1、为什么要使用反向映射

物理内存的分页机制，一个PTE（Page Table Entry）对应一个物理页，但一个物理页可以由多个PTE与之相对应，当该页要被回收时，Linux2.4的做法是遍历每个进程的所有PTE判断该PTE是否与该页建立了映射，如果建立则取消该映射，最后无PTE与该相关联后才回收该页。该方法显而易见效率极低，因为其为了查找某个页的关联PTE遍历了所有的PTE，我们不禁想：如果把每个页关联的PTE保存在页结构里面，每次只需要访问那些与之相关联的PTE不很方便吗？确实，2.4之后确实采用过此方法，为每个页结构（Page）维护一个链表，这样确实节省了时间，但此链表所占用的空间及维护此链表的代价很大，在2.6中弃之不用，但反向映射机制的思想不过如此，所以还是有参考价值的，

2.6内核新引入的反向映射

• 反向映射是2.6内核中新引入的一个机制，主要是为了加速页面置换的时候的效率，由于内核中的页面是不区分进程的，多个进程很有可能会共享一个页面，内核只管每个页面必须和一个或者多个pte对应，反过来，每一个present位为1的pte必须和一个页面相对应，这个反过来的对应是个一一映射关系，但是前面的却不然，也就是说页面到pte的映射却不是一一映射的关系，而在一个页面将要被换出物理内存的时候必须实时更新与之相关的各个pte，由此得出的问题就是必须扫描所有的进程的所有的pte，只要找到pte所对应的页面是将要被换出的页面就更新之，这样效率未免太低下，为什么呢？因为页面被换出本应该只涉及页面和与该页面相关的实体，如果为了找到这些所谓的相关实体而消耗大量的时间和空间资源，那么这必然是一个瓶颈，并且这个缺陷是一定可以弥补的，为什么可以弥补呢？因为我们需要做的仅仅是记录下和此页面相关的实体就可以了，而不是通过遍历寻找的方式，这样可以滤去很多无关的查找，必然的一种可能是浪费了空间来存储额外的信息，带来的优惠就是节省了大量的时间，这就是反向映射的设计初衷，那么反向映射是怎么实现的呢？最简单的实现就是在page数据结构中扩展一个字段，实际上是一个链表，里面链接所有指向这个page的pte，换出该页面的时候遍历这个链表就会得到所有的需要更新的pte，这也是2.6的早期版本中使用的方式：

如果linux和微软一样，那么代码就到此为止了，事实证明这样已经很不错了，是的，代码优美，效率又高，一切都不错，但是linux开发中没有最好只有更好，所有的物理内存都有page结构与之对应，每个page结构中保存一个pte联合实在不是什么明智之举，毕竟很多page根本就不需要pte反向映射，比如内核使用的page以及很多只有一个进程使用的匿名页面，那么就必须想一个办法，一个懒惰的办法将这个反向映射的相关信息保存到一个用户空间使用的结构体之内，就是说只有在使用反向映射的实体中才保存反向映射信息，否则不保存，这样算法的时间复杂度不变，同时可以节省更多的空间，这样一来2.6后来的内核中就废弃了以上的优雅方式，使用了一种更加高效的方法，将反向映射信息保存到vm_area_struct结构中，因为只有用户空间的页面才会有反向映射，而vm_area_struct是只有用户空间进程才有的数据结构

2.6后期的方案利用了mapping的低位没有用的特征从而使用了这些位，利用了一切可以利用的空间，并且这个方案将匿名反向映射和文件缓存反向映射分离，在文件反向映射中使用优先级树高效处理，相比前一个早期的版本性能提高了不少。2.6的后期版本中的反向映射解决方案的资料是比较多的，我就不多说了，但是早期的反向映射的资料比较少，因此本文就分析了代码。本文主要想表达的意思就是linux的后期版本的性能基本都比以前的高，不管它的代码的可读性有多糟糕，其实阅读linux代码和理解代码的关键就是理解作者的设计思想，最好的办法就是看changelog，只要理解了changelog就可以理解作者的意图，读懂了代码才可以修改代码，才可以添加自己的逻辑，开发自己的内核。

2、Linux2.6中是如何实现反向映射

（以下代码均来自内核版本2.6.11.）

2.1 与RM（Reverse Mapping）相关的结构

page, address_space, vm_area_struct, mm_struct, anon_vma.

以下均显示部分成员：

2.2 进程地址空间

1. 每个进程有个进程描述符task_struct，其中有mm域指向该进程的内存描述符mm_struct。

2. 每个进程都拥有一个内存描述符，其中有PGD域，指向该进程地址空间的全局页目录；mmap域指向第一个内存区域描述符vm_area_strut1。

3. 进程通过内存区域描述符vm_area_struct管理内存区域，每个内存区域描述符都有vm_start和vm_end域指向该内存区域的在虚拟内存中的起始位置；vm_mm域指向该进程的内存描述符；每个vm_area_struct都有一个anon_vma域指向该进程的anon_vma；

4. 每个进程都有一个anon_vma，是用于链接所有vm_area_struct的头结点，通过vm_area_struct的anon_vma_node构成双循环链表。

• 　最终形成了上图。

• 现在假设我们要回收一个页，我们要做的是访问所有与该页相关联的PTE并修改之取消二者之间的关联。与之相关联的函数为：try_to_unmap。

2.3 try_to_unmap

2.3.1 try_to_unmap函数及PageOn宏 分析

2.3.2 try_to_unmap_anon函数及page_lock_anon_vma函数及list_for_each_entry宏 分析

• 还没开始看文件系统一节，所以try_to_unmap_file没看懂，所以此处只分析 try_to_unmap_anon函数，等看完vfs后再来补充吧。

2.3.3 try_to_unmap_one函数及vma_address函数及pdg_offset宏 分析

Linux采用三级页表：

1. PGD：顶级页表，由pgd_t项组成的数组，其中第一项指向一个二级页表。

2. PMD：二级页表，由pmd_t项组成的数组，其中第一项指向一个三级页表（两级处理器没有物理的PMD）。

3. PTE：是一个页对齐的数组，第一项称为一个页表项，由pte_t类型表示。一个pte_t包含了数据页的物理地址。