Linux Kernel实现的链表与众不同,大多数人所熟悉的方式应该是在“链表中包含结构体”,而Linux内核的实现方式则是所谓的“结构体中包含链表”。这样的说法听起来很玄乎,不如给出具体的定义和实例。

1 struct list_head {
2    struct list_head *next, *prev;
3 };

这就是内核代码中Linked List的结构体定义,从list_head定义可以看出,内核的链表是循环链表。我们可以这么用它:

struct these_shit_dictators{
   char   name[MAX_LEN];
   char   country[MAX_LEN];
   struct list_head list;
};

链表的操作接口

一般在使用指针时要初始化,这是一个好的编程习惯,操作内核提供的链表也是如此。首先用INIT_LIST_HEAD()函数对其初始化。INIT_LIST_HEAD()做的工作很简单:

#define INIT_LIST_HEAD(ptr) do { \
   (ptr)->next = (ptr); (ptr)->prev = (ptr); \
} while (0)

可以看到初始化就是把指针指向自己。在不同版本的源码中,这些函数的实现方式略有不同,例如在linux-2.6.26中,此函数不是宏定义,而是一个内联函数,不过它们所做的工作都是大同小异的,这一点在本文其他部分都一样,下面就不再提醒了。

list_add操作

插入操作所做的操作非常简单,只要学过基础的数据结构的人一眼就能看明白:

static inline void __list_add(struct list_head *new,
                 struct list_head *prev,
                 struct list_head *next){
   next->prev = new;
   new->next = next;
   new->prev = prev;
   prev->next = new;
}

对于循环链表来说,在头部插入和在尾部插入是一样的,确实,内核也是这么做的,看一段很有意思的代码:

void list_add(struct list_head *new, struct list_head *head){
   __list_add(new, head, head->next);
}

void list_add_tail(struct list_head *new, struct list_head *head){
   __list_add(new, head->prev, head);
}

对于删除、合并等操作也都类似,有兴趣的读者可以自己翻看源码,比较简单的。

遍历操作、获取结构体成员操作

我认为kernel实现的链表最优意思的部分是list_entry、list_for_each等几个宏的实现。

首先有个问题:使用这种“Items contains the list”的方式如何通过这个list_head成员获得结构体的其他成员? 答案是list_entry宏,我们先来看内核源码是怎么写的:

01 #define list_entry(ptr, type, member) \
02     container_of(ptr, type, member)
03 
04 //  in include/linux/kernel.h
05 
06 /**
07  * container_of – cast a member of a structure out to the containing structure
08  * @ptr:    the pointer to the member.
09  * @type:    the type of the container struct this is embedded in.
10  * @member:    the name of the member within the struct.
11  *
12  */
13 #define container_of(ptr, type, member) ({            \
14     const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
15     (type *)( (char *)__mptr – offsetof(type,member) );})

用法: tmp=list_entry(ptr, type, member)
其中,

ptr是指向结构体中struct list_head 成员的指针;
type是本结构体的名字;
member是指在结构体中struct list_head叫什么名字,本例中叫list;
最后返回的是指向这个结构体的指针,有了这个指针,我们就可以调用其他成员了,比如tmp->name;

然后,我们来分析一下这个有意思的宏:

1、const typeof( ((type *)0)->member ) *__mptr = (ptr);
这句是声明了一个与名叫member的成员的类型一样的一个指针__mptr,并赋值为ptr;

2、(type *)( (char *)__mptr – offsetof(type,member) );
mptr指向的地址减去member在type中的偏移,就得到了type的地址了;

至于为什么要重新声明一个mptr,不直接用ptr呢?
我想大概是因为不破坏ptr指针的内容,以便后续的代码继续正常使用ptr。

Update:  感谢 肉兔、Fleuria、Bearice 同学的帮助~

感觉应该就是为了加一层类型的静态检查吧,C的宏是没有类型的,但可以做点功夫给它模拟一点类型检查。假如没有这句,这个ptr若是个无关的类型(比如偶尔可能会敲错变量)在编译时不会报错,甚至warning也不会有。
加上这么一句,如果ptr的类型不对,在编译时就可以报一个warning之类的了。删掉这句内核该依然可以正常编译,但有它可以让开发者的日子更好过一点。

其他几个有意思的宏,例如list_for_each(pos, head)之类的实现原理也类似,在此就不详细写了,有兴趣的话请参看 include/linux/list.h

—————–
参考资料:
1、《Linux内核设计与实现》
2、浅析Linux Kernel中的那些链表

12,308 views
Home

15 Comments so far

Trackbacks/Pingbacks

Leave a comment

Name(required)
Mail (required),(will not be published)
Website(recommended)

Fields in bold are required. Email addresses are never published or distributed.

Some HTML code is allowed:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
URLs must be fully qualified (eg: http://blog.nlogn.cn),and all tags must be properly closed.

Line breaks and paragraphs are automatically converted.

Please keep comments relevant. Off-topic, offensive or inappropriate comments may be edited or removed.