199
Cheetah，曾为 U-boot 社区和 Linux 内核社区提交过若干补丁，主要从事 Linux 相关系统软件开发工作，负责 Soc 芯片 BringUp 及系统软件开发，喜欢阅读内核源代码，在不断的学习和工作中深入理解内存管理，进程调度，文件系统，设备驱动等内核子系统。
为了系统的安全性，Linux 内核将各个用户进程运行在各自独立的虚拟地址空间，用户进程之间通过虚拟地址空间相互隔离，不能相互访问，一个进程的奔溃不会影响到整个系统的异常也不会干扰到系统以及其他进程运行。
Linux 内核可以通过共享内存的方式为系统节省大量内存，例如 fork 子进程的时候，父子进程通过只读的方式共享所有的私有页面。再比如通过 IPC 共享内存方式，各个不相干的进程直接可以共享一块物理内存等等。
我们都知道操作系统开启 mmu 之后 cpu 访问到的都是虚拟地址，当 cpu 访问一个虚拟地址的时候需要通过 mmu 将虚拟地址转化为物理地址，这叫做正向映射。而与本文相关的是反向映射，它主要是通过物理页来找到共享这个页的所有的 vma 对应的页表项，这是本文讨论的问题。
本文目录：
1. 反向映射的发展
2. 反向映射应用场景
3. 匿名页的反向映射
4. 文件页的反向映射
5.ksm 页的反向映射
5. 总结
注：反向映射机制是 Linux 内核虚拟内存管理的难点也是理解内存管理的关键技术之一！！
1. 反向映射的发展
实际上在早期的 Linux 内核版本中是没有反向映射的这个概念的，那个时候为了找到一个物理页面对应的页表项就需要遍历系统中所有的 mm 组成的链表，然后对于每一个 mm 再遍历每一个 vma，然后查看这个 vma 是否映射了这页，这个过程极其漫长而低效，有的时候不得不遍历完所有的 mm 然后才能找映射到这个页的所有 pte。
后来人们发现了这个问题，就再描述物理页面的 page 结构体中增加一个指针的方式来解决，通过这个指针来找到一个描述映射这个页的所有 pte 的数组结构，这对于反向映射查找所有 pte 易如反掌，但是带来的是浪费内存的问题。
接着就在 2.6 内核的时候，内核大神们想到了复用 page 结构中的 mapping 字段，然后通过红黑树的方式来组织所有映射这个页的 vma,形成了匿名页和文件页的反向映射机制。
如下为匿名页反向映射图解：
如下为文件页反向映射图解：
但是后来匿名页的反向映射遇到了效率和锁竞争激烈问题，就促使了目前使用的通过 avc 的方式联系各层级反向映射结构然后将锁的粒度降低的这种方式。可以看到反向映射的发展是伴随着 Linux 内核的发展而发展，是一个不断进行优化演进的过程。
2. 反向映射应用场景
那么为何在 Linux 内核中需要反向映射这种机制呢？它究竟为了解决什么样的问题而产生的呢？
试想有如下场景：
（1）一个物理页面被多个进程的 vma 所映射，系统过程中发生了内存不足，需要回收一些页面，正好发现这个页面是适合我们回收利用的，我们能够直接把这个页面还给伙伴系统吗？答案肯定是不能。因为这个页面被很多个进程所共享，我们必须做的事情就是断开这个页面的所以映射关系，这就是反向映射所做的事情。
（2）一些情况我们需要将一个页面迁移到另一个页面，但是牵一发而动全身，可能有一些进程已经映射这个即将要迁移的页面到自己的 vma 中，那么这个时候同样需要我们知道究竟这个页面被哪些 vma 所映射呢？这同样是反向映射所做的事情。
实际上，反向映射的主要应用场景为内存回收和页面迁移，当系统发生内存回收和页面迁移的时候，对于每一个候选页 Linux 内核都会判断是否为映射页，如果是，就会调用 try_to_unmap 来解除页表映射关系，本文也主要来从 try_to_unmap 函数来解读反向映射机制。
如果我们在细致到其他的内核子系统会发现，在内存回收，内存碎片整理，CMA, 巨型页，页迁移等各个场景中都能发现反向映射所做的关键性的工作，所有理解反向映射机制在 Linux 内核中的实现是理解掌握这些子系统的基础和关键性所在，否则你即将不能理解这些技术背后的脊髓所在，所以说理解反向映射这种机制对于理解 Linux 内核内存管理是至关重要的！！！
3. 匿名页的反向映射
匿名页的共享主要发生在父进程 fork 子进程的时候，父 fork 子进程时，会复制所有 vma 给子进程，并通过调用 dup_mmap->anon_vma_fork 建立子进程的 rmap 以及和长辈进程 rmap 关系结构：
主要通过 anon_vma 这个数据结构体中的红黑树将共享父进程的页的所有子进程的 vma 联系起来（通过 anon_vma_chain 来联系对应的 vma 和 av），当然这个关系建立比较复杂，涉及到 vma,avc 和 av 这些数据结构体。.
而在缺页异常 do_anonymous_page 的时候将 page 和 vma 相关联。
当内存回收或页面迁移的时候，内核路径最终会调用到：
try_to_unmap //mm/rmap.c
->rmap_walk
->rmap_walk_anon
->anon_vma_interval_tree_foreach(avc, &anon_vma->rb_root,pgoff_start, pgoff_end)
->rwc->rmap_one
->try_to_unmap_one
对于候选页，会拿到候选页相关联的 anon_vma，然后从 anon_vma 的红黑树中遍历到所有共享这个页的 vma，然后对于每一个 vma 通过 try_to_unmap_one 来处理相对应的页表项，将映射关系解除。
4. 文件页的反向映射
文件页的共享主要发生在多个进程共享 libc 库，同一个库文件可以只需要读取到 page cache 一次，然后通过各个进程的页表映射到各个进程的 vma 中。
管理共享文件页的所以 vma 是通过 address_space 的区间树来管理，在 mmap 或者 fork 的时候将 vma 加入到这颗区间树中：
发生文件映射缺页异常的时候，将 page 和 address_space 相关联。
当内存回收或页面迁移的时候，内核路径最终会调用到：
try_to_unmap //mm/rmap.c
->rmap_walk
->rmap_walk_file
->vma_interval_tree_foreach(vma, &mapping>i_mmap,pgoff_start, pgoff_end)
->rwc->rmap_one
对于每一个候选的文件页，如果是映射页，就会遍历 page 所对应的 address_space 的区间树，对于每一个满足条件的 vma，调用 try_to_unmap_one 来找到 pte 并解除映射关系。
5.ksm 页的反向映射
ksm 机制是内核将页面内容完全相同的页面进行合并（ksm 管理的都是匿名页），将映射到这个页面的页表项标记为只读，然后释放掉原来的页表，来达到节省大量内存的目的，这对于 host 中开多个虚拟机的应用场景非常有用。
ksm 机制中会管理两课红黑树，一棵是 stable tree,一棵是 unstable tree，stable tree 中的每个节点 stable_node 中管理的页面都是页面内容完全相同的页面（被叫做 kpage）,共享 kpage 的页面的页表项都会标记为只读，而且对于原来的候选页都会有 rmap_item 来描述他的反向映射（其中的 anon_vma 成员的红黑树是描述映射这个候选页的所有 vma 的集合），合并的时候会加入到对应的 stable tree 节点和链表中。
当内存回收或页面迁移的时候，内核路径最终会调用到：
try_to_unmap //mm/rmap.c
->rmap_walk
->rmap_walk_ksm //mm/ksm.c
-> hlist_for_each_entry(rmap_item, &stable_node->hlist, hlist)
->anon_vma_interval_tree_foreach(vmac, &anon_vma->rb_root,0, ULONG_MAX)
->rwc->rmap_one
对于一个 ksm 页面，反向映射的时候，会拿到 ksm 页面对应的节点，然后遍历节点的 hlist 链表，拿到每一个 anon_vma，然后就和上面介绍的匿名页的反向映射一样了，从 anon_vma 的红黑树中找到所有的 vma，最后 try_to_unmap_one 来找到 pte 并解除映射关系。
6. 总结
前面我们介绍了反向映射的三种类型，匿名页，文件页和 ksm 页的反向映射,分别通过 page 所对应的的 vma, address_space, stable_node 结构来查找 vma。当然我们只是介绍了 Linux 内核中的反向映射的冰山一角，主要是 try_to_unmap 函数，其实每种反向映射各个数据结构建立的过程错综复杂，一篇文章三言两语也说不清楚，他们散落在 Linux 内核源代码的进程创建 fork，内存映射 mmap,缺页异常处理，文件系统等各个角落。
诚然，如果我们搞不清楚各种反正映射所对应的各种数据结构之间的关系，或者只是有一些概念上的了解，并没有真正掌握这种机制的实现原理，对于我们来理解 Linux 内核虚拟内存管理来说是一种障碍，不懂得反向映射，内存管理中的很多问题是搞不明白的！
