fenwick.h

filter: Statementstmt 72.3% 379 / 524 Branchbran 46.5% 204 / 438 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 60.6% 583 / 962 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« blib/lib/Data/Fenwick/Shared.pm ↑ Summary Shared.xs »
1 /*
2 * fenwick.h -- Shared-memory Fenwick tree (binary indexed tree) for Linux
3 *
4 * A fixed-size array of n signed int64 positions supporting O(log n) point
5 * update and prefix-sum query: add a delta at a position, ask the sum over any
6 * prefix or range, or binary-search for the position where a cumulative total
7 * is reached (rank / weighted lookup). The tree lives in a shared mapping so
8 * several processes update and query one structure; a write-preferring futex
9 * rwlock with reader-slot dead-process recovery guards mutation. Two trees of
10 * equal size can be merged (element-wise add -- a Fenwick tree is linear).
11 *
12 * Layout: Header -> reader_slots[1024] -> occ bitmap -> tree[(n+1) int64] (1-indexed, slot 0 unused)
13 */
14  
15 #ifndef FEN_H
16 #define FEN_H
17  
18 #include <stddef.h>
19 #include <stdint.h>
20 #include <stdlib.h>
21 #include <string.h>
22 #include <unistd.h>
23 #include <fcntl.h>
24 #include <errno.h>
25 #include <time.h>
26 #include <limits.h>
27 #include <signal.h>
28 #include <stdio.h>
29 #include <math.h>
30 #include <sys/mman.h>
31 #include <sys/stat.h>
32 #include <sys/file.h>
33 #include <sys/syscall.h>
34 #include <linux/futex.h>
35 #include <pthread.h>
36  
37 #if defined(__BYTE_ORDER__) && __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
38 #error "fenwick.h: requires little-endian architecture"
39 #endif
40  
41  
42 /* ================================================================
43 * Constants
44 * ================================================================ */
45  
46 #define FEN_MAGIC 0x574E4546U /* Fenwick */
47 #define FEN_VERSION 2 /* 2: added the occupancy bitmap region (layout change) */
48 #define FEN_ERR_BUFLEN (PATH_MAX + 256)
49 #ifndef FEN_READER_SLOTS
50 #define FEN_READER_SLOTS 1024 /* reader handles per mapping for dead-process recovery */
51 #endif
52 /* Occupancy bitmap: one bit per reader slot, set when a process claims a slot and
53 * cleared on clean release. A writer scans these FEN_OCC_WORDS words to visit
54 * only OCCUPIED slots (O(words + live readers)) instead of all FEN_READER_SLOTS. */
55 #define FEN_OCC_WORDS (((FEN_READER_SLOTS) + 63) / 64) /* 16 for 1024 slots */
56 #define FEN_OCC_BYTES ((uint64_t)FEN_OCC_WORDS * 8) /* 128 bytes */
57 #define FEN_MIN_N 1
58 #define FEN_MAX_N 0x100000000ULL /* 2^32 positions; (n+1)*8-byte tree cap (~32 GiB) */
59  
60 #define FEN_MODE_POINT 0U /* single BIT: point update + prefix/range query */
61 #define FEN_MODE_RANGE 1U /* two BITs: range update (range_add) + range query */
62  
63 #define FEN_ERR(fmt, ...) do { if (errbuf) snprintf(errbuf, FEN_ERR_BUFLEN, fmt, ##__VA_ARGS__); } while (0)
64  
65 /* ================================================================
66 * Structs
67 * ================================================================ */
68  
69 /* Per-process slot for dead-process recovery. In the reader-slots-only rwlock a
70 * reader's ENTIRE contribution to the shared lock is `rdepth` in its OWN slot --
71 * there is no separate shared reader counter to fall out of sync with it -- so a
72 * dead reader's contribution is exactly this one word, which a draining writer
73 * neutralises by clearing the slot's pid (the scan then ignores the slot). No
74 * orphaned counter can exist, so there is no quiescent force-reset and sustained
75 * readers cannot starve a writer. _rsv1/_rsv2 are kept only to preserve the
76 * 16-byte slot size across the already-released builds. */
77 typedef struct {
78 uint32_t pid; /* 0 = unclaimed */
79 uint32_t rdepth; /* read-locks THIS process currently holds (recursion-safe) */
80 uint32_t _rsv1; /* reserved (was waiters_parked); unused, kept for layout size */
81 uint32_t _rsv2; /* reserved (was writers_parked); unused, kept for layout size */
82 } FenReaderSlot;
83  
84 struct FenHeader {
85 uint32_t magic, version; /* 0,4 */
86 uint32_t mode; /* 8 FEN_MODE_POINT | FEN_MODE_RANGE */
87 uint32_t _pad1; /* 12 */
88 uint64_t n; /* 16 number of positions (1..n); tree has n+1 int64 slots */
89 uint64_t tree2_off; /* 24 second BIT (range mode; 0 in point mode) */
90 uint64_t capacity; /* 32 == n (kept for family stats parity) */
91 uint64_t _reserved1; /* 40 */
92 uint64_t total_size; /* 48 */
93 uint64_t reader_slots_off; /* 56 */
94 uint64_t tree_off; /* 64 */
95 uint32_t wlock; /* 72 WRITER word ONLY: 0 (free) or WRITER_BIT|pid. NOT a reader count. */
96 uint32_t rwait; /* 76 parked-waiter hint (readers+writers blocked on wlock); over-count-safe */
97 uint32_t drain_seq; /* 80 futex bumped by a reader releasing under a draining writer (wakes it) */
98 uint32_t slotless_rdepth; /* readers holding with no reader-slot (documented residual) */
99 uint64_t stat_ops; /* 88 */
100 uint8_t sealed; /* 96 0 = mutable, 1 = frozen (read-only; lock-free reads) */
101 uint8_t _pad[159]; /* 97..255 */
102 };
103 typedef struct FenHeader FenHeader;
104  
105 _Static_assert(sizeof(FenHeader) == 256, "FenHeader must be 256 bytes");
106  
107 /* ---- Process-local handle ---- */
108  
109 typedef struct FenHandle {
110 FenHeader *hdr;
111 FenReaderSlot *reader_slots; /* FEN_READER_SLOTS entries */
112 uint64_t *occ; /* FEN_OCC_WORDS-word slot-occupancy bitmap (trusted layout offset) */
113 void *base; /* mmap base */
114 uint64_t tree_off; /* validated tree-array offset, cached: never re-read from the peer-writable header */
115 uint64_t tree2_off; /* second BIT offset (range mode), cached; 0 in point mode */
116 uint32_t mode; /* FEN_MODE_* (cached from validated header) */
117 size_t mmap_size;
118 char *path; /* backing file path (strdup'd) */
119 int backing_fd; /* memfd or reopened-fd to close on destroy, -1 for file/anon */
120 uint32_t my_slot_idx; /* UINT32_MAX if all slots taken (no recovery for this handle) */
121 uint32_t cached_pid; /* getpid() cached at last slot claim */
122 uint32_t cached_fork_gen; /* fen_fork_gen value at last slot claim */
123 uint32_t slotless_held; /* read-locks this process holds with no reader-slot */
124 int readonly; /* 1 = frozen O_RDONLY/PROT_READ view: lock-free reads, mutation croaks */
125 } FenHandle;
126  
127 /* ================================================================
128 * Futex-based write-preferring read-write lock (reader-slots-only)
129 * with dead-process recovery
130 *
131 * The reader count is NOT stored in a shared counter. It is DISTRIBUTED across
132 * per-process reader slots: each slot's `rdepth` is that process's entire
133 * contribution to the lock. A reader publishes its presence in its own slot and
134 * then re-checks the writer word; a writer publishes the writer word and then
135 * scans every slot until all live readers' rdepth reach 0. Sequentially-
136 * consistent store+load on each side (a Dekker handshake) gives mutual exclusion.
137 *
138 * Because a reader's whole contribution is ONE atomic word owned by ONE process,
139 * a crashed reader is recovered by clearing that one slot (CAS its pid to 0) --
140 * there is no second counter to strand, no orphaned +1, and therefore no
141 * quiescent force-reset. A reader killed anywhere in rdlock/rdunlock leaves at
142 * most `rdepth>0` in its dead slot, which the draining writer clears directly, so
143 * sustained read traffic can never starve a writer. Write-preference is inherent
144 * in the gate (new readers see wlock!=0 and yield), so there is no reader-count
145 * yield hack.
146 * ================================================================ */
147  
148 #define FEN_RWLOCK_SPIN_LIMIT 32
149 #define FEN_LOCK_TIMEOUT_SEC 2 /* FUTEX_WAIT timeout for stale-lock detection / drain re-scan */
150  
151 0 static inline void fen_rwlock_spin_pause(void) {
152 #if defined(__x86_64__) || defined(__i386__)
153 0 __asm__ volatile("pause" ::: "memory");
154 #elif defined(__aarch64__)
155 __asm__ volatile("yield" ::: "memory");
156 #else
157 __asm__ volatile("" ::: "memory");
158 #endif
159 0 }
160  
161 /* Writer word encoding: WRITER_BIT|pid when write-locked, 0 when free. */
162 #define FEN_RWLOCK_WRITER_BIT 0x80000000U
163 #define FEN_RWLOCK_PID_MASK 0x7FFFFFFFU
164 #define FEN_RWLOCK_WR(pid) (FEN_RWLOCK_WRITER_BIT | ((uint32_t)(pid) & FEN_RWLOCK_PID_MASK))
165  
166 /* A zombie (dead but not yet reaped) still answers kill(pid,0) as alive, so a
167 * process that crashed while holding the lock and lingers unreaped would never
168 * be recovered. Treat /proc/<pid>/stat state 'Z' as dead. Linux-only (as is
169 * this module); if /proc is unreadable we fall back to "alive" (safe: we never
170 * force-recover a possibly-live holder). */
171 0 static inline int fen_pid_is_zombie(uint32_t pid) {
172 char path[32], buf[256];
173 0 snprintf(path, sizeof(path), "/proc/%u/stat", (unsigned)pid);
174 0 int fd = open(path, O_RDONLY | O_CLOEXEC);
175 0 ▶ if (fd < 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (fd < 0) return 0; 0 0 0
176 0 ssize_t n = read(fd, buf, sizeof(buf) - 1);
177 0 close(fd);
178 0 ▶ if (n <= 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (n <= 0) return 0; 0 0 0
179 0 buf[n] = '\0';
180 /* "pid (comm) state ..."; comm may contain ')', so scan to the last one. */
181 0 char *rp = strrchr(buf, ')');
182 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
183 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
184 }
185 /* 1 if alive or unknown, 0 if definitely dead. Cannot detect PID reuse: a
186 * recycled PID reports "alive" and the slot is not reclaimed until that
187 * process exits. See "Crash Safety" in the POD. */
188 0 static inline int fen_pid_alive(uint32_t pid) {
189 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
190 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
191 0 return !fen_pid_is_zombie(pid); /* kill() also succeeds for a zombie -> treat as dead */
192 }
193  
194 1611 static inline void fen_release_writer(FenHeader *hdr) {
195 /* Pair with the waiter's publish + gate re-check: neither may miss the other. */
196 1611 __atomic_store_n(&hdr->wlock, 0, __ATOMIC_SEQ_CST);
197 1611 ▶ if (__atomic_load_n(&hdr->rwait, __ATOMIC_SEQ_CST) > 0)
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&hdr->rwait, __ATOMIC_SEQ_CST) > 0) 0 1611 1611
198 0 syscall(SYS_futex, &hdr->wlock, FUTEX_WAKE, INT_MAX, NULL, NULL, 0);
199 1611 }
200  
201 /* Force-recover a stale WRITE lock left by a dead writer (held or mid-drain).
202 * CAS to OUR pid to hold the lock while fixing shared state, then release.
203 * Using our pid (not a bare WRITER_BIT sentinel) means a subsequent recovering
204 * process can detect and re-recover if we crash mid-recovery. */
205 0 static inline void fen_recover_stale_lock(FenHandle *h, uint32_t observed_wlock) {
206 0 FenHeader *hdr = h->hdr;
207 0 uint32_t mypid = FEN_RWLOCK_WR((uint32_t)getpid());
208 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
209 mypid, 0, __ATOMIC_ACQUIRE, __ATOMIC_RELAXED))
210 0 return;
211 /* We now hold the write lock as mypid. No additional shared state needs
212 * repair here (this module has no seqlock); just release the lock. */
213 0 fen_release_writer(hdr);
214 }
215  
216 static const struct timespec fen_lock_timeout = { FEN_LOCK_TIMEOUT_SEC, 0 };
217  
218 /* Process-global fork-generation counter. Incremented in the pthread_atfork
219 * child callback so every open handle detects a fork transition on the next
220 * lock call without paying a getpid() syscall on the hot path. */
221 static uint32_t fen_fork_gen = 1;
222 static pthread_once_t fen_atfork_once = PTHREAD_ONCE_INIT;
223 0 static void fen_on_fork_child(void) {
224 0 __atomic_add_fetch(&fen_fork_gen, 1, __ATOMIC_RELAXED);
225 0 }
226 6 static void fen_atfork_init(void) {
227 6 pthread_atfork(NULL, NULL, fen_on_fork_child);
228 6 }
229  
230 /* Occupancy bitmap: set a slot's bit when it is claimed, clear it on clean
231 * release. SEQ_CST so a set bit is ordered before the slot's rdepth can go
232 * non-zero (bit set in claim, which precedes any rdlock), letting a writer's
233 * SEQ_CST bitmap scan never miss a slot a committed reader holds. */
234 39 static inline void fen_occ_set(FenHandle *h, uint32_t s) {
235 39 __atomic_fetch_or(&h->occ[s >> 6], (uint64_t)1 << (s & 63), __ATOMIC_SEQ_CST);
236 39 }
237 39 static inline void fen_occ_clear(FenHandle *h, uint32_t s) {
238 39 __atomic_fetch_and(&h->occ[s >> 6], ~((uint64_t)1 << (s & 63)), __ATOMIC_SEQ_CST);
239 39 }
240  
241 /* Ensure this process owns a reader slot. Called from the lock helpers so that
242 * fork()'d children pick up their own slot lazily instead of sharing the
243 * parent's. Hot-path is a single relaxed load + compare; only on a
244 * fork-generation mismatch do we touch getpid() and scan slots. */
245 3515 static inline void fen_claim_reader_slot(FenHandle *h) {
246 3515 uint32_t cur_gen = __atomic_load_n(&fen_fork_gen, __ATOMIC_RELAXED);
247 3515 ▶ 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)) 3476 39 3515
if (__builtin_expect(cur_gen == h->cached_fork_gen && h->my_slot_idx != UINT32_MAX, 1)) 3476 0 3476
248 3476 return;
249 /* Cold path -- register the atfork hook once per process, then claim. */
250 39 pthread_once(&fen_atfork_once, fen_atfork_init);
251 /* Re-read after pthread_once: fen_on_fork_child may have bumped it. */
252 39 cur_gen = __atomic_load_n(&fen_fork_gen, __ATOMIC_RELAXED);
253 39 uint32_t now_pid = (uint32_t)getpid();
254 39 h->cached_pid = now_pid;
255 39 ▶ 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 */ 39 0 39
256 39 h->cached_fork_gen = cur_gen;
257 39 h->my_slot_idx = UINT32_MAX;
258 39 uint32_t start = now_pid % FEN_READER_SLOTS;
259 /* Pass 1: take a free slot. */
260 41 ▶ for (uint32_t i = 0; i < FEN_READER_SLOTS; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t i = 0; i < FEN_READER_SLOTS; i++) { 41 0 41
261 41 uint32_t s = (start + i) % FEN_READER_SLOTS;
262 41 uint32_t expected = 0;
263 41 ▶ if (__atomic_compare_exchange_n(&h->reader_slots[s].pid,
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_compare_exchange_n(&h->reader_slots[s].pid, 39 2 41
264 &expected, now_pid, 0,
265 __ATOMIC_ACQUIRE, __ATOMIC_RELAXED)) {
266 /* Fresh owner holds no read locks yet; clear any stale rdepth left by
267 * a dead predecessor (its contribution is dropped as we take over). */
268 39 __atomic_store_n(&h->reader_slots[s].rdepth, 0, __ATOMIC_RELAXED);
269 39 fen_occ_set(h, s); /* mark occupied BEFORE any rdlock can bump rdepth */
270 39 h->my_slot_idx = s;
271 39 return;
272 }
273 }
274 /* Pass 2: no free slot -- reclaim one whose owner is dead. Safe to take even
275 * if its rdepth>0: clearing pid drops the dead reader's entire contribution
276 * (a writer scan ignores rdepth when pid==0) and we reset rdepth to 0 as we
277 * claim it. */
278 0 ▶ for (uint32_t i = 0; i < FEN_READER_SLOTS; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t i = 0; i < FEN_READER_SLOTS; i++) { 0 0 0
279 0 uint32_t dpid = __atomic_load_n(&h->reader_slots[i].pid, __ATOMIC_ACQUIRE);
280 0 ▶ if (dpid == 0 || dpid == now_pid || fen_pid_alive(dpid)) continue;
Branch: 3 branches
BranchTrueFalseTotal
if (dpid == 0 || dpid == now_pid || fen_pid_alive(dpid)) continue; 0 0 0
if (dpid == 0 || dpid == now_pid || fen_pid_alive(dpid)) continue; 0 0 0
if (dpid == 0 || dpid == now_pid || fen_pid_alive(dpid)) continue; 0 0 0
281 0 uint32_t expected = dpid;
282 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
283 __ATOMIC_ACQUIRE, __ATOMIC_RELAXED)) {
284 0 __atomic_store_n(&h->reader_slots[i].rdepth, 0, __ATOMIC_RELAXED);
285 0 fen_occ_set(h, i);
286 0 h->my_slot_idx = i;
287 0 return;
288 }
289 }
290 /* Table full -- leave my_slot_idx = UINT32_MAX so this handle takes the
291 * slotless path (lock still works; recovery of THIS reader's death is the
292 * documented slotless limitation). */
293 }
294  
295 /* Inspect the writer word after a futex-wait timeout. If a dead writer holds
296 * it, force-recover. Dead READERS need no action here: only a writer that owns
297 * wlock drains readers, and it clears dead readers inline in its own scan. */
298 0 static inline void fen_recover_after_timeout(FenHandle *h) {
299 0 uint32_t val = __atomic_load_n(&h->hdr->wlock, __ATOMIC_RELAXED);
300 0 ▶ if (val >= FEN_RWLOCK_WRITER_BIT) {
Branch: 1 branch
BranchTrueFalseTotal
if (val >= FEN_RWLOCK_WRITER_BIT) { 0 0 0
301 0 uint32_t pid = val & FEN_RWLOCK_PID_MASK;
302 0 ▶ if (!fen_pid_alive(pid))
Branch: 1 branch
BranchTrueFalseTotal
if (!fen_pid_alive(pid)) 0 0 0
303 0 fen_recover_stale_lock(h, val);
304 }
305 0 }
306  
307 /* Bump/drop the parked-waiter hint. Both readers (blocked at the gate) and
308 * writers (blocked acquiring wlock) wait on the wlock futex and use this, so
309 * wrunlock/recover know whether a FUTEX_WAKE is worth a syscall. A waiter
310 * SIGKILLed while parked leaves rwait over-counted -> at most a spurious wake
311 * (harmless); it can never under-count, so no wakeup is lost. */
312 0 static inline void fen_park(FenHandle *h) {
313 0 __atomic_add_fetch(&h->hdr->rwait, 1, __ATOMIC_SEQ_CST);
314 0 }
315 0 static inline void fen_unpark(FenHandle *h) {
316 0 __atomic_sub_fetch(&h->hdr->rwait, 1, __ATOMIC_RELAXED);
317 0 }
318  
319 /* Publish (inc) / retract (dec) this reader's presence -- its ENTIRE
320 * contribution to the lock. A slotted reader uses its slot's rdepth; a reader
321 * that could not claim a slot uses the global slotless_rdepth. inc() is SEQ_CST
322 * so the wlock re-check that follows it in rdlock forms a Dekker handshake with
323 * the writer's SEQ_CST wlock-store + rdepth-scan. dec() is SEQ_CST so its gate
324 * check cannot miss a draining writer. leave() peels slotless first
325 * so a slot claimed mid-hold cannot misattribute the decrement. */
326 1904 static inline void fen_rdepth_inc(FenHandle *h) {
327 1904 ▶ if (h->my_slot_idx != UINT32_MAX) {
Branch: 1 branch
BranchTrueFalseTotal
if (h->my_slot_idx != UINT32_MAX) { 1904 0 1904
328 1904 __atomic_add_fetch(&h->reader_slots[h->my_slot_idx].rdepth, 1, __ATOMIC_SEQ_CST);
329 } else {
330 0 __atomic_add_fetch(&h->hdr->slotless_rdepth, 1, __ATOMIC_SEQ_CST);
331 0 h->slotless_held++;
332 }
333 1904 }
334 1904 static inline void fen_rdepth_dec(FenHandle *h) {
335 1904 ▶ if (h->slotless_held > 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (h->slotless_held > 0) { 0 1904 1904
336 0 h->slotless_held--;
337 0 __atomic_sub_fetch(&h->hdr->slotless_rdepth, 1, __ATOMIC_SEQ_CST);
338 1904 ▶ } else if (h->my_slot_idx != UINT32_MAX) {
Branch: 1 branch
BranchTrueFalseTotal
} else if (h->my_slot_idx != UINT32_MAX) { 1904 0 1904
339 1904 __atomic_sub_fetch(&h->reader_slots[h->my_slot_idx].rdepth, 1, __ATOMIC_SEQ_CST);
340 }
341 1904 }
342  
343 /* Wake a writer that may be draining readers (it waits on drain_seq). Called
344 * after every rdepth decrement so a released read lock lets the writer re-scan
345 * promptly instead of waiting out its timeout. */
346 1904 static inline void fen_reader_wake_drain(FenHandle *h) {
347 1904 ▶ if (__atomic_load_n(&h->hdr->wlock, __ATOMIC_SEQ_CST) != 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&h->hdr->wlock, __ATOMIC_SEQ_CST) != 0) { 0 1904 1904
348 0 __atomic_add_fetch(&h->hdr->drain_seq, 1, __ATOMIC_RELEASE);
349 0 syscall(SYS_futex, &h->hdr->drain_seq, FUTEX_WAKE, 1, NULL, NULL, 0);
350 }
351 1904 }
352  
353 1904 static inline void fen_rwlock_rdlock(FenHandle *h) {
354 1904 fen_claim_reader_slot(h);
355 1904 FenHeader *hdr = h->hdr;
356 1904 for (int spin = 0; ; spin++) {
357 1904 uint32_t cur = __atomic_load_n(&hdr->wlock, __ATOMIC_ACQUIRE);
358 1904 ▶ if (cur == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (cur == 0) { 1904 0 1904
359 /* Optimistically take the read: publish rdepth, then re-check wlock.
360 * SEQ_CST inc + SEQ_CST load vs the writer's SEQ_CST wlock CAS +
361 * SEQ_CST rdepth scan: by the single total order of SEQ_CST ops the
362 * two sides cannot both miss each other, so we never hold
363 * concurrently with a writer. */
364 1904 fen_rdepth_inc(h);
365 1904 ▶ if (__atomic_load_n(&hdr->wlock, __ATOMIC_SEQ_CST) == 0)
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&hdr->wlock, __ATOMIC_SEQ_CST) == 0) 1904 0 1904
366 1904 return; /* no writer after our publish -> we hold the read lock */
367 /* A writer appeared during our publish -- yield to it (write-preferring). */
368 0 fen_rdepth_dec(h);
369 0 fen_reader_wake_drain(h); /* let the draining writer see rdepth drop */
370 0 spin = 0;
371 0 continue;
372 }
373 /* wlock != 0: a writer holds or is acquiring. Recover if it is dead. */
374 0 if (cur >= FEN_RWLOCK_WRITER_BIT &&
375 0 !fen_pid_alive(cur & FEN_RWLOCK_PID_MASK)) {
376 0 fen_recover_stale_lock(h, cur);
377 0 spin = 0;
378 0 continue;
379 }
380 0 ▶ if (__builtin_expect(spin < FEN_RWLOCK_SPIN_LIMIT, 1)) {
Branch: 1 branch
BranchTrueFalseTotal
if (__builtin_expect(spin < FEN_RWLOCK_SPIN_LIMIT, 1)) { 0 0 0
381 0 fen_rwlock_spin_pause();
382 0 continue;
383 }
384 0 fen_park(h);
385 0 cur = __atomic_load_n(&hdr->wlock, __ATOMIC_SEQ_CST);
386 0 ▶ if (cur != 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (cur != 0) { 0 0 0
387 0 long rc = syscall(SYS_futex, &hdr->wlock, FUTEX_WAIT, cur,
388 &fen_lock_timeout, NULL, 0);
389 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
390 0 fen_unpark(h);
391 0 fen_recover_after_timeout(h);
392 0 spin = 0;
393 0 continue;
394 }
395 }
396 0 fen_unpark(h);
397 0 spin = 0;
398 }
399 }
400  
401 1904 static inline void fen_rwlock_rdunlock(FenHandle *h) {
402 1904 fen_rdepth_dec(h); /* drop our entire contribution */
403 1904 fen_reader_wake_drain(h); /* if a writer is draining, wake it to re-scan */
404 1904 }
405  
406 1611 static inline void fen_rwlock_wrlock(FenHandle *h) {
407 1611 fen_claim_reader_slot(h); /* refresh cached_pid across fork */
408 1611 FenHeader *hdr = h->hdr;
409 /* Encode PID in the wlock word itself (0x80000000 | pid) to eliminate any
410 * crash window between acquiring the lock and storing the owner. */
411 1611 uint32_t mypid = FEN_RWLOCK_WR(h->cached_pid);
412 /* Phase 1: acquire the writer word (mutual exclusion among writers). */
413 1611 for (int spin = 0; ; spin++) {
414 1611 uint32_t expected = 0;
415 1611 ▶ if (__atomic_compare_exchange_n(&hdr->wlock, &expected, mypid,
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_compare_exchange_n(&hdr->wlock, &expected, mypid, 1611 0 1611
416 0, __ATOMIC_SEQ_CST, __ATOMIC_RELAXED))
417 1611 break;
418 /* Contended: expected now holds the current wlock value. */
419 0 if (expected >= FEN_RWLOCK_WRITER_BIT &&
420 0 !fen_pid_alive(expected & FEN_RWLOCK_PID_MASK)) {
421 0 fen_recover_stale_lock(h, expected);
422 0 spin = 0;
423 0 continue;
424 }
425 0 ▶ if (__builtin_expect(spin < FEN_RWLOCK_SPIN_LIMIT, 1)) {
Branch: 1 branch
BranchTrueFalseTotal
if (__builtin_expect(spin < FEN_RWLOCK_SPIN_LIMIT, 1)) { 0 0 0
426 0 fen_rwlock_spin_pause();
427 0 continue;
428 }
429 0 fen_park(h);
430 0 uint32_t cur = __atomic_load_n(&hdr->wlock, __ATOMIC_SEQ_CST);
431 0 ▶ if (cur != 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (cur != 0) { 0 0 0
432 0 long rc = syscall(SYS_futex, &hdr->wlock, FUTEX_WAIT, cur,
433 &fen_lock_timeout, NULL, 0);
434 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
435 0 fen_unpark(h);
436 0 fen_recover_after_timeout(h);
437 0 spin = 0;
438 0 continue;
439 }
440 }
441 0 fen_unpark(h);
442 0 spin = 0;
443 }
444 /* Phase 2: we own wlock, so no NEW reader can join (they see wlock!=0 and
445 * yield). Drain the readers that were already holding when we won the CAS.
446 * The SEQ_CST CAS above + the SEQ_CST rdepth loads below are the writer side
447 * of the Dekker handshake. */
448 0 for (;;) {
449 1611 uint32_t v = __atomic_load_n(&hdr->drain_seq, __ATOMIC_ACQUIRE); /* snapshot BEFORE scan */
450 1611 int busy = 0;
451 /* Visit only OCCUPIED slots via the occupancy bitmap (SEQ_CST: a committed
452 * reader's bit -- set in claim, before its rdepth++ -- is ordered before
453 * this scan, so no held slot is skipped). O(FEN_OCC_WORDS + live readers)
454 * instead of O(FEN_READER_SLOTS). */
455 27387 ▶ for (uint32_t w = 0; w < FEN_OCC_WORDS; w++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t w = 0; w < FEN_OCC_WORDS; w++) { 25776 1611 27387
456 25776 uint64_t word = __atomic_load_n(&h->occ[w], __ATOMIC_SEQ_CST);
457 27388 ▶ while (word) {
Branch: 1 branch
BranchTrueFalseTotal
while (word) { 1612 25776 27388
458 1612 uint32_t i = (w << 6) + (uint32_t)__builtin_ctzll(word);
459 1612 word &= word - 1; /* consume this bit (local copy) */
460 1612 uint32_t rd = __atomic_load_n(&h->reader_slots[i].rdepth, __ATOMIC_SEQ_CST);
461 1612 ▶ if (rd == 0) continue; /* occupied but not read-locking now */
Branch: 1 branch
BranchTrueFalseTotal
if (rd == 0) continue; /* occupied but not read-locking now */ 1612 0 1612
462 0 uint32_t pid = __atomic_load_n(&h->reader_slots[i].pid, __ATOMIC_ACQUIRE);
463 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
464 0 ▶ if (!fen_pid_alive(pid)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!fen_pid_alive(pid)) { 0 0 0
465 /* Dead reader: drop its pid so the slot no longer counts. Leave
466 * the occ bit set (harmless -- a later scan hits pid==0 and skips,
467 * a re-claim re-sets it) to avoid racing a concurrent claimant. */
468 0 uint32_t ep = pid;
469 0 __atomic_compare_exchange_n(&h->reader_slots[i].pid, &ep, 0,
470 0, __ATOMIC_ACQ_REL, __ATOMIC_RELAXED);
471 0 continue;
472 }
473 0 busy = 1; /* live reader still holding */
474 }
475 }
476 /* A live slotless reader keeps us waiting; a crashed slotless reader that
477 * cannot be attributed to a pid is the documented slotless limitation. */
478 1611 ▶ 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 1611 1611
479 0 busy = 1;
480 1611 ▶ if (!busy)
Branch: 1 branch
BranchTrueFalseTotal
if (!busy) 1611 0 1611
481 1611 return; /* exclusive: wlock held + every rdepth 0 */
482 /* Wait for a reader to release (drain_seq bump) or time out to re-scan
483 * (which reclaims any newly-dead slotted reader). */
484 0 syscall(SYS_futex, &hdr->drain_seq, FUTEX_WAIT, v, &fen_lock_timeout, NULL, 0);
485 }
486 }
487  
488 1611 static inline void fen_rwlock_wrunlock(FenHandle *h) {
489 1611 fen_release_writer(h->hdr);
490 1611 }
491  
492 /* ================================================================
493 * Layout math + create / open / destroy
494 *
495 * Layout: Header -> reader_slots[1024] -> occ bitmap -> tree[(n+1) int64]
496 * ================================================================ */
497  
498 /* Single source of truth for the mmap region layout offsets:
499 * Header -> reader_slots[] -> occ bitmap -> tree. */
500 typedef struct { uint64_t reader_slots, occ, tree; } FenLayout;
501  
502 193 static inline FenLayout fen_layout(void) {
503 FenLayout L;
504 193 L.reader_slots = sizeof(FenHeader);
505 193 L.occ = L.reader_slots + (uint64_t)FEN_READER_SLOTS * sizeof(FenReaderSlot);
506 193 L.tree = L.occ + FEN_OCC_BYTES;
507 193 L.tree = (L.tree + 7) & ~(uint64_t)7; /* 8-byte align the int64 tree array */
508 193 return L;
509 }
510  
511 /* the tree is 1-indexed: n+1 int64 slots, slot 0 unused. Range mode appends a
512 * second BIT of the same shape right after the first. */
513 57 static inline uint64_t fen_tree2_off_for(uint64_t n, uint32_t mode) {
514 57 ▶ if (mode != FEN_MODE_RANGE) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (mode != FEN_MODE_RANGE) return 0; 39 18 57
515 18 return fen_layout().tree + (n + 1) * sizeof(int64_t);
516 }
517 65 static inline uint64_t fen_total_size(uint64_t n, uint32_t mode) {
518 65 FenLayout L = fen_layout();
519 65 ▶ uint64_t trees = (mode == FEN_MODE_RANGE) ? 2 : 1;
Branch: 1 branch
BranchTrueFalseTotal
uint64_t trees = (mode == FEN_MODE_RANGE) ? 2 : 1; 19 46 65
520 65 return L.tree + trees * (n + 1) * sizeof(int64_t);
521 }
522  
523 42 static inline void fen_init_header(void *base, uint64_t n, uint32_t mode, uint64_t total) {
524 42 FenLayout L = fen_layout();
525 42 FenHeader *hdr = (FenHeader *)base;
526 /* Zero the header + reader-slot region (lock-recovery state); the tree array
527 relies on the fresh mapping being OS zero-filled (all prefix sums == 0). */
528 42 memset(base, 0, (size_t)L.tree);
529 42 hdr->version = FEN_VERSION;
530 42 hdr->mode = mode;
531 42 hdr->n = n;
532 42 hdr->capacity = n;
533 42 hdr->total_size = total;
534 42 hdr->reader_slots_off = L.reader_slots;
535 42 hdr->tree_off = L.tree;
536 42 hdr->tree2_off = fen_tree2_off_for(n, mode);
537 /* Publish magic LAST, as a release store: it is the commit point, so a
538 creator killed before it leaves magic==0 and never a file mistaken for
539 a valid one. A kill during the field stores leaves one to remove by
540 hand. */
541 42 __atomic_store_n(&hdr->magic, FEN_MAGIC, __ATOMIC_RELEASE);
542 42 __atomic_thread_fence(__ATOMIC_SEQ_CST);
543 42 }
544  
545 5001 static inline int64_t *fen_tree(FenHandle *h) {
546 5001 return (int64_t *)((char *)h->base + h->tree_off);
547 }
548  
549 /* Layer B trusted bound: number of int64 tree slots guaranteed within the real
550 * mapping. Derived from the process-local mmap_size (fixed at attach, not
551 * peer-writable) and the SAME tree_off fen_tree() uses, so a peer that corrupts
552 * hdr->n / tree_off after attach-time validation can never drive an access
553 * outside the mapping. Equals n+1 for a valid tree, so clamps are never taken. */
554 5001 static inline uint64_t fen_tree_slots_max(FenHandle *h) {
555 5001 uint64_t off = h->tree_off;
556 5001 ▶ if (off >= h->mmap_size) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (off >= h->mmap_size) return 0; 0 5001 5001
557 5001 return (h->mmap_size - off) / sizeof(int64_t);
558 }
559  
560 53 static inline FenHandle *fen_setup(void *base, size_t map_size,
561 const char *path, int backing_fd) {
562 53 FenHeader *hdr = (FenHeader *)base;
563 53 FenHandle *h = (FenHandle *)calloc(1, sizeof(FenHandle));
564 53 ▶ if (h && path) h->path = strdup(path);
Branch: 2 branches
BranchTrueFalseTotal
if (h && path) h->path = strdup(path); 53 0 53
if (h && path) h->path = strdup(path); 22 31 53
565 53 ▶ if (!h || (path && !h->path)) {
Branch: 3 branches
BranchTrueFalseTotal
if (!h || (path && !h->path)) { 53 0 53
if (!h || (path && !h->path)) { 22 31 53
if (!h || (path && !h->path)) { 0 22 22
566 0 free(h);
567 0 munmap(base, map_size);
568 0 ▶ if (backing_fd >= 0) close(backing_fd);
Branch: 1 branch
BranchTrueFalseTotal
if (backing_fd >= 0) close(backing_fd); 0 0 0
569 0 return NULL;
570 }
571 53 h->hdr = hdr;
572 53 h->base = base;
573 53 h->reader_slots = (FenReaderSlot *)((uint8_t *)base + sizeof(FenHeader)); /* trusted layout, not the peer-writable header offset */
574 53 h->occ = (uint64_t *)((uint8_t *)base + fen_layout().occ); /* trusted layout offset */
575 53 h->tree_off = hdr->tree_off; /* single validated read; bound and pointer stay consistent */
576 53 h->tree2_off = hdr->tree2_off;
577 53 h->mode = hdr->mode;
578 53 h->mmap_size = map_size;
579 53 h->backing_fd = backing_fd;
580 53 h->my_slot_idx = UINT32_MAX;
581 53 return h;
582 }
583  
584 /* Validate a mapped header (shared by fen_create reopen and fen_open_fd). */
585 19 static inline int fen_validate_header(const FenHeader *hdr, uint64_t file_size) {
586 19 ▶ if (__atomic_load_n(&hdr->magic, __ATOMIC_ACQUIRE) != FEN_MAGIC) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&hdr->magic, __ATOMIC_ACQUIRE) != FEN_MAGIC) return 0; 4 15 19
587 15 ▶ if (hdr->version != FEN_VERSION) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->version != FEN_VERSION) return 0; 0 15 15
588 15 ▶ if (hdr->mode != FEN_MODE_POINT && hdr->mode != FEN_MODE_RANGE) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (hdr->mode != FEN_MODE_POINT && hdr->mode != FEN_MODE_RANGE) return 0; 5 10 15
if (hdr->mode != FEN_MODE_POINT && hdr->mode != FEN_MODE_RANGE) return 0; 0 5 5
589 15 ▶ if (hdr->n < FEN_MIN_N || hdr->n > FEN_MAX_N) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (hdr->n < FEN_MIN_N || hdr->n > FEN_MAX_N) return 0; 15 0 15
if (hdr->n < FEN_MIN_N || hdr->n > FEN_MAX_N) return 0; 0 15 15
590 15 ▶ if (hdr->capacity != hdr->n) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->capacity != hdr->n) return 0; 0 15 15
591 15 ▶ if (hdr->tree2_off != fen_tree2_off_for(hdr->n, hdr->mode)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->tree2_off != fen_tree2_off_for(hdr->n, hdr->mode)) return 0; 0 15 15
592 15 ▶ if (hdr->total_size != file_size) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->total_size != file_size) return 0; 0 15 15
593 15 ▶ if (hdr->total_size != fen_total_size(hdr->n, hdr->mode)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->total_size != fen_total_size(hdr->n, hdr->mode)) return 0; 0 15 15
594 15 FenLayout L = fen_layout();
595 15 ▶ 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 15 15
596 15 ▶ if (hdr->tree_off != L.tree) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->tree_off != L.tree) return 0; 0 15 15
597 15 return 1;
598 }
599  
600 /* validate the requested number of positions n */
601 50 static int fen_validate_n(uint64_t n, char *errbuf) {
602 50 ▶ if (errbuf) errbuf[0] = '\0';
Branch: 1 branch
BranchTrueFalseTotal
if (errbuf) errbuf[0] = '\0'; 50 0 50
603 50 ▶ if (n < FEN_MIN_N) { FEN_ERR("n (number of positions) must be >= 1"); return 0; }
Branch: 2 branches
BranchTrueFalseTotal
if (n < FEN_MIN_N) { FEN_ERR("n (number of positions) must be >= 1"); return 0; } 0 50 50
if (n < FEN_MIN_N) { FEN_ERR("n (number of positions) must be >= 1"); return 0; } 0 0 0
604 50 ▶ if (n > FEN_MAX_N) { FEN_ERR("n too large for the tree cap"); return 0; }
Branch: 2 branches
BranchTrueFalseTotal
if (n > FEN_MAX_N) { FEN_ERR("n too large for the tree cap"); return 0; } 0 50 50
if (n > FEN_MAX_N) { FEN_ERR("n too large for the tree cap"); return 0; } 0 0 0
605 50 return 1;
606 }
607  
608 /* Securely obtain a fd for a path-backed segment: create it exclusively
609 * (O_CREAT|O_EXCL|O_NOFOLLOW at `mode`, default 0600 = owner-only), or, if it
610 * already exists, attach to it (O_RDWR|O_NOFOLLOW, no O_CREAT). O_EXCL blocks a
611 * pre-seeded or hard-linked file and O_NOFOLLOW a symlink swap, so a local
612 * attacker can no longer redirect or poison the backing store through the path.
613 * Cross-user sharing is opt-in via a wider `mode` (e.g. 0660); the caller still
614 * validates the file's contents via fen_validate_header. */
615 21 static int fen_secure_open(const char *path, mode_t mode, char *errbuf) {
616 21 ▶ for (int attempt = 0; attempt < 100; attempt++) {
Branch: 1 branch
BranchTrueFalseTotal
for (int attempt = 0; attempt < 100; attempt++) { 21 0 21
617 21 int fd = open(path, O_RDWR|O_CREAT|O_EXCL|O_NOFOLLOW|O_CLOEXEC, mode);
618 21 ▶ 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 */ 12 9 21
619 9 ▶ if (errno != EEXIST) { FEN_ERR("create %s: %s", path, strerror(errno)); return -1; }
Branch: 2 branches
BranchTrueFalseTotal
if (errno != EEXIST) { FEN_ERR("create %s: %s", path, strerror(errno)); return -1; } 0 9 9
if (errno != EEXIST) { FEN_ERR("create %s: %s", path, strerror(errno)); return -1; } 0 0 0
620 9 fd = open(path, O_RDWR|O_NOFOLLOW|O_CLOEXEC);
621 9 ▶ if (fd >= 0) return fd;
Branch: 1 branch
BranchTrueFalseTotal
if (fd >= 0) return fd; 9 0 9
622 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
623 0 ▶ FEN_ERR("open %s: %s", path, strerror(errno)); /* ELOOP => symlink rejected */
Branch: 1 branch
BranchTrueFalseTotal
FEN_ERR("open %s: %s", path, strerror(errno)); /* ELOOP => symlink rejected */ 0 0 0
624 0 return -1;
625 }
626 0 ▶ FEN_ERR("open %s: create/attach kept racing", path);
Branch: 1 branch
BranchTrueFalseTotal
FEN_ERR("open %s: create/attach kept racing", path); 0 0 0
627 0 return -1;
628 }
629  
630 /* True iff the whole file is zero -- what an abandoned mid-init
631 creator leaves. Lets recovery re-init only a provably-empty file, never
632 one that merely starts with a zero word. Cold path, so a byte scan is
633 fine. Read, not mapped: a read fault on a tmpfs hole allocates the page. */
634 2 static int fen_file_is_zero(int fd, uint64_t size) {
635 char buf[16384];
636 5 ▶ for (uint64_t off = 0; off < size; ) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint64_t off = 0; off < size; ) { 4 1 5
637 4 ssize_t n = pread(fd, buf, size - off < sizeof buf ? (size_t)(size - off) : sizeof buf, (off_t)off);
638 4 ▶ if (n <= 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (n <= 0) return 0; 0 4 4
639 34355 ▶ 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 34351 34352
for (ssize_t i = 0; i < n; i++) if (buf[i]) return 0; 34352 3 34355
640 3 off += (uint64_t)n;
641 }
642 1 return 1;
643 }
644  
645 /* Opt-in (DATA_FENWICK_SHARED_SPARSE=0): reserving commits memory this module otherwise fills lazily. */
646 17 static int fen_reserve(int fd, uint64_t size) {
647 17 const char *sp = getenv("DATA_FENWICK_SHARED_SPARSE");
648 17 ▶ if (!sp || strcmp(sp, "0")) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (!sp || strcmp(sp, "0")) return 0; 0 17 17
if (!sp || strcmp(sp, "0")) return 0; 0 0 0
649 /* Before Linux 6.11 tmpfs gives up at any pending signal and undoes the allocation, so a
650 * periodic one could keep it from ever completing; SIGSTOP cannot be blocked. */
651 sigset_t all, old;
652 0 sigfillset(&all);
653 0 sigprocmask(SIG_BLOCK, &all, &old);
654 int e;
655 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
656 0 sigprocmask(SIG_SETMASK, &old, NULL);
657 0 ▶ if (e == 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (e == 0) return 0; 0 0 0
658 0 errno = e;
659 0 return -1;
660 }
661  
662 46 static FenHandle *fen_create(const char *path, uint64_t n, uint32_t fmode, mode_t mode, char *errbuf) {
663 46 ▶ if (!fen_validate_n(n, errbuf)) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!fen_validate_n(n, errbuf)) return NULL; 0 46 46
664  
665 46 uint64_t total = fen_total_size(n, fmode);
666 46 int anonymous = (path == NULL);
667 46 int fd = -1;
668 size_t map_size;
669 void *base;
670  
671 46 ▶ if (anonymous) {
Branch: 1 branch
BranchTrueFalseTotal
if (anonymous) { 25 21 46
672 25 map_size = (size_t)total;
673 25 base = mmap(NULL, map_size, PROT_READ|PROT_WRITE, MAP_SHARED|MAP_ANONYMOUS, -1, 0);
674 25 ▶ if (base == MAP_FAILED) { FEN_ERR("mmap: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { FEN_ERR("mmap: %s", strerror(errno)); return NULL; } 0 25 25
if (base == MAP_FAILED) { FEN_ERR("mmap: %s", strerror(errno)); return NULL; } 0 0 0
675 } else {
676 21 fd = fen_secure_open(path, mode, errbuf);
677 30 ▶ if (fd < 0) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (fd < 0) return NULL; 0 21 21
678 21 ▶ if (flock(fd, LOCK_EX) < 0) { FEN_ERR("flock: %s", strerror(errno)); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (flock(fd, LOCK_EX) < 0) { FEN_ERR("flock: %s", strerror(errno)); close(fd); return NULL; } 0 21 21
if (flock(fd, LOCK_EX) < 0) { FEN_ERR("flock: %s", strerror(errno)); close(fd); return NULL; } 0 0 0
679 struct stat st;
680 21 ▶ if (fstat(fd, &st) < 0) { FEN_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fstat(fd, &st) < 0) { FEN_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; } 0 21 21
if (fstat(fd, &st) < 0) { FEN_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; } 0 0 0
681 21 int is_new = (st.st_size == 0);
682 21 ▶ if (!is_new && (uint64_t)st.st_size < sizeof(FenHeader)) {
Branch: 2 branches
BranchTrueFalseTotal
if (!is_new && (uint64_t)st.st_size < sizeof(FenHeader)) { 9 12 21
if (!is_new && (uint64_t)st.st_size < sizeof(FenHeader)) { 1 8 9
683 1 ▶ FEN_ERR("%s: file too small (%lld)", path, (long long)st.st_size);
Branch: 1 branch
BranchTrueFalseTotal
FEN_ERR("%s: file too small (%lld)", path, (long long)st.st_size); 1 0 1
684 1 flock(fd, LOCK_UN); close(fd); return NULL;
685 }
686 20 ▶ 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)) { 12 8 20
if (is_new && (st.st_uid != geteuid() || fchmod(fd, mode) < 0)) { 12 0 12
if (is_new && (st.st_uid != geteuid() || fchmod(fd, mode) < 0)) { 0 12 12
687 0 ▶ FEN_ERR("%s: refusing to initialize file not owned by us", path);
Branch: 1 branch
BranchTrueFalseTotal
FEN_ERR("%s: refusing to initialize file not owned by us", path); 0 0 0
688 0 flock(fd, LOCK_UN); close(fd); return NULL;
689 }
690 20 ▶ if (is_new && ftruncate(fd, (off_t)total) < 0) {
Branch: 2 branches
BranchTrueFalseTotal
if (is_new && ftruncate(fd, (off_t)total) < 0) { 12 8 20
if (is_new && ftruncate(fd, (off_t)total) < 0) { 0 12 12
691 0 ▶ FEN_ERR("ftruncate: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
FEN_ERR("ftruncate: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; 0 0 0
692 }
693 20 ▶ if (is_new && fen_reserve(fd, total) < 0) {
Branch: 2 branches
BranchTrueFalseTotal
if (is_new && fen_reserve(fd, total) < 0) { 12 8 20
if (is_new && fen_reserve(fd, total) < 0) { 0 12 12
694 0 ▶ FEN_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
FEN_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno)); 0 0 0
695 0 if (ftruncate(fd, 0) < 0) { /* best effort */ }
696 0 flock(fd, LOCK_UN); close(fd); return NULL;
697 }
698 20 ▶ 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; 8 12 20
699 20 base = mmap(NULL, map_size, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
700 20 ▶ if (base == MAP_FAILED) {
Branch: 1 branch
BranchTrueFalseTotal
if (base == MAP_FAILED) { 0 20 20
701 0 ▶ FEN_ERR("mmap: %s", strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
FEN_ERR("mmap: %s", strerror(errno)); 0 0 0
702 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
703 0 flock(fd, LOCK_UN); close(fd); return NULL;
704 }
705 20 ▶ if (!is_new) {
Branch: 1 branch
BranchTrueFalseTotal
if (!is_new) { 8 12 20
706 8 ▶ if (!fen_validate_header((FenHeader *)base, (uint64_t)st.st_size)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!fen_validate_header((FenHeader *)base, (uint64_t)st.st_size)) { 4 4 8
707 /* Recover an abandoned mid-init file: a creator killed
708 * between the ftruncate and the header init leaves a
709 * full-size, all-zero (magic==0) file that would brick every
710 * future open of this path. Re-initialize ONLY when it is
711 * exactly our size, still uninitialized, and owned by us;
712 * anything else still errors. */
713 4 ▶ if (((FenHeader *)base)->magic == 0 && (uint64_t)st.st_size == total
Branch: 2 branches
BranchTrueFalseTotal
if (((FenHeader *)base)->magic == 0 && (uint64_t)st.st_size == total 3 1 4
if (((FenHeader *)base)->magic == 0 && (uint64_t)st.st_size == total 2 1 3
714 2 ▶ && st.st_uid == geteuid() && fen_file_is_zero(fd, map_size)) {
Branch: 2 branches
BranchTrueFalseTotal
&& st.st_uid == geteuid() && fen_file_is_zero(fd, map_size)) { 2 0 2
&& st.st_uid == geteuid() && fen_file_is_zero(fd, map_size)) { 1 1 2
715 1 ▶ if (fchmod(fd, mode) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (fchmod(fd, mode) < 0) { 0 1 1
716 0 ▶ FEN_ERR("%s: fchmod: %s", path, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
FEN_ERR("%s: fchmod: %s", path, strerror(errno)); 0 0 0
717 0 munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
718 }
719 1 ▶ if (fen_reserve(fd, total) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (fen_reserve(fd, total) < 0) { 0 1 1
720 0 ▶ FEN_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
FEN_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno)); 0 0 0
721 0 munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
722 }
723 1 fen_init_header(base, n, fmode, total);
724 1 flock(fd, LOCK_UN); close(fd);
725 1 return fen_setup(base, map_size, path, -1);
726 }
727 3 ▶ if (((FenHeader *)base)->magic == 0 && (uint64_t)st.st_size == total
Branch: 2 branches
BranchTrueFalseTotal
if (((FenHeader *)base)->magic == 0 && (uint64_t)st.st_size == total 2 1 3
if (((FenHeader *)base)->magic == 0 && (uint64_t)st.st_size == total 1 1 2
728 1 ▶ && st.st_uid == geteuid()) {
Branch: 1 branch
BranchTrueFalseTotal
&& st.st_uid == geteuid()) { 1 0 1
729 1 ▶ FEN_ERR("%s: incomplete Fenwick tree file left by an interrupted create; remove it and retry", path);
Branch: 1 branch
BranchTrueFalseTotal
FEN_ERR("%s: incomplete Fenwick tree file left by an interrupted create; remove it and retry", path); 1 0 1
730 1 munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
731 }
732 2 ▶ FEN_ERR("invalid Fenwick tree file"); munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
FEN_ERR("invalid Fenwick tree file"); munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL; 2 0 2
733 }
734 4 ▶ if (__atomic_load_n(&((FenHeader *)base)->sealed, __ATOMIC_RELAXED)) {
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&((FenHeader *)base)->sealed, __ATOMIC_RELAXED)) { 1 3 4
735 1 ▶ FEN_ERR("%s is frozen (read-only); open it with new_readonly", path);
Branch: 1 branch
BranchTrueFalseTotal
FEN_ERR("%s is frozen (read-only); open it with new_readonly", path); 1 0 1
736 1 munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
737 }
738 3 flock(fd, LOCK_UN); close(fd);
739 3 return fen_setup(base, map_size, path, -1);
740 }
741 }
742 37 fen_init_header(base, n, fmode, total);
743 37 ▶ if (fd >= 0) { flock(fd, LOCK_UN); close(fd); }
Branch: 1 branch
BranchTrueFalseTotal
if (fd >= 0) { flock(fd, LOCK_UN); close(fd); } 12 25 37
744 37 return fen_setup(base, map_size, path, -1);
745 }
746  
747 4 static FenHandle *fen_create_memfd(const char *name, uint64_t n, uint32_t fmode, char *errbuf) {
748 4 ▶ if (!fen_validate_n(n, errbuf)) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!fen_validate_n(n, errbuf)) return NULL; 0 4 4
749  
750 4 uint64_t total = fen_total_size(n, fmode);
751 4 ▶ int fd = memfd_create(name ? name : "fenwick", MFD_CLOEXEC | MFD_ALLOW_SEALING);
Branch: 1 branch
BranchTrueFalseTotal
int fd = memfd_create(name ? name : "fenwick", MFD_CLOEXEC | MFD_ALLOW_SEALING); 4 0 4
752 4 ▶ if (fd < 0) { FEN_ERR("memfd_create: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fd < 0) { FEN_ERR("memfd_create: %s", strerror(errno)); return NULL; } 0 4 4
if (fd < 0) { FEN_ERR("memfd_create: %s", strerror(errno)); return NULL; } 0 0 0
753 4 ▶ if (ftruncate(fd, (off_t)total) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (ftruncate(fd, (off_t)total) < 0) { 0 4 4
754 0 ▶ FEN_ERR("ftruncate: %s", strerror(errno)); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
FEN_ERR("ftruncate: %s", strerror(errno)); close(fd); return NULL; 0 0 0
755 }
756 4 ▶ if (fen_reserve(fd, total) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (fen_reserve(fd, total) < 0) { 0 4 4
757 0 ▶ FEN_ERR("memfd: cannot reserve %llu bytes: %s", (unsigned long long)total, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
FEN_ERR("memfd: cannot reserve %llu bytes: %s", (unsigned long long)total, strerror(errno)); 0 0 0
758 0 close(fd); return NULL;
759 }
760 4 (void)fcntl(fd, F_ADD_SEALS, F_SEAL_SHRINK | F_SEAL_GROW);
761 4 void *base = mmap(NULL, (size_t)total, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
762 4 ▶ if (base == MAP_FAILED) { FEN_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { FEN_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; } 0 4 4
if (base == MAP_FAILED) { FEN_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; } 0 0 0
763 4 fen_init_header(base, n, fmode, total);
764 4 return fen_setup(base, (size_t)total, NULL, fd);
765 }
766  
767 3 static FenHandle *fen_open_fd(int fd, char *errbuf) {
768 3 ▶ if (errbuf) errbuf[0] = '\0';
Branch: 1 branch
BranchTrueFalseTotal
if (errbuf) errbuf[0] = '\0'; 3 0 3
769 struct stat st;
770 3 ▶ if (fstat(fd, &st) < 0) { FEN_ERR("fstat: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fstat(fd, &st) < 0) { FEN_ERR("fstat: %s", strerror(errno)); return NULL; } 0 3 3
if (fstat(fd, &st) < 0) { FEN_ERR("fstat: %s", strerror(errno)); return NULL; } 0 0 0
771 3 ▶ if ((uint64_t)st.st_size < sizeof(FenHeader)) { FEN_ERR("too small"); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if ((uint64_t)st.st_size < sizeof(FenHeader)) { FEN_ERR("too small"); return NULL; } 0 3 3
if ((uint64_t)st.st_size < sizeof(FenHeader)) { FEN_ERR("too small"); return NULL; } 0 0 0
772 /* before mmap: a creator may truncate the file until it has set magic */
773 uint32_t magic;
774 3 ▶ if (pread(fd, &magic, sizeof magic, offsetof(FenHeader, magic)) != (ssize_t)sizeof magic || magic != FEN_MAGIC) {
Branch: 2 branches
BranchTrueFalseTotal
if (pread(fd, &magic, sizeof magic, offsetof(FenHeader, magic)) != (ssize_t)sizeof magic || magic != FEN_MAGIC) { 3 0 3
if (pread(fd, &magic, sizeof magic, offsetof(FenHeader, magic)) != (ssize_t)sizeof magic || magic != FEN_MAGIC) { 0 3 3
775 0 ▶ FEN_ERR("invalid Fenwick tree table"); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
FEN_ERR("invalid Fenwick tree table"); return NULL; 0 0 0
776 }
777 3 size_t ms = (size_t)st.st_size;
778 3 void *base = mmap(NULL, ms, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
779 3 ▶ if (base == MAP_FAILED) { FEN_ERR("mmap: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { FEN_ERR("mmap: %s", strerror(errno)); return NULL; } 0 3 3
if (base == MAP_FAILED) { FEN_ERR("mmap: %s", strerror(errno)); return NULL; } 0 0 0
780 3 ▶ if (!fen_validate_header((FenHeader *)base, (uint64_t)st.st_size)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!fen_validate_header((FenHeader *)base, (uint64_t)st.st_size)) { 0 3 3
781 0 ▶ FEN_ERR("invalid Fenwick tree table"); munmap(base, ms); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
FEN_ERR("invalid Fenwick tree table"); munmap(base, ms); return NULL; 0 0 0
782 }
783 3 ▶ if (__atomic_load_n(&((FenHeader *)base)->sealed, __ATOMIC_RELAXED)) {
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&((FenHeader *)base)->sealed, __ATOMIC_RELAXED)) { 1 2 3
784 1 ▶ FEN_ERR("this Fenwick tree is frozen (read-only); open it with new_readonly");
Branch: 1 branch
BranchTrueFalseTotal
FEN_ERR("this Fenwick tree is frozen (read-only); open it with new_readonly"); 1 0 1
785 1 munmap(base, ms); return NULL;
786 }
787 2 int myfd = fcntl(fd, F_DUPFD_CLOEXEC, 0);
788 2 ▶ if (myfd < 0) { FEN_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (myfd < 0) { FEN_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; } 0 2 2
if (myfd < 0) { FEN_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; } 0 0 0
789 2 return fen_setup(base, ms, NULL, myfd);
790 }
791  
792 /* Open a FROZEN (sealed) file read-only: O_RDONLY + PROT_READ, no lock ever.
793 * A sealed file is immutable and no read path writes the mapping, so queries
794 * take no reader-slot / rwlock traffic and any number of processes can share
795 * one PROT_READ mapping (same architecture; the magic rejects a wrong-endian
796 * file). */
797 9 static FenHandle *fen_open_readonly(const char *path, char *errbuf) {
798 9 ▶ if (errbuf) errbuf[0] = '\0';
Branch: 1 branch
BranchTrueFalseTotal
if (errbuf) errbuf[0] = '\0'; 9 0 9
799 9 int fd = open(path, O_RDONLY|O_NOFOLLOW|O_CLOEXEC);
800 9 ▶ if (fd < 0) { FEN_ERR("open %s: %s", path, strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fd < 0) { FEN_ERR("open %s: %s", path, strerror(errno)); return NULL; } 1 8 9
if (fd < 0) { FEN_ERR("open %s: %s", path, strerror(errno)); return NULL; } 1 0 1
801 struct stat st;
802 8 ▶ if (fstat(fd, &st) < 0) { FEN_ERR("fstat %s: %s", path, strerror(errno)); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fstat(fd, &st) < 0) { FEN_ERR("fstat %s: %s", path, strerror(errno)); close(fd); return NULL; } 0 8 8
if (fstat(fd, &st) < 0) { FEN_ERR("fstat %s: %s", path, strerror(errno)); close(fd); return NULL; } 0 0 0
803 8 ▶ if ((uint64_t)st.st_size < sizeof(FenHeader)) { FEN_ERR("%s: file too small", path); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if ((uint64_t)st.st_size < sizeof(FenHeader)) { FEN_ERR("%s: file too small", path); close(fd); return NULL; } 0 8 8
if ((uint64_t)st.st_size < sizeof(FenHeader)) { FEN_ERR("%s: file too small", path); close(fd); return NULL; } 0 0 0
804 /* before mmap: a creator may truncate the file until it has set magic */
805 uint32_t magic;
806 8 ▶ if (pread(fd, &magic, sizeof magic, offsetof(FenHeader, magic)) != (ssize_t)sizeof magic || magic != FEN_MAGIC) {
Branch: 2 branches
BranchTrueFalseTotal
if (pread(fd, &magic, sizeof magic, offsetof(FenHeader, magic)) != (ssize_t)sizeof magic || magic != FEN_MAGIC) { 8 0 8
if (pread(fd, &magic, sizeof magic, offsetof(FenHeader, magic)) != (ssize_t)sizeof magic || magic != FEN_MAGIC) { 0 8 8
807 0 ▶ FEN_ERR("%s: invalid Fenwick tree file", path); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
FEN_ERR("%s: invalid Fenwick tree file", path); close(fd); return NULL; 0 0 0
808 }
809 8 size_t ms = (size_t)st.st_size;
810 8 void *base = mmap(NULL, ms, PROT_READ, MAP_SHARED, fd, 0);
811 8 close(fd); /* the mapping keeps the file; a read-only view needs no fd (no msync/ftruncate) */
812 8 ▶ if (base == MAP_FAILED) { FEN_ERR("mmap %s: %s", path, strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { FEN_ERR("mmap %s: %s", path, strerror(errno)); return NULL; } 0 8 8
if (base == MAP_FAILED) { FEN_ERR("mmap %s: %s", path, strerror(errno)); return NULL; } 0 0 0
813 8 ▶ if (!fen_validate_header((FenHeader *)base, (uint64_t)st.st_size)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!fen_validate_header((FenHeader *)base, (uint64_t)st.st_size)) { 0 8 8
814 0 ▶ FEN_ERR("%s: invalid Fenwick tree file", path); munmap(base, ms); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
FEN_ERR("%s: invalid Fenwick tree file", path); munmap(base, ms); return NULL; 0 0 0
815 }
816 8 ▶ if (!__atomic_load_n(&((FenHeader *)base)->sealed, __ATOMIC_ACQUIRE)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!__atomic_load_n(&((FenHeader *)base)->sealed, __ATOMIC_ACQUIRE)) { 2 6 8
817 2 ▶ FEN_ERR("%s is not frozen: call ->freeze on the producer before opening read-only", path);
Branch: 1 branch
BranchTrueFalseTotal
FEN_ERR("%s is not frozen: call ->freeze on the producer before opening read-only", path); 2 0 2
818 2 munmap(base, ms); return NULL;
819 }
820 6 FenHandle *h = fen_setup(base, ms, path, -1); /* munmaps on OOM */
821 6 ▶ if (!h) { FEN_ERR("out of memory"); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (!h) { FEN_ERR("out of memory"); return NULL; } 0 6 6
if (!h) { FEN_ERR("out of memory"); return NULL; } 0 0 0
822 6 h->readonly = 1;
823 6 return h;
824 }
825  
826 53 static void fen_destroy(FenHandle *h) {
827 53 ▶ if (!h) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!h) return; 0 53 53
828 /* Release our reader slot on clean teardown (else short-lived-reader churn
829 * exhausts the slot table); skip if a read lock is still held (rdepth>0). */
830 53 ▶ 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 && 53 0 53
if (h->reader_slots && h->my_slot_idx != UINT32_MAX && h->cached_pid && 39 14 53
if (h->reader_slots && h->my_slot_idx != UINT32_MAX && h->cached_pid && 39 0 39
831 39 ▶ h->cached_fork_gen == __atomic_load_n(&fen_fork_gen, __ATOMIC_RELAXED) &&
Branch: 1 branch
BranchTrueFalseTotal
h->cached_fork_gen == __atomic_load_n(&fen_fork_gen, __ATOMIC_RELAXED) && 39 0 39
832 39 ▶ __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) { 39 0 39
833 /* Clear our occ bit BEFORE freeing the slot: we still own the pid so no
834 * claimant can take the slot mid-clear, and rdepth==0 so no writer needs
835 * to see us. (A crash skips this -> the bit is reclaimed lazily by a
836 * writer scan / re-claim, same as the pid.) */
837 39 fen_occ_clear(h, h->my_slot_idx);
838 39 uint32_t expected = h->cached_pid;
839 39 __atomic_compare_exchange_n(&h->reader_slots[h->my_slot_idx].pid,
840 &expected, 0, 0, __ATOMIC_RELEASE, __ATOMIC_RELAXED);
841 }
842 53 ▶ if (h->backing_fd >= 0) close(h->backing_fd);
Branch: 1 branch
BranchTrueFalseTotal
if (h->backing_fd >= 0) close(h->backing_fd); 6 47 53
843 53 ▶ if (h->base) munmap(h->base, h->mmap_size);
Branch: 1 branch
BranchTrueFalseTotal
if (h->base) munmap(h->base, h->mmap_size); 53 0 53
844 53 free(h->path);
845 53 free(h);
846 }
847  
848 6 static inline int fen_msync(FenHandle *h) {
849 6 ▶ if (!h || !h->base) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (!h || !h->base) return 0; 6 0 6
if (!h || !h->base) return 0; 0 6 6
850 6 return msync(h->base, h->mmap_size, MS_SYNC);
851 }
852  
853 /* Seal a tree: make it permanently immutable so it can be shipped and opened
854 * read-only. Takes the write lock so no update is in flight, publishes the
855 * seal, then flushes it (file/memfd-backed). Afterwards every mutator croaks
856 * and a read-write reopen is refused. */
857 3 static int fen_freeze(FenHandle *h) {
858 3 fen_rwlock_wrlock(h);
859 3 __atomic_store_n(&h->hdr->sealed, 1, __ATOMIC_RELEASE);
860 3 fen_rwlock_wrunlock(h);
861 3 ▶ if (h->path || h->backing_fd >= 0) return fen_msync(h); /* durability for file/memfd-backed */
Branch: 2 branches
BranchTrueFalseTotal
if (h->path || h->backing_fd >= 0) return fen_msync(h); /* durability for file/memfd-backed */ 0 3 3
if (h->path || h->backing_fd >= 0) return fen_msync(h); /* durability for file/memfd-backed */ 0 0 0
862 0 return 0; /* anonymous: the seal lives in shared memory (visible to forks); nothing to flush */
863 }
864  
865 /* ================================================================
866 * Fenwick tree (binary indexed tree) operations -- callers hold the lock.
867 * 1-indexed: positions 1..n; tree[x] holds the sum of (x - lowbit(x), x],
868 * lowbit(x) = x & -x. Values are signed int64 (deltas may be negative).
869 * ================================================================ */
870  
871 27460 static inline uint64_t fen_lowbit(uint64_t x) { return x & (~x + 1ULL); }
872  
873 /* highest 1-based index safely inside the mapping (min of n and the Layer-B bound) */
874 1611 static inline uint64_t fen_nmax(FenHandle *h) {
875 1611 uint64_t nn = h->hdr->n;
876 1611 uint64_t smax = fen_tree_slots_max(h); /* n+1 for a valid tree */
877 1611 ▶ uint64_t hi = smax ? smax - 1 : 0; /* highest valid 1-based index */
Branch: 1 branch
BranchTrueFalseTotal
uint64_t hi = smax ? smax - 1 : 0; /* highest valid 1-based index */ 1611 0 1611
878 1611 return nn < hi ? nn : hi;
879 }
880  
881 /* add delta at position i (1-based); caller guarantees 1 <= i <= n */
882 1089 static void fen_update_locked(FenHandle *h, uint64_t i, int64_t delta) {
883 1089 int64_t *tree = fen_tree(h);
884 1089 uint64_t nmax = fen_nmax(h);
885 5639 ▶ for (uint64_t x = i; x >= 1 && x <= nmax; x += fen_lowbit(x))
Branch: 2 branches
BranchTrueFalseTotal
for (uint64_t x = i; x >= 1 && x <= nmax; x += fen_lowbit(x)) 5639 0 5639
for (uint64_t x = i; x >= 1 && x <= nmax; x += fen_lowbit(x)) 4550 1089 5639
886 4550 tree[x] = (int64_t)((uint64_t)tree[x] + (uint64_t)delta);
887 1089 }
888  
889 /* prefix sum over positions 1..i (1-based); caller guarantees 0 <= i <= n */
890 513 static int64_t fen_prefix_locked(FenHandle *h, uint64_t i) {
891 513 const int64_t *tree = fen_tree(h);
892 513 uint64_t nmax = fen_nmax(h);
893 513 ▶ if (i > nmax) i = nmax; /* Layer B: never read past the mapping */
Branch: 1 branch
BranchTrueFalseTotal
if (i > nmax) i = nmax; /* Layer B: never read past the mapping */ 0 513 513
894 513 uint64_t s = 0;
895 2207 ▶ for (uint64_t x = i; x > 0; x -= fen_lowbit(x))
Branch: 1 branch
BranchTrueFalseTotal
for (uint64_t x = i; x > 0; x -= fen_lowbit(x)) 1694 513 2207
896 1694 s += (uint64_t)tree[x];
897 513 return (int64_t)s;
898 }
899  
900 /* sum over positions l..r inclusive (1-based); caller guarantees 1 <= l <= r <= n */
901 137 static int64_t fen_range_locked(FenHandle *h, uint64_t l, uint64_t r) {
902 137 return (int64_t)((uint64_t)fen_prefix_locked(h, r)
903 137 - (uint64_t)fen_prefix_locked(h, l - 1));
904 }
905  
906 /* smallest position i with prefix(i) >= target, or n+1 if none. Binary lifting;
907 * meaningful when all stored values are non-negative (rank / weighted lookup). */
908 9 static uint64_t fen_lower_bound_locked(FenHandle *h, int64_t target) {
909 9 const int64_t *tree = fen_tree(h);
910 9 uint64_t nmax = fen_nmax(h);
911 9 uint64_t pos = 0, step = 1;
912 9 int64_t acc = 0;
913 38 ▶ while ((step << 1) && (step << 1) <= nmax) step <<= 1; /* largest power of two <= nmax */
Branch: 2 branches
BranchTrueFalseTotal
while ((step << 1) && (step << 1) <= nmax) step <<= 1; /* largest power of two <= nmax */ 38 0 38
while ((step << 1) && (step << 1) <= nmax) step <<= 1; /* largest power of two <= nmax */ 29 9 38
914 47 ▶ for (; step > 0; step >>= 1) {
Branch: 1 branch
BranchTrueFalseTotal
for (; step > 0; step >>= 1) { 38 9 47
915 38 uint64_t nxt = pos + step;
916 38 ▶ if (nxt <= nmax) {
Branch: 1 branch
BranchTrueFalseTotal
if (nxt <= nmax) { 36 2 38
917 36 int64_t sum = (int64_t)((uint64_t)acc + (uint64_t)tree[nxt]);
918 36 ▶ if (sum < target) { pos = nxt; acc = sum; }
Branch: 1 branch
BranchTrueFalseTotal
if (sum < target) { pos = nxt; acc = sum; } 14 22 36
919 }
920 }
921 9 return pos + 1;
922 }
923  
924 /* merge src tree slots into dst (equal n): element-wise add -- a Fenwick tree is
925 * linear, so tree(A) + tree(B) == tree(A+B). src_slots = slots the buffer holds. */
926 3 static void fen_merge_locked(FenHandle *dst, const int64_t *src, uint64_t src_slots) {
927 3 int64_t *tree = fen_tree(dst);
928 3 uint64_t slots = dst->hdr->n + 1;
929 3 uint64_t slots_max = fen_tree_slots_max(dst); /* Layer B: clamp writes to dst mapping */
930 3 ▶ if (slots > slots_max) slots = slots_max;
Branch: 1 branch
BranchTrueFalseTotal
if (slots > slots_max) slots = slots_max; 0 3 3
931 3 ▶ if (slots > src_slots) slots = src_slots; /* ...and reads to the src buffer */
Branch: 1 branch
BranchTrueFalseTotal
if (slots > src_slots) slots = src_slots; /* ...and reads to the src buffer */ 0 3 3
932 37 ▶ for (uint64_t x = 1; x < slots; x++) /* slot 0 unused */
Branch: 1 branch
BranchTrueFalseTotal
for (uint64_t x = 1; x < slots; x++) /* slot 0 unused */ 34 3 37
933 34 tree[x] = (int64_t)((uint64_t)tree[x] + (uint64_t)src[x]);
934 3 }
935  
936 /* reset all positions to 0 (caller holds the write lock) */
937 3 static inline void fen_clear_locked(FenHandle *h) {
938 3 uint64_t slots = h->hdr->n + 1;
939 3 ▶ if (h->mode == FEN_MODE_RANGE) slots *= 2; /* both BITs are contiguous after tree_off */
Branch: 1 branch
BranchTrueFalseTotal
if (h->mode == FEN_MODE_RANGE) slots *= 2; /* both BITs are contiguous after tree_off */ 2 1 3
940 3 uint64_t slots_max = fen_tree_slots_max(h); /* Layer B: clamp memset to the mapping */
941 3 ▶ if (slots > slots_max) slots = slots_max;
Branch: 1 branch
BranchTrueFalseTotal
if (slots > slots_max) slots = slots_max; 0 3 3
942 3 memset(fen_tree(h), 0, (size_t)(slots * sizeof(int64_t)));
943 3 }
944  
945 /* ================================================================
946 * Range mode: two BITs (B1 = fen_tree, B2 = fen_tree2) give O(log n) range
947 * update AND range query. range_add(l,r,d): B1 += d@l, -d@(r+1); B2 += d*(l-1)@l,
948 * -d*r@(r+1). prefix(i) = B1.prefix(i)*i - B2.prefix(i). The r+1==n+1 sentinel
949 * write is safely dropped -- it would only affect prefixes beyond n, never queried.
950 * ================================================================ */
951  
952 3381 static inline int64_t *fen_tree2(FenHandle *h) {
953 3381 return (int64_t *)((char *)h->base + h->tree2_off);
954 }
955 /* Layer B trusted bound: int64 slots guaranteed within the mapping past tree2_off */
956 3381 static inline uint64_t fen_tree2_slots_max(FenHandle *h) {
957 3381 uint64_t off = h->tree2_off;
958 3381 ▶ if (off == 0 || off >= h->mmap_size) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (off == 0 || off >= h->mmap_size) return 0; 3381 0 3381
if (off == 0 || off >= h->mmap_size) return 0; 0 3381 3381
959 3381 return (h->mmap_size - off) / sizeof(int64_t);
960 }
961 /* highest 1-based index safely inside BOTH BIT arrays (range mode) */
962 3381 static inline uint64_t fen_range_nmax(FenHandle *h) {
963 3381 uint64_t nn = h->hdr->n;
964 3381 ▶ uint64_t s1 = fen_tree_slots_max(h), hi1 = s1 ? s1 - 1 : 0;
Branch: 1 branch
BranchTrueFalseTotal
uint64_t s1 = fen_tree_slots_max(h), hi1 = s1 ? s1 - 1 : 0; 3381 0 3381
965 3381 ▶ uint64_t s2 = fen_tree2_slots_max(h), hi2 = s2 ? s2 - 1 : 0;
Branch: 1 branch
BranchTrueFalseTotal
uint64_t s2 = fen_tree2_slots_max(h), hi2 = s2 ? s2 - 1 : 0; 3381 0 3381
966 3381 uint64_t hi = hi1 < hi2 ? hi1 : hi2;
967 3381 return nn < hi ? nn : hi;
968 }
969 /* BIT primitives on an explicit tree array, bounded by nmax (1-based) */
970 2022 static inline void fen_bit_add(int64_t *tree, uint64_t i, int64_t delta, uint64_t nmax) {
971 8540 ▶ for (uint64_t x = i; x >= 1 && x <= nmax; x += fen_lowbit(x))
Branch: 2 branches
BranchTrueFalseTotal
for (uint64_t x = i; x >= 1 && x <= nmax; x += fen_lowbit(x)) 8540 0 8540
for (uint64_t x = i; x >= 1 && x <= nmax; x += fen_lowbit(x)) 6518 2022 8540
972 6518 tree[x] = (int64_t)((uint64_t)tree[x] + (uint64_t)delta);
973 2022 }
974 5738 static inline int64_t fen_bit_prefix(const int64_t *tree, uint64_t i, uint64_t nmax) {
975 5738 ▶ if (i > nmax) i = nmax;
Branch: 1 branch
BranchTrueFalseTotal
if (i > nmax) i = nmax; 0 5738 5738
976 5738 uint64_t s = 0;
977 20436 ▶ for (uint64_t x = i; x > 0; x -= fen_lowbit(x)) s += (uint64_t)tree[x];
Branch: 1 branch
BranchTrueFalseTotal
for (uint64_t x = i; x > 0; x -= fen_lowbit(x)) s += (uint64_t)tree[x]; 14698 5738 20436
978 5738 return (int64_t)s;
979 }
980 /* add delta to every position in [l,r] (1-based); caller holds the write lock */
981 512 static void fen_range_add_locked(FenHandle *h, uint64_t l, uint64_t r, int64_t delta) {
982 512 int64_t *b1 = fen_tree(h), *b2 = fen_tree2(h);
983 512 uint64_t nmax = fen_range_nmax(h);
984 512 ▶ if (l < 1) l = 1;
Branch: 1 branch
BranchTrueFalseTotal
if (l < 1) l = 1; 0 512 512
985 512 ▶ if (r > nmax) r = nmax;
Branch: 1 branch
BranchTrueFalseTotal
if (r > nmax) r = nmax; 0 512 512
986 512 ▶ if (l > r) return;
Branch: 1 branch
BranchTrueFalseTotal
if (l > r) return; 0 512 512
987 512 fen_bit_add(b1, l, delta, nmax);
988 512 fen_bit_add(b2, l, (int64_t)((uint64_t)delta * (l - 1)), nmax);
989 512 ▶ if (r + 1 <= nmax) { /* drop the r+1==n+1 sentinel: never queried */
Branch: 1 branch
BranchTrueFalseTotal
if (r + 1 <= nmax) { /* drop the r+1==n+1 sentinel: never queried */ 499 13 512
990 499 uint64_t neg = (uint64_t)0 - (uint64_t)delta;
991 499 fen_bit_add(b1, r + 1, (int64_t)neg, nmax);
992 499 fen_bit_add(b2, r + 1, (int64_t)(neg * r), nmax);
993 }
994 }
995 /* prefix sum over 1..i (range mode); caller holds a lock */
996 2869 static int64_t fen_range_prefix_locked(FenHandle *h, uint64_t i) {
997 2869 uint64_t nmax = fen_range_nmax(h);
998 2869 ▶ if (i > nmax) i = nmax;
Branch: 1 branch
BranchTrueFalseTotal
if (i > nmax) i = nmax; 0 2869 2869
999 2869 int64_t p1 = fen_bit_prefix(fen_tree(h), i, nmax);
1000 2869 int64_t p2 = fen_bit_prefix(fen_tree2(h), i, nmax);
1001 2869 return (int64_t)((uint64_t)p1 * i - (uint64_t)p2);
1002 }
1003 /* sum over l..r inclusive (range mode); caller holds a lock */
1004 1174 static int64_t fen_range_range_locked(FenHandle *h, uint64_t l, uint64_t r) {
1005 1174 ▶ if (l < 1) l = 1;
Branch: 1 branch
BranchTrueFalseTotal
if (l < 1) l = 1; 0 1174 1174
1006 1174 return (int64_t)((uint64_t)fen_range_prefix_locked(h, r)
1007 1174 - (uint64_t)fen_range_prefix_locked(h, l - 1));
1008 }
1009  
1010 /* ---- mode-dispatching wrappers used by the XS (point vs range) ---- */
1011 1418 static inline void fen_add1_locked(FenHandle *h, uint64_t i, int64_t d) {
1012 1418 ▶ if (h->mode == FEN_MODE_RANGE) fen_range_add_locked(h, i, i, d); /* point add == range_add(i,i) */
Branch: 1 branch
BranchTrueFalseTotal
if (h->mode == FEN_MODE_RANGE) fen_range_add_locked(h, i, i, d); /* point add == range_add(i,i) */ 329 1089 1418
1013 1089 else fen_update_locked(h, i, d);
1014 1418 }
1015 760 static inline int64_t fen_pref_locked(FenHandle *h, uint64_t i) {
1016 760 ▶ return (h->mode == FEN_MODE_RANGE) ? fen_range_prefix_locked(h, i) : fen_prefix_locked(h, i);
Branch: 1 branch
BranchTrueFalseTotal
return (h->mode == FEN_MODE_RANGE) ? fen_range_prefix_locked(h, i) : fen_prefix_locked(h, i); 521 239 760
1017 }
1018 1311 static inline int64_t fen_rng_locked(FenHandle *h, uint64_t l, uint64_t r) {
1019 1311 ▶ return (h->mode == FEN_MODE_RANGE) ? fen_range_range_locked(h, l, r) : fen_range_locked(h, l, r);
Branch: 1 branch
BranchTrueFalseTotal
return (h->mode == FEN_MODE_RANGE) ? fen_range_range_locked(h, l, r) : fen_range_locked(h, l, r); 1174 137 1311
1020 }
1021  
1022 #endif /* FEN_H */
« blib/lib/Data/Fenwick/Shared.pm ↑ Summary Shared.xs »