最近又把《Linux内核设计与实现》里“内核数据结构”这一章翻了一遍。说实话这章放在整套书里属于“看着简单、后劲很大”的类型。它讲的链表、队列、映射、红黑树单拎出来任何一个都是计算机本科教材里早就见过的东西但放进内核这种“不能随便动态分配、全程多核并发、性能敏感”的环境里同样名字的数据结构设计取舍和用户态完全不是一回事。这篇笔记不想复述书里原文而是打算把书里容易略过的关键点结合我实际写内核模块和排查问题时的经验整理成一套能直接拿去参考的内容。适合准备内核相关笔试面试的人、正在做Linux驱动和内核模块开发的同事以及单纯想搞懂“内核为什么这样设计”的读者。如果你手头也有这本书建议把对应头文件打开一起看收获会大很多。1. 整体设计与思路拆解先搞清楚内核为什么“不好好说话”1.1 内核态数据结构与用户态的差异在哪用户态写代码标准库随便用vector、map、list随你挑底层内存不够了调用malloc就行失败了抛异常或者返回NULL处理一下。内核态没有这个条件。内核里动态内存分配在普通进程上下文还能用GFP_KERNEL在中断上下文、临界区里就只能用GFP_ATOMIC后者成功率低、内存还可能被碎片化。更重要的是内核代码里很多路径对性能极度敏感比如网络收包、调度器选任务、文件系统缓存查找这几个场景每个包、每次调度、每次读缓存都希望开销越小越好。所以内核数据结构设计有几个明显倾向尽量少分配内存最好把节点嵌进已有的结构体里。操作尽量O(1)实在不行也要O(log n)别出现O(n)的线性扫描热路径。多用宏做“伪泛型”而不是像C那样建立复杂的模板体系。保持极简头文件里看到一堆static inline函数就是为了减少函数调用开销。还有一个容易被忽略的点内核代码要处理并发。同一个链表可能被多个CPU同时遍历、插入、删除所以数据结构本身不负责加锁使用者必须自己保证同步或者使用RCU这类机制。这一点和用户态容器类完全不同也是面试官最喜欢追问的地方。1.2 这一章的阅读策略书里把内容按链表、队列、映射、红黑树、算法复杂度这个顺序排列其实是有讲究的从最基本、最广泛使用的结构逐步过渡到复杂度更高、面向特定场景的结构。链表几乎无处不用队列解决固定缓冲区的读写问题映射处理“整数ID对应指针”的需求红黑树则满足动态有序集合的高效检索。我建议阅读时不要只盯着书里的片段代码。直接在Linux源码目录下打开这几个头文件对照看include/linux/list.hinclude/linux/kfifo.hinclude/linux/idr.hinclude/linux/rbtree.hinclude/linux/xarray.h书里讲的是设计思路头文件里才是真实世界的细节。比如list.h里那些宏的嵌套写法初看像天书但理解了container_of和typeof之后就会觉得这套方案非常精巧。后面第3部分我会用代码实例拆解常见用法。2. 核心数据结构逐个拆解链表、队列、映射、红黑树2.1 双向循环链表不存数据的链表头内核链表最反直觉的设计是链表节点本身不包含数据而是作为一个字段嵌进你的结构体里。经典定义是struct list_head { struct list_head *next, *prev; };你的业务结构体长这样struct my_data { int key; char name[64]; struct list_head node; // 链表节点嵌进来 };这样设计的好处是通用性和扩展性好。用户态的链表通常让节点保存一个指向业务的指针但内核把链表节点塞进业务结构体内部那么只要通过某个节点的list_head成员指针就能用container_of宏反向算出整个业务结构体的起始地址#define container_of(ptr, type, member) \ ({ const typeof(((type *)0)-member) *__mptr (ptr); \ (type *)((char *)__mptr - offsetof(type, member)); })第一次看这个宏容易懵。它先声明一个与member类型一致的指针__mptr并把ptr赋给它然后减去member在type中的偏移量。你想想看如果把结构体想象成一间房子list_head成员是房子里的一扇窗户那么container_of就是通过窗户的位置反推出房子的门牌号。内核里到处都在用这个宏链表、红黑树、定时器、文件对象管理都靠它把通用节点还原回真实结构。链表头用LIST_HEAD(my_list)或INIT_LIST_HEAD(head)初始化。常用操作包括list_add头插list_add_tail尾插list_del删除节点list_empty判断是否空list_for_each_entry / list_for_each_entry_safe遍历业务结构体list_first_entry / list_first_entry_or_null取第一个元素内核链表是循环链表头节点既是起点也是终点所以判断空链表只需要检查头节点的next是否指向自己。这个设计让边界判断非常统一不需要单独处理头指针为NULL的情况。还有一个变体hash list。struct hlist_head只有一个first指针struct hlist_node有next和pprev两个指针。它牺牲了反向遍历能力换来每个哈希桶头节点只占一个指针省内存。在哈希表场景下通常不需要从桶头向前遍历所以这种不对称设计很合理。2.2 内核队列kfifokfifo是内核里的FIFO队列实现底层是一个环形缓冲区。它最核心的设计要求是缓冲区大小必须是2的幂。为什么因为环形缓冲区绕回时通常用取模计算偏移比如pos % size但取模指令开销不低。2的幂大小可以用位与代替取模pos (size - 1)。这个优化在热路径上能省好几个周期。kfifo的核心字段很简单struct __kfifo { unsigned int in; // 写入偏移 unsigned int out; // 读取偏移 unsigned int mask; // size - 1 unsigned int esize; void *data; };书里强调它的“无锁”特性但这里必须说清楚适用条件在有且仅有一个生产者和一个消费者的情况下生产者只修改in消费者只修改out二者不写同一个变量所以不需要加锁。一旦有多生产者或者多消费者竞争随之出现使用者必须自己加锁保护或者利用kfifo接口提供的spinlock封装版本。实际使用中我比较常用这几个接口kfifo_alloc(fifo, size, gfp_mask)分配缓冲区kfifo_in(fifo, buf, len)写入kfifo_out(fifo, buf, len)读出并消费kfifo_out_peek(fifo, buf, len)只读不消费常用于查看队首数据kfifo_len(fifo)返回当前已用字节数kfifo_free(fifo)释放要注意的是kfifo_in和kfifo_out拷贝的是数据本身不是引用。如果往里塞结构体需要关心对齐问题和记录边界。它适合流式数据比如串口接收缓冲、网络收包缓冲不适合做消息队列那种“按条读”的场景除非自己做封装。2.3 映射结构从idr到XArray书里讲的“映射”英文原文是map特指“从唯一ID映射到指针”的关联结构最常见的实现是idr。内核里很多资源需要“分配一个不冲突的整数编号再用这个编号查找对应对象”的场合比如设备号、中断号、某些子系统对象的handle。用一个固定数组可以解决但内核对象的ID往往不是从0开始的连续小整数稀疏分布会造成大量内存浪费。idr的设计目标就是按需分配ID内存占用和已分配的ID数量相关而不是和ID上限相关。旧实现基于基数树radix tree新版本内核已经逐步统一到XArray。XArray本质上是改进版的基数树提供类似稀疏数组的能力支持xa_store、xa_load、xa_alloc等接口。实际使用要注意几点idr_alloc(idr, ptr, start, end, gfp) 会返回一个可用ID失败返回负数错误码。idr_remove(idr, id) 把某个ID对应的指针清掉之后该ID可被复用。查询用 idr_find(idr, id)注意返回的是void指针需要自己强转。XArray的xa_alloc需要搭配XA_FLAGS_ALLOC标志使用否则不会自动分配空闲索引。书上这段内容写早于XArray全面落地现在看源码时不要困惑idr已经是XArray的一张皮底层数据结构是同一个东西。2.4 红黑树rbtree红黑树是内核里用于动态有序集合的主力。它有五个关键性质每个节点是红色或黑色根节点黑色所有叶子空指针是黑色红色节点的子节点必须黑色从任一节点到其所有后代叶子的路径上黑色节点数量相同。这些性质保证了最长路径不会超过最短路径的两倍所以树高严格控制在O(log n)。那为什么选红黑树而不是AVL树AVL树对平衡更苛刻查找略快一点但插入和删除需要更多的旋转操作来维持平衡。内核的使用场景往往是频繁插入删除、偶尔查找红黑树的平均旋转次数比AVL少整体开销更低。CFS调度器的运行队列就是一棵红黑树按虚拟运行时间排序每次想选下一个运行的任务直接取树的最左节点。内核rbtree的实现有几个值得说的细节节点中的__rb_parent_color字段把父节点指针和颜色位塞进了一个unsigned long利用对齐地址低位的空闲bit存储黑色标志。内核rbtree没有维护NULL哨兵节点空指针就是叶子节点这样每条路径的黑高度计算更自然。内核只提供插入后的平衡函数和删除函数不提供通用的按关键字查找函数。因为内核不知道你的key比较规则查找必须由使用者自己写循环遍历。红黑树在内核中有个重要应用场景管理进程的虚拟内存区域VMA。旧版本里每个进程的VMA按起始地址挂在一棵红黑树上快速判断一个地址落在哪个区间。后来这部分实现演进为maple tree但学习rbtree依然不过时它广泛存在于调度器、定时器、文件缓存等多个子系统。3. 实操过程与核心环节实现从声明到调试的完整链路3.1 链表遍历删除的正确姿势书里对链表的API讲得比较全但“如何正确删除当前节点”这件事值得单独拿出来写。先看一段初学者容易写出的错误代码struct my_data *pos; list_for_each_entry(pos, my_list, node) { if (pos-key target) { list_del(pos-node); kfree(pos); } }这段代码在你真正运行之前看起来没毛病但一旦删除第一个命中节点大概率直接触发use-after-free或者死循环。原因在于list_for_each_entry的展开逻辑是取当前节点的next作为下一次遍历指针而你在循环体里把当前节点释放了CPU可能已经在那个已经free的内存上读取了next指针。正确姿势是用safe版本struct my_data *pos, *tmp; list_for_each_entry_safe(pos, tmp, my_list, node) { if (pos-key target) { list_del(pos-node); kfree(pos); } }list_for_each_entry_safe在进入循环体之前就把下一个节点的指针保存到了tmp里这样当前节点被删除、释放都不影响后续遍历。这是内核代码里最常见的固定搭配不要嫌多写一个tmp变量麻烦。还有个细节容易忽略list_del是把节点从链表摘下来但节点本身的next、prev会指向一个固定的毒化地址 LIST_POISON1 和 LIST_POISON2。如果后续还要重新把这个节点插回链表就必须先调用INIT_LIST_HEAD(pos-node)或者直接丢弃这个节点。调试打开CONFIG_DEBUG_LIST之后对已经毒化的节点做操作会立刻打印告警能省很多排查时间。如果想实现LRU那种“访问后移到尾部”的逻辑不要手动摘链再插直接用list_move_tail(pos-node, list)一步到位。这个接口内部就是先list_del再list_add_tail比我最初自己写两步操作少一次竞态窗口。3.2 kfifo驱动实战看书上kfifo的实现分析和自己把它用起来完全是两码事。我在写一个虚拟串口驱动时用kfifo作为DMA收到的数据缓冲。初始化时这样写struct kfifo recv_fifo; int ret; ret kfifo_alloc(recv_fifo, PAGE_SIZE, GFP_KERNEL); if (ret) return -ENOMEM;PAGE_SIZE在大多数架构下是4096天然满足2的幂要求。如果传入的size不是2的幂__kfifo_alloc内部会做roundup_pow_of_two处理但为了代码清晰、避免踩坑建议调用方自己保证。生产者在中断上下文往队列塞数据unsigned int copied; copied kfifo_in(recv_fifo, dma_buffer, length);消费者在read系统调用里取数据unsigned int copied; copied kfifo_out(recv_fifo, user_buffer, size);这里有两个实际问题。第一中断上下文里不能调用可能睡眠的加锁函数如果我的驱动是单一生产者、单一消费者那么理论上可以不做额外加锁因为in和out由不同角色维护。但为了稳妥我在生产者侧关闭了本地中断消费者侧用自旋锁保护避免出现读端看到半截数据的状况。第二kfifo_out返回的是实际拷贝的字节数不一定等于你传入的len尤其是在缓冲快空的时候。很多新手驱动工程师忘了检查返回值导致读出的是垃圾数据残留。我习惯先kfifo_len确认有没有数据再决定是否调用kfifo_out同时用kfifo_out_peek预读一个字节判断消息边界。如果你需要记录“队列里现在有多少条消息”而不是多少字节建议在驱动里自己维护一个原子计数器在kfifo_in成功之后递增、kfifo_out成功之后递减不要试图从in和out的差值推导消息个数因为消息长度不一定相等。3.3 红黑树插入查找手写上一次做内核模块里需要按key管理一堆节点我果断选了rbtree但写的时候发现书上只讲了调用库函数没说怎么组织遍历。内核rbtree的标准插入流程其实很固定。定义节点struct foo_node { u32 key; struct rb_node rb; };插入函数int foo_insert(struct rb_root *root, struct foo_node *new) { struct rb_node **link root-rb_node; struct rb_node *parent NULL; while (*link) { struct foo_node *cur rb_entry(*link, struct foo_node, rb); parent *link; if (new-key cur-key) link (*link)-rb_left; else if (new-key cur-key) link (*link)-rb_right; else return -EEXIST; } rb_link_node(new-rb, parent, link); rb_insert_color(new-rb, root); return 0; }查找函数struct foo_node *foo_search(struct rb_root *root, u32 key) { struct rb_node *node root-rb_node; while (node) { struct foo_node *cur rb_entry(node, struct foo_node, rb); if (key cur-key) node node-rb_left; else if (key cur-key) node node-rb_right; else return cur; } return NULL; }删除则用rb_erase(node-rb, root)。熟悉这套写法之后再看CFS调度器代码就会觉得亲切很多它只是把比较逻辑换成虚拟运行时间把最左节点作为候选运行实体。这里有一个坑rbtree的节点在结构体中的偏移量会导致rb_entry转换出错。如果某个字段声明时没有仔细核对名字用rb_entry拿到的宿主结构体指针永远是错的轻则读到错数据重则直接崩溃。建议每次写rbtree相关代码时都先跑一个简单的自测插入几个节点再遍历整棵树打印key确认顺序正确再往下写业务逻辑。3.4 idr/XArray资源分配示例内核里分配编号这件事用idr处理起来非常顺手。假设我为某个自定义设备分配设备号段内的次设备号struct idr dev_idr; int id; idr_init(dev_idr); id idr_alloc(dev_idr, dev_obj, 0, 256, GFP_KERNEL); if (id 0) return id;释放时idr_remove(dev_idr, id);如果用的是新版XArray接口初始化方式略有不同struct xarray xa; int id; xa_init_flags(xa, XA_FLAGS_ALLOC); id xa_alloc(xa, id, dev_obj, xa_limit_32b, GFP_KERNEL);xa_alloc的第二个参数是“输出型参数”调用前是一个你指定的搜索起始值调用成功后会被内核改写为实际分配的ID。这一点和idr_alloc的返回风格不一样容易写错我至少错过两次。XArray的底层是基数树适合稀疏索引的场景。比如一个文件的页缓存索引是文件内偏移值是指向页结构的指针这种“稀疏的大整数空间映射”用数组就是灾难用哈希表又丢失了顺序性基数树则兼顾了空间利用和迭代顺序。4. 调试经验与问题排查实录4.1 先打开内核调试选项书本教你写代码但没教你代码坏了怎么排查。我踩过几次链表崩溃的坑后学乖了调试内核时预先打开以下配置项。CONFIG_DEBUG_LIST链表完整性校验。在list_add、list_del时检查prev和next是否一致发现问题直接打印“list_del corruption, next-prev should be prev”。CONFIG_DEBUG_OBJECTS_RBTREE红黑树结构校验能检查颜色和黑高是否被破坏。CONFIG_KASAN内存越界和use-after-free检测内核版AddressSanitizer强烈建议在开发版内核里打开。CONFIG_LOCKDEP锁依赖检查虽然不直接查数据结构但很多并发问题最终是通过锁顺序告警浮出水面的。CONFIG_KCSAN数据竞争检测适合怀疑无锁场景被并发写坏的场景缺点是慢到怀疑人生。这些选项会引入额外开销生产内核别开开发机和虚拟机里常驻没问题。查链表损坏还有一个笨但有效的方法崩溃后把节点地址打出来手动检查它的prev和next是否指向LIST_POISON1/LIST_POISON2。如果是说明这个节点被list_del之后又被某个代码路径访问了。看到这个毒化地址先把所有可能引用该节点的调用点列出来逐个排查。4.2 动态追踪内核数据结构的实际使用日常开发里我经常想确认某个数据结构被谁改了、频率多高。Ftrace和kprobe是首选。举个例子给驱动的插入函数挂一个探针echo p:myprobe mydriver_foo_insert key%di /sys/kernel/debug/tracing/kprobe_events echo 1 /sys/kernel/debug/tracing/events/kprobes/myprobe/enable cat /sys/kernel/debug/tracing/tracex86_64下第一个参数保存在rdi寄存器所以%di能拿到插入函数的第一个参数。这种手段在排查“为什么红黑树高度突然变得不平衡”“链表节点在哪一步被重复插入”时非常直观尤其当数据结构被多个子系统共享时靠打印日志往往打不全探针则可以在不重新编译模块的情况下抓到完整调用栈。Ftrace的函数图模式也很有用echo function_graph /sys/kernel/debug/tracing/current_tracer echo rb_insert_color /sys/kernel/debug/tracing/set_ftrace_filter可以看到rb_insert_color的调用时长和调用路径帮助你判断是不是某个异常流程把平衡函数调歪了。4.3 一个典型链表崩溃案例说个我印象比较深的排查过程。某模块运行几个小时后挂掉日志里只有Unable to handle kernel paging request和一堆寄存器。我第一反应不是看业务逻辑而是先看崩溃地址附近的链表指针。用crash工具分析vmcore发现某个结构体的list_head节点的prev指向了一个内核堆对象但该对象的类型完全不对。再往前追发现是另一个模块在释放对象时错误地用了list_del_init而不是list_del把节点从链表中摘下的同时修改了节点自身指针范围导致后续遍历这个链表的模块读到了野指针。这个案例的教训是一个结构体如果可能被多个模块共享那么它的链表节点生命周期必须由明确的“所有者”来管理谁负责删除、谁负责摘链必须在代码注释和函数边界写死。调试工具只能告诉你哪里坏了设计约定才能避免坏。5. 常见问题速查与数据结构选型建议5.1 高频问题速查表内核数据结构这块的面试题有很强的套路性。我把自己见过和问过的一些高频题整理成表格问题关键答题点数组和链表的适用场景数组适合固定大小、随机访问、cache友好链表适合频繁插入删除、大小动态变化内核链表为什么不直接存数据通过container_of反推宿主结构避免为每种业务类型写一套链表实现泛型复用kfifo为什么能无锁只有单一生产者和单一消费者时in和out由不同角色维护写位置不冲突kfifo为什么要求2的幂用位与代替取模提升环形索引计算效率为什么用红黑树不用AVL红黑树插入删除的旋转更少综合性能更好内核动态操作多红黑树和哈希表怎么选需要有序遍历、范围查询用红黑树只按key精确查找、数据量大且内存宽松时用哈希idr/XArray和普通数组的区别按需分配、支持稀疏ID不会因为ID范围大而占满内存container_of宏的原理用member在type中的偏移量反推宿主指针内核哈希表为什么用hlist哈希桶头节点不需要prev指针节省内存一个桶里第一个节点减少了指针维护开销链表删除后为什么毒化指针让释放后仍然访问节点的代码尽早暴露问题配合CONFIG_DEBUG_LIST使用5.2 选型建议很多内核开发新手遇到一个需求第一反应就是用红黑树可能是因为红黑树听起来“高级”。实际选型应该优先从最简单、最贴需求的结构开始。数量有上限、且范围不稀疏直接定长数组简单可靠还能让cache命中率拉满。需要快速分配和释放编号、编号可能稀疏用idr或XArray。FIFO数据缓冲、大小固定kfifo。频繁在头部尾部操作、需要按插入顺序遍历list_head链表。动态有序集合、需要排序和范围查找rbtree。大规模key-value查找、没有顺序要求rhashtable或hlist。记住一句话内核不是算法秀场能用数组说清楚的事不要引入红黑树能用链表解决的事不要上哈希表。复杂结构意味着更复杂的调试、更隐蔽的并发问题以及更长的review时间。5.3 源码阅读入口建议如果读完LKD这一章还觉得不过瘾推荐动手读这几个文件配合内核文档下的Documentation/core-api/目录include/linux/list.h链表宏的完整实现lib/kfifo.c 和 include/linux/kfifo.h队列的分配与读写逻辑lib/rbtree.c 和 include/linux/rbtree.h旋转与颜色维护include/linux/xarray.h 和 lib/xarray.c现代版的基数树实现kernel/sched/fair.c 里的红黑树用法看真实场景怎么管理运行队列读法不要从头读到尾先看结构体定义和API列表再挑一个简单操作函数追进去比如list_add追到__list_add再追到WRITE_ONCE宏。这样一层层剥下去比你硬背API名称有用得多。我个人在实际操作中的体会是这本书的内容常看常新。第一次读觉得“就这”第二次读开始对照源码第三次读才会真正理解每个设计决策背后的约束条件。比如容器思想的container_of、2的幂环形队列、红黑树放弃哨兵节点这些方案单独看都能明白但把它们放在“内存受限、并发激烈、性能敏感”的背景下才能体会出设计的巧妙。如果你正打算深入内核开发我建议从自己最常用的子系统入手找到里面用到的数据结构紧跟一个操作场景把代码读完整。比如你常写网络相关代码就去看sk_buff的链表管理常做调度优化就去看CFS的rbtree操作。这比漫无目的地翻源码高效得多。最后再分享一个小技巧每学完一种内核数据结构尝试在用户态用普通C语言仿写一个最小版本不需要考虑并发和内核API只要复现核心逻辑。等你能写对container_of和红黑树插入的旋转流程再回到内核看代码视野会完全不一样。