| 1 |
|
| /* |
| 2 |
|
| * stack.h -- Fixed-size shared-memory LIFO stack for Linux |
| 3 |
|
| * |
| 4 |
|
| * CAS-based position handout (top) with per-slot publication state |
| 5 |
|
| * machine (EMPTY -> WRITING -> FILLED -> READING -> EMPTY, generation |
| 6 |
|
| * bumped on release). The state machine closes the race between a |
| 7 |
|
| * position CAS and the corresponding slot write/read under MPMC. |
| 8 |
|
| * Futex blocking via push/pop_wake_seq when empty (pop) or full (push). |
| 9 |
|
| * |
| 10 |
|
| * Variants: Int (int64_t), Str (length-prefixed) |
| 11 |
|
| */ |
| 12 |
|
| |
| 13 |
|
| #ifndef STACK_H |
| 14 |
|
| #define STACK_H |
| 15 |
|
| |
| 16 |
|
| #include <stddef.h> |
| 17 |
|
| #include <stdint.h> |
| 18 |
|
| #include <stdbool.h> |
| 19 |
|
| #include <stdlib.h> |
| 20 |
|
| #include <string.h> |
| 21 |
|
| #include <unistd.h> |
| 22 |
|
| #include <fcntl.h> |
| 23 |
|
| #include <errno.h> |
| 24 |
|
| #include <time.h> |
| 25 |
|
| #include <limits.h> |
| 26 |
|
| #include <signal.h> |
| 27 |
|
| #include <sys/mman.h> |
| 28 |
|
| #include <sys/stat.h> |
| 29 |
|
| #include <sys/file.h> |
| 30 |
|
| #include <sys/syscall.h> |
| 31 |
|
| #include <linux/futex.h> |
| 32 |
|
| #include <sys/eventfd.h> |
| 33 |
|
| |
| 34 |
|
| #define STK_MAGIC 0x53544B32U /* "STK2" -- v2 layout (per-slot ctl) */ |
| 35 |
|
| #define STK_VERSION 2 |
| 36 |
|
| #define STK_ERR_BUFLEN (PATH_MAX + 256) |
| 37 |
|
| |
| 38 |
|
| #ifndef STK_WAIT_INTERRUPTED |
| 39 |
|
| #define STK_WAIT_INTERRUPTED() 0 |
| 40 |
|
| #endif |
| 41 |
|
| |
| 42 |
|
| #define STK_VAR_INT 0 |
| 43 |
|
| #define STK_VAR_STR 1 |
| 44 |
|
| |
| 45 |
|
| /* Slot state (low 2 bits of ctl word). Upper 62 bits = generation. */ |
| 46 |
|
| #define STK_SLOT_EMPTY 0u |
| 47 |
|
| #define STK_SLOT_WRITING 1u |
| 48 |
|
| #define STK_SLOT_FILLED 2u |
| 49 |
|
| #define STK_SLOT_READING 3u |
| 50 |
|
| #define STK_SLOT_STATE_MASK 3u |
| 51 |
|
| #define STK_SLOT_STATE(c) ((uint32_t)((c) & STK_SLOT_STATE_MASK)) |
| 52 |
|
| #define STK_SLOT_GEN(c) ((c) >> 2) |
| 53 |
|
| |
| 54 |
|
| /* ================================================================ |
| 55 |
|
| * Header (128 bytes) |
| 56 |
|
| * ================================================================ */ |
| 57 |
|
| |
| 58 |
|
| typedef struct { |
| 59 |
|
| uint32_t magic; |
| 60 |
|
| uint32_t version; |
| 61 |
|
| uint32_t elem_size; |
| 62 |
|
| uint32_t variant_id; |
| 63 |
|
| uint64_t capacity; |
| 64 |
|
| uint64_t total_size; |
| 65 |
|
| uint64_t data_off; |
| 66 |
|
| uint64_t ctl_off; /* offset to per-slot ctl array */ |
| 67 |
|
| uint8_t _pad0[16]; |
| 68 |
|
| |
| 69 |
|
| uint32_t top; /* 64: next free index (0=empty, capacity=full) */ |
| 70 |
|
| uint32_t waiters_push; /* 68 */ |
| 71 |
|
| uint32_t waiters_pop; /* 72 */ |
| 72 |
|
| uint32_t push_wake_seq; /* 76: bumped by every pop, futex word for pushers */ |
| 73 |
|
| uint32_t pop_wake_seq; /* 80: bumped by every push, futex word for poppers */ |
| 74 |
|
| uint32_t _pad1; /* 84 */ |
| 75 |
|
| uint64_t stat_pushes; /* 88 */ |
| 76 |
|
| uint64_t stat_pops; /* 96 */ |
| 77 |
|
| uint64_t stat_waits; /* 104 */ |
| 78 |
|
| uint64_t stat_timeouts; /* 112 */ |
| 79 |
|
| uint8_t _pad2[8]; /* 120-127 */ |
| 80 |
|
| } StkHeader; |
| 81 |
|
| |
| 82 |
|
| #if defined(__STDC_VERSION__) && __STDC_VERSION__ >= 201112L |
| 83 |
|
| _Static_assert(sizeof(StkHeader) == 128, "StkHeader must be 128 bytes"); |
| 84 |
|
| #endif |
| 85 |
|
| |
| 86 |
|
| typedef struct { |
| 87 |
|
| StkHeader *hdr; |
| 88 |
|
| uint8_t *data; |
| 89 |
|
| uint64_t *ctl; /* per-slot state+generation word */ |
| 90 |
|
| size_t mmap_size; |
| 91 |
|
| uint32_t elem_size; /* cached from header at open time */ |
| 92 |
|
| uint64_t capacity; /* cached from header at open time -- trusted bound */ |
| 93 |
|
| char *path; |
| 94 |
|
| int notify_fd; |
| 95 |
|
| int backing_fd; |
| 96 |
|
| } StkHandle; |
| 97 |
|
| |
| 98 |
|
| /* ================================================================ |
| 99 |
|
| * Utility |
| 100 |
|
| * ================================================================ */ |
| 101 |
|
| |
| 102 |
6 |
| static inline void stk_make_deadline(double timeout, struct timespec *dl) { |
| 103 |
6 |
| clock_gettime(CLOCK_MONOTONIC, dl); |
| 104 |
6 |
▶ | if (!(timeout < 1e9)) timeout = 1e9; /* clamp Inf/NaN/huge: avoid UB (time_t) cast -> instant spurious timeout */ |
Branch: 1 branch
| Branch | True | False | Total |
| if (!(timeout < 1e9)) timeout = 1e9; /* clamp Inf/NaN/huge: avoid UB (time_t) cast -> instant spurious timeout */ |
0 |
6 |
6 |
|
| 105 |
6 |
| dl->tv_sec += (time_t)timeout; |
| 106 |
6 |
| dl->tv_nsec += (long)((timeout - (double)(time_t)timeout) * 1e9); |
| 107 |
6 |
▶ | if (dl->tv_nsec >= 1000000000L) { dl->tv_sec++; dl->tv_nsec -= 1000000000L; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (dl->tv_nsec >= 1000000000L) { dl->tv_sec++; dl->tv_nsec -= 1000000000L; } |
2 |
4 |
6 |
|
| 108 |
6 |
| } |
| 109 |
|
| |
| 110 |
5 |
| static inline int stk_remaining(const struct timespec *dl, struct timespec *rem) { |
| 111 |
|
| struct timespec now; |
| 112 |
5 |
| clock_gettime(CLOCK_MONOTONIC, &now); |
| 113 |
5 |
| rem->tv_sec = dl->tv_sec - now.tv_sec; |
| 114 |
5 |
| rem->tv_nsec = dl->tv_nsec - now.tv_nsec; |
| 115 |
5 |
▶ | if (rem->tv_nsec < 0) { rem->tv_sec--; rem->tv_nsec += 1000000000L; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (rem->tv_nsec < 0) { rem->tv_sec--; rem->tv_nsec += 1000000000L; } |
4 |
1 |
5 |
|
| 116 |
5 |
| return rem->tv_sec >= 0; |
| 117 |
|
| } |
| 118 |
|
| |
| 119 |
3 |
| static inline void stk_futex_wait(uint32_t *word, uint32_t seq, struct timespec *timeout) { |
| 120 |
|
| #ifdef STK_WAIT_SLICE_NS |
| 121 |
|
| /* Poll deferred signals even if one arrived just before the syscall. */ |
| 122 |
3 |
| struct timespec slice = { 0, STK_WAIT_SLICE_NS }; |
| 123 |
3 |
▶ | if (!timeout || timeout->tv_sec > 0 || timeout->tv_nsec > slice.tv_nsec) |
Branch: 3 branches
| Branch | True | False | Total |
| if (!timeout || timeout->tv_sec > 0 || timeout->tv_nsec > slice.tv_nsec) |
3 |
0 |
3 |
| if (!timeout || timeout->tv_sec > 0 || timeout->tv_nsec > slice.tv_nsec) |
2 |
1 |
3 |
| if (!timeout || timeout->tv_sec > 0 || timeout->tv_nsec > slice.tv_nsec) |
0 |
2 |
2 |
|
| 124 |
1 |
| timeout = &slice; |
| 125 |
|
| #endif |
| 126 |
3 |
| syscall(SYS_futex, word, FUTEX_WAIT, seq, timeout, NULL, 0); |
| 127 |
3 |
| } |
| 128 |
|
| |
| 129 |
36184 |
| static inline uint8_t *stk_slot(StkHandle *h, uint32_t idx) { |
| 130 |
36184 |
| return h->data + (uint64_t)idx * h->elem_size; |
| 131 |
|
| } |
| 132 |
|
| |
| 133 |
0 |
| static inline void stk_spin_pause(void) { |
| 134 |
|
| #if defined(__x86_64__) || defined(__i386__) |
| 135 |
0 |
| __asm__ volatile("pause" ::: "memory"); |
| 136 |
|
| #elif defined(__aarch64__) |
| 137 |
|
| __asm__ volatile("yield" ::: "memory"); |
| 138 |
|
| #endif |
| 139 |
0 |
| } |
| 140 |
|
| |
| 141 |
|
| /* Slot state machine -- same pattern as Data::Deque::Shared. |
| 142 |
|
| * |
| 143 |
|
| * Bounded wait for `want`, with abandoned-slot recovery. |
| 144 |
|
| * |
| 145 |
|
| * A peer that died between claiming a slot and publishing/releasing it leaves |
| 146 |
|
| * the slot stuck in WRITING (crashed pusher) or READING (crashed popper). An |
| 147 |
|
| * unbounded spin here wedges EVERY process using the stack, forever, at 100% |
| 148 |
|
| * CPU -- stk_drain already bounds its own wait for exactly this reason (see the |
| 149 |
|
| * comment there); push/pop must do the same or a single SIGKILL is a permanent |
| 150 |
|
| * cluster-wide DoS. We hot-spin briefly, then sleep, and on a ~2s deadline force |
| 151 |
|
| * the slot back to EMPTY with the generation bumped. |
| 152 |
|
| * |
| 153 |
|
| * Returns 1 with *out_gen set when the slot was claimed in state `want`. |
| 154 |
|
| * Returns 0 when the slot was abandoned and force-reclaimed. |
| 155 |
|
| * |
| 156 |
|
| * Same false-positive caveat as stk_drain: ctl encodes no PID, so a live peer |
| 157 |
|
| * stalled >2s is indistinguishable from a dead one. Its later publish/release is |
| 158 |
|
| * a CAS against the old generation (stk_slot_publish), so it no-ops instead of |
| 159 |
|
| * resurrecting a phantom slot; the value is dropped exactly as for a real crash. |
| 160 |
|
| * The claim->publish window is a sub-microsecond memcpy, so the threshold is |
| 161 |
|
| * many orders of magnitude above normal latency. */ |
| 162 |
36159 |
| static inline int stk_slot_wait_state(uint64_t *ctl_word, uint32_t want, |
| 163 |
|
| uint64_t *out_gen) { |
| 164 |
|
| struct timespec dl; |
| 165 |
36159 |
| int dl_set = 0; |
| 166 |
36159 |
| uint32_t spins = 0; |
| 167 |
0 |
| for (;;) { |
| 168 |
36159 |
| uint64_t c = __atomic_load_n(ctl_word, __ATOMIC_ACQUIRE); |
| 169 |
36159 |
▶ | if (STK_SLOT_STATE(c) == want) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (STK_SLOT_STATE(c) == want) { |
36159 |
0 |
36159 |
|
| 170 |
36159 |
▶ | uint32_t next = (want == STK_SLOT_EMPTY) ? STK_SLOT_WRITING : STK_SLOT_READING; |
Branch: 1 branch
| Branch | True | False | Total |
| uint32_t next = (want == STK_SLOT_EMPTY) ? STK_SLOT_WRITING : STK_SLOT_READING; |
92 |
36067 |
36159 |
|
| 171 |
36159 |
| uint64_t nc = (STK_SLOT_GEN(c) << 2) | next; |
| 172 |
36159 |
▶ | if (__atomic_compare_exchange_n(ctl_word, &c, nc, |
Branch: 1 branch
| Branch | True | False | Total |
| if (__atomic_compare_exchange_n(ctl_word, &c, nc, |
36159 |
0 |
36159 |
|
| 173 |
|
| 0, __ATOMIC_ACQUIRE, __ATOMIC_RELAXED)) { |
| 174 |
36159 |
| *out_gen = STK_SLOT_GEN(c); |
| 175 |
36159 |
| return 1; |
| 176 |
|
| } |
| 177 |
0 |
| continue; |
| 178 |
|
| } |
| 179 |
0 |
| stk_spin_pause(); |
| 180 |
0 |
▶ | if ((++spins & 0x3F) == 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| if ((++spins & 0x3F) == 0) { |
0 |
0 |
0 |
|
| 181 |
0 |
▶ | if (!dl_set) { stk_make_deadline(2.0, &dl); dl_set = 1; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (!dl_set) { stk_make_deadline(2.0, &dl); dl_set = 1; } |
0 |
0 |
0 |
|
| 182 |
|
| struct timespec rem; |
| 183 |
0 |
▶ | if (!stk_remaining(&dl, &rem)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (!stk_remaining(&dl, &rem)) { |
0 |
0 |
0 |
|
| 184 |
|
| /* Abandoned by a dead peer: force EMPTY with gen bumped. If the |
| 185 |
|
| * CAS loses, the peer just completed (or another recoverer won) |
| 186 |
|
| * -- re-observe rather than clobber. */ |
| 187 |
0 |
| uint64_t nc = ((STK_SLOT_GEN(c) + 1) << 2) | STK_SLOT_EMPTY; |
| 188 |
0 |
▶ | if (__atomic_compare_exchange_n(ctl_word, &c, nc, |
Branch: 1 branch
| Branch | True | False | Total |
| if (__atomic_compare_exchange_n(ctl_word, &c, nc, |
0 |
0 |
0 |
|
| 189 |
|
| 0, __ATOMIC_ACQ_REL, __ATOMIC_RELAXED)) |
| 190 |
0 |
| return 0; |
| 191 |
0 |
| continue; |
| 192 |
|
| } |
| 193 |
|
| /* Short sleep to keep CPU usage low during the long wait. */ |
| 194 |
0 |
| struct timespec ts = { 0, 100000L }; /* 100us */ |
| 195 |
0 |
| nanosleep(&ts, NULL); |
| 196 |
|
| } |
| 197 |
|
| } |
| 198 |
|
| } |
| 199 |
|
| |
| 200 |
92 |
| static inline uint64_t stk_slot_claim_write(uint64_t *ctl_word) { |
| 201 |
|
| uint64_t gen; |
| 202 |
|
| /* On recovery the slot is EMPTY at the bumped gen: retry and take it. */ |
| 203 |
92 |
▶ | while (!stk_slot_wait_state(ctl_word, STK_SLOT_EMPTY, &gen)) { } |
Branch: 1 branch
| Branch | True | False | Total |
| while (!stk_slot_wait_state(ctl_word, STK_SLOT_EMPTY, &gen)) { } |
0 |
92 |
92 |
|
| 204 |
92 |
| return gen; |
| 205 |
|
| } |
| 206 |
|
| |
| 207 |
|
| /* Publish WRITING@gen -> FILLED@gen. Implemented as CAS (not a plain store) |
| 208 |
|
| * so that if stk_drain force-recovered the slot mid-write -- bumping it to |
| 209 |
|
| * EMPTY@(gen+1) -- this publish is a no-op rather than clobbering the |
| 210 |
|
| * recovered state back to FILLED@gen. That would leave a phantom FILLED at |
| 211 |
|
| * a stale gen which the next pusher's stk_slot_claim_write (waits on EMPTY) |
| 212 |
|
| * could never advance past, deadlocking that slot forever. The caller's |
| 213 |
|
| * top CAS was already committed, so on lost-race the value is silently |
| 214 |
|
| * dropped -- matching the documented drain-recovery semantics. */ |
| 215 |
92 |
| static inline void stk_slot_publish(uint64_t *ctl_word, uint64_t gen) { |
| 216 |
92 |
| uint64_t expected = (gen << 2) | STK_SLOT_WRITING; |
| 217 |
92 |
| uint64_t desired = (gen << 2) | STK_SLOT_FILLED; |
| 218 |
92 |
| (void)__atomic_compare_exchange_n(ctl_word, &expected, desired, |
| 219 |
|
| 0, __ATOMIC_RELEASE, __ATOMIC_RELAXED); |
| 220 |
92 |
| } |
| 221 |
|
| |
| 222 |
|
| /* Returns 1 and sets *out_gen on success; 0 if the slot was abandoned by a |
| 223 |
|
| * crashed pusher and has been force-reclaimed (no value to read). */ |
| 224 |
36067 |
| static inline int stk_slot_claim_read(uint64_t *ctl_word, uint64_t *out_gen) { |
| 225 |
36067 |
| return stk_slot_wait_state(ctl_word, STK_SLOT_FILLED, out_gen); |
| 226 |
|
| } |
| 227 |
|
| |
| 228 |
36072 |
| static inline void stk_slot_release(uint64_t *ctl_word, uint64_t gen) { |
| 229 |
36072 |
| __atomic_store_n(ctl_word, ((gen + 1) << 2) | STK_SLOT_EMPTY, __ATOMIC_RELEASE); |
| 230 |
36072 |
| } |
| 231 |
|
| |
| 232 |
|
| /* ================================================================ |
| 233 |
|
| * Push (LIFO top++) |
| 234 |
|
| * ================================================================ */ |
| 235 |
|
| |
| 236 |
96 |
| static inline int stk_try_push(StkHandle *h, const void *val, uint32_t vlen) { |
| 237 |
96 |
| StkHeader *hdr = h->hdr; |
| 238 |
96 |
| uint32_t cap = (uint32_t)h->capacity; /* trusted cached bound, not live mmap */ |
| 239 |
0 |
| for (;;) { |
| 240 |
96 |
| uint32_t t = __atomic_load_n(&hdr->top, __ATOMIC_RELAXED); |
| 241 |
188 |
▶ | if (t >= cap) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (t >= cap) return 0; |
4 |
92 |
96 |
|
| 242 |
92 |
▶ | if (__atomic_compare_exchange_n(&hdr->top, &t, t + 1, |
Branch: 1 branch
| Branch | True | False | Total |
| if (__atomic_compare_exchange_n(&hdr->top, &t, t + 1, |
92 |
0 |
92 |
|
| 243 |
|
| 1, __ATOMIC_ACQ_REL, __ATOMIC_RELAXED)) { |
| 244 |
92 |
| uint32_t sz = h->elem_size; |
| 245 |
92 |
| uint32_t cp = vlen < sz ? vlen : sz; |
| 246 |
92 |
| uint64_t gen = stk_slot_claim_write(&h->ctl[t]); |
| 247 |
92 |
| memcpy(stk_slot(h, t), val, cp); |
| 248 |
92 |
▶ | if (cp < sz) memset(stk_slot(h, t) + cp, 0, sz - cp); |
Branch: 1 branch
| Branch | True | False | Total |
| if (cp < sz) memset(stk_slot(h, t) + cp, 0, sz - cp); |
0 |
92 |
92 |
|
| 249 |
92 |
| stk_slot_publish(&h->ctl[t], gen); |
| 250 |
92 |
| __atomic_add_fetch(&hdr->stat_pushes, 1, __ATOMIC_RELAXED); |
| 251 |
|
| /* StoreLoad barrier: publish top++ before reading waiters_pop, so |
| 252 |
|
| * we observe a popper that registered just before this push. */ |
| 253 |
92 |
| __atomic_thread_fence(__ATOMIC_SEQ_CST); |
| 254 |
92 |
▶ | if (__atomic_load_n(&hdr->waiters_pop, __ATOMIC_RELAXED) > 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (__atomic_load_n(&hdr->waiters_pop, __ATOMIC_RELAXED) > 0) { |
0 |
92 |
92 |
|
| 255 |
0 |
| __atomic_add_fetch(&hdr->pop_wake_seq, 1, __ATOMIC_RELEASE); |
| 256 |
0 |
| syscall(SYS_futex, &hdr->pop_wake_seq, FUTEX_WAKE, 1, NULL, NULL, 0); |
| 257 |
|
| } |
| 258 |
92 |
| return 1; |
| 259 |
|
| } |
| 260 |
|
| } |
| 261 |
|
| } |
| 262 |
|
| |
| 263 |
14 |
| static inline int stk_push(StkHandle *h, const void *val, uint32_t vlen, double timeout) { |
| 264 |
14 |
▶ | if (stk_try_push(h, val, vlen)) return 1; |
Branch: 1 branch
| Branch | True | False | Total |
| if (stk_try_push(h, val, vlen)) return 1; |
13 |
1 |
14 |
|
| 265 |
1 |
▶ | if (timeout == 0) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (timeout == 0) return 0; |
0 |
1 |
1 |
|
| 266 |
|
| |
| 267 |
1 |
| StkHeader *hdr = h->hdr; |
| 268 |
1 |
| uint32_t cap = (uint32_t)h->capacity; /* trusted cached bound, not live mmap */ |
| 269 |
|
| struct timespec dl, rem; |
| 270 |
1 |
| int has_dl = (timeout > 0); |
| 271 |
1 |
▶ | if (has_dl) stk_make_deadline(timeout, &dl); |
Branch: 1 branch
| Branch | True | False | Total |
| if (has_dl) stk_make_deadline(timeout, &dl); |
1 |
0 |
1 |
|
| 272 |
1 |
| __atomic_add_fetch(&hdr->stat_waits, 1, __ATOMIC_RELAXED); |
| 273 |
|
| |
| 274 |
0 |
| for (;;) { |
| 275 |
1 |
▶ | if (STK_WAIT_INTERRUPTED()) { errno = EINTR; return -1; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (STK_WAIT_INTERRUPTED()) { errno = EINTR; return -1; } |
0 |
1 |
1 |
|
| 276 |
1 |
| uint32_t wseq = __atomic_load_n(&hdr->push_wake_seq, __ATOMIC_ACQUIRE); |
| 277 |
1 |
| __atomic_add_fetch(&hdr->waiters_push, 1, __ATOMIC_RELEASE); |
| 278 |
|
| /* StoreLoad barrier: publish waiters_push++ before re-reading `top`, |
| 279 |
|
| * so a concurrent popper sees our registration (and wakes us) or we |
| 280 |
|
| * see its top-- (and don't sleep). Release/acquire lets these reorder |
| 281 |
|
| * on weak memory -> lost wakeup -> hang. */ |
| 282 |
1 |
| __atomic_thread_fence(__ATOMIC_SEQ_CST); |
| 283 |
1 |
| uint32_t t = __atomic_load_n(&hdr->top, __ATOMIC_ACQUIRE); |
| 284 |
1 |
▶ | if (t >= cap) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (t >= cap) { |
1 |
0 |
1 |
|
| 285 |
1 |
| struct timespec *pts = NULL; |
| 286 |
1 |
▶ | if (has_dl) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (has_dl) { |
1 |
0 |
1 |
|
| 287 |
1 |
▶ | if (!stk_remaining(&dl, &rem)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (!stk_remaining(&dl, &rem)) { |
0 |
1 |
1 |
|
| 288 |
0 |
| __atomic_sub_fetch(&hdr->waiters_push, 1, __ATOMIC_RELAXED); |
| 289 |
0 |
| __atomic_add_fetch(&hdr->stat_timeouts, 1, __ATOMIC_RELAXED); |
| 290 |
0 |
| return 0; |
| 291 |
|
| } |
| 292 |
1 |
| pts = &rem; |
| 293 |
|
| } |
| 294 |
1 |
| stk_futex_wait(&hdr->push_wake_seq, wseq, pts); |
| 295 |
|
| } |
| 296 |
1 |
| __atomic_sub_fetch(&hdr->waiters_push, 1, __ATOMIC_RELAXED); |
| 297 |
1 |
▶ | if (STK_WAIT_INTERRUPTED()) { errno = EINTR; return -1; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (STK_WAIT_INTERRUPTED()) { errno = EINTR; return -1; } |
0 |
1 |
1 |
|
| 298 |
1 |
▶ | if (stk_try_push(h, val, vlen)) return 1; |
Branch: 1 branch
| Branch | True | False | Total |
| if (stk_try_push(h, val, vlen)) return 1; |
0 |
1 |
1 |
|
| 299 |
1 |
▶ | if (has_dl && !stk_remaining(&dl, &rem)) { |
Branch: 2 branches
| Branch | True | False | Total |
| if (has_dl && !stk_remaining(&dl, &rem)) { |
1 |
0 |
1 |
| if (has_dl && !stk_remaining(&dl, &rem)) { |
1 |
0 |
1 |
|
| 300 |
1 |
| __atomic_add_fetch(&hdr->stat_timeouts, 1, __ATOMIC_RELAXED); |
| 301 |
1 |
| return 0; |
| 302 |
|
| } |
| 303 |
|
| } |
| 304 |
|
| } |
| 305 |
|
| |
| 306 |
|
| /* ================================================================ |
| 307 |
|
| * Pop (LIFO top--) |
| 308 |
|
| * ================================================================ */ |
| 309 |
|
| |
| 310 |
|
| /* Wake one blocked pusher, if any. Must run after EVERY committed top--, |
| 311 |
|
| * whether the pop produced a value or reclaimed an abandoned slot: either |
| 312 |
|
| * way a slot's worth of room was freed, and pushers parked in stk_push()'s |
| 313 |
|
| * FUTEX_WAIT have no other waker on this path (only a successful pop, |
| 314 |
|
| * drain(), or clear() bumps push_wake_seq). The StoreLoad barrier pairs |
| 315 |
|
| * with the one in the push-wait loop: publish top-- before reading |
| 316 |
|
| * waiters_push. */ |
| 317 |
36067 |
| static inline void stk_wake_pushers(StkHeader *hdr) { |
| 318 |
36067 |
| __atomic_thread_fence(__ATOMIC_SEQ_CST); |
| 319 |
36067 |
▶ | if (__atomic_load_n(&hdr->waiters_push, __ATOMIC_RELAXED) > 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (__atomic_load_n(&hdr->waiters_push, __ATOMIC_RELAXED) > 0) { |
0 |
36067 |
36067 |
|
| 320 |
0 |
| __atomic_add_fetch(&hdr->push_wake_seq, 1, __ATOMIC_RELEASE); |
| 321 |
0 |
| syscall(SYS_futex, &hdr->push_wake_seq, FUTEX_WAKE, 1, NULL, NULL, 0); |
| 322 |
|
| } |
| 323 |
36067 |
| } |
| 324 |
|
| |
| 325 |
36076 |
| static inline int stk_try_pop(StkHandle *h, void *out) { |
| 326 |
36076 |
| StkHeader *hdr = h->hdr; |
| 327 |
0 |
| for (;;) { |
| 328 |
36076 |
| uint32_t t = __atomic_load_n(&hdr->top, __ATOMIC_ACQUIRE); |
| 329 |
72143 |
▶ | if (t == 0) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (t == 0) return 0; |
9 |
36067 |
36076 |
|
| 330 |
36067 |
▶ | if (t > h->capacity) return 0; /* corrupted top: reject rather than OOB h->ctl[t-1]/slot */ |
Branch: 1 branch
| Branch | True | False | Total |
| if (t > h->capacity) return 0; /* corrupted top: reject rather than OOB h->ctl[t-1]/slot */ |
0 |
36067 |
36067 |
|
| 331 |
36067 |
▶ | if (__atomic_compare_exchange_n(&hdr->top, &t, t - 1, |
Branch: 1 branch
| Branch | True | False | Total |
| if (__atomic_compare_exchange_n(&hdr->top, &t, t - 1, |
36067 |
0 |
36067 |
|
| 332 |
|
| 1, __ATOMIC_ACQ_REL, __ATOMIC_RELAXED)) { |
| 333 |
|
| uint64_t gen; |
| 334 |
36067 |
▶ | if (!stk_slot_claim_read(&h->ctl[t - 1], &gen)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (!stk_slot_claim_read(&h->ctl[t - 1], &gen)) { |
0 |
36067 |
36067 |
|
| 335 |
|
| /* Slot was abandoned by a crashed pusher and has been |
| 336 |
|
| * reclaimed: that value never existed. top is already |
| 337 |
|
| * decremented, so retry at the next position down rather than |
| 338 |
|
| * reporting the stack empty while entries remain below. The |
| 339 |
|
| * loop terminates because every iteration lowers top. The |
| 340 |
|
| * committed top-- freed room, so wake a blocked pusher just |
| 341 |
|
| * as a successful pop would -- otherwise a push_wait() that |
| 342 |
|
| * parked while the stack read full sleeps forever now that |
| 343 |
|
| * no successful pop can ever follow on an empty stack. */ |
| 344 |
0 |
| stk_wake_pushers(hdr); |
| 345 |
0 |
| continue; |
| 346 |
|
| } |
| 347 |
36067 |
| memcpy(out, stk_slot(h, t - 1), h->elem_size); |
| 348 |
36067 |
| stk_slot_release(&h->ctl[t - 1], gen); |
| 349 |
36067 |
| __atomic_add_fetch(&hdr->stat_pops, 1, __ATOMIC_RELAXED); |
| 350 |
36067 |
| stk_wake_pushers(hdr); |
| 351 |
36067 |
| return 1; |
| 352 |
|
| } |
| 353 |
|
| } |
| 354 |
|
| } |
| 355 |
|
| |
| 356 |
24 |
| static inline int stk_pop(StkHandle *h, void *out, double timeout) { |
| 357 |
24 |
▶ | if (stk_try_pop(h, out)) return 1; |
Branch: 1 branch
| Branch | True | False | Total |
| if (stk_try_pop(h, out)) return 1; |
22 |
2 |
24 |
|
| 358 |
2 |
▶ | if (timeout == 0) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (timeout == 0) return 0; |
0 |
2 |
2 |
|
| 359 |
|
| |
| 360 |
2 |
| StkHeader *hdr = h->hdr; |
| 361 |
|
| struct timespec dl, rem; |
| 362 |
2 |
| int has_dl = (timeout > 0); |
| 363 |
2 |
▶ | if (has_dl) stk_make_deadline(timeout, &dl); |
Branch: 1 branch
| Branch | True | False | Total |
| if (has_dl) stk_make_deadline(timeout, &dl); |
2 |
0 |
2 |
|
| 364 |
2 |
| __atomic_add_fetch(&hdr->stat_waits, 1, __ATOMIC_RELAXED); |
| 365 |
|
| |
| 366 |
0 |
| for (;;) { |
| 367 |
2 |
▶ | if (STK_WAIT_INTERRUPTED()) { errno = EINTR; return -1; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (STK_WAIT_INTERRUPTED()) { errno = EINTR; return -1; } |
0 |
2 |
2 |
|
| 368 |
2 |
| uint32_t wseq = __atomic_load_n(&hdr->pop_wake_seq, __ATOMIC_ACQUIRE); |
| 369 |
2 |
| __atomic_add_fetch(&hdr->waiters_pop, 1, __ATOMIC_RELEASE); |
| 370 |
|
| /* StoreLoad barrier: see the push-wait path (pairs with a pusher). */ |
| 371 |
2 |
| __atomic_thread_fence(__ATOMIC_SEQ_CST); |
| 372 |
2 |
| uint32_t t = __atomic_load_n(&hdr->top, __ATOMIC_ACQUIRE); |
| 373 |
2 |
▶ | if (t == 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (t == 0) { |
2 |
0 |
2 |
|
| 374 |
2 |
| struct timespec *pts = NULL; |
| 375 |
2 |
▶ | if (has_dl) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (has_dl) { |
2 |
0 |
2 |
|
| 376 |
2 |
▶ | if (!stk_remaining(&dl, &rem)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (!stk_remaining(&dl, &rem)) { |
0 |
2 |
2 |
|
| 377 |
0 |
| __atomic_sub_fetch(&hdr->waiters_pop, 1, __ATOMIC_RELAXED); |
| 378 |
0 |
| __atomic_add_fetch(&hdr->stat_timeouts, 1, __ATOMIC_RELAXED); |
| 379 |
0 |
| return 0; |
| 380 |
|
| } |
| 381 |
2 |
| pts = &rem; |
| 382 |
|
| } |
| 383 |
2 |
| stk_futex_wait(&hdr->pop_wake_seq, wseq, pts); |
| 384 |
|
| } |
| 385 |
2 |
| __atomic_sub_fetch(&hdr->waiters_pop, 1, __ATOMIC_RELAXED); |
| 386 |
2 |
▶ | if (STK_WAIT_INTERRUPTED()) { errno = EINTR; return -1; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (STK_WAIT_INTERRUPTED()) { errno = EINTR; return -1; } |
0 |
2 |
2 |
|
| 387 |
2 |
▶ | if (stk_try_pop(h, out)) return 1; |
Branch: 1 branch
| Branch | True | False | Total |
| if (stk_try_pop(h, out)) return 1; |
1 |
1 |
2 |
|
| 388 |
1 |
▶ | if (has_dl && !stk_remaining(&dl, &rem)) { |
Branch: 2 branches
| Branch | True | False | Total |
| if (has_dl && !stk_remaining(&dl, &rem)) { |
1 |
0 |
1 |
| if (has_dl && !stk_remaining(&dl, &rem)) { |
1 |
0 |
1 |
|
| 389 |
1 |
| __atomic_add_fetch(&hdr->stat_timeouts, 1, __ATOMIC_RELAXED); |
| 390 |
1 |
| return 0; |
| 391 |
|
| } |
| 392 |
|
| } |
| 393 |
|
| } |
| 394 |
|
| |
| 395 |
|
| /* ================================================================ |
| 396 |
|
| * Peek / Status |
| 397 |
|
| * ================================================================ */ |
| 398 |
|
| |
| 399 |
|
| /* Best-effort peek: seqlock-style retry against slot ctl. Returns 0 if |
| 400 |
|
| * empty OR if the top is mutating concurrently after the retry budget. |
| 401 |
|
| * Under no contention this is a single load. */ |
| 402 |
25 |
| static inline int stk_peek(StkHandle *h, void *out) { |
| 403 |
25 |
▶ | for (int tries = 0; tries < 64; tries++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (int tries = 0; tries < 64; tries++) { |
25 |
0 |
25 |
|
| 404 |
25 |
| uint32_t t = __atomic_load_n(&h->hdr->top, __ATOMIC_ACQUIRE); |
| 405 |
25 |
▶ | if (t == 0) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (t == 0) return 0; |
0 |
25 |
25 |
|
| 406 |
25 |
▶ | if (t > h->capacity) return 0; /* corrupted top: reject rather than OOB h->ctl[t-1]/slot */ |
Branch: 1 branch
| Branch | True | False | Total |
| if (t > h->capacity) return 0; /* corrupted top: reject rather than OOB h->ctl[t-1]/slot */ |
0 |
25 |
25 |
|
| 407 |
25 |
| uint64_t c1 = __atomic_load_n(&h->ctl[t - 1], __ATOMIC_ACQUIRE); |
| 408 |
25 |
▶ | if (STK_SLOT_STATE(c1) != STK_SLOT_FILLED) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (STK_SLOT_STATE(c1) != STK_SLOT_FILLED) { |
0 |
25 |
25 |
|
| 409 |
0 |
| stk_spin_pause(); |
| 410 |
0 |
| continue; |
| 411 |
|
| } |
| 412 |
25 |
| memcpy(out, stk_slot(h, t - 1), h->elem_size); |
| 413 |
|
| /* Order payload reads before the final state check on weak memory. */ |
| 414 |
25 |
| __atomic_thread_fence(__ATOMIC_ACQUIRE); |
| 415 |
25 |
| uint64_t c2 = __atomic_load_n(&h->ctl[t - 1], __ATOMIC_ACQUIRE); |
| 416 |
25 |
| uint32_t t2 = __atomic_load_n(&h->hdr->top, __ATOMIC_ACQUIRE); |
| 417 |
25 |
▶ | if (c1 == c2 && t == t2) return 1; |
Branch: 2 branches
| Branch | True | False | Total |
| if (c1 == c2 && t == t2) return 1; |
25 |
0 |
25 |
| if (c1 == c2 && t == t2) return 1; |
25 |
0 |
25 |
|
| 418 |
|
| } |
| 419 |
0 |
| return 0; |
| 420 |
|
| } |
| 421 |
|
| |
| 422 |
21 |
| static inline uint32_t stk_size(StkHandle *h) { |
| 423 |
21 |
| return __atomic_load_n(&h->hdr->top, __ATOMIC_RELAXED); |
| 424 |
|
| } |
| 425 |
|
| |
| 426 |
|
| /* ================================================================ |
| 427 |
|
| * Create / Open / Close |
| 428 |
|
| * ================================================================ */ |
| 429 |
|
| |
| 430 |
|
| #define STK_ERR(fmt, ...) do { if (errbuf) snprintf(errbuf, STK_ERR_BUFLEN, fmt, ##__VA_ARGS__); } while(0) |
| 431 |
|
| |
| 432 |
108 |
| static inline uint64_t stk_ctl_offset(uint32_t elem_size, uint64_t capacity) { |
| 433 |
108 |
| uint64_t data_end = sizeof(StkHeader) + capacity * elem_size; |
| 434 |
108 |
| return (data_end + 7u) & ~(uint64_t)7u; |
| 435 |
|
| } |
| 436 |
|
| |
| 437 |
41 |
| static inline uint64_t stk_total_size(uint32_t elem_size, uint64_t capacity) { |
| 438 |
41 |
| return stk_ctl_offset(elem_size, capacity) + capacity * sizeof(uint64_t); |
| 439 |
|
| } |
| 440 |
|
| |
| 441 |
32 |
| static inline void stk_init_header(void *base, uint64_t total, |
| 442 |
|
| uint32_t elem_size, uint32_t variant_id, |
| 443 |
|
| uint64_t capacity) { |
| 444 |
32 |
| StkHeader *hdr = (StkHeader *)base; |
| 445 |
32 |
| memset(base, 0, (size_t)total); /* zeroes ctl array -> all slots EMPTY, gen=0 */ |
| 446 |
32 |
| hdr->version = STK_VERSION; |
| 447 |
32 |
| hdr->elem_size = elem_size; |
| 448 |
32 |
| hdr->variant_id = variant_id; |
| 449 |
32 |
| hdr->capacity = capacity; |
| 450 |
32 |
| hdr->total_size = total; |
| 451 |
32 |
| hdr->data_off = sizeof(StkHeader); |
| 452 |
32 |
| hdr->ctl_off = stk_ctl_offset(elem_size, capacity); |
| 453 |
32 |
| __atomic_thread_fence(__ATOMIC_SEQ_CST); |
| 454 |
|
| /* Publish magic LAST, as a release store: it is the commit point, so a |
| 455 |
|
| creator killed before it leaves magic==0 and never a file mistaken for |
| 456 |
|
| a valid one. A kill during the field stores leaves one to remove by |
| 457 |
|
| hand. */ |
| 458 |
32 |
| __atomic_store_n(&hdr->magic, STK_MAGIC, __ATOMIC_RELEASE); |
| 459 |
|
| |
| 460 |
32 |
| } |
| 461 |
|
| |
| 462 |
|
| /* Layout fields are passed in by the caller -- either from a validated |
| 463 |
|
| * header snapshot or locally computed -- never re-read from the live |
| 464 |
|
| * mapping, which a hostile peer could rewrite between validation and |
| 465 |
|
| * here (double-fetch TOCTOU). */ |
| 466 |
35 |
| static inline StkHandle *stk_setup(void *base, size_t msize, |
| 467 |
|
| const char *path, int bfd, |
| 468 |
|
| uint64_t data_off, uint64_t ctl_off, |
| 469 |
|
| uint32_t elem_size, uint64_t capacity) { |
| 470 |
35 |
| StkHandle *h = (StkHandle *)calloc(1, sizeof(StkHandle)); |
| 471 |
35 |
▶ | if (!h) { munmap(base, msize); if (bfd >= 0) close(bfd); return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (!h) { munmap(base, msize); if (bfd >= 0) close(bfd); return NULL; } |
0 |
35 |
35 |
| if (!h) { munmap(base, msize); if (bfd >= 0) close(bfd); return NULL; } |
0 |
0 |
0 |
|
| 472 |
35 |
| h->hdr = (StkHeader *)base; |
| 473 |
35 |
| h->data = (uint8_t *)base + data_off; |
| 474 |
35 |
| h->ctl = (uint64_t *)((uint8_t *)base + ctl_off); |
| 475 |
35 |
| h->mmap_size = msize; |
| 476 |
35 |
| h->elem_size = elem_size; /* cached -- safe from shared-mem tampering */ |
| 477 |
35 |
| h->capacity = capacity; /* cached -- trusted index/length bound */ |
| 478 |
35 |
▶ | h->path = path ? strdup(path) : NULL; |
Branch: 1 branch
| Branch | True | False | Total |
| h->path = path ? strdup(path) : NULL; |
7 |
28 |
35 |
|
| 479 |
35 |
| h->notify_fd = -1; |
| 480 |
35 |
| h->backing_fd = bfd; |
| 481 |
35 |
| return h; |
| 482 |
|
| } |
| 483 |
|
| |
| 484 |
|
| /* Validate a mapped header (shared by stk_create reopen and stk_open_fd). */ |
| 485 |
8 |
| static inline int stk_validate_header(const StkHeader *hdr, uint64_t file_size, |
| 486 |
|
| uint32_t expected_variant) { |
| 487 |
8 |
▶ | if (hdr->magic != STK_MAGIC) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (hdr->magic != STK_MAGIC) return 0; |
5 |
3 |
8 |
|
| 488 |
3 |
▶ | if (hdr->version != STK_VERSION) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (hdr->version != STK_VERSION) return 0; |
0 |
3 |
3 |
|
| 489 |
3 |
▶ | if (hdr->variant_id != expected_variant) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (hdr->variant_id != expected_variant) return 0; |
0 |
3 |
3 |
|
| 490 |
3 |
▶ | if (hdr->elem_size == 0 || hdr->capacity == 0) return 0; |
Branch: 2 branches
| Branch | True | False | Total |
| if (hdr->elem_size == 0 || hdr->capacity == 0) return 0; |
3 |
0 |
3 |
| if (hdr->elem_size == 0 || hdr->capacity == 0) return 0; |
0 |
3 |
3 |
|
| 491 |
|
| /* Pin elem_size to the variant so a crafted header can't drive an over-read/write |
| 492 |
|
| in push/pop: Int reads a fixed 8-byte slot; Str needs a 4-byte length prefix + data. */ |
| 493 |
3 |
▶ | if (expected_variant == STK_VAR_INT && hdr->elem_size != 8) return 0; |
Branch: 2 branches
| Branch | True | False | Total |
| if (expected_variant == STK_VAR_INT && hdr->elem_size != 8) return 0; |
3 |
0 |
3 |
| if (expected_variant == STK_VAR_INT && hdr->elem_size != 8) return 0; |
0 |
3 |
3 |
|
| 494 |
3 |
▶ | if (expected_variant == STK_VAR_STR && hdr->elem_size < 5) return 0; |
Branch: 2 branches
| Branch | True | False | Total |
| if (expected_variant == STK_VAR_STR && hdr->elem_size < 5) return 0; |
0 |
3 |
3 |
| if (expected_variant == STK_VAR_STR && hdr->elem_size < 5) return 0; |
0 |
0 |
0 |
|
| 495 |
3 |
▶ | if (hdr->capacity > 0x7FFFFFFFu) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (hdr->capacity > 0x7FFFFFFFu) return 0; |
0 |
3 |
3 |
|
| 496 |
3 |
▶ | if (hdr->total_size != file_size) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (hdr->total_size != file_size) return 0; |
0 |
3 |
3 |
|
| 497 |
3 |
▶ | if (hdr->data_off != sizeof(StkHeader)) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (hdr->data_off != sizeof(StkHeader)) return 0; |
0 |
3 |
3 |
|
| 498 |
3 |
▶ | if (hdr->ctl_off != stk_ctl_offset(hdr->elem_size, hdr->capacity)) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (hdr->ctl_off != stk_ctl_offset(hdr->elem_size, hdr->capacity)) return 0; |
0 |
3 |
3 |
|
| 499 |
3 |
▶ | if (hdr->total_size != stk_total_size(hdr->elem_size, hdr->capacity)) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (hdr->total_size != stk_total_size(hdr->elem_size, hdr->capacity)) return 0; |
0 |
3 |
3 |
|
| 500 |
3 |
| return 1; |
| 501 |
|
| } |
| 502 |
|
| |
| 503 |
|
| /* Securely obtain a fd: create exclusively (O_CREAT|O_EXCL|O_NOFOLLOW at mode, |
| 504 |
|
| * default 0600), or attach an existing file (O_RDWR|O_NOFOLLOW, no O_CREAT). |
| 505 |
|
| * O_EXCL blocks a pre-seeded/hard-linked file and O_NOFOLLOW a symlink swap, |
| 506 |
|
| * so a local peer cannot redirect or pre-own the backing segment. */ |
| 507 |
11 |
| static int stk_secure_open(const char *path, mode_t mode, char *errbuf) { |
| 508 |
11 |
▶ | for (int attempt = 0; attempt < 100; attempt++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (int attempt = 0; attempt < 100; attempt++) { |
11 |
0 |
11 |
|
| 509 |
11 |
| int fd = open(path, O_RDWR|O_CREAT|O_EXCL|O_NOFOLLOW|O_CLOEXEC, mode); |
| 510 |
11 |
▶ | if (fd >= 0) { (void)fchmod(fd, mode); return fd; } /* exact mode: umask narrowed the O_EXCL create */ |
Branch: 1 branch
| Branch | True | False | Total |
| if (fd >= 0) { (void)fchmod(fd, mode); return fd; } /* exact mode: umask narrowed the O_EXCL create */ |
4 |
7 |
11 |
|
| 511 |
7 |
▶ | if (errno != EEXIST) { STK_ERR("create %s: %s", path, strerror(errno)); return -1; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (errno != EEXIST) { STK_ERR("create %s: %s", path, strerror(errno)); return -1; } |
0 |
7 |
7 |
| if (errno != EEXIST) { STK_ERR("create %s: %s", path, strerror(errno)); return -1; } |
0 |
0 |
0 |
|
| 512 |
7 |
| fd = open(path, O_RDWR|O_NOFOLLOW|O_CLOEXEC); |
| 513 |
7 |
▶ | if (fd >= 0) return fd; |
Branch: 1 branch
| Branch | True | False | Total |
| if (fd >= 0) return fd; |
7 |
0 |
7 |
|
| 514 |
0 |
▶ | if (errno == ENOENT) continue; /* creator unlinked between our two opens; retry */ |
Branch: 1 branch
| Branch | True | False | Total |
| if (errno == ENOENT) continue; /* creator unlinked between our two opens; retry */ |
0 |
0 |
0 |
|
| 515 |
0 |
▶ | STK_ERR("open %s: %s", path, strerror(errno)); /* ELOOP => symlink rejected */ |
Branch: 1 branch
| Branch | True | False | Total |
| STK_ERR("open %s: %s", path, strerror(errno)); /* ELOOP => symlink rejected */ |
0 |
0 |
0 |
|
| 516 |
0 |
| return -1; |
| 517 |
|
| } |
| 518 |
0 |
▶ | STK_ERR("open %s: create/attach kept racing", path); |
Branch: 1 branch
| Branch | True | False | Total |
| STK_ERR("open %s: create/attach kept racing", path); |
0 |
0 |
0 |
|
| 519 |
0 |
| return -1; |
| 520 |
|
| } |
| 521 |
|
| |
| 522 |
|
| /* True iff the whole file is zero -- what an abandoned mid-init |
| 523 |
|
| creator leaves. Lets recovery re-init only a provably-empty file, never |
| 524 |
|
| one that merely starts with a zero word. Cold path, so a byte scan is |
| 525 |
|
| fine. Read, not mapped: a read fault on a tmpfs hole allocates the page. */ |
| 526 |
2 |
| static int stk_file_is_zero(int fd, uint64_t size) { |
| 527 |
|
| char buf[16384]; |
| 528 |
3 |
▶ | for (uint64_t off = 0; off < size; ) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (uint64_t off = 0; off < size; ) { |
2 |
1 |
3 |
|
| 529 |
2 |
| ssize_t n = pread(fd, buf, size - off < sizeof buf ? (size_t)(size - off) : sizeof buf, (off_t)off); |
| 530 |
2 |
▶ | if (n <= 0) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (n <= 0) return 0; |
0 |
2 |
2 |
|
| 531 |
769 |
▶ | for (ssize_t i = 0; i < n; i++) if (buf[i]) return 0; |
Branch: 2 branches
| Branch | True | False | Total |
| for (ssize_t i = 0; i < n; i++) if (buf[i]) return 0; |
1 |
767 |
768 |
| for (ssize_t i = 0; i < n; i++) if (buf[i]) return 0; |
768 |
1 |
769 |
|
| 532 |
1 |
| off += (uint64_t)n; |
| 533 |
|
| } |
| 534 |
1 |
| return 1; |
| 535 |
|
| } |
| 536 |
|
| |
| 537 |
|
| /* A sparse segment would SIGBUS at the first write the filesystem cannot back. */ |
| 538 |
6 |
| static int stk_reserve(int fd, uint64_t size) { |
| 539 |
6 |
| const char *sp = getenv("DATA_STACK_SHARED_SPARSE"); |
| 540 |
6 |
▶ | if (sp && *sp && strcmp(sp, "0")) return 0; |
Branch: 3 branches
| Branch | True | False | Total |
| if (sp && *sp && strcmp(sp, "0")) return 0; |
0 |
6 |
6 |
| if (sp && *sp && strcmp(sp, "0")) return 0; |
0 |
0 |
0 |
| if (sp && *sp && strcmp(sp, "0")) return 0; |
0 |
0 |
0 |
|
| 541 |
|
| /* Before Linux 6.11 tmpfs gives up at any pending signal and undoes the allocation, so a |
| 542 |
|
| * periodic one could keep it from ever completing; SIGSTOP cannot be blocked. */ |
| 543 |
|
| sigset_t all, old; |
| 544 |
6 |
| sigfillset(&all); |
| 545 |
6 |
| sigprocmask(SIG_BLOCK, &all, &old); |
| 546 |
|
| int e; |
| 547 |
6 |
▶ | do e = posix_fallocate(fd, 0, (off_t)size); while (e == EINTR); |
Branch: 1 branch
| Branch | True | False | Total |
| do e = posix_fallocate(fd, 0, (off_t)size); while (e == EINTR); |
0 |
6 |
6 |
|
| 548 |
6 |
| sigprocmask(SIG_SETMASK, &old, NULL); |
| 549 |
6 |
▶ | if (e == 0 || e == EOPNOTSUPP || e == EINVAL) return 0; |
Branch: 3 branches
| Branch | True | False | Total |
| if (e == 0 || e == EOPNOTSUPP || e == EINVAL) return 0; |
0 |
6 |
6 |
| if (e == 0 || e == EOPNOTSUPP || e == EINVAL) return 0; |
0 |
0 |
0 |
| if (e == 0 || e == EOPNOTSUPP || e == EINVAL) return 0; |
0 |
0 |
0 |
|
| 550 |
0 |
| errno = e; |
| 551 |
0 |
| return -1; |
| 552 |
|
| } |
| 553 |
|
| |
| 554 |
37 |
| static StkHandle *stk_create(const char *path, uint64_t capacity, |
| 555 |
|
| uint32_t elem_size, uint32_t variant_id, |
| 556 |
|
| mode_t mode, char *errbuf) { |
| 557 |
37 |
▶ | if (errbuf) errbuf[0] = '\0'; |
Branch: 1 branch
| Branch | True | False | Total |
| if (errbuf) errbuf[0] = '\0'; |
37 |
0 |
37 |
|
| 558 |
37 |
▶ | if (capacity == 0) { STK_ERR("capacity must be > 0"); return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (capacity == 0) { STK_ERR("capacity must be > 0"); return NULL; } |
0 |
37 |
37 |
| if (capacity == 0) { STK_ERR("capacity must be > 0"); return NULL; } |
0 |
0 |
0 |
|
| 559 |
37 |
▶ | if (capacity > 0x7FFFFFFFu) { STK_ERR("capacity too large (max 2147483647)"); return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (capacity > 0x7FFFFFFFu) { STK_ERR("capacity too large (max 2147483647)"); return NULL; } |
0 |
37 |
37 |
| if (capacity > 0x7FFFFFFFu) { STK_ERR("capacity too large (max 2147483647)"); return NULL; } |
0 |
0 |
0 |
|
| 560 |
37 |
▶ | if (elem_size == 0) { STK_ERR("elem_size must be > 0"); return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (elem_size == 0) { STK_ERR("elem_size must be > 0"); return NULL; } |
0 |
37 |
37 |
| if (elem_size == 0) { STK_ERR("elem_size must be > 0"); return NULL; } |
0 |
0 |
0 |
|
| 561 |
37 |
▶ | if (capacity > (UINT64_MAX - sizeof(StkHeader) - 16) / (elem_size + sizeof(uint64_t))) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (capacity > (UINT64_MAX - sizeof(StkHeader) - 16) / (elem_size + sizeof(uint64_t))) { |
0 |
37 |
37 |
|
| 562 |
0 |
▶ | STK_ERR("capacity * elem_size overflow"); return NULL; |
Branch: 1 branch
| Branch | True | False | Total |
| STK_ERR("capacity * elem_size overflow"); return NULL; |
0 |
0 |
0 |
|
| 563 |
|
| } |
| 564 |
|
| |
| 565 |
37 |
| uint64_t total = stk_total_size(elem_size, capacity); |
| 566 |
37 |
| int anonymous = (path == NULL); |
| 567 |
37 |
| int fd = -1; |
| 568 |
|
| size_t map_size; |
| 569 |
|
| void *base; |
| 570 |
|
| |
| 571 |
37 |
▶ | if (anonymous) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (anonymous) { |
26 |
11 |
37 |
|
| 572 |
26 |
| map_size = (size_t)total; |
| 573 |
26 |
| base = mmap(NULL, map_size, PROT_READ|PROT_WRITE, |
| 574 |
|
| MAP_SHARED|MAP_ANONYMOUS, -1, 0); |
| 575 |
26 |
▶ | if (base == MAP_FAILED) { STK_ERR("mmap: %s", strerror(errno)); return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (base == MAP_FAILED) { STK_ERR("mmap: %s", strerror(errno)); return NULL; } |
0 |
26 |
26 |
| if (base == MAP_FAILED) { STK_ERR("mmap: %s", strerror(errno)); return NULL; } |
0 |
0 |
0 |
|
| 576 |
|
| } else { |
| 577 |
11 |
| fd = stk_secure_open(path, mode, errbuf); |
| 578 |
18 |
▶ | if (fd < 0) return NULL; |
Branch: 1 branch
| Branch | True | False | Total |
| if (fd < 0) return NULL; |
0 |
11 |
11 |
|
| 579 |
11 |
▶ | if (flock(fd, LOCK_EX) < 0) { STK_ERR("flock: %s", strerror(errno)); close(fd); return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (flock(fd, LOCK_EX) < 0) { STK_ERR("flock: %s", strerror(errno)); close(fd); return NULL; } |
0 |
11 |
11 |
| if (flock(fd, LOCK_EX) < 0) { STK_ERR("flock: %s", strerror(errno)); close(fd); return NULL; } |
0 |
0 |
0 |
|
| 580 |
|
| |
| 581 |
|
| struct stat st; |
| 582 |
11 |
▶ | if (fstat(fd, &st) < 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (fstat(fd, &st) < 0) { |
0 |
11 |
11 |
|
| 583 |
0 |
▶ | STK_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; |
Branch: 1 branch
| Branch | True | False | Total |
| STK_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; |
0 |
0 |
0 |
|
| 584 |
|
| } |
| 585 |
11 |
| int is_new = (st.st_size == 0); |
| 586 |
11 |
▶ | if (!is_new && (uint64_t)st.st_size < sizeof(StkHeader)) { |
Branch: 2 branches
| Branch | True | False | Total |
| if (!is_new && (uint64_t)st.st_size < sizeof(StkHeader)) { |
7 |
4 |
11 |
| if (!is_new && (uint64_t)st.st_size < sizeof(StkHeader)) { |
0 |
7 |
7 |
|
| 587 |
0 |
▶ | STK_ERR("%s: file too small (%lld)", path, (long long)st.st_size); |
Branch: 1 branch
| Branch | True | False | Total |
| STK_ERR("%s: file too small (%lld)", path, (long long)st.st_size); |
0 |
0 |
0 |
|
| 588 |
0 |
| flock(fd, LOCK_UN); close(fd); return NULL; |
| 589 |
|
| } |
| 590 |
|
| |
| 591 |
11 |
▶ | if (is_new && (st.st_uid != geteuid() || fchmod(fd, mode) < 0)) { |
Branch: 3 branches
| Branch | True | False | Total |
| if (is_new && (st.st_uid != geteuid() || fchmod(fd, mode) < 0)) { |
4 |
7 |
11 |
| if (is_new && (st.st_uid != geteuid() || fchmod(fd, mode) < 0)) { |
4 |
0 |
4 |
| if (is_new && (st.st_uid != geteuid() || fchmod(fd, mode) < 0)) { |
0 |
4 |
4 |
|
| 592 |
0 |
▶ | STK_ERR("%s: refusing to initialize file not owned by us", path); |
Branch: 1 branch
| Branch | True | False | Total |
| STK_ERR("%s: refusing to initialize file not owned by us", path); |
0 |
0 |
0 |
|
| 593 |
0 |
| flock(fd, LOCK_UN); close(fd); return NULL; |
| 594 |
|
| } |
| 595 |
11 |
▶ | if (is_new) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (is_new) { |
4 |
7 |
11 |
|
| 596 |
4 |
▶ | if (ftruncate(fd, (off_t)total) < 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (ftruncate(fd, (off_t)total) < 0) { |
0 |
4 |
4 |
|
| 597 |
0 |
▶ | STK_ERR("ftruncate: %s", strerror(errno)); |
Branch: 1 branch
| Branch | True | False | Total |
| STK_ERR("ftruncate: %s", strerror(errno)); |
0 |
0 |
0 |
|
| 598 |
0 |
| flock(fd, LOCK_UN); close(fd); return NULL; |
| 599 |
|
| } |
| 600 |
4 |
▶ | if (stk_reserve(fd, total) < 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (stk_reserve(fd, total) < 0) { |
0 |
4 |
4 |
|
| 601 |
0 |
▶ | STK_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno)); |
Branch: 1 branch
| Branch | True | False | Total |
| STK_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno)); |
0 |
0 |
0 |
|
| 602 |
0 |
| if (ftruncate(fd, 0) < 0) { /* best effort */ } |
| 603 |
0 |
| flock(fd, LOCK_UN); close(fd); return NULL; |
| 604 |
|
| } |
| 605 |
|
| } |
| 606 |
11 |
▶ | map_size = is_new ? (size_t)total : (size_t)st.st_size; |
Branch: 1 branch
| Branch | True | False | Total |
| map_size = is_new ? (size_t)total : (size_t)st.st_size; |
7 |
4 |
11 |
|
| 607 |
11 |
| base = mmap(NULL, map_size, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0); |
| 608 |
11 |
▶ | if (base == MAP_FAILED) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (base == MAP_FAILED) { |
0 |
11 |
11 |
|
| 609 |
0 |
▶ | STK_ERR("mmap: %s", strerror(errno)); |
Branch: 1 branch
| Branch | True | False | Total |
| STK_ERR("mmap: %s", strerror(errno)); |
0 |
0 |
0 |
|
| 610 |
0 |
▶ | if (is_new && ftruncate(fd, 0) < 0) { /* best effort */ } |
Branch: 1 branch
| Branch | True | False | Total |
| if (is_new && ftruncate(fd, 0) < 0) { /* best effort */ } |
0 |
0 |
0 |
|
| 611 |
0 |
| flock(fd, LOCK_UN); close(fd); return NULL; |
| 612 |
|
| } |
| 613 |
|
| |
| 614 |
11 |
▶ | if (!is_new) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (!is_new) { |
7 |
4 |
11 |
|
| 615 |
|
| StkHeader snap; /* single fetch: validate + setup use one copy */ |
| 616 |
7 |
| memcpy(&snap, base, sizeof snap); |
| 617 |
7 |
▶ | if (!stk_validate_header(&snap, (uint64_t)st.st_size, variant_id)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (!stk_validate_header(&snap, (uint64_t)st.st_size, variant_id)) { |
5 |
2 |
7 |
|
| 618 |
|
| /* Recover an abandoned mid-init file: a creator killed |
| 619 |
|
| * between the ftruncate and the header init leaves a |
| 620 |
|
| * full-size, all-zero (magic==0) file that would brick every |
| 621 |
|
| * future open of this path. Re-initialize ONLY when it is |
| 622 |
|
| * exactly our size, still uninitialized, and owned by us; |
| 623 |
|
| * anything else still errors. */ |
| 624 |
5 |
▶ | if (snap.magic == 0 && (uint64_t)st.st_size == total |
Branch: 2 branches
| Branch | True | False | Total |
| if (snap.magic == 0 && (uint64_t)st.st_size == total |
3 |
2 |
5 |
| if (snap.magic == 0 && (uint64_t)st.st_size == total |
2 |
1 |
3 |
|
| 625 |
2 |
▶ | && st.st_uid == geteuid() && stk_file_is_zero(fd, map_size)) { |
Branch: 2 branches
| Branch | True | False | Total |
| && st.st_uid == geteuid() && stk_file_is_zero(fd, map_size)) { |
2 |
0 |
2 |
| && st.st_uid == geteuid() && stk_file_is_zero(fd, map_size)) { |
1 |
1 |
2 |
|
| 626 |
1 |
▶ | if (fchmod(fd, mode) < 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (fchmod(fd, mode) < 0) { |
0 |
1 |
1 |
|
| 627 |
0 |
▶ | STK_ERR("%s: fchmod: %s", path, strerror(errno)); |
Branch: 1 branch
| Branch | True | False | Total |
| STK_ERR("%s: fchmod: %s", path, strerror(errno)); |
0 |
0 |
0 |
|
| 628 |
0 |
| munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL; |
| 629 |
|
| } |
| 630 |
1 |
▶ | if (stk_reserve(fd, total) < 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (stk_reserve(fd, total) < 0) { |
0 |
1 |
1 |
|
| 631 |
0 |
▶ | STK_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno)); |
Branch: 1 branch
| Branch | True | False | Total |
| STK_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno)); |
0 |
0 |
0 |
|
| 632 |
0 |
| munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL; |
| 633 |
|
| } |
| 634 |
1 |
| stk_init_header(base, total, elem_size, variant_id, capacity); |
| 635 |
1 |
| flock(fd, LOCK_UN); close(fd); |
| 636 |
1 |
| return stk_setup(base, map_size, path, -1, |
| 637 |
|
| sizeof(StkHeader), stk_ctl_offset(elem_size, capacity), |
| 638 |
|
| elem_size, capacity); |
| 639 |
|
| } |
| 640 |
4 |
▶ | if (snap.magic == 0 && (uint64_t)st.st_size == total |
Branch: 2 branches
| Branch | True | False | Total |
| if (snap.magic == 0 && (uint64_t)st.st_size == total |
2 |
2 |
4 |
| if (snap.magic == 0 && (uint64_t)st.st_size == total |
1 |
1 |
2 |
|
| 641 |
1 |
▶ | && st.st_uid == geteuid()) |
Branch: 1 branch
| Branch | True | False | Total |
| && st.st_uid == geteuid()) |
1 |
0 |
1 |
|
| 642 |
1 |
▶ | STK_ERR("incomplete stack file left by an interrupted create; remove it and retry"); |
Branch: 1 branch
| Branch | True | False | Total |
| STK_ERR("incomplete stack file left by an interrupted create; remove it and retry"); |
1 |
0 |
1 |
|
| 643 |
|
| else |
| 644 |
3 |
▶ | STK_ERR("invalid or incompatible stack file"); |
Branch: 1 branch
| Branch | True | False | Total |
| STK_ERR("invalid or incompatible stack file"); |
3 |
0 |
3 |
|
| 645 |
4 |
| munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL; |
| 646 |
|
| } |
| 647 |
2 |
| flock(fd, LOCK_UN); close(fd); |
| 648 |
2 |
| return stk_setup(base, map_size, path, -1, |
| 649 |
|
| snap.data_off, snap.ctl_off, |
| 650 |
|
| snap.elem_size, snap.capacity); |
| 651 |
|
| } |
| 652 |
|
| } |
| 653 |
|
| |
| 654 |
30 |
| stk_init_header(base, total, elem_size, variant_id, capacity); |
| 655 |
30 |
▶ | if (fd >= 0) { flock(fd, LOCK_UN); close(fd); } |
Branch: 1 branch
| Branch | True | False | Total |
| if (fd >= 0) { flock(fd, LOCK_UN); close(fd); } |
4 |
26 |
30 |
|
| 656 |
30 |
| return stk_setup(base, map_size, path, -1, |
| 657 |
|
| sizeof(StkHeader), stk_ctl_offset(elem_size, capacity), |
| 658 |
|
| elem_size, capacity); |
| 659 |
|
| } |
| 660 |
|
| |
| 661 |
1 |
| static StkHandle *stk_create_memfd(const char *name, uint64_t capacity, |
| 662 |
|
| uint32_t elem_size, uint32_t variant_id, |
| 663 |
|
| char *errbuf) { |
| 664 |
1 |
▶ | if (errbuf) errbuf[0] = '\0'; |
Branch: 1 branch
| Branch | True | False | Total |
| if (errbuf) errbuf[0] = '\0'; |
1 |
0 |
1 |
|
| 665 |
1 |
▶ | if (capacity == 0) { STK_ERR("capacity must be > 0"); return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (capacity == 0) { STK_ERR("capacity must be > 0"); return NULL; } |
0 |
1 |
1 |
| if (capacity == 0) { STK_ERR("capacity must be > 0"); return NULL; } |
0 |
0 |
0 |
|
| 666 |
1 |
▶ | if (capacity > 0x7FFFFFFFu) { STK_ERR("capacity too large (max 2147483647)"); return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (capacity > 0x7FFFFFFFu) { STK_ERR("capacity too large (max 2147483647)"); return NULL; } |
0 |
1 |
1 |
| if (capacity > 0x7FFFFFFFu) { STK_ERR("capacity too large (max 2147483647)"); return NULL; } |
0 |
0 |
0 |
|
| 667 |
1 |
▶ | if (elem_size == 0) { STK_ERR("elem_size must be > 0"); return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (elem_size == 0) { STK_ERR("elem_size must be > 0"); return NULL; } |
0 |
1 |
1 |
| if (elem_size == 0) { STK_ERR("elem_size must be > 0"); return NULL; } |
0 |
0 |
0 |
|
| 668 |
1 |
▶ | if (capacity > (UINT64_MAX - sizeof(StkHeader) - 16) / (elem_size + sizeof(uint64_t))) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (capacity > (UINT64_MAX - sizeof(StkHeader) - 16) / (elem_size + sizeof(uint64_t))) { |
0 |
1 |
1 |
|
| 669 |
0 |
▶ | STK_ERR("capacity * elem_size overflow"); return NULL; |
Branch: 1 branch
| Branch | True | False | Total |
| STK_ERR("capacity * elem_size overflow"); return NULL; |
0 |
0 |
0 |
|
| 670 |
|
| } |
| 671 |
|
| |
| 672 |
1 |
| uint64_t total = stk_total_size(elem_size, capacity); |
| 673 |
1 |
▶ | int fd = memfd_create(name ? name : "stack", MFD_CLOEXEC | MFD_ALLOW_SEALING); |
Branch: 1 branch
| Branch | True | False | Total |
| int fd = memfd_create(name ? name : "stack", MFD_CLOEXEC | MFD_ALLOW_SEALING); |
1 |
0 |
1 |
|
| 674 |
1 |
▶ | if (fd < 0) { STK_ERR("memfd_create: %s", strerror(errno)); return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (fd < 0) { STK_ERR("memfd_create: %s", strerror(errno)); return NULL; } |
0 |
1 |
1 |
| if (fd < 0) { STK_ERR("memfd_create: %s", strerror(errno)); return NULL; } |
0 |
0 |
0 |
|
| 675 |
1 |
▶ | if (ftruncate(fd, (off_t)total) < 0) { STK_ERR("ftruncate: %s", strerror(errno)); close(fd); return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (ftruncate(fd, (off_t)total) < 0) { STK_ERR("ftruncate: %s", strerror(errno)); close(fd); return NULL; } |
0 |
1 |
1 |
| if (ftruncate(fd, (off_t)total) < 0) { STK_ERR("ftruncate: %s", strerror(errno)); close(fd); return NULL; } |
0 |
0 |
0 |
|
| 676 |
1 |
▶ | if (stk_reserve(fd, total) < 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (stk_reserve(fd, total) < 0) { |
0 |
1 |
1 |
|
| 677 |
0 |
▶ | STK_ERR("memfd: cannot reserve %llu bytes: %s", (unsigned long long)total, strerror(errno)); |
Branch: 1 branch
| Branch | True | False | Total |
| STK_ERR("memfd: cannot reserve %llu bytes: %s", (unsigned long long)total, strerror(errno)); |
0 |
0 |
0 |
|
| 678 |
0 |
| close(fd); return NULL; |
| 679 |
|
| } |
| 680 |
1 |
| (void)fcntl(fd, F_ADD_SEALS, F_SEAL_SHRINK | F_SEAL_GROW); |
| 681 |
1 |
| void *base = mmap(NULL, (size_t)total, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0); |
| 682 |
1 |
▶ | if (base == MAP_FAILED) { STK_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (base == MAP_FAILED) { STK_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; } |
0 |
1 |
1 |
| if (base == MAP_FAILED) { STK_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; } |
0 |
0 |
0 |
|
| 683 |
1 |
| stk_init_header(base, total, elem_size, variant_id, capacity); |
| 684 |
1 |
| return stk_setup(base, (size_t)total, NULL, fd, |
| 685 |
|
| sizeof(StkHeader), stk_ctl_offset(elem_size, capacity), |
| 686 |
|
| elem_size, capacity); |
| 687 |
|
| } |
| 688 |
|
| |
| 689 |
1 |
| static StkHandle *stk_open_fd(int fd, uint32_t variant_id, char *errbuf) { |
| 690 |
1 |
▶ | if (errbuf) errbuf[0] = '\0'; |
Branch: 1 branch
| Branch | True | False | Total |
| if (errbuf) errbuf[0] = '\0'; |
1 |
0 |
1 |
|
| 691 |
|
| struct stat st; |
| 692 |
1 |
▶ | if (fstat(fd, &st) < 0) { STK_ERR("fstat: %s", strerror(errno)); return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (fstat(fd, &st) < 0) { STK_ERR("fstat: %s", strerror(errno)); return NULL; } |
0 |
1 |
1 |
| if (fstat(fd, &st) < 0) { STK_ERR("fstat: %s", strerror(errno)); return NULL; } |
0 |
0 |
0 |
|
| 693 |
1 |
▶ | if ((uint64_t)st.st_size < sizeof(StkHeader)) { STK_ERR("too small"); return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if ((uint64_t)st.st_size < sizeof(StkHeader)) { STK_ERR("too small"); return NULL; } |
0 |
1 |
1 |
| if ((uint64_t)st.st_size < sizeof(StkHeader)) { STK_ERR("too small"); return NULL; } |
0 |
0 |
0 |
|
| 694 |
|
| /* before mmap: a creator may truncate the file until it has set magic */ |
| 695 |
|
| uint32_t magic; |
| 696 |
1 |
▶ | if (pread(fd, &magic, sizeof magic, offsetof(StkHeader, magic)) != (ssize_t)sizeof magic || magic != STK_MAGIC) { |
Branch: 2 branches
| Branch | True | False | Total |
| if (pread(fd, &magic, sizeof magic, offsetof(StkHeader, magic)) != (ssize_t)sizeof magic || magic != STK_MAGIC) { |
1 |
0 |
1 |
| if (pread(fd, &magic, sizeof magic, offsetof(StkHeader, magic)) != (ssize_t)sizeof magic || magic != STK_MAGIC) { |
0 |
1 |
1 |
|
| 697 |
0 |
▶ | STK_ERR("invalid stack"); return NULL; |
Branch: 1 branch
| Branch | True | False | Total |
| STK_ERR("invalid stack"); return NULL; |
0 |
0 |
0 |
|
| 698 |
|
| } |
| 699 |
1 |
| size_t ms = (size_t)st.st_size; |
| 700 |
1 |
| void *base = mmap(NULL, ms, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0); |
| 701 |
1 |
▶ | if (base == MAP_FAILED) { STK_ERR("mmap: %s", strerror(errno)); return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (base == MAP_FAILED) { STK_ERR("mmap: %s", strerror(errno)); return NULL; } |
0 |
1 |
1 |
| if (base == MAP_FAILED) { STK_ERR("mmap: %s", strerror(errno)); return NULL; } |
0 |
0 |
0 |
|
| 702 |
|
| StkHeader snap; /* single fetch: validate + setup use one copy */ |
| 703 |
1 |
| memcpy(&snap, base, sizeof snap); |
| 704 |
1 |
▶ | if (!stk_validate_header(&snap, (uint64_t)st.st_size, variant_id)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (!stk_validate_header(&snap, (uint64_t)st.st_size, variant_id)) { |
0 |
1 |
1 |
|
| 705 |
0 |
▶ | STK_ERR("invalid stack"); munmap(base, ms); return NULL; |
Branch: 1 branch
| Branch | True | False | Total |
| STK_ERR("invalid stack"); munmap(base, ms); return NULL; |
0 |
0 |
0 |
|
| 706 |
|
| } |
| 707 |
1 |
| int myfd = fcntl(fd, F_DUPFD_CLOEXEC, 0); |
| 708 |
1 |
▶ | if (myfd < 0) { STK_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (myfd < 0) { STK_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; } |
0 |
1 |
1 |
| if (myfd < 0) { STK_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; } |
0 |
0 |
0 |
|
| 709 |
1 |
| return stk_setup(base, ms, NULL, myfd, |
| 710 |
|
| snap.data_off, snap.ctl_off, snap.elem_size, snap.capacity); |
| 711 |
|
| } |
| 712 |
|
| |
| 713 |
35 |
| static void stk_destroy(StkHandle *h) { |
| 714 |
35 |
▶ | if (!h) return; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!h) return; |
0 |
35 |
35 |
|
| 715 |
35 |
▶ | if (h->notify_fd >= 0) close(h->notify_fd); |
Branch: 1 branch
| Branch | True | False | Total |
| if (h->notify_fd >= 0) close(h->notify_fd); |
2 |
33 |
35 |
|
| 716 |
35 |
▶ | if (h->backing_fd >= 0) close(h->backing_fd); |
Branch: 1 branch
| Branch | True | False | Total |
| if (h->backing_fd >= 0) close(h->backing_fd); |
2 |
33 |
35 |
|
| 717 |
35 |
▶ | if (h->hdr) munmap(h->hdr, h->mmap_size); |
Branch: 1 branch
| Branch | True | False | Total |
| if (h->hdr) munmap(h->hdr, h->mmap_size); |
35 |
0 |
35 |
|
| 718 |
35 |
| free(h->path); |
| 719 |
35 |
| free(h); |
| 720 |
|
| } |
| 721 |
|
| |
| 722 |
|
| /* NOT concurrency-safe -- use drain() for concurrent scenarios */ |
| 723 |
3 |
| static void stk_clear(StkHandle *h) { |
| 724 |
3 |
| __atomic_store_n(&h->hdr->top, 0, __ATOMIC_RELEASE); |
| 725 |
3 |
| memset(h->ctl, 0, (size_t)h->capacity * sizeof(uint64_t)); /* trusted cached length */ |
| 726 |
|
| /* clear() frees the entire stack at once -- wake all waiters. |
| 727 |
|
| * StoreLoad barrier: publish top=0 before reading the waiter counts. */ |
| 728 |
3 |
| __atomic_thread_fence(__ATOMIC_SEQ_CST); |
| 729 |
3 |
▶ | if (__atomic_load_n(&h->hdr->waiters_push, __ATOMIC_RELAXED) > 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (__atomic_load_n(&h->hdr->waiters_push, __ATOMIC_RELAXED) > 0) { |
0 |
3 |
3 |
|
| 730 |
0 |
| __atomic_add_fetch(&h->hdr->push_wake_seq, 1, __ATOMIC_RELEASE); |
| 731 |
0 |
| syscall(SYS_futex, &h->hdr->push_wake_seq, FUTEX_WAKE, INT_MAX, NULL, NULL, 0); |
| 732 |
|
| } |
| 733 |
3 |
▶ | if (__atomic_load_n(&h->hdr->waiters_pop, __ATOMIC_RELAXED) > 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (__atomic_load_n(&h->hdr->waiters_pop, __ATOMIC_RELAXED) > 0) { |
0 |
3 |
3 |
|
| 734 |
0 |
| __atomic_add_fetch(&h->hdr->pop_wake_seq, 1, __ATOMIC_RELEASE); |
| 735 |
0 |
| syscall(SYS_futex, &h->hdr->pop_wake_seq, FUTEX_WAKE, INT_MAX, NULL, NULL, 0); |
| 736 |
|
| } |
| 737 |
3 |
| } |
| 738 |
|
| |
| 739 |
|
| /* Concurrency-safe drain: atomically swap top to 0, then release each |
| 740 |
|
| * drained slot through the state machine. Returns count drained. |
| 741 |
|
| * |
| 742 |
|
| * Crash-recovery: a pusher that won the top CAS but died (SIGKILL/segfault) |
| 743 |
|
| * between stk_slot_claim_write and stk_slot_publish leaves the slot stuck |
| 744 |
|
| * in WRITING. Plain stk_slot_claim_read would spin forever. We bound the |
| 745 |
|
| * wait at ~2s per slot; on timeout we CAS WRITING -> EMPTY (gen bumped) so |
| 746 |
|
| * the slot is reclaimed. |
| 747 |
|
| * |
| 748 |
|
| * Limitation: slot ctl encodes only (gen << 2) | state -- no PID -- so we |
| 749 |
|
| * cannot distinguish a crashed pusher from a merely slow one. A live pusher |
| 750 |
|
| * stalled > 2s would be falsely reclaimed; its subsequent publish is a CAS |
| 751 |
|
| * (see stk_slot_publish) so it observes the gen bump and silently no-ops |
| 752 |
|
| * rather than resurrecting a phantom FILLED slot. The pusher's value is |
| 753 |
|
| * dropped -- equivalent to a crashed pusher. In practice the gap between |
| 754 |
|
| * claim_write and publish is sub-microsecond memcpy time, so the false- |
| 755 |
|
| * positive threshold is many orders of magnitude away from normal latency. */ |
| 756 |
2 |
| static inline uint32_t stk_drain(StkHandle *h) { |
| 757 |
2 |
| StkHeader *hdr = h->hdr; |
| 758 |
2 |
| uint32_t t = __atomic_exchange_n(&hdr->top, 0, __ATOMIC_ACQ_REL); |
| 759 |
2 |
▶ | if (t == 0) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (t == 0) return 0; |
1 |
1 |
2 |
|
| 760 |
1 |
▶ | if (t > h->capacity) t = (uint32_t)h->capacity; /* corrupted top: clamp loop to real ctl array */ |
Branch: 1 branch
| Branch | True | False | Total |
| if (t > h->capacity) t = (uint32_t)h->capacity; /* corrupted top: clamp loop to real ctl array */ |
0 |
1 |
1 |
|
| 761 |
|
| /* Wall-clock deadline for the per-slot wait. We hot-spin first, then |
| 762 |
|
| * fall back to short sleeps to avoid burning a core for 2s on a stuck |
| 763 |
|
| * slot. The deadline is checked periodically (every 64 iterations) to |
| 764 |
|
| * keep the steady-state cost ~zero. */ |
| 765 |
6 |
▶ | for (uint32_t i = 0; i < t; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (uint32_t i = 0; i < t; i++) { |
5 |
1 |
6 |
|
| 766 |
|
| struct timespec dl; |
| 767 |
5 |
| int dl_set = 0; |
| 768 |
5 |
| uint32_t spins = 0; |
| 769 |
0 |
| for (;;) { |
| 770 |
5 |
| uint64_t c = __atomic_load_n(&h->ctl[i], __ATOMIC_ACQUIRE); |
| 771 |
5 |
| uint32_t st = STK_SLOT_STATE(c); |
| 772 |
5 |
▶ | if (st == STK_SLOT_FILLED) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (st == STK_SLOT_FILLED) { |
5 |
0 |
5 |
|
| 773 |
5 |
| uint64_t nc = (STK_SLOT_GEN(c) << 2) | STK_SLOT_READING; |
| 774 |
5 |
▶ | if (__atomic_compare_exchange_n(&h->ctl[i], &c, nc, |
Branch: 1 branch
| Branch | True | False | Total |
| if (__atomic_compare_exchange_n(&h->ctl[i], &c, nc, |
5 |
0 |
5 |
|
| 775 |
|
| 0, __ATOMIC_ACQUIRE, __ATOMIC_RELAXED)) { |
| 776 |
5 |
| stk_slot_release(&h->ctl[i], STK_SLOT_GEN(c)); |
| 777 |
5 |
| break; |
| 778 |
|
| } |
| 779 |
0 |
| continue; |
| 780 |
|
| } |
| 781 |
0 |
| stk_spin_pause(); |
| 782 |
0 |
▶ | if ((++spins & 0x3F) == 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| if ((++spins & 0x3F) == 0) { |
0 |
0 |
0 |
|
| 783 |
0 |
▶ | if (!dl_set) { stk_make_deadline(2.0, &dl); dl_set = 1; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (!dl_set) { stk_make_deadline(2.0, &dl); dl_set = 1; } |
0 |
0 |
0 |
|
| 784 |
|
| struct timespec rem; |
| 785 |
0 |
▶ | if (!stk_remaining(&dl, &rem)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (!stk_remaining(&dl, &rem)) { |
0 |
0 |
0 |
|
| 786 |
|
| /* Treat as abandoned (crashed writer/reader): force the |
| 787 |
|
| * slot back to EMPTY with gen bumped. If CAS succeeds we |
| 788 |
|
| * skipped the slot; if it fails, the writer just published |
| 789 |
|
| * (or another recoverer fixed it) -- loop and re-observe so |
| 790 |
|
| * a FILLED value is not leaked. */ |
| 791 |
0 |
| uint64_t nc = ((STK_SLOT_GEN(c) + 1) << 2) | STK_SLOT_EMPTY; |
| 792 |
0 |
▶ | if (__atomic_compare_exchange_n(&h->ctl[i], &c, nc, |
Branch: 1 branch
| Branch | True | False | Total |
| if (__atomic_compare_exchange_n(&h->ctl[i], &c, nc, |
0 |
0 |
0 |
|
| 793 |
|
| 0, __ATOMIC_ACQ_REL, __ATOMIC_RELAXED)) |
| 794 |
0 |
| break; |
| 795 |
0 |
| continue; |
| 796 |
|
| } |
| 797 |
|
| /* Short sleep to keep CPU usage low during the long wait. */ |
| 798 |
0 |
| struct timespec ts = { 0, 100000L }; /* 100us */ |
| 799 |
0 |
| nanosleep(&ts, NULL); |
| 800 |
|
| } |
| 801 |
|
| } |
| 802 |
|
| } |
| 803 |
|
| /* drain freed `t` slots at once -- wake up to that many. |
| 804 |
|
| * StoreLoad barrier: publish the freed slots before reading waiters_push. */ |
| 805 |
1 |
| __atomic_thread_fence(__ATOMIC_SEQ_CST); |
| 806 |
1 |
▶ | if (__atomic_load_n(&hdr->waiters_push, __ATOMIC_RELAXED) > 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (__atomic_load_n(&hdr->waiters_push, __ATOMIC_RELAXED) > 0) { |
0 |
1 |
1 |
|
| 807 |
0 |
| __atomic_add_fetch(&hdr->push_wake_seq, 1, __ATOMIC_RELEASE); |
| 808 |
0 |
▶ | syscall(SYS_futex, &hdr->push_wake_seq, FUTEX_WAKE, |
Branch: 1 branch
| Branch | True | False | Total |
| syscall(SYS_futex, &hdr->push_wake_seq, FUTEX_WAKE, |
0 |
0 |
0 |
|
| 809 |
|
| t < INT_MAX ? (int)t : INT_MAX, NULL, NULL, 0); |
| 810 |
|
| } |
| 811 |
1 |
| return t; |
| 812 |
|
| } |
| 813 |
|
| |
| 814 |
|
| /* eventfd */ |
| 815 |
2 |
| static int stk_create_eventfd(StkHandle *h) { |
| 816 |
2 |
▶ | if (h->notify_fd >= 0) return h->notify_fd; |
Branch: 1 branch
| Branch | True | False | Total |
| if (h->notify_fd >= 0) return h->notify_fd; |
0 |
2 |
2 |
|
| 817 |
2 |
| int efd = eventfd(0, EFD_NONBLOCK|EFD_CLOEXEC); |
| 818 |
2 |
▶ | if (efd < 0) return -1; |
Branch: 1 branch
| Branch | True | False | Total |
| if (efd < 0) return -1; |
0 |
2 |
2 |
|
| 819 |
2 |
| h->notify_fd = efd; |
| 820 |
2 |
| return efd; |
| 821 |
|
| } |
| 822 |
3 |
| static int stk_notify(StkHandle *h) { |
| 823 |
3 |
▶ | if (h->notify_fd < 0) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (h->notify_fd < 0) return 0; |
0 |
3 |
3 |
|
| 824 |
3 |
| uint64_t v = 1; |
| 825 |
3 |
| return write(h->notify_fd, &v, sizeof(v)) == sizeof(v); |
| 826 |
|
| } |
| 827 |
2 |
| static int64_t stk_eventfd_consume(StkHandle *h) { |
| 828 |
2 |
▶ | if (h->notify_fd < 0) return -1; |
Branch: 1 branch
| Branch | True | False | Total |
| if (h->notify_fd < 0) return -1; |
0 |
2 |
2 |
|
| 829 |
2 |
| uint64_t v = 0; |
| 830 |
2 |
▶ | if (read(h->notify_fd, &v, sizeof(v)) != sizeof(v)) return -1; |
Branch: 1 branch
| Branch | True | False | Total |
| if (read(h->notify_fd, &v, sizeof(v)) != sizeof(v)) return -1; |
0 |
2 |
2 |
|
| 831 |
2 |
| return (int64_t)v; |
| 832 |
|
| } |
| 833 |
1 |
| static int stk_msync(StkHandle *h) { return msync(h->hdr, h->mmap_size, MS_SYNC); } |
| 834 |
|
| |
| 835 |
|
| #endif /* STACK_H */ |