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
  60 SEMANTICS
  61 ---------
  62
  63 Non-RMW ops:
  64
  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.
  68
  69 The one detail to this is that atomic_set{}() should be observable to the RMW
  70 ops. 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
  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.
  95
  96 This is typically true on 'normal' platforms, where a regular competing STORE
  97 will invalidate a LL/SC or fail a CMPXCHG.
  98
  99 The obvious case where this is not so is when we need to implement atomic ops
 100 with 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
 112 the typical solution is to then implement atomic_set{}() with atomic_xchg().
 113
 114
 115 RMW ops:
 116
 117 These 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
 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.
 139
 140
 141 ORDERING  (go read memory-barriers.txt first)
 142 --------
 143
 144 The 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
 155 Except 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
 161 Where 'unordered' is against other memory locations. Address dependencies are
 162 not defeated.
 163
 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.
 167
 168
 169 The barriers:
 170
 171   smp_mb__{before,after}_atomic()
 172
 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().
 175
 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.
 179
 180 NOTE: when the atomic RmW ops are fully ordered, they should also imply a
 181 compiler barrier.
 182
 183 Thus:
 184
 185   atomic_fetch_add();
 186
 187 is equivalent to:
 188
 189   smp_mb__before_atomic();
 190   atomic_fetch_add_relaxed();
 191   smp_mb__after_atomic();
 192
 193 However the atomic_fetch_add() might be implemented more efficiently.
 194
 195 Further, while something like:
 196
 197   smp_mb__before_atomic();
 198   atomic_dec(&X);
 199
 200 is a 'typical' RELEASE pattern, the barrier is strictly stronger than
 201 a RELEASE. Similarly for something like:
 202
 203   atomic_inc(&X);
 204   smp_mb__after_atomic();
 205
 206 is an ACQUIRE pattern (though very much not typical), but again the barrier is
 207 strictly stronger than ACQUIRE. As illustrated:
 208
 209   C strong-acquire
 210
 211   {
 212   }
 213
 214   P1(int *x, atomic_t *y)
 215   {
 216     r0 = READ_ONCE(*x);
 217     smp_rmb();
 218     r1 = atomic_read(y);
 219   }
 220
 221   P2(int *x, atomic_t *y)
 222   {
 223     atomic_inc(y);
 224     smp_mb__after_atomic();
 225     WRITE_ONCE(*x, 1);
 226   }
 227
 228   exists
 229   (r0=1 /\ r1=0)
 230
 231 This should not happen; but a hypothetical atomic_inc_acquire() --
 232 (void)atomic_fetch_inc_acquire() for instance -- would allow the outcome,
 233 since then:
 234
 235   P1                    P2
 236
 237                         t = LL.acq *y (0)
 238                         t++;
 239                         *x = 1;
 240   r0 = *x (1)
 241   RMB
 242   r1 = *y (0)
 243                         SC *y, t;
 244
 245 is allowed.