一文 吃透 Linux 内核链表(深度分析)

大家好，我是蟹老板~

我们在学习数据结构的时候，链表应该算是最早接触到的数据结构之一。单链表、双向链表、循环链表，大家可能早就已经写过好多遍了。创建一个节点，在节点里面放数据，然后再放一个 next 指针，想要支持反向遍历的话，就再增加一个 prev 指针。看起来链表好像没有什么特别复杂的地方。

可是第一次打开 Linux 内核源码，看到下面这个结构体的时候，好多开发者都会产生一个非常直接的疑问：

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

问题来了：

数据呢？

一个链表节点里面既没有 int，也没有 char *，更加没有一个万能的 void *data，只有两个指针。

那么 Linux 内核里面那些进程对象、设备对象、文件系统对象，到底是怎么被放进链表里面的？

更加让人疑惑的是，我们在内核代码中还经常会看到：

list_add(&obj->list, &head);

遍历的时候却突然又变成：

list_for_each_entry(pos, &head, list)

明明链表里面保存的是：

struct list_head

为什么遍历出来以后，却能够直接变回：

struct my_object *

？？？

这恰恰就是 Linux 内核链表最值得学习的地方。

它真正厉害的并不是实现了一个“双向循环链表”，因为双向循环链表本身并不稀奇。Linux 内核链表真正精妙的地方在于：

它把“链表关系”和“业务数据”彻底分开了。

链表只负责：

谁在我前面谁在我后面

至于节点里面真正装的是什么数据：

进程？设备？inode？网络对象？驱动私有结构？

链表根本不关心。

这套设计使得 Linux 只需要实现一套通用的链表操作，就能够管理各种完全不同的数据结构。Linux 官方文档也明确指出，内核双向链表采用的正是“把 struct list_head 嵌入业务结构体”的方式，从而使链表操作逻辑无需知道实际数据类型。

本文就从这个最核心的问题开始：

struct list_head 里面没有数据，那么链表的数据究竟存在哪里？

然后一步一步把 Linux 内核链表的侵入式设计、初始化、插入删除、container_of()、遍历宏、hlist、并发保护以及实际内核模块使用方式完整梳理清楚。

一、为什么需要重新理解链表？

1.1 从教科书链表到内核链表的认知升级

我们平常学习链表的时候，最容易写出这样的结构：

struct student_node {    int id;    char name[32];struct student_node *next;};

如果想要双向遍历：

struct student_node {    int id;    char name[32];struct student_node *next;struct student_node *prev;};

从直觉上来看，这完全没有问题。

整个节点里面包含两类东西：

业务数据+链表关系

可以画成：

┌────────────────────────┐│ id                     ││ name                   ││ next ----------------------→│ prev ----------------------→└────────────────────────┘

但是问题很快就来了。

今天我要管理：

struct student

于是写：

struct student_node

明天我要管理：

struct device

于是可能又写：

struct device_node

后天我要管理：

struct packet

可能又得重新实现：

packet_list_add()packet_list_del()packet_list_find()packet_list_for_each()

这样一来，我们虽然学习的是一种链表算法，真正写代码的时候却很容易变成：

student 一套链表device 一套链表packet 一套链表task 一套链表……

大量代码做的事情其实完全一样：

修改 next修改 prev连接节点删除节点遍历节点

区别仅仅在于：

节点里面装的数据类型不同。

Linux 内核显然不能接受这种大量重复实现。

所以 Linux 采用了完全不同的思路：

不要让链表节点拥有数据，而是让数据拥有链表节点。

这就是理解内核链表必须完成的第一次认知升级。

1.2 Linux 内核链表的地位

Linux 内核里面大量数据结构都会使用链式组织方式。

例如当前内核源码中的 task_struct 包含多个链表或哈希链表成员，用来参与不同关系的组织；文件系统中的 inode 同样能够看到 list_head、hlist_node、hlist_head 等成员；内核 slab 子系统也存在标准链表维护缓存对象集合。

也就是说，学习 Linux 内核源码的时候，你很快就会遇到：

struct list_head

然后又遇到：

list_add()list_del()list_for_each_entry()list_entry()

再往后还会遇到：

hlist_headhlist_nodehlist_for_each_entry()

甚至还有：

list_add_rcu()list_for_each_entry_rcu()llist_add()

所以 Linux 链表不是一个学完之后很少再见到的知识点。

恰恰相反，它属于：

读内核源码必须掌握的基础设施之一。

不过 Linux 官方文档也专门提醒了一点：链表虽然在内核中非常常见，却并不代表它永远都是最佳数据结构。由于链表的数据局部性较差，在性能敏感场景里面，数组或者其他内核数据结构有时候反而更加合适。

所以学习内核链表的正确目标并不是：

“以后什么数据都往链表里面塞。”

而应该是：

看懂它为什么这样设计，知道什么时候适合使用。

1.3 一个直击灵魂的问题：链表的数据存在哪里？

重新来看：

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

如果我们按照传统链表的思维去看，一定会觉得它少了东西。

但是 Linux 的答案恰恰是：

它什么都没有少。

因为 list_head 本来就不负责保存业务数据。

真正的数据可能是：

struct my_data {    int id;    char name[32];struct list_head list;};

内存布局可以想象成：

struct my_data┌─────────────────────────────┐│ id                          ││ name[32]                    ││                             ││ list.next ----------------------→ 下一个对象里的 list│ list.prev ----------------------→ 上一个对象里的 list└─────────────────────────────┘

真正连起来的确实只有：

list_head

可是每一个：

list_head

都嵌入在一个完整的：

struct my_data

里面。

所以你可以记住一句非常重要的话：

传统链表是“节点里面装数据”，Linux 内核链表是“数据里面装节点”。

甚至可以更加形象一点：

节点不存数据，数据存节点。

Linux 官方链表文档给出的设计正是如此：把 struct list_head 作为实际成员嵌入希望加入链表的数据结构中，然后利用 container_of() 模式从链表成员重新得到外围宿主对象。

二、初识内核链表：侵入式链表的设计哲学

2.1 传统链表 vs 内核链表

先来看传统链表。

假设我们管理学生：

struct student_node {    int id;    char name[32];struct student_node *next;struct student_node *prev;};

这个结构的思路就是：

链表节点├── 数据├── next└── prev

节点把业务数据“包”了起来。

所以可以称为一种：

包裹式设计。

如果我们想写一个更加通用的链表，也许会想到：

struct list_node {    void *data;struct list_node *next;struct list_node *prev;};

然后：

list_node    │    └── data → struct student

这样确实通用很多。

但是又多了一层：

链表节点对象↓data 指针↓真正的数据对象

Linux 没有采用这个思路。

Linux 反过来：

struct student {    int id;    char name[32];struct list_head list;};

于是结构变成：

业务对象├── id├── name└── list_head

这就是典型的：

Intrusive List——侵入式链表。

所谓“侵入”，并不是说链表会破坏数据。

而是：

想要让某个对象加入这套链表体系，就需要在这个对象内部嵌入对应的链表节点。

Linux 官方文档同样把这种“链表成员直接嵌入宿主结构”的方式作为内核标准双向链表的基础。

2.2 侵入式设计的巨大优势

第一大优势：真正的数据类型无关

假设有：

struct student {    int id;struct list_head list;};

也有：

struct device_info {    int dev_id;    char name[64];struct list_head list;};

甚至：

struct packet {    unsigned int len;    void *data;struct list_head list;};

对于链表底层来说，它看到的始终都是：

struct list_head *

因此插入逻辑完全可以统一成：

list_add(&student->list, &head);list_add(&device->list, &head);list_add(&packet->list, &head);

底层根本不用知道：

student 有几个字段device 有多少成员packet 是什么类型

它只处理：

nextprev

于是实现了一套代码管理任意宿主类型。

第二大优势：一个对象能够同时加入多个链表

这个优势特别重要。

假设：

struct task {    int pid;struct list_head all_tasks;struct list_head group_list;};

同一个对象里面存在两套：

list_head

于是：

all_tasks

可以把它挂到“所有任务”链表中。

同时：

group_list

又能够让它加入另外一种逻辑关系。

内存上是同一个对象：

┌────────────────────────────┐│ pid                        ││                            ││ all_tasks.next/prev        │ ───→ 链表 A│                            ││ group_list.next/prev       │ ───→ 链表 B└────────────────────────────┘

如果采用：

struct list_node {    void *data;};

当然也可以做到多重挂载，但是通常需要额外创建多个外部节点。

侵入式结构则天然允许：

一个业务对象拥有多种链表身份。

在真实 Linux 内核中，一个复杂结构体拥有多个 list_head、hlist_node 成员是非常常见的事情。当前 task_struct、inode 等源码结构就能看到这种设计。

第三大优势：链表逻辑与业务逻辑解耦

Linux 的链表函数只处理：

struct list_head

业务代码负责：

struct my_data

两边之间靠：

container_of()

连接。

所以可以理解成：

链表层：我只关心 next / prev业务层：我只关心 id / name / state / ...

这就是非常典型的通用基础设施设计。

第四大优势：一种很有意思的 C 语言“面向对象”思维

C 语言本身没有：

classinheritancetemplategeneric

这些高级抽象。

但是 Linux 经常通过：

结构体嵌入+container_of()+函数指针

实现类似的对象抽象。

例如：

struct my_device {    int id;struct list_head node;};

链表代码只认识：

struct list_head

业务代码却可以通过：

container_of()

重新获得：

struct my_device

这种设计思想在 Linux 内核中不仅用于链表，也广泛存在于设备模型等代码中。官方驱动模型文档也专门说明过 container_of() 从嵌入成员反推外围结构体的使用模式。

2.3 内核链表在源码中的位置

理解源码的时候，可以先记住两个非常重要的位置。

include/linux/types.h

当前主线内核中可以看到：

struct list_head {struct list_head *next, *prev;};struct hlist_head {struct hlist_node *first;};struct hlist_node {struct hlist_node *next, **pprev;};

也就是说：

list_headhlist_headhlist_node

这些基础结构定义位于 include/linux/types.h。

include/linux/list.h

真正大量的链表操作接口则集中在：

include/linux/list.h

比如：

INIT_LIST_HEADlist_addlist_add_taillist_dellist_del_initlist_movelist_replacelist_emptylist_for_eachlist_for_each_entry……

Linux 官方文档也明确说明，使用内核标准链表接口时需要包含：

#include <linux/list.h>

所以以后想深入研究某一个链表 API：

不要只查博客。

直接打开：

include/linux/list.h

很多设计看几行源码就会瞬间明白。

三、核心数据结构：struct list_head 详解

3.1 list_head 结构体定义

它的结构简洁到了极致：

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

只有：

nextprev

两个指针。

假设有三个对象：

ABC

真正通过链表连接起来的，并不是整个 A、B、C：

A → B → C

严格来说，是：

A.list ↔ B.list ↔ C.list

链表层真正看到的是：

struct list_head

至于 list_head 外面包着什么：

struct Astruct Bstruct C

链表并不需要知道。

3.2 为什么是双向循环链表？

Linux 标准 list_head 是：

双向 + 循环。

Linux 官方链表文档明确说明了这一点。

例如：

          ┌────────────────────────────┐          ↓                            │HEAD ↔ NODE1 ↔ NODE2 ↔ NODE3 ↑                            ↓ └────────────────────────────┘

也就是说：

HEAD.next      = NODE1NODE1.prev     = HEADNODE3.next     = HEADHEAD.prev      = NODE3

这样做有一个非常大的好处：

很多边界操作不需要单独处理：

NULL

。

传统非循环链表经常需要：

if (node->next != NULL)

或者：

if (head == NULL)

而循环链表可以把：

HEAD

本身作为天然的哨兵节点。

3.3 头节点 Head 的特殊性

假设：

struct list_head my_list;

这里：

my_list

一般充当链表头。

它通常不是一个真正的业务数据节点。

而是：

Sentinel——哨兵节点。

例如空链表：

        ┌───────────┐        ↓           │     ┌──────┐       │     │ HEAD │───────┘     └──────┘

实际上：

head.next = &head;head.prev = &head;

所以：

next 指向自己prev 指向自己

就表示：

链表里面一个真正的数据节点都没有。

这也是为什么：

list_empty(&head)

本质上能够通过判断：

head.next == &head

来确定链表是否为空。当前 list_empty() 实现正是基于这一关系。

四、链表的初始化：从零开始构建

4.1 静态初始化

Linux 提供：

LIST_HEAD_INIT(name)

用于产生一个：

next 指向自己prev 指向自己

的初始化值。

当前源码中的思想可以简化理解为：

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

然后：

LIST_HEAD(name)

相当于完成：

声明+初始化

例如：

LIST_HEAD(my_list);

创建出来以后立刻就是一个合法的空链表头。当前主线 list.h 中 LIST_HEAD_INIT() 和 LIST_HEAD() 就是按照这种自引用方式实现的。

所以：

LIST_HEAD(my_list);

完成以后：

my_list.next ───┐                ↓             my_list                ↑my_list.prev ───┘

4.2 动态初始化

如果链表头是运行期间创建的，比如：

struct my_device {struct list_head data_list;};

那么通常会：

INIT_LIST_HEAD(&dev->data_list);

它的本质仍然非常简单：

list->next = listlist->prev = list

当前主线内核实现使用 WRITE_ONCE() 完成这两个写操作。

所以一定要记住：

Linux 链表所谓的“初始化”，其实就是建立一个只有 HEAD 自己的环。

不是：

next = NULLprev = NULL

而是：

next = selfprev = self

五、宿主结构：让链表真正“装”数据

5.1 什么是宿主结构？

来看：

struct my_data {    int value;    char name[32];struct list_head list;};

这里真正的数据对象是：

struct my_data

它就可以称为：

宿主结构。

而：

struct list_head list;

只是宿主里面负责建立链表关系的成员。

假设：

struct my_data *obj;

那么插入链表不是：

list_add(obj, &head);

因为：

list_add()

根本不认识：

struct my_data

而应该：

list_add(&obj->list, &head);

也就是说：

进入链表世界以后，业务对象暂时“退化”为它里面的 list_head 成员。

5.2 链表里面实际连起来的是什么？

假设存在：

struct my_data A;struct my_data B;struct my_data C;

传统直觉可能认为：

A ↔ B ↔ C

实际上应该看成：

┌──────── A ────────┐│ value             ││ name              ││ [list_A]          │└───────┬───────────┘        │        ▼┌──────── B ────────┐│ value             ││ name              ││ [list_B]          │└───────┬───────────┘        │        ▼┌──────── C ────────┐│ value             ││ name              ││ [list_C]          │└───────────────────┘

准确来说：

HEAD ↔ list_A ↔ list_B ↔ list_C ↔ HEAD

而不是：

HEAD ↔ A ↔ B ↔ C

这是理解后续 container_of() 的基础。

5.3 一个结构体为什么可以加入多个链表？

例如：

struct my_task {    int pid;struct list_head global_list;struct list_head ready_list;};

那么：

list_add(&task->global_list, &all_tasks);

表示：

把 task 以 global_list 身份挂入 all_tasks

又可以：

list_add(&task->ready_list, &ready_tasks);

表示：

把同一个 task 以 ready_list 身份挂入另外一张链表

于是同一个对象就能同时存在于：

关系 A+关系 B

中。

这一点对于理解 Linux 内核复杂对象尤其重要。

六、核心操作接口全解析

6.1 list_add()：头插

典型代码：

list_add(&new->list, &head);

语义是：

把 new 插入到 head 后面。

如果原来：

HEAD ↔ A ↔ B ↔ HEAD

执行：

list_add(&N->list, &head);

以后：

HEAD ↔ N ↔ A ↔ B ↔ HEAD

所以如果不断：

list_add()

新来的元素总是在最前面。

效果非常像：

栈。

Linux 官方链表 API 也把 list_add() 描述为适合实现栈式插入的操作。

6.2 __list_add() 到底在干什么？

假设现在：

prev ↔ next

想把：

new

插到中间。

最后必须变成：

prev ↔ new ↔ next

本质只需要修正四条关系：

new.next = nextnew.prev = prevprev.next = newnext.prev = new

画出来：

插入前：

prev ───────→ nextprev ←─────── next

插入后：

prev ←→ new ←→ next

因此内核内部的：

__list_add()

本质做的就是：

把一个新节点接到已知的 prev 和 next 中间。

外层：

list_add()

只不过告诉它：

prev = headnext = head->next

而：

list_add_tail()

则告诉它：

prev = head->prevnext = head

这就是为什么内核会把真正底层的“连接动作”和外层的“插入位置语义”分开。当前 list.h 源码也保留了这种内部辅助函数加外层接口的结构。

6.3 list_add_tail()：尾插

假设：

HEAD ↔ A ↔ B ↔ HEAD

执行：

list_add_tail(&N->list, &head);

那么：

HEAD ↔ A ↔ B ↔ N ↔ HEAD

所以：

list_add

像：

push front

而：

list_add_tail

像：

push back

如果配合：

从头取元素+从尾部加入

就很容易构建队列语义。

Linux 官方 API 同样把 list_add_tail() 定义成插入到链表头之前，也就是逻辑尾部。

6.4 list_del()：删除节点

假设：

A ↔ B ↔ C

现在要删除：

B

只需要让：

A.next = CC.prev = A

于是：

A ↔ C

B 就被摘掉了。

你会发现：

删除 B 根本不需要从 HEAD 开始遍历。

因为 B 自己已经保存着：

B.prevB.next

所以删除操作能够直接知道：

前驱是谁后继是谁

因此可以做到：

O(1)

6.5 list_del() 以后节点是什么状态？

这个问题特别容易被忽略。

当前内核中的：

list_del()

完成摘链以后，会把被删除节点的两个链接设置成用于调试的 poison 值；源码注释明确说明，之后不能把这个节点简单理解成“已经重新成为一个空链表”。

也就是说：

list_del(&obj->list);

以后不要理所当然地认为：

list_empty(&obj->list)

就是判断它有没有被删除的正确办法。

如果这个节点后面还希望重新作为一个干净链表节点使用，更适合：

list_del_init(&obj->list);

6.6 list_del_init()

它做两件事情：

第一步：把节点从原链表删除第二步：重新 INIT_LIST_HEAD()

也就是：

entry.next = entryentry.prev = entry

当前内核源码中的 list_del_init() 正是：

删除+重新初始化

这两个动作的组合。

于是节点摘掉以后：

   ┌──────────────┐   ↓              │ [ entry ] ───────┘

重新处于一个自环状态。

6.7 list_move() 与 list_move_tail()

有时候我们不是想删除一个节点。

而是：

把它从一个位置移动到另外一个链表。

例如：

list_move(&obj->list, &new_head);

本质可以理解为：

先从原位置摘掉↓再插入 new_head 后面

而：

list_move_tail()

则是：

先摘掉↓再插入目标链表尾部

当前 list.h 源码也正是组合已有底层删除和添加逻辑完成这两个操作。

这其实又体现了 Linux 内核代码一个很值得学习的思路：

底层原语足够简单，上层复杂操作通过组合完成。

6.8 list_replace() 与 list_replace_init()

假设：

A ↔ OLD ↔ B

我们想让：

NEW

直接占据 OLD 的位置：

A ↔ NEW ↔ B

可以：

list_replace(&old->list, &new->list);

而：

list_replace_init()

除了完成替换，还会把 OLD 节点重新初始化。当前源码就是在替换之后对旧节点执行初始化。

6.9 list_empty()

空链表：

head.next == head

因此：

if (list_empty(&head))    ...

的核心判断非常简单。

当前实现读取 head->next 后判断是否回到 head 自身。

这里再次体现了循环链表的优势：

HEAD 自己就能够承担结束标志，不需要额外 NULL。

6.10 list_is_last()

判断：

某个节点是不是最后一个数据节点

本质只需要看：

node.next == head

因为双向循环链表的最后一个节点后面就是 HEAD。

当前 list_is_last() 的判断逻辑也正是如此。

6.11 list_is_singular()

如果一个链表只有一个真正的数据节点：

       ┌───────────────┐       ↓               │HEAD ↔ A ──────────────┘

那么：

head.next

和：

head.prev

都会指向：

A

因此：

head.next == head.prev

但是空链表同样：

head.next == head.prev == head

所以还必须先保证：

链表不是空的

当前 list_is_singular() 正是按照：

非空+next == prev

判断只有一个节点。

七、遍历与数据获取：从节点到数据的桥梁

到了这里，最关键的问题终于来了。

假设：

struct my_data {    int id;    char name[32];struct list_head list;};

链表里面连接的是：

&obj->list

可是我们真正想访问的是：

obj->idobj->name

那么：

已经拿到 struct list_head \* 以后，怎样重新找到外面的 struct my_data \*？

答案就是：

offsetof+container_of

7.1 先搞懂结构体成员偏移

假设：

struct my_data {    int id;    char name[32];struct list_head list;};

内存布局可以想象成：

struct my_data 起始地址0x1000  │  ▼┌──────────────────────────┐│ id                       │├──────────────────────────┤│ name                     │├──────────────────────────┤│ list                     │ ← 假设地址 0x1028│   next                   ││   prev                   │└──────────────────────────┘

假设：

list 成员相对于结构体首地址的偏移 = 0x28

那么：

结构体地址 + 0x28 = list 地址

反过来：

list 地址 - 0x28 = 结构体地址

是不是瞬间就明白了？

这就是 container_of() 最核心的数学思想。

7.2 offsetof(TYPE, MEMBER)

offsetof() 做的事情就是：

计算某个成员相对于结构体起始位置的字节偏移。

例如：

offsetof(struct my_data, list)

得到：

list 离 struct my_data 起始地址多远

假设结果：

40 bytes

那就意味着：

my_data 首地址 + 40=list 地址

7.3 container_of() 的本质

我们已经知道：

member_address

也知道：

offset

那么：

container_address=member_address - offset

因此可以把 container_of() 的核心思想简化理解成：

container =    (char *)member_ptr    - offsetof(container_type, member);

然后再转换回：

container_type *

Linux 官方驱动模型文档对 container_of() 的解释正是：根据成员地址减去通过 offsetof() 得到的成员偏移，从而得到包含它的外围结构地址。

7.4 用具体地址算一次

假设：

struct my_data 首地址 = 0x1000

其中：

list 偏移 = 0x28

所以：

&obj->list = 0x1028

现在遍历链表以后，我们只拿到了：

ptr = 0x1028

执行：

container_of(ptr, struct my_data, list)

内部逻辑：

0x1028-0x28=0x1000

于是：

0x1000

就是：

struct my_data *

所以 container_of() 并不是什么神秘魔法。

它本质就是：

已知成员地址 + 已知成员在结构体中的位置，倒推出整个结构体的位置。

7.5 当前内核中的 container_of() 还有一个细节

当前主线内核已经提供：

container_of_const()

用于保留传入指针的 const 属性；当前 container_of() 的源码注释也明确提示，新代码在需要保持 const-correctness 的情况下应优先考虑 const-preserving 版本。

不过对于理解 Linux 链表来说，最重要的仍然是刚才这个公式：

宿主地址=成员地址-成员偏移

因为：

list_entry()

就是建立在这一思想上的。

7.6 list_entry()：从节点找到数据

Linux 提供：

list_entry(ptr, type, member)

例如：

struct my_data *obj;obj = list_entry(node,                 struct my_data,                 list);

三个参数：

node↓当前 list_head 指针struct my_data↓宿主类型list↓list_head 在宿主中的成员名

其本质就是：

container_of()

的链表封装。Linux 官方链表文档同样明确说明，list_entry() 内部通过 container_of() 从 list_head 节点得到宿主数据结构。

7.7 list_for_each()：遍历最原始的节点

最基础的遍历方式：

struct list_head *pos;list_for_each(pos, &head) {    ...}

这里：

pos

的类型仍然只是：

struct list_head *

所以如果想访问数据：

struct my_data *entry;entry = list_entry(pos,                   struct my_data,                   list);

然后：

pr_info("%d\n", entry->id);

整个过程就是：

HEAD↓拿到 list_head↓list_entry()↓container_of()↓得到 struct my_data↓访问业务字段

7.8 list_for_each_entry()：直接遍历宿主对象

如果每一次都：

list_for_each(...){    entry = list_entry(...);}

显然有点麻烦。

所以内核提供：

list_for_each_entry(pos, head, member)

例如：

struct my_data *pos;list_for_each_entry(pos, &head, list) {    pr_info("id = %d\n", pos->id);}

现在：

pos

已经不再是：

struct list_head *

而是：

struct my_data *

这就是为什么第一次看到这个宏的时候非常神奇：

list_for_each_entry(pos, &head, list)

好像链表突然知道数据类型了。

其实它并没有真正“知道”。

关键在于：

typeof(*pos)+member+list_entry()+container_of()

帮助它完成了类型转换。

Linux 官方链表文档也专门说明，list_for_each_entry() 的存在就是为了避免用户在遍历 list_head 后手动反复调用 list_entry()。

7.9 为什么遍历删除不能直接使用普通版本？

来看：

struct my_data *pos;list_for_each_entry(pos, &head, list) {    list_del(&pos->list);    kfree(pos);}

看起来好像非常合理：

遍历一个↓删除一个↓释放一个

问题出在哪里？

遍历宏下一轮需要知道：

当前节点的 next

可是你已经：

kfree(pos);

了。

也就是说：

下一轮准备访问 pos->list.next

的时候，pos 指向的内存可能已经失效。

这就可能产生：

Use-After-Free链表损坏崩溃不可预测行为

7.10 list_for_each_entry_safe() 为什么安全？

正确写法：

struct my_data *pos;struct my_data *tmp;list_for_each_entry_safe(pos, tmp, &head, list) {    list_del(&pos->list);    kfree(pos);}

为什么多了一个：

tmp

就安全了？

因为 _safe 版本在进入当前循环体之前，已经提前保存：

下一个节点

简化理解：

pos = 当前节点tmp = 下一个节点↓ 执行循环体删除 pos释放 pos↓ 下一轮pos = tmp

因此：

即使当前 pos 已经被释放

下一轮也不用再访问它才能找到后继。

当前 list_for_each_entry_safe() 宏的实现确实会提前保存下一项，然后再执行循环体，从而支持当前节点在遍历过程中被移除。

这也是 _safe 的真正含义：

safe against removal of current list entry。

需要特别注意：

这里的 safe 并不等于线程安全。

它不是说：

多个 CPU 可以不加锁随便同时改链表

而是说：

当前遍历过程中删除当前节点不会破坏遍历推进所需的信息。

这两个“安全”完全不是一回事。

八、哈希链表 hlist：为散列表而生的优化结构

8.1 为什么已经有 list_head，还需要 hlist？

假设我们实现一个哈希表：

bucket[0]bucket[1]bucket[2]...bucket[65535]

每一个 bucket 后面挂一条链。

如果每一个 bucket 都使用：

struct list_head

那么每一个 bucket 头里面都有：

next+prev

两个指针。

在 64 位系统中，一个指针通常 8 字节。

那么仅仅链表头就需要：

16 字节

如果 bucket 数量特别大：

16 × 65536

就是一笔完全可以注意到的空间开销。

可是哈希 bucket 的头节点真的需要：

prev

吗？

很多时候我们只需要知道：

第一个节点是谁

所以 Linux 设计了：

struct hlist_head {struct hlist_node *first;};

也就是：

bucket head只有一个 first 指针

当前 list.h 注释也直接说明，hlist 是“单指针链表头”的双链形式，主要用于哈希表等场景，因为普通双指针 list head 在大量 bucket 下会比较浪费。

8.2 千万不要误解“节省一半空间”

很多文章会直接写：

hlist 比 list_head 节省一半内存。

这个说法不够准确。

真正节省明显的是：

链表头。

普通：

struct list_head

头节点：

nextprev

两个指针。

而：

struct hlist_head

只有：

first

一个指针。

但是 hlist 的数据节点：

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

仍然是两个指针。

所以真正的优化点是：

海量 bucket×每一个 bucket 头少一个指针

而不是：

所有节点都只剩一个指针。

8.3 hlist_node 为什么有一个奇怪的 **pprev？

结构：

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

最难理解的就是：

**pprev

为什么不是：

struct hlist_node *prev;

这正是 hlist 最精妙的地方。

8.4 先看普通双链表怎么删除

普通：

A ↔ B ↔ C

删除 B：

A.next = CC.prev = A

所以需要：

B.prev

找到 A。

8.5 hlist 想解决的问题

hlist 的第一个节点前面并不是：

struct hlist_node

而是：

struct hlist_head

例如：

hlist_head.first       │       ▼       A → B → C → NULL

如果 A 里面使用普通：

struct hlist_node *prev;

那么：

A 的前驱是谁？

很尴尬。

因为 A 前面的东西不是：

hlist_node

而是：

hlist_head.first

所以 Linux 换了一个思维：

我不保存“前一个节点是谁”，而是保存“哪个指针正在指向我”。

这就是：

pprev

8.6 pprev 到底指向什么？

假设：

head.first → A → B → C

那么 A：

A.pprev

不是指向：

head

而是指向：

&head.first

也就是说：

A.pprev↓指向那个“存放 A 地址的指针变量”

而 B：

B.pprev

则指向：

&A.next

C：

C.pprev

指向：

&B.next

整体：

head.first ─────────→ A   ↑ A.pprevA.next ─────────────→ B   ↑ B.pprevB.next ─────────────→ C   ↑ C.pprev

看到这里就能够理解为什么需要：

struct hlist_node **

了。

因为它保存的是：

一个“指针变量本身”的地址。

8.7 pprev 为什么能让删除保持 O(1)？

假设删除 B。

我们知道：

B.pprev = &A.nextB.next  = C

那么只需要：

*(B.pprev) = B.next

就等价于：

A.next = C

然后：

C.pprev = B.pprev

也就是：

C.pprev = &A.next

删除完成：

head.first → A → C

根本不用：

从 head 开始找 B 的前驱

所以 pprev 的精髓就是：

不保存前驱节点，而保存能够修改“前驱到我”这条链接的地址。

当前内核的 hlist 添加和删除逻辑正是围绕这种“指向前向链接本身”的设计展开，例如头节点插入时第一个元素的 pprev 会关联到 head->first，后续节点则关联到前一节点的 next。

8.8 hlist_add_head()

典型使用：

hlist_add_head(&obj->node, &bucket[index]);

简化理解：

原来：

HEAD → A → B

加入 N：

HEAD → N → A → B

同时需要维护：

N.pprev     = &HEAD.firstA.pprev     = &N.next

所以 hlist 虽然看起来不像传统双向链表，但是依然能够高效删除任意已知节点。

8.9 hlist_del()

因为节点本身拥有：

nextpprev

所以删除依旧可以：

O(1)

完成。

并不需要从哈希 bucket 的：

first

开始重新搜索。

8.10 hlist_for_each_entry()

和普通 list 一样，hlist 节点通常同样嵌入业务结构：

struct my_hash_obj {    int key;struct hlist_node node;};

遍历时可以：

struct my_hash_obj *pos;hlist_for_each_entry(pos, &bucket[index], node) {    ...}

核心思想没有改变：

hlist_node↓container_of↓宿主对象

所以理解了：

list_entry()

以后再看：

hlist_entry()

就非常自然了。

8.11 list_head vs hlist：到底怎么选？

可以简单理解为：

普通通用双向循环链表→ list_head大量 bucket 的 hash 链→ hlist

普通 list：

优点：双向循环头尾访问方便API 极其丰富代价：head 需要两个指针

hlist：

优点：head 只需要一个指针适合大量 hash bucket代价：不是普通循环双链表不能像 list_head 那样直接 O(1) 从 head 找尾部接口语义略有不同

当前 list.h 对 hlist 的设计说明也明确指出：这种单指针 head 的设计主要用于 hash table，一项直接代价就是失去了从 head 在 O(1) 时间取得尾部的能力。

8.12 内核中的实际 hlist 使用

当前文件系统结构里面就可以看到大量 hlist。

例如 inode 中存在：

i_hashi_dentry

等 hlist 相关成员。

当前 dentry 结构也包含：

hlist_nodehlist_head

等成员，用于不同的目录项关系。

网络 socket 相关代码同样大量采用 hlist 管理哈希关系。

这正符合 hlist 的设计目的：

海量哈希桶 + 快速插入删除。

九、源码深读：list.h 中的精妙设计

9.1 为什么大量使用 static inline？

打开：

include/linux/list.h

你会发现大量操作都是：

static inline

形式。

例如：

INIT_LIST_HEADlist_del_initlist_movelist_empty……

当前主线源码确实大量采用这种实现方式。

为什么？

因为链表基本操作通常非常短。

例如删除的核心，无非就是：

修改几个指针

如果这种操作每次都必须进行一次普通函数：

call↓保存现场↓跳转↓return

调用成本有可能显得不划算。

而 inline 给编译器提供了直接展开这些小操作的机会。

当然要注意：

inline 是给编译器的优化提示和语义工具之一，并不意味着编译器在任何情况下都绝对必须展开。

从内核 list.h 的实现风格来看，把这些极小的通用操作写成内联函数，可以同时获得：

类似函数的类型检查+头文件通用实现+编译器内联优化机会

9.2 宏和 inline 为什么混合存在？

你会发现：

list_add()

很多底层操作适合写成内联函数。

但是：

list_for_each_entry()

这类遍历工具通常还是宏。

为什么？

因为遍历宏需要使用：

typeof()成员名称 member宿主类型推导

这些编译期能力。

所以：

简单固定类型操作→ static inline需要类型推导、语法展开→ macro

这也是 Linux C 宏编程非常典型的风格。

9.3 INIT_LIST_HEAD() 为什么使用 WRITE_ONCE()？

当前主线实现中：

INIT_LIST_HEAD()

写 next 和 prev 的时候使用了：

WRITE_ONCE()

很多文章会直接解释：

WRITE_ONCE 保证多核内存可见性。

这个说法过于简单，甚至容易误导。

更加准确地说：

WRITE_ONCE() 的重要作用之一，是约束编译器对共享访问进行某些危险变换，例如访问撕裂、合并或者凭空制造额外访问等；Linux 内核内存模型文档明确建议，共享变量存在多 CPU 访问时，应根据同步设计采用 READ_ONCE()、WRITE_ONCE() 或更强的原语。

但是：

WRITE_ONCE() 本身不能简单等同于完整的 SMP 内存屏障。

如果你真正需要建立：

其他写操作↓必须先于这个写被另外一个 CPU 观察

这种顺序关系，通常需要：

smp_store_release()smp_load_acquire()smp_mb()锁RCU

等相匹配的同步语义。Linux 官方内存模型文档也把普通标记访问与 acquire/release、完整内存屏障明确区分开来。

所以这一点一定要记住：

WRITE_ONCE≠锁WRITE_ONCE≠万能内存屏障WRITE_ONCE≠自动解决链表并发安全

9.4 链表插入为什么是 O(1)？

例如：

list_add(new, head);

已经知道：

插入位置 = head 与 head->next 之间

所以只需要修改固定数量的指针。

节点数无论是：

1010001000000

操作步骤数量都不会随着链表长度增长。

因此：

O(1)

9.5 删除为什么也是 O(1)？

如果已经拿到了：

struct list_head *entry

那么：

entry->preventry->next

已经直接告诉我们：

前一个节点后一个节点

所以摘链仍然只修改固定数量的链接。

因此：

O(1)

但是注意：

如果问题变成：

“帮我找到 id == 100 的节点，然后删除。”

那么首先：

查找

就需要遍历。

所以整体可能是：

搜索 O(n)+删除 O(1)

9.6 遍历为什么是 O(n)？

链表不像数组：

array[100]

可以通过：

首地址 + 下标 × 元素大小

直接定位。

链表要找第 100 个节点，只能：

1↓2↓3↓……↓100

所以遍历：

O(n)

这也是链表的一个明显缺点。

9.7 链表的缓存局部性为什么不好？

这也是实际性能中容易被忽略的地方。

数组通常：

A B C D E

连续存放。

CPU 读取 A 的时候，缓存行可能顺便把：

B C D

也带进 Cache。

链表则可能：

A 在 0x1000B 在 0x8f2100C 在 0x320000D 在 0xff1000

节点散落在不同内存位置。

于是遍历：

读 A↓追 next 指针↓可能发生 cache miss↓读 B↓再追指针

所以即便两个算法理论复杂度都是：

O(n)

实际 CPU 表现也可能非常不一样。

Linux 官方链表文档因此特别提醒，由于数据局部性较差，性能敏感场景不要想当然地认为链表永远合适。

十、并发安全：多核时代的链表保护

10.1 list_add() 自己会不会加锁？

不会。

这个问题非常关键。

调用：

list_add()

并不意味着：

Linux 自动帮你处理好多 CPU 同时操作的问题

标准链表 API 主要负责：

修改链接关系

而：

谁负责同步

通常由调用者根据实际上下文决定。

类似的内核队列接口文档中也会明确指出，某些底层链表/队列操作本身不取得锁，需要调用者持有正确同步。

10.2 并发插入为什么可能把链表搞坏？

假设原来：

HEAD ↔ A

CPU0 想插入：

B

CPU1 同时插入：

C

两边都读取：

head->next = A

CPU0 开始建立：

HEAD ↔ B ↔ A

CPU1 又同时建立：

HEAD ↔ C ↔ A

如果这些指针写操作互相交错：

head.nextA.prevB.nextC.next

最终就可能出现：

next 链和 prev 链互相不一致

甚至某个节点彻底丢失。

所以：

链表结构正确，不代表并发访问自动正确。

10.3 用 spinlock 保护链表

典型写法：

static LIST_HEAD(my_list);static DEFINE_SPINLOCK(my_lock);

插入：

spin_lock(&my_lock);list_add(&obj->list, &my_list);spin_unlock(&my_lock);

删除：

spin_lock(&my_lock);list_del(&obj->list);spin_unlock(&my_lock);

遍历如果要求看到稳定结构，同样需要处于正确同步保护之下。

至于是不是：

spin_lock()

还是：

spin_lock_irqsave()

或者 mutex，则要根据：

访问链表的执行上下文能不能睡眠IRQ 是否参与临界区长度

来决定。

10.4 RCU：读多写少链表的重要方案

如果一个链表：

读非常频繁写非常少

那么所有 reader 每次都争抢同一把全局锁可能会影响扩展性。

RCU 就非常适合某些这样的场景。

例如读侧：

rcu_read_lock();list_for_each_entry_rcu(pos, &head, list) {    ...}rcu_read_unlock();

写侧则使用对应：

list_add_rcu()list_del_rcu()

等接口，并正确处理对象生命周期以及 grace period。

Linux 官方 RCU 文档明确指出，保护 read-mostly 的 struct list_head 链表是 RCU 最典型的使用场景之一。

10.5 RCU 并不是“把 _rcu 后缀加上去就完事”

这是必须强调的一点。

例如删除：

list_del_rcu(&obj->list);kfree(obj);

如果 reader 还可能拿着：

obj

那么马上：

kfree()

就可能导致：

reader 访问已释放内存

RCU 真正的核心之一就是：

先把对象从可发现结构中移除↓允许旧 reader 结束↓经过 grace period↓最后再真正回收

官方 RCU 链表文档中也专门展示了这种“并发遍历 + 延迟销毁”的模式。

所以：

RCU 解决的不仅仅是链表指针怎么改，更重要的是并发对象生命周期怎么管理。

10.6 llist：真正专门设计的无锁单链表

Linux 里面还有：

llist

它不是普通：

list_head

去掉锁以后得到的东西。

而是一套专门设计的：

lock-less NULL terminated singly linked list。

当前 include/linux/llist.h 就明确把它定义为 lock-less 的 NULL 结尾单链表，并说明哪些 producer/consumer 组合能够不加锁使用，哪些情况仍然需要外部同步。

所以：

list_headRCU listllist

并不是三个可以随便互换名字的东西。

它们面向的并发模型不同。

十一、实战演练：在内核模块中使用链表

下面通过一个完整的内核模块，把前面的内容全部串起来。

目标：

1. 创建链表头2. 动态申请 5 个节点3. 插入链表4. 遍历打印5. 安全删除6. 释放内存

11.1 定义宿主结构

struct my_node {    int id;    int value;struct list_head list;};

这里：

idvalue

是真正业务数据。

而：

list

只是负责：

把 my_node 挂入链表

11.2 完整示例代码

#include <linux/init.h>#include <linux/kernel.h>#include <linux/list.h>#include <linux/module.h>#include <linux/slab.h>struct my_node {    int id;    int value;struct list_head list;};static LIST_HEAD(my_list);static int __init list_demo_init(void){struct my_node *node;struct my_node *pos;    int i;    pr_info("list_demo: init\n");    for (i = 0; i < 5; i++) {        node = kmalloc(sizeof(*node), GFP_KERNEL);        if (!node)            goto error;        node->id = i;        node->value = i * 10;        INIT_LIST_HEAD(&node->list);        list_add_tail(&node->list, &my_list);    }    pr_info("list_demo: traverse\n");    list_for_each_entry(pos, &my_list, list) {        pr_info("id=%d value=%d\n",                pos->id, pos->value);    }    return 0;error:    {struct my_node *tmp;        list_for_each_entry_safe(pos, tmp, &my_list, list) {            list_del(&pos->list);            kfree(pos);        }    }    return -ENOMEM;}static void __exit list_demo_exit(void){struct my_node *pos;struct my_node *tmp;    pr_info("list_demo: exit\n");    list_for_each_entry_safe(pos, tmp, &my_list, list) {        pr_info("delete id=%d\n", pos->id);        list_del(&pos->list);        kfree(pos);    }}module_init(list_demo_init);module_exit(list_demo_exit);MODULE_LICENSE("GPL");MODULE_AUTHOR("example");MODULE_DESCRIPTION("Linux kernel list demo");

这段代码就是一个比较完整的：

创建↓插入↓遍历↓删除↓释放

过程。

11.3 为什么节点动态申请以后还初始化 list？

这里：

INIT_LIST_HEAD(&node->list);

对于马上会被 list_add_tail() 正确挂入链表的普通新节点来说，在很多简单场景中并不是插入算法能够工作的绝对前提，因为插入操作会重新写入它的 next/prev。

但是显式初始化有一个好处：

节点在加入任何链表之前已经处于一个清晰、合法的自环状态

如果节点后续还会：

检查是否已独立删除后复用走不同错误分支

良好的初始化习惯可以让状态更容易理解。

具体项目仍然应该遵循对应对象生命周期和 API 约定。

11.4 为什么使用 list_add_tail()？

循环：

for (i = 0; i < 5; i++)

按照：

01234

创建。

如果使用：

list_add_tail()

最后链表顺序：

0 → 1 → 2 → 3 → 4

如果改成：

list_add()

则每次都插到最前面：

4 → 3 → 2 → 1 → 0

这就是：

头插vs尾插

最直观的区别。

11.5 为什么遍历直接得到 struct my_node *？

因为：

list_for_each_entry(pos, &my_list, list)

已经帮我们完成：

list_head↓list_entry↓container_of↓struct my_node

所以循环体里面能够直接：

pos->idpos->value

而不需要自己手动做转换。Linux 官方链表文档同样推荐使用这类 typed traversal 宏直接遍历宿主对象。

11.6 为什么退出时一定使用 _safe？

因为：

list_for_each_entry_safe(pos, tmp, &my_list, list)

提前保存了：

下一节点

所以当前：

pos

即使执行：

list_del(&pos->list);kfree(pos);

也不会影响循环继续推进。当前宏实现就是通过一个额外临时变量保存下一宿主节点完成这一点。

十二、常见错误与避坑指南

12.1 错误一：把同一个 list_head 同时挂到两张链表

假设：

struct my_node {struct list_head list;};

然后：

list_add(&obj->list, &list_A);list_add(&obj->list, &list_B);

这是错误思路。

一个具体：

list_head

里面只有：

nextprev

这一套链接。

第二次挂载会覆盖第一次的链关系。

如果一个对象需要同时加入两张链表，应该：

struct my_node {struct list_head list_A;struct list_head list_B;};

然后：

list_add(&obj->list_A, &head_A);list_add(&obj->list_B, &head_B);

12.2 错误二：遍历删除却不用 _safe

错误：

list_for_each_entry(pos, &head, list) {    list_del(&pos->list);    kfree(pos);}

正确：

list_for_each_entry_safe(pos, tmp, &head, list) {    list_del(&pos->list);    kfree(pos);}

因为后者提前保存了下一节点。

12.3 错误三：只 list_del()，忘记释放宿主对象

list_del(&obj->list);

只做了：

从链表摘除

并没有：

kfree(obj)

链表节点嵌在：

struct my_node

里面。

真正动态申请的是整个：

my_node

所以如果对象生命周期已经结束：

list_del(&obj->list);kfree(obj);

才是：

摘链+释放对象

12.4 错误四：删除以后又直接把节点当成已初始化状态

当前：

list_del()

之后节点会进入不应继续当普通链表节点使用的状态，调试实现还会写入 poison 指针。

如果希望：

摘掉以后保持初始化状态

使用：

list_del_init()

更加符合语义。

12.5 错误五：并发操作不加任何同步

CPU0:list_add()CPU1:list_del()

如果直接同时修改：

nextprev

很容易破坏整个链表结构。

所以必须根据场景设计：

spinlockmutexRCU或者专门的 lockless 数据结构

不能因为：

WRITE_ONCE()

出现在部分链表实现里面，就误认为整个链表 API 已经自动线程安全。

12.6 错误六：把 _safe 理解成并发安全

再次强调：

list_for_each_entry_safe()

的：

safe

主要指：

当前遍历中删除当前元素时，仍然能够正确得到下一元素。

并不意味着：

多个 CPU 可以同时修改链表

如果有并发：

锁还是锁RCU 还是 RCU同步机制还是要正确设计

十三、内核链表在 Linux 中的典型应用

13.1 进程管理

Linux 当前的进程对象：

struct task_struct

中存在：

list_headhlist_node

等多种链接成员。

Linux 官方 RCU 链表文档还给出了一个非常经典的例子：

task_struct::tasks

用于把系统任务串入进程链关系中，并展示了：

for_each_process()

如何结合 RCU 遍历任务。

这就是侵入式链表最大的优势：

task_struct

并不是：

“一个专门为了链表而创建的节点”

它是完整的进程描述对象，只不过内部某些成员让它参与不同的数据结构关系。

需要注意的是：

不要简单地把“Linux 调度运行队列”整体描述为普通 list_head。

现代 Linux 各调度类内部的数据结构并不统一，不能因为 task_struct 使用大量链式结构，就推出“调度器所有 runnable task 都是一张普通链表”。

这也是阅读内核源码时非常重要的一种习惯：

区分“某个对象拥有链表成员”和“整个子系统核心算法使用链表”这两个概念。

13.2 文件系统中的 inode 与 dentry

当前：

struct inode

里面可以看到：

hlist_node i_hashlist_head i_io_listlist_head i_lrulist_head i_sb_list……

等成员。

也就是说：

同一个 inode 对象可以同时参与不同的数据组织关系。

这就是前面说的：

一个宿主+多个链表节点

最真实的内核案例。

当前 dentry 结构同样包含：

d_lrud_sibd_childrend_alias

等 list/hlist 形式的链接成员，用于不同目录项关系。

13.3 设备驱动模型

Linux 驱动模型大量使用：

kobjectksetdevicedriverbus

等对象。

官方 kobject 文档明确提到：

kset

会使用标准内核链表维护其对象关系。

而这些对象又大量采用：

结构体嵌入+container_of()

完成“通用核心对象”和“具体驱动对象”之间的转换。

所以掌握内核链表以后，再学习设备模型时，你会发现两者背后的设计哲学非常相似。

13.4 内存管理

当前 slab 公共代码中就可以看到：

LIST_HEAD(slab_caches);

用于维护 slab cache 相关集合。

而内存管理子系统本身还存在：

LRU回收memcgwriteback

等大量链式组织关系。

所以：

struct list_head

不仅是“写驱动时顺便用一下的链表”。

而是深入整个 Linux 内核的重要基础工具。

十四、再回头看：Linux 内核链表到底高明在哪里？

学到这里，再重新看：

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

是不是已经完全不一样了？

刚开始看到它时，我们可能会问：

数据在哪里？

现在答案已经非常明确：

数据根本不应该在 list_head 里面。

因为：

list_head

只负责描述：

链表拓扑关系

真正的数据属于：

宿主对象

两者之间通过：

container_of()

进行连接。

最终形成：

                Linux 内核链表                      │          ┌───────────┴───────────┐          │                       │     链表关系层                业务数据层          │                       │   struct list_head          struct my_data          │                       │      next / prev            id / name / ...          │                       │          └───────────┬───────────┘                      │                container_of()

这就是整个内核链表最核心的设计。

十五、一张图彻底理解 Linux 内核链表

假设：

struct student {    int id;    char name[32];struct list_head list;};

三个学生：

Student AStudent BStudent C

真正的内存关系不是：

HEAD → Student A → Student B → Student C

而是：

                    ┌─────────────────────┐                    │                     ↓                 ┌──────┐                 │ HEAD │                 └──┬───┘                    │                    ↓┌────────────────────────────┐│ struct student A           ││                            ││ id                         ││ name                       ││                            ││ ┌──────────────────────┐   ││ │ list_A               │───┼────┐│ │ next / prev          │   │    ││ └──────────────────────┘   │    │└────────────────────────────┘    │                                  ↓┌────────────────────────────┐│ struct student B           ││                            ││ id                         ││ name                       ││                            ││ ┌──────────────────────┐   ││ │ list_B               │───┼────┐│ │ next / prev          │   │    ││ └──────────────────────┘   │    │└────────────────────────────┘    │                                  ↓┌────────────────────────────┐│ struct student C           ││                            ││ id                         ││ name                       ││                            ││ ┌──────────────────────┐   ││ │ list_C               │───┼────────→ HEAD│ │ next / prev          │   ││ └──────────────────────┘   │└────────────────────────────┘

链表真正连接：

HEAD ↕list_A ↕list_B ↕list_C ↕HEAD

如果遍历拿到：

list_B

想访问：

Student B

就通过：

list_B 地址-list 在 struct student 中的偏移=Student B 首地址

也就是：

container_of()

这样整个 Linux 链表体系就彻底闭环了。

十六、总结：内核链表的设计智慧

学习 Linux 内核链表以后，真正值得记住的并不是几十个：

list_xxx()

函数。

那些接口以后忘记了，重新打开：

include/linux/list.h

很快就能够查回来。

真正应该掌握的是它背后的设计思想。

第一：侵入式设计

传统链表：

节点包含数据

Linux：

数据包含节点

所以一句话记住：

节点不存数据，数据存节点。

第二：链表与数据彻底解耦

链表层：

只认识 list_head

业务层：

拥有任意数据结构

所以一套：

list_addlist_dellist_movelist_for_each

能够管理无数不同对象。

第三：container_of() 是整个设计的灵魂之一

Linux 可以从：

成员指针

重新找到：

宿主对象

本质就是：

宿主首地址=成员地址-成员偏移

一旦理解这个公式：

list_entry()list_for_each_entry()kobjectdevice model大量 Linux “对象化”写法

都会容易理解很多。

第四：循环双向链表把边界情况变简单

空链表：

head.next = headhead.prev = head

最后节点：

next = head

第一个节点：

prev = head

HEAD 同时承担：

头尾边界空链表标志遍历终点

这就是哨兵节点设计的价值。

第五：hlist 展示了 Linux 对内存和操作复杂度的权衡

hlist 并不是简单“砍掉 prev”。

而是：

head 只保留 first+节点保存 next+pprev 指向指向自己的那个链接

从而既：

减少大量 hash bucket head 的空间

又保持：

已知节点 O(1) 删除

真正高明的地方就在那个看起来非常奇怪的：

struct hlist_node **pprev;

第六：链表操作 O(1)，不代表链表一定快

插入：

O(1)

删除已知节点：

O(1)

但是：

遍历 O(n)查找 O(n)缓存局部性较差

所以算法复杂度只是性能的一部分。

Linux 官方文档也明确提醒：

链表非常常见，但在很多追求性能的数据组织场景中并不一定是最佳选择。

第七：链表本身不等于并发安全

普通：

list_add()list_del()

解决的是：

链表结构操作

而不是：

多 CPU 同步

真正的并发设计仍然需要：

spinlockmutexRCUllist以及正确的对象生命周期管理

尤其要牢记：

list_for_each_entry_safe()

的 _safe：

是遍历删除安全，不是线程并发安全。

最终，如果只用一段话概括 Linux 内核链表，可以这样理解：

Linux 并没有设计一种“能够保存任何数据”的万能链表节点，而是反过来让任何数据结构都能够嵌入一个统一的 list_head 节点。链表操作只管理节点之间的关系，完全不关心宿主数据类型；需要访问真正数据的时候，再通过 container_of() 根据成员偏移反推出宿主结构体。正是这种侵入式设计，使得 Linux 用一个只有 next、prev 两个指针的极简结构，实现了一套能够被整个内核反复复用的通用链表基础设施。

所以第一次看到：

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

的时候，最应该问的问题并不是：

“为什么它里面没有数据？”

而应该变成：

“这个 list_head 被嵌入在哪个数据对象里面？”

当这个思维真正建立起来以后，你才算真正跨过了：

教科书链表

到：

Linux 内核链表

之间最关键的一道门槛。