kswapd

kswapd是linux中用于页面回收的内核线程。

页面回收，并不是回收得越多越好，而是力求达到一种balanced。因为页面回收总是以cache丢弃、内存swap、等为代价的，对系统性能会有一定程度的影响。而balanced，就是既要保证性能，又要应付好新来的页面分配请求。

在讨论kswapd如何工作之前，我们先得搞清楚balanced是如何定义的。

物理内存在kernel中主要有这么几个层次的划分：全体内存、一个NUMA节点的内存、一个NUMA节点中的一个zone的内存（参见《linux内核内存管理浅析》）。维护空闲页面的伙伴系统和维护可回收页面的LRU都工作在zone这一层，所以具体的内存回收操作也是在这一层进行的。

kernel中追求的balanced并不针对全体内存，而是针对每一个NUMA节点的内存而言的。因为NUMA系统中的每一个节点都是并列的，统一考虑整体的balanced其实没什么意义。所以对应于系统中的每个NUMA节点都会有一个kswapd线程来进行balance。我们后续的讨论都只针对单个NUMA节点而言。

单个NUMA节点的内存的balanced由pgdat_balanced函数来判断。pgdat_balanced并不是绝对的，而是带有限定条件order和classzone_idx的。这表示：当我们考查下标为classzone_idx的zone时，2^order的连续内存页面是否达到balanced。

有点绕……先来说说order和classzone_idx分别是什么？

在kernel中，一个NUMA节点的内存被分成若干个zone：比如DMA16、DMA32、NORMAL、HIGH、等等。比如DMA16，这是为16位总线的外设服务的，由于这些外设总线宽度不够，只能访问物理地址在2^16以下的内存，所以物理地址在2^16以下的内存被划为DMA16区域，作为稀缺资源，尽量专供这些16位总线的外设驱动使用。当然，其他地方使用这些DMA16的内存也完全没有问题。DMA32跟DMA16类似。NORMAL是内核可以直接访问的内存，跟HIGH相对应，HIGH是内核不能直接访问的高端内存。出现这种问题的原因是32位系统下地址空间有限，总共4G的地址空间内核让出3G给用户空间，导致内核能够直接访问的内存只能在1G以下，高端内存需要临时建立映射才能访问。而64位系统因为地址空间非常之大，远远大于现有系统的物理内存，所以内核可以有足够的地址空间来直接访问内存，HIGH区域也就不存在了。总的来说，这些zone下标越大，zone里的内存使用范围就越小，小下标zone的内存用途总是包含大下标zone的。所以在进行内存分配的时候，总是会优先尝试在能满足当前需要的下标最大的zone里面的去分配，不行再尝试下标更小的zone；

至于order，我们知道zone里面的内存是用伙伴系统来管理的，伙伴系统里面有很多个freelist，分别是2^n个连续页面的空闲链表。而order就代表这里的n，order越大，意味着需要越多的连续页面。跟前面的classzone_idx类似，大order对小order也是有包含关系的，如果你需要2个连续页面，其实是可以将4个连续页面拆散来使用的。反过来则不成立，任意2个页面一般不能拼成连续页面，除非它们地址连续。但是要想从茫茫人海中找到相连的那两个页面，就不是那么容易了。

那么具体pgdat_balanced怎么定义呢？因为pgdat_balanced是基于zone的balanced的，所以还得先讨论一下zone的balanced。

zone的balanced由zone_balanced函数来判断，这是针对于order来说的。zone_balanced有两个条件：

1、zone内的空闲内存超过高水位

水位是在内存初始化的时候根据每个zone的内存大小自动计算出来的，每个zone可能有不同的水位。具体计算水位的算法可能各个kernel版本不尽相同，比如某个版本是这么算的：对于非高端内存来说（64位机器上已经不存在高端内存了），min_watermark根据各个zone的内存占比，瓜分1024个page；low_watermark在此基础上增加25%；high_watermark在此基础上增加50%。（可以通过/proc/zoneinfo看到系统中的每一个zone，及其free pages和watermark的情况。）这里的高水位对于现在的大内存机器来说，其实只是九牛一毛。由这个高水位来作为判断zone_balanced的基础，可见内核在内存balance的问题上还是很注重系统性能的；

2、要求zone内的内存在0到给定order之间平衡分布

如：总的内存超过高水位、order-1及以上的内存超过高水位的1/2、order-2及以上的内存超过高水位的1/4、……、一直到所要求的order。

为什么针对于order的内存balanced不仅仅关心order阶的内存，而是关心0至order阶的所有内存呢？因为高order的连续内存是稀缺资源。如果内存分布不平衡，低order的内存请求可能因为低order内存的暂时缺货而不得不将高order所对应的连续内存进行分拆。这种浪费是要尽量避免的。并且这样的分拆可能导致高order内存耗尽，而导致满足不了对指定order的内存分配需求。

那么为什么针对于order的内存balanced又仅仅只关心0至order阶的所有内存、而不关心大于order阶的内存呢？当我们需要检查针对于order的zone_balanced时，其实是说明我们需要使用这个zone内2^order的连续页面。由于连续页面回收不易，也不是系统内最普遍的需求（给用户空间使用的内存基本上都是order-0的，不考虑hugepage这样的特殊情况），所以更高的order就不要考虑了。后面会看到，kswapd默认只针对order-0进行回收。

至于pgdat_balanced，要分两种情况：

1、如果针对的order是0，则要求下标小于等于classzone_idx的zone都满足zone_balanced；

2、如果针对的order不为0，只要求下标小于等于classzone_idx的这些zone里面，满足zone_balanced的zone所占的内存比重达到25%。比方说下标小于等于classzone_idx的zone有两个，第一个zone内的内存大小是第二个zone的三倍（第二个zone占两者总合的25%），那么只要第二个zone是balanced的，就认为pgdat_balanced成立；

其实pgdat_balanced就是要求下标为0~classzone_idx的zone都balanced，但是对于order大于0的情况条件有所放宽。前面也提到过，高order的连续内存其实并不是那么容易就回收到的，而且这也不是系统是最普遍的需求，所以就放宽一些吧。至少满足条件且达到zone_balanced的zone覆盖了25%以上的内存，还不至于太惨。

为什么这里也不仅仅只关心下标为classzone_idx的zone，而是0~classzone_idx呢？前面也说过，小下标zone内存的用途是包含大下标zone的，当一个zone里没法分配内存时，总是可以向更小下标的zone去分配。特别是order大于0的情况，由于pgdat_balanced条件放宽，这种情况会更多。

如果是kswapd主动干活，order总是0，classzone_idx总是最大的zone（一般就是32位下的高端内存、或者64位下的NORMAL内存）。那么参考前面zone_balanced的定义，其实kswapd的任务就是让每一个zone的空闲内存都超过高水位，至于页面在各个order间的平衡分布就不用管。

而如果kswapd是被唤醒的，说明有另一个进程在分配内存的时候遇到了麻烦。在唤醒kswapd的同时，这个进程还会把它正在试图分配的order和classzone_idx提交给kswapd，表示kswapd的这次回收操作应该以达到针对order和classzone_idx的pgdat_balanced为目标。对于kswapd拿到的order，会影响到zone_balanced的判断，除了保证zone内的空闲内存超过高水位，还得保证空闲内存在0~order之间平衡分布。所以如果达不到平衡分布，就还得继续回收以及尝试小order向大order的组装。

好了，拿到了order和classzone_idx，kswapd该怎么做呢？按什么样的策略去回收？又何时收手？

回收的活路是由balance_pgdat函数来完成的，该函数的简化版本如下：

unsigned long balance_pgdat(pg_data_t *pgdat, int order, int *classzone_idx)

{

int end_zone = 0;

loop_again:

sc.priority = DEF_PRIORITY; // 初始优先级12，优先级会影响到扫描页面的数量

sc.nr_reclaimed = 0; // 重置回收页面计数，为本次大loop做统计

do {

// 找到下标最大的那个imbalanced的zone，记为end_zone，作为回收的目标

// 注意，并不是直接以classzone_idx作为目标

for (i = pgdat->nr_zones - 1; i >= 0; i--) {

struct zone *zone = pgdat->node_zones + i;

if (!zone_balanced(zone, order, 0, 0)) {

end_zone = i;

break;

}

}

// 如果所有的zone都是zone_balanced的，那就可以收工了

if (i < 0) {

pgdat_is_balanced = true;

goto out;

}

// 试图对每一个zone进行回收，除非这个zone的空闲页面太多

for (i = 0; i <= end_zone; i++) {

struct zone *zone = pgdat->node_zones + i;

// zone的空闲页面太多定义为比高水位还多一个balance_gap

// balance_gap定为zone内页面数的1%

unsigned long balance_gap = min(low_wmark_pages(zone),

(zone->managed_pages + KSWAPD_ZONE_BALANCE_GAP_RATIO-1)

/ KSWAPD_ZONE_BALANCE_GAP_RATIO);

if (!zone_balanced(zone, order, balance_gap, end_zone)) {

// 执行回收

shrink_zone(zone, &sc);

}

}

// 如果本轮回收已经达到了pgdat_balanced的效果，准备收工

// 注意，是pgdat_balanced针对的是classzone_idx，而不是end_zone

if (pgdat_balanced(pgdat, order, *classzone_idx)) {

pgdat_is_balanced = true;

break;

}

// 如果本轮已回收达32个页面，就跳出循环，恢复默认优先级再重试

if (sc.nr_reclaimed >= SWAP_CLUSTER_MAX)

break;

// 在当前优先级下回收未果，减小优先级继续回收

} while (--sc.priority >= 0);

out:

// 没能达到pgdat_balanced，继续从默认优先级开始循环

if (!pgdat_is_balanced) {

// 考虑让出CPU给更有需要的进程

cond_resched();

// 对于高order，如果很难回收到，就暂且放弃，将order重置为0

if (sc.nr_reclaimed < SWAP_CLUSTER_MAX)

order = sc.order = 0;

goto loop_again;

}

// 返回本次回收的order和classzone_idx

// 后续kswapd会检查在order和classzone_idx下是否达到pgdat_balanced，

// 以决定kswapd是睡眠一会、还是继续工作

*classzone_idx = end_zone;

return order;

}

这里面有几点值得再展开一下：

1、balance_pgdat的内存回收并不以classzone_idx为出发点，而是会试图对所有zone都进行一次回收。而回收是否达到要求则是针对classzone_idx进行pgdat_balanced的检查；

2、具体的回收过程由shrink_zone函数来完成，具体过程这里就不赘述了（参见《linux内核内存回收浅析》）。不过有一点需要提一下，shrink_zone会扫描LRU中一定数目的页面并尝试回收它们。这个“一定数目“是以扫描优先级来确定的，sizeof(LRU)>>sc.priority。一个LRU list中一次只有一部分页面会被扫描，不过这并不会导致list头部的页面被重复扫描，因为被扫描过后的页面一般只有两个去向，要么因为没有access而被回收（或从active list下放到inactive list）、要么因为有access而被放到队尾；

3、扫描，意味着页面的老化。一个页面被访问之后，相应的access标记会一直打在那里，直到这个页面被扫描。LRU里面的时间流逝跟自然时间是没有关系的，扫描才是推动历史车轮前进的动力。而扫描又是由于达不到balanced而被触发的，可见页面老化的速度跟系统中内存的紧缺程度是相关的。内存紧缺的时候，1分钟前才被访问过的页面可能都不会被视作活跃；反过来，如果内存不紧缺，长期不需要进行回收，那么几小时前访问过的页面又可能都会被视作活跃，并且在这段时间内被访问过一次和被访问过多次的页面会被同等对待（access是标记而不是计数）；

4、过多的扫描显然是不好的，所以这里对扫描优先级的调整很有讲究：如果回收没效果，就调小优先级，一次扫描更多的页面；如果回收有一定效果，则回退优先级，控制一下扫描页面的数量。这里还有一个问题，大多数时候每次回收都是只有部分页面被扫描（只需要尝试少数几轮就能回收到足够的页面），这对于被扫描到的页面是不是不太公平？其实既然这些可回收页面是由LRU来管理的，LRU list中的页面本身就是按年龄排序的（LRU=最近最少使用）。每次扫描最老的那一部分页面，这是很公平的；

5、其实说白了，所有不满足zone_balanced的zone都会尝试回收，为什么还要弄出一个end_zone呢？这是跟内存分配有关的。在kswapd进行页面回收的同时，其他进程可能会同时正在进行内存分配。这些分配一般都会发生在大下标的zone上面（内存分配总是优先选择满足需要的下标最大的zone）。有了end_zone，就划定了本次回收的范围，下标比end_zone大的zone如果在回收过程中变得imbalanced，那这次也暂不管了（只要最终能满足针对classzone_idx的pgdat_balanced即可）。否则可能造成kswapd一边回收，其他进程一边分配，而陷入内存总是达不到zone_balanced的窘境。这可能导致balance_pgdat一轮又一轮的不断去进行回收，从而可能导致对小下标的zone进行过多不必要的回收；

6、在定位到end_zone之后，会以下标从小到大的顺序去尝试shrink_zone，这一点也很有讲究。刚才提到过其他进程的内存分配大可能落在大下标的zone上，如果这里先回收大下标的end_zone，在继续回收其他zone的时候，end_zone很可能又由于被分配而沦为imbalanced，又导致上一条提到的问题；另外，这样的回收顺序对于其他进程的主动回收也是友好的。在其他进程尝试分配内存未果的时候，他们除了会唤醒kswapd（并将需要分配的order和classzone_idx提交过去），还会调用try_to_free_pages尝试主动回收。里面会以内存分配时的zonelist及其顺序去调用shrink_zone进行回收，而zonelist里的zone顺序通常是下标从大到小的顺序（记住，分配的时候总是优先尝试能满足需要的最普通的zone）。这样一来，两个回收过程就是以相反的zone顺序来进行的。如果不这样的话，两边顺序相同会导致先回收的那些zone成为重灾区，被两边重复扫描。而回收好了以后，主动回收就中断了，其他的zone很可能不会被主动回收扫描到。前面提到扫描就意味着页面的老化，所以让某些zone成为重点扫描对象这肯定是不好的；

7、为什么有了kswapd，还要让进程主动回收呢？如果系统中只有一种回收方式，这肯定是最清楚最简单最爽的。但是假设只有kswapd这么一种异步的回收方式，为了保证绝大多数情况下进程都能分配到内存，可能就得将空闲内存的水位设得比较高才行，而这又会影响性能（毕竟闲着的内存多了、充当cache的少了）。而如果要想保持比较低的空闲内存水位，一种解决办法就是让kswapd提供两种回收策略，普通情况使用常规策略、而当有进程分配内存失败时，被唤醒的kswapd采用快速回收策略。那么，其实进程调用try_to_free_pages主动回收也就相当于唤醒kswapd进行快速回收，只不过是少了一次进程同步而已；

8、balance_pgdat在回收过程中搞了一个balance_gap来检查zone_balanced，这个也有点意思。一方面，因为kswapd在回收的时候别的进程同时可能正在分配，为了避免刚处理完的zone因为分配而变成imbalanced，所以通过增加一个balance_gap临时将zone的水位阈值抬高，让zone_balanced之后还留有一点余量；另一方面，这样可以尽量给这些zone施加同等的扫描压力，尽量保持他们同等的老化节奏（只要zone内空闲的页面还不是太多，就尽量一视同仁，一起扫描）；

9、高order的内存可能是很难回收的，如果经历了一个大loop（LRU中的所有页面都扫描了一遍）还没什么效果，就暂且放弃。否则可能导致kswapd在这里死循环，疯逛的回收，这是很影响性能的；

至此，对kswapd的介绍就差不多告一段落了。想起以前一直对kswapd有个疑惑：如果系统搁在那里一直没人使用（也没有用户进程在后台跑），kswapd周期性的回收页面，过一段时间岂不是会把cache什么的都干掉了么？其实本文已经解答这个问题了：kswapd的目标不是回收内存，而是balance内存；推动kswapd进行回收、或者说推动页面老化的不是时间，而是imbalanced。所以，没人用就意味着没有内存分配，也就意味着内存不会陷入imbalanced，那么也就不会有页面被回收掉。关于这一点，最后再分几个层面总结一下：

1、如果pgdat_balanced能达到，那么kswapd根本就不用干活；

2、如果zone_balanced能达到，那么对应的zone一般也不需要回收；

3、如果zone只有轻微的imbalanced，那么只需要扫描很小比例的页面就能恢复zone_balanced，而不必全部扫描；

4、还有一点在文中没有细说，shrink_zone在回收一个zone的内存时，也会试图balance各个LRU list之间的页面。只有active list长度大于inactive list时才会考虑将其中的页面回收到inactive list。而FILE LRU list和ANON LRU list需要扫描的页面数目也会进行一定比例的分配（根据/proc/sys/vm/swappiness所示的参数）；

可见，kswapd由始至终都贯彻着这样的balance思想，既要保证空闲页面的余量，满足新的页面分配请求、又要避免过度回收，造成性能上的损失。