分类: LINUX
2012-12-25 17:52:58
页面回收的实现
Linux 操作系统进行页面回收需要考虑的方面很多,下图列出了 Linux 操作系统进行页面回收的关键代码流程图,该图给出了实现页面回收的关键代码函数名,并说明它们之间是如何彼此链接的。
上文提到 Linux 中页面回收主要是通过两种方式触发的,一种是由“内存严重不足”事件触发的;一种是由后台进程 kswapd 触发的,该进程周期性地运行,一旦检测到内存不足,就会触发页面回收操作。对于第一种情况,系统会调用函数 try_to_free_pages() 去检查当前内存区域中的页面,回收那些最不常用的页面。对于第二种情况,函数 balance_pgdat() 是入口函数。
当 NUMA 上的某个节点的低内存区域调用函数 try_to_free_pages() 的时候,该函数会反复调用 shrink_zones() 以及 shrink_slab() 释放一定数目的页面,默认值是 32 个页面。如果在特定的循环次数内没有能够成功释放 32 个页面,那么页面回收会调用 OOM killer 选择并杀死一个进程,然后释放它占用的所有页面。函数 shrink_zones() 会对内存区域列表中的所有区域分别调用 shrink_zone() 函数,后者是从内存回收最近最少使用页面的入口函数。
对于定期页面检查并进行回收的入口函数 balance_pgdat() 来说,它主要调用的函数是 shrink_zone() 和 shrink_slab()。从上图中我们也可以看出,进行页面回收的两条代码路径最终汇合到函数 shrink_zone() 和函数 shrink_slab() 上。
函数 shrink_zone()
其中,shrink_zone() 函数是 Linux 操作系统实现页面回收的最核心的函数之一,它实现了对一个内存区域的页面进行回收的功能,该函数主要做了两件事情:
函数 shrink_page_list() 返回的是回收成功的页面数目。概括来说,对于可进行回收的页面,该函数主要做了这样几件事情,其代码流程图如下所示:
图 3. 函数 shrink_page_list() 实现的关键功能
函数 shrink_slab()
函数 shrink_slab() 是用来回收磁盘缓存所占用的页面的。Linux 操作系统并不清楚这类页面是如何使用的,所以如果希望操作系统回收磁盘缓存所占用的页面,那么必须要向操作系统内核注册 shrinker 函数,shrinker 函数会在内存较少的时候主动释放一些该磁盘缓存占用的空间。函数 shrink_slab() 会遍历 shrinker 链表,从而对所有注册了 shrinker 函数的磁盘缓存进行处理。
从实现上来看,shrinker 函数和 slab 分配器并没有固定的联系,只是当前主要是 slab 缓存使用 shrinker 函数最多。
注册 shrinker 是通过函数 set_shrinker() 实现的,解除 shrinker 注册是通过函数 remove_shrinker() 实现的。当前,Linux 操作系统中主要的 shrinker 函数有如下几种:
前文介绍过,在回收一个物理页面之前,需要查找到所有关联了该物理页面的页表项,并逐一更新这些页表项。Linux 2.6 使用了反向映射这种机制用于快速定位那些引用了某个物理页面的所有页表项。Linux 操作系统为物理页面建立一个链表,用于指向引用了该物理页面的所有页表项。其基本思想如下图所述:
在 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; }; …… }; |
匿名页面和文件映射页面分别采用了不同的底层数据结构去存放与页面相关的虚拟内存区域。对于匿名页面来说,与该页面相关的虚拟内存区域存放在结构 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。
通过结构 vm_area_struct 中的 vm_mm 字段可以找到对应的 mm_struct 结构,在该结构中找到页全局目录,从而定位所有相关的页表项。
使用反向映射
在进行页面回收的时候,Linux 2.6 在前边介绍的 shrink_page_list() 函数中调用 try_to_unmap() 函数去更新所有引用了回收页面的页表项。其代码流程如下所示:
页面回收是 Linux 内存管理中比较复杂的一个部分,涉及到的相关内容非常多,本文也不是面面俱到。反向映射是 Linux 2.5 开发过程中一个比较大的亮点,该技术在后续 Linux 2.6 版本中又得到了更进一步的发展。本文的目的是想帮助读者理清 Linux 2.6 中的页面回收和反向映射机制,本文通过相关的数据结构和关键的代码流程介绍了 Linux 操作系统如何利用反向映射机制有效地进行页面回收。关于 Linux 操作系统如何建立反向映射的内容,本文没有做详尽介绍,感兴趣的读者可以自行参考内核源代码。