blob: 913396ac582431cb3acbdc96a1bd7f4293661d0b [file] [log] [blame]
Peter Zijlstra706eeb32017-06-12 14:50:27 +02001
2On atomic types (atomic_t atomic64_t and atomic_long_t).
3
4The atomic type provides an interface to the architecture's means of atomic
5RMW operations between CPUs (atomic operations on MMIO are not supported and
6can lead to fatal traps on some platforms).
7
8API
9---
10
11The 'full' API consists of (atomic64_ and atomic_long_ prefixes omitted for
12brevity):
13
14Non-RMW ops:
15
16 atomic_read(), atomic_set()
17 atomic_read_acquire(), atomic_set_release()
18
19
20RMW atomic operations:
21
22Arithmetic:
23
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}()
27
28
29Bitwise:
30
31 atomic_{and,or,xor,andnot}()
32 atomic_fetch_{and,or,xor,andnot}{,_relaxed,_acquire,_release}()
33
34
35Swap:
36
37 atomic_xchg{,_relaxed,_acquire,_release}()
38 atomic_cmpxchg{,_relaxed,_acquire,_release}()
39 atomic_try_cmpxchg{,_relaxed,_acquire,_release}()
40
41
42Reference 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
48Misc:
49
50 atomic_inc_and_test(), atomic_add_negative()
51 atomic_dec_unless_positive(), atomic_inc_unless_negative()
52
53
54Barriers:
55
56 smp_mb__{before,after}_atomic()
57
58
59
60SEMANTICS
61---------
62
63Non-RMW ops:
64
65The non-RMW ops are (typically) regular LOADs and STOREs and are canonically
66implemented using READ_ONCE(), WRITE_ONCE(), smp_load_acquire() and
67smp_store_release() respectively.
68
69The one detail to this is that atomic_set{}() should be observable to the RMW
70ops. That is:
71
72 C atomic-set
73
74 {
75 atomic_set(v, 1);
76 }
77
78 P1(atomic_t *v)
79 {
80 atomic_add_unless(v, 1, 0);
81 }
82
83 P2(atomic_t *v)
84 {
85 atomic_set(v, 0);
86 }
87
88 exists
89 (v=2)
90
91In this case we would expect the atomic_set() from CPU1 to either happen
92before 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
94outcome.
95
96This is typically true on 'normal' platforms, where a regular competing STORE
97will invalidate a LL/SC or fail a CMPXCHG.
98
99The obvious case where this is not so is when we need to implement atomic ops
100with a lock:
101
102 CPU0 CPU1
103
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();
111
112the typical solution is to then implement atomic_set{}() with atomic_xchg().
113
114
115RMW ops:
116
117These come in various forms:
118
119 - plain operations without return value: atomic_{}()
120
121 - operations which return the modified value: atomic_{}_return()
122
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.
126
127 - operations which return the original value: atomic_fetch_{}()
128
129 - swap operations: xchg(), cmpxchg() and try_cmpxchg()
130
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.
135
136All these operations are SMP atomic; that is, the operations (for a single
137atomic variable) can be fully ordered and no intermediate state is lost or
138visible.
139
140
141ORDERING (go read memory-barriers.txt first)
142--------
143
144The rule of thumb:
145
146 - non-RMW operations are unordered;
147
148 - RMW operations that have no return value are unordered;
149
150 - RMW operations that have a return value are fully ordered;
151
152 - RMW operations that are conditional are unordered on FAILURE,
153 otherwise the above rules apply.
154
155Except of course when an operation has an explicit ordering like:
156
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
160
161Where 'unordered' is against other memory locations. Address dependencies are
162not defeated.
163
164Fully ordered primitives are ordered against everything prior and everything
165subsequent. Therefore a fully ordered primitive is like having an smp_mb()
166before and an smp_mb() after the primitive.
167
168
169The barriers:
170
171 smp_mb__{before,after}_atomic()
172
173only apply to the RMW ops and can be used to augment/upgrade the ordering
174inherent to the used atomic op. These barriers provide a full smp_mb().
175
176These helper barriers exist because architectures have varying implicit
177ordering on their SMP atomic primitives. For example our TSO architectures
178provide full ordered atomics and these barriers are no-ops.
179
180Thus:
181
182 atomic_fetch_add();
183
184is equivalent to:
185
186 smp_mb__before_atomic();
187 atomic_fetch_add_relaxed();
188 smp_mb__after_atomic();
189
190However the atomic_fetch_add() might be implemented more efficiently.
191
192Further, while something like:
193
194 smp_mb__before_atomic();
195 atomic_dec(&X);
196
197is a 'typical' RELEASE pattern, the barrier is strictly stronger than
198a RELEASE. Similarly for something like:
199
Peter Zijlstraca110692017-08-23 18:15:20 +0200200 atomic_inc(&X);
201 smp_mb__after_atomic();
Peter Zijlstra706eeb32017-06-12 14:50:27 +0200202
Peter Zijlstraca110692017-08-23 18:15:20 +0200203is an ACQUIRE pattern (though very much not typical), but again the barrier is
204strictly stronger than ACQUIRE. As illustrated:
205
206 C strong-acquire
207
208 {
209 }
210
211 P1(int *x, atomic_t *y)
212 {
213 r0 = READ_ONCE(*x);
214 smp_rmb();
215 r1 = atomic_read(y);
216 }
217
218 P2(int *x, atomic_t *y)
219 {
220 atomic_inc(y);
221 smp_mb__after_atomic();
222 WRITE_ONCE(*x, 1);
223 }
224
225 exists
226 (r0=1 /\ r1=0)
227
228This should not happen; but a hypothetical atomic_inc_acquire() --
229(void)atomic_fetch_inc_acquire() for instance -- would allow the outcome,
230since then:
231
232 P1 P2
233
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;
241
242is allowed.