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

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