[TOC]

lib/radix-tree.c 基数树(Radix Tree) 整数键到指针的高效映射

历史与背景

这项技术是为了解决什么特定问题而诞生的？

lib/radix-tree.c 提供的基数树（Radix Tree）是为了解决一个在内核中非常常见的问题：如何将一个整数（特别是unsigned long类型）作为键，高效地、空间优化地映射到一个指针。

在基数树出现之前，内核中存在多种方式来解决这个问题，但各有缺点：

  • 哈希表：对于稀疏的键（例如，文件偏移量，可能非常大且不连续），哈希表虽然平均查找速度快，但存在哈希冲突问题，且无法高效地进行范围查找或有序遍历。
  • 红黑树：可以处理稀疏的键并支持有序遍历，但它是指针密集型的数据结构，每个节点都有左右子指针、父指针和颜色等额外开销，导致内存占用较高，且缓存效率不佳。
  • 直接映射数组：如果键的范围不大且密集，这是最快的方法。但如果键的范围很大（例如unsigned long的所有可能值），创建一个如此巨大的指针数组是完全不可行的，会消耗天文数字般的内存。

基数树被设计出来，就是为了结合以上方法的优点，同时避免它们的缺点。它特别擅长管理稀疏但可能聚集成块的整数键，这在文件系统和内存管理中非常常见。

它的发展经历了哪些重要的里程碑或版本迭代？

基数树在Linux内核中的发展是一个持续优化和功能演进的过程：

  • 基本实现：最初的基数树实现奠定了其核心思想——使用整数键的比特位作为路径，逐级在树中导航。它被迅速应用到核心的页缓存（Page Cache）中，用于将文件的逻辑偏移量映射到struct page指针。
  • 标签（Tags）功能：为了满足更复杂的需求，基数树增加了“标签”功能。这允许为树中的每个条目设置或清除一些标志位（tags）。例如，页缓存使用标签来标记哪些页面是“脏”的（dirty）或“需要回写”（writeback）。这使得可以非常快速地查找到所有带有特定标签的页面，而无需遍历整个文件。
  • 多阶（Multi-order）条目：为了进一步优化空间，特别是当多个连续的键都映射到同一个值时，基数树引入了多阶条目的概念。这允许一个叶子节点代表一个键的范围，而不是单个键，从而减少了树的深度和节点的数量。
  • XArray的演进：尽管基数树非常成功，但其API被认为有些复杂和晦涩。内核开发者Matthew Wilcox主导了一个项目，旨在创建一个API更友好、功能更强大、性能更好的替代品，这就是XArray。现代内核中，许多原先使用基数树的地方都已经被迁移到了XArray。XArray可以看作是基数树的下一代演进，它提供了更丰富的功能（如存储多种类型的值而不仅是指针）和更简洁的接口，但其底层核心思想仍然源于基数树。

目前该技术的社区活跃度和主流应用情况如何？

基数树仍然是内核中的一个核心数据结构，尽管它的现代继承者XArray正在逐步取代它。

  • 核心应用：它最著名和最核心的应用是在页缓存中，用于建立文件偏移量（pgoff_t，一个unsigned long）到内存页（struct page *）的映射。
  • 遗留与迁移：许多老的代码路径仍然在使用基数树。新编写的代码则被强烈推荐使用XArray。社区的活跃度主要体现在将现有的基数树用户迁移到XArray上，以及对XArray本身的持续开发。

核心原理与设计

它的核心工作原理是什么？

基数树是一种基于键的二进制位进行路径压缩的前缀树（Trie）。它将一个unsigned long类型的键看作是一个二进制串，并利用这个串来在树中导航。

  1. 树的结构：树由radix_tree_node组成。每个节点内部是一个指针数组（通常大小为64，对应unsigned long中的6个比特位）。树的高度是固定的，取决于unsigned long的总位数和每个节点所能表示的位数。
  2. 查找过程：
    • 从键的最高有效位开始，取出一组比特（例如6个比特）。
    • 使用这组比特作为索引，在当前节点的指针数组中找到下一级节点的指针。
    • 移动到下一级节点，然后取键的下一组比特，重复上述过程。
    • 这个过程一直持续，直到到达叶子节点，叶子节点中存储的就是与该键关联的指针。
  3. 空间优化：基数树的核心优势在于其空间效率。
    • 路径压缩：如果一个中间节点只有一个子节点，那么这个中间节点实际上可以被省略，从而压缩树的路径。
    • 懒分配：只有当需要插入一个键时，通往该键的路径上所需的节点才会被动态分配。对于稀疏的键空间，这意味着树中绝大部分可能的节点根本不会存在，从而节省了大量内存。

它的主要优势体现在哪些方面？

  • 空间效率高：对于稀疏的整数键分布，其内存占用远低于直接映射数组，也通常优于指针开销大的红黑树。
  • 查找速度快且稳定：查找操作的时间复杂度为O(k)，其中k是键的位数。这是一个与树中元素总数无关的、非常稳定的上界。
  • 高效的范围和标签查找：标签机制使得查找具有特定属性的条目变得非常高效。
  • 缓存友好：相比于指针追逐的红黑树，基数树的节点内部是连续的数组，这在一定程度上提高了缓存局部性。

它存在哪些已知的劣势、局限性或在特定场景下的不适用性？

  • API复杂：基数树的API（特别是涉及标签和锁的部分）相对复杂，容易误用。这也是驱动XArray开发的主要动机之一。
  • 只适用于整数键：它被专门设计用来处理unsigned long类型的键。如果键是字符串或其他复杂类型，哈希表是更好的选择。
  • 写操作的锁竞争：基数树的修改操作需要锁来保护。在高并发写入的场景下，这可能会成为瓶颈。（XArray在这方面做了很多改进）。

使用场景

在哪些具体的业务或技术场景下，它是首选解决方案？

在内核中，任何需要将一个稀疏的、unsigned long类型的ID或索引映射到一个指针，特别是还需要高效地查找带有特定标记的条目时，基数树（或其后继者XArray）是首选解决方案。

  • 页缓存（Page Cache）：这是基数树的经典应用。一个文件可能非常大（GB甚至TB级别），但同一时间在内存中的页面可能只有很少一部分。页缓存使用基数树将文件的页偏移量（一个稀疏的unsigned long）映射到struct page指针。同时，它使用标签来快速定位脏页，以便回写线程能高效地找到需要写入磁盘的数据。
  • 文件描述符管理：在某些实现中，可以使用基数树来管理一个进程的文件描述符表，将整数fd映射到struct file指针。
  • 内存管理：用于管理物理内存页帧号（PFN）到struct page的映射，特别是在非连续内存（discontiguous memory）模型中。

是否有不推荐使用该技术的场景？为什么？

  • 键不是unsigned long：如上所述，非整数键应使用哈希表。
  • 需要按键的完整顺序进行遍历：虽然基数树存储的键是有序的，但遍历它不如遍历红黑树或链表来得直接。红黑树能提供中序遍历。
  • 数据量很小且键是密集的：如果键是从0开始的连续整数且数量不多，一个简单的数组会更快、更简单。

对比分析

请将其 与 其他相似技术 进行详细对比。

特性 基数树 (Radix Tree) / XArray 哈希表 (Hash Table) 红黑树 (Red-Black Tree)
核心功能 整数键到指针的空间优化映射，支持标签。 任意键到值的快速映射。 任意可比较的键到值的有序映射。
数据模型 unsigned long -> void * key -> value key -> value
查找性能 O(k) (k为键的位数)，稳定。 平均 O(1)，最坏 O(n)，不稳定。 O(log n)，稳定。
空间效率 非常高（对稀疏键）。 中等。 较低（指针开销大）。
有序性 有序。 无序。 有序。
特殊功能 标签（Tags），用于快速查找带标记的条目。 无。 无。
范围查找 支持，效率高。 不支持。 支持，效率高。
实现复杂性 高。 较低。 中等。
典型用途 页缓存，文件描述符表，PFN到page的映射。 dcache，PID表，连接跟踪。 VMA管理（已被Maple Tree取代），高精度定时器。

include/linux/radix-tree.h

RADIX_TREE_INIT

1
2
3
4
5
6
/* The IDR tag is stored in the low bits of xa_flags */
#define ROOT_IS_IDR	((__force gfp_t)4)
/* The top bits of xa_flags are used to store the root tags */
#define ROOT_TAG_SHIFT	(__GFP_BITS_SHIFT)

#define RADIX_TREE_INIT(name, mask)	XARRAY_INIT(name, mask)

INIT_RADIX_TREE

1
#define INIT_RADIX_TREE(root, mask) xa_init_flags(root, mask)

radix_tree_iter_init 初始化基数树迭代器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

/**
 * radix_tree_iter_init - 初始化基数树迭代器
 *
 * @iter:	指向迭代器状态的指针
 * @start:	迭代起始索引
 * Returns:	NULL
 */
static __always_inline void __rcu **
radix_tree_iter_init(struct radix_tree_iter *iter, unsigned long start)
{
	/*
    * 保持 iter->tags 未初始化。radix_tree_next_chunk() 将在成功查找带标签的块时填写它。
    * 如果查找失败或者没有标签，则没有人关心 ->tags。	
    * 将索引设置为零以绕过 next_index 溢出保护。	 
    * 有关详细信息，请参见 radix_tree_next_chunk() 中的评论。
	 */
	iter->index = 0;
	iter->next_index = start;
	return NULL;
}

radix_tree_next_chunk 迭代下一个槽位

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
/** 
 * radix_tree_next_chunk - 查找用于迭代的下一个槽块 * 
 * @root:  radix tree root 
 * @iter:  迭代器状态 
 * @flags:  RADIX_TREE_ITER_* 标志和标签索引 
 * 返回值: 指向块第一个槽的指针，如果迭代结束则返回 NULL 
 */
void __rcu **radix_tree_next_chunk(const struct radix_tree_root *root,
			     struct radix_tree_iter *iter, unsigned flags)
{
	unsigned tag = flags & RADIX_TREE_ITER_TAG_MASK;
	struct radix_tree_node *node, *child;
	unsigned long index, offset, maxindex;

	if ((flags & RADIX_TREE_ITER_TAGGED) && !root_tag_get(root, tag))
		return NULL;

	/*
	 * 捕获 ~0UL 后的 next_index 溢出。
    * 在迭代过程中，iter->index 永远不会溢出；它只能在开始时为零。
    * 并且由于 RADIX_TREE_MAP_SHIFT < BITS_PER_LONG，我们不能在单步操作中溢出 iter->next_index。
    * 这个条件也被 radix_tree_next_slot() 用来停止连续迭代，并禁止切换到下一个块。
	 */
	index = iter->next_index;
	if (!index && iter->index)
		return NULL;

 restart:
	radix_tree_load_root(root, &child, &maxindex);
	if (index > maxindex)
		return NULL;
	if (!child)
		return NULL;

   /* 单槽位树处理: 如果树中只有一个槽位（非内部节点），直接返回该槽位，并更新迭代器状态。 */
	if (!radix_tree_is_internal_node(child)) {
		/* Single-slot tree */
		iter->index = index;
		iter->next_index = maxindex + 1;
		iter->tags = 1;
		iter->node = NULL;
		return (void __rcu **)&root->xa_head;
	}

   /* 递归下降: 对于多层树，函数通过 radix_tree_descend 递归下降到子节点，直到找到符合条件的槽位或检测到“空洞”（hole）。
    * 如果检测到空洞且设置了 RADIX_TREE_ITER_CONTIG 标志，则停止迭代。 */
	do {
		node = entry_to_node(child);
		offset = radix_tree_descend(node, &child, index);

		if ((flags & RADIX_TREE_ITER_TAGGED) ?
				!tag_get(node, tag, offset) : !child) {
			/* Hole detected */
			if (flags & RADIX_TREE_ITER_CONTIG)
				return NULL;

			if (flags & RADIX_TREE_ITER_TAGGED)
				offset = radix_tree_find_next_bit(node, tag,
						offset + 1);
			else
				while (++offset	< RADIX_TREE_MAP_SIZE) {
					void *slot = rcu_dereference_raw(
							node->slots[offset]);
					if (slot)
						break;
				}
			index &= ~node_maxindex(node);
			index += offset << node->shift;
			/* Overflow after ~0UL */
			if (!index)
				return NULL;
			if (offset == RADIX_TREE_MAP_SIZE)
				goto restart;
			child = rcu_dereference_raw(node->slots[offset]);
		}

		if (!child)
			goto restart;
		if (child == RADIX_TREE_RETRY)
			break;
	} while (node->shift && radix_tree_is_internal_node(child));

	/* Update the iterator state */
	iter->index = (index &~ node_maxindex(node)) | offset;
	iter->next_index = (index | node_maxindex(node)) + 1;
	iter->node = node;

	if (flags & RADIX_TREE_ITER_TAGGED)
		set_iter_tags(iter, node, offset, tag);

	return node->slots + offset;
}
EXPORT_SYMBOL(radix_tree_next_chunk);

radix_tree_for_each_slot 迭代非空槽位

1
2
3
4
5
6
7
8
/** * radix_tree_for_each_slot - 迭代非空槽位 *
 * @slot: 指向槽位的 void** 变量 * @root: struct radix_tree_root 指针
 * @iter: struct radix_tree_iter 指针 * @start: 迭代起始索引 *
 * @slot 指向基数树槽位，@iter->index 包含其索引。 */
#define radix_tree_for_each_slot(slot, root, iter, start)		\
	for (slot = radix_tree_iter_init(iter, start) ;			\
	     slot || (slot = radix_tree_next_chunk(root, iter, 0)) ;	\
	     slot = radix_tree_next_slot(slot, iter, 0))

radix_tree_lookup 在基数树中查找项目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/**
 *	__radix_tree_lookup	-	在基数树中查找项目
 *	@root:		radix tree root
 *	@index:		index key
 *	@nodep:		returns node
 *	@slotp:		returns slot
 *
 * 在基数树 @root 中查找并返回位置 @index 的项。 *  
 * 当树中只有一个项目时，不会分配节点，并且 @root->xa_head 被用作直接槽，而不是指向一个节点，这种情况下 *@nodep 将为 NULL。
 */
void *__radix_tree_lookup(const struct radix_tree_root *root,
			  unsigned long index, struct radix_tree_node **nodep,
			  void __rcu ***slotp)
{
	struct radix_tree_node *node, *parent;
	unsigned long maxindex;
	void __rcu **slot;

 restart:
	parent = NULL;
	slot = (void __rcu **)&root->xa_head;
	radix_tree_load_root(root, &node, &maxindex);
	if (index > maxindex)
		return NULL;

	while (radix_tree_is_internal_node(node)) {
		unsigned offset;

		parent = entry_to_node(node);
		offset = radix_tree_descend(parent, &node, index);
		slot = parent->slots + offset;
		if (node == RADIX_TREE_RETRY)
			goto restart;
		if (parent->shift == 0)
			break;
	}

	if (nodep)
		*nodep = parent;
	if (slotp)
		*slotp = slot;
	return node;
}

/**
 *	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(const struct radix_tree_root *root, unsigned long index)
{
	return __radix_tree_lookup(root, index, NULL, NULL);
}
EXPORT_SYMBOL(radix_tree_lookup);

radix_tree_delete_item 删除基数树中的项目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
static bool __radix_tree_delete(struct radix_tree_root *root,
				struct radix_tree_node *node, void __rcu **slot)
{
	void *old = rcu_dereference_raw(*slot);
	int values = xa_is_value(old) ? -1 : 0;
	unsigned offset = get_slot_offset(node, slot);
	int tag;

	if (is_idr(root))
		node_tag_set(root, node, IDR_FREE, offset);
	else
		for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
			node_tag_clear(root, node, tag, offset);

	replace_slot(slot, NULL, node, -1, values);
	return node && delete_node(root, node);
}

/**
 * radix_tree_delete_item - delete an item from a radix tree
 * @root: radix tree root
 * @index: index key
 * @item: expected item
 *
 * 从以 @root 为根的基数树中删除 @index 处的 @item。 *  
 * 返回：被删除的条目，如果条目不存在或 @index 处的条目不是 @item，则返回 %NULL。
 */
void *radix_tree_delete_item(struct radix_tree_root *root,
			     unsigned long index, void *item)
{
	struct radix_tree_node *node = NULL;
	void __rcu **slot = NULL;
	void *entry;

	entry = __radix_tree_lookup(root, index, &node, &slot);
	if (!slot)
		return NULL;
	if (!entry && (!is_idr(root) || node_tag_get(root, node, IDR_FREE,
						get_slot_offset(node, slot))))
		return NULL;

	if (item && entry != item)
		return NULL;

	__radix_tree_delete(root, node, slot);

	return entry;
}
EXPORT_SYMBOL(radix_tree_delete_item);

lib/radix-tree.c

radix_tree_init radix_tree_node 缓存池的初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
static void
radix_tree_node_ctor(void *arg)
{
	struct radix_tree_node *node = arg;

	memset(node, 0, sizeof(*node));
	INIT_LIST_HEAD(&node->private_list);
}

static int radix_tree_cpu_dead(unsigned int cpu)
{
	struct radix_tree_preload *rtp;
	struct radix_tree_node *node;

	/* Free per-cpu pool of preloaded nodes */
	rtp = &per_cpu(radix_tree_preloads, cpu);
	while (rtp->nr) {
		node = rtp->nodes;
		rtp->nodes = node->parent;
		kmem_cache_free(radix_tree_node_cachep, node);
		rtp->nr--;
	}
	return 0;
}


void __init radix_tree_init(void)
{
	int ret;

	BUILD_BUG_ON(RADIX_TREE_MAX_TAGS + __GFP_BITS_SHIFT > 32);
	BUILD_BUG_ON(ROOT_IS_IDR & ~GFP_ZONEMASK);
	BUILD_BUG_ON(XA_CHUNK_SIZE > 255);
	radix_tree_node_cachep = kmem_cache_create("radix_tree_node",
			sizeof(struct radix_tree_node), 0,
			SLAB_PANIC | SLAB_RECLAIM_ACCOUNT,
			radix_tree_node_ctor);
    /* 用于处理 CPU 热插拔事件（CPU 被移除时）。它的主要任务是清理与被移除 CPU 相关的基数树预加载节点 */
	ret = cpuhp_setup_state_nocalls(CPUHP_RADIX_DEAD, "lib/radix:dead",
					NULL, radix_tree_cpu_dead);
	WARN_ON(ret < 0);
}

__radix_tree_preload 用于预加载当前 CPU 的 radix_tree_node 缓冲区

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/*
 * Per-cpu pool of preloaded nodes
 */
DEFINE_PER_CPU(struct radix_tree_preload, radix_tree_preloads) = {
	.lock = INIT_LOCAL_LOCK(lock),
};
EXPORT_PER_CPU_SYMBOL_GPL(radix_tree_preloads);

/*
 * 预加载当前 CPU 的 radix_tree_node 缓冲区，
 * 以确保在向 Radix 树中添加单个元素时不会因内存分配失败而中断
 *
 * 要使用此功能，必须初始化基数树，而不将__GFP_DIRECT_RECLAIM传递给 INIT_RADIX_TREE（）。
 */
static __must_check int __radix_tree_preload(gfp_t gfp_mask, unsigned nr)
{
	struct radix_tree_preload *rtp;
	struct radix_tree_node *node;
	int ret = -ENOMEM;

	/* 去除 __GFP_ACCOUNT 标志，确保预加载的节点不会被归属于任何特定的内存控制组（cgroup）。
		这是因为预加载的节点可能被不同的 cgroup 使用，因此不能进行内存计费。 */
	gfp_mask &= ~__GFP_ACCOUNT;

	local_lock(&radix_tree_preloads.lock);
	rtp = this_cpu_ptr(&radix_tree_preloads);
	/* 检查当前 CPU 的预加载缓冲区是否已达到所需的节点数量（nr） */
	while (rtp->nr < nr) {
		local_unlock(&radix_tree_preloads.lock);
		/* 尝试分配新的节点对象 */
		node = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask);
		if (node == NULL)
			goto out;
		local_lock(&radix_tree_preloads.lock);
		rtp = this_cpu_ptr(&radix_tree_preloads);
		/* 新节点添加到缓冲区链表中 */
		if (rtp->nr < nr) {
			node->parent = rtp->nodes;
			rtp->nodes = node;
			rtp->nr++;
		} else {
			/* 缓冲区已满足需求，则释放多余的节点 */
			kmem_cache_free(radix_tree_node_cachep, node);
		}
	}
	ret = 0;
out:
	return ret;
}

idr_preload idr_alloc（） 的预加载

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * idr_preload - idr_alloc（） 的预加载
 * @gfp_mask：用于预加载的分配掩码
 *
 * 预分配内存以用于下次调用 idr_alloc（）。 
 * 此函数在禁用抢占的情况下返回。 它将由 idr_preload_end（） 启用。
 */
void idr_preload(gfp_t gfp_mask)
{
	if (__radix_tree_preload(gfp_mask, IDR_PRELOAD_SIZE))
		local_lock(&radix_tree_preloads.lock);
}
EXPORT_SYMBOL(idr_preload);

radix_tree_insert: 向基数树中插入一个条目

此函数是Linux内核基数树(Radix Tree)数据结构的核心API之一。它的作用是将一个”条目”(item, 通常是一个指针)插入到基数树中, 并与一个无符号长整型的”索引”(index)关联起来。

其核心原理是: 将index值的二进制位作为路径, 在树中进行遍历。从高位到低位, index的每若干位被用来决定在树的当前节点中选择哪个分支(槽, slot)进入下一层。

  1. 路径查找与创建: 函数首先调用内部辅助函数__radix_tree_create。这个辅助函数会沿着index指定的路径在树中行进。如果路径上的任何一个中间节点(radix_tree_node)不存在, 它会自动分配内存并创建这个节点, 从而确保路径是完整的。最终, 它会返回一个指向目标槽位(slot)的指针。
  2. 条目放置: 找到目标槽位后, 它会将用户提供的item指针存入该位置。
  3. 状态断言: 在插入成功后, 它会执行一系列BUG_ON断言, 检查与新插入条目关联的”标签(tags)”是否都为0。标签是基数树提供的一种额外机制, 用于标记条目的状态(例如”脏”、”回写”等)。此处的断言确保了一个新条目在初始时没有任何状态标签, 这是一个重要的完整性校验。

在STM32H750这样的嵌入式系统中, pinctrl驱动程序正是利用基数树来管理其所有的物理引脚。它使用引脚的编号(一个整数)作为index, 将指向内核内部引脚描述符(pin_desc)的指针作为item。这提供了一种非常高效的方式来根据引脚编号快速查找到其详细信息, 即使引脚编号是稀疏的(例如, 一个64引脚的芯片可能只使用了0-63范围内的部分编号), 基数树也能有效地利用内存。当__radix_tree_create需要分配新节点时, 它会使用GFP_KERNEL, 这在单核抢占式系统上是安全的, 意味着内存分配过程在需要时可以休眠。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
/**
 *	radix_tree_insert    -    向一个基数树中插入条目
 *	@root:		基数树的根
 *	@index:		索引键
 *	@item:		要插入的条目
 *
 *	在 @index 指定的位置, 向基数树中插入一个条目.
 */
int radix_tree_insert(struct radix_tree_root *root, unsigned long index,
			void *item)
{
	/*
	 * 定义一个指向基数树节点的指针 node. 它将指向包含目标槽位的节点.
	 */
	struct radix_tree_node *node;
	/*
	 * 定义一个指向"被RCU保护的void指针"的指针 slot.
	 * 它将指向最终存放 item 的内存位置 (一个数组中的某个元素).
	 */
	void __rcu **slot;
	/*
	 * 定义一个整型变量 error, 用于存储函数调用的返回值.
	 */
	int error;

	/*
	 * BUG_ON 是一个断言宏. 如果条件为真, 内核会立即崩溃.
	 * radix_tree_is_internal_node 检查 item 指针的最低位是否被设置.
	 * 基数树内部使用最低位来区分一个槽位里存放的是用户数据, 还是指向下一层节点的内部指针.
	 * 此断言确保用户插入的条目没有被意外地标记为内部节点, 防止树结构被破坏.
	 */
	BUG_ON(radix_tree_is_internal_node(item));

	/*
	 * 调用内部辅助函数 __radix_tree_create, 这是插入操作的核心步骤之一.
	 * 它会根据 index 在树中查找路径, 如果路径上的节点不存在, 它会自动分配并创建它们.
	 * 执行成功后, node 将指向包含目标位置的节点, slot 将指向该目标位置的地址.
	 */
	error = __radix_tree_create(root, index, &node, &slot);
	/*
	 * 如果路径创建失败 (例如, 内存不足), 则直接返回错误码.
	 */
	if (error)
		return error;

	/*
	 * 调用内部辅助函数 insert_entries.
	 * 此函数负责将 item 指针安全地存放到由 node 和 slot 指定的位置.
	 */
	error = insert_entries(node, slot, item);
	/*
	 * 如果存放失败 (通常在更复杂的场景下, 此处不太可能失败), 返回错误码.
	 */
	if (error < 0)
		return error;

	/*
	 * 以下是一组插入后的完整性检查.
	 * 如果 node 不为 NULL, 说明条目被插入到了一个常规的 radix_tree_node 中.
	 */
	if (node) {
		/*
		 * 获取 item 在其所在节点 node 内的偏移量.
		 */
		unsigned offset = get_slot_offset(node, slot);
		/*
		 * 对三个可用的标签(tag)进行断言检查.
		 * 确保对于一个新插入的条目, 所有的标签位都必须是清除(0)的.
		 * 这是保证数据状态一致性的重要检查.
		 */
		BUG_ON(tag_get(node, 0, offset));
		BUG_ON(tag_get(node, 1, offset));
		BUG_ON(tag_get(node, 2, offset));
	} else {
		/*
		 * 如果 node 为 NULL, 说明树很小, 条目被直接插入到了 radix_tree_root 结构中.
		 * 同样检查并断言根节点中的标签位是清除的.
		 */
		BUG_ON(root_tags_get(root));
	}

	/*
	 * 插入成功, 返回 0.
	 */
	return 0;
}
/*
 * 将 radix_tree_insert 函数导出, 使其对其他内核模块可用.
 */
EXPORT_SYMBOL(radix_tree_insert);