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. Clang can not yet 123 /// codegen __atomic_is_lock_free(16), so for now we assume 16-byte values are 124 /// not lock free. 125 #define IS_LOCK_FREE_1 __c11_atomic_is_lock_free(1) 126 #define IS_LOCK_FREE_2 __c11_atomic_is_lock_free(2) 127 #define IS_LOCK_FREE_4 __c11_atomic_is_lock_free(4) 128 #define IS_LOCK_FREE_8 __c11_atomic_is_lock_free(8) 129 #define IS_LOCK_FREE_16 0 130 131 /// Macro that calls the compiler-generated lock-free versions of functions 132 /// when they exist. 133 #define LOCK_FREE_CASES() \ 134 do { \ 135 switch (size) { \ 136 case 1: \ 137 if (IS_LOCK_FREE_1) { \ 138 LOCK_FREE_ACTION(uint8_t); \ 139 } \ 140 break; \ 141 case 2: \ 142 if (IS_LOCK_FREE_2) { \ 143 LOCK_FREE_ACTION(uint16_t); \ 144 } \ 145 break; \ 146 case 4: \ 147 if (IS_LOCK_FREE_4) { \ 148 LOCK_FREE_ACTION(uint32_t); \ 149 } \ 150 break; \ 151 case 8: \ 152 if (IS_LOCK_FREE_8) { \ 153 LOCK_FREE_ACTION(uint64_t); \ 154 } \ 155 break; \ 156 case 16: \ 157 if (IS_LOCK_FREE_16) { \ 158 /* FIXME: __uint128_t isn't available on 32 bit platforms. \ 159 LOCK_FREE_ACTION(__uint128_t);*/ \ 160 } \ 161 break; \ 162 } \ 163 } while (0) 164 165 /// An atomic load operation. This is atomic with respect to the source 166 /// pointer only. 167 void __atomic_load_c(int size, void *src, void *dest, int model) { 168 #define LOCK_FREE_ACTION(type) \ 169 *((type *)dest) = __c11_atomic_load((_Atomic(type) *)src, model); \ 170 return; 171 LOCK_FREE_CASES(); 172 #undef LOCK_FREE_ACTION 173 Lock *l = lock_for_pointer(src); 174 lock(l); 175 memcpy(dest, src, size); 176 unlock(l); 177 } 178 179 /// An atomic store operation. This is atomic with respect to the destination 180 /// pointer only. 181 void __atomic_store_c(int size, void *dest, void *src, int model) { 182 #define LOCK_FREE_ACTION(type) \ 183 __c11_atomic_store((_Atomic(type) *)dest, *(type *)src, model); \ 184 return; 185 LOCK_FREE_CASES(); 186 #undef LOCK_FREE_ACTION 187 Lock *l = lock_for_pointer(dest); 188 lock(l); 189 memcpy(dest, src, size); 190 unlock(l); 191 } 192 193 /// Atomic compare and exchange operation. If the value at *ptr is identical 194 /// to the value at *expected, then this copies value at *desired to *ptr. If 195 /// they are not, then this stores the current value from *ptr in *expected. 196 /// 197 /// This function returns 1 if the exchange takes place or 0 if it fails. 198 int __atomic_compare_exchange_c(int size, void *ptr, void *expected, 199 void *desired, int success, int failure) { 200 #define LOCK_FREE_ACTION(type) \ 201 return __c11_atomic_compare_exchange_strong( \ 202 (_Atomic(type) *)ptr, (type *)expected, *(type *)desired, success, \ 203 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 = \ 223 __c11_atomic_exchange((_Atomic(type) *)ptr, *(type *)val, 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 #ifdef __SIZEOF_INT128__ 239 #define OPTIMISED_CASES \ 240 OPTIMISED_CASE(1, IS_LOCK_FREE_1, uint8_t) \ 241 OPTIMISED_CASE(2, IS_LOCK_FREE_2, uint16_t) \ 242 OPTIMISED_CASE(4, IS_LOCK_FREE_4, uint32_t) \ 243 OPTIMISED_CASE(8, IS_LOCK_FREE_8, uint64_t) \ 244 OPTIMISED_CASE(16, IS_LOCK_FREE_16, __uint128_t) 245 #else 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 #endif 252 253 #define OPTIMISED_CASE(n, lockfree, type) \ 254 type __atomic_load_##n(type *src, int model) { \ 255 if (lockfree) \ 256 return __c11_atomic_load((_Atomic(type) *)src, model); \ 257 Lock *l = lock_for_pointer(src); \ 258 lock(l); \ 259 type val = *src; \ 260 unlock(l); \ 261 return val; \ 262 } 263 OPTIMISED_CASES 264 #undef OPTIMISED_CASE 265 266 #define OPTIMISED_CASE(n, lockfree, type) \ 267 void __atomic_store_##n(type *dest, type val, int model) { \ 268 if (lockfree) { \ 269 __c11_atomic_store((_Atomic(type) *)dest, val, model); \ 270 return; \ 271 } \ 272 Lock *l = lock_for_pointer(dest); \ 273 lock(l); \ 274 *dest = val; \ 275 unlock(l); \ 276 return; \ 277 } 278 OPTIMISED_CASES 279 #undef OPTIMISED_CASE 280 281 #define OPTIMISED_CASE(n, lockfree, type) \ 282 type __atomic_exchange_##n(type *dest, type val, int model) { \ 283 if (lockfree) \ 284 return __c11_atomic_exchange((_Atomic(type) *)dest, val, model); \ 285 Lock *l = lock_for_pointer(dest); \ 286 lock(l); \ 287 type tmp = *dest; \ 288 *dest = val; \ 289 unlock(l); \ 290 return tmp; \ 291 } 292 OPTIMISED_CASES 293 #undef OPTIMISED_CASE 294 295 #define OPTIMISED_CASE(n, lockfree, type) \ 296 int __atomic_compare_exchange_##n(type *ptr, type *expected, type desired, \ 297 int success, int failure) { \ 298 if (lockfree) \ 299 return __c11_atomic_compare_exchange_strong( \ 300 (_Atomic(type) *)ptr, expected, desired, success, failure); \ 301 Lock *l = lock_for_pointer(ptr); \ 302 lock(l); \ 303 if (*ptr == *expected) { \ 304 *ptr = desired; \ 305 unlock(l); \ 306 return 1; \ 307 } \ 308 *expected = *ptr; \ 309 unlock(l); \ 310 return 0; \ 311 } 312 OPTIMISED_CASES 313 #undef OPTIMISED_CASE 314 315 //////////////////////////////////////////////////////////////////////////////// 316 // Atomic read-modify-write operations for integers of various sizes. 317 //////////////////////////////////////////////////////////////////////////////// 318 #define ATOMIC_RMW(n, lockfree, type, opname, op) \ 319 type __atomic_fetch_##opname##_##n(type *ptr, type val, int model) { \ 320 if (lockfree) \ 321 return __c11_atomic_fetch_##opname((_Atomic(type) *)ptr, val, model); \ 322 Lock *l = lock_for_pointer(ptr); \ 323 lock(l); \ 324 type tmp = *ptr; \ 325 *ptr = tmp op val; \ 326 unlock(l); \ 327 return tmp; \ 328 } 329 330 #define OPTIMISED_CASE(n, lockfree, type) ATOMIC_RMW(n, lockfree, type, add, +) 331 OPTIMISED_CASES 332 #undef OPTIMISED_CASE 333 #define OPTIMISED_CASE(n, lockfree, type) ATOMIC_RMW(n, lockfree, type, sub, -) 334 OPTIMISED_CASES 335 #undef OPTIMISED_CASE 336 #define OPTIMISED_CASE(n, lockfree, type) ATOMIC_RMW(n, lockfree, type, and, &) 337 OPTIMISED_CASES 338 #undef OPTIMISED_CASE 339 #define OPTIMISED_CASE(n, lockfree, type) ATOMIC_RMW(n, lockfree, type, or, |) 340 OPTIMISED_CASES 341 #undef OPTIMISED_CASE 342 #define OPTIMISED_CASE(n, lockfree, type) ATOMIC_RMW(n, lockfree, type, xor, ^) 343 OPTIMISED_CASES 344 #undef OPTIMISED_CASE 345