目录项

在 ext4 文件系统中，目录或多或少是一个平面文件，它将任意字节字符串（通常是 ASCII）映射到文件系统上的 inode 号。文件系统中可以有许多目录项引用同一个 inode 号——这些被称为硬链接，这也是为什么硬链接不能引用其他文件系统上的文件。因此，通过读取与目录文件关联的数据块来查找所需的特定目录项。

线性（经典）目录

默认情况下，每个目录都以“近似线性”数组的形式列出其条目。我之所以写“近似”，是因为它在内存意义上不是线性数组，因为目录项不会跨文件系统块分割。因此，更准确的说法是，目录是一系列数据块，并且每个块都包含一个目录项的线性数组。每个块内数组的结束通过到达块的末尾来表示；块中的最后一个条目的记录长度延伸到块的末尾。整个目录的结束当然通过到达文件的末尾来表示。未使用的目录项由 inode = 0 表示。默认情况下，文件系统对目录项使用 struct ext4_dir_entry_2，除非“filetype”特性标志未设置，在这种情况下它使用 struct ext4_dir_entry。

原始目录项格式是 struct ext4_dir_entry，它最多长 263 字节，尽管在磁盘上您需要参考 dirent.rec_len 才能确定。

偏移	大小	名称	描述
0x0	__le32	inode	此目录项指向的 inode 号。
0x4	__le16	rec_len	此目录项的长度。必须是 4 的倍数。
0x6	__le16	name_len	文件名的长度。
0x8	char	name[EXT4_NAME_LEN]	文件名。

由于文件名不能超过 255 字节，新的目录项格式缩短了 name_len 字段，并利用该空间存储文件类型标志，这可能是为了避免在目录树遍历期间加载每个 inode。此格式是 ext4_dir_entry_2，它最多长 263 字节，尽管在磁盘上您需要参考 dirent.rec_len 才能确定。

偏移	大小	名称	描述
0x0	__le32	inode	此目录项指向的 inode 号。
0x4	__le16	rec_len	此目录项的长度。
0x6	__u8	name_len	文件名的长度。
0x7	__u8	file_type	文件类型代码，参见下方 ftype 表。
0x8	char	name[EXT4_NAME_LEN]	文件名。

目录文件类型是以下值之一

值	描述
0x0	未知。
0x1	普通文件。
0x2	目录。
0x3	字符设备文件。
0x4	块设备文件。
0x5	FIFO。
0x6	套接字。
0x7	符号链接。

为了支持同时加密和大小写折叠的目录，我们还必须在目录项中包含哈希信息。我们将 ext4_extended_dir_entry_2 附加到 ext4_dir_entry_2 后面，但“点”和“点点”的条目保持不变。该结构紧随在 name 之后，并包含在 rec_len 列出的尺寸中。如果目录项使用此扩展，其大小可能达到 271 字节。

偏移	大小	名称	描述
0x0	__le32	hash	目录名的哈希值
0x4	__le32	minor_hash	目录名的次要哈希值

为了给这些经典目录块添加校验和，一个伪造的 struct ext4_dir_entry 被放置在每个叶块的末尾以保存校验和。该目录项长 12 字节。inode 号和 name_len 字段设置为零，以欺骗旧软件忽略看似空的目录项，并且校验和存储在通常放置名称的位置。该结构是 struct ext4_dir_entry_tail

偏移	大小	名称	描述
0x0	__le32	det_reserved_zero1	inode 号，必须为零。
0x4	__le16	det_rec_len	此目录项的长度，必须为 12。
0x6	__u8	det_reserved_zero2	文件名的长度，必须为零。
0x7	__u8	det_reserved_ft	文件类型，必须为 0xDE。
0x8	__le32	det_checksum	目录叶块校验和。

叶目录块校验和的计算依据是文件系统 UUID、目录的 inode 号、目录的 inode 生成号，以及整个目录项块（但不包括）伪目录项。

哈希树目录

目录项的线性数组对于性能来说并不理想，因此 ext3 中添加了一个新特性，以提供一个更快（但特殊）的平衡树，该树以目录项名称的哈希值为键。如果 inode 中设置了 EXT4_INDEX_FL (0x1000) 标志，则此目录使用哈希 B 树（htree）来组织和查找目录项。为了向后读取兼容 ext2，这棵树实际上隐藏在目录文件中，伪装成“空”目录数据块！前面提到，线性目录项表的末尾用一个指向 inode 0 的条目来表示；这被（滥）用以欺骗旧的线性扫描算法，使其认为目录块的其余部分是空的，从而继续前进。

树的根节点始终位于目录的第一个数据块中。根据 ext2 约定，'.' 和 '..' 条目必须出现在此第一个块的开头，因此它们作为两个 struct ext4_dir_entry_2 放置在此处，而不存储在树中。根节点的其余部分包含有关树的元数据，最后是一个哈希到块的映射，用于查找 htree 中较低层的节点。如果 dx_root.info.indirect_levels 非零，则 htree 有两层；根节点映射指向的数据块是一个内部节点，由次要哈希索引。该树中的内部节点包含一个清零的 struct ext4_dir_entry_2，后跟一个 minor_hash 到块的映射，用于查找叶节点。叶节点包含所有 struct ext4_dir_entry_2 的线性数组；所有这些条目（大概）都哈希到相同的值。如果发生溢出，条目会简单地溢出到下一个叶节点，并且哈希（在内部节点映射中）的最低有效位会设置，该位将我们带到下一个叶节点。

要将目录作为 htree 遍历，代码会计算所需文件名的哈希值，并使用它来查找相应的块号。如果树是扁平的，则该块是一个可搜索的目录项线性数组；否则，将计算文件名的次要哈希值，并将其用于第二个块以查找相应的第三个块号。该第三个块号将是一个目录项的线性数组。

要将目录作为线性数组遍历（就像旧代码所做的那样），代码只需读取目录中的每个数据块。用于 htree 的块将显示没有条目（除了“.”和“..”），因此只有叶节点会显示任何有趣的内容。

htree 的根位于 struct dx_root 中，其长度与一个数据块的完整长度相同

偏移	类型	名称	描述
0x0	__le32	dot.inode	此目录的 inode 号。
0x4	__le16	dot.rec_len	此记录的长度，12。
0x6	u8	dot.name_len	名称长度，1。
0x7	u8	dot.file_type	此条目的文件类型，0x2（目录）（如果设置了特性标志）。
0x8	char	dot.name[4]	“.000”
0xC	__le32	dotdot.inode	父目录的 inode 号。
0x10	__le16	dotdot.rec_len	block_size - 12。记录长度足以覆盖所有 htree 数据。
0x12	u8	dotdot.name_len	名称长度，2。
0x13	u8	dotdot.file_type	此条目的文件类型，0x2（目录）（如果设置了特性标志）。
0x14	char	dotdot_name[4]	“..00”
0x18	__le32	struct dx_root_info.reserved_zero	零。
0x1C	u8	struct dx_root_info.hash_version	哈希类型，参见下方 dirhash 表。
0x1D	u8	struct dx_root_info.info_length	树信息的长度，0x8。
0x1E	u8	struct dx_root_info.indirect_levels	htree 的深度。如果设置了 INCOMPAT_LARGEDIR 特性，则不能大于 3；否则不能大于 2。
0x1F	u8	struct dx_root_info.unused_flags
0x20	__le16	limit	此头部后面可跟随的 dx_entries 的最大数量，加上头部本身的一个。
0x22	__le16	count	此头部后面实际跟随的 dx_entries 的数量，加上头部本身的一个。
0x24	__le32	block	与 hash=0 对应的块号（在目录文件内）。
0x28	struct dx_entry	entries[0]	在数据块其余部分中能容纳的 8 字节 struct dx_entry 的数量。

目录哈希值是以下值之一

值	描述
0x0	传统。
0x1	半 MD4。
0x2	Tea。
0x3	传统，无符号。
0x4	半 MD4，无符号。
0x5	Tea，无符号。
0x6	Siphash。

htree 的内部节点记录为 struct dx_node，其长度也与一个数据块的完整长度相同

偏移	类型	名称	描述
0x0	__le32	fake.inode	零，使其看起来此条目未被使用。
0x4	__le16	fake.rec_len	块的大小，以隐藏所有 dx_node 数据。
0x6	u8	name_len	零。此“未使用”目录项没有名称。
0x7	u8	file_type	零。此“未使用”目录项没有文件类型。
0x8	__le16	limit	此头部后面可跟随的 dx_entries 的最大数量，加上头部本身的一个。
0xA	__le16	count	此头部后面实际跟随的 dx_entries 的数量，加上头部本身的一个。
0xE	__le32	block	与此块的最低哈希值对应的块号（在目录文件内）。此值存储在父块中。
0x12	struct dx_entry	entries[0]	在数据块其余部分中能容纳的 8 字节 struct dx_entry 的数量。

同时存在于 struct dx_root 和 struct dx_node 中的哈希映射记录为 struct dx_entry，其长度为 8 字节

偏移	类型	名称	描述
0x0	__le32	hash	哈希码。
0x4	__le32	block	htree 中下一个节点的块号（在目录文件内，而非文件系统块）。

（如果您觉得这很巧妙且特殊，作者也这样认为。）

如果启用了元数据校验和，目录块的最后 8 字节（恰好是一个 dx_entry 的长度）用于存储一个 struct dx_tail，其中包含校验和。dx_root/dx_node 结构中的 limit 和 count 条目会根据需要进行调整，以使 dx_tail 适合该块。如果没有空间容纳 dx_tail，用户会收到通知，运行 e2fsck -D 来重建目录索引（这将确保有空间存放校验和）。dx_tail 结构长 8 字节，如下所示

偏移	类型	名称	描述
0x0	u32	dt_reserved	零。
0x4	__le32	dt_checksum	htree 目录块的校验和。

校验和的计算依据是文件系统 UUID、htree 索引头部（dx_root 或 dx_node）、所有正在使用的 htree 索引（dx_entry）以及尾部块（dx_tail）。