Linux内核链表深度剖析

Linux内核链表是Linux内核最经典的数据结构之一，Linux内核链表最大的优点就是节省内存，对链表的各项操作较快，实现的思路耳目一新，而且在Linux内核里频繁使用，比如：内存管理，进程调度等。
Linux内核链表是一个双向循环链表，核心思想就是把链表结点放在数据结点里面，通过前后指针分别指向前后数据结点里面的链表结点，这样就可以将各个数据结点连接在一起。

一、链表结点定义

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 INIT_LIST_HEAD(struct list_head *list)
{
    list->next = list;
    list->prev = list;
}

INIT_LIST_HEAD函数prev指针和next指针指向链表头结点。LIST_HEAD_INIT宏初始化链表头结点next指针和prev指针保存头结点地址，实际上和INI_LIST_HEAD函数初始化效果一样，LIST_HEAD宏就是链表结点的完整初始化。我们以实际代码为例：

struct list_head list;
LIST_HEAD(list);              //list = {&list, &list}

三、内核链表插入结点

/*
 * Insert a new entry between two known consecutive entries.
 *
 * This is only for internal list manipulation where we know
 * the prev/next entries already!
 */
#ifndef CONFIG_DEBUG_LIST
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;
}
#else
extern void __list_add(struct list_head *new,
                  struct list_head *prev,
                  struct list_head *next);
#endif

/**
 * list_add - add a new entry
 * @new: new entry to be added
 * @head: list head to add it after
 *
 * Insert a new entry after the specified head.
 * This is good for implementing stacks.
 */
#ifndef CONFIG_DEBUG_LIST
static inline void list_add(struct list_head *new, struct list_head *head)
{
    __list_add(new, head, head->next);
}
#else
extern void list_add(struct list_head *new, struct list_head *head);
#endif
/**
 * list_add_tail - add a new entry
 * @new: new entry to be added
 * @head: list head to add it before
 *
 * Insert a new entry before the specified head.
 * This is useful for implementing queues.
 */
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
    __list_add(new, head->prev, head);
}

我们作图解释会更容易理解内核链表插入操作。
直接看代码我们即可知道内核链表实际上采用的是尾插法，并且有一个头结点。
内核链表插入结点前如图1所示：

插入结点前.PNG

图1

内核链表插入结点后如图2所示：

插入结点后.PNG

结合list_add_tail函数分析可知，假设链表list插入结点node，则next=list->next，prev=list;再调用__list_add则可将新结点插入到链表里面。

四、内核链表删除结点

/*
 * Delete a list entry by making the prev/next entries
 * point to each other.
 *
 * This is only for internal list manipulation where we know
 * the prev/next entries already!
 */
static inline void __list_del(struct list_head * prev, struct list_head * next)
{
    next->prev = prev;
    prev->next = next;
}

/**
 * list_del - deletes entry from list.
 * @entry: the element to delete from the list.
 * Note: list_empty() on entry does not return true after this, the entry is
 * in an undefined state.
 */
#ifndef CONFIG_DEBUG_LIST
static inline void list_del(struct list_head *entry)
{
    __list_del(entry->prev, entry->next);
    entry->next = LIST_POISON1;
    entry->prev = LIST_POISON2;
}
#else
extern void list_del(struct list_head *entry);
#endif

直接分析代码可知，删除结点实际上就是将目标结点后面一个结点的前向指针指向目标结点的前向结点，目标结点的后向结点的前向指针指向目标结点的前向结点。

结尾

Linux内核链表还有很多有意思的实现，例如遍历，获取数据结点结构体首地址等，下一章再详细分析。