2 * Copyright (c) 2003 Hewlett-Packard Development Company, L.P.
4 * Permission is hereby granted, free of charge, to any person obtaining a copy
5 * of this software and associated documentation files (the "Software"), to deal
6 * in the Software without restriction, including without limitation the rights
7 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8 * copies of the Software, and to permit persons to whom the Software is
9 * furnished to do so, subject to the following conditions:
11 * The above copyright notice and this permission notice shall be included in
12 * all copies or substantial portions of the Software.
14 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
30 /* We define various atomic operations on memory in a */
31 /* machine-specific way. Unfortunately, this is complicated */
32 /* by the fact that these may or may not be combined with */
33 /* various memory barriers. Thus the actual operations we */
34 /* define have the form AO_<atomic-op>_<barrier>, for all */
35 /* plausible combinations of <atomic-op> and <barrier>. */
36 /* This of course results in a mild combinatorial explosion. */
37 /* To deal with it, we try to generate derived */
38 /* definitions for as many of the combinations as we can, as */
39 /* automatically as possible. */
41 /* Our assumption throughout is that the programmer will */
42 /* specify the least demanding operation and memory barrier */
43 /* that will guarantee correctness for the implementation. */
44 /* Our job is to find the least expensive way to implement it */
45 /* on the applicable hardware. In many cases that will */
46 /* involve, for example, a stronger memory barrier, or a */
47 /* combination of hardware primitives. */
50 /* "plain" atomic operations are not guaranteed to include */
51 /* a barrier. The suffix in the name specifies the barrier */
52 /* type. Suffixes are: */
53 /* _release: Earlier operations may not be delayed past it. */
54 /* _acquire: Later operations may not move ahead of it. */
55 /* _read: Subsequent reads must follow this operation and */
56 /* preceding reads. */
57 /* _write: Earlier writes precede both this operation and */
59 /* _full: Ordered with respect to both earlier and later memops.*/
60 /* _release_write: Ordered with respect to earlier writes. */
61 /* _acquire_read: Ordered with respect to later reads. */
63 /* Currently we try to define the following atomic memory */
64 /* operations, in combination with the above barriers: */
68 /* AO_test_and_set (binary) */
69 /* AO_fetch_and_add */
70 /* AO_fetch_and_add1 */
71 /* AO_fetch_and_sub1 */
73 /* AO_compare_and_swap */
75 /* Note that atomicity guarantees are valid only if both */
76 /* readers and writers use AO_ operations to access the */
77 /* shared value, while ordering constraints are intended to */
78 /* apply all memory operations. If a location can potentially */
79 /* be accessed simultaneously from multiple threads, and one of */
80 /* those accesses may be a write access, then all such */
81 /* accesses to that location should be through AO_ primitives. */
82 /* However if AO_ operations enforce sufficient ordering to */
83 /* ensure that a location x cannot be accessed concurrently, */
84 /* or can only be read concurrently, then x can be accessed */
85 /* via ordinary references and assignments. */
87 /* Compare_and_exchange takes an address and an expected old */
88 /* value and a new value, and returns an int. Nonzero */
89 /* indicates that it succeeded. */
90 /* Test_and_set takes an address, atomically replaces it by */
91 /* AO_TS_SET, and returns the prior value. */
92 /* An AO_TS_t location can be reset with the */
93 /* AO_CLEAR macro, which normally uses AO_store_release. */
94 /* AO_fetch_and_add takes an address and an AO_t increment */
95 /* value. The AO_fetch_and_add1 and AO_fetch_and_sub1 variants */
96 /* are provided, since they allow faster implementations on */
97 /* some hardware. AO_or atomically ors an AO_t value into a */
98 /* memory location, but does not provide access to the original.*/
100 /* We expect this list to grow slowly over time. */
102 /* Note that AO_nop_full is a full memory barrier. */
104 /* Note that if some data is initialized with */
105 /* data.x = ...; data.y = ...; ... */
106 /* AO_store_release_write(&data_is_initialized, 1) */
107 /* then data is guaranteed to be initialized after the test */
108 /* if (AO_load_release_read(&data_is_initialized)) ... */
109 /* succeeds. Furthermore, this should generate near-optimal */
110 /* code on all common platforms. */
112 /* All operations operate on unsigned AO_t, which */
113 /* is the natural word size, and usually unsigned long. */
114 /* It is possible to check whether a particular operation op */
115 /* is available on a particular platform by checking whether */
116 /* AO_HAVE_op is defined. We make heavy use of these macros */
119 /* The rest of this file basically has three sections: */
121 /* Some utility and default definitions. */
123 /* The architecture dependent section: */
124 /* This defines atomic operations that have direct hardware */
125 /* support on a particular platform, mostly by including the */
126 /* appropriate compiler- and hardware-dependent file. */
128 /* The synthesis section: */
129 /* This tries to define other atomic operations in terms of */
130 /* those that are explicitly available on the platform. */
131 /* This section is hardware independent. */
132 /* We make no attempt to synthesize operations in ways that */
133 /* effectively introduce locks, except for the debugging/demo */
134 /* pthread-based implementation at the beginning. A more */
135 /* realistic implementation that falls back to locks could be */
136 /* added as a higher layer. But that would sacrifice */
137 /* usability from signal handlers. */
138 /* The synthesis section is implemented almost entirely in */
139 /* atomic_ops_generalize.h. */
141 /* Some common defaults. Overridden for some architectures. */
144 /* The test_and_set primitive returns an AO_TS_VAL_t value. */
145 /* AO_TS_t is the type of an in-memory test-and-set location. */
147 #define AO_TS_INITIALIZER (AO_t)AO_TS_CLEAR
149 /* Platform-dependent stuff: */
150 #if defined(__GNUC__) || defined(_MSC_VER) || defined(__INTEL_COMPILER) \
151 || defined(__DMC__) || defined(__WATCOMC__)
152 # define AO_INLINE static __inline
154 # define AO_INLINE static inline
156 # define AO_INLINE static
159 #if defined(__GNUC__) && !defined(__INTEL_COMPILER)
160 # define AO_compiler_barrier() __asm__ __volatile__("" : : : "memory")
161 #elif defined(_MSC_VER) || defined(__DMC__) || defined(__BORLANDC__) \
162 || defined(__WATCOMC__)
163 # if defined(_AMD64_) || defined(_M_X64) || _MSC_VER >= 1400
164 # if defined(_WIN32_WCE)
165 /* # include <cmnintrin.h> */
166 # elif defined(_MSC_VER)
169 # pragma intrinsic(_ReadWriteBarrier)
170 # define AO_compiler_barrier() _ReadWriteBarrier()
171 /* We assume this does not generate a fence instruction. */
172 /* The documentation is a bit unclear. */
174 # define AO_compiler_barrier() __asm { }
175 /* The preceding implementation may be preferable here too. */
176 /* But the documentation warns about VC++ 2003 and earlier. */
178 #elif defined(__INTEL_COMPILER)
179 # define AO_compiler_barrier() __memory_barrier() /* Too strong? IA64-only? */
180 #elif defined(_HPUX_SOURCE)
182 # include <machine/sys/inline.h>
183 # define AO_compiler_barrier() _Asm_sched_fence()
185 /* FIXME - We dont know how to do this. This is a guess. */
186 /* And probably a bad one. */
187 static volatile int AO_barrier_dummy;
188 # define AO_compiler_barrier() (void)(AO_barrier_dummy = AO_barrier_dummy)
191 /* We conjecture that the following usually gives us the right */
192 /* semantics or an error. */
193 # define AO_compiler_barrier() asm("")
196 #if defined(AO_USE_PTHREAD_DEFS)
197 # include "atomic_ops/sysdeps/generic_pthread.h"
198 #endif /* AO_USE_PTHREAD_DEFS */
200 #if (defined(__CC_ARM) || defined(__ARMCC__)) && !defined(__GNUC__) \
201 && !defined(AO_USE_PTHREAD_DEFS)
202 # include "atomic_ops/sysdeps/armcc/arm_v6.h"
203 # define AO_GENERALIZE_TWICE
206 #if defined(__GNUC__) && !defined(AO_USE_PTHREAD_DEFS) \
207 && !defined(__INTEL_COMPILER)
208 # if defined(__i386__)
209 /* We don't define AO_USE_SYNC_CAS_BUILTIN for x86 here because */
210 /* it might require specifying additional options (like -march) */
211 /* or additional link libraries (if -march is not specified). */
212 # include "atomic_ops/sysdeps/gcc/x86.h"
213 # endif /* __i386__ */
214 # if defined(__x86_64__)
215 # if __GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 2)
216 /* It is safe to use __sync CAS built-in on this architecture. */
217 # define AO_USE_SYNC_CAS_BUILTIN
219 # include "atomic_ops/sysdeps/gcc/x86_64.h"
220 # endif /* __x86_64__ */
221 # if defined(__ia64__)
222 # include "atomic_ops/sysdeps/gcc/ia64.h"
223 # define AO_GENERALIZE_TWICE
224 # endif /* __ia64__ */
225 # if defined(__hppa__)
226 # include "atomic_ops/sysdeps/gcc/hppa.h"
227 # define AO_CAN_EMUL_CAS
228 # endif /* __hppa__ */
229 # if defined(__alpha__)
230 # include "atomic_ops/sysdeps/gcc/alpha.h"
231 # define AO_GENERALIZE_TWICE
232 # endif /* __alpha__ */
233 # if defined(__s390__)
234 # include "atomic_ops/sysdeps/gcc/s390.h"
235 # endif /* __s390__ */
236 # if defined(__sparc__)
237 # include "atomic_ops/sysdeps/gcc/sparc.h"
238 # define AO_CAN_EMUL_CAS
239 # endif /* __sparc__ */
240 # if defined(__m68k__)
241 # include "atomic_ops/sysdeps/gcc/m68k.h"
242 # endif /* __m68k__ */
243 # if defined(__powerpc__) || defined(__ppc__) || defined(__PPC__) \
244 || defined(__powerpc64__) || defined(__ppc64__)
245 # include "atomic_ops/sysdeps/gcc/powerpc.h"
246 # endif /* __powerpc__ */
247 # if defined(__arm__) && !defined(AO_USE_PTHREAD_DEFS)
248 # include "atomic_ops/sysdeps/gcc/arm.h"
249 # define AO_CAN_EMUL_CAS
250 # endif /* __arm__ */
251 # if defined(__cris__) || defined(CRIS)
252 # include "atomic_ops/sysdeps/gcc/cris.h"
253 # define AO_GENERALIZE_TWICE
255 # if defined(__mips__)
256 # include "atomic_ops/sysdeps/gcc/mips.h"
257 # endif /* __mips__ */
258 # if defined(__sh__) || defined(SH4)
259 # include "atomic_ops/sysdeps/gcc/sh.h"
260 # define AO_CAN_EMUL_CAS
262 # if defined(__avr32__)
263 # include "atomic_ops/sysdeps/gcc/avr32.h"
265 # if defined(__hexagon__)
266 # include "atomic_ops/sysdeps/gcc/hexagon.h"
268 #endif /* __GNUC__ && !AO_USE_PTHREAD_DEFS */
270 #if (defined(__IBMC__) || defined(__IBMCPP__)) && !defined(__GNUC__) \
271 && !defined(AO_USE_PTHREAD_DEFS)
272 # if defined(__powerpc__) || defined(__powerpc) || defined(__ppc__) \
273 || defined(__PPC__) || defined(_M_PPC) || defined(_ARCH_PPC) \
274 || defined(_ARCH_PWR)
275 # include "atomic_ops/sysdeps/ibmc/powerpc.h"
276 # define AO_GENERALIZE_TWICE
280 #if defined(__INTEL_COMPILER) && !defined(AO_USE_PTHREAD_DEFS)
281 # if defined(__ia64__)
282 # include "atomic_ops/sysdeps/icc/ia64.h"
283 # define AO_GENERALIZE_TWICE
285 # if defined(__GNUC__)
286 /* Intel Compiler in GCC compatible mode */
287 # if defined(__i386__)
288 # include "atomic_ops/sysdeps/gcc/x86.h"
289 # endif /* __i386__ */
290 # if defined(__x86_64__)
291 # if __INTEL_COMPILER > 1110
292 # define AO_USE_SYNC_CAS_BUILTIN
294 # include "atomic_ops/sysdeps/gcc/x86_64.h"
295 # endif /* __x86_64__ */
299 #if defined(_HPUX_SOURCE) && !defined(__GNUC__) && !defined(AO_USE_PTHREAD_DEFS)
301 # include "atomic_ops/sysdeps/hpc/ia64.h"
302 # define AO_GENERALIZE_TWICE
304 # include "atomic_ops/sysdeps/hpc/hppa.h"
305 # define AO_CAN_EMUL_CAS
309 #if defined(_MSC_VER) || defined(__DMC__) || defined(__BORLANDC__) \
310 || (defined(__WATCOMC__) && defined(__NT__))
311 # if defined(_AMD64_) || defined(_M_X64)
312 # include "atomic_ops/sysdeps/msftc/x86_64.h"
313 # elif defined(_M_IX86) || defined(x86)
314 # include "atomic_ops/sysdeps/msftc/x86.h"
315 # elif defined(_M_ARM) || defined(ARM) || defined(_ARM_)
316 # include "atomic_ops/sysdeps/msftc/arm.h"
317 # define AO_GENERALIZE_TWICE
321 #if defined(__sun) && !defined(__GNUC__) && !defined(AO_USE_PTHREAD_DEFS)
322 /* Note: use -DAO_USE_PTHREAD_DEFS if Sun CC does not handle inline asm. */
324 # include "atomic_ops/sysdeps/sunc/x86.h"
326 # if defined(__x86_64) || defined(__amd64)
327 # include "atomic_ops/sysdeps/sunc/x86_64.h"
328 # endif /* __x86_64 */
331 #if !defined(__GNUC__) && (defined(sparc) || defined(__sparc)) \
332 && !defined(AO_USE_PTHREAD_DEFS)
333 # include "atomic_ops/sysdeps/sunc/sparc.h"
334 # define AO_CAN_EMUL_CAS
337 #if defined(AO_REQUIRE_CAS) && !defined(AO_HAVE_compare_and_swap) \
338 && !defined(AO_HAVE_compare_and_swap_full) \
339 && !defined(AO_HAVE_compare_and_swap_acquire)
340 # if defined(AO_CAN_EMUL_CAS)
341 # include "atomic_ops/sysdeps/emul_cas.h"
343 # error Cannot implement AO_compare_and_swap_full on this architecture.
345 #endif /* AO_REQUIRE_CAS && !AO_HAVE_compare_and_swap ... */
347 /* The most common way to clear a test-and-set location */
348 /* at the end of a critical section. */
349 #if AO_AO_TS_T && !defined(AO_CLEAR)
350 # define AO_CLEAR(addr) AO_store_release((AO_TS_t *)(addr), AO_TS_CLEAR)
352 #if AO_CHAR_TS_T && !defined(AO_CLEAR)
353 # define AO_CLEAR(addr) AO_char_store_release((AO_TS_t *)(addr), AO_TS_CLEAR)
356 /* The generalization section. */
357 #if !defined(AO_GENERALIZE_TWICE) && defined(AO_CAN_EMUL_CAS) \
358 && !defined(AO_HAVE_compare_and_swap_full)
359 # define AO_GENERALIZE_TWICE
362 /* Theoretically we should repeatedly include atomic_ops_generalize.h. */
363 /* In fact, we observe that this converges after a small fixed number */
364 /* of iterations, usually one. */
365 #include "atomic_ops/generalize.h"
366 #ifdef AO_GENERALIZE_TWICE
367 # include "atomic_ops/generalize.h"
370 /* For compatibility with version 0.4 and earlier */
371 #define AO_TS_T AO_TS_t
373 #define AO_TS_VAL AO_TS_VAL_t
375 #endif /* ATOMIC_OPS_H */