1 链表简述
在讲Linux内核中的链表之前，我们先来看一下平时所见的链表：
/*平时所见的单向链表*/
struct entry{
int data;
char * desc;
struct entry *next;
}
/*平时所见的双向链表*/
struct entry{
int data;
char * desc;
struct entry *prev;
struct entry *next;
}
用图片表示如下：
下面来看一下Linux内核中关于双向链表的实现：
内核中双向链表的结构体：源代码网址
struct list_head {
struct list_head *next, *prev;
};
先来说一下Linux内核中的链表为什么要这样设计？
对于每一个链表，都需要实现一组操作：初始化链表，插入和删除元素，对链表进行遍历等等。试想，如果我们采用普通链表那样的方式，每一次我们建立一个链表结构体，我们都需要重新实现初始化、插入、删除、遍历元素等，这可能浪费开发人员的精力，也因为对每个不同的链表都要重复相同的原语操作（这里原语操作指的是对链表的建立与增、删、遍历等操作）而造成存储空间的浪费。
2 内核链表实现
Linux内核中有关链表操作的源代码如下：源代码网址
/*对双向链表进行初始化操作*/
#define LIST_HEAD_INIT(name) { &(name), &(name) }
/*创建一个名称为name的双向链表*/
#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)
/*初始化双向链表*/
static inline void INIT_LIST_HEAD(struct list_head *list)
{
list->next = list;
list->prev = list;
}
/*向链表中插入一个元素，准确来说是将new元素插在prev和next元素的中间*/
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;
}
/*向链表头部插入元素，新插入的元素将成为第一个元素。准确来说是将new元素插入到链表第一个元素之前，也就是head之后*/
static inline void list_add(struct list_head *new, struct list_head *head)
{
__list_add(new, head, head->next);
}
/*向链表尾部插入元素，新插入的元素将成为链表中最后一个元素，也就是head的prev指向的元素*/
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
__list_add(new, head->prev, head);
}
/*替换链表中的某个元素，其中old为要替换的元素，new表示用于替换old的元素
如果old元素为空，它将会被覆盖（If @old was empty, it will be overwritten.）。
也就是说，如果old是链表中唯一一个元素，那么这个链表就会被替换*/
static inline void list_replace(struct list_head *old,
struct list_head *new)
{
new->next = old->next;
new->next->prev = new;
new->prev = old->prev;
new->prev->next = new;
}
/*判断list元素是否为链表中的最后一个元素*/
static inline int list_is_last(const struct list_head *list,
const struct list_head *head)
{
return list->next == head;
}
/*判断链表是否为空*/
static inline int list_empty(const struct list_head *head)
{
return head->next == head;
}
/*判断一个链表中是否只有一个元素*/
static inline int list_is_singular(const struct list_head *head)
{
return !list_empty(head) && (head->next == head->prev);
}
/*遍历链表，head表示要遍历的链表，pos表示遍历使用的游标*/
#define list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); pos = pos->next)
/*逆序遍历一个链表，head表示要遍历的链表，pos表示遍历使用的游标*/
#define list_for_each_prev(pos, head) \
for (pos = (head)->prev; pos != (head); pos = pos->prev)
/*安全的遍历一个链表，head表示要遍历的链表，pos表示要遍历的链表的游标，n用来临时存储链表节点
实际上，在遍历链表的时候，可能会发生正在遍历的元素被移除，为此，可以临时保存下一个要遍历的链表节点
*/
#define list_for_each_safe(pos, n, head) \
for (pos = (head)->next, n = pos->next; pos != (head); \
pos = n, n = pos->next)
/*安全的逆序遍历一个链表节点，head表示要遍历的链表，pos表示遍历使用的游标，n用来临时存放链表节点*/
#define list_for_each_prev_safe(pos, n, head) \
for (pos = (head)->prev, n = pos->prev; \
pos != (head); \
pos = n, n = pos->prev)
上面是链表的一些基本的方法，关于这些方法的一些简单说明都已经写在注释中了，这些方法也很容易明白。简单画了一张插入节点的图，对应__list_add方法：
下面重点说一下list_del这个方法，这个方法的定义如下：源代码网址
/*从链表中删除一个元素*/
static inline void __list_del(struct list_head * prev, struct list_head * next)
{
next->prev = prev;
prev->next = next;
}
#ifndef CONFIG_DEBUG_LIST
static inline void __list_del_entry(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
}
static inline void list_del(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
entry->next = LIST_POISON1;
entry->prev = LIST_POISON2;
}
#else
extern void __list_del_entry(struct list_head *entry);
extern void list_del(struct list_head *entry);
#endif
从上面的代码中不难看出list_del(entry)其实就是entry元素从链表中删除，但是下面的两行代码需要解释一下：
entry->next = LIST_POISON1;
entry->prev = LIST_POISON2;
关于LIST_POISON1和LIST_POISON2的宏定义如下：
/*
* These are non-NULL pointers that will result in page faults
* under normal circumstances, used to verify that nobody uses
* non-initialized list entries.
*/
#define LIST_POISON1 ((void *) 0x100 + POISON_POINTER_DELTA)
#define LIST_POISON2 ((void *) 0x200 + POISON_POINTER_DELTA)
这里为什么不将entry->next=NULL;entry->prev=NULL;而是将它们置成LIST_POISON1和LIST_POISON2呢？我们先看一下关于LIST_POISON1和LIST_POISON2的注释，翻译过来就是：
这些非空指针在正常情况下会导致页面错误，用于验证没有人使用非初始化链表项。
页面错误这的就是缺页中断，使用entry->next=LIST_POISON1;entry->LIST_POISON2;应该是在删除链表元素的时候，如果该链表节点已经被删除，那么就可以进行提示了。也就是说，在普通环境中，用来验证所有的链表节点都已经被初始化。
看到上面关于Linux内核链表的介绍，你可能会突然意识到一个问题：
一个链表节点中只有prev和next域，我们的数据放到哪里呢？其实Linux内核中的链表的使用是有技巧的。比如我们定义一个普通的entry元素，元素中包含data和desc连个属性，如果使用linux内核链表，我们该怎么做呢？答案如下：
struct entry{
int data;
char *desc;
list_head list;
}
关于上面定义的链表，就是我们一开始提出来的Linux内核链表的使用，也就是下面的图。
考虑一个问题，我们现在要对上面的这个链表进行遍历，并且在遍历的时候读取data和desc的值，该怎么做呢？
看一个例子：
/**
* container_of - cast a member of a structure out to the containing structure
* @ptr: the pointer to the member.
* @type: the type of the container struct this is embedded in.
* @member: the name of the member within the struct.
*
*/
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
/**
* list_entry - get the struct for this entry
* @ptr: the &struct list_head pointer.
* @type: the type of the struct this is embedded in.
* @member: the name of the list_struct within the struct.
*/
#define list_entry(ptr, type, member) \
container_of(ptr, type, member)
#define list_for_each_safe(pos, n, head) \
for (pos = (head)->next, n = pos->next; pos != (head); \
pos = n, n = pos->next)
struct entry{
int data;
char *desc;
list_head list;
}
struct entry my_entry;
struct entry *ep;
struct list_head *this, *next;
list_for_each_safe(this, next, &my_entry) {
ep = list_entry(this, struct entry, list);
//在这里已经获取到当前遍历的元素，并且是struct entry类型，也就是ep
//所以这里可以通过ep->data，ep->desc来获取到data、desc的值
//to do ......
}
其实上面操作的重点是container_of宏定义，下面我们结合上面的代码重点来看一下这个宏定义：
/**
* container_of - cast a member of a structure out to the containing structure
* @ptr: the pointer to the member.
* @type: the type of the container struct this is embedded in.
* @member: the name of the member within the struct.
*
*/
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
我们将ptr=this,type=struct entry,member=list带入上面的container_of(ptr,type,member)宏定义，得到结果如下：
container_of(this, struct entry, list) ({ \
const typeof( ((struct entry *)0)->list ) *__mptr = (this); \
(struct entry *)( (char *)__mptr - offsetof(struct entry,list) );})
下面我们来一行一行的分析一下这个展开后的宏，首先看展开后的宏的第一个分号前的那一句：
const typeof( ((struct entry *)0)->list ) * __mptr = (this);
为了便于观察，我将括号做了一下切分，接下来一点一点的分析，typeof里面的内容不难理解，就是将0地址强制转换成struct entry类型，这种做法你获取不太清楚，举个常见的例子： ((struct entry *)&my_entry)这样获取容易理解一下，&my_entry其实就是个地址，说白了就是一个数字，只不过上面((struct entry *)0)中是直接将0当做地址了。typeof在内核中很常见，它的作用就是根据变量来获取变量的类型，所以const typeof( ((struct entry *)0)->list )这一句的结果就是list_head类型，也就是struct entry结构体中list元素的类型。所以const typeof( ((struct entry *)0)->list ) * __mptr = (this);这一句就相当于list_head *__mptr=this;而这个this，我们之前的定义就是list_head *this;这一句不难理解。接下来看下面一句：
(struct entry *)( (char *)__mptr - offsetof(struct entry,list) );
其中offsetof函数是获取member在type中的偏移量，在这里就是获取list在struct entry结构体中的偏移量，这里为什么要将__mptr再转换成char *类型呢？其实为了在做地址加减是时候保证不会出错，不转其实是会出问题的，想一想为什么？所以(char *)__mptr - offsetof(struct entry,list)就获取到了整个entry元素所在的地址。所以container_of这个宏定义在上面的例子中的功能很简单：就是根据struct entry元素中list的地址来获取整个entry的地址，获取到整个entry的地址之后，我们就可以访问entry元素中的其他属性了，在上面的例子中就是访问entry元素中的data、desc属性。
好了，关于Linux内核链表的介绍就写到这里。
本人能力有限，文中如有错误，请您批评指正，邮箱：[email protected]，谢谢！