1
2 On atomic types (atomic_t atomic64_t and atomi
3
4 The atomic type provides an interface to the a
5 RMW operations between CPUs (atomic operations
6 can lead to fatal traps on some platforms).
7
8 API
9 ---
10
11 The 'full' API consists of (atomic64_ and atom
12 brevity):
13
14 Non-RMW ops:
15
16 atomic_read(), atomic_set()
17 atomic_read_acquire(), atomic_set_release()
18
19
20 RMW atomic operations:
21
22 Arithmetic:
23
24 atomic_{add,sub,inc,dec}()
25 atomic_{add,sub,inc,dec}_return{,_relaxed,_a
26 atomic_fetch_{add,sub,inc,dec}{,_relaxed,_ac
27
28
29 Bitwise:
30
31 atomic_{and,or,xor,andnot}()
32 atomic_fetch_{and,or,xor,andnot}{,_relaxed,_
33
34
35 Swap:
36
37 atomic_xchg{,_relaxed,_acquire,_release}()
38 atomic_cmpxchg{,_relaxed,_acquire,_release}(
39 atomic_try_cmpxchg{,_relaxed,_acquire,_relea
40
41
42 Reference count (but please see refcount_t):
43
44 atomic_add_unless(), atomic_inc_not_zero()
45 atomic_sub_and_test(), atomic_dec_and_test()
46
47
48 Misc:
49
50 atomic_inc_and_test(), atomic_add_negative()
51 atomic_dec_unless_positive(), atomic_inc_unl
52
53
54 Barriers:
55
56 smp_mb__{before,after}_atomic()
57
58
59 TYPES (signed vs unsigned)
60 -----
61
62 While atomic_t, atomic_long_t and atomic64_t u
63 respectively (for hysterical raisins), the ker
64 (which implies -fwrapv) and defines signed ove
65 2s-complement.
66
67 Therefore, an explicitly unsigned variant of t
68 unnecessary and we can simply cast, there is n
69
70 There was a bug in UBSAN prior to GCC-8 that w
71 signed types.
72
73 With this we also conform to the C/C++ _Atomic
74 P1236R1.
75
76
77 SEMANTICS
78 ---------
79
80 Non-RMW ops:
81
82 The non-RMW ops are (typically) regular LOADs
83 implemented using READ_ONCE(), WRITE_ONCE(), s
84 smp_store_release() respectively. Therefore, i
85 the Non-RMW operations of atomic_t, you do not
86 and are doing it wrong.
87
88 A note for the implementation of atomic_set{}(
89 atomicity of the RMW ops. That is:
90
91 C Atomic-RMW-ops-are-atomic-WRT-atomic_set
92
93 {
94 atomic_t v = ATOMIC_INIT(1);
95 }
96
97 P0(atomic_t *v)
98 {
99 (void)atomic_add_unless(v, 1, 0);
100 }
101
102 P1(atomic_t *v)
103 {
104 atomic_set(v, 0);
105 }
106
107 exists
108 (v=2)
109
110 In this case we would expect the atomic_set()
111 before the atomic_add_unless(), in which case
112 _after_ in which case we'd overwrite its resul
113 outcome.
114
115 This is typically true on 'normal' platforms,
116 will invalidate a LL/SC or fail a CMPXCHG.
117
118 The obvious case where this is not so is when
119 with a lock:
120
121 CPU0
122
123 atomic_add_unless(v, 1, 0);
124 lock();
125 ret = READ_ONCE(v->counter); // == 1
126
127 if (ret != u)
128 WRITE_ONCE(v->counter, ret + 1);
129 unlock();
130
131 the typical solution is to then implement atom
132
133
134 RMW ops:
135
136 These come in various forms:
137
138 - plain operations without return value: atom
139
140 - operations which return the modified value:
141
142 these are limited to the arithmetic operati
143 reversible. Bitops are irreversible and the
144 is of dubious utility.
145
146 - operations which return the original value:
147
148 - swap operations: xchg(), cmpxchg() and try_
149
150 - misc; the special purpose operations that a
151 given the interface, normally be implemente
152 are time critical and can, (typically) on L
153 efficiently implemented.
154
155 All these operations are SMP atomic; that is,
156 atomic variable) can be fully ordered and no i
157 visible.
158
159
160 ORDERING (go read memory-barriers.txt first)
161 --------
162
163 The rule of thumb:
164
165 - non-RMW operations are unordered;
166
167 - RMW operations that have no return value ar
168
169 - RMW operations that have a return value are
170
171 - RMW operations that are conditional are uno
172 otherwise the above rules apply.
173
174 Except of course when a successful operation h
175
176 {}_relaxed: unordered
177 {}_acquire: the R of the RMW (or atomic_read)
178 {}_release: the W of the RMW (or atomic_set)
179
180 Where 'unordered' is against other memory loca
181 not defeated. Conditional operations are stil
182
183 Fully ordered primitives are ordered against e
184 subsequent. Therefore a fully ordered primitiv
185 before and an smp_mb() after the primitive.
186
187
188 The barriers:
189
190 smp_mb__{before,after}_atomic()
191
192 only apply to the RMW atomic ops and can be us
193 ordering inherent to the op. These barriers ac
194 smp_mb__before_atomic() orders all earlier acc
195 itself and all accesses following it, and smp_
196 later accesses against the RMW op and all acce
197 accesses between the smp_mb__{before,after}_at
198 ordered, so it is advisable to place the barri
199 op whenever possible.
200
201 These helper barriers exist because architectu
202 ordering on their SMP atomic primitives. For e
203 provide full ordered atomics and these barrier
204
205 NOTE: when the atomic RmW ops are fully ordere
206 compiler barrier.
207
208 Thus:
209
210 atomic_fetch_add();
211
212 is equivalent to:
213
214 smp_mb__before_atomic();
215 atomic_fetch_add_relaxed();
216 smp_mb__after_atomic();
217
218 However the atomic_fetch_add() might be implem
219
220 Further, while something like:
221
222 smp_mb__before_atomic();
223 atomic_dec(&X);
224
225 is a 'typical' RELEASE pattern, the barrier is
226 a RELEASE because it orders preceding instruct
227 and write parts of the atomic_dec(), and again
228 as well. Similarly, something like:
229
230 atomic_inc(&X);
231 smp_mb__after_atomic();
232
233 is an ACQUIRE pattern (though very much not ty
234 strictly stronger than ACQUIRE. As illustrated
235
236 C Atomic-RMW+mb__after_atomic-is-stronger-th
237
238 {
239 }
240
241 P0(int *x, atomic_t *y)
242 {
243 r0 = READ_ONCE(*x);
244 smp_rmb();
245 r1 = atomic_read(y);
246 }
247
248 P1(int *x, atomic_t *y)
249 {
250 atomic_inc(y);
251 smp_mb__after_atomic();
252 WRITE_ONCE(*x, 1);
253 }
254
255 exists
256 (0:r0=1 /\ 0:r1=0)
257
258 This should not happen; but a hypothetical ato
259 (void)atomic_fetch_inc_acquire() for instance
260 because it would not order the W part of the R
261 WRITE_ONCE. Thus:
262
263 P0 P1
264
265 t = LL.acq *y (0)
266 t++;
267 *x = 1;
268 r0 = *x (1)
269 RMB
270 r1 = *y (0)
271 SC *y, t;
272
273 is allowed.
274
275
276 CMPXCHG vs TRY_CMPXCHG
277 ----------------------
278
279 int atomic_cmpxchg(atomic_t *ptr, int old, i
280 bool atomic_try_cmpxchg(atomic_t *ptr, int *
281
282 Both provide the same functionality, but try_c
283 compact code. The functions relate like:
284
285 bool atomic_try_cmpxchg(atomic_t *ptr, int *
286 {
287 int ret, old = *oldp;
288 ret = atomic_cmpxchg(ptr, old, new);
289 if (ret != old)
290 *oldp = ret;
291 return ret == old;
292 }
293
294 and:
295
296 int atomic_cmpxchg(atomic_t *ptr, int old, i
297 {
298 (void)atomic_try_cmpxchg(ptr, &old, new);
299 return old;
300 }
301
302 Usage:
303
304 old = atomic_read(&v);
305 for (;;) {
306 new = func(old);
307 tmp = atomic_cmpxchg(&v, old, new);
308 if (tmp == old)
309 break;
310 old = tmp;
311 }
312
313 NB. try_cmpxchg() also generates better code o
314 where the function more closely matches the ha
315
316
317 FORWARD PROGRESS
318 ----------------
319
320 In general strong forward progress is expected
321 operations -- those in the Arithmetic and Bitw
322 a fair amount of code also requires forward pr
323 atomic operations.
324
325 Specifically 'simple' cmpxchg() loops are expe
326 indefinitely. However, this is not evident on
327 while an LL/SC architecture 'can/should/must'
328 guarantees between competing LL/SC sections, s
329 transfer to cmpxchg() implemented using LL/SC.
330
331 old = atomic_read(&v);
332 do {
333 new = func(old);
334 } while (!atomic_try_cmpxchg(&v, &old, new))
335
336 which on LL/SC becomes something like:
337
338 old = atomic_read(&v);
339 do {
340 new = func(old);
341 } while (!({
342 volatile asm ("1: LL %[oldval], %[v]\n"
343 " CMP %[oldval], %[old]\n"
344 " BNE 2f\n"
345 " SC %[new], %[v]\n"
346 " BNE 1b\n"
347 "2:\n"
348 : [oldval] "=&r" (oldval), [
349 : [old] "r" (old), [new] "r"
350 : "memory");
351 success = (oldval == old);
352 if (!success)
353 old = oldval;
354 success; }));
355
356 However, even the forward branch from the fail
357 to fail on some architectures, let alone whate
358 loop body. As a result there is no guarantee w
359 containing @v will stay on the local CPU and p
360
361 Even native CAS architectures can fail to prov
362 primitive (See Sparc64 for an example).
363
364 Such implementations are strongly encouraged t
365 to a failed CAS in order to ensure some progre
366 also strongly encouraged to inspect/audit the
367 their locking primitives.
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.