反向映射机制

在Linux内存管理器中，页表保持对进程使用的内存物理页的追踪，它们将虚拟页映射到物理页。有些页可能不是长时间使用，它们应该被交换出去。但是在交换出去之前，我们首先要做的就是要更新使用该交换页的每1个进程的页表项。为了更新进程页表项，以往为了确定某个要回收的物理页面都被哪些页表项引用，必须要遍历所有进程，这是1项非常耗资源和时间的工程。所以引入反向映射(RMAP)机制，使得更加有效地回收1个共享页面，反向映射技术的实现主要是基于页表项链表。

操作系统为每1个物理页面都维护了1个链表，所有与该物理页面关联的页表项都会被放到这个链表上，建立了物理页面和所有映射了该物理页面的页表项之间的1种关联，从而让操作系统可以快速定位引用了该物理页面的所有页表项，不再是遍历每个进程的页表。该机制中内存管理器为每1个物理页建立了1个链表，包含了指向当前映射那个页的每1个进程的页表条目(Page-TableEntries，PTE)的指针。然而基于页表项链表存在为每个物理页面维护这样1个链表，同样需要占用大量的内存空间造成空间资源的消耗。回收1个物理页面的时候，需要先获取该链表上的锁，然后遍历相应的反向映射链表，链表上的项越多，需要的时间越多，造成时间资源消耗越大。为了解决这一弊端引入基于对象的反向映射机制1。

基于对象的反向映射机制基于对象的反向映射机制也是为物理页面设置1个用于反向映射的链表，但是链表上的节点不再是引用该物理页面的所有页表项，而是相应的虚拟内存区域(vm_area_struct结构)，虚拟内存区域通过内存描述符(mm_struct结构)找到页全局目录，从而找到相应的页表项，在一定程度上也节约了内存空间。用于表示虚拟内存区域的描述符比用于表示页面的描述符要少得多，所以遍历基于对象的反向映射链表所消耗的时间也会少很多。所以在一定程度上减少了空间资源和时间资源的消耗。

基于对象的反向映射的实现，数据结构page结构中与基于对象的反向映射相关的关键字段:_mapcount和mapping。

struct page{

atomic_t _mapcount;

union{

……

struct {

……

struct

address _space* mapping;

};

……

};

字段_mapcount表明共享该物理页面的页表项的数目。该计数器可用于快速检查该页面除所有者之外有多少个使用者在使用，初始值是－1，每增加一个使用者，该计数器加1。字段mapping用于区分匿名页面和基于文件映射的页面，如果该字段的最低位被置位了，那么该字段包含的是指向anon_vma用于匿名页面结构的指针;否则，该字段包含指向address_space结构的用于基于文件映射页面指针。

反向映射机制的优势使用基于对象的反向映射机制改善了查找映射到指定物理页对应的虚拟页的内存管理的瓶颈，并且可以快速定位引用了某个物理页面的所有页表项，这极大地方便了操作系统进行页面回收。相对于之前的遍历方法来说，基于对象的反向映射机制在很大程度上减少了操作系统在页面回收上所占用的CPU时间。相对于之前的单纯的反向映射机制来说，在一定程度上也解决了要消耗掉一定的内存空间的问题。

Linux 2.6中反向映射方法Object-page Rmap技术Linux2.6版内核融合的反向映射技术是基于页的反向映射，它提供了一个发现哪些进程正在使用给定的内存物理页的机制。不再是遍历每个进程的页表，内存管理器为每一个物理页建立了一个链表，包含了指向当前映射这个页的每一个进程的页表条目（page-tableentries,PTE）的指针。这个链表叫做PTE链。PTE链极大地提高了找到那些映射到指定页的进程的速度，如图所示2。

Linux2.6版内核中用structpte_chain*chain结构来描述反向映射指针结构，并将此结构加入page数据结构中：

typedef struct page{

……

struct pte_chain* chain;

……}

前面已经讲过分页单元把所有的RAM分为固定长度的页框，也叫物理页（page frame）。线性地址也被分成固定长度为单位的组。把线性地址映射到物理地址的数据结构称为页表（page table）。当某个进程执行的时候，内核才将该进程的部分虚拟地址映射到物理地址，并且在这个进程的页表中做相应的修改，跟踪这种映射关系。现在加入structpte_chain*chain结构以后，利用这个结构，当虚拟地址映射到物理地址时，structpte_chain *chain同时也记录着映射到该物理地址的进程的页表条目，进程页表中记录的是进程虚拟地址映射到物理地址的关系，这样就行成了双向映射。即可以通过页表，查找到指定虚拟地址所映射的物理地址的位置，也可以根据page结构查找到映射到指定物理地址的进程的页表条目的位置。此外，structpte_chain*chain还可组成的指针结构，因为在linux系统中存在多个虚拟地址指向通一个物理地址，也就是多个进程共享同一个物理页，此时，每个structpte_chain*chain指针分别指向映射到该物理地址的进程的页表条目。

反向页表技术的主要设计思想是在传统页表基础上，为每个物理页增加一个反向指针集合，指向使用该物理页的各个页表项，形成物理地址到虚地址的反向映射。如图所示，其中虚线部分表示反向页表结构。使用反向映射技术带来性能的提高是非常明显的，但是同时也增加了系统的开销。首先是内存开销，PTE链的每一个条目使用4个字节来存储指向页表条目的指针，用另外4个字节来存储指向链的下一个条目的指针。节点的Next指针采用32位，所以在32位硬件上不能使用高端内存，低端内存的使用对运行很多进程大量数据的服务器来说竞争非常激烈，例如在一个512M内存的系统中，有128K个物理页，这样就需要有128KB*(sizeof(structpte_chain))的内存被分配用于pte_chain的结构。对于这种对低端内存的占用过多对于服务器的应用不利。此外，基于页面的反向映射在还带来了一些其他的复杂性。当页与一个进程产生映射时，必须为这个页建立反向映射。

同样，当一个进程释放对页的映射时，相应的反向映射也必须都删除掉。这情况在进程生成和退出时会进行大量的操作。而且所有这些操作都必须在锁定情况下进行，锁定情况的增加也不易于并行多进程的应用。对那些执行很多派生和退出的应用程序来说，这可能会非常浪费并且增加很多开销。下面主要看下加入反向映射技术以后为了与系统正向页表保持一致性而对反向页表进行建立和动态增删的维护过程。

反向页表的维护在系统运行过程中，正向页表将不断改变虚实地址的映射关系，反向页表是维护实虚地址映射关系的页表，故反向页表将随正向页表的变化而动态改变.反向页表的维护是在任何一个PTE中的物理地址发生改变时，此时反向页表都需要进行修改，以正确反映当前的实虚映射关系。反向页表的维护主要发生在页失效中断、页迁移中断和换页和交换过程中。

页失效中断

当逻辑页面没有对应的物理页面时,系统会进入页失效中断处理。页失效中断处理例程将为该逻辑页面准备合适的物理页面，并将该物理页面的地址填写到PTE中.页失效发生的情况主要有写时拷贝、文件页失效、匿名页失效、交换页失效。写时拷贝的基本思想是将一个物理页面(旧页)标记为只读，而将其所包含的虚地址访问位(VMA)标识为可写.任何对页面的写操作都会与页级保护相冲突，然后触发一个页失效.当页失效处理程序注意到页级保护和虚地址访问位(VMA)的保护不一致时，它将创建该页的一个可写拷贝(新页)作为替代页.此时需要修改写进程的页表和新旧物理页的反向页表，删除旧页反向页表中有关写进程的项，并为新页分配反向页表，在该表中填加写进程中指向它的页表项地址。此时，我们使用反向页表建立例程为物理页建立反向页表数据结构。文件页是指映射到磁盘文件的虚拟页，当对该类虚拟页进行访问发生失效时，页失效处理例程负资分配一个新物理页，将所缺页内容从磁盘载入内存物理页中，而后将物理页地址添写到虚拟页的PTE表项中。此时，我们使用反向页表建立例程为物理页建立反向页表数据结构。匿名页是指供进程堆栈使用的页，当对该类虚拟页进行首次访问时，会发生页失效。页失效处理例程负责为其分配新页，并初始化为全零，而后将物理页地址添写到虚拟页的PTE表项中。此时，我们使用反向页表建立例程为物理页建立反向页表数据结构。交换页是指被暂时交换到交换设备上，不在内存物理页中的虚拟页.页失效处理例程分配新的物理页，并将缺页的内容从交换设备上换入到新分配的物理页中，而后将物理页地址添写到虚拟页的PTE表项中。此时，我们使用反向页表建立例程为物理页建立反向页表数据结构。以上四种情况中都存在分配新物理页的情况，这些物理页创建反向页表结构，并填写正确的PTE。

页迁移和复制

页迁移和页复制过程中，根据中断给出的需要迁移的物理页地址，通过查阅反向页表，可以快速、准确地定位所有的PTE。页迁移过程中，需要释放旧页，删除其反向页表，并为迁移后的新页重新分配反向页表，且把所有映射到该物理页的页表项虚地址写入反向页表中。我们将旧物理页中的反向页表结构赋予给新物理页，旧物理页指向该反向页表结构的指针随物理页的释放而删除。页复制过程中，需要产生原物理页的拷贝页，此时一个多对一映射分裂为两个多对一映射，每个物理页的反向页表，都应仅包含实际访问它的PTE。此时根据新生成的PTE调用反向页表建立例程为新物理页建立反向页表结构，调用反向页表删除例程删除旧物理页中对应的PTE。

交换和换页

为了提高内存的有效利用率，操作系统通过换页和交换机制将暂时不用的进程页写到交换设备，释放占用的物理页。换页和交换机制通过系统中运行的守护进程swapper实现。在守护进程将暂时不用的进程页写到交换设备，释放占用的物理页时，反向页表随物理页的释放而进行删除操作。根据当时情况调用反向页表的建立和删除例程，完成维护工作。Linux2.6采用的基于页反向映射方法尽管有一些折衷，但可以证明反向映射是对Linux内存管理器的一个颇有价值的修改。通过这一途径，查找定位映射某个页的进程这一严重瓶颈被最小化为只需要一个简单的操作。当大型应用程序向内核请求大量内存和多个进程共享内存时，反向映射帮助系统继续有效地运行和扩展，对Linux作为大型服务器的性能和稳定性方面都有很大的提高。所以接着要做的就是在反向映射的基础上，进行技术改进来减少反向映射带来的内存占用和系统时间花费上所带来的问题。

p页直接方法P页直接方法就是加入到Linux2.6内核中减少反向映射带来的内存开销的一种方法。虽然进程共享同一个物理页在Linux进程操作中是常见现象，但这种两个或者更多个进程共享同一个物理页的情况并不是Linux虚拟映射机制的普遍情况。基于这种情况的分析，为了减少反向映射指针对内存尤其是低端内存的消耗，在Linux2.6内核中可以将反向映射指针structpte_chain*chain用结构体union代替加入page数据结构中：typedefstructpage{……union{structpte_chain*chain;pte_addr_tdirect;}Pte;……}用这种方法就叫做P页直接方法（page-directapproach）。如果只有一个进程映射到这个物理页，那么在建立影射关心的时候，就可以用一个叫做“direct”的指针来代替链表，直接指向映射到这个物理页的进程的页表条目。当然，只有在这个个页只是由一个惟一的进程映射时就可以进行这种优化，这种映射关系在Linux虚拟地址到物理地址内存映射当中还是占绝大部分。采用这种优化以后，单独的“direct”指针虽然也是占用低端内存，但所占大小比用structpte_chain结构小很多。不过如果稍后这个页被另一个进程所映射，它必须删除“direct”指针，然后重新去建立PTE链。同样，当structpte_chain*chain指针链表只剩一个指针的时候，还需要考虑是否转化成“direct”指针。而且这种在“direct”指针和structpte_chain*chain指针链表之间进行转换也会浪费很多系统时间。此外，还需要设置一个标记用来告诉内存管理器什么时候这种优化对一个给定的页有效，即标记是使用“direct”指针还是使用structpte_chain*chain指针链表。所以，综合来看，采用P页直接方法只是减少了一部分对低端内存的占用，对提高反向映射指针的效率并没有带来太大的改变。要想降低反向映射带来的时间内存开销还必须仔细分析系统内核，提出更行之有效的方法。