c8763yee's website

沒有 RMAP metadata 的情況如何實現 RMAP？#

那麼問題來了，我們要怎麼知道這塊 Page 被哪些虛擬記憶體所對應？若沒有任何資料結構輔助，則只能藉由掃描所有 Task 的 mapping 來找到目標 Page/Folio 對應的 PTE 存取狀態 ( Accessed Bit )，並在沒有任何 Task 對應的時候將 Page/Folio 回收到 SWAP。

而這帶來以下兩個問題：

• 成本與「系統上 PTE 總數」成正比，而不是與「需要回收的 Page 數」成正比。掃描大量映射著熱頁的頁表，是純粹的浪費。
• 被多個 process 共享的 Page 必須等到所有映射都在各自的掃描中被拆掉，才真正可回收。核心無法主動選定一個 Page 一次拆光它的映射，Accessed bit（Page 熱度）也散落在各個 Page table 中，無法針對單一 Page 彙整

以 Linux v2.4 之前的 reclaim 為例。它會由 swap_out() 從 init_mm 開始走訪，線性掃描其 Page table，看哪個 PTE 指向的 Page 可以拆掉映射。

per-page RMAP（pte_chain）#

既然問題是「無法從 Page 找到所有 mapping 到該 Page 的 PTE」，那麼最簡單的方式就是直接在 Page 紀錄所有對應到的 PTE。有鑑於此，Rik van Riel 在 2.4.17-rmap-12e 時提出 RMAP，具體實作是在 struct page 這個資料結構上加入 pte_chain 欄位，其指向一條串起所有對應 PTE 位址的鏈結串列，這樣在 Reclaim 時只需要走訪這個鍊結串列並檢查 Accessed Bit。不用像之前走訪整個系統的所有 PTE 了，該 Patch 於 2.5.27 合併至主線。

1
#define NRPTE ((L1_CACHE_BYTES - sizeof(unsigned long))/sizeof(pte_addr_t))
2

3
// NRPTE = 7 when L1_CACHE_BYTES = 64
4
//         3 when L1_CACHE_BYTES = 32
5

6
struct page {
7
  ...
8
  struct pte_chain *pte_chain;  /* 指向所有映射此頁的 PTE */
9
  ...
10
};
11

12
struct pte_chain {
13
  unsigned long next_and_idx;
14
  pte_addr_t ptes[NRPTE];
15
} ____cacheline_aligned;
16

17
pte_chain_encode(pte_chain, idx):  return (unsigned long)pte_chain | idx;
18
pte_chain_next(pc):  return (struct pte_chain *)(pc->next_and_idx & ~NRPTE);
19
pte_chain_idx(pc):   return pc->next_and_idx & NRPTE;
20

21
page_add_rmap(page, ptep);
22
page_remove_rmap(page, ptep);

pte_chain 時期根本沒有 VMA 層級的插入與刪除。記錄單位是 PTE。

1
page_add_rmap(page, ptep);     /* 缺頁處理時，把 pte 位址串上該 page */
2
page_remove_rmap(page, ptep);  /* unmap 時，線性掃描找到並移除 */

fork()：copy_page_range() 逐一走訪 pte，對每個已映射的 page 呼叫一次 page_add_rmap()。成本 O(頁面數)，記憶體也是 O(映射數)。 munmap() / exit()：zap_pte_range() 逐一 page_remove_rmap()，且刪除時需線性掃描 pte_chain 找到匹配項。

從 per-page 到 per-object 的 RMAP（anon_vma）#

然而這項設計還是有問題，隨著共用 task 數增長，pte_chain 鏈結串列的長度也會增長，整個走訪的時間複雜度為 O(N)\text{，N 為 pte_chain 鍊結串列的長度}。 除此之外，pte_chain 帶來的記憶體開銷與系統本身的記憶體大小成正比，由於 pte_chain 至少需要額外 12 Bytes 的空間，即使只是在配備 128MB RAM 的 32-bit 系統中，pte_chain 帶來的記憶體開銷也需要 400KB。

考慮 pte_chain 本身的記憶體開銷問題，社群接受度並不高，因此社群開始討論如何去除 pte_chain 記憶體開銷。對於 File-back page 可以從 address->i_mmap 反查使用的 PTE，然而 Anon page 沒有類似的資料結構，因此 anon_vma 出現了。

在 2.6.7 ，RMAP 從原本的由 Page 擴充 pte_chain 串連改為讓 Anon/File-back page 共用 mapping 欄位，其中 File-back page 放 address_space，Anon page 放 anon_vma，並透過該指標的 LSB 判斷具體存放內容。

1
struct page {
2
  ...
3
  struct address_space *mapping;
4
  ...
5
};

anon_vma 藉由鏈結串列將屬於自身的 vma 串連起來，多個 Page 會對應到同一個 anon_vma。unmap 時藉由 page->index 算出 page offset 後藉由走訪 anon_vma 中的每個 vma，將 page offset 與該 vma 的起始位址相加來判斷這個 vma 與 page 是否關聯，並找出其對應的 PTE。

1
struct anon_vma {
2
  spinlock_t lock;
3
  struct list_head head;   /* 串接 vma->anon_vma_node */
4
};

• 插入（Page fault）：anon_vma_prepare(vma)。先透過 find_mergeable_anon_vma() 嘗試沿用相鄰可合併 VMA 的 anon_vma，找不到才配置新的，最後 list_add(&vma->anon_vma_node, &anon_vma->head)。
• 插入（fork）：anon_vma_link(vma)。子行程直接沿用親代行程的 anon_vma，把自己的節點掛上同一條串列。
• 插入（vma 分裂）：split_vma() 產生的新 VMA 共用同一個 anon_vma，同樣 anon_vma_link()。
• 刪除：anon_vma_unlink(vma)，list_del() 後檢查串列是否已空，空了就釋放 anon_vma。

從 anon_vma 到 anon_vma_chain#

2004 年引入的 anon_vma 解決了 pte_chain 的記憶體開銷，但它對 fork() 的處理過於粗糙：子行程的 VMA 直接掛進親代行程的 anon_vma，整個行程家族共用同一個 anon_vma。

Andrew morton 曾經在 2003 年 object rmap 被合併前針對該機制提出疑惑，object rmap 設計是走訪整個物件 (如 anon_vma 或 address_space) 上關聯的所有 vma，這時一定會走訪到完全無關於要回收 Page 的 vma，並且花費大量時間在走訪動作。反而是 pte_chain 只需要針對 page 相關的 pte 走訪即可。同時他還用一個極端案例說明問題：對於使用相同檔案的 1000 個 Task，當每個 Task 在相同檔案使用 1000 個 vma 時，總共會有 100 萬個 vma，並且在 unmap 時無論如何都需要走訪這 100 萬個 vma。雖然他只提到 File-back page，然而既然說是設計本身問題，代表 Anon page 也有可能出現相同問題。

Andrew 當時本人傾向認為這只是「理論上可能發生」，問題不大，畢竟 2.4 的 virtual scan 設計也有相同問題但沒人遇到。然而 7 年後，Andrew morton 擔心的事確實發生了。

Without the anon_vma changes, when AIM7 hits around 9.7k users (on a test box with 16GB RAM and not quite enough IO), the system ends up running >99% in system time, with every CPU on the same anon_vma lock in the pageout code.

Rik van Riel 發現 AIM7 Benchmark 當使用者數量到 9.7k 時卡死，並且大部分時間都在搶佔 anon_vma 的鎖上面，這也印證了上面提到的需要花費大量時間在走訪的問題。

有鑑於此，Rik van Riel 針對上述問題提出修改的 PATCH，具體想法為針對各個行程建立一個 anon_vma 並使用 anon_vma_chain 資料結構串連 anon_vma 與 vma，再使用 same_vma 與 same_anon_vma 將映射到相同的「vma 或 anon_vma」的 avc 串連起來，行成多對多的關聯。

應用此 PATCH 後 AIM7 到 29.7k 個使用者才開始卡死，並且瓶頸變為 I/O 等待。

1
struct anon_vma_chain {
2
  struct vm_area_struct *vma;
3
  struct anon_vma *anon_vma;
4
  struct list_head same_vma; // 所有鏈結到相同 anon_vma 的 avc
5
  struct list_head same_anon_vma; // 所有鏈結到相同 vma 的 avc
6
};

對應核心 commit/patch：

• 5beb49305251（mm: change anon_vma linking to fix multi-process server scalability issue）。

anon_vma_chain interval tree#

把 same_anon_vma 鏈結串列換成 interval tree（以 augmented rbtree 實作），以每個 VMA 覆蓋的 [\text{vm_pgoff}, \text{vm_pgoff} + \text{vma_pages}) 區間為鍵。RMAP 走訪改為對目標 pgoff 做 stabbing query，只回傳區間真正覆蓋該 pgoff 的 VMA，複雜度 O(log n + 命中數)。同一個 merge window 中，file-back page 這一側行之有年的 prio_tree 也被同一套 interval tree 取代（6b2dbba8b6ac），anon 與 file 的反向走訪自此共用同一種索引結構，也就是今日 anon_vma_interval_tree_foreach() 與 vma_interval_tree_foreach() 巨集的由來。

1
struct anon_vma_chain {
2
  struct vm_area_struct *vma;
3
  struct anon_vma *anon_vma;
4
  struct list_head same_vma;   /* locked by mmap_lock & page_table_lock */
5
  struct rb_node rb;      /* locked by anon_vma->rwsem */
6
  unsigned long rb_subtree_last;
7
#ifdef CONFIG_DEBUG_VM_RB
8
  unsigned long cached_vma_start, cached_vma_last;
9
#endif
10
};

RMAP 走訪時，首先從 Page->mapping 獲取 anon_vma，接著從 anon_vma->rb_root 持續走訪 anon_vma_chain interval tree 檢查對應的 vma 的 vm_start 與 vm_end 判斷這個 vma 對應的 pte 是否 mapping 到這個 Page。

對應核心 commit：

• bf181b9f9d8d（mm anon rmap: replace same_anon_vma linked list with an interval tree）

觀察 Active/Inactive List 如何使用 RMAP#

傳統 Active/Inactive list 的存取偵測完全建立在 RMAP 上。核心無法在硬體設定 Accessed bit 的當下得到通知，只能事後輪詢：folio_referenced() 對 folio 做一次 RMAP 走訪，逐一檢查並清除所有映射 PTE 的 Accessed bit，回傳「自上次檢查以來被幾個 VMA 存取」。

具體來說會有兩個路徑會進行 RMAP 走訪

1. Demotion 時檢查 Active LRU list 的尾端 folio 有沒有被存取過，如果沒有就被移到 inactive list
2. Eviction 時檢查 Inactive LRU list 的尾端 folio 有沒有被存取過，如果沒有就把這個 Folio 丟棄，否則重新移回 Inactive list

以 kswapd 為例，其呼叫 RMAP 的路徑為：

1
kswapd -> balance_pgdat -> shrink_node -> shrink_lruvec
2
  ├── shrink_active_list
3
  │    └── folio_referenced -> __rmap_walk_file
4
  │         ├── folio_referenced_one -> page_vma_mapped_walk
5
  │         └── vma_interval_tree_iter_first
6
  └── shrink_folio_list
7
       ├── folio_referenced -> __rmap_walk_file -> folio_referenced_one
8
       │        └── page_vma_mapped_walk
9
       └── try_to_unmap -> __rmap_walk_file -> try_to_unmap_one
10
                └── set_tlb_ubc_flush_pending

MGLRU 如何減少 RMAP 開銷#

架構改進#

首先，從架構層面來說，Active/Inactive List 在 eviction 的時候需要同時對 active 與 inactive LRU List 操作，而 MGLRU 由於其 Generation 自然老化的特性，因此在 eviction 時只須針對最老的 generation (min_seq) 操作。

1
kswapd -> balance_pgdat -> kswapd_shrink_node -> shrink_node
2
└── lru_gen_shrink_node
3
    └── shrink_one（global）／shrink_many -> shrink_one（memcg）
4
        └── try_to_shrink_lruvec -> evict_folios
5
            └── shrink_folio_list
6
                ├── folio_check_references -> folio_referenced
7
                │   └── rmap_walk -> rmap_walk_anon／rmap_walk_file
8
                │       └── folio_referenced_one
9
                │           └── page_vma_mapped_walk        # 固定成本在這之前全數付清
10
                │               └── lru_gen_look_around     # 邊際成本近零的 64-PTE 視窗
11
                │                   ├── get_pte_pfn / get_pfn_folio
12
                │                   ├── walk_update_folio   # 鄰居就地升代
13
                │                   └── update_bloom_filter # 回饋給 aging
14
                └── try_to_unmap -> rmap_walk -> try_to_unmap_one

接著來看 RMAP 走訪的成本結構。folio_referenced() 為了檢查一個 PTE 的 Accessed bit，固定要付：取得 vma object lock、interval tree 走訪、page_vma_mapped_walk() 逐層下降 Page table 定位 PTE、取得 page table lock（PTL）。而 LRU 依實體頁組織，串列上相鄰 folio 來自各 process 的不同 VMA。因此每次走訪都是一組毫無快取重用的鎖與樹操作。固定成本高、又完全不均攤，這就是為什麼 page_vma_mapped_walk 吃掉 kswapd 18.47% CPU。

1
    patch1-6
2
      39.03%  lzo1x_1_do_compress (real work)
3
      18.47%  page_vma_mapped_walk (overhead)
4
       6.74%  _raw_spin_unlock_irq
5
       3.97%  do_raw_spin_lock
6
       2.49%  ptep_clear_flush
7
       2.48%  anon_vma_interval_tree_iter_first
8
       1.92%  folio_referenced_one
9
       1.88%  __zram_bvec_write
10
       1.48%  memmove
11
       1.31%  vma_interval_tree_iter_next
12

13
    patch1-7
14
      48.16%  lzo1x_1_do_compress (real work)
15
       8.20%  page_vma_mapped_walk (overhead)
16
       7.06%  _raw_spin_unlock_irq
17
       2.92%  ptep_clear_flush
18
       2.53%  __zram_bvec_write
19
       2.11%  do_raw_spin_lock
20
       2.02%  memmove
21
       1.93%  lru_gen_look_around
22
       1.56%  free_unref_page_list
23
       1.40%  memset

因此 lru_gen_look_around() 利用記憶體的空間局部性來改善頁面回收與熱頁面識別，當 shrink_folio_list 找到一個 Hot PTE (Accessed Bit = 1) 時以該 PTE 位址為中心劃出一個 PMD scan window，在其中搜尋總共 BITS_PER_LONG 個 PTE，檢查這些鄰近 PTE 的 Access bit 是否也為 1 (young) 並在足夠多 Hot page 時將 PMD 加入 Bloom filter 以在 Aging 時作為輔助判斷資訊。

$f(young, total) = young \times n \ge total$ $n=clamp(cacheline\div sizeof(pte),2,8)$

最後是 Aging 部份，前面講到當 PMD 中包含足夠多 Hot page 時就會將 PMD 加入 Bloom filter，在 Aging 進行 Page Table 走訪時，會先對每個 PMD entry 查詢 Bloom Filter。如果該 PMD 存在於 Bloom filter，表示該 PMD 的 Hot page 密度足夠高，值得繼續走訪裡面的 PTE 並進行 Promote/Protect。

Reclaim 行為#

• cgroup memory.reclaim
  • 主動式，手動觸發
  • echo <size> > /sys/fs/cgroup/<cg-name>/memory.reclaim
• direct reclaim
  • 反應式，觸發於可用記憶體極度缺乏（水位低於 WMARK_MIN）
  • 同步執行，Page fault 時檢查記憶體水位
  • 水位提昇至 WMARK_LOW 後停止
• kswapd
  • 可用記憶體水位低於 WMARK_LOW 觸發
  • 背景執行，在 WMARK_HIGH 時停止

Google：kstaled / Kreclaimd (ASPLOS 2019)#

• kstaled：週期性走訪 Page table 讀取 Page 的 Accessed bit 以追蹤 Page age
• kreclaimd：將 Page age 超過門檻的 page swap out (壓縮到 Zswap)
• 架構發展：
  1. sysfs + bitmap
  2. kstaled / kreclaimd
• Overhead 隨記憶體大小與掃描頻率線性成長
  • kstaled 掃描改為 PMD linked list 走訪 (降低 3.5 倍 CPU 使用)
  • kreclaimd 改為接收 kstaled 資料

DAMON/S (Data Access MONitoring[-based operation Schemes])#

• By SeongJae Park (sjp38)，前 Amazon 員工
• Region-based sampling
  • 將監測粒度從 Google 上面架構的 Page 改為 Region (可自訂 Region 大小)
  • 使用抽樣法觀測 Region 熱度
  • 每次取樣在每個 region 內隨機挑一個 Page，等一個 interval 後檢查它是否被存取，命中就把該 region 的 nr_accesses 加 1。
• Adaptive Regions Adjustment
  • 前提是同一 region 內頁面熱度相近，而存取模式會變，所以 DAMON 依存取頻率自動合併與分裂 region，持續維持這個前提。
• 可基於觀測到資訊設計 reclaim 策略（DAMOS）
  • Example: DAMON_RECLAIM