1/*
2 * This Source Code Form is subject to the terms of the Mozilla Public
3 * License, v. 2.0. If a copy of the MPL was not distributed with this
4 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
5 *
6 * Copyright 1997 - July 2008 CWI, August 2008 - 2019 MonetDB B.V.
7 */
8
9/* This file provides interfaces to perform certain atomic operations
10 * on variables. Atomic in this sense means that an operation
11 * performed in one thread shows up in another thread either
12 * completely or not at all.
13 *
14 * The following operations are defined:
15 * ATOMIC_VAR_INIT -- initializer for the variable (not necessarily atomic!);
16 * ATOMIC_INIT -- initialize the variable (not necessarily atomic!);
17 * ATOMIC_DESTROY -- destroy the variable
18 * ATOMIC_GET -- return the value of a variable;
19 * ATOMIC_SET -- set the value of a variable;
20 * ATOMIC_XCG -- set the value of a variable, return original value;
21 * ATOMIC_CAS -- compare-and-set (see below)
22 * ATOMIC_ADD -- add a value to a variable, return original value;
23 * ATOMIC_SUB -- subtract a value from a variable, return original value;
24 * ATOMIC_INC -- increment a variable's value, return new value;
25 * ATOMIC_DEC -- decrement a variable's value, return new value;
26 * These interfaces work on variables of type ATOMIC_TYPE
27 * (int or int64_t depending on architecture).
28 *
29 * The compare-and-set operation is based on the C11 standard: if the
30 * atomic variable equals the expected value, the atomic variable is
31 * replaced by the desired value and true is returned. Otherwise, the
32 * expected value is replaced by the current value of the atomic
33 * variable and false is returned.
34 *
35 * Some of these are also available for pointers:
36 * ATOMIC_PTR_INIT
37 * ATOMIC_PTR_DESTROY
38 * ATOMIC_PTR_GET
39 * ATOMIC_PTR_SET
40 * ATOMIC_PTR_XCG
41 * ATOMIC_PTR_CAS
42 * To define an atomic pointer, use ATOMIC_PTR_TYPE. This is a (void *)
43 * pointer that is appropriately adapted for atomic use.
44 *
45 * In addition, the following operations are defined:
46 * ATOMIC_TAS -- test-and-set: set variable to "true" and return old value
47 * ATOMIC_CLEAR -- set variable to "false"
48 * These two operations are only defined on variables of type
49 * ATOMIC_FLAG, and the only values defined for such a variable are
50 * "false" and "true". The variable can be statically initialized
51 * to "false" using the ATOMIC_FLAG_INIT macro.
52 */
53
54#ifndef _MATOMIC_H_
55#define _MATOMIC_H_
56
57/* define this if you don't want to use atomic instructions */
58/* #define NO_ATOMIC_INSTRUCTIONS */
59
60#if defined(HAVE_STDATOMIC_H) && !defined(__STDC_NO_ATOMICS__) && !defined(NO_ATOMIC_INSTRUCTIONS)
61
62#include <stdatomic.h>
63
64#if ATOMIC_LLONG_LOCK_FREE == 2
65typedef volatile atomic_ullong ATOMIC_TYPE;
66typedef unsigned long long ATOMIC_BASE_TYPE;
67#elif ATOMIC_LONG_LOCK_FREE == 2
68typedef volatile atomic_ulong ATOMIC_TYPE;
69typedef unsigned long ATOMIC_BASE_TYPE;
70#elif ATOMIC_INT_LOCK_FREE == 2
71typedef volatile atomic_uint ATOMIC_TYPE;
72typedef unsigned int ATOMIC_BASE_TYPE;
73#elif ATOMIC_LLONG_LOCK_FREE == 1
74typedef volatile atomic_ullong ATOMIC_TYPE;
75typedef unsigned long long ATOMIC_BASE_TYPE;
76#elif ATOMIC_LONG_LOCK_FREE == 1
77typedef volatile atomic_ulong ATOMIC_TYPE;
78typedef unsigned long ATOMIC_BASE_TYPE;
79#elif ATOMIC_INT_LOCK_FREE == 1
80typedef volatile atomic_uint ATOMIC_TYPE;
81typedef unsigned int ATOMIC_BASE_TYPE;
82#else
83typedef volatile atomic_ullong ATOMIC_TYPE;
84typedef unsigned long long ATOMIC_BASE_TYPE;
85#endif
86
87#define ATOMIC_INIT(var, val) atomic_init(var, (ATOMIC_BASE_TYPE) (val))
88#define ATOMIC_DESTROY(var) ((void) 0)
89#define ATOMIC_GET(var) atomic_load(var)
90#define ATOMIC_SET(var, val) atomic_store(var, (ATOMIC_BASE_TYPE) (val))
91#define ATOMIC_XCG(var, val) atomic_exchange(var, (ATOMIC_BASE_TYPE) (val))
92#define ATOMIC_CAS(var, exp, des) atomic_compare_exchange_strong(var, exp, (ATOMIC_BASE_TYPE) (des))
93#define ATOMIC_ADD(var, val) atomic_fetch_add(var, (ATOMIC_BASE_TYPE) (val))
94#define ATOMIC_SUB(var, val) atomic_fetch_sub(var, (ATOMIC_BASE_TYPE) (val))
95#define ATOMIC_INC(var) (atomic_fetch_add(var, 1) + 1)
96#define ATOMIC_DEC(var) (atomic_fetch_sub(var, 1) - 1)
97
98#ifdef __INTEL_COMPILER
99typedef volatile atomic_address ATOMIC_PTR_TYPE;
100#else
101typedef void *_Atomic volatile ATOMIC_PTR_TYPE;
102#endif
103#define ATOMIC_PTR_INIT(var, val) atomic_init(var, val)
104#define ATOMIC_PTR_DESTROY(var) ((void) 0)
105#define ATOMIC_PTR_VAR_INIT(val) ATOMIC_VAR_INIT(val)
106#define ATOMIC_PTR_GET(var) atomic_load(var)
107#define ATOMIC_PTR_SET(var, val) atomic_store(var, (void *) (val))
108#define ATOMIC_PTR_XCG(var, val) atomic_exchange(var, (void *) (val))
109#define ATOMIC_PTR_CAS(var, exp, des) atomic_compare_exchange_strong(var, exp, (void *) (des))
110
111typedef volatile atomic_flag ATOMIC_FLAG;
112/* ATOMIC_FLAG_INIT is already defined by the include file */
113#define ATOMIC_CLEAR(var) atomic_flag_clear(var)
114#define ATOMIC_TAS(var) atomic_flag_test_and_set(var)
115
116#elif defined(_MSC_VER) && !defined(NO_ATOMIC_INSTRUCTIONS)
117
118#include <intrin.h>
119
120/* On Windows, with Visual Studio 2005, the compiler uses acquire
121 * semantics for read operations on volatile variables and release
122 * semantics for write operations on volatile variables.
123 *
124 * With Visual Studio 2003, volatile to volatile references are
125 * ordered; the compiler will not re-order volatile variable access.
126 * However, these operations could be re-ordered by the processor.
127 *
128 * See
129 * https://docs.microsoft.com/en-us/windows/desktop/Sync/synchronization-and-multiprocessor-issues
130 *
131 * This does not go for the Intel compiler, so there we use
132 * _InterlockedExchangeAdd to load the value of an atomic variable.
133 * There might be a better way, but it's hard to find in the
134 * documentation.
135 */
136
137#if SIZEOF_SSIZE_T == 8
138
139typedef volatile int64_t ATOMIC_TYPE;
140typedef int64_t ATOMIC_BASE_TYPE;
141#define ATOMIC_VAR_INIT(val) (val)
142#define ATOMIC_INIT(var, val) (*(var) = (val))
143#define ATOMIC_DESTROY(var) ((void) 0)
144
145#ifdef __INTEL_COMPILER
146#define ATOMIC_GET(var) _InterlockedExchangeAdd64(var, 0)
147#else
148#define ATOMIC_GET(var) (*(var))
149/* should we use _InterlockedExchangeAdd64(var, 0) instead? */
150#endif
151#define ATOMIC_SET(var, val) _InterlockedExchange64(var, (ATOMIC_BASE_TYPE) (val))
152#define ATOMIC_XCG(var, val) _InterlockedExchange64(var, (ATOMIC_BASE_TYPE) (val))
153static inline bool
154ATOMIC_CAS(ATOMIC_TYPE *var, ATOMIC_BASE_TYPE *exp, ATOMIC_BASE_TYPE des)
155{
156 ATOMIC_BASE_TYPE old;
157 old = _InterlockedCompareExchange64(var, des, *exp);
158 if (old == *exp)
159 return true;
160 *exp = old;
161 return false;
162}
163#define ATOMIC_CAS(var, exp, des) ATOMIC_CAS(var, exp, (ATOMIC_BASE_TYPE) (des))
164#define ATOMIC_ADD(var, val) _InterlockedExchangeAdd64(var, (ATOMIC_BASE_TYPE) (val))
165#define ATOMIC_SUB(var, val) _InterlockedExchangeAdd64(var, -(ATOMIC_BASE_TYPE) (val))
166#define ATOMIC_INC(var) _InterlockedIncrement64(var)
167#define ATOMIC_DEC(var) _InterlockedDecrement64(var)
168
169#pragma intrinsic(_InterlockedExchange64)
170#pragma intrinsic(_InterlockedExchangeAdd64)
171#pragma intrinsic(_InterlockedIncrement64)
172#pragma intrinsic(_InterlockedDecrement64)
173#pragma intrinsic(_InterlockedCompareExchange64)
174
175#else
176
177typedef volatile int ATOMIC_TYPE;
178typedef int ATOMIC_BASE_TYPE;
179#define ATOMIC_VAR_INIT(val) (val)
180#define ATOMIC_INIT(var, val) (*(var) = (val))
181#define ATOMIC_DESTROY(var) ((void) 0)
182
183#ifdef __INTEL_COMPILER
184#define ATOMIC_GET(var) _InterlockedExchangeAdd(var, 0)
185#else
186#define ATOMIC_GET(var) (*(var))
187/* should we use _InterlockedExchangeAdd(var, 0) instead? */
188#endif
189#define ATOMIC_SET(var, val) _InterlockedExchange(var, (ATOMIC_BASE_TYPE) (val))
190#define ATOMIC_XCG(var, val) _InterlockedExchange(var, (ATOMIC_BASE_TYPE) (val))
191static inline bool
192ATOMIC_CAS(ATOMIC_TYPE *var, ATOMIC_BASE_TYPE *exp, ATOMIC_BASE_TYPE des)
193{
194 ATOMIC_BASE_TYPE old;
195 old = _InterlockedCompareExchange(var, des, *exp);
196 if (old == *exp)
197 return true;
198 *exp = old;
199 return false;
200}
201#define ATOMIC_CAS(var, exp, des) ATOMIC_CAS(var, exp, (ATOMIC_BASE_TYPE) (des))
202#define ATOMIC_ADD(var, val) _InterlockedExchangeAdd(var, (ATOMIC_BASE_TYPE) (val))
203#define ATOMIC_SUB(var, val) _InterlockedExchangeAdd(var, -(ATOMIC_BASE_TYPE) (val))
204#define ATOMIC_INC(var) _InterlockedIncrement(var)
205#define ATOMIC_DEC(var) _InterlockedDecrement(var)
206
207#pragma intrinsic(_InterlockedExchange)
208#pragma intrinsic(_InterlockedExchangeAdd)
209#pragma intrinsic(_InterlockedIncrement)
210#pragma intrinsic(_InterlockedDecrement)
211
212#endif
213
214typedef PVOID volatile ATOMIC_PTR_TYPE;
215#define ATOMIC_PTR_INIT(var, val) (*(var) = (val))
216#define ATOMIC_PTR_DESTROY(var) ((void) 0)
217#define ATOMIC_PTR_VAR_INIT(val) (val)
218#define ATOMIC_PTR_GET(var) (*(var))
219#define ATOMIC_PTR_SET(var, val) _InterlockedExchangePointer(var, (PVOID) (val))
220#define ATOMIC_PTR_XCG(var, val) _InterlockedExchangePointer(var, (PVOID) (val))
221static inline bool
222ATOMIC_PTR_CAS(ATOMIC_PTR_TYPE *var, void **exp, void *des)
223{
224 void *old;
225 old = _InterlockedCompareExchangePointer(var, des, *exp);
226 if (old == *exp)
227 return true;
228 *exp = old;
229 return false;
230}
231#define ATOMIC_PTR_CAS(var, exp, des) ATOMIC_PTR_CAS(var, exp, (void *) (des))
232
233typedef volatile int ATOMIC_FLAG;
234#define ATOMIC_FLAG_INIT { 0 }
235#define ATOMIC_CLEAR(var) _InterlockedExchange(var, 0)
236#define ATOMIC_TAS(var) _InterlockedCompareExchange(var, 1, 0)
237#pragma intrinsic(_InterlockedCompareExchange)
238
239#elif (defined(__GNUC__) || defined(__INTEL_COMPILER)) && defined(__ATOMIC_SEQ_CST) && !(defined(__sun__) && SIZEOF_SIZE_T == 8) && !defined(_MSC_VER) && !defined(NO_ATOMIC_INSTRUCTIONS)
240
241/* the new way of doing this according to GCC (the old way, using
242 * __sync_* primitives is not supported) */
243
244#if SIZEOF_SSIZE_T == 8
245typedef int64_t ATOMIC_BASE_TYPE;
246typedef volatile int64_t ATOMIC_TYPE;
247#else
248typedef int ATOMIC_BASE_TYPE;
249typedef volatile int ATOMIC_TYPE;
250#endif
251#define ATOMIC_VAR_INIT(val) (val)
252#define ATOMIC_INIT(var, val) (*(var) = (val))
253#define ATOMIC_DESTROY(var) ((void) 0)
254
255#define ATOMIC_GET(var) __atomic_load_n(var, __ATOMIC_SEQ_CST)
256#define ATOMIC_SET(var, val) __atomic_store_n(var, (ATOMIC_BASE_TYPE) (val), __ATOMIC_SEQ_CST)
257#define ATOMIC_XCG(var, val) __atomic_exchange_n(var, (ATOMIC_BASE_TYPE) (val), __ATOMIC_SEQ_CST)
258#define ATOMIC_CAS(var, exp, des) __atomic_compare_exchange_n(var, exp, (ATOMIC_BASE_TYPE) (des), false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)
259#define ATOMIC_ADD(var, val) __atomic_fetch_add(var, (ATOMIC_BASE_TYPE) (val), __ATOMIC_SEQ_CST)
260#define ATOMIC_SUB(var, val) __atomic_fetch_sub(var, (ATOMIC_BASE_TYPE) (val), __ATOMIC_SEQ_CST)
261#define ATOMIC_INC(var) __atomic_add_fetch(var, 1, __ATOMIC_SEQ_CST)
262#define ATOMIC_DEC(var) __atomic_sub_fetch(var, 1, __ATOMIC_SEQ_CST)
263
264typedef void *volatile ATOMIC_PTR_TYPE;
265#define ATOMIC_PTR_INIT(var, val) (*(var) = (val))
266#define ATOMIC_PTR_VAR_INIT(val) (val)
267#define ATOMIC_PTR_DESTROY(var) ((void) 0)
268#define ATOMIC_PTR_GET(var) __atomic_load_n(var, __ATOMIC_SEQ_CST)
269#define ATOMIC_PTR_SET(var, val) __atomic_store_n(var, (val), __ATOMIC_SEQ_CST)
270#define ATOMIC_PTR_XCG(var, val) __atomic_exchange_n(var, (val), __ATOMIC_SEQ_CST)
271#define ATOMIC_PTR_CAS(var, exp, des) __atomic_compare_exchange_n(var, exp, (void *) (des), false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)
272
273typedef volatile char ATOMIC_FLAG;
274#define ATOMIC_FLAG_INIT { 0 }
275#define ATOMIC_CLEAR(var) __atomic_clear(var, __ATOMIC_SEQ_CST)
276#define ATOMIC_TAS(var) __atomic_test_and_set(var, __ATOMIC_SEQ_CST)
277
278#else
279
280/* emulate using mutexes */
281
282#include <pthread.h> /* required for pthread_mutex_t */
283
284typedef size_t ATOMIC_BASE_TYPE;
285typedef struct {
286 ATOMIC_BASE_TYPE val;
287 pthread_mutex_t lck;
288} ATOMIC_TYPE;
289#define ATOMIC_VAR_INIT(v) { .val = (v), .lck = PTHREAD_MUTEX_INITIALIZER }
290
291static inline void
292ATOMIC_INIT(ATOMIC_TYPE *var, ATOMIC_BASE_TYPE val)
293{
294 pthread_mutex_init(&var->lck, 0);
295 var->val = val;
296}
297#define ATOMIC_INIT(var, val) ATOMIC_INIT((var), (ATOMIC_BASE_TYPE) (val))
298
299#define ATOMIC_DESTROY(var) pthread_mutex_destroy(&(var)->lck)
300
301static inline ATOMIC_BASE_TYPE
302ATOMIC_GET(ATOMIC_TYPE *var)
303{
304 ATOMIC_BASE_TYPE old;
305 pthread_mutex_lock(&var->lck);
306 old = var->val;
307 pthread_mutex_unlock(&var->lck);
308 return old;
309}
310
311static inline void
312ATOMIC_SET(ATOMIC_TYPE *var, ATOMIC_BASE_TYPE val)
313{
314 pthread_mutex_lock(&var->lck);
315 var->val = val;
316 pthread_mutex_unlock(&var->lck);
317}
318#define ATOMIC_SET(var, val) ATOMIC_SET(var, (ATOMIC_BASE_TYPE) (val))
319
320static inline ATOMIC_BASE_TYPE
321ATOMIC_XCG(ATOMIC_TYPE *var, ATOMIC_BASE_TYPE val)
322{
323 ATOMIC_BASE_TYPE old;
324 pthread_mutex_lock(&var->lck);
325 old = var->val;
326 var->val = val;
327 pthread_mutex_unlock(&var->lck);
328 return old;
329}
330#define ATOMIC_XCG(var, val) ATOMIC_XCG(var, (ATOMIC_BASE_TYPE) (val))
331
332static inline bool
333ATOMIC_CAS(ATOMIC_TYPE *var, ATOMIC_BASE_TYPE *exp, ATOMIC_BASE_TYPE des)
334{
335 bool ret;
336 pthread_mutex_lock(&var->lck);
337 if (var->val == *exp) {
338 var->val = des;
339 ret = true;
340 } else {
341 *exp = var->val;
342 ret = false;
343 }
344 pthread_mutex_unlock(&var->lck);
345 return ret;
346}
347#define ATOMIC_CAS(var, exp, des) ATOMIC_CAS(var, exp, (ATOMIC_BASE_TYPE) (des))
348
349static inline ATOMIC_BASE_TYPE
350ATOMIC_ADD(ATOMIC_TYPE *var, ATOMIC_BASE_TYPE val)
351{
352 ATOMIC_BASE_TYPE old;
353 pthread_mutex_lock(&var->lck);
354 old = var->val;
355 var->val += val;
356 pthread_mutex_unlock(&var->lck);
357 return old;
358}
359#define ATOMIC_ADD(var, val) ATOMIC_ADD(var, (ATOMIC_BASE_TYPE) (val))
360
361static inline ATOMIC_BASE_TYPE
362ATOMIC_SUB(ATOMIC_TYPE *var, ATOMIC_BASE_TYPE val)
363{
364 ATOMIC_BASE_TYPE old;
365 pthread_mutex_lock(&var->lck);
366 old = var->val;
367 var->val -= val;
368 pthread_mutex_unlock(&var->lck);
369 return old;
370}
371#define ATOMIC_SUB(var, val) ATOMIC_SUB(var, (ATOMIC_BASE_TYPE) (val))
372
373static inline ATOMIC_BASE_TYPE
374ATOMIC_INC(ATOMIC_TYPE *var)
375{
376 ATOMIC_BASE_TYPE new;
377 pthread_mutex_lock(&var->lck);
378 new = var->val += 1;
379 pthread_mutex_unlock(&var->lck);
380 return new;
381}
382
383static inline ATOMIC_BASE_TYPE
384ATOMIC_DEC(ATOMIC_TYPE *var)
385{
386 ATOMIC_BASE_TYPE new;
387 pthread_mutex_lock(&var->lck);
388 new = var->val -= 1;
389 pthread_mutex_unlock(&var->lck);
390 return new;
391}
392
393typedef struct {
394 void *val;
395 pthread_mutex_t lck;
396} ATOMIC_PTR_TYPE;
397#define ATOMIC_PTR_VAR_INIT(v) { .val = (v), .lck = PTHREAD_MUTEX_INITIALIZER }
398
399static inline void
400ATOMIC_PTR_INIT(ATOMIC_PTR_TYPE *var, void *val)
401{
402 pthread_mutex_init(&var->lck, 0);
403 var->val = val;
404}
405
406#define ATOMIC_PTR_DESTROY(var) pthread_mutex_destroy(&(var)->lck)
407
408static inline void *
409ATOMIC_PTR_GET(ATOMIC_PTR_TYPE *var)
410{
411 void *old;
412 pthread_mutex_lock(&var->lck);
413 old = var->val;
414 pthread_mutex_unlock(&var->lck);
415 return old;
416}
417
418static inline void
419ATOMIC_PTR_SET(ATOMIC_PTR_TYPE *var, void *val)
420{
421 pthread_mutex_lock(&var->lck);
422 var->val = val;
423 pthread_mutex_unlock(&var->lck);
424}
425
426static inline void *
427ATOMIC_PTR_XCG(ATOMIC_PTR_TYPE *var, void *val)
428{
429 void *old;
430 pthread_mutex_lock(&var->lck);
431 old = var->val;
432 var->val = val;
433 pthread_mutex_unlock(&var->lck);
434 return old;
435}
436
437static inline bool
438ATOMIC_PTR_CAS(ATOMIC_PTR_TYPE *var, void **exp, void *des)
439{
440 bool ret;
441 pthread_mutex_lock(&var->lck);
442 if (var->val == *exp) {
443 var->val = des;
444 ret = true;
445 } else {
446 *exp = var->val;
447 ret = false;
448 }
449 pthread_mutex_unlock(&var->lck);
450 return ret;
451}
452#define ATOMIC_PTR_CAS(var, exp, des) ATOMIC_PTR_CAS(var, exp, (void *) (des))
453
454typedef struct {
455 bool flg;
456 pthread_mutex_t lck;
457} ATOMIC_FLAG;
458#define ATOMIC_FLAG_INIT { .flg = false, .lck = PTHREAD_MUTEX_INITIALIZER }
459
460static inline bool
461ATOMIC_TAS(ATOMIC_FLAG *var)
462{
463 bool old;
464 pthread_mutex_lock(&var->lck);
465 old = var->flg;
466 var->flg = true;
467 pthread_mutex_unlock(&var->lck);
468 return old;
469}
470
471static inline void
472ATOMIC_CLEAR(ATOMIC_FLAG *var)
473{
474 pthread_mutex_lock(&var->lck);
475 var->flg = false;
476 pthread_mutex_unlock(&var->lck);
477}
478
479#define USE_NATIVE_LOCKS /* must use pthread locks */
480
481#endif
482
483#endif /* _MATOMIC_H_ */
484