详解Linux内核之双向循环链表(一)

摘要: 本文详解了内核中面向对象的list结构的原理，以及如何以list为内嵌对象来构造自己的链表结构，如何从内嵌list对象获得自定义的对象指针；探讨了各种宏或者函数的详细使用方法及怎样以通用list结构来操作自定义对象。

关键字:双向循环链表，list，list_entry，typeof，containerof，list_for_each,list_for_each_entry

1、双循环链表传统实现
2、Linux内核中双循环链表实现
3、定义和初始化
4、通用链表操作接口
  4.1添加节点  4.2删除节点  4.3移动节点  4.4链表判空  4.5链表合并
5、获取宿主对象指针
6、遍历
   6.1 List-head链表遍历  6.2遍历宿主对象
7、如何使用Linux中的双循环链表

1、双循环链表传统实现
    在传统的双循环链表实现中，如果创建某种数据结构的双循环链表，通常采用的办法是在这个数据结构的类型定义中加入两个（指向该类型对象的）指针next和prev。例如：
typedef struct foo {
    …
    struct foo *prev;
    struct foo *next;
    …
} foo_t;
这里给出了对应的节点结构、空的双循环链表和非空的双循环链表示意图。
2、Linux内核中双循环链表实现
    在linux内核中，有大量的数据结构需要用到双循环链表，例如进程、文件、模块、页面等。若采用双循环链表的传统实现方式，需要为这些数据结构维护各自的链表，并且为每个链表都要设计插入、删除等操作函数。因为用来维持链表的next和prev指针指向对应类型的对象，因此一种数据结构的链表操作函数不能用于操作其它数据结构的链表。
    在Linux源代码树的include/linux/list.h文件中，采用了一种类型无关的双循环链表实现方式。其思想是将指针prev和next从具体的数据结构中提取出来构成一种通用的"双链表"数据结构list_head。如果需要构造某类对象的特定链表，则在其结构（被称为宿主数据结构）中定义一个类型为list_head类型的成员，通过这个成员将这类对象连接起来，形成所需链表，并通过通用链表函数对其进行操作。其优点是只需编写通用链表函数，即可构造和操作不同对象的链表，而无需为每类对象的每种列表编写专用函数，实现了代码的重用。

list_head结构
-----------struct list_head{}及初始化宏---------
struct list_head
{
      struct list_head *next, *prev;
};
当用此类型定义一个独立的变量时，其为头结点。当其为某个结构体的一个成员时，其为普通结点。尽管形式一样，但表达的意义不同，是否应该定义为两个类型list_head和list_node？？？无法分开，空链表时指向了自己list_head成员作为"连接件"，把宿主数据结构链接起来。如下图所示：



在Linux内核中的双循环链表实现方式下：

1. list_head类型的变量作为一个成员嵌入到宿主数据结构内；

2. 可以将链表结构放在宿主结构内的任何地方；

3. 可以为链表结构取任何名字；

4. 宿主结构可以有多个链表结构；

5. 用list_head中的成员和相对应的处理函数来对链表进行遍历；

6. 如果想得到宿主结构的指针，使用list_entry可以算出来。


3、定义和初始化

--LIST_HEAD_INIT()--LIST_HEAD()--INIT_LIST_HEAD()------

#define LIST_HEAD_INIT(name) { &(name), &(name) }

#define LIST_HEAD(name) \

       struct list_head name = LIST_HEAD_INIT(name)



需要注意的是，Linux 的每个双循环链表都有一个链表头，链表头也是一个节点，只不过它不嵌入到宿主数据结构中，即不能利用链表头定位到对应的宿主结构，但可以由之获得虚拟的宿主结构指针。



LIST_HEAD()宏可以同时完成定义链表头，并初始化这个双循环链表为空。

静态定义一个list_head 类型变量，该变量一定为头节点。name为struct list_head{}类型的一个变量，&(name)为该结构体变量的地址。用name结构体变量的始地址将该结构体变量进行初始化。



#define INIT_LIST_HEAD(ptr) do { \

       (ptr)->next = (ptr); (ptr)->prev = (ptr); \

} while (0)

动态初始化一个已经存在的list_head对象，ptr为一个结构体的指针，这样可以初始化堆栈以及全局区定义的list_head对象。ptr使用时候，当用括号，(ptr)，避免ptr为表达式时宏扩展带来的异常问题。此宏很少用于动态初始化内嵌的list对象，主要是链表合并或者删除后重新初始化头部。若是在堆中申请了这个链表头，调用INIT_LIST_HEAD()宏初始化链表节点，将next和prev指针都指向其自身，我们就构造了一个空的双循环链表。
2.6内核中内联函数版本如下：
static inline void INIT_LIST_HEAD(struct list_head *list)
{
      list->next = list;
      list->prev = list;
}
此时的参数有明确的类型信息struct list_head，同时可以看出其为指针，list无须象宏中那样（），即使参数为表达式，其也是求值后再作为参数传入的。内联函数有严格的参数类型检查，同时不会出现宏函数扩展带来的异常问题，但是运行效率和空间效率与宏函数一致。
4、通用链表操作接口
4.1添加节点
在上面的设计下，所有链表（包括添加、删除、移动和拼接等）操作都是针对数据结构list_head进行的。提供给用户的的添加链表的操作有两种：表头添加和表尾添加。注意到，Linux双循环链表中有一个链表头，表头添加是指添加到链表头之后，而表尾添加则是添加到链表头的prev所指链表节点之后。
-----------__list_add()------list_add()------list_add_tail()-------
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、prev、next都不能是空值。
Prev可以等于next，此时在只含头节点的链表中插入新节点。
static inline void list_add(struct list_head *new, struct  list_head *head)
{
       __list_add(new, head, head->next);
}
在head和head->next两指针所指向的结点之间插入new所指向的结点。
即：在head指针后面插入new所指向的结点。Head并非一定为头结点。
当现有链表只含有一个头节点时，上述__list_add(new, head, head->next)仍然成立。
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
      __list_add(new, head->prev, head);
}
在结点指针head所指向结点的前面插入new所指向的结点。当head指向头节点时，也相当于在尾结点后面增加一个new所指向的结点。
注意：
head->prev不能为空，即若head为头结点，其head->prev当指向一个数值，一般为指向尾结点，构成循环链表。

上述三个函数实现了添加一个节点的任务，其中__list_add()为底层函数，“__”通常表示该函数是底层函数，供其他模块调用，此处实现了较好的代码复用，list_add和list_add_tail虽然原型一样，但调用底层函数__list_add时传递了不同的参数，从而实现了在head指向节点之前或之后添加新的对象。
4.2删除节点
如果要从链表中删除某个链表节点，则可以调用list_del或list_del_init。
需要注意的是，上述操作均仅仅是把节点从双循环链表中拿掉，用户需要自己负责释放该节点对应的数据结所占用的空间，而这个空间本来就是用户分配的。
-----------__list_del()---list_del()-----list_del_init()----------
static inline void __list_del(struct list_head * prev, struct list_head * next)
{       next->prev = prev;
      prev->next = next;
}
在prev和next指针所指向的结点之间，两者互相所指。在后面会看到：prev为待删除的结点的前面一个结点，next为待删除的结点的后面一个结点。
static inline void list_del(struct list_head *entry)
{
       __list_del(entry->prev, entry->next);
       entry->next = LIST_POISON1;
       entry->prev = LIST_POISON2;
}

删除entry所指的结点，同时将entry所指向的结点指针域封死。
对LIST_POISON1,LIST_POISON2的解释说明：
Linux 内核中解释：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 *) 0x00100100)
#define LIST_POISON2  ((void *) 0x00200200)
常规思想是：entry->next = NULL; entry->prev = NULL; 保证不可通过该节点进行访问。
---------------list_del_init()--------------------
static inline void list_del_init(struct list_head *entry)
{
      __list_del(entry->prev, entry->next);
      INIT_LIST_HEAD(entry);
}
删除entry所指向的结点，同时调用LIST_INIT_HEAD()把被删除节点为作为链表头构建一个新的空双循环链表。
4.3移动节点
Linux还提供了两个移动操作：list_move和list_move_tail。
-----------list_move()--list_move_tail()----------
static inline void list_move(struct list_head *list, struct list_head *head)
{
       __list_del(list->prev, list->next);
        list_add(list, head);
}
将list结点前后两个结点互相指向彼此，删除list指针所指向的结点，再将此结点插入head，和head->next两个指针所指向的结点之间。
即：将list所指向的结点移动到head所指向的结点的后面。
static inline void list_move_tail(struct list_head *list,    struct list_head *head)
{
       __list_del(list->prev, list->next);
       list_add_tail(list, head);
}

删除了list所指向的结点，将其插入到head所指向的结点的前面，如果head->prev指向链表的尾结点的话，就是将list所指向的结点插入到链表的结尾。
4.4链表判空
由list-head构成的双向循环链表中，通常有一个头节点，其不含有有效信息，初始化时prev和next都指向自身。判空操作是判断除了头节点外是否有其他节点。
---------------------list_empty(）-------------
static inline int list_empty(const struct list_head *head)
{
       return head->next == head;
}
测试链表是否为空，如果是只有一个结点，head，head->next，head->prev都指向同一个结点，则这里会返回1，表示空；但这个空不是没有任何结点，而是只有一个头结点，因为头节点只是纯粹的list节点，没有有效信息，故认为为空。
--------------------list_empty_careful(）---------
Static inline int list_empty_careful(const struct list_head *head)
{
      struct list_head *next = head->next;
      return (next == head) && (next == head->prev);
}

分析：
1.只有一个头结点head，这时head指向这个头结点，head->next,head->prev指向head，即：head==head->next==head->prev，这时候list_empty_careful（）函数返回1。

2.有两个结点，head指向头结点，head->next,head->prev均指向后面那个结点，即：head->next==head->prev,而head!=head->next,head!=head->prev.所以函数将返回0

3.有三个及三个以上的结点，这是一般的情况，自己容易分析了。

注意：这里empty list是指只有一个空的头结点，而不是毫无任何结点。并且该头结点必须其head->next==head->prev==head
4.5链表合并

Linux还支持两个链表的拼接，提供给用户的具体函数是list_splice和list_splice_init：
--------------__list_splice()------------------
static inline void __list_splice(struct list_head *list,      struct list_head *head)
{
       struct list_head *first = list->next;
       struct list_head *last  = list->prev;
       struct list_head *at    = head->next;
      first->prev = head;
       head->next = first;
       last->next = at;
      at->prev = last;

}

将一个非空链表插入到另外一个链表中。不作链表是否为空的检查，由调用者默认保证。因为每个链表只有一个头节点，将空链表插入到另外一个链表中是没有意义的。但被插入的链表可以是空的。
--------------------list_splice()----------------



static inline void list_splice(struct list_head *list, struct list_head *head)
{
      if (!list_empty(list))
      __list_splice(list, head);
}

这种情况会丢弃list所指向的头结点，这是特意设计的，因为两个链表有两个头结点，要去掉一个头结点。只要list非空链，head无任何限制，该程序都可以实现链表合并。
-------------------list_splice_init()-----------------------------------


static inline void list_splice_init(struct list_head *list,

                                struct list_head *head)
{
       if (!list_empty(list)) 0
       {
              __list_splice(list, head);
              INIT_LIST_HEAD(list);
       }
}
将一个链表的有效信息合并到另外一个链表后，重新初始化空的链表头。

5、获取宿主对象指针

如果需要有某种数据结构的队列，就在这种数据结构定义内部放上一个list_head数据结构。例如，建立数据结构foo链表的方式是，在foo的定义中，嵌入了一个list_head成员list。这里foo就是所指的"宿主"。

typedef struct foo {
    …
    struct list_head list;
    …
};

但是，如何通过list_head成员访问到宿主结构项呢？毕竟list_head不过是个连接件，而我们需要的是一个"特定"的数据结构链表。

先介绍几个基本宏：offsetof、typeof、containerof
-------\linux\stddef.h-----offsetof()-----------
#define __compiler_offsetof(a,b)  __builtin_offsetof(a,b)
而__builtin_offsetof()宏就是在编译器中已经设计好了的函数，直接调用即可。
-------------------------------
#undef offsetof  //取消先前的任何定义，可以保证下面的定义生效
#ifdef __compiler_offsetof
#define offsetof(TYPE,MEMBER)  __compiler_offsetof(TYPE,MEMBER)
#else
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
#endif

一共4步
1. ( (TYPE *)0 ) 0地址强制 "转换" 为 TYPE结构的指针;
2. ((TYPE *)0)->MEMBER   访问结构中的数据成员;
3.  &( ( (TYPE *)0 )->MEMBER)取出数据成员的地址;
4.(size_t)(&(((TYPE*)0)->MEMBER))结果转换类型.巧妙之处在于将0转换成(TYPE*)，结构以内存空间首地址0作为起始地址，则成员地址自然为偏移地址；
例说明：
#include
typedef struct _test
{

     char i;

     int j;

     char k;

}Test;

int main()

{

     Test *p = 0;

     printf("%p\n", &(p->k));

}

这里使用的是一个利用编译器技术的小技巧（编译器自动算出成员的偏移量），即先求得结构成员变量在结构体中的相对于结构体的首地址的偏移地址，然后根据结构体的首地址为0，从而得出该偏移地址就是该结构体变量在该结构体中的偏移，即：该结构体成员变量距离结构体首的距离。在offsetof()中，这个member成员的地址实际上就是type数据结构中member成员相对于结构变量的偏移量。对于给定一个结构，offsetof(type,member)是一个常量，list_entry()正是利用这个不变的偏移量来求得链表数据项的变量地址。



---------------------typeof()--------------------

unsigned int i;

typeof(i) x;

x=100;

printf("x:%d\n",x);

typeof() 是 gcc 的扩展，和 sizeof() 类似。



------------------------

在 container_of 宏中，它用来给 typeof() 提供参数，以获得 member 成员的数据类型；

---------------container_of()--------------------

container_of() 来自\linux\kernel.h

内核中的注释：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) );})

自己分析：

1.(type *)0->member为设计一个type类型的结构体，起始地址为0，编译器将结构体的起始的地址加上此结构体成员变量的偏移得到此结构体成员变量的地址，由于结构体起始地址为0，所以此结构体成员变量的偏移地址就等于其成员变量在结构体内距离结构体开始部分的偏移量。即：&(type *)0->member就是取出其成员变量的偏移地址。而其等于其在结构体内的偏移量:即为：(size_t)(& ((type *)0)->member)经过size_t的强制类型转换后，其数值为结构体内的偏移量。该偏移量这里由offsetof()求出。



2.typeof( ( (type *)0)->member )为取出member成员的变量类型。用其定义__mptr指针.ptr为指向该成员变量的指针。__mptr为member数据类型的常量指针，其指向ptr所指向的变量处。



3.(char *)__mptr转换为字节型指针。(char *)__mptr - offsetof(type,member) )用来求出结构体起始地址（为char *型指针），然后(type *)( (char *)__mptr - offsetof(type,member) )在(type *)作用下进行将字节型的结构体起始指针转换为type *型的结构体起始指针。

这就是从结构体某成员变量指针来求出该结构体的首指针。指针类型从结构体某成员变量类型转换为该结构体类型。