kswapd是linux中用于页面回收的内核线程。页面回收，并不是回收得越多越好，而是力求达到一种balanced。因为页面回收总是以cache丢弃、内存swap、等为代价的，对系统性能会有一定程度的影响。
1 LRU链表
在最近几十年操作系统的发展过程中，出现了很多的页面置换算法，其中每一个页面置换算法都有各自的优缺点。但是linux内核中采用的主要是经典的LRU链表算法和第二次机会算法。
。LRU(Least Recently Used)：最近最少使用。根据局部性原理，LRU假定最近不使用的页面在较短的时间内也不会频繁使用。
所以在内存不足的时候，这些页面将成为被换出的候选者。内核使用双向链表来定义LRU链表，并且根据页面的类型将LRU链表分为LRU_ANON和LRU_FILE。每种类型根据页面的活跃性分为活跃性LRU链表和不活跃性LRU链表，所以内核提供了以下链表
- 不活跃匿名页面链表 LRU_INACTIVE_ANON
- 活跃匿名页面链表 LRU_ACTIVE_ANON
- 不活跃文件映射页面链表 LRU_INACTIVE_FILE
- 活跃文件映射页面链表 LRU_ACTIVE_FILE
- 不可回收的页面链表 LRU_UNEVICTABLE
LRU链表要被分成这样，是因为当内存短缺时，总是优先换出文件映射的文件缓存页面，而不是匿名页面。因为在大多数情况下，文件缓存页面不需要被回写到磁盘，除非页面内容被修改了，而匿名页面总是要在写入交换分区之后，才能被换出。
页面回收时，会优先回收INACTIVE的页面，只有当INACTIVE页面很少时，才会考虑回收ACTIVE页面。LRU是双向链表，内核根据页面类型(匿名和文件)与活跃性(活跃和不活跃)，分红5种类型LRU链表：
#define LRU_BASE 0
#define LRU_ACTIVE 1
#define LRU_FILE 2
enum lru_list {
LRU_INACTIVE_ANON = LRU_BASE,-------------------------不活跃匿名页面链表，须要交换分区才能回收
LRU_ACTIVE_ANON = LRU_BASE + LRU_ACTIVE,---------------活跃匿名页面链表
LRU_INACTIVE_FILE = LRU_BASE + LRU_FILE,---------------不活跃文件映射页面链表，最优先回收
LRU_ACTIVE_FILE = LRU_BASE + LRU_FILE + LRU_ACTIVE,----活跃文件映射页面链表
LRU_UNEVICTABLE,---------------------------------------不可回收页面链表，禁止换出
NR_LRU_LISTS
};
struct lruvec {
struct list_head lists[NR_LRU_LISTS];
struct zone_reclaim_stat reclaim_stat;
#ifdef CONFIG_MEMCG
struct zone *zone;
#endif
};
struct zone {
...
/* Fields commonly accessed by the page reclaim scanner */
spinlock_t lru_lock;
struct lruvec lruvec;
...
}
经典LRU链表算法如下图所示
。第二次机会算法：该算法是在经典LRU算法基础上做了一些改进，当选择页面置换时，依然和经典的LRU算法一样，选择最早置入链表的页面，即在链表末尾的页面。
- 第二次机会算法设置了一个访问状态位，如果访问位是1，就给他第二次机会，选择下一个页面来换出。
- 当该页面得到第二次机会时，它的访问位被清0，如果该页面在此期间再次被访问过，则访问位设置为1。于是给了第二次机会的页面将不会被淘汰，直至其他页面被淘汰。
2. 页面回收机制
在页面回收的过程中，我们会遇到很多意想不到的情况，如大量脏页、大量正在回写的页面堵塞在块设备的IO通道上等问题，这些会影响页面回收机制的性能，甚至应用程序的用户体验。我们来接上一章学习页面回收的流程，关注于shrink_node开始。
static bool shrink_node(pg_data_t *pgdat, struct scan_control *sc)
{
...
do {//循环回收内存
memcg = mem_cgroup_iter(root, NULL, &reclaim);
do {// //遍历该cgroup，回收内存
if (mem_cgroup_low(root, memcg)) {
if (!sc->may_thrash)
continue;
mem_cgroup_events(memcg, MEMCG_LOW, 1);
}
//针对该cgroup回收内存，主要是LRU链表
shrink_node_memcg(pgdat, memcg, sc, &lru_pages);
node_lru_pages += lru_pages;
if (memcg)//调用系统注册的所有shrinker，回收slab缓存
shrink_slab(sc->gfp_mask, pgdat->node_id,
memcg, sc->nr_scanned - scanned,
lru_pages);
//直接回收和kswap路径需要扫描node上所有内存，但其他情况下，只要
//回收到足够的空闲内存就可以停止扫描
if (!global_reclaim(sc) &&
sc->nr_reclaimed >= sc->nr_to_reclaim) {
mem_cgroup_iter_break(root, memcg);
break;
}
while(((memcg = mem_cgroup_iter(root, memcg, &reclaim))))
vmpressure(sc->gfp_mask, memcg, false,
sc->nr_scanned - scanned,
sc->nr_reclaimed - reclaimed);
if (global_reclaim(sc))
shrink_slab(sc->gfp_mask, pgdat->node_id, NULL,
sc->nr_scanned - nr_scanned,
node_lru_pages);
if (reclaim_state) {
sc->nr_reclaimed += reclaim_state->reclaimed_slab;
reclaim_state->reclaimed_slab = 0;
}
/* Record the subtree's reclaim efficiency */
vmpressure(sc->gfp_mask, sc->target_mem_cgroup, true,
sc->nr_scanned - nr_scanned,
sc->nr_reclaimed - nr_reclaimed);
if (sc->nr_reclaimed - nr_reclaimed)//本次有回收到内存，置位reclaimable标志
reclaimable = true;
//循环条件是此时空闲内存还无法满足进程需要也无法满足内存整理需求
//且非活动LRU链表页面数量大于两倍需回收页面
}while (should_continue_reclaim(pgdat, sc->nr_reclaimed - nr_reclaimed,
sc->nr_scanned - nr_scanned, sc));
...
}
shrink_node函数用于扫面内存节点中所有可用于回收的页面，其主要的操作如下：
- do_while循环的判断条件为should_continue_reclaim，通过这一轮中回收页面的数量和扫面页面的数量来判断是否需要继续扫面
- 首先遍历mem_cgroup，调用shrink_node_memcg回收页面
- shrink_slab函数调用内存管理系统的shrinker接口，很多子系统会注册shrinker接口来回收slab对象
- vmpressure函数通过计算nr_scanned/nr_reclaimed比例来判断内存压力
不管是direct reclaim，还是kswapd，最终都是调用shrink_zone() --> shrink_page_list() 进行回收操作。
static unsigned long shrink_list(enum lru_list lru, unsigned long nr_to_scan,
struct lruvec *lruvec, struct scan_control *sc)
{
if (is_active_lru(lru)) {
if (inactive_list_is_low(lruvec, is_file_lru(lru), sc))
shrink_active_list(nr_to_scan, lruvec, sc, lru);
return 0;
}
return shrink_inactive_list(nr_to_scan, lruvec, sc, lru);
}
- 当LRU链表属于活跃的LRU链表(包括匿名页面或文件映射页面)并且不活跃LRU的链表页面占比比较少时，调用shrink_active_list来收割和迁移一部分活跃的页面到不活跃的LRU链表中
- 调用shrink_inactive_list函数扫面不活跃的LRU链表并且回收页面
shrink_inactive_list --> shrink_page_list 将从inactive list尾端移除选定数目的页面，进行释放。
回收一个页面之前，如果该页面当前是被映射的（根据struct page的_mapcount域判断），需要调用try_to_unmap()，通过reserve mapping更改所有指向这个页面的PTEs。对于anonymous page，还需要在swap space中分配slot，并且将这个page标记为dirty的。anonymous page是没有backing store的，从dirty的角度，它可以算是一直dirty的。
前面提到过，不是所有的页面都可以被回收的。如果检测到页面的flag是PG_locked或者是PG_reserved的，则只能跳过。对于正在回写的（flag是PG_writeback的），通常也是放弃回收，有这功夫去等待回写完成，还不如去找链表上其他的clean page。
之后，对于flag是PG_dirty的页面，启动pageout()将这些页面备份或者同步到外部磁盘，这里“备份”针对的是anonymous page，“同步”针对的是page cache。
3. 内存回收门限
什么情况下触发direct reclaim，什么情况下又会触发kswapd，是由内存的watermark决定的”，那这个"watermark"到底是如何发挥作用的呢？
3.1 Kswapd与Watermark
Linux中物理内存的每个zone都有自己独立的min, low和high三个档位的watermark值，在代码中以struct zone中的_watermark[NR_WMARK]来表示。
enum zone_watermarks {
WMARK_MIN,
WMARK_LOW,
WMARK_HIGH,
NR_WMARK
};
#define min_wmark_pages(z) (z->watermark[WMARK_MIN])
#define low_wmark_pages(z) (z->watermark[WMARK_LOW])
#define high_wmark_pages(z) (z->watermark[WMARK_HIGH])
在进行内存分配的时候，如果分配器（比如buddy allocator）发现
- 当前空余内存的值低于"low"但高于"min"说明现在内存面临一定的压力
那么在此次内存分配完成后，kswapd将被唤醒，以执行内存回收操作。在这种情况下，内存分配虽然会触发内存回收，但不存在被内存回收所阻塞的问题，两者的执行关系是异步的。
对于kswapd来说，要回收多少内存才算完成任务呢？只要把空余内存的大小恢复到"high"对应的watermark值就可以了，当然，这取决于当前空余内存和"high"值之间的差距，差距越大，需要回收的内存也就越多。"low"可以被认为是一个警戒水位线，而"high"则是一个安全的水位线。
-
如果内存分配器发现空余内存的值低于了"min"，说明现在内存严重不足
- 一种是默认的操作，此时分配器将同步等待内存回收完成，再进行内存分配，也就是 direct reclaim
- 如果内存分配的请求是带了PF_MEMALLOC标志位的，并且现在空余内存的大小可以满足本次内存分配的需求，那么也将是先分配，再回收
那谁有这样的权利，可以在内存严重短缺的时候，不等待回收而强行分配内存呢？其中的一个人物就是kswapd啦，因为kswapd本身就是负责回收内存的，它只需要占用一小部分内存支撑其正常运行(就像启动资金一样)，就可以去回收更多的内存(赚更多的钱回来)。
- 虽然kswapd是在"low"到"min"的这段区间被唤醒加入调度队列的，但当它真正执行的时候，空余内存的值可能已经掉到"min"以下了。可见，"min"值存在的一个意义是保证像kswapd这样的特殊任务能够在需要的时候立刻获得所需内存。
kswapd0 定期扫描内存的使用情况，并根据剩余内存落在这三个阈值的空间位置，进行内存的回收操作。
- 剩余内存小于页最小阈值，说明进程可用内存都耗尽了，只有内核才可以分配内存。
- 剩余内存落在页最小阈值和页低阈值中间，说明内存压力比较大，剩余内存不多了。这时 kswapd0 会执行内存回收，直到剩余内存大于高阈值为止。
- 剩余内存落在页低阈值和页高阈值中间，说明内存有一定压力，但还可以满足新内存请求。
- 剩余内存大于页高阈值，说明剩余内存比较多，没有内存压力
3.2 Watermark的取值
那么这三个watermark值的大小又是如何确定的呢？ZONE_HIGHMEM的watermark值比较特殊，但因为现在64位系统已经不再使用ZONE_HIGHMEM了，为了简化讨论，以下将以不含ZONE_HIGHMEM，且只有一个node]的64位系统为例进行讲解。
在这种系统中，总的"min"值约等于所有zones可用内存的总和乘以16再开平方的大小，可通过"/proc/sys/vm/min_free_kbytes"查看和修改。假设可用内存的大小是4GiB，那么其对应的"min"值就是8MiB ( [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-cczX9OAe-1616336160145)(https://www.zhihu.com/equation?tex=%5Csqrt%7B4%2A1024%2A1024%2A16%7D%3D8192)] )。
int __meminit init_per_zone_wmark_min(void)
{
unsigned long lowmem_kbytes;
int new_min_free_kbytes;
lowmem_kbytes = nr_free_buffer_pages() * (PAGE_SIZE >> 10);
new_min_free_kbytes = int_sqrt(lowmem_kbytes * 16);
if (new_min_free_kbytes > user_min_free_kbytes) {
min_free_kbytes = new_min_free_kbytes;
if (min_free_kbytes < 128)
min_free_kbytes = 128;
if (min_free_kbytes > 65536)
min_free_kbytes = 65536;
} else {
pr_warn("min_free_kbytes is not updated to %d because user defined value %d is preferred\n",
new_min_free_kbytes, user_min_free_kbytes);
}
return 0;
}
这里的"min"值有个下限和上限，就是最小不能低于128KiB，最大不能超过65536KiB。在实际应用中，通常建议为不低于1024KiB。
得到总的"min"值后，我们就可以根据各个zone在总内存中的占比，通过do_div()计算出它们各自的"min"值。假设总的"min"值是8MiB，有ZONE_DMA和ZONE_NORMAL两个zones，大小分别是128MiB和896MiB，那么ZONE_DMA和ZONE_NORMAL的"min"值就分别是1MiB和7MiB。
void __setup_per_zone_wmarks(void)
{
unsigned long pages_min = min_free_kbytes >> (PAGE_SHIFT - 10);
for_each_zone(zone) {
tmp = (u64)pages_min * zone->managed_pages;
do_div(tmp, lowmem_pages);
zone->watermark[WMARK_MIN] = tmp;
zone->watermark[WMARK_LOW] = min_wmark_pages(zone) + (tmp >> 2);
zone->watermark[WMARK_HIGH] = min_wmark_pages(zone) + (tmp >> 1);
...
}
一个zone的"low"和"high"的值都是根据它的"min"值算出来的，"low"比"min"的值大1/4左右，"high"比"min"的值大1/2左右，三者的比例关系大致是4:5:6。
使用"cat /proc/zoneinfo"可以查看这三个值的大小（注意这里是以page为单位的）：
总结
- 每个zone区中都有这三个参数，其中从小到大的顺序依次为watermark[min],watermark[low],watermark[high].
- 当空闲中内存低于watermark[low]，开始启用内核守护线程kswapd进行内存回收(每个zone中都会有一个kswapd)，直到该zone的空闲页数量达到watermark[high]之后才停止回收行为
- 如果上层申请内存的速度太快，导致空闲内存降至watermark[low]，内核就会进行drict reclaim(直接内存回收)，也就是直接在应用程序的上下文中进行页面回收，再用回收的内存满足内存申请。所以，当有这样的情况发生时，就会阻塞应用程序的执行，会带来一定的响应延迟，甚至可能触发OOM(out of memory）。因为watermark[min]以下的内存空间是留给系统特殊使用的，所以不会给用户态程序用。
3.3 Watermark的调节
为了尽量避免出现direct reclaim，我们需要空余内存的大小一直保持在"min"值之上。在网络收发的时候，数据量可能突然增大，需要临时申请大量的内存，这种场景被称为" burst allocation "。此时kswapd回收内存的速度可能赶不上内存分配的速度，造成direct reclaim被触发，影响系统性能。
在内存分配时，只有"low"与"min"之间之间的这段区域才是kswapd的活动空间，低于了"min"会触发direct reclaim，高于了"low"又不会唤醒kswapd，而Linux中默认的"low"与"min"之间的差值确实显得小了点。
为此，Android的设计者在Linux的内存watermark的基础上，增加了一个" extra_free_kbytes "的变量，这个"extra"是额外加在"low"与"min"之间的，它在保持"min"值不变的情况下，让"low"值有所增大。假设你的"burst allocation"需要100MiB(100*1024KiB)的空间，那么你就可以把"extra_free_kbytes"的值设为102400。
于是，设置各个zone的watermark的代码变成了这样：
void __setup_per_zone_wmarks(void)
{
unsigned long pages_min = min_free_kbytes >> (PAGE_SHIFT - 10);
unsigned long pages_low = extra_free_kbytes >> (PAGE_SHIFT - 10);
for_each_zone(zone) {
min = (u64)pages_min * zone->managed_pages;
do_div(min, lowmem_pages);
low = (u64)pages_low * zone->managed_pages;
do_div(low, vm_total_pages);
zone->watermark[WMARK_MIN] = min;
zone->watermark[WMARK_LOW] = min + low + (min >> 2);
zone->watermark[WMARK_HIGH] = min + low + (min >> 1)
...
}
和Linux中对应的代码相比，主要就是多了这样一个"extra_free_kbytes"，该参数可通过设置"/proc/sys/vm/extra_free_kbytes"来调节。关于Andoird这个patch的详细信息，请参考这个提交记录。
在Android的机器(基于4.4的Linux内核)上用"cat /proc/zoneinfo"查看一下：
4 总结
进程在申请内存的时候，发现该 zone 的 freelist 上已经没有足够的内存可用，所以不得不去从该 zone 的 LRU 链表里回收 inactive 的page，这种情况就是 direct reclaim（直接回收）。direct reclaim 会比较消耗时间的原因是，如果回收的是 dirty page，就会触发磁盘 IO 的操作，它会首先把 dirty page 里面的内容给回写到磁盘作同步，再去把该 page 给放到 freelist 里。
内核的页回收机制有两种：后台周期性回收和直接回收。
后台回收是有一个内核线程 kswapd 来做，当内存里 free 的 pages 低于一个水位（page_low）时，就会唤醒该内核线程，然后它从 LRU 链表里回收 page cache 到内存的 free_list 里头，它会一直回收直至 free 的 pages 达到另外一个水位 page_high 才停止。
