radix.h

filter: Statementstmt 73.5% 489 / 665 Branchbran 48.7% 271 / 556 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 62.2% 760 / 1221 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« blib/lib/Data/RadixTree/Shared.pm ↑ Summary Shared.xs »
1 /*
2 * radix.h -- Shared-memory compressed radix tree (PATRICIA-style trie) for Linux
3 *
4 * Maps arbitrary byte-string keys to uint64 values. A radix-256 trie with
5 * path/edge compression: each node carries a label (a run of bytes shared by
6 * the whole subtree) so chains of single-child nodes collapse into one edge.
7 * Insert and lookup are O(key length). Beyond exact lookup the tree answers
8 * longest-prefix queries -- the longest stored key that is a prefix of a query
9 * string -- which is what routing tables want. The node pool and label arena
10 * live in a shared mapping so several processes share one tree; a
11 * write-preferring futex rwlock with reader-slot dead-process recovery guards
12 * mutation.
13 *
14 * lookup / exists / longest_prefix are pure reads (no path compression) and run
15 * under the READ lock; insert / delete / clear take the WRITE lock.
16 *
17 * delete is LAZY in v1: it unmarks the key's value but does not free node-pool
18 * or arena space. Size the capacities for the working set, or clear() to reset.
19 *
20 * Layout: Header -> reader_slots[1024] -> occ_bitmap -> node_pool[node_cap] -> label_arena[arena_cap]
21 */
22  
23 #ifndef RADIX_H
24 #define RADIX_H
25  
26 #include <stddef.h>
27 #include <stdint.h>
28 #include <stdlib.h>
29 #include <string.h>
30 #include <unistd.h>
31 #include <fcntl.h>
32 #include <errno.h>
33 #include <time.h>
34 #include <limits.h>
35 #include <signal.h>
36 #include <stdio.h>
37 #include <sys/mman.h>
38 #include <sys/stat.h>
39 #include <sys/file.h>
40 #include <sys/syscall.h>
41 #include <linux/futex.h>
42 #include <pthread.h>
43  
44 #if defined(__BYTE_ORDER__) && __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
45 #error "radix.h: requires little-endian architecture"
46 #endif
47  
48  
49 /* ================================================================
50 * Constants
51 * ================================================================ */
52  
53 #define RDX_MAGIC 0x58444152U /* "RADX" (little-endian) */
54 #define RDX_VERSION 2 /* 2: added the occupancy bitmap region (layout change) */
55 #define RDX_ERR_BUFLEN (PATH_MAX + 256)
56 #ifndef RDX_READER_SLOTS
57 #define RDX_READER_SLOTS 1024 /* max concurrent reader processes for dead-process recovery */
58 #endif
59 /* Occupancy bitmap: one bit per reader slot, set when a process claims a slot and
60 * cleared on clean release. A writer scans these RDX_OCC_WORDS words to visit
61 * only OCCUPIED slots (O(words + live readers)) instead of all RDX_READER_SLOTS. */
62 #define RDX_OCC_WORDS (((RDX_READER_SLOTS) + 63) / 64) /* 16 for 1024 slots */
63 #define RDX_OCC_BYTES ((uint64_t)RDX_OCC_WORDS * 8) /* 128 bytes */
64 #define RDX_MAX_NODES (1u << 24) /* 16.7M nodes: node index 0 is the reserved NIL sentinel */
65 #define RDX_MAX_ARENA 0xF0000000u /* ~3.75 GiB label arena; offsets/lengths are uint32 */
66  
67 #define RDX_ERR(fmt, ...) do { if (errbuf) snprintf(errbuf, RDX_ERR_BUFLEN, fmt, ##__VA_ARGS__); } while (0)
68  
69 /* ================================================================
70 * Structs
71 * ================================================================ */
72  
73 /* Radix-tree node (fixed size). children[b] == 0 means "no child on byte b",
74 * so node index 0 is the reserved NIL sentinel and is never a real node. The
75 * label (children-shared prefix of this edge) lives in the arena at
76 * [label_off, label_off+label_len). */
77 typedef struct {
78 uint32_t children[256]; /* child node index per next byte; 0 == none */
79 uint32_t label_off; /* offset of this edge's label in the arena */
80 uint32_t label_len; /* length of the label in bytes */
81 uint64_t value; /* stored value (valid only when has_value) */
82 uint8_t has_value; /* 1 if a key ends exactly at this node */
83 uint8_t _pad[7]; /* pad to 8-byte alignment (1048 bytes total) */
84 } RdxNode;
85  
86 _Static_assert(sizeof(RdxNode) == 256u * 4u + 4u + 4u + 8u + 8u, "RdxNode layout");
87 _Static_assert(sizeof(RdxNode) % 8 == 0, "RdxNode must be 8-byte aligned");
88  
89 /* Per-process slot for dead-process recovery. In the reader-slots-only rwlock a
90 * reader's ENTIRE contribution to the shared lock is `rdepth` in its OWN slot --
91 * there is no separate shared reader counter to fall out of sync with it -- so a
92 * dead reader's contribution is exactly this one word, which a draining writer
93 * neutralises by clearing the slot's pid (the scan then ignores the slot). No
94 * orphaned counter can exist, so there is no quiescent force-reset and sustained
95 * readers cannot starve a writer. _rsv1/_rsv2 are kept only to preserve the
96 * 16-byte slot size across the already-released builds. */
97 typedef struct {
98 uint32_t pid; /* 0 = unclaimed */
99 uint32_t rdepth; /* read-locks THIS process currently holds (recursion-safe) */
100 uint32_t _rsv1; /* reserved (was waiters_parked); unused, kept for layout size */
101 uint32_t _rsv2; /* reserved (was writers_parked); unused, kept for layout size */
102 } RdxReaderSlot;
103  
104 struct RdxHeader {
105 uint32_t magic, version; /* 0,4 */
106 uint32_t node_cap; /* 8 node-pool capacity (slots, incl. NIL) */
107 uint32_t node_used; /* 12 high-water of ever-allocated nodes (incl. NIL+root) */
108 uint32_t root; /* 16 root node index (allocated at create) */
109 uint32_t arena_cap; /* 20 label-arena capacity in bytes */
110 uint32_t arena_used; /* 24 bytes used in the arena */
111 uint32_t free_head; /* 28 head of the free-node list, 0 == empty (node 0 is
112 * NIL so it can never be on the list). Reuses the
113 * slot this field originally had, so the on-disk
114 * format is unchanged: existing files carry 0 here,
115 * which reads correctly as "no free nodes". */
116 uint64_t keys; /* 32 count of stored keys */
117 uint64_t total_size; /* 40 */
118 uint64_t reader_slots_off; /* 48 */
119 uint64_t node_pool_off; /* 56 */
120 uint64_t arena_off; /* 64 */
121 uint32_t wlock; /* 72 WRITER word ONLY: 0 (free) or WRITER_BIT|pid. NOT a reader count. */
122 uint32_t rwait; /* 76 parked-waiter hint (readers+writers blocked on wlock); over-count-safe */
123 uint32_t drain_seq; /* 80 futex bumped by a reader releasing under a draining writer (wakes it) */
124 uint32_t slotless_rdepth; /* readers holding with no reader-slot (documented residual) */
125 uint64_t stat_ops; /* 88 */
126 uint8_t sealed; /* 96 0 = mutable, 1 = frozen (read-only; lock-free reads) */
127 uint8_t _pad0[7];
128 uint64_t pending_keys; /* mutation journal in formerly reserved bytes */
129 uint64_t pending_off;
130 uint32_t pending_value;
131 uint8_t pending_kind;
132 uint8_t _pad[131];
133 };
134 typedef struct RdxHeader RdxHeader;
135  
136 _Static_assert(sizeof(RdxHeader) == 256, "RdxHeader must be 256 bytes");
137  
138 /* ---- Process-local handle ---- */
139  
140 typedef struct RdxHandle {
141 RdxHeader *hdr;
142 RdxReaderSlot *reader_slots; /* RDX_READER_SLOTS entries */
143 uint64_t *occ; /* RDX_OCC_WORDS-word slot-occupancy bitmap (trusted layout offset) */
144 void *base; /* mmap base */
145 /* Fixed geometry cached at attach from validated header. These bound every
146 * node-pool / arena access so a lock-violating peer that later corrupts the
147 * peer-writable header (node_cap/arena_cap/node_pool_off/arena_off) cannot
148 * turn a live index or offset into an out-of-bounds reference. */
149 uint32_t node_cap; /* node-pool capacity (array size, incl. NIL) */
150 uint32_t arena_cap; /* label-arena capacity in bytes */
151 uint64_t node_pool_off; /* node-pool offset from trusted layout */
152 uint64_t arena_off; /* arena offset from trusted layout */
153 size_t mmap_size;
154 char *path; /* backing file path (strdup'd) */
155 char *unlink_path; /* absolute path for relative backing files */
156 int backing_fd; /* memfd or reopened-fd to close on destroy, -1 for file/anon */
157 uint32_t my_slot_idx; /* UINT32_MAX if all slots taken (no recovery for this handle) */
158 uint32_t cached_pid; /* getpid() cached at last slot claim */
159 uint32_t cached_fork_gen; /* rdx_fork_gen value at last slot claim */
160 uint32_t slotless_held; /* read-locks this process holds with no reader-slot */
161 int readonly; /* 1 = frozen O_RDONLY/PROT_READ view: lock-free reads, mutation croaks */
162 } RdxHandle;
163  
164 /* ================================================================
165 * Futex-based write-preferring read-write lock (reader-slots-only)
166 * with dead-process recovery
167 *
168 * The reader count is NOT stored in a shared counter. It is DISTRIBUTED across
169 * per-process reader slots: each slot's `rdepth` is that process's entire
170 * contribution to the lock. A reader publishes its presence in its own slot and
171 * then re-checks the writer word; a writer publishes the writer word and then
172 * scans every slot until all live readers' rdepth reach 0. Sequentially-
173 * consistent store+load on each side (a Dekker handshake) gives mutual exclusion.
174 *
175 * Because a reader's whole contribution is ONE atomic word owned by ONE process,
176 * a crashed reader is recovered by clearing that one slot (CAS its pid to 0) --
177 * there is no second counter to strand, no orphaned +1, and therefore no
178 * quiescent force-reset. A reader killed anywhere in rdlock/rdunlock leaves at
179 * most `rdepth>0` in its dead slot, which the draining writer clears directly, so
180 * sustained read traffic can never starve a writer. Write-preference is inherent
181 * in the gate (new readers see wlock!=0 and yield), so there is no reader-count
182 * yield hack.
183 * ================================================================ */
184  
185 #define RDX_RWLOCK_SPIN_LIMIT 32
186 #define RDX_LOCK_TIMEOUT_SEC 2 /* FUTEX_WAIT timeout for stale-lock detection / drain re-scan */
187  
188 0 static inline void rdx_rwlock_spin_pause(void) {
189 #if defined(__x86_64__) || defined(__i386__)
190 0 __asm__ volatile("pause" ::: "memory");
191 #elif defined(__aarch64__)
192 __asm__ volatile("yield" ::: "memory");
193 #else
194 __asm__ volatile("" ::: "memory");
195 #endif
196 0 }
197  
198 /* Writer word encoding: WRITER_BIT|pid when write-locked, 0 when free. */
199 #define RDX_RWLOCK_WRITER_BIT 0x80000000U
200 #define RDX_RWLOCK_PID_MASK 0x7FFFFFFFU
201 #define RDX_RWLOCK_WR(pid) (RDX_RWLOCK_WRITER_BIT | ((uint32_t)(pid) & RDX_RWLOCK_PID_MASK))
202  
203 /* A zombie (dead but not yet reaped) still answers kill(pid,0) as alive, so a
204 * process that crashed while holding the lock and lingers unreaped would never
205 * be recovered. Treat /proc/<pid>/stat state 'Z' as dead. Linux-only (as is
206 * this module); if /proc is unreadable we fall back to "alive" (safe: we never
207 * force-recover a possibly-live holder). */
208 0 static inline int rdx_pid_is_zombie(uint32_t pid) {
209 char path[32], buf[256];
210 0 snprintf(path, sizeof(path), "/proc/%u/stat", (unsigned)pid);
211 0 int fd = open(path, O_RDONLY | O_CLOEXEC);
212 0 ▶ if (fd < 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (fd < 0) return 0; 0 0 0
213 0 ssize_t n = read(fd, buf, sizeof(buf) - 1);
214 0 close(fd);
215 0 ▶ if (n <= 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (n <= 0) return 0; 0 0 0
216 0 buf[n] = '\0';
217 /* "pid (comm) state ..."; comm may contain ')', so scan to the last one. */
218 0 char *rp = strrchr(buf, ')');
219 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
220 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
221 }
222 /* 1 if alive or unknown, 0 if definitely dead. Cannot detect PID reuse: a
223 * recycled PID reports "alive" and the slot is not reclaimed until that
224 * process exits. See "Crash Safety" in the POD. */
225 0 static inline int rdx_pid_alive(uint32_t pid) {
226 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
227 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
228 0 return !rdx_pid_is_zombie(pid); /* kill() also succeeds for a zombie -> treat as dead */
229 }
230  
231 /* Force-recover a stale WRITE lock left by a dead writer (held or mid-drain).
232 * CAS to OUR pid to hold the lock while fixing shared state, then release.
233 * Using our pid (not a bare WRITER_BIT sentinel) means a subsequent recovering
234 * process can detect and re-recover if we crash mid-recovery. */
235 static void rdx_repair_mutation(RdxHandle *h);
236 0 static inline void rdx_recover_stale_lock(RdxHandle *h, uint32_t observed_wlock) {
237 0 RdxHeader *hdr = h->hdr;
238 0 uint32_t mypid = RDX_RWLOCK_WR((uint32_t)getpid());
239 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
240 mypid, 0, __ATOMIC_ACQUIRE, __ATOMIC_RELAXED))
241 0 return;
242 0 rdx_repair_mutation(h);
243 0 __atomic_store_n(&hdr->wlock, 0, __ATOMIC_RELEASE);
244 0 ▶ if (__atomic_load_n(&hdr->rwait, __ATOMIC_RELAXED) > 0)
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&hdr->rwait, __ATOMIC_RELAXED) > 0) 0 0 0
245 0 syscall(SYS_futex, &hdr->wlock, FUTEX_WAKE, INT_MAX, NULL, NULL, 0);
246 }
247  
248 static const struct timespec rdx_lock_timeout = { RDX_LOCK_TIMEOUT_SEC, 0 };
249  
250 /* Process-global fork-generation counter. Incremented in the pthread_atfork
251 * child callback so every open handle detects a fork transition on the next
252 * lock call without paying a getpid() syscall on the hot path. */
253 static uint32_t rdx_fork_gen = 1;
254 static pthread_once_t rdx_atfork_once = PTHREAD_ONCE_INIT;
255 0 static void rdx_on_fork_child(void) {
256 0 __atomic_add_fetch(&rdx_fork_gen, 1, __ATOMIC_RELAXED);
257 0 }
258 5 static void rdx_atfork_init(void) {
259 5 pthread_atfork(NULL, NULL, rdx_on_fork_child);
260 5 }
261  
262 /* Occupancy bitmap: set a slot's bit when it is claimed, clear it on clean
263 * release. SEQ_CST so a set bit is ordered before the slot's rdepth can go
264 * non-zero (bit set in claim, which precedes any rdlock), letting a writer's
265 * SEQ_CST bitmap scan never miss a slot a committed reader holds. */
266 27 static inline void rdx_occ_set(RdxHandle *h, uint32_t s) {
267 27 __atomic_fetch_or(&h->occ[s >> 6], (uint64_t)1 << (s & 63), __ATOMIC_SEQ_CST);
268 27 }
269 27 static inline void rdx_occ_clear(RdxHandle *h, uint32_t s) {
270 27 __atomic_fetch_and(&h->occ[s >> 6], ~((uint64_t)1 << (s & 63)), __ATOMIC_SEQ_CST);
271 27 }
272  
273 /* Ensure this process owns a reader slot. Called from the lock helpers so
274 * that fork()'d children pick up their own slot lazily instead of sharing
275 * the parent's. Hot-path is a single relaxed load + compare; only on a
276 * fork-generation mismatch do we touch getpid() and scan slots. */
277 4904 static inline void rdx_claim_reader_slot(RdxHandle *h) {
278 4904 uint32_t cur_gen = __atomic_load_n(&rdx_fork_gen, __ATOMIC_RELAXED);
279 4904 ▶ 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)) 4877 27 4904
if (__builtin_expect(cur_gen == h->cached_fork_gen && h->my_slot_idx != UINT32_MAX, 1)) 4877 0 4877
280 4877 return;
281 /* Cold path -- register the atfork hook once per process, then claim. */
282 27 pthread_once(&rdx_atfork_once, rdx_atfork_init);
283 /* Re-read after pthread_once: rdx_on_fork_child may have bumped it. */
284 27 cur_gen = __atomic_load_n(&rdx_fork_gen, __ATOMIC_RELAXED);
285 27 uint32_t now_pid = (uint32_t)getpid();
286 27 h->cached_pid = now_pid;
287 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
288 27 h->cached_fork_gen = cur_gen;
289 27 h->my_slot_idx = UINT32_MAX;
290 27 uint32_t start = now_pid % RDX_READER_SLOTS;
291 /* Pass 1: take a free slot. */
292 28 ▶ for (uint32_t i = 0; i < RDX_READER_SLOTS; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t i = 0; i < RDX_READER_SLOTS; i++) { 28 0 28
293 28 uint32_t s = (start + i) % RDX_READER_SLOTS;
294 28 uint32_t expected = 0;
295 28 ▶ 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 1 28
296 &expected, now_pid, 0,
297 __ATOMIC_ACQUIRE, __ATOMIC_RELAXED)) {
298 /* Fresh owner holds no read locks yet; clear any stale rdepth left by
299 * a dead predecessor (its contribution is dropped as we take over). */
300 27 __atomic_store_n(&h->reader_slots[s].rdepth, 0, __ATOMIC_RELAXED);
301 27 rdx_occ_set(h, s); /* mark occupied BEFORE any rdlock can bump rdepth */
302 27 h->my_slot_idx = s;
303 27 return;
304 }
305 }
306 /* Pass 2: no free slot -- reclaim one whose owner is dead. Safe to take even
307 * if its rdepth>0: clearing pid drops the dead reader's entire contribution
308 * (a writer scan ignores rdepth when pid==0) and we reset rdepth to 0 as we
309 * claim it. */
310 0 ▶ for (uint32_t i = 0; i < RDX_READER_SLOTS; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t i = 0; i < RDX_READER_SLOTS; i++) { 0 0 0
311 0 uint32_t dpid = __atomic_load_n(&h->reader_slots[i].pid, __ATOMIC_ACQUIRE);
312 0 ▶ if (dpid == 0 || dpid == now_pid || rdx_pid_alive(dpid)) continue;
Branch: 3 branches
BranchTrueFalseTotal
if (dpid == 0 || dpid == now_pid || rdx_pid_alive(dpid)) continue; 0 0 0
if (dpid == 0 || dpid == now_pid || rdx_pid_alive(dpid)) continue; 0 0 0
if (dpid == 0 || dpid == now_pid || rdx_pid_alive(dpid)) continue; 0 0 0
313 0 uint32_t expected = dpid;
314 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
315 __ATOMIC_ACQUIRE, __ATOMIC_RELAXED)) {
316 0 __atomic_store_n(&h->reader_slots[i].rdepth, 0, __ATOMIC_RELAXED);
317 0 rdx_occ_set(h, i);
318 0 h->my_slot_idx = i;
319 0 return;
320 }
321 }
322 /* Table full -- leave my_slot_idx = UINT32_MAX so this handle takes the
323 * slotless path (lock still works; recovery of THIS reader's death is the
324 * documented slotless limitation). */
325 }
326  
327 /* Inspect the writer word after a futex-wait timeout. If a dead writer holds
328 * it, force-recover. Dead READERS need no action here: only a writer that owns
329 * wlock drains readers, and it clears dead readers inline in its own scan. */
330 0 static inline void rdx_recover_after_timeout(RdxHandle *h) {
331 0 uint32_t val = __atomic_load_n(&h->hdr->wlock, __ATOMIC_RELAXED);
332 0 ▶ if (val >= RDX_RWLOCK_WRITER_BIT) {
Branch: 1 branch
BranchTrueFalseTotal
if (val >= RDX_RWLOCK_WRITER_BIT) { 0 0 0
333 0 uint32_t pid = val & RDX_RWLOCK_PID_MASK;
334 0 ▶ if (!rdx_pid_alive(pid))
Branch: 1 branch
BranchTrueFalseTotal
if (!rdx_pid_alive(pid)) 0 0 0
335 0 rdx_recover_stale_lock(h, val);
336 }
337 0 }
338  
339 /* Bump/drop the parked-waiter hint. Both readers (blocked at the gate) and
340 * writers (blocked acquiring wlock) wait on the wlock futex and use this, so
341 * wrunlock/recover know whether a FUTEX_WAKE is worth a syscall. A waiter
342 * SIGKILLed while parked leaves rwait over-counted -> at most a spurious wake
343 * (harmless); it can never under-count, so no wakeup is lost. */
344 0 static inline void rdx_park(RdxHandle *h) {
345 0 __atomic_add_fetch(&h->hdr->rwait, 1, __ATOMIC_RELAXED);
346 0 }
347 0 static inline void rdx_unpark(RdxHandle *h) {
348 0 __atomic_sub_fetch(&h->hdr->rwait, 1, __ATOMIC_RELAXED);
349 0 }
350  
351 /* Publish (inc) / retract (dec) this reader's presence -- its ENTIRE
352 * contribution to the lock. A slotted reader uses its slot's rdepth; a reader
353 * that could not claim a slot uses the global slotless_rdepth. inc() is SEQ_CST
354 * so the wlock re-check that follows it in rdlock forms a Dekker handshake with
355 * the writer's SEQ_CST wlock-store + rdepth-scan. leave() peels slotless first
356 * so a slot claimed mid-hold cannot misattribute the decrement. */
357 3272 static inline void rdx_rdepth_inc(RdxHandle *h) {
358 3272 ▶ if (h->my_slot_idx != UINT32_MAX) {
Branch: 1 branch
BranchTrueFalseTotal
if (h->my_slot_idx != UINT32_MAX) { 3272 0 3272
359 3272 __atomic_add_fetch(&h->reader_slots[h->my_slot_idx].rdepth, 1, __ATOMIC_SEQ_CST);
360 } else {
361 0 __atomic_add_fetch(&h->hdr->slotless_rdepth, 1, __ATOMIC_SEQ_CST);
362 0 h->slotless_held++;
363 }
364 3272 }
365 3272 static inline void rdx_rdepth_dec(RdxHandle *h) {
366 3272 ▶ if (h->slotless_held > 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (h->slotless_held > 0) { 0 3272 3272
367 0 h->slotless_held--;
368 0 __atomic_sub_fetch(&h->hdr->slotless_rdepth, 1, __ATOMIC_RELEASE);
369 3272 ▶ } else if (h->my_slot_idx != UINT32_MAX) {
Branch: 1 branch
BranchTrueFalseTotal
} else if (h->my_slot_idx != UINT32_MAX) { 3272 0 3272
370 3272 __atomic_sub_fetch(&h->reader_slots[h->my_slot_idx].rdepth, 1, __ATOMIC_RELEASE);
371 }
372 3272 }
373  
374 /* Wake a writer that may be draining readers (it waits on drain_seq). Called
375 * after every rdepth decrement so a released read lock lets the writer re-scan
376 * promptly instead of waiting out its timeout. */
377 3272 static inline void rdx_reader_wake_drain(RdxHandle *h) {
378 3272 ▶ if (__atomic_load_n(&h->hdr->wlock, __ATOMIC_ACQUIRE) != 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&h->hdr->wlock, __ATOMIC_ACQUIRE) != 0) { 0 3272 3272
379 0 __atomic_add_fetch(&h->hdr->drain_seq, 1, __ATOMIC_RELEASE);
380 0 syscall(SYS_futex, &h->hdr->drain_seq, FUTEX_WAKE, 1, NULL, NULL, 0);
381 }
382 3272 }
383  
384 3272 static inline void rdx_rwlock_rdlock(RdxHandle *h) {
385 3272 rdx_claim_reader_slot(h);
386 3272 RdxHeader *hdr = h->hdr;
387 3272 for (int spin = 0; ; spin++) {
388 3272 uint32_t cur = __atomic_load_n(&hdr->wlock, __ATOMIC_ACQUIRE);
389 3272 ▶ if (cur == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (cur == 0) { 3272 0 3272
390 /* Optimistically take the read: publish rdepth, then re-check wlock.
391 * SEQ_CST inc + SEQ_CST load vs the writer's SEQ_CST wlock CAS +
392 * SEQ_CST rdepth scan: by the single total order of SEQ_CST ops the
393 * two sides cannot both miss each other, so we never hold
394 * concurrently with a writer. */
395 3272 rdx_rdepth_inc(h);
396 3272 ▶ if (__atomic_load_n(&hdr->wlock, __ATOMIC_SEQ_CST) == 0)
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&hdr->wlock, __ATOMIC_SEQ_CST) == 0) 3272 0 3272
397 3272 return; /* no writer after our publish -> we hold the read lock */
398 /* A writer appeared during our publish -- yield to it (write-preferring). */
399 0 rdx_rdepth_dec(h);
400 0 rdx_reader_wake_drain(h); /* let the draining writer see rdepth drop */
401 0 spin = 0;
402 0 continue;
403 }
404 /* wlock != 0: a writer holds or is acquiring. Recover if it is dead. */
405 0 if (cur >= RDX_RWLOCK_WRITER_BIT &&
406 0 !rdx_pid_alive(cur & RDX_RWLOCK_PID_MASK)) {
407 0 rdx_recover_stale_lock(h, cur);
408 0 spin = 0;
409 0 continue;
410 }
411 0 ▶ if (__builtin_expect(spin < RDX_RWLOCK_SPIN_LIMIT, 1)) {
Branch: 1 branch
BranchTrueFalseTotal
if (__builtin_expect(spin < RDX_RWLOCK_SPIN_LIMIT, 1)) { 0 0 0
412 0 rdx_rwlock_spin_pause();
413 0 continue;
414 }
415 0 rdx_park(h);
416 0 cur = __atomic_load_n(&hdr->wlock, __ATOMIC_RELAXED);
417 0 ▶ if (cur != 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (cur != 0) { 0 0 0
418 0 long rc = syscall(SYS_futex, &hdr->wlock, FUTEX_WAIT, cur,
419 &rdx_lock_timeout, NULL, 0);
420 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
421 0 rdx_unpark(h);
422 0 rdx_recover_after_timeout(h);
423 0 spin = 0;
424 0 continue;
425 }
426 }
427 0 rdx_unpark(h);
428 0 spin = 0;
429 }
430 }
431  
432 3272 static inline void rdx_rwlock_rdunlock(RdxHandle *h) {
433 3272 rdx_rdepth_dec(h); /* RELEASE: drop our entire contribution */
434 3272 rdx_reader_wake_drain(h); /* if a writer is draining, wake it to re-scan */
435 3272 }
436  
437 1632 static inline void rdx_rwlock_wrlock(RdxHandle *h) {
438 1632 rdx_claim_reader_slot(h); /* refresh cached_pid across fork */
439 1632 RdxHeader *hdr = h->hdr;
440 /* Encode PID in the wlock word itself (0x80000000 | pid) to eliminate any
441 * crash window between acquiring the lock and storing the owner. */
442 1632 uint32_t mypid = RDX_RWLOCK_WR(h->cached_pid);
443 /* Phase 1: acquire the writer word (mutual exclusion among writers). */
444 1632 for (int spin = 0; ; spin++) {
445 1632 uint32_t expected = 0;
446 1632 ▶ if (__atomic_compare_exchange_n(&hdr->wlock, &expected, mypid,
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_compare_exchange_n(&hdr->wlock, &expected, mypid, 1632 0 1632
447 0, __ATOMIC_SEQ_CST, __ATOMIC_RELAXED))
448 1632 break;
449 /* Contended: expected now holds the current wlock value. */
450 0 if (expected >= RDX_RWLOCK_WRITER_BIT &&
451 0 !rdx_pid_alive(expected & RDX_RWLOCK_PID_MASK)) {
452 0 rdx_recover_stale_lock(h, expected);
453 0 spin = 0;
454 0 continue;
455 }
456 0 ▶ if (__builtin_expect(spin < RDX_RWLOCK_SPIN_LIMIT, 1)) {
Branch: 1 branch
BranchTrueFalseTotal
if (__builtin_expect(spin < RDX_RWLOCK_SPIN_LIMIT, 1)) { 0 0 0
457 0 rdx_rwlock_spin_pause();
458 0 continue;
459 }
460 0 rdx_park(h);
461 0 uint32_t cur = __atomic_load_n(&hdr->wlock, __ATOMIC_RELAXED);
462 0 ▶ if (cur != 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (cur != 0) { 0 0 0
463 0 long rc = syscall(SYS_futex, &hdr->wlock, FUTEX_WAIT, cur,
464 &rdx_lock_timeout, NULL, 0);
465 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
466 0 rdx_unpark(h);
467 0 rdx_recover_after_timeout(h);
468 0 spin = 0;
469 0 continue;
470 }
471 }
472 0 rdx_unpark(h);
473 0 spin = 0;
474 }
475 /* Phase 2: we own wlock, so no NEW reader can join (they see wlock!=0 and
476 * yield). Drain the readers that were already holding when we won the CAS.
477 * The SEQ_CST CAS above + the SEQ_CST rdepth loads below are the writer side
478 * of the Dekker handshake. */
479 0 for (;;) {
480 1632 uint32_t v = __atomic_load_n(&hdr->drain_seq, __ATOMIC_ACQUIRE); /* snapshot BEFORE scan */
481 1632 int busy = 0;
482 /* Visit only OCCUPIED slots via the occupancy bitmap (SEQ_CST: a committed
483 * reader's bit -- set in claim, before its rdepth++ -- is ordered before
484 * this scan, so no held slot is skipped). O(RDX_OCC_WORDS + live readers)
485 * instead of O(RDX_READER_SLOTS). */
486 27744 ▶ for (uint32_t w = 0; w < RDX_OCC_WORDS; w++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t w = 0; w < RDX_OCC_WORDS; w++) { 26112 1632 27744
487 26112 uint64_t word = __atomic_load_n(&h->occ[w], __ATOMIC_SEQ_CST);
488 27745 ▶ while (word) {
Branch: 1 branch
BranchTrueFalseTotal
while (word) { 1633 26112 27745
489 1633 uint32_t i = (w << 6) + (uint32_t)__builtin_ctzll(word);
490 1633 word &= word - 1; /* consume this bit (local copy) */
491 1633 uint32_t rd = __atomic_load_n(&h->reader_slots[i].rdepth, __ATOMIC_SEQ_CST);
492 1633 ▶ if (rd == 0) continue; /* occupied but not read-locking now */
Branch: 1 branch
BranchTrueFalseTotal
if (rd == 0) continue; /* occupied but not read-locking now */ 1633 0 1633
493 0 uint32_t pid = __atomic_load_n(&h->reader_slots[i].pid, __ATOMIC_ACQUIRE);
494 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
495 0 ▶ if (!rdx_pid_alive(pid)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!rdx_pid_alive(pid)) { 0 0 0
496 /* Dead reader: drop its pid so the slot no longer counts. Leave
497 * the occ bit set (harmless -- a later scan hits pid==0 and skips,
498 * a re-claim re-sets it) to avoid racing a concurrent claimant. */
499 0 uint32_t ep = pid;
500 0 __atomic_compare_exchange_n(&h->reader_slots[i].pid, &ep, 0,
501 0, __ATOMIC_ACQ_REL, __ATOMIC_RELAXED);
502 0 continue;
503 }
504 0 busy = 1; /* live reader still holding */
505 }
506 }
507 /* A live slotless reader keeps us waiting; a crashed slotless reader that
508 * cannot be attributed to a pid is the documented slotless limitation. */
509 1632 ▶ 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 1632 1632
510 0 busy = 1;
511 1632 ▶ if (!busy)
Branch: 1 branch
BranchTrueFalseTotal
if (!busy) 1632 0 1632
512 1632 return; /* exclusive: wlock held + every rdepth 0 */
513 /* Wait for a reader to release (drain_seq bump) or time out to re-scan
514 * (which reclaims any newly-dead slotted reader). */
515 0 syscall(SYS_futex, &hdr->drain_seq, FUTEX_WAIT, v, &rdx_lock_timeout, NULL, 0);
516 }
517 }
518  
519 1632 static inline void rdx_rwlock_wrunlock(RdxHandle *h) {
520 1632 RdxHeader *hdr = h->hdr;
521 1632 __atomic_store_n(&hdr->wlock, 0, __ATOMIC_RELEASE);
522 1632 ▶ if (__atomic_load_n(&hdr->rwait, __ATOMIC_RELAXED) > 0)
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&hdr->rwait, __ATOMIC_RELAXED) > 0) 0 1632 1632
523 0 syscall(SYS_futex, &hdr->wlock, FUTEX_WAKE, INT_MAX, NULL, NULL, 0);
524 1632 }
525  
526 /* ================================================================
527 * Layout math + node-pool / arena accessors
528 *
529 * Layout: Header -> reader_slots[1024] -> occ_bitmap -> node_pool[node_cap] -> arena[arena_cap]
530 * RdxNode is 8-byte aligned (sizeof %8 == 0), RdxReaderSlot is 16 bytes, and the
531 * occ bitmap is RDX_OCC_BYTES (a multiple of 8), so node_pool_off stays 8-byte
532 * aligned. The arena is raw bytes (no alignment requirement) after the pool.
533 * ================================================================ */
534  
535 typedef struct { uint64_t reader_slots, occ, node_pool, arena; } RdxLayout;
536  
537 157 static inline RdxLayout rdx_layout(uint32_t node_cap) {
538 RdxLayout L;
539 157 L.reader_slots = sizeof(RdxHeader);
540 157 L.occ = L.reader_slots + (uint64_t)RDX_READER_SLOTS * sizeof(RdxReaderSlot);
541 157 L.node_pool = L.occ + RDX_OCC_BYTES;
542 157 L.arena = L.node_pool + (uint64_t)node_cap * sizeof(RdxNode);
543 157 return L;
544 }
545  
546 83 static inline uint64_t rdx_total_size(uint32_t node_cap, uint32_t arena_cap) {
547 83 RdxLayout L = rdx_layout(node_cap);
548 83 return L.arena + (uint64_t)arena_cap;
549 }
550  
551 12377 static inline RdxNode *rdx_nodes(RdxHandle *h) {
552 12377 return (RdxNode *)((char *)h->base + h->node_pool_off); /* cached trusted offset, not peer-writable header */
553 }
554 6018 static inline uint8_t *rdx_arena(RdxHandle *h) {
555 6018 return (uint8_t *)((char *)h->base + h->arena_off); /* cached trusted offset, not peer-writable header */
556 }
557  
558 /* ================================================================
559 * Node allocation + arena append. Callers hold the WRITE lock.
560 * ================================================================ */
561  
562 /* Push a node onto the free list. Callers must hold the write lock and must
563 * have already made the node unreachable from the tree. Node 0 is NIL and is
564 * never freed. The free-list link lives in the dead node's label_off. */
565 142 static inline void rdx_free_node(RdxHandle *h, uint32_t idx) {
566 142 ▶ if (idx == 0 || idx >= h->node_cap) return; /* never recycle NIL or an out-of-pool index */
Branch: 2 branches
BranchTrueFalseTotal
if (idx == 0 || idx >= h->node_cap) return; /* never recycle NIL or an out-of-pool index */ 142 0 142
if (idx == 0 || idx >= h->node_cap) return; /* never recycle NIL or an out-of-pool index */ 0 142 142
567 142 RdxHeader *hdr = h->hdr;
568 142 RdxNode *nodes = rdx_nodes(h);
569 142 memset(&nodes[idx], 0, sizeof(RdxNode));
570 142 nodes[idx].label_off = hdr->free_head; /* next-free link (0 terminates) */
571 142 __atomic_store_n(&hdr->free_head, idx, __ATOMIC_RELEASE);
572 }
573  
574 /* Recycle a node or advance the high-water mark; return 0 if exhausted. */
575 1379 static inline uint32_t rdx_alloc_node(RdxHandle *h) {
576 1379 RdxHeader *hdr = h->hdr;
577 1379 RdxNode *nodes = rdx_nodes(h);
578 /* Recycle first. free_head is peer-writable, so bound it against the cached
579 * pool capacity before dereferencing: a corrupt value must never index out of
580 * the node pool (an in-range corrupt value can only confuse the tree, which is
581 * the same trust level as any other header field). */
582 1379 uint32_t idx = hdr->free_head;
583 1379 ▶ if (idx != 0 && idx < h->node_cap) {
Branch: 2 branches
BranchTrueFalseTotal
if (idx != 0 && idx < h->node_cap) { 140 1239 1379
if (idx != 0 && idx < h->node_cap) { 140 0 140
584 140 uint32_t next = nodes[idx].label_off;
585 140 ▶ hdr->free_head = (next < h->node_cap) ? next : 0;
Branch: 1 branch
BranchTrueFalseTotal
hdr->free_head = (next < h->node_cap) ? next : 0; 140 0 140
586 140 __atomic_thread_fence(__ATOMIC_RELEASE); /* unlink before reusing the free-list link */
587 140 memset(&nodes[idx], 0, sizeof(RdxNode));
588 140 return idx;
589 }
590 1239 ▶ if (hdr->node_used < h->node_cap) { /* cached cap: the write index must stay in the real pool */
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->node_used < h->node_cap) { /* cached cap: the write index must stay in the real pool */ 1239 0 1239
591 1239 idx = hdr->node_used++;
592 1239 memset(&nodes[idx], 0, sizeof(RdxNode));
593 1239 return idx;
594 }
595 0 return 0;
596 }
597  
598 /* Append `len` bytes to the arena, returning the offset of the first byte.
599 * Append-only: existing bytes never move, so pointers into the arena stay
600 * valid across appends. The caller pre-checked that len bytes fit. */
601 1095 static inline uint32_t rdx_arena_append(RdxHandle *h, const uint8_t *bytes, uint32_t len) {
602 1095 RdxHeader *hdr = h->hdr;
603 1095 uint32_t off = hdr->arena_used;
604 /* off is the peer-writable arena_used; the caller pre-checked room against
605 * the cached cap, but re-verify here so a concurrent lock-violating peer
606 * that inflated arena_used cannot drive this memcpy past the arena. */
607 1095 ▶ if (len) {
Branch: 1 branch
BranchTrueFalseTotal
if (len) { 1095 0 1095
608 1095 ▶ if ((uint64_t)off + len > h->arena_cap) return off; /* refuse OOB write */
Branch: 1 branch
BranchTrueFalseTotal
if ((uint64_t)off + len > h->arena_cap) return off; /* refuse OOB write */ 0 1095 1095
609 1095 memcpy(rdx_arena(h) + off, bytes, len);
610 }
611 1095 hdr->arena_used += len;
612 1095 return off;
613 }
614  
615 /* Worst case any single insert consumes: the copy-on-write edge split
616 * transiently allocates THREE nodes (mid + ch2 + the new leaf) before the
617 * displaced child is recycled post-commit (net consumption is 2), plus up to
618 * klen arena bytes (the leaf's label). Returns 1 if both fit, 0 otherwise.
619 * Caller holds the write lock. */
620 #define RDX_INSERT_MAX_ALLOC 3
621  
622 /* Count the nodes a single insert can draw on: fresh high-water slots plus
623 * free-list entries. rdx_alloc_node recycles before bumping the high-water
624 * mark, so both sources must count -- checking the high-water mark alone
625 * would refuse inserts that recycled nodes could satisfy, and (pre-fix)
626 * checking it against 2 instead of 3 let a split run out of nodes mid-way
627 * and return 0, which insert reported as "key already existed, updated"
628 * while the key was never stored.
629 * The free-list head and links live in peer-writable shared memory, threaded
630 * through label_off: walking at most the remaining need keeps a corrupt list
631 * containing a cycle bounded here, and every link is checked against the
632 * cached pool capacity before it is dereferenced -- the same bounds
633 * rdx_alloc_node applies when it pops. The walk runs under the caller's
634 * write lock, so a well-formed list cannot change under it. */
635 1106 static inline int rdx_nodes_available(RdxHandle *h, uint32_t need) {
636 1106 RdxHeader *hdr = h->hdr;
637 /* Cached cap: the used counter is peer-writable, so compute headroom
638 * against the fixed geometry (and clamp an inflated used-mark to "no
639 * high-water room", so the unsigned subtraction can never wrap to a huge
640 * "room available"). */
641 1106 ▶ uint32_t avail = (hdr->node_used < h->node_cap) ? h->node_cap - hdr->node_used : 0;
Branch: 1 branch
BranchTrueFalseTotal
uint32_t avail = (hdr->node_used < h->node_cap) ? h->node_cap - hdr->node_used : 0; 1106 0 1106
642 1106 RdxNode *nodes = rdx_nodes(h);
643 1106 uint32_t idx = hdr->free_head;
644 1106 ▶ while (avail < need && idx != 0 && idx < h->node_cap) {
Branch: 3 branches
BranchTrueFalseTotal
while (avail < need && idx != 0 && idx < h->node_cap) { 2 1104 1106
while (avail < need && idx != 0 && idx < h->node_cap) { 0 2 2
while (avail < need && idx != 0 && idx < h->node_cap) { 0 0 0
645 0 avail++;
646 0 idx = nodes[idx].label_off;
647 }
648 1106 return avail >= need;
649 }
650  
651 1106 static inline int rdx_insert_has_room(RdxHandle *h, uint32_t klen) {
652 1106 RdxHeader *hdr = h->hdr;
653 1106 ▶ if (!rdx_nodes_available(h, RDX_INSERT_MAX_ALLOC)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!rdx_nodes_available(h, RDX_INSERT_MAX_ALLOC)) return 0; 2 1104 1106
654 /* Cached cap, same anti-wrap guard as above for the peer-writable
655 * arena_used. */
656 1104 ▶ if (hdr->arena_used > h->arena_cap || h->arena_cap - hdr->arena_used < klen) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (hdr->arena_used > h->arena_cap || h->arena_cap - hdr->arena_used < klen) return 0; 1104 0 1104
if (hdr->arena_used > h->arena_cap || h->arena_cap - hdr->arena_used < klen) return 0; 1 1103 1104
657 1103 return 1;
658 }
659  
660 /* ================================================================
661 * Radix-tree core
662 * ================================================================ */
663  
664 #ifndef RDX_MIN
665 #define RDX_MIN(a, b) ((a) < (b) ? (a) : (b))
666 #endif
667  
668 /* Common-prefix length: number of leading bytes where a[i]==b[i], up to max. */
669 2847 static inline uint32_t rdx_cpl(const uint8_t *a, const uint8_t *b, uint32_t max) {
670 2847 uint32_t i = 0;
671 9002 ▶ while (i < max && a[i] == b[i]) i++;
Branch: 2 branches
BranchTrueFalseTotal
while (i < max && a[i] == b[i]) i++; 6294 2708 9002
while (i < max && a[i] == b[i]) i++; 6155 139 6294
672 2847 return i;
673 }
674  
675 #define RDX_PENDING_VALUE 1
676 #define RDX_PENDING_LINK 2
677 #define RDX_PENDING_DELETE 3
678 #define RDX_PENDING_CLEAR 4
679  
680 /* Record the count and commit word before changing the live tree. Recovery
681 * checks that word to distinguish an interrupted mutation from a committed one. */
682 1623 static inline void rdx_begin_mutation(RdxHandle *h, const void *commit, uint32_t value, uint8_t kind) {
683 1623 RdxHeader *hdr = h->hdr;
684 1623 hdr->pending_keys = hdr->keys;
685 1623 ▶ hdr->pending_off = commit ? (const uint8_t *)commit - (const uint8_t *)h->base : 0;
Branch: 1 branch
BranchTrueFalseTotal
hdr->pending_off = commit ? (const uint8_t *)commit - (const uint8_t *)h->base : 0; 1622 1 1623
686 1623 hdr->pending_value = value;
687 1623 __atomic_store_n(&hdr->pending_kind, kind, __ATOMIC_RELEASE);
688 1623 }
689  
690 1623 static inline void rdx_finish_mutation(RdxHandle *h) {
691 1623 __atomic_store_n(&h->hdr->pending_kind, 0, __ATOMIC_RELEASE);
692 1623 }
693  
694 /* Insert key -> value. Returns 1 if a new key was added, 0 if an existing key
695 * was updated. Caller holds the write lock AND has verified rdx_insert_has_room
696 * (so every rdx_alloc_node / rdx_arena_append below is guaranteed to succeed,
697 * keeping the tree consistent -- no partial-split-on-OOM possibility). */
698 1103 static inline int rdx_insert_locked(RdxHandle *h, const uint8_t *key, uint32_t klen, uint64_t value) {
699 1103 RdxHeader *hdr = h->hdr;
700 1103 RdxNode *nodes = rdx_nodes(h);
701 1103 uint8_t *arena = rdx_arena(h);
702 1103 uint32_t cur = hdr->root, kpos = 0;
703 1103 ▶ if (cur == 0 || cur >= h->node_cap) return 0; /* root read from peer-writable header; keep the index in-pool */
Branch: 2 branches
BranchTrueFalseTotal
if (cur == 0 || cur >= h->node_cap) return 0; /* root read from peer-writable header; keep the index in-pool */ 1103 0 1103
if (cur == 0 || cur >= h->node_cap) return 0; /* root read from peer-writable header; keep the index in-pool */ 1103 0 1103
704 2705 for (;;) {
705 3808 ▶ if (kpos == klen) { /* key ends here -> mark this node */
Branch: 1 branch
BranchTrueFalseTotal
if (kpos == klen) { /* key ends here -> mark this node */ 5 3803 3808
706 5 int isnew = !nodes[cur].has_value;
707 5 ▶ if (isnew) rdx_begin_mutation(h, &nodes[cur].has_value, 1, RDX_PENDING_VALUE);
Branch: 1 branch
BranchTrueFalseTotal
if (isnew) rdx_begin_mutation(h, &nodes[cur].has_value, 1, RDX_PENDING_VALUE); 2 3 5
708 5 nodes[cur].value = value;
709 5 __atomic_store_n(&nodes[cur].has_value, 1, __ATOMIC_RELEASE);
710 5 ▶ if (isnew) { hdr->keys++; rdx_finish_mutation(h); }
Branch: 1 branch
BranchTrueFalseTotal
if (isnew) { hdr->keys++; rdx_finish_mutation(h); } 2 3 5
711 5 return isnew;
712 }
713 3803 uint8_t b = key[kpos];
714 3803 uint32_t ch = nodes[cur].children[b];
715 /* child index is read from the peer-writable mmap; an out-of-pool value
716 * (like the read paths' `ch >= node_used` reject) is treated as absent so
717 * the corrupt link is overwritten by a fresh in-pool leaf below, never
718 * followed into an out-of-bounds node dereference / OOB child write. */
719 3803 ▶ if (ch == 0 || ch >= h->node_cap) { /* no child on b -> new leaf with the rest as its label */
Branch: 2 branches
BranchTrueFalseTotal
if (ch == 0 || ch >= h->node_cap) { /* no child on b -> new leaf with the rest as its label */ 2847 956 3803
if (ch == 0 || ch >= h->node_cap) { /* no child on b -> new leaf with the rest as its label */ 0 2847 2847
720 956 uint32_t leaf = rdx_alloc_node(h);
721 956 nodes = rdx_nodes(h); /* base is stable, but re-fetch defensively after alloc */
722 /* Pool exhausted: rdx_alloc_node returns 0, which is the NIL
723 * sentinel. Writing through it corrupts NIL (every read path
724 * treats 0 as "not found") and linking children[b]=0 silently
725 * drops the key while insert still reports success. Fail instead. */
726 956 ▶ if (!leaf) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!leaf) return 0; 0 956 956
727 956 nodes[leaf].label_off = rdx_arena_append(h, key + kpos, klen - kpos);
728 956 nodes[leaf].label_len = klen - kpos;
729 956 nodes[leaf].has_value = 1;
730 956 nodes[leaf].value = value;
731 /* Publish the fully-initialized leaf before linking it in, so a
732 * process that takes the lock after a mid-insert SIGKILL + dead-
733 * writer recovery never sees children[b]==leaf while the leaf's
734 * label_off/len are still garbage (which would drive an out-of-
735 * bounds arena read). The link is the single-word commit; a crash
736 * before it leaks the node but keeps the tree consistent. */
737 956 rdx_begin_mutation(h, &nodes[cur].children[b], leaf, RDX_PENDING_LINK);
738 956 __atomic_store_n(&nodes[cur].children[b], leaf, __ATOMIC_RELEASE);
739 956 hdr->keys++;
740 956 rdx_finish_mutation(h);
741 956 return 1;
742 }
743 /* match the child's label against key[kpos..]. label_off/label_len also
744 * come from the peer-writable mmap; clamp the extent against the cached
745 * arena capacity (as the read paths do with `loff + llen > arena_used`)
746 * before forming arena + label_off or reading/adjusting the label, so a
747 * corrupted offset can never drive an out-of-bounds arena read or an OOB
748 * label_off/label_len write on the split path below. */
749 2847 uint32_t loff = nodes[ch].label_off, llen = nodes[ch].label_len;
750 2847 ▶ if ((uint64_t)loff + llen > h->arena_cap) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if ((uint64_t)loff + llen > h->arena_cap) return 0; 0 2847 2847
751 2847 const uint8_t *L = arena + loff;
752 2847 uint32_t m = rdx_cpl(L, key + kpos, RDX_MIN(llen, klen - kpos));
753 2847 ▶ if (m == llen) { /* whole label matched -> descend */
Branch: 1 branch
BranchTrueFalseTotal
if (m == llen) { /* whole label matched -> descend */ 2705 142 2847
754 2705 cur = ch;
755 2705 kpos += llen;
756 2705 continue;
757 }
758 /* partial match -> split the child's edge at m.
759 * mid takes L[0..m-1]; child keeps L[m..] (sharing the same arena region).
760 * Capture mid_first = L[m] BEFORE mutating ch's label_off (L is a pointer
761 * into the arena and is unaffected by the label_off change, but be explicit). */
762 142 uint8_t mid_first = L[m];
763 /* Copy-on-write split. Build a NEW child (ch2) that carries the
764 * remainder label and inherits ch's children/value, plus the new middle
765 * node, and leave the live tree COMPLETELY untouched until one final
766 * store publishes mid.
767 *
768 * The previous in-place version truncated ch's label (label_off += m)
769 * before publishing mid, so a crash in that window left `cur` pointing
770 * at a child whose label had lost its first m bytes -- silently losing
771 * every key beneath it. Publishing first instead would leave the prefix
772 * counted twice, so NEITHER in-place ordering is crash-safe; only
773 * copy-on-write is. The displaced ch is recycled AFTER the commit, so a
774 * crash between the two only leaks one node (reclaimed by the free list)
775 * rather than corrupting the tree. Node accounting is unchanged versus
776 * the old code: the extra allocation is paid for by recycling ch. */
777 142 uint32_t mid = rdx_alloc_node(h);
778 /* Pool exhausted -> 0 == NIL; bail before touching anything, so the tree
779 * is left exactly as it was rather than writing through NIL. */
780 142 ▶ if (!mid) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!mid) return 0; 0 142 142
781 142 uint32_t ch2 = rdx_alloc_node(h);
782 142 ▶ if (!ch2) { rdx_free_node(h, mid); return 0; }
Branch: 1 branch
BranchTrueFalseTotal
if (!ch2) { rdx_free_node(h, mid); return 0; } 0 142 142
783 142 uint32_t leaf = 0;
784 142 ▶ if (kpos + m != klen) { /* key continues past the split */
Branch: 1 branch
BranchTrueFalseTotal
if (kpos + m != klen) { /* key continues past the split */ 139 3 142
785 139 leaf = rdx_alloc_node(h);
786 139 ▶ if (!leaf) { rdx_free_node(h, ch2); rdx_free_node(h, mid); return 0; }
Branch: 1 branch
BranchTrueFalseTotal
if (!leaf) { rdx_free_node(h, ch2); rdx_free_node(h, mid); return 0; } 0 139 139
787 }
788 142 nodes = rdx_nodes(h);
789 142 nodes[ch2] = nodes[ch]; /* inherit children/value */
790 142 nodes[ch2].label_off = nodes[ch].label_off + m; /* remainder, same arena region */
791 142 nodes[ch2].label_len = nodes[ch].label_len - m;
792 142 nodes[mid].label_off = nodes[ch].label_off; /* first m bytes */
793 142 nodes[mid].label_len = m;
794 142 nodes[mid].children[mid_first] = ch2;
795 142 ▶ if (leaf) {
Branch: 1 branch
BranchTrueFalseTotal
if (leaf) { 139 3 142
796 139 nodes[leaf].label_off = rdx_arena_append(h, key + kpos + m, klen - kpos - m);
797 139 nodes[leaf].label_len = klen - kpos - m;
798 139 nodes[leaf].has_value = 1;
799 139 nodes[leaf].value = value;
800 139 nodes[mid].children[key[kpos + m]] = leaf;
801 } else { /* key ends exactly at the split point */
802 3 nodes[mid].has_value = 1;
803 3 nodes[mid].value = value;
804 }
805 /* Single-word commit: everything above is unreachable until this store. */
806 142 rdx_begin_mutation(h, &nodes[cur].children[b], mid, RDX_PENDING_LINK);
807 142 __atomic_store_n(&nodes[cur].children[b], mid, __ATOMIC_RELEASE);
808 /* A release store does not keep the recycle's memset below it. */
809 142 __atomic_thread_fence(__ATOMIC_RELEASE);
810 142 rdx_free_node(h, ch); /* displaced: recycle post-commit */
811 142 hdr->keys++;
812 142 rdx_finish_mutation(h);
813 142 return 1;
814 }
815 }
816  
817 /* Navigate `key` to its terminal node. Returns the node index once the full
818 * key is consumed, or 0 (the NIL sentinel) if any step diverges. Read-only, so
819 * the caller may hold the READ or write lock. root is always >= 1, so a 0
820 * return is an unambiguous "not found". */
821 3769 static inline uint32_t rdx_find_locked(RdxHandle *h, const uint8_t *key, uint32_t klen) {
822 3769 RdxNode *nodes = rdx_nodes(h);
823 3769 uint8_t *arena = rdx_arena(h);
824 /* Bounds come from the peer-writable header; clamp the mutable used-marks to
825 * the cached fixed capacities so an inflated node_used/arena_used can never
826 * admit an out-of-pool child index or out-of-arena label extent. */
827 3769 uint32_t node_used = h->hdr->node_used, arena_used = h->hdr->arena_used;
828 3769 ▶ if (node_used > h->node_cap) node_used = h->node_cap;
Branch: 1 branch
BranchTrueFalseTotal
if (node_used > h->node_cap) node_used = h->node_cap; 0 3769 3769
829 3769 ▶ if (arena_used > h->arena_cap) arena_used = h->arena_cap;
Branch: 1 branch
BranchTrueFalseTotal
if (arena_used > h->arena_cap) arena_used = h->arena_cap; 0 3769 3769
830 3769 uint32_t cur = h->hdr->root, kpos = 0;
831 3769 ▶ if (cur == 0 || cur >= node_used) return 0; /* root read from peer-writable header */
Branch: 2 branches
BranchTrueFalseTotal
if (cur == 0 || cur >= node_used) return 0; /* root read from peer-writable header */ 3769 0 3769
if (cur == 0 || cur >= node_used) return 0; /* root read from peer-writable header */ 0 3769 3769
832 14971 for (;;) {
833 18740 ▶ if (kpos == klen) return cur;
Branch: 1 branch
BranchTrueFalseTotal
if (kpos == klen) return cur; 3728 15012 18740
834 15012 uint32_t ch = nodes[cur].children[key[kpos]];
835 /* child index and label extent are read from the mmap'd
836 * (locally attacker-writable) file; bound both before dereferencing.
837 * Valid data always satisfies these, so it is a never-taken branch. */
838 15012 ▶ if (!ch || ch >= node_used) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (!ch || ch >= node_used) return 0; 14983 29 15012
if (!ch || ch >= node_used) return 0; 0 14983 14983
839 14983 uint32_t loff = nodes[ch].label_off, llen = nodes[ch].label_len;
840 14983 ▶ if ((uint64_t)loff + llen > arena_used) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if ((uint64_t)loff + llen > arena_used) return 0; 0 14983 14983
841 14983 ▶ if (klen - kpos < llen) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (klen - kpos < llen) return 0; 10 14973 14983
842 14973 ▶ if (memcmp(arena + loff, key + kpos, llen) != 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (memcmp(arena + loff, key + kpos, llen) != 0) return 0; 2 14971 14973
843 14971 cur = ch;
844 14971 kpos += llen;
845 }
846 }
847  
848 /* Exact lookup. Returns 1 and sets *out if found, else 0. Read-only (no path
849 * compression) so the caller may hold the READ lock. */
850 3245 static inline int rdx_lookup_locked(RdxHandle *h, const uint8_t *key, uint32_t klen, uint64_t *out) {
851 3245 uint32_t n = rdx_find_locked(h, key, klen);
852 3245 ▶ if (!n) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!n) return 0; 40 3205 3245
853 3205 RdxNode *nodes = rdx_nodes(h);
854 3205 ▶ if (nodes[n].has_value) { if (out) *out = nodes[n].value; return 1; }
Branch: 2 branches
BranchTrueFalseTotal
if (nodes[n].has_value) { if (out) *out = nodes[n].value; return 1; } 2680 525 3205
if (nodes[n].has_value) { if (out) *out = nodes[n].value; return 1; } 1617 1063 2680
855 525 return 0;
856 }
857  
858 /* Longest-prefix match: is some stored key a prefix of `key`? Returns 1 and
859 * sets *out to the value of the LONGEST such stored key, else 0. Read-only. */
860 51 static inline int rdx_longest_prefix_locked(RdxHandle *h, const uint8_t *key, uint32_t klen, uint64_t *out) {
861 51 RdxNode *nodes = rdx_nodes(h);
862 51 uint8_t *arena = rdx_arena(h);
863 /* Same clamp as rdx_find_locked: the used-marks are peer-writable, so cap
864 * them at the cached fixed geometry before they bound any array access. */
865 51 uint32_t node_used = h->hdr->node_used, arena_used = h->hdr->arena_used;
866 51 ▶ if (node_used > h->node_cap) node_used = h->node_cap;
Branch: 1 branch
BranchTrueFalseTotal
if (node_used > h->node_cap) node_used = h->node_cap; 0 51 51
867 51 ▶ if (arena_used > h->arena_cap) arena_used = h->arena_cap;
Branch: 1 branch
BranchTrueFalseTotal
if (arena_used > h->arena_cap) arena_used = h->arena_cap; 0 51 51
868 51 uint32_t cur = h->hdr->root, kpos = 0;
869 51 int found = 0;
870 51 ▶ if (cur == 0 || cur >= node_used) return 0; /* root read from peer-writable header */
Branch: 2 branches
BranchTrueFalseTotal
if (cur == 0 || cur >= node_used) return 0; /* root read from peer-writable header */ 51 0 51
if (cur == 0 || cur >= node_used) return 0; /* root read from peer-writable header */ 0 51 51
871 51 ▶ if (nodes[cur].has_value) { if (out) *out = nodes[cur].value; found = 1; } /* empty key stored */
Branch: 2 branches
BranchTrueFalseTotal
if (nodes[cur].has_value) { if (out) *out = nodes[cur].value; found = 1; } /* empty key stored */ 3 48 51
if (nodes[cur].has_value) { if (out) *out = nodes[cur].value; found = 1; } /* empty key stored */ 3 0 3
872 118 for (;;) {
873 169 ▶ if (kpos == klen) break;
Branch: 1 branch
BranchTrueFalseTotal
if (kpos == klen) break; 16 153 169
874 153 uint32_t ch = nodes[cur].children[key[kpos]];
875 /* same bound as rdx_find_locked -- child index and label
876 * extent come from the attacker-writable mmap; reject on a bad value. */
877 153 ▶ if (!ch || ch >= node_used) break;
Branch: 2 branches
BranchTrueFalseTotal
if (!ch || ch >= node_used) break; 131 22 153
if (!ch || ch >= node_used) break; 131 0 131
878 131 uint32_t loff = nodes[ch].label_off, llen = nodes[ch].label_len;
879 131 ▶ if ((uint64_t)loff + llen > arena_used) break;
Branch: 1 branch
BranchTrueFalseTotal
if ((uint64_t)loff + llen > arena_used) break; 0 131 131
880 131 ▶ if (klen - kpos < llen || memcmp(arena + loff, key + kpos, llen) != 0) break;
Branch: 2 branches
BranchTrueFalseTotal
if (klen - kpos < llen || memcmp(arena + loff, key + kpos, llen) != 0) break; 128 3 131
if (klen - kpos < llen || memcmp(arena + loff, key + kpos, llen) != 0) break; 118 10 128
881 118 cur = ch;
882 118 kpos += llen;
883 118 ▶ if (nodes[cur].has_value) { if (out) *out = nodes[cur].value; found = 1; }
Branch: 2 branches
BranchTrueFalseTotal
if (nodes[cur].has_value) { if (out) *out = nodes[cur].value; found = 1; } 60 58 118
if (nodes[cur].has_value) { if (out) *out = nodes[cur].value; found = 1; } 60 0 60
884 }
885 51 return found;
886 }
887  
888 /* Lazy delete: walk to the node; if found and has_value, clear it. Returns
889 * 1 if a key was removed, 0 if absent. Does NOT free nodes or compact the
890 * arena in v1. Caller holds the write lock. */
891 524 static inline int rdx_delete_locked(RdxHandle *h, const uint8_t *key, uint32_t klen) {
892 524 uint32_t n = rdx_find_locked(h, key, klen);
893 524 ▶ if (!n) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!n) return 0; 1 523 524
894 523 RdxNode *nodes = rdx_nodes(h);
895 523 ▶ if (!nodes[n].has_value) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!nodes[n].has_value) return 0; 1 522 523
896 522 rdx_begin_mutation(h, &nodes[n].has_value, 0, RDX_PENDING_DELETE);
897 522 __atomic_store_n(&nodes[n].has_value, 0, __ATOMIC_RELEASE);
898 522 h->hdr->keys--;
899 522 rdx_finish_mutation(h);
900 522 return 1;
901 }
902  
903 /* Reset to a single empty root: node_used=2, arena_used=0, keys=0, and a fresh
904 * zeroed root. Caller holds the write lock. */
905 1 static inline void rdx_clear_locked(RdxHandle *h) {
906 1 RdxHeader *hdr = h->hdr;
907 1 RdxNode *nodes = rdx_nodes(h);
908 1 rdx_begin_mutation(h, NULL, 0, RDX_PENDING_CLEAR);
909 1 __atomic_thread_fence(__ATOMIC_RELEASE);
910 1 ▶ if (hdr->root && hdr->root < h->node_cap) { /* root is peer-writable; keep the memset in-pool */
Branch: 2 branches
BranchTrueFalseTotal
if (hdr->root && hdr->root < h->node_cap) { /* root is peer-writable; keep the memset in-pool */ 1 0 1
if (hdr->root && hdr->root < h->node_cap) { /* root is peer-writable; keep the memset in-pool */ 1 0 1
911 1 nodes[hdr->root].has_value = 0;
912 1 __atomic_thread_fence(__ATOMIC_RELEASE);
913 1 memset(&nodes[hdr->root], 0, sizeof(RdxNode)); /* zero children + has_value + label */
914 }
915 /* Unlink before reclaiming: a writer killed in between must not leave the root linking
916 * nodes the counters already hand out again. */
917 1 __atomic_thread_fence(__ATOMIC_RELEASE);
918 1 hdr->free_head = 0;
919 1 __atomic_thread_fence(__ATOMIC_RELEASE);
920 1 hdr->node_used = 2;
921 1 hdr->arena_used = 0;
922 1 hdr->keys = 0;
923 1 rdx_finish_mutation(h);
924 1 }
925  
926 0 static void rdx_repair_mutation(RdxHandle *h) {
927 0 RdxHeader *hdr = h->hdr;
928 0 uint8_t kind = __atomic_load_n(&hdr->pending_kind, __ATOMIC_ACQUIRE);
929 0 ▶ if (!kind) return; /* a writer killed while draining readers has not mutated */
Branch: 1 branch
BranchTrueFalseTotal
if (!kind) return; /* a writer killed while draining readers has not mutated */ 0 0 0
930 0 ▶ if (kind == RDX_PENDING_CLEAR) { rdx_clear_locked(h); return; }
Branch: 1 branch
BranchTrueFalseTotal
if (kind == RDX_PENDING_CLEAR) { rdx_clear_locked(h); return; } 0 0 0
931 0 uint64_t off = hdr->pending_off;
932 0 ▶ size_t width = kind == RDX_PENDING_LINK ? sizeof(uint32_t) : 1;
Branch: 1 branch
BranchTrueFalseTotal
size_t width = kind == RDX_PENDING_LINK ? sizeof(uint32_t) : 1; 0 0 0
933 0 ▶ if (off < h->node_pool_off || off > h->arena_off - width) return;
Branch: 2 branches
BranchTrueFalseTotal
if (off < h->node_pool_off || off > h->arena_off - width) return; 0 0 0
if (off < h->node_pool_off || off > h->arena_off - width) return; 0 0 0
934 0 ▶ if (kind == RDX_PENDING_LINK && off % sizeof(uint32_t)) return;
Branch: 2 branches
BranchTrueFalseTotal
if (kind == RDX_PENDING_LINK && off % sizeof(uint32_t)) return; 0 0 0
if (kind == RDX_PENDING_LINK && off % sizeof(uint32_t)) return; 0 0 0
935 0 const uint8_t *p = (const uint8_t *)h->base + off;
936 0 uint32_t committed = kind == RDX_PENDING_LINK
937 0 ? __atomic_load_n((const uint32_t *)p, __ATOMIC_ACQUIRE)
938 0 ▶ : __atomic_load_n(p, __ATOMIC_ACQUIRE);
Branch: 1 branch
BranchTrueFalseTotal
: __atomic_load_n(p, __ATOMIC_ACQUIRE); 0 0 0
939 0 hdr->keys = hdr->pending_keys;
940 0 ▶ if (committed == hdr->pending_value)
Branch: 1 branch
BranchTrueFalseTotal
if (committed == hdr->pending_value) 0 0 0
941 0 ▶ hdr->keys += kind == RDX_PENDING_DELETE ? (uint64_t)-1 : 1;
Branch: 1 branch
BranchTrueFalseTotal
hdr->keys += kind == RDX_PENDING_DELETE ? (uint64_t)-1 : 1; 0 0 0
942 0 rdx_finish_mutation(h);
943 }
944  
945 /* ================================================================
946 * Validate args + header init / setup / open / destroy
947 * ================================================================ */
948  
949 /* Validate create args. Single source of truth: the XS layer does NOT
950 * duplicate these range checks. */
951 42 static int rdx_validate_create_args(uint64_t node_cap, uint64_t arena_cap, char *errbuf) {
952 42 ▶ if (errbuf) errbuf[0] = '\0';
Branch: 1 branch
BranchTrueFalseTotal
if (errbuf) errbuf[0] = '\0'; 42 0 42
953 42 ▶ if (node_cap < 2) { RDX_ERR("node_capacity must be >= 2 (NIL + root)"); return 0; }
Branch: 2 branches
BranchTrueFalseTotal
if (node_cap < 2) { RDX_ERR("node_capacity must be >= 2 (NIL + root)"); return 0; } 2 40 42
if (node_cap < 2) { RDX_ERR("node_capacity must be >= 2 (NIL + root)"); return 0; } 2 0 2
954 40 ▶ if (node_cap > RDX_MAX_NODES) { RDX_ERR("node_capacity must be <= %u", (unsigned)RDX_MAX_NODES); return 0; }
Branch: 2 branches
BranchTrueFalseTotal
if (node_cap > RDX_MAX_NODES) { RDX_ERR("node_capacity must be <= %u", (unsigned)RDX_MAX_NODES); return 0; } 1 39 40
if (node_cap > RDX_MAX_NODES) { RDX_ERR("node_capacity must be <= %u", (unsigned)RDX_MAX_NODES); return 0; } 1 0 1
955 39 ▶ if (arena_cap < 1) { RDX_ERR("arena_capacity must be >= 1"); return 0; }
Branch: 2 branches
BranchTrueFalseTotal
if (arena_cap < 1) { RDX_ERR("arena_capacity must be >= 1"); return 0; } 1 38 39
if (arena_cap < 1) { RDX_ERR("arena_capacity must be >= 1"); return 0; } 1 0 1
956 38 ▶ if (arena_cap > RDX_MAX_ARENA) { RDX_ERR("arena_capacity must be <= %u", (unsigned)RDX_MAX_ARENA); return 0; }
Branch: 2 branches
BranchTrueFalseTotal
if (arena_cap > RDX_MAX_ARENA) { RDX_ERR("arena_capacity must be <= %u", (unsigned)RDX_MAX_ARENA); return 0; } 1 37 38
if (arena_cap > RDX_MAX_ARENA) { RDX_ERR("arena_capacity must be <= %u", (unsigned)RDX_MAX_ARENA); return 0; } 1 0 1
957 /* Keep the whole mapping within size_t (matters on 32-bit, but we already
958 * require 64-bit Perl; still, guard against absurd products). */
959 {
960 37 uint64_t total = rdx_total_size((uint32_t)node_cap, (uint32_t)arena_cap);
961 if (total > (uint64_t)SIZE_MAX) { RDX_ERR("requested mapping too large"); return 0; }
962 }
963 37 return 1;
964 }
965  
966 29 static inline void rdx_init_header(void *base, uint32_t node_cap, uint32_t arena_cap, uint64_t total_size) {
967 29 RdxLayout L = rdx_layout(node_cap);
968 29 RdxHeader *hdr = (RdxHeader *)base;
969 /* Zero the header + reader-slot region (lock-recovery state). The node
970 * pool and arena are read only within [0,node_used)/[0,arena_used); a
971 * fresh mapping is OS-zeroed, but we explicitly zero node 0 (NIL) and the
972 * root below for clarity / for the reopen-of-anon path. */
973 29 memset(base, 0, (size_t)L.node_pool);
974 29 hdr->version = RDX_VERSION;
975 29 hdr->node_cap = node_cap;
976 29 hdr->arena_cap = arena_cap;
977 29 hdr->total_size = total_size;
978 29 hdr->reader_slots_off = L.reader_slots;
979 29 hdr->node_pool_off = L.node_pool;
980 29 hdr->arena_off = L.arena;
981 {
982 29 RdxNode *nodes = (RdxNode *)((char *)base + L.node_pool);
983 29 memset(&nodes[0], 0, sizeof(RdxNode)); /* NIL sentinel */
984 29 memset(&nodes[1], 0, sizeof(RdxNode)); /* root: empty label, no value, no children */
985 29 hdr->root = 1;
986 29 hdr->node_used = 2; /* NIL + root */
987 29 hdr->arena_used = 0;
988 29 hdr->keys = 0;
989 }
990 /* Publish magic LAST, as a release store: it is the commit point, so a
991 creator killed before it leaves magic==0 and never a file mistaken for
992 a valid one. A kill during the field stores leaves one to remove by
993 hand. */
994 29 __atomic_store_n(&hdr->magic, RDX_MAGIC, __ATOMIC_RELEASE);
995 29 __atomic_thread_fence(__ATOMIC_SEQ_CST);
996 29 }
997  
998 36 static inline RdxHandle *rdx_setup(void *base, size_t map_size,
999 const char *path, int backing_fd, char *errbuf) {
1000 36 RdxHeader *hdr = (RdxHeader *)base;
1001 36 RdxHandle *h = (RdxHandle *)calloc(1, sizeof(RdxHandle));
1002 36 ▶ if (!h) {
Branch: 1 branch
BranchTrueFalseTotal
if (!h) { 0 36 36
1003 0 munmap(base, map_size);
1004 0 ▶ if (backing_fd >= 0) close(backing_fd);
Branch: 1 branch
BranchTrueFalseTotal
if (backing_fd >= 0) close(backing_fd); 0 0 0
1005 0 return NULL;
1006 }
1007 36 h->hdr = hdr;
1008 36 h->base = base;
1009 36 h->reader_slots = (RdxReaderSlot *)((uint8_t *)base + sizeof(RdxHeader)); /* trusted layout, not the peer-writable header offset */
1010 /* Cache fixed geometry from the (already-validated) header and derive the
1011 * pool/arena offsets from the canonical layout -- never re-read the
1012 * peer-writable node_pool_off/arena_off/node_cap/arena_cap on the hot path. */
1013 {
1014 36 RdxLayout L = rdx_layout(hdr->node_cap);
1015 36 h->occ = (uint64_t *)((uint8_t *)base + L.occ); /* trusted layout offset */
1016 36 h->node_cap = hdr->node_cap;
1017 36 h->arena_cap = hdr->arena_cap;
1018 36 h->node_pool_off = L.node_pool;
1019 36 h->arena_off = L.arena;
1020 }
1021 36 h->mmap_size = map_size;
1022 36 ▶ h->path = path ? strdup(path) : NULL;
Branch: 1 branch
BranchTrueFalseTotal
h->path = path ? strdup(path) : NULL; 16 20 36
1023 36 ▶ if (path && h->path && path[0] != '/') {
Branch: 3 branches
BranchTrueFalseTotal
if (path && h->path && path[0] != '/') { 16 20 36
if (path && h->path && path[0] != '/') { 16 0 16
if (path && h->path && path[0] != '/') { 3 13 16
1024 3 char *cwd = getcwd(NULL, 0);
1025 3 ▶ if (cwd) {
Branch: 1 branch
BranchTrueFalseTotal
if (cwd) { 3 0 3
1026 3 size_t len = strlen(cwd) + strlen(path) + 2;
1027 3 h->unlink_path = (char *)malloc(len);
1028 3 ▶ if (h->unlink_path) snprintf(h->unlink_path, len, "%s/%s", cwd, path);
Branch: 1 branch
BranchTrueFalseTotal
if (h->unlink_path) snprintf(h->unlink_path, len, "%s/%s", cwd, path); 3 0 3
1029 3 free(cwd);
1030 }
1031 }
1032 36 ▶ if (path && (!h->path || (path[0] != '/' && !h->unlink_path))) {
Branch: 4 branches
BranchTrueFalseTotal
if (path && (!h->path || (path[0] != '/' && !h->unlink_path))) { 16 20 36
if (path && (!h->path || (path[0] != '/' && !h->unlink_path))) { 16 0 16
if (path && (!h->path || (path[0] != '/' && !h->unlink_path))) { 3 13 16
if (path && (!h->path || (path[0] != '/' && !h->unlink_path))) { 0 3 3
1033 0 ▶ RDX_ERR("backing path: %s", strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
RDX_ERR("backing path: %s", strerror(errno)); 0 0 0
1034 0 free(h->unlink_path);
1035 0 free(h->path);
1036 0 free(h);
1037 0 munmap(base, map_size);
1038 0 ▶ if (backing_fd >= 0) close(backing_fd);
Branch: 1 branch
BranchTrueFalseTotal
if (backing_fd >= 0) close(backing_fd); 0 0 0
1039 0 return NULL;
1040 }
1041 36 h->backing_fd = backing_fd;
1042 36 h->my_slot_idx = UINT32_MAX;
1043 36 return h;
1044 }
1045  
1046 /* Validate a mapped header (shared by rdx_create reopen and rdx_open_fd).
1047 * Stored geometry wins on reopen; require total_size to equal both the size
1048 * the stored caps imply AND the actual file size, and all offsets to match
1049 * the canonical layout. */
1050 13 static inline int rdx_validate_header(const RdxHeader *hdr, uint64_t file_size) {
1051 13 ▶ if (hdr->magic != RDX_MAGIC) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->magic != RDX_MAGIC) return 0; 4 9 13
1052 9 ▶ if (hdr->version != RDX_VERSION) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->version != RDX_VERSION) return 0; 0 9 9
1053 9 ▶ if (hdr->node_cap < 2 || hdr->node_cap > RDX_MAX_NODES) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (hdr->node_cap < 2 || hdr->node_cap > RDX_MAX_NODES) return 0; 9 0 9
if (hdr->node_cap < 2 || hdr->node_cap > RDX_MAX_NODES) return 0; 0 9 9
1054 9 ▶ if (hdr->arena_cap < 1 || hdr->arena_cap > RDX_MAX_ARENA) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (hdr->arena_cap < 1 || hdr->arena_cap > RDX_MAX_ARENA) return 0; 9 0 9
if (hdr->arena_cap < 1 || hdr->arena_cap > RDX_MAX_ARENA) return 0; 0 9 9
1055 9 ▶ if (hdr->total_size != file_size) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->total_size != file_size) return 0; 0 9 9
1056 9 ▶ if (hdr->total_size != rdx_total_size(hdr->node_cap, hdr->arena_cap)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->total_size != rdx_total_size(hdr->node_cap, hdr->arena_cap)) return 0; 0 9 9
1057 9 RdxLayout L = rdx_layout(hdr->node_cap);
1058 9 ▶ 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 9 9
1059 9 ▶ if (hdr->node_pool_off != L.node_pool) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->node_pool_off != L.node_pool) return 0; 0 9 9
1060 9 ▶ if (hdr->arena_off != L.arena) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->arena_off != L.arena) return 0; 0 9 9
1061 9 ▶ if (hdr->root == 0 || hdr->root >= hdr->node_cap) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (hdr->root == 0 || hdr->root >= hdr->node_cap) return 0; 9 0 9
if (hdr->root == 0 || hdr->root >= hdr->node_cap) return 0; 0 9 9
1062 9 ▶ if (hdr->node_used < 2 || hdr->node_used > hdr->node_cap) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (hdr->node_used < 2 || hdr->node_used > hdr->node_cap) return 0; 9 0 9
if (hdr->node_used < 2 || hdr->node_used > hdr->node_cap) return 0; 0 9 9
1063 9 ▶ if (hdr->arena_used > hdr->arena_cap) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->arena_used > hdr->arena_cap) return 0; 0 9 9
1064 9 ▶ if (hdr->free_head >= hdr->node_cap) return 0; /* 0 == empty; any real entry must be in-pool */
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->free_head >= hdr->node_cap) return 0; /* 0 == empty; any real entry must be in-pool */ 0 9 9
1065 9 return 1;
1066 }
1067  
1068 /* Securely obtain a fd for a file-backed segment: create it exclusively
1069 * (O_CREAT|O_EXCL|O_NOFOLLOW at `mode`, default 0600 = owner-only), or, if it
1070 * already exists, attach to it (O_RDWR|O_NOFOLLOW, no O_CREAT). O_EXCL blocks a
1071 * pre-seeded or hard-linked file and O_NOFOLLOW a symlink swap, so a local
1072 * attacker can no longer redirect or poison the backing store through the path.
1073 * Cross-user sharing is opt-in via a wider `mode` (e.g. 0660); the caller still
1074 * validates the file's contents. */
1075 18 static int rdx_secure_open(const char *path, mode_t mode, char *errbuf) {
1076 18 ▶ for (int attempt = 0; attempt < 100; attempt++) {
Branch: 1 branch
BranchTrueFalseTotal
for (int attempt = 0; attempt < 100; attempt++) { 18 0 18
1077 18 int fd = open(path, O_RDWR|O_CREAT|O_EXCL|O_NOFOLLOW|O_CLOEXEC, mode);
1078 18 ▶ 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 9 18
1079 9 ▶ if (errno != EEXIST) { RDX_ERR("create %s: %s", path, strerror(errno)); return -1; }
Branch: 2 branches
BranchTrueFalseTotal
if (errno != EEXIST) { RDX_ERR("create %s: %s", path, strerror(errno)); return -1; } 0 9 9
if (errno != EEXIST) { RDX_ERR("create %s: %s", path, strerror(errno)); return -1; } 0 0 0
1080 9 fd = open(path, O_RDWR|O_NOFOLLOW|O_CLOEXEC);
1081 9 ▶ if (fd >= 0) return fd;
Branch: 1 branch
BranchTrueFalseTotal
if (fd >= 0) return fd; 9 0 9
1082 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
1083 0 ▶ RDX_ERR("open %s: %s", path, strerror(errno)); /* ELOOP => symlink rejected */
Branch: 1 branch
BranchTrueFalseTotal
RDX_ERR("open %s: %s", path, strerror(errno)); /* ELOOP => symlink rejected */ 0 0 0
1084 0 return -1;
1085 }
1086 0 ▶ RDX_ERR("open %s: create/attach kept racing", path);
Branch: 1 branch
BranchTrueFalseTotal
RDX_ERR("open %s: create/attach kept racing", path); 0 0 0
1087 0 return -1;
1088 }
1089  
1090 /* True iff the whole file is zero -- what an abandoned mid-init
1091 creator leaves. Lets recovery re-init only a provably-empty file, never
1092 one that merely starts with a zero word. Cold path, so a byte scan is
1093 fine. Read, not mapped: a read fault on a tmpfs hole allocates the page. */
1094 2 static int rdx_file_is_zero(int fd, uint64_t size) {
1095 char buf[16384];
1096 537 ▶ for (uint64_t off = 0; off < size; ) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint64_t off = 0; off < size; ) { 536 1 537
1097 536 ssize_t n = pread(fd, buf, size - off < sizeof buf ? (size_t)(size - off) : sizeof buf, (off_t)off);
1098 536 ▶ if (n <= 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (n <= 0) return 0; 0 536 536
1099 8750359 ▶ 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 8749823 8749824
for (ssize_t i = 0; i < n; i++) if (buf[i]) return 0; 8749824 535 8750359
1100 535 off += (uint64_t)n;
1101 }
1102 1 return 1;
1103 }
1104  
1105 /* Opt-in (DATA_RADIXTREE_SHARED_SPARSE=0): reserving commits memory this module otherwise fills lazily. */
1106 12 static int rdx_reserve(int fd, uint64_t size) {
1107 12 const char *sp = getenv("DATA_RADIXTREE_SHARED_SPARSE");
1108 12 ▶ if (!sp || strcmp(sp, "0")) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (!sp || strcmp(sp, "0")) return 0; 0 12 12
if (!sp || strcmp(sp, "0")) return 0; 0 0 0
1109 /* Before Linux 6.11 tmpfs gives up at any pending signal and undoes the allocation, so a
1110 * periodic one could keep it from ever completing; SIGSTOP cannot be blocked. */
1111 sigset_t all, old;
1112 0 sigfillset(&all);
1113 0 sigprocmask(SIG_BLOCK, &all, &old);
1114 int e;
1115 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
1116 0 sigprocmask(SIG_SETMASK, &old, NULL);
1117 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
1118 0 errno = e;
1119 0 return -1;
1120 }
1121  
1122 39 static RdxHandle *rdx_create(const char *path, uint64_t node_cap_in, uint64_t arena_cap_in, mode_t mode, char *errbuf) {
1123 39 ▶ if (!rdx_validate_create_args(node_cap_in, arena_cap_in, errbuf)) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!rdx_validate_create_args(node_cap_in, arena_cap_in, errbuf)) return NULL; 4 35 39
1124 35 uint32_t node_cap = (uint32_t)node_cap_in;
1125 35 uint32_t arena_cap = (uint32_t)arena_cap_in;
1126  
1127 35 uint64_t total = rdx_total_size(node_cap, arena_cap);
1128 35 int anonymous = (path == NULL);
1129 35 int fd = -1;
1130 size_t map_size;
1131 void *base;
1132  
1133 35 ▶ if (anonymous) {
Branch: 1 branch
BranchTrueFalseTotal
if (anonymous) { 17 18 35
1134 17 map_size = (size_t)total;
1135 17 base = mmap(NULL, map_size, PROT_READ|PROT_WRITE, MAP_SHARED|MAP_ANONYMOUS, -1, 0);
1136 17 ▶ if (base == MAP_FAILED) { RDX_ERR("mmap: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { RDX_ERR("mmap: %s", strerror(errno)); return NULL; } 0 17 17
if (base == MAP_FAILED) { RDX_ERR("mmap: %s", strerror(errno)); return NULL; } 0 0 0
1137 } else {
1138 18 fd = rdx_secure_open(path, mode, errbuf);
1139 27 ▶ if (fd < 0) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (fd < 0) return NULL; 0 18 18
1140 18 ▶ if (flock(fd, LOCK_EX) < 0) { RDX_ERR("flock: %s", strerror(errno)); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (flock(fd, LOCK_EX) < 0) { RDX_ERR("flock: %s", strerror(errno)); close(fd); return NULL; } 0 18 18
if (flock(fd, LOCK_EX) < 0) { RDX_ERR("flock: %s", strerror(errno)); close(fd); return NULL; } 0 0 0
1141 struct stat st;
1142 18 ▶ if (fstat(fd, &st) < 0) { RDX_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fstat(fd, &st) < 0) { RDX_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; } 0 18 18
if (fstat(fd, &st) < 0) { RDX_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; } 0 0 0
1143 18 int is_new = (st.st_size == 0);
1144 18 ▶ if (!is_new && (uint64_t)st.st_size < sizeof(RdxHeader)) {
Branch: 2 branches
BranchTrueFalseTotal
if (!is_new && (uint64_t)st.st_size < sizeof(RdxHeader)) { 9 9 18
if (!is_new && (uint64_t)st.st_size < sizeof(RdxHeader)) { 1 8 9
1145 1 ▶ RDX_ERR("%s: file too small (%lld)", path, (long long)st.st_size);
Branch: 1 branch
BranchTrueFalseTotal
RDX_ERR("%s: file too small (%lld)", path, (long long)st.st_size); 1 0 1
1146 1 flock(fd, LOCK_UN); close(fd); return NULL;
1147 }
1148 17 ▶ 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 8 17
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
1149 0 ▶ RDX_ERR("%s: refusing to initialize file not owned by us", path);
Branch: 1 branch
BranchTrueFalseTotal
RDX_ERR("%s: refusing to initialize file not owned by us", path); 0 0 0
1150 0 flock(fd, LOCK_UN); close(fd); return NULL;
1151 }
1152 17 ▶ if (is_new && ftruncate(fd, (off_t)total) < 0) {
Branch: 2 branches
BranchTrueFalseTotal
if (is_new && ftruncate(fd, (off_t)total) < 0) { 9 8 17
if (is_new && ftruncate(fd, (off_t)total) < 0) { 0 9 9
1153 0 ▶ RDX_ERR("ftruncate: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
RDX_ERR("ftruncate: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; 0 0 0
1154 }
1155 17 ▶ if (is_new && rdx_reserve(fd, total) < 0) {
Branch: 2 branches
BranchTrueFalseTotal
if (is_new && rdx_reserve(fd, total) < 0) { 9 8 17
if (is_new && rdx_reserve(fd, total) < 0) { 0 9 9
1156 0 ▶ RDX_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
RDX_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno)); 0 0 0
1157 0 if (ftruncate(fd, 0) < 0) { /* best effort */ }
1158 0 flock(fd, LOCK_UN); close(fd); return NULL;
1159 }
1160 17 ▶ map_size = is_new ? (size_t)total : (size_t)st.st_size;
Branch: 1 branch
BranchTrueFalseTotal
map_size = is_new ? (size_t)total : (size_t)st.st_size; 8 9 17
1161 17 base = mmap(NULL, map_size, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
1162 17 ▶ if (base == MAP_FAILED) {
Branch: 1 branch
BranchTrueFalseTotal
if (base == MAP_FAILED) { 0 17 17
1163 0 ▶ RDX_ERR("mmap: %s", strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
RDX_ERR("mmap: %s", strerror(errno)); 0 0 0
1164 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
1165 0 flock(fd, LOCK_UN); close(fd); return NULL;
1166 }
1167 17 ▶ if (!is_new) {
Branch: 1 branch
BranchTrueFalseTotal
if (!is_new) { 8 9 17
1168 8 ▶ if (!rdx_validate_header((RdxHeader *)base, (uint64_t)st.st_size)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!rdx_validate_header((RdxHeader *)base, (uint64_t)st.st_size)) { 4 4 8
1169 /* Recover an abandoned mid-init file: a creator killed
1170 * between the ftruncate and the header init leaves a
1171 * full-size, all-zero (magic==0) file that would brick every
1172 * future open of this path. Re-initialize ONLY when it is
1173 * exactly our size, still uninitialized, and owned by us;
1174 * anything else still errors. */
1175 4 ▶ if (((RdxHeader *)base)->magic == 0 && (uint64_t)st.st_size == total
Branch: 2 branches
BranchTrueFalseTotal
if (((RdxHeader *)base)->magic == 0 && (uint64_t)st.st_size == total 3 1 4
if (((RdxHeader *)base)->magic == 0 && (uint64_t)st.st_size == total 2 1 3
1176 2 ▶ && st.st_uid == geteuid() && rdx_file_is_zero(fd, map_size)) {
Branch: 2 branches
BranchTrueFalseTotal
&& st.st_uid == geteuid() && rdx_file_is_zero(fd, map_size)) { 2 0 2
&& st.st_uid == geteuid() && rdx_file_is_zero(fd, map_size)) { 1 1 2
1177 1 ▶ if (fchmod(fd, mode) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (fchmod(fd, mode) < 0) { 0 1 1
1178 0 ▶ RDX_ERR("%s: fchmod: %s", path, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
RDX_ERR("%s: fchmod: %s", path, strerror(errno)); 0 0 0
1179 0 munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
1180 }
1181 1 ▶ if (rdx_reserve(fd, total) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (rdx_reserve(fd, total) < 0) { 0 1 1
1182 0 ▶ RDX_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
RDX_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno)); 0 0 0
1183 0 munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
1184 }
1185 1 rdx_init_header(base, node_cap, arena_cap, total);
1186 1 flock(fd, LOCK_UN); close(fd);
1187 1 return rdx_setup(base, map_size, path, -1, errbuf);
1188 }
1189 3 ▶ if (((RdxHeader *)base)->magic == 0 && (uint64_t)st.st_size == total
Branch: 2 branches
BranchTrueFalseTotal
if (((RdxHeader *)base)->magic == 0 && (uint64_t)st.st_size == total 2 1 3
if (((RdxHeader *)base)->magic == 0 && (uint64_t)st.st_size == total 1 1 2
1190 1 ▶ && st.st_uid == geteuid()) {
Branch: 1 branch
BranchTrueFalseTotal
&& st.st_uid == geteuid()) { 1 0 1
1191 1 ▶ RDX_ERR("%s: incomplete radix-tree file left by an interrupted create; remove it and retry", path);
Branch: 1 branch
BranchTrueFalseTotal
RDX_ERR("%s: incomplete radix-tree file left by an interrupted create; remove it and retry", path); 1 0 1
1192 1 munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
1193 }
1194 2 ▶ RDX_ERR("invalid radix-tree file"); munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
RDX_ERR("invalid radix-tree file"); munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL; 2 0 2
1195 }
1196 4 ▶ if (__atomic_load_n(&((RdxHeader *)base)->sealed, __ATOMIC_ACQUIRE)) {
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&((RdxHeader *)base)->sealed, __ATOMIC_ACQUIRE)) { 1 3 4
1197 1 ▶ RDX_ERR("%s is frozen (read-only); open it with new_readonly", path);
Branch: 1 branch
BranchTrueFalseTotal
RDX_ERR("%s is frozen (read-only); open it with new_readonly", path); 1 0 1
1198 1 munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
1199 }
1200 3 flock(fd, LOCK_UN); close(fd);
1201 3 return rdx_setup(base, map_size, path, -1, errbuf);
1202 }
1203 }
1204 26 rdx_init_header(base, node_cap, arena_cap, total);
1205 26 ▶ if (fd >= 0) { flock(fd, LOCK_UN); close(fd); }
Branch: 1 branch
BranchTrueFalseTotal
if (fd >= 0) { flock(fd, LOCK_UN); close(fd); } 9 17 26
1206 26 return rdx_setup(base, map_size, path, -1, errbuf);
1207 }
1208  
1209 3 static RdxHandle *rdx_create_memfd(const char *name, uint64_t node_cap_in, uint64_t arena_cap_in, char *errbuf) {
1210 3 ▶ if (!rdx_validate_create_args(node_cap_in, arena_cap_in, errbuf)) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!rdx_validate_create_args(node_cap_in, arena_cap_in, errbuf)) return NULL; 1 2 3
1211 2 uint32_t node_cap = (uint32_t)node_cap_in;
1212 2 uint32_t arena_cap = (uint32_t)arena_cap_in;
1213  
1214 2 uint64_t total = rdx_total_size(node_cap, arena_cap);
1215 2 ▶ int fd = memfd_create(name ? name : "radix", MFD_CLOEXEC | MFD_ALLOW_SEALING);
Branch: 1 branch
BranchTrueFalseTotal
int fd = memfd_create(name ? name : "radix", MFD_CLOEXEC | MFD_ALLOW_SEALING); 1 1 2
1216 2 ▶ if (fd < 0) { RDX_ERR("memfd_create: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fd < 0) { RDX_ERR("memfd_create: %s", strerror(errno)); return NULL; } 0 2 2
if (fd < 0) { RDX_ERR("memfd_create: %s", strerror(errno)); return NULL; } 0 0 0
1217 2 ▶ if (ftruncate(fd, (off_t)total) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (ftruncate(fd, (off_t)total) < 0) { 0 2 2
1218 0 ▶ RDX_ERR("ftruncate: %s", strerror(errno)); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
RDX_ERR("ftruncate: %s", strerror(errno)); close(fd); return NULL; 0 0 0
1219 }
1220 2 ▶ if (rdx_reserve(fd, total) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (rdx_reserve(fd, total) < 0) { 0 2 2
1221 0 ▶ RDX_ERR("memfd: cannot reserve %llu bytes: %s", (unsigned long long)total, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
RDX_ERR("memfd: cannot reserve %llu bytes: %s", (unsigned long long)total, strerror(errno)); 0 0 0
1222 0 close(fd); return NULL;
1223 }
1224 2 (void)fcntl(fd, F_ADD_SEALS, F_SEAL_SHRINK | F_SEAL_GROW);
1225 2 void *base = mmap(NULL, (size_t)total, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
1226 2 ▶ if (base == MAP_FAILED) { RDX_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { RDX_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; } 0 2 2
if (base == MAP_FAILED) { RDX_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; } 0 0 0
1227 2 rdx_init_header(base, node_cap, arena_cap, total);
1228 2 return rdx_setup(base, (size_t)total, NULL, fd, errbuf);
1229 }
1230  
1231 2 static RdxHandle *rdx_open_fd(int fd, char *errbuf) {
1232 2 ▶ if (errbuf) errbuf[0] = '\0';
Branch: 1 branch
BranchTrueFalseTotal
if (errbuf) errbuf[0] = '\0'; 2 0 2
1233 struct stat st;
1234 2 ▶ if (fstat(fd, &st) < 0) { RDX_ERR("fstat: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fstat(fd, &st) < 0) { RDX_ERR("fstat: %s", strerror(errno)); return NULL; } 0 2 2
if (fstat(fd, &st) < 0) { RDX_ERR("fstat: %s", strerror(errno)); return NULL; } 0 0 0
1235 2 ▶ if ((uint64_t)st.st_size < sizeof(RdxHeader)) { RDX_ERR("too small"); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if ((uint64_t)st.st_size < sizeof(RdxHeader)) { RDX_ERR("too small"); return NULL; } 1 1 2
if ((uint64_t)st.st_size < sizeof(RdxHeader)) { RDX_ERR("too small"); return NULL; } 1 0 1
1236 /* before mmap: a creator may truncate the file until it has set magic */
1237 uint32_t magic;
1238 1 ▶ if (pread(fd, &magic, sizeof magic, offsetof(RdxHeader, magic)) != (ssize_t)sizeof magic || magic != RDX_MAGIC) {
Branch: 2 branches
BranchTrueFalseTotal
if (pread(fd, &magic, sizeof magic, offsetof(RdxHeader, magic)) != (ssize_t)sizeof magic || magic != RDX_MAGIC) { 1 0 1
if (pread(fd, &magic, sizeof magic, offsetof(RdxHeader, magic)) != (ssize_t)sizeof magic || magic != RDX_MAGIC) { 0 1 1
1239 0 ▶ RDX_ERR("invalid radix-tree table"); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
RDX_ERR("invalid radix-tree table"); return NULL; 0 0 0
1240 }
1241 1 size_t ms = (size_t)st.st_size;
1242 1 void *base = mmap(NULL, ms, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
1243 1 ▶ if (base == MAP_FAILED) { RDX_ERR("mmap: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { RDX_ERR("mmap: %s", strerror(errno)); return NULL; } 0 1 1
if (base == MAP_FAILED) { RDX_ERR("mmap: %s", strerror(errno)); return NULL; } 0 0 0
1244 1 ▶ if (!rdx_validate_header((RdxHeader *)base, (uint64_t)st.st_size)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!rdx_validate_header((RdxHeader *)base, (uint64_t)st.st_size)) { 0 1 1
1245 0 ▶ RDX_ERR("invalid radix-tree table"); munmap(base, ms); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
RDX_ERR("invalid radix-tree table"); munmap(base, ms); return NULL; 0 0 0
1246 }
1247 1 ▶ if (__atomic_load_n(&((RdxHeader *)base)->sealed, __ATOMIC_ACQUIRE)) {
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&((RdxHeader *)base)->sealed, __ATOMIC_ACQUIRE)) { 0 1 1
1248 0 ▶ RDX_ERR("this radix tree is frozen (read-only); open it with new_readonly");
Branch: 1 branch
BranchTrueFalseTotal
RDX_ERR("this radix tree is frozen (read-only); open it with new_readonly"); 0 0 0
1249 0 munmap(base, ms); return NULL;
1250 }
1251 1 int myfd = fcntl(fd, F_DUPFD_CLOEXEC, 0);
1252 1 ▶ if (myfd < 0) { RDX_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (myfd < 0) { RDX_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; } 0 1 1
if (myfd < 0) { RDX_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; } 0 0 0
1253 1 return rdx_setup(base, ms, NULL, myfd, errbuf);
1254 }
1255  
1256 36 static void rdx_destroy(RdxHandle *h) {
1257 36 ▶ if (!h) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!h) return; 0 36 36
1258 /* Release our reader slot on clean teardown (else short-lived-reader churn
1259 * exhausts the slot table); skip if a read lock is still held (rdepth>0). */
1260 36 ▶ 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 && 36 0 36
if (h->reader_slots && h->my_slot_idx != UINT32_MAX && h->cached_pid && 27 9 36
if (h->reader_slots && h->my_slot_idx != UINT32_MAX && h->cached_pid && 27 0 27
1261 27 ▶ h->cached_fork_gen == __atomic_load_n(&rdx_fork_gen, __ATOMIC_RELAXED) &&
Branch: 1 branch
BranchTrueFalseTotal
h->cached_fork_gen == __atomic_load_n(&rdx_fork_gen, __ATOMIC_RELAXED) && 27 0 27
1262 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
1263 /* Clear our occ bit BEFORE freeing the slot: we still own the pid so no
1264 * claimant can take the slot mid-clear, and rdepth==0 so no writer needs
1265 * to see us. (A crash skips this -> the bit is reclaimed lazily by a
1266 * writer scan / re-claim, same as the pid.) */
1267 27 rdx_occ_clear(h, h->my_slot_idx);
1268 27 uint32_t expected = h->cached_pid;
1269 27 __atomic_compare_exchange_n(&h->reader_slots[h->my_slot_idx].pid,
1270 &expected, 0, 0, __ATOMIC_RELEASE, __ATOMIC_RELAXED);
1271 }
1272 36 ▶ if (h->backing_fd >= 0) close(h->backing_fd);
Branch: 1 branch
BranchTrueFalseTotal
if (h->backing_fd >= 0) close(h->backing_fd); 3 33 36
1273 36 ▶ if (h->base) munmap(h->base, h->mmap_size);
Branch: 1 branch
BranchTrueFalseTotal
if (h->base) munmap(h->base, h->mmap_size); 36 0 36
1274 36 free(h->unlink_path);
1275 36 free(h->path);
1276 36 free(h);
1277 }
1278  
1279 3 static inline int rdx_msync(RdxHandle *h) {
1280 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
1281 3 return msync(h->base, h->mmap_size, MS_SYNC);
1282 }
1283  
1284 /* Open a FROZEN (sealed) file read-only: O_RDONLY + PROT_READ, no lock ever.
1285 * A sealed file is immutable and no read path writes the mapping, so queries
1286 * take no reader-slot / rwlock traffic and any number of processes can share
1287 * one PROT_READ mapping (same architecture; the magic rejects a wrong-endian
1288 * file). */
1289 5 static RdxHandle *rdx_open_readonly(const char *path, char *errbuf) {
1290 5 ▶ if (errbuf) errbuf[0] = '\0';
Branch: 1 branch
BranchTrueFalseTotal
if (errbuf) errbuf[0] = '\0'; 5 0 5
1291 5 int fd = open(path, O_RDONLY|O_NOFOLLOW|O_CLOEXEC);
1292 5 ▶ if (fd < 0) { RDX_ERR("open %s: %s", path, strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fd < 0) { RDX_ERR("open %s: %s", path, strerror(errno)); return NULL; } 1 4 5
if (fd < 0) { RDX_ERR("open %s: %s", path, strerror(errno)); return NULL; } 1 0 1
1293 struct stat st;
1294 4 ▶ if (fstat(fd, &st) < 0) { RDX_ERR("fstat %s: %s", path, strerror(errno)); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fstat(fd, &st) < 0) { RDX_ERR("fstat %s: %s", path, strerror(errno)); close(fd); return NULL; } 0 4 4
if (fstat(fd, &st) < 0) { RDX_ERR("fstat %s: %s", path, strerror(errno)); close(fd); return NULL; } 0 0 0
1295 4 ▶ if ((uint64_t)st.st_size < sizeof(RdxHeader)) { RDX_ERR("%s: file too small", path); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if ((uint64_t)st.st_size < sizeof(RdxHeader)) { RDX_ERR("%s: file too small", path); close(fd); return NULL; } 0 4 4
if ((uint64_t)st.st_size < sizeof(RdxHeader)) { RDX_ERR("%s: file too small", path); close(fd); return NULL; } 0 0 0
1296 /* before mmap: a creator may truncate the file until it has set magic */
1297 uint32_t magic;
1298 4 ▶ if (pread(fd, &magic, sizeof magic, offsetof(RdxHeader, magic)) != (ssize_t)sizeof magic || magic != RDX_MAGIC) {
Branch: 2 branches
BranchTrueFalseTotal
if (pread(fd, &magic, sizeof magic, offsetof(RdxHeader, magic)) != (ssize_t)sizeof magic || magic != RDX_MAGIC) { 4 0 4
if (pread(fd, &magic, sizeof magic, offsetof(RdxHeader, magic)) != (ssize_t)sizeof magic || magic != RDX_MAGIC) { 0 4 4
1299 0 ▶ RDX_ERR("%s: invalid radix-tree file", path); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
RDX_ERR("%s: invalid radix-tree file", path); close(fd); return NULL; 0 0 0
1300 }
1301 4 size_t ms = (size_t)st.st_size;
1302 4 void *base = mmap(NULL, ms, PROT_READ, MAP_SHARED, fd, 0);
1303 4 close(fd); /* the mapping keeps the file; a read-only view needs no fd (no msync/ftruncate) */
1304 4 ▶ if (base == MAP_FAILED) { RDX_ERR("mmap %s: %s", path, strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { RDX_ERR("mmap %s: %s", path, strerror(errno)); return NULL; } 0 4 4
if (base == MAP_FAILED) { RDX_ERR("mmap %s: %s", path, strerror(errno)); return NULL; } 0 0 0
1305 4 ▶ if (!rdx_validate_header((RdxHeader *)base, (uint64_t)st.st_size)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!rdx_validate_header((RdxHeader *)base, (uint64_t)st.st_size)) { 0 4 4
1306 0 ▶ RDX_ERR("%s: invalid radix-tree file", path); munmap(base, ms); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
RDX_ERR("%s: invalid radix-tree file", path); munmap(base, ms); return NULL; 0 0 0
1307 }
1308 4 ▶ if (!__atomic_load_n(&((RdxHeader *)base)->sealed, __ATOMIC_ACQUIRE)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!__atomic_load_n(&((RdxHeader *)base)->sealed, __ATOMIC_ACQUIRE)) { 1 3 4
1309 1 ▶ RDX_ERR("%s is not frozen: call ->freeze on the producer before opening read-only", path);
Branch: 1 branch
BranchTrueFalseTotal
RDX_ERR("%s is not frozen: call ->freeze on the producer before opening read-only", path); 1 0 1
1310 1 munmap(base, ms); return NULL;
1311 }
1312 3 RdxHandle *h = rdx_setup(base, ms, path, -1, errbuf); /* munmaps on OOM */
1313 3 ▶ if (!h) { RDX_ERR("out of memory"); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (!h) { RDX_ERR("out of memory"); return NULL; } 0 3 3
if (!h) { RDX_ERR("out of memory"); return NULL; } 0 0 0
1314 3 h->readonly = 1;
1315 3 return h;
1316 }
1317  
1318 /* Seal a tree: make it permanently immutable so it can be shipped and opened
1319 * read-only. Takes the write lock so no insert/delete is in flight,
1320 * publishes the seal, then flushes it (file/memfd-backed). Afterwards every
1321 * mutator croaks and a read-write reopen is refused. */
1322 1 static int rdx_freeze(RdxHandle *h) {
1323 1 rdx_rwlock_wrlock(h);
1324 1 __atomic_store_n(&h->hdr->sealed, 1, __ATOMIC_RELEASE);
1325 1 rdx_rwlock_wrunlock(h);
1326 1 ▶ if (h->path || h->backing_fd >= 0) return rdx_msync(h); /* durability for file/memfd-backed */
Branch: 2 branches
BranchTrueFalseTotal
if (h->path || h->backing_fd >= 0) return rdx_msync(h); /* durability for file/memfd-backed */ 0 1 1
if (h->path || h->backing_fd >= 0) return rdx_msync(h); /* durability for file/memfd-backed */ 0 0 0
1327 0 return 0; /* anonymous: the seal lives in shared memory (visible to forks); nothing to flush */
1328 }
1329  
1330 #endif /* RADIX_H */
« blib/lib/Data/RadixTree/Shared.pm ↑ Summary Shared.xs »