linux内存回收机制
1 回收哪些页面
Page cache;
用户地址空间的内存映射页面；
Slab缓存：如dentry和inode cache；
匿名页：进程堆栈和mmap匿名映射内存区；回收前先换置到swap；
2 何时回收
Kswapd定期唤醒：当系统空闲内存小于阈值则进行页面回收；
直接页面回收：假设操作系统需要通过伙伴系统为用户进程分配一大块内存，或者需要创建一个很大的缓冲区，而当时系统中的内存没有办法提供足够多的物理内存以满足这种内存请求，这时候，操作系统就必须尽快进行页面回收操作；
OS尝试内存回收后仍无法获取足够页面，则调用find_bad_process并进行OOM kill；
3 如何回收
基于LRU算法；每个zone维护两个LRU链表
struct zone {
……
spinlock_t lru_lock;
struct list_head active_list;
struct list_head inactive_list;
unsigned long nr_active;
unsigned long nr_inactive;
……
}
PG_active/PG_referenced用于标识页面活跃度，前者标识页面时活跃的；后者表示页面最近是否被访问过，每访问一次便会置位；
注：假如只是用一个标志符，在页面被访问时，置位该标志符，之后该页面一直处于活跃状态，如果操作系统不清除该标志位，那么即使之后很长一段时间内该页面都没有或很少被访问过，该页面也还是处于活跃状态。为了能够有效清除该标志位，需要有定时器的支持以便于在超时时间之后该标志位可以自动被清除。然而，很多 Linux 支持的体系结构并不能提供这样的硬件支持，所以 Linux 中使用两个标志符来判断页面的活跃程度。
Linux依据这两个字段将page在active_list和inactive_list之间移动；
注：1 表示函数 mark_page_accessed()，2 表示函数 page_referenced()，3 表示函数 activate_page()，4 表示函数 shrink_active_list()
不管是kswapd还是直接页面回收，最终都调用shrink_slab和shrink_zone；
直接页面回收：反复调用这两个函数，若特定循环次数内没能成功释放N个page，则调用OOM killer；
Kswapd：对每个zone都调用shrink_zone()；
3.1 Shrink_slab原理
先向操作系统内核注册 shrinker函数，会在内存较少的时候主动释放一些该磁盘缓存占用的空间。
函数 shrink_slab() 会遍历 shrinker 链表，从而对所有注册了 shrinker 函数的磁盘缓存进行处理。
注册 shrinker 是通过函数 set_shrinker() 实现的，解除 shrinker 注册是通过函数 remove_shrinker() 实现的。当前，Linux 操作系统中主要的 shrinker 函数有如下几种：
shrink_dcache_memory()：该 shrinker 函数负责 dentry 缓存。
shrink_icache_memory()：该 shrinker 函数负责 inode 缓存。
mb_cache_shrink_fn()：该 shrinker 函数负责用于文件系统元数据的缓存。
3.2 Shrink_zone原理
1 通过shrink_active_list()将页面从active移到inactive list；
2 调用shrink_inactive_list()将inactive list的页放入临时链表，最终调用shrink_page_list()回收
3.2.1 Swappiness的意义
上文提到的shrink_zone() 会调用 shrink_lruvec()，而active/inactive list又各分为anon匿名页和file cache映射页链表，总计4个LRU；
而swappines只针对anon page，即便其为0也有可能执行swap。
vmscan.c中的get_scan_coun()
1. 首先如果系统禁用了swap或者没有swap空间，则只扫描file based的链表，即不进行匿名页链表扫描
代码：
if (!sc->may_swap || (get_nr_swap_pages() <= 0)) {
scan_balance = SCAN_FILE;
goto out;
}
2. 如果当前进行的不是全局页回收（cgroup资源限额引起的页回收），并且swappiness设为0，则不进行匿名页链表扫描，
代码：
if (!global_reclaim(sc) && !vmscan_swappiness(sc)) {
scan_balance = SCAN_FILE;
goto out;
}
3. 如果进行链表扫描前设置的priority(这个值决定扫描多少分之一的链表元素)为0，且swappiness非0，则可能会进行swap
代码：
if (!sc->priority && vmscan_swappiness(sc)) {
scan_balance = SCAN_EQUAL;
goto out;
}
4. 如果是全局页回收，并且当前空闲内存和所有file based链表page数目的加和都小于系统的high watermark，则必须进行匿名页回收，则必然会发生swap
代码：
anon = get_lru_size(lruvec, LRU_ACTIVE_ANON) +
get_lru_size(lruvec, LRU_INACTIVE_ANON);
file = get_lru_size(lruvec, LRU_ACTIVE_FILE) +
get_lru_size(lruvec, LRU_INACTIVE_FILE);
if (global_reclaim(sc)) {
free = zone_page_state(zone, NR_FREE_PAGES);
if (unlikely(file + free <= high_wmark_pages(zone))) {
scan_balance = SCAN_ANON;
goto out;
}
}
5. 如果系统inactive file链表比较充足，则不考虑进行匿名页的回收，即不进行swap
代码：
if (!inactive_file_is_low(lruvec)) {
scan_balance = SCAN_FILE;
goto out;
}
注：每个zone有min/low/high 3个值，而high watermark指的是最后一个，这3个值依据vm.min_free_kbytes设置
3.2.2 反向映射
回收物理页前需要解除所有关联该页的页表项，而共享内存中的页可能被多个进程引用，因此需要一种机制快速定位页表项；
2.4要遍历所有进程；
2.5引入反向映射，每个物理页维护一个页表项链表；
2.6引入基于对象的反向映射，每个物理页设置一个反向映射链表，链表节点为vm_area_struct结构，其通过mm_struct找到pgd进而找到相应页表项；
struct page {
atomic_t _mapcount; --初始值是 -1，每增加一个使用者，该计数器加 1
union {
……
struct {
……
struct address_space *mapping; --如果最低位置位，为指向 anon_vma 结构（用于匿名页面）的指针；否则为 address_space 指针（用于基于文件映射的页面）。
};
……
};
对于匿名页面来说，页面虽然可以是共享的，但是一般情况下，共享匿名页面的使用者的数目不会很多；而对于基于文件映射的页面来说，共享页面的使用者的数目可能会非常多，使用优先级搜索树这种结构可以更加快速地定位那些引用了该页面的虚拟内存区域。操作系统会为每一个文件都建立一个优先级搜索树，其根节点可以通过结构 address_space 中的 i_mmap 字段获取。
注：LRU缓存
页面根据其活跃程度会在 active 链表和 inactive 链表之间来回移动，如果要将某个页面插入到这两个链表中去，必须要通过自旋锁以保证对链表的并发访问操作不会出错。为了降低锁的竞争，Linux 提供了一种特殊的缓存：LRU 缓存，用以批量地向 LRU 链表中快速地添加页面。有了 LRU 缓存之后，新页不会被马上添加到相应的链表上去，而是先被放到一个缓冲区中去，当该缓冲区缓存了足够多的页面之后，缓冲区中的页面才会被一次性地全部添加到相应的 LRU 链表中去。
LRU 缓存用到了 pagevec 结构，如下所示 :
struct pagevec {
unsigned long nr;
unsigned long cold;
struct page *pages[PAGEVEC_SIZE];
};
lru_cache_add() 和 lru_cache_add_active()。前者用于延迟将页面添加到 inactive 链表上去，后者用于延迟将页面添加到 active 链表上去。这两个函数都会将要移动的页面先放到页向量 pagevec 中，当 pagevec 满了（已经装了 14 个页面的描述符指针），pagevec 结构中的所有页面才会被一次性地移动到相应的链表上去。
参考资料
http://www.ibm.com/developerworks/cn/linux/l-cn-pagerecycle/index.html?ca=dat
http://www.douban.com/note/349467816/
