timingwheel.h

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