前言

逆向映射是指在已知page frame的情况下（可能是PFN、可能是指向page descriptor的指针，也可能是物理地址，内核有各种宏定义用于在它们之间进行转换），找到映射到该物理页面的虚拟页面们。由于一个page frame可以在多个进程之间共享，因此逆向映射的任务是把分散在各个进程地址空间中的所有的page table entry全部找出来。之所以建立逆向映射机制主要是为了方便页面回收。

文件页的反向映射

对于文件映射页面，其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)
{
	unsigned long address;
    pgoff_t pgoff = page->index;
    address = vma->vm_start + ((pgoff - vma->vm_pgoff) << PAGE_SHIFT);
    return address;
}

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

i_mmap指向的Priority search tree类似如下，每个节点包含了vma的起始、大小和结束信息。

文件页查找过程可以参考rmap_walk_file函数实现：

2338  * Find all the mappings of a page using the mapping pointer and the vma chains
2339  * contained in the address_space struct it points to.
2340  *
2341  * When called from page_mlock(), the mmap_lock of the mm containing the vma
2342  * where the page was found will be held for write.  So, we won't recheck
2343  * vm_flags for that VMA.  That should be OK, because that vma shouldn't be
2344  * LOCKED.
2345  */
2346 static void rmap_walk_file(struct page *page, struct rmap_walk_control *rwc,
2347         bool locked)
2348 {
2349     struct address_space *mapping = page_mapping(page);
2350     pgoff_t pgoff_start, pgoff_end;
2351     struct vm_area_struct *vma;
2352 
2353     /* 
2354      * The page lock not only makes sure that page->mapping cannot
2355      * suddenly be NULLified by truncation, it makes sure that the
2356      * structure at mapping cannot be freed and reused yet,
2357      * so we can safely take mapping->i_mmap_rwsem.
2358      */
2359     VM_BUG_ON_PAGE(!PageLocked(page), page);
2360                     
2361     if (!mapping)
2362         return;   
2363 
2364     pgoff_start = page_to_pgoff(page);
2365     pgoff_end = pgoff_start + thp_nr_pages(page) - 1;
2366     if (!locked)
2367         i_mmap_lock_read(mapping);
2368     vma_interval_tree_foreach(vma, &mapping->i_mmap,
2369             pgoff_start, pgoff_end) {
2370         unsigned long address = vma_address(page, vma);
2371 
2372         VM_BUG_ON_VMA(address == -EFAULT, vma);
2373         cond_resched();
2374 
2375         if (rwc->invalid_vma && rwc->invalid_vma(vma, rwc->arg))
2376             continue; 
2377 
2378         if (!rwc->rmap_one(page, vma, address, rwc->arg))
2379             goto done;
2380         if (rwc->done && rwc->done(page))
2381             goto done;
2382     }
2383     
2384 done:
2385     if (!locked)
2386         i_mmap_unlock_read(mapping);
2387 }

匿名页的反向映射

和file mapped类似，anonymous page也是通过VMA来寻找page frame对应的pte entry。
为了节省内存，我们复用了struct page中的mapping指针：一个page frame如果是file mapped，其mapping指针指向对应文件的address_space数据结构。如果是anonymous page，那么mapping指针指向anon_vma数据结构。
通过struct page中的mapping成员我们可以获得该page映射相关的信息，总结如下：
（1） 等于NULL，表示该page frame不再内存中，而是被swap out到磁盘去了。

（2） 如果不等于NULL，并且least signification bit等于1，表示该page frame是匿名映射页面，mapping指向了一个anon_vma的数据结构。

（3） 如果不等于NULL，并且least signification bit等于0，表示该page frame是文件映射页面，mapping指向了一个该文件的address_space数据结构。

通过anon_vma数据结构，我们可以得到映射到该page的所有的VMA，至此，匿名映射和file mapped汇合，进一步解决的问题仅仅是如何从VMA到pte entry而已。

linux为每一个进程创建一个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的“大厦”搭建过程如下

当VMA和VA首次相遇

当该进程的匿名映射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。

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

一旦fork，那么子进程会copy父进程的VMA（参考函数dup_mmap），子进程会有自己的VMA，同时也会分配自己的AV，然后建立父子进程之间的VMA、VA的“大厦”，主要的步骤如下：
（1） 调用anon_vma_clone函数，建立子进程VMA和“父进程们”VA的关系

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

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

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

• 将该AVC加入VMA链表

• 将该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。

构建三层大厦

上一节描述了父进程创建子进程的情况，如果子进程再次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。

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结构。

为何建立如此复杂的“大厦”？

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不需要包括在其中。

页面回收的时候，如何unmap一个page frame的所有的映射？

搭建了那么复杂的数据结构大厦就是为了应用，我们一起看看页面回收的场景。这个场景需要通过page frame找到所有映射到该物理页面的VMAs。有了前面的铺垫，这并不复杂，通过struct page中的mapping成员可以找到该page对应的AV，在该AV的红黑树中，包含了所有的可能共享匿名页面的VMAs。遍历该红黑树，对每一个VMA调用try_to_unmap_one函数就可以解除该物理页帧的所有映射。
每一个进程都有自己特有的anon_vma对象，每一个进程的page都指向自己特有的anon_vma对象。这大大降低了临界区的长度。
文件页查找过程可以参考rmap_walk_anon函数实现：

2279 /*
2280  * rmap_walk_anon - do something to anonymous page using the object-based
2281  * rmap method
2282  * @page: the page to be handled
2283  * @rwc: control variable according to each walk type
2284  *
2285  * Find all the mappings of a page using the mapping pointer and the vma chains
2286  * contained in the anon_vma struct it points to.
2287  *
2288  * When called from page_mlock(), the mmap_lock of the mm containing the vma
2289  * where the page was found will be held for write.  So, we won't recheck
2290  * vm_flags for that VMA.  That should be OK, because that vma shouldn't be
2291  * LOCKED.
2292  */
2293 static void rmap_walk_anon(struct page *page, struct rmap_walk_control *rwc,
2294         bool locked)
2295 {
2296     struct anon_vma *anon_vma;
2297     pgoff_t pgoff_start, pgoff_end;
2298     struct anon_vma_chain *avc;
2299 
2300     if (locked) {
2301         anon_vma = page_anon_vma(page);
2302         /* anon_vma disappear under us? */
2303         VM_BUG_ON_PAGE(!anon_vma, page);
2304     } else {
2305         anon_vma = rmap_walk_anon_lock(page, rwc);
2306     }
2307     if (!anon_vma)
2308         return;
2309             
2310     pgoff_start = page_to_pgoff(page);
2311     pgoff_end = pgoff_start + thp_nr_pages(page) - 1;
2312     anon_vma_interval_tree_foreach(avc, &anon_vma->rb_root,
2313             pgoff_start, pgoff_end) {
2314         struct vm_area_struct *vma = avc->vma;
2315         unsigned long address = vma_address(page, vma);
2316 
2317         VM_BUG_ON_VMA(address == -EFAULT, vma);
2318         cond_resched();
2319 
2320         if (rwc->invalid_vma && rwc->invalid_vma(vma, rwc->arg))
2321             continue;
2322 
2323         if (!rwc->rmap_one(page, vma, address, rwc->arg))
2324             break;
2325         if (rwc->done && rwc->done(page))
2326             break;
2327     }
2328 
2329     if (!locked)
2330         anon_vma_unlock_read(anon_vma);
2331 }

参考: 郭健： Linux内存逆向映射（reverse mapping）技术的前世今生