2 On atomic types (atomic_t atomic64_t and atomic_long_t).
4 The atomic type provides an interface to the architecture's means of atomic
5 RMW operations between CPUs (atomic operations on MMIO are not supported and
6 can lead to fatal traps on some platforms).
8 API
9 ---
11 The 'full' API consists of (atomic64_ and atomic_long_ prefixes omitted for
12 brevity):
14 Non-RMW ops:
16 atomic_read(), atomic_set()
17 atomic_read_acquire(), atomic_set_release()
20 RMW atomic operations:
22 Arithmetic:
24 atomic_{add,sub,inc,dec}()
25 atomic_{add,sub,inc,dec}_return{,_relaxed,_acquire,_release}()
26 atomic_fetch_{add,sub,inc,dec}{,_relaxed,_acquire,_release}()
29 Bitwise:
31 atomic_{and,or,xor,andnot}()
32 atomic_fetch_{and,or,xor,andnot}{,_relaxed,_acquire,_release}()
35 Swap:
37 atomic_xchg{,_relaxed,_acquire,_release}()
38 atomic_cmpxchg{,_relaxed,_acquire,_release}()
39 atomic_try_cmpxchg{,_relaxed,_acquire,_release}()
42 Reference count (but please see refcount_t):
44 atomic_add_unless(), atomic_inc_not_zero()
45 atomic_sub_and_test(), atomic_dec_and_test()
48 Misc:
50 atomic_inc_and_test(), atomic_add_negative()
51 atomic_dec_unless_positive(), atomic_inc_unless_negative()
54 Barriers:
56 smp_mb__{before,after}_atomic()
60 SEMANTICS
61 ---------
63 Non-RMW ops:
65 The non-RMW ops are (typically) regular LOADs and STOREs and are canonically
66 implemented using READ_ONCE(), WRITE_ONCE(), smp_load_acquire() and
67 smp_store_release() respectively.
69 The one detail to this is that atomic_set{}() should be observable to the RMW
70 ops. That is:
72 C atomic-set
74 {
75 atomic_set(v, 1);
76 }
78 P1(atomic_t *v)
79 {
80 atomic_add_unless(v, 1, 0);
81 }
83 P2(atomic_t *v)
84 {
85 atomic_set(v, 0);
86 }
88 exists
89 (v=2)
91 In this case we would expect the atomic_set() from CPU1 to either happen
92 before the atomic_add_unless(), in which case that latter one would no-op, or
93 _after_ in which case we'd overwrite its result. In no case is "2" a valid
94 outcome.
96 This is typically true on 'normal' platforms, where a regular competing STORE
97 will invalidate a LL/SC or fail a CMPXCHG.
99 The obvious case where this is not so is when we need to implement atomic ops
100 with a lock:
102 CPU0 CPU1
104 atomic_add_unless(v, 1, 0);
105 lock();
106 ret = READ_ONCE(v->counter); // == 1
107 atomic_set(v, 0);
108 if (ret != u) WRITE_ONCE(v->counter, 0);
109 WRITE_ONCE(v->counter, ret + 1);
110 unlock();
112 the typical solution is to then implement atomic_set{}() with atomic_xchg().
115 RMW ops:
117 These come in various forms:
119 - plain operations without return value: atomic_{}()
121 - operations which return the modified value: atomic_{}_return()
123 these are limited to the arithmetic operations because those are
124 reversible. Bitops are irreversible and therefore the modified value
125 is of dubious utility.
127 - operations which return the original value: atomic_fetch_{}()
129 - swap operations: xchg(), cmpxchg() and try_cmpxchg()
131 - misc; the special purpose operations that are commonly used and would,
132 given the interface, normally be implemented using (try_)cmpxchg loops but
133 are time critical and can, (typically) on LL/SC architectures, be more
134 efficiently implemented.
136 All these operations are SMP atomic; that is, the operations (for a single
137 atomic variable) can be fully ordered and no intermediate state is lost or
138 visible.
141 ORDERING (go read memory-barriers.txt first)
142 --------
144 The rule of thumb:
146 - non-RMW operations are unordered;
148 - RMW operations that have no return value are unordered;
150 - RMW operations that have a return value are fully ordered;
152 - RMW operations that are conditional are unordered on FAILURE,
153 otherwise the above rules apply.
155 Except of course when an operation has an explicit ordering like:
157 {}_relaxed: unordered
158 {}_acquire: the R of the RMW (or atomic_read) is an ACQUIRE
159 {}_release: the W of the RMW (or atomic_set) is a RELEASE
161 Where 'unordered' is against other memory locations. Address dependencies are
162 not defeated.
164 Fully ordered primitives are ordered against everything prior and everything
165 subsequent. Therefore a fully ordered primitive is like having an smp_mb()
166 before and an smp_mb() after the primitive.
169 The barriers:
171 smp_mb__{before,after}_atomic()
173 only apply to the RMW ops and can be used to augment/upgrade the ordering
174 inherent to the used atomic op. These barriers provide a full smp_mb().
176 These helper barriers exist because architectures have varying implicit
177 ordering on their SMP atomic primitives. For example our TSO architectures
178 provide full ordered atomics and these barriers are no-ops.
180 Thus:
182 atomic_fetch_add();
184 is equivalent to:
186 smp_mb__before_atomic();
187 atomic_fetch_add_relaxed();
188 smp_mb__after_atomic();
190 However the atomic_fetch_add() might be implemented more efficiently.
192 Further, while something like:
194 smp_mb__before_atomic();
195 atomic_dec(&X);
197 is a 'typical' RELEASE pattern, the barrier is strictly stronger than
198 a RELEASE. Similarly for something like:
200 atomic_inc(&X);
201 smp_mb__after_atomic();
203 is an ACQUIRE pattern (though very much not typical), but again the barrier is
204 strictly stronger than ACQUIRE. As illustrated:
206 C strong-acquire
208 {
209 }
211 P1(int *x, atomic_t *y)
212 {
213 r0 = READ_ONCE(*x);
214 smp_rmb();
215 r1 = atomic_read(y);
216 }
218 P2(int *x, atomic_t *y)
219 {
220 atomic_inc(y);
221 smp_mb__after_atomic();
222 WRITE_ONCE(*x, 1);
223 }
225 exists
226 (r0=1 /\ r1=0)
228 This should not happen; but a hypothetical atomic_inc_acquire() --
229 (void)atomic_fetch_inc_acquire() for instance -- would allow the outcome,
230 since then:
232 P1 P2
234 t = LL.acq *y (0)
235 t++;
236 *x = 1;
237 r0 = *x (1)
238 RMB
239 r1 = *y (0)
240 SC *y, t;
242 is allowed.