1 Locking
2 =======
3
4 Locking is well-known and the common use cases
5 CPU holding a given lock sees any changes prev
6 CPU before it previously released that same lo
7 is the only part of this document that most de
8
9 However, developers who would like to also acc
10 variables outside of their corresponding locks
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
19 or made by any CPU before it previousl
20
21 Note that this statement is a bit stronger tha
22 given lock sees all changes made by any CPU du
23 previously holding this same lock". For examp
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() acqui
44 then both r0 and r1 must be set to the value 1
45 consequence that if the final value of r0 is e
46 value of r1 must also be equal to 1. In contr
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: An
54 lock will not see any changes that will be mad
55 subsequently acquires this same lock. This co
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 tha
76 mylock before CPU1(), then both r0 and r1 must
77 This also has the consequence that if the fina
78 to 0, then the final value of r0 must also be
79 the weaker rule would say nothing about the fi
80
81 These examples show only a single pair of CPUs
82 locking basic rule extend across multiple acqu
83 across multiple CPUs.
84
85
86 Double-Checked Locking
87 ----------------------
88
89 It is well known that more than just a lock is
90 double-checked locking work correctly, This l
91 one incorrect approach:
92
93 /* See Documentation/litmus-tests/lock
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(dat
102 WRITE_ONCE(fla
103 }
104 spin_unlock(&lck);
105 }
106 r2 = READ_ONCE(data);
107 }
108 /* CPU1() is the exactly the same as C
109
110 There are two problems. First, there is no or
111 READ_ONCE() of "flag" and the READ_ONCE() of "
112 no ordering between the two WRITE_ONCE() calls
113 no surprise that "r2" can be zero, and a quick
114
115 One way to fix this is to use smp_load_acquire
116 as shown in this corrected version:
117
118 /* See Documentation/litmus-tests/lock
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(dat
127 smp_store_rele
128 }
129 spin_unlock(&lck);
130 }
131 r2 = READ_ONCE(data);
132 }
133 /* CPU1() is the exactly the same as C
134
135 The smp_load_acquire() guarantees that its loa
136 be ordered before the READ_ONCE() from data, t
137 problem. The smp_store_release() guarantees t
138 ordered after the WRITE_ONCE() to "data", solv
139 The smp_store_release() pairs with the smp_loa
140 that the ordering provided by each actually ta
141 quick herd7 run confirms this.
142
143 In short, if you access a lock-protected varia
144 corresponding lock, you will need to provide a
145 this case, via the smp_load_acquire() and the
146
147
148 Ordering Provided by a Lock to CPUs Not Holdin
149 ----------------------------------------------
150
151 It is not necessarily the case that accesses o
152 seen as ordered by CPUs not holding that lock.
153
154 /* See Z6.0+pooncelock+pooncelock+pomb
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 qu
179 the final value of r0 be 1, the final value of
180 value of r1 be 0. The reason for this surpris
181 never acquired the lock, and thus did not full
182 ordering properties.
183
184 Ordering can be extended to CPUs not holding t
185 of smp_mb__after_spinlock():
186
187 /* See Z6.0+pooncelock+poonceLock+pomb
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() stre
213 acquisition sufficiently to rule out the count
214 In other words, the addition of the smp_mb__af
215 the counter-intuitive result where the final v
216 value of z is 2, and the final value of r1 is
217
218
219 No Roach-Motel Locking!
220 -----------------------
221
222 This example requires familiarity with the her
223 please read up on that topic in litmus-tests.t
224
225 It is tempting to allow memory-reference instr
226 into a critical section, but this cannot be al
227 For example, consider a spin loop preceding a
228 Now, herd7 does not model spin loops, but we c
229 loads, with a "filter" clause to constrain the
230 initial value and the second to return the upd
231
232 /* See Documentation/litmus-tests/lock
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 t
254 CPU0() sets it to "1" while holding the lock,
255 spin loop by reading it twice, first into "1:r
256 initial value "0") and then into "1:r1" (which
257 value "1").
258
259 The "filter" clause takes this into account, c
260 equal "0" and "1:r1" to equal 1.
261
262 Then the "exists" clause checks to see if CPU1
263 which should not happen given the filter claus
264 "x" while holding the lock. And herd7 confirm
265
266 But suppose that the compiler was permitted to
267 into CPU1()'s critical section, like this:
268
269 /* See Documentation/litmus-tests/lock
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 eq
293 cannot update "x" while CPU1() holds the lock.
294 showing zero executions matching the "filter"
295
296 And this is why Linux-kernel lock and unlock p
297 code from entering critical sections. It is n
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.