/*===-- atomic.c - Implement support functions for atomic operations.------=== * * The LLVM Compiler Infrastructure * * This file is dual licensed under the MIT and the University of Illinois Open * Source Licenses. See LICENSE.TXT for details. * *===----------------------------------------------------------------------=== * * atomic.c defines a set of functions for performing atomic accesses on * arbitrary-sized memory locations. This design uses locks that should * be fast in the uncontended case, for two reasons: * * 1) This code must work with C programs that do not link to anything * (including pthreads) and so it should not depend on any pthread * functions. * 2) Atomic operations, rather than explicit mutexes, are most commonly used * on code where contended operations are rate. * * To avoid needing a per-object lock, this code allocates an array of * locks and hashes the object pointers to find the one that it should use. * For operations that must be atomic on two locations, the lower lock is * always acquired first, to avoid deadlock. * *===----------------------------------------------------------------------=== */ #include <stdint.h> #include <string.h> // Clang objects if you redefine a builtin. This little hack allows us to // define a function with the same name as an intrinsic. #pragma redefine_extname __atomic_load_c __atomic_load #pragma redefine_extname __atomic_store_c __atomic_store #pragma redefine_extname __atomic_exchange_c __atomic_exchange #pragma redefine_extname __atomic_compare_exchange_c __atomic_compare_exchange /// Number of locks. This allocates one page on 32-bit platforms, two on /// 64-bit. This can be specified externally if a different trade between /// memory usage and contention probability is required for a given platform. #ifndef SPINLOCK_COUNT #define SPINLOCK_COUNT (1<<10) #endif static const long SPINLOCK_MASK = SPINLOCK_COUNT - 1; //////////////////////////////////////////////////////////////////////////////// // Platform-specific lock implementation. Falls back to spinlocks if none is // defined. Each platform should define the Lock type, and corresponding // lock() and unlock() functions. //////////////////////////////////////////////////////////////////////////////// #ifdef __FreeBSD__ #include <errno.h> #include <sys/types.h> #include <machine/atomic.h> #include <sys/umtx.h> typedef struct _usem Lock; inline static void unlock(Lock *l) { __c11_atomic_store((_Atomic(uint32_t)*)&l->_count, 1, __ATOMIC_RELEASE); __c11_atomic_thread_fence(__ATOMIC_SEQ_CST); if (l->_has_waiters) _umtx_op(l, UMTX_OP_SEM_WAKE, 1, 0, 0); } inline static void lock(Lock *l) { uint32_t old = 1; while (!__c11_atomic_compare_exchange_weak((_Atomic(uint32_t)*)&l->_count, &old, 0, __ATOMIC_ACQUIRE, __ATOMIC_RELAXED)) { _umtx_op(l, UMTX_OP_SEM_WAIT, 0, 0, 0); old = 1; } } /// locks for atomic operations static Lock locks[SPINLOCK_COUNT] = { [0 ... SPINLOCK_COUNT-1] = {0,1,0} }; #else typedef _Atomic(uintptr_t) Lock; /// Unlock a lock. This is a release operation. inline static void unlock(Lock *l) { __c11_atomic_store(l, 0, __ATOMIC_RELEASE); } /// Locks a lock. In the current implementation, this is potentially /// unbounded in the contended case. inline static void lock(Lock *l) { uintptr_t old = 0; while (!__c11_atomic_compare_exchange_weak(l, &old, 1, __ATOMIC_ACQUIRE, __ATOMIC_RELAXED)) old = 0; } /// locks for atomic operations static Lock locks[SPINLOCK_COUNT]; #endif /// Returns a lock to use for a given pointer. static inline Lock *lock_for_pointer(void *ptr) { intptr_t hash = (intptr_t)ptr; // Disregard the lowest 4 bits. We want all values that may be part of the // same memory operation to hash to the same value and therefore use the same // lock. hash >>= 4; // Use the next bits as the basis for the hash intptr_t low = hash & SPINLOCK_MASK; // Now use the high(er) set of bits to perturb the hash, so that we don't // get collisions from atomic fields in a single object hash >>= 16; hash ^= low; // Return a pointer to the word to use return locks + (hash & SPINLOCK_MASK); } /// Macros for determining whether a size is lock free. Clang can not yet /// codegen __atomic_is_lock_free(16), so for now we assume 16-byte values are /// not lock free. #define IS_LOCK_FREE_1 __c11_atomic_is_lock_free(1) #define IS_LOCK_FREE_2 __c11_atomic_is_lock_free(2) #define IS_LOCK_FREE_4 __c11_atomic_is_lock_free(4) #define IS_LOCK_FREE_8 __c11_atomic_is_lock_free(8) #define IS_LOCK_FREE_16 0 /// Macro that calls the compiler-generated lock-free versions of functions /// when they exist. #define LOCK_FREE_CASES() \ do {\ switch (size) {\ case 2:\ if (IS_LOCK_FREE_2) {\ LOCK_FREE_ACTION(uint16_t);\ }\ case 4:\ if (IS_LOCK_FREE_4) {\ LOCK_FREE_ACTION(uint32_t);\ }\ case 8:\ if (IS_LOCK_FREE_8) {\ LOCK_FREE_ACTION(uint64_t);\ }\ case 16:\ if (IS_LOCK_FREE_16) {\ /* FIXME: __uint128_t isn't available on 32 bit platforms. LOCK_FREE_ACTION(__uint128_t);*/\ }\ }\ } while (0) /// An atomic load operation. This is atomic with respect to the source /// pointer only. void __atomic_load_c(int size, void *src, void *dest, int model) { #define LOCK_FREE_ACTION(type) \ *((type*)dest) = __c11_atomic_load((_Atomic(type)*)src, model);\ return; LOCK_FREE_CASES(); #undef LOCK_FREE_ACTION Lock *l = lock_for_pointer(src); lock(l); memcpy(dest, src, size); unlock(l); } /// An atomic store operation. This is atomic with respect to the destination /// pointer only. void __atomic_store_c(int size, void *dest, void *src, int model) { #define LOCK_FREE_ACTION(type) \ __c11_atomic_store((_Atomic(type)*)dest, *(type*)dest, model);\ return; LOCK_FREE_CASES(); #undef LOCK_FREE_ACTION Lock *l = lock_for_pointer(dest); lock(l); memcpy(dest, src, size); unlock(l); } /// Atomic compare and exchange operation. If the value at *ptr is identical /// to the value at *expected, then this copies value at *desired to *ptr. If /// they are not, then this stores the current value from *ptr in *expected. /// /// This function returns 1 if the exchange takes place or 0 if it fails. int __atomic_compare_exchange_c(int size, void *ptr, void *expected, void *desired, int success, int failure) { #define LOCK_FREE_ACTION(type) \ return __c11_atomic_compare_exchange_strong((_Atomic(type)*)ptr, (type*)expected,\ *(type*)desired, success, failure) LOCK_FREE_CASES(); #undef LOCK_FREE_ACTION Lock *l = lock_for_pointer(ptr); lock(l); if (memcmp(ptr, expected, size) == 0) { memcpy(ptr, desired, size); unlock(l); return 1; } memcpy(expected, ptr, size); unlock(l); return 0; } /// Performs an atomic exchange operation between two pointers. This is atomic /// with respect to the target address. void __atomic_exchange_c(int size, void *ptr, void *val, void *old, int model) { #define LOCK_FREE_ACTION(type) \ *(type*)old = __c11_atomic_exchange((_Atomic(type)*)ptr, *(type*)val,\ model);\ return; LOCK_FREE_CASES(); #undef LOCK_FREE_ACTION Lock *l = lock_for_pointer(ptr); lock(l); memcpy(old, ptr, size); memcpy(ptr, val, size); unlock(l); } //////////////////////////////////////////////////////////////////////////////// // Where the size is known at compile time, the compiler may emit calls to // specialised versions of the above functions. //////////////////////////////////////////////////////////////////////////////// #define OPTIMISED_CASES\ OPTIMISED_CASE(1, IS_LOCK_FREE_1, uint8_t)\ OPTIMISED_CASE(2, IS_LOCK_FREE_2, uint16_t)\ OPTIMISED_CASE(4, IS_LOCK_FREE_4, uint32_t)\ OPTIMISED_CASE(8, IS_LOCK_FREE_8, uint64_t)\ /* FIXME: __uint128_t isn't available on 32 bit platforms. OPTIMISED_CASE(16, IS_LOCK_FREE_16, __uint128_t)*/\ #define OPTIMISED_CASE(n, lockfree, type)\ type __atomic_load_##n(type *src, int model) {\ if (lockfree)\ return __c11_atomic_load((_Atomic(type)*)src, model);\ Lock *l = lock_for_pointer(src);\ lock(l);\ type val = *src;\ unlock(l);\ return val;\ } OPTIMISED_CASES #undef OPTIMISED_CASE #define OPTIMISED_CASE(n, lockfree, type)\ void __atomic_store_##n(type *dest, type val, int model) {\ if (lockfree) {\ __c11_atomic_store((_Atomic(type)*)dest, val, model);\ return;\ }\ Lock *l = lock_for_pointer(dest);\ lock(l);\ *dest = val;\ unlock(l);\ return;\ } OPTIMISED_CASES #undef OPTIMISED_CASE #define OPTIMISED_CASE(n, lockfree, type)\ type __atomic_exchange_##n(type *dest, type val, int model) {\ if (lockfree)\ return __c11_atomic_exchange((_Atomic(type)*)dest, val, model);\ Lock *l = lock_for_pointer(dest);\ lock(l);\ type tmp = *dest;\ *dest = val;\ unlock(l);\ return tmp;\ } OPTIMISED_CASES #undef OPTIMISED_CASE #define OPTIMISED_CASE(n, lockfree, type)\ int __atomic_compare_exchange_##n(type *ptr, type *expected, type desired,\ int success, int failure) {\ if (lockfree)\ return __c11_atomic_compare_exchange_strong((_Atomic(type)*)ptr, expected, desired,\ success, failure);\ Lock *l = lock_for_pointer(ptr);\ lock(l);\ if (*ptr == *expected) {\ *ptr = desired;\ unlock(l);\ return 1;\ }\ *expected = *ptr;\ unlock(l);\ return 0;\ } OPTIMISED_CASES #undef OPTIMISED_CASE //////////////////////////////////////////////////////////////////////////////// // Atomic read-modify-write operations for integers of various sizes. //////////////////////////////////////////////////////////////////////////////// #define ATOMIC_RMW(n, lockfree, type, opname, op) \ type __atomic_fetch_##opname##_##n(type *ptr, type val, int model) {\ if (lockfree) \ return __c11_atomic_fetch_##opname((_Atomic(type)*)ptr, val, model);\ Lock *l = lock_for_pointer(ptr);\ lock(l);\ type tmp = *ptr;\ *ptr = tmp op val;\ unlock(l);\ return tmp;\ } #define OPTIMISED_CASE(n, lockfree, type) ATOMIC_RMW(n, lockfree, type, add, +) OPTIMISED_CASES #undef OPTIMISED_CASE #define OPTIMISED_CASE(n, lockfree, type) ATOMIC_RMW(n, lockfree, type, sub, -) OPTIMISED_CASES #undef OPTIMISED_CASE #define OPTIMISED_CASE(n, lockfree, type) ATOMIC_RMW(n, lockfree, type, and, &) OPTIMISED_CASES #undef OPTIMISED_CASE #define OPTIMISED_CASE(n, lockfree, type) ATOMIC_RMW(n, lockfree, type, or, |) OPTIMISED_CASES #undef OPTIMISED_CASE #define OPTIMISED_CASE(n, lockfree, type) ATOMIC_RMW(n, lockfree, type, xor, ^) OPTIMISED_CASES #undef OPTIMISED_CASE