内核链表

1-背景

链表是最最常用的数据结构之一，在c语言中没有cpp stl中那些可以动态申请的各种容器，所以链表是非常常用的用来动态分配的数据结构。

内核中也定义了一些基础的api，用来实现链表的各种操作，并且这些基础api也是经过了多年的维护、优化，最大程度的保障了性能以及安全。

在这片文章里总结、记录一下内核链表api的操作吧。

比较有趣的是，这些内核链表的api几乎都是linus 19年前实现的代码，这么多年一直没人修改或者说不必修改。

2-数据结构

内核定义了一个标准的基础链表数据结构list_head

struct list_head {
	struct list_head *next, *prev;
};

可以看到这个头是一个双向链表，但是链表里只有最基础的地址指针，也就是地址域，而没有其他数据域，所以内核中常用的方法是，在其外层再套一个结构体，由我们自己定义数据域，类似用法如下：

struct node {
    int val;
    struct list_head head;
};

这里其实与我们常见的链表不太一致的地方在于，通常链表的指针都是指向自己数据所对应的地址，也就是下边这种

struct node {
    int val;
    struct node *next;
}

但是内核使用list_head的话，虽然可以定制我们自己的数据域，但是他是怎么找到实际外层整个链表节点地址的呢？

这里就不得不提到内核中大名鼎鼎的container_of，通过查找head的地址，直接找到其外层整个链表node地址。

3-初始化

内核有两个初始化链表的宏

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

这里LIST_HEAD可以看作是LIST_HEAD_INIT的更上层版本，当我们执行LIST_HEAD(my_list)的时候，我们就会创建出一个名为my_list的内核链表头，这个头是一个纯粹的头，没有任何数据域，而后续我们需要继续往这个头上添加节点。

而LIST_HEAD_INIT是指传入了一个name，而这个name的结构是需要我们自己去定义的，根据下边的函数可以看到name的结构是struct list_head *list，所以就是说在使用LIST_HEAD_INIT需要自己定义链表头的数据结构，而LIST_HEAD已经帮你定义好了。

所以二者的使用也如下：

• LIST_HEAD

LIST_HEAD(my_list); // 初始化好了一个名为my_list的链表，其目前只包含标准头

• LIST_HEAD_INIT

// 方式1
struct list_head my_list;
LIST_HEAD_INIT(my_list); // 初始化了一个名为my_list的链表，其目前只包含标准头
// 方式2
struct my_list {
    int val;
    struct list_head list;
};
struct my_list test_list;
LIST_HEAD_INIT(&test_list.list); // 初始化了一个名为test_list的自定义链表

而关于第二种用法，其实最常见的方式是在自定义的首节点里初始化自己

struct my_list {
    int val;
    struct list_head list;
};
struct my_list first_node {
    .val = 1,
    .list = LIST_HEAD_INIT(first_node.list),
};

4-添加、删除节点

链表中的添加和删除是常见的操作，内核提供了通用接口来执行这些操作

• 添加：list_add、list_add_tail
• 删除：list_del

4.1-添加

4.1.1-头插list_add

list_add其函数原型如下

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

static inline void __list_add(struct list_head *new,
			      struct list_head *prev,
			      struct list_head *next)
{
	if (!__list_add_valid(new, prev, next))
		return;

	next->prev = new;
	new->next = next; // 插入节点next指向head后的第一个节点
	new->prev = prev;
	WRITE_ONCE(prev->next, new); // head的next指向新插入节点
}

其实这里实现的操作也很简单，就是把新节点的指针添加到head之后第一个节点，例如原来的链表如下是head->1->2，如果执行了list_add(3)则会成为head->3->1->2。

4.1.2-尾插list_add_tail

内核同样提供了尾插的函数

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

static inline void __list_add(struct list_head *new,
			      struct list_head *prev,
			      struct list_head *next)
{
	if (!__list_add_valid(new, prev, next))
		return;

	next->prev = new;
	new->next = next; // 插入节点的next是head
	new->prev = prev; // 插入节点的prev指向原来的尾节点，也就是头结点的prev
	WRITE_ONCE(prev->next, new); // 尾结点的next指向插入节点
}

其实这里很有趣的是，其底层的函数是没有修改的，只是把传参修改一下，就变成了插入到尾结点后。例如原来的链表如下是head->1->2，如果执行了list_add(3)则会成为head->1->2->3。

4.1.3-举例

struct my_list {
    int val;
    struct list_head list;
};

LIST_HEAD(my_list_head);

struct my_list *new_node = kmalloc(sizeof(*new_node), GFP_KERNEL);

list_add_tail(&new_node->list, &my_list_head);
list_add(&new_node->list, &my_list_head);

4.2-删除

static inline void list_del(struct list_head *entry)
{
	__list_del_entry(entry);
	entry->next = LIST_POISON1;
	entry->prev = LIST_POISON2;
}
static inline void __list_del_entry(struct list_head *entry)
{
	if (!__list_del_entry_valid(entry))
		return;

	__list_del(entry->prev, entry->next);
}
static inline void __list_del(struct list_head * prev, struct list_head * next)
{
	next->prev = prev;
	WRITE_ONCE(prev->next, next);
}

这里的操作也很简单，就是把当前链表头的prev和next置空，然后把其前后的节点处理一下。

这里__list_del_entry_valid判断链表节点是否有效的一个方式就是检查这个地址是不是LIST_POISON1或者LIST_POISON2的

__list_valid_slowpath
bool __list_del_entry_valid_or_report(struct list_head *entry)
{
	struct list_head *prev, *next;

	prev = entry->prev;
	next = entry->next;

	if (CHECK_DATA_CORRUPTION(next == NULL,
			"list_del corruption, %px->next is NULL\n", entry) ||
	    CHECK_DATA_CORRUPTION(prev == NULL,
			"list_del corruption, %px->prev is NULL\n", entry) ||
	    CHECK_DATA_CORRUPTION(next == LIST_POISON1,
			"list_del corruption, %px->next is LIST_POISON1 (%px)\n",
			entry, LIST_POISON1) ||
	    CHECK_DATA_CORRUPTION(prev == LIST_POISON2,
			"list_del corruption, %px->prev is LIST_POISON2 (%px)\n",
			entry, LIST_POISON2) ||
	    CHECK_DATA_CORRUPTION(prev->next != entry,
			"list_del corruption. prev->next should be %px, but was %px. (prev=%px)\n",
			entry, prev->next, prev) ||
	    CHECK_DATA_CORRUPTION(next->prev != entry,
			"list_del corruption. next->prev should be %px, but was %px. (next=%px)\n",
			entry, next->prev, next))
		return false;

	return true;
}

5-遍历

5.1-遍历

内核同样模板化的节点遍历的api，其实内核存在两个遍历的api，区别是带不带safe

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

#define list_for_each_entry(pos, head, member)				\
	for (pos = list_first_entry(head, typeof(*pos), member);	\
	     !list_entry_is_head(pos, head, member);			\
	     pos = list_next_entry(pos, member))

这两个宏都用于遍历一个链表，但它们之间有一个关键区别：

• list_for_each_entry_safe(pos, n, head, member)：这个宏用于在遍历链表的过程中安全地删除链表中的元素。它使用两个指针pos和n来遍历链表，其中pos指向当前元素，n指向下一个元素。这样，在遍历过程中，即使删除了pos指向的元素，也可以继续使用n指针来遍历链表。
• list_for_each_entry(pos, head, member)：这个宏用于遍历链表，但在遍历过程中不允许删除链表中的元素。它只使用一个指针pos来遍历链表。

总的来说，这两个宏的主要区别在于是否允许在遍历过程中安全地删除链表中的元素。

两个函数传递的最后一个参数list是指链表结构体里的指针域变量名称，也就是

struct my_list {
    int val;
    struct list_head list; // list指代这个
};

如果我将结构体修改为下列

struct my_list {
    int data;
    struct list_head list_next;
};

则遍历则会成为

list_for_each_entry_safe(pos, tmp, &test_list.list_next, list_next)

使用的具体方法如下

• 遍历删除场景

  struct my_list *pos, *tmp; // 遍历用的tmp，而删除的用pos

  list_for_each_entry_safe(pos, tmp, &test_list.list, list) {
      printk(KERN_INFO "Data: %d\n", pos->data);
      list_del(&pos->list);
      kfree(pos);
  }

• 只遍历不删除

  struct my_list *pos; // 遍历用的pos

  list_for_each_entry(pos, &test_list.list, list) {
      printk(KERN_INFO "Data: %d\n", pos->data);
  }

5.2-获取节点

#define list_next_entry(pos, member) \
	list_entry((pos)->member.next, typeof(*(pos)), member)

#define list_entry(ptr, type, member) \
	container_of(ptr, type, member)

这里进行遍历的核心是使用list_entry通过list_head地址在节点结构体里的偏移，来获取链表节点的地址，也就是通过我们前文提到的container_of。

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

可看到，最底层的方法就是通过list_head的地址减去在链表node结构体中的offset（list_head的长度），这样得到的就是node对应的首地址。

6-其他常用

内核还有其他关于链表常用的操作函数，具体原理其实同上差不多，我们就不详细分析了。

• list_for_each_entry_reverse：逆序遍历链表。

• list_first_entry(ptr, type, member): 获取链表的第一个元素。

• list_last_entry(ptr, type, member): 获取链表的最后一个元素。

• list_next_entry(pos, member): 获取链表中当前元素pos的下一个元素。

• list_prev_entry(pos, member): 获取链表中当前元素pos的上一个元素。

7-例程汇总

把上边提到过的api例程进行一下汇总，使用方法如下

#include <linux/init.h>
#include <linux/module.h>
#include <linux/list.h>
#include <linux/slab.h>

struct my_list {
    int data;
    struct list_head list_next;
};

static struct my_list my_list_head;

static int __init list_example_init(void)
{
    struct my_list *new_node1, *new_node2;

    // 初始化链表头
    INIT_LIST_HEAD(&my_list_head.list_next);

    // 创建新节点
    new_node1 = kmalloc(sizeof(*new_node1), GFP_KERNEL);
    new_node2 = kmalloc(sizeof(*new_node2), GFP_KERNEL);
    if (!new_node1 || !new_node2) {
        printk(KERN_ERR "Failed to allocate memory for new node.\n");
        return -ENOMEM;
    }

    // 初始化新节点并添加到链表
    new_node1->data = 1;
    new_node2->data = 2;
    list_add_tail(&new_node1->list_next, &my_list_head.list_next);
    list_add(&new_node2->list_next, &my_list_head.list_next);

    return 0;
}

static void __exit list_example_exit(void)
{
    struct my_list *pos, *tmp;

    // 遍历并删除链表中的所有元素
    list_for_each_entry_safe(pos, tmp, &my_list_head.list_next, list_next) {
        printk(KERN_INFO "Removing node with data: %d\n", pos->data);
        list_del(&pos->list_next);
        kfree(pos);
    }
}

module_init(list_example_init);
module_exit(list_example_exit);
MODULE_LICENSE("GPL");