[TOC]

lib/xarray.c eXtensible Array (XArray) 可扩展数组

历史与背景

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

XArray（eXtensible Array，可扩展数组）的诞生是为了替代并改进Linux内核中一个非常重要但使用起来十分复杂的数据结构——Radix Tree。Radix Tree长期以来是内核（尤其是页缓存 page cache）用于管理稀疏长整型索引到指针映射的核心组件，但它存在诸多问题：

  • 复杂的API和使用模式：Radix Tree的API不够直观，开发者需要自行处理很多棘手的边界情况，比如存储NULL指针、处理特殊的“异常条目”（exceptional entries），以及管理并发访问的锁。这使得代码容易出错且难以维护。
  • 锁机制外部化：Radix Tree本身不提供锁机制，使用者必须在外部实现自己的锁来保护数据结构，这增加了驱动和子系统开发者的负担。
  • 内存预加载问题：为了在持有锁时避免睡眠（因分配内存可能导致睡眠），Radix Tree的使用者通常需要“预加载”节点内存，这种机制复杂且可能浪费内存。
  • 功能局限：Radix Tree API缺少一些常见的功能，如“比较并交换”（compare-and-swap）操作，导致多个使用者需要自己实现类似的逻辑。此外，它只能存储指针或特殊的“异常条目”，灵活性不足。

XArray被设计为一个全新的抽象层，它保留了Radix Tree高效的底层实现，但提供了一个更安全、更易用、功能更丰富的API，从根本上解决了上述问题。

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

  • 首次提出：XArray由Matthew Wilcox提出，旨在通过提供一个更现代化的API来简化内核开发并减少错误。
  • 合入内核主线：经过多次迭代和审查，XArray最终在Linux 4.20版本左右被合入主线内核。最初的合入包含了XArray的实现，并立刻转换了内核中最复杂、最重要的Radix Tree用户——页缓存（page cache）。
  • 持续替代：在被合入之后，内核社区持续将其他使用Radix Tree和IDR（一种基于Radix Tree的ID分配机制）的子系统迁移到XArray上。

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

XArray现在是Linux内核中用于管理稀疏索引到指针映射的标准和首选数据结构。它已经完全取代了Radix Tree在内核新代码中的地位，并且大量旧代码也已被迁移。

  • 核心应用：页缓存（page cache）是其最重要和最复杂的用户。
  • 广泛使用：它也被用于IDR（ID Allocator）的替代实现、I/O子系统（如io_uring）、内存管理等多个关键领域。
  • API演进：它的API被认为是后续新数据结构（如Maple Tree）设计的范本。

核心原理与设计

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

XArray在概念上表现为一个可以自动扩容的、巨大的指针数组，其索引是unsigned long类型。 尽管其外部表现为数组，但其内部实现仍然基于经过优化的Radix Tree结构。

  1. 树状结构：与Radix Tree类似，XArray使用多级树来存储数据。索引（一个长整型）被拆分成多个比特块，每个比特块用于在树的一层中选择一个槽（slot）。通过逐层向下遍历，最终可以定位到与完整索引对应的指针。
  2. 动态分配：XArray初始时不占用任何内存。当第一次向某个索引存储数据时，它会按需分配树节点。这使得它对于存储稀疏索引（索引之间间隔很大）非常高效。
  3. 内置锁：XArray结构体中内嵌了一个自旋锁（spinlock），其API（如 xa_store()、xa_erase()）会自动处理加锁和解锁，极大地简化了并发编程。
  4. RCU安全查找：查找操作（xa_load()）是无锁的，并且利用了RCU（Read-Copy-Update）机制，允许读操作与写操作并行，提高了并发性能。

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

  • API简洁安全：提供了类似数组的xa_load()和xa_store()接口，隐藏了树操作的复杂性。内置的锁机制避免了大量并发相关的bug。
  • 功能丰富：
    • 支持多种数据类型：除了指针，还可以直接存储整数值（通过xa_mk_value()）和带标签的指针。
    • 处理NULL值：可以清晰地区分“从未使用的索引”和“存储了NULL指针的索引”，后者可以用于预留位置。
    • 多索引条目：支持将一个条目存储到一段连续的索引范围内，对这段范围内的任何索引进行查找都会返回同一个条目。
  • 高性能：查找操作无锁且RCU安全。对于密集索引的场景，其缓存效率很高。
  • 高效的内存使用：按需分配节点，对于稀疏数据非常节省内存。

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

  • 不适合哈希索引：XArray对连续或聚集的索引表现最优。如果将对象的哈希值作为索引，会导致索引分布稀疏且随机，这会降低其性能和内存效率，因为可能需要创建很深的树来存储单个条目。
  • 索引范围限制：索引必须是unsigned long类型，无法支持更大的索引范围。
  • 非最优的范围操作：虽然支持存储多索引条目，但对于需要高效进行大量范围操作（如查找所有与某个范围重叠的条目）的场景，新的Maple Tree数据结构可能更优。

使用场景

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

XArray是内核中将长整型ID映射到指针的通用首选方案，特别适用于ID稀疏分布的场景。

  • 例一：文件页缓存（Page Cache）
    这是XArray最经典的应用。当内核需要读写文件时，它将文件的页偏移量（一个pgoff_t，本质上是unsigned long）作为索引，将指向内存中对应struct page的指针存储在文件的i_pages XArray中。由于用户可能只访问了大文件中的某几部分，这些页偏移量是稀疏的，XArray能高效地管理这种映射。
  • 例二：ID分配器（IDR）
    内核需要为各种对象（如IPC对象、网络设备等）分配唯一的32位整数ID。新的IDR实现就基于XArray，它使用XArray来查找一个未被使用的ID（即XArray中为NULL的索引），并将该ID与指向内核对象的指针关联起来。
  • 例-三：I/O环形缓冲区（io_uring）
    io_uring接口允许用户空间和内核通过一个共享的环形缓冲区高效地提交I/O请求。内核端使用XArray来管理注册的文件描述符，将用户提供的fd作为索引，映射到内部的struct file指针。

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

  • 密集的小范围整数ID：如果需要管理的ID是密集的、从0开始且范围不大（例如，小于几千），那么使用普通的数组（void *array[]）会比XArray更简单、更快，因为它没有树遍历的开销。
  • 基于字符串或复杂键的查找：XArray是基于整数索引的。如果需要通过字符串或其他复杂结构作为键来查找对象，应该使用哈希表（hashtable）。
  • 需要高效范围扫描的场景：如前所述，对于以范围为核心操作的内存管理场景（例如，管理一个进程的虚拟内存区域VMA），红黑树（rbtree）或新的Maple Tree通常是更好的选择。

对比分析

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

特性 XArray Radix Tree (已被取代) IDR (旧实现) 普通数组 哈希表
功能概述 用于稀疏长整型索引到指针映射的通用、安全且功能丰富的数据结构。 Radix Tree的底层实现，API复杂且不安全。 基于Radix Tree的32位整数ID分配和查找机制。 用于密集、小范围索引的简单指针数组。 用于任意类型键到值的映射，通过哈希函数定位。
实现方式 优化的多级Radix Tree。 多级Radix Tree。 Radix Tree + 位图进行ID分配。 连续的内存块。 哈希函数 + 桶数组（通常是链表或树）。
API与安全性 非常高。API简洁，内置锁，RCU安全查找。 低。API复杂，需要外部锁，易用错。 中等。API专用，比Radix Tree简单，但不如XArray通用。 非常高。就是原生数组访问。 中等。需要提供好的哈希函数和处理冲突。
稀疏索引支持 优秀。专为此设计，内存效率高。 优秀。 优秀。 差。会浪费大量空间存储空指针。 优秀。
性能开销 查找为对数时间复杂度，但常数因子小。插入/删除有锁开销。 与XArray底层类似，但API使用不当会引入额外开销。 与Radix Tree类似。 常数时间 O(1)，非常快。 平均为常数时间 O(1)，最差为O(n)。
资源占用 与存储的条目数量成正比，非常节省。 与XArray类似。 与Radix Tree类似。 与索引范围最大值成正比，可能非常浪费。 需要预分配桶数组，占用固定内存。
典型用途 页缓存、新IDR、io_uring、文件描述符管理。 (历史) 页缓存、旧IDR。 (历史) IPC对象ID、设备ID分配。 进程的文件描述符表（files_struct中的fd_array）。 dentry缓存、网络连接跟踪。

include/linux/xarray.h

XARRAY_INIT

1
2
3
4
5
#define XARRAY_INIT(name, flags) {				\
	.xa_lock = __SPIN_LOCK_UNLOCKED(name.xa_lock),		\
	.xa_flags = flags,					\
	.xa_head = NULL,					\
}

xa_init_flags 初始化带有标志的空 XArray

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * xa_init_flags() - 初始化带有标志的空 XArray。
 * @xa: XArray.
 * @flags: XA_FLAG values.
 *
 * 如果您需要使用特殊标志初始化 XArray（例如，您需要从中断上下文中获取锁），请使用此函数而不是 xa_init（）。
 *
 * Context: Any context.
 */
static inline void xa_init_flags(struct xarray *xa, gfp_t flags)
{
	spin_lock_init(&xa->xa_lock);
	xa->xa_flags = flags;
	xa->xa_head = NULL;
}

xa_init 初始化一个空的 XArray

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * xa_init() - 初始化一个空的 XArray.
 * @xa: XArray.
 *
 * An empty XArray is full of NULL entries.
 *
 * Context: Any context.
 */
static inline void xa_init(struct xarray *xa)
{
	xa_init_flags(xa, 0);
}

xa_marked 检查 XArray 中是否有任何条目设置了特定标记

1
2
3
4
5
6
7
8
9
10
11
12
/**
* xa_marked（） - 查询此数组中的任何条目是否具有标记集
 * @xa：数组
 * @mark：标记值
 *
 * 上下文：任何上下文。
 * 如果任何条目设置了此标记，则返回： %true。
 */
static inline bool xa_marked(const struct xarray *xa, xa_mark_t mark)
{
	return xa->xa_flags & XA_FLAGS_MARK(mark);
}

xas_retry 用于判断是否需要重试 XArray 操作，并在必要时重置操作状态（xa_state）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * xas_retry（） - 如果合适，请重试该作。
 * @xas：XArray作状态。
 * @entry：来自 xarray 的条目。
 *
 * 高级函数有时可能会返回内部条目，例如重试条目或零条目。 此函数将 @xas 设置为根据需要从数组的头部重新启动 walk。
 *
 * 上下文：任何上下文。
 * 返回：如果需要重试作，则为 true。
 */
static inline bool xas_retry(struct xa_state *xas, const void *entry)
{
	/* entry 是一个零条目（表示空或无效的条目） */
	if (xa_is_zero(entry))
		return true;
	/* entry 不是一个重试条目， */
	if (!xa_is_retry(entry))
		return false;
	/* entry 是一个重试条目，调用 xas_reset 重置操作状态，使 xa_state 从数组的头部重新开始遍历 */
	xas_reset(xas);
	return true;
}

xas_reload 重新获取 XArray 中指定位置的条目

  • 主要用途是验证之前加载的条目是否仍然保持相同的值，特别是在无锁的页面缓存查找场景中。通过重新加载条目，函数确保操作的正确性和一致性
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
/**
 * xas_reload（） - 从 xarray 中重新获取条目。
 * @xas：XArray作状态。
 *
 * 使用此函数可检查先前加载的条目是否仍具有相同的值。 
 * 这对于无锁页面缓存查找很有用，在无锁中，我们只使用 RCU 锁遍历数组以保护我们，
 * 锁定页面，然后检查页面在我们查找后是否没有移动。
 *
 * 调用方保证 @xas 仍然有效。 如果它可能处于错误或重启状态，请改为调用 xas_load（）。
 *
 * Return：xarray 中此位置的条目。
 */
static inline void *xas_reload(struct xa_state *xas)
{
	struct xa_node *node = xas->xa_node;
	void *entry;
	char offset;
	/* 处理空节点的特殊情况 */
	if (!node)
		return xa_head(xas->xa);
	if (IS_ENABLED(CONFIG_XARRAY_MULTI)) {
		offset = (xas->xa_index >> node->shift) & XA_CHUNK_MASK;
		entry = xa_entry(xas->xa, node, offset);
		if (!xa_is_sibling(entry))
			return entry;
		offset = xa_to_sibling(entry);
	} else {
		/* 未启用多节点支持，直接使用操作状态中的偏移量（xa_offset） */
		offset = xas->xa_offset;
	}
	/* 返回节点中的条目 */
	return xa_entry(xas->xa, node, offset);
}

lib/xarray.c

xa_entry 获取xa_entry条目

1
2
3
4
5
6
7
8
/* Private */
static inline void *xa_entry(const struct xarray *xa,
				const struct xa_node *node, unsigned int offset)
{
	XA_NODE_BUG_ON(node, offset >= XA_CHUNK_SIZE);
	return rcu_dereference_check(node->slots[offset],
						lockdep_is_held(&xa->xa_lock));
}

xas_descend 在 XArray 数据结构中从当前节点向下遍历到子节点或获取目标条目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
static __always_inline void *xas_descend(struct xa_state *xas,
					struct xa_node *node)
{
	unsigned int offset = get_offset(xas->xa_index, node);
	void *entry = xa_entry(xas->xa, node, offset);

	xas->xa_node = node;
	while (xa_is_sibling(entry)) {/* 兄弟节点 */
		offset = xa_to_sibling(entry);	/* 获取兄弟节点的偏移量 */
		entry = xa_entry(xas->xa, node, offset);/*  获取兄弟节点对应的条目 */
		/* 如果当前节点的层级非叶子节点（node->shift 非零）且条目是另一个节点（通过 xa_is_node(entry) 检查） */
		if (node->shift && xa_is_node(entry))
			/* 条目设置为 XA_RETRY_ENTRY，表示需要重新尝试 */
			entry = XA_RETRY_ENTRY;
	}

	xas->xa_offset = offset;
	return entry;
}

xas_reload 从xarray中重新获取一个条目

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
/**
 * xas_reload() - 从xarray中重新获取一个条目。
 * @xas: XArray operation state.
 *
 * Use this function to check that a previously loaded entry still has
 * the same value.  This is useful for the lockless pagecache lookup where
 * we walk the array with only the RCU lock to protect us, lock the page,
 * then check that the page hasn't moved since we looked it up.
 *
 * The caller guarantees that @xas is still valid.  If it may be in an
 * error or restart state, call xas_load() instead.
 *
 * Return: The entry at this location in the xarray.
 */
static inline void *xas_reload(struct xa_state *xas)
{
	struct xa_node *node = xas->xa_node;
	void *entry;
	char offset;

	if (!node)
		return xa_head(xas->xa);
	if (IS_ENABLED(CONFIG_XARRAY_MULTI)) {/* 支持多索引条目 */
		offset = (xas->xa_index >> node->shift) & XA_CHUNK_MASK;
		entry = xa_entry(xas->xa, node, offset);
		if (!xa_is_sibling(entry))
			return entry;
		offset = xa_to_sibling(entry);
	} else {
		offset = xas->xa_offset;
	}
	return xa_entry(xas->xa, node, offset);
}

xas_start 初始化或重新加载 xa_state（XArray 操作状态）以开始遍历 XArray 数据结构

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
/*
 * 开始一次遍历。如果 @xas 已经有效，我们假设它在正确的路径上，只需返回我们到达的位置。
 * 如果我们处于错误状态，返回 NULL。如果索引超出了当前 xarray 的范围，返回 NULL，而不更改 @xas->xa_node。
 * 否则，将 @xas->xa_node 设置为 NULL，并返回数组的当前头部。
 */
static void *xas_start(struct xa_state *xas)
{
	void *entry;

	if (xas_valid(xas))
		return xas_reload(xas);
	if (xas_error(xas))
		return NULL;
	/* 获取 XArray 的头部条目 */
	entry = xa_head(xas->xa);
	if (!xa_is_node(entry)) {
		/* 头部条目不是节点 如果当前索引 xas->xa_index 不为 0 */
		if (xas->xa_index)
			/* 设置边界 */
			return set_bounds(xas);
	} else {
		/* 查索引是否超出当前节点的范围 */
		if ((xas->xa_index >> xa_to_node(entry)->shift) > XA_CHUNK_MASK)
			/* 设置边界 */
			return set_bounds(xas);
	}

	xas->xa_node = NULL;
	return entry;
}

xa_load 加载XArray

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
/**
 * xas_load() - 从 XArray 加载一个条目（高级）。 
 * @xas: XArray 操作状态。 * 
 * 通常会遍历 @xas 到适当状态以加载存储在 xa_index 的条目。然而，如果 @xas 处于错误状态，它将不会执行任何操作并返回 %NULL。xas_load() 不会扩展树。 * 
 * 如果 xa_state 设置为操作多索引条目，xas_load() 可能返回 %NULL 或内部条目，即使 @xas 指定的范围内存在条目。 * 
 * 上下文：任何上下文。调用者应持有 xa_lock 或 RCU 锁。 
 * 返回：通常是 XArray 中的一个条目，但请参阅描述中的例外情况。
 */
void *xas_load(struct xa_state *xas)
{
	/* 根据 xas 的状态获取初始条目 */
	void *entry = xas_start(xas);

	while (xa_is_node(entry)) {
		struct xa_node *node = xa_to_node(entry);
		/* 检查当前节点的层级（node->shift）是否与 xas->xa_shift 匹配。如果 xas->xa_shift 大于 node->shift，说明已经到达目标层级，退出循环 */
		if (xas->xa_shift > node->shift)
			break;
		/* 调用 xas_descend(xas, node) 进入子节点，继续遍历 */
		entry = xas_descend(xas, node);
		if (node->shift == 0)
			break;
	}
	return entry;
}
EXPORT_SYMBOL_GPL(xas_load);

xas_store 将此条目存储在 XArray 中

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
/**
 * xas_store() - 将此条目存储在 XArray 中。
 * @xas: XArray operation state.
 * @entry: New entry.
 *
 * 如果 @xas 在多重索引条目上操作，则该函数返回的条目基本上是毫无意义的（它可能是内部条目，或者可能是 %NULL，即使在范围覆盖的某些索引中有非 NULL 条目）。这对当前用户没有问题，如果需要可以进行更改。
 *
 * Return: The old entry at this index.
 */
void *xas_store(struct xa_state *xas, void *entry)
{
	struct xa_node *node;
	void __rcu **slot = &xas->xa->xa_head;
	unsigned int offset, max;
	int count = 0;
	int values = 0;
	void *first, *next;
	bool value = xa_is_value(entry);

	/* 如果 entry 非空，调用 xas_create 创建必要的节点或结构以存储条目 */
	if (entry) {
		bool allow_root = !xa_is_node(entry) && !xa_is_zero(entry);
		first = xas_create(xas, allow_root);
	} else {
		first = xas_load(xas);
	}-+

	if (xas_invalid(xas))
		return first;
	node = xas->xa_node;
	if (node && (xas->xa_shift < node->shift))
		xas->xa_sibs = 0;
	if ((first == entry) && !xas->xa_sibs)
		return first;

	next = first;
	offset = xas->xa_offset;
	max = xas->xa_offset + xas->xa_sibs;
	if (node) {
		slot = &node->slots[offset];
		if (xas->xa_sibs)
			xas_squash_marks(xas);
	}
	if (!entry)
		xas_init_marks(xas);

	for (;;) {
		/*
		 * Must clear the marks before setting the entry to NULL,
		 * otherwise xas_for_each_marked may find a NULL entry and
		 * stop early.  rcu_assign_pointer contains a release barrier
		 * so the mark clearing will appear to happen before the
		 * entry is set to NULL.
		 */
		rcu_assign_pointer(*slot, entry);
		if (xa_is_node(next) && (!node || node->shift))
			xas_free_nodes(xas, xa_to_node(next));
		if (!node)
			break;
		count += !next - !entry;
		values += !xa_is_value(first) - !value;
		if (entry) {
			if (offset == max)
				break;
			if (!xa_is_sibling(entry))
				entry = xa_mk_sibling(xas->xa_offset);
		} else {
			if (offset == XA_CHUNK_MASK)
				break;
		}
		next = xa_entry_locked(xas->xa, node, ++offset);
		if (!xa_is_sibling(next)) {
			if (!entry && (offset > max))
				break;
			first = next;
		}
		slot++;
	}

	update_node(xas, node, count, values);
	return first;
}
EXPORT_SYMBOL_GPL(xas_store);

xas_find_marked 在 XArray 数据结构中查找具有特定标记（mark）的下一个条目

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
94
95
96
/**
 * xas_find_marked（） - 在 XArray 中查找下一个标记的条目。
 * @xas：XArray作状态。
 * @max：要返回的最高索引。
 * @mark：标记要搜索的号码。
 *
 * 如果@xas尚未遍历到条目，则返回索引为 >= xas.xa_index的标记条目。 如果已遍历，则当前指向的 entry 已被处理，因此我们返回索引> xas.xa_index的第一个标记条目。
 *
 * 如果未找到标记的条目并且数组小于 @max，则@xas设置为 bounds 状态，并将 xas->xa_index 设置为数组中尚未达到的最小索引。 这允许立即传递 @xas toxas_store（）。
 *
 * 如果在到达 @max 之前未找到任何条目，则@xas设置为重新启动状态。
 *
 * 返回：条目（如果找到），否则为 %NULL。
 */
void *xas_find_marked(struct xa_state *xas, unsigned long max, xa_mark_t mark)
{
	bool advance = true;
	unsigned int offset;
	void *entry;

	if (xas_error(xas))
		return NULL;
	if (xas->xa_index > max)
		goto max;

	/* 如果当前节点为空或是顶层节点，函数初始化索引或处理顶层节点的条目。 */
	if (!xas->xa_node) {
		xas->xa_index = 1;
		goto out;
	} else if (xas_top(xas->xa_node)) {
		/* 顶层节点包含标记 */
		advance = false;
		entry = xa_head(xas->xa);
		xas->xa_node = NULL;
		if (xas->xa_index > max_index(entry))
			goto out;
		if (!xa_is_node(entry)) {
			if (xa_marked(xas->xa, mark))
				return entry;
			xas->xa_index = 1;
			goto out;
		}
		xas->xa_node = xa_to_node(entry);
		xas->xa_offset = xas->xa_index >> xas->xa_node->shift;
	}

	while (xas->xa_index <= max) {
		if (unlikely(xas->xa_offset == XA_CHUNK_SIZE)) {
			xas->xa_offset = xas->xa_node->offset + 1;
			xas->xa_node = xa_parent(xas->xa, xas->xa_node);
			if (!xas->xa_node)
				break;
			advance = false;
			continue;
		}

		if (!advance) {
			entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);
			if (xa_is_sibling(entry)) {
				xas->xa_offset = xa_to_sibling(entry);
				xas_move_index(xas, xas->xa_offset);
			}
		}
		/* 查找当前节点中的标记条目，并更新偏移量和索引 */
		offset = xas_find_chunk(xas, advance, mark);
		if (offset > xas->xa_offset) {
			advance = false;
			xas_move_index(xas, offset);
			/* Mind the wrap */
			if ((xas->xa_index - 1) >= max)
				goto max;
			xas->xa_offset = offset;
			if (offset == XA_CHUNK_SIZE)
				continue;
		}

		entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);
		if (!entry && !(xa_track_free(xas->xa) && mark == XA_FREE_MARK))
			continue;
		if (xa_is_sibling(entry))
			continue;
		if (!xa_is_node(entry))
			return entry;
		xas->xa_node = xa_to_node(entry);
		xas_set_offset(xas);
	}

out:
	if (xas->xa_index > max)
		goto max;
	return set_bounds(xas);
max:
	xas->xa_node = XAS_RESTART;
	return NULL;
}
EXPORT_SYMBOL_GPL(xas_find_marked);

xas_find_marked

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
94
95
96
97
98
99
100
101
/**
 * xas_find_marked() - Find the next marked entry in the XArray.
 * @xas: XArray operation state.
 * @max: Highest index to return.
 * @mark: Mark number to search for.
 *
 * If the @xas has not yet been walked to an entry, return the marked entry
 * which has an index >= xas.xa_index.  If it has been walked, the entry
 * currently being pointed at has been processed, and so we return the
 * first marked entry with an index > xas.xa_index.
 *
 * If no marked entry is found and the array is smaller than @max, @xas is
 * set to the bounds state and xas->xa_index is set to the smallest index
 * not yet in the array.  This allows @xas to be immediately passed to
 * xas_store().
 *
 * If no entry is found before @max is reached, @xas is set to the restart
 * state.
 *
 * Return: The entry, if found, otherwise %NULL.
 */
void *xas_find_marked(struct xa_state *xas, unsigned long max, xa_mark_t mark)
{
	bool advance = true;
	unsigned int offset;
	void *entry;

	if (xas_error(xas))
		return NULL;
	if (xas->xa_index > max)
		goto max;

	if (!xas->xa_node) {
		xas->xa_index = 1;
		goto out;
	} else if (xas_top(xas->xa_node)) {
		advance = false;
		entry = xa_head(xas->xa);
		xas->xa_node = NULL;
		if (xas->xa_index > max_index(entry))
			goto out;
		if (!xa_is_node(entry)) {
			if (xa_marked(xas->xa, mark))
				return entry;
			xas->xa_index = 1;
			goto out;
		}
		xas->xa_node = xa_to_node(entry);
		xas->xa_offset = xas->xa_index >> xas->xa_node->shift;
	}

	while (xas->xa_index <= max) {
		if (unlikely(xas->xa_offset == XA_CHUNK_SIZE)) {
			xas->xa_offset = xas->xa_node->offset + 1;
			xas->xa_node = xa_parent(xas->xa, xas->xa_node);
			if (!xas->xa_node)
				break;
			advance = false;
			continue;
		}

		if (!advance) {
			entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);
			if (xa_is_sibling(entry)) {
				xas->xa_offset = xa_to_sibling(entry);
				xas_move_index(xas, xas->xa_offset);
			}
		}

		offset = xas_find_chunk(xas, advance, mark);
		if (offset > xas->xa_offset) {
			advance = false;
			xas_move_index(xas, offset);
			/* Mind the wrap */
			if ((xas->xa_index - 1) >= max)
				goto max;
			xas->xa_offset = offset;
			if (offset == XA_CHUNK_SIZE)
				continue;
		}

		entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);
		if (!entry && !(xa_track_free(xas->xa) && mark == XA_FREE_MARK))
			continue;
		if (xa_is_sibling(entry))
			continue;
		if (!xa_is_node(entry))
			return entry;
		xas->xa_node = xa_to_node(entry);
		xas_set_offset(xas);
	}

out:
	if (xas->xa_index > max)
		goto max;
	return set_bounds(xas);
max:
	xas->xa_node = XAS_RESTART;
	return NULL;
}
EXPORT_SYMBOL_GPL(xas_find_marked);

__xa_alloc 在 XArray 中分配一个新的条目

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
/**
 * __xa_alloc() - 在XArray中找到存储此条目的位置。
 * @xa: XArray。
 * @id: ID指针。
 * @limit: 分配ID的范围。
 * @entry: 新条目。
 * @gfp: 内存分配标志。
 *
 * 在@limit.min和@limit.max之间的@xa中找到一个空条目，
 * 将索引存储到@id指针中，然后将条目存储在该索引处。
 * 并发查找不会看到未初始化的@id。
 *
 * 仅可操作于使用标志XA_FLAGS_ALLOC通过xa_init_flags()初始化的xarray。
 *
 * 上下文：任何上下文。 进入时需要持有xa_lock。如果@gfp标志允许，
 * 可能会释放并重新获取xa_lock。
 * 返回值：成功返回0；如果无法分配内存，则返回-ENOMEM；
 * 如果@limit中没有空闲条目，则返回-EBUSY。
 */
int __xa_alloc(struct xarray *xa, u32 *id, void *entry,
		struct xa_limit limit, gfp_t gfp)
{
	XA_STATE(xas, xa, 0);
	/* 检查 entry 是否为高级条目 */
	if (WARN_ON_ONCE(xa_is_advanced(entry)))
		return -EINVAL;
	/* 检查 XArray 是否启用了空闲跟踪 */
	if (WARN_ON_ONCE(!xa_track_free(xa)))
		return -EINVAL;

	/* 将其设置为默认条目 XA_ZERO_ENTRY */
	if (!entry)
		entry = XA_ZERO_ENTRY;

	do {
		/* 从 limit.min 开始查找标记为空闲（XA_FREE_MARK）的索引 */
		xas.xa_index = limit.min;
		xas_find_marked(&xas, limit.max, XA_FREE_MARK);
		if (xas.xa_node == XAS_RESTART)
			xas_set_err(&xas, -EBUSY);
		else
			*id = xas.xa_index;
		xas_store(&xas, entry);
		xas_clear_mark(&xas, XA_FREE_MARK);
	} while (__xas_nomem(&xas, gfp));/* 如果内存不足，调用 __xas_nomem 处理内存分配。 */

	return xas_error(&xas);
}
EXPORT_SYMBOL(__xa_alloc);