背景

• 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 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記憶體分配器了，待續，

標籤：Linux

上一篇：Linux 重置密碼

下一篇：NCCL(Nvidia Collective multi-GPU Communication Library) Nvidia英偉達的Multi-GPU多卡通信框架NCCL 學習；PCIe 速率調研；