分析文件名检索的散列算法

系统在解析路径时,使用dentry_hashtable来缓冲每一节路径名对应的dentry目录项;
dentry_hashtable是由list_head组成的数组,它们与dentry->d_hash相环接,形成短链,散列表中的
dentry将均分布于这些短链上;
散列表的索引确定于父目录项地址和目录名的hash值;
dentry_hashtable的尺寸由系统内存大小分配,每4M内存分配一个页面,每个页面具有512项索引;
d_hash(dentry,hash)为散列函数,它将dentry地址和hash值相组合,映射到dentry_hashtable表中,
返回相应的散列链;
d_rehash(dentry)将dentry加入散列表;
d_drop(dentry)将dentry从散列表中删除;
d_lookup(dentry,qstr)在散列中找出以dentry作为父目录项,名称为qstr的目录项.

系统用下面的方法计算某节路径名的hash值:

	unsigned long hash;

	struct qstr this;

	unsigned int c;



	hash = init_name_hash();

	do {

		name++;

		hash = partial_name_hash(c, hash);

		c = *(const unsigned char *)name;

	} while (c && (c != '/'));



	this.len = name - (const char *) this.name;

	this.hash = end_name_hash(hash);

	...



有关的代码如下:

static unsigned int d_hash_mask;

static unsigned int d_hash_shift;

static struct list_head *dentry_hashtable;



#define init_name_hash() 0



static __inline__ unsigned long partial_name_hash(unsigned long c, unsigned long
prevhash)

{

	prevhash = (prevhash << 4) | (prevhash >> (8*sizeof(unsigned long)-4));

	return prevhash ^ c;

}



/* Finally: cut down the number of bits to a int value (and try to avoid losing bits)
*/

static __inline__ unsigned long end_name_hash(unsigned long hash)

{

	if (sizeof(hash) > sizeof(unsigned int))

		hash += hash >> 4*sizeof(hash);

	return (unsigned int) hash;

}

#define D_HASHBITS     d_hash_shift

#define D_HASHMASK     d_hash_mask

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

}

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

}

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

}

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(&dcache_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, &dentry->d_name, 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(&dcache_lock);

		return dentry;

	}

	spin_unlock(&dcache_lock);

	return NULL;

}

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 << order) << PAGE_SHIFT) < mempages; order++)



	do {

		unsigned long tmp;



		nr_hash = (1UL << order) * PAGE_SIZE /

			sizeof(struct list_head);

		d_hash_mask = (nr_hash - 1);



		tmp = nr_hash;

		d_hash_shift = 0;

		while ((tmp >>= 1UL) != 0UL)

			d_hash_shift++;



		dentry_hashtable = (struct list_head *)

			__get_free_pages(GFP_ATOMIC, order);

	} while (dentry_hashtable == NULL && --order >= 0);

	; 如果order太大,超过了__get_free_pages最大可分配尺寸,则减小order的值重试.



	printk("Dentry-cache hash table entries: %d (order: %ld, %ld bytes)\n",

			nr_hash, order, (PAGE_SIZE << order));



	if (!dentry_hashtable)

		panic("Failed to allocate dcache hash table\n");



	d = dentry_hashtable;

	i = nr_hash;

	do {

		INIT_LIST_HEAD(d);

		d++;

		i--;

	} while (i);

}

对opera的注释加点解释，读起来可能会更省力些。 

1.为什么要用这个算法 

例如要构造一个文件 /usr/local/cross/my_comp 
这时要沿着上面这个文件名开始依次找直到cross的数据结构，也就是要找到 

/usr/ 
/usr/local/ 
/usr/local/cross/ 
对应的数据结构dentry 

假定我们已经找到/usr/对应的dentry, 现在必须能够从local找到它对应的dentry,这时就要从 
名字---->dentry 
的快速映射，在Linux中一般用哈希映射。如图： 

 


2. 查找方法 

首先，通过d_hash粗分类,找到"local"所在的链表，然后顺序向下一一匹配。 


3.一些操作如opera所述 

4.初始化 

首先通过__get_free_pages获得一些页面，这些页面构成了所有链表头数组。 



我们的