Linux 内核中的数据结构：基数树（Radix Tree）原理与 API 详解

基数树（Radix Tree）是 Linux 内核提供的一种高效「关键字-值」映射数据结构，被广泛应用于页缓存管理、中断描述符查找等关键子系统。本篇以 linux-insides-zh 仓库中的《基数树》文档为主体，结合内核初始化与中断子系统的实际使用场景，系统讲解基数树的数据结构定义、初始化方式与核心 API，帮助读者掌握这一内核数据结构的底层原理与实战用法。

基数树：压缩之后的 Trie

Linux 内核通过许多不同的库与函数提供各种数据结构及算法实现，基数树（Radix tree）就是其中之一。简单来说，Radix tree 是一种「压缩 trie」，而 trie（字典树）是一种通过保存关联数组（associative array）来提供「关键字-值（key-value）」存储与查找的数据结构。通常关键字是字符串，不过也可以是其他数据类型，Linux 内核中的 Radix 树就将值映射为整型关键字。

trie 结构的节点与普通的 n-tree（n 叉树）不同，其节点中并不存储关键字，取而代之的是存储单个字符标签。关键字查找时，通过从树的根开始遍历关键字相关的所有字符标签节点，直至到达最终的叶子节点。下面是一个典型例子：

               +-----------+
               |           |
               |    " "    |
               |           |
          +----+-----------+----+
          |                    |
          |                    |
     +----v------+        +----v-----+
     |           |        |          |
     |     g     |        |    c     |
     |           |        |          |
     +-----------+        +----------+
          |                    |
          |                    |
     +----v------+        +----v-----+
     |           |        |          |
     |     o     |        |    a     |
     |           |        |          |
     +-----------+        +----------+
                                   |
                                   |
                              +----v-----+
                              |          |
                              |    t     |
                              |          |
                              +----------+

这个例子中，我们可以看到一个 trie 所存储的关键字信息 go 与 cat。压缩 trie（即 radix tree）与普通 trie 所不同的是，所有只存在单个孩子的中间节点都会被压缩——这正是它名字中「radix（基数）」的由来：以共享前缀为基数对路径进行合并，从而大幅降低树的高度与内存开销。这种特性使得基数树特别适合存储稀疏的长整型关键字集合，例如内核中用到的页面号（page index）。

内核中的基数树核心结构

Linux 内核中与 radix tree 实现和 API 相关的文件主要有两个：

• include/linux/radix-tree.h（头文件，定义数据结构与宏）
• lib/radix-tree.c（实现文件，提供各 API 函数）

radix_tree_root：树的根节点

radix 树的数据结构定义在 include/linux/radix-tree.h 文件中，根节点结构体如下：

struct radix_tree_root {
        unsigned int            height;
        gfp_t                   gfp_mask;
        struct radix_tree_node  __rcu *rnode;
};

上面这个是 radix 树的 root 节点的结构体，它包含三个成员：

• height —— 从叶节点向上计算出的树高度。
• gfp_mask —— 内存分配标识（flags）。
• rnode —— 指向根子节点的指针。

注意 rnode 成员的类型带有 __rcu 标记，这说明内核基数树对节点的访问走的是 RCU（Read-Copy-Update）机制，读者可以无锁并发访问，而写者通过 RCU 延迟释放节点，这也是基数树能被页缓存、中断描述符等高频读路径广泛采用的重要原因。

gfp_mask：内存申请行为标识

这里我们先讨论结构体成员 gfp_mask：Linux 底层的内存申请接口需要提供一类标识（flag）——gfp_mask，用于描述内存申请的行为。这个以 GFP_ 前缀开头的内存申请控制标识主要包括：

• GFP_NOIO —— 禁止所有 IO 操作，但允许睡眠等待内存。
• __GFP_HIGHMEM —— 允许申请内核的高端内存。
• GFP_ATOMIC —— 高优先级申请内存，且操作不允许被睡眠。

在实际使用时，GFP_NOIO | __GFP_HIGHMEM 这类组合也常见于基数树使用者，表示「可以进行高端内存分配、但绝不能触发 IO 回写」的场景。gfp_mask 会被保存在根节点中，树在内部需要分配新节点时，会把这个掩码透传给底层分配器，从而保证整棵树的分配行为一致。

radix_tree_node：树的中间节点

radix 树的节点结构体同样定义在 include/linux/radix-tree.h 中：

struct radix_tree_node {
        unsigned int    path;
        unsigned int    count;
        union {
                struct {
                        struct radix_tree_node *parent;
                        void *private_data;
                };
                struct rcu_head rcu_head;
        };
        /* For tree user */
        struct list_head private_list;
        void __rcu      *slots[RADIX_TREE_MAP_SIZE];
        unsigned long   tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
};

这个结构体包含以下几类内容：节点与父节点的偏移以及到树底端的高度、子节点的个数、节点的存储数据域，具体描述如下：

• path —— 本节点与父节点的偏移以及到树底端的高度。
• count —— 子节点的个数。
• parent —— 父节点的指针。
• private_data —— 存储数据内容缓冲区。
• rcu_head —— 用于节点释放的 RCU 链表头，配合 RCU 机制延迟回收节点。
• private_list —— 供树使用者（tree user）挂接私有数据的链表。

slots 与 tags：数据指针槽位与状态标签

结构体 radix_tree_node 的最后两个成员 tags 与 slots 非常重要，需要特别注意：

• slots[RADIX_TREE_MAP_SIZE]：每个 Radix 树节点都可以包含一个指向存储数据指针的 slots 集合，空闲 slots 的指针指向 NULL。RADIX_TREE_MAP_SIZE 定义了单个节点拥有的槽位数（典型值为 64），每个 slot 要么指向下一级节点，要么指向使用者存入的数据。
• tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS]：Linux 内核的 Radix 树结构体中还包含用于记录节点存储状态的标签 tags 成员，标签通过位设置指示 Radix 树的数据存储状态。例如内核页缓存用它标记「页是否脏（dirty）」「页是否正在写回（writeback）」，从而实现基于标签的批量扫描，而无需遍历每个 slot 逐一判断。

这种「slot 指针数组 + tags 位图」的设计，让基数树同时具备路径压缩、RCU 并发读和标签快速筛选三种能力。

初始化：两种方式

Linux 内核基数树支持两种方式初始化。

方式一：宏 RADIX_TREE

第一种方式是使用宏 RADIX_TREE：

RADIX_TREE(name, gfp_mask);

只需要提供 name 参数，就能够使用 RADIX_TREE 宏完成 radix 树的定义以及初始化，RADIX_TREE 宏的实现非常简单：

#define RADIX_TREE(name, mask) \
        struct radix_tree_root name = RADIX_TREE_INIT(mask)

#define RADIX_TREE_INIT(mask)   { \
        .height = 0,              \
        .gfp_mask = (mask),       \
        .rnode = NULL,            \
}

RADIX_TREE 宏首先使用 name 定义了一个 radix_tree_root 实例，并用 RADIX_TREE_INIT 宏带参数 mask 进行初始化。宏 RADIX_TREE_INIT 将 radix_tree_root 初始化为默认属性（height 为 0、rnode 为 NULL），并将 gfp_mask 初始化为入参 mask。由于使用了指定初始化器（designated initializer），该宏适用于定义阶段即完成初始化的静态/全局树。

方式二：先定义再初始化

第二种方式是手工定义 radix_tree_root 变量，之后再使用 mask 调用 INIT_RADIX_TREE 宏对变量进行初始化：

struct radix_tree_root my_radix_tree;
INIT_RADIX_TREE(my_tree, gfp_mask_for_my_radix_tree);

INIT_RADIX_TREE 宏定义：

#define INIT_RADIX_TREE(root, mask)  \
do {                                 \
        (root)->height = 0;          \
        (root)->gfp_mask = (mask);   \
        (root)->rnode = NULL;        \
} while (0)

宏 INIT_RADIX_TREE 所初始化的属性与 RADIX_TREE_INIT 一致（height = 0、gfp_mask = mask、rnode = NULL），区别在于前者面向「已经定义好的变量」执行就地初始化，因此可以用于运行期动态创建的树。

核心 API：插入、删除与查找

插入与删除

接下来是 radix 树的节点插入以及删除，对应两个函数：

• radix_tree_insert
• radix_tree_delete

第一个函数 radix_tree_insert 需要三个入参：

1. radix 树 root 节点结构；
2. 索引关键字；
3. 需要插入存储的数据。

第二个函数 radix_tree_delete 除了不需要存储数据参数外，其他与 radix_tree_insert 一致——即传入 root 结构与索引关键字即可删除对应条目。从源码结构看，radix_tree_insert 在插入过程中会根据关键字的位数逐层创建缺失的中间节点，并在路径上的每个节点递增 count，而 radix_tree_delete 则在删除后递减 count，当某节点 count 归零且不再需要时会被回收。

查找

radix 树的查找实现有以下三个函数：

• radix_tree_lookup
• radix_tree_gang_lookup
• radix_tree_lookup_slot

第一个函数 radix_tree_lookup 需要两个参数：

1. radix 树 root 节点结构；
2. 索引关键字。

这个函数通过给定的关键字查找 radix 树，并返回关键字所对应的结点（即存入的数据指针）。

第二个函数 radix_tree_gang_lookup 具有以下特征：

unsigned int radix_tree_gang_lookup(struct radix_tree_root *root,
                                    void **results,
                                    unsigned long first_index,
                                    unsigned int max_items);

函数返回查找到记录的条目数，并根据关键字进行排序，返回的总结点数不超过入参 max_items 的大小。gang（批量）查找非常适合一次取回一段连续关键字区间的所有条目，避免逐条调用 radix_tree_lookup 的开销。

最后一个函数 radix_tree_lookup_slot 返回结点 slot 中所存储的数据（即指向 slot 位置的指针）。与 radix_tree_lookup 返回数据本身不同，它返回的是 slot 的地址，配合 RCU 语义可以在不重查的情况下原地替换 slot 内容。

内核中的实际应用：从启动到中断子系统

启动阶段的 radix_tree_init

在内核初始化流程中，基数树子系统会显式地完成自身初始化。参见仓库中 Initialization/linux-initialization-9.md（RCU 初始化一节）：在 trace_init（追踪子系统初始化）之后，紧跟着调用 radix_tree_init。该函数定义于 lib/radix-tree.c，负责初始化 radix 树内部所需的缓存（如节点内存缓存），为后续各子系统使用基数树做好准备。由此可见，基数树属于内核启动早期就必须就绪的基础设施之一。

中断描述符树：irq_desc_tree

基数树在内核中最典型的应用之一是中断子系统对中断描述符（irq_desc）的管理。参见仓库中 Interrupts/linux-interrupts-7.md（深入外部硬件中断）：

在启用 CONFIG_SPARSE_IRQ 的情况下，内核通过 irq_desc_tree（一棵基数树）来组织中断描述符，树的关键字是中断号（IRQ number），值是对应的 irq_desc 结构。early_irq_init 中通过循环逐个分配描述符并插入到树中：

for (i = 0; i < initcnt; i++) {
    desc = alloc_desc(i, node, NULL);
    set_bit(i, allocated_irqs);
    irq_insert_desc(i, desc);
}

其中 irq_insert_desc(i, desc) 本质上就是把中断号 i 作为关键字、desc 作为值插入基数树。由于 x86 平台中断号可能非常稀疏（如 NR_IRQS 可达数千而实际使用的只有几百个，dmesg 中可见 NR_IRQS:4352 nr_irqs:488），基数树「按关键字位路径压缩、稀疏存储」的特性恰好能避免为不存在的中断号浪费内存，同时保证按中断号查找描述符的时间复杂度可控。

更广阔的用途

从源码结构看，基数树还广泛用于：

• 页缓存（page cache）：以文件页号（page index）为关键字，映射到 struct page 指针，并利用 tags 位图标记脏页/写回页；
• 内存管理：用于跟踪特定范围内已分配/未分配的页帧；
• 文件系统：用于快速定位 inode 与块号等映射关系。

读者可以将 Interrupts/linux-interrupts-7.md 与 Initialization/linux-initialization-9.md 结合本文一起阅读，形成「数据结构定义 → 初始化 → API 使用 → 子系统落地」的完整知识链路。

小结

基数树是 Linux 内核中一款「小而精」的数据结构：它以压缩 trie 的形态实现了整型关键字到指针的高效映射，通过 slots 存储数据、tags 记录状态、RCU 保证并发读安全，并通过 RADIX_TREE/INIT_RADIX_TREE 两种方式灵活初始化。围绕它提供的 radix_tree_insert、radix_tree_delete、radix_tree_lookup、radix_tree_gang_lookup 与 radix_tree_lookup_slot 构成了完整的使用面。从启动早期的 radix_tree_init，到中断子系统按中断号组织 irq_desc 的 irq_desc_tree，基数树贯穿了内核众多关键路径，理解它的结构与 API，是深入研读内核源码的重要基石。本系列其余内容可参见 DataStructures/README.md，其中还包含双向链表（linux-datastructures-1.md）与位数组（linux-datastructures-3.md）等数据结构的讲解。