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 52static 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> 64typedef struct _usem Lock; 65inline 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} 71inline 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 80static Lock locks[SPINLOCK_COUNT] = { [0 ... SPINLOCK_COUNT-1] = {0,1,0} }; 81 82#elif defined(__APPLE__) 83#include <libkern/OSAtomic.h> 84typedef OSSpinLock Lock; 85inline 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. 90inline static void lock(Lock *l) { 91 OSSpinLockLock(l); 92} 93static Lock locks[SPINLOCK_COUNT]; // initialized to OS_SPINLOCK_INIT which is 0 94 95#else 96typedef _Atomic(uintptr_t) Lock; 97/// Unlock a lock. This is a release operation. 98inline 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. 103inline 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 110static Lock locks[SPINLOCK_COUNT]; 111#endif 112 113 114/// Returns a lock to use for a given pointer. 115static 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. 168void __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. 182void __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. 199int __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. 220void __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)\ 247type __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} 256OPTIMISED_CASES 257#undef OPTIMISED_CASE 258 259#define OPTIMISED_CASE(n, lockfree, type)\ 260void __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} 271OPTIMISED_CASES 272#undef OPTIMISED_CASE 273 274#define OPTIMISED_CASE(n, lockfree, type)\ 275type __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} 285OPTIMISED_CASES 286#undef OPTIMISED_CASE 287 288#define OPTIMISED_CASE(n, lockfree, type)\ 289int __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} 305OPTIMISED_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) \ 312type __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, +) 324OPTIMISED_CASES 325#undef OPTIMISED_CASE 326#define OPTIMISED_CASE(n, lockfree, type) ATOMIC_RMW(n, lockfree, type, sub, -) 327OPTIMISED_CASES 328#undef OPTIMISED_CASE 329#define OPTIMISED_CASE(n, lockfree, type) ATOMIC_RMW(n, lockfree, type, and, &) 330OPTIMISED_CASES 331#undef OPTIMISED_CASE 332#define OPTIMISED_CASE(n, lockfree, type) ATOMIC_RMW(n, lockfree, type, or, |) 333OPTIMISED_CASES 334#undef OPTIMISED_CASE 335#define OPTIMISED_CASE(n, lockfree, type) ATOMIC_RMW(n, lockfree, type, xor, ^) 336OPTIMISED_CASES 337#undef OPTIMISED_CASE 338