目錄項(xiàng)緩存與散列表

所謂緩存，是指把存在于磁盤(pán)中的操作系統(tǒng)運(yùn)行時(shí)頻繁使用到的信息讀取到內(nèi)存中去，以提高 CPU 讀取這些信息的速度。所以目錄項(xiàng)的緩存就是指把存在于磁盤(pán)上的目錄項(xiàng)信息讀取到內(nèi)存中去，而這些目錄信息就是一個(gè)個(gè)的 dentry 結(jié)構(gòu)。當(dāng)某個(gè)進(jìn)程運(yùn)行時(shí)用到某個(gè)目錄項(xiàng)，但在內(nèi)存中卻沒(méi)有相應(yīng)的 dentry 結(jié)構(gòu)，就需要在內(nèi)存中建立 ( 所謂的建立實(shí)際是從磁盤(pán)上把相應(yīng)的 dentry 結(jié)構(gòu)讀取到內(nèi)存中去 ) 一個(gè)與該目錄項(xiàng)對(duì)應(yīng)的 dentry 結(jié)構(gòu)。由于在操作系統(tǒng)運(yùn)行的過(guò)程中，用到的目錄項(xiàng)很多，因此讀入到內(nèi)存中的 dentry 結(jié)構(gòu)就非常多，故有必要對(duì)已讀入到內(nèi)存中的所有 dentry 結(jié)構(gòu)進(jìn)行管理，內(nèi)核中的 dentry_hashtable 便是用于此目的的。

       首先分析一下 dentry 的結(jié)構(gòu)，便可知內(nèi)核是如何在內(nèi)存中管理 dentry 結(jié)構(gòu)的。

       Dentry 結(jié)構(gòu)中有 6 個(gè) list_head, 即 d_vfsmnt 、 d_hash 、 d_lru 、 d_child 、 d_subdirs 、和 d_alias 。注意， list_head 既可以用來(lái)作為一個(gè)隊(duì)列的頭部，也可以用來(lái)將其所在的數(shù)據(jù)結(jié)構(gòu)掛入到某個(gè)隊(duì)列中。其中 d_vfsmnt 僅在該 dentry 結(jié)構(gòu)為一個(gè)安裝點(diǎn)時(shí)才使用。一個(gè) dentry 結(jié)構(gòu)一經(jīng)建立就通過(guò)其 d_hash 掛入雜湊表 dentry_hashtable 中的某個(gè)隊(duì)列里，當(dāng)共享計(jì)數(shù)變?yōu)?0 時(shí)則通過(guò) d_lru 掛入隊(duì)列 dentyr_unused 中。同時(shí)， dentry 結(jié)構(gòu)通過(guò) d_child 掛入到其父節(jié)點(diǎn) ( 上一層目錄 ) 的 d_subdirs 隊(duì)列中，同時(shí)又通過(guò)指針 d_parent 指向父目錄的 dentry 結(jié)構(gòu)。而它自己各個(gè)子目錄的 dentry 結(jié)構(gòu)則在它本身的 d_subdirs 隊(duì)列中。一個(gè)有效的 dentry 結(jié)構(gòu)必定有一個(gè)相應(yīng)的 inode 結(jié)構(gòu)，這是因?yàn)橐粋€(gè)目錄項(xiàng)要么代表一個(gè)文件，要么就代表著一個(gè)目錄，而目錄實(shí)際上也是文件。所以，只要是有效的 dentry 結(jié)構(gòu)，則其指針 d_inode 必定指向一個(gè) inode 結(jié)構(gòu)。可是，反過(guò)來(lái)一個(gè) inode 卻可能對(duì)應(yīng)著不止一個(gè) dentry 結(jié)構(gòu)，也就是說(shuō)，一個(gè)文件可以有不止一個(gè)文件名 ( 或路徑名 ) 。這是因?yàn)橐粋€(gè)已經(jīng)建立的文件可以被連接 (link) 到其他文件名。所以，在 inode 結(jié)構(gòu)中有個(gè)隊(duì)列 i_dentry ，凡是代表著這個(gè)文件的所有目錄項(xiàng)都通過(guò)其 dentry 結(jié)構(gòu)中的 d_alias 掛入相應(yīng) inode 結(jié)構(gòu)中的 i_dentry 隊(duì)列。此外， dentry 結(jié)構(gòu)中還有指針 d_sb, 指向其所在設(shè)備的超級(jí)塊 super_block 數(shù)據(jù)結(jié)構(gòu)，以及指針 d_op, 指向特定文件系統(tǒng) ( 指文件格式 ) 的 dentry_operations 結(jié)構(gòu)。也許可以說(shuō)， dentry 結(jié)構(gòu)是文件系統(tǒng)的核心數(shù)據(jù)結(jié)構(gòu)，也是文件訪問(wèn)和為文件訪問(wèn)而做的文件路徑搜索操作樞紐。

       下面是一個(gè)簡(jiǎn)要的總結(jié)：

1、 每個(gè) dentry 結(jié)構(gòu)都通過(guò)隊(duì)列頭 d_hash 鏈入雜湊表 dentry_hashtable 中的某個(gè)隊(duì)列里。

2、 共享計(jì)數(shù)為 0 的 dentry 結(jié)構(gòu)都通過(guò)隊(duì)列頭 d_lru 鏈入 LRU 隊(duì)列 dentry_unused ，在隊(duì)列中等待釋放或者“東山再起”。

3、 每個(gè) dentry 結(jié)構(gòu)都通過(guò)指針 d_inode 指向一個(gè) inode 數(shù)據(jù)結(jié)構(gòu)。但是多個(gè) dentry 結(jié)構(gòu)可以指向同一個(gè) inode 數(shù)據(jù)結(jié)構(gòu)。

4、 指向同一個(gè) inode 數(shù)據(jù)結(jié)構(gòu)的 dentry 結(jié)構(gòu)都通過(guò)隊(duì)列頭 d_alias 鏈接在一起，都在該 inode 結(jié)構(gòu)的 i_dentry 隊(duì)列中。

5、 每個(gè) dentry 結(jié)構(gòu)都通過(guò)指針 d_parent 指向其父目錄節(jié)點(diǎn)的 dentry 結(jié)構(gòu)，并通過(guò)隊(duì)列頭 d_child 跟同一目錄中的其他節(jié)點(diǎn)的 dentry 結(jié)構(gòu)鏈接在一起，都在父目錄節(jié)點(diǎn)的 d_subdirs 隊(duì)列中。

6、 每個(gè) dentry 結(jié)構(gòu)都通過(guò)指針 d_sb 指向一個(gè) super_block 數(shù)據(jù)結(jié)構(gòu)。

7、 每個(gè) dentry 結(jié)構(gòu)都通過(guò)指針 d_op 指向一個(gè) dentry_operations 數(shù)據(jù)結(jié)構(gòu)。

8、 每個(gè) dentry 結(jié)構(gòu)都有個(gè)隊(duì)列頭 d_vfsmnt, 用于文件系統(tǒng)的安裝，詳見(jiàn)“文件系統(tǒng)的安裝與拆卸”。

在分析完 dentry 數(shù)據(jù)結(jié)構(gòu)以后，現(xiàn)在來(lái)看一下 dentry_hashtable 雜湊表的 散列算法。

dentry_hashtable 是由 list_head 組成的數(shù)組 , 它們與 dentry->d_hash 相環(huán)接 , 形成短鏈 , 散列表中的 dentry 將均分布于這些短鏈上 ; 散列表的索引確定于父目錄項(xiàng)地址和目錄名的 hash 值 ; dentry_hashtable 的尺寸由系統(tǒng)內(nèi)存大小分配 , 每 4M 內(nèi)存分配一個(gè)頁(yè)面 , 每個(gè)頁(yè)面具有 512 項(xiàng)索引 ;

哈希鏈表 dentry_hashtable 定義在 dcache.c 文件中，如下：

static struct list_head *dentry_hashtable;

d_hash(dentry,hash) 為散列函數(shù) , 它將 dentry 地址和 hash 值相組合 , 映射到 dentry_hashtable 表中 , 返回相應(yīng)的散列鏈 ;

d_rehash(dentry) 將 dentry 加入散列表 ;

d_drop(dentry) 將 dentry 從散列表中刪除 ;

d_lookup(dentry,qstr) 在散列中找出以 dentry 作為父目錄項(xiàng) , 名稱(chēng)為 qstr 的目錄項(xiàng) .

下面分別介紹一下這幾個(gè)函數(shù)：

一、 d_hash(dentry,hash)

每一個(gè) dentry 對(duì)象都通過(guò)其父目錄 dentry 對(duì)象的指針和其文件名的哈希值 hash 來(lái)唯一地確定它所屬的哈希鏈表的表頭指針，這是通過(guò) d_hash 函數(shù)來(lái)完成的：
　　 static inline struct list_head * d_hash(struct dentry * parent, unsigned long hash)
　　 {
　　 hash += (unsigned long) parent / L1_CACHE_BYTES;
　　 hash = hash ^ (hash >> D_HASHBITS) ^ (hash >> D_HASHBITS*2);
　　 return dentry_hashtable + (hash & D_HASHMASK);
　　 }
　　每個(gè)目錄項(xiàng)文件名的哈希值是通過(guò) full_name_hash() 函數(shù)（定義在 include/linux/dcache.h 文件中）來(lái)計(jì)算的，如下所示：
　　 /* Compute the hash for a name string. */
　　 static __inline__ unsigned int full_name_hash(const unsigned char * name, unsigned int len)
　　 {
　　 unsigned long hash = init_name_hash();
　　 while (len--)
　　 hash = partial_name_hash(*name++, hash);
　　 return end_name_hash(hash);
　　 }
　　可以看出，該函數(shù)又向下調(diào)用 partial_name_hash() 函數(shù)和 end_name_hash （）函數(shù)來(lái)完成哈希值的計(jì)算工作。

二、 d_rehash(dentry)

向哈希鏈表中增加一個(gè) dentry 對(duì)象
　　函數(shù) d_rehash() 實(shí)現(xiàn)這一功能，它首先通過(guò) d_hash() 函數(shù)找到這個(gè) dentry 對(duì)象應(yīng)該掛到哪一個(gè)哈希鏈表中，然后設(shè)置 d_hash 指針。如下所示（ dcache.c ）：
　　 void d_rehash(struct dentry * entry)
　　 {
　　 struct list_head *list = d_hash(entry->d_parent, entry->d_name.hash);
　　 spin_lock(&dcache_lock);
　　 list_add(&entry->d_hash, list);
　　 spin_unlock(&dcache_lock);
　　 }

三、 d_drop(dentry)

從哈希鏈表中摘除一個(gè) dentry 對(duì)象
　　函數(shù) d_drop （）實(shí)現(xiàn)這一點(diǎn)，如下所示（ dcache.h ）：
　　 static __inline__ void d_drop(struct dentry * dentry)
　　 {
　　 spin_lock(&dcache_lock);
　　 list_del(&dentry->d_hash);
　　 INIT_LIST_HEAD(&dentry->d_hash);
　　 spin_unlock(&dcache_lock);
　　 }
　　頭文件 dcache.h 中還定義了一個(gè)函數(shù) d_unhashed() ，用來(lái)測(cè)試一個(gè) dentry 對(duì)象是否沒(méi)有鏈接在哈希鏈表中，如下：
　　 static __inline__ int d_unhashed(struct dentry *dentry)
　　 {
　　 return list_empty(&dentry->d_hash);
　　 }

四、 d_lookup(dentry,qstr)

在散列中找出以 dentry 作為父目錄項(xiàng) , 名稱(chēng)為 qstr 的目錄項(xiàng)

struct dentry * d_lookup(struct dentry * parent, struct qstr * name)
{
        unsigned int len = name->len;
        unsigned int hash = name->hash;
        const unsigned char *str = name->name;
        struct list_head *head = d_hash(parent,hash);
        struct list_head *tmp;

        spin_lock(
        tmp = head->next;
        for (;;) {
                struct dentry * dentry = list_entry(tmp, struct dentry, d_hash);
                if (tmp == head)
                        break;
                tmp = tmp->next;
                if (dentry->d_name.hash != hash)
                        continue;
                if (dentry->d_parent != parent)
                        continue;
                if (parent->d_op  parent->d_op->d_compare) {
                        ; 如果文件系統(tǒng)提供了目錄名比較的方法
                        if (parent->d_op->d_compare(parent,  name))
                                continue;
                } else {
                        if (dentry->d_name.len != len)
                                continue;
                        if (memcmp(dentry->d_name.name, str, len))
                                continue;
                }
                __dget_locked(dentry); 增加dentry的引用計(jì)數(shù)
                dentry->d_flags |= DCACHE_REFERENCED;
                spin_unlock(
                return dentry;
        }
        spin_unlock(
        return NULL;
)