1 Locking
2 =======
3
4 Locking is well-known and the common use cases are straightforward: Any
5 CPU holding a given lock sees any changes previously seen or made by any
6 CPU before it previously released that same lock. This last sentence
7 is the only part of this document that most developers will need to read.
8
9 However, developers who would like to also access lock-protected shared
10 variables outside of their corresponding locks should continue reading.
11
12
13 Locking and Prior Accesses
14 --------------------------
15
16 The basic rule of locking is worth repeating:
17
18 Any CPU holding a given lock sees any changes previously seen
19 or made by any CPU before it previously released that same lock.
20
21 Note that this statement is a bit stronger than "Any CPU holding a
22 given lock sees all changes made by any CPU during the time that CPU was
23 previously holding this same lock". For example, consider the following
24 pair of code fragments:
25
26 /* See MP+polocks.litmus. */
27 void CPU0(void)
28 {
29 WRITE_ONCE(x, 1);
30 spin_lock(&mylock);
31 WRITE_ONCE(y, 1);
32 spin_unlock(&mylock);
33 }
34
35 void CPU1(void)
36 {
37 spin_lock(&mylock);
38 r0 = READ_ONCE(y);
39 spin_unlock(&mylock);
40 r1 = READ_ONCE(x);
41 }
42
43 The basic rule guarantees that if CPU0() acquires mylock before CPU1(),
44 then both r0 and r1 must be set to the value 1. This also has the
45 consequence that if the final value of r0 is equal to 1, then the final
46 value of r1 must also be equal to 1. In contrast, the weaker rule would
47 say nothing about the final value of r1.
48
49
50 Locking and Subsequent Accesses
51 -------------------------------
52
53 The converse to the basic rule also holds: Any CPU holding a given
54 lock will not see any changes that will be made by any CPU after it
55 subsequently acquires this same lock. This converse statement is
56 illustrated by the following litmus test:
57
58 /* See MP+porevlocks.litmus. */
59 void CPU0(void)
60 {
61 r0 = READ_ONCE(y);
62 spin_lock(&mylock);
63 r1 = READ_ONCE(x);
64 spin_unlock(&mylock);
65 }
66
67 void CPU1(void)
68 {
69 spin_lock(&mylock);
70 WRITE_ONCE(x, 1);
71 spin_unlock(&mylock);
72 WRITE_ONCE(y, 1);
73 }
74
75 This converse to the basic rule guarantees that if CPU0() acquires
76 mylock before CPU1(), then both r0 and r1 must be set to the value 0.
77 This also has the consequence that if the final value of r1 is equal
78 to 0, then the final value of r0 must also be equal to 0. In contrast,
79 the weaker rule would say nothing about the final value of r0.
80
81 These examples show only a single pair of CPUs, but the effects of the
82 locking basic rule extend across multiple acquisitions of a given lock
83 across multiple CPUs.
84
85
86 Double-Checked Locking
87 ----------------------
88
89 It is well known that more than just a lock is required to make
90 double-checked locking work correctly, This litmus test illustrates
91 one incorrect approach:
92
93 /* See Documentation/litmus-tests/locking/DCL-broken.litmus. */
94 void CPU0(void)
95 {
96 r0 = READ_ONCE(flag);
97 if (r0 == 0) {
98 spin_lock(&lck);
99 r1 = READ_ONCE(flag);
100 if (r1 == 0) {
101 WRITE_ONCE(data, 1);
102 WRITE_ONCE(flag, 1);
103 }
104 spin_unlock(&lck);
105 }
106 r2 = READ_ONCE(data);
107 }
108 /* CPU1() is the exactly the same as CPU0(). */
109
110 There are two problems. First, there is no ordering between the first
111 READ_ONCE() of "flag" and the READ_ONCE() of "data". Second, there is
112 no ordering between the two WRITE_ONCE() calls. It should therefore be
113 no surprise that "r2" can be zero, and a quick herd7 run confirms this.
114
115 One way to fix this is to use smp_load_acquire() and smp_store_release()
116 as shown in this corrected version:
117
118 /* See Documentation/litmus-tests/locking/DCL-fixed.litmus. */
119 void CPU0(void)
120 {
121 r0 = smp_load_acquire(&flag);
122 if (r0 == 0) {
123 spin_lock(&lck);
124 r1 = READ_ONCE(flag);
125 if (r1 == 0) {
126 WRITE_ONCE(data, 1);
127 smp_store_release(&flag, 1);
128 }
129 spin_unlock(&lck);
130 }
131 r2 = READ_ONCE(data);
132 }
133 /* CPU1() is the exactly the same as CPU0(). */
134
135 The smp_load_acquire() guarantees that its load from "flags" will
136 be ordered before the READ_ONCE() from data, thus solving the first
137 problem. The smp_store_release() guarantees that its store will be
138 ordered after the WRITE_ONCE() to "data", solving the second problem.
139 The smp_store_release() pairs with the smp_load_acquire(), thus ensuring
140 that the ordering provided by each actually takes effect. Again, a
141 quick herd7 run confirms this.
142
143 In short, if you access a lock-protected variable without holding the
144 corresponding lock, you will need to provide additional ordering, in
145 this case, via the smp_load_acquire() and the smp_store_release().
146
147
148 Ordering Provided by a Lock to CPUs Not Holding That Lock
149 ---------------------------------------------------------
150
151 It is not necessarily the case that accesses ordered by locking will be
152 seen as ordered by CPUs not holding that lock. Consider this example:
153
154 /* See Z6.0+pooncelock+pooncelock+pombonce.litmus. */
155 void CPU0(void)
156 {
157 spin_lock(&mylock);
158 WRITE_ONCE(x, 1);
159 WRITE_ONCE(y, 1);
160 spin_unlock(&mylock);
161 }
162
163 void CPU1(void)
164 {
165 spin_lock(&mylock);
166 r0 = READ_ONCE(y);
167 WRITE_ONCE(z, 1);
168 spin_unlock(&mylock);
169 }
170
171 void CPU2(void)
172 {
173 WRITE_ONCE(z, 2);
174 smp_mb();
175 r1 = READ_ONCE(x);
176 }
177
178 Counter-intuitive though it might be, it is quite possible to have
179 the final value of r0 be 1, the final value of z be 2, and the final
180 value of r1 be 0. The reason for this surprising outcome is that CPU2()
181 never acquired the lock, and thus did not fully benefit from the lock's
182 ordering properties.
183
184 Ordering can be extended to CPUs not holding the lock by careful use
185 of smp_mb__after_spinlock():
186
187 /* See Z6.0+pooncelock+poonceLock+pombonce.litmus. */
188 void CPU0(void)
189 {
190 spin_lock(&mylock);
191 WRITE_ONCE(x, 1);
192 WRITE_ONCE(y, 1);
193 spin_unlock(&mylock);
194 }
195
196 void CPU1(void)
197 {
198 spin_lock(&mylock);
199 smp_mb__after_spinlock();
200 r0 = READ_ONCE(y);
201 WRITE_ONCE(z, 1);
202 spin_unlock(&mylock);
203 }
204
205 void CPU2(void)
206 {
207 WRITE_ONCE(z, 2);
208 smp_mb();
209 r1 = READ_ONCE(x);
210 }
211
212 This addition of smp_mb__after_spinlock() strengthens the lock
213 acquisition sufficiently to rule out the counter-intuitive outcome.
214 In other words, the addition of the smp_mb__after_spinlock() prohibits
215 the counter-intuitive result where the final value of r0 is 1, the final
216 value of z is 2, and the final value of r1 is 0.
217
218
219 No Roach-Motel Locking!
220 -----------------------
221
222 This example requires familiarity with the herd7 "filter" clause, so
223 please read up on that topic in litmus-tests.txt.
224
225 It is tempting to allow memory-reference instructions to be pulled
226 into a critical section, but this cannot be allowed in the general case.
227 For example, consider a spin loop preceding a lock-based critical section.
228 Now, herd7 does not model spin loops, but we can emulate one with two
229 loads, with a "filter" clause to constrain the first to return the
230 initial value and the second to return the updated value, as shown below:
231
232 /* See Documentation/litmus-tests/locking/RM-fixed.litmus. */
233 void CPU0(void)
234 {
235 spin_lock(&lck);
236 r2 = atomic_inc_return(&y);
237 WRITE_ONCE(x, 1);
238 spin_unlock(&lck);
239 }
240
241 void CPU1(void)
242 {
243 r0 = READ_ONCE(x);
244 r1 = READ_ONCE(x);
245 spin_lock(&lck);
246 r2 = atomic_inc_return(&y);
247 spin_unlock(&lck);
248 }
249
250 filter (1:r0=0 /\ 1:r1=1)
251 exists (1:r2=1)
252
253 The variable "x" is the control variable for the emulated spin loop.
254 CPU0() sets it to "1" while holding the lock, and CPU1() emulates the
255 spin loop by reading it twice, first into "1:r0" (which should get the
256 initial value "0") and then into "1:r1" (which should get the updated
257 value "1").
258
259 The "filter" clause takes this into account, constraining "1:r0" to
260 equal "0" and "1:r1" to equal 1.
261
262 Then the "exists" clause checks to see if CPU1() acquired its lock first,
263 which should not happen given the filter clause because CPU0() updates
264 "x" while holding the lock. And herd7 confirms this.
265
266 But suppose that the compiler was permitted to reorder the spin loop
267 into CPU1()'s critical section, like this:
268
269 /* See Documentation/litmus-tests/locking/RM-broken.litmus. */
270 void CPU0(void)
271 {
272 int r2;
273
274 spin_lock(&lck);
275 r2 = atomic_inc_return(&y);
276 WRITE_ONCE(x, 1);
277 spin_unlock(&lck);
278 }
279
280 void CPU1(void)
281 {
282 spin_lock(&lck);
283 r0 = READ_ONCE(x);
284 r1 = READ_ONCE(x);
285 r2 = atomic_inc_return(&y);
286 spin_unlock(&lck);
287 }
288
289 filter (1:r0=0 /\ 1:r1=1)
290 exists (1:r2=1)
291
292 If "1:r0" is equal to "0", "1:r1" can never equal "1" because CPU0()
293 cannot update "x" while CPU1() holds the lock. And herd7 confirms this,
294 showing zero executions matching the "filter" criteria.
295
296 And this is why Linux-kernel lock and unlock primitives must prevent
297 code from entering critical sections. It is not sufficient to only
298 prevent code from leaving them.
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.