从 radix tree 到 xarray
内核工匠 2022-09-29

今天我们来讨论一下内核中从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/

声明: 本文转载自其它媒体或授权刊载,目的在于信息传递,并不代表本站赞同其观点和对其真实性负责,如有新闻稿件和图片作品的内容、版权以及其它问题的,请联系我们及时删除。(联系我们,邮箱:evan.li@aspencore.com )
0
评论
  • 相关技术文库
  • C语言
  • 编程
  • 软件开发
  • 程序
  • STM32如何移植uCGUI,看这里!

    [导读]第一部分:在UCGUI移植之前在移植之前,首先要了解在网上下的UCGUI 3.98源码的文件结构是。UCGUI 3.98源码中有三个文件夹:1)“too

    11-22
  • 嵌入式汇编语言学习经验

    [导读]最近参与了一个项目,需要用嵌入式汇编写测试程序。汇编程序写过,C程序也写过,但是将它们混合起来写还是第一次,完全没有概念。只能上网找资料,自己慢慢摸索。

    11-22
  • 数字示波器在高频信号采集中的应用

    1 高频信号的采集 当要对一个高频信号(比如高达100MHz的雷达波形)进行采集和处理的时候。通常会设计一个高速或者超高速硬件采集电路,包括放大部分、滤波部分;A/D和D/A转换部分等,这种电路的要求非常高,要求边采集边存储,电路速度高,而且要考虑各种辐射干扰等,同时,目前市场上成品价格很难承受。并且根据采样定理,一个最高频率为/的连续信号,完全可以用时间上相隔了=1/2f的一系列离散采样值来表示...

    11-22
  • 单片机C语言static属性和数码管显示程序

    简介:static从英文上翻译是静态的意思,在C语言中static所起的作用也正是静态。对于局部变量而言,其作用域是局部的如某一子函数体,程序在每次执行时调用该

    11-21
  • LEMO产品进入EPLAN Data Portal绘图平台部件数据库

      EPLANDataPortal是一个基于web网络的平台,可以让工程师即时访问众多部件制造商的电气原理图,从现在开始,LEMO的连接器也加入了EPLANDa

    11-21
  • DAC0832三种波形的C语言程序

    波形发生器作为一种常用的应用电子仪器设备,传统的波形发生器可以完全用硬件电路搭建,如应用555 振荡电路可以产生正弦波,三三角波,方波等波形,传统的波形发生器多

    11-17
  • 虚拟仪器发展趋势及其对军用测试技术的影响

    1 引言从1986年NI公司提出VI概念到现在,经过十几年的发展,不仅VI技术本身的内涵不断丰富,外延不断扩展,在军事和民用领域均得到了广泛的应用,而且对现代测控技术产生了深远的影响。例如,VI原来最核心的思想是利用计算机的强大资源使本来需要硬件实现的技术软件化,以便最大限度地降低系统成本,增强系统功能与灵活性。由IT产业特征决定了VI技术也必须走标准化、开放性这条技术路线,目前VI已发展成具有G...

    11-16
  • 漫画:什么是 “跳表” ?

    —————  第二天  ————— 如何进行二分查找呢? 首先根据数组下标,定位到数组的中间元素: 由于要查找的元素20,大于中间元素12,再次定位到数组右半部分的中间元素: 这一次定位到的元素正好是20,查找成功。 如果数组的长度

    11-03
  • 总结4个Python数据读取的常见问题

    read_csv()是python数据分析包pandas里面使用频次较高的函数之一。它包括的参数差不多20个,可能一开始未必需要完整知道每个参数作用。不过,随着

    10-26
  • AWTK能为现代GUI编程带来何种改变?

    AWTK是一个伸缩性极强的嵌入式图形框架,它的诞生会给GUI编程研发工程师带来哪些改变?AWTK是一个伸缩性极强的嵌入式图形框架,可在Cortex-M3这样低端

    10-26
  • 可编程中断控制器8259其内部结构及引脚图

    [导读] 中断系统的使用极大的提高了CPU的利用率。中断是一种机制,这种机制实现的过程可分为请求-->响应-->服务-->返回。可编程中断控制器8259A是In

    10-24
下载排行榜
更多
广告