深度剖析Linux内核链表

新闻资讯 2023-06-18 10:25 87 0

👇👇关注后回复 “进群” ，拉你进程序员交流群👇👇

作者丨写代码的牛顿

来源丨编程学习总站（ID：xiedaimadeniudun）

—

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

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

结合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