6.2.8 The directory cache

ディレクトリキャッシュはExt2ファイルシステムが由来である.Linux-1.1.37以降,これはVFSの一部であり,すべてのファイルシステムの実装で利用できる.キャッシュはファイルを開くときに必要なディレクトリの読み込み速度を上げるエントリを保持する.キャッシュ内のエントリは以下の構造体である.

struct dir_cache_entry {
    struct hash_list h;
    unsigned long dev;
    unsigned long dir;
    unsigned long version;
    unsigned long ino;
    unsigned char name_len;
    char name[DCACHE_NAME_LEN];
    struct dir_cache_entry ** lru_head;
    struct dir_cache_entry * next_lru,  * prev_lru;
};

DCACHE_NAME_LENまでのディレクトリエントリのみがキャッシュに保持される.しかし,最も頻繁に使用されるファイルとディレクトリの名前は短いだろうから,これは厳しい制約というわけではない.

ディレクトリキャッシュは2段階のキャッシュであり,各段階がLRU(Least Recently Used)アルゴリズムにしたがって動作する.各段階は,2重連結循環リストで構成され,常にDCACHE_SIZEエントリを含む.level1_headlevel2_headは,各リスト内の,次に上書きされるであろう最も古い要素を指す.構造体のlru_head要素はこれに対するポインタでもあり,すべてのキャッシュエントリがキャッシュのどの段階にあるのかを知ることができる.

すでにキャッシュに入っているエントリを素早く見つけるために,Linuxカーネルではオープンハッシュリストが定期的に使われる.ハッシュキーはデバイス番号devとディレクトリのinode番号dirおよびその名前のハッシュ関数からなる.

ディレクトリキャッシュにアクセスするために,2つの関数が取り込まれた.

dirディレクトリをもつ長さlenのディレクトリ名nameをキャッシュに入れる.inoはディレクトリエントリのinode番号である.

void dcache_add(struct inode * dir, const char * name, int len, unsigned long ino)
{
    struct hash_list * hash;
    struct dir_cache_entry *de;

    if (len > DCACHE_NAME_LEN)
        return;
    hash = hash_table + hash_fn(dir->i_dev, dir->i_ino, namehash(name,len));
    /*
     * 作成されたエントリがすでにキャッシュ内にあるなら,
     * リスト内で最も若いエントリに変更され,関数が終了する.
     */
    if ((de = find_entry(dir, name, len, hash)) != NULL) {
        de->ino = ino;
        update_lru(de);
        return;
    }
    /* 新しいエントリは常に段階1に挿入される.*/
    de = level1_head;
    /* level1_headは最も古い要素を指す */
    level1_head = de->next_lru;
    /* 最初にハッシュテーブルから削除され…… */
    remove_hash(de);
    /* 新しいディレクトリエントリのデータで上書きされる */
    de->dev = dir->i_dev;
    de->dir = dir->i_ino;
    de->version = dir->i_version;
    de->ino = ino;
    de->name_len = len;
    memcpy(de->name, name, len);
    /* 新しいエントリがハッシュテーブルに追加される */
    add_hash(de, hash);
}

この関数はキャッシュへ問い合わせるために使われる.

int dcache_lookup(struct inode * dir, const char * name, int len, unsigned long * ino)
{
    struct hash_list * hash;
    struct dir_cache_entry *de;

    if (len > DCACHE_NAME_LEN)
        return 0;
    hash = hash_table + hash_fn(dir->i_dev, dir->i_ino, namehash(name,len));
    de = find_entry(dir, name, len, hash);
    if (!de)
        return 0; /* エントリ名が見つからない*/
    /*ディレクトリエントリが見つかったのであれば…… */
    /* 見つかったディレクトリエントリのinode番号が引数inoに渡される */
    *ino = de->ino;
    /* 段階2に昇格される. */
    move_to_level2(de, hash);
    return 1;
}

static inline void move_to_level2(struct dir_cache_entry * old_de, struct hash_list * hash)
{
    struct dir_cache_entry * de;

    if (old_de->lru_head == &level2_head) {
        update_lru(old_de);
        return;
    }   
    de = level2_head;
    level2_head = de->next_lru;
    remove_hash(de);
    COPYDATA(old_de, de);
    add_hash(de, hash);
}

inode構造体のi_version構成要素は特に重要である.この構成要素は,キャッシュエントリ内のバージョン構成要素と比較され,この2つが一致する場合のみディレクトリキャッシュが有効である.すべてのファイルシステムの実装では,ディレクトリのinodeが変更されるたびに,このバージョンがインクリメントされることに注意しなければいけない.それ以外の場合,この関数はキャッシュに存在しないディレクトリエントリを提供する可能性がある.しかし,このバージョンは以下のように簡単に更新できる.

dir->i_version = ++event;

eventinclude/linux/sched.h にて符号なしのlong型として定義されている.

extern unsigned long event;

これだけあれば多分重複はしないだろう.

ディレクトリキャッシュはファイルシステムに固有のlookup関数を高速化することを目指しているが,現在はExt2およびISO9660ファイルシステムでのみ使用されている.