| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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 */ |