segtree.h

filter: Statementstmt 69.8% 450 / 644 Branchbran 50.5% 277 / 548 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 60.9% 727 / 1192 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« blib/lib/Data/SegmentTree/Shared.pm ↑ Summary Shared.xs »
1 /*
2 * segtree.h -- Shared-memory segment tree for Linux
3 *
4 * Range queries with range updates over a fixed array of n signed-integer
5 * positions: add a delta to every element of a range in O(log n), and query the
6 * sum, minimum, or maximum of any range in O(log n). A perfect binary tree with
7 * lazy propagation carries each node's sum/min/max plus a pending range-add; the
8 * tree lives in a shared mapping so several processes update and query one array.
9 * A write-preferring futex rwlock with reader-slot dead-process recovery guards
10 * mutation; queries never mutate, so they take only the read lock.
11 *
12 * Layout: Header -> reader_slots[1024] -> occ bitmap -> nodes[2*next_pow2(n)]
13 */
14  
15 #ifndef ST_H
16 #define ST_H
17  
18 #include <stddef.h>
19 #include <stdint.h>
20 #include <stdlib.h>
21 #include <string.h>
22 #include <unistd.h>
23 #include <fcntl.h>
24 #include <errno.h>
25 #include <time.h>
26 #include <limits.h>
27 #include <signal.h>
28 #include <stdio.h>
29 #include <math.h>
30 #include <sys/mman.h>
31 #include <sys/stat.h>
32 #include <sys/file.h>
33 #include <sys/syscall.h>
34 #include <linux/futex.h>
35 #include <pthread.h>
36  
37 #if defined(__BYTE_ORDER__) && __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
38 #error "segtree.h: requires little-endian architecture"
39 #endif
40  
41  
42 /* ================================================================
43 * Constants
44 * ================================================================ */
45  
46 #define ST_MAGIC 0x54474553 /* SegmentTree */
47 #define ST_VERSION 3 /* 3: added the occupancy bitmap region (layout change) */
48 #define ST_ERR_BUFLEN (PATH_MAX + 256)
49 #ifndef ST_READER_SLOTS
50 #define ST_READER_SLOTS 1024 /* max concurrent reader processes for dead-process recovery */
51 #endif
52 /* Occupancy bitmap: one bit per reader slot; lets a writer scan only claimed
53 * slots (O(words + live readers)) instead of all ST_READER_SLOTS. */
54 #define ST_OCC_WORDS (((ST_READER_SLOTS) + 63) / 64) /* 16 for 1024 slots */
55 #define ST_OCC_BYTES ((uint64_t)ST_OCC_WORDS * 8) /* 128 bytes */
56 #define ST_MIN_N 1
57 #define ST_MAX_N 0x1000000ULL /* 2^24 positions cap */
58 #define ST_IDENTITY_MIN INT64_MAX /* min identity (padding leaves / empty range) */
59 #define ST_IDENTITY_MAX INT64_MIN /* max identity */
60  
61 /* StNode.flags bits */
62 #define ST_F_HAS_ASSIGN 0x1U /* node has a pending range-assign (lazy) */
63 #define ST_F_PROD_OVF 0x2U /* node's product overflowed int64 (unusable) */
64  
65 #define ST_ERR(fmt, ...) do { if (errbuf) snprintf(errbuf, ST_ERR_BUFLEN, fmt, ##__VA_ARGS__); } while (0)
66  
67 /* ================================================================
68 * Structs
69 * ================================================================ */
70  
71 /* Per-process slot for dead-process recovery. A reader's ENTIRE lock
72 * contribution is `rdepth` in its OWN slot -- with no separate shared counter,
73 * a draining writer neutralises a dead reader by clearing its slot's pid, so
74 * no orphaned counter can strand and sustained readers cannot starve a writer.
75 * _rsv1/_rsv2 kept only for the 16-byte slot size across released builds. */
76 typedef struct {
77 uint32_t pid; /* 0 = unclaimed */
78 uint32_t rdepth; /* read-locks THIS process currently holds (recursion-safe) */
79 uint32_t _rsv1; /* reserved (was waiters_parked); unused, kept for layout size */
80 uint32_t _rsv2; /* reserved (was writers_parked); unused, kept for layout size */
81 } StReaderSlot;
82  
83 struct StHeader {
84 uint32_t magic, version; /* 0,4 */
85 uint32_t add_used; /* 8 set once any range_add runs -> gcd/product gated off */
86 uint32_t _pad1; /* 12 */
87 uint64_t n; /* 16 number of positions (leaves in use) */
88 uint64_t size; /* 24 next_pow2(n): leaves in the padded tree */
89 uint64_t nodes_off; /* 32 offset of the node array (2*size StNodes) */
90 uint64_t total_size; /* 40 */
91 uint64_t reader_slots_off; /* 48 */
92 uint32_t wlock; /* 56 WRITER word ONLY: 0 (free) or WRITER_BIT|pid. NOT a reader count. */
93 uint32_t rwait; /* 60 parked-waiter hint (readers+writers blocked on wlock); over-count-safe */
94 uint32_t drain_seq; /* 64 futex bumped by a reader releasing under a draining writer (wakes it) */
95 uint32_t slotless_rdepth; /* readers holding with no reader-slot (documented residual) */
96 uint64_t stat_ops; /* 72 */
97 /* A push-down of an add in flight, replayed by recovery (carved from the pad,
98 * so older files read 0: none). */
99 uint64_t pd_node; /* 80 the node pushing, 0 for none */
100 int64_t pd_delta; /* 88 its add */
101 int64_t pd_tag[2]; /* 96 its children's add tags once pushed */
102 uint8_t _pad[144]; /* 112..255 */
103 };
104 typedef struct StHeader StHeader;
105  
106 _Static_assert(sizeof(StHeader) == 256, "StHeader must be 256 bytes");
107  
108 /* One segment-tree node: the sum/min/max/gcd/product aggregate of its covered
109 * range, plus pending lazies -- a "range add" delta (lazy) and/or a "range
110 * assign" value (assign, active when flags has ST_F_HAS_ASSIGN). A node's own
111 * aggregate already includes its own lazies; only its children are stale by them.
112 * gcd/product are exact only while no range_add has ever run (see add_used); an
113 * assigned node stores product as c^cnt, or sets ST_F_PROD_OVF if that overflows. */
114 typedef struct {
115 int64_t sum;
116 int64_t min;
117 int64_t max;
118 int64_t gcd; /* gcd of |values| in the range (0 identity); valid iff !add_used */
119 int64_t prod; /* product of the range (1 identity); unusable if ST_F_PROD_OVF */
120 int64_t lazy; /* pending range-add delta (used only when !ST_F_HAS_ASSIGN) */
121 int64_t assign; /* pending range-assign value (used when ST_F_HAS_ASSIGN) */
122 uint64_t flags; /* ST_F_HAS_ASSIGN | ST_F_PROD_OVF */
123 } StNode;
124 _Static_assert(sizeof(StNode) == 64, "StNode must be 64 bytes");
125  
126 /* ---- Process-local handle ---- */
127  
128 typedef struct StHandle {
129 StHeader *hdr;
130 StReaderSlot *reader_slots; /* ST_READER_SLOTS entries */
131 uint64_t *occ; /* ST_OCC_WORDS-word slot-occupancy bitmap (trusted layout offset) */
132 void *base; /* mmap base */
133 uint64_t nodes_off; /* validated, cached: never re-read from the peer-writable header */
134 uint64_t n; /* cached number of positions */
135 uint64_t size; /* cached next_pow2(n) */
136 size_t mmap_size;
137 char *path; /* backing file path (strdup'd) */
138 char *unlink_path; /* absolute path for relative backing files */
139 int backing_fd; /* memfd or reopened-fd to close on destroy, -1 for file/anon */
140 uint32_t my_slot_idx; /* UINT32_MAX if all slots taken (no recovery for this handle) */
141 uint32_t cached_pid; /* getpid() cached at last slot claim */
142 uint32_t cached_fork_gen; /* st_fork_gen value at last slot claim */
143 uint32_t slotless_held; /* read-locks this process holds with no reader-slot */
144 } StHandle;
145  
146 /* ================================================================
147 * Futex-based write-preferring read-write lock (reader-slots-only)
148 * with dead-process recovery
149 *
150 * The reader count is NOT stored in a shared counter. It is DISTRIBUTED across
151 * per-process reader slots: each slot's `rdepth` is that process's entire
152 * contribution to the lock. A reader publishes its presence in its own slot and
153 * then re-checks the writer word; a writer publishes the writer word and then
154 * scans every slot until all live readers' rdepth reach 0. Sequentially-
155 * consistent store+load on each side (a Dekker handshake) gives mutual exclusion.
156 *
157 * Because a reader's whole contribution is ONE atomic word owned by ONE process,
158 * a crashed reader is recovered by clearing that one slot (CAS its pid to 0) --
159 * there is no second counter to strand, no orphaned +1, and therefore no
160 * quiescent force-reset. A reader killed anywhere in rdlock/rdunlock leaves at
161 * most `rdepth>0` in its dead slot, which the draining writer clears directly, so
162 * sustained read traffic can never starve a writer. Write-preference is inherent
163 * in the gate (new readers see wlock!=0 and yield), so there is no reader-count
164 * yield hack.
165 * ================================================================ */
166  
167 #define ST_RWLOCK_SPIN_LIMIT 32
168 #define ST_LOCK_TIMEOUT_SEC 2 /* FUTEX_WAIT timeout for stale-lock detection / drain re-scan */
169  
170 0 static inline void st_rwlock_spin_pause(void) {
171 #if defined(__x86_64__) || defined(__i386__)
172 0 __asm__ volatile("pause" ::: "memory");
173 #elif defined(__aarch64__)
174 __asm__ volatile("yield" ::: "memory");
175 #else
176 __asm__ volatile("" ::: "memory");
177 #endif
178 0 }
179  
180 /* Writer word encoding: WRITER_BIT|pid when write-locked, 0 when free. */
181 #define ST_RWLOCK_WRITER_BIT 0x80000000U
182 #define ST_RWLOCK_PID_MASK 0x7FFFFFFFU
183 #define ST_RWLOCK_WR(pid) (ST_RWLOCK_WRITER_BIT | ((uint32_t)(pid) & ST_RWLOCK_PID_MASK))
184  
185 /* A zombie (dead, unreaped) still answers kill(pid,0) as alive, so a crashed
186 * lock-holder that lingers unreaped would never be recovered. Treat
187 * /proc/<pid>/stat state 'Z' as dead. Linux-only; if /proc is unreadable,
188 * fall back to "alive" (never force-recover a possibly-live holder). */
189 0 static inline int st_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 st_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 !st_pid_is_zombie(pid); /* kill() also succeeds for a zombie -> treat as dead */
210 }
211  
212 static const struct timespec st_lock_timeout = { ST_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 st_fork_gen = 1;
218 static pthread_once_t st_atfork_once = PTHREAD_ONCE_INIT;
219 0 static void st_on_fork_child(void) {
220 0 __atomic_add_fetch(&st_fork_gen, 1, __ATOMIC_RELAXED);
221 0 }
222 4 static void st_atfork_init(void) {
223 4 pthread_atfork(NULL, NULL, st_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 30 static inline void st_occ_set(StHandle *h, uint32_t s) {
231 30 __atomic_fetch_or(&h->occ[s >> 6], (uint64_t)1 << (s & 63), __ATOMIC_SEQ_CST);
232 30 }
233 30 static inline void st_occ_clear(StHandle *h, uint32_t s) {
234 30 __atomic_fetch_and(&h->occ[s >> 6], ~((uint64_t)1 << (s & 63)), __ATOMIC_SEQ_CST);
235 30 }
236  
237 static inline void st_reader_wake_drain(StHandle *h);
238  
239 /* Ensure this process owns a reader slot. Called from the lock helpers so that
240 * fork()'d children pick up their own slot lazily instead of sharing the
241 * parent's. Hot-path is a single relaxed load + compare; only on a
242 * fork-generation mismatch do we touch getpid() and scan slots. */
243 12218 static inline void st_claim_reader_slot(StHandle *h) {
244 12218 uint32_t cur_gen = __atomic_load_n(&st_fork_gen, __ATOMIC_RELAXED);
245 12218 ▶ 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)) 12188 30 12218
if (__builtin_expect(cur_gen == h->cached_fork_gen && h->my_slot_idx != UINT32_MAX, 1)) 12188 0 12188
246 12188 return;
247 /* Cold path -- register the atfork hook once per process, then claim. */
248 30 pthread_once(&st_atfork_once, st_atfork_init);
249 /* Re-read after pthread_once: st_on_fork_child may have bumped it. */
250 30 cur_gen = __atomic_load_n(&st_fork_gen, __ATOMIC_RELAXED);
251 30 uint32_t now_pid = (uint32_t)getpid();
252 30 h->cached_pid = now_pid;
253 30 ▶ 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 */ 30 0 30
254 30 h->cached_fork_gen = cur_gen;
255 30 h->my_slot_idx = UINT32_MAX;
256 30 uint32_t start = now_pid % ST_READER_SLOTS;
257 /* Pass 1: take a free slot. */
258 31 ▶ for (uint32_t i = 0; i < ST_READER_SLOTS; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t i = 0; i < ST_READER_SLOTS; i++) { 31 0 31
259 31 uint32_t s = (start + i) % ST_READER_SLOTS;
260 31 uint32_t expected = 0;
261 31 ▶ if (__atomic_compare_exchange_n(&h->reader_slots[s].pid,
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_compare_exchange_n(&h->reader_slots[s].pid, 30 1 31
262 &expected, now_pid, 0,
263 __ATOMIC_ACQUIRE, __ATOMIC_RELAXED)) {
264 /* Fresh owner holds no read locks yet; clear any stale rdepth left by
265 * a dead predecessor (its contribution is dropped as we take over). */
266 30 __atomic_store_n(&h->reader_slots[s].rdepth, 0, __ATOMIC_RELAXED);
267 30 st_occ_set(h, s); /* mark occupied BEFORE any rdlock can bump rdepth */
268 30 h->my_slot_idx = s;
269 30 return;
270 }
271 }
272 /* Pass 2: claim one slot and clear other dead slots so exited workers
273 * do not leave the occupancy bitmap permanently full. */
274 0 ▶ for (uint32_t i = 0; i < ST_READER_SLOTS; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t i = 0; i < ST_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 == now_pid || (dpid && st_pid_alive(dpid))) continue;
Branch: 3 branches
BranchTrueFalseTotal
if (dpid == now_pid || (dpid && st_pid_alive(dpid))) continue; 0 0 0
if (dpid == now_pid || (dpid && st_pid_alive(dpid))) continue; 0 0 0
if (dpid == now_pid || (dpid && st_pid_alive(dpid))) continue; 0 0 0
277 0 ▶ if (dpid == 0 && h->my_slot_idx != UINT32_MAX) continue;
Branch: 2 branches
BranchTrueFalseTotal
if (dpid == 0 && h->my_slot_idx != UINT32_MAX) continue; 0 0 0
if (dpid == 0 && h->my_slot_idx != UINT32_MAX) continue; 0 0 0
278 0 uint32_t expected = dpid;
279 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
280 __ATOMIC_ACQUIRE, __ATOMIC_RELAXED)) {
281 0 ▶ if (__atomic_exchange_n(&h->reader_slots[i].rdepth, 0, __ATOMIC_RELEASE))
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_exchange_n(&h->reader_slots[i].rdepth, 0, __ATOMIC_RELEASE)) 0 0 0
282 0 st_reader_wake_drain(h);
283 0 ▶ if (h->my_slot_idx == UINT32_MAX) {
Branch: 1 branch
BranchTrueFalseTotal
if (h->my_slot_idx == UINT32_MAX) { 0 0 0
284 0 st_occ_set(h, i);
285 0 h->my_slot_idx = i;
286 } else {
287 0 st_occ_clear(h, i);
288 0 __atomic_store_n(&h->reader_slots[i].pid, 0, __ATOMIC_RELEASE);
289 }
290 }
291 }
292 0 ▶ if (h->my_slot_idx != UINT32_MAX) return;
Branch: 1 branch
BranchTrueFalseTotal
if (h->my_slot_idx != UINT32_MAX) return; 0 0 0
293 /* Table full -- leave my_slot_idx = UINT32_MAX so this handle takes the
294 * slotless path (lock still works; recovery of THIS reader's death is the
295 * documented slotless limitation). */
296 }
297  
298 /* Wait until no live reader holds the lock; the caller owns wlock, so no NEW
299 * reader can join (they see wlock!=0 and yield). The SEQ_CST wlock CAS + the
300 * SEQ_CST rdepth loads below are the writer side of the Dekker handshake. */
301 6091 static inline void st_rwlock_drain(StHandle *h) {
302 6091 StHeader *hdr = h->hdr;
303 0 for (;;) {
304 6091 uint32_t v = __atomic_load_n(&hdr->drain_seq, __ATOMIC_ACQUIRE); /* snapshot BEFORE scan */
305 6091 int busy = 0;
306 /* Visit only OCCUPIED slots via the occupancy bitmap (SEQ_CST: a committed
307 * reader's bit -- set in claim, before its rdepth++ -- is ordered before
308 * this scan, so no held slot is skipped). O(ST_OCC_WORDS + live readers)
309 * instead of O(ST_READER_SLOTS). */
310 103547 ▶ for (uint32_t w = 0; w < ST_OCC_WORDS; w++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t w = 0; w < ST_OCC_WORDS; w++) { 97456 6091 103547
311 97456 uint64_t word = __atomic_load_n(&h->occ[w], __ATOMIC_SEQ_CST);
312 103548 ▶ while (word) {
Branch: 1 branch
BranchTrueFalseTotal
while (word) { 6092 97456 103548
313 6092 uint32_t i = (w << 6) + (uint32_t)__builtin_ctzll(word);
314 6092 word &= word - 1; /* consume this bit (local copy) */
315 6092 uint32_t rd = __atomic_load_n(&h->reader_slots[i].rdepth, __ATOMIC_SEQ_CST);
316 6092 ▶ if (rd == 0) continue; /* occupied but not read-locking now */
Branch: 1 branch
BranchTrueFalseTotal
if (rd == 0) continue; /* occupied but not read-locking now */ 6092 0 6092
317 0 uint32_t pid = __atomic_load_n(&h->reader_slots[i].pid, __ATOMIC_ACQUIRE);
318 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
319 0 ▶ if (!st_pid_alive(pid)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!st_pid_alive(pid)) { 0 0 0
320 /* Dead reader: drop its pid so the slot no longer counts. Leave
321 * the occ bit set (harmless -- a later scan hits pid==0 and skips,
322 * a re-claim re-sets it) to avoid racing a concurrent claimant. */
323 0 uint32_t ep = pid;
324 0 __atomic_compare_exchange_n(&h->reader_slots[i].pid, &ep, 0,
325 0, __ATOMIC_ACQ_REL, __ATOMIC_RELAXED);
326 0 continue;
327 }
328 0 busy = 1; /* live reader still holding */
329 }
330 }
331 /* A live slotless reader keeps us waiting; a crashed slotless reader that
332 * cannot be attributed to a pid is the documented slotless limitation. */
333 6091 ▶ 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 6091 6091
334 0 busy = 1;
335 6091 ▶ if (!busy)
Branch: 1 branch
BranchTrueFalseTotal
if (!busy) 6091 0 6091
336 6091 return; /* exclusive: wlock held + every rdepth 0 */
337 /* Wait for a reader to release (drain_seq bump) or time out to re-scan
338 * (which reclaims any newly-dead slotted reader). */
339 0 syscall(SYS_futex, &hdr->drain_seq, FUTEX_WAIT, v, &st_lock_timeout, NULL, 0);
340 }
341 }
342  
343 /* 1 if this process holds a read lock on the segment (through any handle). Such a
344 * lock predates the current wlock holder, whose drain could then never have
345 * finished: it died before mutating anything. */
346 0 static int st_self_reading(StHandle *h) {
347 0 ▶ if (h->slotless_held) return 1;
Branch: 1 branch
BranchTrueFalseTotal
if (h->slotless_held) return 1; 0 0 0
348 0 uint32_t me = (uint32_t)getpid();
349 0 ▶ for (uint32_t i = 0; i < ST_READER_SLOTS; i++)
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t i = 0; i < ST_READER_SLOTS; i++) 0 0 0
350 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
351 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
352 0 return 1;
353 0 return 0;
354 }
355  
356 static void st_repair_locked(StHandle *h);
357  
358 /* Force-recover a stale WRITE lock left by a dead writer (held or mid-drain).
359 * CAS to OUR pid to hold the lock while repairing shared state, then release.
360 * Using our pid (not a bare WRITER_BIT sentinel) means a subsequent recovering
361 * process can detect and re-recover if we crash mid-recovery. */
362 0 static inline void st_recover_stale_lock(StHandle *h, uint32_t observed_wlock) {
363 0 StHeader *hdr = h->hdr;
364 0 uint32_t mypid = ST_RWLOCK_WR((uint32_t)getpid());
365 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
366 mypid, 0, __ATOMIC_SEQ_CST, __ATOMIC_RELAXED))
367 0 return;
368 0 ▶ if (!st_self_reading(h)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!st_self_reading(h)) { 0 0 0
369 0 st_rwlock_drain(h);
370 0 st_repair_locked(h);
371 }
372 0 __atomic_store_n(&hdr->wlock, 0, __ATOMIC_RELEASE);
373 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
374 0 syscall(SYS_futex, &hdr->wlock, FUTEX_WAKE, INT_MAX, NULL, NULL, 0);
375 }
376  
377 /* Inspect the writer word after a futex-wait timeout. If a dead writer holds
378 * it, force-recover. Dead READERS need no action here: only a writer that owns
379 * wlock drains readers, and it clears dead readers inline in its own scan. */
380 0 static inline void st_recover_after_timeout(StHandle *h) {
381 0 uint32_t val = __atomic_load_n(&h->hdr->wlock, __ATOMIC_RELAXED);
382 0 ▶ if (val >= ST_RWLOCK_WRITER_BIT) {
Branch: 1 branch
BranchTrueFalseTotal
if (val >= ST_RWLOCK_WRITER_BIT) { 0 0 0
383 0 uint32_t pid = val & ST_RWLOCK_PID_MASK;
384 0 ▶ if (!st_pid_alive(pid))
Branch: 1 branch
BranchTrueFalseTotal
if (!st_pid_alive(pid)) 0 0 0
385 0 st_recover_stale_lock(h, val);
386 }
387 0 }
388  
389 /* Bump/drop the parked-waiter hint. Both readers (blocked at the gate) and
390 * writers (blocked acquiring wlock) wait on the wlock futex and use this, so
391 * wrunlock/recover know whether a FUTEX_WAKE is worth a syscall. A waiter
392 * SIGKILLed while parked leaves rwait over-counted -> at most a spurious wake
393 * (harmless); it can never under-count, so no wakeup is lost. */
394 0 static inline void st_park(StHandle *h) {
395 0 __atomic_add_fetch(&h->hdr->rwait, 1, __ATOMIC_RELAXED);
396 0 }
397 0 static inline void st_unpark(StHandle *h) {
398 0 __atomic_sub_fetch(&h->hdr->rwait, 1, __ATOMIC_RELAXED);
399 0 }
400  
401 /* Publish (inc) / retract (dec) this reader's ENTIRE lock contribution. A
402 * slotted reader uses its slot's rdepth; one that could not claim a slot uses
403 * the global slotless_rdepth. inc() is SEQ_CST so the wlock re-check that
404 * follows it in rdlock forms a Dekker handshake with the writer's SEQ_CST
405 * wlock-store + rdepth-scan. dec() peels slotless first so a slot claimed
406 * mid-hold cannot misattribute the decrement. */
407 6127 static inline void st_rdepth_inc(StHandle *h) {
408 6127 ▶ if (h->my_slot_idx != UINT32_MAX) {
Branch: 1 branch
BranchTrueFalseTotal
if (h->my_slot_idx != UINT32_MAX) { 6127 0 6127
409 6127 __atomic_add_fetch(&h->reader_slots[h->my_slot_idx].rdepth, 1, __ATOMIC_SEQ_CST);
410 } else {
411 0 __atomic_add_fetch(&h->hdr->slotless_rdepth, 1, __ATOMIC_SEQ_CST);
412 0 h->slotless_held++;
413 }
414 6127 }
415 6127 static inline void st_rdepth_dec(StHandle *h) {
416 6127 ▶ if (h->slotless_held > 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (h->slotless_held > 0) { 0 6127 6127
417 0 h->slotless_held--;
418 0 __atomic_sub_fetch(&h->hdr->slotless_rdepth, 1, __ATOMIC_RELEASE);
419 6127 ▶ } else if (h->my_slot_idx != UINT32_MAX) {
Branch: 1 branch
BranchTrueFalseTotal
} else if (h->my_slot_idx != UINT32_MAX) { 6127 0 6127
420 6127 __atomic_sub_fetch(&h->reader_slots[h->my_slot_idx].rdepth, 1, __ATOMIC_RELEASE);
421 }
422 6127 }
423  
424 /* Wake a writer that may be draining readers (it waits on drain_seq). Called
425 * after every rdepth decrement so a released read lock lets the writer re-scan
426 * promptly instead of waiting out its timeout. */
427 6127 static inline void st_reader_wake_drain(StHandle *h) {
428 6127 ▶ 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 6127 6127
429 0 __atomic_add_fetch(&h->hdr->drain_seq, 1, __ATOMIC_RELEASE);
430 0 syscall(SYS_futex, &h->hdr->drain_seq, FUTEX_WAKE, 1, NULL, NULL, 0);
431 }
432 6127 }
433  
434 6127 static inline void st_rwlock_rdlock(StHandle *h) {
435 6127 st_claim_reader_slot(h);
436 6127 StHeader *hdr = h->hdr;
437 6127 for (int spin = 0; ; spin++) {
438 6127 uint32_t cur = __atomic_load_n(&hdr->wlock, __ATOMIC_ACQUIRE);
439 6127 ▶ if (cur == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (cur == 0) { 6127 0 6127
440 /* Optimistically take the read: publish rdepth, then re-check wlock.
441 * SEQ_CST inc + SEQ_CST load vs. the writer's SEQ_CST wlock CAS +
442 * rdepth scan: by the single total order of SEQ_CST ops, the two
443 * sides cannot both miss each other, so we never hold concurrently
444 * with a writer. */
445 6127 st_rdepth_inc(h);
446 6127 ▶ if (__atomic_load_n(&hdr->wlock, __ATOMIC_SEQ_CST) == 0)
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&hdr->wlock, __ATOMIC_SEQ_CST) == 0) 6127 0 6127
447 6127 return; /* no writer after our publish -> we hold the read lock */
448 /* A writer appeared during our publish -- yield to it (write-preferring). */
449 0 st_rdepth_dec(h);
450 0 st_reader_wake_drain(h); /* let the draining writer see rdepth drop */
451 0 spin = 0;
452 0 continue;
453 }
454 /* wlock != 0: a writer holds or is acquiring. Recover if it is dead. */
455 0 if (cur >= ST_RWLOCK_WRITER_BIT &&
456 0 !st_pid_alive(cur & ST_RWLOCK_PID_MASK)) {
457 0 st_recover_stale_lock(h, cur);
458 0 spin = 0;
459 0 continue;
460 }
461 0 ▶ if (__builtin_expect(spin < ST_RWLOCK_SPIN_LIMIT, 1)) {
Branch: 1 branch
BranchTrueFalseTotal
if (__builtin_expect(spin < ST_RWLOCK_SPIN_LIMIT, 1)) { 0 0 0
462 0 st_rwlock_spin_pause();
463 0 continue;
464 }
465 0 st_park(h);
466 0 cur = __atomic_load_n(&hdr->wlock, __ATOMIC_RELAXED);
467 0 ▶ if (cur != 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (cur != 0) { 0 0 0
468 0 long rc = syscall(SYS_futex, &hdr->wlock, FUTEX_WAIT, cur,
469 &st_lock_timeout, NULL, 0);
470 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
471 0 st_unpark(h);
472 0 st_recover_after_timeout(h);
473 0 spin = 0;
474 0 continue;
475 }
476 }
477 0 st_unpark(h);
478 0 spin = 0;
479 }
480 }
481  
482 6127 static inline void st_rwlock_rdunlock(StHandle *h) {
483 6127 st_rdepth_dec(h); /* RELEASE: drop our entire contribution */
484 6127 st_reader_wake_drain(h); /* if a writer is draining, wake it to re-scan */
485 6127 }
486  
487 6091 static inline void st_rwlock_wrlock(StHandle *h) {
488 6091 st_claim_reader_slot(h); /* refresh cached_pid across fork */
489 6091 StHeader *hdr = h->hdr;
490 /* Encode PID in the wlock word itself (0x80000000 | pid) to eliminate any
491 * crash window between acquiring the lock and storing the owner. */
492 6091 uint32_t mypid = ST_RWLOCK_WR(h->cached_pid);
493 /* Phase 1: acquire the writer word (mutual exclusion among writers). */
494 6091 for (int spin = 0; ; spin++) {
495 6091 uint32_t expected = 0;
496 6091 ▶ if (__atomic_compare_exchange_n(&hdr->wlock, &expected, mypid,
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_compare_exchange_n(&hdr->wlock, &expected, mypid, 6091 0 6091
497 0, __ATOMIC_SEQ_CST, __ATOMIC_RELAXED))
498 6091 break;
499 /* Contended: expected now holds the current wlock value. */
500 0 if (expected >= ST_RWLOCK_WRITER_BIT &&
501 0 !st_pid_alive(expected & ST_RWLOCK_PID_MASK)) {
502 0 st_recover_stale_lock(h, expected);
503 0 spin = 0;
504 0 continue;
505 }
506 0 ▶ if (__builtin_expect(spin < ST_RWLOCK_SPIN_LIMIT, 1)) {
Branch: 1 branch
BranchTrueFalseTotal
if (__builtin_expect(spin < ST_RWLOCK_SPIN_LIMIT, 1)) { 0 0 0
507 0 st_rwlock_spin_pause();
508 0 continue;
509 }
510 0 st_park(h);
511 0 uint32_t cur = __atomic_load_n(&hdr->wlock, __ATOMIC_RELAXED);
512 0 ▶ if (cur != 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (cur != 0) { 0 0 0
513 0 long rc = syscall(SYS_futex, &hdr->wlock, FUTEX_WAIT, cur,
514 &st_lock_timeout, NULL, 0);
515 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
516 0 st_unpark(h);
517 0 st_recover_after_timeout(h);
518 0 spin = 0;
519 0 continue;
520 }
521 }
522 0 st_unpark(h);
523 0 spin = 0;
524 }
525 /* Phase 2: drain the readers that were already holding when we won the CAS. */
526 6091 st_rwlock_drain(h);
527 6091 }
528  
529 6091 static inline void st_rwlock_wrunlock(StHandle *h) {
530 6091 StHeader *hdr = h->hdr;
531 6091 __atomic_store_n(&hdr->wlock, 0, __ATOMIC_RELEASE);
532 6091 ▶ if (__atomic_load_n(&hdr->rwait, __ATOMIC_RELAXED) > 0)
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&hdr->rwait, __ATOMIC_RELAXED) > 0) 0 6091 6091
533 0 syscall(SYS_futex, &hdr->wlock, FUTEX_WAKE, INT_MAX, NULL, NULL, 0);
534 6091 }
535  
536 /* ================================================================
537 * Layout math + create / open / destroy
538 * ================================================================ */
539  
540 /* Single source of truth for the mmap region layout offsets:
541 * Header -> reader_slots[1024] -> occ bitmap -> nodes[2*size] (1-indexed, node 0 unused). */
542 typedef struct { uint64_t reader_slots, occ, nodes, total; } StLayout;
543  
544 /* round v up to the next power of two (64-bit), with a floor of 1 */
545 42 static inline uint64_t st_next_pow2_u64(uint64_t v) {
546 42 ▶ if (v <= 1) return 1;
Branch: 1 branch
BranchTrueFalseTotal
if (v <= 1) return 1; 2 40 42
547 40 return 1ULL << (64 - __builtin_clzll(v - 1));
548 }
549  
550 110 static inline StLayout st_layout_for(uint64_t size) {
551 StLayout L;
552 110 L.reader_slots = sizeof(StHeader);
553 110 L.occ = L.reader_slots + (uint64_t)ST_READER_SLOTS * sizeof(StReaderSlot);
554 110 L.nodes = L.occ + ST_OCC_BYTES;
555 110 L.nodes = (L.nodes + 7) & ~(uint64_t)7;
556 110 L.total = L.nodes + 2ULL * size * sizeof(StNode); /* nodes 0 .. 2*size-1 */
557 110 return L;
558 }
559  
560 42 static inline uint64_t st_total_size(uint64_t size) {
561 42 return st_layout_for(size).total;
562 }
563  
564 29 static inline void st_init_header(void *base, uint64_t n, uint64_t size, uint64_t total) {
565 29 StLayout L = st_layout_for(size);
566 29 StHeader *hdr = (StHeader *)base;
567 /* Zero the whole region: every node's sum/min/max/lazy = 0, so all n
568 positions read as 0. Padding leaves (n..size-1) stay 0 too and are
569 never queried (queries clamp to [0, n-1]), so they never surface. */
570 29 memset(base, 0, (size_t)L.total);
571 29 hdr->version = ST_VERSION;
572 29 hdr->n = n;
573 29 hdr->size = size;
574 29 hdr->nodes_off = L.nodes;
575 29 hdr->total_size = total;
576 29 hdr->reader_slots_off = L.reader_slots;
577 /* Publish magic LAST, as a release store: it is the commit point, so a
578 creator killed before it leaves magic==0 and never a file mistaken for
579 a valid one. A kill during the field stores leaves one to remove by
580 hand. */
581 29 __atomic_store_n(&hdr->magic, ST_MAGIC, __ATOMIC_RELEASE);
582 29 __atomic_thread_fence(__ATOMIC_SEQ_CST);
583 29 }
584  
585 13808 static inline StNode *st_nodes(StHandle *h) {
586 13808 return (StNode *)((char *)h->base + h->nodes_off);
587 }
588  
589 /* Layer B trusted bound: the number of nodes guaranteed to lie within the real
590 * mapping. Derived from the process-local mmap_size (fixed at attach, not
591 * peer-writable) and the SAME nodes_off the accessor uses, so a corrupt
592 * hdr->size can never drive a node access outside the mapping. Equals 2*size
593 * for a valid tree. */
594 37 static inline uint64_t st_nodes_max(StHandle *h) {
595 37 ▶ if (h->nodes_off >= h->mmap_size) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (h->nodes_off >= h->mmap_size) return 0; 0 37 37
596 37 return (h->mmap_size - h->nodes_off) / sizeof(StNode);
597 }
598  
599 34 static inline StHandle *st_setup(void *base, size_t map_size,
600 const char *path, int backing_fd, char *errbuf) {
601 34 StHeader *hdr = (StHeader *)base;
602 34 StHandle *h = (StHandle *)calloc(1, sizeof(StHandle));
603 34 ▶ if (!h) {
Branch: 1 branch
BranchTrueFalseTotal
if (!h) { 0 34 34
604 0 munmap(base, map_size);
605 0 ▶ if (backing_fd >= 0) close(backing_fd);
Branch: 1 branch
BranchTrueFalseTotal
if (backing_fd >= 0) close(backing_fd); 0 0 0
606 0 ▶ ST_ERR("out of memory"); /* else callers croak with an empty message */
Branch: 1 branch
BranchTrueFalseTotal
ST_ERR("out of memory"); /* else callers croak with an empty message */ 0 0 0
607 0 return NULL;
608 }
609 34 h->hdr = hdr;
610 34 h->base = base;
611 34 h->reader_slots = (StReaderSlot *)((uint8_t *)base + sizeof(StHeader)); /* trusted layout, not the peer-writable header offset */
612 34 h->occ = (uint64_t *)((uint8_t *)base + st_layout_for(0).occ); /* trusted layout offset (occ offset is size-independent, not from peer-writable header) */
613 /* single validated read of each geometry field, cached process-locally */
614 34 h->nodes_off = hdr->nodes_off;
615 34 h->n = hdr->n;
616 34 h->size = hdr->size;
617 34 h->mmap_size = map_size;
618 /* Layer B: if the mapping cannot hold 2*size nodes the header lied about its
619 size; clamp the cached tree size to what actually fits. The clamped size
620 MUST stay a power of two: the mid-split recursion over [0, size-1] indexes up
621 to ~4*size nodes for a NON-pow2 size but only 2*size-1 for a pow2 size, so a
622 bare `size = fit` (fit possibly non-pow2) would let a node index run past
623 2*size and out of the mapping. Clamp down to the largest power of two <= fit
624 (keeps size pow2 AND 2*size <= nodes_max, so every node index < 2*size stays
625 inside the mapping). A resulting size==0 is handled safely everywhere (ops
626 become no-ops via st_clamp_range). */
627 {
628 34 uint64_t fit = st_nodes_max(h) / 2;
629 34 ▶ if (h->size > fit) {
Branch: 1 branch
BranchTrueFalseTotal
if (h->size > fit) { 0 34 34
630 0 ▶ uint64_t p = 0; for (uint64_t q = 1; q && q <= fit; q <<= 1) p = q; /* largest pow2 <= fit, or 0 */
Branch: 2 branches
BranchTrueFalseTotal
uint64_t p = 0; for (uint64_t q = 1; q && q <= fit; q <<= 1) p = q; /* largest pow2 <= fit, or 0 */ 0 0 0
uint64_t p = 0; for (uint64_t q = 1; q && q <= fit; q <<= 1) p = q; /* largest pow2 <= fit, or 0 */ 0 0 0
631 0 ▶ h->size = p; if (h->n > h->size) h->n = h->size;
Branch: 1 branch
BranchTrueFalseTotal
h->size = p; if (h->n > h->size) h->n = h->size; 0 0 0
632 }
633 }
634 34 ▶ h->path = path ? strdup(path) : NULL;
Branch: 1 branch
BranchTrueFalseTotal
h->path = path ? strdup(path) : NULL; 12 22 34
635 34 ▶ if (path && h->path && path[0] != '/') {
Branch: 3 branches
BranchTrueFalseTotal
if (path && h->path && path[0] != '/') { 12 22 34
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 34 ▶ if (path && (!h->path || (path[0] != '/' && !h->unlink_path))) {
Branch: 4 branches
BranchTrueFalseTotal
if (path && (!h->path || (path[0] != '/' && !h->unlink_path))) { 12 22 34
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 ▶ ST_ERR("backing path: %s", strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
ST_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 34 h->backing_fd = backing_fd;
654 34 h->my_slot_idx = UINT32_MAX;
655 34 return h;
656 }
657  
658 /* Validate a mapped header (shared by st_create reopen and st_open_fd). */
659 9 static inline int st_validate_header(const StHeader *hdr, uint64_t file_size) {
660 9 ▶ if (hdr->magic != ST_MAGIC) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->magic != ST_MAGIC) return 0; 4 5 9
661 5 ▶ if (hdr->version != ST_VERSION) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->version != ST_VERSION) return 0; 0 5 5
662 5 ▶ if (__atomic_load_n(&hdr->add_used, __ATOMIC_RELAXED) > 1) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&hdr->add_used, __ATOMIC_RELAXED) > 1) return 0; 0 5 5
663 5 ▶ if (hdr->n < ST_MIN_N || hdr->n > ST_MAX_N) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (hdr->n < ST_MIN_N || hdr->n > ST_MAX_N) return 0; 5 0 5
if (hdr->n < ST_MIN_N || hdr->n > ST_MAX_N) return 0; 0 5 5
664 5 ▶ if (hdr->size != st_next_pow2_u64(hdr->n)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->size != st_next_pow2_u64(hdr->n)) return 0; 0 5 5
665 5 ▶ if (hdr->size == 0 || (hdr->size & (hdr->size - 1)) != 0) return 0; /* power of two */
Branch: 2 branches
BranchTrueFalseTotal
if (hdr->size == 0 || (hdr->size & (hdr->size - 1)) != 0) return 0; /* power of two */ 5 0 5
if (hdr->size == 0 || (hdr->size & (hdr->size - 1)) != 0) return 0; /* power of two */ 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 != st_total_size(hdr->size)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->total_size != st_total_size(hdr->size)) return 0; 0 5 5
668 5 StLayout L = st_layout_for(hdr->size);
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->nodes_off != L.nodes) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->nodes_off != L.nodes) return 0; 0 5 5
671 5 return 1;
672 }
673  
674 /* validate the requested number of positions n */
675 37 static int st_validate_args(uint64_t n, char *errbuf) {
676 37 ▶ if (errbuf) errbuf[0] = '\0';
Branch: 1 branch
BranchTrueFalseTotal
if (errbuf) errbuf[0] = '\0'; 37 0 37
677 37 ▶ if (n < ST_MIN_N || n > ST_MAX_N) { ST_ERR("number of positions must be between 1 and 2^24"); return 0; }
Branch: 3 branches
BranchTrueFalseTotal
if (n < ST_MIN_N || n > ST_MAX_N) { ST_ERR("number of positions must be between 1 and 2^24"); return 0; } 37 0 37
if (n < ST_MIN_N || n > ST_MAX_N) { ST_ERR("number of positions must be between 1 and 2^24"); return 0; } 0 37 37
if (n < ST_MIN_N || n > ST_MAX_N) { ST_ERR("number of positions must be between 1 and 2^24"); return 0; } 0 0 0
678 37 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 st_validate_header. */
688 16 static int st_secure_open(const char *path, mode_t mode, char *errbuf) {
689 16 ▶ for (int attempt = 0; attempt < 100; attempt++) {
Branch: 1 branch
BranchTrueFalseTotal
for (int attempt = 0; attempt < 100; attempt++) { 16 0 16
690 16 int fd = open(path, O_RDWR|O_CREAT|O_EXCL|O_NOFOLLOW|O_CLOEXEC, mode);
691 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
692 9 ▶ if (errno != EEXIST) { ST_ERR("create %s: %s", path, strerror(errno)); return -1; }
Branch: 2 branches
BranchTrueFalseTotal
if (errno != EEXIST) { ST_ERR("create %s: %s", path, strerror(errno)); return -1; } 0 9 9
if (errno != EEXIST) { ST_ERR("create %s: %s", path, strerror(errno)); return -1; } 0 0 0
693 9 fd = open(path, O_RDWR|O_NOFOLLOW|O_CLOEXEC);
694 9 ▶ if (fd >= 0) return fd;
Branch: 1 branch
BranchTrueFalseTotal
if (fd >= 0) return fd; 9 0 9
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 ▶ ST_ERR("open %s: %s", path, strerror(errno)); /* ELOOP => symlink rejected */
Branch: 1 branch
BranchTrueFalseTotal
ST_ERR("open %s: %s", path, strerror(errno)); /* ELOOP => symlink rejected */ 0 0 0
697 0 return -1;
698 }
699 0 ▶ ST_ERR("open %s: create/attach kept racing", path);
Branch: 1 branch
BranchTrueFalseTotal
ST_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 st_file_is_zero(int fd, uint64_t size) {
708 char buf[16384];
709 9 ▶ for (uint64_t off = 0; off < size; ) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint64_t off = 0; off < size; ) { 8 1 9
710 8 ssize_t n = pread(fd, buf, size - off < sizeof buf ? (size_t)(size - off) : sizeof buf, (off_t)off);
711 8 ▶ if (n <= 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (n <= 0) return 0; 0 8 8
712 99079 ▶ 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 99071 99072
for (ssize_t i = 0; i < n; i++) if (buf[i]) return 0; 99072 7 99079
713 7 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 9 static int st_reserve(int fd, uint64_t size) {
720 9 const char *sp = getenv("DATA_SEGMENTTREE_SHARED_SPARSE");
721 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
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 9 sigfillset(&all);
726 9 sigprocmask(SIG_BLOCK, &all, &old);
727 int e;
728 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
729 9 sigprocmask(SIG_SETMASK, &old, NULL);
730 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
731 0 errno = e;
732 0 return -1;
733 }
734  
735 36 static StHandle *st_create(const char *path, uint64_t n, mode_t mode, char *errbuf) {
736 36 ▶ if (!st_validate_args(n, errbuf)) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!st_validate_args(n, errbuf)) return NULL; 0 36 36
737  
738 36 uint64_t size = st_next_pow2_u64(n);
739 36 uint64_t total = st_total_size(size);
740 36 int anonymous = (path == NULL);
741 36 int fd = -1;
742 size_t map_size;
743 void *base;
744  
745 36 ▶ if (anonymous) {
Branch: 1 branch
BranchTrueFalseTotal
if (anonymous) { 20 16 36
746 20 map_size = (size_t)total;
747 20 base = mmap(NULL, map_size, PROT_READ|PROT_WRITE, MAP_SHARED|MAP_ANONYMOUS, -1, 0);
748 20 ▶ if (base == MAP_FAILED) { ST_ERR("mmap: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { ST_ERR("mmap: %s", strerror(errno)); return NULL; } 0 20 20
if (base == MAP_FAILED) { ST_ERR("mmap: %s", strerror(errno)); return NULL; } 0 0 0
749 } else {
750 16 fd = st_secure_open(path, mode, errbuf);
751 25 ▶ if (fd < 0) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (fd < 0) return NULL; 0 16 16
752 16 ▶ if (flock(fd, LOCK_EX) < 0) { ST_ERR("flock: %s", strerror(errno)); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (flock(fd, LOCK_EX) < 0) { ST_ERR("flock: %s", strerror(errno)); close(fd); return NULL; } 0 16 16
if (flock(fd, LOCK_EX) < 0) { ST_ERR("flock: %s", strerror(errno)); close(fd); return NULL; } 0 0 0
753 struct stat st;
754 16 ▶ if (fstat(fd, &st) < 0) { ST_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fstat(fd, &st) < 0) { ST_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; } 0 16 16
if (fstat(fd, &st) < 0) { ST_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; } 0 0 0
755 16 int is_new = (st.st_size == 0);
756 16 ▶ if (!is_new && (uint64_t)st.st_size < sizeof(StHeader)) {
Branch: 2 branches
BranchTrueFalseTotal
if (!is_new && (uint64_t)st.st_size < sizeof(StHeader)) { 9 7 16
if (!is_new && (uint64_t)st.st_size < sizeof(StHeader)) { 1 8 9
757 1 ▶ ST_ERR("%s: file too small (%lld)", path, (long long)st.st_size);
Branch: 1 branch
BranchTrueFalseTotal
ST_ERR("%s: file too small (%lld)", path, (long long)st.st_size); 1 0 1
758 1 flock(fd, LOCK_UN); close(fd); return NULL;
759 }
760 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
761 0 ▶ ST_ERR("%s: refusing to initialize file not owned by us", path);
Branch: 1 branch
BranchTrueFalseTotal
ST_ERR("%s: refusing to initialize file not owned by us", path); 0 0 0
762 0 flock(fd, LOCK_UN); close(fd); return NULL;
763 }
764 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
765 0 ▶ ST_ERR("ftruncate: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
ST_ERR("ftruncate: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; 0 0 0
766 }
767 15 ▶ if (is_new && st_reserve(fd, total) < 0) {
Branch: 2 branches
BranchTrueFalseTotal
if (is_new && st_reserve(fd, total) < 0) { 7 8 15
if (is_new && st_reserve(fd, total) < 0) { 0 7 7
768 0 ▶ ST_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
ST_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno)); 0 0 0
769 0 if (ftruncate(fd, 0) < 0) { /* best effort */ }
770 0 flock(fd, LOCK_UN); close(fd); return NULL;
771 }
772 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
773 15 base = mmap(NULL, map_size, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
774 15 ▶ if (base == MAP_FAILED) {
Branch: 1 branch
BranchTrueFalseTotal
if (base == MAP_FAILED) { 0 15 15
775 0 ▶ ST_ERR("mmap: %s", strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
ST_ERR("mmap: %s", strerror(errno)); 0 0 0
776 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
777 0 flock(fd, LOCK_UN); close(fd); return NULL;
778 }
779 15 ▶ if (!is_new) {
Branch: 1 branch
BranchTrueFalseTotal
if (!is_new) { 8 7 15
780 8 ▶ if (!st_validate_header((StHeader *)base, (uint64_t)st.st_size)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!st_validate_header((StHeader *)base, (uint64_t)st.st_size)) { 4 4 8
781 /* Recover an abandoned mid-init file: a creator killed
782 * between the ftruncate and the header init leaves a
783 * full-size, all-zero (magic==0) file that would brick every
784 * future open of this path. Re-initialize ONLY when it is
785 * exactly our size, still uninitialized, and owned by us;
786 * anything else still errors. */
787 4 ▶ if (((StHeader *)base)->magic == 0 && (uint64_t)st.st_size == total
Branch: 2 branches
BranchTrueFalseTotal
if (((StHeader *)base)->magic == 0 && (uint64_t)st.st_size == total 3 1 4
if (((StHeader *)base)->magic == 0 && (uint64_t)st.st_size == total 2 1 3
788 2 ▶ && st.st_uid == geteuid() && st_file_is_zero(fd, map_size)) {
Branch: 2 branches
BranchTrueFalseTotal
&& st.st_uid == geteuid() && st_file_is_zero(fd, map_size)) { 2 0 2
&& st.st_uid == geteuid() && st_file_is_zero(fd, map_size)) { 1 1 2
789 1 ▶ if (fchmod(fd, mode) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (fchmod(fd, mode) < 0) { 0 1 1
790 0 ▶ ST_ERR("%s: fchmod: %s", path, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
ST_ERR("%s: fchmod: %s", path, strerror(errno)); 0 0 0
791 0 munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
792 }
793 1 ▶ if (st_reserve(fd, total) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (st_reserve(fd, total) < 0) { 0 1 1
794 0 ▶ ST_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
ST_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno)); 0 0 0
795 0 munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
796 }
797 1 st_init_header(base, n, size, total);
798 1 flock(fd, LOCK_UN); close(fd);
799 1 return st_setup(base, map_size, path, -1, errbuf);
800 }
801 3 ▶ if (((StHeader *)base)->magic == 0 && (uint64_t)st.st_size == total
Branch: 2 branches
BranchTrueFalseTotal
if (((StHeader *)base)->magic == 0 && (uint64_t)st.st_size == total 2 1 3
if (((StHeader *)base)->magic == 0 && (uint64_t)st.st_size == total 1 1 2
802 1 ▶ && st.st_uid == geteuid()) {
Branch: 1 branch
BranchTrueFalseTotal
&& st.st_uid == geteuid()) { 1 0 1
803 1 ▶ ST_ERR("%s: incomplete segment-tree file left by an interrupted create; remove it and retry", path);
Branch: 1 branch
BranchTrueFalseTotal
ST_ERR("%s: incomplete segment-tree file left by an interrupted create; remove it and retry", path); 1 0 1
804 1 munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
805 }
806 2 ▶ ST_ERR("invalid segment-tree file"); munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
ST_ERR("invalid segment-tree file"); munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL; 2 0 2
807 }
808 4 flock(fd, LOCK_UN); close(fd);
809 4 return st_setup(base, map_size, path, -1, errbuf);
810 }
811 }
812 27 st_init_header(base, n, size, total);
813 27 ▶ if (fd >= 0) { flock(fd, LOCK_UN); close(fd); }
Branch: 1 branch
BranchTrueFalseTotal
if (fd >= 0) { flock(fd, LOCK_UN); close(fd); } 7 20 27
814 27 return st_setup(base, map_size, path, -1, errbuf);
815 }
816  
817 1 static StHandle *st_create_memfd(const char *name, uint64_t n, char *errbuf) {
818 1 ▶ if (!st_validate_args(n, errbuf)) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!st_validate_args(n, errbuf)) return NULL; 0 1 1
819  
820 1 uint64_t size = st_next_pow2_u64(n);
821 1 uint64_t total = st_total_size(size);
822 1 ▶ int fd = memfd_create(name ? name : "segtree", MFD_CLOEXEC | MFD_ALLOW_SEALING);
Branch: 1 branch
BranchTrueFalseTotal
int fd = memfd_create(name ? name : "segtree", MFD_CLOEXEC | MFD_ALLOW_SEALING); 1 0 1
823 1 ▶ if (fd < 0) { ST_ERR("memfd_create: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fd < 0) { ST_ERR("memfd_create: %s", strerror(errno)); return NULL; } 0 1 1
if (fd < 0) { ST_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 ▶ ST_ERR("ftruncate: %s", strerror(errno)); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
ST_ERR("ftruncate: %s", strerror(errno)); close(fd); return NULL; 0 0 0
826 }
827 1 ▶ if (st_reserve(fd, total) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (st_reserve(fd, total) < 0) { 0 1 1
828 0 ▶ ST_ERR("memfd: cannot reserve %llu bytes: %s", (unsigned long long)total, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
ST_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) { ST_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { ST_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; } 0 1 1
if (base == MAP_FAILED) { ST_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; } 0 0 0
834 1 st_init_header(base, n, size, total);
835 1 return st_setup(base, (size_t)total, NULL, fd, errbuf);
836 }
837  
838 1 static StHandle *st_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) { ST_ERR("fstat: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fstat(fd, &st) < 0) { ST_ERR("fstat: %s", strerror(errno)); return NULL; } 0 1 1
if (fstat(fd, &st) < 0) { ST_ERR("fstat: %s", strerror(errno)); return NULL; } 0 0 0
842 1 ▶ if ((uint64_t)st.st_size < sizeof(StHeader)) { ST_ERR("too small"); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if ((uint64_t)st.st_size < sizeof(StHeader)) { ST_ERR("too small"); return NULL; } 0 1 1
if ((uint64_t)st.st_size < sizeof(StHeader)) { ST_ERR("too small"); return NULL; } 0 0 0
843 /* A donor fd we do not own can be truncated after we fstat/mmap it, faulting
844 * the reader with SIGBUS on a later access. For a SEALABLE fd (memfd) require
845 * resize seals so its size cannot change under us. A non-sealable fd (regular
846 * file, pipe, etc.) returns EINVAL from F_GET_SEALS -- skip the check there and
847 * leave the trust to the caller (documented in the POD SECURITY note). The
848 * family's own new_memfd seals GROW|SHRINK, so its fds pass. */
849 1 int seals = fcntl(fd, F_GET_SEALS);
850 1 ▶ if (seals >= 0 &&
Branch: 1 branch
BranchTrueFalseTotal
if (seals >= 0 && 1 0 1
851 1 ▶ (seals & (F_SEAL_SHRINK | F_SEAL_GROW)) != (F_SEAL_SHRINK | F_SEAL_GROW)) {
Branch: 1 branch
BranchTrueFalseTotal
(seals & (F_SEAL_SHRINK | F_SEAL_GROW)) != (F_SEAL_SHRINK | F_SEAL_GROW)) { 0 1 1
852 0 ▶ ST_ERR("fd is not sealed against resize (need F_SEAL_SHRINK|F_SEAL_GROW)");
Branch: 1 branch
BranchTrueFalseTotal
ST_ERR("fd is not sealed against resize (need F_SEAL_SHRINK|F_SEAL_GROW)"); 0 0 0
853 0 return NULL;
854 }
855 /* before mmap: a creator may truncate the file until it has set magic */
856 uint32_t magic;
857 1 ▶ if (pread(fd, &magic, sizeof magic, offsetof(StHeader, magic)) != (ssize_t)sizeof magic || magic != ST_MAGIC) {
Branch: 2 branches
BranchTrueFalseTotal
if (pread(fd, &magic, sizeof magic, offsetof(StHeader, magic)) != (ssize_t)sizeof magic || magic != ST_MAGIC) { 1 0 1
if (pread(fd, &magic, sizeof magic, offsetof(StHeader, magic)) != (ssize_t)sizeof magic || magic != ST_MAGIC) { 0 1 1
858 0 ▶ ST_ERR("invalid segment-tree table"); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
ST_ERR("invalid segment-tree table"); return NULL; 0 0 0
859 }
860 1 size_t ms = (size_t)st.st_size;
861 1 void *base = mmap(NULL, ms, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
862 1 ▶ if (base == MAP_FAILED) { ST_ERR("mmap: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { ST_ERR("mmap: %s", strerror(errno)); return NULL; } 0 1 1
if (base == MAP_FAILED) { ST_ERR("mmap: %s", strerror(errno)); return NULL; } 0 0 0
863 1 ▶ if (!st_validate_header((StHeader *)base, (uint64_t)st.st_size)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!st_validate_header((StHeader *)base, (uint64_t)st.st_size)) { 0 1 1
864 0 ▶ ST_ERR("invalid segment-tree table"); munmap(base, ms); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
ST_ERR("invalid segment-tree table"); munmap(base, ms); return NULL; 0 0 0
865 }
866 1 int myfd = fcntl(fd, F_DUPFD_CLOEXEC, 0);
867 1 ▶ if (myfd < 0) { ST_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (myfd < 0) { ST_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; } 0 1 1
if (myfd < 0) { ST_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; } 0 0 0
868 1 return st_setup(base, ms, NULL, myfd, errbuf);
869 }
870  
871 34 static void st_destroy(StHandle *h) {
872 34 ▶ if (!h) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!h) return; 0 34 34
873 /* Release our reader slot on clean teardown (else short-lived-reader churn
874 * exhausts the slot table); skip if a read lock is still held (rdepth>0). */
875 34 ▶ 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 && 34 0 34
if (h->reader_slots && h->my_slot_idx != UINT32_MAX && h->cached_pid && 30 4 34
if (h->reader_slots && h->my_slot_idx != UINT32_MAX && h->cached_pid && 30 0 30
876 30 ▶ h->cached_fork_gen == __atomic_load_n(&st_fork_gen, __ATOMIC_RELAXED) &&
Branch: 1 branch
BranchTrueFalseTotal
h->cached_fork_gen == __atomic_load_n(&st_fork_gen, __ATOMIC_RELAXED) && 30 0 30
877 30 ▶ __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) { 30 0 30
878 /* Clear our occ bit BEFORE freeing the slot: we still own the pid so no
879 * claimant can take the slot mid-clear, and rdepth==0 so no writer needs
880 * to see us. (A crash skips this -> the bit is reclaimed lazily by a
881 * writer scan / re-claim, same as the pid.) */
882 30 st_occ_clear(h, h->my_slot_idx);
883 30 uint32_t expected = h->cached_pid;
884 30 __atomic_compare_exchange_n(&h->reader_slots[h->my_slot_idx].pid,
885 &expected, 0, 0, __ATOMIC_RELEASE, __ATOMIC_RELAXED);
886 }
887 34 ▶ if (h->backing_fd >= 0) close(h->backing_fd);
Branch: 1 branch
BranchTrueFalseTotal
if (h->backing_fd >= 0) close(h->backing_fd); 2 32 34
888 34 ▶ if (h->base) munmap(h->base, h->mmap_size);
Branch: 1 branch
BranchTrueFalseTotal
if (h->base) munmap(h->base, h->mmap_size); 34 0 34
889 34 free(h->unlink_path);
890 34 free(h->path);
891 34 free(h);
892 }
893  
894 3 static inline int st_msync(StHandle *h) {
895 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
896 3 return msync(h->base, h->mmap_size, MS_SYNC);
897 }
898  
899 /* ================================================================
900 * Segment-tree operations (callers hold the lock)
901 *
902 * A perfect binary tree over `size` = next_pow2(n) leaves; node 1 is the root
903 * covering [0, size-1], node v has children 2v and 2v+1. Positions n..size-1
904 * are padding leaves no query ever covers (queries clamp to [0, n-1]). Each
905 * node's sum/min/max already reflects its own pending "range add" lazy; only
906 * its children are stale. Range-add pushes lazy down as it recomputes;
907 * queries never mutate -- they carry ancestors' un-pushed lazy as `pending`
908 * and shift each covered node's aggregate by it. Node indices all come from
909 * the recursion (never from shared memory), so the st_setup size-clamp alone
910 * keeps every access inside the mapping.
911 * ================================================================ */
912  
913 /* gcd of |a|,|b| (INT64_MIN-safe); 0 is the identity, so gcd(0,x) == |x| */
914 57314 static inline int64_t st_gcd2(int64_t a, int64_t b) {
915 57314 ▶ uint64_t x = a < 0 ? (uint64_t)(-(a + 1)) + 1 : (uint64_t)a;
Branch: 1 branch
BranchTrueFalseTotal
uint64_t x = a < 0 ? (uint64_t)(-(a + 1)) + 1 : (uint64_t)a; 3626 53688 57314
916 57314 ▶ uint64_t y = b < 0 ? (uint64_t)(-(b + 1)) + 1 : (uint64_t)b;
Branch: 1 branch
BranchTrueFalseTotal
uint64_t y = b < 0 ? (uint64_t)(-(b + 1)) + 1 : (uint64_t)b; 3 57311 57314
917 124379 ▶ while (y) { uint64_t t = x % y; x = y; y = t; }
Branch: 1 branch
BranchTrueFalseTotal
while (y) { uint64_t t = x % y; x = y; y = t; } 67065 57314 124379
918 57314 return (int64_t)x; /* |gcd| <= max(|a|,|b|) <= INT64_MAX+1; fits when a|b != 0 */
919 }
920 /* base^exp with signed-overflow detection; returns 1 on overflow, else 0 with *out set */
921 8202 static inline int st_ipow_ovf(int64_t base, uint64_t exp, int64_t *out) {
922 8202 int64_t result = 1, b = base;
923 23090 ▶ while (exp) {
Branch: 1 branch
BranchTrueFalseTotal
while (exp) { 14888 8202 23090
924 14888 ▶ if (exp & 1) { if (__builtin_mul_overflow(result, b, &result)) return 1; }
Branch: 2 branches
BranchTrueFalseTotal
if (exp & 1) { if (__builtin_mul_overflow(result, b, &result)) return 1; } 8202 6686 14888
if (exp & 1) { if (__builtin_mul_overflow(result, b, &result)) return 1; } 0 8202 8202
925 14888 exp >>= 1;
926 14888 ▶ if (exp) { if (__builtin_mul_overflow(b, b, &b)) return 1; }
Branch: 2 branches
BranchTrueFalseTotal
if (exp) { if (__builtin_mul_overflow(b, b, &b)) return 1; } 6686 8202 14888
if (exp) { if (__builtin_mul_overflow(b, b, &b)) return 1; } 0 6686 6686
927 }
928 8202 *out = result;
929 8202 return 0;
930 }
931 /* recompute node nd's product/overflow flag from children a,b. A range holds a
932 * zero exactly when prod==0 && !PROD_OVF (on overflow prod is zeroed but flagged);
933 * a zero collapses the parent product to 0 regardless of a sibling's overflow. */
934 47530 static inline void st_combine_prod(StNode *nd, const StNode *a, const StNode *b) {
935 47530 ▶ int azero = !(a->flags & ST_F_PROD_OVF) && a->prod == 0;
Branch: 2 branches
BranchTrueFalseTotal
int azero = !(a->flags & ST_F_PROD_OVF) && a->prod == 0; 36087 11443 47530
int azero = !(a->flags & ST_F_PROD_OVF) && a->prod == 0; 10394 25693 36087
936 47530 ▶ int bzero = !(b->flags & ST_F_PROD_OVF) && b->prod == 0;
Branch: 2 branches
BranchTrueFalseTotal
int bzero = !(b->flags & ST_F_PROD_OVF) && b->prod == 0; 41903 5627 47530
int bzero = !(b->flags & ST_F_PROD_OVF) && b->prod == 0; 17773 24130 41903
937 47530 ▶ if (azero || bzero) { nd->prod = 0; nd->flags &= ~ST_F_PROD_OVF; return; }
Branch: 2 branches
BranchTrueFalseTotal
if (azero || bzero) { nd->prod = 0; nd->flags &= ~ST_F_PROD_OVF; return; } 37136 10394 47530
if (azero || bzero) { nd->prod = 0; nd->flags &= ~ST_F_PROD_OVF; return; } 8676 28460 37136
938 28460 ▶ if ((a->flags & ST_F_PROD_OVF) || (b->flags & ST_F_PROD_OVF) ||
Branch: 2 branches
BranchTrueFalseTotal
if ((a->flags & ST_F_PROD_OVF) || (b->flags & ST_F_PROD_OVF) || 22838 5622 28460
if ((a->flags & ST_F_PROD_OVF) || (b->flags & ST_F_PROD_OVF) || 22837 1 22838
939 22837 ▶ __builtin_mul_overflow(a->prod, b->prod, &nd->prod)) {
Branch: 1 branch
BranchTrueFalseTotal
__builtin_mul_overflow(a->prod, b->prod, &nd->prod)) { 4505 18332 22837
940 10128 nd->flags |= ST_F_PROD_OVF;
941 10128 nd->prod = 0;
942 } else {
943 18332 nd->flags &= ~ST_F_PROD_OVF;
944 }
945 }
946  
947 /* apply a pending range-add of +delta to a node covering `cnt` leaves. Maintains
948 * sum/min/max only; gcd/product are not add-maintainable (gated by add_used). */
949 31729 static inline void st_apply_add(StNode *nd, int64_t delta, uint64_t cnt) {
950 31729 nd->sum += delta * (int64_t)cnt;
951 31729 nd->min += delta;
952 31729 nd->max += delta;
953 31729 ▶ if (nd->flags & ST_F_HAS_ASSIGN) nd->assign += delta; /* fold into the pending assign */
Branch: 1 branch
BranchTrueFalseTotal
if (nd->flags & ST_F_HAS_ASSIGN) nd->assign += delta; /* fold into the pending assign */ 10335 21394 31729
954 21394 else nd->lazy += delta;
955 31729 }
956  
957 /* apply a pending range-assign of value `c` to a node covering `cnt` leaves --
958 * a uniform range, so every aggregate is exact. */
959 7851 static inline void st_apply_assign(StNode *nd, int64_t c, uint64_t cnt) {
960 7851 nd->sum = c * (int64_t)cnt;
961 7851 nd->min = c;
962 7851 nd->max = c;
963 7851 nd->gcd = st_gcd2(c, 0); /* |c| */
964 7851 nd->assign = c;
965 /* The flag supersedes the pending add: set it before dropping that add. */
966 7851 __atomic_signal_fence(__ATOMIC_SEQ_CST);
967 7851 nd->flags = (nd->flags & ~ST_F_PROD_OVF) | ST_F_HAS_ASSIGN;
968 7851 __atomic_signal_fence(__ATOMIC_SEQ_CST);
969 7851 nd->lazy = 0;
970 7851 ▶ { int64_t p; if (st_ipow_ovf(c, cnt, &p)) nd->flags |= ST_F_PROD_OVF; else nd->prod = p; }
Branch: 1 branch
BranchTrueFalseTotal
{ int64_t p; if (st_ipow_ovf(c, cnt, &p)) nd->flags |= ST_F_PROD_OVF; else nd->prod = p; } 0 7851 7851
971 7851 }
972  
973 /* The field st_apply_add changes for good; recovery re-derives the rest from it. */
974 22358 static inline int64_t *st_add_tag(StNode *nd, int leaf) {
975 22358 ▶ return leaf ? &nd->sum : (nd->flags & ST_F_HAS_ASSIGN) ? &nd->assign : &nd->lazy;
Branch: 2 branches
BranchTrueFalseTotal
return leaf ? &nd->sum : (nd->flags & ST_F_HAS_ASSIGN) ? &nd->assign : &nd->lazy; 7496 14862 22358
return leaf ? &nd->sum : (nd->flags & ST_F_HAS_ASSIGN) ? &nd->assign : &nd->lazy; 54 14808 14862
976 }
977  
978 /* push node v's pending lazy (assign or add) down to both children. An
979 * assign lands the same however often it is replayed; an add is journaled. */
980 47530 static inline void st_pushdown(StHeader *hdr, StNode *nodes, uint64_t v, uint64_t lcnt, uint64_t rcnt) {
981 47530 StNode *nd = &nodes[v];
982 47530 ▶ if (nd->flags & ST_F_HAS_ASSIGN) {
Branch: 1 branch
BranchTrueFalseTotal
if (nd->flags & ST_F_HAS_ASSIGN) { 1750 45780 47530
983 1750 st_apply_assign(&nodes[2*v], nd->assign, lcnt);
984 1750 st_apply_assign(&nodes[2*v + 1], nd->assign, rcnt);
985 1750 nd->flags &= ~ST_F_HAS_ASSIGN;
986 45780 ▶ } else if (nd->lazy) {
Branch: 1 branch
BranchTrueFalseTotal
} else if (nd->lazy) { 11179 34601 45780
987 11179 int64_t d = nd->lazy;
988 11179 hdr->pd_delta = d;
989 11179 hdr->pd_tag[0] = *st_add_tag(&nodes[2*v], lcnt == 1) + d;
990 11179 hdr->pd_tag[1] = *st_add_tag(&nodes[2*v + 1], rcnt == 1) + d;
991 11179 __atomic_signal_fence(__ATOMIC_SEQ_CST);
992 11179 hdr->pd_node = v;
993 11179 __atomic_signal_fence(__ATOMIC_SEQ_CST);
994 11179 st_apply_add(&nodes[2*v], d, lcnt);
995 11179 st_apply_add(&nodes[2*v + 1], d, rcnt);
996 11179 __atomic_signal_fence(__ATOMIC_SEQ_CST);
997 11179 nd->lazy = 0;
998 11179 __atomic_signal_fence(__ATOMIC_SEQ_CST);
999 11179 hdr->pd_node = 0;
1000 }
1001 47530 }
1002  
1003 /* recompute node v's aggregate from its two (freshly updated) children */
1004 47530 static inline void st_pull(StNode *nodes, uint64_t v) {
1005 47530 StNode *nd = &nodes[v], *a = &nodes[2*v], *b = &nodes[2*v + 1];
1006 47530 nd->sum = a->sum + b->sum;
1007 47530 nd->min = a->min < b->min ? a->min : b->min;
1008 47530 nd->max = a->max > b->max ? a->max : b->max;
1009 47530 nd->gcd = st_gcd2(a->gcd, b->gcd);
1010 47530 st_combine_prod(nd, a, b);
1011 47530 }
1012  
1013 /* range-add delta to [l,r] within node v covering [lo,hi] (caller holds wrlock) */
1014 59692 static void st_range_add_rec(StHeader *hdr, StNode *nodes, uint64_t v, uint64_t lo, uint64_t hi,
1015 uint64_t l, uint64_t r, int64_t delta) {
1016 59692 ▶ if (r < lo || hi < l) return; /* disjoint */
Branch: 2 branches
BranchTrueFalseTotal
if (r < lo || hi < l) return; /* disjoint */ 47065 12627 59692
if (r < lo || hi < l) return; /* disjoint */ 9523 37542 47065
1017 37542 ▶ if (l <= lo && hi <= r) { st_apply_add(&nodes[v], delta, hi - lo + 1); return; }
Branch: 2 branches
BranchTrueFalseTotal
if (l <= lo && hi <= r) { st_apply_add(&nodes[v], delta, hi - lo + 1); return; } 17877 19665 37542
if (l <= lo && hi <= r) { st_apply_add(&nodes[v], delta, hi - lo + 1); return; } 9371 8506 17877
1018 28171 uint64_t mid = lo + (hi - lo) / 2;
1019 28171 st_pushdown(hdr, nodes, v, mid - lo + 1, hi - mid);
1020 28171 st_range_add_rec(hdr, nodes, 2*v, lo, mid, l, r, delta);
1021 28171 st_range_add_rec(hdr, nodes, 2*v + 1, mid + 1, hi, l, r, delta);
1022 28171 st_pull(nodes, v);
1023 }
1024  
1025 /* range-assign value c to [l,r] within node v covering [lo,hi] (caller holds wrlock) */
1026 41456 static void st_range_assign_rec(StHeader *hdr, StNode *nodes, uint64_t v, uint64_t lo, uint64_t hi,
1027 uint64_t l, uint64_t r, int64_t c) {
1028 41456 ▶ if (r < lo || hi < l) return; /* disjoint */
Branch: 2 branches
BranchTrueFalseTotal
if (r < lo || hi < l) return; /* disjoint */ 31397 10059 41456
if (r < lo || hi < l) return; /* disjoint */ 7690 23707 31397
1029 23707 ▶ if (l <= lo && hi <= r) { st_apply_assign(&nodes[v], c, hi - lo + 1); return; }
Branch: 2 branches
BranchTrueFalseTotal
if (l <= lo && hi <= r) { st_apply_assign(&nodes[v], c, hi - lo + 1); return; } 8345 15362 23707
if (l <= lo && hi <= r) { st_apply_assign(&nodes[v], c, hi - lo + 1); return; } 4348 3997 8345
1030 19359 uint64_t mid = lo + (hi - lo) / 2;
1031 19359 st_pushdown(hdr, nodes, v, mid - lo + 1, hi - mid);
1032 19359 st_range_assign_rec(hdr, nodes, 2*v, lo, mid, l, r, c);
1033 19359 st_range_assign_rec(hdr, nodes, 2*v + 1, mid + 1, hi, l, r, c);
1034 19359 st_pull(nodes, v);
1035 }
1036  
1037 /* Read-only query carry. A covered node's value is (asg ? av : stored) + ad.
1038 * A node's un-pushed lazy applies to its children, so SHALLOWER lazies apply
1039 * LATER (outermost): the SHALLOWEST assign on the path wins (av), adds ABOVE
1040 * it still apply on top (ad), and everything deeper than that assign is
1041 * wiped. Hence: adopt an assign / accumulate an add only while none seen. */
1042 typedef struct { int asg; int64_t av; int64_t ad; } StCarry;
1043  
1044 63837 static inline StCarry st_carry_descend(StCarry c, const StNode *nd) {
1045 63837 ▶ if (c.asg) return c; /* outer assign already fixed the value */
Branch: 1 branch
BranchTrueFalseTotal
if (c.asg) return c; /* outer assign already fixed the value */ 2000 61837 63837
1046 61837 ▶ if (nd->flags & ST_F_HAS_ASSIGN) { c.asg = 1; c.av = nd->assign; }
Branch: 1 branch
BranchTrueFalseTotal
if (nd->flags & ST_F_HAS_ASSIGN) { c.asg = 1; c.av = nd->assign; } 2327 59510 61837
1047 59510 ▶ else if (nd->lazy) { c.ad += nd->lazy; }
Branch: 1 branch
BranchTrueFalseTotal
else if (nd->lazy) { c.ad += nd->lazy; } 6128 53382 59510
1048 61837 return c;
1049 }
1050  
1051 /* accumulate sum/min/max over [l,r] (read-only; caller holds a lock) */
1052 124161 static void st_query_rec(StNode *nodes, uint64_t v, uint64_t lo, uint64_t hi,
1053 uint64_t l, uint64_t r, StCarry c,
1054 int64_t *sum, int64_t *mn, int64_t *mx) {
1055 147565 ▶ if (r < lo || hi < l) return; /* disjoint -> identity */
Branch: 2 branches
BranchTrueFalseTotal
if (r < lo || hi < l) return; /* disjoint -> identity */ 100303 23858 124161
if (r < lo || hi < l) return; /* disjoint -> identity */ 18318 81985 100303
1056 81985 ▶ if (l <= lo && hi <= r) { /* covered */
Branch: 2 branches
BranchTrueFalseTotal
if (l <= lo && hi <= r) { /* covered */ 43749 38236 81985
if (l <= lo && hi <= r) { /* covered */ 23404 20345 43749
1057 23404 uint64_t cnt = hi - lo + 1;
1058 int64_t s, nmin, nmax;
1059 23404 ▶ if (c.asg) { int64_t val = c.av + c.ad; s = val * (int64_t)cnt; nmin = nmax = val; }
Branch: 1 branch
BranchTrueFalseTotal
if (c.asg) { int64_t val = c.av + c.ad; s = val * (int64_t)cnt; nmin = nmax = val; } 2313 21091 23404
1060 21091 else { s = nodes[v].sum + c.ad * (int64_t)cnt;
1061 21091 nmin = nodes[v].min + c.ad; nmax = nodes[v].max + c.ad; }
1062 23404 *sum += s;
1063 23404 ▶ if (nmin < *mn) *mn = nmin;
Branch: 1 branch
BranchTrueFalseTotal
if (nmin < *mn) *mn = nmin; 12477 10927 23404
1064 23404 ▶ if (nmax > *mx) *mx = nmax;
Branch: 1 branch
BranchTrueFalseTotal
if (nmax > *mx) *mx = nmax; 13007 10397 23404
1065 23404 return;
1066 }
1067 58581 uint64_t mid = lo + (hi - lo) / 2;
1068 58581 StCarry cc = st_carry_descend(c, &nodes[v]);
1069 58581 st_query_rec(nodes, 2*v, lo, mid, l, r, cc, sum, mn, mx);
1070 58581 st_query_rec(nodes, 2*v + 1, mid + 1, hi, l, r, cc, sum, mn, mx);
1071 }
1072  
1073 /* accumulate gcd over [l,r] into *g (read-only; only called with add_used == 0,
1074 * so no add lazy exists and the carry is assign-only) */
1075 6738 static void st_gcd_rec(StNode *nodes, uint64_t v, uint64_t lo, uint64_t hi,
1076 uint64_t l, uint64_t r, StCarry c, int64_t *g) {
1077 8140 ▶ if (r < lo || hi < l) return;
Branch: 2 branches
BranchTrueFalseTotal
if (r < lo || hi < l) return; 5461 1277 6738
if (r < lo || hi < l) return; 894 4567 5461
1078 4567 ▶ if (l <= lo && hi <= r) {
Branch: 2 branches
BranchTrueFalseTotal
if (l <= lo && hi <= r) { 2605 1962 4567
if (l <= lo && hi <= r) { 1402 1203 2605
1079 1402 ▶ int64_t ng = c.asg ? st_gcd2(c.av, 0) : nodes[v].gcd;
Branch: 1 branch
BranchTrueFalseTotal
int64_t ng = c.asg ? st_gcd2(c.av, 0) : nodes[v].gcd; 531 871 1402
1080 1402 *g = st_gcd2(*g, ng);
1081 1402 return;
1082 }
1083 3165 uint64_t mid = lo + (hi - lo) / 2;
1084 3165 StCarry cc = st_carry_descend(c, &nodes[v]);
1085 3165 st_gcd_rec(nodes, 2*v, lo, mid, l, r, cc, g);
1086 3165 st_gcd_rec(nodes, 2*v + 1, mid + 1, hi, l, r, cc, g);
1087 }
1088  
1089 /* multiply product over [l,r] into *p. Sets *hasz if the range contains a zero
1090 * (then the product is 0, whatever any sibling overflow says) and *ovf on a real
1091 * int64 overflow with no zero. Does NOT short-circuit on *ovf -- a later zero
1092 * must still be able to force the result to 0. */
1093 4492 static void st_prod_rec(StNode *nodes, uint64_t v, uint64_t lo, uint64_t hi,
1094 uint64_t l, uint64_t r, StCarry c, int64_t *p, int *ovf, int *hasz) {
1095 5347 ▶ if (*hasz || r < lo || hi < l) return; /* a zero already forces the product to 0 */
Branch: 3 branches
BranchTrueFalseTotal
if (*hasz || r < lo || hi < l) return; /* a zero already forces the product to 0 */ 4226 266 4492
if (*hasz || r < lo || hi < l) return; /* a zero already forces the product to 0 */ 3593 633 4226
if (*hasz || r < lo || hi < l) return; /* a zero already forces the product to 0 */ 647 2946 3593
1096 2946 ▶ if (l <= lo && hi <= r) { /* covered */
Branch: 2 branches
BranchTrueFalseTotal
if (l <= lo && hi <= r) { /* covered */ 1501 1445 2946
if (l <= lo && hi <= r) { /* covered */ 855 646 1501
1097 int64_t np;
1098 855 ▶ if (c.asg) {
Branch: 1 branch
BranchTrueFalseTotal
if (c.asg) { 386 469 855
1099 386 ▶ if (c.av == 0) { *hasz = 1; return; } /* assigned zero -> product 0 */
Branch: 1 branch
BranchTrueFalseTotal
if (c.av == 0) { *hasz = 1; return; } /* assigned zero -> product 0 */ 35 351 386
1100 351 ▶ if (st_ipow_ovf(c.av, hi - lo + 1, &np)) { *ovf = 1; return; }
Branch: 1 branch
BranchTrueFalseTotal
if (st_ipow_ovf(c.av, hi - lo + 1, &np)) { *ovf = 1; return; } 0 351 351
1101 } else {
1102 469 const StNode *nd = &nodes[v];
1103 469 ▶ if (!(nd->flags & ST_F_PROD_OVF) && nd->prod == 0) { *hasz = 1; return; } /* range has a zero */
Branch: 2 branches
BranchTrueFalseTotal
if (!(nd->flags & ST_F_PROD_OVF) && nd->prod == 0) { *hasz = 1; return; } /* range has a zero */ 467 2 469
if (!(nd->flags & ST_F_PROD_OVF) && nd->prod == 0) { *hasz = 1; return; } /* range has a zero */ 75 392 467
1104 394 ▶ if (nd->flags & ST_F_PROD_OVF) { *ovf = 1; return; }
Branch: 1 branch
BranchTrueFalseTotal
if (nd->flags & ST_F_PROD_OVF) { *ovf = 1; return; } 2 392 394
1105 392 np = nd->prod;
1106 }
1107 743 ▶ if (__builtin_mul_overflow(*p, np, p)) *ovf = 1;
Branch: 1 branch
BranchTrueFalseTotal
if (__builtin_mul_overflow(*p, np, p)) *ovf = 1; 3 740 743
1108 743 return;
1109 }
1110 2091 uint64_t mid = lo + (hi - lo) / 2;
1111 2091 StCarry cc = st_carry_descend(c, &nodes[v]);
1112 2091 st_prod_rec(nodes, 2*v, lo, mid, l, r, cc, p, ovf, hasz);
1113 2091 st_prod_rec(nodes, 2*v + 1, mid + 1, hi, l, r, cc, p, ovf, hasz);
1114 }
1115  
1116 /* clamp a caller range to [0, n-1]; returns 0 if it is empty/out of range */
1117 11674 static inline int st_clamp_range(StHandle *h, uint64_t *l, uint64_t *r) {
1118 11674 ▶ if (h->n == 0 || h->size == 0) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (h->n == 0 || h->size == 0) return 0; 11674 0 11674
if (h->n == 0 || h->size == 0) return 0; 0 11674 11674
1119 11674 ▶ if (*l >= h->n) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (*l >= h->n) return 0; 0 11674 11674
1120 11674 ▶ if (*r >= h->n) *r = h->n - 1;
Branch: 1 branch
BranchTrueFalseTotal
if (*r >= h->n) *r = h->n - 1; 0 11674 11674
1121 11674 return *l <= *r;
1122 }
1123  
1124 /* add delta to every position in [l,r] (caller holds the write lock). This
1125 * permanently gates off the gcd/product monoids (add_used = 1). */
1126 3350 static void st_range_add_locked(StHandle *h, uint64_t l, uint64_t r, int64_t delta) {
1127 3350 ▶ if (!st_clamp_range(h, &l, &r)) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!st_clamp_range(h, &l, &r)) return; 0 3350 3350
1128 3350 __atomic_store_n(&h->hdr->add_used, 1, __ATOMIC_RELAXED); /* atomic: monoids_valid reads add_used unlocked (RELAXED) -- plain store would be a C11 data race */
1129 /* The gate before the tree: a writer killed mid-add must not leave gcd/product trusted. */
1130 3350 __atomic_signal_fence(__ATOMIC_SEQ_CST);
1131 3350 st_range_add_rec(h->hdr, st_nodes(h), 1, 0, h->size - 1, l, r, delta);
1132 }
1133  
1134 /* assign value c to every position in [l,r] (caller holds the write lock) */
1135 607 static void st_range_assign_locked(StHandle *h, uint64_t l, uint64_t r, int64_t c) {
1136 607 ▶ if (!st_clamp_range(h, &l, &r)) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!st_clamp_range(h, &l, &r)) return; 0 607 607
1137 607 st_range_assign_rec(h->hdr, st_nodes(h), 1, 0, h->size - 1, l, r, c);
1138 }
1139  
1140 /* sum/min/max over [l,r] into *sum/*mn/*mx (caller holds a lock) */
1141 6999 static void st_query_locked(StHandle *h, uint64_t l, uint64_t r,
1142 int64_t *sum, int64_t *mn, int64_t *mx) {
1143 6999 *sum = 0; *mn = ST_IDENTITY_MIN; *mx = ST_IDENTITY_MAX;
1144 6999 ▶ if (!st_clamp_range(h, &l, &r)) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!st_clamp_range(h, &l, &r)) return; 0 6999 6999
1145 6999 StCarry c = { 0, 0, 0 };
1146 6999 st_query_rec(st_nodes(h), 1, 0, h->size - 1, l, r, c, sum, mn, mx);
1147 }
1148  
1149 /* gcd over [l,r] (caller holds a lock and has checked add_used == 0) */
1150 408 static int64_t st_gcd_locked(StHandle *h, uint64_t l, uint64_t r) {
1151 408 int64_t g = 0;
1152 408 ▶ if (!st_clamp_range(h, &l, &r)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!st_clamp_range(h, &l, &r)) return 0; 0 408 408
1153 408 StCarry c = { 0, 0, 0 };
1154 408 st_gcd_rec(st_nodes(h), 1, 0, h->size - 1, l, r, c, &g);
1155 408 return g;
1156 }
1157  
1158 /* product over [l,r]; returns 0 with *ovf=1 on overflow, else the product with
1159 * *ovf=0 (empty range -> 1). Caller holds a lock and has checked add_used == 0. */
1160 310 static int64_t st_prod_locked(StHandle *h, uint64_t l, uint64_t r, int *ovf) {
1161 310 int64_t p = 1;
1162 310 int hasz = 0;
1163 310 *ovf = 0;
1164 310 ▶ if (!st_clamp_range(h, &l, &r)) return 1;
Branch: 1 branch
BranchTrueFalseTotal
if (!st_clamp_range(h, &l, &r)) return 1; 0 310 310
1165 310 StCarry c = { 0, 0, 0 };
1166 310 st_prod_rec(st_nodes(h), 1, 0, h->size - 1, l, r, c, &p, ovf, &hasz);
1167 310 ▶ if (hasz) { *ovf = 0; return 0; } /* a zero anywhere -> product 0, never an overflow */
Branch: 1 branch
BranchTrueFalseTotal
if (hasz) { *ovf = 0; return 0; } /* a zero anywhere -> product 0, never an overflow */ 110 200 310
1168 200 ▶ return *ovf ? 0 : p;
Branch: 1 branch
BranchTrueFalseTotal
return *ovf ? 0 : p; 198 2 200
1169 }
1170  
1171 /* value at position i (caller holds a lock); 0 if out of range */
1172 1710 static int64_t st_get_locked(StHandle *h, uint64_t i) {
1173 int64_t s, mn, mx;
1174 1710 st_query_locked(h, i, i, &s, &mn, &mx);
1175 1710 return s;
1176 }
1177  
1178 /* set position i to val (caller holds the write lock). Uses assign, not add, so
1179 * the gcd/product monoids stay valid across point updates. */
1180 2131 static void st_set_locked(StHandle *h, uint64_t i, int64_t val) {
1181 2131 ▶ if (h->n == 0 || i >= h->n) return;
Branch: 2 branches
BranchTrueFalseTotal
if (h->n == 0 || i >= h->n) return; 2131 0 2131
if (h->n == 0 || i >= h->n) return; 0 2131 2131
1182 2131 st_range_assign_rec(h->hdr, st_nodes(h), 1, 0, h->size - 1, i, i, val);
1183 }
1184  
1185 /* reset every position to 0 (caller holds the write lock) */
1186 3 static inline void st_clear_locked(StHandle *h) {
1187 3 StNode *nodes = st_nodes(h);
1188 3 uint64_t node_count = 2 * h->size;
1189 3 uint64_t nmax = st_nodes_max(h); /* Layer B: clamp to the mapping */
1190 3 ▶ if (node_count > nmax) node_count = nmax;
Branch: 1 branch
BranchTrueFalseTotal
if (node_count > nmax) node_count = nmax; 0 3 3
1191 3 ▶ if (node_count < 2) return;
Branch: 1 branch
BranchTrueFalseTotal
if (node_count < 2) return; 0 3 3
1192 /* A 0 assigned at the root reads as the cleared tree while the nodes under it are zeroed. */
1193 3 st_apply_assign(&nodes[1], 0, h->size);
1194 3 __atomic_signal_fence(__ATOMIC_SEQ_CST);
1195 3 memset(nodes + 2, 0, (size_t)((node_count - 2) * sizeof(StNode)));
1196 3 __atomic_signal_fence(__ATOMIC_SEQ_CST);
1197 3 memset(nodes, 0, 2 * sizeof(StNode)); /* every aggregate + lazy = 0 */
1198 3 __atomic_store_n(&h->hdr->add_used, 0, __ATOMIC_RELAXED); /* atomic: monoids_valid reads add_used unlocked -- a cleared tree is gcd/product-capable again */
1199 }
1200  
1201 /* Each node's lazy tags are authoritative after a writer killed mid range op,
1202 * once a journaled push-down still holding its add has landed: recompute every
1203 * aggregate bottom-up from its children and its own tag (a leaf's value is its
1204 * sum), so the op reads as partly applied. Idempotent. */
1205 0 static void st_repair_locked(StHandle *h) {
1206 0 StHeader *hdr = h->hdr;
1207 0 StNode *nodes = st_nodes(h);
1208 0 uint64_t size = h->size;
1209 0 ▶ if (size == 0 || 2 * size > st_nodes_max(h)) return;
Branch: 2 branches
BranchTrueFalseTotal
if (size == 0 || 2 * size > st_nodes_max(h)) return; 0 0 0
if (size == 0 || 2 * size > st_nodes_max(h)) return; 0 0 0
1210 0 uint64_t pv = hdr->pd_node;
1211 0 ▶ if (pv && pv < size && !(nodes[pv].flags & ST_F_HAS_ASSIGN) &&
Branch: 3 branches
BranchTrueFalseTotal
if (pv && pv < size && !(nodes[pv].flags & ST_F_HAS_ASSIGN) && 0 0 0
if (pv && pv < size && !(nodes[pv].flags & ST_F_HAS_ASSIGN) && 0 0 0
if (pv && pv < size && !(nodes[pv].flags & ST_F_HAS_ASSIGN) && 0 0 0
1212 0 ▶ nodes[pv].lazy && nodes[pv].lazy == hdr->pd_delta) {
Branch: 2 branches
BranchTrueFalseTotal
nodes[pv].lazy && nodes[pv].lazy == hdr->pd_delta) { 0 0 0
nodes[pv].lazy && nodes[pv].lazy == hdr->pd_delta) { 0 0 0
1213 0 int leaf = 2 * pv >= size;
1214 0 *st_add_tag(&nodes[2*pv], leaf) = hdr->pd_tag[0];
1215 0 *st_add_tag(&nodes[2*pv + 1], leaf) = hdr->pd_tag[1];
1216 0 __atomic_signal_fence(__ATOMIC_SEQ_CST);
1217 0 nodes[pv].lazy = 0;
1218 }
1219 0 __atomic_signal_fence(__ATOMIC_SEQ_CST);
1220 0 hdr->pd_node = 0;
1221 0 ▶ for (uint64_t v = size; v < 2 * size; v++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint64_t v = size; v < 2 * size; v++) { 0 0 0
1222 0 StNode *nd = &nodes[v];
1223 0 nd->min = nd->max = nd->prod = nd->sum;
1224 0 nd->gcd = st_gcd2(nd->sum, 0);
1225 0 nd->flags &= ~ST_F_PROD_OVF;
1226 }
1227 0 ▶ for (uint64_t v = size - 1; v >= 1; v--) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint64_t v = size - 1; v >= 1; v--) { 0 0 0
1228 0 StNode *nd = &nodes[v];
1229 0 uint64_t cnt = size >> (63 - __builtin_clzll(v));
1230 0 ▶ if (nd->flags & ST_F_HAS_ASSIGN) { st_apply_assign(nd, nd->assign, cnt); continue; }
Branch: 1 branch
BranchTrueFalseTotal
if (nd->flags & ST_F_HAS_ASSIGN) { st_apply_assign(nd, nd->assign, cnt); continue; } 0 0 0
1231 0 st_pull(nodes, v);
1232 0 nd->sum += nd->lazy * (int64_t)cnt;
1233 0 nd->min += nd->lazy;
1234 0 nd->max += nd->lazy;
1235 }
1236 }
1237  
1238 #endif /* ST_H */
« blib/lib/Data/SegmentTree/Shared.pm ↑ Summary Shared.xs »