在内核中,查找是必不可少的,比如说内核管理这么多用户进程,现在要快速定位
某一个进程,这儿需要查找,还有,一个进程的地址空间中有多个虚存区,内核要快速
定位进程地址空间的某个虚存区,这儿也需要查找,等等。其中用的最多就是基于树的
查找-------->红黑树。和基于计算的查找------->哈希查找。两者的查找的效率高,而且
适应内核的情况,而基于线性表的查找-------->二分查找,尽管效率高但不能适应内核
里面的情况,现在版本的内核几乎不可能使用数组管理一些数据,这太原始了。而二分
查找必须使用数组,所以内核中不用二分查找。
--------------------------------------------------------------------------------
1,内核哈希查找的初始化。(用于进程的快速查找)
-
/*
-
* The pid hash table is scaled according to the amount of memory in the
-
* machine. From a minimum of 16 slots up to 4096 slots at one gigabyte or
-
* more.
-
*/
-
void __init pidhash_init(void)
-
{
-
int i, pidhash_size;
//为数组开辟空间
-
pid_hash = alloc_large_system_hash("PID", sizeof(*pid_hash), 0, 18,
-
HASH_EARLY | HASH_SMALL,
-
&pidhash_shift, NULL, 4096);
-
pidhash_size = 1 << pidhash_shift;//数组的长度
-
-
for (i = 0; i < pidhash_size; i )
-
INIT_HLIST_HEAD(&pid_hash[i]);//将数组中的指针都初始化为NULL
-
}
初始化思想很简单,就是建立一个哈希数组(自己定义的一个概念,哈希表中的那个数组),
并将该数组进行初始化,该函数在start_kernel中被调用,至于数组的长度,可以写个小的
内核模块很简单就可以把它的大小读出来。pidhash_shift是个全局的变量,没有导出,可以
在内核符号表中找到其地址,cat /proc/kallsyms | grep pidhash_shift 把该值打印出来就
知道数组的大小了。从上面的代码可以看出,这个数组的长度还依赖于机器内存的大小,一般
内存环境该数组的长度都为4096.下面有个小模块可以读出pidhash_shift的值。
--------------------------------------------------------------------------------------------
-
1 #include <linux/module.h>
-
2 #include <linux/kernel.h>
-
3 #include <linux/init.h>
-
4 #include <linux/moduleparam.h>
-
5 #include <linux/list.h>
-
6 #include <linux/hash.h>
-
7
-
//cat /proc/kallsyms | grep pidhash_shift
-
8 unsigned int *p_shift = (unsigned int *)0xc176ab0c;
-
9
-
10 static int __init hash_size_init(void)
-
11 {
-
12 ---printk("pidhash_shift----------------->%u\n",*p_shift);
-
13 ---return 0;
-
14 }
-
15
-
16 static void __exit hash_size_exit(void)
-
17 {
-
18 printk("<1>exit ---------------------!\n");
-
19 }
-
20
-
21 module_init(hash_size_init);
-
22 module_exit(hash_size_exit);
-
23 MODULE_LICENSE("GPL");
--------------------------------------------------------------------------------------------
2,哈希函数的建立。
哈希查找肯定离不开哈希函数,其实哈希函数就是一个数学函数,用来将实体分布在
哈希表中,前少冲突的发生。
-
40 #define pid_hashfn(nr, ns) -\
-
41 ---hash_long((unsigned long)nr (unsigned long)ns, pidhash_shift)
-
26 #define hash_long(val, bits) hash_32(val, bits)
-
19 /* 2^31 2^29 - 2^25 2^22 - 2^19 - 2^16 1 */
20 #define GOLDEN_RATIO_PRIME_32 0x9e370001UL
-
-
57 static inline u32 hash_32(u32 val, unsigned int bits)
-
58 {
-
59 ---/* On some cpus multiply is faster, on others gcc will do shifts */
-
60 ---u32 hash = val * GOLDEN_RATIO_PRIME_32;
-
61
-
62 ---/* High bits are more random, so use them. */
-
63 ---return hash >> (32 - bits);
-
64 }
由此看出,内核将进程分布到哈希表的索引是由进程号和命名空间两个决定的,使用的
数学函数也比较复杂。我想这也是为了减少冲突的发生。
--------------------------------------------------------------------------------------------
3,如何避免哈希冲突。
内核里面的哈希一般都是使用连地址法解决冲突,这种方式在应用上很可行,使用
双向链表把冲突的节点都链接起来。
-----------------------------------------------------------------------------------------
4,在创建进程的过程中往哈希表中插入进程的“索引”。
进程在alloc_pid函数中将struct pid插入到哈希表中。
调用过程见下图:
----------------------------------------------------------------------------------------------
alloc_pid中的代码:
-
spin_lock_irq(&pidmap_lock);
-
for ( ; upid >= pid->numbers; --upid)
-
hlist_add_head_rcu(&upid->pid_chain,
-
&pid_hash[pid_hashfn(upid->nr, upid->ns)]);
-
spin_unlock_irq(&pidmap_lock);
进程将创建好的struct pid中的nr和ns作为哈希函数的输入,从而计算出哈希数组的下标,
然后使用头插法,将struct hlist_node *pid_chain节点插入到链表中。
----------------------------------------------------------------------------------------------
5,使用哈希查找快速定位struct pid
在内核函数中,有个find_vpid函数,可以通过进程的pid快速找到进程的struct pid。
其中就是在建立好的哈希表中进行查找。
-
struct pid *find_pid_ns(int nr, struct pid_namespace *ns)
-
{
-
struct hlist_node *elem;
-
struct upid *pnr;
-
-
hlist_for_each_entry_rcu(pnr, elem,
-
&pid_hash[pid_hashfn(nr, ns)], pid_chain)
-
if (pnr->nr == nr && pnr->ns == ns)
-
return container_of(pnr, struct pid,
-
numbers[ns->level]);
-
-
return NULL;
-
}
find_vpid就是直接调用find_pid_ns,该函数的两个参数,一个是进程pid,一个是命名空间ns
通过这两个就可以使用哈希函数定位到哈希数组的下标索引,然后遍历该数组单元的链表即可找到
进程的struct pid
----------------------------------------------------------------------------------------------
阅读(1611) | 评论(0) | 转发(0) |