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

当系统中的一个CPU在执行try_to_unmap_anon函数的时候，需要遍历VMA链表，这时会持有anon_vma->lock这个自旋锁。由于anon_vma存有了很多根本无关的VMA，通过，page table的检索过程，你就会发现这个VMA根本和准备unmap的page无关，因此只能scan下一个VMA，整个过程需要消耗大量的时间，延长了临界区（复杂度是O（N））。与此同时，其他CPU在试获取这把锁的时候，基本会被卡住，这时候整个系统的性能可想而知了。更加糟糕的是内核中并非只有unmap匿名页面的时候会上锁、遍历VMA链表，还有一些其他的场景也会这样（例如page_referenced函数）。想象一下，一百万个页面共享这一个anon_vma，对anon_vma->CPU在执行try_to_unmap_anon函数的时候，需要遍历VMA链表，这时会持有anon_vma->lock这个自旋锁。由于anon_vma存有了很多根本无关的VMA，通过，page table的检索过程，你就会发现这个VMA根本和准备unmap的page无关，因此只能scan下一个VMA，整个过程需要消耗大量的时间，延长了临界区（复杂度是O（N））。与此同时，其他CPU在试获取这把锁的时候，基本会被卡住，这时候整个系统的性能可想而知了。更加糟糕的是内核中并非只有unmap匿名页面的时候会上锁、遍历VMA链表，还有一些其他的场景也会这样（例如page_referenced函数）。想象一下，一百万个页面共享这一个anon_vma，对anon_vma->lock自旋锁的竞争那是相当的激烈埃

2、改进的方案

旧的方案的症结所在是anon_vma承载了太多进程的VMA了，如果能将其变成per-process的，那么问题就解决了。Rik van Riel的解决办法是为每一个进程创建一个anon_vma结构并通过各种数据结构把父子进程的anon_vma（后面简称AV）以及VMA链接在一起。为了链接anon_vma，内核引入了一个新的结构，称为anon_vma_chain（后面简称AVC）：

struct anon_vma_chain {

        struct vm_area_struct *vma;――指向该AVC对应的VMA

        struct anon_vma *anon_vma;――指向该AVC对应的AV

        struct list_head same_vma; ――链接入VMA链表的节点

        struct rb_node rb;―――链接入AV红黑树的节点

        unsigned long rb_subtree_last;

};

AVC是一个神奇的结构，每个AVC都有其对应的VMA和AV。所有指向相同VMA的AVC会被链接到一个链表中，链表头就是VMA的anon_vma_chain成员。而一个AV会管理若干的VMA，所有相关的VMA（其子进程或者孙进程）都挂入红黑树，根节点就是AV的rb_root成员。

这样的描述非常枯燥，估计第一次接触逆向映射的同学是不会明白的，不如我们一起来看看AV、AVC和VMA的"大厦"是如何搭建起来的。

3、当VMA和VA首次相遇

由于采用了COW技术，子进程和父进程的匿名页面往往是共享的，直到其中之一发起写操作。但是如果子进程执行了exec的系统调用，加载了自己的二进制image，这时候，子进程和父进程的执行环境（包括匿名页面）就分道扬镳了（参考flush_old_exec函数），我们的场景就是从这么一个全新的exec后的进程开始。当该进程的匿名映射VMA通过page fault分配第一个page frame的时候，内核会构建下图所示的数据关系：

上图中的AV0就是该进程的anon_vma，由于它是一个顶级结构，因此它的root和parent都是指向了自己。AV这个数据结构当然为了管理VMA了，不过新机制中，这是通过AVC进行中转的。上图中的AVC0搭建了该进程VMA和AV之间的桥梁，分别有指针指向了VMA0和AV0，此外，AVC0插入到AV的红黑树，同时也会插入到VMA的链表中。

对于这个新分配的page frame而言，它会mapping到VMA对应的某个虚拟地址上去，为了维护逆向映射的关系，struct page中的mapping指向了AV0，index成员指向了该page在整个VMA0中的偏移。图中没有画出这个关系，主要因为这是老生常谈了，相信大家都已经熟悉。

VMA0中随后可能会有若干的page frame被mapping到该VMA的某个虚拟页面，不过上面的结构不会变化，只不过每一个page中的mapping都指向了上图中的AV0。另外，上图中那个虚线绿色block的AVC0其实等于那个绿色实线的AVC0 block，也就是说这时候该VMA只有一个anon_vma_chain，即AVC0，上图只是方便表示该AVC也会被挂入VMA的链表，挂入anon_vma的红黑树而已。

如果想参考相关的代码可以仔细看看do_anonymous_page或者do_cow_fault。

4、在fork的时候，匿名映射的VMA经历了什么？

一旦fork，那么子进程会copy父进程的VMA（参考函数dup_mmap），子进程会有自己的VMA，同时也会分配自己的AV（旧的机制下，多个进程共享一个AV，而新的机制中，AV是per process的），然后建立父子进程之间的VMA、VA的"大厦"，主要的步骤如下：

（1）调用anon_vma_clone函数，建立子进程VMA和"父进程们"VA的关系

（2）建立子进程VMA和子进程VA的关系

怎样叫做建立VMA和VA的关系？其实就是anon_vma_chain_link函数的调用过程，步骤如下：

（1）分配一个AVC结构，成员指针指向对应的VMA和VA

（2）将该AVC加入VMA链表

（3）将该