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

bit的Linux运行在配置超过32G内存的公司服务器上。在这些服务器上往往启动大量的进程，共享了大量的物理页帧，消耗了大量的内存。对于Andrea Arcangeli来说，内存消耗的真正元凶是明确的：逆向映射模块，这个模块消耗了太多的low memory，从而导致了系统的各种crash。为了让自己的工作继续推进，他必须解决rmap引入的内存扩展性（memory scalability）问题。

2、file mapped的优化

并非只有Andrea Arcangeli关注到了rmap的内存问题，在2.5版本的开发过程中，IBM公司的Dave McCracken就已经提交了patch，试图在保证逆向映射功能的基础上，同时又能修正rmap带来的各种问题。

Dave McCracken的方案是一种基于对象的逆向映射机制。在过去，通过rmap，我们可以从struct page直接获取其对应的ptes，objrmap的方法借助其他的数据对象来完成从struct page检索到其对应ptes的过程，这个过程的示意图如下：

对于objrmap而言，寻找一个page frame的mappings是一个比较长的路径，它借助了VMA（struct vm_area_struct）这个数据对象。我们知道对于某些page frame是有后备文件的，这种类型的页面和某个文件相关，例如进程的正文段和该进程的可执行文件相关。此外，进程可以调用mmap()对某个文件进行mapping。对于这些页帧我们称之file mapped page。

对于这些文件映射页面，其struct page中有一个成员mapping指向一个struct address_space，address_space是和文件相关的，它保存了文件page cache相关的信息。当然，我们这个场景主要关注一个叫做i_mmap的成员。一个文件可能会被映射到多个进程的多个VMA中，所有的这些VMA都被挂入到i_mmap指向的Priority search tree中。

当然，我们最终的目标是PTEs，下面这幅图展示了如何从VMA和struct page中的信息导出该page frame的虚拟地址的：

而在linux kernel中，函数vma_address可以完成这个功能：

static inline unsigned long

vma_address(struct page *page, struct vm_area_struct *vma)

{

        pgoff_t pgoff = page->index < (PAGE_CACHE_SHIFT - PAGE_SHIFT);

        unsigned long address;

        address = vma->vm_start + ((pgoff - vma->vm_pgoff) < PAGE_SHIFT);

        return address;

}

对于file mapped page，page->index表示的是映射到文件内的偏移（Byte为单位），而vma->vm_pgoff表示的是该VMA映射到文件内的偏移（page为单位），因此，通过vma->vm_pgoff和page->index可以得到该page frame在VMA中的地址偏移，再加上vma->vm_start就可以得到该page frame的虚拟地址。有了虚拟地址和地址空间（vma->vm_mm），我们就可以通过各级页表找到该page对应的pte entry。

3、匿名页面的优化

我们都知道，用户空间进程的页面主要有两种，一种是file mapped page，另外一种是anonymous mapped page。Dave McCracken的objrmap方案虽好，但是只是适用于file mapped page，对于匿名映射页面，这个方案无能为力。因此，我们必须为匿名映射页面也设计一种基于对象的逆向映射机制，最后形成full objrmap方案。

为了解决内存扩展性的问题，Andrea Arcangeli全力工作在full objrmap方案上，不过他还有一个竞争对手，Hugh Dickins，同时也提交了一系列full objrmap补丁，试图并入内核主线，显然，在匿名映射页面上，最后胜出的是Andrea Arcangeli，他的匿名映射方案如下图所示：

和file mapped类似，anonymous page也是通过VMA来寻找page frame对应的pte entry。由于文件映射页面的VMA数量可能非常大，因此我们采用Priority search tree这样的数据结构。对于匿名映射页面，其数量一般不会太大，所以使用链表结构就OK了。

为了节省内存，我们复用了struct page中的mapping指针：一个page frame如果是file mapped，其mapping指针指向对应文件的address_space数据结构。如果是anonymous page，那么mapping指针指向anon_vma数据结构。虽然节省了内存，但是降低了可读性，但是由于内核会为每一个page frame建立一个对应的struct page数据对象，该数据结构即便是增加4B对整个系统的内存消耗都是巨大的，因此内核还是采用了较为丑陋的方式来定义mapping这个成员。通过struct page中的mapping成员我们可以获得该page映射相关的信息