(詹榮開 [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對象的機制。