linux ksm实现与代码简述

本文主要是介绍linux ksm实现与代码简述，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

KSM 全称是 Kernel Samepage Merging，表示相同的物理页只映射一份拷贝。

原理

在ksm初始化时（ksm_init），注册了一个ksm_scan_thread线程，这个线程的核心入口是ksm_do_scan。当对一个进程第一次通过madvice(MADV_MERGEABLE)标记一段内存可合并时，会触发__ksm_enter将当前进程标记为MMF_VM_MERGEABLE，并把进程的mm_struct放在ksm_mm_head链表上。ksm_scan_thread会在ksm_mm_head链表上做扫描，找到标记合并的匿名页中，page内容的checksum不变的页（说明最近没有写入），如果是将找到的mergable 页合并到stable_tree 的 node上，将相应pte置为同一个物理地址。当有写操作时，会因为write_protected标记触发cow机制，生成新的页，并从stable tree里移除。

实现

ksm_scan_thread线程的核心是 ksm_do_scan，它会扫描所有进程（ksm_mm_head链表上的所有进程）的可合并 vma，找到checksum不变的页，如果stable tree没有，就添加到page所在numa 节点的unstable tree上，如果原本unstable tree上有，就一起移至stable tree（即引用超过２页的mergable 页才会移至stable tree中）。一轮扫描结束后，unstable tree会被清空，并在下轮扫描中重建。

每个numa 节点都有一个 stable tree和unstable tree。如果开启了ksm_merge_across_nodes，则所有numa node共用0号节点。

stable tree 是一个红黑树，当共享页的vma很多，超过ksm_max_page_sharing（256）个时，会将stable tree 的node 转为chain list node，每个chain list node 上最多存256个vma节点。它们指向同一个物理页。

unstable tree也是一个红黑树，一轮扫描结束后，unstable tree会被清空，并在下轮扫描中重建。

代码简述

ksm_do_scan主要由scan_get_next_rmap_item找可合并匿名页，由cmp_and_merge_page到对应numa节点找页尝试合并

scan_get_next_rmap_item

找mergable 的mapping了物理页的page。最终会连成一个链存在mm_struct->rmap_list上。

会顺带将不再mapping或设置unmergable的rmap_item删掉。

scan_get_next_rmap_item():// 新一轮扫描if (mm_slot == &ksm_mm_head) {/*** 新一轮扫描前首先触发一次lru_add_drain_all* 因为lru如果一直不刷新的话，有些无用的页会因为引用计数而不能做merge。*/lru_add_drain_all();/*** 如果一页做了迁移，在一轮结束时应该已经有对应节点加在了正确numa节点的stable tree上* 并增加了ref，可以安全地将ref减1了*/if (ksm_merge_across_nodes) {list_for_each_entry_safe(stable_node, next, &migrate_nodes, list) {page = get_ksm_page(stable_node, GET_KSM_PAGE_NOLOCK);if (page)put_page(page);cond_resched();}}}vma_iter_init(&vmi, mm, ksm_scan.address);for_each_vma(vmi, vma) {/*** 遍历一个进程所有mergeable anon vma中的有物理页的page，跳过device页，* 找到对应 address 的 rmap_item，或为它新创建一个rmap_item，* 上一次扫描到的ksm_scan.rmap_list 到它之间的所有item都* 不再mergable或没有物理页了，需要删除 rmap_item。* （这样一轮下来，整个进程的全部mergable的物理页的rmap,*   就全放在mm_struct->rmap_list上了）*/rmap_item = get_next_rmap_item(mm_slot, ksm_scan.rmap_list, ksm_scan.address);return rmap_item; // 找到了一个mergable匿名页}// 如果扫描一轮发现这个进程没有ksm页了，就删掉对应mm_slothash_del(&mm_slot->slot.hash);list_del(&mm_slot->slot.mm_node);

cmp_and_merge_page

如果目标页的ksm页大于等于２个，则能找目标页所在numa节点上的stable node，加入上去。

在还没找到时，会先把自己加在unstable tree对应numa节点上，等后面的ksm页发现自己，并与自己一同加到stable tree上。

如果一个numa节点的stable tree上的一个ksm页，有多个dup节点，它们会连成一个chain，在stable_tree_search->chain_prune时会优先找到映射最多page结构的dup节点，与它合并。

搜索可合并stable node过程中会顺带发现不属于当前numa 节点的ksm页，从树上删除，并在之后整一轮扫描结束时，将ref减１。

cmp_and_merge_page():stable_node = page_stable_node(page);if (stable_node) {如果不支持ksm迁移，且物理页做了 numa node 迁移。则把 stable node 迁移至migrate_nodes上。否则它已经在 stable 树上了，直接返回}// 找出一个 ksm 页kpage = stable_tree_search();// 如果有这样的 ksm 页，则将此页的pte映射到ksm页上去。并插入 stable tree。if (kpage) {try_to_merge_with_ksm_page();stable_tree_append(rmap_item, page_stable_node(kpage));}// 还没有这样的 ksm 页，计算 checksum ，看是不是与上次一样，一样则认为没有修改calc_checksum(page);// 如果checksum变了, 它可能被频繁修改，不对这样的页做合并if (rmap_item->oldchecksum != checksum) {rmap_item->oldchecksum = checksum;return;}// 如果checksum是０页，则与0页合并（0页是刚初始化的页）try_to_merge_one_page(vma, page, ZERO_PAGE(rmap_item->address));// 尝试从本轮的对应 numa 节点的 unstable tree 上找有没有出现过相同内容页,// 没有则插入 unstable treeunstable_tree_search_insert()// 如果unstable tree有，说明有两个同样内容的页内容一直没变，可以合并到 stable treetry_to_merge_two_pages()stable_tree_append(tree_rmap_item, stable_node);stable_tree_append(rmap_item, stable_node);// 如果两个相同内容页出现在同一个 compound page 上// 则只是拆分复合页，先不合并ksm，因为需要重新拿锁，可以等到下一轮split_huge_page();

stable_tree_search

搜索过程中，如果自己的page已经是migrate stable node了，就可以找个树上的节点替换，并返回自己。

在stable tree搜索过程中，会顺便发现物理页已经迁移了的node，并将其从树上移除。

stable_tree_search():// 如果页对应的stable node存在，则前面的cmp_and_merge_page// 保证了它在migrate_nodes上page_node = page_stable_node(page);// 在对应numa节点的红黑树查找nid = get_kpfn_nid(page_to_pfn(page));root = root_stable_tree + nid;new = &root->rb_node;while (*new) /* 一层层找到叶子节点 */{// 红黑树的节点可能是一个dup节点，如果vma超过了256，节点会组成dup链chain// 如果超过一定时间，则红黑树上chain节点的dup链，看是否只有一个dup节了。// 如果是，则用dup节点代替红黑树上的chain节点。// 这同时，会尝试把最多vma的dup节点放在chain的头上，作为下次合并首选dupchain_prune();// 比较页的内容，从而在红黑树上向下找ret = memcmp_pages(page, tree_page);// 如果目标页有stable node节点，且是一个物理页迁移了的 stable 节点if (page_node) {// 修改它的nid为它迁移到的numa节点id，并加回 stable tree //（mapcount > 1 时，以dup形式加到node chain上，等于1时走if后的逻辑加到dup上）DO_NUMA(page_node->nid = nid);stable_node_chain_add_dup(page_node, stable_node)}// chain_prune已经取了最多map页的dup节点// 这里判断下如果numa id不变，说明没有迁移过，可直接返回tree_page = get_ksm_page(stable_node_dup);if (get_kpfn_nid(stable_node_dup->kpfn) == NUMA(stable_node_dup->nid)) {return tree_page;}/*** 如果numa id 变过，则刚好发现了一个 numa 节点迁移了的 node* 可顺便将其从树上删除。并尝试将原page的stable migrate node 加回树上* （调用它的 cmp_and_merge_page 保证了如果page有stable node对应，则一定是migrate node）*/if (dup节点在红黑树上的chain上) {// 可直接将原节点删掉__stable_node_dup_del(stable_node_dup);if (page没有对应stable node migrate 节点))return null;// 如果page有节点，就把page改numa id后加到chain上去DO_NUMA(page_node->nid = nid);stable_node_chain_add_dup(page_node, stable_node);return page;} else /* dup 节点直接在红黑树上 */{if (page有对应stable node migrate 节点) {// 直接交换，并返回原页（因为它已经在树上了）rb_replace_node(&stable_node_dup->node, &page_node->node, root);return page;} else /* page 没有 stable node节点对应 */ {// 移除原节点，返回null（因为它没在树上了）rb_erase(&stable_node_dup->node, root);return null;}}}