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

AVC加入VA红黑树

我们一开始先别把事情搞得太复杂，先看看一个全新进程fork子进程的场景。这时候，内核会构建下图所示的数据关系：

首先看看如何建立子进程VMA1和父进程AV0的关系，这里需要遍历VMA0的anon_vma_chain链表，当然现在这个链表只有一个AVC0（link到AV0），为了建立和父进程的联系，我们分配了AVC_x01，它是一个桥梁，连接了父子进程。（注：AVC_x01中的x表示连接，01表示连接level 0和level 1）。通过这个桥梁，父进程可以找到子进程的VMA（因为AVC_x01插入AV0的红黑树中），而子进程也可以找到父进程的AV（因为AVC_x01插入VMA1的链表中）。

当然，自己的anon_vma也需要创建。在上图中，AV1就是子进程的anon_vma，同时分配一个AVC1来连接该子进程的VMA1和AV1，并调用anon_vma_chain_link函数将AVC1插入VMA1的链表和AV1的红黑树中。

父进程也会创建其他新的子进程，新创建的子进程的层次和VMA1、VA1的类似，这里就不描述了。不过需要注意的是：父进程每创建一个子进程，AV0的红黑树中会增加每一个起"桥梁"作用的AVC，以此连接到子进程的VMA。

5、构建三层大厦

上一节描述了父进程创建子进程的情况，如果子进程再次fork，那么整个VMA-VA的大厦将形成三层结构，具体如下图所示：

当然，首先要进行的仍然是建立孙进程VMA和"父进程们"VA的关系，这里的"父进程们"其实是泛指孙进程的上层的那些进程们。对于这个场景，"父进程们"指的就是上图中的A进程和B进程。如何建立？在fork的时候，我们进行VMA的拷贝：即分配VMA2并以VMA1为原型copy到VMA2中。Copy是沿着VMA1的AVC链表进行的，该链表有两个元素：AVC1和 AVC_x01，分别和父进程A和子进程B的AV关联。因此，在孙进程C中，我们会分配AVC_x02和AVC_x12两个AVC，并建立level 2层和level 0层以及level 1层之间的关系。

同样的，自己level的anon_vma也需要创建。在上图中，AV2就是孙进程C的anon_vma，同时分配一个AVC2来连接该孙进程的VMA2和AV2，并调用anon_vma_chain_link函数将AVC2插入VMA2的链表和AV2的红黑树中。

AV2中的root指向root AV，也就是进程A的AV。Parent成员指向其B进程（C的父进程）的AV。通过Parent这样的指针，不同level的AV建立了父子关系，而通过root指针，每一个level的AV都可以寻找找到root AV。

6、page frame是如何加入"大厦"中？

前面几个小节重点讨论了hierarchy AV的结构是如何搭建起来的，也就是描述fork的过程中，父子进程的VMA、AVC和AV是如何联系的。本小节我们将一起来看看父子进程之一访问页面，发生了page fault的处理过程。这个处理过程有两个场景，一个是父子进程都没有page frame，这时候，内核代码会调用do_anonymous_page分配page frame并调用page_add_new_anon_rmap函数建立该page和对应VMA的关系。第二个场景复杂一点，是父子共享匿名页面的场景，当发生write fault的时候，也是分配page frame并调用page_add_new_anon_rmap函数建立该page和对应VMA的关系，具体代码位于do_wp_page函数。无论哪一个场景，最终都是将该page的mapping成员指向了该进程所属的AV结构。

7、为何建立如此复杂的"大厦"？

如果你能坚持读到这里，那么说明你对枯燥文字的忍受能力还是很强的，哈哈。Page、VMA、VAC、VA组成了如此复杂的层次结构到底是为什么呢？是为了打击你学习内核的兴趣吗？非也，让我们还是用一个实际的场景来说明这个"大厦"的功能。

我们通过下面的步骤建立起上图的结构：

（1）P进程的某个VMA中有两类页面： 一类是有真实的物理页面的，另外一类是还没有配备物理页面的。上图中，我们分别跟踪有物理页面的A以及还没有分配物理页面的B。

（2）P进程fork了P1和P2

（3）P1进程fork了P12进程

（4）P1进程访问了A页面，分配了page frame2

（5）P12进程访问了B页面，分配了page frame3

（6）P2进程访问了B页面，分配了page frame1

（7）P2进程fork了P21进程

经过上面的这一些动作之后，我们来看看page frame共享的情况：对于P进程的page frame（是指该page 的mapping成员指向P进程的AV，即上图中的AV_P）而言，他可能会被任何一个level的的子进程VMA中的page所有共享，因此AV_P需要包括其子进程、孙进程……的所有的VMA。而对于P1进程而言，AV_P1则需要包括P1子进程、孙进程……的所有的VMA，有一点可以确认：至少父进程P和兄弟进程P2的VMA不需要包括在其中。

现在我们回头看看AV结构的大厦，实际上是