文件系统的目的是为了组织和保存数据。文件系统通常支持在用户和应用之间分享数据，并且支持持久化，以便数据在重启后依旧有效。

xv6文件系统提供Unix-like文件、目录和路径（见第0章），并且为了持久化将数据保存在IDE硬盘中（见第3章）。文件系统需要解决以下几个挑战：

文件系统需要保存在硬盘上（on-disk）的数据结构去表示已命名的目录和文件的树形结构，记录保存每个文件内存的块的标记，还要记录硬盘中那些区域是空闲的。
文件系统还要支持故障恢复（crash recovery）。也就是说，如果出现故障（如断电），文件系统在重启之后依旧能正常工作。风险在于，崩溃可能会中断一系列更新，并使磁盘上的数据结构不一致（例如一个块仍被文件使用却被标志位空闲）。
不同的进程可以同时在文件系统上运行，并且必须进行协调以保持一致性。
访问磁盘的速度比访问内存要慢数量级，因此文件系统必须维护常用块的内存中缓存。

本章剩余部分解释了xv6如何解决上述挑战

简介

Xv6文件系统实现分为七个层，如图6-1所示。磁盘层读取和写入IDE硬盘驱动上的块。高速缓存层缓存磁盘块并同步对它们的访问，确保一次只有一个内核进程可以修改存储在任何特定块中的数据。日志层允许更高层将对多个快块的更新包装到一个事务（transaction）中，并确保这些块在发生崩溃时进行原子更新（即所有这些块都已更新或没有更新）。Inode层提供了单独的文件，每个文件表示为具有唯一i-number的inode和一些包含文件数据的块。目录层将每个目录实现为一种特殊的inode，其内容是目录项的序列，每个条目都包含文件名和i-number。路径层（pathname layer）提供分层路径名称，如/usr/rtm/xv6/fs.c，并通过递归查找对其进行解析。文件描述符层使用文件系统接口抽象了许多Unix资源（如管道、设备，文件等），简化了应用程序员的工作。

文件系统必须有一个计划，决定在磁盘上存储inodes和内容块的位置。为此，xv6将磁盘划分为多个部分，如图6-2所示。文件系统不使用block 0（它保存boot sector）。Block 1被称为超级块（superblock）；它包含有关文件系统的元数据（块中的文件系统大小、数据块的数量、inodes的数量和日志中的块数）。从Block 2开始保存 inodes，每个块有多个inodes。在这些数据块之后，位图块（bitmap blocks）跟踪正在使用的数据块。其余的大多数块都是数据块；每个都在位图块中标记为”空闲”，或保留文件或目录的内容。磁盘末端的块保存日志层的日志。

本章的其余部分讨论了每个层，从缓冲区缓存开始。在较低层选择良好的抽象可使得设计较高层变得轻松。

Buﬀer cache Layer

缓冲区缓存有两个作业：（1）同步对磁盘块的访问，以确保内存中只有一个块的副本，并且一次只有一个内核线程使用该副本；（2）缓存热点块，使它们不会从慢速磁盘重新读取。该代码是在bio.c。

缓冲区缓存层提供的主要接口是bread和bwrite；前者获取一个buf，其包含可在内存中读取或修改的块的副本，后者将修改后的缓冲区写入磁盘上的相应块。内核线程必须在使用缓冲区后通过调用brelse来释放缓冲区。

缓冲区缓存通过允许最多一个内核线程具有对块缓冲区的引用来同步对每个块的访问。如果一个内核线程获得了对缓冲区的引用，但尚未释放，则其他线程对同一块的bread的调用将等待。较高的文件系统层依赖于缓冲区缓存的块同步，以帮助它们维持一致性。

缓冲区缓存具有固定数量的缓冲区来容纳磁盘块，这意味着，如果文件系统要求的块尚未在缓存中，则缓冲区缓存必须回收当前包含某些其他块的缓冲区。缓冲区缓存回收最近使用最少的新块缓冲区。假设是，最近使用最少的缓冲区是最不可能很快再次使用的缓冲区。

Code: Buﬀer cache

缓冲区缓存是缓冲区的双向链表（doubly-linked list）。由main（1231）调用的函数binit使用静态数组buf中的NBUF个缓冲区初始化列表（4350-4359）。对缓冲区缓存的所有其他访问都是通过bcache.head来引用链表，而不是通过buf数组。

缓冲区有三个与之关联的状态位。B_VALID表示缓冲区包含块的副本。B_DIRTY表示缓冲区内容已被修改，需要写入磁盘。B_BUSY表示某些内核线程具有对此缓冲区的引用，但尚未释放它。

bread（4402）调用bget，以获得给定扇区（4406）的缓冲。如果需要从磁盘读取缓冲区，bread会在返回缓冲区之前调用iderw来进行读取。

Bget（4366）使用给定的设备和扇区编号扫描缓冲区列表以获取缓冲区（4373-4384）。如果有这样的缓冲区，并且缓冲区不忙，bget设置B_BUSY标志并返回（4376-4383）。如果缓冲区已在使用中，bget在缓冲区上休眠等待其释放。当sleep返回时，bget不能假定缓冲区现在可用。事实上，由于sleep释放和重新获得buf_table_lock，不能保证b仍然是正确的缓冲区：可能它已被重用到不同的磁盘扇区。Bget必须重新开始（4382），希望这次的结果会有所不同。

如果给定扇区没有缓存缓冲区，bget必须创建一个缓冲区，可能会重用包含不同扇区的缓冲区。它第二次扫描缓冲区列表，寻找空闲的的缓冲区：可以使用任何此类缓冲区。Bget编辑缓冲区元数据以记录新设备和扇区编号，并在返回缓冲区之前标记缓冲区为BUSY（4393-4395）。请注意，对标志的分配不仅设置了B_BUSY位，而且还清除了B_VALID和B_DIRTY位，从而确保bread将从磁盘读取块数据，而不是错误地使用缓冲区以前的内容。

由于缓冲区缓存用于同步，因此特定磁盘扇区只有一个缓冲区是很重要的。这些分配（4391-4393）是安全的，因为bget的第一个循环确定该扇区已经不存在缓冲区，此后bget没有放弃buf_table_lock。

如果所有的缓冲区都很忙，就出了问题：bget panics。一个更优雅的反应可能是sleep，直到有缓冲区变得空闲，尽管这样就有可能出现死锁。

一旦bread将缓冲区返回给其调用方，调用方就可以独占使用（exclusive use）该缓冲区，并且可以读取或写入数据字节。如果调用方确实写入了数据，则必须调用bwrite将更改后的数据写入磁盘，然后再释放缓冲区。Bwrite（4414）设置B_DIRTY标志，并调用iderw将缓冲区写入磁盘。

当调用方使用缓冲区完成时，它必须调用brelse释放它。（brelse，是b-release的缩短，是神秘的（cryptic），但值得学习：它起源于Unix，并在BSD，Linux 和 Solaris 也使用。Brelse（4425）将缓冲区移动到链表的前面（4432-4437），清除B_BUSY位，并唤醒在缓冲区上休眠的任何进程。移动缓冲区会导致根据缓冲区最近的使用方式（意味着已释放）对列表进行排序：列表中的第一个缓冲区是最近使用的缓冲区，最后一个缓冲区是最近使用的缓冲区。Bget 中的两个循环利用了这一点：对现有缓冲区的扫描必须在最坏的情况下处理整个列表，但首先检查最近使用的缓冲区（从bcache.head开始，然后是next指针）将减少扫描时间。选择缓冲区以重复使用的扫描通过向后扫描（在prev指针之后）选择最近使用最少的缓冲区。

Logging layer

文件系统设计中最有趣的问题之一是崩溃恢复（crash recovery）。出现此问题的原因是，许多文件系统操作涉及对磁盘的多次写入，并且写入一部分后发生崩溃可能会使磁盘上的文件系统处于不一致的状态。例如，根据磁盘写入的顺序，文件删除过程中的崩溃可能会使目录项指向空闲inode，也可能会保留已分配但未引用的inode。后者是相对良性的，但一个目录条目，指向一个释放的inode很可能会在重新启动后导致严重的问题。

Xv6通过简单版本的日志（simple version of loggin）解决了文件系统操作过程中的崩溃问题。Xv6系统调用不会直接写入磁盘上的文件系统数据结构。相反，它将把有关所有磁盘写入的描述写入磁盘上的日志中。一旦系统调用记录了它的所有写入操作，它就会将一个特殊的提交记录写入磁盘，这表明日志包含一个完整的操作。此时，系统调用将写入操作复制到磁盘上文件系统数据结构。这些写入完成后，系统调用将擦除磁盘上的日志。

如果系统崩溃并重新启动，文件系统代码将从崩溃中恢复，然后再运行任何进程。如果日志被标记为包含完整的操作（containing a complete operation），则恢复代码会将写入操作复制到它们在磁盘文件系统中的位置。如果未将日志标记为包含完整操作，则恢复代码将忽略该日志。恢复代码通过擦除它来结束。

为什么xv6的日志解决了文件系统操作过程中的崩溃问题？如果在提交操作之前发生崩溃，则磁盘上的日志将不会标记为已完成，恢复代码将忽略它，并且磁盘的状态将像操作甚至尚未启动一样。如果在操作提交后发生崩溃，则恢复代码将重做所有写入操作，如果操作已开始将其写入磁盘数据结构，则可能会重复这些写入操作。无论哪种情况，日志都会使操作成为与崩溃有关的原子操作：恢复后，操作的所有写入都显示在磁盘上，或者这些写入操作都不会出现。

Log design

日志驻留在磁盘末尾的已知固定位置。它由一个标头块（header block）和一系列更新的块副本（”记录块”，logged blocks）组成。标头块包含一个扇区编号数组，对应每个记录块。标头块还包含记录块的数量。Xv6在事务提交时写入标头块，并将记录块复制到文件系统后将计数设置为零。因此，事务中途崩溃将导致日志的标头块中的计数为零；提交后的崩溃将导致非零计数。

每个系统调用的代码都指示原子写入序列的开始和结束。为了提高效率，并允许文件系统代码中的一定程度的并发性，日志记录系统可以在每个事务中累积多个系统调用的写入。因此，一次提交可能涉及多个完整系统调用的写入。为了保持原子性，只有在没有文件系统的系统调用的情况下，日志记录系统才会提交。

同时提交多个事务的想法称为组提交（group commit）。组提交允许多个事务同时运行，并允许文件系统批处理多个磁盘操作，并向磁盘驱动程序发出单个磁盘操作。这允许磁盘巧妙地安排块的写入，并以磁盘带宽的速率进行写入。Xv6的IDE驱动程序不支持批处理（batching），但xv6的文件系统设计允许批处理。

Xv6在磁盘上指定固定的空间来保存日志。系统调用在事务中写入的块总数必须适合该空间。这有两个后果。任何单个系统调用都不能比日志中的空间更多地写入块。这对大多数系统调用来说不是问题，但其中两个调用可能会编写许多块：write和unlink。大文件写入可能会写入多个数据块和多个位图块以及inode块；取消大文件链接可能会写入多个位图块和inode。Xv6的写入系统调用将大型写入分解为多个适合日志中的较小的写入，并且unlink不会导致问题，因为实际上xv6文件系统只使用一个位图块。有限日志空间的另一个后果是，日志系统无法允许系统调用启动，除非系统调用的写入符合日志中剩余的空间。

Code: logging

系统调用中典型的日志使用如下所示：

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

begin_op（4628）等待，直到日志记录系统当前未提交，直到有足够的可用日志空间来保存此调用和当前正在执行的所有系统调用的写入。log.outstanding记录调用的个数；该增量既保留了空间，又防止了在此系统调用期间发生提交。代码保守地假定每个系统调用可能写入MAXOPBLOCK不同的块。

log_write（4722）充当bwrite的代理。它在内存中记录块的扇区号，在磁盘上保留一个槽（slot），并标记缓冲区B_DIRTY以防止块缓存将其逐出。提交之前，块必须保留在缓存中：此时缓存的副本是修改的唯一记录；直到提交后，它才能写入它在磁盘上的位置；和同一事务中的其他读取必须看到修改。当一个块在单个事务中多次写入时，log_write会收到通知，并分配该块日志中的同一插槽。这种优化通常被称为吸收（absorption）。例如，通常情况下，包含多个文件的inodes的磁盘块在事务中多次写入。通过将多个磁盘写入归并到一个当中，文件系统可以节省日志空间，并可以获得更好的性能，因为只需将磁盘块的一个副本写入磁盘。

end_op（4653）第一个减少未完成（outstanding）的系统调用的计数。如果计数现在为零，它将通过调用commit()提交当前事务。这一过程分为四个阶段。write_log()（4683）将事务中修改的每个块从缓冲区缓存复制到其在磁盘日志中的插槽。write_head()（4604）将标头块写入磁盘：这是提交点（commit point），写入后的崩溃将导致恢复从日志中重做（replaying）事务的写入。install_trans()（4572）从日志中读取每个块，并将其写入文件系统中的适当位置。最后，end_op写入日志标头的计数为零；这必须在下一个事务开始写入记录块之前发生，因此崩溃不会导致使用一个事务的标头与后续事务的记录块进行恢复。

recover_from_log（4618）由initlog（4556）调用，在第一个用户进程运行之前，在引导过程中调用 initlog（2794）。它读取日志标头，如果标头指示日志包含已提交的事务，则模拟（mimics）end_op的操作。日志的一个示例使用发生在filewrite（5752）中。该事务如下所示：

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

此代码被包装在一个循环中，该循环将大型写入分解为一次只包含几个扇区的单个事务，以避免日志溢出。对writei的调用在此事务中写入多个块：文件的inode、一个或多个位图块和一些数据块。

Code: Block allocator

文件和目录内容存储在磁盘块中，这些磁盘块必须从一个可用池（free pool）中分配。xv6的块分配器在磁盘上维护一个空闲位图（free bitmap），每个块有一个位。零位表示相应的块是空闲的；一个位表示它正在使用中。引导扇区、超级块、inode块和位图块对应不同位，并且Bitmap块对应的位总是设置为1。

块分配器提供了两个功能：balloc分配一个新的磁盘块，然后bfree释放一个块。Balloc（4804）首先调用readsb将磁盘上的超级块（或buﬀer cache）读入sb.balloc，通过计算引导扇区、超级块和inodes（使用BBLOCK）消耗多少块来决定哪些块持有数据块自由位图。循环（4812）考虑每个块，从块0开始，直到sb.size（文件系统中的块数）。它查找位图位为零的块，这表示它是空闲的。如果balloc找到这样的块，它将更新位图并返回该块。为了提高效率，循环被拆分为两个部分。外部循环读取位图位的每个块。内部循环检查单个位图块中的所有BPB位。如果两个进程尝试同时分配一个块，则可能发生的竞争由于缓冲区缓存只允许一个进程同时使用任何一个位图块而被阻止。

Bfree（4831）找到正确的位图块并清除正确位。同样，bread和brelse所暗示的独家使用避免了显式锁定的需要。

与本章其余部分中描述的大部分代码一样，必须在事务中调用balloc和bfree。

Inode layer

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

所有磁盘上的inodes都被打包到一个连续的磁盘区域（contiguous area）中，称为inode块。每个inode的大小相同，因此在给定数字n的情况下，很容易在磁盘上找到第n个inode。事实上，这个数字n，称为inode number或i-number，是如何识别inode的实现方式。

磁盘上的inode由struct dinode（3926）定义。type字段区分文件、目录和特殊文件（设备)。type为0表示磁盘上的inode是空闲的。Nlink字段计算引用此inode的目录项的数量，以便识别何时应释放磁盘上的inode及其数据块。size字段记录文件中内容的字节数。addrs数组记录保存文件内容的磁盘块的块号。

内核在内存中保留一组活动的inodes； struct inode（4012）是磁盘上struct dinode的内存副本。只有当存在引用该inode的C指针时，内核才会在内存中存储一个inode。Ref字段计算引用内存中inode的C指针的数量，如果引用计数下降到零，内核将从内存中丢弃inode。iget和iput函数获取和释放指向inode的指针，修改引用计数。指向inode的指针可以来自文件描述符、当前工作目录和瞬态内核代码（transient kernel code，如exec）。

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

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

Inode缓存仅缓存内核代码或数据结构包含C指针的inode。它的主要工作实际上是通过多个进程而不是缓存来同步访问。如果频繁使用inode，则如果不由inode缓存保存，则缓冲区缓存可能会将其保留在内存中。

Code: Inodes

若要分配新的inode（例如，在创建文件时），xv6调用ialloc（4953）。Ialloc类似于balloc：它在磁盘上的inode结构上循环，一次一个块，寻找一个标记为空闲的结构。当它找到一个，它通过将新类型写入磁盘来声明（claim）它，然后从inode cache返回一个条目并尾调用iget（4970）。Ialloc的正确操作取决于这样一个事实，即一次只能有一个进程持有对bp的引用：ialloc可以确保其他进程不会同时看到inode可用并尝试声明它。

Iget（5004）通过inode cache查看具有所需设备和inode编号的活动条目（ip->ref >0）。如果找到一个，它将返回对该inode的新引用（5013-5017）。当iget扫描时，它记录第一个空插槽（5018-5019）的位置，如果需要分配缓存条目，它将使用该位置。

在读取或写入其元数据或内容之前，代码必须使用ilock锁定inode。Ilock（5053）使用现在熟悉的睡眠循环来等待ip_flag的I_BUSY是否空闲，然后设置它（5062-5064）。一旦ilock具有对inode的独占访问权限（exclusive access），它就可以根据需要从磁盘加载inode元数据（更有可能是缓冲区缓存）。函数iunlock（5085）清除I_BUSY 位，并唤醒睡在ilock中的任何进程。

Iput（5108）通过递减引用计数（5124）将释放指向inode的C指针。如果这是最后一个引用，则 inode缓存中的inode插槽现在是空闲的，可以重新用于不同的inode。

如果iput看到没有指向inode的C指针引用，并且没有指向inode的链接（发生在没有目录中），则必须释放inode及其数据块。Iput重新锁住inode；调用itrunc将文件截断（truncate）为零字节，释放数据块；将inode类型设置为0（未分配）；将更改写入磁盘；最后解锁inode（5111-5123）。

在释放inode的情况下，锁定协议（locking protocol）值得仔细研究。首先，当通过设置I_BUSY锁定ip时，iput假定它已解锁。这必须是这样：调用方需要在调用iput之前解锁ip，并且没有其他进程可以锁定此inode，因为没有其他进程可以获得指向它的指针。这是因为，在此代码路径中，inode没有引用，没有链接（即没有路径名引用它），并且没有（尚未）标记为空闲。第二部分值得研究的是iput临时释放（5116）并重新获取（5120）的inode缓存锁，因为itrunc和iupdate将在磁盘I/O期间休眠。但我们必须考虑在没有锁的情况下可能会发生什么。具体来说，一旦iupdate 完成，磁盘inode将被标记为免费，并在iput完成之前，对ialloc的并发调用可能会找到它并重新分配它。Ialloc通过调用iget，将返回对块的引用，它将在缓存中找到ip，看到I_BUSY标志已设置，并休眠。现在，与磁盘相比，内核中的inode不同步：ialloc重新初始化磁盘版本，但在ilock期间依赖调用方将其加载到内存中。为了确保发生这种情况，iput在释放inode锁之前，不仅必须清除I_BUSY，还必须清除I_VALID。它通过归零标志（5121）来做到这一点。

iput()可以写入磁盘。这意味着使用文件系统的任何系统调用都可能写入磁盘，甚至像read()这样的调用似乎是只读的。这反过来又意味着，即使是只读系统调用，如果它们使用文件系统，也必须包装在事务中。

Code: Inode content

磁盘上的inode结构，struct dinode，包含一个大小和一个块数数组（参见图6-4）。Inode数据在dinode的dinode’s addrs数组中列出的块中找到。数组中的第一个NDIRECT条目中列出了第一个NDECECT数据块；这些块被称为直接块（direct blocks）。下一个NINDECECT数据块不是在inode中列出的，而是在称为间接块（indirect block）的数据块中列出的。addrs数组中的最后一个条目给出了间接块的地址。因此，文件的前6KB（NDECECT BSIZE）字节可以从inode中列出的块加载，而下一个64KB（NINDECT BSIZE）字节只能在咨询间接块后加载。这是一个很好的磁盘表示形式，但对客户端来说是一个复杂的表示形式。函数bmap管理表示（manages the representation），以便更高级别的例程（如readi和writei），我们将很快看到这些例程。Bmap返回inode ip的第bn个数据块的磁盘块号。如果ip还没有这样的方块，bmap将分配一个。

函数bmap（5160）从挑选简单的情况开始：第一个NDIRECT块列在inode本身（5165-5169）中。下一个NINDIECT块列在间接块中，在ip->addrs[NINDIECT]中。Bmap读取间接块（5176），然后从块（5176）内的正确位置读取块号。如果块数超过NDIRECT+NINDECECT，则bmap pancs；writei包含防止这种情况发生的检查（5315）。

Bmap根据需要分配块。一个ip->addrs[]或间接输入零表示没有分配块。当bmap遇到零时，它将替换为按需分配的新块的数量（5166-5167，5174-5175）。

itrunc释放文件的块，将inode的大小重置为零。Itrunc（5206）首先释放直接块（5212-5217），然后释放在间接块（52225225）中列出的块，最后释放间接块本身（5227-5228）。

Bmap使readi和writei更容易获得inode的数据。Readi（5252）首先要确保偏移量和计数不超过文件的末尾。在文件末尾之后开始的读取返回错误（5263-5264），而在文件末尾或交叉的读取返回的字节数少于请求的字节数（5265-5266）。主循环处理文件的每个块，将数据从缓冲区复制到 dst（5268-5273）。writei（5302）与readi相同，但有三种例外：在文件末尾或在文件末尾开始的写入将文件增长，可达最大文件大小（5315-5316）；循环将数据复制到缓冲区而不是输出（5321）；如果写入扩展了文件，则writei必须更新其大小（5326-5329）。

Readi和writei都从检查ip->type == T_DEV开始。这种情况下处理数据不存在于文件系统中的特殊设备；我们将在文件描述符层中返回到这种情况。

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

Code: directory layer

目录在内部实现，就像文件一样。它的inode具有T_DIR类型，其数据是目录项的序列。每个条目都是一个struct dirent（3950），其中包含一个名称和一个inode号。名称最多是DIRSIZ（14）字符；如果较短，则由NUL（0）字节终止。包含inode号零的目录条目是空闲的。

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

函数dirlink（5402）将具有给定名称和inode号的新目录条目写入目录dp。如果名称已存在，dirlink将返回错误（5408-5412）。主循环读取查找未分配项的目录项。当它找到一个时，它会提前停止循环（5372-5373），off设置为可用条目的偏移量。否则，循环以off设置为dp->size结束。无论哪种方式，dirlink都通过写在偏移量off添加一个新的条目到目录中（5422-5425）。

Code: Path names

路径名称查找涉及对dirlookup的连续调用，每个路径组件一个调用。Namei（5540）评估path并返回相应的inode。函数nameiparent是一个变量：它在最后一个元素之前停止，返回父目录的inode并将最后一个元素复制到name中。两者都调用通用函数namex来做实际的工作。

Namex（5505）首先决定路径评估（path evaluation）的起始位置。如果路径以斜杠（Slash）开头，则从根开始计算；否则，从当前目录开始（5509-5512）。然后，它使用skipelem依次考虑路径的每个元素（5514）。循环的每次迭代都必须在当前inode ip中查找名称。迭代首先要锁定ip并检查它是否为目录。如果不是，查找将失败（5515-5519）。（锁定ip是必要的，不是因为ip-type可以在脚底更改（change underfoot，它不能），而是因为在ilock运行之前，不能保证从磁盘加载了ip类型。如果调用是nameiparent和并且是最后一个路径元素，则循环会根据nameiparent的定义提前结束，最终路径元素已被复制到名称中, 因此namex只需返回解锁的ip（5520-5524）。最后循环会使用dirlookup查找路径元素并通过设置ip = next （5525-5530）为下一次迭代做准备。当循环用完路径元素时，它返回ip。

File descriptor layer

Unix接口的一个很酷的方面是，Unix中的大多数资源都可以表示为文件，包括控制台、管道等设备，当然还有实际文件。文件描述符是实现这种一致性（uniformity）的层。

正如我们在第0章中看到的那样，Xv6为每个进程提供了独有的打开文件表或文件描述符。每个打开的文件都由一个struct file（4000）表示，该结构是一个inode或pipe 的包装，外加上一个I/O偏移量。Open的每次调用都会创建一个新的打开文件（一个新的struct file）：如果多个进程独立打开同一文件，则不同的实例将具有不同的I/O偏移量。另一方面，单个打开的文件（相同的结构文件）可以在一个进程的文件表中多次出现，也可以在多个进程的文件表中出现。如果一个进程使用open去打开文件，然后使用dup创建别名，或者使用fork与子进程共享，则会发生这种情况。引用计数值跟踪对特定打开文件的引用数。文件可以打开读取或写入，也可以同时。readable和writable字段跟踪这一点。

系统中所有打开的文件都保存在全局文件表中。文件表具有分配文件（filealloc）、创建重复引用（filealloc）、释放引用（filecloc）以及读取和写入数据（filealloc和filealloc）的函数。

前三个遵循现在熟悉的形式。Filealloc（5625）扫描文件表中的未引用文件（f->ref == 0），并返回新引用；filedup（5652）递增引用计数；fileclose（5664）减少它。当文件的引用计数达到零时，fileclose会根据类型释放基础管道或inode。

函数filestat、fileread和filewrite实现文件上的stat、read和write操作。Filestat（5702）只允许作用在inodes和调用stati。Fileread和filewrite通过open mode检查操作是否被允许，然后将调用传递给管道或inode实现。如果文件表示inode，则fileread和filewrite使用I/O偏移量作为操作的偏移量，然后将其推进（5725-5726、5765-5766）。管道没有偏移量的概念。回想一下，inode函数要求调用方处理锁定（5705-5707，5724-5727，5764-5778）。Inode锁定具有一种方便的副作用，即读取和写入偏移量以原子方式进行更新，因此同时对同一文件的多次写入不能覆盖彼此的数据，尽管它们的写入最终可能会相互交错。

Code: System calls

使用较低层提供的大多数系统调用实现的功能是微不足道的（trivial，请参见sysfile.c）。但仍有几个调用值得仔细研究。

函数sys_link和sys_unlink编辑目录，创建或删除对inodes的引用。它们是使用事务的力量的另一个很好的例子。Sys_link（5913）从获取其参数开始，一个新字符串和一个旧的字符串（5918）。假设旧的存在，且不是一个目录（5922-5925），sys_link增加其ip->nlink。然后，sys_link调用nameiparent来查找新字符串的（5938）的父目录和最终路径元素，并创建一个指向旧inode（5938）的新目录条目。新的父目录必须存在，并且与现有inode位于同一设备上：inode数字在单个磁盘上只有唯一的含义。如果发生这样的错误，sys_link必须返回并减少ip->nlink。

事务简化了实现，因为虽然它需要更新多个磁盘块，但我们不必担心执行这些操作的顺序。他们要么都成功，要么不成功。例如，如果没有事务，在创建链接之前更新ip->nlink会使文件系统暂时处于不安全状态，而两者之间的崩溃可能会导致严重破坏(havoc)。有了事务，我们不必担心这一点。

Sys_link为现有的inode创建一个新名称。函数create（6057）为新的inode创建一个新名称。它是三个文件创建系统调用的泛化：使用O_CREATE标志的open创建一个新的普通文件，mkdir 创建一个新的目录，mkdev创建一个新的设备文件。与sys_link一样，create通过调用nameiparent来得到父目录的inode。然后，它调用dirlookup来检查名称是否已经存在（6067）。如果名称确实存在，则create的行为取决于它所使用的系统调用：open与mkdir和mkdev具有不同的语义。如果create是代表open使用的（type == T_FILE）并且存在的名称本身就是一个常规文件，则open该名称将其视为成功，因此也可以创建（6071）。否则，它是一个错误（6072-6073）。如果名称不存在，create通过ialloc（6076）创建一个新的inode。如果新的inode是一个目录，create初始化它…条目。最后，既然数据已正确初始化，create可以将其链接到父目录（6089）。create，像sys_link，同时持有两个inode的锁：ip和dp。不存在死锁的可能性，因为inode ip是新分配的：系统中没有其他进程会持有ip锁，然后尝试锁定dp。

使用create，可以很容易地实现sys_open、sys_mkdir和sys_mnod。Sys_open（6101）是最复杂的，因为创建新文件只是它所能做的事情的一小部分。如果打开的是O_ CREATE标志，则调用create（6114）。否则，它调用namei（6120）。Create返回锁定的inode，但namei不返回，因此sys_open必须锁定inode本身。这提供了一个方便的地方来检查目录是否只为读取而不是写入打开。假设inode是以这样或那样的方式获得的，sys_open会分配一个文件和一个文件描述符（6132），然后填充该文件（6142-6146）。请注意，没有其他进程可以访问部分初始化的文件，因为它只在当前进程的表中。

在我们有一个文件系统之前，第5章就讲述了管道的实现。函数sys_pipe通过提供一种创建管道对的方法，将该实现连接到文件系统。它的参数是指向两个整数的空间的指针，它将在其中记录两个新的文件描述符。然后，它分配管道并安装文件描述符。

Real world

现实操作系统中的缓冲区缓存比xv6要复杂得多，但它提供了同样的两个用途：缓存和同步对磁盘的访问。Xv6 的缓冲区缓存与V6一样，使用的是最近使用的简单（LRU）逐出策略；有许多更复杂的策略可以实现，每个策略对某些工作负载都有好处，但对其他工作负载就没有那么好。更高效的LRU缓存将消除链接列表，而是使用哈希表进行查找，并为LRU驱逐策略使用堆。现代缓冲区缓存通常与虚拟内存系统集成，以支持内存映射文件。

Xv6的日志记录系统效率低下。提交不能与文件系统调用同时进行。系统记录整个块，即使只更改了块中的几个字节。它执行同步日志写入，一次一个块，每个块都可能需要整个磁盘旋转时间。真正的日志记录系统解决了所有这些问题。

日志记录并不是提供崩溃恢复的唯一方法。早期的文件系统在重新启动期间使用了清除器（scacenger）（例如，UNIX的fsck程序）来检查每个文件和目录以及块和inode空闲列表，查找和解决不一致的问题。清除大型文件系统可能需要数小时，在某些情况下，无法以导致原始系统调用为原子的方式解决不一致问题。从日志中恢复的速度要快得多，并导致系统调用在发生崩溃时是原子的。

Xv6使用与早期UNIX相同的INODES和目录的基本磁盘布局；多年来，这一计划一直非常持久。BSD的UFS/FFS和Linux的ext2ext3使用的数据结构基本相同。文件系统布局中最低效的部分是目录，它需要在每次查找过程中对所有磁盘块进行线性扫描。当目录只有几个磁盘块时，这是合理的，但对于包含许多文件的目录来说，成本很高。仅举几例，微软Windows的NTFS、Mac OS X’s HFS和Solaris的ZFS，实现了一个目录作为磁盘上的平衡树块。这很复杂，但保证了对数时间目录查找。

Xv6对磁盘故障很天真：如果磁盘操作失败，xv6就会恐慌。这是否合理取决于硬件：如果操作系统位于使用冗余来屏蔽磁盘故障的特殊硬件之上，则操作系统可能很少看到故障，从而认为panic是可接受的。另一方面，使用普通磁盘的操作系统应该做好出现故障的准备，并更优雅地处理这些故障，因此在一个文件中丢失一个块不会影响文件系统其余部分的使用。

Xv6要求文件系统适合一个磁盘设备，并且大小不变。随着大型数据库和多媒体文件对存储的要求越来越高，操作系统正在开发消除”每个文件系统一个磁盘”瓶颈的方法。基本方法是将多个磁盘合并到一个逻辑磁盘中。RAID等硬件解决方案仍然是最流行的解决方案，但目前的趋势是尽可能多地在软件中实现这种逻辑。这些软件实现通常允许丰富的功能，如通过动态添加或删除磁盘来增长或收缩逻辑设备。当然，可以动态增长或收缩的存储层需要一个可以执行同样操作的文件系统: xv6使用的固定大小的inode块数组在这种环境中无法正常工作。

将磁盘管理与文件系统分开可能是最干净的设计，但两者之间的复杂接口导致一些系统（如Sun 的ZFS）将它们组合在一起。

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

现代Unix系统允许使用与磁盘存储相同的系统调用访问多种资源：命名管道、网络连接、远程访问的网络文件系统以及监视和控制接口（如/procp）。这些系统通常为每个打开的文件提供一个函数指针表，每个操作一个，并调用函数指针来调用inode对调用的实现，而不是在fileread和filewrite中的xv6的语句。网络文件系统和用户级文件系统提供的功能可将这些调用转换为网络RPCS，并等待响应后再返回。

Exercises

Why panic in balloc? Can xv6 recover?
Why panic in ialloc? Can xv6 recover?
Why doesn’t filealloc panic when it runs out of ﬁles? Why is this more common and therefore worth handling?
Suppose the ﬁle corresponding to ip gets unlinked by another process between sys_link’s calls to iunlock(ip) and dirlink. Will the link be created correctly? Why or why not?
create makes four function calls (one to ialloc and three to dirlink) that it requires to succeed. If any doesn’t，create calls panic. Why is this acceptable? Why can’t any of those four calls fail?
sys_chdir calls iunlock(ip) before iput(cp->cwd)，which might try to lock cp->cwd，yet postponing iunlock(ip) until after the iput would not cause deadlocks. Why not?