xv6：一个简单的unix-like操作系统译文（十）

结构笔记

文件系统

文件系统的目的是组织和存储数据。文件系统通常支持用户和应用之间的数据共享，以及持久性，从而保证在系统重启后数据仍然可用。

xv6 文件系统提供了类 Unix 的文件、目录和路径名（见 Chapter 1），并将数据存储在 virtio 磁盘上以实现持久化。该文件系统需要解决以下几个挑战：

• 文件系统需要磁盘上的数据结构来表示具名目录和文件的树结构，用于记录保存每个文件内容的块的标识，并记录磁盘中哪些区域是空闲的。
• 文件系统必须支持崩溃恢复。也就是说，如果发生崩溃（例如断电），在重启之后文件系统仍必须能够正确工作。风险在于，崩溃可能会中断一系列更新操作，从而留下不一致的磁盘数据结构（例如，一个块既被某个文件使用，又被标记为空闲）。
• 不同的进程可能会同时操作文件系统，因此文件系统代码必须进行协调以维持不变性。
• 访问磁盘的速度比访问内存慢几个数量级，因此文件系统必须维护一个内存中的常用块缓存。

本章余下部分将解释 xv6 是如何应对这些挑战的。

概览

xv6 的文件系统实现被组织为七个层次，如 Figure 10.1 所示。磁盘层在 virtio 硬盘上读写块。缓冲区缓存层缓存磁盘块并对其访问进行同步，确保任意时刻只有一个内核进程能够修改某个特定块中存储的数据。日志层允许更高层将对多个块的更新封装在一个事务中，并在发生崩溃时保证这些块被原子性地更新（即要么全部更新，要么一个也不更新）。inode 层提供单个文件的抽象，每个文件由一个具有唯一 i-number 的 inode 表示，并关联若干保存文件数据的块。目录层将每个目录实现为一种特殊的 inode，其内容是一系列目录项，每个目录项包含一个文件名和一个 i-number。路径名层提供诸如 /usr/rtm/xv6/fs.c 这样的分层路径名，并通过递归查找来解析它们。文件描述符层使用文件系统接口对多种 Unix 资源（例如管道、设备、文件等）进行抽象，从而简化应用程序员的工作。

Figure 10.1：xv6 文件系统的层次结构。

传统的磁盘硬件将磁盘上的数据呈现为一系列编号的 512 字节块（也称为扇区）：扇区 0 是最前面的 512 字节，扇区 1 是接下来的 512 字节，依此类推。操作系统在文件系统中使用的块大小可能与磁盘使用的扇区大小不同，但通常块大小是扇区大小的整数倍。xv6 将已从磁盘读入内存的块副本保存在 struct buf 类型的对象中。该结构中存储的数据有时会与磁盘不同步：它可能尚未从磁盘读入（磁盘正在处理但尚未返回该扇区的内容），或者可能已被软件更新但尚未写回磁盘。

文件系统必须规划inode 和内容块在磁盘上的存储位置。为此，xv6 将磁盘划分为若干个区域，如 Figure 10.2 所示。文件系统不使用块 0（它保存引导扇区）。块 1 被称为超级块，其中包含有关文件系统的元数据（以块为单位的文件系统大小、数据块数量、inode 数量以及日志块数量）。从块 2 开始的若干块用于保存日志。日志之后是 inode 区，每个块中包含多个 inode。再之后是位图块，用于跟踪哪些数据块正在使用。剩余的块是数据块；每个数据块要么在位图中被标记为空闲，要么保存某个文件或目录的内容。超级块由一个名为 mkfs 的独立程序进行初始化，该程序用于构建一个初始的文件系统。

Figure 10.2：xv6 文件系统的结构。

本章其余部分将从缓冲区缓存开始，逐层讨论文件系统的实现。请注意观察：底层中精心设计的抽象如何简化了高层的设计。

缓冲区缓存层

缓冲区缓存有两个职责：（1）同步对磁盘块的访问，以确保内存中只有某个块的一个副本，并且任意时刻只有一个内核线程使用该副本；（2）缓存常用块，从而避免反复从速度很慢的磁盘中读取它们。相关代码位于 bio.c。

缓冲区缓存对外提供的主要接口是 bread 和 bwrite；前者获取一个包含某个磁盘块副本的 buf，该副本可以在内存中被读取或修改；后者将修改后的缓冲区写回磁盘上对应的块。内核线程在使用完缓冲区后，必须调用 brelse 来释放它。缓冲区缓存为每个缓冲区使用一个睡眠锁，以确保任意时刻只有一个线程使用每个缓冲区（也即每个磁盘块）；bread 返回的是一个已加锁的缓冲区，而 brelse 会释放该锁。

再来看缓冲区缓存的工作方式。缓冲区缓存拥有固定数量的缓冲区来保存磁盘块，这意味着如果文件系统请求的块当前不在缓存中，缓冲区缓存就必须回收一个正在保存其他块的缓冲区。缓冲区缓存会为新块回收 最近最少使用（LRU） 的缓冲区。其假设是：最近最少使用的缓冲区在不久的将来再次被使用的可能性最小。

代码：缓冲区缓存

缓冲区缓存由一个双向链表的缓冲区组成。函数 binit 由 main 调用，用于使用静态数组 buf 中的 NBUF 个缓冲区来初始化该链表。此后对缓冲区缓存的所有访问都通过 bcache.head 引用该链表，而不是直接访问 buf 数组。

每个缓冲区都有两个与其状态相关的字段。字段 valid 表示该缓冲区是否包含某个磁盘块的副本。字段 disk 表示缓冲区的内容已经交给磁盘处理，磁盘可能会修改该缓冲区（例如，将磁盘中的数据写入 data）。

bread 调用 bget 来获取指定扇区对应的缓冲区。如果该缓冲区需要从磁盘读取数据，bread 会在返回缓冲区之前调用 virtio_disk_rw 来完成读取。

bget 会扫描缓冲区链表，查找是否存在具有给定设备号和扇区号的缓冲区。如果存在这样的缓冲区，bget 就获取该缓冲区的睡眠锁，然后返回这个已加锁的缓冲区。

如果缓存中不存在给定扇区对应的缓冲区，bget 就必须创建一个，可能需要复用一个原本保存其他扇区的缓冲区。它会第二次扫描缓冲区链表，寻找一个未被使用的缓冲区（b->refcnt = 0）；任何这样的缓冲区都可以使用。bget 会修改缓冲区的元数据以记录新的设备号和扇区号，并获取其睡眠锁。注意，赋值 b->valid = 0 可以确保 bread 会从磁盘读取块数据，而不是错误地使用缓冲区之前的内容。

至关重要的一点是：每个磁盘扇区在缓存中最多只能有一个缓冲区副本。这既是为了保证读操作能够看到写操作的结果，也是因为文件系统使用缓冲区上的锁来进行同步。bget 通过在整个过程中持续持有 bcache.lock 来确保这一不变性：从第一次循环中检查块是否已被缓存，到第二次循环中通过设置 dev、blockno 和 refcnt 来声明该块现在已被缓存。这使得“检查某块是否存在”以及“（若不存在）指定一个缓冲区来保存该块”这两个操作成为一个原子操作。

bget 可以在 bcache.lock 的临界区之外获取缓冲区的睡眠锁，这是安全的，因为非零的 b->refcnt 可以防止该缓冲区被重新用于其他磁盘块。睡眠锁保护的是对块缓冲内容的读写，而 bcache.lock 则保护哪些块被缓存这一信息。

如果所有缓冲区都处于忙碌状态，说明有太多进程同时在执行文件系统调用；此时 bget 会直接 panic。一种更优雅的做法是让进程休眠，直到有缓冲区变为空闲，不过那样会引入死锁的可能性。

一旦 bread（在需要时）从磁盘读入数据并将缓冲区返回给调用者，调用者就对该缓冲区拥有独占使用权，可以读取或写入其中的数据字节。如果调用者修改了缓冲区，就必须在释放缓冲区之前调用 bwrite 将修改后的数据写回磁盘。bwrite 会调用 virtio_disk_rw 与磁盘硬件进行通信。

当调用者使用完一个缓冲区后，必须调用 brelse 来释放它。（名称 brelse 是 b-release 的缩写，虽然有些晦涩，但值得记住：它起源于 Unix，在 BSD、Linux 和 Solaris 中也被使用。）brelse 会释放睡眠锁，并将该缓冲区移动到链表的前端。这样的移动会使链表按最近使用情况排序（这里的“使用”指释放）：链表中的第一个缓冲区是最近使用的，而最后一个则是最久未使用的。bget 中的两个循环正是利用了这一点：查找已有缓冲区的扫描在最坏情况下需要遍历整个链表，但优先检查最近使用的缓冲区（从 bcache.head 开始沿 next 指针遍历）可以在具有良好局部性时减少扫描时间；而选择可复用缓冲区的扫描则通过向后遍历（沿 prev 指针）来选取最近最少使用的缓冲区。

日志层

文件系统设计中最有趣的问题之一是崩溃恢复。问题的根源在于，许多文件系统操作涉及对磁盘的多次写入，而如果在只完成了其中一部分写入后发生崩溃，就可能使磁盘上的文件系统处于不一致状态。例如，假设在文件截断过程中（将文件长度设为零并释放其内容块）发生了崩溃。根据磁盘写入的顺序不同，崩溃可能会导致以下两种情况之一：要么 inode 仍然引用一个已被标记为空闲的内容块；要么留下一个已分配但未被任何 inode 引用的内容块。

后一种情况相对无害，但inode 引用了已释放的块在重启后很可能会引发严重问题。重启之后，内核可能会将该块重新分配给另一个文件，这样就会出现两个不同的文件无意中指向同一个块的情况。如果 xv6 支持多用户，这还会成为一个安全问题，因为旧文件的所有者将能够读写属于另一个用户的新文件中的数据块。

xv6 使用一种简单的日志机制来解决文件系统操作过程中发生崩溃的问题。xv6 的系统调用并不会直接写磁盘上的文件系统数据结构。相反，它会将希望进行的所有磁盘写入的描述记录到磁盘上的一个日志中。一旦系统调用记录了它的所有写操作，就会向磁盘写入一个特殊的提交记录，表明日志中包含一个完整的操作。此时，系统调用才会将这些写操作复制到磁盘上的文件系统数据结构中。当这些写入完成后，系统调用会清除磁盘上的日志。

如果系统发生崩溃并重新启动，在运行任何进程之前，文件系统代码会按如下方式进行恢复：如果日志被标记为包含一个完整的操作，那么恢复代码就会将日志中的写入复制到它们在磁盘文件系统中的正确位置；如果日志没有被标记为包含完整操作，恢复代码就会忽略该日志。恢复过程的最后一步是清除日志。

为什么 xv6 的日志能够解决文件系统操作中的崩溃问题？如果崩溃发生在操作提交之前，那么磁盘上的日志不会被标记为完整，恢复代码会忽略它，磁盘的状态就好像该操作从未开始过一样。如果崩溃发生在操作提交之后，那么恢复过程将会重放该操作的所有写入，即使这些写入在崩溃前已经开始写入文件系统数据结构。在这两种情况下，日志都使得操作在面对崩溃时具有原子性：恢复之后，要么该操作的所有写入都出现在磁盘上，要么一个也不会出现。

日志设计

日志位于磁盘上的一个已知且固定的位置，该位置由超级块指定。日志由一个头块以及其后的一系列已更新块的副本（即“日志块”）组成。头块中包含一个扇区号数组，数组中的每一项对应一个日志块，以及一个日志块数量的计数。磁盘上头块中的计数值要么为零（表示日志中没有事务），要么为非零（表示日志中包含一个已完整提交的事务，且该事务包含所指示数量的日志块）。xv6 仅在事务提交时才写入头块，并且在将日志块复制到文件系统之后，将计数设置为零。因此，在事务进行到一半时发生崩溃，会导致日志头块中的计数为零；而在提交之后发生崩溃，则会导致计数为非零。

每个系统调用的代码都会标明：哪些写操作的开始与结束必须在崩溃面前保持原子性。为了允许不同进程并发执行文件系统操作，日志系统可以将多个系统调用的写操作累积到同一个事务中。因此，一次提交可能涉及多个完整系统调用的写入。为了避免将一个系统调用拆分到多个事务中，日志系统只有在没有文件系统系统调用正在进行时才会执行提交。

将多个事务一起提交的思想被称为组提交（group commit）。组提交通过将一次提交的固定开销分摊到多个操作上，从而减少磁盘操作的数量。组提交还会在同一时间向磁盘系统提供更多并发写入，可能使磁盘能够在一次磁盘旋转中完成所有写入。xv6 的 virtio 驱动并不支持这种批处理，但 xv6 的文件系统设计为此预留了可能性。

xv6 在磁盘上为日志分配了固定大小的空间。一个事务中所有系统调用写入的块总数必须能够放入该空间中。这会带来两个后果。首先，任何单个系统调用都不允许写入超过日志空间容量的不同块。对大多数系统调用来说这并不是问题，但有两个系统调用可能会写入很多块：write 和 unlink。一次对大文件的写操作可能会写入许多数据块和多个位图块，以及一个 inode 块；而删除一个大文件可能会写入多个位图块和一个 inode。xv6 的 write 系统调用会将大的写操作拆分成多个适合放入日志的小写操作；而 unlink 在实践中不会引发问题，因为 xv6 文件系统通常只使用一个位图块。第二个后果是，由于日志空间有限，日志系统在允许某个系统调用开始执行之前，必须能够确定该系统调用的写操作可以放入日志中剩余的空间。

代码：日志

在系统调用中使用日志的一个典型方式如下：

begin_op();
...
bp = bread(...);
bp->data[...] = ...;
log_write(bp);
...
end_op();

begin_op 会等待日志系统当前不在提交状态，并且日志中有足够的未预留空间来容纳本次调用的写入。log.outstanding 记录已经预留日志空间的系统调用数量；已预留的总空间等于 log.outstanding 乘以 MAXOPBLOCKS。递增 log.outstanding 既用于预留空间，也用于防止在该系统调用期间发生提交。代码保守地假设每个系统调用最多可能写入 MAXOPBLOCKS 个不同的块。

log_write 充当 bwrite 的代理。它在内存中记录该块的扇区号，为其在磁盘日志中预留一个槽位，并将该缓冲区钉住（pin）在块缓存中，防止块缓存将其逐出。该块必须一直留在缓存中直到提交完成：在此之前，缓存中的副本是修改的唯一记录；在提交之前不能将其写回到磁盘中的最终位置；并且同一事务中的其他读取必须能够看到这些修改。log_write 能够检测到在单个事务中对同一块的多次写入，并为该块分配相同的日志槽位。这种优化通常称为吸收（absorption）。例如，包含多个文件 inode 的磁盘块在一个事务中往往会被多次写入。通过将多次磁盘写入吸收为一次，文件系统既能节省日志空间，又能提升性能，因为只需要向磁盘写入该块的一份副本。

end_op 首先递减正在进行的系统调用计数。如果计数变为零，则通过调用 commit() 提交当前事务。该过程分为四个阶段。write_log() 将事务中被修改的每个块从缓冲区缓存复制到磁盘日志中的对应槽位。write_head() 将头块写入磁盘：这是提交点，在此之后发生的崩溃会导致恢复过程从日志中重放该事务的写入。install_trans 从日志中读取每个块，并将其写入文件系统中的正确位置。最后，end_op 将日志头块中的计数写为零；这一步必须发生在下一次事务开始写入日志块之前，以防止崩溃时恢复过程将一个事务的头块与后续事务的日志块错误地配对使用。

recover_from_log 在 initlog 中被调用，而 initlog 又是在启动过程中由 fsinit 调用的，并且发生在第一个用户进程运行之前。它读取日志头块，如果头块表明日志中包含一个已提交的事务，就会模拟 end_op 的行为进行恢复。

日志的一个使用示例出现在 filewrite 中。该事务的结构如下：

begin_op();
ilock(f->ip);
r = writei(f->ip, ...);
iunlock(f->ip);
end_op();

这段代码被包裹在一个循环中，用于将大的写操作拆分为一次只处理少量扇区的多个独立事务，从而避免日志溢出。对 writei 的调用会在该事务中写入多个块：文件的 inode、一个或多个位图块，以及若干数据块。

代码：块分配器

文件和目录的内容存储在磁盘块中，这些块必须从一个空闲池中分配。xv6 的块分配器在磁盘上维护一个空闲位图，每个块对应一个位。位为零表示对应的块是空闲的；位为一表示该块正在使用。程序 mkfs 会将引导扇区、超级块、日志块、inode 块以及位图块对应的位设置为已使用。

块分配器提供两个函数：balloc 用于分配一个新的磁盘块，bfree 用于释放一个块。balloc 中的循环会从块 0 一直检查到 sb.size（即文件系统中的块总数）。它查找位图中位为零的块，表示该块是空闲的。一旦找到这样的块，balloc 就会更新位图并返回该块。

为了提高效率，该循环被拆分为两层。外层循环读取每一个位图块；内层循环检查单个位图块中所有的 Bits-Per-Block（BPB） 位。如果两个进程同时尝试分配同一个块，可能会发生竞争，但这一竞争被缓冲区缓存机制所避免，因为缓冲区缓存保证任意时刻只有一个进程可以使用某一个位图块。

bfree 会找到正确的位图块并清除相应的位。同样，由 bread 和 brelse 所隐含的独占使用避免了对显式加锁的需求。

与本章后续描述的大多数代码一样，balloc 和 bfree 必须在一个事务内部调用。

Inode 层

术语 inode 有两个相关但不同的含义。它既可以指磁盘上的数据结构，其中包含文件大小以及数据块号列表；也可以指内存中的 inode，它包含磁盘 inode 的副本，以及内核内部所需的额外信息。

磁盘上的 inode 被紧密地存放在磁盘的一个连续区域中，称为 inode 块。每个 inode 的大小相同，因此给定一个编号 n，就可以很容易地在磁盘上找到第 n 个 inode。实际上，这个编号 n（称为 inode number 或 i-number）正是实现中用来标识 inode 的方式。磁盘上的 inode 由 struct dinode 定义。字段 type 用于区分普通文件、目录以及特殊文件（设备）。type 为零表示该磁盘 inode 是空闲的。字段 nlink 记录引用该 inode 的目录项数量，用于判断何时应该释放该磁盘 inode 及其数据块。字段 size 记录文件内容的字节数。数组 addrs 记录保存该文件内容的磁盘块号。

内核在内存中通过一个名为 itable 的表来维护活动 inode 的集合；struct inode 是磁盘上 struct dinode 的内存副本。只有当存在 C 指针引用某个 inode 时，内核才会将其保存在内存中。字段 ref 统计指向该内存 inode 的 C 指针数量；当引用计数降为零时，内核就会将该 inode 从内存中丢弃。函数 iget 和 iput 分别用于获取和释放指向 inode 的指针，并相应地修改引用计数。指向 inode 的指针可能来自文件描述符、当前工作目录，以及诸如 kexec 之类的临时内核代码。

xv6 的 inode 代码中使用了四种锁或类似锁的机制。itable.lock 保护两个不变性：一个 inode 在 inode 表中最多只出现一次；以及内存 inode 的 ref 字段准确统计了指向该 inode 的内存指针数量。每个内存 inode 都有一个 lock 字段，包含一个睡眠锁，用于确保对 inode 字段（例如文件长度）以及 inode 所对应的文件或目录内容块的独占访问。inode 的 ref 字段只要大于零，系统就会保持该 inode 在表中，而不会将该表项重新用于其他 inode。最后，每个 inode 都包含一个 nlink 字段（磁盘上有一份，若在内存中也会拷贝一份），用于统计指向该文件的目录项数量；只要链接计数大于零，xv6 就不会释放该 inode。

由 iget() 返回的 struct inode 指针在对应的 iput() 调用之前都保证有效：inode 不会被删除，该指针所引用的内存也不会被重新用于其他 inode。iget() 提供的是非独占访问，因此可以同时存在多个指向同一 inode 的指针。文件系统代码的许多部分都依赖于 iget() 的这种行为：既可以长期持有对 inode 的引用（如打开的文件和当前目录），又能在操作多个 inode（例如路径名查找）时避免竞争并防止死锁。

iget 返回的 struct inode 可能尚未包含任何有用的内容。为了确保它持有磁盘 inode 的副本，代码必须调用 ilock。该函数会锁住 inode（使其他进程无法对其调用 ilock），并在尚未读取的情况下从磁盘读取 inode。iunlock 用于释放 inode 上的锁。将获取 inode 指针与锁定 inode分离，有助于在某些场景下避免死锁，例如在目录查找过程中。多个进程可以同时持有由 iget 返回的指向同一 inode 的 C 指针，但任意时刻只能有一个进程锁定该 inode。

inode 表只保存那些被内核代码或数据结构通过 C 指针引用的 inode。它的主要职责是同步多个进程的访问。inode 表也会顺带缓存经常使用的 inode，但缓存并非其主要目的；如果某个 inode 被频繁使用，缓冲区缓存很可能已经将其保存在内存中。修改内存 inode 的代码会通过 iupdate 将其写回磁盘。

代码：Inode

为了分配一个新的 inode（例如在创建文件时），xv6 会调用 ialloc。ialloc 与 balloc 类似：它一次一个块地遍历磁盘上的 inode 结构，寻找一个被标记为空闲的 inode。一旦找到，它就通过将新的 type 写入磁盘来占用该 inode，然后通过尾调用 iget 返回 inode 表中的一个条目。ialloc 的正确运行依赖于这样一个事实：任意时刻只有一个进程能够持有对 bp 的引用；因此，ialloc 可以确信不会有其他进程同时看到该 inode 可用并试图占用它。

iget 会在 inode 表中查找一个活动条目（ip->ref > 0），其设备号和 inode 号与所需的相匹配。如果找到，它就返回对该 inode 的一个新引用。在扫描过程中，iget 会记录第一个空槽的位置，如果需要分配新的表项，就使用该位置。

在读取或写入 inode 的元数据或内容之前，代码必须使用 ilock 对 inode 加锁。ilock 使用一个睡眠锁来实现这一点。一旦 ilock 获得了对 inode 的独占访问权，它就会在需要时从磁盘（更常见的是从缓冲区缓存）中读取 inode。函数 iunlock 会释放该睡眠锁，并可能唤醒正在休眠等待的进程。

iput 通过递减引用计数来释放一个指向 inode 的 C 指针。如果这是最后一个引用，那么该 inode 在 inode 表中的槽位就变为空闲，可以被重新用于其他 inode。

如果 iput 发现某个 inode 既没有任何 C 指针引用，同时也没有任何目录项链接指向它（即不出现在任何目录中），那么该 inode 及其数据块就必须被释放。iput 会调用 itrunc 将文件截断为零字节，从而释放数据块；然后将 inode 的 type 设置为 0（未分配），并将该 inode 写回磁盘。

在 iput 释放 inode 的情形下，其加锁协议值得仔细分析。一个潜在的危险是：某个并发线程可能正在 ilock 中等待使用该 inode（例如读取文件或列出目录），而它并未预期该 inode 已不再被分配。这种情况不会发生，因为如果某个 inode 没有任何链接，并且 ip->ref 为 1，那么系统调用不可能获得指向该内存 inode 的指针；这唯一的引用正是调用 iput 的线程所持有的。另一个主要危险是：并发调用 ialloc 可能会选择 iput 正在释放的同一个 inode。这种情况只有在 iupdate 将 inode 的 type 写成 0 之后才可能发生。这种竞争是良性的；分配线程会礼貌地等待获取该 inode 的睡眠锁，在它读取或写入 inode 时，iput 已经完成了对该 inode 的操作。

iput() 可能会向磁盘写入数据。这意味着，任何使用文件系统的系统调用都有可能写磁盘，因为该系统调用可能恰好是最后一个持有文件引用的调用。即使是看似只读的系统调用（如 read()），也可能最终调用 iput()。因此，只要系统调用使用了文件系统，即便是只读操作也必须被包裹在事务中。

iput() 与崩溃之间存在一个具有挑战性的交互。iput() 并不会在文件的链接计数降为零时立即截断该文件，因为可能仍有进程在内存中持有对该 inode 的引用：某个进程可能已经成功打开了该文件，并仍在对其进行读写。然而，如果在最后一个进程关闭该文件描述符之前发生了崩溃，那么该文件在磁盘上会被标记为已分配，但不会有任何目录项指向它。

文件系统通常通过两种方式之一来处理这种情况。第一种也是较简单的解决方案是：在重启后的恢复过程中，文件系统扫描整个文件系统，查找那些被标记为已分配、但却没有任何目录项指向它们的文件；如果发现这样的文件，就将其释放。

第二种解决方案不需要扫描整个文件系统。在这种方案中，当某个文件的链接计数降为零但其引用计数仍不为零时，文件系统会在磁盘上（例如在超级块中）记录该文件的 inode 号。当文件的引用计数最终降为零并被删除时，文件系统会更新磁盘上的列表，将该 inode 从列表中移除。在恢复时，文件系统会释放列表中的所有文件。

xv6 并未实现上述任一方案，这意味着 inode 可能在磁盘上仍被标记为已分配，尽管它们实际上已经不再被使用。随着时间推移，xv6 可能会面临磁盘空间耗尽的风险。

Figure 10.3：磁盘上文件的表示方式。

代码：Inode 内容

磁盘上的 inode 结构 struct dinode 包含一个 size 字段和一个块号数组（见 Figure 10.3）。inode 的数据存放在 dinode 的 addrs 数组所列出的块中。前 NDIRECT 个数据块列在数组的前 NDIRECT 个条目中；这些块称为直接块。接下来的 NINDIRECT 个数据块并不直接列在 inode 中，而是存放在一个称为间接块的数据块里。addrs 数组的最后一个条目给出了该间接块的地址。因此，文件的前 12 kB（NDIRECT × BSIZE）字节可以直接从 inode 中列出的块加载，而接下来的 256 kB（NINDIRECT × BSIZE）字节则必须在查阅间接块之后才能加载。这是一种良好的磁盘表示方式，但对使用者来说却较为复杂。函数 bmap 管理了这种表示方式，使得更高层的例程（如稍后将看到的 readi 和 writei）无需处理这些复杂性。bmap 返回 inode ip 的第 bn 个数据块对应的磁盘块号；如果 ip 还没有该块，bmap 会为其分配一个。

函数 bmap 首先处理最简单的情况：前 NDIRECT 个块直接列在 inode 本身中。接下来的 NINDIRECT 个块列在位于 ip->addrs[NDIRECT] 的间接块中。bmap 会读取该间接块，然后从块内的正确位置读取一个块号。如果请求的块号超过 NDIRECT + NINDIRECT，bmap 就会触发 panic；writei 中包含了防止这种情况发生的检查。

bmap 会在需要时分配块。ip->addrs[] 或间接块中的某个条目为零，表示尚未分配块。当 bmap 遇到零值时，会用新分配的块号替换它们，实现按需分配。

itrunc 用于释放文件占用的块，并将 inode 的大小重置为零。itrunc 首先释放直接块，然后释放间接块中列出的块，最后释放间接块本身。

bmap 使得 readi 和 writei 能够方便地访问 inode 的数据。readi 首先确保偏移量和读取长度没有超出文件末尾。从文件末尾之后开始的读取会返回错误，而从文件末尾开始或跨越文件末尾的读取会返回少于请求字节数的数据。主循环逐块处理文件内容，将数据从缓冲区复制到 dst 中。writei 与 readi 基本相同，但有三点不同：从文件末尾开始或跨越文件末尾的写入会扩展文件大小，但不超过最大文件大小；循环中是将数据复制到缓冲区而不是从中复制出来；如果写入扩展了文件，writei 还必须更新文件大小。

函数 stati 将 inode 的元数据复制到 stat 结构中，该结构通过 stat 系统调用向用户程序公开。

代码：目录层

目录在内部的实现方式与文件非常相似。其 inode 的类型为 T_DIR，其数据是一个目录项序列。每个目录项是一个 struct dirent，其中包含一个名称和一个 inode 号。名称的最大长度为 DIRSIZ（14） 个字符；如果名称更短，则以 NULL（0）字节结尾。inode 号为零的目录项表示该项是空闲的。

函数 dirlookup 在目录中搜索具有给定名称的目录项。如果找到，它会返回一个指向相应 inode 的指针（未加锁），并将 *poff 设置为该目录项在目录中的字节偏移量，以便调用者在需要时对其进行修改。如果 dirlookup 找到了匹配名称的目录项，它会更新 *poff，并通过 iget 返回一个未加锁的 inode。dirlookup 正是 iget 返回未加锁 inode 的原因。调用者已经锁定了 dp，因此如果查找的是 .（当前目录的别名），在返回之前尝试对 inode 加锁将会再次锁定 dp 并导致死锁。（还存在涉及多个进程以及 ..（父目录的别名）的更复杂死锁场景；. 并不是唯一的问题。）调用者可以先解锁 dp，再锁定 ip，从而确保任意时刻只持有一个锁。

函数 dirlink 会在目录 dp 中写入一个新的目录项，包含给定的名称和 inode 号。如果该名称已经存在，dirlink 会返回一个错误。主循环通过读取目录项来查找一个未分配的目录项。一旦找到，就会提前结束循环，此时 off 被设置为该可用目录项的偏移量；否则，循环结束时 off 等于 dp->size。无论哪种情况，dirlink 都会在偏移量 off 处写入新的目录项。

代码：路径名

路径名查找涉及对每一个路径组成部分依次调用 dirlookup。namei 负责解析路径并返回对应的 inode。函数 nameiparent 是一个变体：它在最后一个元素之前停止，返回父目录的 inode，并将最后一个路径元素复制到 name 中。二者都调用通用函数 namex 来完成实际工作。

namex 首先决定从哪里开始解析路径。如果路径以斜杠 / 开头，则从根目录开始；否则，从当前目录开始。随后，它使用 skipelem 依次处理路径中的每个元素。循环的每一次迭代都必须在当前 inode ip 中查找名称。迭代开始时，先对 ip 加锁，并检查它是否是一个目录；如果不是，查找失败。（对 ip 加锁并不是因为 ip->type 可能在此期间发生变化——它不会——而是因为在调用 ilock 之前，不能保证 ip->type 已经从磁盘加载到内存中。）如果调用的是 nameiparent 且当前是最后一个路径元素，循环会提前结束；根据 nameiparent 的定义，最后一个路径元素已经被复制到 name 中，因此 namex 只需返回未加锁的 ip。最后，循环通过 dirlookup 查找该路径元素，并通过设置 ip = next 来为下一次迭代做准备。当路径元素耗尽时，返回 ip。

过程 namex 可能需要较长时间才能完成：如果相关数据不在缓冲区缓存中，它可能涉及多次磁盘操作，以读取路径中各级目录的 inode 和目录块。xv6 的设计非常谨慎：当一个内核线程在执行 namex 时如果被磁盘 I/O 阻塞，另一个内核线程仍然可以并发地查找不同的路径名。namex 会对路径中的每一个目录分别加锁，从而允许在不同目录中的查找并行进行。

这种并发性也带来了一些挑战。例如，当一个内核线程正在查找路径名时，另一个内核线程可能正在通过 unlink 修改目录树。潜在的风险在于：一次查找可能正在搜索一个已被删除的目录，而该目录的块可能已经被重新用于另一个目录或文件。

xv6 避免了这类竞争。例如，在 namex 中执行 dirlookup 时，查找线程持有目录的锁，并且 dirlookup 返回的 inode 是通过 iget 获得的。iget 会增加该 inode 的引用计数。只有在从 dirlookup 接收到 inode 之后，namex 才会释放目录的锁。此后，即使另一个线程将该 inode 从目录中解除链接，xv6 也不会立即删除该 inode，因为其引用计数仍然大于零。

另一个风险是死锁。例如，在查找 "." 时，next 与 ip 指向同一个 inode。如果在释放 ip 的锁之前就尝试锁定 next，将会导致死锁。为避免这种情况，namex 会在获取 next 的锁之前先解锁目录。在这里我们再次看到，将 iget 与 ilock 分离的重要性。

文件描述符层

Unix 接口的一个很酷的方面在于：Unix 中的大多数资源都被表示为文件，包括诸如控制台这样的设备、管道，以及当然还有普通文件。文件描述符层正是实现这种统一抽象的层次。

正如在 Chapter 1 中看到的那样，xv6 为每个进程提供了一个打开文件表，也称为文件描述符表。每个打开的文件由一个 struct file 表示，它是对 inode 或管道的封装，并包含一个 I/O 偏移量。每次调用 open 都会创建一个新的打开文件（一个新的 struct file）：如果多个进程分别独立地打开同一个文件，这些实例将拥有不同的 I/O 偏移量。另一方面，一个单一的打开文件（同一个 struct file）也可以在一个进程的文件表中出现多次，或者出现在多个进程的文件表中。这种情况会发生在：一个进程通过 open 打开文件后，又使用 dup 创建别名，或者通过 fork 将其与子进程共享。一个引用计数用于跟踪对某个打开文件的引用数量。文件可以以只读、只写或读写方式打开，字段 readable 和 writable 用于记录这些属性。

系统中所有打开的文件都保存在一个全局的文件表中，称为 ftable。文件表提供了一组函数，用于分配文件（filealloc）、创建重复引用（filedup）、释放引用（fileclose），以及进行数据读写（fileread 和 filewrite）。

前三个函数遵循一种我们已经很熟悉的形式。filealloc 扫描文件表，查找一个未被引用的文件（f->ref == 0），并返回一个新的引用；filedup 增加引用计数；fileclose 则递减引用计数。当某个文件的引用计数降为零时，fileclose 会根据文件的类型，释放其底层的管道或 inode。

函数 filestat、fileread 和 filewrite 分别实现了文件上的 stat、read 和 write 操作。filestat 只允许作用于 inode，并会调用 stati。fileread 和 filewrite 会先检查该操作是否被打开模式所允许，然后将调用转交给管道实现或 inode 实现。如果文件表示的是一个 inode，fileread 和 filewrite 会使用 I/O 偏移量作为操作的偏移量，并在操作完成后推进该偏移量。管道则没有偏移量的概念。回忆一下，inode 相关的函数要求调用者自行处理加锁。inode 的加锁还有一个方便的副作用：读写偏移量的更新是原子的，因此多个进程同时向同一个文件写入时，不会相互覆盖对方的数据，尽管它们的写入结果可能会交错在一起。

代码：系统调用

借助底层各层提供的函数，大多数系统调用的实现都相当简单。不过，有少数几个系统调用值得更深入地分析。

函数 sys_link 和 sys_unlink 会编辑目录，创建或删除对 inode 的引用。它们是事务机制强大之处的又一个很好的例子。sys_link 首先获取其参数，即两个字符串 old 和 new。假设 old 存在且不是一个目录，sys_link 会递增其 ip->nlink 计数。随后，sys_link 调用 nameiparent 来找到 new 的父目录 inode 以及最终的路径元素，并创建一个新的目录项，使其指向 old 的 inode。新的父目录必须存在，并且必须与已有的 inode 位于同一个设备上：inode 号只在单个磁盘内才具有唯一意义。如果发生此类错误，sys_link 就必须回退并递减 ip->nlink。

事务简化了实现，因为这些操作需要更新多个磁盘块，但我们不必关心它们的更新顺序；要么全部成功，要么全部失败。例如，如果没有事务机制，在创建链接之前先更新 ip->nlink 会使文件系统暂时处于不安全状态，而在两者之间发生的崩溃可能导致严重问题。有了事务，这些担忧就不复存在。

sys_link 为一个已有的 inode 创建一个新名字。函数 create 则为一个新的 inode 创建新名字。它是三个文件创建系统调用的泛化实现：带有 O_CREATE 标志的 open 会创建一个新的普通文件，mkdir 创建一个新目录，mkdev 创建一个新的设备文件。与 sys_link 类似，create 首先调用 nameiparent 获取父目录的 inode。然后调用 dirlookup 检查该名字是否已经存在。如果名字已存在，create 的行为取决于它是为哪个系统调用服务：open 的语义与 mkdir 和 mkdev 不同。如果 create 是为 open 服务（type == T_FILE），并且已存在的名字本身是一个普通文件，那么 open 会将其视为成功，因此 create 也会如此处理；否则，就会返回错误。如果名字尚不存在，create 会调用 ialloc 分配一个新的 inode。如果新 inode 是一个目录，create 会用 . 和 .. 目录项对其进行初始化。最后，在数据正确初始化之后，create 才会将其链接到父目录中。与 sys_link 一样，create 会同时持有两个 inode 的锁：ip 和 dp。这里不存在死锁的可能性，因为 inode ip 是新分配的：系统中不会有其他进程已经持有 ip 的锁并试图再去锁定 dp。

利用 create，可以很容易地实现 sys_open、sys_mkdir 和 sys_mknod。其中 sys_open 是最复杂的，因为创建新文件只是它功能的一小部分。如果 open 传入了 O_CREATE 标志，它会调用 create；否则，它会调用 namei。create 返回的是一个已加锁的 inode，而 namei 返回的不是，因此 sys_open 必须自行对 inode 加锁。这也为检查“目录只能以只读方式打开而不能写入”提供了一个方便的位置。在成功获得 inode 之后，sys_open 会分配一个文件结构和一个文件描述符，并填充该文件结构。注意，在这一过程中，没有其他进程能够访问这个尚未完全初始化的文件，因为它只存在于当前进程的文件表中。

第 9 章在文件系统尚未出现之前就已经讨论了管道的实现。函数 sys_pipe 通过提供一种创建管道对的方式，将该实现与文件系统连接起来。它的参数是一个指向两个整数空间的指针，用于记录新创建的两个文件描述符。随后，它分配管道并安装相应的文件描述符。

现实世界

真实操作系统中的缓冲区缓存要比 xv6 的复杂得多，但它们承担着相同的两个目的：缓存数据以及同步对磁盘的访问。xv6 的缓冲区缓存和 V6 一样，使用了简单的最近最少使用（LRU）淘汰策略；还存在许多更复杂的策略，它们各自适用于不同的工作负载。更高效的 LRU 缓存可以去除链表结构，改用哈希表进行查找、堆来实现 LRU 淘汰。现代缓冲区缓存通常与虚拟内存系统集成，以支持内存映射文件。

xv6 的日志系统效率并不高。提交操作不能与文件系统系统调用并发进行；系统会记录整个磁盘块，即便只修改了块中的少量字节；它还执行同步的日志写入，一次写一个块，而每次写入很可能都需要一次完整的磁盘旋转时间。真实系统中的日志机制会针对这些问题进行优化。

日志并不是实现崩溃恢复的唯一方法。早期的文件系统在重启时使用清理程序（例如 UNIX 的 fsck）来检查每个文件和目录，以及块和 inode 的空闲列表，查找并修复不一致之处。对于大型文件系统，这种清理可能需要数小时，而且在某些情况下，无法以保证原始系统调用原子性的方式解决不一致问题。基于日志的恢复要快得多，并且能在发生崩溃时保证系统调用的原子性。

xv6 使用的 inode 和目录的磁盘布局与早期 UNIX 基本相同；这一方案多年来表现出了惊人的生命力。BSD 的 UFS/FFS 以及 Linux 的 ext2/ext3 在本质上都使用相同的数据结构。文件系统布局中效率最低的部分是目录：每次查找都需要对所有目录块进行线性扫描。当目录只有少量磁盘块时这是合理的，但当目录包含大量文件时，代价就会很高。Microsoft Windows 的 NTFS、macOS 的 HFS、Solaris 的 ZFS 等系统，将目录实现为磁盘上的平衡树结构。这种方式更加复杂，但可以保证对数时间复杂度的目录查找。

xv6 对磁盘故障的处理非常天真：如果磁盘操作失败，xv6 会直接 panic。这种做法是否合理取决于硬件环境：如果操作系统运行在使用冗余机制屏蔽磁盘故障的专用硬件之上，那么故障可能极其罕见，panic 也许是可以接受的；而如果操作系统直接使用普通磁盘，则应该预期会发生故障，并以更优雅的方式处理它们，以避免某个文件中一个块的损坏影响整个文件系统的使用。

xv6 要求文件系统必须位于单个磁盘设备上，并且大小不可变化。随着大型数据库和多媒体文件不断推动存储需求增长，操作系统正在探索消除“每个文件系统一个磁盘”瓶颈的方法。基本思路是将多个磁盘组合成一个逻辑磁盘。像 RAID 这样的硬件方案仍然非常流行，但当前趋势是尽可能在软件层面实现这些逻辑。软件实现通常支持更丰富的功能，例如在运行时通过添加或移除磁盘来动态扩展或收缩逻辑设备。当然，一个可以动态变化的存储层需要一个同样可以变化的文件系统：xv6 使用的固定大小 inode 块数组在这种环境下并不适用。将磁盘管理与文件系统分离可能是最清晰的设计，但二者之间复杂的接口又促使一些系统（如 Sun 的 ZFS）选择将它们合并实现。

xv6 的文件系统还缺少许多现代文件系统的特性，例如快照和增量备份。

现代 Unix 系统允许使用与磁盘存储相同的系统调用来访问多种资源：命名管道、网络连接、远程网络文件系统，以及诸如 /proc 之类的监控与控制接口。与 xv6 在 fileread 和 filewrite 中使用 if 语句不同，这些系统通常为每个打开的文件维护一个函数指针表，每种操作对应一个函数指针，通过调用该指针来执行该 inode 对应的实现。网络文件系统和用户态文件系统会将这些调用转换为网络 RPC，等待响应后再返回结果。