13.4.5 文件系统内部结构（1）
1. 综述
如前所示，一个磁盘可以分区从而包含多个文件系统。另外，使用mount(加挂)命令可以将一个文件系统扩展到多个物理磁盘上。从逻辑上讲，UNIX中的文件系统的布局结构如图13-14所示。读者可以认为文件系统分为4个不同的逻辑部分，如图所示。
文件系统中第一部分第0块预留给引导块。对文件系统而言，这涉及到引导过程，第一个块包括引导程序。机器加电之后，硬件自动读取包含引导程序的引导块。典型地，该引导程序包含一条读取较长引导程序的指令，或是读取UNIX内核的指令。即使磁盘上有多个文件系统，但也只有一个文件系统有这个引导块。在所有其他文件系统中，这个块是空的。
第二部分或第二个块被称作超级块。它充当文件系统头。它包括与文件系统相关的信息。任一文件系统在使用之前都要加挂到根目录上。当使用mount(加挂)命令时，文件系统的超级块被读到内核的内存中。因此，当UNIX开始运行的时候，对内核而言，所有文件系统的所有超级块在缓冲区内存中都是可用的。超级块不一定就是一个块的大小。通常它要比一个块大。"超级块"是个逻辑名称。
|
| 图13-14 文件系统的逻辑布局图 |
超级块包含的字段如表13-1所示。
表13-1 超级块的内容
● 文件系统的大小 |
● 文件系统中空闲块的数量 |
● 空闲块的部分链表 |
● 空闲链表中指向下一个空闲块的指针 |
● 索引节点链表的大小 |
● 系统中空闲索引节点的数量 |
● 空闲索引节点的部分链表 |
● 空闲链表中指向下一个空闲索引节点的指针 |
● 锁定/标识符字段 |
本书通过以下内容阐述超级块中这些字段的重要性。
文件系统中可分配的块分为两部分：第3部分和第4部分，如图13-14所示。第3部分预留给索引节点。本书已经介绍过索引节点是定长记录，它存储文件的基本信息。它很像基本文件目录(Basic File Directory，BFD)条目。索引节点包含所有者、权限、定位分配给文件的数据块地址等信息。每个文件有且只有一个索引节点。然而，不是每个索引节点只对应一个文件。例如，如果两个符号名指向某个文件，也就是说如果这两个符号名之间存在链接，那么这两个符号名只有一个索引节点，即使它们的路径名不同，因此系统中有两个对应于该文件的不同符号名，该文件也只是有一个索引节点。由于UNIX把目录当作文件，所以每个目录也有一个索引节点，根目录也是如此。
文件系统有一些预留给索引节点条目的块。这就是限制该文件系统中文件、目录和子目录数量的原因。如果文件系统中有效文件/目录很少，又要新建文件，那么在文件系统的第3部分只有少量可分配的索引节点条目。如果用户要创建新的文件，文件系统中第3部分的所有其他条目都是空闲并且可分配的。用户总是会创建比较新的文件，同时删除一些老一点的文件。因此，文件系统第1部分中空闲索引节点条目的分配是一个动态过程。因此，内核必须维护文件系统第1部分中空闲索引节点条目列表，这样当用户新建文件时，内核就可以分配该列表中的条目，然后更新该列表。该列表可以很长。通常，内核会在超级块中预留一小块空间用于保存一些空闲索引节点条目。如果这个列表很小，那么在超级块中就可以保存它。如果比较大，内核就要在超级块外面存储剩余的条目。那么这些存储在超级块外剩余的条目就被称作磁盘索引节点。
在创建文件时，内核从超级块分配一个空闲索引节点。当超级块中的空闲索引节点用完之后，查询保存在超级块之外的空闲索引节点链表。从根本上讲，超级块在这种情况下充当了"缓存"。当超级块不再包含任何空闲索引节目条目时，就用磁盘索引节点中的条目更新它，同样也要对磁盘索引节点进行适当的更新。UNIX包含为新文件分配新索引节点或是如果删除文件，释放索引节点条目并将该索引节点添加到空闲列表的算法。
例如，参考图13-15可以看到本例中文件系统有26个(0～25)索引节点。该图给出了一些空闲的或是没有分配的索引节点。超级块包含空闲索引节点的部分链表，例如25、23、21、19、17、16、15和12。链表按照从高到低的顺序维护。超级块还维护指向文件系统中下一个空闲索引节点的索引或指针。该指针在图13-15中位于索引节点17处。无论何时当用户想要创建新文件时，发生以下情况：
① 内核访问超级块。如前所述，超级块从文件系统中的第二个块开始。因此，对内核而言，访问和读取该块没有任何问题。超级块包含一个指向下一个空闲索引节点的指针。现在内核可以访问该节点。
② 内核将该索引节点分配给新文件。本例中该索引节点是17。
③ 内核更新指向下一个条目的指针，也就是在分配索引节点17后，指针现在指向图13-15中的索引节点19。
④ 当指针指明超级块中没有空闲的索引节点时，内核搜索磁盘索引节点从而找到空闲的索引节点，并更新超级块中空闲索引节点链表。同样内核还要更新指向超级块中链表最初位置的指针值，然后按照前面的步骤开始处理。
|
| （点击查看大图）图13-15 空闲索引节点 |
文件系统中第4部分或可分配块的第二大部分包括可分配给不同文件的数据块，如图13-14所示。UNIX中并没有单元或簇的概念。按照需求，系统每次只能为文件分配一个块。分配给文件的块不必是连续的。因此，UNIX要保存分配给一个文件所有数据块的一个索引。在该文件的索引节点中可以有多个级别的索引以及数据块/索引的地址。因此，在访问文件的索引节点之后，系统就可以遍历文件的所有数据块。稍后在研究索引节点的结构中详细介绍这部分内容。
任何时候，某些数据块分配给某些文件，而其余的数据块空闲。UNIX有一个维护空闲数据块链表的有趣方式。在超级块自身中维护一个空闲数据块的部分链表。超级块还要维护一个保存在超级块中空闲数据块部分链表的指针。显然，超级块不能包含空闲数据块的全部链表。空闲数据块链表的其他条目分开保存。UNIX保存一个从超级块指向其他包含其余空闲数据块链表的块的指针。这很像保存空闲索引节点条目的方式。
13.4.5 文件系统内部结构（2）
2. 空闲块的分配
诚如前面介绍的，超级块保存一个空闲块的不完全链表。超级块要比一个数据块大。假定超级块自身包括一个1024字节的块，也就是包括256个4字节或32位的条目，每个条目对应磁盘上一个空闲块。显然，这是空闲块的不完全链表。图13-16表明超级块中编号为3、7、10、15、…、389的块空闲。该图还给出了指向最右端位置的"下一个空闲块"的指针，该指针指向编号为3的块。这表示当文件请求分配另一个块时，就可以将编号为3的块分配给它。
该链表被称作超级块缓存。如果文件请求块，内核就会从右向左检查超级块缓存以分配块。算法分配因此会很快。这个阶段，内核没必要遍历任何链表或指针。
|
| （点击查看大图）图13-16 空闲块的分配 |
除了超级块中维护的空闲数据块链表之外，同样还要在超级块之外的磁盘上维护一些包含空闲块号的其他块。在超级块和这些块之间有链接，如图所示，这里加以简要介绍。由于编号为3、7、10等的块已经按照该顺序分配给不同的文件，所以内核还要更新超级块中指向"下一个空闲块"的指针。当分配超级块中最后一个块(也就是图13-16中编号为389的块)时，情况就不一样了。原因在于：对超级块中这个最后空闲块的分配约定完全不同。这个最后的空闲块实际上不是一个空闲块，实际上它包含接下来256个空闲块对应的256个条目。因此，当内核存取最后这个条目时，它会执行以下步骤：
① 访问并读取编号为389的块。
② 将块389回写到超级块中空闲块链表上。现在，超级块缓冲中包括编号401、410…到797的空闲块。
③ 初始化超级块中指向编号为401块的(也就是最右端的块)的"下一个空闲块"指针。
④ 将编号为389的块当作空闲块使用，将其分配给请求的文件。
⑤ 使用块389之后，内核对所有顺序请求的分配按照块号401、410…这个顺序进行，直到分配最后一个块(也就是块号为797的块)为止，分配结束。每分配一个块之后，内核更新超级块中指向"下一个空闲块"的指针。
⑥ 重复上述过程，也就是读取编号为797的块，将其存储在内存中，先分配编号为797的块，然后将编号为797的块的内容写回到超级块上。
⑦ 这会持续到所有块分配完为止。
如果文件删除一些记录，那么针对新添加的空闲块设计算法就很有意思。如果超级块可以在"空闲块列表"中放置该空闲块的块号，那么内核只要更新超级块就可以了。如果因为这个新条目的原因，超级块已经满了，那么就要将这个块的块号作为最后一个(也就是最左边的一个)维护，而且新空闲块的条目要放置在这个新分配的块中(类似于图13-16中的块号389)。该过程可以在不同层次进行。
人们比较关注该方法和用于空闲块分配的位映射法的比照情况。
15MB的磁盘需要60个大小为1KB的块，保存空闲块号。15MB的磁盘有15×1024=15 360个大小为1KB的块，因此，如果整个磁盘都没有分配，那么列表中就会有15 360个条目。大小为1KB的块可以保存256个条目。因此，为了保存空闲块号，就要有60个块，因为60×256=15 360。然而，位映射法占用15 360个位或1920字节，它比2个块还要少。相比UNIX使用的前一种方法，它占用的磁盘空间不到前者的1/30。UNIX使用该方法的优点是什么呢？主要优点就是：内核给文件分配块的速度更快。同样地，由于分配的磁盘块越来越多以及磁盘变满(也就是说，剩余的空闲磁盘块很少)，这两种方法的差别也就很小了。
现在研究索引节点的结构，以及内核为文件分配空闲数据块的方法。
3. 索引节点的结构
索引节点包括以下信息：
① 所有者的用户id(uid)
② 所有者的组id (gid)
③ 保护位：诚如所知，UNIX将所有用户分成3类：所有者(Owner)、组(Group)和其他的(Others)。每一类要么有，要么没有读(r)、写(w)和执行(x)权限。因此，内核需要三个位为每类用户指明权限。因此在每个文件的索引节点中总共要用9位。
④ 文件类型：指明文件是普通文件、目录、特殊文件还是FIFO文件。
⑤ 文件访问时间：指明文件创建时间、最后一次使用该文件的时间以及最后一次改动该文件的时间。
⑥ 该文件的链接数：指明文件已知的符号名个数。只有该数为0的时候，内核才会物理删除文件(释放所有数据块以及分配给该文件的索引节点)。显然，只有在所有用户从自己目录中删除该文件时才会出现这种情况。
⑦ 文件大小
⑧ 通过多个不同索引级别分配给该文件所有块的地址。图13-17给出了它们的结构。
|
| （点击查看大图）图13-17 索引节点结构 |
UNIX有一个在索引节点中维护数据块地址的特殊方式，这其中还有一个原因：UNIX是在研发和教育环境中而不是商业环境中设计出来的。因此，它面向的环境已经不同。在这样的环境中，成百上千个学生创建小文件，然后忘了删除这些文件，通常一个人会有大量的小文件，而在商业环境中只有一些比较大的文件。这种情况如图13-18所示。
因此，UNIX想要为使用小文件的用户提供快速处理功能，与此同时对于那些使用大文件的用户也不会造成很大的不公平。UNIX采用的一种实现方式就是减少对小文件的地址转换(Address Translation，AT)时间。其实现如下(参见图13-17)。
索引节点预留一个保存13个块编号的位置。假定1024字节的磁盘块以及需要用4个字节(或32位)表示块号，那么系统要为每个索引节点预留13×4＝52个字节。除了这13个块号之外，前10个是实际分配给文件的数据块的编号。因此，如果文件大小是1024×10＝10 240个字节或者更少，那么分配给该文件的所有块号可以放在索引节点中。因此，内核可以在访问索引节点的时候立刻得到这些块号。编号从0到9的这10个块被当作是图13-16中的直接块。
13.4.5 文件系统内部结构（3）
当创建新文件时，最初所有10个条目都是空的。当向这些条目写某些内容并因此需要使用块时，如前所述，内核检查空闲的数据块链表，选择分配一个空闲数据块，并从空闲数据块列表中删除这个块的编号，在索引节点中插入这个块号。这个过程持续到文件中的前10个块分配完为止。分配块的时候，内核还要更新索引节点中的"文件大小"这个字段。通过执行一个简单的文件大小/块大小的算术操作，内核可以通过这个字段查找索引节点中的新条目，并在这个条目中插入新分配的块号。例如，如果文件大小是2048个字节，内核可以轻松地计算出，这也就是2048/1024＝2个块，也就是10个块中只有两个块被填满。因此，下来就是第三个条目。
|
| 图13-18 针对文件的典型环境 |
如果文件大小超过10个块，会出现什么问题呢？如果发生这种情况，内核会从可用的空闲块中分配数据块，并将该块当作索引块。索引节点的第11个条目提供了该索引块的块号。如图13-17所示，索引块包含地址或者指针。这个索引块也有1024个字节，因此，它可以保存多于256个数据块号的256个条目(1024/4=256)。现在内核遍历空闲块链表，并将其中一个分配给该文件。现在内核将这个实际数据块的块号作为索引块中的第一个条目。随着文件的扩大，它重复这个获取新空闲数据块的过程，分配该数据块，并将该数据块的块号写到索引块中第2个条目，等等。内核通过前面介绍的使用文件大小的简单算术，计算出索引块中接下来要使用的条目。这个索引块被称作单级间接索引块。这是因为索引块直接指向数据块。如果已经分配10+256=266个块，也就是说，如果文件超过266×1024个字节，也就是266KB或0.266MB，那么内核就要使用双级间接索引块，如图13-17所示。
在两级索引中，索引节点中的第12个条目指向两个间接索引块。这个索引块也有256个条目，但不是直接指向256个数据块(像在单级间接索引中)，而是指向间接寻址第二级的256个其他索引块。这里知道，每个索引块可以有256个块号。这就给UNIX提供了寻址10 + 256 + (256×256) = 65 802块或65.8 MB的能力。由此可以看到：内核可以通过三级间接地址，通过多极扩展可以寻址的全部块数是10 + 2561 + 2562 + 2563，这超过16GB的寻址空间。然而，如果索引节点中文件大小只有32位，那么由于这个原因，文件大小就局限在232 或4GB。
文件大小在地址转换中起着重要的作用。根据文件大小，内核知道是否要对索引节点自身中的块号(直接的)或是间接的特定级别的索引进行定位。
4. 地址转换
UNIX将文件当作字节流。假定应用程序提交一个写600字节新记录的系统调用。为了执行该系统调用，内核要经历以下步骤：
① 访问该文件的索引节点，并由文件大小确定内核要写入的逻辑字节数。假定提交写系统调用时，文件大小是20 001字节。因此，逻辑字节0到20000已经被写到这个文件。此时，内核确定要在逻辑字节20001到20600处写入600个字节。
② 通过块大小(本例中块大小是1024字节)的分割，将逻辑字节数转换成逻辑块号和偏移量。因此，可以确定逻辑字节20001在逻辑块19中的偏移量是545，而逻辑字节20600在逻辑块20中的偏移量是120。想象一下，文件按照一系列块逐个摆放，就像是从0开始连续分配。然后，文件大小除以块大小得到的商数就是逻辑块号(Logical Block Number，LBN)，而余数就是LBN在该块中从字节0开始的偏移量。例如，相对字节数。(Relative Byte Number，RBN)0就说明是LBN等于0的第0个字节。类似地，RBN等于1024对应于LBN等于1的第0个字节。LBN等于0，就是占用RBN的0到1023，LBN等于1，就是占用RBN的1024到2047，等等。
③ 将逻辑块号转换成物理块号。例如，逻辑块号19会在单级间接索引中找到。逻辑块0到9就在索引节点自身。逻辑块10就是单级间接索引中的条目0。因此，逻辑块19就是单级间接级别索引中的条目9。同样的，逻辑块20就是同一个索引中的条目10。图13-19 图形化地给出了例子中的LBN。
④ 在计算之后，访问索引节点中单级间接条目，并通过跟踪该指针从单级间接级别访问索引块。
⑤ 访问该索引中条目编号9。它向内核提供磁盘上的物理块号。假定这个块号是501(这个块已经分配给该文件，因为由文件大小可知，已经写入字节0到544)。
⑥ 将物理块号501转换成物理地址：柱面、磁道和扇区。
⑦ 通过设备驱动程序将块从磁盘读入内存。可以知道字节号0~544构成有效数据，而字节545~1023(479个字节)在物理块501中是空的。因此，内核决定将600个字节长的记录中的前479个字节写到块的545~1023这479个字节中，并回写该块。
⑧ 现在，要将剩下的121个字节(600-479=121)写到编号为20 的逻辑块的0~120字节中。这里还没有将这个块号分配给该文件。现在内核检查空闲块链表，并为该文件分配空闲块。此时，更新单级间接级别索引中的条目编号10，指明这个新分配块的块号。假定该物理块号是701。
⑨ 内核再次查找新分配块的物理地址(柱面、磁道、扇区)。
⑩ 内核现在向设备驱动程序提交指令，从而从内存中得到记录剩下的121个字节(通过指明内存地址)，并将它们写到磁盘由编号为701的物理块指定的位置。在该物理块中，还空闲903个字节(1024－121)可用于后面的写操作。
内核现在更新文件大小。
|
| （点击查看大图）图13-19 地址转换中的逻辑块号(LBN) |
如果文件大小超过65 802字节，内核就要通过双级间接索引块进行访问，但采用这种方式读取记录与单级索引索引的方式很相似。
13.4.5 文件系统内部结构（4）
5. UNIX 目录
UNIX目录类似于前面介绍的符号文件目录(SFD)。如前所示，UNIX中的索引节点扮演了和基本文件目录(BFD)条目的相同角色。UNIX目录包括目录下的文件以及子目录的条目。每个条目包括一个符号文件或子目录名以及对应的索引节点号，如图13-6所示。每个条目16个字节长：14个字节用于文件名，2个字节用于索引节点号(这与具体的实现相关)。
6. 路径名解析
本书在符号文件目录(SFD)和基本文件目录(BFD)一节中已经讨论过解析路径名的方法。现在以UNIX的另一个例子重新诠释这个概念。想象一下路径"../x/y"从当前目录开始，一直到父目录，也就是路径名中的".."，到父目录中的另一个目录"x"，从而最终到达目录"x"中名字为"y"的文件。
UNIX执行下面的步骤遍历该路径(参考图13-20)。图中的步骤(i~xi)对应下面的步骤(1)到(11)。
① 内核访问u区(u区类似于该进程的PCB)，其中存储了当前目录。可以将其作为绝对路径名或当前目录的索引节点存储。无论哪一种情况，如果没有明确指明，那么可以通过相同的算法得到当前目录的索引节点号，下述从根目录(/)开始。
② 现在内核访问当前目录的索引节点。
③ 索引节点把分配给当前目录的"文件"的磁盘块链接在一起。索引节点将它们作为直接块(0到9)和不同级别索引的间接块列出。内核检查它们，并实际读取内存中的当前目录文件。
④ 目录有一个预先定义的格式，例如，本例中它有16个字节的条目。内核现在搜索作为目录中符号名的".."条目。SFD的格式参见图13-6。内核解析相对路径名并一直提取到下一个"/"内容为止。路径名是"../x/y"。因此，一开始，这个解析过程产生".."，".."指明父目录。每个目录有一个"."条目，表明当前目录，以及另一个".."条目，它表示父目录(参见图13-6)。
⑤ 内核使用该条目为".."从当前目录中提取出父目录的索引节点号。
⑥ 内核访问父目录的索引节点，并通过再次检索该文件的直接/间接数据块读取有关该父目录的实际内容。
⑦ 现在内核在父目录中搜索符号文件名"x"。这是内核解析相对路径名到下一个"/"后得到的符号名。
⑧ 现在，内核从父目录中提取目录"x"的索引节点，并如前一样读取该目录的内容。
⑨ 现在，内核在目录"x"中搜索符号文件名"y"。这种情况下，这是内核在解析到下一个"/"或相对路径名的结尾处得到的名称。
⑩ 对"y"提取索引节点号，并取回该索引节点。
现在，可以读取文件"y"或是对其进行其他任意操作。可以对数据块在索引节点中使用直接地址和间接地址从而完成该工作。
|
| 图13-20 路径名解析步骤 |
7. UNIX中的ACL
诚如所知，系统管理员为每个用户分配一个用户名，假定该用户在登录系统时输入这个用户名。系统在创建用户的时候，在内部为用户名分配唯一一个被称作用户id(uid)的数字。这些uid及其用户名也由系统存储在/etc/passwd文件中以备将来引用。
除了用户id(uid)之外，UNIX还有一个组id(gid)的概念。典型的，如果项目需要15个程序员，那么所有的15个程序员有不同的uid，但他们可以有相同的gid。一个用户可以只属于一个组。这两者(uid，gid)的组合构成域。对每个用户而言，这个(uid，gid)保存在密码文件/etc/passwd的记录中。本书已经介绍过索引节点还为每个文件保存了uid和gid，其中uid是文件所有者的用户id而gid是文件所有者的组id(参见13.4.5(3)节)。所有者就是创建文件的人。通过为用户匹配uid和gid(在/etc/passwd文件中指明)以及对应文件的内容(在其索引节点中已给出)，UNIX可以确定该用户可以对该文件采取什么样的操作(读/写/执行)。
如果UNIX采用AOS/VS设置访问权限的方式(也就是为每个用户明确指明访问权限)，那么ACL会很长，而且会占用大量的磁盘空间，还要耗费很长的时间进行验证。所以，UNIX进行了一种妥协。它将每个文件的用户分成广泛的三类：第一类被称作所有者(Owner)--创建文件的人。因此，所有者的uid定义了这个类。第二类就是组(Group)--由所有者的gid定义。第三类是其他的(Others)--它不属于前两类。除了所有者之外，所有用户要么属于"组"类，要么属于"其他"类。
因此，UNIX只针对这三类用户为每个文件定义访问权限。UNIX只提供三类访问权限--读(r)、写(w)和执行(x)。它为这三种存取权限预留3个位。0表示拒绝此权限，1表示授权。因此，如果给定文件的访问权限是101，那么意味着用户可以读该文件，但不能向该文件写内容，同时可以执行该文件。假定它是一个包含编译过的、二进制可执行程序的文件。这就是为什么有时候将其写成r-x的原因，虽然在ACL中内部是按照101的形式保存该信息的。类似的，如果组对文件有001或--x的访问权限，那么就意味着组中的任何人都只能执行该文件，但没有人可以执行读/写操作。因此，在索引节点中有9个位(每一类有3位)，它们完整地定义了对该文件的访问权限。
现在，存取控制验证按照以下步骤进行：
① 如上所述，系统管理员为用户分配uid和gid。uid和gid存储在/etc/passwd文件中。这里分别称其为uid-u和gid-u，以备将来引用。
② 任何时候，当用户登录系统时，他键入自己的用户名和密码。如前所示，系统查询/etc/passwd文件之后检索该用户的uid。UNIX (本例中的登录过程)通过存储在/etc/passwd文件中的内容验证这些信息。只有在确认信息匹配之后，用户才被授权访问该系统。此时，用户可以向shell提交命令。当该用户登录并启动任一进程时，就会将该用户的uid-u和gid-u从/etc/passwd文件中复制到该进程的u区。如果该进程创建子进程，那么这个子进程同样也有一个继承父进程的包括相同uid-u和gid-u的u区。
③ 现在假定用户提交命令执行一个名为PAY.COB的COBOL程序。PAY.COB是UNIX目录系统中的一个文件，它包括可执行程序也就是该程序的二进制代码。还假定在编译程序创建该文件之后，系统分析员确定可以执行该程序的人员，并且系统管理员会据此使用只可以执行的优先命令设定该文件的存取控制位。在接收到来自用户执行该程序的命令后，内核通过前面介绍过的符号文件目录的链表以及用于解析文件路径名的索引节点访问PAY.COB的索引节点。
在最终得到PAY.COB的索引节点之后，内核将它保存在PAY.COB索引节点中的uid和gid保存起来。这里称其为uid-i和gid-i以备将来引用。这些就是该文件所有者的uid和gid。现在，将进程u区可执行进程中的uid和gid(uid-u、gid-u)以及进程想要访问的文件索引节点中的uid和gid(uid-i、gid-i)进行匹配。该工作通过以下步骤完成。
④ 内核现在执行以下算法，确定用户类别(假定用户不是超级用户)。
|
⑤ 除了索引节点中为这三个类别存储的9个位之外，现在内核可以访问到步骤(4)中对应该类别的3个位。
⑥ 现在内核检查该类的最后一个(x)位，确保当前用户可以执行该程序。如果可以执行，就让其继续，否则提示错误消息拒绝用户的执行。
⑦ 当运行PAY.COB程序时，形成新的u区，并将父进程的uid和gid复制到该u区。如果PAY.COB调用另一个名为TAX.COB的子程序，通常，内核创建包含另一个u区的新的子进程。再次的，将父进程的u区中的uid-u和gid-u复制给子进程的u区。此时，如果TAX.COB提交打开另一个文件的指令(系统调用)，也就是读EMP.DAT文件，存取控制验证可以按照以下步骤继续：
内核根据层次结构目录可以解析路径名，从而到达包含EMP.DAT文件的目录，这在路径名解析中已经做过介绍。
内核搜索目录中的EMP.DAT文件，并获取该文件的索引节点号。
内核读取EMP.DAT的索引节点，并且将uid和gid存为uid-i和gid-i。
将其和存储在TAX.COB的u区中的uid-u和gid-u比较，内核可以得到对应该文件的用户类别(参见前面例子中的步骤(4))。
内核将查看索引节点中对应该类别的3个访问权限位。
最终，内核根据用户类别，通过检查存取控制位的第一位(r)确保用户对该文件可以进行"读"操作，从而允许或禁止用户请求的操作。
13.4.6 文件系统运行时的数据结构
为了快速访问起见，内核在内存中保存了某些数据结构。例如，如前所示，内核总是将所有文件系统的超级块保存在内存中。这主要是因为超级块保存空闲索引节点条目和空闲数据块的部分链表。因此，当操作系统创建新文件并分配新索引节点时，或是将一些新的数据块分配给现有文件时，它会先查询内存中的超级块。显然，这样速度就比较快，因为它节省了磁盘存取时间。
内核除了在内存中保存超级块之外，还保存以下数据结构：
用户文件描述符表(UFDT)
文件表(FT)
索引节点表(IT)
图13-21描述了它们之间的关系。
|
| 图13-21 文件系统运行时的数据结构 |
下面介绍这些数据结构。
1. 用户文件描述符表(UFDT)
UFDT是进程u区的组成部分。u区很像分配给每个进程的进程控制块(PCB)。这个UFDT有很多编号为0、1、2等的条目或插槽。这些编号被称作文件描述符(file discriptor，fd)。当打开文件时，"open"(打开)系统调用在UFDT中生成一个新的条目，并返回该值。从根本上讲，这个来自UFDT的条目就是指向文件表(FT)中条目的指针。文件打开时已经创建fd，因此对所有后续操作只要指明fd即可。fd被当作是存取UFDT中正确条目的索引，因此内核能够遍历相关的FT条目以及索引节点表(IT)条目，如图13-21所示。
如果用两种方式打开相同的文件，那么在UFDT中就有两个不同的条目，它们有两个指向FT中对应条目的描述符，这可以用图13-21中的进程A描述。注意：索引节点等于11的文件实际上是由两个进程打开的：进程A用两种方式(读、写)打开该文件，这两个模式对应于进程A的UFDT的fd分别等于4和5；而进程B打开它进行读/写，它对应进程B的UFDT的fd等于5。
因此，这些数据结构提供了共享功能。对于要由多个进程用多种方式共享使用的文件而言，在索引节点表(IT)中只有一个条目，但UFDT和FT中有多个指向该条目的条目。
记住：内核为标准输入、标准输出以及标准错误分别预留了前三个条目，它们的fd分别等于0、1、2。对每个进程都是如此，因此这三个条目出现在每个UFDT中。UFDT对进程控制很重要。当进程终止时，内核访问该进程的UFDT，逐个条目检查该UFDT，遍历FT中相关的条目，并删除这些条目。然后遍历对应的IT条目，递减"计数"字段。如果现在"计数"字段变成0，那么就从IT中删除该条目。现在，内核释放该文件占用的所有运行时I/O缓冲区和其他数据结构。即使进程执行的程序没有明确关闭文件，也要完成这样的工作。
2. 文件表(FT)
文件表(FT)是一个表格，它包含对应每个文件的一个条目以及每个进程打开文件的模式。例如，以索引节点号为11的同一个文件为例。图13-21给出了进程A同时以读模式和写模式打开该文件，而且进程B也以读/写模式打开该文件。该图说明所有指向索引节点表(IT)的核心条目(in-core entry)的三个不同的FT。
对特定文件而言，FT的主要功能就是维护特定模式下的文件偏移量。例如，该图给出了由相同进程(进程A)打开的同一个文件(其索引节点号等于11)在读模式下文件偏移量是1100，在写模式下是2000。这表明如果进程A提交"读"这个系统调用，读取这个文件中的500个字节(也就是读取其相对字节数(RBN)1100～1599)，对于读操作而言，进程A的UFDT的fd等于4的FT中文件偏移量被更新为1600。如果同一个程序还提交了写300个字节的系统调用，它们就会将数据写到相对字节数2000～2299这个位置。在完成写操作后，进程A的UFDT的fd等于5的FT中文件偏移量被更新为2300。无论哪种情况，如前所述，内核完成相对字节数到逻辑块号，再到物理块号以及到最终物理地址的转换工作。
要点就是：内核难道不能在UFDT中维护这些与模式相关的文件偏移量值，从而去掉FT呢？读者会注意到：UFDT和FT之间存在着严格的一一对应关系。那么为什么FT条目不能合并到UFDT条目中呢？不这样做的主要原因是由于两个系统调用(也就是"fork"和"dup")。在fork系统调用中，进程创建子进程，并复制所有基本的数据结构，如u区。然而，在父进程和子进程之间还存在共享的一项内容。这两个进程共享使用所有打开的文件。因此，在fork系统调用后，有两个指向同一个FT条目的UFDT。此时，这两个FT条目中的计数字段就是2。shell就经常使用这个特性。
当shell运行分支程序时，它会生成新进程，然后等待新进程的终止。与此同时，新进程从标准输入读取内容，并将其写到标准输出中。shell进程和子进程共享指向标准输入和输出的读/写指针，这使得读/写指针在shell再次获取控制的时候可以准确定位。
正是由于这个原因，FT和UFDT才没有合并成一个表。
3. 索引节点表(IT)
内核预留一部分内存，用于保存索引节点表(IT)中的条目。无论何时，进程打开文件时，它在磁盘上的索引节点以及几个其他字段就会被复制到内存中。如图所示，任何时候，都有从FT指向IT的指针。如果FT中对应同一个文件有三个条目，那么所有这三个都会指向IT中唯一的一个条目。IT条目中的计数就是3。注意：这个计数是磁盘上索引节点的附加内容字段。它记录了运行时指向文件的指针数，也就是它表示运行时按照相同或不同模式打开同一个文件的进程数。
当进程关闭该文件或终止运行时，就删除由FT指向IT的那些指针，同时按照相应的数目递减IT中的计数字段。当该字段变成0的时候，IT中的索引节点条目就会被删除。因此，只有进程运行时才会用到该字段，不能将其和磁盘索引节点中的"文件链接数"或"访问计数"混淆。访问计数字段指的是不同目录中两个以上符号名调用同一个文件。即使没有进程打开它，该字段也会继续存在。
任何时候，IT中都有一些空闲条目。这些空闲条目链接在链表中，这样在打开新文件的时候，内核就可以检索出空闲条目，然后从空闲链表中删除该条目，并将它分配给新文件。当不再使用索引节点时，内核将该条目返回给IT中空闲索引节点链表。
IT的内存条目包括以下其他字段(除了磁盘上的索引节点)，如表13-2所示。
表13-2 位于磁盘索引节点以外的内存IT中的附加字段
|
● 包含该文件的文件系统的逻辑设备号 ● 索引节点号：在磁盘上索引节点中索引节点 ● 号是不必要的，因为索引节点可以直接通过 ● 索引节点区域的条目的相对量访问。索引节点 ● 号在IT条目中是必需的，因为所有的索引节 ● 点可能并没有复制到内存中 ● 指针：指向IT中其他inode条目的指针 ● 计数：如前所述 ● IT条目状态(锁定等) |
包含该文件的文件系统的逻辑设备号
索引节点号：在磁盘上索引节点中索引节点号是不必要的，因为索引节点可以直接通过索引节点区域的条目的相对量访问。索引节点号在IT条目中是必需的，因为所有的索引节点可能并没有复制到内存中
指针：指向IT中其他inode条目的指针
计数：如前所述
IT条目状态(锁定等)
研究完文件系统的全部运行数据结构后，现在介绍系统中的一些系统调用，从而帮助读者了解整个过程。