前言

本篇是关于 MIT 6.S081-2020-Lab9(File System) 的实现；
如果内容上发现有什么问题请不要吝啬您的键盘。

准备工作

Logging Layer

在文件系统中的 Crash 可能是由文件系统操作过程中发生了电力故障（突然断电）或内核 Panic 引起的。因为文件系统存储在持久层，Crash 之后不希望重启后我们的持久性数据处于不一致或不正确的状态（例如 inode 指向的 data blocks 是空的；或者在 bitmap block 分配了 data blocks 但没有 inode 去引用它们），因此这里就需要 Crash Recovry。

磁盘写操作是我们所关心的，而我们不关心磁盘读操作，因为那对我们的持久性数据的正确性没有任何危害。所以之后提及文件系统操作，我们都会默认是磁盘写操作。提及 xv6 代码，我们都会默认那是相应概念的实现，实现与抽象概念有出入是件很正常的事，所以请前后对照着看。

xv6 从数据库相关技术中借鉴了事务(Transaction) 和日志(Log) 这两个重要的抽象概念。

事务

事务的一个重要性质就是原子性，我们可以将一组磁盘写操作执行顺序封装抽象成一个事务，来保证它要么全部执行，要么全部不执行。并且我们假设，位于磁盘的文件系统中，单个的 block 或 sector 的写是一个原子性操作。

在实现中，我在这里为事务的概念给出另一侧面的解释：给定一系列磁盘写操作，在其中插入 n 个 commit 操作（不要在始末插入），就可以将一系列文件系统操作划分为 n 个事务，分别是事务 1~ 事务 n。而事务 n 之后发生的所有文件系统操作，我们不称它为一个事务，因为没有以 commit 操作收尾。由此可以看到，定界事务的唯一标志，就是看有没有 commit 操作。

在 xv6 中，我们约定一个文件系统调用就是一个事务，具体地，在系统调用后为事务的开始，在系统调用返回前是事务的结束。这一点我们可以在 kernel/sysfile.c 中的 sys_open() 这个系统调用中清晰得看到相应的代码，begin_op() 代表事务的开始，它会做一些事务相关的初始化工作以及一些边界检查；end_op() 代表事务的结束，由它来执行 commit 操作。更多的源码部分解析放到下一个部分中，这一部分更多是概念的介绍。

值得一提的是，为了支持文件系统操作的并发性，xv6 允许多个系统调用封装成一个事务，这在 begin_op() 和 end_op() 的边界检查中都有体现。

日志

Crash recovery 的原理就是通过先前在日志中记录的事务，将其重新执行一遍来达成。所以日志是一个基于事务的持久层技术。不难想象，所有的文件系统操作必须先在日志中留有相应的记录，然后才能真正地写到文件系统中去，不然一旦出现 crash 这些操作都没有记录就无法恢复了。是的，我们会将磁盘划分成两个部分，一个部分就是我们熟知的文件系统，另一个部分则是日志，这一点对理解日志实现很重要。

日志在磁盘中的结构很简单，它包括了一个 header block，和紧随其后的 logged blocks 列表。logged blocks 是文件系统中的 blocks 的拷贝。为什么要拷贝这些 blocks，因为日志需要保存事务开始到结束期间执行的一系列的文件系统操作所涉及的文件系统的 blocks，从而 crash recovery。header block 包含日志的一些元信息，包括 logged blocks 的数量，和每个 logged block 所对应的文件系统 block 的块号。header block 和 logged blocks 中的信息（加粗的这三个）组合起来就是完备地表示一个完整的事务（日志里最多存储一个事务的信息），内核可以只依靠这些信息就能把 crash 发生之前的事务完整地再执行一次，从而实现 crash recovery。

Log Design

这一部分会打开源码来看看日志是如何存储事务的，由于内存中会有磁盘数据结构相应的拷贝，所以为了区分开到底是内存中的数据结构还是磁盘中的数据结构，在有必要时，我会在其前加上定语，如磁盘中的日志、内存中的日志。

xv6 的日志系统是依次靠以下三个事务相关操作来运行的（以下函数均在 kernel/log.c 文件下有定义）：

start transaction
- begin_op(void)
record operation
- log_write(struct buf b*)
end transaction（end_op() 调用 commit()）
1. commit transaction
  - write_log(void) 和 write_head(void)
2. install transaction
  - install_trans(int recovering)
3. clean transaction
  - write_head(void)

接下来将以文件系统调用 sys_open() 为例，来逐一介绍这些函数具体是怎么工作的。

/* kernel/sysfile.c */

uint64
sys_open(void)
{
  char path[MAXPATH];
  int fd, omode;
  struct file *f;
  struct inode *ip;
  int n;

  if((n = argstr(0, path, MAXPATH)) < 0 || argint(1, &omode) < 0)
    return -1;

  begin_op();

  ...        // 此处省略一系列文件系统操作

  end_op();

  return fd;
}

Start Transaction

在 sys_open() 执行文件系统操作之前，它先调用了 begin_op() 来逻辑地表明一个事务的开始：

/* kernel/log.c */

// 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;
    }
  }
}

内存的日志是个全局共享的数据结构，因此在尝试访问 log 的字段前先获取 log.lock。while 循环内部有三个分支，前两个分支是边界检查，第三个分支是执行事务的初始化：

检查 log.committing
- 要看懂这个分支的意义就要搭配 end_op() 一起看。我们不希望在内核线程 A 在执行 commit 操作期间，内核线程 B 还在往内存的日志写文件操作记录。因为这时如果内核线程 A 在执行完 commit 操作之后紧接着发生了 crash，倒霉的将是内核线程 B，因为它只 commit 了一部分的文件操作，这会造成数据的不一致性。内核线程 B 所要做的（也是 begin_op() 所做的）就是在正式开始文件操作之前，先看看当前有没有其它线程在执行 commit 操作。如果有就进入 SLEEP 状态（commit 涉及很多的低速的磁盘操作，所以于其自旋一直占用 CPU 不妨，不如直接 SLEEP 走掉），否则就将执行下一项分支检查。
查看新来的系统调用所产生的一系列事务性操作是否可能会溢出日志的大小限制
- xv6 中的日志是有固定大小限制的，log.lh.n 代表当前已被占用的 logged blocks 的数量，MAXOPBLOCKS 代表一个系统调用能够记录的最大文件系统块数，LOGSIZE 就是日志的大小最大值。如果当前操作有可能会使日志大小溢出，那就 SLEEP 等待别的内核线程 commit 后清空日志记录。这里有个问题就是当我系统调用 write() 一个超大的文件时，日志永远都不会满足这样的请求，因为事务远远超过了日志大小上限。针对这种情况，在 kernel/file.c 下的 filewrite() 可以看到，xv6 会将一个大的 filewrite() 操作（系统调用 sys_write() 是由 filewrite() 实现的）分解成若干个小的 writei() 操作，以至于每个 writei() 操作都不会超出日志大小上限。可能会有疑问，这不会破坏系统调用的原子性吗？但这里是个例外，对于系统调用 sys_write() 来说，遵循的是尽力而为策略，并不要求把所有操作都原子性地写到磁盘中。
事务初始化
- 简单的自增 log.outstanding，代表当前并发的文件系统操作线程多了一个。

Record Operation

当事务开始后，来看看文件系统操作是如何被记录到内存中的日志中的：

/* kernel/log.c */

// Caller has modified b->data and is done with the buffer.
// Record the block number and pin in the cache by increasing refcnt.
// commit()/write_log() will do the disk write.
//
// log_write() replaces bwrite(); a typical use is:
//   bp = bread(...)
//   modify bp->data[]
//   log_write(bp)
//   brelse(bp)
void
log_write(struct buf *b)
{
  int i;

  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");

  acquire(&log.lock);
  for (i = 0; i < log.lh.n; i++) {
    if (log.lh.block[i] == b->blockno)   // log absorbtion
      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);
}

原本的没有日志支撑的文件系统操作处的 bwrite()，现在都会被替换为 log_write()。可以看到 log_write() 做的工作非常少，主要有两个：

在内存中的日志的 header block 中记录下这个文件系统块的块号
- 主要是做一个标记，这时候还没有把内容拷贝到 logged block 中
把这个文件系统块 pin 在 buffer cache 中，防止被 evict 走
- 这一步是为了之后 commit 操作服务的，因为日志需要遵循 write ahead rule，即在 commit 之前，你需要保证所有的文件系统操作都在内存中的日志中，不允许落盘到文件系统。否则中途发生 crash，事务将会被截断，失去了原子性。

第 24 行的 Log absorbtion 意味着当该文件系统块已经被记录过了，就直接中断这次 log_write()，因为这个文件系统操作的结果已经反映在 buffer cache 的 pin 块中了，记录是可以覆盖的。

有了 1 2 步之后，我们就可以通过 header block 中的信息（logged blocks 数量以及从老到新的 logged blocks 块号）和 bread(uint dev, uint blockno) 操作，来依次地把事务内的文件系统操作在内存中完整地复现出来了。

End Transaction

/* kernel/log.c */

// called at the end of each FS system call.
// commits if this was the last outstanding operation.
void
end_op(void)
{
  int do_commit = 0;

  acquire(&log.lock);
  log.outstanding -= 1;
  if(log.committing)
    panic("log.committing");
  if(log.outstanding == 0){
    do_commit = 1;
    log.committing = 1;
  } else {
    // begin_op() may be waiting for log space,
    // and decrementing log.outstanding has decreased
    // the amount of reserved space.
    wakeup(&log);
  }
  release(&log.lock);

  if(do_commit){
    // call commit w/o holding locks, since not allowed
    // to sleep with locks.
    commit();
    acquire(&log.lock);
    log.committing = 0;
    wakeup(&log);
    release(&log.lock);
  }
}

首先当前并发文件系统操作线程数自减。当且仅当当前没有其它执行文件系统操作的线程时，log.committing 才会置 1，并在最后执行 commit 操作。所以一开始如果 log.committing == 1 显然是个错误，因此直接 panic。否则如果当前有其它线程在执行时，我们就唤醒之前在 begin_op() 因为日志大小不足而等待的线程。

最后在 commit 操作执行完之后，再将 log.committing 清空，唤醒之前在 begin_op() 因其它线程正在事务提交而等待的线程。我们接下来看看 commit() 是如何将 log_write() 的输出落盘的，这里是重点。

Commit Transaction

/* kernel/log.c */

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
  }
}

commit() 内部依次四个函数调用，其中前两个调用是完成 Commit Transaction 部分，install_trans(0) 是完成 Install Transaction 部分，最后的 write_head() 是完成 Clear Transaction 部分。

/* kernel/log.c */


// 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);
  }
}

// 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);
}

write_log()
- log.start 是在 mkfs/fs.c 中的 main() 中去设置 super block 的 logstart 字段来指定的，代表磁盘中的日志的 header block 的块号，这里是 2。所以 write_log() 所作的，就是把之前在 log_write() 在 buffer cache 被 pin 的 block 的内容拷贝到磁盘中的日志的 logged block 中。如果在这个时候发生 crash 了，事务将不会被恢复。
write_head()
- 这里就是将内存中的日志的 header block 的内容拷贝到磁盘中的日志的 header block 中。如果在这个时候发生 crash 了，事务可以被恢复。因为在上面 Logging Layer 部分有提及过，事务提交的标志，就是磁盘中的日志的 header block 的 count of logged block > 0。

Install Transaction

/* kernel/log.c */

// Copy committed blocks from log to their home location
static void
install_trans(int recovering)
{
  int tail;

  for (tail = 0; tail < log.lh.n; tail++) {
    struct buf *lbuf = bread(log.dev, log.start+tail+1); // read log block
    struct buf *dbuf = bread(log.dev, log.lh.block[tail]); // read dst
    memmove(dbuf->data, lbuf->data, BSIZE);  // copy block to dst
    bwrite(dbuf);  // write dst to disk
    if(recovering == 0)
      bunpin(dbuf);
    brelse(lbuf);
    brelse(dbuf);
  }
}

install_trans() 所做的工作就是将磁盘中的日志的 logged blocks 内容拷贝到对应的文件系统块中。个人拙见，将读取 logged blocks 的语句和拷贝内容的这两条语句，写在 if(recovering != 0) 的条件下效率可能会更高些，因为那些文件系统块一直都 pin 在 buffer cache 中，直接 bwrite(dbuf) 即可。

install 时内核会遍历所有的 logged blocks，假设 install 遍历到一半时发生了 crash 后，重启恢复时会不会出现错误。答案是并不会，因为恢复时的 install 操作会把先前的落盘记录覆盖掉。因此我们称 install transaction 操作是一种幂等操作，幂等操作执行一次和执行多次的效果是一样的，因此你可以执行任意多次 install transaction 操作。

Clear Transaction

执行 log.lh.n = 0; 语句代表清空内存中的日志的 logged blocks。我们需要调用 write_head() 把在内存中的更新落盘到磁盘中的日志的 header block 上。

至此一个完整的事务通过日志落盘的流程就结束了，其中 Record Operation 和 End Transaction 是最重要的两个步骤。

Inode Layer

Block Allocator

讨论 Inode Layer 时，有个绕不开的话题就是 Block 的分配和释放，因为文件系统系统的所有信息都放在 blocks 上面，而用一个 block 之前你总要分配它，用完后还要释放它，否则将会出现错误。

磁盘中的 bitmap（位视图）用若干个 Blocks 记录了磁盘中所有 block 的使用情况，它首先建立了位的位置和块号的映射关系，然后对应 bitmap 位置 1 时表示该块号的块已被分配，反之为空闲。当磁盘容量很大时，需要多个物理上连续的 bitmap blocks 来表示。这些连续的 bitmap blocks 将组成给一个更大的 bitmap。

/* kernel/fs.c */

// Allocate a zeroed disk block.
static uint
balloc(uint dev)
{
  int b, bi, m;
  struct buf *bp;

  bp = 0;
  for(b = 0; b < sb.size; b += BPB){
    bp = bread(dev, BBLOCK(b, sb));
    for(bi = 0; bi < BPB && b + bi < sb.size; bi++){
      m = 1 << (bi % 8);
      if((bp->data[bi/8] & m) == 0){  // Is block free?
        bp->data[bi/8] |= m;  // Mark block in use.
        log_write(bp);
        brelse(bp);
        bzero(dev, b + bi);
        return b + bi;
      }
    }
    brelse(bp);
  }
  panic("balloc: out of blocks");
}

// Free a disk block.
static void
bfree(int dev, uint b)
{
  struct buf *bp;
  int bi, m;

  bp = bread(dev, BBLOCK(b, sb));
  bi = b % BPB;
  m = 1 << (bi % 8);
  if((bp->data[bi/8] & m) == 0)
    panic("freeing free block");
  bp->data[bi/8] &= ~m;
  log_write(bp);
  brelse(bp);
}

BSIZE 是一个 block 的大小，在 xv6 中是 1024。sb.size 是 super block 中记录的文件系统的大小，单位为 BSIZE。BPB 是 bits per block 的意思，宏展开式为 (BSIZE * 8)。也就是说一个 bitmap block 能够管理的范围也就 1 BPB 个 blocks。BBLOCK(b, sb) 的宏展开式为 (b/BPB + sb.bitmapstart)，意为给定一个块号和 super block 结构体变量，就能返回在这个 super block 的描述下，目标块号 b 是受块号为几的 bitmap block 管理的。

balloc() 的第一层循环就是遍历所有的 bitmap block；第二层循环就是遍历当前 bitmap block 的所有位来找出一个空闲块。bfree() 就是给定块号来在 bitmap 释放它。

Dinode & Inode

inode 的一些基本概念我们已经在上一篇（指源码窥探（5））介绍过了。这里再深入讨论一下，xv6 具体是怎么管理和操作 inode 的。为了方便地操作 inode 对象，xv6 分别分别定义了位于磁盘的 inode（在 kernel/fs.h 下的 struct dinode）和位于内存的 inode（在 kernel/file.h 下的 struct inode）：

/* kernel/fs.h */

// On-disk inode structure
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
};

/* kernel/file.h */

// in-memory copy of an 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];
};

struct dinode 是原原本本存储在磁盘上的 inode 的布局，计算 dinode 的各字段大小和正好是 64字节，可以将 dinode 直接写到 inode block 指定位置中。而 struct inode 则是完全继承了 dinode 的字段设置，这样方便在磁盘读或写的时候，dinode 和 inode 相互之间方便来回转化。我们主要需要关注 dinode.nlink 字段和 inode.ref 字段的语义。dinode.nlink 的数值代表在磁盘中，有多少个目录去引用了这个 inode。当这个字段值为 0 时，内核线程会从磁盘上销毁这个 inode，释放它所关联的 data blocks。inode.ref 的数值代表在内存中，有多少个 C 指针去引用了这个 inode（像 C++ 里智能指针的实现），这里的 C 指针引用可能来自 fd(file descriptor), cwd(current working directory)。当这里的引用数为 0 时，内核线程就会把这个 inode 写回到磁盘中。所以可以看到，这两个字段的值都跟 Inode Layer 无关，而是跟 Inode Layer 的上层有关（Directory Layer, Pathname Layer 和 File Descriptor Layer），所以更多的情况放到介绍上层的时候再说了。

iget()

关于 inode 的操作有很多，它们都在 kennel/fs.c 文件中有定义。除了 bmap()，这些函数名基本都以字符 i 开头或结尾。由于数量众多，这里就挑几个重要来介绍：iget(), ilock(), iput(), itrunc(), iupdate(),。了解完这些几个重要的函数之后，像其它的函数，如 ialloc(), readi(), writei(), bmap(), iunlock() 基本看一遍源码实现留个印象就行。

/* kernel/fs.c */

struct {
  struct spinlock lock;
  struct inode inode[NINODE];
} icache;

// Find the inode with number inum on device dev
// and return the in-memory copy. Does not lock
// the inode and does not read it from disk.
static struct inode*
iget(uint dev, uint inum)
{
  struct inode *ip, *empty;

  acquire(&icache.lock);

  // Is the inode already cached?
  empty = 0;
  for(ip = &icache.inode[0]; ip < &icache.inode[NINODE]; ip++){
    if(ip->ref > 0 && ip->dev == dev && ip->inum == inum){
      ip->ref++;
      release(&icache.lock);
      return ip;
    }
    if(empty == 0 && ip->ref == 0)    // Remember empty slot.
      empty = ip;
  }

  // Recycle an inode cache entry.
  if(empty == 0)
    panic("iget: no inodes");

  ip = empty;
  ip->dev = dev;
  ip->inum = inum;
  ip->ref = 1;
  ip->valid = 0;
  release(&icache.lock);

  return ip;
}

简单解释一个问题：我们在做上一个实验的时候碰到过类似的问题，内核线程它不像用户线程一样能以字节为单位分配动态内存，所以我们当时用了一个全局的固定大小的静态数组解决分配哈希表项的问题。这里也是差不多的道理，虽然变量名叫 icache，但它不像 buffer cache 一样是为了缓存 inode 从而解决访问速度差异而开的 inode 数组，这里只是单纯地没有动态分配 inode 的方法而选择静态分配而已。inode cache 和 buffer cache 都在内存，因此用缓存解决访问速度差异的角度来解释是不合理的。

iget() 在这里做的工作很少，它先是去看 icache 是否有已有对应 inode，有的话返回它，没有的话简单初始化一下在返回。

ilock()

iget() 并没有与磁盘做任何的交互，而是负责内存这一侧的 inode 初始化工作。因此要想获得一个真实可用的 inode，我们需要搭配另一个函数来将内存 inode 与磁盘 inode 对应起来，它就是 ilock()：

/* kernel/fs.c */


// Lock the given inode.
// Reads the inode from disk if necessary.
void
ilock(struct inode *ip)
{
  struct buf *bp;
  struct dinode *dip;

  if(ip == 0 || ip->ref < 1)
    panic("ilock");

  acquiresleep(&ip->lock);

  if(ip->valid == 0){
    bp = bread(ip->dev, IBLOCK(ip->inum, sb));
    dip = (struct dinode*)bp->data + ip->inum%IPB;
    ip->type = dip->type;
    ip->major = dip->major;
    ip->minor = dip->minor;
    ip->nlink = dip->nlink;
    ip->size = dip->size;
    memmove(ip->addrs, dip->addrs, sizeof(ip->addrs));
    brelse(bp);
    ip->valid = 1;
    if(ip->type == 0)
      panic("ilock: no type");
  }
}

在磁盘中，inode 是按照 inode number 由小到大的顺序依次在 inode blocks 连续存储的，每个 inode block 可以最多放 16（IPB = BSZIE / sizeof(struct dinode)）个 inode。因此给定 inode blocks 的起始块号和一个目标 inode number，就可以准确定位这个 inode number 对应的 inode 在磁盘块中的位置，这也是 IBLOCK 宏所锁的事情。

在内核中，任意一处要想使用某个 inode 之前，都需要通过 ilock() 获取这个 inode 的锁，使用完后再通过 iunlock() 释放这个 inode 锁。

/* kernel/fs.c */

// Copy a modified in-memory inode to disk.
// Must be called after every change to an ip->xxx field
// that lives on disk, since i-node cache is write-through.
// Caller must hold ip->lock.
void
iupdate(struct inode *ip)
{
  struct buf *bp;
  struct dinode *dip;

  bp = bread(ip->dev, IBLOCK(ip->inum, sb));
  dip = (struct dinode*)bp->data + ip->inum%IPB;
  dip->type = ip->type;
  dip->major = ip->major;
  dip->minor = ip->minor;
  dip->nlink = ip->nlink;
  dip->size = ip->size;
  memmove(dip->addrs, ip->addrs, sizeof(ip->addrs));
  log_write(bp);
  brelse(bp);
}

当我们想把对内存 inode 的更新落盘时，调用 iupdate() 即可。

itrunc()

/* kernel/fs.c */

// Truncate inode (discard contents).
// Caller must hold ip->lock.
void
itrunc(struct inode *ip)
{
  int i, j;
  struct buf *bp;
  uint *a;

  for(i = 0; i < NDIRECT; i++){
    if(ip->addrs[i]){
      bfree(ip->dev, ip->addrs[i]);
      ip->addrs[i] = 0;
    }
  }

  if(ip->addrs[NDIRECT]){
    bp = bread(ip->dev, ip->addrs[NDIRECT]);
    a = (uint*)bp->data;
    for(j = 0; j < NINDIRECT; j++){
      if(a[j])
        bfree(ip->dev, a[j]);
    }
    brelse(bp);
    bfree(ip->dev, ip->addrs[NDIRECT]);
    ip->addrs[NDIRECT] = 0;
  }

  ip->size = 0;
  iupdate(ip);
}

itrunc() 是从磁盘上释放这个 inode 所关联的所有的 data blocks。我们在上一篇介绍过，inode 的 data blocks 是一级索引分配和二级索引分配策略混合的策略，第 0~NDIRECT-1 个 data blocks 是直接 data blocks，第 NDIRECT 个 data block 是索引 data block，这个索引 data block 里依次存有所有二级 data blocks 的 block number，就像下面这个图演示的一样：

因此 itrunc() 的工作流程是，先释放 direct data blocks，再释放 indirect data block，最后将 inode 的 size 置 0 后调用 iupdate() 将对以上 indoe 的更新落盘。

iput()

/* kernel/fs.c */

// Drop a reference to an in-memory inode.
// If that was the last reference, the inode cache entry can
// be recycled.
// If that was the last reference and the inode has no links
// to it, free the inode (and its content) on disk.
// All calls to iput() must be inside a transaction in
// case it has to free the inode.
void
iput(struct inode *ip)
{
  acquire(&icache.lock);

  if(ip->ref == 1 && ip->valid && ip->nlink == 0){
    // inode has no links and no other references: truncate and free.

    // ip->ref == 1 means no other process can have ip locked,
    // so this acquiresleep() won't block (or deadlock).
    acquiresleep(&ip->lock);

    release(&icache.lock);

    itrunc(ip);
    ip->type = 0;
    iupdate(ip);
    ip->valid = 0;

    releasesleep(&ip->lock);

    acquire(&icache.lock);
  }

  ip->ref--;
  release(&icache.lock);
}

iput() 会减少一个内存 inode 的引用数。当引用数减为 0，且 dinode 的链接数也为 0 时，iput() 就会调用 itrunc() 和 iupdate() 来释放回收这个 inode。

其它操作

下面的几个操作都是调用上面的基本操作来完成实现的。

bmap()
- bmap() 和 itrunc() 可以说是一对互逆操作。bmap() 的作用是给定一个 inode，就返回第 bn 个 data block 的块号。
iunlock()
- 释放先前在 ilock() 获取的互斥锁，当前线程放弃对内存 inode 的引用。
ialloc()
- 遍历磁盘的 inode，找到一个空闲的 inode 之后（type == 0 代表空闲），将其 type 字段设置为指定值，最后调用 iget() 在内存中分配这个 inode。
readi()
- 给定一个 inode、是否为物理地址(user_dst)、内存地址(dst)、文件偏移(off) 以及读入的字节数 n ，readi() 将从 inode 关联的 data 的 user_dst+off 开始拷贝 n 个字节到 dst 处。
writei()
- 与 readi() 是互逆操作，基本流程相似。

Directory Layer

我们说 inode 通过设置它的 type 字段的值，使它即可以指向一个文件，也可以指向一个目录。当指向一个文件时，这个 inode 关联的 data blocks 中存放的都是这个文件的内容；当指向一个文件时，这个 inode 关联的 data blocks 中存放的都是目录项(struct dirent）：

/* kernel/fs.h */

struct dirent {
  ushort inum;
  char name[DIRSIZ];
};

dirent.inum 指向的是下一个 inode，没人知道这下一个 inode 的类型到底还是一个目录或是文件。也就是说，目录里面可以包含很多个文件和很多个目录，这就像平时用 Windows 资源管理器随便打开某个目录查看这个目录下的目录项一样：

/* kernel/fs.c */

// Look for a directory entry in a directory.
// If found, set *poff to byte offset of entry.
struct inode*
dirlookup(struct inode *dp, char *name, uint *poff)
{
  uint off, inum;
  struct dirent de;

  if(dp->type != T_DIR)
    panic("dirlookup not DIR");

  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);
    }
  }

  return 0;
}

dirlookup() 的作用就是给定一个 inode 和带查询的目录项名称，返回目标目录项指向的 inode（即可能是文件也可能是目录）。返回的 inode 即没有上锁，也没和 dinode 关联，所以可以看作是仅返回一个目标 inode number。

dirlookup() 的工作就是很简单地遍历读取给定 inode 的所有目录项，找到名字完全匹配的目录项，最后获取并返回目标目录项指向的 inode。另外这个函数还有个副作用就是要设置参数 *poff 的值为目标目录项在给定目录的字节偏移数（假设目标目录项是该目录下的第 i 个目录项，那么 *poff = i * sizeof(struct dirent)）。

dirlink() 的作用是给定目录 inode，在该目录下创建一个新的目录项（给定目录项名称和目录项指向的 inode 的 inode number）。实现很简单所以介绍略过。

Pathname Layer

Pathname Layer 提供的是路径解析的服务，主要有两种需求，例如当解析路径 /a/b/c：

struct inode* namei(char *path)
- namei() 会将给定 path 解析到底，因此返回 c 的 inode，这里的 c 的类型既可以是文件可以是目录。
struct inode* nameiparent(char *path, char *name)
- nameiparent() 会将给定 path 解析到最后一个的前一个名称，因此返回 b 的 inode，注意到这里的 b 的类型一定是个目录。

由于 namei() 和 nameiparent() 做的工作很相近，它们都是通过 namex() 来实现的：

/* kernel/fs.c */

// Look up and return the inode for a path name.
// If parent != 0, return the inode for the parent and copy the final
// path element into name, which must have room for DIRSIZ bytes.
// Must be called inside a transaction since it calls iput().
static struct inode*
namex(char *path, int nameiparent, char *name)
{
  struct inode *ip, *next;

  if(*path == '/')
    ip = iget(ROOTDEV, ROOTINO);
  else
    ip = idup(myproc()->cwd);

  while((path = skipelem(path, name)) != 0){
    ilock(ip);
    if(ip->type != T_DIR){
      iunlockput(ip);
      return 0;
    }
    if(nameiparent && *path == '\0'){
      // Stop one level early.
      iunlock(ip);
      return ip;
    }
    if((next = dirlookup(ip, name, 0)) == 0){
      iunlockput(ip);
      return 0;
    }
    iunlockput(ip);
    ip = next;
  }
  if(nameiparent){
    iput(ip);
    return 0;
  }
  return ip;
}

需要注意的是，我在第 23 被运算符优先级困扰了很久，最好是改成 if(nameiparent && (*path == '\0')){ 这样的写法，否则容易造成误解。

skipelem() 的作用是提取 path 的一个名字前缀作为名词，剩余的部分作为返回值。它内部都是字符串操作，不详细介绍，但源码中这个函数的注释给出使用例：

// Examples:
//   skipelem("a/bb/c", name) = "bb/c", setting name = "a"
//   skipelem("///a//bb", name) = "bb", setting name = "a"
//   skipelem("a", name) = "", setting name = "a"
//   skipelem("", name) = skipelem("////", name) = 0

对路径进行解析时，namex() 在返回结果前，会依次增加再减少 ip 的引用值。这是为了内核线程 A 在操作 ip 时，内核线程 B 想要删除这个 ip。假设不去增加 ip 的引用值，又不巧 ip 是最后一级 inode（意味着 ip->nlink == 0），那么就会去释放掉这个 ip，这对内核线程 A 来说是个错误。

值得一提的是，锁的粒度降低为了一个 inode，这得以多个线程可以并发地进行路径检索，前提是它们不要恰好解析同一个 inode。并且在 namex() 解析的时候，同一时刻只能获取一个路径上 inode 的锁，因为如果遇到了 . 这样的名字，会重复获取两次互斥锁而造成死锁（xv6 只能检测重复获取两次自旋锁造成的死锁（检测到后直接 panic），而这里互斥锁死锁会直接停止运行）。

File Descriptor Layer

File Descriptor Layer 将内核的大部分资源，如 inode 和 pipe，都抽象成了文件(struct file)，并提供了一个统一的接口，如打开(filealloc() 和 filedup())、读(fileread())、写(filewrite())、关闭(fileclose())。

/* kernel/file.h */

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
};

之所能将这些都抽象为了文件并且提供统一的操作，是因为它们都跟 I/O 相关，因此 struct file 还必须记录 I/O offset（事实上 pipe 没有 I/O offset 这种概念），以及其它一些属性，如可读可写。

每打开一个资源都会创建这个资源的文件实例，不同文件实例都是相互独立的，就算是同一个资源的实例，这些实例间也能有不同的 I/O offset。

内核中有一个全局的 filetable 用来保存和管理所有进程打开和关闭过的文件：

/* kernel/file.h */

struct {
  struct spinlock lock;
  struct file file[NFILE];
} ftable;

每个进程也都有自己的局部的 filetable，用来保存和管理该进程打开过的所有文件：

/* kernel/proc.h */

// Per-process state
struct proc {
  ...
  struct file *ofile[NOFILE];  // Open files
  struct inode *cwd;           // Current directory
  ...
};

被打开的文件的文件描述符，指的就是当前进程 myproc()->ofile 里的对应文件的索引。

实验部分

Large files

把跟宏 NINDIRECT 有关的地方扩展一下就好了。

首先是修改下宏定义：

/* kernel/fs.h */

#define NDIRECT 11
#define NINDIRECT (BSIZE / sizeof(uint))
#define MAXFILE (NDIRECT + NINDIRECT + NINDIRECT*NINDIRECT)

既然改变了 NDIRECT 的大小，又由于实验指导书上说不必修改 inode 关联的 data blocks 的个数，需要再把 struct inode 和 struct dinode 这两处 addrs 数组的大小改为 NDIRECT+2 即可。

最后 bmap() 和 itrunc() 的修改逻辑依葫芦画瓢描就完事了。

/* kernel/fs.c */

static uint
bmap(struct inode *ip, uint bn)
{
  uint addr, *a;
  struct buf *bp;

  if(bn < NDIRECT){
    if((addr = ip->addrs[bn]) == 0)
      ip->addrs[bn] = addr = balloc(ip->dev);
    return addr;
  }
  bn -= NDIRECT;

  if(bn < NINDIRECT){
    // Load indirect block, allocating if necessary.
    if((addr = ip->addrs[NDIRECT]) == 0)
      ip->addrs[NDIRECT] = addr = balloc(ip->dev);
    bp = bread(ip->dev, addr);
    a = (uint*)bp->data;
    if((addr = a[bn]) == 0){
      a[bn] = addr = balloc(ip->dev);
      log_write(bp);
    }
    brelse(bp);
    return addr;
  }

  bn -= NINDIRECT;

  if (bn < NINDIRECT*NINDIRECT) {
    if ((addr = ip->addrs[NDIRECT+1]) == 0)
      ip->addrs[NDIRECT+1] = addr = balloc(ip->dev);
    bp = bread(ip->dev, addr);
    a = (uint*)bp->data;
    if ((addr = a[bn/NINDIRECT]) == 0) {
      a[bn/NINDIRECT] = addr = balloc(ip->dev);
      log_write(bp);
    }
    brelse(bp);

    bn %= NINDIRECT;
    bp = bread(ip->dev, addr);
    a = (uint*)bp->data;
    if ((addr = a[bn]) == 0) {
      a[bn] = addr = balloc(ip->dev);
      log_write(bp);
    }
    brelse(bp);
    return addr;
  }

  panic("bmap: out of range");
}


void
itrunc(struct inode *ip)
{
  int i, j;
  struct buf *bp;
  uint *a;

  for(i = 0; i < NDIRECT; i++){
    if(ip->addrs[i]){
      bfree(ip->dev, ip->addrs[i]);
      ip->addrs[i] = 0;
    }
  }

  if(ip->addrs[NDIRECT]){
    bp = bread(ip->dev, ip->addrs[NDIRECT]);
    a = (uint*)bp->data;
    for(j = 0; j < NINDIRECT; j++){
      if(a[j]) {
        bfree(ip->dev, a[j]);
        a[j] = 0;
      }
    }
    brelse(bp);
    bfree(ip->dev, ip->addrs[NDIRECT]);
    ip->addrs[NDIRECT] = 0;
  }

  if (ip->addrs[NDIRECT+1]) {
    bp = bread(ip->dev, ip->addrs[NDIRECT+1]);
    a = (uint*)bp->data;
    for (j = 0; j < NINDIRECT; ++j) {
      if (a[j]) {
        int k;
        struct buf *_bp;
        uint *_a;

        _bp = bread(ip->dev, a[j]);
        _a = (uint*)_bp->data;
        for (k = 0; k < NINDIRECT; ++k) {
          if (_a[k]) {
            bfree(ip->dev, _a[k]);
            _a[k] = 0;
          }
        }
        brelse(_bp);
        bfree(ip->dev, a[j]);
        a[j] = 0;
      }
    }
    brelse(bp);
    bfree(ip->dev, ip->addrs[NDIRECT+1]);
    ip->addrs[NDIRECT+1] = 0;
  }


  ip->size = 0;
  iupdate(ip);
}

Symbolic links

符号链接类似于 Windows 里的快捷方式，本质上就是个存放目标文件的绝对路径名称的文件：

int symlink(char *target, char *path) 中，target 就是这里的“目标”，path 就是这里的“起始位置”。在 user/usys.pl, user/user.h, kernel/syscall.c 和 Makefile 中添加必要的 symlink() 的系统调用代码后，依照实验指导书修改必要的宏以及实现即可：

/* kernel/sysfile.c */


uint64
sys_open(void)
{
  ...
  if(omode & O_CREATE){
  ...
  } else {
  ...
  }

  if (!(omode & O_NOFOLLOW) && ip->type == T_SYMLINK) {
    char path[MAXPATH];
    int depth = 0;

    while (ip->type == T_SYMLINK) {
      if (++depth == 10) {
        iunlockput(ip);
        end_op();
        return -1;
      }

      readi(ip, 0, (uint64)path, 0, MAXPATH);
      iunlockput(ip);

      if ((ip = namei(path)) == 0) {
        end_op();
        return -1;
      }

      ilock(ip);
    }
  }
  ...
}


uint64
sys_symlink(void)
{
  char path[MAXPATH], target[MAXPATH];

  if(argstr(0, target, MAXPATH) < 0 || argstr(1, path, MAXPATH) < 0){
    return -1;
  }

  begin_op();

  struct inode *ip;

  if ((ip = create(path, T_SYMLINK, 0, 0)) == 0) {
    end_op();
    return -1;
  }

  writei(ip, 0, (uint64)target, 0, MAXPATH);

  iunlockput(ip);
  end_op();

  return 0;
}

比较容易踩坑的是 writei() 和 readi() 的参数顺序，注意不要填错了。

后记

刑满一年释放回家了（指在学校不间断待了将近一年，但学校寒假不让留人迫不得已回家），不用关心学校里那一堆破事（指 OOAD 实践和 IoT 课设论文），开始有点时间做点自己能做的事情了。

这个实验总的来说，做之前要看的东西理解清晰，实验部分就可以做得很快，是一个理解准备工作部分更重要的实验。

回头有时间再把文件系统调用（kernel/sysfile.c 下面那一堆操作）的一些内容看看。

thinkingear

【xv6 源码窥探（6）】文件系统

前言