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