前文介绍过，在回收一个物理页面之前，需要查找到所有关联了该物理页面的页表项，并逐一更新这些页表项。Linux 2.6 使用了反向映射这种机制用于快速定位那些引用了某个物理页面的所有页表项。Linux 操作系统为物理页面建立一个链表，用于指向引用了该物理页面的所有页表项。其基本思想如下图所述：
图 4. 反向映射的基本思想
在 Linux 2.4 中，为了确定某个要回收的物理页面都被哪些页表项引用，必须要遍历所有进程，这是一项非常耗资源和时间的工程。为了更加有效地回收一个共享页面，Linux 在 2.5 版本的开发期间引入了反向映射这样一种机制。这种机制建立了物理页面和所有映射了该物理页面的页表项之间的一种关联，从而让操作系统可以快速定位引用了该物理页面的所有页表项。在 Linux 2.6 版本中，反向映射算法又经历了大量改进。
在 Linux 2.5 版本中，反向映射技术的实现主要是基于页表项链表。操作系统为每一个物理页面都维护了一个链表，所有与该物理页面关联的页表项都会被放到这个链表上。这种方法会存在一些问题：
空间资源的消耗：为每个物理页面维护这样一个链表，需要占用大量的内存空间。 时间资源的消耗：回收一个物理页面的时候，需要先获取该链表上的锁，然后遍历相应的反向映射链表，链表上的项越多，需要的时间就越多。后来，Linux 2.6 引入了基于对象的反向映射机制。这种方法也是为物理页面设置一个用于反向映射的链表，但是链表上的节点并不是引用了该物理页面的所有页表项，而是相应的虚拟内存区域（ vm_area_struct 结构），虚拟内存区域通过内存描述符（ mm_struct 结构）找到页全局目录，从而找到相应的页表项。相对于前一种方法来说，用于表示虚拟内存区域的描述符比用于表示页面的描述符要少得多，所以遍历后边这种反向映射链表所消耗的时间也会少很多。
数据结构
page 结构中与基于对象的反向映射相关的关键字段有两个：_mapcount 和 mapping。
struct page { atomic_t _mapcount; union { …… struct { …… struct address_space *mapping; }; …… };字段 _mapcount 表明共享该物理页面的页表项的数目。该计数器可用于快速检查该页面除所有者之外有多少个使用者在使用，初始值是 -1，每增加一个使用者，该计数器加 1。 字段 mapping 用于区分匿名页面和基于文件映射的页面，如果该字段的最低位被置位了，那么该字段包含的是指向 anon_vma 结构（用于匿名页面）的指针；否则，该字段包含指向 address_space 结构的指针（用于基于文件映射的页面）。
匿名页面和文件映射页面分别采用了不同的底层数据结构去存放与页面相关的虚拟内存区域。对于匿名页面来说，与该页面相关的虚拟内存区域存放在结构 anon_vma 中定义的双向链表中。结构 anon_vma 定义很简单，如下所示：
struct anon_vma { spinlock_t lock; struct list_head head; };而对于基于文件映射的页面来说，与匿名页面不同的是，与该页面相关的虚拟内存区域的存放是利用了优先级搜索树这种数据结构的。这是因为对于匿名页面来说，页面虽然可以是共享的，但是一般情况下，共享匿名页面的使用者的数目不会很多；而对于基于文件映射的页面来说，共享页面的使用者的数目可能会非常多，使用优先级搜索树这种结构可以更加快速地定位那些引用了该页面的虚拟内存区域。操作系统会为每一个文件都建立一个优先级搜索树，其根节点可以通过结构 address_space 中的 i_mmap 字段获取。
struct address_space { …… struct prio_tree_root i_mmap; …… }Linux 2.6 中使用 (radix,size,heap) 来表示优先级搜索树中的节点。其中，radix 表示内存区域的起始位置，heap 表示内存区域的结束位置，size 与内存区域的大小成正比。在优先级搜索树中，父节点的 heap 值一定不会小于子节点的 heap 值。在树中进行查找时，根据节点的 radix 值进行。程序可以根据 size 值区分那些具有相同 radix 值的节点。
在用于表示虚拟内存区域的结构 vm_area_struct 中，与上边介绍的双向链表和优先级搜索树相关的字段如下所示：
struct vm_area_struct { struct mm_struct * vm_mm; …… union { struct { struct list_head list; void *parent; struct vm_area_struct *head; } vm_set; struct raw_prio_tree_node prio_tree_node; } shared; struct list_head anon_vma_node; struct anon_vma *anon_vma; };与匿名页面的双向链表相关的字段是 anon_vma_node 和 anon_vma。union shared 则与文件映射页面使用的优先级搜索树相关。字段 anon_vma 指向 anon_vma 表；字段 anon_vma_node 将映射该页面的所有虚拟内存区域链接起来；union shared 中的 prio_tree_node 结构用于表示优先级搜索树的一个节点；在某些情况下，比如不同的进程的内存区域可能映射到了同一个文件的相同部分，也就是说这些内存区域具有相同的（radix,size,heap）值，这个时候 Linux 就会在树上相应的节点（树上原来那个具有相同 （radix,size,heap） 值的内存区域）上接一个双向链表用来存放这些内存区域，这个链表用 vm_set.list 来表示；树上那个节点指向的链表中的第一个节点是表头，用 vm_set.head 表示；vm_set.parent 用于表示是否是树结点。下边给出一个小图示简单说明一下 vm_set.list 和 vm_set.head。
图 5. vm_set.list 和 vm_set.head
通过结构 vm_area_struct 中的 vm_mm 字段可以找到对应的 mm_struct 结构，在该结构中找到页全局目录，从而定位所有相关的页表项。
使用反向映射
在进行页面回收的时候，Linux 2.6 在前边介绍的 shrink_page_list() 函数中调用 try_to_unmap() 函数去更新所有引用了回收页面的页表项。其代码流程如下所示：
图 6. 实现函数 try_to_unmap() 的关键代码流程图
函数 try_to_unmap() 分别调用了两个函数 try_to_unmap_anon() 和 try_to_unmap_file()，其目的都是检查并确定都有哪些页表项引用了同一个物理页面，但是，由于匿名页面和文件映射页面分别采用了不同的数据结构，所以二者采用了不同的方法。
函数 try_to_unmap_anon() 用于匿名页面，该函数扫描相应的 anon_vma 表中包含的所有内存区域，并对这些内存区域分别调用 try_to_unmap_one() 函数。
函数 try_to_unmap_file() 用于文件映射页面，该函数会在优先级搜索树中进行搜索，并为每一个搜索到的内存区域调用 try_to_unmap_one() 函数。
两条代码路径最终汇合到 try_to_unmap_one() 函数中，更新引用特定物理页面的所有页表项的操作都是在这个函数中实现的。该函数实现的关键功能如下图所示：
图 7. 函数 try_to_unmap_one() 实现的关键功能
对于给定的物理页面来说，该函数会根据计算出来的线性地址找到对应的页表项地址，并更新页表项。对于匿名页面来说，换出的位置必须要被保存下来，以便于该页面下次被访问的时候可以被换进来。并非所有的页面都是可以被回收的，比如被 mlock() 函数设置过的内存页，或者最近刚被访问过的页面，等等，都是不可以被回收的。一旦遇上这样的页面，该函数会直接跳出执行并返回错误代码。如果涉及到页缓存中的数据，需要设置页缓存中的数据无效，必要的时候还要置位页面标识符以进行数据回写。该函数还会更新相应的一些页面使用计数器，比如前边提到的 _mapcount 字段，还会相应地更新进程拥有的物理页面数目等。
使用反向映射的优缺点
使用反向映射机制所带来的好处是显而易见的：可以快速定为引用了某个物理页面的所有页表项，这极大地方便了操作系统进行页面回收。相对于之前的遍历方法来说，反向映射机制在很大程度上减少了操作系统在页面回收上所占用的 CPU 时间。
但是，使用反向映射所面临的挑战也是很明显的，不管采用上述介绍的哪种方法建立反向映射，都不可避免地要消耗掉一定的内存空间，区别就在于用哪种方法占用的空间会更少，整体性能会更好。
页面回收是 Linux 内存管理中比较复杂的一个部分，涉及到的相关内容非常多，本文也不是面面俱到。反向映射是 Linux 2.5 开发过程中一个比较大的亮点，该技术在后续 Linux 2.6 版本中又��到了更进一步的发展。本文的目的是想帮助读者理清 Linux 2.6 中的页面回收和反向映射机制，本文通过相关的数据结构和关键的代码流程介绍了 Linux 操作系统如何利用反向映射机制有效地进行页面回收。关于 Linux 操作系统如何建立反向映射的内容，本文没有做详尽介绍，感兴趣的读者可以自行参考内核源代码。