Linux内存管理之页面回收【转】

转自：http://blog.csdn.net/bullbat/article/details/7311205

请求调页机制，只要用户态进程继续执行，他们就能获得页框，然而，请求调页没有办法强制进程释放不再使用的页框。因此，迟早所有空闲内存将被分配给进程和高速缓存，Linux内核的页面回收算法（PFRA）采取从用户进程和内核高速缓存“窃取”页框的办法不从伙伴系统的空闲块列表。

       实际上，在用完所有空闲内存之前，就必须执行页框回收算法。否则，内核很可能陷入一种内存请求的僵局中，并导致系统崩溃。也就是说，要释放一个页框，内核就必须把页框的数据写入磁盘；但是，为了完成这一操作，内核却要请求另一个页框（例如，为I/O数据传送分配缓冲区首部）。因为不存在空闲页框，因此，不可能释放页框。

       页框算法的目标之一就是保存最少的空闲页框并使内核可以安全地从“内存紧缺”的情形中恢复过来。

选择目标页

       PFRA的目标就是获得页框并使之空闲。PFRA按照页框所含内容，以不同的方式处理页框。我们将他们区分成：不可回收页、可交换页、可同步页和可丢弃页：

页类型	说明	回收操作
不可回收页	空闲页（包含子伙伴系统列表中） 保留页（PG_reserved标志置位） 内核动态分配页 进程内核态堆栈页 临时锁定页（PG_locked标志置位） 内存锁定页（在先行区中且VM_LOCKED标志置位）	不允许也无需回收
可回收页	用户太地址空间的匿名页 Tmpfs文件系统的映射页（如IPC共享内存的页）	将页的内容保存在交换区
可同步页	用户态地址空间的映射页 存有磁盘文件数据且在页高速缓存中的页 块设备缓冲区页 某些磁盘高速缓存的页（如索引节点高速缓存）	必要时，与磁盘镜像同步这些页
可丢弃页	内存高速缓存中的未使用页（如slab分配器高速缓存） 目录想高速缓存的未使用页	无需操作

 

进行页面回收的时机

        Linux 操作系统使用如下这两种机制检查系统内存的使用情况，从而确定可用的内存是否太少从而需要进行页面回收。

• • 周期性的检查：这是由后台运行的守护进程 kswapd 完成的。该进程定期检查当前系统的内存使用情况，当发现系统内空闲的物理页面数目少于特定的阈值时，该进程就会发起页面回收的操作。
  • “内存严重不足”事件的触发：在某些情况下，比如，操作系统忽然需要通过伙伴系统为用户进程分配一大块内存，或者需要创建一个很大的缓冲区，而当时系统中的内存没有办法提供足够多的物理内存以满足这种内存请求，这时候，操作系统就必须尽快进行页面回收操作，以便释放出一些内存空间从而满足上述的内存请求。这种页面回收方式也被称作“直接页面回收”。
  • 睡眠回收，在进入suspend-to-disk状态时，内核必须释放内存。

       如果操作系统在进行了内存回收操作之后仍然无法回收到足够多的页面以满足上述内存要求，那么操作系统只有最后一个选择，那就是使用 OOM( out of memory )killer，它从系统中挑选一个最合适的进程杀死它，并释放该进程所占用的所有页面。

       上面介绍的内存回收机制主要依赖于三个字段：pages_min，pages_low 以及 pages_high。每个内存区域（ zone ）都在其区域描述符中定义了这样三个字段，这三个字段的具体含义如下表 所示。

字段含义

名称	字段描述
pages_min	区域的预留页面数目，如果空闲物理页面的数目低于 pages_min，那么系统的压力会比较大，此时，内存区域中急需空闲的物理页面，页面回收的需求非常紧迫。
pages_low	控制进行页面回收的最小阈值，如果空闲物理页面的数目低于 pages_low，那么操作系统内核会开始进行页面回收。
pages_high	控制进行页面回收的最大阈值，如果空闲物理页面的数目多于 pages_high，则内存区域的状态是理想的。

 

PFRA设计

设计总则

1.       首先释放“无害”页，即必须线回收没有被任何进程使用的磁盘与内存高速缓存中的页；

2.       将用户态进程和所有页定为可回首页，FPRA必须能够窃得人任何用户态进程页，包括匿名页。这样，睡眠较长时间的进程将逐渐失去所有页；

3.       同时取消引用一个共享页的所有页表项的映射，就可以回收该共享页；

4.       只回收“未用”页，使用LRU算法。Linux使用每个页表项中的访问标志位，在页被访问时，该标志位由银奖自动置位；而且，页年龄由页描述符在链表（两个不同的链表之一）中的位置来表示。

因此，页框回收算法是集中启发式方法的混合：

1．  谨慎选择检查高速缓存的顺序；

2．  基于页年龄的变化排序；

3．  区别对待不同状态的页；

反向映射

        PFRA的目标之一是能释放共享页框。为达到这个目地。Linux内核能够快速定为指向同一页框的所有页表项。这个过程就叫做反向映射。Linux 操作系统为物理页面建立一个链表，用于指向引用了该物理页面的所有页表项。

基本思想如下图：

       Linux采用“面向对象的反向映射”技术。实际上，对任何可回收的用户态页，内核保留系统中该页所在所有现行区（“对象”）的反向链接，每个线性区描述符（ vm_area_struct 结构）存放一个指针指向一个内存描述符（ mm_struct 结构），而该内存描述符又包含一个指针指向一个页全局目录（PGD）。因此，这些反向链接使得PFRA能够检索引用某页的所有页表项。因为线性区描述符比页描述符少，所以更新共享页的反向链接就比较省时间。下面是具体的实现：

基于对象的反向映射的实现

数据结构

       首先，PFRA必须要确定待回收页是共享的还是非共享的，以及是映射页或是匿名页。为做到这一点，内核要查看页描述符的两个字段：_mapcount和mapping。_mapcount字段存放引用页框的页表项数目，确定其是否共享；mapping字段用于确定页是映射的或是匿名的：为空表示该页属于交换高速缓存；非空，且最低位是1，表示该页为匿名页，同时mapping字段中存放的是指向anon_vma描述符的指针；如果mapping字段非空，且最低位是0，表示该页为映射页；同时mapping字段指向对应文件的address_space对象。

        Linux的address_space对象在RAMA中是对其的，所以其起始地址是4的倍数。因此其mapping字段的最低位可以用作一个标志位来表示该字段的指针是指向address_space对象还是anon_vma描述符。PageAnon检查mapping最低位。

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

匿名页的面向对象反向映射如下图：

       可以通过页面的mapping找到anon_vma然后找到映射该页面的所有线性区域（vm_area_struct结构）。

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

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

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

       与匿名页面的双向链表相关的字段是 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_set.list 和 vm_set.head

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

反向映射实现

       在进行页面回收的时候，Linux的 shrink_page_list() 函数中调用 try_to_unmap() 函数去更新所有引用了回收页面的页表项。其代码流程如下所示：
实现函数 try_to_unmap() 的关键代码流程图

       函数 try_to_unmap() 分别调用了两个函数 try_to_unmap_anon() 和 try_to_unmap_file()，其目的都是检查并确定都有哪些页表项引用了同一个物理页面，但是，由于匿名页面和文件映射页面分别采用了不同的数据结构，所以二者采用了不同的方法。

       函数 try_to_unmap_anon() 用于匿名页面，该函数扫描相应的 anon_vma 表中包含的所有内存区域，并对这些内存区域分别调用 try_to_unmap_one() 函数。

       函数 try_to_unmap_file() 用于文件映射页面，该函数会在优先级搜索树中进行搜索，并为每一个搜索到的内存区域调用 try_to_unmap_one() 函数。

       两条代码路径最终汇合到 try_to_unmap_one() 函数中，更新引用特定物理页面的所有页表项的操作都是在这个函数中实现的。

代码如下，对关键部分做了注释：

        对于给定的物理页面来说，该函数会根据计算出来的线性地址找到对应的页表项地址，并更新页表项。对于匿名页面来说，换出的位置必须要被保存下来，以便于该页面下次被访问的时候可以被换进来。并非所有的页面都是可以被回收的，比如被 mlock() 函数设置过的内存页，或者最近刚被访问过的页面，等等，都是不可以被回收的。一旦遇上这样的页面，该函数会直接跳出执行并返回错误代码。如果涉及到页缓存中的数据，需要设置页缓存中的数据无效，必要的时候还要置位页面标识符以进行数据回写。该函数还会更新相应的一些页面使用计数器，比如前边提到的 _mapcount 字段，还会相应地更新进程拥有的物理页面数目等。

PFRA具体实现

LRU 链表

        在 Linux 中，操作系统对 LRU 的实现主要是基于一对双向链表：active 链表和 inactive 链表，这两个链表是 Linux 操作系统进行页面回收所依赖的关键数据结构，每个内存区域都存在一对这样的链表。顾名思义，那些经常被访问的处于活跃状态的页面会被放在 active 链表上，而那些虽然可能关联到一个或者多个进程，但是并不经常使用的页面则会被放到 inactive 链表上。页面会在这两个双向链表中移动，操作系统会根据页面的活跃程度来判断应该把页面放到哪个链表上。页面可能会从 active 链表上被转移到 inactive 链表上，也可能从 inactive 链表上被转移到 active 链表上，但是，这种转移并不是每次页面访问都会发生，页面的这种转移发生的间隔有可能比较长。那些最近最少使用的页面会被逐个放到 inactive 链表的尾部。进行页面回收的时候，Linux 操作系统会从 inactive 链表的尾部开始进行回收。

用于描述内存区域的 struct zone() 中关于这两个链表以及相关的关键字段的定义如下所示：

各字段含义如下所示：

lru_lock：active_list 和 inactive_list 使用的自旋锁。

active_list：管理内存区域中处于活跃状态的页面。

inactive_list：管理内存区域中处于不活跃状态的页面。

nr_active：active_list 链表上的页面数目。

nr_inactive：inactive_list 链表上的页面数目。

如何在两个LRU 链表之间移动页面

       Linux 引入了两个页面标志符 PG_active 和 PG_referenced 用于标识页面的活跃程度，从而决定如何在两个链表之间移动页面。PG_active 用于表示页面当前是否是活跃的，如果该位被置位，则表示该页面是活跃的。PG_referenced 用于表示页面最近是否被访问过，每次页面被访问，该位都会被置位。Linux 必须同时使用这两个标志符来判断页面的活跃程度，假如只是用一个标志符，在页面被访问时，置位该标志符，之后该页面一直处于活跃状态，如果操作系统不清除该标志位，那么即使之后很长一段时间内该页面都没有或很少被访问过，该页面也还是处于活跃状态。为了能够有效清除该标志位，需要有定时器的支持以便于在超时时间之后该标志位可以自动被清除。然而，很多 Linux 支持的体系结构并不能提供这样的硬件支持，所以 Linux 中使用两个标志符来判断页面的活跃程度。

Linux 2.6 中这两个标志符密切合作，其核心思想如下所示：

• 如果页面被认为是活跃的，则将该页的 PG_active 置位；否则，不置位。
• 当页面被访问时，检查该页的 PG_referenced 位，若未被置位，则置位之；若发现该页的 PG_referenced 已经被置位了，则意味着该页经常被访问，这时，若该页在 inactive 链表上，则置位其 PG_active 位，将其移动到 active 链表上去，并清除其 PG_referenced 位的设置；如果页面的 PG_referenced 位被置位了一段时间后，该页面没有被再次访问，那么 Linux 操作系统会清除该页面的 PG_referenced 位，因为这意味着这个页面最近这段时间都没有被访问。
• PG_referenced 位同样也可以用于页面从 active 链表移动到 inactive 链表。对于某个在 active 链表上的页面来说，其 PG_active 位被置位，如果 PG_referenced 位未被置位，给定一段时间之后，该页面如果还是没有被访问，那么该页面会被清除其 PG_active 位，挪到 inactive 链表上去。

Linux 中实现在 LRU 链表之间移动页面的关键函数如下所示（本文涉及的源代码均是基于 Linux 2.6.18.1 版本的）：

• mark_page_accessed()：当一个页面被访问时，则调用该函数相应地修改 PG_active 和 PG_referenced。
• page_referenced()：当操作系统进行页面回收时，每扫描到一个页面，就会调用该函数设置页面的 PG_referenced 位。如果一个页面的 PG_referenced 位被置位，但是在一定时间内该页面没有被再次访问，那么该页面的 PG_referenced 位会被清除。
• activate_page()：该函数将页面放到 active 链表上去。
• shrink_active_list()：该函数将页面移动到 inactive 链表上去。

LRU 缓存

        前边提到，页面根据其活跃程度会在 active 链表和 inactive 链表之间来回移动，如果要将某个页面插入到这两个链表中去，必须要通过自旋锁以保证对链表的并发访问操作不会出错。为了降低锁的竞争，Linux 提供了一种特殊的缓存：LRU 缓存，用以批量地向 LRU 链表中快速地添加页面。有了 LRU 缓存之后，新页不会被马上添加到相应的链表上去，而是先被放到一个缓冲区中去，当该缓冲区缓存了足够多的页面之后，缓冲区中的页面才会被一次性地全部添加到相应的 LRU 链表中去。Linux 采用这种方法降低了锁的竞争，极大地提升了系统的性能。

LRU 缓存用到了 pagevec 结构，如下所示 :

         pagevec 这个结构就是用来管理 LRU 缓存中的这些页面的。该结构定义了一个数组，这个数组中的项是指向 page 结构的指针。一个 pagevec 结构最多可以存在 14 个这样的项（PAGEVEC_SIZE 的默认值是 14）。当一个 pagevec 的结构满了，那么该 pagevec 中的所有页面会一次性地被移动到相应的 LRU 链表上去。

用来实现 LRU 缓存的两个关键函数是 lru_cache_add() 和 lru_cache_add_active()。前者用于延迟将页面添加到 inactive 链表上去，后者用于延迟将页面添加到 active 链表上去。这两个函数都会将要移动的页面先放到页向量 pagevec 中，当 pagevec 满了（已经装了 14 个页面的描述符指针），pagevec 结构中的所有页面才会被一次性地移动到相应的链表上去。

下图概括总结了上文介绍的如何在两个链表之间移动页面，以及 LRU 缓存在其中起到的作用：

 页面在 LRU 链表之间移动示意图

       其中，1 表示函数 mark_page_accessed()，2 表示函数 page_referenced()，3 表示函数 activate_page()，4 表示函数 shrink_active_list()。

PFRA具体实现

        PFRA必须处理多种属于用户态进程、磁盘高速缓存和内存高速缓存的页，而且必须遵照几条试探法准则。PFRA的大部分函数如下：

       如上图在分配VFS缓冲区或缓冲区首部时，内核调用free_more_memory();而当从伙伴系统分配一个或多个页框时，调用try_to_free_pages()。

页面回收关键代码流程图

       上文提到 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 操作系统实现页面回收的最核心的函数之一，它实现了对一个内存区域的页面进行回收的功能，该函数主要做了两件事情：

• 将某些页面从 active 链表移到 inactive 链表，这是由函数 shrink_active_list() 实现的。
• 从 inactive 链表中选定一定数目的页面，将其放到一个临时链表中，这由函数 shrink_inactive_list() 完成。该函数最终会调用 shrink_page_list() 去回收这些页面。

       函数 shrink_page_list() 返回的是回收成功的页面数目。概括来说，对于可进行回收的页面，该函数主要做了这样几件事情，其代码流程图如下所示：
函数 shrink_page_list() 实现的关键功能

• 对于匿名页面来说，在回收此类页面时，需要将其数据写入到交换区。如果尚未为该页面分配交换区槽位，则先分配一个槽位，并将该页面添加到交换缓存。同时，将相关的 page 实例加入到交换区，这样，对该页面的处理就可以跟其他已经建立映射的页面一样；
• 如果该页面已经被映射到一个或者多个进程的页表项中，那么必须找到所有引用该页面的进程，并更新页表中与这些进程相关的所有页表项。在这里，Linux 2.6 操作系统会利用反向映射机制去检查哪些页表项引用了该页面，关于反向映射的内容在后边会有介绍；
• 如果该页面中的数据是脏的，那么数据必须要被回写；
• 释放页缓存中的干净页面。

函数 shrink_slab()

       函数 shrink_slab() 是用来回收磁盘缓存所占用的页面的。Linux 操作系统并不清楚这类页面是如何使用的，所以如果希望操作系统回收磁盘缓存所占用的页面，那么必须要向操作系统内核注册 shrinker 函数，shrinker 函数会在内存较少的时候主动释放一些该磁盘缓存占用的空间。函数 shrink_slab() 会遍历 shrinker 链表，从而对所有注册了 shrinker 函数的磁盘缓存进行处理。

       从实现上来看，shrinker 函数和 slab 分配器并没有固定的联系，只是当前主要是 slab 缓存使用 shrinker 函数最多。

       注册 shrinker 是通过函数 set_shrinker() 实现的，解除 shrinker 注册是通过函数 remove_shrinker() 实现的。当前，Linux 操作系统中主要的 shrinker 函数有如下几种：

• shrink_dcache_memory()：该 shrinker 函数负责 dentry 缓存。
• shrink_icache_memory()：该 shrinker 函数负责 inode 缓存。

mb_cache_shrink_fn()：该 shrinker 函数负责用于文件系统元数据的缓存。

具体的源代码实现细节有时间再做分析。后面将谈论交换。

 

 

参考：

ULK3

http://www.ibm.com/developerworks/cn/linux/l-cn-pagerecycle/