ext2在设计之初的时候就是通过链表的方式管理目录下的文件项目，ext3,ext4也是直接继承过来了，但随着单个目录下管理的文件越来越多到几十万个，线性的链表查找文件，创建文件（先要查找同名文件）越来越慢，时间复杂的达到了O(n)的级别，尤其对于当前云存储大数据等概念，读写速度是不能接受的。

dirlist_oenhan

为了能快速查找，内核开发人员设计了一个B树索引结构，称为HTree，也就是基于Hash作为键值的索引树，之所以采用hash键值，应该是因为基于文件名做键值可能会导致树分布不均，而且键值长度不一，索引效果差。

查看一个分区是否启用了hash目录索引的方式如下，存在dir_index即是启动目录索引。

tune2fs -l blk | grep dir_index
Filesystem features:      has_journal dir_index filetype sparse_super large_file

#如果没有启动，需要通过如下命令启用，具体参考man手册
tune2fs -O dir_index blk

1.Hash索引的存储形式

正常情况下目录作为一个inode节点存在存储方式如下：

oenhan

以上是正常的inode和具体数据块之间的关系，目录项是放到数据块里面存储的，如果系统启用了dir_index，整个inode结果不变，变得是内部数据块。部分数据块存储不再是ext3_dir_entry，而是dx_entry。

struct dx_entry
{
  __le32 hash;
  __le32 block;
};

hash是根据从需要查找的文件名生成的值，block则对应ext3_dir_entry存储到具体的那个物理块上。如下图：

oenhan-目录索引

目录索引的B树结构图如下：

htree-dir index

树的根就是存储在目录的第一个数据块，即dx_root，其中叶节点存储的目录项的内容，当前目录项并非按照线性排序了，而是hash值处于某一个范围内的目录项存储在一个目录项块中；中间节点存储的是存储的是索引项，内容和第一个目录数据块块内容基本一致。

当前每个索引项dx_entry占8个字节，索引树根部dx_root占32个字节，对于一个4KB大小的块，即如图的第一索引，可以索引508个叶块或节点块，第二层索引可以索引511个块，那么目录索引树支持目录大小为508×511×4KB=1014MB，假定一个目录下文件名平均由22个字符长度，那么一个目录项即30B，那么二级索引树最大支持约34M个文件，即3400万个文件，满足了绝大部分的存储场景需求。

具体的结构呈现也是可以通过debugfs工具中的htree看到的：
篇幅原因，日志贴出部分

$ debugfs blk
debugfs:  stat dir
Inode: 119249   Type: directory    Mode:  0775   Flags: 0x1000
Generation: 3945169678    Version: 0x00000000
User:  1000   Group:  1000   Size: 240640
File ACL: 0    Directory ACL: 0
Links: 2   Blockcount: 472
Fragment:  Address: 0    Number: 0    Size: 0
ctime: 0x530f54ee -- Thu Feb 27 23:08:30 2014
atime: 0x530f54f2 -- Thu Feb 27 23:08:34 2014
mtime: 0x530f54ee -- Thu Feb 27 23:08:30 2014
BLOCKS:
(0):480769, (1-2):63486-63487, (3-11):64293-64301, (IND):64302, (12-234):64303-64525
TOTAL: 236
debugfs:  htree dir
Root node dump:
 Reserved zero: 0
 Hash Version: 1
 Info length: 8
 Indirect levels: 1
 Flags: 0
#第一层索引
Number of entries (count): 2
Number of entries (limit): 124
Entry #0: Hash 0x00000000, block 125
Entry #1: Hash 0x8244b864, block 129

#第二层索引
Entry #0: Hash 0x00000000, block 125
#下面都是从125块解析的内容
Number of entries (count): 116
Number of entries (limit): 127
Entry #0: Hash 0x00000000, block 1
Entry #1: Hash 0x00f6f950, block 211
Entry #2: Hash 0x01e03ae4, block 119
Entry #3: Hash 0x0339dea2, block 60
Entry #4: Hash 0x04267e5a, block 192
Entry #5: Hash 0x054571ce, block 97
Entry #6: Hash 0x0671da66, block 175
Entry #7: Hash 0x075808c8, block 31
Entry #8: Hash 0x08457324, block 213
Entry #9: Hash 0x090b866a, block 82
Entry #10: Hash 0x09e4098a, block 168
Entry #11: Hash 0x0b17be5a, block 16
Entry #12: Hash 0x0c0b437e, block 218
Entry #13: Hash 0x0d03747e, block 98
Entry #14: Hash 0x0dfd04be, block 210
Entry #15: Hash 0x0ef97faa, block 50
Entry #16: Hash 0x0fe13db6, block 167
Entry #17: Hash 0x10d439b2, block 85
Entry #18: Hash 0x1289ff08, block 140
Entry #19: Hash 0x13aa5e90, block 32
Entry #20: Hash 0x14ce67a2, block 131

目录索引的整个结构保持不变，如此，fsck修复的时候可以越过dir_index的机制，避免了复杂的修复机制，但实际修复的时候，索引数据又和具体的目录项数据不同，在每个索引块的前8个字节伪造成0进行区分，即inode为0，相当于被删除的目录项。

2.具体代码实现

2.1 在目录中查找文件

在ext3_find_entry调用中

#ifdef CONFIG_EXT3_INDEX
if (is_dx(dir)) {
bh = ext3_dx_find_entry(dentry, res_dir, &err);
/*
 * On success, or if the error was file not found,
 * return.  Otherwise, fall back to doing a search the
 * old fashioned way.
 */if (bh || (err != ERR_BAD_DX_DIR))
return bh;
dxtrace(printk("ext3_find_entry: dx failed, falling backn"));
}
#endif

调用dx_probe获取文件对应目录项的块，使用ext3_bread获取块内容，解析成功目录项。

if (namelen > 2 || name[0] != '.'||(name[1] != '.' && name[1] != '\0')){
if (!(frame = dx_probe(dentry, NULL, &hinfo, frames, err)))
return NULL;
} else {
frame = frames;
frame->bh = NULL;/* for dx_release() */frame->at = (struct dx_entry *)frames;/* hack for zero entry*/dx_set_block(frame->at, 0);/* dx_root block is 0 */}
hash = hinfo.hash;
do {
block = dx_get_block(frame->at);
if (!(bh = ext3_bread (NULL,dir, block, 0, err)))
goto errout;
de = (struct ext3_dir_entry_2 *) bh->b_data;

dx_probe主要内容：

1.将目录文件的第一个数据块读取到内存中，解析成第一层索引。

2.通过循环2次，就可以找到对应的目录项，因为索引信息是根据hash值大小不同进行排列的，可以直接使用折半查找法进行查找。

while (1)
{
count = dx_get_count(entries);
assert (count && count <= dx_get_limit(entries));
p = entries + 1;
q = entries + count - 1;
while (p <= q)
{
m = p + (q - p)/2;
dxtrace(printk("."));
if (dx_get_hash(m) > hash)
q = m - 1;
else
p = m + 1;
}
at = p - 1;
dxtrace(printk(" %x->%un", at == entries? 0: dx_get_hash(at), dx_get_block(at)));
frame->bh = bh;
frame->entries = entries;
frame->at = at;
if (!indirect--) return frame;
if (!(bh = ext3_bread (NULL,dir, dx_get_block(at), 0, err)))
goto fail2;
at = entries = ((struct dx_node *) bh->b_data)->entries;
assert (dx_get_limit(entries) == dx_node_limit (dir));
frame++;
}

2.2 在目录里面删除文件

ext3_delete_entry完成这一个动作

static int ext3_delete_entry (handle_t *handle,
      struct inode * dir,
      struct ext3_dir_entry_2 * de_del,
      struct buffer_head * bh)
{
struct ext3_dir_entry_2 * de, * pde;
int i;

i = 0;
pde = NULL;
//获取目录项指针
de = (struct ext3_dir_entry_2 *) bh->b_data;
//进入循环
while (i < bh->b_size) {
if (!ext3_check_dir_entry("ext3_delete_entry", dir, de, bh, i))
return -EIO;
               //指针匹配到要删除的目录
if (de == de_del)  {
BUFFER_TRACE(bh, "get_write_access");
ext3_journal_get_write_access(handle, bh);
if (pde)
                        //不是第一个目录项，则将前一个目录项的宽度扩大当前目录项的长度
pde->rec_len =
cpu_to_le16(le16_to_cpu(pde->rec_len) +
    le16_to_cpu(de->rec_len));
else
                        //如果是一个目录项直接将inode置为0
de->inode = 0;
dir->i_version++;
BUFFER_TRACE(bh, "call ext3_journal_dirty_metadata");
ext3_journal_dirty_metadata(handle, bh);
return 0;
}
i += le16_to_cpu(de->rec_len);
pde = de;
de = (struct ext3_dir_entry_2 *)
((char *) de + le16_to_cpu(de->rec_len));
}
return -ENOENT;
}

2.3 在目录里面新增文件

ext3_add_entry调用ext3_dx_add_entry实现具体索引项中更改，通过dx_probe获取hash值所在块，通过ext3_bread获取块内容后用add_dirent_to_buf完成目录项的添加。

add_dirent_to_buf在解析的目录项中寻找合适的空间，主要有两种：1.目录数据块中有没有使用的空间，2.部分目录项由于其旁边删除目录项而没有使用的空间。如果仍没有空间，返回ENOSPC，存在同名文件，返回EEXIST。

返回ENOSPC后，ext3_dx_add_entry重新申请物理块作为索引块，将原来一个块分裂成两个块，新增的文件仍然按照hash值大小添加到顺序位置，具体参考ext3_dx_add_entry代码。


ext3目录索引机制分析来自于OenHan

链接为:https://oenhan.com/ext3-dir-hash-index

发表回复