summaryrefslogtreecommitdiff
path: root/Documentation/vm
diff options
context:
space:
mode:
authorMike Rapoport <rppt@linux.vnet.ibm.com>2018-04-24 09:40:24 +0300
committerJonathan Corbet <corbet@lwn.net>2018-04-27 17:19:33 -0600
commit064fca37bc0545fec0b5abdf9ce09136b73d7083 (patch)
tree3f735385d4b18c3ea3e90ab4cc6987a58fe3cec0 /Documentation/vm
parentdb12c00f13488ecf3eaa1842e845d34f6dc1a5c5 (diff)
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 <rppt@linux.vnet.ibm.com> Signed-off-by: Jonathan Corbet <corbet@lwn.net>
Diffstat (limited to 'Documentation/vm')
-rw-r--r--Documentation/vm/ksm.rst39
1 files changed, 39 insertions, 0 deletions
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