topk.h

filter: Statementstmt 72.8% 508 / 697 Branchbran 50.1% 267 / 532 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 63.0% 775 / 1229 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« xxhash.h ↑ Summary Shared.xs »
1 /*
2 * topk.h -- Shared-memory top-k heavy hitters (Space-Saving) for Linux
3 *
4 * Streaming heavy-hitters: with a fixed set of m counters it tracks the m most
5 * frequent keys of a stream and estimates each one's count, using the
6 * Space-Saving algorithm. Observing a monitored key bumps its counter;
7 * observing a new key when full evicts the smallest counter and hands its count
8 * to the newcomer as an over-estimate bound, so a key's true count lies in
9 * [count-error, count]. A min-heap over the counts finds the eviction victim in
10 * O(log m) and an intrusive hash index tests membership in O(1). The counters
11 * live in a shared mapping so several processes feed one summary; a
12 * write-preferring futex rwlock with reader-slot dead-process recovery guards
13 * mutation. Keys are compared by their first key_size bytes.
14 *
15 * Layout: Header -> reader_slots[1024] -> occ bitmap -> slots[m] -> heap[m] -> buckets[nb]
16 */
17  
18 #ifndef TK_H
19 #define TK_H
20  
21 #include <stddef.h>
22 #include <stdint.h>
23 #include <stdlib.h>
24 #include <string.h>
25 #include <unistd.h>
26 #include <fcntl.h>
27 #include <errno.h>
28 #include <time.h>
29 #include <limits.h>
30 #include <signal.h>
31 #include <stdio.h>
32 #include <math.h>
33 #include <sys/mman.h>
34 #include <sys/stat.h>
35 #include <sys/file.h>
36 #include <sys/syscall.h>
37 #include <linux/futex.h>
38 #include <pthread.h>
39  
40 #define XXH_INLINE_ALL
41 #include "xxhash.h"
42  
43 #if defined(__BYTE_ORDER__) && __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
44 #error "topk.h: requires little-endian architecture"
45 #endif
46  
47  
48 /* ================================================================
49 * Constants
50 * ================================================================ */
51  
52 #define TK_MAGIC 0x4B504F54 /* TopK */
53 #define TK_VERSION 2 /* 2: added the occupancy bitmap region (layout change) */
54 #define TK_ERR_BUFLEN (PATH_MAX + 256)
55 #ifndef TK_READER_SLOTS
56 #define TK_READER_SLOTS 1024 /* max concurrent reader processes for dead-process recovery */
57 #endif
58 /* Occupancy bitmap: one bit per reader slot, set when a process claims a slot and
59 * cleared on clean release. A writer scans these TK_OCC_WORDS words to visit
60 * only OCCUPIED slots (O(words + live readers)) instead of all TK_READER_SLOTS. */
61 #define TK_OCC_WORDS (((TK_READER_SLOTS) + 63) / 64) /* 16 for 1024 slots */
62 #define TK_OCC_BYTES ((uint64_t)TK_OCC_WORDS * 8) /* 128 bytes */
63 #define TK_MIN_CAP 1 /* min number of monitored counters */
64 #define TK_MAX_CAP 0x1000000ULL /* 2^24 counters cap */
65 #define TK_MIN_KEYSIZE 1 /* min inline key bytes */
66 #define TK_MAX_KEYSIZE 4096 /* max inline key bytes */
67 #define TK_NIL 0xFFFFFFFFU /* empty slot-index sentinel (hash chains, heap) */
68  
69 #define TK_MODE_PLAIN 0U /* integer counts (classic Space-Saving) */
70 #define TK_MODE_DECAYED 1U /* forward-decayed weighted counts (Cormode) */
71 #define TK_RESCALE_LN 34.0 /* rescale the landmark once alpha*(now-L) exceeds this (g ~ 6e14) */
72  
73 #define TK_ERR(fmt, ...) do { if (errbuf) snprintf(errbuf, TK_ERR_BUFLEN, fmt, ##__VA_ARGS__); } while (0)
74  
75 /* ================================================================
76 * Structs
77 * ================================================================ */
78  
79 /* Per-process slot for dead-process recovery. In the reader-slots-only rwlock a
80 * reader's ENTIRE contribution to the shared lock is `rdepth` in its OWN slot --
81 * there is no separate shared reader counter to fall out of sync with it -- so a
82 * dead reader's contribution is exactly this one word, which a draining writer
83 * neutralises by clearing the slot's pid (the scan then ignores the slot). No
84 * orphaned counter can exist, so there is no quiescent force-reset and sustained
85 * readers cannot starve a writer. _rsv1/_rsv2 are kept only to preserve the
86 * 16-byte slot size across the already-released builds. */
87 typedef struct {
88 uint32_t pid; /* 0 = unclaimed */
89 uint32_t rdepth; /* read-locks THIS process currently holds (recursion-safe) */
90 uint32_t _rsv1; /* reserved (was waiters_parked); unused, kept for layout size */
91 uint32_t _rsv2; /* reserved (was writers_parked); unused, kept for layout size */
92 } TkReaderSlot;
93  
94 struct TkHeader {
95 uint32_t magic, version; /* 0,4 */
96 uint32_t capacity; /* 8 m: number of monitored counters (slots) */
97 uint32_t key_size; /* 12 max inline key bytes */
98 uint64_t hash_buckets; /* 16 number of hash buckets (power of two) */
99 uint64_t used; /* 24 distinct keys currently monitored (<= capacity) */
100 uint64_t seen; /* 32 total observations */
101 uint64_t slots_off; /* 40 offset of the slots array */
102 uint64_t total_size; /* 48 */
103 uint64_t reader_slots_off; /* 56 */
104 uint64_t heap_off; /* 64 offset of the min-heap array (slot indices) */
105 uint32_t wlock; /* 72 WRITER word ONLY: 0 (free) or WRITER_BIT|pid. NOT a reader count. */
106 uint32_t rwait; /* 76 parked-waiter hint (readers+writers blocked on wlock); over-count-safe */
107 uint32_t drain_seq; /* 80 futex bumped by a reader releasing under a draining writer (wakes it) */
108 uint32_t slotless_rdepth; /* readers holding with no reader-slot (documented residual) */
109 uint64_t stat_ops; /* 88 */
110 uint64_t bucket_off; /* 96 offset of the hash bucket array */
111 uint32_t mode; /* 104 TK_MODE_PLAIN | TK_MODE_DECAYED */
112 uint32_t jsift; /* 108 TK_J_UP/DOWN | hole while a heap sift is in flight, else 0 */
113 double alpha; /* 112 decay rate ln(2)/half_life (decayed mode; 0 if plain) */
114 double now; /* 120 current time: max timestamp seen, or per-add tick */
115 double landmark; /* 128 forward-decay landmark L (decayed mode) */
116 uint32_t jslot; /* 136 slot the in-flight sift will place at its hole */
117 /* A rescale in flight, resumed by recovery (carved from the pad, so older files read 0). */
118 uint32_t rs_on; /* 140 */
119 double rs_inv; /* 144 its factor */
120 uint64_t rs_next; /* 152 slots below it are rescaled; | TK_RS_PEND: it is being written */
121 uint64_t rs_count, rs_error; /* 160 while TK_RS_PEND: slot rs_next's new count and error */
122 uint8_t _pad[80]; /* 176..255 */
123 };
124 typedef struct TkHeader TkHeader;
125  
126 _Static_assert(sizeof(TkHeader) == 256, "TkHeader must be 256 bytes");
127  
128 /* Per-slot record: a monitored (key, count, error) triple. The key bytes
129 * (key_size of them) follow this fixed header in memory; the per-slot stride
130 * is sizeof(TkSlot) + align8(key_size). heap_pos is this slot's index in the
131 * min-heap; hnext chains slots that share a hash bucket. */
132 typedef struct {
133 uint64_t count; /* observed count (an upper bound on the true count) */
134 uint64_t error; /* max over-estimate: true count is in [count-error, count] */
135 uint32_t heap_pos; /* position of this slot in the heap array */
136 uint32_t hnext; /* next slot in the hash chain, or TK_NIL */
137 uint32_t key_len; /* stored key length (<= key_size) */
138 uint32_t _pad; /* keep the trailing key bytes 8-aligned */
139 } TkSlot;
140 _Static_assert(sizeof(TkSlot) == 32, "TkSlot must be 32 bytes");
141  
142 /* ---- Process-local handle ---- */
143  
144 typedef struct TkHandle {
145 TkHeader *hdr;
146 TkReaderSlot *reader_slots; /* TK_READER_SLOTS entries */
147 uint64_t *occ; /* TK_OCC_WORDS-word slot-occupancy bitmap (trusted layout offset) */
148 void *base; /* mmap base */
149 uint64_t slots_off; /* validated, cached: never re-read from the peer-writable header */
150 uint64_t heap_off; /* validated, cached */
151 uint64_t bucket_off; /* validated, cached */
152 uint32_t capacity; /* m, cached */
153 uint32_t key_size; /* cached */
154 uint64_t hash_mask; /* hash_buckets - 1, cached */
155 uint64_t stride; /* per-slot byte stride, cached */
156 uint32_t mode; /* TK_MODE_* (cached from validated header) */
157 double alpha; /* decay rate (cached; 0 if plain) */
158 size_t mmap_size;
159 char *path; /* backing file path (strdup'd) */
160 int backing_fd; /* memfd or reopened-fd to close on destroy, -1 for file/anon */
161 uint32_t my_slot_idx; /* UINT32_MAX if all slots taken (no recovery for this handle) */
162 uint32_t cached_pid; /* getpid() cached at last slot claim */
163 uint32_t cached_fork_gen; /* tk_fork_gen value at last slot claim */
164 uint32_t slotless_held; /* read-locks this process holds with no reader-slot */
165 } TkHandle;
166  
167 /* ================================================================
168 * Futex-based write-preferring read-write lock (reader-slots-only)
169 * with dead-process recovery
170 *
171 * The reader count is NOT stored in a shared counter. It is DISTRIBUTED across
172 * per-process reader slots: each slot's `rdepth` is that process's entire
173 * contribution to the lock. A reader publishes its presence in its own slot and
174 * then re-checks the writer word; a writer publishes the writer word and then
175 * scans every slot until all live readers' rdepth reach 0. Sequentially-
176 * consistent store+load on each side (a Dekker handshake) gives mutual exclusion.
177 *
178 * Because a reader's whole contribution is ONE atomic word owned by ONE process,
179 * a crashed reader is recovered by clearing that one slot (CAS its pid to 0) --
180 * there is no second counter to strand, no orphaned +1, and therefore no
181 * quiescent force-reset. A reader killed anywhere in rdlock/rdunlock leaves at
182 * most `rdepth>0` in its dead slot, which the draining writer clears directly, so
183 * sustained read traffic can never starve a writer. Write-preference is inherent
184 * in the gate (new readers see wlock!=0 and yield), so there is no reader-count
185 * yield hack.
186 * ================================================================ */
187  
188 #define TK_RWLOCK_SPIN_LIMIT 32
189 #define TK_LOCK_TIMEOUT_SEC 2 /* FUTEX_WAIT timeout for stale-lock detection / drain re-scan */
190  
191 0 static inline void tk_rwlock_spin_pause(void) {
192 #if defined(__x86_64__) || defined(__i386__)
193 0 __asm__ volatile("pause" ::: "memory");
194 #elif defined(__aarch64__)
195 __asm__ volatile("yield" ::: "memory");
196 #else
197 __asm__ volatile("" ::: "memory");
198 #endif
199 0 }
200  
201 /* Writer word encoding: WRITER_BIT|pid when write-locked, 0 when free. */
202 #define TK_RWLOCK_WRITER_BIT 0x80000000U
203 #define TK_RWLOCK_PID_MASK 0x7FFFFFFFU
204 #define TK_RWLOCK_WR(pid) (TK_RWLOCK_WRITER_BIT | ((uint32_t)(pid) & TK_RWLOCK_PID_MASK))
205  
206 /* A zombie (dead but not yet reaped) still answers kill(pid,0) as alive, so a
207 * process that crashed while holding the lock and lingers unreaped would never
208 * be recovered. Treat /proc/<pid>/stat state 'Z' as dead. Linux-only (as is
209 * this module); if /proc is unreadable we fall back to "alive" (safe: we never
210 * force-recover a possibly-live holder). */
211 0 static inline int tk_pid_is_zombie(uint32_t pid) {
212 char path[32], buf[256];
213 0 snprintf(path, sizeof(path), "/proc/%u/stat", (unsigned)pid);
214 0 int fd = open(path, O_RDONLY | O_CLOEXEC);
215 0 ▶ if (fd < 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (fd < 0) return 0; 0 0 0
216 0 ssize_t n = read(fd, buf, sizeof(buf) - 1);
217 0 close(fd);
218 0 ▶ if (n <= 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (n <= 0) return 0; 0 0 0
219 0 buf[n] = '\0';
220 /* "pid (comm) state ..."; comm may contain ')', so scan to the last one. */
221 0 char *rp = strrchr(buf, ')');
222 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
223 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
224 }
225 /* 1 if alive or unknown, 0 if definitely dead. Cannot detect PID reuse: a
226 * recycled PID reports "alive" and the slot is not reclaimed until that
227 * process exits. See "Crash Safety" in the POD. */
228 0 static inline int tk_pid_alive(uint32_t pid) {
229 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
230 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
231 0 return !tk_pid_is_zombie(pid); /* kill() also succeeds for a zombie -> treat as dead */
232 }
233  
234 static const struct timespec tk_lock_timeout = { TK_LOCK_TIMEOUT_SEC, 0 };
235  
236 /* Process-global fork-generation counter. Incremented in the pthread_atfork
237 * child callback so every open handle detects a fork transition on the next
238 * lock call without paying a getpid() syscall on the hot path. */
239 static uint32_t tk_fork_gen = 1;
240 static pthread_once_t tk_atfork_once = PTHREAD_ONCE_INIT;
241 0 static void tk_on_fork_child(void) {
242 0 __atomic_add_fetch(&tk_fork_gen, 1, __ATOMIC_RELAXED);
243 0 }
244 4 static void tk_atfork_init(void) {
245 4 pthread_atfork(NULL, NULL, tk_on_fork_child);
246 4 }
247  
248 /* Occupancy bitmap: set a slot's bit when it is claimed, clear it on clean
249 * release. SEQ_CST so a set bit is ordered before the slot's rdepth can go
250 * non-zero (bit set in claim, which precedes any rdlock), letting a writer's
251 * SEQ_CST bitmap scan never miss a slot a committed reader holds. */
252 40 static inline void tk_occ_set(TkHandle *h, uint32_t s) {
253 40 __atomic_fetch_or(&h->occ[s >> 6], (uint64_t)1 << (s & 63), __ATOMIC_SEQ_CST);
254 40 }
255 40 static inline void tk_occ_clear(TkHandle *h, uint32_t s) {
256 40 __atomic_fetch_and(&h->occ[s >> 6], ~((uint64_t)1 << (s & 63)), __ATOMIC_SEQ_CST);
257 40 }
258  
259 /* Ensure this process owns a reader slot. Called from the lock helpers so that
260 * fork()'d children pick up their own slot lazily instead of sharing the
261 * parent's. Hot-path is a single relaxed load + compare; only on a
262 * fork-generation mismatch do we touch getpid() and scan slots. */
263 33086 static inline void tk_claim_reader_slot(TkHandle *h) {
264 33086 uint32_t cur_gen = __atomic_load_n(&tk_fork_gen, __ATOMIC_RELAXED);
265 33086 ▶ 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)) 33046 40 33086
if (__builtin_expect(cur_gen == h->cached_fork_gen && h->my_slot_idx != UINT32_MAX, 1)) 33046 0 33046
266 33046 return;
267 /* Cold path -- register the atfork hook once per process, then claim. */
268 40 pthread_once(&tk_atfork_once, tk_atfork_init);
269 /* Re-read after pthread_once: tk_on_fork_child may have bumped it. */
270 40 cur_gen = __atomic_load_n(&tk_fork_gen, __ATOMIC_RELAXED);
271 40 uint32_t now_pid = (uint32_t)getpid();
272 40 h->cached_pid = now_pid;
273 40 ▶ 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 */ 40 0 40
274 40 h->cached_fork_gen = cur_gen;
275 40 h->my_slot_idx = UINT32_MAX;
276 40 uint32_t start = now_pid % TK_READER_SLOTS;
277 /* Pass 1: take a free slot. */
278 42 ▶ for (uint32_t i = 0; i < TK_READER_SLOTS; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t i = 0; i < TK_READER_SLOTS; i++) { 42 0 42
279 42 uint32_t s = (start + i) % TK_READER_SLOTS;
280 42 uint32_t expected = 0;
281 42 ▶ if (__atomic_compare_exchange_n(&h->reader_slots[s].pid,
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_compare_exchange_n(&h->reader_slots[s].pid, 40 2 42
282 &expected, now_pid, 0,
283 __ATOMIC_ACQUIRE, __ATOMIC_RELAXED)) {
284 /* Fresh owner holds no read locks yet; clear any stale rdepth left by
285 * a dead predecessor (its contribution is dropped as we take over). */
286 40 __atomic_store_n(&h->reader_slots[s].rdepth, 0, __ATOMIC_RELAXED);
287 40 tk_occ_set(h, s); /* mark occupied BEFORE any rdlock can bump rdepth */
288 40 h->my_slot_idx = s;
289 40 return;
290 }
291 }
292 /* Pass 2: no free slot -- reclaim one whose owner is dead. Safe to take even
293 * if its rdepth>0: clearing pid drops the dead reader's entire contribution
294 * (a writer scan ignores rdepth when pid==0) and we reset rdepth to 0 as we
295 * claim it. */
296 0 ▶ for (uint32_t i = 0; i < TK_READER_SLOTS; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t i = 0; i < TK_READER_SLOTS; i++) { 0 0 0
297 0 uint32_t dpid = __atomic_load_n(&h->reader_slots[i].pid, __ATOMIC_ACQUIRE);
298 0 ▶ if (dpid == 0 || dpid == now_pid || tk_pid_alive(dpid)) continue;
Branch: 3 branches
BranchTrueFalseTotal
if (dpid == 0 || dpid == now_pid || tk_pid_alive(dpid)) continue; 0 0 0
if (dpid == 0 || dpid == now_pid || tk_pid_alive(dpid)) continue; 0 0 0
if (dpid == 0 || dpid == now_pid || tk_pid_alive(dpid)) continue; 0 0 0
299 0 uint32_t expected = dpid;
300 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
301 __ATOMIC_ACQUIRE, __ATOMIC_RELAXED)) {
302 0 __atomic_store_n(&h->reader_slots[i].rdepth, 0, __ATOMIC_RELAXED);
303 0 tk_occ_set(h, i);
304 0 h->my_slot_idx = i;
305 0 return;
306 }
307 }
308 /* Table full -- leave my_slot_idx = UINT32_MAX so this handle takes the
309 * slotless path (lock still works; recovery of THIS reader's death is the
310 * documented slotless limitation). */
311 }
312  
313 /* Wait until no live reader holds the lock; the caller owns wlock, so no NEW
314 * reader can join (they see wlock!=0 and yield). The SEQ_CST wlock CAS + the
315 * SEQ_CST rdepth loads below are the writer side of the Dekker handshake. */
316 17098 static inline void tk_rwlock_drain(TkHandle *h) {
317 17098 TkHeader *hdr = h->hdr;
318 0 for (;;) {
319 17098 uint32_t v = __atomic_load_n(&hdr->drain_seq, __ATOMIC_ACQUIRE); /* snapshot BEFORE scan */
320 17098 int busy = 0;
321 /* Visit only OCCUPIED slots via the occupancy bitmap (SEQ_CST: a committed
322 * reader's bit -- set in claim, before its rdepth++ -- is ordered before
323 * this scan, so no held slot is skipped). O(TK_OCC_WORDS + live readers)
324 * instead of O(TK_READER_SLOTS). */
325 290666 ▶ for (uint32_t w = 0; w < TK_OCC_WORDS; w++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t w = 0; w < TK_OCC_WORDS; w++) { 273568 17098 290666
326 273568 uint64_t word = __atomic_load_n(&h->occ[w], __ATOMIC_SEQ_CST);
327 290670 ▶ while (word) {
Branch: 1 branch
BranchTrueFalseTotal
while (word) { 17102 273568 290670
328 17102 uint32_t i = (w << 6) + (uint32_t)__builtin_ctzll(word);
329 17102 word &= word - 1; /* consume this bit (local copy) */
330 17102 uint32_t rd = __atomic_load_n(&h->reader_slots[i].rdepth, __ATOMIC_SEQ_CST);
331 17102 ▶ if (rd == 0) continue; /* occupied but not read-locking now */
Branch: 1 branch
BranchTrueFalseTotal
if (rd == 0) continue; /* occupied but not read-locking now */ 17102 0 17102
332 0 uint32_t pid = __atomic_load_n(&h->reader_slots[i].pid, __ATOMIC_ACQUIRE);
333 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
334 0 ▶ if (!tk_pid_alive(pid)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!tk_pid_alive(pid)) { 0 0 0
335 /* Dead reader: drop its pid so the slot no longer counts. Leave
336 * the occ bit set (harmless -- a later scan hits pid==0 and skips,
337 * a re-claim re-sets it) to avoid racing a concurrent claimant. */
338 0 uint32_t ep = pid;
339 0 __atomic_compare_exchange_n(&h->reader_slots[i].pid, &ep, 0,
340 0, __ATOMIC_ACQ_REL, __ATOMIC_RELAXED);
341 0 continue;
342 }
343 0 busy = 1; /* live reader still holding */
344 }
345 }
346 /* A live slotless reader keeps us waiting; a crashed slotless reader that
347 * cannot be attributed to a pid is the documented slotless limitation. */
348 17098 ▶ 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 17098 17098
349 0 busy = 1;
350 17098 ▶ if (!busy)
Branch: 1 branch
BranchTrueFalseTotal
if (!busy) 17098 0 17098
351 17098 return; /* exclusive: wlock held + every rdepth 0 */
352 /* Wait for a reader to release (drain_seq bump) or time out to re-scan
353 * (which reclaims any newly-dead slotted reader). */
354 0 syscall(SYS_futex, &hdr->drain_seq, FUTEX_WAIT, v, &tk_lock_timeout, NULL, 0);
355 }
356 }
357  
358 /* 1 if this process holds a read lock on the segment (through any handle). Such a
359 * lock predates the current wlock holder, whose drain could then never have
360 * finished: it died before mutating anything. */
361 0 static int tk_self_reading(TkHandle *h) {
362 0 ▶ if (h->slotless_held) return 1;
Branch: 1 branch
BranchTrueFalseTotal
if (h->slotless_held) return 1; 0 0 0
363 0 uint32_t me = (uint32_t)getpid();
364 0 ▶ for (uint32_t i = 0; i < TK_READER_SLOTS; i++)
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t i = 0; i < TK_READER_SLOTS; i++) 0 0 0
365 0 ▶ if (__atomic_load_n(&h->reader_slots[i].pid, __ATOMIC_ACQUIRE) == me &&
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&h->reader_slots[i].pid, __ATOMIC_ACQUIRE) == me && 0 0 0
366 0 ▶ __atomic_load_n(&h->reader_slots[i].rdepth, __ATOMIC_ACQUIRE) != 0)
Branch: 1 branch
BranchTrueFalseTotal
__atomic_load_n(&h->reader_slots[i].rdepth, __ATOMIC_ACQUIRE) != 0) 0 0 0
367 0 return 1;
368 0 return 0;
369 }
370  
371 static void tk_repair_locked(TkHandle *h);
372  
373 17098 static inline void tk_release_writer(TkHeader *hdr) {
374 17098 __atomic_store_n(&hdr->wlock, 0, __ATOMIC_RELEASE);
375 17098 __atomic_thread_fence(__ATOMIC_SEQ_CST); /* pair with tk_park: do not miss a new waiter */
376 17098 ▶ if (__atomic_load_n(&hdr->rwait, __ATOMIC_RELAXED) > 0)
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&hdr->rwait, __ATOMIC_RELAXED) > 0) 0 17098 17098
377 0 syscall(SYS_futex, &hdr->wlock, FUTEX_WAKE, INT_MAX, NULL, NULL, 0);
378 17098 }
379  
380 /* Force-recover a stale WRITE lock left by a dead writer (held or mid-drain).
381 * CAS to OUR pid to hold the lock while repairing shared state, then release.
382 * Using our pid (not a bare WRITER_BIT sentinel) means a subsequent recovering
383 * process can detect and re-recover if we crash mid-recovery. */
384 0 static inline void tk_recover_stale_lock(TkHandle *h, uint32_t observed_wlock) {
385 0 TkHeader *hdr = h->hdr;
386 0 uint32_t mypid = TK_RWLOCK_WR((uint32_t)getpid());
387 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
388 mypid, 0, __ATOMIC_SEQ_CST, __ATOMIC_RELAXED))
389 0 return;
390 0 ▶ if (!tk_self_reading(h)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!tk_self_reading(h)) { 0 0 0
391 0 tk_rwlock_drain(h);
392 0 tk_repair_locked(h);
393 }
394 0 tk_release_writer(hdr);
395 }
396  
397 /* Inspect the writer word after a futex-wait timeout. If a dead writer holds
398 * it, force-recover. Dead READERS need no action here: only a writer that owns
399 * wlock drains readers, and it clears dead readers inline in its own scan. */
400 0 static inline void tk_recover_after_timeout(TkHandle *h) {
401 0 uint32_t val = __atomic_load_n(&h->hdr->wlock, __ATOMIC_RELAXED);
402 0 ▶ if (val >= TK_RWLOCK_WRITER_BIT) {
Branch: 1 branch
BranchTrueFalseTotal
if (val >= TK_RWLOCK_WRITER_BIT) { 0 0 0
403 0 uint32_t pid = val & TK_RWLOCK_PID_MASK;
404 0 ▶ if (!tk_pid_alive(pid))
Branch: 1 branch
BranchTrueFalseTotal
if (!tk_pid_alive(pid)) 0 0 0
405 0 tk_recover_stale_lock(h, val);
406 }
407 0 }
408  
409 /* Bump/drop the parked-waiter hint. Both readers (blocked at the gate) and
410 * writers (blocked acquiring wlock) wait on the wlock futex and use this, so
411 * wrunlock/recover know whether a FUTEX_WAKE is worth a syscall. A waiter
412 * SIGKILLed while parked leaves rwait over-counted -> at most a spurious wake
413 * (harmless); it can never under-count, so no wakeup is lost. */
414 0 static inline void tk_park(TkHandle *h) {
415 0 __atomic_add_fetch(&h->hdr->rwait, 1, __ATOMIC_RELAXED);
416 0 __atomic_thread_fence(__ATOMIC_SEQ_CST);
417 0 }
418 0 static inline void tk_unpark(TkHandle *h) {
419 0 __atomic_sub_fetch(&h->hdr->rwait, 1, __ATOMIC_RELAXED);
420 0 }
421  
422 /* Publish (inc) / retract (dec) this reader's presence -- its ENTIRE
423 * contribution to the lock. A slotted reader uses its slot's rdepth; a reader
424 * that could not claim a slot uses the global slotless_rdepth. inc() is SEQ_CST
425 * so the wlock re-check that follows it in rdlock forms a Dekker handshake with
426 * the writer's SEQ_CST wlock-store + rdepth-scan. leave() peels slotless first
427 * so a slot claimed mid-hold cannot misattribute the decrement. */
428 15988 static inline void tk_rdepth_inc(TkHandle *h) {
429 15988 ▶ if (h->my_slot_idx != UINT32_MAX) {
Branch: 1 branch
BranchTrueFalseTotal
if (h->my_slot_idx != UINT32_MAX) { 15988 0 15988
430 15988 __atomic_add_fetch(&h->reader_slots[h->my_slot_idx].rdepth, 1, __ATOMIC_SEQ_CST);
431 } else {
432 0 __atomic_add_fetch(&h->hdr->slotless_rdepth, 1, __ATOMIC_SEQ_CST);
433 0 h->slotless_held++;
434 }
435 15988 }
436 15988 static inline void tk_rdepth_dec(TkHandle *h) {
437 15988 ▶ if (h->slotless_held > 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (h->slotless_held > 0) { 0 15988 15988
438 0 h->slotless_held--;
439 0 __atomic_sub_fetch(&h->hdr->slotless_rdepth, 1, __ATOMIC_SEQ_CST);
440 15988 ▶ } else if (h->my_slot_idx != UINT32_MAX) {
Branch: 1 branch
BranchTrueFalseTotal
} else if (h->my_slot_idx != UINT32_MAX) { 15988 0 15988
441 15988 __atomic_sub_fetch(&h->reader_slots[h->my_slot_idx].rdepth, 1, __ATOMIC_SEQ_CST);
442 }
443 15988 }
444  
445 /* Wake a writer that may be draining readers (it waits on drain_seq). Called
446 * after every rdepth decrement so a released read lock lets the writer re-scan
447 * promptly instead of waiting out its timeout. */
448 15988 static inline void tk_reader_wake_drain(TkHandle *h) {
449 15988 ▶ if (__atomic_load_n(&h->hdr->wlock, __ATOMIC_SEQ_CST) != 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&h->hdr->wlock, __ATOMIC_SEQ_CST) != 0) { 0 15988 15988
450 0 __atomic_add_fetch(&h->hdr->drain_seq, 1, __ATOMIC_RELEASE);
451 0 syscall(SYS_futex, &h->hdr->drain_seq, FUTEX_WAKE, 1, NULL, NULL, 0);
452 }
453 15988 }
454  
455 15988 static inline void tk_rwlock_rdlock(TkHandle *h) {
456 15988 tk_claim_reader_slot(h);
457 15988 TkHeader *hdr = h->hdr;
458 15988 for (int spin = 0; ; spin++) {
459 15988 uint32_t cur = __atomic_load_n(&hdr->wlock, __ATOMIC_ACQUIRE);
460 15988 ▶ if (cur == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (cur == 0) { 15988 0 15988
461 /* Optimistically take the read: publish rdepth, then re-check wlock.
462 * SEQ_CST inc + SEQ_CST load vs the writer's SEQ_CST wlock CAS +
463 * SEQ_CST rdepth scan: by the single total order of SEQ_CST ops the
464 * two sides cannot both miss each other, so we never hold
465 * concurrently with a writer. */
466 15988 tk_rdepth_inc(h);
467 15988 ▶ if (__atomic_load_n(&hdr->wlock, __ATOMIC_SEQ_CST) == 0)
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&hdr->wlock, __ATOMIC_SEQ_CST) == 0) 15988 0 15988
468 15988 return; /* no writer after our publish -> we hold the read lock */
469 /* A writer appeared during our publish -- yield to it (write-preferring). */
470 0 tk_rdepth_dec(h);
471 0 tk_reader_wake_drain(h); /* let the draining writer see rdepth drop */
472 0 spin = 0;
473 0 continue;
474 }
475 /* wlock != 0: a writer holds or is acquiring. Recover if it is dead. */
476 0 if (cur >= TK_RWLOCK_WRITER_BIT &&
477 0 !tk_pid_alive(cur & TK_RWLOCK_PID_MASK)) {
478 0 tk_recover_stale_lock(h, cur);
479 0 spin = 0;
480 0 continue;
481 }
482 0 ▶ if (__builtin_expect(spin < TK_RWLOCK_SPIN_LIMIT, 1)) {
Branch: 1 branch
BranchTrueFalseTotal
if (__builtin_expect(spin < TK_RWLOCK_SPIN_LIMIT, 1)) { 0 0 0
483 0 tk_rwlock_spin_pause();
484 0 continue;
485 }
486 0 tk_park(h);
487 0 cur = __atomic_load_n(&hdr->wlock, __ATOMIC_RELAXED);
488 0 ▶ if (cur != 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (cur != 0) { 0 0 0
489 0 long rc = syscall(SYS_futex, &hdr->wlock, FUTEX_WAIT, cur,
490 &tk_lock_timeout, NULL, 0);
491 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
492 0 tk_unpark(h);
493 0 tk_recover_after_timeout(h);
494 0 spin = 0;
495 0 continue;
496 }
497 }
498 0 tk_unpark(h);
499 0 spin = 0;
500 }
501 }
502  
503 15988 static inline void tk_rwlock_rdunlock(TkHandle *h) {
504 15988 tk_rdepth_dec(h); /* drop our entire contribution before checking the writer */
505 15988 tk_reader_wake_drain(h); /* if a writer is draining, wake it to re-scan */
506 15988 }
507  
508 17098 static inline void tk_rwlock_wrlock(TkHandle *h) {
509 17098 tk_claim_reader_slot(h); /* refresh cached_pid across fork */
510 17098 TkHeader *hdr = h->hdr;
511 /* Encode PID in the wlock word itself (0x80000000 | pid) to eliminate any
512 * crash window between acquiring the lock and storing the owner. */
513 17098 uint32_t mypid = TK_RWLOCK_WR(h->cached_pid);
514 /* Phase 1: acquire the writer word (mutual exclusion among writers). */
515 17098 for (int spin = 0; ; spin++) {
516 17098 uint32_t expected = 0;
517 17098 ▶ if (__atomic_compare_exchange_n(&hdr->wlock, &expected, mypid,
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_compare_exchange_n(&hdr->wlock, &expected, mypid, 17098 0 17098
518 0, __ATOMIC_SEQ_CST, __ATOMIC_RELAXED))
519 17098 break;
520 /* Contended: expected now holds the current wlock value. */
521 0 if (expected >= TK_RWLOCK_WRITER_BIT &&
522 0 !tk_pid_alive(expected & TK_RWLOCK_PID_MASK)) {
523 0 tk_recover_stale_lock(h, expected);
524 0 spin = 0;
525 0 continue;
526 }
527 0 ▶ if (__builtin_expect(spin < TK_RWLOCK_SPIN_LIMIT, 1)) {
Branch: 1 branch
BranchTrueFalseTotal
if (__builtin_expect(spin < TK_RWLOCK_SPIN_LIMIT, 1)) { 0 0 0
528 0 tk_rwlock_spin_pause();
529 0 continue;
530 }
531 0 tk_park(h);
532 0 uint32_t cur = __atomic_load_n(&hdr->wlock, __ATOMIC_RELAXED);
533 0 ▶ if (cur != 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (cur != 0) { 0 0 0
534 0 long rc = syscall(SYS_futex, &hdr->wlock, FUTEX_WAIT, cur,
535 &tk_lock_timeout, NULL, 0);
536 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
537 0 tk_unpark(h);
538 0 tk_recover_after_timeout(h);
539 0 spin = 0;
540 0 continue;
541 }
542 }
543 0 tk_unpark(h);
544 0 spin = 0;
545 }
546 /* Phase 2: drain the readers that were already holding when we won the CAS. */
547 17098 tk_rwlock_drain(h);
548 17098 }
549  
550 17098 static inline void tk_rwlock_wrunlock(TkHandle *h) {
551 17098 tk_release_writer(h->hdr);
552 17098 }
553  
554 /* ================================================================
555 * Layout math + create / open / destroy
556 *
557 * Layout: Header -> reader_slots[1024] -> slots[m] -> heap[m] -> buckets[nb]
558 * slots[] : m records of (count, error, key); stride = sizeof(TkSlot)+align8(key_size)
559 * heap[] : m uint32 slot-indices, a min-heap ordered by slot count
560 * buckets[] : nb uint32 slot-indices (or TK_NIL), an intrusive hash index
561 * ================================================================ */
562  
563 #define TK_SLOT_OK(h, i) ((uint64_t)(i) < (uint64_t)(h)->capacity)
564  
565 /* Single source of truth for the mmap region layout offsets:
566 * Header -> reader_slots[] -> occ bitmap -> slots[] -> heap[] -> buckets[]. */
567 typedef struct { uint64_t reader_slots, occ, slots, heap, buckets, total; } TkLayout;
568  
569 /* per-slot byte stride for a given key_size (keeps each slot 8-aligned) */
570 179 static inline uint64_t tk_stride(uint32_t key_size) {
571 179 return (uint64_t)sizeof(TkSlot) + (((uint64_t)key_size + 7) & ~(uint64_t)7);
572 }
573  
574 /* number of hash buckets for m counters: next_pow2(2*m), floor 8 (load <= 0.5) */
575 179 static inline uint64_t tk_buckets_for(uint64_t m) {
576 179 uint64_t want = m * 2;
577 179 ▶ if (want < 8) want = 8;
Branch: 1 branch
BranchTrueFalseTotal
if (want < 8) want = 8; 63 116 179
578 179 ▶ if ((want & (want - 1)) == 0) return want;
Branch: 1 branch
BranchTrueFalseTotal
if ((want & (want - 1)) == 0) return want; 120 59 179
579 59 return 1ULL << (64 - __builtin_clzll(want));
580 }
581  
582 136 static inline TkLayout tk_layout_for(uint32_t m, uint32_t key_size) {
583 TkLayout L;
584 136 uint64_t stride = tk_stride(key_size);
585 136 L.reader_slots = sizeof(TkHeader);
586 136 L.occ = L.reader_slots + (uint64_t)TK_READER_SLOTS * sizeof(TkReaderSlot);
587 136 L.slots = L.occ + TK_OCC_BYTES;
588 136 L.slots = (L.slots + 7) & ~(uint64_t)7;
589 136 L.heap = L.slots + (uint64_t)m * stride;
590 136 L.heap = (L.heap + 7) & ~(uint64_t)7;
591 136 L.buckets = L.heap + (uint64_t)m * sizeof(uint32_t);
592 136 L.buckets = (L.buckets + 7) & ~(uint64_t)7;
593 136 L.total = L.buckets + tk_buckets_for(m) * sizeof(uint32_t);
594 136 return L;
595 }
596  
597 50 static inline uint64_t tk_total_size(uint32_t m, uint32_t key_size) {
598 50 return tk_layout_for(m, key_size).total;
599 }
600  
601 38 static inline void tk_init_header(void *base, uint32_t m, uint32_t key_size, uint32_t mode, double alpha, uint64_t total) {
602 38 TkLayout L = tk_layout_for(m, key_size);
603 38 TkHeader *hdr = (TkHeader *)base;
604 /* Zero header + reader-slots + slots + heap, then set every hash bucket to
605 TK_NIL (0xFF bytes) so the table starts empty. */
606 38 memset(base, 0, (size_t)L.buckets);
607 38 memset((char *)base + L.buckets, 0xFF, (size_t)(L.total - L.buckets)); /* buckets = TK_NIL */
608 38 hdr->version = TK_VERSION;
609 38 hdr->capacity = m;
610 38 hdr->key_size = key_size;
611 38 hdr->hash_buckets = tk_buckets_for(m);
612 38 hdr->used = 0;
613 38 hdr->seen = 0;
614 38 hdr->slots_off = L.slots;
615 38 hdr->total_size = total;
616 38 hdr->reader_slots_off = L.reader_slots;
617 38 hdr->heap_off = L.heap;
618 38 hdr->bucket_off = L.buckets;
619 38 hdr->mode = mode;
620 38 hdr->alpha = alpha;
621 38 hdr->now = 0.0;
622 38 hdr->landmark = 0.0;
623 /* Publish magic LAST, as a release store: it is the commit point, so a
624 creator killed before it leaves magic==0 and never a file mistaken for
625 a valid one. A kill during the field stores leaves one to remove by
626 hand. */
627 38 __atomic_store_n(&hdr->magic, TK_MAGIC, __ATOMIC_RELEASE);
628 38 __atomic_thread_fence(__ATOMIC_SEQ_CST);
629 38 }
630  
631 /* ---- accessors ---- */
632 178527 static inline TkSlot *tk_slot(TkHandle *h, uint64_t i) {
633 178527 return (TkSlot *)((char *)h->base + h->slots_off + i * h->stride);
634 }
635 54460 static inline char *tk_slot_key(TkSlot *s) { return (char *)s + sizeof(TkSlot); }
636 22515 static inline uint32_t *tk_heap(TkHandle *h) {
637 22515 return (uint32_t *)((char *)h->base + h->heap_off);
638 }
639 59290 static inline uint32_t *tk_buckets(TkHandle *h) {
640 59290 return (uint32_t *)((char *)h->base + h->bucket_off);
641 }
642  
643 /* Layer B trusted bound: the number of slots guaranteed to lie within the real
644 * mapping. Derived from the process-local mmap_size (fixed at attach, not
645 * peer-writable) and the SAME slots_off/stride the accessors use, so a corrupt
646 * hdr->capacity can never drive a slot access outside the mapping. Equals m
647 * for a valid table; every clamp below it is a never-taken branch in normal use. */
648 270 static inline uint64_t tk_slots_max(TkHandle *h) {
649 270 ▶ if (h->slots_off >= h->mmap_size || h->stride == 0) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (h->slots_off >= h->mmap_size || h->stride == 0) return 0; 270 0 270
if (h->slots_off >= h->mmap_size || h->stride == 0) return 0; 0 270 270
650 270 return (h->mmap_size - h->slots_off) / h->stride;
651 }
652  
653 43 static inline TkHandle *tk_setup(void *base, size_t map_size,
654 const char *path, int backing_fd) {
655 43 TkHeader *hdr = (TkHeader *)base;
656 43 TkHandle *h = (TkHandle *)calloc(1, sizeof(TkHandle));
657 43 ▶ if (!h) {
Branch: 1 branch
BranchTrueFalseTotal
if (!h) { 0 43 43
658 0 munmap(base, map_size);
659 0 ▶ if (backing_fd >= 0) close(backing_fd);
Branch: 1 branch
BranchTrueFalseTotal
if (backing_fd >= 0) close(backing_fd); 0 0 0
660 0 return NULL;
661 }
662 43 h->hdr = hdr;
663 43 h->base = base;
664 43 h->reader_slots = (TkReaderSlot *)((uint8_t *)base + sizeof(TkHeader)); /* trusted layout, not the peer-writable header offset */
665 /* occ offset is invariant to capacity/key_size (reader_slots + a compile-time
666 * constant), so this is a trusted layout offset independent of the header. */
667 43 h->occ = (uint64_t *)((uint8_t *)base + tk_layout_for(0, 0).occ);
668 /* single validated read of each geometry field; cached so the process-local
669 bound and the pointers it feeds stay consistent even if a peer later
670 corrupts the shared header. */
671 43 h->slots_off = hdr->slots_off;
672 43 h->heap_off = hdr->heap_off;
673 43 h->bucket_off = hdr->bucket_off;
674 43 h->capacity = hdr->capacity;
675 43 h->key_size = hdr->key_size;
676 43 h->hash_mask = hdr->hash_buckets - 1;
677 43 h->stride = tk_stride(hdr->key_size);
678 43 h->mode = hdr->mode;
679 43 h->alpha = hdr->alpha;
680 43 h->mmap_size = map_size;
681 /* Layer B: if the mapping cannot even hold `capacity` slots the header lied
682 about its size; clamp the cached capacity to what actually fits. (Uses
683 h->mmap_size + h->slots_off + h->stride, all set just above.) */
684 {
685 43 uint64_t fit = tk_slots_max(h);
686 43 ▶ if ((uint64_t)h->capacity > fit) h->capacity = (uint32_t)fit;
Branch: 1 branch
BranchTrueFalseTotal
if ((uint64_t)h->capacity > fit) h->capacity = (uint32_t)fit; 0 43 43
687 }
688 43 ▶ h->path = path ? strdup(path) : NULL;
Branch: 1 branch
BranchTrueFalseTotal
h->path = path ? strdup(path) : NULL; 9 34 43
689 43 h->backing_fd = backing_fd;
690 43 h->my_slot_idx = UINT32_MAX;
691 43 return h;
692 }
693  
694 /* Validate a mapped header (shared by tk_create reopen and tk_open_fd). */
695 9 static inline int tk_validate_header(const TkHeader *hdr, uint64_t file_size) {
696 9 ▶ if (hdr->magic != TK_MAGIC) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->magic != TK_MAGIC) return 0; 4 5 9
697 5 ▶ if (hdr->version != TK_VERSION) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->version != TK_VERSION) return 0; 0 5 5
698 5 ▶ if (hdr->mode != TK_MODE_PLAIN && hdr->mode != TK_MODE_DECAYED) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (hdr->mode != TK_MODE_PLAIN && hdr->mode != TK_MODE_DECAYED) return 0; 2 3 5
if (hdr->mode != TK_MODE_PLAIN && hdr->mode != TK_MODE_DECAYED) return 0; 0 2 2
699 5 ▶ if (hdr->mode == TK_MODE_DECAYED && !(hdr->alpha > 0.0 && isfinite(hdr->alpha))) return 0;
Branch: 3 branches
BranchTrueFalseTotal
if (hdr->mode == TK_MODE_DECAYED && !(hdr->alpha > 0.0 && isfinite(hdr->alpha))) return 0; 2 3 5
if (hdr->mode == TK_MODE_DECAYED && !(hdr->alpha > 0.0 && isfinite(hdr->alpha))) return 0; 2 0 2
if (hdr->mode == TK_MODE_DECAYED && !(hdr->alpha > 0.0 && isfinite(hdr->alpha))) return 0; 0 2 2
700 5 ▶ if (hdr->mode == TK_MODE_DECAYED && (!isfinite(hdr->now) || !isfinite(hdr->landmark))) return 0;
Branch: 3 branches
BranchTrueFalseTotal
if (hdr->mode == TK_MODE_DECAYED && (!isfinite(hdr->now) || !isfinite(hdr->landmark))) return 0; 2 3 5
if (hdr->mode == TK_MODE_DECAYED && (!isfinite(hdr->now) || !isfinite(hdr->landmark))) return 0; 2 0 2
if (hdr->mode == TK_MODE_DECAYED && (!isfinite(hdr->now) || !isfinite(hdr->landmark))) return 0; 0 2 2
701 5 ▶ if (hdr->capacity < TK_MIN_CAP || hdr->capacity > TK_MAX_CAP) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (hdr->capacity < TK_MIN_CAP || hdr->capacity > TK_MAX_CAP) return 0; 5 0 5
if (hdr->capacity < TK_MIN_CAP || hdr->capacity > TK_MAX_CAP) return 0; 0 5 5
702 5 ▶ if (hdr->key_size < TK_MIN_KEYSIZE || hdr->key_size > TK_MAX_KEYSIZE) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (hdr->key_size < TK_MIN_KEYSIZE || hdr->key_size > TK_MAX_KEYSIZE) return 0; 5 0 5
if (hdr->key_size < TK_MIN_KEYSIZE || hdr->key_size > TK_MAX_KEYSIZE) return 0; 0 5 5
703 5 ▶ if (hdr->hash_buckets != tk_buckets_for(hdr->capacity)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->hash_buckets != tk_buckets_for(hdr->capacity)) return 0; 0 5 5
704 5 ▶ if (hdr->used > hdr->capacity) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->used > hdr->capacity) return 0; 0 5 5
705 5 ▶ if (hdr->total_size != file_size) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->total_size != file_size) return 0; 0 5 5
706 5 ▶ if (hdr->total_size != tk_total_size((uint32_t)hdr->capacity, hdr->key_size)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->total_size != tk_total_size((uint32_t)hdr->capacity, hdr->key_size)) return 0; 0 5 5
707 5 TkLayout L = tk_layout_for((uint32_t)hdr->capacity, hdr->key_size);
708 5 ▶ 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 5 5
709 5 ▶ if (hdr->slots_off != L.slots) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->slots_off != L.slots) return 0; 0 5 5
710 5 ▶ if (hdr->heap_off != L.heap) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->heap_off != L.heap) return 0; 0 5 5
711 5 ▶ if (hdr->bucket_off != L.buckets) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->bucket_off != L.buckets) return 0; 0 5 5
712 5 return 1;
713 }
714  
715 /* validate the requested capacity + key_size */
716 47 static int tk_validate_args(uint64_t capacity, uint64_t key_size, char *errbuf) {
717 47 ▶ if (errbuf) errbuf[0] = '\0';
Branch: 1 branch
BranchTrueFalseTotal
if (errbuf) errbuf[0] = '\0'; 47 0 47
718 47 ▶ if (capacity < TK_MIN_CAP || capacity > TK_MAX_CAP) { TK_ERR("capacity must be between 1 and 2^24"); return 0; }
Branch: 3 branches
BranchTrueFalseTotal
if (capacity < TK_MIN_CAP || capacity > TK_MAX_CAP) { TK_ERR("capacity must be between 1 and 2^24"); return 0; } 47 0 47
if (capacity < TK_MIN_CAP || capacity > TK_MAX_CAP) { TK_ERR("capacity must be between 1 and 2^24"); return 0; } 0 47 47
if (capacity < TK_MIN_CAP || capacity > TK_MAX_CAP) { TK_ERR("capacity must be between 1 and 2^24"); return 0; } 0 0 0
719 47 ▶ if (key_size < TK_MIN_KEYSIZE || key_size > TK_MAX_KEYSIZE) { TK_ERR("key_size must be between 1 and 4096"); return 0; }
Branch: 3 branches
BranchTrueFalseTotal
if (key_size < TK_MIN_KEYSIZE || key_size > TK_MAX_KEYSIZE) { TK_ERR("key_size must be between 1 and 4096"); return 0; } 46 1 47
if (key_size < TK_MIN_KEYSIZE || key_size > TK_MAX_KEYSIZE) { TK_ERR("key_size must be between 1 and 4096"); return 0; } 1 45 46
if (key_size < TK_MIN_KEYSIZE || key_size > TK_MAX_KEYSIZE) { TK_ERR("key_size must be between 1 and 4096"); return 0; } 2 0 2
720 45 return 1;
721 }
722  
723 /* Securely obtain a fd for a path-backed segment: create it exclusively
724 * (O_CREAT|O_EXCL|O_NOFOLLOW at `mode`, default 0600 = owner-only), or, if it
725 * already exists, attach to it (O_RDWR|O_NOFOLLOW, no O_CREAT). O_EXCL blocks a
726 * pre-seeded or hard-linked file and O_NOFOLLOW a symlink swap, so a local
727 * attacker can no longer redirect or poison the backing store through the path.
728 * Cross-user sharing is opt-in via a wider `mode` (e.g. 0660); the caller still
729 * validates the file's contents via tk_validate_header. */
730 13 static int tk_secure_open(const char *path, mode_t mode, char *errbuf) {
731 13 ▶ for (int attempt = 0; attempt < 100; attempt++) {
Branch: 1 branch
BranchTrueFalseTotal
for (int attempt = 0; attempt < 100; attempt++) { 13 0 13
732 13 int fd = open(path, O_RDWR|O_CREAT|O_EXCL|O_NOFOLLOW|O_CLOEXEC, mode);
733 13 ▶ 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 */ 5 8 13
734 8 ▶ if (errno != EEXIST) { TK_ERR("create %s: %s", path, strerror(errno)); return -1; }
Branch: 2 branches
BranchTrueFalseTotal
if (errno != EEXIST) { TK_ERR("create %s: %s", path, strerror(errno)); return -1; } 0 8 8
if (errno != EEXIST) { TK_ERR("create %s: %s", path, strerror(errno)); return -1; } 0 0 0
735 8 fd = open(path, O_RDWR|O_NOFOLLOW|O_CLOEXEC);
736 8 ▶ if (fd >= 0) return fd;
Branch: 1 branch
BranchTrueFalseTotal
if (fd >= 0) return fd; 8 0 8
737 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
738 0 ▶ TK_ERR("open %s: %s", path, strerror(errno)); /* ELOOP => symlink rejected */
Branch: 1 branch
BranchTrueFalseTotal
TK_ERR("open %s: %s", path, strerror(errno)); /* ELOOP => symlink rejected */ 0 0 0
739 0 return -1;
740 }
741 0 ▶ TK_ERR("open %s: create/attach kept racing", path);
Branch: 1 branch
BranchTrueFalseTotal
TK_ERR("open %s: create/attach kept racing", path); 0 0 0
742 0 return -1;
743 }
744  
745 /* True iff the whole file is zero -- what an abandoned mid-init
746 creator leaves. Lets recovery re-init only a provably-empty file, never
747 one that merely starts with a zero word. Cold path, so a byte scan is
748 fine. Read, not mapped: a read fault on a tmpfs hole allocates the page. */
749 2 static int tk_file_is_zero(int fd, uint64_t size) {
750 char buf[16384];
751 5 ▶ for (uint64_t off = 0; off < size; ) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint64_t off = 0; off < size; ) { 4 1 5
752 4 ssize_t n = pread(fd, buf, size - off < sizeof buf ? (size_t)(size - off) : sizeof buf, (off_t)off);
753 4 ▶ if (n <= 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (n <= 0) return 0; 0 4 4
754 41363 ▶ 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 41359 41360
for (ssize_t i = 0; i < n; i++) if (buf[i]) return 0; 41360 3 41363
755 3 off += (uint64_t)n;
756 }
757 1 return 1;
758 }
759  
760 /* A sparse segment would SIGBUS at the first write the filesystem cannot back. */
761 8 static int tk_reserve(int fd, uint64_t size) {
762 8 const char *sp = getenv("DATA_TOPK_SHARED_SPARSE");
763 8 ▶ if (sp && *sp && strcmp(sp, "0")) return 0;
Branch: 3 branches
BranchTrueFalseTotal
if (sp && *sp && strcmp(sp, "0")) return 0; 0 8 8
if (sp && *sp && strcmp(sp, "0")) return 0; 0 0 0
if (sp && *sp && strcmp(sp, "0")) return 0; 0 0 0
764 /* Before Linux 6.11 tmpfs gives up at any pending signal and undoes the allocation, so a
765 * periodic one could keep it from ever completing; SIGSTOP cannot be blocked. */
766 sigset_t all, old;
767 8 sigfillset(&all);
768 8 sigprocmask(SIG_BLOCK, &all, &old);
769 int e;
770 8 ▶ 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 8 8
771 8 sigprocmask(SIG_SETMASK, &old, NULL);
772 8 ▶ if (e == 0 || e == EOPNOTSUPP || e == EINVAL) return 0;
Branch: 3 branches
BranchTrueFalseTotal
if (e == 0 || e == EOPNOTSUPP || e == EINVAL) return 0; 0 8 8
if (e == 0 || e == EOPNOTSUPP || e == EINVAL) return 0; 0 0 0
if (e == 0 || e == EOPNOTSUPP || e == EINVAL) return 0; 0 0 0
773 0 errno = e;
774 0 return -1;
775 }
776  
777 45 static TkHandle *tk_create(const char *path, uint64_t capacity, uint64_t key_size, uint32_t tkmode, double alpha, mode_t mode, char *errbuf) {
778 45 ▶ if (!tk_validate_args(capacity, key_size, errbuf)) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!tk_validate_args(capacity, key_size, errbuf)) return NULL; 2 43 45
779  
780 43 uint64_t total = tk_total_size((uint32_t)capacity, (uint32_t)key_size);
781 43 int anonymous = (path == NULL);
782 43 int fd = -1;
783 size_t map_size;
784 void *base;
785  
786 43 ▶ if (anonymous) {
Branch: 1 branch
BranchTrueFalseTotal
if (anonymous) { 30 13 43
787 30 map_size = (size_t)total;
788 30 base = mmap(NULL, map_size, PROT_READ|PROT_WRITE, MAP_SHARED|MAP_ANONYMOUS, -1, 0);
789 30 ▶ if (base == MAP_FAILED) { TK_ERR("mmap: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { TK_ERR("mmap: %s", strerror(errno)); return NULL; } 0 30 30
if (base == MAP_FAILED) { TK_ERR("mmap: %s", strerror(errno)); return NULL; } 0 0 0
790 } else {
791 13 fd = tk_secure_open(path, mode, errbuf);
792 21 ▶ if (fd < 0) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (fd < 0) return NULL; 0 13 13
793 13 ▶ if (flock(fd, LOCK_EX) < 0) { TK_ERR("flock: %s", strerror(errno)); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (flock(fd, LOCK_EX) < 0) { TK_ERR("flock: %s", strerror(errno)); close(fd); return NULL; } 0 13 13
if (flock(fd, LOCK_EX) < 0) { TK_ERR("flock: %s", strerror(errno)); close(fd); return NULL; } 0 0 0
794 struct stat st;
795 13 ▶ if (fstat(fd, &st) < 0) { TK_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fstat(fd, &st) < 0) { TK_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; } 0 13 13
if (fstat(fd, &st) < 0) { TK_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; } 0 0 0
796 13 int is_new = (st.st_size == 0);
797 13 ▶ if (!is_new && (uint64_t)st.st_size < sizeof(TkHeader)) {
Branch: 2 branches
BranchTrueFalseTotal
if (!is_new && (uint64_t)st.st_size < sizeof(TkHeader)) { 8 5 13
if (!is_new && (uint64_t)st.st_size < sizeof(TkHeader)) { 1 7 8
798 1 ▶ TK_ERR("%s: file too small (%lld)", path, (long long)st.st_size);
Branch: 1 branch
BranchTrueFalseTotal
TK_ERR("%s: file too small (%lld)", path, (long long)st.st_size); 1 0 1
799 1 flock(fd, LOCK_UN); close(fd); return NULL;
800 }
801 12 ▶ 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)) { 5 7 12
if (is_new && (st.st_uid != geteuid() || fchmod(fd, mode) < 0)) { 5 0 5
if (is_new && (st.st_uid != geteuid() || fchmod(fd, mode) < 0)) { 0 5 5
802 0 ▶ TK_ERR("%s: refusing to initialize file not owned by us", path);
Branch: 1 branch
BranchTrueFalseTotal
TK_ERR("%s: refusing to initialize file not owned by us", path); 0 0 0
803 0 flock(fd, LOCK_UN); close(fd); return NULL;
804 }
805 12 ▶ if (is_new && ftruncate(fd, (off_t)total) < 0) {
Branch: 2 branches
BranchTrueFalseTotal
if (is_new && ftruncate(fd, (off_t)total) < 0) { 5 7 12
if (is_new && ftruncate(fd, (off_t)total) < 0) { 0 5 5
806 0 ▶ TK_ERR("ftruncate: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
TK_ERR("ftruncate: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; 0 0 0
807 }
808 12 ▶ if (is_new && tk_reserve(fd, total) < 0) {
Branch: 2 branches
BranchTrueFalseTotal
if (is_new && tk_reserve(fd, total) < 0) { 5 7 12
if (is_new && tk_reserve(fd, total) < 0) { 0 5 5
809 0 ▶ TK_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
TK_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno)); 0 0 0
810 0 if (ftruncate(fd, 0) < 0) { /* best effort */ }
811 0 flock(fd, LOCK_UN); close(fd); return NULL;
812 }
813 12 ▶ map_size = is_new ? (size_t)total : (size_t)st.st_size;
Branch: 1 branch
BranchTrueFalseTotal
map_size = is_new ? (size_t)total : (size_t)st.st_size; 7 5 12
814 12 base = mmap(NULL, map_size, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
815 12 ▶ if (base == MAP_FAILED) {
Branch: 1 branch
BranchTrueFalseTotal
if (base == MAP_FAILED) { 0 12 12
816 0 ▶ TK_ERR("mmap: %s", strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
TK_ERR("mmap: %s", strerror(errno)); 0 0 0
817 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
818 0 flock(fd, LOCK_UN); close(fd); return NULL;
819 }
820 12 ▶ if (!is_new) {
Branch: 1 branch
BranchTrueFalseTotal
if (!is_new) { 7 5 12
821 7 ▶ if (!tk_validate_header((TkHeader *)base, (uint64_t)st.st_size)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!tk_validate_header((TkHeader *)base, (uint64_t)st.st_size)) { 4 3 7
822 /* Recover an abandoned mid-init file: a creator killed
823 * between the ftruncate and the header init leaves a
824 * full-size, all-zero (magic==0) file that would brick every
825 * future open of this path. Re-initialize ONLY when it is
826 * exactly our size, still uninitialized, and owned by us;
827 * anything else still errors. */
828 4 ▶ if (((TkHeader *)base)->magic == 0 && (uint64_t)st.st_size == total
Branch: 2 branches
BranchTrueFalseTotal
if (((TkHeader *)base)->magic == 0 && (uint64_t)st.st_size == total 3 1 4
if (((TkHeader *)base)->magic == 0 && (uint64_t)st.st_size == total 2 1 3
829 2 ▶ && st.st_uid == geteuid() && tk_file_is_zero(fd, map_size)) {
Branch: 2 branches
BranchTrueFalseTotal
&& st.st_uid == geteuid() && tk_file_is_zero(fd, map_size)) { 2 0 2
&& st.st_uid == geteuid() && tk_file_is_zero(fd, map_size)) { 1 1 2
830 1 ▶ if (fchmod(fd, mode) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (fchmod(fd, mode) < 0) { 0 1 1
831 0 ▶ TK_ERR("%s: fchmod: %s", path, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
TK_ERR("%s: fchmod: %s", path, strerror(errno)); 0 0 0
832 0 munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
833 }
834 1 ▶ if (tk_reserve(fd, total) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (tk_reserve(fd, total) < 0) { 0 1 1
835 0 ▶ TK_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
TK_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno)); 0 0 0
836 0 munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
837 }
838 1 tk_init_header(base, (uint32_t)capacity, (uint32_t)key_size, tkmode, alpha, total);
839 1 flock(fd, LOCK_UN); close(fd);
840 1 return tk_setup(base, map_size, path, -1);
841 }
842 3 ▶ if (((TkHeader *)base)->magic == 0 && (uint64_t)st.st_size == total
Branch: 2 branches
BranchTrueFalseTotal
if (((TkHeader *)base)->magic == 0 && (uint64_t)st.st_size == total 2 1 3
if (((TkHeader *)base)->magic == 0 && (uint64_t)st.st_size == total 1 1 2
843 1 ▶ && st.st_uid == geteuid()) {
Branch: 1 branch
BranchTrueFalseTotal
&& st.st_uid == geteuid()) { 1 0 1
844 1 ▶ TK_ERR("%s: incomplete top-k table file left by an interrupted create; remove it and retry", path);
Branch: 1 branch
BranchTrueFalseTotal
TK_ERR("%s: incomplete top-k table file left by an interrupted create; remove it and retry", path); 1 0 1
845 1 munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
846 }
847 2 ▶ TK_ERR("invalid top-k table file"); munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
TK_ERR("invalid top-k table file"); munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL; 2 0 2
848 }
849 3 flock(fd, LOCK_UN); close(fd);
850 3 return tk_setup(base, map_size, path, -1);
851 }
852 }
853 35 tk_init_header(base, (uint32_t)capacity, (uint32_t)key_size, tkmode, alpha, total);
854 35 ▶ if (fd >= 0) { flock(fd, LOCK_UN); close(fd); }
Branch: 1 branch
BranchTrueFalseTotal
if (fd >= 0) { flock(fd, LOCK_UN); close(fd); } 5 30 35
855 35 return tk_setup(base, map_size, path, -1);
856 }
857  
858 2 static TkHandle *tk_create_memfd(const char *name, uint64_t capacity, uint64_t key_size, uint32_t tkmode, double alpha, char *errbuf) {
859 2 ▶ if (!tk_validate_args(capacity, key_size, errbuf)) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!tk_validate_args(capacity, key_size, errbuf)) return NULL; 0 2 2
860  
861 2 uint64_t total = tk_total_size((uint32_t)capacity, (uint32_t)key_size);
862 2 ▶ int fd = memfd_create(name ? name : "topk", MFD_CLOEXEC | MFD_ALLOW_SEALING);
Branch: 1 branch
BranchTrueFalseTotal
int fd = memfd_create(name ? name : "topk", MFD_CLOEXEC | MFD_ALLOW_SEALING); 2 0 2
863 2 ▶ if (fd < 0) { TK_ERR("memfd_create: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fd < 0) { TK_ERR("memfd_create: %s", strerror(errno)); return NULL; } 0 2 2
if (fd < 0) { TK_ERR("memfd_create: %s", strerror(errno)); return NULL; } 0 0 0
864 2 ▶ if (ftruncate(fd, (off_t)total) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (ftruncate(fd, (off_t)total) < 0) { 0 2 2
865 0 ▶ TK_ERR("ftruncate: %s", strerror(errno)); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
TK_ERR("ftruncate: %s", strerror(errno)); close(fd); return NULL; 0 0 0
866 }
867 2 ▶ if (tk_reserve(fd, total) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (tk_reserve(fd, total) < 0) { 0 2 2
868 0 ▶ TK_ERR("memfd: cannot reserve %llu bytes: %s", (unsigned long long)total, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
TK_ERR("memfd: cannot reserve %llu bytes: %s", (unsigned long long)total, strerror(errno)); 0 0 0
869 0 close(fd); return NULL;
870 }
871 2 (void)fcntl(fd, F_ADD_SEALS, F_SEAL_SHRINK | F_SEAL_GROW);
872 2 void *base = mmap(NULL, (size_t)total, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
873 2 ▶ if (base == MAP_FAILED) { TK_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { TK_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; } 0 2 2
if (base == MAP_FAILED) { TK_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; } 0 0 0
874 2 tk_init_header(base, (uint32_t)capacity, (uint32_t)key_size, tkmode, alpha, total);
875 2 return tk_setup(base, (size_t)total, NULL, fd);
876 }
877  
878 2 static TkHandle *tk_open_fd(int fd, char *errbuf) {
879 2 ▶ if (errbuf) errbuf[0] = '\0';
Branch: 1 branch
BranchTrueFalseTotal
if (errbuf) errbuf[0] = '\0'; 2 0 2
880 struct stat st;
881 2 ▶ if (fstat(fd, &st) < 0) { TK_ERR("fstat: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fstat(fd, &st) < 0) { TK_ERR("fstat: %s", strerror(errno)); return NULL; } 0 2 2
if (fstat(fd, &st) < 0) { TK_ERR("fstat: %s", strerror(errno)); return NULL; } 0 0 0
882 2 ▶ if ((uint64_t)st.st_size < sizeof(TkHeader)) { TK_ERR("too small"); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if ((uint64_t)st.st_size < sizeof(TkHeader)) { TK_ERR("too small"); return NULL; } 0 2 2
if ((uint64_t)st.st_size < sizeof(TkHeader)) { TK_ERR("too small"); return NULL; } 0 0 0
883 /* before mmap: a creator may truncate the file until it has set magic */
884 uint32_t magic;
885 2 ▶ if (pread(fd, &magic, sizeof magic, offsetof(TkHeader, magic)) != (ssize_t)sizeof magic || magic != TK_MAGIC) {
Branch: 2 branches
BranchTrueFalseTotal
if (pread(fd, &magic, sizeof magic, offsetof(TkHeader, magic)) != (ssize_t)sizeof magic || magic != TK_MAGIC) { 2 0 2
if (pread(fd, &magic, sizeof magic, offsetof(TkHeader, magic)) != (ssize_t)sizeof magic || magic != TK_MAGIC) { 0 2 2
886 0 ▶ TK_ERR("invalid top-k table"); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
TK_ERR("invalid top-k table"); return NULL; 0 0 0
887 }
888 2 size_t ms = (size_t)st.st_size;
889 2 void *base = mmap(NULL, ms, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
890 2 ▶ if (base == MAP_FAILED) { TK_ERR("mmap: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { TK_ERR("mmap: %s", strerror(errno)); return NULL; } 0 2 2
if (base == MAP_FAILED) { TK_ERR("mmap: %s", strerror(errno)); return NULL; } 0 0 0
891 2 ▶ if (!tk_validate_header((TkHeader *)base, (uint64_t)st.st_size)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!tk_validate_header((TkHeader *)base, (uint64_t)st.st_size)) { 0 2 2
892 0 ▶ TK_ERR("invalid top-k table"); munmap(base, ms); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
TK_ERR("invalid top-k table"); munmap(base, ms); return NULL; 0 0 0
893 }
894 2 int myfd = fcntl(fd, F_DUPFD_CLOEXEC, 0);
895 2 ▶ if (myfd < 0) { TK_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (myfd < 0) { TK_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; } 0 2 2
if (myfd < 0) { TK_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; } 0 0 0
896 2 return tk_setup(base, ms, NULL, myfd);
897 }
898  
899 43 static void tk_destroy(TkHandle *h) {
900 43 ▶ if (!h) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!h) return; 0 43 43
901 /* Release our reader slot on clean teardown (else short-lived-reader churn
902 * exhausts the slot table); skip if a read lock is still held (rdepth>0). */
903 43 ▶ 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 && 43 0 43
if (h->reader_slots && h->my_slot_idx != UINT32_MAX && h->cached_pid && 40 3 43
if (h->reader_slots && h->my_slot_idx != UINT32_MAX && h->cached_pid && 40 0 40
904 40 ▶ h->cached_fork_gen == __atomic_load_n(&tk_fork_gen, __ATOMIC_RELAXED) &&
Branch: 1 branch
BranchTrueFalseTotal
h->cached_fork_gen == __atomic_load_n(&tk_fork_gen, __ATOMIC_RELAXED) && 40 0 40
905 40 ▶ __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) { 40 0 40
906 /* Clear our occ bit BEFORE freeing the slot: we still own the pid so no
907 * claimant can take the slot mid-clear, and rdepth==0 so no writer needs
908 * to see us. (A crash skips this -> the bit is reclaimed lazily by a
909 * writer scan / re-claim, same as the pid.) */
910 40 ▶ if (h->occ) tk_occ_clear(h, h->my_slot_idx);
Branch: 1 branch
BranchTrueFalseTotal
if (h->occ) tk_occ_clear(h, h->my_slot_idx); 40 0 40
911 40 uint32_t expected = h->cached_pid;
912 40 __atomic_compare_exchange_n(&h->reader_slots[h->my_slot_idx].pid,
913 &expected, 0, 0, __ATOMIC_RELEASE, __ATOMIC_RELAXED);
914 }
915 43 ▶ if (h->backing_fd >= 0) close(h->backing_fd);
Branch: 1 branch
BranchTrueFalseTotal
if (h->backing_fd >= 0) close(h->backing_fd); 4 39 43
916 43 ▶ if (h->base) munmap(h->base, h->mmap_size);
Branch: 1 branch
BranchTrueFalseTotal
if (h->base) munmap(h->base, h->mmap_size); 43 0 43
917 43 free(h->path);
918 43 free(h);
919 }
920  
921 3 static inline int tk_msync(TkHandle *h) {
922 3 ▶ if (!h || !h->base) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (!h || !h->base) return 0; 3 0 3
if (!h || !h->base) return 0; 0 3 3
923 3 return msync(h->base, h->mmap_size, MS_SYNC);
924 }
925  
926 /* ================================================================
927 * Space-Saving operations (callers hold the lock)
928 *
929 * A fixed set of m counters monitors the heaviest keys. Observing a key that
930 * is already monitored bumps its count; observing a new key when a counter is
931 * free fills it; observing a new key when full evicts the minimum-count counter,
932 * inheriting its count as the new key's error bound. A min-heap (over counts)
933 * finds the eviction victim in O(log m); an intrusive hash index (chaining via
934 * slot->hnext) tests membership in O(1). Keys are compared by their first
935 * key_size bytes (longer keys are truncated on the way in).
936 * ================================================================ */
937  
938 48333 static inline uint64_t tk_hash(const void *key, size_t len) {
939 48333 return XXH3_64bits(key, len);
940 }
941  
942 /* ---- forward-decay helpers (decayed mode stores a double's bits in count/error) ---- */
943 60665 static inline double tk_w_get(uint64_t bits) { double d; memcpy(&d, &bits, sizeof d); return d; }
944 13253 static inline uint64_t tk_w_bits(double d) { uint64_t b; memcpy(&b, &d, sizeof b); return b; }
945 /* forward-decay factor g(now) = exp(alpha*(now - landmark)); >= 1, == 1 just after a rescale */
946 27866 static inline double tk_g(TkHandle *h) {
947 27866 return exp(h->alpha * (h->hdr->now - h->hdr->landmark));
948 }
949 /* mode-aware count comparisons for the min-heap */
950 32016 static inline int tk_count_lt(TkHandle *h, uint64_t a, uint64_t b) {
951 32016 ▶ if (h->mode == TK_MODE_DECAYED) return tk_w_get(a) < tk_w_get(b);
Branch: 1 branch
BranchTrueFalseTotal
if (h->mode == TK_MODE_DECAYED) return tk_w_get(a) < tk_w_get(b); 14320 17696 32016
952 17696 return a < b;
953 }
954 18305 static inline int tk_slot_lt(TkHandle *h, const TkSlot *a, const TkSlot *b) {
955 18305 return tk_count_lt(h, a->count, b->count);
956 }
957 116 static inline int tk_slot_le(TkHandle *h, const TkSlot *a, const TkSlot *b) {
958 116 ▶ if (h->mode == TK_MODE_DECAYED) return tk_w_get(a->count) <= tk_w_get(b->count);
Branch: 1 branch
BranchTrueFalseTotal
if (h->mode == TK_MODE_DECAYED) return tk_w_get(a->count) <= tk_w_get(b->count); 14 102 116
959 102 return a->count <= b->count;
960 }
961  
962 /* ---- min-heap over slot counts (heap[] holds slot indices) ---- */
963  
964 /* Journaled hole sifts: slot s, saved in hdr->jslot, belongs at the hole heap[pos], which may hold
965 * a stale duplicate; each step copies one entry into the hole and records the new hole in jsift.
966 * A writer killed mid-sift leaves jsift set, and lock recovery finishes the sift. */
967 #define TK_J_UP 0x40000000U
968 #define TK_J_DOWN 0x80000000U
969 #define TK_J_HOLE 0x3FFFFFFFU
970  
971 16635 static inline void tk_heap_put(TkHandle *h, uint32_t *heap, uint64_t i, uint32_t s) {
972 16635 heap[i] = s;
973 16635 ▶ if (TK_SLOT_OK(h, s)) tk_slot(h, s)->heap_pos = (uint32_t)i;
Branch: 1 branch
BranchTrueFalseTotal
if (TK_SLOT_OK(h, s)) tk_slot(h, s)->heap_pos = (uint32_t)i; 16635 0 16635
974 16635 }
975  
976 7435 static inline void tk_journal_begin(TkHandle *h, uint32_t s, uint32_t dir, uint64_t pos) {
977 7435 h->hdr->jslot = s;
978 7435 __atomic_signal_fence(__ATOMIC_SEQ_CST);
979 7435 h->hdr->jsift = dir | (uint32_t)pos;
980 7435 __atomic_signal_fence(__ATOMIC_SEQ_CST);
981 7435 }
982  
983 9200 static inline void tk_journal_step(TkHandle *h, uint32_t *heap, uint64_t pos, uint64_t next, uint32_t dir) {
984 9200 tk_heap_put(h, heap, pos, heap[next]);
985 9200 __atomic_signal_fence(__ATOMIC_SEQ_CST);
986 9200 h->hdr->jsift = dir | (uint32_t)next;
987 9200 __atomic_signal_fence(__ATOMIC_SEQ_CST);
988 9200 }
989  
990 7435 static inline void tk_journal_end(TkHandle *h, uint32_t *heap, uint64_t pos, uint32_t s) {
991 7435 tk_heap_put(h, heap, pos, s);
992 7435 __atomic_signal_fence(__ATOMIC_SEQ_CST);
993 7435 h->hdr->jsift = 0;
994 7435 }
995  
996 /* Whether a slot at heap[pos] whose count becomes c must sink: only then is a journal needed. */
997 22256 static inline int tk_must_sink(TkHandle *h, uint32_t *heap, uint64_t size, uint64_t pos, uint64_t c) {
998 28592 ▶ for (uint64_t i = 2 * pos + 1; i <= 2 * pos + 2 && i < size; i++)
Branch: 2 branches
BranchTrueFalseTotal
for (uint64_t i = 2 * pos + 1; i <= 2 * pos + 2 && i < size; i++) 26744 1848 28592
for (uint64_t i = 2 * pos + 1; i <= 2 * pos + 2 && i < size; i++) 13711 13033 26744
999 13711 ▶ if (TK_SLOT_OK(h, heap[i]) && tk_count_lt(h, tk_slot(h, heap[i])->count, c)) return 1;
Branch: 2 branches
BranchTrueFalseTotal
if (TK_SLOT_OK(h, heap[i]) && tk_count_lt(h, tk_slot(h, heap[i])->count, c)) return 1; 13711 0 13711
if (TK_SLOT_OK(h, heap[i]) && tk_count_lt(h, tk_slot(h, heap[i])->count, c)) return 1; 7375 6336 13711
1000 14881 return 0;
1001 }
1002  
1003 60 static void tk_sift_up(TkHandle *h, uint32_t *heap, uint64_t pos, uint32_t s) {
1004 60 ▶ if (TK_SLOT_OK(h, s)) { /* Layer B */
Branch: 1 branch
BranchTrueFalseTotal
if (TK_SLOT_OK(h, s)) { /* Layer B */ 60 0 60
1005 60 TkSlot *e = tk_slot(h, s);
1006 131 ▶ while (pos > 0) {
Branch: 1 branch
BranchTrueFalseTotal
while (pos > 0) { 116 15 131
1007 116 uint64_t parent = (pos - 1) / 2;
1008 116 uint32_t sp = heap[parent];
1009 116 ▶ if (!TK_SLOT_OK(h, sp) || tk_slot_le(h, tk_slot(h, sp), e)) break;
Branch: 2 branches
BranchTrueFalseTotal
if (!TK_SLOT_OK(h, sp) || tk_slot_le(h, tk_slot(h, sp), e)) break; 116 0 116
if (!TK_SLOT_OK(h, sp) || tk_slot_le(h, tk_slot(h, sp), e)) break; 71 45 116
1010 71 tk_journal_step(h, heap, pos, parent, TK_J_UP);
1011 71 pos = parent;
1012 }
1013 }
1014 60 tk_journal_end(h, heap, pos, s);
1015 60 }
1016  
1017 7375 static void tk_sift_down(TkHandle *h, uint32_t *heap, uint64_t size, uint64_t pos, uint32_t s) {
1018 7375 ▶ if (TK_SLOT_OK(h, s)) { /* Layer B */
Branch: 1 branch
BranchTrueFalseTotal
if (TK_SLOT_OK(h, s)) { /* Layer B */ 7375 0 7375
1019 7375 TkSlot *e = tk_slot(h, s);
1020 9129 for (;;) {
1021 16504 uint64_t c = 2 * pos + 1;
1022 16504 ▶ if (c >= size) break;
Branch: 1 branch
BranchTrueFalseTotal
if (c >= size) break; 6263 10241 16504
1023 10241 uint32_t sc = heap[c];
1024 10241 ▶ if (c + 1 < size) {
Branch: 1 branch
BranchTrueFalseTotal
if (c + 1 < size) { 7850 2391 10241
1025 7850 uint32_t sr = heap[c + 1];
1026 7850 ▶ if (TK_SLOT_OK(h, sr) &&
Branch: 1 branch
BranchTrueFalseTotal
if (TK_SLOT_OK(h, sr) && 7850 0 7850
1027 7850 ▶ (!TK_SLOT_OK(h, sc) || tk_slot_lt(h, tk_slot(h, sr), tk_slot(h, sc)))) { c++; sc = sr; }
Branch: 2 branches
BranchTrueFalseTotal
(!TK_SLOT_OK(h, sc) || tk_slot_lt(h, tk_slot(h, sr), tk_slot(h, sc)))) { c++; sc = sr; } 7850 0 7850
(!TK_SLOT_OK(h, sc) || tk_slot_lt(h, tk_slot(h, sr), tk_slot(h, sc)))) { c++; sc = sr; } 4118 3732 7850
1028 }
1029 10241 ▶ if (!TK_SLOT_OK(h, sc) || !tk_slot_lt(h, tk_slot(h, sc), e)) break;
Branch: 2 branches
BranchTrueFalseTotal
if (!TK_SLOT_OK(h, sc) || !tk_slot_lt(h, tk_slot(h, sc), e)) break; 10241 0 10241
if (!TK_SLOT_OK(h, sc) || !tk_slot_lt(h, tk_slot(h, sc), e)) break; 9129 1112 10241
1030 9129 tk_journal_step(h, heap, pos, c, TK_J_DOWN);
1031 9129 pos = c;
1032 }
1033 }
1034 7375 tk_journal_end(h, heap, pos, s);
1035 7375 }
1036  
1037 /* current heap size, clamped to the capacity (Layer B: hdr->used is peer-writable) */
1038 12645 static inline uint64_t tk_heap_size(TkHandle *h) {
1039 12645 uint64_t used = h->hdr->used;
1040 12645 return (used > h->capacity) ? h->capacity : used;
1041 }
1042  
1043 /* A warm-up insert killed before publishing its slot never happened; any other sift is finished. */
1044 0 static void tk_journal_replay(TkHandle *h) {
1045 0 TkHeader *hdr = h->hdr;
1046 0 uint32_t j = hdr->jsift;
1047 0 ▶ if (!j) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!j) return; 0 0 0
1048 0 uint32_t s = hdr->jslot;
1049 0 uint64_t pos = j & TK_J_HOLE, size = tk_heap_size(h);
1050 0 ▶ if (pos < size && TK_SLOT_OK(h, s)) {
Branch: 2 branches
BranchTrueFalseTotal
if (pos < size && TK_SLOT_OK(h, s)) { 0 0 0
if (pos < size && TK_SLOT_OK(h, s)) { 0 0 0
1051 0 uint32_t *heap = tk_heap(h);
1052 0 ▶ if ((j & ~TK_J_HOLE) == TK_J_UP) { tk_sift_up(h, heap, pos, s); return; }
Branch: 1 branch
BranchTrueFalseTotal
if ((j & ~TK_J_HOLE) == TK_J_UP) { tk_sift_up(h, heap, pos, s); return; } 0 0 0
1053 0 ▶ if ((j & ~TK_J_HOLE) == TK_J_DOWN) { tk_sift_down(h, heap, size, pos, s); return; }
Branch: 1 branch
BranchTrueFalseTotal
if ((j & ~TK_J_HOLE) == TK_J_DOWN) { tk_sift_down(h, heap, size, pos, s); return; } 0 0 0
1054 }
1055 0 hdr->jsift = 0;
1056 }
1057  
1058 /* ---- intrusive hash index (chaining via slot->hnext) ---- */
1059  
1060 /* find the slot monitoring `key` (klen already truncated), or TK_NIL */
1061 37648 static uint32_t tk_hash_find(TkHandle *h, const void *key, uint32_t klen, uint64_t hv) {
1062 37648 uint32_t *buckets = tk_buckets(h);
1063 37648 uint32_t s = buckets[hv & h->hash_mask];
1064 37648 uint64_t guard = 0;
1065 49791 ▶ while (s != TK_NIL && TK_SLOT_OK(h, s) && guard++ <= (uint64_t)h->capacity) {
Branch: 3 branches
BranchTrueFalseTotal
while (s != TK_NIL && TK_SLOT_OK(h, s) && guard++ <= (uint64_t)h->capacity) { 38840 10951 49791
while (s != TK_NIL && TK_SLOT_OK(h, s) && guard++ <= (uint64_t)h->capacity) { 38840 0 38840
while (s != TK_NIL && TK_SLOT_OK(h, s) && guard++ <= (uint64_t)h->capacity) { 38840 0 38840
1066 38840 TkSlot *sl = tk_slot(h, s);
1067 38840 ▶ uint32_t kl = sl->key_len; if (kl > h->key_size) kl = h->key_size; /* Layer B */
Branch: 1 branch
BranchTrueFalseTotal
uint32_t kl = sl->key_len; if (kl > h->key_size) kl = h->key_size; /* Layer B */ 0 38840 38840
1068 38840 ▶ if (kl == klen && memcmp(tk_slot_key(sl), key, klen) == 0) return s;
Branch: 2 branches
BranchTrueFalseTotal
if (kl == klen && memcmp(tk_slot_key(sl), key, klen) == 0) return s; 29748 9092 38840
if (kl == klen && memcmp(tk_slot_key(sl), key, klen) == 0) return s; 26697 3051 29748
1069 12143 s = sl->hnext;
1070 }
1071 10951 return TK_NIL;
1072 }
1073  
1074 /* prepend slot s (key already stored) to its hash chain */
1075 10944 static void tk_hash_insert(TkHandle *h, uint32_t s, uint64_t hv) {
1076 10944 uint32_t *buckets = tk_buckets(h);
1077 10944 uint64_t b = hv & h->hash_mask;
1078 10944 tk_slot(h, s)->hnext = buckets[b];
1079 10944 __atomic_signal_fence(__ATOMIC_SEQ_CST);
1080 10944 buckets[b] = s;
1081 10944 }
1082  
1083 /* unlink slot s from its hash chain (hv = hash of its stored key) */
1084 10685 static void tk_hash_remove(TkHandle *h, uint32_t s, uint64_t hv) {
1085 10685 uint32_t *buckets = tk_buckets(h);
1086 10685 uint64_t b = hv & h->hash_mask;
1087 10685 uint32_t cur = buckets[b];
1088 10685 ▶ if (cur == s) { buckets[b] = tk_slot(h, s)->hnext; return; }
Branch: 1 branch
BranchTrueFalseTotal
if (cur == s) { buckets[b] = tk_slot(h, s)->hnext; return; } 9317 1368 10685
1089 1368 uint64_t guard = 0;
1090 1514 ▶ while (cur != TK_NIL && TK_SLOT_OK(h, cur) && guard++ <= (uint64_t)h->capacity) {
Branch: 3 branches
BranchTrueFalseTotal
while (cur != TK_NIL && TK_SLOT_OK(h, cur) && guard++ <= (uint64_t)h->capacity) { 1514 0 1514
while (cur != TK_NIL && TK_SLOT_OK(h, cur) && guard++ <= (uint64_t)h->capacity) { 1514 0 1514
while (cur != TK_NIL && TK_SLOT_OK(h, cur) && guard++ <= (uint64_t)h->capacity) { 1514 0 1514
1091 1514 TkSlot *c = tk_slot(h, cur);
1092 1514 ▶ if (c->hnext == s) { c->hnext = tk_slot(h, s)->hnext; return; }
Branch: 1 branch
BranchTrueFalseTotal
if (c->hnext == s) { c->hnext = tk_slot(h, s)->hnext; return; } 1368 146 1514
1093 146 cur = c->hnext;
1094 }
1095 }
1096  
1097 /* store (truncated) key bytes into slot s; returns the stored length */
1098 10944 static inline uint32_t tk_store_key(TkHandle *h, uint32_t s, const void *key, size_t len) {
1099 10944 ▶ uint32_t klen = (len > h->key_size) ? h->key_size : (uint32_t)len;
Branch: 1 branch
BranchTrueFalseTotal
uint32_t klen = (len > h->key_size) ? h->key_size : (uint32_t)len; 6483 4461 10944
1100 10944 TkSlot *sl = tk_slot(h, s);
1101 10944 memcpy(tk_slot_key(sl), key, klen);
1102 10944 sl->key_len = klen;
1103 10944 return klen;
1104 }
1105  
1106 #define TK_RS_PEND (1ULL << 63)
1107  
1108 /* Rescale the slots from hdr->rs_next on by hdr->rs_inv, then advance the landmark.
1109 * Each slot's new values go to the header first, so a rescale killed part-way is
1110 * resumed without scaling any slot twice. */
1111 227 static void tk_rescale_run(TkHandle *h) {
1112 227 TkHeader *hdr = h->hdr;
1113 227 uint64_t used = tk_heap_size(h);
1114 227 uint64_t smax = tk_slots_max(h);
1115 227 ▶ if (used > smax) used = smax; /* Layer B */
Branch: 1 branch
BranchTrueFalseTotal
if (used > smax) used = smax; /* Layer B */ 0 227 227
1116 227 uint64_t i = hdr->rs_next;
1117 227 ▶ if (i & TK_RS_PEND) {
Branch: 1 branch
BranchTrueFalseTotal
if (i & TK_RS_PEND) { 0 227 227
1118 0 i &= ~TK_RS_PEND;
1119 0 ▶ if (i < used) { tk_slot(h, i)->count = hdr->rs_count; tk_slot(h, i)->error = hdr->rs_error; }
Branch: 1 branch
BranchTrueFalseTotal
if (i < used) { tk_slot(h, i)->count = hdr->rs_count; tk_slot(h, i)->error = hdr->rs_error; } 0 0 0
1120 0 __atomic_signal_fence(__ATOMIC_SEQ_CST);
1121 0 hdr->rs_next = ++i;
1122 }
1123 227 double inv = hdr->rs_inv;
1124 1051 ▶ for (; i < used; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (; i < used; i++) { 824 227 1051
1125 824 TkSlot *sl = tk_slot(h, i);
1126 824 hdr->rs_count = tk_w_bits(tk_w_get(sl->count) * inv);
1127 824 hdr->rs_error = tk_w_bits(tk_w_get(sl->error) * inv);
1128 824 __atomic_signal_fence(__ATOMIC_SEQ_CST);
1129 824 hdr->rs_next = i | TK_RS_PEND;
1130 824 __atomic_signal_fence(__ATOMIC_SEQ_CST);
1131 824 sl->count = hdr->rs_count;
1132 824 sl->error = hdr->rs_error;
1133 824 __atomic_signal_fence(__ATOMIC_SEQ_CST);
1134 824 hdr->rs_next = i + 1;
1135 }
1136 227 __atomic_signal_fence(__ATOMIC_SEQ_CST);
1137 227 hdr->landmark = hdr->now; /* g(now) == 1 again */
1138 227 __atomic_signal_fence(__ATOMIC_SEQ_CST);
1139 227 hdr->rs_on = 0;
1140 227 }
1141  
1142 /* Rescale all weights by 1/g and advance the landmark to now, keeping the
1143 * forward-decay weights bounded (decayed mode; caller holds the write lock). */
1144 227 static void tk_rescale(TkHandle *h) {
1145 227 double g = tk_g(h);
1146 227 ▶ if (!(g > 1.0)) { h->hdr->landmark = h->hdr->now; return; } /* g <= 1 or NaN: nothing to rescale */
Branch: 1 branch
BranchTrueFalseTotal
if (!(g > 1.0)) { h->hdr->landmark = h->hdr->now; return; } /* g <= 1 or NaN: nothing to rescale */ 0 227 227
1147 227 ▶ h->hdr->rs_inv = isfinite(g) ? 1.0 / g : 0.0; /* g == +Inf: a huge time gap fully decayed all old weight -> 0 */
Branch: 1 branch
BranchTrueFalseTotal
h->hdr->rs_inv = isfinite(g) ? 1.0 / g : 0.0; /* g == +Inf: a huge time gap fully decayed all old weight -> 0 */ 11 216 227
1148 227 h->hdr->rs_next = 0;
1149 227 __atomic_signal_fence(__ATOMIC_SEQ_CST);
1150 227 h->hdr->rs_on = 1;
1151 227 __atomic_signal_fence(__ATOMIC_SEQ_CST);
1152 227 tk_rescale_run(h);
1153 }
1154  
1155 /* Observe one item; returns the item's estimated count after this observation.
1156 * (caller holds the write lock) */
1157 22515 static uint64_t tk_observe_locked(TkHandle *h, const void *item, size_t len, int has_ts, double ts) {
1158 22515 ▶ if (h->capacity == 0) return 0; /* Layer B: unusable mapping */
Branch: 1 branch
BranchTrueFalseTotal
if (h->capacity == 0) return 0; /* Layer B: unusable mapping */ 0 22515 22515
1159 22515 ▶ uint32_t klen = (len > h->key_size) ? h->key_size : (uint32_t)len;
Branch: 1 branch
BranchTrueFalseTotal
uint32_t klen = (len > h->key_size) ? h->key_size : (uint32_t)len; 9030 13485 22515
1160 22515 uint64_t hv = tk_hash(item, klen);
1161 22515 h->hdr->seen++;
1162  
1163 22515 double g = 1.0; /* increment weight (1 in plain mode) */
1164 22515 ▶ if (h->mode == TK_MODE_DECAYED) {
Branch: 1 branch
BranchTrueFalseTotal
if (h->mode == TK_MODE_DECAYED) { 11506 11009 22515
1165 /* advance the monotonic clock: to ts if given and larger, else one tick */
1166 11506 ▶ if (has_ts) { if (ts > h->hdr->now) h->hdr->now = ts; }
Branch: 2 branches
BranchTrueFalseTotal
if (has_ts) { if (ts > h->hdr->now) h->hdr->now = ts; } 6802 4704 11506
if (has_ts) { if (ts > h->hdr->now) h->hdr->now = ts; } 5973 829 6802
1167 4704 else h->hdr->now += 1.0;
1168 11506 ▶ if (h->alpha * (h->hdr->now - h->hdr->landmark) > TK_RESCALE_LN)
Branch: 1 branch
BranchTrueFalseTotal
if (h->alpha * (h->hdr->now - h->hdr->landmark) > TK_RESCALE_LN) 227 11279 11506
1169 227 tk_rescale(h); /* advance the landmark to keep g bounded */
1170 11506 g = tk_g(h);
1171 }
1172  
1173 22515 uint32_t s = tk_hash_find(h, item, klen, hv);
1174 22515 uint32_t *heap = tk_heap(h);
1175 22515 ▶ if (s != TK_NIL) { /* already monitored: bump */
Branch: 1 branch
BranchTrueFalseTotal
if (s != TK_NIL) { /* already monitored: bump */ 11571 10944 22515
1176 11571 TkSlot *sl = tk_slot(h, s);
1177 11571 ▶ uint64_t nc = (h->mode == TK_MODE_DECAYED) ? tk_w_bits(tk_w_get(sl->count) + g) : sl->count + 1;
Branch: 1 branch
BranchTrueFalseTotal
uint64_t nc = (h->mode == TK_MODE_DECAYED) ? tk_w_bits(tk_w_get(sl->count) + g) : sl->count + 1; 7013 4558 11571
1178 11571 uint64_t size = tk_heap_size(h);
1179 11571 uint64_t pos = sl->heap_pos;
1180 11571 ▶ int sink = pos < size && tk_must_sink(h, heap, size, pos, nc);
Branch: 2 branches
BranchTrueFalseTotal
int sink = pos < size && tk_must_sink(h, heap, size, pos, nc); 11571 0 11571
int sink = pos < size && tk_must_sink(h, heap, size, pos, nc); 1421 10150 11571
1181 11571 ▶ uint32_t at = sink ? heap[pos] : TK_NIL;
Branch: 1 branch
BranchTrueFalseTotal
uint32_t at = sink ? heap[pos] : TK_NIL; 1421 10150 11571
1182 11571 ▶ if (sink) tk_journal_begin(h, at, TK_J_DOWN, pos);
Branch: 1 branch
BranchTrueFalseTotal
if (sink) tk_journal_begin(h, at, TK_J_DOWN, pos); 1421 10150 11571
1183 11571 sl->count = nc;
1184 11571 ▶ if (sink) tk_sift_down(h, heap, size, pos, at); /* count rose -> sink it */
Branch: 1 branch
BranchTrueFalseTotal
if (sink) tk_sift_down(h, heap, size, pos, at); /* count rose -> sink it */ 1421 10150 11571
1185 11571 return sl->count;
1186 }
1187  
1188 10944 uint64_t used_now = h->hdr->used; /* Layer B: read the peer-writable count ONCE */
1189 10944 ▶ if (used_now < h->capacity) { /* warm-up: fill a fresh slot */
Branch: 1 branch
BranchTrueFalseTotal
if (used_now < h->capacity) { /* warm-up: fill a fresh slot */ 259 10685 10944
1190 259 uint32_t ns = (uint32_t)used_now; /* index by the same value the guard validated */
1191 259 TkSlot *sl = tk_slot(h, ns);
1192 259 tk_store_key(h, ns, item, len);
1193 259 ▶ sl->count = (h->mode == TK_MODE_DECAYED) ? tk_w_bits(g) : 1;
Branch: 1 branch
BranchTrueFalseTotal
sl->count = (h->mode == TK_MODE_DECAYED) ? tk_w_bits(g) : 1; 99 160 259
1194 259 ▶ sl->error = (h->mode == TK_MODE_DECAYED) ? tk_w_bits(0.0) : 0;
Branch: 1 branch
BranchTrueFalseTotal
sl->error = (h->mode == TK_MODE_DECAYED) ? tk_w_bits(0.0) : 0; 99 160 259
1195 259 sl->hnext = TK_NIL;
1196 259 sl->heap_pos = ns;
1197 259 heap[ns] = ns;
1198 259 ▶ uint32_t sp = ns ? heap[(ns - 1) / 2] : TK_NIL;
Branch: 1 branch
BranchTrueFalseTotal
uint32_t sp = ns ? heap[(ns - 1) / 2] : TK_NIL; 214 45 259
1199 259 ▶ int rise = TK_SLOT_OK(h, sp) && tk_slot_lt(h, sl, tk_slot(h, sp));
Branch: 2 branches
BranchTrueFalseTotal
int rise = TK_SLOT_OK(h, sp) && tk_slot_lt(h, sl, tk_slot(h, sp)); 214 45 259
int rise = TK_SLOT_OK(h, sp) && tk_slot_lt(h, sl, tk_slot(h, sp)); 60 154 214
1200 259 ▶ if (rise) tk_journal_begin(h, ns, TK_J_UP, ns);
Branch: 1 branch
BranchTrueFalseTotal
if (rise) tk_journal_begin(h, ns, TK_J_UP, ns); 60 199 259
1201 /* Claim the slot before indexing it: a writer killed in between leaves an unindexed slot
1202 * that eviction reclaims, not one the next key reuses while it is still chained. */
1203 259 __atomic_signal_fence(__ATOMIC_SEQ_CST);
1204 259 h->hdr->used++;
1205 259 __atomic_signal_fence(__ATOMIC_SEQ_CST);
1206 259 tk_hash_insert(h, ns, hv);
1207 259 ▶ if (rise) tk_sift_up(h, heap, ns, ns);
Branch: 1 branch
BranchTrueFalseTotal
if (rise) tk_sift_up(h, heap, ns, ns); 60 199 259
1208 259 return sl->count;
1209 }
1210  
1211 /* full: evict the minimum-count slot (heap root) */
1212 10685 uint32_t victim = heap[0];
1213 10685 ▶ if (!TK_SLOT_OK(h, victim)) return 0; /* Layer B: corrupt heap root */
Branch: 1 branch
BranchTrueFalseTotal
if (!TK_SLOT_OK(h, victim)) return 0; /* Layer B: corrupt heap root */ 0 10685 10685
1214 10685 TkSlot *sl = tk_slot(h, victim);
1215 10685 ▶ uint32_t old_kl = sl->key_len; if (old_kl > h->key_size) old_kl = h->key_size;
Branch: 1 branch
BranchTrueFalseTotal
uint32_t old_kl = sl->key_len; if (old_kl > h->key_size) old_kl = h->key_size; 0 10685 10685
1216 10685 uint64_t old_hv = tk_hash(tk_slot_key(sl), old_kl);
1217 10685 tk_hash_remove(h, victim, old_hv); /* drop the evicted key */
1218 10685 uint64_t min_count = sl->count, nc; /* victim's count: the heap minimum */
1219 /* The bound before the key: a kill between them leaves count - error <= 0, not a claim. */
1220 10685 sl->error = min_count; /* over-estimate bound */
1221 10685 __atomic_signal_fence(__ATOMIC_SEQ_CST);
1222 10685 tk_store_key(h, victim, item, len);
1223 10685 ▶ if (h->mode == TK_MODE_DECAYED) nc = tk_w_bits(tk_w_get(min_count) + g);
Branch: 1 branch
BranchTrueFalseTotal
if (h->mode == TK_MODE_DECAYED) nc = tk_w_bits(tk_w_get(min_count) + g); 4394 6291 10685
1224 6291 else nc = min_count + 1;
1225 10685 int sink = tk_must_sink(h, heap, h->capacity, 0, nc);
1226 10685 ▶ if (sink) tk_journal_begin(h, victim, TK_J_DOWN, 0);
Branch: 1 branch
BranchTrueFalseTotal
if (sink) tk_journal_begin(h, victim, TK_J_DOWN, 0); 5954 4731 10685
1227 10685 sl->count = nc;
1228 10685 tk_hash_insert(h, victim, hv);
1229 10685 ▶ if (sink) tk_sift_down(h, heap, h->capacity, 0, victim); /* root's count rose -> sink it */
Branch: 1 branch
BranchTrueFalseTotal
if (sink) tk_sift_down(h, heap, h->capacity, 0, victim); /* root's count rose -> sink it */ 5954 4731 10685
1230 10685 return sl->count;
1231 }
1232  
1233 /* estimated count of `item` (0 if not monitored); *err_out gets the over-estimate
1234 * bound if non-NULL. (caller holds a lock) */
1235 15133 static uint64_t tk_estimate_locked(TkHandle *h, const void *item, size_t len, uint64_t *err_out) {
1236 15133 ▶ uint32_t klen = (len > h->key_size) ? h->key_size : (uint32_t)len;
Branch: 1 branch
BranchTrueFalseTotal
uint32_t klen = (len > h->key_size) ? h->key_size : (uint32_t)len; 3823 11310 15133
1237 15133 uint64_t hv = tk_hash(item, klen);
1238 15133 uint32_t s = tk_hash_find(h, item, klen, hv);
1239 15133 ▶ if (s == TK_NIL) { if (err_out) *err_out = 0; return 0; }
Branch: 2 branches
BranchTrueFalseTotal
if (s == TK_NIL) { if (err_out) *err_out = 0; return 0; } 7 15126 15133
if (s == TK_NIL) { if (err_out) *err_out = 0; return 0; } 2 5 7
1240 15126 TkSlot *sl = tk_slot(h, s);
1241 15126 ▶ if (err_out) *err_out = sl->error;
Branch: 1 branch
BranchTrueFalseTotal
if (err_out) *err_out = sl->error; 3002 12124 15126
1242 15126 return sl->count;
1243 }
1244  
1245 #define TK_J_CLEAR (TK_J_UP | TK_J_DOWN) /* jsift: a clear in flight */
1246  
1247 /* reset to an empty table (caller holds the write lock) */
1248 13 static inline void tk_clear_locked(TkHandle *h) {
1249 13 uint64_t nb = h->hash_mask + 1;
1250 13 h->hdr->jsift = TK_J_CLEAR;
1251 13 __atomic_signal_fence(__ATOMIC_SEQ_CST);
1252 13 memset(tk_buckets(h), 0xFF, (size_t)(nb * sizeof(uint32_t))); /* all buckets -> TK_NIL */
1253 /* Unindex before emptying: a writer killed in between leaves slots no key reaches, not
1254 * chains into slots the next keys refill. */
1255 13 __atomic_signal_fence(__ATOMIC_SEQ_CST);
1256 13 h->hdr->used = 0;
1257 13 h->hdr->seen = 0;
1258 13 h->hdr->now = 0.0;
1259 13 h->hdr->landmark = 0.0;
1260 13 __atomic_signal_fence(__ATOMIC_SEQ_CST);
1261 13 h->hdr->jsift = 0;
1262 13 }
1263  
1264 /* Rebuild the hash index from the slots in use: an add killed between claiming or
1265 * rewriting a slot and chaining it leaves a slot no key reaches. */
1266 0 static void tk_reindex(TkHandle *h) {
1267 0 uint64_t used = tk_heap_size(h), smax = tk_slots_max(h);
1268 0 ▶ if (used > smax) used = smax; /* Layer B */
Branch: 1 branch
BranchTrueFalseTotal
if (used > smax) used = smax; /* Layer B */ 0 0 0
1269 0 memset(tk_buckets(h), 0xFF, (size_t)((h->hash_mask + 1) * sizeof(uint32_t)));
1270 0 ▶ for (uint64_t s = 0; s < used; s++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint64_t s = 0; s < used; s++) { 0 0 0
1271 0 TkSlot *sl = tk_slot(h, s);
1272 0 ▶ uint32_t kl = sl->key_len; if (kl > h->key_size) kl = h->key_size;
Branch: 1 branch
BranchTrueFalseTotal
uint32_t kl = sl->key_len; if (kl > h->key_size) kl = h->key_size; 0 0 0
1273 0 uint64_t hv = tk_hash(tk_slot_key(sl), kl);
1274 /* A key torn by a killed eviction can repeat another. The torn counter has
1275 * error == count, a real one counts above its error: index the real one,
1276 * else the larger count, else the one below the heap root, where the torn
1277 * one was evicted (decayed weights all 0 tie with it). */
1278 0 uint32_t t = tk_hash_find(h, tk_slot_key(sl), kl, hv);
1279 0 ▶ if (t != TK_NIL) {
Branch: 1 branch
BranchTrueFalseTotal
if (t != TK_NIL) { 0 0 0
1280 0 TkSlot *ts = tk_slot(h, t);
1281 0 int s_torn = !tk_count_lt(h, sl->error, sl->count);
1282 0 int t_torn = !tk_count_lt(h, ts->error, ts->count);
1283 0 int keep_t = s_torn != t_torn ? s_torn
1284 0 ▶ : tk_count_lt(h, sl->count, ts->count) ? 1
Branch: 1 branch
BranchTrueFalseTotal
: tk_count_lt(h, sl->count, ts->count) ? 1 0 0 0
1285 0 ▶ : tk_count_lt(h, ts->count, sl->count) ? 0
Branch: 2 branches
BranchTrueFalseTotal
: tk_count_lt(h, ts->count, sl->count) ? 0 0 0 0
: tk_count_lt(h, ts->count, sl->count) ? 0 0 0 0
1286 0 ▶ : ts->heap_pos >= sl->heap_pos;
Branch: 1 branch
BranchTrueFalseTotal
: ts->heap_pos >= sl->heap_pos; 0 0 0
1287 0 ▶ if (keep_t) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (keep_t) continue; 0 0 0
1288 0 tk_hash_remove(h, t, hv);
1289 }
1290 0 tk_hash_insert(h, (uint32_t)s, hv);
1291 }
1292 0 }
1293  
1294 /* Finish what a dead writer left part-way -- a clear, a rescale or a sift, each from
1295 * its header record -- then re-derive the hash index. Idempotent. */
1296 0 static void tk_repair_locked(TkHandle *h) {
1297 0 ▶ if (h->hdr->jsift == TK_J_CLEAR) { tk_clear_locked(h); return; }
Branch: 1 branch
BranchTrueFalseTotal
if (h->hdr->jsift == TK_J_CLEAR) { tk_clear_locked(h); return; } 0 0 0
1298 0 ▶ if (h->hdr->rs_on) tk_rescale_run(h);
Branch: 1 branch
BranchTrueFalseTotal
if (h->hdr->rs_on) tk_rescale_run(h); 0 0 0
1299 0 tk_journal_replay(h);
1300 0 tk_reindex(h);
1301 }
1302  
1303 #endif /* TK_H */
« xxhash.h ↑ Summary Shared.xs »