| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (sa_at_load32_acq(&h->magic) != SA_RING_MAGIC) { |
67 |
0 |
67 |
|
| 350 |
67 |
▶ | if (!nslots || !slot_size |
Branch: 2 branches
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| || sa_ring_capacity(slot_size) == 0 |
67 |
0 |
67 |
|
| 352 |
67 |
▶ | || sa_ring_bytes(nslots, slot_size) > e->len) { |
Branch: 1 branch
| Branch | True | False | Total |
| || 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (!sa_wait_magic32(&h->magic, SA_RING_MAGIC)) { |
0 |
67 |
67 |
|
| 372 |
0 |
▶ | if (err) *err = SA_E_MAGIC; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| || (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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| ? 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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 |
2617 |
| static int sa_cursor_room(sa_cursor *c, size_t n) { |
| 560 |
|
| char *p; |
| 561 |
2617 |
▶ | if (n <= c->scratch_sz) return 1; |
Branch: 1 branch
| Branch | True | False | Total |
| if (n <= c->scratch_sz) return 1; |
2603 |
14 |
2617 |
|
| 562 |
14 |
| p = (char *)realloc(c->scratch, n); |
| 563 |
14 |
▶ | if (!p) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| 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 |
3886 |
| 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 |
3886 |
| sa_ring *r = c->ring; |
| 580 |
3886 |
| 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 |
3886 |
| have = sa_at_load64_acq(&s->end); |
| 586 |
3886 |
▶ | if (have < want) return SA_READ_PENDING; |
Branch: 1 branch
| Branch | True | False | Total |
| if (have < want) return SA_READ_PENDING; |
123 |
3763 |
3886 |
|
| 587 |
3763 |
▶ | if (have > want) return SA_READ_LAPPED; |
Branch: 1 branch
| Branch | True | False | Total |
| if (have > want) return SA_READ_LAPPED; |
1146 |
2617 |
3763 |
|
| 588 |
|
| |
| 589 |
2617 |
| tl = s->tlen; |
| 590 |
2617 |
| dl = s->dlen; |
| 591 |
2617 |
| total = s->total; |
| 592 |
2617 |
| parts = s->parts; |
| 593 |
2617 |
| fl = s->flags; |
| 594 |
2617 |
▶ | if (!parts) return SA_READ_LAPPED; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!parts) return SA_READ_LAPPED; |
0 |
2617 |
2617 |
|
| 595 |
2617 |
▶ | if ((uint64_t)tl + (uint64_t)dl > r->payload_max) return SA_READ_LAPPED; |
Branch: 1 branch
| Branch | True | False | Total |
| if ((uint64_t)tl + (uint64_t)dl > r->payload_max) return SA_READ_LAPPED; |
0 |
2617 |
2617 |
|
| 596 |
2617 |
▶ | if ((uint64_t)parts > r->parts_max) return SA_READ_LAPPED; |
Branch: 1 branch
| Branch | True | False | Total |
| if ((uint64_t)parts > r->parts_max) return SA_READ_LAPPED; |
0 |
2617 |
2617 |
|
| 597 |
2617 |
▶ | if ((uint64_t)tl + (uint64_t)total > r->record_max) return SA_READ_LAPPED; |
Branch: 1 branch
| Branch | True | False | Total |
| if ((uint64_t)tl + (uint64_t)total > r->record_max) return SA_READ_LAPPED; |
0 |
2617 |
2617 |
|
| 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 |
2617 |
▶ | if (!sa_cursor_room(c, (size_t)tl + (size_t)total)) return SA_READ_LAPPED; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!sa_cursor_room(c, (size_t)tl + (size_t)total)) return SA_READ_LAPPED; |
0 |
2617 |
2617 |
|
| 605 |
|
| |
| 606 |
2617 |
| 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 |
2617 |
| 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 |
2617 |
▶ | if (sa_at_load64_acq(&s->begin) != want) return SA_READ_LAPPED; |
Branch: 1 branch
| Branch | True | False | Total |
| if (sa_at_load64_acq(&s->begin) != want) return SA_READ_LAPPED; |
96 |
2521 |
2617 |
|
| 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 |
2521 |
▶ | if (parts > 1) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (parts > 1) { |
24 |
2497 |
2521 |
|
| 622 |
24 |
| uint64_t got = dl, i; |
| 623 |
801 |
▶ | for (i = 1; i < parts; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (got != (uint64_t)total) return SA_READ_LAPPED; |
0 |
24 |
24 |
|
| 636 |
24 |
| dl = total; |
| 637 |
|
| } |
| 638 |
|
| |
| 639 |
2521 |
▶ | if (flags) *flags = fl; |
Branch: 1 branch
| Branch | True | False | Total |
| if (flags) *flags = fl; |
2521 |
0 |
2521 |
|
| 640 |
2521 |
▶ | if (topic) *topic = c->scratch; |
Branch: 1 branch
| Branch | True | False | Total |
| if (topic) *topic = c->scratch; |
2521 |
0 |
2521 |
|
| 641 |
2521 |
▶ | if (tlen) *tlen = tl; |
Branch: 1 branch
| Branch | True | False | Total |
| if (tlen) *tlen = tl; |
2521 |
0 |
2521 |
|
| 642 |
2521 |
▶ | if (data) *data = c->scratch + tl; |
Branch: 1 branch
| Branch | True | False | Total |
| if (data) *data = c->scratch + tl; |
2521 |
0 |
2521 |
|
| 643 |
2521 |
▶ | if (dlen) *dlen = dl; |
Branch: 1 branch
| Branch | True | False | Total |
| if (dlen) *dlen = dl; |
2521 |
0 |
2521 |
|
| 644 |
2521 |
▶ | if (span) *span = parts; |
Branch: 1 branch
| Branch | True | False | Total |
| if (span) *span = parts; |
2521 |
0 |
2521 |
|
| 645 |
2521 |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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 |
380 |
| static uint64_t sa_cursor_catchup(sa_cursor *c) { |
| 687 |
|
| #if !SA_HAVE_ATOMICS |
| 688 |
|
| (void)c; |
| 689 |
|
| return 0; |
| 690 |
|
| #else |
| 691 |
380 |
| sa_ring *r = c->ring; |
| 692 |
380 |
| uint64_t end = sa_at_load64_acq(&r->hdr->seq); |
| 693 |
|
| uint64_t oldest, missed; |
| 694 |
|
| |
| 695 |
380 |
▶ | if (end <= r->nslots) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (end <= r->nslots) return 0; |
168 |
212 |
380 |
|
| 696 |
212 |
| oldest = end - r->nslots; |
| 697 |
212 |
▶ | if (c->seq >= oldest) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (c->seq >= oldest) return 0; |
198 |
14 |
212 |
|
| 698 |
|
| |
| 699 |
14 |
| missed = oldest - c->seq; |
| 700 |
14 |
| c->lapped += missed; |
| 701 |
14 |
| c->seq = oldest; |
| 702 |
14 |
| 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 |
123 |
| 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 |
123 |
| sa_ring *r = c->ring; |
| 733 |
123 |
| sa_slot *s = SA_SLOT_AT(r, want); |
| 734 |
123 |
| 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 |
123 |
▶ | if (c->hole_seq != want) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (c->hole_seq != want) { |
3 |
120 |
123 |
|
| 758 |
3 |
| c->hole_seq = want; |
| 759 |
3 |
| c->hole_next_us = 0; |
| 760 |
3 |
| c->hole_counted = 0; |
| 761 |
3 |
| c->hole_since_us = sa_now_us(); |
| 762 |
3 |
| c->hole_hb0 = sa_peer_hb(a, sa_at_load64_acq(&s->claim)); |
| 763 |
|
| } |
| 764 |
|
| |
| 765 |
246123 |
▶ | for (spin = 0; spin < 2000; spin++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (spin = 0; spin < 2000; spin++) { |
246000 |
123 |
246123 |
|
| 766 |
246000 |
▶ | if (sa_at_load64_acq(&s->end) == want) { /* it landed */ |
Branch: 1 branch
| Branch | True | False | Total |
| if (sa_at_load64_acq(&s->end) == want) { /* it landed */ |
0 |
246000 |
246000 |
|
| 767 |
0 |
| c->hole_seq = 0; |
| 768 |
0 |
| return 0; |
| 769 |
|
| } |
| 770 |
|
| } |
| 771 |
|
| |
| 772 |
123 |
| now = sa_now_us(); |
| 773 |
123 |
| grace = sa_at_load32_acq(&a->hdr->reap_grace_us); |
| 774 |
123 |
▶ | if (!grace) grace = 1000; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!grace) grace = 1000; |
0 |
123 |
123 |
|
| 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 |
123 |
▶ | if (c->hole_next_us && now < c->hole_next_us) return 0; |
Branch: 2 branches
| Branch | True | False | Total |
| if (c->hole_next_us && now < c->hole_next_us) return 0; |
7 |
116 |
123 |
| 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 |
116 |
▶ | if (now >= c->hole_since_us && now - c->hole_since_us < grace) return 0; |
Branch: 2 branches
| Branch | True | False | Total |
| if (now >= c->hole_since_us && now - c->hole_since_us < grace) return 0; |
116 |
0 |
116 |
| if (now >= c->hole_since_us && now - c->hole_since_us < grace) return 0; |
114 |
2 |
116 |
|
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (rc == SA_READ_PENDING) { |
0 |
40 |
40 |
|
| 864 |
0 |
▶ | if (!sa_ring_tombstone(c, c->seq)) break; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (rc == SA_READ_LAPPED) { c->lapped++; c->seq++; continue; } |
0 |
40 |
40 |
|
| 870 |
40 |
▶ | if (flags & SA_SF_CONT) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (err) *err = SA_E_OK; |
70 |
0 |
70 |
|
| 938 |
70 |
▶ | if (!r) { if (err) *err = SA_E_NOENT; return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| || tlen >= SA_GROUP_TOPIC) { |
0 |
70 |
70 |
|
| 941 |
0 |
▶ | if (err) *err = SA_E_NAME; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (g->tlen != tlen |
21 |
0 |
21 |
|
| 957 |
21 |
▶ | || (tlen && memcmp(g->topic, topic, tlen))) { |
Branch: 2 branches
| Branch | True | False | Total |
| || (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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (!gh) return; |
0 |
64 |
64 |
|
| 1014 |
64 |
▶ | if (gh->scratch) sa_cursor_free(gh->scratch); |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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 |
520 |
▶ | for (guard = 0; guard < 1024; guard++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (guard = 0; guard < 1024; guard++) { |
520 |
0 |
520 |
|
| 1042 |
520 |
| uint64_t cur = sa_at_load64_acq(&g->cursor); |
| 1043 |
520 |
| uint64_t end = sa_at_load64_acq(&h->seq); |
| 1044 |
520 |
| uint64_t span = 1, oldest; |
| 1045 |
520 |
| const char *tp = NULL, *dp = NULL; |
| 1046 |
520 |
| uint32_t tl = 0, dl = 0, fl = 0; |
| 1047 |
|
| int rc; |
| 1048 |
|
| |
| 1049 |
1007 |
▶ | if (cur >= end) return SA_READ_PENDING; /* nothing published */ |
Branch: 1 branch
| Branch | True | False | Total |
| if (cur >= end) return SA_READ_PENDING; /* nothing published */ |
21 |
499 |
520 |
|
| 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 |
499 |
▶ | oldest = (end > r->nslots) ? end - r->nslots : 1; |
Branch: 1 branch
| Branch | True | False | Total |
| oldest = (end > r->nslots) ? end - r->nslots : 1; |
0 |
499 |
499 |
|
| 1055 |
499 |
▶ | if (cur < oldest) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (cur < oldest) { |
0 |
499 |
499 |
|
| 1056 |
0 |
▶ | if (sa_at_cas64(&g->cursor, cur, oldest)) |
Branch: 1 branch
| Branch | True | False | Total |
| if (sa_at_cas64(&g->cursor, cur, oldest)) |
0 |
0 |
0 |
|
| 1057 |
0 |
| sa_at_fetch_add64(&g->lapped, oldest - cur); |
| 1058 |
12 |
| continue; |
| 1059 |
|
| } |
| 1060 |
|
| |
| 1061 |
|
| /* Look before claiming, because the span decides how far the cursor |
| 1062 |
|
| * moves and only the head knows it. */ |
| 1063 |
499 |
| rc = sa_ring_read(scratch, cur, &tp, &tl, &dp, &dl, &fl, &span); |
| 1064 |
|
| |
| 1065 |
499 |
▶ | if (rc == SA_READ_PENDING) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (rc == SA_READ_PENDING) { |
0 |
499 |
499 |
|
| 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
| Branch | True | False | Total |
| if (!sa_ring_tombstone(scratch, cur)) return SA_READ_PENDING; |
0 |
0 |
0 |
|
| 1071 |
0 |
| continue; |
| 1072 |
|
| } |
| 1073 |
499 |
▶ | if (rc == SA_READ_LAPPED || (fl & SA_SF_CONT)) { |
Branch: 2 branches
| Branch | True | False | Total |
| if (rc == SA_READ_LAPPED || (fl & SA_SF_CONT)) { |
499 |
0 |
499 |
| if (rc == SA_READ_LAPPED || (fl & SA_SF_CONT)) { |
0 |
499 |
499 |
|
| 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
| Branch | True | False | Total |
| 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 |
499 |
▶ | if (!sa_at_cas64(&g->cursor, cur, cur + span)) continue; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!sa_at_cas64(&g->cursor, cur, cur + span)) continue; |
5 |
494 |
499 |
|
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (seq) *seq = cur; |
487 |
0 |
487 |
|
| 1109 |
487 |
▶ | if (topic) *topic = tp; |
Branch: 1 branch
| Branch | True | False | Total |
| if (topic) *topic = tp; |
487 |
0 |
487 |
|
| 1110 |
487 |
▶ | if (tlen) *tlen = tl; |
Branch: 1 branch
| Branch | True | False | Total |
| if (tlen) *tlen = tl; |
487 |
0 |
487 |
|
| 1111 |
487 |
▶ | if (data) *data = dp; |
Branch: 1 branch
| Branch | True | False | Total |
| if (data) *data = dp; |
487 |
0 |
487 |
|
| 1112 |
487 |
▶ | if (dlen) *dlen = dl; |
Branch: 1 branch
| Branch | True | False | Total |
| if (dlen) *dlen = dl; |
487 |
0 |
487 |
|
| 1113 |
487 |
▶ | if (flags) *flags = fl; |
Branch: 1 branch
| Branch | True | False | Total |
| 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 */ |