第十一章 EXT2文件系统
一. 梗概
多年来，Linux 一直使用EXT2(Card等 1995)作为默认文件系统。EXT3(EXT3，14)是 EXT2 的扩展。EXT3 中增加的主要内容是一个日志文件，它将文件系统的变更记录在日志中。日志可在文件系统崩溃时更快地从错误中恢复。没有错误的 EXT3 文件系统与 EXT2 文件系统相同。EXT3 的最新扩展是 EXT4(Cao 等 2007)。EXT4 的主要变化是磁盘块的分配。在 EXT4中，块编号为48位。EXT4不是分配不连续的磁盘块，而是分配连续的磁盘块区，称为区段。除了这些细微的更改之外，文件系统结构和文件操作保持不变。本书的目的是讲授文件系统的原理。主要目标并非实现大的文件存储容量，而是重点论述文件系统设计和实现的原则，强调简单性以及与 Linux 的兼容性。
二.主要知识点归纳
1、超级块
如果说inode块是Unix操作系统中文件的核心，那么超级块就是文件系统的心脏。启动Unix操作系统后，发现某个文件系统无法使用，很有 可能就是超级块出现了问题。为什么这个超级块有这么大的作用呢?主要是因为在超级块中保存了全局文件信息，如硬盘已用空间、数据块可用空间、inode结 点信息等等。做一个形象的比喻，这个超级块就好像是企业的资产负债表，一个文件系统中有哪些资源都记录在这个表中。
2、块组描述符
块组描述符表的起始地址位于超级块所在块的下一个块，在整个文件系统中有很多块 组描述符表的备份，备份的方式具体分为两种：
(1) 文件系统不具备稀疏超级块特性。
如果文件系统不具备稀疏超级块特性，那么在每个块组中都会有一个超级块的备份， 同时也有块组描述符表的备份。
(2) 文件系统具备稀疏超级块特性。
如果文件系统具备稀疏超级块特性，那么只在块组号是3、5、7的幂的块组（如1、3、 5、7、9、25、49等）内才对超级块和块组描述符表做备份，其他块组内则没有备份。
3、索引节点
理解inode，要从文件储存说起。
文件储存在硬盘上，硬盘的最小存储单位叫做”扇区”（Sector）。每个扇区储存512字节（相当于0.5KB）。
操作系统读取硬盘的时候，不会一个个扇区地读取，这样效率太低，而是一次性连续读取多个扇区，即一次性读取一个”块”（block）。这种由多个扇区组成的”块”，是文件存取的最小单位。”块”的大小，最常见的是4KB，即连续八个 sector组成一个 block。
文件数据都储存在”块”中，那么很显然，我们还必须找到一个地方储存文件的元信息，比如文件的创建者、文件的创建日期、文件的大小等等。这种储存文件元信息的区域就叫做inode，中文译名为”索引节点”。
每一个文件都有对应的inode，里面包含了与该文件有关的一些信息。
inode包含文件的元信息，具体来说有以下内容：
1）文件的字节数
2）文件拥有者的User ID
3）文件的Group ID
4）文件的读、写、执行权限
5）文件的时间戳，共有三个：
ctime指inode上一次变动的时间
mtime指文件内容上一次变动的时间
atime指文件上一次打开的时间。
6）链接数，即有多少文件名指向这个inode
7）文件数据block的位置
可以用stat命令，查看某个文件的inode信息：
stat example.txt
i_block[15]数组包含的磁盘块指针：
4、文件系统结构
EXT2文件系统的主要组成结构有：inode table（inode表格）、data block（信息区块）、superblock（超级区块）、filesystem description（文件系统描述说明）、inode bitmap（inode对照表）、block bitmap（区块对照表）等。
在EXT2文件系统中，文件的权限、属性与文件的内容是分开存储的，文件的权限和属性都存储在inode中，而文件内容则存储在block中。inode和block的大小和数量都是在格式化（即文件系统创建）的时候就已经固定了的。每个inode的大小均为128bytes（ext4与xfs可以设置256bytes），每个文件仅占用一个inode，所以文件系统中能够建立的文件数量与inode的数量有关。block有1k，2k和4k三种大小，所以当文件内容的大小超出block的大小时就需要多个block来存储了。
每个inode和block都是有编号的。inode中不仅存储了文件的权限和属性，也存储了文件内容存放的所有block的编号，这样只要找到文件的inode就能根据inode中记录的block的编号一次性把所有存放该文件内容的block的数据全部读取出来了。如图：
记录一个block编号需要4bytes的空间，如果一个文件比较大的话，需要的block的数量是比较多的，但是inode只有128bytes啊，怎么记录得了那么多的block编号呢？其实并不是所有的block编号都直接记录在inode中的，当文件占用的block数量比较多的时候，系统会拿出一些block专门来记录文件内容block的编号，然后inode只要记录这些block的编号就可以读取到文件内容block的编号了。EXT2把inode中记录blok编号的区域定义为12个直接，一个间接，一个双间接，和一个三间接记录区。如图
inode结构体
i_mode
i_block[15]数组存了15个指针
i_block[0-11]指向12个直接磁盘块
i_block[12]是间接块，指向一个磁盘块，该磁盘块包含256个块编号，即能映射256个磁盘块
i_block[13]是双重间接块，即双重映射，1 --> 256 * 256
i_block[14]是三重间接块，即三重映射，1 --> 256 * 256 * 256
dentry结构体
遍历算法：
(1）读取超级块。检查幻数s_magic ( OxEF53)，验证它确实是EXT2FS。
(2）读取块组描述符块(1+s_first_data_block)，以访问组0描述符。从块组描述符的bg_inode_table条目中找到索引节点的起始块编号，并将其称为InodesBeginBlock 。
(3)读取 InodeBeginBlock，获取/的索引节点，即INODE #2。
(4）将路径名标记为组件字符串，假设组件数量为n。
例如，如果路径名=/a/b/c，则组件字符串是“a”"b”“c”，其中n =3。用name[0]，name[1]，…，name[n-1]来表示组件。
(5)
从(3）中的根索引节点开始，在其数据块中搜索name[0]。
为简单起见，我们可以假设某个目录中的条目数量很少，因此一个目录索引节点只有12个直接数据块。
有了这个假设，就可以在12个(非零)直接块中搜索name[0]。目录索引节点的每个数据块都包含以下形式的dir_entry结构体:
[ino rec_len name_len NANE] [ino rec_len name_len NAME]
其中NAME是一系列nlen字符，不含终止NULL。
对于每个数据块，将该块读入内存并使用dir_entry *dp指向加载的数据块。
然后使用name_len将NAME提取为字符串，并与name[0]进行比较。如果它们不匹配,则通过以下代码转到下一个dir_entry:
dp = (dir_entry *) ((char *)dp + dp->rec_len);
继续搜索。如果存在name[0]，则可以找到它的dir_entry，从而找到它的索引节点号。
(6)
使用索引节点号ino来定位相应的索引节点。回想前面的内容，ino从1开始计数。使用邮差算法计算包含索引节点的磁盘块及其在该块中的偏移量。
blk=(ino - 1) / INODES_PER_BLOCK+ InodesBeginBlock;
offset = (ino - 1)% INODES_PER_BLOCK;
然后在索引节点中读取/a，从中确定它是否是一个目录(DIR)。
如果/a不是目录，则不能有/a/b，因此搜索失败。
如果它是目录，并且有更多需要搜索的组件，那么继续搜索下一个组件name[1]。
现在的问题是:在索引节点中搜索/a的name[1]，与第(5)步完全相同。
(7)
由于(5)~(6)步将会重复n次，所以最好编写一个搜索函数:
u32 search ( INODE*inodePtr, char *name)
然后只需调用n次search函数
如果搜索循环成功结束，ip必须指向路径名的索引节点。
文件系统的结构
文件系统的级别
文件系统的实现分为三个级别。每个级别处理文件系统的不同部分。这使得实现过程模块化，更容易理解。
第1级别实现了基本文件系统树。用户命令程序有：mkdir，creat，mknod，rmdir，link，unlink，symlink，rm，ls，cd和pwd
第2级别实现了文件内容读写函数
第3级别实现了文件系统的挂载、卸载和文件保护
基本文件系统
type.h文件
这类文件包含EXT2文件系统的数据结构类型，比如超块、组描述符、索引节点和目录条目结构。
此外，它还包含打开文件表、挂载表、PROC结构体和文件系统常数。
global.c文件
这类文件包含文件系统的全局变量。全局变量的例子有:
MINODE minode [NMINODE]; //in memory INODEs
MTABLE mtable[NMTABLE]; //mount tables
OFT oft[NOFT]; //Opened file instance
PROC proc [NPROC] //PRoC structures
PROC *running; //current executing PROC
util.c文件
该文件包含文件系统常用的实用程序函数。最重要的实用程序函数是读/写磁盘块函数iget()、iput()和 getino()。
mount-root.c文件
该文件包含mount_root()函数，在系统初始化期间调用该函数来挂载根文件系统。它读取根设备的超级块，以验证该设备是否为有效的EXT2文件系统。
然后，它将根设备的根 INODE ( ino = 2)加载到minode中，并将根指针设置为根minode。它还将所有进程的当前工作目录设置为根minode。
分配一个挂载表条目来记录挂载的根文件系统。根设备的一些关键信息，如 inode和块的数量、位图的起始块和inode,表，也记录在挂载表中，以便快速访问。
学习自测
