幼儿体验职业的好处:文件系统-目录项缓存与散列表
来源:百度文库 编辑:偶看新闻 时间:2024/10/02 17:15:33
目录项缓存与散列表
所谓缓存,是指把存在于磁盘中的操作系统运行时频繁使用到的信息读取到内存中去,以提高 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;
)