BiscuitOS 内存管理之分页大专题订阅入口

STRUCT vm_area_struct 数据结构的 vm_rb 成员用于描述 VMA 在进程地址空间区间树的节点，rb_subtree_gap 成员则描述该区间树节点子树中最大 GAP. vm_rb 成员经常用在通过虚拟地址查找 VMA 的场景，rb_subtree_gap 则用在分配新虚拟内存的场景, 两者都与区间树有密不可分的联系.

VM_RB/RB_SUBTREE_GAP 创建

当调用 mmap 系统调用分配一段虚拟内存时，内核会按上图函数调用逻辑分配虚拟内存，内核在 get_unmapped_area 函数里已经找到一块可用的区域，那么区间树的叶子节点的 GAP 满足分配需求. 内核接着在 LINK RB-NODE 处调用 __vma_link_rb 函数将新的 VMA 的 vm_rb 插入到区间树指定的位置，并且更新 VMA 的 rb_subtree_gap 的值，以此记录其子树最大 GAP 值,

内核调用 find_vma_link 函数查找新分配可用虚拟地址 addr 的 PREV VMA，这里由于速度考虑，并不是从进程地址空间维护的双链表 mmap 处开始查找，而是从进程地址空间维护的区间树基于 addr 进行查找，这样会节省查找的时间，当遍历到区间树的叶子节点，如果叶子节点的 rb_subtree_gap 大于分配需求的大小，那么找到可分配的区域，于是结束遍历，并记录叶子节点机器父节点的位置.

基于对 find_vma_link 函数逻辑的分析，接下来结合上图案例进行实际分析具体过程:

• A: 内核获得一个可用的虚拟地址 addr，此时从区间树的 ROOT 开始查询，此时 addr 小于 A-VMA 的结束地址，因此其进入 LEFT
• B: 由于 B-VMA 的结束地址小于 addr，那么此时进入 RIGHT，并将 PREV 指向 B-VMA
• D: 由于 D-VMA 的结束地址大于 addr，那么进入 LEFT，并不更新 PREV
• E: 由于 E 节点已经是叶子节点，并且 E 节点的 rb_subtree_gap 符合分配需求，那么查找结束，此时 PREV 指向 B-VMA，此时 B-VMA 的结束地址确实是最接近 addr.

由于 find_vma_link 函数已经在区间树中找到合适的位置，那么插入 VMA 的 vm_rb 节点只需像红黑树一样插入即可，那么函数在 615 行调用 rb_link_node 函数和 vma_rb_insert 函数进行实际的插入操作，具体细节涉及红黑树的技术，这里不做详细描述，开发者只需知道将新 VMA 的 vm_rb 插入到区间树即可。函数接着在 616-617 行更新了 VMA 的 rb_subtree_gap 的值，其将记录新 VMA 的子树中最大 GAP 值. 另外函数在 601-604 行判断新的 VMA 是否为 VMA 链表的最后一个，如果是那么执行 604 的逻辑，将进程地址空间的 mm->highest_vm_end 设置为 VMA 的结束地址, 反之则更新新 VMA 的 NEXT VMA 的 rb_subtree_gap 值. 以上便是 VMA 的 vm_rb 和 rb_subtree_gap 的代码逻辑，接下来通过一些实践案例介绍两个成员的使用场景，实践案例在 BiscuitOS 上的部署逻辑如下:

cd BiscuitOS
make menuconfig

  [*] Package  --->
      [*] Memory Mapping Mechanism  --->
          [*] Memory Mapping: VMA VM_RB/RB_SUBTREE_GAP --->

# 部署实践案例
make
# 源码目录
cd BiscuitOS/output/linux-6.0-x86_64/package/BiscuitOS-MEMORY-MMAP-VMA-VM-RB-default/
# 部署源码
make download
# 在 BiscuitOS 中实践
make build

BiscuitOS-MEMORY-MMAP-VMA-VM-RB-default Source Code on Gitee

实践案例由两部分组成，其中一部分是一个应用程序，其逻辑是在 26 行通过 open 函数打开 “/dev/BiscuitOS-VMA” 文件，然后在 33 行基于 ioctl 函数向文件发送 TRAVER_VMA 请求，处理完毕之后关闭文件.

实践案例的另外一部分是内核模块，其由 MISC 驱动框架构成，并向用户空间提供 “/dev/BiscuitOS-VMA” 文件，文件实现了 ioctl 回调，即用户进程打开该文件，并通过 ioctl 向该文件发送请求时，BiscuitOS_ioctl 函数会被调用。BiscuitOS_ioctl 函数只处理 TRAVER_VMA 请求，当用户进程发起 TRAVER_VMA 请求时，进入 25 行分支进行处理. 函数首先在 27 行获得当前进程的虚拟地址空间，然后在 29 行先检查用户进程的地址空间的区间树是否为空，如果为空直接返回错误. 当区间树不为空时在 35 行使用 for 循环中旬遍历区间树，所谓中序遍历红黑树指的是按左中右的顺序遍历，因为在区间树里左子树的地址小于当前节点，而右节点的地址大于当前节点. 遍历过程中也将节点的 RB_SUBTREE_GAP 打印出来, 接下来在 BiscuitOS 上实践该案例:

当 BiscuitOS 运行之后，直接运行 RunBiscuitOS.sh 脚本可以看到运行实践案例，此时实践案例将进程区间树的内容全部打印出来，并且打印的区域都是从低地址到高地址进行打印，另外还打印了 RB_SUBTREE_GAP 的值，以此可知遍历区间树按中序方式进行遍历. 以上提供了一种 VM_RB 和 RB_SUBTREE_GAP 的使用场景，更多场景开发者可以结合本节学的内容进行拓展.