UNIX传统文件系统s5fs的实现

文件系统实现—重点讲述s5fs

两种在现代UNIX 系统中常见的、用于通用目的的本地文件系统是System V 文件系统
(s5fs)和伯克利快速文件系统(FFS)。s5fs 是UNIX 最初的文件系统，System V 的所有版本和一些商业UNIX 系统都支持s5fs 。由伯克利UNIX 4.2BSD 版引进的FFS 比sSfs 性能更好，更可靠且功能更强大。它在商业界赢得了广泛的接受，融入SVR4 系统是FFS 文件系统的顶峰(SVR4 支持三种用于通用目的文件系统：s5fs，FFS 和VxFS，Veritas 的日志文件系统)。
当FFS 第一次被提出时，UNIX 文件系统框架还只能支持一种类型的文件系统。这就迫使
厂商们必须在s5fs 和FFS 之间作出选择。由Sun[ Kiel 86] 提出来的vnode/vfs 接口可以允许多种类型的文件系统共存于同一台机器上。这样，原先的文件系统实现必须要修改，以便能同vnode/vfs 集成起来。FFS 集成vnode/vfs 之后成为现在的UNIX 文件系统(ufs)。在[ Bach 86] 中对s5fs 做了详细的介绍[ Leff 89] 则对FFS 做了详细的分析。本章主要总结和比较了两种不同的实现，既是为了完整性，同时也为理解以后几章描述的高级文件系统打下基础。
在UNIX 中，文件包括各种I/O 对象，比如通过套接字和STREAMS 建立的网络连接，像管道和FIFO 之类的进程间通信机制，以及块设备和字符设备等等。vnode/vfs 体系结构将文件和文件系统抽象为一种概念，并向内核的其他部分提供模块化接口。这一结构促成了几种专用文件系统的产生。这些文件系统跟文件和I/O 关系很小，而仅仅利用该接口的抽象特征来实现特殊的功能。本章将介绍几种有趣的实现。
最后，本章描述了UNIX 的磁盘高速缓存。在早期的像SVR3 和4.3BSD 中的UNIX 版本中，
所有的文件I/O 都使用这个高速缓存。像SVR4 之类的现代版本将文件I/O 与内存管理集成在一起，通过将文件映射到内核的地址空间中来访问它们。尽管本章介绍了这种方法的一些细节，大多数的讨论将放在14 章中介绍(14 章主要讨论SVR4 中的虚存管理)。传统的磁盘高速缓存机制仍用在元数据块中。这里，元数据指的是一个文件或文件系统的属性和辅助信息。高速缓存是一种全局资源，可以被所有的文件系统所共享，而不仅仅用于某—种特定的文件系统。 我们首先讨论s5fs，并描述其在磁盘仁的排列方式和在内核中的组织。尽管FFS 和s5fs在很多重要的方面相差很大，但它们还是有一些共同点的，其基本操作的实现方式相同。我们关于FFS 的讨论将主要集中在它们的区别上面，除了特别指明，所有在9.3 节中描述的s5fs的一般算法也适用于FFS 。

1、 System V 文件系统(s5fs)
文件系统驻留在某个的逻辑盘或分区内，每个逻辑磁盘可能最多只能有一个文件系统。每一个文件系统是自包含的，有自己的根目录、子目录、文件和所有相关的数据和元数据。用户可见的文件树是由一个或多个这样的文件系统连接而成的。一个分区在逻辑上可以被视为块的线性数组。一个块的大小为512 字节乘以2 的n 次幂(不同的版本可能为512，1024 或2048 个字节)。它代表了文件空间分配和文件I/O 操作的粒度。物理块号(简称块号)是这个线性数组的索引，它唯一地标识了某个指定磁盘分区上的一个块。这个号必须由磁盘驱动程序转换成柱面号、磁道和扇区号。这种转换依赖于磁盘的物理特性(柱面和磁道、每个磁道中的扇面个数)以及分区在磁盘上的位置。

在分区的开始部分是包含有操作系统自举(加载和初始)代码的启动区(boot area)。虽然只有一个分区需要包含启动信息，但每一分区都包含一个空的启动区。紧接着启动区的是超级块，其中包含着文件系统属性和元数据。在超级块后面是i 节点表，这是i 节点的一个线性数组。每一个文件都有一个i 节点。
i 节点由i 节点号(inode number)唯一地标识，这个号跟该i 节点在i 节点表中的索引相同。每个i 节点有64 个字节。几个i 节点放在一个磁盘块中。超级块和i 节点表的起始偏移在系统的每个分区中都是不变的。因此i 节点号就可以很容易地转换为一个磁盘块号和从该块起始位置开始的偏移。i 节点表长度固定(其长度是在该分区中创建文件系统时设定)，它限制了一个分区中最多含有的文件数。在i 节点表之
后的空间是数据区。其中有文件和目录的数据块以及间接块，间接块中包含有指向文件数据
块的指针.

2、目录
s5fs 的目录是包含有文件和子目录列表的特殊文件。它包含有一些固定长度的记录，其中每个记录16 字节。前两个字节包含的内容是i 节点号，下面14 个字节是文件名。这就限制了一个磁盘分区中最多有65535 个文件(因为0 不是一个合法的i 节点号)，并且每个文件名占14 个字符的长度。如果文件名少于14 个字符，则会以空(NULL)字符填补。因为目录也是文件，所以它也有一个i 节点，只是在i 节点中有一个域将其标识为目录。目录的头两项第一个是“.”，代表了目录本身，第二个是“..”，表示父目录。如果一个表项的i 节点号为零，则表示对应的文件不存在。一个分区的根目录和它的“.”表项的i 节点号都是2 。这也是文件系统能够识别其为根目录的方法。

3、i 节点
每一个文件都有一个与之相联系的i 节点。i 节点中包含有文件的管理信息或者称为元
数据。它存储在i 节点表的磁盘空间内。当一个文件被打开，或者一个目录变为活动目录时，
内核将磁盘i 节点中的内容复制到内存中的一个也称为i 节点的一个数据结构中。但这个结
构中包含有许多磁盘i 节点中所不包含的信息。为了不产生二义性，我们将在磁盘上的数据
结构(struct dinode)称为磁盘i 节点，而将在内存中的结构(struct inode)称为内存i 节点。

域 大小(字节)说明
di_mode 2 文件类型，权限等
di_nlinks 2 对文件的硬链接数
di_uid 2 属主UID
di_gid 2 属主GID
di_size 4 字节大小
di_addr 39 块地址数组
di_gen 1 总数(每次i 节点重用于一个新文件时都递增)
di_atlme 4 上次访问的时间
di_mtime 4 上次修改的时间文件
di_ctime 4 上次改动的时间i 节点(除了di_atime 或di_mtime 的改变)
di_mode 域被分为几个位元(图9-3)，前四位指定了文件的类型，既可能是IFREG(常规
文件)，也可能是IFDIR(目录文件)，还有可能是IFBLK(块设备)，IFCHR(字符设备)等等。9
个低位分别指定厂文件所有者，用户组以及其他人对该文件的读、写、执行权限。

关于di_addr 需要详细地阐述一下。UNIX 文件在磁盘上并不是连续的。当文件长度增加时，内核从磁盘上任何方便的地方分配一个新的块。这样就可以很方便地增大或缩小文件，
同时又没有连续分配策略固有的磁盘碎片问题。很显然，这种分配策略仍然没有完全消除磁
盘碎片，因为每个文件的最后一个块可能包含有未用的空间。平均下来每个文件浪费了半个
磁盘块的空间。
这种方法要求文件系统对文件的每一个磁盘块的位置都维持一个映射。这可以用一个物
理块地址数组来实现。每个文件中的逻辑块号便是这个数组的索引。这个数组的大小依赖于
文件的大小。大文件可能要用几个磁盘块来存储该数组。然而大多数文件都很小[ Saly 81] ，
如果使用大的数组会浪费很多空间。而且如果将磁盘块数组存放在分离的块中访问文件需要
多次读操作，会降低系统性能。
UNIX 的解决方法是在i 节点中用一个很小的表存储i 节点，如果文件是够大，则使用附加的结构存储i 节点。这种方法对小文件来说效率很高，同时也能足够灵活地处理大文件。
29 个字节的di_attr 域由13 个元素表项组成，每个表项用三个字节来存放物理块号。数组元素0 到9 包含着文件的从0 到9 的数据块的i 节点号。因此，如果一个文件的数据块个数少于等于10 个，则这些数据块的地址都在i 节点表中找到。元素10 是间接块的i 节点号，即块中包含块号数组。表项11 指向一个二级间接块，在二级间接块中有其他间接块的块号。最后表项12 指向一个三级间接块，其中包含有二级间接块的i节点号。

对于有1024 个字节的块来说，这种策略使用直接索引可以寻址10 个块，使用一次间接
块可以寻址256 多块，使用二级间接块可以寻址65536 多块，使用三级间接块可以寻址16，
777，216 多块。
UNIX 文件中可以包含有空洞(holes)。如果一个用户创建了一个文件，然后将文件指针
调整到一个很大的偏移(通过调用lseek 可在打开文件对象中设置偏移指针，详见8.2.4 小
节)，再往里写入数据。这样，该偏移前的空间中就没有数据因此使形成了一个“空洞”。如果一个进程试图从文件“空洞”处读取数据，它将得到全零字节。
文件“空洞”有时候会很大，甚至整个磁盘块都是“空洞”。为这样的磁盘块分配空间，
无疑是很浪费的。解决方法是内核将di_addr 数组的相应表项(既可能是直接块，也可能是间接块)置为零。当用户试图读这样一个块时，内核将充满0 的块返回给用户。只有当有人试图往这个块里写数据时内核才分配磁盘空间。
拒绝为空洞分配空间有很重要的意义。一个进程在试图往空洞里写数据时可能意外地超
出了磁盘空间。如果复制一个包含空洞的文件，新文件在磁盘上可能会有充满零的页，而不
是预期的空洞。这是因为复制文件要先从源文件中读出内容，然后写到目的文件中。当内核
读取一个空洞时，它创建了一个充满零的页，然后该页会被原样复制到目的文件中去。这样，
一些像tar 或cpio 之类的在文件级而非原始磁盘级上操作的备份和归档工具便会出现问题。系统管理员可能要为一个文件系统作备份，可是他会发现复制的数据在相同磁盘上却没有足够的空间来恢复。

4、超级块
超级块中包含有文件系统本身的元数据。每一个文件系统都有一个超级块，它在磁盘文
件系统的开始处。当内核安装一个文件系统时读取超级块，将其放在内存中，直到该文件系
统被卸载。超级块包含有如下的信息：
·文件系统中块的大小
·i 节点表中块大小
·空闲块和空闲i 节点的数目
·空闲块表
·空闲i 节点表
因为文件系统可能有很多空闲i 节点或空闲磁盘块，因此无论是将空闲块表还是将空闲
i 节点表完全放在超级块中都是不现实的。对于i 节点，超级块维持一个局部表。当空闲i
节点表为空时，内核扫描磁盘寻找空闲i 节点(di_mode==0)，将其充实到表中。
这种方法对于空闲块表是不可能的，因为不可能通过检查一个块的内容而判别它是否空
闲。因此无论在任何时候，文件系统都必须维持一个在磁盘上的所有空闲块的完整列表。超级块包含了表的第一部分并且在表的尾部增加或删除数据。表的第一个元素指向包含该表下一部分的磁盘块等等。

有时候，磁盘块分配程序会发现超级块中的空闲块表仅包含一个元素。存储在该元素中
的值是包含空闲表下一部分的块号(图9-5 中的块a)。内核将表从那个块中复制到超级块，
这样那个块便成为空闲的了。这样的好处是存储空闲块表占用的空间直接依赖于分区上的空
闲空间大小。对于一个几乎全满的磁盘来说，根本不需要浪费任何空间去存储空闲块表。

5、s5fs 内核组织
i 节点是s5fs 中的基本的文件系统相关对象。它是与一个s5fs v 节点相关的私有数据
结构，正如前面所说，内存i 节点同磁盘i 节点是不同的。本节主要讲述内存i 节点，我们
将会看到s5fs 是如何操纵它们来实现各种文件系统操作的。

6、内存i 节点
struct inode 代表一个内存i 节点。其中包含所有磁盘i 节点的内容，另外，它还有其
他一些数据，如：
·v 节点——i 节点的i_vnode 数据域包含有文件的v 节点。
·文件所在分区的设备号
·文件的i 节点号
·用于同步和高速缓存管理的标志位
·i 节点在空闲i 节点表的指针(指向其前后节点的指针)
·i 节点在哈希队列中的指针(指向其在哈希队列中的前后节点的指针)。内核根据i 节
点的i 节点号由哈希函数求得索引值，从而在需要时可快速得到数据。
·上一次读取块的块号。

7、i 节点查找
文件系统无关层中的lookuppn()函数用于路径名解析。它调用VOP_LOOKUP 操作，每次解析一个分量。当解析到一个s5fs 目录的时候，则要调用s5lookup()函数。s5lookup 首先检查日录名查询高速缓存。如果找不到，它每次读取目录中的一个块，查找指定的文件名表项。
如果目录中包含有该文件的—个合法表项，s5lookup()得到该表项的i 节点号。接着它
调用iget()函数去定位i 节点。iget()使用哈希函数处理i 节点号，然后到相应的哈希队列
中查找i 节点。如果i 节点不在这个哈希队列中，iget()分配一个i 节点，并且从磁盘i 节点中读取数据将其初始化。当将磁盘i 节点复制到内核i 节点中去时，iget()将di_addr[ ] 中的每个元素扩展到四个字节。接着将该新i 节点加入到相应的哈希队列中。它同时也初始化v 节点，将其v_op 域指向s5vnodeops 向量，v_data 指向其本身，v_vfsp指向它所属的文件系统。最后它向s5lookup()返回一个指向i 节点的指针。s5lookup()将该指针返回给lookuppn()。
注意，iget()是s5fs 中唯一用来分配和初始化i 节点和v 节点的函数。例如，当创建一个新文件时，s5create()分配一个未使用的i 节点号(从超级块的空闲i 节点表中得到)并且调用iget()将其调入到内存中。

文件I/O系统调用read()和write()都接受一个文件描述符(open 返回的索引)、数据源或目的用户缓冲区地址，以及要传送的字节数作为参数。文件中的偏移是从与描述符相联系的打开文件对象中获得的。在I/O 操作的最后，将此次读写操作传输的字节数加到偏移量上去，这意味着下一次读写操作要从本次读写操作结束的地方开始。如果想进行随机I/O，用户必须首先调用lseek 函数将文件指针移到希望的偏移处。
文件系统无关代码利用文件描述符从描述符表中索引得到指向打开文件对象(struct file)的指针，然后验证文件是否按所需要的方式被打开。如果是，内核从file 结构中得到v 节点指针。在每次I/O 前内核调用VOP_RWLOCK 操作将对文件的访问串行化。在s5fs 中，这是通过给i 节点加上排斥性锁来实现的②。这保证了在一次系统调用中读写的数据是一致的，并且对文件的所有写是单线程的。内核接着便可以调用VOP_READ 或VOP_WRITE操作，这将分别导致对s5read()和s5write()的调用。在早期的实现中，文件I/O 例程使用了磁盘块高速缓存(block buffer cache)，它是一块专为文件系统块预留的内存区域。SVR4 把文件I/O 和虚拟内存结合了起来，它仅为元数据块使用磁盘块高速缓存。9.12 节中将描述原有的高速缓存，本节只是总结SVR4 的操作.
我们使用read 操作作为例子详细地讲述一下I/O 过程。s5read()将文件I/O 操作的起始偏移转换成逻辑块号以及块内偏移量。接着它每次读取一页数据③，方法是将块映射到内核虚地址空间并且调用uiomove()将数据复制到用户空间，uiomove()调用copyout()例程来进行实际数据传输。如果页没有在物理内存中，或者内核没有将其合理地进行地址转换，
eopyout()将产生一个页面失效。失效处理函数将标识出该页所属的文件，然后在文件v 节点上进行VOP_GETPAGE 操作。
在s5fs 中，该操作是由s5getpage()实现的。s5getpage()首先调用bmap()函数将逻辑
块号转换成磁盘上的物理块号。接着它搜索v 节点的页表(由v_page 所指的)查看该页是否已经在内存中了，如果不是，s5getpage()分配一空闲页，调用磁盘驱动程序从磁盘上读取数据。
在I/O 操作进行过程中调用进程一直处于睡眠状态。当块读取完毕之后，磁盘驱动程序
唤醒调用进程，恢复copyout()中的数据复制过程。在将数据复制到用户空间之前copyout()
首先要确认一下用户是否对其所指定的要将数据复制于其中的缓冲区有写权限。否则，用户
可能无意或有意地指定错误的地址，导致很多问题。例如，如果用户指定一内核地址，内核
将会错误地重写内核的正文或数据结构。
当所有的数据都已读完或者发生错误时s5read()返回，系统无关代码将v 节点解锁(使
用VOP_RWUNLOCK)，将file 结构中的指针偏移加上读取的字节数，然后返回用户。read 的返
回值是读取字节总数。一般来说它等于要求的字节数，除非到达了文件尾或者发生了其他的
错误。
write 系统调用过程类似，但有一些差别。write 修改过的数据并不立即写回磁盘，而是
留在内存中，根据高速缓存替换算法在以后的某一时刻写回磁盘。除此外，write 可能会增
加文件尺寸因而需要分配数据块，也有可能是间接块。最后，如果只有磁盘块的一部分数据
被修改，内核必须要从磁盘上将整个数据块读入内存，修改相关的部分，再写回磁盘。

8、i 节点的分配与回收
一个i 节点只要它的v 节点的引用计数不为零，它就会一直保持活跃，当引用计数降至
零时，文件系统无关代码便会调用VOP_INACTIVE 操作释放i 节点。在SVR2 中，空闲i 节点
被标明是无效的，因此在需要的时候还要从磁盘重新读取。这会导致效率低下，因此新的UNIX
系统将i 节点尽可能地放在高速缓存中。当i 节点变为不活跃时，内核将其放到空闲表中，
但并不使之无效。iget()函数可以在需要的时候找到它，因为它在被重用之前一直被放在某
一哈希队列中。
每一个文件系统都有一个长度固定的i 节点表，这样就限制了内核中同时活动的i 节点
数。在SVR3 中，i 节点高速缓存机制使用一种最近最少使用的替换算法。内核释放i 节点时将其放到该表的尾部，当分配i 节点时则从其头部获得。尽管这是一种很通用的启发式高速缓存替换算法，但把它用到i 节点的高速缓存中却并不是很合适。这是因为有些不活动的i节点大概要比别的不活动i 节点更有用。
如果一个文件当前正被使用，其i 节点便被钉(pinned)在i 节点表中，当文件被访问时，
它的页被放到高速缓存中。当文件变为不活动时，它的一些页可能仍在内存中。这些页可以
通过访问v 节点的页表的v_page 域而被找到。分页系统(paging system)也按照v 节点指针和页面在文件中的偏移将它们放到哈希队列中，如果内核重用i 节点(以及v 节点)，这些页
便丢掉了其标识。如果进程需要某一页，尽管该页已经在内存中，内核也必须重新到磁盘上
读取。 注意：如果一个对象既不能被释放也不能被删除，我们便说该对象被钉在内存中。有
引用计数的对象会被钉在内存中，卖二手手机号直到其最后一个引用被释放。另一个例子是，一个进程可
以用mlock 系统调用将其地址空间的一部分钉在内存中。因此，重用那些没有内存缓冲页的
i 节点比较好。当v 节点引用计数到达零后，内核调用VOP_INACTIVE 操作释放v 节点以及其私有数据(在这里便是i 节点)，当释放i 节点时，内核检查v 节点的页表。如果页表为空，
内核便将i 节点放到空闲表的头部。如果页表不为空，内核则将i 节点放到空闲表的尾部。
如果i 节点保持不活跃，分页系统便及时地将它的页释放掉。[ Bark 90] 讨论了一种新的i 节点分配和回收方法，该方法根据系统的负载调整内存i节点的数目。文件系统使用内核内存分配程序动态地分配i 节点，而不使用固定长度的i 节点表。这样，内存中的i 节点数便可以根据需要增力喊减少。系统管理员也没有必要在预先配置系统时猜测系统中该有多少个i 节点。当iget()在i 节点哈希队列中找不到某一i 节点时，它从空闲表中删除第一个节点。如果这个i 节点在内存中仍然有页面，iget()将它放回到空闲表的尾部，然后调用内核内存分配程序分配一个新的内存i 节点结构。当然，也可以检索整个空闲表找到一个在内存中没有页面的i 节点，但是我们上面描述的算法更简单有效。它唯一的缺点是有可能分配的i 节点数目比需要的多。
在一个多用户分时系统上的负载基准测试[ Gaed 82] 实验显示新算法对系统时间(内核态所占的CPU 的时间)的占有减少了12％到16％。这种方法最初是在s5fs 中实现的，但是也可用在其他的文件系统中，比如说FFS 。

9、对s5fs 的分析
s5fs 以其设计简单而著名，可是设计的简单性却给它的可靠性、性能、功能等带来很多
问题。本节我们便讨论一下这些问题，正是这些问题才导致了BSD 快速文件系统的出现。
最主要的可靠性考虑是超级块。超级块中有很多关于整个文件系统的重要信息，比如空
闲块表和空闲i 节点表等。每个文件系统仅包含超级块的—个副本，如果副本崩溃，整个文
件系统便不再可用。有几个原因导致性能的不佳。s5fs 把所有的i 节点组织到文件系统的开始位置，而用剩余的磁盘空间容纳文件数据块。访问—个文件需要首先读取i 节点，然后再读取文件数据.这种分隔导致在两次操作间有一段很长的搜索时间，这使得I/O 时间大增，i 节点是随机组织的，而没有将相关文件的i 节点分组，比如将同一个目录下的文件组织起来。这样对一个目录底下所有文件的访问操作(比如，ls -l)就会导致磁盘的随机访问。
磁盘块分配方案也不是最佳的。当文件系统第一次被创建时(使用mkfs 程序)，s5fs 以
最佳方式组织空闲块表，这样磁盘块分配就会以旋转连续的方法进行了。然而，随着文件的
创建和删除，返回空闲表的磁盘块的顺序被完全打乱。这样文件的顺序访问就会变慢，这是
因为逻辑上连续的磁盘块在物理磁盘上可能相距非常远。
磁盘块大小也是影响性能的一个因素，SVR2 的磁盘块大小512 字节，SVR3 则使用了1024字节。提高磁盘块大小之后，一次磁盘访问可以读取更多的数据，从而提高了性能。然而，这会浪费更多的磁盘空间，因为平均每个文件就要浪费半个磁盘块的空间。这就需要有更加灵活的磁盘中间分配方案。最后，该文件系统在功能上仍然有很多限制。将文件名字长度限制在14 个字符之内可能在早期UNIX 使用的环境中不会有很多麻烦，然而对一个功能强大的商用大系统来说，这和限制是不能接受的。有些程序往往通过在已有文件名上加上一些扩展来自动产生文件名，可是有了这个限制，他们不得不小心翼翼地避免使得文件名长度超过14 个字符。另外，每个文件系统只允许有65535 个i 节点也是很大的限制。
所有上述这些问题促使伯克利UNIX 开发一种新的文件系统，这就是快速文件系统
(FFS)，它首次出现于4.2BSD 中。下面一节讨论其主要特征。