Linux6.1内核中maple_tree的应用--find_vma

🕗 发布于 2024-12-07 10:29 学习 memory maple tree

一、前言

在Linux6.1版本之前，内核中对于虚拟地址空间（VMA）是基于红黑树+双向链表进行实现的，之所以选取两种数据结构组织，是因为红黑树的查询效率较高，但遍历的时间复杂度也高，而双向链表适合遍历，但查询的效率低下。因此内核采用这两种数据结构进行管理，来取长补短。

红黑树+双向链表的组织方式在很长一段时间都被大家认可，但随着近年来cpu核数的扩展，应用程序的线程数量也随之增加，多线程情况下锁的争用问题也逐渐浮现出来了：

红黑树的修改需要同步到双向链表
红黑树的平衡操作，会影响多个节点。

在Linux6.1版本，对VMA的管理被替换成maple_tree。这种数据结构按照无锁的方式进行设计，使用Linux中的线程安全RCU无锁编程来实现。

struct maple_tree {
union {
spinlock_tma_lock;
lockdep_map_pma_external_lock;
};
void __rcu      *ma_root;
unsigned intma_flags;
};

接下来我们着重分析一下在对VMA的操作里，maple_tree的应用，在此之前，先了解一下 ma_state 和节点状态值。

二、预备知识

ma_state 结构体是一个在枫树（Maple Tree）操作期间维护操作状态的结构。它包含了指向操作树的指针、当前操作的索引范围、当前节点以及其他与操作相关的信息。每次进行插入、查找或删除操作时，ma_state 中的数据会被更新，以便在操作过程中跟踪树的状态，其定义如下：

struct ma_state {
struct maple_tree *tree;/* 指向当前操作的枫树 */
unsigned long index;/* 操作范围的起始索引位置 */
unsigned long last;/* 表示当前操作所涉及范围的结束索引值 */
struct maple_enode *node;/* 包含此entry的节点，它是一个 maple_enode 结构，保存了当前范围内的条目 */
unsigned long min;/* 用于表示当前节点的最小索引值 */
unsigned long max;/* 用于表示当前节点的最大索引值*/
struct maple_alloc *alloc;/* 表示为当前操作分配的节点，maple_alloc结构体中包含slot数组 */
unsigned char depth;/*树的当前深度 */
unsigned char offset;//当前在节点中的插槽的位置
unsigned char mas_flags;
};

在枫树中，node 和 index, last 之间的关系非常紧密。index 和 last 定义了一个范围，而该范围内的条目存储在 node 中。在这个结构体中，记录了对maple_tree的操作，以及对应的状态信息。

节点的状态信息一般存储在struct maple_enode *node中，其状态信息有几个重要的如下：

MAS_START：代表这棵树还没被搜索过
MAS_ROOT：代表这棵树已经被搜索过了，条目存在于树根，即其索引为0，长度为1。这个树中只要这一个条目
MAS_NONE ：表示我们搜索了该树，但该树中没有包含该条目的节点
MA_ERROR：代表错误

三、源码分析

3.1 find_vma

find_vma的代码 mm/nommu.c中定义，其核心是通过MA_STATE构建结构体mas，再通过调用mas_walk函数去完成遍历查找。

/*
 * look up the first VMA in which addr resides, NULL if none
 * - should be called with mm->mmap_lock at least held readlocked
 */
struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
{
MA_STATE(mas, &mm->mm_mt, addr, addr);

return mas_walk(&mas);
}

其中MA_STATE宏的定义如下：

#define MA_STATE(name, mt, first, end)\
struct ma_state name = {\
.tree = mt,\
.index = first,\
.last = end,\
.node = MAS_START,\
.min = 0,\
.max = ULONG_MAX,\
.alloc = NULL,\
}

在maple_tree结构体构造完毕之后，则调用mas_walk函数去查询。

3.2 mas_walk

在树结构中根据 mas->index 搜索一个特定的节点，并在搜索过程中更新 mas->index 和 mas->last 以维持该状态的范围。具体如下：

通过mas_state_walk() 来尝试获取当前的条目
如果该枫树还没查找，则重新执行上面的步骤
如果该枫树只有一个节点，并且当前查找的索引值为0，说明第一个entry就是要查找的，则将其的结束索引值设置为0。如果当前查找的索引值不为0，说明要查找的entry不是第一个，则将起始索引设置为1，结束索引设置为ULONG_MAX。并返回当前查找的条目。
如果枫树为空，则重新设置查找范围为0-ULONG_MAX，并返回当前查找的条目

void *mas_walk(struct ma_state *mas)
{
void *entry;

retry:
    // 调用 mas_state_walk() 来尝试获取当前的条目
entry = mas_state_walk(mas);
  //如果mas->node是MAS_START，则说明这棵树还没开始查找，则重新尝试
if (mas_is_start(mas))
goto retry;
//如果mas->node是 MAS_ROOT，说明该树只有一个节点，则
if (mas_is_ptr(mas)) {
        //此时如果当前的索引值index=0，说明查找操作在起始的节点，则将 mas->last 置为 0，并返回当前查找的条目
if (!mas->index) {
mas->last = 0;
} else {
         //如果当前索引值index不为0，将 mas->index 置为 1，更新索引值。将 mas->last 置为 ULONG_MAX，重置查找范围
mas->index = 1;
mas->last = ULONG_MAX;
}
return entry;
}
//如果mas->node为 MAS_NONE，说明节点无效，则设置查找范围为0-ULONG_MAX，并返回当前查找的条目
if (mas_is_none(mas)) {
mas->index = 0;
mas->last = ULONG_MAX;
}

return entry;
}

3.3 mas_state_walk

在mas_walk() 函数中调用mas_state_walk()函数去获取当前查询的条目。其具体工作是：

根据mas_start函数去设置枫树的状态
查看mas->node的值，去判断返回当前的条目还是NULL
如果mas->node的值不为MAS_NONE或MAS_ROOT，则说明枫树是一颗有多个节点的树，因此通过函数mtree_range_walk()去遍历查找

static inline void *mas_state_walk(struct ma_state *mas)
{
void *entry;

entry = mas_start(mas);//设置枫树的状态
    //如果mas->node是MAS_NONE，则说明是空树，返回NULL
if (mas_is_none(mas))
return NULL;
 //如果mas->node是MAS_ROOT，则说明节点有效，返回当前的条目
if (mas_is_ptr(mas))
return entry;

return mtree_range_walk(mas);//实际的调用操作是通过mtree_range_walk()函数来实现的
}

接下来分析，如何去设置枫树的状态函数mas_start()

3.3.1 mas_start

该函数会根据mas->node的值进行如下操作：

mas->node!==MAS_START：则返回NULL
否则，代表这棵树还没遍历，则初始化mas的值，并获取枫树的根节点，根据枫树类型去做处理：
- 如果枫树是空树，则设置偏移量mas->offset = MAPLE_NODE_SLOTS，并返回NULL
- 如果枫树具有多个节点，则设置其depth为1，返回NULL
- 如果枫树仅包含一个根节点，则根据index的值去判定返回根节点还是NULL

//该函数用于设置当前操作的枫树的状态，即设置mas->node
static inline struct maple_enode *mas_start(struct ma_state *mas)
{
    //如果mas->node是MAS_START，则初始化mas的成员
if (likely(mas_is_start(mas))) {
struct maple_enode *root;

mas->node = MAS_NONE;
mas->min = 0;
mas->max = ULONG_MAX;
mas->depth = 0;
mas->offset = 0;

root = mas_root(mas);
/* 具有多个节点的树 */
if (likely(xa_is_node(root))) {
mas->depth = 1;
mas->node = mte_safe_root(root);
return NULL;
}

/* 空树 */
if (unlikely(!root)) {
mas->offset = MAPLE_NODE_SLOTS;
return NULL;
}

/* 代表树中仅包含一个节点，检查mas->index是否大于0。如果是则返回NULL,否则返回当前的条目entry */
mas->node = MAS_ROOT;
mas->offset = MAPLE_NODE_SLOTS;
if (mas->index > 0)
return NULL;

return root;
}
    
    //如果节点的状态不是MAS_START或者有错误，则返回NULL
return NULL;
}

在mas_state_walk()函数中通过检查枫树状态不是MAS_PTR和MAS_NONE，则调用mtree_range_walk()进行遍历查找的

3.3.2 mtree_range_walk

这个函数主要是用于遍历枫树，通过给定的索引 (mas->index) 查找树中符合条件的节点，并逐层遍历直到找到叶节点，同时更新相关状态。具体工作如下：

首先保存当前节点以及当前节点的最大最小索引值，在去做遍历：
- 首先初始化offset=0，并保存当前节点。然后根据函数ma_pivots获取当前节点的pivots，pivot 在树的内部节点中用于划分范围，每个 pivot 范围表示一个节点的边界。
- 根据pivots[offset]以及mas->index的大小进行不同的处理，这里借助了二分法的思想。如果pivots[offset]值大于等于给定的索引mas->index，则将pivots[offset]设置为新的max，接着去获取当前节点的slots，然后根据offset获取下一个节点。
- 如果pivots[offset]值小于给定的索引mas->index，则offset++，继续寻找下一个 pivot，直到找到大于等于 mas->index 的 pivot，找到后更新最小值为 pivots[offset-1]+1
- 一直遍历，直到到达叶子节点。在遍历完成之后，更新mas结构体，并返回当前的节点。

//根据给定的索引（mas->index）查找并更新树中的节点，并且逐步遍历树的每一层，直到找到符合条件的叶节点
static inline void *mtree_range_walk(struct ma_state *mas)
{
unsigned long *pivots;
unsigned char offset;
struct maple_node *node; 
struct maple_enode *next, *last;
enum maple_type type;
void __rcu **slots;
unsigned char end;
unsigned long max, min;
unsigned long prev_max, prev_min;
/* 保存当前操作的节点及当前节点的最小最大的索引值 */
next = mas->node;
min = mas->min;
max = mas->max;
do {
offset = 0;
last = next;//遍历
node = mte_to_node(next);//将节点强制转换为maple_node类型
type = mte_node_type(next);
        //获取当前节点的 pivots 数组
pivots = ma_pivots(node, type);
        //获取数据的结束位置
end = ma_data_end(node, type, pivots, max);
        //如果当前的节点是死节点，即父节点无效，则返回NULL
if (unlikely(ma_dead_node(node)))
goto dead_node;
//检查 pivots[offset] 是否大于等于给定的索引，如果是，则更新pivots[offset]为最大值
if (pivots[offset] >= mas->index) {
            //将当前节点的max和min更新为prev的max和min
prev_max = max;
prev_min = min;
max = pivots[offset];
goto next;
}
//如果 pivots[offset] 小于 mas->index，继续寻找下一个 pivot，直到找到大于等于 mas->index 的 pivot，找到更新最小值为 pivots[offset - 1] + 1
do {
offset++;
} while ((offset < end) && (pivots[offset] < mas->index));

prev_min = min;
min = pivots[offset - 1] + 1;
prev_max = max;
if (likely(offset < end && pivots[offset]))
max = pivots[offset];

next:
        //获取当前节点的slots
slots = ma_slots(node, type);
        //根据 offset 获取下一个子节点
next = mt_slot(mas->tree, slots, offset);
        
        //如果标记为死节点，返回null
if (unlikely(ma_dead_node(node)))
goto dead_node;
} while (!ma_is_leaf(type));//继续遍历，直到到达叶子节点
    
//遍历完成，更新mas结构体，并返回当前的节点
mas->offset = offset;
mas->index = min;
mas->last = max;
mas->min = prev_min;
mas->max = prev_max;
mas->node = last;
return (void *) next;

dead_node:
mas_reset(mas);
return NULL;
}

笔者能力有限，如有错误请指出。

原文地址：https://blog.csdn.net/qq_43573047/article/details/144300423

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：大数据新视界 -- Hive 元数据管理工具与实践（下）（28 / 30）
下一篇：简易图书管理系统

.NET(C#) 如何配置用户首选项及保存用户设置
.NET(C#) 如何配置用户首选项及保存用户设置
阅读更多2024-12-14
【最新】北大数字普惠金融指数数据集-省市县（2011-2023年）
郭峰,王靖一,王芳,孔涛,张勋,程志云.测度中国数字普惠金融发展:指数编制与空间特征[J].经济学(季刊),2020,19(04):1401-1418.时间跨度：省级和城市级指数时间跨度为2011-2
阅读更多2024-12-14
GESP202412 四级【Recamán】题解（AC）
a11ak−1−kkakak−1−kak−1k小杨想知道 Recamán 数列的前n项从小到大排序后的结果。手动计算非常困难，小杨希望你能帮他解决这个问题。
阅读更多2024-12-14
IDEA遇到EasyConnect中的网络资源无法访问的问题
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。原文链接：https://blog.csdn.net/wanshanyu_/article/de
阅读更多2024-12-14
双目摄像头标定方法
此时已经完成标定，左下角为反投影误差，右边为外参可视化。将双目左右目拍的图像上传（左右目最好不少于20张）此时回到主页面，即可看到成功导出。把这些误差大的删除即可。
阅读更多2024-12-14
Servlet、omcat服务器架构与工作原理
Servlet是运行在服务器端的Java程序，它的主要职责之一是接收并处理来自客户端（如浏览器）的HTTP请求。当客户端发送一个请求到服务器时，Servlet可以解析请求中的信息，例如请求的URL路径
阅读更多2024-12-14
Vue生命周期钩子函数：深入解析与实践
作为高级Vue前端开发人员，对Vue组件的生命周期钩子函数有着深刻的理解是至关重要的。生命周期钩子函数是指在Vue组件的创建、更新、销毁等过程中，Vue自动调用的一系列方法。通过这些钩子函数，我们可以
阅读更多2024-12-14
安卓开发--使用android studio发布APP
app发布
阅读更多2024-12-14
数据结构与算法学习笔记----拓扑排序
@ author: 明月清了个风。
阅读更多2024-12-14
python 将数据保存到现有的Excel文件的新工作表
out_file = ‘query.xlsx’df1 = pd.DataFrame(out_data)若直接写入：df1.to_excel(out_file, index=False, sheet_n
阅读更多2024-12-14