ddsketch.h

filter: Statementstmt 73.8% 400 / 542 Branchbran 44.7% 205 / 458 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 60.5% 605 / 1000 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« blib/lib/Data/DDSketch/Shared.pm ↑ Summary Shared.xs »
1 /*
2 * ddsketch.h -- Shared-memory DDSketch quantile sketch for Linux
3 *
4 * Relative-error quantiles: estimates any quantile of a distribution to within a
5 * configured relative accuracy alpha, in a fixed amount of memory, using the
6 * DDSketch algorithm. Each value falls into a logarithmic bucket key =
7 * ceil(log_gamma(|v|)) with gamma = (1+alpha)/(1-alpha), so a bucket's
8 * representative value is within alpha of every value it holds; the counts live
9 * in a shared mapping so several processes feed one sketch. A write-preferring
10 * futex rwlock with reader-slot dead-process recovery guards mutation. Two
11 * sketches of the same (alpha, num_buckets) layout merge by an element-wise sum
12 * of their bucket counts.
13 *
14 * Layout: Header -> reader_slots[1024] -> occ bitmap -> neg[num_buckets] -> pos[num_buckets]
15 */
16  
17 #ifndef DD_H
18 #define DD_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 #if defined(__BYTE_ORDER__) && __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
40 #error "ddsketch.h: requires little-endian architecture"
41 #endif
42  
43  
44 /* ================================================================
45 * Constants
46 * ================================================================ */
47  
48 #define DD_MAGIC 0x4B534444 /* DDSketch */
49 #define DD_VERSION 2 /* 2: added the occupancy bitmap region (layout change) */
50 #define DD_ERR_BUFLEN (PATH_MAX + 256)
51 #ifndef DD_READER_SLOTS
52 #define DD_READER_SLOTS 1024 /* mutable handles per mapping for dead-process recovery */
53 #endif
54 /* Occupancy bitmap: one bit per reader slot, set when a process claims a slot and
55 * cleared on clean release. A writer scans these DD_OCC_WORDS words to visit
56 * only OCCUPIED slots (O(words + live readers)) instead of all DD_READER_SLOTS. */
57 #define DD_OCC_WORDS (((DD_READER_SLOTS) + 63) / 64) /* 16 for 1024 slots */
58 #define DD_OCC_BYTES ((uint64_t)DD_OCC_WORDS * 8) /* 128 bytes */
59 #define DD_MIN_BUCKETS 8
60 #define DD_MAX_BUCKETS 0x1000000U /* 2^24 buckets per store */
61 #define DD_MIN_ALPHA 1e-6
62 #define DD_MAX_ALPHA 0.5
63  
64 #define DD_ERR(fmt, ...) do { if (errbuf) snprintf(errbuf, DD_ERR_BUFLEN, fmt, ##__VA_ARGS__); } while (0)
65  
66 /* ================================================================
67 * Structs
68 * ================================================================ */
69  
70 /* Per-handle slot for dead-process recovery. In the reader-slots-only rwlock a
71 * reader's ENTIRE contribution to the shared lock is `rdepth` in its OWN slot --
72 * there is no separate shared reader counter to fall out of sync with it -- so a
73 * dead reader's contribution is exactly this one word, which a draining writer
74 * neutralises by clearing the slot's pid (the scan then ignores the slot). No
75 * orphaned counter can exist, so there is no quiescent force-reset and sustained
76 * readers cannot starve a writer. _rsv1/_rsv2 are kept only to preserve the
77 * 16-byte slot size across the already-released builds. */
78 typedef struct {
79 uint32_t pid; /* 0 = unclaimed */
80 uint32_t rdepth; /* read-locks THIS handle currently holds (recursion-safe) */
81 uint32_t _rsv1; /* reserved (was waiters_parked); unused, kept for layout size */
82 uint32_t _rsv2; /* reserved (was writers_parked); unused, kept for layout size */
83 } DdReaderSlot;
84  
85 struct DdHeader {
86 uint32_t magic, version; /* 0,4 */
87 uint32_t num_buckets; /* 8 buckets per store (positive and negative each) */
88 uint32_t bias; /* 12 slot = key + bias (bias = num_buckets/2) */
89 double gamma; /* 16 log base (1+alpha)/(1-alpha) */
90 double inv_ln_gamma; /* 24 1/ln(gamma), for key = ceil(ln|v| * inv_ln_gamma) */
91 double alpha; /* 32 configured relative accuracy */
92 uint64_t total_count; /* 40 total values inserted */
93 uint64_t zero_count; /* 48 count of exact-zero values */
94 double sum; /* 56 sum of all values (for mean) */
95 double min_value; /* 64 smallest value inserted (+inf when empty) */
96 double max_value; /* 72 largest value inserted (-inf when empty) */
97 uint64_t neg_off; /* 80 offset of the negative-value store */
98 uint64_t pos_off; /* 88 offset of the positive-value store */
99 uint64_t total_size; /* 96 */
100 uint64_t reader_slots_off; /* 104 */
101 uint32_t wlock; /* 112 WRITER word ONLY: 0 (free) or WRITER_BIT|pid. NOT a reader count. */
102 uint32_t rwait; /* 116 parked-waiter hint (readers+writers blocked on wlock); over-count-safe */
103 uint32_t drain_seq; /* 120 futex bumped by a reader releasing under a draining writer (wakes it) */
104 uint32_t slotless_rdepth; /* readers holding with no reader-slot (documented residual) */
105 uint64_t stat_ops; /* 128 */
106 uint8_t sealed; /* 136 0 = mutable, 1 = frozen (read-only; lock-free reads) */
107 uint8_t _pad[119]; /* 137..255 */
108 };
109 typedef struct DdHeader DdHeader;
110  
111 _Static_assert(sizeof(DdHeader) == 256, "DdHeader must be 256 bytes");
112  
113 /* ---- Process-local handle ---- */
114  
115 typedef struct DdHandle {
116 DdHeader *hdr;
117 DdReaderSlot *reader_slots; /* DD_READER_SLOTS entries */
118 uint64_t *occ; /* DD_OCC_WORDS-word slot-occupancy bitmap (trusted layout offset) */
119 void *base; /* mmap base */
120 uint64_t neg_off; /* validated store offsets, cached: never re-read from the peer-writable header */
121 uint64_t pos_off;
122 uint32_t num_buckets; /* cached */
123 uint32_t bias; /* cached */
124 double gamma; /* cached */
125 double inv_ln_gamma; /* cached */
126 size_t mmap_size;
127 char *path; /* backing file path (strdup'd) */
128 int backing_fd; /* memfd or reopened-fd to close on destroy, -1 for file/anon */
129 uint32_t my_slot_idx; /* UINT32_MAX if all slots taken (no recovery for this handle) */
130 uint32_t cached_pid; /* getpid() cached at last slot claim */
131 uint32_t cached_fork_gen; /* dd_fork_gen value at last slot claim */
132 uint32_t slotless_held; /* read-locks this process holds with no reader-slot */
133 int readonly; /* 1 = frozen O_RDONLY/PROT_READ view: lock-free reads, mutation croaks */
134 } DdHandle;
135  
136 /* ================================================================
137 * Futex-based write-preferring read-write lock (reader-slots-only)
138 * with dead-process recovery
139 *
140 * The reader count is NOT stored in a shared counter. It is DISTRIBUTED across
141 * per-handle reader slots: each slot's `rdepth` is that handle's entire
142 * contribution to the lock. A reader publishes its presence in its own slot and
143 * then re-checks the writer word; a writer publishes the writer word and then
144 * scans every slot until all live readers' rdepth reach 0. Sequentially-
145 * consistent store+load on each side (a Dekker handshake) gives mutual exclusion.
146 *
147 * Because a reader's whole contribution is ONE atomic word owned by ONE process,
148 * a crashed reader is recovered by clearing that one slot (CAS its pid to 0) --
149 * there is no second counter to strand, no orphaned +1, and therefore no
150 * quiescent force-reset. A reader killed anywhere in rdlock/rdunlock leaves at
151 * most `rdepth>0` in its dead slot, which the draining writer clears directly, so
152 * sustained read traffic can never starve a writer. Write-preference is inherent
153 * in the gate (new readers see wlock!=0 and yield), so there is no reader-count
154 * yield hack.
155 * ================================================================ */
156  
157 #define DD_RWLOCK_SPIN_LIMIT 32
158 #define DD_LOCK_TIMEOUT_SEC 2 /* FUTEX_WAIT timeout for stale-lock detection / drain re-scan */
159  
160 1833 static inline void dd_rwlock_spin_pause(void) {
161 #if defined(__x86_64__) || defined(__i386__)
162 1833 __asm__ volatile("pause" ::: "memory");
163 #elif defined(__aarch64__)
164 __asm__ volatile("yield" ::: "memory");
165 #else
166 __asm__ volatile("" ::: "memory");
167 #endif
168 1833 }
169  
170 /* Writer word encoding: WRITER_BIT|pid when write-locked, 0 when free. */
171 #define DD_RWLOCK_WRITER_BIT 0x80000000U
172 #define DD_RWLOCK_PID_MASK 0x7FFFFFFFU
173 #define DD_RWLOCK_WR(pid) (DD_RWLOCK_WRITER_BIT | ((uint32_t)(pid) & DD_RWLOCK_PID_MASK))
174  
175 /* A zombie (dead but not yet reaped) still answers kill(pid,0) as alive, so a
176 * process that crashed while holding the lock and lingers unreaped would never
177 * be recovered. Treat /proc/<pid>/stat state 'Z' as dead. Linux-only (as is
178 * this module); if /proc is unreadable we fall back to "alive" (safe: we never
179 * force-recover a possibly-live holder). */
180 1835 static inline int dd_pid_is_zombie(uint32_t pid) {
181 char path[32], buf[256];
182 1835 snprintf(path, sizeof(path), "/proc/%u/stat", (unsigned)pid);
183 1835 int fd = open(path, O_RDONLY | O_CLOEXEC);
184 1835 ▶ if (fd < 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (fd < 0) return 0; 0 1835 1835
185 1835 ssize_t n = read(fd, buf, sizeof(buf) - 1);
186 1835 close(fd);
187 1835 ▶ if (n <= 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (n <= 0) return 0; 0 1835 1835
188 1835 buf[n] = '\0';
189 /* "pid (comm) state ..."; comm may contain ')', so scan to the last one. */
190 1835 char *rp = strrchr(buf, ')');
191 1835 ▶ 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 */ 1835 0 1835
if (!rp || rp + 2 >= buf + n) return 0; /* need ") X" within the bytes read */ 0 1835 1835
192 1835 ▶ return rp[1] == ' ' && rp[2] == 'Z';
Branch: 2 branches
BranchTrueFalseTotal
return rp[1] == ' ' && rp[2] == 'Z'; 1835 0 1835
return rp[1] == ' ' && rp[2] == 'Z'; 0 1835 1835
193 }
194 /* 1 if alive or unknown, 0 if definitely dead. Cannot detect PID reuse: a
195 * recycled PID reports "alive" and the slot is not reclaimed until that
196 * process exits. See "Crash Safety" in the POD. */
197 1835 static inline int dd_pid_alive(uint32_t pid) {
198 1835 ▶ 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 1835 1835
199 1835 ▶ 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 1835 1835
if (kill((pid_t)pid, 0) == -1 && errno == ESRCH) return 0; /* definitely dead */ 0 0 0
200 1835 return !dd_pid_is_zombie(pid); /* kill() also succeeds for a zombie -> treat as dead */
201 }
202  
203 static const struct timespec dd_lock_timeout = { DD_LOCK_TIMEOUT_SEC, 0 };
204  
205 /* Process-global fork-generation counter. Incremented in the pthread_atfork
206 * child callback so every open handle detects a fork transition on the next
207 * lock call without paying a getpid() syscall on the hot path. */
208 static uint32_t dd_fork_gen = 1;
209 static pthread_once_t dd_atfork_once = PTHREAD_ONCE_INIT;
210 0 static void dd_on_fork_child(void) {
211 0 __atomic_add_fetch(&dd_fork_gen, 1, __ATOMIC_RELAXED);
212 0 }
213 4 static void dd_atfork_init(void) {
214 4 pthread_atfork(NULL, NULL, dd_on_fork_child);
215 4 }
216  
217 /* Occupancy bitmap: set a slot's bit when it is claimed, clear it on clean
218 * release. SEQ_CST so a set bit is ordered before the slot's rdepth can go
219 * non-zero (bit set in claim, which precedes any rdlock), letting a writer's
220 * SEQ_CST bitmap scan never miss a slot a committed reader holds. */
221 28 static inline void dd_occ_set(DdHandle *h, uint32_t s) {
222 28 __atomic_fetch_or(&h->occ[s >> 6], (uint64_t)1 << (s & 63), __ATOMIC_SEQ_CST);
223 28 }
224 28 static inline void dd_occ_clear(DdHandle *h, uint32_t s) {
225 28 __atomic_fetch_and(&h->occ[s >> 6], ~((uint64_t)1 << (s & 63)), __ATOMIC_SEQ_CST);
226 28 }
227  
228 /* Ensure this process owns a reader slot. Called from the lock helpers so
229 * that fork()'d children pick up their own slot lazily instead of sharing
230 * the parent's. Hot-path is a single relaxed load + compare; only on a
231 * fork-generation mismatch do we touch getpid() and scan slots. */
232 37528 static inline void dd_claim_reader_slot(DdHandle *h) {
233 37528 uint32_t cur_gen = __atomic_load_n(&dd_fork_gen, __ATOMIC_RELAXED);
234 37528 ▶ 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)) 37500 28 37528
if (__builtin_expect(cur_gen == h->cached_fork_gen && h->my_slot_idx != UINT32_MAX, 1)) 37500 0 37500
235 37500 return;
236 /* Cold path -- register the atfork hook once per process, then claim. */
237 28 pthread_once(&dd_atfork_once, dd_atfork_init);
238 /* Re-read after pthread_once: dd_on_fork_child may have bumped it. */
239 28 cur_gen = __atomic_load_n(&dd_fork_gen, __ATOMIC_RELAXED);
240 28 uint32_t now_pid = (uint32_t)getpid();
241 28 h->cached_pid = now_pid;
242 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
243 28 h->cached_fork_gen = cur_gen;
244 28 h->my_slot_idx = UINT32_MAX;
245 28 uint32_t start = now_pid % DD_READER_SLOTS;
246 /* Pass 1: take a free slot. */
247 30 ▶ for (uint32_t i = 0; i < DD_READER_SLOTS; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t i = 0; i < DD_READER_SLOTS; i++) { 30 0 30
248 30 uint32_t s = (start + i) % DD_READER_SLOTS;
249 30 uint32_t expected = 0;
250 30 ▶ if (__atomic_compare_exchange_n(&h->reader_slots[s].pid,
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_compare_exchange_n(&h->reader_slots[s].pid, 28 2 30
251 &expected, now_pid, 0,
252 __ATOMIC_ACQUIRE, __ATOMIC_RELAXED)) {
253 /* Fresh owner holds no read locks yet; clear any stale rdepth left by
254 * a dead predecessor (its contribution is dropped as we take over). */
255 28 __atomic_store_n(&h->reader_slots[s].rdepth, 0, __ATOMIC_RELAXED);
256 28 dd_occ_set(h, s); /* mark occupied BEFORE any rdlock can bump rdepth */
257 28 h->my_slot_idx = s;
258 28 return;
259 }
260 }
261 /* Pass 2: no free slot -- reclaim one whose owner is dead. Safe to take even
262 * if its rdepth>0: clearing pid drops the dead reader's entire contribution
263 * (a writer scan ignores rdepth when pid==0) and we reset rdepth to 0 as we
264 * claim it. */
265 0 ▶ for (uint32_t i = 0; i < DD_READER_SLOTS; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t i = 0; i < DD_READER_SLOTS; i++) { 0 0 0
266 0 uint32_t dpid = __atomic_load_n(&h->reader_slots[i].pid, __ATOMIC_ACQUIRE);
267 0 ▶ if (dpid == 0 || dpid == now_pid || dd_pid_alive(dpid)) continue;
Branch: 3 branches
BranchTrueFalseTotal
if (dpid == 0 || dpid == now_pid || dd_pid_alive(dpid)) continue; 0 0 0
if (dpid == 0 || dpid == now_pid || dd_pid_alive(dpid)) continue; 0 0 0
if (dpid == 0 || dpid == now_pid || dd_pid_alive(dpid)) continue; 0 0 0
268 0 uint32_t expected = dpid;
269 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
270 __ATOMIC_ACQUIRE, __ATOMIC_RELAXED)) {
271 0 __atomic_store_n(&h->reader_slots[i].rdepth, 0, __ATOMIC_RELAXED);
272 0 dd_occ_set(h, i);
273 0 h->my_slot_idx = i;
274 0 return;
275 }
276 }
277 /* Table full -- leave my_slot_idx = UINT32_MAX so this handle takes the
278 * slotless path (lock still works; recovery of THIS reader's death is the
279 * documented slotless limitation). */
280 }
281  
282 /* Wait until no live reader holds the lock; the caller owns wlock, so no NEW
283 * reader can join (they see wlock!=0 and yield). The SEQ_CST wlock CAS + the
284 * SEQ_CST rdepth loads below are the writer side of the Dekker handshake. */
285 33461 static inline void dd_rwlock_drain(DdHandle *h) {
286 33461 DdHeader *hdr = h->hdr;
287 0 for (;;) {
288 33461 uint32_t v = __atomic_load_n(&hdr->drain_seq, __ATOMIC_ACQUIRE); /* snapshot BEFORE scan */
289 33461 int busy = 0;
290 /* Visit only OCCUPIED slots via the occupancy bitmap (SEQ_CST: a committed
291 * reader's bit -- set in claim, before its rdepth++ -- is ordered before
292 * this scan, so no held slot is skipped). O(DD_OCC_WORDS + live readers)
293 * instead of O(DD_READER_SLOTS). */
294 568837 ▶ for (uint32_t w = 0; w < DD_OCC_WORDS; w++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t w = 0; w < DD_OCC_WORDS; w++) { 535376 33461 568837
295 535376 uint64_t word = __atomic_load_n(&h->occ[w], __ATOMIC_SEQ_CST);
296 568842 ▶ while (word) {
Branch: 1 branch
BranchTrueFalseTotal
while (word) { 33466 535376 568842
297 33466 uint32_t i = (w << 6) + (uint32_t)__builtin_ctzll(word);
298 33466 word &= word - 1; /* consume this bit (local copy) */
299 33466 uint32_t rd = __atomic_load_n(&h->reader_slots[i].rdepth, __ATOMIC_SEQ_CST);
300 33466 ▶ if (rd == 0) continue; /* occupied but not read-locking now */
Branch: 1 branch
BranchTrueFalseTotal
if (rd == 0) continue; /* occupied but not read-locking now */ 33466 0 33466
301 0 uint32_t pid = __atomic_load_n(&h->reader_slots[i].pid, __ATOMIC_ACQUIRE);
302 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
303 0 ▶ if (!dd_pid_alive(pid)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!dd_pid_alive(pid)) { 0 0 0
304 /* Dead reader: drop its pid so the slot no longer counts. Leave
305 * the occ bit set (harmless -- a later scan hits pid==0 and skips,
306 * a re-claim re-sets it) to avoid racing a concurrent claimant. */
307 0 uint32_t ep = pid;
308 0 __atomic_compare_exchange_n(&h->reader_slots[i].pid, &ep, 0,
309 0, __ATOMIC_ACQ_REL, __ATOMIC_RELAXED);
310 0 continue;
311 }
312 0 busy = 1; /* live reader still holding */
313 }
314 }
315 /* A live slotless reader keeps us waiting; a crashed slotless reader that
316 * cannot be attributed to a pid is the documented slotless limitation. */
317 33461 ▶ 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 33461 33461
318 0 busy = 1;
319 33461 ▶ if (!busy)
Branch: 1 branch
BranchTrueFalseTotal
if (!busy) 33461 0 33461
320 33461 return; /* exclusive: wlock held + every rdepth 0 */
321 /* Wait for a reader to release (drain_seq bump) or time out to re-scan
322 * (which reclaims any newly-dead slotted reader). */
323 0 syscall(SYS_futex, &hdr->drain_seq, FUTEX_WAIT, v, &dd_lock_timeout, NULL, 0);
324 }
325 }
326  
327 /* A read lock already held by this handle predates the dead writer's drain.
328 * Another thread's slot can instead be provisional, published after that drain,
329 * and must not suppress repair. */
330 0 static int dd_self_reading(DdHandle *h) {
331 0 ▶ if (h->slotless_held) return 1;
Branch: 1 branch
BranchTrueFalseTotal
if (h->slotless_held) return 1; 0 0 0
332 0 ▶ return h->my_slot_idx != UINT32_MAX &&
Branch: 1 branch
BranchTrueFalseTotal
return h->my_slot_idx != UINT32_MAX && 0 0 0
333 0 ▶ __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; 0 0 0
334 }
335  
336 static void dd_repair_locked(DdHandle *h);
337  
338 /* Force-recover a stale WRITE lock left by a dead writer (held or mid-drain).
339 * CAS to OUR pid to hold the lock while repairing shared state, then release.
340 * Using our pid (not a bare WRITER_BIT sentinel) means a subsequent recovering
341 * process can detect and re-recover if we crash mid-recovery. */
342 0 static inline void dd_recover_stale_lock(DdHandle *h, uint32_t observed_wlock) {
343 0 DdHeader *hdr = h->hdr;
344 0 uint32_t mypid = DD_RWLOCK_WR((uint32_t)getpid());
345 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
346 mypid, 0, __ATOMIC_SEQ_CST, __ATOMIC_RELAXED))
347 0 return;
348 0 ▶ if (!dd_self_reading(h)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!dd_self_reading(h)) { 0 0 0
349 0 dd_rwlock_drain(h);
350 0 dd_repair_locked(h);
351 }
352 0 __atomic_store_n(&hdr->wlock, 0, __ATOMIC_SEQ_CST);
353 0 ▶ if (__atomic_load_n(&hdr->rwait, __ATOMIC_SEQ_CST) > 0)
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&hdr->rwait, __ATOMIC_SEQ_CST) > 0) 0 0 0
354 0 syscall(SYS_futex, &hdr->wlock, FUTEX_WAKE, INT_MAX, NULL, NULL, 0);
355 }
356  
357 /* Inspect the writer word after a futex-wait timeout. If a dead writer holds
358 * it, force-recover. Dead READERS need no action here: only a writer that owns
359 * wlock drains readers, and it clears dead readers inline in its own scan. */
360 0 static inline void dd_recover_after_timeout(DdHandle *h) {
361 0 uint32_t val = __atomic_load_n(&h->hdr->wlock, __ATOMIC_RELAXED);
362 0 ▶ if (val >= DD_RWLOCK_WRITER_BIT) {
Branch: 1 branch
BranchTrueFalseTotal
if (val >= DD_RWLOCK_WRITER_BIT) { 0 0 0
363 0 uint32_t pid = val & DD_RWLOCK_PID_MASK;
364 0 ▶ if (!dd_pid_alive(pid))
Branch: 1 branch
BranchTrueFalseTotal
if (!dd_pid_alive(pid)) 0 0 0
365 0 dd_recover_stale_lock(h, val);
366 }
367 0 }
368  
369 /* Bump/drop the parked-waiter hint. Both readers (blocked at the gate) and
370 * writers (blocked acquiring wlock) wait on the wlock futex and use this, so
371 * wrunlock/recover know whether a FUTEX_WAKE is worth a syscall. A waiter
372 * SIGKILLed while parked leaves rwait over-counted -> at most a spurious wake
373 * (harmless); it can never under-count, so no wakeup is lost. */
374 2 static inline void dd_park(DdHandle *h) {
375 2 __atomic_add_fetch(&h->hdr->rwait, 1, __ATOMIC_SEQ_CST);
376 2 }
377 2 static inline void dd_unpark(DdHandle *h) {
378 2 __atomic_sub_fetch(&h->hdr->rwait, 1, __ATOMIC_RELAXED);
379 2 }
380  
381 /* Publish (inc) / retract (dec) this reader's presence -- its ENTIRE
382 * contribution to the lock. A slotted reader uses its slot's rdepth; a reader
383 * that could not claim a slot uses the global slotless_rdepth. inc() is SEQ_CST
384 * so the wlock re-check that follows it in rdlock forms a Dekker handshake with
385 * the writer's SEQ_CST wlock-store + rdepth-scan. leave() peels slotless first
386 * so a slot claimed mid-hold cannot misattribute the decrement. */
387 4323 static inline void dd_rdepth_inc(DdHandle *h) {
388 4323 ▶ if (h->my_slot_idx != UINT32_MAX) {
Branch: 1 branch
BranchTrueFalseTotal
if (h->my_slot_idx != UINT32_MAX) { 4323 0 4323
389 4323 __atomic_add_fetch(&h->reader_slots[h->my_slot_idx].rdepth, 1, __ATOMIC_SEQ_CST);
390 } else {
391 0 __atomic_add_fetch(&h->hdr->slotless_rdepth, 1, __ATOMIC_SEQ_CST);
392 0 h->slotless_held++;
393 }
394 4323 }
395 4323 static inline void dd_rdepth_dec(DdHandle *h) {
396 4323 ▶ if (h->slotless_held > 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (h->slotless_held > 0) { 0 4323 4323
397 0 h->slotless_held--;
398 0 __atomic_sub_fetch(&h->hdr->slotless_rdepth, 1, __ATOMIC_SEQ_CST);
399 4323 ▶ } else if (h->my_slot_idx != UINT32_MAX) {
Branch: 1 branch
BranchTrueFalseTotal
} else if (h->my_slot_idx != UINT32_MAX) { 4323 0 4323
400 4323 __atomic_sub_fetch(&h->reader_slots[h->my_slot_idx].rdepth, 1, __ATOMIC_SEQ_CST);
401 }
402 4323 }
403  
404 /* Wake a writer that may be draining readers (it waits on drain_seq). Called
405 * after every rdepth decrement so a released read lock lets the writer re-scan
406 * promptly instead of waiting out its timeout. SEQ_CST pairs the decrement +
407 * gate check with the writer's gate CAS + reader scan. */
408 4323 static inline void dd_reader_wake_drain(DdHandle *h) {
409 4323 ▶ if (__atomic_load_n(&h->hdr->wlock, __ATOMIC_SEQ_CST) != 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&h->hdr->wlock, __ATOMIC_SEQ_CST) != 0) { 581 3742 4323
410 581 __atomic_add_fetch(&h->hdr->drain_seq, 1, __ATOMIC_RELEASE);
411 581 syscall(SYS_futex, &h->hdr->drain_seq, FUTEX_WAKE, 1, NULL, NULL, 0);
412 }
413 4323 }
414  
415 4067 static inline void dd_rwlock_rdlock(DdHandle *h) {
416 4067 dd_claim_reader_slot(h);
417 4067 DdHeader *hdr = h->hdr;
418 6158 for (int spin = 0; ; spin++) {
419 6158 uint32_t cur = __atomic_load_n(&hdr->wlock, __ATOMIC_ACQUIRE);
420 6158 ▶ if (cur == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (cur == 0) { 4323 1835 6158
421 /* Optimistically take the read: publish rdepth, then re-check wlock.
422 * SEQ_CST inc + SEQ_CST load vs the writer's SEQ_CST wlock CAS +
423 * SEQ_CST rdepth scan: by the single total order of SEQ_CST ops the
424 * two sides cannot both miss each other, so we never hold
425 * concurrently with a writer. */
426 4323 dd_rdepth_inc(h);
427 4323 ▶ if (__atomic_load_n(&hdr->wlock, __ATOMIC_SEQ_CST) == 0)
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&hdr->wlock, __ATOMIC_SEQ_CST) == 0) 4067 256 4323
428 4067 return; /* no writer after our publish -> we hold the read lock */
429 /* A writer appeared during our publish -- yield to it (write-preferring). */
430 256 dd_rdepth_dec(h);
431 256 dd_reader_wake_drain(h); /* let the draining writer see rdepth drop */
432 256 spin = 0;
433 256 continue;
434 }
435 /* wlock != 0: a writer holds or is acquiring. Recover if it is dead. */
436 3670 if (cur >= DD_RWLOCK_WRITER_BIT &&
437 1835 !dd_pid_alive(cur & DD_RWLOCK_PID_MASK)) {
438 0 dd_recover_stale_lock(h, cur);
439 0 spin = 0;
440 0 continue;
441 }
442 1835 ▶ if (__builtin_expect(spin < DD_RWLOCK_SPIN_LIMIT, 1)) {
Branch: 1 branch
BranchTrueFalseTotal
if (__builtin_expect(spin < DD_RWLOCK_SPIN_LIMIT, 1)) { 1833 2 1835
443 1833 dd_rwlock_spin_pause();
444 1833 continue;
445 }
446 2 dd_park(h);
447 2 cur = __atomic_load_n(&hdr->wlock, __ATOMIC_SEQ_CST);
448 2 ▶ if (cur != 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (cur != 0) { 2 0 2
449 2 long rc = syscall(SYS_futex, &hdr->wlock, FUTEX_WAIT, cur,
450 &dd_lock_timeout, NULL, 0);
451 2 ▶ if (rc == -1 && errno == ETIMEDOUT) {
Branch: 2 branches
BranchTrueFalseTotal
if (rc == -1 && errno == ETIMEDOUT) { 0 2 2
if (rc == -1 && errno == ETIMEDOUT) { 0 0 0
452 0 dd_unpark(h);
453 0 dd_recover_after_timeout(h);
454 0 spin = 0;
455 0 continue;
456 }
457 }
458 2 dd_unpark(h);
459 2 spin = 0;
460 }
461 }
462  
463 4067 static inline void dd_rwlock_rdunlock(DdHandle *h) {
464 4067 dd_rdepth_dec(h); /* RELEASE: drop our entire contribution */
465 4067 dd_reader_wake_drain(h); /* if a writer is draining, wake it to re-scan */
466 4067 }
467  
468 33461 static inline void dd_rwlock_wrlock(DdHandle *h) {
469 33461 dd_claim_reader_slot(h); /* refresh cached_pid across fork */
470 33461 DdHeader *hdr = h->hdr;
471 /* Encode PID in the wlock word itself (0x80000000 | pid) to eliminate any
472 * crash window between acquiring the lock and storing the owner. */
473 33461 uint32_t mypid = DD_RWLOCK_WR(h->cached_pid);
474 /* Phase 1: acquire the writer word (mutual exclusion among writers). */
475 33461 for (int spin = 0; ; spin++) {
476 33461 uint32_t expected = 0;
477 33461 ▶ if (__atomic_compare_exchange_n(&hdr->wlock, &expected, mypid,
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_compare_exchange_n(&hdr->wlock, &expected, mypid, 33461 0 33461
478 0, __ATOMIC_SEQ_CST, __ATOMIC_RELAXED))
479 33461 break;
480 /* Contended: expected now holds the current wlock value. */
481 0 if (expected >= DD_RWLOCK_WRITER_BIT &&
482 0 !dd_pid_alive(expected & DD_RWLOCK_PID_MASK)) {
483 0 dd_recover_stale_lock(h, expected);
484 0 spin = 0;
485 0 continue;
486 }
487 0 ▶ if (__builtin_expect(spin < DD_RWLOCK_SPIN_LIMIT, 1)) {
Branch: 1 branch
BranchTrueFalseTotal
if (__builtin_expect(spin < DD_RWLOCK_SPIN_LIMIT, 1)) { 0 0 0
488 0 dd_rwlock_spin_pause();
489 0 continue;
490 }
491 0 dd_park(h);
492 0 uint32_t cur = __atomic_load_n(&hdr->wlock, __ATOMIC_SEQ_CST);
493 0 ▶ if (cur != 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (cur != 0) { 0 0 0
494 0 long rc = syscall(SYS_futex, &hdr->wlock, FUTEX_WAIT, cur,
495 &dd_lock_timeout, NULL, 0);
496 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
497 0 dd_unpark(h);
498 0 dd_recover_after_timeout(h);
499 0 spin = 0;
500 0 continue;
501 }
502 }
503 0 dd_unpark(h);
504 0 spin = 0;
505 }
506 /* Phase 2: drain the readers that were already holding when we won the CAS. */
507 33461 dd_rwlock_drain(h);
508 33461 }
509  
510 33461 static inline void dd_rwlock_wrunlock(DdHandle *h) {
511 33461 DdHeader *hdr = h->hdr;
512 /* Pair with park + gate recheck: neither side may miss the other's store. */
513 33461 __atomic_store_n(&hdr->wlock, 0, __ATOMIC_SEQ_CST);
514 33461 ▶ if (__atomic_load_n(&hdr->rwait, __ATOMIC_SEQ_CST) > 0)
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&hdr->rwait, __ATOMIC_SEQ_CST) > 0) 0 33461 33461
515 0 syscall(SYS_futex, &hdr->wlock, FUTEX_WAKE, INT_MAX, NULL, NULL, 0);
516 33461 }
517  
518 /* ================================================================
519 * Layout math + create / open / destroy
520 *
521 * Layout: Header -> reader_slots[1024] -> neg[num_buckets] -> pos[num_buckets]
522 * ================================================================ */
523  
524 /* Single source of truth for the mmap region layout offsets.
525 * Layout: Header -> reader_slots[1024] -> occ bitmap -> neg[num_buckets] -> pos[num_buckets] */
526 typedef struct { uint64_t reader_slots, occ, neg, pos, total; } DdLayout;
527  
528 138 static inline DdLayout dd_layout_for(uint32_t num_buckets) {
529 DdLayout L;
530 138 L.reader_slots = sizeof(DdHeader);
531 138 L.occ = L.reader_slots + (uint64_t)DD_READER_SLOTS * sizeof(DdReaderSlot);
532 138 L.neg = L.occ + DD_OCC_BYTES;
533 138 L.neg = (L.neg + 7) & ~(uint64_t)7; /* 8-byte align the count arrays */
534 138 L.pos = L.neg + (uint64_t)num_buckets * sizeof(uint64_t);
535 138 L.total = L.pos + (uint64_t)num_buckets * sizeof(uint64_t);
536 138 return L;
537 }
538  
539 53 static inline uint64_t dd_total_size(uint32_t num_buckets) {
540 53 return dd_layout_for(num_buckets).total;
541 }
542  
543 31 static inline void dd_init_header(void *base, uint32_t num_buckets, double alpha, uint64_t total) {
544 31 DdLayout L = dd_layout_for(num_buckets);
545 31 DdHeader *hdr = (DdHeader *)base;
546 /* Zero the header, reader slots and occupancy bitmap (through the 8-byte
547 alignment pad at L.neg). The two count stores are NOT zeroed here: every
548 caller hands us a region that is already zero -- a fresh ftruncate, a fresh
549 anonymous/memfd map, or a file the recovery path just scanned -- so writing
550 them would only fault in and allocate every page of an otherwise sparse
551 file, which on a nearly-full filesystem turns create into a SIGBUS. This
552 matches the other sketches (Histogram, CountMinSketch, HyperLogLog, TopK). */
553 31 memset(base, 0, (size_t)L.neg);
554 31 double gamma = (1.0 + alpha) / (1.0 - alpha);
555 31 hdr->version = DD_VERSION;
556 31 hdr->num_buckets = num_buckets;
557 31 hdr->bias = num_buckets / 2;
558 31 hdr->gamma = gamma;
559 31 hdr->inv_ln_gamma = 1.0 / log(gamma);
560 31 hdr->alpha = alpha;
561 31 hdr->total_count = 0;
562 31 hdr->zero_count = 0;
563 31 hdr->sum = 0.0;
564 31 hdr->min_value = INFINITY;
565 31 hdr->max_value = -INFINITY;
566 31 hdr->neg_off = L.neg;
567 31 hdr->pos_off = L.pos;
568 31 hdr->total_size = total;
569 31 hdr->reader_slots_off = L.reader_slots;
570 /* Publish magic LAST, as a release store: it is the commit point, so a
571 creator killed before it leaves magic==0 and never a file mistaken for
572 a valid one. A kill during the field stores leaves one to remove by
573 hand. */
574 31 __atomic_store_n(&hdr->magic, DD_MAGIC, __ATOMIC_RELEASE);
575 31 __atomic_thread_fence(__ATOMIC_SEQ_CST);
576 31 }
577  
578 1041 static inline uint64_t *dd_neg(DdHandle *h) { return (uint64_t *)((char *)h->base + h->neg_off); }
579 32782 static inline uint64_t *dd_pos(DdHandle *h) { return (uint64_t *)((char *)h->base + h->pos_off); }
580  
581 /* Layer B trusted bound: the number of bucket counters guaranteed to lie within
582 * the real mapping for the store at `off`. Derived from the process-local
583 * mmap_size (fixed at attach, not peer-writable) and the SAME cached offset the
584 * accessors use, so a corrupt hdr->num_buckets can never drive a store access
585 * outside the mapping. Equals num_buckets for a valid sketch. */
586 88 static inline uint64_t dd_store_max(DdHandle *h, uint64_t off) {
587 88 ▶ if (off >= h->mmap_size) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (off >= h->mmap_size) return 0; 0 88 88
588 88 return (h->mmap_size - off) / sizeof(uint64_t);
589 }
590  
591 40 static inline DdHandle *dd_setup(void *base, size_t map_size,
592 const char *path, int backing_fd) {
593 40 DdHeader *hdr = (DdHeader *)base;
594 40 DdHandle *h = (DdHandle *)calloc(1, sizeof(DdHandle));
595 40 ▶ if (!h) {
Branch: 1 branch
BranchTrueFalseTotal
if (!h) { 0 40 40
596 0 munmap(base, map_size);
597 0 ▶ if (backing_fd >= 0) close(backing_fd);
Branch: 1 branch
BranchTrueFalseTotal
if (backing_fd >= 0) close(backing_fd); 0 0 0
598 0 return NULL;
599 }
600 40 h->hdr = hdr;
601 40 h->base = base;
602 40 h->reader_slots = (DdReaderSlot *)((uint8_t *)base + sizeof(DdHeader)); /* trusted layout, not the peer-writable header offset */
603 40 h->occ = (uint64_t *)((uint8_t *)base + dd_layout_for(0).occ); /* trusted layout offset (occ offset is num_buckets-independent) */
604 /* single validated read of each geometry field; cached so the bound and the
605 pointers/arithmetic it feeds stay consistent even under later peer corruption */
606 40 h->neg_off = hdr->neg_off;
607 40 h->pos_off = hdr->pos_off;
608 40 h->num_buckets = hdr->num_buckets;
609 40 h->bias = hdr->bias;
610 /* Derive gamma / inv_ln_gamma from the validated alpha rather than trusting
611 the stored copies: validate_header bounds alpha to [DD_MIN_ALPHA,
612 DD_MAX_ALPHA], so these are always finite and in range, whereas a corrupt
613 stored inv_ln_gamma (NaN/wild) would make the key computation's double->
614 int64 cast undefined behaviour. */
615 40 h->gamma = (1.0 + hdr->alpha) / (1.0 - hdr->alpha);
616 40 h->inv_ln_gamma = 1.0 / log(h->gamma);
617 40 h->mmap_size = map_size;
618 /* Layer B: if the mapping cannot hold `num_buckets` in each store, clamp the
619 cached count to what actually fits (pos is the last, tightest region). */
620 {
621 40 uint64_t nfit = dd_store_max(h, h->neg_off);
622 40 uint64_t pfit = dd_store_max(h, h->pos_off);
623 40 uint64_t fit = nfit < pfit ? nfit : pfit;
624 40 ▶ if ((uint64_t)h->num_buckets > fit) h->num_buckets = (uint32_t)fit;
Branch: 1 branch
BranchTrueFalseTotal
if ((uint64_t)h->num_buckets > fit) h->num_buckets = (uint32_t)fit; 0 40 40
625 }
626 40 ▶ h->path = path ? strdup(path) : NULL;
Branch: 1 branch
BranchTrueFalseTotal
h->path = path ? strdup(path) : NULL; 19 21 40
627 40 ▶ if (path && !h->path) {
Branch: 2 branches
BranchTrueFalseTotal
if (path && !h->path) { 19 21 40
if (path && !h->path) { 0 19 19
628 0 munmap(base, map_size);
629 0 ▶ if (backing_fd >= 0) close(backing_fd);
Branch: 1 branch
BranchTrueFalseTotal
if (backing_fd >= 0) close(backing_fd); 0 0 0
630 0 free(h);
631 0 return NULL;
632 }
633 40 h->backing_fd = backing_fd;
634 40 h->my_slot_idx = UINT32_MAX;
635 40 return h;
636 }
637  
638 /* Validate a mapped header (shared by dd_create reopen and dd_open_fd). */
639 18 static inline int dd_validate_header(const DdHeader *hdr, uint64_t file_size) {
640 18 ▶ if (hdr->magic != DD_MAGIC) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->magic != DD_MAGIC) return 0; 4 14 18
641 14 ▶ if (hdr->version != DD_VERSION) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->version != DD_VERSION) return 0; 0 14 14
642 14 ▶ if (hdr->num_buckets < DD_MIN_BUCKETS || hdr->num_buckets > DD_MAX_BUCKETS) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (hdr->num_buckets < DD_MIN_BUCKETS || hdr->num_buckets > DD_MAX_BUCKETS) return 0; 14 0 14
if (hdr->num_buckets < DD_MIN_BUCKETS || hdr->num_buckets > DD_MAX_BUCKETS) return 0; 0 14 14
643 14 ▶ if (hdr->bias != hdr->num_buckets / 2) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->bias != hdr->num_buckets / 2) return 0; 0 14 14
644 14 ▶ if (!(hdr->alpha >= DD_MIN_ALPHA && hdr->alpha <= DD_MAX_ALPHA)) return 0; /* same bounds as create; rejects NaN */
Branch: 2 branches
BranchTrueFalseTotal
if (!(hdr->alpha >= DD_MIN_ALPHA && hdr->alpha <= DD_MAX_ALPHA)) return 0; /* same bounds as create; rejects NaN */ 14 0 14
if (!(hdr->alpha >= DD_MIN_ALPHA && hdr->alpha <= DD_MAX_ALPHA)) return 0; /* same bounds as create; rejects NaN */ 0 14 14
645 14 ▶ if (!(hdr->gamma > 1.0)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!(hdr->gamma > 1.0)) return 0; 0 14 14
646 14 ▶ if (hdr->total_size != file_size) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->total_size != file_size) return 0; 0 14 14
647 14 ▶ if (hdr->total_size != dd_total_size(hdr->num_buckets)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->total_size != dd_total_size(hdr->num_buckets)) return 0; 0 14 14
648 14 DdLayout L = dd_layout_for(hdr->num_buckets);
649 14 ▶ 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 14 14
650 14 ▶ if (hdr->neg_off != L.neg) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->neg_off != L.neg) return 0; 0 14 14
651 14 ▶ if (hdr->pos_off != L.pos) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->pos_off != L.pos) return 0; 0 14 14
652 14 return 1;
653 }
654  
655 /* validate the requested relative accuracy + bucket count */
656 42 static int dd_validate_args(double alpha, uint64_t num_buckets, char *errbuf) {
657 42 ▶ if (errbuf) errbuf[0] = '\0';
Branch: 1 branch
BranchTrueFalseTotal
if (errbuf) errbuf[0] = '\0'; 42 0 42
658 42 ▶ if (!(alpha >= DD_MIN_ALPHA && alpha <= DD_MAX_ALPHA))
Branch: 2 branches
BranchTrueFalseTotal
if (!(alpha >= DD_MIN_ALPHA && alpha <= DD_MAX_ALPHA)) 41 1 42
if (!(alpha >= DD_MIN_ALPHA && alpha <= DD_MAX_ALPHA)) 1 40 41
659 2 ▶ { DD_ERR("alpha (relative accuracy) must be between 1e-6 and 0.5"); return 0; }
Branch: 1 branch
BranchTrueFalseTotal
{ DD_ERR("alpha (relative accuracy) must be between 1e-6 and 0.5"); return 0; } 2 0 2
660 40 ▶ if (num_buckets < DD_MIN_BUCKETS || num_buckets > DD_MAX_BUCKETS)
Branch: 2 branches
BranchTrueFalseTotal
if (num_buckets < DD_MIN_BUCKETS || num_buckets > DD_MAX_BUCKETS) 39 1 40
if (num_buckets < DD_MIN_BUCKETS || num_buckets > DD_MAX_BUCKETS) 0 39 39
661 1 ▶ { DD_ERR("num_buckets must be between 8 and 2^24"); return 0; }
Branch: 1 branch
BranchTrueFalseTotal
{ DD_ERR("num_buckets must be between 8 and 2^24"); return 0; } 1 0 1
662 39 return 1;
663 }
664  
665 /* Securely obtain a fd for a path-backed segment: create it exclusively
666 * (O_CREAT|O_EXCL|O_NOFOLLOW at `mode`, default 0600 = owner-only), or, if it
667 * already exists, attach to it (O_RDWR|O_NOFOLLOW, no O_CREAT). O_EXCL blocks a
668 * pre-seeded or hard-linked file and O_NOFOLLOW a symlink swap, so a local
669 * attacker can no longer redirect or poison the backing store through the path.
670 * Cross-user sharing is opt-in via a wider `mode` (e.g. 0660); the caller still
671 * validates the file's contents via dd_validate_header. */
672 19 static int dd_secure_open(const char *path, mode_t mode, char *errbuf) {
673 19 ▶ for (int attempt = 0; attempt < 100; attempt++) {
Branch: 1 branch
BranchTrueFalseTotal
for (int attempt = 0; attempt < 100; attempt++) { 19 0 19
674 19 int fd = open(path, O_RDWR|O_CREAT|O_EXCL|O_NOFOLLOW|O_CLOEXEC, mode);
675 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
676 9 ▶ if (errno != EEXIST) { DD_ERR("create %s: %s", path, strerror(errno)); return -1; }
Branch: 2 branches
BranchTrueFalseTotal
if (errno != EEXIST) { DD_ERR("create %s: %s", path, strerror(errno)); return -1; } 0 9 9
if (errno != EEXIST) { DD_ERR("create %s: %s", path, strerror(errno)); return -1; } 0 0 0
677 9 fd = open(path, O_RDWR|O_NOFOLLOW|O_CLOEXEC);
678 9 ▶ if (fd >= 0) return fd;
Branch: 1 branch
BranchTrueFalseTotal
if (fd >= 0) return fd; 9 0 9
679 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
680 0 ▶ DD_ERR("open %s: %s", path, strerror(errno)); /* ELOOP => symlink rejected */
Branch: 1 branch
BranchTrueFalseTotal
DD_ERR("open %s: %s", path, strerror(errno)); /* ELOOP => symlink rejected */ 0 0 0
681 0 return -1;
682 }
683 0 ▶ DD_ERR("open %s: create/attach kept racing", path);
Branch: 1 branch
BranchTrueFalseTotal
DD_ERR("open %s: create/attach kept racing", path); 0 0 0
684 0 return -1;
685 }
686  
687 /* True iff the whole file is zero -- what an abandoned mid-init
688 creator leaves. Lets recovery re-init only a provably-empty file, never
689 one that merely starts with a zero word. Cold path, so a byte scan is
690 fine. Read, not mapped: a read fault on a tmpfs hole allocates the page. */
691 2 static int dd_file_is_zero(int fd, uint64_t size) {
692 char buf[16384];
693 5 ▶ for (uint64_t off = 0; off < size; ) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint64_t off = 0; off < size; ) { 4 1 5
694 4 ssize_t n = pread(fd, buf, size - off < sizeof buf ? (size_t)(size - off) : sizeof buf, (off_t)off);
695 4 ▶ if (n <= 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (n <= 0) return 0; 0 4 4
696 41731 ▶ 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 41727 41728
for (ssize_t i = 0; i < n; i++) if (buf[i]) return 0; 41728 3 41731
697 3 off += (uint64_t)n;
698 }
699 1 return 1;
700 }
701  
702 /* Opt-in (DATA_DDSKETCH_SHARED_SPARSE=0): reserving commits memory this module otherwise fills lazily. */
703 13 static int dd_reserve(int fd, uint64_t size) {
704 13 const char *sp = getenv("DATA_DDSKETCH_SHARED_SPARSE");
705 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
706 /* Before Linux 6.11 tmpfs gives up at any pending signal and undoes the allocation, so a
707 * periodic one could keep it from ever completing; SIGSTOP cannot be blocked. */
708 sigset_t all, old;
709 0 sigfillset(&all);
710 0 sigprocmask(SIG_BLOCK, &all, &old);
711 int e;
712 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
713 0 sigprocmask(SIG_SETMASK, &old, NULL);
714 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
715 0 errno = e;
716 0 return -1;
717 }
718  
719 40 static DdHandle *dd_create(const char *path, double alpha, uint64_t num_buckets, mode_t mode, char *errbuf) {
720 40 ▶ if (!dd_validate_args(alpha, num_buckets, errbuf)) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!dd_validate_args(alpha, num_buckets, errbuf)) return NULL; 3 37 40
721  
722 37 uint64_t total = dd_total_size((uint32_t)num_buckets);
723 37 int anonymous = (path == NULL);
724 37 int fd = -1;
725 size_t map_size;
726 void *base;
727  
728 37 ▶ if (anonymous) {
Branch: 1 branch
BranchTrueFalseTotal
if (anonymous) { 18 19 37
729 18 map_size = (size_t)total;
730 18 base = mmap(NULL, map_size, PROT_READ|PROT_WRITE, MAP_SHARED|MAP_ANONYMOUS, -1, 0);
731 18 ▶ if (base == MAP_FAILED) { DD_ERR("mmap: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { DD_ERR("mmap: %s", strerror(errno)); return NULL; } 0 18 18
if (base == MAP_FAILED) { DD_ERR("mmap: %s", strerror(errno)); return NULL; } 0 0 0
732 } else {
733 19 fd = dd_secure_open(path, mode, errbuf);
734 28 ▶ if (fd < 0) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (fd < 0) return NULL; 0 19 19
735 19 ▶ if (flock(fd, LOCK_EX) < 0) { DD_ERR("flock: %s", strerror(errno)); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (flock(fd, LOCK_EX) < 0) { DD_ERR("flock: %s", strerror(errno)); close(fd); return NULL; } 0 19 19
if (flock(fd, LOCK_EX) < 0) { DD_ERR("flock: %s", strerror(errno)); close(fd); return NULL; } 0 0 0
736 struct stat st;
737 19 ▶ if (fstat(fd, &st) < 0) { DD_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fstat(fd, &st) < 0) { DD_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; } 0 19 19
if (fstat(fd, &st) < 0) { DD_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; } 0 0 0
738 19 int is_new = (st.st_size == 0);
739 19 ▶ if (!is_new && (uint64_t)st.st_size < sizeof(DdHeader)) {
Branch: 2 branches
BranchTrueFalseTotal
if (!is_new && (uint64_t)st.st_size < sizeof(DdHeader)) { 9 10 19
if (!is_new && (uint64_t)st.st_size < sizeof(DdHeader)) { 1 8 9
740 1 ▶ DD_ERR("%s: file too small (%lld)", path, (long long)st.st_size);
Branch: 1 branch
BranchTrueFalseTotal
DD_ERR("%s: file too small (%lld)", path, (long long)st.st_size); 1 0 1
741 1 flock(fd, LOCK_UN); close(fd); return NULL;
742 }
743 18 ▶ 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)) { 10 8 18
if (is_new && (st.st_uid != geteuid() || fchmod(fd, mode) < 0)) { 10 0 10
if (is_new && (st.st_uid != geteuid() || fchmod(fd, mode) < 0)) { 0 10 10
744 0 ▶ DD_ERR("%s: refusing to initialize file not owned by us", path);
Branch: 1 branch
BranchTrueFalseTotal
DD_ERR("%s: refusing to initialize file not owned by us", path); 0 0 0
745 0 flock(fd, LOCK_UN); close(fd); return NULL;
746 }
747 18 ▶ if (is_new && ftruncate(fd, (off_t)total) < 0) {
Branch: 2 branches
BranchTrueFalseTotal
if (is_new && ftruncate(fd, (off_t)total) < 0) { 10 8 18
if (is_new && ftruncate(fd, (off_t)total) < 0) { 0 10 10
748 0 ▶ DD_ERR("ftruncate: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
DD_ERR("ftruncate: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; 0 0 0
749 }
750 18 ▶ if (is_new && dd_reserve(fd, total) < 0) {
Branch: 2 branches
BranchTrueFalseTotal
if (is_new && dd_reserve(fd, total) < 0) { 10 8 18
if (is_new && dd_reserve(fd, total) < 0) { 0 10 10
751 0 ▶ DD_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
DD_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno)); 0 0 0
752 0 if (ftruncate(fd, 0) < 0) { /* best effort */ }
753 0 flock(fd, LOCK_UN); close(fd); return NULL;
754 }
755 18 ▶ map_size = is_new ? (size_t)total : (size_t)st.st_size;
Branch: 1 branch
BranchTrueFalseTotal
map_size = is_new ? (size_t)total : (size_t)st.st_size; 8 10 18
756 18 base = mmap(NULL, map_size, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
757 18 ▶ if (base == MAP_FAILED) {
Branch: 1 branch
BranchTrueFalseTotal
if (base == MAP_FAILED) { 0 18 18
758 0 ▶ DD_ERR("mmap: %s", strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
DD_ERR("mmap: %s", strerror(errno)); 0 0 0
759 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
760 0 flock(fd, LOCK_UN); close(fd); return NULL;
761 }
762 18 ▶ if (!is_new) {
Branch: 1 branch
BranchTrueFalseTotal
if (!is_new) { 8 10 18
763 8 ▶ if (!dd_validate_header((DdHeader *)base, (uint64_t)st.st_size)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!dd_validate_header((DdHeader *)base, (uint64_t)st.st_size)) { 4 4 8
764 /* Recover an abandoned mid-init file: a creator killed
765 * between the ftruncate and the header init leaves a
766 * full-size, all-zero (magic==0) file that would brick every
767 * future open of this path. Re-initialize ONLY when it is
768 * exactly our size, still uninitialized, and owned by us;
769 * anything else still errors. */
770 4 ▶ if (((DdHeader *)base)->magic == 0 && (uint64_t)st.st_size == total
Branch: 2 branches
BranchTrueFalseTotal
if (((DdHeader *)base)->magic == 0 && (uint64_t)st.st_size == total 3 1 4
if (((DdHeader *)base)->magic == 0 && (uint64_t)st.st_size == total 2 1 3
771 2 ▶ && st.st_uid == geteuid() && dd_file_is_zero(fd, map_size)) {
Branch: 2 branches
BranchTrueFalseTotal
&& st.st_uid == geteuid() && dd_file_is_zero(fd, map_size)) { 2 0 2
&& st.st_uid == geteuid() && dd_file_is_zero(fd, map_size)) { 1 1 2
772 1 ▶ if (fchmod(fd, mode) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (fchmod(fd, mode) < 0) { 0 1 1
773 0 ▶ DD_ERR("%s: fchmod: %s", path, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
DD_ERR("%s: fchmod: %s", path, strerror(errno)); 0 0 0
774 0 munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
775 }
776 1 ▶ if (dd_reserve(fd, total) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (dd_reserve(fd, total) < 0) { 0 1 1
777 0 ▶ DD_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
DD_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno)); 0 0 0
778 0 munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
779 }
780 1 dd_init_header(base, (uint32_t)num_buckets, alpha, total);
781 1 flock(fd, LOCK_UN); close(fd);
782 1 return dd_setup(base, map_size, path, -1);
783 }
784 3 ▶ if (((DdHeader *)base)->magic == 0 && (uint64_t)st.st_size == total
Branch: 2 branches
BranchTrueFalseTotal
if (((DdHeader *)base)->magic == 0 && (uint64_t)st.st_size == total 2 1 3
if (((DdHeader *)base)->magic == 0 && (uint64_t)st.st_size == total 1 1 2
785 1 ▶ && st.st_uid == geteuid()) {
Branch: 1 branch
BranchTrueFalseTotal
&& st.st_uid == geteuid()) { 1 0 1
786 1 ▶ DD_ERR("%s: incomplete DDSketch file left by an interrupted create; remove it and retry", path);
Branch: 1 branch
BranchTrueFalseTotal
DD_ERR("%s: incomplete DDSketch file left by an interrupted create; remove it and retry", path); 1 0 1
787 1 munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
788 }
789 2 ▶ DD_ERR("invalid DDSketch file"); munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
DD_ERR("invalid DDSketch file"); munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL; 2 0 2
790 }
791 4 ▶ if (__atomic_load_n(&((DdHeader *)base)->sealed, __ATOMIC_ACQUIRE)) {
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&((DdHeader *)base)->sealed, __ATOMIC_ACQUIRE)) { 1 3 4
792 1 ▶ DD_ERR("%s is frozen (read-only); open it with new_readonly", path);
Branch: 1 branch
BranchTrueFalseTotal
DD_ERR("%s is frozen (read-only); open it with new_readonly", path); 1 0 1
793 1 munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
794 }
795 3 flock(fd, LOCK_UN); close(fd);
796 3 return dd_setup(base, map_size, path, -1);
797 }
798 }
799 28 dd_init_header(base, (uint32_t)num_buckets, alpha, total);
800 28 ▶ if (fd >= 0) { flock(fd, LOCK_UN); close(fd); }
Branch: 1 branch
BranchTrueFalseTotal
if (fd >= 0) { flock(fd, LOCK_UN); close(fd); } 10 18 28
801 28 return dd_setup(base, map_size, path, -1);
802 }
803  
804 2 static DdHandle *dd_create_memfd(const char *name, double alpha, uint64_t num_buckets, char *errbuf) {
805 2 ▶ if (!dd_validate_args(alpha, num_buckets, errbuf)) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!dd_validate_args(alpha, num_buckets, errbuf)) return NULL; 0 2 2
806  
807 2 uint64_t total = dd_total_size((uint32_t)num_buckets);
808 2 ▶ int fd = memfd_create(name ? name : "ddsketch", MFD_CLOEXEC | MFD_ALLOW_SEALING);
Branch: 1 branch
BranchTrueFalseTotal
int fd = memfd_create(name ? name : "ddsketch", MFD_CLOEXEC | MFD_ALLOW_SEALING); 1 1 2
809 2 ▶ if (fd < 0) { DD_ERR("memfd_create: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fd < 0) { DD_ERR("memfd_create: %s", strerror(errno)); return NULL; } 0 2 2
if (fd < 0) { DD_ERR("memfd_create: %s", strerror(errno)); return NULL; } 0 0 0
810 2 ▶ if (ftruncate(fd, (off_t)total) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (ftruncate(fd, (off_t)total) < 0) { 0 2 2
811 0 ▶ DD_ERR("ftruncate: %s", strerror(errno)); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
DD_ERR("ftruncate: %s", strerror(errno)); close(fd); return NULL; 0 0 0
812 }
813 2 ▶ if (dd_reserve(fd, total) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (dd_reserve(fd, total) < 0) { 0 2 2
814 0 ▶ DD_ERR("memfd: cannot reserve %llu bytes: %s", (unsigned long long)total, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
DD_ERR("memfd: cannot reserve %llu bytes: %s", (unsigned long long)total, strerror(errno)); 0 0 0
815 0 close(fd); return NULL;
816 }
817 2 (void)fcntl(fd, F_ADD_SEALS, F_SEAL_SHRINK | F_SEAL_GROW);
818 2 void *base = mmap(NULL, (size_t)total, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
819 2 ▶ if (base == MAP_FAILED) { DD_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { DD_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; } 0 2 2
if (base == MAP_FAILED) { DD_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; } 0 0 0
820 2 dd_init_header(base, (uint32_t)num_buckets, alpha, total);
821 2 return dd_setup(base, (size_t)total, NULL, fd);
822 }
823  
824 1 static DdHandle *dd_open_fd(int fd, char *errbuf) {
825 1 ▶ if (errbuf) errbuf[0] = '\0';
Branch: 1 branch
BranchTrueFalseTotal
if (errbuf) errbuf[0] = '\0'; 1 0 1
826 struct stat st;
827 1 ▶ if (fstat(fd, &st) < 0) { DD_ERR("fstat: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fstat(fd, &st) < 0) { DD_ERR("fstat: %s", strerror(errno)); return NULL; } 0 1 1
if (fstat(fd, &st) < 0) { DD_ERR("fstat: %s", strerror(errno)); return NULL; } 0 0 0
828 1 ▶ if ((uint64_t)st.st_size < sizeof(DdHeader)) { DD_ERR("too small"); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if ((uint64_t)st.st_size < sizeof(DdHeader)) { DD_ERR("too small"); return NULL; } 0 1 1
if ((uint64_t)st.st_size < sizeof(DdHeader)) { DD_ERR("too small"); return NULL; } 0 0 0
829 /* before mmap: a creator may truncate the file until it has set magic */
830 uint32_t magic;
831 1 ▶ if (pread(fd, &magic, sizeof magic, offsetof(DdHeader, magic)) != (ssize_t)sizeof magic || magic != DD_MAGIC) {
Branch: 2 branches
BranchTrueFalseTotal
if (pread(fd, &magic, sizeof magic, offsetof(DdHeader, magic)) != (ssize_t)sizeof magic || magic != DD_MAGIC) { 1 0 1
if (pread(fd, &magic, sizeof magic, offsetof(DdHeader, magic)) != (ssize_t)sizeof magic || magic != DD_MAGIC) { 0 1 1
832 0 ▶ DD_ERR("invalid DDSketch table"); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
DD_ERR("invalid DDSketch table"); return NULL; 0 0 0
833 }
834 1 size_t ms = (size_t)st.st_size;
835 1 void *base = mmap(NULL, ms, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
836 1 ▶ if (base == MAP_FAILED) { DD_ERR("mmap: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { DD_ERR("mmap: %s", strerror(errno)); return NULL; } 0 1 1
if (base == MAP_FAILED) { DD_ERR("mmap: %s", strerror(errno)); return NULL; } 0 0 0
837 1 ▶ if (!dd_validate_header((DdHeader *)base, (uint64_t)st.st_size)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!dd_validate_header((DdHeader *)base, (uint64_t)st.st_size)) { 0 1 1
838 0 ▶ DD_ERR("invalid DDSketch table"); munmap(base, ms); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
DD_ERR("invalid DDSketch table"); munmap(base, ms); return NULL; 0 0 0
839 }
840 1 ▶ if (__atomic_load_n(&((DdHeader *)base)->sealed, __ATOMIC_ACQUIRE)) {
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&((DdHeader *)base)->sealed, __ATOMIC_ACQUIRE)) { 0 1 1
841 0 ▶ DD_ERR("this DDSketch is frozen (read-only); open it with new_readonly");
Branch: 1 branch
BranchTrueFalseTotal
DD_ERR("this DDSketch is frozen (read-only); open it with new_readonly"); 0 0 0
842 0 munmap(base, ms); return NULL;
843 }
844 1 int myfd = fcntl(fd, F_DUPFD_CLOEXEC, 0);
845 1 ▶ if (myfd < 0) { DD_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (myfd < 0) { DD_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; } 0 1 1
if (myfd < 0) { DD_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; } 0 0 0
846 1 return dd_setup(base, ms, NULL, myfd);
847 }
848  
849 40 static void dd_destroy(DdHandle *h) {
850 40 ▶ if (!h) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!h) return; 0 40 40
851 /* Release our reader slot on clean teardown (else short-lived-reader churn
852 * exhausts the slot table); skip if a read lock is still held (rdepth>0). */
853 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 && 28 12 40
if (h->reader_slots && h->my_slot_idx != UINT32_MAX && h->cached_pid && 28 0 28
854 28 ▶ h->cached_fork_gen == __atomic_load_n(&dd_fork_gen, __ATOMIC_RELAXED) &&
Branch: 1 branch
BranchTrueFalseTotal
h->cached_fork_gen == __atomic_load_n(&dd_fork_gen, __ATOMIC_RELAXED) && 28 0 28
855 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
856 /* Clear our occ bit BEFORE freeing the slot: we still own the pid so no
857 * claimant can take the slot mid-clear, and rdepth==0 so no writer needs
858 * to see us. (A crash skips this -> the bit is reclaimed lazily by a
859 * writer scan / re-claim, same as the pid.) */
860 28 dd_occ_clear(h, h->my_slot_idx);
861 28 uint32_t expected = h->cached_pid;
862 28 __atomic_compare_exchange_n(&h->reader_slots[h->my_slot_idx].pid,
863 &expected, 0, 0, __ATOMIC_RELEASE, __ATOMIC_RELAXED);
864 }
865 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
866 40 ▶ if (h->base) munmap(h->base, h->mmap_size);
Branch: 1 branch
BranchTrueFalseTotal
if (h->base) munmap(h->base, h->mmap_size); 40 0 40
867 40 free(h->path);
868 40 free(h);
869 }
870  
871 4 static inline int dd_msync(DdHandle *h) {
872 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
873 4 return msync(h->base, h->mmap_size, MS_SYNC);
874 }
875  
876 /* Open a FROZEN (sealed) file read-only: O_RDONLY + PROT_READ, no lock ever.
877 * A sealed file is immutable and no read path writes the mapping, so queries
878 * take no reader-slot / rwlock traffic and any number of processes can share
879 * one PROT_READ mapping (same architecture; the magic rejects a wrong-endian
880 * file). */
881 10 static DdHandle *dd_open_readonly(const char *path, char *errbuf) {
882 10 ▶ if (errbuf) errbuf[0] = '\0';
Branch: 1 branch
BranchTrueFalseTotal
if (errbuf) errbuf[0] = '\0'; 10 0 10
883 10 int fd = open(path, O_RDONLY|O_NOFOLLOW|O_CLOEXEC);
884 10 ▶ if (fd < 0) { DD_ERR("open %s: %s", path, strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fd < 0) { DD_ERR("open %s: %s", path, strerror(errno)); return NULL; } 1 9 10
if (fd < 0) { DD_ERR("open %s: %s", path, strerror(errno)); return NULL; } 1 0 1
885 struct stat st;
886 9 ▶ if (fstat(fd, &st) < 0) { DD_ERR("fstat %s: %s", path, strerror(errno)); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fstat(fd, &st) < 0) { DD_ERR("fstat %s: %s", path, strerror(errno)); close(fd); return NULL; } 0 9 9
if (fstat(fd, &st) < 0) { DD_ERR("fstat %s: %s", path, strerror(errno)); close(fd); return NULL; } 0 0 0
887 9 ▶ if ((uint64_t)st.st_size < sizeof(DdHeader)) { DD_ERR("%s: file too small", path); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if ((uint64_t)st.st_size < sizeof(DdHeader)) { DD_ERR("%s: file too small", path); close(fd); return NULL; } 0 9 9
if ((uint64_t)st.st_size < sizeof(DdHeader)) { DD_ERR("%s: file too small", path); close(fd); return NULL; } 0 0 0
888 /* before mmap: a creator may truncate the file until it has set magic */
889 uint32_t magic;
890 9 ▶ if (pread(fd, &magic, sizeof magic, offsetof(DdHeader, magic)) != (ssize_t)sizeof magic || magic != DD_MAGIC) {
Branch: 2 branches
BranchTrueFalseTotal
if (pread(fd, &magic, sizeof magic, offsetof(DdHeader, magic)) != (ssize_t)sizeof magic || magic != DD_MAGIC) { 9 0 9
if (pread(fd, &magic, sizeof magic, offsetof(DdHeader, magic)) != (ssize_t)sizeof magic || magic != DD_MAGIC) { 0 9 9
891 0 ▶ DD_ERR("%s: invalid DDSketch file", path); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
DD_ERR("%s: invalid DDSketch file", path); close(fd); return NULL; 0 0 0
892 }
893 9 size_t ms = (size_t)st.st_size;
894 9 void *base = mmap(NULL, ms, PROT_READ, MAP_SHARED, fd, 0);
895 9 close(fd); /* the mapping keeps the file; a read-only view needs no fd (no msync/ftruncate) */
896 9 ▶ if (base == MAP_FAILED) { DD_ERR("mmap %s: %s", path, strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { DD_ERR("mmap %s: %s", path, strerror(errno)); return NULL; } 0 9 9
if (base == MAP_FAILED) { DD_ERR("mmap %s: %s", path, strerror(errno)); return NULL; } 0 0 0
897 9 ▶ if (!dd_validate_header((DdHeader *)base, (uint64_t)st.st_size)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!dd_validate_header((DdHeader *)base, (uint64_t)st.st_size)) { 0 9 9
898 0 ▶ DD_ERR("%s: invalid DDSketch file", path); munmap(base, ms); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
DD_ERR("%s: invalid DDSketch file", path); munmap(base, ms); return NULL; 0 0 0
899 }
900 9 ▶ if (!__atomic_load_n(&((DdHeader *)base)->sealed, __ATOMIC_ACQUIRE)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!__atomic_load_n(&((DdHeader *)base)->sealed, __ATOMIC_ACQUIRE)) { 4 5 9
901 4 ▶ DD_ERR("%s is not frozen: call ->freeze on the producer before opening read-only", path);
Branch: 1 branch
BranchTrueFalseTotal
DD_ERR("%s is not frozen: call ->freeze on the producer before opening read-only", path); 4 0 4
902 4 munmap(base, ms); return NULL;
903 }
904 5 DdHandle *h = dd_setup(base, ms, path, -1); /* munmaps on OOM */
905 5 ▶ if (!h) { DD_ERR("out of memory"); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (!h) { DD_ERR("out of memory"); return NULL; } 0 5 5
if (!h) { DD_ERR("out of memory"); return NULL; } 0 0 0
906 5 h->readonly = 1;
907 5 return h;
908 }
909  
910 /* Seal a sketch: make it permanently immutable so it can be shipped and opened
911 * read-only. Takes the write lock so no add/merge/clear is in flight, publishes
912 * the seal, then flushes it (file/memfd-backed). Afterwards every mutator
913 * croaks and a read-write reopen is refused. */
914 2 static int dd_freeze(DdHandle *h) {
915 2 dd_rwlock_wrlock(h);
916 2 __atomic_store_n(&h->hdr->sealed, 1, __ATOMIC_RELEASE);
917 2 dd_rwlock_wrunlock(h);
918 2 ▶ if (h->path || h->backing_fd >= 0) return dd_msync(h); /* durability for file/memfd-backed */
Branch: 2 branches
BranchTrueFalseTotal
if (h->path || h->backing_fd >= 0) return dd_msync(h); /* durability for file/memfd-backed */ 0 2 2
if (h->path || h->backing_fd >= 0) return dd_msync(h); /* durability for file/memfd-backed */ 0 0 0
919 0 return 0; /* anonymous: the seal lives in shared memory (visible to forks); nothing to flush */
920 }
921  
922 /* ================================================================
923 * DDSketch operations (callers hold the lock)
924 *
925 * A value v != 0 maps to a logarithmic bucket key = ceil(log_gamma(|v|)); each
926 * bucket [gamma^(k-1), gamma^k) collects a count, so a bucket's representative
927 * value is within relative error alpha of every value it holds. Positive and
928 * negative magnitudes use separate stores; exact zeros use a dedicated counter.
929 * The bucket key is mapped to a fixed centred window slot = key + bias (bias =
930 * num_buckets/2); keys past either end collapse into the extreme bucket, which
931 * bounds memory while keeping every sketch of the same (alpha, num_buckets)
932 * layout mergeable by a plain element-wise sum.
933 * ================================================================ */
934  
935 /* representative value of positive bucket key k: 2*gamma^k/(gamma+1), the value
936 * whose relative distance to every point in the bucket is at most alpha */
937 34 static inline double dd_value_of_key(DdHandle *h, int64_t key) {
938 34 return 2.0 * pow(h->gamma, (double)key) / (h->gamma + 1.0);
939 }
940  
941 /* map a bucket key to a store slot in the fixed centred window, collapsing keys
942 * past either end into the extreme bucket. */
943 33744 static inline uint64_t dd_slot_of_key(DdHandle *h, int64_t key) {
944 33744 int64_t s = key + (int64_t)h->bias;
945 33744 ▶ if (s < 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (s < 0) return 0; 0 33744 33744
946 33744 ▶ if ((uint64_t)s >= (uint64_t)h->num_buckets) return h->num_buckets ? h->num_buckets - 1 : 0;
Branch: 2 branches
BranchTrueFalseTotal
if ((uint64_t)s >= (uint64_t)h->num_buckets) return h->num_buckets ? h->num_buckets - 1 : 0; 4 33740 33744
if ((uint64_t)s >= (uint64_t)h->num_buckets) return h->num_buckets ? h->num_buckets - 1 : 0; 4 0 4
947 33740 return (uint64_t)s;
948 }
949  
950 /* insert one finite value (caller holds the write lock; caller has rejected NaN/Inf) */
951 33799 static void dd_insert_locked(DdHandle *h, double v, uint64_t count) {
952 33799 DdHeader *hdr = h->hdr;
953 33799 ▶ if (v == 0.0) {
Branch: 1 branch
BranchTrueFalseTotal
if (v == 0.0) { 55 33744 33799
954 55 hdr->zero_count += count;
955 33744 ▶ } else if (h->num_buckets != 0) { /* Layer B: unusable mapping */
Branch: 1 branch
BranchTrueFalseTotal
} else if (h->num_buckets != 0) { /* Layer B: unusable mapping */ 33744 0 33744
956 33744 ▶ double mag = v > 0 ? v : -v;
Branch: 1 branch
BranchTrueFalseTotal
double mag = v > 0 ? v : -v; 32744 1000 33744
957 33744 int64_t key = (int64_t)ceil(log(mag) * h->inv_ln_gamma);
958 33744 uint64_t slot = dd_slot_of_key(h, key);
959 33744 ▶ uint64_t *store = (v > 0) ? dd_pos(h) : dd_neg(h);
Branch: 1 branch
BranchTrueFalseTotal
uint64_t *store = (v > 0) ? dd_pos(h) : dd_neg(h); 32744 1000 33744
960 33744 store[slot] += count;
961 }
962 /* Quantiles walk the buckets up to total_count: a writer killed before it must add nothing. */
963 33799 __atomic_signal_fence(__ATOMIC_SEQ_CST);
964 33799 hdr->total_count += count;
965 33799 hdr->sum += v * (double)count;
966 33799 ▶ if (v < hdr->min_value) hdr->min_value = v;
Branch: 1 branch
BranchTrueFalseTotal
if (v < hdr->min_value) hdr->min_value = v; 22 33777 33799
967 33799 ▶ if (v > hdr->max_value) hdr->max_value = v;
Branch: 1 branch
BranchTrueFalseTotal
if (v > hdr->max_value) hdr->max_value = v; 33738 61 33799
968 33799 }
969  
970 /* value at 0-based rank `rank` (typically q*(count-1)), walking buckets from
971 * most-negative to most-positive; *found set to 1 when a bucket is returned.
972 * (caller holds a lock) */
973 35 static double dd_value_at_rank(DdHandle *h, double rank, int *found) {
974 35 uint64_t nb = h->num_buckets;
975 35 uint64_t cum = 0;
976 35 *found = 1;
977 /* negative store: larger key = more negative value, so walk high slot -> low */
978 35 uint64_t *neg = dd_neg(h);
979 60549 ▶ for (uint64_t i = nb; i-- > 0; ) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint64_t i = nb; i-- > 0; ) { 60516 33 60549
980 60516 cum += neg[i];
981 60516 ▶ if ((double)cum > rank) {
Branch: 1 branch
BranchTrueFalseTotal
if ((double)cum > rank) { 2 60514 60516
982 2 int64_t key = (int64_t)i - (int64_t)h->bias;
983 2 return -dd_value_of_key(h, key);
984 }
985 }
986 /* exact zeros */
987 33 cum += h->hdr->zero_count;
988 33 ▶ if ((double)cum > rank) return 0.0;
Branch: 1 branch
BranchTrueFalseTotal
if ((double)cum > rank) return 0.0; 1 32 33
989 /* positive store: low slot -> high */
990 32 uint64_t *pos = dd_pos(h);
991 37264 ▶ for (uint64_t i = 0; i < nb; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint64_t i = 0; i < nb; i++) { 37264 0 37264
992 37264 cum += pos[i];
993 37264 ▶ if ((double)cum > rank) {
Branch: 1 branch
BranchTrueFalseTotal
if ((double)cum > rank) { 32 37232 37264
994 32 int64_t key = (int64_t)i - (int64_t)h->bias;
995 32 return dd_value_of_key(h, key);
996 }
997 }
998 0 *found = 0; /* rank beyond total (empty) */
999 0 return 0.0;
1000 }
1001  
1002 /* merge another sketch's stores into this one (caller guarantees equal geometry).
1003 * src_neg/src_pos are snapshots of length src_nb. */
1004 2 static void dd_merge_locked(DdHandle *dst, const uint64_t *src_neg, const uint64_t *src_pos,
1005 uint64_t src_nb, uint64_t src_total, uint64_t src_zero,
1006 double src_sum, double src_min, double src_max) {
1007 2 uint64_t nb = dst->num_buckets;
1008 2 ▶ if (nb > src_nb) nb = src_nb; /* Layer B: clamp to both buffers */
Branch: 1 branch
BranchTrueFalseTotal
if (nb > src_nb) nb = src_nb; /* Layer B: clamp to both buffers */ 0 2 2
1009 2 uint64_t *neg = dd_neg(dst), *pos = dd_pos(dst);
1010 3074 ▶ for (uint64_t i = 0; i < nb; i++) { neg[i] += src_neg[i]; pos[i] += src_pos[i]; }
Branch: 1 branch
BranchTrueFalseTotal
for (uint64_t i = 0; i < nb; i++) { neg[i] += src_neg[i]; pos[i] += src_pos[i]; } 3072 2 3074
1011 2 dst->hdr->zero_count += src_zero;
1012 2 __atomic_signal_fence(__ATOMIC_SEQ_CST);
1013 2 dst->hdr->total_count += src_total;
1014 2 dst->hdr->sum += src_sum;
1015 2 ▶ if (src_min < dst->hdr->min_value) dst->hdr->min_value = src_min;
Branch: 1 branch
BranchTrueFalseTotal
if (src_min < dst->hdr->min_value) dst->hdr->min_value = src_min; 0 2 2
1016 2 ▶ if (src_max > dst->hdr->max_value) dst->hdr->max_value = src_max;
Branch: 1 branch
BranchTrueFalseTotal
if (src_max > dst->hdr->max_value) dst->hdr->max_value = src_max; 2 0 2
1017 2 }
1018  
1019 /* reset to an empty sketch (caller holds the write lock) */
1020 1 static inline void dd_clear_locked(DdHandle *h) {
1021 1 DdHeader *hdr = h->hdr;
1022 1 uint64_t nb = h->num_buckets;
1023 1 uint64_t nfit = dd_store_max(h, h->neg_off); /* Layer B: clamp memset to the mapping */
1024 1 uint64_t pfit = dd_store_max(h, h->pos_off);
1025 1 memset(dd_neg(h), 0, (size_t)((nb < nfit ? nb : nfit) * sizeof(uint64_t)));
1026 1 memset(dd_pos(h), 0, (size_t)((nb < pfit ? nb : pfit) * sizeof(uint64_t)));
1027 1 hdr->total_count = 0;
1028 1 hdr->zero_count = 0;
1029 1 hdr->sum = 0.0;
1030 1 hdr->min_value = INFINITY;
1031 1 hdr->max_value = -INFINITY;
1032 1 }
1033  
1034 /* The buckets and zero_count are authoritative after a writer killed mid add,
1035 * merge or clear: recount total_count from them. When it disagrees, sum/min/max
1036 * are re-estimated from the bucket representatives (total last, so a crash here
1037 * is re-detected). Idempotent. */
1038 0 static void dd_repair_locked(DdHandle *h) {
1039 0 DdHeader *hdr = h->hdr;
1040 0 uint64_t nb = h->num_buckets;
1041 0 uint64_t nfit = dd_store_max(h, h->neg_off), pfit = dd_store_max(h, h->pos_off);
1042 0 ▶ if (nb > nfit) nb = nfit;
Branch: 1 branch
BranchTrueFalseTotal
if (nb > nfit) nb = nfit; 0 0 0
1043 0 ▶ if (nb > pfit) nb = pfit;
Branch: 1 branch
BranchTrueFalseTotal
if (nb > pfit) nb = pfit; 0 0 0
1044 0 const uint64_t *neg = dd_neg(h), *pos = dd_pos(h);
1045 0 uint64_t n = hdr->zero_count;
1046 0 ▶ for (uint64_t i = 0; i < nb; i++) n += neg[i] + pos[i];
Branch: 1 branch
BranchTrueFalseTotal
for (uint64_t i = 0; i < nb; i++) n += neg[i] + pos[i]; 0 0 0
1047 0 ▶ if (n == hdr->total_count && (n == 0 || hdr->min_value <= hdr->max_value)) {
Branch: 3 branches
BranchTrueFalseTotal
if (n == hdr->total_count && (n == 0 || hdr->min_value <= hdr->max_value)) { 0 0 0
if (n == hdr->total_count && (n == 0 || hdr->min_value <= hdr->max_value)) { 0 0 0
if (n == hdr->total_count && (n == 0 || hdr->min_value <= hdr->max_value)) { 0 0 0
1048 0 ▶ if (n == 0) { hdr->sum = 0.0; hdr->min_value = INFINITY; hdr->max_value = -INFINITY; }
Branch: 1 branch
BranchTrueFalseTotal
if (n == 0) { hdr->sum = 0.0; hdr->min_value = INFINITY; hdr->max_value = -INFINITY; } 0 0 0
1049 0 return;
1050 }
1051 0 double sum = 0.0, lo = INFINITY, hi = -INFINITY;
1052 0 ▶ if (hdr->zero_count) lo = hi = 0.0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->zero_count) lo = hi = 0.0; 0 0 0
1053 0 ▶ for (uint64_t i = 0; i < nb; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint64_t i = 0; i < nb; i++) { 0 0 0
1054 0 double v = dd_value_of_key(h, (int64_t)i - (int64_t)h->bias);
1055 0 ▶ if (neg[i]) { sum -= v * (double)neg[i]; if (-v < lo) lo = -v; if (-v > hi) hi = -v; }
Branch: 3 branches
BranchTrueFalseTotal
if (neg[i]) { sum -= v * (double)neg[i]; if (-v < lo) lo = -v; if (-v > hi) hi = -v; } 0 0 0
if (neg[i]) { sum -= v * (double)neg[i]; if (-v < lo) lo = -v; if (-v > hi) hi = -v; } 0 0 0
if (neg[i]) { sum -= v * (double)neg[i]; if (-v < lo) lo = -v; if (-v > hi) hi = -v; } 0 0 0
1056 0 ▶ if (pos[i]) { sum += v * (double)pos[i]; if (v < lo) lo = v; if (v > hi) hi = v; }
Branch: 3 branches
BranchTrueFalseTotal
if (pos[i]) { sum += v * (double)pos[i]; if (v < lo) lo = v; if (v > hi) hi = v; } 0 0 0
if (pos[i]) { sum += v * (double)pos[i]; if (v < lo) lo = v; if (v > hi) hi = v; } 0 0 0
if (pos[i]) { sum += v * (double)pos[i]; if (v < lo) lo = v; if (v > hi) hi = v; } 0 0 0
1057 }
1058 0 hdr->sum = sum;
1059 0 hdr->min_value = lo;
1060 0 hdr->max_value = hi;
1061 0 __atomic_signal_fence(__ATOMIC_SEQ_CST);
1062 0 hdr->total_count = n;
1063 }
1064  
1065 #endif /* DD_H */
« blib/lib/Data/DDSketch/Shared.pm ↑ Summary Shared.xs »