页面回收

背景

linux操作系统设计的时候提供了cache的功能,如果有空闲内存就可以用来作为cache提升性能,例如page cache缓冲硬盘中的内容,dcache,icache缓存文件系统的metadata数据,这些内容是为了提升性能而设计的,还可以再次从硬盘中重新读取来构建对象,所以这部分内容可以在内存紧张的时候可以直接释放。
另外除了提供缓存机制,还提供了缓冲机制,当写文件的时候,默认不会直接进行写入硬盘,而是会在page cache中缓冲,一直到超时或者脏页过多时进行回写操作,这样可以减少随机的IO数量和重复写操作,这部分页在内存紧张的时候需要首先回写到硬盘,之后可以进行回收.
对于匿名页,例如进程中的堆,栈区域,它是没有后备文件的,linux为匿名页创建了swap机制,可以是分区,也可以是文件,在开启了swap功能的系统中可以将匿名页当做文件一样写到磁盘中,在访问数据的时候再次从swap中恢复.

页面回收的基本思想就是将磁盘和内存看做一体,只是访问速度有差异,将经常访问的数据放到速度比较快的内存中,不经常访问的数据放到磁盘上.

用户进程的地址空间相互隔离，而内核是所有应用共用的地址空间,虽然同样都是经过页表映射访问物理内存,但是他们的访问频度相差很大,所有的进程陷入到内核中时都要访问内核空间的数据,所以对内核进行页面回收是十分不明智的.

用户进程只能看到虚拟地址空间,访问时通过页表转换到物理地址,而linux上内核对应用进程提供的内存都是虚假的,只有在实际访问的时候才按需分配,也叫lazy paging. Linux中通过MMU转换时的异常提供修复机制,也就是我们常说的缺页异常,是应用进程lazy paging的基础,理论上用户空间的所有虚拟地址都可以不分配实际的物理内存，只有实际访问时在缺页异常中进行页面分配、文件映射等操作。

linux在设计的时候是面向多种应用的，虽然页面回收包括其中的swap，背后的lazy paging机制非常影响性能，但是通过复用物理内存确实可以提升系统的寿命和运行容量。

下面系统的总结内存回收的内容，解决几个问题:

1. 哪些页面可以被回收
2. 页面回收的策略
3. 页面回收的细节实现
4. 对于不用页面的回收方式

页面回收的对象

先来看一下哪些页不能不回收，首先内核中的页绝大多数都不能别回收，linux除了它的核心代码之外还有module模块，当module被加载之后除了可以被卸载,只能使用部分export的api之外，它得到的待遇和core中的代码是相同的，总之对于加载成功的module是完全信任的。而内核空间是所有进程公用的，内核中使用的页通常是伴随整个系统运行周期的，频繁的页换入和换出是非常影响性能的，所以内核中的页基本上不能回收，不是技术上实现不了而是这样做得不偿失。
另外一种是应用程序主动申请锁定的页，它的实时性要求比较高，频繁的换入换出和缺页异常处理无法满足它对于时间上的要求，所以这部分程序可能使用mlock api将页主动锁定，不允许它进行回收。

其他用途使用的物理页基本上都是可以进行回收的，可以分成两大类:

1. 文件映射的页，包括page cache,slab中的dcache,icache,用户进程的可执行程序的代码段，文件映射页面。
   其中page cache包括文件系统的page，还包括裸块设备的buffer cache，万物皆文件，block也是一种文件，它也有关联的file,inode等。另外根据页是否是脏的，在回收的时候处理有所不同，脏页需要先回写到磁盘再回收，干净的页可以直接释放。
2. 匿名页，包括进程使用各种api（malloc,mmap,brk/sbrk）申请到的物理内存(这些api通常只是申请虚拟地址，真实的页分配发生在page fault中)，包括堆、栈，进程间通信中的共享内存，pipe，bss段，数据段，tmpfs的页。这部分没有办法直接回写，为他们创建swap区域，这些页也转化成了文件映射的页，可以回写到磁盘。

页面回收的策略

页面回收主要有两种方式:后台异步回收和同步阻塞回收，其中后台回收主要是指kswapd线程中进行的页面回收，两种方式除了是否堵塞当前的页面分配之外，回收的力度也有所不同，kswapd在zone的空闲页满足high watermark之后就停止回收，而直接回收在回收到一定数量的页(当前32个页)就会停止.
直接回收是在申请页面的路径上，它的上下文比较复杂，可能是IO栈上或者文件系统中申请的页面,这时候页面回收的时候不能进行回写磁盘的动作,因为这时候的回写可能又会触发新一轮的页面申请,陷入到死循环中。

页面回收的基准watermark

申请内存的时候，首先会检查是否内存紧张，也就是到达当前zone的空闲页帧是否小于watermark,如果低于low watermark会开始内存回收，保证申请结束后水位还能满足要求,这样尽量在内存开始紧张的时候就后台慢慢回收,此时只回收那些没有映射的页并且不需要回写的页。
申请不到内存之后，首先会wakeup kswapd线程在后台进行回收，等待短时间之后再次尝试页申请,系统希望通过kswapd后台回收方式能够得到足够的内存,这样不会影响正常的页面申请.
最后申请失败，则开始同步内存回收，这时候直接堵塞住了内存申请的路径,页面回收结束后再次开始进行页面申请。

alloc_page申请内存时会表明自身的紧急情况,用来指示当内存紧张时是否应该等待

__GFP_REPEAT：内存紧张时，等待内存回收结束，之后再次尝试，目前重试3次
__GFP_NOFAIL：内存紧张时，唤醒kswapd之后周期性再次尝试获取页，如果一直没有获取到就一直循环
__GFP_NORETRY:尝试获取内存，获取不到就返回失败
__GFP_NOMEMALLOC:清除该标志位的时候，申请的时候不管watermark是否到达min，只要有就分配给他

水位的计算可以通过vm.min_free_kbytes来调节，系统默认是1024，根据zone的大小进行调节，和min_free_kbytes成正相关的，但是规定了上下限128k-64M，这样在小内存的系统中仍然会预留足够的紧急内存处理核心模块的内存分配，在大内存系统中不会造成太多的空闲内存浪费，这些是通用场景的经验调值，可以根据自身业务场景调节的。紧急内存是为了特殊场景使用的,例如页面回收,对于脏页和匿名页需要写到磁盘上,这中间需要经过文件系统,IO栈等,他们也需要申请buffer_head之类的内存.

 * min_free_kbytes = 4 * sqrt(lowmem_kbytes)   //DMA+DMA32+NORMAL zone bytes* 16MB:    512k                                                                    * 32MB:    724k                                                                    * 64MB:    1024k * ......* 16384MB: 16384k

根据各个zone占据low mem的比例平分了min_free_kbytes，计算出每个zone的pages_min和low,high水位参数。

enum zone_watermarks {                                                              WMARK_MIN,                                                                      WMARK_LOW,                                                                      WMARK_HIGH,                                                                     NR_WMARK                                                                                                                                   
};

名称	字段描述	计算方式
min	zone的预留页面数目，如果空闲物理页面的数目低于 pages_min，那么系统的压力会比较大，此时，内存区域中急需空闲的物理页面，页面回收的需求非常紧迫。	(zone page /lowmem page)*lmin_free_kbytes
low	控制进行页面回收的最小阈值，如果空闲物理页面的数目低于 pages_low，那么内核会开始进行后台页面回收。	pages_min + pages_min/4
high	控制进行页面回收的最大阈值，如果空闲物理页面的数目多于 pages_high，则内存区域的状态是理想的。	pages_min + pages_min/2

页面回收中的LRU

Linux 中的页面回收是基于 LRU(least recently used，即最近最少使用 ) 算法的，它假设过去一段时间内频繁使用的页面，很快可能会被再次访问到，已经很久没有访问过的页面在未来较短的时间内也不会被频繁访问到。因此，在物理内存不够用的情况下，这样的页面成为被换出的最佳候选者。

LRU 算法的基本原理很简单，在访问页的时候对其进行标记,对于活动的页不断的提升它在链表中的位置,这样不经常活动的页自然就会落到LRU链表尾部。单个链表如果没有计数只能根据他们的相对位置表示两种状态：最近被访问和最近没有被访问,但是对于被访问的频次没有反应,访问1次和访问100次得到的待遇是一样的,所以内核使用了两个LRU链表来维护页的老化程度:active_list和inactive_list,这样它能够表示4种状态，对于访问频次更高的提升到active_list中，对于访问频次较低的逐渐老化到inactive_list中。

对于记录页是否被访问的方式,有的arch上提供了硬件置位,例如x86,在页表项中增加了一个accessed位,当页面被访问到的时候被MMU自动置位，之后需要通过软件来清除这个标志位。如果arch不支持硬件置位，则需要软件在每次访问页的时候进行软件标记，也就是page中的PG_referenced标志位。

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

active_list和inactive_list

当每次访问页的时候,软件会主动进行mark_page_accessed来标记当前页已经被访问过，因为不是所有的arch MMU都能自动设置accessed标记，所以需要软件主动设置标记。代码中的注释详细的说明了根据当前页面的状态进行状态迁移。

/*  * Mark a page as having seen activity. * * inactive,unreferenced    ->  inactive,referenced                             * inactive,referenced      ->  active,unreferenced                             * active,unreferenced      ->  active,referenced                               */                                                                             
void fastcall mark_page_accessed(struct page *page)                             
{                                                                               if (!PageActive(page) && PageReferenced(page) && PageLRU(page)) {           activate_page(page);                                                    ClearPageReferenced(page);                                              } else if (!PageReferenced(page)) {SetPageReferenced(page); }
}

而page_referenced()一个是测试当前page是否最近被访问过，如果当前页被访问过则清除page的访问标记。当一个page被多次映射，例如一块匿名共享内存作为进程间通信使用，一个可执行文件被执行多次，此时会有反向映射的数据结构来记录有哪些虚拟地址区域映射了该页，遍历所有的反向映射区域，检查vma对应的页表项并清除accessed位，除此之外还检查vma的flag是否被锁定VMLOCKED，通过mlock告诉系统不希望这块区域被交换出去，只要其中有vma标记被锁定或者被访问，就不会swap out这个页。和访问页时随时标记mark_page_accessed不一样，只有在后台页面回收或者直接页面回收的时候才会清除页的标记。

activate_page完成从inactive_list到active_list头部的迁移，主要是上面的mark_page_accessed中当前页PG_active=0和PG_referenced=1时进行页面迁移。早期的实现直接完成page在链表间的迁移，从3.x之后都是将页从inactive_list中摘除先放到lru缓存中，缓存满的时候再放入active_list中，lru缓存会解释。
shrink_active_list是页面回收过程中的一环，从active_list中摘除部分PG_referenced=0的页，先批量放到中间链表l_hold上，判断当前回收的压力和页面状态分别放到中间链表l_active和l_inactive中，最终批量放到zone的active_list和inactive_list上。
上面4种方式共同完成了lru两个链表的内部循环，而页面回收的时候从inactive_list中尾部获取到可回收页进行回收彻底从LRU删除，那么页又是怎么加入到LRU中的？
在页面回收的时候，对不同的页面是有倾向性的，主要是回收代价的大小，首先回收哪些没有映射的页面代价最小，例如page cache中预读的但是还没有映射的页，直接回收不需要任何IO和页表项修改，主要是内核中的可回收页。其次是经过映射的页，这部分主要是用户空间进程使用的页面，包括堆、栈、数据段、shmem共享的内存，映射文件的页。内核对于用户空间使用页都是laze paging的模式，为他们分配或者映射页主要是缺页异常触发之后才实际分配物理页。

页类型	缺页异常中fix过程	对应的lru链表
进程堆、栈、数据段中使用的匿名页，mmap共享内存映射页	do_anonymous_page do_cow_fault do_wp_page	lru_cache_add_active到活动匿名页lru链表
映射文件页	filemap_fault	add_to_page_cache_lru非活动文件页lru链表

SMP中的lru缓存

在多核系统中，操作active_list/inactive_list链表需要获取锁来防止并发访问，频繁的申请和释放页就会使得锁竞争变得激烈，所以这里使用了per-cpu的lru缓存：pagevec，通过批量操作来减少冲突的概率，当缓存满的时候批量移到active_list/inactive_list中。

struct pagevec {                                                                                                                               unsigned long nr;                                                              unsigned long cold;                                                            struct page *pages[PAGEVEC_SIZE]; //目前是14个页                                              
}; 
static DEFINE_PER_CPU(struct pagevec, lru_add_pvecs) = { 0, };              //缓存加入到inactive链表中的页    
static DEFINE_PER_CPU(struct pagevec, lru_add_active_pvecs) = { 0, };    //缓存加入到active链表中的页

页面回收的倾向性

1、 尽量不要修改page table。例如回收各种没有使用的内核cache的时候，我们直接回收，根本不需要修改页表项。而用户空间进程的页面回收往往涉及将对应的pte条目修改为无效状态。
2、 除非调用mlock将page锁定，否则所有的用户空间对应的page frame都应该可以被回收。
3、 如果一个page frame被多个进程共享，那么我们需要清除所有的pte entry，之后才能回收该页面。
4、 不要回收那些最近访问过的page frame，或者说优先回收那些最近没有访问的page frame。
5、 尽量先回收那些不需要磁盘IO操作的page frame。

页面回收的过程

扫描控制

页面回收需要扫描不同的页，而当前内存的紧急情况也分不同的等级，包括是否开启了swap，是否允许writeback操作等，在页面回收过程中就构造了scan_control对象来指示页面回收的范围。另外回收时还有priority来指示当前页面回收的激烈程度,初始值为12,逐步递减,当前zone需要扫描的页面=LRU链表上的页面除以(2^priority)，每次页面回收结束后，如果回收的页面还是不能满足页面申请的要求，伴随着priority的递减逐步增加页面扫描的数量。

其中初始的扫描控制参数如下,

    struct scan_control sc = {                                                  .gfp_mask = gfp_mask,.may_writepage = !laptop_mode,	//是否允许回收匿名页和脏页.swap_cluster_max = SWAP_CLUSTER_MAX,	//直接回收页数量大于该值时结束回收.may_swap = 1, //是否开启了swap.swappiness = vm_swappiness, //文件映射页和匿名页回收时的倾向，范围从0-100，默认60，值越高对匿名页回收越积极 };

链表转移

1. 扫描active_list,根据当前优先级选择需要扫描zone,当active_list上页太少时就不再扫描了,可以通过不断调高优先级加大扫描力度.为了减少对于lru链表的竞争,在收缩active_list链表的时候创建了三个临时链表:l_hold,l_active,l_inactive,批量从active_list中移除和添加页.
   首先从active_list链表尾部摘取需要扫描的页,放到临时链表l_hold中,这样后续的处理可以访问在l_hold中,之后检查是否回收这些扫描过的页.如果当前不需要回收页表映射过的页,将这这部分页从l_hold移到l_active中.
   如果当前没有可用的swap,将匿名页从l_hold移到l_active中.
   再次检查是否访问过该页面,不回收最近访问过的页,将页从l_hold移到l_active中.
   剩余的页都是可以回收的,从l_hold中转移到l_inactive中;之后将l_active批量加入到active_list的lru缓存中,将l_inactive中的页批量加入到inactive_list的lru缓存中.
2. 扫描inactive_list,直接从链表尾部摘除页到page_list上,之后shrink_page_list开始进行页面回收,回收失败的页仍然保留在page_list,按照当前状态加回到对应的lru链表上.

slab的回收

并不是所有的slab都可以回收的，只有那些注册了shrinker的才能收缩，在申请和释放的时候他们也会维护类似于LRU这样的老化链表，当收缩的时候进行回收

页面回收

1. 页面回收不包括PG_locked,PG_writeback的页,前者表示页正在使用中,后者表示页正在被回写
2. 再次检查页是否被访问过,准备回收的页PG_active=0,PG_referenced=0并且已经不在lru链表中了,当页被访问过之后PG_referenced=1,但是PG_active一定不会被置位,它又不是新分配的页,不能凭空从inactive_list直接跃升到active_list.
3. 对于匿名页,需要在swap中分配位置,如果swap已经满的情况就不能swap out了.之后page先加入到swap cache中,它是类似于page cache一样的结构,因为一个页可能在多个vma中被映射使用,只有当所有的区域都解除了映射之后,它才会从swap cache中移除,实现页面回收.在加入到swap cache之后它标记当前页PG_dirty,在下面的pageout中将页内容先写入到磁盘.
4. 对于页表映射的页需要逐个解除映射,linux使用反向映射来管理多个虚拟地址和物理页的对应关系,对于匿名页和文件映射页都是遍历反向映射区间.对于匿名页,需要更新它在swap中的位置到页表项中,这样在缺页中断中仍然能够从swap中恢复数据,并且将反向映射关系进行销毁.对于文件页来说就比较简单了,只需要将反向映射解除就OK了.
   
5. 对于需要进行回写的页进行处理,包括文件脏页,匿名页。文件脏页都是基于文件系统的，文件系统定义的address_space->a_ops->writepage进行实际回写，它再往下就属于IO栈的东西了；对于匿名页，它是属于swap管理的，有自己的address_space和address_space_operations。当页回写成功,释放页的引用计数,最后一个引用计数释放时将页返回给buddy系统.

static const struct address_space_operations swap_aops = {.writepage  = swap_writepage,
}

6. 对于不能回收的页和回收失败的页,将他们再次返回,根据page的状态加入到LRU链表中

页面回收终止条件

1.对于kswapd中的页面回收,当zone的page高于high watermark之后就会停止页面回收
2.对于直接页面回收,每次回收页面数量大于SWAP_CLUSTER_MAX就会终止,如果扫描页面较多,它会主动wakeup pdflush线程将脏页回写来释放更多的页.
3.如果回收不到任何的页,代表系统已经到了绝境了,为了生存开始自残:OOM,和斗地主一样,哪个进程占用的物理内存最多就它释放物理页.

reflink:
https://www.ibm.com/developerworks/cn/linux/l-cn-pagerecycle/
http://www.wowotech.net/memory_management/page_reclaim_basic.html