Linux内核中的双循环链表

Linux内核中的双循环链表

2006-11-27 19:14

双循环链表传统实现
在传统的双循环链表实现中，如果创建某种数据结构的双循环链表，通常采用的办法是在这个数据结构的类型定义中加入两个（指向该类型对象的）指针next和prev。例如：
typedef struct foo {
    …
    struct foo *prev;
    struct foo *next;
    …
} foo_t;
这里给出了对应的节点结构、空的双循环链表和非空的双循环链表示意图。

Linux内核中双循环链表实现
在linux内核中，有大量的数据结构需要用到双循环链表，例如进程、文件、模块、页面等。若采用双循环链表的传统实现方式，需要为这些数据结构维护各自的链表，并且为每个链表都要设计插入、删除等操作函数。（由于用来维持链表的next和prev指针指向对应类型的对象，因此一种数据结构的链表操作函数不能用于操作其它数据结构的链表。）
在Linux源代码树的include/linux/list.h文件中，采用了一种（数据结构）类型无关的双循环链表实现方式。其思想是将指针prev和next从具体的数据结构中提取处理构成一种通用的"双链表"数据结构list_head，而list_head被作为一个成员嵌入到要拉链的数据结构（被称为宿主数据结构）中。这样，只需要一套通用的链表操作函数就可以将list_head成员作为"连接件"，把宿主数据结构链接起来。如下图所示：

在Linux内核中的双循环链表实现方式下：
1. 链表结构作为一个成员嵌入到宿主数据结构内；
2. 可以将链表结构放在宿主结构内的任何地方；
3. 可以为链表结构取任何名字；
4. 宿主结构可以有多个链表结构。
下面我们将基于Linux 2.4.21分析Linux内核双循环链表的实现及应用。
声明和初始化
链表结构定义如下：
struct list_head {
    struct list_head *next, *prev;
};
我们可以用struct list_head声明一个链表节点。需要注意的是，Linux 的每个双循环链表都有一个链表头，链表头也是一个节点，只不过它不嵌入到宿主数据结构中，即不能利用链表头定位到对应的宿主结构。
我们可以调用INIT_LIST_HEAD()宏初始化链表节点，将next和prev指针都指向其自身。如果这个节点是链表头，我们就构造了一个空的双循环链表。
#define INIT_LIST_HEAD(ptr) do { \
    (ptr)->next = (ptr); (ptr)->prev = (ptr); \
} while (0)
LIST_HEAD()宏可以同时完成声明链表头，并初始化这个双循环链表为空。
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
    struct list_head name = LIST_HEAD_INIT(name)
添加
在上面的设计下，所有链表（包括添加、删除、移动和拼接等）操作都是针对数据结构list_head进行的。
对链表的添加操作有两种：表头添加和表尾添加。注意到，Linux双循环链表中有一个链表头，表头添加是指添加到链表头之后，而表尾添加则是添加到链表头的prev所指链表节点（如果是空链表，这个链表节点为链表头自身）之后。Linux为此提供了两个接口：
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);
具体添加是调用__list_add完成的，我们不予赘述。
static inline void __list_add(struct list_head *new, struct list_head *prev, struct list_head *next);
删除
如果要从链表中删除某个链表节点，则可以调用list_del或list_del_init。
static inline void list_del(struct list_head *entry);
static inline void list_del_init(struct list_head *entry);
两者都调用__list_del将节点从链表中取出，之后，list_del将要删除节点的prev和next指针均设为NULL，保证不可通过该节点进行访问；而list_del则调用LIST_INIT_HEAD()把被删除节点为作为链表头构建一个新的双循环链表。
需要注意的是，上述操作均仅仅是把节点从双循环链表中拿掉，用户需要自己负责释放该节点对应的数据结构所占用的空间，而这个空间本来就是用户分配的。
移动
Linux还提供了两个移动操作：list_move和list_move_tail。前者将指定节点从其所在链表中取出，添加到另一个链表的头部。而后者在取出后添加到新链表的尾部。
static inline void list_move(struct list_head *list, struct list_head *head);
static inline void list_move_tail(struct list_head *list, struct list_head *head);
拼接
Linux还支持两个链表的拼接，具体函数是list_splice和list_splice_init：
static inline void list_splice(struct list_head *list, struct list_head *head);
static inline void list_splice_init(struct list_head *list, struct list_head *head);
两个函数都将一个链表的所有节点依次添加到另一个链表的头部，新链表将一原链表的第一个节点为首节点，而尾节点不变。区别在于：前者，原链表头的next和prev仍然指向原来的地方；而后者调用INIT_LIST_HEAD()为原链表头初始化一个空的双循环链表。
获取宿主对象指针
如果需要有某种数据结构的队列，就在这种数据结构定义内部放上一个list_head数据结构。例如，建立数据结构foo链表的方式是，在foo的定义中，嵌入了一个list_head成员list。这里foo就是所指的"宿主"。
typedef struct foo {
    …
    struct list_head list;
    …
};
上述的添加、删除、移动和合并都是针对list进行的，后面要讲到的遍历操作也基于list。但是，如何通过list_head成员访问到宿主结构项呢？毕竟list_head不过是个连接件，而我们需要的是一个"特定"的数据结构链表。
Linux为此提供了list_entry()宏，获取当前list_head链表节点所在的宿主结构项。第一个参数为当前list_head节点的指针，即指向宿主结构项的list_head成员。第二个参数是宿主数据结构的定义类型。第三个参数为宿主结构类型定义中list_head成员名。
#define list_entry(ptr, type, member) \
    ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
例如，我们要访问foo链表（链表头为head）中首个元素，则如此调用：
list_entry(head->next, struct foo, list);
经过C预处理的文字替换，这一行的内容就成为：
((struct foo *)((char *)(head->next) - (unsigned long)(&((struct page *)0)->list)))

获取宿主对象指针的原理如上图所示。我们考虑list_head成员member相对于宿主结构（类型为type）起始地址的偏移量。对于所有该类型的宿主对象，这个偏移量是固定的。并且可以在假设宿主对象地址值为0，通过返回member成员的地址获得，即等于(unsigned long)(&((type *)0)->member)。这样，将当前宿主对象的"连接件"地址（ptr）减去这个偏移量，得到宿主对象地址，再将它转换为宿主数据结构类型的指针。
需要重申的是，链表头没有被嵌入到宿主对象中，因此对链表头执行宿主对象指针获取操作是没有意义的。
遍历
遍历是双循环链表的基本操作，为此Linux定义了一些宏。
list_for_each对遍历链表中的所有list_head节点，不涉及到对宿主结构的处理。list_for_each实际是一个 for 循环，利用传入的指向list_head结构的指针作为循环变量，从链表头开始（并跳过链表头），逐项向后移动指针，直至又回到链表头。为提高遍历速度，还使用了预取。
#define list_for_each(pos, head) \
    for (pos = (head)->next, prefetch(pos->next); pos != (head); \
        pos = pos->next, prefetch(pos->next))
如果需要反向遍历list_head链表，可以使用list_for_each_prev宏。
#define list_for_each_prev(pos, head) \
    for (pos = (head)->prev, prefetch(pos->prev); pos != (head); \
        pos = pos->prev, prefetch(pos->prev))
上述两个操作都是通过移动（指向list_head结构的）指针来达到遍历的目的。但如果在遍历过程中，包含有删除或移动当前链接节点的操作，由于这些操作会修改遍历指针，这样会导致遍历的中断。这种情况下，必须使用list_for_each_safe宏，在操作之前将遍历指针缓存下来：
#define list_for_each_safe(pos, n, head) \
    for (pos = (head)->next, n = pos->next; pos != (head); \
        pos = n, n = pos->next)
如果只提供对list_head结构的遍历操作是远远不够的，我们希望实现的是对宿主结构的遍历，即在遍历时直接获得当前链表节点所在的宿主结构项，而不是每次要同时调用list_for_each和list_entry。对此，Linux提供了list_for_each_entry()宏，第一个参数为传入的遍历指针，指向宿主数据结构，第二个参数为链表头，为list_head结构，第三个参数为list_head结构在宿主结构中的成员名。
#define list_for_each_entry(pos, head, member)    \
    for (pos = list_entry((head)->next, typeof(*pos), member), \
        prefetch(pos->member.next);   \
       &pos->member != (head);      \
       pos = list_entry(pos->member.next, typeof(*pos), member), \
       prefetch(pos->member.next))
如何使用Linux中的双循环链表
本文例子来自，只是对其中注释部分作了翻译。
#include
#include

#include "list.h"

struct kool_list{
    int to;
    struct list_head list;
    int from;
};

int main(int argc, char **argv){
    struct kool_list *tmp;
    struct list_head *pos, *q;
    unsigned int i;

    struct kool_list mylist;
    INIT_LIST_HEAD(&mylist.list);
    /* 您也可以使用宏LIST_HEAD(mylist)来声明并初始化这个链表 */

    /*向链表中添加元素*/
    for(i=5; i!=0; --i){
        tmp= (struct kool_list *)malloc(sizeof(struct kool_list));
  
        /*INIT_LIST_HEAD(&tmp->list); 调用这个函数将初始化一个动态分配的list_head。也可以不调用它，因为在后面调用的add_list()中将设置next和prev域。*/
        printf("enter to and from:");
        scanf("%d %d", &tmp->to, &tmp->from);

        /*将tmp添加到mylist链表中*/
        list_add(&(tmp->list), &(mylist.list));
        /*也可以使用list_add_tail()将新元素添加到链表的尾部。*/
    }
    printf("\n");

    /*现在我们得到了数据结构struct kool_list的一个循环链表，我们将遍历这个链表，并打印其中的元素。*/

    /*list_for_each()定义了一个for循环宏，第一个参数用作for循环的计数器，换句话说，在整个循环过程中它指向了当前项的list_head。第二个参数是指向链表的指针，在宏中保持不变。*/
    printf("traversing the list using list_for_each()\n");
    list_for_each(pos, &mylist.list){
        /*此刻：pos->next指向了下一项的list变量，而pos->prev指向上一项的list变量。而每项都是struct kool_list类型。但是，我们需要访问的是这些项，而不是项中的list变量。因此需要调用list_entry()宏。*/
        tmp= list_entry(pos, struct kool_list, list);
        /*给定指向struct list_head的指针，它所属的宿主数据结构的类型，以及它在宿主数据结构中的名称，list_entry返回指向宿主数据结构的指针。例如，在上面一行， list_entry()返回指向pos所属struct kool_list项的指针。*/
        printf("to= %d from= %d\n", tmp->to, tmp->from);
    }
    printf("\n");
    /* 因为这是一个循环链表，我们也可以向前遍历。只需要将list_for_each替换为list_for_each_prev。我们也可以使用list_for_each_entry()遍历链表，在给定类型的项间进行循环。例如：*/
    printf("traversing the list using list_for_each_entry()\n");
    list_for_each_entry(tmp, &mylist.list, list)
    printf("to= %d from= %d\n", tmp->to, tmp->from);
    printf("\n");
 

    /*下面将释放这些项。因为我们调用list_del()从链表中删除各项，因此需要使用list_for_each()宏的"安全"版本，即list_for_each_safe()。务必注意，如果在循环中有删除项（或把项从一个链表移动到另一个链表）的操作，必须使用这个宏。*/
    printf("deleting the list using list_for_each_safe()\n");
    list_for_each_safe(pos, q, &mylist.list){
        tmp= list_entry(pos, struct kool_list, list);
        printf("freeing item to= %d from= %d\n", tmp->to, tmp->from);
        list_del(pos);
        free(tmp);
    }
    return 0;
}

注意：上述代码在使用gcc编译时需要加上__KERNEL__定义。