<!DOCTYPE html>
<html lang="en" data-content_root="../">
<head>
<meta charset="utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" /><meta name="viewport" content="width=device-width, initial-scale=1" />
<title>Kernel Samepage Merging — The Linux Kernel documentation</title>
<link rel="stylesheet" type="text/css" href="../_static/pygments.css?v=fa44fd50" />
<link rel="stylesheet" type="text/css" href="../_static/alabaster.css?v=3918102e" />
<script src="../_static/documentation_options.js?v=5929fcd5"></script>
<script src="../_static/doctools.js?v=9bcbadda"></script>
<script src="../_static/sphinx_highlight.js?v=dc90522c"></script>
<link rel="index" title="Index" href="../genindex.html" />
<link rel="search" title="Search" href="../search.html" />
<link rel="next" title="Physical Memory Model" href="memory-model.html" />
<link rel="prev" title="Hugetlbfs Reservation" href="hugetlbfs_reserv.html" />
<link rel="stylesheet" href="../_static/custom.css" type="text/css" />
</head><body>
<div class="document">
<div class="sphinxsidebar" role="navigation" aria-label="Main">
<div class="sphinxsidebarwrapper">
<p class="logo"><a href="../index.html">
<img class="logo" src="../_static/logo.svg" alt="Logo of The Linux Kernel"/>
</a></p>
<h1 class="logo"><a href="../index.html">The Linux Kernel</a></h1>
<p class="blurb">6.18.50</p>
<search id="searchbox" style="display: none" role="search">
<h3 id="searchlabel">Quick search</h3>
<div class="searchformwrapper">
<form class="search" action="../search.html" method="get">
<input type="text" name="q" aria-labelledby="searchlabel" autocomplete="off" autocorrect="off" autocapitalize="off" spellcheck="false"/>
<input type="submit" value="Go" />
</form>
</div>
</search>
<script>document.getElementById('searchbox').style.display = "block"</script>
<p>
<h3 class="kernel-toc-contents">Contents</h3>
<input type="checkbox" class="kernel-toc-toggle" id = "kernel-toc-toggle" checked>
<label class="kernel-toc-title" for="kernel-toc-toggle"></label>
<div class="kerneltoc" id="kerneltoc">
<ul>
<li class="toctree-l1"><a class="reference internal" href="../process/development-process.html">Development process</a></li>
<li class="toctree-l1"><a class="reference internal" href="../process/submitting-patches.html">Submitting patches</a></li>
<li class="toctree-l1"><a class="reference internal" href="../process/code-of-conduct.html">Code of conduct</a></li>
<li class="toctree-l1"><a class="reference internal" href="../maintainer/index.html">Maintainer handbook</a></li>
<li class="toctree-l1"><a class="reference internal" href="../process/index.html">All development-process docs</a></li>
</ul>
<ul class="current">
<li class="toctree-l1"><a class="reference internal" href="../core-api/index.html">Core API</a></li>
<li class="toctree-l1"><a class="reference internal" href="../driver-api/index.html">Driver APIs</a></li>
<li class="toctree-l1 current"><a class="reference internal" href="../subsystem-apis.html">Subsystems</a><ul class="current">
<li class="toctree-l2 current"><a class="reference internal" href="../subsystem-apis.html#core-subsystems">Core subsystems</a><ul class="current">
<li class="toctree-l3"><a class="reference internal" href="../core-api/index.html">Core API Documentation</a></li>
<li class="toctree-l3"><a class="reference internal" href="../driver-api/index.html">Driver implementer’s API guide</a></li>
<li class="toctree-l3 current"><a class="reference internal" href="index.html">Memory Management Documentation</a></li>
<li class="toctree-l3"><a class="reference internal" href="../power/index.html">Power Management</a></li>
<li class="toctree-l3"><a class="reference internal" href="../scheduler/index.html">Scheduler</a></li>
<li class="toctree-l3"><a class="reference internal" href="../timers/index.html">Timers</a></li>
<li class="toctree-l3"><a class="reference internal" href="../locking/index.html">Locking</a></li>
</ul>
</li>
<li class="toctree-l2"><a class="reference internal" href="../subsystem-apis.html#human-interfaces">Human interfaces</a></li>
<li class="toctree-l2"><a class="reference internal" href="../subsystem-apis.html#networking-interfaces">Networking interfaces</a></li>
<li class="toctree-l2"><a class="reference internal" href="../subsystem-apis.html#storage-interfaces">Storage interfaces</a></li>
<li class="toctree-l2"><a class="reference internal" href="../subsystem-apis.html#other-subsystems">Other subsystems</a></li>
</ul>
</li>
<li class="toctree-l1"><a class="reference internal" href="../locking/index.html">Locking</a></li>
</ul>
<ul>
<li class="toctree-l1"><a class="reference internal" href="../process/license-rules.html">Licensing rules</a></li>
<li class="toctree-l1"><a class="reference internal" href="../doc-guide/index.html">Writing documentation</a></li>
<li class="toctree-l1"><a class="reference internal" href="../dev-tools/index.html">Development tools</a></li>
<li class="toctree-l1"><a class="reference internal" href="../dev-tools/testing-overview.html">Testing guide</a></li>
<li class="toctree-l1"><a class="reference internal" href="../kernel-hacking/index.html">Hacking guide</a></li>
<li class="toctree-l1"><a class="reference internal" href="../trace/index.html">Tracing</a></li>
<li class="toctree-l1"><a class="reference internal" href="../fault-injection/index.html">Fault injection</a></li>
<li class="toctree-l1"><a class="reference internal" href="../livepatch/index.html">Livepatching</a></li>
<li class="toctree-l1"><a class="reference internal" href="../rust/index.html">Rust</a></li>
</ul>
<ul>
<li class="toctree-l1"><a class="reference internal" href="../admin-guide/index.html">Administration</a></li>
<li class="toctree-l1"><a class="reference internal" href="../kbuild/index.html">Build system</a></li>
<li class="toctree-l1"><a class="reference internal" href="../admin-guide/reporting-issues.html">Reporting issues</a></li>
<li class="toctree-l1"><a class="reference internal" href="../tools/index.html">Userspace tools</a></li>
<li class="toctree-l1"><a class="reference internal" href="../userspace-api/index.html">Userspace API</a></li>
</ul>
<ul>
<li class="toctree-l1"><a class="reference internal" href="../firmware-guide/index.html">Firmware</a></li>
<li class="toctree-l1"><a class="reference internal" href="../devicetree/index.html">Firmware and Devicetree</a></li>
</ul>
<ul>
<li class="toctree-l1"><a class="reference internal" href="../arch/index.html">CPU architectures</a></li>
</ul>
<ul>
<li class="toctree-l1"><a class="reference internal" href="../staging/index.html">Unsorted documentation</a></li>
</ul>
<ul>
<li class="toctree-l1"><a class="reference internal" href="../translations/index.html">Translations</a></li>
</ul>
</div>
<script type="text/javascript"> <!--
var sbar = document.getElementsByClassName("sphinxsidebar")[0];
let currents = document.getElementsByClassName("current")
if (currents.length) {
sbar.scrollTop = currents[currents.length - 1].offsetTop;
}
--> </script>
<div role="note" aria-label="source link">
<h3>This Page</h3>
<ul class="this-page-menu">
<li><a href="../_sources/mm/ksm.rst.txt"
rel="nofollow">Show Source</a></li>
</ul>
</div>
</div>
</div>
<div class="documentwrapper">
<div class="bodywrapper">
<div class="body" role="main">
<div class="language-selection">
English
<ul>
<li><a href="../translations/zh_CN/mm/ksm.html">Chinese (Simplified)</a></li>
</ul>
</div>
<section id="kernel-samepage-merging">
<h1>Kernel Samepage Merging<a class="headerlink" href="#kernel-samepage-merging" title="Link to this heading">¶</a></h1>
<p>KSM is a memory-saving de-duplication feature, enabled by CONFIG_KSM=y,
added to the Linux kernel in 2.6.32. See <code class="docutils literal notranslate"><span class="pre">mm/ksm.c</span></code> for its implementation,
and <a class="reference external" href="http://lwn.net/Articles/306704/">http://lwn.net/Articles/306704/</a> and <a class="reference external" href="https://lwn.net/Articles/330589/">https://lwn.net/Articles/330589/</a></p>
<p>The userspace interface of KSM is described in <a class="reference internal" href="../admin-guide/mm/ksm.html"><span class="doc">Kernel Samepage Merging</span></a></p>
<section id="design">
<h2>Design<a class="headerlink" href="#design" title="Link to this heading">¶</a></h2>
<section id="overview">
<h3>Overview<a class="headerlink" href="#overview" title="Link to this heading">¶</a></h3>
<p>A few notes about the KSM scanning process,
to make it easier to understand the data structures below:</p>
<p>In order to reduce excessive scanning, KSM sorts the memory pages by their
contents into a data structure that holds pointers to the pages’ locations.</p>
<p>Since the contents of the pages may change at any moment, KSM cannot just
insert the pages into a normal sorted tree and expect it to find anything.
Therefore KSM uses two data structures - the stable and the unstable tree.</p>
<p>The stable tree holds pointers to all the merged pages (ksm pages), sorted
by their contents. Because each such page is write-protected, searching on
this tree is fully assured to be working (except when pages are unmapped),
and therefore this tree is called the stable tree.</p>
<p>The stable tree node includes information required for reverse
mapping from a KSM page to virtual addresses that map this page.</p>
<p>In order to avoid large latencies of the rmap walks on KSM pages,
KSM maintains two types of nodes in the stable tree:</p>
<ul class="simple">
<li><p>the regular nodes that keep the reverse mapping structures in a
linked list</p></li>
<li><p>the “chains” that link nodes (“dups”) that represent the same
write protected memory content, but each “dup” corresponds to a
different KSM page copy of that content</p></li>
</ul>
<p>Internally, the regular nodes, “dups” and “chains” are represented
using the same <code class="xref c c-struct broken_xref docutils literal notranslate"><span class="pre">struct</span> <span class="pre">ksm_stable_node</span></code> structure.</p>
<p>In addition to the stable tree, KSM uses a second data structure called the
unstable tree: this tree holds pointers to pages which have been found to
be “unchanged for a period of time”. The unstable tree sorts these pages
by their contents, but since they are not write-protected, KSM cannot rely
upon the unstable tree to work correctly - the unstable tree is liable to
be corrupted as its contents are modified, and so it is called unstable.</p>
<p>KSM solves this problem by several techniques:</p>
<ol class="arabic simple">
<li><p>The unstable tree is flushed every time KSM completes scanning all
memory areas, and then the tree is rebuilt again from the beginning.</p></li>
<li><p>KSM will only insert into the unstable tree, pages whose hash value
has not changed since the previous scan of all memory areas.</p></li>
<li><p>The unstable tree is a RedBlack Tree - so its balancing is based on the
colors of the nodes and not on their contents, assuring that even when
the tree gets “corrupted” it won’t get out of balance, so scanning time
remains the same (also, searching and inserting nodes in an rbtree uses
the same algorithm, so we have no overhead when we flush and rebuild).</p></li>
<li><p>KSM never flushes the stable tree, which means that even if it were to
take 10 attempts to find a page in the unstable tree, once it is found,
it is secured in the stable tree. (When we scan a new page, we first
compare it against the stable tree, and then against the unstable tree.)</p></li>
</ol>
<p>If the merge_across_nodes tunable is unset, then KSM maintains multiple
stable trees and multiple unstable trees: one of each for each NUMA node.</p>
</section>
<section id="reverse-mapping">
<h3>Reverse mapping<a class="headerlink" href="#reverse-mapping" title="Link to this heading">¶</a></h3>
<p>KSM maintains reverse mapping information for KSM pages in the stable
tree.</p>
<p>If a KSM page is shared between less than <code class="docutils literal notranslate"><span class="pre">max_page_sharing</span></code> VMAs,
the node of the stable tree that represents such KSM page points to a
list of <code class="xref c c-struct broken_xref docutils literal notranslate"><span class="pre">struct</span> <span class="pre">ksm_rmap_item</span></code> and the <code class="docutils literal notranslate"><span class="pre">page->mapping</span></code> of the
KSM page points to the stable tree node.</p>
<p>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 <code class="docutils literal notranslate"><span class="pre">page->mapping</span></code> pointing to that “dup”.</p>
<p>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.</p>
<p>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.</p>
<p>The deduplication limit enforced by <code class="docutils literal notranslate"><span class="pre">max_page_sharing</span></code> is required
to avoid the virtual memory rmap lists to grow too large. The rmap
walk has O(N) complexity where N is the number of rmap_items
(i.e. virtual mappings) that are sharing the page, which is in turn
capped by <code class="docutils literal notranslate"><span class="pre">max_page_sharing</span></code>. So this effectively spreads the linear
O(N) computational complexity from rmap walk context over different
KSM pages. The ksmd walk over the stable_node “chains” is also O(N),
but N is the number of stable_node “dups”, not the number of
rmap_items, so it has not a significant impact on ksmd performance. In
practice the best stable_node “dup” candidate will be kept and found
at the head of the “dups” list.</p>
<p>High values of <code class="docutils literal notranslate"><span class="pre">max_page_sharing</span></code> result in faster memory merging
(because there will be fewer stable_node dups queued into the
stable_node chain->hlist to check for pruning) and higher
deduplication factor at the expense of slower worst case for rmap
walks for any KSM page which can happen during swapping, compaction,
NUMA balancing and page migration.</p>
<p>The <code class="docutils literal notranslate"><span class="pre">stable_node_dups/stable_node_chains</span></code> ratio is also affected by the
<code class="docutils literal notranslate"><span class="pre">max_page_sharing</span></code> tunable, and an high ratio may indicate fragmentation
in the stable_node dups, which could be solved by introducing
fragmentation algorithms in ksmd which would refile rmap_items from
one stable_node dup to another stable_node dup, in order to free up
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.</p>
<p>The whole list of stable_node “dups” linked in the stable_node
“chains” is scanned periodically in order to prune stale stable_nodes.
The frequency of such scans is defined by
<code class="docutils literal notranslate"><span class="pre">stable_node_chains_prune_millisecs</span></code> sysfs tunable.</p>
</section>
<section id="reference">
<h3>Reference<a class="headerlink" href="#reference" title="Link to this heading">¶</a></h3>
<dl class="c struct">
<dt class="sig sig-object c" id="c.ksm_scan">
<span class="k"><span class="pre">struct</span></span><span class="w"> </span><span class="sig-name descname"><span class="n"><span class="pre">ksm_scan</span></span></span><a class="headerlink" href="#c.ksm_scan" title="Link to this definition">¶</a><br /></dt>
<dd><p>cursor for scanning</p>
</dd></dl>
<div class="kernelindent docutils container">
<p><strong>Definition</strong>:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>struct ksm_scan {
struct ksm_mm_slot *mm_slot;
unsigned long address;
struct ksm_rmap_item **rmap_list;
unsigned long seqnr;
};
</pre></div>
</div>
<p><strong>Members</strong></p>
<dl class="simple">
<dt><code class="docutils literal notranslate"><span class="pre">mm_slot</span></code></dt><dd><p>the current mm_slot we are scanning</p>
</dd>
<dt><code class="docutils literal notranslate"><span class="pre">address</span></code></dt><dd><p>the next address inside that to be scanned</p>
</dd>
<dt><code class="docutils literal notranslate"><span class="pre">rmap_list</span></code></dt><dd><p>link to the next rmap to be scanned in the rmap_list</p>
</dd>
<dt><code class="docutils literal notranslate"><span class="pre">seqnr</span></code></dt><dd><p>count of completed full scans (needed when removing unstable node)</p>
</dd>
</dl>
</div>
<p><strong>Description</strong></p>
<p>There is only the one ksm_scan instance of this cursor structure.</p>
<p>--
Izik Eidus,
Hugh Dickins, 17 Nov 2009</p>
</section>
</section>
</section>
</div>
</div>
</div>
<div class="clearer"></div>
</div>
<div class="footer">
©The kernel development community.
|
Powered by <a href="https://www.sphinx-doc.org/">Sphinx 8.1.3</a>
& <a href="https://alabaster.readthedocs.io">Alabaster 0.7.16</a>
|
<a href="../_sources/mm/ksm.rst.txt"
rel="nofollow">Page source</a>
</div>
</body>
</html>