Lec 14,15 文件系统
当我们向 文件 append 一个单词时，背后发生了啥？
一， 找到父亲文件夹的inode
- 首先我们可能会打开（没有的时候创建一个文件），这个是通过在用户空间调用
fd = open(name, O_CREATE | O_RDWR);实现的。 - 接下来会去定位到这个路径下的dir，他会从当前路径的inode，往下一路寻找。直到找到这个文件上一级的inode，就是这个文件上一级dir的inode。
struct inode {
uint dev; // Device number
uint inum; // Inode number
int ref; // Reference count
struct sleeplock lock; // protects everything below here
int valid; // inode has been read from disk?
short type; // copy of disk inode
short major;
short minor;
short nlink;
uint size;
uint addrs[NDIRECT+1];
};
- 下面讲解下找
inode的过程
1705635681264.png
上图中，inode块里，存的是这样的数据结构的内容：
struct dinode {
short type; // File type
short major; // Major device number (T_DEVICE only)
short minor; // Minor device number (T_DEVICE only)
short nlink; // Number of links to inode in file system
uint size; // Size of file (bytes)
uint addrs[NDIRECT+1]; // Data block addresses
};
我们需要把inode磁盘上的数据加载进内存里缓存起来（注，这里读的不是磁盘上的文件内容，而是inode的内容，也就是文件里会存dinode这个数据结构里的几个数据），这个就是ilock这个方法做的事情。所以这里会第一次读磁盘（存在bcache里）
a. 首先通过下面代码定位当前inode, 一种路径是绝对路径，一种是相对路径。
if(*path == '/')
ip = iget(ROOTDEV, ROOTINO);
else
ip = idup(myproc()->cwd);
b. 循环弹出，每一级folder 的 folder名。 如a/b/c， 就依次遍历a,b,c
c. 当前inode必为dir, 查找弹出的名字，如a
d. 得到新的inode，继续循环，知道到最后一级（不再是dir,是文件了），不再查找文件，直接返回父亲dir 的inode
- 下面讲解下在dir
inode中找下一级inode的过程
1705639931332.png
for(off = 0; off < dp->size; off += sizeof(de)){
if(readi(dp, 0, (uint64)&de, off, sizeof(de)) != sizeof(de))
panic("dirlookup read");
if(de.inum == 0)
continue;
if(namecmp(name, de.name) == 0){
// entry matches path element
if(poff)
*poff = off;
inum = de.inum;
return iget(dp->dev, inum);
}
}
a. 首先我们需要读取当前dir inode里的数据，因为dir存的就是下面有哪些dir或文件。我们要判断我们这个文件名在不在里面，以及在什么位置。dir文件内容是由下面的数据结构组成的。inum 就是子文件或子DIR的inode编号
struct dirent {
ushort inum;
char name[DIRSIZ];
};
所以可以看到for 循环每次off += sizeof(de)
b. 那么有了偏移量和inode，就可以计算数据在磁盘上的物理地址. 就是用offset/BSIZE,得到一个序号，这个序号就可以从inode的addrs， 找到对应磁盘的地址了。
c. 然后就是读取磁盘的地址，有可能一个dirent ，会跨2个BBLOCK，所以我们要注意这种可能。这也是下面代码m的作用：
for(tot=0; tot<n; tot+=m, off+=m, dst+=m){
uint addr = bmap(ip, off/BSIZE);
if(addr == 0)
break;
bp = bread(ip->dev, addr);
m = min(n - tot, BSIZE - off%BSIZE);
if(either_copyout(user_dst, dst, bp->data + (off % BSIZE), m) == -1) {
brelse(bp);
tot = -1;
break;
}
brelse(bp);
}
- 综上我们成功找到了要创建/打开的文件的父文件夹目录。
二， 创建并返回文件inode
- 先用同样的方法遍历父文件夹下有没有这个文件的文件名，有的话，直接返回该文件名的inode （实际只需要inum，其余的属性会在ilock时去文件系统读）
- 如果不存在，就代表要创建一个新文件，那么就调用
ialloc
struct inode*
ialloc(uint dev, short type)
{
int inum;
struct buf *bp;
struct dinode *dip;
for(inum = 1; inum < sb.ninodes; inum++){
bp = bread(dev, IBLOCK(inum, sb));
dip = (struct dinode*)bp->data + inum%IPB;
if(dip->type == 0){ // a free inode
memset(dip, 0, sizeof(*dip));
dip->type = type;
log_write(bp); // mark it allocated on the disk
brelse(bp);
return iget(dev, inum);
}
brelse(bp);
}
printf("ialloc: no inodes\n");
return 0;
}
- 读取inum所属的那个inode文件，找到对应偏移量，判断是不是freenode，是的话，就可以用来创建了。这边有一个读取inode区域的读磁盘操作。
三，关联file 和 fd
- 在ftable 里加一个新的file 的数据结构
struct file {
enum { FD_NONE, FD_PIPE, FD_INODE, FD_DEVICE } type;
int ref; // reference count
char readable;
char writable;
struct pipe *pipe; // FD_PIPE
struct inode *ip; // FD_INODE and FD_DEVICE
uint off; // FD_INODE
short major; // FD_DEVICE
};
// Allocate a file structure.
struct file*
filealloc(void)
{
struct file *f;
acquire(&ftable.lock);
for(f = ftable.file; f < ftable.file + NFILE; f++){
if(f->ref == 0){
f->ref = 1;
release(&ftable.lock);
return f;
}
}
release(&ftable.lock);
return 0;
}
- 在该进程下找到一个空闲的fd去存储这个file
static int
fdalloc(struct file *f)
{
int fd;
struct proc *p = myproc();
for(fd = 0; fd < NOFILE; fd++){
if(p->ofile[fd] == 0){
p->ofile[fd] = f;
return fd;
}
}
return -1;
}
- 配置file的ip(inode)
f->ip = ip;
f->readable = !(omode & O_WRONLY);
f->writable = (omode & O_WRONLY) || (omode & O_RDWR);
- 返回文件描述符到用户空间。 （此时文件描述符可以找到file, file可以找到inode， inode下可以找到file的metadata, 和data在磁盘上的地址。
四，开始写一个单词
-
现在我们在用户空间可以向fd 写一些数据，具体操作如
write(fd, (void*)addr, 8192);分别描述向哪个文件描述符，从addr开始把里面8192长度的数据写进fd所属的文件里。 -
锁定inode, 写数据，解锁inode
if(f->type == FD_INODE){
// write a few blocks at a time to avoid exceeding
// the maximum log transaction size, including
// i-node, indirect block, allocation blocks,
// and 2 blocks of slop for non-aligned writes.
// this really belongs lower down, since writei()
// might be writing a device like the console.
int max = ((MAXOPBLOCKS-1-1-2) / 2) * BSIZE;
int i = 0;
while(i < n){
int n1 = n - i;
if(n1 > max)
n1 = max;
begin_op();
ilock(f->ip);
if ((r = writei(f->ip, 1, addr + i, f->off, n1)) > 0)
f->off += r;
iunlock(f->ip);
end_op();
if(r != n1){
// error from writei
break;
}
i += r;
}
ret = (i == n ? n : -1);
}
上面可以隐式看到 文件的off 被维护住了，随着写的发生，off值相应增大。
- writei 就是根据off 去查在inode的哪个addr里，取到addr，把它从磁盘读进缓存，然后开始向缓存buf写数据.
- 最后更新inode的size 为新的off, 然后写回磁盘的inode区域
int
writei(struct inode *ip, int user_src, uint64 src, uint off, uint n)
{
uint tot, m;
struct buf *bp;
if(off > ip->size || off + n < off)
return -1;
if(off + n > MAXFILE*BSIZE)
return -1;
for(tot=0; tot<n; tot+=m, off+=m, src+=m){
uint addr = bmap(ip, off/BSIZE);
if(addr == 0)
break;
bp = bread(ip->dev, addr);
m = min(n - tot, BSIZE - off%BSIZE);
if(either_copyin(bp->data + (off % BSIZE), user_src, src, m) == -1) {
brelse(bp);
break;
}
log_write(bp);
brelse(bp);
}
if(off > ip->size)
ip->size = off;
// write the i-node back to disk even if the size didn't change
// because the loop above might have called bmap() and added a new
// block to ip->addrs[].
iupdate(ip);
return tot;
}
综上，我们完成了向文件系统写一个单词的操作。当然具体的落盘会由log取真正的保证。下面我们会去讲解LOG的部分。。
我们这里来回顾一下，当我们往文件里写一个单词会发生什么？
- 首先，要定位路径父亲的inode，这里会用到
itable这个缓存，如果没在缓存里找到，那么会建一个新的条目放进itable里，并且之后通过ilock方法，会根据inum把这个inode相关缺失的属性从文件系统中的inode区域里读出来。 - 当处理dir的inode时，他的数据存放的其实是这个DIR下所有的其他INUM。我们依次遍历找到名字可以对的上的INUM，然后用这个inum用步骤1去找到对应的inode.
- 如果名字没有匹配，需要创建时,通过在文件系统的inode区域找到一个空闲的inode，进行写入。
- 那么文件的inode创建出来后，就会在进程下找到一个空闲的
fd去关联这个file, file里面最重要的就是这个inode - 这个inode 具体文件内容写的地址，会在调用
readi或writei时调用bmap的时候，用balloc去分配 - bmap返回一个
addr, 随后会调用bread去读这个addr( 也就是blockno) - cache层会先找到一个可用的cache，然后把内容从磁盘读进cache里，之后就是操作内存。
- 最后通过
log的记录会进行数据落盘
Log是如何工作的？
这里的思想是，在任何一个写操作前，我们会先记这个写操作到LOG里. 然后通过写一条commit的标志，表示前面的操作要么全执行成功，要么全部不执行（如果没有commit标志，前面的LOG全部丢弃）
那么在任意时间断电，我们就可以去读取LOG FILE，根据里面的COMMIT的标志，来恢复数据了。
在XV6中，以创建文件的sys_open为例（在sysfile.c文件中）每个文件系统操作，都有begin_op和end_op分别表示事物的开始和结束。在end_op中会实现commit操作。
中间的写log操作
void
log_write(struct buf *b)
{
int i;
acquire(&log.lock);
if (log.lh.n >= LOGSIZE || log.lh.n >= log.size - 1)
panic("too big a transaction");
if (log.outstanding < 1)
panic("log_write outside of trans");
for (i = 0; i < log.lh.n; i++) {
if (log.lh.block[i] == b->blockno) // log absorption
break;
}
log.lh.block[i] = b->blockno;
if (i == log.lh.n) { // Add new block to log?
bpin(b);
log.lh.n++;
}
release(&log.lock);
}
这里其实只是更新了log.lh 的总size（也就是有几个BLOCK 需要落盘，然后存放了哪几个）
比如写block 45，我们已经更新了block cache中的block 45。接下来我们需要在内存中记录，在稍后的commit中，要将block 45写入到磁盘的log中。
这里的代码先获取log header的锁，之后再更新log header。首先代码会查看block 45是否已经被log记录了。如果是的话，其实不用做任何事情，因为block 45已经会被写入了。这种忽略的行为称为log absorbtion。如果block 45不在需要写入到磁盘中的block列表中，接下来会对n加1，并将block 45记录在列表的最后。
下面我们看下commit函数，是怎么实现的
static void
commit()
{
if (log.lh.n > 0) {
write_log(); // Write modified blocks from cache to log
write_head(); // Write header to disk -- the real commit
install_trans(0); // Now install writes to home locations
log.lh.n = 0;
write_head(); // Erase the transaction from the log
}
}
首先是write_log。这基本上就是将所有存在于内存中的log header中的block编号对应的block，从block cache写入到磁盘上的log区域中（注，也就是将变化先从内存拷贝到log中）。
write_head会将内存中的log header写入到磁盘中。
// Copy modified blocks from cache to log.
static void
write_log(void)
{
int tail;
for (tail = 0; tail < log.lh.n; tail++) {
struct buf *to = bread(log.dev, log.start+tail+1); // log block
struct buf *from = bread(log.dev, log.lh.block[tail]); // cache block
memmove(to->data, from->data, BSIZE);
bwrite(to); // write the log
brelse(from);
brelse(to);
}
}
依次遍历log中记录的block，并写入到log中。它首先读出log block，将cache中的block拷贝到log block，最后再将log block写回到磁盘中。这样可以确保需要写入的block都记录在文件系统的log区域中。
但是在这个位置，我们还没有commit，现在我们只是将block存放在了log中。如果我们在这个位置也就是在write_head之前crash了，那么最终的表现就像是transaction从来没有发生过。
接下来看一下write_head函数，我之前将write_head称为commit point。
// Write in-memory log header to disk.
// This is the true point at which the
// current transaction commits.
static void
write_head(void)
{
struct buf *buf = bread(log.dev, log.start);
struct logheader *hb = (struct logheader *) (buf->data);
int i;
hb->n = log.lh.n;
for (i = 0; i < log.lh.n; i++) {
hb->block[i] = log.lh.block[i];
}
bwrite(buf);
brelse(buf);
}
上面的bwrite，就是真正的commit point. 在这部之前crash, 都会像transaction从来没有发生过一样。
install_trans实际上就是将block数据从log中拷贝到了实际的文件系统block中。当然，可能在这里代码的某个位置会出现问题，但是这应该也没问题，因为在恢复的时候，我们会从最开始重新执行过。
灾难恢复
initlog基本上就是调用recover_from_log函数。
static void
recover_from_log(void)
{
read_head();
install_trans(1); // if committed, copy from log to disk
log.lh.n = 0;
write_head(); // clear the log
}
recover_from_log先调用read_head函数从磁盘中读取header，之后调用install_trans函数。这个函数之前在commit函数中也调用过，它就是读取log header中的n，然后根据n将所有的log block拷贝到文件系统的block中。recover_from_log在最后也会跟之前一样清除log。
xv6文件系统的三个挑战
1. Cache Eviction 问题
- 问题描述：当进行中的事务需要更新一个数据块（如block 45），而缓冲区（buffer cache）已满时，系统可能需要撤回（evict）这个刚刚更新的数据块以腾出空间。如果这时直接将更新后的数据块写回磁盘，会违反事务的原子性和前写规则（write ahead rule）。前写规则要求在实际更新文件系统的数据块之前，必须先将所有更改写入日志。
- 解决方案：通过引用计数来“固定”（pin）相关的数据块在缓冲区中，避免它们被撤回，直到相关的日志条目被写入，从而保证了数据的一致性和事务的原子性。
2. 文件系统操作与日志大小的适配问题
- 问题描述：在XV6文件系统中，日志的大小是固定的（例如，30个数据块），这意味着所有文件系统操作都必须适应这个日志大小。如果一个操作尝试写入超过日志容量的数据块，将违反前写规则。
- 解决方案：将大的文件系统操作分割成多个小的操作，每个小操作作为独立的事务处理，并逐个写入日志。虽然这意味着大的写操作不是原子的，但它遵守了不破坏文件系统一致性的原则。
3. 并发文件系统调用的挑战
- 问题描述：如果有多个并发执行的事务同时占用日志空间，可能会导致日志空间用尽，而没有任何一个事务能够完全完成。这种情况下，如果提交任何一个部分完成的事务，都将违反前写规则，因为这样会提交一个不完整的事务。
- 解决方案：XV6通过限制同时进行的文件系统操作的数量来解决这个问题。如果当前有太多操作正在执行，在begin_op中, 系统会暂停新的文件系统操作，直到足够多的操作完成并提交（commit）。这种方法有时被称为“组提交”（group commit），因为它允许多个操作像一个大事务一样同时提交，确保它们要么全部成功，要么全部失败，从而保证了事务的原子性和系统的一致性。
// called at the start of each FS system call.
void
begin_op(void)
{
acquire(&log.lock);
while(1){
if(log.committing){
sleep(&log, &log.lock);
} else if(log.lh.n + (log.outstanding+1)*MAXOPBLOCKS > LOGSIZE){
// this op might exhaust log space; wait for commit.
sleep(&log, &log.lock);
} else {
log.outstanding += 1;
release(&log.lock);
break;
}
}
}
