| 1 |
|
| #ifndef SA_ARENA_H |
| 2 |
|
| #define SA_ARENA_H |
| 3 |
|
| |
| 4 |
|
| /* sa_arena.h - the handle, the bump allocator and the name registry. |
| 5 |
|
| * Perl-free. |
| 6 |
|
| * |
| 7 |
|
| * ---- the handle is process-local, and that is the point --------------------- |
| 8 |
|
| * |
| 9 |
|
| * Everything a process knows about a region that is NOT shared lives here: |
| 10 |
|
| * the base address it mapped at, the length, the name it opened. A consuming |
| 11 |
|
| * .so gets its own handle and shares the region, rather than getting its own |
| 12 |
|
| * copy of a static and quietly sharing nothing - which is the failure this |
| 13 |
|
| * design starts from. |
| 14 |
|
| * |
| 15 |
|
| * ---- allocation is a bump, and there is no free ----------------------------- |
| 16 |
|
| * |
| 17 |
|
| * A sub-region is carved by advancing a high-water offset and lives as long as |
| 18 |
|
| * the region does. That is a deliberate limit rather than an omission. |
| 19 |
|
| * |
| 20 |
|
| * A free list in shared memory is corrupted permanently by one process dying |
| 21 |
|
| * between two stores, and unlike a torn record there is no way to detect it |
| 22 |
|
| * afterwards or bound the damage: the next allocation hands out memory somebody |
| 23 |
|
| * else is using. Nothing that wants an arena needs to release a sub-region - a |
| 24 |
|
| * bus takes one for its whole life, a rate limiter takes two tables, a bloom |
| 25 |
|
| * filter takes three. A caller who genuinely needs reuse can implement it |
| 26 |
|
| * INSIDE its own carved region, where getting it wrong costs one feature |
| 27 |
|
| * instead of the whole arena. |
| 28 |
|
| * |
| 29 |
|
| * ---- the registry is what makes attaching worth anything -------------------- |
| 30 |
|
| * |
| 31 |
|
| * Without it, a second process has to be told an offset out of band, which |
| 32 |
|
| * means the two builds must agree on a layout neither can check. With it, a |
| 33 |
|
| * late arriver asks for "events" and is handed the offset and the length, or |
| 34 |
|
| * nothing. |
| 35 |
|
| */ |
| 36 |
|
| |
| 37 |
|
| #include "sa/sa_map.h" |
| 38 |
|
| |
| 39 |
|
| #ifndef SA_REGION_FWD |
| 40 |
|
| #define SA_REGION_FWD |
| 41 |
|
| typedef struct sa_region sa_region; |
| 42 |
|
| #endif |
| 43 |
|
| |
| 44 |
|
| struct sa_region { |
| 45 |
|
| sa_map map; |
| 46 |
|
| sa_header *hdr; /* == map.base, cached */ |
| 47 |
|
| uint64_t total; |
| 48 |
|
| int created; /* did THIS process create it */ |
| 49 |
|
| |
| 50 |
|
| /* This process's peer slot, filled lazily on first use. `peer_pid` is |
| 51 |
|
| * what makes a fork child take a slot of its OWN rather than inheriting |
| 52 |
|
| * its parent's, which would attribute the child's records to the wrong |
| 53 |
|
| * process and make a crash unprovable. */ |
| 54 |
|
| int peer_idx; |
| 55 |
|
| uint32_t peer_epoch; |
| 56 |
|
| uint64_t peer_pid; |
| 57 |
|
| |
| 58 |
|
| /* Why the last region lookup or carve on THIS handle came back empty. |
| 59 |
|
| * |
| 60 |
|
| * Diagnostic only, and on the handle rather than at file scope so two |
| 61 |
|
| * handles - or two ithreads - do not overwrite each other's answer. It |
| 62 |
|
| * exists because an empty list is not a reason: a smoker that refused two |
| 63 |
|
| * carves could not say whether the arena was full or a stripe was busy, |
| 64 |
|
| * and those want opposite responses from the caller. */ |
| 65 |
|
| int last_err; |
| 66 |
|
| |
| 67 |
|
| /* The waker table, carved like any other sub-region and found by name, so |
| 68 |
|
| * a fork child resolves it without being told where it is. */ |
| 69 |
|
| uint64_t wakers_off; |
| 70 |
|
| uint32_t wakers_max; |
| 71 |
|
| int waker_idx; |
| 72 |
|
| /* Looked for the waker table and found none. Cached, because sa_wake_poke |
| 73 |
|
| * runs on every publish and a registry walk per record on a ring that |
| 74 |
|
| * simply has no wakers was a measurable share of the publish. wake_init |
| 75 |
|
| * clears it. */ |
| 76 |
|
| int wakers_probed; |
| 77 |
|
| |
| 78 |
|
| /* Whether the descriptors in the waker table are the ones THIS process |
| 79 |
|
| * holds, answered once with an fstat and cached here rather than in the |
| 80 |
|
| * mapping - it is a fact about this process, not about the region. See the |
| 81 |
|
| * identity comment in sa_wake.h. */ |
| 82 |
|
| int wake_checked; |
| 83 |
|
| int wake_ok; |
| 84 |
|
| uint64_t wake_pid; |
| 85 |
|
| }; |
| 86 |
|
| |
| 87 |
|
| /* ---- carving --------------------------------------------------------------- */ |
| 88 |
|
| |
| 89 |
|
| /* Advance the high-water mark by `len` and return the offset, or 0 when the |
| 90 |
|
| * region is full. Offset 0 is never a valid carve, because the header lives |
| 91 |
|
| * there, so 0 doubles as the failure value. |
| 92 |
|
| * |
| 93 |
|
| * A CAS loop rather than a fetch-add: a fetch-add that overshoots has already |
| 94 |
|
| * consumed the space it could not use, so a region that refuses one oversized |
| 95 |
|
| * carve would go on refusing every small one after it. */ |
| 96 |
40779 |
| static uint64_t sa_bump(sa_region *r, uint64_t len) { |
| 97 |
|
| #if !SA_HAVE_ATOMICS |
| 98 |
|
| (void)r; (void)len; |
| 99 |
|
| return 0; |
| 100 |
|
| #else |
| 101 |
40779 |
| sa_header *h = r->hdr; |
| 102 |
|
| uint64_t old, want; |
| 103 |
|
| for (;;) { |
| 104 |
40849 |
| old = sa_at_load64_acq(&h->brk); |
| 105 |
40849 |
| want = sa_align_up(old); |
| 106 |
40849 |
▶ | if (want + len > h->total || want + len < want) return 0; |
Branch: 2 branches
| Branch | True | False | Total |
| if (want + len > h->total || want + len < want) return 0; |
40848 |
1 |
40849 |
| if (want + len > h->total || want + len < want) return 0; |
0 |
40848 |
40848 |
|
| 107 |
40848 |
▶ | if (sa_at_cas64(&h->brk, old, want + len)) return want; |
Branch: 1 branch
| Branch | True | False | Total |
| if (sa_at_cas64(&h->brk, old, want + len)) return want; |
40778 |
70 |
40848 |
|
| 108 |
|
| } |
| 109 |
|
| #endif |
| 110 |
|
| } |
| 111 |
|
| |
| 112 |
|
| /* ---- AN OFFSET IS NOT ENOUGH: A STRUCTURE HAS A LENGTH -------------------- |
| 113 |
|
| * |
| 114 |
|
| * sa_ptr answers whether the START of something is inside the mapping, which |
| 115 |
|
| * is not the question a caller about to read a structure is asking. Every |
| 116 |
|
| * tenant used to bind with it and then check its own size against the registry |
| 117 |
|
| * entry's `len` - a number that comes OUT OF THE SHARED SEGMENT, so anybody |
| 118 |
|
| * who can write to the segment chooses it. |
| 119 |
|
| * |
| 120 |
|
| * Measured: a process that knew only the name rewrote one registry entry to |
| 121 |
|
| * `off = total - 64, len = 1GB`, and the next process to bind that ring wrote |
| 122 |
|
| * about twenty-one kilobytes past the end of its own mapping. SIGSEGV, and the |
| 123 |
|
| * POD at the time promised that "a reader will not follow a length past the |
| 124 |
|
| * end of a mapping". t/30-bounds.t is that PoC. |
| 125 |
|
| * |
| 126 |
|
| * This is the check that makes the promise true. The comparison is written as |
| 127 |
|
| * `off > total - len` rather than `off + len > total` BECAUSE THE ADDITION CAN |
| 128 |
|
| * WRAP: with a 64-bit len chosen by an attacker, `off + len` is small again and |
| 129 |
|
| * the guard passes the very case it exists to refuse. |
| 130 |
|
| * |
| 131 |
|
| * The lower bound keeps a carve off the header, the registry and the peer |
| 132 |
|
| * table, which is where a hostile entry would point to make a tenant's memset |
| 133 |
|
| * eat the arena's own bookkeeping. */ |
| 134 |
5748 |
| static void *sa_ptr_len(sa_region *r, uint64_t off, uint64_t len) { |
| 135 |
|
| uint64_t floor; |
| 136 |
5748 |
▶ | if (!r || !r->map.base || !r->hdr) return NULL; |
Branch: 3 branches
| Branch | True | False | Total |
| if (!r || !r->map.base || !r->hdr) return NULL; |
5748 |
0 |
5748 |
| if (!r || !r->map.base || !r->hdr) return NULL; |
5748 |
0 |
5748 |
| if (!r || !r->map.base || !r->hdr) return NULL; |
0 |
5748 |
5748 |
|
| 137 |
5748 |
| floor = r->hdr->peers_off |
| 138 |
5748 |
| + (uint64_t)r->hdr->peers_max * (uint64_t)sizeof(sa_peer); |
| 139 |
5748 |
▶ | if (off < floor) return NULL; |
Branch: 1 branch
| Branch | True | False | Total |
| if (off < floor) return NULL; |
0 |
5748 |
5748 |
|
| 140 |
5748 |
▶ | if (len > r->total) return NULL; |
Branch: 1 branch
| Branch | True | False | Total |
| if (len > r->total) return NULL; |
1 |
5747 |
5748 |
|
| 141 |
5747 |
▶ | if (off > r->total - len) return NULL; |
Branch: 1 branch
| Branch | True | False | Total |
| if (off > r->total - len) return NULL; |
0 |
5747 |
5747 |
|
| 142 |
5747 |
| return SA_AT(r->map.base, off); |
| 143 |
|
| } |
| 144 |
|
| |
| 145 |
|
| /* Does this registry entry describe bytes that are actually in the mapping? |
| 146 |
|
| * |
| 147 |
|
| * Checked where an entry is READ rather than in each of the seven tenants that |
| 148 |
|
| * use one, so a tenant added later cannot forget it. An entry that fails is |
| 149 |
|
| * treated as not live: a name that does not resolve, rather than a pointer |
| 150 |
|
| * into somebody else's memory. */ |
| 151 |
4844 |
| static int sa_reg_ok(sa_region *r, const sa_reg *e) { |
| 152 |
4844 |
▶ | return e && sa_ptr_len(r, e->off, e->len) != NULL; |
Branch: 2 branches
| Branch | True | False | Total |
| return e && sa_ptr_len(r, e->off, e->len) != NULL; |
4844 |
0 |
4844 |
| return e && sa_ptr_len(r, e->off, e->len) != NULL; |
4843 |
1 |
4844 |
|
| 153 |
|
| } |
| 154 |
|
| |
| 155 |
|
| /* The registry entry for a name, or NULL. |
| 156 |
|
| * |
| 157 |
|
| * Only entries whose `state` has been published are visible, so a carve that is |
| 158 |
|
| * still being filled in is invisible rather than half-readable. */ |
| 159 |
45673 |
| static sa_reg *sa_find(sa_region *r, const char *name, size_t nlen) { |
| 160 |
|
| #if !SA_HAVE_ATOMICS |
| 161 |
|
| (void)r; (void)name; (void)nlen; |
| 162 |
|
| return NULL; |
| 163 |
|
| #else |
| 164 |
45673 |
| sa_header *h = r->hdr; |
| 165 |
45673 |
| sa_reg *regs = SA_REGS(r->map.base, h); |
| 166 |
|
| uint32_t used, i; |
| 167 |
|
| |
| 168 |
45673 |
▶ | if (!name || !nlen || nlen >= SA_NAMELEN) return NULL; |
Branch: 3 branches
| Branch | True | False | Total |
| if (!name || !nlen || nlen >= SA_NAMELEN) return NULL; |
45673 |
0 |
45673 |
| if (!name || !nlen || nlen >= SA_NAMELEN) return NULL; |
45673 |
0 |
45673 |
| if (!name || !nlen || nlen >= SA_NAMELEN) return NULL; |
0 |
45673 |
45673 |
|
| 169 |
45673 |
| used = sa_at_load32_acq(&h->reg_used); |
| 170 |
45673 |
▶ | if (used > h->reg_max) used = h->reg_max; |
Branch: 1 branch
| Branch | True | False | Total |
| if (used > h->reg_max) used = h->reg_max; |
9 |
45664 |
45673 |
|
| 171 |
|
| |
| 172 |
88017660 |
▶ | for (i = 0; i < used; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < used; i++) { |
87976830 |
40830 |
88017660 |
|
| 173 |
87976830 |
▶ | if (sa_at_load32_acq(®s[i].state) != SA_R_LIVE) continue; |
Branch: 1 branch
| Branch | True | False | Total |
| if (sa_at_load32_acq(®s[i].state) != SA_R_LIVE) continue; |
1 |
87976829 |
87976830 |
|
| 174 |
|
| /* memcmp, not strncmp: a name is `nlen` bytes and the reserved ones |
| 175 |
|
| * begin with a NUL, so strncmp called "\0leases" and "\0wakers" the |
| 176 |
|
| * same name and a region with a lease refused its wakers as a shape |
| 177 |
|
| * mismatch. */ |
| 178 |
87976829 |
▶ | if (memcmp(regs[i].name, name, nlen) == 0 && regs[i].name[nlen] == '\0') { |
Branch: 2 branches
| Branch | True | False | Total |
| if (memcmp(regs[i].name, name, nlen) == 0 && regs[i].name[nlen] == '\0') { |
4846 |
87971983 |
87976829 |
| if (memcmp(regs[i].name, name, nlen) == 0 && regs[i].name[nlen] == '\0') { |
4844 |
2 |
4846 |
|
| 179 |
|
| /* AN ENTRY WHOSE EXTENT IS NOT IN THE MAPPING IS NOT AN ENTRY, so |
| 180 |
|
| * it is skipped exactly as a non-live one is - not treated as a |
| 181 |
|
| * fatal answer for the name. |
| 182 |
|
| * |
| 183 |
|
| * Returning NULL here instead looks safer and is worse twice over: |
| 184 |
|
| * the name becomes permanently unresolvable, AND sa_carve, finding |
| 185 |
|
| * nothing, carves a SECOND entry under the same name. One bad word |
| 186 |
|
| * in the registry would shadow a working region for the life of the |
| 187 |
|
| * arena. Skipping means the bad entry describes nothing anybody |
| 188 |
|
| * will dereference, and a good entry for that name still wins. |
| 189 |
|
| * |
| 190 |
|
| * It is counted, because a refused entry means either corruption or |
| 191 |
|
| * somebody writing to the segment who should not be, and a fallback |
| 192 |
|
| * that says nothing is how that goes unnoticed. */ |
| 193 |
4844 |
▶ | if (!sa_reg_ok(r, ®s[i])) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (!sa_reg_ok(r, ®s[i])) { |
1 |
4843 |
4844 |
|
| 194 |
1 |
| sa_at_fetch_add32(&h->reg_refused, 1); |
| 195 |
1 |
| continue; |
| 196 |
|
| } |
| 197 |
4843 |
| return ®s[i]; |
| 198 |
|
| } |
| 199 |
|
| } |
| 200 |
40830 |
| return NULL; |
| 201 |
|
| #endif |
| 202 |
|
| } |
| 203 |
|
| |
| 204 |
|
| /* Carve a named sub-region, or return the existing one with that name. |
| 205 |
|
| * |
| 206 |
|
| * Returning the existing one rather than refusing is what lets every process |
| 207 |
|
| * run the same setup code: whoever gets there first creates it, everybody else |
| 208 |
|
| * finds it, and no caller has to know which it was. The type and length are |
| 209 |
|
| * checked against what is already there, because two processes disagreeing |
| 210 |
|
| * about the shape of a region is worse than either of them failing. |
| 211 |
|
| * |
| 212 |
|
| * Writes *err and returns NULL on refusal. Never croaks: the reader is C. |
| 213 |
|
| */ |
| 214 |
|
| /* A bounded acquire that SLEEPS between attempts instead of spinning through |
| 215 |
|
| * its whole budget in one go. |
| 216 |
|
| * |
| 217 |
|
| * sa_at_lock is a pure spin, which is right on a hot path where the holder is |
| 218 |
|
| * about to finish and a sleep would cost more than the wait. It is wrong where |
| 219 |
|
| * there are more contenders than there are cores: the budget burns while the |
| 220 |
|
| * process actually holding the lock is not scheduled at all, and the caller is |
| 221 |
|
| * refused for being unlucky rather than for anything being full. |
| 222 |
|
| * |
| 223 |
|
| * Found on a 32-bit perl under emulation, eight processes carving four |
| 224 |
|
| * thousand regions: FOUR were refused, every run, deterministically, while the |
| 225 |
|
| * same four thousand carved serially were all fine. That is not a full arena, |
| 226 |
|
| * it is a spin that never got a turn. |
| 227 |
|
| * |
| 228 |
|
| * Still bounded, and that is not negotiable: a process that died holding a |
| 229 |
|
| * stripe must not wedge everybody who comes after it. The budget is just spent |
| 230 |
|
| * as sleeps rather than as one long burn, so the holder gets a chance to run |
| 231 |
|
| * and hand it over. |
| 232 |
|
| * |
| 233 |
|
| * SIXTY-FOUR FIFTY-MICROSECOND SLEEPS WAS STILL A GUESS ABOUT THE SCHEDULER, |
| 234 |
|
| * and a loaded smoker beat it: FreeBSD 15 on perl 5.42.2 refused two carves in |
| 235 |
|
| * four thousand, with room in the arena for every one of them and the serial |
| 236 |
|
| * arm of the same test passing. Three milliseconds is an ordinary amount of |
| 237 |
|
| * time not to be scheduled on a box running a dozen builds. |
| 238 |
|
| * |
| 239 |
|
| * So the wait escalates instead: a spin first, because the usual holder really |
| 240 |
|
| * is about to finish, then sleeps doubling from 50us to a 20ms ceiling. That |
| 241 |
|
| * spends about two seconds over its rounds - the same budget sa_map_open |
| 242 |
|
| * already allows a half-written header (SA_CREATE_WAIT_US), and for the same |
| 243 |
|
| * reason. An ordinary preemption becomes invisible; a process that died |
| 244 |
|
| * holding the stripe still hands everybody else a refusal rather than a hang. |
| 245 |
|
| * |
| 246 |
|
| * The retries after the first are a single test-and-set, NOT another spin: |
| 247 |
|
| * hammering the lock byte from eight waiters is what keeps the holder from |
| 248 |
|
| * reaching its own unlock. See sa_at_trylock. |
| 249 |
|
| * |
| 250 |
|
| * For rare operations only - carving a region, publishing a block, a worker |
| 251 |
|
| * claiming its row. A per-request path takes sa_lock_wait_brief below. */ |
| 252 |
|
| #define SA_LOCK_ROUNDS 110 |
| 253 |
|
| #define SA_LOCK_STALL_US 50 |
| 254 |
|
| #define SA_LOCK_STALL_MAX 20000 |
| 255 |
|
| |
| 256 |
|
| /* The escalation with its budget as arguments: one shape, two budgets, so a |
| 257 |
|
| * path that cannot afford two seconds does not grow its own copy of the loop |
| 258 |
|
| * with its own guess in it. */ |
| 259 |
43417 |
| static int sa_lock_wait_for(volatile unsigned char *locks, uint64_t h, |
| 260 |
|
| int rounds, uint32_t stall_max) { |
| 261 |
|
| int round; |
| 262 |
43417 |
| uint32_t us = SA_LOCK_STALL_US; |
| 263 |
|
| |
| 264 |
43417 |
▶ | if (sa_at_lock(locks, h)) return 1; |
Branch: 1 branch
| Branch | True | False | Total |
| if (sa_at_lock(locks, h)) return 1; |
43417 |
0 |
43417 |
|
| 265 |
0 |
▶ | for (round = 0; round < rounds; round++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (round = 0; round < rounds; round++) { |
0 |
0 |
0 |
|
| 266 |
0 |
| sa_stall(us); |
| 267 |
0 |
▶ | if (sa_at_trylock(locks, h)) return 1; |
Branch: 1 branch
| Branch | True | False | Total |
| if (sa_at_trylock(locks, h)) return 1; |
0 |
0 |
0 |
|
| 268 |
0 |
▶ | if (us < stall_max) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (us < stall_max) { |
0 |
0 |
0 |
|
| 269 |
0 |
| us *= 2; |
| 270 |
0 |
▶ | if (us > stall_max) us = stall_max; |
Branch: 1 branch
| Branch | True | False | Total |
| if (us > stall_max) us = stall_max; |
0 |
0 |
0 |
|
| 271 |
|
| } |
| 272 |
|
| } |
| 273 |
0 |
| return 0; |
| 274 |
|
| } |
| 275 |
|
| |
| 276 |
41100 |
| static int sa_lock_wait(volatile unsigned char *locks, uint64_t h) { |
| 277 |
41100 |
| return sa_lock_wait_for(locks, h, SA_LOCK_ROUNDS, SA_LOCK_STALL_MAX); |
| 278 |
|
| } |
| 279 |
|
| |
| 280 |
|
| /* The per-request budget: sleeps doubling from 50us to a 2ms ceiling, about |
| 281 |
|
| * fifteen milliseconds over its rounds. Enough to cover an ordinary preemption |
| 282 |
|
| * of the holder, which is the only thing that was ever wrong, and short enough |
| 283 |
|
| * that a store, an incr or a lease renew stalled behind a descheduled holder |
| 284 |
|
| * does not do more damage waiting than the lost answer would have. The map's |
| 285 |
|
| * write path and the lease's acquire, renew and release take this one. */ |
| 286 |
|
| #define SA_LOCK_BRIEF_ROUNDS 12 |
| 287 |
|
| #define SA_LOCK_BRIEF_MAX 2000 |
| 288 |
|
| |
| 289 |
2317 |
| static int sa_lock_wait_brief(volatile unsigned char *locks, uint64_t h) { |
| 290 |
2317 |
| return sa_lock_wait_for(locks, h, SA_LOCK_BRIEF_ROUNDS, SA_LOCK_BRIEF_MAX); |
| 291 |
|
| } |
| 292 |
|
| |
| 293 |
40968 |
| static sa_reg *sa_carve(sa_region *r, const char *name, size_t nlen, |
| 294 |
|
| uint64_t len, uint32_t type, int *err) |
| 295 |
|
| { |
| 296 |
|
| #if !SA_HAVE_ATOMICS |
| 297 |
|
| (void)r; (void)name; (void)nlen; (void)len; (void)type; |
| 298 |
|
| if (err) *err = SA_E_NOATOMICS; |
| 299 |
|
| return NULL; |
| 300 |
|
| #else |
| 301 |
40968 |
| sa_header *h = r->hdr; |
| 302 |
|
| sa_reg *regs, *e; |
| 303 |
|
| uint64_t off, hash; |
| 304 |
|
| uint32_t idx; |
| 305 |
|
| |
| 306 |
40968 |
▶ | if (err) *err = SA_E_OK; |
Branch: 1 branch
| Branch | True | False | Total |
| if (err) *err = SA_E_OK; |
40968 |
0 |
40968 |
|
| 307 |
40968 |
▶ | if (!name || !nlen || nlen >= SA_NAMELEN) { |
Branch: 3 branches
| Branch | True | False | Total |
| if (!name || !nlen || nlen >= SA_NAMELEN) { |
40968 |
0 |
40968 |
| if (!name || !nlen || nlen >= SA_NAMELEN) { |
40967 |
1 |
40968 |
| if (!name || !nlen || nlen >= SA_NAMELEN) { |
1 |
40966 |
40967 |
|
| 308 |
2 |
▶ | if (err) *err = SA_E_NAME; |
Branch: 1 branch
| Branch | True | False | Total |
| if (err) *err = SA_E_NAME; |
2 |
0 |
2 |
|
| 309 |
2 |
| return NULL; |
| 310 |
|
| } |
| 311 |
|
| |
| 312 |
40966 |
| hash = sa_at_fnv(name, nlen); |
| 313 |
|
| /* The lock covers only the name check and the claim, so two processes |
| 314 |
|
| * carving DIFFERENT names contend on a stripe at worst. |
| 315 |
|
| * |
| 316 |
|
| * WAITS RATHER THAN SPINS. Carving happens once per region at startup, so |
| 317 |
|
| * a few microseconds of sleep costs nothing and a refusal costs a worker |
| 318 |
|
| * its region. See sa_lock_wait: a pure spin refused four carves in four |
| 319 |
|
| * thousand, every run, on a machine with fewer cores than carvers. */ |
| 320 |
40966 |
▶ | if (!sa_lock_wait(h->locks, hash)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (!sa_lock_wait(h->locks, hash)) { |
0 |
40966 |
40966 |
|
| 321 |
|
| /* SA_E_BUSY, not SA_E_FULL: nothing here is full. */ |
| 322 |
0 |
▶ | if (err) *err = SA_E_BUSY; |
Branch: 1 branch
| Branch | True | False | Total |
| if (err) *err = SA_E_BUSY; |
0 |
0 |
0 |
|
| 323 |
0 |
| return NULL; |
| 324 |
|
| } |
| 325 |
|
| |
| 326 |
40966 |
| e = sa_find(r, name, nlen); |
| 327 |
40966 |
▶ | if (e) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (e) { |
177 |
40789 |
40966 |
|
| 328 |
|
| /* SA_E_SHAPE, not SA_E_NAME. The name is fine - it is the type or the |
| 329 |
|
| * size that disagrees with what is already carved, and telling a caller |
| 330 |
|
| * its name is "too long or empty" when the name is neither sends it |
| 331 |
|
| * looking in the wrong place entirely. */ |
| 332 |
177 |
▶ | int bad = (e->type != type) || (len && e->len < len); |
Branch: 3 branches
| Branch | True | False | Total |
| int bad = (e->type != type) || (len && e->len < len); |
176 |
1 |
177 |
| int bad = (e->type != type) || (len && e->len < len); |
116 |
60 |
176 |
| int bad = (e->type != type) || (len && e->len < len); |
21 |
95 |
116 |
|
| 333 |
177 |
| sa_at_unlock(h->locks, hash); |
| 334 |
177 |
▶ | if (bad) { if (err) *err = SA_E_SHAPE; return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (bad) { if (err) *err = SA_E_SHAPE; return NULL; } |
22 |
155 |
177 |
| if (bad) { if (err) *err = SA_E_SHAPE; return NULL; } |
22 |
0 |
22 |
|
| 335 |
155 |
| return e; |
| 336 |
|
| } |
| 337 |
|
| |
| 338 |
|
| /* THE SLOT IS CLAIMED WITH ONE ATOMIC, NOT READ AND THEN WRITTEN. |
| 339 |
|
| * |
| 340 |
|
| * The stripe lock above is keyed on the NAME, so it serialises two carves |
| 341 |
|
| * of the same name and does nothing at all for two carves of different |
| 342 |
|
| * ones - and the registry append is a resource they share. Reading |
| 343 |
|
| * `reg_used` here and storing `idx + 1` twenty lines later left a window in |
| 344 |
|
| * which two processes took the same index, both filled it, and the loser's |
| 345 |
|
| * entry was gone with its arena space still spent. Both callers were told |
| 346 |
|
| * they had succeeded. |
| 347 |
|
| * |
| 348 |
|
| * Measured before it was fixed: eight processes carving 4000 names between |
| 349 |
|
| * them kept 3263 of them, with no refusal reported for the other 737. |
| 350 |
|
| * t/04-carve-race.t is that test. |
| 351 |
|
| * |
| 352 |
|
| * fetch-add cannot overshoot into somebody else's entry, so `reg_used` may |
| 353 |
|
| * pass `reg_max` when the registry is full and every reader already clamps |
| 354 |
|
| * it - `sa_find` and `sa_regions` both do. It is never decremented: undoing |
| 355 |
|
| * it would hand the same index to a caller that is still writing. */ |
| 356 |
40789 |
| idx = sa_at_fetch_add32(&h->reg_used, 1); |
| 357 |
40789 |
▶ | if (idx >= h->reg_max) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (idx >= h->reg_max) { |
10 |
40779 |
40789 |
|
| 358 |
10 |
| sa_at_unlock(h->locks, hash); |
| 359 |
10 |
▶ | if (err) *err = SA_E_FULL; |
Branch: 1 branch
| Branch | True | False | Total |
| if (err) *err = SA_E_FULL; |
10 |
0 |
10 |
|
| 360 |
10 |
| return NULL; |
| 361 |
|
| } |
| 362 |
|
| |
| 363 |
40779 |
| off = sa_bump(r, len); |
| 364 |
40779 |
▶ | if (!off) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (!off) { |
1 |
40778 |
40779 |
|
| 365 |
1 |
| sa_at_unlock(h->locks, hash); |
| 366 |
1 |
▶ | if (err) *err = SA_E_FULL; |
Branch: 1 branch
| Branch | True | False | Total |
| if (err) *err = SA_E_FULL; |
1 |
0 |
1 |
|
| 367 |
1 |
| return NULL; |
| 368 |
|
| } |
| 369 |
|
| |
| 370 |
40778 |
| regs = SA_REGS(r->map.base, h); |
| 371 |
40778 |
| e = ®s[idx]; |
| 372 |
40778 |
| memset(e->name, 0, SA_NAMELEN); |
| 373 |
40778 |
| memcpy(e->name, name, nlen); |
| 374 |
40778 |
| e->off = off; |
| 375 |
40778 |
| e->len = len; |
| 376 |
40778 |
| e->type = type; |
| 377 |
|
| /* `state` is published LAST with a release store: the count already moved |
| 378 |
|
| * when the index was claimed, so a concurrent reader scanning this far |
| 379 |
|
| * finds an entry that is still EMPTY rather than one that is half filled. |
| 380 |
|
| * A scan that sees nothing is a miss it will retry; a scan that reads a |
| 381 |
|
| * half-filled entry is a wrong answer it cannot detect. */ |
| 382 |
40778 |
| sa_at_store32_rel(&e->state, SA_R_LIVE); |
| 383 |
|
| |
| 384 |
40778 |
| sa_at_unlock(h->locks, hash); |
| 385 |
40778 |
| return e; |
| 386 |
|
| #endif |
| 387 |
|
| } |
| 388 |
|
| |
| 389 |
|
| /* An offset into this process's address space. The one place an offset becomes |
| 390 |
|
| * a pointer, and it is never stored anywhere shared. */ |
| 391 |
636 |
| static void *sa_ptr(sa_region *r, uint64_t off) { |
| 392 |
636 |
▶ | if (!r || !r->map.base || off >= r->total) return NULL; |
Branch: 3 branches
| Branch | True | False | Total |
| if (!r || !r->map.base || off >= r->total) return NULL; |
636 |
0 |
636 |
| if (!r || !r->map.base || off >= r->total) return NULL; |
636 |
0 |
636 |
| if (!r || !r->map.base || off >= r->total) return NULL; |
1 |
635 |
636 |
|
| 393 |
635 |
| return SA_AT(r->map.base, off); |
| 394 |
|
| } |
| 395 |
|
| |
| 396 |
|
| |
| 397 |
|
| /* ---- lifecycle -------------------------------------------------------------- */ |
| 398 |
|
| |
| 399 |
161 |
| static sa_region *sa_region_open(const char *name, size_t nlen, uint64_t len, |
| 400 |
|
| uint32_t reg_max, int may_create, int *err) |
| 401 |
|
| { |
| 402 |
|
| sa_region *r; |
| 403 |
|
| char nbuf[SA_NAMELEN + 8]; |
| 404 |
161 |
| const char *nm = NULL; |
| 405 |
161 |
| int rc, created = 0; |
| 406 |
|
| |
| 407 |
161 |
▶ | if (err) *err = SA_E_OK; |
Branch: 1 branch
| Branch | True | False | Total |
| if (err) *err = SA_E_OK; |
161 |
0 |
161 |
|
| 408 |
|
| |
| 409 |
161 |
▶ | if (name && nlen) { |
Branch: 2 branches
| Branch | True | False | Total |
| if (name && nlen) { |
12 |
149 |
161 |
| if (name && nlen) { |
12 |
0 |
12 |
|
| 410 |
|
| /* A POSIX shared name must start with a slash and contain no others, |
| 411 |
|
| * and macOS caps the whole thing at 31 characters including the NUL - |
| 412 |
|
| * shorter than PATH_MAX by a long way and the reason a name that works |
| 413 |
|
| * on Linux can fail there. Keep the caller's name inside SA_NAMELEN and |
| 414 |
|
| * the slash is ours to add. */ |
| 415 |
12 |
▶ | if (nlen >= SA_NAMELEN || memchr(name, '/', nlen)) { |
Branch: 2 branches
| Branch | True | False | Total |
| if (nlen >= SA_NAMELEN || memchr(name, '/', nlen)) { |
12 |
0 |
12 |
| if (nlen >= SA_NAMELEN || memchr(name, '/', nlen)) { |
0 |
12 |
12 |
|
| 416 |
0 |
▶ | if (err) *err = SA_E_NAME; |
Branch: 1 branch
| Branch | True | False | Total |
| if (err) *err = SA_E_NAME; |
0 |
0 |
0 |
|
| 417 |
0 |
| return NULL; |
| 418 |
|
| } |
| 419 |
12 |
| nbuf[0] = '/'; |
| 420 |
12 |
| memcpy(nbuf + 1, name, nlen); |
| 421 |
12 |
| nbuf[nlen + 1] = '\0'; |
| 422 |
12 |
| nm = nbuf; |
| 423 |
|
| } |
| 424 |
|
| |
| 425 |
161 |
| r = (sa_region *)calloc(1, sizeof(sa_region)); |
| 426 |
161 |
▶ | if (!r) { if (err) *err = SA_E_NOMEM; return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (!r) { if (err) *err = SA_E_NOMEM; return NULL; } |
0 |
161 |
161 |
| if (!r) { if (err) *err = SA_E_NOMEM; return NULL; } |
0 |
0 |
0 |
|
| 427 |
161 |
| r->peer_idx = -1; |
| 428 |
161 |
| r->waker_idx = -1; |
| 429 |
|
| |
| 430 |
161 |
| rc = sa_map_open(&r->map, nm, len, reg_max, &created, may_create); |
| 431 |
161 |
▶ | if (rc != SA_E_OK) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (rc != SA_E_OK) { |
2 |
159 |
161 |
|
| 432 |
2 |
| free(r); |
| 433 |
2 |
▶ | if (err) *err = rc; |
Branch: 1 branch
| Branch | True | False | Total |
| if (err) *err = rc; |
2 |
0 |
2 |
|
| 434 |
2 |
| return NULL; |
| 435 |
|
| } |
| 436 |
|
| |
| 437 |
159 |
| r->hdr = (sa_header *)r->map.base; |
| 438 |
159 |
| r->total = r->hdr->total; |
| 439 |
159 |
| r->created = created; |
| 440 |
159 |
| return r; |
| 441 |
|
| } |
| 442 |
|
| |
| 443 |
159 |
| static void sa_region_release(sa_region *r) { |
| 444 |
159 |
▶ | if (!r) return; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!r) return; |
0 |
159 |
159 |
|
| 445 |
159 |
| sa_map_release(&r->map); |
| 446 |
159 |
| free(r); |
| 447 |
|
| } |
| 448 |
|
| |
| 449 |
8 |
| static int sa_region_destroy(const char *name, size_t nlen) { |
| 450 |
|
| char nbuf[SA_NAMELEN + 8]; |
| 451 |
8 |
▶ | if (!name || !nlen || nlen >= SA_NAMELEN || memchr(name, '/', nlen)) |
Branch: 4 branches
| Branch | True | False | Total |
| if (!name || !nlen || nlen >= SA_NAMELEN || memchr(name, '/', nlen)) |
8 |
0 |
8 |
| if (!name || !nlen || nlen >= SA_NAMELEN || memchr(name, '/', nlen)) |
8 |
0 |
8 |
| if (!name || !nlen || nlen >= SA_NAMELEN || memchr(name, '/', nlen)) |
8 |
0 |
8 |
| if (!name || !nlen || nlen >= SA_NAMELEN || memchr(name, '/', nlen)) |
0 |
8 |
8 |
|
| 452 |
0 |
| return SA_E_NAME; |
| 453 |
8 |
| nbuf[0] = '/'; |
| 454 |
8 |
| memcpy(nbuf + 1, name, nlen); |
| 455 |
8 |
| nbuf[nlen + 1] = '\0'; |
| 456 |
8 |
| return sa_os_destroy(nbuf); |
| 457 |
|
| } |
| 458 |
|
| |
| 459 |
|
| #endif /* SA_ARENA_H */ |