Refer to <

内核源代码情景分析

>> and <>

Having any problems, send mails to viloner@163.com

目录项缓存与散列表

所谓缓存，是指把存在于磁盘中的操作系统运行时频繁使用到的信息读取到内存中去，以提高

CPU

读取这些信息的速度。所以目录项的缓存就是指把存在于磁盘上的目录项信息读取到内存中去，而这些目录信息就是一个个的

dentry

结构。当某个进程运行时用到某个目录项，但在内存中却没有相应的

dentry

结构，就需要在内存中建立

(

所谓的建立实际是从磁盘上把相应的

dentry

结构读取到内存中去

)

一个与该目录项对应的

dentry

结构。由于在操作系统运行的过程中，用到的目录项很多，因此读入到内存中的

dentry

结构就非常多，故有必要对已读入到内存中的所有

dentry

结构进行管理，内核中的

dentry_hashtable

便是用于此目的的。

首先分析一下

dentry

的结构，便可知内核是如何在内存中管理

dentry

结构的。

Dentry

结构中有

6

个

list_head,

即

d_vfsmnt

、

d_hash

、

d_lru

、

d_child

、

d_subdirs

、和

d_alias

。注意，

list_head

既可以用来作为一个队列的头部，也可以用来将其所在的数据结构挂入到某个队列中。其中

d_vfsmnt

仅在该

dentry

结构为一个安装点时才使用。一个

dentry

结构一经建立就通过其

d_hash

挂入杂凑表

dentry_hashtable

中的某个队列里，当共享计数变为

0

时则通过

d_lru

挂入队列

dentyr_unused

中。同时，

dentry

结构通过

d_child

挂入到其父节点

(

上一层目录

)

的

d_subdirs

队列中，同时又通过指针

d_parent

指向父目录的

dentry

结构。而它自己各个子目录的

dentry

结构则在它本身的

d_subdirs

队列中。一个有效的

dentry

结构必定有一个相应的

inode

结构，这是因为一个目录项要么代表一个文件，要么就代表着一个目录，而目录实际上也是文件。所以，只要是有效的

dentry

结构，则其指针

d_inode

必定指向一个

inode

结构。可是，反过来一个

inode

却可能对应着不止一个

dentry

结构，也就是说，一个文件可以有不止一个文件名

(

或路径名

)

。这是因为一个已经建立的文件可以被连接

(link)

到其他文件名。所以，在

inode

结构中有个队列

i_dentry

，凡是代表着这个文件的所有目录项都通过其

dentry

结构中的

d_alias

挂入相应

inode

结构中的

i_dentry

队列。此外，

dentry

结构中还有指针

d_sb,

指向其所在设备的超级块

super_block

数据结构，以及指针

d_op,

指向特定文件系统

(

指文件格式

)

的

dentry_operations

结构。也许可以说，

dentry

结构是文件系统的核心数据结构，也是文件访问和为文件访问而做的文件路径搜索操作枢纽。

下面是一个简要的总结：

1、

每个

dentry

结构都通过队列头

d_hash

链入杂凑表

dentry_hashtable

中的某个队列里。

2、

共享计数为

0

的

dentry

结构都通过队列头

d_lru

链入

LRU

队列

dentry_unused

，在队列中等待释放或者“东山再起”。

3、

每个

dentry

结构都通过指针

d_inode

指向一个

inode

数据结构。但是多个

dentry

结构可以指向同一个

inode

数据结构。

4、

指向同一个

inode

数据结构的

dentry

结构都通过队列头

d_alias

链接在一起，都在该

inode

结构的

i_dentry

队列中。

5、

每个

dentry

结构都通过指针

d_parent

指向其父目录节点的

dentry

结构，并通过队列头

d_child

跟同一目录中的其他节点的

dentry

结构链接在一起，都在父目录节点的

d_subdirs

队列中。

6、

每个

dentry

结构都通过指针

d_sb

指向一个

super_block

数据结构。

7、

每个

dentry

结构都通过指针

d_op

指向一个

dentry_operations

数据结构。

8、

每个

dentry

结构都有个队列头

d_vfsmnt,

用于文件系统的安装，详见“文件系统的安装与拆卸”。

在分析完

dentry

数据结构以后，现在来看一下

dentry_hashtable

杂凑表的

散列算法。

dentry_hashtable

是由

list_head

组成的数组

,

它们与

dentry->d_hash

相环接

,

形成短链

,

散列表中的

dentry

将均分布于这些短链上

;

散列表的索引确定于父目录项地址和目录名的

hash

值

; dentry_hashtable

的尺寸由系统内存大小分配

,

每

4M

内存分配一个页面

,

每个页面具有

512

项索引

;

哈希链表

dentry_hashtable

定义在

dcache.c

文件中，如下：

static struct list_head *dentry_hashtable;

d_hash(dentry,hash)

为散列函数

,

它将

dentry

地址和

hash

值相组合

,

映射到

dentry_hashtable

表中

,

返回相应的散列链

;

d_rehash(dentry)

将

dentry

加入散列表

;

d_drop(dentry)

将

dentry

从散列表中删除

;

d_lookup(dentry,qstr)

在散列中找出以

dentry

作为父目录项

,

名称为

qstr

的目录项

.

下面分别介绍一下这几个函数：

一、

d_hash(dentry,hash)

每一个

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

()函数来完成哈希值的计算工作。

二、

d_rehash(dentry)

向哈希链表中增加一个

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);

}

三、

d_drop(dentry)

从哈希链表中摘除一个

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);

}

四、

d_lookup(dentry,qstr)

在散列中找出以

dentry

作为父目录项

,

名称为

qstr

的目录项

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) {

; 如果文件系统提供了目录名比较的方法

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的引用计数

dentry->d_flags |= DCACHE_REFERENCED;

spin_unlock(

return dentry;

}

spin_unlock(

return NULL;

)