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

加了一个pte chain的成员，以便把所有mapping到该page的pte entry指针给串起来。这样想要unmap一个page就易如反掌了，沿着这个pte chain就可以找到所有的mappings。一个基本的示意图如下，下面的小节会给出更详细的解释。

2、对Struct page的修改

Struct page的修改如下：

struct page {

……

        union {

                 struct pte_chain *chain;

                 pte_addr_t direct;

        } pte;

……

当然，很多页面都不是共享的，只有一个pte entry，因此direct直接指向那个pte entry就OK了。如果存在页面共享的情况，那么chain成员则会指向一个struct pte_chain的链表。

3、定义struct pte_chain 

struct pte_chain {

        unsigned long next_and_idx;

        pte_addr_t ptes[NRPTE];

} ____cacheline_aligned;

如果pte_chain只保存一个pte entry的指针那么就太浪费了，比较好的方法是把struct pte_chain对齐在cache line并让整个struct pte_chain占用一个cache line。除了next_and_idx用于指向下一个pte_chain，形成链表之外，其余的空间都用于保存pte entry指针。由于pte entry指针形成了数组，因此我们还需要一个index指示下一个空闲的pte entry pointer的位置，由于pte_chain对齐在cache line，因此next_and_idx的LSB的若干个bit是等于0的，可以复用做index。

4、页面回收算法的修改

在进入基于rmap的页面回收算法之前，让我们先回忆一下痛苦的过去。假设一个物理页面P被A和B两个进程共享，在过去，释放P这个物理页面需要扫描进程地址空间，首先scan到A进程，解除P和A进程的关系，但是这时候不能回收，B进程还在使用该page frame。当然扫描过程最终会来到B进程，只有在这时候才有机会回收这个物理页面P。你可能会问：如果scan B进程地址空间的时候，A进程又访问了P从而导致映射建立。然后scan A的时候，B进程又再次访问，如此反反复复，那么P不就永远无法回收了吗？这个怎么办呢？这个……理论上是这样的，别问我，其实我也很绝望。

有了rmap，页面回收算法顿时感觉轻松多了，只要是页面回收算法看中的page frame，总是能够通过try_to_unmap解除和所有进程的关联，从而将其回收到伙伴系统中。如果该page frame没有共享（page flag设定PG_direct flag），那么page->pte.direct直接命中pte entry，调用try_to_unmap_one来进行unmap的操作。如果映射到了多个虚拟地址空间，那么沿着pte_chain依次调用try_to_unmap_one来进行unmap的操作。

五、女娲补天

虽然Rik van Riel开辟了逆向映射的新天地，但是，天和地都有着巨大的窟窿，需要有人修补。首先让我们看看这个"巨大的窟窿"是什么？

在引入第一个版本的rmap之后，Linux的页面回收变得简单、可控了，但是这个简单的设计是有代价的：每一个struct page增加一个指针成员，在32bit的系统上也就是增加了4B。考虑到系统为了管理内存会为每一个page frame建立一个struct page对象，引入rmap而导致的内存开销也不是一个小数目啊。此外，share page需要建立pte_chain链表，也是一个不小的内存开销。除了内存方面的压力，第一个版本的rmap对性能也造成了一定的影响。例如：在fork操作的时候，父子进程共享了很多的page frame，这样，在copy page table的时候就会伴随大量的pte_chain的操作，从而让fork的速度变得缓慢。

本章就是带领大家看看object-based reverse mapping（后文简称objrmap）是如何填补那个"巨大的窟窿"。本章的代码来自2.6.11版本的内核。

1、问题的引入

推动rmap优化的动力来自内存方面的压力，与此相关的问题是：32-bit的Linux内核是否支持4G以上的memory。在1999年，Linus的决定是：32-bit的Linux内核永远也不会支持2G以上的内存。不过历史的洪流不可阻挡，处理器厂商设计了扩展模块以便寻址更多的内存，高端的服务器也配置了越来越多的内存。这也迫使Linus改变之前的思路，让Linux内核支持更大的内存。

红帽公司的Andrea Arcangeli当时正在做的工作就是让32-