作者简介：马宜萱，西安邮电大学计算机专业研二学生，热衷于探索linux内核。
物理内存不足时，操作系统使用存储设备作为交换分区，内核将很少使用的内存换到交换分区，这个机制称为页交换，统称为页面回收。
页交换算法：
LRU链表算法 第二机会法
一、LRU链表算法
#define LRU_BASE 0
#define LRU_ACTIVE 1
#define LRU_FILE 2
// 枚举类型变量 lru_list 列举出各种 LRU 链表的类型
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
};
// 每个内存节点中都有一整套LRU链表
// 内存节点描述符数据结构pglist_data中成员lruvec
struct lruvec {
struct list_head lists[NR_LRU_LISTS];
...
};
typedef struct pglist_data {
...
struct lruvec __lruvec;
...
} ;
LRU链表如何实现页面老化？
void lru_cache_add(struct page *page)
{
struct pagevec *pvec;
get_page(page);
pvec = this_cpu_ptr(&lru_pvecs.lru_add);
if (pagevec_add_and_need_flush(pvec, page))
__pagevec_lru_add(pvec);
local_unlock(&lru_pvecs.lock);
}lru_cache_add（）函数使用了页向量（pagevec）数据结构，借助数组来保存特数目的页。页向量会以批处理的方式执行。
#define PAGEVEC_SIZE 15
struct pagevec {
unsigned char nr;
bool percpu_pvec_drained;
struct page *pages[PAGEVEC_SIZE];
};pagevec_add_and_need_flush函数往pvec->pages[]数组添加页面，如果没有空间，调用__pagevec_lru_add函数把原有页面添加到LRU链表。
lru_to_page()和list_del(&page-lru)函数的组合用于从LRU链表中获取页面。#define lru_to_page(head) (list_entry((head)->prev, struct page, lru))
二、第二次机会法
和LRU链表算法一样，最早置入链表的页面。二次机会法设置了一个访问状态位，所以要检查页面的访问位。如果访问位是0，就淘汰这个页面；如果访问位是1，就给它第二次机会。
内核使用PG_active和PG_referenced这两个标志位来实现第二次机会法。PG_active表示该页面是否活跃，PG_referenced表示该页面是否被引用过。
mark_page_accessed()函数void mark_page_accessed(struct page *page)
{
page = compound_head(page);
// 如果PG_referenced==0
if (!PageReferenced(page)) {
// 设置PG_referenced标志位
SetPageReferenced(page);
} else if (PageUnevictable(page)) {
}
// 如果PG_active==0 && PG_referenced==1
else if (!PageActive(page)) {
// 则把该页面加入活跃LRU链表，并设置PG_active==1
if (PageLRU(page))
activate_page(page);
else
__lru_cache_activate_page(page);
// 清除PG_referenced标志位
ClearPageReferenced(page);
workingset_activation(page);
}
if (page_is_idle(page))
clear_page_idle(page);
}如果 PG_active==0 &&PG_referenced==1，则把该页面加入活跃LRU链表，并设置PG_active==1，清除PG_referenced标志位。如果 PG_referenced==0，则设置PG_referenced标志位。page_check_references()函数static enum page_references page_check_references(struct page *page,
struct scan_control *sc)若该页面是匿名页面，则加入活跃LRU链表。 若页面位于最近第二次访问的文件缓存或者是共享文件缓存，则加入活跃LRU链表。 若页面位于可执行文件的文件缓存，则加入活跃LRU链表。 如果访问、引用了PTE，那么分情况处理
除上面三种情况外，页面还可以继续留在不活跃LRU链表，如第一次访问的文件缓存中的页面。
如果没有访问、引用PTE，则可以尝试回收它。
page_referenced()函数int page_referenced(struct page *page,
int is_locked,
struct mem_cgroup *memcg,
unsigned long *vm_flags)利用RMAP系统遍历所有映射该页面的PTE。 对于每个PTE，如果
PTE_AF位置位，说明它之前被访问过，referenced计数加1，然后清零PTE_AF位。返回引用的PTE的个数，即访问引用这个页面的用户进程空间虚拟页面的个数。
返回 referenced计数，表示该页面访问、引用了多少个PTE。page_reference_one()函数static bool page_referenced_one(struct page *page, struct vm_area_struct *vma,
unsigned long address, void *arg)page_reference_one()函数用来统计访问、引用的PTE的个数。
三、触发页面回收
内核中触发页面回收方式：
直接页面回收机制：使用页面分配接口函数 alloc_page()分配物理页面时，由于系统内存短缺，内核会自陷到页面回收机制来解决燃眉之急。周期性回收内存机制：kswapd内核线程的工作职责。无法在低水位情况下分配出内存，会唤醒kswapd内核线程来异步回收内存。 slab收割机机制：用来回收slab对象。
直接回收内存是同步回收，会阻塞调用者进程的执行。
直接内存回收中的等待队列
在直接内存回收过程中，有可能会造成当前需要分配内存的进程被加入一个等待队列，当整个node的空闲页数量满足要求时，由kswapd唤醒它重新获取内存。
直接内存回收执行路径是：
__alloc_pages_slowpath() -> __alloc_pages_direct_reclaim() -> __perform_reclaim() -> try_to_free_pages() -> do_try_to_free_pages() -> shrink_zones() -> shrink_zone()
唤醒所有node的kswapd内核线程的情况：
在
__alloc_pages_slowpath()中可能唤醒了所有node的kswapd内核线程，也可能没有唤醒，每个node的kswapd是否在__alloc_pages_slowpath()中被唤醒有两个条件：
分配标志中没有 __GFP_NO_KSWAPD，只有在透明大页的分配过程中会有这个标志。node中有至少一个zone的空闲页框没有达到 空闲页框数量 >= high阈值 + 1 << order + 保留内存，或者有至少一个zone需要进行内存压缩，这两种情况node的kswapd都会被唤醒。
而在kswapd中会对node中每一个不平衡的zone进行内存回收，直到所有zone都满足 **zone分配页框后剩余的页框数量 > 此zone的high阀值 + 此zone保留的页框数量**。kswapd就会停止内存回收，然后唤醒在等待队列的进程。
之后进程由于内存不足，对zonelist进行直接回收时，会调用到try_to_free_pages()。
try_to_free_pages()函数unsigned long try_to_free_pages(struct zonelist *zonelist, int order,
gfp_t gfp_mask, nodemask_t *nodemask)
{
unsigned long nr_reclaimed;
struct scan_control sc = {
.nr_to_reclaim = SWAP_CLUSTER_MAX,
.gfp_mask = current_gfp_context(gfp_mask),
.reclaim_idx = gfp_zone(gfp_mask),
.order = order,
.nodemask = nodemask,
.priority = DEF_PRIORITY,
.may_writepage = !laptop_mode,
.may_unmap = 1,
.may_swap = 1,
};
if (throttle_direct_reclaim(sc.gfp_mask, zonelist, nodemask))
return 1;
set_task_reclaim_state(current, &sc.reclaim_state);
trace_mm_vmscan_direct_reclaim_begin(order, sc.gfp_mask);
nr_reclaimed = do_try_to_free_pages(zonelist, &sc);
trace_mm_vmscan_direct_reclaim_end(nr_reclaimed);
set_task_reclaim_state(current, NULL);
return nr_reclaimed;
}try_to_free_pages函数用于在内存不足时尝试回收内存页框，以满足内存分配请求。其工作流程如下：
初始化回收参数：设置 scan_control结构体中的参数，如回收的页框数量、内存分配标志、节点掩码、优先级等。判断是否需要限制回收：调用 throttle_direct_reclaim函数检查节点平衡情况，决定是否暂停回收操作。记录内存回收的开始：跟踪和记录内存回收操作的开始状态。 执行内存回收：调用 do_try_to_free_pages函数，按照设定的策略回收内存。记录内存回收的结束：跟踪并记录回收结束的状态，返回成功回收的页框数。
主要通过throttle_direct_reclaim()函数判断是否加入到pgdat->pfmemalloc_wait等待队列中
static bool throttle_direct_reclaim(gfp_t gfp_mask, struct zonelist *zonelist,
nodemask_t *nodemask)
{
struct zoneref *z;
struct zone *zone;
pg_data_t *pgdat = NULL;
if (current->flags & PF_KTHREAD)
goto out;
if (fatal_signal_pending(current))
goto out;
for_each_zone_zonelist_nodemask(zone, z, zonelist,
gfp_zone(gfp_mask), nodemask) {
if (zone_idx(zone) > ZONE_NORMAL)
continue;
pgdat = zone->zone_pgdat;
if (allow_direct_reclaim(pgdat))
goto out;
break;
}
if (!pgdat)
goto out;
count_vm_event(PGSCAN_DIRECT_THROTTLE);
if (!(gfp_mask & __GFP_FS))
wait_event_interruptible_timeout(pgdat->pfmemalloc_wait,
allow_direct_reclaim(pgdat), HZ);
else
wait_event_killable(zone->zone_pgdat->pfmemalloc_wait,
allow_direct_reclaim(pgdat));
if (fatal_signal_pending(current))
return true;
out:
return false;
}
throttle_direct_reclaim 函数用于判断内存节点是否平衡，并在不平衡的情况下限制直接内存回收操作，防止系统中止（OOM）进程。具体工作流程如下：
如果分配标志禁止文件系统操作 ( __GFP_FS)，将进程设置为TASK_INTERRUPTIBLE状态并加入pgdat->pfmemalloc_wait等待队列，等待节点变平衡或超时（1秒）。如果未禁止文件系统操作，将进程设置为 TASK_KILLABLE状态并加入等待队列，在节点平衡或接收到致命信号时被唤醒。
检查内核线程和进程状态：如果当前进程是内核线程 ( PF_KTHREAD标志) 或接收到终止信号 (fatal_signal_pending)，直接返回，不做处理。**遍历 zonelist**：遍历zonelist中的每个内存区域，仅处理ZONE_NORMAL和ZONE_DMA区域，找到第一个非平衡的pgdat（节点）。判断节点平衡性：调用 pfmemalloc_watermark_ok函数检查节点是否平衡。如果节点平衡，立即返回；否则，继续执行后续操作。加入等待队列： 检查是否被终止：如果进程从等待队列中被唤醒后接收到终止信号，返回 true，表示被限制了回收操作；否则，返回false，表示未被限制。
