一、学习笔记

1.EXT2文件系统

多年来，Linux 一直使用EXT2(Card等1995)作为默认文件系统。EXT3(EXT3,2014)是EXT2的扩展。EXT3中增加的主要内容是一个日志文件，它将文件系统的变更记录在日志中°日志可在文件系统崩溃时更快地从错误中恢复。没有错误的EXT3文件系统与EXT2文件系统相同。EXT3的最新扩展是EXT4 ( Cao等2007)。EXT4的主要变化是磁盘块的分配。在EXT4中，块编号为48位。EXT4不是分配不连续的磁盘块，而是分配连续的磁盘块区，称为区段。除了这些细微的更改之外，文件系统结构和文件操作保持不变。本书的目的是讲授文件系统的原理°主要目标并非实现大的文件存储容量，而是重点论述文件系统设计和实现的原则，强调简单性以及与Linux的兼容性。为此，我们以ETX2作为文件系统。

2.EXT2文件系统数据结构

（1）通过mkfs创建虚拟磁盘：
mke2fs [-b blksize -N ninodes] device nblocks
在设备上创建一个带有nblocks个块(每个块大小为blksize字节)和ninodes个索引节点的EXT2文件系统。设备可以是真实设备，也可以是虚拟磁盘文件。如果未指定blksize,则默认块大小为1KB,如果未指定ninoides, mke2fs将根据nblocks计算一个默认的ninodes数。得到的EXT2文件系统可在Linux中使用。举个具体的例子，下面的命令
dd if=/dev/zero of=vdisk bs«1024 count«1440
mke2fs vdiek 1440
可在一个名为vdisk的虚拟磁盘文件上创建一个EXT2文件系统，有1440个大小为1KB的块。

（2）虚拟磁盘布局
一开始，我们先使用这个基本文件系统布局进行假设。在适当的时候，我们会指出一些变化，包括硬盘上大型EXT2/3文件系统中的变化。下面来简要解释一下磁盘块的内容。
Block#0：引导块：B0是引导块，文件系统不会使用它。它用来容纳一个引导程序，从磁盘引导操作系统。

（3）超级块
Block#1：超级块：(在硬盘分区中字节偏移量为1024)B1是超级块，用于容纳整个文件系统的信息。下文说明了超级块结构中的一些重要字段：
struct ext2_auper_block{
u32 s_inodes_count; /*Inodes count /
u32 s_blocks_count; /Blocks count /
u32 s_r_blocks_count； /Reserved blocks count /
u32 s_free_blocks_count； /Free blocks count /
u32 s_free_inodes_count; /Free inodes count /
u32 s_first_data_block； /First Data Block /
u32 s_log_block_size; /Block size /
u32 s_log_cluster_size; /Allocation cluster size /
u32 s_blocks_per_group; /# Blocks per group /
u32 s_clusters_per_group； /# Fragments per group /
u32 s_inodes_per_group； /# Inodes per group /
u32 s_mtime; /Mount time /
u32 s_wtime; /Write time /
U16 s_jnnt_count; /Mount count /
S16 s_max_mnt_count; /Maximal mount count /
ul6 s_magic; /Magic signature /
// more non-essential fields
ul6 s_inode_size; / size of inode structure */

}
大多数超级块字段的含义都非常明显。只有少数几个字段需要详细解释。 s_first_data_block：0表示4KB块大小，1表示1KB块大小。它用于确定块组描述符的起始块，即 s_first_data_block+1。 s_log_block_size：确定文件块大小，为1KB*(2**s_log_block_size),例如：0表示1KB块大小，1表示2KB块大小，2表示4KB块大小等。最常用的块大小是用于小文件系统的1KB和用于大文件系统的4KB。 s_mnt_count：已挂载文件系统的次数。当挂载计数达到max_mnt_count时，fsck会话将被迫检查文件系统的一致性。 s_magic：标识文件系统类型的幻数。EXT2/3/4文件系统的幻数是0xEF53。

（4）快组描述符
Block#2：块组描述符块(硬盘上的s_first_data_block+1) EXT2将磁盘块分成几个组。每个组有8192个块(硬盘上的大小为32K)。每组用一个块组描述符结构体来描述。
struct ext2_group_desc{
u32 bg_block_bitmap; //Bmap block number
u32 bg_inode_bicmap; //Imap block number
u32 bg_inode_table; //Inodes begin block number
ul6 bg_free_blocks_count; //THESE are OBVIOUS
U16 bg_free_inodes_count;
U16 bg_used_dirs_count;
ul6 bg_pad; //ignore these
u32 bg_reserved(3);
｝;
由于一个虚拟软盘(FD)只有1440个块，B2就只包含一个块组描述符。其余的都是0。在有大量块组的硬盘上，块组描述符可以跨越多个块。块组描述符中最重要的字段是bg_block_bitmap、bg_inode_bitmap和bg_inode_table,它们分别指向块组的块位图、索引节点位图和索引节点起始块。对于Linux格式的EXT2文件系统，保留了块3到块7。所以bmap=8,imap=9,inode_table= 10。

（5）块和索引点位图
Block#8：块位图(Bmap)(bg_block_bitmap)位图是用来表示某种项的位序列，例如磁盘块或索引节点。位图用于分配和回收项。在位图中，0位表示对应项处于FREE状态，1位表示对应项处于IN_USE状态。一个软盘有1440个块，但是Block#。未被文件系统使用。所以，位图只有1439个有效位。无效位被视作IN_USE,设置为1。
Block#9：索引节点位图(Imap)(bg_inode_bitmap)一个索引节点就是用来代表一个文件的数据结构。EXT2文件系统是使用有限数量的索引节点创建的。各索引节点的状态用B9的Imap中的一个位表示。在EXT2 FS中，前10个索引节点是预留的。所以，空EXT2 FS的Imap以10个1开头，然后是0。无效位再次设置为1。

（6）索引节点
*Block#10：索引(开始)节点：(bg_inode_table)每个文件都用一个128字节(EXT4中是256字节)的唯一索引节点结构体表示。下面列出了主要索引节点字段。
struct ext2_inode {
ul6 i_mode; //16 bits = |tttt|ugs|rwx|rwx|rwx|
ul6 i_uid; //owner uid
u32 i_size; //file size in bytes
u32 i_atime; //time fields in seconds
u32 i_ctime; //since 00:00:00,1-1-1970
u32 i_mtime;
u32 i__dtime;
U16 i_gid; //group ID
u16 i_links_count; //hard-link count
u32 i_blocks; //number of 512-byte sectors
u32 i_flags; //IGNORE
u32 i_reserved1; //IGNORE
u32 i_block[15]; //See details below
u32 i_pad[7];； //for inode size = 128 bytes
}
在索引节点结构体中，i_mode为U16或2字节无符号整数。在i_mode字段中，前4位指定了文件类型，例如：tttt=1000表示REG文件，0100表示DIR文件等。接下来的3位ugs表示文件的特殊用法。最后9位是用于文件保护的rwx权限位。 i_size字段表示文件大小（以字节为单位）。各时间字段表示自1970年1月1日0时0分0秒以来经过的秒数。所以，每个时间字段都是一个非常大的无符号整数：可借助以下库函数将它们转换为日历形式：
char *ctime （&time_field）
将指针指向时间字段，然后返回一个日历形式的字符串。例如:
printf("%s", ctime(&inode.i_atime); // note： pass & of time field prints i_atime in calendar form.
i_block[l5]数组包含指向文件磁盘块的指针，这些磁盘块有：
直接块：i_block[0] Mi_block[ll],指向直接磁盘块。
间接块：i_block[12]指向一个包含256个块编号（对于1KB BLKSIZE）的磁盘块，每个块编号指向一个磁盘块。
双重间接块：i_block[13]指向一个指向256个块的块，每个块指向256个磁盘块。
三重间接块： **i_block[14]是三重间接块。对于“小型” EXT2文件系统，可以忽略它。
索引节点大小（128或256 ）用于平均分割块大小（1KB或4KB）,所以，每个索引节点块都包含整数个索引节点在简単的EXT2文件系统中，索引节点的数量是184个（Linux默认值）。索引节点块数等于184/8-23个。因此，索引节点块为B10至B32。每个索引节点都有一个唯一的索引节点编号，即索引节点在索引节点块上的位置+1。注意，索引节点位置从0开始计数，而索引节点编号从1开始计数。0索引节点编号表示没有索引节点一根目录的索引节点编号为2。同样，磁盘块编号也从1开始计数，因为文件系统从未使用块0。块编号0表示没有磁盘块。

（7）数据块
紧跟在索引节点块后面的是文件存储数据块，假设有184个索引节点，第一个实际数据块是B33,它就是根目录/的i_block[0]。

（8）目录条目
目录包含dir_entry结构，即
struct ext2_dir_entry_2{**
U32 inode; //inode number; count from 1; NOT 0
U16 rec_len; //this entry's length in bytes
U8 name_len; //name length in bytes
u8 file_type; //not used
char name[EXT2_NAME_LEN]; //name:1-255 chars, no ending NULL
dir_entry是一种可扩充结构。名称字段包含1到255个字符，不含终止NULL。所以 dir_entry的rec_len也各不相同。

3.邮差算法

在计算机系统中，经常出现下面这个问题。一个城市有M个街区，编号从0到M-1。每个街区有N座房子，编号从0到N-1。每座房子有一个唯一的街区地址。用(街区，房子)表示，其中0≤街区＜M, 0≤房子＜N。来自外太空的外星人可能不熟悉地球上的街区寻址方案，倾向于采用线性方法将这些房子地址编为0, 1, N-l, N, N+1等。已知某个街区地址BA=（街区，房子），怎么把它转换为线性地址LA,反过来，已知线性地址, 怎么把它转换为街区地址？如果都从0开始计数，转换就会非常简单。
Linear_address LA = N*block + house;
Block_address BA = (LA / N, LA % N);
注意，只有都从0开始计数时，转换才有效。如果有些条目不是从。开始计数的，则不能直接在转换公式中使用。读者可以试着找出处理这种情况的一般方法。为方便表述，我们把这种转换方法称为邮差算法。下面给出了邮差算法的几种应用。

（1）C语言中的Test-Set-Clear位
在标准C语言程序中，最小的可寻址单元是一个字符或字节。在一系列位组成的位图中，通常需要对位进行操作。考虑字符bufI1024],它有1024个字节，用buf[i]表示，其中
i = 0,1,…,1023。它还有8192个位，编号为0,1,2,…,8191=已知一个位号BIT,
例如1234,那么哪个字节i包含这个位，以及哪个位j在该字节中呢？
i = BIT/8; j = BIT%8; //8 = number of bits in a byte.
我们可在c语言中结合使用邮差算法和位屏蔽来进行下面的位操作。
.TST a bit for 1 or 0 : if (buf[i] & (1 « j))
.SET a bit to 1 : buf[i] |= (1 « j);
.CLR a bit to 0 : buffi] &= ~(1 « j);
注意，一些c语言编译器允许在结构体中指定位，如:
struct bits{
unsigned int bit0 : 1; // bit0 field is a single bit
unsigned int bit123 : 3; // bitl23 field is a range of 3 bits
unsigned int otherbits : 27; // other bits field has 27 bits
unsigned int bit31 : 1; // bit31 is the highest bit
}var;
该结构体将var.定义为一个32位无符号整数，具有单独的位或位范围。那么，var.bitO= 0；将1赋值给第0位，则有var.bit123 = 5：将101赋值给第1位到第3位等。但是，生成的代码仍然依赖于邮差算法和位屏蔽来访问各个位。我们可以用邮差算法直接操作位图中的位，无须定义复杂的C语言结构体。

（2）将索引节点号转换为磁盘上的索引节点
在EXT2文件系统中，每个文件都有一个唯一的索引节点结构。在文件系统磁盘上，索引节点从inodejable块开始。每个磁盘块包含
INODES_PER_BLOCK = BLOCK_SIZE/sizeof (INODE)
个索引节点。每个索引节点都有一个唯一的索引节点号，ino=l,2，…，从1开始线性计数。已知一个ino,如1234，那么哪个磁盘块包含该索引节点，以及哪个索引节点在该块中呢？我们需要知道磁盘块号，因为需要通过块来读/写一个真正的磁盘。
block = (ino - 1) / INODES_PER_BLOCK + inode_table;
inode - (ino - 1) % INODES_PER_BLOCK;
同样，将EXT2文件系统中的双重和三重间接逻辑块号转换为物理块号也依赖于邮差算法。将线性磁盘块号转换为CHS =(柱面、磁头、扇区)格式：软盘和旧硬盘使用CHS寻址，但文件系统始终使用线性块寻址。在调用BIOS INT13时，可用该算法将磁盘块号转换为CHS。

5.遍历EXT2 文件系统树

遍历算法
（1）读取超级块。检查幻数 s_magic（0xEF53），验证它确实是 EXT2 FS。
（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）从根索引节点开始，在其数据块中搜索 name[0]。为简单起见，我们可以假设某个目录中的条目数量很
少，因此一个目录索引节点只有12个直接数据块。有了这个假设，就可以在12个（非零）直接块中搜索
name[0]。目录索引节点的每个数据块都包含以下形式的 dir_entry 结构体;
[ino rec_len name_len NAME] [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);
（6）继续搜索。如果存在 name[0]，则可以找到它的 dir_entry，从而找到它的索引节点号。
使用索引节点号ino来定位相应的索引节点。回想前面的内容，ino 从1开始计数。使用邮差算法计算包含索引节点的磁盘块及其在该块中的偏移量。
blk =(ino - 1) / INODE8_PER_BLOCK + InodesBeginBlock;
offset = (ino - 1) % INODES_PER_BLOCK;
然后在索引节点中读取/a，从中确定它是否是一个目录（DIR）。如果/a不是目录，则不能有/a/b，因此搜索失败。如果它是目录，并且有更多需要搜索的组件，那么继续搜索下一个组件 name[1]。现在的问题是∶在索引节点中搜索/a的 name[1]，与第（5）步完全相同。
由于（5）～（6）步将会重复n次，所以最好编写一个搜索函数∶
u32 search (INODE *inodePtr, char *name)
{
// search for name in the data blocks of current DIR inode
// if found, return its ino; else return 0 )
}
然后我们只需调用 search()n次，如下所示。
Assume:n,name[0],....,name[n-1] are globals
INODE *ip points at INODE of /
for（i=0; i<n; i++）
{
ino = search(ip, name[4])
if(!ino){ // can't find name[i], exit;}
use ino to zead in INODE and let ip point to INODE
}
如果搜索循环成功结束，ip必须指向路径名的索引节点。遍历有多个组的大型 EXT2/3 文件系统也是类似操作。

6.基本文件系统

（1）type.h 文件
这类文件包含EXT2文件系统的数据结构类型，比如超块、组描述符、索引节点和目录条目结构。此外，它还包含打开文件表、挂载表、PROC结构体和文件系统常数。

（2）global.c 文件
这类文件包含文件系统的全局变量。全局变量的例子有：
MINODE minode [NMINODE]; // in memory INODEs
MTABLE mtable [NMTABLE]; // mount tables
OFT oft [NOFT]; // Opened file instance
PROC proc[NPROC]PROC ] // PROC structures
PROC *running; // current executing

（3）实用程序函数
a. get_block/put_block 函数
b. iget(dev, ino) 函数
c. The iput（INODE *mip）函数
d. getino（）函数
e. getino（）/iget（）/iput（）的使用

（4）mount-root
如何执行ls

7.文件系统的级别

文件系统的实现分为三个级别。每个级别处理文件系统的不同部分。这使得实现过程模块化，更容易理解。在文件系统的实现过程中，FS目录包含实现EXT2文件系统的文件。

1级文件系统函数及其原理
1级文件系统函数的功能是文件和路径、创建和删除等较为直接和底层的相关的操作。
mkdir：mkdir创建一个带路径名的新目录。同时将目录的权限设置为 0755 ，即 rwxr_xr_x ，所有人可以访问和读写，其他人可以访问但是只能读取。
creat：creat创建一个空的普通文件。
rmdir：删除一个路径。
link：链接文件。
unlink:解除链接文件。
2级文件系统函数及其原理
2级文件系统函数的功能常常是打开、读取文件、写入文件等对文件进行的操作。
open：打开文件。
lseek：将打开的文件描述符在OFT中的偏移量从文件开头或当前位置开始的字节位置。
close：关闭文件描述符。
3级文件系统函数及其原理
3级文件系统函数进行文件系统的挂载、卸载和文件保护等。
mount:挂载。使用方法：
mount filesys mount_point
卸载：卸载已经挂载的文件系统。