minhash.h

filter: Statementstmt 71.3% 348 / 488 Branchbran 45.3% 186 / 410 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 59.4% 534 / 898 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« xxhash.h ↑ Summary Shared.xs »
1 /*
2 * minhash.h -- Shared-memory MinHash sketch for Linux
3 *
4 * Jaccard-similarity estimation: keeps k "minimum hash" registers so that two
5 * sketches, compared register by register, estimate the Jaccard similarity of
6 * their underlying sets by the fraction of registers that agree, in a fixed
7 * amount of memory. Each item is hashed once (XXH3-64) and mixed with each
8 * register's index, so the k registers behave like k independent min-hashes and
9 * every register keeps the minimum value it has ever seen. The registers live
10 * in a shared mapping so several processes update one sketch; a write-preferring
11 * futex rwlock with reader-slot dead-process recovery guards mutation. Two
12 * sketches of equal size can be merged (element-wise minimum -> the sketch of
13 * the union of the two sets).
14 *
15 * Layout: Header -> reader_slots[1024] -> occ bitmap -> registers[k*8]
16 */
17  
18 #ifndef MNH_H
19 #define MNH_H
20  
21 #include <stddef.h>
22 #include <stdint.h>
23 #include <stdlib.h>
24 #include <string.h>
25 #include <unistd.h>
26 #include <fcntl.h>
27 #include <errno.h>
28 #include <time.h>
29 #include <limits.h>
30 #include <signal.h>
31 #include <stdio.h>
32 #include <math.h>
33 #include <sys/mman.h>
34 #include <sys/stat.h>
35 #include <sys/file.h>
36 #include <sys/syscall.h>
37 #include <linux/futex.h>
38 #include <pthread.h>
39  
40 #define XXH_INLINE_ALL
41 #include "xxhash.h"
42  
43 #if defined(__BYTE_ORDER__) && __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
44 #error "minhash.h: requires little-endian architecture"
45 #endif
46  
47  
48 /* ================================================================
49 * Constants
50 * ================================================================ */
51  
52 #define MNH_MAGIC 0x484E494DU /* MinHash */
53 #define MNH_VERSION 2 /* 2: added the occupancy bitmap region (layout change) */
54 #define MNH_ERR_BUFLEN (PATH_MAX + 256)
55 #ifndef MNH_READER_SLOTS
56 #define MNH_READER_SLOTS 1024 /* max concurrent reader processes for dead-process recovery */
57 #endif
58 /* Occupancy bitmap: one bit per reader slot, set when a process claims a slot and
59 * cleared on clean release. A writer scans these MNH_OCC_WORDS words to visit
60 * only OCCUPIED slots (O(words + live readers)) instead of all MNH_READER_SLOTS. */
61 #define MNH_OCC_WORDS (((MNH_READER_SLOTS) + 63) / 64) /* 16 for 1024 slots */
62 #define MNH_OCC_BYTES ((uint64_t)MNH_OCC_WORDS * 8) /* 128 bytes */
63 #define MNH_MIN_K 1
64 #define MNH_MAX_K 0x1000000ULL /* 2^24 registers cap */
65  
66 #define MNH_ERR(fmt, ...) do { if (errbuf) snprintf(errbuf, MNH_ERR_BUFLEN, fmt, ##__VA_ARGS__); } while (0)
67  
68 /* ================================================================
69 * Structs
70 * ================================================================ */
71  
72 /* Per-process slot for dead-process recovery. In the reader-slots-only rwlock a
73 * reader's ENTIRE contribution to the shared lock is `rdepth` in its OWN slot --
74 * there is no separate shared reader counter to fall out of sync with it -- so a
75 * dead reader's contribution is exactly this one word, which a draining writer
76 * neutralises by clearing the slot's pid (the scan then ignores the slot). No
77 * orphaned counter can exist, so there is no quiescent force-reset and sustained
78 * readers cannot starve a writer. _rsv1/_rsv2 are kept only to preserve the
79 * 16-byte slot size across the already-released builds. */
80 typedef struct {
81 uint32_t pid; /* 0 = unclaimed */
82 uint32_t rdepth; /* read-locks THIS process currently holds (recursion-safe) */
83 uint32_t _rsv1; /* reserved (was waiters_parked); unused, kept for layout size */
84 uint32_t _rsv2; /* reserved (was writers_parked); unused, kept for layout size */
85 } MnhReaderSlot;
86  
87 struct MnhHeader {
88 uint32_t magic, version; /* 0,4 */
89 uint32_t _pad0; /* 8 */
90 uint32_t _pad1; /* 12 */
91 uint64_t k; /* 16 number of min-hash registers */
92 uint64_t _reserved0; /* 24 */
93 uint64_t capacity; /* 32 == k (family stats parity) */
94 uint64_t _reserved1; /* 40 */
95 uint64_t total_size; /* 48 */
96 uint64_t reader_slots_off; /* 56 */
97 uint64_t registers_off; /* 64 */
98 uint32_t wlock; /* 72 WRITER word ONLY: 0 (free) or WRITER_BIT|pid. NOT a reader count. */
99 uint32_t rwait; /* 76 parked-waiter hint (readers+writers blocked on wlock); over-count-safe */
100 uint32_t drain_seq; /* 80 futex bumped by a reader releasing under a draining writer (wakes it) */
101 uint32_t slotless_rdepth; /* readers holding with no reader-slot (documented residual) */
102 uint64_t stat_ops; /* 88 */
103 uint8_t sealed; /* 96 0 = mutable, 1 = frozen (read-only; lock-free reads) */
104 uint8_t _pad[159]; /* 97..255 */
105 };
106 typedef struct MnhHeader MnhHeader;
107  
108 _Static_assert(sizeof(MnhHeader) == 256, "MnhHeader must be 256 bytes");
109  
110 /* ---- Process-local handle ---- */
111  
112 typedef struct MnhHandle {
113 MnhHeader *hdr;
114 MnhReaderSlot *reader_slots; /* MNH_READER_SLOTS entries */
115 uint64_t *occ; /* MNH_OCC_WORDS-word slot-occupancy bitmap (trusted layout offset) */
116 void *base; /* mmap base */
117 uint64_t registers_off; /* validated register-array offset, cached: never re-read from the peer-writable header */
118 size_t mmap_size;
119 char *path; /* backing file path (strdup'd) */
120 int backing_fd; /* memfd or reopened-fd to close on destroy, -1 for file/anon */
121 uint32_t my_slot_idx; /* UINT32_MAX if all slots taken (no recovery for this handle) */
122 uint32_t cached_pid; /* getpid() cached at last slot claim */
123 uint32_t cached_fork_gen; /* mnh_fork_gen value at last slot claim */
124 uint32_t slotless_held; /* read-locks this process holds with no reader-slot */
125 int readonly; /* 1 = frozen O_RDONLY/PROT_READ view: lock-free reads, mutation croaks */
126 } MnhHandle;
127  
128 /* ================================================================
129 * Futex-based write-preferring read-write lock (reader-slots-only)
130 * with dead-process recovery
131 *
132 * The reader count is NOT stored in a shared counter. It is DISTRIBUTED across
133 * per-process reader slots: each slot's `rdepth` is that process's entire
134 * contribution to the lock. A reader publishes its presence in its own slot and
135 * then re-checks the writer word; a writer publishes the writer word and then
136 * scans every slot until all live readers' rdepth reach 0. Sequentially-
137 * consistent store+load on each side (a Dekker handshake) gives mutual exclusion.
138 *
139 * Because a reader's whole contribution is ONE atomic word owned by ONE process,
140 * a crashed reader is recovered by clearing that one slot (CAS its pid to 0) --
141 * there is no second counter to strand, no orphaned +1, and therefore no
142 * quiescent force-reset. A reader killed anywhere in rdlock/rdunlock leaves at
143 * most `rdepth>0` in its dead slot, which the draining writer clears directly, so
144 * sustained read traffic can never starve a writer. Write-preference is inherent
145 * in the gate (new readers see wlock!=0 and yield), so there is no reader-count
146 * yield hack.
147 * ================================================================ */
148  
149 #define MNH_RWLOCK_SPIN_LIMIT 32
150 #define MNH_LOCK_TIMEOUT_SEC 2 /* FUTEX_WAIT timeout for stale-lock detection / drain re-scan */
151  
152 0 static inline void mnh_rwlock_spin_pause(void) {
153 #if defined(__x86_64__) || defined(__i386__)
154 0 __asm__ volatile("pause" ::: "memory");
155 #elif defined(__aarch64__)
156 __asm__ volatile("yield" ::: "memory");
157 #else
158 __asm__ volatile("" ::: "memory");
159 #endif
160 0 }
161  
162 /* Writer word encoding: WRITER_BIT|pid when write-locked, 0 when free. */
163 #define MNH_RWLOCK_WRITER_BIT 0x80000000U
164 #define MNH_RWLOCK_PID_MASK 0x7FFFFFFFU
165 #define MNH_RWLOCK_WR(pid) (MNH_RWLOCK_WRITER_BIT | ((uint32_t)(pid) & MNH_RWLOCK_PID_MASK))
166  
167 /* A zombie (dead but not yet reaped) still answers kill(pid,0) as alive, so a
168 * process that crashed while holding the lock and lingers unreaped would never
169 * be recovered. Treat /proc/<pid>/stat state 'Z' as dead. Linux-only (as is
170 * this module); if /proc is unreadable we fall back to "alive" (safe: we never
171 * force-recover a possibly-live holder). */
172 0 static inline int mnh_pid_is_zombie(uint32_t pid) {
173 char path[32], buf[256];
174 0 snprintf(path, sizeof(path), "/proc/%u/stat", (unsigned)pid);
175 0 int fd = open(path, O_RDONLY | O_CLOEXEC);
176 0 ▶ if (fd < 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (fd < 0) return 0; 0 0 0
177 0 ssize_t n = read(fd, buf, sizeof(buf) - 1);
178 0 close(fd);
179 0 ▶ if (n <= 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (n <= 0) return 0; 0 0 0
180 0 buf[n] = '\0';
181 /* "pid (comm) state ..."; comm may contain ')', so scan to the last one. */
182 0 char *rp = strrchr(buf, ')');
183 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
184 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
185 }
186 /* 1 if alive or unknown, 0 if definitely dead. Cannot detect PID reuse: a
187 * recycled PID reports "alive" and the slot is not reclaimed until that
188 * process exits. See "Crash Safety" in the POD. */
189 0 static inline int mnh_pid_alive(uint32_t pid) {
190 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
191 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
192 0 return !mnh_pid_is_zombie(pid); /* kill() also succeeds for a zombie -> treat as dead */
193 }
194  
195 /* Force-recover a stale WRITE lock left by a dead writer (held or mid-drain).
196 * CAS to OUR pid to hold the lock while fixing shared state, then release.
197 * Using our pid (not a bare WRITER_BIT sentinel) means a subsequent recovering
198 * process can detect and re-recover if we crash mid-recovery. */
199 0 static inline void mnh_recover_stale_lock(MnhHandle *h, uint32_t observed_wlock) {
200 0 MnhHeader *hdr = h->hdr;
201 0 uint32_t mypid = MNH_RWLOCK_WR((uint32_t)getpid());
202 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
203 mypid, 0, __ATOMIC_ACQUIRE, __ATOMIC_RELAXED))
204 0 return;
205 /* We now hold the write lock as mypid. No additional shared state needs
206 * repair here (this module has no seqlock); just release the lock. */
207 0 __atomic_store_n(&hdr->wlock, 0, __ATOMIC_SEQ_CST);
208 0 ▶ if (__atomic_load_n(&hdr->rwait, __ATOMIC_SEQ_CST) > 0)
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&hdr->rwait, __ATOMIC_SEQ_CST) > 0) 0 0 0
209 0 syscall(SYS_futex, &hdr->wlock, FUTEX_WAKE, INT_MAX, NULL, NULL, 0);
210 }
211  
212 static const struct timespec mnh_lock_timeout = { MNH_LOCK_TIMEOUT_SEC, 0 };
213  
214 /* Process-global fork-generation counter. Incremented in the pthread_atfork
215 * child callback so every open handle detects a fork transition on the next
216 * lock call without paying a getpid() syscall on the hot path. */
217 static uint32_t mnh_fork_gen = 1;
218 static pthread_once_t mnh_atfork_once = PTHREAD_ONCE_INIT;
219 0 static void mnh_on_fork_child(void) {
220 0 __atomic_add_fetch(&mnh_fork_gen, 1, __ATOMIC_RELAXED);
221 0 }
222 4 static void mnh_atfork_init(void) {
223 4 pthread_atfork(NULL, NULL, mnh_on_fork_child);
224 4 }
225  
226 /* Occupancy bitmap: set a slot's bit when it is claimed, clear it on clean
227 * release. SEQ_CST so a set bit is ordered before the slot's rdepth can go
228 * non-zero (bit set in claim, which precedes any rdlock), letting a writer's
229 * SEQ_CST bitmap scan never miss a slot a committed reader holds. */
230 47 static inline void mnh_occ_set(MnhHandle *h, uint32_t s) {
231 47 __atomic_fetch_or(&h->occ[s >> 6], (uint64_t)1 << (s & 63), __ATOMIC_SEQ_CST);
232 47 }
233 47 static inline void mnh_occ_clear(MnhHandle *h, uint32_t s) {
234 47 __atomic_fetch_and(&h->occ[s >> 6], ~((uint64_t)1 << (s & 63)), __ATOMIC_SEQ_CST);
235 47 }
236  
237 /* Ensure this process owns a reader slot. Called from the lock helpers so
238 * that fork()'d children pick up their own slot lazily instead of sharing
239 * the parent's. Hot-path is a single relaxed load + compare; only on a
240 * fork-generation mismatch do we touch getpid() and scan slots. */
241 17078 static inline void mnh_claim_reader_slot(MnhHandle *h) {
242 17078 uint32_t cur_gen = __atomic_load_n(&mnh_fork_gen, __ATOMIC_RELAXED);
243 17078 ▶ 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)) 17031 47 17078
if (__builtin_expect(cur_gen == h->cached_fork_gen && h->my_slot_idx != UINT32_MAX, 1)) 17031 0 17031
244 17031 return;
245 /* Cold path -- register the atfork hook once per process, then claim. */
246 47 pthread_once(&mnh_atfork_once, mnh_atfork_init);
247 /* Re-read after pthread_once: mnh_on_fork_child may have bumped it. */
248 47 cur_gen = __atomic_load_n(&mnh_fork_gen, __ATOMIC_RELAXED);
249 47 uint32_t now_pid = (uint32_t)getpid();
250 47 h->cached_pid = now_pid;
251 47 ▶ 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 */ 47 0 47
252 47 h->cached_fork_gen = cur_gen;
253 47 h->my_slot_idx = UINT32_MAX;
254 47 uint32_t start = now_pid % MNH_READER_SLOTS;
255 /* Pass 1: take a free slot. */
256 51 ▶ for (uint32_t i = 0; i < MNH_READER_SLOTS; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t i = 0; i < MNH_READER_SLOTS; i++) { 51 0 51
257 51 uint32_t s = (start + i) % MNH_READER_SLOTS;
258 51 uint32_t expected = 0;
259 51 ▶ if (__atomic_compare_exchange_n(&h->reader_slots[s].pid,
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_compare_exchange_n(&h->reader_slots[s].pid, 47 4 51
260 &expected, now_pid, 0,
261 __ATOMIC_ACQUIRE, __ATOMIC_RELAXED)) {
262 /* Fresh owner holds no read locks yet; clear any stale rdepth left by
263 * a dead predecessor (its contribution is dropped as we take over). */
264 47 __atomic_store_n(&h->reader_slots[s].rdepth, 0, __ATOMIC_RELAXED);
265 47 mnh_occ_set(h, s); /* mark occupied BEFORE any rdlock can bump rdepth */
266 47 h->my_slot_idx = s;
267 47 return;
268 }
269 }
270 /* Pass 2: no free slot -- reclaim one whose owner is dead. Safe to take even
271 * if its rdepth>0: clearing pid drops the dead reader's entire contribution
272 * (a writer scan ignores rdepth when pid==0) and we reset rdepth to 0 as we
273 * claim it. */
274 0 ▶ for (uint32_t i = 0; i < MNH_READER_SLOTS; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t i = 0; i < MNH_READER_SLOTS; i++) { 0 0 0
275 0 uint32_t dpid = __atomic_load_n(&h->reader_slots[i].pid, __ATOMIC_ACQUIRE);
276 0 ▶ if (dpid == 0 || dpid == now_pid || mnh_pid_alive(dpid)) continue;
Branch: 3 branches
BranchTrueFalseTotal
if (dpid == 0 || dpid == now_pid || mnh_pid_alive(dpid)) continue; 0 0 0
if (dpid == 0 || dpid == now_pid || mnh_pid_alive(dpid)) continue; 0 0 0
if (dpid == 0 || dpid == now_pid || mnh_pid_alive(dpid)) continue; 0 0 0
277 0 uint32_t expected = dpid;
278 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
279 __ATOMIC_ACQUIRE, __ATOMIC_RELAXED)) {
280 0 __atomic_store_n(&h->reader_slots[i].rdepth, 0, __ATOMIC_RELAXED);
281 0 mnh_occ_set(h, i);
282 0 h->my_slot_idx = i;
283 0 return;
284 }
285 }
286 /* Table full -- leave my_slot_idx = UINT32_MAX so this handle takes the
287 * slotless path (lock still works; recovery of THIS reader's death is the
288 * documented slotless limitation). */
289 }
290  
291 /* Inspect the writer word after a futex-wait timeout. If a dead writer holds
292 * it, force-recover. Dead READERS need no action here: only a writer that owns
293 * wlock drains readers, and it clears dead readers inline in its own scan. */
294 0 static inline void mnh_recover_after_timeout(MnhHandle *h) {
295 0 uint32_t val = __atomic_load_n(&h->hdr->wlock, __ATOMIC_RELAXED);
296 0 ▶ if (val >= MNH_RWLOCK_WRITER_BIT) {
Branch: 1 branch
BranchTrueFalseTotal
if (val >= MNH_RWLOCK_WRITER_BIT) { 0 0 0
297 0 uint32_t pid = val & MNH_RWLOCK_PID_MASK;
298 0 ▶ if (!mnh_pid_alive(pid))
Branch: 1 branch
BranchTrueFalseTotal
if (!mnh_pid_alive(pid)) 0 0 0
299 0 mnh_recover_stale_lock(h, val);
300 }
301 0 }
302  
303 /* Bump/drop the parked-waiter hint. Both readers (blocked at the gate) and
304 * writers (blocked acquiring wlock) wait on the wlock futex and use this, so
305 * wrunlock/recover know whether a FUTEX_WAKE is worth a syscall. A waiter
306 * SIGKILLed while parked leaves rwait over-counted -> at most a spurious wake
307 * (harmless); it can never under-count, so no wakeup is lost. */
308 0 static inline void mnh_park(MnhHandle *h) {
309 0 __atomic_add_fetch(&h->hdr->rwait, 1, __ATOMIC_SEQ_CST);
310 0 }
311 0 static inline void mnh_unpark(MnhHandle *h) {
312 0 __atomic_sub_fetch(&h->hdr->rwait, 1, __ATOMIC_RELAXED);
313 0 }
314  
315 /* Publish (inc) / retract (dec) this reader's presence -- its ENTIRE
316 * contribution to the lock. A slotted reader uses its slot's rdepth; a reader
317 * that could not claim a slot uses the global slotless_rdepth. inc() is SEQ_CST
318 * so the wlock re-check that follows it in rdlock forms a Dekker handshake with
319 * the writer's SEQ_CST wlock-store + rdepth-scan. leave() peels slotless first
320 * so a slot claimed mid-hold cannot misattribute the decrement. */
321 648 static inline void mnh_rdepth_inc(MnhHandle *h) {
322 648 ▶ if (h->my_slot_idx != UINT32_MAX) {
Branch: 1 branch
BranchTrueFalseTotal
if (h->my_slot_idx != UINT32_MAX) { 648 0 648
323 648 __atomic_add_fetch(&h->reader_slots[h->my_slot_idx].rdepth, 1, __ATOMIC_SEQ_CST);
324 } else {
325 0 __atomic_add_fetch(&h->hdr->slotless_rdepth, 1, __ATOMIC_SEQ_CST);
326 0 h->slotless_held++;
327 }
328 648 }
329 648 static inline void mnh_rdepth_dec(MnhHandle *h) {
330 648 ▶ if (h->slotless_held > 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (h->slotless_held > 0) { 0 648 648
331 0 h->slotless_held--;
332 0 __atomic_sub_fetch(&h->hdr->slotless_rdepth, 1, __ATOMIC_SEQ_CST);
333 648 ▶ } else if (h->my_slot_idx != UINT32_MAX) {
Branch: 1 branch
BranchTrueFalseTotal
} else if (h->my_slot_idx != UINT32_MAX) { 648 0 648
334 648 __atomic_sub_fetch(&h->reader_slots[h->my_slot_idx].rdepth, 1, __ATOMIC_SEQ_CST);
335 }
336 648 }
337  
338 /* Wake a writer that may be draining readers (it waits on drain_seq). Called
339 * after every rdepth decrement so a released read lock lets the writer re-scan
340 * promptly instead of waiting out its timeout. */
341 648 static inline void mnh_reader_wake_drain(MnhHandle *h) {
342 648 ▶ if (__atomic_load_n(&h->hdr->wlock, __ATOMIC_SEQ_CST) != 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&h->hdr->wlock, __ATOMIC_SEQ_CST) != 0) { 0 648 648
343 0 __atomic_add_fetch(&h->hdr->drain_seq, 1, __ATOMIC_RELEASE);
344 0 syscall(SYS_futex, &h->hdr->drain_seq, FUTEX_WAKE, 1, NULL, NULL, 0);
345 }
346 648 }
347  
348 648 static inline void mnh_rwlock_rdlock(MnhHandle *h) {
349 648 mnh_claim_reader_slot(h);
350 648 MnhHeader *hdr = h->hdr;
351 648 for (int spin = 0; ; spin++) {
352 648 uint32_t cur = __atomic_load_n(&hdr->wlock, __ATOMIC_ACQUIRE);
353 648 ▶ if (cur == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (cur == 0) { 648 0 648
354 /* Optimistically take the read: publish rdepth, then re-check wlock.
355 * SEQ_CST inc + SEQ_CST load vs the writer's SEQ_CST wlock CAS +
356 * SEQ_CST rdepth scan: by the single total order of SEQ_CST ops the
357 * two sides cannot both miss each other, so we never hold
358 * concurrently with a writer. */
359 648 mnh_rdepth_inc(h);
360 648 ▶ if (__atomic_load_n(&hdr->wlock, __ATOMIC_SEQ_CST) == 0)
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&hdr->wlock, __ATOMIC_SEQ_CST) == 0) 648 0 648
361 648 return; /* no writer after our publish -> we hold the read lock */
362 /* A writer appeared during our publish -- yield to it (write-preferring). */
363 0 mnh_rdepth_dec(h);
364 0 mnh_reader_wake_drain(h); /* let the draining writer see rdepth drop */
365 0 spin = 0;
366 0 continue;
367 }
368 /* wlock != 0: a writer holds or is acquiring. Recover if it is dead. */
369 0 if (cur >= MNH_RWLOCK_WRITER_BIT &&
370 0 !mnh_pid_alive(cur & MNH_RWLOCK_PID_MASK)) {
371 0 mnh_recover_stale_lock(h, cur);
372 0 spin = 0;
373 0 continue;
374 }
375 0 ▶ if (__builtin_expect(spin < MNH_RWLOCK_SPIN_LIMIT, 1)) {
Branch: 1 branch
BranchTrueFalseTotal
if (__builtin_expect(spin < MNH_RWLOCK_SPIN_LIMIT, 1)) { 0 0 0
376 0 mnh_rwlock_spin_pause();
377 0 continue;
378 }
379 0 mnh_park(h);
380 0 cur = __atomic_load_n(&hdr->wlock, __ATOMIC_SEQ_CST);
381 0 ▶ if (cur != 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (cur != 0) { 0 0 0
382 0 long rc = syscall(SYS_futex, &hdr->wlock, FUTEX_WAIT, cur,
383 &mnh_lock_timeout, NULL, 0);
384 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
385 0 mnh_unpark(h);
386 0 mnh_recover_after_timeout(h);
387 0 spin = 0;
388 0 continue;
389 }
390 }
391 0 mnh_unpark(h);
392 0 spin = 0;
393 }
394 }
395  
396 648 static inline void mnh_rwlock_rdunlock(MnhHandle *h) {
397 648 mnh_rdepth_dec(h); /* RELEASE: drop our entire contribution */
398 648 mnh_reader_wake_drain(h); /* if a writer is draining, wake it to re-scan */
399 648 }
400  
401 16430 static inline void mnh_rwlock_wrlock(MnhHandle *h) {
402 16430 mnh_claim_reader_slot(h); /* refresh cached_pid across fork */
403 16430 MnhHeader *hdr = h->hdr;
404 /* Encode PID in the wlock word itself (0x80000000 | pid) to eliminate any
405 * crash window between acquiring the lock and storing the owner. */
406 16430 uint32_t mypid = MNH_RWLOCK_WR(h->cached_pid);
407 /* Phase 1: acquire the writer word (mutual exclusion among writers). */
408 16430 for (int spin = 0; ; spin++) {
409 16430 uint32_t expected = 0;
410 16430 ▶ if (__atomic_compare_exchange_n(&hdr->wlock, &expected, mypid,
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_compare_exchange_n(&hdr->wlock, &expected, mypid, 16430 0 16430
411 0, __ATOMIC_SEQ_CST, __ATOMIC_RELAXED))
412 16430 break;
413 /* Contended: expected now holds the current wlock value. */
414 0 if (expected >= MNH_RWLOCK_WRITER_BIT &&
415 0 !mnh_pid_alive(expected & MNH_RWLOCK_PID_MASK)) {
416 0 mnh_recover_stale_lock(h, expected);
417 0 spin = 0;
418 0 continue;
419 }
420 0 ▶ if (__builtin_expect(spin < MNH_RWLOCK_SPIN_LIMIT, 1)) {
Branch: 1 branch
BranchTrueFalseTotal
if (__builtin_expect(spin < MNH_RWLOCK_SPIN_LIMIT, 1)) { 0 0 0
421 0 mnh_rwlock_spin_pause();
422 0 continue;
423 }
424 0 mnh_park(h);
425 0 uint32_t cur = __atomic_load_n(&hdr->wlock, __ATOMIC_SEQ_CST);
426 0 ▶ if (cur != 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (cur != 0) { 0 0 0
427 0 long rc = syscall(SYS_futex, &hdr->wlock, FUTEX_WAIT, cur,
428 &mnh_lock_timeout, NULL, 0);
429 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
430 0 mnh_unpark(h);
431 0 mnh_recover_after_timeout(h);
432 0 spin = 0;
433 0 continue;
434 }
435 }
436 0 mnh_unpark(h);
437 0 spin = 0;
438 }
439 /* Phase 2: we own wlock, so no NEW reader can join (they see wlock!=0 and
440 * yield). Drain the readers that were already holding when we won the CAS.
441 * The SEQ_CST CAS above + the SEQ_CST rdepth loads below are the writer side
442 * of the Dekker handshake. */
443 0 for (;;) {
444 16430 uint32_t v = __atomic_load_n(&hdr->drain_seq, __ATOMIC_ACQUIRE); /* snapshot BEFORE scan */
445 16430 int busy = 0;
446 /* Visit only OCCUPIED slots via the occupancy bitmap (SEQ_CST: a committed
447 * reader's bit -- set in claim, before its rdepth++ -- is ordered before
448 * this scan, so no held slot is skipped). O(MNH_OCC_WORDS + live readers)
449 * instead of O(MNH_READER_SLOTS). */
450 279310 ▶ for (uint32_t w = 0; w < MNH_OCC_WORDS; w++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t w = 0; w < MNH_OCC_WORDS; w++) { 262880 16430 279310
451 262880 uint64_t word = __atomic_load_n(&h->occ[w], __ATOMIC_SEQ_CST);
452 279314 ▶ while (word) {
Branch: 1 branch
BranchTrueFalseTotal
while (word) { 16434 262880 279314
453 16434 uint32_t i = (w << 6) + (uint32_t)__builtin_ctzll(word);
454 16434 word &= word - 1; /* consume this bit (local copy) */
455 16434 uint32_t rd = __atomic_load_n(&h->reader_slots[i].rdepth, __ATOMIC_SEQ_CST);
456 16434 ▶ if (rd == 0) continue; /* occupied but not read-locking now */
Branch: 1 branch
BranchTrueFalseTotal
if (rd == 0) continue; /* occupied but not read-locking now */ 16434 0 16434
457 0 uint32_t pid = __atomic_load_n(&h->reader_slots[i].pid, __ATOMIC_ACQUIRE);
458 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
459 0 ▶ if (!mnh_pid_alive(pid)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!mnh_pid_alive(pid)) { 0 0 0
460 /* Dead reader: drop its pid so the slot no longer counts. Leave
461 * the occ bit set (harmless -- a later scan hits pid==0 and skips,
462 * a re-claim re-sets it) to avoid racing a concurrent claimant. */
463 0 uint32_t ep = pid;
464 0 __atomic_compare_exchange_n(&h->reader_slots[i].pid, &ep, 0,
465 0, __ATOMIC_ACQ_REL, __ATOMIC_RELAXED);
466 0 continue;
467 }
468 0 busy = 1; /* live reader still holding */
469 }
470 }
471 /* A live slotless reader keeps us waiting; a crashed slotless reader that
472 * cannot be attributed to a pid is the documented slotless limitation. */
473 16430 ▶ 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 16430 16430
474 0 busy = 1;
475 16430 ▶ if (!busy)
Branch: 1 branch
BranchTrueFalseTotal
if (!busy) 16430 0 16430
476 16430 return; /* exclusive: wlock held + every rdepth 0 */
477 /* Wait for a reader to release (drain_seq bump) or time out to re-scan
478 * (which reclaims any newly-dead slotted reader). */
479 0 syscall(SYS_futex, &hdr->drain_seq, FUTEX_WAIT, v, &mnh_lock_timeout, NULL, 0);
480 }
481 }
482  
483 16430 static inline void mnh_rwlock_wrunlock(MnhHandle *h) {
484 16430 MnhHeader *hdr = h->hdr;
485 /* Pair with park + gate re-check so neither side can miss the other. */
486 16430 __atomic_store_n(&hdr->wlock, 0, __ATOMIC_SEQ_CST);
487 16430 ▶ if (__atomic_load_n(&hdr->rwait, __ATOMIC_SEQ_CST) > 0)
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&hdr->rwait, __ATOMIC_SEQ_CST) > 0) 0 16430 16430
488 0 syscall(SYS_futex, &hdr->wlock, FUTEX_WAKE, INT_MAX, NULL, NULL, 0);
489 16430 }
490  
491 /* ================================================================
492 * Layout math + create / open / destroy
493 *
494 * Layout: Header -> reader_slots[1024] -> occ bitmap -> registers[k*8]
495 * ================================================================ */
496  
497 /* Single source of truth for the mmap region layout offsets:
498 * Header -> reader_slots[] -> occ bitmap -> registers[]. */
499 typedef struct { uint64_t reader_slots, occ, registers; } MnhLayout;
500  
501 186 static inline MnhLayout mnh_layout(void) {
502 MnhLayout L;
503 186 L.reader_slots = sizeof(MnhHeader);
504 186 L.occ = L.reader_slots + (uint64_t)MNH_READER_SLOTS * sizeof(MnhReaderSlot);
505 186 L.registers = L.occ + MNH_OCC_BYTES;
506 186 L.registers = (L.registers + 7) & ~(uint64_t)7; /* 8-byte align the uint64 registers */
507 186 return L;
508 }
509  
510 68 static inline uint64_t mnh_total_size(uint64_t k) {
511 68 MnhLayout L = mnh_layout();
512 68 return L.registers + k * sizeof(uint64_t);
513 }
514  
515 49 static inline void mnh_init_header(void *base, uint64_t k, uint64_t total) {
516 49 MnhLayout L = mnh_layout();
517 49 MnhHeader *hdr = (MnhHeader *)base;
518 /* zero the header + reader-slot region, then fill the registers with the
519 empty sentinel UINT64_MAX (a min-update replaces it with any real hash) */
520 49 memset(base, 0, (size_t)L.registers);
521 49 hdr->version = MNH_VERSION;
522 49 hdr->k = k;
523 49 hdr->capacity = k;
524 49 hdr->total_size = total;
525 49 hdr->reader_slots_off = L.reader_slots;
526 49 hdr->registers_off = L.registers;
527 49 memset((char *)base + L.registers, 0xFF, (size_t)(k * sizeof(uint64_t))); /* registers = UINT64_MAX */
528 /* Publish magic LAST, as a release store: it is the commit point, so a
529 creator killed before it leaves magic==0 and never a file mistaken for
530 a valid one. A kill during the field stores leaves one to remove by
531 hand. */
532 49 __atomic_store_n(&hdr->magic, MNH_MAGIC, __ATOMIC_RELEASE);
533 49 __atomic_thread_fence(__ATOMIC_SEQ_CST);
534 49 }
535  
536 17314 static inline uint64_t *mnh_registers(MnhHandle *h) {
537 17314 return (uint64_t *)((char *)h->base + h->registers_off);
538 }
539  
540 /* Layer B trusted bound: number of uint64 registers guaranteed within the real
541 * mapping. Derived from the process-local mmap_size and the SAME registers_off
542 * mnh_registers() uses, so a peer that corrupts hdr->k / registers_off after
543 * attach-time validation can never drive an access outside the mapping. Equals
544 * k for a valid sketch, so every clamp below it is a never-taken branch. */
545 17314 static inline uint64_t mnh_reg_max(MnhHandle *h) {
546 17314 uint64_t off = h->registers_off;
547 17314 ▶ if (off >= h->mmap_size) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (off >= h->mmap_size) return 0; 0 17314 17314
548 17314 return (h->mmap_size - off) / sizeof(uint64_t);
549 }
550  
551 58 static inline MnhHandle *mnh_setup(void *base, size_t map_size,
552 const char *path, int backing_fd) {
553 58 MnhHeader *hdr = (MnhHeader *)base;
554 58 MnhHandle *h = (MnhHandle *)calloc(1, sizeof(MnhHandle));
555 58 ▶ if (!h) {
Branch: 1 branch
BranchTrueFalseTotal
if (!h) { 0 58 58
556 0 munmap(base, map_size);
557 0 ▶ if (backing_fd >= 0) close(backing_fd);
Branch: 1 branch
BranchTrueFalseTotal
if (backing_fd >= 0) close(backing_fd); 0 0 0
558 0 return NULL;
559 }
560 58 h->hdr = hdr;
561 58 h->base = base;
562 58 h->reader_slots = (MnhReaderSlot *)((uint8_t *)base + sizeof(MnhHeader)); /* trusted layout, not the peer-writable header offset */
563 58 h->occ = (uint64_t *)((uint8_t *)base + mnh_layout().occ); /* trusted layout offset */
564 58 h->registers_off = hdr->registers_off; /* single validated read; bound and pointer stay consistent */
565 58 h->mmap_size = map_size;
566 58 ▶ h->path = path ? strdup(path) : NULL;
Branch: 1 branch
BranchTrueFalseTotal
h->path = path ? strdup(path) : NULL; 15 43 58
567 58 h->backing_fd = backing_fd;
568 58 h->my_slot_idx = UINT32_MAX;
569 58 return h;
570 }
571  
572 /* Validate a mapped header (shared by mnh_create reopen and mnh_open_fd). */
573 15 static inline int mnh_validate_header(const MnhHeader *hdr, uint64_t file_size) {
574 15 ▶ if (__atomic_load_n(&hdr->magic, __ATOMIC_ACQUIRE) != MNH_MAGIC) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&hdr->magic, __ATOMIC_ACQUIRE) != MNH_MAGIC) return 0; 4 11 15
575 11 ▶ if (hdr->version != MNH_VERSION) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->version != MNH_VERSION) return 0; 0 11 11
576 11 ▶ if (hdr->k < MNH_MIN_K || hdr->k > MNH_MAX_K) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (hdr->k < MNH_MIN_K || hdr->k > MNH_MAX_K) return 0; 11 0 11
if (hdr->k < MNH_MIN_K || hdr->k > MNH_MAX_K) return 0; 0 11 11
577 11 ▶ if (hdr->capacity != hdr->k) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->capacity != hdr->k) return 0; 0 11 11
578 11 ▶ if (hdr->total_size != file_size) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->total_size != file_size) return 0; 0 11 11
579 11 ▶ if (hdr->total_size != mnh_total_size(hdr->k)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->total_size != mnh_total_size(hdr->k)) return 0; 0 11 11
580 11 MnhLayout L = mnh_layout();
581 11 ▶ if (hdr->reader_slots_off != L.reader_slots) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->reader_slots_off != L.reader_slots) return 0; 0 11 11
582 11 ▶ if (hdr->registers_off != L.registers) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->registers_off != L.registers) return 0; 0 11 11
583 11 return 1;
584 }
585  
586 /* validate the requested number of registers k */
587 57 static int mnh_validate_args(uint64_t k, char *errbuf) {
588 57 ▶ if (errbuf) errbuf[0] = '\0';
Branch: 1 branch
BranchTrueFalseTotal
if (errbuf) errbuf[0] = '\0'; 57 0 57
589 57 ▶ if (k < MNH_MIN_K || k > MNH_MAX_K) { MNH_ERR("number of registers must be between 1 and 2^24"); return 0; }
Branch: 3 branches
BranchTrueFalseTotal
if (k < MNH_MIN_K || k > MNH_MAX_K) { MNH_ERR("number of registers must be between 1 and 2^24"); return 0; } 57 0 57
if (k < MNH_MIN_K || k > MNH_MAX_K) { MNH_ERR("number of registers must be between 1 and 2^24"); return 0; } 0 57 57
if (k < MNH_MIN_K || k > MNH_MAX_K) { MNH_ERR("number of registers must be between 1 and 2^24"); return 0; } 0 0 0
590 57 return 1;
591 }
592  
593 /* Securely obtain a fd for a path-backed segment: create it exclusively
594 * (O_CREAT|O_EXCL|O_NOFOLLOW at `mode`, default 0600 = owner-only), or, if it
595 * already exists, attach to it (O_RDWR|O_NOFOLLOW, no O_CREAT). O_EXCL blocks a
596 * pre-seeded or hard-linked file and O_NOFOLLOW a symlink swap, so a local
597 * attacker can no longer redirect or poison the backing store through the path.
598 * Cross-user sharing is opt-in via a wider `mode` (e.g. 0660); the caller still
599 * validates the file's contents via mnh_validate_header. */
600 16 static int mnh_secure_open(const char *path, mode_t mode, char *errbuf) {
601 16 ▶ for (int attempt = 0; attempt < 100; attempt++) {
Branch: 1 branch
BranchTrueFalseTotal
for (int attempt = 0; attempt < 100; attempt++) { 16 0 16
602 16 int fd = open(path, O_RDWR|O_CREAT|O_EXCL|O_NOFOLLOW|O_CLOEXEC, mode);
603 16 ▶ 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 */ 7 9 16
604 9 ▶ if (errno != EEXIST) { MNH_ERR("create %s: %s", path, strerror(errno)); return -1; }
Branch: 2 branches
BranchTrueFalseTotal
if (errno != EEXIST) { MNH_ERR("create %s: %s", path, strerror(errno)); return -1; } 0 9 9
if (errno != EEXIST) { MNH_ERR("create %s: %s", path, strerror(errno)); return -1; } 0 0 0
605 9 fd = open(path, O_RDWR|O_NOFOLLOW|O_CLOEXEC);
606 9 ▶ if (fd >= 0) return fd;
Branch: 1 branch
BranchTrueFalseTotal
if (fd >= 0) return fd; 9 0 9
607 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
608 0 ▶ MNH_ERR("open %s: %s", path, strerror(errno)); /* ELOOP => symlink rejected */
Branch: 1 branch
BranchTrueFalseTotal
MNH_ERR("open %s: %s", path, strerror(errno)); /* ELOOP => symlink rejected */ 0 0 0
609 0 return -1;
610 }
611 0 ▶ MNH_ERR("open %s: create/attach kept racing", path);
Branch: 1 branch
BranchTrueFalseTotal
MNH_ERR("open %s: create/attach kept racing", path); 0 0 0
612 0 return -1;
613 }
614  
615 /* True iff the whole file is zero -- what an abandoned mid-init
616 creator leaves. Lets recovery re-init only a provably-empty file, never
617 one that merely starts with a zero word. Cold path, so a byte scan is
618 fine. Read, not mapped: a read fault on a tmpfs hole allocates the page. */
619 2 static int mnh_file_is_zero(int fd, uint64_t size) {
620 char buf[16384];
621 5 ▶ for (uint64_t off = 0; off < size; ) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint64_t off = 0; off < size; ) { 4 1 5
622 4 ssize_t n = pread(fd, buf, size - off < sizeof buf ? (size_t)(size - off) : sizeof buf, (off_t)off);
623 4 ▶ if (n <= 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (n <= 0) return 0; 0 4 4
624 35587 ▶ 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 35583 35584
for (ssize_t i = 0; i < n; i++) if (buf[i]) return 0; 35584 3 35587
625 3 off += (uint64_t)n;
626 }
627 1 return 1;
628 }
629  
630 /* A sparse segment would SIGBUS at the first write the filesystem cannot back. */
631 10 static int mnh_reserve(int fd, uint64_t size) {
632 10 const char *sp = getenv("DATA_MINHASH_SHARED_SPARSE");
633 10 ▶ if (sp && *sp && strcmp(sp, "0")) return 0;
Branch: 3 branches
BranchTrueFalseTotal
if (sp && *sp && strcmp(sp, "0")) return 0; 0 10 10
if (sp && *sp && strcmp(sp, "0")) return 0; 0 0 0
if (sp && *sp && strcmp(sp, "0")) return 0; 0 0 0
634 /* Before Linux 6.11 tmpfs gives up at any pending signal and undoes the allocation, so a
635 * periodic one could keep it from ever completing; SIGSTOP cannot be blocked. */
636 sigset_t all, old;
637 10 sigfillset(&all);
638 10 sigprocmask(SIG_BLOCK, &all, &old);
639 int e;
640 10 ▶ 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 10 10
641 10 sigprocmask(SIG_SETMASK, &old, NULL);
642 10 ▶ if (e == 0 || e == EOPNOTSUPP || e == EINVAL) return 0;
Branch: 3 branches
BranchTrueFalseTotal
if (e == 0 || e == EOPNOTSUPP || e == EINVAL) return 0; 0 10 10
if (e == 0 || e == EOPNOTSUPP || e == EINVAL) return 0; 0 0 0
if (e == 0 || e == EOPNOTSUPP || e == EINVAL) return 0; 0 0 0
643 0 errno = e;
644 0 return -1;
645 }
646  
647 55 static MnhHandle *mnh_create(const char *path, uint64_t k, mode_t mode, char *errbuf) {
648 55 ▶ if (!mnh_validate_args(k, errbuf)) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!mnh_validate_args(k, errbuf)) return NULL; 0 55 55
649  
650 55 uint64_t total = mnh_total_size(k);
651 55 int anonymous = (path == NULL);
652 55 int fd = -1;
653 size_t map_size;
654 void *base;
655  
656 55 ▶ if (anonymous) {
Branch: 1 branch
BranchTrueFalseTotal
if (anonymous) { 39 16 55
657 39 map_size = (size_t)total;
658 39 base = mmap(NULL, map_size, PROT_READ|PROT_WRITE, MAP_SHARED|MAP_ANONYMOUS, -1, 0);
659 39 ▶ if (base == MAP_FAILED) { MNH_ERR("mmap: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { MNH_ERR("mmap: %s", strerror(errno)); return NULL; } 0 39 39
if (base == MAP_FAILED) { MNH_ERR("mmap: %s", strerror(errno)); return NULL; } 0 0 0
660 } else {
661 16 fd = mnh_secure_open(path, mode, errbuf);
662 24 ▶ if (fd < 0) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (fd < 0) return NULL; 0 16 16
663 16 ▶ if (flock(fd, LOCK_EX) < 0) { MNH_ERR("flock: %s", strerror(errno)); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (flock(fd, LOCK_EX) < 0) { MNH_ERR("flock: %s", strerror(errno)); close(fd); return NULL; } 0 16 16
if (flock(fd, LOCK_EX) < 0) { MNH_ERR("flock: %s", strerror(errno)); close(fd); return NULL; } 0 0 0
664 struct stat st;
665 16 ▶ if (fstat(fd, &st) < 0) { MNH_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fstat(fd, &st) < 0) { MNH_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; } 0 16 16
if (fstat(fd, &st) < 0) { MNH_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; } 0 0 0
666 16 int is_new = (st.st_size == 0);
667 16 ▶ if (!is_new && (uint64_t)st.st_size < sizeof(MnhHeader)) {
Branch: 2 branches
BranchTrueFalseTotal
if (!is_new && (uint64_t)st.st_size < sizeof(MnhHeader)) { 9 7 16
if (!is_new && (uint64_t)st.st_size < sizeof(MnhHeader)) { 1 8 9
668 1 ▶ MNH_ERR("%s: file too small (%lld)", path, (long long)st.st_size);
Branch: 1 branch
BranchTrueFalseTotal
MNH_ERR("%s: file too small (%lld)", path, (long long)st.st_size); 1 0 1
669 1 flock(fd, LOCK_UN); close(fd); return NULL;
670 }
671 15 ▶ if (!is_new) {
Branch: 1 branch
BranchTrueFalseTotal
if (!is_new) { 8 7 15
672 MnhHeader disk_hdr;
673 8 ▶ if (pread(fd, &disk_hdr, sizeof disk_hdr, 0) != (ssize_t)sizeof disk_hdr) {
Branch: 1 branch
BranchTrueFalseTotal
if (pread(fd, &disk_hdr, sizeof disk_hdr, 0) != (ssize_t)sizeof disk_hdr) { 0 8 8
674 0 ▶ MNH_ERR("invalid MinHash sketch file");
Branch: 1 branch
BranchTrueFalseTotal
MNH_ERR("invalid MinHash sketch file"); 0 0 0
675 4 flock(fd, LOCK_UN); close(fd); return NULL;
676 }
677 8 ▶ if (!mnh_validate_header(&disk_hdr, (uint64_t)st.st_size)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!mnh_validate_header(&disk_hdr, (uint64_t)st.st_size)) { 4 4 8
678 /* Inspect holes with pread: mmap faults can SIGBUS on a full tmpfs. */
679 4 ▶ if (disk_hdr.magic == 0 && (uint64_t)st.st_size == total
Branch: 2 branches
BranchTrueFalseTotal
if (disk_hdr.magic == 0 && (uint64_t)st.st_size == total 3 1 4
if (disk_hdr.magic == 0 && (uint64_t)st.st_size == total 2 1 3
680 2 ▶ && st.st_uid == geteuid()) {
Branch: 1 branch
BranchTrueFalseTotal
&& st.st_uid == geteuid()) { 2 0 2
681 2 ▶ if (mnh_file_is_zero(fd, (uint64_t)st.st_size)) is_new = 1;
Branch: 1 branch
BranchTrueFalseTotal
if (mnh_file_is_zero(fd, (uint64_t)st.st_size)) is_new = 1; 1 1 2
682 else {
683 1 ▶ MNH_ERR("%s: incomplete MinHash sketch file left by an interrupted create; remove it and retry", path);
Branch: 1 branch
BranchTrueFalseTotal
MNH_ERR("%s: incomplete MinHash sketch file left by an interrupted create; remove it and retry", path); 1 0 1
684 1 flock(fd, LOCK_UN); close(fd); return NULL;
685 }
686 } else {
687 2 ▶ MNH_ERR("invalid MinHash sketch file");
Branch: 1 branch
BranchTrueFalseTotal
MNH_ERR("invalid MinHash sketch file"); 2 0 2
688 2 flock(fd, LOCK_UN); close(fd); return NULL;
689 }
690 4 ▶ } else if (disk_hdr.sealed) {
Branch: 1 branch
BranchTrueFalseTotal
} else if (disk_hdr.sealed) { 1 3 4
691 1 ▶ MNH_ERR("%s is frozen (read-only); open it with new_readonly", path);
Branch: 1 branch
BranchTrueFalseTotal
MNH_ERR("%s is frozen (read-only); open it with new_readonly", path); 1 0 1
692 1 flock(fd, LOCK_UN); close(fd); return NULL;
693 }
694 }
695 11 ▶ 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)) { 8 3 11
if (is_new && (st.st_uid != geteuid() || fchmod(fd, mode) < 0)) { 8 0 8
if (is_new && (st.st_uid != geteuid() || fchmod(fd, mode) < 0)) { 0 8 8
696 0 ▶ MNH_ERR("%s: refusing to initialize file not owned by us", path);
Branch: 1 branch
BranchTrueFalseTotal
MNH_ERR("%s: refusing to initialize file not owned by us", path); 0 0 0
697 0 flock(fd, LOCK_UN); close(fd); return NULL;
698 }
699 11 ▶ if (is_new && ftruncate(fd, (off_t)total) < 0) {
Branch: 2 branches
BranchTrueFalseTotal
if (is_new && ftruncate(fd, (off_t)total) < 0) { 8 3 11
if (is_new && ftruncate(fd, (off_t)total) < 0) { 0 8 8
700 0 ▶ MNH_ERR("ftruncate: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
MNH_ERR("ftruncate: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; 0 0 0
701 }
702 11 ▶ if (is_new && mnh_reserve(fd, total) < 0) {
Branch: 2 branches
BranchTrueFalseTotal
if (is_new && mnh_reserve(fd, total) < 0) { 8 3 11
if (is_new && mnh_reserve(fd, total) < 0) { 0 8 8
703 0 ▶ MNH_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
MNH_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno)); 0 0 0
704 0 if (ftruncate(fd, 0) < 0) { /* best effort */ }
705 0 flock(fd, LOCK_UN); close(fd); return NULL;
706 }
707 11 ▶ 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; 3 8 11
708 11 base = mmap(NULL, map_size, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
709 11 ▶ if (base == MAP_FAILED) {
Branch: 1 branch
BranchTrueFalseTotal
if (base == MAP_FAILED) { 0 11 11
710 0 ▶ MNH_ERR("mmap: %s", strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
MNH_ERR("mmap: %s", strerror(errno)); 0 0 0
711 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
712 0 flock(fd, LOCK_UN); close(fd); return NULL;
713 }
714 11 ▶ if (!is_new) {
Branch: 1 branch
BranchTrueFalseTotal
if (!is_new) { 3 8 11
715 3 flock(fd, LOCK_UN); close(fd);
716 3 return mnh_setup(base, map_size, path, -1);
717 }
718 }
719 47 mnh_init_header(base, k, total);
720 47 ▶ if (fd >= 0) { flock(fd, LOCK_UN); close(fd); }
Branch: 1 branch
BranchTrueFalseTotal
if (fd >= 0) { flock(fd, LOCK_UN); close(fd); } 8 39 47
721 47 return mnh_setup(base, map_size, path, -1);
722 }
723  
724 2 static MnhHandle *mnh_create_memfd(const char *name, uint64_t k, char *errbuf) {
725 2 ▶ if (!mnh_validate_args(k, errbuf)) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!mnh_validate_args(k, errbuf)) return NULL; 0 2 2
726  
727 2 uint64_t total = mnh_total_size(k);
728 2 ▶ int fd = memfd_create(name ? name : "minhash", MFD_CLOEXEC | MFD_ALLOW_SEALING);
Branch: 1 branch
BranchTrueFalseTotal
int fd = memfd_create(name ? name : "minhash", MFD_CLOEXEC | MFD_ALLOW_SEALING); 2 0 2
729 2 ▶ if (fd < 0) { MNH_ERR("memfd_create: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fd < 0) { MNH_ERR("memfd_create: %s", strerror(errno)); return NULL; } 0 2 2
if (fd < 0) { MNH_ERR("memfd_create: %s", strerror(errno)); return NULL; } 0 0 0
730 2 ▶ if (ftruncate(fd, (off_t)total) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (ftruncate(fd, (off_t)total) < 0) { 0 2 2
731 0 ▶ MNH_ERR("ftruncate: %s", strerror(errno)); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
MNH_ERR("ftruncate: %s", strerror(errno)); close(fd); return NULL; 0 0 0
732 }
733 2 ▶ if (mnh_reserve(fd, total) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (mnh_reserve(fd, total) < 0) { 0 2 2
734 0 ▶ MNH_ERR("memfd: cannot reserve %llu bytes: %s", (unsigned long long)total, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
MNH_ERR("memfd: cannot reserve %llu bytes: %s", (unsigned long long)total, strerror(errno)); 0 0 0
735 0 close(fd); return NULL;
736 }
737 2 (void)fcntl(fd, F_ADD_SEALS, F_SEAL_SHRINK | F_SEAL_GROW);
738 2 void *base = mmap(NULL, (size_t)total, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
739 2 ▶ if (base == MAP_FAILED) { MNH_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { MNH_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; } 0 2 2
if (base == MAP_FAILED) { MNH_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; } 0 0 0
740 2 mnh_init_header(base, k, total);
741 2 return mnh_setup(base, (size_t)total, NULL, fd);
742 }
743  
744 2 static MnhHandle *mnh_open_fd(int fd, char *errbuf) {
745 2 ▶ if (errbuf) errbuf[0] = '\0';
Branch: 1 branch
BranchTrueFalseTotal
if (errbuf) errbuf[0] = '\0'; 2 0 2
746 struct stat st;
747 2 ▶ if (fstat(fd, &st) < 0) { MNH_ERR("fstat: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fstat(fd, &st) < 0) { MNH_ERR("fstat: %s", strerror(errno)); return NULL; } 0 2 2
if (fstat(fd, &st) < 0) { MNH_ERR("fstat: %s", strerror(errno)); return NULL; } 0 0 0
748 2 ▶ if ((uint64_t)st.st_size < sizeof(MnhHeader)) { MNH_ERR("too small"); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if ((uint64_t)st.st_size < sizeof(MnhHeader)) { MNH_ERR("too small"); return NULL; } 0 2 2
if ((uint64_t)st.st_size < sizeof(MnhHeader)) { MNH_ERR("too small"); return NULL; } 0 0 0
749 /* before mmap: a creator may truncate the file until it has set magic */
750 uint32_t magic;
751 2 ▶ if (pread(fd, &magic, sizeof magic, offsetof(MnhHeader, magic)) != (ssize_t)sizeof magic || magic != MNH_MAGIC) {
Branch: 2 branches
BranchTrueFalseTotal
if (pread(fd, &magic, sizeof magic, offsetof(MnhHeader, magic)) != (ssize_t)sizeof magic || magic != MNH_MAGIC) { 2 0 2
if (pread(fd, &magic, sizeof magic, offsetof(MnhHeader, magic)) != (ssize_t)sizeof magic || magic != MNH_MAGIC) { 0 2 2
752 0 ▶ MNH_ERR("invalid MinHash sketch table"); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
MNH_ERR("invalid MinHash sketch table"); return NULL; 0 0 0
753 }
754 2 size_t ms = (size_t)st.st_size;
755 2 void *base = mmap(NULL, ms, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
756 2 ▶ if (base == MAP_FAILED) { MNH_ERR("mmap: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { MNH_ERR("mmap: %s", strerror(errno)); return NULL; } 0 2 2
if (base == MAP_FAILED) { MNH_ERR("mmap: %s", strerror(errno)); return NULL; } 0 0 0
757 2 ▶ if (!mnh_validate_header((MnhHeader *)base, (uint64_t)st.st_size)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!mnh_validate_header((MnhHeader *)base, (uint64_t)st.st_size)) { 0 2 2
758 0 ▶ MNH_ERR("invalid MinHash sketch table"); munmap(base, ms); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
MNH_ERR("invalid MinHash sketch table"); munmap(base, ms); return NULL; 0 0 0
759 }
760 2 ▶ if (((MnhHeader *)base)->sealed) {
Branch: 1 branch
BranchTrueFalseTotal
if (((MnhHeader *)base)->sealed) { 0 2 2
761 0 ▶ MNH_ERR("this MinHash sketch is frozen (read-only); open it with new_readonly");
Branch: 1 branch
BranchTrueFalseTotal
MNH_ERR("this MinHash sketch is frozen (read-only); open it with new_readonly"); 0 0 0
762 0 munmap(base, ms); return NULL;
763 }
764 2 int myfd = fcntl(fd, F_DUPFD_CLOEXEC, 0);
765 2 ▶ if (myfd < 0) { MNH_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (myfd < 0) { MNH_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; } 0 2 2
if (myfd < 0) { MNH_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; } 0 0 0
766 2 return mnh_setup(base, ms, NULL, myfd);
767 }
768  
769 /* Open a FROZEN (sealed) file read-only: O_RDONLY + PROT_READ, no lock ever.
770 * A sealed file is immutable and no read path writes the mapping, so queries
771 * take no reader-slot / rwlock traffic and any number of processes can share
772 * one PROT_READ mapping (same architecture; the magic rejects a wrong-endian
773 * file). */
774 6 static MnhHandle *mnh_open_readonly(const char *path, char *errbuf) {
775 6 ▶ if (errbuf) errbuf[0] = '\0';
Branch: 1 branch
BranchTrueFalseTotal
if (errbuf) errbuf[0] = '\0'; 6 0 6
776 6 int fd = open(path, O_RDONLY|O_NOFOLLOW|O_CLOEXEC);
777 6 ▶ if (fd < 0) { MNH_ERR("open %s: %s", path, strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fd < 0) { MNH_ERR("open %s: %s", path, strerror(errno)); return NULL; } 1 5 6
if (fd < 0) { MNH_ERR("open %s: %s", path, strerror(errno)); return NULL; } 1 0 1
778 struct stat st;
779 5 ▶ if (fstat(fd, &st) < 0) { MNH_ERR("fstat %s: %s", path, strerror(errno)); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fstat(fd, &st) < 0) { MNH_ERR("fstat %s: %s", path, strerror(errno)); close(fd); return NULL; } 0 5 5
if (fstat(fd, &st) < 0) { MNH_ERR("fstat %s: %s", path, strerror(errno)); close(fd); return NULL; } 0 0 0
780 5 ▶ if ((uint64_t)st.st_size < sizeof(MnhHeader)) { MNH_ERR("%s: file too small", path); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if ((uint64_t)st.st_size < sizeof(MnhHeader)) { MNH_ERR("%s: file too small", path); close(fd); return NULL; } 0 5 5
if ((uint64_t)st.st_size < sizeof(MnhHeader)) { MNH_ERR("%s: file too small", path); close(fd); return NULL; } 0 0 0
781 /* before mmap: a creator may truncate the file until it has set magic */
782 uint32_t magic;
783 5 ▶ if (pread(fd, &magic, sizeof magic, offsetof(MnhHeader, magic)) != (ssize_t)sizeof magic || magic != MNH_MAGIC) {
Branch: 2 branches
BranchTrueFalseTotal
if (pread(fd, &magic, sizeof magic, offsetof(MnhHeader, magic)) != (ssize_t)sizeof magic || magic != MNH_MAGIC) { 5 0 5
if (pread(fd, &magic, sizeof magic, offsetof(MnhHeader, magic)) != (ssize_t)sizeof magic || magic != MNH_MAGIC) { 0 5 5
784 0 ▶ MNH_ERR("%s: invalid MinHash sketch file", path); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
MNH_ERR("%s: invalid MinHash sketch file", path); close(fd); return NULL; 0 0 0
785 }
786 5 size_t ms = (size_t)st.st_size;
787 5 void *base = mmap(NULL, ms, PROT_READ, MAP_SHARED, fd, 0);
788 5 close(fd); /* the mapping keeps the file; a read-only view needs no fd (no msync/ftruncate) */
789 5 ▶ if (base == MAP_FAILED) { MNH_ERR("mmap %s: %s", path, strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { MNH_ERR("mmap %s: %s", path, strerror(errno)); return NULL; } 0 5 5
if (base == MAP_FAILED) { MNH_ERR("mmap %s: %s", path, strerror(errno)); return NULL; } 0 0 0
790 5 ▶ if (!mnh_validate_header((MnhHeader *)base, (uint64_t)st.st_size)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!mnh_validate_header((MnhHeader *)base, (uint64_t)st.st_size)) { 0 5 5
791 0 ▶ MNH_ERR("%s: invalid MinHash sketch file", path); munmap(base, ms); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
MNH_ERR("%s: invalid MinHash sketch file", path); munmap(base, ms); return NULL; 0 0 0
792 }
793 5 ▶ if (!__atomic_load_n(&((MnhHeader *)base)->sealed, __ATOMIC_ACQUIRE)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!__atomic_load_n(&((MnhHeader *)base)->sealed, __ATOMIC_ACQUIRE)) { 1 4 5
794 1 ▶ MNH_ERR("%s is not frozen: call ->freeze on the producer before opening read-only", path);
Branch: 1 branch
BranchTrueFalseTotal
MNH_ERR("%s is not frozen: call ->freeze on the producer before opening read-only", path); 1 0 1
795 1 munmap(base, ms); return NULL;
796 }
797 4 MnhHandle *h = mnh_setup(base, ms, path, -1); /* munmaps on OOM */
798 4 ▶ if (!h) { MNH_ERR("out of memory"); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (!h) { MNH_ERR("out of memory"); return NULL; } 0 4 4
if (!h) { MNH_ERR("out of memory"); return NULL; } 0 0 0
799 4 h->readonly = 1;
800 4 return h;
801 }
802  
803 58 static void mnh_destroy(MnhHandle *h) {
804 58 ▶ if (!h) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!h) return; 0 58 58
805 /* Release our reader slot on clean teardown (else short-lived-reader churn
806 * exhausts the slot table); skip if a read lock is still held (rdepth>0). */
807 58 ▶ 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 && 58 0 58
if (h->reader_slots && h->my_slot_idx != UINT32_MAX && h->cached_pid && 47 11 58
if (h->reader_slots && h->my_slot_idx != UINT32_MAX && h->cached_pid && 47 0 47
808 47 ▶ h->cached_fork_gen == __atomic_load_n(&mnh_fork_gen, __ATOMIC_RELAXED) &&
Branch: 1 branch
BranchTrueFalseTotal
h->cached_fork_gen == __atomic_load_n(&mnh_fork_gen, __ATOMIC_RELAXED) && 47 0 47
809 47 ▶ __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) { 47 0 47
810 /* Clear our occ bit BEFORE freeing the slot: we still own the pid so no
811 * claimant can take the slot mid-clear, and rdepth==0 so no writer needs
812 * to see us. (A crash skips this -> the bit is reclaimed lazily by a
813 * writer scan / re-claim, same as the pid.) */
814 47 mnh_occ_clear(h, h->my_slot_idx);
815 47 uint32_t expected = h->cached_pid;
816 47 __atomic_compare_exchange_n(&h->reader_slots[h->my_slot_idx].pid,
817 &expected, 0, 0, __ATOMIC_RELEASE, __ATOMIC_RELAXED);
818 }
819 58 ▶ if (h->backing_fd >= 0) close(h->backing_fd);
Branch: 1 branch
BranchTrueFalseTotal
if (h->backing_fd >= 0) close(h->backing_fd); 4 54 58
820 58 ▶ if (h->base) munmap(h->base, h->mmap_size);
Branch: 1 branch
BranchTrueFalseTotal
if (h->base) munmap(h->base, h->mmap_size); 58 0 58
821 58 free(h->path);
822 58 free(h);
823 }
824  
825 4 static inline int mnh_msync(MnhHandle *h) {
826 4 ▶ if (!h || !h->base) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (!h || !h->base) return 0; 4 0 4
if (!h || !h->base) return 0; 0 4 4
827 4 return msync(h->base, h->mmap_size, MS_SYNC);
828 }
829  
830 /* Seal a sketch: make it permanently immutable so it can be shipped and opened
831 * read-only. Takes the write lock so no add/add_many/merge/clear is in flight,
832 * publishes the seal, then flushes it (file/memfd-backed). Afterwards every
833 * mutator croaks and a read-write reopen is refused. */
834 2 static int mnh_freeze(MnhHandle *h) {
835 2 mnh_rwlock_wrlock(h);
836 2 __atomic_store_n(&h->hdr->sealed, 1, __ATOMIC_RELEASE);
837 2 mnh_rwlock_wrunlock(h);
838 2 ▶ if (h->path || h->backing_fd >= 0) return mnh_msync(h); /* durability for file/memfd-backed */
Branch: 2 branches
BranchTrueFalseTotal
if (h->path || h->backing_fd >= 0) return mnh_msync(h); /* durability for file/memfd-backed */ 0 2 2
if (h->path || h->backing_fd >= 0) return mnh_msync(h); /* durability for file/memfd-backed */ 0 0 0
839 0 return 0; /* anonymous: the seal lives in shared memory (visible to forks); nothing to flush */
840 }
841  
842 /* ================================================================
843 * MinHash operations (callers hold the lock). Each of the k registers
844 * holds the minimum hash value seen for an independent hash function; an
845 * item is hashed once, then mixed with each register's index so the k
846 * registers behave like k independent min-hashes. The Jaccard similarity
847 * of two sets is estimated by the fraction of registers that agree between
848 * their sketches.
849 * ================================================================ */
850  
851 /* mix a base hash with register index j into an independent 64-bit value
852 * (a splitmix64-style finalizer keyed by j) */
853 13579640 static inline uint64_t mnh_mix(uint64_t base, uint64_t j) {
854 13579640 uint64_t x = base + (j + 1) * 0x9E3779B97F4A7C15ULL;
855 13579640 x ^= x >> 30; x *= 0xBF58476D1CE4E5B9ULL;
856 13579640 x ^= x >> 27; x *= 0x94D049BB133111EBULL;
857 13579640 x ^= x >> 31;
858 13579640 return x;
859 }
860  
861 /* fold one item into the sketch: for each register keep the smaller of its
862 * current value and this item's mixed hash. Returns 1 if any register was
863 * lowered (the item changed the sketch), else 0. */
864 16639 static int mnh_add_locked(MnhHandle *h, const void *item, size_t len) {
865 16639 uint64_t base = XXH3_64bits(item, len);
866 16639 uint64_t k = h->hdr->k;
867 16639 uint64_t kmax = mnh_reg_max(h); /* Layer B: clamp to the mapping */
868 16639 ▶ if (k > kmax) k = kmax;
Branch: 1 branch
BranchTrueFalseTotal
if (k > kmax) k = kmax; 0 16639 16639
869 16639 uint64_t *reg = mnh_registers(h);
870 16639 int changed = 0;
871 13596279 ▶ for (uint64_t j = 0; j < k; j++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint64_t j = 0; j < k; j++) { 13579640 16639 13596279
872 13579640 uint64_t v = mnh_mix(base, j);
873 13579640 ▶ if (v < reg[j]) { reg[j] = v; changed = 1; }
Branch: 1 branch
BranchTrueFalseTotal
if (v < reg[j]) { reg[j] = v; changed = 1; } 122589 13457051 13579640
874 }
875 16639 return changed;
876 }
877  
878 /* count registers that agree between this sketch and a snapshot of another's
879 * registers; the Jaccard estimate is agree / k. other_k is how many
880 * registers the snapshot buffer actually holds. */
881 16 static uint64_t mnh_agree_locked(MnhHandle *h, const uint64_t *other, uint64_t other_k) {
882 16 uint64_t k = h->hdr->k;
883 16 uint64_t kmax = mnh_reg_max(h); /* Layer B: clamp to the mapping */
884 16 ▶ if (k > kmax) k = kmax;
Branch: 1 branch
BranchTrueFalseTotal
if (k > kmax) k = kmax; 0 16 16
885 16 ▶ if (k > other_k) k = other_k; /* ...and to the snapshot buffer */
Branch: 1 branch
BranchTrueFalseTotal
if (k > other_k) k = other_k; /* ...and to the snapshot buffer */ 0 16 16
886 16 uint64_t *reg = mnh_registers(h);
887 16 uint64_t agree = 0;
888 7924 ▶ for (uint64_t j = 0; j < k; j++)
Branch: 1 branch
BranchTrueFalseTotal
for (uint64_t j = 0; j < k; j++) 7908 16 7924
889 7908 ▶ if (reg[j] == other[j]) agree++;
Branch: 1 branch
BranchTrueFalseTotal
if (reg[j] == other[j]) agree++; 4301 3607 7908
890 16 return agree;
891 }
892  
893 /* ---- b-bit MinHash: compare / export only the low b bits of each register ---- */
894 439 static inline uint64_t mnh_bbit_mask(uint32_t b) {
895 439 ▶ return (b >= 64) ? ~(uint64_t)0 : (((uint64_t)1 << b) - 1);
Branch: 1 branch
BranchTrueFalseTotal
return (b >= 64) ? ~(uint64_t)0 : (((uint64_t)1 << b) - 1); 421 18 439
896 }
897 /* correct the observed b-bit match fraction f to a Jaccard estimate: two registers
898 * whose true minimums differ still collide in b bits with probability 2^-b, so
899 * P(match) = J + (1-J)*2^-b => J = (f - 2^-b)/(1 - 2^-b), clamped to [0,1]. */
900 301 static inline double mnh_bbit_correct(double f, uint32_t b) {
901 double j;
902 301 ▶ if (b >= 64) j = f; /* no random-collision term */
Branch: 1 branch
BranchTrueFalseTotal
if (b >= 64) j = f; /* no random-collision term */ 15 286 301
903 286 else { double p0 = 1.0 / (double)((uint64_t)1 << b); /* 2^-b, exact for b < 64 */
904 286 j = (f - p0) / (1.0 - p0); }
905 301 ▶ return j < 0.0 ? 0.0 : (j > 1.0 ? 1.0 : j);
Branch: 2 branches
BranchTrueFalseTotal
return j < 0.0 ? 0.0 : (j > 1.0 ? 1.0 : j); 1 300 301
return j < 0.0 ? 0.0 : (j > 1.0 ? 1.0 : j); 0 300 300
906 }
907 /* count registers whose low b bits agree between this sketch and the `other` snapshot */
908 165 static uint64_t mnh_bbit_agree_locked(MnhHandle *h, const uint64_t *other, uint64_t other_k, uint64_t mask) {
909 165 uint64_t k = h->hdr->k;
910 165 uint64_t kmax = mnh_reg_max(h); /* Layer B: clamp to the mapping */
911 165 ▶ if (k > kmax) k = kmax;
Branch: 1 branch
BranchTrueFalseTotal
if (k > kmax) k = kmax; 0 165 165
912 165 ▶ if (k > other_k) k = other_k; /* ...and to the snapshot buffer */
Branch: 1 branch
BranchTrueFalseTotal
if (k > other_k) k = other_k; /* ...and to the snapshot buffer */ 0 165 165
913 165 uint64_t *reg = mnh_registers(h);
914 165 uint64_t agree = 0;
915 36005 ▶ for (uint64_t j = 0; j < k; j++)
Branch: 1 branch
BranchTrueFalseTotal
for (uint64_t j = 0; j < k; j++) 35840 165 36005
916 35840 ▶ if ((reg[j] & mask) == (other[j] & mask)) agree++;
Branch: 1 branch
BranchTrueFalseTotal
if ((reg[j] & mask) == (other[j] & mask)) agree++; 20192 15648 35840
917 165 return agree;
918 }
919 /* pack the low b bits of n registers into out[] (ceil(n*b/8) bytes; register i at bit i*b) */
920 274 static void mnh_bbit_pack(const uint64_t *reg, uint64_t n, uint32_t b, uint8_t *out) {
921 274 uint64_t nbytes = (n * (uint64_t)b + 7) / 8;
922 274 memset(out, 0, (size_t)nbytes);
923 274 uint64_t mask = mnh_bbit_mask(b);
924 20882 ▶ for (uint64_t i = 0; i < n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint64_t i = 0; i < n; i++) { 20608 274 20882
925 20608 uint64_t v = reg[i] & mask, bitpos = i * (uint64_t)b;
926 390272 ▶ for (uint32_t j = 0; j < b; j++)
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t j = 0; j < b; j++) 369664 20608 390272
927 369664 ▶ if ((v >> j) & 1) out[(bitpos + j) >> 3] |= (uint8_t)(1u << ((bitpos + j) & 7));
Branch: 1 branch
BranchTrueFalseTotal
if ((v >> j) & 1) out[(bitpos + j) >> 3] |= (uint8_t)(1u << ((bitpos + j) & 7)); 177102 192562 369664
928 }
929 274 }
930 /* extract register i's b-bit value from a packed signature buffer */
931 17664 static inline uint64_t mnh_bbit_get(const uint8_t *buf, uint64_t i, uint32_t b) {
932 17664 uint64_t bitpos = i * (uint64_t)b, v = 0;
933 378624 ▶ for (uint32_t j = 0; j < b; j++)
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t j = 0; j < b; j++) 360960 17664 378624
934 360960 v |= (uint64_t)((buf[(bitpos + j) >> 3] >> ((bitpos + j) & 7)) & 1) << j;
935 17664 return v;
936 }
937  
938 /* number of registers that have taken a value (differ from the UINT64_MAX
939 * empty sentinel); 0 means the sketch is empty. (caller holds a lock) */
940 13 static uint64_t mnh_filled_locked(MnhHandle *h) {
941 13 uint64_t k = h->hdr->k;
942 13 uint64_t kmax = mnh_reg_max(h); /* Layer B: clamp to the mapping */
943 13 ▶ if (k > kmax) k = kmax;
Branch: 1 branch
BranchTrueFalseTotal
if (k > kmax) k = kmax; 0 13 13
944 13 uint64_t *reg = mnh_registers(h);
945 13 uint64_t filled = 0;
946 1613 ▶ for (uint64_t j = 0; j < k; j++)
Branch: 1 branch
BranchTrueFalseTotal
for (uint64_t j = 0; j < k; j++) 1600 13 1613
947 1600 ▶ if (reg[j] != UINT64_MAX) filled++;
Branch: 1 branch
BranchTrueFalseTotal
if (reg[j] != UINT64_MAX) filled++; 1280 320 1600
948 13 return filled;
949 }
950  
951 /* merge another sketch's registers into this one: element-wise minimum, so
952 * the result is the min-hash sketch of the union of the two input sets.
953 * src_k is the number of registers the src buffer actually holds. */
954 2 static void mnh_merge_locked(MnhHandle *dst, const uint64_t *src, uint64_t src_k) {
955 2 uint64_t k = dst->hdr->k;
956 2 uint64_t kmax = mnh_reg_max(dst); /* Layer B: clamp writes to dst mapping */
957 2 ▶ if (k > kmax) k = kmax;
Branch: 1 branch
BranchTrueFalseTotal
if (k > kmax) k = kmax; 0 2 2
958 2 ▶ if (k > src_k) k = src_k; /* ...and reads to the src buffer */
Branch: 1 branch
BranchTrueFalseTotal
if (k > src_k) k = src_k; /* ...and reads to the src buffer */ 0 2 2
959 2 uint64_t *reg = mnh_registers(dst);
960 642 ▶ for (uint64_t j = 0; j < k; j++)
Branch: 1 branch
BranchTrueFalseTotal
for (uint64_t j = 0; j < k; j++) 640 2 642
961 640 ▶ if (src[j] < reg[j]) reg[j] = src[j];
Branch: 1 branch
BranchTrueFalseTotal
if (src[j] < reg[j]) reg[j] = src[j]; 307 333 640
962 2 }
963  
964 /* reset every register to the empty sentinel (caller holds the write lock) */
965 1 static inline void mnh_clear_locked(MnhHandle *h) {
966 1 uint64_t k = h->hdr->k;
967 1 uint64_t kmax = mnh_reg_max(h); /* Layer B: clamp memset to the mapping */
968 1 ▶ if (k > kmax) k = kmax;
Branch: 1 branch
BranchTrueFalseTotal
if (k > kmax) k = kmax; 0 1 1
969 1 memset(mnh_registers(h), 0xFF, (size_t)(k * sizeof(uint64_t)));
970 1 }
971  
972 #endif /* MNH_H */
« xxhash.h ↑ Summary Shared.xs »