【读书笔记unix操作系统设计】文件的内部表示
文章目录
读完本文可以了解到什么
本章从索引节点和磁盘块的角度讲述了文件创建删除、读取时所采取的索引节点和磁盘块的操作，主要涉及索引节点的分配与释放（第五部分）（用于创建删除文件）、磁盘块的分配与释放（第六部分）（用于创建删除文件）、内存中索引节点的分配与释放（第一部分）（用于读取文件）。
文件系统概述
一个文件系统由一个逻辑块序列组成，每个块包含512、1024、2048个字节或512个字节的任意倍数，这依赖于系统的实现。如下图所示：
- 引导块： 文件系统的开头，可以含有被读入机器中起引导作用或初启操作系统作用的引导代码。虽然为了引导系统只需要一个引导块，但每个文件系统都有一个引导块（虽然可能是空的）。
- 超级快： 描述文件系统的状态----如文件系统多大，能存储多少文件，文件系统何处能找到空闲的空间以及其他信息。
- 索引节点表： 一张装有索引节点的表（存放在磁盘）。内核通过索引来访问索引节点表中的索引节点。有一个索引节点是文件系统的根索引节点，在执行了系统调用mount后，该文件系统的目录结构就可以从这个根索引节点进行读取了。对索引节点表操作时会被加入内存（不是全部加入内存，是部分加入）（内存中索引节点表和磁盘上数据结构有些差别）。
- 数据块： 存储数据。
一个文件的内部由一个索引节点给出，索引节点记录了文件数据在磁盘上的布局，并且包含文件所有者、创建时期等等信息。每个文件都有一个索引节点，但是它可以有几个名字，这几个名字都映射到该索引节点上（这一个文件）。每个名字都被称为一个联结。
上面描述了磁盘中文件的结构，下面简单介绍下内核中和文件系统相关的数据结构：
内核中包含另外两个数据结构（除了磁盘上的inode）：文件表和用户文件描述符表
- 文件表：是一个全局核心表，文件表中存着文件中的字节偏移量（下一次读写位置），对打开进程的所允许的存取权限。
- 用户文件描述符表：每个进程有一张，标识这一个进程的所有打开文件。
综上，文件系统主要通过三张表维护，索引节点表、用户文件描述符表、文件表。下图展示了三者的关系：
一、索引节点
1.1索引节点的定义
索引节点以静态形式存放在磁盘上，内核把他们读入内存索引节点表中以便操作它们。故在磁盘和内存中都有索引节点存在，但存储内容略有不同。
磁盘索引节点数据结构如下：
内存索引节点数据结构如下：
其中，内存索引节点状态、该文件的文件系统逻辑设备号、索引节点号、指向其他内存索引节点的指针、引用数均为内存索引节点独有的。
- 内存索引节点状态：是否上锁、索引结点是否更改、对应文件数据是否更改、是否有进程在等待、是否该文件为安装点（第5章详解）
- 索引节点号：文件在磁盘索引结点块中索引结点的数组下标
- 指向其他内存索引节点的指针：在空闲表和散列队列中的指针
- 引用计数：该文件的活跃实例数目（如几个进程打开了文件）
1.2索引节点的存取与释放
在介绍完文件系统中索引节点的数据结构后，我们将来探讨内核是如何获取索引节点并释放索引节点的。
1.2.1索引节点的存取
在获取将要读取的文件的索引节点号后（如何获取是上层服务完成），利用算法iget在内存中分配一个存储空间存放磁盘索引节点的拷贝（当然还有一些其他信息，正如1.1所述）。可以将内存中的索引节点理解为磁盘索引节点的高速缓冲，其分配算法和上一章中磁盘高速缓冲分配算法getblk几乎相同：内核把设备号和索引节点号散列映射到一个散列队列上，并搜索散列队列以找到该索引节点。如果找到索引节点但被上锁，那么阻塞等待唤醒。如果能找到索引节点且未上锁，则在空闲表中移除该节点，并且索引节点引用计数增加1。如果找不到索引节点，那么就会从空闲表分配一个索引节点（空闲表空会报错），并对其上锁。随后把磁盘索引节点的数据拷贝到内存索引节点中。
下面是分配索引节点iget算法的具体描述：
**现在考虑一个问题，在找不到索引节点时，需要将磁盘索引节点数据拷贝到高速缓存中。内核知道逻辑设备号和索引节点号，该如何找到包含该索引节点的逻辑磁盘块进行拷贝呢？**因为内核是已知索引节点大小的，所以只需获取索引节点起始地址（即在哪个磁盘块的第几个字节偏移量）即可，下面给出计算公式（索引节点从1开始编号）：
1.2.2索引节点的释放
在考虑了索引节点存放问题后，我们来考虑索引节点的释放问题。索引节点释放利用iput算法，描述如下：
当一个进程释放索引节点时，内存索引节点计数减1。若果其访问计数减为0，这说明当前没有进程打开该文件。需要将索引节点放到空闲表中（为了在再次需要时可以直接获取），并将其内容写入磁盘索引节点。如果索引节点的联结计数值为0，则可以删除磁盘文件（后面会讲free算法），释放磁盘索引节点（后面会讲ifree算法）。
二、索引节点如何记录文件存储区域
若在索引节点中采用记录起始地址和偏移量的方式（此时采取连续分配策略），则会造成存储上的困扰（文件增长复杂）。故采用在索引节点中依次记录存放文件的磁盘块号（此时采取不连续分配策略）。但每个索引节点只能指向有限个数据块，如果这些数据块不够存储怎么办？那么采用一次间接、二次间接甚至三次间接索引完成。（此处是磁盘固定一些位置存放直接索引、一些位置存放间接索引。还是根据索引节点的一些信息获得此节点指向的数据块是直接索引或间接索引未知，是以后需要查阅的问题）
根据偏移量如何获取数据所在磁盘块也是一个需要计算的问题，此处就不详细说明了。
三、文件目录
文件目录也是文件，只是它的数据是一些列目录表项，每个目录表项由一个索引节点号和一个包含在这个目录中的文件名组成。文件目录中含有两个固定的表项：. 和 . . 。前者代表当前目录，后者代表上级目录。
四、路径名到索引节点的转换
最初对一个文件的存取是通过文件名（即路径名全名或相对路径名）来进行操作的，然而内核在内部是通过索引节点而不是路径名进行文件操作的，所以如何将一个完整的文件路径转换成索引节点号是需要考虑的问题。
每个进程都与一个当前目录所联系。u区（每个进程都被分配一个u区----userblock）包含一个指向当前目录索引节点的指针。系统中第一个进程–0号进程的当前目录是根目录。其他每个进程的当前目录都是fork时父进程的当前目录。可以通过系统调用chdir来改变当前目录。所有路径名搜索都是从当前目录或根目录（当以/开始的目录）开始，无论哪种情况下，内核都能轻易找到开始搜索的目录的索引节点。当前目录存储在u区，系统根索引节点被存储在一个全局变量中。
下面一张图是namei算法描述，由于较为简单，故不详细阐述：
五、为新文件分配和释放索引节点
前面的探讨都是基于索引节点已经绑定到一个文件上了，并且已经分配了磁盘块以容纳文件数据。下面将探讨内核怎样分配和释放索引节点和磁盘块。
5.1分配索引节点
内核使用iget算法为一个已知的磁盘索引节点号在内存中分配索引节点。在算法namei中，内核把路径名映射为索引节点号。而本次要阐述的ialloc算法则把一个磁盘索引节点分配给一个新建立的文件。
正如概述中所说，文件系统中包含一个索引节点（线性）表，这个表存放在磁盘中。当一个进程需要一个新的索引节点时，理论上说，只需要内核搜索磁盘上索引节点表即可，但是这样搜索花费的代价太高了，至少需要对每个索引节点都需要一个读操作（从磁盘读入内存）。为了改善性能，文件系统超级块包含一个数组（也是在磁盘中），以便把文件系统中空闲的索引节点号缓存起来。
ialloc算法如下：
内核首先验证无其他进程锁住超级块空闲索引节点表的存取。如果超级块中索引节点号表非空，则内核分配下一个索引节点号，使用iget算法为新分配的磁盘索引节点分配一个空闲的内存索引节点（如果需要，读取磁盘索引节点到内存），对索引节点各字段初始化（并写入磁盘，标志该节点已被分配出去），并返回这一上锁的索引节点。如果超级块中索引节点表为空，内核搜索磁盘索引节点线性表，并把尽可能多的索引节点号放入超级块中，直至超级块填满。最后填入的（即最大索引节点号）称为“铭记”索引节点，用来记录下次磁盘索引节点线性表搜索时的起始地址。
5.2释放索引节点
释放索引节点算法ifree如下：
六、磁盘块的分配与释放
上一小节讲述了索引节点的分配，文件不只有索引节点，还有磁盘块。本节阐述磁盘块的分配与释放。
6.1磁盘块的分配
文件系统超级块中包含一个用来把文件系统中的空闲磁盘块高速缓冲起来的数组。mkfs（文件系统生成）程序把一个文件系统的数据块组织到一张链表中，每个链是一个磁盘块，块中包含的是一个数组，数组分量是空闲磁盘块号，并且数组中有一个分量是链表上下一链的块号（需要说明的是，链上所有块都存在超级块中）。如下图所示：
当内核想从文件系统中分配一块的时候，把超级快中一个可用的分配出去。当超级块只剩第一个时，将超级块链接的下一块分配出去，并把其中存的数组数据复制到超级块中（如：当超级块只剩109时，将109分配出去，109数组内容复制到超级块，空出来用来分配给文件）。
算法描述如下：
6.2磁盘块的释放
释放算法free与分配算法相反 ：如果超级块未满，新释放的块的块号放入超级块。如果满了，新释放的块变为一个链接块，内核把超级块表写到这一块上，然后将原来超级块的块号写入刚释放的块（即现在超级快上）。
七、总结
本章从索引节点和磁盘块的角度讲述了文件创建删除、读取时所采取的索引节点和磁盘块的操作，涉及索引节点的分配与释放（第五部分）（用于创建删除文件）、磁盘块的分配与释放（第六部分）（用于创建删除文件）、内存中索引节点的分配与释放（第一部分）（用于读取文件）。