cms.h

filter: Statementstmt 68.4% 319 / 466 Branchbran 44.1% 181 / 410 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 57.0% 500 / 876 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« xxhash.h ↑ Summary Shared.xs »
1 /*
2 * cms.h -- Shared-memory Count-Min sketch for Linux
3 *
4 * Approximate frequency estimation over a stream in fixed memory. Each item is
5 * hashed once (XXH3-128); the two 64-bit halves drive one column per row
6 * (d-row double hashing) into a d x w counter matrix (w a power of two). add
7 * increments the d cells; estimate returns the minimum of the d cells, which
8 * never underestimates the true count; double hashing makes the usual CMS
9 * probability bound approximate. The matrix lives in a shared mapping so several
10 * processes share one sketch; a write-preferring futex rwlock with reader-slot
11 * dead-process recovery guards mutation. Two sketches of equal geometry can be
12 * merged (cellwise add -> sum of streams).
13 *
14 * Layout: Header -> reader_slots[1024] -> occ bitmap -> counters[d * w]
15 */
16  
17 #ifndef CMS_H
18 #define CMS_H
19  
20 #include <stddef.h>
21 #include <stdint.h>
22 #include <stdlib.h>
23 #include <string.h>
24 #include <unistd.h>
25 #include <fcntl.h>
26 #include <errno.h>
27 #include <time.h>
28 #include <limits.h>
29 #include <signal.h>
30 #include <stdio.h>
31 #include <math.h>
32 #include <sys/mman.h>
33 #include <sys/stat.h>
34 #include <sys/file.h>
35 #include <sys/syscall.h>
36 #include <linux/futex.h>
37 #include <pthread.h>
38  
39 #define XXH_INLINE_ALL
40 #include "xxhash.h"
41  
42 #if defined(__BYTE_ORDER__) && __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
43 #error "cms.h: requires little-endian architecture"
44 #endif
45  
46  
47 /* ================================================================
48 * Constants
49 * ================================================================ */
50  
51 #define CMS_MAGIC 0x534D4F43U /* "COMS" (little-endian) */
52 #define CMS_VERSION 2 /* 2: added the occupancy bitmap region (layout change) */
53 #define CMS_ERR_BUFLEN (PATH_MAX + 256)
54 #ifndef CMS_READER_SLOTS
55 #define CMS_READER_SLOTS 1024 /* max concurrent reader processes for dead-process recovery */
56 #endif
57 /* Occupancy bitmap: one bit per reader slot, set when a process claims a slot and
58 * cleared on clean release. A writer scans these CMS_OCC_WORDS words to visit
59 * only OCCUPIED slots (O(words + live readers)) instead of all CMS_READER_SLOTS. */
60 #define CMS_OCC_WORDS (((CMS_READER_SLOTS) + 63) / 64) /* 16 for 1024 slots */
61 #define CMS_OCC_BYTES ((uint64_t)CMS_OCC_WORDS * 8) /* 128 bytes */
62 #define CMS_MIN_W 2 /* floor on the column count (power of two) */
63 #define CMS_MAX_W 0x100000000ULL /* 2^32 columns cap */
64 #define CMS_MIN_D 1
65 #define CMS_MAX_D 32
66  
67 #define CMS_ERR(fmt, ...) do { if (errbuf) snprintf(errbuf, CMS_ERR_BUFLEN, fmt, ##__VA_ARGS__); } while (0)
68  
69 /* ================================================================
70 * Structs
71 * ================================================================ */
72  
73 /* Per-process slot for dead-process recovery. In the reader-slots-only rwlock a
74 * reader's ENTIRE contribution to the shared lock is `rdepth` in its OWN slot --
75 * there is no separate shared reader counter to fall out of sync with it -- so a
76 * dead reader's contribution is exactly this one word, which a draining writer
77 * neutralises by clearing the slot's pid (the scan then ignores the slot). No
78 * orphaned counter can exist, so there is no quiescent force-reset and sustained
79 * readers cannot starve a writer. _rsv1/_rsv2 are kept only to preserve the
80 * 16-byte slot size across the already-released builds. */
81 typedef struct {
82 uint32_t pid; /* 0 = unclaimed */
83 uint32_t rdepth; /* read-locks THIS process currently holds (recursion-safe) */
84 uint32_t _rsv1; /* reserved (was waiters_parked); unused, kept for layout size */
85 uint32_t _rsv2; /* reserved (was writers_parked); unused, kept for layout size */
86 } CmsReaderSlot;
87  
88 struct CmsHeader {
89 uint32_t magic, version; /* 0,4 */
90 uint32_t d; /* 8 rows (hash functions), in [1,32] */
91 uint32_t _pad0; /* 12 */
92 uint64_t w; /* 16 columns (power of two) */
93 uint64_t mask; /* 24 w - 1 (column index mask) */
94 uint64_t total; /* 32 sum of all increments (for stats) */
95 uint64_t total_size; /* 40 */
96 uint64_t reader_slots_off; /* 48 */
97 uint64_t counters_off; /* 56 */
98 uint32_t wlock; /* 64 WRITER word ONLY: 0 (free) or WRITER_BIT|pid. NOT a reader count. */
99 uint32_t rwait; /* 68 parked-waiter hint (readers+writers blocked on wlock); over-count-safe */
100 uint32_t drain_seq; /* 72 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; /* 80 */
103 uint8_t sealed; /* 88 0 = mutable, 1 = frozen (read-only; lock-free reads) */
104 uint8_t _pad[167]; /* 89..255 */
105 };
106 typedef struct CmsHeader CmsHeader;
107  
108 _Static_assert(sizeof(CmsHeader) == 256, "CmsHeader must be 256 bytes");
109  
110 /* ---- Process-local handle ---- */
111  
112 typedef struct CmsHandle {
113 CmsHeader *hdr;
114 CmsReaderSlot *reader_slots; /* CMS_READER_SLOTS entries */
115 uint64_t *occ; /* CMS_OCC_WORDS-word slot-occupancy bitmap (trusted layout offset) */
116 void *base; /* mmap base */
117 size_t mmap_size;
118 char *path; /* backing file path (strdup'd) */
119 int backing_fd; /* memfd or reopened-fd to close on destroy, -1 for file/anon */
120 uint32_t my_slot_idx; /* UINT32_MAX if all slots taken (no recovery for this handle) */
121 uint32_t cached_pid; /* getpid() cached at last slot claim */
122 uint32_t cached_fork_gen; /* cms_fork_gen value at last slot claim */
123 uint32_t slotless_held; /* read-locks this process holds with no reader-slot */
124 int readonly; /* 1 = frozen O_RDONLY/PROT_READ view: lock-free reads, mutation croaks */
125 } CmsHandle;
126  
127 /* ================================================================
128 * Futex-based write-preferring read-write lock (reader-slots-only)
129 * with dead-process recovery
130 *
131 * The reader count is NOT stored in a shared counter. It is DISTRIBUTED across
132 * per-process reader slots: each slot's `rdepth` is that process's entire
133 * contribution to the lock. A reader publishes its presence in its own slot and
134 * then re-checks the writer word; a writer publishes the writer word and then
135 * scans every slot until all live readers' rdepth reach 0. Sequentially-
136 * consistent store+load on each side (a Dekker handshake) gives mutual exclusion.
137 *
138 * Because a reader's whole contribution is ONE atomic word owned by ONE process,
139 * a crashed reader is recovered by clearing that one slot (CAS its pid to 0) --
140 * there is no second counter to strand, no orphaned +1, and therefore no
141 * quiescent force-reset. A reader killed anywhere in rdlock/rdunlock leaves at
142 * most `rdepth>0` in its dead slot, which the draining writer clears directly, so
143 * sustained read traffic can never starve a writer. Write-preference is inherent
144 * in the gate (new readers see wlock!=0 and yield), so there is no reader-count
145 * yield hack.
146 * ================================================================ */
147  
148 #define CMS_RWLOCK_SPIN_LIMIT 32
149 #define CMS_LOCK_TIMEOUT_SEC 2 /* FUTEX_WAIT timeout for stale-lock detection / drain re-scan */
150  
151 0 static inline void cms_rwlock_spin_pause(void) {
152 #if defined(__x86_64__) || defined(__i386__)
153 0 __asm__ volatile("pause" ::: "memory");
154 #elif defined(__aarch64__)
155 __asm__ volatile("yield" ::: "memory");
156 #else
157 __asm__ volatile("" ::: "memory");
158 #endif
159 0 }
160  
161 /* Writer word encoding: WRITER_BIT|pid when write-locked, 0 when free. */
162 #define CMS_RWLOCK_WRITER_BIT 0x80000000U
163 #define CMS_RWLOCK_PID_MASK 0x7FFFFFFFU
164 #define CMS_RWLOCK_WR(pid) (CMS_RWLOCK_WRITER_BIT | ((uint32_t)(pid) & CMS_RWLOCK_PID_MASK))
165  
166 /* A zombie (dead but not yet reaped) still answers kill(pid,0) as alive, so a
167 * process that crashed while holding the lock and lingers unreaped would never
168 * be recovered. Treat /proc/<pid>/stat state 'Z' as dead. Linux-only (as is
169 * this module); if /proc is unreadable we fall back to "alive" (safe: we never
170 * force-recover a possibly-live holder). */
171 0 static inline int cms_pid_is_zombie(uint32_t pid) {
172 char path[32], buf[256];
173 0 snprintf(path, sizeof(path), "/proc/%u/stat", (unsigned)pid);
174 0 int fd = open(path, O_RDONLY | O_CLOEXEC);
175 0 ▶ if (fd < 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (fd < 0) return 0; 0 0 0
176 0 ssize_t n = read(fd, buf, sizeof(buf) - 1);
177 0 close(fd);
178 0 ▶ if (n <= 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (n <= 0) return 0; 0 0 0
179 0 buf[n] = '\0';
180 /* "pid (comm) state ..."; comm may contain ')', so scan to the last one. */
181 0 char *rp = strrchr(buf, ')');
182 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
183 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
184 }
185 /* 1 if alive or unknown, 0 if definitely dead. Cannot detect PID reuse: a
186 * recycled PID reports "alive" and the slot is not reclaimed until that
187 * process exits. See "Crash Safety" in the POD. */
188 0 static inline int cms_pid_alive(uint32_t pid) {
189 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
190 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
191 0 return !cms_pid_is_zombie(pid); /* kill() also succeeds for a zombie -> treat as dead */
192 }
193  
194 /* Force-recover a stale WRITE lock left by a dead writer (held or mid-drain).
195 * CAS to OUR pid to hold the lock while fixing shared state, then release.
196 * Using our pid (not a bare WRITER_BIT sentinel) means a subsequent recovering
197 * process can detect and re-recover if we crash mid-recovery. */
198 0 static inline void cms_recover_stale_lock(CmsHandle *h, uint32_t observed_wlock) {
199 0 CmsHeader *hdr = h->hdr;
200 0 uint32_t mypid = CMS_RWLOCK_WR((uint32_t)getpid());
201 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
202 mypid, 0, __ATOMIC_ACQUIRE, __ATOMIC_RELAXED))
203 0 return;
204 /* We now hold the write lock as mypid. No additional shared state needs
205 * repair here (this module has no seqlock); just release the lock. */
206 0 __atomic_store_n(&hdr->wlock, 0, __ATOMIC_RELEASE);
207 0 ▶ if (__atomic_load_n(&hdr->rwait, __ATOMIC_RELAXED) > 0)
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&hdr->rwait, __ATOMIC_RELAXED) > 0) 0 0 0
208 0 syscall(SYS_futex, &hdr->wlock, FUTEX_WAKE, INT_MAX, NULL, NULL, 0);
209 }
210  
211 static const struct timespec cms_lock_timeout = { CMS_LOCK_TIMEOUT_SEC, 0 };
212  
213 /* Process-global fork-generation counter. Incremented in the pthread_atfork
214 * child callback so every open handle detects a fork transition on the next
215 * lock call without paying a getpid() syscall on the hot path. */
216 static uint32_t cms_fork_gen = 1;
217 static pthread_once_t cms_atfork_once = PTHREAD_ONCE_INIT;
218 0 static void cms_on_fork_child(void) {
219 0 __atomic_add_fetch(&cms_fork_gen, 1, __ATOMIC_RELAXED);
220 0 }
221 4 static void cms_atfork_init(void) {
222 4 pthread_atfork(NULL, NULL, cms_on_fork_child);
223 4 }
224  
225 /* Ensure this process owns a reader slot. Called from the lock helpers so
226 * that fork()'d children pick up their own slot lazily instead of sharing
227 * the parent's. Hot-path is a single relaxed load + compare; only on a
228 * fork-generation mismatch do we touch getpid() and scan slots. */
229 /* Occupancy bitmap: set a slot's bit when it is claimed, clear it on clean
230 * release. SEQ_CST so a set bit is ordered before the slot's rdepth can go
231 * non-zero (bit set in claim, which precedes any rdlock), letting a writer's
232 * SEQ_CST bitmap scan never miss a slot a committed reader holds. */
233 28 static inline void cms_occ_set(CmsHandle *h, uint32_t s) {
234 28 __atomic_fetch_or(&h->occ[s >> 6], (uint64_t)1 << (s & 63), __ATOMIC_SEQ_CST);
235 28 }
236 28 static inline void cms_occ_clear(CmsHandle *h, uint32_t s) {
237 28 __atomic_fetch_and(&h->occ[s >> 6], ~((uint64_t)1 << (s & 63)), __ATOMIC_SEQ_CST);
238 28 }
239  
240 16408 static inline void cms_claim_reader_slot(CmsHandle *h) {
241 16408 uint32_t cur_gen = __atomic_load_n(&cms_fork_gen, __ATOMIC_RELAXED);
242 16408 ▶ 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)) 16380 28 16408
if (__builtin_expect(cur_gen == h->cached_fork_gen && h->my_slot_idx != UINT32_MAX, 1)) 16380 0 16380
243 16380 return;
244 /* Cold path -- register the atfork hook once per process, then claim. */
245 28 pthread_once(&cms_atfork_once, cms_atfork_init);
246 /* Re-read after pthread_once: cms_on_fork_child may have bumped it. */
247 28 cur_gen = __atomic_load_n(&cms_fork_gen, __ATOMIC_RELAXED);
248 28 uint32_t now_pid = (uint32_t)getpid();
249 28 h->cached_pid = now_pid;
250 28 ▶ 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 */ 28 0 28
251 28 h->cached_fork_gen = cur_gen;
252 28 h->my_slot_idx = UINT32_MAX;
253 28 uint32_t start = now_pid % CMS_READER_SLOTS;
254 /* Pass 1: take a free slot. */
255 29 ▶ for (uint32_t i = 0; i < CMS_READER_SLOTS; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t i = 0; i < CMS_READER_SLOTS; i++) { 29 0 29
256 29 uint32_t s = (start + i) % CMS_READER_SLOTS;
257 29 uint32_t expected = 0;
258 29 ▶ if (__atomic_compare_exchange_n(&h->reader_slots[s].pid,
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_compare_exchange_n(&h->reader_slots[s].pid, 28 1 29
259 &expected, now_pid, 0,
260 __ATOMIC_ACQUIRE, __ATOMIC_RELAXED)) {
261 /* Fresh owner holds no read locks yet; clear any stale rdepth left by
262 * a dead predecessor (its contribution is dropped as we take over). */
263 28 __atomic_store_n(&h->reader_slots[s].rdepth, 0, __ATOMIC_RELAXED);
264 28 cms_occ_set(h, s); /* mark occupied BEFORE any rdlock can bump rdepth */
265 28 h->my_slot_idx = s;
266 28 return;
267 }
268 }
269 /* Pass 2: no free slot -- reclaim one whose owner is dead. Safe to take even
270 * if its rdepth>0: clearing pid drops the dead reader's entire contribution
271 * (a writer scan ignores rdepth when pid==0) and we reset rdepth to 0 as we
272 * claim it. */
273 0 ▶ for (uint32_t i = 0; i < CMS_READER_SLOTS; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t i = 0; i < CMS_READER_SLOTS; i++) { 0 0 0
274 0 uint32_t dpid = __atomic_load_n(&h->reader_slots[i].pid, __ATOMIC_ACQUIRE);
275 0 ▶ if (dpid == 0 || dpid == now_pid || cms_pid_alive(dpid)) continue;
Branch: 3 branches
BranchTrueFalseTotal
if (dpid == 0 || dpid == now_pid || cms_pid_alive(dpid)) continue; 0 0 0
if (dpid == 0 || dpid == now_pid || cms_pid_alive(dpid)) continue; 0 0 0
if (dpid == 0 || dpid == now_pid || cms_pid_alive(dpid)) continue; 0 0 0
276 0 uint32_t expected = dpid;
277 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
278 __ATOMIC_ACQUIRE, __ATOMIC_RELAXED)) {
279 0 __atomic_store_n(&h->reader_slots[i].rdepth, 0, __ATOMIC_RELAXED);
280 0 cms_occ_set(h, i);
281 0 h->my_slot_idx = i;
282 0 return;
283 }
284 }
285 /* Table full -- leave my_slot_idx = UINT32_MAX so this handle takes the
286 * slotless path (lock still works; recovery of THIS reader's death is the
287 * documented slotless limitation). */
288 }
289  
290 /* Inspect the writer word after a futex-wait timeout. If a dead writer holds
291 * it, force-recover. Dead READERS need no action here: only a writer that owns
292 * wlock drains readers, and it clears dead readers inline in its own scan. */
293 0 static inline void cms_recover_after_timeout(CmsHandle *h) {
294 0 uint32_t val = __atomic_load_n(&h->hdr->wlock, __ATOMIC_RELAXED);
295 0 ▶ if (val >= CMS_RWLOCK_WRITER_BIT) {
Branch: 1 branch
BranchTrueFalseTotal
if (val >= CMS_RWLOCK_WRITER_BIT) { 0 0 0
296 0 uint32_t pid = val & CMS_RWLOCK_PID_MASK;
297 0 ▶ if (!cms_pid_alive(pid))
Branch: 1 branch
BranchTrueFalseTotal
if (!cms_pid_alive(pid)) 0 0 0
298 0 cms_recover_stale_lock(h, val);
299 }
300 0 }
301  
302 /* Bump/drop the parked-waiter hint. Both readers (blocked at the gate) and
303 * writers (blocked acquiring wlock) wait on the wlock futex and use this, so
304 * wrunlock/recover know whether a FUTEX_WAKE is worth a syscall. A waiter
305 * SIGKILLed while parked leaves rwait over-counted -> at most a spurious wake
306 * (harmless); it can never under-count, so no wakeup is lost. */
307 0 static inline void cms_park(CmsHandle *h) {
308 0 __atomic_add_fetch(&h->hdr->rwait, 1, __ATOMIC_RELAXED);
309 0 }
310 0 static inline void cms_unpark(CmsHandle *h) {
311 0 __atomic_sub_fetch(&h->hdr->rwait, 1, __ATOMIC_RELAXED);
312 0 }
313  
314 /* Publish (inc) / retract (dec) this reader's presence -- its ENTIRE
315 * contribution to the lock. A slotted reader uses its slot's rdepth; a reader
316 * that could not claim a slot uses the global slotless_rdepth. inc() is SEQ_CST
317 * so the wlock re-check that follows it in rdlock forms a Dekker handshake with
318 * the writer's SEQ_CST wlock-store + rdepth-scan. leave() peels slotless first
319 * so a slot claimed mid-hold cannot misattribute the decrement. */
320 9448 static inline void cms_rdepth_inc(CmsHandle *h) {
321 9448 ▶ if (h->my_slot_idx != UINT32_MAX) {
Branch: 1 branch
BranchTrueFalseTotal
if (h->my_slot_idx != UINT32_MAX) { 9448 0 9448
322 9448 __atomic_add_fetch(&h->reader_slots[h->my_slot_idx].rdepth, 1, __ATOMIC_SEQ_CST);
323 } else {
324 0 __atomic_add_fetch(&h->hdr->slotless_rdepth, 1, __ATOMIC_SEQ_CST);
325 0 h->slotless_held++;
326 }
327 9448 }
328 9448 static inline void cms_rdepth_dec(CmsHandle *h) {
329 9448 ▶ if (h->slotless_held > 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (h->slotless_held > 0) { 0 9448 9448
330 0 h->slotless_held--;
331 0 __atomic_sub_fetch(&h->hdr->slotless_rdepth, 1, __ATOMIC_RELEASE);
332 9448 ▶ } else if (h->my_slot_idx != UINT32_MAX) {
Branch: 1 branch
BranchTrueFalseTotal
} else if (h->my_slot_idx != UINT32_MAX) { 9448 0 9448
333 9448 __atomic_sub_fetch(&h->reader_slots[h->my_slot_idx].rdepth, 1, __ATOMIC_RELEASE);
334 }
335 9448 }
336  
337 /* Wake a writer that may be draining readers (it waits on drain_seq). Called
338 * after every rdepth decrement so a released read lock lets the writer re-scan
339 * promptly instead of waiting out its timeout. */
340 9448 static inline void cms_reader_wake_drain(CmsHandle *h) {
341 9448 ▶ 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 9448 9448
342 0 __atomic_add_fetch(&h->hdr->drain_seq, 1, __ATOMIC_RELEASE);
343 0 syscall(SYS_futex, &h->hdr->drain_seq, FUTEX_WAKE, 1, NULL, NULL, 0);
344 }
345 9448 }
346  
347 9448 static inline void cms_rwlock_rdlock(CmsHandle *h) {
348 9448 cms_claim_reader_slot(h);
349 9448 CmsHeader *hdr = h->hdr;
350 9448 for (int spin = 0; ; spin++) {
351 9448 uint32_t cur = __atomic_load_n(&hdr->wlock, __ATOMIC_ACQUIRE);
352 9448 ▶ if (cur == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (cur == 0) { 9448 0 9448
353 /* Optimistically take the read: publish rdepth, then re-check wlock.
354 * SEQ_CST inc + SEQ_CST load vs the writer's SEQ_CST wlock CAS +
355 * SEQ_CST rdepth scan: by the single total order of SEQ_CST ops the
356 * two sides cannot both miss each other, so we never hold
357 * concurrently with a writer. */
358 9448 cms_rdepth_inc(h);
359 9448 ▶ if (__atomic_load_n(&hdr->wlock, __ATOMIC_SEQ_CST) == 0)
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&hdr->wlock, __ATOMIC_SEQ_CST) == 0) 9448 0 9448
360 9448 return; /* no writer after our publish -> we hold the read lock */
361 /* A writer appeared during our publish -- yield to it (write-preferring). */
362 0 cms_rdepth_dec(h);
363 0 cms_reader_wake_drain(h); /* let the draining writer see rdepth drop */
364 0 spin = 0;
365 0 continue;
366 }
367 /* wlock != 0: a writer holds or is acquiring. Recover if it is dead. */
368 0 if (cur >= CMS_RWLOCK_WRITER_BIT &&
369 0 !cms_pid_alive(cur & CMS_RWLOCK_PID_MASK)) {
370 0 cms_recover_stale_lock(h, cur);
371 0 spin = 0;
372 0 continue;
373 }
374 0 ▶ if (__builtin_expect(spin < CMS_RWLOCK_SPIN_LIMIT, 1)) {
Branch: 1 branch
BranchTrueFalseTotal
if (__builtin_expect(spin < CMS_RWLOCK_SPIN_LIMIT, 1)) { 0 0 0
375 0 cms_rwlock_spin_pause();
376 0 continue;
377 }
378 0 cms_park(h);
379 0 cur = __atomic_load_n(&hdr->wlock, __ATOMIC_RELAXED);
380 0 ▶ if (cur != 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (cur != 0) { 0 0 0
381 0 long rc = syscall(SYS_futex, &hdr->wlock, FUTEX_WAIT, cur,
382 &cms_lock_timeout, NULL, 0);
383 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
384 0 cms_unpark(h);
385 0 cms_recover_after_timeout(h);
386 0 spin = 0;
387 0 continue;
388 }
389 }
390 0 cms_unpark(h);
391 0 spin = 0;
392 }
393 }
394  
395 9448 static inline void cms_rwlock_rdunlock(CmsHandle *h) {
396 9448 cms_rdepth_dec(h); /* RELEASE: drop our entire contribution */
397 9448 cms_reader_wake_drain(h); /* if a writer is draining, wake it to re-scan */
398 9448 }
399  
400 6960 static inline void cms_rwlock_wrlock(CmsHandle *h) {
401 6960 cms_claim_reader_slot(h); /* refresh cached_pid across fork */
402 6960 CmsHeader *hdr = h->hdr;
403 /* Encode PID in the wlock word itself (0x80000000 | pid) to eliminate any
404 * crash window between acquiring the lock and storing the owner. */
405 6960 uint32_t mypid = CMS_RWLOCK_WR(h->cached_pid);
406 /* Phase 1: acquire the writer word (mutual exclusion among writers). */
407 6960 for (int spin = 0; ; spin++) {
408 6960 uint32_t expected = 0;
409 6960 ▶ if (__atomic_compare_exchange_n(&hdr->wlock, &expected, mypid,
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_compare_exchange_n(&hdr->wlock, &expected, mypid, 6960 0 6960
410 0, __ATOMIC_SEQ_CST, __ATOMIC_RELAXED))
411 6960 break;
412 /* Contended: expected now holds the current wlock value. */
413 0 if (expected >= CMS_RWLOCK_WRITER_BIT &&
414 0 !cms_pid_alive(expected & CMS_RWLOCK_PID_MASK)) {
415 0 cms_recover_stale_lock(h, expected);
416 0 spin = 0;
417 0 continue;
418 }
419 0 ▶ if (__builtin_expect(spin < CMS_RWLOCK_SPIN_LIMIT, 1)) {
Branch: 1 branch
BranchTrueFalseTotal
if (__builtin_expect(spin < CMS_RWLOCK_SPIN_LIMIT, 1)) { 0 0 0
420 0 cms_rwlock_spin_pause();
421 0 continue;
422 }
423 0 cms_park(h);
424 0 uint32_t cur = __atomic_load_n(&hdr->wlock, __ATOMIC_RELAXED);
425 0 ▶ if (cur != 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (cur != 0) { 0 0 0
426 0 long rc = syscall(SYS_futex, &hdr->wlock, FUTEX_WAIT, cur,
427 &cms_lock_timeout, NULL, 0);
428 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
429 0 cms_unpark(h);
430 0 cms_recover_after_timeout(h);
431 0 spin = 0;
432 0 continue;
433 }
434 }
435 0 cms_unpark(h);
436 0 spin = 0;
437 }
438 /* Phase 2: we own wlock, so no NEW reader can join (they see wlock!=0 and
439 * yield). Drain the readers that were already holding when we won the CAS.
440 * The SEQ_CST CAS above + the SEQ_CST rdepth loads below are the writer side
441 * of the Dekker handshake. */
442 0 for (;;) {
443 6960 uint32_t v = __atomic_load_n(&hdr->drain_seq, __ATOMIC_ACQUIRE); /* snapshot BEFORE scan */
444 6960 int busy = 0;
445 /* Visit only OCCUPIED slots via the occupancy bitmap (SEQ_CST: a committed
446 * reader's bit -- set in claim, before its rdepth++ -- is ordered before
447 * this scan, so no held slot is skipped). O(CMS_OCC_WORDS + live readers)
448 * instead of O(CMS_READER_SLOTS). */
449 118320 ▶ for (uint32_t wd = 0; wd < CMS_OCC_WORDS; wd++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t wd = 0; wd < CMS_OCC_WORDS; wd++) { 111360 6960 118320
450 111360 uint64_t word = __atomic_load_n(&h->occ[wd], __ATOMIC_SEQ_CST);
451 118324 ▶ while (word) {
Branch: 1 branch
BranchTrueFalseTotal
while (word) { 6964 111360 118324
452 6964 uint32_t i = (wd << 6) + (uint32_t)__builtin_ctzll(word);
453 6964 word &= word - 1; /* consume this bit (local copy) */
454 6964 uint32_t rd = __atomic_load_n(&h->reader_slots[i].rdepth, __ATOMIC_SEQ_CST);
455 6964 ▶ if (rd == 0) continue; /* occupied but not read-locking now */
Branch: 1 branch
BranchTrueFalseTotal
if (rd == 0) continue; /* occupied but not read-locking now */ 6964 0 6964
456 0 uint32_t pid = __atomic_load_n(&h->reader_slots[i].pid, __ATOMIC_ACQUIRE);
457 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
458 0 ▶ if (!cms_pid_alive(pid)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!cms_pid_alive(pid)) { 0 0 0
459 /* Dead reader: drop its pid so the slot no longer counts. Leave
460 * the occ bit set (harmless -- a later scan hits pid==0 and skips,
461 * a re-claim re-sets it) to avoid racing a concurrent claimant. */
462 0 uint32_t ep = pid;
463 0 __atomic_compare_exchange_n(&h->reader_slots[i].pid, &ep, 0,
464 0, __ATOMIC_ACQ_REL, __ATOMIC_RELAXED);
465 0 continue;
466 }
467 0 busy = 1; /* live reader still holding */
468 }
469 }
470 /* A live slotless reader keeps us waiting; a crashed slotless reader that
471 * cannot be attributed to a pid is the documented slotless limitation. */
472 6960 ▶ 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 6960 6960
473 0 busy = 1;
474 6960 ▶ if (!busy)
Branch: 1 branch
BranchTrueFalseTotal
if (!busy) 6960 0 6960
475 6960 return; /* exclusive: wlock held + every rdepth 0 */
476 /* Wait for a reader to release (drain_seq bump) or time out to re-scan
477 * (which reclaims any newly-dead slotted reader). */
478 0 syscall(SYS_futex, &hdr->drain_seq, FUTEX_WAIT, v, &cms_lock_timeout, NULL, 0);
479 }
480 }
481  
482 6960 static inline void cms_rwlock_wrunlock(CmsHandle *h) {
483 6960 CmsHeader *hdr = h->hdr;
484 6960 __atomic_store_n(&hdr->wlock, 0, __ATOMIC_RELEASE);
485 6960 ▶ if (__atomic_load_n(&hdr->rwait, __ATOMIC_RELAXED) > 0)
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&hdr->rwait, __ATOMIC_RELAXED) > 0) 0 6960 6960
486 0 syscall(SYS_futex, &hdr->wlock, FUTEX_WAKE, INT_MAX, NULL, NULL, 0);
487 6960 }
488  
489 /* ================================================================
490 * Layout math + create / open / destroy
491 *
492 * Layout: Header -> reader_slots[1024] -> occ bitmap -> counters[d * w]
493 * ================================================================ */
494  
495 /* Single source of truth for the mmap region layout offsets:
496 * Header -> reader_slots[] -> occ bitmap -> counters. */
497 typedef struct { uint64_t reader_slots, occ, counters; } CmsLayout;
498  
499 192 static inline CmsLayout cms_layout(void) {
500 CmsLayout L;
501 192 L.reader_slots = sizeof(CmsHeader);
502 192 L.occ = L.reader_slots + (uint64_t)CMS_READER_SLOTS * sizeof(CmsReaderSlot);
503 192 L.counters = L.occ + CMS_OCC_BYTES;
504 192 L.counters = (L.counters + 7) & ~(uint64_t)7; /* 8-byte align the counter matrix (uint64_t words) */
505 192 return L;
506 }
507  
508 55 static inline uint64_t cms_total_size(uint64_t w, uint32_t d) {
509 55 CmsLayout L = cms_layout();
510 55 return L.counters + (uint64_t)d * w * sizeof(uint64_t); /* d*w uint64_t cells */
511 }
512  
513 /* round v up to the next power of two (64-bit), with a floor of CMS_MIN_W */
514 44 static inline uint64_t cms_next_pow2_u64(uint64_t v) {
515 44 ▶ if (v <= CMS_MIN_W) return CMS_MIN_W;
Branch: 1 branch
BranchTrueFalseTotal
if (v <= CMS_MIN_W) return CMS_MIN_W; 0 44 44
516 44 return 1ULL << (64 - __builtin_clzll(v - 1));
517 }
518  
519 36 static inline void cms_init_header(void *base, uint64_t w, uint32_t d,
520 uint64_t total_size) {
521 36 CmsLayout L = cms_layout();
522 36 CmsHeader *hdr = (CmsHeader *)base;
523 /* Explicitly zero the header + reader-slot region (lock-recovery state);
524 the counter matrix relies on the fresh mapping being OS zero-filled. */
525 36 memset(base, 0, (size_t)L.counters);
526 36 hdr->version = CMS_VERSION;
527 36 hdr->d = d;
528 36 hdr->w = w;
529 36 hdr->mask = w - 1;
530 36 hdr->total = 0;
531 36 hdr->total_size = total_size;
532 36 hdr->reader_slots_off = L.reader_slots;
533 36 hdr->counters_off = L.counters;
534 /* Publish magic LAST, as a release store: it is the commit point, so a
535 creator killed before it leaves magic==0 and never a file mistaken for
536 a valid one. A kill during the field stores leaves one to remove by
537 hand. */
538 36 __atomic_store_n(&hdr->magic, CMS_MAGIC, __ATOMIC_RELEASE);
539 36 __atomic_thread_fence(__ATOMIC_SEQ_CST);
540 36 }
541  
542 static inline uint64_t *cms_counters(CmsHandle *h) {
543 return (uint64_t *)((char *)h->base + h->hdr->counters_off);
544 }
545  
546 45 static inline CmsHandle *cms_setup(void *base, size_t map_size,
547 const char *path, int backing_fd) {
548 45 CmsHeader *hdr = (CmsHeader *)base;
549 45 CmsHandle *h = (CmsHandle *)calloc(1, sizeof(CmsHandle));
550 45 ▶ if (!h) {
Branch: 1 branch
BranchTrueFalseTotal
if (!h) { 0 45 45
551 0 munmap(base, map_size);
552 0 ▶ if (backing_fd >= 0) close(backing_fd);
Branch: 1 branch
BranchTrueFalseTotal
if (backing_fd >= 0) close(backing_fd); 0 0 0
553 0 return NULL;
554 }
555 45 h->hdr = hdr;
556 45 h->base = base;
557 /* Derive reader_slots from the trusted fixed layout, not the stored
558 * (shared-segment, attacker-mutable) reader_slots_off. validate_header
559 * requires reader_slots_off to equal this for any file we open, so this is
560 * identical for valid data and never trusts a poisoned offset. */
561 45 h->reader_slots = (CmsReaderSlot *)((uint8_t *)base + cms_layout().reader_slots);
562 45 h->occ = (uint64_t *)((uint8_t *)base + cms_layout().occ); /* trusted layout offset */
563 45 h->mmap_size = map_size;
564 45 ▶ h->path = path ? strdup(path) : NULL;
Branch: 1 branch
BranchTrueFalseTotal
h->path = path ? strdup(path) : NULL; 19 26 45
565 45 h->backing_fd = backing_fd;
566 45 h->my_slot_idx = UINT32_MAX;
567 45 return h;
568 }
569  
570 /* Validate a mapped header (shared by cms_create reopen and cms_open_fd). */
571 15 static inline int cms_validate_header(const CmsHeader *hdr, uint64_t file_size) {
572 15 ▶ if (hdr->magic != CMS_MAGIC) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->magic != CMS_MAGIC) return 0; 4 11 15
573 11 ▶ if (hdr->version != CMS_VERSION) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->version != CMS_VERSION) return 0; 0 11 11
574 11 ▶ if (hdr->d < CMS_MIN_D || hdr->d > CMS_MAX_D) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (hdr->d < CMS_MIN_D || hdr->d > CMS_MAX_D) return 0; 11 0 11
if (hdr->d < CMS_MIN_D || hdr->d > CMS_MAX_D) return 0; 0 11 11
575 11 ▶ if (hdr->w < CMS_MIN_W || hdr->w > CMS_MAX_W) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (hdr->w < CMS_MIN_W || hdr->w > CMS_MAX_W) return 0; 11 0 11
if (hdr->w < CMS_MIN_W || hdr->w > CMS_MAX_W) return 0; 0 11 11
576 11 ▶ if ((hdr->w & (hdr->w - 1)) != 0) return 0; /* power of two */
Branch: 1 branch
BranchTrueFalseTotal
if ((hdr->w & (hdr->w - 1)) != 0) return 0; /* power of two */ 0 11 11
577 11 ▶ if (hdr->mask != hdr->w - 1) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->mask != hdr->w - 1) 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 != cms_total_size(hdr->w, hdr->d)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->total_size != cms_total_size(hdr->w, hdr->d)) return 0; 0 11 11
580 11 CmsLayout L = cms_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->counters_off != L.counters) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->counters_off != L.counters) return 0; 0 11 11
583 11 return 1;
584 }
585  
586 /* validate args + compute the geometry (w, d).
587 * w = next_pow2(ceil(M_E / epsilon)), floor CMS_MIN_W, cap CMS_MAX_W
588 * d = ceil(log(1 / delta)) clamped to [1, 32] */
589 52 static int cms_validate_create_args(double epsilon, double delta,
590 uint64_t *w_out, uint32_t *d_out, char *errbuf) {
591 52 ▶ if (errbuf) errbuf[0] = '\0';
Branch: 1 branch
BranchTrueFalseTotal
if (errbuf) errbuf[0] = '\0'; 52 0 52
592 52 ▶ if (!(epsilon > 0.0 && epsilon < 1.0)) { CMS_ERR("epsilon must be between 0 and 1 (exclusive)"); return 0; }
Branch: 3 branches
BranchTrueFalseTotal
if (!(epsilon > 0.0 && epsilon < 1.0)) { CMS_ERR("epsilon must be between 0 and 1 (exclusive)"); return 0; } 50 2 52
if (!(epsilon > 0.0 && epsilon < 1.0)) { CMS_ERR("epsilon must be between 0 and 1 (exclusive)"); return 0; } 2 48 50
if (!(epsilon > 0.0 && epsilon < 1.0)) { CMS_ERR("epsilon must be between 0 and 1 (exclusive)"); return 0; } 4 0 4
593 48 ▶ if (!(delta > 0.0 && delta < 1.0)) { CMS_ERR("delta must be between 0 and 1 (exclusive)"); return 0; }
Branch: 3 branches
BranchTrueFalseTotal
if (!(delta > 0.0 && delta < 1.0)) { CMS_ERR("delta must be between 0 and 1 (exclusive)"); return 0; } 47 1 48
if (!(delta > 0.0 && delta < 1.0)) { CMS_ERR("delta must be between 0 and 1 (exclusive)"); return 0; } 2 45 47
if (!(delta > 0.0 && delta < 1.0)) { CMS_ERR("delta must be between 0 and 1 (exclusive)"); return 0; } 3 0 3
594  
595 /* w = next_pow2(ceil(e / epsilon)), floor CMS_MIN_W. Reject (don't silently
596 clamp) an epsilon so small the column count would exceed the cap, else the
597 achieved error bound would be worse than requested (and the mapping huge). */
598 45 double w_opt_d = ceil(M_E / epsilon);
599 45 ▶ if (w_opt_d > (double)CMS_MAX_W) { CMS_ERR("epsilon too small for the column cap"); return 0; }
Branch: 2 branches
BranchTrueFalseTotal
if (w_opt_d > (double)CMS_MAX_W) { CMS_ERR("epsilon too small for the column cap"); return 0; } 1 44 45
if (w_opt_d > (double)CMS_MAX_W) { CMS_ERR("epsilon too small for the column cap"); return 0; } 1 0 1
600 44 uint64_t w = cms_next_pow2_u64((uint64_t)w_opt_d);
601  
602 /* d = ceil(log(1/delta)) clamped to [1, 32]. Clamp in DOUBLE before the cast:
603 a delta below 1/DBL_MAX (~5.6e-309) makes 1.0/delta overflow to +inf, and
604 (long)inf is undefined -- on x86-64 it yields INT64_MIN, which the lower
605 clamp would then raise to depth 1, handing the caller who asked for the
606 STRONGEST guarantee the weakest possible sketch (and differing by
607 architecture, since aarch64 saturates the other way). The comparison is
608 false for NaN, which therefore also lands on the maximum. */
609 44 double d_d = ceil(log(1.0 / delta));
610 44 ▶ long dl = (d_d < (double)CMS_MAX_D) ? (long)d_d : (long)CMS_MAX_D;
Branch: 1 branch
BranchTrueFalseTotal
long dl = (d_d < (double)CMS_MAX_D) ? (long)d_d : (long)CMS_MAX_D; 44 0 44
611 44 ▶ if (dl < CMS_MIN_D) dl = CMS_MIN_D;
Branch: 1 branch
BranchTrueFalseTotal
if (dl < CMS_MIN_D) dl = CMS_MIN_D; 0 44 44
612 44 uint32_t d = (uint32_t)dl;
613  
614 44 *w_out = w;
615 44 *d_out = d;
616 44 return 1;
617 }
618  
619 /* Securely obtain a fd: create exclusively (O_CREAT|O_EXCL|O_NOFOLLOW at mode,
620 * default 0600), or attach an existing file (O_RDWR|O_NOFOLLOW, no O_CREAT). */
621 19 static int cms_secure_open(const char *path, mode_t mode, char *errbuf) {
622 19 ▶ for (int attempt = 0; attempt < 100; attempt++) {
Branch: 1 branch
BranchTrueFalseTotal
for (int attempt = 0; attempt < 100; attempt++) { 19 0 19
623 19 int fd = open(path, O_RDWR|O_CREAT|O_EXCL|O_NOFOLLOW|O_CLOEXEC, mode);
624 19 ▶ if (fd >= 0) { (void)fchmod(fd, mode); return fd; } /* exact mode: umask narrowed the O_EXCL create */
Branch: 1 branch
BranchTrueFalseTotal
if (fd >= 0) { (void)fchmod(fd, mode); return fd; } /* exact mode: umask narrowed the O_EXCL create */ 10 9 19
625 9 ▶ if (errno != EEXIST) { CMS_ERR("create %s: %s", path, strerror(errno)); return -1; }
Branch: 2 branches
BranchTrueFalseTotal
if (errno != EEXIST) { CMS_ERR("create %s: %s", path, strerror(errno)); return -1; } 0 9 9
if (errno != EEXIST) { CMS_ERR("create %s: %s", path, strerror(errno)); return -1; } 0 0 0
626 9 fd = open(path, O_RDWR|O_NOFOLLOW|O_CLOEXEC);
627 9 ▶ if (fd >= 0) return fd;
Branch: 1 branch
BranchTrueFalseTotal
if (fd >= 0) return fd; 9 0 9
628 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
629 0 ▶ CMS_ERR("open %s: %s", path, strerror(errno)); /* ELOOP => symlink rejected */
Branch: 1 branch
BranchTrueFalseTotal
CMS_ERR("open %s: %s", path, strerror(errno)); /* ELOOP => symlink rejected */ 0 0 0
630 0 return -1;
631 }
632 0 ▶ CMS_ERR("open %s: create/attach kept racing", path);
Branch: 1 branch
BranchTrueFalseTotal
CMS_ERR("open %s: create/attach kept racing", path); 0 0 0
633 0 return -1;
634 }
635  
636 /* True iff the whole file is zero -- what an abandoned mid-init
637 creator leaves. Lets recovery re-init only a provably-empty file, never
638 one that merely starts with a zero word. Cold path, so a byte scan is
639 fine. Read, not mapped: a read fault on a tmpfs hole allocates the page. */
640 2 static int cms_file_is_zero(int fd, uint64_t size) {
641 char buf[16384];
642 7 ▶ for (uint64_t off = 0; off < size; ) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint64_t off = 0; off < size; ) { 6 1 7
643 6 ssize_t n = pread(fd, buf, size - off < sizeof buf ? (size_t)(size - off) : sizeof buf, (off_t)off);
644 6 ▶ if (n <= 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (n <= 0) return 0; 0 6 6
645 74501 ▶ 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 74495 74496
for (ssize_t i = 0; i < n; i++) if (buf[i]) return 0; 74496 5 74501
646 5 off += (uint64_t)n;
647 }
648 1 return 1;
649 }
650  
651 /* Opt-in (DATA_COUNTMINSKETCH_SHARED_SPARSE=0): reserving commits memory this module otherwise fills lazily. */
652 13 static int cms_reserve(int fd, uint64_t size) {
653 13 const char *sp = getenv("DATA_COUNTMINSKETCH_SHARED_SPARSE");
654 13 ▶ if (!sp || strcmp(sp, "0")) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (!sp || strcmp(sp, "0")) return 0; 0 13 13
if (!sp || strcmp(sp, "0")) return 0; 0 0 0
655 /* Before Linux 6.11 tmpfs gives up at any pending signal and undoes the allocation, so a
656 * periodic one could keep it from ever completing; SIGSTOP cannot be blocked. */
657 sigset_t all, old;
658 0 sigfillset(&all);
659 0 sigprocmask(SIG_BLOCK, &all, &old);
660 int e;
661 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
662 0 sigprocmask(SIG_SETMASK, &old, NULL);
663 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
664 0 errno = e;
665 0 return -1;
666 }
667  
668 48 static CmsHandle *cms_create(const char *path, double epsilon, double delta, mode_t mode, char *errbuf) {
669 uint64_t w;
670 uint32_t d;
671 48 ▶ if (!cms_validate_create_args(epsilon, delta, &w, &d, errbuf)) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!cms_validate_create_args(epsilon, delta, &w, &d, errbuf)) return NULL; 6 42 48
672  
673 42 uint64_t total = cms_total_size(w, d);
674 42 int anonymous = (path == NULL);
675 42 int fd = -1;
676 42 int initialize = anonymous;
677 size_t map_size;
678 void *base;
679  
680 42 ▶ if (anonymous) {
Branch: 1 branch
BranchTrueFalseTotal
if (anonymous) { 23 19 42
681 23 map_size = (size_t)total;
682 23 base = mmap(NULL, map_size, PROT_READ|PROT_WRITE, MAP_SHARED|MAP_ANONYMOUS, -1, 0);
683 23 ▶ if (base == MAP_FAILED) { CMS_ERR("mmap: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { CMS_ERR("mmap: %s", strerror(errno)); return NULL; } 0 23 23
if (base == MAP_FAILED) { CMS_ERR("mmap: %s", strerror(errno)); return NULL; } 0 0 0
684 } else {
685 19 fd = cms_secure_open(path, mode, errbuf);
686 24 ▶ if (fd < 0) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (fd < 0) return NULL; 0 19 19
687 19 ▶ if (flock(fd, LOCK_EX) < 0) { CMS_ERR("flock: %s", strerror(errno)); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (flock(fd, LOCK_EX) < 0) { CMS_ERR("flock: %s", strerror(errno)); close(fd); return NULL; } 0 19 19
if (flock(fd, LOCK_EX) < 0) { CMS_ERR("flock: %s", strerror(errno)); close(fd); return NULL; } 0 0 0
688 struct stat st;
689 19 ▶ if (fstat(fd, &st) < 0) { CMS_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fstat(fd, &st) < 0) { CMS_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; } 0 19 19
if (fstat(fd, &st) < 0) { CMS_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; } 0 0 0
690 19 int is_new = (st.st_size == 0);
691 19 ▶ if (!is_new && (uint64_t)st.st_size < sizeof(CmsHeader)) {
Branch: 2 branches
BranchTrueFalseTotal
if (!is_new && (uint64_t)st.st_size < sizeof(CmsHeader)) { 9 10 19
if (!is_new && (uint64_t)st.st_size < sizeof(CmsHeader)) { 1 8 9
692 1 ▶ CMS_ERR("%s: file too small (%lld)", path, (long long)st.st_size);
Branch: 1 branch
BranchTrueFalseTotal
CMS_ERR("%s: file too small (%lld)", path, (long long)st.st_size); 1 0 1
693 1 flock(fd, LOCK_UN); close(fd); return NULL;
694 }
695 18 initialize = is_new;
696 18 ▶ if (!is_new) {
Branch: 1 branch
BranchTrueFalseTotal
if (!is_new) { 8 10 18
697 /* A mapped read of a tmpfs hole can allocate a page; validate before mapping. */
698 CmsHeader hdr;
699 ssize_t n;
700 8 ▶ do n = pread(fd, &hdr, sizeof hdr, 0); while (n < 0 && errno == EINTR);
Branch: 2 branches
BranchTrueFalseTotal
do n = pread(fd, &hdr, sizeof hdr, 0); while (n < 0 && errno == EINTR); 0 8 8
do n = pread(fd, &hdr, sizeof hdr, 0); while (n < 0 && errno == EINTR); 0 0 0
701 8 ▶ if (n != (ssize_t)sizeof hdr) {
Branch: 1 branch
BranchTrueFalseTotal
if (n != (ssize_t)sizeof hdr) { 0 8 8
702 0 ▶ CMS_ERR("%s: cannot read Count-Min sketch header: %s", path, n < 0 ? strerror(errno) : "short read");
Branch: 2 branches
BranchTrueFalseTotal
CMS_ERR("%s: cannot read Count-Min sketch header: %s", path, n < 0 ? strerror(errno) : "short read"); 0 0 0
CMS_ERR("%s: cannot read Count-Min sketch header: %s", path, n < 0 ? strerror(errno) : "short read"); 0 0 0
703 4 flock(fd, LOCK_UN); close(fd); return NULL;
704 }
705 8 ▶ if (!cms_validate_header(&hdr, (uint64_t)st.st_size)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!cms_validate_header(&hdr, (uint64_t)st.st_size)) { 4 4 8
706 4 ▶ if (hdr.magic == 0 && (uint64_t)st.st_size == total && st.st_uid == geteuid()) {
Branch: 3 branches
BranchTrueFalseTotal
if (hdr.magic == 0 && (uint64_t)st.st_size == total && st.st_uid == geteuid()) { 3 1 4
if (hdr.magic == 0 && (uint64_t)st.st_size == total && st.st_uid == geteuid()) { 2 1 3
if (hdr.magic == 0 && (uint64_t)st.st_size == total && st.st_uid == geteuid()) { 2 0 2
707 2 ▶ if (!cms_file_is_zero(fd, total)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!cms_file_is_zero(fd, total)) { 1 1 2
708 1 ▶ CMS_ERR("%s: incomplete Count-Min sketch file left by an interrupted create; remove it and retry", path);
Branch: 1 branch
BranchTrueFalseTotal
CMS_ERR("%s: incomplete Count-Min sketch file left by an interrupted create; remove it and retry", path); 1 0 1
709 1 flock(fd, LOCK_UN); close(fd); return NULL;
710 }
711 1 initialize = 1;
712 } else {
713 2 ▶ CMS_ERR("invalid Count-Min sketch file");
Branch: 1 branch
BranchTrueFalseTotal
CMS_ERR("invalid Count-Min sketch file"); 2 0 2
714 2 flock(fd, LOCK_UN); close(fd); return NULL;
715 }
716 }
717 5 ▶ if (!initialize && hdr.sealed) {
Branch: 2 branches
BranchTrueFalseTotal
if (!initialize && hdr.sealed) { 4 1 5
if (!initialize && hdr.sealed) { 1 3 4
718 1 ▶ CMS_ERR("%s is frozen (read-only); open it with new_readonly", path);
Branch: 1 branch
BranchTrueFalseTotal
CMS_ERR("%s is frozen (read-only); open it with new_readonly", path); 1 0 1
719 1 flock(fd, LOCK_UN); close(fd); return NULL;
720 }
721 }
722 14 ▶ if (initialize && st.st_uid != geteuid()) {
Branch: 2 branches
BranchTrueFalseTotal
if (initialize && st.st_uid != geteuid()) { 11 3 14
if (initialize && st.st_uid != geteuid()) { 0 11 11
723 0 ▶ CMS_ERR("%s: refusing to initialize file not owned by us", path);
Branch: 1 branch
BranchTrueFalseTotal
CMS_ERR("%s: refusing to initialize file not owned by us", path); 0 0 0
724 0 flock(fd, LOCK_UN); close(fd); return NULL;
725 }
726 14 ▶ if (initialize && fchmod(fd, mode) < 0) {
Branch: 2 branches
BranchTrueFalseTotal
if (initialize && fchmod(fd, mode) < 0) { 11 3 14
if (initialize && fchmod(fd, mode) < 0) { 0 11 11
727 0 ▶ CMS_ERR("%s: fchmod: %s", path, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
CMS_ERR("%s: fchmod: %s", path, strerror(errno)); 0 0 0
728 0 flock(fd, LOCK_UN); close(fd); return NULL;
729 }
730 14 ▶ if (is_new && ftruncate(fd, (off_t)total) < 0) {
Branch: 2 branches
BranchTrueFalseTotal
if (is_new && ftruncate(fd, (off_t)total) < 0) { 10 4 14
if (is_new && ftruncate(fd, (off_t)total) < 0) { 0 10 10
731 0 ▶ CMS_ERR("ftruncate: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
CMS_ERR("ftruncate: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; 0 0 0
732 }
733 14 ▶ if (initialize && cms_reserve(fd, total) < 0) {
Branch: 2 branches
BranchTrueFalseTotal
if (initialize && cms_reserve(fd, total) < 0) { 11 3 14
if (initialize && cms_reserve(fd, total) < 0) { 0 11 11
734 0 ▶ CMS_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
CMS_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno)); 0 0 0
735 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
736 0 flock(fd, LOCK_UN); close(fd); return NULL;
737 }
738 14 ▶ 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; 4 10 14
739 14 base = mmap(NULL, map_size, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
740 14 ▶ if (base == MAP_FAILED) {
Branch: 1 branch
BranchTrueFalseTotal
if (base == MAP_FAILED) { 0 14 14
741 0 ▶ CMS_ERR("mmap: %s", strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
CMS_ERR("mmap: %s", strerror(errno)); 0 0 0
742 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
743 0 flock(fd, LOCK_UN); close(fd); return NULL;
744 }
745 }
746 37 ▶ if (initialize) cms_init_header(base, w, d, total);
Branch: 1 branch
BranchTrueFalseTotal
if (initialize) cms_init_header(base, w, d, total); 34 3 37
747 37 ▶ if (fd >= 0) { flock(fd, LOCK_UN); close(fd); }
Branch: 1 branch
BranchTrueFalseTotal
if (fd >= 0) { flock(fd, LOCK_UN); close(fd); } 14 23 37
748 37 return cms_setup(base, map_size, path, -1);
749 }
750  
751 4 static CmsHandle *cms_create_memfd(const char *name, double epsilon, double delta, char *errbuf) {
752 uint64_t w;
753 uint32_t d;
754 4 ▶ if (!cms_validate_create_args(epsilon, delta, &w, &d, errbuf)) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!cms_validate_create_args(epsilon, delta, &w, &d, errbuf)) return NULL; 2 2 4
755  
756 2 uint64_t total = cms_total_size(w, d);
757 2 ▶ int fd = memfd_create(name ? name : "cms", MFD_CLOEXEC | MFD_ALLOW_SEALING);
Branch: 1 branch
BranchTrueFalseTotal
int fd = memfd_create(name ? name : "cms", MFD_CLOEXEC | MFD_ALLOW_SEALING); 1 1 2
758 2 ▶ if (fd < 0) { CMS_ERR("memfd_create: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fd < 0) { CMS_ERR("memfd_create: %s", strerror(errno)); return NULL; } 0 2 2
if (fd < 0) { CMS_ERR("memfd_create: %s", strerror(errno)); return NULL; } 0 0 0
759 2 ▶ if (ftruncate(fd, (off_t)total) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (ftruncate(fd, (off_t)total) < 0) { 0 2 2
760 0 ▶ CMS_ERR("ftruncate: %s", strerror(errno)); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
CMS_ERR("ftruncate: %s", strerror(errno)); close(fd); return NULL; 0 0 0
761 }
762 2 ▶ if (cms_reserve(fd, total) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (cms_reserve(fd, total) < 0) { 0 2 2
763 0 ▶ CMS_ERR("memfd: cannot reserve %llu bytes: %s", (unsigned long long)total, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
CMS_ERR("memfd: cannot reserve %llu bytes: %s", (unsigned long long)total, strerror(errno)); 0 0 0
764 0 close(fd); return NULL;
765 }
766 2 (void)fcntl(fd, F_ADD_SEALS, F_SEAL_SHRINK | F_SEAL_GROW);
767 2 void *base = mmap(NULL, (size_t)total, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
768 2 ▶ if (base == MAP_FAILED) { CMS_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { CMS_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; } 0 2 2
if (base == MAP_FAILED) { CMS_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; } 0 0 0
769 2 cms_init_header(base, w, d, total);
770 2 return cms_setup(base, (size_t)total, NULL, fd);
771 }
772  
773 2 static CmsHandle *cms_open_fd(int fd, char *errbuf) {
774 2 ▶ if (errbuf) errbuf[0] = '\0';
Branch: 1 branch
BranchTrueFalseTotal
if (errbuf) errbuf[0] = '\0'; 2 0 2
775 struct stat st;
776 2 ▶ if (fstat(fd, &st) < 0) { CMS_ERR("fstat: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fstat(fd, &st) < 0) { CMS_ERR("fstat: %s", strerror(errno)); return NULL; } 0 2 2
if (fstat(fd, &st) < 0) { CMS_ERR("fstat: %s", strerror(errno)); return NULL; } 0 0 0
777 2 ▶ if ((uint64_t)st.st_size < sizeof(CmsHeader)) { CMS_ERR("too small"); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if ((uint64_t)st.st_size < sizeof(CmsHeader)) { CMS_ERR("too small"); return NULL; } 1 1 2
if ((uint64_t)st.st_size < sizeof(CmsHeader)) { CMS_ERR("too small"); return NULL; } 1 0 1
778 /* before mmap: a creator may truncate the file until it has set magic */
779 uint32_t magic;
780 1 ▶ if (pread(fd, &magic, sizeof magic, offsetof(CmsHeader, magic)) != (ssize_t)sizeof magic || magic != CMS_MAGIC) {
Branch: 2 branches
BranchTrueFalseTotal
if (pread(fd, &magic, sizeof magic, offsetof(CmsHeader, magic)) != (ssize_t)sizeof magic || magic != CMS_MAGIC) { 1 0 1
if (pread(fd, &magic, sizeof magic, offsetof(CmsHeader, magic)) != (ssize_t)sizeof magic || magic != CMS_MAGIC) { 0 1 1
781 0 ▶ CMS_ERR("invalid Count-Min sketch table"); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
CMS_ERR("invalid Count-Min sketch table"); return NULL; 0 0 0
782 }
783 1 size_t ms = (size_t)st.st_size;
784 1 void *base = mmap(NULL, ms, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
785 1 ▶ if (base == MAP_FAILED) { CMS_ERR("mmap: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { CMS_ERR("mmap: %s", strerror(errno)); return NULL; } 0 1 1
if (base == MAP_FAILED) { CMS_ERR("mmap: %s", strerror(errno)); return NULL; } 0 0 0
786 1 ▶ if (!cms_validate_header((CmsHeader *)base, (uint64_t)st.st_size)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!cms_validate_header((CmsHeader *)base, (uint64_t)st.st_size)) { 0 1 1
787 0 ▶ CMS_ERR("invalid Count-Min sketch table"); munmap(base, ms); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
CMS_ERR("invalid Count-Min sketch table"); munmap(base, ms); return NULL; 0 0 0
788 }
789 1 ▶ if (((CmsHeader *)base)->sealed) {
Branch: 1 branch
BranchTrueFalseTotal
if (((CmsHeader *)base)->sealed) { 0 1 1
790 0 ▶ CMS_ERR("this Count-Min sketch is frozen (read-only); open it with new_readonly");
Branch: 1 branch
BranchTrueFalseTotal
CMS_ERR("this Count-Min sketch is frozen (read-only); open it with new_readonly"); 0 0 0
791 0 munmap(base, ms); return NULL;
792 }
793 1 int myfd = fcntl(fd, F_DUPFD_CLOEXEC, 0);
794 1 ▶ if (myfd < 0) { CMS_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (myfd < 0) { CMS_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; } 0 1 1
if (myfd < 0) { CMS_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; } 0 0 0
795 1 return cms_setup(base, ms, NULL, myfd);
796 }
797  
798 /* Open a FROZEN (sealed) file read-only: O_RDONLY + PROT_READ, no lock ever.
799 * A sealed file is immutable and no read path writes the mapping, so queries
800 * take no reader-slot / rwlock traffic and any number of processes can share
801 * one PROT_READ mapping (same architecture; the magic rejects a wrong-endian
802 * file). */
803 7 static CmsHandle *cms_open_readonly(const char *path, char *errbuf) {
804 7 ▶ if (errbuf) errbuf[0] = '\0';
Branch: 1 branch
BranchTrueFalseTotal
if (errbuf) errbuf[0] = '\0'; 7 0 7
805 7 int fd = open(path, O_RDONLY|O_NOFOLLOW|O_CLOEXEC);
806 7 ▶ if (fd < 0) { CMS_ERR("open %s: %s", path, strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fd < 0) { CMS_ERR("open %s: %s", path, strerror(errno)); return NULL; } 1 6 7
if (fd < 0) { CMS_ERR("open %s: %s", path, strerror(errno)); return NULL; } 1 0 1
807 struct stat st;
808 6 ▶ if (fstat(fd, &st) < 0) { CMS_ERR("fstat %s: %s", path, strerror(errno)); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fstat(fd, &st) < 0) { CMS_ERR("fstat %s: %s", path, strerror(errno)); close(fd); return NULL; } 0 6 6
if (fstat(fd, &st) < 0) { CMS_ERR("fstat %s: %s", path, strerror(errno)); close(fd); return NULL; } 0 0 0
809 6 ▶ if ((uint64_t)st.st_size < sizeof(CmsHeader)) { CMS_ERR("%s: file too small", path); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if ((uint64_t)st.st_size < sizeof(CmsHeader)) { CMS_ERR("%s: file too small", path); close(fd); return NULL; } 0 6 6
if ((uint64_t)st.st_size < sizeof(CmsHeader)) { CMS_ERR("%s: file too small", path); close(fd); return NULL; } 0 0 0
810 /* before mmap: a creator may truncate the file until it has set magic */
811 uint32_t magic;
812 6 ▶ if (pread(fd, &magic, sizeof magic, offsetof(CmsHeader, magic)) != (ssize_t)sizeof magic || magic != CMS_MAGIC) {
Branch: 2 branches
BranchTrueFalseTotal
if (pread(fd, &magic, sizeof magic, offsetof(CmsHeader, magic)) != (ssize_t)sizeof magic || magic != CMS_MAGIC) { 6 0 6
if (pread(fd, &magic, sizeof magic, offsetof(CmsHeader, magic)) != (ssize_t)sizeof magic || magic != CMS_MAGIC) { 0 6 6
813 0 ▶ CMS_ERR("%s: invalid Count-Min sketch file", path); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
CMS_ERR("%s: invalid Count-Min sketch file", path); close(fd); return NULL; 0 0 0
814 }
815 6 size_t ms = (size_t)st.st_size;
816 6 void *base = mmap(NULL, ms, PROT_READ, MAP_SHARED, fd, 0);
817 6 close(fd); /* the mapping keeps the file; a read-only view needs no fd (no msync/ftruncate) */
818 6 ▶ if (base == MAP_FAILED) { CMS_ERR("mmap %s: %s", path, strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { CMS_ERR("mmap %s: %s", path, strerror(errno)); return NULL; } 0 6 6
if (base == MAP_FAILED) { CMS_ERR("mmap %s: %s", path, strerror(errno)); return NULL; } 0 0 0
819 6 ▶ if (!cms_validate_header((CmsHeader *)base, (uint64_t)st.st_size)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!cms_validate_header((CmsHeader *)base, (uint64_t)st.st_size)) { 0 6 6
820 0 ▶ CMS_ERR("%s: invalid Count-Min sketch file", path); munmap(base, ms); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
CMS_ERR("%s: invalid Count-Min sketch file", path); munmap(base, ms); return NULL; 0 0 0
821 }
822 6 ▶ if (!__atomic_load_n(&((CmsHeader *)base)->sealed, __ATOMIC_ACQUIRE)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!__atomic_load_n(&((CmsHeader *)base)->sealed, __ATOMIC_ACQUIRE)) { 1 5 6
823 1 ▶ CMS_ERR("%s is not frozen: call ->freeze on the producer before opening read-only", path);
Branch: 1 branch
BranchTrueFalseTotal
CMS_ERR("%s is not frozen: call ->freeze on the producer before opening read-only", path); 1 0 1
824 1 munmap(base, ms); return NULL;
825 }
826 5 CmsHandle *h = cms_setup(base, ms, path, -1); /* munmaps on OOM */
827 5 ▶ if (!h) { CMS_ERR("out of memory"); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (!h) { CMS_ERR("out of memory"); return NULL; } 0 5 5
if (!h) { CMS_ERR("out of memory"); return NULL; } 0 0 0
828 5 h->readonly = 1;
829 5 return h;
830 }
831  
832 45 static void cms_destroy(CmsHandle *h) {
833 45 ▶ if (!h) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!h) return; 0 45 45
834 /* Release our reader slot on clean teardown (else short-lived-reader churn
835 * exhausts the slot table); skip if a read lock is still held (rdepth>0). */
836 45 ▶ 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 && 45 0 45
if (h->reader_slots && h->my_slot_idx != UINT32_MAX && h->cached_pid && 28 17 45
if (h->reader_slots && h->my_slot_idx != UINT32_MAX && h->cached_pid && 28 0 28
837 28 ▶ h->cached_fork_gen == __atomic_load_n(&cms_fork_gen, __ATOMIC_RELAXED) &&
Branch: 1 branch
BranchTrueFalseTotal
h->cached_fork_gen == __atomic_load_n(&cms_fork_gen, __ATOMIC_RELAXED) && 28 0 28
838 28 ▶ __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) { 28 0 28
839 /* Clear our occ bit BEFORE freeing the slot: we still own the pid so no
840 * claimant can take the slot mid-clear, and rdepth==0 so no writer needs
841 * to see us. (A crash skips this -> the bit is reclaimed lazily by a
842 * writer scan / re-claim, same as the pid.) */
843 28 cms_occ_clear(h, h->my_slot_idx);
844 28 uint32_t expected = h->cached_pid;
845 28 __atomic_compare_exchange_n(&h->reader_slots[h->my_slot_idx].pid,
846 &expected, 0, 0, __ATOMIC_RELEASE, __ATOMIC_RELAXED);
847 }
848 45 ▶ if (h->backing_fd >= 0) close(h->backing_fd);
Branch: 1 branch
BranchTrueFalseTotal
if (h->backing_fd >= 0) close(h->backing_fd); 3 42 45
849 45 ▶ if (h->base) munmap(h->base, h->mmap_size);
Branch: 1 branch
BranchTrueFalseTotal
if (h->base) munmap(h->base, h->mmap_size); 45 0 45
850 45 free(h->path);
851 45 free(h);
852 }
853  
854 4 static inline int cms_msync(CmsHandle *h) {
855 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
856 4 return msync(h->base, h->mmap_size, MS_SYNC);
857 }
858  
859 /* Seal a sketch: make it permanently immutable so it can be shipped and opened
860 * read-only. Takes the write lock so no add is in flight, publishes the seal,
861 * then flushes it (file/memfd-backed). Afterwards every mutator croaks and a
862 * read-write reopen is refused. */
863 2 static int cms_freeze(CmsHandle *h) {
864 2 cms_rwlock_wrlock(h);
865 2 __atomic_store_n(&h->hdr->sealed, 1, __ATOMIC_RELEASE);
866 2 cms_rwlock_wrunlock(h);
867 2 ▶ if (h->path || h->backing_fd >= 0) return cms_msync(h); /* durability for file/memfd-backed */
Branch: 2 branches
BranchTrueFalseTotal
if (h->path || h->backing_fd >= 0) return cms_msync(h); /* durability for file/memfd-backed */ 0 2 2
if (h->path || h->backing_fd >= 0) return cms_msync(h); /* durability for file/memfd-backed */ 0 0 0
868 0 return 0; /* anonymous: the seal lives in shared memory (visible to forks); nothing to flush */
869 }
870  
871 /* ================================================================
872 * Count-Min sketch operations (callers hold the lock) -- d-row double
873 * hashing: one XXH3-128 hash drives all d row probes.
874 * Row r's column = (h1 + r*h2) & mask.
875 * ================================================================ */
876  
877 18884 static inline void cms_indices(const void *item, size_t len,
878 uint64_t *h1, uint64_t *h2) {
879 18884 XXH128_hash_t hh = XXH3_128bits(item, len);
880 18884 *h1 = hh.low64;
881 18884 *h2 = hh.high64 | 1ULL; /* force odd so the d row columns spread over the pow2 matrix */
882 18884 }
883  
884 /* add n to each of the d cells; bump total by n (caller holds the write lock) */
885 9447 static void cms_add_locked(CmsHandle *h, const void *item, size_t len, uint64_t n) {
886 uint64_t h1, h2;
887 9447 cms_indices(item, len, &h1, &h2);
888 9447 uint64_t w = h->hdr->w;
889 9447 uint64_t mask = h->hdr->mask;
890 9447 uint32_t d = h->hdr->d;
891 /* w/mask/d/counters_off are read from the shared segment; a local peer with
892 * write access to the backing file can corrupt them after we validated the
893 * header at open. Snapshot the offset once and bound every derived cell
894 * index against the process-local mmap_size (trusted) so a poisoned header
895 * can never drive an out-of-bounds write. Never-taken for valid data. */
896 9447 uint64_t off = h->hdr->counters_off;
897 9447 ▶ uint64_t avail = (off <= h->mmap_size) ? (h->mmap_size - off) / sizeof(uint64_t) : 0;
Branch: 1 branch
BranchTrueFalseTotal
uint64_t avail = (off <= h->mmap_size) ? (h->mmap_size - off) / sizeof(uint64_t) : 0; 9447 0 9447
898 9447 uint64_t *counters = (uint64_t *)((char *)h->base + off);
899 75534 ▶ for (uint32_t r = 0; r < d; r++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t r = 0; r < d; r++) { 66087 9447 75534
900 66087 uint64_t c = (h1 + (uint64_t)r * h2) & mask;
901 66087 uint64_t idx = (uint64_t)r * w + c;
902 66087 ▶ if (idx < avail) counters[idx] += n;
Branch: 1 branch
BranchTrueFalseTotal
if (idx < avail) counters[idx] += n; 66087 0 66087
903 }
904 9447 h->hdr->total += n;
905 9447 }
906  
907 /* return the minimum of the d cells -- the Count-Min estimate, which never
908 * underestimates the true count (caller holds a lock) */
909 9437 static uint64_t cms_estimate_locked(CmsHandle *h, const void *item, size_t len) {
910 uint64_t h1, h2;
911 9437 cms_indices(item, len, &h1, &h2);
912 9437 uint64_t w = h->hdr->w;
913 9437 uint64_t mask = h->hdr->mask;
914 9437 uint32_t d = h->hdr->d;
915 /* Same at-use bound as cms_add_locked: reject any poisoned-header index that
916 * would fall outside the mapping instead of reading out of bounds. */
917 9437 uint64_t off = h->hdr->counters_off;
918 9437 ▶ uint64_t avail = (off <= h->mmap_size) ? (h->mmap_size - off) / sizeof(uint64_t) : 0;
Branch: 1 branch
BranchTrueFalseTotal
uint64_t avail = (off <= h->mmap_size) ? (h->mmap_size - off) / sizeof(uint64_t) : 0; 9437 0 9437
919 9437 uint64_t *counters = (uint64_t *)((char *)h->base + off);
920 9437 uint64_t m = UINT64_MAX;
921 75458 ▶ for (uint32_t r = 0; r < d; r++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t r = 0; r < d; r++) { 66021 9437 75458
922 66021 uint64_t c = (h1 + (uint64_t)r * h2) & mask;
923 66021 uint64_t idx = (uint64_t)r * w + c;
924 66021 ▶ if (idx < avail) {
Branch: 1 branch
BranchTrueFalseTotal
if (idx < avail) { 66021 0 66021
925 66021 uint64_t v = counters[idx];
926 66021 ▶ if (v < m) m = v;
Branch: 1 branch
BranchTrueFalseTotal
if (v < m) m = v; 16858 49163 66021
927 }
928 }
929 9437 return m;
930 }
931  
932 /* merge src cells into dst (caller guarantees equal w and d); cellwise add,
933 * saturating at UINT64_MAX on overflow (caller holds dst's write lock) */
934 4 static void cms_merge_counters(uint64_t *dst, const uint64_t *src, uint64_t cells) {
935 60132 ▶ for (uint64_t i = 0; i < cells; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint64_t i = 0; i < cells; i++) { 60128 4 60132
936 60128 ▶ if (dst[i] > UINT64_MAX - src[i]) dst[i] = UINT64_MAX;
Branch: 1 branch
BranchTrueFalseTotal
if (dst[i] > UINT64_MAX - src[i]) dst[i] = UINT64_MAX; 0 60128 60128
937 60128 else dst[i] += src[i];
938 }
939 4 }
940  
941 /* reset all counters to 0 and total to 0 (caller holds the write lock) */
942 1 static inline void cms_clear_locked(CmsHandle *h) {
943 /* d/w/counters_off are attacker-controlled shared-segment reads; clamp the
944 * memset length to what the process-local mmap_size actually backs so a
945 * poisoned geometry can never memset past the mapping. Equal for valid data. */
946 1 uint64_t off = h->hdr->counters_off;
947 1 ▶ uint64_t avail = (off <= h->mmap_size) ? (h->mmap_size - off) / sizeof(uint64_t) : 0;
Branch: 1 branch
BranchTrueFalseTotal
uint64_t avail = (off <= h->mmap_size) ? (h->mmap_size - off) / sizeof(uint64_t) : 0; 1 0 1
948 1 uint64_t cells = (uint64_t)h->hdr->d * h->hdr->w;
949 1 ▶ if (cells > avail) cells = avail;
Branch: 1 branch
BranchTrueFalseTotal
if (cells > avail) cells = avail; 0 1 1
950 1 memset((char *)h->base + off, 0, (size_t)(cells * sizeof(uint64_t)));
951 1 h->hdr->total = 0;
952 1 }
953  
954 #endif /* CMS_H */
« xxhash.h ↑ Summary Shared.xs »