背景

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