<!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>vlocks for Bare-Metal Mutual Exclusion — 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="Porting" href="porting.html" />
<link rel="prev" title="The Unified Extensible Firmware Interface (UEFI)" href="uefi.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>
<li class="toctree-l1"><a class="reference internal" href="../../core-api/index.html">Core API</a></li>
<li class="toctree-l1"><a class="reference internal" href="../../driver-api/index.html">Driver APIs</a></li>
<li class="toctree-l1"><a class="reference internal" href="../../subsystem-apis.html">Subsystems</a></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 class="current">
<li class="toctree-l1 current"><a class="reference internal" href="../index.html">CPU architectures</a><ul class="current">
<li class="toctree-l2"><a class="reference internal" href="../arc/index.html">ARC architecture</a></li>
<li class="toctree-l2 current"><a class="reference internal" href="index.html">ARM Architecture</a><ul class="current">
<li class="toctree-l3"><a class="reference internal" href="arm.html">ARM Linux 2.6 and upper</a></li>
<li class="toctree-l3"><a class="reference internal" href="booting.html">Booting ARM Linux</a></li>
<li class="toctree-l3"><a class="reference internal" href="cluster-pm-race-avoidance.html">Cluster-wide Power-up/power-down race avoidance algorithm</a></li>
<li class="toctree-l3"><a class="reference internal" href="firmware.html">Interface for registering and calling firmware-specific operations for ARM</a></li>
<li class="toctree-l3"><a class="reference internal" href="interrupts.html">Interrupts</a></li>
<li class="toctree-l3"><a class="reference internal" href="kernel_mode_neon.html">Kernel mode NEON</a></li>
<li class="toctree-l3"><a class="reference internal" href="kernel_user_helpers.html">Kernel-provided User Helpers</a></li>
<li class="toctree-l3"><a class="reference internal" href="memory.html">Kernel Memory Layout on ARM Linux</a></li>
<li class="toctree-l3"><a class="reference internal" href="mem_alignment.html">Memory alignment</a></li>
<li class="toctree-l3"><a class="reference internal" href="tcm.html">ARM TCM (Tightly-Coupled Memory) handling in Linux</a></li>
<li class="toctree-l3"><a class="reference internal" href="setup.html">Kernel initialisation parameters on ARM Linux</a></li>
<li class="toctree-l3"><a class="reference internal" href="swp_emulation.html">Software emulation of deprecated SWP instruction (CONFIG_SWP_EMULATE)</a></li>
<li class="toctree-l3"><a class="reference internal" href="uefi.html">The Unified Extensible Firmware Interface (UEFI)</a></li>
<li class="toctree-l3 current"><a class="current reference internal" href="#">vlocks for Bare-Metal Mutual Exclusion</a></li>
<li class="toctree-l3"><a class="reference internal" href="porting.html">Porting</a></li>
<li class="toctree-l3"><a class="reference internal" href="features.html">Feature status on arm architecture</a></li>
<li class="toctree-l3"><a class="reference internal" href="index.html#soc-specific-documents">SoC-specific documents</a></li>
</ul>
</li>
<li class="toctree-l2"><a class="reference internal" href="../arm64/index.html">ARM64 Architecture</a></li>
<li class="toctree-l2"><a class="reference internal" href="../loongarch/index.html">LoongArch Architecture</a></li>
<li class="toctree-l2"><a class="reference internal" href="../m68k/index.html">m68k Architecture</a></li>
<li class="toctree-l2"><a class="reference internal" href="../mips/index.html">MIPS-specific Documentation</a></li>
<li class="toctree-l2"><a class="reference internal" href="../nios2/index.html">Nios II Specific Documentation</a></li>
<li class="toctree-l2"><a class="reference internal" href="../openrisc/index.html">OpenRISC Architecture</a></li>
<li class="toctree-l2"><a class="reference internal" href="../parisc/index.html">PA-RISC Architecture</a></li>
<li class="toctree-l2"><a class="reference internal" href="../powerpc/index.html">powerpc</a></li>
<li class="toctree-l2"><a class="reference internal" href="../riscv/index.html">RISC-V architecture</a></li>
<li class="toctree-l2"><a class="reference internal" href="../s390/index.html">s390 Architecture</a></li>
<li class="toctree-l2"><a class="reference internal" href="../sh/index.html">SuperH Interfaces Guide</a></li>
<li class="toctree-l2"><a class="reference internal" href="../sparc/index.html">Sparc Architecture</a></li>
<li class="toctree-l2"><a class="reference internal" href="../x86/index.html">x86-specific Documentation</a></li>
<li class="toctree-l2"><a class="reference internal" href="../xtensa/index.html">Xtensa Architecture</a></li>
</ul>
</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/arch/arm/vlocks.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="vlocks-for-bare-metal-mutual-exclusion">
<h1>vlocks for Bare-Metal Mutual Exclusion<a class="headerlink" href="#vlocks-for-bare-metal-mutual-exclusion" title="Link to this heading">¶</a></h1>
<p>Voting Locks, or “vlocks” provide a simple low-level mutual exclusion
mechanism, with reasonable but minimal requirements on the memory
system.</p>
<p>These are intended to be used to coordinate critical activity among CPUs
which are otherwise non-coherent, in situations where the hardware
provides no other mechanism to support this and ordinary spinlocks
cannot be used.</p>
<p>vlocks make use of the atomicity provided by the memory system for
writes to a single memory location. To arbitrate, every CPU “votes for
itself”, by storing a unique number to a common memory location. The
final value seen in that memory location when all the votes have been
cast identifies the winner.</p>
<p>In order to make sure that the election produces an unambiguous result
in finite time, a CPU will only enter the election in the first place if
no winner has been chosen and the election does not appear to have
started yet.</p>
<section id="algorithm">
<h2>Algorithm<a class="headerlink" href="#algorithm" title="Link to this heading">¶</a></h2>
<p>The easiest way to explain the vlocks algorithm is with some pseudo-code:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>int currently_voting[NR_CPUS] = { 0, };
int last_vote = -1; /* no votes yet */
bool vlock_trylock(int this_cpu)
{
/* signal our desire to vote */
currently_voting[this_cpu] = 1;
if (last_vote != -1) {
/* someone already volunteered himself */
currently_voting[this_cpu] = 0;
return false; /* not ourself */
}
/* let's suggest ourself */
last_vote = this_cpu;
currently_voting[this_cpu] = 0;
/* then wait until everyone else is done voting */
for_each_cpu(i) {
while (currently_voting[i] != 0)
/* wait */;
}
/* result */
if (last_vote == this_cpu)
return true; /* we won */
return false;
}
bool vlock_unlock(void)
{
last_vote = -1;
}
</pre></div>
</div>
<p>The currently_voting[] array provides a way for the CPUs to determine
whether an election is in progress, and plays a role analogous to the
“entering” array in Lamport’s bakery algorithm [1].</p>
<p>However, once the election has started, the underlying memory system
atomicity is used to pick the winner. This avoids the need for a static
priority rule to act as a tie-breaker, or any counters which could
overflow.</p>
<p>As long as the last_vote variable is globally visible to all CPUs, it
will contain only one value that won’t change once every CPU has cleared
its currently_voting flag.</p>
</section>
<section id="features-and-limitations">
<h2>Features and limitations<a class="headerlink" href="#features-and-limitations" title="Link to this heading">¶</a></h2>
<blockquote>
<div><ul>
<li><p>vlocks are not intended to be fair. In the contended case, it is the
_last_ CPU which attempts to get the lock which will be most likely
to win.</p>
<p>vlocks are therefore best suited to situations where it is necessary
to pick a unique winner, but it does not matter which CPU actually
wins.</p>
</li>
<li><p>Like other similar mechanisms, vlocks will not scale well to a large
number of CPUs.</p>
<p>vlocks can be cascaded in a voting hierarchy to permit better scaling
if necessary, as in the following hypothetical example for 4096 CPUs:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>/* first level: local election */
my_town = towns[(this_cpu >> 4) & 0xf];
I_won = vlock_trylock(my_town, this_cpu & 0xf);
if (I_won) {
/* we won the town election, let's go for the state */
my_state = states[(this_cpu >> 8) & 0xf];
I_won = vlock_lock(my_state, this_cpu & 0xf));
if (I_won) {
/* and so on */
I_won = vlock_lock(the_whole_country, this_cpu & 0xf];
if (I_won) {
/* ... */
}
vlock_unlock(the_whole_country);
}
vlock_unlock(my_state);
}
vlock_unlock(my_town);
</pre></div>
</div>
</li>
</ul>
</div></blockquote>
</section>
<section id="arm-implementation">
<h2>ARM implementation<a class="headerlink" href="#arm-implementation" title="Link to this heading">¶</a></h2>
<p>The current ARM implementation [2] contains some optimisations beyond
the basic algorithm:</p>
<blockquote>
<div><ul>
<li><p>By packing the members of the currently_voting array close together,
we can read the whole array in one transaction (providing the number
of CPUs potentially contending the lock is small enough). This
reduces the number of round-trips required to external memory.</p>
<p>In the ARM implementation, this means that we can use a single load
and comparison:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>LDR Rt, [Rn]
CMP Rt, #0
</pre></div>
</div>
<p>...in place of code equivalent to:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>LDRB Rt, [Rn]
CMP Rt, #0
LDRBEQ Rt, [Rn, #1]
CMPEQ Rt, #0
LDRBEQ Rt, [Rn, #2]
CMPEQ Rt, #0
LDRBEQ Rt, [Rn, #3]
CMPEQ Rt, #0
</pre></div>
</div>
<p>This cuts down on the fast-path latency, as well as potentially
reducing bus contention in contended cases.</p>
<p>The optimisation relies on the fact that the ARM memory system
guarantees coherency between overlapping memory accesses of
different sizes, similarly to many other architectures. Note that
we do not care which element of currently_voting appears in which
bits of Rt, so there is no need to worry about endianness in this
optimisation.</p>
<p>If there are too many CPUs to read the currently_voting array in
one transaction then multiple transactions are still required. The
implementation uses a simple loop of word-sized loads for this
case. The number of transactions is still fewer than would be
required if bytes were loaded individually.</p>
<p>In principle, we could aggregate further by using LDRD or LDM, but
to keep the code simple this was not attempted in the initial
implementation.</p>
</li>
<li><p>vlocks are currently only used to coordinate between CPUs which are
unable to enable their caches yet. This means that the
implementation removes many of the barriers which would be required
when executing the algorithm in cached memory.</p>
<p>packing of the currently_voting array does not work with cached
memory unless all CPUs contending the lock are cache-coherent, due
to cache writebacks from one CPU clobbering values written by other
CPUs. (Though if all the CPUs are cache-coherent, you should be
probably be using proper spinlocks instead anyway).</p>
</li>
<li><p>The “no votes yet” value used for the last_vote variable is 0 (not
-1 as in the pseudocode). This allows statically-allocated vlocks
to be implicitly initialised to an unlocked state simply by putting
them in .bss.</p>
<p>An offset is added to each CPU’s ID for the purpose of setting this
variable, so that no CPU uses the value 0 for its ID.</p>
</li>
</ul>
</div></blockquote>
</section>
<section id="colophon">
<h2>Colophon<a class="headerlink" href="#colophon" title="Link to this heading">¶</a></h2>
<p>Originally created and documented by Dave Martin for Linaro Limited, for
use in ARM-based big.LITTLE platforms, with review and input gratefully
received from Nicolas Pitre and Achin Gupta. Thanks to Nicolas for
grabbing most of this text out of the relevant mail thread and writing
up the pseudocode.</p>
<p>Copyright (C) 2012-2013 Linaro Limited
Distributed under the terms of Version 2 of the GNU General Public
License, as defined in linux/COPYING.</p>
</section>
<section id="references">
<h2>References<a class="headerlink" href="#references" title="Link to this heading">¶</a></h2>
<dl>
<dt>[1] Lamport, L. “A New Solution of Dijkstra’s Concurrent Programming</dt><dd><p>Problem”, Communications of the ACM 17, 8 (August 1974), 453-455.</p>
<p><a class="reference external" href="https://en.wikipedia.org/wiki/Lamport%27s_bakery_algorithm">https://en.wikipedia.org/wiki/Lamport%27s_bakery_algorithm</a></p>
</dd>
</dl>
<p>[2] linux/arch/arm/common/vlock.S, www.kernel.org.</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/arch/arm/vlocks.rst.txt"
rel="nofollow">Page source</a>
</div>
</body>
</html>