XArray 的全称为：eXtensible Arrays。看用途，明明是一个字典（有键值对），为什么名字里带着 Array 呢？可能是因为 key 不能是字符串，只能是 unsigned long 类型的。所以看起来就像是一个 Array 的下标，只不过这个 Array 非常大，可以有 unsigned long 可取值范围个元素。

XArray 是基于基数树（Radix Tree） 实现的一种数据结构。因为 key 是 unsigned long，所以其是根据二进制表示来作为前缀树里的前缀的。其实在 XArray 之前就是有 Radix Trie 的 API 的，只不过 Matthew Wilcox 认为内核的基数树的 API 设计不合理，比如：

• “树”这个术语就很有迷惑性。基数树跟传统的，教科书上那种树，并不是很像。举例来说，传统树上的增加 entry 的操作，一直都被称为“插入”。但对基数树而言，“插入”并不是字面上发生的事情，尤其是当 key 已经存在的时候。基数树也支持“异常 entry“，光是这个名字，就让用户听着不敢用了。
• 基数树还要求用户自己处理锁。

Wilcox 决定改良接口。基数树本身不变，它本身没什么问题。改变的是接口，现在接口暗示用户，把它当做数组来用，而不是当做树来用。因为基数树看起来就像是一个自动增长的数组：一个用 unsigned long 来索引的指针数组。这种视图，更好地描述了基数树的用途。

• XArray 默认自己处理了锁，简化了使用；
• 基数树的“预加载”机制允许用户获取锁之前先预先分配内存，这个机制在 XArray 中被取消了，它太复杂又没有太多实际价值。
• XArray API 被分为两部分，普通 API 和高级 API。后者给用户更多可控性，比如用户可以显式管理锁。API 可以用于不同的场景，满足不同的需求。比如 Page Cache 就可以用 XArray。普通 API 完全在高级 API 的基础上实现，所以普通 API 也是高级 API 的使用范例。

内核基础设施——XArray - Notes about linux and my work

一个新初始化的 XArray 在每个索引处都包含一个 NULL 指针。

XArray 是 resizable 的。XArray 是可以存普通的指针的。

XArray 还有一个 feature，它可以把很多个 index 组成的 range 看作是原子的。也就是说，这些 indexes share 同一个存储空间，在这个 range 内的任意一个 index 取或者存都是针对同一个数据进行的操作。

XArray 基础 API / XArray Normal API

Start by initializing an XArray, either

• with DEFINE_XARRAY() for statically allocated XArrays or
• xa_init() for dynamically allocated ones.

然后你可以用 xa_store() 来设置条目，用 xa_load() 来获取条目。

xa_insert()，在 index 处插入值，只有在此处为空时才成功。

Iterate using xa_for_each(), xa_for_each_start() or xa_for_each_range().

xa_find() or xa_find_after() 可以 iterate 到下一个不为空的地方。

xa_erase() 用来把一个 index 重新置 NULL。

Sometimes you need to ensure that a subsequent call to xa_store() will not need to allocate memory. The xa_reserve() function will store a reserved entry at the indicated index. Use xa_release() to cancel the reservation.

用完了需要 xa_destroy() 来 destroy：Finally, you can remove all entries from an XArray by calling xa_destroy().

为什么 XArray 的 value 需要是非负值？

因为最低位被用来当作一个 mark 标记使用了。这意味着原来的值需要左移一位，所以最高位会被丢掉，因此不能有数据。

static inline void *xa_mk_value(unsigned long v)
{
	WARN_ON((long)v < 0);
	return (void *)((v << 1) | 1);
}

xa_load() Kernel

如果没有存值怎么办？

XArray marks

Each entry in the array has three bits associated with it called marks. You can iterate over marked entries by using the xa_for_each_marked() iterator.

Setting or clearing a mark on any index of a multi-index entry will affect all indices covered by that entry. Querying the mark on any index will return the same result.

XArray — The Linux Kernel documentation

XArray 高级 API

高级 API 提供了更多的灵活性和更好的性能，但代价是接口可能更难使用，保障措施更少。

高级 API 是基于 xa_state 的。这是一个不透明的数据结构，你使用 XA_STATE() 宏在堆栈中声明。It is used as a cursor to maintain the position in the XArray and let you compose various operations together without having to restart from the top every time.

完整的 API 参考：XArray — The Linux Kernel documentation

完整的英文文档：XArray — The Linux Kernel documentation

The XArray data structure [LWN.net]

xas_retry

Internal entry

The XArray reserves some entries for its own purposes.

• These are never exposed through the normal API,
• but when using the advanced API, it's possible to see them.

Usually the best way to handle them is to pass them to xas_retry(), and retry the operation if it returns true.

xas.xa_index

当前 entry 的 index。

xa_to_value() Kernel

Get value stored in an XArray entry.

xas_next()

Move state to next index.