<!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>Reference-count design for elements of lists/arrays protected by RCU — 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="RCU Torture Test Operation" href="torture.html" />
<link rel="prev" title="Using RCU hlist_nulls to protect list and objects" href="rculist_nulls.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 current"><a class="reference internal" href="../core-api/index.html">Core API</a><ul class="current">
<li class="toctree-l2"><a class="reference internal" href="../core-api/index.html#core-utilities">Core utilities</a></li>
<li class="toctree-l2"><a class="reference internal" href="../core-api/index.html#data-structures-and-low-level-utilities">Data structures and low-level utilities</a></li>
<li class="toctree-l2"><a class="reference internal" href="../core-api/index.html#low-level-entry-and-exit">Low level entry and exit</a></li>
<li class="toctree-l2 current"><a class="reference internal" href="../core-api/index.html#concurrency-primitives">Concurrency primitives</a><ul class="current">
<li class="toctree-l3"><a class="reference internal" href="../core-api/refcount-vs-atomic.html">refcount_t API compared to atomic_t</a></li>
<li class="toctree-l3"><a class="reference internal" href="../core-api/irq/index.html">IRQs</a></li>
<li class="toctree-l3"><a class="reference internal" href="../core-api/local_ops.html">Semantics and Behavior of Local Atomic Operations</a></li>
<li class="toctree-l3"><a class="reference internal" href="../core-api/padata.html">The padata parallel execution mechanism</a></li>
<li class="toctree-l3 current"><a class="reference internal" href="index.html">RCU Handbook</a></li>
<li class="toctree-l3"><a class="reference internal" href="../core-api/wrappers/memory-barriers.html">Linux kernel memory barriers</a></li>
</ul>
</li>
<li class="toctree-l2"><a class="reference internal" href="../core-api/index.html#low-level-hardware-management">Low-level hardware management</a></li>
<li class="toctree-l2"><a class="reference internal" href="../core-api/index.html#memory-management">Memory management</a></li>
<li class="toctree-l2"><a class="reference internal" href="../core-api/index.html#interfaces-for-kernel-debugging">Interfaces for kernel debugging</a></li>
<li class="toctree-l2"><a class="reference internal" href="../core-api/index.html#everything-else">Everything else</a></li>
</ul>
</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 current"><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"><a class="reference internal" href="../mm/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/RCU/rcuref.rst.txt"
rel="nofollow">Show Source</a></li>
</ul>
</div>
</div>
</div>
<div class="documentwrapper">
<div class="bodywrapper">
<div class="body" role="main">
<section id="reference-count-design-for-elements-of-lists-arrays-protected-by-rcu">
<h1>Reference-count design for elements of lists/arrays protected by RCU<a class="headerlink" href="#reference-count-design-for-elements-of-lists-arrays-protected-by-rcu" title="Link to this heading">¶</a></h1>
<p>Please note that the percpu-ref feature is likely your first
stop if you need to combine reference counts and RCU. Please see
include/linux/percpu-refcount.h for more information. However, in
those unusual cases where percpu-ref would consume too much memory,
please read on.</p>
<hr class="docutils" />
<p>Reference counting on elements of lists which are protected by traditional
reader/writer spinlocks or semaphores are straightforward:</p>
<p>CODE LISTING A:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>1. 2.
add() search_and_reference()
{ {
alloc_object read_lock(&list_lock);
... search_for_element
atomic_set(&el->rc, 1); atomic_inc(&el->rc);
write_lock(&list_lock); ...
add_element read_unlock(&list_lock);
... ...
write_unlock(&list_lock); }
}
3. 4.
release_referenced() delete()
{ {
... write_lock(&list_lock);
if(atomic_dec_and_test(&el->rc)) ...
kfree(el);
... remove_element
} write_unlock(&list_lock);
...
if (atomic_dec_and_test(&el->rc))
kfree(el);
...
}
</pre></div>
</div>
<p>If this list/array is made lock free using RCU as in changing the
<code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">write_lock()</span></code> in <code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">add()</span></code> and <code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">delete()</span></code> to <code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">spin_lock()</span></code> and changing <code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">read_lock()</span></code>
in <code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">search_and_reference()</span></code> to <a class="reference internal" href="../core-api/kernel-api.html#c.rcu_read_lock" title="rcu_read_lock"><code class="xref c c-func docutils literal notranslate"><span class="pre">rcu_read_lock()</span></code></a>, the <a class="reference internal" href="../driver-api/basics.html#c.atomic_inc" title="atomic_inc"><code class="xref c c-func docutils literal notranslate"><span class="pre">atomic_inc()</span></code></a> in
<code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">search_and_reference()</span></code> could potentially hold reference to an element which
has already been deleted from the list/array. Use <a class="reference internal" href="../driver-api/basics.html#c.atomic_inc_not_zero" title="atomic_inc_not_zero"><code class="xref c c-func docutils literal notranslate"><span class="pre">atomic_inc_not_zero()</span></code></a>
in this scenario as follows:</p>
<p>CODE LISTING B:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>1. 2.
add() search_and_reference()
{ {
alloc_object rcu_read_lock();
... search_for_element
atomic_set(&el->rc, 1); if (!atomic_inc_not_zero(&el->rc)) {
spin_lock(&list_lock); rcu_read_unlock();
return FAIL;
add_element }
... ...
spin_unlock(&list_lock); rcu_read_unlock();
} }
3. 4.
release_referenced() delete()
{ {
... spin_lock(&list_lock);
if (atomic_dec_and_test(&el->rc)) ...
call_rcu(&el->head, el_free); remove_element
... spin_unlock(&list_lock);
} ...
if (atomic_dec_and_test(&el->rc))
call_rcu(&el->head, el_free);
...
}
</pre></div>
</div>
<p>Sometimes, a reference to the element needs to be obtained in the
update (write) stream. In such cases, <a class="reference internal" href="../driver-api/basics.html#c.atomic_inc_not_zero" title="atomic_inc_not_zero"><code class="xref c c-func docutils literal notranslate"><span class="pre">atomic_inc_not_zero()</span></code></a> might be
overkill, since we hold the update-side spinlock. One might instead
use <a class="reference internal" href="../driver-api/basics.html#c.atomic_inc" title="atomic_inc"><code class="xref c c-func docutils literal notranslate"><span class="pre">atomic_inc()</span></code></a> in such cases.</p>
<p>It is not always convenient to deal with “FAIL” in the
<code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">search_and_reference()</span></code> code path. In such cases, the
<a class="reference internal" href="../driver-api/basics.html#c.atomic_dec_and_test" title="atomic_dec_and_test"><code class="xref c c-func docutils literal notranslate"><span class="pre">atomic_dec_and_test()</span></code></a> may be moved from <code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">delete()</span></code> to <code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">el_free()</span></code>
as follows:</p>
<p>CODE LISTING C:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>1. 2.
add() search_and_reference()
{ {
alloc_object rcu_read_lock();
... search_for_element
atomic_set(&el->rc, 1); atomic_inc(&el->rc);
spin_lock(&list_lock); ...
add_element rcu_read_unlock();
... }
spin_unlock(&list_lock); 4.
} delete()
3. {
release_referenced() spin_lock(&list_lock);
{ ...
... remove_element
if (atomic_dec_and_test(&el->rc)) spin_unlock(&list_lock);
kfree(el); ...
... call_rcu(&el->head, el_free);
} ...
5. }
void el_free(struct rcu_head *rhp)
{
release_referenced();
}
</pre></div>
</div>
<p>The key point is that the initial reference added by <code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">add()</span></code> is not removed
until after a grace period has elapsed following removal. This means that
<code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">search_and_reference()</span></code> cannot find this element, which means that the value
of el->rc cannot increase. Thus, once it reaches zero, there are no
readers that can or ever will be able to reference the element. The
element can therefore safely be freed. This in turn guarantees that if
any reader finds the element, that reader may safely acquire a reference
without checking the value of the reference counter.</p>
<p>A clear advantage of the RCU-based pattern in listing C over the one
in listing B is that any call to <code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">search_and_reference()</span></code> that locates
a given object will succeed in obtaining a reference to that object,
even given a concurrent invocation of <code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">delete()</span></code> for that same object.
Similarly, a clear advantage of both listings B and C over listing A is
that a call to <code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">delete()</span></code> is not delayed even if there are an arbitrarily
large number of calls to <code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">search_and_reference()</span></code> searching for the same
object that <code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">delete()</span></code> was invoked on. Instead, all that is delayed is
the eventual invocation of <a class="reference internal" href="../core-api/mm-api.html#c.kfree" title="kfree"><code class="xref c c-func docutils literal notranslate"><span class="pre">kfree()</span></code></a>, which is usually not a problem on
modern computer systems, even the small ones.</p>
<p>In cases where <code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">delete()</span></code> can sleep, <a class="reference internal" href="../core-api/kernel-api.html#c.synchronize_rcu" title="synchronize_rcu"><code class="xref c c-func docutils literal notranslate"><span class="pre">synchronize_rcu()</span></code></a> can be called from
<code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">delete()</span></code>, so that <code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">el_free()</span></code> can be subsumed into delete as follows:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>4.
delete()
{
spin_lock(&list_lock);
...
remove_element
spin_unlock(&list_lock);
...
synchronize_rcu();
if (atomic_dec_and_test(&el->rc))
kfree(el);
...
}
</pre></div>
</div>
<p>As additional examples in the kernel, the pattern in listing C is used by
reference counting of <code class="xref c c-struct broken_xref docutils literal notranslate"><span class="pre">struct</span> <span class="pre">pid</span></code>, while the pattern in listing B is used by
<code class="xref c c-struct broken_xref docutils literal notranslate"><span class="pre">struct</span> <span class="pre">posix_acl</span></code>.</p>
</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/RCU/rcuref.rst.txt"
rel="nofollow">Page source</a>
</div>
</body>
</html>