第5章 内核表示法（Kernel Data Structures）

一、导读

1.1 本章学习目标

理解 Linux 内核中链表（linked list）的独特侵入式设计及其优势

掌握 list_head 结构体的使用方法和容器宏（container_of）的原理

了解内核中队列（queue）的实现方式和应用场景

深入理解基数树（radix tree）的工作原理及其在内核中的应用

掌握红黑树（red-black tree）的概念及其在 CFS 调度器和 VMA 管理中的使用

了解哈希表（hash table）在内核中的实现和 RCU 安全的哈希操作

理解内核数据结构设计中"机制与策略分离"的原则

能够根据具体场景选择合适的数据结构

1.2 为什么本章如此重要

数据结构是算法和系统实现的基石。Linux 内核作为一个大型软件项目，广泛使用了各种数据结构来组织和管理系统资源。然而，内核中的数据结构设计与用户空间的标准库有着显著的不同。内核不使用指针数组或通用的容器库，而是采用了一种独特的"侵入式"设计——将数据结构节点嵌入到目标结构体中，而非相反。

这种设计选择有着深刻的技术原因。内核代码对性能要求极高，任何不必要的间接引用和内存分配都可能成为瓶颈。侵入式设计消除了动态内存分配的开销（节点随宿主结构体一起分配），提高了缓存局部性（相关数据在内存中更靠近），并允许一个结构体同时属于多个链表。理解这些数据结构的设计思想，对于阅读内核源码至关重要，因为它们是内核实现的"基础设施"。

1.3 核心问题引导

为什么内核不使用标准库中的链表实现（如 C++ 的 std::list）？

list_head 的侵入式设计有什么优势？一个结构体如何同时属于多个链表？

container_of 宏是如何通过链表节点指针找到宿主结构体的？它的原理是什么？

基数树与哈希表相比有什么优势？它适用于什么场景？

红黑树为什么被用于 CFS 调度器？它的自平衡特性带来了什么保证？

内核中的哈希表如何处理并发访问？RCU 安全的哈希操作是如何实现的？

什么是"机制与策略分离"？这种设计原则如何体现在内核数据结构中？

如何根据具体需求选择合适的数据结构？

二、核心概念详解

5.1 侵入式链表（Intrusive Linked List）

Linux 内核的链表实现是内核数据结构设计的经典案例。与传统链表不同，内核的链表并不在节点中包含数据，而是将链表节点嵌入到数据结构中。链表节点由 list_head 结构体表示：

struct list_head {
    struct list_head *next, *prev;
};

双向链表的头节点通常嵌入到管理结构体中，而每个数据项通过在自己的结构体中包含 list_head 成员来加入链表。例如：

struct task_struct {
    // ... 其他字段
    struct list_head tasks;  // 进程链表节点
    // ...
};

要从链表节点的指针获取宿主结构体的指针，内核使用 list_entry() 宏（底层是 container_of 宏）。container_of 的原理是：已知结构体中某个成员的指针，通过计算该成员在结构体中的偏移量，反推出结构体的起始地址。这通过 offsetof 宏实现：

#define list_entry(ptr, type, member) \
    ((type *)((char *)(ptr) - (unsigned long)(&((type *)0)->member)))

这种设计的优势包括：第一，通用性——一个 list_head 可以用于任何结构体类型；第二，一个结构体可以包含多个 list_head 成员，同时属于多个链表（例如，一个进程可以同时在全局进程链表和某个进程组链表中）；第三，节点随宿主结构体一起分配，无需额外的内存分配操作；第四，提高了缓存局部性，因为链表节点和宿主数据在内存中相邻。

内核提供了丰富的链表操作函数：list_add() 在头部插入、list_add_tail() 在尾部插入、list_del() 删除节点、list_empty() 检查链表是否为空、list_for_each() 遍历链表、list_for_each_entry() 直接遍历宿主结构体。还有原子操作的变体 list_del_rcu() 等，用于 RCU 保护的并发场景。

5.2 基数树（Radix Tree）

基数树（也叫 Patricia trie 或 radix tree）是一种空间优化的 trie 结构，用于将整数键（通常是索引或 ID）映射到指针。在内核中，基数树主要用于页面缓存（page cache）——将文件偏移量（以页面为单位）映射到对应的内存页面。

基数树的核心思想是将键的二进制表示按位分段，每一段对应树的一层。例如，如果基数为 2^6 = 64，则每个节点有 64 个子节点指针，键的每 6 位索引一个子节点。对于 32 位键，树的最大深度为 ceil(32/6) = 6 层。查找操作从根节点开始，逐层根据键的相应位段向下遍历，直到叶子节点。

基数树相比哈希表的优势在于：第一，有序性——基数树天然保持键的有序性，支持范围查询（如查找某个文件偏移范围内的所有缓存页面）；第二，无冲突——不需要处理哈希冲突；第三，稀疏性——基数树可以高效地处理稀疏的键空间，空的子树不分配节点。

在内核中，基数树还用于 IDA（ID Allocator）子系统，为设备、文件描述符等分配唯一的整数 ID。较新的内核版本中，部分基数树的使用正在被 XArray 取代，XArray 提供了更安全、更易用的 API。

5.3 红黑树（Red-Black Tree）

红黑树是一种自平衡二叉搜索树，保证树的高度始终为 O(log N)，从而保证查找、插入和删除操作的时间复杂度为 O(log N)。红黑树通过给每个节点着色（红色或黑色）并维护一组平衡规则来实现自平衡：

每个节点要么是红色要么是黑色

根节点是黑色

每个叶子节点（NIL）是黑色

如果一个节点是红色，则它的两个子节点都是黑色（不能有连续的红色节点）

从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点

这些规则保证了最长路径不超过最短路径的两倍，从而维持了树的近似平衡。

在内核中，红黑树用于多个关键场景：CFS 调度器使用红黑树按 vruntime 排序所有可运行进程；虚拟内存区域（VMA）使用红黑树管理进程的地址空间映射；文件系统（如 ext3/ext4）使用红黑树管理目录项和扩展属性；epoll 使用红黑树管理监听的文件描述符集合。

内核中的红黑树实现定义在 <linux/rbtree.h> 中，同样采用侵入式设计。用户需要在其结构体中包含 rb_node 成员，并提供比较函数。内核还提供了 augmented rbtree 的变体，允许在每个节点上维护额外的聚合信息。

5.4 哈希表（Hash Table）

哈希表提供了平均 O(1) 的查找时间，是内核中使用最广泛的数据结构之一。内核的哈希表实现采用链地址法（chaining）处理冲突：每个桶（bucket）是一个链表的头，哈希到同一个桶的元素通过链表串联。

内核提供了 DEFINE_HASHTABLE() 宏来定义静态哈希表，以及 hash_add()、hash_del()、hash_for_each() 等操作函数。哈希表广泛应用于各种内核子系统：inode 缓存、dentry 缓存、进程组查找、网络连接的连接跟踪表等。

在并发环境中，哈希表需要特殊的处理。传统的做法是在每个桶上放置一把锁（桶锁），允许不同桶的操作并发进行。更现代的做法是使用 RCU（Read-Copy-Update）机制，使得读操作完全无锁。RCU 安全的哈希表允许读取者在没有持有任何锁的情况下遍历链表，写入者通过"先添加新节点、等待旧读取者退出、再删除旧节点"的方式保证正确性。

三、深入分析与讨论

3.1 container_of 宏的底层原理

container_of 是内核中最精巧的宏之一。它的实现看似简单，却涉及 C 语言中一些深层的特性。宏的核心是计算成员在结构体中的偏移量：

#define container_of(ptr, type, member) ({          \
    const typeof(((type *)0)->member) *__mptr = (ptr); \
    (type *)((char *)__mptr - offsetof(type, member)); })

offsetof(type, member) 通过 &((type *)0)->member 计算成员相对于结构体起始地址的偏移量。这里将地址 0 强制转换为结构体指针，然后取成员的地址，得到的就是偏移量。虽然访问地址 0 在运行时会导致段错误，但 offsetof 只在编译时计算，不会生成运行时代码。

container_of 的安全性通过 typeof 检查来保证：如果传入的指针类型与成员类型不匹配，编译器会产生类型不兼容的警告。这种编译时类型检查是内核代码安全性的重要保障。

3.2 数据结构选择的设计考量

内核数据结构的选择体现了"机制与策略分离"的设计原则。内核提供通用的数据结构（如链表、红黑树、哈希表），但不规定它们的使用策略。例如，链表本身不决定元素的排序方式，排序策略由使用者决定。这种分离使得数据结构可以被广泛应用于不同的场景。

选择数据结构时需要权衡多个因素：查找频率（高频查找适合哈希表或红黑树）、插入/删除频率（频繁插入删除适合链表）、有序性需求（需要有序遍历则选择红黑树或基数树）、并发访问模式（读多写少适合 RCU 保护的结构）。

四、实践案例

4.1 案例一：编写内核模块使用链表

编写一个内核模块，定义一个包含 list_head 成员的结构体，动态创建多个实例并加入链表，然后遍历链表打印每个元素的信息，最后清理链表并释放内存。通过这个练习，可以深入理解侵入式链表的使用方法和 list_for_each_entry() 等遍历宏的使用。

4.2 案例二：分析 /proc 中的数据结构使用

通过阅读内核源码，分析 /proc 文件系统的实现中使用了哪些数据结构。例如，进程列表使用双向链表（task_struct 的 tasks 字段），/proc 目录的查找使用哈希表（pid hash table），文件描述符表使用基数树（或较新内核中的 XArray）。理解这些数据结构的选择原因，有助于掌握数据结构设计的实践智慧。

五、常见误区与注意事项

误区：侵入式链表比非侵入式链表更快。侵入式链表的优势不在于单个操作的速度，而在于减少了内存分配次数和提高了缓存局部性。在元素数量很少的场景下，差异可能不明显。

误区：container_of 可以在运行时用于任意指针转换。container_of 要求传入的指针确实指向结构体的指定成员。如果指针类型不匹配，结果将是未定义行为。编译器只能检查类型兼容性，无法检查运行时指针的正确性。

误区：红黑树总是比哈希表好。红黑树保证 O(log N) 的查找时间，而哈希表平均 O(1)。在不需要有序性的场景中，哈希表通常更快。红黑树的优势在于有序性和最坏情况的保证。

注意：链表遍历时的安全性。使用 list_for_each() 遍历时，如果在循环体中删除当前节点，会导致链表指针混乱。应使用 list_for_each_safe() 或 list_for_each_entry_safe()，它们预先保存下一个节点的指针。

注意：RCU 保护的链表操作有特殊要求。在 RCU 保护的链表中，删除节点后不能立即释放内存，必须等待一个宽限期（grace period）后才能释放，以确保所有读取者已经完成遍历。

六、本章小结

本章介绍了 Linux 内核中常用的数据结构及其设计思想。侵入式链表是内核最基础的数据结构，通过将链表节点嵌入到目标结构体中，实现了通用性和高效性的统一。container_of 宏是侵入式设计的核心，通过偏移量计算实现从成员指针到宿主结构体指针的转换。基数树用于整数键到指针的有序映射，广泛应用于页面缓存。红黑树提供 O(log N) 的自平衡搜索，用于调度器、虚拟内存管理等关键场景。哈希表提供平均 O(1) 的快速查找，配合 RCU 机制支持高并发访问。理解这些数据结构的设计原理和使用场景，是阅读和理解内核源码的基础。

七、思考题与练习

实现一个简单的内核模块，使用 list_head 创建一个双向链表，支持插入、删除和遍历操作。

分析 container_of 宏的实现，解释为什么 &((type *)0)->member 可以计算偏移量而不会导致段错误。

比较基数树和哈希表在页面缓存场景下的优劣。为什么内核选择基数树（而非哈希表）来管理页面缓存？

画出红黑树的五种平衡规则，并解释为什么这些规则能保证树的高度为 O(log N)。

研究 XArray 的设计目标和 API，说明它相比基数树有哪些改进。

分析 list_for_each() 和 list_for_each_safe() 的区别，编写一个在遍历中删除节点的示例。

在内核源码中找到一个使用哈希表的实例，分析它的哈希函数和并发控制机制。

讨论"机制与策略分离"原则在内核数据结构中的体现，举出至少三个例子。