内核同页合并¶
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 日