# Maple Tree Maple Tree是2022年，由Liam引入，为了解决vma处理时的锁问题。 ``` commit 54a611b605901c7d5d05b6b8f5d04a6ceb0962aa Author: Liam R. Howlett Date: Tue Sep 6 19:48:39 2022 +0000 Maple Tree: add new data structure Patch series "Introducing the Maple Tree" ``` 虽然Maple Tree脱胎于B树，但是细节上还是有很大的差异的。而且这代码我真的是费了老大劲才终于看懂一点。赶紧记录一下，以免忘记。 ## maple tree的目标 引入新的数据结构总是有目的的，在上面的这个commit中，Liam叙述了这个目标： * 减少访问时的cache miss * 降低mmap\_lock的竞争 减少cache miss的原因是： * maple tree的分支比红黑树多，所以高度低。这样要找到某个地址空间需要检索的节点数就少。 * 访问相邻vma的链表是嵌入在vma结构体内的，所以每次访问都要再次读取链表。但用了maple tree后，这个信息已经保存在访问过的节点内了。 ## maple\_node如何表达数据 Maple Tree中的一个节点用maple\_node表示，理解了其中时如何表达数据的，才能理解相关的操作是如何执行的。 ``` S: slot P: pivot (P0 < P1 < P2 ...) +------+......+------+......+------+ | S0 | P0 | S1 | P1 | S2 | +------+......+------+......+------+ [min, P0] [P0+1, P1] [P1+1, max] ``` 每个节点包含了多个slot/pivot，且slot数量比pivot数量多1,其中pivot按照递增的顺序排列。 当我们在一个坐标上依次标注pivot后，就展现出一段段由pivot分割的区域，而这些区域对应的值，则存储在相应的slot中。 最后一个maple\_node上的数据，就可以形成这么一个区间到数值的映射关系。 ``` [min, P0][P0+1, P1][P1+1, max] | | | v v v S0 S1 S2 ``` 如果我们以slot为中心，每一个slot\[n]代表的区域就是\[P(n-1) + 1, Pn]。当然其中由两个特例，头和尾的slot由整个节点的min/max限制。 便于理解，我们看一下父子关系下的情况。 ``` +------+......+------+......+------+ | S0 | P0 | S1 | P1 | S2 | +------+......+------+......+------+ ^ / parent / +------+......+------+......+------+ | Sa | Pa | Sb | Pb | Sc | +------+......+------+......+------+ [P0+1, Pa] [Pa+1, Pb] [Pb+1, P1] ``` 区域slot 1代表的区域，分割成了更小粒度的区域，由子节点表达。此时子节点的min/max就是slot 1的区域界限P0+1和P1了。 ## 函数详解 ### mas\_wr\_walk() 这个函数是用来在写入数据前查找对应节点的，这个的作用和红黑树和B树在插入前做的动作一样。所以遍历过程就不再赘述，而是讲一下遍历中保存的几个在最后修改值过程中要用到的值。 我们先来直观看一下遍历完，几个重要值之间的关系 ``` mas->node +------+......+------+......+------+......+------+......+------+ | S0 | P0 | S1 | P1 | S2 | P2 | S3 | P3 | S4 | +------+......+------+......+------+......+------+......+------+ [mas->min, mas->max] [r_min, r_max] [, end_piv] [index, last] ^ ^ | | offset offset_end ``` 依次解释一下： * 遍历过程中mas->node指向的是当前的节点，遍历完时就指向需要修改的叶子节点 * mas->min/max表达的是当前节点的界限 * mas->index/last形成了一个区域\[index, last]，这是本次修改涉及的区域 * offset/offset\_end是\[index, last]这个区域所在的起始和结束的下标 * \[r\_min, r\_max]是offset下标对应区域范围 * end\_piv是offset\_end下标对应区域右侧界限 根据上面的这些含义，我们可以得出的隐含含义是： * 区域\[index, last] 包含在 区域\[r\_min, end\_piv] 有了这些背景知识，我们就可以看看具体的修改过程，以及各种不同的case了。 PS: 补充一点， end\_piv是在mas\_wr\_end\_piv()中计算的，和mas\_wr\_walk()搭配使用才有效果。 ### mas\_wr\_node\_store() 遍历完找到需要修改的叶子节点，我们最终的目的是将\[index, last]写入到节点中。这个过程有好几种case，我们打开看一下。 首先按照offset和offset\_end的关系，分两个大类。也就是新的区域是在原来的一个区域里，还是跨了多个区域。 然后按照\[index, last]和\[r\_min, end\_piv]的关系，分四小类。决定是改写还是要插入新的。 因为有新增插入slot的情况，此时新增一个变量new\_end以表示完成插入后节点预期长度。 #### offset == offset\_end 这时，说明\[index, last]这个区域就在offset下标所指定的区域内，并不影响到其他区域。 并且, end\_piv实际上等于r\_max。 此时我们假设初始情况如下： ``` +------+......+------+......+------+ | S0 | P0 | S1 | P1 | S2 | +------+......+------+......+------+ ^ | offset ``` **index == r\_min && last == r\_max** 这种情况说明只要直接改写原有slot的值，并没有改变区域划分。比较直接。 ``` +------+......+------+......+------+ | S0 | P0 | entry| P1 | S2 | +------+......+------+......+------+ | | | | direct replace new_end = end ``` 此时节点长度并没有变化。 **index != r\_min && last != r\_max** 这种情况需要在原区域的前后都要切一块出来。 ``` +------+......+------+......+------+......+------+......+------+ | S0 | P0 | S1 | idx-1| entry| last | S1 | P1 | S2 | +------+......+------+......+------+......+------+......+------+ | | | | |<- copied ->|<--- modified --->|<--- copied --->| new_end = end + 2 ``` 所以这种情况下，需要增加两个slot来标记。 **index == r\_min && last != r\_max** ``` +------+......+------+......+------+......+------+ | S0 | P0 | entry| last | S1 | P1 | S2 | +------+......+------+......+------+......+------+ | | | | |<- copied ->|<-modified ->|<--- copied --->| new_end = end + 1 ``` **index != r\_min && last == r\_max** ``` +------+......+------+......+------+......+------+ | S0 | P0 | S1 | idx-1| entry| P1 | S2 | +------+......+------+......+------+......+------+ | | | | |<- copied ->|<--- modified --->|< cp >| new_end = end + 1 ``` #### offset < offset\_end 这时，说明\[index, last]在原节点上跨了多个区域。并且在小case的比较上，不是对比r\_max了，而是end\_piv。 此时我们假设初始情况如下： ``` +------+......+------+......+ +------+......+------+ | S0 | P0 | S1 | P1 | xxx | Se | Pe | Sx | +------+......+------+......+ +------+......+------+ ^ ^ | | offset offset_end ``` **index == r\_min && last == end\_piv** ``` +------+......+------+......+------+ | S0 | P0 | entry| Pe | Sx | +------+......+------+......+------+ | | | | |<- copied ->|<- modified >|< cp >| new_end = end - (offset_end - offset) ``` **index != r\_min && last != end\_piv** ``` +------+......+------+......+------+......+------+......+------+ | S0 | P0 | S1 | idx-1| entry| last | Se | Pe | Sx | +------+......+------+......+------+......+------+......+------+ | | | | |<- copied ->|<--- modified --->|<--- copied --->| new_end = end + 2 - (offset_end - offset) ``` **index == r\_min && last != end\_piv** ``` +------+......+------+......+------+......+------+ | S0 | P0 | entry| last | Se | Pe | Sx | +------+......+------+......+------+......+------+ | | | | |<- copied ->|<-modified ->|<--- copied --->| new_end = end + 1 - (offset_end - offset) ``` **index != r\_min && last == end\_piv** ``` +------+......+------+......+------+......+------+ | S0 | P0 | S1 | idx-1| entry| last | Sx | +------+......+------+......+------+......+------+ | | | | |<- copied ->|<--- modified --->|< cp >| new_end = end + 1 - (offset_end - offset) ``` ### mas\_wr\_modify() mas\_wr\_modify()是mas\_wr\_node\_store()的父函数，虽然在mas\_wr\_node\_store()中可以处理（几乎）所有的情况，但是在mas\_wr\_modify()里还是做了点优化。 原因是mas\_wr\_node\_store()的操作都是基于复制节点来实现的。而在某些情况下，并不需要复制节点，而只要在原节点上进行修改依然可以做到rcu safe。 在了解了各种修改的情况后，我们再来看看这些可以优化的case。 **PS: 强调一点，进入mas\_wr\_modify时，mas->node一定是叶子节点。所以不用拷贝gap。** #### offset == end: mas\_wr\_append() 变化的区间正好是当前节点最后一个区域的情况。而且隐含的条件是offset == offset\_end，因为offset\_end不可能大于end。 因为只需要添加到节点最后，所以单独拿出来做了一个优化。不过对rcu情况不适用。 #### new\_end == end: mas\_wr\_slot\_store() 这中情况说明节点内的数据长度并没有变化，所以我们不需要复制一个新的节点来做变更，只要在本地做修改就性了。 而且这里有个隐含条件是offset < offset\_end，因为在offset == offset\_end的case中，没有长度不变的情况。PS:唯一不便的情况已经被特殊处理了。 ## 常用API maple tree提供了一些API，然后其他子系统，比如mm，会在这个基础上再封装一层。 ### mas\_prev|next() 这一类一共有四个函数 * mas\_prev(mas, min) * mas\_next(mas, max) * mas\_prev\_range(mas, min) * mas\_next\_range(mas, max) 他们两两行为是对称的，一个是往前，一个是往后。 > 在叶子节点一层，在mas->index位置上往前|后一格。 区别在与 * mas\_prev|next(): 是要一直找到前|后面一格非空的slot。 * mas\_prev|next\_range(): 则只是往前|后一格，如果是空也没有关系。 除此之外，还要关注mas中index/last的变化。 * 遍历时是按照mas->index的值去找的，和mas->last没有关系。查找的最大范围是通过参数max来指定的。 * 不论找不找得到，mas->index/last都会设置到某个真实的range的范围上 * 如果不能再往前或者往后了，status会被设置成ma\_overflow或者ma\_underflow * 最后mas->index/last指定的范围一定和min/max指定的范围有交叉 ### mas\_find() 这个函数的行为和mas\_next()非常相似，除了在第一次执行的时候。 如果第一次执行时，mas->index对应有值则返回这个值。而mas\_next()则需要时返回下一个。 如果第一次执行时，mas->index对应值为NULL，返回结果和mas\_next()一样。 ## 测试代码 在内核代码里有专门的测试程序，在这里记录一下。一旦有改动，需要通过测试程序才能提交。 ``` # cd tools/testing/radix-tree/ # make maple # ./maple ``` 还有对应的内核模块测试代码。 ``` # ls lib/test_maple_tree.c ``` 不过需要打开选项CONFIG\_TEST\_MAPLE\_TREE。 编译完，安装内核模块也是测试。不过比用户态的程序少了点case。 ## 参考资料 * [内核文档](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/Documentation/core-api/maple_tree.rst) * [作者博客](https://blogs.oracle.com/linux/the-maple-tree) --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://richardweiyang-2.gitbook.io/kernel-exploring/00-index-3/06-maple_tree.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.