Rev.1を表示中。最新版はこちら。

ext3はディレクトリにハッシュを持たす事で、ディレクトリ内の検索効率を高めています。ハッシュはディレクトリのルートブロック（inode内のブロック位置が0)に収められています。このブロックはstruct dx_rootのフォーマットをしいています。

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;
  	u8 unused_flags;
   } info;
   struct dx_entry
   {
       __le32 hash;
       __le32 block;
   } entries[0]; 
};

struct fake_dirent
{
   __le32 inode;
   __le16 rec_len;
   u8 name_len;
   u8 file_type;
};

struct fake_dirent dot/struct fake_dirent dotdotには./..が、struct dx_root_infoにはハッシュ情報が、そしてstruct dx_entryに、個々のdentryの対するブロック位置のハッシュテーブルが設定されます。ディレクトリエントリーそのものは、それ以外のブロック下に配置されることになります。dir_entryはext2と同じです。従ってstruct fake_dirent dotdotのrec_lenをブロックの終端にすることで、ext2からみたらこのブロックは、./..保持するディレクトリエントリーとして、処理する事ができるわけです。（たぶん）

ext3で実装されているのが、ハッシュツリー(htree)と言うもので、要はハッシュ値を昇順に配置したものです。この実装はハッシュ値がらブロック位置を検索するdx_probe関数で読み取れます。entriesはルートブロックのハッシュテーブル群を収めて先頭アドレスで、hashはext3fs_dirhash関数で、dentryからhinfo->hash_versionのハッシュ形式に従ってハッシュした値です。

static struct dx_frame *
dx_probe(struct dentry *dentry, struct inode *dir,
struct dx_hash_info *hinfo, struct dx_frame *frame_in, int *err)
{
  :
  :
   hinfo->hash_version = root->info.hash_version;
   hinfo->seed = EXT3_SB(dir->i_sb)->s_hash_seed;
   if (dentry)
       ext3fs_dirhash(dentry->d_name.name, dentry->d_name.len, hinfo);
       hash = hinfo->hash;
   }
   entries = (struct dx_entry *) (((char *)&root->info) +
   root->info.info_length);
   while (1)
   {
       count = dx_get_count(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->%u\n", 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;
:
}

 :

}
ハッシュツリーは、上部の二重ループ内の以下の処理になります。

while (p <= q)
{
   m = p + (q - p)/2;
   dxtrace(printk("."));
   if (dx_get_hash(m) > hash)
       q = m - 1;
   else
       p = m + 1;
}

になります。目的とするハッシュ値に対して、ハッシュテーブルの範囲の半分のインデックス(m = p + (q - p)/2)のハッシュ値と、その大小をチェック(if (dx_get_hash(m) > hash)します。もし、ターゲットのハッシュ値の方が小さければ、今度はハッシュテーブルの先頭から、そのの半分までの範囲で同じ処理をしていきます。反対に大きければ、先頭を半分の位置にして、そこからテーブルエンドまでの範囲で同じ処理をしていき、その範囲を半分づつにしながら、最終的な位置を求めているようです。

補足

ext3のインデックスハッシュ回りの実装よくわかりません。ラチ空きそうもないので、とりあずという事です。