VMA 与 Maple Tree

覆盖: vm_area_struct → VMA 操作 (mmap/munmap/mprotect/mremap) → Maple Tree 取代红黑树 (6.1+) → VMA merging → page fault 与 VMA 查找 内核版本: 2.6 ~ 6.x，重点标注 Maple Tree 迁移

概述

每个进程的地址空间由一组 VMA (Virtual Memory Area) 描述。一个 VMA 代表一段连续的虚拟地址范围，具有相同的保护属性和映射类型（匿名内存、文件映射、设备映射等）。mmap() 创建 VMA，munmap() 销毁 VMA，mprotect() 修改 VMA 属性。

传统的 VMA 用红黑树 + 双向链表管理（O(log n) 查找，O(n) 遍历）。6.1 引入的 Maple Tree 将操作降到 O(log n)，同时支持 lockless 读遍历——这是内存管理子系统近年来最重要的数据结构变更之一。

vm_area_struct

// include/linux/mm_types.h
struct vm_area_struct {
    // 地址范围
    unsigned long           vm_start;
    unsigned long           vm_end;         // 不包含在 VMA 内 (半开区间)

    // 链表/树节点（旧: 红黑树，新: Maple Tree）
    union {
        struct {
            struct list_head    vm_list;    // 双向链表 (遍历用)
            struct rb_node      vm_rb;      // 红黑树 (查找用, 6.0-)
        };
        // 6.1+: VMA 完全由 Maple Tree 管理, 这两个字段被覆盖
    };

    // 属性
    pgprot_t                vm_page_prot;  // 页保护位 (R/W/X 编码)
    unsigned long           vm_flags;      // VM_READ, VM_WRITE, VM_EXEC, VM_SHARED, ...

    // 关联的 mm_struct 和文件 (如果是 file-backed)
    struct mm_struct        *vm_mm;
    struct file             *vm_file;      // NULL for anonymous
    unsigned long           vm_pgoff;      // 在文件中的偏移 (page 为单位)

    // 操作函数表
    const struct vm_operations_struct *vm_ops;  // open, close, fault, ...

    // 匿名映射 (anonymous)
    struct anon_vma         *anon_vma;     // 反向映射 (rmap) 的关键
    struct anon_vma_name    *anon_name;    // [anon:name] (5.17+)

    // 共享内存 (shmem / MAP_SHARED anonymous)
    struct address_space    *vm_swap;      // swap cache 的 address_space
};

关键 vm_flags

VMA 的匿名 / 文件分类

匿名 VMA (anonymous):
  vm_file == NULL
  例子: malloc/mmap(MAP_ANONYMOUS) 分配的堆/栈/heap
  数据没有对应的磁盘文件
  swap 时写入 swap 分区/文件

文件映射 VMA (file-backed):
  vm_file != NULL
  例子: mmap(普通文件), 代码段 (exec 的 ELF LOAD 段)
  page cache 中的页面与文件内容一致
  dirty 页面写回对应的文件

VMA 操作

mmap: 创建 VMA

flowchart TD
    SYSCALL["mmap() 系统调用"] --> AREA["get_unmapped_area()<br/>找空闲地址区间"]

    AREA --> ARCH{"架构相关搜索"}
    ARCH -->|"x86"| TOPDOWN["自顶向下搜索<br/>(top-down, ASLR)"]
    ARCH -->|"legacy"| BOTTOMUP["自底向上<br/>(mmap_legacy_base)"]

    AREA --> REGION["mmap_region()"]

    REGION --> CHECK{"检查与已有<br/>VMA 的关系"}
    CHECK -->|"完全匹配"| MERGE["复用或合并"]
    CHECK -->|"部分重叠"| SPLIT["split VMA"]
    CHECK -->|"不相干"| NEW["新建 VMA"]

    NEW --> VM_OPS["调用 vm_ops->mmap()<br/>文件系统回调<br/>如 ext4: 注册 filemap_fault()"]

    VM_OPS --> DEMAND["⚠️ 不更新页表!<br/>demand paging:<br/>实际分配推迟到 page fault"]

    DEMAND --> RET["返回映射起始地址 ✅"]

    classDef sys call fill:#e3f2fd,stroke:#1565c0
    classDef step fill:#f3e5f5,stroke:#7b1fa2
    classDef decision fill:#fff3e0,stroke:#ef6c00
    classDef done fill:#e8f5e9,stroke:#2e7d32
    class SYSCALL syscall
    class AREA,TOPDOWN,BOTTOMUP,REGION,MERGE,SPLIT,NEW,VM_OPS,DEMAND step
    class ARCH,CHECK decision
    class RET done

munmap: 销毁 VMA

SYSCALL_DEFINE2(munmap, ...) → do_munmap()

do_munmap():
  ├─ find_vma_intersection()   // 找到覆盖该区间的 VMA
  ├─ split VMA (如果部分清除)
  ├─ detach_vmas_to_be_unmapped()
  │   └─ 从 mm 的 VMA 集合中摘除
  ├─ unmap_region()
  │   └─ unmap_vmas → 遍历 VMA 列表
  │       └─ unmap_page_range()
  │           → 清空对应页表项 (zap_pte_range)
  │           → 释放物理页 (put_page → 非最后一个引用则丢到 page cache)
  │           → TLB shootdown (多核)
  └─ remove_vma_list()
      └─ 释放 vm_area_struct (kmem_cache_free)

mprotect: 改权限

SYSCALL_DEFINE3(mprotect, ...) → do_mprotect_pkey()

// 不需要重新分配物理页，只需改 PTE 标志:
//   改 VM_WRITE → PTE 的 R/W bit
//   改 VM_EXEC  → PTE 的 NX bit
//   加上 page table walk → set_pte_at() → flush TLB

mremap: 调整大小/移动

SYSCALL_DEFINE5(mremap, ...) → do_mremap()

// MREMAP_MAYMOVE: 允许移动
//   → 如果当前地址后面空间不够:
//     get_unmapped_area() 找新位置
//     move_page_tables()  → 复制页表项到新位置 (不复制物理页!)
//     → TLB flush
//
// 与 realloc 的配合:
//   glibc 使用 mremap 扩展 big allocations → 避免物理内存复制

Maple Tree: VMA 管理的新引擎

为什么替换红黑树

旧设计 (红黑树 + 链表, 2.6 ~ 6.0):
  VMA 存在红黑树 (查找 O(log n)) 和双向链表 (遍历 O(n)) 中
  缺点:
    - 两个数据结构必须保持同步 → 复杂
    - 所有操作必须在 mmap_lock 下 → 锁竞争
    - 链表遍历在 VMA 密集场景 (如大量 mmap) 下 O(n)

新设计 (Maple Tree, 6.1+):
  VMA 只存在 Maple Tree 中
  优点:
    - 所有操作 O(log n): 查找/插入/删除/区间查询
    - 支持 Lockless 读遍历 (RCU-protected): 未来的 page fault 可能不需要锁
    - 区间操作高效: 直接找到重叠的所有 VMA
    - B-tree 变种: cache-line 友好, 节点大小可变

Maple Tree 结构

// lib/maple_tree.c
// Maple Tree 是一个 B-tree 变种，每个节点有最多 16 个 slot

// 节点类型:
//   MAPLE_NODE_DENSE:  所有 slot 都是数据 (类似数组)
//   MAPLE_NODE_RANGE:  slot 携带 range 信息 (用于稀疏存储)

// 每层可以编码不同范围的 key:
//   Node 0: [0, 4096)     (4K)
//   Node 1: [0, 16777216) (16M)
//   Node 2: [0, 68719476736) (64G)
//   ...
//   总共最多 8 层 (对于 64-bit key)

// 对于 VMA 来说:
//   key = 虚拟地址 (起始)
//   value = vm_area_struct *
//   查找: mas_find() → 找到覆盖某地址的 VMA

Lockless 遍历

// Maple Tree 的 RCU 安全设计:
//   修改者: 拿 spinlock → 修改节点 (如果节点满 → split + copy)
//   读者:   不拿锁 → rcu_dereference 读节点
//           节点不会被修改者直接改写，而是复制后修改 → RCU 回收旧节点
//
// 这是 Maple Tree 最大的价值:
//   未来的 do_page_fault() 可以在 RCU read lock 下查找 VMA
//   → 不需要 mmap_lock (读端) → 消除 mmap_lock 的锁竞争

Page Fault 与 VMA 查找

// arch/x86/mm/fault.c
// do_page_fault() 是最热的 VMA 查找路径

static void do_page_fault(struct pt_regs *regs, unsigned long error_code) {
    unsigned long address = read_cr2();  // 取出错的虚拟地址

    // 1. 拿 mmap_read_lock(mm)
    //
    // 2. find_vma(mm, address)
    //    旧: find_vma() → 红黑树查找
    //    新: find_vma() → mas_find(&mas, address, ...) → Maple Tree 查找
    //
    //    找到: 返回覆盖 address 的 VMA
    //    找不到: SIGSEGV
    //
    // 3. 检查 VMA 权限 (vm_flags 与 error_code 对比)
    //    读但 VM_READ 没开? → SIGSEGV
    //    写但 VM_WRITE 没开? → SIGSEGV (COPY-ON-WRITE 时特别关键!)
    //
    // 4. handle_mm_fault() → 分配物理页 + 建 PTE
    //    匿名: do_anonymous_page() / do_swap_page()
    //    文件: do_fault() → filemap_fault()
    //
    // 5. 释放 mmap_read_lock(mm)
}

VMA 合并 (Merging)

相邻且属性相同的 VMA 会被自动合并：

// mm/mmap.c
// vma_merge():
//   新 mmap 请求与前后 VMA 比较:
//     vm_flags 相同?
//     vm_file 相同? (或都是匿名)
//     vm_pgoff 连续?
//     PROT 匹配?
//     anon_vma 兼容?
//   → 满足条件: 合并为一个更大的 VMA
//
// 为什么要合并?
//   减少 VMA 数量 → 更少的查找时间
//   减少 slab 分配 (vm_area_struct)
//   /proc/<pid>/maps 显示更简洁
//
// 经典例子:
//   brk() 扩展堆 → 多次小扩展 → 自动合并为一个大的 [heap] VMA

调试

# VMA 布局
cat /proc/<pid>/maps  # 人类可读
cat /proc/<pid>/smaps # 每个 VMA 的内存统计 (RSS/PSS/Swap)

# VMA 统计
cat /proc/<pid>/status | grep Vm
# VmPeak: 历史最大虚拟内存
# VmSize: 当前虚拟内存总量
# VmRSS:  物理内存使用 (Resident Set Size)
# VmData/VmStk/VmExe/VmLib: 数据/栈/代码/库

# VMA 数量监控 (大量 VMA 会降低性能)
wc -l /proc/<pid>/maps

参考与延伸

• 内核文档⁠: Documentation/core-api/maple_tree.rst, Documentation/mm/mmap.rst
• LWN:
  • "Introducing the Maple Tree" (lwn.net/Articles/867525/)
  • "The state of the Maple Tree" (lwn.net/Articles/905317/)
  • "mmap_lock and VMA locking" (lwn.net/Articles/909840/)
• 源码文件⁠:
  • lib/maple_tree.c — Maple Tree 实现
  • mm/mmap.c — VMA 管理 (mmap/munmap/mprotect)
  • include/linux/mm_types.h — vm_area_struct 定义
  • arch/x86/mm/fault.c — page fault handler

关键词: vm_area_struct, VMA, mmap, munmap, Maple Tree, page fault, find_vma, VM_MERGEABLE, mmap_lock