侵入式链表：Linux 内核如何管理进程列表
文章摘要
这是一篇 2019 年的老文，最近被重新翻上 HN 首页。文章用 Linux 内核的进程管理作为实例，讲清楚了「侵入式链表」（intrusive linked list）到底是什么、为什么内核开发者偏爱它。
核心区别在于链接节点住在哪里。传统（非侵入式）链表的节点里有两个指针：一个 next 指向下一个节点，一个 data 指向真正的数据对象——节点和数据是两块分开的内存。侵入式链表反过来：链表节点被嵌入到数据对象内部，节点里只有 next（以及双向链表的 prev），没有 data 指针，因为数据就在它周围。
这带来一个显而易见的问题：拿到一个节点指针，怎么找回包含它的那个对象？答案是指针算术——用节点地址减去该成员在结构体中的偏移量。文章解释了 GCC 下把指针转成 void * 再做减法的做法（void 在 GCC 里视作 1 字节，虽然对 void 指针做算术在标准 C 里其实是非法的），但更可移植的写法是用 offsetof 宏。Linux 把这套封装成了大名鼎鼎的 container_of 宏，以及基于它的 list_entry。
为什么值得这么折腾？ 文章给出两条理由：一是内存分配次数减半——传统链表插入一个新对象要分配两次（对象一次、节点一次），侵入式只需一次，意味着可能出错的分配点也少了一半；二是缓存抖动更少——遍历传统链表每一步要解引用两次（先节点后数据），侵入式只需一次。
后半篇转向 Linux 实战。内核的链表定义在 include/linux/list.h，结构叫 struct list_head，是循环双向链表：初始化时 next 和 prev 都指向自己（LIST_HEAD_INIT / INIT_LIST_HEAD）。作者引用了 Rusty Russell 的统计：Linux 正常运行时，遍历只占链表全部操作的 6%，而这 6% 里又有 28% 发生在空链表或只有一个节点的链表上。也就是说，内核用链表主要是为了「装一堆对象」，遍历本来就不频繁，或者链表本来就很短——这正好是链表最合适的场景。
进程管理部分：Linux 内部把进程叫 task，task_struct 里嵌了一个名为 tasks 的 list_head。初始任务 init_task 静态分配并把自己作为头节点；copy_process（fork 的实现）里通过 list_add_tail_rcu 把新任务挂到链表尾部，RCU 版本支持单写者多读者并发。当内核需要对每个进程做操作时（休眠时冻结任务、live patch 时切换内核版本、或者按下 SysRq+E 向所有进程发 SIGTERM），就用 for_each_process 宏遍历——它展开成一个从 init_task 出发、用 next_task 逐个推进的 for 循环，而 next_task 最终又落回 container_of。作者提醒：task 链表并不是内核唯一的进程索引，内核同时维护一个 idr 字典结构提供 O(1) 的 pid 查找，按 pid 找单个进程走的是那条路，而不是遍历链表。
HN 评论精华
讨论质量很高，主要沿三条线展开：技术补充、术语考据之争、语言与生态。
一、被文章低估的两大好处
el_pollo_diablo 贡献了讨论中最有分量的一条补充，指出侵入式结构还有两个文章没强调的优势。其一是同一个对象可以同时挂进多个平行链表而不需要任何间接层——传统做法通常是一个容器拥有数据、其他容器只存非拥有指针。他给了一个内核式的例子：struct thread 里同时放 process_entry（所属进程的线程链表）和 sched_entry（调度队列），从 list_node 指针反推 thread 时，从上下文就知道该按哪个成员的偏移量减。dahart 一开始被这点绕住了，问「既然靠地址算术找 payload，那 payload 不就绑死在唯一一个 next 指针上了吗」，apple1417 用一个含 next / next_10th / next_100th 三个指针的 Node 例子点破：不同成员减不同偏移，自然是三个互不相干的链表，container_of 的 type + member 参数就是干这个的。其二是侵入式结构把元素的分配责任完全交还给使用者——可以在堆上、栈上、全局数组里、专门的 arena 里，甚至混用（比如循环链表的锚点放栈上，其余节点嵌在堆上的 payload 里）。
pclmulqdq 补充了另一个被文章当作旁注带过的关键收益：对象可以在链表之间、链表内部移动而无需拷贝数据，并且只要手上有对象指针，就能 O(1) 从链表中间摘除。abcd_f 把这归结为更本质的一句：增删元素完全不需要堆操作，所有控制元素等于预分配好了。dahart 补充了历史场景——早年主机游戏开发既不允许动态分配也不允许用 STL，内存全部预分配，链表纯靠改指针在运行时组装，和内存管理器的做法如出一辙。
二、「intrusive 是 C++ 黑话」的术语之争
这是评论区最热闹的一支。klps10 开炮说文章在改写历史：「intrusive」是 C++ 的说法，传统的链表一直就是数据和指针混在一个 struct 里的；他还刻薄地补了一句这篇文章「已经被 clanker（指 AI）引用了」。tantalor 附议：学生时代第一次实现链表就是把数据和 next 指针放一起，那是「宝宝的第一个链表」。flohofwoe 的说法是：常规链表在 C++ 出现之前隐含就是侵入式的，是标准库引入了「外挂式」链表。ahgas 指出维基百科给的典型链表例子（一个内嵌整数 + 一个 next 链接）也没人叫它 intrusive。
dahart 做了一次相当有说服力的考据回应：Stroustrup 1985 年的 C++ 书里首次使用「intrusive」这个词，正是因为当时有人开始用 C++ 把节点和 payload 分开分配，他需要一个词来区分新旧两种做法。所以自 1955 年前后起，大多数人心目中的「常规链表」就是侵入式那种，「非侵入式」这个提法本身带有推销意味——推销把节点类型和 payload 解耦的抽象，同时淡化了它的代价。他还说自己整个职业生涯只用过侵入式链表，课堂之外几乎没有理由用非侵入式的：要么用数组，要么用侵入式链表，工程上通常更优。layer8 给出了平衡视角：这取决于你所在的生态——在托管运行时里工作的开发者，默认见到的就是非侵入式链表（而且很多时候连链表都不是，是 Java 的 ArrayList 这类数组）。usrnm 从更古的角度提醒：Lisp 的 cons cell 是数据嵌在里面而不是反过来，而 Lisp 是最古老的语言之一。HarHarVeryFunny 分享了实战：他写过一个被广泛采用的 XML/JSON 库，用侵入式链表连接子元素，性能收益可观，而 DOM API 把这个实现细节完全对用户隐藏了。
三、C 宏 vs C++ 模板
uecker（C 标准委员会背景，多次提到 C2y 提案）认为 C 里用宏生成类型安全的链表并不比 C++ 模板版本更难写或更差，问题只是缺一个标准化的现成实现（除了那套并不理想的老 BSD 宏）。el_pollo_diablo 从实践经验反驳：宏元编程处处是坑（比如成员声明必须写 typeof(payload_type) payload; 而不能直接写类型名，否则别人传数组类型或函数指针类型就炸；数组类型还没法按值传递），他宁可选模板的语义替换而不是宏的文本替换。他认为最大的限制是没有集中的单态化：两个库各自宏生成一份 int 链表，因为 C 的类型系统是名义类型，生成出来的类型同构但不兼容；而 C++ 里两个独立的库可以愉快地共享 std::list<int>。
这引发了 Joker_vD 和 uecker 之间一段非常细致的 C 标准条文辩论，两人反复引用 6.2.7.1 / 6.7.3.4 关于「不同翻译单元中声明的结构体何时兼容」的措辞。结论是：Joker_vD 对标准条文的引用没错，但 uecker 指出了关键前提——兼容规则说的是不同翻译单元；一旦你在同一个 .c 里同时 include 了 lib_a.h 和 lib_b.h，两个头文件又都 include 了同一个泛型链表头并各自定义了 list(int) 的 API，那就不兼容了。真正可行的办法是让宏合成一个依赖于类型的 tag（list_int、list_float），实践中效果不错但不完美。el_pollo_diablo 还补了一刀：标准意义上的「兼容」比「内存布局相同」严格得多——布局相同也不允许把一个类型的指针传给期待另一个类型指针的地方；而且两个成员列表相同的结构体，标准并不保证 size 和 alignment 相同（虽然实践中都相同）。icedchai 打了个圆场：看你说的「兼容」是哪个意思，内存布局一样、能 memcpy，那是另一回事。
四、其他值得一提的
flohofwoe 介绍了 AmigaOS 那个优雅的「重叠链表头」技巧：节点是常规的两指针（succ/pred），但链表头有三个指针，构成两个重叠的 Node 结构。空表时 lh_Head 指向 &lh_Tail、lh_TailPred 指向 &lh_Head，而 lh_Tail 永远是 null 充当结束标记。这样只要有一个节点指针就能前后遍历、插入、删除，遇到 null 就知道到头了——而 Linux 风格的链表必须知道表头地址才能判断遍历结束。layer8 附上了 AmigaOS wiki 的出处佐证。
amelius 抛出经典挑衅：「现在试试用 safe Rust 写一个。」steveklabnik 回应得很干脆：侵入式链表几乎按定义就不太可能在 safe 代码里实现，而且这不是 trait 能解决的问题；至于 safe Rust 的边界会不会随时间扩大，他的回答是「算是吧，但也不尽然」。afdbcreid 甩出 intrusive-collections crate，amelius 反驳说引第三方库不算数，而且不知道它内部是不是 unsafe。cryptonector 从另一个角度切入：真正的难点在于带回指的数据结构（双向链表就是）天生难以做到线程安全的修改。max_k 反问「跟什么比更难？」——改 std::vector 必须上粗粒度锁序列化所有访问，别无选择；链表反而可以粗锁、细锁、原子操作、甚至 RCU 这类花招，选择多得多。
eventualcomp 贡献了当日最佳吐槽：「服务员，再来一篇没有 benchmark 的性能优化文章。」
blt 提出了一个安全角度的观察（并诚实声明自己没有实战经验）：侵入式链表可能是对 C 里 use-after-free 的一层软防御——节点结构自己就知道它属于哪些容器，写「析构」逻辑非常局部化；而用指针数组的等价方案，你必须理解整个周边代码库才能找出哪些数组指向了这个对象。
zahlman 问这类内容是不是已经不在标准 CS 本科课程里了，引出 flohofwoe 的挑衅式回答：「你上一次用链表是什么时候？」——他认为 90 年代末 CPU 和内存延迟差距拉开之后链表就过气了，紧凑数组几乎总是更好。max_k 强烈反对，称「链表过气」是个迷思：他每天都在用，有些东西没有链表几乎无法实现，而这些场景里侵入式的优势是巨大的；一个程序员完全可能整个职业生涯不直接碰链表，然后就想象不出为什么有人要用它——高层框架的平整表面之下，其实一路都是链表。zahlman 补充说，任何需要记住父状态的状态机本质上就是侵入式链表，撤销/重做最直观的实现也是；这些场景里它比显式容器更简单易懂，而常数因子性能根本无关紧要，因为响应的是人类速度的 GUI 交互。