本文转载自微信公众号「Linux内核远航者」，作者Linux内核远航者。转载本文请联系Linux内核远航者公众号。
本文以ext2文件系统为例来剖析一个真实的文件系统如何查找文件，这对于深入理解文件系统至关重要。
1.准备文件系统镜像
所用工具：dd、mkfs.ext2、hexdump、dumpe2fs、mount等工具
1)制作100k大小镜像文件
- $ dd if=/dev/zero of=ext2.img bs=1k count=100
- 记录了100+0 的读入
- 记录了100+0 的写出
- 102400 bytes (102 kB, 100 KiB) copied, 0.00125457 s, 81.6 MB/s
2)格式化为ext2文件系统格式
- $ mkfs.ext2 ext2.img
- mke2fs 1.44.1 (24-Mar-2018)
- 丢弃设备块： 完成
- 创建含有 100 个块（每块 1k）和 16 个inode的文件系统
-
- 正在分配组表： 完成
- 正在写入inode表： 完成
- 写入超级块和文件系统账户统计信息： 已完成
3)查看文件系统信息
- $ dumpe2fs ext2.img
- dumpe2fs 1.44.1 (24-Mar-2018)
- Filesystem volume name:
- Last mounted on: <not available>
- Filesystem UUID: 3680e1d5-7f58-4324-9cbd-c7d382f0c3df
- Filesystem magic number: 0xEF53
- Filesystem revision #: 1 (dynamic)
- Filesystem features: ext_attr resize_inode dir_index filetype sparse_super large_file
- Filesystem flags: signed_directory_hash
- Default mount options: user_xattr acl
- Filesystem state: clean
- Errors behavior: Continue
- Filesystem OS type: Linux
- Inode count: 16
- Block count: 100
- Reserved block count: 5
- Free blocks: 79
- Free inodes: 5
- First block: 1
- Block size: 1024
- Fragment size: 1024
- Blocks per group: 8192
- Fragments per group: 8192
- Inodes per group: 16
- Inode blocks per group: 2
- Filesystem created: Wed May 26 15:23:33 2021
- Last mount time: n/a
- Last write time: Wed May 26 15:23:33 2021
- Mount count: 0
- Maximum mount count: -1
- Last checked: Wed May 26 15:23:33 2021
- Check interval: 0 (
) - Reserved blocks uid: 0 (user root)
- Reserved blocks gid: 0 (group root)
- First inode: 11
- Inode size: 128
- Default directory hash: half_md4
- Directory Hash Seed: 5b0daa29-c2a0-4ab1-b09e-50992d3b070d
-
-
- 组 0：(块 1-99)
- 主 超级块位于 1，组描述符位于 2-2
- 块位图位于 3 (+2)
- Inode 位图位于 4 (+3)
- Inode表位于 5-6 (+4)
- 79 个可用 块，5 个可用inode，2 个目录
- 可用块数： 21-99
- 可用inode数： 12-16
这实际是是读取文件系统的超级块和块组描述符信息。我们可以看的创建的文件系统的总体信息：
Filesystem magic number：0xEF53 表示为ext2文件系统
Inode count: 16 表示文件系统inode个数为16
Block count: 100 表示文件系统块个数为100
Free blocks: 79 表示文件系统空闲块个数为79
Free inodes: 5 表示文件系统空闲inode个数为5
First block: 1 第一个数据块编号为1(编号0保留为引导块)
Block size: 1024 文件系统块大小为1k
Blocks per group: 8192 每个块组8192个块
Inodes per group: 16 每个块组个inode
Inode blocks per group: 2 每个块组2个inode块
First inode: 11 分配的第一个inode号为11(除根inode外，根inode号为2)
Inode size: 128 inode大小为128字节
块组的信息(这里只有一个块组) 1 - 99号
超级块块编号为 1
块组描述符块编号为 2 块
位图块编号为 3
inode位图块编号为 4
inode表位于5和6块
79 个可用 块，5 个可用inode，2 个目录 (一个为根目录一个为lost+found，存放坏块) 可用块数：21-99 可用inode数：12-16
4)挂载文件系统并创建文件
- 创建一个挂载点目录：
- $ mkdir root_dir
-
- 挂载：
- $ sudo mount -t ext2 ext2.img root_dir
-
- 查看文件：
- $ ls -la
- 总用量 17
- drwxr-xr-x 3 root root 1024 5月 26 15:23 .
- drwxrwxr-x 3 hanch hanch 4096 5月 26 15:28 ..
- drwx------ 2 root root 12288 5月 26 15:23 lost+found
可以发现有三个目录:
- .
- ..
- lost+found
实际上是根目录的数据块的内容(包含各个目录项)。
下面我们来创建一个目录，目录下创建文件：
- $ sudo mkdir dir
-
- $ cd dir/
- $ su
- # echo hello > test.txt
现在目录树是这样的：
- $ tree
- .
- ├── dir
- │ └── test.txt
- └── lost+found [error opening dir]
-
- 2 directories, 1 file
后面我们会通过解析文件系统镜像来观察如何查找 /dir/test.txt 文件的
现在关注一下相关的索引节点：
- $ cd dir
-
- $ ls -lai
- 总用量 3
- 12 drwxr-xr-x 2 root root 1024 5月 26 15:57 .
- 2 drwxr-xr-x 4 root root 1024 5月 26 15:56 ..
- 13 -rw-r--r-- 1 root root 6 5月 26 15:57 test.txt
可以发现 /dir目录下：当前工作目录下索引节点为12(dir目录的)，上一级目录的索引节点为2(根目录)，test.txt文件的所有节点为13。记住这几个索引节点后面我们会通过解析文件系统镜像来获得。
2.解析文件系统镜像
1)dump文件系统镜像
- $ hexdump -C ext2.img
-
- 00000000 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................|
- *
- 00000400 10 00 00 00 64 00 00 00 05 00 00 00 4f 00 00 00 |....d.......O...|
- 00000410 05 00 00 00 01 00 00 00 00 00 00 00 00 00 00 00 |................|
- 00000420 00 20 00 00 00 20 00 00 10 00 00 00 ae f8 ad 60 |. ... .........`|
- 00000430 ae f8 ad 60 01 00 ff ff 53 ef 00 00 01 00 00 00 |...`....S.......|
- 00000440 75 f7 ad 60 00 00 00 00 00 00 00 00 01 00 00 00 |u..`............|
- ...
- *
- 00018c00 0c 00 00 00 0c 00 01 02 2e 00 00 00 02 00 00 00 |................|
- 00018c10 0c 00 02 02 2e 2e 00 00 0d 00 00 00 e8 03 08 01 |................|
- 00018c20 74 65 73 74 2e 74 78 74 00 00 00 00 00 00 00 00 |test.txt........|
- 00018c30 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................|
- *
- 00019000
根据之前dumpe2fs的信息我们知道：
镜像文件中(均为16进制显示)
00000000 开始的1k大小 保留的引导块
块1 00000400 开始的1k大小 保存磁盘的超级块 (dumpe2fs的部分信息从这里获得)
块2 00000800 开始的1k大小 保存块组描述符 (dumpe2fs的部分信息从这里获得)
块3 00000c00 开始的1k大小 保存块位图
块4 00001000 开始的1k大小 保存 Inode 位图
块5 块6 00001400 开始的2k大小 保存 Inode表
剩下的为数据块
磁盘中的文件系统对象结构在内核如下文件定义：
- fs/ext2/ext2.h
-
- 磁盘超级块：
- struct ext2_super_block {
- __le32 s_inodes_count;
- __le32 s_blocks_count;
- __le32 s_r_blocks_count;
- __le32 s_free_blocks_count;
- __le32 s_free_inodes_count;
- __le32 s_first_data_block;
- __le32 s_log_block_size;
- __le32 s_log_frag_size;
- __le32 s_blocks_per_group;
- __le32 s_frags_per_group;
- __le32 s_inodes_per_group;
- ...
- }
-
- 磁盘块组描述符：
- struct ext2_group_desc
- {
- __le32 bg_block_bitmap;
- __le32 bg_inode_bitmap;
- __le32 bg_inode_table;
- __le16 bg_free_blocks_count;
- __le16 bg_free_inodes_count;
- __le16 bg_used_dirs_count;
- __le16 bg_pad;
- __le32 bg_reserved[3];
- };
-
-
- 磁盘inode:
- struct ext2_inode {
- __le16 i_mode;
- __le16 i_uid;
- __le32 i_size;
- __le32 i_atime;
- __le32 i_ctime;
- __le32 i_mtime;
- __le32 i_dtime;
- __le16 i_gid;
- __le16 i_links_count;
- __le32 i_blocks;
- ...
- __le32 i_block[EXT2_N_BLOCKS];
- ...
- };
-
-
- 磁盘目录项：
- struct ext2_dir_entry_2 {
- __le32 inode;
- __le16 rec_len;
- __u8 name_len;
- __u8 file_type;
- char name[];
- };
大家可以对照磁盘镜像文件和磁盘数据结构定义来解析出文件系统的超级块和块组描述符信息(可以发现和dumpe2fs工具显示的是一致的，例如镜像文件00000400 处四字节为10 00 00 00 是小端存储，所以为0x00000010=16);
3.路径名查找
下面开始我们的重头戏：查找文件系统中的 /dir/test.txt 文件。
我们知道，使用文件系统给我最直观也是最大的好处是：用户可以通过一个路径名来访问文件，那么一个文件系统究竟如何来找到我们所需要的文件呢?下面我们详细来看ext2文件系统如何查找指定的文件的?(实际的内核中路径名查找比较复杂，考虑很多情况，如dentry cache查找、解析软链接文件、上级目录、挂载点等，当然如果目录分量是挂载点就会步进到相应文件系统的根目录，后面文件系统挂载专题会讲解，这里以简单的路径解析来让大家有个深刻的认识)。
1)查找根目录
万事开头难，对于访问一个目录上挂载的文件系统，内核路径名查找会判断并找到挂载的文件系统的根目录，这个过程在文件系统挂载的时候，会从磁盘上读取并在内存构建超级块实例，然后进行的最重要的一步是读取文件系统的根inode:
- fs/ext2/super.c
- ext2_fill_super
- ->root = ext2_iget(sb, EXT2_ROOT_INO) //EXT2_ROOT_INO为2，系统定义好的
- ->raw_inode = ext2_get_inode(inode->i_sb, ino, &bh); //根据inode号查找磁盘inode
- 核心算法如下：
- ->block_group = (ino - 1) / EXT2_INODES_PER_GROUP(sb) //获得块组 编号
- gdp = ext2_get_group_desc(sb, block_group, NULL); //获得块组描述符
- offset = ((ino - 1) % EXT2_INODES_PER_GROUP(sb)) * EXT2_INODE_SIZE(sb); //计算出在 块组的 inode表中的inode偏移
- block = le32_to_cpu(gdp->bg_inode_table) + (offset >> EXT2_BLOCK_SIZE_BITS(sb)); //计算出在文件系统中的块号
- bh = sb_bread(sb, block)) //组合成submit_bh 读取这个块到bh
- *p = bh; //赋值bh 用于返回
- offset &= (EXT2_BLOCK_SIZE(sb) - 1); //计算出块中偏移
- return (struct ext2_inode *) (bh->b_data + offset); //返回inode中位置
简述ext2通过inode号找到并读取磁盘inode核心算法：
根据inode号计算出所在的块组block_group
根据inode号计算出块组中的inode表中的字节偏移offset
根据inode号计算出磁盘inode在文件系统中的块号block
根据块号block 通过sb_bread读取缓冲区块到内存
根据inode表中的字节偏移offset 计算出 磁盘inode在块中偏移
通过读取的缓冲区和磁盘inode在块中偏移 最终返回磁盘inode结构
我们已知：
每个块组inode个数：EXT2_INODES_PER_GROUP(sb) = 16
磁盘inode大小：EXT2_INODE_SIZE(sb) = 128
块大小的bit表示：EXT2_BLOCK_SIZE_BITS(sb) = 10
所以计算根inode块号：
- ino=2 跟inode时：
-
- 块组编号: block_group = (ino - 1) / EXT2_INODES_PER_GROUP(sb) = (2 - 1) / 16 = 0
- inode表中的根inode偏移 : offset = ((ino - 1) % EXT2_INODES_PER_GROUP(sb)) * EXT2_INODE_SIZE(sb
- = ( 1 % 16 ) * 128 = 128 =0x80 (第2个inode 也就是0x1480处)
- 文件系统中的根inode所在块号 : block = le32_to_cpu(gdp->bg_inode_table) + (offset >> EXT2_BLOCK_SIZE_BITS(sb))
- = 5 + (128 >> 10) = 5
- 根inode所在块中偏移：offset &= (EXT2_BLOCK_SIZE(sb) - 1) = 128 = 0x80
- inode中位置 = bh->b_data + offset = 所在块 + 0x80
所以：根inode所在的镜像文件中偏移为：5 * 0x400 + 0x80 = 0x1400 + 0x80 = 0x1480
- 查看0x1480偏移处内容如下（即是根目录的磁盘inode内容）：
- *
- 00001480 ed 41 00 00 00 04 00 00 54 ff ad 60 44 ff ad 60 |.A......T..`D..`|
- 00001490 44 ff ad 60 00 00 00 00 00 00 04 00 02 00 00 00 |D..`............|
- 000014a0 00 00 00 00 01 00 00 00 07 00 00 00 00 00 00 00 |................|
- 000014b0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................|
- *
对照ext2文件系统磁盘inode结构，可知i_block为磁盘inode结构的偏移40B处，内容即为0x07(ext2通过i_block来查找文件在磁盘中的位置)。
于是我们知道，根目录数据块的块号 为0x7(镜像中字节偏移为 0x400 * 7= 1c00)，这个数据块中保存的是根目录中包含的所有目录和文件的目录项(我们知道这里为"."、".."、"dir"、"lost+found"四个目录项)。
- 根目录数据块的内容：
- *
- 00001c00 02 00 00 00 0c 00 01 02 2e 00 00 00 02 00 00 00 |................|
- 00001c10 0c 00 02 02 2e 2e 00 00 0b 00 00 00 14 00 0a 02 |................|
- 00001c20 6c 6f 73 74 2b 66 6f 75 6e 64 00 00 0c 00 00 00 |lost+found......|
- 00001c30 d4 03 03 02 64 69 72 00 00 00 00 00 00 00 00 00 |....dir.........|
- 00001c40 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................|
- *
根据目录项ext2_dir_entry_2 结构我们可以查询到文件名为dir的目录项，从而获取dir目录的inode号，为0x0c(和我们之前通ls -lai显示的dir目录inode号12是一致)。
2)查找dir目录
和上面查询根inode一样的原理，计算过程如下：
- dir目录所在块组编号: block_group = (ino - 1) / EXT2_INODES_PER_GROUP(sb) = (12 - 1) / 16 = 0
- dir目录所在inode表中的inode偏移 : offset = ((ino - 1) % EXT2_INODES_PER_GROUP(sb)) * EXT2_INODE_SIZE(sb
- = ( 11 % 16 ) * 128 = 1408（0x580）
- 文件系统中的dir目录的inode所在块号 : block = le32_to_cpu(gdp->bg_inode_table) + (offset >> EXT2_BLOCK_SIZE_BITS(sb))
- = 5 + (1408 >> 10) = 5 +1 =6
- dir目录的inode所在块号中偏移：offset &= (EXT2_BLOCK_SIZE(sb) - 1) = 1408（0x580）& (0x400 -1) = 0x180
- inode中位置 = bh->b_data + offset = 所在块 + 0x180
-
所以：dir目录inode所在的镜像文件中字节偏移为：6 * 0x400 + 0x180 = 0x1800 + 0x180 = 0x1980
- 查看0x1980偏移处内容如下（即是dir目录的磁盘inode内容）：
-
- *
- 00001980 ed 41 00 00 00 04 00 00 84 ff ad 60 66 ff ad 60 |.A.........`f..`|
- 00001990 66 ff ad 60 00 00 00 00 00 00 02 00 02 00 00 00 |f..`............|
- 000019a0 00 00 00 00 02 00 00 00 63 00 00 00 00 00 00 00 |........c.......|
- 000019b0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................|
- *
对照ext2文件系统磁盘inode结构，可知i_block为磁盘inode结构的偏移40B处，内容即为0x63。
于是我们知道，dir目录数据块的块号 为0x63(偏移为 0x400 * 0x63= 0x18c00)，这个数据块中保存的是dir目录中包含的所有目录和文件的目录项(我们知道这里为"."、".."、"test.txt"三个目录项)。
- dir目录数据块的内容：
-
- *
- 00018c00 0c 00 00 00 0c 00 01 02 2e 00 00 00 02 00 00 00 |................|
- 00018c10 0c 00 02 02 2e 2e 00 00 0d 00 00 00 e8 03 08 01 |................|
- 00018c20 74 65 73 74 2e 74 78 74 00 00 00 00 00 00 00 00 |test.txt........|
- 00018c30 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................|
- *
对照目录项ext2_dir_entry_2 结构，查找文件名为test.txt的inode号，即为0x0d(和我们之前通ls -lai显示的dir目录inode号13是一致)。
于是我们知道，test.txt文件的inode号为0x0d(13)。
2)查找test.txt文件
和上面查询根inode一样的原理，计算过程如下：
- test.txt文件inode所在块组 编号: block_group = (ino - 1) / EXT2_INODES_PER_GROUP(sb) = (13 - 1) / 16 = 0
- test.txt文件inode在 inode表中的inode偏移 : offset = ((ino - 1) % EXT2_INODES_PER_GROUP(sb)) * EXT2_INODE_SIZE(sb
- = ( 12 % 16 ) * 128 = 1536（0x600）
- 文件系统中的test.txt文件inode所在块号 : block = le32_to_cpu(gdp->bg_inode_table) + (offset >> EXT2_BLOCK_SIZE_BITS(sb))
- = 5 + (1536 >> 10) = 5 +1 =6
- test.txt文件inode所在块号中偏移：offset &= (EXT2_BLOCK_SIZE(sb) - 1) = 1408（0x600）& (0x400 -1) = 0x200
- inode中位置 = bh->b_data + offset = 所在块 + 0x200
所以：test.txt文件inode所在的镜像文件中偏移为：= 6 * 0x400 + 0x200 = 0x1800 + 0x200 = 0x1a00
- 查看 0x1a00偏移处内容如下（即是test.txt文件的磁盘inode内容）：
-
- 00001a00 a4 81 00 00 06 00 00 00 85 ff ad 60 66 ff ad 60 |...........`f..`|
- 00001a10 66 ff ad 60 00 00 00 00 00 00 01 00 02 00 00 00 |f..`............|
- 00001a20 00 00 00 00 01 00 00 00 15 00 00 00 00 00 00 00 |................|
- 00001a30 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................|
- *
对照ext2文件系统磁盘inode结构，可知i_block为磁盘inode结构的偏移40B处，内容即为0x15。
于是我们知道，test.txt文件数据块的块号 为0x15(偏移为0x15 * 0x400 = 0x5400)。
查看 0x5400偏移处内容如下(test.txt文件数据块的内容)：
- 查看 0x5400偏移处内容如下(test.txt文件数据块的内容)：
- *
- 00005400 68 65 6c 6c 6f 0a 00 00 00 00 00 00 00 00 00 00 |hello...........|
- 00005410 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................|
- *
最终可以看到文件数据为"hello"。
4)查找过程图解
以下为 dir/test.txt查找过程：
已知根目录inode号(ext2为2) -> 查找根目录磁盘inode(文件系统挂载时查找) -> 查找根目录的数据块 -> 查找dir目录的目录项找到其inode号 (为12) -> 查找dir目录的磁盘inode -> 查找dir目录的数据块 -> 查找test.txt文件的inode号(为13) -> 查找test.txt文件的磁盘inode -> 查找test.txt文件的数据块
下面为查找图解：
4.总结
对于ext2文件系统，路径名查找中，实际上是解析路径名的各个分量，查找每个分量的目录项，然后通过目录项找到inode号，通过inode号找到对应的磁盘inode，然后通过磁盘inode获得目录/文件的数据块, 最终查找到对应目录/文件的磁盘inode，而磁盘inode的i_block中保存着文件的逻辑块号和磁盘的逻辑块号映射关系，读写文件时就可以访问到整个文件。
