优享资讯 | Linux Kernel：内核数据结构之基数树（Radix Tree）

掘金后端 ( ) • 2024-06-05 11:22

Linux Kernel：内核数据结构之基数树（Radix Tree）

highlight: monokai theme: smartblue

本文采用 Linux 内核 v3.10 版本 x86_64架构

一、基数树简介

1.1 前缀树（Trie）

Trie，又称为前缀树（prefix tree）或字典树，是一种 k 路搜索树，用来在一组集合中搜索特定的键。这些键通常是字符串，但也可以是其它数据类型。在前缀树中，可以为键保存对应的值，这些值通常保存在叶子节点。

与二叉搜索树不同的是，前缀树的节点并不保存完整的键，而是保存单个字符。要想获得节点对应的键，需要按照深度优先原则，从根节点遍历到对应节点，将遍历路径上每个节点的字符连接起来。

在实现上，每个节点有一个数组，节点中的字符通常是隐式存储的。

以下图为例，每个节点有一个数组，数组的索引对应着 a ~ z 这 26 个不同的字符，数组的成员指向下一层节点（如果有的话）。在叶子节点上，存储着键对应的值，比如键 she 对应着数值 0，键 sells 对应数值 1，键 sea 对应数值 2。

上图引用自维基百科Trie。

1.2 基数树（Radix Tree）

基数树（Radix Tree）也称为压缩前缀树（compact prefix tree）或 compressed trie，是一种更节省空间的前缀树。在基数树中，当父节点只有一个子节点时，子节点会合并到父节点。

基数树中的基 r，表示每个节点最多可以拥有 r 个子节点，其中 r 是 2 的 $x$ 次幂，$x \geq 1$。

基数树示例如下：

上图引用自维基百科Radix tree。

1.3 内核中的基数树

Linux 内核中，基数树的键（或者说索引）为整数类型，其相关的数据结构和接口主要在 2 个文件中：

include/linux/radix-tree.h
lib/radix-tree.c

二、数据结构

2.1 radix_tree_root

// file: include/linux/radix-tree.h
/* root tags are stored in gfp_mask, shifted by __GFP_BITS_SHIFT */
struct radix_tree_root {
unsigned intheight;
gfp_tgfp_mask;
struct radix_tree_node__rcu *rnode;
};

基数树的树根由结构体radix_tree_root 表示，它包含 3 个成员：

height -- 树的高度
gfp_mask -- 内存分配标识
rnode -- 指向下一层的 radix_tree_node 节点（如果有的话）

2.2 radix_tree_node

// file: lib/radix-tree.c
struct radix_tree_node {
unsigned intheight;/* Height from the bottom */
unsigned intcount;
union {
struct radix_tree_node *parent;/* Used when ascending tree */
struct rcu_headrcu_head;/* Used when freeing node */
};
void __rcu*slots[RADIX_TREE_MAP_SIZE];
unsigned longtags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
};

除根节点外，基数树的其它节点使用结构体 radix_tree_node 来表示。该结构体包含如下字段：

height -- 从最底层到当前层的高度
count -- 子节点数量
parent -- 指向父节点的指针
slots -- 指针数组

如果当前节点为位于树的最底层，则数组中的指针指向数据；否则，指向下一级节点。

2.2.1 宏 RADIX_TREE_MAP_SIZE / RADIX_TREE_MAP_SHIFT

宏RADIX_TREE_MAP_SIZE 表示基数树中的基数大小，该宏最终扩展为 64，即每个节点最多可以有 64 个子节点，其定义如下：

// file: lib/radix-tree.c
#define RADIX_TREE_MAP_SIZE(1UL << RADIX_TREE_MAP_SHIFT)// 1 << 6

宏RADIX_TREE_MAP_SIZE 又引用了宏 RADIX_TREE_MAP_SHIFT，该宏表示基数对应着 2 的多少次幂，其定义如下：

// file: lib/radix-tree.c
#define RADIX_TREE_MAP_SHIFT(CONFIG_BASE_SMALL ? 4 : 6)// 6

宏 RADIX_TREE_MAP_SHIFT 的扩展依赖于宏 CONFIG_BASE_SMALL ，在我们的案例中，该宏扩展为 0：

// file: include/generated/autoconf.h
#define CONFIG_BASE_SMALL 0

CONFIG_BASE_SMALL 对应着内核配置参数 BASE_SMALL ，该值是另一个内核配置参数 BASE_FULL 的反数，即当 BASE_FULL 为 1 时，该值为 0；否则，该值为 1：

// file: init/Kconfig
config BASE_SMALL
int
default 0 if BASE_FULL
default 1 if !BASE_FULL

BASE_FULL 指示内核是否使用全尺寸的数据结构，默认值为 1。当机器的内存较小时（比如嵌入式系统），可以选择 0 以节省内存，但会降低性能。

// file: init/Kconfig
config BASE_FULL
default y
bool "Enable full-sized data structures for core" if EXPERT
help
  Disabling this option reduces the size of miscellaneous core
  kernel data structures. This saves memory on small machines,
  but may reduce performance.

在我们的案例中，BASE_FULL 使用了默认值 1，所以 CONFIG_BASE_SMALL 的值为 0；宏 RADIX_TREE_MAP_SHIFT 扩展为 6；RADIX_TREE_MAP_SIZE 扩展为 1 << 6 ，即 64。

所以，slots 是一个包含 64 个指针的数组。也就是说，每个节点最多有 64 个子节点（中间节点），或者最多包含 64 条数据（底层节点）。

tags -- 一个二维数组，也是一个位图数组，用来标记基数树中所存储数据的状态。

其中，宏RADIX_TREE_MAX_TAGS 扩展为 3：
```
// file: include/linux/radix-tree.h
#define RADIX_TREE_MAX_TAGS 3
```
表示 tags 中包含 3 个位图，每个位图的比特位数量就是 slots 数组的成员数量，即每个比特位对应着 slots 数组中的一个成员。

宏 RADIX_TREE_TAG_LONGS用于将比特位数量转换成 unsigned long 成员数量并向上圆整，该宏定义如下：
```
// file: lib/radix-tree.c
#define RADIX_TREE_TAG_LONGS\
((RADIX_TREE_MAP_SIZE + BITS_PER_LONG - 1) / BITS_PER_LONG)
```
其中，宏 RADIX_TREE_MAP_SIZE 和BITS_PER_LONG 都扩展为 64：
```
// file: include/asm-generic/bitsperlong.h
#define BITS_PER_LONG 64
```
最终，tags 是一个有着 3 个成员的数组，每个成员又是一个位图，位图中的每个比特位对应着 slots 数组中的一个元素的状态。

由于 tags 中有 3 个位图，所以基数树最多可以为每个数据保存 3 种状态。

2.2.2 tags 说明

在普通的基数树中，我们只需要对数据本身进行查询、添加、删除等操作。但是在内核中，还有一种需求就是获取特定状态的数据。

以页高速缓（Page Cache）存为例。由于页的状态可能是脏页（PG_dirty），当我们要批量查找页高速缓存中的脏页时，如果要遍历整个基数树顺序访问所有的叶子节点（页描述符）就太慢了。相反，为了能快速搜索脏页，基数树中的每个中间节点都包含一个针对每个子节点（或叶子节点）的脏位标记，当至少有一个子节点的脏位标记被置位时，此标志被置位。通过这种方式，当内核遍历基数树搜索脏页时，就可以跳过脏位标记为 0 的中间节点的所有子树：中间节点的脏位标记为 0 说明其子树中的所有页描述符都不是脏的。

同样的想法应用到了PG_writeback 标记，该标记表示页正在被写回磁盘。

这样，为基数树的每个节点引入了两个页描述符的标记：PG_dirty 和 PG_writeback。每个节点的 tags 字段中使用了 2 个 64 位的数组（即位图）来存放这两个标记，tags[0] 数组是脏位标记，而 tags[1] 数组是写回标记。

2.3 height_to_maxindex

height_to_maxindex是一个静态 unsigned long 数组，数组的下标对应着树的高度，值对应着该高度下的基数树所能表示的最大索引值。

// file: lib/radix-tree.c
/*
 * The height_to_maxindex array needs to be one deeper than the maximum
 * path as height 0 holds only 1 entry.
 */
static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH + 1] __read_mostly;

该数组容量为 RADIX_TREE_MAX_PATH + 1。

2.3.1 宏 RADIX_TREE_MAX_PATH / RADIX_TREE_INDEX_BITS

宏 RADIX_TREE_MAX_PATH 表示搜索路径的最大高度，其定义如下：

// file: lib/radix-tree.c
#define RADIX_TREE_MAX_PATH (DIV_ROUND_UP(RADIX_TREE_INDEX_BITS, \
  RADIX_TREE_MAP_SHIFT))

其中宏 RADIX_TREE_INDEX_BITS表示每个索引值所占用的比特位数量，在 64 位模式下，该宏扩展为 64，其定义如下：

#define RADIX_TREE_INDEX_BITS  (8 /* CHAR_BIT */ * sizeof(unsigned long))

宏 RADIX_TREE_MAP_SHIFT 扩展为 6（见上文）。

宏 DIV_ROUND_UP 用于计算 RADIX_TREE_INDEX_BITS 对于 RADIX_TREE_MAP_SHIFT 的倍数，并向上圆整，其定义如下：

// file: include/linux/kernel.h
#define DIV_ROUND_UP(n,d) (((n) + (d) - 1) / (d))

在 x86-64 系统下，宏 RADIX_TREE_INDEX_BITS 扩展为 64，所以宏 RADIX_TREE_MAX_PATH 最终扩展为 11。也就是说，在满高度的基数树中搜索一个键，最多需要遍历 11 个节点。数组 height_to_maxindex 的成员数量为 RADIX_TREE_MAX_PATH + 1，之所以加 1，是因为要加上树根 root 层（第 0 层）。在 x86-64 系统下，第一层的子结点数量最大为 $2^4 = 16$ 个，而不是 $2^6 = 64$ 个。

2.3.2 初始化 -- radix_tree_init_maxindex()

数组 height_to_maxindex 在 radix_tree_init_maxindex() 函数中被初始化。

// file: lib/radix-tree.c
static __init void radix_tree_init_maxindex(void)
{
unsigned int i;

for (i = 0; i < ARRAY_SIZE(height_to_maxindex); i++)
height_to_maxindex[i] = __maxindex(i);
}

2.3.2.1 宏 ARRAY_SIZE()

宏 ARRAY_SIZE() 计算数组的成员数量，并检查参数是否数组指针，其定义如下：

// file: include/linux/kernel.h
#define ARRAY_SIZE(arr) (sizeof(arr) / sizeof((arr)[0]) + __must_be_array(arr))

它的实现很简单，就是通过 sizeof 获取整个数组的大小，然后除以单个数组元素的大小。

宏 __must_be_array() 用来检查入参是否数组指针。如果不是，在编译时就会报错；如果是，__must_be_array(arr) 的结果为 0，不会影响 ARRAY_SIZE() 的计算结果。该宏定义如下：

// file: include/linux/compiler-gcc.h
/* &a[0] degrades to a pointer: a different type from an array */
#define __must_be_array(a) BUILD_BUG_ON_ZERO(__same_type((a), &(a)[0]))

其中，宏 __same_type()定义如下：

// file: include/linux/compiler.h
# define __same_type(a, b) __builtin_types_compatible_p(typeof(a), typeof(b))

__builtin_types_compatible_p 是 gcc 编译器的内建函数，它用于判断一个变量的类型是否为某指定的类型，假如是就返回 1，否则返回 0。

在这里，会比较指针和指针指向的第一个元素的地址是否相同类型来判断是否为数组。如果是数组的话，数组指针和指向数组首元素的指针是不同类型，__same_type() 的值为 0；否则，为 1。

比如数组 int arr[] = {1, 2, 3, 4, 5} 中， arr 是 int[5] 类型，而 &arr[0] 是 int * 类型。

宏BUILD_BUG_ON_ZERO() 定义如下：

// file: include/linux/bug.h
/* Force a compilation error if condition is true, but also produce a
   result (of value 0 and type size_t), so the expression can be used
   e.g. in a structure initializer (or where-ever else comma expressions
   aren't permitted). */
#define BUILD_BUG_ON_ZERO(e) (sizeof(struct { int:-!!(e); }))

当入参为 1 时，结构体的位域字段大小为 -1，会导致编译时错误；当入参为 0 时，sizeof 操作符的计算结果为 0。

2.3.2.2 __maxindex()

radix_tree_init_maxindex() 函数遍历数组，调用 __maxindex() 函数为数组的每个成员赋值。

// file: lib/radix-tree.c
static __init unsigned long __maxindex(unsigned int height)
{
unsigned int width = height * RADIX_TREE_MAP_SHIFT;
int shift = RADIX_TREE_INDEX_BITS - width;

if (shift < 0)
return ~0UL;
if (shift >= BITS_PER_LONG)
return 0UL;
return ~0UL >> shift;
}

由于每层能容纳的子节点数量为 2 的 RADIX_TREE_MAP_SHIFT（扩展为 6）次方（即 64），所以正常情况下，高度为 height 的树，能够容纳$(2^{RADIX_TREE_MAP_SHIFT})^{height}$ 个数据，也就是 $2^{height * RADIX_TREE_MAP_SHIFT}$ 个数据，即 $2^{width}$ 个数据，那么最大索引值就是 $2^{width} - 1$ 。

但是，计算机中使用移位操作效率更高，所以内核使用移位操作来计算。那么，问题转换成计算移位的位数。最容易想到的是使用 (1UL << width) -1 来计算最大索引，但是里面会有减法操作。内核使用了纯的位操作，避免了算术操作。宏 RADIX_TREE_INDEX_BITS（扩展为 64）表示索引的比特位数；而 width 表示当前高度下，所能使用的索引位数；两者之差即为所要移位的位数，即 shift。所以，正常情况下，~0UL >> shift 就计算出当前高度下的最大索引值。

除了正常情况，还有 2 个例外。

第一个，就是高度为 0 时，也就是只有根节点而没有任何子节点。此时树高 height 为 0，通过计算 width 值为 0，shift 为 64，而最大索引值为 0，即满足代码中的 shift >= BITS_PER_LONG 的条件。

另外一个，是索引本身位数的限制。由于索引是 RADIX_TREE_INDEX_BITS （扩展为 64）位的，所以理论上基数树最多可存储 2 的 RADIX_TREE_INDEX_BITS 次方（$2^{64}$）个数据，所以最大索引值就是 $2^{64}-1$。此时，height 的临界值为 11，且第一层的 64 个槽位，只使用了 $2^{4}$ = 16 个。也就是说，由于索引自身位数的限制，基数树只需要 11 层（不包含 root 层）就可以保存所有的索引值。即使 height 再高，也没有意义。当 height >= 11 时，shift 小于 0，即满足 shift < 0 的条件时，索引已用满，此时索引的最大值为 $2^{64}-1$，是由索引自身位数限制的。

不同高度的基数树对应的最大索引值：

基数树高度最大索引值 0 0 1 $2^{6}$ -1 = 63 2 $2^{12}$ -1 = 4 095 3 $2^{18}$ -1 = 262 143 4 $2^{24}$-1 = 16 777 215 5 $2^{30}$ -1 = 1 073 741 823 6 $2^{36}$ -1 7 $2^{42}$ -1 8 $2^{48}$ -1 9 $2^{54}$ -1 10 $2^{60}$ -1 11 $2^{64}$ -1

2.4 radix_tree_preloads

radix_tree_preloads 是个 per-cpu 变量，也就是说每个 CPU 都有一份该变量的副本。其定义如下：

// file: lib/radix-tree.c
static DEFINE_PER_CPU(struct radix_tree_preload, radix_tree_preloads) = { 0, };

这是一个 radix_tree_preload 结构体类型的变量，是为节点预分配的缓存池：

// file: lib/radix-tree.c
/*
 * Per-cpu pool of preloaded nodes
 */
struct radix_tree_preload {
int nr;
struct radix_tree_node *nodes[RADIX_TREE_PRELOAD_SIZE];
};

radix_tree_preload 结构体包括 2 个成员：

nr -- 剩余可分配的成员数量
nodes -- 节点指针数组。

其中，宏 RADIX_TREE_PRELOAD_SIZE表示数组的大小，该宏定义如下：

// file: lib/radix-tree.c
/*
 * The radix tree is variable-height, so an insert operation not only has
 * to build the branch to its corresponding item, it also has to build the
 * branch to existing items if the size has to be increased (by
 * radix_tree_extend).
 *
 * The worst case is a zero height tree with just a single item at index 0,
 * and then inserting an item at index ULONG_MAX. This requires 2 new branches
 * of RADIX_TREE_MAX_PATH size to be created, with only the root node shared.
 * Hence:
 */
#define RADIX_TREE_PRELOAD_SIZE (RADIX_TREE_MAX_PATH * 2 - 1)

在 x86-64 架构下，宏 RADIX_TREE_MAX_PATH 扩展为 11，所以 RADIX_TREE_PRELOAD_SIZE 扩展为 21。

从注释中不难看出，缓存池中的节点数量 RADIX_TREE_PRELOAD_SIZE （扩展为 21）是按照最坏情况考虑的，即需要一次性分配 21 个节点的内存。什么情况下要一次性分配这么多节点呢？就是在基数树高度为 0 且只有一个索引为 0 的数据的情况下，要插入一个最大索引 ULONG_MAX 的数据。此时，两条路径都要扩展到最大高度。

2.4.1 缓存池的初始化 - radix_tree_preload()

变量 radix_tree_preloads 通过 radix_tree_preload() 函数进行初始化，该函数定义如下：

// file: lib/radix-tree.c
/*
 * Load up this CPU's radix_tree_node buffer with sufficient objects to
 * ensure that the addition of a single element in the tree cannot fail.  On
 * success, return zero, with preemption disabled.  On error, return -ENOMEM
 * with preemption not disabled.
 *
 * To make use of this facility, the radix tree must be initialised without
 * __GFP_WAIT being passed to INIT_RADIX_TREE().
 */
int radix_tree_preload(gfp_t gfp_mask)
{
struct radix_tree_preload *rtp;
struct radix_tree_node *node;
int ret = -ENOMEM;

preempt_disable();
rtp = &__get_cpu_var(radix_tree_preloads);
while (rtp->nr < ARRAY_SIZE(rtp->nodes)) {
preempt_enable();
node = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask);
if (node == NULL)
goto out;
preempt_disable();
rtp = &__get_cpu_var(radix_tree_preloads);
if (rtp->nr < ARRAY_SIZE(rtp->nodes))
rtp->nodes[rtp->nr++] = node;
else
kmem_cache_free(radix_tree_node_cachep, node);
}
ret = 0;
out:
return ret;
}

radix_tree_preload() 函数的实现也非常简单。

先是通过 __get_cpu_var() 函数获取到 per-cpu 变量 radix_tree_preloads 的地址并保存到变量 rtp 中；然后遍历数组 rtp->nodes，调用kmem_cache_alloc() 函数为数组的每个成员分配内存；分配成功后，将内存地址存储到数组成员中。

其中，宏 ARRAY_SIZE用于计算数组的大小，上文已经介绍过了。

kmem_cache_alloc() 函数用于在 slab 分配器上分配内存。

preempt_disable() 和 preempt_enable() 这两个函数，用于关闭和开启抢占。

关于 slab 分配器和抢占相关的内容，本文不会深入讲解。

2.5 基数树示意图

如果树中的索引不大于 63，那么树的深度就等于 1，因为可能存在的 64 个叶子可以都存放在第一层的节点中。

如果保存的数据索引大于 63，比如 131 ，那么树的高度就增加为 2，这样基数树可以查找的最大索引为 4095 。

三、接口函数

3.1 基数树的创建

创建基数树有 2 种方法：宏 RADIX_TREE 及 INIT_RADIX_TREE。

3.1.1 宏 RADIX_TREE

// file: include/linux/radix-tree.h
#define RADIX_TREE(name, mask) \
struct radix_tree_root name = RADIX_TREE_INIT(mask)

宏 RADIX_TREE 接收 2 个参数：

name -- 基数树的名称
mask -- 请求内存时所用的标志掩码

其内部又调用了 RADIX_TREE_INIT 宏，该宏定义如下：

// file: include/linux/radix-tree.h
#define RADIX_TREE_INIT(mask){\
.height = 0,\
.gfp_mask = (mask),\
.rnode = NULL,\
}

3.1.2 宏 INIT_RADIX_TREE

// file: include/linux/radix-tree.h
#define INIT_RADIX_TREE(root, mask)\
do {\
(root)->height = 0;\
(root)->gfp_mask = (mask);\
(root)->rnode = NULL;\
} while (0)

宏 INIT_RADIX_TREE 接收 2 个参数：

root -- 基数树的根节点
mask -- 请求内存时所用的标志掩码

3.2 间接指针相关函数

当 root->rnode 指向 radix_tree_node结构而不是数据项时，被称为间接指针（indirect pointer）。间接指针通过将 root->rnode 的最低位设置为 1 来标识。内核文件对此说明如下：

// file: include/linux/radix-tree.h
/*
 * An indirect pointer (root->rnode pointing to a radix_tree_node, rather
 * than a data item) is signalled by the low bit set in the root->rnode
 * pointer.
 *
 * In this case root->height is > 0, but the indirect pointer tests are
 * needed for RCU lookups (because root->height is unreliable). The only
 * time callers need worry about this is when doing a lookup_slot under
 * RCU.
 *
 * Indirect pointer in fact is also used to tag the last pointer of a node
 * when it is shrunk, before we rcu free the node. See shrink code for
 * details.
 */

3.2.1 radix_tree_is_indirect_ptr()

radix_tree_is_indirect_ptr() 函数用来检测给定的指针是否为间接指针，其定义如下：

// file: include/linux/radix-tree.h
static inline int radix_tree_is_indirect_ptr(void *ptr)
{
return (int)((unsigned long)ptr & RADIX_TREE_INDIRECT_PTR);
}

其中宏 RADIX_TREE_INDIRECT_PTR 定义如下：

// file: include/linux/radix-tree.h
#define RADIX_TREE_INDIRECT_PTR1

radix_tree_is_indirect_ptr() 函数的实现非常简单，就是将给定指针与常量 1 进行按位与运算，并返回计算结果。如果结果为 0，说明指针最低位为 0，不是间接指针；如果结果为 1，说明指针最低位为 1，是间接指针。

3.2.2 ptr_to_indirect()

ptr_to_indirect() 函数将给定指针转换成间接指针。

// file: lib/radix-tree.c
static inline void *ptr_to_indirect(void *ptr)
{
return (void *)((unsigned long)ptr | RADIX_TREE_INDIRECT_PTR);
}

3.2.3 indirect_to_ptr()

indirect_to_ptr() 函数将间接指针转换成普通指针。

// file: lib/radix-tree.c
static inline void *indirect_to_ptr(void *ptr)
{
return (void *)((unsigned long)ptr & ~RADIX_TREE_INDIRECT_PTR);
}

3.3 标记相关函数

3.3.1 root_gfp_mask()

root_gfp_mask() 函数用来获取根节点中的页分配标识。当基数树需要为新增节点分配内存时，会以此作为分配标识。 GFP 是 Get Free Page 的缩写。

// file: lib/radix-tree.c
static inline gfp_t root_gfp_mask(struct radix_tree_root *root)
{
return root->gfp_mask & __GFP_BITS_MASK;
}

在基数树中，普通节点有一个专门的字段 tags 来存储状态标记，但根节点没有对应的字段，它的标记存储在 gfp_mask 字段中。在 gfp_mask 中，低 25 位（位 0 ~ 24）已经被占用，对应着页分配的不同标识。从位 25 开始的其余位，可用于其它用途。

// file: include/linux/gfp.h
/* Plain integer GFP bitmasks. Do not use this directly. */
#define ___GFP_DMA0x01u
#define ___GFP_HIGHMEM0x02u
#define ___GFP_DMA320x04u
#define ___GFP_MOVABLE0x08u
#define ___GFP_WAIT0x10u
#define ___GFP_HIGH0x20u
#define ___GFP_IO0x40u
#define ___GFP_FS0x80u
#define ___GFP_COLD0x100u
#define ___GFP_NOWARN0x200u
#define ___GFP_REPEAT0x400u
#define ___GFP_NOFAIL0x800u
#define ___GFP_NORETRY0x1000u
#define ___GFP_MEMALLOC0x2000u
#define ___GFP_COMP0x4000u
#define ___GFP_ZERO0x8000u
#define ___GFP_NOMEMALLOC0x10000u
#define ___GFP_HARDWALL0x20000u
#define ___GFP_THISNODE0x40000u
#define ___GFP_RECLAIMABLE0x80000u
#define ___GFP_KMEMCG0x100000u
#define ___GFP_NOTRACK0x200000u
#define ___GFP_NO_KSWAPD0x400000u
#define ___GFP_OTHER_NODE0x800000u
#define ___GFP_WRITE0x1000000u
/* If the above are modified, __GFP_BITS_SHIFT may need updating */

所以，要想获取 gpf 的标识，只需获取 root->gfp_mask 的低 25 位即可。

宏 __GFP_BITS_MASK 用作获取 gpf 标识的掩码，该宏扩展为 $(1 << 25) - 1$ ，其定义如下：

// file: include/linux/gfp.h
#define __GFP_BITS_MASK ((__force gfp_t)((1 << __GFP_BITS_SHIFT) - 1))

#define __GFP_BITS_SHIFT 25/* Room for N __GFP_FOO bits */

其中，gfp_t 类型是 unsigned 类型的别名。

// file: include/linux/gfp.h
typedef unsigned __bitwise__ gfp_t;

3.3.2 root_tag_get()

基数树中，每项数据可以存储 3 种标记。root_tag_get() 函数用于获取根节点中指定标记的状态。

该函数接收 2 个参数：

root -- 根节点
tag -- 标记类型，一共有 0 ~ 2 共三种类型，对应着 radix_tree_node->tags 的索引。

// file: lib/radix-tree.c
static inline int root_tag_get(struct radix_tree_root *root, unsigned int tag)
{
return (__force unsigned)root->gfp_mask & (1 << (tag + __GFP_BITS_SHIFT));
}

宏 __GFP_BITS_SHIFT 扩展为 25：

// file: include/linux/gfp.h
#define __GFP_BITS_SHIFT 25/* Room for N __GFP_FOO bits */

从上文已经知道，在 gfp_mask 中，低 25 位（位 0 ~ 24）对应着页分配的不同标识，从位 25 开始，可用于其它用途。

在此处，第 25 ~ 27 位，用作基数树根节点的标记位。

radix tree_root_gfp_mask.png

所以，想要获取指定 tag 类型标记，只需获取 root->gfp_mask 中第 tag + __GFP_BITS_SHIFT 位的值即可。 root_tag_get() 函数通过按位与操作，实现此功能。

3.3.3 root_tag_set()

static inline void root_tag_set(struct radix_tree_root *root, unsigned int tag)
{
root->gfp_mask |= (__force gfp_t)(1 << (tag + __GFP_BITS_SHIFT));
}

root_tag_set() 函数，通过按位或操作，将根节点中指定 tag 类型的标记置位。

3.3.4 root_tag_clear()

static inline void root_tag_clear(struct radix_tree_root *root, unsigned int tag)
{
root->gfp_mask &= (__force gfp_t)~(1 << (tag + __GFP_BITS_SHIFT));
}

root_tag_clear() 函数，将根节点中指定 tag 类型的标记清除。

3.3.5 root_tag_clear_all()

static inline void root_tag_clear_all(struct radix_tree_root *root)
{
root->gfp_mask &= __GFP_BITS_MASK;
}

root_tag_clear_all() 函数，将根节点中的 tag 标记全部清除，只保留 gpf 标识。

3.3.6 tag_set()

// file: lib/radix-tree.c
static inline void tag_set(struct radix_tree_node *node, unsigned int tag,
int offset)
{
__set_bit(offset, node->tags[tag]);
}

tag_set() 函数调用位图接口 __set_bit()，将中间节点指定 tag 类型标记的位图中 offset 处的比特位设置为 1。

关于位图的详细内容，请参考Linux Kernel：内核数据结构之位图（Bitmap）。

3.3.7 tag_get()

static inline int tag_get(struct radix_tree_node *node, unsigned int tag,
int offset)
{
return test_bit(offset, node->tags[tag]);
}

tag_get() 函数调用位图接口 test_bit() ，获取中间节点指定 tag 类型标记的位图中 offset 处比特位的值。

3.3.8 any_tag_set()

any_tag_set() 函数检查指定节点中是否有特定类型的标记被置位。如果任何一个比特位的标记被置位，该函数返回 1；否则，返回 0。

该函数接收 2 个参数：

node -- 基数树节点
tag -- 标记类型

/*
 * Returns 1 if any slot in the node has this tag set.
 * Otherwise returns 0.
 */
static inline int any_tag_set(struct radix_tree_node *node, unsigned int tag)
{
int idx;
for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) {
if (node->tags[tag][idx])
return 1;
}
return 0;
}

该函数的实现非常简单。遍历标记对应的数组，如果任何一个数组成员不为 0，则说明有标记被置位，返回 1；否则，返回 0。

宏 RADIX_TREE_TAG_LONGS 表示位图数组大小。

3.3.9 radix_tree_tag_clear()

// file: lib/radix-tree.c
/**
 *radix_tree_tag_clear - clear a tag on a radix tree node
 *@root:radix tree root
 *@index:index key
 *@tag: tag index
 *
 *Clear the search tag (which must be < RADIX_TREE_MAX_TAGS)
 *corresponding to @index in the radix tree.  If
 *this causes the leaf node to have no tags set then clear the tag in the
 *next-to-leaf node, etc.
 *
 *Returns the address of the tagged item on success, else NULL.  ie:
 *has the same return value and semantics as radix_tree_lookup().
 */
void *radix_tree_tag_clear(struct radix_tree_root *root,
unsigned long index, unsigned int tag)
{
struct radix_tree_node *node = NULL;
struct radix_tree_node *slot = NULL;
unsigned int height, shift;
int uninitialized_var(offset);

height = root->height;
if (index > radix_tree_maxindex(height))
goto out;

shift = height * RADIX_TREE_MAP_SHIFT;
slot = indirect_to_ptr(root->rnode);

while (shift) {
if (slot == NULL)
goto out;

shift -= RADIX_TREE_MAP_SHIFT;
offset = (index >> shift) & RADIX_TREE_MAP_MASK;
node = slot;
slot = slot->slots[offset];
}

if (slot == NULL)
goto out;

while (node) {
if (!tag_get(node, tag, offset))
goto out;
tag_clear(node, tag, offset);
if (any_tag_set(node, tag))
goto out;

index >>= RADIX_TREE_MAP_SHIFT;
offset = index & RADIX_TREE_MAP_MASK;
node = node->parent;
}

/* clear the root's tag bit */
if (root_tag_get(root, tag))
root_tag_clear(root, tag);

out:
return slot;
}

radix_tree_tag_clear() 函数将索引查找路径上相关节点的标记清除，该函数接收 3 个参数：

root -- 基数树的根节点
index -- 索引
tag -- 标记类型

如果索引 index 对应的数据的标记被置位，该函数返回对应数据的指针；否则，返回 NULL。

struct radix_tree_node *node = NULL;
struct radix_tree_node *slot = NULL;
unsigned int height, shift;
int uninitialized_var(offset);

首先，声明了一批变量，其中 node 和 slot 被初始化为 NULL。其中，node

height = root->height;
if (index > radix_tree_maxindex(height))
goto out;

如果指定的索引值超出当前高度所能表示的最大索引，说明该索引不存在，直接跳转到 out 标签处。

out:
return slot;

out 标签处，会返回 slot 的值，此时 slot 为 NULL。

shift = height * RADIX_TREE_MAP_SHIFT;
slot = indirect_to_ptr(root->rnode);

计算初始位偏移 shift 并将 slot 转换成普通指针。

while (shift) {
if (slot == NULL)
goto out;

shift -= RADIX_TREE_MAP_SHIFT;
offset = (index >> shift) & RADIX_TREE_MAP_MASK;
node = slot;
slot = slot->slots[offset];
}

接下来是一个 while 循环，从 rnode 节点开始，从上向下逐层查找。在循环中，node 指向父节点，slot 指向子节点。正如我们 3.4.2 节所介绍的，每降低一层，shift 的值就会减少 RADIX_TREE_MAP_SHIFT。offset 计算出 index 对应的当前层的槽位。如果 shift 不为 0 时，slot 为 NULL ，说明要查找的索引不存在，不需要清除标记，直接跳转到 out 标签处执行。

if (slot == NULL)
goto out;

如果查到到最底层，发现 slot 为 NULL，说明该索引没有对应的值，不需要清除标记，直接跳转到 out 标签处执行。

while (node) {
if (!tag_get(node, tag, offset))
goto out;
tag_clear(node, tag, offset);
if (any_tag_set(node, tag))
goto out;

index >>= RADIX_TREE_MAP_SHIFT;
offset = index & RADIX_TREE_MAP_MASK;
node = node->parent;
}

现在，我们已经来到了最底层节点。此时 node 指向最底层节点，slot 指向索引 index 对应的数据，offset 表示索引 index 对应数据在最底层节点的槽位。接下来要做的工作，就是从最底层节点开始，从底向上逐层清除标记，这是在 while 循环中完成的。

我们来看一下 while 循环所做的工作。

调用 tag_get() 函数获取 node 节点对应槽位的标记。如果该值为 0，说明不需要清除，直接跳转到 out 标签处执行。否则，继续执行下述工作。

调用 tag_clear() 函数清除对应槽位的标记。如果该节点中还有其它位置的标记被置位，则不需要处理上层节点了，清除工作结束，直接跳转到 out 标签处执行。

接下来，就是更新 offset 使其等于上一层的槽位，更新 node 使其指向父节点。

然后进入下一循环，开始处理上一层节点。

/* clear the root's tag bit */
if (root_tag_get(root, tag))
root_tag_clear(root, tag);

接下来处理 while 循环之后和 out 标签之间的代码。程序走到这里，说明到达了根节点，需要清除根节点的 tag 标记。

out:
return slot;

最后，到达 out 标签，返回 slot 的值。如果 index 对应的数据的标记被清除，返回该数据的指针；否则，返回 NULL。

3.3.10 radix_tree_tag_set()

radix_tree_tag_set() 函数将索引搜索路径上相关节点的标记置位。索引对应的数据必须存在，否则就是 bug。该函数会返回被打上标记的数据的地址。

/**
 *radix_tree_tag_set - set a tag on a radix tree node
 *@root:radix tree root
 *@index:index key
 *@tag: tag index
 *
 *Set the search tag (which must be < RADIX_TREE_MAX_TAGS)
 *corresponding to @index in the radix tree.  From
 *the root all the way down to the leaf node.
 *
 *Returns the address of the tagged item.   Setting a tag on a not-present
 *item is a bug.
 */
void *radix_tree_tag_set(struct radix_tree_root *root,
unsigned long index, unsigned int tag)
{
unsigned int height, shift;
struct radix_tree_node *slot;

height = root->height;
BUG_ON(index > radix_tree_maxindex(height));

slot = indirect_to_ptr(root->rnode);
shift = (height - 1) * RADIX_TREE_MAP_SHIFT;

while (height > 0) {
int offset;

offset = (index >> shift) & RADIX_TREE_MAP_MASK;
if (!tag_get(slot, tag, offset))
tag_set(slot, tag, offset);
slot = slot->slots[offset];
BUG_ON(slot == NULL);
shift -= RADIX_TREE_MAP_SHIFT;
height--;
}

/* set the root's tag bit */
if (slot && !root_tag_get(root, tag))
root_tag_set(root, tag);

return slot;
}

该函数接收 3 个参数：

root -- 基数树的根
index -- 索引
tag -- 标记类型

unsigned int height, shift;
struct radix_tree_node *slot;

height = root->height;
BUG_ON(index > radix_tree_maxindex(height));

如果索引 index 的值超出基数树的最大索引，这是内核 bug，调用 BUG_ON() 进行处理。

slot = indirect_to_ptr(root->rnode);
shift = (height - 1) * RADIX_TREE_MAP_SHIFT;

将 slot 初始化为 rnode 节点，shift 初始化为 rnode 节点对应的位偏移。

while (height > 0) {
int offset;

offset = (index >> shift) & RADIX_TREE_MAP_MASK;
if (!tag_get(slot, tag, offset))
tag_set(slot, tag, offset);
slot = slot->slots[offset];
BUG_ON(slot == NULL);
shift -= RADIX_TREE_MAP_SHIFT;
height--;
}

接下来是一个 while 循环。在循环内部，首先根据 shift 值计算出 index 对应的当前层槽位 offset；然后检查该槽位对应的标记，如果该槽位没有设置标记，则将对应的标记位置位。将 slot 指向下一层节点，如果该节点为 NULL，说明 index 路径上出现空缺，这是一个bug，调用 BUG_ON() 进行处理。再接着，更新 shift 的值为下一层位偏移，并将高度减一，进入下一层继续执行。

/* set the root's tag bit */
if (slot && !root_tag_get(root, tag))
root_tag_set(root, tag);

return slot;

最后，给根节点打上标记，并返回 slot 的值。

3.4 基数树相关函数

3.4.1 radix_tree_maxindex()

radix_tree_maxindex() 函数根据指定的高度，返回该高度下基数树所能表示的最大索引。

// file: lib/radix-tree.c
/*
 *Return the maximum key which can be store into a
 *radix tree with height HEIGHT.
 */
static inline unsigned long radix_tree_maxindex(unsigned int height)
{
return height_to_maxindex[height];
}

由于变量 height_to_maxindex 中存储了不同高度对应的最大索引值，这里直接获取即可。

3.4.2 radix_tree_lookup_element()

radix_tree_lookup_element() 查找指定索引 index 对应的元素。

// file: lib/radix-tree.c
/*
 * is_slot == 1 : search for the slot.
 * is_slot == 0 : search for the node.
 */
static void *radix_tree_lookup_element(struct radix_tree_root *root,
unsigned long index, int is_slot)
{
unsigned int height, shift;
struct radix_tree_node *node, **slot;

node = rcu_dereference_raw(root->rnode);
if (node == NULL)
return NULL;

if (!radix_tree_is_indirect_ptr(node)) {
if (index > 0)
return NULL;
return is_slot ? (void *)&root->rnode : node;
}
node = indirect_to_ptr(node);

height = node->height;
if (index > radix_tree_maxindex(height))
return NULL;

shift = (height-1) * RADIX_TREE_MAP_SHIFT;

do {
slot = (struct radix_tree_node **)
(node->slots + ((index>>shift) & RADIX_TREE_MAP_MASK));
node = rcu_dereference_raw(*slot);
if (node == NULL)
return NULL;

shift -= RADIX_TREE_MAP_SHIFT;
height--;
} while (height > 0);

return is_slot ? (void *)slot : indirect_to_ptr(node);
}

radix_tree_lookup_element() 函数接收 3 个参数：

root -- 基数树的根
index -- 索引值
is_slot -- 查找标识。0 - 返回数据指针；1 - 返回数据所在槽位的指针。

unsigned int height, shift;
struct radix_tree_node *node, **slot;

node = rcu_dereference_raw(root->rnode);
if (node == NULL)
return NULL;

在函数内部，首先通过 rcu_dereference_raw(root->rnode) 获取到指针 root->rnode。如果该值为 NULL，说明这是一颗空树，直接返回 NULL。

if (!radix_tree_is_indirect_ptr(node)) {
if (index > 0)
return NULL;
return is_slot ? (void *)&root->rnode : node;
}

接下来通过 radix_tree_is_indirect_ptr() 函数检测 root->rnode 是否间接指针。

如果不是间接指针，说明 root->rnode 直接指向数据项，此时只有一个数据，index 为 0。如果 index > 0，该索引对应的数据肯定是不存在的，所以直接返回 NULL；否则，根据 is_slot 的值返回不同的指针类型，当 is_slot 为真时，说明要返回是槽位指针，将 &root->rnode 转换成 void *类型返回；否则，说明要返回的是数据指针，直接返回 node，即 root->rnode。

接下来，处理 root->rnode 为间接指针的情况，即 root->rnode 指向中间节点。

node = indirect_to_ptr(node);

首先，将 node 转换成普通指针。此处， node 是根节点的子节点。

height = node->height;
if (index > radix_tree_maxindex(height))
return NULL;

通过 node->height 获取到树的高度，并赋值给变量 height。

通过 radix_tree_maxindex(height)获取到当前高度对应的最大索引值。如果给定的索引值 index 大于高度对应的最大索引值，说明要查找的索引超出当前高度能表示的范围，直接返回 NULL。

shift = (height-1) * RADIX_TREE_MAP_SHIFT;

在 x86-64架构：内存分页机制中，我们了解到在 4 级分页下，虚拟地址被分割成 5 个部分，每一部分表示不同层级的索引。为了方便计算每一层级的索引值，内核为他们定义了偏移量，如下图所示：

与线性地址转换类似，在基数树中，索引也会按照层数被分割成不同的部分，每一层也有着对应的位数。第 2 ~ 11 层，每层对应着 6 个比特位，第 1 层对应着 4 个（当树高度为 11 时）或 6 个（当树高度小于 11 时）比特位。同时，每一层也有着不同的偏移量，如下图所示：

radix tree_level.png

此处变量 shift 就用来表示偏移量。当前处于第 1 层，我们要获取到索引 index 中的最高的 6 位（或 4 位），所以位偏移为 (height-1) * RADIX_TREE_MAP_SHIFT。

do {
slot = (struct radix_tree_node **)
(node->slots + ((index>>shift) & RADIX_TREE_MAP_MASK));
node = rcu_dereference_raw(*slot);
if (node == NULL)
return NULL;

shift -= RADIX_TREE_MAP_SHIFT;
height--;
} while (height > 0);

接下来，通过 while 循环，从第一层开始，从上向下逐层进行查找。

宏 RADIX_TREE_MAP_MASK 是一个掩码，该掩码的低 6 位全为 1，其定义如下：

// file: lib/radix-tree.c
#define RADIX_TREE_MAP_MASK(RADIX_TREE_MAP_SIZE-1)

宏 RADIX_TREE_MAP_SIZE 扩展为 64（见上文）。

在查找的过程中，node 指向父节点，slot 指向子节点所在槽位。查找方式类似于虚拟地址到物理地址的转换。先从第一层开始，此时 node 是第一层的节点，node->slots 得到当前节点 slots 成员的地址，然后通过 (index>>shift) & RADIX_TREE_MAP_MASK) 获取到 index 在 slots 数组中的对应槽位，node->slots + ((index>>shift) & RADIX_TREE_MAP_MASK)就得到了该索引对应的 slots 数组成员的地址，并赋值给 slot，这是一个二级指针。然后调用 rcu_dereference_raw() 函数对指针 slot 解引用，获取到指向下一层节点的指针，并赋值给 node。如果 node == NULL，说明基数树中没有该索引对应的数据，直接返回 NULL。否则，执行 shift -= RADIX_TREE_MAP_SHIFT 及 height--，进入下一层继续搜索。

当 height 等于 0 时，搜索执行完毕，并找到了索引 index 对应的数据（未找到的话，会提前返回 NULL）。此时，slot 是数据所在槽位的地址，node 是指向数据的指针。

return is_slot ? (void *)slot : indirect_to_ptr(node);

最后，如果 is_slot为真，需要返回槽位 slot 的指针，则将 slot 转换成 (void *)类型的指针并返回；否则，表示要返回数据指针，则将 node 转换成普通指针并返回。

3.4.3 radix_tree_lookup()

// file: lib/radix-tree.c
/**
 *radix_tree_lookup    -    perform lookup operation on a radix tree
 *@root:radix tree root
 *@index:index key
 *
 *Lookup the item at the position @index in the radix tree @root.
 *
 *This function can be called under rcu_read_lock, however the caller
 *must manage lifetimes of leaf nodes (eg. RCU may also be used to free
 *them safely). No RCU barriers are required to access or modify the
 *returned item, however.
 */
void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
{
return radix_tree_lookup_element(root, index, 0);
}

radix_tree_lookup() 函数从基数树中查找 index 位置处的数据，并返回指向该数据的指针。

其内部调用 radix_tree_lookup_element() 函数来实现查找功能。

3.4.4 radix_tree_lookup_slot()

// file: lib/radix-tree.c
/**
 *radix_tree_lookup_slot    -    lookup a slot in a radix tree
 *@root:radix tree root
 *@index:index key
 *
 *Returns:  the slot corresponding to the position @index in the
 *radix tree @root. This is useful for update-if-exists operations.
 *
 *This function can be called under rcu_read_lock iff the slot is not
 *modified by radix_tree_replace_slot, otherwise it must be called
 *exclusive from other writers. Any dereference of the slot must be done
 *using radix_tree_deref_slot.
 */
void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index)
{
return (void **)radix_tree_lookup_element(root, index, 1);
}

radix_tree_lookup_slot() 函数从基数树中查找 index 位置处的数据，返回对应的槽位 slot 的指针。

其内部调用 radix_tree_lookup_element() 函数来实现查找功能。

3.4.5 radix_tree_node_alloc()

radix_tree_node_alloc() 函数用来为节点申请内存。

/*
 * This assumes that the caller has performed appropriate preallocation, and
 * that the caller has pinned this thread of control to the current CPU.
 */
static struct radix_tree_node *
radix_tree_node_alloc(struct radix_tree_root *root)
{
struct radix_tree_node *ret = NULL;
gfp_t gfp_mask = root_gfp_mask(root);

if (!(gfp_mask & __GFP_WAIT)) {
struct radix_tree_preload *rtp;

/*
 * Provided the caller has preloaded here, we will always
 * succeed in getting a node here (and never reach
 * kmem_cache_alloc)
 */
rtp = &__get_cpu_var(radix_tree_preloads);
if (rtp->nr) {
ret = rtp->nodes[rtp->nr - 1];
rtp->nodes[rtp->nr - 1] = NULL;
rtp->nr--;
}
}
if (ret == NULL)
ret = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask);

BUG_ON(radix_tree_is_indirect_ptr(ret));
return ret;
}

首先，调用 root_gfp_mask() 函数获取到根节点中存储的页分配标识，并赋值给 gfp_mask。

如果页标识里没有 ___GFP_WAIT 标记，说明在分配内存时不能被打断，那么直接从预分配的缓存池中为节点分配空间。

// file: include/linux/gfp.h
#define __GFP_WAIT((__force gfp_t)___GFP_WAIT)/* Can wait and reschedule? */

__get_cpu_var(radix_tree_preloads) 函数用来获取 per-cpu 变量 radix_tree_preloads，然后将变量地址赋值给 rtp。

获取到 radix_tree_preloads 的地址后，判断内存池中是否还有可用空间。如果 rtp->nr 为真，说明还有可用的空间，则将 nodes 数组中第 rtp->nr - 1 个成员（节点地址）赋值给 ret ，然后将该成员的值设置为 NULL ，表示不可用；最后，rtp->nr 自减一，表示可用的空间又减少一个。

如果 ret == NULL，说明从内存池分配失败，则调用 kmem_cache_alloc() 函数，从 slab 分配器中分配。

最后，将分配的内存地址 ret 返回。

3.4.6 radix_tree_extend()

当树的高度不足以保存指定 index 处的数据时，需要对树进行扩展，也就是要增加高度。radix_tree_extend() 函数用来实现基数树高度的扩展。

// file: lib/radix-tree.c
/*
 *Extend a radix tree so it can store key @index.
 */
static int radix_tree_extend(struct radix_tree_root *root, unsigned long index)
{
struct radix_tree_node *node;
struct radix_tree_node *slot;
unsigned int height;
int tag;

/* Figure out what the height should be.  */
height = root->height + 1;
while (index > radix_tree_maxindex(height))
height++;

if (root->rnode == NULL) {
root->height = height;
goto out;
}

do {
unsigned int newheight;
if (!(node = radix_tree_node_alloc(root)))
return -ENOMEM;

/* Propagate the aggregated tag info into the new root */
for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
if (root_tag_get(root, tag))
tag_set(node, tag, 0);
}

/* Increase the height.  */
newheight = root->height+1;
node->height = newheight;
node->count = 1;
node->parent = NULL;
slot = root->rnode;
if (newheight > 1) {
slot = indirect_to_ptr(slot);
slot->parent = node;
}
node->slots[0] = slot;
node = ptr_to_indirect(node);
rcu_assign_pointer(root->rnode, node);
root->height = newheight;
} while (height > root->height);
out:
return 0;
}

该函数接收 2 个参数：

root -- 基数树的根节点
index -- 要存储的索引

/* Figure out what the height should be.  */
height = root->height + 1;
while (index > radix_tree_maxindex(height))
height++;

首先计算出，为了能够存储索引 index 所需要的树的高度 height。

if (root->rnode == NULL) {
root->height = height;
goto out;
}

如果 root->rnode == NULL ，说明这是一棵空树，那么直接将树根的高度设置为 height，跳转到 out 标签处执行。

out:
return 0;

在 out 标签处，直接返回 0。

如果不是空树，那就需要对树高度进行扩展，扩展工作是在一个 do-while 循环中完成的。如果需要的高度 height 大于当前的高度 root->height，那么说明当前的高度不足以容纳 index，就会通过循环对基数树的高度进行扩展。每次循环，都会给树增加一层高度，即 root->height 会加一。

do {
unsigned int newheight;
if (!(node = radix_tree_node_alloc(root)))
return -ENOMEM;

...
            
} while (height > root->height);

树的高度要扩展，就需要增加新的节点。在循环开始，先通过 radix_tree_node_alloc() 函数给树分配一个节点，如果分配失败，则返回 -ENOMEM。

do {
        ...
            
/* Propagate the aggregated tag info into the new root */
for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
if (root_tag_get(root, tag))
tag_set(node, tag, 0);
}

...
            
} while (height > root->height);

接下来，需要修改节点的状态标记。在基数树中，状态标记会从底层向上层传播。也就是说，如果一个节点设置了某种标记，那么该标记会沿着父节点向上传播到根节点 root，传播路径上的每个节点都需要将该标记置位。

从上文可知，在基数树中，最多可以给一项数据保存 RADIX_TREE_MAX_TAGS（扩展为 3）种状态。对于根节点，这些状态存储在 gfp_mask 字段的位 25 ~ 27；对于中间节点，这些状态存储在 radix_tree_node 结构体的 tags 字段中。之所以使用 for 循环，就是因为这 3 种状态都需要处理，每次循环处理一种状态。

root_tag_get(root, tag) 用于获取根节点中 tag 类型的标记，如果该标记为真，说明至少有一个子节点的 tag 标记被置位。那么调用 tag_set() 函数，将新建节点 node 中 tag 类型位图中的位 0 置位。为什么是将位 0 置位？因为新节点会插入到根节点和第一层节点之间，插入后，新节点只在槽位 0 处有一个子节点。插入过程详见下文。

do {
        ...
            
/* Increase the height.  */
newheight = root->height+1;
node->height = newheight;
node->count = 1;
node->parent = NULL;
slot = root->rnode;
if (newheight > 1) {
slot = indirect_to_ptr(slot);
slot->parent = node;
}
node->slots[0] = slot;
node = ptr_to_indirect(node);
rcu_assign_pointer(root->rnode, node);
root->height = newheight;     
} while (height > root->height);

接下来，先将树的高度加一并赋值给 newheight；然后，对新节点进行设置。新节点的高度设置为 newheight，count 字段设置为 1，parent 字段设置为 NULL。

接下来执行的操作，是将新节点插入 root 和 rnode 之间，插入过程描述如下。

先将 slot 指向 rnode 节点。如果树的新高度 newheight 大于 1，则将原 rnode 节点的父节点指向新创建的节点 node。然后，将原 rnode 节点作为 node 的第一个子节点。由于新增的是一个节点，而不是数据，节点的地址要求是间接指针。所以，通过 ptr_to_indirect() 函数，将 node 转换为间接指针。再然后，调用 rcu_assign_pointer() 函数将 node 赋值给 root->rnode ，即将 node 变成新的 rnode 节点。

将新节点插入后，树的高度增加，所以将 root 节点的高度更新为 newheight。

out:
return 0;

最后，执行到标签 out 处，返回 0。

从扩展流程能够看出，每次扩展都是在 root 节点及 rnode 节点之间，插入一个新节点。也就是说，只更新了高度，没涉及到路径分支。

扩展示意图：

3.4.7 radix_tree_insert()

// file: lib/radix-tree.c
/**
 *radix_tree_insert    -    insert into a radix tree
 *@root:radix tree root
 *@index:index key
 *@item:item to insert
 *
 *Insert an item into the radix tree at position @index.
 */
int radix_tree_insert(struct radix_tree_root *root,
unsigned long index, void *item)
{
struct radix_tree_node *node = NULL, *slot;
unsigned int height, shift;
int offset;
int error;

BUG_ON(radix_tree_is_indirect_ptr(item));

/* Make sure the tree is high enough.  */
if (index > radix_tree_maxindex(root->height)) {
error = radix_tree_extend(root, index);
if (error)
return error;
}

slot = indirect_to_ptr(root->rnode);

height = root->height;
shift = (height-1) * RADIX_TREE_MAP_SHIFT;

offset = 0;/* uninitialised var warning */
while (height > 0) {
if (slot == NULL) {
/* Have to add a child node.  */
if (!(slot = radix_tree_node_alloc(root)))
return -ENOMEM;
slot->height = height;
slot->parent = node;
if (node) {
rcu_assign_pointer(node->slots[offset], slot);
node->count++;
} else
rcu_assign_pointer(root->rnode, ptr_to_indirect(slot));
}

/* Go a level down */
offset = (index >> shift) & RADIX_TREE_MAP_MASK;
node = slot;
slot = node->slots[offset];
shift -= RADIX_TREE_MAP_SHIFT;
height--;
}

if (slot != NULL)
return -EEXIST;

if (node) {
node->count++;
rcu_assign_pointer(node->slots[offset], item);
BUG_ON(tag_get(node, 0, offset));
BUG_ON(tag_get(node, 1, offset));
} else {
rcu_assign_pointer(root->rnode, item);
BUG_ON(root_tag_get(root, 0));
BUG_ON(root_tag_get(root, 1));
}

return 0;
}

radix_tree_insert() 函数用于向基数树中插入一个指定索引的数据，该函数接收 3 个参数：

root -- 基数树的根节点
index -- 待插入数据的索引值
item -- 待插入的数据指针

BUG_ON(radix_tree_is_indirect_ptr(item));

首先，检测插入的数据指针是否间接指针。间接指针用于指向 radix_tree_node 结构，所以插入的指针不应该为间接指针。

// file: include/asm-generic/bug.h
#define BUG_ON(condition) do { if (unlikely(condition)) BUG(); } while(0)

宏 BUG_ON接收一个参数，即判断条件。如果条件为真，说明内核出现了 bug，会执行 BUG()中的代码。

在此处，如果是间接指针，说明内核出现了 bug。

/* Make sure the tree is high enough.  */
if (index > radix_tree_maxindex(root->height)) {
error = radix_tree_extend(root, index);
if (error)
return error;
}

接下来，如果 index 的值大于当前树的高度所能容纳的最大索引，则调用 radix_tree_extend() 函数对树进行扩展。如果扩展失败，返回错误码。

slot = indirect_to_ptr(root->rnode);

height = root->height;
shift = (height-1) * RADIX_TREE_MAP_SHIFT;

offset = 0;/* uninitialised var warning */

再接着，获取 rnode 节点地址，转换成普通指针后保存到变量 slot 中；获取树的高度保存到变量 height 中；计算移位数量保存到 shift 变量中（关于 shift 的计算详见 3.4.2 节）；并将 offset 初始化为 0。

while (height > 0) {
if (slot == NULL) {
/* Have to add a child node.  */
if (!(slot = radix_tree_node_alloc(root)))
return -ENOMEM;
slot->height = height;
slot->parent = node;
if (node) {
rcu_assign_pointer(node->slots[offset], slot);
node->count++;
} else
rcu_assign_pointer(root->rnode, ptr_to_indirect(slot));
}

...
}

接下来进入 while 循环，将 index 路径上的节点补全。

如果 slot == NULL，说明 index 路径上的节点不存在，需要补全。先调用 radix_tree_node_alloc() 函数，为节点申请内存，并将申请的内存地址赋值给 slot。如果申请失败，直接返回错误码 -ENOMEM 。接下来，设置新节点的高度为 height 及父节点为 node。如果 node 为真，说明不是为根节点增加子节点，把新节点插入到 node 中对应的位置，即把 slot 赋值给 node->slots[offset]，然后将 node 的子节点数量加一（node->count++）；否则，说明是为根节点增加子节点，则将新节点 slot 赋值给 root->rnode。

while (height > 0) {

...
            
        /* Go a level down */
offset = (index >> shift) & RADIX_TREE_MAP_MASK;
node = slot;
slot = node->slots[offset];
shift -= RADIX_TREE_MAP_SHIFT;
height--;
}

接下来，为下一层查找做准备。offset 计算出 index 在下一层的槽位。然后将 node 指向新插入的节点 slot ，作为下一次查询的父节点。再接着，将 slot 指向 index 路径的下一层节点。然后更新位偏移 shift 。由于基数树的每层对应着 6（RADIX_TREE_MAP_SHIFT）个比特位，所以将当前层的 shift 减去 RADIX_TREE_MAP_SHIFT 后，就得到下一层的位偏移。

再接着，将高度自减一，进入下一层，继续执行插入功能。

if (slot != NULL)
return -EEXIST;

如果查找到最后，发现 slot != NULL，说明该索引对应的值已经存在了，无法添加，所以返回错误码 -EEXIST。

if (node) {
node->count++;
rcu_assign_pointer(node->slots[offset], item);
BUG_ON(tag_get(node, 0, offset));
BUG_ON(tag_get(node, 1, offset));
} else {
...
}

现在，我们已经到达最底层的节点了，接下来，就要将数据 item 插入到节点中对应的槽位。

如果 node 为真，说明要插入数据的节点不是根节点 root。那么，先将 node 节点的子节点数量加一；然后将 item 赋值给

node->slots[offset]，即将数据 item 插入到 node 中的第 offset 个槽位。

tag_get() 函数用于获取中间节点中指定标记的状态。由于是新插入的数据，node 节点中 tags[0] 及 tags[1] 这两个位图中对应的位都应该为 0。如果不为 0，说明出现了 bug，调用BUG_ON() 宏进行处理。

if (node) {
...
} else {
rcu_assign_pointer(root->rnode, item);
BUG_ON(root_tag_get(root, 0));
BUG_ON(root_tag_get(root, 1));
}

如果 node 为假，说明是给根节点增加数据。直接将 item 赋值给 root->rnode。

root_tag_get() 函数用于获取根节点中，指定标记的状态。

由于是新插入的数据，root 节点中指示前两种标记的比特位都应该为 0。如果不为 0，说明出现了 bug，调用BUG_ON() 宏进行处理。

3.4.8 radix_tree_shrink()

radix_tree_shrink() 函数用于收缩基数树的高度。

// file: lib/radix-tree.c
/**
 *radix_tree_shrink    -    shrink height of a radix tree to minimal
 *@rootradix tree root
 */
static inline void radix_tree_shrink(struct radix_tree_root *root)
{
/* try to shrink tree height */
while (root->height > 0) {
struct radix_tree_node *to_free = root->rnode;
struct radix_tree_node *slot;

BUG_ON(!radix_tree_is_indirect_ptr(to_free));
to_free = indirect_to_ptr(to_free);

/*
 * The candidate node has more than one child, or its child
 * is not at the leftmost slot, we cannot shrink.
 */
if (to_free->count != 1)
break;
if (!to_free->slots[0])
break;

/*
 * We don't need rcu_assign_pointer(), since we are simply
 * moving the node from one part of the tree to another: if it
 * was safe to dereference the old pointer to it
 * (to_free->slots[0]), it will be safe to dereference the new
 * one (root->rnode) as far as dependent read barriers go.
 */
slot = to_free->slots[0];
if (root->height > 1) {
slot->parent = NULL;
slot = ptr_to_indirect(slot);
}
root->rnode = slot;
root->height--;

/*
 * We have a dilemma here. The node's slot[0] must not be
 * NULLed in case there are concurrent lookups expecting to
 * find the item. However if this was a bottom-level node,
 * then it may be subject to the slot pointer being visible
 * to callers dereferencing it. If item corresponding to
 * slot[0] is subsequently deleted, these callers would expect
 * their slot to become empty sooner or later.
 *
 * For example, lockless pagecache will look up a slot, deref
 * the page pointer, and if the page is 0 refcount it means it
 * was concurrently deleted from pagecache so try the deref
 * again. Fortunately there is already a requirement for logic
 * to retry the entire slot lookup -- the indirect pointer
 * problem (replacing direct root node with an indirect pointer
 * also results in a stale slot). So tag the slot as indirect
 * to force callers to retry.
 */
if (root->height == 0)
*((unsigned long *)&to_free->slots[0]) |=
RADIX_TREE_INDIRECT_PTR;

radix_tree_node_free(to_free);
}
}

可以看到，radix_tree_shrink() 函数就是一个大的 while 循环，所有的代码都是在循环内部执行的。当基数树的高度为 0，或者候选节点不止一个子节点，或者候选节点的子节点不在槽的最左侧时，循环结束。

/* try to shrink tree height */
while (root->height > 0) {
struct radix_tree_node *to_free = root->rnode;
struct radix_tree_node *slot;

BUG_ON(!radix_tree_is_indirect_ptr(to_free));
to_free = indirect_to_ptr(to_free);
        
        ...
            
    }

循环内部，先获取到 rnode 节点，并赋值给 to_free 作为第一个候选节点。由于树的高度大于 0，所以 to_free 只能是间接指针。如果不是，那就是 bug，会调用宏 BUG_ON() 来处理。接下来，调用 indirect_to_ptr() 函数，将 to_free 转换成普通指针。

/* try to shrink tree height */
while (root->height > 0) {
        ...
/*
 * The candidate node has more than one child, or its child
 * is not at the leftmost slot, we cannot shrink.
 */
if (to_free->count != 1)
break;
if (!to_free->slots[0])
break;
        
        ...   
    }

如果候选节点的子节点数量大于 1，或者唯一子节点不在槽的最左侧，就不能收缩高度，则直接跳出循环。

while (root->height > 0) {
        ...
            
slot = to_free->slots[0];
if (root->height > 1) {
slot->parent = NULL;
slot = ptr_to_indirect(slot);
}
root->rnode = slot;
root->height--;
        
        ...   
    }

接下来执行收缩操作，也就是将 rnode 节点从树上摘掉，把 rnode 的子节点变成 rnode 节点。然后将树的高度减一。

while (root->height > 0) {
        ...
        /*
 * We have a dilemma here. The node's slot[0] must not be
 * NULLed in case there are concurrent lookups expecting to
 * find the item. However if this was a bottom-level node,
 * then it may be subject to the slot pointer being visible
 * to callers dereferencing it. If item corresponding to
 * slot[0] is subsequently deleted, these callers would expect
 * their slot to become empty sooner or later.
 *
 * For example, lockless pagecache will look up a slot, deref
 * the page pointer, and if the page is 0 refcount it means it
 * was concurrently deleted from pagecache so try the deref
 * again. Fortunately there is already a requirement for logic
 * to retry the entire slot lookup -- the indirect pointer
 * problem (replacing direct root node with an indirect pointer
 * also results in a stale slot). So tag the slot as indirect
 * to force callers to retry.
 */  
if (root->height == 0)
*((unsigned long *)&to_free->slots[0]) |=
RADIX_TREE_INDIRECT_PTR;

... 
    }

当树的高度降为 0 时，将待删除节点 0 号槽位的子节点指针设置为间接指针。

根据注释所说，这么做的原因是因为在收缩时，可能有其它的程序在进行并发查询。在删除节点时，不能将其子节点的指针设置为 NULL，因为并发查询有可能走的是被删除节点的那条路径，即顺着被删除节点向下查询。当查询到最底层时，有可能要查询的数据已经被删除了，但查询的程序并不知晓。这里将被删除节点中指向数据的指针设置为间接指针，是给查找程序一个信号，要求其重新查询。

while (root->height > 0) {
        ...

radix_tree_node_free(to_free); 
    }

最后，调用 radix_tree_node_free() 函数，释放节点内存。

3.4.9 radix_tree_delete()

// file: lib/radix-tree.c
/**
 *radix_tree_delete    -    delete an item from a radix tree
 *@root:radix tree root
 *@index:index key
 *
 *Remove the item at @index from the radix tree rooted at @root.
 *
 *Returns the address of the deleted item, or NULL if it was not present.
 */
void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
{
struct radix_tree_node *node = NULL;
struct radix_tree_node *slot = NULL;
struct radix_tree_node *to_free;
unsigned int height, shift;
int tag;
int uninitialized_var(offset);

height = root->height;
if (index > radix_tree_maxindex(height))
goto out;

slot = root->rnode;
if (height == 0) {
root_tag_clear_all(root);
root->rnode = NULL;
goto out;
}
slot = indirect_to_ptr(slot);
shift = height * RADIX_TREE_MAP_SHIFT;

do {
if (slot == NULL)
goto out;

shift -= RADIX_TREE_MAP_SHIFT;
offset = (index >> shift) & RADIX_TREE_MAP_MASK;
node = slot;
slot = slot->slots[offset];
} while (shift);

if (slot == NULL)
goto out;

/*
 * Clear all tags associated with the item to be deleted.
 * This way of doing it would be inefficient, but seldom is any set.
 */
for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
if (tag_get(node, tag, offset))
radix_tree_tag_clear(root, index, tag);
}

to_free = NULL;
/* Now free the nodes we do not need anymore */
while (node) {
node->slots[offset] = NULL;
node->count--;
/*
 * Queue the node for deferred freeing after the
 * last reference to it disappears (set NULL, above).
 */
if (to_free)
radix_tree_node_free(to_free);

if (node->count) {
if (node == indirect_to_ptr(root->rnode))
radix_tree_shrink(root);
goto out;
}

/* Node with zero slots in use so free it */
to_free = node;

index >>= RADIX_TREE_MAP_SHIFT;
offset = index & RADIX_TREE_MAP_MASK;
node = node->parent;
}

root_tag_clear_all(root);
root->height = 0;
root->rnode = NULL;
if (to_free)
radix_tree_node_free(to_free);

out:
return slot;
}

radix_tree_delete() 函数会删除指定索引位置的数据，该函数接收 2 个参数：

root -- 基数树的根节点
index -- 待删除数据的索引值

struct radix_tree_node *node = NULL;
struct radix_tree_node *slot = NULL;
struct radix_tree_node *to_free;
unsigned int height, shift;
int tag;
int uninitialized_var(offset);

首先声明了一批变量，其中 node 和 slot 被初始化为 NULL。

// file: include/linux/compiler-gcc.h
/*
 * A trick to suppress uninitialized variable warning without generating any
 * code
 */
#define uninitialized_var(x) x = x

其中，宏 uninitialized_var() 使用了小技巧用来抑制编译器对未初始化变量产生 warning 信息。该宏在内核 v5.9 版本被移除。可参考 Removing uninitialized_var()。

height = root->height;
if (index > radix_tree_maxindex(height))
goto out;

如果指定的索引值超出当前高度所能表示的最大索引，说明不需要删除，直接跳转到 out 标签处。

out:
return slot;

out 标签处，会返回 slot 的值，此时 slot 为 NULL。

slot = root->rnode;
if (height == 0) {
root_tag_clear_all(root);
root->rnode = NULL;
goto out;
}

将 slot 指向 rnode 节点。如果树的高度为 0，说明是空树，不需要删除。调用 root_tag_clear_all() 函数清除根节点的所用标记，并将 root->rnode 设置为 NULL。

slot = indirect_to_ptr(slot);
shift = height * RADIX_TREE_MAP_SHIFT;

将 slot 转换成普通指针，并计算初始位偏移 shift。

do {
if (slot == NULL)
goto out;

shift -= RADIX_TREE_MAP_SHIFT;
offset = (index >> shift) & RADIX_TREE_MAP_MASK;
node = slot;
slot = slot->slots[offset];
} while (shift);

接下来是一个循环，从 rnode 节点开始，自上往下逐层查找。在查找的过程，node 指向父节点，slot 指向子节点。正如 3.4.2 节所介绍的，每降低一层，shift 的值就会减少 RADIX_TREE_MAP_SHIFT。offset 计算出 index 对应的当前层的槽位。如果 shift 不为 0 时，slot 为 NULL ，说明要删除的索引不存在，跳转到 out 标签处执行。

if (slot == NULL)
goto out;

如果查到到最底层，发现 slot 为 NULL，说明该索引没有对应的值，直接跳转到 out 标签处执行。

/*
 * Clear all tags associated with the item to be deleted.
 * This way of doing it would be inefficient, but seldom is any set.
 */
for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
if (tag_get(node, tag, offset))
radix_tree_tag_clear(root, index, tag);
}

所有异常情况都排除了，现在找到了索引对应的数据。由于该数据即将被删除，如果该数据有标记被置位，那么需要清除整条路径上相关节点的标记。由于每项数据可能有 RADIX_TREE_MAX_TAGS 种状态，所以使用了一个 for 循环，每次循环清除一种状态。调用 tag_get() 函数获取节点中待删除数据对应的标记位。如果标记被置位，则调用 radix_tree_tag_clear() 函数来清除整个路径上的标记。

to_free = NULL;
/* Now free the nodes we do not need anymore */
while (node) {
node->slots[offset] = NULL;
node->count--;
/*
 * Queue the node for deferred freeing after the
 * last reference to it disappears (set NULL, above).
 */
if (to_free)
radix_tree_node_free(to_free);

if (node->count) {
if (node == indirect_to_ptr(root->rnode))
radix_tree_shrink(root);
goto out;
}

/* Node with zero slots in use so free it */
to_free = node;

index >>= RADIX_TREE_MAP_SHIFT;
offset = index & RADIX_TREE_MAP_MASK;
node = node->parent;
}

接下来，就是执行节点的释放工作。变量 to_free 表示要释放的节点，被初始化为 NULL。此时，node 指向最底层节点，slot 指向要删除的数据，offset 表示数据的槽位。

先将 node->slots[offset] 设置为 NULL，切断了父子节点间的联系；然后将父节点的子节点数量减一，即 node->count--。

如果 to_free 为真，说明有节点需要释放，调用 radix_tree_node_free() 函数释放节点。从注释中可以看出，该函数会将节点放入队列，等到没有引用时才会真正释放。

如果删除后，父节点 node 的子节点数量不为 0，说明该节点不能删除。调用 radix_tree_shrink() 函数尝试进行收缩，然后跳转到标签 out 处执行。

如果删除后，父节点 node 没有子节点了，那么 node 也将被释放，此时将 node 赋值给 to_free。

接下来，需要进入上一层执行删除工作。在进入上一层之前，需要计算出索引 index 对应的上一层的槽位，即 offset 的值。然后，将 node 指向其父节点，进入下一轮循环。

root_tag_clear_all(root);
root->height = 0;
root->rnode = NULL;
if (to_free)
radix_tree_node_free(to_free);

现在我们来到了 while 循环结束和 out 标签之间的代码。能来到这里，说明已经来到了根节点。如果在非根节点停止的话，在 while 循环内部就会跳转到 out 标签处执行。接下来，调用 root_tag_clear_all() 函数将根节点的所有标记清除。将树的高度设置为 0，rnode 设置为 NULL。如果 to_free 为真，调用radix_tree_node_free() 函数将其释放。

out:
return slot;

最后，执行到 out 标签处，返回 slot 的值。如果删除了数据，slot 指向该数据；否则，slot 为 NULL。

四、参考文献

1、Trie

2、Radix tree

3、《深入理解 Linux 内核（第三版）》第 15 章，基树小节

4、Removing uninitialized_var()

5、Linux Kernel：内核数据结构之位图（Bitmap）

6、 __builtin_types_compatible_p

7、 x86-64架构：内存分页机制