按文件页区间查找相关进程映射
Linux 用增强红黑树索引文件映射的页偏移区间，反向查找与一个 folio 相交的 VMA。
工程问题#
同一文件的不同范围可以映射到多个进程。回收或迁移文件页时，需要找出可能映射这些页的 VMA；逐个扫描文件的全部映射会把无关区间也带入处理。
实际实现#
address_space.i_mmap 以 VMA 的文件页偏移区间建立 interval tree，节点额外保存整棵子树的最大结束偏移。rmap_walk_file 将 folio 转为闭区间，搜索时结合区间起点排序与子树最大终点排除不相交分支，再调用 rmap_one 处理候选 VMA。
处理流程#
- 用 vm_pgoff 和 VMA 页数确定文件页偏移闭区间
- 以区间起点排序，在红黑树节点维护子树最大终点
- 将 folio 的起始偏移及页数换算为待查闭区间
- 遍历相交 VMA，换算虚拟地址后交给反向映射回调
源码片段#
固定版本 · 原文摘录13static inline unsigned long vma_start_pgoff(struct vm_area_struct *v)14{15 return v->vm_pgoff;16}1718static inline unsigned long vma_last_pgoff(struct vm_area_struct *v)19{20 return v->vm_pgoff + vma_pages(v) - 1;21}2223INTERVAL_TREE_DEFINE(struct vm_area_struct, shared.rb,24 unsigned long, shared.rb_subtree_last,25 vma_start_pgoff, vma_last_pgoff, /* empty */, vma_interval_tree)VMA 的起止键来自文件页偏移，shared.rb_subtree_last 是子树最大终点；宏将这些字段绑定到增强红黑树。
2685lookup:2686 vma_interval_tree_foreach(vma, &mapping->i_mmap,2687 pgoff_start, pgoff_end) {2688 unsigned long address = vma_address(vma, pgoff_start,2689 folio_nr_pages(folio));26902691 VM_BUG_ON_VMA(address == -EFAULT, vma);2692 cond_resched();26932694 if (rwc->invalid_vma && rwc->invalid_vma(vma, rwc->arg))2695 continue;26962697 if (!rwc->rmap_one(folio, vma, address, rwc->arg))2698 goto done;2699 if (rwc->done && rwc->done(folio))2700 goto done;2701 }遍历与 folio 文件页区间相交的 VMA，先换算虚拟地址，再执行 rmap_one；这段调用证明 interval tree 直接用于文件页反向映射。
88 if (node->ITRB.rb_left) { \89 ITSTRUCT *left = rb_entry(node->ITRB.rb_left, \90 ITSTRUCT, ITRB); \91 if (start <= left->ITSUBTREE) { \92 /* \93 * Some nodes in left subtree satisfy Cond2. \94 * Iterate to find the leftmost such node N. \95 * If it also satisfies Cond1, that's the \96 * match we are looking for. Otherwise, there \97 * is no matching interval as nodes to the \98 * right of N can't satisfy Cond1 either. \99 */ \100 node = left; \101 continue; \102 } \103 } \104 if (ITSTART(node) <= last) { /* Cond1 */ \105 if (start <= ITLAST(node)) /* Cond2 */ \106 return node; /* node is leftmost match */ \只有左子树最大终点不小于查询起点时才进入该子树；随后检验当前节点两端是否相交。查询依赖区间增强信息，而不只是普通键值查找。
依次展示区间定义、反向映射调用和子树剪枝。完整函数还包括锁获取、调度让出及停止条件，摘录未将它们视为树本身提供的能力。
收益与取舍#
工程分析带来的收益
- 查询可以跳过最大终点仍小于待查起点的整棵子树
- 一个文件页范围可以返回多个进程中的候选 VMA，而不局限于单个包含区间
付出的代价
- 每个节点增加区间增强字段；插入、删除和旋转需要维护子树最大终点
- 区间命中只是候选映射，具体页表状态仍由回调检查；还需要 folio 锁和 i_mmap 读锁保护
可比较的选择
线性扫描文件的全部 VMA结构更简单，但每次查询都要检查无关映射；映射数量增多时扫描成本上升。
版本与适用范围#
对应 Linux v6.12 的 rmap_walk_file。键是同一文件内的页偏移，不是进程虚拟地址；与 mm_struct.mm_mt 管理进程 VMA 的 Maple Tree 是不同索引。回调可以提前结束，区间相交不保证页表当前仍存在映射。
参考来源#
源码、官方文档与原始论文mm/interval_tree.c · vma_start_pgoff / vma_last_pgoff / INTERVAL_TREE_DEFINE
include/linux/interval_tree_generic.h · INTERVAL_TREE_DEFINE · _subtree_search