学习Linux内核链表
讲述在学习Linux内核链接过程的见解，整理笔记共享。
方法/步骤
对于链表的优缺点，我们对比数组可以说出一些，但在随机存储的情况下，我们会选择链表来处理，而我们使用双向链表时，经常会定义成如下形式：
struct list_node {
TYPE data;
struct list_node *prev,*next;
};
相对应的链表结构如下：
对于该数据结构定义，存在一个局限，整个结构中只能有一个双向循环链表，而不能存在多个，并且链表的操作只能针对该数据结构操作，没能通用，而在Linux内核（下面以3.0.8版本为例）中则把链表与数据域分开了，实现通用链表结构及操作，其定义存在于include/linux/types.h文件中，形式如下：
struct list_head {
struct list_head *next, *prev;
};
上面是通用链表的结构，而利用该定义，我们可以把我们常用的双向链表定义为如下形式：
struct list_node {
TYPE data;
struct list_head list;
};
相应的链表结构如下：
从图中可以看出，其链表只是通过list_head这个结构体连接起来，这样就只能对链表结构操作了？那么data要如何操作呢？
这就是linux 通用链表的技巧所在了，把链表独立出来，而不用去管其数据是什么，链表的操作得到了统一。
接下来，我们继续分析，体验linux的算法之美。
在linux内核源码的include/linux/list.h文件中包含了链表的操作，首先我们先来看看如何通过list_head的地址来找到包含它的结构体元素的首地址，在list.h文件中有如下的宏：
#define list_entry(ptr, type, member) \
container_of(ptr, type, member)
在include/linux/kernel.h文件中有如下定义：
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
在include/linux/stddef.h文件中有如下定义：
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
其中，size_t在i386上定义为unsigned int。
一看到这三个宏，多少有点头晕了，我们先把它转化为一个宏：
#define list_entry(ptr, type, member) \
( (type *)((char *)(ptr)-(unsigned int)(&(type *)0)->member) )
其中，(unsigned int)(&(type *)0)->member) 是把0地址转换为type类型的指针，然后再获取type类型结构体中的member成员的指针，并将其转化为unsigned int值，即得到member成员相对于type类型的偏移Offset。
然后通过将ptr指针减去这Offset值，就得到了ptr对应的结构体的起始位置Base。
上面ptr、type、member对应解释如下：
ptr是指向结构体中list_head类型成员的指针；
type为一个包含list_head类型成员的结构体类型；
member为结构体中类型list_head的成员名。
上面的转换，我们可以通过如下图示来理解：
如上图，我们将member指向的地址值减去0地址值，就得到了member相对于整个结构体的偏移offset了，然后理所当然就得到了我们的ptr对应的结构体地址值，这样就可以通过list_head来获得包含其的结构体了，即相当于：
包含list_head成员的结构体绝对地址=ptr绝对地址-相对地址offset
至此，一目了然了吧！此时，我们回头看内核里的定义，就应该不那么难理解了。
在上面内容中，我们已知道了内核中双向链表的定义，接下来继续了解链表的其他内容：
1、链表的初始化宏
现在先来确认如何创建链表头，在内核源码里的include/linux/list.h中有如下宏：
#define LIST_HEAD_INIT(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;
}
从上面看到，其实就是将自身赋给前、后指针，即在初始化时，链表头的prev和next都指向自身。如此一来，我们也可以很容易判断链表是不是空的。
2、常用链表操作函数、宏
static inline void list_add(struct list_head *new, struct list_head *head);
static inline void list_add_tail(struct list_head *new, struct list_head *head);
static inline void list_del(struct list_head *entry);
static inline int list_empty(const struct list_head *head);
#define list_entry(ptr, type, member) \
container_of(ptr, type, member)
#define list_for_each_entry(pos, head, member) \
for (pos = list_entry((head)->next, typeof(*pos), member); \
&pos->member != (head); \
pos = list_entry(pos->member.next, typeof(*pos), member))
更多的函数、宏可以在内核源码的include/linux/list.h文件里找到。
3、实例验证
接下来我们在应用程序上验证下内核中这链表结构的实操性，这样可以让我们更好的在我们的应用程序中应用内核的思想。
例子代码如下（文件名为list_test.c）：
#include <stdio.h>
#include <stdlib.h>
#include "list.h"
struct test_list {
int data;
struct list_head list;
};
int main(void){
LIST_HEAD(head);
int i;
struct test_list *ptr[10];
struct list_head *tmp = NULL;
struct test_list *node;
for(i=0;i<10;i++){
ptr[i] = (struct test_list*)malloc(sizeof(struct test_list));
if(!ptr[i]){
printf("malloc error!\n");
}
ptr[i]->data = i;
}
for(i=0;i<10;i++){
list_add_tail(&ptr[i]->list,&head);
}
printf("Test Link:\n");
list_for_each(tmp,&head){
node = list_entry(tmp,struct test_list,list);
printf("%d ",node->data);
}
printf("\n");
return 0;
}
list.h:
#ifndef _LINUX_LIST_H
#define _LINUX_LIST_H
struct list_head {
struct list_head *next, *prev;
};
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)
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;
}
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
__list_add(new, head->prev, head);
}
#define list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); pos = pos->next)
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
#define list_entry(ptr, type, member) \
container_of(ptr, type, member)
#endif
编译时用到的Makefile内容如下：
all:
gcc -o list_test list_test.c list.h
clean:
rm -rf list_test
接下来执行make生成目标可执行文件list_test，再使用命令./list_test执行，结果如下：
至此，我们对内核链表有了初步了解，开始领略到内核的设计思想，让我们继续进行内核的学习之路。