读书这件事最怕的就是“看完了”和“看懂了”之间隔着一条巨大的鸿沟。我当初第一次翻《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在多读多写场景下主要依赖RCURead-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等接口但它的设计仍然要求调用者自己实现比较函数和节点嵌入逻辑。很多人第一次用的时候觉得别扭——为什么不干脆提供一个像用户态那样的mapstring, 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 几大数据结构的演进逻辑读这章时我建议大家顺手做一个对比表把几个核心数据结构的适用场景记清楚数据结构核心特征典型应用常见操作复杂度双向链表嵌入节点、O(1)插入删除设备管理、任务管理查找O(n)hlist头节点瘦身、二级指针哈希表冲突链查找O(n/桶长)kfifo环形缓冲、无锁读驱动数据流入队出队O(1)idr/xarray稀疏数组、ID映射设备号、fd管理查找O(log n)红黑树自平衡、稳定O(log n)CFS、epoll、VMA查找/插入/删除O(log n)这个表不是让你背的是让你在选型时有据可依。你如果在内核里要设计一个新的管理结构先对照这个表选一个合适的再动手写比自己造一个“万能结构”靠谱得多。还有一个演进细节容易被忽略很多老代码里的idr已经被转换成xarray但API兼容层还在。你读老版本内核代码时看到idr_alloc在新版本里编译还能过是因为兼容代码的存在。这时你需要意识到它们背后的实现已经换了不理解这一点的话你会被一些奇怪的性能差异迷惑。7. 我的阅读建议和最终心得说实话《Linux内核设计与实现》这章的内容量并不大但它像一张地图为你指出了以后读内核源码时需要反复面对的几类结构。我在这本书上前后画了三次重点每次重读都有新的体会。第一次读时我只关心list_head怎么用、红黑树怎么回事API都记了一大堆。第二次读时我开始问“为什么这么设计”于是去翻了list.h、rbtree.h和xarray.c的实现发现每个宏、每个分支都极其讲究。第三次读时我带着自己在项目中踩的坑回来看到每个结构体都能想起具体的调试场景才真正觉得这一章读透了。如果你也想真正掌握内核数据结构我的建议是别急着背API先理清四个问题这个数据结构解决了什么性能问题如果换成传统教科书里的实现会差在哪里它的并发访问模型是怎么设计的它用在哪些内核子系统里为什么这些子系统选择了它把这四个问题想明白再回到代码里去验证你就能从一个“读代码的人”慢慢变成一个“写代码的人”。最后分享一个我自己总结的小技巧读任何数据结构相关的内核代码时永远先看它的头文件注释。内核的代码注释质量很高很多复杂的边界条件和设计意图都写在里面。比如linux/list.h的头部注释就明确告诉了你链表头的嵌入方式和遍历宏的使用方法。这比你自己翻实现去猜省太多力气了。