include/hyperman/hm_atomic.h

filter: Statementstmt 47.3% 5 / 38 (13 uncoverable) Branchbran 100% 2 / 6 (4 uncoverable) Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 54.5% 7 / 44 (17 uncoverable) CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« xs/quic.xs ↑ Summary include/hyperman/hm_http2.h »
1 /* hm_atomic.h - the atomics probe, and the handful of operations the
2 * fork-shared arena code is built from.
3 *
4 * Its own file because more than one header needs the same operations over
5 * the same builtins (today the FNV the abuse controls and the bus key on).
6 * Probed separately they would eventually disagree, on the one machine
7 * nobody develops on.
8 *
9 * THE PROBE IS OF A FEATURE, NOT A COMPILER VERSION. The __atomic builtins
10 * only arrived in GCC 4.7, so __GNUC__ alone is the wrong question and asking
11 * it broke the FreeBSD 9 build ('__ATOMIC_ACQUIRE' undeclared, base cc gcc
12 * 4.2.1). That compiler has the older __sync family (GCC 4.1), which says
13 * everything needed here: a lock test-and-set IS an acquire, a lock release
14 * IS a release, and a full barrier either side of a plain aligned word turns
15 * it into the acquire load / release store a slot is published with.
16 *
17 * Only when NEITHER family exists is the whole thing disabled, and every
18 * caller fails open in that case. That is a supported configuration.
19 */
20  
21 #ifndef HM_ATOMIC_H
22 #define HM_ATOMIC_H
23  
24 #include <stdint.h>
25  
26 #if defined(__has_builtin)
27 # if __has_builtin(__atomic_load_n)
28 # define HM_ATOMIC_GNU 1
29 # endif
30 #endif
31 #if !defined(HM_ATOMIC_GNU) && defined(__GNUC__) \
32 && (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 7))
33 # define HM_ATOMIC_GNU 1
34 #endif
35  
36 #if defined(_WIN32)
37 /* No arena on Windows, and nothing to lose by it: an arena exists so state is
38 * exact across a FORKED pool, and Windows runs a single worker (there is no
39 * fork there), where per-process state is exact by construction. Every caller
40 * is written to fail open with no arena, so this is the tested path rather
41 * than a new one. CreateFileMapping only becomes worth writing if a
42 * multi-process pool ever lands. */
43 # define HM_HAVE_ATOMICS 0
44 #elif defined(HM_ATOMIC_GNU)
45 # define HM_HAVE_ATOMICS 1
46 #elif defined(__GNUC__) \
47 && (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 1))
48 # define HM_HAVE_ATOMICS 1
49 # define HM_ATOMIC_SYNC 1
50 #else
51 # define HM_HAVE_ATOMICS 0
52 #endif
53  
54 #define HM_LOCK_STRIPES 64 /* spinlock stripes in an arena */
55 #define HM_SPIN_MAX 100000 /* bounded spin -> fail open */
56  
57 #if HM_HAVE_ATOMICS
58  
59 /* The operations an arena needs, over whichever builtin family exists.
60 *
61 * Reads and writes of a naturally aligned 32-bit or 64-bit word cannot tear
62 * on any target this builds on; the barrier is what orders them against the
63 * other fields of the slot they publish, and that is all the __sync spelling
64 * has to add. */
65  
66 /*
67 # uncoverable statement
68 # uncoverable subroutine */
69 0 static int hm_at_tas(volatile unsigned char *l) {
70 #if defined(HM_ATOMIC_SYNC)
71 return __sync_lock_test_and_set(l, (unsigned char)1) != 0;
72 #else
73 0 return __atomic_test_and_set(l, __ATOMIC_ACQUIRE) != 0; /* # uncoverable statement */
74 #endif
75 }
76  
77 /*
78 # uncoverable statement
79 # uncoverable subroutine */
80 0 static void hm_at_clear(volatile unsigned char *l) {
81 #if defined(HM_ATOMIC_SYNC)
82 __sync_lock_release(l);
83 #else
84 0 __atomic_clear(l, __ATOMIC_RELEASE); /* # uncoverable statement */
85 #endif
86 0 }
87  
88 /*
89 # uncoverable statement
90 # uncoverable subroutine */
91 0 static uint32_t hm_at_load32_acq(volatile uint32_t *p) {
92 #if defined(HM_ATOMIC_SYNC)
93 uint32_t v = *p;
94 __sync_synchronize(); /* nothing below may be hoisted above it */
95 return v;
96 #else
97 0 return __atomic_load_n(p, __ATOMIC_ACQUIRE); /* # uncoverable statement */
98 #endif
99 }
100  
101 /*
102 # uncoverable statement
103 # uncoverable subroutine */
104 0 static void hm_at_store32_rel(volatile uint32_t *p, uint32_t v) {
105 #if defined(HM_ATOMIC_SYNC)
106 __sync_synchronize(); /* the other fields land before this one */
107 *p = v;
108 #else
109 0 __atomic_store_n(p, v, __ATOMIC_RELEASE); /* # uncoverable statement */
110 #endif
111 0 }
112  
113 /* The 64-bit pair, for the bus: a sequence number that must not wrap in any
114 * plausible lifetime, and a slot stamped with the sequence it holds. */
115  
116 /*
117 # uncoverable statement
118 # uncoverable subroutine */
119 0 static uint64_t hm_at_load64_acq(volatile uint64_t *p) {
120 #if defined(HM_ATOMIC_SYNC)
121 uint64_t v = *p;
122 __sync_synchronize();
123 return v;
124 #else
125 0 return __atomic_load_n(p, __ATOMIC_ACQUIRE); /* # uncoverable statement */
126 #endif
127 }
128  
129 /*
130 # uncoverable statement
131 # uncoverable subroutine */
132 0 static void hm_at_store64_rel(volatile uint64_t *p, uint64_t v) {
133 #if defined(HM_ATOMIC_SYNC)
134 __sync_synchronize();
135 *p = v;
136 #else
137 0 __atomic_store_n(p, v, __ATOMIC_RELEASE); /* # uncoverable statement */
138 #endif
139 0 }
140  
141 /* The one that makes a queue group work: take the next sequence and return
142 * the one this caller now owns, exclusively, across every process sharing the
143 * mapping. Both families spell it the same way. */
144 /*
145 # uncoverable statement
146 # uncoverable subroutine */
147 0 static uint64_t hm_at_fetch_add64(volatile uint64_t *p, uint64_t n) {
148 #if defined(HM_ATOMIC_SYNC)
149 return __sync_fetch_and_add(p, n);
150 #else
151 0 return __atomic_fetch_add(p, n, __ATOMIC_ACQ_REL); /* # uncoverable statement */
152 #endif
153 }
154  
155 /* Compare and swap a 64-bit word; 1 if this caller won.
156 *
157 * The queue group's claim needs this rather than a plain fetch-add. A
158 * fetch-add cannot be undone: a claimer that adds and then finds it overshot
159 * the last published sequence has ALREADY moved the shared cursor past
160 * sequences that have not been written yet, and those messages are then
161 * skipped forever - with nothing counted, because nothing noticed. A CAS
162 * advances only when the caller both wins the race and is still inside what
163 * has been published. */
164 /*
165 # uncoverable statement
166 # uncoverable subroutine */
167 0 static int hm_at_cas64(volatile uint64_t *p, uint64_t expect, uint64_t want) {
168 #if defined(HM_ATOMIC_SYNC)
169 return __sync_bool_compare_and_swap(p, expect, want) ? 1 : 0;
170 #else
171 0 return __atomic_compare_exchange_n(p, &expect, want, 0, /* # uncoverable statement */
172 __ATOMIC_ACQ_REL, __ATOMIC_ACQUIRE)
173 0 ? 1 : 0; /* # uncoverable statement */
174 #endif
175 }
176  
177 /* Set a flag from 0 to 1 and say whether this caller was the one who did it.
178 * The bus wakeup needs exactly this: whoever wins pokes the worker, everybody
179 * else has nothing to do. */
180 /*
181 # uncoverable statement
182 # uncoverable subroutine */
183 0 static int hm_at_test_and_set32(volatile uint32_t *p) {
184 #if defined(HM_ATOMIC_SYNC)
185 return __sync_bool_compare_and_swap(p, 0u, 1u) ? 1 : 0;
186 #else
187 0 uint32_t expect = 0; /* # uncoverable statement */
188 0 return __atomic_compare_exchange_n(p, &expect, 1u, 0, /* # uncoverable statement */
189 __ATOMIC_ACQ_REL, __ATOMIC_ACQUIRE)
190 0 ? 1 : 0; /* # uncoverable statement */
191 #endif
192 }
193  
194 /* Bounded acquire on a striped lock; returns 1 if it was taken, 0 if it gave
195 * up. A worker that died holding one must not wedge the pool, so the caller
196 * fails open rather than spinning forever. */
197 /*
198 # uncoverable statement
199 # uncoverable subroutine */
200 0 static int hm_at_lock(volatile unsigned char *locks, uint64_t h) {
201 0 volatile unsigned char *l = &locks[h % HM_LOCK_STRIPES]; /* # uncoverable statement */
202 0 long spin = 0; /* # uncoverable statement */
203 /*
204 # uncoverable statement
205 # uncoverable branch true
206 # uncoverable branch false
207 # uncoverable condition left count:1
208 # uncoverable condition right count:1 */
209 0 ▶ while (hm_at_tas(l)) {
Branch: 1 branch
BranchTrueFalseTotal
while (hm_at_tas(l)) { 0 0 0
210 /*
211 # uncoverable statement
212 # uncoverable branch true
213 # uncoverable branch false
214 # uncoverable condition left count:1
215 # uncoverable condition right count:1 */
216 0 ▶ if (++spin >= HM_SPIN_MAX) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (++spin >= HM_SPIN_MAX) return 0; 0 0 0
217 }
218 0 return 1; /* # uncoverable statement */
219 }
220  
221 /*
222 # uncoverable statement
223 # uncoverable subroutine */
224 0 static void hm_at_unlock(volatile unsigned char *locks, uint64_t h) {
225 0 hm_at_clear(&locks[h % HM_LOCK_STRIPES]); /* # uncoverable statement */
226 0 }
227  
228 #endif /* HM_HAVE_ATOMICS */
229  
230 /* FNV-1a 64, for hashing a key onto a table slot. Not cryptographic and not
231 * meant to be: the tables it indexes hold no secret, and a collision costs a
232 * probe. */
233 23 static uint64_t hm_at_fnv(const void *data, size_t len) {
234 23 const unsigned char *p = (const unsigned char *)data;
235 23 uint64_t h = 1469598103934665603ULL;
236 size_t i;
237 164 ▶ 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; } 141 23 164
238 23 return h;
239 }
240  
241 #endif /* HM_ATOMIC_H */
« xs/quic.xs ↑ Summary include/hyperman/hm_http2.h »