Internal Layout
Ext2文件系统内部布局
Dave Poirier
instinc@users.sf.net
翻译：Vitamin C[抗坏血酸]
sing9806@sohu.com
sing9806@yahoo.com.cn
Copyright © 2001-2002 by Dave Poirier
Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.1 or any later version published by the Free Software Foundation; with no Invariant Sections, with no Front-Cover Texts, and with no Back-Cover Texts. A copy of the license can be acquired electronically from http://www.fsf.org/licenses/fdl.html or by writing to 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
（这是原文关于版权的说明，予原样保留。）
内容目录
关于本书
1. 磁盘组织
1.1. 超级块
1.1.1. s_inodes_count
1.1.2. s_blocks_count
1.1.3. s_r_blocks_count
1.1.4. s_free_blocks_count
1.1.5. s_free_inodes_count
1.1.6. s_first_data_block
1.1.7. s_log_block_size
1.1.8. s_log_frag_size
1.1.9. s_blocks_per_group
1.1.10. s_frags_per_group
1.1.11. s_inodes_per_group
1.1.12. s_mtime
1.1.13. s_wtime
1.1.14. s_mnt_count
1.1.15. s_max_mnt_count
1.1.16. s_magic
1.1.17. s_state
1.1.18. s_errors
1.1.19. s_minor_rev_level
1.1.20. s_lastcheck
1.1.21. s_checkinterval
1.1.22. s_creator_os
1.1.23. s_rev_level
1.1.24. s_def_resuid
1.1.25. s_def_resgid
1.1.26. s_first_ino
1.1.27. s_inode_size
1.1.28. s_block_group_nr
1.1.29. s_feature_compat
1.1.30. s_feature_incompat
1.1.31. s_feature_ro_compat
1.1.32. s_uuid
1.1.33. s_volume_name
1.1.34. s_last_mounted
1.1.35. s_algo_bitmap
1.2. 块组描述符
1.2.1. bg_block_bitmap
1.2.2. bg_inode_bitmap
1.2.3. bg_inode_table
1.2.4. bg_free_blocks_count
1.2.5. bg_free_inodes_count
1.2.6. bg_used_dirs_count
1.2.7. bg_pad
1.2.8. bg_reserved
1.3. 块位图
1.4. Inode 位图
1.5. Inode 表
1.5.1. i_mode
1.5.2. i_uid
1.5.3. i_size
1.5.4. i_atime
1.5.5. i_ctime
1.5.6. i_mtime
1.5.7. i_dtime
1.5.8. i_gid
1.5.9. i_links_count
1.5.10. i_blocks
1.5.11. i_flags
1.5.12. i_osd1
1.5.13. i_block
1.5.14. i_generation
1.5.15. i_file_acl
1.5.16. i_dir_acl
1.5.17. i_faddr
1.5.18. i_osd2
1.6. 数据块
2. 目录结构
2.1. 目录文件格式
2.1.1. inode
2.1.2. rec_len
2.1.3. name_len
2.1.4. file_type
2.1.5.name
2.2. 目录例子
2.3. 索引目录格式
2.3.1. 索引结构
2.3.2. 查找算法
2.3.3. 插入算法
2.3.4. 分解
2.3.5. Key 冲突
2.3.6. Hash 功能
2.3.7. 性能
3. Inode, 文件的标识符
3.1. Inode 编号
3.2. 定位Inode 结构
3.3. 定位Inode 表
4. 文件属性
4.1. 标准属性
4.1.1. SUID, SGID 和 -rwxrwxrwx
4.1.2. 文件大小
4.1.3. 属主与属组
4.2. 扩展属性
4.2.1. 属性块头部
4.2.2. 属性入口头部
4.3. 行为控制标记
4.3.1. EXT2_SECRM_FL - 安全删除
4.3.2. EXT2_UNRM_FL - 用于反删除的记录
4.3.3. EXT2_COMPR_FL - 压缩的文件
4.3.4. EXT2_SYNC_FL - 同步更新
4.3.5. EXT2_IMMUTABLE_FL - 不可变文件
4.3.6. EXT2_APPEND_FL - 只添加
4.3.7. EXT2_NODUMP_FL - 不可 Dump/删除
4.3.8. EXT2_NOATIME_FL - 不更新 .i_atime
4.3.9. EXT2_DIRTY_FL - 脏的
4.3.10. EXT2_COMPRBLK_FL - 压缩的块
4.3.11. EXT2_NOCOMPR_FL -Raw方式访问压缩的数据
4.3.12. EXT2_ECOMPR_FL - 压缩错误
4.3.13. EXT2_BTREE_FL - B-Tree 格式目录
4.3.14. EXT2_INDEX_FL - Hash 索引的目录
4.3.15. EXT2_IMAGIC_FL -
4.3.16. EXT2_JOURNAL_DATA_FL - 日志文件数据
4.3.17. EXT2_RESERVED_FL - 保留
A. 鸣谢
B．译者后记
表格列表
1-1. EXT2_ERRORS 值
1-2. EXT2_OS 值
1-3. EXT2 修订版本
1-4. EXT2_*_INO值
1-5. EXT2_S_I值
2-1. EXT2_FT值
4-1. 行为控制标记
图片列表
1-1. 磁盘的元数据布局
1-2. 20mb 分区元数据布局
1-3. 超级块结构
1-4. group_desc 结构
1-5. inode 结构
1-6. inode osd2 结构: Hurd
1-7. inode osd2 结构: Linux
1-8. inode osd2 结构: Masix
2-1. 目录入口
2-2. 目录数据布局例子
2-3. 索引目录的性能
3-1. inode计算例子
4-1. ext2_xattr_header 结构
4-2. ext2_xattr_header 结构
关于本书
本书的最新版本下载的URL：http://www.freesoftware.fsf.org/ext2-doc/
本书的目的在于提供关于The Second Extended File System即Ext2文件系统的入门指南。本书假定熟悉关于文件系统的相关概念（如：文件，目录，分区等等）。
实现ext2的驱动程序并非一件易事，其最大的困难正好就是相关文档资料的缺乏。而目前网上所有关于ext2内部布局的文档资料只不过是作为Linux sourcesr的补充，并没有完整的关于ext2内部布局的文档资料。
本文档资料的目的正是为解决此问题而生，希望它能对有此需要的人有所帮助。
Unless otherwise stated, all values are stored in little endian byte order.
Chapter 1. 磁盘组织
在使用The Second Extended File System首先要明确的是所有的元数据结构的大小均基于“块（block）”而不是“扇区（sector）”。块的大小是可变的，依赖于文件系统的大小。例如在一个软盘块的大小为1KB（2个扇区），而在一个10G的分区里块的大小通常为4KB或8KB（分别为8或16个扇区）。
每一个块可以进一步划分为“段（fragments）”，但我见过一个段的大小与块的大小不相匹配的文件系统。尽管常识告诉我段与块不相匹配是不合理的。
除了超级块（superblock）外，所有的元数据结构都以块为基准调整大小。这里有一点要注意，在安装任何其它的文件系统到软盘上时，inode表块（Inode Tabel Block）在块大小为4KB比在块大小为1KB的文件系统里可以容纳更多的入口，这是当访问这样的一个特殊的结构时需要注意的。
下步要明确的是文件系统还划分了“块组（block groups）”。在一张软盘里只使用一个块组包含文件系统里所有的块，但在一个10G的硬盘分区里将划分30个这样的包含有一定数量块的块组。
在每个块组的开始有多种多样的元数据结构描述彼此的位置，更重要的是，元数据结构定义了当前文件系统的状态。下面是在一张软盘的ext2文件系统的磁盘组织：
Figure 1-1. 软盘的元数据布局
offset # of blocks description
偏移 块号 描述
-------- ----------- -----------
0 1 boot record 引导记录
-- block group 0 -
块组 0
(1024 bytes) 1 superblock 超级块
2 1 group descriptors 块组描述符
3 1 block bitmap 块位图
4 1 inode bitmap inode位图
5 23 inode table inode 表
28 1412 data blocks 数据块
下面是一个20MB ext2文件系统的磁盘组织：
Figure 1-2. 20mb 分区元数据布局
offset # of blocks description
-------- ----------- -----------
0 1 boot record
-- block group 0 --
(1024 bytes) 1 superblock
2 1 group descriptors
3 1 block bitmap
4 1 inode bitmap
5 214 inode table
219 7974 data blocks
-- block group 1 --
8193 1 superblock backup
8194 1 group descriptors backup
8195 1 block bitmap
8196 1 inode bitmap
8197 214 inode table
8408 7974 data blocks
-- block group 2 --
16385 1 block bitmap
16386 1 inode bitmap
16387 214 inode table
16601 3879 data blocks
只要你了解磁盘基本的信息，磁盘的布局是可以预知的；块的大小，每个块组包含多少块，每个块组的inode数等这些信息是可以在超级块结构里找到或通过计算得到的。
没有超级块的信息，磁盘将不可用；所以只要磁盘上的空间允许，在磁盘上将有一个或多个超级块的备份。
块位图与inode位图用于识别哪些块和哪些inode入口是可用的。各种各样的文件将保存在数据块里。注意：在ext2里目录也被视为文件，在下面我们将详细对此进行描述。
为兼容不同的ext2实现，在不同结构里的一些因为特定的操作系统而有所差别的字段，将在适当的时候给予简要的说明。
1.1. 超级块
超级块这个结构里包含了磁盘里ext2 文件系统属性里最基本的信息。它的布局如下：
Figure 1-3. 超级块结构
offset size description
偏移 大小 描述
------- ------- -----------
0 4 s_inodes_count
4 4 s_blocks_count
8 4 s_r_blocks_count
12 4 s_free_blocks_count
16 4 s_free_inodes_count
20 4 s_first_data_block
24 4 s_log_block_size
28 4 s_log_frag_size
32 4 s_blocks_per_group
36 4 s_frags_per_group
40 4 s_inodes_per_group
44 4 s_mtime
48 4 s_wtime
52 2 s_mnt_count
54 2 s_max_mnt_count
56 2 s_magic
58 2 s_state
60 2 s_errors
62 2 s_minor_rev_level
64 4 s_lastcheck
68 4 s_checkinterval
72 4 s_creator_os
76 4 s_rev_level
80 2 s_def_resuid
82 2 s_def_resgid
-- EXT2_DYNAMIC_REV Specific --
84 4 s_first_ino
88 2 s_inode_size
90 2 s_block_group_nr
92 4 s_feature_compat
96 4 s_feature_incompat
100 4 s_feature_ro_compat
104 16 s_uuid
120 16 s_volume_name
136 64 s_last_mounted
200 4 s_algo_bitmap
-- Performance Hints --
204 1 s_prealloc_blocks
205 1 s_prealloc_dir_blocks
206 2 - (alignment)
-- Journaling Support --
208 16 s_journal_uuid
224 4 s_journal_inum
228 4 s_journal_dev
232 4 s_last_orphan
-- Unused --
236 788 - (padding)
1.1.1. s_inodes_count
32bit的值表示所有inode总数，包括文件系统里已用和未用的。
1.1.2. s_blocks_count
32bit的值表示块的总数，包括文件系统里已用和未用的。
1.1.3. s_r_blocks_count
32bit的值表示为超级用户保留的块的总数。这是非常有用的：当某个用户有意或无意用数据充满了整个文件系统的空间时，超级用户可以用这些保留的只有超级用户可用的空间来保存或编辑配置文件来解决相关问题。
1.1.4. s_free_blocks_count
32bit的值表示未用的块的总数，包括保留的块（查看s_r_blocks_count）。这是所有块组里的所有未用的块的总数。
1.1.5. s_free_inodes_count
32bit的值表示未用的inode的总数。这是所有块组里的所有未用的inode的总数。
1.1.6. s_first_data_block
32bit的值识别每一个数据块，也就是包含超级块结构的块ID。
注意：这个值在块大小大于1KB的文件系统里总是0，而在块大小为1KB的文件系统里总是1。因为超级块总是在磁盘的第1024个字节开始的，也就正好是第三个扇区的第一个字节。
1.1.7. s_log_block_size
块的大小用值1024算术左移以此值为位数而得。这个值是一定正值。
block size = 1024 << s_log_block_size;
1.1.8. s_log_frag_size
段的大小用值1024算术左移以此值为位数而得。注意：若此值为负值则算术右移。
if( positive )
fragment size = 1024 << s_log_frag_size;
else
fragment size = 1024 >> -s_log_frag_size;
1.1.9. s_blocks_per_group
32bit的值表示每块组里块的总数。这个值与s_first_data_block联合决定块组的边界。
1.1.10. s_frags_per_group
32bit的值表示每块组段的总数。它也用于决定每个块组里块位图的大小。
1.1.11. s_inodes_per_group
32bit的值表示每块组inode的总数。也用于决定每块组里inode位图的大小。
1.1.12. s_mtime
Unix时间，在POSIX定义，文件系统最近被安装的时间。
1.1.13. s_wtime
Unix时间，在POSIX定义，文件系统最近被访问的时间。
1.1.14. s_mnt_count
32bit的值表示文件系统从最近一次完整校验后被安装的次数。
1.1.15. s_max_mnt_count
32bit的值表示在被完整校验前文件系统还可以被安装的最大次数。
1.1.16. s_magic
16bit的值用于识别文件系统为ext2。此值通常固定为0xEF53。
1.1.17. s_state
16bit的值表示文件系统的状态。当文件系统被安装，此状态被设EXT2_ERROR_FS。当文件系统没有被安装，此值是EXT2_VALID_FS 或在文件系统没有被正确卸载时为EXT2_ERROR_FS。
1.1.18. s_errors
16bit的值表示当文件系统发现错误时文件系统驱动程序将如何做。其值如下：
Table 1-1. EXT2_ERRORS 值
EXT2_ERRORS_CONTINUE 1 继续，犹如没有错误
EXT2_ERRORS_RO 2 重新安装为只读模式
EXT2_ERRORS_PANIC 3 引起一个内核应急
EXT2_ERRORS_DEFAULT 变化 在0.5版本里，此值等同于EXT2_ERRORS_CONTINUE
1.1.19. s_minor_rev_level
16bit的值在revision level里识别局部修订级别。
1.1.20. s_lastcheck
Unix时间，在POSIX定义，文件系统最近检查的时间。
1.1.21. s_checkinterval
最大的Unix时间间隔，在POSIX定义，文件系统最近检查的最大间隔时间。
1.1.22. s_creator_os
32bit识别生成文件系统的操作系统。定义如下：
Table 1-2. EXT2_OS 值
EXT2_OS_LINUX 0 Linux
EXT2_OS_HURD 1 Hurd
EXT2_OS_MASIX 2 MASIX
EXT2_OS_FREEBSD 3 FreeBSD
EXT2_OS_LITES4 4 Lites
1.1.23. s_rev_level
32bit修订级别值。目前有2个值被定义：
Table 1-3. EXT2 修订
EXT2_GOOD_OLD_REV 0 原始的格式
EXT2_DYNAMIC_REV 1 使用动态inode大小的V2格式
1.1.24. s_def_resuid
16bit值用于定义保留块的默认用户ID。
1.1.25. s_def_resgid
16bit值用于定义保留块的默认组ID。
1.1.26. s_first_ino
32bit值作为标准文件的第一个可用inode的索引。在非动态文件系统修订版本里，每一个非保留inode固定为11。在引入动态文件系统修订版本里这个值是可变的。
1.1.27. s_inode_size
16bit值表示inode结构的大小。在非动态文件系统修订版本里这个值是128。
1.1.28. s_block_group_nr
16bit值表示保存有此超级块的块组号。可以用此值找到超级块备份来重建文件系统。
1.1.29. s_feature_compat
兼容特性的32bit位掩码。文件系统实现里不一定都支持，但对结元数据无影响。（以后对此将有更多的信息加入）
1.1.30. s_feature_incompat
不兼容特性的32bit位掩码。如果缺少某些需要的特性支持，文件系统实现将拒绝安装此文件系统。（以后对此将有更多的信息加入）
1.1.31. s_feature_ro_compat
“只读”特性的32bit位掩码。如果缺少某些需要的特性支持，文件系统实现将以只读模式安装此文件系统。（以后对此将有更多的信息加入）
1.1.32. s_uuid
128bit值用于描述卷ID。应该尽可能每个文件系统格式有唯一的值。
1.1.33. s_volume_name
16bit卷名，大多数没用。有效的卷名只能由ISO-Latin-1字符组成，以0结束。
1.1.34. s_last_mounted
64bytes表示文件系统最近被安装的目录路径。一般不用，它可以在命令行下不指定安装目录路径时自动查找安装点。因为兼容性目录路径以0结束。有效的目录路径由ISO-Latin-1字符组成。
1.1.35. s_algo_bitmap
32bit值用于压缩算法决定使用何种压缩方式。（对于此字段我没有更多的理解，如果你对此字段熟悉可以将你知道的信息发送给我，谢谢）。
1.2. 块组描述符
块组描述符（Goup Descriptors）是一组group_desc结构，每一组描述一个“块组”，给出块组的inode表，块和inode位图的位置及其它一些有用的信息。
块组描述符紧接于超级块结构所在块的后面第一个块。这里有一个块组描述符的例子：
Figure 1-4. group_desc 结构
offset size description
------- ------- -----------
0 4 bg_block_bitmap
4 4 bg_inode_bitmap
8 4 bg_inode_table
12 2 bg_free_blocks_count
14 2 bg_free_inodes_count
16 2 bg_used_dirs_count
18 2 bg_pad
20 12 bg_reserved
在文件系统里每一个块组都建立有group_desc这样的结构。在文件系统里每个这样的结构描述一个单一的“块组”，而每个这样的结构只描述它所在的块组的相关信息。每个“块组描述符表（Group Descriptor Table）”包含所有块组的所有信息。
所有可用的“块ID”是唯一的。
1.2.1. bg_block_bitmap
32bit值为当前块组指出“块位图”的第一个块的块ID。
1.2.2. bg_inode_bitmap
32bit值为当前块组指出“inode位图”的第一个块的块ID。
1.2.3. bg_inode_table
32bit值为当前块组指出“inode表”的第一个块的块ID。
1.2.4. bg_free_blocks_count
16bit值表示当前块组未用的块的总数。
1.2.5. bg_free_inodes_count
16bit值表示当前块组未用的块的总数。
1.2.6. bg_used_dirs_count
16bit值表示当前块组分配给目录的inode 数。
1.2.7. bg_pad
16bit用于填充结构的32bit边界。
1.2.8. bg_reserved
3个连续的32bit值为将来的实现保留。
1.3. 块位图
“块位图”通常位于块组的每一个块，若存在备份超级块则在每二个块。它的实际位置可以通过在块组描述符里的“bg_block_bitmap”得知。
每一位指出在该块组内的所对应块的当前状态，其中1表示“已用”和0表示“未用”。在该块组里的每一个块被字节0的第0位标记，每二个块被字节0的每1位标记。第8个块则对应字节0的第7位而每9个块就对应字节1里的第0位。以此类推。
1.4. Inode 位图
Inode位图的作用类同于“块位图”，不同的是每一个位对应“inode表”里的一个inode而不是块。
每一个块组有一个inode位图，它的位置可以通过块组描述符里的“bg_inode_bitmap”得知。
当inode表被建立时，所有的保留inode被标记为已用。在“Good Old修订版本”里对应inode位图里的前11位。
1.5. Inode 表
Inode表用于跟踪定位每个文件；文件的位置，大小，类型和访问权限均保存在inode。然而文件名并不保存在inode里，在inode表里，是依赖文件的inode号来管理所有的文件的。
一个块组只有一个inode表且此表可以通过相关的块组描述符里的“bg_inode_table” 得知。一个表共有s_inodes_per_group个inode。
每个inode包含关于在系统里单个物理文件的信息。一个文件可以是一个目录，一个套接字，一个缓冲区，一个字符或者是块设备，符号连接或一个正常文件。所以，一个inode可以看作是与一个实体相关的信息块，描述它在磁盘的位置、大小、属主。一个inode如下：
Figure 1-5. inode 结构
offset size description
------- ------- -----------
0 2 i_mode
2 2 i_uid
4 4 i_size
8 4 i_atime
12 4 i_ctime
16 4 i_mtime
20 4 i_dtime
24 2 i_gid
26 2 i_links_count
28 4 i_blocks
32 4 i_flags
36 4 i_osd1
40 15 x 4 i_block
100 4 i_generation
104 4 i_file_acl
108 4 i_dir_acl
112 4 i_faddr
116 12 i_osd2
Inode表的前面几个入口是保留的。在EXT2_GOOD_OLD_REV保留了11个入口，而在较新的EXT2_DYNAMIC_REV里保留的入口数量在超级块结构里的s_first_ino指出。下面是已知的保留inode入口的列表：
Table 1-4. EXT2_*_INO 值
EXT2_BAD_INO 0x01 坏块inode
EXT2_ROOT_INO 0x02 根目录inode
EXT2_ACL_IDX_INO 0x03 ACL 索引inode (抗议?)
EXT2_ACL_DATA_INO 0x04 ACL 数据 inode (抗议?)
EXT2_BOOT_LOADER_INO 0x05 引导程序inode
EXT2_UNDEL_DIR_INO 0x06 反删除目录inode
1.5.1. i_mode
16bit值指出文件格式和访问权限。这里有可能的值，且可以与不同方式组合起来：
Table 1-5. EXT2_S_I 值
-- 文件格式 --
EXT2_S_IFMT 0xF000 格式掩码
EXT2_S_IFSOCK 0xC000 套接字
EXT2_S_IFLNK 0xA000 符号连接
EXT2_S_IFREG 0x8000 正常文件
EXT2_S_IFBLK 0x6000 块设备
EXT2_S_IFDIR 0x4000 目录
EXT2_S_IFCHR 0x2000 字符设备
EXT2_S_IFIFO 0x1000 fifo
-- 访问权限 --
EXT2_S_ISUID 0x0800 SUID
EXT2_S_ISGID 0x0400 SGID
EXT2_S_ISVTX 0x0200 粘着位
EXT2_S_IRWXU 0x01C0 用户访问权限掩码
EXT2_S_IRUSR 0x0100 读
EXT2_S_IWUSR 0x0080 写
EXT2_S_IXUSR 0x0040 执行
EXT2_S_IRWXG 0x0038 组访问权限掩码
EXT2_S_IRGRP 0x0020 读
EXT2_S_IWGRP 0x0010 写
EXT2_S_IXGRP 0x0008 执行
EXT2_S_IRWXO 0x0007 其他用户访问权限
EXT2_S_IROTH 0x0004 读
EXT2_S_IWOTH 0x0002 写
EXT2_S_IXOTH 0x0001 执行
1.5.2. i_uid
16bit文件相关联的用户ID。
1.5.3. i_size
32bit值表示文件的大小（以字节为单位）。
1.5.4. i_atime
32bit值指出文件最近被访问的时间距离1970年1月1日的秒数。
1.5.5. i_ctime
32bit值指出文件建立的时间距离1970年1月1日的秒数。
1.5.6. i_mtime
32bit值指出文件被修改的时间距离1970年1月1日的秒数。
1.5.7. i_dtime
32bit值指出文件被删除的时间距离1970年1月1日的秒数。这很重要，这个值总是0，除非文件被删除。
1.5.8. i_gid
16bit值指出组曾经访问过此文件。
1.5.9. i_links_count
16bit值表示此inode被连接的次数。
1.5.10. i_blocks
32bit值表示与此文件数据关联的保留块的个数。包括当前已经使用了的和当前为满足文件增大所需要的。
需要指出：此值表示大小为512bytes的块的个数而不是在超级块里指定大小的块的个数。所以若一个文件系统的块的大小是1024bytes，它的.i_blocks的值是2。
1.5.11. i_flags
32bit值表示当在此inode访问数据时ext2该如何实现。（详细查看行为标记部分。）
1.5.12. i_osd1
32bit操作系统依赖的值。
1.5.12.1. Hurd
32bit的“翻译者”标签。
1.5.12.2. Linux
32bit目前保留。
1.5.12.3. Masix
32bit目前保留。
1.5.13. i_block
用于定位存贮正常文件的块的数组。每一个入口是一个32bit的块编号。在此数组的前12个入口是块号，可直接用于定位存贮此文件的前12个块。
第13个入口是一级间接块号。此块号指向另一个包含有存贮这个文件其它块编号的块。即第13个入口给出的块是用于存贮此文件的块号，这些块号可直接定位存贮此文件的块。
每14个入口是一个二级间接块号。块号指向一个特殊的数据块，此数据块存贮一个间接块号数组，通过这些数组的间接块号可以找到存贮直接定位存贮此文件块号的块（就是类似于第13个入口所指向的块）。
每15个入口是一个三级间接块号。它是一个指向一个存贮二级间接块号数组的块，等等。
每个一级间接/二级间接/三级间接块数组如果文件足够大均包含有同样数量的32bit块号的入口（充满整个块）。
译者：对i_block的理解很重要。它们的关系的如下图：
1.5.14. i_generation
32bit值用于表示文件版本（用于NFS）。
1.5.15. i_file_acl
32bit值用于表示包含扩展属性的块号。在以前的修订版本其值总是0。
关于ACL for Digital UNIX的全面的描述可以访问：
http://www.tru64unix.compaq.com/ ... 1_html/sec.c27.html
1.5.16. i_dir_acl
32bit值用于表示文件的“High Size”。 在以前的修订版本其值总是0。
1.5.17. i_faddr
32bit值用于表示文件最后一个段的位置。
1.5.18. i_osd2
96bit操作系统依赖的结构。
1.5.18.1. Hurd
Figure 1-6. inode osd2 结构: Hurd
offset size description
------- ------- -----------
0 1 h_i_frag
1 1 h_i_fsize
2 2 h_i_mode_high
4 2 h_i_uid_high
6 2 h_i_gid_high
8 4 h_i_author
1.5.18.1.1. h_i_frag
8bit段号。
1.5.18.1.2. h_i_fsize
8bit段大小。
1.5.18.1.3. h_i_mode_high
1.5.18.1.4. h_i_uid_high
用户ID的高16bit。
1.5.18.1.5. h_i_gid_high
组ID的高16bit。
1.5.18.1.6. h_i_author
1.5.18.2. Linux
Figure 1-7. inode osd2 结构: Linux
offset size description
------- ------- -----------
0 1 l_i_frag
1 1 l_i_fsize
2 2 reserved
4 2 l_i_uid_high
6 2 l_i_gid_high
8 4 reserved
1.5.18.2.1. l_i_frag
8bit段号。
1.5.18.2.2. l_i_fsize
8bit段大小。
1.5.18.2.3. l_i_uid_high
用户ID的高16bit。
1.5.18.2.4. l_i_gid_high
组ID的高16bit。
1.5.18.3. Masix
Figure 1-8. inode osd2 结构: Masix
offset size description
------- ------- -----------
0 1 m_i_frag
1 1 m_i_fsize
2 10 reserved
1.5.18.3.1. m_i_frag
8bit段号。
1.5.18.3.2. m_i_fsize
8bit段大小。
1.6. 数据块
数据块用于存贮大量的文件的内容，包括目录表，扩展属性，符号连接，等等。
Chapter 2. 目录结构
目录是作为文件存贮的。它在ext2_inode.i_mode里表示EXT2_S_IFDIR值的文件格式位里确定。
其中根目录总是在inode表的每二个入口（EXT2_ROOT_INO的值是2）。其它的子录可以在根目录文件的内容里定位。
2.1. 目录文件格式
Figure 2-1. 目录入口
offset size description
------- ------- -----------
0 4 inode
4 2 rec_len
6 1 name_len
7 1 file_type
8 ... name
在早期的Ext2实现里name_len是16bit的值，但自从此值存贮在Intel(little-endian)字节命令和在大多数Ext2实现的文件名受到255字符的限制时，允许一个字节用于重复利用。
2.1.1. inode
32bit文件入口的inode号。如果值为0表示此入口未用。
2.1.2. rec_len
16bit无符号值表示从当前目录入口到下一个目录入口的偏移。
2.1.3. name_len
8bit无符号值表示文件名包含的字符数。
2.1.4. file_type
8bit无符号值表示文件类型。在早期的实现里这些值为0。当前这些值的定义为：
Table 2-1. EXT2_FT 值
EXT2_FT_UNKNOWN 0 未知
EXT2_FT_REG_FILE 1 正常文件
EXT2_FT_DIR 2 目录
EXT2_FT_CHRDEV 3 字符设备
EXT2_FT_BLKDEV 4 块设备
EXT2_FT_FIFO 5 FIFO
EXT2_FT_SOCK 6 套接字
EXT2_FT_SYMLINK 7 符号连接
EXT2_FT_MAX 8 MAX
2.1.5. name
入口名称（文件名）。使用ISO-Latin-1字符。
2.2. 目录例子
这里是一个我系统里的一用户Home目录的例子：
$ ls -1a /home/eks
.
..
.bash_profile
.bashrc
mbox
public_html
tmp
下面列出的数据可以在存贮设备里找到：
Figure 2-2. 目录例子数据布局
offset size description
------- ------- -----------
0 4 inode number (783362) inode号
4 2 record length (9) 记录长度
6 1 name length (1) 文件名长度
7 1 file type (EXT2_FT_DIR) 文件类型
8 1 name (.) 文件名
9 4 inode number (1109761)
13 2 record length (10)
15 1 name length (2)
16 1 file type (EXT2_FT_DIR)
17 2 name (..)
19 4 inode number (783364)
23 2 record length (21)
25 1 name length (13)
26 1 file type (EXT2_FT_REG_FILE)
27 13 name (.bash_profile)
40 4 inode number (783363)
44 2 record length (15)
46 1 name length (7)
47 1 file type (EXT2_FT_REG_FILE)
48 7 name (.bashrc)
55 4 inode number (783377)
59 2 record length (12)
61 1 name length (4)
62 1 file type (EXT2_FT_REG_FILE)
63 4 name (mbox)
67 4 inode number (783545)
71 2 record length (19)
73 1 name length (11)
74 1 file type (EXT2_FT_DIR)
75 11 name (public_html)
86 4 inode number (669354)
90 2 record length (11)
92 1 name length (3)
93 1 file type (EXT2_FT_DIR)
94 3 name (tmp)
97 4 inode number (0)
101 2 record length (3999)
103 1 name length (0)
104 1 file type (EXT2_FT_UNKNOWN)
105 0 name ()
需要注意：在一些实现里，为在主处理器上获得更好的性能将在目录入口进行填充，重要的是将使用记录长度而不使用文件名长度来查找下一条记录。
2.3. 索引目录格式
为提高文件系统的性能，建立一个Hash索引，可快速定位需要的文件。
在behaviour control flags里的EXT2_INDEX_FL位将被设置，如果使用索引目录格式时。
2.3.1. 索引结构
根目录的索引树在文件的第0块。为索引树的第二层保留了1到511个块（在4K/块的文件系统）。目录的叶块添加于第512块开始处，因此文件的尾部看起来就像一个正常的Ext2目录并可以直接被ext2_readdir处理。如果目录数小于90K个文件时在第1块到第511块里将有一片空白区，所以一个空的目录只有2个块，尽管它在目录列表里看起来大小是2M。
所以一个目录文件如下：
0: Root index block
1: Index block/0
2: Index block/0
...
511: Index block/0
512: Dirent block
513: Dirent block
...
每个索引块包含如下结构的512个索引入口：
hash, block
Hash是将任意长度的一块数据转换为一个定长的、不可逆转的、唯一的32bit数据，而块是一个叶块的索引的逻辑块号，依赖于树的层次。
第0个索引入口的hash值是不需要的，因为它总是可以在层次里获得，因此它用于记录在一个索引块里索引入口的数量。这里给出了一个很好的分支因子(Branching Factor)：512，这样使查找有规则性获得的好处多于因此获得的性能上的改善。（另一方面，巨大的分支因子能获得更好的性能。）
根索引块具有和其它索引块一样的格式，其中前8个字节为头部而保留。
1byte头长度（默认：8）
1byte索引类型（默认：0）
1byte hash版本（默认：0）
1byte树深度（默认：1）
在不同的补丁里对头部的处理有些许不同。通常，实现里只有一个单一的索引树（根）。已经证明这样已足够处理大约90，000个入口，在目前来说是足够的。当在树里加入第二层时可以处理的入口数量为50,000,000个入口，可以看出目前没有必要使用N层索引，必且第三层也许永远也用不上，就算需要时，目前的设计也是予以支持的。
2.3.2. 查找算法
查找的算法如下：
- 计算文件名的Hash值
- 读索引根
- 使用二制查找（从当前代码线性查找）包含有目标hash值的第一个索引或叶块（依树的顺序）
- 重复上面的查找直到树的最底层
- 读叶目录的入口块并在正常的Ext2目录块里查找
- 如果找到了文件名，返回其目录入口和缓冲区
- 另外，如果设置了下一目录的入口冲突位，则在查找成功的块里继续查找
一般来说，文件的2个逻辑块将要被访问，一个或两个元数据索引块。其效果就是只要元数据索引块没有撤出cache那么访问元数据索引块的时间在磁盘访问时间里可以几乎被忽略。所以移动整个目录到页面cache里可以减少查找占用CPU开销。
2.3.3. 插入算法
往目录里插入一个新的入口比查找复杂得多，当叶块满了就需要拆分叶块，并且需满足的条件是允许hash钥冲突被有效且可靠的处理。这里我将概要的提及：
- 类似查找一样探查索引
- 如果目标叶块已满，拆分叶块并标记块将接受新的入口
- 使用正常的Ext2目录入口插入代码往叶块里插入新的入口。
关于拆分和hash冲突处理的细节比较混乱，如谁能详述这方面的内容我乐意将这些内容加入到文档中。
2.3.4. 拆分
简要的讲，当我们往一个已经满了的叶inode里插入新的入口时，叶必需被拆分，且它们共享的hash空间必需被分割。最直截了当的做法是以hash值排序入口且在序列的中部拆分。这个操作被记录(number_of_entries_in_leaf)且使用高效的排序程序时开销并不大。尽管在平均性能比最坏性能重要时Quicksort也可以做得很好，但我还是使用Combsort完成它。
An alternative approach would be just to guess a median value for the hash key, and the partition could be done in linear time, but the resulting poorer partitioning of hash key space outweighs the small advantage of the linear partition algorithm. In any event, the number of entries needing sorting is bounded by the number that fit in a leaf.
2.3.5. Key 冲突
Some complexity is introduced by the need to handle sequences of hash key collisions. It is desireable to avoid splitting such sequences between blocks, so the split point of a block is adjusted with this in mind. But the possibility still remains that if the block fills up with identically-hashed entries, the sequence may still have to be split. This situation is flagged by placing a 1 in the low bit of the index entry that points at the sucessor block, which is naturally interpreted by the index probe as an intermediate value without any special coding. Thus, handling the collision problem imposes no real processing overhead, just come extra code and a slight reduction in the hash key space. The hash key space remains sufficient for any conceivable number of directory entries, up into the billions.
2.3.6. Hash 功能
The exact properties of the hash function critically affect the performance of this indexing strategy, as I learned by trying a number of poor hash functions, at times intentionally. A poor hash function will result in many collisions or poor partitioning of the hash space. To illustrate why the latter is a problem, consider what happens when a block is split such that it covers just a few distinct hash values. The probability of later index entries hashing into the same, small hash space is very small. In practice, once a block is split, if its hash space is too small it tends to stay half full forever, an effect I observed in practice.
After some experimentation I came up with a hash function that gives reasonably good dispersal of hash keys across the entire 31 bit key space. This improved the average fullness of leaf blocks considerably, getting much closer to the theoretical average of 3/4 full.
But the current hash function is just a place holder, waiting for an better version based on some solid theory. I currently favor the idea of using crc32 as the default hash function, but I welcome suggestions.
Inevitably, no matter how good a hash function I come up with, somebody will come up with a better one later. For this reason the design allows for additional hash functiones to be added, with backward compatibility. This is accomplished simply, by including a hash function number in the index root. If a new, improved hash function is added, all the previous versions remain available, and previously created indexes remain readable.
Of course, the best strategy is to have a good hash function right from the beginning. The initial, quick hack has produced results that certainly have not been disappointing.
2.3.7. 性能
OK，到了这里毫无疑问你最关心的将是性能问题。简要的说，其性能比普通的Ext2有极大的提高。如果在很小的目录数量上其性能并不比标准的Ext2好多少，但随目录的数量的增长Ext2的性能呈指数级下降，而在htree-enhanced Ext2里只是呈线性下降。
Uli Luckas 运行benchmarks测试在不同目录数量级里建立10，000到90，000个文件所需要的时间。结果是可喜的：建立文件所用的总时间在索引目录里呈线性增长，而与之对比的普通Ext2则呈指数级增长。
时间如下：
Figure 2-3. 索引目录的性能
Indexed Normal
======= ======
10000 Files: 0m1.350s 0m23.670s
20000 Files: 0m2.720s 1m20.470s
30000 Files: 0m4.330s 3m9.320s
40000 Files: 0m5.890s 5m48.750s
50000 Files: 0m7.040s 9m31.270s
60000 Files: 0m8.610s 13m52.250s
70000 Files: 0m9.980s 19m24.070s
80000 Files: 0m12.060s 25m36.730s
90000 Files: 0m13.400s 33m18.550s
其结果的图像在：
所有的这些测试是受CPU限制的，若非如此可能会有意外的结果。目录可以很容易适应cache，而在标准Ext2里受限制的是在缓冲区cache里查找目录块，低级的目录入口扫描。而在htree索引里只有一个开销被考虑，所有的这些都有极好的控制。尽管如此，还是明显地可以对此进行优化：
- 在内部的索引inode里使用二进制查找替换线性查找。
- 如果在叶块里只有一个目录，绕过索引探测，直接访问块。
- 更改映射目录到缓冲区cache为映射目录到页面cache。
所有的这些优化可以明显的提高性能，当然性能也不可能从N**2飞跃到Log512(n),~N。优化后我们可以看到性能的成倍或更好的提高。
当目录大到要使用第二层时性能会有所折扣。因为它们的快速缓冲将很小。遍历目录元数据索引块要很大的开销，然而再者，可以通过将目录块放入页面cache里来减少这些开销。
通常，我们读或写一个目录入口会遍历3个块，如果数量增加到4-5将是一个巨大的目录。但比起普通Ext2来说性能下降几乎微不足道，因为在同样情形下普通Ext2要遍历几百个块。
Chapter 3. Inode, 文件标识符
每个文件，目录，符号连接，特殊设备，或任何其它保存在Ext2文件系统里的东东，都是通过其inode来标识的。如果你知道所读取的文件的inode号，甚至你不知道文件名，你仍可以在磁盘上定位并读取它。
3.1. Inode 号
Inode号是在inode表里一个inode结构的一个索引。Inode表的大小在格式化时就固定下来，它被设置为尽可能容纳最多的入口。尽管所需的入口数量很大，但表的大小是足以满足需求的，况且它还被平均地拆分了放在所有的“块组”里（查看Chapter 1获得更多说明）。
3.2. 定位inode结构
在超级块结构里的s_inodes_per_group字段告诉我们一个块组里定义有多少个inode。以此我们可以知道inode 1是在inode表里定义的第一个inode，所以可以有以下公式：
group = (inode - 1) / s_inodes_per_group
为定位块组的inode表哪里包含了要查找的inode入口可用以下公式：
index = (inode - 1) % s_inodes_per_group
使用index在inode表里查找inode入口。这里有一组例子，你可以用以测试你自己的Ext2实现：
Figure 3-1. inode计算例子
s_inodes_per_group = 1712
inode 号 计算
------------ -----------
1 group = (1 - 1) / 1712 = 0
index = (1 - 1) % 1712 = 0
2 group = (2 - 1) / 1712 = 0
index = (2 - 1) % 1712 = 1
963 group = (963 - 1) / 1712 = 0
index = (963 - 1) % 1712 = 962
1712 group = (1712 - 1) / 1712 = 0
index = (1712 - 1) % 1712 = 1711
1713 group = (1713 - 1) / 1712 = 1
index = (1713 - 1) % 1712 = 0
3424 group = (3424 - 1) / 1712 = 1
index = (3424 - 1) % 1712 = 1711
3425 group = (3425 - 1) / 1712 = 2
index = (3425 - 1) % 1712 = 0
正如你所熟悉的，index 0意味着第一个入口。为何使用0开始，而不是使用1开始的目的在于，可以将此值乘于结构的大小就得到文件在内存或磁盘里的最终偏移。
3.3. 定位Inode表
如Section 3.1所介绍的，inode表被平均地拆分后放在各个块组里。如果一个文件系统允许有数千个inode，拆分为5个块组，那在每个部分的inode表里将有200个inode。Figure 3-1已经举例说明了类似的分布。
每个部分的inode表可以通过所在块组的块组描述符里的bg_inode_table字段里被定位。
Chapter 4. 文件属性
文件的（包括目录，符号连接，设备……）属性大多数是位于文件inode里的标准属性。而除此之外还有一些不在inode里的扩展属性。
4.1. 标准属性
4.1.1. SUID, SGID 与 -rwxrwxrwx
在这里就不再对此有过多的描述，它们在ext2_inode.i_mode里的SGID和SUID位里有详细说明。
4.1.2. 文件大小
文件的大小可以通过查看ext2_inode.i_size字段得知。
4.1.3. 属主与属组
在多数的实现里，属主与属组为16bit的值，但在最新的Linux和Hurd的实现里它们的属主与属组ID为32bit。当使用16bit值时，只有“低位”部分起作用，而使用32bit值时，字段的“低位”与“高位”部分均起作用，其中“高位”部分经左移16位后与“低位”部分相加。
属主与属组ID的“低位”部分分别位于ext2_inode.i_uid与ext2_inode.i_gid。
属主与属组ID的“高位”部分分别位于ext2_inode.osd2.hurd.h_i_uid_high和ext2_inode.osd2.hurd.h_i_gid_high（Hurd），或ext2_inode.osd2.linux.l_i_uid_high和ext2_inode.osd2.linux.l_i_gid_high（Linux）。
4.2. 扩展属性
扩展属性的定义：文件与目录偶合的永远关联的一组值，类似于与一个进程相关联的环境信息串。一个属性可以已定义或没定义。定义了的属性其值可以是空的或非空的。
扩展属性是对标准属性的扩展，且是与在系统里所有的inode相关联的。它们常常用于为一信文件系统增加额外的功能----如：使用扩展属性为文件系统添加类似于访问控制列表（ACLs）的安全特性。
扩展属性是作为原子对象被访问的。读取时需检索一个属性的整个值并将它保存在缓冲区里。写入时用新的值取代任何一个旧值。
在每一个Ext2 inode里，有一个i_file_acl字段，它是为访问控制列表保留的。此字段的值指出存贮有一个inode扩展属性的块的块号。
扩展属性被保存于一个“无格式”的磁盘块，这些块不隶属于任何文件，其磁盘布局类似于目录的布局。在属性块头部后面为入口头部。入口头部的大小随属性名称的长度而变。
属性值和它们的属性入口描述位于同一个块，排列在属性块的末尾。这样有利于添加附加的属性。
与一个文件关联的属性名称列表可以被检索。文件系统返回一个属性名称的字符串，各名称之间用1个NULL字符分隔，以2个NULL字符结束列表。
4.2.1. 属性块头部
Figure 4-1. ext2_xattr_header 结构
offset size description
------- ------- -----------
0 4 h_magic
4 4 h_refcount
8 4 h_blocks
12 4 h_hash
16 16 保留
4.2.1.1. h_magic
32bit的Magic标识码（EXT2_XATTR_MAGIC = 0xEA020000）。
4.2.1.2. h_refcount
32bit值用于参考计数。此值在每次属性建立一个连接时增加而取消一个连接时减少。当值为0时此属性块的空间就可以释放出开。
4.2.1.3. h_blocks
32bit值表示目前有多少块用于扩展属性。
4.2.1.4. h_hash
所有属性的32bit Hash值。
4.2.2. 属性入口头部
Figure 4-2. ext2_xattr_header 结构
offset size description
------- ------- -----------
0 1 e_name_len
1 1 e_name_index
2 2 e_value_offs
4 4 e_value_block
8 4 e_value_size
12 4 e_hash
16 ... e_name
一个属性入口的大小，它总是包括4-bytes的边界。
4.2.2.1. e_name_len
8bit无符号值用于表示名称的长度。
4.2.2.2. e_name_index
8bit无符号值用于属性名称的索引。
4.2.2.3. e_value_offs
16bit无符号值表示在值块里距离值的偏移。
4.2.2.4. e_value_block
32bit，存贮值的块ID。
4.2.2.5. e_value_size
32bit无符号值表示属性值的长度。
4.2.2.6. e_hash
属性名称和值的32bit Hash值。
4.2.2.7. e_name
属性名称。
4.3. 行为控制标记
在inode结构里的i_flags值允许指定文件系统处理文件时的行为。下面是已知的定义：
Table 4-1. 行为控制标记
EXT2_SECRM_FL
0x00000001 安全删除
EXT2_UNRM_FL
0x00000002 用于反删除的记录
EXT2_COMPR_FL
0x00000004 压缩的文件
EXT2_SYNC_FL
0x00000008 同步更新
EXT2_IMMUTABLE_FL
0x00000010 不可变文件
EXT2_APPEND_FL
0x00000020 只添加
EXT2_NODUMP_FL
0x00000040 不可 Dump/删除
EXT2_NOATIME_FL
0x00000080 不更新 .i_atime
EXT2_DIRTY_FL
0x00000100 脏的(文件正在使用?)
EXT2_COMPRBLK_FL
0x00000200 压缩的块
EXT2_NOCOMPR_FL
0x00000400 Raw方式访问压缩的数据
EXT2_ECOMPR_FL
0x00000800 压缩错误
EXT2_BTREE_FL
0x00010000 B-Tree 格式目录
EXT2_INDEX_FL
0x00010000 Hash 索引的目录
EXT2_IMAGIC_FL
0x00020000 ?
EXT3_JOURNAL_DATA_FL
0x00040000 日志文件数据
EXT2_RESERVED_FL
0x80000000 保留
4.3.1. EXT2_SECRM_FL - 安全删除
启用这个位在块没有释放前将引起大小为文件数倍的任意数据被写入文件。注意：此功能高度依赖实现，且并非100%安全。在使用此功能前请详细了解当前的实现
4.3.2. EXT2_UNRM_FL - 用于反删除的记录
当实现支持此功能且设置了此位时，被删除的数据将被除移到一个临时位置，使用户恢复原始文件时没有任何数据丢失的风险。这对于在桌面与工作站使用Ext2来说非常有用。
4.3.3. EXT2_COMPR_FL - 压缩的文件
文件的内容被压缩。所使用的算法并没有指出，或许使用超级块结构里s_algo_bitmap字段描述的算法。
4.3.4. EXT2_SYNC_FL - 同步更新
文件在磁盘里的内容和在内存里的将保持同步一致。像对引导或密钥等这些会在一次crash里丢失的文件的保护十分有用。
4.3.5. EXT2_IMMUTABLE_FL - 不可变文件
与此关联的文件的块将不会被更换。如在文件系统的整理程序运行时，这些文件将不会被移动。大多用于stage2和stage1.5的引导程序。
4.3.6. EXT2_APPEND_FL - 只添加
所有的写入只能将内容添加于文件的末尾而不能更改当前的内容。如邮箱，任何人发送信息给一个用户时不能更改已有的内容。
4.3.7. EXT2_NODUMP_FL - 不可Dump/删除
设置此位可以保护文件不被删除。只要设置了此位就算i_links_count值为0，文件也不会被删除。
4.3.8. EXT2_NOATIME_FL - 不更新 .i_atime
设置此位后当文件被访问时其inode结构里的i_atime字段将不被更改。这样做我能相到的唯一好处便是出于安全性。
4.3.9. EXT2_DIRTY_FL - 脏的
目前对此没有更多的信息。
4.3.10. EXT2_COMPRBLK_FL - 压缩的块
如果有一个或更多的块被压缩了就设置此位。关于在Ext2的压缩的更多信息可以访问http://www.netspace.net.au/~reiter/e2compr/ 但这个项目在1999年就没有更新了。
4.3.11. EXT2_NOCOMPR_FL -Raw方式访问压缩数据
设置此位后，文件系统实现在将压缩数据传送给应用程序时对数据不进行解压缩。
4.3.12. EXT2_ECOMPR_FL - 压缩错误
如果在对文件进行解压缩时检测出错误将设置此位。
4.3.13. EXT2_BTREE_FL - B-Tree Format Directory
4.3.14. EXT2_INDEX_FL - Hash Indexed Directory
若此位被设置，目录文件的格式是Hash索引的。在Section 2.3有更多的细节。
4.3.15. EXT2_IMAGIC_FL -
4.3.16. EXT2_JOURNAL_DATA_FL - 日志文件数据
4.3.17. EXT2_RESERVED_FL - Reserved
Appendix A. 鸣谢
（给予原文保留）
I would like to personally thank everybody who contributed to this document, you are numerous and in many cases I haven\'t kept track of all of you. Be sure that if you are not in this list, it\'s a mistake and do not hesitate to contact me, it will be a pleasure to add your name to the list.
Andreas Gruenbacher (a.gruenbacher@bestbits.at)
Section 4.2
Daniel Phillips (phillips@innominate.de)
Section 2.3.1
Section 2.3.2
Section 2.3.3
Section 2.3.4
Section 2.3.5
Section 2.3.6
Section 2.3.7
Jeremy Stanley of Access Data Inc.
Pointed out the inversed values for EXT2_S_IFSOCK and EXT2_S_IFLNK