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