intern.h

filter: Statementstmt 74.7% 372 / 498 Branchbran 46.8% 196 / 418 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 62.0% 568 / 916 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« xxhash.h ↑ Summary Shared.xs »
1 /*
2 * intern.h -- Shared-memory string interning table for Linux
3 *
4 * Maps arbitrary byte strings to dense uint32 ids and back. Each string is
5 * stored once in an append-only arena ([uint32 len][bytes]); an open-addressed
6 * forward hash maps string -> id; reverse[id] -> arena offset is the one
7 * authoritative id->offset map. Several processes share the mapping; a
8 * write-preferring futex rwlock with reader-slot dead-process recovery guards
9 * mutation.
10 *
11 * Layout: Header -> reader_slots[1024] -> forward_hash -> reverse_array -> arena
12 */
13  
14 #ifndef INTERN_H
15 #define INTERN_H
16  
17 #include <stddef.h>
18 #include <stdint.h>
19 #include <stdlib.h>
20 #include <string.h>
21 #include <unistd.h>
22 #include <fcntl.h>
23 #include <errno.h>
24 #include <time.h>
25 #include <limits.h>
26 #include <signal.h>
27 #include <stdio.h>
28 #include <sys/mman.h>
29 #include <sys/stat.h>
30 #include <sys/file.h>
31 #include <sys/syscall.h>
32 #include <linux/futex.h>
33 #include <pthread.h>
34  
35 #define XXH_INLINE_ALL
36 #include "xxhash.h"
37  
38 #if defined(__BYTE_ORDER__) && __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
39 #error "intern.h: requires little-endian architecture"
40 #endif
41  
42  
43 /* ================================================================
44 * Constants
45 * ================================================================ */
46  
47 #define SI_MAGIC 0x544E4953U /* "SINT" (little-endian) */
48 #define SI_VERSION 2 /* 2: added the occupancy bitmap region (layout change) */
49 #define SI_ERR_BUFLEN (PATH_MAX + 256)
50 #define SI_READER_SLOTS 1024 /* max concurrent reader processes for dead-process recovery */
51 /* Occupancy bitmap: one bit per reader slot, set when a process claims a slot and
52 * cleared on clean release. A writer scans these SI_OCC_WORDS words to visit only
53 * OCCUPIED slots (O(words + live readers)) instead of all SI_READER_SLOTS. */
54 #define SI_OCC_WORDS (((SI_READER_SLOTS) + 63) / 64) /* 16 for 1024 slots */
55 #define SI_OCC_BYTES ((uint64_t)SI_OCC_WORDS * 8) /* 128 bytes */
56 #define SI_MAX_STRINGS 0x40000000u /* id-space cap (2^30) */
57 #define SI_MAX_ARENA 0xFFFFFFFFu /* arena cap (offsets are uint32) */
58  
59 #define SI_ERR(fmt, ...) do { if (errbuf) snprintf(errbuf, SI_ERR_BUFLEN, fmt, ##__VA_ARGS__); } while (0)
60  
61 /* ================================================================
62 * Structs
63 * ================================================================ */
64  
65 /* forward-hash slot (open addressing): string -> id. Stores only the id; the
66 string bytes are reached via reverse[id] -> arena, so there is one
67 authoritative id->offset map. `fp` is the low 8 hash bits, a cheap
68 fingerprint to skip most full compares on a probe collision. */
69 typedef struct {
70 uint32_t id; /* interned id */
71 uint8_t fp; /* low 8 bits of the hash */
72 uint8_t state; /* 0 empty, 1 occupied */
73 uint16_t _pad;
74 } SiSlot;
75  
76 /* Per-process slot for dead-process recovery. In the reader-slots-only rwlock a
77 * reader's ENTIRE contribution to the shared lock is `rdepth` in its OWN slot --
78 * there is no separate shared reader counter to fall out of sync with it -- so a
79 * dead reader's contribution is exactly this one word, which a draining writer
80 * neutralises by clearing the slot's pid (the scan then ignores the slot). No
81 * orphaned counter can exist, so there is no quiescent force-reset and sustained
82 * readers cannot starve a writer. _rsv1/_rsv2 are kept only to preserve the
83 * 16-byte slot size across the already-released builds. */
84 typedef struct {
85 uint32_t pid; /* 0 = unclaimed */
86 uint32_t rdepth; /* read-locks THIS process currently holds (recursion-safe) */
87 uint32_t _rsv1; /* reserved (was waiters_parked); unused, kept for layout size */
88 uint32_t _rsv2; /* reserved (was writers_parked); unused, kept for layout size */
89 } SiReaderSlot;
90  
91 struct SiHeader {
92 uint32_t magic, version; /* 0,4 */
93 uint32_t max_strings; /* 8 id capacity */
94 uint32_t hash_slots; /* 12 forward-hash slots (power of two) */
95 uint32_t arena_bytes; /* 16 arena capacity */
96 uint32_t count; /* 20 interned strings; also the next id to assign */
97 uint32_t arena_used; /* 24 bytes used in the arena */
98 uint32_t clear_pending; /* 28 finish an interrupted clear during recovery */
99 uint64_t total_size; /* 32 */
100 uint64_t reader_slots_off; /* 40 */
101 uint64_t hash_off; /* 48 */
102 uint64_t reverse_off; /* 56 */
103 uint64_t arena_off; /* 64 */
104 uint32_t wlock; /* 72 WRITER word ONLY: 0 (free) or WRITER_BIT|pid. NOT a reader count. */
105 uint32_t rwait; /* 76 parked-waiter hint (readers+writers blocked on wlock); over-count-safe */
106 uint32_t drain_seq; /* 80 futex bumped by a reader releasing under a draining writer (wakes it) */
107 uint32_t slotless_rdepth; /* 84 readers holding with no reader-slot (documented residual; was padding) */
108 uint64_t stat_ops; /* 88 */
109 uint8_t sealed; /* 96 0 = mutable, 1 = frozen (read-only; lock-free reads) */
110 uint8_t _pad[159]; /* 97..255 */
111 };
112 typedef struct SiHeader SiHeader;
113  
114 _Static_assert(sizeof(SiHeader) == 256, "SiHeader must be 256 bytes");
115  
116 /* ---- Process-local handle ---- */
117  
118 typedef struct SiHandle {
119 SiHeader *hdr;
120 SiReaderSlot *reader_slots; /* SI_READER_SLOTS entries */
121 uint64_t *occ; /* SI_OCC_WORDS-word slot-occupancy bitmap (trusted layout offset) */
122 SiSlot *slots; /* forward hash: string -> id */
123 uint32_t *reverse; /* id -> arena offset */
124 uint8_t *arena; /* string store ([uint32 len][bytes] records) */
125 size_t mmap_size;
126 /* Immutable geometry cached at attach (values are validated in
127 * si_validate_header on the open path, and correct-by-construction on the
128 * create path). Array indexing and loop bounds use THESE, never the live
129 * h->hdr->{hash_slots,max_strings,arena_bytes}, so a lock-violating peer
130 * that corrupts those header words after we attach cannot redirect an
131 * index or loop bound out of the physically-sized shared arrays. */
132 uint32_t hash_slots; /* forward-hash slot count (sizes h->slots) */
133 uint32_t max_strings; /* id capacity (sizes h->reverse) */
134 uint32_t arena_bytes; /* arena capacity (sizes h->arena) */
135 char *path; /* backing file path (strdup'd) */
136 int backing_fd; /* memfd or reopened-fd to close on destroy, -1 for file/anon */
137 uint32_t my_slot_idx; /* UINT32_MAX if all slots taken (no recovery for this handle) */
138 uint32_t cached_pid; /* getpid() cached at last slot claim */
139 uint32_t cached_fork_gen; /* si_fork_gen value at last slot claim */
140 uint32_t slotless_held; /* read-locks this process holds with no reader-slot */
141 int readonly; /* 1 = frozen O_RDONLY/PROT_READ view: lock-free reads, mutation croaks */
142 } SiHandle;
143  
144 /* ================================================================
145 * Helpers
146 * ================================================================ */
147  
148 41 static inline uint32_t si_next_pow2(uint32_t v) {
149 41 ▶ if (v < 2) return 1;
Branch: 1 branch
BranchTrueFalseTotal
if (v < 2) return 1; 0 41 41
150 41 return 1u << (32 - __builtin_clz(v - 1));
151 }
152  
153 /* string hash (XXH3): deterministic across processes on this LE platform */
154 131705 static inline uint64_t si_hash(const void *s, size_t n) {
155 131705 return XXH3_64bits(s, n);
156 }
157  
158 /* ================================================================
159 * Futex-based write-preferring read-write lock (reader-slots-only)
160 * with dead-process recovery
161 *
162 * The reader count is NOT stored in a shared counter. It is DISTRIBUTED across
163 * per-process reader slots: each slot's `rdepth` is that process's entire
164 * contribution to the lock. A reader publishes its presence in its own slot and
165 * then re-checks the writer word; a writer publishes the writer word and then
166 * scans every slot until all live readers' rdepth reach 0. Sequentially-
167 * consistent store+load on each side (a Dekker handshake) gives mutual exclusion.
168 *
169 * Because a reader's whole contribution is ONE atomic word owned by ONE process,
170 * a crashed reader is recovered by clearing that one slot (CAS its pid to 0) --
171 * there is no second counter to strand, no orphaned +1, and therefore no
172 * quiescent force-reset. A reader killed anywhere in rdlock/rdunlock leaves at
173 * most `rdepth>0` in its dead slot, which the draining writer clears directly, so
174 * sustained read traffic can never starve a writer. Write-preference is inherent
175 * in the gate (new readers see wlock!=0 and yield), so there is no reader-count
176 * yield hack.
177 * ================================================================ */
178  
179 #define SI_RWLOCK_SPIN_LIMIT 32
180 #define SI_LOCK_TIMEOUT_SEC 2 /* FUTEX_WAIT timeout for stale-lock detection / drain re-scan */
181  
182 0 static inline void si_rwlock_spin_pause(void) {
183 #if defined(__x86_64__) || defined(__i386__)
184 0 __asm__ volatile("pause" ::: "memory");
185 #elif defined(__aarch64__)
186 __asm__ volatile("yield" ::: "memory");
187 #else
188 __asm__ volatile("" ::: "memory");
189 #endif
190 0 }
191  
192 /* Writer word encoding: WRITER_BIT|pid when write-locked, 0 when free. */
193 #define SI_RWLOCK_WRITER_BIT 0x80000000U
194 #define SI_RWLOCK_PID_MASK 0x7FFFFFFFU
195 #define SI_RWLOCK_WR(pid) (SI_RWLOCK_WRITER_BIT | ((uint32_t)(pid) & SI_RWLOCK_PID_MASK))
196  
197 /* A zombie (dead but not yet reaped) still answers kill(pid,0) as alive, so a
198 * process that crashed while holding the lock and lingers unreaped would never
199 * be recovered. Treat /proc/<pid>/stat state 'Z' as dead. Linux-only (as is
200 * this module); if /proc is unreadable we fall back to "alive" (safe: we never
201 * force-recover a possibly-live holder). */
202 0 static inline int si_pid_is_zombie(uint32_t pid) {
203 char path[32], buf[256];
204 0 snprintf(path, sizeof(path), "/proc/%u/stat", (unsigned)pid);
205 0 int fd = open(path, O_RDONLY | O_CLOEXEC);
206 0 ▶ if (fd < 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (fd < 0) return 0; 0 0 0
207 0 ssize_t n = read(fd, buf, sizeof(buf) - 1);
208 0 close(fd);
209 0 ▶ if (n <= 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (n <= 0) return 0; 0 0 0
210 0 buf[n] = '\0';
211 /* "pid (comm) state ..."; comm may contain ')', so scan to the last one. */
212 0 char *rp = strrchr(buf, ')');
213 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
214 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
215 }
216 /* 1 if alive or unknown, 0 if definitely dead. Cannot detect PID reuse: a
217 * recycled PID reports "alive" and the slot is not reclaimed until that
218 * process exits. See "Crash Safety" in the POD. */
219 4 static inline int si_pid_alive(uint32_t pid) {
220 4 ▶ 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 4 4
221 4 ▶ 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 */ 4 0 4
if (kill((pid_t)pid, 0) == -1 && errno == ESRCH) return 0; /* definitely dead */ 4 0 4
222 0 return !si_pid_is_zombie(pid); /* kill() also succeeds for a zombie -> treat as dead */
223 }
224  
225 /* Force-recover a stale WRITE lock left by a dead writer (held or mid-drain).
226 * CAS to OUR pid to hold the lock while fixing shared state, then release.
227 * Using our pid (not a bare WRITER_BIT sentinel) means a subsequent recovering
228 * process can detect and re-recover if we crash mid-recovery. */
229 static inline void si_clear_locked(SiHandle *h);
230  
231 4 static inline void si_recover_stale_lock(SiHandle *h, uint32_t observed_wlock) {
232 4 SiHeader *hdr = h->hdr;
233 4 uint32_t mypid = SI_RWLOCK_WR((uint32_t)getpid());
234 4 ▶ if (!__atomic_compare_exchange_n(&hdr->wlock, &observed_wlock,
Branch: 1 branch
BranchTrueFalseTotal
if (!__atomic_compare_exchange_n(&hdr->wlock, &observed_wlock, 0 4 4
235 mypid, 0, __ATOMIC_ACQUIRE, __ATOMIC_RELAXED))
236 0 return;
237 /* clear_pending is set only after readers have drained. */
238 4 ▶ if (__atomic_load_n(&hdr->clear_pending, __ATOMIC_ACQUIRE))
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&hdr->clear_pending, __ATOMIC_ACQUIRE)) 4 0 4
239 4 si_clear_locked(h);
240 4 __atomic_store_n(&hdr->wlock, 0, __ATOMIC_RELEASE);
241 4 ▶ if (__atomic_load_n(&hdr->rwait, __ATOMIC_RELAXED) > 0)
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&hdr->rwait, __ATOMIC_RELAXED) > 0) 0 4 4
242 0 syscall(SYS_futex, &hdr->wlock, FUTEX_WAKE, INT_MAX, NULL, NULL, 0);
243 }
244  
245 static const struct timespec si_lock_timeout = { SI_LOCK_TIMEOUT_SEC, 0 };
246  
247 /* Process-global fork-generation counter. Incremented in the pthread_atfork
248 * child callback so every open handle detects a fork transition on the next
249 * lock call without paying a getpid() syscall on the hot path. */
250 static uint32_t si_fork_gen = 1;
251 static pthread_once_t si_atfork_once = PTHREAD_ONCE_INIT;
252 0 static void si_on_fork_child(void) {
253 0 __atomic_add_fetch(&si_fork_gen, 1, __ATOMIC_RELAXED);
254 0 }
255 6 static void si_atfork_init(void) {
256 6 pthread_atfork(NULL, NULL, si_on_fork_child);
257 6 }
258  
259 /* Ensure this process owns a reader slot. Called from the lock helpers so that
260 * fork()'d children pick up their own slot lazily instead of sharing the
261 * parent's. Hot-path is a single relaxed load + compare; only on a
262 * fork-generation mismatch do we touch getpid() and scan slots. */
263 /* Occupancy bitmap: set a slot's bit when it is claimed, clear it on clean
264 * release. SEQ_CST so a set bit is ordered before the slot's rdepth can go
265 * non-zero (bit set in claim, which precedes any rdlock), letting a writer's
266 * SEQ_CST bitmap scan never miss a slot a committed reader holds. */
267 30 static inline void si_occ_set(SiHandle *h, uint32_t s) {
268 30 __atomic_fetch_or(&h->occ[s >> 6], (uint64_t)1 << (s & 63), __ATOMIC_SEQ_CST);
269 30 }
270 30 static inline void si_occ_clear(SiHandle *h, uint32_t s) {
271 30 __atomic_fetch_and(&h->occ[s >> 6], ~((uint64_t)1 << (s & 63)), __ATOMIC_SEQ_CST);
272 30 }
273  
274 173778 static inline void si_claim_reader_slot(SiHandle *h) {
275 173778 uint32_t cur_gen = __atomic_load_n(&si_fork_gen, __ATOMIC_RELAXED);
276 173778 ▶ 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)) 173748 30 173778
if (__builtin_expect(cur_gen == h->cached_fork_gen && h->my_slot_idx != UINT32_MAX, 1)) 173748 0 173748
277 173748 return;
278 /* Cold path -- register the atfork hook once per process, then claim. */
279 30 pthread_once(&si_atfork_once, si_atfork_init);
280 /* Re-read after pthread_once: si_on_fork_child may have bumped it. */
281 30 cur_gen = __atomic_load_n(&si_fork_gen, __ATOMIC_RELAXED);
282 30 uint32_t now_pid = (uint32_t)getpid();
283 30 h->cached_pid = now_pid;
284 30 ▶ 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 */ 30 0 30
285 30 h->cached_fork_gen = cur_gen;
286 30 h->my_slot_idx = UINT32_MAX;
287 30 uint32_t start = now_pid % SI_READER_SLOTS;
288 /* Pass 1: take a free slot. */
289 31 ▶ for (uint32_t i = 0; i < SI_READER_SLOTS; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t i = 0; i < SI_READER_SLOTS; i++) { 31 0 31
290 31 uint32_t s = (start + i) % SI_READER_SLOTS;
291 31 uint32_t expected = 0;
292 31 ▶ if (__atomic_compare_exchange_n(&h->reader_slots[s].pid,
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_compare_exchange_n(&h->reader_slots[s].pid, 30 1 31
293 &expected, now_pid, 0,
294 __ATOMIC_ACQUIRE, __ATOMIC_RELAXED)) {
295 /* Fresh owner holds no read locks yet; clear any stale rdepth left by
296 * a dead predecessor (its contribution is dropped as we take over). */
297 30 __atomic_store_n(&h->reader_slots[s].rdepth, 0, __ATOMIC_RELAXED);
298 30 si_occ_set(h, s); /* mark occupied BEFORE any rdlock can bump rdepth */
299 30 h->my_slot_idx = s;
300 30 return;
301 }
302 }
303 /* Pass 2: no free slot -- reclaim one whose owner is dead. Safe to take even
304 * if its rdepth>0: clearing pid drops the dead reader's entire contribution
305 * (a writer scan ignores rdepth when pid==0) and we reset rdepth to 0 as we
306 * claim it. */
307 0 ▶ for (uint32_t i = 0; i < SI_READER_SLOTS; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t i = 0; i < SI_READER_SLOTS; i++) { 0 0 0
308 0 uint32_t dpid = __atomic_load_n(&h->reader_slots[i].pid, __ATOMIC_ACQUIRE);
309 0 ▶ if (dpid == 0 || dpid == now_pid || si_pid_alive(dpid)) continue;
Branch: 3 branches
BranchTrueFalseTotal
if (dpid == 0 || dpid == now_pid || si_pid_alive(dpid)) continue; 0 0 0
if (dpid == 0 || dpid == now_pid || si_pid_alive(dpid)) continue; 0 0 0
if (dpid == 0 || dpid == now_pid || si_pid_alive(dpid)) continue; 0 0 0
310 0 uint32_t expected = dpid;
311 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
312 __ATOMIC_ACQUIRE, __ATOMIC_RELAXED)) {
313 0 __atomic_store_n(&h->reader_slots[i].rdepth, 0, __ATOMIC_RELAXED);
314 0 si_occ_set(h, i);
315 0 h->my_slot_idx = i;
316 0 return;
317 }
318 }
319 /* Table full -- leave my_slot_idx = UINT32_MAX so this handle takes the
320 * slotless path (lock still works; recovery of THIS reader's death is the
321 * documented slotless limitation). */
322 }
323  
324 /* Inspect the writer word after a futex-wait timeout. If a dead writer holds
325 * it, force-recover. Dead READERS need no action here: only a writer that owns
326 * wlock drains readers, and it clears dead readers inline in its own scan. */
327 0 static inline void si_recover_after_timeout(SiHandle *h) {
328 0 uint32_t val = __atomic_load_n(&h->hdr->wlock, __ATOMIC_RELAXED);
329 0 ▶ if (val >= SI_RWLOCK_WRITER_BIT) {
Branch: 1 branch
BranchTrueFalseTotal
if (val >= SI_RWLOCK_WRITER_BIT) { 0 0 0
330 0 uint32_t pid = val & SI_RWLOCK_PID_MASK;
331 0 ▶ if (!si_pid_alive(pid))
Branch: 1 branch
BranchTrueFalseTotal
if (!si_pid_alive(pid)) 0 0 0
332 0 si_recover_stale_lock(h, val);
333 }
334 0 }
335  
336 /* Bump/drop the parked-waiter hint. Both readers (blocked at the gate) and
337 * writers (blocked acquiring wlock) wait on the wlock futex and use this, so
338 * wrunlock/recover know whether a FUTEX_WAKE is worth a syscall. A waiter
339 * SIGKILLed while parked leaves rwait over-counted -> at most a spurious wake
340 * (harmless); it can never under-count, so no wakeup is lost. */
341 0 static inline void si_park(SiHandle *h) {
342 0 __atomic_add_fetch(&h->hdr->rwait, 1, __ATOMIC_RELAXED);
343 0 }
344 0 static inline void si_unpark(SiHandle *h) {
345 0 __atomic_sub_fetch(&h->hdr->rwait, 1, __ATOMIC_RELAXED);
346 0 }
347  
348 /* Publish (inc) / retract (dec) this reader's presence -- its ENTIRE
349 * contribution to the lock. A slotted reader uses its slot's rdepth; a reader
350 * that could not claim a slot uses the global slotless_rdepth. inc() is SEQ_CST
351 * so the wlock re-check that follows it in rdlock forms a Dekker handshake with
352 * the writer's SEQ_CST wlock-store + rdepth-scan. leave() peels slotless first
353 * so a slot claimed mid-hold cannot misattribute the decrement. */
354 119923 static inline void si_rdepth_inc(SiHandle *h) {
355 119923 ▶ if (h->my_slot_idx != UINT32_MAX) {
Branch: 1 branch
BranchTrueFalseTotal
if (h->my_slot_idx != UINT32_MAX) { 119923 0 119923
356 119923 __atomic_add_fetch(&h->reader_slots[h->my_slot_idx].rdepth, 1, __ATOMIC_SEQ_CST);
357 } else {
358 0 __atomic_add_fetch(&h->hdr->slotless_rdepth, 1, __ATOMIC_SEQ_CST);
359 0 h->slotless_held++;
360 }
361 119923 }
362 119923 static inline void si_rdepth_dec(SiHandle *h) {
363 119923 ▶ if (h->slotless_held > 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (h->slotless_held > 0) { 0 119923 119923
364 0 h->slotless_held--;
365 0 __atomic_sub_fetch(&h->hdr->slotless_rdepth, 1, __ATOMIC_RELEASE);
366 119923 ▶ } else if (h->my_slot_idx != UINT32_MAX) {
Branch: 1 branch
BranchTrueFalseTotal
} else if (h->my_slot_idx != UINT32_MAX) { 119923 0 119923
367 119923 __atomic_sub_fetch(&h->reader_slots[h->my_slot_idx].rdepth, 1, __ATOMIC_RELEASE);
368 }
369 119923 }
370  
371 /* Wake a writer that may be draining readers (it waits on drain_seq). Called
372 * after every rdepth decrement so a released read lock lets the writer re-scan
373 * promptly instead of waiting out its timeout. */
374 119923 static inline void si_reader_wake_drain(SiHandle *h) {
375 119923 ▶ 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 119923 119923
376 0 __atomic_add_fetch(&h->hdr->drain_seq, 1, __ATOMIC_RELEASE);
377 0 syscall(SYS_futex, &h->hdr->drain_seq, FUTEX_WAKE, 1, NULL, NULL, 0);
378 }
379 119923 }
380  
381 119923 static inline void si_rwlock_rdlock(SiHandle *h) {
382 119923 si_claim_reader_slot(h);
383 119923 SiHeader *hdr = h->hdr;
384 119925 for (int spin = 0; ; spin++) {
385 119925 uint32_t cur = __atomic_load_n(&hdr->wlock, __ATOMIC_ACQUIRE);
386 119925 ▶ if (cur == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (cur == 0) { 119923 2 119925
387 /* Optimistically take the read: publish rdepth, then re-check wlock.
388 * SEQ_CST inc + SEQ_CST load vs the writer's SEQ_CST wlock CAS +
389 * SEQ_CST rdepth scan: by the single total order of SEQ_CST ops the
390 * two sides cannot both miss each other, so we never hold
391 * concurrently with a writer. */
392 119923 si_rdepth_inc(h);
393 119923 ▶ if (__atomic_load_n(&hdr->wlock, __ATOMIC_SEQ_CST) == 0)
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&hdr->wlock, __ATOMIC_SEQ_CST) == 0) 119923 0 119923
394 119923 return; /* no writer after our publish -> we hold the read lock */
395 /* A writer appeared during our publish -- yield to it (write-preferring). */
396 0 si_rdepth_dec(h);
397 0 si_reader_wake_drain(h); /* let the draining writer see rdepth drop */
398 0 spin = 0;
399 0 continue;
400 }
401 /* wlock != 0: a writer holds or is acquiring. Recover if it is dead. */
402 4 if (cur >= SI_RWLOCK_WRITER_BIT &&
403 2 !si_pid_alive(cur & SI_RWLOCK_PID_MASK)) {
404 2 si_recover_stale_lock(h, cur);
405 2 spin = 0;
406 2 continue;
407 }
408 0 ▶ if (__builtin_expect(spin < SI_RWLOCK_SPIN_LIMIT, 1)) {
Branch: 1 branch
BranchTrueFalseTotal
if (__builtin_expect(spin < SI_RWLOCK_SPIN_LIMIT, 1)) { 0 0 0
409 0 si_rwlock_spin_pause();
410 0 continue;
411 }
412 0 si_park(h);
413 0 cur = __atomic_load_n(&hdr->wlock, __ATOMIC_RELAXED);
414 0 ▶ if (cur != 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (cur != 0) { 0 0 0
415 0 long rc = syscall(SYS_futex, &hdr->wlock, FUTEX_WAIT, cur,
416 &si_lock_timeout, NULL, 0);
417 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
418 0 si_unpark(h);
419 0 si_recover_after_timeout(h);
420 0 spin = 0;
421 0 continue;
422 }
423 }
424 0 si_unpark(h);
425 0 spin = 0;
426 }
427 }
428  
429 119923 static inline void si_rwlock_rdunlock(SiHandle *h) {
430 119923 si_rdepth_dec(h); /* RELEASE: drop our entire contribution */
431 119923 si_reader_wake_drain(h); /* if a writer is draining, wake it to re-scan */
432 119923 }
433  
434 53855 static inline void si_rwlock_wrlock(SiHandle *h) {
435 53855 si_claim_reader_slot(h); /* refresh cached_pid across fork */
436 53855 SiHeader *hdr = h->hdr;
437 /* Encode PID in the wlock word itself (0x80000000 | pid) to eliminate any
438 * crash window between acquiring the lock and storing the owner. */
439 53855 uint32_t mypid = SI_RWLOCK_WR(h->cached_pid);
440 /* Phase 1: acquire the writer word (mutual exclusion among writers). */
441 53857 for (int spin = 0; ; spin++) {
442 53857 uint32_t expected = 0;
443 53857 ▶ if (__atomic_compare_exchange_n(&hdr->wlock, &expected, mypid,
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_compare_exchange_n(&hdr->wlock, &expected, mypid, 53855 2 53857
444 0, __ATOMIC_SEQ_CST, __ATOMIC_RELAXED))
445 53855 break;
446 /* Contended: expected now holds the current wlock value. */
447 4 if (expected >= SI_RWLOCK_WRITER_BIT &&
448 2 !si_pid_alive(expected & SI_RWLOCK_PID_MASK)) {
449 2 si_recover_stale_lock(h, expected);
450 2 spin = 0;
451 2 continue;
452 }
453 0 ▶ if (__builtin_expect(spin < SI_RWLOCK_SPIN_LIMIT, 1)) {
Branch: 1 branch
BranchTrueFalseTotal
if (__builtin_expect(spin < SI_RWLOCK_SPIN_LIMIT, 1)) { 0 0 0
454 0 si_rwlock_spin_pause();
455 0 continue;
456 }
457 0 si_park(h);
458 0 uint32_t cur = __atomic_load_n(&hdr->wlock, __ATOMIC_RELAXED);
459 0 ▶ if (cur != 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (cur != 0) { 0 0 0
460 0 long rc = syscall(SYS_futex, &hdr->wlock, FUTEX_WAIT, cur,
461 &si_lock_timeout, NULL, 0);
462 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
463 0 si_unpark(h);
464 0 si_recover_after_timeout(h);
465 0 spin = 0;
466 0 continue;
467 }
468 }
469 0 si_unpark(h);
470 0 spin = 0;
471 }
472 /* Phase 2: we own wlock, so no NEW reader can join (they see wlock!=0 and
473 * yield). Drain the readers that were already holding when we won the CAS.
474 * The SEQ_CST CAS above + the SEQ_CST rdepth loads below are the writer side
475 * of the Dekker handshake. */
476 0 for (;;) {
477 53855 uint32_t v = __atomic_load_n(&hdr->drain_seq, __ATOMIC_ACQUIRE); /* snapshot BEFORE scan */
478 53855 int busy = 0;
479 /* Visit only OCCUPIED slots via the occupancy bitmap (SEQ_CST: a committed
480 * reader's bit -- set in claim, before its rdepth++ -- is ordered before
481 * this scan, so no held slot is skipped). O(SI_OCC_WORDS + live readers)
482 * instead of O(SI_READER_SLOTS). */
483 915535 ▶ for (uint32_t w = 0; w < SI_OCC_WORDS; w++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t w = 0; w < SI_OCC_WORDS; w++) { 861680 53855 915535
484 861680 uint64_t word = __atomic_load_n(&h->occ[w], __ATOMIC_SEQ_CST);
485 915537 ▶ while (word) {
Branch: 1 branch
BranchTrueFalseTotal
while (word) { 53857 861680 915537
486 53857 uint32_t i = (w << 6) + (uint32_t)__builtin_ctzll(word);
487 53857 word &= word - 1; /* consume this bit (local copy) */
488 53857 uint32_t rd = __atomic_load_n(&h->reader_slots[i].rdepth, __ATOMIC_SEQ_CST);
489 53857 ▶ if (rd == 0) continue; /* occupied but not read-locking now */
Branch: 1 branch
BranchTrueFalseTotal
if (rd == 0) continue; /* occupied but not read-locking now */ 53857 0 53857
490 0 uint32_t pid = __atomic_load_n(&h->reader_slots[i].pid, __ATOMIC_ACQUIRE);
491 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
492 0 ▶ if (!si_pid_alive(pid)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!si_pid_alive(pid)) { 0 0 0
493 /* Dead reader: drop its pid so the slot no longer counts. Leave
494 * the occ bit set (harmless -- a later scan hits pid==0 and skips,
495 * a re-claim re-sets it) to avoid racing a concurrent claimant. */
496 0 uint32_t ep = pid;
497 0 __atomic_compare_exchange_n(&h->reader_slots[i].pid, &ep, 0,
498 0, __ATOMIC_ACQ_REL, __ATOMIC_RELAXED);
499 0 continue;
500 }
501 0 busy = 1; /* live reader still holding */
502 }
503 }
504 /* A live slotless reader keeps us waiting; a crashed slotless reader that
505 * cannot be attributed to a pid is the documented slotless limitation. */
506 53855 ▶ 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 53855 53855
507 0 busy = 1;
508 53855 ▶ if (!busy)
Branch: 1 branch
BranchTrueFalseTotal
if (!busy) 53855 0 53855
509 53855 return; /* exclusive: wlock held + every rdepth 0 */
510 /* Wait for a reader to release (drain_seq bump) or time out to re-scan
511 * (which reclaims any newly-dead slotted reader). */
512 0 syscall(SYS_futex, &hdr->drain_seq, FUTEX_WAIT, v, &si_lock_timeout, NULL, 0);
513 }
514 }
515  
516 53855 static inline void si_rwlock_wrunlock(SiHandle *h) {
517 53855 SiHeader *hdr = h->hdr;
518 53855 __atomic_store_n(&hdr->wlock, 0, __ATOMIC_RELEASE);
519 53855 ▶ if (__atomic_load_n(&hdr->rwait, __ATOMIC_RELAXED) > 0)
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&hdr->rwait, __ATOMIC_RELAXED) > 0) 0 53855 53855
520 0 syscall(SYS_futex, &hdr->wlock, FUTEX_WAKE, INT_MAX, NULL, NULL, 0);
521 53855 }
522  
523 /* ================================================================
524 * Layout math + create / open / destroy
525 *
526 * Layout: Header -> reader_slots[1024] -> occ bitmap -> forward_hash -> reverse_array -> arena
527 * ================================================================ */
528  
529 /* Single source of truth for the mmap region layout offsets. */
530 typedef struct { uint64_t reader_slots, occ, hash, reverse, arena; } SiLayout;
531  
532 139 static inline SiLayout si_layout(uint32_t hash_slots, uint32_t max_strings) {
533 SiLayout L;
534 139 L.reader_slots = sizeof(SiHeader);
535 139 L.occ = L.reader_slots + (uint64_t)SI_READER_SLOTS * sizeof(SiReaderSlot);
536 139 L.hash = L.occ + SI_OCC_BYTES;
537 139 L.reverse = L.hash + (uint64_t)hash_slots * sizeof(SiSlot);
538 139 L.arena = L.reverse + (uint64_t)max_strings * sizeof(uint32_t);
539 139 L.arena = (L.arena + 7) & ~(uint64_t)7; /* 8-byte align the arena */
540 139 return L;
541 }
542  
543 56 static inline uint64_t si_total_size(uint32_t hash_slots, uint32_t max_strings, uint32_t arena_bytes) {
544 56 SiLayout L = si_layout(hash_slots, max_strings);
545 56 return L.arena + (uint64_t)arena_bytes;
546 }
547  
548 28 static inline void si_init_header(void *base, uint32_t max_strings, uint32_t hash_slots,
549 uint32_t arena_bytes, uint64_t total) {
550 28 SiLayout L = si_layout(hash_slots, max_strings);
551 28 SiHeader *hdr = (SiHeader *)base;
552 /* zero the header + reader slots + hash region only; the reverse array and
553 arena are read solely within [0,count)/[0,arena_used), both starting at 0,
554 and the fresh mapping is already zero-filled by the OS. */
555 28 memset(base, 0, (size_t)L.reverse);
556 28 hdr->version = SI_VERSION;
557 28 hdr->max_strings = max_strings;
558 28 hdr->hash_slots = hash_slots;
559 28 hdr->arena_bytes = arena_bytes;
560 28 hdr->count = 0;
561 28 hdr->arena_used = 0;
562 28 hdr->total_size = total;
563 28 hdr->reader_slots_off = L.reader_slots;
564 28 hdr->hash_off = L.hash;
565 28 hdr->reverse_off = L.reverse;
566 28 hdr->arena_off = L.arena;
567 /* Publish magic LAST, as a release store: it is the commit point, so a
568 creator killed before it leaves magic==0 and never a file mistaken for
569 a valid one. A kill during the field stores leaves one to remove by
570 hand. */
571 28 __atomic_store_n(&hdr->magic, SI_MAGIC, __ATOMIC_RELEASE);
572 28 __atomic_thread_fence(__ATOMIC_SEQ_CST);
573 28 }
574  
575 40 static inline SiHandle *si_setup(void *base, size_t map_size,
576 const char *path, int backing_fd) {
577 40 SiHeader *hdr = (SiHeader *)base;
578 40 SiHandle *h = (SiHandle *)calloc(1, sizeof(SiHandle));
579 40 ▶ if (!h) {
Branch: 1 branch
BranchTrueFalseTotal
if (!h) { 0 40 40
580 0 munmap(base, map_size);
581 0 ▶ if (backing_fd >= 0) close(backing_fd);
Branch: 1 branch
BranchTrueFalseTotal
if (backing_fd >= 0) close(backing_fd); 0 0 0
582 0 return NULL;
583 }
584 40 h->hdr = hdr;
585 40 h->reader_slots = (SiReaderSlot *)((uint8_t *)base + sizeof(SiHeader)); /* trusted layout, not the peer-writable header offset */
586 40 h->occ = (uint64_t *)((uint8_t *)base + si_layout(hdr->hash_slots, hdr->max_strings).occ); /* trusted layout offset */
587 40 h->slots = (SiSlot *)((uint8_t *)base + hdr->hash_off);
588 40 h->reverse = (uint32_t *)((uint8_t *)base + hdr->reverse_off);
589 40 h->arena = (uint8_t *)base + hdr->arena_off;
590 40 h->hash_slots = hdr->hash_slots; /* cache immutable geometry at attach */
591 40 h->max_strings = hdr->max_strings;
592 40 h->arena_bytes = hdr->arena_bytes;
593 40 h->mmap_size = map_size;
594 40 ▶ h->path = path ? strdup(path) : NULL;
Branch: 1 branch
BranchTrueFalseTotal
h->path = path ? strdup(path) : NULL; 26 14 40
595 40 h->backing_fd = backing_fd;
596 40 h->my_slot_idx = UINT32_MAX;
597 40 return h;
598 }
599  
600 /* Validate a mapped header (shared by si_create reopen and si_open_fd). */
601 19 static inline int si_validate_header(const SiHeader *hdr, uint64_t file_size) {
602 19 ▶ if (hdr->magic != SI_MAGIC) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->magic != SI_MAGIC) return 0; 4 15 19
603 15 ▶ if (hdr->version != SI_VERSION) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->version != SI_VERSION) return 0; 0 15 15
604 15 ▶ if (hdr->max_strings == 0 || hdr->max_strings > SI_MAX_STRINGS) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (hdr->max_strings == 0 || hdr->max_strings > SI_MAX_STRINGS) return 0; 15 0 15
if (hdr->max_strings == 0 || hdr->max_strings > SI_MAX_STRINGS) return 0; 0 15 15
605 15 ▶ if (hdr->hash_slots == 0 || (hdr->hash_slots & (hdr->hash_slots - 1)) != 0) return 0; /* pow2 */
Branch: 2 branches
BranchTrueFalseTotal
if (hdr->hash_slots == 0 || (hdr->hash_slots & (hdr->hash_slots - 1)) != 0) return 0; /* pow2 */ 15 0 15
if (hdr->hash_slots == 0 || (hdr->hash_slots & (hdr->hash_slots - 1)) != 0) return 0; /* pow2 */ 0 15 15
606 15 ▶ if (hdr->hash_slots <= hdr->max_strings) return 0; /* probe termination: an empty slot always exists */
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->hash_slots <= hdr->max_strings) return 0; /* probe termination: an empty slot always exists */ 0 15 15
607 15 ▶ if (hdr->arena_bytes == 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->arena_bytes == 0) return 0; 0 15 15
608 15 ▶ if (hdr->total_size != file_size) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->total_size != file_size) return 0; 0 15 15
609 15 ▶ if (hdr->total_size != si_total_size(hdr->hash_slots, hdr->max_strings, hdr->arena_bytes)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->total_size != si_total_size(hdr->hash_slots, hdr->max_strings, hdr->arena_bytes)) return 0; 0 15 15
610 15 SiLayout L = si_layout(hdr->hash_slots, hdr->max_strings);
611 15 ▶ 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 15 15
612 15 ▶ if (hdr->hash_off != L.hash) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->hash_off != L.hash) return 0; 0 15 15
613 15 ▶ if (hdr->reverse_off != L.reverse) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->reverse_off != L.reverse) return 0; 0 15 15
614 15 ▶ if (hdr->arena_off != L.arena) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->arena_off != L.arena) return 0; 0 15 15
615 15 ▶ if (hdr->count > hdr->max_strings) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->count > hdr->max_strings) return 0; 0 15 15
616 15 ▶ if (hdr->arena_used > hdr->arena_bytes) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->arena_used > hdr->arena_bytes) return 0; 0 15 15
617 15 return 1;
618 }
619  
620 /* validate args + compute the hash-slot count and (if 0) a default arena size */
621 42 static int si_validate_create_args(uint32_t max_strings, uint32_t *arena_bytes_io,
622 uint32_t *hash_slots, char *errbuf) {
623 42 ▶ if (errbuf) errbuf[0] = '\0';
Branch: 1 branch
BranchTrueFalseTotal
if (errbuf) errbuf[0] = '\0'; 42 0 42
624 42 ▶ if (max_strings == 0) { SI_ERR("max_strings must be > 0"); return 0; }
Branch: 2 branches
BranchTrueFalseTotal
if (max_strings == 0) { SI_ERR("max_strings must be > 0"); return 0; } 1 41 42
if (max_strings == 0) { SI_ERR("max_strings must be > 0"); return 0; } 1 0 1
625 41 ▶ if (max_strings > SI_MAX_STRINGS) { SI_ERR("max_strings too large (max %u)", SI_MAX_STRINGS); return 0; }
Branch: 2 branches
BranchTrueFalseTotal
if (max_strings > SI_MAX_STRINGS) { SI_ERR("max_strings too large (max %u)", SI_MAX_STRINGS); return 0; } 0 41 41
if (max_strings > SI_MAX_STRINGS) { SI_ERR("max_strings too large (max %u)", SI_MAX_STRINGS); return 0; } 0 0 0
626 41 uint64_t want = (uint64_t)max_strings * 10 / 7 + 1; /* hash load factor ~0.7 */
627 /* next_pow2(want) is always strictly > max_strings, so a probe always finds
628 an empty slot (lookup misses cannot loop forever). With max_strings capped
629 at 2^30, want <= ~1.43*2^30 < 2^31, whose next_pow2 is 2^31 -- fits uint32. */
630 41 *hash_slots = si_next_pow2((uint32_t)want);
631 41 ▶ if (*arena_bytes_io == 0) { /* default arena: 32 bytes/string */
Branch: 1 branch
BranchTrueFalseTotal
if (*arena_bytes_io == 0) { /* default arena: 32 bytes/string */ 11 30 41
632 11 uint64_t a = (uint64_t)max_strings * 32;
633 11 ▶ if (a > SI_MAX_ARENA) a = SI_MAX_ARENA;
Branch: 1 branch
BranchTrueFalseTotal
if (a > SI_MAX_ARENA) a = SI_MAX_ARENA; 0 11 11
634 11 ▶ if (a < 64) a = 64;
Branch: 1 branch
BranchTrueFalseTotal
if (a < 64) a = 64; 0 11 11
635 11 *arena_bytes_io = (uint32_t)a;
636 }
637 41 return 1;
638 }
639  
640 /* Securely obtain a fd: create exclusively (O_CREAT|O_EXCL|O_NOFOLLOW at mode,
641 * default 0600), or attach an existing file (O_RDWR|O_NOFOLLOW, no O_CREAT). */
642 28 static int si_secure_open(const char *path, mode_t mode, char *errbuf) {
643 28 ▶ for (int attempt = 0; attempt < 100; attempt++) {
Branch: 1 branch
BranchTrueFalseTotal
for (int attempt = 0; attempt < 100; attempt++) { 28 0 28
644 28 int fd = open(path, O_RDWR|O_CREAT|O_EXCL|O_NOFOLLOW|O_CLOEXEC, mode);
645 28 ▶ 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 14 28
646 14 ▶ if (errno != EEXIST) { SI_ERR("create %s: %s", path, strerror(errno)); return -1; }
Branch: 2 branches
BranchTrueFalseTotal
if (errno != EEXIST) { SI_ERR("create %s: %s", path, strerror(errno)); return -1; } 0 14 14
if (errno != EEXIST) { SI_ERR("create %s: %s", path, strerror(errno)); return -1; } 0 0 0
647 14 fd = open(path, O_RDWR|O_NOFOLLOW|O_CLOEXEC);
648 14 ▶ if (fd >= 0) return fd;
Branch: 1 branch
BranchTrueFalseTotal
if (fd >= 0) return fd; 14 0 14
649 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
650 0 ▶ SI_ERR("open %s: %s", path, strerror(errno)); /* ELOOP => symlink rejected */
Branch: 1 branch
BranchTrueFalseTotal
SI_ERR("open %s: %s", path, strerror(errno)); /* ELOOP => symlink rejected */ 0 0 0
651 0 return -1;
652 }
653 0 ▶ SI_ERR("open %s: create/attach kept racing", path);
Branch: 1 branch
BranchTrueFalseTotal
SI_ERR("open %s: create/attach kept racing", path); 0 0 0
654 0 return -1;
655 }
656  
657 /* True iff the whole file is zero -- what an abandoned mid-init
658 creator leaves. Lets recovery re-init only a provably-empty file, never
659 one that merely starts with a zero word. Cold path, so a byte scan is
660 fine. Read, not mapped: a read fault on a tmpfs hole allocates the page. */
661 2 static int si_file_is_zero(int fd, uint64_t size) {
662 char buf[16384];
663 5 ▶ for (uint64_t off = 0; off < size; ) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint64_t off = 0; off < size; ) { 4 1 5
664 4 ssize_t n = pread(fd, buf, size - off < sizeof buf ? (size_t)(size - off) : sizeof buf, (off_t)off);
665 4 ▶ if (n <= 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (n <= 0) return 0; 0 4 4
666 46627 ▶ 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 46623 46624
for (ssize_t i = 0; i < n; i++) if (buf[i]) return 0; 46624 3 46627
667 3 off += (uint64_t)n;
668 }
669 1 return 1;
670 }
671  
672 /* Opt-in (DATA_INTERN_SHARED_SPARSE=0): reserving commits memory this module otherwise fills lazily. */
673 17 static int si_reserve(int fd, uint64_t size) {
674 17 const char *sp = getenv("DATA_INTERN_SHARED_SPARSE");
675 17 ▶ if (!sp || strcmp(sp, "0")) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (!sp || strcmp(sp, "0")) return 0; 0 17 17
if (!sp || strcmp(sp, "0")) return 0; 0 0 0
676 /* Before Linux 6.11 tmpfs gives up at any pending signal and undoes the allocation, so a
677 * periodic one could keep it from ever completing; SIGSTOP cannot be blocked. */
678 sigset_t all, old;
679 0 sigfillset(&all);
680 0 sigprocmask(SIG_BLOCK, &all, &old);
681 int e;
682 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
683 0 sigprocmask(SIG_SETMASK, &old, NULL);
684 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
685 0 errno = e;
686 0 return -1;
687 }
688  
689 40 static SiHandle *si_create(const char *path, uint32_t max_strings, uint32_t arena_bytes, mode_t mode, char *errbuf) {
690 uint32_t hash_slots;
691 40 ▶ if (!si_validate_create_args(max_strings, &arena_bytes, &hash_slots, errbuf)) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!si_validate_create_args(max_strings, &arena_bytes, &hash_slots, errbuf)) return NULL; 1 39 40
692  
693 39 uint64_t total = si_total_size(hash_slots, max_strings, arena_bytes);
694 39 int anonymous = (path == NULL);
695 39 int fd = -1;
696 size_t map_size;
697 void *base;
698  
699 39 ▶ if (anonymous) {
Branch: 1 branch
BranchTrueFalseTotal
if (anonymous) { 11 28 39
700 11 map_size = (size_t)total;
701 11 base = mmap(NULL, map_size, PROT_READ|PROT_WRITE, MAP_SHARED|MAP_ANONYMOUS, -1, 0);
702 11 ▶ if (base == MAP_FAILED) { SI_ERR("mmap: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { SI_ERR("mmap: %s", strerror(errno)); return NULL; } 0 11 11
if (base == MAP_FAILED) { SI_ERR("mmap: %s", strerror(errno)); return NULL; } 0 0 0
703 } else {
704 28 fd = si_secure_open(path, mode, errbuf);
705 42 ▶ if (fd < 0) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (fd < 0) return NULL; 0 28 28
706 28 ▶ if (flock(fd, LOCK_EX) < 0) { SI_ERR("flock: %s", strerror(errno)); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (flock(fd, LOCK_EX) < 0) { SI_ERR("flock: %s", strerror(errno)); close(fd); return NULL; } 0 28 28
if (flock(fd, LOCK_EX) < 0) { SI_ERR("flock: %s", strerror(errno)); close(fd); return NULL; } 0 0 0
707 struct stat st;
708 28 ▶ if (fstat(fd, &st) < 0) { SI_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fstat(fd, &st) < 0) { SI_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; } 0 28 28
if (fstat(fd, &st) < 0) { SI_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; } 0 0 0
709 28 int is_new = (st.st_size == 0);
710 28 ▶ if (!is_new && (uint64_t)st.st_size < sizeof(SiHeader)) {
Branch: 2 branches
BranchTrueFalseTotal
if (!is_new && (uint64_t)st.st_size < sizeof(SiHeader)) { 14 14 28
if (!is_new && (uint64_t)st.st_size < sizeof(SiHeader)) { 1 13 14
711 1 ▶ SI_ERR("%s: file too small (%lld)", path, (long long)st.st_size);
Branch: 1 branch
BranchTrueFalseTotal
SI_ERR("%s: file too small (%lld)", path, (long long)st.st_size); 1 0 1
712 1 flock(fd, LOCK_UN); close(fd); return NULL;
713 }
714 27 ▶ 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 13 27
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
715 0 ▶ SI_ERR("%s: refusing to initialize file not owned by us", path);
Branch: 1 branch
BranchTrueFalseTotal
SI_ERR("%s: refusing to initialize file not owned by us", path); 0 0 0
716 0 flock(fd, LOCK_UN); close(fd); return NULL;
717 }
718 27 ▶ if (is_new && ftruncate(fd, (off_t)total) < 0) {
Branch: 2 branches
BranchTrueFalseTotal
if (is_new && ftruncate(fd, (off_t)total) < 0) { 14 13 27
if (is_new && ftruncate(fd, (off_t)total) < 0) { 0 14 14
719 0 ▶ SI_ERR("ftruncate: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
SI_ERR("ftruncate: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; 0 0 0
720 }
721 27 ▶ if (is_new && si_reserve(fd, total) < 0) {
Branch: 2 branches
BranchTrueFalseTotal
if (is_new && si_reserve(fd, total) < 0) { 14 13 27
if (is_new && si_reserve(fd, total) < 0) { 0 14 14
722 0 ▶ SI_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
SI_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno)); 0 0 0
723 0 if (ftruncate(fd, 0) < 0) { /* best effort */ }
724 0 flock(fd, LOCK_UN); close(fd); return NULL;
725 }
726 27 ▶ 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; 13 14 27
727 27 base = mmap(NULL, map_size, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
728 27 ▶ if (base == MAP_FAILED) {
Branch: 1 branch
BranchTrueFalseTotal
if (base == MAP_FAILED) { 0 27 27
729 0 ▶ SI_ERR("mmap: %s", strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
SI_ERR("mmap: %s", strerror(errno)); 0 0 0
730 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
731 0 flock(fd, LOCK_UN); close(fd); return NULL;
732 }
733 27 ▶ if (!is_new) {
Branch: 1 branch
BranchTrueFalseTotal
if (!is_new) { 13 14 27
734 13 ▶ if (!si_validate_header((SiHeader *)base, (uint64_t)st.st_size)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!si_validate_header((SiHeader *)base, (uint64_t)st.st_size)) { 4 9 13
735 /* Recover an abandoned mid-init file: a creator killed
736 * between the ftruncate and the header init leaves a
737 * full-size, all-zero (magic==0) file that would brick every
738 * future open of this path. Re-initialize ONLY when it is
739 * exactly our size, still uninitialized, and owned by us;
740 * anything else still errors. */
741 4 ▶ if (((SiHeader *)base)->magic == 0 && (uint64_t)st.st_size == total
Branch: 2 branches
BranchTrueFalseTotal
if (((SiHeader *)base)->magic == 0 && (uint64_t)st.st_size == total 3 1 4
if (((SiHeader *)base)->magic == 0 && (uint64_t)st.st_size == total 2 1 3
742 2 ▶ && st.st_uid == geteuid() && si_file_is_zero(fd, map_size)) {
Branch: 2 branches
BranchTrueFalseTotal
&& st.st_uid == geteuid() && si_file_is_zero(fd, map_size)) { 2 0 2
&& st.st_uid == geteuid() && si_file_is_zero(fd, map_size)) { 1 1 2
743 1 ▶ if (fchmod(fd, mode) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (fchmod(fd, mode) < 0) { 0 1 1
744 0 ▶ SI_ERR("%s: fchmod: %s", path, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
SI_ERR("%s: fchmod: %s", path, strerror(errno)); 0 0 0
745 0 munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
746 }
747 1 ▶ if (si_reserve(fd, total) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (si_reserve(fd, total) < 0) { 0 1 1
748 0 ▶ SI_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
SI_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno)); 0 0 0
749 0 munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
750 }
751 1 si_init_header(base, max_strings, hash_slots, arena_bytes, total);
752 1 flock(fd, LOCK_UN); close(fd);
753 1 return si_setup(base, map_size, path, -1);
754 }
755 3 ▶ if (((SiHeader *)base)->magic == 0 && (uint64_t)st.st_size == total
Branch: 2 branches
BranchTrueFalseTotal
if (((SiHeader *)base)->magic == 0 && (uint64_t)st.st_size == total 2 1 3
if (((SiHeader *)base)->magic == 0 && (uint64_t)st.st_size == total 1 1 2
756 1 ▶ && st.st_uid == geteuid()) {
Branch: 1 branch
BranchTrueFalseTotal
&& st.st_uid == geteuid()) { 1 0 1
757 1 ▶ SI_ERR("%s: incomplete intern file left by an interrupted create; remove it and retry", path);
Branch: 1 branch
BranchTrueFalseTotal
SI_ERR("%s: incomplete intern file left by an interrupted create; remove it and retry", path); 1 0 1
758 1 munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
759 }
760 2 ▶ SI_ERR("invalid intern file"); munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
SI_ERR("invalid intern file"); munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL; 2 0 2
761 }
762 9 ▶ if (__atomic_load_n(&((SiHeader *)base)->sealed, __ATOMIC_ACQUIRE)) {
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&((SiHeader *)base)->sealed, __ATOMIC_ACQUIRE)) { 1 8 9
763 1 ▶ SI_ERR("%s is frozen (read-only); open it with new_readonly", path);
Branch: 1 branch
BranchTrueFalseTotal
SI_ERR("%s is frozen (read-only); open it with new_readonly", path); 1 0 1
764 1 munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
765 }
766 8 flock(fd, LOCK_UN); close(fd);
767 8 return si_setup(base, map_size, path, -1);
768 }
769 }
770 25 si_init_header(base, max_strings, hash_slots, arena_bytes, total);
771 25 ▶ if (fd >= 0) { flock(fd, LOCK_UN); close(fd); }
Branch: 1 branch
BranchTrueFalseTotal
if (fd >= 0) { flock(fd, LOCK_UN); close(fd); } 14 11 25
772 25 return si_setup(base, map_size, path, -1);
773 }
774  
775 2 static SiHandle *si_create_memfd(const char *name, uint32_t max_strings, uint32_t arena_bytes, char *errbuf) {
776 uint32_t hash_slots;
777 2 ▶ if (!si_validate_create_args(max_strings, &arena_bytes, &hash_slots, errbuf)) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!si_validate_create_args(max_strings, &arena_bytes, &hash_slots, errbuf)) return NULL; 0 2 2
778  
779 2 uint64_t total = si_total_size(hash_slots, max_strings, arena_bytes);
780 2 ▶ int fd = memfd_create(name ? name : "intern", MFD_CLOEXEC | MFD_ALLOW_SEALING);
Branch: 1 branch
BranchTrueFalseTotal
int fd = memfd_create(name ? name : "intern", MFD_CLOEXEC | MFD_ALLOW_SEALING); 1 1 2
781 2 ▶ if (fd < 0) { SI_ERR("memfd_create: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fd < 0) { SI_ERR("memfd_create: %s", strerror(errno)); return NULL; } 0 2 2
if (fd < 0) { SI_ERR("memfd_create: %s", strerror(errno)); return NULL; } 0 0 0
782 2 ▶ if (ftruncate(fd, (off_t)total) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (ftruncate(fd, (off_t)total) < 0) { 0 2 2
783 0 ▶ SI_ERR("ftruncate: %s", strerror(errno)); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
SI_ERR("ftruncate: %s", strerror(errno)); close(fd); return NULL; 0 0 0
784 }
785 2 ▶ if (si_reserve(fd, total) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (si_reserve(fd, total) < 0) { 0 2 2
786 0 ▶ SI_ERR("memfd: cannot reserve %llu bytes: %s", (unsigned long long)total, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
SI_ERR("memfd: cannot reserve %llu bytes: %s", (unsigned long long)total, strerror(errno)); 0 0 0
787 0 close(fd); return NULL;
788 }
789 2 (void)fcntl(fd, F_ADD_SEALS, F_SEAL_SHRINK | F_SEAL_GROW);
790 2 void *base = mmap(NULL, (size_t)total, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
791 2 ▶ if (base == MAP_FAILED) { SI_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { SI_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; } 0 2 2
if (base == MAP_FAILED) { SI_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; } 0 0 0
792 2 si_init_header(base, max_strings, hash_slots, arena_bytes, total);
793 2 return si_setup(base, (size_t)total, NULL, fd);
794 }
795  
796 2 static SiHandle *si_open_fd(int fd, char *errbuf) {
797 2 ▶ if (errbuf) errbuf[0] = '\0';
Branch: 1 branch
BranchTrueFalseTotal
if (errbuf) errbuf[0] = '\0'; 2 0 2
798 struct stat st;
799 2 ▶ if (fstat(fd, &st) < 0) { SI_ERR("fstat: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fstat(fd, &st) < 0) { SI_ERR("fstat: %s", strerror(errno)); return NULL; } 0 2 2
if (fstat(fd, &st) < 0) { SI_ERR("fstat: %s", strerror(errno)); return NULL; } 0 0 0
800 2 ▶ if ((uint64_t)st.st_size < sizeof(SiHeader)) { SI_ERR("too small"); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if ((uint64_t)st.st_size < sizeof(SiHeader)) { SI_ERR("too small"); return NULL; } 0 2 2
if ((uint64_t)st.st_size < sizeof(SiHeader)) { SI_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 2 ▶ if (pread(fd, &magic, sizeof magic, offsetof(SiHeader, magic)) != (ssize_t)sizeof magic || magic != SI_MAGIC) {
Branch: 2 branches
BranchTrueFalseTotal
if (pread(fd, &magic, sizeof magic, offsetof(SiHeader, magic)) != (ssize_t)sizeof magic || magic != SI_MAGIC) { 2 0 2
if (pread(fd, &magic, sizeof magic, offsetof(SiHeader, magic)) != (ssize_t)sizeof magic || magic != SI_MAGIC) { 0 2 2
804 0 ▶ SI_ERR("invalid intern table"); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
SI_ERR("invalid intern table"); return NULL; 0 0 0
805 }
806 2 size_t ms = (size_t)st.st_size;
807 2 void *base = mmap(NULL, ms, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
808 2 ▶ if (base == MAP_FAILED) { SI_ERR("mmap: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { SI_ERR("mmap: %s", strerror(errno)); return NULL; } 0 2 2
if (base == MAP_FAILED) { SI_ERR("mmap: %s", strerror(errno)); return NULL; } 0 0 0
809 2 ▶ if (!si_validate_header((SiHeader *)base, (uint64_t)st.st_size)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!si_validate_header((SiHeader *)base, (uint64_t)st.st_size)) { 0 2 2
810 0 ▶ SI_ERR("invalid intern table"); munmap(base, ms); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
SI_ERR("invalid intern table"); munmap(base, ms); return NULL; 0 0 0
811 }
812 2 ▶ if (__atomic_load_n(&((SiHeader *)base)->sealed, __ATOMIC_ACQUIRE)) {
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&((SiHeader *)base)->sealed, __ATOMIC_ACQUIRE)) { 1 1 2
813 1 ▶ SI_ERR("this intern table is frozen (read-only); open it with new_readonly");
Branch: 1 branch
BranchTrueFalseTotal
SI_ERR("this intern table is frozen (read-only); open it with new_readonly"); 1 0 1
814 1 munmap(base, ms); return NULL;
815 }
816 1 int myfd = fcntl(fd, F_DUPFD_CLOEXEC, 0);
817 1 ▶ if (myfd < 0) { SI_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (myfd < 0) { SI_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; } 0 1 1
if (myfd < 0) { SI_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; } 0 0 0
818 1 return si_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 5 static SiHandle *si_open_readonly(const char *path, char *errbuf) {
827 5 ▶ if (errbuf) errbuf[0] = '\0';
Branch: 1 branch
BranchTrueFalseTotal
if (errbuf) errbuf[0] = '\0'; 5 0 5
828 5 int fd = open(path, O_RDONLY|O_NOFOLLOW|O_CLOEXEC);
829 5 ▶ if (fd < 0) { SI_ERR("open %s: %s", path, strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fd < 0) { SI_ERR("open %s: %s", path, strerror(errno)); return NULL; } 1 4 5
if (fd < 0) { SI_ERR("open %s: %s", path, strerror(errno)); return NULL; } 1 0 1
830 struct stat st;
831 4 ▶ if (fstat(fd, &st) < 0) { SI_ERR("fstat %s: %s", path, strerror(errno)); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fstat(fd, &st) < 0) { SI_ERR("fstat %s: %s", path, strerror(errno)); close(fd); return NULL; } 0 4 4
if (fstat(fd, &st) < 0) { SI_ERR("fstat %s: %s", path, strerror(errno)); close(fd); return NULL; } 0 0 0
832 4 ▶ if ((uint64_t)st.st_size < sizeof(SiHeader)) { SI_ERR("%s: file too small", path); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if ((uint64_t)st.st_size < sizeof(SiHeader)) { SI_ERR("%s: file too small", path); close(fd); return NULL; } 0 4 4
if ((uint64_t)st.st_size < sizeof(SiHeader)) { SI_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 4 ▶ if (pread(fd, &magic, sizeof magic, offsetof(SiHeader, magic)) != (ssize_t)sizeof magic || magic != SI_MAGIC) {
Branch: 2 branches
BranchTrueFalseTotal
if (pread(fd, &magic, sizeof magic, offsetof(SiHeader, magic)) != (ssize_t)sizeof magic || magic != SI_MAGIC) { 4 0 4
if (pread(fd, &magic, sizeof magic, offsetof(SiHeader, magic)) != (ssize_t)sizeof magic || magic != SI_MAGIC) { 0 4 4
836 0 ▶ SI_ERR("%s: invalid intern file", path); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
SI_ERR("%s: invalid intern file", path); close(fd); return NULL; 0 0 0
837 }
838 4 size_t ms = (size_t)st.st_size;
839 4 void *base = mmap(NULL, ms, PROT_READ, MAP_SHARED, fd, 0);
840 4 close(fd); /* the mapping keeps the file; a read-only view needs no fd (no msync/ftruncate) */
841 4 ▶ if (base == MAP_FAILED) { SI_ERR("mmap %s: %s", path, strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { SI_ERR("mmap %s: %s", path, strerror(errno)); return NULL; } 0 4 4
if (base == MAP_FAILED) { SI_ERR("mmap %s: %s", path, strerror(errno)); return NULL; } 0 0 0
842 4 ▶ if (!si_validate_header((SiHeader *)base, (uint64_t)st.st_size)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!si_validate_header((SiHeader *)base, (uint64_t)st.st_size)) { 0 4 4
843 0 ▶ SI_ERR("%s: invalid intern file", path); munmap(base, ms); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
SI_ERR("%s: invalid intern file", path); munmap(base, ms); return NULL; 0 0 0
844 }
845 4 ▶ if (!__atomic_load_n(&((SiHeader *)base)->sealed, __ATOMIC_ACQUIRE)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!__atomic_load_n(&((SiHeader *)base)->sealed, __ATOMIC_ACQUIRE)) { 1 3 4
846 1 ▶ SI_ERR("%s is not frozen: call ->freeze on the producer before opening read-only", path);
Branch: 1 branch
BranchTrueFalseTotal
SI_ERR("%s is not frozen: call ->freeze on the producer before opening read-only", path); 1 0 1
847 1 munmap(base, ms); return NULL;
848 }
849 3 SiHandle *h = si_setup(base, ms, path, -1); /* munmaps on OOM */
850 3 ▶ if (!h) { SI_ERR("out of memory"); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (!h) { SI_ERR("out of memory"); return NULL; } 0 3 3
if (!h) { SI_ERR("out of memory"); return NULL; } 0 0 0
851 3 h->readonly = 1;
852 3 return h;
853 }
854  
855 40 static void si_destroy(SiHandle *h) {
856 40 ▶ if (!h) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!h) return; 0 40 40
857 /* Release our reader slot on clean teardown (else short-lived-reader churn
858 * exhausts the slot table); skip if a read lock is still held (rdepth>0). */
859 40 ▶ 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 && 40 0 40
if (h->reader_slots && h->my_slot_idx != UINT32_MAX && h->cached_pid && 30 10 40
if (h->reader_slots && h->my_slot_idx != UINT32_MAX && h->cached_pid && 30 0 30
860 30 ▶ h->cached_fork_gen == __atomic_load_n(&si_fork_gen, __ATOMIC_RELAXED) &&
Branch: 1 branch
BranchTrueFalseTotal
h->cached_fork_gen == __atomic_load_n(&si_fork_gen, __ATOMIC_RELAXED) && 30 0 30
861 30 ▶ __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) { 30 0 30
862 /* Clear our occ bit BEFORE freeing the slot: we still own the pid so no
863 * claimant can take the slot mid-clear, and rdepth==0 so no writer needs
864 * to see us. (A crash skips this -> the bit is reclaimed lazily by a
865 * writer scan / re-claim, same as the pid.) */
866 30 si_occ_clear(h, h->my_slot_idx);
867 30 uint32_t expected = h->cached_pid;
868 30 __atomic_compare_exchange_n(&h->reader_slots[h->my_slot_idx].pid,
869 &expected, 0, 0, __ATOMIC_RELEASE, __ATOMIC_RELAXED);
870 }
871 40 ▶ if (h->backing_fd >= 0) close(h->backing_fd);
Branch: 1 branch
BranchTrueFalseTotal
if (h->backing_fd >= 0) close(h->backing_fd); 3 37 40
872 40 ▶ if (h->hdr) munmap(h->hdr, h->mmap_size);
Branch: 1 branch
BranchTrueFalseTotal
if (h->hdr) munmap(h->hdr, h->mmap_size); 40 0 40
873 40 free(h->path);
874 40 free(h);
875 }
876  
877 7 static inline int si_msync(SiHandle *h) {
878 7 ▶ if (!h || !h->hdr) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (!h || !h->hdr) return 0; 7 0 7
if (!h || !h->hdr) return 0; 0 7 7
879 7 return msync(h->hdr, h->mmap_size, MS_SYNC);
880 }
881  
882 /* Seal a table: make it permanently immutable so it can be shipped and opened
883 * read-only. Takes the write lock so no intern is in flight, publishes the
884 * seal, then flushes it (file/memfd-backed). Afterwards every mutator croaks
885 * and a read-write reopen is refused. */
886 4 static int si_freeze(SiHandle *h) {
887 4 si_rwlock_wrlock(h);
888 4 __atomic_store_n(&h->hdr->sealed, 1, __ATOMIC_RELEASE);
889 4 si_rwlock_wrunlock(h);
890 4 ▶ if (h->path || h->backing_fd >= 0) return si_msync(h); /* durability for file/memfd-backed */
Branch: 2 branches
BranchTrueFalseTotal
if (h->path || h->backing_fd >= 0) return si_msync(h); /* durability for file/memfd-backed */ 1 3 4
if (h->path || h->backing_fd >= 0) return si_msync(h); /* durability for file/memfd-backed */ 0 1 1
891 1 return 0; /* anonymous: the seal lives in shared memory (visible to forks); nothing to flush */
892 }
893  
894 /* ================================================================
895 * Interning (callers hold the lock)
896 * ================================================================ */
897  
898 /* reset to empty (caller holds the write lock) */
899 10 static inline void si_clear_locked(SiHandle *h) {
900 10 SiHeader *hdr = h->hdr;
901 10 __atomic_store_n(&hdr->clear_pending, 1, __ATOMIC_RELAXED);
902 10 __atomic_thread_fence(__ATOMIC_RELEASE);
903 10 hdr->count = 0;
904 10 hdr->arena_used = 0;
905 10 memset(h->slots, 0, (size_t)h->hash_slots * sizeof(SiSlot)); /* cached geometry, not peer-writable hdr->hash_slots */
906 10 __atomic_store_n(&hdr->clear_pending, 0, __ATOMIC_RELEASE);
907 10 }
908  
909 /* the string record at arena offset `off`: sets *len, returns a pointer to the
910 bytes (the uint32 length prefix is read unaligned-safely) */
911 137290 static inline const char *si_arena_str(SiHandle *h, uint32_t off, uint32_t *len) {
912 uint32_t l;
913 137290 memcpy(&l, h->arena + off, sizeof(l));
914 137290 *len = l;
915 137290 return (const char *)(h->arena + off + sizeof(uint32_t));
916 }
917  
918 /* slot for (s,n): if *found, an occupied matching slot; else the first empty
919 slot for insertion. A probe always terminates (hash_slots > max_strings >= count). */
920 131705 static inline uint32_t si_idx_find(SiHandle *h, const char *s, size_t n, uint64_t hash, int *found) {
921 131705 uint32_t hslots = h->hash_slots; /* cached geometry: masks + bounds h->slots[] */
922 131705 uint32_t mask = hslots - 1;
923 131705 uint32_t i = (uint32_t)(hash & mask);
924 131705 uint8_t want_fp = (uint8_t)(hash & 0xff);
925 /* count/arena_used are MUTABLE peer-writable header words used below as the
926 * bound gating h->reverse[id] and h->arena[off] access. Clamp each to the
927 * cached PHYSICAL array size so a corrupted (over-large) counter cannot let
928 * a crafted id/offset index past the mapped array. No-op for a valid table
929 * (count <= max_strings, arena_used <= arena_bytes always hold). */
930 131705 uint32_t count = h->hdr->count;
931 131705 ▶ if (count > h->max_strings) count = h->max_strings;
Branch: 1 branch
BranchTrueFalseTotal
if (count > h->max_strings) count = h->max_strings; 0 131705 131705
932 131705 uint32_t used = h->hdr->arena_used;
933 131705 ▶ if (used > h->arena_bytes) used = h->arena_bytes;
Branch: 1 branch
BranchTrueFalseTotal
if (used > h->arena_bytes) used = h->arena_bytes; 0 131705 131705
934 131705 uint32_t probes = 0;
935 153202 ▶ while (h->slots[i].state) {
Branch: 1 branch
BranchTrueFalseTotal
while (h->slots[i].state) { 103748 49454 153202
936 103748 ▶ if (h->slots[i].fp == want_fp) {
Branch: 1 branch
BranchTrueFalseTotal
if (h->slots[i].fp == want_fp) { 95098 8650 103748
937 /* slots[i].id, reverse[id] and the arena length prefix all come from
938 * the mmap'd file; a local peer can corrupt them. Bound each before
939 * dereferencing so a bad value skips this slot instead of trapping:
940 * id must be a live id (< count), and the record [off .. off+4+len]
941 * must lie within arena_used. For a valid table every check holds,
942 * so a real hit is never dropped. */
943 95098 uint32_t id = h->slots[i].id;
944 95098 ▶ if (id < count) {
Branch: 1 branch
BranchTrueFalseTotal
if (id < count) { 95098 0 95098
945 95098 uint32_t off = h->reverse[id];
946 95098 ▶ if (off <= used && used - off >= sizeof(uint32_t)) {
Branch: 2 branches
BranchTrueFalseTotal
if (off <= used && used - off >= sizeof(uint32_t)) { 95098 0 95098
if (off <= used && used - off >= sizeof(uint32_t)) { 95098 0 95098
947 uint32_t l;
948 95098 const char *cand = si_arena_str(h, off, &l);
949 95098 ▶ if (l <= used - off - (uint32_t)sizeof(uint32_t)
Branch: 1 branch
BranchTrueFalseTotal
if (l <= used - off - (uint32_t)sizeof(uint32_t) 95098 0 95098
950 95098 ▶ && l == n && memcmp(cand, s, n) == 0) { *found = 1; return i; }
Branch: 2 branches
BranchTrueFalseTotal
&& l == n && memcmp(cand, s, n) == 0) { *found = 1; return i; } 85558 9540 95098
&& l == n && memcmp(cand, s, n) == 0) { *found = 1; return i; } 82251 3307 85558
951 }
952 }
953 }
954 21497 i = (i + 1) & mask;
955 /* Cap the probe at the table size: a corrupted, fully-occupied slot
956 * table (every state=1) would otherwise loop forever on a miss. A valid
957 * table always has an empty slot (hash_slots > max_strings >= count). */
958 21497 ▶ if (++probes >= hslots) break;
Branch: 1 branch
BranchTrueFalseTotal
if (++probes >= hslots) break; 0 21497 21497
959 }
960 49454 *found = 0;
961 49454 return i;
962 }
963  
964 /* id of (s,n) if present: returns 1 and sets *id, else 0 */
965 77862 static inline int si_id_of_locked(SiHandle *h, const char *s, size_t n, uint32_t *id) {
966 int f;
967 77862 uint32_t i = si_idx_find(h, s, n, si_hash(s, n), &f);
968 77862 ▶ if (f) { *id = h->slots[i].id; return 1; }
Branch: 1 branch
BranchTrueFalseTotal
if (f) { *id = h->slots[i].id; return 1; } 77853 9 77862
969 9 return 0;
970 }
971  
972 /* intern (s,n): returns the id (>=0, existing or new), or -1 if the id space or
973 the arena is exhausted */
974 53843 static int64_t si_intern_locked(SiHandle *h, const char *s, size_t n) {
975 53843 SiHeader *hdr = h->hdr;
976 53843 uint64_t hash = si_hash(s, n);
977 int f;
978 53843 uint32_t slot = si_idx_find(h, s, n, hash, &f);
979 53843 ▶ if (f) return h->slots[slot].id;
Branch: 1 branch
BranchTrueFalseTotal
if (f) return h->slots[slot].id; 4398 49445 53843
980 /* Read the mutable counters ONCE and bound them against the cached PHYSICAL
981 * geometry (max_strings sizes reverse[], arena_bytes sizes arena[]); the
982 * same local is then used as the write index, so a peer that mutates the
983 * header word after the check cannot redirect the store out of bounds. */
984 49445 uint32_t id = hdr->count;
985 49445 ▶ if (id >= h->max_strings) return -1;
Branch: 1 branch
BranchTrueFalseTotal
if (id >= h->max_strings) return -1; 1 49444 49445
986 49444 uint64_t need = (uint64_t)sizeof(uint32_t) + n; /* arena cap (<= UINT32_MAX) also bounds n */
987 49444 uint32_t off = hdr->arena_used;
988 49444 ▶ if ((uint64_t)off + need > h->arena_bytes) return -1;
Branch: 1 branch
BranchTrueFalseTotal
if ((uint64_t)off + need > h->arena_bytes) return -1; 3 49441 49444
989 49441 uint32_t l = (uint32_t)n;
990 49441 memcpy(h->arena + off, &l, sizeof(l));
991 49441 ▶ if (n) memcpy(h->arena + off + sizeof(uint32_t), s, n);
Branch: 1 branch
BranchTrueFalseTotal
if (n) memcpy(h->arena + off + sizeof(uint32_t), s, n); 49439 2 49441
992 49441 hdr->arena_used += (uint32_t)need;
993 49441 h->reverse[id] = off;
994 49441 h->slots[slot].id = id;
995 49441 h->slots[slot].fp = (uint8_t)(hash & 0xff);
996 /* Crash-consistent commit order: publish the arena bytes, reverse[id] and
997 * slot id/fp, THEN commit the id (count++), THEN -- last -- make the slot
998 * findable (state=1). A writer SIGKILL'd mid-commit then leaves at worst a
999 * committed-but-unfindable id (a re-intern makes a harmless duplicate) or
1000 * a few leaked arena bytes. The old order (state=1 before count++) instead
1001 * left a FINDABLE slot whose id `count` had not advanced past, so the next
1002 * intern reused that id and collided (string(id) then returned the wrong
1003 * bytes). The release fences keep the order visible to a process that takes
1004 * the lock after dead-writer recovery. */
1005 49441 __atomic_thread_fence(__ATOMIC_RELEASE);
1006 49441 hdr->count++;
1007 49441 __atomic_thread_fence(__ATOMIC_RELEASE);
1008 49441 h->slots[slot].state = 1;
1009 49441 return id;
1010 }
1011  
1012 #endif /* INTERN_H */
« xxhash.h ↑ Summary Shared.xs »