Linux Radix Tree 详解
Linux Radix Tree 详解
关注微信公众号：Linux 内核拾遗
1 概述
众所周知，Linux 内核提供了许多不同的库和函数来实现不同的数据结构和算法，其中基数树（Radix Tree）作为一种常见的数据结构，由于其查找速度快、节省存储空间等特性，它在 Linux 内核中有着广泛的应用，例如在 v4.20 以前 Linux 内核使用 Radix Tree 来存储所有的页缓存（在后续的版本中采用 xarray 来取代了 Radix Tree，本文暂不深入），struct address_space 结构体中包含了一个 Radix Tree 用于跟踪所有的映射页，以及 Linux 内存管理单元使用 Radix Tree 来快速查找脏页或者回写页等等。本文将对基数树这一数据结构作基本介绍，然后探讨 Radix Tree 在 Linux 内核中的设计实现以及使用方法。
2 基数树
根据维基百科的定义，基数树（Radix Trie，也叫基数特里树或压缩前缀树）是一种数据结构，是一种更节省空间的 Trie（前缀树），其中作为唯一子节点的每个节点都与其父节点合并，边既可以表示为元素序列又可以表示为单个元素。 因此每个内部节点的子节点数最多为基数树的基数 r ，其中 r 为正整数以及 x 为 2 的幂（x≥1），这使得基数树更适用于对于较小的集合（尤其是字符串很长的情况下）和有很长相同前缀的字符串集合。
基数树的查找方式与常规树不同（常规的树查找一开始就对整个键进行比较，直到不相同为止），基数树查找节点时，对于节点上的键都按块进行逐块比较，其中该节点中块的长度是基数 r。
当 r 为 2 时，基数树是二元基数树（即该节点的键的长度为 1bit），增加了树的深度来降低稀疏性（即最大限度地合并键中没有分叉的节点）。
当 r≥4 且为 2 的整数次幂时，基数树是 r 元基数树，牺牲了稀疏性来降低基数树的深度。
基数树支持插入、删除和查找等操作。插入操作将新的元素插入到树结构中，同时尽可能最小化数据的存储空间；删除操作将元素从树结构中移除；查找操作包括但不限于精准查找、查找前继元素、查找后继元素以及查找拥有公共前缀的所有元素。所有的这些操作的时间复杂度均为，其中 k 是集合中全部元素的最大长度。
2.1 查找
查找操作用于确定一个元素是否存在于基数树中，基本操作流程如下：
2.2 插入
插入操作是在查找基数树的过程中执行相关节点或者边的调整操作，直到无法执行进一步操作为止。这种调整操作通常可以分为如下两种情况：
对于当前节点，如果有一个输出边与剩余的串共享一个前缀，此时将该输出边拆分成两条边，其中一条边标记为公共前缀。这时候转变成了第二种情况。
对于当前节点，此时所有的输出边都没有和剩余的串共享一个前缀，此时直接添加一个新的输出边，并用输出串的所有剩余元素进行标记。
以下是插入时可以遇到的几种情况示例，其中用 r 表示基数树根节点，带空标签的边表示一个串的结束。
插入"water"
插入"slower"，同时保留"slow"
插入"test"，它是"tester"的前缀
插入"team"，同时将"test"进行拆分并且创建了一个带"st"标签的新边
插入"toast"，同时将"te"进行拆分并且将之前的串移到树的下一层
2.3 删除
要从基数树中删除串 x，首先需要定位到表示 x 的叶子节点。如果 x 存在，则将相应的叶子节点移除，同时作如下的结构调整：
如果该叶子节点的父节点只有一个额外的子节点（不包括 x 自身），那么将子节点的标签追加到父节点的标签之后，并且将该子节点删除。
否则不作调整。
3 Linux Radix Tree
Linux radix tree 是一种采用基数树数据结构来将一个值（通常是指针）关联到一个整数类型键的机制。
3.1 内部结构
Linux radix tree 的叶子节点结构如下图所示，该节点包含了多个槽（slot），每个 slot 包含了一个指针，它指向了 radix tree 创建者感兴趣的东西（通常是一个结构体或者一段内存），而空的 slot 包含了 NULL 指针。
Linux radix tree 是一种”胖型“树结构，在 Linux 2.6 版本中每个树节点包含了 64 个 slot，每个 slot 都是通过整数类型的键值的其中一部分进行索引。如果键值的最大取值小于 64，那么整棵树可以表示成单个节点，但是通常情况下键值的范围是相当大的，否则就直接使用一个简单的数组即可而无需使用 radix tree。一个稍大点的 radix tree 结构类似下图：
上图的 radix tree 有三层节点，内核在 radix tree 中查找一个特定的键值的基本步骤如下：
键值中最高 6 bits 用于查找根节点中合适的 slot；
键值中随后的 6 bits 用于在中间节点中对 slot 进行索引；
键值中最后的 6 bits 则指向了包含了指向实际值的指针的 slot。
没有子节点的节点不被包含在 radix tree 中，因此 radix tree 能够为稀疏树结构提供高效的存储方式。
3.3 内核 API
Linux 内核提供了相当多的 API 接口，方便内核用户进行创建、查找、插入、遍历和删除等操作。下面介绍一些最常用的 Radix Tree API 接口。
3.3.1 声明和初始化
Linux 提供了两种声明和初始化 radix tree 的方法：
RADIX_TREE：这个宏静态声明并初始化了一个名为 name 的 radix tree。
INIT_RADIX_TREE：这个宏用于在运行时对 radix tree 进行初始化。
在上面两种方式中，都必须提供 gfp_mask 来制定内存分配的策略，例如当 radix tree 操作（尤其是插入操作）需要在原子上下文中执行时，给定的 mask 必须是 GFP_ATOMIC。
3.3.2 插入
该方法将键值 index 关联的元素 item 插入到 radix tree 树结构 root 中，成功时返回值为 0。
该方法可能触发内存分配操作，如果内存分配失败，那么插入操作失败并且返回值为-ENOMEM。
该方法不会覆写一个已经存在的元素，如果 index 已经存在于 radix tree 中，该方法将会返回-EEXIST。
3.3.3 删除
该方法将键值 index 关联的元素从 radix tree 中移除，如果该元素存在则返回指向该元素的指针。需要注意的是，该方法并不会释放元素的内存空间。
3.3.4 内存预分配
Linux 内核提供了一对专用的函数来帮助避免 radix tree 插入操作失败的情况：
radix_tree_preload：该方法尝试分配足够的内存来保证下一次 radix tree 插入操作不会失败。它预分配的数据结构存储在 per-CPU 变量中，这意味着该函数的调用方必须在其允许调度或者被移动到不同的处理器之前执行插入操作。因此该函数执行成功后会禁用抢占再返回，调用者必须确保最终会重新开启抢占（通过调用 radix_tree_preload_end 方法）。如果失败，该方法返回-ENOMEM，同时不会禁用抢占。
radix_tree_preload_end：重新开启抢占，与 radix_tree_preload 配对使用。
3.3.5 查找
radix_tree_lookup：在 radix tree 中查找键值 index 并且返回其关联的元素（查找失败返回 NULL）。
radix_tree_lookup_slot：功能同 radix_tree_lookup，但返回的是指向 slot 的指针，而 slot 中存储了指向元素的指针，可以简单理解为该方法返回的是元素的二级指针，调用者可以通过这个方法修改键值 key 指向新的元素。如果元素不存在，该方法不会为其创建一个 slot，因此它不能用于取代 radix_tree_insert()方法。
3.3.6 遍历
该宏用于遍历 radix tree 中所有的非空 slot：
slot：指向 slot 的指针，类型为 void**。
root：指向 radix tree 根节点的指针，类型为 struct radix_tree_root *。
iter：类型为 struct radix_tree_iter *的指针，iter->index 包含了当前元素的索引。
start：遍历的起始索引。
3.3.7 销毁
Linux 内核并没有提供用于销毁和回收 radix tree 内存空间的 API，这意味着 radix tree 会永久存在于内存中直到通过其他方式手动释放。在实践中，通常的方法是遍历 radix tree 中的所有元素并将其从 radix tree 中移除，然后对全部的元素调用对应的内存释放方法（kfree 等）。
4 示例
下面演示了 Linux radix tree API 的基本使用：
编译运行输出如下：
5 参考资料
Trees I: Radix trees：https://lwn.net/Articles/175432/
Radix Tree：https://en.wikipedia.org/wiki/Radix_tree
Why we use radix-tree(or xarray) for storing page caches?：https://stackoverflow.com/questions/62447084/why-we-use-radix-treeor-xarray-for-storing-page-caches
关注微信公众号：Linux 内核拾遗
还未添加个人签名 2023-01-12 加入
还未添加个人简介
评论