fenwick2d.h

filter: Statementstmt 67.0% 315 / 470 Branchbran 41.1% 172 / 418 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 54.8% 487 / 888 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« blib/lib/Data/Fenwick2D/Shared.pm ↑ Summary Shared.xs »
1 /*
2 * fenwick2d.h -- Shared-memory 2-D Fenwick tree (binary indexed tree) for Linux
3 *
4 * A fixed rows x cols grid of signed int64 cells supporting O(log rows*log cols)
5 * point update and rectangle-sum query: add a delta at cell (x,y), ask the sum
6 * over the origin rectangle [1..x]x[1..y] or any axis-aligned rectangle. The
7 * grid lives in a shared mapping so several processes update and query one
8 * structure; a write-preferring futex rwlock with reader-slot dead-process
9 * recovery guards mutation.
10 *
11 * Layout: Header -> reader_slots[1024] -> occ bitmap -> grid[(rows+1)*(cols+1) int64]
12 * (row-major, 1-indexed; row 0 and col 0 unused)
13 */
14  
15 #ifndef F2D_H
16 #define F2D_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 "fenwick2d.h: requires little-endian architecture"
39 #endif
40  
41  
42 /* ================================================================
43 * Constants
44 * ================================================================ */
45  
46 #define F2D_MAGIC 0x42443246U /* Fenwick2D */
47 #define F2D_VERSION 2 /* 2: added the occupancy bitmap region (layout change) */
48 #define F2D_ERR_BUFLEN (PATH_MAX + 256)
49 #ifndef F2D_READER_SLOTS
50 #define F2D_READER_SLOTS 1024 /* max concurrent reader processes 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 F2D_OCC_WORDS words to visit
54 * only OCCUPIED slots (O(words + live readers)) instead of all F2D_READER_SLOTS. */
55 #define F2D_OCC_WORDS (((F2D_READER_SLOTS) + 63) / 64) /* 16 for 1024 slots */
56 #define F2D_OCC_BYTES ((uint64_t)F2D_OCC_WORDS * 8) /* 128 bytes */
57 #define F2D_MIN_DIM 1
58 #define F2D_MAX_DIM 0x1000000ULL /* 2^24 per side; grid is (rows+1)*(cols+1) int64 */
59  
60 #define F2D_ERR(fmt, ...) do { if (errbuf) snprintf(errbuf, F2D_ERR_BUFLEN, fmt, ##__VA_ARGS__); } while (0)
61  
62 /* ================================================================
63 * Structs
64 * ================================================================ */
65  
66 /* Per-process slot for dead-process recovery. In the reader-slots-only rwlock a
67 * reader's ENTIRE contribution to the shared lock is `rdepth` in its OWN slot --
68 * there is no separate shared reader counter to fall out of sync with it -- so a
69 * dead reader's contribution is exactly this one word, which a draining writer
70 * neutralises by clearing the slot's pid (the scan then ignores the slot). No
71 * orphaned counter can exist, so there is no quiescent force-reset and sustained
72 * readers cannot starve a writer. _rsv1/_rsv2 are kept only to preserve the
73 * 16-byte slot size across the already-released builds. */
74 typedef struct {
75 uint32_t pid; /* 0 = unclaimed */
76 uint32_t rdepth; /* read-locks THIS process currently holds (recursion-safe) */
77 uint32_t _rsv1; /* reserved (was waiters_parked); unused, kept for layout size */
78 uint32_t _rsv2; /* reserved (was writers_parked); unused, kept for layout size */
79 } F2dReaderSlot;
80  
81 struct F2dHeader {
82 uint32_t magic, version; /* 0,4 */
83 uint32_t _pad0; /* 8 */
84 uint32_t _pad1; /* 12 */
85 uint64_t rows; /* 16 grid rows (1..rows), 1-indexed */
86 uint64_t cols; /* 24 grid cols (1..cols), 1-indexed */
87 uint64_t total_size; /* 32 */
88 uint64_t reader_slots_off; /* 40 */
89 uint64_t tree_off; /* 48 (rows+1)*(cols+1) int64 grid, row-major */
90 uint32_t wlock; /* 56 WRITER word ONLY: 0 (free) or WRITER_BIT|pid. NOT a reader count. */
91 uint32_t rwait; /* 60 parked-waiter hint (readers+writers blocked on wlock); over-count-safe */
92 uint32_t drain_seq; /* 64 futex bumped by a reader releasing under a draining writer (wakes it) */
93 uint32_t slotless_rdepth; /* readers holding with no reader-slot (documented residual) */
94 uint64_t stat_ops; /* 72 */
95 uint8_t sealed; /* 80 0 = mutable, 1 = frozen (read-only; lock-free reads) */
96 uint8_t _pad[175]; /* 81..255 */
97 };
98 typedef struct F2dHeader F2dHeader;
99  
100 _Static_assert(sizeof(F2dHeader) == 256, "F2dHeader must be 256 bytes");
101  
102 /* ---- Process-local handle ---- */
103  
104 typedef struct F2dHandle {
105 F2dHeader *hdr;
106 F2dReaderSlot *reader_slots; /* F2D_READER_SLOTS entries */
107 uint64_t *occ; /* F2D_OCC_WORDS-word slot-occupancy bitmap (trusted layout offset) */
108 void *base; /* mmap base */
109 uint64_t tree_off; /* validated tree-array offset, cached: never re-read from the peer-writable header */
110 uint64_t rows; /* cached grid rows */
111 uint64_t cols; /* cached grid cols */
112 size_t mmap_size;
113 char *path; /* backing file path (strdup'd) */
114 int backing_fd; /* memfd or reopened-fd to close on destroy, -1 for file/anon */
115 uint32_t my_slot_idx; /* UINT32_MAX if all slots taken (no recovery for this handle) */
116 uint32_t cached_pid; /* getpid() cached at last slot claim */
117 uint32_t cached_fork_gen; /* f2d_fork_gen value at last slot claim */
118 uint32_t slotless_held; /* read-locks this process holds with no reader-slot */
119 int readonly; /* 1 = frozen O_RDONLY/PROT_READ view: lock-free reads, mutation croaks */
120 } F2dHandle;
121  
122 /* ================================================================
123 * Futex-based write-preferring read-write lock (reader-slots-only)
124 * with dead-process recovery
125 *
126 * The reader count is NOT stored in a shared counter. It is DISTRIBUTED across
127 * per-process reader slots: each slot's `rdepth` is that process's entire
128 * contribution to the lock. A reader publishes its presence in its own slot and
129 * then re-checks the writer word; a writer publishes the writer word and then
130 * scans every slot until all live readers' rdepth reach 0. Sequentially-
131 * consistent store+load on each side (a Dekker handshake) gives mutual exclusion.
132 *
133 * Because a reader's whole contribution is ONE atomic word owned by ONE process,
134 * a crashed reader is recovered by clearing that one slot (CAS its pid to 0) --
135 * there is no second counter to strand, no orphaned +1, and therefore no
136 * quiescent force-reset. A reader killed anywhere in rdlock/rdunlock leaves at
137 * most `rdepth>0` in its dead slot, which the draining writer clears directly, so
138 * sustained read traffic can never starve a writer. Write-preference is inherent
139 * in the gate (new readers see wlock!=0 and yield), so there is no reader-count
140 * yield hack.
141 * ================================================================ */
142  
143 #define F2D_RWLOCK_SPIN_LIMIT 32
144 #define F2D_LOCK_TIMEOUT_SEC 2 /* FUTEX_WAIT timeout for stale-lock detection / drain re-scan */
145  
146 0 static inline void f2d_rwlock_spin_pause(void) {
147 #if defined(__x86_64__) || defined(__i386__)
148 0 __asm__ volatile("pause" ::: "memory");
149 #elif defined(__aarch64__)
150 __asm__ volatile("yield" ::: "memory");
151 #else
152 __asm__ volatile("" ::: "memory");
153 #endif
154 0 }
155  
156 /* Writer word encoding: WRITER_BIT|pid when write-locked, 0 when free. */
157 #define F2D_RWLOCK_WRITER_BIT 0x80000000U
158 #define F2D_RWLOCK_PID_MASK 0x7FFFFFFFU
159 #define F2D_RWLOCK_WR(pid) (F2D_RWLOCK_WRITER_BIT | ((uint32_t)(pid) & F2D_RWLOCK_PID_MASK))
160  
161 /* A zombie (dead but not yet reaped) still answers kill(pid,0) as alive, so a
162 * process that crashed while holding the lock and lingers unreaped would never
163 * be recovered. Treat /proc/<pid>/stat state 'Z' as dead. Linux-only (as is
164 * this module); if /proc is unreadable we fall back to "alive" (safe: we never
165 * force-recover a possibly-live holder). */
166 0 static inline int f2d_pid_is_zombie(uint32_t pid) {
167 char path[32], buf[256];
168 0 snprintf(path, sizeof(path), "/proc/%u/stat", (unsigned)pid);
169 0 int fd = open(path, O_RDONLY | O_CLOEXEC);
170 0 ▶ if (fd < 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (fd < 0) return 0; 0 0 0
171 0 ssize_t n = read(fd, buf, sizeof(buf) - 1);
172 0 close(fd);
173 0 ▶ if (n <= 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (n <= 0) return 0; 0 0 0
174 0 buf[n] = '\0';
175 /* "pid (comm) state ..."; comm may contain ')', so scan to the last one. */
176 0 char *rp = strrchr(buf, ')');
177 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
178 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
179 }
180 /* 1 if alive or unknown, 0 if definitely dead. Cannot detect PID reuse: a
181 * recycled PID reports "alive" and the slot is not reclaimed until that
182 * process exits. See "Crash Safety" in the POD. */
183 0 static inline int f2d_pid_alive(uint32_t pid) {
184 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
185 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
186 0 return !f2d_pid_is_zombie(pid); /* kill() also succeeds for a zombie -> treat as dead */
187 }
188  
189 /* Force-recover a stale WRITE lock left by a dead writer (held or mid-drain).
190 * CAS to OUR pid to hold the lock while fixing shared state, then release.
191 * Using our pid (not a bare WRITER_BIT sentinel) means a subsequent recovering
192 * process can detect and re-recover if we crash mid-recovery. */
193 0 static inline void f2d_recover_stale_lock(F2dHandle *h, uint32_t observed_wlock) {
194 0 F2dHeader *hdr = h->hdr;
195 0 uint32_t mypid = F2D_RWLOCK_WR((uint32_t)getpid());
196 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
197 mypid, 0, __ATOMIC_ACQUIRE, __ATOMIC_RELAXED))
198 0 return;
199 /* We now hold the write lock as mypid. No additional shared state needs
200 * repair here (this module has no seqlock); just release the lock. */
201 0 __atomic_store_n(&hdr->wlock, 0, __ATOMIC_SEQ_CST);
202 0 ▶ 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 0 0
203 0 syscall(SYS_futex, &hdr->wlock, FUTEX_WAKE, INT_MAX, NULL, NULL, 0);
204 }
205  
206 static const struct timespec f2d_lock_timeout = { F2D_LOCK_TIMEOUT_SEC, 0 };
207  
208 /* Process-global fork-generation counter. Incremented in the pthread_atfork
209 * child callback so every open handle detects a fork transition on the next
210 * lock call without paying a getpid() syscall on the hot path. */
211 static uint32_t f2d_fork_gen = 1;
212 static pthread_once_t f2d_atfork_once = PTHREAD_ONCE_INIT;
213 0 static void f2d_on_fork_child(void) {
214 0 __atomic_add_fetch(&f2d_fork_gen, 1, __ATOMIC_RELAXED);
215 0 }
216 4 static void f2d_atfork_init(void) {
217 4 pthread_atfork(NULL, NULL, f2d_on_fork_child);
218 4 }
219  
220 /* Occupancy bitmap: set a slot's bit when it is claimed, clear it on clean
221 * release. SEQ_CST so a set bit is ordered before the slot's rdepth can go
222 * non-zero (bit set in claim, which precedes any rdlock), letting a writer's
223 * SEQ_CST bitmap scan never miss a slot a committed reader holds. */
224 21 static inline void f2d_occ_set(F2dHandle *h, uint32_t s) {
225 21 __atomic_fetch_or(&h->occ[s >> 6], (uint64_t)1 << (s & 63), __ATOMIC_SEQ_CST);
226 21 }
227 21 static inline void f2d_occ_clear(F2dHandle *h, uint32_t s) {
228 21 __atomic_fetch_and(&h->occ[s >> 6], ~((uint64_t)1 << (s & 63)), __ATOMIC_SEQ_CST);
229 21 }
230  
231 static inline void f2d_reader_wake_drain(F2dHandle *h);
232  
233 /* Ensure this process owns a reader slot. Called from the lock helpers so that
234 * fork()'d children pick up their own slot lazily instead of sharing the
235 * parent's. Hot-path is a single relaxed load + compare; only on a
236 * fork-generation mismatch do we touch getpid() and scan slots. */
237 1393 static inline void f2d_claim_reader_slot(F2dHandle *h) {
238 1393 uint32_t cur_gen = __atomic_load_n(&f2d_fork_gen, __ATOMIC_RELAXED);
239 1393 ▶ 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)) 1372 21 1393
if (__builtin_expect(cur_gen == h->cached_fork_gen && h->my_slot_idx != UINT32_MAX, 1)) 1372 0 1372
240 1372 return;
241 /* Cold path -- register the atfork hook once per process, then claim. */
242 21 pthread_once(&f2d_atfork_once, f2d_atfork_init);
243 /* Re-read after pthread_once: f2d_on_fork_child may have bumped it. */
244 21 cur_gen = __atomic_load_n(&f2d_fork_gen, __ATOMIC_RELAXED);
245 21 uint32_t now_pid = (uint32_t)getpid();
246 21 h->cached_pid = now_pid;
247 21 ▶ 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 */ 21 0 21
248 21 h->cached_fork_gen = cur_gen;
249 21 h->my_slot_idx = UINT32_MAX;
250 21 uint32_t start = now_pid % F2D_READER_SLOTS;
251 /* Pass 1: take a free slot. */
252 23 ▶ for (uint32_t i = 0; i < F2D_READER_SLOTS; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t i = 0; i < F2D_READER_SLOTS; i++) { 23 0 23
253 23 uint32_t s = (start + i) % F2D_READER_SLOTS;
254 23 uint32_t expected = 0;
255 23 ▶ if (__atomic_compare_exchange_n(&h->reader_slots[s].pid,
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_compare_exchange_n(&h->reader_slots[s].pid, 21 2 23
256 &expected, now_pid, 0,
257 __ATOMIC_ACQUIRE, __ATOMIC_RELAXED)) {
258 /* Fresh owner holds no read locks yet; clear any stale rdepth left by
259 * a dead predecessor (its contribution is dropped as we take over). */
260 21 uint32_t stale = __atomic_exchange_n(&h->reader_slots[s].rdepth, 0, __ATOMIC_SEQ_CST);
261 21 f2d_occ_set(h, s); /* mark occupied BEFORE any rdlock can bump rdepth */
262 21 ▶ if (stale) f2d_reader_wake_drain(h);
Branch: 1 branch
BranchTrueFalseTotal
if (stale) f2d_reader_wake_drain(h); 0 21 21
263 21 h->my_slot_idx = s;
264 21 return;
265 }
266 }
267 /* Pass 2: no free slot -- reclaim one whose owner is dead. Safe to take even
268 * if its rdepth>0: clearing pid drops the dead reader's entire contribution
269 * (a writer scan ignores rdepth when pid==0) and we reset rdepth to 0 as we
270 * claim it. */
271 0 ▶ for (uint32_t i = 0; i < F2D_READER_SLOTS; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t i = 0; i < F2D_READER_SLOTS; i++) { 0 0 0
272 0 uint32_t dpid = __atomic_load_n(&h->reader_slots[i].pid, __ATOMIC_ACQUIRE);
273 0 ▶ if (dpid == 0 || dpid == now_pid || f2d_pid_alive(dpid)) continue;
Branch: 3 branches
BranchTrueFalseTotal
if (dpid == 0 || dpid == now_pid || f2d_pid_alive(dpid)) continue; 0 0 0
if (dpid == 0 || dpid == now_pid || f2d_pid_alive(dpid)) continue; 0 0 0
if (dpid == 0 || dpid == now_pid || f2d_pid_alive(dpid)) continue; 0 0 0
274 0 uint32_t expected = dpid;
275 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
276 __ATOMIC_ACQUIRE, __ATOMIC_RELAXED)) {
277 0 uint32_t stale = __atomic_exchange_n(&h->reader_slots[i].rdepth, 0, __ATOMIC_SEQ_CST);
278 0 f2d_occ_set(h, i);
279 0 ▶ if (stale) f2d_reader_wake_drain(h);
Branch: 1 branch
BranchTrueFalseTotal
if (stale) f2d_reader_wake_drain(h); 0 0 0
280 0 h->my_slot_idx = i;
281 0 return;
282 }
283 }
284 /* Table full -- leave my_slot_idx = UINT32_MAX so this handle takes the
285 * slotless path (lock still works; recovery of THIS reader's death is the
286 * documented slotless limitation). */
287 }
288  
289 /* Inspect the writer word after a futex-wait timeout. If a dead writer holds
290 * it, force-recover. Dead READERS need no action here: only a writer that owns
291 * wlock drains readers, and it clears dead readers inline in its own scan. */
292 0 static inline void f2d_recover_after_timeout(F2dHandle *h) {
293 0 uint32_t val = __atomic_load_n(&h->hdr->wlock, __ATOMIC_RELAXED);
294 0 ▶ if (val >= F2D_RWLOCK_WRITER_BIT) {
Branch: 1 branch
BranchTrueFalseTotal
if (val >= F2D_RWLOCK_WRITER_BIT) { 0 0 0
295 0 uint32_t pid = val & F2D_RWLOCK_PID_MASK;
296 0 ▶ if (!f2d_pid_alive(pid))
Branch: 1 branch
BranchTrueFalseTotal
if (!f2d_pid_alive(pid)) 0 0 0
297 0 f2d_recover_stale_lock(h, val);
298 }
299 0 }
300  
301 /* Bump/drop the parked-waiter hint. Both readers (blocked at the gate) and
302 * writers (blocked acquiring wlock) wait on the wlock futex and use this, so
303 * wrunlock/recover know whether a FUTEX_WAKE is worth a syscall. A waiter
304 * SIGKILLed while parked leaves rwait over-counted -> at most a spurious wake
305 * (harmless). SEQ_CST pairs publication + gate check with unlock + hint check. */
306 0 static inline void f2d_park(F2dHandle *h) {
307 0 __atomic_add_fetch(&h->hdr->rwait, 1, __ATOMIC_SEQ_CST);
308 0 }
309 0 static inline void f2d_unpark(F2dHandle *h) {
310 0 __atomic_sub_fetch(&h->hdr->rwait, 1, __ATOMIC_RELAXED);
311 0 }
312  
313 /* Publish (inc) / retract (dec) this reader's presence -- its ENTIRE
314 * contribution to the lock. A slotted reader uses its slot's rdepth; a reader
315 * that could not claim a slot uses the global slotless_rdepth. inc() is SEQ_CST
316 * so the wlock re-check that follows it in rdlock forms a Dekker handshake with
317 * the writer's SEQ_CST wlock-store + rdepth-scan. leave() peels slotless first
318 * so a slot claimed mid-hold cannot misattribute the decrement. */
319 1057 static inline void f2d_rdepth_inc(F2dHandle *h) {
320 1057 ▶ if (h->my_slot_idx != UINT32_MAX) {
Branch: 1 branch
BranchTrueFalseTotal
if (h->my_slot_idx != UINT32_MAX) { 1057 0 1057
321 1057 __atomic_add_fetch(&h->reader_slots[h->my_slot_idx].rdepth, 1, __ATOMIC_SEQ_CST);
322 } else {
323 0 __atomic_add_fetch(&h->hdr->slotless_rdepth, 1, __ATOMIC_SEQ_CST);
324 0 h->slotless_held++;
325 }
326 1057 }
327 1057 static inline void f2d_rdepth_dec(F2dHandle *h) {
328 1057 ▶ if (h->slotless_held > 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (h->slotless_held > 0) { 0 1057 1057
329 0 h->slotless_held--;
330 0 __atomic_sub_fetch(&h->hdr->slotless_rdepth, 1, __ATOMIC_SEQ_CST);
331 1057 ▶ } else if (h->my_slot_idx != UINT32_MAX) {
Branch: 1 branch
BranchTrueFalseTotal
} else if (h->my_slot_idx != UINT32_MAX) { 1057 0 1057
332 1057 __atomic_sub_fetch(&h->reader_slots[h->my_slot_idx].rdepth, 1, __ATOMIC_SEQ_CST);
333 }
334 1057 }
335  
336 /* Wake a writer that may be draining readers (it waits on drain_seq). Called
337 * after every rdepth decrement so a released read lock lets the writer re-scan
338 * promptly instead of waiting out its timeout. */
339 1057 static inline void f2d_reader_wake_drain(F2dHandle *h) {
340 1057 ▶ 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 1057 1057
341 0 __atomic_add_fetch(&h->hdr->drain_seq, 1, __ATOMIC_RELEASE);
342 0 syscall(SYS_futex, &h->hdr->drain_seq, FUTEX_WAKE, 1, NULL, NULL, 0);
343 }
344 1057 }
345  
346 1057 static inline void f2d_rwlock_rdlock(F2dHandle *h) {
347 1057 f2d_claim_reader_slot(h);
348 1057 F2dHeader *hdr = h->hdr;
349 1057 for (int spin = 0; ; spin++) {
350 1057 uint32_t cur = __atomic_load_n(&hdr->wlock, __ATOMIC_ACQUIRE);
351 1057 ▶ if (cur == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (cur == 0) { 1057 0 1057
352 /* Optimistically take the read: publish rdepth, then re-check wlock.
353 * SEQ_CST inc + SEQ_CST load vs the writer's SEQ_CST wlock CAS +
354 * SEQ_CST rdepth scan: by the single total order of SEQ_CST ops the
355 * two sides cannot both miss each other, so we never hold
356 * concurrently with a writer. */
357 1057 f2d_rdepth_inc(h);
358 1057 ▶ if (__atomic_load_n(&hdr->wlock, __ATOMIC_SEQ_CST) == 0)
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&hdr->wlock, __ATOMIC_SEQ_CST) == 0) 1057 0 1057
359 1057 return; /* no writer after our publish -> we hold the read lock */
360 /* A writer appeared during our publish -- yield to it (write-preferring). */
361 0 f2d_rdepth_dec(h);
362 0 f2d_reader_wake_drain(h); /* let the draining writer see rdepth drop */
363 0 spin = 0;
364 0 continue;
365 }
366 /* wlock != 0: a writer holds or is acquiring. Recover if it is dead. */
367 0 if (cur >= F2D_RWLOCK_WRITER_BIT &&
368 0 !f2d_pid_alive(cur & F2D_RWLOCK_PID_MASK)) {
369 0 f2d_recover_stale_lock(h, cur);
370 0 spin = 0;
371 0 continue;
372 }
373 0 ▶ if (__builtin_expect(spin < F2D_RWLOCK_SPIN_LIMIT, 1)) {
Branch: 1 branch
BranchTrueFalseTotal
if (__builtin_expect(spin < F2D_RWLOCK_SPIN_LIMIT, 1)) { 0 0 0
374 0 f2d_rwlock_spin_pause();
375 0 continue;
376 }
377 0 f2d_park(h);
378 0 cur = __atomic_load_n(&hdr->wlock, __ATOMIC_SEQ_CST);
379 0 ▶ if (cur != 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (cur != 0) { 0 0 0
380 0 long rc = syscall(SYS_futex, &hdr->wlock, FUTEX_WAIT, cur,
381 &f2d_lock_timeout, NULL, 0);
382 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
383 0 f2d_unpark(h);
384 0 f2d_recover_after_timeout(h);
385 0 spin = 0;
386 0 continue;
387 }
388 }
389 0 f2d_unpark(h);
390 0 spin = 0;
391 }
392 }
393  
394 1057 static inline void f2d_rwlock_rdunlock(F2dHandle *h) {
395 1057 f2d_rdepth_dec(h); /* SEQ_CST: drop presence before checking the writer */
396 1057 f2d_reader_wake_drain(h); /* if a writer is draining, wake it to re-scan */
397 1057 }
398  
399 336 static inline void f2d_rwlock_wrlock(F2dHandle *h) {
400 336 f2d_claim_reader_slot(h); /* refresh cached_pid across fork */
401 336 F2dHeader *hdr = h->hdr;
402 /* Encode PID in the wlock word itself (0x80000000 | pid) to eliminate any
403 * crash window between acquiring the lock and storing the owner. */
404 336 uint32_t mypid = F2D_RWLOCK_WR(h->cached_pid);
405 /* Phase 1: acquire the writer word (mutual exclusion among writers). */
406 336 for (int spin = 0; ; spin++) {
407 336 uint32_t expected = 0;
408 336 ▶ if (__atomic_compare_exchange_n(&hdr->wlock, &expected, mypid,
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_compare_exchange_n(&hdr->wlock, &expected, mypid, 336 0 336
409 0, __ATOMIC_SEQ_CST, __ATOMIC_RELAXED))
410 336 break;
411 /* Contended: expected now holds the current wlock value. */
412 0 if (expected >= F2D_RWLOCK_WRITER_BIT &&
413 0 !f2d_pid_alive(expected & F2D_RWLOCK_PID_MASK)) {
414 0 f2d_recover_stale_lock(h, expected);
415 0 spin = 0;
416 0 continue;
417 }
418 0 ▶ if (__builtin_expect(spin < F2D_RWLOCK_SPIN_LIMIT, 1)) {
Branch: 1 branch
BranchTrueFalseTotal
if (__builtin_expect(spin < F2D_RWLOCK_SPIN_LIMIT, 1)) { 0 0 0
419 0 f2d_rwlock_spin_pause();
420 0 continue;
421 }
422 0 f2d_park(h);
423 0 uint32_t cur = __atomic_load_n(&hdr->wlock, __ATOMIC_SEQ_CST);
424 0 ▶ if (cur != 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (cur != 0) { 0 0 0
425 0 long rc = syscall(SYS_futex, &hdr->wlock, FUTEX_WAIT, cur,
426 &f2d_lock_timeout, NULL, 0);
427 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
428 0 f2d_unpark(h);
429 0 f2d_recover_after_timeout(h);
430 0 spin = 0;
431 0 continue;
432 }
433 }
434 0 f2d_unpark(h);
435 0 spin = 0;
436 }
437 /* Phase 2: we own wlock, so no NEW reader can join (they see wlock!=0 and
438 * yield). Drain the readers that were already holding when we won the CAS.
439 * The SEQ_CST CAS above + the SEQ_CST rdepth loads below are the writer side
440 * of the Dekker handshake. */
441 0 for (;;) {
442 336 uint32_t v = __atomic_load_n(&hdr->drain_seq, __ATOMIC_ACQUIRE); /* snapshot BEFORE scan */
443 336 int busy = 0;
444 /* Visit only OCCUPIED slots via the occupancy bitmap (SEQ_CST: a committed
445 * reader's bit -- set in claim, before its rdepth++ -- is ordered before
446 * this scan, so no held slot is skipped). O(F2D_OCC_WORDS + live readers)
447 * instead of O(F2D_READER_SLOTS). */
448 5712 ▶ for (uint32_t w = 0; w < F2D_OCC_WORDS; w++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t w = 0; w < F2D_OCC_WORDS; w++) { 5376 336 5712
449 5376 uint64_t word = __atomic_load_n(&h->occ[w], __ATOMIC_SEQ_CST);
450 5715 ▶ while (word) {
Branch: 1 branch
BranchTrueFalseTotal
while (word) { 339 5376 5715
451 339 uint32_t i = (w << 6) + (uint32_t)__builtin_ctzll(word);
452 339 word &= word - 1; /* consume this bit (local copy) */
453 339 uint32_t rd = __atomic_load_n(&h->reader_slots[i].rdepth, __ATOMIC_SEQ_CST);
454 339 ▶ if (rd == 0) continue; /* occupied but not read-locking now */
Branch: 1 branch
BranchTrueFalseTotal
if (rd == 0) continue; /* occupied but not read-locking now */ 339 0 339
455 0 uint32_t pid = __atomic_load_n(&h->reader_slots[i].pid, __ATOMIC_ACQUIRE);
456 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
457 0 ▶ if (!f2d_pid_alive(pid)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!f2d_pid_alive(pid)) { 0 0 0
458 /* Dead reader: drop its pid so the slot no longer counts. Leave
459 * the occ bit set (harmless -- a later scan hits pid==0 and skips,
460 * a re-claim re-sets it) to avoid racing a concurrent claimant. */
461 0 uint32_t ep = pid;
462 0 __atomic_compare_exchange_n(&h->reader_slots[i].pid, &ep, 0,
463 0, __ATOMIC_ACQ_REL, __ATOMIC_RELAXED);
464 0 continue;
465 }
466 0 busy = 1; /* live reader still holding */
467 }
468 }
469 /* A live slotless reader keeps us waiting; a crashed slotless reader that
470 * cannot be attributed to a pid is the documented slotless limitation. */
471 336 ▶ 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 336 336
472 0 busy = 1;
473 336 ▶ if (!busy)
Branch: 1 branch
BranchTrueFalseTotal
if (!busy) 336 0 336
474 336 return; /* exclusive: wlock held + every rdepth 0 */
475 /* Wait for a reader to release (drain_seq bump) or time out to re-scan
476 * (which reclaims any newly-dead slotted reader). */
477 0 syscall(SYS_futex, &hdr->drain_seq, FUTEX_WAIT, v, &f2d_lock_timeout, NULL, 0);
478 }
479 }
480  
481 336 static inline void f2d_rwlock_wrunlock(F2dHandle *h) {
482 336 F2dHeader *hdr = h->hdr;
483 336 __atomic_store_n(&hdr->wlock, 0, __ATOMIC_SEQ_CST);
484 336 ▶ 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 336 336
485 0 syscall(SYS_futex, &hdr->wlock, FUTEX_WAKE, INT_MAX, NULL, NULL, 0);
486 336 }
487  
488 /* ================================================================
489 * Layout math + create / open / destroy
490 *
491 * Layout: Header -> reader_slots[1024] -> occ bitmap -> grid[(rows+1)*(cols+1) int64]
492 * ================================================================ */
493  
494 /* Single source of truth for the mmap region layout offsets:
495 * Header -> reader_slots[] -> occ bitmap -> grid. */
496 typedef struct { uint64_t reader_slots, occ, tree; } F2dLayout;
497  
498 91 static inline F2dLayout f2d_layout(void) {
499 F2dLayout L;
500 91 L.reader_slots = sizeof(F2dHeader);
501 91 L.occ = L.reader_slots + (uint64_t)F2D_READER_SLOTS * sizeof(F2dReaderSlot);
502 91 L.tree = L.occ + F2D_OCC_BYTES;
503 91 L.tree = (L.tree + 7) & ~(uint64_t)7; /* 8-byte align the int64 tree array */
504 91 return L;
505 }
506  
507 /* the grid is 1-indexed row-major: (rows+1)*(cols+1) int64 slots, row/col 0 unused */
508 36 static inline uint64_t f2d_total_size(uint64_t rows, uint64_t cols) {
509 36 F2dLayout L = f2d_layout();
510 36 return L.tree + (rows + 1) * (cols + 1) * sizeof(int64_t);
511 }
512  
513 18 static inline void f2d_init_header(void *base, uint64_t rows, uint64_t cols, uint64_t total) {
514 18 F2dLayout L = f2d_layout();
515 18 F2dHeader *hdr = (F2dHeader *)base;
516 /* Zero the header + reader-slot region; the grid relies on the fresh mapping
517 being OS zero-filled (every prefix sum starts at 0). */
518 18 memset(base, 0, (size_t)L.tree);
519 18 hdr->version = F2D_VERSION;
520 18 hdr->rows = rows;
521 18 hdr->cols = cols;
522 18 hdr->total_size = total;
523 18 hdr->reader_slots_off = L.reader_slots;
524 18 hdr->tree_off = L.tree;
525 /* Publish magic LAST, as a release store: it is the commit point, so a
526 creator killed before it leaves magic==0 and never a file mistaken for
527 a valid one. A kill during the field stores leaves one to remove by
528 hand. */
529 18 __atomic_store_n(&hdr->magic, F2D_MAGIC, __ATOMIC_RELEASE);
530 18 __atomic_thread_fence(__ATOMIC_SEQ_CST);
531 18 }
532  
533 3289 static inline int64_t *f2d_tree(F2dHandle *h) {
534 3289 return (int64_t *)((char *)h->base + h->tree_off);
535 }
536  
537 /* Layer B trusted bound: number of int64 tree slots guaranteed within the real
538 * mapping. Derived from the process-local mmap_size (fixed at attach, not
539 * peer-writable) and the SAME tree_off f2d_tree() uses, so a peer that corrupts
540 * hdr->rows / hdr->cols / tree_off after attach-time validation can never drive
541 * an access outside the mapping. Equals (rows+1)*(cols+1) for a valid grid. */
542 6575 static inline uint64_t f2d_tree_slots_max(F2dHandle *h) {
543 6575 uint64_t off = h->tree_off;
544 6575 ▶ if (off >= h->mmap_size) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (off >= h->mmap_size) return 0; 0 6575 6575
545 6575 return (h->mmap_size - off) / sizeof(int64_t);
546 }
547  
548 26 static inline F2dHandle *f2d_setup(void *base, size_t map_size,
549 const char *path, int backing_fd) {
550 26 F2dHeader *hdr = (F2dHeader *)base;
551 26 F2dHandle *h = (F2dHandle *)calloc(1, sizeof(F2dHandle));
552 26 ▶ if (!h) {
Branch: 1 branch
BranchTrueFalseTotal
if (!h) { 0 26 26
553 0 munmap(base, map_size);
554 0 ▶ if (backing_fd >= 0) close(backing_fd);
Branch: 1 branch
BranchTrueFalseTotal
if (backing_fd >= 0) close(backing_fd); 0 0 0
555 0 return NULL;
556 }
557 26 h->hdr = hdr;
558 26 h->base = base;
559 26 h->reader_slots = (F2dReaderSlot *)((uint8_t *)base + sizeof(F2dHeader)); /* trusted layout, not the peer-writable header offset */
560 26 h->occ = (uint64_t *)((uint8_t *)base + f2d_layout().occ); /* trusted layout offset */
561 26 h->tree_off = hdr->tree_off; /* single validated read; bound and pointer stay consistent */
562 26 h->rows = hdr->rows;
563 26 h->cols = hdr->cols;
564 26 h->mmap_size = map_size;
565 26 ▶ h->path = path ? strdup(path) : NULL;
Branch: 1 branch
BranchTrueFalseTotal
h->path = path ? strdup(path) : NULL; 14 12 26
566 26 h->backing_fd = backing_fd;
567 26 h->my_slot_idx = UINT32_MAX;
568 26 return h;
569 }
570  
571 /* Validate a mapped header (shared by f2d_create reopen and f2d_open_fd). */
572 13 static inline int f2d_validate_header(const F2dHeader *hdr, uint64_t file_size) {
573 13 ▶ if (__atomic_load_n(&hdr->magic, __ATOMIC_ACQUIRE) != F2D_MAGIC) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&hdr->magic, __ATOMIC_ACQUIRE) != F2D_MAGIC) return 0; 2 11 13
574 11 ▶ if (hdr->version != F2D_VERSION) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->version != F2D_VERSION) return 0; 0 11 11
575 11 ▶ if (hdr->rows < F2D_MIN_DIM || hdr->rows > F2D_MAX_DIM) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (hdr->rows < F2D_MIN_DIM || hdr->rows > F2D_MAX_DIM) return 0; 11 0 11
if (hdr->rows < F2D_MIN_DIM || hdr->rows > F2D_MAX_DIM) return 0; 0 11 11
576 11 ▶ if (hdr->cols < F2D_MIN_DIM || hdr->cols > F2D_MAX_DIM) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (hdr->cols < F2D_MIN_DIM || hdr->cols > F2D_MAX_DIM) return 0; 11 0 11
if (hdr->cols < F2D_MIN_DIM || hdr->cols > F2D_MAX_DIM) return 0; 0 11 11
577 11 ▶ if (hdr->total_size != file_size) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->total_size != file_size) return 0; 0 11 11
578 11 ▶ if (hdr->total_size != f2d_total_size(hdr->rows, hdr->cols)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->total_size != f2d_total_size(hdr->rows, hdr->cols)) return 0; 0 11 11
579 11 F2dLayout L = f2d_layout();
580 11 ▶ 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 11 11
581 11 ▶ if (hdr->tree_off != L.tree) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->tree_off != L.tree) return 0; 0 11 11
582 11 return 1;
583 }
584  
585 /* validate the requested grid dimensions (rows, cols) */
586 25 static int f2d_validate_args(uint64_t rows, uint64_t cols, char *errbuf) {
587 25 ▶ if (errbuf) errbuf[0] = '\0';
Branch: 1 branch
BranchTrueFalseTotal
if (errbuf) errbuf[0] = '\0'; 25 0 25
588 25 ▶ if (rows < F2D_MIN_DIM || rows > F2D_MAX_DIM) { F2D_ERR("rows must be between 1 and 2^24"); return 0; }
Branch: 3 branches
BranchTrueFalseTotal
if (rows < F2D_MIN_DIM || rows > F2D_MAX_DIM) { F2D_ERR("rows must be between 1 and 2^24"); return 0; } 25 0 25
if (rows < F2D_MIN_DIM || rows > F2D_MAX_DIM) { F2D_ERR("rows must be between 1 and 2^24"); return 0; } 0 25 25
if (rows < F2D_MIN_DIM || rows > F2D_MAX_DIM) { F2D_ERR("rows must be between 1 and 2^24"); return 0; } 0 0 0
589 25 ▶ if (cols < F2D_MIN_DIM || cols > F2D_MAX_DIM) { F2D_ERR("cols must be between 1 and 2^24"); return 0; }
Branch: 3 branches
BranchTrueFalseTotal
if (cols < F2D_MIN_DIM || cols > F2D_MAX_DIM) { F2D_ERR("cols must be between 1 and 2^24"); return 0; } 25 0 25
if (cols < F2D_MIN_DIM || cols > F2D_MAX_DIM) { F2D_ERR("cols must be between 1 and 2^24"); return 0; } 0 25 25
if (cols < F2D_MIN_DIM || cols > F2D_MAX_DIM) { F2D_ERR("cols must be between 1 and 2^24"); return 0; } 0 0 0
590 25 ▶ if ((cols + 1) > (UINT64_MAX / 8) / (rows + 1)) { F2D_ERR("rows * cols too large for the grid"); return 0; }
Branch: 2 branches
BranchTrueFalseTotal
if ((cols + 1) > (UINT64_MAX / 8) / (rows + 1)) { F2D_ERR("rows * cols too large for the grid"); return 0; } 0 25 25
if ((cols + 1) > (UINT64_MAX / 8) / (rows + 1)) { F2D_ERR("rows * cols too large for the grid"); return 0; } 0 0 0
591 25 return 1;
592 }
593  
594 /* Exclusively create a path-backed segment at `mode` (default 0600), or
595 * attach to an existing file; neither open follows a final symlink.
596 * A wider mode (e.g. 0660) opts into cross-user sharing. The caller validates
597 * the header on attach; an existing valid file is trusted. */
598 14 static int f2d_secure_open(const char *path, mode_t mode, char *errbuf) {
599 14 ▶ for (int attempt = 0; attempt < 100; attempt++) {
Branch: 1 branch
BranchTrueFalseTotal
for (int attempt = 0; attempt < 100; attempt++) { 14 0 14
600 14 int fd = open(path, O_RDWR|O_CREAT|O_EXCL|O_NOFOLLOW|O_CLOEXEC, mode);
601 14 ▶ 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 */ 6 8 14
602 8 ▶ if (errno != EEXIST) { F2D_ERR("create %s: %s", path, strerror(errno)); return -1; }
Branch: 2 branches
BranchTrueFalseTotal
if (errno != EEXIST) { F2D_ERR("create %s: %s", path, strerror(errno)); return -1; } 0 8 8
if (errno != EEXIST) { F2D_ERR("create %s: %s", path, strerror(errno)); return -1; } 0 0 0
603 8 fd = open(path, O_RDWR|O_NOFOLLOW|O_CLOEXEC);
604 8 ▶ if (fd >= 0) return fd;
Branch: 1 branch
BranchTrueFalseTotal
if (fd >= 0) return fd; 8 0 8
605 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
606 0 ▶ F2D_ERR("open %s: %s", path, strerror(errno)); /* ELOOP => symlink rejected */
Branch: 1 branch
BranchTrueFalseTotal
F2D_ERR("open %s: %s", path, strerror(errno)); /* ELOOP => symlink rejected */ 0 0 0
607 0 return -1;
608 }
609 0 ▶ F2D_ERR("open %s: create/attach kept racing", path);
Branch: 1 branch
BranchTrueFalseTotal
F2D_ERR("open %s: create/attach kept racing", path); 0 0 0
610 0 return -1;
611 }
612  
613 /* True iff the whole file is zero -- what an abandoned mid-init
614 creator leaves. Lets recovery re-init only a provably-empty file, never
615 one that merely starts with a zero word. Cold path, so a byte scan is
616 fine. Read, not mapped: a read fault on a tmpfs hole allocates the page. */
617 2 static int f2d_file_is_zero(int fd, uint64_t size) {
618 char buf[16384];
619 5 ▶ for (uint64_t off = 0; off < size; ) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint64_t off = 0; off < size; ) { 4 1 5
620 4 ssize_t n = pread(fd, buf, size - off < sizeof buf ? (size_t)(size - off) : sizeof buf, (off_t)off);
621 4 ▶ if (n <= 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (n <= 0) return 0; 0 4 4
622 34547 ▶ 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 34543 34544
for (ssize_t i = 0; i < n; i++) if (buf[i]) return 0; 34544 3 34547
623 3 off += (uint64_t)n;
624 }
625 1 return 1;
626 }
627  
628 /* Opt-in (DATA_FENWICK2D_SHARED_SPARSE=0): reserving commits memory this module otherwise fills lazily. */
629 8 static int f2d_reserve(int fd, uint64_t size) {
630 8 const char *sp = getenv("DATA_FENWICK2D_SHARED_SPARSE");
631 8 ▶ if (!sp || strcmp(sp, "0")) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (!sp || strcmp(sp, "0")) return 0; 0 8 8
if (!sp || strcmp(sp, "0")) return 0; 0 0 0
632 /* Before Linux 6.11 tmpfs gives up at any pending signal and undoes the allocation, so a
633 * periodic one could keep it from ever completing; SIGSTOP cannot be blocked. */
634 sigset_t all, old;
635 0 sigfillset(&all);
636 0 sigprocmask(SIG_BLOCK, &all, &old);
637 int e;
638 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
639 0 sigprocmask(SIG_SETMASK, &old, NULL);
640 0 ▶ if (e == 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (e == 0) return 0; 0 0 0
641 0 errno = e;
642 0 return -1;
643 }
644  
645 24 static F2dHandle *f2d_create(const char *path, uint64_t rows, uint64_t cols, mode_t mode, char *errbuf) {
646 24 ▶ if (!f2d_validate_args(rows, cols, errbuf)) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!f2d_validate_args(rows, cols, errbuf)) return NULL; 0 24 24
647  
648 24 uint64_t total = f2d_total_size(rows, cols);
649 24 int anonymous = (path == NULL);
650 24 int fd = -1;
651 size_t map_size;
652 void *base;
653  
654 24 ▶ if (anonymous) {
Branch: 1 branch
BranchTrueFalseTotal
if (anonymous) { 10 14 24
655 10 map_size = (size_t)total;
656 10 base = mmap(NULL, map_size, PROT_READ|PROT_WRITE, MAP_SHARED|MAP_ANONYMOUS, -1, 0);
657 10 ▶ if (base == MAP_FAILED) { F2D_ERR("mmap: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { F2D_ERR("mmap: %s", strerror(errno)); return NULL; } 0 10 10
if (base == MAP_FAILED) { F2D_ERR("mmap: %s", strerror(errno)); return NULL; } 0 0 0
658 } else {
659 14 fd = f2d_secure_open(path, mode, errbuf);
660 21 ▶ if (fd < 0) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (fd < 0) return NULL; 0 14 14
661 14 ▶ if (flock(fd, LOCK_EX) < 0) { F2D_ERR("flock: %s", strerror(errno)); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (flock(fd, LOCK_EX) < 0) { F2D_ERR("flock: %s", strerror(errno)); close(fd); return NULL; } 0 14 14
if (flock(fd, LOCK_EX) < 0) { F2D_ERR("flock: %s", strerror(errno)); close(fd); return NULL; } 0 0 0
662 struct stat st;
663 14 ▶ if (fstat(fd, &st) < 0) { F2D_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fstat(fd, &st) < 0) { F2D_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; } 0 14 14
if (fstat(fd, &st) < 0) { F2D_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; } 0 0 0
664 14 int is_new = (st.st_size == 0);
665 14 ▶ if (!is_new && (uint64_t)st.st_size < sizeof(F2dHeader)) {
Branch: 2 branches
BranchTrueFalseTotal
if (!is_new && (uint64_t)st.st_size < sizeof(F2dHeader)) { 8 6 14
if (!is_new && (uint64_t)st.st_size < sizeof(F2dHeader)) { 0 8 8
666 0 ▶ F2D_ERR("%s: file too small (%lld)", path, (long long)st.st_size);
Branch: 1 branch
BranchTrueFalseTotal
F2D_ERR("%s: file too small (%lld)", path, (long long)st.st_size); 0 0 0
667 0 flock(fd, LOCK_UN); close(fd); return NULL;
668 }
669 /* Reading a mapped tmpfs hole allocates a page, even during validation. */
670 14 ▶ if (!is_new && st.st_blocks == 0) {
Branch: 2 branches
BranchTrueFalseTotal
if (!is_new && st.st_blocks == 0) { 8 6 14
if (!is_new && st.st_blocks == 0) { 2 6 8
671 uint32_t magic;
672 2 ▶ if (pread(fd, &magic, sizeof magic, 0) != (ssize_t)sizeof magic) {
Branch: 1 branch
BranchTrueFalseTotal
if (pread(fd, &magic, sizeof magic, 0) != (ssize_t)sizeof magic) { 0 2 2
673 0 ▶ F2D_ERR("%s: cannot read Fenwick2D tree header", path);
Branch: 1 branch
BranchTrueFalseTotal
F2D_ERR("%s: cannot read Fenwick2D tree header", path); 0 0 0
674 1 flock(fd, LOCK_UN); close(fd); return NULL;
675 }
676 2 ▶ if (magic == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (magic == 0) { 2 0 2
677 2 ▶ if ((uint64_t)st.st_size != total || st.st_uid != geteuid() || !f2d_file_is_zero(fd, total)) {
Branch: 3 branches
BranchTrueFalseTotal
if ((uint64_t)st.st_size != total || st.st_uid != geteuid() || !f2d_file_is_zero(fd, total)) { 1 1 2
if ((uint64_t)st.st_size != total || st.st_uid != geteuid() || !f2d_file_is_zero(fd, total)) { 1 0 1
if ((uint64_t)st.st_size != total || st.st_uid != geteuid() || !f2d_file_is_zero(fd, total)) { 0 1 1
678 1 ▶ F2D_ERR("invalid Fenwick2D tree file");
Branch: 1 branch
BranchTrueFalseTotal
F2D_ERR("invalid Fenwick2D tree file"); 1 0 1
679 1 flock(fd, LOCK_UN); close(fd); return NULL;
680 }
681 1 is_new = 1;
682 }
683 }
684 13 ▶ 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)) { 7 6 13
if (is_new && (st.st_uid != geteuid() || fchmod(fd, mode) < 0)) { 7 0 7
if (is_new && (st.st_uid != geteuid() || fchmod(fd, mode) < 0)) { 0 7 7
685 0 ▶ F2D_ERR("%s: refusing to initialize file not owned by us", path);
Branch: 1 branch
BranchTrueFalseTotal
F2D_ERR("%s: refusing to initialize file not owned by us", path); 0 0 0
686 0 flock(fd, LOCK_UN); close(fd); return NULL;
687 }
688 13 ▶ if (is_new && ftruncate(fd, (off_t)total) < 0) {
Branch: 2 branches
BranchTrueFalseTotal
if (is_new && ftruncate(fd, (off_t)total) < 0) { 7 6 13
if (is_new && ftruncate(fd, (off_t)total) < 0) { 0 7 7
689 0 ▶ F2D_ERR("ftruncate: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
F2D_ERR("ftruncate: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; 0 0 0
690 }
691 13 ▶ if (is_new && f2d_reserve(fd, total) < 0) {
Branch: 2 branches
BranchTrueFalseTotal
if (is_new && f2d_reserve(fd, total) < 0) { 7 6 13
if (is_new && f2d_reserve(fd, total) < 0) { 0 7 7
692 0 ▶ F2D_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
F2D_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno)); 0 0 0
693 0 if (ftruncate(fd, 0) < 0) { /* best effort */ }
694 0 flock(fd, LOCK_UN); close(fd); return NULL;
695 }
696 13 ▶ 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; 6 7 13
697 13 base = mmap(NULL, map_size, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
698 13 ▶ if (base == MAP_FAILED) {
Branch: 1 branch
BranchTrueFalseTotal
if (base == MAP_FAILED) { 0 13 13
699 0 ▶ F2D_ERR("mmap: %s", strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
F2D_ERR("mmap: %s", strerror(errno)); 0 0 0
700 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
701 0 flock(fd, LOCK_UN); close(fd); return NULL;
702 }
703 13 ▶ if (!is_new) {
Branch: 1 branch
BranchTrueFalseTotal
if (!is_new) { 6 7 13
704 6 ▶ if (!f2d_validate_header((F2dHeader *)base, (uint64_t)st.st_size)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!f2d_validate_header((F2dHeader *)base, (uint64_t)st.st_size)) { 2 4 6
705 /* Recover an abandoned mid-init file: a creator killed
706 * between the ftruncate and the header init leaves a
707 * full-size, all-zero (magic==0) file that would brick every
708 * future open of this path. Re-initialize ONLY when it is
709 * exactly our size, still uninitialized, and owned by us;
710 * anything else still errors. */
711 2 ▶ if (((F2dHeader *)base)->magic == 0 && (uint64_t)st.st_size == total
Branch: 2 branches
BranchTrueFalseTotal
if (((F2dHeader *)base)->magic == 0 && (uint64_t)st.st_size == total 1 1 2
if (((F2dHeader *)base)->magic == 0 && (uint64_t)st.st_size == total 1 0 1
712 1 ▶ && st.st_uid == geteuid() && f2d_file_is_zero(fd, map_size)) {
Branch: 2 branches
BranchTrueFalseTotal
&& st.st_uid == geteuid() && f2d_file_is_zero(fd, map_size)) { 1 0 1
&& st.st_uid == geteuid() && f2d_file_is_zero(fd, map_size)) { 0 1 1
713 0 ▶ if (fchmod(fd, mode) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (fchmod(fd, mode) < 0) { 0 0 0
714 0 ▶ F2D_ERR("%s: fchmod: %s", path, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
F2D_ERR("%s: fchmod: %s", path, strerror(errno)); 0 0 0
715 0 munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
716 }
717 0 ▶ if (f2d_reserve(fd, total) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (f2d_reserve(fd, total) < 0) { 0 0 0
718 0 ▶ F2D_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
F2D_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno)); 0 0 0
719 0 munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
720 }
721 0 f2d_init_header(base, rows, cols, total);
722 0 flock(fd, LOCK_UN); close(fd);
723 0 return f2d_setup(base, map_size, path, -1);
724 }
725 2 ▶ if (((F2dHeader *)base)->magic == 0 && (uint64_t)st.st_size == total
Branch: 2 branches
BranchTrueFalseTotal
if (((F2dHeader *)base)->magic == 0 && (uint64_t)st.st_size == total 1 1 2
if (((F2dHeader *)base)->magic == 0 && (uint64_t)st.st_size == total 1 0 1
726 1 ▶ && st.st_uid == geteuid()) {
Branch: 1 branch
BranchTrueFalseTotal
&& st.st_uid == geteuid()) { 1 0 1
727 1 ▶ F2D_ERR("%s: incomplete Fenwick2D tree file left by an interrupted create; remove it and retry", path);
Branch: 1 branch
BranchTrueFalseTotal
F2D_ERR("%s: incomplete Fenwick2D tree file left by an interrupted create; remove it and retry", path); 1 0 1
728 1 munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
729 }
730 1 ▶ F2D_ERR("invalid Fenwick2D tree file"); munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
F2D_ERR("invalid Fenwick2D tree file"); munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL; 1 0 1
731 }
732 4 ▶ if (__atomic_load_n(&((F2dHeader *)base)->sealed, __ATOMIC_ACQUIRE)) {
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&((F2dHeader *)base)->sealed, __ATOMIC_ACQUIRE)) { 1 3 4
733 1 ▶ F2D_ERR("%s is frozen (read-only); open it with new_readonly", path);
Branch: 1 branch
BranchTrueFalseTotal
F2D_ERR("%s is frozen (read-only); open it with new_readonly", path); 1 0 1
734 1 munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
735 }
736 3 flock(fd, LOCK_UN); close(fd);
737 3 return f2d_setup(base, map_size, path, -1);
738 }
739 }
740 17 f2d_init_header(base, rows, cols, total);
741 17 ▶ if (fd >= 0) { flock(fd, LOCK_UN); close(fd); }
Branch: 1 branch
BranchTrueFalseTotal
if (fd >= 0) { flock(fd, LOCK_UN); close(fd); } 7 10 17
742 17 return f2d_setup(base, map_size, path, -1);
743 }
744  
745 1 static F2dHandle *f2d_create_memfd(const char *name, uint64_t rows, uint64_t cols, char *errbuf) {
746 1 ▶ if (!f2d_validate_args(rows, cols, errbuf)) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!f2d_validate_args(rows, cols, errbuf)) return NULL; 0 1 1
747  
748 1 uint64_t total = f2d_total_size(rows, cols);
749 1 ▶ int fd = memfd_create(name ? name : "fenwick2d", MFD_CLOEXEC | MFD_ALLOW_SEALING);
Branch: 1 branch
BranchTrueFalseTotal
int fd = memfd_create(name ? name : "fenwick2d", MFD_CLOEXEC | MFD_ALLOW_SEALING); 1 0 1
750 1 ▶ if (fd < 0) { F2D_ERR("memfd_create: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fd < 0) { F2D_ERR("memfd_create: %s", strerror(errno)); return NULL; } 0 1 1
if (fd < 0) { F2D_ERR("memfd_create: %s", strerror(errno)); return NULL; } 0 0 0
751 1 ▶ if (ftruncate(fd, (off_t)total) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (ftruncate(fd, (off_t)total) < 0) { 0 1 1
752 0 ▶ F2D_ERR("ftruncate: %s", strerror(errno)); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
F2D_ERR("ftruncate: %s", strerror(errno)); close(fd); return NULL; 0 0 0
753 }
754 1 ▶ if (f2d_reserve(fd, total) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (f2d_reserve(fd, total) < 0) { 0 1 1
755 0 ▶ F2D_ERR("memfd: cannot reserve %llu bytes: %s", (unsigned long long)total, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
F2D_ERR("memfd: cannot reserve %llu bytes: %s", (unsigned long long)total, strerror(errno)); 0 0 0
756 0 close(fd); return NULL;
757 }
758 1 (void)fcntl(fd, F_ADD_SEALS, F_SEAL_SHRINK | F_SEAL_GROW);
759 1 void *base = mmap(NULL, (size_t)total, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
760 1 ▶ if (base == MAP_FAILED) { F2D_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { F2D_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; } 0 1 1
if (base == MAP_FAILED) { F2D_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; } 0 0 0
761 1 f2d_init_header(base, rows, cols, total);
762 1 return f2d_setup(base, (size_t)total, NULL, fd);
763 }
764  
765 2 static F2dHandle *f2d_open_fd(int fd, char *errbuf) {
766 2 ▶ if (errbuf) errbuf[0] = '\0';
Branch: 1 branch
BranchTrueFalseTotal
if (errbuf) errbuf[0] = '\0'; 2 0 2
767 struct stat st;
768 2 ▶ if (fstat(fd, &st) < 0) { F2D_ERR("fstat: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fstat(fd, &st) < 0) { F2D_ERR("fstat: %s", strerror(errno)); return NULL; } 0 2 2
if (fstat(fd, &st) < 0) { F2D_ERR("fstat: %s", strerror(errno)); return NULL; } 0 0 0
769 2 ▶ if ((uint64_t)st.st_size < sizeof(F2dHeader)) { F2D_ERR("too small"); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if ((uint64_t)st.st_size < sizeof(F2dHeader)) { F2D_ERR("too small"); return NULL; } 0 2 2
if ((uint64_t)st.st_size < sizeof(F2dHeader)) { F2D_ERR("too small"); return NULL; } 0 0 0
770 /* before mmap: a creator may truncate the file until it has set magic */
771 uint32_t magic;
772 2 ▶ if (pread(fd, &magic, sizeof magic, offsetof(F2dHeader, magic)) != (ssize_t)sizeof magic || magic != F2D_MAGIC) {
Branch: 2 branches
BranchTrueFalseTotal
if (pread(fd, &magic, sizeof magic, offsetof(F2dHeader, magic)) != (ssize_t)sizeof magic || magic != F2D_MAGIC) { 2 0 2
if (pread(fd, &magic, sizeof magic, offsetof(F2dHeader, magic)) != (ssize_t)sizeof magic || magic != F2D_MAGIC) { 0 2 2
773 0 ▶ F2D_ERR("invalid Fenwick2D tree table"); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
F2D_ERR("invalid Fenwick2D tree table"); return NULL; 0 0 0
774 }
775 2 size_t ms = (size_t)st.st_size;
776 2 void *base = mmap(NULL, ms, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
777 2 ▶ if (base == MAP_FAILED) { F2D_ERR("mmap: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { F2D_ERR("mmap: %s", strerror(errno)); return NULL; } 0 2 2
if (base == MAP_FAILED) { F2D_ERR("mmap: %s", strerror(errno)); return NULL; } 0 0 0
778 2 ▶ if (!f2d_validate_header((F2dHeader *)base, (uint64_t)st.st_size)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!f2d_validate_header((F2dHeader *)base, (uint64_t)st.st_size)) { 0 2 2
779 0 ▶ F2D_ERR("invalid Fenwick2D tree table"); munmap(base, ms); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
F2D_ERR("invalid Fenwick2D tree table"); munmap(base, ms); return NULL; 0 0 0
780 }
781 2 ▶ if (__atomic_load_n(&((F2dHeader *)base)->sealed, __ATOMIC_ACQUIRE)) {
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&((F2dHeader *)base)->sealed, __ATOMIC_ACQUIRE)) { 1 1 2
782 1 ▶ F2D_ERR("this Fenwick2D tree is frozen (read-only); open it with new_readonly");
Branch: 1 branch
BranchTrueFalseTotal
F2D_ERR("this Fenwick2D tree is frozen (read-only); open it with new_readonly"); 1 0 1
783 1 munmap(base, ms); return NULL;
784 }
785 1 int myfd = fcntl(fd, F_DUPFD_CLOEXEC, 0);
786 1 ▶ if (myfd < 0) { F2D_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (myfd < 0) { F2D_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; } 0 1 1
if (myfd < 0) { F2D_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; } 0 0 0
787 1 return f2d_setup(base, ms, NULL, myfd);
788 }
789  
790 /* Open a FROZEN (sealed) file read-only: O_RDONLY + PROT_READ, no lock ever.
791 * A sealed file is immutable and no read path writes the mapping, so queries
792 * take no reader-slot / rwlock traffic and any number of processes can share
793 * one PROT_READ mapping (same architecture; the magic rejects a wrong-endian
794 * file). */
795 6 static F2dHandle *f2d_open_readonly(const char *path, char *errbuf) {
796 6 ▶ if (errbuf) errbuf[0] = '\0';
Branch: 1 branch
BranchTrueFalseTotal
if (errbuf) errbuf[0] = '\0'; 6 0 6
797 6 int fd = open(path, O_RDONLY|O_NOFOLLOW|O_CLOEXEC);
798 6 ▶ if (fd < 0) { F2D_ERR("open %s: %s", path, strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fd < 0) { F2D_ERR("open %s: %s", path, strerror(errno)); return NULL; } 1 5 6
if (fd < 0) { F2D_ERR("open %s: %s", path, strerror(errno)); return NULL; } 1 0 1
799 struct stat st;
800 5 ▶ if (fstat(fd, &st) < 0) { F2D_ERR("fstat %s: %s", path, strerror(errno)); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fstat(fd, &st) < 0) { F2D_ERR("fstat %s: %s", path, strerror(errno)); close(fd); return NULL; } 0 5 5
if (fstat(fd, &st) < 0) { F2D_ERR("fstat %s: %s", path, strerror(errno)); close(fd); return NULL; } 0 0 0
801 5 ▶ if ((uint64_t)st.st_size < sizeof(F2dHeader)) { F2D_ERR("%s: file too small", path); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if ((uint64_t)st.st_size < sizeof(F2dHeader)) { F2D_ERR("%s: file too small", path); close(fd); return NULL; } 0 5 5
if ((uint64_t)st.st_size < sizeof(F2dHeader)) { F2D_ERR("%s: file too small", path); close(fd); return NULL; } 0 0 0
802 /* before mmap: a creator may truncate the file until it has set magic */
803 uint32_t magic;
804 5 ▶ if (pread(fd, &magic, sizeof magic, offsetof(F2dHeader, magic)) != (ssize_t)sizeof magic || magic != F2D_MAGIC) {
Branch: 2 branches
BranchTrueFalseTotal
if (pread(fd, &magic, sizeof magic, offsetof(F2dHeader, magic)) != (ssize_t)sizeof magic || magic != F2D_MAGIC) { 5 0 5
if (pread(fd, &magic, sizeof magic, offsetof(F2dHeader, magic)) != (ssize_t)sizeof magic || magic != F2D_MAGIC) { 0 5 5
805 0 ▶ F2D_ERR("%s: invalid Fenwick2D tree file", path); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
F2D_ERR("%s: invalid Fenwick2D tree file", path); close(fd); return NULL; 0 0 0
806 }
807 5 size_t ms = (size_t)st.st_size;
808 5 void *base = mmap(NULL, ms, PROT_READ, MAP_SHARED, fd, 0);
809 5 close(fd); /* the mapping keeps the file; a read-only view needs no fd (no msync/ftruncate) */
810 5 ▶ if (base == MAP_FAILED) { F2D_ERR("mmap %s: %s", path, strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { F2D_ERR("mmap %s: %s", path, strerror(errno)); return NULL; } 0 5 5
if (base == MAP_FAILED) { F2D_ERR("mmap %s: %s", path, strerror(errno)); return NULL; } 0 0 0
811 5 ▶ if (!f2d_validate_header((F2dHeader *)base, (uint64_t)st.st_size)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!f2d_validate_header((F2dHeader *)base, (uint64_t)st.st_size)) { 0 5 5
812 0 ▶ F2D_ERR("%s: invalid Fenwick2D tree file", path); munmap(base, ms); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
F2D_ERR("%s: invalid Fenwick2D tree file", path); munmap(base, ms); return NULL; 0 0 0
813 }
814 5 ▶ if (!__atomic_load_n(&((F2dHeader *)base)->sealed, __ATOMIC_ACQUIRE)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!__atomic_load_n(&((F2dHeader *)base)->sealed, __ATOMIC_ACQUIRE)) { 1 4 5
815 1 ▶ F2D_ERR("%s is not frozen: call ->freeze on the producer before opening read-only", path);
Branch: 1 branch
BranchTrueFalseTotal
F2D_ERR("%s is not frozen: call ->freeze on the producer before opening read-only", path); 1 0 1
816 1 munmap(base, ms); return NULL;
817 }
818 4 F2dHandle *h = f2d_setup(base, ms, path, -1); /* munmaps on OOM */
819 4 ▶ if (!h) { F2D_ERR("out of memory"); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (!h) { F2D_ERR("out of memory"); return NULL; } 0 4 4
if (!h) { F2D_ERR("out of memory"); return NULL; } 0 0 0
820 4 h->readonly = 1;
821 4 return h;
822 }
823  
824 26 static void f2d_destroy(F2dHandle *h) {
825 26 ▶ if (!h) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!h) return; 0 26 26
826 /* Release our reader slot on clean teardown (else short-lived-reader churn
827 * exhausts the slot table); skip if a read lock is still held (rdepth>0). */
828 26 ▶ 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 && 26 0 26
if (h->reader_slots && h->my_slot_idx != UINT32_MAX && h->cached_pid && 21 5 26
if (h->reader_slots && h->my_slot_idx != UINT32_MAX && h->cached_pid && 21 0 21
829 21 ▶ h->cached_fork_gen == __atomic_load_n(&f2d_fork_gen, __ATOMIC_RELAXED) &&
Branch: 1 branch
BranchTrueFalseTotal
h->cached_fork_gen == __atomic_load_n(&f2d_fork_gen, __ATOMIC_RELAXED) && 21 0 21
830 21 ▶ __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) { 21 0 21
831 /* Clear our occ bit BEFORE freeing the slot: we still own the pid so no
832 * claimant can take the slot mid-clear, and rdepth==0 so no writer needs
833 * to see us. (A crash skips this -> the bit is reclaimed lazily by a
834 * writer scan / re-claim, same as the pid.) */
835 21 f2d_occ_clear(h, h->my_slot_idx);
836 21 uint32_t expected = h->cached_pid;
837 21 __atomic_compare_exchange_n(&h->reader_slots[h->my_slot_idx].pid,
838 &expected, 0, 0, __ATOMIC_RELEASE, __ATOMIC_RELAXED);
839 }
840 26 ▶ if (h->backing_fd >= 0) close(h->backing_fd);
Branch: 1 branch
BranchTrueFalseTotal
if (h->backing_fd >= 0) close(h->backing_fd); 2 24 26
841 26 ▶ if (h->base) munmap(h->base, h->mmap_size);
Branch: 1 branch
BranchTrueFalseTotal
if (h->base) munmap(h->base, h->mmap_size); 26 0 26
842 26 free(h->path);
843 26 free(h);
844 }
845  
846 3 static inline int f2d_msync(F2dHandle *h) {
847 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
848 3 return msync(h->base, h->mmap_size, MS_SYNC);
849 }
850  
851 /* Seal a grid: make it permanently immutable so it can be shipped and opened
852 * read-only. Takes the write lock so no update is in flight, publishes the
853 * seal, then flushes it (file/memfd-backed). Afterwards every mutator croaks
854 * and a read-write reopen is refused. */
855 2 static int f2d_freeze(F2dHandle *h) {
856 2 f2d_rwlock_wrlock(h);
857 2 __atomic_store_n(&h->hdr->sealed, 1, __ATOMIC_RELEASE);
858 2 f2d_rwlock_wrunlock(h);
859 2 ▶ if (h->path || h->backing_fd >= 0) return f2d_msync(h); /* durability for file/memfd-backed */
Branch: 2 branches
BranchTrueFalseTotal
if (h->path || h->backing_fd >= 0) return f2d_msync(h); /* durability for file/memfd-backed */ 0 2 2
if (h->path || h->backing_fd >= 0) return f2d_msync(h); /* durability for file/memfd-backed */ 0 0 0
860 0 return 0; /* anonymous: the seal lives in shared memory (visible to forks); nothing to flush */
861 }
862  
863 /* ================================================================
864 * 2-D Fenwick tree (binary indexed tree) operations -- callers hold the lock.
865 * 1-indexed row-major grid; along each axis a BIT node x covers (x-lowbit(x), x],
866 * lowbit(x) = x & -x. Values are signed int64 (deltas may be negative).
867 * ================================================================ */
868  
869 10259 static inline uint64_t f2d_lowbit(uint64_t x) { return x & (~x + 1ULL); }
870  
871 /* flat row-major index of grid cell (i,j) in the (rows+1)x(cols+1) array */
872 5838 static inline uint64_t f2d_idx(uint64_t i, uint64_t j, uint64_t cols) {
873 5838 return i * (cols + 1) + j;
874 }
875 /* highest 1-based (row, col) safely inside the mapping. cols is used as-is (a
876 * corrupt-large cols is caught by the per-access flat bound below); rows is
877 * clamped so (rows+1) full rows of stride (cols+1) fit -- Layer B. */
878 3286 static inline void f2d_dims(F2dHandle *h, uint64_t *rmax, uint64_t *cmax) {
879 3286 uint64_t stride = h->cols + 1;
880 3286 uint64_t smax = f2d_tree_slots_max(h);
881 3286 ▶ uint64_t fit1 = stride ? smax / stride : 0; /* whole (rows+1) that fit */
Branch: 1 branch
BranchTrueFalseTotal
uint64_t fit1 = stride ? smax / stride : 0; /* whole (rows+1) that fit */ 3286 0 3286
882 3286 ▶ uint64_t maxr = fit1 ? fit1 - 1 : 0;
Branch: 1 branch
BranchTrueFalseTotal
uint64_t maxr = fit1 ? fit1 - 1 : 0; 3286 0 3286
883 3286 *rmax = h->rows < maxr ? h->rows : maxr;
884 3286 *cmax = h->cols;
885 3286 }
886  
887 /* add delta at grid cell (x,y) (1-based); caller holds the write lock */
888 328 static void f2d_update_locked(F2dHandle *h, uint64_t x, uint64_t y, int64_t delta) {
889 328 int64_t *tree = f2d_tree(h);
890 328 uint64_t rmax, cmax; f2d_dims(h, &rmax, &cmax);
891 328 uint64_t smax = f2d_tree_slots_max(h);
892 876 ▶ for (uint64_t i = x; i >= 1 && i <= rmax; i += f2d_lowbit(i))
Branch: 2 branches
BranchTrueFalseTotal
for (uint64_t i = x; i >= 1 && i <= rmax; i += f2d_lowbit(i)) 876 0 876
for (uint64_t i = x; i >= 1 && i <= rmax; i += f2d_lowbit(i)) 548 328 876
893 1564 ▶ for (uint64_t j = y; j >= 1 && j <= cmax; j += f2d_lowbit(j)) {
Branch: 2 branches
BranchTrueFalseTotal
for (uint64_t j = y; j >= 1 && j <= cmax; j += f2d_lowbit(j)) { 1564 0 1564
for (uint64_t j = y; j >= 1 && j <= cmax; j += f2d_lowbit(j)) { 1016 548 1564
894 1016 uint64_t f = f2d_idx(i, j, cmax);
895 1016 ▶ if (f < smax) tree[f] = (int64_t)((uint64_t)tree[f] + (uint64_t)delta);
Branch: 1 branch
BranchTrueFalseTotal
if (f < smax) tree[f] = (int64_t)((uint64_t)tree[f] + (uint64_t)delta); 1016 0 1016
896 }
897 328 }
898  
899 /* prefix sum over the rectangle [1..x] x [1..y] (1-based; x or y == 0 -> 0) */
900 2958 static int64_t f2d_prefix_locked(F2dHandle *h, uint64_t x, uint64_t y) {
901 2958 const int64_t *tree = f2d_tree(h);
902 2958 uint64_t rmax, cmax; f2d_dims(h, &rmax, &cmax);
903 2958 uint64_t smax = f2d_tree_slots_max(h);
904 2958 ▶ if (x > rmax) x = rmax;
Branch: 1 branch
BranchTrueFalseTotal
if (x > rmax) x = rmax; 0 2958 2958
905 2958 ▶ if (y > cmax) y = cmax;
Branch: 1 branch
BranchTrueFalseTotal
if (y > cmax) y = cmax; 0 2958 2958
906 2958 uint64_t s = 0;
907 6831 ▶ for (uint64_t i = x; i > 0; i -= f2d_lowbit(i))
Branch: 1 branch
BranchTrueFalseTotal
for (uint64_t i = x; i > 0; i -= f2d_lowbit(i)) 3873 2958 6831
908 8695 ▶ for (uint64_t j = y; j > 0; j -= f2d_lowbit(j)) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint64_t j = y; j > 0; j -= f2d_lowbit(j)) { 4822 3873 8695
909 4822 uint64_t f = f2d_idx(i, j, cmax);
910 4822 ▶ if (f < smax) s += (uint64_t)tree[f];
Branch: 1 branch
BranchTrueFalseTotal
if (f < smax) s += (uint64_t)tree[f]; 4822 0 4822
911 }
912 2958 return (int64_t)s;
913 }
914  
915 /* sum over the inclusive rectangle [x1..x2] x [y1..y2] (1-based) via inclusion-exclusion */
916 628 static int64_t f2d_rect_locked(F2dHandle *h, uint64_t x1, uint64_t y1, uint64_t x2, uint64_t y2) {
917 628 return (int64_t)((uint64_t)f2d_prefix_locked(h, x2, y2)
918 628 - (uint64_t)f2d_prefix_locked(h, x1 - 1, y2)
919 628 - (uint64_t)f2d_prefix_locked(h, x2, y1 - 1)
920 628 + (uint64_t)f2d_prefix_locked(h, x1 - 1, y1 - 1));
921 }
922  
923 /* value at cell (x,y) == the 1x1 rectangle sum */
924 324 static int64_t f2d_point_locked(F2dHandle *h, uint64_t x, uint64_t y) {
925 324 return f2d_rect_locked(h, x, y, x, y);
926 }
927  
928 /* reset the whole grid to 0 (caller holds the write lock) */
929 3 static inline void f2d_clear_locked(F2dHandle *h) {
930 3 uint64_t slots = (h->rows + 1) * (h->cols + 1);
931 3 uint64_t slots_max = f2d_tree_slots_max(h); /* Layer B: clamp memset to the mapping */
932 3 ▶ if (slots > slots_max) slots = slots_max;
Branch: 1 branch
BranchTrueFalseTotal
if (slots > slots_max) slots = slots_max; 0 3 3
933 3 memset(f2d_tree(h), 0, (size_t)(slots * sizeof(int64_t)));
934 3 }
935  
936 #endif /* F2D_H */
« blib/lib/Data/Fenwick2D/Shared.pm ↑ Summary Shared.xs »