#include #include #include "stdatomic-impl.h" #include "atomic_generic.h" #include "libc.h" #ifdef HASH_STAT # include # include #endif /* This is compatible with musl's internal locks. */ /* The lock itself must be lock-free, so in general the can only be an atomic_flag if we know nothing else about the platform. */ typedef int volatile __impl_lock[2]; /* the size of this table has a trade off between the probability of collisions (the bigger the table, the better) and the waste of space (the smaller, the better). */ #ifndef HBIT # define HBIT 8 #endif /* len is a power of two such that we just can mask out higher bits */ enum { LEN = 1< 8*HBIT) x ^= (x / (len*len*len*len*len*len*len*len)); if (ptrbit > 4*HBIT) x ^= (x / (len*len*len*len)); if (ptrbit > 2*HBIT) x ^= (x / (len*len)); if (ptrbit > 1*HBIT) x ^= (x / len); x %= len; #ifdef HASH_STAT atomic_fetch_add_explicit(&draw[x], 1, memory_order_relaxed); #endif return x; } __attribute__((__unused__)) static unsigned __impl_jenkins_one_at_a_time_hash(void volatile const* k) { union { unsigned char b[sizeof k]; uintptr_t v; void volatile const* k; } key = { .k = k, }; uintptr_t i, x = 0; for(i = 0; i < sizeof(uintptr_t); ++i) { x += key.b[i]; x += (x << 10); x ^= (x >> 6); } x += (x << 3); x ^= (x >> 11); x += (x << 15); x %= LEN; #ifdef HASH_STAT atomic_fetch_add_explicit(&draw[x], 1, memory_order_relaxed); #endif return x; } __attribute__((__unused__)) static uintptr_t __impl_mix(void volatile const* x) { uintptr_t h = (uintptr_t)x; h ^= h >> 16; h *= 0x85ebca6b; h ^= h >> 13; h *= 0xc2b2ae35; h ^= h >> 16; h %= LEN; #ifdef HASH_STAT atomic_fetch_add_explicit(&draw[h], 1, memory_order_relaxed); #endif return h; } __attribute__((__unused__)) static uintptr_t __impl_8(void volatile const* x) { uintptr_t h = (uintptr_t)x; h ^= (h >> 8); h %= LEN; #ifdef HASH_STAT atomic_fetch_add_explicit(&draw[h], 1, memory_order_relaxed); #endif return h; } #ifndef __ATOMIC_HASH # define __ATOMIC_HASH __impl_hash #endif #define hash __ATOMIC_HASH void __impl_load (size_t size, void volatile* ptr, void volatile* ret, int mo) { unsigned pos = hash(ptr); LOCK(table[pos]); if (mo == memory_order_seq_cst) atomic_thread_fence(memory_order_seq_cst); memcpy((void*)ret, (void*)ptr, size); UNLOCK(table[pos]); } void __impl_store (size_t size, void volatile* ptr, void const volatile* val, int mo) { unsigned pos = hash(ptr); LOCK(table[pos]); memcpy((void*)ptr, (void*)val, size); if (mo == memory_order_seq_cst) atomic_thread_fence(memory_order_seq_cst); UNLOCK(table[pos]); } static void atomic_exchange_restrict (size_t size, void volatile*__restrict__ ptr, void const volatile*__restrict__ val, void volatile*__restrict__ ret, int mo) { unsigned pos = hash(ptr); LOCK(table[pos]); memcpy((void*)ret, (void*)ptr, size); if (mo == memory_order_seq_cst) atomic_thread_fence(memory_order_seq_cst); memcpy((void*)ptr, (void*)val, size); UNLOCK(table[pos]); } void __impl_exchange (size_t size, void volatile*__restrict__ ptr, void const volatile* val, void volatile* ret, int mo) { if (val == ret) { unsigned char buffer[size]; atomic_exchange_restrict(size, ptr, val, buffer, mo); memcpy((void*)ret, buffer, size); } else { atomic_exchange_restrict(size, ptr, val, ret, mo); } } _Bool __impl_compare_exchange (size_t size, void volatile* ptr, void volatile* expected, void const volatile* desired, int mos, int mof) { unsigned pos = hash(ptr); LOCK(table[pos]); _Bool ret = !memcmp((void*)ptr, (void*)expected, size); if (ret) { memcpy((void*)ptr, (void*)desired, size); if (mos == memory_order_seq_cst) atomic_thread_fence(memory_order_seq_cst); } else { if (mof == memory_order_seq_cst) atomic_thread_fence(memory_order_seq_cst); memcpy((void*)expected, (void*)ptr, size); } UNLOCK(table[pos]); /* fprintf(stderr, "cas for %p (%zu) at pos %u, %s, exp %p, des %p\n", */ /* ptr, size, pos, ret ? "suceeded" : "failed", */ /* expected, desired); */ return ret; } /* To collect hash statistics about atomics, compile with ``HASH_STAT'' */ void __impl_print_stat(void) { #ifdef HASH_STAT size_t x1 = 0; size_t x2 = 0; size_t min = -1; size_t max = 0; size_t i; for (i = 0; i < LEN; i++) { size_t val = atomic_load(&draw[i]); fprintf(stderr, "\t%zu", val); if ((i % 8) == 7) fputc('\n', stderr); x1 += val; x2 += val*val; if (val < min) min = val; if (val > max) max = val; } fputc('\n', stderr); double avg1 = (x1+0.0)/LEN; double avg2 = (x2+0.0)/LEN; double var = avg2 - avg1*avg1; fprintf(stderr, "hash utilisation, %d positions, %zu draws: %zu < %e (+%e) < %zu\n", LEN, x1, min, avg1, sqrt(var), max); #endif } /* For the four functions defined here, we need two entries in the symbol table. One will be the final link name of the replacement stub, something like __atomic_load, e.g. The other one is the __impl prefixed name. It may eventually be used by the fixed-sized stub functions, since these can't use the name that corresponds to the builtin. The replacement to the final name is not done within compiling, since the name clashes can only create conflicts for a C compiler. Instead, we use an external tool (objcopy) that does the renaming. We want these to be strong aliases, so they can't accidentally be replaced. Therefore we can't use musl's weak_alias macro but create one of our own. */ #define alias(X, Y) __attribute__((__alias__(#X))) __typeof__(X) Y alias(__impl_load, __impl_load_replace); alias(__impl_store, __impl_store_replace); alias(__impl_exchange, __impl_exchange_replace); alias(__impl_compare_exchange, __impl_compare_exchange_replace);