Documentation/atomic_t.txt

   1
   2 On atomic types (atomic_t atomic64_t and atomic_long_t).
   3
   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).
   7
   8 API
   9 ---
  10
  11 The 'full' API consists of (atomic64_ and atomic_long_ prefixes omitted for
  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,_acquire,_release}()
  26   atomic_fetch_{add,sub,inc,dec}{,_relaxed,_acquire,_release}()
  27
  28
  29 Bitwise:
  30
  31   atomic_{and,or,xor,andnot}()
  32   atomic_fetch_{and,or,xor,andnot}{,_relaxed,_acquire,_release}()
  33
  34
  35 Swap:
  36
  37   atomic_xchg{,_relaxed,_acquire,_release}()
  38   atomic_cmpxchg{,_relaxed,_acquire,_release}()
  39   atomic_try_cmpxchg{,_relaxed,_acquire,_release}()
  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_unless_negative()
  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 use int, long and s64
  63 respectively (for hysterical raisins), the kernel uses -fno-strict-overflow
  64 (which implies -fwrapv) and defines signed overflow to behave like
  65 2s-complement.
  66
  67 Therefore, an explicitly unsigned variant of the atomic ops is strictly
  68 unnecessary and we can simply cast, there is no UB.
  69
  70 There was a bug in UBSAN prior to GCC-8 that would generate UB warnings for
  71 signed types.
  72
  73 With this we also conform to the C/C++ _Atomic behaviour and things like
  74 P1236R1.
  75
  76
  77 SEMANTICS
  78 ---------
  79
  80 Non-RMW ops:
  81
  82 The non-RMW ops are (typically) regular LOADs and STOREs and are canonically
  83 implemented using READ_ONCE(), WRITE_ONCE(), smp_load_acquire() and
  84 smp_store_release() respectively.
  85
  86 The one detail to this is that atomic_set{}() should be observable to the RMW
  87 ops. That is:
  88
  89   C atomic-set
  90
  91   {
  92     atomic_set(v, 1);
  93   }
  94
  95   P1(atomic_t *v)
  96   {
  97     atomic_add_unless(v, 1, 0);
  98   }
  99
 100   P2(atomic_t *v)
 101   {
 102     atomic_set(v, 0);
 103   }
 104
 105   exists
 106   (v=2)
 107
 108 In this case we would expect the atomic_set() from CPU1 to either happen
 109 before the atomic_add_unless(), in which case that latter one would no-op, or
 110 _after_ in which case we'd overwrite its result. In no case is "2" a valid
 111 outcome.
 112
 113 This is typically true on 'normal' platforms, where a regular competing STORE
 114 will invalidate a LL/SC or fail a CMPXCHG.
 115
 116 The obvious case where this is not so is when we need to implement atomic ops
 117 with a lock:
 118
 119   CPU0                                          CPU1
 120
 121   atomic_add_unless(v, 1, 0);
 122     lock();
 123     ret = READ_ONCE(v->counter); // == 1
 124                                                 atomic_set(v, 0);
 125     if (ret != u)                                 WRITE_ONCE(v->counter, 0);
 126       WRITE_ONCE(v->counter, ret + 1);
 127     unlock();
 128
 129 the typical solution is to then implement atomic_set{}() with atomic_xchg().
 130
 131
 132 RMW ops:
 133
 134 These come in various forms:
 135
 136  - plain operations without return value: atomic_{}()
 137
 138  - operations which return the modified value: atomic_{}_return()
 139
 140    these are limited to the arithmetic operations because those are
 141    reversible. Bitops are irreversible and therefore the modified value
 142    is of dubious utility.
 143
 144  - operations which return the original value: atomic_fetch_{}()
 145
 146  - swap operations: xchg(), cmpxchg() and try_cmpxchg()
 147
 148  - misc; the special purpose operations that are commonly used and would,
 149    given the interface, normally be implemented using (try_)cmpxchg loops but
 150    are time critical and can, (typically) on LL/SC architectures, be more
 151    efficiently implemented.
 152
 153 All these operations are SMP atomic; that is, the operations (for a single
 154 atomic variable) can be fully ordered and no intermediate state is lost or
 155 visible.
 156
 157
 158 ORDERING  (go read memory-barriers.txt first)
 159 --------
 160
 161 The rule of thumb:
 162
 163  - non-RMW operations are unordered;
 164
 165  - RMW operations that have no return value are unordered;
 166
 167  - RMW operations that have a return value are fully ordered;
 168
 169  - RMW operations that are conditional are unordered on FAILURE,
 170    otherwise the above rules apply.
 171
 172 Except of course when an operation has an explicit ordering like:
 173
 174  {}_relaxed: unordered
 175  {}_acquire: the R of the RMW (or atomic_read) is an ACQUIRE
 176  {}_release: the W of the RMW (or atomic_set)  is a  RELEASE
 177
 178 Where 'unordered' is against other memory locations. Address dependencies are
 179 not defeated.
 180
 181 Fully ordered primitives are ordered against everything prior and everything
 182 subsequent. Therefore a fully ordered primitive is like having an smp_mb()
 183 before and an smp_mb() after the primitive.
 184
 185
 186 The barriers:
 187
 188   smp_mb__{before,after}_atomic()
 189
 190 only apply to the RMW atomic ops and can be used to augment/upgrade the
 191 ordering inherent to the op. These barriers act almost like a full smp_mb():
 192 smp_mb__before_atomic() orders all earlier accesses against the RMW op
 193 itself and all accesses following it, and smp_mb__after_atomic() orders all
 194 later accesses against the RMW op and all accesses preceding it. However,
 195 accesses between the smp_mb__{before,after}_atomic() and the RMW op are not
 196 ordered, so it is advisable to place the barrier right next to the RMW atomic
 197 op whenever possible.
 198
 199 These helper barriers exist because architectures have varying implicit
 200 ordering on their SMP atomic primitives. For example our TSO architectures
 201 provide full ordered atomics and these barriers are no-ops.
 202
 203 Thus:
 204
 205   atomic_fetch_add();
 206
 207 is equivalent to:
 208
 209   smp_mb__before_atomic();
 210   atomic_fetch_add_relaxed();
 211   smp_mb__after_atomic();
 212
 213 However the atomic_fetch_add() might be implemented more efficiently.
 214
 215 Further, while something like:
 216
 217   smp_mb__before_atomic();
 218   atomic_dec(&X);
 219
 220 is a 'typical' RELEASE pattern, the barrier is strictly stronger than
 221 a RELEASE because it orders preceding instructions against both the read
 222 and write parts of the atomic_dec(), and against all following instructions
 223 as well. Similarly, something like:
 224
 225   atomic_inc(&X);
 226   smp_mb__after_atomic();
 227
 228 is an ACQUIRE pattern (though very much not typical), but again the barrier is
 229 strictly stronger than ACQUIRE. As illustrated:
 230
 231   C strong-acquire
 232
 233   {
 234   }
 235
 236   P1(int *x, atomic_t *y)
 237   {
 238     r0 = READ_ONCE(*x);
 239     smp_rmb();
 240     r1 = atomic_read(y);
 241   }
 242
 243   P2(int *x, atomic_t *y)
 244   {
 245     atomic_inc(y);
 246     smp_mb__after_atomic();
 247     WRITE_ONCE(*x, 1);
 248   }
 249
 250   exists
 251   (r0=1 /\ r1=0)
 252
 253 This should not happen; but a hypothetical atomic_inc_acquire() --
 254 (void)atomic_fetch_inc_acquire() for instance -- would allow the outcome,
 255 because it would not order the W part of the RMW against the following
 256 WRITE_ONCE.  Thus:
 257
 258   P1                    P2
 259
 260                         t = LL.acq *y (0)
 261                         t++;
 262                         *x = 1;
 263   r0 = *x (1)
 264   RMB
 265   r1 = *y (0)
 266                         SC *y, t;
 267
 268 is allowed.