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 <stdbool.h> 27 #include <stdint.h> 28 #include <string.h> 29 30 #include "assembly.h" 31 32 // Clang objects if you redefine a builtin. This little hack allows us to 33 // define a function with the same name as an intrinsic. 34 #pragma redefine_extname __atomic_load_c SYMBOL_NAME(__atomic_load) 35 #pragma redefine_extname __atomic_store_c SYMBOL_NAME(__atomic_store) 36 #pragma redefine_extname __atomic_exchange_c SYMBOL_NAME(__atomic_exchange) 37 #pragma redefine_extname __atomic_compare_exchange_c SYMBOL_NAME( \ 38 __atomic_compare_exchange) 39 40 /// Number of locks. This allocates one page on 32-bit platforms, two on 41 /// 64-bit. This can be specified externally if a different trade between 42 /// memory usage and contention probability is required for a given platform. 43 #ifndef SPINLOCK_COUNT 44 #define SPINLOCK_COUNT (1 << 10) 45 #endif 46 static const long SPINLOCK_MASK = SPINLOCK_COUNT - 1; 47 48 //////////////////////////////////////////////////////////////////////////////// 49 // Platform-specific lock implementation. Falls back to spinlocks if none is 50 // defined. Each platform should define the Lock type, and corresponding 51 // lock() and unlock() functions. 52 //////////////////////////////////////////////////////////////////////////////// 53 #ifdef __FreeBSD__ 54 #include <errno.h> 55 // clang-format off 56 #include <sys/types.h> 57 #include <machine/atomic.h> 58 #include <sys/umtx.h> 59 // clang-format on 60 typedef struct _usem Lock; 61 __inline static void unlock(Lock *l) { 62 __c11_atomic_store((_Atomic(uint32_t) *)&l->_count, 1, __ATOMIC_RELEASE); 63 __c11_atomic_thread_fence(__ATOMIC_SEQ_CST); 64 if (l->_has_waiters) 65 _umtx_op(l, UMTX_OP_SEM_WAKE, 1, 0, 0); 66 } 67 __inline static void lock(Lock *l) { 68 uint32_t old = 1; 69 while (!__c11_atomic_compare_exchange_weak((_Atomic(uint32_t) *)&l->_count, 70 &old, 0, __ATOMIC_ACQUIRE, 71 __ATOMIC_RELAXED)) { 72 _umtx_op(l, UMTX_OP_SEM_WAIT, 0, 0, 0); 73 old = 1; 74 } 75 } 76 /// locks for atomic operations 77 static Lock locks[SPINLOCK_COUNT] = {[0 ... SPINLOCK_COUNT - 1] = {0, 1, 0}}; 78 79 #elif defined(__APPLE__) 80 #include <libkern/OSAtomic.h> 81 typedef OSSpinLock Lock; 82 __inline static void unlock(Lock *l) { OSSpinLockUnlock(l); } 83 /// Locks a lock. In the current implementation, this is potentially 84 /// unbounded in the contended case. 85 __inline static void lock(Lock *l) { OSSpinLockLock(l); } 86 static Lock locks[SPINLOCK_COUNT]; // initialized to OS_SPINLOCK_INIT which is 0 87 88 #else 89 typedef _Atomic(uintptr_t) Lock; 90 /// Unlock a lock. This is a release operation. 91 __inline static void unlock(Lock *l) { 92 __c11_atomic_store(l, 0, __ATOMIC_RELEASE); 93 } 94 /// Locks a lock. In the current implementation, this is potentially 95 /// unbounded in the contended case. 96 __inline static void lock(Lock *l) { 97 uintptr_t old = 0; 98 while (!__c11_atomic_compare_exchange_weak(l, &old, 1, __ATOMIC_ACQUIRE, 99 __ATOMIC_RELAXED)) 100 old = 0; 101 } 102 /// locks for atomic operations 103 static Lock locks[SPINLOCK_COUNT]; 104 #endif 105 106 /// Returns a lock to use for a given pointer. 107 static __inline Lock *lock_for_pointer(void *ptr) { 108 intptr_t hash = (intptr_t)ptr; 109 // Disregard the lowest 4 bits. We want all values that may be part of the 110 // same memory operation to hash to the same value and therefore use the same 111 // lock. 112 hash >>= 4; 113 // Use the next bits as the basis for the hash 114 intptr_t low = hash & SPINLOCK_MASK; 115 // Now use the high(er) set of bits to perturb the hash, so that we don't 116 // get collisions from atomic fields in a single object 117 hash >>= 16; 118 hash ^= low; 119 // Return a pointer to the word to use 120 return locks + (hash & SPINLOCK_MASK); 121 } 122 123 /// Macros for determining whether a size is lock free. Clang can not yet 124 /// codegen __atomic_is_lock_free(16), so for now we assume 16-byte values are 125 /// not lock free. 126 #define IS_LOCK_FREE_1 __c11_atomic_is_lock_free(1) 127 #define IS_LOCK_FREE_2 __c11_atomic_is_lock_free(2) 128 #define IS_LOCK_FREE_4 __c11_atomic_is_lock_free(4) 129 #define IS_LOCK_FREE_8 __c11_atomic_is_lock_free(8) 130 #define IS_LOCK_FREE_16 0 131 132 /// Macro that calls the compiler-generated lock-free versions of functions 133 /// when they exist. 134 #define LOCK_FREE_CASES() \ 135 do { \ 136 switch (size) { \ 137 case 1: \ 138 if (IS_LOCK_FREE_1) { \ 139 LOCK_FREE_ACTION(uint8_t); \ 140 } \ 141 break; \ 142 case 2: \ 143 if (IS_LOCK_FREE_2) { \ 144 LOCK_FREE_ACTION(uint16_t); \ 145 } \ 146 break; \ 147 case 4: \ 148 if (IS_LOCK_FREE_4) { \ 149 LOCK_FREE_ACTION(uint32_t); \ 150 } \ 151 break; \ 152 case 8: \ 153 if (IS_LOCK_FREE_8) { \ 154 LOCK_FREE_ACTION(uint64_t); \ 155 } \ 156 break; \ 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 break; \ 163 } \ 164 } while (0) 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 *)src, 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( \ 203 (_Atomic(type) *)ptr, (type *)expected, *(type *)desired, success, \ 204 failure) 205 LOCK_FREE_CASES(); 206 #undef LOCK_FREE_ACTION 207 Lock *l = lock_for_pointer(ptr); 208 lock(l); 209 if (memcmp(ptr, expected, size) == 0) { 210 memcpy(ptr, desired, size); 211 unlock(l); 212 return 1; 213 } 214 memcpy(expected, ptr, size); 215 unlock(l); 216 return 0; 217 } 218 219 /// Performs an atomic exchange operation between two pointers. This is atomic 220 /// with respect to the target address. 221 void __atomic_exchange_c(int size, void *ptr, void *val, void *old, int model) { 222 #define LOCK_FREE_ACTION(type) \ 223 *(type *)old = \ 224 __c11_atomic_exchange((_Atomic(type) *)ptr, *(type *)val, model); \ 225 return; 226 LOCK_FREE_CASES(); 227 #undef LOCK_FREE_ACTION 228 Lock *l = lock_for_pointer(ptr); 229 lock(l); 230 memcpy(old, ptr, size); 231 memcpy(ptr, val, size); 232 unlock(l); 233 } 234 235 //////////////////////////////////////////////////////////////////////////////// 236 // Where the size is known at compile time, the compiler may emit calls to 237 // specialised versions of the above functions. 238 //////////////////////////////////////////////////////////////////////////////// 239 #ifdef __SIZEOF_INT128__ 240 #define OPTIMISED_CASES \ 241 OPTIMISED_CASE(1, IS_LOCK_FREE_1, uint8_t) \ 242 OPTIMISED_CASE(2, IS_LOCK_FREE_2, uint16_t) \ 243 OPTIMISED_CASE(4, IS_LOCK_FREE_4, uint32_t) \ 244 OPTIMISED_CASE(8, IS_LOCK_FREE_8, uint64_t) \ 245 OPTIMISED_CASE(16, IS_LOCK_FREE_16, __uint128_t) 246 #else 247 #define OPTIMISED_CASES \ 248 OPTIMISED_CASE(1, IS_LOCK_FREE_1, uint8_t) \ 249 OPTIMISED_CASE(2, IS_LOCK_FREE_2, uint16_t) \ 250 OPTIMISED_CASE(4, IS_LOCK_FREE_4, uint32_t) \ 251 OPTIMISED_CASE(8, IS_LOCK_FREE_8, uint64_t) 252 #endif 253 254 #define OPTIMISED_CASE(n, lockfree, type) \ 255 type __atomic_load_##n(type *src, int model) { \ 256 if (lockfree) \ 257 return __c11_atomic_load((_Atomic(type) *)src, model); \ 258 Lock *l = lock_for_pointer(src); \ 259 lock(l); \ 260 type val = *src; \ 261 unlock(l); \ 262 return val; \ 263 } 264 OPTIMISED_CASES 265 #undef OPTIMISED_CASE 266 267 #define OPTIMISED_CASE(n, lockfree, type) \ 268 void __atomic_store_##n(type *dest, type val, int model) { \ 269 if (lockfree) { \ 270 __c11_atomic_store((_Atomic(type) *)dest, val, model); \ 271 return; \ 272 } \ 273 Lock *l = lock_for_pointer(dest); \ 274 lock(l); \ 275 *dest = val; \ 276 unlock(l); \ 277 return; \ 278 } 279 OPTIMISED_CASES 280 #undef OPTIMISED_CASE 281 282 #define OPTIMISED_CASE(n, lockfree, type) \ 283 type __atomic_exchange_##n(type *dest, type val, int model) { \ 284 if (lockfree) \ 285 return __c11_atomic_exchange((_Atomic(type) *)dest, val, model); \ 286 Lock *l = lock_for_pointer(dest); \ 287 lock(l); \ 288 type tmp = *dest; \ 289 *dest = val; \ 290 unlock(l); \ 291 return tmp; \ 292 } 293 OPTIMISED_CASES 294 #undef OPTIMISED_CASE 295 296 #define OPTIMISED_CASE(n, lockfree, type) \ 297 bool __atomic_compare_exchange_##n(type *ptr, type *expected, type desired, \ 298 int success, int failure) { \ 299 if (lockfree) \ 300 return __c11_atomic_compare_exchange_strong( \ 301 (_Atomic(type) *)ptr, expected, desired, success, failure); \ 302 Lock *l = lock_for_pointer(ptr); \ 303 lock(l); \ 304 if (*ptr == *expected) { \ 305 *ptr = desired; \ 306 unlock(l); \ 307 return true; \ 308 } \ 309 *expected = *ptr; \ 310 unlock(l); \ 311 return false; \ 312 } 313 OPTIMISED_CASES 314 #undef OPTIMISED_CASE 315 316 //////////////////////////////////////////////////////////////////////////////// 317 // Atomic read-modify-write operations for integers of various sizes. 318 //////////////////////////////////////////////////////////////////////////////// 319 #define ATOMIC_RMW(n, lockfree, type, opname, op) \ 320 type __atomic_fetch_##opname##_##n(type *ptr, type val, int model) { \ 321 if (lockfree) \ 322 return __c11_atomic_fetch_##opname((_Atomic(type) *)ptr, val, model); \ 323 Lock *l = lock_for_pointer(ptr); \ 324 lock(l); \ 325 type tmp = *ptr; \ 326 *ptr = tmp op val; \ 327 unlock(l); \ 328 return tmp; \ 329 } 330 331 #define OPTIMISED_CASE(n, lockfree, type) ATOMIC_RMW(n, lockfree, type, add, +) 332 OPTIMISED_CASES 333 #undef OPTIMISED_CASE 334 #define OPTIMISED_CASE(n, lockfree, type) ATOMIC_RMW(n, lockfree, type, sub, -) 335 OPTIMISED_CASES 336 #undef OPTIMISED_CASE 337 #define OPTIMISED_CASE(n, lockfree, type) ATOMIC_RMW(n, lockfree, type, and, &) 338 OPTIMISED_CASES 339 #undef OPTIMISED_CASE 340 #define OPTIMISED_CASE(n, lockfree, type) ATOMIC_RMW(n, lockfree, type, or, |) 341 OPTIMISED_CASES 342 #undef OPTIMISED_CASE 343 #define OPTIMISED_CASE(n, lockfree, type) ATOMIC_RMW(n, lockfree, type, xor, ^) 344 OPTIMISED_CASES 345 #undef OPTIMISED_CASE 346