核心同頁合併¶
KSM 是一種節省記憶體的去重功能，由 CONFIG_KSM=y 啟用，在 2.6.32 版本中新增到 Linux 核心。有關其實現，請參見 mm/ksm.c，以及 http://lwn.net/Articles/306704/ 和 https://lwn.net/Articles/330589/
KSM 的使用者空間介面在 核心同頁合併 中描述
設計¶
概述¶
關於 KSM 掃描過程的一些說明，以便更容易理解下面的資料結構
為了減少過多的掃描，KSM 將記憶體頁按其內容排序到一種資料結構中，該資料結構儲存指向頁面位置的指標。
由於頁面的內容可能隨時更改，KSM 不能只是將頁面插入到普通的排序樹中並期望它能找到任何東西。因此，KSM 使用兩個資料結構——穩定樹和不穩定樹。
穩定樹儲存指向所有合併頁面（ksm 頁面）的指標，按其內容排序。因為每個這樣的頁面都是防寫的，所以在這個樹上搜索完全可以保證工作（除非頁面被取消對映），因此這個樹被稱為穩定樹。
穩定樹節點包括從 KSM 頁面反向對映到對映此頁面的虛擬地址所需的資訊。
為了避免 KSM 頁面上的 rmap 遍歷的大延遲，KSM 在穩定樹中維護兩種型別的節點
常規節點，將反向對映結構儲存在連結串列中
“鏈”，它連結代表相同防寫記憶體內容的節點（“副本”），但每個“副本”對應於該內容的不同 KSM 頁面副本
在內部，常規節點、“副本”和“鏈”使用相同的 struct ksm_stable_node 結構表示。
除了穩定樹之外，KSM 還使用第二個資料結構，稱為不穩定樹：這個樹儲存指向已被發現“在一段時間內未更改”的頁面的指標。不穩定樹按其內容對這些頁面進行排序，但由於它們不是防寫的，因此 KSM 不能依賴於不穩定樹來正確工作——不穩定樹很容易在其內容被修改時損壞，因此它被稱為不穩定。
KSM 通過幾種技術解決了這個問題
每次 KSM 完成掃描所有記憶體區域時，不穩定樹都會被重新整理，然後從頭開始重新構建該樹。
KSM 只會將雜湊值自上次掃描所有記憶體區域以來沒有更改的頁面插入到不穩定樹中。
不穩定樹是紅黑樹 - 因此它的平衡是基於節點的顏色而不是它們的內容，即使樹被“損壞”也不會失去平衡，所以掃描時間保持不變（此外，在 rbtree 中搜索和插入節點使用相同的演算法，所以我們在重新整理和重建時沒有開銷）。
KSM 從不重新整理穩定樹，這意味著即使在不穩定樹中找到頁面需要 10 次嘗試，一旦找到它，它就會被安全地儲存在穩定樹中。（當我們掃描一個新頁面時，我們首先將其與穩定樹進行比較，然後與不穩定樹進行比較。）
如果未設定 merge_across_nodes 可調引數，則 KSM 維護多個穩定樹和多個不穩定樹：每個 NUMA 節點各一個。
反向對映¶
KSM 在穩定樹中維護 KSM 頁面的反向對映資訊。
如果一個 KSM 頁面在小於 max_page_sharing VMA 之間共享，則代表該 KSM 頁面的穩定樹節點指向 struct ksm_rmap_item 列表，並且 KSM 頁面的 page->mapping 指向穩定樹節點。
當共享超過此閾值時，KSM 會向穩定樹新增第二個維度。樹節點變成“鏈”，它連結一個或多個“副本”。每個“副本”都儲存 KSM 頁面的反向對映資訊，其中 page->mapping 指向該“副本”。
每個“鏈”和連結到“鏈”中的所有“副本”都強制執行這樣一個不變性，即它們代表相同的防寫記憶體內容，即使每個“副本”將由該內容的不同 KSM 頁面副本指向。
這樣，與無限的反向對映列表相比，穩定樹查詢的計算複雜性不受影響。仍然強制執行穩定樹本身中不能存在 KSM 頁面內容副本。
max_page_sharing 強制執行的去重限制是必需的，以避免虛擬記憶體 rmap 列表增長過大。rmap 遍歷具有 O(N) 複雜度，其中 N 是共享該頁面的 rmap_items（即虛擬對映）的數量，這反過來受到 max_page_sharing 的限制。因此，這有效地將線性 O(N) 計算複雜度從 rmap 遍歷上下文分散到不同的 KSM 頁面上。ksmd 在 stable_node “鏈”上的遍歷也是 O(N)，但 N 是 stable_node “副本”的數量，而不是 rmap_items 的數量，因此它對 ksmd 效能沒有顯著影響。實際上，最佳 stable_node “副本”候選者將被保留並在“副本”列表的頭部找到。
max_page_sharing 的高值會導致更快的記憶體合併（因為將有更少的 stable_node 副本排隊到 stable_node chain->hlist 中以檢查修剪）和更高的去重因子，但代價是任何 KSM 頁面的 rmap 遍歷的最壞情況會更慢，這可能發生在交換、壓縮、NUMA 平衡和頁面遷移期間。
stable_node_dups/stable_node_chains 比率也受到 max_page_sharing 可調引數的影響，高比率可能表明 stable_node 副本中的碎片，這可以透過在 ksmd 中引入碎片整理演算法來解決，這將 rmap_items 從一個 stable_node 副本重新歸檔到另一個 stable_node 副本，以便釋放 stable_node “副本”，其中包含的 rmap_items 很少，但這可能會增加 ksmd 的 CPU 使用率，並可能減慢應用程式的 KSM 頁面上的只讀計算。
定期掃描連結到 stable_node “鏈”中的 stable_node “副本”的整個列表，以便修剪陳舊的 stable_nodes。此類掃描的頻率由 stable_node_chains_prune_millisecs sysfs 可調引數定義。
參考¶
-
struct ksm_scan¶
掃描遊標
定義:
struct ksm_scan {
struct ksm_mm_slot *mm_slot;
unsigned long address;
struct ksm_rmap_item **rmap_list;
unsigned long seqnr;
};
成員
mm_slot我們當前掃描的 mm_slot
地址在該槽中要掃描的下一個地址
rmap_list連結到 rmap_list 中要掃描的下一個 rmap
seqnr已完成的完整掃描計數（刪除不穩定節點時需要）
描述
此遊標結構只有一個 ksm_scan 例項。
-- Izik Eidus, Hugh Dickins, 2009 年 11 月 17 日