一般来说，我们的手机的内存 RAM 的容量是固定的，用多少，就少多少，这是不可逆转的。为了解决这个难题，内存交换的思想应运而生，通过将一些不活动页交换到速度较慢的硬盘，SD 卡等，然后将这些内存腾出来，从而变相地达到了增大内存的效果。（然而这个并不是新东西，我读过 Linux 0.12 的源代码，发现在那个时候就已经有这个东东了）
整个内存交换分为两个部分——页面回收，页面回写。页面回收主要是通过一系列的算法判断筛选出回收页的候选者，页面回写则负责将这些页回写到交换设备中。这里面最重要和最复杂的是页面回收算法，也是这篇东东所要描述的重点。
注：在学习这一部分内容的时候，我查阅了大量的资料，并且发现而英语术语的重要性，所以对于重要的术语，我会在后面注明它的英文原文。
预备知识
- 匿名页（anonymous page） 和 文件页（file page）
匿名页指的是内存页的内容没有备份在文件或者其他后备设备（backup device），一般我们进程的栈和堆都属于这一类型，或者我们在使用 mmap() 进行映射的时候，加入了 MAP_ANONYMOUS 的参数。这种内存页的特点是，内存页里面的内容，丢了就没了。所以如果在将这一种内存页交换出去的时候，必须为其申请一块交换空间（swap space）
文件页则是与上面的相反，这一类内存页里面的内容都有备份到后备设备。但是这一类内存页存在一个问题就是同步，即内存里面的数据被修改了，从而导致内存页变成了脏页（dirty page），这个时候就需要进行回写（writeback），使其后备设备的内容与内存页的内容一致。
struct page中一些重要的flag
- PG_swapcache: 说明当前页是页缓存。并且当前页的
struct page里面的private成员指向的是交换设备的标识符，mapping成员指向NULL。（具体什么是页缓存请看下一节：重要的数据结构） - PG_swapbacked: 当前页被备份在 RAM 或者是 swap 分区上。
- PG_reclaim: 似乎是表明当前页是脏的，但是还没有进行回写操作。
- 注意：内核有专门的函数来检测这些标志位，例如
PG_swapcache就是用PageSwapCache()，PG_reclaim就是用PageReclaim()。但是，如果你通过grep或者其他工具根据函数名去搜索这些函数的实现的时候，你会很神奇地发现你找不到。其实这是内核使用的一个技巧，因为这些函数大同小异，所以系统使用了宏（macro）来统一表达。所以你就会发现，这么一堆函数在内核的实现中只用了两行（具体在include/linux/page-flags）:*
static inline int Page##uname(const struct page *page) \
{ return test_bit(PG_##lname, &page->flags); }所以，这也给了我们一个提示，如果我们在搜索一些变量或者函数的时候找不到它的实现，那么很有可能内核使用了宏来实现，而解决方法页很简单，就是抽取出这些变量或者函数的共同处，然后使用这个共同处去搜索，会有意想不到的收获～
struct zone中一些重要的flag
- ZONE_DIRTY: 页回收扫描过程最近在 LRU 链表的尾部发现了大量的脏页
- ZONE_WRITEBACK: 回收扫描阶段遇到大量正在处于回写阶段的内存页
- ZONE_CONGESTED: 当前的 zone 有许多备份在已经处于拥塞（congested）的后备设备的脏页。
- 一些重要的内存分配器（memory allocator）的
flag
其实这里比较模糊的是 __GFP_IO 和 __GFP_FS，而要理解这两个的区别就需要知道一个知识点——交换设备是没有文件系统的（当然，交换设备有可能是存放在文件系统上的文件），所以对这些设备的写操作不需要特别繁琐的过程。所以在代码中你会看到这样的代码组合：
(PageSwapCache(page) && (sc->gfp_mask & __GFP_IO));重要的数据结构
注意，我这里提到的都是 Linux Kernel 3.x 之后变动很大的数据结构，如果没有提到的，都是基本保持不变的，直接看书即可，几乎市面上所有的内核书都是基于 Linux Kernel 2.6.x 的。
- struct vm_area_struct
这个数据结构是用来描述虚拟内存区域（virtual memory area）的，关于这个数据结构的详细说明我想放在逆向映射（reverse mapping），这里主要提一点，就是内核是如何分辨一个内存映射是匿名映射（anonymous mapping）和文件映射（file mapping）。首先，每个物理页帧（page flame）都有一个 struct page 的结构体变量实例，这个结构体里面有一个成员 mapping 。每个进程的所有内存区域都是用 struct vm_area_struct 来统一管理的，进程通过 struct task_struct 里面的成员 struct vm_area_struct *mmap 来管理关联到该进程的所有 struct vm_area_struct 实例（通过链表和红黑树）。一个页帧要关联到一个进程，就是要关联到一个 struct vm_area_struct 。具体的流程是这样的：如果是匿名映射，那么将 struct page 里面的 mapping 指向所在的 struct vm_arear_struct 里面的 struct anon_vma 加上 PAGE_MAPPING_ANON ，这样通过判断 page->mapping 的最低位是否为 PAGE_MAPPING_ANON 就可以很好的区分匿名映射。这样就可以通过 page->mapping 获取页帧的 struct anon_vma ，最后通过 container_of 之类的宏就可以访问到整个 struct vm_area_struct 。
- struct lruvec
在 Linux Kernel 2.6 以及之前的版本，内核试图将内存页分类到两个 LRU 链表 —— 活动的（active）和不活动的（inactive），系统是通过在每个内存域（zone）的结构体 struct zone 里面两个成员 struct list_head active_list 和 struct list_head inactive_list 来表示的。后来，Linux Kernel 又将这两个链表根据它们的来源进行了细化和划分，将每个链表分成了 file 和 anon ，再加上一个不可驱逐的 unevictable 的链表，总共有 5 个 LRU 链表。
struct lruvec {
struct list_head lists[NR_LRU_LISTS];
struct zone_reclaim_stat reclaim_stat;
struct zone *zone;
};
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
}; 然后，需要指出的是：回收行为分为 global reclaim 和 target reclaim 。其中， target reclaim 是针对 memory cgroup 的（因为 memory cgroup 也包含有 struct lruvec 这个数据结构） ，而 global reclaim 是针对整个内存域的。
- struct scan_control
这是一个很重要的数据结构，扫描的调用者通过这个数据结构向执行回收扫描的函数来控制扫描行为，这里面有几个比较重要的成员变量要说明一下（只挑选了一部分）：
struct scan_control {
/*指明了 shrink_list() 应该回收多少内存页 */
unsigned long nr_to_reclaim;
/* 这个是传给后续页面回收函数的 GFP 标志 */
gfp_t gfp_mask;
/* 系统通过判断这个成员是否为 NULL 来判断 global reclaim 还是 target reclaim */
struct mem_cgroup *target_mem_cgroup;
/* 扫描的数目是整个 LRU 的大小 >> priority （具体在 get_scan_count() 体现）
* 也就是说，priority 越大，扫描的数目就越少
*/
int priority;
// 指定了内核是否允许将页面写出到后备设备上
unsigned int may_writepage:1;
/* 指定了已经映射的页面能否被回收 */
unsigned int may_unmap:1;
/* 指定了页面回收阶段是否允许页交换 */
unsigned int may_swap:1;
/* 到目前为止通过 shrink_zones() 释放掉的页面数目 */
unsigned long nr_reclaimed;
};- 交换缓存（swap cache）
交换缓存是个很重要的数据结构，不过由于它是属于页面回写部分的，而且，它是属于页缓存的一种。所以，比较详细的实现就暂且留个 TODO ，不过，大体上还是能够说明这个交换缓存的作用的。
想象没有交换缓存的情形，现在有一个内存页被两个进程在同时使用。此时如果内核选择将这个内存页交换出去（swap out）那么这两个进程都会将该页对应的页表项修改为页面交换所在的后备设备。然后，进程 A 想要读该内存页，那么内核将会把这个内存页换回。然后问题来了，如果接下来进程 B 也想要读该内存页，但是 B 并不知道 A 已经将该页换入（swap in）了，所以势必会造成页面的重复换入，这是一种浪费的行为，也根本没必要。所以交换缓存就应运而生了。
对于交换缓存是如何解决这个问题的，我觉得没有那一本书能够讲得比《Understanding the Linux Kernel》这本书详细了，而且我对自己的表述能力肯定无法超过这本书，所以下将书中的相关内容摘录如下：
Before being written to disk, each page to be swapped out is stored in the swap cache by shrink_list(). Consider a page P that is shared among two processes, A and B. Initially, the Page Table entries of both processes contain a reference to the page frame, and the page has two owners. When the PFRA selects the page for reclaiming, shrink_list( ) inserts the page frame in the swap cache, now the page frame has three owners, while the page slot in the swap area is referenced only by the swap cache. Next, the PFRA invokes try_to_unmap( ) to remove the references to the page frame from the Page Table of the processes; once this function terminates, the page frame is referenced only by the swap cache, while the page slot is referenced by the two processes and the swap cache. Let’s suppose that, while the page’s contents are being written to disk, process B accesses the pagethat is, it tries to access a memory cell using a linear address inside the page. Then, the page fault handler finds the page frame in the swap cache and puts back its physical address in the Page Table entry of process B. Conversely, if the swap-out operation terminates without concurrent swap-in operations, the shrink_list( ) function removes the page frame from the swap cache and releases the page frame to the Buddy system.
简单的说，就是进程每一次需要调入页的时候，都必须要搜索一下交换缓存是否有当前要换入的页。
详细说明
shrink_lruvec()
首先，shrink_lruvec() 先调用 get_scan_count() 来统计各个 LRU 链表要扫描的内存页的数目：
get_scan_count()
首先，判断是否需要强制扫描，这个是通过 force_scan 来表示的。需要强制扫描有以下两种情况：
- 当前进程是
kswapd()，并且当前的 zone 并不需要回收 - 是
memory cgroup在进行页面回收
首先说明一下强制扫描指的是什么？前面提到过，扫描行为最终在每个 LRU 链表的扫描数目是根据当前 LRU 链表的内存页数 >> sc->priority，所以扫描数目是有可能为 0 的，所以如果进行强制扫描的话，那么如果上面的计算结果为 0 的话，也要重新计算扫描的数目。
get_scan_count() 的职责是根据当前 zone 的情况，判断需要扫描的 LRU 链表的类型，并且是首先倾向于扫描 file 链表的（因为其有后备设备，可以直接释放），并且要以一定的比例来分别确定 file 链表和 anon 链表的数目：
// 注意：
// nr[0] 是 anon inactive pages 要扫描的数目; nr[1] = anon active pages 要扫描的数目
// nr[2] = file inactive pages 要扫描的数目; nr[3] = file active pages 要扫描的数目
static void get_scan_count(struct lruvec *lruvec, int swappiness,
struct scan_control *sc, unsigned long *nr)
{
......
// 如果指示回收过程不允许页交换，或者系统没有交换空间，则只扫描 file page ，则是非常显然的，不然没有地方给匿名页分配 swap space
if (!sc->may_swap || (get_nr_swap_pages() <= 0)) {
scan_balance = SCAN_FILE;
goto out;
}
// 这里首先得理解一下 swappiness 这个参数的意义。swappiness 是一个系统参数，它控制了系统交换的好斗程度（aggressive），当取值小的时候，系统倾向于不交换，取值大的时候，系统则会进行页交换。默认值是 60 。当取值为 0 的时候，系统除非为了相应 OOM（out of memory） ，否则不进行页交换。
// 然后还得注意，swappiness 有两份，一份是控制全局的，一份是每个 memory cgroup 的，在下面的这个 case 是 cgroup 的 swappiness
if (!global_reclaim(sc) && !vmscan_swappiness(sc)) {
scan_balance = SCAN_FILE;
goto out;
}
// 前面提到了 sc->priority 的意义，也就说，priority 越小，扫描的数目就越多，当 priority = 0 的时候，说明系统已经接近 OOM 了，那么此时除非系统 swappiness 等于 0 （也就是不进行页交换），否则，则 file page 和 anonymous page 都要扫描
if (!sc->priority && vmscan_swappiness(sc)) {
scan_balance = SCAN_EQUAL;
goto out;
}
/*
* Prevent the reclaimer from falling into the cache trap: as
* cache pages start out inactive, every cache fault will tip
* the scan balance towards the file LRU. And as the file LRU
* shrinks, so does the window for rotation from references.
* This means we have a runaway feedback loop where a tiny
* thrashing file LRU becomes infinitely more attractive than
* anon pages. Try to detect this based on file LRU size.
*/
// 上面的注释我看不大懂，所以保留
// 这里先说明以下 zone 里面的 watermark 的意义：这是系统根据当前 zone 的内存大小设置的三个水位线，用以区分当前内存的紧缺程度
// HIGH_WMARK: 如果超过这个值，说明当前的内存剩余是理想的，如果小于 HIGH_WMARK 则是要开始页回收了
// 不过根据下面的代码推测，似乎是如果当前 zone 的 file page 的总量加上剩余的内存页重量低于 HIGH_WMARK ，则要扫描 anon 链表，不过具体的逻辑还得进一步探究
// TODO: 理解上面的注释
if (global_reclaim(sc)) {
unsigned long zonefile;
unsigned long zonefree;
zonefree = zone_page_state(zone, NR_FREE_PAGES);
zonefile = zone_page_state(zone, NR_ACTIVE_FILE) +
zone_page_state(zone, NR_INACTIVE_FILE);
if (unlikely(zonefile + zonefree <= high_wmark_pages(zone))) {
scan_balance = SCAN_ANON;
goto out;
}
}
// 当 LRU 链表上的不活动页足够的时候，那么就只回收 file page
if (!inactive_file_is_low(lruvec)) {
scan_balance = SCAN_FILE;
goto out;
}
// 默认情况是 SCAN_FRACT
scan_balance = SCAN_FRACT;
// 在这里，swappiness 这个变量的意义似乎就显示出来了。swappiness 控制了匿名页的优先级，如果 swappiness 等于 100 ，那么匿名页和 file page 的优先级一样。
anon_prio = vmscan_swappiness(sc);
file_prio = 200 - anon_prio;
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);
.........
/*
* OK, so we have swap space and a fair amount of page cache
* pages. We use the recently rotated / recently scanned
* ratios to determine how valuable each cache is.
*
* Because workloads change over time (and to avoid overflow)
* we keep these statistics as a floating average, which ends
* up weighing recent references more than old ones.
*
* anon in [0], file in [1]
*/
// PROBLEM: 这里的逻辑还不是太懂，注释保留
spin_lock_irq(&zone->lru_lock);
if (unlikely(reclaim_stat->recent_scanned[0] > anon / 4)) {
reclaim_stat->recent_scanned[0] /= 2;
reclaim_stat->recent_rotated[0] /= 2;
}
if (unlikely(reclaim_stat->recent_scanned[1] > file / 4)) {
reclaim_stat->recent_scanned[1] /= 2;
reclaim_stat->recent_rotated[1] /= 2;
}
/*
* The amount of pressure on anon vs file pages is inversely
* proportional to the fraction of recently scanned pages on
* each list that were recently referenced and in active use.
*/
// 这里依旧无法解释，不过经过大量的搜索以及跟踪 Kernel 中这一部分的改动，似乎只是为了更加合理的计算出要扫描的 file page 和 anonymous page 的数量
// 之前的 Kernel 版本中，ap 和 fp 的数量不是这么计算的，这里之所以是这么计算是为了保证当 swappiness 等于 0 的时候，ap 能够真的等于 0 。
// 具体可以查看：
// 1) http://gitorious.ti.com/ti-linux-kernel/ti-linux-kernel/commit/fe35004fbf9eaf67482b074a2e032abb9c89b1dd?format=patch
// 2) https://eklitzke.org/swappiness
ap = anon_prio * (reclaim_stat->recent_scanned[0] + 1);
ap /= reclaim_stat->recent_rotated[0] + 1;
fp = file_prio * (reclaim_stat->recent_scanned[1] + 1);
fp /= reclaim_stat->recent_rotated[1] + 1;
spin_unlock_irq(&zone->lru_lock);
fraction[0] = ap;
fraction[1] = fp;
denominator = ap + fp + 1;
out:
// 这里的 some_scanned 的作用就是一个二次机会（second chance）的思想
some_scanned = false;
for (pass = 0; !some_scanned && pass < 2; pass++) {
for_each_evictable_lru(lru) {
int file = is_file_lru(lru);
unsigned long size;
unsigned long scan;
// 看，这里计算出了每个链表要扫描的页的数目
size = get_lru_size(lruvec, lru);
scan = size >> sc->priority;
// 如果 scan 等于 0，并且前面已经标记要强制扫描了，那么就在这里给它第二次机会
// 必须在第二轮，也就是 pass 等于 1
if (!scan && pass && force_scan)
scan = min(size, SWAP_CLUSTER_MAX);
switch (scan_balance) {
case SCAN_EQUAL:
/* Scan lists relative to size */
break;
case SCAN_FRACT:
// 似乎有点理解 SCAN_FRACT 的意思了。FRACT 就是 fraction，就是默认的扫描类型，主要是根据上面计算出来的 ap 和 fp 的数量，对 scan （要扫描的总量）进行等比例的分配
scan = div64_u64(scan * fraction[file],
denominator);
break;
case SCAN_FILE:
case SCAN_ANON:
/* Scan one type exclusively */
// 如果是 file lru 要扫描 anon page 或者是 anon lru 要扫描 file page ，则 scan 为 0
if ((scan_balance == SCAN_FILE) != file)
scan = 0;
break;
default:
BUG();
}
nr[lru] = scan;
// 如果我们找到有内存页可以扫描，那么就不用使用 second chance 了
// 这里的 !! 的作用是让零值位零，非零值为一
// 前面的循环的条件是 !some_scanned
some_scanned |= !!scan;
}
}
}
好，计算了各个链表应该扫描的数目之后，就要开始进行扫描了：
scan_adjusted = (global_reclaim(sc) && !current_is_kswapd() &&
sc->priority == DEF_PRIORITY);
blk_start_plug(&plug);
while (nr[LRU_INACTIVE_ANON] || nr[LRU_ACTIVE_FILE] ||
nr[LRU_INACTIVE_FILE]) {
unsigned long nr_anon, nr_file, percentage;
unsigned long nr_scanned;
for_each_evictable_lru(lru) {
if (nr[lru]) {
// 如果 lru 链表要移除的超过了 SWAP_CLUSTER_MAX ，那么移除操作将拆成多步完成
// 至于为什么要这么做，可以参考这个链接：
// http://blog.csdn.net/dog250/article/details/5303568
nr_to_scan = min(nr[lru], SWAP_CLUSTER_MAX);
nr[lru] -= nr_to_scan;K
nr_reclaimed += shrink_list(lru, nr_to_scan,
lruvec, sc);
}
}
从上面的代码我们可以看到，每一次扫描的数目不超过 SWAP_CLUSTER_MAX。
同时，要注意一个点，就是 scan_adjusted 这个变量的作用。我现在还不是太清楚这个变量的作用，不过通过跟踪内核上游的代码变更，我找到了加入了这个变量的几个 patch ，通过里面的 commit 好像是说为了保证一开始当 sc->priority == DEF_PRIORITY 的时候，需要扫描更多的页。所以引入了这个变量，因为在循环后面的操作会减少内存页扫描的数目。具体可以看看这几个 patch ：
mm: vmscan: Obey proportional scanning requirements for kswapd
performance regression due to commit e82e0561
好，上面是一个小插曲，我们接下来看看重头戏，扫描回收的主程序：
shrink_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, lru))
shrink_active_list(nr_to_scan, lruvec, sc, lru);
return 0;
}
return shrink_inactive_list(nr_to_scan, lruvec, sc, lru);
}
如果当前是 active lru 并且 inactive lru 里面的内存页太少了，那么将调用 shrink_active_list():
shrink_active_list()
这个函数的主要作用是从 active lru 移动一些内存页到 inactive lru。为了避免锁的麻烦，shrink_active_list() 和 shrink_inactive_list() 都使用了一个 isolate_lru_pages() 来将扫描的内存页隔离到一个临时的链表中。这个函数没有什么好说的，不过有一点比较重要，就是可能存在页结合（conbine page）的情况，这个在下面会提到：
static void shrink_active_list(unsigned long nr_to_scan,
struct lruvec *lruvec,
struct scan_control *sc,
enum lru_list lru)
{
......
LIST_HEAD(l_hold); /* The pages which were snipped off */
LIST_HEAD(l_active);
LIST_HEAD(l_inactive);
......
// 这个函数是是将每个 CPU 的页向量写回到 lru 链表上
// 页向量是一个 Per-CPU 的变量
// 这个在变动不大，所以就不详细说明了，看书就好
lru_add_drain();
......
// 从当前的 lru 页表隔离 nr_to_scan 个页面到 l_hold 链表上
// @nr_to_scan: 计划要扫描的页的数目
// @nr_scanned: 实际扫描的数目。注意，这里是忽略了 combine page 的，也就是说，不管是多少页合并到一起，都是算作一页
// @nr_taken: 扫描的总页数。这里是考虑 combine page 的
nr_taken = isolate_lru_pages(nr_to_scan, lruvec, &l_hold,
&nr_scanned, sc, isolate_mode, lru);
......
while (!list_empty(&l_hold)) {
cond_resched();
page = lru_to_page(&l_hold);
list_del(&page->lru);
if (unlikely(!page_evictable(page))) {
// 将当前页移回 lru 链表上
putback_lru_page(page);
continue;
}
// 这一块也不是很清楚
if (unlikely(buffer_heads_over_limit)) {
if (page_has_private(page) && trylock_page(page)) {
if (page_has_private(page))
try_to_release_page(page, 0);
unlock_page(page);
}
}
// TODO: 逆向映射是个大工程啊，得花很长的时间去说明，这里先跳过
// page_referenced() 的返回值是当前页的引用数目
if (page_referenced(page, 0, sc->target_mem_cgroup,
&vm_flags)) {
nr_rotated += hpage_nr_pages(page);
/*
* Identify referenced, file-backed active pages and
* give them one more trip around the active list. So
* that executable code get better chances to stay in
* memory under moderate memory pressure. Anon pages
* are not likely to be evicted by use-once streaming
* IO, plus JVM can create lots of anon VM_EXEC pages,
* so we ignore them here.
*/
// 根据注释，好像是为了防止一些页被加入到 inactive list ，然后给他们第二次机会
// 也就是说，只要当前页有被引用到，那么就有机会重新回到 active list 上
if ((vm_flags & VM_EXEC) && page_is_file_cache(page)) {
list_add(&page->lru, &l_active);
continue;
}
}
ClearPageActive(page); /* we are de-activating */
list_add(&page->lru, &l_inactive);
}
......
// l_active 移到 lru 活动链表，l_inactive 移动到 lru 不活动链表
// 同时，上面的操作会将内存页的引用次数减去一，并且判断是否为 0 。并移到相应的 LRU 链表中
// 如果为 0 的话，那么就去掉这个函数之后加入的 PG_lru 标志以及 PG_active 标志，从 LRU 链表中移除，并重新放回原来的 l_hold 链表中
move_active_pages_to_lru(lruvec, &l_active, &l_hold, lru);
move_active_pages_to_lru(lruvec, &l_inactive, &l_hold, lru - LRU_ACTIVE);
__mod_zone_page_state(zone, NR_ISOLATED_ANON + file, -nr_taken);
spin_unlock_irq(&zone->lru_lock);
mem_cgroup_uncharge_list(&l_hold);
// 依然就在 l_hold 链表的内存页都是引用次数为 0 的内存页，所以将他们释放回伙伴系统
free_hot_cold_page_list(&l_hold, true);
}
如果 inactive lru 的内存页数目充足，那么就开始调用 shrink_inactive_list()：
shrink_inactive_list()
这个函数的主要作用是从 inactive list 上的内存页释放掉一些返回给伙伴系统，这里面涉及到的逻辑很多，我们详细地说明：
static noinline_for_stack unsigned long
shrink_inactive_list(unsigned long nr_to_scan, struct lruvec *lruvec,
struct scan_control *sc, enum lru_list lru)
{
LIST_HEAD(page_list);
unsigned long nr_scanned = 3000;
unsigned long nr_reclaimed = 0;
unsigned long nr_taken;
unsigned long nr_dirty = 0;
unsigned long nr_congested = 0;
unsigned long nr_unqueued_dirty = 0;
unsigned long nr_writeback = 0;
unsigned long nr_immediate = 0;
isolate_mode_t isolate_mode = 0;
int file = is_file_lru(lru);
struct zone *zone = lruvec_zone(lruvec);
struct zone_reclaim_stat *reclaim_stat = &lruvec->reclaim_stat;
lru_add_drain();
......
nr_taken = isolate_lru_pages(nr_to_scan, lruvec, &page_list,
&nr_scanned, sc, isolate_mode, lru);
nr_reclaimed = shrink_page_list(&page_list, zone, sc, TTU_UNMAP,
&nr_dirty, &nr_unqueued_dirty, &nr_congested,
&nr_writeback, &nr_immediate,
false);
函数首先的套路跟 shrink_active_list() 是一模一样的，都是调用 isolate_lru_pages() 从当前的 lru 链表中移除一部分的内存页到一个临时链表，然后，整个重头戏来了，执行最终的回写释放操作都在接下来调用的 shrink_page_list() 这个函数中，可以说，这个函数是连接页面回收和页面回写的中间桥梁。
shrink_page_list()
这个函数将从 shrink_inactive_list() 传来的临时链表上的内存页进行回写操作。当然有一些内存页是不需要回写并且需要重新放回 LRU 链表的。
static unsigned long shrink_page_list(struct list_head *page_list,
struct zone *zone,
struct scan_control *sc,
enum ttu_flags ttu_flags,
unsigned long *ret_nr_dirty,
unsigned long *ret_nr_unqueued_dirty,
unsigned long *ret_nr_congested,
unsigned long *ret_nr_writeback,
unsigned long *ret_nr_immediate,
bool force_reclaim)
{
LIST_HEAD(ret_pages);
LIST_HEAD(free_pages);
int pgactivate = 0;
unsigned long nr_unqueued_dirty = 0;
unsigned long nr_dirty = 0;
unsigned long nr_congested = 0;
unsigned long nr_reclaimed = 0;
unsigned long nr_writeback = 0;
unsigned long nr_immediate = 0;
cond_resched();
while (!list_empty(page_list)) {
struct address_space *mapping;
struct page *page;
int may_enter_fs;
enum page_references references = PAGEREF_RECLAIM_CLEAN;
bool dirty, writeback;
cond_resched();
//取出一页，将其从当前链表删除
page = lru_to_page(page_list);
list_del(&page->lru);
//锁定当前页，具体做法是在 page->flag 打上 PG_lock 的标志
if (!trylock_page(page))
goto keep;
sc->nr_scanned++;
// 当前页不可驱逐
// 一个页面是不可驱逐的原因有两个：
// 1. 当前页面的映射是不可驱逐的：mapping->flag
// 2. 当前页面是 mloacked VMA 的一部分
if (unlikely(!page_evictable(page)))
goto cull_mlocked;
// 当前 scan_control 表示不能回收已经 map 的页，但是当前页已经 mapped 了
if (!sc->may_unmap && page_mapped(page))
goto keep_locked;
/* Double the slab pressure for mapped and swapcache pages */
// PROBLEM：这一句不是很清楚，这跟 slab 有什么关系
if (page_mapped(page) || PageSwapCache(page))
sc->nr_scanned++;
// 后续操作中可能进行 IO 操作？这里就是我们上面提到的 __GFP_FS 和 __GFP_IO 的区别所在了
may_enter_fs = (sc->gfp_mask & __GFP_FS) ||
(PageSwapCache(page) && (sc->gfp_mask & __GFP_IO));
// 页面是脏的或者正处在回写状态
page_check_dirty_writeback(page, &dirty, &writeback);
if (dirty || writeback)
nr_dirty++;
// 页面是脏的并且还没有在进行回写
// 回写肯定是要在等待队列中排队，所以这里是 unqueued
if (dirty && !writeback)
nr_unqueued_dirty++;
mapping = page_mapping(page);
// 如果当前页有被映射，但是后备设备正处在拥塞状态
if ((mapping && bdi_write_congested(mapping->backing_dev_info)) ||
(writeback && PageReclaim(page)))
nr_congested++;
......
if (!force_reclaim)
references = page_check_references(page, sc);
在这里要说明一下 page_check_references() 这个函数。我们在看《深入理解 Linux 内核》或者《深入 Linux 内核架构》这些内核书的时候，会看到这样的一个名词——第二次机会（second chance）算法。这个函数就充分地表现了这个算法。这个函数只要发现当前的内存页被引用（reference）了，那么就会试图让当前页不被回收而是重新回到 LRU 链表上。这个算法也是避免页颠簸（page thrashing）的一个重要的体现。我们既要回收不活动的内存页，也要避免将活动页回收。这也是为什么这一部分的代码十分繁杂的缘故了。因为他要考虑到很多很多中情况。
// 根据当前页的状态，如果是 RECLAIM 状态的，就在接下来进行回收，否则则跳出进行处理
switch (references) {
case PAGEREF_ACTIVATE:
goto activate_locked;
case PAGEREF_KEEP:
goto keep_locked;
case PAGEREF_RECLAIM:
case PAGEREF_RECLAIM_CLEAN:
; /* try to reclaim the page below */
}
if (PageAnon(page) && !PageSwapCache(page)) {
if (!(sc->gfp_mask & __GFP_IO))
goto keep_locked;
if (!add_to_swap(page, page_list)) // INPORTANT：为当前页分配一个 swap entry 并且把它加入到 swap cache，具体请看上面关于页缓存的描述
goto activate_locked;
may_enter_fs = 1;
/* Adding to swap updated mapping */
mapping = page_mapping(page);
}
// 当前内存页被映射了，调用 try_to_unmap() 来解除映射
if (page_mapped(page) && mapping) {
switch (try_to_unmap(page, ttu_flags)) {
case SWAP_FAIL:
goto activate_locked;
case SWAP_AGAIN:
goto keep_locked;
case SWAP_MLOCK:
goto cull_mlocked;
case SWAP_SUCCESS:
; /* try to free the page below */
}
}
if (PageDirty(page)) {
// 如果当前页是脏的，那么必须回写
// 根据注释说明，只有 kswapd 能够回写备份在文件系统的内存页（page backed by a regular filesystem）。
// 或者是回收扫描操作遇到了许多的脏页（由 ZONE_DIRTY 标志位标志）
// 所以如果当前当前页是备份在文件系统但是当前进程不是 kswap ，
// 或者是当前还没有扫描到足够多的脏页，都不能进行回写
if (page_is_file_cache(page) &&
(!current_is_kswapd() ||
!test_bit(ZONE_DIRTY, &zone->flags))) {
/*
* Immediately reclaim when written back.
* Similar in principal to deactivate_page()
* except we already have the page isolated
* and know it's dirty
*/
inc_zone_page_state(page, NR_VMSCAN_IMMEDIATE);
SetPageReclaim(page);
goto keep_locked;
}
if (references == PAGEREF_RECLAIM_CLEAN)
goto keep_locked;
if (!may_enter_fs)
goto keep_locked;
if (!sc->may_writepage)
goto keep_locked;
// 脏页在这里尝试写回
switch (pageout(page, mapping, sc)) {
case PAGE_KEEP:
goto keep_locked;
case PAGE_ACTIVATE:
goto activate_locked;
case PAGE_SUCCESS:
if (PageWriteback(page))
goto keep;
if (PageDirty(page))
goto keep;
if (!trylock_page(page))
goto keep;
if (PageDirty(page) || PageWriteback(page))
goto keep_locked;
mapping = page_mapping(page);
case PAGE_CLEAN:
; /* try to free the page below */
}
}
......
if (!mapping || !__remove_mapping(mapping, page, true))
goto keep_locked;
__clear_page_locked(page);
// 要释放的内存页添加到 free_pages 链表，要放回的放到 ret_pages 链表
free_it:
nr_reclaimed++;
list_add(&page->lru, &free_pages);
continue;
cull_mlocked:
if (PageSwapCache(page))
try_to_free_swap(page);
unlock_page(page);
putback_lru_page(page);
continue;
activate_locked:
if (PageSwapCache(page) && vm_swap_full())
try_to_free_swap(page);
VM_BUG_ON_PAGE(PageActive(page), page);
SetPageActive(page);
pgactivate++;
keep_locked:
unlock_page(page);
keep:
list_add(&page->lru, &ret_pages);
VM_BUG_ON_PAGE(PageLRU(page) || PageUnevictable(page), page);
}
mem_cgroup_uncharge_list(&free_pages);
free_hot_cold_page_list(&free_pages, true);
// free_pages 链表上的内存页会被上面的 free_hot_cold_page_list() 释放掉
// 上面循环未处理的内存页所在的 ret_pages 将移到 page_list 链表（即调用者传进来的参数），然后在本函数的调用者那里被重新移到不活动链表上
list_splice(&ret_pages, page_list);
count_vm_events(PGACTIVATE, pgactivate);
*ret_nr_dirty += nr_dirty;
*ret_nr_congested += nr_congested;
*ret_nr_unqueued_dirty += nr_unqueued_dirty;
*ret_nr_writeback += nr_writeback;
*ret_nr_immediate += nr_immediate;
return nr_reclaimed;
}
这里要说明一下上面那几个 nr_ 变量的意义：
nr_dirty
当前页是脏的或者处于回写状态nr_unqueued_dirty
当前页是脏的并且没有处于回写状态nr_congested
当前页已经被映射并且该页的后备设备正处在阻塞状态（congested），或者是当前页正处在回写状态并且该页即将被回收nr_immediate
好像是某一页 “marked for immediate reclaim and under writeback(nr_immediate)”，也就是说，当前页即将被回收，而且正处在回写状态（这个跟上面是不一样的，只有当前 zone 标记了 ZONE_WRITEBACK 才将内存页计入这里）nr_reclaimed
总共回收的页数
最后，ret_pages 链表中要返回的内存页重新放到了传进来的参数 page_list ，交给调用者去重新放回 LRU 链表。
然后，回到 shrink_inactive_list() ，回写操作完成之后，必须根据本次的回写情况重新界定当前 zone 的情况，这就要用到上面提到的那几个 nr_ 变量了。后面的代码比较的清晰直接，就补贴代码了。
我们重新回到 shrink_lruvec() ，当所有的 LRU 链表扫描完了之后，我们要重新计算下一次的扫描数目了。前面提到，整个扫描活动都是遵循则比例扫描的原则，计算方法：
nr_file = nr[LRU_INACTIVE_FILE] + nr[LRU_ACTIVE_FILE];
nr_anon = nr[LRU_INACTIVE_ANON] + nr[LRU_ACTIVE_ANON];
// 如果某一个链表需要扫描的数目已经为 0 ，那么跳出循环，本次页面回收结束
if (!nr_file || !nr_anon)
break;
// 下面的做法是将剩下需要扫描数目少的清零，并且标志那个较大的 LRU 链表（lru 变量）
// percentage：已经扫描的内存页相对于 get_scan_count() 计算出来的需要扫描的内存页的占比
// 用于提供下面的比例扫描的重新计算
if (nr_file > nr_anon) {
unsigned long scan_target = targets[LRU_INACTIVE_ANON] +
targets[LRU_ACTIVE_ANON] + 1;
lru = LRU_BASE;
percentage = nr_anon * 100 / scan_target;
} else {
unsigned long scan_target = targets[LRU_INACTIVE_FILE] +
targets[LRU_ACTIVE_FILE] + 1;
lru = LRU_FILE;
percentage = nr_file * 100 / scan_target;
}
// 少的我们就不扫描了
nr[lru] = 0;
nr[lru + LRU_ACTIVE] = 0;
// 根据占比重新计算需要扫描的数目
lru = (lru == LRU_FILE) ? LRU_BASE : LRU_FILE;
nr_scanned = targets[lru] - nr[lru];
nr[lru] = targets[lru] * (100 - percentage) / 100;
nr[lru] -= min(nr[lru], nr_scanned);
lru += LRU_ACTIVE;
nr_scanned = targets[lru] - nr[lru];
nr[lru] = targets[lru] * (100 - percentage) / 100;
nr[lru] -= min(nr[lru], nr_scanned);
在这里我想提一点，在我看这些源代码的过程中，经历了一个痛苦的过程，就是我自己掉入了一个逻辑怪圈——我看得懂代码，但是却参不透其背后的逻辑，然后就大量地进行搜索，依旧没有解答。后来开始跟踪 Linux Kernel 社区的邮件列表和 patch 变动，我终于得出了一个结论 —— 我们现在说看到的所有的代码的正确性都是相对的，也就是说，是这个 patch 的提交者认为这样写能够 work right ，我们自己也可以有自己的，不同的想法和结论。不要去纠结于里面的个中细节！！！！体会思想才是关键！！！！！整个页面回收算法体现了几个思想（我觉得叫做思想十分地贴切，或者用大白话说就是大方向），比例扫描，第二次机会，当然还有最重要的 LRU （least recently used），而内核代码的提交者都是在用他们自己的方式去描述他们心中的这些思想，这或许就是 Linux Kernel 自由的意义所在吧。
以上。
EOF
Author: simowce
Permalink: https://blog.simowce.com/page-fram-reclaim-algorithm/
本作品采用 知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可。