1238901Sandrew/*===-- atomic.c - Implement support functions for atomic operations.------=== 2238901Sandrew * 3238901Sandrew * The LLVM Compiler Infrastructure 4238901Sandrew * 5238901Sandrew * This file is dual licensed under the MIT and the University of Illinois Open 6238901Sandrew * Source Licenses. See LICENSE.TXT for details. 7238901Sandrew * 8238901Sandrew *===----------------------------------------------------------------------=== 9238901Sandrew * 10238901Sandrew * atomic.c defines a set of functions for performing atomic accesses on 11238901Sandrew * arbitrary-sized memory locations. This design uses locks that should 12238901Sandrew * be fast in the uncontended case, for two reasons: 13238901Sandrew * 14238901Sandrew * 1) This code must work with C programs that do not link to anything 15238901Sandrew * (including pthreads) and so it should not depend on any pthread 16238901Sandrew * functions. 17238901Sandrew * 2) Atomic operations, rather than explicit mutexes, are most commonly used 18238901Sandrew * on code where contended operations are rate. 19238901Sandrew * 20238901Sandrew * To avoid needing a per-object lock, this code allocates an array of 21238901Sandrew * locks and hashes the object pointers to find the one that it should use. 22238901Sandrew * For operations that must be atomic on two locations, the lower lock is 23238901Sandrew * always acquired first, to avoid deadlock. 24238901Sandrew * 25238901Sandrew *===----------------------------------------------------------------------=== 26238901Sandrew */ 27238901Sandrew 28238901Sandrew#include <stdint.h> 29238901Sandrew#include <string.h> 30238901Sandrew 31238901Sandrew// Clang objects if you redefine a builtin. This little hack allows us to 32238901Sandrew// define a function with the same name as an intrinsic. 33238901Sandrew#pragma redefine_extname __atomic_load_c __atomic_load 34238901Sandrew#pragma redefine_extname __atomic_store_c __atomic_store 35238901Sandrew#pragma redefine_extname __atomic_exchange_c __atomic_exchange 36238901Sandrew#pragma redefine_extname __atomic_compare_exchange_c __atomic_compare_exchange 37238901Sandrew 38238901Sandrew/// Number of locks. This allocates one page on 32-bit platforms, two on 39238901Sandrew/// 64-bit. This can be specified externally if a different trade between 40238901Sandrew/// memory usage and contention probability is required for a given platform. 41238901Sandrew#ifndef SPINLOCK_COUNT 42238901Sandrew#define SPINLOCK_COUNT (1<<10) 43238901Sandrew#endif 44238901Sandrewstatic const long SPINLOCK_MASK = SPINLOCK_COUNT - 1; 45238901Sandrew 46238901Sandrew//////////////////////////////////////////////////////////////////////////////// 47238901Sandrew// Platform-specific lock implementation. Falls back to spinlocks if none is 48238901Sandrew// defined. Each platform should define the Lock type, and corresponding 49238901Sandrew// lock() and unlock() functions. 50238901Sandrew//////////////////////////////////////////////////////////////////////////////// 51238901Sandrew#ifdef __FreeBSD__ 52238901Sandrew#include <errno.h> 53238901Sandrew#include <sys/types.h> 54238901Sandrew#include <machine/atomic.h> 55238901Sandrew#include <sys/umtx.h> 56238901Sandrewtypedef struct _usem Lock; 57238901Sandrewinline static void unlock(Lock *l) { 58238901Sandrew __c11_atomic_store((_Atomic(uint32_t)*)&l->_count, 1, __ATOMIC_RELEASE); 59238901Sandrew __c11_atomic_thread_fence(__ATOMIC_SEQ_CST); 60238901Sandrew if (l->_has_waiters) 61238901Sandrew _umtx_op(l, UMTX_OP_SEM_WAKE, 1, 0, 0); 62238901Sandrew} 63238901Sandrewinline static void lock(Lock *l) { 64238901Sandrew uint32_t old = 1; 65238901Sandrew while (!__c11_atomic_compare_exchange_weak((_Atomic(uint32_t)*)&l->_count, &old, 66238901Sandrew 0, __ATOMIC_ACQUIRE, __ATOMIC_RELAXED)) { 67238901Sandrew _umtx_op(l, UMTX_OP_SEM_WAIT, 0, 0, 0); 68238901Sandrew old = 1; 69238901Sandrew } 70238901Sandrew} 71238901Sandrew/// locks for atomic operations 72238901Sandrewstatic Lock locks[SPINLOCK_COUNT] = { [0 ... SPINLOCK_COUNT-1] = {0,1,0} }; 73238901Sandrew#else 74238901Sandrewtypedef _Atomic(uintptr_t) Lock; 75238901Sandrew/// Unlock a lock. This is a release operation. 76238901Sandrewinline static void unlock(Lock *l) { 77238901Sandrew __c11_atomic_store(l, 0, __ATOMIC_RELEASE); 78238901Sandrew} 79238901Sandrew/// Locks a lock. In the current implementation, this is potentially 80238901Sandrew/// unbounded in the contended case. 81238901Sandrewinline static void lock(Lock *l) { 82238901Sandrew uintptr_t old = 0; 83238901Sandrew while (!__c11_atomic_compare_exchange_weak(l, &old, 1, __ATOMIC_ACQUIRE, 84238901Sandrew __ATOMIC_RELAXED)) 85238901Sandrew old = 0; 86238901Sandrew} 87238901Sandrew/// locks for atomic operations 88238901Sandrewstatic Lock locks[SPINLOCK_COUNT]; 89238901Sandrew#endif 90238901Sandrew 91238901Sandrew 92238901Sandrew/// Returns a lock to use for a given pointer. 93238901Sandrewstatic inline Lock *lock_for_pointer(void *ptr) { 94238901Sandrew intptr_t hash = (intptr_t)ptr; 95238901Sandrew // Disregard the lowest 4 bits. We want all values that may be part of the 96238901Sandrew // same memory operation to hash to the same value and therefore use the same 97238901Sandrew // lock. 98238901Sandrew hash >>= 4; 99238901Sandrew // Use the next bits as the basis for the hash 100238901Sandrew intptr_t low = hash & SPINLOCK_MASK; 101238901Sandrew // Now use the high(er) set of bits to perturb the hash, so that we don't 102238901Sandrew // get collisions from atomic fields in a single object 103238901Sandrew hash >>= 16; 104238901Sandrew hash ^= low; 105238901Sandrew // Return a pointer to the word to use 106238901Sandrew return locks + (hash & SPINLOCK_MASK); 107238901Sandrew} 108238901Sandrew 109238901Sandrew/// Macros for determining whether a size is lock free. Clang can not yet 110238901Sandrew/// codegen __atomic_is_lock_free(16), so for now we assume 16-byte values are 111238901Sandrew/// not lock free. 112238901Sandrew#define IS_LOCK_FREE_1 __c11_atomic_is_lock_free(1) 113238901Sandrew#define IS_LOCK_FREE_2 __c11_atomic_is_lock_free(2) 114238901Sandrew#define IS_LOCK_FREE_4 __c11_atomic_is_lock_free(4) 115238901Sandrew#define IS_LOCK_FREE_8 __c11_atomic_is_lock_free(8) 116238901Sandrew#define IS_LOCK_FREE_16 0 117238901Sandrew 118238901Sandrew/// Macro that calls the compiler-generated lock-free versions of functions 119238901Sandrew/// when they exist. 120238901Sandrew#define LOCK_FREE_CASES() \ 121238901Sandrew do {\ 122238901Sandrew switch (size) {\ 123238901Sandrew case 2:\ 124238901Sandrew if (IS_LOCK_FREE_2) {\ 125238901Sandrew LOCK_FREE_ACTION(uint16_t);\ 126238901Sandrew }\ 127238901Sandrew case 4:\ 128238901Sandrew if (IS_LOCK_FREE_4) {\ 129238901Sandrew LOCK_FREE_ACTION(uint32_t);\ 130238901Sandrew }\ 131238901Sandrew case 8:\ 132238901Sandrew if (IS_LOCK_FREE_8) {\ 133238901Sandrew LOCK_FREE_ACTION(uint64_t);\ 134238901Sandrew }\ 135238901Sandrew case 16:\ 136238901Sandrew if (IS_LOCK_FREE_16) {\ 137238901Sandrew /* FIXME: __uint128_t isn't available on 32 bit platforms. 138238901Sandrew LOCK_FREE_ACTION(__uint128_t);*/\ 139238901Sandrew }\ 140238901Sandrew }\ 141238901Sandrew } while (0) 142238901Sandrew 143238901Sandrew 144238901Sandrew/// An atomic load operation. This is atomic with respect to the source 145238901Sandrew/// pointer only. 146238901Sandrewvoid __atomic_load_c(int size, void *src, void *dest, int model) { 147238901Sandrew#define LOCK_FREE_ACTION(type) \ 148238901Sandrew *((type*)dest) = __c11_atomic_load((_Atomic(type)*)src, model);\ 149238901Sandrew return; 150238901Sandrew LOCK_FREE_CASES(); 151238901Sandrew#undef LOCK_FREE_ACTION 152238901Sandrew Lock *l = lock_for_pointer(src); 153238901Sandrew lock(l); 154238901Sandrew memcpy(dest, src, size); 155238901Sandrew unlock(l); 156238901Sandrew} 157238901Sandrew 158238901Sandrew/// An atomic store operation. This is atomic with respect to the destination 159238901Sandrew/// pointer only. 160238901Sandrewvoid __atomic_store_c(int size, void *dest, void *src, int model) { 161238901Sandrew#define LOCK_FREE_ACTION(type) \ 162238901Sandrew __c11_atomic_store((_Atomic(type)*)dest, *(type*)dest, model);\ 163238901Sandrew return; 164238901Sandrew LOCK_FREE_CASES(); 165238901Sandrew#undef LOCK_FREE_ACTION 166238901Sandrew Lock *l = lock_for_pointer(dest); 167238901Sandrew lock(l); 168238901Sandrew memcpy(dest, src, size); 169238901Sandrew unlock(l); 170238901Sandrew} 171238901Sandrew 172238901Sandrew/// Atomic compare and exchange operation. If the value at *ptr is identical 173238901Sandrew/// to the value at *expected, then this copies value at *desired to *ptr. If 174238901Sandrew/// they are not, then this stores the current value from *ptr in *expected. 175238901Sandrew/// 176238901Sandrew/// This function returns 1 if the exchange takes place or 0 if it fails. 177238901Sandrewint __atomic_compare_exchange_c(int size, void *ptr, void *expected, 178238901Sandrew void *desired, int success, int failure) { 179238901Sandrew#define LOCK_FREE_ACTION(type) \ 180238901Sandrew return __c11_atomic_compare_exchange_strong((_Atomic(type)*)ptr, (type*)expected,\ 181238901Sandrew *(type*)desired, success, failure) 182238901Sandrew LOCK_FREE_CASES(); 183238901Sandrew#undef LOCK_FREE_ACTION 184238901Sandrew Lock *l = lock_for_pointer(ptr); 185238901Sandrew lock(l); 186238901Sandrew if (memcmp(ptr, expected, size) == 0) { 187238901Sandrew memcpy(ptr, desired, size); 188238901Sandrew unlock(l); 189238901Sandrew return 1; 190238901Sandrew } 191238901Sandrew memcpy(expected, ptr, size); 192238901Sandrew unlock(l); 193238901Sandrew return 0; 194238901Sandrew} 195238901Sandrew 196238901Sandrew/// Performs an atomic exchange operation between two pointers. This is atomic 197238901Sandrew/// with respect to the target address. 198238901Sandrewvoid __atomic_exchange_c(int size, void *ptr, void *val, void *old, int model) { 199238901Sandrew#define LOCK_FREE_ACTION(type) \ 200238901Sandrew *(type*)old = __c11_atomic_exchange((_Atomic(type)*)ptr, *(type*)val,\ 201238901Sandrew model);\ 202238901Sandrew return; 203238901Sandrew LOCK_FREE_CASES(); 204238901Sandrew#undef LOCK_FREE_ACTION 205238901Sandrew Lock *l = lock_for_pointer(ptr); 206238901Sandrew lock(l); 207238901Sandrew memcpy(old, ptr, size); 208238901Sandrew memcpy(ptr, val, size); 209238901Sandrew unlock(l); 210238901Sandrew} 211238901Sandrew 212238901Sandrew//////////////////////////////////////////////////////////////////////////////// 213238901Sandrew// Where the size is known at compile time, the compiler may emit calls to 214238901Sandrew// specialised versions of the above functions. 215238901Sandrew//////////////////////////////////////////////////////////////////////////////// 216238901Sandrew#define OPTIMISED_CASES\ 217238901Sandrew OPTIMISED_CASE(1, IS_LOCK_FREE_1, uint8_t)\ 218238901Sandrew OPTIMISED_CASE(2, IS_LOCK_FREE_2, uint16_t)\ 219238901Sandrew OPTIMISED_CASE(4, IS_LOCK_FREE_4, uint32_t)\ 220238901Sandrew OPTIMISED_CASE(8, IS_LOCK_FREE_8, uint64_t)\ 221238901Sandrew /* FIXME: __uint128_t isn't available on 32 bit platforms. 222238901Sandrew OPTIMISED_CASE(16, IS_LOCK_FREE_16, __uint128_t)*/\ 223238901Sandrew 224238901Sandrew#define OPTIMISED_CASE(n, lockfree, type)\ 225238901Sandrewtype __atomic_load_##n(type *src, int model) {\ 226238901Sandrew if (lockfree)\ 227238901Sandrew return __c11_atomic_load((_Atomic(type)*)src, model);\ 228238901Sandrew Lock *l = lock_for_pointer(src);\ 229238901Sandrew lock(l);\ 230238901Sandrew type val = *src;\ 231238901Sandrew unlock(l);\ 232238901Sandrew return val;\ 233238901Sandrew} 234238901SandrewOPTIMISED_CASES 235238901Sandrew#undef OPTIMISED_CASE 236238901Sandrew 237238901Sandrew#define OPTIMISED_CASE(n, lockfree, type)\ 238238901Sandrewvoid __atomic_store_##n(type *dest, type val, int model) {\ 239238901Sandrew if (lockfree) {\ 240238901Sandrew __c11_atomic_store((_Atomic(type)*)dest, val, model);\ 241238901Sandrew return;\ 242238901Sandrew }\ 243238901Sandrew Lock *l = lock_for_pointer(dest);\ 244238901Sandrew lock(l);\ 245238901Sandrew *dest = val;\ 246238901Sandrew unlock(l);\ 247238901Sandrew return;\ 248238901Sandrew} 249238901SandrewOPTIMISED_CASES 250238901Sandrew#undef OPTIMISED_CASE 251238901Sandrew 252238901Sandrew#define OPTIMISED_CASE(n, lockfree, type)\ 253238901Sandrewtype __atomic_exchange_##n(type *dest, type val, int model) {\ 254238901Sandrew if (lockfree)\ 255238901Sandrew return __c11_atomic_exchange((_Atomic(type)*)dest, val, model);\ 256238901Sandrew Lock *l = lock_for_pointer(dest);\ 257238901Sandrew lock(l);\ 258238901Sandrew type tmp = *dest;\ 259238901Sandrew *dest = val;\ 260238901Sandrew unlock(l);\ 261238901Sandrew return tmp;\ 262238901Sandrew} 263238901SandrewOPTIMISED_CASES 264238901Sandrew#undef OPTIMISED_CASE 265238901Sandrew 266238901Sandrew#define OPTIMISED_CASE(n, lockfree, type)\ 267238901Sandrewint __atomic_compare_exchange_##n(type *ptr, type *expected, type desired,\ 268238901Sandrew int success, int failure) {\ 269238901Sandrew if (lockfree)\ 270238901Sandrew return __c11_atomic_compare_exchange_strong((_Atomic(type)*)ptr, expected, desired,\ 271238901Sandrew success, failure);\ 272238901Sandrew Lock *l = lock_for_pointer(ptr);\ 273238901Sandrew lock(l);\ 274238901Sandrew if (*ptr == *expected) {\ 275238901Sandrew *ptr = desired;\ 276238901Sandrew unlock(l);\ 277238901Sandrew return 1;\ 278238901Sandrew }\ 279238901Sandrew *expected = *ptr;\ 280238901Sandrew unlock(l);\ 281238901Sandrew return 0;\ 282238901Sandrew} 283238901SandrewOPTIMISED_CASES 284238901Sandrew#undef OPTIMISED_CASE 285238901Sandrew 286238901Sandrew//////////////////////////////////////////////////////////////////////////////// 287238901Sandrew// Atomic read-modify-write operations for integers of various sizes. 288238901Sandrew//////////////////////////////////////////////////////////////////////////////// 289238901Sandrew#define ATOMIC_RMW(n, lockfree, type, opname, op) \ 290238901Sandrewtype __atomic_fetch_##opname##_##n(type *ptr, type val, int model) {\ 291238901Sandrew if (lockfree) \ 292238901Sandrew return __c11_atomic_fetch_##opname((_Atomic(type)*)ptr, val, model);\ 293238901Sandrew Lock *l = lock_for_pointer(ptr);\ 294238901Sandrew lock(l);\ 295238901Sandrew type tmp = *ptr;\ 296238901Sandrew *ptr = tmp op val;\ 297238901Sandrew unlock(l);\ 298238901Sandrew return tmp;\ 299238901Sandrew} 300238901Sandrew 301238901Sandrew#define OPTIMISED_CASE(n, lockfree, type) ATOMIC_RMW(n, lockfree, type, add, +) 302238901SandrewOPTIMISED_CASES 303238901Sandrew#undef OPTIMISED_CASE 304238901Sandrew#define OPTIMISED_CASE(n, lockfree, type) ATOMIC_RMW(n, lockfree, type, sub, -) 305238901SandrewOPTIMISED_CASES 306238901Sandrew#undef OPTIMISED_CASE 307238901Sandrew#define OPTIMISED_CASE(n, lockfree, type) ATOMIC_RMW(n, lockfree, type, and, &) 308238901SandrewOPTIMISED_CASES 309238901Sandrew#undef OPTIMISED_CASE 310238901Sandrew#define OPTIMISED_CASE(n, lockfree, type) ATOMIC_RMW(n, lockfree, type, or, |) 311238901SandrewOPTIMISED_CASES 312238901Sandrew#undef OPTIMISED_CASE 313238901Sandrew#define OPTIMISED_CASE(n, lockfree, type) ATOMIC_RMW(n, lockfree, type, xor, ^) 314238901SandrewOPTIMISED_CASES 315238901Sandrew#undef OPTIMISED_CASE 316