From 064fca37bc0545fec0b5abdf9ce09136b73d7083 Mon Sep 17 00:00:00 2001 From: Mike Rapoport Date: Tue, 24 Apr 2018 09:40:24 +0300 Subject: docs/vm: ksm: add "Design" section Include the KSM description from the source code comment, add a subsection about reverse mapping and include kernel-doc references for KSM data structures. Signed-off-by: Mike Rapoport Signed-off-by: Jonathan Corbet --- Documentation/vm/ksm.rst | 39 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 39 insertions(+) (limited to 'Documentation/vm') diff --git a/Documentation/vm/ksm.rst b/Documentation/vm/ksm.rst index 786d460a0e46..0e5a085694e5 100644 --- a/Documentation/vm/ksm.rst +++ b/Documentation/vm/ksm.rst @@ -206,6 +206,45 @@ stable_node "dups" with few rmap_items in them, but that may increase the ksmd CPU usage and possibly slowdown the readonly computations on the KSM pages of the applications. +Design +====== + +Overview +-------- + +.. kernel-doc:: mm/ksm.c + :DOC: Overview + +Reverse mapping +--------------- +KSM maintains reverse mapping information for KSM pages in the stable +tree. + +If a KSM page is shared between less than ``max_page_sharing`` VMAs, +the node of the stable tree that represents such KSM page points to a +list of :c:type:`struct rmap_item` and the ``page->mapping`` of the +KSM page points to the stable tree node. + +When the sharing passes this threshold, KSM adds a second dimension to +the stable tree. The tree node becomes a "chain" that links one or +more "dups". Each "dup" keeps reverse mapping information for a KSM +page with ``page->mapping`` pointing to that "dup". + +Every "chain" and all "dups" linked into a "chain" enforce the +invariant that they represent the same write protected memory content, +even if each "dup" will be pointed by a different KSM page copy of +that content. + +This way the stable tree lookup computational complexity is unaffected +if compared to an unlimited list of reverse mappings. It is still +enforced that there cannot be KSM page content duplicates in the +stable tree itself. + +Reference +--------- +.. kernel-doc:: mm/ksm.c + :functions: mm_slot ksm_scan stable_node rmap_item + -- Izik Eidus, Hugh Dickins, 17 Nov 2009 -- cgit v1.2.3