kdtree.h

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