实易热讯 :: 实易文章 :: Unix/Linux

By 阿开

1. 目录项缓存dcache
　　Author:詹荣开
　　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.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.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.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锁。因此它在返回之前对该自旋锁进行解锁。

1.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中。

　　1.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)
",
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;
}

　　1.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()操作。

1.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);
}

1.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机制实现。

　　1.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);
}

　　1.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。

　　1.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);
}

　　1.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
",
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
",
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循环则宣告整个搜索过程结束。

　　1.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对象个数就越少。

1.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的索引节点。

1.7 小结
　　由于dentry是一种纯软件数据结构，不存在对应的磁盘数据。因此，与icache机制和buffer cache机制不同，dcache中没有如何同步一个dentry对象的机制。