linux学习18，内核是如何操作链表的

上一节较为详细的介绍了 linux 内核中链表的设计与实现，能够看出，内核实际上是将链表“塞入”数据结构的。事实上，为了方便的操作这些链表，linux内核实现了一系列方法，本节将了解此。

链表的初始化

正如上一节介绍的，list_head 本身没有记录额外的信息，它仅仅起到连接各个数据节点的作用，所以在 linux 内核中，链表常常都是嵌入数据结构使用的，由这些数据结构存储需要记录的数据。例如将 list_head 嵌入 struct fox:

struct fox{
    int tail_len;
    int weight;
};
// 嵌入 list_head，构成链表节点。
struct fox{
    int tail_len;
    int weight;
    struct list_head list;
};

链表特别适合记录动态创建的数据，请看下面的C语言代码：

struct fox* rf;
rf = kmalloc(sizeof(struct fox), GFP_KERNEL);
rf->tail_length = 40;
rf->weight = 6;
INIT_LIST_HEAD(&rf->list);

实际上，程序中的多数元素都是在程序运行时动态创建的，若希望使用链表，则最好将其初始化，linux 内核提供了 INIT_LIST_HEAD() 函数用于初始化链表，它的C语言代码如下：

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

可以看出，linux 内核初始化链表相当简单，就是让 list 的 prev 和 next 指针都指向自己而已。INIT_LIST_HEAD() 虽然很简单，但是却很有用，它可以避免 list 的 prev 和 next 指向未知的区域。

指针指向未知区域，是非常危险的。（为什么危险，可以参考我之前的文章。）

我们也可以直接使用 LIST_HEAD() 宏定义并初始化一个链表，它的 C语言代码如下，请看：

#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
    struct list_head name = LIST_HEAD_INIT(name)

该宏定义了一个名为 name 的链表，并按照 INIT_LIST_HEAD() 函数方式初始化了该链表。

向链表加入一个节点

以上介绍的是 linux 内核创建并初始化一个新链表的方法，如何将其加入已有的链表呢？linux 内核定义了 list_add() 函数，它的C语言代码如下，请看：

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);
}

该函数往链表 head 节点后插入了 new 节点。从 __list_add() 函数可以看出，这一操作无非就是调整了各个链表节点的指向关系而已。

上一节我们说过，linux 内核使用的链表都是双向环形链表，所有没有“首尾”的概念，每个节点都可以当作 head 节点。

例如，假设有如 strcut fox* 型的节点 f，若想将其加入 fox_list 链表，可以这么做：

list_add(&f->list, &fox_list)

list_add_tail() 函数和 list_add() 函数是相似的，它的 C语言代码如下：

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

容易看出，与 list_add() 函数不同的是，list_add_tail() 函数是将 new 节点插入到 head 节点的前面。

从链表删除节点

既然有往链表加入节点的需求，也一定有从链表删除节点的需求，linux 内核是通过 list_del() 函数实现的，它的C语言代码如下：

static inline void __list_del(struct list_head * prev, struct list_head * next)
{
     next->prev = prev;
     prev->next = next;
}
#define LIST_POISON1  ((void *) 0x00100100)
#define LIST_POISON2  ((void *) 0x00200200)
static inline void list_del(struct list_head *entry)
{
     __list_del(entry->prev, entry->next);
     entry->next = LIST_POISON1;
     entry->prev = LIST_POISON2;
 }

__list_del() 函数是删除节点的核心部分，不过从C语言代码可以看出，它仅仅是将节点从链表移出而已，并没有释放该节点，也就是说，之后 linux 内核还能继续使用该节点中的数据。

list_del() 函数的后两行让被删除节点的 prev 和 next 指针指向指定值了，这两个值是非 NULL 值，但是也能引起页异常，避免调用者因为使用没有初始化的节点引发的错误。

上一节说过，链表适合记录需要遍历的数据，那么，linux 内核是怎样遍历链表的呢？答案是使用 list_for_each() 宏，它的C语言代码如下：

 #define list_for_each(pos, head) \
     for (pos = (head)->next; prefetch(pos->next), pos != (head); \
            pos = pos->next)

容易看出，list_for_each() 宏其实就是一个 for(;;) 循环的头而已，它从 head->next 开始遍历，每次让 post 指向下一个节点，遍历到 pos == head 结束（一圈，即全部链表节点）。

不过，list_for_each() 宏操作的都是 list_head，我们更常需要遍历的其实是存储数据的结构体，当然可以如下使用：

list_for_each(p, &fox_list){
    f = list_entry(p, struct fox, list);
    //...
}

但是，更方便的方法是使用 list_for_each_entry() 宏，它帮助我们找到结构体指针了，请看C语言代码：

#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))

如上一节介绍的一致，双向链表既可以往前遍历，也可以往后遍历。linux 内核提供了反向遍历的宏——其实就是在正向宏后加上 reverse 而已：

list_for_each_entry_reverse(pos, head, member)

遍历同时删除

以上遍历宏都是建立在链表结构不会改变的基础上的，也就是说标准的遍历过程中是不能删除节点的，否则接下来的遍历就找不到 next 或者 prev 指针了。一个解决方法就是在删除节点时，使用临时变量先将该节点的信息存储下来，事实上，linux 内核也的确是这么设计的，请看：

 #define list_for_each_entry_safe(pos, n, head, member)          \
     for (pos = list_entry((head)->next, typeof(*pos), member),  \
         n = list_entry(pos->member.next, typeof(*pos), member); \
          &pos->member != (head);                    \
         pos = n, n = list_entry(n->member.next, typeof(*n), member))

借助 list_for_each_entry_safe() 宏，我们就可以在遍历链表节点的同时删除它。

linux 内核操作链表非常关键的函数或者宏就介绍到这里。这里再延伸一点，使用上面介绍的方法遍历链表节点时，是不能有其他地方并发删除的，如果有，就应该做好同步。