(詹榮開 [email protected])
Linux用數據結構dentry來描述fs中與某個文件索引節點相鏈接的一個目錄項(可以是文件,也可以是目錄)。
每個dentry對象都屬於下列幾種狀態之一：
（1）未使用（unused）狀態：該dentry對象的引用計數d_count的值為0，但其d_inode指針仍然指向相關的的索引節點。該目錄項仍然包含有效的信息，只是當前沒有人引用他。這種dentry對象在回收內存時可能會被釋放。
（2）正在使用（inuse）狀態：處於該狀態下的dentry對象的引用計數d_count大於0，且其d_inode指向相關的inode對象。這種dentry對象不能被釋放。
（3）負（negative）狀態：與目錄項相關的inode對象不復存在（相應的磁盤索引節點可能已經被刪除），dentry對象的d_inode指針為NULL。但這種dentry對象仍然保存在dcache中，以便後續對同一文件名的查找能夠快速完成。這種dentry對象在回收內存時將首先被釋放。
Linux為了提高目錄項對象的處理效率，設計與實現了目錄項高速緩存（dentry cache，簡稱dcache），它主要由兩個數據結構組成：
1. 哈希鏈表dentry_hashtable：dcache中的所有dentry對象都通過d_hash指針域鏈到相應的dentry哈希鏈表中。
2. 未使用的dentry對象鏈表dentry_unused：dcache中所有處於“unused”狀態和“negative”狀態的dentry對象都通過其d_lru指針域鏈入dentry_unused鏈表中。該鏈表也稱為LRU鏈表。
目錄項高速緩存dcache是索引節點緩存icache的主控器（master），也即dcache中的dentry對象控制著icache中的inode對象的生命期轉換。無論何時，只要一個目錄項對象存在於dcache中（非negative狀態），則相應的inode就將總是存在，因為inode的引用計數i_count總是大於0。當dcache中的一個dentry被釋放時，針對相應inode對象的iput()方法就會被調用。
1 目錄項對象的SLAB分配器緩存dentry_cache
dcache是建立在dentry對象的slab分配器緩存dentry_cache（按照Linux的命名規則，似乎應該是dentry_cachep，^_^）之上的。因此，目錄項對象的創建和銷毀都應該通過kmem_cache_alloc()函數和kmem_cache_free（）函數來進行。
dentry_cache是一個kmem_cache_t類型的指針。它定義在dcache.c文件中：
static kmem_cache_t *dentry_cache;
這個slab分配器緩存是在dcache機制的初始化例程dcache_init()中通過調用函數kmem_cache_create()來創建的。
1．1 分配接口
dcache在kmem_cache_alloc（）的基礎上定義兩個高層分配接口：d_alloc()函數和d_alloc_root()函數，用來從dentry_cache slab分配器緩存中為一般的目錄項和根目錄分配一個dentry對象。
其中，d_alloc（）的實現如下：
#define NAME_ALLOC_LEN(len) ((len+16) & ~15)
struct dentry * d_alloc(struct dentry * parent, const struct qstr *name)
{
char * str;
struct dentry *dentry;
dentry = kmem_cache_alloc(dentry_cache, GFP_KERNEL);
if (!dentry)
return NULL;
if (name->len > DNAME_INLINE_LEN-1) {
str = kmalloc(NAME_ALLOC_LEN(name->len), GFP_KERNEL);
if (!str) {
kmem_cache_free(dentry_cache, dentry);
return NULL;
}
} else
str = dentry->d_iname;
memcpy(str, name->name, name->len);
str[name->len] = 0;
atomic_set(&dentry->d_count, 1);
dentry->d_flags = 0;
dentry->d_inode = NULL;
dentry->d_parent = NULL;
dentry->d_sb = NULL;
dentry->d_name.name = str;
dentry->d_name.len = name->len;
dentry->d_name.hash = name->hash;
dentry->d_op = NULL;
dentry->d_fsdata = NULL;
INIT_LIST_HEAD(&dentry->d_vfsmnt);
INIT_LIST_HEAD(&dentry->d_hash);
INIT_LIST_HEAD(&dentry->d_lru);
INIT_LIST_HEAD(&dentry->d_subdirs);
INIT_LIST_HEAD(&dentry->d_alias);
if (parent) {
dentry->d_parent = dget(parent);
dentry->d_sb = parent->d_sb;
spin_lock(&dcache_lock);
list_add(&dentry->d_child, &parent->d_subdirs);
spin_unlock(&dcache_lock);
} else
INIT_LIST_HEAD(&dentry->d_child);
dentry_stat.nr_dentry++;
return dentry;
}
NOTE:
（1）如果文件名的長度大於15，則調用kmalloc（）函數從slab分配器中為文件名分配內存；否則將文件名拷貝到d_iname數組中，並讓b_name.name指針指向d_iname。
（2）引用計數d_count將被初始化為1，其余成員都被初始化為NULL。
（3）如果父目錄的dentry被給定，則設置d_parent指針指向父目錄的dentry對象（因此必須通過dget函數來增加父目錄dentry對象的引用計數）。並通過d_child指針域將這個dentry對象鏈入父目錄dentry對象的d_subdirs鏈表。否則，將d_child初始化為指向自身。
（4）將dcache統計信息中的dentry對象總數nr_dentry值加1。
函數d_alloc_root（）用來為fs的根目錄（並不一定是系統全局文件系統的根“／”）分配dentry對象。它以根目錄的inode對象指針為參數，如下所示：
struct dentry * d_alloc_root(struct inode * root_inode)
{
struct dentry *res = NULL;
if (root_inode) {
res = d_alloc(NULL, &(const struct qstr) { "/", 1, 0 });
if (res) {
res->d_sb = root_inode->i_sb;
res->d_parent = res;
d_instantiate(res, root_inode);
}
}
return res;
}
（1）可以看出，首先還是必須調用d_alloc()函數來從dentry_cache slab分配器緩存中分配一個dentry對象。注意！特別之處在於d_alloc（）函數的調用參數。
（2）然後，將所分配的dentry對象的d_parent指針設置為指向自身。NOTE！這一點是判斷一個dentry對象是否是一個fs的根目錄的唯一准則（include／linux／dcache.h）：
＃define IS_ROOT（x） （（x）＝＝（x）－>d_parent）
（3）最後，通過調用d_instantiate（）函數來實例化這個dentry對象。
函數d_instantiate用於向dentry結構中填寫inode信息，因此該函數會將一個dentry對象從negative狀態轉變為inuse狀態。如下所示：
void d_instantiate(struct dentry *entry, struct inode * inode)
{
spin_lock(&dcache_lock);
if (inode)
list_add(&entry->d_alias, &inode->i_dentry);
entry->d_inode = inode;
spin_unlock(&dcache_lock);
}
NOTE! 函數d_instantiate（）假定在被調用之前，調用者已經增加了inode的引用計數。
1．2 釋放接口
目錄項緩存dcache定義了兩個高層釋放接口：d_free()函數和dentry_iput()函數。其中，d_free函數用來將dcache中不使用的dentry對象釋放回dentry_cache slab分配器緩存；而dentry_iput（）函數則用來釋放一個dentry對象對一個inode對象的引用關聯。
函數d_free()首先調用dentry對象操作方法中的d_release（）函數（如果定義了的話），通常在d_release()函數中釋放dentry->fsdata數據。然後，用dname_external（）函數判斷是否已經為目錄項名字d_name分配了內存，如果是，則調用kfree（）函數釋放d_name所占用的內存。接下來，調用kmem_cache_free()函數釋放這個dentry對象。最後，修改dcache統計信息中的dentry對象總數（減1）。其源碼如下：
/* no dcache_lock, please */
static inline void d_free(struct dentry *dentry)
{
if (dentry->d_op && dentry->d_op->d_release)
dentry->d_op->d_release(dentry);
if (dname_external(dentry))
kfree(dentry->d_name.name);
kmem_cache_free(dentry_cache, dentry);
dentry_stat.nr_dentry--;
}
其中，dname_external（）是定義在dcache.h頭文件中的內聯函數，如下：
static __inline__ int dname_external(struct dentry *d)
{
return d->d_name.name != d->d_iname;
}
而dentry_iput（）函數則主要用於在調用d_free()函數釋放一個dentry對象之前，釋放該dentry對象與相應inode對象的關聯，從而將一個dentry對象轉變為negative狀態。主要包括如下幾項任務：（1）將這個dentry對象從相應inode對象的別名鏈表i_dentry中摘除；（2）解除自旋鎖dcache_lock；（3）調用dentry的操作方法d_iput()函數（如果有的話），或者iput()方法。
該函數與d_instantiate（）函數是相反的，如下：
static inline void dentry_iput(struct dentry * dentry)
{
struct inode *inode = dentry->d_inode;
if (inode) {
dentry->d_inode = NULL;
list_del_init(&dentry->d_alias);
spin_unlock(&dcache_lock);
if (dentry->d_op && dentry->d_op->d_iput)
dentry->d_op->d_iput(dentry, inode);
else
iput(inode);
} else
spin_unlock(&dcache_lock);
}
NOTE：
（1）如果定義了dentry方法d_iput()，則dentry_iput()通過調用d_iput()方法來釋放inode對象，否則就通過iput()來釋放inode對象。
（2）dentry_iput（）函數假定被調用時調用者已經持有了dcache_lock鎖。因此它在返回之前對該自旋鎖進行解鎖。
2 dcache數據結構
Linux通過在dentry_cache slab分配器緩存上定義了各種dentry鏈表來有效地管理目錄項對象，從而實現dcache機制。它們包括：
1. dentry對象的哈希鏈表dentry_hashtable。
2. dentry對象的LRU鏈表dentry_unused。
3. 每個索引節點對象的別名鏈表i_dentry。每個非negative狀態的dentry對象都通過d_alias指針域鏈入其對應的inode對象的別名鏈表i_dentry中。
4. 父目錄dentry對象的子目錄項（目錄或文件）鏈表d_subdirs。每個dentry對象都通過d_child指針域鏈入其父目錄dentry對象的子目錄項鏈表d_subdirs中。
2．1 哈希鏈表dentry_hashtable
dcache中的每個dentry對象都通過其中的d_hash指針域鏈入哈希鏈表dentry_hashtable,以便加快對dentry對象的查找速度。哈希鏈表dentry_hashtable定義在dcache.c文件中，如下：
#define D_HASHBITS d_hash_shift
#define D_HASHMASK d_hash_mask
static unsigned int d_hash_mask;
static unsigned int d_hash_shift;
static struct list_head *dentry_hashtable;
指針dentry_hashtable定義了dentry哈希鏈表表頭數組的首地址，而d_hash_mask和d_hash_shift的含義與icache中的inode哈希鏈表的i_hash_mask和i_hash_shift的含義相同，這裡就不再解釋。
每一個dentry對象都通過其父目錄dentry對象的指針和其文件名的哈希值hash來唯一地確定它所屬的哈希鏈表的表頭指針，這是通過d_hash函數來完成的：
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);
}
每個目錄項文件名的哈希值是通過full_name_hash()函數（定義在include/linux/dcache.h文件中）來計算的，如下所示：
/* 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);
}
可以看出，該函數又向下調用partial_name_hash()函數和end_name_hash（）函數來完成哈希值的計算工作。
n dcache的初始化
函數dcache_init()完成整個dcache機制的初始化工作，它主要做兩件事：（1）哈希鏈表表頭數組的初始化；（2）slab分配器緩存dentry_cache的創建。該函數的實現思想與icache的初始化函數inode_init()相似，這裡就不再詳細分析了。如下所示：
static void __init dcache_init(unsigned long mempages)
{
struct list_head *d;
unsigned long order;
unsigned int nr_hash;
int i;
/*
* A constructor could be added for stable state like the lists,
* but it is probably not worth it because of the cache nature
* of the dcache.
* If fragmentation is too bad then the SLAB_HWCACHE_ALIGN
* flag could be removed here, to hint to the allocator that
* it should not try to get multiple page regions.
*/
dentry_cache = kmem_cache_create("dentry_cache",
sizeof(struct dentry),
0,
SLAB_HWCACHE_ALIGN,
NULL, NULL);
if (!dentry_cache)
panic("Cannot create dentry cache");
#if PAGE_SHIFT < 13
mempages >>= (13 - PAGE_SHIFT);
#endif
mempages *= sizeof(struct list_head);
for (order = 0; ((1UL = 0);
printk("Dentry-cache hash table entries: %d (order: %ld, %ld bytes)\n",
nr_hash, order, (PAGE_SIZE d_count))
BUG();
atomic_inc(&dentry->d_count);
}
return dentry;
}
從上述實現可以看出，對於引用那些d_count＝0的dentry對象，我們決不應該使用dget()函數，而是應該使用dget_locked()函數。這是因為：引用一個d_count＝0的dentry對象，將使該dentry對象從unused狀態轉變為inuse狀態，該dentry狀態也必須從LRU鏈表中脫離，而在操作dcache鏈表時是必須先持有自旋鎖dcache_lock的。函數dget()並不對調用者由任何調用假設，相反，dget_locked()函數則假定調用者在調用它之前已經持有自旋鎖dentry_lock。
函數dget_locked（）定義在dcache.c中：
struct dentry * dget_locked(struct dentry *dentry)
{
return __dget_locked(dentry);
}
可以看出，內部函數__dget_locked()完成實際的工作：
/* This should be called _only_ with dcache_lock held */
static inline struct dentry * __dget_locked(struct dentry *dentry)
{
atomic_inc(&dentry->d_count);
if (atomic_read(&dentry->d_count) == 1) {
dentry_stat.nr_unused--;
list_del(&dentry->d_lru);
INIT_LIST_HEAD(&dentry->d_lru); /* make "list_empty()" work */
}
return dentry;
}
3．2 釋放接口dput
函數dput()用於釋放對一個dentry對象的引用。該函數的核心就是將dentry對象的引用計數d_count減1。如果d_count減1後還不為0，則dput直接返回即可；否則就將該dentry對象放到LRU鏈表中，或直接釋放掉（在該dentry對象未鏈入哈希鏈表的情況下）。其源碼如下：
void dput(struct dentry *dentry)
{
if (!dentry)
return;
repeat:
if (!atomic_dec_and_lock(&dentry->d_count, &dcache_lock))
return;
/* dput on a free dentry? */
if (!list_empty(&dentry->d_lru))
BUG();
/*
* AV: ->d_delete() is _NOT_ allowed to block now.
*/
if (dentry->d_op && dentry->d_op->d_delete) {
if (dentry->d_op->d_delete(dentry))
goto unhash_it;
}
/* Unreachable? Get rid of it */
if (list_empty(&dentry->d_hash))
goto kill_it;
list_add(&dentry->d_lru, &dentry_unused);
dentry_stat.nr_unused++;
/*
* Update the timestamp
*/
dentry->d_reftime = jiffies;
spin_unlock(&dcache_lock);
return;
unhash_it:
list_del_init(&dentry->d_hash);
kill_it: {
struct dentry *parent;
list_del(&dentry->d_child);
/* drops the lock, at that point nobody can reach this dentry */
dentry_iput(dentry);
parent = dentry->d_parent;
d_free(dentry);
if (dentry == parent)
return;
dentry = parent;
goto repeat;
}
}
NOTE：
（1）首先判斷是否對LRU鏈表中的一個dentry對象進行dput操作，如果是則報錯。
（2）如果定義了dentry操作方法d_delete（），則應該按照d_delete（）方法的功能描述首先調用它來刪除這個dentry獨享。如果d_delete（）返回非0值（執行出錯），則跳轉到unhash_it部分，將這個dentry對象從哈希鏈表中摘除，並將他釋放回slab分配器緩存。
（3）判斷這個dentry對象是否鏈在哈希鏈表中，如果沒有，則跳轉到kill_it部分，將這個dentry對象釋放掉。
（4）如果這個dentry對象是鏈在哈希鏈表中的，則將它移到dentry_unused鏈表的首部，並將統計信息的nr_unused域加1，最後更新這個dentry對象的最近一次引用時間戳d_reftime，然後就直接返回。
（5）unhash_it部分：將這個dentry對象從哈希鏈表中摘除。
（6）kill_it部分：這一部分將dentry對象釋放回給dentry_cache slab分配器緩存，其過程如下：
n 首先，將dentry對象從它的父目錄dentry的d_subdirs鏈表中摘除。
n 然後，調用dentry_iput()函數釋放其對相應inode對象的引用。
n 保存父目錄dentry對象的指針，然後調用d_free（）函數將這個dentry對象釋放回dentry_cache slab分配器緩存。
n 如果這個dentry對象的父目錄指針指向自身，這說明這個dentry對象就是fs的根目錄，因此就可以返回了。否則，就要對父目錄dentry對象做一次dput()操作。
4 對哈希鏈表的操作
（1） 向哈希鏈表中增加一個dentry對象
函數d_rehash()實現這一功能，它首先通過d_hash()函數找到這個dentry對象應該掛到哪一個哈希鏈表中，然後設置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);
}
（2） 從哈希鏈表中摘除一個dentry對象
函數d_drop（）實現這一點，如下所示（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中還定義了一個函數d_unhashed()，用來測試一個dentry對象是否沒有鏈接在哈希鏈表中，如下：
static __inline__ int d_unhashed(struct dentry *dentry)
{
return list_empty(&dentry->d_hash);
}
5 對LRU鏈表的管理與操作
對LRU鏈表dentry_unused的管理和維護主要體現在兩點上：
（1）當哈希鏈表中的一個dentry對象從inuse狀態轉變為unused狀態時，應該將他插入到LRU鏈表的首部，具體請參見dput()函數的實現。
（2）當系統內存緊張時，應該釋放LRU鏈表中的一些dentry對象，且通常是釋放LRU鏈表尾部的dentry對象（因為它們是最近最少使用的）。但是也可以根據指定條件釋放LRU中特定的dentry對象，因此在這之前要做一個挑選過程，並由這一過程將所選中的dentry對象移到dentry_unused鏈表的尾部。這一機制也稱為dcache的壓縮（shrink）機制。
下面將詳細分析dcache的shrink機制實現。
5．1 prune_one_dentry()函數
該函數實現從LRU鏈表中釋放一個指定的dentry對象。這是一個靜態的內部函數，它通常被別的函數調用。NOTE! Prune_one_dentry()函數假定被調用之前，調用者已經將dentry對象從LRU鏈表中摘除，並且持有自旋鎖dcache_lock。因此，它所要做的事情就是：①將這個dentry對象從哈希鏈表中摘除；②將這個dentry對象從其父目錄對象的d_subdirs鏈表中摘除；③用dentry_iput()函數釋放對相應inode對象的引用；④用d_free()釋放這個dentry對象；⑤對父目錄dentry對象做一次dput操作。
該函數的源碼如下：
void prune_dcache(int count)
{
spin_lock(&dcache_lock);
for (;;) {
struct dentry *dentry;
struct list_head *tmp;
tmp = dentry_unused.prev;
if (tmp == &dentry_unused)
break;
list_del_init(tmp);
dentry = list_entry(tmp, struct dentry, d_lru);
/* If the dentry was recently referenced, don't free it. */
if (dentry->d_flags & DCACHE_REFERENCED) {
dentry->d_flags &= ~DCACHE_REFERENCED;
list_add(&dentry->d_lru, &dentry_unused);
count--;
continue;
}
dentry_stat.nr_unused--;
/* Unused dentry with a count? */
if (atomic_read(&dentry->d_count))
BUG();
prune_one_dentry(dentry);
if (!--count)
break;
}
spin_unlock(&dcache_lock);
}
5．2 prune_dcache()函數
該函數用於實現從LRU鏈表的尾部開始倒序釋放指定個數的dentry對象。它從尾部開始掃描LRU鏈表，如果被掃描的dentry對象設置了DCACHE_REFERENCED標志，則讓其繼續留在LRU鏈表中，否則就將其從LRU鏈表中摘除，然後調用prune_one_dentry()函數釋放該dentry對象。其源碼如下（dcache.c）：
void prune_dcache(int count)
{
spin_lock(&dcache_lock);
for (;;) {
struct dentry *dentry;
struct list_head *tmp;
tmp = dentry_unused.prev;
if (tmp == &dentry_unused)
break;
list_del_init(tmp);
dentry = list_entry(tmp, struct dentry, d_lru);
/* If the dentry was recently referenced, don't free it. */
if (dentry->d_flags & DCACHE_REFERENCED) {
dentry->d_flags &= ~DCACHE_REFERENCED;
list_add(&dentry->d_lru, &dentry_unused);
count--;
continue;
}
dentry_stat.nr_unused--;
/* Unused dentry with a count? */
if (atomic_read(&dentry->d_count))
BUG();
prune_one_dentry(dentry);
if (!--count)
break;
}
spin_unlock(&dcache_lock);
}
上述兩個函數prune_one_dentry()和prune_dcache（）是dcache的shrink機制的實現基礎。在此基礎上，Linux實現了根據指定條件壓縮dcache的高層接口函數：①shink_dcache_sb()——根據指定的超級塊對象，壓縮dcache；②shrink_dcache_parent()——根據指定的父目錄dentry對象，壓縮dcache；③shrink_dcache_memory()——根據優先級壓縮dcache。
5．3 shrink_dcache_sb()函數
該函數釋放dcache的LRU鏈表中屬於某個特定超級塊對象的dentry對象。該函數的實現過程主要是兩次遍歷dentry_unused鏈表：
①第一次遍歷過程將屬於指定超級塊對象的dentry對象移到dentry_unused鏈表的首部。
②第二次遍歷則將屬於指定超級塊對象、且d_count＝0的dentry對象釋放掉（通過prune_one_dentry函數）。個人認為，判斷條件d_count＝0是不必要的，當然偏執一點也沒什麼不好：）
函數源碼如下：
void shrink_dcache_sb(struct super_block * sb)
{
struct list_head *tmp, *next;
struct dentry *dentry;
/*
* Pass one ... move the dentries for the specified
* superblock to the most recent end of the unused list.
*/
spin_lock(&dcache_lock);
next = dentry_unused.next;
while (next != &dentry_unused) {
tmp = next;
next = tmp->next;
dentry = list_entry(tmp, struct dentry, d_lru);
if (dentry->d_sb != sb)
continue;
list_del(tmp);
list_add(tmp, &dentry_unused);
}
/*
* Pass two ... free the dentries for this superblock.
*/
repeat:
next = dentry_unused.next;
while (next != &dentry_unused) {
tmp = next;
next = tmp->next;
dentry = list_entry(tmp, struct dentry, d_lru);
if (dentry->d_sb != sb)
continue;
if (atomic_read(&dentry->d_count))
continue;
dentry_stat.nr_unused--;
list_del(tmp);
INIT_LIST_HEAD(tmp);
prune_one_dentry(dentry);
goto repeat;
}
spin_unlock(&dcache_lock);
}
5．4 shrink_dcache_parent()函數
該函數釋放LRU鏈表中屬於給定父目錄對象的子dentry對象。實現源碼如下：
void shrink_dcache_parent(struct dentry * parent)
{
int found;
while ((found = select_parent(parent)) != 0)
prune_dcache(found);
}
可以看出，shrink_dcache_parent()函數首先通過調用select_parent()函數來從LRU鏈表中查找父目錄parent的子目錄對象，並將這些子dentry對象移到LRU鏈表的尾部，並返回所找到的子dentry對象的個數（這一步是為調用prune_dcache()函數做准備的）；然後，調用prune_dcache()函數將LRU鏈表尾部的子dentry對象釋放掉。
函數select_parent()是在dcache.c中實現的內部函數，他根據給定的參數parent，在LRU鏈表中查找父目錄parent的子目錄對象，並將這些子dentry對象移到LRU鏈表的尾部，並返回所找到的子dentry對象的個數。源代碼如下：
static int select_parent(struct dentry * parent)
{
struct dentry *this_parent = parent;
struct list_head *next;
int found = 0;
spin_lock(&dcache_lock);
repeat:
next = this_parent->d_subdirs.next;
resume:
while (next != &this_parent->d_subdirs) {
struct list_head *tmp = next;
struct dentry *dentry = list_entry(tmp, struct dentry, d_child);
next = tmp->next;
if (!atomic_read(&dentry->d_count)) {
list_del(&dentry->d_lru);
list_add(&dentry->d_lru, dentry_unused.prev);
found++;
}
/*
* Descend a level if the d_subdirs list is non-empty.
*/
if (!list_empty(&dentry->d_subdirs)) {
this_parent = dentry;
#ifdef DCACHE_DEBUG
printk(KERN_DEBUG "select_parent: descending to %s/%s, found=%d\n",
dentry->d_parent->d_name.name, dentry->d_name.name, found);
#endif
goto repeat;
}
}
/*
* All done at this level ... ascend and resume the search.
*/
if (this_parent != parent) {
next = this_parent->d_child.next;
this_parent = this_parent->d_parent;
#ifdef DCACHE_DEBUG
printk(KERN_DEBUG "select_parent: ascending to %s/%s, found=%d\n",
this_parent->d_parent->d_name.name, this_parent->d_name.name, found);
#endif
goto resume;
}
spin_unlock(&dcache_lock);
return found;
}
這是一個算法比較復雜的函數，對他的NOTE如下：
（1）由於所有在以parent為根的部分目錄樹中的目錄項都是parent目錄的子目錄項（直接或間接），而且dentry對象的父、子關系是級聯的，因此函數select_parent()必須搜索出LRU鏈表中所有parent目錄的直接或間接子目錄項。
為此，函數維護一個指針this_parent，表示當前正在對部分目錄樹（以parent為根）中的那一個中間目錄（非葉節點）進行搜索。初始時，this_parent指針指向parent，因此整個搜索過程是從上到下、從左到右的一個樹型結構遍歷過程。
（2）while循環對當前父目錄this_parent的子目錄項鏈表d_subdirs進行搜索。如果鏈表中dentry對象的d_count=0，則將該dentry對象移到LRU鏈表的表尾，並將返回值found加1。然後判斷這個dentry對象的d_subdirs鏈表是否為空（也即是否為目錄樹的中間節點），如果不為空，則讓this_parent指針指向這個dentry對象，並跳轉回repeat部分，從而對這個dentry對象的子目錄項鏈表開始進行搜索。
（3）如果當前while循環中測試的每一個dentry對象都沒有d_subdirs鏈表，也即this_parent目錄的子目錄項全部為目錄樹的葉節點，則在完成對這一層次的搜索後，退出while循環。函數接下來考慮上升搜索層次（直到this_parent=parent），於是它將next指針修改為this_parent->d_child.next（當前父目錄的兄弟），然後將this_parent指針修改為this_parent->d_parent，然後跳轉到resume部分，於是搜索過程就從上一層次正確地繼續。
（4）is_parent=parent的情況下退出while循環則宣告整個搜索過程結束。
5．5 shringk_dcache_memory()函數
當我們需要內存，但又不知道具體需要多少時，就可以調用這個函數來壓縮dcache所占用的內存。該函數通常被kswapd守護進程所調用。如下：
void shrink_dcache_memory(int priority, unsigned int gfp_mask)
{
int count = 0;
/*
* Nasty deadlock avoidance.
*
* ext2_new_block->getblk->GFP->shrink_dcache_memory->prune_dcache->
* prune_one_dentry->dput->dentry_iput->iput->inode->i_sb->s_op->
* put_inode->ext2_discard_prealloc->ext2_free_blocks->lock_super->
* DEADLOCK.
*
* We should make sure we don't hold the superblock lock over
* block allocations, but for now:
*/
if (!(gfp_mask & __GFP_IO))
return;
if (priority)
count = dentry_stat.nr_unused / priority;
prune_dcache(count);
kmem_cache_shrink(dentry_cache);
}
優先級參數priority值越大（優先級越低），表明對內存的需要就越不迫切。因此prune_dcache（）函數釋放的dentry對象個數就越少。
6 對dentry對象的VFS操作接口
VFS實現了幾個對dcache中的dentry對象的操作函數，下面我們列舉一些：
1. d_invalidate()——是一個dcache中的dentry對象無效。該函數的核心就是要將指定的dentry對象從哈希鏈表中摘除。
2. d_find_alias()——為指定inode對象找到一個位於哈希鏈表中的、且在該索引節點的別名鏈表i_dentry中的dentry對象。
3. d_prune_aliases()——釋放指定inode對象的別名鏈表i_dentry中未使用的dentry對象。
4. have_submounts()——查看在參數parent指定的部分目錄樹中是否至少有一個安裝點。
5. d_lookup()——在參數parent指定的父目錄中查找名字為name的目錄項。
6. d_validate()——驗證一個dentry對象的有效性。
7. d_delete()——刪除一個dentry對象。實際上是將這個dentry對象轉變為negative狀態或unused狀態。
8. d_move()——移動一個dentry對象。
9. __d_path()——得到一個dentry對象的全路徑名。
10. is_subdir()——判斷一個dentry對象是否是另一個dentry對象的子孫。
11. find_inode_number()——在父目錄dir中，查找是否存在參數name指定的名字的目錄項，並返回對應inode的索引節點。
7 小結
由於dentry是一種純軟件數據結構，不存在對應的磁盤數據。因此，與icache機制和buffer cache機制不同，dcache中沒有如何同步一個dentry對象的機制。
