hiertimingwheel.h

filter: Statementstmt 70.4% 402 / 571 Branchbran 47.4% 227 / 478 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 59.9% 629 / 1049 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« blib/lib/Data/HierTimingWheel/Shared.pm ↑ Summary Shared.xs »
1 /*
2 * hiertimingwheel.h -- Shared-memory hierarchical timing wheel for Linux
3 *
4 * O(1) timer scheduling at any delay: a hierarchical (Varghese-Lauck) timing
5 * wheel of num_levels cascading wheels, each with num_slots (=S) buckets. A
6 * level-k slot spans S^k ticks, so the structure schedules any delay in
7 * [1, S^num_levels). Scheduling and cancelling a timer are O(1); a far-future
8 * timer waits in a coarse level and cascades down to finer levels as its time
9 * approaches, so it is touched only once per coarse tick (versus a single-level
10 * wheel that revisits it every rotation). The wheels live in a shared mapping so
11 * several processes schedule into and advance one clock; a write-preferring futex
12 * rwlock with reader-slot dead-process recovery guards mutation. Each timer
13 * carries an arbitrary 64-bit payload returned when it fires.
14 *
15 * Layout: Header -> reader_slots[1024] -> occ bitmap -> buckets[num_levels*num_slots] -> timers[capacity]
16 */
17  
18 #ifndef HW_H
19 #define HW_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 #if defined(__BYTE_ORDER__) && __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
41 #error "hiertimingwheel.h: requires little-endian architecture"
42 #endif
43  
44  
45 /* ================================================================
46 * Constants
47 * ================================================================ */
48  
49 #define HW_MAGIC 0x4C575448 /* HierTimingWheel */
50 #define HW_VERSION 2 /* 2: added the occupancy bitmap region (layout change) */
51 #define HW_ERR_BUFLEN (PATH_MAX + 256)
52 #ifndef HW_READER_SLOTS
53 #define HW_READER_SLOTS 1024 /* max concurrent reader processes for dead-process recovery */
54 #endif
55 /* Occupancy bitmap: one bit per reader slot, set when a process claims a slot and
56 * cleared on clean release. A writer scans these HW_OCC_WORDS words to visit
57 * only OCCUPIED slots (O(words + live readers)) instead of all HW_READER_SLOTS. */
58 #define HW_OCC_WORDS (((HW_READER_SLOTS) + 63) / 64) /* 16 for 1024 slots */
59 #define HW_OCC_BYTES ((uint64_t)HW_OCC_WORDS * 8) /* 128 bytes */
60 #define HW_MIN_SLOTS 2
61 #define HW_MAX_SLOTS 0x10000U /* 2^16 slots per level */
62 #define HW_MIN_LEVELS 1
63 #define HW_MAX_LEVELS 16 /* number of cascading wheels */
64 #define HW_MIN_CAP 1
65 #define HW_MAX_CAP 0x1000000U /* 2^24 concurrent timers (index fits uint32, < HW_NIL) */
66 #define HW_NIL 0xFFFFFFFFU /* empty list link / free-list terminator */
67 #define HW_OP_CLEAR 1u /* hdr->op: a clear is in progress */
68  
69 #define HW_ERR(fmt, ...) do { if (errbuf) snprintf(errbuf, HW_ERR_BUFLEN, fmt, ##__VA_ARGS__); } while (0)
70  
71 /* ================================================================
72 * Structs
73 * ================================================================ */
74  
75 /* Per-process slot for dead-process recovery. In the reader-slots-only rwlock a
76 * reader's ENTIRE contribution to the shared lock is `rdepth` in its OWN slot --
77 * there is no separate shared reader counter to fall out of sync with it -- so a
78 * dead reader's contribution is exactly this one word, which a draining writer
79 * neutralises by clearing the slot's pid (the scan then ignores the slot). No
80 * orphaned counter can exist, so there is no quiescent force-reset and sustained
81 * readers cannot starve a writer. _rsv1/_rsv2 are kept only to preserve the
82 * 16-byte slot size across the already-released builds. */
83 typedef struct {
84 uint32_t pid; /* 0 = unclaimed */
85 uint32_t rdepth; /* read-locks THIS process currently holds (recursion-safe) */
86 uint32_t _rsv1; /* reserved (was waiters_parked); unused, kept for layout size */
87 uint32_t _rsv2; /* reserved (was writers_parked); unused, kept for layout size */
88 } HwReaderSlot;
89  
90 struct HwHeader {
91 uint32_t magic, version; /* 0,4 */
92 uint32_t num_slots; /* 8 slots per level (S) */
93 uint32_t num_levels; /* 12 number of cascading wheels (L) */
94 uint32_t capacity; /* 16 max concurrent timers */
95 uint32_t free_head; /* 20 free-list head (timer index) or HW_NIL */
96 uint64_t now; /* 24 absolute tick counter */
97 uint64_t count; /* 32 active timers */
98 uint64_t slots_off; /* 40 offset of the bucket heads (num_levels*num_slots uint32) */
99 uint64_t timers_off; /* 48 offset of the timer pool */
100 uint64_t total_size; /* 56 */
101 uint64_t reader_slots_off; /* 64 */
102 uint32_t wlock; /* 72 WRITER word ONLY: 0 (free) or WRITER_BIT|pid. NOT a reader count. */
103 uint32_t rwait; /* 76 parked-waiter hint (readers+writers blocked on wlock); over-count-safe */
104 uint32_t drain_seq; /* 80 futex bumped by a reader releasing under a draining writer (wakes it) */
105 uint32_t slotless_rdepth; /* readers holding with no reader-slot (documented residual) */
106 uint64_t stat_ops; /* 88 */
107 uint32_t op; /* 96 HW_OP_* in progress, 0 = none (carved from the pad) */
108 uint8_t _pad[156]; /* 100..255 */
109 };
110 typedef struct HwHeader HwHeader;
111  
112 _Static_assert(sizeof(HwHeader) == 256, "HwHeader must be 256 bytes");
113  
114 /* One timer: a payload plus its absolute expiry tick, linked into its current
115 * bucket by a doubly-linked list (prev/next) for O(1) cancellation. `bucket` is
116 * the flat bucket index (level*num_slots + slot) it currently sits in. state is
117 * 0 when the timer is on the free list, 1 when active. */
118 typedef struct {
119 uint64_t payload;
120 uint64_t expiry;
121 uint32_t prev;
122 uint32_t next;
123 uint32_t bucket;
124 uint32_t state;
125 } HwTimer;
126 _Static_assert(sizeof(HwTimer) == 32, "HwTimer must be 32 bytes");
127  
128 /* ---- Process-local handle ---- */
129  
130 typedef struct HwHandle {
131 HwHeader *hdr;
132 HwReaderSlot *reader_slots; /* HW_READER_SLOTS entries */
133 uint64_t *occ; /* HW_OCC_WORDS-word slot-occupancy bitmap (trusted layout offset) */
134 void *base; /* mmap base */
135 uint64_t slots_off; /* validated offsets, cached: never re-read from the peer-writable header */
136 uint64_t timers_off;
137 uint32_t num_slots; /* cached (S) */
138 uint32_t num_levels; /* cached (L) */
139 uint64_t tick[HW_MAX_LEVELS + 1]; /* tick[k] = S^k ticks per level-k slot; tick[L] = max delay + 1 */
140 uint32_t capacity; /* cached */
141 size_t mmap_size;
142 char *path; /* backing file path (strdup'd) */
143 int backing_fd; /* memfd or reopened-fd to close on destroy, -1 for file/anon */
144 uint32_t my_slot_idx; /* UINT32_MAX if all slots taken (no recovery for this handle) */
145 uint32_t cached_pid; /* getpid() cached at last slot claim */
146 uint32_t cached_fork_gen; /* hw_fork_gen value at last slot claim */
147 uint32_t slotless_held; /* read-locks this process holds with no reader-slot */
148 } HwHandle;
149  
150 /* ================================================================
151 * Futex-based write-preferring read-write lock (reader-slots-only)
152 * with dead-process recovery
153 *
154 * The reader count is NOT stored in a shared counter. It is DISTRIBUTED across
155 * per-process reader slots: each slot's `rdepth` is that process's entire
156 * contribution to the lock. A reader publishes its presence in its own slot and
157 * then re-checks the writer word; a writer publishes the writer word and then
158 * scans every slot until all live readers' rdepth reach 0. Sequentially-
159 * consistent store+load on each side (a Dekker handshake) gives mutual exclusion.
160 *
161 * Because a reader's whole contribution is ONE atomic word owned by ONE process,
162 * a crashed reader is recovered by clearing that one slot (CAS its pid to 0) --
163 * there is no second counter to strand, no orphaned +1, and therefore no
164 * quiescent force-reset. A reader killed anywhere in rdlock/rdunlock leaves at
165 * most `rdepth>0` in its dead slot, which the draining writer clears directly, so
166 * sustained read traffic can never starve a writer. Write-preference is inherent
167 * in the gate (new readers see wlock!=0 and yield), so there is no reader-count
168 * yield hack.
169 * ================================================================ */
170  
171 #define HW_RWLOCK_SPIN_LIMIT 32
172 #define HW_LOCK_TIMEOUT_SEC 2 /* FUTEX_WAIT timeout for stale lock detection */
173  
174 0 static inline void hw_rwlock_spin_pause(void) {
175 #if defined(__x86_64__) || defined(__i386__)
176 0 __asm__ volatile("pause" ::: "memory");
177 #elif defined(__aarch64__)
178 __asm__ volatile("yield" ::: "memory");
179 #else
180 __asm__ volatile("" ::: "memory");
181 #endif
182 0 }
183  
184 /* Writer word encoding: WRITER_BIT|pid when write-locked, 0 when free. */
185 #define HW_RWLOCK_WRITER_BIT 0x80000000U
186 #define HW_RWLOCK_PID_MASK 0x7FFFFFFFU
187 #define HW_RWLOCK_WR(pid) (HW_RWLOCK_WRITER_BIT | ((uint32_t)(pid) & HW_RWLOCK_PID_MASK))
188  
189 /* A zombie (dead but not yet reaped) still answers kill(pid,0) as alive, so a
190 * process that crashed while holding the lock and lingers unreaped would never
191 * be recovered. Treat /proc/<pid>/stat state 'Z' as dead. Linux-only (as is
192 * this module); if /proc is unreadable we fall back to "alive" (safe: we never
193 * force-recover a possibly-live holder). */
194 0 static inline int hw_pid_is_zombie(uint32_t pid) {
195 char path[32], buf[256];
196 0 snprintf(path, sizeof(path), "/proc/%u/stat", (unsigned)pid);
197 0 int fd = open(path, O_RDONLY | O_CLOEXEC);
198 0 ▶ if (fd < 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (fd < 0) return 0; 0 0 0
199 0 ssize_t n = read(fd, buf, sizeof(buf) - 1);
200 0 close(fd);
201 0 ▶ if (n <= 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (n <= 0) return 0; 0 0 0
202 0 buf[n] = '\0';
203 /* "pid (comm) state ..."; comm may contain ')', so scan to the last one. */
204 0 char *rp = strrchr(buf, ')');
205 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
206 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
207 }
208 /* 1 if alive or unknown, 0 if definitely dead. Cannot detect PID reuse: a
209 * recycled PID reports "alive" and the slot is not reclaimed until that
210 * process exits. See "Crash Safety" in the POD. */
211 0 static inline int hw_pid_alive(uint32_t pid) {
212 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
213 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
214 0 return !hw_pid_is_zombie(pid); /* kill() also succeeds for a zombie -> treat as dead */
215 }
216  
217 static const struct timespec hw_lock_timeout = { HW_LOCK_TIMEOUT_SEC, 0 };
218  
219 /* Process-global fork-generation counter. Incremented in the pthread_atfork
220 * child callback so every open handle detects a fork transition on the next
221 * lock call without paying a getpid() syscall on the hot path. */
222 static uint32_t hw_fork_gen = 1;
223 static pthread_once_t hw_atfork_once = PTHREAD_ONCE_INIT;
224 0 static void hw_on_fork_child(void) {
225 0 __atomic_add_fetch(&hw_fork_gen, 1, __ATOMIC_RELAXED);
226 0 }
227 3 static void hw_atfork_init(void) {
228 3 pthread_atfork(NULL, NULL, hw_on_fork_child);
229 3 }
230  
231 /* Occupancy bitmap: set a slot's bit when it is claimed, clear it on clean
232 * release. SEQ_CST so a set bit is ordered before the slot's rdepth can go
233 * non-zero (bit set in claim, which precedes any rdlock), letting a writer's
234 * SEQ_CST bitmap scan never miss a slot a committed reader holds. */
235 56 static inline void hw_occ_set(HwHandle *h, uint32_t s) {
236 56 __atomic_fetch_or(&h->occ[s >> 6], (uint64_t)1 << (s & 63), __ATOMIC_SEQ_CST);
237 56 }
238 56 static inline void hw_occ_clear(HwHandle *h, uint32_t s) {
239 56 __atomic_fetch_and(&h->occ[s >> 6], ~((uint64_t)1 << (s & 63)), __ATOMIC_SEQ_CST);
240 56 }
241  
242 /* Ensure this process owns a reader slot. Called from the lock helpers so
243 * that fork()'d children pick up their own slot lazily instead of sharing
244 * the parent's. Hot-path is a single relaxed load + compare; only on a
245 * fork-generation mismatch do we touch getpid() and scan slots. */
246 84801 static inline void hw_claim_reader_slot(HwHandle *h) {
247 84801 uint32_t cur_gen = __atomic_load_n(&hw_fork_gen, __ATOMIC_RELAXED);
248 84801 ▶ 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)) 84745 56 84801
if (__builtin_expect(cur_gen == h->cached_fork_gen && h->my_slot_idx != UINT32_MAX, 1)) 84745 0 84745
249 84745 return;
250 /* Cold path -- register the atfork hook once per process, then claim. */
251 56 pthread_once(&hw_atfork_once, hw_atfork_init);
252 /* Re-read after pthread_once: hw_on_fork_child may have bumped it. */
253 56 cur_gen = __atomic_load_n(&hw_fork_gen, __ATOMIC_RELAXED);
254 56 uint32_t now_pid = (uint32_t)getpid();
255 56 h->cached_pid = now_pid;
256 56 ▶ 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 */ 56 0 56
257 56 h->cached_fork_gen = cur_gen;
258 56 h->my_slot_idx = UINT32_MAX;
259 56 uint32_t start = now_pid % HW_READER_SLOTS;
260 /* Pass 1: take a free slot. */
261 71 ▶ for (uint32_t i = 0; i < HW_READER_SLOTS; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t i = 0; i < HW_READER_SLOTS; i++) { 71 0 71
262 71 uint32_t s = (start + i) % HW_READER_SLOTS;
263 71 uint32_t expected = 0;
264 71 ▶ if (__atomic_compare_exchange_n(&h->reader_slots[s].pid,
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_compare_exchange_n(&h->reader_slots[s].pid, 56 15 71
265 &expected, now_pid, 0,
266 __ATOMIC_ACQUIRE, __ATOMIC_RELAXED)) {
267 /* Fresh owner holds no read locks yet; clear any stale rdepth left by
268 * a dead predecessor (its contribution is dropped as we take over). */
269 56 __atomic_store_n(&h->reader_slots[s].rdepth, 0, __ATOMIC_RELAXED);
270 56 hw_occ_set(h, s); /* mark occupied BEFORE any rdlock can bump rdepth */
271 56 h->my_slot_idx = s;
272 56 return;
273 }
274 }
275 /* Pass 2: no free slot -- reclaim one whose owner is dead. Safe to take even
276 * if its rdepth>0: clearing pid drops the dead reader's entire contribution
277 * (a writer scan ignores rdepth when pid==0) and we reset rdepth to 0 as we
278 * claim it. */
279 0 ▶ for (uint32_t i = 0; i < HW_READER_SLOTS; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t i = 0; i < HW_READER_SLOTS; i++) { 0 0 0
280 0 uint32_t dpid = __atomic_load_n(&h->reader_slots[i].pid, __ATOMIC_ACQUIRE);
281 0 ▶ if (dpid == 0 || dpid == now_pid || hw_pid_alive(dpid)) continue;
Branch: 3 branches
BranchTrueFalseTotal
if (dpid == 0 || dpid == now_pid || hw_pid_alive(dpid)) continue; 0 0 0
if (dpid == 0 || dpid == now_pid || hw_pid_alive(dpid)) continue; 0 0 0
if (dpid == 0 || dpid == now_pid || hw_pid_alive(dpid)) continue; 0 0 0
282 0 uint32_t expected = dpid;
283 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
284 __ATOMIC_ACQUIRE, __ATOMIC_RELAXED)) {
285 0 __atomic_store_n(&h->reader_slots[i].rdepth, 0, __ATOMIC_RELAXED);
286 0 hw_occ_set(h, i);
287 0 h->my_slot_idx = i;
288 0 return;
289 }
290 }
291 /* Table full -- leave my_slot_idx = UINT32_MAX so this handle takes the
292 * slotless path (lock still works; recovery of THIS reader's death is the
293 * documented slotless limitation). */
294 }
295  
296 /* Wait until no live reader holds the lock; the caller owns wlock, so no NEW
297 * reader can join (they see wlock!=0 and yield). The SEQ_CST wlock CAS + the
298 * SEQ_CST rdepth loads below are the writer side of the Dekker handshake. */
299 42761 static inline void hw_rwlock_drain(HwHandle *h) {
300 42761 HwHeader *hdr = h->hdr;
301 0 for (;;) {
302 42761 uint32_t v = __atomic_load_n(&hdr->drain_seq, __ATOMIC_ACQUIRE); /* snapshot BEFORE scan */
303 42761 int busy = 0;
304 /* Visit only OCCUPIED slots via the occupancy bitmap (SEQ_CST: a committed
305 * reader's bit -- set in claim, before its rdepth++ -- is ordered before
306 * this scan, so no held slot is skipped). O(HW_OCC_WORDS + live readers)
307 * instead of O(HW_READER_SLOTS). */
308 726937 ▶ for (uint32_t w = 0; w < HW_OCC_WORDS; w++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t w = 0; w < HW_OCC_WORDS; w++) { 684176 42761 726937
309 684176 uint64_t word = __atomic_load_n(&h->occ[w], __ATOMIC_SEQ_CST);
310 754893 ▶ while (word) {
Branch: 1 branch
BranchTrueFalseTotal
while (word) { 70717 684176 754893
311 70717 uint32_t i = (w << 6) + (uint32_t)__builtin_ctzll(word);
312 70717 word &= word - 1; /* consume this bit (local copy) */
313 70717 uint32_t rd = __atomic_load_n(&h->reader_slots[i].rdepth, __ATOMIC_SEQ_CST);
314 70717 ▶ if (rd == 0) continue; /* occupied but not read-locking now */
Branch: 1 branch
BranchTrueFalseTotal
if (rd == 0) continue; /* occupied but not read-locking now */ 70717 0 70717
315 0 uint32_t pid = __atomic_load_n(&h->reader_slots[i].pid, __ATOMIC_ACQUIRE);
316 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
317 0 ▶ if (!hw_pid_alive(pid)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!hw_pid_alive(pid)) { 0 0 0
318 /* Dead reader: drop its pid so the slot no longer counts. Leave
319 * the occ bit set (harmless -- a later scan hits pid==0 and skips,
320 * a re-claim re-sets it) to avoid racing a concurrent claimant. */
321 0 uint32_t ep = pid;
322 0 __atomic_compare_exchange_n(&h->reader_slots[i].pid, &ep, 0,
323 0, __ATOMIC_ACQ_REL, __ATOMIC_RELAXED);
324 0 continue;
325 }
326 0 busy = 1; /* live reader still holding */
327 }
328 }
329 /* A live slotless reader keeps us waiting; a crashed slotless reader that
330 * cannot be attributed to a pid is the documented slotless limitation. */
331 42761 ▶ 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 42761 42761
332 0 busy = 1;
333 42761 ▶ if (!busy)
Branch: 1 branch
BranchTrueFalseTotal
if (!busy) 42761 0 42761
334 42761 return; /* exclusive: wlock held + every rdepth 0 */
335 /* Wait for a reader to release (drain_seq bump) or time out to re-scan
336 * (which reclaims any newly-dead slotted reader). */
337 0 syscall(SYS_futex, &hdr->drain_seq, FUTEX_WAIT, v, &hw_lock_timeout, NULL, 0);
338 }
339 }
340  
341 /* 1 if this process holds a read lock on the segment (through any handle). Such a
342 * lock predates the current wlock holder, whose drain could then never have
343 * finished: it died before mutating anything. */
344 0 static int hw_self_reading(HwHandle *h) {
345 0 ▶ if (h->slotless_held) return 1;
Branch: 1 branch
BranchTrueFalseTotal
if (h->slotless_held) return 1; 0 0 0
346 0 uint32_t me = (uint32_t)getpid();
347 0 ▶ for (uint32_t i = 0; i < HW_READER_SLOTS; i++)
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t i = 0; i < HW_READER_SLOTS; i++) 0 0 0
348 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
349 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
350 0 return 1;
351 0 return 0;
352 }
353  
354 static void hw_repair_locked(HwHandle *h);
355  
356 /* Force-recover a stale WRITE lock left by a dead writer (held or mid-drain).
357 * CAS to OUR pid to hold the lock while repairing shared state, then release.
358 * Using our pid (not a bare WRITER_BIT sentinel) means a subsequent recovering
359 * process can detect and re-recover if we crash mid-recovery. */
360 0 static inline void hw_recover_stale_lock(HwHandle *h, uint32_t observed_wlock) {
361 0 HwHeader *hdr = h->hdr;
362 0 uint32_t mypid = HW_RWLOCK_WR((uint32_t)getpid());
363 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
364 mypid, 0, __ATOMIC_SEQ_CST, __ATOMIC_RELAXED))
365 0 return;
366 0 ▶ if (!hw_self_reading(h)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!hw_self_reading(h)) { 0 0 0
367 0 hw_rwlock_drain(h);
368 0 hw_repair_locked(h);
369 }
370 0 __atomic_store_n(&hdr->wlock, 0, __ATOMIC_RELEASE);
371 0 ▶ if (__atomic_load_n(&hdr->rwait, __ATOMIC_RELAXED) > 0)
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&hdr->rwait, __ATOMIC_RELAXED) > 0) 0 0 0
372 0 syscall(SYS_futex, &hdr->wlock, FUTEX_WAKE, INT_MAX, NULL, NULL, 0);
373 }
374  
375 /* Inspect the writer word after a futex-wait timeout. If a dead writer holds
376 * it, force-recover. Dead READERS need no action here: only a writer that owns
377 * wlock drains readers, and it clears dead readers inline in its own scan. */
378 0 static inline void hw_recover_after_timeout(HwHandle *h) {
379 0 uint32_t val = __atomic_load_n(&h->hdr->wlock, __ATOMIC_RELAXED);
380 0 ▶ if (val >= HW_RWLOCK_WRITER_BIT) {
Branch: 1 branch
BranchTrueFalseTotal
if (val >= HW_RWLOCK_WRITER_BIT) { 0 0 0
381 0 uint32_t pid = val & HW_RWLOCK_PID_MASK;
382 0 ▶ if (!hw_pid_alive(pid))
Branch: 1 branch
BranchTrueFalseTotal
if (!hw_pid_alive(pid)) 0 0 0
383 0 hw_recover_stale_lock(h, val);
384 }
385 0 }
386  
387 /* Bump/drop the parked-waiter hint. Both readers (blocked at the gate) and
388 * writers (blocked acquiring wlock) wait on the wlock futex and use this, so
389 * wrunlock/recover know whether a FUTEX_WAKE is worth a syscall. A waiter
390 * SIGKILLed while parked leaves rwait over-counted -> at most a spurious wake
391 * (harmless); it can never under-count, so no wakeup is lost. */
392 0 static inline void hw_park(HwHandle *h) {
393 0 __atomic_add_fetch(&h->hdr->rwait, 1, __ATOMIC_RELAXED);
394 0 }
395 0 static inline void hw_unpark(HwHandle *h) {
396 0 __atomic_sub_fetch(&h->hdr->rwait, 1, __ATOMIC_RELAXED);
397 0 }
398  
399 /* Publish (inc) / retract (dec) this reader's presence -- its ENTIRE
400 * contribution to the lock. A slotted reader uses its slot's rdepth; a reader
401 * that could not claim a slot uses the global slotless_rdepth. inc() is SEQ_CST
402 * so the wlock re-check that follows it in rdlock forms a Dekker handshake with
403 * the writer's SEQ_CST wlock-store + rdepth-scan. leave() peels slotless first
404 * so a slot claimed mid-hold cannot misattribute the decrement. */
405 42040 static inline void hw_rdepth_inc(HwHandle *h) {
406 42040 ▶ if (h->my_slot_idx != UINT32_MAX) {
Branch: 1 branch
BranchTrueFalseTotal
if (h->my_slot_idx != UINT32_MAX) { 42040 0 42040
407 42040 __atomic_add_fetch(&h->reader_slots[h->my_slot_idx].rdepth, 1, __ATOMIC_SEQ_CST);
408 } else {
409 0 __atomic_add_fetch(&h->hdr->slotless_rdepth, 1, __ATOMIC_SEQ_CST);
410 0 h->slotless_held++;
411 }
412 42040 }
413 42040 static inline void hw_rdepth_dec(HwHandle *h) {
414 42040 ▶ if (h->slotless_held > 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (h->slotless_held > 0) { 0 42040 42040
415 0 h->slotless_held--;
416 0 __atomic_sub_fetch(&h->hdr->slotless_rdepth, 1, __ATOMIC_RELEASE);
417 42040 ▶ } else if (h->my_slot_idx != UINT32_MAX) {
Branch: 1 branch
BranchTrueFalseTotal
} else if (h->my_slot_idx != UINT32_MAX) { 42040 0 42040
418 42040 __atomic_sub_fetch(&h->reader_slots[h->my_slot_idx].rdepth, 1, __ATOMIC_RELEASE);
419 }
420 42040 }
421  
422 /* Wake a writer that may be draining readers (it waits on drain_seq). Called
423 * after every rdepth decrement so a released read lock lets the writer re-scan
424 * promptly instead of waiting out its timeout. */
425 42040 static inline void hw_reader_wake_drain(HwHandle *h) {
426 42040 ▶ if (__atomic_load_n(&h->hdr->wlock, __ATOMIC_ACQUIRE) != 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&h->hdr->wlock, __ATOMIC_ACQUIRE) != 0) { 0 42040 42040
427 0 __atomic_add_fetch(&h->hdr->drain_seq, 1, __ATOMIC_RELEASE);
428 0 syscall(SYS_futex, &h->hdr->drain_seq, FUTEX_WAKE, 1, NULL, NULL, 0);
429 }
430 42040 }
431  
432 42040 static inline void hw_rwlock_rdlock(HwHandle *h) {
433 42040 hw_claim_reader_slot(h);
434 42040 HwHeader *hdr = h->hdr;
435 42040 for (int spin = 0; ; spin++) {
436 42040 uint32_t cur = __atomic_load_n(&hdr->wlock, __ATOMIC_ACQUIRE);
437 42040 ▶ if (cur == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (cur == 0) { 42040 0 42040
438 /* Optimistically take the read: publish rdepth, then re-check wlock.
439 * SEQ_CST inc + SEQ_CST load vs the writer's SEQ_CST wlock CAS +
440 * SEQ_CST rdepth scan: by the single total order of SEQ_CST ops the
441 * two sides cannot both miss each other, so we never hold
442 * concurrently with a writer. */
443 42040 hw_rdepth_inc(h);
444 42040 ▶ if (__atomic_load_n(&hdr->wlock, __ATOMIC_SEQ_CST) == 0)
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&hdr->wlock, __ATOMIC_SEQ_CST) == 0) 42040 0 42040
445 42040 return; /* no writer after our publish -> we hold the read lock */
446 /* A writer appeared during our publish -- yield to it (write-preferring). */
447 0 hw_rdepth_dec(h);
448 0 hw_reader_wake_drain(h); /* let the draining writer see rdepth drop */
449 0 spin = 0;
450 0 continue;
451 }
452 /* wlock != 0: a writer holds or is acquiring. Recover if it is dead. */
453 0 if (cur >= HW_RWLOCK_WRITER_BIT &&
454 0 !hw_pid_alive(cur & HW_RWLOCK_PID_MASK)) {
455 0 hw_recover_stale_lock(h, cur);
456 0 spin = 0;
457 0 continue;
458 }
459 0 ▶ if (__builtin_expect(spin < HW_RWLOCK_SPIN_LIMIT, 1)) {
Branch: 1 branch
BranchTrueFalseTotal
if (__builtin_expect(spin < HW_RWLOCK_SPIN_LIMIT, 1)) { 0 0 0
460 0 hw_rwlock_spin_pause();
461 0 continue;
462 }
463 0 hw_park(h);
464 0 cur = __atomic_load_n(&hdr->wlock, __ATOMIC_RELAXED);
465 0 ▶ if (cur != 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (cur != 0) { 0 0 0
466 0 long rc = syscall(SYS_futex, &hdr->wlock, FUTEX_WAIT, cur,
467 &hw_lock_timeout, NULL, 0);
468 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
469 0 hw_unpark(h);
470 0 hw_recover_after_timeout(h);
471 0 spin = 0;
472 0 continue;
473 }
474 }
475 0 hw_unpark(h);
476 0 spin = 0;
477 }
478 }
479  
480 42040 static inline void hw_rwlock_rdunlock(HwHandle *h) {
481 42040 hw_rdepth_dec(h); /* RELEASE: drop our entire contribution */
482 42040 hw_reader_wake_drain(h); /* if a writer is draining, wake it to re-scan */
483 42040 }
484  
485 42761 static inline void hw_rwlock_wrlock(HwHandle *h) {
486 42761 hw_claim_reader_slot(h); /* refresh cached_pid across fork */
487 42761 HwHeader *hdr = h->hdr;
488 /* Encode PID in the wlock word itself (0x80000000 | pid) to eliminate any
489 * crash window between acquiring the lock and storing the owner. */
490 42761 uint32_t mypid = HW_RWLOCK_WR(h->cached_pid);
491 /* Phase 1: acquire the writer word (mutual exclusion among writers). */
492 42761 for (int spin = 0; ; spin++) {
493 42761 uint32_t expected = 0;
494 42761 ▶ if (__atomic_compare_exchange_n(&hdr->wlock, &expected, mypid,
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_compare_exchange_n(&hdr->wlock, &expected, mypid, 42761 0 42761
495 0, __ATOMIC_SEQ_CST, __ATOMIC_RELAXED))
496 42761 break;
497 /* Contended: expected now holds the current wlock value. */
498 0 if (expected >= HW_RWLOCK_WRITER_BIT &&
499 0 !hw_pid_alive(expected & HW_RWLOCK_PID_MASK)) {
500 0 hw_recover_stale_lock(h, expected);
501 0 spin = 0;
502 0 continue;
503 }
504 0 ▶ if (__builtin_expect(spin < HW_RWLOCK_SPIN_LIMIT, 1)) {
Branch: 1 branch
BranchTrueFalseTotal
if (__builtin_expect(spin < HW_RWLOCK_SPIN_LIMIT, 1)) { 0 0 0
505 0 hw_rwlock_spin_pause();
506 0 continue;
507 }
508 0 hw_park(h);
509 0 uint32_t cur = __atomic_load_n(&hdr->wlock, __ATOMIC_RELAXED);
510 0 ▶ if (cur != 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (cur != 0) { 0 0 0
511 0 long rc = syscall(SYS_futex, &hdr->wlock, FUTEX_WAIT, cur,
512 &hw_lock_timeout, NULL, 0);
513 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
514 0 hw_unpark(h);
515 0 hw_recover_after_timeout(h);
516 0 spin = 0;
517 0 continue;
518 }
519 }
520 0 hw_unpark(h);
521 0 spin = 0;
522 }
523 /* Phase 2: drain the readers that were already holding when we won the CAS. */
524 42761 hw_rwlock_drain(h);
525 42761 }
526  
527 42761 static inline void hw_rwlock_wrunlock(HwHandle *h) {
528 42761 HwHeader *hdr = h->hdr;
529 42761 __atomic_store_n(&hdr->wlock, 0, __ATOMIC_RELEASE);
530 42761 ▶ if (__atomic_load_n(&hdr->rwait, __ATOMIC_RELAXED) > 0)
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&hdr->rwait, __ATOMIC_RELAXED) > 0) 0 42761 42761
531 0 syscall(SYS_futex, &hdr->wlock, FUTEX_WAKE, INT_MAX, NULL, NULL, 0);
532 42761 }
533  
534 /* ================================================================
535 * Layout math + create / open / destroy
536 *
537 * Layout: Header -> reader_slots[1024] -> occ bitmap -> buckets[num_levels*num_slots] -> timers[capacity]
538 * ================================================================ */
539  
540 /* Single source of truth for the mmap region layout offsets.
541 * Layout: Header -> reader_slots[1024] -> occ bitmap -> buckets[num_levels*num_slots] -> timers[capacity] */
542 typedef struct { uint64_t reader_slots, occ, slots, timers, total; } HwLayout;
543  
544 187 static inline HwLayout hw_layout_for(uint32_t num_slots, uint32_t num_levels, uint32_t capacity) {
545 HwLayout L;
546 187 L.reader_slots = sizeof(HwHeader);
547 187 L.occ = L.reader_slots + (uint64_t)HW_READER_SLOTS * sizeof(HwReaderSlot);
548 187 L.slots = L.occ + HW_OCC_BYTES;
549 187 L.slots = (L.slots + 7) & ~(uint64_t)7;
550 187 L.timers = L.slots + (uint64_t)num_levels * num_slots * sizeof(uint32_t);
551 187 L.timers = (L.timers + 7) & ~(uint64_t)7;
552 187 L.total = L.timers + (uint64_t)capacity * sizeof(HwTimer);
553 187 return L;
554 }
555  
556 71 static inline uint64_t hw_total_size(uint32_t num_slots, uint32_t num_levels, uint32_t capacity) {
557 71 return hw_layout_for(num_slots, num_levels, capacity).total;
558 }
559  
560 /* compute tick[k] = num_slots^k (ticks per level-k slot) for k in 0..num_levels
561 * into out[]; returns 0 if num_slots^num_levels overflows uint64 (the maximum
562 * schedulable delay + 1), else 1. */
563 130 static inline int hw_compute_ticks(uint32_t num_slots, uint32_t num_levels, uint64_t *out) {
564 130 out[0] = 1;
565 524 ▶ for (uint32_t k = 1; k <= num_levels; k++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t k = 1; k <= num_levels; k++) { 395 129 524
566 395 ▶ if (num_slots == 0 || out[k - 1] > UINT64_MAX / num_slots) return 0; /* overflow */
Branch: 2 branches
BranchTrueFalseTotal
if (num_slots == 0 || out[k - 1] > UINT64_MAX / num_slots) return 0; /* overflow */ 395 0 395
if (num_slots == 0 || out[k - 1] > UINT64_MAX / num_slots) return 0; /* overflow */ 1 394 395
567 394 out[k] = out[k - 1] * num_slots;
568 }
569 129 return 1;
570 }
571  
572 292095 static inline uint32_t *hw_slots(HwHandle *h) { return (uint32_t *)((char *)h->base + h->slots_off); }
573 121197 static inline HwTimer *hw_timer(HwHandle *h, uint64_t i) { return (HwTimer *)((char *)h->base + h->timers_off) + i; }
574 6845 static inline uint64_t hw_num_bucket(HwHandle *h) { return (uint64_t)h->num_levels * h->num_slots; }
575  
576 41 static inline void hw_init_header(void *base, uint32_t num_slots, uint32_t num_levels, uint32_t capacity, uint64_t total) {
577 41 HwLayout L = hw_layout_for(num_slots, num_levels, capacity);
578 41 HwHeader *hdr = (HwHeader *)base;
579 41 memset(base, 0, (size_t)L.total);
580 41 uint32_t *slots = (uint32_t *)((char *)base + L.slots);
581 41 uint64_t nb = (uint64_t)num_levels * num_slots;
582 263782 ▶ for (uint64_t s = 0; s < nb; s++) slots[s] = HW_NIL; /* all buckets empty */
Branch: 1 branch
BranchTrueFalseTotal
for (uint64_t s = 0; s < nb; s++) slots[s] = HW_NIL; /* all buckets empty */ 263741 41 263782
583 41 HwTimer *timers = (HwTimer *)((char *)base + L.timers);
584 4344 ▶ for (uint32_t i = 0; i < capacity; i++) { /* thread the free list */
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t i = 0; i < capacity; i++) { /* thread the free list */ 4303 41 4344
585 4303 ▶ timers[i].next = (i + 1 < capacity) ? (i + 1) : HW_NIL;
Branch: 1 branch
BranchTrueFalseTotal
timers[i].next = (i + 1 < capacity) ? (i + 1) : HW_NIL; 4262 41 4303
586 4303 timers[i].prev = HW_NIL;
587 4303 timers[i].bucket = HW_NIL;
588 4303 timers[i].state = 0;
589 }
590 41 hdr->version = HW_VERSION;
591 41 hdr->num_slots = num_slots;
592 41 hdr->num_levels = num_levels;
593 41 hdr->capacity = capacity;
594 41 ▶ hdr->free_head = capacity ? 0 : HW_NIL;
Branch: 1 branch
BranchTrueFalseTotal
hdr->free_head = capacity ? 0 : HW_NIL; 41 0 41
595 41 hdr->now = 0;
596 41 hdr->count = 0;
597 41 hdr->slots_off = L.slots;
598 41 hdr->timers_off = L.timers;
599 41 hdr->total_size = total;
600 41 hdr->reader_slots_off = L.reader_slots;
601 /* Publish magic LAST, as a release store: it is the commit point, so a
602 creator killed before it leaves magic==0 and never a file mistaken for
603 a valid one. A kill during the field stores leaves one to remove by
604 hand. */
605 41 __atomic_store_n(&hdr->magic, HW_MAGIC, __ATOMIC_RELEASE);
606 41 __atomic_thread_fence(__ATOMIC_SEQ_CST);
607 41 }
608  
609 /* Layer B trusted bound: number of timers guaranteed within the real mapping.
610 * Equals capacity for a valid wheel; every timer index from shared memory is
611 * checked against it so a corrupt link can never drive an access out of bounds. */
612 230 static inline uint64_t hw_timers_max(HwHandle *h) {
613 230 ▶ if (h->timers_off >= h->mmap_size) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (h->timers_off >= h->mmap_size) return 0; 0 230 230
614 230 return (h->mmap_size - h->timers_off) / sizeof(HwTimer);
615 }
616 #define HW_TIMER_OK(h, i) ((uint32_t)(i) != HW_NIL && (uint64_t)(i) < (uint64_t)(h)->capacity)
617 #define HW_BUCKET_OK(h, b) ((uint32_t)(b) != HW_NIL && (uint64_t)(b) < hw_num_bucket(h))
618  
619 58 static inline HwHandle *hw_setup(void *base, size_t map_size,
620 const char *path, int backing_fd) {
621 58 HwHeader *hdr = (HwHeader *)base;
622 58 HwHandle *h = (HwHandle *)calloc(1, sizeof(HwHandle));
623 58 ▶ if (!h) {
Branch: 1 branch
BranchTrueFalseTotal
if (!h) { 0 58 58
624 0 munmap(base, map_size);
625 0 ▶ if (backing_fd >= 0) close(backing_fd);
Branch: 1 branch
BranchTrueFalseTotal
if (backing_fd >= 0) close(backing_fd); 0 0 0
626 0 return NULL;
627 }
628 58 h->hdr = hdr;
629 58 h->base = base;
630 58 h->reader_slots = (HwReaderSlot *)((uint8_t *)base + sizeof(HwHeader)); /* trusted layout, not the peer-writable header offset */
631 58 h->occ = (uint64_t *)((uint8_t *)base + hw_layout_for(0, 0, 0).occ); /* occ offset is geometry-independent (trusted) */
632 58 h->slots_off = hdr->slots_off; /* single validated read of each geometry field */
633 58 h->timers_off = hdr->timers_off;
634 58 h->num_slots = hdr->num_slots;
635 58 h->num_levels = hdr->num_levels;
636 58 h->capacity = hdr->capacity;
637 58 hw_compute_ticks(h->num_slots, h->num_levels, h->tick); /* validate_header ensured no overflow */
638 58 h->mmap_size = map_size;
639 /* Layer B: clamp the cached capacity to the number of timers that actually fit */
640 {
641 58 uint64_t fit = hw_timers_max(h);
642 58 ▶ 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 58 58
643 }
644 58 ▶ h->path = path ? strdup(path) : NULL;
Branch: 1 branch
BranchTrueFalseTotal
h->path = path ? strdup(path) : NULL; 21 37 58
645 58 h->backing_fd = backing_fd;
646 58 h->my_slot_idx = UINT32_MAX;
647 58 return h;
648 }
649  
650 /* Validate a mapped header (shared by hw_create reopen and hw_open_fd). */
651 21 static inline int hw_validate_header(const HwHeader *hdr, uint64_t file_size) {
652 21 ▶ if (hdr->magic != HW_MAGIC) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->magic != HW_MAGIC) return 0; 4 17 21
653 17 ▶ if (hdr->version != HW_VERSION) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->version != HW_VERSION) return 0; 0 17 17
654 17 ▶ if (hdr->num_slots < HW_MIN_SLOTS || hdr->num_slots > HW_MAX_SLOTS) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (hdr->num_slots < HW_MIN_SLOTS || hdr->num_slots > HW_MAX_SLOTS) return 0; 17 0 17
if (hdr->num_slots < HW_MIN_SLOTS || hdr->num_slots > HW_MAX_SLOTS) return 0; 0 17 17
655 17 ▶ if (hdr->num_levels < HW_MIN_LEVELS || hdr->num_levels > HW_MAX_LEVELS) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (hdr->num_levels < HW_MIN_LEVELS || hdr->num_levels > HW_MAX_LEVELS) return 0; 17 0 17
if (hdr->num_levels < HW_MIN_LEVELS || hdr->num_levels > HW_MAX_LEVELS) return 0; 0 17 17
656 17 ▶ if (hdr->capacity < HW_MIN_CAP || hdr->capacity > HW_MAX_CAP) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (hdr->capacity < HW_MIN_CAP || hdr->capacity > HW_MAX_CAP) return 0; 17 0 17
if (hdr->capacity < HW_MIN_CAP || hdr->capacity > HW_MAX_CAP) return 0; 0 17 17
657 17 ▶ if (hdr->count > hdr->capacity) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->count > hdr->capacity) return 0; 0 17 17
658 { uint64_t t[HW_MAX_LEVELS + 1];
659 17 ▶ if (!hw_compute_ticks(hdr->num_slots, hdr->num_levels, t)) return 0; } /* S^L must fit uint64 */
Branch: 1 branch
BranchTrueFalseTotal
if (!hw_compute_ticks(hdr->num_slots, hdr->num_levels, t)) return 0; } /* S^L must fit uint64 */ 0 17 17
660 17 ▶ if (hdr->total_size != file_size) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->total_size != file_size) return 0; 0 17 17
661 17 ▶ if (hdr->total_size != hw_total_size(hdr->num_slots, hdr->num_levels, hdr->capacity)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->total_size != hw_total_size(hdr->num_slots, hdr->num_levels, hdr->capacity)) return 0; 0 17 17
662 17 HwLayout L = hw_layout_for(hdr->num_slots, hdr->num_levels, hdr->capacity);
663 17 ▶ 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 17 17
664 17 ▶ if (hdr->slots_off != L.slots) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->slots_off != L.slots) return 0; 0 17 17
665 17 ▶ if (hdr->timers_off != L.timers) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->timers_off != L.timers) return 0; 0 17 17
666 17 return 1;
667 }
668  
669 /* validate the requested wheel geometry + timer capacity */
670 57 static int hw_validate_args(uint64_t num_slots, uint64_t num_levels, uint64_t capacity, char *errbuf) {
671 57 ▶ if (errbuf) errbuf[0] = '\0';
Branch: 1 branch
BranchTrueFalseTotal
if (errbuf) errbuf[0] = '\0'; 57 0 57
672 57 ▶ if (num_slots < HW_MIN_SLOTS || num_slots > HW_MAX_SLOTS) { HW_ERR("num_slots must be between 2 and 2^16"); return 0; }
Branch: 3 branches
BranchTrueFalseTotal
if (num_slots < HW_MIN_SLOTS || num_slots > HW_MAX_SLOTS) { HW_ERR("num_slots must be between 2 and 2^16"); return 0; } 56 1 57
if (num_slots < HW_MIN_SLOTS || num_slots > HW_MAX_SLOTS) { HW_ERR("num_slots must be between 2 and 2^16"); return 0; } 0 56 56
if (num_slots < HW_MIN_SLOTS || num_slots > HW_MAX_SLOTS) { HW_ERR("num_slots must be between 2 and 2^16"); return 0; } 1 0 1
673 56 ▶ if (num_levels < HW_MIN_LEVELS || num_levels > HW_MAX_LEVELS) { HW_ERR("num_levels must be between 1 and 16"); return 0; }
Branch: 3 branches
BranchTrueFalseTotal
if (num_levels < HW_MIN_LEVELS || num_levels > HW_MAX_LEVELS) { HW_ERR("num_levels must be between 1 and 16"); return 0; } 55 1 56
if (num_levels < HW_MIN_LEVELS || num_levels > HW_MAX_LEVELS) { HW_ERR("num_levels must be between 1 and 16"); return 0; } 0 55 55
if (num_levels < HW_MIN_LEVELS || num_levels > HW_MAX_LEVELS) { HW_ERR("num_levels must be between 1 and 16"); return 0; } 1 0 1
674 55 ▶ if (capacity < HW_MIN_CAP || capacity > HW_MAX_CAP) { HW_ERR("capacity must be between 1 and 2^24"); return 0; }
Branch: 3 branches
BranchTrueFalseTotal
if (capacity < HW_MIN_CAP || capacity > HW_MAX_CAP) { HW_ERR("capacity must be between 1 and 2^24"); return 0; } 55 0 55
if (capacity < HW_MIN_CAP || capacity > HW_MAX_CAP) { HW_ERR("capacity must be between 1 and 2^24"); return 0; } 0 55 55
if (capacity < HW_MIN_CAP || capacity > HW_MAX_CAP) { HW_ERR("capacity must be between 1 and 2^24"); return 0; } 0 0 0
675 { uint64_t t[HW_MAX_LEVELS + 1];
676 55 ▶ if (!hw_compute_ticks((uint32_t)num_slots, (uint32_t)num_levels, t))
Branch: 1 branch
BranchTrueFalseTotal
if (!hw_compute_ticks((uint32_t)num_slots, (uint32_t)num_levels, t)) 1 54 55
677 1 ▶ { HW_ERR("num_slots^num_levels overflows 64 bits; reduce num_slots or num_levels"); return 0; } }
Branch: 1 branch
BranchTrueFalseTotal
{ HW_ERR("num_slots^num_levels overflows 64 bits; reduce num_slots or num_levels"); return 0; } } 1 0 1
678 54 return 1;
679 }
680  
681 /* Securely obtain a fd for a path-backed segment: create it exclusively
682 * (O_CREAT|O_EXCL|O_NOFOLLOW at `mode`, default 0600 = owner-only), or, if it
683 * already exists, attach to it (O_RDWR|O_NOFOLLOW, no O_CREAT). O_EXCL blocks a
684 * pre-seeded or hard-linked file and O_NOFOLLOW a symlink swap, so a local
685 * attacker can no longer redirect or poison the backing store through the path.
686 * Cross-user sharing is opt-in via a wider `mode` (e.g. 0660); the caller still
687 * validates the file's contents via hw_validate_header. */
688 25 static int hw_secure_open(const char *path, mode_t mode, char *errbuf) {
689 25 ▶ for (int attempt = 0; attempt < 100; attempt++) {
Branch: 1 branch
BranchTrueFalseTotal
for (int attempt = 0; attempt < 100; attempt++) { 25 0 25
690 25 int fd = open(path, O_RDWR|O_CREAT|O_EXCL|O_NOFOLLOW|O_CLOEXEC, mode);
691 25 ▶ 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 */ 11 14 25
692 14 ▶ if (errno != EEXIST) { HW_ERR("create %s: %s", path, strerror(errno)); return -1; }
Branch: 2 branches
BranchTrueFalseTotal
if (errno != EEXIST) { HW_ERR("create %s: %s", path, strerror(errno)); return -1; } 0 14 14
if (errno != EEXIST) { HW_ERR("create %s: %s", path, strerror(errno)); return -1; } 0 0 0
693 14 fd = open(path, O_RDWR|O_NOFOLLOW|O_CLOEXEC);
694 14 ▶ if (fd >= 0) return fd;
Branch: 1 branch
BranchTrueFalseTotal
if (fd >= 0) return fd; 14 0 14
695 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
696 0 ▶ HW_ERR("open %s: %s", path, strerror(errno)); /* ELOOP => symlink rejected */
Branch: 1 branch
BranchTrueFalseTotal
HW_ERR("open %s: %s", path, strerror(errno)); /* ELOOP => symlink rejected */ 0 0 0
697 0 return -1;
698 }
699 0 ▶ HW_ERR("open %s: create/attach kept racing", path);
Branch: 1 branch
BranchTrueFalseTotal
HW_ERR("open %s: create/attach kept racing", path); 0 0 0
700 0 return -1;
701 }
702  
703 /* True iff the whole file is zero -- what an abandoned mid-init
704 creator leaves. Lets recovery re-init only a provably-empty file, never
705 one that merely starts with a zero word. Cold path, so a byte scan is
706 fine. Read, not mapped: a read fault on a tmpfs hole allocates the page. */
707 2 static int hw_file_is_zero(int fd, uint64_t size) {
708 char buf[16384];
709 5 ▶ for (uint64_t off = 0; off < size; ) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint64_t off = 0; off < size; ) { 4 1 5
710 4 ssize_t n = pread(fd, buf, size - off < sizeof buf ? (size_t)(size - off) : sizeof buf, (off_t)off);
711 4 ▶ if (n <= 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (n <= 0) return 0; 0 4 4
712 40323 ▶ 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 40319 40320
for (ssize_t i = 0; i < n; i++) if (buf[i]) return 0; 40320 3 40323
713 3 off += (uint64_t)n;
714 }
715 1 return 1;
716 }
717  
718 /* A sparse segment would SIGBUS at the first write the filesystem cannot back. */
719 21 static int hw_reserve(int fd, uint64_t size) {
720 21 const char *sp = getenv("DATA_HIERTIMINGWHEEL_SHARED_SPARSE");
721 21 ▶ if (sp && *sp && strcmp(sp, "0")) return 0;
Branch: 3 branches
BranchTrueFalseTotal
if (sp && *sp && strcmp(sp, "0")) return 0; 0 21 21
if (sp && *sp && strcmp(sp, "0")) return 0; 0 0 0
if (sp && *sp && strcmp(sp, "0")) return 0; 0 0 0
722 /* Before Linux 6.11 tmpfs gives up at any pending signal and undoes the allocation, so a
723 * periodic one could keep it from ever completing; SIGSTOP cannot be blocked. */
724 sigset_t all, old;
725 21 sigfillset(&all);
726 21 sigprocmask(SIG_BLOCK, &all, &old);
727 int e;
728 21 ▶ 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 21 21
729 21 sigprocmask(SIG_SETMASK, &old, NULL);
730 21 ▶ if (e == 0 || e == EOPNOTSUPP || e == EINVAL) return 0;
Branch: 3 branches
BranchTrueFalseTotal
if (e == 0 || e == EOPNOTSUPP || e == EINVAL) return 0; 0 21 21
if (e == 0 || e == EOPNOTSUPP || e == EINVAL) return 0; 0 0 0
if (e == 0 || e == EOPNOTSUPP || e == EINVAL) return 0; 0 0 0
731 0 errno = e;
732 0 return -1;
733 }
734  
735 48 static HwHandle *hw_create(const char *path, uint64_t num_slots, uint64_t num_levels, uint64_t capacity, mode_t mode, char *errbuf) {
736 48 ▶ if (!hw_validate_args(num_slots, num_levels, capacity, errbuf)) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!hw_validate_args(num_slots, num_levels, capacity, errbuf)) return NULL; 3 45 48
737  
738 45 uint64_t total = hw_total_size((uint32_t)num_slots, (uint32_t)num_levels, (uint32_t)capacity);
739 45 int anonymous = (path == NULL);
740 45 int fd = -1;
741 size_t map_size;
742 void *base;
743  
744 45 ▶ if (anonymous) {
Branch: 1 branch
BranchTrueFalseTotal
if (anonymous) { 20 25 45
745 20 map_size = (size_t)total;
746 20 base = mmap(NULL, map_size, PROT_READ|PROT_WRITE, MAP_SHARED|MAP_ANONYMOUS, -1, 0);
747 20 ▶ if (base == MAP_FAILED) { HW_ERR("mmap: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { HW_ERR("mmap: %s", strerror(errno)); return NULL; } 0 20 20
if (base == MAP_FAILED) { HW_ERR("mmap: %s", strerror(errno)); return NULL; } 0 0 0
748 } else {
749 25 fd = hw_secure_open(path, mode, errbuf);
750 39 ▶ if (fd < 0) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (fd < 0) return NULL; 0 25 25
751 25 ▶ if (flock(fd, LOCK_EX) < 0) { HW_ERR("flock: %s", strerror(errno)); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (flock(fd, LOCK_EX) < 0) { HW_ERR("flock: %s", strerror(errno)); close(fd); return NULL; } 0 25 25
if (flock(fd, LOCK_EX) < 0) { HW_ERR("flock: %s", strerror(errno)); close(fd); return NULL; } 0 0 0
752 struct stat st;
753 25 ▶ if (fstat(fd, &st) < 0) { HW_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fstat(fd, &st) < 0) { HW_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; } 0 25 25
if (fstat(fd, &st) < 0) { HW_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; } 0 0 0
754 25 int is_new = (st.st_size == 0);
755 25 ▶ if (!is_new && (uint64_t)st.st_size < sizeof(HwHeader)) {
Branch: 2 branches
BranchTrueFalseTotal
if (!is_new && (uint64_t)st.st_size < sizeof(HwHeader)) { 14 11 25
if (!is_new && (uint64_t)st.st_size < sizeof(HwHeader)) { 1 13 14
756 1 ▶ HW_ERR("%s: file too small (%lld)", path, (long long)st.st_size);
Branch: 1 branch
BranchTrueFalseTotal
HW_ERR("%s: file too small (%lld)", path, (long long)st.st_size); 1 0 1
757 1 flock(fd, LOCK_UN); close(fd); return NULL;
758 }
759 24 ▶ 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)) { 11 13 24
if (is_new && (st.st_uid != geteuid() || fchmod(fd, mode) < 0)) { 11 0 11
if (is_new && (st.st_uid != geteuid() || fchmod(fd, mode) < 0)) { 0 11 11
760 0 ▶ HW_ERR("%s: refusing to initialize file not owned by us", path);
Branch: 1 branch
BranchTrueFalseTotal
HW_ERR("%s: refusing to initialize file not owned by us", path); 0 0 0
761 0 flock(fd, LOCK_UN); close(fd); return NULL;
762 }
763 24 ▶ if (is_new && ftruncate(fd, (off_t)total) < 0) {
Branch: 2 branches
BranchTrueFalseTotal
if (is_new && ftruncate(fd, (off_t)total) < 0) { 11 13 24
if (is_new && ftruncate(fd, (off_t)total) < 0) { 0 11 11
764 0 ▶ HW_ERR("ftruncate: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
HW_ERR("ftruncate: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; 0 0 0
765 }
766 24 ▶ if (is_new && hw_reserve(fd, total) < 0) {
Branch: 2 branches
BranchTrueFalseTotal
if (is_new && hw_reserve(fd, total) < 0) { 11 13 24
if (is_new && hw_reserve(fd, total) < 0) { 0 11 11
767 0 ▶ HW_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
HW_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno)); 0 0 0
768 0 if (ftruncate(fd, 0) < 0) { /* best effort */ }
769 0 flock(fd, LOCK_UN); close(fd); return NULL;
770 }
771 24 ▶ map_size = is_new ? (size_t)total : (size_t)st.st_size;
Branch: 1 branch
BranchTrueFalseTotal
map_size = is_new ? (size_t)total : (size_t)st.st_size; 13 11 24
772 24 base = mmap(NULL, map_size, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
773 24 ▶ if (base == MAP_FAILED) {
Branch: 1 branch
BranchTrueFalseTotal
if (base == MAP_FAILED) { 0 24 24
774 0 ▶ HW_ERR("mmap: %s", strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
HW_ERR("mmap: %s", strerror(errno)); 0 0 0
775 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
776 0 flock(fd, LOCK_UN); close(fd); return NULL;
777 }
778 24 ▶ if (!is_new) {
Branch: 1 branch
BranchTrueFalseTotal
if (!is_new) { 13 11 24
779 13 ▶ if (!hw_validate_header((HwHeader *)base, (uint64_t)st.st_size)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!hw_validate_header((HwHeader *)base, (uint64_t)st.st_size)) { 4 9 13
780 /* Recover an abandoned mid-init file: a creator killed
781 * between the ftruncate and the header init leaves a
782 * full-size, all-zero (magic==0) file that would brick every
783 * future open of this path. Re-initialize ONLY when it is
784 * exactly our size, still uninitialized, and owned by us;
785 * anything else still errors. */
786 4 ▶ if (((HwHeader *)base)->magic == 0 && (uint64_t)st.st_size == total
Branch: 2 branches
BranchTrueFalseTotal
if (((HwHeader *)base)->magic == 0 && (uint64_t)st.st_size == total 3 1 4
if (((HwHeader *)base)->magic == 0 && (uint64_t)st.st_size == total 2 1 3
787 2 ▶ && st.st_uid == geteuid() && hw_file_is_zero(fd, map_size)) {
Branch: 2 branches
BranchTrueFalseTotal
&& st.st_uid == geteuid() && hw_file_is_zero(fd, map_size)) { 2 0 2
&& st.st_uid == geteuid() && hw_file_is_zero(fd, map_size)) { 1 1 2
788 1 ▶ if (fchmod(fd, mode) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (fchmod(fd, mode) < 0) { 0 1 1
789 0 ▶ HW_ERR("%s: fchmod: %s", path, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
HW_ERR("%s: fchmod: %s", path, strerror(errno)); 0 0 0
790 0 munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
791 }
792 1 ▶ if (hw_reserve(fd, total) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (hw_reserve(fd, total) < 0) { 0 1 1
793 0 ▶ HW_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
HW_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno)); 0 0 0
794 0 munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
795 }
796 1 hw_init_header(base, (uint32_t)num_slots, (uint32_t)num_levels, (uint32_t)capacity, total);
797 1 flock(fd, LOCK_UN); close(fd);
798 1 return hw_setup(base, map_size, path, -1);
799 }
800 3 ▶ if (((HwHeader *)base)->magic == 0 && (uint64_t)st.st_size == total
Branch: 2 branches
BranchTrueFalseTotal
if (((HwHeader *)base)->magic == 0 && (uint64_t)st.st_size == total 2 1 3
if (((HwHeader *)base)->magic == 0 && (uint64_t)st.st_size == total 1 1 2
801 1 ▶ && st.st_uid == geteuid()) {
Branch: 1 branch
BranchTrueFalseTotal
&& st.st_uid == geteuid()) { 1 0 1
802 1 ▶ HW_ERR("%s: incomplete hierarchical timing-wheel file left by an interrupted create; remove it and retry", path);
Branch: 1 branch
BranchTrueFalseTotal
HW_ERR("%s: incomplete hierarchical timing-wheel file left by an interrupted create; remove it and retry", path); 1 0 1
803 1 munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
804 }
805 2 ▶ HW_ERR("invalid hierarchical timing-wheel file"); munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
HW_ERR("invalid hierarchical timing-wheel file"); munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL; 2 0 2
806 }
807 9 flock(fd, LOCK_UN); close(fd);
808 9 return hw_setup(base, map_size, path, -1);
809 }
810 }
811 31 hw_init_header(base, (uint32_t)num_slots, (uint32_t)num_levels, (uint32_t)capacity, total);
812 31 ▶ if (fd >= 0) { flock(fd, LOCK_UN); close(fd); }
Branch: 1 branch
BranchTrueFalseTotal
if (fd >= 0) { flock(fd, LOCK_UN); close(fd); } 11 20 31
813 31 return hw_setup(base, map_size, path, -1);
814 }
815  
816 9 static HwHandle *hw_create_memfd(const char *name, uint64_t num_slots, uint64_t num_levels, uint64_t capacity, char *errbuf) {
817 9 ▶ if (!hw_validate_args(num_slots, num_levels, capacity, errbuf)) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!hw_validate_args(num_slots, num_levels, capacity, errbuf)) return NULL; 0 9 9
818  
819 9 uint64_t total = hw_total_size((uint32_t)num_slots, (uint32_t)num_levels, (uint32_t)capacity);
820 9 ▶ int fd = memfd_create(name ? name : "hiertimingwheel", MFD_CLOEXEC | MFD_ALLOW_SEALING);
Branch: 1 branch
BranchTrueFalseTotal
int fd = memfd_create(name ? name : "hiertimingwheel", MFD_CLOEXEC | MFD_ALLOW_SEALING); 9 0 9
821 9 ▶ if (fd < 0) { HW_ERR("memfd_create: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fd < 0) { HW_ERR("memfd_create: %s", strerror(errno)); return NULL; } 0 9 9
if (fd < 0) { HW_ERR("memfd_create: %s", strerror(errno)); return NULL; } 0 0 0
822 9 ▶ if (ftruncate(fd, (off_t)total) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (ftruncate(fd, (off_t)total) < 0) { 0 9 9
823 0 ▶ HW_ERR("ftruncate: %s", strerror(errno)); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
HW_ERR("ftruncate: %s", strerror(errno)); close(fd); return NULL; 0 0 0
824 }
825 9 ▶ if (hw_reserve(fd, total) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (hw_reserve(fd, total) < 0) { 0 9 9
826 0 ▶ HW_ERR("memfd: cannot reserve %llu bytes: %s", (unsigned long long)total, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
HW_ERR("memfd: cannot reserve %llu bytes: %s", (unsigned long long)total, strerror(errno)); 0 0 0
827 0 close(fd); return NULL;
828 }
829 9 (void)fcntl(fd, F_ADD_SEALS, F_SEAL_SHRINK | F_SEAL_GROW);
830 9 void *base = mmap(NULL, (size_t)total, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
831 9 ▶ if (base == MAP_FAILED) { HW_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { HW_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; } 0 9 9
if (base == MAP_FAILED) { HW_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; } 0 0 0
832 9 hw_init_header(base, (uint32_t)num_slots, (uint32_t)num_levels, (uint32_t)capacity, total);
833 9 return hw_setup(base, (size_t)total, NULL, fd);
834 }
835  
836 8 static HwHandle *hw_open_fd(int fd, char *errbuf) {
837 8 ▶ if (errbuf) errbuf[0] = '\0';
Branch: 1 branch
BranchTrueFalseTotal
if (errbuf) errbuf[0] = '\0'; 8 0 8
838 struct stat st;
839 8 ▶ if (fstat(fd, &st) < 0) { HW_ERR("fstat: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fstat(fd, &st) < 0) { HW_ERR("fstat: %s", strerror(errno)); return NULL; } 0 8 8
if (fstat(fd, &st) < 0) { HW_ERR("fstat: %s", strerror(errno)); return NULL; } 0 0 0
840 8 ▶ if ((uint64_t)st.st_size < sizeof(HwHeader)) { HW_ERR("too small"); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if ((uint64_t)st.st_size < sizeof(HwHeader)) { HW_ERR("too small"); return NULL; } 0 8 8
if ((uint64_t)st.st_size < sizeof(HwHeader)) { HW_ERR("too small"); return NULL; } 0 0 0
841 /* before mmap: a creator may truncate the file until it has set magic */
842 uint32_t magic;
843 8 ▶ if (pread(fd, &magic, sizeof magic, offsetof(HwHeader, magic)) != (ssize_t)sizeof magic || magic != HW_MAGIC) {
Branch: 2 branches
BranchTrueFalseTotal
if (pread(fd, &magic, sizeof magic, offsetof(HwHeader, magic)) != (ssize_t)sizeof magic || magic != HW_MAGIC) { 8 0 8
if (pread(fd, &magic, sizeof magic, offsetof(HwHeader, magic)) != (ssize_t)sizeof magic || magic != HW_MAGIC) { 0 8 8
844 0 ▶ HW_ERR("invalid hierarchical timing-wheel table"); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
HW_ERR("invalid hierarchical timing-wheel table"); return NULL; 0 0 0
845 }
846 8 size_t ms = (size_t)st.st_size;
847 8 void *base = mmap(NULL, ms, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
848 8 ▶ if (base == MAP_FAILED) { HW_ERR("mmap: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { HW_ERR("mmap: %s", strerror(errno)); return NULL; } 0 8 8
if (base == MAP_FAILED) { HW_ERR("mmap: %s", strerror(errno)); return NULL; } 0 0 0
849 8 ▶ if (!hw_validate_header((HwHeader *)base, (uint64_t)st.st_size)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!hw_validate_header((HwHeader *)base, (uint64_t)st.st_size)) { 0 8 8
850 0 ▶ HW_ERR("invalid hierarchical timing-wheel table"); munmap(base, ms); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
HW_ERR("invalid hierarchical timing-wheel table"); munmap(base, ms); return NULL; 0 0 0
851 }
852 8 int myfd = fcntl(fd, F_DUPFD_CLOEXEC, 0);
853 8 ▶ if (myfd < 0) { HW_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (myfd < 0) { HW_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; } 0 8 8
if (myfd < 0) { HW_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; } 0 0 0
854 8 return hw_setup(base, ms, NULL, myfd);
855 }
856  
857 58 static void hw_destroy(HwHandle *h) {
858 58 ▶ if (!h) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!h) return; 0 58 58
859 /* Release our reader slot on clean teardown (else short-lived-reader churn
860 * exhausts the slot table); skip if a read lock is still held (rdepth>0). */
861 58 ▶ if (h->reader_slots && h->my_slot_idx != UINT32_MAX && h->cached_pid &&
Branch: 3 branches
BranchTrueFalseTotal
if (h->reader_slots && h->my_slot_idx != UINT32_MAX && h->cached_pid && 58 0 58
if (h->reader_slots && h->my_slot_idx != UINT32_MAX && h->cached_pid && 56 2 58
if (h->reader_slots && h->my_slot_idx != UINT32_MAX && h->cached_pid && 56 0 56
862 56 ▶ h->cached_fork_gen == __atomic_load_n(&hw_fork_gen, __ATOMIC_RELAXED) &&
Branch: 1 branch
BranchTrueFalseTotal
h->cached_fork_gen == __atomic_load_n(&hw_fork_gen, __ATOMIC_RELAXED) && 56 0 56
863 56 ▶ __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) { 56 0 56
864 /* Clear our occ bit BEFORE freeing the slot: we still own the pid so no
865 * claimant can take the slot mid-clear, and rdepth==0 so no writer needs
866 * to see us. (A crash skips this -> the bit is reclaimed lazily by a
867 * writer scan / re-claim, same as the pid.) */
868 56 hw_occ_clear(h, h->my_slot_idx);
869 56 uint32_t expected = h->cached_pid;
870 56 __atomic_compare_exchange_n(&h->reader_slots[h->my_slot_idx].pid,
871 &expected, 0, 0, __ATOMIC_RELEASE, __ATOMIC_RELAXED);
872 }
873 58 ▶ if (h->backing_fd >= 0) close(h->backing_fd);
Branch: 1 branch
BranchTrueFalseTotal
if (h->backing_fd >= 0) close(h->backing_fd); 17 41 58
874 58 ▶ if (h->base) munmap(h->base, h->mmap_size);
Branch: 1 branch
BranchTrueFalseTotal
if (h->base) munmap(h->base, h->mmap_size); 58 0 58
875 58 free(h->path);
876 58 free(h);
877 }
878  
879 2 static inline int hw_msync(HwHandle *h) {
880 2 ▶ if (!h || !h->base) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (!h || !h->base) return 0; 2 0 2
if (!h || !h->base) return 0; 0 2 2
881 2 return msync(h->base, h->mmap_size, MS_SYNC);
882 }
883  
884 /* ================================================================
885 * Hierarchical timing-wheel operations (callers hold the lock)
886 *
887 * num_levels cascading wheels of num_slots (=S) buckets each; a level-k slot
888 * spans tick[k]=S^k ticks, so the whole structure schedules any delay in
889 * [1, S^num_levels). A timer stores its absolute expiry; it is placed in the
890 * lowest level whose range covers its remaining delay, at slot (expiry/tick[k])%S.
891 * On each tick level 0 fires its current slot; when level 0 wraps, the next
892 * level's now-current slot cascades down -- its timers are re-binned into finer
893 * levels by remaining delay -- recursively up the levels. Timers live in a fixed
894 * pool with a free list; each bucket is a doubly-linked list (prev/next) so
895 * cancellation is O(1). Every timer index and bucket index read from shared
896 * memory is bounds checked, so a corrupt link can never drive an OOB access.
897 * ================================================================ */
898  
899 /* unlink timer `t` from its current bucket's doubly-linked list */
900 8033 static void hw_unlink(HwHandle *h, uint32_t t) {
901 8033 HwTimer *tm = hw_timer(h, t);
902 8033 uint32_t pv = tm->prev, nx = tm->next;
903 8033 ▶ if (HW_TIMER_OK(h, pv)) hw_timer(h, pv)->next = nx;
Branch: 2 branches
BranchTrueFalseTotal
if (HW_TIMER_OK(h, pv)) hw_timer(h, pv)->next = nx; 1360 6673 8033
if (HW_TIMER_OK(h, pv)) hw_timer(h, pv)->next = nx; 1360 0 1360
904 6673 ▶ else if (HW_BUCKET_OK(h, tm->bucket)) hw_slots(h)[tm->bucket] = nx; /* t was the head */
Branch: 2 branches
BranchTrueFalseTotal
else if (HW_BUCKET_OK(h, tm->bucket)) hw_slots(h)[tm->bucket] = nx; /* t was the head */ 6673 0 6673
else if (HW_BUCKET_OK(h, tm->bucket)) hw_slots(h)[tm->bucket] = nx; /* t was the head */ 6673 0 6673
905 8033 ▶ if (HW_TIMER_OK(h, nx)) hw_timer(h, nx)->prev = pv;
Branch: 2 branches
BranchTrueFalseTotal
if (HW_TIMER_OK(h, nx)) hw_timer(h, nx)->prev = pv; 2126 5907 8033
if (HW_TIMER_OK(h, nx)) hw_timer(h, nx)->prev = pv; 2126 0 2126
906 8033 }
907  
908 /* return timer `t` to the free list (caller has already unlinked it) */
909 8033 static void hw_free(HwHandle *h, uint32_t t) {
910 8033 HwTimer *tm = hw_timer(h, t);
911 8033 tm->state &= ~1u; /* clear active bit; keep generation so the next reuse of this slot gets a fresh one */
912 8033 tm->prev = HW_NIL;
913 8033 tm->bucket = HW_NIL;
914 8033 tm->next = h->hdr->free_head;
915 8033 __atomic_signal_fence(__ATOMIC_SEQ_CST);
916 8033 h->hdr->free_head = t;
917 8033 }
918  
919 /* link an already-populated timer `t` into flat bucket `b` (prepend) */
920 17279 static void hw_link(HwHandle *h, uint32_t t, uint64_t b) {
921 17279 HwTimer *tm = hw_timer(h, t);
922 17279 tm->bucket = (uint32_t)b;
923 17279 tm->prev = HW_NIL;
924 17279 uint32_t head = hw_slots(h)[b];
925 17279 tm->next = head;
926 17279 hw_slots(h)[b] = t;
927 17279 ▶ if (HW_TIMER_OK(h, head)) hw_timer(h, head)->prev = t;
Branch: 2 branches
BranchTrueFalseTotal
if (HW_TIMER_OK(h, head)) hw_timer(h, head)->prev = t; 6137 11142 17279
if (HW_TIMER_OK(h, head)) hw_timer(h, head)->prev = t; 6137 0 6137
928 17279 }
929  
930 /* choose the flat bucket for a timer whose absolute expiry is E, given the
931 * current time now: the lowest level k with (E-now) < tick[k+1], slot
932 * (E/tick[k])%S. A remaining delay of 0 lands in level 0's current slot. */
933 17279 static uint64_t hw_bucket_for(HwHandle *h, uint64_t E, uint64_t now) {
934 17279 ▶ uint64_t delay = (E > now) ? E - now : 0;
Branch: 1 branch
BranchTrueFalseTotal
uint64_t delay = (E > now) ? E - now : 0; 16426 853 17279
935 17279 uint32_t S = h->num_slots, L = h->num_levels, k = 0;
936 48113 ▶ while (k + 1 < L && delay >= h->tick[k + 1]) k++; /* lowest level covering `delay` */
Branch: 2 branches
BranchTrueFalseTotal
while (k + 1 < L && delay >= h->tick[k + 1]) k++; /* lowest level covering `delay` */ 39384 8729 48113
while (k + 1 < L && delay >= h->tick[k + 1]) k++; /* lowest level covering `delay` */ 30834 8550 39384
937 17279 uint64_t slot = (E / h->tick[k]) % S;
938 17279 return (uint64_t)k * S + slot; /* flat bucket index */
939 }
940  
941 /* schedule a timer to fire in `delay` ticks (>= 1); returns its id, or -1 if the
942 * pool is full or the delay exceeds the wheel's range. (caller holds wrlock) */
943 10557 static int64_t hw_add_locked(HwHandle *h, uint64_t delay, uint64_t payload) {
944 10557 ▶ if (h->num_slots == 0 || h->num_levels == 0 || h->capacity == 0) return -1;
Branch: 3 branches
BranchTrueFalseTotal
if (h->num_slots == 0 || h->num_levels == 0 || h->capacity == 0) return -1; 10557 0 10557
if (h->num_slots == 0 || h->num_levels == 0 || h->capacity == 0) return -1; 10557 0 10557
if (h->num_slots == 0 || h->num_levels == 0 || h->capacity == 0) return -1; 0 10557 10557
945 10557 ▶ if (delay < 1) delay = 1; /* minimum effective delay is one tick */
Branch: 1 branch
BranchTrueFalseTotal
if (delay < 1) delay = 1; /* minimum effective delay is one tick */ 829 9728 10557
946 10557 ▶ if (delay >= h->tick[h->num_levels]) return -2; /* beyond S^num_levels: not schedulable */
Branch: 1 branch
BranchTrueFalseTotal
if (delay >= h->tick[h->num_levels]) return -2; /* beyond S^num_levels: not schedulable */ 5 10552 10557
947 10552 uint32_t t = h->hdr->free_head;
948 10552 ▶ if (!HW_TIMER_OK(h, t)) return -1; /* full (or corrupt free head) */
Branch: 2 branches
BranchTrueFalseTotal
if (!HW_TIMER_OK(h, t)) return -1; /* full (or corrupt free head) */ 10469 83 10552
if (!HW_TIMER_OK(h, t)) return -1; /* full (or corrupt free head) */ 0 10469 10469
949 10469 ▶ if (hw_timer(h, t)->state & 1u) return -1; /* Layer B: free head points at an active timer */
Branch: 1 branch
BranchTrueFalseTotal
if (hw_timer(h, t)->state & 1u) return -1; /* Layer B: free head points at an active timer */ 0 10469 10469
950 10469 h->hdr->free_head = hw_timer(h, t)->next; /* pop the free list */
951  
952 10469 uint64_t now = h->hdr->now, E = now + delay;
953 10469 HwTimer *tm = hw_timer(h, t);
954 10469 tm->payload = payload;
955 10469 tm->expiry = E;
956 10469 uint32_t gen = (tm->state + 2u) >> 1; /* bump within the 31-bit generation */
957 /* Recovery re-bins every active timer by its expiry. */
958 10469 __atomic_signal_fence(__ATOMIC_SEQ_CST);
959 10469 tm->state = (gen << 1) | 1u; /* low bit = active, upper bits = generation */
960 10469 hw_link(h, t, hw_bucket_for(h, E, now));
961 10469 h->hdr->count++;
962 10469 return ((int64_t)gen << 32) | (int64_t)t; /* id encodes the generation so cancel() can reject a reused slot */
963 }
964  
965 /* cancel timer `t`; returns 1 if it was active and is now removed, else 0.
966 * (caller holds the write lock) */
967 24597 static int hw_cancel_locked(HwHandle *h, uint64_t id) {
968 24597 uint32_t idx = (uint32_t)(id & 0xFFFFFFFFu);
969 24597 uint32_t gen = (uint32_t)((id >> 32) & 0x7FFFFFFFu);
970 24597 ▶ if (!HW_TIMER_OK(h, idx)) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (!HW_TIMER_OK(h, idx)) return 0; 24597 0 24597
if (!HW_TIMER_OK(h, idx)) return 0; 1 24596 24597
971 24596 HwTimer *tm = hw_timer(h, idx);
972 24596 ▶ if (!(tm->state & 1u)) return 0; /* free / already fired */
Branch: 1 branch
BranchTrueFalseTotal
if (!(tm->state & 1u)) return 0; /* free / already fired */ 10467 14129 24596
973 14129 ▶ if ((tm->state >> 1) != gen) return 0; /* stale id: this slot was reused by a later timer */
Branch: 1 branch
BranchTrueFalseTotal
if ((tm->state >> 1) != gen) return 0; /* stale id: this slot was reused by a later timer */ 10468 3661 14129
974 3661 hw_unlink(h, idx);
975 3661 hw_free(h, idx);
976 3661 ▶ if (h->hdr->count) h->hdr->count--;
Branch: 1 branch
BranchTrueFalseTotal
if (h->hdr->count) h->hdr->count--; 3661 0 3661
977 3661 return 1;
978 }
979  
980 /* re-bin every timer in level-k's now-current bucket into a finer level (called
981 * when `now` has just reached a multiple of tick[k]). If level k also wrapped,
982 * cascade level k+1 first (top-down) so higher levels feed into this one. */
983 38113 static void hw_cascade(HwHandle *h, uint32_t k, uint64_t now) {
984 38113 uint32_t S = h->num_slots;
985 38113 uint64_t slot = (now / h->tick[k]) % S;
986 38113 ▶ if (slot == 0 && k + 1 < h->num_levels) hw_cascade(h, k + 1, now); /* level k wrapped too */
Branch: 2 branches
BranchTrueFalseTotal
if (slot == 0 && k + 1 < h->num_levels) hw_cascade(h, k + 1, now); /* level k wrapped too */ 13797 24316 38113
if (slot == 0 && k + 1 < h->num_levels) hw_cascade(h, k + 1, now); /* level k wrapped too */ 12857 940 13797
987 38113 uint64_t b = (uint64_t)k * S + slot;
988 38113 uint32_t t = hw_slots(h)[b];
989 38113 hw_slots(h)[b] = HW_NIL; /* detach the whole list */
990 38113 uint64_t guard = 0;
991 44923 ▶ while (HW_TIMER_OK(h, t) && guard++ <= (uint64_t)h->capacity) {
Branch: 3 branches
BranchTrueFalseTotal
while (HW_TIMER_OK(h, t) && guard++ <= (uint64_t)h->capacity) { 6810 38113 44923
while (HW_TIMER_OK(h, t) && guard++ <= (uint64_t)h->capacity) { 6810 0 6810
while (HW_TIMER_OK(h, t) && guard++ <= (uint64_t)h->capacity) { 6810 0 6810
992 6810 HwTimer *tm = hw_timer(h, t);
993 6810 uint32_t nx = tm->next;
994 6810 ▶ if (tm->state & 1u) /* re-insert into a lower level (or level-0 current slot) */
Branch: 1 branch
BranchTrueFalseTotal
if (tm->state & 1u) /* re-insert into a lower level (or level-0 current slot) */ 6810 0 6810
995 6810 hw_link(h, t, hw_bucket_for(h, tm->expiry, now));
996 6810 t = nx;
997 }
998 38113 }
999  
1000 /* advance the wheel by `ticks`, collecting fired payloads into out[] (capped at
1001 * out_cap); returns the number fired. (caller holds the write lock) */
1002 7435 static uint64_t hw_advance_locked(HwHandle *h, uint64_t ticks, uint64_t *out, uint64_t out_cap) {
1003 7435 uint64_t fired = 0;
1004 7435 uint32_t S = h->num_slots;
1005 7435 ▶ if (S == 0 || h->num_levels == 0) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (S == 0 || h->num_levels == 0) return 0; 7435 0 7435
if (S == 0 || h->num_levels == 0) return 0; 0 7435 7435
1006 181901 ▶ for (uint64_t j = 0; j < ticks; j++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint64_t j = 0; j < ticks; j++) { 174466 7435 181901
1007 174466 uint64_t now = h->hdr->now + 1;
1008 174466 ▶ if (now % S == 0 && h->num_levels > 1) /* level 0 wrapped -> cascade higher levels down */
Branch: 2 branches
BranchTrueFalseTotal
if (now % S == 0 && h->num_levels > 1) /* level 0 wrapped -> cascade higher levels down */ 35693 138773 174466
if (now % S == 0 && h->num_levels > 1) /* level 0 wrapped -> cascade higher levels down */ 25256 10437 35693
1009 25256 hw_cascade(h, 1, now);
1010 174466 uint64_t b = now % S; /* level-0 current slot (tick[0]==1) */
1011 174466 uint32_t t = hw_slots(h)[b];
1012 174466 uint64_t guard = 0;
1013 178838 ▶ while (HW_TIMER_OK(h, t) && guard++ <= (uint64_t)h->capacity) {
Branch: 3 branches
BranchTrueFalseTotal
while (HW_TIMER_OK(h, t) && guard++ <= (uint64_t)h->capacity) { 4372 174466 178838
while (HW_TIMER_OK(h, t) && guard++ <= (uint64_t)h->capacity) { 4372 0 4372
while (HW_TIMER_OK(h, t) && guard++ <= (uint64_t)h->capacity) { 4372 0 4372
1014 4372 HwTimer *tm = hw_timer(h, t);
1015 4372 ▶ if (!(tm->state & 1u)) break; /* Layer B: corrupt link into a freed node */
Branch: 1 branch
BranchTrueFalseTotal
if (!(tm->state & 1u)) break; /* Layer B: corrupt link into a freed node */ 0 4372 4372
1016 4372 uint32_t nx = tm->next;
1017 4372 hw_unlink(h, t); /* every timer in level-0's current slot is due now */
1018 4372 hw_free(h, t);
1019 4372 ▶ if (h->hdr->count) h->hdr->count--;
Branch: 1 branch
BranchTrueFalseTotal
if (h->hdr->count) h->hdr->count--; 4372 0 4372
1020 4372 ▶ if (fired < out_cap) out[fired++] = tm->payload; /* cap BOTH the write and the count */
Branch: 1 branch
BranchTrueFalseTotal
if (fired < out_cap) out[fired++] = tm->payload; /* cap BOTH the write and the count */ 4372 0 4372
1021 4372 t = nx;
1022 }
1023 /* The tick is done only once it has fired; a writer killed before this has it rerun. */
1024 174466 __atomic_signal_fence(__ATOMIC_SEQ_CST);
1025 174466 h->hdr->now = now;
1026 }
1027 7435 return fired;
1028 }
1029  
1030 /* reset to an empty wheel: rethread the free list, clear the buckets, reset time.
1031 * (caller holds the write lock) */
1032 172 static inline uint64_t hw_buckets_max(HwHandle *h) {
1033 172 uint64_t nb = hw_num_bucket(h);
1034 172 ▶ uint64_t smax = (h->slots_off < h->mmap_size) ? (h->mmap_size - h->slots_off) / sizeof(uint32_t) : 0;
Branch: 1 branch
BranchTrueFalseTotal
uint64_t smax = (h->slots_off < h->mmap_size) ? (h->mmap_size - h->slots_off) / sizeof(uint32_t) : 0; 172 0 172
1035 172 return nb > smax ? smax : nb; /* Layer B */
1036 }
1037  
1038 172 static inline void hw_clear_locked(HwHandle *h) {
1039 172 h->hdr->op = HW_OP_CLEAR;
1040 172 __atomic_signal_fence(__ATOMIC_SEQ_CST);
1041 172 uint64_t nb = hw_buckets_max(h), cap = h->capacity;
1042 172 uint64_t tmax = hw_timers_max(h);
1043 172 ▶ if (cap > tmax) cap = tmax;
Branch: 1 branch
BranchTrueFalseTotal
if (cap > tmax) cap = tmax; 0 172 172
1044 172 uint32_t *slots = hw_slots(h);
1045 8188 ▶ for (uint64_t s = 0; s < nb; s++) slots[s] = HW_NIL;
Branch: 1 branch
BranchTrueFalseTotal
for (uint64_t s = 0; s < nb; s++) slots[s] = HW_NIL; 8016 172 8188
1046 11216 ▶ for (uint64_t i = 0; i < cap; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint64_t i = 0; i < cap; i++) { 11044 172 11216
1047 11044 HwTimer *tm = hw_timer(h, i);
1048 11044 ▶ tm->next = (i + 1 < cap) ? (uint32_t)(i + 1) : HW_NIL;
Branch: 1 branch
BranchTrueFalseTotal
tm->next = (i + 1 < cap) ? (uint32_t)(i + 1) : HW_NIL; 10872 172 11044
1049 11044 tm->prev = HW_NIL;
1050 11044 tm->bucket = HW_NIL;
1051 11044 tm->state &= ~1u; /* clear active bit; keep generation so ids from before clear() stay distinguishable (no clear-then-reuse ABA) */
1052 }
1053 172 h->hdr->now = 0;
1054 172 h->hdr->count = 0;
1055 172 ▶ h->hdr->free_head = cap ? 0 : HW_NIL;
Branch: 1 branch
BranchTrueFalseTotal
h->hdr->free_head = cap ? 0 : HW_NIL; 172 0 172
1056 172 __atomic_signal_fence(__ATOMIC_SEQ_CST);
1057 172 h->hdr->op = 0;
1058 172 }
1059  
1060 /* A clear killed part-way left its op word set: run it again from scratch.
1061 * Otherwise an add, cancel, cascade or tick may have left links half made or a
1062 * bucket detached: re-bin every active timer by its expiry, put every other one
1063 * on the free list, and recount. Idempotent. */
1064 0 static void hw_repair_locked(HwHandle *h) {
1065 0 HwHeader *hdr = h->hdr;
1066 0 ▶ if (hdr->op == HW_OP_CLEAR) { hw_clear_locked(h); return; }
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->op == HW_OP_CLEAR) { hw_clear_locked(h); return; } 0 0 0
1067 0 uint64_t nb = hw_buckets_max(h), cap = h->capacity, count = 0, now = hdr->now;
1068 0 uint64_t tmax = hw_timers_max(h);
1069 0 ▶ if (cap > tmax) cap = tmax;
Branch: 1 branch
BranchTrueFalseTotal
if (cap > tmax) cap = tmax; 0 0 0
1070 0 ▶ if (nb < hw_num_bucket(h)) return;
Branch: 1 branch
BranchTrueFalseTotal
if (nb < hw_num_bucket(h)) return; 0 0 0
1071 0 uint32_t *slots = hw_slots(h), free_head = HW_NIL;
1072 0 ▶ for (uint64_t b = 0; b < nb; b++) slots[b] = HW_NIL;
Branch: 1 branch
BranchTrueFalseTotal
for (uint64_t b = 0; b < nb; b++) slots[b] = HW_NIL; 0 0 0
1073 0 ▶ for (uint64_t i = cap; i-- > 0; ) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint64_t i = cap; i-- > 0; ) { 0 0 0
1074 0 HwTimer *tm = hw_timer(h, i);
1075 0 ▶ if (tm->state & 1u) {
Branch: 1 branch
BranchTrueFalseTotal
if (tm->state & 1u) { 0 0 0
1076 0 ▶ hw_link(h, (uint32_t)i, hw_bucket_for(h, tm->expiry > now ? tm->expiry : now + 1, now));
Branch: 1 branch
BranchTrueFalseTotal
hw_link(h, (uint32_t)i, hw_bucket_for(h, tm->expiry > now ? tm->expiry : now + 1, now)); 0 0 0
1077 0 count++;
1078 } else {
1079 0 tm->prev = HW_NIL;
1080 0 tm->bucket = HW_NIL;
1081 0 tm->next = free_head;
1082 0 free_head = (uint32_t)i;
1083 }
1084 }
1085 0 hdr->free_head = free_head;
1086 0 hdr->count = count;
1087 }
1088  
1089 #endif /* HW_H */
« blib/lib/Data/HierTimingWheel/Shared.pm ↑ Summary Shared.xs »