Linux内核中list

原文:http://blog.csdn.net/hongchangfirst/article/details/7076225

作者:hongchangfirst

Linux内核需要经常用到链表，所以为了避免重复的代码，就自己实现了一个循环双向链表。
首先我们先看一下list_head的定义，该结构体在linux/types.h中定义。

struct list_head {
struct list_head *next, *prev;
};
 
list_head很简单，其实就是一个双向链表，但是我们也许会奇怪，这样的双向链表能干什么，它里面连最起码的一个泛化指针（void*）都没有，也就是说我们不可能通过它来获得其他对象的引用，那有什么用呢？也许，让我们来定义list_head，我们也许会这样定义：
 
struct hongchangfirst_list_head {
struct list_head *next, *prev;
         void *general_pointer;
};

这样我们就可以随心所欲的建立我们需要的任何数据结构的双向链表了。但是Linux内核毕竟不是”一般人“写出来的，所以人家就可以用刚才那种定义来实现任何数据结构的双向链表，它是怎么实现的呢？要明白这个问题，我们还得看看其它的一些结构体。
 
首先我们看一下list_for_each，它在linux/list.h中定义，我们可以看到它只是一个宏定义。
 
#define list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); pos = pos->next)


其中head是list_head组成的双向链表的指针，因为一般来说list_head双向链表都是循环双向链表，所以head就定义了你从哪里开始遍历这个链表，而pos就是指向list_head的指针，用来具体的对每一个list_head进行操作。用这个宏我们就可以实现对一个循环双向链表的完整遍历一遍。
 
如果只有这个遍历又有什么用呢，我们怎么得到我们想要的相关数据结构引用呢？关键是我们还得有list_entry，它其实就是一个从list_head到一个拥有该list_head字段的“包含体”的入口宏定义，我们先看看这个宏定义，具体在linux/list.h中定义。
 
#define list_entry(ptr, type, member) \
container_of(ptr, type, member)
 
其实list_entry就是直接使用了container_of，那我们就得看看container_of 了，具体在linux/kernel.h里定义。关于它的详细理解请参考http://blog.csdn.net/hongchangfirst/article/details/7076520 。
 
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr);\
(type *)( (char *)__mptr - offsetof(type,member) );})
 
其中ptr是指向包含体成员的指针，比如指向list_head的指针，type就是包含该成员（比如list_head字段）的”包含体“类型，member是该成员（比如list_head）在该包含体类型中具体的名字。它的返回值是一个指向type的指针。
 
 它是怎么工作的呢？比如我们有以下结构体定义:
struct hongchangfirst
{
        struct zhc_t zhc;
        //其它字段
         list_head sibling;
        int i;
};
 
        如果我们有一个：hongchangfirst *p;现在p指向了一个hongchangfirst的对象，我们很自然的可以得到该对象的内部成员，如p->sibling.
        但是如果我们只有sibling的地址(list_head * p_sibling)，我们怎么得到zhc的地址呢？难道我们去计算sibling和zhc之间相差了几个字节吗，然后加或者减吗？但是这样我们就把程序结果运行的正确性完全交给了编译器和硬件结构，这样会带来不可移植性，那我们怎么办呢？其实我们可以这样做：
       hongchangfirst * p_hcf =  list_entry(p_sibling,struct hongchangfirst,sibling);
        这样子我们就拥有了其包容体的指针，我们还怕得不到其zhc成员的引用吗？用p_hcf->zhc就行了。
这张图就可以清楚的展示它们之间的关系：

 

        其实Linux内核这样子做也是为了减少运行时的复杂性，因为如果像我之前定义的双向链表hognchangfirst_list_head 那样，那么Linux内核就必须维护general_pointer字段，以保证其指向正确的地址，这样大大降低了内核的运行效率，Linux内核追求的就是速度。其实我们可以完全利用对于特定的平台，一个结构体的相关字段之间的偏移量是固定的这样一个事实，来达到我们提高程序的运行效率的目的。但是这样做也有不好的地方，就是不容易理解，但是Linux内核源代码又有多少人看呢？大部分人都只是用一下Linux操作系统而已，又不是去自己编写一个操作系统。

[cpp] view plaincopy

1. <pre></pre>  
2. <pre></pre>  
3. <pre></pre>  
4. <pre></pre>  
5. <pre></pre>  
6. <pre></pre>  
7. <pre></pre>  
8. <pre></pre>  
9. <pre></pre>  
10. <pre></pre>