roaring.h

filter: Statementstmt 78.9% 682 / 864 Branchbran 57.9% 341 / 588 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 70.4% 1023 / 1452 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« blib/lib/Data/RoaringBitmap/Shared.pm ↑ Summary Shared.xs »
1 /*
2 * roaring.h -- Shared-memory Roaring bitmap (compressed uint32 set) for Linux
3 *
4 * A Roaring bitmap is a compressed set of 32-bit unsigned integers. The 32-bit
5 * space is split into 65536 buckets keyed by the high 16 bits; each bucket holds
6 * the low 16 bits of its members in one of two container kinds, chosen by
7 * density:
8 *
9 * - array container : a SORTED ascending uint16 array (good when the bucket is
10 * sparse, <= 4096 elements).
11 * - bitmap container: a 65536-bit bitmap (good when the bucket is dense).
12 *
13 * A bucket starts as an array and is converted to a bitmap once it would exceed
14 * RB_ARRAY_MAX (4096) elements. Both kinds occupy one fixed 8192-byte slot
15 * (4096 * sizeof(uint16) == 1024 * sizeof(uint64) == 8192), drawn from a slot
16 * pool with a freelist, so several processes share one bitmap in a shared
17 * mapping. A write-preferring futex rwlock with reader-slot dead-process
18 * recovery guards mutation.
19 *
20 * contains / cardinality / min / max / to_array are pure reads under the READ
21 * lock; add / remove / clear / union / intersect take the WRITE lock.
22 *
23 * v1 scope: array + bitmap containers (no run containers); union and intersect
24 * only (no xor / andnot yet); bitmap containers are NOT down-converted to arrays
25 * on removal.
26 *
27 * Layout: Header -> reader_slots[1024] -> occ_bitmap -> bucket_table[65536] -> container_pool[container_cap]
28 */
29  
30 #ifndef ROARING_H
31 #define ROARING_H
32  
33 #include <stdint.h>
34 #include <stddef.h>
35 #include <stdlib.h>
36 #include <string.h>
37 #include <unistd.h>
38 #include <fcntl.h>
39 #include <errno.h>
40 #include <time.h>
41 #include <limits.h>
42 #include <signal.h>
43 #include <stdio.h>
44 #include <sys/mman.h>
45 #include <sys/stat.h>
46 #include <sys/file.h>
47 #include <sys/syscall.h>
48 #include <sys/random.h>
49 #include <linux/futex.h>
50 #include <pthread.h>
51  
52 #if defined(__BYTE_ORDER__) && __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
53 #error "roaring.h: requires little-endian architecture"
54 #endif
55  
56  
57 /* ================================================================
58 * Constants
59 * ================================================================ */
60  
61 #define RB_MAGIC 0x474E5252U /* "RRNG" (little-endian) */
62 #define RB_VERSION 2 /* 2: added the occupancy bitmap region (layout change) */
63 #define RB_ERR_BUFLEN (PATH_MAX + 256)
64 #define RB_READER_SLOTS 1024 /* max concurrent reader processes for dead-process recovery */
65  
66 /* Occupancy bitmap: one bit per reader slot, set when a process claims a slot and
67 * cleared on clean release. A writer scans these RB_OCC_WORDS words to visit only
68 * OCCUPIED slots (O(words + live readers)) instead of all RB_READER_SLOTS. */
69 #define RB_OCC_WORDS (((RB_READER_SLOTS) + 63) / 64) /* 16 for 1024 slots */
70 #define RB_OCC_BYTES ((uint64_t)RB_OCC_WORDS * 8) /* 128 bytes */
71 #define RB_NUM_BUCKETS 65536u /* one bucket per high-16 value */
72 #define RB_CONTAINER_BYTES 8192u /* 4096*2 == 1024*8: array and bitmap share this size */
73 #define RB_ARRAY_MAX 4096u /* convert array -> bitmap when an array would exceed this */
74 #define RB_MAX_CONTAINERS (1u << 20) /* container-pool ceiling; slot index 0 is the NULL sentinel */
75  
76 /* Container types (stored in bucket_table[hi].type) */
77 #define RB_TYPE_NONE 0u
78 #define RB_TYPE_ARRAY 1u
79 #define RB_TYPE_BITMAP 2u
80 #define RB_PUB_CLEAR (RB_NUM_BUCKETS + 1u)
81  
82 #define RB_ERR(fmt, ...) do { if (errbuf) snprintf(errbuf, RB_ERR_BUFLEN, fmt, ##__VA_ARGS__); } while (0)
83  
84 /* ================================================================
85 * Structs
86 * ================================================================ */
87  
88 /* Direct-indexed bucket entry, one per high-16 value. container_off == 0 means
89 * the bucket is empty (slot index 0 is the reserved NULL sentinel, never a real
90 * container). When non-empty, container_off is the 1-based slot index into the
91 * container pool and `type` selects the interpretation of that slot. */
92 typedef struct {
93 uint32_t container_off; /* 1-based slot index; 0 == empty bucket */
94 uint32_t cardinality; /* number of members in this bucket (1..65536) */
95 uint32_t type; /* RB_TYPE_NONE / RB_TYPE_ARRAY / RB_TYPE_BITMAP */
96 uint32_t _pad; /* pad to 16 bytes for clean alignment */
97 } RbBucket;
98  
99 _Static_assert(sizeof(RbBucket) == 16, "RbBucket must be 16 bytes");
100  
101 /* Per-process slot for dead-process recovery. In the reader-slots-only rwlock a
102 * reader's ENTIRE contribution to the shared lock is `rdepth` in its OWN slot --
103 * there is no separate shared reader counter to fall out of sync with it -- so a
104 * dead reader's contribution is exactly this one word, which a draining writer
105 * neutralises by clearing the slot's pid (the scan then ignores the slot). No
106 * orphaned counter can exist, so there is no quiescent force-reset and sustained
107 * readers cannot starve a writer. _rsv1/_rsv2 are kept only to preserve the
108 * 16-byte slot size across the already-released builds. */
109 typedef struct {
110 uint32_t pid; /* 0 = unclaimed */
111 uint32_t rdepth; /* read-locks THIS process currently holds (recursion-safe) */
112 uint32_t _rsv1; /* reserved (was waiters_parked); unused, kept for layout size */
113 uint32_t _rsv2; /* reserved (was writers_parked); unused, kept for layout size */
114 } RbReaderSlot;
115  
116 struct RbHeader {
117 uint32_t magic, version; /* 0,4 */
118 uint32_t container_cap; /* 8 container-pool capacity (slots, incl. NULL sentinel) */
119 uint32_t container_used; /* 12 1-based high-water of slots allocated since creation/last clear (slot 0 reserved) */
120 uint32_t free_head; /* 16 freelist head (slot index, 0 == empty) */
121 uint32_t free_count; /* 20 number of slots on the freelist (O(1) capacity check) */
122 uint64_t bitmap_id; /* 24 per-bitmap identity (random, set once at create, never 0);
123 * orders set-op lock acquisition consistently across processes */
124 uint64_t cardinality; /* 32 TOTAL elements across all buckets */
125 uint64_t total_size; /* 40 */
126 uint64_t reader_slots_off; /* 48 */
127 uint64_t bucket_table_off; /* 56 */
128 uint64_t container_pool_off; /* 64 */
129 uint32_t wlock; /* 72 WRITER word ONLY: 0 (free) or WRITER_BIT|pid. NOT a reader count. */
130 uint32_t rwait; /* 76 parked-waiter hint (readers+writers blocked on wlock); over-count-safe */
131 uint32_t drain_seq; /* 80 futex bumped by a reader releasing under a draining writer (wakes it) */
132 uint32_t slotless_rdepth; /* 84 readers holding with no reader-slot (documented residual); also aligns stat_ops */
133 uint64_t stat_ops; /* 88 */
134 uint8_t sealed; /* 96 0 = mutable, 1 = frozen (read-only; lock-free reads) */
135 uint8_t _pad0[3]; /* 97..99 */
136 uint32_t pub_hi; /* 100 1 + bucket of a switch, RB_PUB_CLEAR, or 0 = none */
137 RbBucket pub; /* 104 that switch's new bucket value, replayed by recovery */
138 uint8_t _pad1[136]; /* 120..255 */
139 };
140 typedef struct RbHeader RbHeader;
141  
142 _Static_assert(sizeof(RbHeader) == 256, "RbHeader must be 256 bytes");
143 _Static_assert(offsetof(RbHeader, pub_hi) / 64 == offsetof(RbHeader, wlock) / 64
144 && (offsetof(RbHeader, pub) + sizeof(RbBucket) - 1) / 64 == offsetof(RbHeader, wlock) / 64,
145 "the switch record shares the write lock's cache line");
146  
147 /* ---- Process-local handle ---- */
148  
149 typedef struct RbHandle {
150 RbHeader *hdr;
151 RbReaderSlot *reader_slots; /* RB_READER_SLOTS entries */
152 uint64_t *occ; /* RB_OCC_WORDS-word slot-occupancy bitmap (trusted layout offset) */
153 RbBucket *bucket_table; /* cached from trusted layout, not the peer-writable header offset */
154 uint8_t *pool; /* cached container-pool base (trusted layout) */
155 void *base; /* mmap base */
156 size_t mmap_size;
157 char *path; /* backing file path (strdup'd) */
158 int backing_fd; /* memfd or reopened-fd to close on destroy, -1 for file/anon */
159 uint32_t container_cap; /* cached fixed geometry, validated in range at attach */
160 uint32_t my_slot_idx; /* UINT32_MAX if all slots taken (no recovery for this handle) */
161 uint32_t cached_pid; /* getpid() cached at last slot claim */
162 uint32_t cached_fork_gen;/* rb_fork_gen value at last slot claim */
163 uint32_t slotless_held; /* read-locks this process holds with no reader-slot */
164 int readonly; /* 1 = frozen O_RDONLY/PROT_READ view: lock-free reads, mutation croaks */
165 } RbHandle;
166  
167 /* ================================================================
168 * Futex-based write-preferring read-write lock (reader-slots-only)
169 * with dead-process recovery
170 *
171 * The reader count is NOT stored in a shared counter. It is DISTRIBUTED across
172 * per-process reader slots: each slot's `rdepth` is that process's entire
173 * contribution to the lock. A reader publishes its presence in its own slot and
174 * then re-checks the writer word; a writer publishes the writer word and then
175 * scans every slot until all live readers' rdepth reach 0. Sequentially-
176 * consistent store+load on each side (a Dekker handshake) gives mutual exclusion.
177 *
178 * Because a reader's whole contribution is ONE atomic word owned by ONE process,
179 * a crashed reader is recovered by clearing that one slot (CAS its pid to 0) --
180 * there is no second counter to strand, no orphaned +1, and therefore no
181 * quiescent force-reset. A reader killed anywhere in rdlock/rdunlock leaves at
182 * most `rdepth>0` in its dead slot, which the draining writer clears directly, so
183 * sustained read traffic can never starve a writer. Write-preference is inherent
184 * in the gate (new readers see wlock!=0 and yield), so there is no reader-count
185 * yield hack.
186 * ================================================================ */
187  
188 #define RB_RWLOCK_SPIN_LIMIT 32
189 #define RB_LOCK_TIMEOUT_SEC 2 /* FUTEX_WAIT timeout for stale-lock detection / drain re-scan */
190  
191 0 static inline void rb_rwlock_spin_pause(void) {
192 #if defined(__x86_64__) || defined(__i386__)
193 0 __asm__ volatile("pause" ::: "memory");
194 #elif defined(__aarch64__)
195 __asm__ volatile("yield" ::: "memory");
196 #else
197 __asm__ volatile("" ::: "memory");
198 #endif
199 0 }
200  
201 /* Writer word encoding: WRITER_BIT|pid when write-locked, 0 when free. */
202 #define RB_RWLOCK_WRITER_BIT 0x80000000U
203 #define RB_RWLOCK_PID_MASK 0x7FFFFFFFU
204 #define RB_RWLOCK_WR(pid) (RB_RWLOCK_WRITER_BIT | ((uint32_t)(pid) & RB_RWLOCK_PID_MASK))
205  
206 /* A zombie (dead but not yet reaped) still answers kill(pid,0) as alive, so a
207 * process that crashed while holding the lock and lingers unreaped would never
208 * be recovered. Treat /proc/<pid>/stat state 'Z' as dead. Linux-only (as is
209 * this module); if /proc is unreadable we fall back to "alive" (safe: we never
210 * force-recover a possibly-live holder). */
211 0 static inline int rb_pid_is_zombie(uint32_t pid) {
212 char path[32], buf[256];
213 0 snprintf(path, sizeof(path), "/proc/%u/stat", (unsigned)pid);
214 0 int fd = open(path, O_RDONLY | O_CLOEXEC);
215 0 ▶ if (fd < 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (fd < 0) return 0; 0 0 0
216 0 ssize_t n = read(fd, buf, sizeof(buf) - 1);
217 0 close(fd);
218 0 ▶ if (n <= 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (n <= 0) return 0; 0 0 0
219 0 buf[n] = '\0';
220 /* "pid (comm) state ..."; comm may contain ')', so scan to the last one. */
221 0 char *rp = strrchr(buf, ')');
222 0 ▶ if (!rp || rp + 2 >= buf + n) return 0; /* need ") X" within the bytes read */
Branch: 2 branches
BranchTrueFalseTotal
if (!rp || rp + 2 >= buf + n) return 0; /* need ") X" within the bytes read */ 0 0 0
if (!rp || rp + 2 >= buf + n) return 0; /* need ") X" within the bytes read */ 0 0 0
223 0 ▶ return rp[1] == ' ' && rp[2] == 'Z';
Branch: 2 branches
BranchTrueFalseTotal
return rp[1] == ' ' && rp[2] == 'Z'; 0 0 0
return rp[1] == ' ' && rp[2] == 'Z'; 0 0 0
224 }
225 /* 1 if alive or unknown, 0 if definitely dead. Cannot detect PID reuse: a
226 * recycled PID reports "alive" and the slot is not reclaimed until that
227 * process exits. See "Crash Safety" in the POD. */
228 10 static inline int rb_pid_alive(uint32_t pid) {
229 10 ▶ 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 10 10
230 10 ▶ 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 */ 10 0 10
if (kill((pid_t)pid, 0) == -1 && errno == ESRCH) return 0; /* definitely dead */ 10 0 10
231 0 return !rb_pid_is_zombie(pid); /* kill() also succeeds for a zombie -> treat as dead */
232 }
233  
234 static void rb_drain_readers(RbHandle *h);
235 static void rb_repair_locked(RbHandle *h);
236  
237 /* Force-recover a stale WRITE lock left by a dead writer (held or mid-drain).
238 * CAS to OUR pid to hold the lock while fixing shared state, then release.
239 * Using our pid (not a bare WRITER_BIT sentinel) means a subsequent recovering
240 * process can detect and re-recover if we crash mid-recovery. */
241 10 static inline void rb_recover_stale_lock(RbHandle *h, uint32_t observed_wlock) {
242 10 RbHeader *hdr = h->hdr;
243 10 uint32_t mypid = RB_RWLOCK_WR((uint32_t)getpid());
244 10 ▶ if (!__atomic_compare_exchange_n(&hdr->wlock, &observed_wlock,
Branch: 1 branch
BranchTrueFalseTotal
if (!__atomic_compare_exchange_n(&hdr->wlock, &observed_wlock, 0 10 10
245 mypid, 0, __ATOMIC_ACQUIRE, __ATOMIC_RELAXED))
246 0 return;
247 /* The dead writer may have been mid-drain, so readers can still hold. */
248 10 rb_drain_readers(h);
249 10 rb_repair_locked(h);
250 10 __atomic_store_n(&hdr->wlock, 0, __ATOMIC_RELEASE);
251 10 ▶ if (__atomic_load_n(&hdr->rwait, __ATOMIC_RELAXED) > 0)
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&hdr->rwait, __ATOMIC_RELAXED) > 0) 0 10 10
252 0 syscall(SYS_futex, &hdr->wlock, FUTEX_WAKE, INT_MAX, NULL, NULL, 0);
253 }
254  
255 static const struct timespec rb_lock_timeout = { RB_LOCK_TIMEOUT_SEC, 0 };
256  
257 /* Process-global fork-generation counter. Incremented in the pthread_atfork
258 * child callback so every open handle detects a fork transition on the next
259 * lock call without paying a getpid() syscall on the hot path. */
260 static uint32_t rb_fork_gen = 1;
261 static pthread_once_t rb_atfork_once = PTHREAD_ONCE_INIT;
262 0 static void rb_on_fork_child(void) {
263 0 __atomic_add_fetch(&rb_fork_gen, 1, __ATOMIC_RELAXED);
264 0 }
265 5 static void rb_atfork_init(void) {
266 5 pthread_atfork(NULL, NULL, rb_on_fork_child);
267 5 }
268  
269 /* Occupancy bitmap: set a slot's bit when it is claimed, clear it on clean
270 * release. SEQ_CST so a set bit is ordered before the slot's rdepth can go
271 * non-zero (bit set in claim, which precedes any rdlock), letting a writer's
272 * SEQ_CST bitmap scan never miss a slot a committed reader holds. */
273 70 static inline void rb_occ_set(RbHandle *h, uint32_t s) {
274 70 __atomic_fetch_or(&h->occ[s >> 6], (uint64_t)1 << (s & 63), __ATOMIC_SEQ_CST);
275 70 }
276 70 static inline void rb_occ_clear(RbHandle *h, uint32_t s) {
277 70 __atomic_fetch_and(&h->occ[s >> 6], ~((uint64_t)1 << (s & 63)), __ATOMIC_SEQ_CST);
278 70 }
279  
280 /* Ensure this process owns a reader slot. Called from the lock helpers so that
281 * fork()'d children pick up their own slot lazily instead of sharing the
282 * parent's. Hot-path is a single relaxed load + compare; only on a
283 * fork-generation mismatch do we touch getpid() and scan slots. */
284 62751 static inline void rb_claim_reader_slot(RbHandle *h) {
285 62751 uint32_t cur_gen = __atomic_load_n(&rb_fork_gen, __ATOMIC_RELAXED);
286 62751 ▶ 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)) 62681 70 62751
if (__builtin_expect(cur_gen == h->cached_fork_gen && h->my_slot_idx != UINT32_MAX, 1)) 62681 0 62681
287 62681 return;
288 /* Cold path -- register the atfork hook once per process, then claim. */
289 70 pthread_once(&rb_atfork_once, rb_atfork_init);
290 /* Re-read after pthread_once: rb_on_fork_child may have bumped it. */
291 70 cur_gen = __atomic_load_n(&rb_fork_gen, __ATOMIC_RELAXED);
292 70 uint32_t now_pid = (uint32_t)getpid();
293 70 h->cached_pid = now_pid;
294 70 ▶ 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 */ 70 0 70
295 70 h->cached_fork_gen = cur_gen;
296 70 h->my_slot_idx = UINT32_MAX;
297 70 uint32_t start = now_pid % RB_READER_SLOTS;
298 /* Pass 1: take a free slot. */
299 72 ▶ for (uint32_t i = 0; i < RB_READER_SLOTS; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t i = 0; i < RB_READER_SLOTS; i++) { 72 0 72
300 72 uint32_t s = (start + i) % RB_READER_SLOTS;
301 72 uint32_t expected = 0;
302 72 ▶ if (__atomic_compare_exchange_n(&h->reader_slots[s].pid,
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_compare_exchange_n(&h->reader_slots[s].pid, 70 2 72
303 &expected, now_pid, 0,
304 __ATOMIC_ACQUIRE, __ATOMIC_RELAXED)) {
305 /* Fresh owner holds no read locks yet; clear any stale rdepth left by
306 * a dead predecessor (its contribution is dropped as we take over). */
307 70 __atomic_store_n(&h->reader_slots[s].rdepth, 0, __ATOMIC_RELAXED);
308 70 rb_occ_set(h, s); /* mark occupied BEFORE any rdlock can bump rdepth */
309 70 h->my_slot_idx = s;
310 70 return;
311 }
312 }
313 /* Pass 2: no free slot -- reclaim one whose owner is dead. Safe to take even
314 * if its rdepth>0: clearing pid drops the dead reader's entire contribution
315 * (a writer scan ignores rdepth when pid==0) and we reset rdepth to 0 as we
316 * claim it. */
317 0 ▶ for (uint32_t i = 0; i < RB_READER_SLOTS; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t i = 0; i < RB_READER_SLOTS; i++) { 0 0 0
318 0 uint32_t dpid = __atomic_load_n(&h->reader_slots[i].pid, __ATOMIC_ACQUIRE);
319 0 ▶ if (dpid == 0 || dpid == now_pid || rb_pid_alive(dpid)) continue;
Branch: 3 branches
BranchTrueFalseTotal
if (dpid == 0 || dpid == now_pid || rb_pid_alive(dpid)) continue; 0 0 0
if (dpid == 0 || dpid == now_pid || rb_pid_alive(dpid)) continue; 0 0 0
if (dpid == 0 || dpid == now_pid || rb_pid_alive(dpid)) continue; 0 0 0
320 0 uint32_t expected = dpid;
321 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
322 __ATOMIC_ACQUIRE, __ATOMIC_RELAXED)) {
323 0 __atomic_store_n(&h->reader_slots[i].rdepth, 0, __ATOMIC_RELAXED);
324 0 rb_occ_set(h, i);
325 0 h->my_slot_idx = i;
326 0 return;
327 }
328 }
329 /* Table full -- leave my_slot_idx = UINT32_MAX so this handle takes the
330 * slotless path (lock still works; recovery of THIS reader's death is the
331 * documented slotless limitation). */
332 }
333  
334 /* Inspect the writer word after a futex-wait timeout. If a dead writer holds
335 * it, force-recover. Dead READERS need no action here: only a writer that owns
336 * wlock drains readers, and it clears dead readers inline in its own scan. */
337 0 static inline void rb_recover_after_timeout(RbHandle *h) {
338 0 uint32_t val = __atomic_load_n(&h->hdr->wlock, __ATOMIC_RELAXED);
339 0 ▶ if (val >= RB_RWLOCK_WRITER_BIT) {
Branch: 1 branch
BranchTrueFalseTotal
if (val >= RB_RWLOCK_WRITER_BIT) { 0 0 0
340 0 uint32_t pid = val & RB_RWLOCK_PID_MASK;
341 0 ▶ if (!rb_pid_alive(pid))
Branch: 1 branch
BranchTrueFalseTotal
if (!rb_pid_alive(pid)) 0 0 0
342 0 rb_recover_stale_lock(h, val);
343 }
344 0 }
345  
346 /* Bump/drop the parked-waiter hint. Both readers (blocked at the gate) and
347 * writers (blocked acquiring wlock) wait on the wlock futex and use this, so
348 * wrunlock/recover know whether a FUTEX_WAKE is worth a syscall. A waiter
349 * SIGKILLed while parked leaves rwait over-counted -> at most a spurious wake
350 * (harmless); it can never under-count, so no wakeup is lost. */
351 0 static inline void rb_park(RbHandle *h) {
352 0 __atomic_add_fetch(&h->hdr->rwait, 1, __ATOMIC_RELAXED);
353 0 }
354 0 static inline void rb_unpark(RbHandle *h) {
355 0 __atomic_sub_fetch(&h->hdr->rwait, 1, __ATOMIC_RELAXED);
356 0 }
357  
358 /* Publish (inc) / retract (dec) this reader's presence -- its ENTIRE
359 * contribution to the lock. A slotted reader uses its slot's rdepth; a reader
360 * that could not claim a slot uses the global slotless_rdepth. inc() is SEQ_CST
361 * so the wlock re-check that follows it in rdlock forms a Dekker handshake with
362 * the writer's SEQ_CST wlock-store + rdepth-scan. leave() peels slotless first
363 * so a slot claimed mid-hold cannot misattribute the decrement. */
364 13007 static inline void rb_rdepth_inc(RbHandle *h) {
365 13007 ▶ if (h->my_slot_idx != UINT32_MAX) {
Branch: 1 branch
BranchTrueFalseTotal
if (h->my_slot_idx != UINT32_MAX) { 13007 0 13007
366 13007 __atomic_add_fetch(&h->reader_slots[h->my_slot_idx].rdepth, 1, __ATOMIC_SEQ_CST);
367 } else {
368 0 __atomic_add_fetch(&h->hdr->slotless_rdepth, 1, __ATOMIC_SEQ_CST);
369 0 h->slotless_held++;
370 }
371 13007 }
372 13007 static inline void rb_rdepth_dec(RbHandle *h) {
373 13007 ▶ if (h->slotless_held > 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (h->slotless_held > 0) { 0 13007 13007
374 0 h->slotless_held--;
375 0 __atomic_sub_fetch(&h->hdr->slotless_rdepth, 1, __ATOMIC_RELEASE);
376 13007 ▶ } else if (h->my_slot_idx != UINT32_MAX) {
Branch: 1 branch
BranchTrueFalseTotal
} else if (h->my_slot_idx != UINT32_MAX) { 13007 0 13007
377 13007 __atomic_sub_fetch(&h->reader_slots[h->my_slot_idx].rdepth, 1, __ATOMIC_RELEASE);
378 }
379 13007 }
380  
381 /* Wake a writer that may be draining readers (it waits on drain_seq). Called
382 * after every rdepth decrement so a released read lock lets the writer re-scan
383 * promptly instead of waiting out its timeout. */
384 13007 static inline void rb_reader_wake_drain(RbHandle *h) {
385 13007 ▶ 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 13007 13007
386 0 __atomic_add_fetch(&h->hdr->drain_seq, 1, __ATOMIC_RELEASE);
387 0 syscall(SYS_futex, &h->hdr->drain_seq, FUTEX_WAKE, 1, NULL, NULL, 0);
388 }
389 13007 }
390  
391 13007 static inline void rb_rwlock_rdlock(RbHandle *h) {
392 13007 rb_claim_reader_slot(h);
393 13007 RbHeader *hdr = h->hdr;
394 13017 for (int spin = 0; ; spin++) {
395 13017 uint32_t cur = __atomic_load_n(&hdr->wlock, __ATOMIC_ACQUIRE);
396 13017 ▶ if (cur == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (cur == 0) { 13007 10 13017
397 /* Optimistically take the read: publish rdepth, then re-check wlock.
398 * SEQ_CST inc + SEQ_CST load vs the writer's SEQ_CST wlock CAS +
399 * SEQ_CST rdepth scan: by the single total order of SEQ_CST ops the
400 * two sides cannot both miss each other, so we never hold
401 * concurrently with a writer. */
402 13007 rb_rdepth_inc(h);
403 13007 ▶ if (__atomic_load_n(&hdr->wlock, __ATOMIC_SEQ_CST) == 0)
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&hdr->wlock, __ATOMIC_SEQ_CST) == 0) 13007 0 13007
404 13007 return; /* no writer after our publish -> we hold the read lock */
405 /* A writer appeared during our publish -- yield to it (write-preferring). */
406 0 rb_rdepth_dec(h);
407 0 rb_reader_wake_drain(h); /* let the draining writer see rdepth drop */
408 0 spin = 0;
409 0 continue;
410 }
411 /* wlock != 0: a writer holds or is acquiring. Recover if it is dead. */
412 20 if (cur >= RB_RWLOCK_WRITER_BIT &&
413 10 !rb_pid_alive(cur & RB_RWLOCK_PID_MASK)) {
414 10 rb_recover_stale_lock(h, cur);
415 10 spin = 0;
416 10 continue;
417 }
418 0 ▶ if (__builtin_expect(spin < RB_RWLOCK_SPIN_LIMIT, 1)) {
Branch: 1 branch
BranchTrueFalseTotal
if (__builtin_expect(spin < RB_RWLOCK_SPIN_LIMIT, 1)) { 0 0 0
419 0 rb_rwlock_spin_pause();
420 0 continue;
421 }
422 0 rb_park(h);
423 0 cur = __atomic_load_n(&hdr->wlock, __ATOMIC_RELAXED);
424 0 ▶ if (cur != 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (cur != 0) { 0 0 0
425 0 long rc = syscall(SYS_futex, &hdr->wlock, FUTEX_WAIT, cur,
426 &rb_lock_timeout, NULL, 0);
427 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
428 0 rb_unpark(h);
429 0 rb_recover_after_timeout(h);
430 0 spin = 0;
431 0 continue;
432 }
433 }
434 0 rb_unpark(h);
435 0 spin = 0;
436 }
437 }
438  
439 13007 static inline void rb_rwlock_rdunlock(RbHandle *h) {
440 13007 rb_rdepth_dec(h); /* RELEASE: drop our entire contribution */
441 13007 rb_reader_wake_drain(h); /* if a writer is draining, wake it to re-scan */
442 13007 }
443  
444 49744 static inline void rb_rwlock_wrlock(RbHandle *h) {
445 49744 rb_claim_reader_slot(h); /* refresh cached_pid across fork */
446 49744 RbHeader *hdr = h->hdr;
447 /* Encode PID in the wlock word itself (0x80000000 | pid) to eliminate any
448 * crash window between acquiring the lock and storing the owner. */
449 49744 uint32_t mypid = RB_RWLOCK_WR(h->cached_pid);
450 /* Phase 1: acquire the writer word (mutual exclusion among writers). */
451 49744 for (int spin = 0; ; spin++) {
452 49744 uint32_t expected = 0;
453 49744 ▶ if (__atomic_compare_exchange_n(&hdr->wlock, &expected, mypid,
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_compare_exchange_n(&hdr->wlock, &expected, mypid, 49744 0 49744
454 0, __ATOMIC_SEQ_CST, __ATOMIC_RELAXED))
455 49744 break;
456 /* Contended: expected now holds the current wlock value. */
457 0 if (expected >= RB_RWLOCK_WRITER_BIT &&
458 0 !rb_pid_alive(expected & RB_RWLOCK_PID_MASK)) {
459 0 rb_recover_stale_lock(h, expected);
460 0 spin = 0;
461 0 continue;
462 }
463 0 ▶ if (__builtin_expect(spin < RB_RWLOCK_SPIN_LIMIT, 1)) {
Branch: 1 branch
BranchTrueFalseTotal
if (__builtin_expect(spin < RB_RWLOCK_SPIN_LIMIT, 1)) { 0 0 0
464 0 rb_rwlock_spin_pause();
465 0 continue;
466 }
467 0 rb_park(h);
468 0 uint32_t cur = __atomic_load_n(&hdr->wlock, __ATOMIC_RELAXED);
469 0 ▶ if (cur != 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (cur != 0) { 0 0 0
470 0 long rc = syscall(SYS_futex, &hdr->wlock, FUTEX_WAIT, cur,
471 &rb_lock_timeout, NULL, 0);
472 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
473 0 rb_unpark(h);
474 0 rb_recover_after_timeout(h);
475 0 spin = 0;
476 0 continue;
477 }
478 }
479 0 rb_unpark(h);
480 0 spin = 0;
481 }
482 49744 rb_drain_readers(h);
483 49744 }
484  
485 /* Phase 2 of taking the write lock: we own wlock, so no NEW reader can join
486 * (they see wlock!=0 and yield). Drain the readers that were already holding
487 * when we won the CAS. The SEQ_CST CAS on wlock + the SEQ_CST rdepth loads below
488 * are the writer side of the Dekker handshake. */
489 49754 static void rb_drain_readers(RbHandle *h) {
490 49754 RbHeader *hdr = h->hdr;
491 0 for (;;) {
492 49754 uint32_t v = __atomic_load_n(&hdr->drain_seq, __ATOMIC_ACQUIRE); /* snapshot BEFORE scan */
493 49754 int busy = 0;
494 /* Visit only OCCUPIED slots via the occupancy bitmap (SEQ_CST: a committed
495 * reader's bit -- set in claim, before its rdepth++ -- is ordered before
496 * this scan, so no held slot is skipped). O(RB_OCC_WORDS + live readers)
497 * instead of O(RB_READER_SLOTS). */
498 845818 ▶ for (uint32_t w = 0; w < RB_OCC_WORDS; w++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t w = 0; w < RB_OCC_WORDS; w++) { 796064 49754 845818
499 796064 uint64_t word = __atomic_load_n(&h->occ[w], __ATOMIC_SEQ_CST);
500 845819 ▶ while (word) {
Branch: 1 branch
BranchTrueFalseTotal
while (word) { 49755 796064 845819
501 49755 uint32_t i = (w << 6) + (uint32_t)__builtin_ctzll(word);
502 49755 word &= word - 1; /* consume this bit (local copy) */
503 49755 uint32_t rd = __atomic_load_n(&h->reader_slots[i].rdepth, __ATOMIC_SEQ_CST);
504 49755 ▶ if (rd == 0) continue; /* occupied but not read-locking now */
Branch: 1 branch
BranchTrueFalseTotal
if (rd == 0) continue; /* occupied but not read-locking now */ 49755 0 49755
505 0 uint32_t pid = __atomic_load_n(&h->reader_slots[i].pid, __ATOMIC_ACQUIRE);
506 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
507 0 ▶ if (!rb_pid_alive(pid)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!rb_pid_alive(pid)) { 0 0 0
508 /* Dead reader: drop its pid so the slot no longer counts. Leave
509 * the occ bit set (harmless -- a later scan hits pid==0 and skips,
510 * a re-claim re-sets it) to avoid racing a concurrent claimant. */
511 0 uint32_t ep = pid;
512 0 __atomic_compare_exchange_n(&h->reader_slots[i].pid, &ep, 0,
513 0, __ATOMIC_ACQ_REL, __ATOMIC_RELAXED);
514 0 continue;
515 }
516 0 busy = 1; /* live reader still holding */
517 }
518 }
519 /* A live slotless reader keeps us waiting; a crashed slotless reader that
520 * cannot be attributed to a pid is the documented slotless limitation. */
521 49754 ▶ 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 49754 49754
522 0 busy = 1;
523 49754 ▶ if (!busy)
Branch: 1 branch
BranchTrueFalseTotal
if (!busy) 49754 0 49754
524 49754 return; /* exclusive: wlock held + every rdepth 0 */
525 /* Wait for a reader to release (drain_seq bump) or time out to re-scan
526 * (which reclaims any newly-dead slotted reader). */
527 0 syscall(SYS_futex, &hdr->drain_seq, FUTEX_WAIT, v, &rb_lock_timeout, NULL, 0);
528 }
529 }
530  
531 49744 static inline void rb_rwlock_wrunlock(RbHandle *h) {
532 49744 RbHeader *hdr = h->hdr;
533 49744 __atomic_store_n(&hdr->wlock, 0, __ATOMIC_RELEASE);
534 49744 ▶ if (__atomic_load_n(&hdr->rwait, __ATOMIC_RELAXED) > 0)
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&hdr->rwait, __ATOMIC_RELAXED) > 0) 0 49744 49744
535 0 syscall(SYS_futex, &hdr->wlock, FUTEX_WAKE, INT_MAX, NULL, NULL, 0);
536 49744 }
537  
538 /* ================================================================
539 * Layout math + bucket-table / container-pool accessors
540 *
541 * Layout: Header -> reader_slots[1024] -> occ bitmap -> bucket_table[65536] -> container_pool
542 * RbReaderSlot is 16 bytes and RbBucket is 16 bytes, and the occ bitmap is 128
543 * bytes (16 * uint64), so every region begins on a 16-byte boundary; container
544 * slots are 8192 bytes (8-byte aligned for the uint64 bitmap interpretation).
545 * ================================================================ */
546  
547 typedef struct { uint64_t reader_slots, occ, bucket_table, container_pool; } RbLayout;
548  
549 346 static inline RbLayout rb_layout(void) {
550 RbLayout L;
551 346 L.reader_slots = sizeof(RbHeader);
552 346 L.occ = L.reader_slots + (uint64_t)RB_READER_SLOTS * sizeof(RbReaderSlot);
553 346 L.bucket_table = L.occ + RB_OCC_BYTES;
554 346 L.container_pool = L.bucket_table + (uint64_t)RB_NUM_BUCKETS * sizeof(RbBucket);
555 346 return L;
556 }
557  
558 182 static inline uint64_t rb_total_size(uint32_t container_cap) {
559 182 RbLayout L = rb_layout();
560 182 return L.container_pool + (uint64_t)container_cap * RB_CONTAINER_BYTES;
561 }
562  
563 /* bucket_table / container-pool base pointers come from the cached trusted
564 * layout, NOT the peer-writable header offsets: a lock-violating peer that
565 * corrupts hdr->bucket_table_off / hdr->container_pool_off after we attached
566 * would otherwise redirect every bucket/slot access to a wild pointer. */
567 437751 static inline RbBucket *rb_buckets(RbHandle *h) {
568 437751 return h->bucket_table;
569 }
570 423926 static inline uint8_t *rb_pool(RbHandle *h) {
571 423926 return h->pool;
572 }
573 /* Base pointer of container slot `i` (1-based; i==0 is the NULL sentinel).
574 * `i` originates from a bucket's file-stored container_off, which a local peer
575 * can corrupt to an out-of-range slot; clamp to the reserved sentinel (0) so the
576 * returned pointer always lands inside the container pool. The clamp bound is
577 * the cached container_cap (fixed geometry validated at attach and sizing the
578 * mmap), never the live peer-writable hdr->container_cap. */
579 423926 static inline void *rb_slot(RbHandle *h, uint32_t i) {
580 423926 ▶ if (i >= h->container_cap) i = 0;
Branch: 1 branch
BranchTrueFalseTotal
if (i >= h->container_cap) i = 0; 0 423926 423926
581 423926 return (void *)(rb_pool(h) + (size_t)i * RB_CONTAINER_BYTES);
582 }
583 /* An array container holds at most RB_ARRAY_MAX entries in its fixed-size slot;
584 * a corrupt file could store a larger cardinality and drive a search or scan
585 * past the slot. Clamp the file-stored count to the physical slot capacity. */
586 102354 static inline uint32_t rb_array_card(const RbBucket *bt) {
587 102354 return bt->cardinality > RB_ARRAY_MAX ? RB_ARRAY_MAX : bt->cardinality;
588 }
589 200728 static inline uint16_t *rb_array(RbHandle *h, uint32_t i) {
590 200728 return (uint16_t *)rb_slot(h, i);
591 }
592 28884 static inline uint64_t *rb_bitmap(RbHandle *h, uint32_t i) {
593 28884 return (uint64_t *)rb_slot(h, i);
594 }
595  
596 /* ================================================================
597 * Container-slot allocation (freelist). Callers hold the WRITE lock.
598 * ================================================================ */
599  
600 /* Number of container slots available to satisfy future allocations:
601 * fresh high-water headroom plus returned slots on the freelist. */
602 2585 static inline uint32_t rb_avail_slots(RbHandle *h) {
603 2585 RbHeader *hdr = h->hdr;
604 2585 return (hdr->container_cap - hdr->container_used) + hdr->free_count;
605 }
606  
607 /* Allocate one container slot, contents unspecified. Returns a 1-based slot
608 * index, or 0 if the pool is exhausted. Pops the freelist first (the freelist
609 * threads through the first 4 bytes of each freed slot), else bumps the
610 * high-water mark. */
611 98398 static inline uint32_t rb_alloc_slot_raw(RbHandle *h) {
612 98398 RbHeader *hdr = h->hdr;
613 uint32_t idx;
614 98398 ▶ if (hdr->free_head) {
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->free_head) { 95821 2577 98398
615 95821 idx = hdr->free_head;
616 95821 uint32_t next = *(uint32_t *)rb_slot(h, idx); /* next free slot */
617 /* Count before head: a kill between them under-counts, never over-counts an empty list. */
618 95821 hdr->free_count--;
619 95821 __atomic_signal_fence(__ATOMIC_SEQ_CST);
620 95821 hdr->free_head = next;
621 2577 ▶ } else if (hdr->container_used < hdr->container_cap) {
Branch: 1 branch
BranchTrueFalseTotal
} else if (hdr->container_used < hdr->container_cap) { 2576 1 2577
622 2576 idx = hdr->container_used++;
623 } else {
624 1 return 0;
625 }
626 98397 return idx;
627 }
628  
629 /* As rb_alloc_slot_raw, but the returned slot is fully zeroed. */
630 2585 static inline uint32_t rb_alloc_slot(RbHandle *h) {
631 2585 uint32_t idx = rb_alloc_slot_raw(h);
632 2585 ▶ if (idx) memset(rb_slot(h, idx), 0, RB_CONTAINER_BYTES);
Branch: 1 branch
BranchTrueFalseTotal
if (idx) memset(rb_slot(h, idx), 0, RB_CONTAINER_BYTES); 2585 0 2585
633 2585 return idx;
634 }
635  
636 /* Return a container slot to the freelist. */
637 95900 static inline void rb_free_slot(RbHandle *h, uint32_t i) {
638 95900 RbHeader *hdr = h->hdr;
639 95900 *(uint32_t *)rb_slot(h, i) = hdr->free_head;
640 95900 __atomic_signal_fence(__ATOMIC_SEQ_CST);
641 95900 hdr->free_head = i;
642 95900 hdr->free_count++;
643 95900 }
644  
645 /* Point bucket hi at a container built in a fresh slot. Its three words are
646 * separate stores, so the new value goes to the header record first and
647 * recovery replays it when a kill lands between them. */
648 95832 static inline void rb_switch_bucket(RbHandle *h, uint32_t hi, uint32_t off,
649 uint32_t card, uint32_t type) {
650 95832 RbHeader *hdr = h->hdr;
651 95832 RbBucket *bt = &rb_buckets(h)[hi];
652 95832 hdr->pub.container_off = off;
653 95832 hdr->pub.cardinality = card;
654 95832 hdr->pub.type = type;
655 95832 __atomic_signal_fence(__ATOMIC_SEQ_CST);
656 95832 __atomic_store_n(&hdr->pub_hi, hi + 1, __ATOMIC_RELAXED);
657 95832 __atomic_signal_fence(__ATOMIC_SEQ_CST);
658 95832 bt->container_off = off;
659 95832 bt->cardinality = card;
660 95832 bt->type = type;
661 95832 __atomic_signal_fence(__ATOMIC_SEQ_CST);
662 95832 __atomic_store_n(&hdr->pub_hi, 0, __ATOMIC_RELAXED);
663 95832 }
664  
665 /* Copy-on-write replacement of bucket hi's container: switch to the slot
666 * `fresh`, then free the old one (a kill between them only strands the old
667 * slot, which recovery reclaims). */
668 95832 static inline void rb_replace_container(RbHandle *h, uint32_t hi, uint32_t fresh,
669 uint32_t card, uint32_t type) {
670 95832 uint32_t old = rb_buckets(h)[hi].container_off;
671 95832 rb_switch_bucket(h, hi, fresh, card, type);
672 95832 __atomic_signal_fence(__ATOMIC_SEQ_CST);
673 95832 rb_free_slot(h, old);
674 95832 }
675  
676 /* Empty bucket hi and free its slot. The type unpublishes it first: a kill
677 * before the free only strands the slot, never leaves it shared. */
678 60 static inline void rb_unlink_bucket(RbHandle *h, uint32_t hi) {
679 60 RbBucket *bt = &rb_buckets(h)[hi];
680 60 uint32_t off = bt->container_off;
681 60 bt->type = RB_TYPE_NONE;
682 60 bt->container_off = 0;
683 60 bt->cardinality = 0;
684 60 __atomic_signal_fence(__ATOMIC_SEQ_CST);
685 60 rb_free_slot(h, off);
686 60 }
687  
688 /* Write a sorted array result into bucket hi: a fresh slot when one is free,
689 * else in place (a kill mid-copy then tears the container). */
690 244 static inline void rb_commit_array(RbHandle *h, uint32_t hi, const uint16_t *vals, uint32_t n) {
691 244 ▶ if (n == 0) { rb_unlink_bucket(h, hi); return; }
Branch: 1 branch
BranchTrueFalseTotal
if (n == 0) { rb_unlink_bucket(h, hi); return; } 59 185 244
692 185 uint32_t s = rb_alloc_slot_raw(h);
693 185 ▶ if (s) {
Branch: 1 branch
BranchTrueFalseTotal
if (s) { 185 0 185
694 185 memcpy(rb_array(h, s), vals, (size_t)n * sizeof(uint16_t));
695 185 rb_replace_container(h, hi, s, n, RB_TYPE_ARRAY);
696 185 return;
697 }
698 0 RbBucket *bt = &rb_buckets(h)[hi];
699 0 memcpy(rb_array(h, bt->container_off), vals, (size_t)n * sizeof(uint16_t));
700 0 bt->type = RB_TYPE_ARRAY;
701 0 bt->cardinality = n;
702 }
703  
704 /* ================================================================
705 * Bit / popcount helpers
706 * ================================================================ */
707  
708 7 static inline uint64_t rb_popcount_bitmap(const uint64_t *bits) {
709 7 uint64_t c = 0;
710 7175 ▶ for (uint32_t w = 0; w < 1024; w++) c += (uint64_t)__builtin_popcountll(bits[w]);
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t w = 0; w < 1024; w++) c += (uint64_t)__builtin_popcountll(bits[w]); 7168 7 7175
711 7 return c;
712 }
713  
714 /* Binary search for `lo` in a sorted uint16 array of `card` entries. Returns
715 * 1 and sets *pos to the index if found; returns 0 and sets *pos to the
716 * insertion point (lower bound) if absent. */
717 100399 static inline int rb_array_search(const uint16_t *vals, uint32_t card, uint16_t lo, uint32_t *pos) {
718 100399 uint32_t lo_i = 0, hi_i = card;
719 1100882 ▶ while (lo_i < hi_i) {
Branch: 1 branch
BranchTrueFalseTotal
while (lo_i < hi_i) { 1000483 100399 1100882
720 1000483 uint32_t mid = lo_i + ((hi_i - lo_i) >> 1);
721 1000483 ▶ if (vals[mid] < lo) lo_i = mid + 1;
Branch: 1 branch
BranchTrueFalseTotal
if (vals[mid] < lo) lo_i = mid + 1; 797453 203030 1000483
722 203030 else hi_i = mid;
723 }
724 100399 *pos = lo_i;
725 100399 ▶ return (lo_i < card && vals[lo_i] == lo);
Branch: 2 branches
BranchTrueFalseTotal
return (lo_i < card && vals[lo_i] == lo); 37716 62683 100399
return (lo_i < card && vals[lo_i] == lo); 1712 36004 37716
726 }
727  
728 /* ================================================================
729 * Single-bitmap operations. Callers hold the WRITE lock (mutators) or the
730 * READ lock (rb_contains_locked).
731 * ================================================================ */
732  
733 /* Convert bucket `hi`'s array container to a bitmap, in place (same slot).
734 * The slot is reinterpreted, so the array values are copied to a C-stack temp
735 * first. The array is at most RB_ARRAY_MAX entries (a full array container). */
736 0 static inline void rb_array_to_bitmap(RbHandle *h, uint32_t hi) {
737 0 RbBucket *bt = &rb_buckets(h)[hi];
738 0 uint32_t card = rb_array_card(bt);
739 uint16_t tmp[RB_ARRAY_MAX];
740 0 uint16_t *vals = rb_array(h, bt->container_off);
741 0 memcpy(tmp, vals, (size_t)card * sizeof(uint16_t));
742 0 uint64_t *bits = rb_bitmap(h, bt->container_off);
743 0 memset(bits, 0, RB_CONTAINER_BYTES);
744 0 ▶ for (uint32_t i = 0; i < card; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t i = 0; i < card; i++) { 0 0 0
745 0 uint16_t lo = tmp[i];
746 0 bits[lo >> 6] |= (uint64_t)1 << (lo & 63);
747 }
748 0 bt->type = RB_TYPE_BITMAP;
749 0 }
750  
751 /* Add x to the set. Returns 1 if newly added, 0 if already present. The
752 * caller has verified (under the lock) that a free slot exists when the target
753 * bucket is currently empty. */
754 114015 static inline int rb_add_locked(RbHandle *h, uint32_t x) {
755 114015 uint32_t hi = x >> 16;
756 114015 uint16_t lo = (uint16_t)(x & 0xffff);
757 114015 RbBucket *bt = &rb_buckets(h)[hi];
758  
759 114015 ▶ if (bt->type == RB_TYPE_NONE) {
Branch: 1 branch
BranchTrueFalseTotal
if (bt->type == RB_TYPE_NONE) { 2564 111451 114015
760 2564 uint32_t s = rb_alloc_slot(h); /* guaranteed available by caller */
761 2564 rb_array(h, s)[0] = lo;
762 2564 bt->container_off = s;
763 2564 bt->cardinality = 1;
764 /* The type publishes the bucket: everything it names goes first. */
765 2564 __atomic_signal_fence(__ATOMIC_SEQ_CST);
766 2564 bt->type = RB_TYPE_ARRAY;
767 2564 h->hdr->cardinality++;
768 2564 return 1;
769 }
770 111451 ▶ if (bt->type == RB_TYPE_ARRAY) {
Branch: 1 branch
BranchTrueFalseTotal
if (bt->type == RB_TYPE_ARRAY) { 95656 15795 111451
771 95656 uint16_t *vals = rb_array(h, bt->container_off);
772 95656 uint32_t card = rb_array_card(bt);
773 uint32_t pos;
774 95656 ▶ if (rb_array_search(vals, card, lo, &pos)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (rb_array_search(vals, card, lo, &pos)) return 0; 13 95643 95656
775 /* A full array container (RB_ARRAY_MAX entries) cannot hold one more
776 * value without overflowing its fixed-size slot; promote it to a
777 * bitmap FIRST, then set the bit. (The new value is genuinely absent,
778 * confirmed above, so this always grows the set.) */
779 95643 ▶ if (card >= RB_ARRAY_MAX) {
Branch: 1 branch
BranchTrueFalseTotal
if (card >= RB_ARRAY_MAX) { 18 95625 95643
780 18 uint32_t s = rb_alloc_slot(h);
781 18 ▶ if (s) {
Branch: 1 branch
BranchTrueFalseTotal
if (s) { 18 0 18
782 18 uint64_t *bits = rb_bitmap(h, s);
783 73746 ▶ for (uint32_t i = 0; i < card; i++)
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t i = 0; i < card; i++) 73728 18 73746
784 73728 bits[vals[i] >> 6] |= (uint64_t)1 << (vals[i] & 63);
785 18 bits[lo >> 6] |= (uint64_t)1 << (lo & 63);
786 18 rb_replace_container(h, hi, s, card + 1, RB_TYPE_BITMAP);
787 18 h->hdr->cardinality++;
788 18 return 1;
789 }
790 0 rb_array_to_bitmap(h, hi);
791 0 uint64_t *bits = rb_bitmap(h, bt->container_off);
792 0 bt->cardinality++;
793 0 __atomic_signal_fence(__ATOMIC_SEQ_CST);
794 0 bits[lo >> 6] |= (uint64_t)1 << (lo & 63);
795 0 h->hdr->cardinality++;
796 0 return 1;
797 }
798 95625 uint32_t s = rb_alloc_slot_raw(h);
799 95625 ▶ if (s) {
Branch: 1 branch
BranchTrueFalseTotal
if (s) { 95624 1 95625
800 95624 uint16_t *nv = rb_array(h, s);
801 95624 memcpy(nv, vals, (size_t)pos * sizeof(uint16_t));
802 95624 nv[pos] = lo;
803 95624 memcpy(nv + pos + 1, vals + pos, (size_t)(card - pos) * sizeof(uint16_t));
804 95624 rb_replace_container(h, hi, s, card + 1, RB_TYPE_ARRAY);
805 } else {
806 1 memmove(&vals[pos + 1], &vals[pos], (size_t)(card - pos) * sizeof(uint16_t));
807 1 vals[pos] = lo;
808 1 bt->cardinality++;
809 }
810 95625 h->hdr->cardinality++;
811 95625 return 1;
812 }
813 /* bitmap */
814 {
815 15795 uint64_t *bits = rb_bitmap(h, bt->container_off);
816 15795 uint32_t w = lo >> 6;
817 15795 uint64_t b = (uint64_t)1 << (lo & 63);
818 15795 ▶ if (bits[w] & b) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (bits[w] & b) return 0; 0 15795 15795
819 /* Count before bit: a kill between them over-counts, which never frees a live container. */
820 15795 bt->cardinality++;
821 15795 __atomic_signal_fence(__ATOMIC_SEQ_CST);
822 15795 bits[w] |= b;
823 15795 h->hdr->cardinality++;
824 15795 return 1;
825 }
826 }
827  
828 /* Membership test. Read-only. */
829 12813 static inline int rb_contains_locked(RbHandle *h, uint32_t x) {
830 12813 uint32_t hi = x >> 16;
831 12813 uint16_t lo = (uint16_t)(x & 0xffff);
832 12813 RbBucket *bt = &rb_buckets(h)[hi];
833 12813 ▶ if (bt->type == RB_TYPE_NONE) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (bt->type == RB_TYPE_NONE) return 0; 41 12772 12813
834 12772 ▶ if (bt->type == RB_TYPE_ARRAY) {
Branch: 1 branch
BranchTrueFalseTotal
if (bt->type == RB_TYPE_ARRAY) { 4735 8037 12772
835 uint32_t pos;
836 4735 return rb_array_search(rb_array(h, bt->container_off), rb_array_card(bt), lo, &pos);
837 }
838 {
839 8037 uint64_t *bits = rb_bitmap(h, bt->container_off);
840 8037 return (bits[lo >> 6] >> (lo & 63)) & 1;
841 }
842 }
843  
844 /* Remove x from the set. Returns 1 if removed, 0 if absent. Frees the slot
845 * (and clears the bucket) when the last element of a bucket is removed. v1
846 * does NOT down-convert a bitmap to an array. */
847 5010 static inline int rb_remove_locked(RbHandle *h, uint32_t x) {
848 5010 uint32_t hi = x >> 16;
849 5010 uint16_t lo = (uint16_t)(x & 0xffff);
850 5010 RbBucket *bt = &rb_buckets(h)[hi];
851 5010 ▶ if (bt->type == RB_TYPE_NONE) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (bt->type == RB_TYPE_NONE) return 0; 1 5009 5010
852 5009 ▶ if (bt->type == RB_TYPE_ARRAY) {
Branch: 1 branch
BranchTrueFalseTotal
if (bt->type == RB_TYPE_ARRAY) { 8 5001 5009
853 8 uint16_t *vals = rb_array(h, bt->container_off);
854 8 uint32_t card = rb_array_card(bt);
855 uint32_t pos;
856 8 ▶ if (!rb_array_search(vals, card, lo, &pos)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!rb_array_search(vals, card, lo, &pos)) return 0; 0 8 8
857 8 ▶ uint32_t s = card > 1 ? rb_alloc_slot_raw(h) : 0;
Branch: 1 branch
BranchTrueFalseTotal
uint32_t s = card > 1 ? rb_alloc_slot_raw(h) : 0; 1 7 8
858 8 ▶ if (s) {
Branch: 1 branch
BranchTrueFalseTotal
if (s) { 1 7 8
859 1 uint16_t *nv = rb_array(h, s);
860 1 memcpy(nv, vals, (size_t)pos * sizeof(uint16_t));
861 1 memcpy(nv + pos, vals + pos + 1, (size_t)(card - pos - 1) * sizeof(uint16_t));
862 1 rb_replace_container(h, hi, s, card - 1, RB_TYPE_ARRAY);
863 1 h->hdr->cardinality--;
864 1 return 1;
865 }
866 7 memmove(&vals[pos], &vals[pos + 1], (size_t)(card - pos - 1) * sizeof(uint16_t));
867 7 bt->cardinality--;
868 7 h->hdr->cardinality--;
869 7 ▶ if (bt->cardinality == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (bt->cardinality == 0) { 7 0 7
870 7 uint32_t off = bt->container_off;
871 /* Unlink before freeing: a kill between them leaks the slot, never shares it. */
872 7 bt->type = RB_TYPE_NONE;
873 7 bt->container_off = 0;
874 7 __atomic_signal_fence(__ATOMIC_SEQ_CST);
875 7 rb_free_slot(h, off);
876 }
877 7 return 1;
878 }
879 {
880 5001 uint64_t *bits = rb_bitmap(h, bt->container_off);
881 5001 uint32_t w = lo >> 6;
882 5001 uint64_t b = (uint64_t)1 << (lo & 63);
883 5001 ▶ if (!(bits[w] & b)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!(bits[w] & b)) return 0; 1 5000 5001
884 5000 bits[w] &= ~b;
885 5000 bt->cardinality--;
886 5000 h->hdr->cardinality--;
887 5000 ▶ if (bt->cardinality == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (bt->cardinality == 0) { 1 4999 5000
888 1 uint32_t off = bt->container_off;
889 1 bt->type = RB_TYPE_NONE;
890 1 bt->container_off = 0;
891 1 __atomic_signal_fence(__ATOMIC_SEQ_CST);
892 1 rb_free_slot(h, off);
893 }
894 5000 return 1;
895 }
896 }
897  
898 /* Reset to empty: free every container, zero the bucket table, reset the pool.
899 * Caller holds the write lock. */
900 5 static inline void rb_clear_locked(RbHandle *h) {
901 5 RbHeader *hdr = h->hdr;
902 5 RbBucket *bt = rb_buckets(h);
903 5 __atomic_store_n(&hdr->pub_hi, RB_PUB_CLEAR, __ATOMIC_RELAXED);
904 5 __atomic_thread_fence(__ATOMIC_RELEASE); /* publish before erasing any bucket bytes */
905 5 memset(bt, 0, (size_t)RB_NUM_BUCKETS * sizeof(RbBucket));
906 5 hdr->free_count = 0;
907 5 __atomic_signal_fence(__ATOMIC_SEQ_CST);
908 5 hdr->container_used = 1; /* slot 0 reserved */
909 5 hdr->free_head = 0;
910 5 hdr->cardinality = 0;
911 5 __atomic_store_n(&hdr->pub_hi, 0, __ATOMIC_RELEASE);
912 5 }
913  
914 /* Smallest set element. Returns 1 and sets *out, else 0 (empty set). */
915 15 static inline int rb_min_locked(RbHandle *h, uint32_t *out) {
916 15 RbBucket *bt = rb_buckets(h);
917 65557 ▶ for (uint32_t hi = 0; hi < RB_NUM_BUCKETS; hi++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t hi = 0; hi < RB_NUM_BUCKETS; hi++) { 65556 1 65557
918 65556 ▶ if (bt[hi].type == RB_TYPE_NONE) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (bt[hi].type == RB_TYPE_NONE) continue; 65542 14 65556
919 14 ▶ if (bt[hi].type == RB_TYPE_ARRAY) {
Branch: 1 branch
BranchTrueFalseTotal
if (bt[hi].type == RB_TYPE_ARRAY) { 10 4 14
920 10 ▶ if (rb_array_card(&bt[hi]) == 0) continue; /* corrupt: an array container with 0 entries */
Branch: 1 branch
BranchTrueFalseTotal
if (rb_array_card(&bt[hi]) == 0) continue; /* corrupt: an array container with 0 entries */ 0 10 10
921 10 *out = (hi << 16) | rb_array(h, bt[hi].container_off)[0];
922 10 return 1;
923 }
924 {
925 4 uint64_t *bits = rb_bitmap(h, bt[hi].container_off);
926 4 ▶ for (uint32_t w = 0; w < 1024; w++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t w = 0; w < 1024; w++) { 4 0 4
927 4 ▶ if (bits[w]) {
Branch: 1 branch
BranchTrueFalseTotal
if (bits[w]) { 4 0 4
928 4 uint32_t lo = (w << 6) + (uint32_t)__builtin_ctzll(bits[w]);
929 4 *out = (hi << 16) | lo;
930 4 return 1;
931 }
932 }
933 }
934 }
935 1 return 0;
936 }
937  
938 /* Largest set element. Returns 1 and sets *out, else 0 (empty set). */
939 9 static inline int rb_max_locked(RbHandle *h, uint32_t *out) {
940 9 RbBucket *bt = rb_buckets(h);
941 524052 ▶ for (uint32_t hi = RB_NUM_BUCKETS; hi-- > 0; ) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t hi = RB_NUM_BUCKETS; hi-- > 0; ) { 524051 1 524052
942 524051 ▶ if (bt[hi].type == RB_TYPE_NONE) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (bt[hi].type == RB_TYPE_NONE) continue; 524043 8 524051
943 8 ▶ if (bt[hi].type == RB_TYPE_ARRAY) {
Branch: 1 branch
BranchTrueFalseTotal
if (bt[hi].type == RB_TYPE_ARRAY) { 6 2 8
944 6 uint32_t c = rb_array_card(&bt[hi]);
945 6 ▶ if (c == 0) continue; /* corrupt: an array container with 0 entries */
Branch: 1 branch
BranchTrueFalseTotal
if (c == 0) continue; /* corrupt: an array container with 0 entries */ 0 6 6
946 6 *out = (hi << 16) | rb_array(h, bt[hi].container_off)[c - 1];
947 6 return 1;
948 }
949 {
950 2 uint64_t *bits = rb_bitmap(h, bt[hi].container_off);
951 1892 ▶ for (uint32_t w = 1024; w-- > 0; ) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t w = 1024; w-- > 0; ) { 1892 0 1892
952 1892 ▶ if (bits[w]) {
Branch: 1 branch
BranchTrueFalseTotal
if (bits[w]) { 2 1890 1892
953 2 uint32_t lo = (w << 6) + (63 - (uint32_t)__builtin_clzll(bits[w]));
954 2 *out = (hi << 16) | lo;
955 2 return 1;
956 }
957 }
958 }
959 }
960 1 return 0;
961 }
962  
963 /* Count the number of non-empty buckets (for stats). Read-only. */
964 32 static inline uint32_t rb_buckets_used(RbHandle *h) {
965 32 RbBucket *bt = rb_buckets(h);
966 32 uint32_t n = 0;
967 2097184 ▶ for (uint32_t hi = 0; hi < RB_NUM_BUCKETS; hi++)
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t hi = 0; hi < RB_NUM_BUCKETS; hi++) 2097152 32 2097184
968 2097152 ▶ if (bt[hi].type != RB_TYPE_NONE) n++;
Branch: 1 branch
BranchTrueFalseTotal
if (bt[hi].type != RB_TYPE_NONE) n++; 246 2096906 2097152
969 32 return n;
970 }
971  
972 /* ================================================================
973 * In-place set operations. Callers hold a's WRITE lock and b's READ lock
974 * (acquired in a globally-consistent order keyed on the shared-memory
975 * bitmap_id to avoid cross-process deadlock). a and b are guaranteed to be
976 * DISTINCT underlying bitmaps (the same-bitmap case -- whether o==h or merely
977 * o->hdr->bitmap_id == h->hdr->bitmap_id -- is a no-op handled by the caller).
978 * ================================================================ */
979  
980 /* a |= b for a single bucket where a's container is a bitmap. Reads b's
981 * container of either kind; returns the new popcount. */
982 4 static inline uint32_t rb_or_into_bitmap(uint64_t *abits, RbHandle *b, const RbBucket *bbt) {
983 4 ▶ if (bbt->type == RB_TYPE_ARRAY) {
Branch: 1 branch
BranchTrueFalseTotal
if (bbt->type == RB_TYPE_ARRAY) { 3 1 4
984 3 const uint16_t *bv = rb_array(b, bbt->container_off);
985 3 uint32_t bc = rb_array_card(bbt);
986 4025 ▶ for (uint32_t i = 0; i < bc; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t i = 0; i < bc; i++) { 4022 3 4025
987 4022 uint16_t lo = bv[i];
988 4022 abits[lo >> 6] |= (uint64_t)1 << (lo & 63);
989 }
990 } else { /* bitmap */
991 1 const uint64_t *bb = rb_bitmap(b, bbt->container_off);
992 1025 ▶ for (uint32_t w = 0; w < 1024; w++) abits[w] |= bb[w];
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t w = 0; w < 1024; w++) abits[w] |= bb[w]; 1024 1 1025
993 }
994 4 return (uint32_t)rb_popcount_bitmap(abits);
995 }
996  
997 /* Pre-count how many NEW container slots a |= b will need: one per bucket that
998 * b occupies and a does not. Caller holds both locks. */
999 8 static inline uint32_t rb_union_new_slots_needed(RbHandle *a, RbHandle *b) {
1000 8 RbBucket *abt = rb_buckets(a);
1001 8 RbBucket *bbt = rb_buckets(b);
1002 8 uint32_t need = 0;
1003 524296 ▶ for (uint32_t hi = 0; hi < RB_NUM_BUCKETS; hi++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t hi = 0; hi < RB_NUM_BUCKETS; hi++) { 524288 8 524296
1004 524288 ▶ if (bbt[hi].type != RB_TYPE_NONE && abt[hi].type == RB_TYPE_NONE) need++;
Branch: 2 branches
BranchTrueFalseTotal
if (bbt[hi].type != RB_TYPE_NONE && abt[hi].type == RB_TYPE_NONE) need++; 132 524156 524288
if (bbt[hi].type != RB_TYPE_NONE && abt[hi].type == RB_TYPE_NONE) need++; 3 129 132
1005 }
1006 8 return need;
1007 }
1008  
1009 /* Recompute the total cardinality from the per-bucket cards (after a set op). */
1010 13 static inline void rb_recompute_cardinality(RbHandle *a, RbBucket *abt) {
1011 13 uint64_t total = 0;
1012 851981 ▶ for (uint32_t hi = 0; hi < RB_NUM_BUCKETS; hi++)
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t hi = 0; hi < RB_NUM_BUCKETS; hi++) 851968 13 851981
1013 851968 ▶ if (abt[hi].type != RB_TYPE_NONE) total += abt[hi].cardinality;
Branch: 1 branch
BranchTrueFalseTotal
if (abt[hi].type != RB_TYPE_NONE) total += abt[hi].cardinality; 199 851769 851968
1014 13 a->hdr->cardinality = total;
1015 13 }
1016  
1017 /* a |= b. Caller has verified rb_avail_slots(a) >= rb_union_new_slots_needed.
1018 * A rewritten array container is built in a spare slot when one is free. */
1019 7 static inline void rb_union_locked(RbHandle *a, RbHandle *b) {
1020 7 RbBucket *abt = rb_buckets(a);
1021 7 RbBucket *bbt = rb_buckets(b);
1022 458759 ▶ for (uint32_t hi = 0; hi < RB_NUM_BUCKETS; hi++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t hi = 0; hi < RB_NUM_BUCKETS; hi++) { 458752 7 458759
1023 458752 ▶ if (bbt[hi].type == RB_TYPE_NONE) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (bbt[hi].type == RB_TYPE_NONE) continue; 458623 129 458752
1024  
1025 129 ▶ if (abt[hi].type == RB_TYPE_NONE) {
Branch: 1 branch
BranchTrueFalseTotal
if (abt[hi].type == RB_TYPE_NONE) { 1 128 129
1026 /* a lacks this bucket -> copy b's container wholesale. */
1027 1 uint32_t s = rb_alloc_slot(a); /* guaranteed available */
1028 1 memcpy(rb_slot(a, s), rb_slot(b, bbt[hi].container_off), RB_CONTAINER_BYTES);
1029 1 abt[hi].container_off = s;
1030 1 abt[hi].cardinality = bbt[hi].cardinality;
1031 1 __atomic_signal_fence(__ATOMIC_SEQ_CST);
1032 1 abt[hi].type = bbt[hi].type;
1033 1 continue;
1034 }
1035  
1036 128 ▶ if (abt[hi].type == RB_TYPE_ARRAY && bbt[hi].type == RB_TYPE_ARRAY) {
Branch: 2 branches
BranchTrueFalseTotal
if (abt[hi].type == RB_TYPE_ARRAY && bbt[hi].type == RB_TYPE_ARRAY) { 124 4 128
if (abt[hi].type == RB_TYPE_ARRAY && bbt[hi].type == RB_TYPE_ARRAY) { 122 2 124
1037 /* array | array -> merge sorted, dedup, into a C-stack temp. */
1038 uint16_t tmp[2 * RB_ARRAY_MAX];
1039 122 uint16_t *av = rb_array(a, abt[hi].container_off);
1040 122 const uint16_t *bv = rb_array(b, bbt[hi].container_off);
1041 122 uint32_t ai = 0, bi = 0, n = 0;
1042 122 uint32_t ac = rb_array_card(&abt[hi]), bc = rb_array_card(&bbt[hi]);
1043 10584 ▶ while (ai < ac && bi < bc) {
Branch: 2 branches
BranchTrueFalseTotal
while (ai < ac && bi < bc) { 10462 122 10584
while (ai < ac && bi < bc) { 10462 0 10462
1044 10462 uint16_t x = av[ai], y = bv[bi];
1045 10462 ▶ if (x < y) { tmp[n++] = x; ai++; }
Branch: 1 branch
BranchTrueFalseTotal
if (x < y) { tmp[n++] = x; ai++; } 3787 6675 10462
1046 6675 ▶ else if (x > y) { tmp[n++] = y; bi++; }
Branch: 1 branch
BranchTrueFalseTotal
else if (x > y) { tmp[n++] = y; bi++; } 3666 3009 6675
1047 3009 else { tmp[n++] = x; ai++; bi++; }
1048 }
1049 122 ▶ while (ai < ac) tmp[n++] = av[ai++];
Branch: 1 branch
BranchTrueFalseTotal
while (ai < ac) tmp[n++] = av[ai++]; 0 122 122
1050 246 ▶ while (bi < bc) tmp[n++] = bv[bi++];
Branch: 1 branch
BranchTrueFalseTotal
while (bi < bc) tmp[n++] = bv[bi++]; 124 122 246
1051 122 ▶ if (n <= RB_ARRAY_MAX) {
Branch: 1 branch
BranchTrueFalseTotal
if (n <= RB_ARRAY_MAX) { 120 2 122
1052 120 ▶ if (n != ac) rb_commit_array(a, hi, tmp, n);
Branch: 1 branch
BranchTrueFalseTotal
if (n != ac) rb_commit_array(a, hi, tmp, n); 120 0 120
1053 } else {
1054 2 uint32_t s = rb_alloc_slot(a);
1055 2 ▶ uint64_t *bits = rb_bitmap(a, s ? s : abt[hi].container_off);
Branch: 1 branch
BranchTrueFalseTotal
uint64_t *bits = rb_bitmap(a, s ? s : abt[hi].container_off); 0 2 2
1056 2 ▶ if (!s) memset(bits, 0, RB_CONTAINER_BYTES);
Branch: 1 branch
BranchTrueFalseTotal
if (!s) memset(bits, 0, RB_CONTAINER_BYTES); 0 2 2
1057 9028 ▶ for (uint32_t i = 0; i < n; i++) bits[tmp[i] >> 6] |= (uint64_t)1 << (tmp[i] & 63);
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t i = 0; i < n; i++) bits[tmp[i] >> 6] |= (uint64_t)1 << (tmp[i] & 63); 9026 2 9028
1058 2 ▶ if (s) {
Branch: 1 branch
BranchTrueFalseTotal
if (s) { 2 0 2
1059 2 rb_replace_container(a, hi, s, n, RB_TYPE_BITMAP);
1060 } else {
1061 0 abt[hi].type = RB_TYPE_BITMAP;
1062 0 abt[hi].cardinality = n;
1063 }
1064 }
1065 122 continue;
1066 }
1067  
1068 6 ▶ if (abt[hi].type == RB_TYPE_ARRAY && bbt[hi].type == RB_TYPE_BITMAP) {
Branch: 2 branches
BranchTrueFalseTotal
if (abt[hi].type == RB_TYPE_ARRAY && bbt[hi].type == RB_TYPE_BITMAP) { 2 4 6
if (abt[hi].type == RB_TYPE_ARRAY && bbt[hi].type == RB_TYPE_BITMAP) { 2 0 2
1069 2 uint32_t s = rb_alloc_slot_raw(a);
1070 2 ▶ if (s) {
Branch: 1 branch
BranchTrueFalseTotal
if (s) { 2 0 2
1071 2 uint64_t *nbits = rb_bitmap(a, s);
1072 2 const uint16_t *av = rb_array(a, abt[hi].container_off);
1073 2 uint32_t ac = rb_array_card(&abt[hi]);
1074 2 memcpy(nbits, rb_bitmap(b, bbt[hi].container_off), RB_CONTAINER_BYTES);
1075 4 ▶ for (uint32_t i = 0; i < ac; i++) nbits[av[i] >> 6] |= (uint64_t)1 << (av[i] & 63);
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t i = 0; i < ac; i++) nbits[av[i] >> 6] |= (uint64_t)1 << (av[i] & 63); 2 2 4
1076 2 rb_replace_container(a, hi, s, (uint32_t)rb_popcount_bitmap(nbits), RB_TYPE_BITMAP);
1077 2 continue;
1078 }
1079 /* array(a) | bitmap(b): copy b's bitmap into a, then OR a's old
1080 * array values back in. Snapshot a's array first (slot reused). */
1081 uint16_t tmp[RB_ARRAY_MAX];
1082 0 uint16_t *av = rb_array(a, abt[hi].container_off);
1083 0 uint32_t ac = rb_array_card(&abt[hi]);
1084 0 memcpy(tmp, av, (size_t)ac * sizeof(uint16_t));
1085 0 uint64_t *abits = rb_bitmap(a, abt[hi].container_off);
1086 0 memcpy(abits, rb_bitmap(b, bbt[hi].container_off), RB_CONTAINER_BYTES);
1087 0 ▶ for (uint32_t i = 0; i < ac; i++) abits[tmp[i] >> 6] |= (uint64_t)1 << (tmp[i] & 63);
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t i = 0; i < ac; i++) abits[tmp[i] >> 6] |= (uint64_t)1 << (tmp[i] & 63); 0 0 0
1088 0 abt[hi].type = RB_TYPE_BITMAP;
1089 0 abt[hi].cardinality = (uint32_t)rb_popcount_bitmap(abits);
1090 0 continue;
1091 }
1092  
1093 /* bitmap(a) | array(b) and bitmap(a) | bitmap(b): in place; each word only
1094 * gains bits, and recovery recounts a cardinality a kill leaves stale. */
1095 {
1096 4 uint64_t *abits = rb_bitmap(a, abt[hi].container_off);
1097 4 abt[hi].cardinality = rb_or_into_bitmap(abits, b, &bbt[hi]);
1098 }
1099 }
1100  
1101 7 rb_recompute_cardinality(a, abt);
1102 7 }
1103  
1104 /* a &= b. Needs no new slots: intersection only shrinks or frees, and a
1105 * rewritten container borrows a spare slot only when one is free. Caller
1106 * holds a's write lock and b's read lock. */
1107 6 static inline void rb_intersect_locked(RbHandle *a, RbHandle *b) {
1108 6 RbBucket *abt = rb_buckets(a);
1109 6 RbBucket *bbt = rb_buckets(b);
1110 393222 ▶ for (uint32_t hi = 0; hi < RB_NUM_BUCKETS; hi++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t hi = 0; hi < RB_NUM_BUCKETS; hi++) { 393216 6 393222
1111 393216 ▶ if (abt[hi].type == RB_TYPE_NONE) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (abt[hi].type == RB_TYPE_NONE) continue; 393087 129 393216
1112  
1113 129 ▶ if (bbt[hi].type == RB_TYPE_NONE) {
Branch: 1 branch
BranchTrueFalseTotal
if (bbt[hi].type == RB_TYPE_NONE) { 1 128 129
1114 1 rb_unlink_bucket(a, hi);
1115 1 continue;
1116 }
1117  
1118 128 ▶ if (abt[hi].type == RB_TYPE_ARRAY) {
Branch: 1 branch
BranchTrueFalseTotal
if (abt[hi].type == RB_TYPE_ARRAY) { 124 4 128
1119 /* array(a) & either -> a's values that b holds, into a C-stack temp. */
1120 uint16_t tmp[RB_ARRAY_MAX];
1121 124 const uint16_t *av = rb_array(a, abt[hi].container_off);
1122 124 uint32_t n = 0, ac = rb_array_card(&abt[hi]);
1123 124 ▶ if (bbt[hi].type == RB_TYPE_ARRAY) {
Branch: 1 branch
BranchTrueFalseTotal
if (bbt[hi].type == RB_TYPE_ARRAY) { 122 2 124
1124 122 const uint16_t *bv = rb_array(b, bbt[hi].container_off);
1125 122 uint32_t ai = 0, bi = 0, bc = rb_array_card(&bbt[hi]);
1126 6071 ▶ while (ai < ac && bi < bc) {
Branch: 2 branches
BranchTrueFalseTotal
while (ai < ac && bi < bc) { 6008 63 6071
while (ai < ac && bi < bc) { 5949 59 6008
1127 5949 uint16_t x = av[ai], y = bv[bi];
1128 5949 ▶ if (x < y) ai++;
Branch: 1 branch
BranchTrueFalseTotal
if (x < y) ai++; 2222 3727 5949
1129 3727 ▶ else if (x > y) bi++;
Branch: 1 branch
BranchTrueFalseTotal
else if (x > y) bi++; 1833 1894 3727
1130 1894 else { tmp[n++] = x; ai++; bi++; }
1131 }
1132 } else {
1133 2 const uint64_t *bb = rb_bitmap(b, bbt[hi].container_off);
1134 3004 ▶ for (uint32_t i = 0; i < ac; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t i = 0; i < ac; i++) { 3002 2 3004
1135 3002 uint16_t lo = av[i];
1136 3002 ▶ if ((bb[lo >> 6] >> (lo & 63)) & 1) tmp[n++] = lo;
Branch: 1 branch
BranchTrueFalseTotal
if ((bb[lo >> 6] >> (lo & 63)) & 1) tmp[n++] = lo; 3002 0 3002
1137 }
1138 }
1139 124 ▶ if (n != ac) rb_commit_array(a, hi, tmp, n);
Branch: 1 branch
BranchTrueFalseTotal
if (n != ac) rb_commit_array(a, hi, tmp, n); 121 3 124
1140 124 continue;
1141 }
1142  
1143 4 ▶ if (bbt[hi].type == RB_TYPE_ARRAY) {
Branch: 1 branch
BranchTrueFalseTotal
if (bbt[hi].type == RB_TYPE_ARRAY) { 3 1 4
1144 /* bitmap(a) & array(b) -> b's values that are set in a, as an ARRAY. */
1145 uint16_t tmp[RB_ARRAY_MAX];
1146 3 const uint16_t *bv = rb_array(b, bbt[hi].container_off);
1147 3 const uint64_t *abits = rb_bitmap(a, abt[hi].container_off);
1148 3 uint32_t n = 0, bc = rb_array_card(&bbt[hi]);
1149 5023 ▶ for (uint32_t i = 0; i < bc; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t i = 0; i < bc; i++) { 5020 3 5023
1150 5020 uint16_t lo = bv[i];
1151 5020 ▶ if ((abits[lo >> 6] >> (lo & 63)) & 1) tmp[n++] = lo;
Branch: 1 branch
BranchTrueFalseTotal
if ((abits[lo >> 6] >> (lo & 63)) & 1) tmp[n++] = lo; 4011 1009 5020
1152 }
1153 3 rb_commit_array(a, hi, tmp, n);
1154 3 continue;
1155 }
1156  
1157 /* bitmap(a) & bitmap(b): in place; each word only loses bits, and
1158 * recovery recounts a cardinality a kill leaves stale. */
1159 {
1160 1 uint64_t *abits = rb_bitmap(a, abt[hi].container_off);
1161 1 const uint64_t *bb = rb_bitmap(b, bbt[hi].container_off);
1162 1025 ▶ for (uint32_t w = 0; w < 1024; w++) abits[w] &= bb[w];
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t w = 0; w < 1024; w++) abits[w] &= bb[w]; 1024 1 1025
1163 1 abt[hi].cardinality = (uint32_t)rb_popcount_bitmap(abits);
1164 1 ▶ if (abt[hi].cardinality == 0) rb_unlink_bucket(a, hi);
Branch: 1 branch
BranchTrueFalseTotal
if (abt[hi].cardinality == 0) rb_unlink_bucket(a, hi); 0 1 1
1165 }
1166 }
1167  
1168 6 rb_recompute_cardinality(a, abt);
1169 6 }
1170  
1171 /* Run by the process that took over the write lock from a dead writer.
1172 * Finishes an interrupted bucket switch, then rebuilds from the bucket table
1173 * what it determines: bitmap counts, the freelist (reclaiming slots a kill
1174 * stranded between allocate, switch and free) and the total. Rewrites only
1175 * derived state, so a crash here is recovered by running it again. */
1176 10 static void rb_repair_locked(RbHandle *h) {
1177 10 RbHeader *hdr = h->hdr;
1178 10 RbBucket *bt = rb_buckets(h);
1179 10 ▶ if (hdr->sealed) return;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->sealed) return; 0 10 10
1180 10 uint32_t p = __atomic_load_n(&hdr->pub_hi, __ATOMIC_ACQUIRE);
1181 10 ▶ if (p == RB_PUB_CLEAR) { rb_clear_locked(h); return; }
Branch: 1 branch
BranchTrueFalseTotal
if (p == RB_PUB_CLEAR) { rb_clear_locked(h); return; } 4 6 10
1182 6 ▶ if (p) {
Branch: 1 branch
BranchTrueFalseTotal
if (p) { 0 6 6
1183 0 ▶ if (p <= RB_NUM_BUCKETS) {
Branch: 1 branch
BranchTrueFalseTotal
if (p <= RB_NUM_BUCKETS) { 0 0 0
1184 0 bt[p - 1].container_off = hdr->pub.container_off;
1185 0 bt[p - 1].cardinality = hdr->pub.cardinality;
1186 0 bt[p - 1].type = hdr->pub.type;
1187 }
1188 0 __atomic_signal_fence(__ATOMIC_SEQ_CST);
1189 0 __atomic_store_n(&hdr->pub_hi, 0, __ATOMIC_RELAXED);
1190 }
1191 6 uint32_t used = hdr->container_used;
1192 6 ▶ if (used < 1 || used > h->container_cap) return;
Branch: 2 branches
BranchTrueFalseTotal
if (used < 1 || used > h->container_cap) return; 6 0 6
if (used < 1 || used > h->container_cap) return; 0 6 6
1193 6 uint8_t *live = (uint8_t *)calloc(used / 8 + 1, 1);
1194 6 ▶ if (!live) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!live) return; 0 6 6
1195 6 uint64_t total = 0;
1196 393222 ▶ for (uint32_t hi = 0; hi < RB_NUM_BUCKETS; hi++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t hi = 0; hi < RB_NUM_BUCKETS; hi++) { 393216 6 393222
1197 393216 RbBucket *b = &bt[hi];
1198 393216 ▶ if (b->type == RB_TYPE_NONE) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (b->type == RB_TYPE_NONE) continue; 393206 10 393216
1199 10 uint32_t off = b->container_off;
1200 10 ▶ if (off == 0 || off >= used) {
Branch: 2 branches
BranchTrueFalseTotal
if (off == 0 || off >= used) { 6 4 10
if (off == 0 || off >= used) { 0 6 6
1201 /* clear may have zeroed the offset before reaching the type. */
1202 4 memset(b, 0, sizeof(*b));
1203 4 continue;
1204 }
1205 6 ▶ if (b->type != RB_TYPE_ARRAY)
Branch: 1 branch
BranchTrueFalseTotal
if (b->type != RB_TYPE_ARRAY) 0 6 6
1206 0 b->cardinality = (uint32_t)rb_popcount_bitmap(rb_bitmap(h, off));
1207 6 ▶ if (b->cardinality == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (b->cardinality == 0) { 0 6 6
1208 0 b->type = RB_TYPE_NONE;
1209 0 b->container_off = 0;
1210 0 continue;
1211 }
1212 6 live[off >> 3] |= (uint8_t)(1u << (off & 7));
1213 6 total += b->cardinality;
1214 }
1215 6 uint32_t head = 0, nfree = 0;
1216 6 hdr->free_count = 0;
1217 6 __atomic_signal_fence(__ATOMIC_SEQ_CST);
1218 18 ▶ for (uint32_t i = used; i-- > 1; ) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t i = used; i-- > 1; ) { 12 6 18
1219 12 ▶ if (live[i >> 3] & (1u << (i & 7))) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (live[i >> 3] & (1u << (i & 7))) continue; 6 6 12
1220 6 *(uint32_t *)rb_slot(h, i) = head;
1221 6 head = i;
1222 6 nfree++;
1223 }
1224 6 __atomic_signal_fence(__ATOMIC_SEQ_CST);
1225 6 hdr->free_head = head;
1226 6 hdr->free_count = nfree;
1227 6 hdr->cardinality = total;
1228 6 free(live);
1229 }
1230  
1231 /* ================================================================
1232 * Validate args + header init / setup / open / destroy
1233 * ================================================================ */
1234  
1235 /* Validate create args. Single source of truth: the XS layer does NOT
1236 * duplicate these range checks. */
1237 83 static int rb_validate_create_args(uint64_t container_cap, char *errbuf) {
1238 83 ▶ if (errbuf) errbuf[0] = '\0';
Branch: 1 branch
BranchTrueFalseTotal
if (errbuf) errbuf[0] = '\0'; 83 0 83
1239 83 ▶ if (container_cap < 1) { RB_ERR("container_capacity must be >= 1"); return 0; }
Branch: 2 branches
BranchTrueFalseTotal
if (container_cap < 1) { RB_ERR("container_capacity must be >= 1"); return 0; } 2 81 83
if (container_cap < 1) { RB_ERR("container_capacity must be >= 1"); return 0; } 2 0 2
1240 81 ▶ if (container_cap > RB_MAX_CONTAINERS) { RB_ERR("container_capacity must be <= %u", (unsigned)RB_MAX_CONTAINERS); return 0; }
Branch: 2 branches
BranchTrueFalseTotal
if (container_cap > RB_MAX_CONTAINERS) { RB_ERR("container_capacity must be <= %u", (unsigned)RB_MAX_CONTAINERS); return 0; } 1 80 81
if (container_cap > RB_MAX_CONTAINERS) { RB_ERR("container_capacity must be <= %u", (unsigned)RB_MAX_CONTAINERS); return 0; } 1 0 1
1241 {
1242 80 uint64_t total = rb_total_size((uint32_t)container_cap);
1243 if (total > (uint64_t)SIZE_MAX) { RB_ERR("requested mapping too large"); return 0; }
1244 }
1245 80 return 1;
1246 }
1247  
1248 /* Generate a non-zero per-bitmap identity, used ONLY at create time to order
1249 * set-op lock acquisition consistently across unrelated processes. Prefers
1250 * getrandom(); on any failure/short read falls back to a non-zero mix of pid,
1251 * a process-local counter, and the header address. Never returns 0. */
1252 61 static inline uint64_t rb_gen_bitmap_id(const void *hdr_addr) {
1253 static uint32_t rb_id_counter = 0;
1254 61 uint64_t id = 0;
1255 61 ssize_t r = getrandom(&id, sizeof id, 0);
1256 61 ▶ if (r != (ssize_t)sizeof id) {
Branch: 1 branch
BranchTrueFalseTotal
if (r != (ssize_t)sizeof id) { 0 61 61
1257 0 uint32_t c = __atomic_add_fetch(&rb_id_counter, 1, __ATOMIC_RELAXED);
1258 0 id = ((uint64_t)(uint32_t)getpid() << 32)
1259 0 ^ ((uint64_t)c * 0x9E3779B97F4A7C15ull)
1260 0 ^ (uint64_t)(uintptr_t)hdr_addr;
1261 }
1262 61 ▶ if (id == 0) id = 0x9E3779B97F4A7C15ull; /* never 0 */
Branch: 1 branch
BranchTrueFalseTotal
if (id == 0) id = 0x9E3779B97F4A7C15ull; /* never 0 */ 0 61 61
1263 61 return id;
1264 }
1265  
1266 61 static inline void rb_init_header(void *base, uint32_t container_cap, uint64_t total_size) {
1267 61 RbLayout L = rb_layout();
1268 61 RbHeader *hdr = (RbHeader *)base;
1269 /* Zero the header + reader-slot + occ-bitmap + bucket-table region (up to the
1270 * container pool, so the occ bitmap starts all-clear). A fresh mapping is
1271 * OS-zeroed, but zero explicitly for the reopen-of-anon path. */
1272 61 memset(base, 0, (size_t)L.container_pool);
1273 61 hdr->version = RB_VERSION;
1274 61 hdr->bitmap_id = rb_gen_bitmap_id(base);
1275 61 hdr->container_cap = container_cap;
1276 61 hdr->container_used = 1; /* slot 0 reserved as the NULL sentinel */
1277 61 hdr->free_head = 0;
1278 61 hdr->free_count = 0;
1279 61 hdr->cardinality = 0;
1280 61 hdr->total_size = total_size;
1281 61 hdr->reader_slots_off = L.reader_slots;
1282 61 hdr->bucket_table_off = L.bucket_table;
1283 61 hdr->container_pool_off = L.container_pool;
1284 /* Publish magic LAST, as a release store: it is the commit point, so a
1285 creator killed before it leaves magic==0 and never a file mistaken for
1286 a valid one. A kill during the field stores leaves one to remove by
1287 hand. */
1288 61 __atomic_store_n(&hdr->magic, RB_MAGIC, __ATOMIC_RELEASE);
1289 61 __atomic_thread_fence(__ATOMIC_SEQ_CST);
1290 61 }
1291  
1292 81 static inline RbHandle *rb_setup(void *base, size_t map_size,
1293 const char *path, int backing_fd) {
1294 81 RbHeader *hdr = (RbHeader *)base;
1295 81 RbHandle *h = (RbHandle *)calloc(1, sizeof(RbHandle));
1296 81 ▶ if (!h) {
Branch: 1 branch
BranchTrueFalseTotal
if (!h) { 0 81 81
1297 0 munmap(base, map_size);
1298 0 ▶ if (backing_fd >= 0) close(backing_fd);
Branch: 1 branch
BranchTrueFalseTotal
if (backing_fd >= 0) close(backing_fd); 0 0 0
1299 0 return NULL;
1300 }
1301 81 RbLayout L = rb_layout();
1302 81 h->hdr = hdr;
1303 81 h->base = base;
1304 /* All region bases derive from the trusted compile-time layout, not the
1305 * peer-writable header offsets; container_cap is the validated fixed
1306 * geometry (rb_validate_header / rb_validate_create_args ran before this). */
1307 81 h->reader_slots = (RbReaderSlot *)((uint8_t *)base + L.reader_slots);
1308 81 h->occ = (uint64_t *)((uint8_t *)base + L.occ); /* trusted layout offset */
1309 81 h->bucket_table = (RbBucket *)((uint8_t *)base + L.bucket_table);
1310 81 h->pool = (uint8_t *)base + L.container_pool;
1311 81 h->container_cap = hdr->container_cap;
1312 81 h->mmap_size = map_size;
1313 81 ▶ h->path = path ? strdup(path) : NULL;
Branch: 1 branch
BranchTrueFalseTotal
h->path = path ? strdup(path) : NULL; 40 41 81
1314 81 h->backing_fd = backing_fd;
1315 81 h->my_slot_idx = UINT32_MAX;
1316 81 return h;
1317 }
1318  
1319 /* Validate a mapped header (shared by rb_create reopen and rb_open_fd).
1320 * Stored geometry wins on reopen. */
1321 26 static inline int rb_validate_header(const RbHeader *hdr, uint64_t file_size) {
1322 26 ▶ if (hdr->magic != RB_MAGIC) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->magic != RB_MAGIC) return 0; 4 22 26
1323 22 ▶ if (hdr->version != RB_VERSION) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->version != RB_VERSION) return 0; 0 22 22
1324 22 ▶ if (hdr->bitmap_id == 0) return 0; /* identity must have been set at create */
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->bitmap_id == 0) return 0; /* identity must have been set at create */ 0 22 22
1325 22 ▶ if (hdr->container_cap < 1 || hdr->container_cap > RB_MAX_CONTAINERS) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (hdr->container_cap < 1 || hdr->container_cap > RB_MAX_CONTAINERS) return 0; 22 0 22
if (hdr->container_cap < 1 || hdr->container_cap > RB_MAX_CONTAINERS) return 0; 0 22 22
1326 22 ▶ if (hdr->total_size != file_size) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->total_size != file_size) return 0; 0 22 22
1327 22 ▶ if (hdr->total_size != rb_total_size(hdr->container_cap)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->total_size != rb_total_size(hdr->container_cap)) return 0; 0 22 22
1328 22 RbLayout L = rb_layout();
1329 22 ▶ 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 22 22
1330 22 ▶ if (hdr->bucket_table_off != L.bucket_table) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->bucket_table_off != L.bucket_table) return 0; 0 22 22
1331 22 ▶ if (hdr->container_pool_off != L.container_pool) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->container_pool_off != L.container_pool) return 0; 0 22 22
1332 22 ▶ if (hdr->container_used < 1 || hdr->container_used > hdr->container_cap) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (hdr->container_used < 1 || hdr->container_used > hdr->container_cap) return 0; 22 0 22
if (hdr->container_used < 1 || hdr->container_used > hdr->container_cap) return 0; 0 22 22
1333 22 ▶ if (hdr->free_head >= hdr->container_cap) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->free_head >= hdr->container_cap) return 0; 0 22 22
1334 22 ▶ if (hdr->free_count > hdr->container_cap) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->free_count > hdr->container_cap) return 0; 0 22 22
1335 22 return 1;
1336 }
1337  
1338 /* Securely obtain a fd: create exclusively (O_CREAT|O_EXCL|O_NOFOLLOW at
1339 * file_mode, default 0600), or attach an existing file (O_RDWR|O_NOFOLLOW, no
1340 * O_CREAT). Blocks a symlink swap or pre-seeded/hard-linked backing file;
1341 * cross-user sharing is opt-in via a wider file_mode. */
1342 40 static int rb_secure_open(const char *path, mode_t file_mode, char *errbuf) {
1343 40 ▶ for (int attempt = 0; attempt < 100; attempt++) {
Branch: 1 branch
BranchTrueFalseTotal
for (int attempt = 0; attempt < 100; attempt++) { 40 0 40
1344 40 int fd = open(path, O_RDWR|O_CREAT|O_EXCL|O_NOFOLLOW|O_CLOEXEC, file_mode);
1345 40 ▶ if (fd >= 0) { (void)fchmod(fd, file_mode); return fd; } /* exact mode: umask narrowed the O_EXCL create */
Branch: 1 branch
BranchTrueFalseTotal
if (fd >= 0) { (void)fchmod(fd, file_mode); return fd; } /* exact mode: umask narrowed the O_EXCL create */ 20 20 40
1346 20 ▶ if (errno != EEXIST) { RB_ERR("create(%s): %s", path, strerror(errno)); return -1; }
Branch: 2 branches
BranchTrueFalseTotal
if (errno != EEXIST) { RB_ERR("create(%s): %s", path, strerror(errno)); return -1; } 0 20 20
if (errno != EEXIST) { RB_ERR("create(%s): %s", path, strerror(errno)); return -1; } 0 0 0
1347 20 fd = open(path, O_RDWR|O_NOFOLLOW|O_CLOEXEC);
1348 20 ▶ if (fd >= 0) return fd;
Branch: 1 branch
BranchTrueFalseTotal
if (fd >= 0) return fd; 20 0 20
1349 0 ▶ if (errno == ENOENT) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (errno == ENOENT) continue; 0 0 0
1350 0 ▶ RB_ERR("open(%s): %s", path, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
RB_ERR("open(%s): %s", path, strerror(errno)); 0 0 0
1351 0 return -1;
1352 }
1353 0 ▶ RB_ERR("open(%s): create/attach kept racing", path);
Branch: 1 branch
BranchTrueFalseTotal
RB_ERR("open(%s): create/attach kept racing", path); 0 0 0
1354 0 return -1;
1355 }
1356  
1357 /* True iff the whole file is zero -- what an abandoned mid-init
1358 creator leaves. Lets recovery re-init only a provably-empty file, never
1359 one that merely starts with a zero word. Cold path, so a byte scan is
1360 fine. Read, not mapped: a read fault on a tmpfs hole allocates the page. */
1361 2 static int rb_file_is_zero(int fd, uint64_t size) {
1362 char buf[16384];
1363 389 ▶ for (uint64_t off = 0; off < size; ) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint64_t off = 0; off < size; ) { 388 1 389
1364 388 ssize_t n = pread(fd, buf, size - off < sizeof buf ? (size_t)(size - off) : sizeof buf, (off_t)off);
1365 388 ▶ if (n <= 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (n <= 0) return 0; 0 388 388
1366 6325379 ▶ 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 6324991 6324992
for (ssize_t i = 0; i < n; i++) if (buf[i]) return 0; 6324992 387 6325379
1367 387 off += (uint64_t)n;
1368 }
1369 1 return 1;
1370 }
1371  
1372 /* Opt-in (DATA_ROARINGBITMAP_SHARED_SPARSE=0): reserving commits memory this module otherwise fills lazily. */
1373 23 static int rb_reserve(int fd, uint64_t size) {
1374 23 const char *sp = getenv("DATA_ROARINGBITMAP_SHARED_SPARSE");
1375 23 ▶ if (!sp || strcmp(sp, "0")) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (!sp || strcmp(sp, "0")) return 0; 0 23 23
if (!sp || strcmp(sp, "0")) return 0; 0 0 0
1376 /* Before Linux 6.11 tmpfs gives up at any pending signal and undoes the allocation, so a
1377 * periodic one could keep it from ever completing; SIGSTOP cannot be blocked. */
1378 sigset_t all, old;
1379 0 sigfillset(&all);
1380 0 sigprocmask(SIG_BLOCK, &all, &old);
1381 int e;
1382 0 ▶ do e = posix_fallocate(fd, 0, (off_t)size); while (e == EINTR);
Branch: 1 branch
BranchTrueFalseTotal
do e = posix_fallocate(fd, 0, (off_t)size); while (e == EINTR); 0 0 0
1383 0 sigprocmask(SIG_SETMASK, &old, NULL);
1384 0 ▶ if (e == 0 || e == EOPNOTSUPP || e == EINVAL) return 0;
Branch: 3 branches
BranchTrueFalseTotal
if (e == 0 || e == EOPNOTSUPP || e == EINVAL) return 0; 0 0 0
if (e == 0 || e == EOPNOTSUPP || e == EINVAL) return 0; 0 0 0
if (e == 0 || e == EOPNOTSUPP || e == EINVAL) return 0; 0 0 0
1385 0 errno = e;
1386 0 return -1;
1387 }
1388  
1389 80 static RbHandle *rb_create(const char *path, uint64_t container_cap_in, mode_t file_mode, char *errbuf) {
1390 80 ▶ if (!rb_validate_create_args(container_cap_in, errbuf)) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!rb_validate_create_args(container_cap_in, errbuf)) return NULL; 2 78 80
1391 78 uint32_t container_cap = (uint32_t)container_cap_in;
1392  
1393 78 uint64_t total = rb_total_size(container_cap);
1394 78 int anonymous = (path == NULL);
1395 78 int fd = -1;
1396 size_t map_size;
1397 void *base;
1398  
1399 78 ▶ if (anonymous) {
Branch: 1 branch
BranchTrueFalseTotal
if (anonymous) { 38 40 78
1400 38 map_size = (size_t)total;
1401 38 base = mmap(NULL, map_size, PROT_READ|PROT_WRITE, MAP_SHARED|MAP_ANONYMOUS, -1, 0);
1402 38 ▶ if (base == MAP_FAILED) { RB_ERR("mmap: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { RB_ERR("mmap: %s", strerror(errno)); return NULL; } 0 38 38
if (base == MAP_FAILED) { RB_ERR("mmap: %s", strerror(errno)); return NULL; } 0 0 0
1403 } else {
1404 40 fd = rb_secure_open(path, file_mode, errbuf);
1405 60 ▶ if (fd < 0) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (fd < 0) return NULL; 0 40 40
1406 40 ▶ if (flock(fd, LOCK_EX) < 0) { RB_ERR("flock: %s", strerror(errno)); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (flock(fd, LOCK_EX) < 0) { RB_ERR("flock: %s", strerror(errno)); close(fd); return NULL; } 0 40 40
if (flock(fd, LOCK_EX) < 0) { RB_ERR("flock: %s", strerror(errno)); close(fd); return NULL; } 0 0 0
1407 struct stat st;
1408 40 ▶ if (fstat(fd, &st) < 0) { RB_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fstat(fd, &st) < 0) { RB_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; } 0 40 40
if (fstat(fd, &st) < 0) { RB_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; } 0 0 0
1409 40 int is_new = (st.st_size == 0);
1410 40 ▶ if (!is_new && (uint64_t)st.st_size < sizeof(RbHeader)) {
Branch: 2 branches
BranchTrueFalseTotal
if (!is_new && (uint64_t)st.st_size < sizeof(RbHeader)) { 20 20 40
if (!is_new && (uint64_t)st.st_size < sizeof(RbHeader)) { 1 19 20
1411 1 ▶ RB_ERR("%s: file too small (%lld)", path, (long long)st.st_size);
Branch: 1 branch
BranchTrueFalseTotal
RB_ERR("%s: file too small (%lld)", path, (long long)st.st_size); 1 0 1
1412 1 flock(fd, LOCK_UN); close(fd); return NULL;
1413 }
1414 39 ▶ if (is_new && (st.st_uid != geteuid() || fchmod(fd, file_mode) < 0)) {
Branch: 3 branches
BranchTrueFalseTotal
if (is_new && (st.st_uid != geteuid() || fchmod(fd, file_mode) < 0)) { 20 19 39
if (is_new && (st.st_uid != geteuid() || fchmod(fd, file_mode) < 0)) { 20 0 20
if (is_new && (st.st_uid != geteuid() || fchmod(fd, file_mode) < 0)) { 0 20 20
1415 0 ▶ RB_ERR("%s: refusing to initialize file not owned by us", path);
Branch: 1 branch
BranchTrueFalseTotal
RB_ERR("%s: refusing to initialize file not owned by us", path); 0 0 0
1416 0 flock(fd, LOCK_UN); close(fd); return NULL;
1417 }
1418 39 ▶ if (is_new && ftruncate(fd, (off_t)total) < 0) {
Branch: 2 branches
BranchTrueFalseTotal
if (is_new && ftruncate(fd, (off_t)total) < 0) { 20 19 39
if (is_new && ftruncate(fd, (off_t)total) < 0) { 0 20 20
1419 0 ▶ RB_ERR("ftruncate: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
RB_ERR("ftruncate: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; 0 0 0
1420 }
1421 39 ▶ if (is_new && rb_reserve(fd, total) < 0) {
Branch: 2 branches
BranchTrueFalseTotal
if (is_new && rb_reserve(fd, total) < 0) { 20 19 39
if (is_new && rb_reserve(fd, total) < 0) { 0 20 20
1422 0 ▶ RB_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
RB_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno)); 0 0 0
1423 0 if (ftruncate(fd, 0) < 0) { /* best effort */ }
1424 0 flock(fd, LOCK_UN); close(fd); return NULL;
1425 }
1426 39 ▶ 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; 19 20 39
1427 39 base = mmap(NULL, map_size, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
1428 39 ▶ if (base == MAP_FAILED) {
Branch: 1 branch
BranchTrueFalseTotal
if (base == MAP_FAILED) { 0 39 39
1429 0 ▶ RB_ERR("mmap: %s", strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
RB_ERR("mmap: %s", strerror(errno)); 0 0 0
1430 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
1431 0 flock(fd, LOCK_UN); close(fd); return NULL;
1432 }
1433 39 ▶ if (!is_new) {
Branch: 1 branch
BranchTrueFalseTotal
if (!is_new) { 19 20 39
1434 19 ▶ if (!rb_validate_header((RbHeader *)base, (uint64_t)st.st_size)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!rb_validate_header((RbHeader *)base, (uint64_t)st.st_size)) { 4 15 19
1435 /* Recover an abandoned mid-init file: a creator killed
1436 * between the ftruncate and the header init leaves a
1437 * full-size, all-zero (magic==0) file that would brick every
1438 * future open of this path. Re-initialize ONLY when it is
1439 * exactly our size, still uninitialized, and owned by us;
1440 * anything else still errors. */
1441 4 ▶ if (((RbHeader *)base)->magic == 0 && (uint64_t)st.st_size == total
Branch: 2 branches
BranchTrueFalseTotal
if (((RbHeader *)base)->magic == 0 && (uint64_t)st.st_size == total 3 1 4
if (((RbHeader *)base)->magic == 0 && (uint64_t)st.st_size == total 2 1 3
1442 2 ▶ && st.st_uid == geteuid() && rb_file_is_zero(fd, map_size)) {
Branch: 2 branches
BranchTrueFalseTotal
&& st.st_uid == geteuid() && rb_file_is_zero(fd, map_size)) { 2 0 2
&& st.st_uid == geteuid() && rb_file_is_zero(fd, map_size)) { 1 1 2
1443 1 ▶ if (fchmod(fd, file_mode) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (fchmod(fd, file_mode) < 0) { 0 1 1
1444 0 ▶ RB_ERR("%s: fchmod: %s", path, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
RB_ERR("%s: fchmod: %s", path, strerror(errno)); 0 0 0
1445 0 munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
1446 }
1447 1 ▶ if (rb_reserve(fd, total) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (rb_reserve(fd, total) < 0) { 0 1 1
1448 0 ▶ RB_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
RB_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno)); 0 0 0
1449 0 munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
1450 }
1451 1 rb_init_header(base, container_cap, total);
1452 1 flock(fd, LOCK_UN); close(fd);
1453 1 return rb_setup(base, map_size, path, -1);
1454 }
1455 3 ▶ if (((RbHeader *)base)->magic == 0 && (uint64_t)st.st_size == total
Branch: 2 branches
BranchTrueFalseTotal
if (((RbHeader *)base)->magic == 0 && (uint64_t)st.st_size == total 2 1 3
if (((RbHeader *)base)->magic == 0 && (uint64_t)st.st_size == total 1 1 2
1456 1 ▶ && st.st_uid == geteuid()) {
Branch: 1 branch
BranchTrueFalseTotal
&& st.st_uid == geteuid()) { 1 0 1
1457 1 ▶ RB_ERR("%s: incomplete roaring-bitmap file left by an interrupted create; remove it and retry", path);
Branch: 1 branch
BranchTrueFalseTotal
RB_ERR("%s: incomplete roaring-bitmap file left by an interrupted create; remove it and retry", path); 1 0 1
1458 1 munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
1459 }
1460 2 ▶ RB_ERR("invalid roaring-bitmap file"); munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
RB_ERR("invalid roaring-bitmap file"); munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL; 2 0 2
1461 }
1462 15 ▶ if (__atomic_load_n(&((RbHeader *)base)->sealed, __ATOMIC_ACQUIRE)) {
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&((RbHeader *)base)->sealed, __ATOMIC_ACQUIRE)) { 1 14 15
1463 1 ▶ RB_ERR("%s is frozen (read-only); open it with new_readonly", path);
Branch: 1 branch
BranchTrueFalseTotal
RB_ERR("%s is frozen (read-only); open it with new_readonly", path); 1 0 1
1464 1 munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
1465 }
1466 14 flock(fd, LOCK_UN); close(fd);
1467 14 return rb_setup(base, map_size, path, -1);
1468 }
1469 }
1470 58 rb_init_header(base, container_cap, total);
1471 58 ▶ if (fd >= 0) { flock(fd, LOCK_UN); close(fd); }
Branch: 1 branch
BranchTrueFalseTotal
if (fd >= 0) { flock(fd, LOCK_UN); close(fd); } 20 38 58
1472 58 return rb_setup(base, map_size, path, -1);
1473 }
1474  
1475 3 static RbHandle *rb_create_memfd(const char *name, uint64_t container_cap_in, char *errbuf) {
1476 3 ▶ if (!rb_validate_create_args(container_cap_in, errbuf)) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!rb_validate_create_args(container_cap_in, errbuf)) return NULL; 1 2 3
1477 2 uint32_t container_cap = (uint32_t)container_cap_in;
1478  
1479 2 uint64_t total = rb_total_size(container_cap);
1480 2 ▶ int fd = memfd_create(name ? name : "roaring", MFD_CLOEXEC | MFD_ALLOW_SEALING);
Branch: 1 branch
BranchTrueFalseTotal
int fd = memfd_create(name ? name : "roaring", MFD_CLOEXEC | MFD_ALLOW_SEALING); 1 1 2
1481 2 ▶ if (fd < 0) { RB_ERR("memfd_create: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fd < 0) { RB_ERR("memfd_create: %s", strerror(errno)); return NULL; } 0 2 2
if (fd < 0) { RB_ERR("memfd_create: %s", strerror(errno)); return NULL; } 0 0 0
1482 2 ▶ if (ftruncate(fd, (off_t)total) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (ftruncate(fd, (off_t)total) < 0) { 0 2 2
1483 0 ▶ RB_ERR("ftruncate: %s", strerror(errno)); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
RB_ERR("ftruncate: %s", strerror(errno)); close(fd); return NULL; 0 0 0
1484 }
1485 2 ▶ if (rb_reserve(fd, total) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (rb_reserve(fd, total) < 0) { 0 2 2
1486 0 ▶ RB_ERR("memfd: cannot reserve %llu bytes: %s", (unsigned long long)total, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
RB_ERR("memfd: cannot reserve %llu bytes: %s", (unsigned long long)total, strerror(errno)); 0 0 0
1487 0 close(fd); return NULL;
1488 }
1489 2 (void)fcntl(fd, F_ADD_SEALS, F_SEAL_SHRINK | F_SEAL_GROW);
1490 2 void *base = mmap(NULL, (size_t)total, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
1491 2 ▶ if (base == MAP_FAILED) { RB_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { RB_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; } 0 2 2
if (base == MAP_FAILED) { RB_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; } 0 0 0
1492 2 rb_init_header(base, container_cap, total);
1493 2 return rb_setup(base, (size_t)total, NULL, fd);
1494 }
1495  
1496 2 static RbHandle *rb_open_fd(int fd, char *errbuf) {
1497 2 ▶ if (errbuf) errbuf[0] = '\0';
Branch: 1 branch
BranchTrueFalseTotal
if (errbuf) errbuf[0] = '\0'; 2 0 2
1498 struct stat st;
1499 2 ▶ if (fstat(fd, &st) < 0) { RB_ERR("fstat: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fstat(fd, &st) < 0) { RB_ERR("fstat: %s", strerror(errno)); return NULL; } 0 2 2
if (fstat(fd, &st) < 0) { RB_ERR("fstat: %s", strerror(errno)); return NULL; } 0 0 0
1500 2 ▶ if ((uint64_t)st.st_size < sizeof(RbHeader)) { RB_ERR("too small"); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if ((uint64_t)st.st_size < sizeof(RbHeader)) { RB_ERR("too small"); return NULL; } 1 1 2
if ((uint64_t)st.st_size < sizeof(RbHeader)) { RB_ERR("too small"); return NULL; } 1 0 1
1501 /* before mmap: a creator may truncate the file until it has set magic */
1502 uint32_t magic;
1503 1 ▶ if (pread(fd, &magic, sizeof magic, offsetof(RbHeader, magic)) != (ssize_t)sizeof magic || magic != RB_MAGIC) {
Branch: 2 branches
BranchTrueFalseTotal
if (pread(fd, &magic, sizeof magic, offsetof(RbHeader, magic)) != (ssize_t)sizeof magic || magic != RB_MAGIC) { 1 0 1
if (pread(fd, &magic, sizeof magic, offsetof(RbHeader, magic)) != (ssize_t)sizeof magic || magic != RB_MAGIC) { 0 1 1
1504 0 ▶ RB_ERR("invalid roaring-bitmap file"); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
RB_ERR("invalid roaring-bitmap file"); return NULL; 0 0 0
1505 }
1506 1 size_t ms = (size_t)st.st_size;
1507 1 void *base = mmap(NULL, ms, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
1508 1 ▶ if (base == MAP_FAILED) { RB_ERR("mmap: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { RB_ERR("mmap: %s", strerror(errno)); return NULL; } 0 1 1
if (base == MAP_FAILED) { RB_ERR("mmap: %s", strerror(errno)); return NULL; } 0 0 0
1509 1 ▶ if (!rb_validate_header((RbHeader *)base, (uint64_t)st.st_size)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!rb_validate_header((RbHeader *)base, (uint64_t)st.st_size)) { 0 1 1
1510 0 ▶ RB_ERR("invalid roaring-bitmap file"); munmap(base, ms); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
RB_ERR("invalid roaring-bitmap file"); munmap(base, ms); return NULL; 0 0 0
1511 }
1512 1 ▶ if (__atomic_load_n(&((RbHeader *)base)->sealed, __ATOMIC_ACQUIRE)) {
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&((RbHeader *)base)->sealed, __ATOMIC_ACQUIRE)) { 0 1 1
1513 0 ▶ RB_ERR("this roaring bitmap is frozen (read-only); open it with new_readonly");
Branch: 1 branch
BranchTrueFalseTotal
RB_ERR("this roaring bitmap is frozen (read-only); open it with new_readonly"); 0 0 0
1514 0 munmap(base, ms); return NULL;
1515 }
1516 1 int myfd = fcntl(fd, F_DUPFD_CLOEXEC, 0);
1517 1 ▶ if (myfd < 0) { RB_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (myfd < 0) { RB_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; } 0 1 1
if (myfd < 0) { RB_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; } 0 0 0
1518 1 return rb_setup(base, ms, NULL, myfd);
1519 }
1520  
1521 81 static void rb_destroy(RbHandle *h) {
1522 81 ▶ if (!h) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!h) return; 0 81 81
1523 /* Release our reader slot on clean teardown (else short-lived-reader churn
1524 * exhausts the slot table); skip if a read lock is still held (rdepth>0). */
1525 81 ▶ 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 && 81 0 81
if (h->reader_slots && h->my_slot_idx != UINT32_MAX && h->cached_pid && 70 11 81
if (h->reader_slots && h->my_slot_idx != UINT32_MAX && h->cached_pid && 70 0 70
1526 70 ▶ h->cached_fork_gen == __atomic_load_n(&rb_fork_gen, __ATOMIC_RELAXED) &&
Branch: 1 branch
BranchTrueFalseTotal
h->cached_fork_gen == __atomic_load_n(&rb_fork_gen, __ATOMIC_RELAXED) && 70 0 70
1527 70 ▶ __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) { 70 0 70
1528 /* Clear our occ bit BEFORE freeing the slot: we still own the pid so no
1529 * claimant can take the slot mid-clear, and rdepth==0 so no writer needs
1530 * to see us. (A crash skips this -> the bit is reclaimed lazily by a
1531 * writer scan / re-claim, same as the pid.) */
1532 70 rb_occ_clear(h, h->my_slot_idx);
1533 70 uint32_t expected = h->cached_pid;
1534 70 __atomic_compare_exchange_n(&h->reader_slots[h->my_slot_idx].pid,
1535 &expected, 0, 0, __ATOMIC_RELEASE, __ATOMIC_RELAXED);
1536 }
1537 81 ▶ if (h->backing_fd >= 0) close(h->backing_fd);
Branch: 1 branch
BranchTrueFalseTotal
if (h->backing_fd >= 0) close(h->backing_fd); 3 78 81
1538 81 ▶ if (h->base) munmap(h->base, h->mmap_size);
Branch: 1 branch
BranchTrueFalseTotal
if (h->base) munmap(h->base, h->mmap_size); 81 0 81
1539 81 free(h->path);
1540 81 free(h);
1541 }
1542  
1543 5 static inline int rb_msync(RbHandle *h) {
1544 5 ▶ if (!h || !h->base) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (!h || !h->base) return 0; 5 0 5
if (!h || !h->base) return 0; 0 5 5
1545 5 return msync(h->base, h->mmap_size, MS_SYNC);
1546 }
1547  
1548 /* Open a FROZEN (sealed) file read-only: O_RDONLY + PROT_READ, no lock ever.
1549 * A sealed file is immutable and no read path writes the mapping, so queries
1550 * take no reader-slot / rwlock traffic and any number of processes can share
1551 * one PROT_READ mapping (same architecture; the magic rejects a wrong-endian
1552 * file). */
1553 7 static RbHandle *rb_open_readonly(const char *path, char *errbuf) {
1554 7 ▶ if (errbuf) errbuf[0] = '\0';
Branch: 1 branch
BranchTrueFalseTotal
if (errbuf) errbuf[0] = '\0'; 7 0 7
1555 7 int fd = open(path, O_RDONLY|O_NOFOLLOW|O_CLOEXEC);
1556 7 ▶ if (fd < 0) { RB_ERR("open %s: %s", path, strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fd < 0) { RB_ERR("open %s: %s", path, strerror(errno)); return NULL; } 1 6 7
if (fd < 0) { RB_ERR("open %s: %s", path, strerror(errno)); return NULL; } 1 0 1
1557 struct stat st;
1558 6 ▶ if (fstat(fd, &st) < 0) { RB_ERR("fstat %s: %s", path, strerror(errno)); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fstat(fd, &st) < 0) { RB_ERR("fstat %s: %s", path, strerror(errno)); close(fd); return NULL; } 0 6 6
if (fstat(fd, &st) < 0) { RB_ERR("fstat %s: %s", path, strerror(errno)); close(fd); return NULL; } 0 0 0
1559 6 ▶ if ((uint64_t)st.st_size < sizeof(RbHeader)) { RB_ERR("%s: file too small", path); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if ((uint64_t)st.st_size < sizeof(RbHeader)) { RB_ERR("%s: file too small", path); close(fd); return NULL; } 0 6 6
if ((uint64_t)st.st_size < sizeof(RbHeader)) { RB_ERR("%s: file too small", path); close(fd); return NULL; } 0 0 0
1560 /* before mmap: a creator may truncate the file until it has set magic */
1561 uint32_t magic;
1562 6 ▶ if (pread(fd, &magic, sizeof magic, offsetof(RbHeader, magic)) != (ssize_t)sizeof magic || magic != RB_MAGIC) {
Branch: 2 branches
BranchTrueFalseTotal
if (pread(fd, &magic, sizeof magic, offsetof(RbHeader, magic)) != (ssize_t)sizeof magic || magic != RB_MAGIC) { 6 0 6
if (pread(fd, &magic, sizeof magic, offsetof(RbHeader, magic)) != (ssize_t)sizeof magic || magic != RB_MAGIC) { 0 6 6
1563 0 ▶ RB_ERR("%s: invalid roaring-bitmap file", path); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
RB_ERR("%s: invalid roaring-bitmap file", path); close(fd); return NULL; 0 0 0
1564 }
1565 6 size_t ms = (size_t)st.st_size;
1566 6 void *base = mmap(NULL, ms, PROT_READ, MAP_SHARED, fd, 0);
1567 6 close(fd); /* the mapping keeps the file; a read-only view needs no fd (no msync/ftruncate) */
1568 6 ▶ if (base == MAP_FAILED) { RB_ERR("mmap %s: %s", path, strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { RB_ERR("mmap %s: %s", path, strerror(errno)); return NULL; } 0 6 6
if (base == MAP_FAILED) { RB_ERR("mmap %s: %s", path, strerror(errno)); return NULL; } 0 0 0
1569 6 ▶ if (!rb_validate_header((RbHeader *)base, (uint64_t)st.st_size)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!rb_validate_header((RbHeader *)base, (uint64_t)st.st_size)) { 0 6 6
1570 0 ▶ RB_ERR("%s: invalid roaring-bitmap file", path); munmap(base, ms); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
RB_ERR("%s: invalid roaring-bitmap file", path); munmap(base, ms); return NULL; 0 0 0
1571 }
1572 6 ▶ if (!__atomic_load_n(&((RbHeader *)base)->sealed, __ATOMIC_ACQUIRE)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!__atomic_load_n(&((RbHeader *)base)->sealed, __ATOMIC_ACQUIRE)) { 1 5 6
1573 1 ▶ RB_ERR("%s is not frozen: call ->freeze on the producer before opening read-only", path);
Branch: 1 branch
BranchTrueFalseTotal
RB_ERR("%s is not frozen: call ->freeze on the producer before opening read-only", path); 1 0 1
1574 1 munmap(base, ms); return NULL;
1575 }
1576 5 RbHandle *h = rb_setup(base, ms, path, -1); /* munmaps on OOM */
1577 5 ▶ if (!h) { RB_ERR("out of memory"); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (!h) { RB_ERR("out of memory"); return NULL; } 0 5 5
if (!h) { RB_ERR("out of memory"); return NULL; } 0 0 0
1578 5 h->readonly = 1;
1579 5 return h;
1580 }
1581  
1582 /* Seal a bitmap: make it permanently immutable so it can be shipped and opened
1583 * read-only. Takes the write lock so no mutation is in flight, publishes the
1584 * seal, then flushes it (file/memfd-backed). Afterwards every mutator croaks
1585 * and a read-write reopen is refused. */
1586 3 static int rb_freeze(RbHandle *h) {
1587 3 rb_rwlock_wrlock(h);
1588 3 __atomic_store_n(&h->hdr->sealed, 1, __ATOMIC_RELEASE);
1589 3 rb_rwlock_wrunlock(h);
1590 3 ▶ if (h->path || h->backing_fd >= 0) return rb_msync(h); /* durability for file/memfd-backed */
Branch: 2 branches
BranchTrueFalseTotal
if (h->path || h->backing_fd >= 0) return rb_msync(h); /* durability for file/memfd-backed */ 0 3 3
if (h->path || h->backing_fd >= 0) return rb_msync(h); /* durability for file/memfd-backed */ 0 0 0
1591 0 return 0; /* anonymous: the seal lives in shared memory (visible to forks); nothing to flush */
1592 }
1593  
1594 #endif /* ROARING_H */
« blib/lib/Data/RoaringBitmap/Shared.pm ↑ Summary Shared.xs »