contrib/llvm-project/compiler-rt/lib/builtins/atomic.c

   1 //===-- atomic.c - Implement support functions for atomic operations.------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 //  atomic.c defines a set of functions for performing atomic accesses on
  10 //  arbitrary-sized memory locations.  This design uses locks that should
  11 //  be fast in the uncontended case, for two reasons:
  12 //
  13 //  1) This code must work with C programs that do not link to anything
  14 //     (including pthreads) and so it should not depend on any pthread
  15 //     functions.
  16 //  2) Atomic operations, rather than explicit mutexes, are most commonly used
  17 //     on code where contended operations are rate.
  18 //
  19 //  To avoid needing a per-object lock, this code allocates an array of
  20 //  locks and hashes the object pointers to find the one that it should use.
  21 //  For operations that must be atomic on two locations, the lower lock is
  22 //  always acquired first, to avoid deadlock.
  23 //
  24 //===----------------------------------------------------------------------===//
  25
  26 #include <stdint.h>
  27 #include <string.h>
  28
  29 #include "assembly.h"
  30
  31 // Clang objects if you redefine a builtin.  This little hack allows us to
  32 // define a function with the same name as an intrinsic.
  33 #pragma redefine_extname __atomic_load_c SYMBOL_NAME(__atomic_load)
  34 #pragma redefine_extname __atomic_store_c SYMBOL_NAME(__atomic_store)
  35 #pragma redefine_extname __atomic_exchange_c SYMBOL_NAME(__atomic_exchange)
  36 #pragma redefine_extname __atomic_compare_exchange_c SYMBOL_NAME(              \
  37     __atomic_compare_exchange)
  38
  39 /// Number of locks.  This allocates one page on 32-bit platforms, two on
  40 /// 64-bit.  This can be specified externally if a different trade between
  41 /// memory usage and contention probability is required for a given platform.
  42 #ifndef SPINLOCK_COUNT
  43 #define SPINLOCK_COUNT (1 << 10)
  44 #endif
  45 static const long SPINLOCK_MASK = SPINLOCK_COUNT - 1;
  46
  47 ////////////////////////////////////////////////////////////////////////////////
  48 // Platform-specific lock implementation.  Falls back to spinlocks if none is
  49 // defined.  Each platform should define the Lock type, and corresponding
  50 // lock() and unlock() functions.
  51 ////////////////////////////////////////////////////////////////////////////////
  52 #ifdef __FreeBSD__
  53 #include <errno.h>
  54 // clang-format off
  55 #include <sys/types.h>
  56 #include <machine/atomic.h>
  57 #include <sys/umtx.h>
  58 // clang-format on
  59 typedef struct _usem Lock;
  60 __inline static void unlock(Lock *l) {
  61   __c11_atomic_store((_Atomic(uint32_t) *)&l->_count, 1, __ATOMIC_RELEASE);
  62   __c11_atomic_thread_fence(__ATOMIC_SEQ_CST);
  63   if (l->_has_waiters)
  64     _umtx_op(l, UMTX_OP_SEM_WAKE, 1, 0, 0);
  65 }
  66 __inline static void lock(Lock *l) {
  67   uint32_t old = 1;
  68   while (!__c11_atomic_compare_exchange_weak((_Atomic(uint32_t) *)&l->_count,
  69                                              &old, 0, __ATOMIC_ACQUIRE,
  70                                              __ATOMIC_RELAXED)) {
  71     _umtx_op(l, UMTX_OP_SEM_WAIT, 0, 0, 0);
  72     old = 1;
  73   }
  74 }
  75 /// locks for atomic operations
  76 static Lock locks[SPINLOCK_COUNT] = {[0 ... SPINLOCK_COUNT - 1] = {0, 1, 0}};
  77
  78 #elif defined(__APPLE__)
  79 #include <libkern/OSAtomic.h>
  80 typedef OSSpinLock Lock;
  81 __inline static void unlock(Lock *l) { OSSpinLockUnlock(l); }
  82 /// Locks a lock.  In the current implementation, this is potentially
  83 /// unbounded in the contended case.
  84 __inline static void lock(Lock *l) { OSSpinLockLock(l); }
  85 static Lock locks[SPINLOCK_COUNT]; // initialized to OS_SPINLOCK_INIT which is 0
  86
  87 #else
  88 typedef _Atomic(uintptr_t) Lock;
  89 /// Unlock a lock.  This is a release operation.
  90 __inline static void unlock(Lock *l) {
  91   __c11_atomic_store(l, 0, __ATOMIC_RELEASE);
  92 }
  93 /// Locks a lock.  In the current implementation, this is potentially
  94 /// unbounded in the contended case.
  95 __inline static void lock(Lock *l) {
  96   uintptr_t old = 0;
  97   while (!__c11_atomic_compare_exchange_weak(l, &old, 1, __ATOMIC_ACQUIRE,
  98                                              __ATOMIC_RELAXED))
  99     old = 0;
 100 }
 101 /// locks for atomic operations
 102 static Lock locks[SPINLOCK_COUNT];
 103 #endif
 104
 105 /// Returns a lock to use for a given pointer.
 106 static __inline Lock *lock_for_pointer(void *ptr) {
 107   intptr_t hash = (intptr_t)ptr;
 108   // Disregard the lowest 4 bits.  We want all values that may be part of the
 109   // same memory operation to hash to the same value and therefore use the same
 110   // lock.
 111   hash >>= 4;
 112   // Use the next bits as the basis for the hash
 113   intptr_t low = hash & SPINLOCK_MASK;
 114   // Now use the high(er) set of bits to perturb the hash, so that we don't
 115   // get collisions from atomic fields in a single object
 116   hash >>= 16;
 117   hash ^= low;
 118   // Return a pointer to the word to use
 119   return locks + (hash & SPINLOCK_MASK);
 120 }
 121
 122 /// Macros for determining whether a size is lock free.
 123 #define IS_LOCK_FREE_1 __c11_atomic_is_lock_free(1)
 124 #define IS_LOCK_FREE_2 __c11_atomic_is_lock_free(2)
 125 #define IS_LOCK_FREE_4 __c11_atomic_is_lock_free(4)
 126
 127 /// 32 bit PowerPC doesn't support 8-byte lock_free atomics
 128 #if !defined(__powerpc64__) && defined(__powerpc__)
 129 #define IS_LOCK_FREE_8 0
 130 #else
 131 #define IS_LOCK_FREE_8 __c11_atomic_is_lock_free(8)
 132 #endif
 133
 134 /// Clang can not yet codegen __atomic_is_lock_free(16), so for now we assume
 135 /// 16-byte values are not lock free.
 136 #define IS_LOCK_FREE_16 0
 137
 138 /// Macro that calls the compiler-generated lock-free versions of functions
 139 /// when they exist.
 140 #define LOCK_FREE_CASES()                                                      \
 141   do {                                                                         \
 142     switch (size) {                                                            \
 143     case 1:                                                                    \
 144       if (IS_LOCK_FREE_1) {                                                    \
 145         LOCK_FREE_ACTION(uint8_t);                                             \
 146       }                                                                        \
 147       break;                                                                   \
 148     case 2:                                                                    \
 149       if (IS_LOCK_FREE_2) {                                                    \
 150         LOCK_FREE_ACTION(uint16_t);                                            \
 151       }                                                                        \
 152       break;                                                                   \
 153     case 4:                                                                    \
 154       if (IS_LOCK_FREE_4) {                                                    \
 155         LOCK_FREE_ACTION(uint32_t);                                            \
 156       }                                                                        \
 157       break;                                                                   \
 158     case 8:                                                                    \
 159       if (IS_LOCK_FREE_8) {                                                    \
 160         LOCK_FREE_ACTION(uint64_t);                                            \
 161       }                                                                        \
 162       break;                                                                   \
 163     case 16:                                                                   \
 164       if (IS_LOCK_FREE_16) {                                                   \
 165         /* FIXME: __uint128_t isn't available on 32 bit platforms.             \
 166         LOCK_FREE_ACTION(__uint128_t);*/                                       \
 167       }                                                                        \
 168       break;                                                                   \
 169     }                                                                          \
 170   } while (0)
 171
 172 /// An atomic load operation.  This is atomic with respect to the source
 173 /// pointer only.
 174 void __atomic_load_c(int size, void *src, void *dest, int model) {
 175 #define LOCK_FREE_ACTION(type)                                                 \
 176   *((type *)dest) = __c11_atomic_load((_Atomic(type) *)src, model);            \
 177   return;
 178   LOCK_FREE_CASES();
 179 #undef LOCK_FREE_ACTION
 180   Lock *l = lock_for_pointer(src);
 181   lock(l);
 182   memcpy(dest, src, size);
 183   unlock(l);
 184 }
 185
 186 /// An atomic store operation.  This is atomic with respect to the destination
 187 /// pointer only.
 188 void __atomic_store_c(int size, void *dest, void *src, int model) {
 189 #define LOCK_FREE_ACTION(type)                                                 \
 190   __c11_atomic_store((_Atomic(type) *)dest, *(type *)src, model);              \
 191   return;
 192   LOCK_FREE_CASES();
 193 #undef LOCK_FREE_ACTION
 194   Lock *l = lock_for_pointer(dest);
 195   lock(l);
 196   memcpy(dest, src, size);
 197   unlock(l);
 198 }
 199
 200 /// Atomic compare and exchange operation.  If the value at *ptr is identical
 201 /// to the value at *expected, then this copies value at *desired to *ptr.  If
 202 /// they  are not, then this stores the current value from *ptr in *expected.
 203 ///
 204 /// This function returns 1 if the exchange takes place or 0 if it fails.
 205 int __atomic_compare_exchange_c(int size, void *ptr, void *expected,
 206                                 void *desired, int success, int failure) {
 207 #define LOCK_FREE_ACTION(type)                                                 \
 208   return __c11_atomic_compare_exchange_strong(                                 \
 209       (_Atomic(type) *)ptr, (type *)expected, *(type *)desired, success,       \
 210       failure)
 211   LOCK_FREE_CASES();
 212 #undef LOCK_FREE_ACTION
 213   Lock *l = lock_for_pointer(ptr);
 214   lock(l);
 215   if (memcmp(ptr, expected, size) == 0) {
 216     memcpy(ptr, desired, size);
 217     unlock(l);
 218     return 1;
 219   }
 220   memcpy(expected, ptr, size);
 221   unlock(l);
 222   return 0;
 223 }
 224
 225 /// Performs an atomic exchange operation between two pointers.  This is atomic
 226 /// with respect to the target address.
 227 void __atomic_exchange_c(int size, void *ptr, void *val, void *old, int model) {
 228 #define LOCK_FREE_ACTION(type)                                                 \
 229   *(type *)old =                                                               \
 230       __c11_atomic_exchange((_Atomic(type) *)ptr, *(type *)val, model);        \
 231   return;
 232   LOCK_FREE_CASES();
 233 #undef LOCK_FREE_ACTION
 234   Lock *l = lock_for_pointer(ptr);
 235   lock(l);
 236   memcpy(old, ptr, size);
 237   memcpy(ptr, val, size);
 238   unlock(l);
 239 }
 240
 241 ////////////////////////////////////////////////////////////////////////////////
 242 // Where the size is known at compile time, the compiler may emit calls to
 243 // specialised versions of the above functions.
 244 ////////////////////////////////////////////////////////////////////////////////
 245 #ifdef __SIZEOF_INT128__
 246 #define OPTIMISED_CASES                                                        \
 247   OPTIMISED_CASE(1, IS_LOCK_FREE_1, uint8_t)                                   \
 248   OPTIMISED_CASE(2, IS_LOCK_FREE_2, uint16_t)                                  \
 249   OPTIMISED_CASE(4, IS_LOCK_FREE_4, uint32_t)                                  \
 250   OPTIMISED_CASE(8, IS_LOCK_FREE_8, uint64_t)                                  \
 251   OPTIMISED_CASE(16, IS_LOCK_FREE_16, __uint128_t)
 252 #else
 253 #define OPTIMISED_CASES                                                        \
 254   OPTIMISED_CASE(1, IS_LOCK_FREE_1, uint8_t)                                   \
 255   OPTIMISED_CASE(2, IS_LOCK_FREE_2, uint16_t)                                  \
 256   OPTIMISED_CASE(4, IS_LOCK_FREE_4, uint32_t)                                  \
 257   OPTIMISED_CASE(8, IS_LOCK_FREE_8, uint64_t)
 258 #endif
 259
 260 #define OPTIMISED_CASE(n, lockfree, type)                                      \
 261   type __atomic_load_##n(type *src, int model) {                               \
 262     if (lockfree)                                                              \
 263       return __c11_atomic_load((_Atomic(type) *)src, model);                   \
 264     Lock *l = lock_for_pointer(src);                                           \
 265     lock(l);                                                                   \
 266     type val = *src;                                                           \
 267     unlock(l);                                                                 \
 268     return val;                                                                \
 269   }
 270 OPTIMISED_CASES
 271 #undef OPTIMISED_CASE
 272
 273 #define OPTIMISED_CASE(n, lockfree, type)                                      \
 274   void __atomic_store_##n(type *dest, type val, int model) {                   \
 275     if (lockfree) {                                                            \
 276       __c11_atomic_store((_Atomic(type) *)dest, val, model);                   \
 277       return;                                                                  \
 278     }                                                                          \
 279     Lock *l = lock_for_pointer(dest);                                          \
 280     lock(l);                                                                   \
 281     *dest = val;                                                               \
 282     unlock(l);                                                                 \
 283     return;                                                                    \
 284   }
 285 OPTIMISED_CASES
 286 #undef OPTIMISED_CASE
 287
 288 #define OPTIMISED_CASE(n, lockfree, type)                                      \
 289   type __atomic_exchange_##n(type *dest, type val, int model) {                \
 290     if (lockfree)                                                              \
 291       return __c11_atomic_exchange((_Atomic(type) *)dest, val, model);         \
 292     Lock *l = lock_for_pointer(dest);                                          \
 293     lock(l);                                                                   \
 294     type tmp = *dest;                                                          \
 295     *dest = val;                                                               \
 296     unlock(l);                                                                 \
 297     return tmp;                                                                \
 298   }
 299 OPTIMISED_CASES
 300 #undef OPTIMISED_CASE
 301
 302 #define OPTIMISED_CASE(n, lockfree, type)                                      \
 303   int __atomic_compare_exchange_##n(type *ptr, type *expected, type desired,   \
 304                                     int success, int failure) {                \
 305     if (lockfree)                                                              \
 306       return __c11_atomic_compare_exchange_strong(                             \
 307           (_Atomic(type) *)ptr, expected, desired, success, failure);          \
 308     Lock *l = lock_for_pointer(ptr);                                           \
 309     lock(l);                                                                   \
 310     if (*ptr == *expected) {                                                   \
 311       *ptr = desired;                                                          \
 312       unlock(l);                                                               \
 313       return 1;                                                                \
 314     }                                                                          \
 315     *expected = *ptr;                                                          \
 316     unlock(l);                                                                 \
 317     return 0;                                                                  \
 318   }
 319 OPTIMISED_CASES
 320 #undef OPTIMISED_CASE
 321
 322 ////////////////////////////////////////////////////////////////////////////////
 323 // Atomic read-modify-write operations for integers of various sizes.
 324 ////////////////////////////////////////////////////////////////////////////////
 325 #define ATOMIC_RMW(n, lockfree, type, opname, op)                              \
 326   type __atomic_fetch_##opname##_##n(type *ptr, type val, int model) {         \
 327     if (lockfree)                                                              \
 328       return __c11_atomic_fetch_##opname((_Atomic(type) *)ptr, val, model);    \
 329     Lock *l = lock_for_pointer(ptr);                                           \
 330     lock(l);                                                                   \
 331     type tmp = *ptr;                                                           \
 332     *ptr = tmp op val;                                                         \
 333     unlock(l);                                                                 \
 334     return tmp;                                                                \
 335   }
 336
 337 #define OPTIMISED_CASE(n, lockfree, type) ATOMIC_RMW(n, lockfree, type, add, +)
 338 OPTIMISED_CASES
 339 #undef OPTIMISED_CASE
 340 #define OPTIMISED_CASE(n, lockfree, type) ATOMIC_RMW(n, lockfree, type, sub, -)
 341 OPTIMISED_CASES
 342 #undef OPTIMISED_CASE
 343 #define OPTIMISED_CASE(n, lockfree, type) ATOMIC_RMW(n, lockfree, type, and, &)
 344 OPTIMISED_CASES
 345 #undef OPTIMISED_CASE
 346 #define OPTIMISED_CASE(n, lockfree, type) ATOMIC_RMW(n, lockfree, type, or, |)
 347 OPTIMISED_CASES
 348 #undef OPTIMISED_CASE
 349 #define OPTIMISED_CASE(n, lockfree, type) ATOMIC_RMW(n, lockfree, type, xor, ^)
 350 OPTIMISED_CASES
 351 #undef OPTIMISED_CASE