1ee65728eSMike Rapoport======================= 2ee65728eSMike RapoportKernel Samepage Merging 3ee65728eSMike Rapoport======================= 4ee65728eSMike Rapoport 5ee65728eSMike RapoportKSM is a memory-saving de-duplication feature, enabled by CONFIG_KSM=y, 6ee65728eSMike Rapoportadded to the Linux kernel in 2.6.32. See ``mm/ksm.c`` for its implementation, 7ee65728eSMike Rapoportand http://lwn.net/Articles/306704/ and https://lwn.net/Articles/330589/ 8ee65728eSMike Rapoport 9*ee865889SMike Rapoport (IBM)The userspace interface of KSM is described in Documentation/admin-guide/mm/ksm.rst 10ee65728eSMike Rapoport 11ee65728eSMike RapoportDesign 12ee65728eSMike Rapoport====== 13ee65728eSMike Rapoport 14ee65728eSMike RapoportOverview 15ee65728eSMike Rapoport-------- 16ee65728eSMike Rapoport 17ee65728eSMike Rapoport.. kernel-doc:: mm/ksm.c 18ee65728eSMike Rapoport :DOC: Overview 19ee65728eSMike Rapoport 20ee65728eSMike RapoportReverse mapping 21ee65728eSMike Rapoport--------------- 22ee65728eSMike RapoportKSM maintains reverse mapping information for KSM pages in the stable 23ee65728eSMike Rapoporttree. 24ee65728eSMike Rapoport 25ee65728eSMike RapoportIf a KSM page is shared between less than ``max_page_sharing`` VMAs, 26ee65728eSMike Rapoportthe node of the stable tree that represents such KSM page points to a 2721fbd591SQi Zhenglist of struct ksm_rmap_item and the ``page->mapping`` of the 28ee65728eSMike RapoportKSM page points to the stable tree node. 29ee65728eSMike Rapoport 30ee65728eSMike RapoportWhen the sharing passes this threshold, KSM adds a second dimension to 31ee65728eSMike Rapoportthe stable tree. The tree node becomes a "chain" that links one or 32ee65728eSMike Rapoportmore "dups". Each "dup" keeps reverse mapping information for a KSM 33ee65728eSMike Rapoportpage with ``page->mapping`` pointing to that "dup". 34ee65728eSMike Rapoport 35ee65728eSMike RapoportEvery "chain" and all "dups" linked into a "chain" enforce the 36ee65728eSMike Rapoportinvariant that they represent the same write protected memory content, 37ee65728eSMike Rapoporteven if each "dup" will be pointed by a different KSM page copy of 38ee65728eSMike Rapoportthat content. 39ee65728eSMike Rapoport 40ee65728eSMike RapoportThis way the stable tree lookup computational complexity is unaffected 41ee65728eSMike Rapoportif compared to an unlimited list of reverse mappings. It is still 42ee65728eSMike Rapoportenforced that there cannot be KSM page content duplicates in the 43ee65728eSMike Rapoportstable tree itself. 44ee65728eSMike Rapoport 45ee65728eSMike RapoportThe deduplication limit enforced by ``max_page_sharing`` is required 46ee65728eSMike Rapoportto avoid the virtual memory rmap lists to grow too large. The rmap 47ee65728eSMike Rapoportwalk has O(N) complexity where N is the number of rmap_items 48ee65728eSMike Rapoport(i.e. virtual mappings) that are sharing the page, which is in turn 49ee65728eSMike Rapoportcapped by ``max_page_sharing``. So this effectively spreads the linear 50ee65728eSMike RapoportO(N) computational complexity from rmap walk context over different 51ee65728eSMike RapoportKSM pages. The ksmd walk over the stable_node "chains" is also O(N), 52ee65728eSMike Rapoportbut N is the number of stable_node "dups", not the number of 53ee65728eSMike Rapoportrmap_items, so it has not a significant impact on ksmd performance. In 54ee65728eSMike Rapoportpractice the best stable_node "dup" candidate will be kept and found 55ee65728eSMike Rapoportat the head of the "dups" list. 56ee65728eSMike Rapoport 57ee65728eSMike RapoportHigh values of ``max_page_sharing`` result in faster memory merging 58ee65728eSMike Rapoport(because there will be fewer stable_node dups queued into the 59ee65728eSMike Rapoportstable_node chain->hlist to check for pruning) and higher 60ee65728eSMike Rapoportdeduplication factor at the expense of slower worst case for rmap 61ee65728eSMike Rapoportwalks for any KSM page which can happen during swapping, compaction, 62ee65728eSMike RapoportNUMA balancing and page migration. 63ee65728eSMike Rapoport 64ee65728eSMike RapoportThe ``stable_node_dups/stable_node_chains`` ratio is also affected by the 65ee65728eSMike Rapoport``max_page_sharing`` tunable, and an high ratio may indicate fragmentation 66ee65728eSMike Rapoportin the stable_node dups, which could be solved by introducing 67ee65728eSMike Rapoportfragmentation algorithms in ksmd which would refile rmap_items from 68ee65728eSMike Rapoportone stable_node dup to another stable_node dup, in order to free up 69ee65728eSMike Rapoportstable_node "dups" with few rmap_items in them, but that may increase 70ee65728eSMike Rapoportthe ksmd CPU usage and possibly slowdown the readonly computations on 71ee65728eSMike Rapoportthe KSM pages of the applications. 72ee65728eSMike Rapoport 73ee65728eSMike RapoportThe whole list of stable_node "dups" linked in the stable_node 74ee65728eSMike Rapoport"chains" is scanned periodically in order to prune stale stable_nodes. 75ee65728eSMike RapoportThe frequency of such scans is defined by 76ee65728eSMike Rapoport``stable_node_chains_prune_millisecs`` sysfs tunable. 77ee65728eSMike Rapoport 78ee65728eSMike RapoportReference 79ee65728eSMike Rapoport--------- 80ee65728eSMike Rapoport.. kernel-doc:: mm/ksm.c 81ee65728eSMike Rapoport :functions: mm_slot ksm_scan stable_node rmap_item 82ee65728eSMike Rapoport 83ee65728eSMike Rapoport-- 84ee65728eSMike RapoportIzik Eidus, 85ee65728eSMike RapoportHugh Dickins, 17 Nov 2009 86