1. 从一道内核链表题说起为什么值得认真拆解第一次看到“用链表存储若干自然数把 1 2 3 4 5 6 7 8 9 重排成 1 3 5 7 9 8 6 4 2”这个题目时很多人第一反应是“这不就是个数组排序题吗开个数组分奇偶两半奇数正着放、偶数倒着放两分钟搞定”。如果只是应付一道普通作业这么想没错。但题目里明明白白写着“Linux内核链表”这就把问题的性质完全改变了——它考的不是排序算法而是你对内核链表这套基础设施的理解和运用能力。Linux内核链表是内核源码里使用频率最高的数据结构之一进程管理、设备驱动、文件系统、网络协议栈几乎无处不在。它和教科书上那种“数据域指针域”的链表长得完全不一样核心思想是把链表节点嵌入到业务数据结构内部让链表只负责“串起来”不负责“存什么”。这个设计带来的最大好处是同一套链表操作代码可以复用到任何结构体上不需要为每种数据类型重写一遍增删改查。这道题的实际价值在于它用一个极简的场景存储自然数并重排逼着你去实践内核链表的三件核心事情怎么定义节点、怎么遍历、怎么在遍历过程中安全地移动节点。尤其是最后一步“重排”涉及节点摘除和重新插入是内核链表操作里最容易出错的地方也是面试和实际开发中区分“会用”和“用对”的分水岭。这篇文章适合三类人看正在学操作系统或内核模块开发的学生、想从应用层转向底层开发的工程师、以及工作中需要维护内核态代码但链表操作总是写不利索的从业者。我会从设计思路讲到具体实现把每个关键决策背后的原因说清楚再把我自己踩过的坑和排查经验一并分享出来。整篇内容基于常见的内核链表实践展开代码可以直接参考复现。2. 内核链表到底和普通链表差在哪2.1 普通链表的痛点每换一种数据就得重写一遍先回忆一下教科书上的单链表长什么样。通常是这样的结构struct node { int data; struct node *next; };这个结构把数据域和指针域绑死在一起。如果现在要存一个字符串就得再定义一个struct string_node把int data换成char *data然后增删查改的函数全部重写一遍。数据种类一多代码里就充斥着一堆功能重复、只是类型不同的链表实现。这是典型的代码冗余维护起来非常痛苦。更麻烦的是当业务结构体本身很复杂时你没法把一个已经存在的结构体“变成”链表节点。比如你有一个表示进程的结构体里面几十个字段你不可能为了把它挂到链表上就在里面塞一个next指针然后到处传递这个结构体的指针——因为一旦你要把同一个进程同时挂到“就绪队列”和“等待队列”两个链表上一个next指针根本不够用。2.2 内核链表的解法把“钩子”嵌进结构体内核链表换了个思路。它定义了一个纯粹的链表节点里面只有前后指针没有任何数据struct list_head { struct list_head *next, *prev; };注意这是双向循环链表next和prev都有而且头节点的prev指向尾节点尾节点的next指向头节点形成一个环。这个设计的好处后面会讲。用的时候你把它作为一个成员嵌入到自己的业务结构体里struct my_data { int value; struct list_head list; };这样一来链表节点和业务数据是“包含”关系而不是“绑定”关系。同一个struct my_data里可以放多个list_head成员就能同时挂到多个链表上。链表操作函数只认list_head不关心外面包的是什么通用性直接拉满。2.3 最关键的宏container_of 和 list_entry嵌入式的设计带来一个新问题我手里拿到的是一个struct list_head *指针怎么反推出包含它的那个struct my_data *答案就是内核里大名鼎鼎的container_of宏。它的原理是根据成员在结构体中的偏移量用指针减法算出结构体的起始地址。内核链表在此基础上封装了list_entry新版本叫list_first_entry等系列用法是struct my_data *p list_entry(ptr, struct my_data, list);意思是ptr是一个指向list成员的指针list是struct my_data里的成员名请帮我算出整个struct my_data的地址。这个宏是理解内核链表的钥匙不理解它后面遍历和重排都会看得很懵。提示container_of依赖编译器对结构体成员偏移的计算所以成员名必须写对写错了编译能过但运行时会拿到错误地址这是新手最常见的坑之一。2.4 为什么是循环链表而不是单链表很多人会问双向循环链表是不是过度设计了。实际用下来循环结构带来两个实打实的便利。第一头节点的prev直接指向尾节点要在尾部插入元素时不需要从头遍历到尾O(1) 就能拿到尾指针。第二遍历的终止条件是“回到起点”不需要额外判断 NULL代码更统一。对于这道重排题来说我们需要频繁地在头部和尾部之间搬移节点循环双向结构让这些操作都变得非常顺手。3. 重排需求拆解奇数升序偶数降序怎么落地3.1 先明确目标序列的规律原始序列是 1 到 9 的自然数升序排列。目标序列是 1 3 5 7 9 8 6 4 2。拆开看前半段是所有奇数保持升序后半段是所有偶数但是降序。所以本质上要做两件事按奇偶把节点分成两组奇数组保持原序偶数组反转顺序最后把偶数组接到奇数组后面。这里有个容易忽略的点题目说的是“若干自然数”不一定非得是 1 到 9 连续。可能是任意一组自然数比如 3 1 4 1 5 9 2 6。所以算法不能假设输入是连续递增的得按通用情况处理。不过为了和题目示例对齐我们后面用 1 到 9 来演示同时说明通用处理方式。3.2 三种可行思路的对比面对这个需求脑子里至少能冒出三种做法各有取舍。第一种是新建两个链表遍历原链表奇数尾插到奇数链表偶数头插到偶数链表最后拼接。头插天然实现逆序所以偶数链表自动就是降序。这种做法逻辑最清晰但需要额外的头节点内存开销略大。第二种是原地重排不新建链表直接在原链表上把偶数节点摘下来重新插入到合适位置。这种做法省内存但指针操作复杂容易断链。第三种是先全部摘下来再按规则重建相当于把原链表拆散然后按目标顺序一个个重新挂上去。这种做法介于前两者之间逻辑比原地重排简单又比新建链表省一点。考虑到这是内核链表练习题我倾向于选第二种原地重排因为它最能锻炼对list_del和list_add系列函数的掌握也最贴近真实内核代码的风格。但我会在实现里把关键步骤拆细避免断链。3.3 关键操作函数速查在动手之前先把要用到的内核链表函数列清楚这些是后面代码的基础。函数/宏作用使用场景INIT_LIST_HEAD(head)初始化头节点前后指针指向自己创建空链表list_add(new, head)把 new 插到 head 之后头插需要逆序时用list_add_tail(new, head)把 new 插到 head 之前尾插需要保持顺序时用list_del(entry)把 entry 从链表中摘除移动节点前必须先摘list_empty(head)判断链表是否为空循环终止条件list_for_each(pos, head)正向遍历只读遍历list_for_each_safe(pos, n, head)安全遍历允许删除当前节点遍历中摘除节点list_entry(ptr, type, member)由链表节点反推业务结构体取数据这张表建议存下来写内核链表代码时对着看能省很多查文档的时间。4. 完整实现从建表到重排的每一步4.1 数据结构定义与初始化先定义业务结构体和头节点。为了演示清晰业务数据就存一个整数。#include linux/list.h #include linux/kernel.h #include linux/slab.h struct num_node { int value; struct list_head list; }; static LIST_HEAD(num_list); // 定义并初始化全局头节点LIST_HEAD宏等价于定义一个struct list_head并调用INIT_LIST_HEAD一步到位。如果是在函数内部用就写成struct list_head head; INIT_LIST_HEAD(head);初始化这一步千万别省。未初始化的list_head里是垃圾值直接list_add进去会导致指针指向随机内存轻则数据错乱重则内核崩溃。我见过有人图省事跳过初始化调试了半天才发现问题出在这里。4.2 建表把自然数挂上去假设我们要插入 1 到 9用尾插保持升序int i; for (i 1; i 9; i) { struct num_node *n kmalloc(sizeof(*n), GFP_KERNEL); if (!n) return -ENOMEM; n-value i; INIT_LIST_HEAD(n-list); // 单个节点也要初始化 list_add_tail(n-list, num_list); }这里有两个细节值得说。第一每个新节点的list成员也要INIT_LIST_HEAD虽然list_add_tail会覆盖next和prev但养成初始化的习惯能避免很多隐蔽问题。第二kmalloc分配的内存不会自动清零所以value必须显式赋值不能指望它是 0。建完表后链表里就是 1 2 3 4 5 6 7 8 9头节点的next指向 1prev指向 9。4.3 遍历打印先确认建表正确在重排之前先写个打印函数验证一下链表内容这是排查问题的基本习惯。static void print_list(struct list_head *head) { struct num_node *pos; list_for_each_entry(pos, head, list) { printk(KERN_INFO %d , pos-value); } printk(KERN_INFO \n); }list_for_each_entry是遍历的常用宏它内部自动做了list_entry转换用起来比手动list_for_each加list_entry方便。打印出来应该是1 2 3 4 5 6 7 8 9如果顺序不对或者缺元素说明建表阶段就有问题先别往下走。4.4 重排核心逻辑摘偶数、头插、拼接现在进入正题。我的思路是遍历原链表遇到偶数就把它从当前位置摘下来头插到一个临时的偶数链表里。因为头插是逆序的遍历完原链表后偶数链表自然就是降序。最后把偶数链表整体接到奇数链表也就是原链表剩下的部分后面。static void rearrange(struct list_head *head) { struct list_head even_head; struct num_node *pos, *n; INIT_LIST_HEAD(even_head); list_for_each_entry_safe(pos, n, head, list) { if (pos-value % 2 0) { list_del(pos-list); // 从原链表摘除 list_add(pos-list, even_head); // 头插到偶数链表 } } // 把偶数链表整体拼到奇数链表尾部 list_splice_tail(even_head, head); }这段代码不长但每一行都有讲究。先说list_for_each_entry_safe它比普通遍历多了一个n参数用来暂存下一个节点。为什么需要因为我们在循环体里对pos执行了list_del摘除后pos-list.next就不可靠了如果还用普通遍历下一轮就会访问到错误地址。_safe版本提前把下一个节点存到n里保证遍历安全。这是内核链表操作里最重要的一个习惯凡是遍历中可能删除节点就必须用_safe版本。再说list_del和list_add的配合。list_del只是把节点从链表里摘出来节点本身的内存还在list_add再把它挂到新链表上。这两个操作合起来就是“移动节点”。注意list_del之后节点的next和prev会被设成特殊值在开启调试时会指向毒药地址所以摘除后不要再去读它的前后指针。最后list_splice_tail把even_head里的所有节点接到head的尾部并重新初始化even_head。这个函数比手动遍历一个个搬要高效也更不容易出错。4.5 验证结果与内存释放重排完再调用一次print_list应该输出1 3 5 7 9 8 6 4 2。如果结果对了别忘了释放内存static void free_list(struct list_head *head) { struct num_node *pos, *n; list_for_each_entry_safe(pos, n, head, list) { list_del(pos-list); kfree(pos); } }释放同样要用_safe版本因为循环体里删除了当前节点。这个函数写不好会导致内存泄漏或者释放后访问是内核模块里常见的资源管理问题。5. 踩坑记录与排查经验5.1 遍历中删除节点导致崩溃这是最经典的坑。我早期写类似逻辑时用了list_for_each_entry而不是_safe版本结果在摘除偶数节点后下一轮循环访问pos-list.next拿到的是已经被改写的指针直接触发内核 oops。排查这类问题有个技巧看崩溃地址是不是一个很奇怪的值比如0xdead000000000000这种如果是基本可以确定是访问了已删除节点的指针。解决办法就是无脑用_safe版本养成肌肉记忆。5.2 忘记初始化头节点另一个高频问题是头节点没初始化。表现是插入第一个节点时看起来正常插入第二个就乱套或者遍历时死循环。原因是未初始化的head-next指向随机地址list_add_tail会试图去修改那个随机地址的prev行为完全不可预测。用LIST_HEAD宏或者显式INIT_LIST_HEAD都能避免关键是别偷懒。5.3 头插和尾插用反导致顺序错误这道题里奇数要保持升序所以遍历时不能动它们让它们留在原链表里自然保持顺序。偶数要降序所以用头插。如果偶数也用尾插结果就会变成1 3 5 7 9 2 4 6 8偶数部分顺序反了。判断用哪种插入方式就看你要的顺序和遍历顺序是一致还是相反一致用尾插相反用头插。这个规律记住能省很多试错时间。5.4 常见问题速查表现象可能原因排查方向遍历死循环头节点未初始化或链表成环异常检查INIT_LIST_HEAD是否调用崩溃在list_del附近遍历中删除未用_safe改用list_for_each_entry_safe数据顺序错乱头插尾插用反对照目标顺序判断插入方式内存泄漏释放时漏掉节点用_safe遍历逐个kfree取到的 value 是垃圾值container_of成员名写错核对list_entry第三个参数拼接后偶数部分顺序不对list_splice方向搞反区分list_splice和list_splice_tail5.5 一个容易被忽略的调试技巧内核代码不像用户态程序那样能随便加printf但printk配合日志级别很好用。我习惯在关键步骤后打印链表状态比如建表后打一次、摘除循环每轮打一次、拼接后再打一次。虽然日志会多但定位问题时能一眼看出是哪一步开始不对。另外如果是在可加载模块里调试记得用dmesg -w实时看输出比反复dmesg | tail高效得多。6. 从这道题延伸出去的实际应用6.1 内核里真实的重排场景这道题看着像玩具但“按条件分组再重组”在内核里非常常见。比如进程调度器需要把进程按优先级分组网络协议栈需要把数据包按类型分流设备驱动需要把请求按方向排队。它们的共同点是数据节点本身已经在某个链表上需要根据某个字段的值把它们重新组织到不同的队列里。这时候list_del加list_add的组合就是标准操作和这道题的偶数摘除逻辑本质相同。6.2 多链表挂载的实战价值前面提到一个结构体可以嵌多个list_head从而同时挂在多个链表上。这个特性在实际开发中非常有用。比如一个任务节点既要在“待处理队列”里又要在“按优先级排序的队列”里就可以定义两个list_head成员分别挂到两个链表。操作时要注意从其中一个链表摘除不影响另一个但释放内存前必须确保从所有链表都摘干净否则会出现悬空指针。这是比单链表复杂的地方也是内核链表灵活性的代价。6.3 性能上的考量有人可能担心list_del加list_add这种“摘了再挂”的操作会不会很慢。实际上这两个操作都是 O(1) 的只改几个指针不涉及数据搬移。整道题的时间复杂度是 O(n)遍历一遍就完成重排空间上除了一个临时头节点没有额外分配。这比“新建两个数组再拷贝”的做法在内存受限的内核环境里优势明显。当然如果数据量极小两种做法差别不大但养成 O(1) 移动节点的习惯在处理大规模链表时收益很大。6.4 如果要支持任意自然数序列题目示例是 1 到 9但真实场景里输入可能是乱序的。如果输入是3 1 4 1 5 9 2 6要求奇数升序、偶数降序那就不能只靠“保持原序”了得在插入时做排序。一种做法是插入奇数时用list_add找到合适位置插入保持升序偶数头插到偶数链表后再对偶数链表做一次排序。另一种做法是先把所有节点摘下来用两个临时链表分别收集奇偶奇数链表排序后拼接偶数链表。具体选哪种看数据规模和性能要求但核心的链表操作函数还是那几个万变不离其宗。7. 几个让代码更稳的实操建议写内核链表代码我总结了几个能显著降低出错率的习惯分享出来。第一任何可能修改链表的遍历都用_safe版本。不要试图判断“这次循环应该不会删节点”就省掉n参数需求一变就容易出事统一用_safe最省心。第二摘除节点后立刻处理不要留着悬空指针。list_del之后要么马上list_add到新位置要么马上kfree中间不要插入可能出错的逻辑。悬空指针是内核 bug 的头号来源。第三头节点永远用宏初始化。LIST_HEAD一行搞定比手动写两行赋值不容易漏。局部变量用INIT_LIST_HEAD别嫌麻烦。第四调试时先验证链表结构再验证数据。先打印节点个数和顺序确认链表本身没问题再看value对不对。如果链表结构都乱了纠结数据没意义。第五拼接操作用list_splice系列而不是手动遍历。内核提供的拼接函数已经处理好了边界情况手动搬容易在头尾衔接处出错尤其是空链表的情况。这道题我前后用不同思路实现过三四遍每次都能发现之前没注意的细节。内核链表这套东西看文档觉得简单真动手写才会发现坑都在细节里。把这道题吃透再去写进程队列、设备请求队列之类的代码会顺畅很多。后续如果想继续深入可以试试把单链表版本改成支持多链表挂载或者加上按值查找和删除的功能都是很好的练手方向。