前言

• 本篇是对于 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 文件下有定义）：

1. start transaction

   • begin_op(void)

2. record operation

   • log_write(struct buf b*)

3. 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 循环外部有三个分支，前两个分支是边界查看，第三个分支是执行事务的初始化：

1. 查看 log.committing

   • 要看懂这个分支的意义就要搭配 end_op() 一起看。咱们不心愿在内核线程 A 在执行 commit 操作期间，内核线程 B 还在往内存的日志写文件操作记录。因为这时如果内核线程 A 在执行完 commit 操作之后紧接着产生了 crash，晦气的将是内核线程 B，因为它只 commit 了一部分的文件操作，这会造成数据的不一致性。内核线程 B 所要做的（也是 begin_op() 所做的）就是在正式开始文件操作之前，先看看以后有没有其它线程在执行 commit 操作。如果有就进入 SLEEP 状态（commit 波及很多的低速的磁盘操作，所以于其自旋始终占用 CPU 无妨，不如间接 SLEEP 走掉），否则就将执行下一项分支查看。

2. 查看新来的零碎调用所产生的一系列事务性操作是否可能会溢出日志的大小限度

   • xv6 中的日志是有固定大小限度的，log.lh.n 代表以后已被占用的 logged blocks 的数量，MAXOPBLOCKS 代表一个零碎调用可能记录的最大文件系统块数，LOGSIZE 就是日志的大小最大值。如果以后操作有可能会使日志大小溢出，那就 SLEEP 期待别的内核线程 commit 后清空日志记录。这里有个问题就是当我零碎调用 write() 一个超大的文件时，日志永远都不会满足这样的申请，因为事务远远超过了日志大小下限。针对这种状况，在 kernel/file.c 下的 filewrite() 能够看到，xv6 会将一个大的 filewrite() 操作（零碎调用 sys_write() 是由 filewrite() 实现的）分解成若干个小的 writei() 操作，以至于每个 writei() 操作都不会超出日志大小下限。可能会有疑难，这不会毁坏零碎调用的原子性吗？但这里是个例外，对于零碎调用 sys_write() 来说，遵循的是尽力而为策略，并不要求把所有操作都原子性地写到磁盘中。

3. 事务初始化

   • 简略的自增 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() 做的工作非常少，次要有两个：

1. 在内存中的日志的 header block 中记录下这个文件系统块的块号

   • 次要是做一个标记，这时候还没有把内容拷贝到 logged block 中

2. 把这个文件系统块 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);
}

1. 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 了，事务将不会被复原。

2. 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。

其它操作

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

1. bmap()

   • bmap() 和 itrunc() 能够说是一对互逆操作。bmap() 的作用是给定一个 inode，就返回第 bn 个 data block 的块号。

2. iunlock()

   • 开释先前在 ilock() 获取的互斥锁，以后线程放弃对内存 inode 的援用。

3. ialloc()

   • 遍历磁盘的 inode，找到一个闲暇的 inode 之后（type == 0 代表闲暇），将其 type 字段设置为指定值，最初调用 iget() 在内存中调配这个 inode。

4. readi()

   • 给定一个 inode、源地址(user_dst)、目标地址(dst)、源地址偏移(off) 以及读入的字节数 n，readi() 将从 inode 关联的 data 的 user_dst+off 开始拷贝 n 个字节到 dst 处。

5. 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：

1. struct inode* namei(char *path)

   • namei() 会将给定 path 解析到底，因而返回 c 的 inode，这里的 c 的类型既能够是文件能够是目录。

2. 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 上面那一堆操作）的一些内容看看。