1 ======================================
2 vlocks for Bare-Metal Mutual Exclusion
3 ======================================
5 Voting Locks, or "vlocks" provide a simple low-level mutual exclusion
6 mechanism, with reasonable but minimal requirements on the memory
9 These are intended to be used to coordinate critical activity among CPUs
10 which are otherwise non-coherent, in situations where the hardware
11 provides no other mechanism to support this and ordinary spinlocks
15 vlocks make use of the atomicity provided by the memory system for
16 writes to a single memory location. To arbitrate, every CPU "votes for
17 itself", by storing a unique number to a common memory location. The
18 final value seen in that memory location when all the votes have been
19 cast identifies the winner.
21 In order to make sure that the election produces an unambiguous result
22 in finite time, a CPU will only enter the election in the first place if
23 no winner has been chosen and the election does not appear to have
30 The easiest way to explain the vlocks algorithm is with some pseudo-code::
33 int currently_voting[NR_CPUS] = { 0, };
34 int last_vote = -1; /* no votes yet */
36 bool vlock_trylock(int this_cpu)
38 /* signal our desire to vote */
39 currently_voting[this_cpu] = 1;
40 if (last_vote != -1) {
41 /* someone already volunteered himself */
42 currently_voting[this_cpu] = 0;
43 return false; /* not ourself */
46 /* let's suggest ourself */
48 currently_voting[this_cpu] = 0;
50 /* then wait until everyone else is done voting */
52 while (currently_voting[i] != 0)
57 if (last_vote == this_cpu)
58 return true; /* we won */
62 bool vlock_unlock(void)
68 The currently_voting[] array provides a way for the CPUs to determine
69 whether an election is in progress, and plays a role analogous to the
70 "entering" array in Lamport's bakery algorithm [1].
72 However, once the election has started, the underlying memory system
73 atomicity is used to pick the winner. This avoids the need for a static
74 priority rule to act as a tie-breaker, or any counters which could
77 As long as the last_vote variable is globally visible to all CPUs, it
78 will contain only one value that won't change once every CPU has cleared
79 its currently_voting flag.
82 Features and limitations
83 ------------------------
85 * vlocks are not intended to be fair. In the contended case, it is the
86 _last_ CPU which attempts to get the lock which will be most likely
89 vlocks are therefore best suited to situations where it is necessary
90 to pick a unique winner, but it does not matter which CPU actually
93 * Like other similar mechanisms, vlocks will not scale well to a large
96 vlocks can be cascaded in a voting hierarchy to permit better scaling
97 if necessary, as in the following hypothetical example for 4096 CPUs::
99 /* first level: local election */
100 my_town = towns[(this_cpu >> 4) & 0xf];
101 I_won = vlock_trylock(my_town, this_cpu & 0xf);
103 /* we won the town election, let's go for the state */
104 my_state = states[(this_cpu >> 8) & 0xf];
105 I_won = vlock_lock(my_state, this_cpu & 0xf));
108 I_won = vlock_lock(the_whole_country, this_cpu & 0xf];
112 vlock_unlock(the_whole_country);
114 vlock_unlock(my_state);
116 vlock_unlock(my_town);
122 The current ARM implementation [2] contains some optimisations beyond
125 * By packing the members of the currently_voting array close together,
126 we can read the whole array in one transaction (providing the number
127 of CPUs potentially contending the lock is small enough). This
128 reduces the number of round-trips required to external memory.
130 In the ARM implementation, this means that we can use a single load
136 ...in place of code equivalent to::
147 This cuts down on the fast-path latency, as well as potentially
148 reducing bus contention in contended cases.
150 The optimisation relies on the fact that the ARM memory system
151 guarantees coherency between overlapping memory accesses of
152 different sizes, similarly to many other architectures. Note that
153 we do not care which element of currently_voting appears in which
154 bits of Rt, so there is no need to worry about endianness in this
157 If there are too many CPUs to read the currently_voting array in
158 one transaction then multiple transations are still required. The
159 implementation uses a simple loop of word-sized loads for this
160 case. The number of transactions is still fewer than would be
161 required if bytes were loaded individually.
164 In principle, we could aggregate further by using LDRD or LDM, but
165 to keep the code simple this was not attempted in the initial
169 * vlocks are currently only used to coordinate between CPUs which are
170 unable to enable their caches yet. This means that the
171 implementation removes many of the barriers which would be required
172 when executing the algorithm in cached memory.
174 packing of the currently_voting array does not work with cached
175 memory unless all CPUs contending the lock are cache-coherent, due
176 to cache writebacks from one CPU clobbering values written by other
177 CPUs. (Though if all the CPUs are cache-coherent, you should be
178 probably be using proper spinlocks instead anyway).
181 * The "no votes yet" value used for the last_vote variable is 0 (not
182 -1 as in the pseudocode). This allows statically-allocated vlocks
183 to be implicitly initialised to an unlocked state simply by putting
186 An offset is added to each CPU's ID for the purpose of setting this
187 variable, so that no CPU uses the value 0 for its ID.
193 Originally created and documented by Dave Martin for Linaro Limited, for
194 use in ARM-based big.LITTLE platforms, with review and input gratefully
195 received from Nicolas Pitre and Achin Gupta. Thanks to Nicolas for
196 grabbing most of this text out of the relevant mail thread and writing
199 Copyright (C) 2012-2013 Linaro Limited
200 Distributed under the terms of Version 2 of the GNU General Public
201 License, as defined in linux/COPYING.
207 [1] Lamport, L. "A New Solution of Dijkstra's Concurrent Programming
208 Problem", Communications of the ACM 17, 8 (August 1974), 453-455.
210 https://en.wikipedia.org/wiki/Lamport%27s_bakery_algorithm
212 [2] linux/arch/arm/common/vlock.S, www.kernel.org.