多代 LRU

多代 LRU 是一種替代的 LRU 實現，它可以最佳化頁面回收，並在記憶體壓力下提高效能。頁面回收決定了核心的快取策略和過度提交記憶體的能力。它直接影響 kswapd 的 CPU 使用率和 RAM 效率。

設計概述

目標

設計目標是

  • 良好地表示訪問的新近度

  • 嘗試從空間區域性性中獲益

  • 快速路徑做出顯而易見的選擇

  • 簡單的自我糾正啟發法

訪問新近度的表示是所有 LRU 實現的核心。在多代 LRU 中，每一代代表一組具有相似訪問新近度的頁面。各代建立了一個（基於時間的）共同參考框架，因此有助於做出更好的選擇，例如，在計算機上的不同 memcg 之間或資料中心中的不同計算機之間（用於作業排程）。

利用空間區域性性可以在收集訪問位時提高效率。rmap 遍歷以單個頁面為目標，並不試圖從發現新的 PTE 中獲益。頁表遍歷可以掃描地址空間中的所有新 PTE，但地址空間可能過於稀疏而無法獲利。關鍵是最佳化這兩種方法並將它們結合使用。

快速路徑降低了程式碼複雜性和執行時開銷。未對映的頁面不需要 TLB 重新整理；乾淨的頁面不需要寫回。只有當其他條件（例如，訪問新近度）相似時，這些事實才有用。以代為共同參考框架，其他因素會更加突出。但顯而易見的選擇可能不是好的選擇；因此自我糾正至關重要。

簡單的自我糾正啟發法的好處是不言而喻的。同樣，以代為共同參考框架，這變得可以實現。具體來說，同一代中的頁面可以基於其他因素進行分類，並且反饋迴圈可以統計地比較這些類別中的缺頁中斷百分比，並推斷出哪些是更好的選擇。

假設

熱頁面的保護和冷頁面的選擇基於頁面訪問通道和模式。有兩種訪問通道

  • 透過頁表訪問

  • 透過檔案描述符訪問

前一種通道的保護在設計上更強，因為

  1. 由於訪問位的近似，確定前一種通道的訪問模式的不確定性更高。

  2. 由於所需的 TLB 重新整理和遇到髒位的可能性，驅逐前一種通道的成本更高。

  3. 對前一種通道的保護不足的懲罰更高，因為應用程式通常不會像為阻塞 I/O 那樣為主要缺頁中斷做好準備。例如，GUI 應用程式通常使用專用 I/O 執行緒來避免阻塞渲染執行緒。

還有兩種訪問模式

  • 表現出時間區域性性的訪問

  • 不表現出時間區域性性的訪問

由於上述原因，除非存在 VM_SEQ_READ 或 VM_RAND_READ，否則假定前一種通道遵循前一種模式，除非已觀察到異常缺頁中斷，否則假定後一種通道遵循後一種模式。

工作流程概述

對於每個 lruvec，可驅逐頁面分為多個代。最年輕的代號儲存在 lrugen->max_seq 中，用於匿名和檔案型別，因為它們以相同的地位老化。最老的代號儲存在 lrugen->min_seq[] 中，分別用於匿名和檔案型別，因為無論交換約束如何，都可以驅逐乾淨的檔案頁面。這三個變數單調遞增。

代號被截斷為 order_base_2(MAX_NR_GENS+1) 位，以便適應 folio->flags 中的 gen 計數器。每個截斷的代號都是 lrugen->folios[] 的索引。滑動視窗技術用於跟蹤至少 MIN_NR_GENS 個和最多 MAX_NR_GENS 個代。當頁面位於 lrugen->folios[] 之一時，gen 計數器儲存一個在 [1, MAX_NR_GENS] 範圍內的值；否則它儲存零。

每一代都分為多個層級。透過檔案描述符訪問 N 次的頁面位於層級 order_base_2(N) 中。與代不同，層級沒有專用的 lrugen->folios[]。與跨代移動（需要 LRU 鎖）相比，跨層級移動僅涉及 folio->flags 上的原子操作，因此成本可以忽略不計。模仿 PID 控制器的反饋迴圈監視來自匿名和檔案型別的所有層級的缺頁中斷，並決定從哪些型別驅逐或保護哪些層級。所需的效果是平衡匿名和檔案型別之間的缺頁中斷百分比，與交換級別成正比。

有兩個概念上獨立的程式：老化和驅逐。它們形成一個閉環系統，即頁面回收。

老化

老化產生年輕的代。給定一個 lruvec，當 max_seq-min_seq+1 接近 MIN_NR_GENS 時，它會遞增 max_seq。當老化發現熱頁面透過頁表訪問時，它會將熱頁面提升到最年輕的代；當它遞增 max_seq 時，冷頁面的降級會隨之發生。老化使用頁表遍歷和 rmap 遍歷來查詢新的 PTE。對於前者，它迭代 lruvec_memcg()->mm_list，並使用此列表上的每個 mm_struct 呼叫 walk_page_range() 來掃描 PTE，並且在每次迭代後，它會遞增 max_seq。對於後者，當驅逐遍歷 rmap 並找到新的 PTE 時，老化會掃描相鄰的 PTE。對於兩者，在找到新的 PTE 時，老化會清除訪問位，並將此 PTE 對映的頁面的 gen 計數器更新為 (max_seq%MAX_NR_GENS)+1。

驅逐

驅逐消耗舊的代。給定一個 lruvec，當以 min_seq%MAX_NR_GENS 索引的 lrugen->folios[] 變為空時，它會遞增 min_seq。要選擇要從中驅逐的型別和層級，它首先比較 min_seq[] 以選擇較舊的型別。如果兩種型別都同樣舊，它會選擇其第一個層級具有較低缺頁中斷百分比的型別。第一個層級包含單次使用的未映射干淨頁面，這是最佳選擇。如果老化發現此頁面透過頁表訪問並更新了其 gen 計數器，則驅逐會根據其 gen 計數器對頁面進行排序。如果此頁面透過檔案描述符訪問了多次，並且反饋迴圈檢測到此頁面所在的層級的異常缺頁中斷，它也會將頁面移動到下一代，即 min_seq+1。為此，反饋迴圈將第一個層級用作基線，原因如前所述。

工作集保護

每一代都在誕生時蓋上時間戳。如果設定了 lru_gen_min_ttl，則當 lruvec 最舊的代在 lru_gen_min_ttl 毫秒內誕生時，該 lruvec 會受到保護免受驅逐。換句話說，它可以防止 lru_gen_min_ttl 毫秒的工作集被驅逐。如果此工作集無法儲存在記憶體中，則會觸發 OOM killer。

這種基於時間的方法具有以下優點

  1. 它更容易配置，因為它與應用程式和記憶體大小無關。

  2. 它更可靠，因為它直接連線到 OOM killer。

mm_struct 列表

為每個 memcg 維護一個 mm_struct 列表，並且當此任務遷移時，mm_struct 會跟隨其所有者任務到新的 memcg。

頁表遍歷器迭代 lruvec_memcg()->mm_list，並使用此列表上的每個 mm_struct 呼叫 walk_page_range() 來掃描 PTE。當多個頁表遍歷器迭代同一列表時，它們中的每一個都會獲得一個唯一的 mm_struct，因此它們可以並行執行。

頁表遍歷器忽略任何錯位的頁面，例如，如果 mm_struct 已遷移，則噹噹前 memcg 正在回收時，將忽略留在先前 memcg 中的頁面。同樣，頁表遍歷器將忽略來自回收下的節點以外的節點的頁面。

此基礎結構還會跟蹤上下文切換之間 mm_struct 的使用情況，以便頁表遍歷器可以跳過自上次迭代以來一直處於休眠狀態的程序。

Rmap/PT 遍歷反饋

搜尋 rmap 以查詢 LRU 列表上的每個頁面對映的 PTE（以測試和清除訪問位）可能很昂貴，因為來自不同 VMA（PA 空間）的頁面對 rmap（VA 空間）不友好。對於主要使用對映頁面的工作負載，搜尋 rmap 可能會導致回收路徑中最高的 CPU 成本。

lru_gen_look_around() 利用空間區域性性來減少進入 rmap 的次數。它掃描新的 PTE 的相鄰 PTE 並提升熱頁面。如果以快取記憶體行高效地完成掃描，它會將指向 PTE 表的 PMD 條目新增到 Bloom 過濾器。這在驅逐和老化之間形成一個反饋迴圈。

Bloom 過濾器

Bloom 過濾器是一種空間和記憶體高效的資料結構，用於集合成員測試，即測試元素是否不在集合中或可能在集合中。

在驅逐路徑中，具體來說，在 lru_gen_look_around() 中，如果 PMD 具有足夠數量的熱頁面，則將其地址放置在過濾器中。在老化路徑中，集合成員意味著將掃描 PTE 範圍以查詢新的頁面。

請注意，Bloom 過濾器在集合成員資格方面是機率性的。如果測試是假陽性，則成本是額外掃描 PTE 範圍，這可能會產生熱頁面。過濾器本身的引數可以控制限制中的假陽性率。

PID 控制器

模仿比例-積分-微分 (PID) 控制器的反饋迴圈監視匿名和檔案型別的缺頁中斷，並決定當兩種型別都來自同一代時要驅逐哪種型別。

PID 控制器使用代而不是掛鐘作為時間域，因為 CPU 可以在不同的記憶體壓力下以不同的速率掃描頁面。它為每個新代計算移動平均值，以避免永久鎖定在次優狀態。

Memcg LRU

memcg LRU 是每個節點的 memcg 的 LRU。它也是 LRU 的 LRU，因為每個節點和 memcg 組合都有一個 folios 的 LRU（請參閱 mem_cgroup_lruvec()）。它的目標是提高全域性回收的可伸縮性，這對於資料中心中系統範圍內的記憶體過度提交至關重要。請注意，memcg LRU 僅適用於全域性回收。

memcg LRU 的基本結構可以透過類似於 active/inactive LRU（的 folios）來理解

  1. 它具有年輕和舊（代），即 active 和 inactive 的對應項；

  2. max_seq 的遞增觸發提升，即啟用的對應項；

  3. 其他事件觸發類似的操作，例如，離線 memcg 觸發降級，即停用的對應項。

在全域性回收方面，它具有兩個不同的功能

  1. 分片，允許每個執行緒從隨機 memcg（在舊代中）開始並提高並行性；

  2. 最終公平性，允許直接回收隨意退出並減少延遲，而不影響一段時間內的公平性。

在全域性回收期間遍歷 memcg 方面，它將最佳情況複雜度從 O(n) 提高到 O(1)，並且不影響最壞情況複雜度 O(n)。因此，平均而言，它具有亞線性複雜度。

總結

多代 LRU（的 folios）可以分解為以下部分

  • 代

  • Rmap 遍歷

  • 透過 mm_struct 列表的頁表遍歷

  • 用於 rmap/PT 遍歷反饋的 Bloom 過濾器

  • 用於缺頁中斷反饋的 PID 控制器

老化和驅逐形成生產者-消費者模型；具體來說，後者透過對代進行滑動視窗來驅動前者。在老化中，rmap 遍歷透過將熱的密集填充的頁表插入到 Bloom 過濾器來驅動頁表遍歷。在驅逐中，PID 控制器使用缺頁中斷作為反饋來選擇要驅逐的型別和要保護的層級。