8. 反向映射RMAP机制全解析反向映射Reverse Mapping, RMAP是Linux内存管理中最核心、也最容易被忽略的机制它解决了一个核心问题给定一个物理页如何快速找到所有映射了这个页的进程页表项。没有反向映射之前内核要回收一个物理页必须遍历系统中所有进程的所有页表查找是否有映射了这个页的页表项时间复杂度极高完全不可用。反向映射机制的出现让内核可以在O(1)~O(n)的时间复杂度内找到所有映射了该页的页表项是内存回收、页迁移、COW写时复制、KSM同页合并等机制的底层基础。本章节基于Linux 6.6 LTS内核完整拆解反向映射的设计思想、核心数据结构、匿名页与文件页的反向映射实现、全链路操作流程。8.1 反向映射的核心设计目标快速查找页表项给定一个物理页能快速找到所有映射了这个页的进程页表项用于修改页表项比如回收页时清除页表项、页迁移时修改页表项的物理地址最小化内存开销反向映射的元数据开销必须极小不能占用大量内存尤其是系统中有海量进程、海量物理页的场景高性能的操作接口反向映射的遍历、添加、删除操作必须高效不能成为内存管理的性能瓶颈支持复杂场景支持私有映射、共享映射、写时复制、线程共享地址空间、大页等复杂场景。8.2 反向映射的核心分类Linux的反向映射分为两大类分别对应两种不同类型的页文件页的反向映射基于struct address_space和优先级搜索树Interval Tree实现用于页缓存中的文件页包括可执行文件、共享库、数据文件的映射页匿名页的反向映射基于struct anon_vma和anon_vma_chain实现用于没有后备文件的匿名页包括堆、栈、mmap匿名映射的页。两者的核心差异文件页的后备存储是磁盘文件所有映射了该文件同一偏移的进程共享同一个页缓存反向映射的核心是找到所有映射了该文件偏移的VMA匿名页没有后备文件是进程私有的COW之前反向映射的核心是找到所有共享该页的VMA。8.3 文件页的反向映射实现文件页的反向映射是Linux最早实现的反向映射机制设计相对简单基于文件的地址空间和VMA的区间树实现。8.3.1 核心数据结构struct address_space每个打开的文件对应一个address_space实例管理该文件的页缓存是文件页反向映射的核心锚点定义在include/linux/fs.h中核心字段struct address_space { // 文件的宿主inode struct inode *host; // 页缓存的XArray存储该文件的所有缓存页 struct xarray i_pages; // 映射了该文件的所有VMA的区间树反向映射的核心 struct maple_tree i_mmap; // 地址空间的自旋锁 rwlock_t i_mmap_rwsem; // 脏页、回写相关字段 unsigned long nrpages; struct writeback_control *writeback; };核心字段i_mmapMaple Tree枫树树Linux 6.2替换了之前的优先级搜索树存储所有映射了该文件的VMA每个VMA对应文件的一个偏移区间通过文件偏移可以快速找到所有映射了该偏移的VMA。struct vm_area_struct每个文件映射的VMA会被插入到对应文件的address_space-i_mmap区间树中key是VMA映射的文件偏移区间[vm_pgoff, vm_pgoff (vm_end - vm_start)/PAGE_SIZE]。8.3.2 文件页反向映射的核心流程文件页反向映射的核心目标是给定一个文件页对应文件的inode和页内偏移找到所有映射了该页的VMA然后通过VMA和虚拟地址找到对应的页表项。完整执行流程从物理页的struct page结构体中获取对应的address_spacepage-mapping和页内偏移page-index加i_mmap_rwsem读锁遍历address_space-i_mmap区间树找到所有映射了该文件偏移page-index的VMA对于每个找到的VMA计算该页在VMA中的虚拟地址vma-vm_start (page-index - vma-vm_pgoff) * PAGE_SIZE通过VMA所属的mm_structvma-vm_mm和虚拟地址遍历页表找到对应的页表项对页表项执行对应的操作比如内存回收时清除页表项、页迁移时修改页表项的物理地址、设置页表项为只读COW等。核心工程细节文件页的反向映射只需要存储文件的address_space和页内偏移不需要为每个页存储额外的元数据内存开销极小Maple Tree的区间查询效率极高O(logn)时间复杂度就能找到所有映射了该偏移的VMA同一个文件的多个共享映射、私有映射都会被插入到同一个i_mmap区间树中一次遍历就能找到所有映射了该页的VMA。8.4 匿名页的反向映射实现匿名页没有后备文件无法像文件页那样基于address_space做反向映射而且匿名页会通过fork()被多个进程共享COW反向映射的设计比文件页复杂得多。Linux采用了基于anon_vma和anon_vma_chain的匿名页反向映射机制完美解决了COW场景下的反向映射问题。8.4.1 核心设计思想匿名页反向映射的核心设计是每个匿名VMA对应一个anon_vma结构体所有共享该匿名页的VMA都会被链接到同一个anon_vma中通过anon_vma可以找到所有映射了该匿名页的VMA。fork()创建子进程时子进程会复制父进程的匿名VMA同时创建anon_vma_chain把子进程的VMA链接到父进程的anon_vma中这样父进程的匿名页被共享后通过anon_vma就能找到所有子进程中映射了该页的VMA。8.4.2 核心数据结构struct anon_vma匿名页反向映射的核心锚点管理所有映射了同一组匿名页的VMA定义在include/linux/rmap.h中struct anon_vma { // 保护该结构的自旋锁 struct rw_semaphore rwsem; // 所有链接到该anon_vma的VMA的链表 struct rb_root rb_root; // 该anon_vma对应的根VMA struct vm_area_struct *root_vma; // 引用计数 atomic_t refcount; };核心字段rb_root红黑树存储所有链接到该anon_vma的VMA通过虚拟地址可以快速找到对应的VMA。struct anon_vma_chain连接VMA和anon_vma的桥梁每个VMA和anon_vma的对应关系都有一个anon_vma_chain实例定义在include/linux/rmap.h中struct anon_vma_chain { // 对应的VMA struct vm_area_struct *vma; // 对应的anon_vma struct anon_vma *anon_vma; // 加入anon_vma-rb_root的红黑树节点 struct rb_node rb; // 加入VMA的anon_vma_chain链表的节点 struct list_head same_vma; };每个VMA有一个anon_vma_chain链表链接了所有和该VMA关联的anon_vma每个anon_vma有一个红黑树链接了所有和该anon_vma关联的VMA。struct page中的反向映射字段匿名页的page-mapping字段设置为PAGE_MAPPING_ANON表示这是匿名页page-anon_vma指向该页对应的anon_vmapage-index是该页在VMA中的虚拟地址偏移。8.4.3 匿名页反向映射的核心流程匿名页反向映射的核心目标是给定一个匿名页找到所有映射了该页的VMA然后找到对应的页表项。完整执行流程从物理页的struct page结构体中确认是匿名页PAGE_MAPPING_ANON获取对应的anon_vmapage_anon_vma(page)和页的虚拟地址偏移page-index加anon_vma-rwsem读锁遍历anon_vma-rb_root红黑树找到所有包含该偏移的VMA对于每个找到的VMA计算该页在VMA中的虚拟地址vma-vm_start (page-index - vma-vm_pgoff) * PAGE_SIZE通过VMA所属的mm_struct和虚拟地址遍历页表找到对应的页表项对页表项执行对应的操作清除页表项、修改物理地址、设置只读等。8.4.4 fork()场景下的反向映射处理fork()创建子进程时会复制父进程的所有VMA包括匿名VMA同时处理匿名反向映射子进程复制父进程的匿名VMA创建新的VMA结构体为子进程的VMA创建新的anon_vma_chain实例把子进程的VMA通过anon_vma_chain链接到父进程的anon_vma中同时为子进程的VMA创建新的anon_vma用于子进程后续新建的匿名页父子进程的匿名页的页表项都设置为只读后续写入时触发COW异常。这样父进程的匿名页对应的anon_vma就链接了父子进程的所有VMA通过反向映射就能找到所有映射了该页的VMA完美支持COW场景。8.5 反向映射的核心应用场景反向映射是Linux内存管理的基础设施几乎所有的内存操作都依赖反向映射核心应用场景内存回收内核回收一个物理页时必须通过反向映射找到所有映射了该页的页表项清除页表项刷新TLB然后才能释放物理页。如果没有反向映射内存回收完全无法实现写时复制COWCOW异常处理时需要通过反向映射找到所有共享该页的页表项修改页表项确保只有触发异常的进程复制新页其他进程的页表项保持不变页迁移内存碎片整理、内存热插拔、NUMA平衡时需要把物理页从一个地址迁移到另一个地址必须通过反向映射找到所有映射了该页的页表项修改页表项的物理地址刷新TLB保证进程访问不受影响KSM同页合并内核同页合并机制KSM会把内容相同的匿名页合并为一个只读页减少内存占用必须通过反向映射找到所有映射了原页的页表项修改为指向合并后的页页错误处理处理页被换出swap、页被锁定等异常时需要通过反向映射找到对应的页表项修改页表项的状态。8.6 工程实践与认知纠正1.反向映射的内存开销认知很多工程师误以为反向映射会占用大量内存实际上文件页的反向映射元数据存储在文件的address_space中每个文件只需要一个区间树内存开销极小匿名页的反向映射anon_vma和anon_vma_chain的数量和VMA的数量成正比而不是和物理页的数量成正比哪怕系统中有几十GB的内存反向映射的元数据开销也只有几MB完全可以忽略内核做了大量的优化比如anon_vma的复用、红黑树的高效管理最小化内存开销。2.反向映射的性能优化反向映射的遍历是内存回收、页迁移的核心开销内核做了大量的性能优化用Maple Tree替换了传统的优先级搜索树区间查询的性能提升了30%以上反向映射的遍历采用RCU机制读操作不需要加排他锁允许多个CPU并发遍历内存回收时优先回收只有一个映射的页_mapcount 0不需要遍历反向映射提升回收效率页迁移时优先迁移映射数量少的页减少反向映射的遍历开销。3.反向映射的调试与排查反向映射的异常会导致内核崩溃、内存泄漏、OOM等问题内核提供了相应的调试手段开启CONFIG_DEBUG_RMAP内核配置开启反向映射的调试检查检测非法的VMA链接、引用计数泄漏等问题用/proc/pid/maps查看进程的VMA确认匿名VMA的anon_vma是否正常用crash工具分析内核coredump查看anon_vma的红黑树、VMA的链表定位反向映射的异常。4.认知纠正匿名页的共享范围很多工程师误以为匿名页是进程私有的实际上通过fork()匿名页会被父子进程共享直到触发COW反向映射机制就是为了处理这种共享场景。如果没有反向映射fork()之后的COW完全无法实现这也是反向映射机制最核心的设计目标。
Linux内核学习轨迹第五部：反向映射RMAP机制全解析（第八小节）
8. 反向映射RMAP机制全解析反向映射Reverse Mapping, RMAP是Linux内存管理中最核心、也最容易被忽略的机制它解决了一个核心问题给定一个物理页如何快速找到所有映射了这个页的进程页表项。没有反向映射之前内核要回收一个物理页必须遍历系统中所有进程的所有页表查找是否有映射了这个页的页表项时间复杂度极高完全不可用。反向映射机制的出现让内核可以在O(1)~O(n)的时间复杂度内找到所有映射了该页的页表项是内存回收、页迁移、COW写时复制、KSM同页合并等机制的底层基础。本章节基于Linux 6.6 LTS内核完整拆解反向映射的设计思想、核心数据结构、匿名页与文件页的反向映射实现、全链路操作流程。8.1 反向映射的核心设计目标快速查找页表项给定一个物理页能快速找到所有映射了这个页的进程页表项用于修改页表项比如回收页时清除页表项、页迁移时修改页表项的物理地址最小化内存开销反向映射的元数据开销必须极小不能占用大量内存尤其是系统中有海量进程、海量物理页的场景高性能的操作接口反向映射的遍历、添加、删除操作必须高效不能成为内存管理的性能瓶颈支持复杂场景支持私有映射、共享映射、写时复制、线程共享地址空间、大页等复杂场景。8.2 反向映射的核心分类Linux的反向映射分为两大类分别对应两种不同类型的页文件页的反向映射基于struct address_space和优先级搜索树Interval Tree实现用于页缓存中的文件页包括可执行文件、共享库、数据文件的映射页匿名页的反向映射基于struct anon_vma和anon_vma_chain实现用于没有后备文件的匿名页包括堆、栈、mmap匿名映射的页。两者的核心差异文件页的后备存储是磁盘文件所有映射了该文件同一偏移的进程共享同一个页缓存反向映射的核心是找到所有映射了该文件偏移的VMA匿名页没有后备文件是进程私有的COW之前反向映射的核心是找到所有共享该页的VMA。8.3 文件页的反向映射实现文件页的反向映射是Linux最早实现的反向映射机制设计相对简单基于文件的地址空间和VMA的区间树实现。8.3.1 核心数据结构struct address_space每个打开的文件对应一个address_space实例管理该文件的页缓存是文件页反向映射的核心锚点定义在include/linux/fs.h中核心字段struct address_space { // 文件的宿主inode struct inode *host; // 页缓存的XArray存储该文件的所有缓存页 struct xarray i_pages; // 映射了该文件的所有VMA的区间树反向映射的核心 struct maple_tree i_mmap; // 地址空间的自旋锁 rwlock_t i_mmap_rwsem; // 脏页、回写相关字段 unsigned long nrpages; struct writeback_control *writeback; };核心字段i_mmapMaple Tree枫树树Linux 6.2替换了之前的优先级搜索树存储所有映射了该文件的VMA每个VMA对应文件的一个偏移区间通过文件偏移可以快速找到所有映射了该偏移的VMA。struct vm_area_struct每个文件映射的VMA会被插入到对应文件的address_space-i_mmap区间树中key是VMA映射的文件偏移区间[vm_pgoff, vm_pgoff (vm_end - vm_start)/PAGE_SIZE]。8.3.2 文件页反向映射的核心流程文件页反向映射的核心目标是给定一个文件页对应文件的inode和页内偏移找到所有映射了该页的VMA然后通过VMA和虚拟地址找到对应的页表项。完整执行流程从物理页的struct page结构体中获取对应的address_spacepage-mapping和页内偏移page-index加i_mmap_rwsem读锁遍历address_space-i_mmap区间树找到所有映射了该文件偏移page-index的VMA对于每个找到的VMA计算该页在VMA中的虚拟地址vma-vm_start (page-index - vma-vm_pgoff) * PAGE_SIZE通过VMA所属的mm_structvma-vm_mm和虚拟地址遍历页表找到对应的页表项对页表项执行对应的操作比如内存回收时清除页表项、页迁移时修改页表项的物理地址、设置页表项为只读COW等。核心工程细节文件页的反向映射只需要存储文件的address_space和页内偏移不需要为每个页存储额外的元数据内存开销极小Maple Tree的区间查询效率极高O(logn)时间复杂度就能找到所有映射了该偏移的VMA同一个文件的多个共享映射、私有映射都会被插入到同一个i_mmap区间树中一次遍历就能找到所有映射了该页的VMA。8.4 匿名页的反向映射实现匿名页没有后备文件无法像文件页那样基于address_space做反向映射而且匿名页会通过fork()被多个进程共享COW反向映射的设计比文件页复杂得多。Linux采用了基于anon_vma和anon_vma_chain的匿名页反向映射机制完美解决了COW场景下的反向映射问题。8.4.1 核心设计思想匿名页反向映射的核心设计是每个匿名VMA对应一个anon_vma结构体所有共享该匿名页的VMA都会被链接到同一个anon_vma中通过anon_vma可以找到所有映射了该匿名页的VMA。fork()创建子进程时子进程会复制父进程的匿名VMA同时创建anon_vma_chain把子进程的VMA链接到父进程的anon_vma中这样父进程的匿名页被共享后通过anon_vma就能找到所有子进程中映射了该页的VMA。8.4.2 核心数据结构struct anon_vma匿名页反向映射的核心锚点管理所有映射了同一组匿名页的VMA定义在include/linux/rmap.h中struct anon_vma { // 保护该结构的自旋锁 struct rw_semaphore rwsem; // 所有链接到该anon_vma的VMA的链表 struct rb_root rb_root; // 该anon_vma对应的根VMA struct vm_area_struct *root_vma; // 引用计数 atomic_t refcount; };核心字段rb_root红黑树存储所有链接到该anon_vma的VMA通过虚拟地址可以快速找到对应的VMA。struct anon_vma_chain连接VMA和anon_vma的桥梁每个VMA和anon_vma的对应关系都有一个anon_vma_chain实例定义在include/linux/rmap.h中struct anon_vma_chain { // 对应的VMA struct vm_area_struct *vma; // 对应的anon_vma struct anon_vma *anon_vma; // 加入anon_vma-rb_root的红黑树节点 struct rb_node rb; // 加入VMA的anon_vma_chain链表的节点 struct list_head same_vma; };每个VMA有一个anon_vma_chain链表链接了所有和该VMA关联的anon_vma每个anon_vma有一个红黑树链接了所有和该anon_vma关联的VMA。struct page中的反向映射字段匿名页的page-mapping字段设置为PAGE_MAPPING_ANON表示这是匿名页page-anon_vma指向该页对应的anon_vmapage-index是该页在VMA中的虚拟地址偏移。8.4.3 匿名页反向映射的核心流程匿名页反向映射的核心目标是给定一个匿名页找到所有映射了该页的VMA然后找到对应的页表项。完整执行流程从物理页的struct page结构体中确认是匿名页PAGE_MAPPING_ANON获取对应的anon_vmapage_anon_vma(page)和页的虚拟地址偏移page-index加anon_vma-rwsem读锁遍历anon_vma-rb_root红黑树找到所有包含该偏移的VMA对于每个找到的VMA计算该页在VMA中的虚拟地址vma-vm_start (page-index - vma-vm_pgoff) * PAGE_SIZE通过VMA所属的mm_struct和虚拟地址遍历页表找到对应的页表项对页表项执行对应的操作清除页表项、修改物理地址、设置只读等。8.4.4 fork()场景下的反向映射处理fork()创建子进程时会复制父进程的所有VMA包括匿名VMA同时处理匿名反向映射子进程复制父进程的匿名VMA创建新的VMA结构体为子进程的VMA创建新的anon_vma_chain实例把子进程的VMA通过anon_vma_chain链接到父进程的anon_vma中同时为子进程的VMA创建新的anon_vma用于子进程后续新建的匿名页父子进程的匿名页的页表项都设置为只读后续写入时触发COW异常。这样父进程的匿名页对应的anon_vma就链接了父子进程的所有VMA通过反向映射就能找到所有映射了该页的VMA完美支持COW场景。8.5 反向映射的核心应用场景反向映射是Linux内存管理的基础设施几乎所有的内存操作都依赖反向映射核心应用场景内存回收内核回收一个物理页时必须通过反向映射找到所有映射了该页的页表项清除页表项刷新TLB然后才能释放物理页。如果没有反向映射内存回收完全无法实现写时复制COWCOW异常处理时需要通过反向映射找到所有共享该页的页表项修改页表项确保只有触发异常的进程复制新页其他进程的页表项保持不变页迁移内存碎片整理、内存热插拔、NUMA平衡时需要把物理页从一个地址迁移到另一个地址必须通过反向映射找到所有映射了该页的页表项修改页表项的物理地址刷新TLB保证进程访问不受影响KSM同页合并内核同页合并机制KSM会把内容相同的匿名页合并为一个只读页减少内存占用必须通过反向映射找到所有映射了原页的页表项修改为指向合并后的页页错误处理处理页被换出swap、页被锁定等异常时需要通过反向映射找到对应的页表项修改页表项的状态。8.6 工程实践与认知纠正1.反向映射的内存开销认知很多工程师误以为反向映射会占用大量内存实际上文件页的反向映射元数据存储在文件的address_space中每个文件只需要一个区间树内存开销极小匿名页的反向映射anon_vma和anon_vma_chain的数量和VMA的数量成正比而不是和物理页的数量成正比哪怕系统中有几十GB的内存反向映射的元数据开销也只有几MB完全可以忽略内核做了大量的优化比如anon_vma的复用、红黑树的高效管理最小化内存开销。2.反向映射的性能优化反向映射的遍历是内存回收、页迁移的核心开销内核做了大量的性能优化用Maple Tree替换了传统的优先级搜索树区间查询的性能提升了30%以上反向映射的遍历采用RCU机制读操作不需要加排他锁允许多个CPU并发遍历内存回收时优先回收只有一个映射的页_mapcount 0不需要遍历反向映射提升回收效率页迁移时优先迁移映射数量少的页减少反向映射的遍历开销。3.反向映射的调试与排查反向映射的异常会导致内核崩溃、内存泄漏、OOM等问题内核提供了相应的调试手段开启CONFIG_DEBUG_RMAP内核配置开启反向映射的调试检查检测非法的VMA链接、引用计数泄漏等问题用/proc/pid/maps查看进程的VMA确认匿名VMA的anon_vma是否正常用crash工具分析内核coredump查看anon_vma的红黑树、VMA的链表定位反向映射的异常。4.认知纠正匿名页的共享范围很多工程师误以为匿名页是进程私有的实际上通过fork()匿名页会被父子进程共享直到触发COW反向映射机制就是为了处理这种共享场景。如果没有反向映射fork()之后的COW完全无法实现这也是反向映射机制最核心的设计目标。
