atomic.c revision 238901
164562Sgshapiro/*===-- atomic.c - Implement support functions for atomic operations.------=== 264562Sgshapiro * 364562Sgshapiro * The LLVM Compiler Infrastructure 464562Sgshapiro * 564562Sgshapiro * This file is dual licensed under the MIT and the University of Illinois Open 664562Sgshapiro * Source Licenses. See LICENSE.TXT for details. 764562Sgshapiro * 864562Sgshapiro *===----------------------------------------------------------------------=== 964562Sgshapiro * 1064562Sgshapiro * atomic.c defines a set of functions for performing atomic accesses on 1164562Sgshapiro * arbitrary-sized memory locations. This design uses locks that should 1264562Sgshapiro * be fast in the uncontended case, for two reasons: 1364562Sgshapiro * 1464562Sgshapiro * 1) This code must work with C programs that do not link to anything 1564562Sgshapiro * (including pthreads) and so it should not depend on any pthread 1664562Sgshapiro * functions. 1764562Sgshapiro * 2) Atomic operations, rather than explicit mutexes, are most commonly used 1864562Sgshapiro * on code where contended operations are rate. 1964562Sgshapiro * 2064562Sgshapiro * To avoid needing a per-object lock, this code allocates an array of 2164562Sgshapiro * locks and hashes the object pointers to find the one that it should use. 2264562Sgshapiro * For operations that must be atomic on two locations, the lower lock is 2364562Sgshapiro * always acquired first, to avoid deadlock. 2464562Sgshapiro * 2564562Sgshapiro *===----------------------------------------------------------------------=== 2664562Sgshapiro */ 2764562Sgshapiro 2864562Sgshapiro#include <stdint.h> 2964562Sgshapiro#include <string.h> 3064562Sgshapiro 3164562Sgshapiro// Clang objects if you redefine a builtin. This little hack allows us to 3264562Sgshapiro// define a function with the same name as an intrinsic. 3364562Sgshapiro#pragma redefine_extname __atomic_load_c __atomic_load 3464562Sgshapiro#pragma redefine_extname __atomic_store_c __atomic_store 3564562Sgshapiro#pragma redefine_extname __atomic_exchange_c __atomic_exchange 3664562Sgshapiro#pragma redefine_extname __atomic_compare_exchange_c __atomic_compare_exchange 3764562Sgshapiro 3864562Sgshapiro/// Number of locks. This allocates one page on 32-bit platforms, two on 3964562Sgshapiro/// 64-bit. This can be specified externally if a different trade between 4064562Sgshapiro/// memory usage and contention probability is required for a given platform. 4164562Sgshapiro#ifndef SPINLOCK_COUNT 4264562Sgshapiro#define SPINLOCK_COUNT (1<<10) 4364562Sgshapiro#endif 4464562Sgshapirostatic const long SPINLOCK_MASK = SPINLOCK_COUNT - 1; 4564562Sgshapiro 4664562Sgshapiro//////////////////////////////////////////////////////////////////////////////// 4764562Sgshapiro// Platform-specific lock implementation. Falls back to spinlocks if none is 4864562Sgshapiro// defined. Each platform should define the Lock type, and corresponding 4964562Sgshapiro// lock() and unlock() functions. 5064562Sgshapiro//////////////////////////////////////////////////////////////////////////////// 5164562Sgshapiro#ifdef __FreeBSD__ 5264562Sgshapiro#include <errno.h> 5364562Sgshapiro#include <sys/types.h> 5464562Sgshapiro#include <machine/atomic.h> 5564562Sgshapiro#include <sys/umtx.h> 5664562Sgshapirotypedef struct _usem Lock; 5764562Sgshapiroinline static void unlock(Lock *l) { 5864562Sgshapiro __c11_atomic_store((_Atomic(uint32_t)*)&l->_count, 1, __ATOMIC_RELEASE); 5964562Sgshapiro __c11_atomic_thread_fence(__ATOMIC_SEQ_CST); 6064562Sgshapiro if (l->_has_waiters) 6164562Sgshapiro _umtx_op(l, UMTX_OP_SEM_WAKE, 1, 0, 0); 6264562Sgshapiro} 6364562Sgshapiroinline static void lock(Lock *l) { 6464562Sgshapiro uint32_t old = 1; 6564562Sgshapiro while (!__c11_atomic_compare_exchange_weak((_Atomic(uint32_t)*)&l->_count, &old, 6664562Sgshapiro 0, __ATOMIC_ACQUIRE, __ATOMIC_RELAXED)) { 6764562Sgshapiro _umtx_op(l, UMTX_OP_SEM_WAIT, 0, 0, 0); 6864562Sgshapiro old = 1; 6964562Sgshapiro } 7064562Sgshapiro} 7164562Sgshapiro/// locks for atomic operations 7264562Sgshapirostatic Lock locks[SPINLOCK_COUNT] = { [0 ... SPINLOCK_COUNT-1] = {0,1,0} }; 7364562Sgshapiro#else 7464562Sgshapirotypedef _Atomic(uintptr_t) Lock; 7564562Sgshapiro/// Unlock a lock. This is a release operation. 7664562Sgshapiroinline static void unlock(Lock *l) { 7764562Sgshapiro __c11_atomic_store(l, 0, __ATOMIC_RELEASE); 7864562Sgshapiro} 7964562Sgshapiro/// Locks a lock. In the current implementation, this is potentially 8064562Sgshapiro/// unbounded in the contended case. 8164562Sgshapiroinline static void lock(Lock *l) { 8264562Sgshapiro uintptr_t old = 0; 8364562Sgshapiro while (!__c11_atomic_compare_exchange_weak(l, &old, 1, __ATOMIC_ACQUIRE, 8464562Sgshapiro __ATOMIC_RELAXED)) 8564562Sgshapiro old = 0; 8664562Sgshapiro} 8764562Sgshapiro/// locks for atomic operations 8864562Sgshapirostatic Lock locks[SPINLOCK_COUNT]; 8964562Sgshapiro#endif 9064562Sgshapiro 9164562Sgshapiro 9264562Sgshapiro/// Returns a lock to use for a given pointer. 9364562Sgshapirostatic inline Lock *lock_for_pointer(void *ptr) { 9464562Sgshapiro intptr_t hash = (intptr_t)ptr; 9564562Sgshapiro // Disregard the lowest 4 bits. We want all values that may be part of the 9664562Sgshapiro // same memory operation to hash to the same value and therefore use the same 9764562Sgshapiro // lock. 9864562Sgshapiro hash >>= 4; 9964562Sgshapiro // Use the next bits as the basis for the hash 10064562Sgshapiro intptr_t low = hash & SPINLOCK_MASK; 10164562Sgshapiro // Now use the high(er) set of bits to perturb the hash, so that we don't 10264562Sgshapiro // get collisions from atomic fields in a single object 10364562Sgshapiro hash >>= 16; 10464562Sgshapiro hash ^= low; 10564562Sgshapiro // Return a pointer to the word to use 10664562Sgshapiro return locks + (hash & SPINLOCK_MASK); 10764562Sgshapiro} 108 109/// Macros for determining whether a size is lock free. Clang can not yet 110/// codegen __atomic_is_lock_free(16), so for now we assume 16-byte values are 111/// not lock free. 112#define IS_LOCK_FREE_1 __c11_atomic_is_lock_free(1) 113#define IS_LOCK_FREE_2 __c11_atomic_is_lock_free(2) 114#define IS_LOCK_FREE_4 __c11_atomic_is_lock_free(4) 115#define IS_LOCK_FREE_8 __c11_atomic_is_lock_free(8) 116#define IS_LOCK_FREE_16 0 117 118/// Macro that calls the compiler-generated lock-free versions of functions 119/// when they exist. 120#define LOCK_FREE_CASES() \ 121 do {\ 122 switch (size) {\ 123 case 2:\ 124 if (IS_LOCK_FREE_2) {\ 125 LOCK_FREE_ACTION(uint16_t);\ 126 }\ 127 case 4:\ 128 if (IS_LOCK_FREE_4) {\ 129 LOCK_FREE_ACTION(uint32_t);\ 130 }\ 131 case 8:\ 132 if (IS_LOCK_FREE_8) {\ 133 LOCK_FREE_ACTION(uint64_t);\ 134 }\ 135 case 16:\ 136 if (IS_LOCK_FREE_16) {\ 137 /* FIXME: __uint128_t isn't available on 32 bit platforms. 138 LOCK_FREE_ACTION(__uint128_t);*/\ 139 }\ 140 }\ 141 } while (0) 142 143 144/// An atomic load operation. This is atomic with respect to the source 145/// pointer only. 146void __atomic_load_c(int size, void *src, void *dest, int model) { 147#define LOCK_FREE_ACTION(type) \ 148 *((type*)dest) = __c11_atomic_load((_Atomic(type)*)src, model);\ 149 return; 150 LOCK_FREE_CASES(); 151#undef LOCK_FREE_ACTION 152 Lock *l = lock_for_pointer(src); 153 lock(l); 154 memcpy(dest, src, size); 155 unlock(l); 156} 157 158/// An atomic store operation. This is atomic with respect to the destination 159/// pointer only. 160void __atomic_store_c(int size, void *dest, void *src, int model) { 161#define LOCK_FREE_ACTION(type) \ 162 __c11_atomic_store((_Atomic(type)*)dest, *(type*)dest, model);\ 163 return; 164 LOCK_FREE_CASES(); 165#undef LOCK_FREE_ACTION 166 Lock *l = lock_for_pointer(dest); 167 lock(l); 168 memcpy(dest, src, size); 169 unlock(l); 170} 171 172/// Atomic compare and exchange operation. If the value at *ptr is identical 173/// to the value at *expected, then this copies value at *desired to *ptr. If 174/// they are not, then this stores the current value from *ptr in *expected. 175/// 176/// This function returns 1 if the exchange takes place or 0 if it fails. 177int __atomic_compare_exchange_c(int size, void *ptr, void *expected, 178 void *desired, int success, int failure) { 179#define LOCK_FREE_ACTION(type) \ 180 return __c11_atomic_compare_exchange_strong((_Atomic(type)*)ptr, (type*)expected,\ 181 *(type*)desired, success, failure) 182 LOCK_FREE_CASES(); 183#undef LOCK_FREE_ACTION 184 Lock *l = lock_for_pointer(ptr); 185 lock(l); 186 if (memcmp(ptr, expected, size) == 0) { 187 memcpy(ptr, desired, size); 188 unlock(l); 189 return 1; 190 } 191 memcpy(expected, ptr, size); 192 unlock(l); 193 return 0; 194} 195 196/// Performs an atomic exchange operation between two pointers. This is atomic 197/// with respect to the target address. 198void __atomic_exchange_c(int size, void *ptr, void *val, void *old, int model) { 199#define LOCK_FREE_ACTION(type) \ 200 *(type*)old = __c11_atomic_exchange((_Atomic(type)*)ptr, *(type*)val,\ 201 model);\ 202 return; 203 LOCK_FREE_CASES(); 204#undef LOCK_FREE_ACTION 205 Lock *l = lock_for_pointer(ptr); 206 lock(l); 207 memcpy(old, ptr, size); 208 memcpy(ptr, val, size); 209 unlock(l); 210} 211 212//////////////////////////////////////////////////////////////////////////////// 213// Where the size is known at compile time, the compiler may emit calls to 214// specialised versions of the above functions. 215//////////////////////////////////////////////////////////////////////////////// 216#define OPTIMISED_CASES\ 217 OPTIMISED_CASE(1, IS_LOCK_FREE_1, uint8_t)\ 218 OPTIMISED_CASE(2, IS_LOCK_FREE_2, uint16_t)\ 219 OPTIMISED_CASE(4, IS_LOCK_FREE_4, uint32_t)\ 220 OPTIMISED_CASE(8, IS_LOCK_FREE_8, uint64_t)\ 221 /* FIXME: __uint128_t isn't available on 32 bit platforms. 222 OPTIMISED_CASE(16, IS_LOCK_FREE_16, __uint128_t)*/\ 223 224#define OPTIMISED_CASE(n, lockfree, type)\ 225type __atomic_load_##n(type *src, int model) {\ 226 if (lockfree)\ 227 return __c11_atomic_load((_Atomic(type)*)src, model);\ 228 Lock *l = lock_for_pointer(src);\ 229 lock(l);\ 230 type val = *src;\ 231 unlock(l);\ 232 return val;\ 233} 234OPTIMISED_CASES 235#undef OPTIMISED_CASE 236 237#define OPTIMISED_CASE(n, lockfree, type)\ 238void __atomic_store_##n(type *dest, type val, int model) {\ 239 if (lockfree) {\ 240 __c11_atomic_store((_Atomic(type)*)dest, val, model);\ 241 return;\ 242 }\ 243 Lock *l = lock_for_pointer(dest);\ 244 lock(l);\ 245 *dest = val;\ 246 unlock(l);\ 247 return;\ 248} 249OPTIMISED_CASES 250#undef OPTIMISED_CASE 251 252#define OPTIMISED_CASE(n, lockfree, type)\ 253type __atomic_exchange_##n(type *dest, type val, int model) {\ 254 if (lockfree)\ 255 return __c11_atomic_exchange((_Atomic(type)*)dest, val, model);\ 256 Lock *l = lock_for_pointer(dest);\ 257 lock(l);\ 258 type tmp = *dest;\ 259 *dest = val;\ 260 unlock(l);\ 261 return tmp;\ 262} 263OPTIMISED_CASES 264#undef OPTIMISED_CASE 265 266#define OPTIMISED_CASE(n, lockfree, type)\ 267int __atomic_compare_exchange_##n(type *ptr, type *expected, type desired,\ 268 int success, int failure) {\ 269 if (lockfree)\ 270 return __c11_atomic_compare_exchange_strong((_Atomic(type)*)ptr, expected, desired,\ 271 success, failure);\ 272 Lock *l = lock_for_pointer(ptr);\ 273 lock(l);\ 274 if (*ptr == *expected) {\ 275 *ptr = desired;\ 276 unlock(l);\ 277 return 1;\ 278 }\ 279 *expected = *ptr;\ 280 unlock(l);\ 281 return 0;\ 282} 283OPTIMISED_CASES 284#undef OPTIMISED_CASE 285 286//////////////////////////////////////////////////////////////////////////////// 287// Atomic read-modify-write operations for integers of various sizes. 288//////////////////////////////////////////////////////////////////////////////// 289#define ATOMIC_RMW(n, lockfree, type, opname, op) \ 290type __atomic_fetch_##opname##_##n(type *ptr, type val, int model) {\ 291 if (lockfree) \ 292 return __c11_atomic_fetch_##opname((_Atomic(type)*)ptr, val, model);\ 293 Lock *l = lock_for_pointer(ptr);\ 294 lock(l);\ 295 type tmp = *ptr;\ 296 *ptr = tmp op val;\ 297 unlock(l);\ 298 return tmp;\ 299} 300 301#define OPTIMISED_CASE(n, lockfree, type) ATOMIC_RMW(n, lockfree, type, add, +) 302OPTIMISED_CASES 303#undef OPTIMISED_CASE 304#define OPTIMISED_CASE(n, lockfree, type) ATOMIC_RMW(n, lockfree, type, sub, -) 305OPTIMISED_CASES 306#undef OPTIMISED_CASE 307#define OPTIMISED_CASE(n, lockfree, type) ATOMIC_RMW(n, lockfree, type, and, &) 308OPTIMISED_CASES 309#undef OPTIMISED_CASE 310#define OPTIMISED_CASE(n, lockfree, type) ATOMIC_RMW(n, lockfree, type, or, |) 311OPTIMISED_CASES 312#undef OPTIMISED_CASE 313#define OPTIMISED_CASE(n, lockfree, type) ATOMIC_RMW(n, lockfree, type, xor, ^) 314OPTIMISED_CASES 315#undef OPTIMISED_CASE 316