reservoir.h

filter: Statementstmt 71.6% 411 / 574 Branchbran 48.2% 221 / 458 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 61.2% 632 / 1032 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« blib/lib/Data/Reservoir/Shared.pm ↑ Summary Shared.xs »
1 /*
2 * reservoir.h -- Shared-memory reservoir sampler for Linux
3 *
4 * Maintains a uniform random sample of k items drawn from an unbounded stream
5 * (Algorithm R) in fixed memory: each observed item either fills an empty slot
6 * (while the reservoir is not yet full) or, once full, replaces a uniformly
7 * random slot with probability k/i for the i-th item. A shared xorshift64 RNG
8 * lives in the header so concurrent processes sample one consistent reservoir.
9 * A write-preferring futex rwlock with reader-slot dead-process recovery guards
10 * mutation. Items are stored inline, truncated to item_size bytes.
11 *
12 * A reservoir may instead be created in WEIGHTED mode (Efraimidis-Spirakis
13 * A-Res): each item carries a weight and is kept with probability proportional
14 * to it, via a shared min-heap keyed by log(u)/weight over the same items region.
15 *
16 * Layout (uniform): Header -> reader_slots[1024] -> occ -> items[k * (8 + item_size)]
17 * Layout (weighted): Header -> reader_slots[1024] -> occ -> heap[k * 16] -> items[...]
18 */
19  
20 #ifndef RSV_H
21 #define RSV_H
22  
23 #include <stddef.h>
24 #include <stdint.h>
25 #include <stdlib.h>
26 #include <string.h>
27 #include <unistd.h>
28 #include <fcntl.h>
29 #include <errno.h>
30 #include <time.h>
31 #include <limits.h>
32 #include <signal.h>
33 #include <stdio.h>
34 #include <math.h>
35 #include <sys/mman.h>
36 #include <sys/stat.h>
37 #include <sys/file.h>
38 #include <sys/syscall.h>
39 #include <linux/futex.h>
40 #include <pthread.h>
41  
42 #if defined(__BYTE_ORDER__) && __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
43 #error "reservoir.h: requires little-endian architecture"
44 #endif
45  
46  
47 /* ================================================================
48 * Constants
49 * ================================================================ */
50  
51 #define RSV_MAGIC 0x52565352U /* Reservoir */
52 #define RSV_VERSION 2 /* 2: added the occupancy bitmap region (layout change) */
53 #define RSV_WEIGHTED_VERSION 3 /* logarithmic weighted keys */
54 #define RSV_ERR_BUFLEN (PATH_MAX + 256)
55 #ifndef RSV_READER_SLOTS
56 #define RSV_READER_SLOTS 1024 /* max concurrent reader processes for dead-process recovery */
57 #endif
58 /* Occupancy bitmap: one bit per reader slot, set when a process claims a slot and
59 * cleared on clean release. A writer scans these RSV_OCC_WORDS words to visit
60 * only OCCUPIED slots (O(words + live readers)) instead of all RSV_READER_SLOTS. */
61 #define RSV_OCC_WORDS (((RSV_READER_SLOTS) + 63) / 64) /* 16 for 1024 slots */
62 #define RSV_OCC_BYTES ((uint64_t)RSV_OCC_WORDS * 8) /* 128 bytes */
63 #define RSV_MIN_K 1
64 #define RSV_MAX_K 0x40000000ULL /* 2^30 reservoir slots cap */
65 #define RSV_MIN_ITEM 1
66 #define RSV_MAX_ITEM 0x10000ULL /* 64 KiB max bytes per stored item */
67  
68 #define RSV_MODE_UNIFORM 0U /* Algorithm R: uniform sample of the stream */
69 #define RSV_MODE_WEIGHTED 1U /* Efraimidis-Spirakis A-Res: weighted sample */
70  
71 #define RSV_ERR(fmt, ...) do { if (errbuf) snprintf(errbuf, RSV_ERR_BUFLEN, fmt, ##__VA_ARGS__); } while (0)
72  
73 /* ================================================================
74 * Structs
75 * ================================================================ */
76  
77 /* Per-process slot for dead-process recovery. In the reader-slots-only rwlock a
78 * reader's ENTIRE contribution to the shared lock is `rdepth` in its OWN slot --
79 * there is no separate shared reader counter to fall out of sync with it -- so a
80 * dead reader's contribution is exactly this one word, which a draining writer
81 * neutralises by clearing the slot's pid (the scan then ignores the slot). No
82 * orphaned counter can exist, so there is no quiescent force-reset and sustained
83 * readers cannot starve a writer. _rsv1/_rsv2 are kept only to preserve the
84 * 16-byte slot size across the already-released builds. */
85 typedef struct {
86 uint32_t pid; /* 0 = unclaimed */
87 uint32_t rdepth; /* read-locks THIS process currently holds (recursion-safe) */
88 uint32_t _rsv1; /* reserved (was waiters_parked); unused, kept for layout size */
89 uint32_t _rsv2; /* reserved (was writers_parked); unused, kept for layout size */
90 } RsvReaderSlot;
91  
92 /* Weighted (A-Res) min-heap entry: `key` = log(u)/weight, the smallest at the
93 * root so a heavier arrival can evict it. `item` indexes the items region (a
94 * fixed cell that stays put -- only these 16-byte entries move during sift). */
95 typedef struct { double key; uint64_t item; } RsvHeapEnt;
96 _Static_assert(sizeof(RsvHeapEnt) == 16, "RsvHeapEnt must be 16 bytes");
97  
98 struct RsvHeader {
99 uint32_t magic, version; /* 0,4 */
100 uint32_t mode; /* 8 RSV_MODE_UNIFORM | RSV_MODE_WEIGHTED */
101 uint32_t _pad1; /* 12 */
102 uint64_t k; /* 16 reservoir capacity (number of slots) */
103 uint64_t item_size; /* 24 max bytes stored per item */
104 uint64_t capacity; /* 32 == k (family stats parity) */
105 uint64_t stride; /* 40 bytes per slot: 8 (len) + item_size, 8-aligned */
106 uint64_t total_size; /* 48 */
107 uint64_t reader_slots_off; /* 56 */
108 uint64_t slots_off; /* 64 */
109 uint32_t wlock; /* 72 WRITER word ONLY: 0 (free) or WRITER_BIT|pid. NOT a reader count. */
110 uint32_t rwait; /* 76 parked-waiter hint (readers+writers blocked on wlock); over-count-safe */
111 uint32_t drain_seq; /* 80 futex bumped by a reader releasing under a draining writer (wakes it) */
112 uint32_t slotless_rdepth; /* readers holding with no reader-slot (documented residual) */
113 uint64_t stat_ops; /* 88 */
114 uint64_t seen; /* 96 total items observed (mutable, under wrlock) */
115 uint64_t rng_state; /* 104 xorshift64 RNG state (mutable, under wrlock) */
116 uint64_t heap_off; /* 112 weighted A-Res min-heap region (0 in uniform mode) */
117 uint32_t jsift; /* 120 RSV_J_UP/DOWN | hole while a heap sift is in flight, else 0 */
118 uint32_t _pad2; /* 124 */
119 RsvHeapEnt jent; /* 128 entry the in-flight sift will place at its hole */
120 uint8_t _pad[112]; /* 144..255 */
121 };
122 typedef struct RsvHeader RsvHeader;
123  
124 _Static_assert(sizeof(RsvHeader) == 256, "RsvHeader must be 256 bytes");
125  
126 /* ---- Process-local handle ---- */
127  
128 typedef struct RsvHandle {
129 RsvHeader *hdr;
130 RsvReaderSlot *reader_slots; /* RSV_READER_SLOTS entries */
131 uint64_t *occ; /* RSV_OCC_WORDS-word slot-occupancy bitmap (trusted layout offset) */
132 void *base; /* mmap base */
133 uint64_t slots_off; /* validated geometry, cached: never re-read from the peer-writable header */
134 uint64_t k; /* reservoir size (cached) */
135 uint64_t item_size; /* max bytes per item (cached) */
136 uint64_t stride; /* per-slot byte stride (cached) */
137 uint32_t mode; /* RSV_MODE_* sampling mode (cached from validated header) */
138 uint64_t heap_off; /* weighted min-heap region offset (cached), 0 if uniform */
139 size_t mmap_size;
140 char *path; /* backing file path (strdup'd) */
141 char *unlink_path; /* absolute path for relative backing files */
142 int backing_fd; /* memfd or reopened-fd to close on destroy, -1 for file/anon */
143 uint32_t my_slot_idx; /* UINT32_MAX if all slots taken (no recovery for this handle) */
144 uint32_t cached_pid; /* getpid() cached at last slot claim */
145 uint32_t cached_fork_gen; /* rsv_fork_gen value at last slot claim */
146 uint32_t slotless_held; /* read-locks this process holds with no reader-slot */
147 } RsvHandle;
148  
149 /* ================================================================
150 * Futex-based write-preferring read-write lock (reader-slots-only)
151 * with dead-process recovery
152 *
153 * The reader count is NOT stored in a shared counter. It is DISTRIBUTED across
154 * per-process reader slots: each slot's `rdepth` is that process's entire
155 * contribution to the lock. A reader publishes its presence in its own slot and
156 * then re-checks the writer word; a writer publishes the writer word and then
157 * scans every slot until all live readers' rdepth reach 0. Sequentially-
158 * consistent store+load on each side (a Dekker handshake) gives mutual exclusion.
159 *
160 * Because a reader's whole contribution is ONE atomic word owned by ONE process,
161 * a crashed reader is recovered by clearing that one slot (CAS its pid to 0) --
162 * there is no second counter to strand, no orphaned +1, and therefore no
163 * quiescent force-reset. A reader killed anywhere in rdlock/rdunlock leaves at
164 * most `rdepth>0` in its dead slot, which the draining writer clears directly, so
165 * sustained read traffic can never starve a writer. Write-preference is inherent
166 * in the gate (new readers see wlock!=0 and yield), so there is no reader-count
167 * yield hack.
168 * ================================================================ */
169  
170 #define RSV_RWLOCK_SPIN_LIMIT 32
171 #define RSV_LOCK_TIMEOUT_SEC 2 /* FUTEX_WAIT timeout for stale-lock detection / drain re-scan */
172  
173 0 static inline void rsv_rwlock_spin_pause(void) {
174 #if defined(__x86_64__) || defined(__i386__)
175 0 __asm__ volatile("pause" ::: "memory");
176 #elif defined(__aarch64__)
177 __asm__ volatile("yield" ::: "memory");
178 #else
179 __asm__ volatile("" ::: "memory");
180 #endif
181 0 }
182  
183 /* Writer word encoding: WRITER_BIT|pid when write-locked, 0 when free. */
184 #define RSV_RWLOCK_WRITER_BIT 0x80000000U
185 #define RSV_RWLOCK_PID_MASK 0x7FFFFFFFU
186 #define RSV_RWLOCK_WR(pid) (RSV_RWLOCK_WRITER_BIT | ((uint32_t)(pid) & RSV_RWLOCK_PID_MASK))
187  
188 /* A zombie (dead but not yet reaped) still answers kill(pid,0) as alive, so a
189 * process that crashed while holding the lock and lingers unreaped would never
190 * be recovered. Treat /proc/<pid>/stat state 'Z' as dead. Linux-only (as is
191 * this module); if /proc is unreadable we fall back to "alive" (safe: we never
192 * force-recover a possibly-live holder). */
193 0 static inline int rsv_pid_is_zombie(uint32_t pid) {
194 char path[32], buf[256];
195 0 snprintf(path, sizeof(path), "/proc/%u/stat", (unsigned)pid);
196 0 int fd = open(path, O_RDONLY | O_CLOEXEC);
197 0 ▶ if (fd < 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (fd < 0) return 0; 0 0 0
198 0 ssize_t n = read(fd, buf, sizeof(buf) - 1);
199 0 close(fd);
200 0 ▶ if (n <= 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (n <= 0) return 0; 0 0 0
201 0 buf[n] = '\0';
202 /* "pid (comm) state ..."; comm may contain ')', so scan to the last one. */
203 0 char *rp = strrchr(buf, ')');
204 0 ▶ if (!rp || rp + 2 >= buf + n) return 0; /* need ") X" within the bytes read */
Branch: 2 branches
BranchTrueFalseTotal
if (!rp || rp + 2 >= buf + n) return 0; /* need ") X" within the bytes read */ 0 0 0
if (!rp || rp + 2 >= buf + n) return 0; /* need ") X" within the bytes read */ 0 0 0
205 0 ▶ return rp[1] == ' ' && rp[2] == 'Z';
Branch: 2 branches
BranchTrueFalseTotal
return rp[1] == ' ' && rp[2] == 'Z'; 0 0 0
return rp[1] == ' ' && rp[2] == 'Z'; 0 0 0
206 }
207 /* 1 if alive or unknown, 0 if definitely dead. Cannot detect PID reuse: a
208 * recycled PID reports "alive" and the slot is not reclaimed until that
209 * process exits. See "Crash Safety" in the POD. */
210 0 static inline int rsv_pid_alive(uint32_t pid) {
211 0 ▶ if (pid == 0) return 0; /* no owner recorded, treat as dead */
Branch: 1 branch
BranchTrueFalseTotal
if (pid == 0) return 0; /* no owner recorded, treat as dead */ 0 0 0
212 0 ▶ if (kill((pid_t)pid, 0) == -1 && errno == ESRCH) return 0; /* definitely dead */
Branch: 2 branches
BranchTrueFalseTotal
if (kill((pid_t)pid, 0) == -1 && errno == ESRCH) return 0; /* definitely dead */ 0 0 0
if (kill((pid_t)pid, 0) == -1 && errno == ESRCH) return 0; /* definitely dead */ 0 0 0
213 0 return !rsv_pid_is_zombie(pid); /* kill() also succeeds for a zombie -> treat as dead */
214 }
215  
216 /* Force-recover a stale WRITE lock left by a dead writer (held or mid-drain).
217 * CAS to OUR pid to hold the lock while fixing shared state, then release.
218 * Using our pid (not a bare WRITER_BIT sentinel) means a subsequent recovering
219 * process can detect and re-recover if we crash mid-recovery. */
220 static void rsv_journal_replay(RsvHandle *h);
221 0 static inline void rsv_recover_stale_lock(RsvHandle *h, uint32_t observed_wlock) {
222 0 RsvHeader *hdr = h->hdr;
223 0 uint32_t mypid = RSV_RWLOCK_WR((uint32_t)getpid());
224 0 ▶ if (!__atomic_compare_exchange_n(&hdr->wlock, &observed_wlock,
Branch: 1 branch
BranchTrueFalseTotal
if (!__atomic_compare_exchange_n(&hdr->wlock, &observed_wlock, 0 0 0
225 mypid, 0, __ATOMIC_ACQUIRE, __ATOMIC_RELAXED))
226 0 return;
227 /* A journal is only set past the writer's reader drain, so no reader holds while we replay it. */
228 0 rsv_journal_replay(h);
229 0 __atomic_store_n(&hdr->wlock, 0, __ATOMIC_RELEASE);
230 0 ▶ if (__atomic_load_n(&hdr->rwait, __ATOMIC_RELAXED) > 0)
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&hdr->rwait, __ATOMIC_RELAXED) > 0) 0 0 0
231 0 syscall(SYS_futex, &hdr->wlock, FUTEX_WAKE, INT_MAX, NULL, NULL, 0);
232 }
233  
234 static const struct timespec rsv_lock_timeout = { RSV_LOCK_TIMEOUT_SEC, 0 };
235  
236 /* Process-global fork-generation counter. Incremented in the pthread_atfork
237 * child callback so every open handle detects a fork transition on the next
238 * lock call without paying a getpid() syscall on the hot path. */
239 static uint32_t rsv_fork_gen = 1;
240 static pthread_once_t rsv_atfork_once = PTHREAD_ONCE_INIT;
241 0 static void rsv_on_fork_child(void) {
242 0 __atomic_add_fetch(&rsv_fork_gen, 1, __ATOMIC_RELAXED);
243 0 }
244 4 static void rsv_atfork_init(void) {
245 4 pthread_atfork(NULL, NULL, rsv_on_fork_child);
246 4 }
247  
248 /* Occupancy bitmap: set a slot's bit when it is claimed, clear it on clean
249 * release. SEQ_CST so a set bit is ordered before the slot's rdepth can go
250 * non-zero (bit set in claim, which precedes any rdlock), letting a writer's
251 * SEQ_CST bitmap scan never miss a slot a committed reader holds. */
252 3043 static inline void rsv_occ_set(RsvHandle *h, uint32_t s) {
253 3043 __atomic_fetch_or(&h->occ[s >> 6], (uint64_t)1 << (s & 63), __ATOMIC_SEQ_CST);
254 3043 }
255 3043 static inline void rsv_occ_clear(RsvHandle *h, uint32_t s) {
256 3043 __atomic_fetch_and(&h->occ[s >> 6], ~((uint64_t)1 << (s & 63)), __ATOMIC_SEQ_CST);
257 3043 }
258  
259 /* Ensure this process owns a reader slot. Called from the lock helpers so
260 * that fork()'d children pick up their own slot lazily instead of sharing
261 * the parent's. Hot-path is a single relaxed load + compare; only on a
262 * fork-generation mismatch do we touch getpid() and scan slots. */
263 381313 static inline void rsv_claim_reader_slot(RsvHandle *h) {
264 381313 uint32_t cur_gen = __atomic_load_n(&rsv_fork_gen, __ATOMIC_RELAXED);
265 381313 ▶ if (__builtin_expect(cur_gen == h->cached_fork_gen && h->my_slot_idx != UINT32_MAX, 1))
Branch: 2 branches
BranchTrueFalseTotal
if (__builtin_expect(cur_gen == h->cached_fork_gen && h->my_slot_idx != UINT32_MAX, 1)) 378270 3043 381313
if (__builtin_expect(cur_gen == h->cached_fork_gen && h->my_slot_idx != UINT32_MAX, 1)) 378270 0 378270
266 378270 return;
267 /* Cold path -- register the atfork hook once per process, then claim. */
268 3043 pthread_once(&rsv_atfork_once, rsv_atfork_init);
269 /* Re-read after pthread_once: rsv_on_fork_child may have bumped it. */
270 3043 cur_gen = __atomic_load_n(&rsv_fork_gen, __ATOMIC_RELAXED);
271 3043 uint32_t now_pid = (uint32_t)getpid();
272 3043 h->cached_pid = now_pid;
273 3043 ▶ if (cur_gen != h->cached_fork_gen) h->slotless_held = 0; /* fork: child holds none of the parent's slotless read locks */
Branch: 1 branch
BranchTrueFalseTotal
if (cur_gen != h->cached_fork_gen) h->slotless_held = 0; /* fork: child holds none of the parent's slotless read locks */ 3043 0 3043
274 3043 h->cached_fork_gen = cur_gen;
275 3043 h->my_slot_idx = UINT32_MAX;
276 3043 uint32_t start = now_pid % RSV_READER_SLOTS;
277 /* Pass 1: take a free slot. */
278 3044 ▶ for (uint32_t i = 0; i < RSV_READER_SLOTS; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t i = 0; i < RSV_READER_SLOTS; i++) { 3044 0 3044
279 3044 uint32_t s = (start + i) % RSV_READER_SLOTS;
280 3044 uint32_t expected = 0;
281 3044 ▶ if (__atomic_compare_exchange_n(&h->reader_slots[s].pid,
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_compare_exchange_n(&h->reader_slots[s].pid, 3043 1 3044
282 &expected, now_pid, 0,
283 __ATOMIC_ACQUIRE, __ATOMIC_RELAXED)) {
284 /* Fresh owner holds no read locks yet; clear any stale rdepth left by
285 * a dead predecessor (its contribution is dropped as we take over). */
286 3043 __atomic_store_n(&h->reader_slots[s].rdepth, 0, __ATOMIC_RELAXED);
287 3043 rsv_occ_set(h, s); /* mark occupied BEFORE any rdlock can bump rdepth */
288 3043 h->my_slot_idx = s;
289 3043 return;
290 }
291 }
292 /* Pass 2: no free slot -- reclaim one whose owner is dead. Safe to take even
293 * if its rdepth>0: clearing pid drops the dead reader's entire contribution
294 * (a writer scan ignores rdepth when pid==0) and we reset rdepth to 0 as we
295 * claim it. */
296 0 ▶ for (uint32_t i = 0; i < RSV_READER_SLOTS; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t i = 0; i < RSV_READER_SLOTS; i++) { 0 0 0
297 0 uint32_t dpid = __atomic_load_n(&h->reader_slots[i].pid, __ATOMIC_ACQUIRE);
298 0 ▶ if (dpid == 0 || dpid == now_pid || rsv_pid_alive(dpid)) continue;
Branch: 3 branches
BranchTrueFalseTotal
if (dpid == 0 || dpid == now_pid || rsv_pid_alive(dpid)) continue; 0 0 0
if (dpid == 0 || dpid == now_pid || rsv_pid_alive(dpid)) continue; 0 0 0
if (dpid == 0 || dpid == now_pid || rsv_pid_alive(dpid)) continue; 0 0 0
299 0 uint32_t expected = dpid;
300 0 ▶ if (__atomic_compare_exchange_n(&h->reader_slots[i].pid, &expected, now_pid, 0,
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_compare_exchange_n(&h->reader_slots[i].pid, &expected, now_pid, 0, 0 0 0
301 __ATOMIC_ACQUIRE, __ATOMIC_RELAXED)) {
302 0 __atomic_store_n(&h->reader_slots[i].rdepth, 0, __ATOMIC_RELAXED);
303 0 rsv_occ_set(h, i);
304 0 h->my_slot_idx = i;
305 0 return;
306 }
307 }
308 /* Table full -- leave my_slot_idx = UINT32_MAX so this handle takes the
309 * slotless path (lock still works; recovery of THIS reader's death is the
310 * documented slotless limitation). */
311 }
312  
313 /* Inspect the writer word after a futex-wait timeout. If a dead writer holds
314 * it, force-recover. Dead READERS need no action here: only a writer that owns
315 * wlock drains readers, and it clears dead readers inline in its own scan. */
316 0 static inline void rsv_recover_after_timeout(RsvHandle *h) {
317 0 uint32_t val = __atomic_load_n(&h->hdr->wlock, __ATOMIC_RELAXED);
318 0 ▶ if (val >= RSV_RWLOCK_WRITER_BIT) {
Branch: 1 branch
BranchTrueFalseTotal
if (val >= RSV_RWLOCK_WRITER_BIT) { 0 0 0
319 0 uint32_t pid = val & RSV_RWLOCK_PID_MASK;
320 0 ▶ if (!rsv_pid_alive(pid))
Branch: 1 branch
BranchTrueFalseTotal
if (!rsv_pid_alive(pid)) 0 0 0
321 0 rsv_recover_stale_lock(h, val);
322 }
323 0 }
324  
325 /* Bump/drop the parked-waiter hint. Both readers (blocked at the gate) and
326 * writers (blocked acquiring wlock) wait on the wlock futex and use this, so
327 * wrunlock/recover know whether a FUTEX_WAKE is worth a syscall. A waiter
328 * SIGKILLed while parked leaves rwait over-counted -> at most a spurious wake
329 * (harmless); it can never under-count, so no wakeup is lost. */
330 0 static inline void rsv_park(RsvHandle *h) {
331 0 __atomic_add_fetch(&h->hdr->rwait, 1, __ATOMIC_RELAXED);
332 0 }
333 0 static inline void rsv_unpark(RsvHandle *h) {
334 0 __atomic_sub_fetch(&h->hdr->rwait, 1, __ATOMIC_RELAXED);
335 0 }
336  
337 /* Publish (inc) / retract (dec) this reader's presence -- its ENTIRE
338 * contribution to the lock. A slotted reader uses its slot's rdepth; a reader
339 * that could not claim a slot uses the global slotless_rdepth. inc() is SEQ_CST
340 * so the wlock re-check that follows it in rdlock forms a Dekker handshake with
341 * the writer's SEQ_CST wlock-store + rdepth-scan. leave() peels slotless first
342 * so a slot claimed mid-hold cannot misattribute the decrement. */
343 54076 static inline void rsv_rdepth_inc(RsvHandle *h) {
344 54076 ▶ if (h->my_slot_idx != UINT32_MAX) {
Branch: 1 branch
BranchTrueFalseTotal
if (h->my_slot_idx != UINT32_MAX) { 54076 0 54076
345 54076 __atomic_add_fetch(&h->reader_slots[h->my_slot_idx].rdepth, 1, __ATOMIC_SEQ_CST);
346 } else {
347 0 __atomic_add_fetch(&h->hdr->slotless_rdepth, 1, __ATOMIC_SEQ_CST);
348 0 h->slotless_held++;
349 }
350 54076 }
351 54076 static inline void rsv_rdepth_dec(RsvHandle *h) {
352 54076 ▶ if (h->slotless_held > 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (h->slotless_held > 0) { 0 54076 54076
353 0 h->slotless_held--;
354 0 __atomic_sub_fetch(&h->hdr->slotless_rdepth, 1, __ATOMIC_RELEASE);
355 54076 ▶ } else if (h->my_slot_idx != UINT32_MAX) {
Branch: 1 branch
BranchTrueFalseTotal
} else if (h->my_slot_idx != UINT32_MAX) { 54076 0 54076
356 54076 __atomic_sub_fetch(&h->reader_slots[h->my_slot_idx].rdepth, 1, __ATOMIC_RELEASE);
357 }
358 54076 }
359  
360 /* Wake a writer that may be draining readers (it waits on drain_seq). Called
361 * after every rdepth decrement so a released read lock lets the writer re-scan
362 * promptly instead of waiting out its timeout. */
363 54076 static inline void rsv_reader_wake_drain(RsvHandle *h) {
364 54076 ▶ if (__atomic_load_n(&h->hdr->wlock, __ATOMIC_ACQUIRE) != 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&h->hdr->wlock, __ATOMIC_ACQUIRE) != 0) { 0 54076 54076
365 0 __atomic_add_fetch(&h->hdr->drain_seq, 1, __ATOMIC_RELEASE);
366 0 syscall(SYS_futex, &h->hdr->drain_seq, FUTEX_WAKE, 1, NULL, NULL, 0);
367 }
368 54076 }
369  
370 54076 static inline void rsv_rwlock_rdlock(RsvHandle *h) {
371 54076 rsv_claim_reader_slot(h);
372 54076 RsvHeader *hdr = h->hdr;
373 54076 for (int spin = 0; ; spin++) {
374 54076 uint32_t cur = __atomic_load_n(&hdr->wlock, __ATOMIC_ACQUIRE);
375 54076 ▶ if (cur == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (cur == 0) { 54076 0 54076
376 /* Optimistically take the read: publish rdepth, then re-check wlock.
377 * SEQ_CST inc + SEQ_CST load vs the writer's SEQ_CST wlock CAS +
378 * SEQ_CST rdepth scan: by the single total order of SEQ_CST ops the
379 * two sides cannot both miss each other, so we never hold
380 * concurrently with a writer. */
381 54076 rsv_rdepth_inc(h);
382 54076 ▶ if (__atomic_load_n(&hdr->wlock, __ATOMIC_SEQ_CST) == 0)
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&hdr->wlock, __ATOMIC_SEQ_CST) == 0) 54076 0 54076
383 54076 return; /* no writer after our publish -> we hold the read lock */
384 /* A writer appeared during our publish -- yield to it (write-preferring). */
385 0 rsv_rdepth_dec(h);
386 0 rsv_reader_wake_drain(h); /* let the draining writer see rdepth drop */
387 0 spin = 0;
388 0 continue;
389 }
390 /* wlock != 0: a writer holds or is acquiring. Recover if it is dead. */
391 0 if (cur >= RSV_RWLOCK_WRITER_BIT &&
392 0 !rsv_pid_alive(cur & RSV_RWLOCK_PID_MASK)) {
393 0 rsv_recover_stale_lock(h, cur);
394 0 spin = 0;
395 0 continue;
396 }
397 0 ▶ if (__builtin_expect(spin < RSV_RWLOCK_SPIN_LIMIT, 1)) {
Branch: 1 branch
BranchTrueFalseTotal
if (__builtin_expect(spin < RSV_RWLOCK_SPIN_LIMIT, 1)) { 0 0 0
398 0 rsv_rwlock_spin_pause();
399 0 continue;
400 }
401 0 rsv_park(h);
402 0 cur = __atomic_load_n(&hdr->wlock, __ATOMIC_RELAXED);
403 0 ▶ if (cur != 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (cur != 0) { 0 0 0
404 0 long rc = syscall(SYS_futex, &hdr->wlock, FUTEX_WAIT, cur,
405 &rsv_lock_timeout, NULL, 0);
406 0 ▶ if (rc == -1 && errno == ETIMEDOUT) {
Branch: 2 branches
BranchTrueFalseTotal
if (rc == -1 && errno == ETIMEDOUT) { 0 0 0
if (rc == -1 && errno == ETIMEDOUT) { 0 0 0
407 0 rsv_unpark(h);
408 0 rsv_recover_after_timeout(h);
409 0 spin = 0;
410 0 continue;
411 }
412 }
413 0 rsv_unpark(h);
414 0 spin = 0;
415 }
416 }
417  
418 54076 static inline void rsv_rwlock_rdunlock(RsvHandle *h) {
419 54076 rsv_rdepth_dec(h); /* RELEASE: drop our entire contribution */
420 54076 rsv_reader_wake_drain(h); /* if a writer is draining, wake it to re-scan */
421 54076 }
422  
423 327237 static inline void rsv_rwlock_wrlock(RsvHandle *h) {
424 327237 rsv_claim_reader_slot(h); /* refresh cached_pid across fork */
425 327237 RsvHeader *hdr = h->hdr;
426 /* Encode PID in the wlock word itself (0x80000000 | pid) to eliminate any
427 * crash window between acquiring the lock and storing the owner. */
428 327237 uint32_t mypid = RSV_RWLOCK_WR(h->cached_pid);
429 /* Phase 1: acquire the writer word (mutual exclusion among writers). */
430 327237 for (int spin = 0; ; spin++) {
431 327237 uint32_t expected = 0;
432 327237 ▶ if (__atomic_compare_exchange_n(&hdr->wlock, &expected, mypid,
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_compare_exchange_n(&hdr->wlock, &expected, mypid, 327237 0 327237
433 0, __ATOMIC_SEQ_CST, __ATOMIC_RELAXED))
434 327237 break;
435 /* Contended: expected now holds the current wlock value. */
436 0 if (expected >= RSV_RWLOCK_WRITER_BIT &&
437 0 !rsv_pid_alive(expected & RSV_RWLOCK_PID_MASK)) {
438 0 rsv_recover_stale_lock(h, expected);
439 0 spin = 0;
440 0 continue;
441 }
442 0 ▶ if (__builtin_expect(spin < RSV_RWLOCK_SPIN_LIMIT, 1)) {
Branch: 1 branch
BranchTrueFalseTotal
if (__builtin_expect(spin < RSV_RWLOCK_SPIN_LIMIT, 1)) { 0 0 0
443 0 rsv_rwlock_spin_pause();
444 0 continue;
445 }
446 0 rsv_park(h);
447 0 uint32_t cur = __atomic_load_n(&hdr->wlock, __ATOMIC_RELAXED);
448 0 ▶ if (cur != 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (cur != 0) { 0 0 0
449 0 long rc = syscall(SYS_futex, &hdr->wlock, FUTEX_WAIT, cur,
450 &rsv_lock_timeout, NULL, 0);
451 0 ▶ if (rc == -1 && errno == ETIMEDOUT) {
Branch: 2 branches
BranchTrueFalseTotal
if (rc == -1 && errno == ETIMEDOUT) { 0 0 0
if (rc == -1 && errno == ETIMEDOUT) { 0 0 0
452 0 rsv_unpark(h);
453 0 rsv_recover_after_timeout(h);
454 0 spin = 0;
455 0 continue;
456 }
457 }
458 0 rsv_unpark(h);
459 0 spin = 0;
460 }
461 /* Phase 2: we own wlock, so no NEW reader can join (they see wlock!=0 and
462 * yield). Drain the readers that were already holding when we won the CAS.
463 * The SEQ_CST CAS above + the SEQ_CST rdepth loads below are the writer side
464 * of the Dekker handshake. */
465 0 for (;;) {
466 327237 uint32_t v = __atomic_load_n(&hdr->drain_seq, __ATOMIC_ACQUIRE); /* snapshot BEFORE scan */
467 327237 int busy = 0;
468 /* Visit only OCCUPIED slots via the occupancy bitmap (SEQ_CST: a committed
469 * reader's bit -- set in claim, before its rdepth++ -- is ordered before
470 * this scan, so no held slot is skipped). O(RSV_OCC_WORDS + live readers)
471 * instead of O(RSV_READER_SLOTS). */
472 5563029 ▶ for (uint32_t w = 0; w < RSV_OCC_WORDS; w++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t w = 0; w < RSV_OCC_WORDS; w++) { 5235792 327237 5563029
473 5235792 uint64_t word = __atomic_load_n(&h->occ[w], __ATOMIC_SEQ_CST);
474 5563029 ▶ while (word) {
Branch: 1 branch
BranchTrueFalseTotal
while (word) { 327237 5235792 5563029
475 327237 uint32_t i = (w << 6) + (uint32_t)__builtin_ctzll(word);
476 327237 word &= word - 1; /* consume this bit (local copy) */
477 327237 uint32_t rd = __atomic_load_n(&h->reader_slots[i].rdepth, __ATOMIC_SEQ_CST);
478 327237 ▶ if (rd == 0) continue; /* occupied but not read-locking now */
Branch: 1 branch
BranchTrueFalseTotal
if (rd == 0) continue; /* occupied but not read-locking now */ 327237 0 327237
479 0 uint32_t pid = __atomic_load_n(&h->reader_slots[i].pid, __ATOMIC_ACQUIRE);
480 0 ▶ if (pid == 0) continue; /* stale rdepth on a freed slot */
Branch: 1 branch
BranchTrueFalseTotal
if (pid == 0) continue; /* stale rdepth on a freed slot */ 0 0 0
481 0 ▶ if (!rsv_pid_alive(pid)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!rsv_pid_alive(pid)) { 0 0 0
482 /* Dead reader: drop its pid so the slot no longer counts. Leave
483 * the occ bit set (harmless -- a later scan hits pid==0 and skips,
484 * a re-claim re-sets it) to avoid racing a concurrent claimant. */
485 0 uint32_t ep = pid;
486 0 __atomic_compare_exchange_n(&h->reader_slots[i].pid, &ep, 0,
487 0, __ATOMIC_ACQ_REL, __ATOMIC_RELAXED);
488 0 continue;
489 }
490 0 busy = 1; /* live reader still holding */
491 }
492 }
493 /* A live slotless reader keeps us waiting; a crashed slotless reader that
494 * cannot be attributed to a pid is the documented slotless limitation. */
495 327237 ▶ if (__atomic_load_n(&hdr->slotless_rdepth, __ATOMIC_SEQ_CST) != 0)
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&hdr->slotless_rdepth, __ATOMIC_SEQ_CST) != 0) 0 327237 327237
496 0 busy = 1;
497 327237 ▶ if (!busy)
Branch: 1 branch
BranchTrueFalseTotal
if (!busy) 327237 0 327237
498 327237 return; /* exclusive: wlock held + every rdepth 0 */
499 /* Wait for a reader to release (drain_seq bump) or time out to re-scan
500 * (which reclaims any newly-dead slotted reader). */
501 0 syscall(SYS_futex, &hdr->drain_seq, FUTEX_WAIT, v, &rsv_lock_timeout, NULL, 0);
502 }
503 }
504  
505 327237 static inline void rsv_rwlock_wrunlock(RsvHandle *h) {
506 327237 RsvHeader *hdr = h->hdr;
507 327237 __atomic_store_n(&hdr->wlock, 0, __ATOMIC_RELEASE);
508 327237 ▶ if (__atomic_load_n(&hdr->rwait, __ATOMIC_RELAXED) > 0)
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&hdr->rwait, __ATOMIC_RELAXED) > 0) 0 327237 327237
509 0 syscall(SYS_futex, &hdr->wlock, FUTEX_WAKE, INT_MAX, NULL, NULL, 0);
510 327237 }
511  
512 /* ================================================================
513 * Layout math + create / open / destroy
514 *
515 * Layout: Header -> reader_slots[1024] -> slots[k*(8+item_size)]
516 * ================================================================ */
517  
518 /* Single source of truth for the mmap region layout offsets:
519 * Header -> reader_slots[] -> occ bitmap -> slots. */
520 typedef struct { uint64_t reader_slots, occ, slots; } RsvLayout;
521  
522 12225 static inline RsvLayout rsv_layout(void) {
523 RsvLayout L;
524 12225 L.reader_slots = sizeof(RsvHeader);
525 12225 L.occ = L.reader_slots + (uint64_t)RSV_READER_SLOTS * sizeof(RsvReaderSlot);
526 12225 L.slots = L.occ + RSV_OCC_BYTES;
527 12225 L.slots = (L.slots + 7) & ~(uint64_t)7; /* 8-byte align the slots array */
528 12225 return L;
529 }
530  
531 /* bytes per slot: an 8-byte length followed by item_size data bytes, 8-aligned */
532 9158 static inline uint64_t rsv_stride(uint64_t item_size) {
533 9158 return (8 + item_size + 7) & ~(uint64_t)7;
534 }
535  
536 /* Weighted mode inserts a k-entry min-heap between the reader slots and the
537 * items region; uniform mode has no heap. These are the single source of truth
538 * for the region offsets, used by both init and validate (never trust a stored
539 * derived field -- always re-derive from k + mode). */
540 3048 static inline uint64_t rsv_heap_region_off(uint32_t mode) {
541 3048 ▶ return (mode == RSV_MODE_WEIGHTED) ? rsv_layout().slots : 0;
Branch: 1 branch
BranchTrueFalseTotal
return (mode == RSV_MODE_WEIGHTED) ? rsv_layout().slots : 0; 23 3025 3048
542 }
543 6106 static inline uint64_t rsv_items_off(uint64_t k, uint32_t mode) {
544 6106 RsvLayout L = rsv_layout();
545 6106 ▶ if (mode == RSV_MODE_WEIGHTED) {
Branch: 1 branch
BranchTrueFalseTotal
if (mode == RSV_MODE_WEIGHTED) { 48 6058 6106
546 48 uint64_t after_heap = L.slots + k * sizeof(RsvHeapEnt);
547 48 return (after_heap + 7) & ~(uint64_t)7; /* 8-align the items array */
548 }
549 6058 return L.slots;
550 }
551 3058 static inline uint64_t rsv_total_size(uint64_t k, uint64_t item_size, uint32_t mode) {
552 3058 return rsv_items_off(k, mode) + k * rsv_stride(item_size);
553 }
554  
555 3042 static inline void rsv_init_header(void *base, uint64_t k, uint64_t item_size, uint32_t mode, uint64_t total) {
556 3042 RsvLayout L = rsv_layout();
557 3042 RsvHeader *hdr = (RsvHeader *)base;
558 /* Zero the header + reader-slot region (lock-recovery state); the slots array
559 relies on the fresh mapping being OS zero-filled (all lengths 0 = empty). */
560 3042 memset(base, 0, (size_t)L.slots);
561 3042 ▶ hdr->version = mode == RSV_MODE_WEIGHTED ? RSV_WEIGHTED_VERSION : RSV_VERSION;
Branch: 1 branch
BranchTrueFalseTotal
hdr->version = mode == RSV_MODE_WEIGHTED ? RSV_WEIGHTED_VERSION : RSV_VERSION; 21 3021 3042
562 3042 hdr->mode = mode;
563 3042 hdr->k = k;
564 3042 hdr->item_size = item_size;
565 3042 hdr->capacity = k;
566 3042 hdr->stride = rsv_stride(item_size);
567 3042 hdr->total_size = total;
568 3042 hdr->reader_slots_off = L.reader_slots;
569 3042 hdr->heap_off = rsv_heap_region_off(mode);
570 3042 hdr->slots_off = rsv_items_off(k, mode);
571 3042 hdr->seen = 0;
572 /* seed the shared RNG from process + monotonic-clock entropy (never zero) */
573 {
574 3042 struct timespec ts; clock_gettime(CLOCK_MONOTONIC, &ts);
575 3042 uint64_t s = ((uint64_t)getpid() << 32) ^ (uint64_t)ts.tv_nsec ^ ((uint64_t)ts.tv_sec << 20);
576 3042 s ^= 0x9E3779B97F4A7C15ULL;
577 3042 ▶ hdr->rng_state = s ? s : 0x9E3779B97F4A7C15ULL;
Branch: 1 branch
BranchTrueFalseTotal
hdr->rng_state = s ? s : 0x9E3779B97F4A7C15ULL; 3042 0 3042
578 }
579 /* Publish magic LAST, as a release store: it is the commit point, so a
580 creator killed before it leaves magic==0 and never a file mistaken for
581 a valid one. A kill during the field stores leaves one to remove by
582 hand. */
583 3042 __atomic_store_n(&hdr->magic, RSV_MAGIC, __ATOMIC_RELEASE);
584 3042 __atomic_thread_fence(__ATOMIC_SEQ_CST);
585 3042 }
586  
587 267669 static inline uint8_t *rsv_slots(RsvHandle *h) {
588 267669 return (uint8_t *)((char *)h->base + h->slots_off);
589 }
590  
591 /* Layer B trusted bound: number of whole slots guaranteed within the real
592 * mapping. Derived from the process-local mmap_size and the SAME slots_off /
593 * stride rsv_slots() uses, so a peer that corrupts hdr->k / stride / slots_off
594 * after attach-time validation can never drive an access outside the mapping. */
595 395954 static inline uint64_t rsv_slots_max(RsvHandle *h) {
596 395954 uint64_t off = h->slots_off;
597 395954 uint64_t stride = h->stride; /* cached at attach, not the peer-writable header */
598 395954 ▶ if (off >= h->mmap_size || stride == 0) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (off >= h->mmap_size || stride == 0) return 0; 395954 0 395954
if (off >= h->mmap_size || stride == 0) return 0; 0 395954 395954
599 395954 return (h->mmap_size - off) / stride;
600 }
601  
602 3048 static inline RsvHandle *rsv_setup(void *base, size_t map_size,
603 const char *path, int backing_fd, char *errbuf) {
604 3048 RsvHeader *hdr = (RsvHeader *)base;
605 3048 RsvHandle *h = (RsvHandle *)calloc(1, sizeof(RsvHandle));
606 3048 ▶ if (!h) {
Branch: 1 branch
BranchTrueFalseTotal
if (!h) { 0 3048 3048
607 0 munmap(base, map_size);
608 0 ▶ if (backing_fd >= 0) close(backing_fd);
Branch: 1 branch
BranchTrueFalseTotal
if (backing_fd >= 0) close(backing_fd); 0 0 0
609 0 return NULL;
610 }
611 3048 h->hdr = hdr;
612 3048 h->base = base;
613 3048 h->reader_slots = (RsvReaderSlot *)((uint8_t *)base + sizeof(RsvHeader)); /* trusted layout, not the peer-writable header offset */
614 3048 h->occ = (uint64_t *)((uint8_t *)base + rsv_layout().occ); /* trusted layout offset */
615 /* Cache the geometry from the validated header; the ops use these, never the
616 peer-writable hdr->* fields, so a later corruption cannot change a stride /
617 item_size / count out from under a bounds check. */
618 3048 h->slots_off = hdr->slots_off;
619 3048 h->k = hdr->k;
620 3048 h->item_size = hdr->item_size;
621 3048 h->stride = hdr->stride;
622 3048 h->mode = hdr->mode;
623 3048 h->heap_off = hdr->heap_off;
624 3048 h->mmap_size = map_size;
625 /* Layer B: if the mapping cannot even hold k slots the header lied about its
626 size; clamp k to what actually fits (stride is validated 8+item_size). */
627 3048 ▶ if (h->stride) {
Branch: 1 branch
BranchTrueFalseTotal
if (h->stride) { 3048 0 3048
628 3048 ▶ uint64_t fit = (map_size > h->slots_off) ? (map_size - h->slots_off) / h->stride : 0;
Branch: 1 branch
BranchTrueFalseTotal
uint64_t fit = (map_size > h->slots_off) ? (map_size - h->slots_off) / h->stride : 0; 3048 0 3048
629 3048 ▶ if (h->k > fit) h->k = fit;
Branch: 1 branch
BranchTrueFalseTotal
if (h->k > fit) h->k = fit; 0 3048 3048
630 }
631 3048 ▶ h->path = path ? strdup(path) : NULL;
Branch: 1 branch
BranchTrueFalseTotal
h->path = path ? strdup(path) : NULL; 13 3035 3048
632 3048 ▶ if (path && h->path && path[0] != '/') {
Branch: 3 branches
BranchTrueFalseTotal
if (path && h->path && path[0] != '/') { 13 3035 3048
if (path && h->path && path[0] != '/') { 13 0 13
if (path && h->path && path[0] != '/') { 3 10 13
633 3 char *cwd = getcwd(NULL, 0);
634 3 ▶ if (cwd) {
Branch: 1 branch
BranchTrueFalseTotal
if (cwd) { 3 0 3
635 3 size_t len = strlen(cwd) + strlen(path) + 2;
636 3 h->unlink_path = (char *)malloc(len);
637 3 ▶ if (h->unlink_path) snprintf(h->unlink_path, len, "%s/%s", cwd, path);
Branch: 1 branch
BranchTrueFalseTotal
if (h->unlink_path) snprintf(h->unlink_path, len, "%s/%s", cwd, path); 3 0 3
638 3 free(cwd);
639 }
640 }
641 3048 ▶ if (path && (!h->path || (path[0] != '/' && !h->unlink_path))) {
Branch: 4 branches
BranchTrueFalseTotal
if (path && (!h->path || (path[0] != '/' && !h->unlink_path))) { 13 3035 3048
if (path && (!h->path || (path[0] != '/' && !h->unlink_path))) { 13 0 13
if (path && (!h->path || (path[0] != '/' && !h->unlink_path))) { 3 10 13
if (path && (!h->path || (path[0] != '/' && !h->unlink_path))) { 0 3 3
642 0 ▶ RSV_ERR("backing path: %s", strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
RSV_ERR("backing path: %s", strerror(errno)); 0 0 0
643 0 free(h->unlink_path);
644 0 free(h->path);
645 0 free(h);
646 0 munmap(base, map_size);
647 0 ▶ if (backing_fd >= 0) close(backing_fd);
Branch: 1 branch
BranchTrueFalseTotal
if (backing_fd >= 0) close(backing_fd); 0 0 0
648 0 return NULL;
649 }
650 3048 h->backing_fd = backing_fd;
651 3048 h->my_slot_idx = UINT32_MAX;
652 3048 return h;
653 }
654  
655 /* Validate a mapped header (shared by rsv_create reopen and rsv_open_fd). */
656 13 static inline int rsv_validate_header(const RsvHeader *hdr, uint64_t file_size) {
657 13 ▶ if (hdr->magic != RSV_MAGIC) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->magic != RSV_MAGIC) return 0; 4 9 13
658 9 ▶ if (hdr->mode != RSV_MODE_UNIFORM && hdr->mode != RSV_MODE_WEIGHTED) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (hdr->mode != RSV_MODE_UNIFORM && hdr->mode != RSV_MODE_WEIGHTED) return 0; 5 4 9
if (hdr->mode != RSV_MODE_UNIFORM && hdr->mode != RSV_MODE_WEIGHTED) return 0; 0 5 5
659 9 ▶ if (hdr->version != (hdr->mode == RSV_MODE_WEIGHTED ? RSV_WEIGHTED_VERSION : RSV_VERSION)) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (hdr->version != (hdr->mode == RSV_MODE_WEIGHTED ? RSV_WEIGHTED_VERSION : RSV_VERSION)) return 0; 5 4 9
if (hdr->version != (hdr->mode == RSV_MODE_WEIGHTED ? RSV_WEIGHTED_VERSION : RSV_VERSION)) return 0; 3 6 9
660 6 ▶ if (hdr->k < RSV_MIN_K || hdr->k > RSV_MAX_K) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (hdr->k < RSV_MIN_K || hdr->k > RSV_MAX_K) return 0; 6 0 6
if (hdr->k < RSV_MIN_K || hdr->k > RSV_MAX_K) return 0; 0 6 6
661 6 ▶ if (hdr->item_size < RSV_MIN_ITEM || hdr->item_size > RSV_MAX_ITEM) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (hdr->item_size < RSV_MIN_ITEM || hdr->item_size > RSV_MAX_ITEM) return 0; 6 0 6
if (hdr->item_size < RSV_MIN_ITEM || hdr->item_size > RSV_MAX_ITEM) return 0; 0 6 6
662 6 ▶ if (hdr->capacity != hdr->k) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->capacity != hdr->k) return 0; 0 6 6
663 6 ▶ if (hdr->stride != rsv_stride(hdr->item_size)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->stride != rsv_stride(hdr->item_size)) return 0; 0 6 6
664 6 ▶ if (hdr->heap_off != rsv_heap_region_off(hdr->mode)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->heap_off != rsv_heap_region_off(hdr->mode)) return 0; 0 6 6
665 6 ▶ if (hdr->slots_off != rsv_items_off(hdr->k, hdr->mode)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->slots_off != rsv_items_off(hdr->k, hdr->mode)) return 0; 0 6 6
666 6 ▶ if (hdr->total_size != file_size) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->total_size != file_size) return 0; 0 6 6
667 6 ▶ if (hdr->total_size != rsv_total_size(hdr->k, hdr->item_size, hdr->mode)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->total_size != rsv_total_size(hdr->k, hdr->item_size, hdr->mode)) return 0; 0 6 6
668 6 RsvLayout L = rsv_layout();
669 6 ▶ if (hdr->reader_slots_off != L.reader_slots) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->reader_slots_off != L.reader_slots) return 0; 0 6 6
670 6 return 1;
671 }
672  
673 /* validate constructor args (k reservoir size, item_size max bytes per item) */
674 3053 static int rsv_validate_args(uint64_t k, uint64_t item_size, uint32_t mode, char *errbuf) {
675 3053 ▶ if (errbuf) errbuf[0] = '\0';
Branch: 1 branch
BranchTrueFalseTotal
if (errbuf) errbuf[0] = '\0'; 3053 0 3053
676 3053 ▶ if (k < RSV_MIN_K || k > RSV_MAX_K) { RSV_ERR("reservoir size must be between 1 and 2^30"); return 0; }
Branch: 3 branches
BranchTrueFalseTotal
if (k < RSV_MIN_K || k > RSV_MAX_K) { RSV_ERR("reservoir size must be between 1 and 2^30"); return 0; } 3053 0 3053
if (k < RSV_MIN_K || k > RSV_MAX_K) { RSV_ERR("reservoir size must be between 1 and 2^30"); return 0; } 0 3053 3053
if (k < RSV_MIN_K || k > RSV_MAX_K) { RSV_ERR("reservoir size must be between 1 and 2^30"); return 0; } 0 0 0
677 3053 ▶ if (item_size < RSV_MIN_ITEM || item_size > RSV_MAX_ITEM) { RSV_ERR("item_size must be between 1 and 65536"); return 0; }
Branch: 3 branches
BranchTrueFalseTotal
if (item_size < RSV_MIN_ITEM || item_size > RSV_MAX_ITEM) { RSV_ERR("item_size must be between 1 and 65536"); return 0; } 3052 1 3053
if (item_size < RSV_MIN_ITEM || item_size > RSV_MAX_ITEM) { RSV_ERR("item_size must be between 1 and 65536"); return 0; } 0 3052 3052
if (item_size < RSV_MIN_ITEM || item_size > RSV_MAX_ITEM) { RSV_ERR("item_size must be between 1 and 65536"); return 0; } 1 0 1
678 3052 ▶ if (rsv_stride(item_size) > (UINT64_MAX / 4) / k) { RSV_ERR("reservoir_size * item_size too large"); return 0; }
Branch: 2 branches
BranchTrueFalseTotal
if (rsv_stride(item_size) > (UINT64_MAX / 4) / k) { RSV_ERR("reservoir_size * item_size too large"); return 0; } 0 3052 3052
if (rsv_stride(item_size) > (UINT64_MAX / 4) / k) { RSV_ERR("reservoir_size * item_size too large"); return 0; } 0 0 0
679 3052 ▶ if (mode == RSV_MODE_WEIGHTED && sizeof(RsvHeapEnt) > (UINT64_MAX / 4) / k) { RSV_ERR("reservoir_size too large for the weighted heap"); return 0; }
Branch: 3 branches
BranchTrueFalseTotal
if (mode == RSV_MODE_WEIGHTED && sizeof(RsvHeapEnt) > (UINT64_MAX / 4) / k) { RSV_ERR("reservoir_size too large for the weighted heap"); return 0; } 23 3029 3052
if (mode == RSV_MODE_WEIGHTED && sizeof(RsvHeapEnt) > (UINT64_MAX / 4) / k) { RSV_ERR("reservoir_size too large for the weighted heap"); return 0; } 0 23 23
if (mode == RSV_MODE_WEIGHTED && sizeof(RsvHeapEnt) > (UINT64_MAX / 4) / k) { RSV_ERR("reservoir_size too large for the weighted heap"); return 0; } 0 0 0
680 3052 return 1;
681 }
682  
683 /* Securely obtain a fd for a path-backed segment: create it exclusively
684 * (O_CREAT|O_EXCL|O_NOFOLLOW at `mode`, default 0600 = owner-only), or, if it
685 * already exists, attach to it (O_RDWR|O_NOFOLLOW, no O_CREAT). O_EXCL blocks a
686 * pre-seeded or hard-linked file and O_NOFOLLOW a symlink swap, so a local
687 * attacker can no longer redirect or poison the backing store through the path.
688 * Cross-user sharing is opt-in via a wider `mode` (e.g. 0660); the caller still
689 * validates the file's contents via rsv_validate_header. */
690 19 static int rsv_secure_open(const char *path, mode_t mode, char *errbuf) {
691 19 ▶ for (int attempt = 0; attempt < 100; attempt++) {
Branch: 1 branch
BranchTrueFalseTotal
for (int attempt = 0; attempt < 100; attempt++) { 19 0 19
692 19 int fd = open(path, O_RDWR|O_CREAT|O_EXCL|O_NOFOLLOW|O_CLOEXEC, mode);
693 19 ▶ 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 */ 8 11 19
694 11 ▶ if (errno != EEXIST) { RSV_ERR("create %s: %s", path, strerror(errno)); return -1; }
Branch: 2 branches
BranchTrueFalseTotal
if (errno != EEXIST) { RSV_ERR("create %s: %s", path, strerror(errno)); return -1; } 0 11 11
if (errno != EEXIST) { RSV_ERR("create %s: %s", path, strerror(errno)); return -1; } 0 0 0
695 11 fd = open(path, O_RDWR|O_NOFOLLOW|O_CLOEXEC);
696 11 ▶ if (fd >= 0) return fd;
Branch: 1 branch
BranchTrueFalseTotal
if (fd >= 0) return fd; 11 0 11
697 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
698 0 ▶ RSV_ERR("open %s: %s", path, strerror(errno)); /* ELOOP => symlink rejected */
Branch: 1 branch
BranchTrueFalseTotal
RSV_ERR("open %s: %s", path, strerror(errno)); /* ELOOP => symlink rejected */ 0 0 0
699 0 return -1;
700 }
701 0 ▶ RSV_ERR("open %s: create/attach kept racing", path);
Branch: 1 branch
BranchTrueFalseTotal
RSV_ERR("open %s: create/attach kept racing", path); 0 0 0
702 0 return -1;
703 }
704  
705 /* True iff the whole file is zero -- what an abandoned mid-init
706 creator leaves. Lets recovery re-init only a provably-empty file, never
707 one that merely starts with a zero word. Cold path, so a byte scan is
708 fine. Read, not mapped: a read fault on a tmpfs hole allocates the page. */
709 2 static int rsv_file_is_zero(int fd, uint64_t size) {
710 char buf[16384];
711 5 ▶ for (uint64_t off = 0; off < size; ) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint64_t off = 0; off < size; ) { 4 1 5
712 4 ssize_t n = pread(fd, buf, size - off < sizeof buf ? (size_t)(size - off) : sizeof buf, (off_t)off);
713 4 ▶ if (n <= 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (n <= 0) return 0; 0 4 4
714 34019 ▶ 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 34015 34016
for (ssize_t i = 0; i < n; i++) if (buf[i]) return 0; 34016 3 34019
715 3 off += (uint64_t)n;
716 }
717 1 return 1;
718 }
719  
720 /* Opt-in (DATA_RESERVOIR_SHARED_SPARSE=0): reserving commits memory this module otherwise fills lazily. */
721 11 static int rsv_reserve(int fd, uint64_t size) {
722 11 const char *sp = getenv("DATA_RESERVOIR_SHARED_SPARSE");
723 11 ▶ if (!sp || strcmp(sp, "0")) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (!sp || strcmp(sp, "0")) return 0; 0 11 11
if (!sp || strcmp(sp, "0")) return 0; 0 0 0
724 /* Before Linux 6.11 tmpfs gives up at any pending signal and undoes the allocation, so a
725 * periodic one could keep it from ever completing; SIGSTOP cannot be blocked. */
726 sigset_t all, old;
727 0 sigfillset(&all);
728 0 sigprocmask(SIG_BLOCK, &all, &old);
729 int e;
730 0 ▶ 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 0 0
731 0 sigprocmask(SIG_SETMASK, &old, NULL);
732 0 ▶ if (e == 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (e == 0) return 0; 0 0 0
733 0 errno = e;
734 0 return -1;
735 }
736  
737 3051 static RsvHandle *rsv_create(const char *path, uint64_t k, uint64_t item_size, uint32_t weighted, mode_t mode, char *errbuf) {
738 3051 ▶ if (!rsv_validate_args(k, item_size, weighted, errbuf)) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!rsv_validate_args(k, item_size, weighted, errbuf)) return NULL; 1 3050 3051
739  
740 3050 uint64_t total = rsv_total_size(k, item_size, weighted);
741 3050 int anonymous = (path == NULL);
742 3050 int fd = -1;
743 size_t map_size;
744 void *base;
745  
746 3050 ▶ if (anonymous) {
Branch: 1 branch
BranchTrueFalseTotal
if (anonymous) { 3031 19 3050
747 3031 map_size = (size_t)total;
748 3031 base = mmap(NULL, map_size, PROT_READ|PROT_WRITE, MAP_SHARED|MAP_ANONYMOUS, -1, 0);
749 3031 ▶ if (base == MAP_FAILED) { RSV_ERR("mmap: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { RSV_ERR("mmap: %s", strerror(errno)); return NULL; } 0 3031 3031
if (base == MAP_FAILED) { RSV_ERR("mmap: %s", strerror(errno)); return NULL; } 0 0 0
750 } else {
751 19 fd = rsv_secure_open(path, mode, errbuf);
752 30 ▶ if (fd < 0) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (fd < 0) return NULL; 0 19 19
753 19 ▶ if (flock(fd, LOCK_EX) < 0) { RSV_ERR("flock: %s", strerror(errno)); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (flock(fd, LOCK_EX) < 0) { RSV_ERR("flock: %s", strerror(errno)); close(fd); return NULL; } 0 19 19
if (flock(fd, LOCK_EX) < 0) { RSV_ERR("flock: %s", strerror(errno)); close(fd); return NULL; } 0 0 0
754 struct stat st;
755 19 ▶ if (fstat(fd, &st) < 0) { RSV_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fstat(fd, &st) < 0) { RSV_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; } 0 19 19
if (fstat(fd, &st) < 0) { RSV_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; } 0 0 0
756 19 int is_new = (st.st_size == 0);
757 19 ▶ if (!is_new && (uint64_t)st.st_size < sizeof(RsvHeader)) {
Branch: 2 branches
BranchTrueFalseTotal
if (!is_new && (uint64_t)st.st_size < sizeof(RsvHeader)) { 11 8 19
if (!is_new && (uint64_t)st.st_size < sizeof(RsvHeader)) { 1 10 11
758 1 ▶ RSV_ERR("%s: file too small (%lld)", path, (long long)st.st_size);
Branch: 1 branch
BranchTrueFalseTotal
RSV_ERR("%s: file too small (%lld)", path, (long long)st.st_size); 1 0 1
759 1 flock(fd, LOCK_UN); close(fd); return NULL;
760 }
761 18 ▶ 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)) { 8 10 18
if (is_new && (st.st_uid != geteuid() || fchmod(fd, mode) < 0)) { 8 0 8
if (is_new && (st.st_uid != geteuid() || fchmod(fd, mode) < 0)) { 0 8 8
762 0 ▶ RSV_ERR("%s: refusing to initialize file not owned by us", path);
Branch: 1 branch
BranchTrueFalseTotal
RSV_ERR("%s: refusing to initialize file not owned by us", path); 0 0 0
763 0 flock(fd, LOCK_UN); close(fd); return NULL;
764 }
765 18 ▶ if (is_new && ftruncate(fd, (off_t)total) < 0) {
Branch: 2 branches
BranchTrueFalseTotal
if (is_new && ftruncate(fd, (off_t)total) < 0) { 8 10 18
if (is_new && ftruncate(fd, (off_t)total) < 0) { 0 8 8
766 0 ▶ RSV_ERR("ftruncate: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
RSV_ERR("ftruncate: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; 0 0 0
767 }
768 18 ▶ if (is_new && rsv_reserve(fd, total) < 0) {
Branch: 2 branches
BranchTrueFalseTotal
if (is_new && rsv_reserve(fd, total) < 0) { 8 10 18
if (is_new && rsv_reserve(fd, total) < 0) { 0 8 8
769 0 ▶ RSV_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
RSV_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno)); 0 0 0
770 0 if (ftruncate(fd, 0) < 0) { /* best effort */ }
771 0 flock(fd, LOCK_UN); close(fd); return NULL;
772 }
773 18 ▶ 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; 10 8 18
774 18 base = mmap(NULL, map_size, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
775 18 ▶ if (base == MAP_FAILED) {
Branch: 1 branch
BranchTrueFalseTotal
if (base == MAP_FAILED) { 0 18 18
776 0 ▶ RSV_ERR("mmap: %s", strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
RSV_ERR("mmap: %s", strerror(errno)); 0 0 0
777 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
778 0 flock(fd, LOCK_UN); close(fd); return NULL;
779 }
780 18 ▶ if (!is_new) {
Branch: 1 branch
BranchTrueFalseTotal
if (!is_new) { 10 8 18
781 10 ▶ if (!rsv_validate_header((RsvHeader *)base, (uint64_t)st.st_size)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!rsv_validate_header((RsvHeader *)base, (uint64_t)st.st_size)) { 6 4 10
782 /* Recover an abandoned mid-init file: a creator killed
783 * between the ftruncate and the header init leaves a
784 * full-size, all-zero (magic==0) file that would brick every
785 * future open of this path. Re-initialize ONLY when it is
786 * exactly our size, still uninitialized, and owned by us;
787 * anything else still errors. */
788 6 ▶ if (((RsvHeader *)base)->magic == 0 && (uint64_t)st.st_size == total
Branch: 2 branches
BranchTrueFalseTotal
if (((RsvHeader *)base)->magic == 0 && (uint64_t)st.st_size == total 3 3 6
if (((RsvHeader *)base)->magic == 0 && (uint64_t)st.st_size == total 2 1 3
789 2 ▶ && st.st_uid == geteuid() && rsv_file_is_zero(fd, map_size)) {
Branch: 2 branches
BranchTrueFalseTotal
&& st.st_uid == geteuid() && rsv_file_is_zero(fd, map_size)) { 2 0 2
&& st.st_uid == geteuid() && rsv_file_is_zero(fd, map_size)) { 1 1 2
790 1 ▶ if (fchmod(fd, mode) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (fchmod(fd, mode) < 0) { 0 1 1
791 0 ▶ RSV_ERR("%s: fchmod: %s", path, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
RSV_ERR("%s: fchmod: %s", path, strerror(errno)); 0 0 0
792 0 munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
793 }
794 1 ▶ if (rsv_reserve(fd, total) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (rsv_reserve(fd, total) < 0) { 0 1 1
795 0 ▶ RSV_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
RSV_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno)); 0 0 0
796 0 munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
797 }
798 1 rsv_init_header(base, k, item_size, weighted, total);
799 1 flock(fd, LOCK_UN); close(fd);
800 1 return rsv_setup(base, map_size, path, -1, errbuf);
801 }
802 5 ▶ if (((RsvHeader *)base)->magic == 0 && (uint64_t)st.st_size == total
Branch: 2 branches
BranchTrueFalseTotal
if (((RsvHeader *)base)->magic == 0 && (uint64_t)st.st_size == total 2 3 5
if (((RsvHeader *)base)->magic == 0 && (uint64_t)st.st_size == total 1 1 2
803 1 ▶ && st.st_uid == geteuid()) {
Branch: 1 branch
BranchTrueFalseTotal
&& st.st_uid == geteuid()) { 1 0 1
804 1 ▶ RSV_ERR("%s: incomplete reservoir file left by an interrupted create; remove it and retry", path);
Branch: 1 branch
BranchTrueFalseTotal
RSV_ERR("%s: incomplete reservoir file left by an interrupted create; remove it and retry", path); 1 0 1
805 1 munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
806 }
807 4 ▶ RSV_ERR("invalid reservoir file"); munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
RSV_ERR("invalid reservoir file"); munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL; 4 0 4
808 }
809 4 flock(fd, LOCK_UN); close(fd);
810 4 return rsv_setup(base, map_size, path, -1, errbuf);
811 }
812 }
813 3039 rsv_init_header(base, k, item_size, weighted, total);
814 3039 ▶ if (fd >= 0) { flock(fd, LOCK_UN); close(fd); }
Branch: 1 branch
BranchTrueFalseTotal
if (fd >= 0) { flock(fd, LOCK_UN); close(fd); } 8 3031 3039
815 3039 return rsv_setup(base, map_size, path, -1, errbuf);
816 }
817  
818 2 static RsvHandle *rsv_create_memfd(const char *name, uint64_t k, uint64_t item_size, uint32_t weighted, char *errbuf) {
819 2 ▶ if (!rsv_validate_args(k, item_size, weighted, errbuf)) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!rsv_validate_args(k, item_size, weighted, errbuf)) return NULL; 0 2 2
820  
821 2 uint64_t total = rsv_total_size(k, item_size, weighted);
822 2 ▶ int fd = memfd_create(name ? name : "reservoir", MFD_CLOEXEC | MFD_ALLOW_SEALING);
Branch: 1 branch
BranchTrueFalseTotal
int fd = memfd_create(name ? name : "reservoir", MFD_CLOEXEC | MFD_ALLOW_SEALING); 2 0 2
823 2 ▶ if (fd < 0) { RSV_ERR("memfd_create: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fd < 0) { RSV_ERR("memfd_create: %s", strerror(errno)); return NULL; } 0 2 2
if (fd < 0) { RSV_ERR("memfd_create: %s", strerror(errno)); return NULL; } 0 0 0
824 2 ▶ if (ftruncate(fd, (off_t)total) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (ftruncate(fd, (off_t)total) < 0) { 0 2 2
825 0 ▶ RSV_ERR("ftruncate: %s", strerror(errno)); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
RSV_ERR("ftruncate: %s", strerror(errno)); close(fd); return NULL; 0 0 0
826 }
827 2 ▶ if (rsv_reserve(fd, total) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (rsv_reserve(fd, total) < 0) { 0 2 2
828 0 ▶ RSV_ERR("memfd: cannot reserve %llu bytes: %s", (unsigned long long)total, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
RSV_ERR("memfd: cannot reserve %llu bytes: %s", (unsigned long long)total, strerror(errno)); 0 0 0
829 0 close(fd); return NULL;
830 }
831 2 (void)fcntl(fd, F_ADD_SEALS, F_SEAL_SHRINK | F_SEAL_GROW);
832 2 void *base = mmap(NULL, (size_t)total, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
833 2 ▶ if (base == MAP_FAILED) { RSV_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { RSV_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; } 0 2 2
if (base == MAP_FAILED) { RSV_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; } 0 0 0
834 2 rsv_init_header(base, k, item_size, weighted, total);
835 2 return rsv_setup(base, (size_t)total, NULL, fd, errbuf);
836 }
837  
838 3 static RsvHandle *rsv_open_fd(int fd, char *errbuf) {
839 3 ▶ if (errbuf) errbuf[0] = '\0';
Branch: 1 branch
BranchTrueFalseTotal
if (errbuf) errbuf[0] = '\0'; 3 0 3
840 struct stat st;
841 3 ▶ if (fstat(fd, &st) < 0) { RSV_ERR("fstat: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fstat(fd, &st) < 0) { RSV_ERR("fstat: %s", strerror(errno)); return NULL; } 0 3 3
if (fstat(fd, &st) < 0) { RSV_ERR("fstat: %s", strerror(errno)); return NULL; } 0 0 0
842 3 ▶ if ((uint64_t)st.st_size < sizeof(RsvHeader)) { RSV_ERR("too small"); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if ((uint64_t)st.st_size < sizeof(RsvHeader)) { RSV_ERR("too small"); return NULL; } 0 3 3
if ((uint64_t)st.st_size < sizeof(RsvHeader)) { RSV_ERR("too small"); return NULL; } 0 0 0
843 /* before mmap: a creator may truncate the file until it has set magic */
844 uint32_t magic;
845 3 ▶ if (pread(fd, &magic, sizeof magic, offsetof(RsvHeader, magic)) != (ssize_t)sizeof magic || magic != RSV_MAGIC) {
Branch: 2 branches
BranchTrueFalseTotal
if (pread(fd, &magic, sizeof magic, offsetof(RsvHeader, magic)) != (ssize_t)sizeof magic || magic != RSV_MAGIC) { 3 0 3
if (pread(fd, &magic, sizeof magic, offsetof(RsvHeader, magic)) != (ssize_t)sizeof magic || magic != RSV_MAGIC) { 0 3 3
846 0 ▶ RSV_ERR("invalid reservoir table"); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
RSV_ERR("invalid reservoir table"); return NULL; 0 0 0
847 }
848 3 size_t ms = (size_t)st.st_size;
849 3 void *base = mmap(NULL, ms, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
850 3 ▶ if (base == MAP_FAILED) { RSV_ERR("mmap: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { RSV_ERR("mmap: %s", strerror(errno)); return NULL; } 0 3 3
if (base == MAP_FAILED) { RSV_ERR("mmap: %s", strerror(errno)); return NULL; } 0 0 0
851 3 ▶ if (!rsv_validate_header((RsvHeader *)base, (uint64_t)st.st_size)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!rsv_validate_header((RsvHeader *)base, (uint64_t)st.st_size)) { 1 2 3
852 1 ▶ RSV_ERR("invalid reservoir table"); munmap(base, ms); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
RSV_ERR("invalid reservoir table"); munmap(base, ms); return NULL; 1 0 1
853 }
854 2 int myfd = fcntl(fd, F_DUPFD_CLOEXEC, 0);
855 2 ▶ if (myfd < 0) { RSV_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (myfd < 0) { RSV_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; } 0 2 2
if (myfd < 0) { RSV_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; } 0 0 0
856 2 return rsv_setup(base, ms, NULL, myfd, errbuf);
857 }
858  
859 3048 static void rsv_destroy(RsvHandle *h) {
860 3048 ▶ if (!h) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!h) return; 0 3048 3048
861 /* Release our reader slot on clean teardown (else short-lived-reader churn
862 * exhausts the slot table); skip if a read lock is still held (rdepth>0). */
863 3048 ▶ if (h->reader_slots && h->my_slot_idx != UINT32_MAX && h->cached_pid &&
Branch: 3 branches
BranchTrueFalseTotal
if (h->reader_slots && h->my_slot_idx != UINT32_MAX && h->cached_pid && 3048 0 3048
if (h->reader_slots && h->my_slot_idx != UINT32_MAX && h->cached_pid && 3043 5 3048
if (h->reader_slots && h->my_slot_idx != UINT32_MAX && h->cached_pid && 3043 0 3043
864 3043 ▶ h->cached_fork_gen == __atomic_load_n(&rsv_fork_gen, __ATOMIC_RELAXED) &&
Branch: 1 branch
BranchTrueFalseTotal
h->cached_fork_gen == __atomic_load_n(&rsv_fork_gen, __ATOMIC_RELAXED) && 3043 0 3043
865 3043 ▶ __atomic_load_n(&h->reader_slots[h->my_slot_idx].rdepth, __ATOMIC_ACQUIRE) == 0) {
Branch: 1 branch
BranchTrueFalseTotal
__atomic_load_n(&h->reader_slots[h->my_slot_idx].rdepth, __ATOMIC_ACQUIRE) == 0) { 3043 0 3043
866 /* Clear our occ bit BEFORE freeing the slot: we still own the pid so no
867 * claimant can take the slot mid-clear, and rdepth==0 so no writer needs
868 * to see us. (A crash skips this -> the bit is reclaimed lazily by a
869 * writer scan / re-claim, same as the pid.) */
870 3043 rsv_occ_clear(h, h->my_slot_idx);
871 3043 uint32_t expected = h->cached_pid;
872 3043 __atomic_compare_exchange_n(&h->reader_slots[h->my_slot_idx].pid,
873 &expected, 0, 0, __ATOMIC_RELEASE, __ATOMIC_RELAXED);
874 }
875 3048 ▶ if (h->backing_fd >= 0) close(h->backing_fd);
Branch: 1 branch
BranchTrueFalseTotal
if (h->backing_fd >= 0) close(h->backing_fd); 4 3044 3048
876 3048 ▶ if (h->base) munmap(h->base, h->mmap_size);
Branch: 1 branch
BranchTrueFalseTotal
if (h->base) munmap(h->base, h->mmap_size); 3048 0 3048
877 3048 free(h->unlink_path);
878 3048 free(h->path);
879 3048 free(h);
880 }
881  
882 3 static inline int rsv_msync(RsvHandle *h) {
883 3 ▶ if (!h || !h->base) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (!h || !h->base) return 0; 3 0 3
if (!h || !h->base) return 0; 0 3 3
884 3 return msync(h->base, h->mmap_size, MS_SYNC);
885 }
886  
887 /* ================================================================
888 * Reservoir sampling operations (callers hold the lock) -- Algorithm R with a
889 * shared xorshift64 RNG. Each slot is [uint64 len][item_size data bytes].
890 * ================================================================ */
891  
892 275761 static inline uint64_t rsv_rng_next(RsvHeader *hdr) {
893 275761 uint64_t x = hdr->rng_state;
894 275761 x ^= x << 13; x ^= x >> 7; x ^= x << 17; /* xorshift64 state advance (period/determinism preserved) */
895 275761 hdr->rng_state = x;
896 /* SplitMix64 output finalizer: xorshift64 does not diffuse the seed into the
897 * high bits, so the first post-seed output (and the high bits the weighted
898 * A-Res key reads) would be a near-deterministic function of the seed. Mix
899 * the returned value across all 64 bits without touching the state advance. */
900 275761 uint64_t z = x;
901 275761 z = (z ^ (z >> 30)) * 0xBF58476D1CE4E5B9ULL;
902 275761 z = (z ^ (z >> 27)) * 0x94D049BB133111EBULL;
903 275761 return z ^ (z >> 31);
904 }
905  
906 /* pointer to slot i's [uint64 len][item_size data] record */
907 213648 static inline uint8_t *rsv_slot(RsvHandle *h, uint64_t i) {
908 213648 return rsv_slots(h) + i * h->stride;
909 }
910  
911 /* store an item into slot idx (truncated to item_size) */
912 156630 static inline void rsv_store(RsvHandle *h, uint64_t idx, const void *item, uint64_t len) {
913 156630 uint8_t *slot = rsv_slot(h, idx);
914 156630 uint64_t cap = h->item_size; /* cached: <= stride-8, so the write stays in-slot */
915 156630 ▶ if (len > cap) len = cap; /* truncate over-long items */
Branch: 1 branch
BranchTrueFalseTotal
if (len > cap) len = cap; /* truncate over-long items */ 1 156629 156630
916 156630 memcpy(slot, &len, sizeof(uint64_t)); /* stored length */
917 156630 ▶ if (len) memcpy(slot + 8, item, (size_t)len);
Branch: 1 branch
BranchTrueFalseTotal
if (len) memcpy(slot + 8, item, (size_t)len); 156630 0 156630
918 156630 }
919  
920 /* number of items currently held = min(seen, k) */
921 54055 static inline uint64_t rsv_count_locked(RsvHandle *h) {
922 54055 uint64_t k = h->k, seen = h->hdr->seen; /* k cached; seen is live mutable state */
923 54055 return seen < k ? seen : k;
924 }
925  
926 /* observe one item. Returns 1 if stored in the reservoir, 0 if discarded.
927 * Algorithm R: the i-th item fills slot i-1 while the reservoir is not full;
928 * once full, it replaces a uniformly random slot with probability k/i. */
929 62847 static int rsv_add_locked(RsvHandle *h, const void *item, uint64_t len) {
930 62847 RsvHeader *hdr = h->hdr;
931 62847 uint64_t k = h->k; /* cached geometry */
932 62847 uint64_t smax = rsv_slots_max(h);
933 62847 ▶ if (k > smax) k = smax; /* Layer B: never index past the mapping */
Branch: 1 branch
BranchTrueFalseTotal
if (k > smax) k = smax; /* Layer B: never index past the mapping */ 0 62847 62847
934 62847 ▶ if (k == 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (k == 0) return 0; 0 62847 62847
935 62847 uint64_t s = hdr->seen + 1; /* 1-based index of this item */
936 uint64_t idx;
937 62847 ▶ if (s <= k) {
Branch: 1 branch
BranchTrueFalseTotal
if (s <= k) { 15160 47687 62847
938 15160 idx = s - 1; /* still filling the reservoir */
939 } else {
940 47687 hdr->seen = s;
941 47687 uint64_t j = rsv_rng_next(hdr) % s; /* uniform in [0, s) */
942 47687 ▶ if (j >= k) return 0; /* discard (prob (s-k)/s) */
Branch: 1 branch
BranchTrueFalseTotal
if (j >= k) return 0; /* discard (prob (s-k)/s) */ 27606 20081 47687
943 20081 idx = j; /* replace slot j (prob k/s) */
944 }
945 35241 ▶ if (idx >= smax) { hdr->seen = s; return 0; } /* Layer B: reject a wrapped/corrupt seen (idx underflow) -> no OOB */
Branch: 1 branch
BranchTrueFalseTotal
if (idx >= smax) { hdr->seen = s; return 0; } /* Layer B: reject a wrapped/corrupt seen (idx underflow) -> no OOB */ 0 35241 35241
946 35241 rsv_store(h, idx, item, len);
947 /* While filling, the count publishes the slot: store the item first. */
948 35241 __atomic_signal_fence(__ATOMIC_SEQ_CST);
949 35241 hdr->seen = s;
950 35241 return 1;
951 }
952  
953 /* ---- weighted (A-Res) min-heap over the items region (weighted mode only) ----
954 * One 16-byte {key,item} entry per kept item; entry.item indexes a fixed items
955 * cell that stays put -- sifting moves only these entries, never the item bytes. */
956 228074 static inline RsvHeapEnt *rsv_heap(RsvHandle *h) {
957 228074 return (RsvHeapEnt *)((char *)h->base + h->heap_off);
958 }
959 /* Layer B trusted bound: heap entries guaranteed within the real mapping. */
960 228074 static inline uint64_t rsv_heap_max(RsvHandle *h) {
961 228074 uint64_t off = h->heap_off;
962 228074 ▶ if (off == 0 || off >= h->mmap_size) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (off == 0 || off >= h->mmap_size) return 0; 228074 0 228074
if (off == 0 || off >= h->mmap_size) return 0; 0 228074 228074
963 228074 return (h->mmap_size - off) / sizeof(RsvHeapEnt);
964 }
965 /* Journaled hole sifts: entry e, saved in hdr->jent, belongs at the hole hp[i], which may hold a
966 * stale duplicate; each step copies one entry into the hole and records the new hole in jsift.
967 * A writer killed mid-sift leaves jsift set, and lock recovery finishes the sift. */
968 #define RSV_J_UP 0x40000000U
969 #define RSV_J_DOWN 0x80000000U
970 #define RSV_J_HOLE 0x3FFFFFFFU
971  
972 26199 static inline void rsv_journal_begin(RsvHeader *hdr, RsvHeapEnt e, uint32_t dir, uint64_t i) {
973 26199 hdr->jent = e;
974 26199 __atomic_signal_fence(__ATOMIC_SEQ_CST);
975 26199 hdr->jsift = dir | (uint32_t)i;
976 26199 __atomic_signal_fence(__ATOMIC_SEQ_CST);
977 26199 }
978 28909 static inline void rsv_journal_step(RsvHeader *hdr, RsvHeapEnt *hp, uint64_t i, uint64_t next, uint32_t dir) {
979 28909 hp[i] = hp[next];
980 28909 __atomic_signal_fence(__ATOMIC_SEQ_CST);
981 28909 hdr->jsift = dir | (uint32_t)next;
982 28909 __atomic_signal_fence(__ATOMIC_SEQ_CST);
983 28909 }
984 26199 static inline void rsv_journal_end(RsvHeader *hdr, RsvHeapEnt *hp, uint64_t i, RsvHeapEnt e) {
985 26199 hp[i] = e;
986 26199 __atomic_signal_fence(__ATOMIC_SEQ_CST);
987 26199 hdr->jsift = 0;
988 26199 }
989 2791 static inline void rsv_heap_sift_up(RsvHeader *hdr, RsvHeapEnt *hp, uint64_t i, RsvHeapEnt e) {
990 5751 ▶ while (i > 0) {
Branch: 1 branch
BranchTrueFalseTotal
while (i > 0) { 3196 2555 5751
991 3196 uint64_t p = (i - 1) / 2;
992 3196 ▶ if (!(e.key < hp[p].key)) break;
Branch: 1 branch
BranchTrueFalseTotal
if (!(e.key < hp[p].key)) break; 236 2960 3196
993 2960 rsv_journal_step(hdr, hp, i, p, RSV_J_UP);
994 2960 i = p;
995 }
996 2791 rsv_journal_end(hdr, hp, i, e);
997 2791 }
998 23408 static inline void rsv_heap_sift_down(RsvHeader *hdr, RsvHeapEnt *hp, uint64_t i, uint64_t size, RsvHeapEnt e) {
999 25949 for (;;) {
1000 49357 uint64_t c = 2*i + 1;
1001 49357 ▶ if (c >= size) break;
Branch: 1 branch
BranchTrueFalseTotal
if (c >= size) break; 22958 26399 49357
1002 26399 ▶ if (c + 1 < size && hp[c + 1].key < hp[c].key) c++;
Branch: 2 branches
BranchTrueFalseTotal
if (c + 1 < size && hp[c + 1].key < hp[c].key) c++; 26358 41 26399
if (c + 1 < size && hp[c + 1].key < hp[c].key) c++; 13597 12761 26358
1003 26399 ▶ if (!(hp[c].key < e.key)) break;
Branch: 1 branch
BranchTrueFalseTotal
if (!(hp[c].key < e.key)) break; 450 25949 26399
1004 25949 rsv_journal_step(hdr, hp, i, c, RSV_J_DOWN);
1005 25949 i = c;
1006 }
1007 23408 rsv_journal_end(hdr, hp, i, e);
1008 23408 }
1009  
1010 /* A fill killed before publishing its item never happened; any other sift is finished. */
1011 0 static void rsv_journal_replay(RsvHandle *h) {
1012 0 RsvHeader *hdr = h->hdr;
1013 0 uint32_t j = hdr->jsift;
1014 0 ▶ if (!j) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!j) return; 0 0 0
1015 0 uint64_t k = h->k, smax = rsv_slots_max(h), hmax = rsv_heap_max(h);
1016 0 ▶ if (k > smax) k = smax;
Branch: 1 branch
BranchTrueFalseTotal
if (k > smax) k = smax; 0 0 0
1017 0 ▶ if (k > hmax) k = hmax; /* Layer B, as in rsv_add_weighted_locked */
Branch: 1 branch
BranchTrueFalseTotal
if (k > hmax) k = hmax; /* Layer B, as in rsv_add_weighted_locked */ 0 0 0
1018 0 uint64_t size = hdr->seen < k ? hdr->seen : k, i = j & RSV_J_HOLE;
1019 0 RsvHeapEnt e = hdr->jent;
1020 0 ▶ if (h->mode == RSV_MODE_WEIGHTED && i < size && e.item < k) {
Branch: 3 branches
BranchTrueFalseTotal
if (h->mode == RSV_MODE_WEIGHTED && i < size && e.item < k) { 0 0 0
if (h->mode == RSV_MODE_WEIGHTED && i < size && e.item < k) { 0 0 0
if (h->mode == RSV_MODE_WEIGHTED && i < size && e.item < k) { 0 0 0
1021 0 ▶ if ((j & ~RSV_J_HOLE) == RSV_J_UP) { rsv_heap_sift_up(hdr, rsv_heap(h), i, e); return; }
Branch: 1 branch
BranchTrueFalseTotal
if ((j & ~RSV_J_HOLE) == RSV_J_UP) { rsv_heap_sift_up(hdr, rsv_heap(h), i, e); return; } 0 0 0
1022 0 ▶ if ((j & ~RSV_J_HOLE) == RSV_J_DOWN) { rsv_heap_sift_down(hdr, rsv_heap(h), i, size, e); return; }
Branch: 1 branch
BranchTrueFalseTotal
if ((j & ~RSV_J_HOLE) == RSV_J_DOWN) { rsv_heap_sift_down(hdr, rsv_heap(h), i, size, e); return; } 0 0 0
1023 }
1024 0 hdr->jsift = 0;
1025 }
1026  
1027 /* observe one weighted item. A-Res: assign it key = log(u)/weight, u ~ U(0,1];
1028 * keep the k items with the largest keys via a min-heap (root = smallest kept
1029 * key). Returns 1 if kept, 0 if discarded. `weight` is validated finite > 0 in
1030 * XS before the lock. Caller holds the write lock. */
1031 228074 static int rsv_add_weighted_locked(RsvHandle *h, const void *item, uint64_t len, double weight) {
1032 228074 RsvHeader *hdr = h->hdr;
1033 228074 uint64_t k = h->k; /* cached geometry */
1034 228074 uint64_t smax = rsv_slots_max(h);
1035 228074 uint64_t hmax = rsv_heap_max(h);
1036 228074 ▶ if (k > smax) k = smax;
Branch: 1 branch
BranchTrueFalseTotal
if (k > smax) k = smax; 0 228074 228074
1037 228074 ▶ if (k > hmax) k = hmax; /* Layer B: never index past either region */
Branch: 1 branch
BranchTrueFalseTotal
if (k > hmax) k = hmax; /* Layer B: never index past either region */ 0 228074 228074
1038 228074 ▶ if (k == 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (k == 0) return 0; 0 228074 228074
1039 228074 uint64_t x = rsv_rng_next(hdr);
1040 228074 double u = (double)((x >> 11) + 1) * (1.0 / 9007199254740992.0); /* (0, 1] */
1041 228074 double key = log(u) / weight;
1042 228074 RsvHeapEnt *hp = rsv_heap(h);
1043 228074 uint64_t size = hdr->seen < k ? hdr->seen : k; /* items currently kept */
1044 228074 ▶ if (size < k) { /* still filling: append + sift up */
Branch: 1 branch
BranchTrueFalseTotal
if (size < k) { /* still filling: append + sift up */ 57406 170668 228074
1045 57406 RsvHeapEnt e = { key, size };
1046 57406 rsv_store(h, size, item, len);
1047 57406 ▶ if (size > 0 && key < hp[(size - 1) / 2].key) {
Branch: 2 branches
BranchTrueFalseTotal
if (size > 0 && key < hp[(size - 1) / 2].key) { 6393 51013 57406
if (size > 0 && key < hp[(size - 1) / 2].key) { 2791 3602 6393
1048 2791 rsv_journal_begin(hdr, e, RSV_J_UP, size);
1049 2791 hdr->seen++;
1050 2791 __atomic_signal_fence(__ATOMIC_SEQ_CST);
1051 2791 rsv_heap_sift_up(hdr, hp, size, e);
1052 } else {
1053 54615 hp[size] = e;
1054 /* The count publishes the entry. */
1055 54615 __atomic_signal_fence(__ATOMIC_SEQ_CST);
1056 54615 hdr->seen++;
1057 }
1058 57406 return 1;
1059 }
1060 170668 hdr->seen++; /* full: this item was observed regardless */
1061 170668 ▶ if (key > hp[0].key) { /* heavier than the current minimum: evict it */
Branch: 1 branch
BranchTrueFalseTotal
if (key > hp[0].key) { /* heavier than the current minimum: evict it */ 63983 106685 170668
1062 63983 uint64_t cell = hp[0].item;
1063 63983 ▶ if (cell >= k) return 0; /* Layer B: corrupt heap entry -> refuse */
Branch: 1 branch
BranchTrueFalseTotal
if (cell >= k) return 0; /* Layer B: corrupt heap entry -> refuse */ 0 63983 63983
1064 63983 RsvHeapEnt e = { key, cell };
1065 63983 rsv_store(h, cell, item, len);
1066 63983 ▶ if ((k > 1 && hp[1].key < key) || (k > 2 && hp[2].key < key)) {
Branch: 4 branches
BranchTrueFalseTotal
if ((k > 1 && hp[1].key < key) || (k > 2 && hp[2].key < key)) { 31939 32044 63983
if ((k > 1 && hp[1].key < key) || (k > 2 && hp[2].key < key)) { 13661 18278 31939
if ((k > 1 && hp[1].key < key) || (k > 2 && hp[2].key < key)) { 13661 32044 45705
if ((k > 1 && hp[1].key < key) || (k > 2 && hp[2].key < key)) { 5130 8531 13661
1067 23408 rsv_journal_begin(hdr, e, RSV_J_DOWN, 0);
1068 23408 rsv_heap_sift_down(hdr, hp, 0, k, e);
1069 } else {
1070 40575 hp[0].key = key;
1071 }
1072 63983 return 1;
1073 }
1074 106685 return 0; /* lighter: discard */
1075 }
1076  
1077 /* point *out_ptr/*out_len at slot i's item inside the mapping (caller holds the
1078 * read lock). Returns 1 if i is a filled slot, else 0. */
1079 11 static int rsv_get_locked(RsvHandle *h, uint64_t i, const uint8_t **out_ptr, uint64_t *out_len) {
1080 11 ▶ if (i >= rsv_count_locked(h) || i >= rsv_slots_max(h)) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (i >= rsv_count_locked(h) || i >= rsv_slots_max(h)) return 0; 10 1 11
if (i >= rsv_count_locked(h) || i >= rsv_slots_max(h)) return 0; 0 10 10
1081 10 uint8_t *slot = rsv_slot(h, i);
1082 10 uint64_t len; memcpy(&len, slot, sizeof(uint64_t));
1083 10 ▶ if (len > h->item_size) len = h->item_size; /* Layer B clamp (cached item_size) */
Branch: 1 branch
BranchTrueFalseTotal
if (len > h->item_size) len = h->item_size; /* Layer B clamp (cached item_size) */ 0 10 10
1084 10 *out_ptr = slot + 8;
1085 10 *out_len = len;
1086 10 return 1;
1087 }
1088  
1089 /* reset the reservoir to empty (caller holds the write lock) */
1090 51002 static inline void rsv_clear_locked(RsvHandle *h) {
1091 51002 uint64_t k = h->k; /* cached geometry */
1092 51002 uint64_t smax = rsv_slots_max(h);
1093 51002 ▶ if (k > smax) k = smax;
Branch: 1 branch
BranchTrueFalseTotal
if (k > smax) k = smax; 0 51002 51002
1094 /* Empty first: a writer killed mid-loop then leaves no counted slot already zeroed. */
1095 51002 h->hdr->seen = 0;
1096 51002 __atomic_signal_fence(__ATOMIC_SEQ_CST);
1097 108010 ▶ for (uint64_t i = 0; i < k; i++) { /* zero each slot's length word */
Branch: 1 branch
BranchTrueFalseTotal
for (uint64_t i = 0; i < k; i++) { /* zero each slot's length word */ 57008 51002 108010
1098 57008 uint64_t z = 0; memcpy(rsv_slot(h, i), &z, sizeof(uint64_t));
1099 }
1100 51002 }
1101  
1102 #endif /* RSV_H */
« blib/lib/Data/Reservoir/Shared.pm ↑ Summary Shared.xs »