Linux的页面回收与反向映射机制(1)(4)

反向映射(reverse mapping)

前文介绍过，在回收一个物理页面之前，需要查找到所有关联了该物理页面的页表项，并逐一更新这些页表项。Linux 2.6 使用了反向映射这种机制用于快速定位那些引用了某个物理页面的所有页表项。Linux 操作系统为物理页面建立一个链表，用于指向引用了该物理页面的所有页表项。其基本思想如下图所述：

图 4. 反向映射的基本思想

反向映射技术的发展历史

在 Linux 2.4 中，为了确定某个要回收的物理页面都被哪些页表项引用，必须要遍历所有进程，这是一项非常耗资源和时间的工程。为了更加有效地回收一个共享页面，Linux 在 2.5 版本的开发期间引入了反向映射这样一种机制。这种机制建立了物理页面和所有映射了该物理页面的页表项之间的一种关联，从而让操作系统可以快速定位引用了该物理页面的所有页表项。在 Linux 2.6 版本中，反向映射算法又经历了大量改进。

在 Linux 2.5 版本中，反向映射技术的实现主要是基于页表项链表。操作系统为每一个物理页面都维护了一个链表，所有与该物理页面关联的页表项都会被放到这个链表上。这种方法会存在一些问题：

●空间资源的消耗：为每个物理页面维护这样一个链表，需要占用大量的内存空间。

●时间资源的消耗：回收一个物理页面的时候，需要先获取该链表上的锁，然后遍历相应的反向映射链表，链表上的项越多，需要的时间就越多。

后来，Linux 2.6 引入了基于对象的反向映射机制。这种方法也是为物理页面设置一个用于反向映射的链表，但是链表上的节点并不是引用了该物理页面的所有页表项，而是相应的虚拟内存区域( 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 结构的指针(用于基于文件映射的页面)。

匿名页面和文件映射页面分别采用了不同的底层数据结构去存放与页面相关的虚拟内存区域。对于匿名页面来说，与该页面相关的虚拟内存区域存放在结构 anon_vma 中定义的双向链表中。结构 anon_vma 定义很简单，如下所示：

struct anon_vma {
spinlock_t lock;
struct list_head head;
};

而对于基于文件映射的页面来说，与匿名页面不同的是，与该页面相关的虚拟内存区域的存放是利用了优先级搜索树这种数据结构的。这是因为对于匿名页面来说，页面虽然可以是共享的，但是一般情况下，共享匿名页面的使用者的数目不会很多;而对于基于文件映射的页面来说，共享页面的使用者的数目可能会非常多，使用优先级搜索树这种结构可以更加快速地定位那些引用了该页面的虚拟内存区域。操作系统会为每一个文件都建立一个优先级搜索树，其根节点可以通过结构 address_space 中的 i_mmap 字段获取。

struct address_space {
……
struct prio_tree_root i_mmap;
……
}

Linux 2.6 中使用 (radix,size,heap) 来表示优先级搜索树中的节点。其中，radix 表示内存区域的起始位置，heap 表示内存区域的结束位置，size 与内存区域的大小成正比。在优先级搜索树中，父节点的 heap 值一定不会小于子节点的 heap 值。在树中进行查找时，根据节点的 radix 值进行。程序可以根据 size 值区分那些具有相同 radix 值的节点。

在用于表示虚拟内存区域的结构 vm_area_struct 中，与上边介绍的双向链表和优先级搜索树相关的字段如下所示：

struct vm_area_struct {
struct mm_struct * vm_mm;
……
union {
struct {
struct list_head list;
void *parent;
struct vm_area_struct *head;
} vm_set;
struct raw_prio_tree_node prio_tree_node;
} shared;
struct list_head anon_vma_node;
struct anon_vma *anon_vma;
};

与匿名页面的双向链表相关的字段是 anon_vma_node 和 anon_vma。union shared 则与文件映射页面使用的优先级搜索树相关。字段 anon_vma 指向 anon_vma 表;字段 anon_vma_node 将映射该页面的所有虚拟内存区域链接起来;union shared 中的 prio_tree_node 结构用于表示优先级搜索树的一个节点;在某些情况下，比如不同的进程的内存区域可能映射到了同一个文件的相同部分，也就是说这些内存区域具有相同的(radix,size,heap)值，这个时候 Linux 就会在树上相应的节点(树上原来那个具有相同 (radix,size,heap) 值的内存区域)上接一个双向链表用来存放这些内存区域，这个链表用 vm_set.list 来表示;树上那个节点指向的链表中的第一个节点是表头，用 vm_set.head 表示;vm_set.parent 用于表示是否是树结点。下边给出一个小图示简单说明一下 vm_set.list 和 vm_set.head。

图 5. vm_set.list 和 vm_set.head

通过结构 vm_area_struct 中的 vm_mm 字段可以找到对应的 mm_struct 结构，在该结构中找到页全局目录，从而定位所有相关的页表项。