从 radix tree 到 xarray

今天我们来讨论一下内核中从radix tree到xarray结构的演变。radix tree现在普遍应用于page cache中，用于搜索页高速缓存。但是在Linux内核4.20版本之后便被xarray结构所替代。xarray数据结构是2018 LSFMM峰会上最后一个文件系统会议的主题。它是内核的基数树的一个新API。这个会议由Matthew Wilcox领导，是由他创造了xarray。这篇文章中我们会就page cache的含义到radix树的结构，再到xarray的兴起这一演变过程进行讲解。

一、page cache

CPU想要访问外部存储介质譬如磁盘上的文件，首先要将文件的内容拷贝到内存中，但是由于硬件或者软件设计上的限制，我们从磁盘到内存的传输速度比较慢，这时候我们便使用一些空余内存，也就是DDR上的一部分空间来缓存一部分磁盘上的文件内容，这个部分空余的内存我们就叫做page cache。用户启动read的系统调用之后，会从用户层到VFS层面之后再到文件系统中，在文件系统的读接口中会首先查看page cache中是否有用户需要的文件内容，如果有就直接读取，如果没有在通过IO操作下发请求从磁盘读取，然后放到page cache中，方便下次访问。

这个原理和CPU中的硬件cache有点像，不过硬件cache是CPU缓存内存的数据。因为内存有限我们不能缓存全部数据，只需要把调用的内容缓存起来就可以了，这种方式叫做demand paging（按需取页）。在page cache中缓存了很多的页，怎么查找和管理呢？这时候就要关注一下address_space结构体，一个address_space管理了一个文件在内存中缓存的所有pages，这部分缓存也是页高速缓存。这个address_space可不是进程虚拟地址空间的address space，但是两者之间也是有很多联系的。mmap映射会将文件的一部分内容映射到虚拟地址空间的VMA，如果有5个进程，每个进程mmap同一个文件两次（文件的不同部分），就会有10个VMA，但address_space只有一个，虚拟空间的VMA使用的是rbtree，下面会介绍到为什么不在rbtree上去做xarray。在inode的结构体中会有一个i_mapping指向这个结构体。下面看下这个结构体的内容：

• host指向address_space对应文件的inode。
• address_space中的page cache之前一直是用radix tree的数据结构组织的，tree_lock是访问这个radix tree的spinlcok（现在已换成xarray）。
• i_mmap是管理address_space所属文件的多个VMAs映射的，用priority search tree的数据结构组织，i_mmap_lock是访问这个priority search tree的spinlcok。
• nrpages是address_space中含有的page frames的总数。
• a_ops是关于page cache如何与磁盘（backing store）交互的一系列operations。

二、radix tree基本架构

我们现在介绍完了大体框架，现在来聊一下第一个主角radix tree。

radix tree采用的是key-value的方式插入和查找的，即利用一个长整型的数据快速找到其对应的对象指针。存储和查找效率比较高，如内核中的内存管理、IDR等机制都在使用。下面咱们来看一下主要的数据结构。

• shift成员用于指向当前节点slots的单位;

• offset表示该节点在父节点的slot中偏移值;

• count 表示当前节点有多少个slot已经被使用;

• exceptional表示当前节点有多少个exceptional节点;

• parent 指向父节点; 参数 root 指向根节点;

• slots是个指针数组, 该数组既可以存储下一级的节点, 也可以用于存储即将插入的对象指针;

• tags 用于标识当前节点;

这里主要挑选一些重要的数据进行说明。

Radix tree是一个多叉搜索树，存在插入、删除、查找等操作，这系列的操作的时间复杂度是O(k)，树的叶子结点是实际的数据条目，每个节点都有固定的指针数目指向子节点，这些指针也成为了槽位slot，Linux内核使用radix树快速定位文件缓存页，下图是一个普通的radix树的样例，树的分叉是4，树高为4，树的每个叶子节点可以快速定位8位文件内偏移，也就是可以定位4x4x4x4=256页，图中虚线为搜索路径。

图1 四叉radix树

在Linux的radix树每个节点有64个slot，与数据类型long对应，也就是key，下面是一个3级节点的radix树，每个数据条目一般可用3个6位的键值进行索引，一级使用6位，键值从左到右分别代表第1--3层的节点位置，没有子节点的以及root节点在图中不显示。

图2 3级节点radix树

Radix树每个节点有多少个slot主要取决于RADIX_TREE_MAP_SHIFT ，参考上面的宏定义，取值一般为6，标识每个节点有2^6=64个节点，RADIX_TREE_MAP_SIZE，表示1个叶子结点可映射的页数，如：1<<6=64，表示1个slot可映射64页。当树高为1时，64个slot对应64个页，当树高为2时，对应64*64个页。

Tags是一个二维数组，RADIX_TREE_MAX_TAGS为3代表的是3种tag类型，RADIX_TREE_TAG_LONGS定义slot数占用的long类型长度个数。加入这个值为64，也就是3*64的数组，这样每一行代表一种tag的集合，假如tag[0]代表PAGE_CACHE_DIRTY，假如我们查到当前节点的tags[0]值为1，那么它的子树节点就存在PAGE_CACHE_DIRTY节点，在我们查找PG_dirty的页面时，就不用遍历整个树了，可以提高查找效率。Radix树提供了一些关于tag的操作函数。这个大家可以去内核的/lib/radix-tree.c官网上去查看源码。这里就不细讲了。

经过上面对radix树的结构讲解，看代码就比较容易了。下面说说radix树的基本操作插入、查找和删除。

插入函数：

EXPORT_SYMBOL(radix_tree_insert);

①首先根据插入的条目的index值，创建对应的树节点;

②之后将条目插入到节点的槽位slot中。

①计算当前树的最大shift的为多少, 即目前可以计量的单位为多大(侧面反应了树的深度), maxindex变量保存当前树能存储index值范围;

②如果当前条目的index值已经超过了当前树所能计量的范围, 则需要调用该函数拓展树的深度, 使其可以顺利插入条目;

③在shift>0的情况, 如果子节点为空则继续创建节点(新创建的节点会记录该节点shift值和在其父节点的offset值), 并将其挂slot下(*slot = node_to_entry(child););

④根据index获取node节点slots对应位置的值给child, 并返回了该位置的offset;

⑤形参记录下要插入的节点和slot地址;

这个函数主要是将条目指针挂载到对应slot的上, 而且对当前节点中slot使用情况进行了计数，比较简单。

查找函数：

①首先是计算了当前树最大index范围, 如果查找的index值超过该范围, 则说明该index对应条目不在该树中;

②节点指针的最后两位是代表指针指向的节点类型，判断是否是内部节点，也就是是否有下一级指向的节点，根据index从父节点开始获取存储了条目的叶子节点node(通过while循环), 因为条目都存储在叶子节点的slots中，当最后找到了对应条目后, 经过判断发现已经不是树的节点则退出循环，radix_tree_descend对index进行了一个移位运算，进行shift值的移位运算。

举个例子，查找index值是1550的item, 当shift为6时, 则计算出的offset为24, 获取该父节点slots偏移为24的值, 发现还是一个节点, 再次计算偏移, 1550%64后得到值为14, 获取该父节点slot指向的子节点偏移为14的值, 发现该值不是一个节点, 则退出。在这其中便看到了一些关于RCU的操作。

删除函数：

EXPORT_SYMBOL(radix_tree_delete_item);

①通过 index调用查找函数查找到对应的条目, 返回值即是;

②如果entry存在则继续向下执行删除函数;

③根据节点地址和对应的slot地址删除该条目;

①根据slot地址获取在slots中的偏移值;

②更换slot, 该函数的第二个参数表示条目, 赋值为NULL, 表示清空了该slot下记录的条目; 并且对slot计数进行减一操作;

③删除node, 如果节点slots已经没有挂载条目则需要进行删除操作;

①如果该节点的slots上还有条目则, 判断该节点是否为root节点, 不是则立即返回, 否则将基数缩小到最小高度;

②根据该节点的信息, 对其父节点slots上对应的位置进行清零并进行计数减一操作;

③释放该节点内存，接下来对删除节点的父节点进行操作(因为它父节点slots如果没有挂有其他节点也需要删除)。radix_tree_shrink功能是缩减树的高度, 去除一些没有使用的节点。

在数据库中也有一种Adaptive Radix Tree（自适应基数/前缀树，ART），这里每个节点可以存储任意长度的键切片，并不像Linux中固定64，有兴趣的同学可以研究一下。

三、RCU机制

Radix树中还有一个重要的特性是RCU（Read-Copy Update）。因为页高速缓存在各进程间不断被访问，需要考虑并发的情况，单独使用锁的机制不能满足对读取速度的需求，便采用RCU机制。RCU的基本思想是先创建一个旧数据的空间，然后将数据更新到这个空间，最后再用新的数据替换掉旧的数据。以一个链表为例：

此时一个指针p指向3这个节点，使用RCU来更新这个节点数据。首先分配一段内存空间来存储用指针q来指向

然后将p指向的节点的数据以及与下一个节点4的关系都copy到q指向的内存地址中。

之后我们更新这个节点数据将3改成5。

修改完成后就要将更新发布，在发布之后读到的数据是更新后的，在发布前读到的是更新之前的数据。

等到所有引用旧数据的read动作结束后便释放这部分内存区域。

重要的是，RCU中的read不用像rwlock中的read那样，在write操作期间必须spin等待了。rcu_read_lock(),rcu_read_unlock()作用是禁止和启用抢占.因为在读者临界区,不允许发生上下文切换. rcu_dereference()本身都是原子操作.因为只是为了cache一致性,插上了内存屏障.可以让其它的读者/写者可以看到保护指针的最新值，radix树接口中要时刻注意RCU的安全保护，这个令radix树的使用上比较不便，这里只是大致叙述一下，就不详细展开了，起一个辅助理解的作用。

四、XRRAY的选择

内核中使用的树的类型比较多，如上面叙述的radix树，VMA使用的rbtree，以及今年提出的maple tree。XRRAY的出现是由Matthew Wilcox领导，他认为内核的基数树是一个很好的数据结构，但是它的用户数量远远少于人们的预期。相反，各种内核子系统已经实现了自己的数据结构来解决相同的问题。他试图通过转换其中一些子系统来解决此问题，于是便有了内核4.20之后版本中出现的XRRAY，在一次演讲中他对比了其他的一些内核中使用的树，比如说rbtree，也许会疑惑为什么单独选择在radix树的基础上改造，而不是其他的树结构。演讲中提到了一部分。

rbtree有着几个相对应的缺点。首先他并不是RCU安全的。现在的VMA搜索问题，在虚拟内存区，任务的地址空间是一组不重叠的虚拟内存区域，当前存储在增强的rbtree中，但是必须要mmap_sem锁定才能walk tree。其次使用红黑树会涉及大量的代码编写问题，因为必须编写属于自己的搜索接口等。谈论到内核中使用的另外一种树Btree，它对密集索引的效率不如radix树高，实际上他的效率也大约只有基数树的一半，因此Matthew Wilcox选择了radix树做基础。

正如上面讲述的radix树的框架，他的搜索效率还有RCU安全的特性对于搜索页面缓存来说也是至关重要的，不过radix树有几个需要解决的关键点。保持现有的基数树数据结构不变，因为它几乎没有问题。但是，描述其操作的结构已从树更改为数组，所以我们需要做接口适配。它的行为很像一个自动调整大小的数组。基数树要求用户自己进行锁定；XArray默认情况下会处理自身的锁定，从而简化了使用它的任务。删除“预加载”机制，该机制使得用户在获取锁之前预分配内存；它增加了复杂性，几乎没有任何实际价值。

XARRAY有以下几个特点：保持基数树的数据结构不变，将结构更改为数组，默认情况下提供锁定，删除内存预加载，使内存分配标志明确，向用户隐藏实施细节并且提供两个级别的API-普通和高级，方便人们使用。目前page cache已经转换完成，IDR也转换了大部分。简单的API是在高级API的基础上实现的，只管拿来使用，不必担心锁的问题。下面是一部分接口与radix树的对比。

在include/linux/radix-tree.h中您可以看到它已被Xarray取代。

在include/linux/xarray.h您可以检查相应的结构声明。

这里可以看出和radix树结构的相似点和区别。例如radix树使用的node节点、tags，而xarray使用的是entry、marks，只不过换了一个名字而已，结构属性都差不多。

下面介绍一下一些基本的函数：

1. 初始化一个XArray数组，xa_init(&array);

2. 在XArray里存放一个值：

void *xa_store(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp);

这个函数会把参数给出的entry，放到请求的index这个地方。如果xarray需要分配内存，会使用给定的gfp来分配。如果成功，返回值是之前存放在index的值。删除一个entry可以通过在这里存放NULL来实现，或者调用void *xa_erase(struct xarray *xa, unsigned long index);

xa_store的变体：xa_insert用于存放但不覆盖现有的entry。另一个变体：xa_cmpxchng，只有当存的值和old参数匹配上时，才会将entry存在index处。

void *xa_cmpxchg(struct xarray *xa, unsigned long index, void *old,void *entry, gfp_t gfp);

xa_insert和xa_cmpxchng都会返回存入的值。

3、用xa_load()从XArray里取出一个值

void *xa_load(struct xarray *xa, unsigned long index);

下面以一个查找函数为例：

①主要进行一个结构格式的转换，由xarray 转换成xa_state ，存储更多的数据，内部含有index数据。

②根据转换成的xa_state结构中的信息进行搜索，这里会为防止失败有一个retry的动作。

①获得开始节点；

②判断是否是一个节点，如果是便先转换一下数据格式xa_node这种数据格式由之前的宏定义可以看出与radix树的联系，之后由xas_descend进行移位操作，这个函数与之前的radix_tree_descend非常相似。

xas_descend函数同样是对index进行了移位的操作。

温故而知新，大致就是这个意思吧。由此可见接口确实比radix简洁很多。每个不为NULL的指针都可以标记多达3位的额外信息，可以通过xas_get_mark（），xa_set_mark（）和xa_clear_mark（）进行访问。您还可以通过调用xas_find（），xas_next（）或xas_for_each（）来遍历数组中的指针。

五、maple tree

Red-Black树和Radix树在内核的许多地方都用于存储范围数据。当用于范围时，这两种树都有缺点。红黑树需要编写您自己的插入和搜索代码。在设计时还假定内存访问廉价，这不再适用。当范围对齐到2的幂时，基数树的性能令人满意，但是在最坏情况下却表现不佳。

maple tree是一种具有简单API的快速、高效缓存的树。它有效地支持连续范围，而对不连续范围仅造成较小的损失。并且这种结构后续也会使用XARRAY的API接口，这里只是稍微提一下，就不展开谈论了。下面是maple tree的结构图：

六、结语

目前为止，XARRAY还在不断完善中，从之前介绍radix树，确实可以看出API做出了改善，感兴趣的同学可以查看内核中的xarray源码研究。

参考文献

[1]兰新宇.Linux中的Page Cache[EB/OL].

http://zhuanlan.zhihu.com/p/68071761

[2] Sourcelink.详解Linux内核Radix树算法的实现[EB/OL].

http://sourcelink.top/2019/09/26/linux-kernel-radix-tree-analysis/

[3] 吴一昊.The Xarray Data Structure [EB/OL].

https://kernel.taobao.org/2018/05/The-XArray-data-structure/

[4] Matthew Wilcox.2018-Wilcox-Replacing-the-Radix-Tree.pdf[EB/OL].

http://lca-kernel.ozlabs.org/2018-Wilcox-Replacing-the-Radix-Tree.pdf

[5]内核源码

https://git.kernel.org/pub/scm/linux/kernel/git/stable/linux.git/tree/lib

https://git.kernel.org/pub/scm/linux/kernel/git/stable/linux.git/tree/include/