Kernel Samepage Merging（KSM）
KSM是一种节省内存的去重功能，通过CONFIG_KSM=y启用，添加到Linux内核中的2.6.32版本。有关其实现，请参阅mm/ksm.c，以及http://lwn.net/Articles/306704/和https://lwn.net/Articles/330589/。
KSM的用户空间接口在《Kernel Samepage Merging设计概述》中有描述。
设计
概述
以下是关于KSM扫描过程的一些说明，以便更容易理解下面的数据结构：
为了减少过多的扫描，KSM将内存页面按其内容排序，并将其存储在一个数据结构中，该数据结构保存了页面位置的指针。
由于页面的内容可能随时发生变化，KSM不能只是将页面插入到普通的排序树中并期望找到内容。因此，KSM使用两个数据结构 - 稳定树和不稳定树。
稳定树保存了所有合并页面（ksm页面）的指针，按其内容排序。由于每个这样的页面都是写保护的，因此在该树上进行搜索是完全可靠的（除非页面被取消映射），因此该树被称为稳定树。
稳定树节点包括从KSM页面到映射此页面的虚拟地址的反向映射所需的信息。
为了避免在KSM页面上进行rmap遍历时出现较大的延迟，KSM在稳定树中维护两种类型的节点：
- 保持反向映射结构的常规节点，存储在链表中
- 链接表示相同写保护内存内容的节点（"dups"），但每个"dups"对应于该内容的不同KSM页面副本的"chains"
在内部，常规节点、"dups"和"chains"使用相同的struct ksm_stable_node结构表示。
除了稳定树，KSM还使用了第二个数据结构，称为不稳定树：该树保存了被发现在一段时间内“未更改”的页面的指针。不稳定树按其内容排序，但由于它们没有写保护，KSM不能依赖不稳定树的正确工作 - 不稳定树可能会在其内容被修改时损坏，因此称为不稳定树。
KSM通过几种技术解决了这个问题：
- 每次KSM完成扫描所有内存区域后，都会刷新不稳定树，然后从头开始重新构建树。
- KSM只会将哈希值自上次扫描所有内存区域以来未更改的页面插入到不稳定树中。
- 不稳定树是红黑树 - 因此其平衡是基于节点的颜色而不是内容，确保即使树被“损坏”，它也不会失去平衡，因此扫描时间保持不变（此外，在rbtree中搜索和插入节点使用相同的算法，因此在刷新和重建时没有额外开销）。
- KSM从不刷新稳定树，这意味着即使在不稳定树中查找页面需要尝试10次，一旦找到，它就会被安全地放入稳定树中（当我们扫描新页面时，首先与稳定树进行比较，然后与不稳定树进行比较）。
如果未设置merge_across_nodes可调参数，则KSM为每个NUMA节点维护多个稳定树和多个不稳定树：每个NUMA节点对应一个稳定树和一个不稳定树。
反向映射
KSM在稳定树中维护KSM页面的反向映射信息。
如果KSM页面在少于max_page_sharing个VMA之间共享，则表示该KSM页面的稳定树节点指向一个struct ksm_rmap_item列表，而KSM页面的page->mapping指向稳定树节点。
当共享超过此阈值时，KSM在稳定树中添加了第二个维度。树节点变为一个“chain”，链接一个或多个“dup”。每个“dup”保留了指向该“dup”的KSM页面的反向映射信息。
每个“chain”和所有链接到“chain”的“dup”都强制执行相同写保护内存内容的不变性，即使每个“dup”将被不同的KSM页面副本指向。
这样，与无限制的反向映射列表相比，稳定树查找的计算复杂性不受影响。仍然强制执行稳定树本身不允许存在KSM页面内容重复的规则。
max_page_sharing强制执行的去重限制是为了避免虚拟内存rmap列表变得过大。rmap遍历的复杂度为O(N)，其中N是共享页面的rmap_items（即虚拟映射）的数量，而这又受到max_page_sharing的限制。因此，这将线性的O(N)计算复杂度从rmap遍历上下文中分散到不同的KSM页面上。ksmd对稳定节点“chains”的遍历也是O(N)，但N是稳定节点“dups”的数量，而不是rmap_items的数量，因此对ksmd性能没有显著影响。实际上，最佳的稳定节点“dup”候选项将保留并位于“dups”列表的开头。
较大的max_page_sharing值会导致更快的内存合并（因为稳定节点dups排队到稳定节点chain->hlist中的数量较少），以及更高的去重因子，但代价是在交换、压缩、NUMA平衡和页面迁移期间，rmap遍历的最坏情况速度较慢。
稳定节点dups/稳定节点chains的比率也受到max_page_sharing可调参数的影响，较高的比率可能表明稳定节点dups中存在碎片化，可以通过在ksmd中引入碎片化算法来将rmap_items从一个稳定节点dup重新分类到另一个稳定节点dup，以释放具有少量rmap_items的稳定节点“dups”，但这可能会增加ksmd的CPU使用率，并可能减慢应用程序的KSM页面上的只读计算。
稳定节点“dups”链表中的所有稳定节点“dups”定期进行扫描，以删除过时的稳定节点。此类扫描的频率由stable_node_chains_prune_millisecs sysfs可调参数定义。
参考
- struct ksm_scan
https://www.kernel.org/doc/html/v6.6/mm/ksm.html#c.ksm_scan