1//===-- atomic.c - Implement support functions for atomic operations.------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// atomic.c defines a set of functions for performing atomic accesses on
10// arbitrary-sized memory locations. This design uses locks that should
11// be fast in the uncontended case, for two reasons:
12//
13// 1) This code must work with C programs that do not link to anything
14// (including pthreads) and so it should not depend on any pthread
15// functions.
16// 2) Atomic operations, rather than explicit mutexes, are most commonly used
17// on code where contended operations are rate.
18//
19// To avoid needing a per-object lock, this code allocates an array of
20// locks and hashes the object pointers to find the one that it should use.
21// For operations that must be atomic on two locations, the lower lock is
22// always acquired first, to avoid deadlock.
23//
24//===----------------------------------------------------------------------===//
25
26#include <stdbool.h>
27#include <stddef.h>
28#include <stdint.h>
29
30#include "assembly.h"
31
32// We use __builtin_mem* here to avoid dependencies on libc-provided headers.
33#define memcpy __builtin_memcpy
34#define memcmp __builtin_memcmp
35
36// Clang objects if you redefine a builtin. This little hack allows us to
37// define a function with the same name as an intrinsic.
38#pragma redefine_extname __atomic_load_c SYMBOL_NAME(__atomic_load)
39#pragma redefine_extname __atomic_store_c SYMBOL_NAME(__atomic_store)
40#pragma redefine_extname __atomic_exchange_c SYMBOL_NAME(__atomic_exchange)
41#pragma redefine_extname __atomic_compare_exchange_c SYMBOL_NAME( \
42 __atomic_compare_exchange)
43#pragma redefine_extname __atomic_is_lock_free_c SYMBOL_NAME( \
44 __atomic_is_lock_free)
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#if defined(__FreeBSD__) || defined(__DragonFly__)
60#include <errno.h>
61// clang-format off
62#include <sys/types.h>
63#include <machine/atomic.h>
64#include <sys/umtx.h>
65// clang-format on
66typedef struct _usem Lock;
67__inline static void unlock(Lock *l) {
68 __c11_atomic_store((_Atomic(uint32_t) *)&l->_count, 1, __ATOMIC_RELEASE);
69 __c11_atomic_thread_fence(__ATOMIC_SEQ_CST);
70 if (l->_has_waiters)
71 _umtx_op(l, UMTX_OP_SEM_WAKE, 1, 0, 0);
72}
73__inline static void lock(Lock *l) {
74 uint32_t old = 1;
75 while (!__c11_atomic_compare_exchange_weak((_Atomic(uint32_t) *)&l->_count,
76 &old, 0, __ATOMIC_ACQUIRE,
77 __ATOMIC_RELAXED)) {
78 _umtx_op(l, UMTX_OP_SEM_WAIT, 0, 0, 0);
79 old = 1;
80 }
81}
82/// locks for atomic operations
83static Lock locks[SPINLOCK_COUNT] = {[0 ... SPINLOCK_COUNT - 1] = {0, 1, 0}};
84
85#elif defined(__APPLE__)
86#include <libkern/OSAtomic.h>
87typedef OSSpinLock Lock;
88__inline static void unlock(Lock *l) { OSSpinLockUnlock(l); }
89/// Locks a lock. In the current implementation, this is potentially
90/// unbounded in the contended case.
91__inline static void lock(Lock *l) { OSSpinLockLock(l); }
92static Lock locks[SPINLOCK_COUNT]; // initialized to OS_SPINLOCK_INIT which is 0
93
94#else
95_Static_assert(__atomic_always_lock_free(sizeof(uintptr_t), 0),
96 "Implementation assumes lock-free pointer-size cmpxchg");
97typedef _Atomic(uintptr_t) Lock;
98/// Unlock a lock. This is a release operation.
99__inline static void unlock(Lock *l) {
100 __c11_atomic_store(l, 0, __ATOMIC_RELEASE);
101}
102/// Locks a lock. In the current implementation, this is potentially
103/// unbounded in the contended case.
104__inline static void lock(Lock *l) {
105 uintptr_t old = 0;
106 while (!__c11_atomic_compare_exchange_weak(l, &old, 1, __ATOMIC_ACQUIRE,
107 __ATOMIC_RELAXED))
108 old = 0;
109}
110/// locks for atomic operations
111static Lock locks[SPINLOCK_COUNT];
112#endif
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.
132#define ATOMIC_ALWAYS_LOCK_FREE_OR_ALIGNED_LOCK_FREE(size, p) \
133 (__atomic_always_lock_free(size, p) || \
134 (__atomic_always_lock_free(size, 0) && ((uintptr_t)p % size) == 0))
135#define IS_LOCK_FREE_1(p) ATOMIC_ALWAYS_LOCK_FREE_OR_ALIGNED_LOCK_FREE(1, p)
136#define IS_LOCK_FREE_2(p) ATOMIC_ALWAYS_LOCK_FREE_OR_ALIGNED_LOCK_FREE(2, p)
137#define IS_LOCK_FREE_4(p) ATOMIC_ALWAYS_LOCK_FREE_OR_ALIGNED_LOCK_FREE(4, p)
138#define IS_LOCK_FREE_8(p) ATOMIC_ALWAYS_LOCK_FREE_OR_ALIGNED_LOCK_FREE(8, p)
139#define IS_LOCK_FREE_16(p) ATOMIC_ALWAYS_LOCK_FREE_OR_ALIGNED_LOCK_FREE(16, p)
140
141/// Macro that calls the compiler-generated lock-free versions of functions
142/// when they exist.
143#define TRY_LOCK_FREE_CASE(n, type, ptr) \
144 case n: \
145 if (IS_LOCK_FREE_##n(ptr)) { \
146 LOCK_FREE_ACTION(type); \
147 } \
148 break;
149#ifdef __SIZEOF_INT128__
150#define TRY_LOCK_FREE_CASE_16(p) TRY_LOCK_FREE_CASE(16, __uint128_t, p)
151#else
152#define TRY_LOCK_FREE_CASE_16(p) /* __uint128_t not available */
153#endif
154
155#define LOCK_FREE_CASES(ptr) \
156 do { \
157 switch (size) { \
158 TRY_LOCK_FREE_CASE(1, uint8_t, ptr) \
159 TRY_LOCK_FREE_CASE(2, uint16_t, ptr) \
160 TRY_LOCK_FREE_CASE(4, uint32_t, ptr) \
161 TRY_LOCK_FREE_CASE(8, uint64_t, ptr) \
162 TRY_LOCK_FREE_CASE_16(ptr) /* __uint128_t may not be supported */ \
163 default: \
164 break; \
165 } \
166 } while (0)
167
168/// Whether atomic operations for the given size (and alignment) are lock-free.
169bool __atomic_is_lock_free_c(size_t size, void *ptr) {
170#define LOCK_FREE_ACTION(type) return true;
171 LOCK_FREE_CASES(ptr);
172#undef LOCK_FREE_ACTION
173 return false;
174}
175
176/// An atomic load operation. This is atomic with respect to the source
177/// pointer only.
178void __atomic_load_c(int size, void *src, void *dest, int model) {
179#define LOCK_FREE_ACTION(type) \
180 *((type *)dest) = __c11_atomic_load((_Atomic(type) *)src, model); \
181 return;
182 LOCK_FREE_CASES(src);
183#undef LOCK_FREE_ACTION
184 Lock *l = lock_for_pointer(ptr: src);
185 lock(l);
186 memcpy(dest, src, size);
187 unlock(l);
188}
189
190/// An atomic store operation. This is atomic with respect to the destination
191/// pointer only.
192void __atomic_store_c(int size, void *dest, void *src, int model) {
193#define LOCK_FREE_ACTION(type) \
194 __c11_atomic_store((_Atomic(type) *)dest, *(type *)src, model); \
195 return;
196 LOCK_FREE_CASES(dest);
197#undef LOCK_FREE_ACTION
198 Lock *l = lock_for_pointer(ptr: dest);
199 lock(l);
200 memcpy(dest, src, size);
201 unlock(l);
202}
203
204/// Atomic compare and exchange operation. If the value at *ptr is identical
205/// to the value at *expected, then this copies value at *desired to *ptr. If
206/// they are not, then this stores the current value from *ptr in *expected.
207///
208/// This function returns 1 if the exchange takes place or 0 if it fails.
209int __atomic_compare_exchange_c(int size, void *ptr, void *expected,
210 void *desired, int success, int failure) {
211#define LOCK_FREE_ACTION(type) \
212 return __c11_atomic_compare_exchange_strong( \
213 (_Atomic(type) *)ptr, (type *)expected, *(type *)desired, success, \
214 failure)
215 LOCK_FREE_CASES(ptr);
216#undef LOCK_FREE_ACTION
217 Lock *l = lock_for_pointer(ptr);
218 lock(l);
219 if (memcmp(ptr, expected, size) == 0) {
220 memcpy(ptr, desired, size);
221 unlock(l);
222 return 1;
223 }
224 memcpy(expected, ptr, size);
225 unlock(l);
226 return 0;
227}
228
229/// Performs an atomic exchange operation between two pointers. This is atomic
230/// with respect to the target address.
231void __atomic_exchange_c(int size, void *ptr, void *val, void *old, int model) {
232#define LOCK_FREE_ACTION(type) \
233 *(type *)old = \
234 __c11_atomic_exchange((_Atomic(type) *)ptr, *(type *)val, model); \
235 return;
236 LOCK_FREE_CASES(ptr);
237#undef LOCK_FREE_ACTION
238 Lock *l = lock_for_pointer(ptr);
239 lock(l);
240 memcpy(old, ptr, size);
241 memcpy(ptr, val, size);
242 unlock(l);
243}
244
245////////////////////////////////////////////////////////////////////////////////
246// Where the size is known at compile time, the compiler may emit calls to
247// specialised versions of the above functions.
248////////////////////////////////////////////////////////////////////////////////
249#ifdef __SIZEOF_INT128__
250#define OPTIMISED_CASES \
251 OPTIMISED_CASE(1, IS_LOCK_FREE_1, uint8_t) \
252 OPTIMISED_CASE(2, IS_LOCK_FREE_2, uint16_t) \
253 OPTIMISED_CASE(4, IS_LOCK_FREE_4, uint32_t) \
254 OPTIMISED_CASE(8, IS_LOCK_FREE_8, uint64_t) \
255 OPTIMISED_CASE(16, IS_LOCK_FREE_16, __uint128_t)
256#else
257#define OPTIMISED_CASES \
258 OPTIMISED_CASE(1, IS_LOCK_FREE_1, uint8_t) \
259 OPTIMISED_CASE(2, IS_LOCK_FREE_2, uint16_t) \
260 OPTIMISED_CASE(4, IS_LOCK_FREE_4, uint32_t) \
261 OPTIMISED_CASE(8, IS_LOCK_FREE_8, uint64_t)
262#endif
263
264#define OPTIMISED_CASE(n, lockfree, type) \
265 type __atomic_load_##n(type *src, int model) { \
266 if (lockfree(src)) \
267 return __c11_atomic_load((_Atomic(type) *)src, model); \
268 Lock *l = lock_for_pointer(src); \
269 lock(l); \
270 type val = *src; \
271 unlock(l); \
272 return val; \
273 }
274OPTIMISED_CASES
275#undef OPTIMISED_CASE
276
277#define OPTIMISED_CASE(n, lockfree, type) \
278 void __atomic_store_##n(type *dest, type val, int model) { \
279 if (lockfree(dest)) { \
280 __c11_atomic_store((_Atomic(type) *)dest, val, model); \
281 return; \
282 } \
283 Lock *l = lock_for_pointer(dest); \
284 lock(l); \
285 *dest = val; \
286 unlock(l); \
287 return; \
288 }
289OPTIMISED_CASES
290#undef OPTIMISED_CASE
291
292#define OPTIMISED_CASE(n, lockfree, type) \
293 type __atomic_exchange_##n(type *dest, type val, int model) { \
294 if (lockfree(dest)) \
295 return __c11_atomic_exchange((_Atomic(type) *)dest, val, model); \
296 Lock *l = lock_for_pointer(dest); \
297 lock(l); \
298 type tmp = *dest; \
299 *dest = val; \
300 unlock(l); \
301 return tmp; \
302 }
303OPTIMISED_CASES
304#undef OPTIMISED_CASE
305
306#define OPTIMISED_CASE(n, lockfree, type) \
307 bool __atomic_compare_exchange_##n(type *ptr, type *expected, type desired, \
308 int success, int failure) { \
309 if (lockfree(ptr)) \
310 return __c11_atomic_compare_exchange_strong( \
311 (_Atomic(type) *)ptr, expected, desired, success, failure); \
312 Lock *l = lock_for_pointer(ptr); \
313 lock(l); \
314 if (*ptr == *expected) { \
315 *ptr = desired; \
316 unlock(l); \
317 return true; \
318 } \
319 *expected = *ptr; \
320 unlock(l); \
321 return false; \
322 }
323OPTIMISED_CASES
324#undef OPTIMISED_CASE
325
326////////////////////////////////////////////////////////////////////////////////
327// Atomic read-modify-write operations for integers of various sizes.
328////////////////////////////////////////////////////////////////////////////////
329#define ATOMIC_RMW(n, lockfree, type, opname, op) \
330 type __atomic_fetch_##opname##_##n(type *ptr, type val, int model) { \
331 if (lockfree(ptr)) \
332 return __c11_atomic_fetch_##opname((_Atomic(type) *)ptr, val, model); \
333 Lock *l = lock_for_pointer(ptr); \
334 lock(l); \
335 type tmp = *ptr; \
336 *ptr = tmp op val; \
337 unlock(l); \
338 return tmp; \
339 }
340
341#define ATOMIC_RMW_NAND(n, lockfree, type) \
342 type __atomic_fetch_nand_##n(type *ptr, type val, int model) { \
343 if (lockfree(ptr)) \
344 return __c11_atomic_fetch_nand((_Atomic(type) *)ptr, val, model); \
345 Lock *l = lock_for_pointer(ptr); \
346 lock(l); \
347 type tmp = *ptr; \
348 *ptr = ~(tmp & val); \
349 unlock(l); \
350 return tmp; \
351 }
352
353#define OPTIMISED_CASE(n, lockfree, type) ATOMIC_RMW(n, lockfree, type, add, +)
354OPTIMISED_CASES
355#undef OPTIMISED_CASE
356#define OPTIMISED_CASE(n, lockfree, type) ATOMIC_RMW(n, lockfree, type, sub, -)
357OPTIMISED_CASES
358#undef OPTIMISED_CASE
359#define OPTIMISED_CASE(n, lockfree, type) ATOMIC_RMW(n, lockfree, type, and, &)
360OPTIMISED_CASES
361#undef OPTIMISED_CASE
362#define OPTIMISED_CASE(n, lockfree, type) ATOMIC_RMW(n, lockfree, type, or, |)
363OPTIMISED_CASES
364#undef OPTIMISED_CASE
365#define OPTIMISED_CASE(n, lockfree, type) ATOMIC_RMW(n, lockfree, type, xor, ^)
366OPTIMISED_CASES
367#undef OPTIMISED_CASE
368// Allow build with clang without __c11_atomic_fetch_nand builtin (pre-14)
369#if __has_builtin(__c11_atomic_fetch_nand)
370#define OPTIMISED_CASE(n, lockfree, type) ATOMIC_RMW_NAND(n, lockfree, type)
371OPTIMISED_CASES
372#undef OPTIMISED_CASE
373#endif
374

source code of compiler-rt/lib/builtins/atomic.c