By沈东良(良少)http://blog.csdn.net/shendl
Linux内核的实现,大量使用了数据结构,包括了数组、链表和散列表。其中用的最多的是双向循环链表。Linux内核使用的是自己定义的链表和散列表,简单而高效,使用方法也非常的别具一格。 研究Linux内核的链表和散列表对于看懂Linux内核源代码有重要的意义。本文基于kernel2.6.39版本进行分析。
Linux的链表和散列表定义在include/linux/types.h文件中structlist_head { 223 struct list_head *next, *prev; 224}; 225 226structhlist_head { 227 struct hlist_node *first; 228}; 229 230structhlist_node { 231 struct hlist_node *next, **pprev; 232}; 233
list_head就是使用最为广泛的双向循环链表。这个数据结构可以说是LinuxKernel的基石,大量内核源代码使用了这个数据结构。 hlist_head和hlist_node常常用于散列表中。
Linux的链表和散列表的操作函数的定义在include/linux/list.h文件中初始化双向循环链表,只有一个元素的双向循环链表,next和prev指向自身。
staticinline voidINIT_LIST_HEAD(structlist_head *list)
初始化散列表的链表。 空的散列表链表的first==NULL。每一个散列表链表的元素初始化时next和pprev指针都是NULL,而不是指向自身。 我们可以看到,散列表链表hlist_node虽然和双向循环链表list_head一样,都有两个指针,但有本质的区别。 散列表链表hlist_node不是循环链表。它有头和尾,是单向的链表。 散列表链表hlist_node之所以有两个指针,是为了提高插入和删除链表的效率。hlist_node的插入,只需要一个相邻的hlist_head或者hlist_node节点即可。它的删除,只需要它本身即可定位其相邻的前后两个元素。
570 脱离链表的元素的状态
staticinline void__list_add(structlist_head *new,
/*
92/**
散列表链表的脱离链表代码:
90staticinline void__hlist_del(structhlist_node *n) 看看LIST_POISON1和LIST_POISON2是何方神圣。
16
表示链表元素是未初始化的,既不在链表中,也没有经过初始化,不应该使用。
遍历Linuxkernel的链表时删除元素的方法在list_head双向循环链表的迭代中删除元素的方法,见我之前写的《遍历Linuxkernel的链表时删除元素的方法》一文,地址:http://blog.csdn.net/shendl/article/details/6397898
散列表链表也有同样的问题:
665
链表元素的使用方式和container_of宏
LinuxKernel的链表使用方式和其他一般的链表的使用方式大相径庭! 一般的链表,总是有一个链表结构体,它的内部有指针指向实际的对象。一般是这样子的: struct node{ struct node * next; struct node * prev; void * data; }; 然后有一些操作函数,负责使用这样的链表元素实现链表。这应该算是非常标准的链表形式了。大量已有的各类语言的链表都是类似这样实现的。
再回头看看LinuxKernel的链表定义:
structlist_head { 咦!实际的数据元素呢?这种链表有什么用?一堆指针链接在一起,却没有数据,有个毛用!
:-)确实挺奇怪的,放眼全球各类语言,也没有哪一个数据结构库的链表是这样子的!
我们看看kernel是怎样使用这些链表的:
structinode { …... 这些链表的实例成了数据结构的属性! 是的,kernel的链表的使用方式和一般的链表是相反的。不是数据在链表内,而是链表在数据内!
inode的i_hash散列表链表,把inode实例链接到一个全局的inode散列表中,fs/inode.c文件定义了一些操作散列表的方法:
/** 我们看到,这些函数调用了我们熟悉的hlist_node的操作函数,对inode的hlist_node类型属性进行了处理。
这样就把具有相同hash值的inode的i_hash链接到了一个链表上。
回到我们的老问题,我们怎么样才能从链表元素找到包括该链表元素的真实对象呢?毕竟真实对象才是我们的链表真正需要链接的东西。
再看一个函数:
1082/*
hlist_for_each_entry是怎么把inode找到的? /** *hlist_for_each_entry - iterate over list of given type *@tpos: thetype * to use as a loop cursor. 类型的指针类型的循环变量,也就是真正的值。 *@pos: the&structhlist_node to use as a loop cursor.循环链表的变量 *@head: the head for your list.表头 *@member: the name of the hlist_node within thestruct.类型内的成员 */ #definehlist_for_each_entry(tpos, pos, head, member) \ for(pos = (head)->first; \ pos && ({ prefetch(pos->next); 1;}) && \ ({tpos = hlist_entry(pos,typeof(*tpos),member); 1;}); \ pos = pos->next)
上面的typeof(*tpos),typeof是GCC的扩展,现在好像是C99的特性,用来获得对象的类型。 这里,使用*得到指针指向的对象,然后取得类型,就得到了对象的真正类型!
传递的是:包含list_head/hlist_node的结构体类型和对应的属性名i_hash,这些信息有什么用?
344/**
谜底在就在container_of宏:
606/**
这里使用了C语言隐秘的技巧:
606 const typeof( ((type *)0)->member ) *__mptr = (ptr);
(type*)0把地址0强制类型转换为包含hlist_node链表元素的结构体的指针类型。 我们知道地址0是不允许使用的,会造成崩溃。但是这里并没有给地址0开头的数据赋值,所以没有关系。
然后求其->member成员的类型,得到了一个hlist_node*类型的临时变量,给它赋值,就是该链表元素的地址。
15#defineoffsetof(TYPE,MEMBER)
((size_t) &((TYPE *)0)->MEMBER)
这里,故伎重演,利用地址0进行强制类型转换,转换成结构体类型的指针,然后求i_hash成员的地址。成员地址-0就得到了该成员相对于结构体实例的距离。
实际的链表元素的地址-链表元素在结构体内的相对偏移,就得到了该结构体实例的地址。然后(type*)强制类型转换。 606 tpos= hlist_entry(pos,typeof(*tpos),member); 1;}); 这个赋值语句,被宏替换,变成: 606 tpos=container_of(pos,typeof(*tpos),member); 1;}); 又被宏替换,成了:
606 tpos=({ consttypeof( ((typeof(*tpos)*)0)->member ) *__mptr = (pos);(typeof(*tpos) *)( (char *)__mptr -offsetof(typeof(*tpos),member) );})
这就是最后得到的C语句。 这里左式是待赋值的变量,右式是一个语句块! 怎么可以呢? 确实可以! 这里()把语句块包围起来,使整个语句块能够参与表达式。右式的返回值是语句块内最后一个表达式的值。 至此,我们能够从结构体内的链表元素属性,反向得到结构体实例!Linux Kernel双向循环链表和散列表链表的谜底揭开了! LinuxKernel如何实现散列表前文中,我们说了,hlist_head和hlist_node这两个数据结构是用来实现散列表的。我把它们称为散列表链表,因为它们实现的是散列表的一部分:链表。 散列表,逻辑上是<hash,value>这样一个表格形式的数据对的集合。
让我们先考虑一个散列表的伪实现: 如,考虑一个散列表查询函数的原型示例:void* lookup(void * obj,int hash); 这个函数首先通过hash在散列表中搜索,然后会得到[0,1...n]个value。 因为hash可能会出现冲突,多个不同对象的hash值相同。 然后可以根据查询对象的其他特征进行匹配,找出真正需要的对象。如obj的name,uuid,或者就是obj的地址。 如果找到,返回hashtable内的对象的指针。如果找不到返回NULL。
由此,我们想到如何构造一个散列表: 1,一个数组,元素是hlist_head对象。hlist_head指向一个散列表链表。 2,hash就是数组的索引。 hash值相同的对象,存入相同的hlist_head链表。
LinuxKernel的散列表就是这样实现的。
实例Inode-cacheLinuxKernel文件系统中,inode存放在一个全局的散列表Inode-cache中,代码在fs/inode.c中:
static structhlist_head *inode_hashtable__read_mostly;
它使用内核启动时保留的内存分配了一个数据。
/* *search theinode cache for a matchinginode number. *If we find one, then theinode number we are trying to *allocate is not unique and so we should not use it. *如果是唯一的,返回1。也就是说inode_hash表里没有数据。 否则不是唯一的,返回0。也就是说表里有这个inode。 *Returns 1 if theinode number is unique, 0 if it is not. */ staticinttest_inode_iunique(structsuper_block *sb, unsignedlongino) { 根据sb的地址+inode的唯一号码(在一个超级块内是唯一的)得到散列值。 structhlist_head *b = inode_hashtable + hash(sb, ino); structhlist_node *node; structinode *inode; 锁住整个散列表 spin_lock(&inode_hash_lock); hlist_for_each_entry(inode,node, b, i_hash) { 如果i_sb超级块的地址相同,并且inode的i_ino序号也相同,那么解锁整个表,返回0。 if(inode->i_ino== ino && inode->i_sb== sb) { spin_unlock(&inode_hash_lock); return0; } } spin_unlock(&inode_hash_lock); 否则返回1。 return1; } 上例中,如果hash相同,那么就根据inode所属的i_sb超级块对象的地址是否相同,以及inode的i_ino是否相同决定散列表中的inode对象是否就是我们正在寻找的对象。 inode可以通过i_sb和i_ino在逻辑上唯一定位。
实例 DentrycacheLinuxKernel的dentry也保存在一个散列表Dentrycache中,代码在fs/dcache.c:
102static
struct hlist_bl_head *dentry_hashtable__read_mostly;
实现方法都一样!
PS: Blog格式有点难看,上传了PDF版本, 想要的朋友请移步: http://d.download.csdn.net/down/3441424/shendl |
|
来自: 千年长叹 > 《linux内核学习》