include/sa/sa_ring.h

filter: Statementstmt 89.4% 312 / 349 Branchbran 57.3% 180 / 314 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 74.2% 492 / 663 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« include/sa/sa_cms.h ↑ Summary xs/map.xs »
1 #ifndef SA_RING_H
2 #define SA_RING_H
3  
4 /* sa_ring.h - a multi-producer record ring, as a tenant of an arena region.
5 * Perl-free.
6 *
7 * ---- fixed slots, and why not a byte ring -----------------------------------
8 *
9 * Records are variable length and a record may span several slots. What it may
10 * NOT do is float: slot N is always at `slots_off + (N % nslots) * slot_size`,
11 * arithmetic on a sequence number and nothing else.
12 *
13 * That is the property a byte-addressed ring gives up, and giving it up costs
14 * more than it saves. In a byte ring, record N's offset is
15 * `offset(N-1) + len(N-1)`, so a consumer competing for the next record must
16 * first READ a length header that may be mid-write or already lapped, and then
17 * advance a SHARED cursor based on what it read. A torn or stale read moves
18 * that cursor to an offset in the middle of a record, and every other consumer
19 * follows it there. Repairing that needs a self-validating header, a
20 * forward-scan resynchronisation that only ever runs in the case nobody tests,
21 * and gap accounting in bytes instead of messages.
22 *
23 * What a byte ring buys is storage proportional to the real message size. That
24 * is a tuning property. Claim correctness is a design property. So: fixed
25 * slots, and a record that does not fit takes more of them.
26 *
27 * ---- a record spans slots, and the head is the commit point -----------------
28 *
29 * A record too big for one slot reserves several with ONE fetch_add, so the
30 * claim is still a single atomic and the slot address is still arithmetic.
31 *
32 * The parts are then published in REVERSE ORDER, head last. That is what makes
33 * a spanned record atomic to a reader: holding a committed head is proof that
34 * every continuation behind it is already committed, so the reader gathers the
35 * tail by arithmetic and a lap re-check, and never waits a second time. Publish
36 * the head first and a reader can hold a valid head whose body has not been
37 * written yet, which is a hole in the middle of a record rather than between
38 * two of them.
39 *
40 * A record may span at most half the ring, so it can never lap itself while it
41 * is being written. Larger than that is REFUSED, never truncated - a truncated
42 * record is a lie the reader cannot detect, since it arrives with the right
43 * sequence, the right topic and a body that silently is not what was sent.
44 *
45 * ---- TWO sequence words, because one is not enough --------------------------
46 *
47 * The obvious protocol is one word per slot: zero it, write the body, then
48 * release-store the sequence, and have the reader check that sequence before
49 * and after it copies. That is wrong, and the way it is wrong is worth writing
50 * down because it looks right and it passes every gentle test.
51 *
52 * Two publishers a full lap apart share a slot. A takes sequence 1000 and is
53 * preempted mid-write. B takes 1256, writes its record into the same slot and
54 * commits. A then wakes, finishes writing ITS body over B's, and commits 1000.
55 * A reader asking for 1000 now sees 1000 before its copy and 1000 after it, and
56 * delivers a body that is half A's and half B's. The check passed because the
57 * final value is simply whoever stored last, which says nothing about who
58 * touched the bytes in between.
59 *
60 * So a slot carries the sequence TWICE. `begin` is stored before the body,
61 * `end` after it:
62 *
63 * publisher begin = N ... body ... end = N
64 * reader end == N ? copy ? begin still == N ?
65 *
66 * In the interleaving above the slot ends with begin=1256 and end=1000, and
67 * both readers are told the truth: the one asking for 1000 sees begin moved on
68 * and calls it LAPPED, and the one asking for 1256 sees end behind and waits.
69 * A false LAPPED is possible - a writer that starts just after a clean read
70 * finishes - and that is the right direction to be wrong in: a counted loss,
71 * never a corrupt delivery.
72 *
73 * Three answers, and they are not two:
74 *
75 * OK this slot holds N, whole
76 * PENDING the slot has not reached N yet: a publisher is mid-write
77 * LAPPED the ring moved past N: it is gone
78 *
79 * Conflating PENDING and LAPPED turns "wait a moment" into "give up and count a
80 * loss", which silently drops live records under load.
81 *
82 * Sequence 0 is never used, so a cursor that has never moved cannot be mistaken
83 * for one sitting on a written slot.
84 *
85 * ---- overflow is drop-oldest, and it is counted -----------------------------
86 *
87 * A publisher never blocks and never fails because a reader is slow: it
88 * overwrites the oldest slot. A reader that has been overtaken discovers it by
89 * arithmetic, jumps to the oldest sequence still present, and adds what it
90 * skipped to its own gap count. Loss is a number a caller can read, never a
91 * silence.
92 *
93 * `lapped` counts SLOTS, not records, and the two are the same number only in
94 * a ring where every record fits one slot. A spanned record that is overwritten
95 * costs one `lapped` per slot it occupied, because by the time a reader finds
96 * the hole the header that said how many slots there were is gone with it.
97 * Counting records instead would mean guessing, and a count that guesses is
98 * worse than one that is merely in different units.
99 *
100 * Needs sa_arena.h.
101 */
102  
103 #include "sa/sa_arena.h"
104 #include "sa/sa_peer.h"
105 #include "sa/sa_wake.h"
106  
107 #define SA_RING_MAGIC 0x474E4952u /* 'R','I','N','G' little-endian */
108  
109 /* Read results. Guarded, because sa_abi.h publishes the same three names for
110 * consumers and either header may arrive first; sa_abi_impl.h pins the values. */
111 #ifndef SA_READ_OK
112 #define SA_READ_OK 0
113 #define SA_READ_PENDING 1
114 #define SA_READ_LAPPED 2
115 #endif
116  
117 /* Publish results. */
118 #define SA_PUB_OK 1
119 #define SA_PUB_NORING 0
120 #define SA_PUB_OVERSIZE (-1)
121  
122 /* Slot flags. */
123 #define SA_SF_HEAD 0x1u /* the first (or only) part of a record */
124 #define SA_SF_CONT 0x2u /* a continuation */
125 #define SA_SF_ABANDONED 0x4u /* a tombstone: the publisher died */
126  
127 typedef struct {
128 /* TWO sequence words, and one is not enough - see the comment above.
129 * `begin` says which record is being written into this slot, `end` says
130 * which one finished. A reader is only holding a whole record when both
131 * say the sequence it asked for. */
132 volatile uint64_t begin; /* written FIRST, release */
133 volatile uint64_t end; /* written LAST, release: the commit */
134 volatile uint64_t claim; /* (peer << 32) | epoch. Unused until the
135 * peer table lands; it is in the layout now
136 * so adding crash attribution is not a
137 * layout change. */
138 uint32_t tlen; /* topic bytes (head only) */
139 uint32_t dlen; /* data bytes IN THIS SLOT */
140 uint32_t total; /* data bytes in the whole record (head) */
141 uint32_t flags; /* SA_SF_* */
142 uint16_t part; /* 0-based */
143 uint16_t parts; /* how many slots this record spans */
144 uint32_t pad;
145 char bytes[1]; /* topic then data, slot_size in total */
146 } sa_slot;
147  
148 /* ---- A QUEUE GROUP: ONE CURSOR, IN THE MAPPING ----------------------------
149 *
150 * A cursor object is process-local, so every reader holding one sees every
151 * record. That is fanout, and it is the right default - but it is only half of
152 * what a worker pool needs. The other half is a queue: each record delivered to
153 * exactly ONE member, so N workers share the work rather than all doing it.
154 *
155 * THE DIFFERENCE IS WHERE THE CURSOR LIVES, and nothing else. A group's cursor
156 * is in the ring's own region, so every process advancing it advances the same
157 * word, and whoever wins the compare-and-swap owns that record.
158 *
159 * The load balancing falls out of the claim and needs no scheduler: a worker
160 * busy with the last record is not in the claim loop, so it is not claiming,
161 * so the free ones take the next. A lost race costs a CAS and a retry.
162 *
163 * CAS AND NOT FETCH-ADD, for the same reason the reservation uses one. A
164 * fetch-add on a shared cursor cannot be taken back: a claimer that adds and
165 * then finds it overshot the last published sequence has ALREADY moved the
166 * cursor past sequences nobody has written, and those records are skipped
167 * forever with nothing counted, because nothing noticed.
168 *
169 * ---- AT MOST ONCE, and it is a data-loss decision -------------------------
170 *
171 * A worker that claims a record and then dies loses it. The claim moved the
172 * shared cursor and there is nothing left that says which record was in flight
173 * or who had it.
174 *
175 * That is deliberate and it is the same answer the sibling design in Hyperman
176 * gives: making it at-least-once means recording the claimant with every claim
177 * and having a survivor prove it dead and re-claim, which is a queue rather
178 * than a cursor and belongs in its own tenant. Choosing wrongly here is a
179 * data-loss bug rather than a slow path, so it is stated beside the feature.
180 *
181 * ---- bound to a topic ------------------------------------------------------
182 *
183 * A group advances past everything, and delivers only what matches its topic.
184 * Records of other topics are counted in `skipped` rather than delivered.
185 * Groups do not consume from each other: each has its own cursor, so a record
186 * can go to one member of every group that wants it.
187 */
188 #define SA_GROUPS_MAX 64
189 #define SA_GROUP_NAME 32
190 #define SA_GROUP_TOPIC 32
191  
192 /* EMPTY -> CLAIMING -> LIVE. The middle state is what stops a scanner reading
193 * a name that is still being written: the CAS out of EMPTY is exclusive, and
194 * LIVE is published last with a release. */
195 #define SA_G_EMPTY 0u
196 #define SA_G_CLAIMING 1u
197 #define SA_G_LIVE 2u
198  
199 typedef struct {
200 volatile uint32_t state; /* SA_G_* - published LAST */
201 uint32_t tlen; /* bound topic length, 0 = every topic */
202 volatile uint64_t cursor; /* THE SHARED POSITION */
203 volatile uint64_t delivered;
204 volatile uint64_t lapped; /* records gone before anybody claimed */
205 volatile uint64_t skipped; /* advanced past: another topic's */
206 char name[SA_GROUP_NAME];
207 char topic[SA_GROUP_TOPIC];
208 } sa_group;
209  
210 typedef struct {
211 volatile uint32_t magic; /* published LAST at init */
212 uint32_t slot_size;
213 uint64_t nslots;
214 uint64_t slots_off; /* from the RING's base, not the arena's */
215 uint64_t groups_off; /* the queue-group table, likewise */
216 uint32_t ngroups;
217 uint32_t gpad;
218 volatile uint64_t seq; /* the next sequence to hand out */
219 volatile uint64_t published; /* records committed */
220 volatile uint64_t oversize; /* records refused for size */
221 volatile unsigned char locks[SA_LOCK_STRIPES];
222 } sa_ring_hdr;
223  
224 /* The process-local handle. As everywhere in this dist, nothing here is written
225 * into shared memory: `hdr` and `slots` are this process's addresses. */
226 #ifndef SA_RING_FWD
227 #define SA_RING_FWD
228 typedef struct sa_ring sa_ring;
229 #endif
230  
231 struct sa_ring {
232 sa_region *arena;
233 sa_ring_hdr *hdr;
234 sa_group *groups;
235 char *slots;
236 uint32_t slot_size;
237 uint64_t nslots;
238 uint64_t payload_max; /* topic + data that fits ONE slot */
239 uint64_t parts_max; /* slots one record may span */
240 uint64_t record_max; /* topic + data across all of them */
241 };
242  
243 /* A reader's position. An OBJECT, deliberately: two readers in one process must
244 * not consume each other's records, and a cursor kept as a file-scope static is
245 * how a second reader silently becomes a thief. Its scratch is its own, sized
246 * from the ring, so a cursor can never report everything as lapped because
247 * somebody else's buffer was too small. */
248 #ifndef SA_CURSOR_FWD
249 #define SA_CURSOR_FWD
250 typedef struct sa_cursor sa_cursor;
251 #endif
252  
253 struct sa_cursor {
254 sa_ring *ring;
255 uint64_t seq;
256 uint64_t delivered;
257 uint64_t lapped;
258 uint64_t abandoned; /* holes left by a publisher that died */
259 uint64_t unattributed;/* holes nobody could be blamed for */
260 char *scratch;
261 size_t scratch_sz;
262  
263 /* The hole this cursor is stuck on, so the escalation in sa_ring_tombstone
264 * is paid once per hole rather than once per drain. Sequence 0 is never
265 * used, so it doubles as "not stuck". `hole_since_us` is when this cursor
266 * first saw it and `hole_hb0` the publisher's heartbeat at that moment:
267 * the grace period runs from first sight, across drains, instead of being
268 * slept inside one. `hole_asks` counts the peer checks run for this hole,
269 * which is how a caller tells "not yet" from "asked, and it is alive". */
270 uint64_t hole_seq;
271 uint64_t hole_next_us;
272 uint64_t hole_since_us;
273 uint64_t hole_hb0;
274 uint64_t hole_asks;
275 int hole_counted;
276 };
277  
278 #define SA_SLOT_AT(r, n) \
279 ((sa_slot *)((r)->slots + (size_t)((n) % (r)->nslots) * (r)->slot_size))
280  
281 /* The bytes a slot can carry beside its header. `bytes[1]` is declared inside
282 * the struct, so it is already counted once - subtracting sizeof and adding it
283 * back is what makes the arithmetic exact rather than one byte pessimistic. */
284 199 static uint64_t sa_ring_capacity(uint32_t slot_size) {
285 199 uint64_t hdr = (uint64_t)sizeof(sa_slot) - 1;
286 199 ▶ return slot_size > hdr ? (uint64_t)slot_size - hdr : 0;
Branch: 1 branch
BranchTrueFalseTotal
return slot_size > hdr ? (uint64_t)slot_size - hdr : 0; 199 0 199
287 }
288  
289 /* How many slots a record of this size needs, or 0 when it cannot be carried.
290 *
291 * The head holds the topic and as much data as then fits; every continuation
292 * holds data alone. A topic too big for one slot on its own is refused, because
293 * splitting the topic would mean a reader could not tell what a record was
294 * about until it had gathered all of it. */
295 2997 static uint64_t sa_ring_parts_for(const sa_ring *r, uint32_t tlen,
296 uint32_t dlen) {
297 2997 uint64_t cap = r->payload_max, first, rest;
298 2997 ▶ if ((uint64_t)tlen >= cap) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if ((uint64_t)tlen >= cap) return 0; 1 2996 2997
299 2996 first = cap - (uint64_t)tlen;
300 2996 ▶ if ((uint64_t)dlen <= first) return 1;
Branch: 1 branch
BranchTrueFalseTotal
if ((uint64_t)dlen <= first) return 1; 2939 57 2996
301 57 rest = (uint64_t)dlen - first;
302 57 return 1 + (rest + cap - 1) / cap;
303 }
304  
305 /* The queue-group table is a FIXED size and always present, which costs about
306 * five kilobytes against a ring that is measured in megabytes. Sizing it per
307 * ring would put a third number in every carve, in the geometry check, and in
308 * both doors, to save nothing anybody would notice. */
309 268 static uint64_t sa_ring_groups_bytes(void) {
310 268 return sa_align_up((uint64_t)SA_GROUPS_MAX * (uint64_t)sizeof(sa_group));
311 }
312  
313 /* How much region a ring of this shape needs. */
314 201 static uint64_t sa_ring_bytes(uint64_t nslots, uint32_t slot_size) {
315 201 return sa_align_up((uint64_t)sizeof(sa_ring_hdr))
316 201 + sa_ring_groups_bytes()
317 201 + nslots * (uint64_t)slot_size;
318 }
319  
320 /* Attach this process to a ring living in a carved region, initialising it if
321 * nobody has yet. Returns NULL and sets *err on refusal.
322 *
323 * The init race is the arena's create race one level down and takes the same
324 * answer: whoever finds magic unset writes the whole header and stores magic
325 * last, and everybody else spins bounded and then validates. */
326 67 static sa_ring *sa_ring_bind(sa_region *arena, sa_reg *e,
327 uint64_t nslots, uint32_t slot_size, int *err)
328 {
329 #if !SA_HAVE_ATOMICS
330 (void)arena; (void)e; (void)nslots; (void)slot_size;
331 if (err) *err = SA_E_NOATOMICS;
332 return NULL;
333 #else
334 sa_ring *r;
335 sa_ring_hdr *h;
336 uint64_t hash;
337  
338 67 ▶ if (err) *err = SA_E_OK;
Branch: 1 branch
BranchTrueFalseTotal
if (err) *err = SA_E_OK; 67 0 67
339 67 ▶ if (!arena || !e) { if (err) *err = SA_E_NOENT; return NULL; }
Branch: 3 branches
BranchTrueFalseTotal
if (!arena || !e) { if (err) *err = SA_E_NOENT; return NULL; } 67 0 67
if (!arena || !e) { if (err) *err = SA_E_NOENT; return NULL; } 0 67 67
if (!arena || !e) { if (err) *err = SA_E_NOENT; return NULL; } 0 0 0
340  
341 67 h = (sa_ring_hdr *)sa_ptr_len(arena, e->off, sizeof(sa_ring_hdr));
342 67 ▶ if (!h) { if (err) *err = SA_E_NOENT; return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (!h) { if (err) *err = SA_E_NOENT; return NULL; } 0 67 67
if (!h) { if (err) *err = SA_E_NOENT; return NULL; } 0 0 0
343  
344 67 ▶ if (sa_at_load32_acq(&h->magic) != SA_RING_MAGIC) {
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_load32_acq(&h->magic) != SA_RING_MAGIC) { 67 0 67
345 /* Not initialised, or not yet. One writer wins the stripe and does it;
346 * the others fall through to the wait below. */
347 67 hash = sa_at_fnv(e->name, strlen(e->name));
348 67 ▶ if (sa_at_lock(h->locks, hash)) {
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_lock(h->locks, hash)) { 67 0 67
349 67 ▶ if (sa_at_load32_acq(&h->magic) != SA_RING_MAGIC) {
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_load32_acq(&h->magic) != SA_RING_MAGIC) { 67 0 67
350 67 ▶ if (!nslots || !slot_size
Branch: 2 branches
BranchTrueFalseTotal
if (!nslots || !slot_size 67 0 67
if (!nslots || !slot_size 67 0 67
351 67 ▶ || sa_ring_capacity(slot_size) == 0
Branch: 1 branch
BranchTrueFalseTotal
|| sa_ring_capacity(slot_size) == 0 67 0 67
352 67 ▶ || sa_ring_bytes(nslots, slot_size) > e->len) {
Branch: 1 branch
BranchTrueFalseTotal
|| sa_ring_bytes(nslots, slot_size) > e->len) { 0 67 67
353 0 sa_at_unlock(h->locks, hash);
354 0 ▶ if (err) *err = SA_E_FULL;
Branch: 1 branch
BranchTrueFalseTotal
if (err) *err = SA_E_FULL; 0 0 0
355 0 return NULL;
356 }
357 67 memset((void *)h, 0, (size_t)sizeof(sa_ring_hdr));
358 67 h->slot_size = slot_size;
359 67 h->nslots = nslots;
360 67 h->groups_off = sa_align_up((uint64_t)sizeof(sa_ring_hdr));
361 67 h->ngroups = SA_GROUPS_MAX;
362 67 h->slots_off = h->groups_off + sa_ring_groups_bytes();
363 /* Sequence 1, not 0: a cursor that has never moved sits at 1
364 * and a slot that has never been written holds 0, so the two
365 * can never be confused for one another. */
366 67 sa_at_store64_rel(&h->seq, 1);
367 67 sa_at_store32_rel(&h->magic, SA_RING_MAGIC);
368 }
369 67 sa_at_unlock(h->locks, hash);
370 }
371 67 ▶ if (!sa_wait_magic32(&h->magic, SA_RING_MAGIC)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!sa_wait_magic32(&h->magic, SA_RING_MAGIC)) { 0 67 67
372 0 ▶ if (err) *err = SA_E_MAGIC;
Branch: 1 branch
BranchTrueFalseTotal
if (err) *err = SA_E_MAGIC; 0 0 0
373 0 return NULL;
374 }
375 }
376  
377 /* THE GEOMETRY IN THE HEADER IS ALSO SOMEBODY ELSE'S NUMBER.
378 *
379 * The branch above only checks a size when this process is the one doing
380 * the INITIALISING. A process that finds the magic already set reads the
381 * shape out of the shared header and believed it, so a header claiming
382 * four billion slots put every later read past the end of the mapping.
383 * sa_reg_ok makes `len` trustworthy; this makes the shape trustworthy. */
384 67 ▶ if (sa_ring_bytes(h->nslots, h->slot_size) > e->len) {
Branch: 1 branch
BranchTrueFalseTotal
if (sa_ring_bytes(h->nslots, h->slot_size) > e->len) { 0 67 67
385 0 ▶ if (err) *err = SA_E_SHORT;
Branch: 1 branch
BranchTrueFalseTotal
if (err) *err = SA_E_SHORT; 0 0 0
386 0 return NULL;
387 }
388  
389 /* THE GEOMETRY IN THE HEADER IS ALSO SOMEBODY ELSE'S NUMBER.
390 *
391 * The branch above only checks a size when this process is the one doing
392 * the INITIALISING. A process that finds the magic already set reads the
393 * shape out of the shared header and believed it - so a header saying it
394 * had four billion slots put every later read past the end of the mapping.
395 * The registry entry is bounds-checked now (sa_reg_ok), which makes `len`
396 * trustworthy, so this one comparison is what makes the shape trustworthy
397 * too. */
398  
399 /* A caller asking for a shape the ring does not have is a caller that will
400 * misread it. Say no rather than silently handing back somebody else's
401 * geometry. */
402 67 ▶ if ((nslots && h->nslots != nslots)
Branch: 2 branches
BranchTrueFalseTotal
if ((nslots && h->nslots != nslots) 67 0 67
if ((nslots && h->nslots != nslots) 67 0 67
403 67 ▶ || (slot_size && h->slot_size != slot_size)) {
Branch: 2 branches
BranchTrueFalseTotal
|| (slot_size && h->slot_size != slot_size)) { 67 0 67
|| (slot_size && h->slot_size != slot_size)) { 0 67 67
404 0 ▶ if (err) *err = SA_E_NAME;
Branch: 1 branch
BranchTrueFalseTotal
if (err) *err = SA_E_NAME; 0 0 0
405 0 return NULL;
406 }
407  
408 67 r = (sa_ring *)calloc(1, sizeof(sa_ring));
409 67 ▶ if (!r) { if (err) *err = SA_E_NOMEM; return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (!r) { if (err) *err = SA_E_NOMEM; return NULL; } 0 67 67
if (!r) { if (err) *err = SA_E_NOMEM; return NULL; } 0 0 0
410 67 r->arena = arena;
411 67 r->hdr = h;
412 67 r->groups = (sa_group *)((char *)h + (size_t)h->groups_off);
413 67 r->slots = (char *)h + (size_t)h->slots_off;
414 67 r->slot_size = h->slot_size;
415 67 r->nslots = h->nslots;
416 67 r->payload_max = sa_ring_capacity(h->slot_size);
417 /* Half the ring, so a record can never overwrite its own head while it is
418 * still being written. */
419 67 r->parts_max = h->nslots / 2;
420 67 ▶ if (r->parts_max < 1) r->parts_max = 1;
Branch: 1 branch
BranchTrueFalseTotal
if (r->parts_max < 1) r->parts_max = 1; 0 67 67
421 67 r->record_max = r->payload_max * r->parts_max;
422 67 return r;
423 #endif
424 }
425  
426 67 static void sa_ring_free(sa_ring *r) { free(r); }
427  
428 /* ---- publishing ------------------------------------------------------------ */
429  
430 /* One record into one slot.
431 *
432 * A record too big for a slot is REFUSED, never truncated. A truncated record
433 * is a lie the reader cannot detect: it has the right sequence, the right
434 * topic and a body that silently is not what was sent. Refusing gives the
435 * caller something it can act on, and the count is in the ring's stats.
436 */
437 2997 static int sa_ring_publish(sa_ring *r, const char *topic, uint32_t tlen,
438 const char *data, uint32_t dlen, uint64_t *out_seq)
439 {
440 #if !SA_HAVE_ATOMICS
441 (void)r; (void)topic; (void)tlen; (void)data; (void)dlen; (void)out_seq;
442 return SA_PUB_NORING;
443 #else
444 sa_ring_hdr *h;
445 sa_slot *s;
446 2997 uint64_t seq, claim = 0, parts;
447  
448 2997 ▶ if (!r) return SA_PUB_NORING;
Branch: 1 branch
BranchTrueFalseTotal
if (!r) return SA_PUB_NORING; 0 2997 2997
449 2997 h = r->hdr;
450  
451 2997 parts = sa_ring_parts_for(r, tlen, dlen);
452 2997 ▶ if (!parts || parts > r->parts_max) {
Branch: 2 branches
BranchTrueFalseTotal
if (!parts || parts > r->parts_max) { 2996 1 2997
if (!parts || parts > r->parts_max) { 5 2991 2996
453 6 sa_at_fetch_add64(&h->oversize, 1);
454 6 return SA_PUB_OVERSIZE;
455 }
456  
457 /* Register, so a hole this process leaves behind can be attributed to it.
458 * Lazy rather than at bind, because a fork child must take a slot of its
459 * own and the fork happens after the ring is bound. */
460 2991 sa_peer_join(r->arena);
461 5982 claim = (r->arena->peer_idx >= 0)
462 2991 ▶ ? SA_CLAIM((uint32_t)r->arena->peer_idx, r->arena->peer_epoch) : 0;
Branch: 1 branch
BranchTrueFalseTotal
? SA_CLAIM((uint32_t)r->arena->peer_idx, r->arena->peer_epoch) : 0; 2991 0 2991
463  
464 /* Raised BEFORE the reservation and lowered after the commit, so a reader
465 * can ask whether any dead peer has an unfinished record even when the
466 * publisher died before it could announce which one it was.
467 *
468 * A release STORE, not a read-modify-write: the row has one writer, this
469 * process, and a publish is serial within it, so a flag says everything a
470 * count did. Three atomic read-modify-writes per record on the publisher's
471 * own row were a measurable share of a publish (phase 01 of the Hyperman
472 * port); three plain stores are not. */
473 2991 ▶ if (r->arena->peer_idx >= 0)
Branch: 1 branch
BranchTrueFalseTotal
if (r->arena->peer_idx >= 0) 2991 0 2991
474 2991 sa_at_store64_rel(&SA_PEERS(r->arena->map.base,
475 2991 r->arena->hdr)[r->arena->peer_idx].want, 1);
476  
477 /* The reservation. ONE atomic however many slots the record needs, and
478 * what it returns is this publisher's alone - no other process can be
479 * handed any of these sequences. */
480 2991 seq = sa_at_fetch_add64(&h->seq, parts);
481  
482 /* IN REVERSE, HEAD LAST. A reader holding a committed head is then holding
483 * proof that every continuation behind it is committed too, so it gathers
484 * the tail with arithmetic and never waits twice. */
485 {
486 2991 uint64_t first = r->payload_max - (uint64_t)tlen;
487 uint64_t i;
488 7039 ▶ for (i = parts; i-- > 0; ) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = parts; i-- > 0; ) { 4048 2991 7039
489 uint64_t off, n;
490 4048 ▶ if (i == 0) { off = 0; n = (dlen < first) ? dlen : first; }
Branch: 1 branch
BranchTrueFalseTotal
if (i == 0) { off = 0; n = (dlen < first) ? dlen : first; } 2991 1057 4048
491 else {
492 1057 off = first + (i - 1) * r->payload_max;
493 1057 n = (uint64_t)dlen - off;
494 1057 ▶ if (n > r->payload_max) n = r->payload_max;
Branch: 1 branch
BranchTrueFalseTotal
if (n > r->payload_max) n = r->payload_max; 1005 52 1057
495 }
496 4048 s = SA_SLOT_AT(r, seq + i);
497  
498 /* Claim the slot before touching the body. Any reader still working
499 * on the record this slot used to hold will see `begin` has moved
500 * and discard what it copied, which is the half of the protocol a
501 * single word cannot do. */
502 4048 sa_at_store64_rel(&s->begin, seq + i);
503 4048 sa_at_store64_rel(&s->claim, claim);
504 /* THE BARRIER IS THE PROTOCOL. Without it the body below may reach
505 * another CPU before the claim above does, and a reader then sees
506 * new bytes under an old sequence and calls them whole. */
507 4048 sa_at_fence_rel();
508  
509 /* The test hook, and the only reason it exists: the window between
510 * taking a sequence and committing it is a few instructions wide,
511 * and a crash-safety test that tries to kill a process inside it by
512 * luck is a test that flakes, gets marked TODO, and stops meaning
513 * anything. Zero in every ordinary build and every ordinary run. */
514 4048 ▶ if (i == 0 && r->arena->hdr->stall_us)
Branch: 2 branches
BranchTrueFalseTotal
if (i == 0 && r->arena->hdr->stall_us) 2991 1057 4048
if (i == 0 && r->arena->hdr->stall_us) 0 2991 2991
515 0 sa_stall(r->arena->hdr->stall_us);
516  
517 4048 ▶ s->tlen = (i == 0) ? tlen : 0;
Branch: 1 branch
BranchTrueFalseTotal
s->tlen = (i == 0) ? tlen : 0; 2991 1057 4048
518 4048 s->dlen = (uint32_t)n;
519 4048 s->total = dlen;
520 4048 ▶ s->flags = (i == 0) ? SA_SF_HEAD : SA_SF_CONT;
Branch: 1 branch
BranchTrueFalseTotal
s->flags = (i == 0) ? SA_SF_HEAD : SA_SF_CONT; 2991 1057 4048
521 4048 s->part = (uint16_t)i;
522 4048 s->parts = (uint16_t)parts;
523 4048 ▶ if (i == 0 && tlen) memcpy(s->bytes, topic, tlen);
Branch: 2 branches
BranchTrueFalseTotal
if (i == 0 && tlen) memcpy(s->bytes, topic, tlen); 2991 1057 4048
if (i == 0 && tlen) memcpy(s->bytes, topic, tlen); 2990 1 2991
524 4048 ▶ if (n) memcpy(s->bytes + ((i == 0) ? tlen : 0), data + off,
Branch: 2 branches
BranchTrueFalseTotal
if (n) memcpy(s->bytes + ((i == 0) ? tlen : 0), data + off, 4046 2 4048
if (n) memcpy(s->bytes + ((i == 0) ? tlen : 0), data + off, 2989 1057 4046
525 (size_t)n);
526  
527 /* The commit. Everything above lands first, and a reader that sees
528 * this store sees all of it. */
529 4048 sa_at_store64_rel(&s->end, seq + i);
530 }
531 2991 s = SA_SLOT_AT(r, seq);
532 }
533 2991 ▶ if (r->arena->peer_idx >= 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (r->arena->peer_idx >= 0) { 2991 0 2991
534 2991 sa_peer *me = &SA_PEERS(r->arena->map.base,
535 2991 r->arena->hdr)[r->arena->peer_idx];
536 2991 sa_at_store64_rel(&me->want, 0);
537 2991 sa_at_store64_rel(&me->heartbeat, sa_at_load64_acq(&me->heartbeat) + 1);
538 }
539 2991 sa_at_fetch_add64(&h->published, 1);
540 /* Tell anybody who is asleep. Only the publisher that flips a waker's flag
541 * writes a byte, so a busy ring costs one wakeup per drain cycle rather
542 * than one per record. */
543 2991 sa_wake_poke(r->arena);
544 2991 ▶ if (out_seq) *out_seq = seq;
Branch: 1 branch
BranchTrueFalseTotal
if (out_seq) *out_seq = seq; 2991 0 2991
545 2991 return SA_PUB_OK;
546 #endif
547 }
548  
549 /* ---- reading ---------------------------------------------------------------- */
550  
551 /* Copy the record at `want` into the cursor's scratch.
552 *
553 * The sequence is checked BEFORE and AFTER the copy. Checking only before
554 * leaves a window in which a publisher laps the ring during the memcpy and the
555 * reader delivers half of one record and half of another, with a sequence that
556 * says it is fine.
557 */
558 /* Make sure the cursor's scratch can hold `n` bytes. */
559 3664 static int sa_cursor_room(sa_cursor *c, size_t n) {
560 char *p;
561 3664 ▶ if (n <= c->scratch_sz) return 1;
Branch: 1 branch
BranchTrueFalseTotal
if (n <= c->scratch_sz) return 1; 3650 14 3664
562 14 p = (char *)realloc(c->scratch, n);
563 14 ▶ if (!p) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!p) return 0; 0 14 14
564 14 c->scratch = p;
565 14 c->scratch_sz = n;
566 14 return 1;
567 }
568  
569 3809 static int sa_ring_read(sa_cursor *c, uint64_t want,
570 const char **topic, uint32_t *tlen,
571 const char **data, uint32_t *dlen, uint32_t *flags,
572 uint64_t *span)
573 {
574 #if !SA_HAVE_ATOMICS
575 (void)c; (void)want; (void)topic; (void)tlen; (void)data; (void)dlen;
576 (void)flags; (void)span;
577 return SA_READ_LAPPED;
578 #else
579 3809 sa_ring *r = c->ring;
580 3809 sa_slot *s = SA_SLOT_AT(r, want);
581 uint64_t have;
582 uint32_t tl, dl, total, fl;
583 uint64_t parts;
584  
585 3809 have = sa_at_load64_acq(&s->end);
586 3809 ▶ if (have < want) return SA_READ_PENDING;
Branch: 1 branch
BranchTrueFalseTotal
if (have < want) return SA_READ_PENDING; 122 3687 3809
587 3687 ▶ if (have > want) return SA_READ_LAPPED;
Branch: 1 branch
BranchTrueFalseTotal
if (have > want) return SA_READ_LAPPED; 23 3664 3687
588  
589 3664 tl = s->tlen;
590 3664 dl = s->dlen;
591 3664 total = s->total;
592 3664 parts = s->parts;
593 3664 fl = s->flags;
594 3664 ▶ if (!parts) return SA_READ_LAPPED;
Branch: 1 branch
BranchTrueFalseTotal
if (!parts) return SA_READ_LAPPED; 0 3664 3664
595 3664 ▶ if ((uint64_t)tl + (uint64_t)dl > r->payload_max) return SA_READ_LAPPED;
Branch: 1 branch
BranchTrueFalseTotal
if ((uint64_t)tl + (uint64_t)dl > r->payload_max) return SA_READ_LAPPED; 0 3664 3664
596 3664 ▶ if ((uint64_t)parts > r->parts_max) return SA_READ_LAPPED;
Branch: 1 branch
BranchTrueFalseTotal
if ((uint64_t)parts > r->parts_max) return SA_READ_LAPPED; 0 3664 3664
597 3664 ▶ if ((uint64_t)tl + (uint64_t)total > r->record_max) return SA_READ_LAPPED;
Branch: 1 branch
BranchTrueFalseTotal
if ((uint64_t)tl + (uint64_t)total > r->record_max) return SA_READ_LAPPED; 0 3664 3664
598  
599 /* The scratch grows to whatever this record needs and stays grown, so a
600 * ring of large records costs one allocation per cursor rather than one
601 * per read - and a cursor can never report a record as lapped merely
602 * because its own buffer was too small, which is what a fixed buffer
603 * shared between readers does. */
604 3664 ▶ if (!sa_cursor_room(c, (size_t)tl + (size_t)total)) return SA_READ_LAPPED;
Branch: 1 branch
BranchTrueFalseTotal
if (!sa_cursor_room(c, (size_t)tl + (size_t)total)) return SA_READ_LAPPED; 0 3664 3664
605  
606 3664 memcpy(c->scratch, s->bytes, (size_t)tl + (size_t)dl);
607  
608 /* And the reader's half: the copy above must be complete before the check
609 * below, or the check is of a slot the copy had not finished reading. */
610 3664 sa_at_fence_acq();
611  
612 /* Was anybody else writing this slot while we copied? `begin` moves the
613 * moment a publisher claims the slot, so a value other than `want` means
614 * the bytes in scratch may be a mixture of two records - and a mixture is
615 * indistinguishable from a real record once it is delivered. */
616 3664 ▶ if (sa_at_load64_acq(&s->begin) != want) return SA_READ_LAPPED;
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_load64_acq(&s->begin) != want) return SA_READ_LAPPED; 7 3657 3664
617  
618 /* THE TAIL, gathered by arithmetic. The head was committed last, so every
619 * continuation behind it was committed before it - there is nothing to wait
620 * for here, only a lap to re-check. */
621 3657 ▶ if (parts > 1) {
Branch: 1 branch
BranchTrueFalseTotal
if (parts > 1) { 24 3633 3657
622 24 uint64_t got = dl, i;
623 801 ▶ for (i = 1; i < parts; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 1; i < parts; i++) { 777 24 801
624 777 sa_slot *k = SA_SLOT_AT(r, want + i);
625 uint32_t kn;
626 777 ▶ if (sa_at_load64_acq(&k->end) != want + i) return SA_READ_LAPPED;
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_load64_acq(&k->end) != want + i) return SA_READ_LAPPED; 0 777 777
627 777 kn = k->dlen;
628 777 ▶ if ((uint64_t)kn > r->payload_max) return SA_READ_LAPPED;
Branch: 1 branch
BranchTrueFalseTotal
if ((uint64_t)kn > r->payload_max) return SA_READ_LAPPED; 0 777 777
629 777 ▶ if (got + kn > (uint64_t)total) return SA_READ_LAPPED;
Branch: 1 branch
BranchTrueFalseTotal
if (got + kn > (uint64_t)total) return SA_READ_LAPPED; 0 777 777
630 777 memcpy(c->scratch + tl + got, k->bytes, (size_t)kn);
631 777 sa_at_fence_acq();
632 777 ▶ if (sa_at_load64_acq(&k->begin) != want + i) return SA_READ_LAPPED;
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_load64_acq(&k->begin) != want + i) return SA_READ_LAPPED; 0 777 777
633 777 got += kn;
634 }
635 24 ▶ if (got != (uint64_t)total) return SA_READ_LAPPED;
Branch: 1 branch
BranchTrueFalseTotal
if (got != (uint64_t)total) return SA_READ_LAPPED; 0 24 24
636 24 dl = total;
637 }
638  
639 3657 ▶ if (flags) *flags = fl;
Branch: 1 branch
BranchTrueFalseTotal
if (flags) *flags = fl; 3657 0 3657
640 3657 ▶ if (topic) *topic = c->scratch;
Branch: 1 branch
BranchTrueFalseTotal
if (topic) *topic = c->scratch; 3657 0 3657
641 3657 ▶ if (tlen) *tlen = tl;
Branch: 1 branch
BranchTrueFalseTotal
if (tlen) *tlen = tl; 3657 0 3657
642 3657 ▶ if (data) *data = c->scratch + tl;
Branch: 1 branch
BranchTrueFalseTotal
if (data) *data = c->scratch + tl; 3657 0 3657
643 3657 ▶ if (dlen) *dlen = dl;
Branch: 1 branch
BranchTrueFalseTotal
if (dlen) *dlen = dl; 3657 0 3657
644 3657 ▶ if (span) *span = parts;
Branch: 1 branch
BranchTrueFalseTotal
if (span) *span = parts; 3657 0 3657
645 3657 return SA_READ_OK;
646 #endif
647 }
648  
649 95 static sa_cursor *sa_cursor_new(sa_ring *r, int from_start) {
650 sa_cursor *c;
651 95 ▶ if (!r) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!r) return NULL; 0 95 95
652 95 c = (sa_cursor *)calloc(1, sizeof(sa_cursor));
653 95 ▶ if (!c) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!c) return NULL; 0 95 95
654 95 c->scratch_sz = (size_t)r->payload_max;
655 95 ▶ c->scratch = (char *)malloc(c->scratch_sz ? c->scratch_sz : 1);
Branch: 1 branch
BranchTrueFalseTotal
c->scratch = (char *)malloc(c->scratch_sz ? c->scratch_sz : 1); 95 0 95
656 95 ▶ if (!c->scratch) { free(c); return NULL; }
Branch: 1 branch
BranchTrueFalseTotal
if (!c->scratch) { free(c); return NULL; } 0 95 95
657 95 c->ring = r;
658 #if SA_HAVE_ATOMICS
659 /* From the start of what is still in the ring, or from now. "From now" is
660 * the right default for a tail; "from the start" is what a test wants. */
661 95 ▶ if (from_start) {
Branch: 1 branch
BranchTrueFalseTotal
if (from_start) { 3 92 95
662 3 uint64_t end = sa_at_load64_acq(&r->hdr->seq);
663 3 ▶ c->seq = (end > r->nslots) ? end - r->nslots : 1;
Branch: 1 branch
BranchTrueFalseTotal
c->seq = (end > r->nslots) ? end - r->nslots : 1; 0 3 3
664 }
665 else {
666 92 c->seq = sa_at_load64_acq(&r->hdr->seq);
667 }
668 #else
669 (void)from_start;
670 c->seq = 1;
671 #endif
672 95 return c;
673 }
674  
675 95 static void sa_cursor_free(sa_cursor *c) {
676 95 ▶ if (!c) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!c) return; 0 95 95
677 95 free(c->scratch);
678 95 free(c);
679 }
680  
681 /* Has this cursor been overtaken? If so, move it to the oldest sequence still
682 * present and count everything skipped.
683 *
684 * `end - nslots` is the oldest sequence the ring can still hold: anything
685 * before it has been overwritten by definition, whatever the slot says. */
686 416 static uint64_t sa_cursor_catchup(sa_cursor *c) {
687 #if !SA_HAVE_ATOMICS
688 (void)c;
689 return 0;
690 #else
691 416 sa_ring *r = c->ring;
692 416 uint64_t end = sa_at_load64_acq(&r->hdr->seq);
693 uint64_t oldest, missed;
694  
695 416 ▶ if (end <= r->nslots) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (end <= r->nslots) return 0; 205 211 416
696 211 oldest = end - r->nslots;
697 211 ▶ if (c->seq >= oldest) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (c->seq >= oldest) return 0; 198 13 211
698  
699 13 missed = oldest - c->seq;
700 13 c->lapped += missed;
701 13 c->seq = oldest;
702 13 return missed;
703 #endif
704 }
705  
706 /* ---- a hole, and who is to blame for it -------------------------------------
707 *
708 * A reader that finds sequence `want` uncommitted cannot simply wait, and
709 * cannot simply skip. This is the escalation: cheap first, and a syscall only
710 * once the cheap answers have run out.
711 *
712 * 1. spin - the overwhelming case is a publisher two memcpys from done
713 * 2. sleep - the grace period, so an ordinary preemption is just a wait
714 * 3. ask - who claimed this slot, and is that process gone
715 *
716 * Step 3 is the one a timeout cannot do, and it is why this waits on a QUESTION
717 * rather than on a clock.
718 *
719 * When the answer is yes, the reader does not skip the hole - it FILLS it, with
720 * a well-formed record carrying SA_SF_ABANDONED. That is the move that matters:
721 * every other reader, present and future, then passes the hole by READING it,
722 * so no timeout is left anywhere in anybody's steady-state path. A skip would
723 * have to be rediscovered, and paid for, by every cursor separately.
724 *
725 * Returns 1 when the hole was filled and the caller should read it again.
726 */
727 122 static int sa_ring_tombstone(sa_cursor *c, uint64_t want) {
728 #if !SA_HAVE_ATOMICS
729 (void)c; (void)want;
730 return 0;
731 #else
732 122 sa_ring *r = c->ring;
733 122 sa_slot *s = SA_SLOT_AT(r, want);
734 122 sa_region *a = r->arena;
735 uint64_t claim, now;
736 uint32_t grace;
737 long spin;
738  
739 /* ---- THE ESCALATION IS PER HOLE, NOT PER VISIT, AND IT NEVER SLEEPS ----
740 *
741 * A drain that finds an unfilled hole stops there, so the NEXT drain
742 * arrives at the same sequence - and the first version paid the whole
743 * escalation again every time: two thousand spins, a sleep of the full
744 * grace period, and a walk of up to 256 peers calling kill() on each. A
745 * caller draining in an event loop therefore slept 250ms per turn for as
746 * long as the hole lasted, which is the opposite of what a bounded wait is
747 * for. It also counted `unattributed` once per VISIT, so a single hole
748 * inflated the number that exists to tell you how rare this is.
749 *
750 * The second version still slept the grace period INSIDE the read, once
751 * per hole. An event-loop worker cannot afford a quarter second in a drain
752 * either, so now the grace period runs on the cursor: the publisher's
753 * heartbeat is captured the FIRST time the hole is seen, and the peer
754 * check runs on whichever visit finds the grace period elapsed. A caller
755 * that wants to wait naps between drains; this function only ever spins
756 * its two thousand turns. */
757 122 ▶ if (c->hole_seq != want) {
Branch: 1 branch
BranchTrueFalseTotal
if (c->hole_seq != want) { 4 118 122
758 4 c->hole_seq = want;
759 4 c->hole_next_us = 0;
760 4 c->hole_counted = 0;
761 4 c->hole_since_us = sa_now_us();
762 4 c->hole_hb0 = sa_peer_hb(a, sa_at_load64_acq(&s->claim));
763 }
764  
765 244122 ▶ for (spin = 0; spin < 2000; spin++) {
Branch: 1 branch
BranchTrueFalseTotal
for (spin = 0; spin < 2000; spin++) { 244000 122 244122
766 244000 ▶ if (sa_at_load64_acq(&s->end) == want) { /* it landed */
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_load64_acq(&s->end) == want) { /* it landed */ 0 244000 244000
767 0 c->hole_seq = 0;
768 0 return 0;
769 }
770 }
771  
772 122 now = sa_now_us();
773 122 grace = sa_at_load32_acq(&a->hdr->reap_grace_us);
774 122 ▶ if (!grace) grace = 1000;
Branch: 1 branch
BranchTrueFalseTotal
if (!grace) grace = 1000; 0 122 122
775  
776 /* Asked recently, and the answer cannot have changed: the heartbeat test
777 * below needs a grace period to have passed before it means anything. */
778 122 ▶ if (c->hole_next_us && now < c->hole_next_us) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (c->hole_next_us && now < c->hole_next_us) return 0; 7 115 122
if (c->hole_next_us && now < c->hole_next_us) return 0; 7 0 7
779  
780 /* The grace period is still running. The clock can step backwards, and a
781 * wait that then never ends is the one thing rule 5 forbids, so a `now`
782 * before `since` counts as elapsed. */
783 115 ▶ if (now >= c->hole_since_us && now - c->hole_since_us < grace) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (now >= c->hole_since_us && now - c->hole_since_us < grace) return 0; 115 0 115
if (now >= c->hole_since_us && now - c->hole_since_us < grace) return 0; 113 2 115
784  
785 2 c->hole_next_us = now + grace;
786 2 c->hole_asks++;
787  
788 /* Re-read: a publisher may have claimed the slot during the wait, in which
789 * case the heartbeat we hold belongs to the wrong peer. Start the grace
790 * period again against the new one. */
791 2 claim = sa_at_load64_acq(&s->claim);
792 2 ▶ if (!sa_peer_is_dead(a, claim, c->hole_hb0)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!sa_peer_is_dead(a, claim, c->hole_hb0)) { 1 1 2
793 /* Nobody provably dead. If SOME dead peer has an uncommitted
794 * reservation, this hole is very likely theirs and waiting for ever is
795 * worse than counting it - but say so separately, because a non-zero
796 * unattributed count means this design has a gap and the number is how
797 * anybody would ever find out. Counted ONCE for this hole, however many
798 * times the cursor comes back to it. */
799 1 ▶ if (!c->hole_counted && sa_peer_any_dead_pending(a)) {
Branch: 2 branches
BranchTrueFalseTotal
if (!c->hole_counted && sa_peer_any_dead_pending(a)) { 1 0 1
if (!c->hole_counted && sa_peer_any_dead_pending(a)) { 0 1 1
800 0 c->unattributed++;
801 0 c->hole_counted = 1;
802 }
803 /* A fresh baseline for the next question: the heartbeat must stand
804 * still for a WHOLE grace period, measured from here. */
805 1 c->hole_since_us = now;
806 1 c->hole_hb0 = sa_peer_hb(a, claim);
807 1 return 0;
808 }
809  
810 1 (void)sa_peer_reap(a, claim);
811  
812 /* The same protocol a real record uses, because this IS a real record. */
813 1 sa_at_store64_rel(&s->begin, want);
814 1 sa_at_store64_rel(&s->claim, 0);
815 1 sa_at_fence_rel();
816 1 s->tlen = 0;
817 1 s->dlen = 0;
818 1 s->total = 0;
819 1 s->flags = SA_SF_HEAD | SA_SF_ABANDONED;
820 1 s->part = 0;
821 1 s->parts = 1;
822 1 sa_at_store64_rel(&s->end, want);
823 1 c->hole_seq = 0;
824 1 return 1;
825 #endif
826 }
827  
828 #ifndef SA_REC_FN_FWD
829 #define SA_REC_FN_FWD
830 typedef void (*sa_rec_fn)(void *ud, uint64_t seq,
831 const char *topic, uint32_t tlen,
832 const char *data, uint32_t dlen, uint32_t flags);
833 #endif
834  
835 /* Everything published since this cursor last looked, up to `max` records.
836 * Returns how many were delivered.
837 *
838 * Stops at the first PENDING rather than waiting: an uncommitted slot means a
839 * publisher is mid-write, and the caller is better off coming back than
840 * blocking a whole event loop on one memcpy.
841 */
842 5 static long sa_cursor_drain(sa_cursor *c, long max, sa_rec_fn cb, void *ud) {
843 #if !SA_HAVE_ATOMICS
844 (void)c; (void)max; (void)cb; (void)ud;
845 return 0;
846 #else
847 sa_ring *r;
848 uint64_t end;
849 5 long n = 0;
850  
851 5 ▶ if (!c || !cb) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (!c || !cb) return 0; 5 0 5
if (!c || !cb) return 0; 0 5 5
852 5 r = c->ring;
853 5 sa_cursor_catchup(c);
854 5 end = sa_at_load64_acq(&r->hdr->seq);
855  
856 45 ▶ while (c->seq < end && (max <= 0 || n < max)) {
Branch: 3 branches
BranchTrueFalseTotal
while (c->seq < end && (max <= 0 || n < max)) { 41 4 45
while (c->seq < end && (max <= 0 || n < max)) { 38 3 41
while (c->seq < end && (max <= 0 || n < max)) { 2 1 3
857 40 const char *topic = NULL, *data = NULL;
858 40 uint32_t tlen = 0, dlen = 0, flags = 0;
859 40 uint64_t span = 1;
860 40 int rc = sa_ring_read(c, c->seq, &topic, &tlen, &data, &dlen, &flags,
861 &span);
862  
863 40 ▶ if (rc == SA_READ_PENDING) {
Branch: 1 branch
BranchTrueFalseTotal
if (rc == SA_READ_PENDING) { 0 40 40
864 0 ▶ if (!sa_ring_tombstone(c, c->seq)) break;
Branch: 1 branch
BranchTrueFalseTotal
if (!sa_ring_tombstone(c, c->seq)) break; 0 0 0
865 0 rc = sa_ring_read(c, c->seq, &topic, &tlen, &data, &dlen, &flags,
866 &span);
867 0 ▶ if (rc != SA_READ_OK) break;
Branch: 1 branch
BranchTrueFalseTotal
if (rc != SA_READ_OK) break; 0 0 0
868 }
869 40 ▶ if (rc == SA_READ_LAPPED) { c->lapped++; c->seq++; continue; }
Branch: 1 branch
BranchTrueFalseTotal
if (rc == SA_READ_LAPPED) { c->lapped++; c->seq++; continue; } 0 40 40
870 40 ▶ if (flags & SA_SF_CONT) {
Branch: 1 branch
BranchTrueFalseTotal
if (flags & SA_SF_CONT) { 0 40 40
871 /* A continuation reached on its own means its HEAD was missed -
872 * a delivered record jumps the cursor past its own tail, so these
873 * are only ever seen when the record they belong to was lost.
874 *
875 * Counted as lapped, and that is what keeps the accounting exact:
876 * `lapped` is in SLOTS, a lost record cost as many slots as it
877 * spanned, and skipping these silently would leave the difference
878 * unexplained in every ring that carries a record bigger than a
879 * slot.
880 *
881 * This flag, not the `seq += span` below, is what makes spanning
882 * safe: a cursor advancing one slot at a time would land on every
883 * continuation and skip it here, arriving at the same place. The
884 * span is an optimisation. */
885 0 c->lapped++;
886 0 c->seq++;
887 0 continue;
888 }
889 40 ▶ if (flags & SA_SF_ABANDONED) { c->abandoned++; c->seq++; continue; }
Branch: 1 branch
BranchTrueFalseTotal
if (flags & SA_SF_ABANDONED) { c->abandoned++; c->seq++; continue; } 0 40 40
890  
891 40 cb(ud, c->seq, topic, tlen, data, dlen, flags);
892 40 c->delivered++;
893 40 c->seq += span;
894 40 n++;
895 }
896 5 return n;
897 #endif
898 }
899  
900 /* ---- queue groups ---------------------------------------------------------- */
901  
902 /* The process-local half of a group. As everywhere in this dist, nothing here
903 * is written into the mapping: `g` is this process's address for the shared
904 * record, and `claimed` is this member's own tally rather than the pool's. */
905 #ifndef SA_GROUP_H_FWD
906 #define SA_GROUP_H_FWD
907 typedef struct sa_group_h sa_group_h;
908 #endif
909  
910 struct sa_group_h {
911 sa_ring *ring;
912 sa_group *g;
913 sa_cursor *scratch;
914 uint64_t claimed;
915 };
916  
917 #if SA_HAVE_ATOMICS
918  
919 /* Find the group of this name, or make it.
920 *
921 * The stripe lock covers the search and the claim, so two processes asking for
922 * the same name cannot both create it - which would be two groups with one
923 * name, each delivering half the work to somebody who thought they were in the
924 * other. The same reasoning, and the same lock, as carving a region.
925 *
926 * A group that already exists is checked against the topic asked for. Two
927 * callers disagreeing about which topic a group consumes is worse than either
928 * of them failing, for the same reason a ring checks its geometry. */
929 70 static sa_group *sa_group_bind(sa_ring *r, const char *name, uint32_t nlen,
930 const char *topic, uint32_t tlen,
931 uint64_t from, int *err)
932 {
933 sa_ring_hdr *h;
934 uint64_t hash;
935 uint32_t i, n;
936  
937 70 ▶ if (err) *err = SA_E_OK;
Branch: 1 branch
BranchTrueFalseTotal
if (err) *err = SA_E_OK; 70 0 70
938 70 ▶ if (!r) { if (err) *err = SA_E_NOENT; return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (!r) { if (err) *err = SA_E_NOENT; return NULL; } 0 70 70
if (!r) { if (err) *err = SA_E_NOENT; return NULL; } 0 0 0
939 70 ▶ if (!name || !nlen || nlen >= SA_GROUP_NAME
Branch: 3 branches
BranchTrueFalseTotal
if (!name || !nlen || nlen >= SA_GROUP_NAME 70 0 70
if (!name || !nlen || nlen >= SA_GROUP_NAME 70 0 70
if (!name || !nlen || nlen >= SA_GROUP_NAME 70 0 70
940 70 ▶ || tlen >= SA_GROUP_TOPIC) {
Branch: 1 branch
BranchTrueFalseTotal
|| tlen >= SA_GROUP_TOPIC) { 0 70 70
941 0 ▶ if (err) *err = SA_E_NAME;
Branch: 1 branch
BranchTrueFalseTotal
if (err) *err = SA_E_NAME; 0 0 0
942 0 return NULL;
943 }
944  
945 70 h = r->hdr;
946 70 n = h->ngroups > SA_GROUPS_MAX ? SA_GROUPS_MAX : h->ngroups;
947 70 hash = sa_at_fnv(name, (size_t)nlen);
948  
949 70 ▶ if (!sa_at_lock(h->locks, hash)) { if (err) *err = SA_E_FULL; return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (!sa_at_lock(h->locks, hash)) { if (err) *err = SA_E_FULL; return NULL; } 0 70 70
if (!sa_at_lock(h->locks, hash)) { if (err) *err = SA_E_FULL; return NULL; } 0 0 0
950  
951 3206 ▶ for (i = 0; i < n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n; i++) { 3157 49 3206
952 3157 sa_group *g = &r->groups[i];
953 3157 ▶ if (sa_at_load32_acq(&g->state) != SA_G_LIVE) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_load32_acq(&g->state) != SA_G_LIVE) continue; 3129 28 3157
954 28 ▶ if (strncmp(g->name, name, nlen) || g->name[nlen]) continue;
Branch: 2 branches
BranchTrueFalseTotal
if (strncmp(g->name, name, nlen) || g->name[nlen]) continue; 21 7 28
if (strncmp(g->name, name, nlen) || g->name[nlen]) continue; 0 21 21
955 21 sa_at_unlock(h->locks, hash);
956 21 ▶ if (g->tlen != tlen
Branch: 1 branch
BranchTrueFalseTotal
if (g->tlen != tlen 21 0 21
957 21 ▶ || (tlen && memcmp(g->topic, topic, tlen))) {
Branch: 2 branches
BranchTrueFalseTotal
|| (tlen && memcmp(g->topic, topic, tlen))) { 6 15 21
|| (tlen && memcmp(g->topic, topic, tlen))) { 6 0 6
958 6 ▶ if (err) *err = SA_E_SHAPE;
Branch: 1 branch
BranchTrueFalseTotal
if (err) *err = SA_E_SHAPE; 6 0 6
959 6 return NULL;
960 }
961 15 return g;
962 }
963  
964 56 ▶ for (i = 0; i < n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n; i++) { 56 0 56
965 56 sa_group *g = &r->groups[i];
966 56 ▶ if (!sa_at_cas32(&g->state, SA_G_EMPTY, SA_G_CLAIMING)) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (!sa_at_cas32(&g->state, SA_G_EMPTY, SA_G_CLAIMING)) continue; 7 49 56
967 49 memset(g->name, 0, SA_GROUP_NAME);
968 49 memcpy(g->name, name, nlen);
969 49 memset(g->topic, 0, SA_GROUP_TOPIC);
970 49 ▶ if (tlen) memcpy(g->topic, topic, tlen);
Branch: 1 branch
BranchTrueFalseTotal
if (tlen) memcpy(g->topic, topic, tlen); 13 36 49
971 49 g->tlen = tlen;
972 49 sa_at_store64_rel(&g->delivered, 0);
973 49 sa_at_store64_rel(&g->lapped, 0);
974 49 sa_at_store64_rel(&g->skipped, 0);
975 /* From now, not from the beginning: a worker joining a pool wants the
976 * work that arrives after it, not a replay of everything the ring still
977 * happens to hold. `from` overrides it for a caller that wants one. */
978 98 ▶ sa_at_store64_rel(&g->cursor,
Branch: 1 branch
BranchTrueFalseTotal
sa_at_store64_rel(&g->cursor, 49 0 49
979 49 from ? from : sa_at_load64_acq(&h->seq));
980 49 sa_at_store32_rel(&g->state, SA_G_LIVE);
981 49 sa_at_unlock(h->locks, hash);
982 49 return g;
983 }
984  
985 0 sa_at_unlock(h->locks, hash);
986 0 ▶ if (err) *err = SA_E_FULL;
Branch: 1 branch
BranchTrueFalseTotal
if (err) *err = SA_E_FULL; 0 0 0
987 0 return NULL;
988 }
989  
990 /* The handle both doors use, so the Perl surface and the C ABI cannot differ
991 * about what opening a group means. The scratch cursor is for the record
992 * buffer and the hole machinery; its own position is never consulted. */
993 70 static sa_group_h *sa_group_new(sa_ring *r, const char *name, uint32_t nlen,
994 const char *topic, uint32_t tlen,
995 uint64_t from, int *err)
996 {
997 sa_group_h *gh;
998 70 sa_group *g = sa_group_bind(r, name, nlen, topic, tlen, from, err);
999 70 ▶ if (!g) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!g) return NULL; 6 64 70
1000 64 gh = (sa_group_h *)calloc(1, sizeof(sa_group_h));
1001 64 ▶ if (!gh) { if (err) *err = SA_E_NOMEM; return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (!gh) { if (err) *err = SA_E_NOMEM; return NULL; } 0 64 64
if (!gh) { if (err) *err = SA_E_NOMEM; return NULL; } 0 0 0
1002 64 gh->scratch = sa_cursor_new(r, 0);
1003 64 ▶ if (!gh->scratch) { free(gh); if (err) *err = SA_E_NOMEM; return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (!gh->scratch) { free(gh); if (err) *err = SA_E_NOMEM; return NULL; } 0 64 64
if (!gh->scratch) { free(gh); if (err) *err = SA_E_NOMEM; return NULL; } 0 0 0
1004 64 gh->ring = r;
1005 64 gh->g = g;
1006 64 return gh;
1007 }
1008  
1009 /* Leaving is not releasing. The group in the mapping outlives this member:
1010 * another worker is still claiming from that cursor, and a member that exits
1011 * must not take the pool's position with it. */
1012 64 static void sa_group_free(sa_group_h *gh) {
1013 64 ▶ if (!gh) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!gh) return; 0 64 64
1014 64 ▶ if (gh->scratch) sa_cursor_free(gh->scratch);
Branch: 1 branch
BranchTrueFalseTotal
if (gh->scratch) sa_cursor_free(gh->scratch); 64 0 64
1015 64 free(gh);
1016 }
1017  
1018 /* Take the next record for this group, or report that there is none.
1019 *
1020 * `scratch` is a process-local cursor, used only for its buffer and for the
1021 * hole machinery - its own position is never consulted, because the position
1022 * that matters is the group's and that one is shared.
1023 *
1024 * Returns SA_READ_OK with the record filled in, or SA_READ_PENDING when there
1025 * is nothing to take. `*seq` is the sequence claimed.
1026 */
1027 508 static int sa_group_claim(sa_ring *r, sa_group *g, sa_cursor *scratch,
1028 uint64_t *seq, const char **topic, uint32_t *tlen,
1029 const char **data, uint32_t *dlen, uint32_t *flags)
1030 {
1031 sa_ring_hdr *h;
1032 long guard;
1033  
1034 508 ▶ if (!r || !g || !scratch) return SA_READ_PENDING;
Branch: 3 branches
BranchTrueFalseTotal
if (!r || !g || !scratch) return SA_READ_PENDING; 508 0 508
if (!r || !g || !scratch) return SA_READ_PENDING; 508 0 508
if (!r || !g || !scratch) return SA_READ_PENDING; 0 508 508
1035 508 h = r->hdr;
1036  
1037 /* Bounded, because every loop in this dist is. Each turn either claims,
1038 * advances past something, or loses a race to somebody who did - so this
1039 * cannot spin without the ring moving, and the bound is only there so a
1040 * pathological interleaving cannot hold a worker for ever. */
1041 521 ▶ for (guard = 0; guard < 1024; guard++) {
Branch: 1 branch
BranchTrueFalseTotal
for (guard = 0; guard < 1024; guard++) { 521 0 521
1042 521 uint64_t cur = sa_at_load64_acq(&g->cursor);
1043 521 uint64_t end = sa_at_load64_acq(&h->seq);
1044 521 uint64_t span = 1, oldest;
1045 521 const char *tp = NULL, *dp = NULL;
1046 521 uint32_t tl = 0, dl = 0, fl = 0;
1047 int rc;
1048  
1049 1008 ▶ if (cur >= end) return SA_READ_PENDING; /* nothing published */
Branch: 1 branch
BranchTrueFalseTotal
if (cur >= end) return SA_READ_PENDING; /* nothing published */ 21 500 521
1050  
1051 /* Overtaken. `end - nslots` is the oldest sequence the ring can still
1052 * hold, whatever the slots say, so the group jumps there and counts
1053 * what it never saw. Losing this CAS is fine: somebody else did it. */
1054 500 ▶ oldest = (end > r->nslots) ? end - r->nslots : 1;
Branch: 1 branch
BranchTrueFalseTotal
oldest = (end > r->nslots) ? end - r->nslots : 1; 0 500 500
1055 500 ▶ if (cur < oldest) {
Branch: 1 branch
BranchTrueFalseTotal
if (cur < oldest) { 0 500 500
1056 0 ▶ if (sa_at_cas64(&g->cursor, cur, oldest))
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_cas64(&g->cursor, cur, oldest)) 0 0 0
1057 0 sa_at_fetch_add64(&g->lapped, oldest - cur);
1058 13 continue;
1059 }
1060  
1061 /* Look before claiming, because the span decides how far the cursor
1062 * moves and only the head knows it. */
1063 500 rc = sa_ring_read(scratch, cur, &tp, &tl, &dp, &dl, &fl, &span);
1064  
1065 500 ▶ if (rc == SA_READ_PENDING) {
Branch: 1 branch
BranchTrueFalseTotal
if (rc == SA_READ_PENDING) { 0 500 500
1066 /* A hole: a publisher is mid-write, or died mid-write. The same
1067 * escalation the fanout door uses - and it has to be here too,
1068 * because a pool with no fanout reader would otherwise wait on a
1069 * dead process for ever. */
1070 0 ▶ if (!sa_ring_tombstone(scratch, cur)) return SA_READ_PENDING;
Branch: 1 branch
BranchTrueFalseTotal
if (!sa_ring_tombstone(scratch, cur)) return SA_READ_PENDING; 0 0 0
1071 0 continue;
1072 }
1073 500 ▶ if (rc == SA_READ_LAPPED || (fl & SA_SF_CONT)) {
Branch: 2 branches
BranchTrueFalseTotal
if (rc == SA_READ_LAPPED || (fl & SA_SF_CONT)) { 500 0 500
if (rc == SA_READ_LAPPED || (fl & SA_SF_CONT)) { 0 500 500
1074 /* Gone, or the tail of a record whose head somebody else took.
1075 * Advance one and let the next turn look again. */
1076 0 ▶ if (sa_at_cas64(&g->cursor, cur, cur + 1) && rc == SA_READ_LAPPED)
Branch: 2 branches
BranchTrueFalseTotal
if (sa_at_cas64(&g->cursor, cur, cur + 1) && rc == SA_READ_LAPPED) 0 0 0
if (sa_at_cas64(&g->cursor, cur, cur + 1) && rc == SA_READ_LAPPED) 0 0 0
1077 0 sa_at_fetch_add64(&g->lapped, 1);
1078 0 continue;
1079 }
1080  
1081 /* THE CLAIM. Exactly one process wins this, and that is the whole
1082 * mechanism: whoever wins owns `cur` and everybody else moves on. */
1083 500 ▶ if (!sa_at_cas64(&g->cursor, cur, cur + span)) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (!sa_at_cas64(&g->cursor, cur, cur + span)) continue; 6 494 500
1084  
1085 /* We own it - but the read above happened BEFORE the claim, and a
1086 * publisher may have lapped the ring in between. Read it again now
1087 * that it is ours; a record that went during the claim is a loss this
1088 * group counts rather than a body it delivers. */
1089 494 rc = sa_ring_read(scratch, cur, &tp, &tl, &dp, &dl, &fl, &span);
1090 494 ▶ if (rc != SA_READ_OK) {
Branch: 1 branch
BranchTrueFalseTotal
if (rc != SA_READ_OK) { 0 494 494
1091 0 sa_at_fetch_add64(&g->lapped, 1);
1092 0 continue;
1093 }
1094 494 ▶ if (fl & SA_SF_ABANDONED) {
Branch: 1 branch
BranchTrueFalseTotal
if (fl & SA_SF_ABANDONED) { 0 494 494
1095 0 sa_at_fetch_add64(&g->lapped, 1);
1096 0 continue;
1097 }
1098  
1099 /* Bound to a topic: advance past anything else rather than delivering
1100 * it. Another group with another topic has its own cursor and will see
1101 * this record itself. */
1102 494 ▶ if (g->tlen && (tl != g->tlen || memcmp(tp, g->topic, tl))) {
Branch: 3 branches
BranchTrueFalseTotal
if (g->tlen && (tl != g->tlen || memcmp(tp, g->topic, tl))) { 20 474 494
if (g->tlen && (tl != g->tlen || memcmp(tp, g->topic, tl))) { 20 0 20
if (g->tlen && (tl != g->tlen || memcmp(tp, g->topic, tl))) { 7 13 20
1103 7 sa_at_fetch_add64(&g->skipped, 1);
1104 7 continue;
1105 }
1106  
1107 487 sa_at_fetch_add64(&g->delivered, 1);
1108 487 ▶ if (seq) *seq = cur;
Branch: 1 branch
BranchTrueFalseTotal
if (seq) *seq = cur; 487 0 487
1109 487 ▶ if (topic) *topic = tp;
Branch: 1 branch
BranchTrueFalseTotal
if (topic) *topic = tp; 487 0 487
1110 487 ▶ if (tlen) *tlen = tl;
Branch: 1 branch
BranchTrueFalseTotal
if (tlen) *tlen = tl; 487 0 487
1111 487 ▶ if (data) *data = dp;
Branch: 1 branch
BranchTrueFalseTotal
if (data) *data = dp; 487 0 487
1112 487 ▶ if (dlen) *dlen = dl;
Branch: 1 branch
BranchTrueFalseTotal
if (dlen) *dlen = dl; 487 0 487
1113 487 ▶ if (flags) *flags = fl;
Branch: 1 branch
BranchTrueFalseTotal
if (flags) *flags = fl; 487 0 487
1114 487 return SA_READ_OK;
1115 }
1116 0 return SA_READ_PENDING;
1117 }
1118  
1119 #else /* !SA_HAVE_ATOMICS */
1120  
1121 /* No atomics, so no group: sa_group_new is not compiled and the XS refuses to
1122 * make one. Releasing touches nothing shared, though, so the release is the
1123 * same one, here so that DESTROY and the ABI table have it in this build. */
1124 static void sa_group_free(sa_group_h *gh) {
1125 if (!gh) return;
1126 if (gh->scratch) sa_cursor_free(gh->scratch);
1127 free(gh);
1128 }
1129  
1130 #endif /* SA_HAVE_ATOMICS */
1131  
1132 #endif /* SA_RING_H */
« include/sa/sa_cms.h ↑ Summary xs/map.xs »