include/sa/sa_atomic.h

filter: Statementstmt 100% 49 / 49 Branchbran 100% 6 / 6 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 100% 55 / 55 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« blib/lib/Shared/Arena.pm ↑ Summary
1 #ifndef SA_ATOMIC_H
2 #define SA_ATOMIC_H
3  
4 /* sa_atomic.h - the atomics probe, and the operations the arena is built from.
5 *
6 * THE PROBE IS OF A FEATURE, NOT A COMPILER VERSION. The __atomic builtins
7 * arrived in GCC 4.7, so __GNUC__ alone is the wrong question: asking it that
8 * way is what broke a FreeBSD 9 build elsewhere in this workspace, whose base
9 * cc is gcc 4.2.1. That compiler has the older __sync family (GCC 4.1), which
10 * says everything needed here - a lock test-and-set IS an acquire, a lock
11 * release IS a release, and a full barrier either side of a plain aligned word
12 * turns it into the acquire load / release store a slot is published with.
13 *
14 * WINDOWS GETS REAL ATOMICS HERE, and that is a departure from the sibling
15 * header in Hyperman, which disables them outright on _WIN32. Its reasoning is
16 * that an arena exists to make state exact across a forked pool and Windows has
17 * no fork, so per-process state is already exact. That reasoning does not
18 * transfer: a named region is the whole point of this dist, and on Windows a
19 * named region is the ONLY mode there is. A Windows build that fails open is a
20 * Windows build with no product.
21 *
22 * Only when no family exists at all is the whole thing disabled, and every
23 * caller fails open in that case. That is a supported configuration.
24 */
25  
26 #include <stdint.h>
27 #include <stddef.h>
28  
29 #if defined(__has_builtin)
30 # if __has_builtin(__atomic_load_n)
31 # define SA_ATOMIC_GNU 1
32 # endif
33 #endif
34 #if !defined(SA_ATOMIC_GNU) && defined(__GNUC__) \
35 && (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 7))
36 # define SA_ATOMIC_GNU 1
37 #endif
38  
39 /* SA_NO_ATOMICS is Makefile.PL's verdict, and it outranks every family check
40 * below. The probe compiles AND links a 64-bit compare-and-swap, so it sees the
41 * one case those checks cannot: a compiler that has the builtins on a target
42 * where they fail to link. Until 0.03 the define was set and nothing read it,
43 * so that target built the atomic paths anyway and failed at dlopen. It is also
44 * how a build with no atomics is compiled and tested on a machine that has
45 * them: make DEFINE=-DSA_NO_ATOMICS */
46 #if defined(SA_NO_ATOMICS)
47 # define SA_HAVE_ATOMICS 0
48 #elif defined(SA_ATOMIC_GNU)
49 # define SA_HAVE_ATOMICS 1
50 #elif defined(__GNUC__) \
51 && (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 1))
52 /* The __sync family. Note for whoever ports this to a 32-bit target: the
53 * 64-bit __sync builtins can LINK-fail rather than compile-fail on x86 without
54 * -march=i586 or better, so Makefile.PL's probe compiles AND links a 64-bit
55 * compare-and-swap. A probe that only compiles would pass here and fail at
56 * dlopen, which is the worst place to find out. */
57 # define SA_HAVE_ATOMICS 1
58 # define SA_ATOMIC_SYNC 1
59 #elif defined(_MSC_VER)
60 /* Untested: Strawberry is MinGW, which takes the GNU path above, so no smoker
61 * in reach compiles this branch. It is here so an MSVC build is a compile
62 * error to fix rather than a silent fail-open. */
63 # include <windows.h>
64 # include <intrin.h>
65 # define SA_HAVE_ATOMICS 1
66 # define SA_ATOMIC_MSVC 1
67 #else
68 # define SA_HAVE_ATOMICS 0
69 #endif
70  
71 /* ---- A 32-BIT TARGET CANNOT LOAD 64 BITS IN ONE GO -------------------------
72 *
73 * A naturally aligned 32-bit word is indivisible everywhere this builds. A
74 * 64-bit one is NOT: on 32-bit x86 and 32-bit ARM a plain `uint64_t v = *p` is
75 * two loads, and a reader can take the low half of one value and the high half
76 * of another. Every sequence in the ring and the arena's high-water mark are
77 * 64-bit, so a torn read there is a slot address out of thin air.
78 *
79 * The __atomic family already handles this: on a target that needs one it emits
80 * a locked compare-exchange, or calls libatomic. The __sync family has no
81 * 64-bit load at all, so where the machine word is narrow the pair below is
82 * built out of compare-and-swap instead - which is what makes them atomic
83 * rather than merely ordered. Makefile.PL link-probes a 64-bit CAS for exactly
84 * this reason, so a target that reaches here has one.
85 */
86 #if defined(UINTPTR_MAX) && UINTPTR_MAX <= 0xFFFFFFFFUL
87 # define SA_NARROW_WORD 1
88 #endif
89  
90 #define SA_LOCK_STRIPES 64 /* striped spinlocks in the header */
91 #define SA_SPIN_MAX 100000 /* bounded spin -> fail open */
92  
93 #if SA_HAVE_ATOMICS
94  
95 /* Reads and writes of a naturally aligned 32-bit word cannot tear on any target
96 * this builds on, and neither can a 64-bit one where the machine word is that
97 * wide. The barrier is what orders them against the other fields of the record
98 * they publish, and that is all the __sync spelling has to add. Where the word
99 * is narrower, see SA_NARROW_WORD above: the 64-bit pair becomes a CAS. */
100  
101 3007295 static int sa_at_tas(volatile unsigned char *l) {
102 #if defined(SA_ATOMIC_SYNC)
103 return __sync_lock_test_and_set(l, (unsigned char)1) != 0;
104 #elif defined(SA_ATOMIC_MSVC)
105 return _InterlockedExchange8((volatile char *)l, 1) != 0;
106 #else
107 3007295 return __atomic_test_and_set(l, __ATOMIC_ACQUIRE) != 0;
108 #endif
109 }
110  
111 46020 static void sa_at_clear(volatile unsigned char *l) {
112 #if defined(SA_ATOMIC_SYNC)
113 __sync_lock_release(l);
114 #elif defined(SA_ATOMIC_MSVC)
115 _InterlockedExchange8((volatile char *)l, 0);
116 #else
117 46020 __atomic_clear(l, __ATOMIC_RELEASE);
118 #endif
119 46020 }
120  
121 /* MemoryBarrier rather than _ReadWriteBarrier on the MSVC path, and the
122 * difference is not pedantry: _ReadWriteBarrier stops the COMPILER reordering
123 * and emits no instruction, which is enough on x86 and nothing at all on the
124 * ARM64 that MSVC also targets. This branch has no smoker, so it takes the
125 * spelling that is correct everywhere over the one that is cheaper on the
126 * machine nobody here is testing. */
127 98064554 static uint32_t sa_at_load32_acq(volatile uint32_t *p) {
128 #if defined(SA_ATOMIC_SYNC)
129 uint32_t v = *p;
130 __sync_synchronize(); /* nothing below may be hoisted above it */
131 return v;
132 #elif defined(SA_ATOMIC_MSVC)
133 uint32_t v = *p;
134 MemoryBarrier();
135 return v;
136 #else
137 98064554 return __atomic_load_n(p, __ATOMIC_ACQUIRE);
138 #endif
139 }
140  
141 1752013 static void sa_at_store32_rel(volatile uint32_t *p, uint32_t v) {
142 #if defined(SA_ATOMIC_SYNC)
143 __sync_synchronize(); /* the other fields land before this one */
144 *p = v;
145 #elif defined(SA_ATOMIC_MSVC)
146 MemoryBarrier();
147 *p = v;
148 #else
149 1752013 __atomic_store_n(p, v, __ATOMIC_RELEASE);
150 #endif
151 1752013 }
152  
153 /* Take the next N and return what this caller now owns, exclusively, across
154 * every process sharing the mapping. The bump allocator and the ring's
155 * reservation are both this one operation. */
156 1096181 static uint64_t sa_at_fetch_add64(volatile uint64_t *p, uint64_t n) {
157 #if defined(SA_ATOMIC_SYNC)
158 return __sync_fetch_and_add(p, n);
159 #elif defined(SA_ATOMIC_MSVC)
160 return (uint64_t)_InterlockedExchangeAdd64((volatile __int64 *)p,
161 (__int64)n);
162 #else
163 1096181 return __atomic_fetch_add(p, n, __ATOMIC_ACQ_REL);
164 #endif
165 }
166  
167 40790 static uint32_t sa_at_fetch_add32(volatile uint32_t *p, uint32_t n) {
168 #if defined(SA_ATOMIC_SYNC)
169 return __sync_fetch_and_add(p, n);
170 #elif defined(SA_ATOMIC_MSVC)
171 return (uint32_t)_InterlockedExchangeAdd((volatile long *)p, (long)n);
172 #else
173 40790 return __atomic_fetch_add(p, n, __ATOMIC_ACQ_REL);
174 #endif
175 }
176  
177 /* Set bits in a word and return what was there before. A bloom filter is
178 * nothing but this: no other operation in this dist needs it, because no other
179 * structure lets two processes modify one word without agreeing first. */
180 180740 static uint64_t sa_at_fetch_or64(volatile uint64_t *p, uint64_t bits) {
181 #if defined(SA_ATOMIC_SYNC)
182 return __sync_fetch_and_or(p, bits);
183 #elif defined(SA_ATOMIC_MSVC)
184 return (uint64_t)_InterlockedOr64((volatile __int64 *)p, (__int64)bits);
185 #else
186 180740 return __atomic_fetch_or(p, bits, __ATOMIC_ACQ_REL);
187 #endif
188 }
189  
190 /* Compare and swap a 64-bit word; 1 if this caller won.
191 *
192 * A shared cursor is advanced with this and never with a plain fetch-add. A
193 * fetch-add cannot be undone: a claimer that adds and then finds it overshot
194 * the last published sequence has ALREADY moved the shared cursor past
195 * sequences nobody has written, and those records are skipped forever with
196 * nothing counted, because nothing noticed. A CAS advances only when the
197 * caller both wins the race and is still inside what has been published. */
198 112343 static int sa_at_cas64(volatile uint64_t *p, uint64_t expect, uint64_t want) {
199 #if defined(SA_ATOMIC_SYNC)
200 return __sync_bool_compare_and_swap(p, expect, want) ? 1 : 0;
201 #elif defined(SA_ATOMIC_MSVC)
202 return _InterlockedCompareExchange64((volatile __int64 *)p, (__int64)want,
203 (__int64)expect) == (__int64)expect;
204 #else
205 112343 return __atomic_compare_exchange_n(p, &expect, want, 0,
206 __ATOMIC_ACQ_REL, __ATOMIC_ACQUIRE)
207 112343 ? 1 : 0;
208 #endif
209 }
210  
211 /* The 64-bit pair, DEFINED AFTER THE CAS BECAUSE ON A NARROW WORD THEY ARE ONE.
212 *
213 * On a 64-bit machine these are a plain aligned access plus the barrier that
214 * orders it. On a 32-bit one a plain access is two instructions and can tear,
215 * so the load becomes a compare-and-swap against a value it does not expect -
216 * which returns the current word whether or not it wins - and the store becomes
217 * a CAS loop. Slower, and the only spelling that is correct there. */
218 8496237 static uint64_t sa_at_load64_acq(volatile uint64_t *p) {
219 #if defined(SA_NARROW_WORD) && defined(SA_ATOMIC_SYNC)
220 return __sync_val_compare_and_swap(p, (uint64_t)0, (uint64_t)0);
221 #elif defined(SA_NARROW_WORD) && defined(SA_ATOMIC_MSVC)
222 return (uint64_t)_InterlockedCompareExchange64((volatile __int64 *)p, 0, 0);
223 #elif defined(SA_ATOMIC_SYNC)
224 uint64_t v = *p;
225 __sync_synchronize();
226 return v;
227 #elif defined(SA_ATOMIC_MSVC)
228 uint64_t v = *p;
229 MemoryBarrier();
230 return v;
231 #else
232 8496237 return __atomic_load_n(p, __ATOMIC_ACQUIRE);
233 #endif
234 }
235  
236 1661408 static void sa_at_store64_rel(volatile uint64_t *p, uint64_t v) {
237 #if defined(SA_NARROW_WORD) && (defined(SA_ATOMIC_SYNC) || defined(SA_ATOMIC_MSVC))
238 for (;;) {
239 uint64_t old = sa_at_load64_acq(p);
240 if (sa_at_cas64(p, old, v)) return;
241 }
242 #elif defined(SA_ATOMIC_SYNC)
243 __sync_synchronize();
244 *p = v;
245 #elif defined(SA_ATOMIC_MSVC)
246 MemoryBarrier();
247 *p = v;
248 #else
249 1661408 __atomic_store_n(p, v, __ATOMIC_RELEASE);
250 #endif
251 1661408 }
252  
253 712341 static int sa_at_cas32(volatile uint32_t *p, uint32_t expect, uint32_t want) {
254 #if defined(SA_ATOMIC_SYNC)
255 return __sync_bool_compare_and_swap(p, expect, want) ? 1 : 0;
256 #elif defined(SA_ATOMIC_MSVC)
257 return (uint32_t)_InterlockedCompareExchange((volatile long *)p,
258 (long)want, (long)expect)
259 == expect;
260 #else
261 712341 return __atomic_compare_exchange_n(p, &expect, want, 0,
262 __ATOMIC_ACQ_REL, __ATOMIC_ACQUIRE)
263 712341 ? 1 : 0;
264 #endif
265 }
266  
267 /* ---- fences, and why a release STORE is not enough -------------------------
268 *
269 * A release store orders everything BEFORE it against itself. It says nothing
270 * about the writes that come after, which are free to become visible to another
271 * CPU first. A seqlock writer that stores its sequence and then writes the body
272 * therefore has no guarantee the body does not arrive first - and a reader that
273 * sees the new body under the old sequence accepts it as whole.
274 *
275 * That is why the canonical seqlock has a barrier AFTER the opening sequence
276 * store and BEFORE the closing one, and a read barrier between the body and the
277 * second sequence load. Linux spells them smp_wmb and smp_rmb; these are the
278 * same two, over whichever builtin family exists.
279 *
280 * Getting this wrong is not theoretical and does not show up in a gentle test:
281 * it produced whole, well-formed records delivered under a sequence belonging
282 * to a different one, about ten times in sixteen thousand, only under real
283 * multi-process contention. */
284  
285 1636421 static void sa_at_fence_rel(void) {
286 #if defined(SA_ATOMIC_SYNC)
287 __sync_synchronize();
288 #elif defined(SA_ATOMIC_MSVC)
289 MemoryBarrier();
290 #else
291 1636421 __atomic_thread_fence(__ATOMIC_RELEASE);
292 #endif
293 1636421 }
294  
295 185605 static void sa_at_fence_acq(void) {
296 #if defined(SA_ATOMIC_SYNC)
297 __sync_synchronize();
298 #elif defined(SA_ATOMIC_MSVC)
299 MemoryBarrier();
300 #else
301 185605 __atomic_thread_fence(__ATOMIC_ACQUIRE);
302 #endif
303 185605 }
304  
305 /* Bounded acquire on a striped lock; 1 if taken, 0 if it gave up. A process
306 * that died holding one must not wedge everybody else, so the caller fails
307 * open rather than spinning forever. */
308 46020 static int sa_at_lock(volatile unsigned char *locks, uint64_t h) {
309 46020 volatile unsigned char *l = &locks[h % SA_LOCK_STRIPES];
310 46020 long spin = 0;
311 3007242 ▶ while (sa_at_tas(l)) {
Branch: 1 branch
BranchTrueFalseTotal
while (sa_at_tas(l)) { 2961236 46006 3007242
312 2961236 ▶ if (++spin >= SA_SPIN_MAX) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (++spin >= SA_SPIN_MAX) return 0; 14 2961222 2961236
313 }
314 46006 return 1;
315 }
316  
317 /* ONE attempt, no spin at all: 1 if taken, 0 if somebody else has it.
318 *
319 * For a caller that intends to sleep between attempts. sa_at_lock's spin is
320 * right when the holder is about to finish, and wrong when it is not running:
321 * a hundred thousand test-and-sets on the holder's own cache line make it
322 * slower to reach its unlock, so waiting harder makes the wait longer. */
323 53 static int sa_at_trylock(volatile unsigned char *locks, uint64_t h) {
324 53 return !sa_at_tas(&locks[h % SA_LOCK_STRIPES]);
325 }
326  
327 46020 static void sa_at_unlock(volatile unsigned char *locks, uint64_t h) {
328 46020 sa_at_clear(&locks[h % SA_LOCK_STRIPES]);
329 46020 }
330  
331 #else /* !SA_HAVE_ATOMICS */
332  
333 /* COMPILE-ONLY, AND NEVER REACHED. With no atomics sa_map_open refuses, so no
334 * region is ever created or attached and no tenant or handle ever exists to
335 * call any of these. They are here so that every caller need not be wrapped in
336 * #if SA_HAVE_ATOMICS: most callers were not, and the configuration this file
337 * calls supported did not build until 0.03. Plain accesses, which are right
338 * for one thread and would be wrong across processes; nothing runs them. */
339 static int sa_at_tas(volatile unsigned char *l) {
340 int was = *l != 0;
341 *l = 1;
342 return was;
343 }
344 static void sa_at_clear(volatile unsigned char *l) { *l = 0; }
345 static uint32_t sa_at_load32_acq(volatile uint32_t *p) { return *p; }
346 static void sa_at_store32_rel(volatile uint32_t *p, uint32_t v) { *p = v; }
347 static uint64_t sa_at_load64_acq(volatile uint64_t *p) { return *p; }
348 static void sa_at_store64_rel(volatile uint64_t *p, uint64_t v) { *p = v; }
349 static uint64_t sa_at_fetch_add64(volatile uint64_t *p, uint64_t n) {
350 uint64_t was = *p;
351 *p = was + n;
352 return was;
353 }
354 static uint32_t sa_at_fetch_add32(volatile uint32_t *p, uint32_t n) {
355 uint32_t was = *p;
356 *p = was + n;
357 return was;
358 }
359 static uint64_t sa_at_fetch_or64(volatile uint64_t *p, uint64_t bits) {
360 uint64_t was = *p;
361 *p = was | bits;
362 return was;
363 }
364 static int sa_at_cas64(volatile uint64_t *p, uint64_t expect, uint64_t want) {
365 if (*p != expect) return 0;
366 *p = want;
367 return 1;
368 }
369 static int sa_at_cas32(volatile uint32_t *p, uint32_t expect, uint32_t want) {
370 if (*p != expect) return 0;
371 *p = want;
372 return 1;
373 }
374 static void sa_at_fence_rel(void) { }
375 static void sa_at_fence_acq(void) { }
376 static int sa_at_lock(volatile unsigned char *locks, uint64_t h) {
377 return !sa_at_tas(&locks[h % SA_LOCK_STRIPES]);
378 }
379 static int sa_at_trylock(volatile unsigned char *locks, uint64_t h) {
380 return !sa_at_tas(&locks[h % SA_LOCK_STRIPES]);
381 }
382 static void sa_at_unlock(volatile unsigned char *locks, uint64_t h) {
383 sa_at_clear(&locks[h % SA_LOCK_STRIPES]);
384 }
385  
386 #endif /* SA_HAVE_ATOMICS */
387  
388 /* FNV-1a 64, for hashing a name onto a lock stripe. Not cryptographic and not
389 * meant to be: a collision costs a spin. */
390 1507379 static uint64_t sa_at_fnv(const void *data, size_t len) {
391 1507379 const unsigned char *p = (const unsigned char *)data;
392 1507379 uint64_t h = 1469598103934665603ULL;
393 size_t i;
394 11241592 ▶ for (i = 0; i < len; i++) { h ^= p[i]; h *= 1099511628211ULL; }
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < len; i++) { h ^= p[i]; h *= 1099511628211ULL; } 9734213 1507379 11241592
395 1507379 return h;
396 }
397  
398 #endif /* SA_ATOMIC_H */
« blib/lib/Shared/Arena.pm ↑ Summary