type
status
date
slug
summary
tags
category
icon
password
URL
1. 背景
有些内核数据结构被证明不足以很好地完成其预期任务，问题可能出在用于访问它的 API 中。Matthew Wilcox 在 2018 年演讲表明，对于内核古老的基数树（radix tree）数据结构正是如此。
内核的基数树是一种很棒的数据结构，但它的用户比预期的要少得多。相反，各种内核子系统已经实现了自己的数据结构来解决相同的问题。问题在于基数树的 API 不好；它不适合内核中的实际用例。内核 4.20 版本之后 radix tree 便被 xarray 结构所替代。
2. radix tree 的不足
Matthew Wilcox 认为内核的基数树的 API 设计不合理，主要表现为：
1）“树” 术语在这种情况下令人困惑。基数树并不像人们在数据结构教科书中找
的经典树。例如，几十年来，将项目添加到树中一直被称为 “插入”，但“插入” 并不能真正 描述基数树发生的情况，尤其是当具有给定键的项目已经存在时。基数树还支持诸如 “异常 entry” 之类的概念，用户会因为使用的命名而感到害怕。
2）基数树需要用户自己加锁；
Matthew Wilcox 决定修复接口。保持现有的基数树数据结构不变；基数树数据结构本身没有问题。现在接口暗示用户，把它当做数组来用，而不是当做树来用。因为基数树看起来就像是一个自动增长的数组：一个用 unsigned long 来索引的指针数组。这种视图，更好地描述了基数树的用途。
相对应的，XArray 做了以下修改：
XArray 默认自己处理了锁，简化了使用。基数树的 “预加载” 机制允许用户获取锁之前先预先分配内存，这个机制在 XArray 中被取消了，它太复杂又没有太多实际价值。XArray API 被分为两部分，普通 API 和高级 API。后者给用户更多可控性，比如用户可以显式管理锁。API 可以用于不同的场景，满足不同的需求。比如 Page Cache 就可以用 XArray。普通 API 完全在高级 API 的基础上实现，所以普通 API 也是高级 API 的使用范例。
3. 应用场景
xarray 数据结构主要的应用场景是在文件缓存。我们知道在 Linux 内核中，为了加快文件的访问速度，将空闲的内存页就用做了磁盘的 cache。一个文件的缓存通过 address_space 数据结构进行管理，而这里面用于记录文件数据与内存页之间映射关系的数据结构就是采用了 xarray。
当每次需要访问文件的数据时，都需要先查找这个缓存表，所以它的最重要的需求就是查找速度要快。如果把文件的偏移看作是虚拟地址，那么这个表其实做的事情就是——虚拟地址到内存页 的映射。这不就是虚拟内存的页表所做的事情吗？所以其实 xarray 就是类似于内存的页表结构，二者的区别就是 xarray 的 “地址” 范围是可变的，而页表的地址范围是固定的（CPU 的寻址位宽决定）。
3. 数据结构
xarray 这个数据结构主要由两个结构体：
- xa_node
成员含义说明：
成员 | 含义 |
shift | 指定当前 xa_node 的 slots 数组中成员的单位，当 shift 为 0 时，说明当前 xa_node 的 slots 数组中成员为叶子节点，当 shift 为 6 时，说明当前 xa_node 的 slots 数组中成员指向的 xa_node 可以最多包含 2^6(即 64）个节点 |
offset | xa_node 在父节点的 slots 数组中的偏移 |
count | xa_node 有多少个 slots 已经被使用 |
nr_values | xa_node 有多少个 slots 存储的 Value Entry |
parent | 指向该 xa_node 的父节点 |
array | array 成员指向该 xa_node 所属的 xarray |
slots | slots 是个指针数组，该数组既可以存储下一级的节点, 也可以用于存储即将插入的对象指针 |
- xarray
光看这个数据结构没有什么感觉，那就让我们来看看当 XA_CHUNK_SHIFT = 4 时，一个 xarray 会是什么样子。
从图可以看到：
1) XA_CHUNK_SIZE 表示了一个 xa_node 节点可以表示的最大数量槽位2) offset 表示了自己在父节点上的位置3) shift 表示了自己在数字中表示第几段数字
总的来讲和页表很像。有了这个数据结构在心里，有些函数就相对比较容易理解了。
4. 技术原理
XArray 是一种抽象的数据类型，其行为类似于一个非常大的指针数组。它满足了与散列或常规可调整大小的数组相同的许多需求。与散列不同，它允许您以高效缓存的方式明智地转到下一个或上一个条目。与可调整大小的阵列相比，无需为了扩展阵列而复制数据或更改 MMU 映射。与双向链接列表相比，它具有更高的内存效率，可并行性和缓存友好性。它利用 RCU 来执行查找而无需锁定。
Xarray 在 linux 下的图解：
上面描述了 xarray 的 3 次插入过程，随着插入的 index 增大，树的深度也一级一级的增长。显而易见，树的深度越小，树的查找速度就越快。按照内核默认的每个结点 64 个 slot，那么只需要一个深度为 7 的树（64 的 7 次方），就可以覆盖 4T 的地址（也就可以索引 4T 大小的文件缓存）。
5. API 介绍
5.1 状态判断
理解一下 slots 中存放的 Entry 的规则
slots 中存储的 entry 中的低两位决定了 Xarray 如何解析其内容。
低 2 位是 00 时：它是一个 Pointer Entry低 2 位是 10 时：它是一个 Internal Entry，一般指向下一级的 xa_node.低 2 为是 x1 时：它是一个 Value Entry，或者 tagged pointer
具体可以参考代码注释:
基于上面规则, 代码中有两套判断状态的辅助函数:
1) 判断 entry 的 xa_is_xxx()
xa_is_value
xa_is_internal
- xa_is_sibling
xa_is_retry
xa_is_zero
xa_is_node
xa_is_err
5.2 判断 xas 的 xas_xxx()
xas->xa_node 中编码 errnos, 如下所示：
xas_invalid
xas_frozen
xas_top
xas_is_node
xas_error
6. 关键 API
6.1 定义 xarray
6.2 将值存储到 XArray 中
这个函数会把参数给出的 entry，放到请求的 index 这个地方。如果要 XArray 需要分配内存，会使用给定的 gfp 来分配。如果成功，返回值是之前存放在 index 的值。
xa_store 的变体有以下 2 个:
xa_insert 用于存放但不覆盖现有的 entry
xa_cmpxchg，只有当存的值和 old 参数匹配上时，才会将 entry 存在 index 处。
6.3 删除一个 entry
删除一个 entry 可以通过 xa_store 存放 NULL 来实现，或者调用以下接口：
6.4 从 XArray 里取出一个值
返回值是存放在 index 处的值。XArray 里，空 entry 和存入 NULL 的 entry 是等价的。因此 xa_load 不会对空 entry 有特殊的处理。
6.5 标签管理函数
非空 entry 上还可以设置最多 3 个比特的标签，标签管理函数：
6.6 查找多个非空项
XArray 是很稀疏的，因此一个普遍的准则是，不要进行低效的遍历查找非空项。要查找多个非空项，应该使用这个宏：
在进入循环之前，需要把 index 设为遍历的起点，max 设为遍历的最大 index，filter 指定需要过滤的 mark。 循环执行时，index 会被设为当前匹配到的 entry。可以在循环里修改 index，来改变迭代过程。修改 XArray 自身也是允许的。
6.7 删除一个 Xarray 中所有的 Entry
7. 进阶 API
先进的 API 以接口为代价提供了更高的灵活性和更好的性能，而接口却可能更难使用且保护措施更少。高级 API 不会为您完成锁的操作，需要开发者自行在修改数组时使用 xa_lock。开发者可以选择在执行只读操作时使用 xa_lock 还是 RCU 锁。可以在混合使用高级操作和普通操作。实际上，普通 API 是根据进阶 API 实现的。进阶 API 仅适用于具有 GPL 兼容许可证的模块。
高级 API 基于 xa_state。这是一个不透明的数据结构，您可以使用 XA_STATE() 宏在堆栈上声明。该宏初始化了准备开始在 XArray 周围移动的 xa_state。它用作游标以维护 XArray 中的位置，并让您一起进行各种操作，而不必每次都从顶部重新启动。
8. 使用示例
Xarray 在 pagecache 中广泛使用， 下面以 filemap.c 中 find_get_pages_range 接口使用为示例呈现 xrarry 的使用示例。
8. 参考资料
https://wushifublog.com/2021/04/16/Linux-lib-%E4%B9%8B-xarray/