Linux内核双向循环链表详述

1.普通链表的节点定义

普通的链表数据结构是：

[cce_cpp]
struct Node
{
    DataType data;
    Node *node;
}
[/cce_cpp]

2.内核中循环双链表的节点定义

链表节点：

[cce_cpp]
struct list_head
{
    struct list_head *prev, *next;
}
[/cce_cpp]

数据对象：

[cce_cpp]
struct  Node
{
    DataType data;
    struct list_head list;
}
[/cce_cpp]

内核中的链表结构是将链表节点与数据节点分开来，这样链表就可以不受数据结构的限制，适用于任何一种数据结构；甚至在向链表中添加删除节点的时候，可以添加或者删除同一个链表上的不同类型的数据节点，也就是说一个链表上可以放不同类型数据结构的节点，这是内核链表的巧妙之处。
具体的定义可参考：include//list.h。

二、内核3.4中的链表数据结构实现方法

内核中的链表的实现方法大都比较巧妙、精炼，主要是通过宏定义和内联函数来实现的。

1.链表的声明与初始化

（1）使用LIST_HEAD宏在编译时静态初始化

[cce_cpp]
#define LIST_HEAD_INIT(name) { &(name), &(name) } 
#define LIST_HEAD(name) \ 
        struct list_head name = LIST_HEAD_INIT(name)
[/cce_cpp]

将上边两句合并起来就是声明一个链表并将其初始化，使链表的前驱和后继指向自身。

（2）INIT_LIST_HEAD函数，在运行时动态初始化

[cce_cpp]
static inline void INIT_LIST_HEAD(struct list_head *list) 
{ 
        list->next = list; 
        list->prev = list; 
}
[/cce_cpp]

这个很明显，仅作初始化，将链表指向自身，与第一种情况类似，只是这种方法一般用于动态过程中的初始化。

2.添加节点

[cce_cpp]
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(struct list_head *new, struct list_head *head) 
{ 
        __list_add(new, head, head->next); 
}
[/cce_cpp]

上边是将一个节点插入到链表头部。

[cce_cpp]
static inline void list_add_tail(struct list_head *new, struct list_head *head) 
{ 
        __list_add(new, head->prev, head); 
}
[/cce_cpp]

将节点插入到链表的尾部。

3.删除节点

[cce_cpp]
static inline void __list_del(struct list_head * prev, struct list_head * next) 
{ 
        next->prev = prev; 
        prev->next = next; 
} 
static inline void list_del(struct list_head *entry) 
{ 
        __list_del(entry->prev, entry->next); 
        entry->next = LIST_POISON1; 
        entry->prev = LIST_POISON2; 
}
[/cce_cpp]

删除节点，仅仅是将数据节点从链表中去掉，数据节点仍然存在。删除之后的节点指向比较安全的位置：LIST_POISON1和LIST_POISON2。

4.替换节点

[cce_cpp]
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; 
}
[/cce_cpp]

用一个新节点替换链表中的某一个节点。

5.移动节点

[cce_cpp]
static inline void list_move(struct list_head *list, struct list_head *head) 
{ 
        __list_del_entry(list); 
        list_add(list, head); 
}
[/cce_cpp]

将某个节点移动到链表头部。

[cce_cpp]
static inline void list_move_tail(struct list_head *list, 
                                  struct list_head *head) 
{ 
        __list_del_entry(list); 
        list_add_tail(list, head); 
}
[/cce_cpp]

将某个节点移动到链表尾部。

6.从链表中取出数据

这个宏定义应该属于内核链表中最经典的链表操作方法之一。

[cce_cpp]
#define list_entry(ptr, type, member) \ 
        container_of(ptr, type, member)
[/cce_cpp]

使用list_entry宏来取出整个数据节点，其中ptr是指向整个数据节点中member的指针，type是整个数据节点的数据类型（注意：以数据类型作为参数），member是数据节点中用于链表的名称，注意是名称，不是变量。

在include/linux/kernel.h中查看container_of原型:

[cce_cpp]
#define container_of(ptr, type, member) ({                      \ 
        const typeof( ((type *)0)->member ) *__mptr = (ptr);    \ 
        (type *)( (char *)__mptr - offsetof(type,member) );})
[/cce_cpp]

这个宏设计得很精妙，通过计算偏移量来获得整个数据节点的地址：大括号中的第一段定义一个指向member地址的常量，并获取指向member的地址；第二行通过计算member在type中的偏移量获取type类型数据节点的地址。

再扩展一下，typeof是GCC在标准C的基础上新扩展的关键字，与sizeof类似，主要用于获取一个数据类型的名称，可以参考。

offsetof也是一个宏，在include/linux/stddef.h中有定义：

[cce_cpp]#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)[/cce_cpp]

size_t是为了增强程序的可移植性而采用的，不同系统上定义的size_t不一样。在32位系统中，（char *）为4个字节，size_t为unsigned int,是4个字节；在64位系统中，（char *）为8个字节，size_t被定义为unsigned long，为8个字节：
include/asm-generic/posix_types.h定义__kernel_size_t为unsigned int
arch/s390/include/asm/posix_types.h定义__kernel_size_t为unsigned long
include/linux/types.h定义size_t为__kernel_size_t。

7.链表非空否

[cce_cpp]
static inline int list_empty(const struct list_head *head) 
{ 
        return head->next == head; 
}
[/cce_cpp]

通过判断头指针的后继是否指向自身来判断链表是否为空。

8.遍历链表

[cce_cpp]
#define list_for_each(pos, head) \ 
        for (pos = (head)->next; pos != (head); pos = pos->next)
[/cce_cpp]

又是一个宏定义，pos需要提前声明。这种遍历方式一般适用于对节点不做修改的情况；当在遍历的过程中对节点做出修改会引起错误，因此内核中另外还定义了一种比较安全的遍历方式：

[cce_cpp]
#define list_for_each_safe(pos, n, head) \ 
        for (pos = (head)->next, n = pos->next; pos != (head); \ 
                pos = n, n = pos->next)
[/cce_cpp]

还有一个比较有用的：

[cce_cpp]
#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))
[/cce_cpp]

一个一个地取出head链表中的数据对象，并放入pos中。

9.合并两个链表

[cce_cpp]
static inline void __list_splice(const struct list_head *list, 
                                 struct list_head *prev, 
                                 struct list_head *next) 
{ 
        struct list_head *first = list->next; 
        struct list_head *last = list->prev; 

        first->prev = prev; 
        prev->next = first; 

        last->next = next; 
        next->prev = last; 
} 
static inline void list_splice(const struct list_head *list, 
                                struct list_head *head) 
{ 
        if (!list_empty(list)) 
                __list_splice(list, head, head->next); 
}
[/cce_cpp]

用于将list和head这两个链表合并成一个链表，新的链表仍以head为头指针。

三、补充

1.关于hlist

hlist即hash list，它是在普通的list的基础上设计出来的，目的是尽可能地将list的head由双指针缩减为单指针，也就是说hlist的表头只有一个指向首节点的指针，而没有指向尾节点的指针。也许在内核中，这样设计的链表可以在海量的hash表中存储的表头能减少一半的空间消耗。

2.关于链表中的RCU

RCU（Read-Copy Update）技术是内核中通过延迟写操作来提高同步性能的一项技术。一般情况下，系统数据中读取操作远多于写操作，而rwlock机制smp在环境下随着处理机的增多，性能会迅速下降。针对这一技术背景，IBMlinux中心提出了RCU技术，并将其应用于Linux内核当中。RCU技术的核心是将写操作分为写-更新两部，允许读操作在任何时候都能无阻碍访问；当系统有写错作的时候，更新动作一直延迟到对该数据的所有读操作完成为止。而RCU链表，就是加了RCU机制进行并发访问保护的链表，对RCU链表的操作和普通链表的操作方法基本相同，可以参考：include/linux/rculist.h

这里仅举一个例子：RCU模式下向链表中添加节点

[cce_cpp]
#define list_next_rcu(list)     (*((struct list_head __rcu **)(&(list)->next)))
static inline void __list_add_rcu(struct list_head *new, 
                struct list_head *prev, struct list_head *next) 
{ 
        new->next = next; 
        new->prev = prev; 
        rcu_assign_pointer(list_next_rcu(prev), new); 
        next->prev = new; 
}
static inline void list_add_rcu(struct list_head *new, struct list_head *head) 
{ 
        __list_add_rcu(new, head, head->next); 
}
[/cce_cpp]

list_next_rcu是获取list指向的下一个list_head_rcu的地址；__list_add_rcu中的
rcu_assign_pointer(list_next_rcu(prev), new); 意思是对插入值的指针作保护操作。