Linux内核数据结构读书笔记：链表、kfifo与红黑树的设计之道

读书这件事，最怕的就是“看完了”和“看懂了”之间隔着一条巨大的鸿沟。我当初第一次翻《Linux内核设计与实现》的内核数据结构这一章时，觉得挺简单——链表不就是指针指来指去，队列不就是先进先出，哈希表不就是数组加链表嘛。可等我真的去读内核源码、去写内核模块、去调试一个莫名其妙的崩溃时，才意识到自己当初有多天真。

这章内容在整本书里篇幅不大，但它藏着一个非常重要的信号：内核里的数据结构，绝对不是把教科书里的东西原封不动搬进来，而是为了性能、并发和可维护性做了大量“反直觉”的定制。如果你只是把这一章当科普翻过去，那跟没读差不多；如果你能顺着这一章的几个关键点，挖出背后的设计动机，再去翻对应的内核源码，那这章的含金量会在你后面的实际开发里持续兑现。

这篇文章，我就以读书笔记的形式，结合我实际读内核源码和写内核模块的经验，把这章里的核心数据结构逐个拆开讲。不光是讲它们是什么，更想聊聊它们为什么被设计成这个样子、用在哪些场景、以及你在读代码和写代码时最容易踩的坑。适合刚接触内核开发的人，也适合那些做用户态开发但对底层数据结构设计感兴趣的朋友。

1. 内核为什么没有直接“复用”现成的数据结构库

在读这一章之前，你可以先停下来问自己一个问题：为什么内核不干脆用一套通用的链表、队列库，非要自己搞一套？毕竟在用户态，C++的STL、Java的集合框架、甚至C语言里各种开源的数据结构库都挺成熟。

1.1 从用户态思维到内核思维的转变

你以前在用户态写业务代码，习惯了“数据是数据，结构是结构”。比如你要管理一批用户，你会定义一个User结构体，然后把它丢进一个List 或者std::vector 里。数据结构和你的业务对象是分离的，容器负责组织，对象负责存储信息。

内核里的思路是反过来的。以内核链表为例，它用的是list_head这个结构体，但你的业务结构体不是“包含”一个链表头，而是把list_head直接“嵌”进你的结构体里面。什么意思？就是说，你的业务结构体里有一个成员是struct list_head，通过这个成员把结构体串起来。

struct list_head { struct list_head *next, *prev; }; struct my_data { int id; char name[32]; struct list_head list; // 链表节点嵌入业务结构体 };

这种设计的第一个好处是：同一个结构体可以同时挂到多个链表上。比如一个网络缓冲区，既可能在“待发送队列”里，也可能在“超时重传队列”里，你只需要在结构体里放两个list_head成员就行。这在用户态用STL就做不到这么干净。

另一个更重要的原因是内核里没有“内存分配自由”这么一说。在用户态你随便new一个节点，不用了delete掉。在内核里，节点往往和一大块连续内存、硬件描述、文件状态绑定在一起，你没办法把数据拷贝进拷贝出，只能通过指针把节点组织起来。嵌入了list_head之后，节点的生命周期和管理结构是解耦的，你完全可以用一个栈上分配的变量挂到全局链表里，再手动摘下来。

1.2 内核数据结构的三个设计原则

这本书的内核数据结构章节实际上在传达三个非常明确的设计原则，你把握住它们，后面读代码会顺畅很多：

• O(1)优先：内核里绝大多数热路径操作都要求常数时间完成。你很少看到内核里出现O(n)的遍历查找作为常规操作，如果有，那一定是被包装在某种特殊场景下（比如只遍历少量节点）。红黑树、哈希表、链表的插入删除都是O(1)或O(log n)，这是硬要求。

• 内存即资源：内核里每个字节都金贵。链表头为了节省空间可以只保留一个指针（hlist就是这种思路，后面细说）；红黑树不额外存父节点，而是通过编码技巧隐式保存；队列不用传统链表而用环形缓冲区，能少一次内存分配就少一次。

• 并发访问是常态：用户态的数据结构在单线程下随便写，内核对数据结构的每一次访问都可能在多CPU之间竞争。所以，数据结构的设计必须为锁、原子操作和无锁编程留出空间。

1.3 这些选择背后的性能账本

你可能觉得，这有什么可讲究的，链表头多一个指针少一个指针能有多大差别？但你要知道，内核里的哈希表，动辄就是几十万个桶，每个桶里是一个hlist头，如果每个头多8个字节（一个指针大小），那么光哈希表的头部就是几百万字节的额外内存。按内核的标准，这种浪费是不可接受的。

同样，链表的插入操作为什么要分list_add和list_add_tail？因为不同场景对遍历顺序、缓存利用的要求不一样。在用户态你可能不在乎顺序，在内核里，一个调度实体加入队列的方向，可能直接影响多核下的缓存亲和性。

所以你看，内核里的每一个“奇怪设计”，背后都是一笔清晰的性能账。你读这一章时，不能只记API，要把API还原成性能决策。

2. 链表：一个“嵌”出来的数据结构帝国

如果你打开内核源码的include/linux/list.h，你会发现这套链表API已经被用得滚瓜烂熟，不夸张地说，它是整个内核数据结构的基石。链表这节，表面上是讲怎么插入删除遍历，实际上真正值钱的地方是两个：一个是“嵌入”思想，另一个是container_of这个宏。

2.1 为什么能在一个节点结构上长出“分身”

你仔细想一下list_head的工作原理。每个节点都有一个next和一个prev指针，指向相邻节点的list_head成员，而不是指向整个结构体的起始地址。这一下就把链表从“对象组织工具”变成了一种“视图机制”。

打个比方，你有一批学生，每个学生不仅在学校花名册里，同时还在篮球队名单里。你不需要为学生单独建两张表，只需要在学生结构体里放两个list_head，花名册的链表把所有学生通过一个头串联起来，篮球队的链表通过另一个头把部分学生串联起来。两个链表互不干扰，节点只有一个副本。

struct student { int id; struct list_head roster; // 花名册链表节点 struct list_head team; // 篮球队链表节点 };

这就是“分身”的含义：同一个内存对象，可以被多个链表同时管理。内核里到处都是这种用法。网络协议栈里一个sock结构体，可能要同时挂在协议哈希表、监听队列、等待队列等多个链表上，少了嵌入式的list_head设计，这根本无法实现。

2.2 遍历、插入、删除的常规操作与注意事项

链表操作本身的API很简单，但有几个细节值得单独拎出来说：

• 遍历删除的安全写法：当你遍历一个链表并准备删除当前节点时，必须先保存下一个节点的指针，否则list_del之后你就找不到下一个节点了。内核为此专门提供了list_for_each_entry_safe宏，它内部帮你缓存了n指针。

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

这个写法是我见过内核初学者最容易写错的。自己手动写list_for_each加list_del时，一旦删除当前节点，遍历就断了，紧接着访问野指针直接崩溃。内核把这种“安全遍历+删除”模式封装进宏，就是为了逼你用正确的写法。

• 空链表判断：用list_empty(&head)判断，返回非零代表空。注意它只检查头节点的next是否指向自己。很多新手喜欢遍历一遍数个数，完全没必要。

• 头节点的位置：链表头通常不是业务节点，只是一个锚点。list_add添加的新节点在头节点之后，list_add_tail添加在头节点之前，也就是说头节点始终像个“哨兵”一样夹在首尾之间。这种设计让所有操作都不需要特殊处理空表的情况，统一了代码路径。

2.3 hlist：哈希表场景下的头节点瘦身

hlist这个结构很多人读这章时会忽略，但它在哈希表场景下非常重要。普通list_head头节点有两个指针（next和prev），而hlist的头节点只有一个first指针。

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

节省那一个指针不是抠门，而是因为哈希表可能有海量的桶，但大多数桶是空的。如果一个空桶还要保存两个指针，那么几百万元素的哈希表光空桶头部开销就非常可观。节省一半头部空间，对哈希表这种“桶多元素稀”的数据结构来说，是实打实的内存收益。

hlist_node里的pprev是“指向前一个节点next指针的指针”，设计成二级指针的原因是为了在删除节点时，不需要区分“是不是头节点”也能统一操作。如果只有一个普通的prev指针，那么删除第一个节点时，你要额外更新桶头的first，逻辑就多了一个分支；用pprev的话，直接*pprev = next就搞定了。

2.4 现实中我用链表踩过的坑

我自己在内核模块里用链表管理设备状态的时候，踩过一个非常典型的坑：没有初始化链表头就调用list_add。

struct my_struct *obj = kmalloc(sizeof(*obj), GFP_KERNEL); // 忘了 INIT_LIST_HEAD(&obj->list); list_add(&obj->list, &global_head);

而内核的list_add内部只是纯粹地接指针，不做任何合法性校验。结果就是，obj->list的next和prev保存着未初始化的垃圾值，一旦list_add把它接入链表，整个链表就被污染了，后面遍历时直接访问到非法地址，系统崩溃。这个问题的排查难度极高，因为崩溃发生在不知道多久之后、不知道多少条指令之外的地方。

从那以后我记住了：挂入链表前，先INIT_LIST_HEAD，这不是可选项，是必选项。还有一次，我把一个已经释放的节点留在了链表里，后续遍历时通过list_entry拿到了野指针，内核直接oops。这个问题的教训是：kfree节点之前一定要先把它从链表里摘掉，顺序不能反过来。

3. 队列与映射：内核里“排队办事”和“翻字典”的正确姿势

链表的“嵌入”思想让你能在业务结构体里自由编织数据关系，但到了队列和映射这里，设计思路又不一样了。内核队列追求的是锁开销最小化、读写效率最大化，内核映射则要解决“给定一个整数ID，快速找到对应对象”这种高频问题。

3.1 kfifo：无锁读取的环形队列

内核里的队列叫kfifo，它不是用链表实现的，而是一个环形缓冲区。为什么要用环形缓冲区？因为队列这种场景，操作永远发生在两头：从一头入队，从另一头出队。如果每个节点都动态分配，入队和出队都牵扯内存分配、释放和链表指针更新，在高频I/O路径上太慢了。

环形缓冲区用一段连续内存配合读写指针实现，入队就是把数据写进缓冲区并移动写指针，出队就是从读指针位置取数据并移动读指针。它有几个优点：

• 分配一次内存，后续所有操作零分配
• 天然支持批量的数据拷贝（memcpy可比一个个搬运节点快多了）
• 单生产者单消费场景下，可以做到无锁

kfifo内部维护了in和out两个无符号整数表示读写位置，并且把队列大小限制为2的幂，这样取模运算就能改成位掩码操作。这是典型的“为了性能愿意在API上做限制”的内核设计风格。

在单生产者单消费者模式下，只要保证写入方只修改in、读取方只修改out，两个指针之间就不存在竞争条件，完全没有锁也能保证正确性。你在驱动里做DMA数据接收、串口环形缓冲，经常能看到这种模式。

3.2 映射的两种实现路径

映射在内核里指的是从唯一整数UID到指针的关联关系。最经典的实现是idr，后来演进成了xarray。我读这章的时候，对idr的理解是：它本质是一个分配ID和管理ID到指针映射的机制，常用于设备节点号、文件描述符这类场景。

idr用基数树（radix tree）实现，这种树按ID的二进制位分层次组织，查找时每一层检查一个位段，跳过的层级和分支远少于普通链表遍历。后来xarray把idr收编，成为一个更通用的稀疏数组管理结构，不仅存指针，还能存标记位、实现RCU-safe的查找。

内核为什么不用一个简单的哈希表做映射？因为ID分配有连续性特征，而且内核经常需要“找到第一个空闲的ID”，哈希表做这个操作非常吃力。树的顺序性让“分配最小可用ID”这个操作变得非常自然。

从代码写法上看，如果你在写驱动时需要为每个设备实例分配一个ID，并且后续要通过这个ID反查设备结构体，那么xarray就是你该用的工具。它比你自己维护哈希表更不容易出错，而且有完善的并发支持。

3.3 从锁与并发角度看队列和映射的安全性

这一章的隐含线索是并发，但对队列和映射的并发要求略有不同。kfifo在单生产者单消费者下无锁，这是建立在两个指针“各自独享”的前提下的；而xarray在多读多写场景下主要依赖RCU（Read-Copy Update）实现读侧无锁。RCU的核心理念是：读操作不直接加锁，而是通过一个宽限期来保证“正在读的读者都结束后，才释放旧数据”。这种机制非常适合读多写少、并且读者不允许睡眠的场景。

你如果自己实现一套映射表，很可能用互斥锁保护所有操作。在内核里这通常被视作“简单但低效”的做法。如果你的映射表在中断上下文或热路径上被频繁读取，一把大锁瞬间就变成性能瓶颈。

4. 红黑树：为什么“近似平衡”比“完全平衡”更吃香

很多人对红黑树的第一印象是“复杂”，第二印象是“不知道有什么用”。这一章里红黑树被浓墨重彩地介绍，因为它是内核里最关键的几个数据结构之一：CFS调度器用它管理可运行任务，epoll用它管理监听的fd，虚拟内存管理用它管理内存区域。

4.1 从二叉搜索树到红黑树的动机

普通二叉搜索树在随机数据下表现不错，但在有序插入的场景下会退化成一条链表，查找就变成了O(n)。AVL树通过严格平衡保证左右子树高度差不超过1，查询性能稳定，但每次插入删除后都要反复旋转，维护成本高。

红黑树放弃了“完全平衡”，只要求最长路径不超过最短路径的两倍。这个松弛带来的收益是：插入和删除时的旋转次数大幅减少，总体性能更好。内核的取舍逻辑很有代表性：它不需要最严格的平衡，只需要能保证查询复杂度稳定在O(log n)的直接结果。

4.2 红黑树的旋转与着色到底在调什么

红黑树有五条性质，核心就是根黑、叶黑、红节点的孩子必黑、任意节点到后代叶节点的路径上黑节点数相同。你记不住这些性质也没关系，关键在于理解这五条性质共同保证了“从根到最远叶子的路径不超过最短路径的两倍”。

插入时，新节点默认涂红，如果它的父节点也是红色，就触发了调整。调整分三种情况：叔节点是红色就变色，叔节点是黑色且当前节点是内侧孩子就旋转加变色，叔节点是黑色且当前节点是外侧孩子就单旋加变色。这些规则看起来复杂，但本质就是在不破坏黑高的前提下尽量少旋转。红黑树的实现代码你可以不手写，但你应该看得懂它每一步在干什么，因为内核里嵌入红黑树节点之后，你需要调用它的插入、删除、查找接口，理解规则能帮你定位使用中的问题。

4.3 红黑树在调度器与文件系统中的实际运用

CFS调度器以虚拟运行时间为键值，把每个可运行任务挂到一棵红黑树上。调度器每次要选下一个运行的任务，就是从这棵树上找“最左”节点（虚拟运行时间最小的任务）。这个操作的复杂度是O(log n)，几万个任务也能快速选出下一个。如果你用链表存任务，每次找最小都要O(n)，在千级任务量上就会暴露明显开销。

epoll在监听大量文件描述符时，也用红黑树管理已经注册的fd。当新事件到来，内核需要快速判断这个fd是否已经被注册过，红黑树的O(log n)查找在这里非常关键。你要是自己写过epoll服务，应该能体会：几十万连接下，如果每次注册都用线性扫描，服务早就卡死了。

4.4 写内核代码时不建议自己造轮子的原因

内核里的红黑树已经封装得很完善，提供了rb_root、rb_node和rb_insert_color、rb_erase等接口，但它的设计仍然要求调用者自己实现比较函数和节点嵌入逻辑。很多人第一次用的时候觉得别扭——为什么不干脆提供一个像用户态那样的map<string, void*>？

原因还是性能和灵活性的折衷：内核红黑树不分配内存，节点就在你的结构体里，这样就避免了树操作中动态分配节点的开销。它不做任何类型假设，也就是说你的键值可以是任意类型，只要你自己写比较函数就行。这给了内核代码极大的自由，代价是调用者有责任保证比较逻辑的正确性。所以我的建议是：你不需要自己实现一棵红黑树，但你一定要会正确使用内核的红黑树接口，并且理解节点嵌入的机制。

5. 实操：用链表管理模拟设备节点

纸上得来终觉浅，这章读完你必须动手写点东西。这里我给出一个极简但完整的内核模块示例，用链表管理一组模拟的设备节点。它会演示初始化、插入、遍历、删除的完整流程，以及最关键的一些注意事项。

5.1 场景定义与代码骨架

假设我们有一个驱动，需要动态管理多个设备实例。每个实例有唯一的id和一个名字。

#include <linux/module.h> #include <linux/kernel.h> #include <linux/slab.h> #include <linux/list.h> #include <linux/err.h> struct my_device { int id; char name[32]; struct list_head list; }; static LIST_HEAD(device_list);

不要小看这个LIST_HEAD(device_list)，它展开后是一个静态定义的链表头，初始化了next和prev都指向自己。所有后续操作都以它为锚点。

5.2 插入、遍历与删除的实现

插入节点时，我们必须先为业务结构体分配内存，再初始化链表节点，最后挂入链表：

static struct my_device *create_device(int id, const char *name) { struct my_device *dev; dev = kzalloc(sizeof(*dev), GFP_KERNEL); if (!dev) return ERR_PTR(-ENOMEM); dev->id = id; snprintf(dev->name, sizeof(dev->name), "%s", name); INIT_LIST_HEAD(&dev->list); return dev; } static void add_device(int id, const char *name) { struct my_device *dev = create_device(id, name); if (IS_ERR(dev)) return; list_add_tail(&dev->list, &device_list); }

遍历时，注意我用的是list_for_each_entry，它通过container_of从链表节点指针自动推导出外层结构体指针：

static void dump_device_list(void) { struct my_device *dev; list_for_each_entry(dev, &device_list, list) { pr_info("device id=%d name=%s\n", dev->id, dev->name); } }

删除节点时，先摘链表再释放内存，顺序不能反：

static void remove_device(int id) { struct my_device *dev, *tmp; list_for_each_entry_safe(dev, tmp, &device_list, list) { if (dev->id == id) { list_del(&dev->list); kfree(dev); return; } } }

5.3 常见编译/运行期问题与排查

这段代码看起来简单，但实际运行中还是有几个高频问题：

• 节点未初始化就插入：如果漏了INIT_LIST_HEAD(&dev->list)，链表指针是垃圾值，list_add_tail会直接写坏链表。复现方式：创建一个模块，插入几百个节点后遍历，大概率崩溃。

• 删除和遍历并发：如果在遍历过程中另一个CPU核心删除了当前节点，你极可能访问到已释放内存。解决思路是使用锁或RCU保护遍历过程。

• 内存泄漏：模块卸载时如果你只销毁链表头而不逐个释放节点，整个链表上的所有节点都泄漏了。我见过不少初学者在exit函数里只做了INIT_LIST_HEAD(&device_list)这种“重置”操作，这等于把链表的根切断了，但节点都还躺在内存里没人管。

• 错误用list_add和list_add_tail：这两个API的方向不同，前者把节点插在头部，后者插在尾部。如果你的业务逻辑依赖先进先出，就必须用list_add_tail，否则顺序就反了。

5.4 模块卸载时的完整清理

卸载模块时，应该逐个摘除节点并释放内存：

static void cleanup_device_list(void) { struct my_device *dev, *tmp; list_for_each_entry_safe(dev, tmp, &device_list, list) { list_del(&dev->list); kfree(dev); } }

这一段代码是内核模块生命周期的标准收尾动作，宁可多写也不能省。

6. 读书过程中容易被忽略的关键细节

这一章的很多知识点一眼看过就没了，但它们其实在源码里反复出现。我把它们集中整理在这里，算是几个“如果不注意就被坑”的彩蛋。

6.1 内核中“头节点”与“业务节点”的区别

链表头本身不代表任何业务数据，它是一个纯粹的锚点。很多内核新手读完这章后动手写代码时，会试图把一个业务数据塞进链表头里，这就把模型搞错了。链表头就是一个struct list_head，它不指向任何业务对象；业务节点必须通过“嵌入”一个list_head成员来挂入链表。

这个区分在使用list_entry时尤其重要——你必须告诉宏“链表成员在外层结构体中的名字”，它才能从成员指针反推出整个结构体的指针。如果嵌套层级深了，还要用container_of逐层提取。

6.2 container_of的魔法与边界

container_of是内核魔法的基础。它的核心思想是利用C语言结构体的内存布局：当你有一个指向结构体成员的指针时，用该指针减去该成员在结构体中的偏移量，就能得到结构体的起始地址。

#define container_of(ptr, type, member) \ ((type *)((char *)(ptr) - offsetof(type, member)))

看起来简单，但它有一个隐含前提：ptr必须确实指向一个type类型对象内部的member成员。如果你把一个无关的指针传进来，得到的地址是随机的，后续访问必然崩溃。内核里许多崩溃案例的根因，都是list_entry用错了成员名，或者传入了错误类型的指针。

6.3 几大数据结构的演进逻辑

读这章时我建议大家顺手做一个对比表，把几个核心数据结构的适用场景记清楚：

这个表不是让你背的，是让你在选型时有据可依。你如果在内核里要设计一个新的管理结构，先对照这个表选一个合适的，再动手写，比自己造一个“万能结构”靠谱得多。

还有一个演进细节容易被忽略：很多老代码里的idr已经被转换成xarray，但API兼容层还在。你读老版本内核代码时看到idr_alloc，在新版本里编译还能过，是因为兼容代码的存在。这时你需要意识到它们背后的实现已经换了，不理解这一点的话，你会被一些奇怪的性能差异迷惑。

7. 我的阅读建议和最终心得

说实话，《Linux内核设计与实现》这章的内容量并不大，但它像一张地图，为你指出了以后读内核源码时需要反复面对的几类结构。我在这本书上前后画了三次重点，每次重读都有新的体会。

第一次读时，我只关心list_head怎么用、红黑树怎么回事，API都记了一大堆。第二次读时，我开始问“为什么这么设计”，于是去翻了list.h、rbtree.h和xarray.c的实现，发现每个宏、每个分支都极其讲究。第三次读时，我带着自己在项目中踩的坑回来，看到每个结构体都能想起具体的调试场景，才真正觉得这一章读透了。

如果你也想真正掌握内核数据结构，我的建议是别急着背API，先理清四个问题：

1. 这个数据结构解决了什么性能问题？
2. 如果换成传统教科书里的实现，会差在哪里？
3. 它的并发访问模型是怎么设计的？
4. 它用在哪些内核子系统里，为什么这些子系统选择了它？

把这四个问题想明白，再回到代码里去验证，你就能从一个“读代码的人”慢慢变成一个“写代码的人”。

最后分享一个我自己总结的小技巧：读任何数据结构相关的内核代码时，永远先看它的头文件注释。内核的代码注释质量很高，很多复杂的边界条件和设计意图都写在里面。比如linux/list.h的头部注释就明确告诉了你链表头的嵌入方式和遍历宏的使用方法。这比你自己翻实现去猜省太多力气了。