deque.h

filter: Statementstmt 85.4% 442 / 517 Branchbran 53.9% 231 / 428 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 71.2% 673 / 945 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« Shared.xs ↑ Summary
1 /*
2 * deque.h -- Fixed-size shared-memory double-ended queue for Linux
3 *
4 * Ring buffer with CAS-based push/pop at both ends, plus a per-slot
5 * publication state machine for MPMC safety:
6 *
7 * EMPTY -> WRITING (pusher claims slot)
8 * WRITING-> FILLED (pusher publishes value)
9 * FILLED -> READING (popper claims slot)
10 * READING-> EMPTY (popper releases, generation bumps)
11 *
12 * The slot's ctl word encodes (generation << 2) | state_bits, and
13 * transitions are made via CAS. Head/tail still serialize the POSITION
14 * handout; the per-slot state machine serializes the VALUE handoff.
15 * Readers take the publication gate before advancing head/tail.
16 *
17 * Futex blocking when empty or full.
18 */
19  
20 #ifndef DEQUE_H
21 #define DEQUE_H
22  
23 #include <stddef.h>
24 #include <stdint.h>
25 #include <stdbool.h>
26 #include <stdlib.h>
27 #include <string.h>
28 #include <unistd.h>
29 #include <fcntl.h>
30 #include <errno.h>
31 #include <time.h>
32 #include <limits.h>
33 #include <signal.h>
34 #include <sys/mman.h>
35 #include <sys/stat.h>
36 #include <sys/file.h>
37 #include <sys/syscall.h>
38 #include <linux/futex.h>
39 #include <sys/eventfd.h>
40  
41 #define DEQ_MAGIC 0x44455133U /* "DEQ3" -- generation-qualified wake hints */
42 #define DEQ_VERSION 3
43 #define DEQ_ERR_BUFLEN (PATH_MAX + 256)
44  
45 #ifndef DEQ_WAIT_INTERRUPTED
46 #define DEQ_WAIT_INTERRUPTED() 0
47 #endif
48  
49 /* A slot must stay stuck this long before recovery. */
50 #define DEQ_DRAIN_RECOVERY_SEC 2
51  
52 #define DEQ_VAR_INT 0
53 #define DEQ_VAR_STR 1
54  
55 /* Slot state (low 2 bits of ctl word). Upper 62 bits = generation. */
56 #define DEQ_SLOT_EMPTY 0u
57 #define DEQ_SLOT_WRITING 1u
58 #define DEQ_SLOT_FILLED 2u
59 #define DEQ_SLOT_READING 3u
60 #define DEQ_SLOT_STATE_MASK 3u
61 #define DEQ_SLOT_STATE(c) ((uint32_t)((c) & DEQ_SLOT_STATE_MASK))
62 #define DEQ_SLOT_GEN(c) ((c) >> 2)
63  
64 /* Combined cursor: upper 32 bits = head, lower 32 bits = tail. A single
65 * 64-bit CAS atomically updates both ends, so push_front vs push_back (or
66 * pop_front vs pop_back) cannot both succeed when they share a boundary
67 * slot. Capacity is bounded by 2^31 elements. Head and tail wrap mod 2^32
68 * after 4B ops; size = (tail - head) treated as uint32.
69 */
70 typedef struct {
71 uint32_t magic;
72 uint32_t version;
73 uint32_t elem_size;
74 uint32_t variant_id;
75 uint64_t capacity;
76 uint64_t total_size;
77 uint64_t data_off;
78 uint64_t ctl_off; /* offset to per-slot ctl array */
79 uint32_t push_wait_hint; /* registration generation + active bit */
80 uint32_t pop_wait_hint;
81 uint8_t _pad0[8];
82  
83 uint64_t cursor; /* 64: (head<<32)|tail */
84 uint32_t waiters_push; /* 72 */
85 uint32_t waiters_pop; /* 76 */
86 uint64_t stat_pushes; /* 80 */
87 uint64_t stat_pops; /* 88 */
88 uint64_t stat_waits; /* 96 */
89 uint64_t stat_timeouts; /* 104 */
90 uint32_t push_wake_seq; /* 112: futex word for pushers */
91 uint32_t pop_wake_seq; /* 116: futex word for poppers */
92 uint64_t stat_recoveries; /* 120: recovery of abandoned/stuck slots (WRITING, READING, or EMPTY) */
93 } DeqHeader;
94  
95 #define DEQ_CURSOR(head, tail) (((uint64_t)(head) << 32) | (uint32_t)(tail))
96 #define DEQ_CURSOR_HEAD(c) ((uint32_t)((c) >> 32))
97 #define DEQ_CURSOR_TAIL(c) ((uint32_t)(c))
98 #define DEQ_CURSOR_SIZE(c) ((uint32_t)(DEQ_CURSOR_TAIL(c) - DEQ_CURSOR_HEAD(c)))
99  
100 #if defined(__STDC_VERSION__) && __STDC_VERSION__ >= 201112L
101 _Static_assert(sizeof(DeqHeader) == 128, "DeqHeader must be 128 bytes");
102 #endif
103  
104 typedef struct {
105 DeqHeader *hdr;
106 uint8_t *data;
107 uint64_t *ctl; /* per-slot state+generation word */
108 size_t mmap_size;
109 uint32_t elem_size;
110 uint32_t capacity; /* cached-at-attach ring size (fixed geometry) */
111 char *path;
112 int notify_fd;
113 int backing_fd;
114 } DeqHandle;
115  
116 /* ================================================================ */
117  
118 13 static inline void deq_make_deadline(double t, struct timespec *dl) {
119 13 clock_gettime(CLOCK_MONOTONIC, dl);
120 13 ▶ if (!(t < 1e9)) t = 1e9; /* clamp Inf/NaN/huge: avoid UB (time_t) cast -> instant spurious timeout */
Branch: 1 branch
BranchTrueFalseTotal
if (!(t < 1e9)) t = 1e9; /* clamp Inf/NaN/huge: avoid UB (time_t) cast -> instant spurious timeout */ 0 13 13
121 13 dl->tv_sec += (time_t)t;
122 13 dl->tv_nsec += (long)((t - (double)(time_t)t) * 1e9);
123 13 ▶ if (dl->tv_nsec >= 1000000000L) { dl->tv_sec++; dl->tv_nsec -= 1000000000L; }
Branch: 1 branch
BranchTrueFalseTotal
if (dl->tv_nsec >= 1000000000L) { dl->tv_sec++; dl->tv_nsec -= 1000000000L; } 0 13 13
124 13 }
125  
126 30318 static inline int deq_remaining(const struct timespec *dl, struct timespec *rem) {
127 struct timespec now;
128 30318 clock_gettime(CLOCK_MONOTONIC, &now);
129 30318 rem->tv_sec = dl->tv_sec - now.tv_sec;
130 30318 rem->tv_nsec = dl->tv_nsec - now.tv_nsec;
131 30318 ▶ if (rem->tv_nsec < 0) { rem->tv_sec--; rem->tv_nsec += 1000000000L; }
Branch: 1 branch
BranchTrueFalseTotal
if (rem->tv_nsec < 0) { rem->tv_sec--; rem->tv_nsec += 1000000000L; } 10692 19626 30318
132 30318 return rem->tv_sec >= 0;
133 }
134  
135 36272 static inline uint64_t *deq_ctl_at(DeqHandle *h, uint32_t idx) {
136 36272 return &h->ctl[idx];
137 }
138  
139 36258 static inline void deq_copy(void *dst, const void *src, uint32_t size) {
140 36258 ▶ if (size == sizeof(uint64_t)) memcpy(dst, src, sizeof(uint64_t));
Branch: 1 branch
BranchTrueFalseTotal
if (size == sizeof(uint64_t)) memcpy(dst, src, sizeof(uint64_t)); 36178 80 36258
141 80 else memcpy(dst, src, size);
142 36258 }
143  
144 34 static inline uint32_t deq_size(DeqHandle *h) {
145 34 uint64_t c = __atomic_load_n(&h->hdr->cursor, __ATOMIC_ACQUIRE);
146 34 return DEQ_CURSOR_SIZE(c);
147 }
148  
149 1939776 static inline void deq_spin_pause(void) {
150 #if defined(__x86_64__) || defined(__i386__)
151 1939776 __asm__ volatile("pause" ::: "memory");
152 #elif defined(__aarch64__)
153 __asm__ volatile("yield" ::: "memory");
154 #endif
155 1939776 }
156  
157 36259 static inline void deq_after_rmw_fence(void) {
158 #if defined(__x86_64__) || defined(__i386__)
159 /* The preceding locked RMW already supplies the CPU fence. */
160 36259 __asm__ volatile("" ::: "memory");
161 #else
162 __atomic_thread_fence(__ATOMIC_SEQ_CST);
163 #endif
164 36259 }
165  
166 5 static inline void deq_waiter_enter(uint32_t *count, uint32_t *hint) {
167 5 __atomic_add_fetch(count, 1, __ATOMIC_RELEASE);
168 5 uint32_t c = __atomic_load_n(hint, __ATOMIC_RELAXED);
169 5 ▶ while (!__atomic_compare_exchange_n(hint, &c, (c + 2u) | 1u,
Branch: 1 branch
BranchTrueFalseTotal
while (!__atomic_compare_exchange_n(hint, &c, (c + 2u) | 1u, 0 5 5
170 1, __ATOMIC_RELEASE, __ATOMIC_RELAXED)) {}
171 5 }
172  
173 5 static inline void deq_waiter_leave(uint32_t *count, uint32_t *hint) {
174 5 uint32_t c = __atomic_load_n(hint, __ATOMIC_RELAXED);
175 5 ▶ if (__atomic_sub_fetch(count, 1, __ATOMIC_RELAXED) == 0)
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_sub_fetch(count, 1, __ATOMIC_RELAXED) == 0) 5 0 5
176 5 __atomic_compare_exchange_n(hint, &c, c & ~1u,
177 0, __ATOMIC_RELEASE, __ATOMIC_RELAXED);
178 5 }
179  
180 1 static void deq_wake_slow(DeqHeader *hdr, int push, int n, uint32_t c) {
181 1 ▶ uint32_t *hint = push ? &hdr->push_wait_hint : &hdr->pop_wait_hint;
Branch: 1 branch
BranchTrueFalseTotal
uint32_t *hint = push ? &hdr->push_wait_hint : &hdr->pop_wait_hint; 1 0 1
182 1 ▶ uint32_t *seq = push ? &hdr->push_wake_seq : &hdr->pop_wake_seq;
Branch: 1 branch
BranchTrueFalseTotal
uint32_t *seq = push ? &hdr->push_wake_seq : &hdr->pop_wake_seq; 1 0 1
183 1 __atomic_add_fetch(seq, 1, __ATOMIC_RELEASE);
184 /* Forget dead waiters only if nobody registered during the wake. */
185 1 ▶ if (syscall(SYS_futex, seq, FUTEX_WAKE, n, NULL, NULL, 0) == 0)
Branch: 1 branch
BranchTrueFalseTotal
if (syscall(SYS_futex, seq, FUTEX_WAKE, n, NULL, NULL, 0) == 0) 0 1 1
186 0 __atomic_compare_exchange_n(hint, &c, c & ~1u,
187 0, __ATOMIC_RELEASE, __ATOMIC_RELAXED);
188 1 }
189  
190 36268 static inline void deq_wake(DeqHeader *hdr, int push, int n) {
191 36268 ▶ uint32_t c = __atomic_load_n(push ? &hdr->push_wait_hint : &hdr->pop_wait_hint,
Branch: 1 branch
BranchTrueFalseTotal
uint32_t c = __atomic_load_n(push ? &hdr->push_wait_hint : &hdr->pop_wait_hint, 36101 167 36268
192 __ATOMIC_RELAXED);
193 36268 ▶ if (c & 1u) deq_wake_slow(hdr, push, n, c);
Branch: 1 branch
BranchTrueFalseTotal
if (c & 1u) deq_wake_slow(hdr, push, n, c); 1 36267 36268
194 36268 }
195  
196 /* Readers reserve BEFORE moving the cursor, so the position cannot be reused
197 * while an earlier reader is descheduled. Writers claim after the cursor CAS. */
198 3 static uint64_t deq_slot_reserve_slow(DeqHandle *__restrict h, uint64_t *ctl_word, uint64_t cursor,
199 uint32_t want) {
200 struct timespec dl;
201 3 int dl_set = 0;
202 3 uint32_t spins = 0;
203 3 uint64_t waiting_ctl = UINT64_MAX;
204 1939773 for (;;) {
205 1939776 ▶ if (want == DEQ_SLOT_FILLED
Branch: 1 branch
BranchTrueFalseTotal
if (want == DEQ_SLOT_FILLED 1939776 0 1939776
206 1939779 ▶ && __atomic_load_n(&h->hdr->cursor, __ATOMIC_ACQUIRE) != cursor) return 0;
Branch: 1 branch
BranchTrueFalseTotal
&& __atomic_load_n(&h->hdr->cursor, __ATOMIC_ACQUIRE) != cursor) return 0; 0 1939776 1939776
207 1939776 uint64_t c = __atomic_load_n(ctl_word, __ATOMIC_ACQUIRE);
208 1939776 ▶ if (c != waiting_ctl) { waiting_ctl = c; dl_set = 0; }
Branch: 1 branch
BranchTrueFalseTotal
if (c != waiting_ctl) { waiting_ctl = c; dl_set = 0; } 3 1939773 1939776
209 1939776 ▶ if (DEQ_SLOT_STATE(c) == want) {
Branch: 1 branch
BranchTrueFalseTotal
if (DEQ_SLOT_STATE(c) == want) { 0 1939776 1939776
210 0 uint64_t nc = c | 1u;
211 0 ▶ if (__atomic_compare_exchange_n(ctl_word, &c, nc,
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_compare_exchange_n(ctl_word, &c, nc, 0 0 0
212 0, __ATOMIC_ACQUIRE, __ATOMIC_RELAXED)) {
213 0 return c;
214 }
215 0 continue;
216 }
217 1939776 deq_spin_pause();
218 1939776 ▶ if ((++spins & 0x3F) == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ((++spins & 0x3F) == 0) { 30309 1909467 1939776
219 30309 ▶ if (!dl_set) { deq_make_deadline((double)DEQ_DRAIN_RECOVERY_SEC, &dl); dl_set = 1; }
Branch: 1 branch
BranchTrueFalseTotal
if (!dl_set) { deq_make_deadline((double)DEQ_DRAIN_RECOVERY_SEC, &dl); dl_set = 1; } 3 30306 30309
220 struct timespec rem;
221 30309 ▶ if (!deq_remaining(&dl, &rem)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!deq_remaining(&dl, &rem)) { 3 30306 30309
222 3 uint64_t nc = ((DEQ_SLOT_GEN(c) + 1) << 2) | (want | 1u);
223 3 ▶ if (__atomic_compare_exchange_n(ctl_word, &c, nc,
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_compare_exchange_n(ctl_word, &c, nc, 3 0 3
224 0, __ATOMIC_ACQ_REL, __ATOMIC_RELAXED)) {
225 3 __atomic_add_fetch(&h->hdr->stat_recoveries, 1, __ATOMIC_RELAXED);
226 3 return nc;
227 }
228 }
229 30306 struct timespec ts = { 0, 100000L };
230 30306 nanosleep(&ts, NULL);
231 }
232 }
233 }
234  
235 /* Reads return FILLED@gen, READING@gen on recovery, or 0 to retry. */
236 36272 static inline uint64_t deq_slot_reserve(DeqHandle *__restrict h, uint64_t *ctl_word, uint64_t cursor,
237 uint32_t want) {
238 36296 ▶ for (uint32_t spins = 0; spins < 8; spins++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t spins = 0; spins < 8; spins++) { 36293 3 36296
239 36293 uint64_t c = __atomic_load_n(ctl_word, __ATOMIC_ACQUIRE);
240 36293 ▶ if (DEQ_SLOT_STATE(c) == want) {
Branch: 1 branch
BranchTrueFalseTotal
if (DEQ_SLOT_STATE(c) == want) { 36269 24 36293
241 36269 uint64_t nc = c | 1u;
242 36269 ▶ if (__atomic_compare_exchange_n(ctl_word, &c, nc,
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_compare_exchange_n(ctl_word, &c, nc, 36269 0 36269
243 0, __ATOMIC_ACQUIRE, __ATOMIC_RELAXED)) {
244 36269 return c;
245 }
246 }
247 24 ▶ if (want == DEQ_SLOT_FILLED
Branch: 1 branch
BranchTrueFalseTotal
if (want == DEQ_SLOT_FILLED 24 0 24
248 24 ▶ && __atomic_load_n(&h->hdr->cursor, __ATOMIC_ACQUIRE) != cursor) return 0;
Branch: 1 branch
BranchTrueFalseTotal
&& __atomic_load_n(&h->hdr->cursor, __ATOMIC_ACQUIRE) != cursor) return 0; 0 24 24
249 }
250 3 return deq_slot_reserve_slow(h, ctl_word, cursor, want);
251 }
252  
253 0 static inline void deq_slot_cancel(uint64_t *ctl_word, uint64_t reserved) {
254 0 uint64_t expected = reserved | DEQ_SLOT_READING;
255 0 uint64_t restored = DEQ_SLOT_STATE(reserved) == DEQ_SLOT_FILLED
256 0 ▶ ? reserved : reserved & ~(uint64_t)DEQ_SLOT_STATE_MASK;
Branch: 1 branch
BranchTrueFalseTotal
? reserved : reserved & ~(uint64_t)DEQ_SLOT_STATE_MASK; 0 0 0
257 0 __atomic_compare_exchange_n(ctl_word, &expected, restored,
258 0, __ATOMIC_RELEASE, __ATOMIC_RELAXED);
259 0 }
260  
261 /* Keep the reservation when only the opposite boundary moved. */
262 36108 static inline int deq_cursor_commit(DeqHandle *__restrict h, uint64_t c, int front) {
263 36108 ▶ uint32_t boundary = front ? DEQ_CURSOR_HEAD(c) : DEQ_CURSOR_TAIL(c);
Branch: 1 branch
BranchTrueFalseTotal
uint32_t boundary = front ? DEQ_CURSOR_HEAD(c) : DEQ_CURSOR_TAIL(c); 36094 14 36108
264 36108 c = __atomic_load_n(&h->hdr->cursor, __ATOMIC_ACQUIRE);
265 36108 ▶ while ((front ? DEQ_CURSOR_HEAD(c) : DEQ_CURSOR_TAIL(c)) == boundary
Branch: 1 branch
BranchTrueFalseTotal
while ((front ? DEQ_CURSOR_HEAD(c) : DEQ_CURSOR_TAIL(c)) == boundary 36094 14 36108
266 36108 ▶ && DEQ_CURSOR_SIZE(c) != 0) {
Branch: 2 branches
BranchTrueFalseTotal
&& DEQ_CURSOR_SIZE(c) != 0) { 36108 0 36108
&& DEQ_CURSOR_SIZE(c) != 0) { 36108 0 36108
267 36108 uint64_t nc = front
268 36094 ? DEQ_CURSOR(boundary + 1u, DEQ_CURSOR_TAIL(c))
269 36108 ▶ : DEQ_CURSOR(DEQ_CURSOR_HEAD(c), boundary - 1u);
Branch: 1 branch
BranchTrueFalseTotal
: DEQ_CURSOR(DEQ_CURSOR_HEAD(c), boundary - 1u); 36094 14 36108
270 36108 ▶ if (__atomic_compare_exchange_n(&h->hdr->cursor, &c, nc,
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_compare_exchange_n(&h->hdr->cursor, &c, nc, 36108 0 36108
271 36108 0, __ATOMIC_ACQ_REL, __ATOMIC_RELAXED)) return 1;
272 }
273 0 return 0;
274 }
275  
276 /* A late publish cannot resurrect a generation replaced by recovery. */
277 164 static inline void deq_slot_publish(uint64_t *ctl_word, uint64_t gen) {
278 164 uint64_t expected = (gen << 2) | DEQ_SLOT_WRITING;
279 164 uint64_t desired = (gen << 2) | DEQ_SLOT_FILLED;
280 164 (void)__atomic_compare_exchange_n(ctl_word, &expected, desired,
281 0, __ATOMIC_RELEASE, __ATOMIC_RELAXED);
282 164 }
283  
284 /* Release slot after read: READING@gen -> EMPTY@gen+1, via CAS not a blind
285 * store (a drain force-recovery may have reused the slot; mirror publish-CAS). */
286 36108 static inline void deq_slot_release(uint64_t *ctl_word, uint64_t gen) {
287 36108 uint64_t expected = (gen << 2) | DEQ_SLOT_READING;
288 36108 uint64_t desired = ((gen + 1) << 2) | DEQ_SLOT_EMPTY;
289 36108 __atomic_compare_exchange_n(ctl_word, &expected, desired,
290 0, __ATOMIC_RELEASE, __ATOMIC_RELAXED);
291 36108 }
292  
293 /* ================================================================
294 * Push back (tail++)
295 * ================================================================ */
296  
297 149 static inline int deq_try_push_back(DeqHandle *__restrict h, const void *val, uint32_t vlen) {
298 149 DeqHeader *hdr = h->hdr;
299 149 uint32_t cap = h->capacity; /* cached-at-attach geometry, not live hdr */
300 0 for (;;) {
301 149 uint64_t c = __atomic_load_n(&hdr->cursor, __ATOMIC_ACQUIRE);
302 149 uint32_t hd = DEQ_CURSOR_HEAD(c), t = DEQ_CURSOR_TAIL(c);
303 293 ▶ if ((uint32_t)(t - hd) >= cap) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if ((uint32_t)(t - hd) >= cap) return 0; 5 144 149
304 144 uint64_t nc = DEQ_CURSOR(hd, t + 1);
305 144 ▶ if (__atomic_compare_exchange_n(&hdr->cursor, &c, nc,
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_compare_exchange_n(&hdr->cursor, &c, nc, 144 0 144
306 1, __ATOMIC_ACQ_REL, __ATOMIC_RELAXED)) {
307 144 uint32_t sz = h->elem_size;
308 144 uint32_t cp = vlen < sz ? vlen : sz;
309 144 uint32_t idx = t & (cap - 1);
310 144 uint64_t *ctl_word = deq_ctl_at(h, idx);
311 144 uint64_t gen = DEQ_SLOT_GEN(deq_slot_reserve(h, ctl_word, 0, DEQ_SLOT_EMPTY));
312 144 deq_copy((h->data + (size_t)idx * sz), val, cp);
313 144 ▶ if (cp < sz) memset((h->data + (size_t)idx * sz) + cp, 0, sz - cp);
Branch: 1 branch
BranchTrueFalseTotal
if (cp < sz) memset((h->data + (size_t)idx * sz) + cp, 0, sz - cp); 0 144 144
314 144 deq_slot_publish(ctl_word, gen);
315 144 __atomic_add_fetch(&hdr->stat_pushes, 1, __ATOMIC_RELAXED);
316 /* StoreLoad: publish our slot/cursor change before reading waiters. */
317 144 deq_after_rmw_fence();
318 144 deq_wake(hdr, 0, 1);
319 144 return 1;
320 }
321 }
322 }
323  
324 /* ================================================================
325 * Push front (head--)
326 * ================================================================ */
327  
328 25 static inline int deq_try_push_front(DeqHandle *__restrict h, const void *val, uint32_t vlen) {
329 25 DeqHeader *hdr = h->hdr;
330 25 uint32_t cap = h->capacity; /* cached-at-attach geometry, not live hdr */
331 0 for (;;) {
332 25 uint64_t c = __atomic_load_n(&hdr->cursor, __ATOMIC_ACQUIRE);
333 25 uint32_t hd = DEQ_CURSOR_HEAD(c), t = DEQ_CURSOR_TAIL(c);
334 45 ▶ if ((uint32_t)(t - hd) >= cap) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if ((uint32_t)(t - hd) >= cap) return 0; 5 20 25
335 20 uint32_t new_hd = hd - 1;
336 20 uint64_t nc = DEQ_CURSOR(new_hd, t);
337 20 ▶ if (__atomic_compare_exchange_n(&hdr->cursor, &c, nc,
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_compare_exchange_n(&hdr->cursor, &c, nc, 20 0 20
338 1, __ATOMIC_ACQ_REL, __ATOMIC_RELAXED)) {
339 20 uint32_t sz = h->elem_size;
340 20 uint32_t cp = vlen < sz ? vlen : sz;
341 20 uint32_t idx = new_hd & (cap - 1);
342 20 uint64_t *ctl_word = deq_ctl_at(h, idx);
343 20 uint64_t gen = DEQ_SLOT_GEN(deq_slot_reserve(h, ctl_word, 0, DEQ_SLOT_EMPTY));
344 20 deq_copy((h->data + (size_t)idx * sz), val, cp);
345 20 ▶ if (cp < sz) memset((h->data + (size_t)idx * sz) + cp, 0, sz - cp);
Branch: 1 branch
BranchTrueFalseTotal
if (cp < sz) memset((h->data + (size_t)idx * sz) + cp, 0, sz - cp); 0 20 20
346 20 deq_slot_publish(ctl_word, gen);
347 20 __atomic_add_fetch(&hdr->stat_pushes, 1, __ATOMIC_RELAXED);
348 /* StoreLoad: publish our slot/cursor change before reading waiters. */
349 20 deq_after_rmw_fence();
350 20 deq_wake(hdr, 0, 1);
351 20 return 1;
352 }
353 }
354 }
355  
356 /* ================================================================
357 * Pop front (head++)
358 * ================================================================ */
359  
360 36088 static inline int deq_try_pop_front(DeqHandle *__restrict h, void *out) {
361 36088 DeqHeader *hdr = h->hdr;
362 36088 uint32_t sz = h->elem_size;
363 36088 uint32_t cap = h->capacity; /* cached-at-attach geometry, not live hdr */
364 1 for (;;) {
365 36089 uint64_t c = __atomic_load_n(&hdr->cursor, __ATOMIC_ACQUIRE);
366 36089 uint32_t hd = DEQ_CURSOR_HEAD(c), t = DEQ_CURSOR_TAIL(c);
367 36089 ▶ if ((uint32_t)(t - hd) == 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if ((uint32_t)(t - hd) == 0) return 0; 8 36081 36089
368 36081 uint32_t idx = hd & (cap - 1);
369 36081 uint64_t *ctl_word = deq_ctl_at(h, idx);
370 36081 uint64_t reserved = deq_slot_reserve(h, ctl_word, c, DEQ_SLOT_FILLED);
371 36081 ▶ if (!reserved) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (!reserved) continue; 0 36081 36081
372 36081 ▶ if (deq_cursor_commit(h, c, 1)) {
Branch: 1 branch
BranchTrueFalseTotal
if (deq_cursor_commit(h, c, 1)) { 36081 0 36081
373 36081 uint64_t gen = DEQ_SLOT_GEN(reserved);
374 36081 ▶ if (DEQ_SLOT_STATE(reserved) == DEQ_SLOT_READING) {
Branch: 1 branch
BranchTrueFalseTotal
if (DEQ_SLOT_STATE(reserved) == DEQ_SLOT_READING) { 1 36080 36081
375 1 deq_slot_release(ctl_word, gen);
376 /* Recovery advanced the cursor and freed space. */
377 1 deq_after_rmw_fence();
378 1 deq_wake(hdr, 1, 1);
379 1 continue;
380 }
381 36080 deq_copy(out, (h->data + (size_t)idx * sz), sz);
382 36080 deq_slot_release(ctl_word, gen);
383 36080 __atomic_add_fetch(&hdr->stat_pops, 1, __ATOMIC_RELAXED);
384 /* StoreLoad: publish our slot/cursor change before reading waiters. */
385 36080 deq_after_rmw_fence();
386 36080 deq_wake(hdr, 1, 1);
387 36080 return 1;
388 }
389 0 deq_slot_cancel(ctl_word, reserved);
390 }
391 }
392  
393 /* ================================================================
394 * Pop back (tail--)
395 * ================================================================ */
396  
397 18 static inline int deq_try_pop_back(DeqHandle *__restrict h, void *out) {
398 18 DeqHeader *hdr = h->hdr;
399 18 uint32_t sz = h->elem_size;
400 18 uint32_t cap = h->capacity; /* cached-at-attach geometry, not live hdr */
401 0 for (;;) {
402 18 uint64_t c = __atomic_load_n(&hdr->cursor, __ATOMIC_ACQUIRE);
403 18 uint32_t hd = DEQ_CURSOR_HEAD(c), t = DEQ_CURSOR_TAIL(c);
404 18 ▶ if ((uint32_t)(t - hd) == 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if ((uint32_t)(t - hd) == 0) return 0; 4 14 18
405 14 uint32_t idx = (t - 1) & (cap - 1);
406 14 uint64_t *ctl_word = deq_ctl_at(h, idx);
407 14 uint64_t reserved = deq_slot_reserve(h, ctl_word, c, DEQ_SLOT_FILLED);
408 14 ▶ if (!reserved) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (!reserved) continue; 0 14 14
409 14 ▶ if (deq_cursor_commit(h, c, 0)) {
Branch: 1 branch
BranchTrueFalseTotal
if (deq_cursor_commit(h, c, 0)) { 14 0 14
410 14 uint64_t gen = DEQ_SLOT_GEN(reserved);
411 14 ▶ if (DEQ_SLOT_STATE(reserved) == DEQ_SLOT_READING) {
Branch: 1 branch
BranchTrueFalseTotal
if (DEQ_SLOT_STATE(reserved) == DEQ_SLOT_READING) { 0 14 14
412 0 deq_slot_release(ctl_word, gen);
413 /* Abandoned slot reclaimed (see deq_try_pop_front). */
414 0 deq_after_rmw_fence();
415 0 deq_wake(hdr, 1, 1);
416 0 continue;
417 }
418 14 deq_copy(out, (h->data + (size_t)idx * sz), sz);
419 14 deq_slot_release(ctl_word, gen);
420 14 __atomic_add_fetch(&hdr->stat_pops, 1, __ATOMIC_RELAXED);
421 /* StoreLoad: publish our slot/cursor change before reading waiters. */
422 14 deq_after_rmw_fence();
423 14 deq_wake(hdr, 1, 1);
424 14 return 1;
425 }
426 0 deq_slot_cancel(ctl_word, reserved);
427 }
428 }
429  
430 /* ================================================================
431 * Blocking push/pop
432 * ================================================================ */
433  
434 2 static int deq_push_wait_slow(DeqHandle *h, const void *val, uint32_t vlen,
435 int front, double timeout) {
436 2 ▶ int (*try_fn)(DeqHandle*, const void*, uint32_t) =
Branch: 1 branch
BranchTrueFalseTotal
int (*try_fn)(DeqHandle*, const void*, uint32_t) = 1 1 2
437 front ? deq_try_push_front : deq_try_push_back;
438 2 DeqHeader *hdr = h->hdr;
439 struct timespec dl, rem;
440 2 int has_dl = (timeout > 0);
441 2 ▶ if (has_dl) deq_make_deadline(timeout, &dl);
Branch: 1 branch
BranchTrueFalseTotal
if (has_dl) deq_make_deadline(timeout, &dl); 2 0 2
442 2 __atomic_add_fetch(&hdr->stat_waits, 1, __ATOMIC_RELAXED);
443  
444 2 uint32_t cap = h->capacity; /* cached-at-attach geometry, not live hdr */
445 0 for (;;) {
446 2 ▶ if (DEQ_WAIT_INTERRUPTED()) {
Branch: 1 branch
BranchTrueFalseTotal
if (DEQ_WAIT_INTERRUPTED()) { 0 2 2
447 0 deq_wake(hdr, 1, 1);
448 0 errno = EINTR;
449 0 return -1;
450 }
451 2 uint32_t wseq = __atomic_load_n(&hdr->push_wake_seq, __ATOMIC_ACQUIRE);
452 2 deq_waiter_enter(&hdr->waiters_push, &hdr->push_wait_hint);
453 /* StoreLoad: publish waiters++ before re-reading the cursor, so a
454 * concurrent waker can't read waiters==0 while we read a stale cursor. */
455 2 __atomic_thread_fence(__ATOMIC_SEQ_CST);
456 2 uint64_t c = __atomic_load_n(&hdr->cursor, __ATOMIC_ACQUIRE);
457 2 ▶ if (DEQ_CURSOR_SIZE(c) >= cap) {
Branch: 1 branch
BranchTrueFalseTotal
if (DEQ_CURSOR_SIZE(c) >= cap) { 2 0 2
458 2 struct timespec *pts = NULL;
459 2 ▶ if (has_dl) {
Branch: 1 branch
BranchTrueFalseTotal
if (has_dl) { 2 0 2
460 2 ▶ if (!deq_remaining(&dl, &rem)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!deq_remaining(&dl, &rem)) { 0 2 2
461 0 deq_waiter_leave(&hdr->waiters_push, &hdr->push_wait_hint);
462 0 __atomic_add_fetch(&hdr->stat_timeouts, 1, __ATOMIC_RELAXED);
463 0 return 0;
464 }
465 2 pts = &rem;
466 }
467 #ifdef DEQ_WAIT_POLL_NS
468 2 struct timespec tick = { 0, DEQ_WAIT_POLL_NS };
469 2 ▶ if (!pts || pts->tv_sec > 0 || pts->tv_nsec > DEQ_WAIT_POLL_NS) pts = &tick;
Branch: 3 branches
BranchTrueFalseTotal
if (!pts || pts->tv_sec > 0 || pts->tv_nsec > DEQ_WAIT_POLL_NS) pts = &tick; 2 0 2
if (!pts || pts->tv_sec > 0 || pts->tv_nsec > DEQ_WAIT_POLL_NS) pts = &tick; 2 0 2
if (!pts || pts->tv_sec > 0 || pts->tv_nsec > DEQ_WAIT_POLL_NS) pts = &tick; 0 2 2
470 #endif
471 2 syscall(SYS_futex, &hdr->push_wake_seq, FUTEX_WAIT, wseq, pts, NULL, 0);
472 }
473 2 deq_waiter_leave(&hdr->waiters_push, &hdr->push_wait_hint);
474 2 ▶ if (DEQ_WAIT_INTERRUPTED()) {
Branch: 1 branch
BranchTrueFalseTotal
if (DEQ_WAIT_INTERRUPTED()) { 0 2 2
475 0 deq_wake(hdr, 1, 1);
476 0 errno = EINTR;
477 0 return -1;
478 }
479 2 ▶ if (try_fn(h, val, vlen)) return 1;
Branch: 1 branch
BranchTrueFalseTotal
if (try_fn(h, val, vlen)) return 1; 0 2 2
480 2 ▶ if (has_dl && !deq_remaining(&dl, &rem)) {
Branch: 2 branches
BranchTrueFalseTotal
if (has_dl && !deq_remaining(&dl, &rem)) { 2 0 2
if (has_dl && !deq_remaining(&dl, &rem)) { 2 0 2
481 2 __atomic_add_fetch(&hdr->stat_timeouts, 1, __ATOMIC_RELAXED);
482 2 return 0;
483 }
484 }
485 }
486  
487 3 static int deq_pop_wait_slow(DeqHandle *h, void *out, int back, double timeout) {
488 3 ▶ int (*try_fn)(DeqHandle*, void*) =
Branch: 1 branch
BranchTrueFalseTotal
int (*try_fn)(DeqHandle*, void*) = 1 2 3
489 back ? deq_try_pop_back : deq_try_pop_front;
490 3 DeqHeader *hdr = h->hdr;
491 struct timespec dl, rem;
492 3 int has_dl = (timeout > 0);
493 3 ▶ if (has_dl) deq_make_deadline(timeout, &dl);
Branch: 1 branch
BranchTrueFalseTotal
if (has_dl) deq_make_deadline(timeout, &dl); 3 0 3
494 3 __atomic_add_fetch(&hdr->stat_waits, 1, __ATOMIC_RELAXED);
495  
496 0 for (;;) {
497 3 ▶ if (DEQ_WAIT_INTERRUPTED()) {
Branch: 1 branch
BranchTrueFalseTotal
if (DEQ_WAIT_INTERRUPTED()) { 0 3 3
498 0 deq_wake(hdr, 0, 1);
499 0 errno = EINTR;
500 0 return -1;
501 }
502 3 uint32_t wseq = __atomic_load_n(&hdr->pop_wake_seq, __ATOMIC_ACQUIRE);
503 3 deq_waiter_enter(&hdr->waiters_pop, &hdr->pop_wait_hint);
504 /* StoreLoad: publish waiters++ before re-reading the cursor, so a
505 * concurrent waker can't read waiters==0 while we read a stale cursor. */
506 3 __atomic_thread_fence(__ATOMIC_SEQ_CST);
507 3 uint64_t c = __atomic_load_n(&hdr->cursor, __ATOMIC_ACQUIRE);
508 3 ▶ if (DEQ_CURSOR_SIZE(c) == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (DEQ_CURSOR_SIZE(c) == 0) { 3 0 3
509 3 struct timespec *pts = NULL;
510 3 ▶ if (has_dl) {
Branch: 1 branch
BranchTrueFalseTotal
if (has_dl) { 3 0 3
511 3 ▶ if (!deq_remaining(&dl, &rem)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!deq_remaining(&dl, &rem)) { 0 3 3
512 0 deq_waiter_leave(&hdr->waiters_pop, &hdr->pop_wait_hint);
513 0 __atomic_add_fetch(&hdr->stat_timeouts, 1, __ATOMIC_RELAXED);
514 0 return 0;
515 }
516 3 pts = &rem;
517 }
518 #ifdef DEQ_WAIT_POLL_NS
519 3 struct timespec tick = { 0, DEQ_WAIT_POLL_NS };
520 3 ▶ if (!pts || pts->tv_sec > 0 || pts->tv_nsec > DEQ_WAIT_POLL_NS) pts = &tick;
Branch: 3 branches
BranchTrueFalseTotal
if (!pts || pts->tv_sec > 0 || pts->tv_nsec > DEQ_WAIT_POLL_NS) pts = &tick; 3 0 3
if (!pts || pts->tv_sec > 0 || pts->tv_nsec > DEQ_WAIT_POLL_NS) pts = &tick; 2 1 3
if (!pts || pts->tv_sec > 0 || pts->tv_nsec > DEQ_WAIT_POLL_NS) pts = &tick; 0 2 2
521 #endif
522 3 syscall(SYS_futex, &hdr->pop_wake_seq, FUTEX_WAIT, wseq, pts, NULL, 0);
523 }
524 3 deq_waiter_leave(&hdr->waiters_pop, &hdr->pop_wait_hint);
525 3 ▶ if (DEQ_WAIT_INTERRUPTED()) {
Branch: 1 branch
BranchTrueFalseTotal
if (DEQ_WAIT_INTERRUPTED()) { 0 3 3
526 0 deq_wake(hdr, 0, 1);
527 0 errno = EINTR;
528 0 return -1;
529 }
530 3 ▶ if (try_fn(h, out)) return 1;
Branch: 1 branch
BranchTrueFalseTotal
if (try_fn(h, out)) return 1; 1 2 3
531 2 ▶ if (has_dl && !deq_remaining(&dl, &rem)) {
Branch: 2 branches
BranchTrueFalseTotal
if (has_dl && !deq_remaining(&dl, &rem)) { 2 0 2
if (has_dl && !deq_remaining(&dl, &rem)) { 2 0 2
532 2 __atomic_add_fetch(&hdr->stat_timeouts, 1, __ATOMIC_RELAXED);
533 2 return 0;
534 }
535 }
536 }
537  
538 2 static inline int deq_push_wait(DeqHandle *h, const void *val, uint32_t vlen,
539 int front, double timeout) {
540 2 ▶ if (front ? deq_try_push_front(h, val, vlen) : deq_try_push_back(h, val, vlen)) return 1;
Branch: 2 branches
BranchTrueFalseTotal
if (front ? deq_try_push_front(h, val, vlen) : deq_try_push_back(h, val, vlen)) return 1; 1 1 2
if (front ? deq_try_push_front(h, val, vlen) : deq_try_push_back(h, val, vlen)) return 1; 0 2 2
541 2 ▶ if (timeout == 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (timeout == 0) return 0; 0 2 2
542 2 return deq_push_wait_slow(h, val, vlen, front, timeout);
543 }
544  
545 3 static inline int deq_pop_wait(DeqHandle *h, void *out, int back, double timeout) {
546 3 ▶ if (back ? deq_try_pop_back(h, out) : deq_try_pop_front(h, out)) return 1;
Branch: 2 branches
BranchTrueFalseTotal
if (back ? deq_try_pop_back(h, out) : deq_try_pop_front(h, out)) return 1; 1 2 3
if (back ? deq_try_pop_back(h, out) : deq_try_pop_front(h, out)) return 1; 0 3 3
547 3 ▶ if (timeout == 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (timeout == 0) return 0; 0 3 3
548 3 return deq_pop_wait_slow(h, out, back, timeout);
549 }
550  
551 /* ================================================================
552 * Create / Open / Close
553 * ================================================================ */
554  
555 #define DEQ_ERR(fmt, ...) do { if (errbuf) snprintf(errbuf, DEQ_ERR_BUFLEN, fmt, ##__VA_ARGS__); } while(0)
556  
557 /* Layout offsets -- data array first, then 8-byte-aligned ctl array. */
558 204 static inline uint64_t deq_ctl_offset(uint32_t elem_size, uint64_t capacity) {
559 204 uint64_t data_end = sizeof(DeqHeader) + capacity * elem_size;
560 204 return (data_end + 7u) & ~(uint64_t)7u;
561 }
562  
563 76 static inline uint64_t deq_total_size(uint32_t elem_size, uint64_t capacity) {
564 76 return deq_ctl_offset(elem_size, capacity) + capacity * sizeof(uint64_t);
565 }
566  
567 62 static inline void deq_init_header(void *base, uint64_t total,
568 uint32_t elem_size, uint32_t variant_id,
569 uint64_t capacity) {
570 62 DeqHeader *hdr = (DeqHeader *)base;
571 62 memset(base, 0, (size_t)total); /* zeroes data + ctl -> all slots EMPTY, gen=0 */
572 62 hdr->version = DEQ_VERSION;
573 62 hdr->elem_size = elem_size;
574 62 hdr->variant_id = variant_id;
575 62 hdr->capacity = capacity;
576 62 hdr->total_size = total;
577 62 hdr->data_off = sizeof(DeqHeader);
578 62 hdr->ctl_off = deq_ctl_offset(elem_size, capacity);
579 62 __atomic_thread_fence(__ATOMIC_SEQ_CST);
580 /* Publish magic LAST, as a release store: it is the commit point, so a
581 creator killed before it leaves magic==0 and never a file mistaken for
582 a valid one. A kill during the field stores leaves one to remove by
583 hand. */
584 62 __atomic_store_n(&hdr->magic, DEQ_MAGIC, __ATOMIC_RELEASE);
585  
586 62 }
587  
588 /* Layout fields are passed in by the caller -- either from a validated
589 * header snapshot or locally computed -- never re-read from the live
590 * mapping, which a hostile peer could rewrite between validation and
591 * here (double-fetch TOCTOU). */
592 66 static inline DeqHandle *deq_setup(void *base, size_t ms, const char *path, int bfd,
593 uint64_t data_off, uint64_t ctl_off,
594 uint32_t elem_size, uint64_t capacity) {
595 66 DeqHandle *h = (DeqHandle *)calloc(1, sizeof(DeqHandle));
596 66 ▶ if (!h) { munmap(base, ms); if (bfd >= 0) close(bfd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (!h) { munmap(base, ms); if (bfd >= 0) close(bfd); return NULL; } 0 66 66
if (!h) { munmap(base, ms); if (bfd >= 0) close(bfd); return NULL; } 0 0 0
597 66 h->hdr = (DeqHeader *)base;
598 66 h->data = (uint8_t *)base + data_off;
599 66 h->ctl = (uint64_t *)((uint8_t *)base + ctl_off);
600 66 h->mmap_size = ms;
601 66 h->elem_size = elem_size;
602 66 h->capacity = (uint32_t)capacity; /* validated <= 2^31 at attach; fixed geometry */
603 66 ▶ h->path = path ? strdup(path) : NULL;
Branch: 1 branch
BranchTrueFalseTotal
h->path = path ? strdup(path) : NULL; 29 37 66
604 66 ▶ if (path && !h->path) {
Branch: 2 branches
BranchTrueFalseTotal
if (path && !h->path) { 29 37 66
if (path && !h->path) { 0 29 29
605 0 munmap(base, ms);
606 0 ▶ if (bfd >= 0) close(bfd);
Branch: 1 branch
BranchTrueFalseTotal
if (bfd >= 0) close(bfd); 0 0 0
607 0 free(h);
608 0 return NULL;
609 }
610 66 h->notify_fd = -1;
611 66 h->backing_fd = bfd;
612 66 return h;
613 }
614  
615 /* Validate a mapped header (shared by deq_create reopen and deq_open_fd). */
616 12 static inline int deq_validate_header(const DeqHeader *hdr, uint64_t file_size,
617 uint32_t expected_variant) {
618 12 ▶ if (hdr->magic != DEQ_MAGIC) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->magic != DEQ_MAGIC) return 0; 6 6 12
619 6 ▶ if (hdr->version != DEQ_VERSION) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->version != DEQ_VERSION) return 0; 0 6 6
620 6 ▶ if (hdr->variant_id != expected_variant) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->variant_id != expected_variant) return 0; 0 6 6
621 6 ▶ if (hdr->elem_size == 0 || hdr->capacity == 0) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (hdr->elem_size == 0 || hdr->capacity == 0) return 0; 6 0 6
if (hdr->elem_size == 0 || hdr->capacity == 0) return 0; 0 6 6
622 6 ▶ if (hdr->capacity > 0x80000000u) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->capacity > 0x80000000u) return 0; 0 6 6
623 6 ▶ if (hdr->capacity & (hdr->capacity - 1)) return 0; /* capacity must be a power of two (slot map is idx % capacity) */
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->capacity & (hdr->capacity - 1)) return 0; /* capacity must be a power of two (slot map is idx % capacity) */ 0 6 6
624 /* Variant-specific elem_size sanity: prevents buffer overflows in the
625 * XS push paths if a corrupted/tampered file claims an impossibly-small
626 * elem_size (e.g. < 4 for a Str variant where push writes a 4-byte
627 * length prefix). */
628 6 ▶ if (expected_variant == DEQ_VAR_INT && hdr->elem_size != sizeof(int64_t))
Branch: 2 branches
BranchTrueFalseTotal
if (expected_variant == DEQ_VAR_INT && hdr->elem_size != sizeof(int64_t)) 4 2 6
if (expected_variant == DEQ_VAR_INT && hdr->elem_size != sizeof(int64_t)) 1 3 4
629 1 return 0;
630 5 ▶ if (expected_variant == DEQ_VAR_STR && hdr->elem_size < sizeof(uint32_t) + 1)
Branch: 2 branches
BranchTrueFalseTotal
if (expected_variant == DEQ_VAR_STR && hdr->elem_size < sizeof(uint32_t) + 1) 2 3 5
if (expected_variant == DEQ_VAR_STR && hdr->elem_size < sizeof(uint32_t) + 1) 1 1 2
631 1 return 0;
632 4 ▶ if (hdr->total_size != file_size) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->total_size != file_size) return 0; 0 4 4
633 4 ▶ if (hdr->data_off != sizeof(DeqHeader)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->data_off != sizeof(DeqHeader)) return 0; 0 4 4
634 4 ▶ if (hdr->ctl_off != deq_ctl_offset(hdr->elem_size, hdr->capacity)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->ctl_off != deq_ctl_offset(hdr->elem_size, hdr->capacity)) return 0; 0 4 4
635 4 ▶ if (hdr->total_size != deq_total_size(hdr->elem_size, hdr->capacity)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->total_size != deq_total_size(hdr->elem_size, hdr->capacity)) return 0; 0 4 4
636 4 return 1;
637 }
638  
639 /* Ring slots map via idx % capacity on a free-running 32-bit index; that tiles the
640 2^32 index space correctly only when capacity divides 2^32, i.e. is a power of two,
641 so a non-power-of-2 request would collide slots across the 2^32 wrap seam. Round up. */
642 72 static inline uint64_t deq_next_pow2(uint64_t n) {
643 72 ▶ if (n <= 1) return 1;
Branch: 1 branch
BranchTrueFalseTotal
if (n <= 1) return 1; 38 34 72
644 34 n--; n |= n >> 1; n |= n >> 2; n |= n >> 4; n |= n >> 8; n |= n >> 16; n |= n >> 32;
645 34 return n + 1;
646 }
647  
648 /* Securely obtain a fd for the path-based backing store. Either create it fresh
649 * (O_CREAT|O_EXCL|O_NOFOLLOW at `mode`, default 0600 = owner-only), or, if it
650 * already exists, attach to it (O_RDWR|O_NOFOLLOW, no O_CREAT). O_EXCL blocks a
651 * pre-seeded or hard-linked file and O_NOFOLLOW a symlink swap, so a local
652 * attacker can no longer redirect or poison the backing store through the path.
653 * Cross-user sharing is opt-in via a wider `mode` (e.g. 0660); the caller still
654 * validates the file's contents. */
655 36 static int deq_secure_open(const char *path, mode_t mode, char *errbuf) {
656 36 ▶ for (int attempt = 0; attempt < 100; attempt++) {
Branch: 1 branch
BranchTrueFalseTotal
for (int attempt = 0; attempt < 100; attempt++) { 36 0 36
657 36 int fd = open(path, O_RDWR|O_CREAT|O_EXCL|O_NOFOLLOW|O_CLOEXEC, mode);
658 36 ▶ if (fd >= 0) { (void)fchmod(fd, mode); return fd; } /* exact mode: umask narrowed the O_EXCL create */
Branch: 1 branch
BranchTrueFalseTotal
if (fd >= 0) { (void)fchmod(fd, mode); return fd; } /* exact mode: umask narrowed the O_EXCL create */ 25 11 36
659 11 ▶ if (errno != EEXIST) { DEQ_ERR("create %s: %s", path, strerror(errno)); return -1; }
Branch: 2 branches
BranchTrueFalseTotal
if (errno != EEXIST) { DEQ_ERR("create %s: %s", path, strerror(errno)); return -1; } 0 11 11
if (errno != EEXIST) { DEQ_ERR("create %s: %s", path, strerror(errno)); return -1; } 0 0 0
660 11 fd = open(path, O_RDWR|O_NOFOLLOW|O_CLOEXEC);
661 11 ▶ if (fd >= 0) return fd;
Branch: 1 branch
BranchTrueFalseTotal
if (fd >= 0) return fd; 11 0 11
662 0 ▶ if (errno == ENOENT) continue; /* creator unlinked between our two opens; retry */
Branch: 1 branch
BranchTrueFalseTotal
if (errno == ENOENT) continue; /* creator unlinked between our two opens; retry */ 0 0 0
663 0 ▶ DEQ_ERR("open %s: %s", path, strerror(errno)); /* ELOOP => symlink rejected */
Branch: 1 branch
BranchTrueFalseTotal
DEQ_ERR("open %s: %s", path, strerror(errno)); /* ELOOP => symlink rejected */ 0 0 0
664 0 return -1;
665 }
666 0 ▶ DEQ_ERR("open %s: create/attach kept racing", path);
Branch: 1 branch
BranchTrueFalseTotal
DEQ_ERR("open %s: create/attach kept racing", path); 0 0 0
667 0 return -1;
668 }
669  
670 /* True iff the whole file is zero -- what an abandoned mid-init
671 creator leaves. Lets recovery re-init only a provably-empty file, never
672 one that merely starts with a zero word. Cold path, so a byte scan is
673 fine. Read, not mapped: a read fault on a tmpfs hole allocates the page. */
674 2 static int deq_file_is_zero(int fd, uint64_t size) {
675 char buf[16384];
676 3 ▶ for (uint64_t off = 0; off < size; ) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint64_t off = 0; off < size; ) { 2 1 3
677 2 ssize_t n = pread(fd, buf, size - off < sizeof buf ? (size_t)(size - off) : sizeof buf, (off_t)off);
678 2 ▶ if (n <= 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (n <= 0) return 0; 0 2 2
679 513 ▶ for (ssize_t i = 0; i < n; i++) if (buf[i]) return 0;
Branch: 2 branches
BranchTrueFalseTotal
for (ssize_t i = 0; i < n; i++) if (buf[i]) return 0; 1 511 512
for (ssize_t i = 0; i < n; i++) if (buf[i]) return 0; 512 1 513
680 1 off += (uint64_t)n;
681 }
682 1 return 1;
683 }
684  
685 /* A sparse segment would SIGBUS at the first write the filesystem cannot back. */
686 27 static int deq_reserve(int fd, uint64_t size) {
687 27 const char *sp = getenv("DATA_DEQUE_SHARED_SPARSE");
688 27 ▶ if (sp && *sp && strcmp(sp, "0")) return 0;
Branch: 3 branches
BranchTrueFalseTotal
if (sp && *sp && strcmp(sp, "0")) return 0; 0 27 27
if (sp && *sp && strcmp(sp, "0")) return 0; 0 0 0
if (sp && *sp && strcmp(sp, "0")) return 0; 0 0 0
689 /* Before Linux 6.11 tmpfs gives up at any pending signal and undoes the allocation, so a
690 * periodic one could keep it from ever completing; SIGSTOP cannot be blocked. */
691 sigset_t all, old;
692 27 sigfillset(&all);
693 27 sigprocmask(SIG_BLOCK, &all, &old);
694 int e;
695 27 ▶ do e = posix_fallocate(fd, 0, (off_t)size); while (e == EINTR);
Branch: 1 branch
BranchTrueFalseTotal
do e = posix_fallocate(fd, 0, (off_t)size); while (e == EINTR); 0 27 27
696 27 sigprocmask(SIG_SETMASK, &old, NULL);
697 27 ▶ if (e == 0 || e == EOPNOTSUPP || e == EINVAL) return 0;
Branch: 3 branches
BranchTrueFalseTotal
if (e == 0 || e == EOPNOTSUPP || e == EINVAL) return 0; 0 27 27
if (e == 0 || e == EOPNOTSUPP || e == EINVAL) return 0; 0 0 0
if (e == 0 || e == EOPNOTSUPP || e == EINVAL) return 0; 0 0 0
698 0 errno = e;
699 0 return -1;
700 }
701  
702 71 static DeqHandle *deq_create(const char *path, uint64_t capacity,
703 uint32_t elem_size, uint32_t variant_id,
704 mode_t mode, char *errbuf) {
705 71 ▶ if (errbuf) errbuf[0] = '\0';
Branch: 1 branch
BranchTrueFalseTotal
if (errbuf) errbuf[0] = '\0'; 71 0 71
706 71 ▶ if (capacity == 0) { DEQ_ERR("capacity must be > 0"); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (capacity == 0) { DEQ_ERR("capacity must be > 0"); return NULL; } 0 71 71
if (capacity == 0) { DEQ_ERR("capacity must be > 0"); return NULL; } 0 0 0
707 71 ▶ if (elem_size == 0) { DEQ_ERR("elem_size must be > 0"); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (elem_size == 0) { DEQ_ERR("elem_size must be > 0"); return NULL; } 0 71 71
if (elem_size == 0) { DEQ_ERR("elem_size must be > 0"); return NULL; } 0 0 0
708 71 capacity = deq_next_pow2(capacity);
709 71 ▶ if (capacity == 0 || capacity > 0x80000000u) {
Branch: 2 branches
BranchTrueFalseTotal
if (capacity == 0 || capacity > 0x80000000u) { 71 0 71
if (capacity == 0 || capacity > 0x80000000u) { 0 71 71
710 0 ▶ DEQ_ERR("capacity must be <= 2^31 (32-bit cursor halves)"); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
DEQ_ERR("capacity must be <= 2^31 (32-bit cursor halves)"); return NULL; 0 0 0
711 }
712  
713 71 uint64_t total = deq_total_size(elem_size, capacity);
714 71 int anonymous = (path == NULL);
715 71 int fd = -1;
716 size_t map_size;
717 void *base;
718  
719 71 ▶ if (anonymous) {
Branch: 1 branch
BranchTrueFalseTotal
if (anonymous) { 35 36 71
720 35 map_size = (size_t)total;
721 35 base = mmap(NULL, map_size, PROT_READ|PROT_WRITE, MAP_SHARED|MAP_ANONYMOUS, -1, 0);
722 35 ▶ if (base == MAP_FAILED) { DEQ_ERR("mmap: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { DEQ_ERR("mmap: %s", strerror(errno)); return NULL; } 0 35 35
if (base == MAP_FAILED) { DEQ_ERR("mmap: %s", strerror(errno)); return NULL; } 0 0 0
723 } else {
724 36 fd = deq_secure_open(path, mode, errbuf);
725 47 ▶ if (fd < 0) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (fd < 0) return NULL; 0 36 36
726 36 ▶ if (flock(fd, LOCK_EX) < 0) { DEQ_ERR("flock: %s", strerror(errno)); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (flock(fd, LOCK_EX) < 0) { DEQ_ERR("flock: %s", strerror(errno)); close(fd); return NULL; } 0 36 36
if (flock(fd, LOCK_EX) < 0) { DEQ_ERR("flock: %s", strerror(errno)); close(fd); return NULL; } 0 0 0
727 struct stat st;
728 36 ▶ if (fstat(fd, &st) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (fstat(fd, &st) < 0) { 0 36 36
729 0 ▶ DEQ_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
DEQ_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; 0 0 0
730 }
731 36 int is_new = (st.st_size == 0);
732 36 ▶ if (!is_new && (uint64_t)st.st_size < sizeof(DeqHeader)) {
Branch: 2 branches
BranchTrueFalseTotal
if (!is_new && (uint64_t)st.st_size < sizeof(DeqHeader)) { 11 25 36
if (!is_new && (uint64_t)st.st_size < sizeof(DeqHeader)) { 0 11 11
733 0 ▶ DEQ_ERR("%s: file too small (%lld)", path, (long long)st.st_size);
Branch: 1 branch
BranchTrueFalseTotal
DEQ_ERR("%s: file too small (%lld)", path, (long long)st.st_size); 0 0 0
734 0 flock(fd, LOCK_UN); close(fd); return NULL;
735 }
736 36 ▶ if (is_new && (st.st_uid != geteuid() || fchmod(fd, mode) < 0)) {
Branch: 3 branches
BranchTrueFalseTotal
if (is_new && (st.st_uid != geteuid() || fchmod(fd, mode) < 0)) { 25 11 36
if (is_new && (st.st_uid != geteuid() || fchmod(fd, mode) < 0)) { 25 0 25
if (is_new && (st.st_uid != geteuid() || fchmod(fd, mode) < 0)) { 0 25 25
737 0 ▶ DEQ_ERR("%s: refusing to initialize file not owned by us", path);
Branch: 1 branch
BranchTrueFalseTotal
DEQ_ERR("%s: refusing to initialize file not owned by us", path); 0 0 0
738 0 flock(fd, LOCK_UN); close(fd); return NULL;
739 }
740 36 ▶ if (is_new && ftruncate(fd, (off_t)total) < 0) {
Branch: 2 branches
BranchTrueFalseTotal
if (is_new && ftruncate(fd, (off_t)total) < 0) { 25 11 36
if (is_new && ftruncate(fd, (off_t)total) < 0) { 0 25 25
741 0 ▶ DEQ_ERR("ftruncate: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
DEQ_ERR("ftruncate: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; 0 0 0
742 }
743 36 ▶ if (is_new && deq_reserve(fd, total) < 0) {
Branch: 2 branches
BranchTrueFalseTotal
if (is_new && deq_reserve(fd, total) < 0) { 25 11 36
if (is_new && deq_reserve(fd, total) < 0) { 0 25 25
744 0 ▶ DEQ_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
DEQ_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno)); 0 0 0
745 0 if (ftruncate(fd, 0) < 0) { /* best effort */ }
746 0 flock(fd, LOCK_UN); close(fd); return NULL;
747 }
748 36 ▶ map_size = is_new ? (size_t)total : (size_t)st.st_size;
Branch: 1 branch
BranchTrueFalseTotal
map_size = is_new ? (size_t)total : (size_t)st.st_size; 11 25 36
749 36 base = mmap(NULL, map_size, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
750 36 ▶ if (base == MAP_FAILED) {
Branch: 1 branch
BranchTrueFalseTotal
if (base == MAP_FAILED) { 0 36 36
751 0 ▶ DEQ_ERR("mmap: %s", strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
DEQ_ERR("mmap: %s", strerror(errno)); 0 0 0
752 0 ▶ if (is_new && ftruncate(fd, 0) < 0) { /* best effort */ }
Branch: 1 branch
BranchTrueFalseTotal
if (is_new && ftruncate(fd, 0) < 0) { /* best effort */ } 0 0 0
753 0 flock(fd, LOCK_UN); close(fd); return NULL;
754 }
755 36 ▶ if (!is_new) {
Branch: 1 branch
BranchTrueFalseTotal
if (!is_new) { 11 25 36
756 DeqHeader snap; /* single fetch: validate + setup use one copy */
757 11 memcpy(&snap, base, sizeof snap);
758 11 ▶ if (!deq_validate_header(&snap, (uint64_t)st.st_size, variant_id)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!deq_validate_header(&snap, (uint64_t)st.st_size, variant_id)) { 8 3 11
759 /* Recover an abandoned mid-init file: a creator killed
760 * between the ftruncate and the header init leaves a
761 * full-size, all-zero (magic==0) file that would brick every
762 * future open of this path. Re-initialize ONLY when it is
763 * exactly our size, still uninitialized, and owned by us;
764 * anything else still errors. Reads snap.magic, the snapshot
765 * already fetched, rather than `base` again -- the same
766 * single-fetch TOCTOU avoidance used above. */
767 8 ▶ if (snap.magic == 0 && (uint64_t)st.st_size == total
Branch: 2 branches
BranchTrueFalseTotal
if (snap.magic == 0 && (uint64_t)st.st_size == total 3 5 8
if (snap.magic == 0 && (uint64_t)st.st_size == total 2 1 3
768 2 ▶ && st.st_uid == geteuid() && deq_file_is_zero(fd, map_size)) {
Branch: 2 branches
BranchTrueFalseTotal
&& st.st_uid == geteuid() && deq_file_is_zero(fd, map_size)) { 2 0 2
&& st.st_uid == geteuid() && deq_file_is_zero(fd, map_size)) { 1 1 2
769 1 ▶ if (fchmod(fd, mode) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (fchmod(fd, mode) < 0) { 0 1 1
770 0 ▶ DEQ_ERR("%s: fchmod: %s", path, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
DEQ_ERR("%s: fchmod: %s", path, strerror(errno)); 0 0 0
771 0 munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
772 }
773 1 ▶ if (deq_reserve(fd, total) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (deq_reserve(fd, total) < 0) { 0 1 1
774 0 ▶ DEQ_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
DEQ_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno)); 0 0 0
775 0 munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
776 }
777 1 deq_init_header(base, total, elem_size, variant_id, capacity);
778 1 flock(fd, LOCK_UN); close(fd);
779 1 return deq_setup(base, map_size, path, -1,
780 sizeof(DeqHeader), deq_ctl_offset(elem_size, capacity),
781 elem_size, capacity);
782 }
783 7 ▶ if (snap.magic == 0 && (uint64_t)st.st_size == total
Branch: 2 branches
BranchTrueFalseTotal
if (snap.magic == 0 && (uint64_t)st.st_size == total 2 5 7
if (snap.magic == 0 && (uint64_t)st.st_size == total 1 1 2
784 1 ▶ && st.st_uid == geteuid()) {
Branch: 1 branch
BranchTrueFalseTotal
&& st.st_uid == geteuid()) { 1 0 1
785 1 ▶ DEQ_ERR("%s: incomplete deque file left by an interrupted create; remove it and retry", path);
Branch: 1 branch
BranchTrueFalseTotal
DEQ_ERR("%s: incomplete deque file left by an interrupted create; remove it and retry", path); 1 0 1
786 1 munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
787 }
788 6 ▶ DEQ_ERR("invalid deque file"); munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
DEQ_ERR("invalid deque file"); munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL; 6 0 6
789 }
790 3 flock(fd, LOCK_UN); close(fd);
791 3 return deq_setup(base, map_size, path, -1,
792 snap.data_off, snap.ctl_off, snap.elem_size, snap.capacity);
793 }
794 }
795 60 deq_init_header(base, total, elem_size, variant_id, capacity);
796 60 ▶ if (fd >= 0) { flock(fd, LOCK_UN); close(fd); }
Branch: 1 branch
BranchTrueFalseTotal
if (fd >= 0) { flock(fd, LOCK_UN); close(fd); } 25 35 60
797 60 return deq_setup(base, map_size, path, -1,
798 sizeof(DeqHeader), deq_ctl_offset(elem_size, capacity),
799 elem_size, capacity);
800 }
801  
802 1 static DeqHandle *deq_create_memfd(const char *name, uint64_t capacity,
803 uint32_t elem_size, uint32_t variant_id,
804 char *errbuf) {
805 1 ▶ if (errbuf) errbuf[0] = '\0';
Branch: 1 branch
BranchTrueFalseTotal
if (errbuf) errbuf[0] = '\0'; 1 0 1
806 1 ▶ if (capacity == 0) { DEQ_ERR("capacity must be > 0"); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (capacity == 0) { DEQ_ERR("capacity must be > 0"); return NULL; } 0 1 1
if (capacity == 0) { DEQ_ERR("capacity must be > 0"); return NULL; } 0 0 0
807 1 ▶ if (elem_size == 0) { DEQ_ERR("elem_size must be > 0"); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (elem_size == 0) { DEQ_ERR("elem_size must be > 0"); return NULL; } 0 1 1
if (elem_size == 0) { DEQ_ERR("elem_size must be > 0"); return NULL; } 0 0 0
808 1 capacity = deq_next_pow2(capacity);
809 1 ▶ if (capacity == 0 || capacity > 0x80000000u) {
Branch: 2 branches
BranchTrueFalseTotal
if (capacity == 0 || capacity > 0x80000000u) { 1 0 1
if (capacity == 0 || capacity > 0x80000000u) { 0 1 1
810 0 ▶ DEQ_ERR("capacity must be <= 2^31 (32-bit cursor halves)"); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
DEQ_ERR("capacity must be <= 2^31 (32-bit cursor halves)"); return NULL; 0 0 0
811 }
812 1 uint64_t total = deq_total_size(elem_size, capacity);
813 1 ▶ int fd = memfd_create(name ? name : "deque", MFD_CLOEXEC | MFD_ALLOW_SEALING);
Branch: 1 branch
BranchTrueFalseTotal
int fd = memfd_create(name ? name : "deque", MFD_CLOEXEC | MFD_ALLOW_SEALING); 1 0 1
814 1 ▶ if (fd < 0) { DEQ_ERR("memfd_create: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fd < 0) { DEQ_ERR("memfd_create: %s", strerror(errno)); return NULL; } 0 1 1
if (fd < 0) { DEQ_ERR("memfd_create: %s", strerror(errno)); return NULL; } 0 0 0
815 1 ▶ if (ftruncate(fd, (off_t)total) < 0) { DEQ_ERR("ftruncate: %s", strerror(errno)); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (ftruncate(fd, (off_t)total) < 0) { DEQ_ERR("ftruncate: %s", strerror(errno)); close(fd); return NULL; } 0 1 1
if (ftruncate(fd, (off_t)total) < 0) { DEQ_ERR("ftruncate: %s", strerror(errno)); close(fd); return NULL; } 0 0 0
816 1 ▶ if (deq_reserve(fd, total) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (deq_reserve(fd, total) < 0) { 0 1 1
817 0 ▶ DEQ_ERR("memfd: cannot reserve %llu bytes: %s", (unsigned long long)total, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
DEQ_ERR("memfd: cannot reserve %llu bytes: %s", (unsigned long long)total, strerror(errno)); 0 0 0
818 0 close(fd); return NULL;
819 }
820 1 (void)fcntl(fd, F_ADD_SEALS, F_SEAL_SHRINK | F_SEAL_GROW);
821 1 void *base = mmap(NULL, (size_t)total, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
822 1 ▶ if (base == MAP_FAILED) { DEQ_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { DEQ_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; } 0 1 1
if (base == MAP_FAILED) { DEQ_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; } 0 0 0
823 1 deq_init_header(base, total, elem_size, variant_id, capacity);
824 1 return deq_setup(base, (size_t)total, NULL, fd,
825 sizeof(DeqHeader), deq_ctl_offset(elem_size, capacity),
826 elem_size, capacity);
827 }
828  
829 2 static DeqHandle *deq_open_fd(int fd, uint32_t variant_id, char *errbuf) {
830 2 ▶ if (errbuf) errbuf[0] = '\0';
Branch: 1 branch
BranchTrueFalseTotal
if (errbuf) errbuf[0] = '\0'; 2 0 2
831 struct stat st;
832 2 ▶ if (fstat(fd, &st) < 0) { DEQ_ERR("fstat: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fstat(fd, &st) < 0) { DEQ_ERR("fstat: %s", strerror(errno)); return NULL; } 0 2 2
if (fstat(fd, &st) < 0) { DEQ_ERR("fstat: %s", strerror(errno)); return NULL; } 0 0 0
833 2 ▶ if ((uint64_t)st.st_size < sizeof(DeqHeader)) { DEQ_ERR("too small"); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if ((uint64_t)st.st_size < sizeof(DeqHeader)) { DEQ_ERR("too small"); return NULL; } 0 2 2
if ((uint64_t)st.st_size < sizeof(DeqHeader)) { DEQ_ERR("too small"); return NULL; } 0 0 0
834 /* before mmap: a creator may truncate the file until it has set magic */
835 uint32_t magic;
836 2 ▶ if (pread(fd, &magic, sizeof magic, offsetof(DeqHeader, magic)) != (ssize_t)sizeof magic || magic != DEQ_MAGIC) {
Branch: 2 branches
BranchTrueFalseTotal
if (pread(fd, &magic, sizeof magic, offsetof(DeqHeader, magic)) != (ssize_t)sizeof magic || magic != DEQ_MAGIC) { 2 0 2
if (pread(fd, &magic, sizeof magic, offsetof(DeqHeader, magic)) != (ssize_t)sizeof magic || magic != DEQ_MAGIC) { 1 1 2
837 1 ▶ DEQ_ERR("invalid deque"); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
DEQ_ERR("invalid deque"); return NULL; 1 0 1
838 }
839 1 size_t ms = (size_t)st.st_size;
840 1 void *base = mmap(NULL, ms, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
841 1 ▶ if (base == MAP_FAILED) { DEQ_ERR("mmap: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { DEQ_ERR("mmap: %s", strerror(errno)); return NULL; } 0 1 1
if (base == MAP_FAILED) { DEQ_ERR("mmap: %s", strerror(errno)); return NULL; } 0 0 0
842 DeqHeader snap; /* single fetch: validate + setup use one copy */
843 1 memcpy(&snap, base, sizeof snap);
844 1 ▶ if (!deq_validate_header(&snap, (uint64_t)st.st_size, variant_id)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!deq_validate_header(&snap, (uint64_t)st.st_size, variant_id)) { 0 1 1
845 0 ▶ DEQ_ERR("invalid deque"); munmap(base, ms); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
DEQ_ERR("invalid deque"); munmap(base, ms); return NULL; 0 0 0
846 }
847 1 int myfd = fcntl(fd, F_DUPFD_CLOEXEC, 0);
848 1 ▶ if (myfd < 0) { DEQ_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (myfd < 0) { DEQ_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; } 0 1 1
if (myfd < 0) { DEQ_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; } 0 0 0
849 1 return deq_setup(base, ms, NULL, myfd,
850 snap.data_off, snap.ctl_off, snap.elem_size, snap.capacity);
851 }
852  
853 66 static void deq_destroy(DeqHandle *h) {
854 66 ▶ if (!h) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!h) return; 0 66 66
855 66 ▶ if (h->notify_fd >= 0) close(h->notify_fd);
Branch: 1 branch
BranchTrueFalseTotal
if (h->notify_fd >= 0) close(h->notify_fd); 2 64 66
856 66 ▶ if (h->backing_fd >= 0) close(h->backing_fd);
Branch: 1 branch
BranchTrueFalseTotal
if (h->backing_fd >= 0) close(h->backing_fd); 2 64 66
857 66 ▶ if (h->hdr) munmap(h->hdr, h->mmap_size);
Branch: 1 branch
BranchTrueFalseTotal
if (h->hdr) munmap(h->hdr, h->mmap_size); 66 0 66
858 66 free(h->path);
859 66 free(h);
860 }
861  
862 /* NOT concurrency-safe -- use drain() for concurrent scenarios */
863 3 static void deq_clear(DeqHandle *h) {
864 3 __atomic_store_n(&h->hdr->cursor, 0, __ATOMIC_RELEASE);
865 /* Reset all slot ctl to {EMPTY, gen=0}. Safe only when no concurrent
866 * push/pop -- which is the documented contract of clear(). */
867 3 memset(h->ctl, 0, (size_t)h->capacity * sizeof(uint64_t));
868 /* clear() frees the entire deque at once -- wake all waiters so they
869 * can re-evaluate state, not just one. */
870 /* StoreLoad: publish our slot/cursor change before reading waiters. */
871 3 __atomic_thread_fence(__ATOMIC_SEQ_CST);
872 3 deq_wake(h->hdr, 1, INT_MAX);
873 /* StoreLoad: publish our slot/cursor change before reading waiters. */
874 3 __atomic_thread_fence(__ATOMIC_SEQ_CST);
875 3 deq_wake(h->hdr, 0, INT_MAX);
876 3 }
877  
878 /* Drain at most the entry size, reserving each slot before advancing head.
879 * Abandoned slots use the same bounded recovery as push/pop. */
880 4 static inline uint32_t deq_drain(DeqHandle *h) {
881 4 DeqHeader *hdr = h->hdr;
882 4 uint32_t cap = h->capacity; /* cached-at-attach geometry, not live hdr */
883 /* Bound the work even if producers keep adding items. */
884 4 uint64_t c0 = __atomic_load_n(&hdr->cursor, __ATOMIC_ACQUIRE);
885 4 uint32_t target = (uint32_t)(DEQ_CURSOR_TAIL(c0) - DEQ_CURSOR_HEAD(c0));
886 4 uint32_t drained = 0;
887 17 ▶ while (drained < target) {
Branch: 1 branch
BranchTrueFalseTotal
while (drained < target) { 13 4 17
888 13 uint64_t c = __atomic_load_n(&hdr->cursor, __ATOMIC_ACQUIRE);
889 13 uint32_t hd = DEQ_CURSOR_HEAD(c), t = DEQ_CURSOR_TAIL(c);
890 13 ▶ if ((uint32_t)(t - hd) == 0) break; /* emptied by a concurrent consumer */
Branch: 1 branch
BranchTrueFalseTotal
if ((uint32_t)(t - hd) == 0) break; /* emptied by a concurrent consumer */ 0 13 13
891 13 uint32_t idx = hd & (cap - 1);
892 13 uint64_t *ctl_word = deq_ctl_at(h, idx);
893 13 uint64_t reserved = deq_slot_reserve(h, ctl_word, c, DEQ_SLOT_FILLED);
894 13 ▶ if (!reserved) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (!reserved) continue; 0 13 13
895 13 ▶ if (!deq_cursor_commit(h, c, 1)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!deq_cursor_commit(h, c, 1)) { 0 13 13
896 0 deq_slot_cancel(ctl_word, reserved);
897 0 continue;
898 }
899 13 deq_slot_release(ctl_word, DEQ_SLOT_GEN(reserved));
900 13 drained++;
901 }
902 4 ▶ if (drained > 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (drained > 0) { 3 1 4
903 /* StoreLoad: publish our slot/cursor changes before reading waiters. */
904 3 __atomic_thread_fence(__ATOMIC_SEQ_CST);
905 3 ▶ deq_wake(hdr, 1, drained < INT_MAX ? (int)drained : INT_MAX);
Branch: 1 branch
BranchTrueFalseTotal
deq_wake(hdr, 1, drained < INT_MAX ? (int)drained : INT_MAX); 3 0 3
906 }
907 4 return drained;
908 }
909  
910 2 static int deq_create_eventfd(DeqHandle *h) {
911 2 ▶ if (h->notify_fd >= 0) return h->notify_fd;
Branch: 1 branch
BranchTrueFalseTotal
if (h->notify_fd >= 0) return h->notify_fd; 0 2 2
912 2 int efd = eventfd(0, EFD_NONBLOCK|EFD_CLOEXEC);
913 2 ▶ if (efd < 0) return -1;
Branch: 1 branch
BranchTrueFalseTotal
if (efd < 0) return -1; 0 2 2
914 2 h->notify_fd = efd; return efd;
915 }
916 2 static int deq_notify(DeqHandle *h) {
917 2 ▶ if (h->notify_fd < 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (h->notify_fd < 0) return 0; 0 2 2
918 2 uint64_t v = 1; return write(h->notify_fd, &v, sizeof(v)) == sizeof(v);
919 }
920 2 static int64_t deq_eventfd_consume(DeqHandle *h) {
921 2 ▶ if (h->notify_fd < 0) return -1;
Branch: 1 branch
BranchTrueFalseTotal
if (h->notify_fd < 0) return -1; 0 2 2
922 2 uint64_t v = 0;
923 2 ▶ if (read(h->notify_fd, &v, sizeof(v)) != sizeof(v)) return -1;
Branch: 1 branch
BranchTrueFalseTotal
if (read(h->notify_fd, &v, sizeof(v)) != sizeof(v)) return -1; 0 2 2
924 2 return (int64_t)v;
925 }
926 1 static int deq_msync(DeqHandle *h) { return msync(h->hdr, h->mmap_size, MS_SYNC); }
927  
928 #endif /* DEQUE_H */
« Shared.xs ↑ Summary