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 #include <machine/atomic.h>
  55 #include <sys/types.h>
  56 #include <sys/umtx.h>
  57 typedef struct _usem Lock;
  58 __inline static void unlock(Lock *l) {
  59   __c11_atomic_store((_Atomic(uint32_t) *)&l->_count, 1, __ATOMIC_RELEASE);
  60   __c11_atomic_thread_fence(__ATOMIC_SEQ_CST);
  61   if (l->_has_waiters)
  62     _umtx_op(l, UMTX_OP_SEM_WAKE, 1, 0, 0);
  63 }
  64 __inline static void lock(Lock *l) {
  65   uint32_t old = 1;
  66   while (!__c11_atomic_compare_exchange_weak((_Atomic(uint32_t) *)&l->_count,
  67                                              &old, 0, __ATOMIC_ACQUIRE,
  68                                              __ATOMIC_RELAXED)) {
  69     _umtx_op(l, UMTX_OP_SEM_WAIT, 0, 0, 0);
  70     old = 1;
  71   }
  72 }
  73 /// locks for atomic operations
  74 static Lock locks[SPINLOCK_COUNT] = {[0 ... SPINLOCK_COUNT - 1] = {0, 1, 0}};
  75
  76 #elif defined(__APPLE__)
  77 #include <libkern/OSAtomic.h>
  78 typedef OSSpinLock Lock;
  79 __inline static void unlock(Lock *l) { OSSpinLockUnlock(l); }
  80 /// Locks a lock.  In the current implementation, this is potentially
  81 /// unbounded in the contended case.
  82 __inline static void lock(Lock *l) { OSSpinLockLock(l); }
  83 static Lock locks[SPINLOCK_COUNT]; // initialized to OS_SPINLOCK_INIT which is 0
  84
  85 #else
  86 typedef _Atomic(uintptr_t) Lock;
  87 /// Unlock a lock.  This is a release operation.
  88 __inline static void unlock(Lock *l) {
  89   __c11_atomic_store(l, 0, __ATOMIC_RELEASE);
  90 }
  91 /// Locks a lock.  In the current implementation, this is potentially
  92 /// unbounded in the contended case.
  93 __inline static void lock(Lock *l) {
  94   uintptr_t old = 0;
  95   while (!__c11_atomic_compare_exchange_weak(l, &old, 1, __ATOMIC_ACQUIRE,
  96                                              __ATOMIC_RELAXED))
  97     old = 0;
  98 }
  99 /// locks for atomic operations
 100 static Lock locks[SPINLOCK_COUNT];
 101 #endif
 102
 103 /// Returns a lock to use for a given pointer.
 104 static __inline Lock *lock_for_pointer(void *ptr) {
 105   intptr_t hash = (intptr_t)ptr;
 106   // Disregard the lowest 4 bits.  We want all values that may be part of the
 107   // same memory operation to hash to the same value and therefore use the same
 108   // lock.
 109   hash >>= 4;
 110   // Use the next bits as the basis for the hash
 111   intptr_t low = hash & SPINLOCK_MASK;
 112   // Now use the high(er) set of bits to perturb the hash, so that we don't
 113   // get collisions from atomic fields in a single object
 114   hash >>= 16;
 115   hash ^= low;
 116   // Return a pointer to the word to use
 117   return locks + (hash & SPINLOCK_MASK);
 118 }
 119
 120 /// Macros for determining whether a size is lock free.  Clang can not yet
 121 /// codegen __atomic_is_lock_free(16), so for now we assume 16-byte values are
 122 /// not 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 #define IS_LOCK_FREE_8 __c11_atomic_is_lock_free(8)
 127 #define IS_LOCK_FREE_16 0
 128
 129 /// Macro that calls the compiler-generated lock-free versions of functions
 130 /// when they exist.
 131 #define LOCK_FREE_CASES()                                                      \
 132   do {                                                                         \
 133     switch (size) {                                                            \
 134     case 1:                                                                    \
 135       if (IS_LOCK_FREE_1) {                                                    \
 136         LOCK_FREE_ACTION(uint8_t);                                             \
 137       }                                                                        \
 138       break;                                                                   \
 139     case 2:                                                                    \
 140       if (IS_LOCK_FREE_2) {                                                    \
 141         LOCK_FREE_ACTION(uint16_t);                                            \
 142       }                                                                        \
 143       break;                                                                   \
 144     case 4:                                                                    \
 145       if (IS_LOCK_FREE_4) {                                                    \
 146         LOCK_FREE_ACTION(uint32_t);                                            \
 147       }                                                                        \
 148       break;                                                                   \
 149     case 8:                                                                    \
 150       if (IS_LOCK_FREE_8) {                                                    \
 151         LOCK_FREE_ACTION(uint64_t);                                            \
 152       }                                                                        \
 153       break;                                                                   \
 154     case 16:                                                                   \
 155       if (IS_LOCK_FREE_16) {                                                   \
 156         /* FIXME: __uint128_t isn't available on 32 bit platforms.             \
 157         LOCK_FREE_ACTION(__uint128_t);*/                                       \
 158       }                                                                        \
 159       break;                                                                   \
 160     }                                                                          \
 161   } while (0)
 162
 163 /// An atomic load operation.  This is atomic with respect to the source
 164 /// pointer only.
 165 void __atomic_load_c(int size, void *src, void *dest, int model) {
 166 #define LOCK_FREE_ACTION(type)                                                 \
 167   *((type *)dest) = __c11_atomic_load((_Atomic(type) *)src, model);            \
 168   return;
 169   LOCK_FREE_CASES();
 170 #undef LOCK_FREE_ACTION
 171   Lock *l = lock_for_pointer(src);
 172   lock(l);
 173   memcpy(dest, src, size);
 174   unlock(l);
 175 }
 176
 177 /// An atomic store operation.  This is atomic with respect to the destination
 178 /// pointer only.
 179 void __atomic_store_c(int size, void *dest, void *src, int model) {
 180 #define LOCK_FREE_ACTION(type)                                                 \
 181   __c11_atomic_store((_Atomic(type) *)dest, *(type *)src, model);              \
 182   return;
 183   LOCK_FREE_CASES();
 184 #undef LOCK_FREE_ACTION
 185   Lock *l = lock_for_pointer(dest);
 186   lock(l);
 187   memcpy(dest, src, size);
 188   unlock(l);
 189 }
 190
 191 /// Atomic compare and exchange operation.  If the value at *ptr is identical
 192 /// to the value at *expected, then this copies value at *desired to *ptr.  If
 193 /// they  are not, then this stores the current value from *ptr in *expected.
 194 ///
 195 /// This function returns 1 if the exchange takes place or 0 if it fails.
 196 int __atomic_compare_exchange_c(int size, void *ptr, void *expected,
 197                                 void *desired, int success, int failure) {
 198 #define LOCK_FREE_ACTION(type)                                                 \
 199   return __c11_atomic_compare_exchange_strong(                                 \
 200       (_Atomic(type) *)ptr, (type *)expected, *(type *)desired, success,       \
 201       failure)
 202   LOCK_FREE_CASES();
 203 #undef LOCK_FREE_ACTION
 204   Lock *l = lock_for_pointer(ptr);
 205   lock(l);
 206   if (memcmp(ptr, expected, size) == 0) {
 207     memcpy(ptr, desired, size);
 208     unlock(l);
 209     return 1;
 210   }
 211   memcpy(expected, ptr, size);
 212   unlock(l);
 213   return 0;
 214 }
 215
 216 /// Performs an atomic exchange operation between two pointers.  This is atomic
 217 /// with respect to the target address.
 218 void __atomic_exchange_c(int size, void *ptr, void *val, void *old, int model) {
 219 #define LOCK_FREE_ACTION(type)                                                 \
 220   *(type *)old =                                                               \
 221       __c11_atomic_exchange((_Atomic(type) *)ptr, *(type *)val, model);        \
 222   return;
 223   LOCK_FREE_CASES();
 224 #undef LOCK_FREE_ACTION
 225   Lock *l = lock_for_pointer(ptr);
 226   lock(l);
 227   memcpy(old, ptr, size);
 228   memcpy(ptr, val, size);
 229   unlock(l);
 230 }
 231
 232 ////////////////////////////////////////////////////////////////////////////////
 233 // Where the size is known at compile time, the compiler may emit calls to
 234 // specialised versions of the above functions.
 235 ////////////////////////////////////////////////////////////////////////////////
 236 #ifdef __SIZEOF_INT128__
 237 #define OPTIMISED_CASES                                                        \
 238   OPTIMISED_CASE(1, IS_LOCK_FREE_1, uint8_t)                                   \
 239   OPTIMISED_CASE(2, IS_LOCK_FREE_2, uint16_t)                                  \
 240   OPTIMISED_CASE(4, IS_LOCK_FREE_4, uint32_t)                                  \
 241   OPTIMISED_CASE(8, IS_LOCK_FREE_8, uint64_t)                                  \
 242   OPTIMISED_CASE(16, IS_LOCK_FREE_16, __uint128_t)
 243 #else
 244 #define OPTIMISED_CASES                                                        \
 245   OPTIMISED_CASE(1, IS_LOCK_FREE_1, uint8_t)                                   \
 246   OPTIMISED_CASE(2, IS_LOCK_FREE_2, uint16_t)                                  \
 247   OPTIMISED_CASE(4, IS_LOCK_FREE_4, uint32_t)                                  \
 248   OPTIMISED_CASE(8, IS_LOCK_FREE_8, uint64_t)
 249 #endif
 250
 251 #define OPTIMISED_CASE(n, lockfree, type)                                      \
 252   type __atomic_load_##n(type *src, int model) {                               \
 253     if (lockfree)                                                              \
 254       return __c11_atomic_load((_Atomic(type) *)src, model);                   \
 255     Lock *l = lock_for_pointer(src);                                           \
 256     lock(l);                                                                   \
 257     type val = *src;                                                           \
 258     unlock(l);                                                                 \
 259     return val;                                                                \
 260   }
 261 OPTIMISED_CASES
 262 #undef OPTIMISED_CASE
 263
 264 #define OPTIMISED_CASE(n, lockfree, type)                                      \
 265   void __atomic_store_##n(type *dest, type val, int model) {                   \
 266     if (lockfree) {                                                            \
 267       __c11_atomic_store((_Atomic(type) *)dest, val, model);                   \
 268       return;                                                                  \
 269     }                                                                          \
 270     Lock *l = lock_for_pointer(dest);                                          \
 271     lock(l);                                                                   \
 272     *dest = val;                                                               \
 273     unlock(l);                                                                 \
 274     return;                                                                    \
 275   }
 276 OPTIMISED_CASES
 277 #undef OPTIMISED_CASE
 278
 279 #define OPTIMISED_CASE(n, lockfree, type)                                      \
 280   type __atomic_exchange_##n(type *dest, type val, int model) {                \
 281     if (lockfree)                                                              \
 282       return __c11_atomic_exchange((_Atomic(type) *)dest, val, model);         \
 283     Lock *l = lock_for_pointer(dest);                                          \
 284     lock(l);                                                                   \
 285     type tmp = *dest;                                                          \
 286     *dest = val;                                                               \
 287     unlock(l);                                                                 \
 288     return tmp;                                                                \
 289   }
 290 OPTIMISED_CASES
 291 #undef OPTIMISED_CASE
 292
 293 #define OPTIMISED_CASE(n, lockfree, type)                                      \
 294   int __atomic_compare_exchange_##n(type *ptr, type *expected, type desired,   \
 295                                     int success, int failure) {                \
 296     if (lockfree)                                                              \
 297       return __c11_atomic_compare_exchange_strong(                             \
 298           (_Atomic(type) *)ptr, expected, desired, success, failure);          \
 299     Lock *l = lock_for_pointer(ptr);                                           \
 300     lock(l);                                                                   \
 301     if (*ptr == *expected) {                                                   \
 302       *ptr = desired;                                                          \
 303       unlock(l);                                                               \
 304       return 1;                                                                \
 305     }                                                                          \
 306     *expected = *ptr;                                                          \
 307     unlock(l);                                                                 \
 308     return 0;                                                                  \
 309   }
 310 OPTIMISED_CASES
 311 #undef OPTIMISED_CASE
 312
 313 ////////////////////////////////////////////////////////////////////////////////
 314 // Atomic read-modify-write operations for integers of various sizes.
 315 ////////////////////////////////////////////////////////////////////////////////
 316 #define ATOMIC_RMW(n, lockfree, type, opname, op)                              \
 317   type __atomic_fetch_##opname##_##n(type *ptr, type val, int model) {         \
 318     if (lockfree)                                                              \
 319       return __c11_atomic_fetch_##opname((_Atomic(type) *)ptr, val, model);    \
 320     Lock *l = lock_for_pointer(ptr);                                           \
 321     lock(l);                                                                   \
 322     type tmp = *ptr;                                                           \
 323     *ptr = tmp op val;                                                         \
 324     unlock(l);                                                                 \
 325     return tmp;                                                                \
 326   }
 327
 328 #define OPTIMISED_CASE(n, lockfree, type) ATOMIC_RMW(n, lockfree, type, add, +)
 329 OPTIMISED_CASES
 330 #undef OPTIMISED_CASE
 331 #define OPTIMISED_CASE(n, lockfree, type) ATOMIC_RMW(n, lockfree, type, sub, -)
 332 OPTIMISED_CASES
 333 #undef OPTIMISED_CASE
 334 #define OPTIMISED_CASE(n, lockfree, type) ATOMIC_RMW(n, lockfree, type, and, &)
 335 OPTIMISED_CASES
 336 #undef OPTIMISED_CASE
 337 #define OPTIMISED_CASE(n, lockfree, type) ATOMIC_RMW(n, lockfree, type, or, |)
 338 OPTIMISED_CASES
 339 #undef OPTIMISED_CASE
 340 #define OPTIMISED_CASE(n, lockfree, type) ATOMIC_RMW(n, lockfree, type, xor, ^)
 341 OPTIMISED_CASES
 342 #undef OPTIMISED_CASE