企业官网建设流程全解析

Linux 内核并没有采用教科书式的"数据节点内嵌指针"链表，而是自己实现了一套以struct list_head为核心的侵入式双向链表，其定义与全部 API 位于内核头文件include/linux/list.h中。本篇文章基于本仓库 DataStructures/linux-datastructures-1.md 展开，深入剖析list_head的结构设计、初始化宏、插入与删除接口，以及反向定位宿主结构体的container_of宏原理，并通过杂项字符驱动（misc 设备）的真实注册流程和本仓库多篇内核主题文章中的实际用例，帮助读者彻底理解这一在内核中被广泛使用的数据结构。

为什么内核要自己实现一套双向链表

几乎所有操作系统内核都会提供链表，Linux 内核也不例外。不过，Linux 内核并没有直接使用用户空间常见的"数据 + 指针"链表模型，而是在头文件include/linux/list.h中实现了侵入式（intrusive）双向链表，其核心结构体定义在include/linux/types.h中：

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

注意：struct list_head中没有数据域。这与传统的链表实现截然不同。例如 GNU C 库（glib）中的链表是这样定义的：

struct GList { gpointer data; GList *next; GList *prev; };

传统链表把"数据指针"和"链接指针"放在同一个节点里，节点直接保存指向数据的指针；而内核的侵入式链表恰好相反——节点只包含指向前驱和后继的指针，真正的数据被"附加"在链表节点之外，由宿主结构体把struct list_head作为自己的成员变量嵌入。

这种设计带来的最大好处是通用性：链表操作只关心next/prev两个指针，完全不感知宿主数据的类型，因此同一套list_add、list_del、list_for_each接口可以服务于内核中任意结构体。例如，内核中保存 NMI 描述符的结构体可以这样嵌入链表节点：

struct nmi_desc { spinlock_t lock; struct list_head head; };

宿主结构体（如nmi_desc）与链表节点（head）通过成员偏移关联起来——这正是后面要讲的container_of宏存在的意义。

实战案例：杂项字符驱动如何用链表管理设备

内核中有大量的地方使用list_head。本仓库 DataStructures/linux-datastructures-1.md 选取了一个非常直观的例子——杂项字符驱动（misc device），其 API 位于内核源文件drivers/char/misc.c。杂项字符驱动用于编写处理小型硬件和虚拟设备的小驱动，所有这类设备共享同一个主设备号：

#define MISC_MAJOR 10

但各自拥有不同的次设备号（minor number）。在 Linux 系统上执行ls -l /dev | grep 10可以看到：

crw------- 1 root root 10, 235 Mar 21 12:01 autofs drwxr-xr-x 10 root root 200 Mar 21 12:01 cpu crw------- 1 root root 10, 62 Mar 21 12:01 cpu_dma_latency crw------- 1 root root 10, 203 Mar 21 12:01 cuse drwxr-xr-x 2 root root 100 Mar 21 12:01 dri crw-rw-rw- 1 root root 10, 229 Mar 21 12:01 fuse crw------- 1 root root 10, 228 Mar 21 12:01 hpet crw------- 1 root root 10, 183 Mar 21 12:01 hwrng crw-rw----+ 1 root kvm 10, 232 Mar 21 12:01 kvm crw-rw---- 1 root disk 10, 237 Mar 21 12:01 loop-control crw------- 1 root root 10, 227 Mar 21 12:01 mcelog crw------- 1 root root 10, 59 Mar 21 12:01 memory_bandwidth crw------- 1 root root 10, 61 Mar 21 12:01 network_latency crw------- 1 root root 10, 60 Mar 21 12:01 network_throughput crw-r----- 1 root kmem 10, 144 Mar 21 12:01 nvram brw-rw---- 1 root disk 1, 10 Mar 21 12:01 ram10 crw--w---- 1 root tty 4, 10 Mar 21 12:01 tty10 crw-rw---- 1 root dialout 4, 74 Mar 21 12:01 ttyS10 crw------- 1 root root 10, 63 Mar 21 12:01 vga_arbiter crw------- 1 root root 10, 137 Mar 21 12:01 vhci

内核需要把所有这些共享主设备号 10 的杂项设备组织起来统一管理，这个任务正是由双向链表完成的。先看描述杂项设备的结构体miscdevice：

struct miscdevice { int minor; const char *name; const struct file_operations *fops; struct list_head list; struct device *parent; struct device *this_device; const char *nodename; mode_t mode; };

结构体第四个成员list就是链表节点，它把所有已注册的杂项设备串成一条链表。链表的头在源码文件drivers/char/misc.c开头以静态方式定义：

static LIST_HEAD(misc_list);

链表头的定义与初始化宏

LIST_HEAD(name)宏展开后实际上就是定义一个并初始化一个struct list_head类型的变量：

#define LIST_HEAD(name) \ struct list_head name = LIST_HEAD_INIT(name)

而LIST_HEAD_INIT使用变量自身的地址同时填充prev和next，使空链表头自指——既没有前驱也没有后继：

#define LIST_HEAD_INIT(name) { &(name), &(name) }

也就是说，一个空的list_head的两个指针都指向它自己，这是内核链表判断"链表是否为空"的基础。

当设备需要被动态注册时，misc_register函数一开始就用INIT_LIST_HEAD初始化miscdevice->list：

INIT_LIST_HEAD(&misc->list);

INIT_LIST_HEAD的效果与LIST_HEAD_INIT完全相同，只是它作用于一个已经存在的指针：

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

从本仓库其他章节也可以看到这两个宏在内核各处被反复使用：

• 信号量结构体的wait_list等待队列就是用LIST_HEAD_INIT静态初始化成空链表，参见 SyncPrim/linux-sync-3.md；
• init/main.c附近的init_mm内存描述符中的.mmlist同样以LIST_HEAD_INIT(init_mm.mmlist)初始化，参见 Initialization/linux-initialization-5.md；
• 根任务组root_task_group的children/siblings链表在调度器初始化时通过INIT_LIST_HEAD清零，参见 Initialization/linux-initialization-8.md；
• 工作队列（workqueue）宏在初始化work_struct时也会调用INIT_LIST_HEAD(&(_work)->entry)，参见 Interrupts/linux-interrupts-9.md。

向链表添加节点：list_add 与 __list_add

在device_create创建设备之后，misc_register用下面这条语句把新设备挂到misc_list链表头之后：

list_add(&misc->list, &misc_list);

list_add的接口很简单，但它真正的逻辑在内部函数__list_add中：

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

__list_add接收三个参数：

• new—— 要插入的新节点；
• prev—— 新节点将被插入到它之后；
• next—— 原本在prev之后的那个节点（即head->next）。

其实现只有四条指针赋值语句：

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

可以看到，__list_add的本质是在prev与next两个既有节点之间"缝合"一个新节点：先让next->prev指向新节点，再让new的next/prev分别指向next与prev，最后让prev->next指向新节点。四条赋值缺一不可，否则链表就会出现断链。

因此，经过LIST_HEAD_INIT初始化的misc_list与每个新注册设备miscdevice->list之间，就通过这种双向指针互链的方式组织成了一条完整的环形双向链表。

核心魔法：list_entry 与 container_of 反向定位宿主结构体

链表里只存指针，那么内核是如何从链表节点找回它所归属的宿主结构体的呢？这就要用到list_entry宏：

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

它接收三个参数：

• ptr—— 指向链表节点的指针（即宿主结构体内list_head成员的地址）；
• type—— 宿主结构体的类型；
• member—— 宿主结构体中那个list_head类型成员的名字。

例如，遍历misc_list时可以通过下面的方式拿到每一个miscdevice：

const struct miscdevice *p = list_entry(v, struct miscdevice, list)

拿到p之后就可以直接访问p->minor、p->name等字段了。list_entry本身只是container_of的简单包装，真正的工作由container_of完成：

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

这个宏看起来相当奇特，我们从左到右拆解它的三个关键点。

1. 花括号表达式：整个语句块的值等于最后一个表达式的值

container_of被一对花括号包起来，里面有两个表达式。这是 GCC 的语句表达式（statement expression）特性：编译器会依次执行花括号内的所有语句，并把最后一个表达式的值作为整个语句表达式的值返回。例如：

#include <stdio.h> int main() { int i = 0; printf("i = %d\n", ({++i; ++i;})); return 0; }

最终会打印2——两个++i依次执行，最后一个表达式的值2被作为结果传出。

2. typeof：返回变量/表达式的类型

typeof是 GCC 扩展，作用正如其名：返回给定变量或表达式的类型。container_of第一行中的typeof(((type *)0)->member)表示"type类型结构体的member成员的类型"，再配合const声明出一个与ptr同类型的指针__mptr。这一行并不是实现上必需的，但它承担了类型检查的重任：如果传入的ptr不是struct list_head *，编译器会给出类型不兼容的告警；同时((type *)0)->member会强制编译器检查type中确实存在名为member的成员，从而大大提升代码的鲁棒性。

3. 零偏移技巧与 offsetof：从成员地址反推结构体起始地址

container_of中最令人困惑的是那个0。它其实是"零基地址"技巧：把地址0强制转换为type *，再取它的member成员地址，得到的值恰好就是member在type中的字节偏移。用一个简单的例子验证：

#include <stdio.h> struct s { int field1; char field2; char field3; }; int main() { printf("%p\n", &((struct s*)0)->field3); return 0; }

由于int field1占 4 字节、char field2占 1 字节（偏移 4），field3的偏移就是0x5，程序输出的正是0x5。

offsetof宏（标准 C 也提供）就是这一技巧的官方化表达：

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

于是container_of的第二行逻辑就很清晰了：先用offsetof算出member相对于结构体起始地址的偏移，再从member的地址（__mptr）中减去这个偏移，得到的就是宿主结构体的起始地址。最后把它强制转换成type *返回。

总结：只要知道宿主结构体的类型type、list_head成员的名字member以及该成员的地址ptr，container_of就能通过一次减法运算反推出整个结构体的起始地址。这也是"侵入式链表"得以工作的基石——链表只需要维护指针，数据永远可以通过成员偏移"算"回来。

container_of在内核中的应用远不止链表。例如在 SyncPrim/linux-sync-4.md 中，互斥锁的慢路径处理函数就是通过container_of从锁状态变量反推出整个mutex结构体的。

完整的 list_head API 全景

list_add和list_entry远不是<linux/list.h>的全部。Linux 内核的双向链表实现还提供了以下常用 API：

其中list_add_tail与list_add是对称的，它调用__list_add(new, head->prev, head)，即把新节点插入到链表头节点的前驱（也就是链表的真正末尾）与链表头之间，从而实现 FIFO 式的追加。list_del则通过__list_del(entry->prev, entry->next)把前后两个节点直接互链、跳过当前节点。

遍历方面，list_for_each直接操作list_head *指针；而更常用的是list_for_each_entry，它在循环内部自动组合list_entry（即container_of），让使用者直接拿到宿主结构体：

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

循环从链表头的next出发，取出第一个宿主结构体，直到再次回到链表头为止。list_entry与list_for_each_entry配合，正是内核代码中遍历设备链表、进程链表、等待队列等最典型的写法。

内核各子系统中的实际用法佐证

list_head双向链表遍布内核各个子系统，本仓库的多个主题文章都直接依赖它，可以交叉印证其通用性：

• 信号量的等待队列：struct semaphore内嵌struct list_head wait_list，用于组织所有等待获取信号量的进程；down/up等操作正是围绕这条链表展开的，参见 SyncPrim/linux-sync-3.md；
• 进程地址空间管理：init_mm的mmlist链表把所有内存描述符串在一起，参见 Initialization/linux-initialization-5.md；
• 调度器任务组：根任务组通过children/siblings链表管理任务组之间的层级关系，参见 Initialization/linux-initialization-8.md；
• 工作队列：work_struct通过内嵌的entry链表节点挂入工作队列，参见 Interrupts/linux-interrupts-9.md；
• RCU 与基数树：radix_tree_node中的private_list也是list_head，参见 DataStructures/linux-datastructures-2.md。

使用 list_head 的注意事项

在实际使用内核链表时有几点需要特别留意：

1. 链表操作本身不是原子操作：list_add、list_del这类接口只是一组指针赋值，多个 CPU 并发修改同一链表时必须借助自旋锁等同步原语保护。正如 SyncPrim/linux-sync-1.md 等章节所讨论的，内核中链表操作几乎总是与锁配合使用（例如misc_register内部就用自旋锁保护misc_list的插入与遍历）。
2. 空链表头必须自指：无论是LIST_HEAD(name)静态定义，还是INIT_LIST_HEAD(&node)动态初始化，next与prev都必须指向自身，否则list_empty与遍历宏的判断就会失效。
3. container_of依赖成员偏移：list_entry的正确性建立在member确实是宿主结构体中的list_head成员这一前提上，传错成员名或类型会得到未定义行为；好在container_of第一行的类型检查能帮助提前发现大部分错误。

小结

Linux 内核通过struct list_head实现了一种通用的侵入式双向链表：节点只保存next/prev指针，数据通过成员嵌入与container_of的偏移运算与之关联。以杂项字符驱动的misc_list为例，我们完整走通了"定义链表头（LIST_HEAD）→ 初始化节点（INIT_LIST_HEAD）→ 插入节点（list_add/__list_add）→ 反向取回宿主结构体（list_entry/container_of）→ 遍历（list_for_each_entry）"的全部环节。这套设计让链表操作与数据类型彻底解耦，成为内核中组织对象集合的事实标准。本仓库 DataStructures/linux-datastructures-1.md 是该主题的原始出处，后续还可继续阅读 基数树 与 位数组，了解内核数据结构的全貌。