文件系统的目的是为了组织和存放数据。文件系统通常是为了用户之间和应用程序之间共享数据使用,同时还能够实现持久话存储,以便于数据在重启之后依旧可用。

xv6文件系统提供了类Unix的文件,目录和路径名称,并且存储它的数据在virtio磁盘以持久话数据。文件系统需要解决几个挑战:

  • 文件系统需要在磁盘之上的数据结构来表达树形的目录和文件,能够记录块标识来控制每个文件的内容,记录磁盘上的哪些区域是空闲的。
  • 文件系统必须支持崩溃恢复。这是因为,如果崩溃发生了(如断电),文件系统必须在重启之后仍然能够正常地工作。风险在于崩溃可能会中断一个一连串的的更新,并且在磁盘数据结构上留下不一致性。(例如:一个块既被一个文件所使用又被标记为空闲块)
  • 不同的进程可能在同一时间操作文件系统,所以文件系统的代码必须是 coordinate 来维持 invariants.
  • 访问一个磁盘比访问内存慢几个数量级,所以文件系统对于频繁使用的块必须维护一个内存缓存。

这一章阐述了xv6的文件系统将如何应对这些挑战。

8.1 Overview

xv6文件系统实现被组织成为了7层,如图8.1。
disk层在virtio硬件上读写块数据。
buffer层缓存了磁盘块,并且同步访问他们,来确保同一时间只有一个内核进程能够修改任意一个块上存放的数据。
logging层允许更高层去包装几个块的更新到一个事务之中,并确保数据块被原子地更新以面对崩溃(例如:所有块操作要么被更新要么没有更新)。
inode层提供了个人文件,每个文件都被表述为一个inode,拥有一个独立的数字i。
directory层实现了每个文件夹作为一个特殊种类的文件,它的内容是一系列目录条目,每一个目录条目都包含了文件名和 i-number。
pathname层提供了分级的路径名,比如 /usr/rtm/xv6/fs.c,并且能够实现他们的递归查询。
file descriptor层抽象了许多unix资源(如: 管道,设备,文件等等),通过系统调用接口,简化了应用程序员的开发成本。

磁盘硬件设备通常表达磁盘上的数据通过一系列被标号的512-byte的数据块(也被称作扇区): 0扇区是第一个 512 字节,1扇区是下一个,等等。
一个操作系统在它的文件系统上使用的块的大小可能与扇区的大小存在差异,但是通常块大小是扇区大小的倍数。
xv6持有了在类型struct buf的对象中保存了它已经读入到内存块的副本。
数据存放在这样的数据结构中有时与磁盘不同步: 他可能还没有被从磁盘中读入(磁盘正忙,还没有返回扇区的内容),或者它可能被软件更新了但未写入磁盘。

文件系统必须对inode和内容块在磁盘上的存放有一个计划。为了做到这一点,xv6将磁盘划分为了几个区域,如图8.2所示。
文件系统不使用0块(它持有了引导扇区)。
1号块被称作superblock,它存放了文件系统的元数据(以块为单位的文件系统的大小,数据块数,inode数,和日志中的块数)。
2号块开始存放了日志,日志之后就是许多inode,每个block有很多inode。
紧随其后的就是bitmap块,它跟踪记录了哪些块被使用了。
剩下的块就是数据块了。每个数据块都在bitmap块中被标记了空闲状态或是否持有一个文件或目录内容。
超级块将被分区软件填充,叫做mkfs,这将构建一个最初的文件系统。

这一章后面将讨论每一层,从缓存开始。注意需要精心选择低层的抽象来使得高层更易于设计。

8.2 Buffer cache layer

缓存层有两个工作:

  1. 同步磁盘块数据的访问以确保一个块在内存中只有一个副本,并且同一时间只能有一个内核线程使用这个副本。
  2. 缓存热点块,以便于不再需要缓慢地从磁盘上再读取。这个代码在bio.c中。

缓存层导出的主要接口就是breadbwrite;前者获取了一个buf,包含了一个可以在内存中读取或修改的磁盘块,后者将修改后的缓冲区写入对应的磁盘块。内核线程必须在使用完成后,通过调用brelse释放缓冲区。
缓冲层对每个缓存块都使用了sleep-lock来确保同一时间每个buffer(或者说每个磁盘块)只有一个线程使用。bread方法返回了一个加锁的buffer,并且调用brelse可以释放该锁。

让我们回到缓存层。缓存层有一个固定数目的缓冲区来持有磁盘块,这意味着如果文件系统请求获取一个不在缓存中的块,则缓冲层必须回收当前持有的一些其他的缓存块。缓存层将会为新块回收最近最少使用的缓存块。假设最近最少使用的缓存区不大可能不久后被再次使用。

8.3 Code: Buffer cache

缓冲区缓存是一个双向链表。函数binit会在main函数中被调用(kernel/main.c:27),在静态数组buf使用NBUF个缓冲区初始化链表(kernel/bio.c:43-52)。访问这个缓冲区缓存都需要通过bcache.head来引用这个链表,而不是使用buf数组。

每个缓冲区有两个状态字段分配给它。valid字段标识了缓冲区包含了一个块的副本。disk字段标识来这个缓冲区的内容已经被提交到磁盘。该缓冲区可随时更改(例如:从磁盘写数据到data)。

bread(kernel/bio.c:93)调用了bget来根据指定的扇区获取一个缓冲区(kernel/bio.c:97)。如果这个缓冲区需要从磁盘读入,bread将会在返回缓冲区之前调用virtio_disk_rw

bget(kernel/bio.c:59)函数将扫描缓冲区列表通过传入设备和扇区号,返回相应的缓冲区(kernel/bio.c:65-73)。如果存在这么一个缓冲区,bget将为这个缓冲区获得sleep-lockbget将返回一个带锁的缓冲区。

如果给定的扇区没有被缓存,bget必须需要创建一个缓冲区,可能会复用其他已经持有不同扇区的缓冲区。这将再次扫描缓冲区列表,寻找没有被使用的缓冲区(b->refcnt = 0;引用计数为0时)。

8.15 Real world

缓冲区缓存在现实世界的操作系统中是明显要比xv6的更加复杂,但是它也是为了两个相同的目的:缓存和同步地访问磁盘。xv6的缓冲区缓存,就像是V6的一样,使用了一个简单的LRU淘汰策略;还有许多更复杂的被实现的策略,每一种策略都适用于某些情况而不适用于另一种情况。一个更加有效的LRU缓存将忽视链表,而使用一个哈希表去寻找,使用一个堆实现LRU淘汰。现代的缓冲区缓存通常被集成到了虚拟内存系统来支持内存映射的文件memory-mapped file

xv6的日志系统是效率低下的。一个提交不能和文件系统的系统调用并发地发生。即使某个块仅仅只有很少的字节被改变,系统也需要记录整个块。它执行同步的日志写入,一次一个块,每个块都可能需要获取整个磁盘轮转时间。真正的日志系统将解决这些问题。

日志并不是仅有的提供崩溃恢复的手段。早期的文件系统在重启时候使用了一种清理器来检查每个文件,目录,块,inode free list,寻找解决他们的不一致性。