旧版本的Ext2以及ext3中采用了简单的单向链表来管理目录，也就是说当我们搜索目录中的某个文件时将花去O(n)的时间，其中n代表目录中文件个数。但是对于一些特殊应用，比如web缓冲和使用Maildir格式的邮件系统来说将带来严重的性能下降。
为了解决这个问题，ext2的开发人员首先提出了使用B树，但是B树存在一些和ext2的简单健壮的设计哲学冲突的地方。譬如，XFS中B树实现的代码量大于ext2和ext3源代码的总量；而且用户也报告过使用B树的文件系统在文件系统的B树的高层节点崩溃时将导致数据丢失。
针对这个问题，ext3设计了快速而简单的树结构，与很多其它文件系统不同，包括XFS,JFS,HFS,Reiserfs，他们使用通用的B树。我们将该结构称作HTree(hash-keyed uniform-depth index Tree)，从名字我们看出，它是基于hash键值(基于文件名的hash值，而不是线性搜索中使用的文件名本身)的具有统一深度的索引树，在ext2/ext3中采用这种结构来存储目录项。既然是树，那么就涉及到根，中间结点，叶结点，树的根就是目录文件的第一个目录项块，其中存储的是索引头和索引信息，索引头包含的是目录索引所使用的总体信息，包括当前树的深度，使用的hash版本等信息，而索引信息则根据当前树的深度，可能指向的是叶结点(深度=1)或者中间节点(深度>1); 叶结点中存储的是目录项内容，当然现在目录项按照索引进行存储，即hash值处于某一个范围内的目录项存储在一个目录项块中; 而中间节点存储的是索引信息，也就是hash值和对应的目录项存储的块号，该hash值是对应的目录项块中的目录项的最小hash值。
目前每个索引项占8个字节，而索引头占32个字节，因此对于一个4k的块来说，如果当前树的深度为1，那么可以索引508个叶块。假设每个目录项占用20个字节(对于文件名长度为12的文件来说)，那么一个4k块可以容纳204个目录项，如果每个块有一半的空间用来存储这些目录项，那么我们就可以索引大约500*200*50%=50k个文件，如果我们采用二级索引，那么可以支持50k*512=25M个文件，一个目录中支持这么大的数量的文件对于一般的企业级应用来说应该够了。因此当前ext3实现中采用了深度为2的HTree。
为了支持目录索引，目录项在磁盘中的存储也需要满足一定的格式，前面说过，目前这种Htree支持常数层的深度，最多两层，下面我将先用图来表达目录项在磁盘中的存储，然后逐步说明如何添加一个新的目录项，以及在建立好目录索引之后如何进行查找。
1.1.1 磁盘布局
我们知道，一个文件对应的数据块就是文件本身的内容，一个目录它对应的数据块存储的则是其包含的子目录名或者文件名，也就是目录项。通常，目录项是在父目录的数据块中依次存储的，但是引入了目录索引之后，那就需要存储索引信息了，图2是一个包含一层索引信息的图，
由图，我们可以看出，在目录的数据块0中开始存储索引信息，为了保持向后的兼容性，目录文件中第一个数据块(块0)存储的是当前目录(.)和父目录(..)，而这两个文件所占有的空间为数据块的长度，因此当旧内核看到含有索引信息的文件系统时仅仅认为含有两个文件信息，从而保持了目录信息的兼容性。
索引头中存储的是当前HTree树的深度，版本信息等，而索引0存储的则是当前索引块中索引节点的个数，索引节点的个数限制以及所指向的块信息(索引0与其它索引项不同的地方就是其没有存储hash值，但是其存储的文件的索引信息都小于所有其它块中的文件的hash值)。
为了便于查找，文件所在的目录项块按照hash值由小到大进行存储，也就是说索引1所指向的块的hash值小于索引2所指向块的hash值。
如下是数据块0在程序中的结构化表达：
struct dx_root
{
struct fake_dirent dot;
char dot_name[4];
struct fake_dirent dotdot;
char dotdot_name[4];
struct dx_root_info
{
__le32 reserved_zero;
u8 hash_version;
u8 info_length; /* 8 */
u8 indirect_levels; /*映射的层数，目前最多有两层，0和1*/
u8 unused_flags;
} info;
struct dx_entry entries[0];
};
而索引项则有struct dx_entry来表达：
struct dx_entry
{
__le32 hash;
__le32 block;
};
由上面的解释我们应该很容易的理解目录索引在磁盘中的布局了。对于深度为2的HTree来说，为了保证兼容性，这些索引块的前8个字节进行了伪造(inode=0)，使得旧内核在碰到该块时认为它是一个删除了的目录项，它在磁盘上的结构表达为：
struct dx_node
{
struct fake_dirent fake;
struct dx_entry entries[0];
};
HTree中的叶目录项块存储目录项的方式和以前的相同，这么做除了兼容性之外，还带来了另外一个好处：提高健壮性，当索引信息损坏时，文件系统的一致性检查者(fsck)会通过线性搜索找到目录中所有的项。其中ext3目录项在磁盘上的结构表达如下：
struct ext3_dir_entry_2 {
__le32 inode; /* Inode number */
__le16 rec_len; /* Directory entry length */
__u8 name_len; /* Name length */
__u8 file_type;
char name[EXT3_NAME_LEN]; /* File name */
};
我们可以看看目struct dx_node中使用的struct fake_dirent的具体表达：
struct fake_dirent
{
__le32 inode;
__le16 rec_len;
u8 name_len;
u8 file_type;
};
由上可以看出这些伪造的目录项在保持兼容性方面起到了重要作用。
1.1.2 目录项的探测
不论是什么目录项操作，第一步都是需要读取索引头信息，也就是目录文件的第一个块从而判断是否可以执行目录索引操作。如果存在有效的索引信息，那么就采用HTree进行搜索；否则将采用线性搜索。
在ext3实现中，主要是由dx_probe函数来完成该功能，它执行如下步骤：
1) 读取目录文件的第一个块到内存中，并判断hash版本是否为当前内核所支持和从超级块获取hash种子。
2) 计算将要操作的文件名的hash值。
3) 判断HTree树的深度是否<=2，当前仅支持最大深度为2。 4) 循环直到找到相应的叶目录项块为止。因为当前树的深度最大为2，因此最多两次循环就可以找到我们所需要的块。由于索引信息按照hash值由小到大进行存储，因此按照折半查找算法进行查找。 1.1.3 目录项的添加 下面将介绍如何添加一个目录项(我们都是围绕内核支持目录索引来进行阐述，至于不支持目录索引的添加在此就不再进一步阐述)。应该很容易就能够想到，在添加一个新的目录项时，首先应该根据待添加目录项的hash值给它定位到某个数据块，如果找到了，并且当前数据块还有空间，那么非常好，直接加入到该数据块中就行。我们先看看这种情况： 在ext3中目录项的添加是通过ext3_dx_add_entry()函数来完成的， static int ext3_dx_add_entry(handle_t *handle, struct dentry *dentry, struct inode *inode) { struct dx_frame frames[2], *frame; struct dx_entry *entries, *at; struct dx_hash_info hinfo; struct buffer_head * bh; struct inode *dir = dentry->d_parent->d_inode;
struct super_block * sb = dir->i_sb;
struct ext3_dir_entry_2 *de;
int err;
frame = dx_probe(dentry, NULL, &hinfo, frames, &err);
if (!frame)
return err;
entries = frame->entries;
at = frame->at;
if (!(bh = ext3_bread(handle,dir, dx_get_block(frame->at), 0, &err)))
goto cleanup;
BUFFER_TRACE(bh, "get_write_access");
err = ext3_journal_get_write_access(handle, bh);
if (err)
goto journal_error;
err = add_dirent_to_buf(handle, dentry, inode, NULL, bh);
if (err != -ENOSPC) {
bh = NULL;
goto cleanup;
}
/* Block full, should compress but for now just split */
dxtrace(printk("using %u of %u node entries\n",
dx_get_count(entries), dx_get_limit(entries)));
/* Need to split index? */
if (dx_get_count(entries) == dx_get_limit(entries)) {
u32 newblock;
unsigned icount = dx_get_count(entries);
int levels = frame - frames;
struct dx_entry *entries2;
struct dx_node *node2;
struct buffer_head *bh2;
if (levels && (dx_get_count(frames->entries) ==
dx_get_limit(frames->entries))) {
ext3_warning(sb, __FUNCTION__,
"Directory index full!");
err = -ENOSPC;
goto cleanup;
}
bh2 = ext3_append (handle, dir, &newblock, &err);
if (!(bh2))
goto cleanup;
node2 = (struct dx_node *)(bh2->b_data);
entries2 = node2->entries;
node2->fake.rec_len = cpu_to_le16(sb->s_blocksize);
node2->fake.inode = 0;
BUFFER_TRACE(frame->bh, "get_write_access");
err = ext3_journal_get_write_access(handle, frame->bh);
if (err)
goto journal_error;
if (levels) {
unsigned icount1 = icount/2, icount2 = icount - icount1;
unsigned hash2 = dx_get_hash(entries + icount1);
dxtrace(printk("Split index %i/%i\n", icount1, icount2));
BUFFER_TRACE(frame->bh, "get_write_access"); /* index root */
err = ext3_journal_get_write_access(handle,
frames[0].bh);
if (err)
goto journal_error;
memcpy ((char *) entries2, (char *) (entries + icount1),
icount2 * sizeof(struct dx_entry));
dx_set_count (entries, icount1);
dx_set_count (entries2, icount2);
dx_set_limit (entries2, dx_node_limit(dir));
/* Which index block gets the new entry? */
if (at - entries >= icount1) {
frame->at = at = at - entries - icount1 + entries2;
frame->entries = entries = entries2;
swap(frame->bh, bh2);
}
dx_insert_block (frames + 0, hash2, newblock);
dxtrace(dx_show_index ("node", frames[1].entries));
dxtrace(dx_show_index ("node",
((struct dx_node *) bh2->b_data)->entries));
err = ext3_journal_dirty_metadata(handle, bh2);
if (err)
goto journal_error;
brelse (bh2);
} else {
dxtrace(printk("Creating second level index...\n"));
memcpy((char *) entries2, (char *) entries,
icount * sizeof(struct dx_entry));
dx_set_limit(entries2, dx_node_limit(dir));
/* Set up root */
dx_set_count(entries, 1);
dx_set_block(entries + 0, newblock);
((struct dx_root *) frames[0].bh->b_data)->info.indirect_levels = 1;
/* Add new access path frame */
frame = frames + 1;
frame->at = at = at - entries + entries2;
frame->entries = entries = entries2;
frame->bh = bh2;
err = ext3_journal_get_write_access(handle,
frame->bh);
if (err)
goto journal_error;
}
ext3_journal_dirty_metadata(handle, frames[0].bh);
}
de = do_split(handle, dir, &bh, frame, &hinfo, &err);
if (!de)
goto cleanup;
err = add_dirent_to_buf(handle, dentry, inode, de, bh);
bh = NULL;
goto cleanup;
journal_error:
ext3_std_error(dir->i_sb, err);
cleanup:
if (bh)
brelse(bh);
dx_release(frames);
return err;
}
它首先通过dx_probe函数来获取该目录项应该在的目录项块信息，然后调用add_dirent_to_buf函数来添加一个目录项，该函数原型如下：
static int add_dirent_to_buf(handle_t *handle, struct dentry *dentry,
struct inode *inode, struct ext3_dir_entry_2 *de,
struct buffer_head * bh)
{
struct inode *dir = dentry->d_parent->d_inode;
const char *name = dentry->d_name.name;
int namelen = dentry->d_name.len;
unsigned long offset = 0;
unsigned short reclen;
int nlen, rlen, err;
char *top;
reclen = EXT3_DIR_REC_LEN(namelen);
if (!de) {
de = (struct ext3_dir_entry_2 *)bh->b_data;
top = bh->b_data + dir->i_sb->s_blocksize - reclen;
while ((char *) de <= top) { if (!ext3_check_dir_entry("ext3_add_entry", dir, de, bh, offset)) { brelse (bh); return -EIO; } if (ext3_match (namelen, name, de)) { brelse (bh); return -EEXIST; } nlen = EXT3_DIR_REC_LEN(de->name_len);
rlen = le16_to_cpu(de->rec_len);
if ((de->inode? rlen - nlen: rlen) >= reclen)
break;
de = (struct ext3_dir_entry_2 *)((char *)de + rlen);
offset += rlen;
}
if ((char *) de > top)
return -ENOSPC;
}
BUFFER_TRACE(bh, "get_write_access");
err = ext3_journal_get_write_access(handle, bh);
if (err) {
ext3_std_error(dir->i_sb, err);
brelse(bh);
return err;
}
/* By now the buffer is marked for journaling */
nlen = EXT3_DIR_REC_LEN(de->name_len);
rlen = le16_to_cpu(de->rec_len);
if (de->inode) {
struct ext3_dir_entry_2 *de1 = (struct ext3_dir_entry_2 *)((char *)de + nlen);
de1->rec_len = cpu_to_le16(rlen - nlen);
de->rec_len = cpu_to_le16(nlen);
de = de1;
}
de->file_type = EXT3_FT_UNKNOWN;
if (inode) {
de->inode = cpu_to_le32(inode->i_ino);
ext3_set_de_type(dir->i_sb, de, inode->i_mode);
} else
de->inode = 0;
de->name_len = namelen;
memcpy (de->name, name, namelen);
dir->i_mtime = dir->i_ctime = CURRENT_TIME_SEC;
ext3_update_dx_flag(dir);
dir->i_version++;
ext3_mark_inode_dirty(handle, dir);
BUFFER_TRACE(bh, "call ext3_journal_dirty_metadata");
err = ext3_journal_dirty_metadata(handle, bh);
if (err)
ext3_std_error(dir->i_sb, err);
brelse(bh);
return 0;
}
先解释一下函数参数：
1) handle代表一个原子更新操作，由JBD模块提供的接口
2) dentry代表当前待添加的目录项
3) inode代表当前待添加的目录项的inode
4) de指向一个有足够空间能够容纳当前待添加的目录项的目录项，如果为空，那么需要在目录项块中查找空间
5) bh指向目录项块在内存中的地址
该函数执行如下步骤：
a) 判断参数de是否为空，如果为空，那么我们将为待添加的目录项查找空间。由于目录项块中存储的都是目录项，而且它有这样一个特点：所有的目录项的长度(不一定是实际长度)之和等于目录项块的长度；如果我们删除了其中某一个目录项，那么只是将该目录项的标志设置成了删除，其所占用的空间并未回收。因此在这里所做的工作就是查找合适的目录项，只要其空闲空间能够覆盖我们所需要的空间，那么其就是我们找的。在这里有两种可能情况：第一种就是其中的某个目录项所占用空间很大，但是其实际所需要的空间很小，那么其剩下的空间我们是可以利用的；第二种就是那些被删除了的目录项，其空间如果满足我们要求是可以利用的。按照如上进行查找，如果未找到合适的空间，那么将返回空间不足ENOSPC的信息给其调用者；如果目录中已经有同名的文件，那么返回文件已存在EEXIST给其调用者。
b) 到达这里我们已经找到了能够容纳当前待添加的目录项的目录项。由上我们知道需要进行一些处理，也是分两种情况：第一种情况，如果是空间很大的目录项，那么就需要调整其所占用的空间为实际需要的空间，从而腾出空间给待添加的目录项；第二种情况，如果是已删除的目录项，那么很简单，直接占用其空间即可。
c) 为该目录项赋值，包括文件名，所占长度，inode；修改父目录inode的时间戳信息，然后将这些需要写回的数据置成dirty。
当add_dirent_to_buf执行完毕后，我们可能会碰到一种情况需要特殊处理，那就是当返回值为ENOSPC时，代表目前目录项块空间不足。我们所做的工作应该是尝试进行压缩，看是否有足够的空间来存储待添加的目录项，但是当前实现中并未进行这样的处理，而是进行分裂，即将一个块中的内容分到两个块中，再尝试进行添加。
我们沿着代码往下看，此时需要判断当前索引块是否满，因为目录项块已经满，那么当我们添加一个新的目录项块时，需要在索引块中增加相应的索引项。因此当前需要解决的一个问题是要有一个索引项能够索引我们新添加的目录项块。执行如下步骤进行处理：
a) 判断当前索引块是否满，如果未满，那么我们就可以在其中增加一个索引项，从而可以索引新加的目录项块。
b) 如果已满，那么我们需要进一步判断。如果当前目录中的目录索引的深度已经为2并且第一层索引块已满，那么我们需要报告空间不足的信息给用户。反之，有两种可能性：第一种，当前目录索引深度为1，而且第一层索引块已满，我们可以通过增加树的深度为2来进行扩充索引项；第二种情况，当前树的深度已经为2，但是第一层索引块并未满，此时我们可以在第一层中增加新的索引项来扩充，下面分别看看这两种情况。
c) 对于第一种，增加一个新的索引块，准备构建第二层索引。它将第一层索引块中的索引信息全部拷贝到新块中，并且设置新索引块的索引限制；当然，也需要设置第一层索引的信息，因为它目前只有一个索引项了，指向新索引块。
d) 对于第二种情况，当前索引块已满，而第一层索引块未满。将在第二层中增加一个新的索引块，同时将已满索引块中的索引信息的一半拷贝到新索引块中，然后分别调整对应索引块的当前索引数量。将新索引块插入到第一层索引中，并确定新的目录项将插入到哪个索引块中。
e) 通过上述操作，可以确保有索引项可以索引新添加的目录项块。新增一个目录项块之后，将以前满的目录项块中的目录项信息分成两半分别存储在这两个目录项块中。之后再将待添加的目录项加入到目录项块中。
1.1.4 目录项的删除
目录项的删除很简单，在ext3中由函数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 <>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
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;
}
主要执行如下步骤：在目录项所在块中进行搜索，如果找到了对应的目录项，那么将其所占有的空间与前一目录项进行合并，也就是将其空间加到前一目录项上；如果该目录项是目录项块的第一个目录项，那么将其标志为删除即可。
1.1.5 目录项的查找
通过上面的内容，我们已经知道了目录项的存储结构，那么在进行目录项搜索时就应该很容易了。考虑到兼容性的问题，在进行查找时，首先需要判断是否支持目录索引功能，即判断该文件系统支持和当前目录是否支持。在ext3中，该功能由函数ext3_find_entry实现，我们在这里关注支持目录索引的情况，具体来说由函数ext3_dx_find_entry完成：
static struct buffer_head * ext3_dx_find_entry(struct dentry *dentry,
struct ext3_dir_entry_2 **res_dir, int *err)
{
struct super_block * sb;
struct dx_hash_info hinfo;
u32 hash;
struct dx_frame frames[2], *frame;
struct ext3_dir_entry_2 *de, *top;
struct buffer_head *bh;
unsigned long block;
int retval;
int namelen = dentry->d_name.len;
const u8 *name = dentry->d_name.name;
struct inode *dir = dentry->d_parent->d_inode;
sb = dir->i_sb;
/* NFS may look up ".." - look at dx_root directory block */
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;
top = (struct ext3_dir_entry_2 *) ((char *) de + sb->s_blocksize -
EXT3_DIR_REC_LEN(0));
for (; de < de =" ext3_next_entry(de))">b_data))) {
brelse (bh);
goto errout;
}
*res_dir = de;
dx_release (frames);
return bh;
}
brelse (bh);
/* Check to see if we should continue to search */
retval = ext3_htree_next_block(dir, hash, frame,
frames, NULL);
if (retval <>i_ino);
*err = retval;
goto errout;
}
} while (retval == 1);
*err = -ENOENT;
errout:
dxtrace(printk("%s not found\n", name));
dx_release (frames);
return NULL;
}
主要执行如下步骤：
1) 先获得目录项所在的目录项块，对于特殊文件.和..，直接将其目录项块设置为当前目录inode的第一个块，由前述内容，很容易理解。
2) 在目录项块中进行匹配，如果找到对应项就返回。
3) 如果未找到需要判断是否还需要进一步的查找，因为我们在目录项的添加时做过切割，也就是将目录项分成两部分分别存储到两个不同的块中，那么存在这样一种可能性：前一个块中的最后一个目录项和后一个目录项的第一个目录项的hash值相同，而这个目录项很有可能就是我们要搜索的但是在前一个块中未搜索到的。我们在目录项的添加可以注意到：当存在上述可能性时，后一个目录项块的索引和前一个目录项块的索引值相差仅为1。
No comments:
Post a Comment