Maple Tree：结构和算法¶
标题：The Maple Tree: Structure and Algorithms
日期：2024/10/10
作者：Liam Howlett
链接：https://www.youtube.com/watch?v=RaXhP-QLUxI
注意：此为 AI 翻译生成 的中文转录稿，详细说明请参阅仓库中的 README 文件。
大家好，我是Liam Howlett，我在Oracle工作。欢迎参加关于Maple Tree数据结构的结构和算法的讨论。那么，我将稍微谈谈Maple Tree的总体思路，它与其他树的不同之处以及相似之处。我会回顾一下我们编写这个树的原因、使用它的好处和理由，然后我们将深入节点细节，展示一些小树的例子，接着探讨查找、存储或修改树结构的算法。
Maple Tree满足了大多数B树的要求。Maple Tree的特别之处在于它能够存储范围。一个条目可以通过多个索引找到。一个索引仍然可以引用一个条目，但以目前的实现方式效率较低。我们将在不久的将来研究解决这个问题。Maple Tree的另一个好处是对读取者的RCU保护。这意味着写入者不必阻塞读取者。还有一些术语上的差异。我们称存储条目的地方为“槽位”，而“枢轴点”通常被称为“键”。我们使用枢轴点与索引和最后作为特定条目的范围。我们称之为枢轴点，是因为正如我之前所说，它可以对应多个键。所以这里只是想指出这个区别。B树历史上是为了加速磁盘访问而存在的。Maple Tree的设计旨在优化缓存命中。基本上，我们不是去访问RAM，而是尝试在CPU缓存中完成所有操作。每个节点的大小被设计为四条缓存行。
这使得它比红黑树的解引用次数更少，主要是因为分支因子。红黑树必须转到下一个、上一个或当前节点，这基本上是一个分支因子为三，而Maple Tree节点的分支因子最多可达16。你可以在2019年LPC上关于Maple Tree的演讲“最甜美的数据结构”中了解更多，屏幕上有二维码。某些类型的树，特别是基数树，其中的空条目会占用大量空间。Maple Tree在空条目分组在一起时，将它们减少为一个条目。你可以在2022年LPC关于Maple Tree的演讲“将40升数据压缩至一升”中了解更多。我下一张幻灯片也会提到这一点。目前，我们正在优化写入速度，包括添加另一种称为“密集节点”的节点类型，用于一对一映射。那是用于单例存储。还有其他一些节点类型也在规划阶段。如果你看基数树，它会存储空值，并将连续的条目链接回前一个条目。例如，在这个例子中，我们在512到1023有一个分组，并且在512处有一个条目。那么513到1023将链接回那个512条目。然后其他条目被扩展到下面的另一个节点中。所以Maple Tree能够在单个节点中完成这个操作，而基数树需要多个节点。关于基数树和Maple Tree的更多信息，你可以在2022年LPC的演讲中再次看到。
Maple Tree被编写的原因是为了更好地存储虚拟内存区域。它在6.1内核中被引入，并首次用于该内核中的虚拟内存区域。它用一个双链表和VMA缓存替代了红黑树。在不更新锁的情况下，性能大致相同。在6.4到6.6内核版本之间，锁被更新以引入“每个VMA的锁”。每个后续版本都增加了由“每个VMA锁”处理的页面错误数量，同时提高了性能。Saren和Matthew完成了大部分这项工作。右边又是一个二维码，你可以扫描查看那个补丁集或那些补丁集。后来，用户空间错误FD操作也被更新为使用“每个VMA的锁”，其中Android垃圾回收锁争用是问题所在。正如你所看到的，这带来了压缩性能的提升以及不可中断睡眠时间的减少。这是在Android运行时上发生的一个非常用户可见的事情。所以看到这个被采用真的很好。
此时，Linux内核中Maple Tree还有许多其他用户。其中之一是FS中的LibFS从X-Array切换过来。当他们首次用X-Array实现LibFS变更时，性能下降了约15.5%。改用Maple Tree将性能下降减少到了3.7%。所以使用Maple Tree要快得多。但我们怀疑，当我们为单例实现密集节点时，我们甚至能够改进那个性能。
那么看看Maple Tree的节点，树中节点的内部结构。目前，树中的节点存储64位指针。每个节点最多可包含16个条目和15个枢轴点。根节点包含从0到无穷大的范围。在内核中，无穷大实际上是ULONG_MAX。所以这两个值，0和ULONG_MAX，不需要实际存储在树中，因为它们是隐含的。因此，树的每一级都从父节点继承隐含的最小值和最大值。看一个高度为2的小树示例，你可以看到根节点有隐含的0到无穷大范围。在这个例子中，枢轴点0的值是100。显示根节点的第一个叶子节点或第一个子节点，我们看到槽位0有一个隐含的最小值0，这是从父节点的最小值继承来的。值为100的枢轴点0意味着该节点的最大值为100。之后的节点，槽位1的节点，其最小值将是101。那么看同一个例子，但信息稍微多一点，我在下面的值添加了一些枢轴点。所以你可以看到范围取决于枢轴点，并且是包含性的。所以0到5在第一个槽位，6到10在第二个槽位，11到15在这个子节点的第三个槽位。如果我们要查找值8，首先我们会搜索根节点以找到8会落在哪里，它会落在第一个槽位，槽位0，因为它介于0到100之间。然后我们会进入子节点，找到第一个大于或等于8的枢轴点，那将是10，所以它会是6到10，然后我们会返回这里选中的槽位中的条目。
写入操作，Maple Tree的写入比读取慢。我们优先考虑查找，以牺牲修改为代价。我是对的，传统的B树在向下遍历时扩展。我见过的任何实现，当树几乎满或节点满了时，在向下遍历过程中，节点会被拆分，以便有空间存储你即将写入的信息。这对于范围存储实际上行不通，因为你可能实际上在压缩数据或减少存储在特定节点中的数据，所以你实际上直到到达子节点才知道是否需要拆分。当发生写入时，你可能直接替换某个东西，或者你可能实际上拆分那个范围，在开头留下一部分并放入一个新的部分，或者你可能覆盖一个范围的中间部分，这实际上会使特定节点的总条目数增加2。你可能还会覆盖多个条目，一直到覆盖从0到无穷大的整个树。所以你通常必须在到达叶子节点时，才决定将执行哪种类型的存储操作。直接替换是我要讨论的第一种写入类型。它是最快的，基本上就是覆盖条目。如果我们看一个示例树，类似于前面的例子，首先，当我们要存储6到10时，我们会通过遍历树来寻找6到10会落在哪个范围。我们再次向下遍历树到第一个叶子节点，因为6在0到100之间，然后我们找到6到10的范围。我们意识到这是一个直接替换。直接替换真正的好处是你实际上不需要使用新节点。所以我们只是把新条目放入槽位，就完成了。
那么下一种类型是节点替换。由于树的RCU特性，这常常排除了使用现有节点的可能性。所以我们需要创建一个新节点，分配它，构建它，然后插入树中。值得一看以熟悉这些操作。所以，如果我们要存储，比如说，8到9到前面的例子中，注意这里略有不同，隐含的100不再隐含了，因为它实际上被存储了，这个节点中有额外的空间来扩展数据。所以我们做的第一件事是再次向下遍历到我们将要存储数据的位置，我们意识到，是的，这将是一个节点存储。所以我们将继续看看我们要做什么。我们分配一个新节点，然后复制前两个条目。当我们复制前两个条目时，我们复制将被部分覆盖的条目，主要是因为存储操作不会完全替换它。所以我们将需要修改范围。这发生在我们存储新数据之后。我们覆盖旧的枢轴点以缩短范围。所以它不再是10，我们现在是7。这个7意味着这个范围是6到7，这意味着下一个从8开始。我们在这里写9以限制这个特定槽位的范围到9。我们放入新数据。然后我们必须存储我们在这里拆分的槽位的剩余部分，因为它是6到10，而我们只覆盖到之前的9。我们必须把之前在那里的相同数据放进去以覆盖到10。然后我们简单地将槽位0节点的剩余数据复制到新节点中。所以在这个例子中，你看到我们实际上只写入了一个值就使节点增长了2。发生这种情况是因为，我们通过写入范围的中间部分将其拆分。在我们得到新节点后，我们通过用新条目或新的槽位0节点替换之前的槽位0节点，将新节点安装到根节点中。
节点拆分。当特定节点空间不足时，我们必须拆分成两个节点。但这效率不高。如果我们拆分，就降低了数据的集中度。为了尽量避免这种情况，如果可能，我们会将数据推送到其中一个兄弟节点。所以基本上，如果可以的话，我们不拆分节点，而是与前一个节点重新平衡。所以如果可能，我们总是把数据推到左边。如果不行，我们就推到右边。如果两边都不行，那么我们就被迫拆分。当我们拆分时，它可能会向上传播多个层级。如果父节点满了，而我们无法向左或向右推，我们就必须拆分父节点。但我们总是尝试在拆分时向左或向右推，以减少数据碎片化以及使用的节点数量和树本身的变动。如果你到达根节点并且它满了，那么你就被迫拆分根节点，这将增加树的高度。
那么，如果我们这里再有一个例子，类似于前一个，我们现在有一个满的叶子节点。父节点在这里有一个额外的槽位，我们可以在工作区中使用。我们再次存储八到九。所以这将导致这个节点溢出。但我们再次直到向下遍历找到槽位并计算所需的槽位数时才知道。当我们计算所需的槽位数时，我们意识到空间不足。我们尝试向左推，但在这个例子中，没有左节点。所以我们尝试推向右边的节点，但它满了。所以我们被迫拆分。因此我们创建两个新节点，并精确地确定数据将放在哪里。你可以在这里通过颜色看到… 你可以在这里通过颜色看到紫色部分将进入第一个新节点，而浅色部分将进入第二个新节点。通过八、九的插入，我们知道这个节点将增长两个条目。所以我们将在特定位置拆分，因为那里大致均匀。实际上，我认为在两个节点之间是完全均匀的。所以我们做的第一件事是复制槽位0节点直到插入位置，包括我们将要插入的插入范围。然后我们再次操作，我们覆盖枢轴点以将插入位置限制在7，我们存储新值，并写入新的枢轴点值9。然后我们复制剩余的数据直到拆分点，包括那个没有被完全覆盖的部分，它是什么？六到十在九之后。所以现在只有十将指向这个值，而六到七也将指向同一个条目。
然后我们将槽位0节点从拆分点到结束的剩余部分复制到第二个新节点中。注意，我们必须将先前隐含的枢轴点安装到新节点中，即第二个新节点。
因此，缩小槽位0节点，以便我们在这里有工作空间，我们创建一个新的根节点，并从旧的根节点复制到新的根节点，但只复制到插入位置之前，但在这个例子中没有插入位置，所以我们什么也没复制。然后我们插入第一个新节点和第二个新节点。先前节点的拆分，这里的这个枢轴点将与根节点中的枢轴点相同，而100保持不变，因为现在这两个节点包含了旧树中第一个节点所包含的范围。
然后我们必须复制剩余的条目。注意，这里的最后一个枢轴点有点被推到末端，现在它是隐含的。但它会有内核期望的无穷大或ULONG_MAX值。所以它将成为一个隐含的条目或隐含的枢轴点。
那么我们就简单地替换新的根节点。在这个例子中，它是新的根节点。它也可能是一个更大树的父节点被替换。但在这里，它基本上是一棵全新的树。
除此之外，我们还有重新平衡。我们知道在B树中它们是自平衡的。Maple Tree在这里没有什么不同。任何需要重新平衡的操作都会发生，树将持续保持平衡。不足节点是指没有足够数据的节点。在B树中，大约需要一半的槽位被使用。在Maple Tree中，空值可能被计入，因为它们是范围，所以它们需要空间。不足节点将在兄弟节点之间重新平衡，父节点必须是足够的，因此在重新平衡的情况下，保证兄弟节点存在。这可能会折叠根节点的高度，如果根节点最终只有一个条目。所以如果你在根节点只有一个条目，那么你就可以让那个条目成为根节点，从而降低树的高度。重新平衡可能导致两个新节点，如果有足够的数据以至于我们需要两个节点来容纳这些数据，那么我们创建两个新节点并替换它们，这将由于树的RCU特性而要求替换父节点，然后那个父节点将被存储在树中。重新平衡中，一个节点基本上吸收了全部数据，即兄弟节点被完全吸收，这是一个有趣的情况，这是我接下来要看的。
那么继续使用相同的例子，我们有一个槽位0节点和一个槽位1节点，它们都有最少8个条目，并且它们在一个根节点中。
我们向下遍历到将要存储六到二十的位置，我们看到它跨越了多个槽位。粉色框高亮了将被新存储操作覆盖的槽位，然后我们计算新节点的大小，并意识到它不足。
重新平衡总是从右边开始。嗯，它尝试从右边开始。如果没有右节点，它将从左边的重新平衡中获取数据，但理想情况下，我们不断地将数据推到左边以保持数据密度高。这样我们就不会在CPU上引起缓存颠簸。所以我们希望在合理范围内拥有最密集的树。有时，如果你在写入东西并不断覆盖，会导致这种抖动扩展和收缩，我们试图避免这种情况。所以在这里，我们用一个条目覆盖了三个条目，这将导致槽位0节点变得不足。因此，在计算之后——也许我应该说在计算出添加全部条目数之后——我们意识到这可以容纳在一个节点内。这意味着我们将分配一个单独的叶子节点。我们从槽位0节点复制到插入位置。我们可能需要复制下一个槽位的一部分，下一个范围，包括槽位和枢轴点。但因为这个操作实际上要覆盖整个槽位，我们不需要那样做。然后我们插入带新枢轴点的新条目，再次，如果它没有完全覆盖最后一个枢轴点，我们将不得不复制那个最后部分的一部分，并且我们将不得不复制那个槽位和那个枢轴点，这仅仅因为安装了先前的枢轴点就会改变范围。然后我们复制槽位0的剩余部分，接着我们也把槽位1的数据复制到新的叶子节点中。
现在，我们所有的数据都已考虑在内。如果你再次注意到，这里槽位1节点中的枢轴点，最后一个枢轴点有点被推到节点边缘，这意味着它将是一个隐含的枢轴点，而这里的隐含枢轴点本来就已经在根节点的槽位或枢轴点1中了，所以它将是相同的枢轴点，因为再次，这个节点将覆盖与之前两个节点相同的范围。因此我们检查父节点，我们再次缩小它以便实际上有一些工作空间，我们分配的新根节点，我们将从旧的根节点复制到新的根节点，直到插入位置，再次，这处理的是槽位0和1，所以我们实际上不会在那里复制任何东西，但我们安装带新枢轴点的新叶子节点，这个新枢轴点再次将与旧根节点中的枢轴点1相同，然后我们将剩余数据复制到新根节点中，并再次安装或替换树中的父节点——这个特定情况是根节点，所以它又是一棵全新的树，但不必如此，它可能是一个本身有父节点的节点，如果它不是根节点，它实际上可能会变得不足——根节点没有最小条目数限制，除了一个条目，但在那种情况下它几乎没用——习惯作为根节点… 或者是的，所以在这种情况下如果这实际上是一个父节点会发生什么，我们将再次与它的兄弟节点重新平衡，可能完全吸收它也可能不吸收，并在树中安装一个新的父节点或祖父节点。
这把我们带到了树中可能更复杂的一个部分：跨越存储。跨越存储是指一次写入操作跨越了多个节点。现在我们已经看到写入操作跨越了多个槽位，但如果它跨越了非叶子节点中的多个槽位，那么它就被视为跨越存储。这非常难做，因为树的RCU特性，它要求或者可能需要父节点的重新平衡。我尝试重用任何可以重用的树的部分；它可能导致一棵全新的树；它可能减少到一个条目；如果你真的愿意，你可以存储从0到ULONG_MAX，并创建一棵只有一个指针的树；但这是迄今为止——如果不是最复杂的操作，也是最复杂的操作之一——我认为为什么会这样会变得很明显。我首先要做的是尝试弄清楚如何展示这个——分支因子为16的情况下，要展示任何有规模数据的树是非常困难的——这就是我做的，我想出的是包含一个最小值8，因为这是最小值，树在不引起折叠或节点相互吸收的重新平衡的情况下… 所以这是一棵高度为3的树，每个子节点大约是父节点大小的25%，只是为了它们能放在一页或一张幻灯片上。那么我在这里要做的是，我将存储125到260。所以我要覆盖相当多的条目。我展示这个，我在这里右下角创建了这个缩放图。在蓝框里，我把它放大了，你看到那里有像往常一样的隐含枢轴点0到无穷大，然后是范围50、100、150，写入125将写入第二个槽位2，实际上在我深入之前，你可以看到这里的第一个子节点有隐含的0到50，而根节点的最后一个子节点有隐含的351到无穷大。
我们遍历到125，我们在这里通过选中的枢轴点和选中的槽位看到。检测到跨越存储，因为存储的范围超出了这个槽位的范围。所以一旦看到这种情况，如果不是根节点，它可能发生在更下层，但当它发生时，我们启动两个遍历器，我们遍历到125和260。再次说明，这仍然是根节点的放大视图，所以我们向下遍历，你在这里可以看到我创建了一个左放大在蓝框，一个右放大在红框，在缩放图中你看到我们向下遍历到了槽位2和槽位5，所以我们向下遍历到了那些子节点，我在这里展示了细节，隐含值和限制值，然后我们再次向下遍历到子节点，在子节点中我们看到实际的条目，枢轴点124和260在这里被高亮了，并且有不同的区域——只要你能找到你要做的事情，这并不重要。这个例子实际上相当简单，因为我们最终会有足够的数据容纳在一个节点内；有时情况比这糟糕得多，如果这两个节点之间的数据对于一个节点来说不足，那么我们需要合并这些节点左边或右边的其他节点，如果这些节点是父节点最左和最右的节点，这可能变得极其复杂，那么我们就必须去到节点的“堂兄弟”那里，向上到父节点再向下获取数据，如果发生这种情况，父节点将不得不合并，它就会自己折叠起来。即使在这个例子中，我们高亮——我在这里高亮在插入位置之后左边将被覆盖的内容，以及在插入位置之前右边将被覆盖的内容。如果我们看这里的树，再次用粉色高亮的将是会消失的东西。所以这里的蓝色块是左边的子节点，它将有部分写入，它右边父节点中的所有东西都需要被销毁，即这些特定的槽位以及它们下面的任何东西都需要被释放，包括这里是树的另一层，也必须被修改。你可以在我们正在查看的缩放图中看到黄色部分。所以在这个场景中，整个子树都会消失。
那么我们怎么做呢？嗯，首先我们意识到这能够容纳在一个节点内，所以我们创建一个叶子节点，我们再次复制到插入位置，有点类似于我们之前做的操作，然后我们插入带新枢轴点的新数据，然后我们从右边节点复制… 从右边节点复制我们覆盖之后的部分。注意这些是特别选择的，我们不会拆分特定的范围，但也可能发生你拆分了一个特定范围，那样的话部分会被复制，并且枢轴点会被修改以改变那些特定槽位存储的范围。然后我们必须向上走回去构建一个新的子树。所以我再次遍历到左边和右边的父节点，如果你看缩放图，你可以看到我向上走了一层树，我创建了一个新的父节点，我复制了左边父节点直到插入位置的所有内容，然后插入带新枢轴点的新叶子节点，然后我们将从右边父节点复制我们要重用的剩余部分到新的父节点中。然后我们再向上一层，在根节点中我们必须创建一个新的根节点，粉色框高亮的，选中的槽位之间的任何东西都必须被销毁，正如我之前在图里用黄色框提到的，但选中的槽位中的那些有点不同，因为那些子树的部分正在新树中被重用，所以那里的操作有点不同。所以我们再次只复制不会被覆盖的部分，我们存储带新枢轴点的新父节点，它再次将与这里的枢轴点相同，因为这个新父节点现在拥有这个粉色框中所有范围的范围，然后我们将旧根节点的剩余部分复制到新根节点中。所以这就是最终树的样子。你注意到根节点中这个新条目指向一个相对容易的跨越存储会去的位置。
这大概就是我为这次演讲准备的所有操作了。所有这些操作中还有一些其他涉及的事情，但这是树运行所需的大部分操作的基本概述。
有问题吗？
Liam，让我问你一个关于这个的问题。你会如何… 其他核心子系统使用这个的最佳案例是什么？哪些子系统会是使用Maple Tree的好候选？是的。所以大多数使用红黑树的东西… 是的。所以本质上… 内核中使用树的大多数东西要么使用基数树，要么使用红黑树，但他们实际上并不直接使用红黑树。他们使用区间树。他们使用区间树的原因是它更容易使用。他们不必为自己的数据编写搜索功能，因为区间树已经提供了。区间树是专门为重叠范围设计的，而大多数区间树的用户实际上并没有重叠范围。所以任何使用区间树但实际上没有重叠范围的用户应该切换到Maple Tree。另一组用户是进程的PID ID。
让我回到这里。这里。
所以PID ID是需要顺序编号的分配器。是的。是的。是的。那些用户… 所以这里，使用… 比如PID ID目前使用基数树。当你有一个，比如说，哦，我不知道，PID为1的进程，它永远不会消失，然后你让你的系统连续运行几周，基数树效率极低。PIDs通常有，比如1，然后可能是5、6，然后13、14、30左右，然后变得非常稀疏，你在频谱的末端有像3000、30000之类的东西，因为你的系统一直在分配PIDs，你不断获得新的，而很多短生命周期的进程已经死亡。
在基数树中，最终你会得到很多包含信息很少的节点。在一个例子中，我拿我的运行系统。我的笔记本电脑。它运行了大约两周左右，有521个正在运行的进程。在基数树中，基于数字、PID ID或PIDs，存储这521个值需要147K。那是巨大的空间浪费，对吧？当我查看时，有大约115个基数树节点，每个节点只有一个值。相比之下，Maple Tree将使用16K来存储这些值。当你试图将东西保留在缓存中时，你不想有如此低的数据到内存使用率。所以任何使用顺序编号，需要做这类事情的系统。这正是LibFS所做的。这也是他们切换到Maple Tree的原因，因为发生的是，不是拥有带大量空值的大节点，Maple Tree会将其减少为一个空值。在这里，你可以看到，顶部是枢轴点，下面是槽位。所以我们在低位槽位有几个被使用的，然后这里有一个大间隙。但在基数树中，这个大间隙实际上会是大量的指针，而在Maple Tree中，它是一个指针。
所以本质上，嗯，你说16K，你给的例子，16K对114，你说140？147K对16K。那是巨大的。巨大。是的，是253个节点对64个节点。所以节省量巨大。但我的意思是，人们会说，嗯，你知道，147K，谁在乎？但当你开始把它塞进CPU缓存时，嗯，你就在乎了，对吧？不仅如此，你还需要少得多的解引用来获取你需要的东西。所以我们不仅有更大的分支因子，而且空条目的压缩确实节省了大量搜索实际值的时间。
是的。如果有人正在看他们的子系统，我是说，有人正在看他们的子系统或有人正在跨子系统查看，看看哪个子系统可以从Maple Tree中受益？有没有更简单的方法来判断？我是说，你有什么工具之类的东西可以全局运行吗？还是你必须了解这些子系统？我认为你确实需要对这些子系统有一些了解。就像我说的，最大的指标是，嗯，首先，IDA、IDR是这个用于PID的东西。它可以显著受益于切换到Maple Tree。一旦我们有了密集节点，它会变得更好得多。
密集节点的想法是，不是拥有枢轴点，我们只有一个数组。这个数组很大，比如31个元素。隐含的最小值来自父节点。最大值就是最小值加31。然后你只需根据你查找的值确切地知道你要在密集节点中去哪里。但这允许我们做的是，在拥有顺序编号时，将数据密度进一步提高到我们已有的水平之上。所以一旦这个就位，将在某些领域带来巨大的改进。这就是我目前在内核内存管理社区之外有时间时正在做的事情。
所以任何使用那种需求的东西，如果有子系统使用基数树，那就是候选。如果它使用区间树，我的意思是，我无法强调有多少区间树的用户实际上没有重叠范围，因此实际上不适合区间树的用例。只是碰巧在当时它是最容易使用的东西。还有那些切换到X-Array的人可能想重新审视一下，看看Maple Tree将如何使他们受益。所以这些是方式，如果有子系统使用这类东西，那么他们应该重新审视他们的选择，看看切换到Maple Tree是否有益。
另一件事是，如果你正在设计新东西，那么你可能想看看这个以及它将如何使你的用例受益。肯定有它不适用的用例。分配与嵌入。红黑树将信息嵌入到你自己的结构体中，而Maple Tree有自己的节点。所以基于存储操作需要发生分配，你可能无法避免或在操作前知道会发生什么。我在内存管理中遇到过这个，因为我们需要避免在特定锁的区域内分配。所以有一个预分配调用来说我要存储这个。请现在就分配。然后我们获取锁，再存储它，这样我们就为Maple Tree预留了必要的内存。我们正在努力实现这类东西。我们正在努力将其优化到分配器本身，KMEM缓存中。所以我们将在未来看看效果如何。但肯定存在由于分配要求而不适合的领域。
我明白了。所以我快速看了一下工具测试，基数树测试。所以你确实有像IDR测试这样的东西。你提到的所有这些是X-Array之类的。它们是组合在一起的吗，所有种类的树？虽然我看到也有maple。所以看起来你把所有测试都存在那里了？还是怎么运作的？
是的，所以我们开始了，你在那里看到的是用户空间测试。我们意识到在内核中运行测试甚至构建测试都需要很多时间。所以我们所做的是模拟能够在用户空间运行它，这允许我们直接在GDB上运行东西。在初始阶段，我所做的是放入跟踪点来说明Maple Tree发生了什么，发生了什么存储和删除之类的操作，我可以记录这些，然后在用户空间重放以更容易调试。然后我把那些问题作为测试用例留下来。所以任何时候发生任何问题，我就创建一个新的测试用例并放进去，这样它就再也不会发生了。所以你在那里看到的是用户空间测试。
在lib中还有一个文件，是lib中的一个测试Maple Tree的文件，它构建成一个可以加载的模块。它也在用户空间测试中运行。用户空间测试做了一些我在K单元测试以及模块中无法完成的事情。例如，RCU线程测试之类的东西在里面。所以那里积累了大量的测试，它相当成功，以至于我们正在为BMA测试复制它。
是的，它运行得非常好，因为它允许我们独立于内核进行测试。那个测试实际上允许我重写了算法的一部分，一旦它在测试中工作，它就在内核中工作了，这很棒。是的，那就是我正在看的。我确实看到了。我认为对于想理解这个的人来说，这将是一个开始的好领域。是的，我还发现了一个实时测试。似乎有一个实时的Maple Tree和test_maple_tree.c。所以看起来如你所说，你说你在添加回归测试。我看到在那些.c文件里已经有回归1、2、3了。所以那可能就是你指的radix tree目录下的东西。
是的。所以那实际上是一个很好的测试方式，对吧？有时当你有，特别是当你为关键的东西使用Maple Tree时，比如pids或liveFS之类的东西，调试和测试就变得更难了。所以特别是这个确实允许测试。是的，我是说，如果我做了一个改动并破坏了，我将无法启动到可以加载模块来运行测试的程度。所以这是一种，一种很好的隔离方式，隔离在你知道之前执行了什么… 这样其他东西不会碍事。
对的。那么我们在Q&A里有一个问题。这是一个很长的问题。有办法你能看到问题吗？还是你希望我读给你听？我可以看它。好的。我在LPC24上已经问过了。有兴趣解释一下。据我所知，内核树中有用户使用mtree_alloc_range，其条目并不真正重要。内核BPF竞技场。重要的是跟踪已分配的范围。我有一个类似的用例，基本上使用Maple Tree来分配不重叠的整数范围，我存储在范围中的条目并不重要。我只需要知道该范围是空闲还是已分配，并通过mtapi按需分配和释放它。假设这是Maple Tree的一个有效用例，在那里可以进行什么观察？尝试一下是否是一个简单的改变？显然，在专用分配器上，给定整数空间的范围可以被写入，但既然Maple Tree目前没有，这似乎不太有用。我不确定。我没跟上最后一点。
Lorenzo，你能取消静音吗？我们可以取消静音，然后你或许可以… 有人举手了。让我看看是谁。 继续问问题吧。用例… 我认为BPF的竞技场并不是真正有用的。你需要跟踪哪些范围在使用中，哪些不在。我认为如果条目不是真正有用，有什么可以优化Maple Tree的吗？我已经问过你了。我不知道你是否理解我在问什么。我的意思是，我理解这是一个特别的问题，但我想这是一个有效的用例吧。
是的，我不完全确定… 我记得你问过这个，我不记得了，我不知道…我想了解更多关于这个用例的信息，因为这看起来像是你需要类似… 我不明白你怎么会有一个范围却只需要知道它是否被使用。你需要引用特定范围的东西。必须有一些与范围相关的事情要做，你似乎错过了利用树来存储一些东西以便更快查找的机会，而只是用它来查找看看它是否曾经被使用过。这说得通吗？是的，说得通。我的意思是，你可以跟踪范围。例如，这基本上是一个需要一定数量IRQ的设备，比如0到20，你可以存储一个索引。嗯，例如，你知道那个范围分配给了一个特定的设备，但你不必添加一个条目。你只需要知道那个条目被分配了0到20，如果你想释放它，我想你可以通过传递一个索引给Maple Tree来释放它，不需要做其他事情。你不需要为了这个原因在树中存储一个指针。这样对吗？或者也许我不理解如何使用Maple Tree？
嗯，我只是觉得，我的意思是，这是一个有趣的想法，要做到那样，我们将不得不做的是，再次，我觉得这错过了一个机会，你有一个特定的IRQ，你可能应该在里面存储一些东西，以便你能知道它引用了什么，什么设备与该IRQ关联之类的。这说得通。我的意思是，我只是好奇看看如果信息不是必需的，是否有什么可以在那里优化的。我的意思是，这就是我在问的。我理解，我的意思是，这主要是关于Maple Tree中条目如何存储的问题，以及如果不需要它们是否有意义。我意思是，那里有什么可以优化的吗？真的只是出于好奇。
对的。所以，如果你想专门为此优化，我们要做的是创建一个新的叶子节点类型，这种叶子类型能够存储更多的范围，因为我们实际上不需要，这里的每个槽位是一个指针，那太大了。我们可以只用一位，然后我们可以大幅增加枢轴点的数量。对的。那么你就可以在每个叶子节点有更多的条目。如果你在每个叶子节点有更多的条目，那么你就可以提高树的密度。我认为实际上密集节点会是最好的计划，因为是的，我的意思是，我想你能做的是… 不，不，是的，一个新的叶子节点会是最好的方式。你能做的是，就像我说的，你可以让槽位不是一个指针，一个64位指针，而是用一个位表示开或关。然后我们每个叶子节点可以有更多。我认为那将是最好的方法。
但我不确定是否有足够的用户来支持这个用例，为那个目的创建一个新的叶子节点类型。明白了。我的意思是，但你澄清了。非常感谢。我现在明白你的意思了。所以我明白了。谢谢。是的，没问题。
看Q&A，里面还有另一个问题。是的，对于VMA，我们有for_each_vma宏定义。for_each_vma中的一些符号是GPL的，由于第三方内核模块不能使用for_each_vma。遍历VMA的Maple Tree有什么替代方案？
把你的模块GPL化？
是的，所以我并不真正支持树外模块。
肯定有一个查找，我的意思是，有一个next和previous，它们会去到下一个和上一个条目，你可以在那里做你的限制检查。有一个mas_find，它从一个给定的条目或给定的范围运行，所以你可以用mas_find来做你想做的事，我猜，但理想情况下你应该把模块GPL化，这样你就能使用所有内核功能。
我尝试添加了多种方式来做与其他数据结构类似的事情。我尝试使用previous和next，尝试模拟成链表，主要是因为MM过去用红黑树时有一个链表。VMAs存储在一个红黑树中，但红黑树被增强了一个双链表用于previous和next，以及一个VMA缓存来加速访问。当我们替换所有那些时，我想要一些能像链表一样使用previous和next的东西。所以真的有一些棘手的部分，比如如果你在第一个条目然后previous会发生什么，以及之后如果next会发生什么之类的。
所以有一些操作我尝试去做，我尝试让它对可能使用先前数据结构的用户来说合乎逻辑。MM中的一个函数是find_vma，它会从一个特定位置开始向上查找直到命中某个东西。这在树中也被实现了，如果你想想… 如果你想想我之前说的把空值压缩成一个条目，那么你会意识到find_vma如果落在一个空值上，只需去到下一个槽位，这实际上非常棒。还有问题吗？没有，目前Q&A或聊天里没有了。
如果你想分享任何其他你有的幻灯片，那也很好，或者你知道我们还有时间，如果你想展示… 我之前展示的节点并不完全是节点里包含的全部内容。节点里实际上还有更多东西。如果还有空间，最后一个槽位可以存储元数据，这是一种双重用途的东西。还有一个链接指回父节点，这样我们可以向上遍历，实际上父节点——因为这些节点实际上是256位对齐的——我们有7位用来存储元数据，父指针中的几位实际上告诉我们在父节点中的位置。这里的元数据会指示节点中最大的间隙… 实际上在叶子节点中，它指示节点的结尾，因为在我编写这个的时候，我注意到很多时候我们花在寻找节点的结尾上，而且很多时候节点不是完全满的。所以我可以在最后一个槽位存储节点结尾的元数据，我可以通过检查最后一个枢轴点来检查是否有元数据。如果最后一个枢轴点是空的，那么我知道有元数据告诉我们结尾；如果最后一个枢轴点是某个值并且它是父节点传来的隐含枢轴点，那么我知道结尾是前一个；否则我知道节点是满的。所以这里有种双重用途…
数据密度方面，树还可以跟踪间隙，这对VMA的东西特别有好处，因为我们搜索是为了找到可以放东西的位置；我们不只是说我想存储10到20，他们说我想存储大小为10的东西，给我找个位置。所以我们有这些可以存在于节点中的间隙。当我们这样做时，它并不完全奏效… 内部节点中总有空间放元数据，所以我们称之为分配树，因为它用于分配。当你使用分配树时，你必须初始化一棵树，声明它将是一棵分配树。所以内部节点是分配节点，它跟踪间隙以及范围，代价是分支因子从16减少到10，但你能找出最大的间隙在哪里。例如这里我们看到在槽位1的子节点中有一个间隙是最大的，我们在这里存储间隙大小。这个分配节点元数据中存储的另一件事是最大的间隙，这样我们就知道不需要向上传播到树的上层；如果我们覆盖了一个特定的间隙，我们知道最大的间隙被覆盖了，那么我们必须向上走，否则我们知道我们没问题。所以我们把这个用于自顶向下搜索或自底向上搜索，取决于架构，通常是自顶向下。我们得到一个提示说我们想要9000左右的东西，我们从9000开始向下工作。这里我们说我们想要500到7000之间的东西，我们正在搜索30。那么我们要做的是… 哦等等，这里的元数据指向最大的间隙在这里，所以它几乎总是会指向这里。它主要用于更新。所以首先，当我们自顶向下遍历时，我们会下到7000，这是这里被选中的。我们有一个20的间隙在这个槽位和这个枢轴点之间。我们正在搜索30，所以20不够，所以我们继续搜索下一个。5000有一个50的间隙，这足够了，所以我们进入这里的叶子节点，我们自顶向下搜索以找到足够大的间隙。这个不够大，我们继续找，找到我们可以存储的区域，然后把这个返回给调用者。调用者现在知道它将在哪里存储它的东西——也许它实际上不是存储30，而是存储28之类的——但它正在寻找一个大小为30的空洞，出于某种原因和对齐，所以他们通常搜索比他们实际需要稍大的东西，然后实际存储发生在另一个操作中。这只是树的另一个方面，用于任何使用分配的地方。所以如果你需要一个间隙，你可以用这棵树找到它。
节点布局… 密集节点的想法我想我已经讲过了，但想法是… 没有间隙跟踪，只有叶子节点，没有枢轴点。所以它只是带有一个隐含起点和终点的一对一映射。在一个密集节点中，可以有多个连续的空值，但基本上我所做的是通过只允许一定数量的连续空值来确保密度保持在特定的可用水平，然后我们将折叠回我们之前看到的范围节点，这种切换实际上会自动发生。所以如果你在存储，比如说pids，你像往常一样从1开始并向上增长，你将有一个密集节点，然后另一个，再另一个，然后随着东西被释放，你可以向下折叠成一个分配节点，也许旁边会有一个密集节点，或者它会重新平衡以从密集节点获取足够的数据，或者那里没有足够的条目，它会把它变成别的东西。所以这真的会变成对节点更动态的使用，以提高存储信息的密度。密集节点实际上只发生在叶子节点，所以它是一个叶子节点，而内部节点仍然有范围。
另一件事是节点的逻辑视图与代码中的结构不同。结构大多只是数组；它们不是混合的；没有槽位0、枢轴点0、槽位1；它只是一个数组。树还有另一个优化，树可能是一个指向0的单指针。所以如果你存储0到树中，0到0的范围，大小为1，那么我们实际上不创建节点；我们只是放一个指向那个条目的指针。这对于像这样的情况非常重要：当你试图跟踪几乎总是一个东西，但偶尔需要超过一个东西时，你可以直接使用这个，它会在需要时分配，或者大多数时候根本不需要分配。我今天在取消映射VMAs时使用了这个，通常只有一个VMA被移除，但在启动时通常——至少在我的x86_64或AMD64机器上——我通常看到一个，然后三个，偶尔看到七个。
树的另一部分我稍微提到过，节点是256位对齐的，这允许7位用于编码信息。父指针和子指针都可以编码不同的东西。在子指针中，我编码子类型以及下面是否有任何空值——这实际上目前没有使用，但这里的想法是未来当我们将其用于IDA IDR类型的分配时，我们有单例，有时你想知道在这个范围内是否有一个pid可以重用，然后你在向下遍历之前就会知道，这样我们就不必使用间隙跟踪来知道这个子树下面至少有一个条目可用。所以那是一个我们正在考虑做的进一步优化。
我提到过这个，树的迭代器… 有链表式的previous和next。我也有previous range和next range，因为有时即使它是空的，你也想去上一个或下一个范围。previous和next有点被理解为像链表操作，你去到下一个或上一个条目，而previous range和next range实际上可能返回一个空值，这些对于VMA空间中的某些操作很有用。我们检查是否可以合并VMAs，但这只在地址匹配结束地址和起始地址接触时才重要，所以如果上一个范围是空的，那么我们就不需要再往前走了。我们还有mas_for_each和mas_for_each_rev迭代器来遍历每个条目。我想这在问题中被提出来了。我想它是GPL的。所以是的，那是树的另一个方面。
未来的工作… 我们想添加对影子条目的支持；这将需要一个新的节点类型，并将取代间隙跟踪。这是为了达到与X-Array同等的功能，这样我们就可以用它来做影子条目和压缩、紧凑之类的事情。我也提到了下一个点… 树抖动… 早期我注意到，严格限制一半为最小条目数，一旦我们低于那个，会导致树中的这种波动，东西不断折叠进去。很多时候发生的是，我们在一个紧密循环中添加和移除一个条目。通常这是一个人工基准测试，但它可能在现实生活中发生，我见过，持续做这个代价极高。所以我们不得不放宽一半的限制，如果它在一个特定范围内——我想只有一两个条目时——比如你降到7，我们可以打包… 如果你接近限制，那么它会重新平衡，但它不像一个固定数字那么严格，这样你就有摆动空间用于添加或移除一两个条目。
还有重写树以避免RCU开销和重新检查SMP写内存屏障的想法。写路径使用与读路径相同的代码，但拥有两条路径可能是有益的。我最初并不真想这样做，因为我必须为树编写大量代码，所以我不想有两条路径需要调试。随着树变得更稳定，可能值得看看性能提升有多大。RCU本身的开销并不那么大，所以可能不值得做。
我有一个关于Maple Tree的邮件列表，我定期发送正在处理的事情列表以及处理它们的人。我有几个人接手了任务，我有一个正在进行的列表，列出可能未完成的事项，我猜你会这么说。其中之一是模糊测试器。我正在找… 早期有人写了一个模糊测试器，它真的很有帮助，但此刻我想要一个更好的，它对树了解更多或知道特定的事情，而不仅仅是发送随机数据来发现问题，我认为那将是有益的。
你在寻找一个更智能的模糊器，可能可以针对某些特定事物进行测试？是的，是的。我认为那对这个来说会是一个好主意。
那么问你一个问题。你提到它是RCU的。我们的大多数树似乎都使用RCU。Maple Tree的RCU使用与其他树有什么不同？抱歉，哪些树有RCU？RCU… 我是说IDR似乎使用RCU，红黑树似乎也使用RCU。Maple Tree比其他树更广泛地使用它吗？
嗯，所以红黑树有RCU支持，但它的工作方式是，在你完成后，你必须重新检查你所拥有的，看看你是否跑偏了，这相当好，但它依赖于使用红黑树的人在自己的代码中知道如何正确使用它，这对人们来说是一个巨大的障碍，每个人都在自己做，所以它又回到了整个事情上… 对于VMAs，当我们替换红黑树时，红黑树有RCU，但它也有链表，这导致了与RCU的问题。Maple Tree更像是一个交钥匙解决方案，我们试图让接口相当简单和有用，并坚持人们熟悉的概念，而不是试图让他们编写自己的搜索和RCU保护。现在有一点是，Maple Tree不保护它为RCU存储的内容。例如，当我们切换到“每个VMA的锁”时，VMAs必须以RCU安全的方式释放，才能以RCU方式使用。所以你确实必须用RCU保护你自己的数据，但树本身会返回之前在那里的东西或现在在那里的东西，所以它比尝试使用其他方式更不容易出错。
是的，所以我想区别在于易用性，我会这么说。所以你有点像，如你所说，不要求用户弄清楚如何做搜索，你做了很多，除了数据保护… 我想在这个演讲中看到不同树之间的比较会很棒，但你知道也许那是… 无论何时你做另一个演讲，或者你可以考虑比较这些树。是的，我几年前做过一个比较，我不知道那是不是你想要的那种，那里有一个表格列出了不同的东西… 哦，那会很棒。是的，是的。我只是不知道它是否足够满足你的需求。我得重新审视它。是的，而且我的意思是，它… 是的，我的意思是，有一个树的比较表是个很棒的主意。密度和分支因子绝对是其中最好的。我的意思是，就像我说的，红黑树的分支因子是3，而这个的分支因子是16或10，但基数树在那个方面更好，我相信。
听起来不错。谢谢你。谢谢你耐心回答所有问题。
是的，没问题。Candice，时间怎么样？还有来自… 我想我们还有一点时间。如果有任何问题… 是的，我们还有大约五分钟，所以如果有人有其他问题，请随意放到Q&A或聊天里。所以非常感谢这个演讲。是的，欢迎。谢谢邀请我。好的，那么我们可以结束了。谢谢Liam和Shua今天的时间，谢谢大家加入我们。提醒一下，这个录音将在今天晚些时候发布在Linux基金会的YouTube页面上，演讲幻灯片的副本将添加到Linux基金会网站。希望你能参加未来的导师辅导课。祝你有美好的一天。