摘 要：隨著虛擬化的大規(guī)模運用，同一主機的不同的虛擬機可能運行相同的軟件或處理相同的數(shù)據也正在迅速增長。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ā)現(xiàn)匹配穩(wěn)定樹，KSM通過比對頁面的校驗和來確定匿名頁面內容是否改變，如果校驗和自上次KSM掃描以來發(fā)生改變，KSM更新校驗和并跳過本頁面。這是為了避免合并頻繁改變內容的頁面導致不穩(wěn)定樹出現(xià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架構（以及大多數(shù)的體系結構）是4096個字節(jié)。找到一個相等的頁面成本，是將memcmp（）的成本乘以樹的級數(shù)。得益于rbtree的特性，所有的計算時間的復雜度（包括插入/搜索/刪除功能）是O（log（N）），其中N是掃描的KSM的頁面總數(shù)。因此，即使在最糟糕的情況下：前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ā)現(xiàn)內容發(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