KSM （Kernel Samepage Merging）

内核合并页，目的是为了把内容完全相同的页面合并，从而释放内存供其他应用使用。Linux对虚拟机的支持，增加了相同页面的数量，所以KSM存在的合理性也就越来越大了，KSM页面在struct page中的page->mapping中标识，并且KSM页面一定也是一个匿名页。

#define PAGE_MAPPING_ANON    1
#define PAGE_MAPPING_KSM    2
#define PAGE_MAPPING_FLAGS    (PAGE_MAPPING_ANON | PAGE_MAPPING_KSM)

内核提供了如下几个辅助函数来判断page类型：

static inline int PageAnon(struct page *page)
{
    return ((unsigned long)page->mapping & PAGE_MAPPING_ANON) != 0;
}

static inline int PageKsm(struct page *page)
{
    return ((unsigned long)page->mapping & PAGE_MAPPING_FLAGS) ==
                (PAGE_MAPPING_ANON | PAGE_MAPPING_KSM);
}

由上面的辅助函数来说，KSM page必须是一个ANON类型，也就是必须是一个匿名页面。我们知道，通过反向映射，内核可以知道每个物理页page所对应的所有内存页表项，KSM页面必须也要是一个匿名页面。

实现方法

内核中实现了ksmd线程用来处理ksm页面，该线程会定期执行页面扫描，识别并且合并相同的页面，合并后的页面是被多个进程共享的，并且利用内核的写时复制（COW）机制，当某个进程要修改该页面时，再拷贝一份出来进行修改。KSM可以扫描系统中的匿名页面，并且判断哪些页面内容是相同的，然后把他们合并，并释放一份内存，但这将浪费很多CPU 和内存资源，因此内核实现了一个系统调用madvise，这样KSM的实现就需要应用层去设置了，应用程序利用此系统调用可以配置该进程的可合并区域，这样内核会记录此区域，后面在扫描时就只取这些“可合并”区域的页面进行操作了。

KSM使用两个树来管理合并页面，分别是stable tree和unstable tree。当处理一个“待合并”页面时，会先从stable tree中扫描，如果发现存在有相同的页面，那么标记该页的ref count，那么就把待合并页面释放做他用；如果stable tree中扫描发现不存在与之相同的页面，则转向unstable tree去搜索。在unstable tree搜索开始前，先判断下当前页面是否有修改，如果有修改则放弃继续搜索，如果没有修改，则真正开机搜索。当搜索unstable tree中发现有相同页，那么把该页移动到stable页，并且释放其中一个副本页，如果unstable tree中不存在相同页，则把该页放入unstable tree中。