intervaltree.h

filter: Statementstmt 69.6% 344 / 494 Branchbran 44.4% 185 / 416 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 58.1% 529 / 910 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« blib/lib/Data/IntervalTree/Shared.pm ↑ Summary Shared.xs »
1 /*
2 * intervaltree.h -- Shared-memory interval tree for Linux
3 *
4 * A set of integer intervals [lo, hi] with fast overlap queries: which stored
5 * intervals contain a point (stabbing), or overlap a query range. Backed by an
6 * augmented balanced BST -- keyed by the low endpoint, each node carrying the
7 * maximum high endpoint of its subtree so a query prunes subtrees that end
8 * before it. Intervals are appended in O(1) and the balanced tree is bulk-built
9 * on the first query after any insert (so query recursion stays O(log n) deep
10 * regardless of insertion order). The intervals and tree live in a shared
11 * mapping so several processes build and query one index; a write-preferring
12 * futex rwlock with reader-slot dead-process recovery guards mutation, and
13 * queries take only the read lock once the tree is built.
14 *
15 * Layout: Header -> reader_slots[1024] -> nodes[capacity] -> build_idx[capacity]
16 */
17  
18 #ifndef IT_H
19 #define IT_H
20  
21 #include <stddef.h>
22 #include <stdint.h>
23 #include <stdlib.h>
24 #include <string.h>
25 #include <unistd.h>
26 #include <fcntl.h>
27 #include <errno.h>
28 #include <time.h>
29 #include <limits.h>
30 #include <signal.h>
31 #include <stdio.h>
32 #include <math.h>
33 #include <sys/mman.h>
34 #include <sys/stat.h>
35 #include <sys/file.h>
36 #include <sys/syscall.h>
37 #include <linux/futex.h>
38 #include <pthread.h>
39  
40 #if defined(__BYTE_ORDER__) && __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
41 #error "intervaltree.h: requires little-endian architecture"
42 #endif
43  
44  
45 /* ================================================================
46 * Constants
47 * ================================================================ */
48  
49 #define IT_MAGIC 0x52545649 /* IntervalTree */
50 #define IT_VERSION 2 /* 2: added the occupancy bitmap region (layout change) */
51 #define IT_ERR_BUFLEN (PATH_MAX + 256)
52 #ifndef IT_READER_SLOTS
53 #define IT_READER_SLOTS 1024 /* max concurrent reader processes for dead-process recovery */
54 #endif
55 /* Occupancy bitmap: one bit per reader slot, set when a process claims a slot and
56 * cleared on clean release. A writer scans these IT_OCC_WORDS words to visit
57 * only OCCUPIED slots (O(words + live readers)) instead of all IT_READER_SLOTS. */
58 #define IT_OCC_WORDS (((IT_READER_SLOTS) + 63) / 64) /* 16 for 1024 slots */
59 #define IT_OCC_BYTES ((uint64_t)IT_OCC_WORDS * 8) /* 128 bytes */
60 #define IT_MIN_CAP 1
61 #define IT_MAX_CAP 0x1000000U /* 2^24 intervals cap (index fits uint32, < IT_NIL) */
62 #define IT_NIL 0xFFFFFFFFU /* empty child / root sentinel */
63 /* A balanced bulk-built tree over <= 2^24 intervals is <= ~25 deep; this cap is
64 * a runaway guard so a Layer-B-corrupted link chain (a cycle, or a degenerate
65 * chain of valid indices) cannot recurse a query into a stack overflow. */
66 #define IT_MAX_DEPTH 96
67  
68 #define IT_ERR(fmt, ...) do { if (errbuf) snprintf(errbuf, IT_ERR_BUFLEN, fmt, ##__VA_ARGS__); } while (0)
69  
70 /* ================================================================
71 * Structs
72 * ================================================================ */
73  
74 /* Per-process slot for dead-process recovery. In the reader-slots-only rwlock a
75 * reader's ENTIRE contribution to the shared lock is `rdepth` in its OWN slot --
76 * there is no separate shared reader counter to fall out of sync with it -- so a
77 * dead reader's contribution is exactly this one word, which a draining writer
78 * neutralises by clearing the slot's pid (the scan then ignores the slot). No
79 * orphaned counter can exist, so there is no quiescent force-reset and sustained
80 * readers cannot starve a writer. _rsv1/_rsv2 are kept only to preserve the
81 * 16-byte slot size across the already-released builds. */
82 typedef struct {
83 uint32_t pid; /* 0 = unclaimed */
84 uint32_t rdepth; /* read-locks THIS process currently holds (recursion-safe) */
85 uint32_t _rsv1; /* reserved (was waiters_parked); unused, kept for layout size */
86 uint32_t _rsv2; /* reserved (was writers_parked); unused, kept for layout size */
87 } ItReaderSlot;
88  
89 struct ItHeader {
90 uint32_t magic, version; /* 0,4 */
91 uint32_t capacity; /* 8 max intervals */
92 uint32_t _pad0; /* 12 */
93 uint64_t count; /* 16 intervals inserted */
94 uint32_t root; /* 24 root node index, or IT_NIL when empty */
95 uint32_t dirty; /* 28 1 if the tree needs a (re)build before querying */
96 uint64_t nodes_off; /* 32 offset of the node array */
97 uint64_t idx_off; /* 40 offset of the build scratch (capacity uint32) */
98 uint64_t total_size; /* 48 */
99 uint64_t reader_slots_off; /* 56 */
100 uint32_t wlock; /* 64 WRITER word ONLY: 0 (free) or WRITER_BIT|pid. NOT a reader count. */
101 uint32_t rwait; /* 68 parked-waiter hint (readers+writers blocked on wlock); over-count-safe */
102 uint32_t drain_seq; /* 72 futex bumped by a reader releasing under a draining writer (wakes it) */
103 uint32_t slotless_rdepth; /* readers holding with no reader-slot (documented residual) */
104 uint64_t stat_ops; /* 80 */
105 uint8_t sealed; /* 88 0 = mutable, 1 = frozen (read-only; lock-free reads) */
106 uint8_t _pad[167]; /* 89..255 */
107 };
108 typedef struct ItHeader ItHeader;
109  
110 _Static_assert(sizeof(ItHeader) == 256, "ItHeader must be 256 bytes");
111  
112 /* One interval node: [lo, hi] with a user payload id, plus max_hi = the maximum
113 * hi endpoint over this node's whole subtree (the augmentation that lets a query
114 * prune subtrees that cannot reach the query point/range). A balanced BST keyed
115 * by lo; left/right are child indices (IT_NIL for none). */
116 typedef struct {
117 int64_t lo, hi;
118 int64_t max_hi;
119 uint64_t payload;
120 uint32_t left, right;
121 } ItNode;
122 _Static_assert(sizeof(ItNode) == 40, "ItNode must be 40 bytes");
123  
124 /* ---- Process-local handle ---- */
125  
126 typedef struct ItHandle {
127 ItHeader *hdr;
128 ItReaderSlot *reader_slots; /* IT_READER_SLOTS entries */
129 uint64_t *occ; /* IT_OCC_WORDS-word slot-occupancy bitmap (trusted layout offset) */
130 void *base; /* mmap base */
131 uint64_t nodes_off; /* validated offsets, cached: never re-read from the peer-writable header */
132 uint64_t idx_off;
133 uint32_t capacity; /* cached */
134 size_t mmap_size;
135 char *path; /* backing file path (strdup'd) */
136 int backing_fd; /* memfd or reopened-fd to close on destroy, -1 for file/anon */
137 uint32_t my_slot_idx; /* UINT32_MAX if all slots taken (no recovery for this handle) */
138 uint32_t cached_pid; /* getpid() cached at last slot claim */
139 uint32_t cached_fork_gen; /* it_fork_gen value at last slot claim */
140 uint32_t slotless_held; /* read-locks this process holds with no reader-slot */
141 int readonly; /* 1 = frozen O_RDONLY/PROT_READ view: lock-free reads, mutation croaks */
142 } ItHandle;
143  
144 /* ================================================================
145 * Futex-based write-preferring read-write lock (reader-slots-only)
146 * with dead-process recovery
147 *
148 * The reader count is NOT stored in a shared counter. It is DISTRIBUTED across
149 * per-process reader slots: each slot's `rdepth` is that process's entire
150 * contribution to the lock. A reader publishes its presence in its own slot and
151 * then re-checks the writer word; a writer publishes the writer word and then
152 * scans every slot until all live readers' rdepth reach 0. Sequentially-
153 * consistent store+load on each side (a Dekker handshake) gives mutual exclusion.
154 *
155 * Because a reader's whole contribution is ONE atomic word owned by ONE process,
156 * a crashed reader is recovered by clearing that one slot (CAS its pid to 0) --
157 * there is no second counter to strand, no orphaned +1, and therefore no
158 * quiescent force-reset. A reader killed anywhere in rdlock/rdunlock leaves at
159 * most `rdepth>0` in its dead slot, which the draining writer clears directly, so
160 * sustained read traffic can never starve a writer. Write-preference is inherent
161 * in the gate (new readers see wlock!=0 and yield), so there is no reader-count
162 * yield hack.
163 * ================================================================ */
164  
165 #define IT_RWLOCK_SPIN_LIMIT 32
166 #define IT_LOCK_TIMEOUT_SEC 2 /* FUTEX_WAIT timeout for stale-lock detection / drain re-scan */
167  
168 0 static inline void it_rwlock_spin_pause(void) {
169 #if defined(__x86_64__) || defined(__i386__)
170 0 __asm__ volatile("pause" ::: "memory");
171 #elif defined(__aarch64__)
172 __asm__ volatile("yield" ::: "memory");
173 #else
174 __asm__ volatile("" ::: "memory");
175 #endif
176 0 }
177  
178 /* Writer word encoding: WRITER_BIT|pid when write-locked, 0 when free. */
179 #define IT_RWLOCK_WRITER_BIT 0x80000000U
180 #define IT_RWLOCK_PID_MASK 0x7FFFFFFFU
181 #define IT_RWLOCK_WR(pid) (IT_RWLOCK_WRITER_BIT | ((uint32_t)(pid) & IT_RWLOCK_PID_MASK))
182  
183 /* A zombie (dead but not yet reaped) still answers kill(pid,0) as alive, so a
184 * process that crashed while holding the lock and lingers unreaped would never
185 * be recovered. Treat /proc/<pid>/stat state 'Z' as dead. Linux-only (as is
186 * this module); if /proc is unreadable we fall back to "alive" (safe: we never
187 * force-recover a possibly-live holder). */
188 0 static inline int it_pid_is_zombie(uint32_t pid) {
189 char path[32], buf[256];
190 0 snprintf(path, sizeof(path), "/proc/%u/stat", (unsigned)pid);
191 0 int fd = open(path, O_RDONLY | O_CLOEXEC);
192 0 ▶ if (fd < 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (fd < 0) return 0; 0 0 0
193 0 ssize_t n = read(fd, buf, sizeof(buf) - 1);
194 0 close(fd);
195 0 ▶ if (n <= 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (n <= 0) return 0; 0 0 0
196 0 buf[n] = '\0';
197 /* "pid (comm) state ..."; comm may contain ')', so scan to the last one. */
198 0 char *rp = strrchr(buf, ')');
199 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
200 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
201 }
202 /* 1 if alive or unknown, 0 if definitely dead. Cannot detect PID reuse: a
203 * recycled PID reports "alive" and the slot is not reclaimed until that
204 * process exits. See "Crash Safety" in the POD. */
205 0 static inline int it_pid_alive(uint32_t pid) {
206 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
207 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
208 0 return !it_pid_is_zombie(pid); /* kill() also succeeds for a zombie -> treat as dead */
209 }
210  
211 /* Force-recover a stale WRITE lock left by a dead writer (held or mid-drain).
212 * CAS to OUR pid to hold the lock while fixing shared state, then release.
213 * Using our pid (not a bare WRITER_BIT sentinel) means a subsequent recovering
214 * process can detect and re-recover if we crash mid-recovery. */
215 0 static inline void it_recover_stale_lock(ItHandle *h, uint32_t observed_wlock) {
216 0 ItHeader *hdr = h->hdr;
217 0 uint32_t mypid = IT_RWLOCK_WR((uint32_t)getpid());
218 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
219 mypid, 0, __ATOMIC_ACQUIRE, __ATOMIC_RELAXED))
220 0 return;
221 /* We now hold the write lock as mypid. No additional shared state needs
222 * repair here (this module has no seqlock); just release the lock. */
223 0 __atomic_store_n(&hdr->wlock, 0, __ATOMIC_SEQ_CST);
224 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
225 0 syscall(SYS_futex, &hdr->wlock, FUTEX_WAKE, INT_MAX, NULL, NULL, 0);
226 }
227  
228 static const struct timespec it_lock_timeout = { IT_LOCK_TIMEOUT_SEC, 0 };
229  
230 /* Process-global fork-generation counter. Incremented in the pthread_atfork
231 * child callback so every open handle detects a fork transition on the next
232 * lock call without paying a getpid() syscall on the hot path. */
233 static uint32_t it_fork_gen = 1;
234 static pthread_once_t it_atfork_once = PTHREAD_ONCE_INIT;
235 0 static void it_on_fork_child(void) {
236 0 __atomic_add_fetch(&it_fork_gen, 1, __ATOMIC_RELAXED);
237 0 }
238 4 static void it_atfork_init(void) {
239 4 pthread_atfork(NULL, NULL, it_on_fork_child);
240 4 }
241  
242 /* Ensure this process owns a reader slot. Called from the lock helpers so
243 * that fork()'d children pick up their own slot lazily instead of sharing
244 * the parent's. Hot-path is a single relaxed load + compare; only on a
245 * fork-generation mismatch do we touch getpid() and scan slots. */
246 /* Occupancy bitmap: set a slot's bit when it is claimed, clear it on clean
247 * release. SEQ_CST so a set bit is ordered before the slot's rdepth can go
248 * non-zero (bit set in claim, which precedes any rdlock), letting a writer's
249 * SEQ_CST bitmap scan never miss a slot a committed reader holds. */
250 27 static inline void it_occ_set(ItHandle *h, uint32_t s) {
251 27 __atomic_fetch_or(&h->occ[s >> 6], (uint64_t)1 << (s & 63), __ATOMIC_SEQ_CST);
252 27 }
253 27 static inline void it_occ_clear(ItHandle *h, uint32_t s) {
254 27 __atomic_fetch_and(&h->occ[s >> 6], ~((uint64_t)1 << (s & 63)), __ATOMIC_SEQ_CST);
255 27 }
256  
257 static inline void it_reader_wake_drain(ItHandle *h);
258 27 static inline void it_reset_reader_slot(ItHandle *h, uint32_t s) {
259 27 uint32_t stale = __atomic_exchange_n(&h->reader_slots[s].rdepth, 0, __ATOMIC_SEQ_CST);
260 27 it_occ_set(h, s);
261 27 h->my_slot_idx = s;
262 /* A draining writer may have seen the predecessor's depth with our new pid. */
263 27 ▶ if (stale) it_reader_wake_drain(h);
Branch: 1 branch
BranchTrueFalseTotal
if (stale) it_reader_wake_drain(h); 0 27 27
264 27 }
265  
266 2220 static inline void it_claim_reader_slot(ItHandle *h) {
267 2220 uint32_t cur_gen = __atomic_load_n(&it_fork_gen, __ATOMIC_RELAXED);
268 2220 ▶ 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)) 2193 27 2220
if (__builtin_expect(cur_gen == h->cached_fork_gen && h->my_slot_idx != UINT32_MAX, 1)) 2193 0 2193
269 2193 return;
270 /* Cold path -- register the atfork hook once per process, then claim. */
271 27 pthread_once(&it_atfork_once, it_atfork_init);
272 /* Re-read after pthread_once: it_on_fork_child may have bumped it. */
273 27 cur_gen = __atomic_load_n(&it_fork_gen, __ATOMIC_RELAXED);
274 27 uint32_t now_pid = (uint32_t)getpid();
275 27 h->cached_pid = now_pid;
276 27 ▶ 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 */ 27 0 27
277 27 h->cached_fork_gen = cur_gen;
278 27 h->my_slot_idx = UINT32_MAX;
279 27 uint32_t start = now_pid % IT_READER_SLOTS;
280 /* Pass 1: take a free slot. */
281 30 ▶ for (uint32_t i = 0; i < IT_READER_SLOTS; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t i = 0; i < IT_READER_SLOTS; i++) { 30 0 30
282 30 uint32_t s = (start + i) % IT_READER_SLOTS;
283 30 uint32_t expected = 0;
284 30 ▶ if (__atomic_compare_exchange_n(&h->reader_slots[s].pid,
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_compare_exchange_n(&h->reader_slots[s].pid, 27 3 30
285 &expected, now_pid, 0,
286 __ATOMIC_ACQUIRE, __ATOMIC_RELAXED)) {
287 /* Fresh owner holds no read locks yet; clear any stale rdepth left by
288 * a dead predecessor (its contribution is dropped as we take over). */
289 27 it_reset_reader_slot(h, s);
290 27 return;
291 }
292 }
293 /* Pass 2: no free slot -- reclaim one whose owner is dead. Safe to take even
294 * if its rdepth>0: clearing pid drops the dead reader's entire contribution
295 * (a writer scan ignores rdepth when pid==0) and we reset rdepth to 0 as we
296 * claim it. */
297 0 ▶ for (uint32_t i = 0; i < IT_READER_SLOTS; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t i = 0; i < IT_READER_SLOTS; i++) { 0 0 0
298 0 uint32_t dpid = __atomic_load_n(&h->reader_slots[i].pid, __ATOMIC_ACQUIRE);
299 0 ▶ if (dpid == 0 || dpid == now_pid || it_pid_alive(dpid)) continue;
Branch: 3 branches
BranchTrueFalseTotal
if (dpid == 0 || dpid == now_pid || it_pid_alive(dpid)) continue; 0 0 0
if (dpid == 0 || dpid == now_pid || it_pid_alive(dpid)) continue; 0 0 0
if (dpid == 0 || dpid == now_pid || it_pid_alive(dpid)) continue; 0 0 0
300 0 uint32_t expected = dpid;
301 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
302 __ATOMIC_ACQUIRE, __ATOMIC_RELAXED)) {
303 0 it_reset_reader_slot(h, i);
304 0 return;
305 }
306 }
307 /* Table full -- leave my_slot_idx = UINT32_MAX so this handle takes the
308 * slotless path (lock still works; recovery of THIS reader's death is the
309 * documented slotless limitation). */
310 }
311  
312 /* Inspect the writer word after a futex-wait timeout. If a dead writer holds
313 * it, force-recover. Dead READERS need no action here: only a writer that owns
314 * wlock drains readers, and it clears dead readers inline in its own scan. */
315 0 static inline void it_recover_after_timeout(ItHandle *h) {
316 0 uint32_t val = __atomic_load_n(&h->hdr->wlock, __ATOMIC_RELAXED);
317 0 ▶ if (val >= IT_RWLOCK_WRITER_BIT) {
Branch: 1 branch
BranchTrueFalseTotal
if (val >= IT_RWLOCK_WRITER_BIT) { 0 0 0
318 0 uint32_t pid = val & IT_RWLOCK_PID_MASK;
319 0 ▶ if (!it_pid_alive(pid))
Branch: 1 branch
BranchTrueFalseTotal
if (!it_pid_alive(pid)) 0 0 0
320 0 it_recover_stale_lock(h, val);
321 }
322 0 }
323  
324 /* Bump/drop the parked-waiter hint. Both readers (blocked at the gate) and
325 * writers (blocked acquiring wlock) wait on the wlock futex and use this, so
326 * wrunlock/recover know whether a FUTEX_WAKE is worth a syscall. A waiter
327 * SIGKILLed while parked leaves rwait over-counted -> at most a spurious wake
328 * (harmless); it can never under-count, so no wakeup is lost. */
329 0 static inline void it_park(ItHandle *h) {
330 0 __atomic_add_fetch(&h->hdr->rwait, 1, __ATOMIC_SEQ_CST);
331 0 }
332 0 static inline void it_unpark(ItHandle *h) {
333 0 __atomic_sub_fetch(&h->hdr->rwait, 1, __ATOMIC_RELAXED);
334 0 }
335  
336 /* Publish (inc) / retract (dec) this reader's presence -- its ENTIRE
337 * contribution to the lock. A slotted reader uses its slot's rdepth; a reader
338 * that could not claim a slot uses the global slotless_rdepth. inc() is SEQ_CST
339 * so the wlock re-check that follows it in rdlock forms a Dekker handshake with
340 * the writer's SEQ_CST wlock-store + rdepth-scan. leave() peels slotless first
341 * so a slot claimed mid-hold cannot misattribute the decrement. */
342 254 static inline void it_rdepth_inc(ItHandle *h) {
343 254 ▶ if (h->my_slot_idx != UINT32_MAX) {
Branch: 1 branch
BranchTrueFalseTotal
if (h->my_slot_idx != UINT32_MAX) { 254 0 254
344 254 __atomic_add_fetch(&h->reader_slots[h->my_slot_idx].rdepth, 1, __ATOMIC_SEQ_CST);
345 } else {
346 0 __atomic_add_fetch(&h->hdr->slotless_rdepth, 1, __ATOMIC_SEQ_CST);
347 0 h->slotless_held++;
348 }
349 254 }
350 254 static inline void it_rdepth_dec(ItHandle *h) {
351 254 ▶ if (h->slotless_held > 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (h->slotless_held > 0) { 0 254 254
352 0 h->slotless_held--;
353 0 __atomic_sub_fetch(&h->hdr->slotless_rdepth, 1, __ATOMIC_SEQ_CST);
354 254 ▶ } else if (h->my_slot_idx != UINT32_MAX) {
Branch: 1 branch
BranchTrueFalseTotal
} else if (h->my_slot_idx != UINT32_MAX) { 254 0 254
355 254 __atomic_sub_fetch(&h->reader_slots[h->my_slot_idx].rdepth, 1, __ATOMIC_SEQ_CST);
356 }
357 254 }
358  
359 /* Wake a writer that may be draining readers (it waits on drain_seq). Called
360 * after every rdepth decrement so a released read lock lets the writer re-scan
361 * promptly instead of waiting out its timeout. */
362 254 static inline void it_reader_wake_drain(ItHandle *h) {
363 /* Pair the SC decrement/check with the writer's SC gate/scan. */
364 254 ▶ 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 254 254
365 0 __atomic_add_fetch(&h->hdr->drain_seq, 1, __ATOMIC_RELEASE);
366 0 syscall(SYS_futex, &h->hdr->drain_seq, FUTEX_WAKE, 1, NULL, NULL, 0);
367 }
368 254 }
369  
370 254 static inline void it_rwlock_rdlock(ItHandle *h) {
371 254 it_claim_reader_slot(h);
372 254 ItHeader *hdr = h->hdr;
373 254 for (int spin = 0; ; spin++) {
374 254 uint32_t cur = __atomic_load_n(&hdr->wlock, __ATOMIC_ACQUIRE);
375 254 ▶ if (cur == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (cur == 0) { 254 0 254
376 /* Optimistically take the read: publish rdepth, then re-check wlock.
377 * SEQ_CST inc + SEQ_CST load vs the writer's SEQ_CST wlock CAS +
378 * SEQ_CST rdepth scan: by the single total order of SEQ_CST ops the
379 * two sides cannot both miss each other, so we never hold
380 * concurrently with a writer. */
381 254 it_rdepth_inc(h);
382 254 ▶ if (__atomic_load_n(&hdr->wlock, __ATOMIC_SEQ_CST) == 0)
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&hdr->wlock, __ATOMIC_SEQ_CST) == 0) 254 0 254
383 254 return; /* no writer after our publish -> we hold the read lock */
384 /* A writer appeared during our publish -- yield to it (write-preferring). */
385 0 it_rdepth_dec(h);
386 0 it_reader_wake_drain(h); /* let the draining writer see rdepth drop */
387 0 spin = 0;
388 0 continue;
389 }
390 /* wlock != 0: a writer holds or is acquiring. Recover if it is dead. */
391 0 if (cur >= IT_RWLOCK_WRITER_BIT &&
392 0 !it_pid_alive(cur & IT_RWLOCK_PID_MASK)) {
393 0 it_recover_stale_lock(h, cur);
394 0 spin = 0;
395 0 continue;
396 }
397 0 ▶ if (__builtin_expect(spin < IT_RWLOCK_SPIN_LIMIT, 1)) {
Branch: 1 branch
BranchTrueFalseTotal
if (__builtin_expect(spin < IT_RWLOCK_SPIN_LIMIT, 1)) { 0 0 0
398 0 it_rwlock_spin_pause();
399 0 continue;
400 }
401 0 it_park(h);
402 0 cur = __atomic_load_n(&hdr->wlock, __ATOMIC_SEQ_CST);
403 0 ▶ if (cur != 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (cur != 0) { 0 0 0
404 0 long rc = syscall(SYS_futex, &hdr->wlock, FUTEX_WAIT, cur,
405 &it_lock_timeout, NULL, 0);
406 0 ▶ if (rc == -1 && errno == ETIMEDOUT) {
Branch: 2 branches
BranchTrueFalseTotal
if (rc == -1 && errno == ETIMEDOUT) { 0 0 0
if (rc == -1 && errno == ETIMEDOUT) { 0 0 0
407 0 it_unpark(h);
408 0 it_recover_after_timeout(h);
409 0 spin = 0;
410 0 continue;
411 }
412 }
413 0 it_unpark(h);
414 0 spin = 0;
415 }
416 }
417  
418 254 static inline void it_rwlock_rdunlock(ItHandle *h) {
419 254 it_rdepth_dec(h); /* RELEASE: drop our entire contribution */
420 254 it_reader_wake_drain(h); /* if a writer is draining, wake it to re-scan */
421 254 }
422  
423 1966 static inline void it_rwlock_wrlock(ItHandle *h) {
424 1966 it_claim_reader_slot(h); /* refresh cached_pid across fork */
425 1966 ItHeader *hdr = h->hdr;
426 /* Encode PID in the wlock word itself (0x80000000 | pid) to eliminate any
427 * crash window between acquiring the lock and storing the owner. */
428 1966 uint32_t mypid = IT_RWLOCK_WR(h->cached_pid);
429 /* Phase 1: acquire the writer word (mutual exclusion among writers). */
430 1966 for (int spin = 0; ; spin++) {
431 1966 uint32_t expected = 0;
432 1966 ▶ if (__atomic_compare_exchange_n(&hdr->wlock, &expected, mypid,
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_compare_exchange_n(&hdr->wlock, &expected, mypid, 1966 0 1966
433 0, __ATOMIC_SEQ_CST, __ATOMIC_RELAXED))
434 1966 break;
435 /* Contended: expected now holds the current wlock value. */
436 0 if (expected >= IT_RWLOCK_WRITER_BIT &&
437 0 !it_pid_alive(expected & IT_RWLOCK_PID_MASK)) {
438 0 it_recover_stale_lock(h, expected);
439 0 spin = 0;
440 0 continue;
441 }
442 0 ▶ if (__builtin_expect(spin < IT_RWLOCK_SPIN_LIMIT, 1)) {
Branch: 1 branch
BranchTrueFalseTotal
if (__builtin_expect(spin < IT_RWLOCK_SPIN_LIMIT, 1)) { 0 0 0
443 0 it_rwlock_spin_pause();
444 0 continue;
445 }
446 0 it_park(h);
447 0 uint32_t cur = __atomic_load_n(&hdr->wlock, __ATOMIC_SEQ_CST);
448 0 ▶ if (cur != 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (cur != 0) { 0 0 0
449 0 long rc = syscall(SYS_futex, &hdr->wlock, FUTEX_WAIT, cur,
450 &it_lock_timeout, NULL, 0);
451 0 ▶ if (rc == -1 && errno == ETIMEDOUT) {
Branch: 2 branches
BranchTrueFalseTotal
if (rc == -1 && errno == ETIMEDOUT) { 0 0 0
if (rc == -1 && errno == ETIMEDOUT) { 0 0 0
452 0 it_unpark(h);
453 0 it_recover_after_timeout(h);
454 0 spin = 0;
455 0 continue;
456 }
457 }
458 0 it_unpark(h);
459 0 spin = 0;
460 }
461 /* Phase 2: we own wlock, so no NEW reader can join (they see wlock!=0 and
462 * yield). Drain the readers that were already holding when we won the CAS.
463 * The SEQ_CST CAS above + the SEQ_CST rdepth loads below are the writer side
464 * of the Dekker handshake. */
465 0 for (;;) {
466 1966 uint32_t v = __atomic_load_n(&hdr->drain_seq, __ATOMIC_ACQUIRE); /* snapshot BEFORE scan */
467 1966 int busy = 0;
468 /* Visit only OCCUPIED slots via the occupancy bitmap (SEQ_CST: a committed
469 * reader's bit -- set in claim, before its rdepth++ -- is ordered before
470 * this scan, so no held slot is skipped). O(IT_OCC_WORDS + live readers)
471 * instead of O(IT_READER_SLOTS). */
472 33422 ▶ for (uint32_t w = 0; w < IT_OCC_WORDS; w++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t w = 0; w < IT_OCC_WORDS; w++) { 31456 1966 33422
473 31456 uint64_t word = __atomic_load_n(&h->occ[w], __ATOMIC_SEQ_CST);
474 33431 ▶ while (word) {
Branch: 1 branch
BranchTrueFalseTotal
while (word) { 1975 31456 33431
475 1975 uint32_t i = (w << 6) + (uint32_t)__builtin_ctzll(word);
476 1975 word &= word - 1; /* consume this bit (local copy) */
477 1975 uint32_t rd = __atomic_load_n(&h->reader_slots[i].rdepth, __ATOMIC_SEQ_CST);
478 1975 ▶ if (rd == 0) continue; /* occupied but not read-locking now */
Branch: 1 branch
BranchTrueFalseTotal
if (rd == 0) continue; /* occupied but not read-locking now */ 1975 0 1975
479 0 uint32_t pid = __atomic_load_n(&h->reader_slots[i].pid, __ATOMIC_ACQUIRE);
480 0 ▶ if (pid == 0) continue; /* stale rdepth on a freed slot */
Branch: 1 branch
BranchTrueFalseTotal
if (pid == 0) continue; /* stale rdepth on a freed slot */ 0 0 0
481 0 ▶ if (!it_pid_alive(pid)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!it_pid_alive(pid)) { 0 0 0
482 /* Dead reader: drop its pid so the slot no longer counts. Leave
483 * the occ bit set (harmless -- a later scan hits pid==0 and skips,
484 * a re-claim re-sets it) to avoid racing a concurrent claimant. */
485 0 uint32_t ep = pid;
486 0 __atomic_compare_exchange_n(&h->reader_slots[i].pid, &ep, 0,
487 0, __ATOMIC_ACQ_REL, __ATOMIC_RELAXED);
488 0 continue;
489 }
490 0 busy = 1; /* live reader still holding */
491 }
492 }
493 /* A live slotless reader keeps us waiting; a crashed slotless reader that
494 * cannot be attributed to a pid is the documented slotless limitation. */
495 1966 ▶ 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 1966 1966
496 0 busy = 1;
497 1966 ▶ if (!busy)
Branch: 1 branch
BranchTrueFalseTotal
if (!busy) 1966 0 1966
498 1966 return; /* exclusive: wlock held + every rdepth 0 */
499 /* Wait for a reader to release (drain_seq bump) or time out to re-scan
500 * (which reclaims any newly-dead slotted reader). */
501 0 syscall(SYS_futex, &hdr->drain_seq, FUTEX_WAIT, v, &it_lock_timeout, NULL, 0);
502 }
503 }
504  
505 1966 static inline void it_rwlock_wrunlock(ItHandle *h) {
506 1966 ItHeader *hdr = h->hdr;
507 /* Pair with the waiter's SC hint increment and gate re-check. */
508 1966 __atomic_store_n(&hdr->wlock, 0, __ATOMIC_SEQ_CST);
509 1966 ▶ 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 1966 1966
510 0 syscall(SYS_futex, &hdr->wlock, FUTEX_WAKE, INT_MAX, NULL, NULL, 0);
511 1966 }
512  
513 /* ================================================================
514 * Layout math + create / open / destroy
515 *
516 * Layout: Header -> reader_slots[1024] -> nodes[capacity] -> build_idx[capacity]
517 * ================================================================ */
518  
519 /* Single source of truth for the mmap region layout offsets.
520 * Layout: Header -> reader_slots[1024] -> occ bitmap -> nodes[capacity] -> build_idx[capacity] */
521 typedef struct { uint64_t reader_slots, occ, nodes, idx, total; } ItLayout;
522  
523 145 static inline ItLayout it_layout_for(uint32_t capacity) {
524 ItLayout L;
525 145 L.reader_slots = sizeof(ItHeader);
526 145 L.occ = L.reader_slots + (uint64_t)IT_READER_SLOTS * sizeof(ItReaderSlot);
527 145 L.nodes = L.occ + IT_OCC_BYTES;
528 145 L.nodes = (L.nodes + 7) & ~(uint64_t)7;
529 145 L.idx = L.nodes + (uint64_t)capacity * sizeof(ItNode);
530 145 L.idx = (L.idx + 7) & ~(uint64_t)7;
531 145 L.total = L.idx + (uint64_t)capacity * sizeof(uint32_t);
532 145 return L;
533 }
534  
535 77 static inline uint64_t it_total_size(uint32_t capacity) {
536 77 return it_layout_for(capacity).total;
537 }
538  
539 23 static inline void it_init_header(void *base, uint32_t capacity, uint64_t total) {
540 23 ItLayout L = it_layout_for(capacity);
541 23 ItHeader *hdr = (ItHeader *)base;
542 23 memset(base, 0, (size_t)L.nodes); /* header + reader slots; node data is written on add */
543 23 hdr->version = IT_VERSION;
544 23 hdr->capacity = capacity;
545 23 hdr->count = 0;
546 23 hdr->root = IT_NIL;
547 23 hdr->dirty = 0;
548 23 hdr->nodes_off = L.nodes;
549 23 hdr->idx_off = L.idx;
550 23 hdr->total_size = total;
551 23 hdr->reader_slots_off = L.reader_slots;
552 /* Publish magic LAST, as a release store: it is the commit point, so a
553 creator killed before it leaves magic==0 and never a file mistaken for
554 a valid one. A kill during the field stores leaves one to remove by
555 hand. */
556 23 __atomic_store_n(&hdr->magic, IT_MAGIC, __ATOMIC_RELEASE);
557 23 __atomic_thread_fence(__ATOMIC_SEQ_CST);
558 23 }
559  
560 /* ---- accessors ---- */
561 57202 static inline ItNode *it_node(ItHandle *h, uint64_t i) { return (ItNode *)((char *)h->base + h->nodes_off) + i; }
562 19 static inline uint32_t *it_idx(ItHandle *h) { return (uint32_t *)((char *)h->base + h->idx_off); }
563  
564 /* Layer B trusted bound: number of nodes guaranteed within the real mapping.
565 * Equals capacity for a valid tree; every child index read from shared memory is
566 * checked against it so a corrupt link can never drive an access out of bounds. */
567 33 static inline uint64_t it_nodes_max(ItHandle *h) {
568 33 ▶ if (h->nodes_off >= h->mmap_size) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (h->nodes_off >= h->mmap_size) return 0; 0 33 33
569 33 return (h->mmap_size - h->nodes_off) / sizeof(ItNode);
570 }
571 #define IT_NODE_OK(h, i) ((uint32_t)(i) != IT_NIL && (uint64_t)(i) < (uint64_t)(h)->capacity)
572  
573 33 static inline ItHandle *it_setup(void *base, size_t map_size,
574 const char *path, int backing_fd) {
575 33 ItHeader *hdr = (ItHeader *)base;
576 33 ItHandle *h = (ItHandle *)calloc(1, sizeof(ItHandle));
577 33 ▶ if (!h) {
Branch: 1 branch
BranchTrueFalseTotal
if (!h) { 0 33 33
578 0 munmap(base, map_size);
579 0 ▶ if (backing_fd >= 0) close(backing_fd);
Branch: 1 branch
BranchTrueFalseTotal
if (backing_fd >= 0) close(backing_fd); 0 0 0
580 0 return NULL;
581 }
582 33 h->hdr = hdr;
583 33 h->base = base;
584 33 h->reader_slots = (ItReaderSlot *)((uint8_t *)base + sizeof(ItHeader)); /* trusted layout, not the peer-writable header offset */
585 /* Snapshot the geometry ONCE and re-verify it against the mapping, then
586 * derive every offset from the TRUSTED computed layout instead of the
587 * peer-writable header fields: a writer can flip capacity/idx_off in the
588 * window between it_validate_header and here, and idx_off is otherwise
589 * never range-checked (it_build_locked writes capacity*4 bytes at it_idx). */
590 {
591 33 uint32_t cap = __atomic_load_n(&hdr->capacity, __ATOMIC_ACQUIRE);
592 66 ▶ if (cap < IT_MIN_CAP || cap > IT_MAX_CAP ||
Branch: 1 branch
BranchTrueFalseTotal
if (cap < IT_MIN_CAP || cap > IT_MAX_CAP || 33 0 33
593 33 it_total_size(cap) != (uint64_t)map_size) {
594 0 munmap(base, map_size);
595 0 ▶ if (backing_fd >= 0) close(backing_fd);
Branch: 1 branch
BranchTrueFalseTotal
if (backing_fd >= 0) close(backing_fd); 0 0 0
596 0 free(h);
597 0 return NULL;
598 }
599 33 ItLayout L = it_layout_for(cap);
600 33 h->occ = (uint64_t *)((uint8_t *)base + L.occ);
601 33 h->nodes_off = L.nodes;
602 33 h->idx_off = L.idx;
603 33 h->capacity = cap;
604 }
605 33 h->mmap_size = map_size;
606 /* Layer B: clamp the cached capacity to the number of nodes that actually fit */
607 {
608 33 uint64_t fit = it_nodes_max(h);
609 33 ▶ if ((uint64_t)h->capacity > fit) h->capacity = (uint32_t)fit;
Branch: 1 branch
BranchTrueFalseTotal
if ((uint64_t)h->capacity > fit) h->capacity = (uint32_t)fit; 0 33 33
610 }
611 33 ▶ h->path = path ? strdup(path) : NULL;
Branch: 1 branch
BranchTrueFalseTotal
h->path = path ? strdup(path) : NULL; 18 15 33
612 33 h->backing_fd = backing_fd;
613 33 h->my_slot_idx = UINT32_MAX;
614 33 return h;
615 }
616  
617 /* Validate a mapped header (shared by it_create reopen and it_open_fd). */
618 16 static inline int it_validate_header(const ItHeader *hdr, uint64_t file_size) {
619 16 ▶ if (__atomic_load_n(&hdr->magic, __ATOMIC_ACQUIRE) != IT_MAGIC) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&hdr->magic, __ATOMIC_ACQUIRE) != IT_MAGIC) return 0; 4 12 16
620 12 ▶ if (hdr->version != IT_VERSION) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->version != IT_VERSION) return 0; 0 12 12
621 12 ▶ if (hdr->capacity < IT_MIN_CAP || hdr->capacity > IT_MAX_CAP) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (hdr->capacity < IT_MIN_CAP || hdr->capacity > IT_MAX_CAP) return 0; 12 0 12
if (hdr->capacity < IT_MIN_CAP || hdr->capacity > IT_MAX_CAP) return 0; 0 12 12
622 12 ▶ if (hdr->count > hdr->capacity) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->count > hdr->capacity) return 0; 0 12 12
623 12 ▶ if (hdr->total_size != file_size) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->total_size != file_size) return 0; 0 12 12
624 12 ▶ if (hdr->total_size != it_total_size(hdr->capacity)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->total_size != it_total_size(hdr->capacity)) return 0; 0 12 12
625 12 ItLayout L = it_layout_for(hdr->capacity);
626 12 ▶ 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 12 12
627 12 ▶ if (hdr->nodes_off != L.nodes) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->nodes_off != L.nodes) return 0; 0 12 12
628 12 ▶ if (hdr->idx_off != L.idx) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->idx_off != L.idx) return 0; 0 12 12
629 12 return 1;
630 }
631  
632 /* validate the requested capacity */
633 32 static int it_validate_args(uint64_t capacity, char *errbuf) {
634 32 ▶ if (errbuf) errbuf[0] = '\0';
Branch: 1 branch
BranchTrueFalseTotal
if (errbuf) errbuf[0] = '\0'; 32 0 32
635 32 ▶ if (capacity < IT_MIN_CAP || capacity > IT_MAX_CAP) { IT_ERR("capacity must be between 1 and 2^24"); return 0; }
Branch: 3 branches
BranchTrueFalseTotal
if (capacity < IT_MIN_CAP || capacity > IT_MAX_CAP) { IT_ERR("capacity must be between 1 and 2^24"); return 0; } 32 0 32
if (capacity < IT_MIN_CAP || capacity > IT_MAX_CAP) { IT_ERR("capacity must be between 1 and 2^24"); return 0; } 0 32 32
if (capacity < IT_MIN_CAP || capacity > IT_MAX_CAP) { IT_ERR("capacity must be between 1 and 2^24"); return 0; } 0 0 0
636 32 return 1;
637 }
638  
639 /* Securely obtain a fd for a path-backed segment: create it exclusively
640 * (O_CREAT|O_EXCL|O_NOFOLLOW at `mode`, default 0600 = owner-only), or, if it
641 * already exists, attach to it (O_RDWR|O_NOFOLLOW, no O_CREAT). O_EXCL blocks a
642 * pre-seeded or hard-linked file and O_NOFOLLOW a symlink swap, so a local
643 * attacker can no longer redirect or poison the backing store through the path.
644 * Cross-user sharing is opt-in via a wider `mode` (e.g. 0660); the caller still
645 * validates the file's contents via it_validate_header. */
646 19 static int it_secure_open(const char *path, mode_t mode, char *errbuf) {
647 19 ▶ for (int attempt = 0; attempt < 100; attempt++) {
Branch: 1 branch
BranchTrueFalseTotal
for (int attempt = 0; attempt < 100; attempt++) { 19 0 19
648 19 int fd = open(path, O_RDWR|O_CREAT|O_EXCL|O_NOFOLLOW|O_CLOEXEC, mode);
649 19 ▶ if (fd >= 0) { (void)fchmod(fd, mode); return fd; } /* exact mode: umask narrowed the O_EXCL create */
Branch: 1 branch
BranchTrueFalseTotal
if (fd >= 0) { (void)fchmod(fd, mode); return fd; } /* exact mode: umask narrowed the O_EXCL create */ 9 10 19
650 10 ▶ if (errno != EEXIST) { IT_ERR("create %s: %s", path, strerror(errno)); return -1; }
Branch: 2 branches
BranchTrueFalseTotal
if (errno != EEXIST) { IT_ERR("create %s: %s", path, strerror(errno)); return -1; } 0 10 10
if (errno != EEXIST) { IT_ERR("create %s: %s", path, strerror(errno)); return -1; } 0 0 0
651 10 fd = open(path, O_RDWR|O_NOFOLLOW|O_CLOEXEC);
652 10 ▶ if (fd >= 0) return fd;
Branch: 1 branch
BranchTrueFalseTotal
if (fd >= 0) return fd; 10 0 10
653 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
654 0 ▶ IT_ERR("open %s: %s", path, strerror(errno)); /* ELOOP => symlink rejected */
Branch: 1 branch
BranchTrueFalseTotal
IT_ERR("open %s: %s", path, strerror(errno)); /* ELOOP => symlink rejected */ 0 0 0
655 0 return -1;
656 }
657 0 ▶ IT_ERR("open %s: create/attach kept racing", path);
Branch: 1 branch
BranchTrueFalseTotal
IT_ERR("open %s: create/attach kept racing", path); 0 0 0
658 0 return -1;
659 }
660  
661 /* True iff the whole file is zero -- what an abandoned mid-init
662 creator leaves. Lets recovery re-init only a provably-empty file, never
663 one that merely starts with a zero word. Cold path, so a byte scan is
664 fine. Read, not mapped: a read fault on a tmpfs hole allocates the page. */
665 2 static int it_file_is_zero(int fd, uint64_t size) {
666 char buf[16384];
667 5 ▶ for (uint64_t off = 0; off < size; ) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint64_t off = 0; off < size; ) { 4 1 5
668 4 ssize_t n = pread(fd, buf, size - off < sizeof buf ? (size_t)(size - off) : sizeof buf, (off_t)off);
669 4 ▶ if (n <= 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (n <= 0) return 0; 0 4 4
670 42339 ▶ 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 42335 42336
for (ssize_t i = 0; i < n; i++) if (buf[i]) return 0; 42336 3 42339
671 3 off += (uint64_t)n;
672 }
673 1 return 1;
674 }
675  
676 /* Opt-in (DATA_INTERVALTREE_SHARED_SPARSE=0): reserving commits memory this module otherwise fills lazily. */
677 11 static int it_reserve(int fd, uint64_t size) {
678 11 const char *sp = getenv("DATA_INTERVALTREE_SHARED_SPARSE");
679 11 ▶ if (!sp || strcmp(sp, "0")) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (!sp || strcmp(sp, "0")) return 0; 0 11 11
if (!sp || strcmp(sp, "0")) return 0; 0 0 0
680 /* Before Linux 6.11 tmpfs gives up at any pending signal and undoes the allocation, so a
681 * periodic one could keep it from ever completing; SIGSTOP cannot be blocked. */
682 sigset_t all, old;
683 0 sigfillset(&all);
684 0 sigprocmask(SIG_BLOCK, &all, &old);
685 int e;
686 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
687 0 sigprocmask(SIG_SETMASK, &old, NULL);
688 0 ▶ if (e == 0 || e == EOPNOTSUPP || e == EINVAL) return 0;
Branch: 3 branches
BranchTrueFalseTotal
if (e == 0 || e == EOPNOTSUPP || e == EINVAL) return 0; 0 0 0
if (e == 0 || e == EOPNOTSUPP || e == EINVAL) return 0; 0 0 0
if (e == 0 || e == EOPNOTSUPP || e == EINVAL) return 0; 0 0 0
689 0 errno = e;
690 0 return -1;
691 }
692  
693 31 static ItHandle *it_create(const char *path, uint64_t capacity, mode_t mode, char *errbuf) {
694 31 ▶ if (!it_validate_args(capacity, errbuf)) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!it_validate_args(capacity, errbuf)) return NULL; 0 31 31
695  
696 31 uint64_t total = it_total_size((uint32_t)capacity);
697 31 int anonymous = (path == NULL);
698 31 int fd = -1;
699 size_t map_size;
700 void *base;
701  
702 31 ▶ if (anonymous) {
Branch: 1 branch
BranchTrueFalseTotal
if (anonymous) { 12 19 31
703 12 map_size = (size_t)total;
704 12 base = mmap(NULL, map_size, PROT_READ|PROT_WRITE, MAP_SHARED|MAP_ANONYMOUS, -1, 0);
705 12 ▶ if (base == MAP_FAILED) { IT_ERR("mmap: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { IT_ERR("mmap: %s", strerror(errno)); return NULL; } 0 12 12
if (base == MAP_FAILED) { IT_ERR("mmap: %s", strerror(errno)); return NULL; } 0 0 0
706 } else {
707 19 fd = it_secure_open(path, mode, errbuf);
708 29 ▶ if (fd < 0) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (fd < 0) return NULL; 0 19 19
709 19 ▶ if (flock(fd, LOCK_EX) < 0) { IT_ERR("flock: %s", strerror(errno)); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (flock(fd, LOCK_EX) < 0) { IT_ERR("flock: %s", strerror(errno)); close(fd); return NULL; } 0 19 19
if (flock(fd, LOCK_EX) < 0) { IT_ERR("flock: %s", strerror(errno)); close(fd); return NULL; } 0 0 0
710 struct stat st;
711 19 ▶ if (fstat(fd, &st) < 0) { IT_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fstat(fd, &st) < 0) { IT_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; } 0 19 19
if (fstat(fd, &st) < 0) { IT_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; } 0 0 0
712 19 int is_new = (st.st_size == 0);
713 19 ▶ if (!is_new && (uint64_t)st.st_size < sizeof(ItHeader)) {
Branch: 2 branches
BranchTrueFalseTotal
if (!is_new && (uint64_t)st.st_size < sizeof(ItHeader)) { 10 9 19
if (!is_new && (uint64_t)st.st_size < sizeof(ItHeader)) { 1 9 10
714 1 ▶ IT_ERR("%s: file too small (%lld)", path, (long long)st.st_size);
Branch: 1 branch
BranchTrueFalseTotal
IT_ERR("%s: file too small (%lld)", path, (long long)st.st_size); 1 0 1
715 1 flock(fd, LOCK_UN); close(fd); return NULL;
716 }
717 18 ▶ if (is_new && (st.st_uid != geteuid() || fchmod(fd, mode) < 0)) {
Branch: 3 branches
BranchTrueFalseTotal
if (is_new && (st.st_uid != geteuid() || fchmod(fd, mode) < 0)) { 9 9 18
if (is_new && (st.st_uid != geteuid() || fchmod(fd, mode) < 0)) { 9 0 9
if (is_new && (st.st_uid != geteuid() || fchmod(fd, mode) < 0)) { 0 9 9
718 0 ▶ IT_ERR("%s: refusing to initialize file not owned by us", path);
Branch: 1 branch
BranchTrueFalseTotal
IT_ERR("%s: refusing to initialize file not owned by us", path); 0 0 0
719 0 flock(fd, LOCK_UN); close(fd); return NULL;
720 }
721 18 ▶ if (is_new && ftruncate(fd, (off_t)total) < 0) {
Branch: 2 branches
BranchTrueFalseTotal
if (is_new && ftruncate(fd, (off_t)total) < 0) { 9 9 18
if (is_new && ftruncate(fd, (off_t)total) < 0) { 0 9 9
722 0 ▶ IT_ERR("ftruncate: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
IT_ERR("ftruncate: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; 0 0 0
723 }
724 18 ▶ if (is_new && it_reserve(fd, total) < 0) {
Branch: 2 branches
BranchTrueFalseTotal
if (is_new && it_reserve(fd, total) < 0) { 9 9 18
if (is_new && it_reserve(fd, total) < 0) { 0 9 9
725 0 ▶ IT_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
IT_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno)); 0 0 0
726 0 if (ftruncate(fd, 0) < 0) { /* best effort */ }
727 0 flock(fd, LOCK_UN); close(fd); return NULL;
728 }
729 18 ▶ map_size = is_new ? (size_t)total : (size_t)st.st_size;
Branch: 1 branch
BranchTrueFalseTotal
map_size = is_new ? (size_t)total : (size_t)st.st_size; 9 9 18
730 18 base = mmap(NULL, map_size, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
731 18 ▶ if (base == MAP_FAILED) {
Branch: 1 branch
BranchTrueFalseTotal
if (base == MAP_FAILED) { 0 18 18
732 0 ▶ IT_ERR("mmap: %s", strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
IT_ERR("mmap: %s", strerror(errno)); 0 0 0
733 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
734 0 flock(fd, LOCK_UN); close(fd); return NULL;
735 }
736 18 ▶ if (!is_new) {
Branch: 1 branch
BranchTrueFalseTotal
if (!is_new) { 9 9 18
737 9 ▶ if (!it_validate_header((ItHeader *)base, (uint64_t)st.st_size)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!it_validate_header((ItHeader *)base, (uint64_t)st.st_size)) { 4 5 9
738 /* Recover an abandoned mid-init file: a creator killed
739 * between the ftruncate and the header init leaves a
740 * full-size, all-zero (magic==0) file that would brick every
741 * future open of this path. Re-initialize ONLY when it is
742 * exactly our size, still uninitialized, and owned by us;
743 * anything else still errors. */
744 4 ▶ if (((ItHeader *)base)->magic == 0 && (uint64_t)st.st_size == total
Branch: 2 branches
BranchTrueFalseTotal
if (((ItHeader *)base)->magic == 0 && (uint64_t)st.st_size == total 3 1 4
if (((ItHeader *)base)->magic == 0 && (uint64_t)st.st_size == total 2 1 3
745 2 ▶ && st.st_uid == geteuid() && it_file_is_zero(fd, map_size)) {
Branch: 2 branches
BranchTrueFalseTotal
&& st.st_uid == geteuid() && it_file_is_zero(fd, map_size)) { 2 0 2
&& st.st_uid == geteuid() && it_file_is_zero(fd, map_size)) { 1 1 2
746 1 ▶ if (fchmod(fd, mode) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (fchmod(fd, mode) < 0) { 0 1 1
747 0 ▶ IT_ERR("%s: fchmod: %s", path, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
IT_ERR("%s: fchmod: %s", path, strerror(errno)); 0 0 0
748 0 munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
749 }
750 1 ▶ if (it_reserve(fd, total) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (it_reserve(fd, total) < 0) { 0 1 1
751 0 ▶ IT_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
IT_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno)); 0 0 0
752 0 munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
753 }
754 1 it_init_header(base, (uint32_t)capacity, total);
755 1 flock(fd, LOCK_UN); close(fd);
756 1 return it_setup(base, map_size, path, -1);
757 }
758 3 ▶ if (((ItHeader *)base)->magic == 0 && (uint64_t)st.st_size == total
Branch: 2 branches
BranchTrueFalseTotal
if (((ItHeader *)base)->magic == 0 && (uint64_t)st.st_size == total 2 1 3
if (((ItHeader *)base)->magic == 0 && (uint64_t)st.st_size == total 1 1 2
759 1 ▶ && st.st_uid == geteuid()) {
Branch: 1 branch
BranchTrueFalseTotal
&& st.st_uid == geteuid()) { 1 0 1
760 1 ▶ IT_ERR("%s: incomplete interval tree file left by an interrupted create; remove it and retry", path);
Branch: 1 branch
BranchTrueFalseTotal
IT_ERR("%s: incomplete interval tree file left by an interrupted create; remove it and retry", path); 1 0 1
761 1 munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
762 }
763 2 ▶ IT_ERR("invalid interval tree file"); munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
IT_ERR("invalid interval tree file"); munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL; 2 0 2
764 }
765 5 ▶ if (__atomic_load_n(&((ItHeader *)base)->sealed, __ATOMIC_ACQUIRE)) {
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&((ItHeader *)base)->sealed, __ATOMIC_ACQUIRE)) { 1 4 5
766 1 ▶ IT_ERR("%s is frozen (read-only); open it with new_readonly", path);
Branch: 1 branch
BranchTrueFalseTotal
IT_ERR("%s is frozen (read-only); open it with new_readonly", path); 1 0 1
767 1 munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
768 }
769 4 flock(fd, LOCK_UN); close(fd);
770 4 return it_setup(base, map_size, path, -1);
771 }
772 }
773 21 it_init_header(base, (uint32_t)capacity, total);
774 21 ▶ if (fd >= 0) { flock(fd, LOCK_UN); close(fd); }
Branch: 1 branch
BranchTrueFalseTotal
if (fd >= 0) { flock(fd, LOCK_UN); close(fd); } 9 12 21
775 21 return it_setup(base, map_size, path, -1);
776 }
777  
778 1 static ItHandle *it_create_memfd(const char *name, uint64_t capacity, char *errbuf) {
779 1 ▶ if (!it_validate_args(capacity, errbuf)) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!it_validate_args(capacity, errbuf)) return NULL; 0 1 1
780  
781 1 uint64_t total = it_total_size((uint32_t)capacity);
782 1 ▶ int fd = memfd_create(name ? name : "intervaltree", MFD_CLOEXEC | MFD_ALLOW_SEALING);
Branch: 1 branch
BranchTrueFalseTotal
int fd = memfd_create(name ? name : "intervaltree", MFD_CLOEXEC | MFD_ALLOW_SEALING); 1 0 1
783 1 ▶ if (fd < 0) { IT_ERR("memfd_create: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fd < 0) { IT_ERR("memfd_create: %s", strerror(errno)); return NULL; } 0 1 1
if (fd < 0) { IT_ERR("memfd_create: %s", strerror(errno)); return NULL; } 0 0 0
784 1 ▶ if (ftruncate(fd, (off_t)total) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (ftruncate(fd, (off_t)total) < 0) { 0 1 1
785 0 ▶ IT_ERR("ftruncate: %s", strerror(errno)); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
IT_ERR("ftruncate: %s", strerror(errno)); close(fd); return NULL; 0 0 0
786 }
787 1 ▶ if (it_reserve(fd, total) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (it_reserve(fd, total) < 0) { 0 1 1
788 0 ▶ IT_ERR("memfd: cannot reserve %llu bytes: %s", (unsigned long long)total, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
IT_ERR("memfd: cannot reserve %llu bytes: %s", (unsigned long long)total, strerror(errno)); 0 0 0
789 0 close(fd); return NULL;
790 }
791 1 (void)fcntl(fd, F_ADD_SEALS, F_SEAL_SHRINK | F_SEAL_GROW);
792 1 void *base = mmap(NULL, (size_t)total, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
793 1 ▶ if (base == MAP_FAILED) { IT_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { IT_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; } 0 1 1
if (base == MAP_FAILED) { IT_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; } 0 0 0
794 1 it_init_header(base, (uint32_t)capacity, total);
795 1 return it_setup(base, (size_t)total, NULL, fd);
796 }
797  
798 2 static ItHandle *it_open_fd(int fd, char *errbuf) {
799 2 ▶ if (errbuf) errbuf[0] = '\0';
Branch: 1 branch
BranchTrueFalseTotal
if (errbuf) errbuf[0] = '\0'; 2 0 2
800 struct stat st;
801 2 ▶ if (fstat(fd, &st) < 0) { IT_ERR("fstat: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fstat(fd, &st) < 0) { IT_ERR("fstat: %s", strerror(errno)); return NULL; } 0 2 2
if (fstat(fd, &st) < 0) { IT_ERR("fstat: %s", strerror(errno)); return NULL; } 0 0 0
802 2 ▶ if ((uint64_t)st.st_size < sizeof(ItHeader)) { IT_ERR("too small"); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if ((uint64_t)st.st_size < sizeof(ItHeader)) { IT_ERR("too small"); return NULL; } 0 2 2
if ((uint64_t)st.st_size < sizeof(ItHeader)) { IT_ERR("too small"); return NULL; } 0 0 0
803 /* before mmap: a creator may truncate the file until it has set magic */
804 uint32_t magic;
805 2 ▶ if (pread(fd, &magic, sizeof magic, offsetof(ItHeader, magic)) != (ssize_t)sizeof magic || magic != IT_MAGIC) {
Branch: 2 branches
BranchTrueFalseTotal
if (pread(fd, &magic, sizeof magic, offsetof(ItHeader, magic)) != (ssize_t)sizeof magic || magic != IT_MAGIC) { 2 0 2
if (pread(fd, &magic, sizeof magic, offsetof(ItHeader, magic)) != (ssize_t)sizeof magic || magic != IT_MAGIC) { 0 2 2
806 0 ▶ IT_ERR("invalid interval tree table"); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
IT_ERR("invalid interval tree table"); return NULL; 0 0 0
807 }
808 2 size_t ms = (size_t)st.st_size;
809 2 void *base = mmap(NULL, ms, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
810 2 ▶ if (base == MAP_FAILED) { IT_ERR("mmap: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { IT_ERR("mmap: %s", strerror(errno)); return NULL; } 0 2 2
if (base == MAP_FAILED) { IT_ERR("mmap: %s", strerror(errno)); return NULL; } 0 0 0
811 2 ▶ if (!it_validate_header((ItHeader *)base, (uint64_t)st.st_size)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!it_validate_header((ItHeader *)base, (uint64_t)st.st_size)) { 0 2 2
812 0 ▶ IT_ERR("invalid interval tree table"); munmap(base, ms); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
IT_ERR("invalid interval tree table"); munmap(base, ms); return NULL; 0 0 0
813 }
814 2 ▶ if (__atomic_load_n(&((ItHeader *)base)->sealed, __ATOMIC_ACQUIRE)) {
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&((ItHeader *)base)->sealed, __ATOMIC_ACQUIRE)) { 0 2 2
815 0 ▶ IT_ERR("this interval tree is frozen (read-only); open it with new_readonly");
Branch: 1 branch
BranchTrueFalseTotal
IT_ERR("this interval tree is frozen (read-only); open it with new_readonly"); 0 0 0
816 0 munmap(base, ms); return NULL;
817 }
818 2 int myfd = fcntl(fd, F_DUPFD_CLOEXEC, 0);
819 2 ▶ if (myfd < 0) { IT_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (myfd < 0) { IT_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; } 0 2 2
if (myfd < 0) { IT_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; } 0 0 0
820 2 return it_setup(base, ms, NULL, myfd);
821 }
822  
823 /* Open a FROZEN (sealed) file read-only: O_RDONLY + PROT_READ, no lock ever.
824 * A sealed file is immutable and no read path writes the mapping, so queries
825 * take no reader-slot / rwlock traffic and any number of processes can share
826 * one PROT_READ mapping (same architecture; the magic rejects a wrong-endian
827 * file). */
828 6 static ItHandle *it_open_readonly(const char *path, char *errbuf) {
829 6 ▶ if (errbuf) errbuf[0] = '\0';
Branch: 1 branch
BranchTrueFalseTotal
if (errbuf) errbuf[0] = '\0'; 6 0 6
830 6 int fd = open(path, O_RDONLY|O_NOFOLLOW|O_CLOEXEC);
831 6 ▶ if (fd < 0) { IT_ERR("open %s: %s", path, strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fd < 0) { IT_ERR("open %s: %s", path, strerror(errno)); return NULL; } 1 5 6
if (fd < 0) { IT_ERR("open %s: %s", path, strerror(errno)); return NULL; } 1 0 1
832 struct stat st;
833 5 ▶ if (fstat(fd, &st) < 0) { IT_ERR("fstat %s: %s", path, strerror(errno)); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fstat(fd, &st) < 0) { IT_ERR("fstat %s: %s", path, strerror(errno)); close(fd); return NULL; } 0 5 5
if (fstat(fd, &st) < 0) { IT_ERR("fstat %s: %s", path, strerror(errno)); close(fd); return NULL; } 0 0 0
834 5 ▶ if ((uint64_t)st.st_size < sizeof(ItHeader)) { IT_ERR("%s: file too small", path); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if ((uint64_t)st.st_size < sizeof(ItHeader)) { IT_ERR("%s: file too small", path); close(fd); return NULL; } 0 5 5
if ((uint64_t)st.st_size < sizeof(ItHeader)) { IT_ERR("%s: file too small", path); close(fd); return NULL; } 0 0 0
835 /* before mmap: a creator may truncate the file until it has set magic */
836 uint32_t magic;
837 5 ▶ if (pread(fd, &magic, sizeof magic, offsetof(ItHeader, magic)) != (ssize_t)sizeof magic || magic != IT_MAGIC) {
Branch: 2 branches
BranchTrueFalseTotal
if (pread(fd, &magic, sizeof magic, offsetof(ItHeader, magic)) != (ssize_t)sizeof magic || magic != IT_MAGIC) { 5 0 5
if (pread(fd, &magic, sizeof magic, offsetof(ItHeader, magic)) != (ssize_t)sizeof magic || magic != IT_MAGIC) { 0 5 5
838 0 ▶ IT_ERR("%s: invalid interval tree file", path); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
IT_ERR("%s: invalid interval tree file", path); close(fd); return NULL; 0 0 0
839 }
840 5 size_t ms = (size_t)st.st_size;
841 5 void *base = mmap(NULL, ms, PROT_READ, MAP_SHARED, fd, 0);
842 5 close(fd); /* the mapping keeps the file; a read-only view needs no fd (no msync/ftruncate) */
843 5 ▶ if (base == MAP_FAILED) { IT_ERR("mmap %s: %s", path, strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { IT_ERR("mmap %s: %s", path, strerror(errno)); return NULL; } 0 5 5
if (base == MAP_FAILED) { IT_ERR("mmap %s: %s", path, strerror(errno)); return NULL; } 0 0 0
844 5 ▶ if (!it_validate_header((ItHeader *)base, (uint64_t)st.st_size)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!it_validate_header((ItHeader *)base, (uint64_t)st.st_size)) { 0 5 5
845 0 ▶ IT_ERR("%s: invalid interval tree file", path); munmap(base, ms); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
IT_ERR("%s: invalid interval tree file", path); munmap(base, ms); return NULL; 0 0 0
846 }
847 5 ▶ if (!__atomic_load_n(&((ItHeader *)base)->sealed, __ATOMIC_ACQUIRE)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!__atomic_load_n(&((ItHeader *)base)->sealed, __ATOMIC_ACQUIRE)) { 1 4 5
848 1 ▶ IT_ERR("%s is not frozen: call ->freeze on the producer before opening read-only", path);
Branch: 1 branch
BranchTrueFalseTotal
IT_ERR("%s is not frozen: call ->freeze on the producer before opening read-only", path); 1 0 1
849 1 munmap(base, ms); return NULL;
850 }
851 4 ItHandle *h = it_setup(base, ms, path, -1); /* munmaps on OOM */
852 4 ▶ if (!h) { IT_ERR("out of memory"); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (!h) { IT_ERR("out of memory"); return NULL; } 0 4 4
if (!h) { IT_ERR("out of memory"); return NULL; } 0 0 0
853 4 h->readonly = 1;
854 4 return h;
855 }
856  
857 33 static void it_destroy(ItHandle *h) {
858 33 ▶ if (!h) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!h) return; 0 33 33
859 /* Release our reader slot on clean teardown (else short-lived-reader churn
860 * exhausts the slot table); skip if a read lock is still held (rdepth>0). */
861 33 ▶ 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 && 33 0 33
if (h->reader_slots && h->my_slot_idx != UINT32_MAX && h->cached_pid && 27 6 33
if (h->reader_slots && h->my_slot_idx != UINT32_MAX && h->cached_pid && 27 0 27
862 27 ▶ h->cached_fork_gen == __atomic_load_n(&it_fork_gen, __ATOMIC_RELAXED) &&
Branch: 1 branch
BranchTrueFalseTotal
h->cached_fork_gen == __atomic_load_n(&it_fork_gen, __ATOMIC_RELAXED) && 27 0 27
863 27 ▶ __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) { 27 0 27
864 /* Clear our occ bit BEFORE freeing the slot: we still own the pid so no
865 * claimant can take the slot mid-clear, and rdepth==0 so no writer needs
866 * to see us. (A crash skips this -> the bit is reclaimed lazily by a
867 * writer scan / re-claim, same as the pid.) */
868 27 it_occ_clear(h, h->my_slot_idx);
869 27 uint32_t expected = h->cached_pid;
870 27 __atomic_compare_exchange_n(&h->reader_slots[h->my_slot_idx].pid,
871 &expected, 0, 0, __ATOMIC_RELEASE, __ATOMIC_RELAXED);
872 }
873 33 ▶ if (h->backing_fd >= 0) close(h->backing_fd);
Branch: 1 branch
BranchTrueFalseTotal
if (h->backing_fd >= 0) close(h->backing_fd); 3 30 33
874 33 ▶ if (h->base) munmap(h->base, h->mmap_size);
Branch: 1 branch
BranchTrueFalseTotal
if (h->base) munmap(h->base, h->mmap_size); 33 0 33
875 33 free(h->path);
876 33 free(h);
877 }
878  
879 5 static inline int it_msync(ItHandle *h) {
880 5 ▶ if (!h || !h->base) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (!h || !h->base) return 0; 5 0 5
if (!h || !h->base) return 0; 0 5 5
881 5 return msync(h->base, h->mmap_size, MS_SYNC);
882 }
883  
884 /* forward decl: it_freeze (below) must force a pending build to completion
885 * before sealing; it_build_locked itself is defined further down, alongside
886 * the rest of the tree operations. */
887 static void it_build_locked(ItHandle *h);
888  
889 /* Seal a tree: make it permanently immutable so it can be shipped and opened
890 * read-only. Takes the write lock and, if a build is pending (dirty), force-
891 * completes it right there -- a sealed tree must NEVER be left dirty, because
892 * the read-only query path (it_open_readonly handles) takes no lock and never
893 * builds; publishing the seal is what makes that lock-free path safe. Then
894 * flushes it (file/memfd-backed). Afterwards every mutator croaks and a
895 * read-write reopen is refused. */
896 3 static int it_freeze(ItHandle *h) {
897 3 it_rwlock_wrlock(h);
898 3 ▶ if (h->hdr->dirty) it_build_locked(h);
Branch: 1 branch
BranchTrueFalseTotal
if (h->hdr->dirty) it_build_locked(h); 2 1 3
899 3 __atomic_store_n(&h->hdr->sealed, 1, __ATOMIC_RELEASE);
900 3 it_rwlock_wrunlock(h);
901 3 ▶ if (h->path || h->backing_fd >= 0) return it_msync(h);
Branch: 2 branches
BranchTrueFalseTotal
if (h->path || h->backing_fd >= 0) return it_msync(h); 0 3 3
if (h->path || h->backing_fd >= 0) return it_msync(h); 0 0 0
902 0 return 0; /* anonymous: the seal lives in shared memory (visible to forks); nothing to flush */
903 }
904  
905 /* ================================================================
906 * Interval-tree operations (callers hold the lock)
907 *
908 * Intervals are appended O(1) and marked dirty; a balanced BST keyed by the low
909 * endpoint is bulk-built on the first query after any insert (sorted once by lo,
910 * then median-split), so query recursion is O(log n) deep whatever the insertion
911 * order. Each node carries max_hi = the maximum hi endpoint over its whole
912 * subtree, so a query can prune a subtree whose intervals all end before it.
913 * Every child index read from shared memory is bounds-checked.
914 * ================================================================ */
915  
916 /* one snapshotted matching interval, for a query result */
917 typedef struct { uint64_t id; int64_t lo, hi; } ItRes;
918  
919 /* append an interval [lo,hi] with a payload id; returns its slot, or -1 if the
920 * tree is full. Marks the tree dirty so the next query rebuilds. (caller holds wrlock) */
921 1941 static int64_t it_add_locked(ItHandle *h, int64_t lo, int64_t hi, uint64_t payload) {
922 1941 uint64_t slot = h->hdr->count;
923 1941 ▶ if (slot >= h->capacity) return -1; /* full */
Branch: 1 branch
BranchTrueFalseTotal
if (slot >= h->capacity) return -1; /* full */ 1 1940 1941
924 1940 ItNode *nd = it_node(h, slot);
925 1940 nd->lo = lo; nd->hi = hi; nd->max_hi = hi; nd->payload = payload;
926 1940 nd->left = IT_NIL; nd->right = IT_NIL;
927 /* Dirty before the count: a kill between costs a rebuild, never a counted node outside the tree. */
928 1940 h->hdr->dirty = 1;
929 1940 __atomic_thread_fence(__ATOMIC_RELEASE);
930 1940 h->hdr->count = slot + 1;
931 1940 return (int64_t)slot;
932 }
933  
934 /* ---- balanced bulk build (sort once by lo, median split, augment max_hi) ---- */
935 16416 static int it_cmp_lo(const void *pa, const void *pb, void *arg) {
936 16416 ItHandle *h = (ItHandle *)arg;
937 16416 uint32_t a = *(const uint32_t *)pa, b = *(const uint32_t *)pb;
938 16416 int64_t la = it_node(h, a)->lo, lb = it_node(h, b)->lo;
939 16416 ▶ if (la < lb) return -1;
Branch: 1 branch
BranchTrueFalseTotal
if (la < lb) return -1; 8068 8348 16416
940 8348 ▶ if (la > lb) return 1;
Branch: 1 branch
BranchTrueFalseTotal
if (la > lb) return 1; 8216 132 8348
941 132 ▶ return (a < b) ? -1 : (a > b ? 1 : 0); /* stable tiebreak */
Branch: 1 branch
BranchTrueFalseTotal
return (a < b) ? -1 : (a > b ? 1 : 0); /* stable tiebreak */ 0 132 132
942 }
943  
944 /* build a balanced subtree over the already-lo-sorted idx[lo..hi]; returns the
945 * subtree root and sets its max_hi from its own hi and its children's max_hi. */
946 3889 static uint32_t it_build_rec(ItHandle *h, uint32_t *idx, int64_t lo, int64_t hi) {
947 3889 ▶ if (lo > hi) return IT_NIL;
Branch: 1 branch
BranchTrueFalseTotal
if (lo > hi) return IT_NIL; 1954 1935 3889
948 1935 int64_t mid = lo + (hi - lo) / 2;
949 1935 uint32_t node = idx[mid];
950 1935 uint32_t l = it_build_rec(h, idx, lo, mid - 1);
951 1935 uint32_t r = it_build_rec(h, idx, mid + 1, hi);
952 1935 ItNode *nd = it_node(h, node);
953 1935 nd->left = l; nd->right = r;
954 1935 int64_t mx = nd->hi;
955 1935 ▶ if (l != IT_NIL && it_node(h, l)->max_hi > mx) mx = it_node(h, l)->max_hi;
Branch: 2 branches
BranchTrueFalseTotal
if (l != IT_NIL && it_node(h, l)->max_hi > mx) mx = it_node(h, l)->max_hi; 680 1255 1935
if (l != IT_NIL && it_node(h, l)->max_hi > mx) mx = it_node(h, l)->max_hi; 471 209 680
956 1935 ▶ if (r != IT_NIL && it_node(h, r)->max_hi > mx) mx = it_node(h, r)->max_hi;
Branch: 2 branches
BranchTrueFalseTotal
if (r != IT_NIL && it_node(h, r)->max_hi > mx) mx = it_node(h, r)->max_hi; 1236 699 1935
if (r != IT_NIL && it_node(h, r)->max_hi > mx) mx = it_node(h, r)->max_hi; 750 486 1236
957 1935 nd->max_hi = mx;
958 1935 return node;
959 }
960  
961 /* (re)build a balanced tree over all inserted intervals (caller holds wrlock) */
962 19 static void it_build_locked(ItHandle *h) {
963 19 uint64_t n = h->hdr->count;
964 19 ▶ if (n > h->capacity) n = h->capacity; /* Layer B */
Branch: 1 branch
BranchTrueFalseTotal
if (n > h->capacity) n = h->capacity; /* Layer B */ 0 19 19
965 19 ▶ if (n == 0) { h->hdr->root = IT_NIL; __atomic_thread_fence(__ATOMIC_RELEASE); h->hdr->dirty = 0; return; }
Branch: 1 branch
BranchTrueFalseTotal
if (n == 0) { h->hdr->root = IT_NIL; __atomic_thread_fence(__ATOMIC_RELEASE); h->hdr->dirty = 0; return; } 0 19 19
966 19 uint32_t *idx = it_idx(h); /* scratch region inside the mapping */
967 1954 ▶ for (uint64_t i = 0; i < n; i++) idx[i] = (uint32_t)i;
Branch: 1 branch
BranchTrueFalseTotal
for (uint64_t i = 0; i < n; i++) idx[i] = (uint32_t)i; 1935 19 1954
968 19 qsort_r(idx, (size_t)n, sizeof(uint32_t), it_cmp_lo, h); /* sort by lo once (subranges stay sorted) */
969 19 h->hdr->root = it_build_rec(h, idx, 0, (int64_t)n - 1);
970 19 __atomic_thread_fence(__ATOMIC_RELEASE);
971 19 h->hdr->dirty = 0;
972 }
973  
974 /* ---- overlap query: collect intervals [lo,hi] intersecting [ql,qh] (a point
975 * stab is ql==qh). Overlap iff lo <= qh && hi >= ql. ---- */
976 29164 static void it_overlaps_rec(ItHandle *h, uint32_t node, int64_t ql, int64_t qh, uint32_t depth,
977 ItRes *out, uint64_t *cnt, uint64_t cap, uint64_t *budget) {
978 29164 ▶ if (!IT_NODE_OK(h, node) || depth > IT_MAX_DEPTH) return; /* Layer B: bounds + recursion depth */
Branch: 3 branches
BranchTrueFalseTotal
if (!IT_NODE_OK(h, node) || depth > IT_MAX_DEPTH) return; /* Layer B: bounds + recursion depth */ 17358 11806 29164
if (!IT_NODE_OK(h, node) || depth > IT_MAX_DEPTH) return; /* Layer B: bounds + recursion depth */ 17358 0 17358
if (!IT_NODE_OK(h, node) || depth > IT_MAX_DEPTH) return; /* Layer B: bounds + recursion depth */ 0 17358 17358
979 17358 ▶ if (*budget == 0) return; /* runaway guard: a corrupt tree (cycle/diamond of valid indices)
Branch: 1 branch
BranchTrueFalseTotal
if (*budget == 0) return; /* runaway guard: a corrupt tree (cycle/diamond of valid indices) 0 17358 17358
980 * can revisit a node exponentially; the depth cap bounds stack
981 * depth but not total work. A valid tree makes <= 2n+1 calls, so
982 * this budget never trips on legitimate data. */
983 17358 (*budget)--;
984 17358 ItNode *nd = it_node(h, node);
985 17358 ▶ if (nd->max_hi < ql) return; /* whole subtree ends before ql -> prune */
Branch: 1 branch
BranchTrueFalseTotal
if (nd->max_hi < ql) return; /* whole subtree ends before ql -> prune */ 2378 14980 17358
986 14980 it_overlaps_rec(h, nd->left, ql, qh, depth + 1, out, cnt, cap, budget); /* left subtree may overlap */
987 14980 ▶ if (nd->lo <= qh && nd->hi >= ql && *cnt < cap) { /* this interval overlaps [ql,qh] */
Branch: 3 branches
BranchTrueFalseTotal
if (nd->lo <= qh && nd->hi >= ql && *cnt < cap) { /* this interval overlaps [ql,qh] */ 13937 1043 14980
if (nd->lo <= qh && nd->hi >= ql && *cnt < cap) { /* this interval overlaps [ql,qh] */ 10993 2944 13937
if (nd->lo <= qh && nd->hi >= ql && *cnt < cap) { /* this interval overlaps [ql,qh] */ 10993 0 10993
988 10993 out[*cnt].id = nd->payload; out[*cnt].lo = nd->lo; out[*cnt].hi = nd->hi; (*cnt)++;
989 }
990 14980 ▶ if (nd->lo <= qh) /* right lo's >= node.lo; skip if node.lo > qh */
Branch: 1 branch
BranchTrueFalseTotal
if (nd->lo <= qh) /* right lo's >= node.lo; skip if node.lo > qh */ 13937 1043 14980
991 13937 it_overlaps_rec(h, nd->right, ql, qh, depth + 1, out, cnt, cap, budget);
992 }
993  
994 247 static uint64_t it_overlaps_locked(ItHandle *h, int64_t ql, int64_t qh, ItRes *out, uint64_t cap) {
995 247 uint64_t cnt = 0;
996 247 uint64_t budget = 2 * (uint64_t)h->capacity + 1; /* valid tree visits each node once (<=2n+1 calls) */
997 247 it_overlaps_rec(h, h->hdr->root, ql, qh, 0, out, &cnt, cap, &budget);
998 247 return cnt;
999 }
1000  
1001 /* reset to an empty tree (caller holds the write lock) */
1002 2 static inline void it_clear_locked(ItHandle *h) {
1003 /* Dirty first: a kill at any point then reads as not cleared (rebuilt) or cleared. */
1004 2 h->hdr->dirty = 1;
1005 2 __atomic_thread_fence(__ATOMIC_RELEASE);
1006 2 h->hdr->count = 0;
1007 2 h->hdr->root = IT_NIL;
1008 2 __atomic_thread_fence(__ATOMIC_RELEASE);
1009 2 h->hdr->dirty = 0;
1010 2 }
1011  
1012 #endif /* IT_H */
« blib/lib/Data/IntervalTree/Shared.pm ↑ Summary Shared.xs »