内核同页合并¶
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 在稳定树中维护两种类型的节点
常规节点，将反向映射结构保存在链表中
“链”，链接代表相同写保护内存内容的节点（“dups”），但每个“dup”对应于该内容的不同 KSM 页面副本
在内部，常规节点、“dups”和“链”使用相同的 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 会向稳定树添加第二个维度。树节点变成“链”，链接一个或多个“dups”。每个“dup”都保留一个 KSM 页面的反向映射信息，其中 page->mapping 指向该“dup”。
每个“链”和链接到“链”中的所有“dups”都强制执行以下不变量：它们表示相同的写保护内存内容，即使每个“dup”都由该内容的不同 KSM 页面副本指向。
这样，与无限制的反向映射列表相比，稳定树查找的计算复杂度不受影响。仍然强制执行稳定树本身中不能存在 KSM 页面内容重复项。
通过 max_page_sharing 强制执行的去重限制是必需的，以避免虚拟内存 rmap 列表增长过大。rmap 遍历具有 O(N) 的复杂度，其中 N 是共享该页面的 rmap_items（即虚拟映射）的数量，这又受限于 max_page_sharing。因此，这实际上将 rmap 遍历上下文的线性 O(N) 计算复杂度分散到不同的 KSM 页面上。ksmd 对 stable_node “链”的遍历也是 O(N)，但 N 是 stable_node “dups”的数量，而不是 rmap_items 的数量，因此对 ksmd 性能没有显着影响。在实践中，最佳的 stable_node “dup”候选者将被保留并在“dups”列表的头部找到。
max_page_sharing 的高值会导致更快的内存合并（因为将有更少的 stable_node dups 排队到 stable_node chain->hlist 中进行修剪）和更高的去重因子，但代价是对于任何 KSM 页面的 rmap 遍历，在交换、压缩、NUMA 平衡和页面迁移期间，最坏情况会变慢。
stable_node_dups/stable_node_chains 比率也受 max_page_sharing 可调参数的影响，高比率可能表明 stable_node dups 中的碎片化，这可以通过在 ksmd 中引入碎片化算法来解决，该算法会将 rmap_items 从一个 stable_node dup 重新归档到另一个 stable_node dup，以便释放其中 rmap_items 较少的 stable_node “dups”，但这可能会增加 ksmd 的 CPU 使用率，并可能减慢应用程序 KSM 页面的只读计算。
会定期扫描链接在 stable_node “链”中的整个 stable_node “dups”列表，以修剪过时的 stable_node。此类扫描的频率由 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 日