背景

• Read the fucking source code! --By 鲁迅
• A picture is worth a thousand words. --By 高尔基

说明：

1. Kernel版本：4.14
2. ARM64处理器，Contex-A53，双核
3. 使用工具：Source Insight 3.5， Visio

1. 概述

本文将分析watermark。
简单来说，在使用zoned page frame allocator分配页面时，会将可用的free pages与zone的watermark进行比较，以便确定是否分配内存。
同时watermark也用来决定kswapd内核线程的睡眠与唤醒，以便对内存进行检索和压缩处理。

回忆一下之前提到过的struct zone结构体：

struct zone {
	/* Read-mostly fields */

	/* zone watermarks, access with *_wmark_pages(zone) macros */
	unsigned long watermark[NR_WMARK];

	unsigned long nr_reserved_highatomic;
    
    ....
}

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])

可以看出，总共有三种水印，并且只能通过特定的宏来访问。

• WMARK_MIN
  内存不足的最低点，如果计算出的可用页面低于该值，则无法进行页面计数；

• WMARK_LOW
  默认情况下，该值为WMARK_MIN的125%，此时kswapd将被唤醒，可以通过修改watermark_scale_factor来改变比例值；

• WMARK_HIGH
  默认情况下，该值为WMARK_MAX的150%，此时kswapd将睡眠，可以通过修改watermark_scale_factor来改变比例值；

图来了：

下边将对细节进一步分析。

1. watermark初始化

先看一下初始化的相关调用函数：

• nr_free_buffer_pages：统计ZONE_DMA和ZONE_NORMAL中可用页面，managed_pages - high_pages；

• setup_per_zone_wmarks：根据min_free_kbytes来计算水印值，来一张图会比较清晰易懂：

  

• refresh_zone_stat_thresholds：
  先来回顾一下struct pglist_data和struct zone：

typedef struct pglist_data {
...
struct per_cpu_nodestat __percpu *per_cpu_nodestats;
...
} pg_data_t;

struct per_cpu_nodestat {
	s8 stat_threshold;
	s8 vm_node_stat_diff[NR_VM_NODE_STAT_ITEMS];
};

struct zone {
...
struct per_cpu_pageset __percpu *pageset;
...
}

struct per_cpu_pageset {
	struct per_cpu_pages pcp;
#ifdef CONFIG_NUMA
	s8 expire;
	u16 vm_numa_stat_diff[NR_VM_NUMA_STAT_ITEMS];
#endif
#ifdef CONFIG_SMP
	s8 stat_threshold;
	s8 vm_stat_diff[NR_VM_ZONE_STAT_ITEMS];
#endif
};

从数据结构中可以看出，针对Node和Zone，都有一个Per-CPU的结构来存储信息，而refresh_zone_stat_thresholds就跟这两个结构相关，用于更新这两个结构中的stat_threshold字段，具体的计算方式就不表了，此外还计算了percpu_drift_mark，这个在水印判断的时候需要用到该值。阈值的作用就是用来进行判断，从而触发某个行为，比如内存压缩处理等。

• setup_per_zone_lowmem_reserve：
  设置每个zone的lowmem_reserve大小，代码中的实现逻辑如下图所示。

  

• calculate_totalreserve_pages：
  计算各个zone的保留页面，以及系统的总的保留页面，其中会将high watermark看成保留页面。如图：

  

2. watermark判断

老规矩，先看看函数调用关系图：

• __zone_watermark_ok：
  watermark判断的关键函数，从图中的调用关系可以看出，最终的处理都是通过它来完成判断的。还是用图片来说明整体逻辑吧：

  

上图中左边判断是否有足够的空闲页面，右边直接查询free_area[]是否可以最终进行分配。

• zone_watermark_ok：直接调用__zone_watermark_ok`，没有其他逻辑。

• zone_watermark_fast：
  从名字可以看出，这个是进行快速判断，快速的体现主要是在order = 0的时候进行判断决策，满足条件时直接返回true，否则调用__zone_watermark_ok。
  贴个代码吧，清晰明了：

static inline bool zone_watermark_fast(struct zone *z, unsigned int order,
		unsigned long mark, int classzone_idx, unsigned int alloc_flags)
{
	long free_pages = zone_page_state(z, NR_FREE_PAGES);
	long cma_pages = 0;

#ifdef CONFIG_CMA
	/* If allocation can't use CMA areas don't use free CMA pages */
	if (!(alloc_flags & ALLOC_CMA))
		cma_pages = zone_page_state(z, NR_FREE_CMA_PAGES);
#endif

	/*
	 * Fast check for order-0 only. If this fails then the reserves
	 * need to be calculated. There is a corner case where the check
	 * passes but only the high-order atomic reserve are free. If
	 * the caller is !atomic then it'll uselessly search the free
	 * list. That corner case is then slower but it is harmless.
	 */
	if (!order && (free_pages - cma_pages) > mark + z->lowmem_reserve[classzone_idx])
		return true;

	return __zone_watermark_ok(z, order, mark, classzone_idx, alloc_flags,
					free_pages);
}

• zone_watermark_ok_safe：
  在zone_watermark_ok_safe函数中，主要增加了zone_page_state_snapshot的调用，用来计算free_pages，这个计算过程将比直接通过zone_page_state(z, NR_FREE_PAGES)更加精确。

bool zone_watermark_ok_safe(struct zone *z, unsigned int order,
			unsigned long mark, int classzone_idx)
{
	long free_pages = zone_page_state(z, NR_FREE_PAGES);

	if (z->percpu_drift_mark && free_pages < z->percpu_drift_mark)
		free_pages = zone_page_state_snapshot(z, NR_FREE_PAGES);

	return __zone_watermark_ok(z, order, mark, classzone_idx, 0,
								free_pages);
}

percpu_drift_mask在refresh_zone_stat_thresholds函数中设置的，这个在上文中已经讨论过了。
每个zone维护了三个字段用于页面的统计，如下：

struct zone {
...
struct per_cpu_pageset __percpu *pageset;
...
/*
 * When free pages are below this point, additional steps are taken
 * when reading the number of free pages to avoid per-cpu counter
 * drift allowing watermarks to be breached
 */
unsigned long percpu_drift_mark;
...
/* Zone statistics */
atomic_long_t		vm_stat[NR_VM_ZONE_STAT_ITEMS];
}

内核在内存管理中，读取空闲页面与watermark值进行比较，要读取正确的空闲页面值，必须同时读取vm_stat[]和__percpu *pageset计算器。如果每次都读取的话会降低效率，因此设定了percpu_drift_mark值，只有在低于这个值的时候，才触发更精确的计算来保持性能。

__percpu *pageset计数器的值更新时，当计数器值超过stat_threshold值，会更新到vm_stat[]中，如下图：

zone_watermark_ok_safe中调用了zone_page_state_snapshot，与zone_page_state的区别如下图所示：

watermark的分析到此为止，收工！

背景

• Read the fucking source code! --By 鲁迅
• A picture is worth a thousand words. --By 高尔基

说明：

1. Kernel版本：4.14
2. ARM64处理器，Contex-A53，双核
3. 使用工具：Source Insight 3.5， Visio

1. 概述

本文将描述memory compaction，内存碎片整理技术。
内存碎片分为内碎片和外碎片：

• 内碎片：内存页里边的碎片；
• 外碎片：内存页之间的碎片，可能会造成连续物理页面分配失败。

memory compaction就是通过将正在使用的可移动页面迁移到另一个地方以获得连续的空闲页面的方法。针对内存碎片，内核中定义了migrate_type用于描述迁移类型：

• MIGRATE_UNMOVABLE：不可移动，对应于内核分配的页面；
• MIGRATE_MOVABLE：可移动，对应于从用户空间分配的内存或文件；
• MIGRATE_RECLAIMABLE：不可移动，可以进行回收处理；

先来一张memory compaction的概况图：

上图对应的是struct page的操作，而针对物理内存的操作如下图所示：

在之前的文章中提到过pageblock，我们看到图中zone区域是以pageblock为单位上下扫描的，pageblock的大小定义如下（未使用huge table情况下），与Buddy System管理中的最大块大小一致：

/* If huge pages are not used, group by MAX_ORDER_NR_PAGES */
#define pageblock_order		(MAX_ORDER-1)

#define pageblock_nr_pages	(1UL << pageblock_order)

好了，已经有一个初步印象了，那就进一步的分析吧。

1. 数据结构

1.1 compact_priority

/*
 * Determines how hard direct compaction should try to succeed.
 * Lower value means higher priority, analogically to reclaim priority.
 */
enum compact_priority {
	COMPACT_PRIO_SYNC_FULL,
	MIN_COMPACT_PRIORITY = COMPACT_PRIO_SYNC_FULL,
	COMPACT_PRIO_SYNC_LIGHT,
	MIN_COMPACT_COSTLY_PRIORITY = COMPACT_PRIO_SYNC_LIGHT,
	DEF_COMPACT_PRIORITY = COMPACT_PRIO_SYNC_LIGHT,
	COMPACT_PRIO_ASYNC,
	INIT_COMPACT_PRIORITY = COMPACT_PRIO_ASYNC
};

本结构用于描述memory compact的几种不同方式：

• COMPACT_PRIO_SYNC_FULL/MIN_COMPACT_PRIORITY：最高优先级，压缩和迁移以同步的方式完成；
• COMPACT_PRIO_SYNC_LIGHT/MIN_COMPACT_COSTLY_PRIORITY/DEF_COMPACT_PRIORITY：中优先级，压缩以同步方式处理，迁移以异步方式处理；
• COMPACT_PRIO_ASYNC/INIT_COMPACT_PRIORITY：最低优先级，压缩和迁移以异步方式处理。

1.2 compact_result

本结构用于描述压缩处理函数的返回值：

/* Return values for compact_zone() and try_to_compact_pages() */
/* When adding new states, please adjust include/trace/events/compaction.h */
enum compact_result {
	/* For more detailed tracepoint output - internal to compaction */
	COMPACT_NOT_SUITABLE_ZONE,
	/*
	 * compaction didn't start as it was not possible or direct reclaim
	 * was more suitable
	 */
	COMPACT_SKIPPED,
	/* compaction didn't start as it was deferred due to past failures */
	COMPACT_DEFERRED,

	/* compaction not active last round */
	COMPACT_INACTIVE = COMPACT_DEFERRED,

	/* For more detailed tracepoint output - internal to compaction */
	COMPACT_NO_SUITABLE_PAGE,
	/* compaction should continue to another pageblock */
	COMPACT_CONTINUE,

	/*
	 * The full zone was compacted scanned but wasn't successfull to compact
	 * suitable pages.
	 */
	COMPACT_COMPLETE,
	/*
	 * direct compaction has scanned part of the zone but wasn't successfull
	 * to compact suitable pages.
	 */
	COMPACT_PARTIAL_SKIPPED,

	/* compaction terminated prematurely due to lock contentions */
	COMPACT_CONTENDED,

	/*
	 * direct compaction terminated after concluding that the allocation
	 * should now succeed
	 */
	COMPACT_SUCCESS,
};

1.3 migrate_mode

本结构用于描述migrate过程中的不同模式，主要针对同步和异步的处理。

/*
 * MIGRATE_ASYNC means never block
 * MIGRATE_SYNC_LIGHT in the current implementation means to allow blocking
 *	on most operations but not ->writepage as the potential stall time
 *	is too significant
 * MIGRATE_SYNC will block when migrating pages
 * MIGRATE_SYNC_NO_COPY will block when migrating pages but will not copy pages
 *	with the CPU. Instead, page copy happens outside the migratepage()
 *	callback and is likely using a DMA engine. See migrate_vma() and HMM
 *	(mm/hmm.c) for users of this mode.
 */
enum migrate_mode {
	MIGRATE_ASYNC,
	MIGRATE_SYNC_LIGHT,
	MIGRATE_SYNC,
	MIGRATE_SYNC_NO_COPY,
};

1.4 compact_control

compact_control结构体用于在执行compact的时候，维护两个扫描器，对应freepages和migratepages，最终将migratepages中的页拷贝到freepages中去。具体的字段注释足够详尽，不细说了。

/*
 * compact_control is used to track pages being migrated and the free pages
 * they are being migrated to during memory compaction. The free_pfn starts
 * at the end of a zone and migrate_pfn begins at the start. Movable pages
 * are moved to the end of a zone during a compaction run and the run
 * completes when free_pfn <= migrate_pfn
 */
struct compact_control {
	struct list_head freepages;	/* List of free pages to migrate to */
	struct list_head migratepages;	/* List of pages being migrated */
	struct zone *zone;
	unsigned long nr_freepages;	/* Number of isolated free pages */
	unsigned long nr_migratepages;	/* Number of pages to migrate */
	unsigned long total_migrate_scanned;
	unsigned long total_free_scanned;
	unsigned long free_pfn;		/* isolate_freepages search base */
	unsigned long migrate_pfn;	/* isolate_migratepages search base */
	unsigned long last_migrated_pfn;/* Not yet flushed page being freed */
	const gfp_t gfp_mask;		/* gfp mask of a direct compactor */
	int order;			/* order a direct compactor needs */
	int migratetype;		/* migratetype of direct compactor */
	const unsigned int alloc_flags;	/* alloc flags of a direct compactor */
	const int classzone_idx;	/* zone index of a direct compactor */
	enum migrate_mode mode;		/* Async or sync migration mode */
	bool ignore_skip_hint;		/* Scan blocks even if marked skip */
	bool ignore_block_suitable;	/* Scan blocks considered unsuitable */
	bool direct_compaction;		/* False from kcompactd or /proc/... */
	bool whole_zone;		/* Whole zone should/has been scanned */
	bool contended;			/* Signal lock or sched contention */
	bool finishing_block;		/* Finishing current pageblock */
};

2. 调用流程

光看上文的数据结构，会比较零散，看看整体的流程吧。
在内核中，有三种方式来操作memory compact：

1. 在内存分配过程中，由于分配请求不能满足，直接触发内存compact处理；
2. 在没有足够内存的情况下，kcompactd守护线程在后台唤醒，执行compact处理；
3. 手动触发，通过echo 1 > /proc/sys/vm/compact_memory来触发；

图来了：

实际操作一把：
cat /proc/pagetypeinfo如下图：

3. compact处理

这个处理的过程还是很复杂的，下图显示了大概的过程：

下边将针对各个子模块更深入点分析。

• compaction_suitable

  

判断是否执行内存的碎片整理，需要满足以下三个条件：

1. 除去申请的页面，空闲页面数将低于水印值，或者虽然大于等于水印值，但是没有一个足够大的空闲页块；
2. 空闲页面减去两倍的申请页面（两倍表明有足够多的的空闲页面作为迁移目标），高于水印值；
3. 申请的order大于PAGE_ALLOC_COSTLY_ORDER时，计算碎片指数fragindex，根据值来判断；

• isolate_migratepages
isolate_migratepages函数中，迁移扫描器以pageblock为单位，扫描可移动页，最终把可移动的页添加到struct compact_control结构中的migratepages链表中。如下图所示：

  

isolate_freepages的逻辑与isolate_migratepages类似，也是对页进行隔离处理，最终添加cc->freepages链表中。

当空闲扫描器和迁移扫描器完成扫描之后，那就是时候将两个链表中的页做一下migrate操作了。

• migrate_pages

1. 调用compact_alloc函数，从cc->freepages链表中取出一个空闲页；
2. 调用__unmap_and_move来把可移动页移动到空闲页处；
   _unmap_and_move函数涉及到反向映射，以及页缓存等，留在以后再深入看。这个函数两个关键作用：1）调用try_to_unmap删除进程页表中旧的映射关系，在需要访问的时候再重新映射到新的物理地址上；2）调用move_to_new_page函数将旧页移动到新的物理页上，其中在汇编文件arch/arm64/lib/copy_page.S中copy_page函数完成拷贝。

• compact_finished
compact_finished函数主要用于检查compact是否完成。

  

• compaction_deferred/compaction_defer_reset/defer_compaction
  上述这三个函数与内存碎片推迟compact有关，这三个函数是在try_to_compact_pages中调用。当free pages除去申请页面数高于水位值，且申请或备用的迁移类型至少有一个足够大的空闲页面时，可以认为compact成功。在没有成功时，可能需要推迟几次来处理。
  struct zone结构中与之有关的字段如下：

struct zone {
...
	/*
	 * On compaction failure, 1<<compact_defer_shift compactions
	 * are skipped before trying again. The number attempted since
	 * last failure is tracked with compact_considered.
	 */
	unsigned int		compact_considered; //记录推迟次数
	unsigned int		compact_defer_shift; //（1 << compact_defer_shift）=推迟次数，最大为6
	int			           compact_order_failed; //记录碎片整理失败时的申请order值
...
};

1. 概述

本文将讨论memory reclaim内存回收这个话题。

在内存分配出现不足时，可以通过唤醒kswapd内核线程来异步回收，或者通过direct reclaim直接回收来处理。在针对不同的物理页会采取相应的回收策略，而页回收算法采用LRU(Least Recently Used)来选择物理页。

直奔主题吧。

2. LRU和pagevec

2.1 数据结构

简单来说，每个Node节点会维护一个lrvvec结构，该结构用于存放5种不同类型的LRU链表，在内存进行回收时，在LRU链表中检索最少使用的页面进行处理。

为了提高性能，每个CPU有5个struct pagevecs结构，存储一定数量的页面（14），最终一次性把这些页面加入到LRU链表中。

上述的描述不太直观，先看代码，后看图，一目了然！

typedef struct pglist_data {
...
/* Fields commonly accessed by the page reclaim scanner */
struct lruvec		lruvec;
...
}

/*  5种不同类型的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
};

struct lruvec {
	struct list_head		lists[NR_LRU_LISTS];
	struct zone_reclaim_stat	reclaim_stat;  //与回收相关的统计数据
	/* Evictions & activations on the inactive file list */
	atomic_long_t			inactive_age;
	/* Refaults at the time of last reclaim cycle */
	unsigned long			refaults;
#ifdef CONFIG_MEMCG
	struct pglist_data *pgdat;
#endif

/* 14 pointers + two long's align the pagevec structure to a power of two */
#define PAGEVEC_SIZE	14
struct pagevec {
	unsigned long nr;
	unsigned long cold;
	struct page *pages[PAGEVEC_SIZE];  //存放14个page结构
};

/*  每个CPU定义5种类型 */
static DEFINE_PER_CPU(struct pagevec, lru_add_pvec);
static DEFINE_PER_CPU(struct pagevec, lru_rotate_pvecs);
static DEFINE_PER_CPU(struct pagevec, lru_deactivate_file_pvecs);
static DEFINE_PER_CPU(struct pagevec, lru_lazyfree_pvecs);
#ifdef CONFIG_SMP
static DEFINE_PER_CPU(struct pagevec, activate_page_pvecs);
#endif

上述的数据结构，可以用下图来进行说明：

简单来说，在物理内存进行回收的时候可以选择两种方式：

• 直接回收，比如某些只读代码段等；
• 页面内容保存后再回收；

针对页面内容保存又分为两种情况：

1. swap支持的页，写入到swap分区后回收，包括进程堆栈段数据段等使用的匿名页，共享内存页等，swap区可以是一个磁盘分区，也可以是存储设备上的一个文件；
2. 存储设备支持的页，写入到存储设备后回收，主要是针对文件操作，如果不是脏页就直接释放，否则需要先写回；

有上述这几种情况，便产生了5种LRU链表，其中ACTIVE和INACTIVE用于表示最近的访问频率，最终页面也是在这些链表间流转。UNEVITABLE，表示被锁定在内存中，不允许回收的物理页，比如像内核中大部分页框都不允许回收。

2.2 流程分析

看一下LRU链表的整体操作：

上图中，主要实现的功能就是将CPU缓存的页面，转移到lruvec链表中，而在转移过程中，最终会调用pagevec_lru_move_fn函数，实际的转移函数是传递给pagevec_lru_move_fn的函数指针。在这些具体的转移函数中，会对Page结构状态位进行判断，清零，设置等处理，并最终调用del_page_from_lru_list/add_page_to_lru_list接口来从一个链表中删除，并加入到另一个链表中。

首先看看图中最右侧部分中，关于Page状态，在内核中include/linux/page-flags.h中有描述，罗列关键字段如下：

enum pageflags {
    PG_locked,		/* Page is locked. Don't touch. */
    PG_referenced, //最近是否被访问
    PG_dirty,  //脏页
    PG_lru,   //处于LRU链表中
    PG_active, //活动页
    PG_swapbacked,		/* Page is backed by RAM/swap */
    PG_unevictable,		/* Page is "unevictable"  */
}    

针对这些状态在该头文件中还有一系列的宏来判断和设置等处理，罗列几个如下：

ClearPageActive(page);
ClearPageReferenced(page);
SetPageReclaim(page);
PageWriteback(page);
PageLRU(page);
PageUnevictable(page);
...

上述的每个CPU5种缓存struct pagevec，基本描述了LRU链表的几种操作：

• lru_add_pvec：缓存不属于LRU链表的页，新加入的页；
• lru_rotate_pvecs：缓存已经在INACTIVE LRU链表中的非活动页，将这些页添加到INACTIVE LRU链表的尾部；
• lru_deactivate_pvecs：缓存已经在ACTIVE LRU链表中的页，清除掉PG_activate, PG_referenced标志后，将这些页加入到INACTIVE LRU链表中；
• lru_lazyfree_pvecs：缓存匿名页，清除掉PG_activate, PG_referenced, PG_swapbacked标志后，将这些页加入到LRU_INACTIVE_FILE链表中；
• activate_page_pvecs：将LRU中的页加入到ACTIVE LRU链表中；

分析一个典型的流程吧，看看缓存中的页是如何加入到lruvec的LRU链表中，对应到图中的执行流为：pagevec_lru_add --> pagevec_lru_move_fn --> __pagevec_lru_add_fn，分别看看这三个函数，代码简单直接附上：

/*
 * Add the passed pages to the LRU, then drop the caller's refcount
 * on them.  Reinitialises the caller's pagevec.
 */
void __pagevec_lru_add(struct pagevec *pvec)
{
    //直接调用pagevec_lru_move_fn函数，并传入转移函数指针
	pagevec_lru_move_fn(pvec, __pagevec_lru_add_fn, NULL);
}
EXPORT_SYMBOL(__pagevec_lru_add);

static void pagevec_lru_move_fn(struct pagevec *pvec,
	void (*move_fn)(struct page *page, struct lruvec *lruvec, void *arg),
	void *arg)
{
	int i;
	struct pglist_data *pgdat = NULL;
	struct lruvec *lruvec;
	unsigned long flags = 0;

    //遍历缓存中的所有页
	for (i = 0; i < pagevec_count(pvec); i++) {
		struct page *page = pvec->pages[i];
		struct pglist_data *pagepgdat = page_pgdat(page);

       //判断是否为同一个node，同一个node不需要加锁，否则需要加锁处理
		if (pagepgdat != pgdat) {
			if (pgdat)
				spin_unlock_irqrestore(&pgdat->lru_lock, flags);
			pgdat = pagepgdat;
			spin_lock_irqsave(&pgdat->lru_lock, flags);
		}

       //找到目标lruvec，最终页转移到该结构中的LRU链表中
		lruvec = mem_cgroup_page_lruvec(page, pgdat);
		(*move_fn)(page, lruvec, arg);  //根据传入的函数进行回调
	}
	if (pgdat)
		spin_unlock_irqrestore(&pgdat->lru_lock, flags);
    //减少page的引用值，当引用值为0时，从LRU链表中移除页表并释放掉
	release_pages(pvec->pages, pvec->nr, pvec->cold);
    //重置pvec结构
	pagevec_reinit(pvec);
}

static void __pagevec_lru_add_fn(struct page *page, struct lruvec *lruvec,
				 void *arg)
{
	int file = page_is_file_cache(page);
	int active = PageActive(page);
	enum lru_list lru = page_lru(page);

	VM_BUG_ON_PAGE(PageLRU(page), page);
    //设置page的状态位，表示处于Active状态
	SetPageLRU(page);
    //加入到链表中
	add_page_to_lru_list(page, lruvec, lru);
    //更新lruvec中的reclaim_state统计信息
	update_page_reclaim_stat(lruvec, file, active);
	trace_mm_lru_insertion(page, lru);
}

具体的分析在注释中标明了，其余4种缓存类型的迁移都大体类似，至于何时进行迁移以及策略，这个在下文中关于内存回收的进一步分析中再阐述。

正常情况下，LRU链表之间的转移是不需要的，只有在需要进行内存回收的时候，才需要去在ACTIVE和INACTIVE之间去操作。

进入具体的回收分析吧。

3. 页面回收

3.1 数据结构

与memory compact类似，页面回收也有一个与之相关的数据结构：struct scan_control

struct scan_control {
	/* How many pages shrink_list() should reclaim */
	unsigned long nr_to_reclaim;

	/* This context's GFP mask */
	gfp_t gfp_mask;

	/* Allocation order */
	int order;

	/*
	 * Nodemask of nodes allowed by the caller. If NULL, all nodes
	 * are scanned.
	 */
	nodemask_t	*nodemask;

	/*
	 * The memory cgroup that hit its limit and as a result is the
	 * primary target of this reclaim invocation.
	 */
	struct mem_cgroup *target_mem_cgroup;

	/* Scan (total_size >> priority) pages at once */
	int priority;

	/* The highest zone to isolate pages for reclaim from */
	enum zone_type reclaim_idx;

	/* Writepage batching in laptop mode; RECLAIM_WRITE */
	unsigned int may_writepage:1;

	/* Can mapped pages be reclaimed? */
	unsigned int may_unmap:1;

	/* Can pages be swapped as part of reclaim? */
	unsigned int may_swap:1;

	/*
	 * Cgroups are not reclaimed below their configured memory.low,
	 * unless we threaten to OOM. If any cgroups are skipped due to
	 * memory.low and nothing was reclaimed, go back for memory.low.
	 */
	unsigned int memcg_low_reclaim:1;
	unsigned int memcg_low_skipped:1;

	unsigned int hibernation_mode:1;

	/* One of the zones is ready for compaction */
	unsigned int compaction_ready:1;

	/* Incremented by the number of inactive pages that were scanned */
	unsigned long nr_scanned;

	/* Number of pages freed so far during a call to shrink_zones() */
	unsigned long nr_reclaimed;
};

• nr_to_reclaim：需要回收的页面数量；
• gfp_mask：申请分配的掩码，用户申请页面时可以通过设置标志来限制调用底层文件系统或不允许读写存储设备，最终传递给LRU处理；
• order：申请分配的阶数值，最终期望内存回收后能满足申请要求；
• nodemask：内存节点掩码，空指针则访问所有的节点；
• priority：扫描LRU链表的优先级，用于计算每次扫描页面的数量(total_size >> priority，初始值12)，值越小，扫描的页面数越大，逐级增加扫描粒度；
• may_writepage：是否允许把修改过文件页写回存储设备；
• may_unmap：是否取消页面的映射并进行回收处理；
• may_swap：是否将匿名页交换到swap分区，并进行回收处理；
• nr_scanned：统计扫描过的非活动页面总数；
• nr_reclaimed：统计回收了的页面总数；

3.2 总体流程分析

与页面压缩类似，有两种方式来触发页面回收：

1. 内存节点中的内存空闲页面低于low watermark时，kswapd内核线程被唤醒，进行异步回收；
2. 在内存分配的时候，遇到内存不足，空闲页面低于min watermark时，直接进行回收；

两种方式的调用流程如下图所示：

3.3 直接回收

• __alloc_pages_slowpath
  该函数调用_perform_reclaim来对页面进行回收处理后，再重新申请分配页面，如果第一次申请失败，将pcp缓存清空后再retry。

• __perform_reclaim
  该函数中做了以下工作：

1. 如果设置了cpuset_memory_pressure_enabled，则先更新当前任务的cpuset频率表fmeter;
2. 将当前任务的标志置上PF_MEMALLOC，防止递归调用页面回收例程；
3. 调用try_to_free_pages来进行回收处理；
4. 恢复当前任务的标志；

• try_to_free_pages
try_to_free_pages函数中，主要完成了以下工作：

1. 初始化struct scan_control sc结构；
2. 调用throttle_direct_reclaim函数进行判断，该函数会对用户任务的直接回收请求进行限制；
3. 调用do_try_to_free_pages进行回收处理；

   

再来看看throttle_direct_reclaim函数中调用的alloc_direct_reclaim：

只有throttle_direct_reclaim函数返回值为false，页面的回收才会进一步往下执行。

• do_try_to_free_pages

1. 通过delayacct_freepages_start/delayacct_freepages_end量化页面回收的时间开销；
2. 随着回收优先级的调整，通过vmpressure_prio来更新memory pressure值；
3. 循环调用shrink_zones来回收页面，回收页面足够了或者可以进行内存压缩时，就会跳出循环不再进行回收处理；

3.4 异步回收

kswapd内核线程，当空闲页面低于watermark时会被唤醒，进行页面回收处理，balance_pgdat是回收的主函数，如下图：

异步回收线程和同步直接回收存进程在交互的地方：

1. 在低水位情况下进程在直接回收时会唤醒kswapd线程；
2. 异步回收时，kswapd线程也会通过wake_up_all(&pgdat->pfmemalloc_wait)来唤醒等待在该队列上进行同步回收的进程；

kswapd内核线程会在内存节点达到平衡状态时，退出LRU链表的扫描。

3.5 shrink_node

前边铺垫了很多，真正的主角要上场了，不管是同步还是异步的回收，最终都落实在shrink_node函数上。

shrink_node的调用关系如上图所示，下边将针对关键函数进行分析。

• get_scan_count
  这个函数用于获取针对文件页和匿名页的扫描页面数。这个函数决定内存回收每次扫描多少页，匿名页和文件页分别是多少，比例如何分配等。
  在函数的执行过程中，根据四种扫描平衡的方法标签来最终选择计算方式，四种扫描平衡标签如下：

enum scan_balance {
	SCAN_EQUAL,  // 计算出的扫描值按原样使用
	SCAN_FRACT,  // 将分数应用于计算的扫描值
	SCAN_ANON,  // 对于文件页LRU，将扫描次数更改为0
	SCAN_FILE,     // 对于匿名页LRU，将扫描次数更改为0
};

来一张图：

• shrink_node_memcg
shrink_node_memcg函数中，调用了get_scan_count函数之后，获取到了扫描页面的信息后，就开始进入主题对LRU链表进行扫描处理了。它会对匿名页和文件页做平衡处理，选择更合适的页面来进行回收。当回收的页面超过了目标页面数后，将停止对文件页和匿名页两者间LRU页面数少的那一方的扫描，并调整对页面数多的另一方的扫描速度。最后，如果不活跃页面少于活跃页面，则需要将活跃页面迁移到不活跃页面链表中。
  来一张图：

  

• shrink_list
  在shrink_list函数中主要是从lruvec的链表中进行页面回收：

1. 仅当活动页面数多于非活动页面数时才调用shrink_active_list对活动链表处理；
2. 调用shrink_inactive_list对非活动链表进行处理；

• shrink_active_list
  从函数的调用关系图中可以看出，shrink_active_list/shrink_inactive_list函数都调用了isolate_lru_pages函数，有必要先了解一下这个函数。
  isolate_lru_pages函数，完成的工作就是从指定的lruvec中链表扫描目标数量的页面进行分离处理，并将分离的页面以链表形式返回。而在这个过程中，有些特殊页面不能进行分离处理时，会被rotate到LRU链表的头部。

shrink_active_list的整体效果图如下：

先对LRU ACTIVE链表做isolate操作，这部分操作会分离出来一部分页面，然后再对这些分离页面做进一步的判断，根据最近是否被referenced以及其它标志位做处理，基本上有四种去向：
1）rotate回原来的ACTIVE链表中；
2）处理成功移动到对应的UNACTIVE链表中；
3）不再使用返回Buddy系统；
4）如果出现了不可回收的情况（概率比较低），则放回LRU_UNEVICTABLE链表。

• shrink_inactive_list
  内存回收的最后一步就是处理LRU_UNACTIVE链表了，该写回存储设备的写回存储设备，该写到Swap分区的写到Swap分区，最终就是释放处理。
  在提供最终效果图之前，先来分析一下shrink_page_list函数，它是shrink_inactive_list的核心。

  

从上图中可以看出，shrink_page_list函数执行完毕后，页面要不就是rotate回原来的LRU链表中了，要不就是进行回收并最终返回了Buddy System了。

所以，最终的shrink_inactive_list的效果如下图：

页面回收的模块还是挺复杂的，还有很多内容没有深入细扣，比如页面反向映射，memcg内存控制组等。
前前后后看了半个月时间的代码，就此收工。

下一个专题要开始看看SLUB内存分配器了，待续。