<!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>What is RCU? -- “Read, Copy, Update” — 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 Concepts" href="rcu.html" />
<link rel="prev" title="PROPER CARE AND FEEDING OF RETURN VALUES FROM rcu_dereference()" href="rcu_dereference.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/whatisRCU.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="what-is-rcu-read-copy-update">
<span id="whatisrcu-doc"></span><h1>What is RCU? -- “Read, Copy, Update”<a class="headerlink" href="#what-is-rcu-read-copy-update" title="Link to this heading">¶</a></h1>
<p>Please note that the “What is RCU?” LWN series is an excellent place
to start learning about RCU:</p>
<div class="line-block">
<div class="line">1. What is RCU, Fundamentally? <a class="reference external" href="https://lwn.net/Articles/262464/">https://lwn.net/Articles/262464/</a></div>
<div class="line">2. What is RCU? Part 2: Usage <a class="reference external" href="https://lwn.net/Articles/263130/">https://lwn.net/Articles/263130/</a></div>
<div class="line">3. RCU part 3: the RCU API <a class="reference external" href="https://lwn.net/Articles/264090/">https://lwn.net/Articles/264090/</a></div>
<div class="line">4. The RCU API, 2010 Edition <a class="reference external" href="https://lwn.net/Articles/418853/">https://lwn.net/Articles/418853/</a></div>
<div class="line-block">
<div class="line">2010 Big API Table <a class="reference external" href="https://lwn.net/Articles/419086/">https://lwn.net/Articles/419086/</a></div>
</div>
<div class="line">5. The RCU API, 2014 Edition <a class="reference external" href="https://lwn.net/Articles/609904/">https://lwn.net/Articles/609904/</a></div>
<div class="line-block">
<div class="line">2014 Big API Table <a class="reference external" href="https://lwn.net/Articles/609973/">https://lwn.net/Articles/609973/</a></div>
</div>
<div class="line">6. The RCU API, 2019 Edition <a class="reference external" href="https://lwn.net/Articles/777036/">https://lwn.net/Articles/777036/</a></div>
<div class="line-block">
<div class="line">2019 Big API Table <a class="reference external" href="https://lwn.net/Articles/777165/">https://lwn.net/Articles/777165/</a></div>
</div>
<div class="line">7. The RCU API, 2024 Edition <a class="reference external" href="https://lwn.net/Articles/988638/">https://lwn.net/Articles/988638/</a></div>
<div class="line-block">
<div class="line">2024 Background Information <a class="reference external" href="https://lwn.net/Articles/988641/">https://lwn.net/Articles/988641/</a></div>
<div class="line">2024 Big API Table <a class="reference external" href="https://lwn.net/Articles/988666/">https://lwn.net/Articles/988666/</a></div>
</div>
</div>
<p>For those preferring video:</p>
<div class="line-block">
<div class="line">1. Unraveling RCU Mysteries: Fundamentals <a class="reference external" href="https://www.linuxfoundation.org/webinars/unraveling-rcu-usage-mysteries">https://www.linuxfoundation.org/webinars/unraveling-rcu-usage-mysteries</a></div>
<div class="line">2. Unraveling RCU Mysteries: Additional Use Cases <a class="reference external" href="https://www.linuxfoundation.org/webinars/unraveling-rcu-usage-mysteries-additional-use-cases">https://www.linuxfoundation.org/webinars/unraveling-rcu-usage-mysteries-additional-use-cases</a></div>
</div>
<p>What is RCU?</p>
<p>RCU is a synchronization mechanism that was added to the Linux kernel
during the 2.5 development effort that is optimized for read-mostly
situations. Although RCU is actually quite simple, making effective use
of it requires you to think differently about your code. Another part
of the problem is the mistaken assumption that there is “one true way” to
describe and to use RCU. Instead, the experience has been that different
people must take different paths to arrive at an understanding of RCU,
depending on their experiences and use cases. This document provides
several different paths, as follows:</p>
<p><a class="reference internal" href="#whatisrcu"><span class="std std-ref">1. RCU OVERVIEW</span></a></p>
<p><a class="reference internal" href="#id1"><span class="std std-ref">2. WHAT IS RCU’S CORE API?</span></a></p>
<p><a class="reference internal" href="#id6"><span class="std std-ref">3. WHAT ARE SOME EXAMPLE USES OF CORE RCU API?</span></a></p>
<p><a class="reference internal" href="#id7"><span class="std std-ref">4. WHAT IF MY UPDATING THREAD CANNOT BLOCK?</span></a></p>
<p><a class="reference internal" href="#id8"><span class="std std-ref">5. WHAT ARE SOME SIMPLE IMPLEMENTATIONS OF RCU?</span></a></p>
<p><a class="reference internal" href="#id9"><span class="std std-ref">6. ANALOGY WITH READER-WRITER LOCKING</span></a></p>
<p><a class="reference internal" href="#id10"><span class="std std-ref">7. ANALOGY WITH REFERENCE COUNTING</span></a></p>
<p><a class="reference internal" href="#id11"><span class="std std-ref">8. FULL LIST OF RCU APIs</span></a></p>
<p><a class="reference internal" href="#id12"><span class="std std-ref">9. ANSWERS TO QUICK QUIZZES</span></a></p>
<p>People who prefer starting with a conceptual overview should focus on
Section 1, though most readers will profit by reading this section at
some point. People who prefer to start with an API that they can then
experiment with should focus on Section 2. People who prefer to start
with example uses should focus on Sections 3 and 4. People who need to
understand the RCU implementation should focus on Section 5, then dive
into the kernel source code. People who reason best by analogy should
focus on Section 6 and 7. Section 8 serves as an index to the docbook
API documentation, and Section 9 is the traditional answer key.</p>
<p>So, start with the section that makes the most sense to you and your
preferred method of learning. If you need to know everything about
everything, feel free to read the whole thing -- but if you are really
that type of person, you have perused the source code and will therefore
never need this document anyway. ;-)</p>
<section id="rcu-overview">
<span id="whatisrcu"></span><h2>1. RCU OVERVIEW<a class="headerlink" href="#rcu-overview" title="Link to this heading">¶</a></h2>
<p>The basic idea behind RCU is to split updates into “removal” and
“reclamation” phases. The removal phase removes references to data items
within a data structure (possibly by replacing them with references to
new versions of these data items), and can run concurrently with readers.
The reason that it is safe to run the removal phase concurrently with
readers is the semantics of modern CPUs guarantee that readers will see
either the old or the new version of the data structure rather than a
partially updated reference. The reclamation phase does the work of reclaiming
(e.g., freeing) the data items removed from the data structure during the
removal phase. Because reclaiming data items can disrupt any readers
concurrently referencing those data items, the reclamation phase must
not start until readers no longer hold references to those data items.</p>
<p>Splitting the update into removal and reclamation phases permits the
updater to perform the removal phase immediately, and to defer the
reclamation phase until all readers active during the removal phase have
completed, either by blocking until they finish or by registering a
callback that is invoked after they finish. Only readers that are active
during the removal phase need be considered, because any reader starting
after the removal phase will be unable to gain a reference to the removed
data items, and therefore cannot be disrupted by the reclamation phase.</p>
<p>So the typical RCU update sequence goes something like the following:</p>
<ol class="loweralpha simple">
<li><p>Remove pointers to a data structure, so that subsequent
readers cannot gain a reference to it.</p></li>
<li><p>Wait for all previous readers to complete their RCU read-side
critical sections.</p></li>
<li><p>At this point, there cannot be any readers who hold references
to the data structure, so it now may safely be reclaimed
(e.g., <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>d).</p></li>
</ol>
<p>Step (b) above is the key idea underlying RCU’s deferred destruction.
The ability to wait until all readers are done allows RCU readers to
use much lighter-weight synchronization, in some cases, absolutely no
synchronization at all. In contrast, in more conventional lock-based
schemes, readers must use heavy-weight synchronization in order to
prevent an updater from deleting the data structure out from under them.
This is because lock-based updaters typically update data items in place,
and must therefore exclude readers. In contrast, RCU-based updaters
typically take advantage of the fact that writes to single aligned
pointers are atomic on modern CPUs, allowing atomic insertion, removal,
and replacement of data items in a linked structure without disrupting
readers. Concurrent RCU readers can then continue accessing the old
versions, and can dispense with the atomic operations, memory barriers,
and communications cache misses that are so expensive on present-day
SMP computer systems, even in absence of lock contention.</p>
<p>In the three-step procedure shown above, the updater is performing both
the removal and the reclamation step, but it is often helpful for an
entirely different thread to do the reclamation, as is in fact the case
in the Linux kernel’s directory-entry cache (dcache). Even if the same
thread performs both the update step (step (a) above) and the reclamation
step (step (c) above), it is often helpful to think of them separately.
For example, RCU readers and updaters need not communicate at all,
but RCU provides implicit low-overhead communication between readers
and reclaimers, namely, in step (b) above.</p>
<p>So how the heck can a reclaimer tell when a reader is done, given
that readers are not doing any sort of synchronization operations???
Read on to learn about how RCU’s API makes this easy.</p>
</section>
<section id="what-is-rcu-s-core-api">
<span id="id1"></span><h2>2. WHAT IS RCU’S CORE API?<a class="headerlink" href="#what-is-rcu-s-core-api" title="Link to this heading">¶</a></h2>
<p>The core RCU API is quite small:</p>
<ol class="loweralpha simple">
<li><p><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></p></li>
<li><p><a class="reference internal" href="../core-api/kernel-api.html#c.rcu_read_unlock" title="rcu_read_unlock"><code class="xref c c-func docutils literal notranslate"><span class="pre">rcu_read_unlock()</span></code></a></p></li>
<li><p><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> / <a class="reference internal" href="../core-api/kernel-api.html#c.call_rcu" title="call_rcu"><code class="xref c c-func docutils literal notranslate"><span class="pre">call_rcu()</span></code></a></p></li>
<li><p><a class="reference internal" href="../core-api/kernel-api.html#c.rcu_assign_pointer" title="rcu_assign_pointer"><code class="xref c c-func docutils literal notranslate"><span class="pre">rcu_assign_pointer()</span></code></a></p></li>
<li><p><a class="reference internal" href="../core-api/kernel-api.html#c.rcu_dereference" title="rcu_dereference"><code class="xref c c-func docutils literal notranslate"><span class="pre">rcu_dereference()</span></code></a></p></li>
</ol>
<p>There are many other members of the RCU API, but the rest can be
expressed in terms of these five, though most implementations instead
express <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> in terms of the <a class="reference internal" href="../core-api/kernel-api.html#c.call_rcu" title="call_rcu"><code class="xref c c-func docutils literal notranslate"><span class="pre">call_rcu()</span></code></a> callback API.</p>
<p>The five core RCU APIs are described below, the other 18 will be enumerated
later. See the kernel docbook documentation for more info, or look directly
at the function header comments.</p>
<section id="rcu-read-lock">
<h3>rcu_read_lock()<a class="headerlink" href="#rcu-read-lock" title="Link to this heading">¶</a></h3>
<blockquote>
<div><p>void rcu_read_lock(void);</p>
<p>This temporal primitive is used by a reader to inform the
reclaimer that the reader is entering an RCU read-side critical
section. It is illegal to block while in an RCU read-side
critical section, though kernels built with CONFIG_PREEMPT_RCU
can preempt RCU read-side critical sections. Any RCU-protected
data structure accessed during an RCU read-side critical section
is guaranteed to remain unreclaimed for the full duration of that
critical section. Reference counts may be used in conjunction
with RCU to maintain longer-term references to data structures.</p>
<p>Note that anything that disables bottom halves, preemption,
or interrupts also enters an RCU read-side critical section.
Acquiring a spinlock also enters an RCU read-side critical
sections, even for spinlocks that do not disable preemption,
as is the case in kernels built with CONFIG_PREEMPT_RT=y.
Sleeplocks do <em>not</em> enter RCU read-side critical sections.</p>
</div></blockquote>
</section>
<section id="rcu-read-unlock">
<h3>rcu_read_unlock()<a class="headerlink" href="#rcu-read-unlock" title="Link to this heading">¶</a></h3>
<blockquote>
<div><p>void rcu_read_unlock(void);</p>
<p>This temporal primitives is used by a reader to inform the
reclaimer that the reader is exiting an RCU read-side critical
section. Anything that enables bottom halves, preemption,
or interrupts also exits an RCU read-side critical section.
Releasing a spinlock also exits an RCU read-side critical section.</p>
<p>Note that RCU read-side critical sections may be nested and/or
overlapping.</p>
</div></blockquote>
</section>
<section id="synchronize-rcu">
<h3>synchronize_rcu()<a class="headerlink" href="#synchronize-rcu" title="Link to this heading">¶</a></h3>
<blockquote>
<div><p>void synchronize_rcu(void);</p>
<p>This temporal primitive marks the end of updater code and the
beginning of reclaimer code. It does this by blocking until
all pre-existing RCU read-side critical sections on all CPUs
have completed. Note that <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> will <strong>not</strong>
necessarily wait for any subsequent RCU read-side critical
sections to complete. For example, consider the following
sequence of events:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span> CPU 0 CPU 1 CPU 2
----------------- ------------------------- ---------------
1. rcu_read_lock()
2. enters synchronize_rcu()
3. rcu_read_lock()
4. rcu_read_unlock()
5. exits synchronize_rcu()
6. rcu_read_unlock()
</pre></div>
</div>
<p>To reiterate, <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> waits only for ongoing RCU
read-side critical sections to complete, not necessarily for
any that begin after <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> is invoked.</p>
<p>Of course, <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> does not necessarily return
<strong>immediately</strong> after the last pre-existing RCU read-side critical
section completes. For one thing, there might well be scheduling
delays. For another thing, many RCU implementations process
requests in batches in order to improve efficiencies, which can
further delay <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>.</p>
<p>Since <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> is the API that must figure out when
readers are done, its implementation is key to RCU. For RCU
to be useful in all but the most read-intensive situations,
<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>’s overhead must also be quite small.</p>
<p>The <a class="reference internal" href="../core-api/kernel-api.html#c.call_rcu" title="call_rcu"><code class="xref c c-func docutils literal notranslate"><span class="pre">call_rcu()</span></code></a> API is an asynchronous callback form of
<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>, and is described in more detail in a later
section. Instead of blocking, it registers a function and
argument which are invoked after all ongoing RCU read-side
critical sections have completed. This callback variant is
particularly useful in situations where it is illegal to block
or where update-side performance is critically important.</p>
<p>However, the <a class="reference internal" href="../core-api/kernel-api.html#c.call_rcu" title="call_rcu"><code class="xref c c-func docutils literal notranslate"><span class="pre">call_rcu()</span></code></a> API should not be used lightly, as use
of the <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> API generally results in simpler code.
In addition, the <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> API has the nice property
of automatically limiting update rate should grace periods
be delayed. This property results in system resilience in face
of denial-of-service attacks. Code using <a class="reference internal" href="../core-api/kernel-api.html#c.call_rcu" title="call_rcu"><code class="xref c c-func docutils literal notranslate"><span class="pre">call_rcu()</span></code></a> should limit
update rate in order to gain this same sort of resilience. See
<a class="reference internal" href="checklist.html"><span class="doc">Review Checklist for RCU Patches</span></a> for some approaches to limiting the update rate.</p>
</div></blockquote>
</section>
<section id="rcu-assign-pointer">
<h3>rcu_assign_pointer()<a class="headerlink" href="#rcu-assign-pointer" title="Link to this heading">¶</a></h3>
<blockquote>
<div><p>void rcu_assign_pointer(p, typeof(p) v);</p>
<p>Yes, <a class="reference internal" href="../core-api/kernel-api.html#c.rcu_assign_pointer" title="rcu_assign_pointer"><code class="xref c c-func docutils literal notranslate"><span class="pre">rcu_assign_pointer()</span></code></a> <strong>is</strong> implemented as a macro, though
it would be cool to be able to declare a function in this manner.
(And there has been some discussion of adding overloaded functions
to the C language, so who knows?)</p>
<p>The updater uses this spatial macro to assign a new value to an
RCU-protected pointer, in order to safely communicate the change
in value from the updater to the reader. This is a spatial (as
opposed to temporal) macro. It does not evaluate to an rvalue,
but it does provide any compiler directives and memory-barrier
instructions required for a given compile or CPU architecture.
Its ordering properties are that of a store-release operation,
that is, any prior loads and stores required to initialize the
structure are ordered before the store that publishes the pointer
to that structure.</p>
<p>Perhaps just as important, <a class="reference internal" href="../core-api/kernel-api.html#c.rcu_assign_pointer" title="rcu_assign_pointer"><code class="xref c c-func docutils literal notranslate"><span class="pre">rcu_assign_pointer()</span></code></a> serves to document
(1) which pointers are protected by RCU and (2) the point at which
a given structure becomes accessible to other CPUs. That said,
<a class="reference internal" href="../core-api/kernel-api.html#c.rcu_assign_pointer" title="rcu_assign_pointer"><code class="xref c c-func docutils literal notranslate"><span class="pre">rcu_assign_pointer()</span></code></a> is most frequently used indirectly, via
the _rcu list-manipulation primitives such as <a class="reference internal" href="../core-api/kernel-api.html#c.list_add_rcu" title="list_add_rcu"><code class="xref c c-func docutils literal notranslate"><span class="pre">list_add_rcu()</span></code></a>.</p>
</div></blockquote>
</section>
<section id="rcu-dereference">
<h3>rcu_dereference()<a class="headerlink" href="#rcu-dereference" title="Link to this heading">¶</a></h3>
<blockquote>
<div><p>typeof(p) rcu_dereference(p);</p>
<p>Like <a class="reference internal" href="../core-api/kernel-api.html#c.rcu_assign_pointer" title="rcu_assign_pointer"><code class="xref c c-func docutils literal notranslate"><span class="pre">rcu_assign_pointer()</span></code></a>, <a class="reference internal" href="../core-api/kernel-api.html#c.rcu_dereference" title="rcu_dereference"><code class="xref c c-func docutils literal notranslate"><span class="pre">rcu_dereference()</span></code></a> must be implemented
as a macro.</p>
<p>The reader uses the spatial <a class="reference internal" href="../core-api/kernel-api.html#c.rcu_dereference" title="rcu_dereference"><code class="xref c c-func docutils literal notranslate"><span class="pre">rcu_dereference()</span></code></a> macro to fetch
an RCU-protected pointer, which returns a value that may
then be safely dereferenced. Note that <a class="reference internal" href="../core-api/kernel-api.html#c.rcu_dereference" title="rcu_dereference"><code class="xref c c-func docutils literal notranslate"><span class="pre">rcu_dereference()</span></code></a>
does not actually dereference the pointer, instead, it
protects the pointer for later dereferencing. It also
executes any needed memory-barrier instructions for a given
CPU architecture. Currently, only Alpha needs memory barriers
within <a class="reference internal" href="../core-api/kernel-api.html#c.rcu_dereference" title="rcu_dereference"><code class="xref c c-func docutils literal notranslate"><span class="pre">rcu_dereference()</span></code></a> -- on other CPUs, it compiles to a
volatile load. However, no mainstream C compilers respect
address dependencies, so <a class="reference internal" href="../core-api/kernel-api.html#c.rcu_dereference" title="rcu_dereference"><code class="xref c c-func docutils literal notranslate"><span class="pre">rcu_dereference()</span></code></a> uses volatile casts,
which, in combination with the coding guidelines listed in
<a class="reference internal" href="rcu_dereference.html"><span class="doc">PROPER CARE AND FEEDING OF RETURN VALUES FROM rcu_dereference()</span></a>, prevent current compilers from breaking
these dependencies.</p>
<p>Common coding practice uses <a class="reference internal" href="../core-api/kernel-api.html#c.rcu_dereference" title="rcu_dereference"><code class="xref c c-func docutils literal notranslate"><span class="pre">rcu_dereference()</span></code></a> to copy an
RCU-protected pointer to a local variable, then dereferences
this local variable, for example as follows:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>p = rcu_dereference(head.next);
return p->data;
</pre></div>
</div>
<p>However, in this case, one could just as easily combine these
into one statement:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>return rcu_dereference(head.next)->data;
</pre></div>
</div>
<p>If you are going to be fetching multiple fields from the
RCU-protected structure, using the local variable is of
course preferred. Repeated <a class="reference internal" href="../core-api/kernel-api.html#c.rcu_dereference" title="rcu_dereference"><code class="xref c c-func docutils literal notranslate"><span class="pre">rcu_dereference()</span></code></a> calls look
ugly, do not guarantee that the same pointer will be returned
if an update happened while in the critical section, and incur
unnecessary overhead on Alpha CPUs.</p>
<p>Note that the value returned by <a class="reference internal" href="../core-api/kernel-api.html#c.rcu_dereference" title="rcu_dereference"><code class="xref c c-func docutils literal notranslate"><span class="pre">rcu_dereference()</span></code></a> is valid
only within the enclosing RCU read-side critical section <a class="footnote-reference brackets" href="#id4" id="id2" role="doc-noteref"><span class="fn-bracket">[</span>1<span class="fn-bracket">]</span></a>.
For example, the following is <strong>not</strong> legal:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>rcu_read_lock();
p = rcu_dereference(head.next);
rcu_read_unlock();
x = p->address; /* BUG!!! */
rcu_read_lock();
y = p->data; /* BUG!!! */
rcu_read_unlock();
</pre></div>
</div>
<p>Holding a reference from one RCU read-side critical section
to another is just as illegal as holding a reference from
one lock-based critical section to another! Similarly,
using a reference outside of the critical section in which
it was acquired is just as illegal as doing so with normal
locking.</p>
<p>As with <a class="reference internal" href="../core-api/kernel-api.html#c.rcu_assign_pointer" title="rcu_assign_pointer"><code class="xref c c-func docutils literal notranslate"><span class="pre">rcu_assign_pointer()</span></code></a>, an important function of
<a class="reference internal" href="../core-api/kernel-api.html#c.rcu_dereference" title="rcu_dereference"><code class="xref c c-func docutils literal notranslate"><span class="pre">rcu_dereference()</span></code></a> is to document which pointers are protected by
RCU, in particular, flagging a pointer that is subject to changing
at any time, including immediately after the <a class="reference internal" href="../core-api/kernel-api.html#c.rcu_dereference" title="rcu_dereference"><code class="xref c c-func docutils literal notranslate"><span class="pre">rcu_dereference()</span></code></a>.
And, again like <a class="reference internal" href="../core-api/kernel-api.html#c.rcu_assign_pointer" title="rcu_assign_pointer"><code class="xref c c-func docutils literal notranslate"><span class="pre">rcu_assign_pointer()</span></code></a>, <a class="reference internal" href="../core-api/kernel-api.html#c.rcu_dereference" title="rcu_dereference"><code class="xref c c-func docutils literal notranslate"><span class="pre">rcu_dereference()</span></code></a> is
typically used indirectly, via the _rcu list-manipulation
primitives, such as <a class="reference internal" href="../core-api/kernel-api.html#c.list_for_each_entry_rcu" title="list_for_each_entry_rcu"><code class="xref c c-func docutils literal notranslate"><span class="pre">list_for_each_entry_rcu()</span></code></a> <a class="footnote-reference brackets" href="#id5" id="id3" role="doc-noteref"><span class="fn-bracket">[</span>2<span class="fn-bracket">]</span></a>.</p>
</div></blockquote>
<aside class="footnote-list brackets">
<aside class="footnote brackets" id="id4" role="doc-footnote">
<span class="label"><span class="fn-bracket">[</span><a role="doc-backlink" href="#id2">1</a><span class="fn-bracket">]</span></span>
<p>The variant <a class="reference internal" href="../core-api/kernel-api.html#c.rcu_dereference_protected" title="rcu_dereference_protected"><code class="xref c c-func docutils literal notranslate"><span class="pre">rcu_dereference_protected()</span></code></a> can be used outside
of an RCU read-side critical section as long as the usage is
protected by locks acquired by the update-side code. This variant
avoids the lockdep warning that would happen when using (for
example) <a class="reference internal" href="../core-api/kernel-api.html#c.rcu_dereference" title="rcu_dereference"><code class="xref c c-func docutils literal notranslate"><span class="pre">rcu_dereference()</span></code></a> without <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> protection.
Using <a class="reference internal" href="../core-api/kernel-api.html#c.rcu_dereference_protected" title="rcu_dereference_protected"><code class="xref c c-func docutils literal notranslate"><span class="pre">rcu_dereference_protected()</span></code></a> also has the advantage
of permitting compiler optimizations that <a class="reference internal" href="../core-api/kernel-api.html#c.rcu_dereference" title="rcu_dereference"><code class="xref c c-func docutils literal notranslate"><span class="pre">rcu_dereference()</span></code></a>
must prohibit. The <a class="reference internal" href="../core-api/kernel-api.html#c.rcu_dereference_protected" title="rcu_dereference_protected"><code class="xref c c-func docutils literal notranslate"><span class="pre">rcu_dereference_protected()</span></code></a> variant takes
a lockdep expression to indicate which locks must be acquired
by the caller. If the indicated protection is not provided,
a lockdep splat is emitted. See <a class="reference internal" href="Design/Requirements/Requirements.html"><span class="doc">A Tour Through RCU’s Requirements</span></a>
and the API’s code comments for more details and example usage.</p>
</aside>
<aside class="footnote brackets" id="id5" role="doc-footnote">
<span class="label"><span class="fn-bracket">[</span><a role="doc-backlink" href="#id3">2</a><span class="fn-bracket">]</span></span>
<p>If the <a class="reference internal" href="../core-api/kernel-api.html#c.list_for_each_entry_rcu" title="list_for_each_entry_rcu"><code class="xref c c-func docutils literal notranslate"><span class="pre">list_for_each_entry_rcu()</span></code></a> instance might be used by
update-side code as well as by RCU readers, then an additional
lockdep expression can be added to its list of arguments.
For example, given an additional “lock_is_held(&mylock)” argument,
the RCU lockdep code would complain only if this instance was
invoked outside of an RCU read-side critical section and without
the protection of mylock.</p>
</aside>
</aside>
<p>The following diagram shows how each API communicates among the
reader, updater, and reclaimer.</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>rcu_assign_pointer()
+--------+
+---------------------->| reader |---------+
| +--------+ |
| | |
| | | Protect:
| | | rcu_read_lock()
| | | rcu_read_unlock()
| rcu_dereference() | |
+---------+ | |
| updater |<----------------+ |
+---------+ V
| +-----------+
+----------------------------------->| reclaimer |
+-----------+
Defer:
synchronize_rcu() & call_rcu()
</pre></div>
</div>
<p>The RCU infrastructure observes the temporal sequence of <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>,
<a class="reference internal" href="../core-api/kernel-api.html#c.rcu_read_unlock" title="rcu_read_unlock"><code class="xref c c-func docutils literal notranslate"><span class="pre">rcu_read_unlock()</span></code></a>, <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>, and <a class="reference internal" href="../core-api/kernel-api.html#c.call_rcu" title="call_rcu"><code class="xref c c-func docutils literal notranslate"><span class="pre">call_rcu()</span></code></a> invocations in
order to determine when (1) <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> invocations may return
to their callers and (2) <a class="reference internal" href="../core-api/kernel-api.html#c.call_rcu" title="call_rcu"><code class="xref c c-func docutils literal notranslate"><span class="pre">call_rcu()</span></code></a> callbacks may be invoked. Efficient
implementations of the RCU infrastructure make heavy use of batching in
order to amortize their overhead over many uses of the corresponding APIs.
The <a class="reference internal" href="../core-api/kernel-api.html#c.rcu_assign_pointer" title="rcu_assign_pointer"><code class="xref c c-func docutils literal notranslate"><span class="pre">rcu_assign_pointer()</span></code></a> and <a class="reference internal" href="../core-api/kernel-api.html#c.rcu_dereference" title="rcu_dereference"><code class="xref c c-func docutils literal notranslate"><span class="pre">rcu_dereference()</span></code></a> invocations communicate
spatial changes via stores to and loads from the RCU-protected pointer in
question.</p>
<p>There are at least three flavors of RCU usage in the Linux kernel. The diagram
above shows the most common one. On the updater side, the <a class="reference internal" href="../core-api/kernel-api.html#c.rcu_assign_pointer" title="rcu_assign_pointer"><code class="xref c c-func docutils literal notranslate"><span class="pre">rcu_assign_pointer()</span></code></a>,
<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> and <a class="reference internal" href="../core-api/kernel-api.html#c.call_rcu" title="call_rcu"><code class="xref c c-func docutils literal notranslate"><span class="pre">call_rcu()</span></code></a> primitives used are the same for all three
flavors. However for protection (on the reader side), the primitives used vary
depending on the flavor:</p>
<ol class="loweralpha simple">
<li><p><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> / <a class="reference internal" href="../core-api/kernel-api.html#c.rcu_read_unlock" title="rcu_read_unlock"><code class="xref c c-func docutils literal notranslate"><span class="pre">rcu_read_unlock()</span></code></a>
<a class="reference internal" href="../core-api/kernel-api.html#c.rcu_dereference" title="rcu_dereference"><code class="xref c c-func docutils literal notranslate"><span class="pre">rcu_dereference()</span></code></a></p></li>
<li><p><a class="reference internal" href="../core-api/kernel-api.html#c.rcu_read_lock_bh" title="rcu_read_lock_bh"><code class="xref c c-func docutils literal notranslate"><span class="pre">rcu_read_lock_bh()</span></code></a> / <a class="reference internal" href="../core-api/kernel-api.html#c.rcu_read_unlock_bh" title="rcu_read_unlock_bh"><code class="xref c c-func docutils literal notranslate"><span class="pre">rcu_read_unlock_bh()</span></code></a>
<code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">local_bh_disable()</span></code> / <code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">local_bh_enable()</span></code>
<a class="reference internal" href="../core-api/kernel-api.html#c.rcu_dereference_bh" title="rcu_dereference_bh"><code class="xref c c-func docutils literal notranslate"><span class="pre">rcu_dereference_bh()</span></code></a></p></li>
<li><p><a class="reference internal" href="../core-api/kernel-api.html#c.rcu_read_lock_sched" title="rcu_read_lock_sched"><code class="xref c c-func docutils literal notranslate"><span class="pre">rcu_read_lock_sched()</span></code></a> / <a class="reference internal" href="../core-api/kernel-api.html#c.rcu_read_unlock_sched" title="rcu_read_unlock_sched"><code class="xref c c-func docutils literal notranslate"><span class="pre">rcu_read_unlock_sched()</span></code></a>
<code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">preempt_disable()</span></code> / <code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">preempt_enable()</span></code>
<code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">local_irq_save()</span></code> / <code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">local_irq_restore()</span></code>
hardirq enter / hardirq exit
NMI enter / NMI exit
<a class="reference internal" href="../core-api/kernel-api.html#c.rcu_dereference_sched" title="rcu_dereference_sched"><code class="xref c c-func docutils literal notranslate"><span class="pre">rcu_dereference_sched()</span></code></a></p></li>
</ol>
<p>These three flavors are used as follows:</p>
<ol class="loweralpha simple">
<li><p>RCU applied to normal data structures.</p></li>
<li><p>RCU applied to networking data structures that may be subjected
to remote denial-of-service attacks.</p></li>
<li><p>RCU applied to scheduler and interrupt/NMI-handler tasks.</p></li>
</ol>
<p>Again, most uses will be of (a). The (b) and (c) cases are important
for specialized uses, but are relatively uncommon. The SRCU, RCU-Tasks,
RCU-Tasks-Rude, and RCU-Tasks-Trace have similar relationships among
their assorted primitives.</p>
</section>
</section>
<section id="what-are-some-example-uses-of-core-rcu-api">
<span id="id6"></span><h2>3. WHAT ARE SOME EXAMPLE USES OF CORE RCU API?<a class="headerlink" href="#what-are-some-example-uses-of-core-rcu-api" title="Link to this heading">¶</a></h2>
<p>This section shows a simple use of the core RCU API to protect a
global pointer to a dynamically allocated structure. More-typical
uses of RCU may be found in <a class="reference internal" href="listRCU.html"><span class="doc">Using RCU to Protect Read-Mostly Linked Lists</span></a> and <a class="reference internal" href="NMI-RCU.html"><span class="doc">Using RCU to Protect Dynamic NMI Handlers</span></a>.</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>struct foo {
int a;
char b;
long c;
};
DEFINE_SPINLOCK(foo_mutex);
struct foo __rcu *gbl_foo;
/*
* Create a new struct foo that is the same as the one currently
* pointed to by gbl_foo, except that field "a" is replaced
* with "new_a". Points gbl_foo to the new structure, and
* frees up the old structure after a grace period.
*
* Uses rcu_assign_pointer() to ensure that concurrent readers
* see the initialized version of the new structure.
*
* Uses synchronize_rcu() to ensure that any readers that might
* have references to the old structure complete before freeing
* the old structure.
*/
void foo_update_a(int new_a)
{
struct foo *new_fp;
struct foo *old_fp;
new_fp = kmalloc(sizeof(*new_fp), GFP_KERNEL);
spin_lock(&foo_mutex);
old_fp = rcu_dereference_protected(gbl_foo, lockdep_is_held(&foo_mutex));
*new_fp = *old_fp;
new_fp->a = new_a;
rcu_assign_pointer(gbl_foo, new_fp);
spin_unlock(&foo_mutex);
synchronize_rcu();
kfree(old_fp);
}
/*
* Return the value of field "a" of the current gbl_foo
* structure. Use rcu_read_lock() and rcu_read_unlock()
* to ensure that the structure does not get deleted out
* from under us, and use rcu_dereference() to ensure that
* we see the initialized version of the structure (important
* for DEC Alpha and for people reading the code).
*/
int foo_get_a(void)
{
int retval;
rcu_read_lock();
retval = rcu_dereference(gbl_foo)->a;
rcu_read_unlock();
return retval;
}
</pre></div>
</div>
<p>So, to sum up:</p>
<ul class="simple">
<li><p>Use <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> and <a class="reference internal" href="../core-api/kernel-api.html#c.rcu_read_unlock" title="rcu_read_unlock"><code class="xref c c-func docutils literal notranslate"><span class="pre">rcu_read_unlock()</span></code></a> to guard RCU
read-side critical sections.</p></li>
<li><p>Within an RCU read-side critical section, use <a class="reference internal" href="../core-api/kernel-api.html#c.rcu_dereference" title="rcu_dereference"><code class="xref c c-func docutils literal notranslate"><span class="pre">rcu_dereference()</span></code></a>
to dereference RCU-protected pointers.</p></li>
<li><p>Use some solid design (such as locks or semaphores) to
keep concurrent updates from interfering with each other.</p></li>
<li><p>Use <a class="reference internal" href="../core-api/kernel-api.html#c.rcu_assign_pointer" title="rcu_assign_pointer"><code class="xref c c-func docutils literal notranslate"><span class="pre">rcu_assign_pointer()</span></code></a> to update an RCU-protected pointer.
This primitive protects concurrent readers from the updater,
<strong>not</strong> concurrent updates from each other! You therefore still
need to use locking (or something similar) to keep concurrent
<a class="reference internal" href="../core-api/kernel-api.html#c.rcu_assign_pointer" title="rcu_assign_pointer"><code class="xref c c-func docutils literal notranslate"><span class="pre">rcu_assign_pointer()</span></code></a> primitives from interfering with each other.</p></li>
<li><p>Use <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> <strong>after</strong> removing a data element from an
RCU-protected data structure, but <strong>before</strong> reclaiming/freeing
the data element, in order to wait for the completion of all
RCU read-side critical sections that might be referencing that
data item.</p></li>
</ul>
<p>See <a class="reference internal" href="checklist.html"><span class="doc">Review Checklist for RCU Patches</span></a> for additional rules to follow when using RCU.
And again, more-typical uses of RCU may be found in <a class="reference internal" href="listRCU.html"><span class="doc">Using RCU to Protect Read-Mostly Linked Lists</span></a>
and <a class="reference internal" href="NMI-RCU.html"><span class="doc">Using RCU to Protect Dynamic NMI Handlers</span></a>.</p>
</section>
<section id="what-if-my-updating-thread-cannot-block">
<span id="id7"></span><h2>4. WHAT IF MY UPDATING THREAD CANNOT BLOCK?<a class="headerlink" href="#what-if-my-updating-thread-cannot-block" title="Link to this heading">¶</a></h2>
<p>In the example above, <code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">foo_update_a()</span></code> blocks until a grace period elapses.
This is quite simple, but in some cases one cannot afford to wait so
long -- there might be other high-priority work to be done.</p>
<p>In such cases, one uses <a class="reference internal" href="../core-api/kernel-api.html#c.call_rcu" title="call_rcu"><code class="xref c c-func docutils literal notranslate"><span class="pre">call_rcu()</span></code></a> rather than <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>.
The <a class="reference internal" href="../core-api/kernel-api.html#c.call_rcu" title="call_rcu"><code class="xref c c-func docutils literal notranslate"><span class="pre">call_rcu()</span></code></a> API is as follows:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>void call_rcu(struct rcu_head *head, rcu_callback_t func);
</pre></div>
</div>
<p>This function invokes func(head) after a grace period has elapsed.
This invocation might happen from either softirq or process context,
so the function is not permitted to block. The foo <code class="xref c c-struct broken_xref docutils literal notranslate"><span class="pre">struct</span> <span class="pre">needs</span></code> to
have an rcu_head structure added, perhaps as follows:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>struct foo {
int a;
char b;
long c;
struct rcu_head rcu;
};
</pre></div>
</div>
<p>The <code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">foo_update_a()</span></code> function might then be written as follows:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>/*
* Create a new struct foo that is the same as the one currently
* pointed to by gbl_foo, except that field "a" is replaced
* with "new_a". Points gbl_foo to the new structure, and
* frees up the old structure after a grace period.
*
* Uses rcu_assign_pointer() to ensure that concurrent readers
* see the initialized version of the new structure.
*
* Uses call_rcu() to ensure that any readers that might have
* references to the old structure complete before freeing the
* old structure.
*/
void foo_update_a(int new_a)
{
struct foo *new_fp;
struct foo *old_fp;
new_fp = kmalloc(sizeof(*new_fp), GFP_KERNEL);
spin_lock(&foo_mutex);
old_fp = rcu_dereference_protected(gbl_foo, lockdep_is_held(&foo_mutex));
*new_fp = *old_fp;
new_fp->a = new_a;
rcu_assign_pointer(gbl_foo, new_fp);
spin_unlock(&foo_mutex);
call_rcu(&old_fp->rcu, foo_reclaim);
}
</pre></div>
</div>
<p>The <code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">foo_reclaim()</span></code> function might appear as follows:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>void foo_reclaim(struct rcu_head *rp)
{
struct foo *fp = container_of(rp, struct foo, rcu);
foo_cleanup(fp->a);
kfree(fp);
}
</pre></div>
</div>
<p>The <code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">container_of()</span></code> primitive is a macro that, given a pointer into a
struct, the type of the struct, and the pointed-to field within the
struct, returns a pointer to the beginning of the struct.</p>
<p>The use of <a class="reference internal" href="../core-api/kernel-api.html#c.call_rcu" title="call_rcu"><code class="xref c c-func docutils literal notranslate"><span class="pre">call_rcu()</span></code></a> permits the caller of <code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">foo_update_a()</span></code> to
immediately regain control, without needing to worry further about the
old version of the newly updated element. It also clearly shows the
RCU distinction between updater, namely <code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">foo_update_a()</span></code>, and reclaimer,
namely <code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">foo_reclaim()</span></code>.</p>
<p>The summary of advice is the same as for the previous section, except
that we are now using <a class="reference internal" href="../core-api/kernel-api.html#c.call_rcu" title="call_rcu"><code class="xref c c-func docutils literal notranslate"><span class="pre">call_rcu()</span></code></a> rather than <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>:</p>
<ul class="simple">
<li><p>Use <a class="reference internal" href="../core-api/kernel-api.html#c.call_rcu" title="call_rcu"><code class="xref c c-func docutils literal notranslate"><span class="pre">call_rcu()</span></code></a> <strong>after</strong> removing a data element from an
RCU-protected data structure in order to register a callback
function that will be invoked after the completion of all RCU
read-side critical sections that might be referencing that
data item.</p></li>
</ul>
<p>If the callback for <a class="reference internal" href="../core-api/kernel-api.html#c.call_rcu" title="call_rcu"><code class="xref c c-func docutils literal notranslate"><span class="pre">call_rcu()</span></code></a> is not doing anything more than calling
<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> on the structure, you can use <a class="reference internal" href="../core-api/kernel-api.html#c.kfree_rcu" title="kfree_rcu"><code class="xref c c-func docutils literal notranslate"><span class="pre">kfree_rcu()</span></code></a> instead of <a class="reference internal" href="../core-api/kernel-api.html#c.call_rcu" title="call_rcu"><code class="xref c c-func docutils literal notranslate"><span class="pre">call_rcu()</span></code></a>
to avoid having to write your own callback:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>kfree_rcu(old_fp, rcu);
</pre></div>
</div>
<p>If the occasional sleep is permitted, the single-argument form may
be used, omitting the rcu_head structure from <code class="xref c c-struct broken_xref docutils literal notranslate"><span class="pre">struct</span> <span class="pre">foo</span></code>.</p>
<blockquote>
<div><p>kfree_rcu_mightsleep(old_fp);</p>
</div></blockquote>
<p>This variant almost never blocks, but might do so by invoking
<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> in response to memory-allocation failure.</p>
<p>Again, see <a class="reference internal" href="checklist.html"><span class="doc">Review Checklist for RCU Patches</span></a> for additional rules governing the use of RCU.</p>
</section>
<section id="what-are-some-simple-implementations-of-rcu">
<span id="id8"></span><h2>5. WHAT ARE SOME SIMPLE IMPLEMENTATIONS OF RCU?<a class="headerlink" href="#what-are-some-simple-implementations-of-rcu" title="Link to this heading">¶</a></h2>
<p>One of the nice things about RCU is that it has extremely simple “toy”
implementations that are a good first step towards understanding the
production-quality implementations in the Linux kernel. This section
presents two such “toy” implementations of RCU, one that is implemented
in terms of familiar locking primitives, and another that more closely
resembles “classic” RCU. Both are way too simple for real-world use,
lacking both functionality and performance. However, they are useful
in getting a feel for how RCU works. See kernel/rcu/update.c for a
production-quality implementation, and see:</p>
<blockquote>
<div><p><a class="reference external" href="https://docs.google.com/document/d/1X0lThx8OK0ZgLMqVoXiR4ZrGURHrXK6NyLRbeXe3Xac/edit">https://docs.google.com/document/d/1X0lThx8OK0ZgLMqVoXiR4ZrGURHrXK6NyLRbeXe3Xac/edit</a></p>
</div></blockquote>
<p>for papers describing the Linux kernel RCU implementation. The OLS’01
and OLS’02 papers are a good introduction, and the dissertation provides
more details on the current implementation as of early 2004.</p>
<section id="a-toy-implementation-1-locking">
<h3>5A. “TOY” IMPLEMENTATION #1: LOCKING<a class="headerlink" href="#a-toy-implementation-1-locking" title="Link to this heading">¶</a></h3>
<p>This section presents a “toy” RCU implementation that is based on
familiar locking primitives. Its overhead makes it a non-starter for
real-life use, as does its lack of scalability. It is also unsuitable
for realtime use, since it allows scheduling latency to “bleed” from
one read-side critical section to another. It also assumes recursive
reader-writer locks: If you try this with non-recursive locks, and
you allow nested <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> calls, you can deadlock.</p>
<p>However, it is probably the easiest implementation to relate to, so is
a good starting point.</p>
<p>It is extremely simple:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>static DEFINE_RWLOCK(rcu_gp_mutex);
void rcu_read_lock(void)
{
read_lock(&rcu_gp_mutex);
}
void rcu_read_unlock(void)
{
read_unlock(&rcu_gp_mutex);
}
void synchronize_rcu(void)
{
write_lock(&rcu_gp_mutex);
smp_mb__after_spinlock();
write_unlock(&rcu_gp_mutex);
}
</pre></div>
</div>
<p>[You can ignore <a class="reference internal" href="../core-api/kernel-api.html#c.rcu_assign_pointer" title="rcu_assign_pointer"><code class="xref c c-func docutils literal notranslate"><span class="pre">rcu_assign_pointer()</span></code></a> and <a class="reference internal" href="../core-api/kernel-api.html#c.rcu_dereference" title="rcu_dereference"><code class="xref c c-func docutils literal notranslate"><span class="pre">rcu_dereference()</span></code></a> without missing
much. But here are simplified versions anyway. And whatever you do,
don’t forget about them when submitting patches making use of RCU!]:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>#define rcu_assign_pointer(p, v) \
({ \
smp_store_release(&(p), (v)); \
})
#define rcu_dereference(p) \
({ \
typeof(p) _________p1 = READ_ONCE(p); \
(_________p1); \
})
</pre></div>
</div>
<p>The <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> and <a class="reference internal" href="../core-api/kernel-api.html#c.rcu_read_unlock" title="rcu_read_unlock"><code class="xref c c-func docutils literal notranslate"><span class="pre">rcu_read_unlock()</span></code></a> primitive read-acquire
and release a global reader-writer lock. The <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>
primitive write-acquires this same lock, then releases it. This means
that once <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> exits, all RCU read-side critical sections
that were in progress before <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> was called are guaranteed
to have completed -- there is no way that <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> would have
been able to write-acquire the lock otherwise. The <code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">smp_mb__after_spinlock()</span></code>
promotes <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> to a full memory barrier in compliance with
the “Memory-Barrier Guarantees” listed in:</p>
<blockquote>
<div><p><a class="reference internal" href="Design/Requirements/Requirements.html"><span class="doc">A Tour Through RCU’s Requirements</span></a></p>
</div></blockquote>
<p>It is possible to nest <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>, since reader-writer locks may
be recursively acquired. Note also that <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> is immune
from deadlock (an important property of RCU). The reason for this is
that the only thing that can block <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> is a <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>.
But <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> does not acquire any locks while holding rcu_gp_mutex,
so there can be no deadlock cycle.</p>
<dl class="simple" id="quiz-1">
<dt>Quick Quiz #1:</dt><dd><p>Why is this argument naive? How could a deadlock
occur when using this algorithm in a real-world Linux
kernel? How could this deadlock be avoided?</p>
</dd>
</dl>
<p><a class="reference internal" href="#id12"><span class="std std-ref">Answers to Quick Quiz</span></a></p>
</section>
<section id="b-toy-example-2-classic-rcu">
<h3>5B. “TOY” EXAMPLE #2: CLASSIC RCU<a class="headerlink" href="#b-toy-example-2-classic-rcu" title="Link to this heading">¶</a></h3>
<p>This section presents a “toy” RCU implementation that is based on
“classic RCU”. It is also short on performance (but only for updates) and
on features such as hotplug CPU and the ability to run in CONFIG_PREEMPTION
kernels. The definitions of <a class="reference internal" href="../core-api/kernel-api.html#c.rcu_dereference" title="rcu_dereference"><code class="xref c c-func docutils literal notranslate"><span class="pre">rcu_dereference()</span></code></a> and <a class="reference internal" href="../core-api/kernel-api.html#c.rcu_assign_pointer" title="rcu_assign_pointer"><code class="xref c c-func docutils literal notranslate"><span class="pre">rcu_assign_pointer()</span></code></a>
are the same as those shown in the preceding section, so they are omitted.</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>void rcu_read_lock(void) { }
void rcu_read_unlock(void) { }
void synchronize_rcu(void)
{
int cpu;
for_each_possible_cpu(cpu)
run_on(cpu);
}
</pre></div>
</div>
<p>Note that <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> and <a class="reference internal" href="../core-api/kernel-api.html#c.rcu_read_unlock" title="rcu_read_unlock"><code class="xref c c-func docutils literal notranslate"><span class="pre">rcu_read_unlock()</span></code></a> do absolutely nothing.
This is the great strength of classic RCU in a non-preemptive kernel:
read-side overhead is precisely zero, at least on non-Alpha CPUs.
And there is absolutely no way that <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> can possibly
participate in a deadlock cycle!</p>
<p>The implementation of <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> simply schedules itself on each
CPU in turn. The <code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">run_on()</span></code> primitive can be implemented straightforwardly
in terms of the <code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">sched_setaffinity()</span></code> primitive. Of course, a somewhat less
“toy” implementation would restore the affinity upon completion rather
than just leaving all tasks running on the last CPU, but when I said
“toy”, I meant <strong>toy</strong>!</p>
<p>So how the heck is this supposed to work???</p>
<p>Remember that it is illegal to block while in an RCU read-side critical
section. Therefore, if a given CPU executes a context switch, we know
that it must have completed all preceding RCU read-side critical sections.
Once <strong>all</strong> CPUs have executed a context switch, then <strong>all</strong> preceding
RCU read-side critical sections will have completed.</p>
<p>So, suppose that we remove a data item from its structure and then invoke
<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>. Once <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> returns, we are guaranteed
that there are no RCU read-side critical sections holding a reference
to that data item, so we can safely reclaim it.</p>
<dl class="simple" id="quiz-2">
<dt>Quick Quiz #2:</dt><dd><p>Give an example where Classic RCU’s read-side
overhead is <strong>negative</strong>.</p>
</dd>
</dl>
<p><a class="reference internal" href="#id12"><span class="std std-ref">Answers to Quick Quiz</span></a></p>
<dl class="simple" id="quiz-3">
<dt>Quick Quiz #3:</dt><dd><p>If it is illegal to block in an RCU read-side
critical section, what the heck do you do in
CONFIG_PREEMPT_RT, where normal spinlocks can block???</p>
</dd>
</dl>
<p><a class="reference internal" href="#id12"><span class="std std-ref">Answers to Quick Quiz</span></a></p>
</section>
</section>
<section id="analogy-with-reader-writer-locking">
<span id="id9"></span><h2>6. ANALOGY WITH READER-WRITER LOCKING<a class="headerlink" href="#analogy-with-reader-writer-locking" title="Link to this heading">¶</a></h2>
<p>Although RCU can be used in many different ways, a very common use of
RCU is analogous to reader-writer locking. The following unified
diff shows how closely related RCU and reader-writer locking can be.</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>@@ -5,5 +5,5 @@ struct el {
int data;
/* Other data fields */
};
-rwlock_t listmutex;
+spinlock_t listmutex;
struct el head;
@@ -13,15 +14,15 @@
struct list_head *lp;
struct el *p;
- read_lock(&listmutex);
- list_for_each_entry(p, head, lp) {
+ rcu_read_lock();
+ list_for_each_entry_rcu(p, head, lp) {
if (p->key == key) {
*result = p->data;
- read_unlock(&listmutex);
+ rcu_read_unlock();
return 1;
}
}
- read_unlock(&listmutex);
+ rcu_read_unlock();
return 0;
}
@@ -29,15 +30,16 @@
{
struct el *p;
- write_lock(&listmutex);
+ spin_lock(&listmutex);
list_for_each_entry(p, head, lp) {
if (p->key == key) {
- list_del(&p->list);
- write_unlock(&listmutex);
+ list_del_rcu(&p->list);
+ spin_unlock(&listmutex);
+ synchronize_rcu();
kfree(p);
return 1;
}
}
- write_unlock(&listmutex);
+ spin_unlock(&listmutex);
return 0;
}
</pre></div>
</div>
<p>Or, for those who prefer a side-by-side listing:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>1 struct el { 1 struct el {
2 struct list_head list; 2 struct list_head list;
3 long key; 3 long key;
4 spinlock_t mutex; 4 spinlock_t mutex;
5 int data; 5 int data;
6 /* Other data fields */ 6 /* Other data fields */
7 }; 7 };
8 rwlock_t listmutex; 8 spinlock_t listmutex;
9 struct el head; 9 struct el head;
</pre></div>
</div>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span> 1 int search(long key, int *result) 1 int search(long key, int *result)
2 { 2 {
3 struct list_head *lp; 3 struct list_head *lp;
4 struct el *p; 4 struct el *p;
5 5
6 read_lock(&listmutex); 6 rcu_read_lock();
7 list_for_each_entry(p, head, lp) { 7 list_for_each_entry_rcu(p, head, lp) {
8 if (p->key == key) { 8 if (p->key == key) {
9 *result = p->data; 9 *result = p->data;
10 read_unlock(&listmutex); 10 rcu_read_unlock();
11 return 1; 11 return 1;
12 } 12 }
13 } 13 }
14 read_unlock(&listmutex); 14 rcu_read_unlock();
15 return 0; 15 return 0;
16 } 16 }
</pre></div>
</div>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span> 1 int delete(long key) 1 int delete(long key)
2 { 2 {
3 struct el *p; 3 struct el *p;
4 4
5 write_lock(&listmutex); 5 spin_lock(&listmutex);
6 list_for_each_entry(p, head, lp) { 6 list_for_each_entry(p, head, lp) {
7 if (p->key == key) { 7 if (p->key == key) {
8 list_del(&p->list); 8 list_del_rcu(&p->list);
9 write_unlock(&listmutex); 9 spin_unlock(&listmutex);
10 synchronize_rcu();
10 kfree(p); 11 kfree(p);
11 return 1; 12 return 1;
12 } 13 }
13 } 14 }
14 write_unlock(&listmutex); 15 spin_unlock(&listmutex);
15 return 0; 16 return 0;
16 } 17 }
</pre></div>
</div>
<p>Either way, the differences are quite small. Read-side locking moves
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> and rcu_read_unlock, update-side locking moves from
a reader-writer lock to a simple spinlock, and a <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>
precedes the <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>.</p>
<p>However, there is one potential catch: the read-side and update-side
critical sections can now run concurrently. In many cases, this will
not be a problem, but it is necessary to check carefully regardless.
For example, if multiple independent list updates must be seen as
a single atomic update, converting to RCU will require special care.</p>
<p>Also, the presence of <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> means that the RCU version of
<code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">delete()</span></code> can now block. If this is a problem, there is a callback-based
mechanism that never blocks, namely <a class="reference internal" href="../core-api/kernel-api.html#c.call_rcu" title="call_rcu"><code class="xref c c-func docutils literal notranslate"><span class="pre">call_rcu()</span></code></a> or <a class="reference internal" href="../core-api/kernel-api.html#c.kfree_rcu" title="kfree_rcu"><code class="xref c c-func docutils literal notranslate"><span class="pre">kfree_rcu()</span></code></a>, that can
be used in place of <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>.</p>
</section>
<section id="analogy-with-reference-counting">
<span id="id10"></span><h2>7. ANALOGY WITH REFERENCE COUNTING<a class="headerlink" href="#analogy-with-reference-counting" title="Link to this heading">¶</a></h2>
<p>The reader-writer analogy (illustrated by the previous section) is not
always the best way to think about using RCU. Another helpful analogy
considers RCU an effective reference count on everything which is
protected by RCU.</p>
<p>A reference count typically does not prevent the referenced object’s
values from changing, but does prevent changes to type -- particularly the
gross change of type that happens when that object’s memory is freed and
re-allocated for some other purpose. Once a type-safe reference to the
object is obtained, some other mechanism is needed to ensure consistent
access to the data in the object. This could involve taking a spinlock,
but with RCU the typical approach is to perform reads with SMP-aware
operations such as <code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">smp_load_acquire()</span></code>, to perform updates with atomic
read-modify-write operations, and to provide the necessary ordering.
RCU provides a number of support functions that embed the required
operations and ordering, such as the <a class="reference internal" href="../core-api/kernel-api.html#c.list_for_each_entry_rcu" title="list_for_each_entry_rcu"><code class="xref c c-func docutils literal notranslate"><span class="pre">list_for_each_entry_rcu()</span></code></a> macro
used in the previous section.</p>
<p>A more focused view of the reference counting behavior is that,
between <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> and <a class="reference internal" href="../core-api/kernel-api.html#c.rcu_read_unlock" title="rcu_read_unlock"><code class="xref c c-func docutils literal notranslate"><span class="pre">rcu_read_unlock()</span></code></a>, any reference taken with
<a class="reference internal" href="../core-api/kernel-api.html#c.rcu_dereference" title="rcu_dereference"><code class="xref c c-func docutils literal notranslate"><span class="pre">rcu_dereference()</span></code></a> on a pointer marked as <code class="docutils literal notranslate"><span class="pre">__rcu</span></code> can be treated as
though a reference-count on that object has been temporarily increased.
This prevents the object from changing type. Exactly what this means
will depend on normal expectations of objects of that type, but it
typically includes that spinlocks can still be safely locked, normal
reference counters can be safely manipulated, and <code class="docutils literal notranslate"><span class="pre">__rcu</span></code> pointers
can be safely dereferenced.</p>
<p>Some operations that one might expect to see on an object for
which an RCU reference is held include:</p>
<blockquote>
<div><ul class="simple">
<li><p>Copying out data that is guaranteed to be stable by the object’s type.</p></li>
<li><p>Using <a class="reference internal" href="../core-api/kref.html#c.kref_get_unless_zero" title="kref_get_unless_zero"><code class="xref c c-func docutils literal notranslate"><span class="pre">kref_get_unless_zero()</span></code></a> or similar to get a longer-term
reference. This may fail of course.</p></li>
<li><p>Acquiring a spinlock in the object, and checking if the object still
is the expected object and if so, manipulating it freely.</p></li>
</ul>
</div></blockquote>
<p>The understanding that RCU provides a reference that only prevents a
change of type is particularly visible with objects allocated from a
slab cache marked <code class="docutils literal notranslate"><span class="pre">SLAB_TYPESAFE_BY_RCU</span></code>. RCU operations may yield a
reference to an object from such a cache that has been concurrently freed
and the memory reallocated to a completely different object, though of
the same type. In this case RCU doesn’t even protect the identity of the
object from changing, only its type. So the object found may not be the
one expected, but it will be one where it is safe to take a reference
(and then potentially acquiring a spinlock), allowing subsequent code
to check whether the identity matches expectations. It is tempting
to simply acquire the spinlock without first taking the reference, but
unfortunately any spinlock in a <code class="docutils literal notranslate"><span class="pre">SLAB_TYPESAFE_BY_RCU</span></code> object must be
initialized after each and every call to <a class="reference internal" href="../core-api/mm-api.html#c.kmem_cache_alloc" title="kmem_cache_alloc"><code class="xref c c-func docutils literal notranslate"><span class="pre">kmem_cache_alloc()</span></code></a>, which renders
reference-free spinlock acquisition completely unsafe. Therefore, when
using <code class="docutils literal notranslate"><span class="pre">SLAB_TYPESAFE_BY_RCU</span></code>, make proper use of a reference counter.
If using refcount_t, the specialized refcount_{add|inc}<code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">_not_zero_acquire()</span></code>
and <a class="reference internal" href="../driver-api/basics.html#c.refcount_set_release" title="refcount_set_release"><code class="xref c c-func docutils literal notranslate"><span class="pre">refcount_set_release()</span></code></a> APIs should be used to ensure correct operation
ordering when verifying object identity and when initializing newly
allocated objects. Acquire fence in refcount_{add|inc}<code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">_not_zero_acquire()</span></code>
ensures that identity checks happen <em>after</em> reference count is taken.
<a class="reference internal" href="../driver-api/basics.html#c.refcount_set_release" title="refcount_set_release"><code class="xref c c-func docutils literal notranslate"><span class="pre">refcount_set_release()</span></code></a> should be called after a newly allocated object is
fully initialized and release fence ensures that new values are visible
<em>before</em> refcount can be successfully taken by other users. Once
<a class="reference internal" href="../driver-api/basics.html#c.refcount_set_release" title="refcount_set_release"><code class="xref c c-func docutils literal notranslate"><span class="pre">refcount_set_release()</span></code></a> is called, the object should be considered visible
by other tasks.
(Those willing to initialize their locks in a kmem_cache constructor
may also use locking, including cache-friendly sequence locking.)</p>
<p>With traditional reference counting -- such as that implemented by the
kref library in Linux -- there is typically code that runs when the last
reference to an object is dropped. With kref, this is the function
passed to <a class="reference internal" href="../core-api/kref.html#c.kref_put" title="kref_put"><code class="xref c c-func docutils literal notranslate"><span class="pre">kref_put()</span></code></a>. When RCU is being used, such finalization code
must not be run until all <code class="docutils literal notranslate"><span class="pre">__rcu</span></code> pointers referencing the object have
been updated, and then a grace period has passed. Every remaining
globally visible pointer to the object must be considered to be a
potential counted reference, and the finalization code is typically run
using <a class="reference internal" href="../core-api/kernel-api.html#c.call_rcu" title="call_rcu"><code class="xref c c-func docutils literal notranslate"><span class="pre">call_rcu()</span></code></a> only after all those pointers have been changed.</p>
<p>To see how to choose between these two analogies -- of RCU as a
reader-writer lock and RCU as a reference counting system -- it is useful
to reflect on the scale of the thing being protected. The reader-writer
lock analogy looks at larger multi-part objects such as a linked list
and shows how RCU can facilitate concurrency while elements are added
to, and removed from, the list. The reference-count analogy looks at
the individual objects and looks at how they can be accessed safely
within whatever whole they are a part of.</p>
</section>
<section id="full-list-of-rcu-apis">
<span id="id11"></span><h2>8. FULL LIST OF RCU APIs<a class="headerlink" href="#full-list-of-rcu-apis" title="Link to this heading">¶</a></h2>
<p>The RCU APIs are documented in docbook-format header comments in the
Linux-kernel source code, but it helps to have a full list of the
APIs, since there does not appear to be a way to categorize them
in docbook. Here is the list, by category.</p>
<p>RCU list traversal:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>list_entry_rcu
list_entry_lockless
list_first_entry_rcu
list_first_or_null_rcu
list_tail_rcu
list_next_rcu
list_next_or_null_rcu
list_for_each_entry_rcu
list_for_each_entry_continue_rcu
list_for_each_entry_from_rcu
list_for_each_entry_lockless
hlist_first_rcu
hlist_next_rcu
hlist_pprev_rcu
hlist_for_each_entry_rcu
hlist_for_each_entry_rcu_notrace
hlist_for_each_entry_rcu_bh
hlist_for_each_entry_from_rcu
hlist_for_each_entry_continue_rcu
hlist_for_each_entry_continue_rcu_bh
hlist_nulls_first_rcu
hlist_nulls_next_rcu
hlist_nulls_for_each_entry_rcu
hlist_nulls_for_each_entry_safe
hlist_bl_first_rcu
hlist_bl_for_each_entry_rcu
</pre></div>
</div>
<p>RCU pointer/list update:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>rcu_assign_pointer
rcu_replace_pointer
INIT_LIST_HEAD_RCU
list_add_rcu
list_add_tail_rcu
list_del_rcu
list_replace_rcu
list_splice_init_rcu
list_splice_tail_init_rcu
hlist_add_behind_rcu
hlist_add_before_rcu
hlist_add_head_rcu
hlist_add_tail_rcu
hlist_del_rcu
hlist_del_init_rcu
hlist_replace_rcu
hlist_nulls_del_init_rcu
hlist_nulls_del_rcu
hlist_nulls_add_head_rcu
hlist_nulls_add_tail_rcu
hlist_nulls_add_fake
hlists_swap_heads_rcu
hlist_bl_add_head_rcu
hlist_bl_del_rcu
hlist_bl_set_first_rcu
</pre></div>
</div>
<p>RCU:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>Critical sections Grace period Barrier
rcu_read_lock synchronize_net rcu_barrier
rcu_read_unlock synchronize_rcu
guard(rcu)() synchronize_rcu_expedited
scoped_guard(rcu) synchronize_rcu_mult
rcu_dereference call_rcu
rcu_dereference_check call_rcu_hurry
rcu_dereference_protected kfree_rcu
rcu_read_lock_held kvfree_rcu
rcu_read_lock_any_held kfree_rcu_mightsleep
rcu_pointer_handoff cond_synchronize_rcu
unrcu_pointer cond_synchronize_rcu_full
cond_synchronize_rcu_expedited
cond_synchronize_rcu_expedited_full
get_completed_synchronize_rcu
get_completed_synchronize_rcu_full
get_state_synchronize_rcu
get_state_synchronize_rcu_full
poll_state_synchronize_rcu
poll_state_synchronize_rcu_full
same_state_synchronize_rcu
same_state_synchronize_rcu_full
start_poll_synchronize_rcu
start_poll_synchronize_rcu_full
start_poll_synchronize_rcu_expedited
start_poll_synchronize_rcu_expedited_full
</pre></div>
</div>
<p>bh:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>Critical sections Grace period Barrier
rcu_read_lock_bh [Same as RCU] [Same as RCU]
rcu_read_unlock_bh
[local_bh_disable]
[and friends]
rcu_dereference_bh
rcu_dereference_bh_check
rcu_dereference_bh_protected
rcu_read_lock_bh_held
</pre></div>
</div>
<p>sched:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>Critical sections Grace period Barrier
rcu_read_lock_sched [Same as RCU] [Same as RCU]
rcu_read_unlock_sched
[preempt_disable]
[and friends]
rcu_read_lock_sched_notrace
rcu_read_unlock_sched_notrace
rcu_dereference_sched
rcu_dereference_sched_check
rcu_dereference_sched_protected
rcu_read_lock_sched_held
</pre></div>
</div>
<p>RCU: Initialization/cleanup/ordering:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>RCU_INIT_POINTER
RCU_INITIALIZER
RCU_POINTER_INITIALIZER
init_rcu_head
destroy_rcu_head
init_rcu_head_on_stack
destroy_rcu_head_on_stack
SLAB_TYPESAFE_BY_RCU
</pre></div>
</div>
<p>RCU: Quiescents states and control:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>cond_resched_tasks_rcu_qs
rcu_all_qs
rcu_softirq_qs_periodic
rcu_end_inkernel_boot
rcu_expedite_gp
rcu_gp_is_expedited
rcu_unexpedite_gp
rcu_cpu_stall_reset
rcu_head_after_call_rcu
rcu_is_watching
</pre></div>
</div>
<p>RCU-sync primitive:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>rcu_sync_is_idle
rcu_sync_init
rcu_sync_enter
rcu_sync_exit
rcu_sync_dtor
</pre></div>
</div>
<p>RCU-Tasks:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>Critical sections Grace period Barrier
N/A call_rcu_tasks rcu_barrier_tasks
synchronize_rcu_tasks
</pre></div>
</div>
<p>RCU-Tasks-Rude:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>Critical sections Grace period Barrier
N/A synchronize_rcu_tasks_rude rcu_barrier_tasks_rude
call_rcu_tasks_rude
</pre></div>
</div>
<p>RCU-Tasks-Trace:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>Critical sections Grace period Barrier
rcu_read_lock_trace call_rcu_tasks_trace rcu_barrier_tasks_trace
rcu_read_unlock_trace synchronize_rcu_tasks_trace
guard(rcu_tasks_trace)()
scoped_guard(rcu_tasks_trace)
</pre></div>
</div>
<dl class="simple">
<dt>SRCU list traversal::</dt><dd><p>list_for_each_entry_srcu
hlist_for_each_entry_srcu</p>
</dd>
</dl>
<p>SRCU:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>Critical sections Grace period Barrier
srcu_read_lock call_srcu srcu_barrier
srcu_read_unlock synchronize_srcu
srcu_read_lock_fast synchronize_srcu_expedited
srcu_read_unlock_fast get_state_synchronize_srcu
srcu_read_lock_nmisafe start_poll_synchronize_srcu
srcu_read_unlock_nmisafe start_poll_synchronize_srcu_expedited
srcu_read_lock_notrace poll_state_synchronize_srcu
srcu_read_unlock_notrace
srcu_down_read
srcu_up_read
srcu_down_read_fast
srcu_up_read_fast
guard(srcu)()
scoped_guard(srcu)
srcu_read_lock_held
srcu_dereference
srcu_dereference_check
srcu_dereference_notrace
srcu_read_lock_held
</pre></div>
</div>
<p>SRCU: Initialization/cleanup/ordering:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>DEFINE_SRCU
DEFINE_STATIC_SRCU
init_srcu_struct
cleanup_srcu_struct
smp_mb__after_srcu_read_unlock
</pre></div>
</div>
<p>All: lockdep-checked RCU utility APIs:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>RCU_LOCKDEP_WARN
rcu_sleep_check
</pre></div>
</div>
<p>All: Unchecked RCU-protected pointer access:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>rcu_dereference_raw
</pre></div>
</div>
<p>All: Unchecked RCU-protected pointer access with dereferencing prohibited:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>rcu_access_pointer
</pre></div>
</div>
<p>See the comment headers in the source code (or the docbook generated
from them) for more information.</p>
<p>However, given that there are no fewer than four families of RCU APIs
in the Linux kernel, how do you choose which one to use? The following
list can be helpful:</p>
<ol class="loweralpha simple">
<li><p>Will readers need to block? If so, you need SRCU.</p></li>
<li><p>Will readers need to block and are you doing tracing, for
example, ftrace or BPF? If so, you need RCU-tasks,
RCU-tasks-rude, and/or RCU-tasks-trace.</p></li>
<li><p>What about the -rt patchset? If readers would need to block in
an non-rt kernel, you need SRCU. If readers would block when
acquiring spinlocks in a -rt kernel, but not in a non-rt kernel,
SRCU is not necessary. (The -rt patchset turns spinlocks into
sleeplocks, hence this distinction.)</p></li>
<li><p>Do you need to treat NMI handlers, hardirq handlers,
and code segments with preemption disabled (whether
via <code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">preempt_disable()</span></code>, <code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">local_irq_save()</span></code>, <code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">local_bh_disable()</span></code>,
or some other mechanism) as if they were explicit RCU readers?
If so, RCU-sched readers are the only choice that will work
for you, but since about v4.20 you use can use the vanilla RCU
update primitives.</p></li>
<li><p>Do you need RCU grace periods to complete even in the face of
softirq monopolization of one or more of the CPUs? For example,
is your code subject to network-based denial-of-service attacks?
If so, you should disable softirq across your readers, for
example, by using <a class="reference internal" href="../core-api/kernel-api.html#c.rcu_read_lock_bh" title="rcu_read_lock_bh"><code class="xref c c-func docutils literal notranslate"><span class="pre">rcu_read_lock_bh()</span></code></a>. Since about v4.20 you
use can use the vanilla RCU update primitives.</p></li>
<li><p>Is your workload too update-intensive for normal use of
RCU, but inappropriate for other synchronization mechanisms?
If so, consider SLAB_TYPESAFE_BY_RCU (which was originally
named SLAB_DESTROY_BY_RCU). But please be careful!</p></li>
<li><p>Do you need read-side critical sections that are respected even
on CPUs that are deep in the idle loop, during entry to or exit
from user-mode execution, or on an offlined CPU? If so, SRCU
and RCU Tasks Trace are the only choices that will work for you,
with SRCU being strongly preferred in almost all cases.</p></li>
<li><p>Otherwise, use RCU.</p></li>
</ol>
<p>Of course, this all assumes that you have determined that RCU is in fact
the right tool for your job.</p>
</section>
<section id="answers-to-quick-quizzes">
<span id="id12"></span><h2>9. ANSWERS TO QUICK QUIZZES<a class="headerlink" href="#answers-to-quick-quizzes" title="Link to this heading">¶</a></h2>
<dl>
<dt>Quick Quiz #1:</dt><dd><p>Why is this argument naive? How could a deadlock
occur when using this algorithm in a real-world Linux
kernel? [Referring to the lock-based “toy” RCU
algorithm.]</p>
</dd>
<dt>Answer:</dt><dd><p>Consider the following sequence of events:</p>
<ol class="arabic simple">
<li><p>CPU 0 acquires some unrelated lock, call it
“problematic_lock”, disabling irq via
<code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">spin_lock_irqsave()</span></code>.</p></li>
<li><p>CPU 1 enters <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>, write-acquiring
rcu_gp_mutex.</p></li>
<li><p>CPU 0 enters <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>, but must wait
because CPU 1 holds rcu_gp_mutex.</p></li>
<li><p>CPU 1 is interrupted, and the irq handler
attempts to acquire problematic_lock.</p></li>
</ol>
<p>The system is now deadlocked.</p>
<p>One way to avoid this deadlock is to use an approach like
that of CONFIG_PREEMPT_RT, where all normal spinlocks
become blocking locks, and all irq handlers execute in
the context of special tasks. In this case, in step 4
above, the irq handler would block, allowing CPU 1 to
release rcu_gp_mutex, avoiding the deadlock.</p>
<p>Even in the absence of deadlock, this RCU implementation
allows latency to “bleed” from readers to other
readers through <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>. To see this,
consider task A in an RCU read-side critical section
(thus read-holding rcu_gp_mutex), task B blocked
attempting to write-acquire rcu_gp_mutex, and
task C blocked in <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> attempting to
read_acquire rcu_gp_mutex. Task A’s RCU read-side
latency is holding up task C, albeit indirectly via
task B.</p>
<p>Realtime RCU implementations therefore use a counter-based
approach where tasks in RCU read-side critical sections
cannot be blocked by tasks executing <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>.</p>
</dd>
</dl>
<p><a class="reference internal" href="#quiz-1"><span class="std std-ref">Back to Quick Quiz #1</span></a></p>
<dl>
<dt>Quick Quiz #2:</dt><dd><p>Give an example where Classic RCU’s read-side
overhead is <strong>negative</strong>.</p>
</dd>
<dt>Answer:</dt><dd><p>Imagine a single-CPU system with a non-CONFIG_PREEMPTION
kernel where a routing table is used by process-context
code, but can be updated by irq-context code (for example,
by an “ICMP REDIRECT” packet). The usual way of handling
this would be to have the process-context code disable
interrupts while searching the routing table. Use of
RCU allows such interrupt-disabling to be dispensed with.
Thus, without RCU, you pay the cost of disabling interrupts,
and with RCU you don’t.</p>
<p>One can argue that the overhead of RCU in this
case is negative with respect to the single-CPU
interrupt-disabling approach. Others might argue that
the overhead of RCU is merely zero, and that replacing
the positive overhead of the interrupt-disabling scheme
with the zero-overhead RCU scheme does not constitute
negative overhead.</p>
<p>In real life, of course, things are more complex. But
even the theoretical possibility of negative overhead for
a synchronization primitive is a bit unexpected. ;-)</p>
</dd>
</dl>
<p><a class="reference internal" href="#quiz-2"><span class="std std-ref">Back to Quick Quiz #2</span></a></p>
<dl>
<dt>Quick Quiz #3:</dt><dd><p>If it is illegal to block in an RCU read-side
critical section, what the heck do you do in
CONFIG_PREEMPT_RT, where normal spinlocks can block???</p>
</dd>
<dt>Answer:</dt><dd><p>Just as CONFIG_PREEMPT_RT permits preemption of spinlock
critical sections, it permits preemption of RCU
read-side critical sections. It also permits
spinlocks blocking while in RCU read-side critical
sections.</p>
<p>Why the apparent inconsistency? Because it is
possible to use priority boosting to keep the RCU
grace periods short if need be (for example, if running
short of memory). In contrast, if blocking waiting
for (say) network reception, there is no way to know
what should be boosted. Especially given that the
process we need to boost might well be a human being
who just went out for a pizza or something. And although
a computer-operated cattle prod might arouse serious
interest, it might also provoke serious objections.
Besides, how does the computer know what pizza parlor
the human being went to???</p>
</dd>
</dl>
<p><a class="reference internal" href="#quiz-3"><span class="std std-ref">Back to Quick Quiz #3</span></a></p>
<p>ACKNOWLEDGEMENTS</p>
<p>My thanks to the people who helped make this human-readable, including
Jon Walpole, Josh Triplett, Serge Hallyn, Suzanne Wood, and Alan Stern.</p>
<p>For more information, see <a class="reference external" href="http://www.rdrop.com/users/paulmck/RCU">http://www.rdrop.com/users/paulmck/RCU</a>.</p>
</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/RCU/whatisRCU.rst.txt"
rel="nofollow">Page source</a>
</div>
</body>
</html>