什么是嵌入式数据结构？
在讨论具体的数据结构之前，我们首先要理解“嵌入式”（Embedded）或“侵入式”（Intrusive）这个概念在内核中的含义。
- 常规数据结构（非侵入式）：比如你在大学 C 语言课程中学到的链表，通常会定义一个链表节点，这个节点包含一个数据指针
void* data和一个next指针。当你想要把你的数据（比如一个struct student）放入链表时，你需要先为struct student分配内存，再为链表节点分配内存，然后让节点的data指针指向你的学生结构体。数据被“装”在数据结构的容器里。 - 嵌入式数据结构（侵入式）：Linux 内核反其道而行之。它不创建单独的节点容器，而是要求你直接将数据结构的“连接件”（如
next/prev指针）嵌入到你自己的数据结构中。
一个形象的比喻：
想象一下你有许多不同类型的货物（你的数据结构，如进程、文件、内存区域等），你想把它们用链条连起来。
- 常规方法：你制造了很多标准尺寸的“集装箱”（链表节点），每个集装箱里面可以放一件货物。然后你把这些集装箱连起来。缺点是：你不仅要管理货物，还要管理一堆集装箱，浪费空间和精力。
- 嵌入式方法：你在设计每件货物的时候，就在其上预留了标准的“挂钩”或“连接环”（数据结构的连接件）。这样，任何类型的货物，只要有这种标准挂钩，就可以直接相互连接起来，形成一条链。这种方式更高效，因为货物和连接件是一体的。
这种设计的核心优势是：
- 内存效率高：只需要为你的业务数据结构分配一次内存，连接件作为其一部分，无需额外分配。
- 灵活性强：同一个数据结构可以嵌入多个不同的“连接件”，从而同时加入到多个不同的链表或树中。
- 性能好：数据和连接件在内存中是连续的，这大大提高了 CPU 缓存的命中率。
现在，我们来看内核中最经典的几种嵌入式数据结构。
1. 内核双向循环链表 (struct list_head)
这是 Linux 内核中使用最广泛、最基础的嵌入式数据结构。
形象说明
它就是我们上面比喻中提到的“标准连接环”。这个连接环本身非常简单，只包含两个指针：一个指向下一个（next），一个指向上一个（prev）。
// a/include/linux/list.h
struct list_head {
struct list_head *next, *prev;
};它自身不包含任何数据。它就像乐高积木上的“凸点”和“凹槽”，是用来连接的标准件。
在内核中如何应用？
- 嵌入：当内核开发者定义一个需要被链式管理的数据结构时，会直接在结构体内部放一个
struct list_head成员。 例如，内核中描述一个进程的task_struct结构体：struct task_struct { // ... 大量关于进程状态、内存、信号等的信息 int pid; char comm[TASK_COMM_LEN];struct list_head tasks; // <--- “连接环”在这里！ // ... 更多信息};这里的tasks就是一个连接环，用来将所有进程连接成一个双向循环链表。 - “魔法”般的
container_of宏：现在问题来了，当你遍历链表，拿到一个struct list_head的指针时，如何找到包含它的那个更大的task_struct结构体的起始地址呢？ 答案是container_of(ptr, type, member)宏。这是一个 C 语言指针运算的绝技。 形象说明container_of：
想象你手里拿着一节火车车厢的“连接器”（list_head指针），你知道这节车厢是“餐车”（task_struct类型），也知道连接器在车厢的什么位置（比如在车厢正中间，tasks成员名）。那么你就可以通过“连接器的地址”减去“连接器在车厢内的偏移量”，从而精确计算出“餐车车厢的起始位置”（task_struct的起始地址）。
具体应用场景
- 进程管理：全局的
init_task作为链表头，所有的task_struct通过其tasks成员连接成一个巨大的进程链表。当需要遍历所有进程时（如ps命令的底层实现），就会遍历这个链表。 - 虚拟内存区域 (VMA)：每个进程的内存空间由多个
vm_area_struct(VMA) 描述，例如代码段、数据段、堆、栈等。这些 VMA 在mm_struct结构体中通过一个链表连接起来，方便按顺序访问。 - 文件系统：已加载的文件系统（
struct super_block）被组织在一个链表中。打开的文件描述符、各种缓存（dentry cache, inode cache）也大量使用链表来管理。
2. 红黑树 (struct rb_root, struct rb_node)
红黑树是一种自平衡的二叉查找树，用于高效的查找、插入和删除操作。
形象说明
如果说链表是一个“线性队列”，那么红黑树就是一个“高效的、自动整理的图书馆索引系统”。
你每放一本新书（插入一个节点），这个系统都会自动调整（旋转、变色），确保从任何一个入口查找任何一本书都非常快（时间复杂度为 O(log n)），不会因为书架的一边书太多而导致查找缓慢。
rb_node 就像是每本书上贴的“索引标签”，上面有指向“父标签”、“左子标签”和“右子标签”的信息，以及一个“颜色”（红色或黑色）标记。
// include/linux/rbtree.h
struct rb_node {
unsigned long __rb_parent_color;
struct rb_node *rb_right;
struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));
struct rb_root {
struct rb_node *rb_node;
};在内核中如何应用？
应用方式与链表类似：
- 嵌入：在需要被红黑树管理的数据结构中嵌入一个
struct rb_node。 - 查找与提取：使用
rb_search、rb_insert_color等函数操作树。当找到一个rb_node后，同样使用container_of宏来获得父结构体的地址。
一个数据结构可以同时拥有 list_head 和 rb_node，这意味着它可以同时存在于一个链表和一个红黑树中，服务于不同的访问需求。
具体应用场景
- 虚拟内存区域 (VMA) 管理：这是最经典的例子。一个进程的 VMA 不仅通过链表连接（用于顺序遍历），还通过一个
rb_node组织成红黑树。当发生缺页中断，需要快速查找某个地址属于哪个 VMA 时，就会在红黑树上进行查找，这比遍历链表快得多。 - CFS 调度器 (Completely Fair Scheduler)：CFS 是 Linux 的默认进程调度器。它使用红黑树来管理所有可运行的进程。树的键（key）是进程的“虚拟运行时间”（vruntime）。调度器总是选择树中最左边的节点（vruntime 最小的进程）来运行，从而保证了公平性。
- 高精度定时器 (hrtimers)：内核用红黑树来管理定时器事件，按它们的到期时间排序。这样，内核可以快速找到下一个即将到期的定时器。
3. 基数树 (Radix Tree)
基数树是一种特殊的树形数据结构，非常适合用于将整数索引（特别是稀疏的）映射到指针。
形象说明
把它想象成一个“多级导航的电话号码簿”或一个“巨大的公寓楼”。
假设你要找 85739 这个号码对应的指针。
- 你先根据第一位数字
8，进入第 8 大卷。 - 在第 8 卷里，根据第二位数字
5，找到第 5 章。 - 在第 5 章里，根据第三位数字
7，找到第 7 节…
…以此类推，直到最终找到存储指针的那个位置。
基数树是按索引值的二进制位（bit）来分层的，所以查找速度极快，且与树中元素的数量无关，只与索引的位数有关。它非常节省空间，因为如果某个分支下面没有条目，那么对应的子树就不会被创建。
在内核中如何应用？
与前两者不同，基数树通常不要求你在数据结构中嵌入节点。它是一个独立的管理器，负责维护 unsigned long 类型的索引和 void * 指针之间的映射关系。
具体应用场景
- 页缓存 (Page Cache)：这是基数树最核心的应用。当内核从文件中读取数据时，会将数据页（
struct page）缓存起来。一个文件的address_space结构体中就有一个基数树，它建立了文件内的偏移量（页索引）到内存中的struct page指针之间的映射。当需要再次访问文件的某个位置时，内核通过这个基制树快速查找对应的缓存页是否存在。 - IDR/IDA (ID Reservation)：内核需要为各种资源（如块设备、字符设备）分配唯一的、小整数 ID。IDR (ID Radix tree) 和 IDA (ID Allocator) 机制就使用基数树来管理这些 ID 的分配和查找，确保能高效地将一个整数 ID 映射到对应的资源指针。
总结
| 数据结构 | 形象比喻 | 核心作用 | 典型内核应用场景 |
|---|---|---|---|
双向循环链表 (list_head) | 火车车厢的“标准连接环” | 顺序遍历、添加、删除元素 | 进程列表、VMA列表、驱动程序队列 |
红黑树 (rb_node) | 自我整理的“图书馆索引系统” | 快速查找、插入、删除 (O(log n)) | VMA快速地址查找、CFS调度器、高精度定时器 |
基数树 (radix_tree) | 多级导航的“电话号码簿” | 稀疏整数索引到指针的高效映射 | 页缓存 (Page Cache)、IDR/IDA 分配 |