第十七章--回收页框

一、页框回收算法
          减少控制是一种设计选择，这使内核以最好的可行方式使用可用的RAM。当系统负载较低时，RAM的大部分由磁盘高速缓存占用，很少正在运行的进程可以从中获益。但是，当系统负载增加时，RAM的大部分则由进程页占用，高速缓存就会缩小从而给后来的进程让出空间。
          迟早所有空闲内存将被分配给进程和高速缓存。Linux内核的页框回收算法(page frame reclaiming algorithm，PFRA)采取从用户态进程和内核高速缓存“窃取”页框的方法补充伙伴系统的空闲块列表。
          实际上，在用完所有空闲内存之前，就必须执行页框回收算法。否则，内核很可能陷入一种内存请求的僵局中，并导致系统崩溃。也就是说，要释放一个页框，内核就必须把页框的数据写入磁盘；但是，为了完成这一操作，内核却要请求另一个页框(例如，为I/O数据传送分配缓冲区首部)。因为不存在空闲页框，因此，不可能释放页框。
        页框回收算法的目标之一就是保存最少的空闲页框池以便内核可以安全地从“内存紧缺”的情形中恢复过来。
1.1、选择目标页
        页框回收算法(PFRA)的目标就是获得页框并使之空闲。显然，PFRA选取的页框肯定不是空闲的，即这些页框原本不在伙伴系统的任何一个free_area数组中。
        PFRA按照页框所含内容，以不同的方式处理页框。我们将它们区分成：不可回收页、可交换页、可同步页和可丢弃页。
        当PFRA必须回收属于某进程用户态地址空间的页框时，它必须考虑页框是否为共享的。共享页框属于多个用户态地址空间，而非共享页框属于单个用户态地址空间。注意，非共享页框可能属于几个轻量级进程，这些进程使用同一个内存描述符。
        当进程创建子进程时，就建立了共享页框。子进程页表都是从父进程中复制过来的，父子进程因此共享同一个页框。共享页框的另一个常见情形是：一个或多个进程以共享内存映射的方式访问同一个文件。
1.2、PFRA设计
        让我们看看PFRA采用的几个总的原则：
        首先释放“无害”页：在进程用户态地址空间的页回收之前，必须先回收没有被任何进程使用的磁盘与内存高速缓存中的页。实际上，回收磁盘与内存高速缓存的页框并不需要修改任何页表项。
        将用户态进程的所有页定为可回收页：除了锁定页，PFRA必须能够窃得任何用户态进程页，包括匿名页。这样，睡眠较长时间的进程将逐渐失去所有页框。
        同时取消引用一个共享页框的所有页表项的映射，就可以回收该共享页框：当PFRA要释放几个进程共享的页框时，它就清空引用该页框的所有页表项，然后回收该页框。
        只回收“未用”页：使用简化的最近最少使用(Least Recently Used，LRU)置换算法，PFRA将页分为“在用(in_use)”与“未用(unused)”。如果某页很长时间没有被访问，那么它将来被访问的可能性较小，就可以将它看作未用；另一方面，如果某页最近被访问过，那么它将来被访问的可能性较大，就必须将它看作在用。PFRA只回收未用页。
        因此，页框回收算法是几种启发式方法的混合：
        * 谨慎选择检查高速缓存的顺序。
        * 基于页年龄的变化顺序(在释放最近访问的页之前，应当释放最近最少使用的页)。
        * 区别对待不同状态的页(例如，不脏的页与脏页之间，最好把前者换出，因为前者不必写磁盘)。
二、反向映射
        Linux2.6内核能够快速定位指向同一页框的所有页表项。这个过程就叫做反向映射(reverse mapping)。
        首先，PFRA必须要确定待回收页是共享的或是非共享的，以及是映射页或是匿名页。为做到这一点，内核要查看页描述符的两个字段：_mapcount和mapping。
        _mapcount字段存放引用页框的页表项数目。计数器的初始值为-1，这表示没有页表项引用该页框；如果值为0，就表示页是非共享的；而如果值大于0,则表示页是共享的。page_mapcount函数接收页描述符地址，返回值为_mapcount + 1(这样，如返回值为1，表明是某个进程的用户态地址空间中存放的一个非共享页)。
        页描述符的mapping字段用于确定页是映射的或匿名的。说明如下：
        * 如果mapping字段空，则该页属于交换高速缓存。
        * 如果mapping字段非空，且最低位是1,表示该页为匿名页；同时mapping字段中存放的是指向anon_vma描述符的指针。
        * 如果mapping字段非空，且最低位是0,表示该页为映射页；同时mapping字段指向对应文件的address_space对象。
2.1、匿名页的反向映射

2.1.1、try_to_unmap_anon()函数
        当回收匿名页框时，PFRA必须扫描anon_vma链表中的所有线性区，仔细检查是否每个区域都存有一个匿名页，而其对应的页框就是目标页框。这一工作就是通过try_to_unmap_anon()函数实现的，它接收目标页框描述符作为参数，执行的主要步骤如下：

2.1.2、try_to_unmap_one()函数

2.2、映射页的反向映射
        与匿名页相比，映射页的面向对象反向映射所基于的思想很简单：我们总是可以获得指向一个给定页框的页表项，方法就是访问相应映射页所在的线性区描述符。因此，反向映射的关键就是一个精巧的数据结构，这个数据结构可以存放与给定页框有关的所有线性区描述符。
        每个文件对应一个优先搜索树。它存放在address_space对象的i_mmap字段中，该address_space对象包含在文件的索引节点对象中。因为映射页描述符的mapping字段指向address_space对象，所以总是能够快速检索搜索树的根。
2.2.1、优先搜索树
        PST中的每一个区间相当于一个树的节点，它由基索引(radix index)和堆索引(heap index)两个索引来标识。基索引表示区间的起始点而堆索引表示终点。PST实际上是一个依赖于基索引的搜索树，并附加一个类堆属性，即一个节点的索引不会小于其子节点的堆索引。
        Linux优先搜索树与McCreight数据结构的不同有两个重要方面：第一，Linux树不总是对称的(对称算法要耗费很多的系统空间和执行时间)；第二，Linux树被修改成存放线性区而不是线性区间。

2.2.2、try_to_unmap_file()函数

三、PFRA实现
        PFRA有几个入口(entry point)。实际上，页框回收算法的执行有三种基本情形：
        内存紧缺回收：内核发现内存紧缺。
        睡眠回收：在进入suspend-to-disk状态时，内核必须释放内存。
        周期回收：必要时，周期性激活内核线程执行内存回收算法。
        内存紧缺回收在下列几种情形下激活：
        * grow_buffer()函数(由__getblk()调用)无法获得新的缓冲区页。
        * alloc_page_buffers()函数(由create_empty_buffers()调用)无法获得页临时缓冲区首部。
        * __alloc_pages()函数无法在给定的内存管理区(memory zone)中分配一组连续页框。
        周期性回收由下面两种不同的内核线程激活：
        * kswapd内核线程，它检查某个内存管理区中空闲页框数是否已低于pages_high值的标高。
        * events内核线程，它是预定义工作队列的工作者线程；PFRA周期性地调度预定义工作队列中的一个任务执行，从而回收slab分配器处理的位于内存高速缓存中的所有空闲slab。
3.1、最近最少使用(LRU)链表
        属于进程用户态地址空间或页高速缓存的所有页被分成两组：活动链表与非活动链表。它们被统称为LRU链表。前面一个链表用于存放最近被访问过的页；后面的则存放有一段时间没有被访问过的页。显然，页必须从非活动链表中窃取。

3.1.1、在LRU链表之间移动页
        PFRA把最近访问过的页集中放在活动链表中，以便当查找要回收的页框时不扫描这些页。相反，PFRA把很长时间没有访问的页集中放在非活动链表中。当然，应该根据页是否正被访问，把页从非活动链表移到活动链表或者退回。

3.1.2、mark_page_accessed()函数
        当内核必须把一个页标记为访问过时，就调用mark_page_accessed()函数。每当内核决定一个页是否被用户态进程、文件系统层还是设备驱动程序引用时，这种情况就会发生。
3.1.3、page_referenced()函数

3.1.4、refill_inactive_zone()函数

3.2、内存紧缺回收
        当内存分配失败时激活内存紧缺回收。在分配VFS缓冲区或缓冲区首部时，内核调用free_more_memory()；而当从伙伴系统分配一个或多个页框时，调用try_to_free_pages()。
3.2.1、free_more_memory()函数

3.2.2、try_to_free_pages()函数

3.2.3、shrink_caches()函数

3.2.4、shrink_zone()函数

3.2.5、shrink_cache()函数
        shrink_cache()函数又是一个辅助函数，它的主要目的就是从管理区非活动链表取出一组页，把它们放入一个临时链表，然后调用shrink_list()函数对这个链表中的每一页进行有效的页框回收操作。shrink_cache()函数的参数与shrink_zones()一样，都是zone和sc。

3.2.6、shrink_list()函数
        我们现在讨论页框回收算法的核心部分。从try_to_free_pages()到shrink_cache()函数，前面所述这些函数的目的就是找到一组适合回收的候选页。shrink_list()函数则从参数page_list链表中尝试回收这些页，该函数的第二个参数sc是指向scan_control描述符的指针。当shrink_list()返回时，page_list链表中剩下的是无法回收的页。
        shrink_list()处理的每个页框只可能有三种结果：
        * 调用free_cold_page()函数，把页释放到管理区伙伴系统，因此被有效回收。
        * 页没有被回收，因此被重新插入page_list链表。但是shrink_list()假设不久还能回收该页。因此函数让页描述符的PG_active标志保持清0，这样页将被放回内存管理区的非活动链表。
        * 页没有被回收，因此被重新插入page_list链表。但是，或是页正被使用，或是shrink_list()假设近期无法回收该页。函数将页描述符的PG_active标志置位，这样页将被放回内存管理区的活动链表。

3.2.7、pageout()函数
        当一个脏页必须写回磁盘时，shrink_list()调用pageout()函数。
3.3、回收可压缩磁盘高速缓存的页
        PFRA处理的每个磁盘高速缓存在初始化时必须注册一个shrinker函数。shrinker函数有两个参数：待回收页框数和一组GFP分配标志。函数按照要求从磁盘高速缓存回收页，然后返回仍然留在高速缓存内的可回收页数。

3.3.1、从目录项高速缓存回收页框

3.3.2、从索引节点高速缓存回收页框

3.4、周期回收
        PFRA用两种机制进行周期回收：kswapd内核线程和cache_reap函数。前者调用shrink_zone()和shrink_slab()从LRU链表中回收页；后者则被周期性地调用以便从slab分配器中回收未用的slab。

3.4.1、kswapd内核线程

3.4.2、cache_reap()函数
        PFRA还必须回收slab分配器高速缓存的页。为此，它使用cache_reap()函数，该函数周期性地(差不多每两秒一次)地在预定事件工作队列中被调度。它的地址存放在每CPU变量reap_work的func字段，该变量为work_struct类型。
3.5、内存不足删除程序

3.6、交换标记

四、交换
        交换(swapping)用来为非映射页在磁盘上提供备份。从前面的讨论我们知道有三类页必须由交换子系统处理：
        * 属于进程匿名线性区(例如，用户态堆栈和堆)的页。
        * 属于进程私有内存映射的脏页。
        * 属于IPC共享内存区的页。
        交换子系统的主要功能总结如下：
        * 在磁盘上建立交换区(swap area)，用于存放没有磁盘映像的页。
        * 管理交换区空间。当需求发生时，分配与释放页槽(page slot)。
        * 提供函数用于从RAM中把页换出(swap out)到交换区或从交换区换入(swap in)到RAM中。
        * 利用页表项(现已被换出的换出页页表项)中的换出页标识符跟踪数据在交换区中的位置。
        总之，交换是页框回收的一个最高级特性。如果我们要确保进程的所有页框都能被PFRA随意回收，而不仅仅是回收有磁盘映像的页，那么就必须使用交换。当然，你可以用swapoff命令关闭交换，但此时随着磁盘系统负载增加，很快就会发生磁盘系统瘫痪
        交换可以用来扩展内存地址空间，使之被用户态进程有效地使用。事实上，一个大交换区可允许内核运行几个大需求量的应用，它们的内存总需求量超过系统中安装的物理内存量。但是，就性能而言，RAM的仿真还是比不上RAM本身。进程对当前换出页的每一次访问，与对RAM中页的访问比起来，要慢几个数量级。简而言之，如果性能重要，那么交换仅仅作为最后一个方案；为了解决不断增长的计算需求增加RAM芯片的容量仍然是一个最好的方法。
4.1、交换区
        从内存中换出的页存放在交换区(swap area)中，交换区的实现可以使用自己的磁盘分区，也可以使用包含在大型分区的文件中。可以定义集中不同的交换区，最大个数由MAX_SWAPFILES宏(通常被设置为32)确定。

4.1.1、创建与激活交换区

4.1.2、如何在交换区中分布页

4.2、交换区描述符

4.3、换出页描述符

4.4、激活和禁用交换区
        一旦交换区被初始化，超级用户(或者更确切地说是任何具有CAP_SYS_ADMIN权能的用户)就可以分别使用swapon和swapoff程序激活和禁用交换区。这两个程序分别使用了swapon()和swapoff()系统调用。
4.4.1、sys_swapon()服务例程

4.4.2、sys_swapoff()服务例程

4.4.3、try_to_unuse()函数

4.5、分配和释放页槽
        搜索空闲页槽的第一种方法可以选择下列两种既简单而又有些极端的策略之一：
        * 总是从交换区的开头开始。这种方法在换出操作过程中可能会增加平均寻道时间，因为空闲页槽可能已经被弄得凌乱不堪。
        * 总是从最后一个已分配的页槽开始。如果交换区的大部分空间都是空闲的(这是最通常的情况)，那么这种方法在换入操作过程中会增加平均寻道时间，因为所占用的为数不多的页槽可能是零散存放的。
        Linux采用了一种混合的方法。除非发生以下这些条件之一，否则Linux总是从最后一个已分配的页槽开始查找。
        * 已经到达交换区的末尾。
        * 上次从交换区的开头重新分配之后，已经分配了SWAPFILE_CLUSTER(通常是256)个空闲页槽。
        为了加速对空闲页槽的搜索，内核要保证每个交换区描述符的lowest_bit和highest_bit字段是最新的。这两个字段定义了第一个和最后一个可能为空的页槽，换言之，所有低于lowest_bit和高于highest_bit的页槽都被认为已经分配过。
4.5.1、scan_swap_map()函数

4.5.2、get_swap_page()函数
        get_swap_page()函数通过搜索所有活动的交换区来查找一个空闲的页槽。它返回一个新近分配页槽的换出页标识符，如果所有的交换区都填满，就返回0,该函数要考虑活动交换区的不同优先级。

4.5.2、swap_free()函数

4.6、交换高速缓存
        向交换区来回传送页会引发很多竞争条件，具体地说，交换子系统必须仔细处理下面的情形：
        多重换入：两个进程可能同时要换入同一个共享匿名页。
        同时换入换出：一个进程可能换入正由PFRA换出的页。
        交换高速缓存(swap cache)的引入就是为了解决这类同步问题。关键的原则是，没有检查交换高速缓存是否已包括了所涉及的页，就不能进行换入或换出操作。有了交换高速缓存，涉及同一页的并发交换操作总是作用于同一个页框的。因此，内核可以安全地依赖页描述符的PG_locked标志，以避免任何竞争条件。

4.6.1、交换高速缓存的实现
        在交换高速缓存中页的存放方式是隔页存放，并有下列特征：
        * 页描述符的mapping字段为NULL。
        * 页描述符的PG_swapcache标志置位。
        * private字段存放与该页有关的换出页标识符。

4.6.2、交换高速缓存的辅助函数

4.7、换出页

4.7.1、向交换高速缓存插入页框

4.7.2、更新页表项

4.7.3、将页写入交换区

4.7.4、从交换高速缓存中删除页框

4.8、换入页
        当进程试图对一个已被换出到磁盘的页进行寻址时，必然会发生页的换入。在以下条件发生时，缺页异常处理程序就会触发一个换入操作：
        * 引起异常的地址所在的页是一个有效的页，也就是说，它属于当前进程的一个线性区。
        * 页不在内存中，也就是说，页表项中的Present标志被清除。
        * 与页有关的页表项不为空，但是Dirty位清0，这意味着页表项包含一个换出页标识符。
4.8.1、do_swap_page()函数

4.8.2、read_swap_cache_async()函数