Linux內存優(yōu)化KSM

摘 要：隨著虛擬化的大規(guī)模運用，同一主機的不同的虛擬機可能運行相同的軟件或處理相同的數據也正在迅速增長。KSM是一個Linux內核模塊，允許在不同的進程和KVM虛擬機共享匿名內存。KSM主要任務是系統(tǒng)中找到相同的頁面。它使用了兩棵樹，一個是穩(wěn)定樹，另一種是不穩(wěn)定樹。穩(wěn)定樹只包含已經共享的匿名頁，不穩(wěn)定樹只包含由KSM監(jiān)測但未共享的頁面。本文介紹了KSM的穩(wěn)定樹和不穩(wěn)定樹，分析了KSM不穩(wěn)定樹的不穩(wěn)定性，以及KSM的改進。

關鍵詞：KSM，rbtrees，匿名頁

中圖分類號：TP316.81

1 穩(wěn)定樹和不穩(wěn)定樹

KSM樹算法使用兩個rbtrees，一個是穩(wěn)定樹，另一個是不穩(wěn)定樹。使用兩棵樹是一種優(yōu)化，對最有可能適合使用共享樹的虛擬內存區(qū)域，使用兩棵樹會增加頁面共享的概率，同時減少不穩(wěn)定樹的不穩(wěn)定。

對于每一個匿名頁掃描，內核線程首先在穩(wěn)定樹中搜索匹配，穩(wěn)定樹中只包含已經共享的頁面，其中的共享頁面是寫保護，因此其內容是穩(wěn)定的。如果在穩(wěn)定樹找到匹配，匿名頁面就與KSM頁面合并到穩(wěn)定樹中。

如果沒有發(fā)現匹配穩(wěn)定樹，KSM通過比對頁面的校驗和來確定匿名頁面內容是否改變，如果校驗和自上次KSM掃描以來發(fā)生改變，KSM更新校驗和并跳過本頁面。這是為了避免合并頻繁改變內容的頁面導致不穩(wěn)定樹出現顛簸。如果校驗和不變，則搜索不穩(wěn)定樹。如果在不穩(wěn)定樹找到匹配頁，則將不穩(wěn)定樹中的匿名頁刪除，并將合并的KSM匿名頁加入到穩(wěn)定樹中，如果在不穩(wěn)定樹中找不到匹配項，則將匿名頁加入到不穩(wěn)定樹中。當然，也可以通過頁表項dirty位的改變，發(fā)信號通知KSM加入頁表項對應的匿名頁加入到不穩(wěn)定樹中。或通過CPU的特殊指令（這與具體的體系結構相關）加速計算校驗和。這里的校驗和本身和KSM樹算法無關。不使用校驗也能找到相同的頁面；校驗和本身只是保持不穩(wěn)定樹的穩(wěn)定，避免將頻繁變化的頁加入不穩(wěn)定樹中。即使我們不計算校驗和，KSM合并算法仍然可以工作。

2 不穩(wěn)定樹的不穩(wěn)定性

我們必須避免不共享的頁面的寫保護，我們同時要避免通過KSM對整個虛擬內存掃描使匿名頁在大部分時間都是寫保護，這將導致大量的寫時復制導致系統(tǒng)不可用。穩(wěn)定樹只包含共享KSM頁，因為頁面是寫保護的，頁面內容不會改變。而不穩(wěn)定樹只包含非共享的匿名頁面，仍然可以通過應用程序改寫匿名頁面，不穩(wěn)定樹的查找會產生問題，圖1是不穩(wěn)定樹的一個例子，它是穩(wěn)定的。然而，如果一個應用程序寫入不穩(wěn)定樹中的頁面索引的第一個字節(jié)，比如頁插入穩(wěn)定樹時第一個字節(jié)是0x3，之后應用程序改變?yōu)?x07，如圖2所示不穩(wěn)定樹可能變得不穩(wěn)定，這時的查找可能產生錯誤。

為了避免不穩(wěn)定和查找產生的錯誤，在每一次KSM掃描后，KSM清空不穩(wěn)定樹，這樣新的不穩(wěn)定樹會在下次掃描時重建，這就避免了查找錯誤。

圖1 KSM不穩(wěn)定樹

圖2 KSM不穩(wěn)定樹的不穩(wěn)定性

3 KSM頁合并

用于頁面合并的過程包含兩個功能：page_wrprotect（）和replace_page（）。前者寫保護所有頁表映射的頁面；后者合并兩個頁面并相應更新頁表，然后釋放已合并且沒有頁表映射的匿名頁面。在page_wrprotect（）之后，通過memcmp（）確定兩個頁面內容完全相同，之后用replace_page合并頁。

4 計算時間的復雜度

通常的x86架構（以及大多數的體系結構）是4096個字節(jié)。找到一個相等的頁面成本，是將memcmp（）的成本乘以樹的級數。得益于rbtree的特性，所有的計算時間的復雜度（包括插入/搜索/刪除功能）是O（log（N）），其中N是掃描的KSM的頁面總數。因此，即使在最糟糕的情況下：前4092個字節(jié)的所有頁面是相等的，只有最后一個4個字節(jié)不同，KSM樹算法性能也不會降低太多。當然在memcmp（）之前，如果引入hash算法，能夠提高KSM樹算法的性能，然而vmware公司的專利技術是不能回避的問題。

5 KSM改進PKSM/UKSM

5.1 對用戶透明

自動添加全系統(tǒng)的用戶進程的匿名頁面到PKSM中，因此不在需要用戶修改用戶程序

5.2 高效的匿名內存頁面檢測

自動檢測匿名頁面的創(chuàng)建和釋放，使用新的算法和機制來直接處理Linux內核創(chuàng)建/釋放匿名頁面。PKSM不再需要浪費大量的CPU來遍歷所有的VMA區(qū)域來查找可用的匿名頁面。

5.3 考慮內容全零頁面

PKSM將全零內存塊視作特殊的內存頁面，并將他們合并到一個特殊的不能交換的pksm zero page。

5.4 周期性檢查內存塊的內容

PKSM將不穩(wěn)定的匿名頁面放入一個FIFO隊列中，周期性地檢查其這些匿名頁面的校驗值，如果發(fā)現內容發(fā)生變化，那麼這些頁面會重新進行比較和合并。系統(tǒng)默認每20分鐘檢查完所有的不穩(wěn)定的匿名頁面。

參考文獻：

[1]Daniel P.Bovet，Marco Cesati，陳莉君，譯.深入理解Linux內核[M].北京：中國電力出版社，2007（09）.

[2]ksm tries again[OL].http：//lwn.net/Articles/330589/.

[3]Anon-page KSM.Data Deduplication for Linux Kernel[OL].http：//code.google.com/p/pksm/.

作者單位：華為武漢研究所，武漢 430073