论文部分内容阅读
摘 要：随着虚拟化的大规模运用，同一主机的不同的虚拟机可能运行相同的软件或处理相同的数据也正在迅速增长。KSM是一个Linux内核模块，允许在不同的进程和KVM虚拟机共享匿名内存。KSM主要任务是系统中找到相同的页面。它使用了两棵树，一个是稳定树，另一种是不稳定树。稳定树只包含已经共享的匿名页，不稳定树只包含由KSM监测但未共享的页面。本文介绍了KSM的稳定树和不稳定树，分析了KSM不稳定树的不稳定性，以及KSM的改进。
关键词：KSM，rbtrees，匿名页
中图分类号：TP316.81
1 稳定树和不稳定树
KSM树算法使用两个rbtrees，一个是稳定树，另一个是不稳定树。使用两棵树是一種优化，对最有可能适合使用共享树的虚拟内存区域，使用两棵树会增加页面共享的概率，同时减少不稳定树的不稳定。
对于每一个匿名页扫描，内核线程首先在稳定树中搜索匹配，稳定树中只包含已经共享的页面，其中的共享页面是写保护，因此其内容是稳定的。如果在稳定树找到匹配，匿名页面就与KSM页面合并到稳定树中。
如果没有发现匹配稳定树，KSM通过比对页面的校验和来确定匿名页面内容是否改变，如果校验和自上次KSM扫描以来发生改变，KSM更新校验和并跳过本页面。这是为了避免合并频繁改变内容的页面导致不稳定树出现颠簸。如果校验和不变，则搜索不稳定树。如果在不稳定树找到匹配页，则将不稳定树中的匿名页删除，并将合并的KSM匿名页加入到稳定树中，如果在不稳定树中找不到匹配项，则将匿名页加入到不稳定树中。当然，也可以通过页表项dirty位的改变，发信号通知KSM加入页表项对应的匿名页加入到不稳定树中。或通过CPU的特殊指令（这与具体的体系结构相关）加速计算校验和。这里的校验和本身和KSM树算法无关。不使用校验也能找到相同的页面；校验和本身只是保持不稳定树的稳定，避免将频繁变化的页加入不稳定树中。即使我们不计算校验和，KSM合并算法仍然可以工作。
2 不稳定树的不稳定性
我们必须避免不共享的页面的写保护，我们同时要避免通过KSM对整个虚拟内存扫描使匿名页在大部分时间都是写保护，这将导致大量的写时复制导致系统不可用。稳定树只包含共享KSM页，因为页面是写保护的，页面内容不会改变。而不稳定树只包含非共享的匿名页面，仍然可以通过应用程序改写匿名页面，不稳定树的查找会产生问题，图1是不稳定树的一个例子，它是稳定的。然而，如果一个应用程序写入不稳定树中的页面索引的第一个字节，比如页插入稳定树时第一个字节是0x3，之后应用程序改变为0x07，如图2所示不稳定树可能变得不稳定，这时的查找可能产生错误。
为了避免不稳定和查找产生的错误，在每一次KSM扫描后，KSM清空不稳定树，这样新的不稳定树会在下次扫描时重建，这就避免了查找错误。
图1 KSM不稳定树
图2 KSM不稳定树的不稳定性
3 KSM页合并
用于页面合并的过程包含两个功能：page_wrprotect（）和replace_page（）。前者写保护所有页表映射的页面；后者合并两个页面并相应更新页表，然后释放已合并且没有页表映射的匿名页面。在page_wrprotect（）之后，通过memcmp（）确定两个页面内容完全相同，之后用replace_page合并页。
4 计算时间的复杂度
通常的x86架构（以及大多数的体系结构）是4096个字节。找到一个相等的页面成本，是将memcmp（）的成本乘以树的级数。得益于rbtree的特性，所有的计算时间的复杂度（包括插入/搜索/删除功能）是O（log（N）），其中N是扫描的KSM的页面总数。因此，即使在最糟糕的情况下：前4092个字节的所有页面是相等的，只有最后一个4个字节不同，KSM树算法性能也不会降低太多。当然在memcmp（）之前，如果引入hash算法，能够提高KSM树算法的性能，然而vmware公司的专利技术是不能回避的问题。
5 KSM改进PKSM/UKSM
5.1 对用户透明
自动添加全系统的用户进程的匿名页面到PKSM中，因此不在需要用户修改用户程序
5.2 高效的匿名内存页面检测
自动检测匿名页面的创建和释放，使用新的算法和机制来直接处理Linux内核创建/释放匿名页面。PKSM不再需要浪费大量的CPU来遍历所有的VMA区域来查找可用的匿名页面。
5.3 考虑内容全零页面
PKSM将全零内存块视作特殊的内存页面，并将他们合并到一个特殊的不能交换的pksm zero page。
5.4 周期性检查内存块的内容
PKSM将不稳定的匿名页面放入一个FIFO队列中，周期性地检查其这些匿名页面的校验值，如果发现内容发生变化，那麽这些页面会重新进行比较和合并。系统默认每20分钟检查完所有的不稳定的匿名页面。
参考文献：
[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
关键词：KSM，rbtrees，匿名页
中图分类号：TP316.81
1 稳定树和不稳定树
KSM树算法使用两个rbtrees，一个是稳定树，另一个是不稳定树。使用两棵树是一種优化，对最有可能适合使用共享树的虚拟内存区域，使用两棵树会增加页面共享的概率，同时减少不稳定树的不稳定。
对于每一个匿名页扫描，内核线程首先在稳定树中搜索匹配，稳定树中只包含已经共享的页面，其中的共享页面是写保护，因此其内容是稳定的。如果在稳定树找到匹配，匿名页面就与KSM页面合并到稳定树中。
如果没有发现匹配稳定树，KSM通过比对页面的校验和来确定匿名页面内容是否改变，如果校验和自上次KSM扫描以来发生改变，KSM更新校验和并跳过本页面。这是为了避免合并频繁改变内容的页面导致不稳定树出现颠簸。如果校验和不变，则搜索不稳定树。如果在不稳定树找到匹配页，则将不稳定树中的匿名页删除，并将合并的KSM匿名页加入到稳定树中，如果在不稳定树中找不到匹配项，则将匿名页加入到不稳定树中。当然，也可以通过页表项dirty位的改变，发信号通知KSM加入页表项对应的匿名页加入到不稳定树中。或通过CPU的特殊指令（这与具体的体系结构相关）加速计算校验和。这里的校验和本身和KSM树算法无关。不使用校验也能找到相同的页面；校验和本身只是保持不稳定树的稳定，避免将频繁变化的页加入不稳定树中。即使我们不计算校验和，KSM合并算法仍然可以工作。
2 不稳定树的不稳定性
我们必须避免不共享的页面的写保护，我们同时要避免通过KSM对整个虚拟内存扫描使匿名页在大部分时间都是写保护，这将导致大量的写时复制导致系统不可用。稳定树只包含共享KSM页，因为页面是写保护的，页面内容不会改变。而不稳定树只包含非共享的匿名页面，仍然可以通过应用程序改写匿名页面，不稳定树的查找会产生问题，图1是不稳定树的一个例子，它是稳定的。然而，如果一个应用程序写入不稳定树中的页面索引的第一个字节，比如页插入稳定树时第一个字节是0x3，之后应用程序改变为0x07，如图2所示不稳定树可能变得不稳定，这时的查找可能产生错误。
为了避免不稳定和查找产生的错误，在每一次KSM扫描后，KSM清空不稳定树，这样新的不稳定树会在下次扫描时重建，这就避免了查找错误。
图1 KSM不稳定树
图2 KSM不稳定树的不稳定性
3 KSM页合并
用于页面合并的过程包含两个功能：page_wrprotect（）和replace_page（）。前者写保护所有页表映射的页面；后者合并两个页面并相应更新页表，然后释放已合并且没有页表映射的匿名页面。在page_wrprotect（）之后，通过memcmp（）确定两个页面内容完全相同，之后用replace_page合并页。
4 计算时间的复杂度
通常的x86架构（以及大多数的体系结构）是4096个字节。找到一个相等的页面成本，是将memcmp（）的成本乘以树的级数。得益于rbtree的特性，所有的计算时间的复杂度（包括插入/搜索/删除功能）是O（log（N）），其中N是扫描的KSM的页面总数。因此，即使在最糟糕的情况下：前4092个字节的所有页面是相等的，只有最后一个4个字节不同，KSM树算法性能也不会降低太多。当然在memcmp（）之前，如果引入hash算法，能够提高KSM树算法的性能，然而vmware公司的专利技术是不能回避的问题。
5 KSM改进PKSM/UKSM
5.1 对用户透明
自动添加全系统的用户进程的匿名页面到PKSM中，因此不在需要用户修改用户程序
5.2 高效的匿名内存页面检测
自动检测匿名页面的创建和释放，使用新的算法和机制来直接处理Linux内核创建/释放匿名页面。PKSM不再需要浪费大量的CPU来遍历所有的VMA区域来查找可用的匿名页面。
5.3 考虑内容全零页面
PKSM将全零内存块视作特殊的内存页面，并将他们合并到一个特殊的不能交换的pksm zero page。
5.4 周期性检查内存块的内容
PKSM将不稳定的匿名页面放入一个FIFO队列中，周期性地检查其这些匿名页面的校验值，如果发现内容发生变化，那麽这些页面会重新进行比较和合并。系统默认每20分钟检查完所有的不稳定的匿名页面。
参考文献：
[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