Refer to <<linux
内核源代码情景分析
>> and <<Linux kernel Version:2.4.0>>
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;
)