【免费下载链接】linux-insides-zhLinux 内核揭秘项目地址https://gitcode.com/hust-open-atom-club/linux-insides-zh点击查看免费下载Linux 内核并没有采用教科书式的数据节点内嵌指针链表而是自己实现了一套以struct list_head为核心的侵入式双向链表其定义与全部 API 位于内核头文件include/linux/list.h中。本篇文章基于本仓库 DataStructures/linux-datastructures-1.md 展开深入剖析list_head的结构设计、初始化宏、插入与删除接口以及反向定位宿主结构体的container_of宏原理并通过杂项字符驱动misc 设备的真实注册流程和本仓库多篇内核主题文章中的实际用例帮助读者彻底理解这一在内核中被广泛使用的数据结构。为什么内核要自己实现一套双向链表几乎所有操作系统内核都会提供链表Linux 内核也不例外。不过Linux 内核并没有直接使用用户空间常见的数据 指针链表模型而是在头文件include/linux/list.h中实现了侵入式intrusive双向链表其核心结构体定义在include/linux/types.h中struct list_head { struct list_head *next, *prev; };注意struct list_head中没有数据域。这与传统的链表实现截然不同。例如 GNU C 库glib中的链表是这样定义的struct GList { gpointer data; GList *next; GList *prev; };传统链表把数据指针和链接指针放在同一个节点里节点直接保存指向数据的指针而内核的侵入式链表恰好相反——节点只包含指向前驱和后继的指针真正的数据被附加在链表节点之外由宿主结构体把struct list_head作为自己的成员变量嵌入。这种设计带来的最大好处是通用性链表操作只关心next/prev两个指针完全不感知宿主数据的类型因此同一套list_add、list_del、list_for_each接口可以服务于内核中任意结构体。例如内核中保存 NMI 描述符的结构体可以这样嵌入链表节点struct nmi_desc { spinlock_t lock; struct list_head head; };宿主结构体如nmi_desc与链表节点head通过成员偏移关联起来——这正是后面要讲的container_of宏存在的意义。实战案例杂项字符驱动如何用链表管理设备内核中有大量的地方使用list_head。本仓库 DataStructures/linux-datastructures-1.md 选取了一个非常直观的例子——杂项字符驱动misc device其 API 位于内核源文件drivers/char/misc.c。杂项字符驱动用于编写处理小型硬件和虚拟设备的小驱动所有这类设备共享同一个主设备号#define MISC_MAJOR 10但各自拥有不同的次设备号minor number。在 Linux 系统上执行ls -l /dev | grep 10可以看到crw------- 1 root root 10, 235 Mar 21 12:01 autofs drwxr-xr-x 10 root root 200 Mar 21 12:01 cpu crw------- 1 root root 10, 62 Mar 21 12:01 cpu_dma_latency crw------- 1 root root 10, 203 Mar 21 12:01 cuse drwxr-xr-x 2 root root 100 Mar 21 12:01 dri crw-rw-rw- 1 root root 10, 229 Mar 21 12:01 fuse crw------- 1 root root 10, 228 Mar 21 12:01 hpet crw------- 1 root root 10, 183 Mar 21 12:01 hwrng crw-rw---- 1 root kvm 10, 232 Mar 21 12:01 kvm crw-rw---- 1 root disk 10, 237 Mar 21 12:01 loop-control crw------- 1 root root 10, 227 Mar 21 12:01 mcelog crw------- 1 root root 10, 59 Mar 21 12:01 memory_bandwidth crw------- 1 root root 10, 61 Mar 21 12:01 network_latency crw------- 1 root root 10, 60 Mar 21 12:01 network_throughput crw-r----- 1 root kmem 10, 144 Mar 21 12:01 nvram brw-rw---- 1 root disk 1, 10 Mar 21 12:01 ram10 crw--w---- 1 root tty 4, 10 Mar 21 12:01 tty10 crw-rw---- 1 root dialout 4, 74 Mar 21 12:01 ttyS10 crw------- 1 root root 10, 63 Mar 21 12:01 vga_arbiter crw------- 1 root root 10, 137 Mar 21 12:01 vhci内核需要把所有这些共享主设备号 10 的杂项设备组织起来统一管理这个任务正是由双向链表完成的。先看描述杂项设备的结构体miscdevicestruct miscdevice { int minor; const char *name; const struct file_operations *fops; struct list_head list; struct device *parent; struct device *this_device; const char *nodename; mode_t mode; };结构体第四个成员list就是链表节点它把所有已注册的杂项设备串成一条链表。链表的头在源码文件drivers/char/misc.c开头以静态方式定义static LIST_HEAD(misc_list);链表头的定义与初始化宏LIST_HEAD(name)宏展开后实际上就是定义一个并初始化一个struct list_head类型的变量#define LIST_HEAD(name) \ struct list_head name LIST_HEAD_INIT(name)而LIST_HEAD_INIT使用变量自身的地址同时填充prev和next使空链表头自指——既没有前驱也没有后继#define LIST_HEAD_INIT(name) { (name), (name) }也就是说一个空的list_head的两个指针都指向它自己这是内核链表判断链表是否为空的基础。当设备需要被动态注册时misc_register函数一开始就用INIT_LIST_HEAD初始化miscdevice-listINIT_LIST_HEAD(misc-list);INIT_LIST_HEAD的效果与LIST_HEAD_INIT完全相同只是它作用于一个已经存在的指针static inline void INIT_LIST_HEAD(struct list_head *list) { list-next list; list-prev list; }从本仓库其他章节也可以看到这两个宏在内核各处被反复使用信号量结构体的wait_list等待队列就是用LIST_HEAD_INIT静态初始化成空链表参见 SyncPrim/linux-sync-3.mdinit/main.c附近的init_mm内存描述符中的.mmlist同样以LIST_HEAD_INIT(init_mm.mmlist)初始化参见 Initialization/linux-initialization-5.md根任务组root_task_group的children/siblings链表在调度器初始化时通过INIT_LIST_HEAD清零参见 Initialization/linux-initialization-8.md工作队列workqueue宏在初始化work_struct时也会调用INIT_LIST_HEAD((_work)-entry)参见 Interrupts/linux-interrupts-9.md。向链表添加节点list_add 与 __list_add在device_create创建设备之后misc_register用下面这条语句把新设备挂到misc_list链表头之后list_add(misc-list, misc_list);list_add的接口很简单但它真正的逻辑在内部函数__list_add中static inline void list_add(struct list_head *new, struct list_head *head) { __list_add(new, head, head-next); }__list_add接收三个参数new—— 要插入的新节点prev—— 新节点将被插入到它之后next—— 原本在prev之后的那个节点即head-next。其实现只有四条指针赋值语句static inline void __list_add(struct list_head *new, struct list_head *prev, struct list_head *next) { next-prev new; new-next next; new-prev prev; prev-next new; }可以看到__list_add的本质是在prev与next两个既有节点之间缝合一个新节点先让next-prev指向新节点再让new的next/prev分别指向next与prev最后让prev-next指向新节点。四条赋值缺一不可否则链表就会出现断链。因此经过LIST_HEAD_INIT初始化的misc_list与每个新注册设备miscdevice-list之间就通过这种双向指针互链的方式组织成了一条完整的环形双向链表。核心魔法list_entry 与 container_of 反向定位宿主结构体链表里只存指针那么内核是如何从链表节点找回它所归属的宿主结构体的呢这就要用到list_entry宏#define list_entry(ptr, type, member) \ container_of(ptr, type, member)它接收三个参数ptr—— 指向链表节点的指针即宿主结构体内list_head成员的地址type—— 宿主结构体的类型member—— 宿主结构体中那个list_head类型成员的名字。例如遍历misc_list时可以通过下面的方式拿到每一个miscdeviceconst struct miscdevice *p list_entry(v, struct miscdevice, list)拿到p之后就可以直接访问p-minor、p-name等字段了。list_entry本身只是container_of的简单包装真正的工作由container_of完成#define container_of(ptr, type, member) ({ \ const typeof( ((type *)0)-member ) *__mptr (ptr); \ (type *)( (char *)__mptr - offsetof(type,member) );})这个宏看起来相当奇特我们从左到右拆解它的三个关键点。1. 花括号表达式整个语句块的值等于最后一个表达式的值container_of被一对花括号包起来里面有两个表达式。这是 GCC 的语句表达式statement expression特性编译器会依次执行花括号内的所有语句并把最后一个表达式的值作为整个语句表达式的值返回。例如#include stdio.h int main() { int i 0; printf(i %d\n, ({i; i;})); return 0; }最终会打印2——两个i依次执行最后一个表达式的值2被作为结果传出。2. typeof返回变量/表达式的类型typeof是 GCC 扩展作用正如其名返回给定变量或表达式的类型。container_of第一行中的typeof(((type *)0)-member)表示type类型结构体的member成员的类型再配合const声明出一个与ptr同类型的指针__mptr。这一行并不是实现上必需的但它承担了类型检查的重任如果传入的ptr不是struct list_head *编译器会给出类型不兼容的告警同时((type *)0)-member会强制编译器检查type中确实存在名为member的成员从而大大提升代码的鲁棒性。3. 零偏移技巧与 offsetof从成员地址反推结构体起始地址container_of中最令人困惑的是那个0。它其实是零基地址技巧把地址0强制转换为type *再取它的member成员地址得到的值恰好就是member在type中的字节偏移。用一个简单的例子验证#include stdio.h struct s { int field1; char field2; char field3; }; int main() { printf(%p\n, ((struct s*)0)-field3); return 0; }由于int field1占 4 字节、char field2占 1 字节偏移 4field3的偏移就是0x5程序输出的正是0x5。offsetof宏标准 C 也提供就是这一技巧的官方化表达#define offsetof(TYPE, MEMBER) ((size_t) ((TYPE *)0)-MEMBER)于是container_of的第二行逻辑就很清晰了先用offsetof算出member相对于结构体起始地址的偏移再从member的地址__mptr中减去这个偏移得到的就是宿主结构体的起始地址。最后把它强制转换成type *返回。总结只要知道宿主结构体的类型type、list_head成员的名字member以及该成员的地址ptrcontainer_of就能通过一次减法运算反推出整个结构体的起始地址。这也是侵入式链表得以工作的基石——链表只需要维护指针数据永远可以通过成员偏移算回来。container_of在内核中的应用远不止链表。例如在 SyncPrim/linux-sync-4.md 中互斥锁的慢路径处理函数就是通过container_of从锁状态变量反推出整个mutex结构体的。完整的 list_head API 全景list_add和list_entry远不是linux/list.h的全部。Linux 内核的双向链表实现还提供了以下常用 APIAPI功能list_add在链表头之后插入新节点头插法list_add_tail在链表头之前、即链表尾部插入新节点尾插法list_del将节点从链表中摘除list_replace用一个新节点替换链表中的旧节点list_move将节点从原位置移动到另一条链表list_is_last判断节点是否为链表最后一个节点list_empty判断链表是否为空即头节点自指list_cut_position从链表的指定位置切出一段list_splice将一条链表拼接到另一条链表中list_for_each遍历链表中的每一个节点得到的是list_head *list_for_each_entry遍历链表并直接得到每一个宿主结构体指针其中list_add_tail与list_add是对称的它调用__list_add(new, head-prev, head)即把新节点插入到链表头节点的前驱也就是链表的真正末尾与链表头之间从而实现 FIFO 式的追加。list_del则通过__list_del(entry-prev, entry-next)把前后两个节点直接互链、跳过当前节点。遍历方面list_for_each直接操作list_head *指针而更常用的是list_for_each_entry它在循环内部自动组合list_entry即container_of让使用者直接拿到宿主结构体#define list_for_each_entry(pos, head, member) \ for (pos list_entry((head)-next, typeof(*pos), member); \ pos-member ! (head); \ pos list_entry(pos-member.next, typeof(*pos), member))循环从链表头的next出发取出第一个宿主结构体直到再次回到链表头为止。list_entry与list_for_each_entry配合正是内核代码中遍历设备链表、进程链表、等待队列等最典型的写法。内核各子系统中的实际用法佐证list_head双向链表遍布内核各个子系统本仓库的多个主题文章都直接依赖它可以交叉印证其通用性信号量的等待队列struct semaphore内嵌struct list_head wait_list用于组织所有等待获取信号量的进程down/up等操作正是围绕这条链表展开的参见 SyncPrim/linux-sync-3.md进程地址空间管理init_mm的mmlist链表把所有内存描述符串在一起参见 Initialization/linux-initialization-5.md调度器任务组根任务组通过children/siblings链表管理任务组之间的层级关系参见 Initialization/linux-initialization-8.md工作队列work_struct通过内嵌的entry链表节点挂入工作队列参见 Interrupts/linux-interrupts-9.mdRCU 与基数树radix_tree_node中的private_list也是list_head参见 DataStructures/linux-datastructures-2.md。使用 list_head 的注意事项在实际使用内核链表时有几点需要特别留意链表操作本身不是原子操作list_add、list_del这类接口只是一组指针赋值多个 CPU 并发修改同一链表时必须借助自旋锁等同步原语保护。正如 SyncPrim/linux-sync-1.md 等章节所讨论的内核中链表操作几乎总是与锁配合使用例如misc_register内部就用自旋锁保护misc_list的插入与遍历。空链表头必须自指无论是LIST_HEAD(name)静态定义还是INIT_LIST_HEAD(node)动态初始化next与prev都必须指向自身否则list_empty与遍历宏的判断就会失效。container_of依赖成员偏移list_entry的正确性建立在member确实是宿主结构体中的list_head成员这一前提上传错成员名或类型会得到未定义行为好在container_of第一行的类型检查能帮助提前发现大部分错误。小结Linux 内核通过struct list_head实现了一种通用的侵入式双向链表节点只保存next/prev指针数据通过成员嵌入与container_of的偏移运算与之关联。以杂项字符驱动的misc_list为例我们完整走通了定义链表头LIST_HEAD→ 初始化节点INIT_LIST_HEAD→ 插入节点list_add/__list_add→ 反向取回宿主结构体list_entry/container_of→ 遍历list_for_each_entry的全部环节。这套设计让链表操作与数据类型彻底解耦成为内核中组织对象集合的事实标准。本仓库 DataStructures/linux-datastructures-1.md 是该主题的原始出处后续还可继续阅读 基数树 与 位数组了解内核数据结构的全貌。赞分享【免费下载链接】linux-insides-zhLinux 内核揭秘项目地址https://gitcode.com/hust-open-atom-club/linux-insides-zh点击查看免费下载相关推荐Linux 内核揭秘交换空间Swap内存扩展的实现原理Linux 内核揭秘交换空间Swap内存扩展的实现原理 在Linux系统中当物理内存RAM不足时内核需要一种机制来扩展可用内存。交换空间Swa文档教程操作系统Linux 内核揭秘内核解压缩实现zImage 与 bzImage 的解压过程Linux 内核揭秘内核解压缩实现zImage 与 bzImage 的解压过程 为什么内核需要压缩 你是否曾经好奇为什么几 MB 的 Linux 内核镜文档教程操作系统Linux 内核揭秘实时内核RT_PREEMPT低延迟补丁的实现Linux 内核揭秘实时内核RT_PREEMPT低延迟补丁的实现 实时内核的价值与应用场景 在工业自动化、机器人控制、音频处理等领域系统对响应时间的要文档教程操作系统上一篇Agent Zero 框架扩展开发完全指南从 a0-development 技能到源码级实践下一篇RemoveWindowsAI 一键移除 Windows 11 Copilot Recall 完整实操指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
