基于 Linux 内核源码（截至 2026-03 master 分支）进行分析。 主要参考文件：
lib/maple_tree.c（7268 行，Maple Tree 核心实现）include/linux/maple_tree.h（数据结构与 API 声明）mm/mmap.c（mmap 系统调用与 VMA 管理主体逻辑）include/linux/mm_types.h（vma_iterator、mm_struct定义）mm/vma.c（VMA 辅助操作，合并/分裂/迭代）
- 背景：为什么需要 Maple Tree
- Maple Tree 设计原理
- 核心数据结构
- 节点类型详解
- 指针编码与 RCU 机制
- Maple Tree API 分层
- 读操作：RCU 安全遍历
- 写操作与预分配机制
- 锁模型
- VMA 管理：mm_struct.mm_mt
- vma_iterator：游标迭代器
- VMA 查找 API
- mmap_region 流程中的 Maple Tree
- VMA 分裂与合并
- vm_area_free 与树的联动
- 性能对比与改进
- 调试支持
- 架构总览
- 从 rbtree 到 Maple Tree 的迁移历史
- Maple Tree 操作深度分析
- RCU 保护下的无锁读详解
- vm_area_struct 完整字段解析
- vm_flags 语义深度分析
- mmap/munmap 完整流程分析
- VMA 合并条件完整检查链
- address_space 与 VMA 的关联
- /proc/PID/maps 输出生成机制
- Per-VMA 锁机制详解
- fork() 中的 VMA 树复制
- Maple Tree 在其他子系统的应用
- 参考源码位置汇总（完整版）
Linux 内核在 5.x 时代管理进程虚拟内存区域（VMA）依赖两个并行维护的数据结构：
- 红黑树（rbtree）：
mm_struct.mm_rb，按vm_start索引，支持 O(log N) 查找 - 双向链表：
vm_area_struct.vm_next/vm_prev，维护 VMA 的线性顺序
这种双结构的设计导致以下问题：
- 冗余维护：每次插入、删除、分裂 VMA 都要同时更新两种结构，代码路径复杂且易出错
- 顺序遍历低效：链表遍历是 O(N) 线性扫描，无法利用树结构的局部性
- gap 查找（mmap 寻找空洞）成本高：旧版依赖
rb_subtree_gap（记录子树最大空洞），在每次 VMA 变动时自底向上更新，实现繁琐 - cache 不友好：链表指针分散在
vm_area_struct各处，批量遍历 cache miss 率高 - 并发复杂度：双结构保持一致性需要同时持锁修改两处，增加了 mmap_lock 的临界区长度
Maple Tree 由 Oracle 工程师 Liam R. Howlett 和 Matthew Wilcox（willy@infradead.org）开发，版权声明见 lib/maple_tree.c 第 1–9 行：
// lib/maple_tree.c 第 1-9 行
// SPDX-License-Identifier: GPL-2.0+
/*
* Maple Tree implementation
* Copyright (c) 2018-2022 Oracle Corporation
* Authors: Liam R. Howlett <Liam.Howlett@oracle.com>
* Matthew Wilcox <willy@infradead.org>
* Copyright (c) 2023 ByteDance
* Author: Peng Zhang <zhangpeng.00@bytedance.com>
*/Maple Tree 在 Linux 6.1 正式合并主线，替换了 VMA 管理中的 rbtree + linked list 双结构，同时实现了：
- 用单一数据结构同时支持快速查找（O(log N)）和高效遍历（游标迭代）
- 内置gap 追踪（
maple_arange_64节点），使mmap寻找空闲地址空间的效率显著提升 - 原生 RCU 安全访问支持，降低读者开销
- 批量预分配节点避免写操作中途因内存不足导致树状态损坏
Maple Tree 本质上是一棵区间 B-Tree（Interval B-Tree），其关键设计思想如下：
与传统 B-Tree 的"点键"不同，Maple Tree 存储的是区间（range），每个槽（slot）对应一个连续地址范围 [min, max]。
lib/maple_tree.c 开头的注释清晰说明了这一点（第 11–53 行）：
* In regular B-Tree terms, pivots are called keys. The term pivot is used to
* indicate that the tree is specifying ranges. Pivots may appear in the
* subtree with an entry attached to the value whereas keys are unique to a
* specific position of a B-tree. Pivot values are inclusive of the slot with
* the same index.
pivot（主元）是区间的包含性右端点，即 slot[i] 对应的范围是 (pivot[i-1], pivot[i]]。
以 64 位系统的 maple_range_64 节点为例，lib/maple_tree.c 第 25–39 行绘制了其布局：
Slots -> | 0 | 1 | 2 | ... | 12 | 13 | 14 | 15 |
┬ ┬ ┬ ┬ ┬ ┬ ┬ ┬ ┬
│ │ │ │ │ │ │ │ └─ Implied maximum
│ │ │ │ │ │ │ └─ Pivot 14
│ │ │ │ │ │ └─ Pivot 13
│ │ │ │ │ └─ Pivot 12
│ │ │ │ └─ Pivot 11
│ │ │ └─ Pivot 2
│ │ └─ Pivot 1
│ └─ Pivot 0
└─ Implied minimum
所有 Maple Tree 节点固定 256 字节，对齐到 256 字节边界（include/linux/maple_tree.h 第 29–38 行）：
// 64bit sizes
#define MAPLE_NODE_SLOTS 31 /* 256 bytes including ->parent */
#define MAPLE_RANGE64_SLOTS 16 /* 256 bytes */
#define MAPLE_ARANGE64_SLOTS 10 /* 240 bytes */256 字节对齐使低 8 位可以用于存储节点类型和元数据，这是后文指针编码的基础。
树的高度由 ma_flags 的 MT_FLAGS_HEIGHT_MASK（bit 2–6，最多 31 层）记录，空树高度为 0，单根节点高度为 1，每增加一层可容纳 16 倍以上的条目。
定义于 include/linux/maple_tree.h 第 222–231 行：
struct maple_tree {
union {
spinlock_t ma_lock;
#ifdef CONFIG_LOCKDEP
struct lockdep_map *ma_external_lock;
#endif
};
unsigned int ma_flags;
void __rcu *ma_root;
};字段说明：
| 字段 | 含义 |
|---|---|
ma_lock |
树内置自旋锁，用于写保护（VMA 管理使用外部 mmap_lock 替代） |
ma_external_lock |
lockdep 专用，指向外部锁的 lockdep_map |
ma_flags |
标志位，包含树高度（bit 2–6）、MT_FLAGS_ALLOC_RANGE、MT_FLAGS_USE_RCU 等 |
ma_root |
RCU 保护的根指针，单条目树时直接存储值，多条目时指向节点 |
关键标志位定义（include/linux/maple_tree.h 第 171–179 行）：
#define MT_FLAGS_ALLOC_RANGE 0x01 // 启用 gap 追踪（用于 mmap 空洞搜索）
#define MT_FLAGS_USE_RCU 0x02 // RCU 模式（节点复用而非 RCU 释放）
#define MT_FLAGS_HEIGHT_OFFSET 0x02 // 树高在 flags 中的偏移
#define MT_FLAGS_HEIGHT_MASK 0x7C // 树高掩码（5 bits，最大高度 31）
#define MT_FLAGS_LOCK_MASK 0x300 // 锁类型掩码
#define MT_FLAGS_LOCK_IRQ 0x100 // IRQ 安全锁
#define MT_FLAGS_LOCK_BH 0x200 // BH 安全锁
#define MT_FLAGS_LOCK_EXTERN 0x300 // 使用外部锁（如 mmap_lock）定义于 include/linux/maple_tree.h 第 285–303 行，是所有节点类型的联合体：
struct maple_node {
union {
struct {
struct maple_pnode *parent;
void __rcu *slot[MAPLE_NODE_SLOTS];
};
struct {
void *pad;
struct rcu_head rcu;
struct maple_enode *piv_parent;
unsigned char parent_slot;
enum maple_type type;
unsigned char slot_len;
unsigned int ma_flags;
};
struct maple_range_64 mr64;
struct maple_arange_64 ma64;
};
};操作游标，定义于 include/linux/maple_tree.h 第 430–446 行：
struct ma_state {
struct maple_tree *tree; /* 操作的树 */
unsigned long index; /* 操作范围起点 */
unsigned long last; /* 操作范围终点 */
struct maple_enode *node; /* 当前所在节点（编码指针） */
unsigned long min; /* 当前节点的隐含最小值 */
unsigned long max; /* 当前节点的隐含最大值 */
struct slab_sheaf *sheaf; /* 批量预分配节点的 slab sheaf */
struct maple_node *alloc; /* 快速路径的单节点预分配 */
unsigned long node_request; /* 需要预分配的节点数 */
enum maple_status status; /* 状态机状态 */
unsigned char depth; /* 写操作下行深度 */
unsigned char offset; /* 在当前节点中的偏移 */
unsigned char mas_flags; /* MA_STATE_PREALLOC 等标志 */
unsigned char end; /* 节点末尾偏移 */
enum store_type store_type; /* 写操作类型 */
};ma_state 充当了位置游标（cursor）的角色，连续操作时可保留树遍历的位置信息，避免从根重新搜索，这是 Maple Tree 相比 rbtree 的核心性能优化之一。
状态机的各状态（enum maple_status，include/linux/maple_tree.h 第 379–388 行）：
enum maple_status {
ma_active, // 游标有效，指向某节点的某槽
ma_start, // 初始状态，下次操作从根开始
ma_root, // 树只有根条目（单值优化）
ma_none, // 未找到条目
ma_pause, // 暂停状态（释放锁后可继续）
ma_overflow, // 超出上界
ma_underflow, // 超出下界
ma_error, // 错误（node 指针携带 errno）
};定义于 include/linux/maple_tree.h 第 137–142 行：
enum maple_type {
maple_dense, // 密集节点：紧凑存储小整数索引
maple_leaf_64, // 64 位叶节点（含 pivot 数组）
maple_range_64, // 64 位区间内部节点
maple_arange_64, // 64 位区间 + gap 追踪节点（仅用于 alloc range 树）
};类型编码存储在编码指针的 bit 3–6 中（MAPLE_NODE_TYPE_SHIFT = 3，MAPLE_NODE_TYPE_MASK = 0x0F）。
定义于 include/linux/maple_tree.h 第 103–113 行：
struct maple_range_64 {
struct maple_pnode *parent;
unsigned long pivot[MAPLE_RANGE64_SLOTS - 1]; // 15 个 pivot
union {
void __rcu *slot[MAPLE_RANGE64_SLOTS]; // 16 个槽
struct {
void __rcu *pad[MAPLE_RANGE64_SLOTS - 1];
struct maple_metadata meta; // 最后一个槽位置存 metadata
};
};
};- 16 个 slot，15 个 pivot：slot[i] 的范围是
(pivot[i-1], pivot[i]]，slot[15] 的上界由父节点提供（隐含最大值） - 叶节点的 slot 存储用户数据（如
struct vm_area_struct *），内部节点的 slot 存储子节点编码指针 struct maple_metadata包含end（数据末尾偏移）和gap（最大 gap 位置），用于快速定位
定义于 include/linux/maple_tree.h 第 124–130 行：
struct maple_arange_64 {
struct maple_pnode *parent;
unsigned long pivot[MAPLE_ARANGE64_SLOTS - 1]; // 9 个 pivot
void __rcu *slot[MAPLE_ARANGE64_SLOTS]; // 10 个槽
unsigned long gap[MAPLE_ARANGE64_SLOTS]; // 10 个 gap 值
struct maple_metadata meta; // gap 字段记录最大 gap 的索引
};maple_arange_64 相比 maple_range_64 多了 gap[] 数组，代价是槽数量从 16 减少到 10（MAPLE_ARANGE64_SLOTS = 10）。
每个 gap[i] 记录 slot[i] 所管辖子树中的最大空洞大小（NULL 区间的最大连续长度）。meta.gap 记录 gap[] 中最大值所在的索引，从而可以在 O(log N) 内定位满足大小要求的空洞，无需遍历。
这是 VMA 管理中 get_unmapped_area() 高效的关键：mas_empty_area() 和 mas_empty_area_rev() 利用 arange_64 节点的 gap 信息自上而下定位合适的空洞。
密集节点没有 pivot 数组，槽的位置隐式对应索引值（slot[i] 对应 index min + i）。仅用于小范围整数索引（如进程的小 fd 表），在 VMA 管理场景下不直接出现。
槽容量与 pivot 数量统计（lib/maple_tree.c 第 108–131 行）：
static const unsigned char mt_slots[] = {
[maple_dense] = MAPLE_NODE_SLOTS, // 31
[maple_leaf_64] = MAPLE_RANGE64_SLOTS, // 16
[maple_range_64] = MAPLE_RANGE64_SLOTS, // 16
[maple_arange_64]= MAPLE_ARANGE64_SLOTS, // 10
};
static const unsigned char mt_pivots[] = {
[maple_dense] = 0,
[maple_leaf_64] = MAPLE_RANGE64_SLOTS - 1, // 15
[maple_range_64] = MAPLE_RANGE64_SLOTS - 1, // 15
[maple_arange_64]= MAPLE_ARANGE64_SLOTS - 1, // 9
};
static const unsigned char mt_min_slots[] = {
[maple_dense] = MAPLE_NODE_SLOTS / 2, // 15
[maple_leaf_64] = (MAPLE_RANGE64_SLOTS / 2) - 2, // 6
[maple_range_64] = (MAPLE_RANGE64_SLOTS / 2) - 2, // 6
[maple_arange_64]= (MAPLE_ARANGE64_SLOTS / 2) - 1,// 4
};最少槽数（mt_min_slots）定义了节点欠满时触发**再平衡（rebalance）**的阈值，类似 B-Tree 的半满规则。
maple_range_64 节点（256 字节）：
+--------+--------+--------+--------+--------+--------+--------+
| parent | piv0 | piv1 | piv2 | ... | piv14 | meta |
| 8 bytes| 8bytes | 8bytes | 8bytes | ... | 8bytes | 8bytes |
+--------+--------+--------+--------+--------+--------+--------+
| slot0 | slot1 | slot2 | slot3 | ... | slot14 | slot15 |
| 8 bytes| 8bytes | 8bytes | 8bytes | ... | 8bytes | 8bytes |
+--------+--------+--------+--------+--------+--------+--------+
共 1 + 15 + 16 = 32 个 8 字节字段 = 256 字节
maple_arange_64 节点（256 字节）：
+--------+--------+--------+--------+--------+--------+
| parent | piv0 | piv1 | ... | piv8 | meta |
| 8 bytes| 8bytes | 8bytes | ... | 8bytes | 8bytes |
+--------+--------+--------+--------+--------+--------+
| slot0 | slot1 | ... | slot9 | gap0 | gap1 |
| 8 bytes| 8bytes | ... | 8bytes | 8bytes | 8bytes |
+--------+--------+--------+--------+--------+--------+
| gap2 | ... | gap9 |
| 8bytes | ... | 8bytes |
+--------+--------+--------+
共 1 + 9 + 1 + 10 + 10 = 31 个 8 字节字段 = 248 字节
（加上对齐填充到 256 字节）
Maple Tree 大量使用指针位域复用技术。节点 256 字节对齐，低 8 位（MAPLE_NODE_MASK = 255UL）用于存储元数据：
- bit 0：
MAPLE_PARENT_ROOT (0x01)— 若置 1，表示该节点是根节点，剩余位指向maple_tree本身 - bit 1–2：用于编码父节点类型（
MAPLE_PARENT_RANGE64 = 0x06，MAPLE_PARENT_RANGE32 = 0x02） - bit 3–6（非叶节点指针）：编码所指子节点的
enum maple_type，偏移为MAPLE_ENODE_TYPE_SHIFT = 3 - bit 2：
MAPLE_ENODE_NULL (0x04)— 该节点子树中存在 NULL 条目
mte_node_type() 函数（lib/maple_tree.c 第 231–236 行）从编码指针提取节点类型：
static __always_inline enum maple_type mte_node_type(
const struct maple_enode *entry)
{
return ((unsigned long)entry >> MAPLE_NODE_TYPE_SHIFT) &
MAPLE_NODE_TYPE_MASK;
}RCU 的核心挑战是：写操作替换节点后，旧节点上的 RCU 读者仍在访问，必须安全地判断节点是否已被移除。
Maple Tree 的解决方案：当节点从树中移除时，将 node->parent 设置为指向自身（mte_set_node_dead()，lib/maple_tree.c 第 332–336 行）：
static inline void mte_set_node_dead(struct maple_enode *mn)
{
mte_to_node(mn)->parent = ma_parent_ptr(mte_to_node(mn));
smp_wmb(); /* Needed for RCU */
}读者在访问节点数据前检查 ma_dead_node()（lib/maple_tree.c 第 566–574 行）：
static __always_inline bool ma_dead_node(const struct maple_node *node)
{
struct maple_node *parent;
/* Do not reorder reads from the node prior to the parent check */
smp_rmb();
parent = (void *)((unsigned long) node->parent & ~MAPLE_NODE_MASK);
return (parent == node);
}若检测到 dead node，读操作重试（从 ma_start 重新开始）。
节点释放通过 ma_free_rcu() 使用 kfree_rcu()（lib/maple_tree.c 第 205–209 行）：
static void ma_free_rcu(struct maple_node *node)
{
WARN_ON(node->parent != ma_parent_ptr(node));
kfree_rcu(node, rcu);
}struct maple_node 的 rcu 字段（struct rcu_head rcu，见 include/linux/maple_tree.h 第 294 行）与 slot[] 数组复用同一内存空间，不额外占用节点体积。
Maple Tree 提供两层 API：
+----------------------------------------------------------+
| High-Level (Simple) API |
| mtree_store() mtree_insert() mtree_load() |
| mtree_erase() mtree_alloc_range() mtree_destroy() |
+----------------------------------------------------------+
| Advanced (Cursor-based) API |
| ma_state mas_find() mas_next() mas_prev() |
| mas_store() mas_walk() mas_preallocate() |
+----------------------------------------------------------+
| Internal Implementation |
| mas_start() mas_descend() mas_ascend() |
| mas_wr_store_entry() mas_wr_preallocate() |
+----------------------------------------------------------+
High-Level API 每次操作都在函数内部完成加锁/解锁，适合简单单次操作。Advanced API 保留 ma_state 游标，适合批量操作、跨操作位置保持等场景。
最简单的点查找（lib/maple_tree.c 第 5882–5911 行）：
void *mtree_load(struct maple_tree *mt, unsigned long index)
{
MA_STATE(mas, mt, index, index);
void *entry;
trace_ma_read(TP_FCT, &mas);
rcu_read_lock();
retry:
entry = mas_start(&mas);
if (unlikely(mas_is_none(&mas)))
goto unlock;
if (unlikely(mas_is_ptr(&mas))) {
if (index)
entry = NULL;
goto unlock;
}
entry = mtree_lookup_walk(&mas);
if (!entry && unlikely(mas_is_start(&mas)))
goto retry;
unlock:
rcu_read_unlock();
if (xa_is_zero(entry))
return NULL;
return entry;
}整个查找在 rcu_read_lock() 保护下进行，遇到 dead node 时自动重试（mas_is_start() 检查）。注意这里不需要持有任何互斥锁，是真正的无锁并发读。
mas_find() 是游标查找的核心，定义于 lib/maple_tree.c 第 5614–5626 行：
void *mas_find(struct ma_state *mas, unsigned long max)
{
void *entry = NULL;
if (mas_find_setup(mas, max, &entry))
return entry;
/* Retries on dead nodes handled by mas_next_slot */
entry = mas_next_slot(mas, max, false);
/* Ignore overflow */
mas->status = ma_active;
return entry;
}mas_find_setup() 处理游标状态机：ma_active 时直接返回下一个（无需重新搜索），ma_pause 时从上次暂停的位置继续，ma_start 时从根重新搜索。这种状态机设计让游标可以安全地在释放锁后恢复遍历。
高级别的迭代宏（include/linux/maple_tree.h 第 594–595 行）：
#define mas_for_each(__mas, __entry, __max) \
while (((__entry) = mas_find((__mas), (__max))) != NULL)等效的反向迭代（第 608–609 行）：
#define mas_for_each_rev(__mas, __entry, __min) \
while (((__entry) = mas_find_rev((__mas), (__min))) != NULL)当遍历过程中需要短暂释放锁（例如执行可能阻塞的操作），需要先调用 mas_pause()（lib/maple_tree.c 第 5508–5512 行）：
void mas_pause(struct ma_state *mas)
{
mas->status = ma_pause;
mas->node = NULL;
}恢复时，mas_find() 检测到 ma_pause 状态，会从 mas->last + 1 位置重新搜索，安全跳过已过期的游标位置。
高层 API mtree_store_range() 的实现（lib/maple_tree.c 第 5924–5942 行）：
int mtree_store_range(struct maple_tree *mt, unsigned long index,
unsigned long last, void *entry, gfp_t gfp)
{
MA_STATE(mas, mt, index, last);
int ret = 0;
if (WARN_ON_ONCE(xa_is_advanced(entry)))
return -EINVAL;
if (index > last)
return -EINVAL;
mtree_lock(mt);
ret = mas_store_gfp(&mas, entry, gfp);
mtree_unlock(mt);
return ret;
}mtree_store() 是其单点版本（第 5955–5960 行），直接调用 mtree_store_range(mt, index, index, entry, gfp)。
写操作前会分析存储场景，选择最优路径（include/linux/maple_tree.h 第 144–155 行）：
enum store_type {
wr_invalid,
wr_new_root, // 写入全新的根
wr_store_root, // 修改根指针
wr_exact_fit, // 恰好覆盖一个现有区间（最快路径）
wr_spanning_store, // 跨越多个节点的写入（最复杂）
wr_split_store, // 节点已满，需要分裂
wr_rebalance, // 节点欠满，需要再平衡
wr_append, // 追加到节点末尾
wr_node_store, // 普通节点内写入
wr_slot_store, // 只修改单个 slot（最快路径之一）
};mas_wr_store_type()（lib/maple_tree.c 第 3893–3934 行）在 mas_wr_preallocate() 前调用，根据目标区间与当前树状态决定写入类型，从而精确计算需要预分配的节点数。
lib/maple_tree.c:3893 中，决策流程如下：
mas_wr_store_type()
|
+-- mas 是 none/ptr 状态？ --> wr_store_root
|
+-- mas_wr_walk() 返回 false（跨多节点）？ --> wr_spanning_store
|
+-- 精确命中现有区间？ --> wr_exact_fit
|
+-- 目标是整树？ --> wr_new_root
|
+-- 计算新末尾偏移 new_end
| +-- new_end < mt_min_slots? --> wr_rebalance（或 wr_node_store 若为根）
| +-- new_end >= mt_slots? --> wr_split_store
| +-- 追加场景？ --> wr_append
| +-- 单 slot 更新？ --> wr_slot_store
| +-- 其他 --> wr_node_store
Maple Tree 的关键设计：在获取树锁之前完成节点分配，避免持锁时因内存不足导致问题。
mas_preallocate() 定义于 lib/maple_tree.c 第 5183–5207 行：
int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp)
{
MA_WR_STATE(wr_mas, mas, entry);
mas_wr_prealloc_setup(&wr_mas);
mas->store_type = mas_wr_store_type(&wr_mas);
mas_prealloc_calc(&wr_mas, entry); // 计算 node_request
if (!mas->node_request)
goto set_flag;
mas->mas_flags &= ~MA_STATE_PREALLOC;
mas_alloc_nodes(mas, gfp); // 实际分配
if (mas_is_err(mas)) {
int ret = xa_err(mas->node);
mas->node_request = 0;
mas_destroy(mas);
mas_reset(mas);
return ret;
}
set_flag:
mas->mas_flags |= MA_STATE_PREALLOC;
return 0;
}mas_alloc_nodes() 的实现（lib/maple_tree.c 第 1098–1148 行）使用两级分配策略：
- 快速路径：
node_request == 1时，优先从mas->alloc单节点缓存获取，回退到mt_alloc_one(gfp) - 批量路径：
node_request > 1时，使用slab sheaf（struct slab_sheaf *sheaf）——kmem_cache_prefill_sheaf()批量预分配
Slab sheaf 是内核 6.x 引入的批量 slab 分配优化，容量由 maple_tree_init() 中的 sheaf_capacity = 32 指定（lib/maple_tree.c 第 5866–5872 行）：
void __init maple_tree_init(void)
{
struct kmem_cache_args args = {
.align = sizeof(struct maple_node),
.sheaf_capacity = 32,
};
maple_node_cache = kmem_cache_create("maple_node",
sizeof(struct maple_node), &args,
SLAB_PANIC);
}未使用的预分配节点通过 mas_destroy() / mt_return_sheaf() 归还给 slab，不会泄露。
mtree_insert_range() 与 mtree_store_range() 的区别在于：insert 在目标范围已存在条目时返回 -EEXIST，不覆盖（lib/maple_tree.c 第 5973–5997 行）：
int mtree_insert_range(struct maple_tree *mt, unsigned long first,
unsigned long last, void *entry, gfp_t gfp)
{
MA_STATE(ms, mt, first, last);
...
mtree_lock(mt);
retry:
mas_insert(&ms, entry);
if (mas_nomem(&ms, gfp)) // OOM 时释放锁重分配后重试
goto retry;
mtree_unlock(mt);
...
}mtree_alloc_range() 用于在指定范围内自动寻找并分配一段空洞（lib/maple_tree.c 第 6017–6053 行），内部调用 mas_empty_area() 利用 arange_64 节点的 gap 信息：
int mtree_alloc_range(struct maple_tree *mt, unsigned long *startp, ...)
{
MA_STATE(mas, mt, 0, 0);
if (!mt_is_alloc(mt)) // 必须有 MT_FLAGS_ALLOC_RANGE
return -EINVAL;
...
mtree_lock(mt);
retry:
ret = mas_empty_area(&mas, min, max, size); // 利用 gap 快速定位
if (ret) goto unlock;
mas_insert(&mas, entry);
if (mas_nomem(&mas, gfp))
goto retry;
...
}mas_nomem() 是写操作的标准 OOM 处理函数（lib/maple_tree.c 第 5842–5861 行）：
bool mas_nomem(struct ma_state *mas, gfp_t gfp)
__must_hold(mas->tree->ma_lock)
{
if (likely(mas->node != MA_ERROR(-ENOMEM)))
return false;
if (gfpflags_allow_blocking(gfp) && !mt_external_lock(mas->tree)) {
mtree_unlock(mas->tree);
mas_alloc_nodes(mas, gfp); // 释放锁后分配（允许阻塞）
mtree_lock(mas->tree);
} else {
mas_alloc_nodes(mas, gfp);
}
...
mas->status = ma_start;
return true; // 返回 true 表示需要重试
}这使得写操作可以在不持锁的情况下进行内存分配，重试时重新从根搜索，保证了树的一致性。
用于通用 Maple Tree（如 idr、进程 fd 表等），通过 mtree_lock(mt) / mtree_unlock(mt) 操作（include/linux/maple_tree.h 第 264–267 行）：
#define mtree_lock(mt) spin_lock((&(mt)->ma_lock))
#define mtree_unlock(mt) spin_unlock((&(mt)->ma_lock))对应 ma_state 层：mas_lock(mas) / mas_unlock(mas)（第 464–467 行）。
VMA 管理使用 mmap_lock（struct rw_semaphore）作为外部锁，而非树内置的 spinlock。这通过 MT_FLAGS_LOCK_EXTERN 标志指示。
在 lockdep 模式下，通过 mt_set_external_lock(mt, lock) 将外部锁注册到 Maple Tree，mt_lock_is_held() 验证持锁状态（include/linux/maple_tree.h 第 190–198 行）：
#define mt_lock_is_held(mt) \
(!(mt)->ma_external_lock || lock_is_held((mt)->ma_external_lock))
#define mt_set_external_lock(mt, lock) \
(mt)->ma_external_lock = &(lock)->dep_mapRCU 读者不需要任何锁，直接在 rcu_read_lock() / rcu_read_unlock() 保护的临界区内操作。写操作完成后，旧节点通过 RCU grace period 延迟释放（kfree_rcu(node, rcu)）。
现代内核（6.1+）还支持 per-VMA 粒度的读锁（vm_refcnt），允许无 mmap_lock 读锁的情况下安全访问 VMA。这由 vma_start_read() / vma_end_read() 实现，是比 mmap_lock 更细粒度的锁优化，但这属于 VMA 锁优化的独立话题。
struct mm_struct 中，mm_mt 字段（include/linux/mm_types.h 第 1140 行）直接替代了旧的 mm_rb：
struct mm_struct {
struct {
...
struct maple_tree mm_mt; // 核心：VMA 树（替代 mm_rb + VMA 链表）
unsigned long mmap_base;
unsigned long mmap_legacy_base;
...
int map_count; // VMA 数量（与 mm_mt 同步）
struct rw_semaphore mmap_lock;
...
};
};mm_mt 使用 MT_FLAGS_ALLOC_RANGE | MT_FLAGS_LOCK_EXTERN 初始化（从而启用 gap 追踪和外部锁模式），以 VMA 的虚拟地址范围 [vm_start, vm_end - 1] 为键存储 struct vm_area_struct *。
在进程 mm_struct 创建时（mm_init() 或 dup_mm()），mm_mt 通过 MTREE_INIT_EXT() 宏初始化，外部锁指向 mmap_lock。VMA 的范围 [vm_start, vm_end - 1] 作为区间存入树。
目前 vm_area_struct 仍保留了 shared.rb（struct rb_node rb，include/linux/mm_types.h 第 1040–1043 行），但这是文件反向映射（i_mmap interval tree）使用的，与 VMA 地址空间搜索无关——地址空间搜索已完全由 mm_mt 承担。
struct vma_iterator 是对 ma_state 的轻量包装（include/linux/mm_types.h 第 1497–1499 行）：
struct vma_iterator {
struct ma_state mas;
};VMA_ITERATOR 栈上初始化宏（include/linux/mm_types.h 第 1501–1509 行）：
#define VMA_ITERATOR(name, __mm, __addr) \
struct vma_iterator name = { \
.mas = { \
.tree = &(__mm)->mm_mt, \
.index = __addr, \
.node = NULL, \
.status = ma_start, \
}, \
}注意 .status = ma_start 表示首次使用时从根开始搜索。
vma_iter_init() 函数版本（include/linux/mm_types.h 第 1511–1515 行）：
static inline void vma_iter_init(struct vma_iterator *vmi,
struct mm_struct *mm, unsigned long addr)
{
mas_init(&vmi->mas, &mm->mm_mt, addr);
}游标操作的核心内联函数（include/linux/mm.h 第 1311–1383 行）：
// 前向查找 [当前位置, max) 范围内第一个 VMA
static inline
struct vm_area_struct *vma_find(struct vma_iterator *vmi, unsigned long max)
{
return mas_find(&vmi->mas, max - 1);
}
// 移动到下一个 VMA（第一次调用时返回初始位置处的 VMA）
static inline struct vm_area_struct *vma_next(struct vma_iterator *vmi)
{
return mas_find(&vmi->mas, ULONG_MAX);
}
// 向后移动到下一个区间（包含 NULL 区间）
static inline
struct vm_area_struct *vma_iter_next_range(struct vma_iterator *vmi)
{
return mas_next_range(&vmi->mas, ULONG_MAX);
}
// 移动到上一个 VMA
static inline struct vm_area_struct *vma_prev(struct vma_iterator *vmi)
{
return mas_prev(&vmi->mas, 0);
}便利宏（include/linux/mm.h 第 1378–1383 行）：
#define for_each_vma(__vmi, __vma) \
while (((__vma) = vma_next(&(__vmi))) != NULL)
/* 遍历 [vmi当前位置, end) 范围内所有 VMA */
#define for_each_vma_range(__vmi, __vma, __end) \
while (((__vma) = vma_find(&(__vmi), (__end))) != NULL)典型使用模式（来自 mm/vma.c 第 647–688 行的 validate_mm()）：
VMA_ITERATOR(vmi, mm, 0);
for_each_vma(vmi, vma) {
// 遍历所有 VMA
}定义于 include/linux/mm.h 第 3956–3960 行：
static inline
struct vm_area_struct *vma_lookup(struct mm_struct *mm, unsigned long addr)
{
return mtree_load(&mm->mm_mt, addr);
}直接调用 mtree_load，在 RCU 保护下无锁查找。addr 必须恰好落在某个 VMA 的 [vm_start, vm_end - 1] 区间内才能命中。
定义于 mm/mmap.c 第 902–908 行：
struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
{
unsigned long index = addr;
mmap_assert_locked(mm);
return mt_find(&mm->mm_mt, &index, ULONG_MAX);
}mt_find() 是游标版本的 mtree_load，若 addr 不在任何 VMA 中，则返回 addr 之后的第一个 VMA（语义类似旧版的 find_vma）。
定义于 mm/mmap.c 第 883–891 行：
struct vm_area_struct *find_vma_intersection(struct mm_struct *mm,
unsigned long start_addr,
unsigned long end_addr)
{
unsigned long index = start_addr;
mmap_assert_locked(mm);
return mt_find(&mm->mm_mt, &index, end_addr - 1);
}查找与 [start_addr, end_addr) 相交的第一个 VMA，用于冲突检测（如 MAP_FIXED_NOREPLACE）。
定义于 mm/mmap.c 第 924–936 行，使用 vma_iterator 游标实现：
struct vm_area_struct *
find_vma_prev(struct mm_struct *mm, unsigned long addr,
struct vm_area_struct **pprev)
{
struct vm_area_struct *vma;
VMA_ITERATOR(vmi, mm, addr);
vma = vma_iter_load(&vmi);
*pprev = vma_prev(&vmi);
if (!vma)
vma = vma_next(&vmi);
return vma;
}旧版实现需要遍历链表找前驱，新版利用游标的 mas_prev() 直接在树中反向遍历，时间复杂度 O(log N)。
以下是 mmap(2) 系统调用路径中 Maple Tree 的参与方式（以匿名私有映射为例）：
sys_mmap()
└─ ksys_mmap_pgoff() [mm/mmap.c:567]
└─ vm_mmap_pgoff()
└─ do_mmap() [mm/mmap.c:335]
├─ __get_unmapped_area() // 使用 mas_empty_area_rev() 利用 arange gap
└─ mmap_region() [mm/vma.c 调用]
├─ vma_iter_init(&vmi, mm, addr)
├─ // 查找重叠 VMA（MAP_FIXED 处理）
├─ // 尝试与相邻 VMA 合并
│ └─ vma_merge_new_range()
│ └─ commit_merge()
│ └─ vma_iter_store_overwrite(&vmi, target)
└─ // 不能合并时创建新 VMA
├─ vm_area_alloc(mm)
├─ vma_iter_config(&vmi, addr, end)
├─ vma_iter_prealloc(&vmi, vma) // 预分配节点
└─ vma_iter_store_new(&vmi, vma) // 写入 mm_mt
generic_get_unmapped_area_topdown() 调用 vm_unmapped_area() → unmapped_area_topdown() → mas_empty_area_rev()，利用 maple_arange_64 节点的 gap[] 数组自顶向下定位满足大小要求的空洞，时间复杂度 O(log N)，而旧版需要线性遍历 VMA 链表。
vma_iter_store_new() 最终调用 mas_store_prealloc() 或 mas_store_gfp() 将 VMA 存入树。由于此时已通过 vma_iter_prealloc() 预分配了节点，写操作不会在持锁期间进行内存分配。
mm/mmap.c 第 124 行的 SYSCALL_DEFINE1(brk, ...) 展示了游标的典型用法：
struct vma_iterator vmi;
// 初始化游标
vma_iter_init(&vmi, mm, newbrk);
// 查找 [newbrk, oldbrk) 范围内的 VMA
brkvma = vma_find(&vmi, oldbrk);
if (!brkvma || brkvma->vm_start >= oldbrk)
goto out;
// 使用 vmi 的位置信息直接执行 munmap，无需再次搜索
do_vmi_align_munmap(&vmi, brkvma, mm, newbrk, oldbrk, &uf, true);游标 vmi 同时传入 do_vmi_align_munmap()，使 munmap 操作可以从 brkvma 位置直接开始，避免重复的树遍历。
定义于 mm/vma.c 第 497–584 行，分裂一个 VMA 为两个相邻的 VMA：
static __must_check int
__split_vma(struct vma_iterator *vmi, struct vm_area_struct *vma,
unsigned long addr, int new_below)
{
struct vma_prepare vp;
struct vm_area_struct *new;
...
new = vm_area_dup(vma);
...
vma_iter_config(vmi, new->vm_start, new->vm_end);
if (vma_iter_prealloc(vmi, new)) // 预分配节点
goto out_free_vma;
...
init_vma_prep(&vp, vma);
vp.insert = new;
vma_prepare(&vp);
...
/* vma_complete 负责更新树 */
vma_complete(&vp, vmi, vma->vm_mm);
...
}vma_complete() 最终调用 vma_iter_store_new(vmi, vp.insert) 将新 VMA 写入 mm_mt，并更新 mm->map_count（mm/vma.c 第 356–358 行）：
vma_iter_store_new(vmi, vp->insert);
mm->map_count++;合并操作由 mm/vma.c 第 805 行的 vma_merge_existing_range() 驱动，最终通过 commit_merge() 更新树（第 728–768 行）：
static int commit_merge(struct vma_merge_struct *vmg)
{
...
vma_iter_config(vmg->vmi, vmg->start, vmg->end);
...
if (vma_iter_prealloc(vmg->vmi, vma)) // 预分配节点
return -ENOMEM;
vma_prepare(&vp);
vma_set_range(vma, vmg->start, vmg->end, vmg->pgoff);
vmg_adjust_set_range(vmg);
vma_iter_store_overwrite(vmg->vmi, vmg->target); // 覆盖写入
vma_complete(&vp, vmg->vmi, vma->vm_mm);
return 0;
}vma_iter_store_overwrite() 区别于 vma_iter_store_new()：前者覆盖已存在的条目，后者插入新条目。两者底层均通过 mas_store() 实现。
场景：prev、middle、next 三者连续且属性兼容时执行 merge_both
Before:
[prev_start .... prev_end][middle_start ... middle_end][next_start ... next_end]
prev middle next
After (commit_merge):
[prev_start ................................................ next_end]
prev（扩展）
（middle 和 next 从树中删除，vm_area_free() 释放）
vma_mark_detached() 用于将被删除的 VMA 从树中标记为分离（设置 vm_refcnt = 0），防止 per-VMA 读锁的 reader 继续使用它。
remove_vma() 定义于 mm/vma.c 第 463–471 行：
void remove_vma(struct vm_area_struct *vma)
{
might_sleep();
vma_close(vma); // 调用 vm_ops->close（如 mmap 的 close 钩子）
if (vma->vm_file)
fput(vma->vm_file); // 释放文件引用
mpol_put(vma_policy(vma));
vm_area_free(vma); // 归还内存
}注意 remove_vma() 本身不从树中删除 VMA——树的更新发生在 vma_complete() 中，即合并/分裂完成时。remove_vma() 仅负责释放 vm_area_struct 结构的资源。
VMA 从 mm_mt 中的移除发生在：
vma_complete()中：当vp->remove非空时，vma_mark_detached(vp->remove)标记分离，vm_area_free()释放（mm/vma.c第 378–403 行）do_vmi_align_munmap()等 munmap 流程中，批量清除树中的范围（vma_iter_clear_gfp()）
validate_mm()（mm/vma.c 第 642–694 行，仅在 CONFIG_DEBUG_VM_MAPLE_TREE 下编译）在每次 VMA 操作后验证树的一致性：
#ifdef CONFIG_DEBUG_VM_MAPLE_TREE
void validate_mm(struct mm_struct *mm)
{
int i = 0;
struct vm_area_struct *vma;
VMA_ITERATOR(vmi, mm, 0);
mt_validate(&mm->mm_mt); // 验证 Maple Tree 内部结构
for_each_vma(vmi, vma) {
unsigned long vmi_start = vma_iter_addr(&vmi);
unsigned long vmi_end = vma_iter_end(&vmi);
// 检查树中存储的范围与 VMA 字段是否一致
VM_WARN_ON_ONCE_MM(vma->vm_end != vmi_end, mm);
VM_WARN_ON_ONCE_MM(vma->vm_start != vmi_start, mm);
...
}
...
}
#endif| 操作 | 旧版（rbtree + 链表） | Maple Tree |
|---|---|---|
| 顺序遍历所有 VMA | O(N) 链表遍历 | O(N) 游标遍历（cache 更友好，B-Tree 局部性） |
| 按地址查找 VMA | O(log N) rbtree | O(log N) Maple Tree |
| 查找下一个 VMA | O(1) 链表 vm_next |
O(log N) 最坏，通常 O(1) 游标缓存 |
| 寻找 N 字节空洞 | O(N log N) 最坏 | O(log N) gap 追踪 |
| 插入/删除 VMA | O(log N) + 链表更新 | O(log N)（单次操作） |
旧版的 rb_subtree_gap 是 rb_node 的一个附加字段，记录子树最大 gap，每次 VMA 变化需要自底向上更新整个路径。
Maple Tree 的 maple_arange_64 将 gap 信息作为节点结构的一等公民（gap[] 数组 + meta.gap 字段），每个内部节点存储所有子节点中最大 gap 的位置，mas_empty_area() / mas_empty_area_rev() 直接从根开始贪心下降。
topdown mmap 的典型改进：对于拥有数千个 VMA 的进程，每次 mmap 调用寻找空闲区的时间从 O(N) 降低到 O(log N)。
fork() 调用 dup_mmap() 需要复制父进程的整个 VMA 树。新版通过 __mt_dup() 直接复制 Maple Tree 结构（lib/maple_tree.c 第 6163+ 行），比逐条重新插入效率更高。
Maple Tree 相比 rbtree + 链表的双结构，减少了 vm_area_struct 的开销：
- 删除了
vm_rb（struct rb_node，24 字节） - 删除了
vm_next/vm_prev（各 8 字节，共 16 字节）
但 maple_arange_64 节点（240 字节）比 rbtree 节点更大，整体是以更大节点换取更少的节点数量（B-Tree 的基本权衡）。
旧版需要同时维护 __vma_link_rb()、__vma_link_list() 两套函数，以及在每次插入/删除后手动调用 vma_gap_update() 更新 gap。Maple Tree 将这些逻辑统一到节点操作中自动维护，大幅减少了代码路径中的一致性维护负担。
Maple Tree 提供了丰富的调试工具（CONFIG_DEBUG_MAPLE_TREE）：
定义于 include/linux/maple_tree.h 第 625–688 行：
// 树级别断言
#define MT_BUG_ON(__tree, __x) do { ... mt_dump(__tree, mt_dump_hex); ... } while (0)
// 状态级别断言
#define MAS_BUG_ON(__mas, __x) do { ... mas_dump(__mas); mt_dump(...); } while (0)
// 写状态级别断言
#define MAS_WR_BUG_ON(__wrmas, __x) do { ... mas_wr_dump(__wrmas); ... } while (0)void mt_dump(const struct maple_tree *mt, enum mt_dump_format format);
void mas_dump(const struct ma_state *mas);
void mas_wr_dump(const struct ma_wr_state *wr_mas);
void mt_validate(struct maple_tree *mt);mt_validate() 全树一致性检查，验证所有节点的 pivot 顺序、gap 值、metadata 正确性。
Maple Tree 内部广泛使用 trace points（trace/events/maple_tree.h），可通过 ftrace 追踪每次读写操作：
trace_ma_read(TP_FCT, &mas); // 读操作
trace_ma_write(TP_FCT, &mas, 0, entry); // 写操作
trace_ma_op(TP_FCT, &mas); // 通用操作maple_tree
├── ma_flags (height | alloc_range | lock_mode | rcu_mode)
└── ma_root (RCU pointer)
│
└── [maple_arange_64 root node] <- 启用 alloc_range 时
├── pivot[0..8] <- 9 个 pivot
├── slot[0..9] <- 10 个子树/叶
├── gap[0..9] <- 每个子树的最大 gap
└── meta.gap <- 最大 gap 在 gap[] 中的索引
│
├── [maple_arange_64 内部节点]
│ └── ...
│
└── [maple_range_64 / maple_leaf_64 叶节点]
├── pivot[0..14] <- 15 个 pivot
├── slot[0..15] <- 16 个 vm_area_struct* 指针
└── meta.end <- 末尾有效槽偏移
+------------------------------- mm_struct --------------------------------+
| struct maple_tree mm_mt; // VMA 地址空间树（替代 mm_rb） |
| struct rw_semaphore mmap_lock; // 外部锁（MT_FLAGS_LOCK_EXTERN） |
| int map_count; // VMA 数量 |
+-------------------------------------------------------------------------+
|
| mm_mt 存储 key=[vm_start, vm_end-1], value=vm_area_struct*
|
+--------v----- maple_tree (mm_mt, MT_FLAGS_ALLOC_RANGE) -----------------+
| |
| arange_64 root |
| +--------+--------+--------+--------+--------+ |
| | gap[0] | gap[1] | gap[2] | gap[3] | gap[4] | <- 每子树最大空洞 |
| | slot[0]| slot[1]| slot[2]| slot[3]| slot[4]| <- 子节点或叶VMA指针 |
| +--------+--------+--------+--------+--------+ |
| | | | |
| [leaf] [leaf] [leaf] <- 叶节点直接存 vm_area_struct* |
| vma1,2,3 vma4,5 vma6,7 |
+-------------------------------------------------------------------------+
VMA 操作路径：
mmap() --[寻找空洞]--> mas_empty_area_rev() 利用 gap[] 快速定位
--[插入VMA]---> mas_store_gfp() 预分配节点+写入
munmap() --> vma_iter_clear_gfp() 清除范围
fork() --> __mt_dup() 复制整树
/proc/pid/maps --> for_each_vma() 游标顺序遍历
MA_STATE(mas, mt, start, end) // 栈上初始化，status=ma_start
|
v
mas_find() / mas_walk()
|
[status: ma_start] ---> 从 ma_root 开始下行搜索
|
[status: ma_active] ---> 游标有效，index/last 对应当前条目范围
|
[可选] mas_pause() ---> [status: ma_pause]，释放锁暂停
| |
| 重新加锁后
| mas_find() 从 last+1 恢复
|
[status: ma_overflow] ---> 超出上界，遍历结束
|
mas_destroy() ---> 归还未使用预分配节点
caller
|
├─ mas_preallocate(mas, entry, GFP_KERNEL)
│ ├─ 分析存储类型 (mas_wr_store_type)
│ ├─ 计算需要节点数 (mas_prealloc_calc -> node_request)
│ └─ 分配节点 (mas_alloc_nodes)
│ ├─ node_request==1 -> mt_alloc_one() -> mas->alloc
│ └─ node_request>1 -> kmem_cache_prefill_sheaf() -> mas->sheaf
│
├─ <acquire lock>
│
├─ mas_store_prealloc(mas, entry) // 使用预分配节点，不分配
│ └─ mas_wr_store_entry()
│ └─ 根据 store_type 执行对应路径
│ wr_exact_fit -> 直接替换 slot
│ wr_slot_store -> 更新 slot + pivot
│ wr_split_store -> 分裂节点（消耗预分配节点）
│ wr_spanning_store -> 跨节点覆盖（最复杂）
│
├─ <release lock>
│
└─ mas_destroy(mas) // 归还剩余节点到 slab sheaf
Linux 内核 VMA 管理的数据结构经历了漫长的演进：
2.4 时代
└─ 单链表（vm_next）：简单但 O(N) 查找
|
2.4.7（约 2001 年）
└─ 引入 rbtree + 链表双结构
|
5.14（2021 年）
└─ 性能基准测试揭示高 VMA 数量下的严重瓶颈
|
6.1-rc1（2022 年 10 月）
└─ Maple Tree 首次合并进主线（commit: d3c4a19）
替换 mm_struct.mm_rb + vm_next/vm_prev
|
6.1（2022 年 12 月正式发布）
└─ Maple Tree 成为 VMA 管理的唯一数据结构
在 6.1 合并前，Oracle 团队进行了大量性能评测，主要场景如下：
场景一：高 VMA 数量的服务端进程
现代 Java 应用（如 JVM）可能有数万个 VMA（每个 class 文件对应一个 mmap 区域），每次 mmap 调用需要遍历链表寻找空洞，随 VMA 数量增加而线性退化。
场景二：/proc/PID/smaps 读取
smaps 需要遍历所有 VMA 并统计每个 VMA 的物理内存用量，旧版的链表遍历虽然是 O(N)，但 cache 局部性差（链表节点分散在堆上）；Maple Tree 的 B-Tree 结构使相邻 VMA 的槽在同一缓存行上。
场景三：mprotect 批量操作
mprotect 需要对一个地址范围内的所有 VMA 修改权限标志，旧版需要先 find_vma 定位，再沿链表前进，还要维护 rbtree gap 信息。新版通过 for_each_vma_range 游标遍历，单次操作即可完成。
迁移过程中，以下字段从 vm_area_struct 中移除（见相关提交信息）：
| 移除字段 | 字节数 | 说明 |
|---|---|---|
vm_rb (struct rb_node) |
24 | rbtree 节点，红黑树用 |
vm_next |
8 | 链表前向指针 |
vm_prev |
8 | 链表后向指针 |
rb_subtree_gap |
8 | rbtree 子树 gap，现由 arange_64 维护 |
共节省每个 vm_area_struct 约 48 字节，对于拥有数万 VMA 的进程有数 MB 的内存节省。
迁移并非完全无痛，为了兼容性保留了部分接口：
find_vma()保留原有签名，内部实现从 rbtree 改为mt_find()（mm/mmap.c:883）/proc/PID/maps遍历接口保持不变，底层改为vma_next()游标madvise、mprotect、munmap等系统调用的外部接口完全不变
mt_find() 是 VMA 查找的核心低层函数（lib/maple_tree.c:6482）：
void *mt_find(struct maple_tree *mt, unsigned long *index, unsigned long max)
{
MA_STATE(mas, mt, *index, *index);
void *entry;
trace_ma_read(TP_FCT, &mas);
if ((*index) > max)
return NULL;
rcu_read_lock();
retry:
entry = mas_state_walk(&mas);
if (mas_is_start(&mas))
goto retry; // dead node 触发重试
if (unlikely(xa_is_zero(entry)))
entry = NULL;
if (entry)
goto unlock;
while (mas_is_active(&mas) && (mas.last < max)) {
entry = mas_next_slot(&mas, max, false); // 向后扫描直到找到非空槽
if (likely(entry && !xa_is_zero(entry)))
break;
}
...
unlock:
rcu_read_unlock();
if (likely(entry)) {
*index = mas.last + 1; // 更新 index 到下一位置（游标语义）
}
return entry;
}关键点：
rcu_read_lock()保护整个查找过程，不持任何睡眠锁mas_is_start()检测 dead node 重试（对应smp_rmb()+ parent self-check）*index在找到条目后更新为mas.last + 1，这是游标语义——调用者下次从这里开始
以一次 VMA 插入为例（mm/vma.c 中的 __mmap_new_vma() 路径）：
vma_iter_prealloc(vmi, vma)
└─ mas_preallocate(&vmi->mas, vma, GFP_KERNEL)
├─ [无锁] 分析写入类型（通过 mas_wr_prealloc_setup + mas_wr_store_type）
├─ [无锁] 计算 node_request（最多 3 个新节点：叶+父+祖父）
└─ [无锁] kmem_cache_alloc / prefill_sheaf
（此时已持 mmap_lock 写锁，但不持 ma_lock；
因为 mm_mt 使用外部锁，ma_lock 无效）
vma_iter_store_new(vmi, vma)
└─ mas_store_prealloc(&vmi->mas, vma)
├─ 使用已预分配的节点
├─ 根据 store_type 执行写入
├─ 若 wr_split_store：分裂当前节点（消耗 1 个预分配节点）
├─ 若父节点也满：向上传播分裂（消耗更多预分配节点）
└─ 更新所有祖先节点的 gap[] 值（arange_64 特有）
mas_destroy(&vmi->mas) // 归还未使用节点
mtree_erase() 的实现（lib/maple_tree.c:6148）：
void *mtree_erase(struct maple_tree *mt, unsigned long index)
{
void *entry = NULL;
MA_STATE(mas, mt, index, index);
trace_ma_op(TP_FCT, &mas);
mtree_lock(mt);
entry = mas_erase(&mas); // 等价于 mas_store(mas, NULL)
mtree_unlock(mt);
return entry;
}源码注释（lib/maple_tree.c:6140）说明：
Erasing is the same as a walk to an entry then a store of a NULL to that ENTIRE range. In fact, it is implemented as such using the advanced API.
即 erase 等价于将整个区间存储为 NULL。这统一了插入和删除的语义——都是 range store，只是值不同（有效指针 vs NULL）。
这两个函数是 mmap 地址分配的关键（lib/maple_tree.c:4727 和 lib/maple_tree.c:4788）：
mas_empty_area()（低地址优先）：
1. mas_start(mas) -- 从根开始
2. mas_awalk(mas, size)
└─ 遍历 arange_64 节点
├─ 检查 gap[i] >= size 且区间与 [min, max] 有交集
├─ 找到后 mas_descend() 进入该子树
└─ 到叶节点时定位具体空槽
3. 更新 mas->index = 满足条件的起始地址
4. 更新 mas->last = mas->index + size - 1
mas_empty_area_rev()（高地址优先，topdown mmap 使用）：
1. mas_start(mas) -- 从根开始
2. while (!mas_rev_awalk(mas, size, &min, &max))
└─ mas_rewind_node(mas) -- 向左移动节点
3. 从高地址端裁剪结果
4. 更新 mas->index = mas->last - size + 1
高地址优先搜索对应 Linux 默认的 mmap_base 方向（arch_get_mmap_base() 返回用户空间高端地址），这使得堆（向上增长）和 mmap 区域（向下分配）之间的冲突概率最小。
当叶节点的 slot 数量达到 mt_slots[type] 时触发分裂（wr_split_store 路径）。分裂过程保证 B-Tree 平衡性：
分裂前（叶节点满，16 个 slot）：
[p0][p1][p2]...[p14]
[s0][s1][s2]...[s14][s15]
分裂后（两个新节点，各约 8 个 slot）：
新左节点：[p0]..[p6] | 新右节点：[p8]..[p14]
[s0]..[s7] | [s8]..[s15]
父节点新增一个 pivot（p7）指向分裂点，
父节点的两个相邻 slot 分别指向新左/右节点
若父节点也满，则递归向上分裂，直到根节点——根节点分裂时树高增加 1（新分配一个根节点，原根变为子节点）。
Maple Tree 的写操作遵循 RCU 的核心原则：写者从不原地修改正在被读者访问的节点，而是复制-修改-替换（Copy-Modify-Publish）。
写者流程（持有 mmap_lock 写锁）：
读者线程 写者线程
| |
rcu_read_lock() mmap_write_lock(mm)
| |
读取 node_A 分配 node_A_new（复制自 node_A）
| |
访问 slot[3] = vma_X 修改 node_A_new->slot[3] = vma_Y
| |
（仍在用 node_A） rcu_assign_pointer(parent->slot[i],
| node_A_new) // 原子替换
| |
（继续用 node_A） mte_set_node_dead(node_A)
| | // 置 node_A->parent = node_A
检查 ma_dead_node(node_A) mmap_write_unlock(mm)
| // 返回 true |
重试（ma_start） 等待 RCU grace period
|
rcu_read_unlock()
kfree_rcu(node_A, rcu) // 安全释放
Maple Tree 使用以下内存屏障保证 RCU 安全性：
写者侧（mte_set_node_dead()，lib/maple_tree.c:332）：
mte_to_node(mn)->parent = ma_parent_ptr(mte_to_node(mn));
smp_wmb(); // 确保 dead 标记在节点内容修改之后可见读者侧（ma_dead_node()，lib/maple_tree.c:566）：
smp_rmb(); // 确保 parent 检查在读取节点数据之前完成
parent = (void *)((unsigned long) node->parent & ~MAPLE_NODE_MASK);
return (parent == node);smp_wmb() 和 smp_rmb() 的配对保证了：读者要么看到旧节点的完整数据（parent 未改变），要么看到 dead 标记（parent == self），不会看到中间状态。
在无锁读路径中，读取子节点指针必须使用 mt_slot()（内部调用 rcu_dereference()）：
// 正确方式（来自 lib/maple_tree.c 内部实现）
entry = mt_slot(mas->tree, slots, offset);
// 等价于：
// entry = rcu_dereference(*xa_mk_node(slots + offset));直接读取 slots[i] 而不经过 rcu_dereference() 可能在弱内存序架构（ARM64、POWER）上导致读到过期的指针值。
操作类型 需要的锁
------------------------------------------
只读 VMA 属性 rcu_read_lock() 或 per-VMA 读锁
查找 VMA（find_vma） mmap_read_lock() 或 rcu_read_lock()
修改 VMA 属性 mmap_write_lock()
插入/删除 VMA mmap_write_lock()
/proc/PID/maps 遍历 per-VMA 读锁（CONFIG_PER_VMA_LOCK 时）
或 mmap_read_lock()（无 per-VMA 锁时）
vma_lookup() 直接调用 mtree_load()，后者内部持 rcu_read_lock()，因此不需要调用者持任何锁——只要 VMA 不被释放（由 per-VMA 引用计数保证）即可安全访问返回的 VMA 指针。
struct vm_area_struct 定义于 include/linux/mm_types.h:913，是 Linux 虚拟内存管理的核心结构。
struct vm_area_struct {
union {
struct {
unsigned long vm_start; // VMA 起始虚拟地址（含）
unsigned long vm_end; // VMA 结束虚拟地址（不含）
};
freeptr_t vm_freeptr; // SLAB_TYPESAFE_BY_RCU 使用的空闲指针
};
struct mm_struct *vm_mm; // 所属进程的 mm_struct
pgprot_t vm_page_prot; // 页表项保护位（从 vm_flags 派生）
...vm_start 和 vm_end 确定了 VMA 在虚拟地址空间中的位置，作为区间 [vm_start, vm_end - 1] 存入 mm_mt。vm_end - vm_start 必须是 PAGE_SIZE 的整数倍。
union {
const vm_flags_t vm_flags; // VMA 标志（VM_READ/WRITE/EXEC 等）
vma_flags_t flags; // 内部标志位图类型（转换过渡期）
};vm_flags 是 VMA 的核心控制字段，详细分析见第 23 章。
#ifdef CONFIG_PER_VMA_LOCK
unsigned int vm_lock_seq; // 写锁序列号（与 mm->mm_lock_seq 比较）
refcount_t vm_refcnt; // VMA 引用计数（见 mm_types.h:993 的详细注释）
#endifvm_refcnt 的语义（include/linux/mm_types.h:993）：
vm_refcnt 值 含义
-------------------------------------------------------
0 VMA 已分离（detached），读者不能再增加引用
1 已附加（attached），未读锁或写锁状态
>1, <EXCL_FLAG 已附加，有读者持有读锁
EXCL_FLAG 待分离，等待 __vma_end_exclude_readers()
EXCL_FLAG+1 写锁获取中（或分离中，有孤立读者）
>EXCL_FLAG+1 写锁/分离中，等待多个读者退出
unsigned long vm_pgoff; // 文件内偏移（单位：页帧，PAGE_SIZE）
struct file *vm_file; // 文件指针（匿名映射为 NULL）
void *vm_private_data; // 驱动私有数据（如 DMA 缓冲区描述符）对于文件映射，vm_pgoff 和 vm_file 共同决定了 VMA 映射到文件的哪个部分。合并检查时必须验证相邻 VMA 的 vm_file 相同且 vm_pgoff 连续（can_vma_merge_before() / can_vma_merge_after()）。
struct list_head anon_vma_chain; // anon_vma 链表头（page_table_lock 保护）
struct anon_vma *anon_vma; // 匿名 VMA 的 anon_vma（page_table_lock 保护）
struct {
struct rb_node rb; // i_mmap 区间树节点（文件反向映射）
unsigned long rb_subtree_last;
} shared;anon_vma 用于在物理页面 fault 时反向查找哪些进程映射了该物理页（COW 场景）。shared.rb 用于文件的 address_space->i_mmap 区间树（与 mm_mt 无关，是另一套独立的数据结构）。
const struct vm_operations_struct *vm_ops;定义于 include/linux/mm.h:749，包含一系列回调函数：
| 回调 | 触发时机 | 典型用途 |
|---|---|---|
open |
VMA 被复制（fork）或 mremap 时 | 增加文件引用 |
close |
VMA 被移除时 | 释放驱动资源 |
may_split |
分裂前检查 | 驱动不允许分裂时返回 -EINVAL |
fault |
缺页异常时 | 将文件内容映射到物理页 |
huge_fault |
大页缺页时 | THP 处理 |
page_mkwrite |
COW 后首次写时 | 通知文件系统标记脏页 |
name |
/proc/PID/maps 输出时 |
返回 VMA 的显示名称 |
注意：vm_ops->close 的存在会阻止 VMA 在合并时被移除（can_merge_remove_vma() 检查），因为 close 钩子必须在 VMA 生命周期结束时正确调用。
vm_flags 是一个位图，定义于 include/linux/mm.h:402。每个标志通过 INIT_VM_FLAG(name) 宏定义为 BIT(VMA_##name##_BIT)。
// include/linux/mm.h:402-408
#define VM_READ INIT_VM_FLAG(READ) // 用户可读
#define VM_WRITE INIT_VM_FLAG(WRITE) // 用户可写
#define VM_EXEC INIT_VM_FLAG(EXEC) // 用户可执行
#define VM_SHARED INIT_VM_FLAG(SHARED) // 共享映射（对应 MAP_SHARED）这四个标志直接对应 mmap(2) 的 prot 参数（PROT_READ/WRITE/EXEC）和 flags 参数（MAP_SHARED/MAP_PRIVATE）。
在 /proc/PID/maps 的 rwxs 字段中（fs/proc/task_mmu.c:451-454）：
seq_putc(m, flags & VM_READ ? 'r' : '-');
seq_putc(m, flags & VM_WRITE ? 'w' : '-');
seq_putc(m, flags & VM_EXEC ? 'x' : '-');
seq_putc(m, flags & VM_MAYSHARE ? 's' : 'p'); // 注意用 VM_MAYSHARE 而非 VM_SHARED#define VM_MAYREAD INIT_VM_FLAG(MAYREAD) // 允许将来设置 VM_READ
#define VM_MAYWRITE INIT_VM_FLAG(MAYWRITE) // 允许将来设置 VM_WRITE
#define VM_MAYEXEC INIT_VM_FLAG(MAYEXEC) // 允许将来设置 VM_EXEC
#define VM_MAYSHARE INIT_VM_FLAG(MAYSHARE) // 允许将来设置 VM_SHAREDMAY* 标志与 mprotect(2) 相关：mprotect 只能在对应 MAY* 标志已置位的情况下升级权限。例如 MAP_PRIVATE 文件映射的 VM_MAYWRITE 被清除后，mprotect 无法重新添加写权限。
在 do_mmap() 中（mm/mmap.c:401-402）：
vm_flags |= calc_vm_prot_bits(prot, pkey) | calc_vm_flag_bits(file, flags) |
mm->def_flags | VM_MAYREAD | VM_MAYWRITE | VM_MAYEXEC;VM_MAYREAD/MAYWRITE/MAYEXEC 默认总是设置，除非文件系统的 noexec 挂载选项清除了 VM_MAYEXEC（mm/mmap.c:472-473）。
#define VM_GROWSDOWN INIT_VM_FLAG(GROWSDOWN) // 栈向下增长（x86/arm 等）
#ifdef CONFIG_STACK_GROWSUP
#define VM_STACK INIT_VM_FLAG(STACK) // = VM_GROWSUP（PA-RISC 等）
#else
#define VM_STACK INIT_VM_FLAG(STACK) // = VM_GROWSDOWN（绝大多数架构）
#endif栈 VMA 设置 VM_STACK | VM_GROWSDOWN，使缺页处理程序知道该 VMA 可以自动向下扩展（expand_stack() 函数）。
#define VM_LOCKED INIT_VM_FLAG(LOCKED) // mlock() 锁定，不可换出
#define VM_LOCKONFAULT INIT_VM_FLAG(LOCKONFAULT) // mlock(MLOCK_ONFAULT)，缺页时锁定VM_LOCKED_MASK = VM_LOCKED | VM_LOCKONFAULT（include/linux/mm.h:575）。
do_mmap() 在设置 MAP_LOCKED 时检查 mlock_future_ok()（mm/mmap.c:420），确保不超过 RLIMIT_MEMLOCK 限制。
// include/linux/mm.h:550
#define VM_SPECIAL (VM_IO | VM_DONTEXPAND | VM_PFNMAP | VM_MIXEDMAP)设置了任意一个 VM_SPECIAL 位的 VMA 不能参与合并（vma_merge_existing_range() 第 847 行检查）：
if (vmg->vm_flags & VM_SPECIAL || (!left_side && !right_side))
return NULL;各标志含义：
| 标志 | 含义 | 典型场景 |
|---|---|---|
VM_IO |
映射 I/O 内存，访问有副作用 | /dev/mem 映射、PCIe BAR |
VM_DONTEXPAND |
禁止 mremap 扩展 | 某些驱动映射 |
VM_PFNMAP |
纯 PFN 映射，页帧无 struct page |
DMA 一致性内存、RDMA |
VM_MIXEDMAP |
混合普通页和 PFN 映射 | /dev/zero + dax |
// include/linux/mm.h:611
#define VM_IGNORE_MERGE VM_STICKYVM_STICKY 是一种特殊情况：合并时，若两个 VMA 只有 sticky 标志不同，仍然允许合并，但合并结果会保留两者的 sticky 标志（取 OR）。
这在 is_mergeable_vma() 中实现（mm/vma.c:92）：
if ((vma->vm_flags ^ vmg->vm_flags) & ~VM_IGNORE_MERGE)
return false; // 只有非 sticky 标志不同才拒绝合并#define VM_DONTCOPY INIT_VM_FLAG(DONTCOPY) // fork 时不复制（不出现在子进程）
#define VM_DONTDUMP INIT_VM_FLAG(DONTDUMP) // 不出现在 core dump
#define VM_WIPEONFORK INIT_VM_FLAG(WIPEONFORK) // fork 后子进程中内容清零
#define VM_NORESERVE INIT_VM_FLAG(NORESERVE) // 不预留 swap 空间（过提交）
#define VM_ACCOUNT INIT_VM_FLAG(ACCOUNT) // 计入 overcommit 统计
#define VM_HUGETLB INIT_VM_FLAG(HUGETLB) // 大页映射
#define VM_HUGEPAGE INIT_VM_FLAG(HUGEPAGE) // 建议使用 THP
#define VM_NOHUGEPAGE INIT_VM_FLAG(NOHUGEPAGE) // 禁止 THP
#define VM_MERGEABLE INIT_VM_FLAG(MERGEABLE) // 允许 KSM 扫描
#define VM_SEALED INIT_VM_FLAG(SEALED) // 已密封（memfd_seal）
#define VM_DROPPABLE INIT_VM_FLAG(DROPPABLE) // 可随时被丢弃（MAP_DROPPABLE）VM_DROPPABLE 是较新引入的标志，对应 MAP_DROPPABLE（mm/mmap.c:504），其语义是页面可被内核在内存压力下随时丢弃（不写回），适用于可重建的临时缓冲区。
do_mmap() 是 mmap 的核心函数（mm/mmap.c:335），负责参数验证和 vm_flags 计算：
sys_mmap_pgoff()
└─ ksys_mmap_pgoff() [mm/mmap.c:567]
├─ fget(fd) // 获取文件对象（文件映射时）
└─ vm_mmap_pgoff()
├─ security_mmap_file() // LSM 安全检查
├─ mmap_write_lock(mm) // 获取 mmap_lock 写锁
└─ do_mmap() [mm/mmap.c:335]
├─ 1. 参数校验
│ ├─ len = PAGE_ALIGN(len)
│ ├─ pgoff 溢出检查
│ └─ map_count > sysctl_max_map_count? -> ENOMEM
├─ 2. prot -> vm_flags 转换
│ ├─ calc_vm_prot_bits(prot, pkey)
│ ├─ calc_vm_flag_bits(file, flags)
│ └─ mm->def_flags | VM_MAYREAD | VM_MAYWRITE | VM_MAYEXEC
├─ 3. 文件/匿名映射特定处理
│ ├─ MAP_SHARED -> VM_SHARED | VM_MAYSHARE
│ ├─ MAP_PRIVATE -> pgoff = addr >> PAGE_SHIFT（匿名时）
│ └─ MAP_DROPPABLE -> VM_DROPPABLE | VM_NORESERVE | VM_WIPEONFORK | VM_DONTDUMP
├─ 4. 地址分配
│ └─ __get_unmapped_area() -> mas_empty_area_rev()
├─ 5. MAP_FIXED_NOREPLACE 冲突检查
│ └─ find_vma_intersection()
└─ 6. mmap_region()
└─ __mmap_region() [mm/vma.c:2720]
mm/vma.c:2720 的 __mmap_region() 是实际分配 VMA 的位置：
static unsigned long __mmap_region(...)
{
VMA_ITERATOR(vmi, mm, addr); // 初始化游标
MMAP_STATE(map, mm, &vmi, ...); // 初始化 mmap 状态机
// 1. 设置 mmap 准备阶段（含 munmap 可能的重叠 VMA）
error = __mmap_setup(&map, &desc, uf);
// 2. 调用文件驱动的 mmap_prepare()（新 API）
if (have_mmap_prepare)
error = call_mmap_prepare(&map, &desc);
// 3. 尝试与相邻 VMA 合并
if (map.prev || map.next) {
VMG_MMAP_STATE(vmg, &map, NULL);
vma = vma_merge_new_range(&vmg); // 成功则扩展现有 VMA
}
// 4. 合并失败，分配新 VMA
if (!vma) {
error = __mmap_new_vma(&map, &vma);
// 内部：vm_area_alloc() + vma_iter_prealloc() + vma_iter_store_new()
}
// 5. 完成映射（调用 vm_ops->mmap()、通知 khugepaged 等）
__mmap_complete(&map, vma);
return addr;
}sys_munmap(addr, len)
└─ __vm_munmap()
├─ mmap_write_lock(mm)
└─ do_vmi_munmap() [mm/vma.c]
└─ do_vmi_align_munmap()
├─ 1. 初始化游标 vmi 到 addr
├─ 2. vma_find() 定位第一个重叠 VMA
├─ 3. 处理起始部分分裂（若 addr > vma->vm_start）
│ └─ __split_vma(vmi, vma, addr, 1)
├─ 4. 遍历并收集所有待删除 VMA
│ └─ for_each_vma_range(vmi, vma, end)
│ └─ vma_mark_detached(vma)
│ vma_iter_clear() // 从 mm_mt 中清除
├─ 5. 处理末尾部分分裂（若 end < vma->vm_end）
│ └─ __split_vma(vmi, vma, end, 0)
├─ 6. unmap_region() — 解除物理页面映射
│ ├─ unmap_vmas() // 清除页表项 + TLB flush
│ └─ free_pgtables() // 释放页表页
└─ 7. remove_vma_list() — 释放 vm_area_struct 对象
└─ for each detached VMA:
remove_vma(vma)
└─ vm_area_free(vma)
mprotect(2) 需要修改一个地址范围的权限，可能导致 VMA 分裂和合并：
sys_mprotect(addr, len, prot)
└─ do_mprotect_pkey()
├─ mmap_write_lock(mm)
├─ VMA_ITERATOR(vmi, mm, addr)
├─ for_each_vma_range(vmi, vma, end)
│ ├─ 若 addr > vma->vm_start: __split_vma()（头部分裂）
│ ├─ 若 end < vma->vm_end: __split_vma()（尾部分裂）
│ └─ mprotect_fixup()
│ ├─ 计算新 vm_flags
│ ├─ vma_merge_existing_range() // 尝试与相邻 VMA 合并
│ └─ change_protection() // 更新页表保护位
└─ mmap_write_unlock(mm)
此流程中，Maple Tree 游标 vmi 贯穿整个操作，避免了多次重新搜索。
VMA 合并（vma_merge_new_range() 和 vma_merge_existing_range()）需要满足一系列条件。mm/vma.c:86 中 is_mergeable_vma() 检查基础合并条件：
static inline bool is_mergeable_vma(struct vma_merge_struct *vmg, bool merge_next)
{
struct vm_area_struct *vma = merge_next ? vmg->next : vmg->prev;
// 1. NUMA 策略必须相同
if (!mpol_equal(vmg->policy, vma_policy(vma)))
return false;
// 2. vm_flags 必须相同（忽略 VM_IGNORE_MERGE/VM_STICKY 位）
if ((vma->vm_flags ^ vmg->vm_flags) & ~VM_IGNORE_MERGE)
return false;
// 3. 映射文件必须相同（均为 NULL 或同一文件）
if (vma->vm_file != vmg->file)
return false;
// 4. userfaultfd 上下文必须相同
if (!is_mergeable_vm_userfaultfd_ctx(vma, vmg->uffd_ctx))
return false;
// 5. 匿名 VMA 名称必须相同（CONFIG_ANON_VMA_NAME）
if (!anon_vma_name_eq(anon_vma_name(vma), vmg->anon_name))
return false;
return true;
}检查新区域是否可以并入 vmg->next 的前端（mm/vma.c:195）：
static bool can_vma_merge_before(struct vma_merge_struct *vmg)
{
pgoff_t pglen = PHYS_PFN(vmg->end - vmg->start);
if (is_mergeable_vma(vmg, /* merge_next = */ true) &&
is_mergeable_anon_vma(vmg, /* merge_next = */ true)) {
// 文件偏移必须连续
if (vmg->next->vm_pgoff == vmg->pgoff + pglen)
return true;
}
return false;
}检查新区域是否可以接在 vmg->prev 的后端（mm/vma.c:217）：
static bool can_vma_merge_after(struct vma_merge_struct *vmg)
{
if (is_mergeable_vma(vmg, /* merge_next = */ false) &&
is_mergeable_anon_vma(vmg, /* merge_next = */ false)) {
// 文件偏移必须连续：prev 的末尾 pgoff 等于新区域的起始 pgoff
if (vmg->prev->vm_pgoff + vma_pages(vmg->prev) == vmg->pgoff)
return true;
}
return false;
}当双侧合并时（prev + new + next），还需要检查 prev 和 next 的 anon_vma 兼容性（mm/vma.c:436）：
static bool can_vma_merge_right(struct vma_merge_struct *vmg,
bool can_merge_left)
{
...
if (!can_merge_left)
return true; // 单侧合并，无需检查 prev/next 兼容性
// 双侧合并：额外检查 prev 和 next 的 anon_vma 是否兼容
prev = vmg->prev;
return !prev->anon_vma || !next->anon_vma ||
prev->anon_vma == next->anon_vma; // 必须使用同一个 anon_vma
}当合并导致某个 VMA 被删除时，该 VMA 不能有 vm_ops->close（mm/vma.c:771）：
static bool can_merge_remove_vma(struct vm_area_struct *vma)
{
return !vma->vm_ops || !vma->vm_ops->close;
}原因：close 回调负责清理驱动资源，若合并时直接删除 VMA 而跳过 close，会导致资源泄露。因此设有 close 的 VMA（如设备驱动 mmap）不会被合并删除。
场景 操作
----------------------------------------------
new | prev 且可合并 扩展 prev 的右边界
new | next 且可合并 缩小 next 的左边界（扩展 next）
prev | new | next 扩展 prev，删除 next（merge_both）
均不可合并 插入新的 vm_area_struct
vma_merge_new_range() 的判断流程（mm/vma.c:1046）：
can_merge_left = can_vma_merge_left(vmg); // 是否可与 prev 合并
can_merge_right = can_vma_merge_right(vmg, can_merge_left); // 是否可与 next 合并
if (can_merge_right) vmg->end = next->vm_end; // 扩展到 next 的末尾
if (can_merge_left) vmg->start = prev->vm_start; // 扩展到 prev 的起始
// 调用 vma_expand() 执行实际合并
if (vmg->target && !vma_expand(vmg)) { ... }定义于 include/linux/fs.h:470：
struct address_space {
struct inode *host; // 所属 inode
struct xarray i_pages; // 页面缓存（基数树后继）
struct rw_semaphore invalidate_lock; // 页面缓存一致性锁
gfp_t gfp_mask; // 页面分配标志
atomic_t i_mmap_writable; // 可写共享映射计数
struct rb_root_cached i_mmap; // 所有映射此文件的 VMA（区间树）
unsigned long nrpages; // 页面缓存数量
const struct address_space_operations *a_ops; // 操作函数表
struct rw_semaphore i_mmap_rwsem; // 保护 i_mmap 和 i_mmap_writable
...
};这是容易混淆的两套独立数据结构：
文件（inode）
└─ address_space
└─ i_mmap（rb_root_cached）
├─ VMA_A（进程1 映射该文件的某段）
│ shared.rb 节点
├─ VMA_B（进程2 映射该文件的某段）
│ shared.rb 节点
└─ VMA_C（进程1 映射该文件的另一段）
shared.rb 节点
进程1（mm_struct）
└─ mm_mt（maple_tree）
├─ VMA_A（地址范围 [0x7f000, 0x7f100)）
└─ VMA_C（地址范围 [0x7f200, 0x7f300)）
进程2（mm_struct）
└─ mm_mt（maple_tree）
└─ VMA_B（地址范围 [0x8a000, 0x8a200)）
mm_mt 按虚拟地址索引，用于进程内的 VMA 查找。i_mmap 按文件偏移索引，用于文件到所有映射 VMA 的反向查找（rmap），在页面回收、文件 truncate 时使用。
文件 VMA 插入时，vma_complete() -> vma_prepare() -> __vma_link_file() 将 VMA 插入 i_mmap（mm/vma.c:227）：
static void __vma_link_file(struct vm_area_struct *vma,
struct address_space *mapping)
{
if (vma_is_shared_maywrite(vma))
mapping_allow_writable(mapping); // 增加 i_mmap_writable 计数
flush_dcache_mmap_lock(mapping);
vma_interval_tree_insert(vma, &mapping->i_mmap); // 插入区间树
flush_dcache_mmap_unlock(mapping);
}当文件被 truncate 缩短时，内核需要找到所有映射了被截断范围的 VMA 并解除映射。这通过 unmap_mapping_range() 遍历 i_mmap 实现，不通过 mm_mt：
// mm/memory.c 中
void unmap_mapping_range(struct address_space *mapping,
loff_t const holebegin, loff_t const holelen, int even_cows)
{
// 遍历 mapping->i_mmap 中所有与 [holebegin, holebegin+holelen) 相交的 VMA
vma_interval_tree_foreach(vma, &mapping->i_mmap, hba, hba + hlen - 1) {
unmap_mapping_range_vma(vma, start, end, &details);
}
}匿名 VMA（无文件）使用另一套反向映射机制 anon_vma：
匿名 VMA（vm_file == NULL）
└─ vma->anon_vma（struct anon_vma*）
└─ anon_vma->rb_root（rb_root_cached）
├─ 父进程的 VMA（COW 前原始 VMA）
├─ 子进程 fork 后的 VMA（COW 候选）
└─ ...
anon_vma 允许在物理页面被多个进程共享（COW 前）时，通过物理页面的 page->mapping 反向找到所有映射了该页的 VMA，从而完成页面回收或页面移动操作。
/proc/PID/maps 通过 proc_base_stuff[] 表注册（fs/proc/base.c），对应 proc_pid_maps_operations（fs/proc/task_mmu.c:832）：
const struct file_operations proc_pid_maps_operations = {
.open = pid_maps_open,
.read = seq_read,
.llseek = seq_lseek,
.release = proc_map_release,
};/proc/PID/maps 使用 seq_file 框架（fs/proc/task_mmu.c:505）：
static const struct seq_operations proc_pid_maps_op = {
.start = m_start, // 获取第一个 VMA
.next = m_next, // 移动到下一个 VMA
.stop = m_stop, // 释放锁
.show = show_map // 输出一个 VMA 的文本表示
};m_start() 定义于 fs/proc/task_mmu.c:275：
static void *m_start(struct seq_file *m, loff_t *ppos)
{
struct proc_maps_private *priv = m->private;
loff_t last_addr = *ppos;
struct mm_struct *mm;
priv->task = get_proc_task(priv->inode);
...
mm = lock_ctx->mm;
mmget_not_zero(mm);
// 加锁（maps 只需 per-VMA 锁，smaps 需要 mmap_read_lock）
lock_vma_range(m, lock_ctx);
// 初始化游标到上次读取位置（支持 lseek 和分页读取）
vma_iter_init(&priv->iter, mm, (unsigned long)last_addr);
return proc_get_vma(m, ppos);
}fs/proc/task_mmu.c:151 展示了 maps 与 smaps 的锁策略区别：
static inline bool lock_vma_range(struct seq_file *m,
struct proc_maps_locking_ctx *lock_ctx)
{
// smaps 需要做页表遍历（pagewalk），必须持 mmap_read_lock
if (m->op != &proc_pid_maps_op) {
if (mmap_read_lock_killable(lock_ctx->mm))
return false;
lock_ctx->mmap_locked = true;
} else {
// maps 只读取 VMA 属性，使用 per-VMA 锁 + RCU 即可
rcu_read_lock();
reset_lock_ctx(lock_ctx);
}
return true;
}/proc/PID/maps 采用 RCU + per-VMA 读锁策略：
- 通过
vma_next(&priv->iter)推进游标（底层mas_find()，RCU 保护） - 通过
vma_start_read(vma)获取 per-VMA 读锁，锁定单个 VMA 的访问
这比持 mmap_read_lock 的代价更低，减少了对写者的阻塞。
fs/proc/task_mmu.c:463 展示了如何将 VMA 信息格式化为 /proc/PID/maps 的一行：
static void show_map_vma(struct seq_file *m, struct vm_area_struct *vma)
{
vm_flags_t flags = vma->vm_flags;
unsigned long ino = 0;
unsigned long long pgoff = 0;
dev_t dev = 0;
if (vma->vm_file) {
const struct inode *inode = file_user_inode(vma->vm_file);
dev = inode->i_sb->s_dev;
ino = inode->i_ino;
pgoff = ((loff_t)vma->vm_pgoff) << PAGE_SHIFT; // 字节偏移
}
// 输出：地址范围 + 权限标志 + 偏移 + 设备号 + inode + 名称
show_vma_header_prefix(m, vma->vm_start, vma->vm_end,
flags, pgoff, dev, ino);
get_vma_name(vma, &path, &name, &name_fmt);
// 输出文件路径 或 [heap]/[stack]/[vvar] 等特殊标记
...
seq_putc(m, '\n');
}一行 /proc/PID/maps 输出格式（show_vma_header_prefix()，fs/proc/task_mmu.c:442）：
地址范围 权限 偏移 设备号 inode 映射名称
7f0000000000-7f0001000000 r-xp 00000000 fd:01 1234567 /usr/lib/libc.so.6
^^^^
r: VM_READ
w: VM_WRITE
x: VM_EXEC
p/s: VM_MAYSHARE（p=私有, s=共享）
注意权限字段的第 4 列使用 VM_MAYSHARE 而非 VM_SHARED（fs/proc/task_mmu.c:454）：
seq_putc(m, flags & VM_MAYSHARE ? 's' : 'p');这是因为 MAP_PRIVATE 的文件映射在 COW 后 VM_SHARED 被清除，但 VM_MAYSHARE 仍然保留，用于正确反映原始映射类型。
get_vma_name() 函数（fs/proc/task_mmu.c:381）处理特殊 VMA 的名称：
VMA 类型 maps 中的名称
---------------------------------------------
匿名映射（无名） （空）
堆（brk 区域） [heap]
主线程栈 [stack]
vsyscall [vsyscall]
vvar（内核变量） [vvar]
vdso（虚拟 DSO） [vdso]
匿名命名映射（prctl 设置） [anon:名称]
文件映射 文件路径（/usr/lib/...）
传统上，访问任何 VMA 都需要持 mmap_lock 读锁。在多线程程序中：
- 所有线程共享同一个
mm_struct，因此共享同一个mmap_lock - 频繁的 page fault、
mmap、munmap操作会造成mmap_lock的严重竞争 - 持
mmap_lock读锁时，写者（mprotect、munmap）被完全阻塞
CONFIG_PER_VMA_LOCK 引入了更细粒度的 VMA 级别锁（include/linux/mm_types.h:943）：
#ifdef CONFIG_PER_VMA_LOCK
unsigned int vm_lock_seq; // 写锁版本号
refcount_t vm_refcnt; // VMA 引用计数（同时作为读锁）
#endif写者（修改 VMA）使用 vma_start_write() 先排除读者：
// mm/vma.h（内部实现）
static inline void vma_start_write(struct vm_area_struct *vma)
{
// 增加 mm->mm_lock_seq，使所有持有旧 vm_lock_seq 的读者失效
// 等待引用计数归 1（所有读者退出）
}读者（缺页处理、/proc/maps 等）使用 vma_start_read()：
static inline bool vma_start_read(struct vm_area_struct *vma)
{
// 检查 vm_lock_seq != mm->mm_lock_seq（无写锁时相等）
// 原子增加 vm_refcnt
return true; // 成功获取读锁
}以缺页处理为例（mm/memory.c），Per-VMA 锁允许绕过 mmap_lock：
CPU 发生 page fault
└─ handle_page_fault()
├─ 快路径：
│ ├─ rcu_read_lock()
│ ├─ vma = lock_vma_under_rcu(mm, addr)
│ │ └─ mtree_load(&mm->mm_mt, addr) // RCU 无锁查找
│ │ + vma_start_read(vma) // per-VMA 读锁
│ ├─ 处理缺页（填充页表项）
│ ├─ vma_end_read(vma)
│ └─ rcu_read_unlock()
│
└─ 慢路径（per-VMA 锁失败时）：
├─ mmap_read_lock(mm) // 持 mmap_lock 读锁
├─ find_vma(mm, addr)
├─ 处理缺页
└─ mmap_read_unlock(mm)
如前所述，/proc/PID/maps 使用 per-VMA 锁逐个锁定 VMA（fs/proc/task_mmu.c:182）：
static struct vm_area_struct *get_next_vma(struct proc_maps_private *priv,
loff_t last_pos)
{
if (lock_ctx->mmap_locked)
return vma_next(&priv->iter); // 持 mmap_lock 时直接迭代
// per-VMA 锁模式：解锁上一个，锁定下一个
unlock_ctx_vma(lock_ctx); // vma_end_read(old_vma)
vma = lock_next_vma(lock_ctx->mm, &priv->iter, last_pos);
lock_ctx->locked_vma = vma; // vma_start_read(new_vma)
return vma;
}若 vma_start_read() 失败（写者正在修改），则 fallback_to_mmap_lock() 回退到持 mmap_read_lock 的慢路径（fs/proc/task_mmu.c:199）。
进程 fork 时（kernel/fork.c:1515），dup_mm() 调用 dup_mmap() 复制父进程的内存映射：
fork()/clone()
└─ copy_process()
└─ copy_mm()
└─ dup_mm(tsk, current->mm)
├─ allocate_mm() // 分配新 mm_struct
├─ memcpy(mm, ...) // 浅拷贝 mm_struct
├─ mm_init(mm, ...) // 初始化新 mm（包括 mm_mt）
└─ dup_mmap(mm, oldmm) // 复制 VMA 树
dup_mmap() 使用 __mt_dup() 复制 Maple Tree（lib/maple_tree.c:6376）：
int __mt_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp)
{
int ret = 0;
MA_STATE(mas, mt, 0, 0);
MA_STATE(new_mas, new, 0, 0);
// DFS 前序遍历，memcpy 每个节点后分配新子节点
mas_dup_build(&mas, &new_mas, gfp);
if (unlikely(mas_is_err(&mas))) {
ret = xa_err(mas.node);
if (ret == -ENOMEM)
mas_dup_free(&new_mas); // 失败时释放已分配节点
}
return ret;
}mas_dup_build() 的核心逻辑（DFS 复制，lib/maple_tree.c:6208+）：
// 对每个节点：memcpy 源节点内容到新节点
memcpy(new_node, node, sizeof(struct maple_node));
// 更新父节点指针（指向新树中的对应父节点）
val = (unsigned long)node->parent & MAPLE_NODE_MASK;
new_node->parent = ma_parent_ptr(val | (unsigned long)parent);复制完成后，新树的 slot 中的 vm_area_struct * 指针仍然指向父进程的 VMA 对象，后续 dup_mmap() 会为每个 VMA 创建新的 vm_area_struct 副本（通过 vm_area_dup()）并更新新树中的指针。
dup_mmap() 逐个遍历父进程的 VMA（通过 for_each_vma），对每个 VMA：
vm_area_dup(vma)— 复制 VMA 结构体vma_dup_policy(vma, tmp)— 复制 NUMA 策略- 若 VMA 有
vm_ops->open，调用open(tmp)通知驱动 copy_page_range(tmp, vma)— 标记页表项为写保护（COW 设置）- 将新 VMA 插入子进程的
mm_mt
由于使用了 __mt_dup() 先复制整树结构，实际的 VMA 指针更新可以在同一次遍历中完成，避免了对子进程 mm_mt 的多次独立插入操作。
| 操作 | 旧版（rbtree + 链表） | Maple Tree |
|---|---|---|
| 树结构复制 | O(N log N)（逐个 rb_insert） | O(N)（__mt_dup DFS memcpy） |
| VMA 遍历 | O(N) 链表 | O(N) 游标 |
| 整体 fork 时间 | O(N log N) | O(N) |
Linux 内核用 Maple Tree 替换了 fd 表的旧位图实现。进程的打开文件描述符以整数 fd 为键存储在 Maple Tree 中。
与 VMA 场景不同，fd 表使用密集节点（maple_dense）为主，因为 fd 通常是从 0 开始的小整数。
lib/idr.c 的 IDR 机制（整数 ID 到对象的映射）也基于 Maple Tree 实现：
// include/linux/idr.h
struct idr {
struct maple_tree idr_rt;
unsigned int idr_base;
unsigned int idr_next;
};IDR 广泛用于内核各子系统分配唯一 ID，如 PID、设备号、inode 号等。
vhost（虚拟设备后端）和 io_uring 中的固定缓冲区（io_uring_register 的 IORING_REGISTER_BUFFERS）也使用 Maple Tree 追踪用户空间内存范围。
场景 键类型 树类型 主要特性
------------------------------------------------------------
VMA 管理 地址范围 arange_64 gap 追踪
fd 表 整数 fd dense 紧凑存储
IDR 整数 ID range_64 范围分配
vhost 内存映射 地址范围 range_64 高效查找
| 主题 | 文件 | 行号 |
|---|---|---|
| Maple Tree 总体注释 | lib/maple_tree.c |
11–53 |
struct maple_tree |
include/linux/maple_tree.h |
222–231 |
struct maple_range_64 |
include/linux/maple_tree.h |
103–113 |
struct maple_arange_64 |
include/linux/maple_tree.h |
124–130 |
struct maple_node |
include/linux/maple_tree.h |
285–303 |
struct ma_state |
include/linux/maple_tree.h |
430–446 |
enum maple_type |
include/linux/maple_tree.h |
137–142 |
enum maple_status |
include/linux/maple_tree.h |
379–388 |
enum store_type |
include/linux/maple_tree.h |
144–155 |
MA_STATE 宏 |
include/linux/maple_tree.h |
481–495 |
mt_slots[] / mt_pivots[] 数组 |
lib/maple_tree.c |
108–131 |
maple_tree_init() |
lib/maple_tree.c |
5863–5872 |
mte_node_type() |
lib/maple_tree.c |
231–236 |
mte_set_node_dead() |
lib/maple_tree.c |
332–336 |
ma_dead_node() |
lib/maple_tree.c |
566–574 |
ma_free_rcu() |
lib/maple_tree.c |
205–209 |
| 主题 | 文件 | 行号 |
|---|---|---|
mtree_load() |
lib/maple_tree.c |
5882–5911 |
mtree_store_range() |
lib/maple_tree.c |
5924–5942 |
mtree_store() |
lib/maple_tree.c |
5955–5960 |
mtree_insert_range() |
lib/maple_tree.c |
5973–5997 |
mtree_alloc_range() |
lib/maple_tree.c |
6017–6053 |
mtree_erase() |
lib/maple_tree.c |
6148–6161 |
mt_find() |
lib/maple_tree.c |
6467–6528 |
mt_find_after() |
lib/maple_tree.c |
6531–6549 |
mas_find() |
lib/maple_tree.c |
5614–5626 |
mas_preallocate() |
lib/maple_tree.c |
5183–5207 |
mas_alloc_nodes() |
lib/maple_tree.c |
1098–1148 |
mas_nomem() |
lib/maple_tree.c |
5842–5861 |
mas_empty_area() |
lib/maple_tree.c |
4727–4777 |
mas_empty_area_rev() |
lib/maple_tree.c |
4781–4838 |
mas_wr_store_type() |
lib/maple_tree.c |
3893–3934 |
mas_insert() |
lib/maple_tree.c |
3963–4000 |
__mt_dup() |
lib/maple_tree.c |
6356–6391 |
| 主题 | 文件 | 行号 |
|---|---|---|
struct mm_struct.mm_mt |
include/linux/mm_types.h |
~1140 |
struct vm_area_struct |
include/linux/mm_types.h |
913–1056 |
struct vma_iterator |
include/linux/mm_types.h |
1497–1499 |
VMA_ITERATOR 宏 |
include/linux/mm_types.h |
1501–1509 |
vma_iter_init() |
include/linux/mm_types.h |
1511–1515 |
struct address_space |
include/linux/fs.h |
470–490 |
vm_flags 定义 |
include/linux/mm.h |
402–509 |
VM_SPECIAL 宏 |
include/linux/mm.h |
550 |
VM_IGNORE_MERGE 宏 |
include/linux/mm.h |
611 |
struct vm_operations_struct |
include/linux/mm.h |
749–830 |
| 主题 | 文件 | 行号 |
|---|---|---|
vma_find() / vma_next() |
include/linux/mm.h |
1311–1324 |
for_each_vma 宏 |
include/linux/mm.h |
1378–1379 |
vma_lookup() |
include/linux/mm.h |
3956–3960 |
find_vma() |
mm/mmap.c |
902–908 |
find_vma_intersection() |
mm/mmap.c |
883–891 |
find_vma_prev() |
mm/mmap.c |
924–936 |
do_mmap() |
mm/mmap.c |
335–565 |
ksys_mmap_pgoff() |
mm/mmap.c |
567–620 |
SYSCALL_DEFINE1(brk) |
mm/mmap.c |
116–214 |
__mmap_region() |
mm/vma.c |
2720–2785 |
mmap_region() |
mm/vma.c |
2811–2845 |
__split_vma() |
mm/vma.c |
497–584 |
commit_merge() |
mm/vma.c |
728–768 |
vma_merge_existing_range() |
mm/vma.c |
805–999 |
vma_merge_new_range() |
mm/vma.c |
1046–1106 |
vma_expand() |
mm/vma.c |
1151–1220 |
remove_vma() |
mm/vma.c |
463–471 |
validate_mm() |
mm/vma.c |
642–694 |
is_mergeable_vma() |
mm/vma.c |
86–100 |
can_vma_merge_before() |
mm/vma.c |
195–206 |
can_vma_merge_after() |
mm/vma.c |
217–225 |
can_vma_merge_right() |
mm/vma.c |
436–458 |
can_merge_remove_vma() |
mm/vma.c |
771–773 |
__vma_link_file() |
mm/vma.c |
227–236 |
do_brk_flags() |
mm/vma.c |
2859–2900 |
| 主题 | 文件 | 行号 |
|---|---|---|
proc_pid_maps_operations |
fs/proc/task_mmu.c |
832 |
proc_pid_maps_op (seq_ops) |
fs/proc/task_mmu.c |
505–510 |
m_start() |
fs/proc/task_mmu.c |
275–317 |
m_next() |
fs/proc/task_mmu.c |
319–326 |
show_map_vma() |
fs/proc/task_mmu.c |
463–497 |
show_vma_header_prefix() |
fs/proc/task_mmu.c |
442–460 |
lock_vma_range() |
fs/proc/task_mmu.c |
151–170 |
get_next_vma() |
fs/proc/task_mmu.c |
182–197 |
fallback_to_mmap_lock() |
fs/proc/task_mmu.c |
199–213 |
由 Claude Code 分析生成