在linux平台下很多用户都在使用ext3文件系统，主要原因是其可靠性，健壮性和兼容性。在linux 2.6内核中已经包括了适合在服务器环境中使用的很多特性，譬如目录索引，块预留，在线调整大小。为支持更大容量的文件系统，其下一个版本ext4也正处于开发中。本文主要介绍当前ext3和ext4文件系统中在线调整大小的工作机制，以及如何使用meta block group来扩展其大小(该功能目前还未实现，我已提交patch)。

(一) 磁盘布局
为了更好的理解在线调整大小工作机制，我们首先需要理解ext3和ext4文件系统的磁盘布局，对于该功能的实现来说，这两个文件系统在磁盘上的结构是一致的，同时为了简化和突出重点，对于与在线调整大小功能不相关的内容我们将不会介绍。

Ext3文件系统将其所管理的磁盘或者分区(引导块除外)中的块划分到不同的块组中。每个块组大小相同，当然最后一个块组所管理的块可能会少一些，其大小在文件系统创建时决定，主要取决于文件系统的块大小，对于大小为4k的文件系统块来说，块组大小为168M。每个块组都包含一些重要的元数据信息，见图1：
每个块组包含一个块位图块，一个inode位图块，一个或多个块用于描述inode表和用于存储文件数据的数据块，除此之外，还有可能包含超级块和所有块组描述符表(取决于块组号和文件系统创建时使用的参数)。下面将对这些元数据作一些简要介绍。

块位图用于描述该块组所管理的块的分配状态。如果某个块对应的位未置位，那么代表该块未分配，可以用于存储数据；否则，代表该块已经用于存储数据或者该块不能够使用(譬如该块物理上不存在)。由于块位图仅占一个块，因此这也就决定了块组的大小。

Inode位图用于描述该块组所管理的inode的分配状态。我们知道inode是用于描述文件的元数据，每个inode对应文件系统中唯一的一个号，如果inode位图中相应位置位，那么代表该inode已经分配出去；否则可以使用。由于其仅占用一个块，因此这也限制了一个块组中所能够使用的最大inode数量。

Inode表用于存储inode信息。它占用一个或多个块(为了有效的利用空间，多个inode存储在一个块中)，其大小取决于文件系统创建时的参数，由于inode位图的限制，决定了其最大所占用的空间。

超级块用于存储文件系统全局的配置参数(譬如：块大小，总的块数和inode数)和动态信息(譬如：当前空闲块数和inode数)，其处于文件系统开始位置的1k处，所占大小为1k。为了系统的健壮性，最初每个块组都有超级块和组描述符表(以下将用GDT)的一个拷贝，但是当文件系统很大时，这样浪费了很多块(尤其是GDT占用的块多)，后来采用了一种稀疏的方式来存储这些拷贝，只有块组号是3, 5 ,7的幂的块组(譬如说1,3,5,7,9,25,49…)才备份这个拷贝。通常情况下，只有主拷贝(第0块块组)的超级块信息被文件系统使用，其它拷贝只有在主拷贝被破坏的情况下才使用。

GDT用于存储块组描述符，其占用一个或者多个数据块，具体取决于文件系统的大小。它主要包含块位图，inode位图和inode表位置，当前空闲块数，inode数以及使用的目录数(用于平衡各个块组目录数)，具体定义可以参见ext3_fs.h文件中struct ext3_group_desc。每个块组都对应这样一个描述符，目前该结构占用32个字节，因此对于块大小为4k的文件系统来说，每个块可以存储128个块组描述符。由于GDT对于定位文件系统的元数据非常重要，因此和超级块一样，也对其进行了备份。GDT在每个块组(如果有备份)中内容都是一样的，其所占块数也是相同的。从上面的介绍可以看出块组中的元数据譬如块位图，inode位图,inode表其位置不是固定的，当然默认情况下，文件系统在创建时其位置在每个块组中都是一样的，如图2所示(假设按照稀疏方式存储)：

从图我们可以看出，每个块组大小相同，除了最后一个块组可能包含的块少一些(用虚线表达)。

(二) Online resizing工作机制
由上，文件系统所管理的块最终都是分派到块组中进行管理的。如果我们希望扩大文件系统的大小或者管理更多的物理块，那么需要将这些待添加的物理块分配到适当的块组中进行管理。很容易就能够想到，按照如下三个步骤一步步添加直到达到希望的文件系统大小为止：
1) 将物理块添加到最后一个块组中直到其满位置，如图2所示，我们可以将第n块块组中虚线部分填充满，然后增加文件系统可用的块数。
2) 如果GDT最后一个块还可以添加新的块组描述符，那么我们就添加一个新的块组。
3) 如果当前GDT中已经不能够添加新的块组了，那么我们需要新的块能够容纳块组描述符，对于该步骤，当前内核预留了一些块，用于存储块组描述符；当然这些预留块也是有限的，因此如果预留块耗尽，那么我们将采用meta block group来完成这个功能。下面我们将先看看当前内核是如何处理的。见图3

当文件系统在创建时考虑到将来在线调整文件系统大小的需要，预留了一些块，并且使用一个inode(其对应的inode号为7)来管理这些预留块，以免这些块被分配给其它文件使用了。因此对于步骤3，当我们需要新块来存储块组描述符时，我们将从预留的组描述符块中分配一个块给GDT，由于GDT和预留的组描述符块在物理上是相邻的，因此很容易和原先的GDT块合并起来。

当我们在创建新的块组时，需要考虑该块组是否需要存储超级块和GDT的备份，如果需要备份，那么拷贝备份，同时将预留块添加到预留的组描述符inode中，然后增加超级块的块组数，空闲块数以及空闲inode数，为了保证文件系统的一致性，需要这些操作要么都完成，要么都不完成，它由JBD的事务机制来保证。

(三) 使用meta block group
由于预留的组描述符有限，当我们需要文件系统增加到很大时，预留块可能已经耗尽，此时文件系统不能够增加，除非卸载文件系统，采用ext2prepare或者类似工具来预留块，但是文件系统在这段时间内将不能够使用，对于生产系统来说是不可接受的。因此我提交了使用meta block group来进行在线增长文件系统的补丁，使得文件系统在保持兼容的情况下，能够扩大其容量。

元块组的概念其实很早就出现在内核中了，但是直到linux 2.6.21内核并未得到很好的支持。元块组实际上是可以用一个组描述符块来进行描述的块组集。它的出现使得ext3的磁盘布局有了一定的变化，以往超级块后紧跟的是变长的GDT块，现在超级块(决定于是否是3,5,7的幂)和一个组描述符块存储在元块组的第一个，第二个和最后一个块组的开始处(见图4)。

在两种情况下我们可能会用到：
1) 文件系统创建时。用户可以指定将使用这种布局。
2) 当文件系统增长而且预留的组描述符块耗尽时。目前超级块中有一个域s_first_meta_bg用于描述第一个使用元块组的块组。

该方法非常高效同时保留了足够的冗余以防止异常情况。这种布局中GDT仅占用一个块，由于组描述符占用32个字节，对于块大小为4k的文件系统来说，每个元块组包含128个块组，可以管理16GB的空间，而且每个元块组中对于组描述符表都有3个备份。

对比图4与图3我们就能够发现，当增加新块组时，我们不需要给组描述符表预留空间，而是在当前文件系统后面直接添加新的元块组就可以了。

(四) 结论
由于我们在创建文件系统时无法很好的预测将来可能的容量，因此文件系统的在线增长功能是非常有必要的。特别是LVM的出现更大的刺激了该需求，请注意本文所谈到的文件系统的在线增长并未涉及到如何扩大分区或者磁盘的大小，读者可以自己先采用lvm或者类似的工具扩大分区或者卷的大小，然后再采用ext2resize或者类似工具来完成ext3或者ext4文件系统的在线增长，其在内核中的工作机制本文已经阐述，希望对读者能够有所帮助。

参考资料
l Andreas E. Dilger:Online ext2 and ext3 Filesystem Resizing. June 26th–29th, 2002
l Theodore Y. Ts’o: Planned Extensions to the Linux Ext2/Ext3 Filesystem. 2002 USENIX Annual Technical Conference
l Linux kernel 2.6.21 source code

Ext2/3块分配机制

磁盘延迟是影响文件系统性能的主要因素，现代文件系统总是试图将文件连续分布在文件系统上，这样尽可能减少磁头的移动。但是，如果文件系统按需分配块，当同一目录下的两个文件同时写，这两个文件的块分配将相互交叉。为了解决这个问题，一些文件系统使用了预分配技巧，通过预测哪些文件需要分配块，而提前分配这些块。

ext2预分配的在磁盘上完成，也就是说预分配块的信息记录到磁盘上，当分配一个新的磁盘块时，文件系统内部会预分配一些相邻的磁盘块出来，为了避免预分配的磁盘块很快填充了文件系统空间，每个inode一次最多只能够预分配7个磁盘块。这些信息在如下三种情况下扔弃掉：第一种，在释放inode(put_inode)时，第二种，遇到不连续写时，第三种在截取文件时。因此在umount时，进程有可能还在引用inode，文件的预分配信息没有释放掉，涉及到的块也没有回收，这就导致这些块在磁盘上已经进行了分配，但是它们却不存在于inode的块映射中，之后fsck将修补这些错误。

对于ext3来说，如果也采用这种方式，fsck不能够将这些预分配的块归还，因为ext3区别于ext2的地方就是减少这种检查时间，增强系统的可用性。但是禁止了预分配意味着同一目录下的两个文件同时分配块时会出现交叉，而且当使用extent来寻址时该问题变得更加严重。ext3在内存中进行块的预分配，这些信息并不写到磁盘上，我们仅在该inode的最后一个file关闭时才扔掉预留信息，所以我们在iput_final->ext3_clear_inode完成该工作，与ext2相比，它在每次调用iput()时都会释放(put_inode)。

1 ext2的块分配
我们先看看ext2文件系统中块的分配，当我们确定目标物理块goal之后，将调用ext2_alloc_block()(ext2/inode.c)函数进行分配,它主要执行如下步骤：
1) 如果该块已经预分配，那么非常好，直接分配返回。
2) 否则抛弃预分配的块，因为出现了不连续的写，调用ext2_new_block()函数分配新块。该函数首先在当前块组中搜索，如果当前块组中没有合适的，那么就在其它块组中进行查找。在当前块组中进行搜索时，首先看指定块goal是否空闲，如果空闲，那么直接返回,否则，在接下来的区间内(当前位置与第一个64对齐的位置间)查找，有空闲则返回,否则，查找8个空闲块的位置,否则，查找一个空闲块,找到这种空闲块之后将其设置为1。找到新块之后，那么我们进行预分配，在接下来的相邻块中查看是否有空闲块，如果有就将其分配，最多7个，同时将这些信息写到磁盘上。

2 ext3的块分配
ext3中块的搜索与ext2基本相同，不同点就是在于其预分配策略，前面已经大致介绍过ext3的预分配在内存中完成，而ext2是写到磁盘上，下面将做一详细介绍。

在ext3中这种策略叫预留，也就是说资源预留，块分配器为每个需要磁盘块的inode预留一定范围的磁盘块，这个区间叫预留窗口。以后该inode的块分配将从该窗口中进行，而不是从整个文件系统，当然每个inode只能够从自己的预留窗口中进行分配，而不能够从其它窗口进行分配。这样当同一目录下的多个文件同时写时可以减少文件分片。预留和ext2中采用的预分配最大的区别就是这些块仅仅在内存中预留，而不是在磁盘上，因此当系统宕掉后，块组中的位图不会出现不一致的情况。

当inode第一次申请新块时，块分配的结构，用于描述预留窗口的信息以及相关信息被分配而且与inode相连接。块分配器将搜寻一个满足如下3个准则的块区域：
1) 该区域基于当前ext2/3的块放置算法，离理想的目标块不远。
2) 该区域不能够和其它inode的预留窗口相交叉。
3) 该区域至少有一个空闲块。
当inode增长时，在预留窗口的空闲块最终将会被消耗完，此时我们需要为该inode创建一个新的窗口，最好是在找到最后一个目标块之后。

所有的预留窗口都通过文件系统的红黑树来进行索引，这样块分配器能够快速决定特定的块或者区域是否已经为某个inode预留，这棵树上的所有操作都用文件系统的全局自旋锁来保护。
初始时，每个inode默认的预留的窗口大小设置成8块。如果预留分配器检测出inode的块分配是连续的，那么它将动态的增大那个inode的窗口大小。如果应用程序在文件创建之前能够知道文件大小，那么它可以发出一个ioctl命令将窗口大小设置成预期的文件大小，这样可以马上预留块。

在申请一个新块时，首先从inode自己的预留窗口进行分配，如果没有预留窗口，我们不会像ext2中那样到位图中去搜索空闲块，而是搜索预留列表来检测其是否在其它预留窗口中，我们将试图分配一个从目标块开始的预留窗口，然后在预留窗口中进行块的分配。

ext3中块分配由ext3_new_blocks()函数来完成，先在goal所在块组进行分配，如果分配不成功，那么就在其它块组中进行分配，如果依旧不成功，那么我们将不使用预留窗口机制(前两者首先会在预留窗口中进行分配)，因为此时系统中可能存在空闲块，但是这些块都被预留窗口预留了，所以我们将不使用预留窗口，也许有可能分配到空闲块。

Ext3目录索引的实现机制

旧版本的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, &amp;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, &amp;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, &amp;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。