Xv6 book 的第八章节

File system

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

Xv6文件系统提供类似于Unix的文件、目录和路径名（参见第1章），并将其数据存储在virtio磁盘上以实现持久性。文件系统解决了以下几个问题：

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

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

Overview

Xv6文件系统实现分为七个层次，如图8.1所示。Disk层读取和写入virtio硬盘上的块。Buffer cache层缓存磁盘块并同步对它们的访问，确保每次只有一个内核进程可以修改任何特定块中存储的数据。Logging层允许更高层将对多个块的更新包装在transaction中，并确保在发生崩溃时原子地更新这些块（即它们要么全部更新，要么一个也不更新）。Inode层提供了单个文件，每个文件都表示为一个具有唯一编号i和一些包含文件数据的块的inode。Directory层将每个目录实现为一种特殊类型的inode，其内容是一系列目录条目，每个目录条目包含文件的名称和i编号。Pathname层提供类似于/usr/rtm/xv6/fs.c的分层路径名，并使用递归查找解析它们。File descriptor层使用文件系统接口抽象了许多Unix资源（例如，管道、设备、文件等），简化了应用程序程序员的工作。

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

文件系统必须有一个计划，确定在磁盘上存储inode和content blocks的位置。为此，xv6将磁盘划分为几个部分，如图8.2所示。文件系统不使用块0（它保存引导扇区）。块1称为superblock；它包含有关文件系统的元数据（文件系统大小、数据块数、inode数和日志中的块数）。从块2开始保存日志。在日志之后是inodes，每个块包含多个inode。在它们之后是用于跟踪哪些数据块正在使用的bitmap block。其余的块是数据块；每个数据块在bitmap block中标记为free，或者保存文件或目录的内容。superblock由一个名为mkfs的单独的程序填充，该程序构建初始文件系统。

本章的其余部分将讨论文件系统的每一层，从buffer cache开始。请注意在较低层次选择得当的抽象如何简化较高层次的设计。

Buffer cache layer

缓冲区缓存有两个任务：(1) 同步对磁盘块的访问，以确保内存中只有一个块的副本，并且每次只有一个内核线程使用该副本；(2) 缓存常用块，以便它们无需从慢速磁盘重新读取。相关代码在bio.c中。

Buffer cache主要提供的接口包括bread()和bwrite()；前者获取一个包含块副本的buf，可以在内存中读取或修改，而后者将修改后的缓冲区写入磁盘上的相应的block。内核线程在完成对缓冲区的使用后必须通过调用brelse()来释放缓冲区。Buffer cache通过使用每个缓冲区的sleep-lock确保了每次只有一个线程使用该缓冲区；bread()返回一个已锁定的缓冲区，而brelse()释放锁。

Buffer cache有固定数量的缓冲区来保存磁盘块，这意味着如果文件系统请求一个尚未在缓存中的块，缓冲区缓存必须回收当前保存其他块的缓冲区。缓冲区缓存为新块回收最近最少使用的缓冲区。这个假设是最近最少使用的缓冲区最不可能很快再次被使用。

Code: Buffer cache

Buffer cache是一个双向链表，由NBUF个缓冲区的静态数组buf（kernel/bio.c）初始化。由main()调用的函数binit()负责初始化这个链表。所有对buffer cache的访问都通过bcache.head引用链表，而不是buf数组。

每个cache都有两个与之相关的状态字段。valid字段指示缓冲区包含块的副本。disk字段指示缓冲区内容已经交给磁盘，这可能会改变缓冲区（例如，从磁盘写入数据）。

bread()调用bget()以获取给定扇区的缓冲区。如果需要从磁盘读取缓冲区，bread()调用virtio_disk_rw()执行读取操作，然后返回缓冲区。

bget()扫描缓冲区列表，查找具有给定设备和扇区号的缓冲区。如果存在这样的缓冲区，bget()获取缓冲区的sleep-lock。然后，bget()返回锁定的缓冲区。

如果给定扇区没有缓存的缓冲区，bget()必须创建一个，可能会重用曾经包含不同扇区的缓冲区。它再次扫描缓冲区列表，寻找未使用的缓冲区（b->refcnt = 0）；任何这样的缓冲区都可以使用。bget()编辑buffer的metadata以记录新的设备和扇区号，并获取其sleep-lock。请注意，赋值b->valid = 0确保bread()将从磁盘读取块数据，而不会错误地使用缓冲区的先前内容。

为了确保读取者能够看到写入的内容和文件系统在cache上使用锁进行同步，必须确保每个磁盘扇区最多只有一个buffer cache。bget()通过在第一个循环检查块是否已缓存时持续持有bache.lock，直到第二个循环声明块现在已缓存（通过设置dev、blockno和refcnt）来确保这个不变式。这导致对block存在性的检查（如果不存在，则指定用于保存块的缓冲区）是原子的。

bget()在bcache.lock关键部分之外获取缓冲区的sleep-lock是安全的，因为非零的b->refcnt阻止重用缓冲区用于不同的磁盘块。Sleep-lock保护对块缓冲内容的读取和写入，而bcache.lock保护有关哪些块已被缓存的信息。

如果所有的缓冲区都是busy的，说明有太多的进程同时执行文件系统调用；此时，bget()会产生 panic。一个更好的响应可能是等待到有一个缓冲区变为空闲，虽然这样可能导致死锁。

一旦bread()读取了磁盘并将缓冲区返回给调用者，调用者就独占了该缓冲区，并可以读取或写入数据字节。如果调用者修改了缓冲区，必须调用bwrite()将更改的数据写入磁盘，然后释放缓冲区。bwrite()调virtio_disk_rw()与磁盘硬件进行通信。

当调用者使用完缓冲区后，必须调用brelse()进行释放。brelse()的名字虽然有点神秘(b-release)，但值得学习：它起源于 Unix，并在 BSD、Linux 和 Solaris 中也被使用。brelse()释放了sleep-lock，并将缓冲区移动到链表的前面。移动缓冲区会导致链表按照缓冲区的最近使用时间排序：链表中的第一个缓冲区是最近使用过的，而最后一个是最久未使用的。bget()中的两个循环利用了这一点：在最坏的情况下，查找现有缓冲区必须处理整个链表，但首先检查最近使用的缓冲区（从bcache.head开始，按照next指针进行跟踪）将减少扫描时间，当引用局部性较好时。选择要重用的缓冲区的扫描通过向后扫描（按照prev指针进行跟踪）选择最久未使用的缓冲区。

Logging layer

文件系统设计中最有趣的问题之一是crash recovery。这个问题的出现是因为许多文件系统操作涉及对磁盘的多次写入，而在一些写入的子集之后发生的崩溃可能会导致磁盘上的文件系统处于不一致的状态。例如，假设在文件截断（将文件长度设置为零并释放其内容块）期间发生崩溃。根据磁盘写入的顺序，崩溃可能会使一个inode引用一个被标记为自由的内容块，或者它可能会留下一个分配但未引用的内容块。

后者相对无害，但是引用已释放块的inode在重启后可能会导致严重的问题。重启后，内核可能会将该块分配给另一个文件，现在我们有两个不同的文件无意中指向相同的块。如果xv6支持多个用户，这种情况可能是一个安全问题，因为旧文件的所有者将能够读取和写入由不同用户拥有的新文件中的块。

Xv6通过一种简单的日志形式解决了在文件系统操作期间发生崩溃的问题。在xv6中，一个系统调用不会直接写入磁盘上的文件系统数据结构。相反，它将希望进行的所有磁盘写入的描述放入磁盘上的一个日志中。一旦系统调用记录了所有的写入，它就会向磁盘写入一个特殊的commit记录，指示日志包含一个完整的操作。此时，系统调用将写入复制到磁盘上的文件系统数据结构中。在这些写入完成之后，系统调用会擦除磁盘上的日志。

如果系统崩溃并重新启动，文件系统代码将在运行任何进程之前按照以下步骤从崩溃中恢复。如果日志被标记为包含完整的操作，那么恢复代码将把写入复制到它们在磁盘上的正确位置。如果日志没有被标记为包含完整的操作，恢复代码将忽略该日志。恢复代码最后会擦除日志。

为什么xv6的日志解决了文件系统操作期间发生崩溃的问题呢？如果崩溃发生在操作提交之前，那么磁盘上的日志将不会被标记为完整，恢复代码将忽略它，磁盘的状态将好像操作甚至还没有开始。如果崩溃发生在操作提交之后，那么恢复将重新播放所有操作的写入，如果该操作已经开始将它们写入磁盘数据结构，则可能重复执行它们。在任一情况下，日志使操作在崩溃方面具有原子性：恢复后，要么所有操作的写入都出现在磁盘上，要么它们都不出现。

Log design

Log位于superblock中指定的已知固定位置。它由一个header block和一个更新块副本序列（“logged blocks”）组成。Header block包含一个用于记录扇区号的数组和log blocks的计数。磁盘上header block中的计数要么为零，表示日志中没有事务，要么为非零，表示日志包含一个完整的已提交事务，其中包含指定数量的logged blocks。Xv6在transaction提交时写入header block，但在此之前不写入，并在将logged blocks复制到文件系统后将计数设置为零。因此，在transaction中途发生崩溃将导致日志头块中的计数为零；在提交后发生崩溃将导致计数为非零。

每个系统调用的代码指示了必须在崩溃方面具有原子性的写入序列的开始和结束。为了允许不同进程之间并发执行文件系统操作，日志系统可以将多个系统调用的写入积累到一个transaction中。因此，一个单独的提交可能涉及多个完整系统调用的写入。为了避免将系统调用跨越多个transaction，日志系统仅在没有进行文件系统系统调用时才进行提交。

将多个事务一起提交的想法称为group commit。Group commit减少了磁盘操作的次数，因为它将提交的固定成本分摊到多个操作中。Group commit还一次性向磁盘系统提供了更多的并发写入，也许允许磁盘在单个磁盘旋转期间将它们全部写入。Xv6的virtio驱动程序不支持这种批处理方式，但xv6的文件系统设计允许这样做。

Xv6在磁盘上专门分配了一定数量的空间来保存日志。事务中由系统调用写入的块的总数必须适应该空间。这带来了两个后果。

1. 不允许单个系统调用写入的不同块的数量超过日志中的空间。对于大多数系统调用来说，这不是问题，但其中两个系统调用可能会写入许多块：write()和unlink()。大文件写入可能会写入许多data blocks和许多bitmap blocks以及一个inode块；取消链接大文件可能会写入许多bitmap blocks和一个inode。Xv6的write()系统调用将大写入拆分为适应日志的多个较小写入，而unlink()不会引起问题，因为实际上xv6文件系统只使用一个bitmap block。
2. 有限的日志空间的另一个后果是，除非确定系统调用的写入将适应日志中剩余的空间，否则日志系统不能允许系统调用启动。

Code: logging

在系统调用中，一个典型的log的使用如下所示：

1
2
3
4
5
6
7

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

begin_op()（kernel/log.c）会等待，直到日志系统当前没有进行提交，并且有足够的未保留的日志空间来容纳此调用的写入。log.outstanding计算已经保留了日志空间的系统调用数量；总的保留空间是log.outstanding乘以MAXOPBLOCKS。增加log.outstanding既保留空间又防止在此系统调用期间发生提交。该代码保守地假设每个系统调用可能写入多达MAXOPBLOCKS个不同的块。

log_write()替代了bwrite。它在内存中记录块的扇区号，在磁盘上为其保留一个槽，并将缓冲区锁定在块缓存中，以防止块缓存将其逐出。块必须保留在缓存中直到提交为止：在那之前，缓存的副本是修改的唯一记录；在提交之前，不能将其写入磁盘上的位置；同一事务中的其他读取必须看到修改。log_write()在单个transaction中多次写入块时会注意到，并在日志中为该块分配相同的槽。这种优化通常称为absorption。例如，在单个transaction中可能多次写入包含多个文件的inode的磁盘块。通过将多个磁盘写入吸收为一个，文件系统可以节省日志空间，并且因为只需要将磁盘块的一个副本写入磁盘，所以可以实现更好的性能。

end_op()首先递减未完成的系统调用计数。如果计数现在为零，则通过调用commit()提交当前事务。该过程分为四个阶段。write_log()将transaction中修改的每个块从缓冲区复制到磁盘上的日志槽中。write_head()将header block写入磁盘：这是commit point，如果在写入后发生崩溃，恢复将从日志中重新执行transaction的写入。install_trans()从日志中读取每个块并将其写入文件系统中的适当位置。最后，end_op()写入带有计数零的log header；这必须在下一个transaction开始写入logged blocks之前发生，以便在崩溃时恢复不会使用一个transaction的头以及后续transaction的logged blocks。

recover_from_log()是从initlog()调用的，而initlog()是在引导过程中，在第一个用户进程运行之前从fsinit()被调用。它读取log header，并在header指示日志包含一个已提交transaction时模仿end_op()的操作。

日志的一个示例用法出现在filewrite()中。该transaction如下：

1
2
3
4
5

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

此代码被包装在一个循环中，将大型写操作分解为仅包含几个扇区的单独transaction，以避免日志溢出。writei()的调用在此transaction中写入许多块：文件的 inode，一个或多个bitmap blocks以及一些data blocks。

Code: Block allocator

文件和目录内容存储在磁盘块中，这些块必须从一个空闲的pool中分配。Xv6 的block allocator在磁盘上维护一个free bitmap，每个块对应一个位。零位表示相应的块是空闲的；一位表示它正在使用中。mkfs程序设置与boot sector、superblock、log blocks、inode 块和bitmap blocks对应的位。

Block allocator提供两个功能：balloc()用于分配新的磁盘块，bfree()用于释放块。balloc()中的循环（kernel/fs.c）考虑每个块，从块 0 到 sb.size（文件系统中的块数）。它查找bitmap位为零的块，表示它是空闲的。如果找到这样的块，balloc()就会更新bitmap并返回该块。为了提高效率，循环分为两个部分。外部循环读取每个bitmap位的块。内部循环检查单个bitmap block中的所有Bits-Per-Block（BPB）。如果两个进程尝试同时分配块，可能发生的竞争由于缓冲区缓存一次只允许一个进程使用任何一个bitmap block而被阻止。

bfree()找到正确的bitmap block并清除正确的位。同样，由bread()和brelse()隐含的独占使用避免了对显式锁定的需求。

与本章剩余部分描述的大部分代码一样，balloc()和bfree()必须在一个transaction内调用。

Inode layer

术语 “inode” 可以有两个相关的含义。它可能指的是包含文件大小和数据块编号列表的磁盘上的数据结构。或者 “inode” 可能指的是内存中的 inode，其中包含磁盘上 inode 的副本以及内核内部所需的额外信息。

磁盘上的 inodes 被紧密地打包成一个称为 inode 块的连续磁盘区域。每个 inode 的大小相同，因此，根据给定的编号 n，可以轻松找到磁盘上的第 n 个 inode。实际上，这个编号 n，称为 inode 编号或 i-number，是实现中用于标识 inodes 的方式。

磁盘上的 inode 由struct dinode定义。type 字段区分文件、目录和特殊文件（设备）。类型为零表示磁盘上的 inode 是空闲的。nlink 字段计算引用此 inode 的目录条目数量，以便在应该释放磁盘上的 inode 及其数据块时识别。size 字段记录文件内容的字节数。addrs 数组记录持有文件内容的磁盘块的块编号。

内核将active的 inodes 集合保存在内存中的一个称为 itable 的表中；struct inode是磁盘上 struct dinode 的内存副本。内核仅在有 C 指针引用该 inode 时才将 inode 保存在内存中。ref 字段计算引用该内存中的 inode 的 C 指针数量，如果引用计数降至零，内核将从内存中丢弃该 inode。iget() 和 iput() 函数获取和释放对 inode 的指针，同时修改引用计数。指向 inode 的指针可以来自文件描述符、当前工作目录和transient kernel code（如 exec）。

xv6 的 inode 代码中有四个锁或类似锁的机制。itable.lock 保护 inode 最多只在 inode 表中出现一次的不变性，以及内存中的 inode 的 ref 字段计算指向该 inode 的内存指针的数量的不变性。每个内存中的 inode 都有一个 lock 字段，其中包含一个 sleep-lock，确保对 inode 的字段（如文件长度）以及 inode 的文件或目录内容块的独占访问。如果 inode 的 ref 大于零，则系统会在表中维护该 inode，并且不会重用表条目以用于不同的 inode。最后，每个 inode 包含一个 nlink 字段（在磁盘上和在内存中复制），计算引用文件的目录条目数量；如果 inode 的链接计数大于零，xv6 将不会释放该 inode。

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

iget() 返回的 struct inode 可能没有任何有用的内容。为了确保它包含磁盘上 inode 的副本，代码必须调用 ilock。这将锁定 inode（以便其他进程无法锁定它），并从磁盘读取 inode，如果尚未读取。iunlock 释放 inode 上的锁。将获取 inode 指针与锁定分开有助于在某些情况下避免死锁，例如在目录查找期间。多个进程可以持有 iget() 返回的指向 inode 的 C 指针，但一次只能有一个进程锁定 inode。

inode表仅存储内核代码或数据结构持有 C 指针的 inodes。其主要工作是同步多个进程的访问。inode表也恰好缓存了频繁使用的 inodes，但缓存是次要的；如果 inode 频繁使用，缓冲区缓存可能会保持它在内存中。修改内存中的 inode 的代码使用 iupdate() 将其写入磁盘。

Code: Inodes

为了分配一个新的 inode（例如，创建文件时），xv6 调用 ialloc()（kernel/fs.c）。ialloc() 类似于 balloc()：它循环遍历磁盘上的 inode 结构，逐个块查找标记为 free 的 inode。当找到一个时，它通过将新的类型写入磁盘来声明它，然后通过调用 iget() 返回 inode 表中的一个条目。ialloc() 的正确操作依赖于一个事实，即一次只能有一个进程持有对 bp 的引用：ialloc() 可以确信没有其他进程同时看到 inode 可用并尝试声明它。

iget() 在 inode 表中查找一个具有所需设备和 inode 编号的活动条目（ip->ref > 0）。如果找到一个，它将返回对该 inode 的新引用。在扫描时，iget 记录了第一个空槽的位置，如果需要分配表条目，它将使用该位置。

代码在读取或写入 inode 的metadata或内容之前必须使用 ilock() 锁定 inode。ilock()为此目的使用了一个 sleep-lock。一旦 ilock 具有对 inode 的独占访问权，它将根据需要从磁盘（更可能是缓冲区缓存）读取 inode。iunlock() 函数释放了 sleep-lock，这可能导致正在休眠的任何进程被唤醒。

iput() 通过减少引用计数释放对 inode 的 C 指针。如果这是最后一个引用，那么 inode 表中的该 inode 位置现在空闲，可以用于不同的 inode。

如果 iput() 发现没有 C 指针引用一个 inode，并且该 inode 没有指向它的链接（在任何目录中都没有），那么这个 inode 及其data block必须被释放。iput() 调用 itrunc() 将文件截断为零字节，释放数据块；将 inode 类型设置为 0（未分配）；并将 inode 写入磁盘。

iput() 在释放 inode 的情况下的锁定协议值得仔细研究。一个危险是，一个并发线程可能正在 ilock() 中等待使用此 inode（例如，读取文件或列出目录），并且还没准备好发现该 inode 不再分配。这不会发生，因为系统调用无法在它没有对其进行链接的情况下获取指向内存中 inode 的指针，而 ip->ref 为 1。这一个引用是调用 iput() 的线程拥有的引用。iput() 确实在 itable.lock 临界区外检查引用计数是否为 1，但在那时，链接计数已知为零，因此没有线程会尝试获取新引用。另一个主要的危险是，一个并发的 ialloc() 调用可能选择 iput() 正在释放的相同 inode。这只能在 iupdate() 写入磁盘后，inode 具有类型零的情况下发生。这种竞争是无害的；分配线程将在读取或写入 inode 之前礼貌地等待获取 inode 的 sleep-lock，在那时 iput 已经完成了对它的使用。

iput() 可以写入磁盘。这意味着任何使用文件系统的系统调用都可能写入磁盘，因为该系统调用可能是对文件的最后一个引用。即使像 read() 这样表面上是只读的调用，也可能最终调用 iput()。这反过来意味着即使是只读系统调用，如果它们使用文件系统，也必须包装在transaction中。

iput() 和crash之间存在一个复杂的交互。iput() 在文件的链接计数降至零时并不立即截断文件，因为某些进程可能仍然在内存中持有对 inode 的引用：进程可能仍然在读取和写入文件，因为它成功打开了文件。但是，如果在最后一个进程关闭文件描述符之前发生崩溃，那么文件将在磁盘上标记为已分配，但没有目录项指向它。

文件系统处理这种情况的方式有两种。简单的解决方案是在重启后的恢复过程中，文件系统扫描整个文件系统，查找已标记为分配但没有目录项指向它们的文件。如果存在这样的文件，它们就可以被释放。

第二种解决方案则无需扫描整个文件系统。在这种解决方案中，文件系统在磁盘上记录（例如，在super block中）链接计数降至零但引用计数不为零的文件的 inode 编号。如果文件系统在引用计数达到 0 时删除文件，那么它会通过从列表中删除该 inode 来更新磁盘上的列表。在恢复时，文件系统会释放列表中的任何文件。

Xv6 没有实现这两种解决方案，这意味着即使 inode 不再使用，它们可能仍然在磁盘上标记为已分配。这意味着随着时间的推移，xv6 有可能会耗尽磁盘空间。

Code: Inode content

磁盘上的 inode 结构 struct dinode 包含一个大小（size）和一个block numbers数组（见图 8.3）。inode 数据位于列在 dinode 的 addrs 数组中的块中。前 NDIRECT 个数据块列在数组的前 NDIRECT 个条目中；这些块称为直接块（direct blocks）。接下来的 NINDIRECT 个数据块的位置不在 inode 中，而是在一个称为间接块（indirect block）的数据块中。addrs 数组中的最后一个条目给出了间接块的地址。因此，文件的前 12 kB（NDIRECT x BSIZE）字节可以从 inode 中列出的块中加载，而接下来的 256 kB（NINDIRECT x BSIZE）字节只能在查阅间接块后加载。这是一种适合磁盘的表示，但对客户端而言过于复杂。函数 bmap() 管理这种表示，以便higher-level routines，例如后面将要看到的 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()首先释放direct blocks，然后释放indirect block中列出的块，最后释放indirect block本身。

bmap() 使得 readi() 和 writei() 能够轻松获取到 inode 的数据。readi()首先确保偏移量和计数不超出文件的末尾。从文件末尾开始的读取返回错误，而从文件末尾开始或横跨文件末尾的读取返回比请求的字节数少。主循环处理文件的每个块，将数据从缓冲区复制到 dst。writei() 与 readi() 相同，有三个例外：从文件末尾开始或横跨文件末尾的写入将增加文件的大小，最多增长到MAXFILE*BSIZE；循环将数据复制到缓冲区而不是从中复制；如果写入扩展了文件，则 writei() 必须更新其大小。

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

Code: directory layer

一个目录在内部的实现方式与文件非常相似。它的 inode 的类型是 T_DIR，其数据是目录项的序列。每个目录项是一个 struct dirent（kernel/fs.h），其中包含一个名称和一个 inode 号。名称最多为 DIRSIZ（14）个字符；如果较短，它以 NULL（0）字节终止。inode 号为零的目录项是空闲的。

函数 dirlookup()（kernel/fs.c）在目录中搜索具有给定名称的条目。如果找到，则返回指向相应 inode 的指针（未锁定），并将 *poff 设置为目录内条目的字节偏移量，以便调用者希望对其进行编辑。如果 dirlookup() 找到具有正确名称的条目，它将更新 *poff 并返回通过 iget() 获得的未锁定 inode。dirlookup() 是 iget() 返回未锁定 inode 的原因。调用者已锁定 dp，因此如果查找是为了 .（表示当前目录的别名），在返回之前尝试锁定 inode 将尝试重新锁定 dp 并导致死锁。（涉及多个进程和 ..，表示父目录的别名，有更复杂的死锁场景；. 不是唯一的问题。）调用者可以解锁 dp 然后锁定 ip，确保一次只持有一个锁。

函数 dirlink()向目录 dp 写入具有给定名称和 inode 号的新目录项。如果名称已经存在，dirlink() 返回错误。主循环读取目录条目，寻找未分配的条目。当找到一个时，它提前结束循环，off 设置为可用条目的偏移量。否则，循环以 dp->size 为结束，dirlink() 然后通过在偏移量 off 处写入新条目将新条目添加到目录中。

Code: Path names

Path names查找涉及对 dirlookup() 的一系列调用，每个调用对应路径的一个组成部分。namei()评估路径并返回相应的 inode。函数 nameiparent() 是一个变体：它在最后一个元素之前停止，返回父目录的 inode 并将最后一个元素复制到 name 中。这两个函数都调用了执行实际工作的通用函数 namex()。

namex() 首先决定路径评估从哪里开始。如果路径以斜杠开头，评估将从根目录开始；否则，从当前目录开始。然后使用 skipelem() 逐个考虑路径的每个元素。循环的每次迭代都必须在当前 inode ip 中查找 name。迭代从锁定 ip 并检查其是否为目录开始。如果不是，则查找失败。（锁定 ip 是必要的，不是因为 ip->type 可能在底层发生变化，而是因为在运行 ilock 之前，不能保证已从磁盘加载 ip->type。）如果调用了nameiparent 并且这是最后一个路径元素，则循环提前停止，根据 nameiparent() 的定义；最后的路径元素已经复制到 name 中，因此 namex 只需返回未锁定的 ip。最后，循环使用 dirlookup() 查找路径元素并准备进行下一次迭代，设置 ip = next。当循环耗尽路径元素时，返回 ip。

namex() 过程可能需要很长时间才能完成：它可能涉及多个磁盘操作，用于读取路径名中遍历的目录的 inode 和目录块（如果它们不在缓冲区中）。Xv6 被精心设计以便于在一个内核线程的 namex() 调用由于磁盘 I/O 而被阻塞的情况下，另一个内核线程查找不同的路径名可以同时进行。namex() 单独锁定路径中的每个目录，以便在不同的目录中进行的查找可以并行进行。

这种并发性带来了一些麻烦。例如，当一个内核线程正在查找路径名时，另一个内核线程可能正在通过取消链接目录来更改目录树。潜在的风险是，查找可能正在搜索已被另一个内核线程删除的目录，其块已被重新用于另一个目录或文件。

Xv6避免了这样的竞争情况。例如，在namex()中执行dirlookup()时，查找线程持有目录的锁，dirlookup()返回一个使用iget()获得的inode。iget()增加了inode的引用计数。只有在从dirlookup()接收到inode后，namex()才释放对目录的锁。现在，另一个线程可以从目录中取消链接inode，但是xv6不会立即删除inode，因为inode的引用计数仍然大于零。

另一个风险是死锁。例如，当查找".“时，next指向与ip相同的inode。在释放ip的锁之前锁定next将导致死锁。为了避免这种死锁，namex()在获取对next的锁之前释放目录的锁。在这里我们再次看到iget()和ilock()之间的分离的重要。

File descriptor layer

Unix接口的一个很酷的方面是，Unix中的大多数资源都被表示为文件，包括console、pipe，当然还有真实的文件。File descriptor层是实现这种一致性的层。

Xv6为每个进程提供了其自己的打开文件表，或者称为文件描述符，正如我们在第一章中看到的那样。每个打开的文件由一个struct file表示，它是一个围绕inode或pipe的包装器，还有一个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()释放底层的pipe或inode，根据类型而定。

filestat()、fileread()和filewrite()函数实现了对文件的stat、read和write操作。filestat()只允许在inodes上调用，并调用stati()。fileread()和filewrite()检查打开模式是否允许该操作，然后将调用传递给pipe或inode的实现。如果文件表示inode，fileread()和filewrite()使用I/O偏移作为操作的偏移，然后将其递增。Pipe没有偏移的概念。回想一下，inode函数要求调用者处理锁定。inode锁定的方便之处在于读写偏移是原子更新的，因此同时对同一文件进行多次写入不能覆盖彼此的数据，尽管它们的写入可能交织在一起。

Code: System calls

具有较低层提供的功能，大多数系统调用的实现都很简单（见(kernel/sysfile.c)）。有一些调用值得仔细研究。

函数sys_link和sys_unlink编辑目录，创建或删除对inodes的引用。它们是使用transaction的强大功能的另一个很好的例子。sys_link开始通过获取其参数，两个字符串old和new。假设old存在且不是目录，sys_link增加了它的ip->nlink计数。然后，sys_link调用nameiparent()来找到new的父目录和最终路径元素，并创建一个指向old的inode的新目录项。新的父目录必须存在，并且在相同的设备上：inode号仅在单个磁盘上有唯一的含义。如果发生此类错误，sys_link必须返回并减少ip->nlink。

transaction简化了实现，因为它需要更新多个磁盘块，但我们不必担心执行它们的顺序。它们要么全部成功，要么全部不成功。例如，如果没有transaction，先更新ip->nlink再创建链接会使文件系统暂时处于不安全状态，而在两者之间崩溃可能导致混乱。有了transaction，我们就不必担心这个问题。

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 flag，它调用create()。否则，它调用namei()。create()返回一个锁定的inode，但namei()没有，所以sys_open()必须自己锁定inode。这提供了一个方便的机制来检查目录是否只能以读方式打开，而不能以写方式打开。假设inode以某种方式获取，sys_open()分配一个文件和一个文件描述符，然后填充文件。请注意，由于它只在当前进程的表中，因此没有其他进程可以访问部分初始化的文件。

第7章在我们甚至没有文件系统之前就研究了pipe的实现。sys_pipe()函数通过提供一种创建pipe对的方式将其连接到文件系统。它的参数是指向两个整数空间的指针，它将记录两个新文件描述符。然后，它分配pipe并安装文件描述符。

Real world

实际操作系统中的buffer cache比xv6的复杂得多，但它具有相同的两个目的：缓存和同步对磁盘的访问。xv6的buffer cache，就像xv6的一样，使用了简单的最近最少使用（LRU）淘汰策略；有许多更复杂的策略可以实现，每个都对某些工作负载有效，对其他工作负载则不太有效。一个更有效的LRU缓存会消除链表，而是使用哈希表进行查找和用于LRU淘汰的堆。现代buffer cache通常与虚拟内存系统集成，以支持内存映射文件。

xv6的日志系统效率较低。在文件系统系统调用期间，不能同时发生提交。该系统记录整个块，即使块中只更改了少量字节。它执行同步的日志写入，每次写入一个块，每次写入很可能需要整个磁盘旋转时间。真实的日志系统解决了所有这些问题。

日志记录不是提供崩溃恢复的唯一方法。早期的文件系统在重新启动时使用清理程序（例如UNIX的fsck程序）来检查每个文件和目录以及块和inode空闲列表，查找并解决不一致。对于大型文件系统，清理可能需要几个小时，并且存在无法以使原始系统调用成为原子操作的方式解决不一致的情况。从日志中恢复要快得多，并且在面临崩溃时使系统调用成为原子操作。

Xv6使用与早期UNIX相同的基本磁盘上的inode和目录布局；这种方案多年来一直非常持久。BSD的UFS/FFS和Linux的ext2/ext3基本上使用相同的数据结构。文件系统布局中最低效的部分是目录，在每次查找时需要在所有磁盘块上进行线性扫描。当目录只占用几个磁盘块时，这是合理的，但对于包含许多文件的目录而言，这是昂贵的。Microsoft Windows的NTFS，macOS的HFS和Solaris的ZFS等实现目录为磁盘上的均衡块树。这很复杂，但保证了对数时间的目录查找。

Xv6对磁盘故障的处理比较简单：如果磁盘操作失败，xv6就会崩溃。这是否合理取决于硬件：如果操作系统位于使用冗余来掩盖磁盘故障的特殊硬件之上，也许操作系统很少见到故障，那么崩溃可能是可以接受的。另一方面，使用普通磁盘的操作系统应该预期到发生故障，并更优雅地处理它们，以便一个文件中的一个块的丢失不会影响文件系统的其余部分的使用。

Xv6要求文件系统适应一个磁盘设备并且大小不会改变。随着大型数据库和多媒体文件推动存储需求不断增加，操作系统正在开发消除“one disk per file system”的瓶颈的方法。基本的方法是将多个磁盘组合成一个单一的逻辑磁盘。硬件解决方案，如RAID，仍然是最流行的，但目前的趋势是朝着尽可能在软件中实现这些逻辑的方向发展。这些软件实现通常允许丰富的功能，如通过添加或删除磁盘来动态调整逻辑设备的大小。当然，一个可以动态增长或缩小的存储层需要一个可以执行相同操作的文件系统：xv6使用的固定大小的inode块数组在这样的环境中效果不佳。将磁盘管理与文件系统分离可能是最清晰的设计，但两者之间复杂的接口导致一些系统（如Sun的ZFS）将它们合并起来。

Xv6的文件系统缺乏现代文件系统的许多其他功能；例如，它不支持快照和增量备份。

现代Unix系统允许使用与磁盘存储相同的系统调用访问许多种类的资源：named pipes、网络连接、远程访问的网络文件系统以及监控和控制接口，如/proc。与xv6在fileread()和filewrite()中的if语句不同，这些系统通常为每个打开的文件提供一个函数指针表，每个操作一个函数指针，并调用函数指针来调用该inode对调用的实现。网络文件系统和用户级文件系统提供将这些调用转换为网络RPC并在返回之前等待响应的函数。