Linux list.h 浅析

#　Linux 中的 list.h

基于内核版本5.15.158分析，该文件位于/include/linux/list.h，是在 Linux 中的众多数据结构中使用的双向链表结构。

原理架构

/include/linux/types.h中定义了链表节点struct list_head，包含了指向前后两个节点的双向指针。

1
2
3

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

区别于常用的 List 节点存储节点对象地址的形式，list.h这个双向链表的使用方式是将struct list_head声明为节点数据结构的变量成员。这种方式的好处是不再需要单独的一个链表头对象才能访问到各个节点。当索引到某个节点时，通过成员相对节点数据结构的结构体地址的偏移来从struct list_head还原这个节点的地址。

例如，在 Linux 的 pcb 结构struct task_struct中就有多个struct list_head成员，将一个 pcb 实例放在多个功能不同的链表上进行管理。

struct task_struct {
    /* ... */
    #ifdef CONFIG_PREEMPT_RCU
	/* ... */
	struct list_head		rcu_node_entry;
	/* ... */
#endif /* #ifdef CONFIG_PREEMPT_RCU */
#ifdef CONFIG_TASKS_RCU
	/* ... */
	struct list_head		rcu_tasks_holdout_list;
#endif /* #ifdef CONFIG_TASKS_RCU */
#ifdef CONFIG_TASKS_TRACE_RCU
	/* ... */
	struct list_head		trc_holdout_list;
#endif /* #ifdef CONFIG_TASKS_TRACE_RCU */
	/* ... */
	struct list_head		tasks;
#ifdef CONFIG_SMP
    /* ... */
}

操作

list 的初始化有两种方式，一种是用LIST_HEAD宏直接定义struct list_head并且初始化，适用于单独使用的链表节点；另一种是使用INIT_LIST_HEAD初始化声明好的struct list_head，两种初始化都会将节点的双向指针指向自己。

list 提供的操作主要为add、del、replace等，其功能简单如字面意思。值得注意的是有些功能有一些特别的地方，如在add操作中

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;
	WRITE_ONCE(prev->next, new);
}

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

head->next应该是一个多核同步的变量（即实质 volatile 的），为防止编译器优化将其放入寄存器或者 cache，使用这个宏使其这次写是直接写入内存的，保持并行场景中更严格的内存模型。

另外，在del操作中

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

Linux 内核为防止访问未初始化或者已删除的 entry，会将这些 entry 的两个指针指向两个非法的预设值，称为POISON，对其进行访问会触发 page fault（dmesg 应该里面会报 page not present 的错），这样也可以区分访问非法指针的错误出现在代码的哪里。

list.h中也有用于遍历链表的宏，可以方便地替换手写的循环，也有 lock-free 的 rcu 版本。

/**
 * list_for_each	-	iterate over a list
 * @pos:	the &struct list_head to use as a loop cursor.
 * @head:	the head for your list.
 */
#define list_for_each(pos, head) \
	for (pos = (head)->next; !list_is_head(pos, (head)); pos = pos->next)

/**
 * list_for_each_rcu - Iterate over a list in an RCU-safe fashion
 * @pos:	the &struct list_head to use as a loop cursor.
 * @head:	the head for your list.
 */
#define list_for_each_rcu(pos, head)		  \
	for (pos = rcu_dereference((head)->next); \
	     !list_is_head(pos, (head)); \
	     pos = rcu_dereference(pos->next))

hlist

上述均说的是 list，其实list.h中还有一种哈希链表 hlist，它的数据结构定义如下：

struct hlist_head {
	struct hlist_node *first;
};

struct hlist_node {
	struct hlist_node *next, **pprev;
};

其中hlist_node::pprev指向上一个节点的 next 指针，由于哈希链表有异质的链表头，而struct hlist_head和struct hlist_node在起始地址都有相同的成员struct hlist_node*，所以这个双重指针可以做到无论节点还是链表头做到操作的统一并且节约空间。