从史前文明到女娲补天：Linux内存逆向映射（reverse mapping）技术的前世今生

ry mapping和swapping机制的支持。这两种机制的工作原理类似，只不过一个用于file mapped page，另外一个用于anonymous page。不过对于页面回收而言，他们的工作原理类似：就是把某些进程不常使用的page frame交换到磁盘上去，同时解除进程和这个page frame的一切关系，完成这两步之后，这个物理页帧已经自由了，可以回收到伙伴系统中。

OK，了解了基本原理，现在需要看看如何具体实现：不常使用的page frame很好找（inactive lru链表），不过断绝page frame和进程们之间的关系很难，因为没有逆向映射。不过这难不倒Linux内核开发人员，他们选择了扫描整个系统的各个进程的地址空间的方法。

2、如何对进程地址空间进行扫描？

下图是一个对进程地址空间进行扫描的示意图：

系统中的所有进程地址空间（memory descriptor）被串成一个链表，链表头就是init_mm，系统中所有的进程地址空间都挂在了这个链表中。所谓scan当然就是沿着这条mm链表进行了。当然，页面回收算法尽量不scan整个系统的全部进程地址空间，毕竟那是一个比较笨的办法。回收算法可以考虑收缩内存cache，也可以遍历inactive_list来试图完成本次reclaim数目的要求（该链表中有些page不和任何进程相关），如果通过这些方法释放了足够多的page frame，那么一切都搞定了，不需要scan进程地址空间。当然，情况并非总是那么美好，有时候，必须启动进程物理页面回收过程才能满足页面回收的要求。

进程物理页面回收过程是通过调用swap_out函数完成的，而scan进程地址空间的代码也是开始于这个函数。该函数是一个三层嵌套结构：

（1）首先沿着init_mm，对每一个进程地址空间进行扫描

（2）在扫描一个进程地址空间的时候，对属于该进程地址空间的每一个VMA进行扫描

（3）在扫描每一个VMA的时候，对属于该VMA的每一个page进行扫描

在扫描过程中，如果命中了进程A的page frame0，由于该page只是被进程A 使用（即只是被A进程mapping），那么可直接unmap并回收该page。对于共享页面，我们不能这么处理了，例如上图中的page frame 1，但scan A进程的时候，如果条件符合，那么我们会unmap该page，解除它和进程A的关系，当然，这时候不能回收该page，因为进程X还在使用该page。直到scan过程历经千山万水来到进程X，完成对page frame 1的unmaping操作，该物理页面才可以真正会伙伴系统的怀抱。

3、地址空间扫描的细节问题

首先，第一个问题：到底scan多少虚拟地址空间才停止scan呢？当目标已经达到的时候，例如本次scan打算reclaim 32个page frame，如果目标达到，那么scan停止，不需scan全部虚拟地址空间。还有一种比较悲惨的情况，那就是scan了系统中所有的地址空间之后，仍然没有达成目标，这时候也就可以停止了，不过这属于OOM的处理了。为了确保系统中的进程被均匀的scan（毕竟swap out会影响进程性能，我们肯定不能只逮住部分进程薅其羊毛），每次scan完成后，记录当前scan的位置（保存在swap_mm变量），等下次又启动scan过程的时候，从swap_mm开始继续scan。

由于对性能有影响，swap out需要雨露均沾，各个进程都跑不掉。同样的道理，对于一个进程的地址空间，我们一样也是需要公平对待，因此需要保存每次scan的虚拟地址（mm->swap_address），这样，每次重启scan的时候，总是从swap_mm那个地址空间的mm->swap_address虚拟地址开始scan。

具体对一个page frame进行swap out的代码位于try_to_swap_out函数中，在这个函数中，如果条件满足，会解除该page frame的该进程之间的关系，完成必要的IO操作，该page reference count减一，对应的pte清零或者设定swap entry等。当然，swap out一个page之后，我们并非一定能够回收它，因为这个page很可能被多个进程共享。而在scan过程中，如果碰巧找到了该page对应的所有的页面表条目，那么说明该页面已经不被任何进程引用，这时候该page frame就会被逐出磁盘，从而完成一个页面的回收。

四、开天辟地

时间又回到2002年1月，那时VM大神Rik van Riel遭遇了人生中的一次重大挫折，他的耗费心血维护的代码被一个全新的VM子系统取代了。不过Rik van Riel并没有消沉下去，他在憋大招，也就是传说中的reverse mapping（后文简称rmap）。本章主要描述第一个版本的rmap，代码来自Linux 2.6.0。

1、设计概念

如何构建rmap？最直观的想法就是针对每一个page frame，我们维护一个链表，保存属于该page的所有PTEs。因此，Rik van Riel给struct page增