Ext2

一个磁盘可以划分成多个分区,每个分区必须先用格式化工具(例如某种mkfs命令)格式化成某种格式的文件系统,然后才能存储文件,格式化的过程会在磁盘上写一些管理存储布局的信息。

格式

文件系统中存储的最小单位是块(Block),一个块究竟多大是在格式化时确定的,例如mke2fs的-b选项可以设定块大小为1024、2048或4096字节。而上图中启动块(Boot Block)的大小是确定的,就是1KB,启动块是由PC标准规定的,用来存储磁盘分区信息和启动信息,任何文件系统都不能使用启动块。启动块之后才是ext2文件系统的开始,ext2文件系统将整个分区划成若干个同样大小的块组(Block Group)

fs-ext2layout.png

做一个EXT2看看

做一个EXT2的文件系统,然后将其挂载,看看其文件格式。

1
2
3
4
5
6
$ dd if=/dev/zero of=./img.1m count=256 bs=4K
...
$ mke2fs fs
...
$ sudo mount -o loop ./img.1m /mnt
$ sudo umount /mnt

使用od查看img.1m镜像文件

1
od -tx1 -Ax ./img.1m

Super Block

描述整个分区的文件系统信息,例如块大小、文件系统版本号、上次mount的时间等等。超级块在每个块组的开头都有一份拷贝。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
struct ext2_super_block {
__le32 s_inodes_count; /* Inodes count */
__le32 s_blocks_count; /* Blocks count */
__le32 s_r_blocks_count; /* Reserved blocks count */
__le32 s_free_blocks_count; /* Free blocks count */
__le32 s_free_inodes_count; /* Free inodes count */
__le32 s_first_data_block; /* First Data Block */
__le32 s_log_block_size; /* Block size */
__le32 s_log_frag_size; /* Fragment size */
__le32 s_blocks_per_group; /* # Blocks per group */
__le32 s_frags_per_group; /* # Fragments per group */
__le32 s_inodes_per_group; /* # Inodes per group */
__le32 s_mtime; /* Mount time */
__le32 s_wtime; /* Write time */
__le16 s_mnt_count; /* Mount count */
__le16 s_max_mnt_count; /* Maximal mount count */
__le16 s_magic; /* Magic signature */
__le16 s_state; /* File system state */
__le16 s_errors; /* Behaviour when detecting errors */
__le16 s_minor_rev_level; /* minor revision level */
__le32 s_lastcheck; /* time of last check */
__le32 s_checkinterval; /* max. time between checks */
__le32 s_creator_os; /* OS */
__le32 s_rev_level; /* Revision level */
__le16 s_def_resuid; /* Default uid for reserved blocks */
__le16 s_def_resgid; /* Default gid for reserved blocks */
__le32 s_first_ino; /* First non-reserved inode */
__le16 s_inode_size; /* size of inode structure */
__le16 s_block_group_nr; /* block group # of this superblock */
__le32 s_feature_compat; /* compatible feature set */
__le32 s_feature_incompat; /* incompatible feature set */
__le32 s_feature_ro_compat; /* readonly-compatible feature set */
__u8 s_uuid[16]; /* 128-bit uuid for volume */
char s_volume_name[16]; /* volume name */
char s_last_mounted[64]; /* directory where last mounted */
__le32 s_algorithm_usage_bitmap; /* For compression */
__u8 s_prealloc_blocks; /* Nr of blocks to try to preallocate*/
__u8 s_prealloc_dir_blocks; /* Nr to preallocate for dirs */
__u16 s_padding1;
/*
* Journaling support valid if EXT3_FEATURE_COMPAT_HAS_JOURNAL set.
*/
__u8 s_journal_uuid[16]; /* uuid of journal superblock */
__u32 s_journal_inum; /* inode number of journal file */
__u32 s_journal_dev; /* device number of journal file */
__u32 s_last_orphan; /* start of list of inodes to delete */
__u32 s_hash_seed[4]; /* HTREE hash seed */
__u8 s_def_hash_version; /* Default hash version to use */
__u8 s_reserved_char_pad;
__u16 s_reserved_word_pad;
__le32 s_default_mount_opts;
__le32 s_first_meta_bg; /* First metablock block group */
__u32 s_reserved[190]; /* Padding to the end of the block */
};

fs.sb.png

从000000开始的1KB是启动块,由于这不是一个真正的磁盘分区,启动块的内容全部为零。从000400到0007ff的1KB是超级块,可以对照着dumpe2fs分析。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
$ dumpe2fs ./img.1m 1
dumpe2fs 1.42.9 (28-Dec-2013)
Filesystem volume name: <none>
Last mounted on: <not available>
Filesystem UUID: 2b8250d9-29fa-459e-9e2d-8b9c887b860b
Filesystem magic number: 0xEF53
Filesystem revision #: 1 (dynamic)
Filesystem features: ext_attr resize_inode dir_index filetype sparse_super
Filesystem flags: signed_directory_hash
Default mount options: user_xattr acl
Filesystem state: not clean
Errors behavior: Continue
Filesystem OS type: Linux
Inode count: 128
Block count: 1024
Reserved block count: 51
Free blocks: 986
Free inodes: 117
First block: 1
Block size: 1024
Fragment size: 1024
Reserved GDT blocks: 3
Blocks per group: 8192
Fragments per group: 8192
Inodes per group: 128
Inode blocks per group: 16
Filesystem created: Wed Oct 25 09:56:05 2017
Last mount time: Wed Oct 25 09:56:48 2017
Last write time: Wed Oct 25 09:56:48 2017
Mount count: 1
Maximum mount count: -1
Last checked: Wed Oct 25 09:56:05 2017
Check interval: 0 (<none>)
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: 2feeee23-e3de-4126-a60d-1d05a11b0ab3
...

块大小是1024字节,1MB的分区共有1024个块,第0个块是启动块,启动块之后才算ext2文件系统的开始,因此Group 0占据第1个到第1023个块,共1023个块。块位图占一个块,共有1024×8=8192个bit,足够表示这1023个块了,因此只要一个块组就够了。默认是每8KB分配一个inode,因此1MB的分区对应128个inode,这些数据都和dumpe2fs的输出吻合。

GDT(Group Descriptor Table)

由很多块组描述符组成,整个分区分成多少个块组就对应有多少个块组描述符。每个块组描述符(Group Descriptor)存储一个块组的描述信息,例如在这个块组中从哪里开始是inode表,从哪里开始是数据块,空闲的inode和数据块还有多少个等等。和超级块类似,块组描述符表在每个块组的开头也都有一份拷贝,这些信息是非常重要的,一旦超级块意外损坏就会丢失整个分区的数据,一旦块组描述符意外损坏就会丢失整个块组的数据,因此它们都有多份拷贝。通常内核只用到第0个块组中的拷贝,当执行e2fsck检查文件系统一致性时,第0个块组中的超级块和块组描述符表就会拷贝到其它块组,这样当第0个块组的开头意外损坏时就可以用其它拷贝来恢复,从而减少损失。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*
* Structure of a blocks group descriptor
*/
struct ext2_group_desc
{
__le32 bg_block_bitmap; /* Blocks bitmap block */
__le32 bg_inode_bitmap; /* Inodes bitmap block */
__le32 bg_inode_table; /* Inodes table block */
__le16 bg_free_blocks_count; /* Free blocks count */
__le16 bg_free_inodes_count; /* Free inodes count */
__le16 bg_used_dirs_count; /* Directories count */
__le16 bg_pad;
__le32 bg_reserved[3];
};

fs.gd.png

从000800开始是块组描述符表,这个文件系统较小,只有一个块组描述符,对照着dumpe2fs的输出信息分析

1
2
3
4
5
6
7
8
9
10
11
$ dumpe2fs ./img.1m 1
...
Group 0: (Blocks 1-1023)
主 superblock at 1, Group descriptors at 2-2
保留的GDT块位于 3-5
Block bitmap at 6 (+5), Inode bitmap at 7 (+6)
Inode表位于 8-23 (+7)
986 free blocks, 117 free inodes, 2 directories
可用块数: 38-1023
可用inode数: 12-128k
...

整个文件系统是1MB,每个块是1KB,应该有1024个块,除去启动块还有1023个块,分别编号为1-1023,它们全都属于Group 0。其中,Block 1是超级块,接下来的块组描述符指出,块位图是Block 6,因此中间的Block 2-5是块组描述符表,其中Block 3-5保留未用。块组描述符还指出,inode位图是Block 7,inode表是从Block 8开始的,那么inode表到哪个块结束呢?由于超级块中指出每个块组有128个inode,每个inode的大小是128字节,因此共占16个块,inode表的范围是Block 8-23。从Block 24开始就是数据块了。块组描述符中指出,空闲的数据块有986个,由于文件系统是新创建的,空闲块是连续的Block 38-1023,用掉了前面的Block 24-37

Block Bitmap

一个块组中的块是这样利用的:数据块(Data Block)存储所有文件的数据,比如某个分区的块大小是1024字节,某个文件是2049字节,那么就需要三个数据块来存,即使第三个块只存了一个字节也需要占用一个整块;超级块、块组描述符表、块位图、inode位图、inode表这几部分存储该块组的描述信息。那么如何知道哪些块已经用来存储文件数据或其它描述信息,哪些块仍然空闲可用呢?块位图就是用来描述整个块组中哪些块已用哪些块空闲的,它本身占一个块,其中的每个bit代表本块组中的一个块,这个bit为1表示该块已用,这个bit为0表示该块空闲可用。
为什么用df命令统计整个磁盘的已用空间非常快呢?因为只需要查看每个块组的块位图即可,而不需要搜遍整个分区。相反,用du命令查看一个较大目录的已用空间就非常慢,因为不可避免地要搜遍整个目录的所有文件。
与此相联系的另一个问题是:在格式化一个分区时究竟会划出多少个块组呢?主要的限制在于块位图本身必须只占一个块。用mke2fs格式化时默认块大小是1024字节,可以用-b参数指定块大小,现在设块大小指定为b字节,那么一个块可以有8b个bit,这样大小的一个块位图就可以表示8b个块的占用情况,因此一个块组最多可以有8b个块,如果整个分区有s个块,那么就可以有s/(8b)个块组。格式化时可以用-g参数指定一个块组有多少个块,但是通常不需要手动指定,mke2fs工具会计算出最优的数值。

fs_blk_bmp.png

从块位图中可以看出,前37位(前4个字节加最后一个字节的低5位)都是1,,就表示Block 1-37已用。在块位图中,Block 38-1023对应的位都是0(一直到001870那一行最后一个字节的低7位),接下来的位已经超出了文件系统的空间,不管是0还是1都没有意义。可见,块位图每个字节中的位应该按从低位到高位的顺序来看。以后随着文件系统的使用和添加删除文件,块位图中的1就变得不连续了。

Inode Bitmap

和块位图类似,本身占一个块,其中每个bit表示一个inode是否空闲可用。

fs_inode_bmp.png

块组描述符指出,空闲的inode有117个,由于文件系统是新创建的,空闲的inode也是连续的,inode编号从1到128,空闲的inode编号从12到128。从inode位图可以看出,前11位都是1,表示前11个inode已用。以后随着文件系统的使用和添加删除文件,inode位图中的1就变得不连续了。001c00这一行的128位就表示了所有inode,因此下面的行不管是0还是1都没有意义。已用的11个inode中,前10个inode是被ext2文件系统保留的,其中第2个inode是根目录,第11个inode是lost+found目录,块组描述符也指出该组有两个目录,就是根目录和lost+found。

Inode Table

一个文件除了数据需要存储之外,一些描述信息也需要存储,例如文件类型(常规、目录、符号链接等),权限,文件大小,创建/修改/访问时间等,也就是ls -l命令看到的那些信息,这些信息存在inode中而不是数据块中。每个文件都有一个inode,一个块组中的所有inode组成了inode表。
inode表占多少个块在格式化时就要决定并写入块组描述符中,mke2fs格式化工具的默认策略是一个块组有多少个8KB就分配多少个inode。由于数据块占了整个块组的绝大部分,也可以近似认为数据块有多少个8KB就分配多少个inode,换句话说,如果平均每个文件的大小是8KB,当分区存满的时候inode表会得到比较充分的利用,数据块也不浪费。如果这个分区存的都是很大的文件(比如电影),则数据块用完的时候inode会有一些浪费,如果这个分区存的都是很小的文件(比如源代码),则有可能数据块还没用完inode就已经用完了,数据块可能有很大的浪费。如果用户在格式化时能够对这个分区以后要存储的文件大小做一个预测,也可以用mke2fs的-i参数手动指定每多少个字节分配一个inode。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/*
* Structure of an inode on the disk
*/
struct ext2_inode {
__le16 i_mode; /* File mode */
__le16 i_uid; /* Low 16 bits of Owner Uid */
__le32 i_size; /* Size in bytes */
__le32 i_atime; /* Access time */
__le32 i_ctime; /* Creation time */
__le32 i_mtime; /* Modification time */
__le32 i_dtime; /* Deletion Time */
__le16 i_gid; /* Low 16 bits of Group Id */
__le16 i_links_count; /* Links count */
__le32 i_blocks; /* Blocks count */
__le32 i_flags; /* File flags */
union {
struct {
__le32 l_i_reserved1;
} linux1;
struct {
__le32 h_i_translator;
} hurd1;
struct {
__le32 m_i_reserved1;
} masix1;
} osd1; /* OS dependent 1 */
__le32 i_block[EXT2_N_BLOCKS];/* Pointers to blocks */
__le32 i_generation; /* File version (for NFS) */
__le32 i_file_acl; /* File ACL */
__le32 i_dir_acl; /* Directory ACL */
__le32 i_faddr; /* Fragment address */
union {
struct {
__u8 l_i_frag; /* Fragment number */
__u8 l_i_fsize; /* Fragment size */
__u16 i_pad1;
__le16 l_i_uid_high; /* these 2 fields */
__le16 l_i_gid_high; /* were reserved2[0] */
__u32 l_i_reserved2;
} linux2;
struct {
__u8 h_i_frag; /* Fragment number */
__u8 h_i_fsize; /* Fragment size */
__le16 h_i_mode_high;
__le16 h_i_uid_high;
__le16 h_i_gid_high;
__le32 h_i_author;
} hurd2;
struct {
__u8 m_i_frag; /* Fragment number */
__u8 m_i_fsize; /* Fragment size */
__u16 m_pad1;
__u32 m_i_reserved2[2];
} masix2;
} osd2; /* OS dependent 2 */
};

根目录inode信息:
fs.rootinode.png

st_mode以八进制表示,包含了文件类型和文件权限,最高位的4表示文件类型为目录(各种文件类型的编码详见stat(2)),低位的755表示权限。Size是1024,说明根目录现在只有一个数据块。Links为3表示根目录有三个硬链接,分别是根目录下的.和..,以及lost+found子目录下的..。注意,虽然我们通常用/表示根目录,但是并没有名为/的硬链接,事实上,/是路径分隔符,不能在文件名中出现。这里的Blockcount是以512字节为一个块来数的,并非格式化文件系统时所指定的块大小,磁盘的最小读写单位称为扇区(Sector),通常是512字节,所以Blockcount是磁盘的物理块数量,而非分区的逻辑块数量。根目录数据块的位置由上图中的Blocks[0]指出,也就是第24个块,它在文件系统中的位置是24×0x400=0x6000

探索文件系统还有一个很有用的工具debugfs,它提供一个命令行界面,可以对文件系统做各种操作,例如查看信息、恢复数据、修正文件系统中的错误。使用debugfs ./img.1m打开文件系统,使用stat /命令查看根目录inode信息

1
2
3
4
5
6
7
8
9
10
11
12
Inode: 2 Type: directory Mode: 0755 Flags: 0x0
Generation: 0 Version: 0x00000000
User: 0 Group: 0 Size: 1024
File ACL: 0 Directory ACL: 0
Links: 3 Blockcount: 2
Fragment: Address: 0 Number: 0 Size: 0
ctime: 0x59efef35 -- Wed Oct 25 09:56:05 2017
atime: 0x59efef63 -- Wed Oct 25 09:56:51 2017
mtime: 0x59efef35 -- Wed Oct 25 09:56:05 2017
BLOCKS:
(0):24
TOTAL: 1

数据块寻址

通过__le32 i_block[EXT2_N_BLOCKS]来完成数据块的寻址。

1
2
3
4
5
6
7
8
/*
* Constants relative to the data blocks
*/
#define EXT2_NDIR_BLOCKS 12
#define EXT2_IND_BLOCK EXT2_NDIR_BLOCKS
#define EXT2_DIND_BLOCK (EXT2_IND_BLOCK + 1)
#define EXT2_TIND_BLOCK (EXT2_DIND_BLOCK + 1)
#define EXT2_N_BLOCKS (EXT2_TIND_BLOCK + 1)
  • EXT2_NDIR_BLOCKS
    i_block前12项属于直接寻址,直接存储数据块的”block id”。所以总共可记录 12 笔记录,总额大小为12*1k=12k
  • EXT2_IND_BLOCK
    i_block第13项为一级间接寻址,每笔 block 号码的记录会花去 4bytes,因此 1K 的大小能够记录 256 笔记录,因此一个间接可以记录的文件大小为(1k/4)*1K=256k
  • EXT2_DIND_BLOCK
    i_block第14项为二级间接寻址,第一层 block 会指定 256 个第二层,每个第二层可以指定 256 个号码,因此总额大小为2562561k
  • EXT2_TIND_BLOCK
    i_block第15项为三级间接寻址,第一层 block 会指定 256 个第二层,每个第二层可以指定 256 个第三层,每个第三层可以指定 256 个号码,因此总额大小为256256256*1k

总容量为直接寻址+一级间接+二级间接+三级间接=16.06GB

fs.datablockaddr.png

Blocks

  • 对于常规文件,文件的数据存储在数据块中。
  • 对于目录,该目录下的所有文件名和目录名存储在数据块中,注意文件名保存在它所在目录的数据块中,除文件名之外,ls -l命令看到的其它信息都保存在该文件的inode中。注意这个概念:目录也是一种文件,是一种特殊类型的文件。
  • 对于符号链接,如果目标路径名较短则直接保存在inode中以便更快地查找,如果目标路径名较长则分配一个数据块来保存。
  • 设备文件、FIFO和socket等特殊文件没有数据块,设备文件的主设备号和次设备号保存在inode中。

根目录的数据结构

1
2
3
4
5
6
7
struct ext2_dir_entry_2 {
__le32 inode; /* Inode number */
__le16 rec_len; /* Directory entry length */
__u8 name_len; /* Name length */
__u8 file_type;
char name[]; /* File name, up to EXT2_NAME_LEN */
};

根目录的数据块
fs.datablock.png

根据上文中根目录inode信息找到根目录数据块006000地址,目录的数据块由许多不定长的记录组成,每条记录描述该目录下的一个文件,在上图中用框表示。第一条记录描述inode号为2的文件,也就是根目录本身,该记录的总长度为12字节,其中文件名的长度为1字节,文件类型为2(见下表,注意此处的文件类型编码和st_mode不一致),文件名是.。第二条记录也是描述inode号为2的文件(根目录),该记录总长度为12字节,其中文件名的长度为2字节,文件类型为2,文件名字符串是..。第三条记录一直延续到该数据块的末尾,描述inode号为11的文件(lost+found目录),该记录的总长度为1000字节(和前面两条记录加起来是1024字节),文件类型为2,文件名字符串是lost+found,后面全是0字节。如果要在根目录下创建新的文件,可以把第三条记录截短,在原来的0字节处创建新的记录。如果该目录下的文件名太多,一个数据块不够用,则会分配新的数据块,块编号会填充到inode的Blocks[1]字段。

编码 文件类型(file type)
0 Unknown
1 Regular File
2 Directory
3 Character device
4 Block device
5 Named pipe
6 Socket
7 Symbolic link

参考&鸣谢