include/sa/sa_frozen.h

filter: Statementstmt 90.0% 81 / 90 Branchbran 50.0% 37 / 74 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 71.9% 118 / 164 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« xs/abi.xs ↑ Summary include/sa/sa_map.h »
1 #ifndef SA_FROZEN_H
2 #define SA_FROZEN_H
3  
4 /* sa_frozen.h - a block of bytes republished in place, read by everyone at
5 * once. Perl-free, and Frozen-free: this file knows nothing about what is in
6 * the bytes.
7 *
8 * ---- what this is for -------------------------------------------------------
9 *
10 * Everything else in this dist stores values a caller has already flattened:
11 * keys and values are opaque bytes, so a nested structure has to be serialised
12 * on the way in and rebuilt on the way out. Rebuilding is the expensive half,
13 * and it happens on EVERY read.
14 *
15 * A Frozen block is not rebuilt. It is a flat, offset-addressed structure whose
16 * fields are read where they lie, so a reader looks up one key without
17 * materialising the other ten thousand. That is a different shape of thing from
18 * a map, and it wants a different tenant: one big value that changes rarely and
19 * is read constantly, rather than many small ones that change all the time.
20 *
21 * Configuration, routing tables, feature flags, a compiled ruleset. The block is
22 * built once by whoever has the data and read by every worker for the life of
23 * the process.
24 *
25 * ---- publishing without stopping the readers -------------------------------
26 *
27 * A block cannot be edited in place. It is offset-addressed throughout, so a
28 * change to one string moves everything after it, and a reader halfway through
29 * such an edit would follow an offset into the middle of something else.
30 *
31 * So a publish never touches the block anybody is reading. The region holds
32 * SEVERAL slots, and a publish writes the new block into the slot furthest from
33 * use, then points `current` at it with a release store. A reader takes
34 * `current` with an acquire load and reads that slot. Neither waits for the
35 * other, and no reader ever sees a half-written block.
36 *
37 * ---- what a reader has to accept -------------------------------------------
38 *
39 * A view borrows the bytes where they lie. It does not copy them, which is the
40 * whole reason this is faster than handing the same structure through a pipe -
41 * and it means the bytes are not the reader's to keep.
42 *
43 * After `slots` further publishes the slot a view is reading is reused. The
44 * view then reads a DIFFERENT block: still a structurally valid one, still
45 * inside its own bounds, but not the one it was opened on. Every slot carries
46 * the generation it was written with, so a reader can ask whether the ground
47 * moved under it, and that is what `sa_frozen_fresh` is for.
48 *
49 * The rule that follows is short: take a view, read it, drop it. A view held
50 * across a config reload is the one thing this cannot make safe, and a view
51 * taken per request costs a borrow.
52 *
53 * ---- publishing takes the lock, and that is fine ---------------------------
54 *
55 * A publish copies a whole block, so it is already thousands of times the cost
56 * of the compare-and-swap that would let two of them race. Two processes
57 * publishing at once want serialising anyway - they disagree about what the
58 * configuration is, and the answer is that one of them wins outright rather
59 * than that the slots interleave.
60 *
61 * Reads take nothing. That is the half that had to be free.
62 *
63 * Needs sa_arena.h.
64 */
65  
66 #include "sa/sa_arena.h"
67  
68 #define SA_FROZEN_MAGIC 0x5A4F5246u /* 'F','R','O','Z' little-endian */
69  
70 #define SA_FROZEN_MIN_SLOTS 2
71 #define SA_FROZEN_MAX_SLOTS 16
72  
73 /* Written before the bytes, read after them. `gen` is what tells a reader
74 * whether the slot still holds what it opened. */
75 typedef struct {
76 volatile uint64_t len;
77 volatile uint64_t gen;
78 } sa_frozen_slot;
79  
80 typedef struct {
81 volatile uint32_t magic; /* published LAST at init */
82 uint32_t nslots;
83 uint64_t slot_bytes; /* the most one block may be */
84 uint64_t slots_off; /* from the TENANT's base */
85 volatile uint64_t generation; /* bumped once per publish, never reused */
86 volatile uint32_t current; /* the slot a reader should take */
87 uint32_t pad;
88 volatile uint64_t published;
89 volatile uint64_t refused; /* did not fit a slot */
90 volatile unsigned char locks[SA_LOCK_STRIPES];
91 } sa_frozen_hdr;
92  
93 typedef struct sa_frozen {
94 sa_region *arena;
95 sa_frozen_hdr *hdr;
96 unsigned char *slots; /* nslots * (slot header + slot_bytes) */
97 uint32_t nslots;
98 uint64_t slot_bytes;
99 /* A reader over the live block, kept by this process between reads and
100 * replaced when a publish moves on. Opaque here, because this file does
101 * not know what the bytes are; the layer that does supplies the release. */
102 void *reader;
103 void (*reader_free)(void *reader);
104 uint64_t reader_gen;
105 uint32_t reader_slot;
106 } sa_frozen;
107  
108 #define SA_FZ_OK 0
109 #define SA_FZ_EMPTY (-1) /* nothing has been published yet */
110 #define SA_FZ_BIG (-2) /* the block does not fit a slot */
111  
112 /* One slot is its header, then the block, aligned so the block starts on the
113 * arena's alignment - a structure read in place should not be read across an
114 * unaligned boundary on the platforms that care. */
115 123 static uint64_t sa_frozen_stride(uint64_t slot_bytes) {
116 123 return sa_align_up((uint64_t)sizeof(sa_frozen_slot))
117 123 + sa_align_up(slot_bytes);
118 }
119  
120 38 static uint64_t sa_frozen_bytes(uint64_t slot_bytes, uint32_t nslots) {
121 38 return sa_align_up((uint64_t)sizeof(sa_frozen_hdr))
122 38 + sa_frozen_stride(slot_bytes) * (uint64_t)nslots;
123 }
124  
125 85 static sa_frozen_slot *sa_frozen_slot_at(sa_frozen *f, uint32_t i) {
126 255 return (sa_frozen_slot *)(f->slots
127 85 + (size_t)(sa_frozen_stride(f->slot_bytes) * (uint64_t)i));
128 }
129  
130 40 static unsigned char *sa_frozen_body_at(sa_frozen *f, uint32_t i) {
131 40 return (unsigned char *)sa_frozen_slot_at(f, i)
132 40 + (size_t)sa_align_up((uint64_t)sizeof(sa_frozen_slot));
133 }
134  
135 13 static sa_frozen *sa_frozen_bind(sa_region *arena, sa_reg *e,
136 uint64_t slot_bytes, uint32_t nslots, int *err)
137 {
138 #if !SA_HAVE_ATOMICS
139 (void)arena; (void)e; (void)slot_bytes; (void)nslots;
140 if (err) *err = SA_E_NOATOMICS;
141 return NULL;
142 #else
143 sa_frozen *f;
144 sa_frozen_hdr *h;
145 uint64_t hash;
146  
147 13 ▶ if (err) *err = SA_E_OK;
Branch: 1 branch
BranchTrueFalseTotal
if (err) *err = SA_E_OK; 13 0 13
148 13 ▶ 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; } 13 0 13
if (!arena || !e) { if (err) *err = SA_E_NOENT; return NULL; } 0 13 13
if (!arena || !e) { if (err) *err = SA_E_NOENT; return NULL; } 0 0 0
149  
150 13 h = (sa_frozen_hdr *)sa_ptr_len(arena, e->off, sizeof(sa_frozen_hdr));
151 13 ▶ 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 13 13
if (!h) { if (err) *err = SA_E_NOENT; return NULL; } 0 0 0
152  
153 13 ▶ if (sa_at_load32_acq(&h->magic) != SA_FROZEN_MAGIC) {
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_load32_acq(&h->magic) != SA_FROZEN_MAGIC) { 12 1 13
154 12 hash = sa_at_fnv(e->name, strlen(e->name));
155 12 ▶ if (sa_at_lock(h->locks, hash)) {
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_lock(h->locks, hash)) { 12 0 12
156 12 ▶ if (sa_at_load32_acq(&h->magic) != SA_FROZEN_MAGIC) {
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_load32_acq(&h->magic) != SA_FROZEN_MAGIC) { 12 0 12
157 12 ▶ if (!slot_bytes || nslots < SA_FROZEN_MIN_SLOTS
Branch: 2 branches
BranchTrueFalseTotal
if (!slot_bytes || nslots < SA_FROZEN_MIN_SLOTS 12 0 12
if (!slot_bytes || nslots < SA_FROZEN_MIN_SLOTS 12 0 12
158 12 ▶ || nslots > SA_FROZEN_MAX_SLOTS
Branch: 1 branch
BranchTrueFalseTotal
|| nslots > SA_FROZEN_MAX_SLOTS 12 0 12
159 12 ▶ || sa_frozen_bytes(slot_bytes, nslots) > e->len) {
Branch: 1 branch
BranchTrueFalseTotal
|| sa_frozen_bytes(slot_bytes, nslots) > e->len) { 0 12 12
160 0 sa_at_unlock(h->locks, hash);
161 0 ▶ if (err) *err = SA_E_FULL;
Branch: 1 branch
BranchTrueFalseTotal
if (err) *err = SA_E_FULL; 0 0 0
162 0 return NULL;
163 }
164 12 memset((void *)h, 0,
165 12 (size_t)sa_frozen_bytes(slot_bytes, nslots));
166 12 h->nslots = nslots;
167 12 h->slot_bytes = slot_bytes;
168 12 h->slots_off = sa_align_up((uint64_t)sizeof(sa_frozen_hdr));
169 12 sa_at_store32_rel(&h->magic, SA_FROZEN_MAGIC);
170 }
171 12 sa_at_unlock(h->locks, hash);
172 }
173 12 ▶ if (!sa_wait_magic32(&h->magic, SA_FROZEN_MAGIC)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!sa_wait_magic32(&h->magic, SA_FROZEN_MAGIC)) { 0 12 12
174 0 ▶ if (err) *err = SA_E_MAGIC;
Branch: 1 branch
BranchTrueFalseTotal
if (err) *err = SA_E_MAGIC; 0 0 0
175 0 return NULL;
176 }
177 }
178  
179 /* A caller asking for a shape this does not have would be reading somebody
180 * else's blocks through the wrong arithmetic. Say no, as every other
181 * tenant does. */
182 13 ▶ if ((slot_bytes && h->slot_bytes != slot_bytes)
Branch: 2 branches
BranchTrueFalseTotal
if ((slot_bytes && h->slot_bytes != slot_bytes) 13 0 13
if ((slot_bytes && h->slot_bytes != slot_bytes) 13 0 13
183 13 ▶ || (nslots && h->nslots != nslots)) {
Branch: 2 branches
BranchTrueFalseTotal
|| (nslots && h->nslots != nslots)) { 13 0 13
|| (nslots && h->nslots != nslots)) { 0 13 13
184 0 ▶ if (err) *err = SA_E_SHAPE;
Branch: 1 branch
BranchTrueFalseTotal
if (err) *err = SA_E_SHAPE; 0 0 0
185 0 return NULL;
186 }
187  
188 13 f = (sa_frozen *)calloc(1, sizeof(sa_frozen));
189 13 ▶ if (!f) { if (err) *err = SA_E_NOMEM; return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (!f) { if (err) *err = SA_E_NOMEM; return NULL; } 0 13 13
if (!f) { if (err) *err = SA_E_NOMEM; return NULL; } 0 0 0
190 13 f->arena = arena;
191 13 f->hdr = h;
192 13 f->slots = (unsigned char *)h + (size_t)h->slots_off;
193 13 f->nslots = h->nslots;
194 13 f->slot_bytes = h->slot_bytes;
195 13 return f;
196 #endif
197 }
198  
199 13 static void sa_frozen_free(sa_frozen *f) {
200 13 ▶ if (f && f->reader && f->reader_free) f->reader_free(f->reader);
Branch: 3 branches
BranchTrueFalseTotal
if (f && f->reader && f->reader_free) f->reader_free(f->reader); 13 0 13
if (f && f->reader && f->reader_free) f->reader_free(f->reader); 1 12 13
if (f && f->reader && f->reader_free) f->reader_free(f->reader); 1 0 1
201 13 free(f);
202 13 }
203  
204 /* Put a block in the slot furthest from use and point `current` at it.
205 *
206 * The generation is taken INSIDE the lock and never reused, so a reader that
207 * remembers one can always tell whether the slot it holds is still that
208 * generation's. */
209 19 static int sa_frozen_publish(sa_frozen *f, const void *bytes, uint64_t len,
210 uint64_t *gen_out)
211 {
212 #if SA_HAVE_ATOMICS
213 19 sa_frozen_hdr *h = f->hdr;
214 19 uint64_t hash = (uint64_t)(uintptr_t)h;
215 uint32_t next;
216 uint64_t gen;
217 sa_frozen_slot *s;
218  
219 19 ▶ if (gen_out) *gen_out = 0;
Branch: 1 branch
BranchTrueFalseTotal
if (gen_out) *gen_out = 0; 19 0 19
220 19 ▶ if (len > f->slot_bytes) {
Branch: 1 branch
BranchTrueFalseTotal
if (len > f->slot_bytes) { 1 18 19
221 1 sa_at_fetch_add64(&h->refused, 1);
222 1 return SA_FZ_BIG;
223 }
224 /* Waits rather than spins: publishing is rare, and `refused` is documented
225 * as meaning a block did not FIT. A refusal because a spin ran out would be
226 * the same number meaning something else entirely. */
227 18 ▶ if (!sa_lock_wait(h->locks, hash)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!sa_lock_wait(h->locks, hash)) { 0 18 18
228 0 sa_at_fetch_add64(&h->refused, 1);
229 0 return SA_FZ_BIG;
230 }
231  
232 /* The slot after the live one, which is the one no reader has been sent to
233 * for the longest. */
234 18 next = (uint32_t)((sa_at_load32_acq(&h->current) + 1u) % f->nslots);
235 18 s = sa_frozen_slot_at(f, next);
236 18 gen = sa_at_load64_acq(&h->generation) + 1u;
237  
238 /* Length first, then the bytes, then the generation, then `current`. A
239 * reader that arrives partway through this sees the slot's OLD generation
240 * and the old `current`, so it reads the old block - which is whole. */
241 18 sa_at_store64_rel(&s->len, len);
242 18 memcpy(sa_frozen_body_at(f, next), bytes, (size_t)len);
243 18 sa_at_fence_rel();
244 18 sa_at_store64_rel(&s->gen, gen);
245 18 sa_at_store64_rel(&h->generation, gen);
246 18 sa_at_store32_rel(&h->current, next);
247 18 sa_at_fetch_add64(&h->published, 1);
248  
249 18 sa_at_unlock(h->locks, hash);
250 18 ▶ if (gen_out) *gen_out = gen;
Branch: 1 branch
BranchTrueFalseTotal
if (gen_out) *gen_out = gen; 18 0 18
251 18 return SA_FZ_OK;
252 #else
253 (void)f; (void)bytes; (void)len; (void)gen_out;
254 return SA_FZ_BIG;
255 #endif
256 }
257  
258 /* The live block: where it is, how long, and which generation it is.
259 *
260 * The pointer is INTO THE ARENA and is not the caller's to free or to keep. */
261 27 static int sa_frozen_current(sa_frozen *f, const unsigned char **bytes,
262 uint64_t *len, uint64_t *gen, uint32_t *slot)
263 {
264 #if SA_HAVE_ATOMICS
265 uint32_t i;
266 sa_frozen_slot *s;
267  
268 27 ▶ if (!sa_at_load64_acq(&f->hdr->generation)) return SA_FZ_EMPTY;
Branch: 1 branch
BranchTrueFalseTotal
if (!sa_at_load64_acq(&f->hdr->generation)) return SA_FZ_EMPTY; 5 22 27
269  
270 22 i = sa_at_load32_acq(&f->hdr->current);
271 22 ▶ if (i >= f->nslots) return SA_FZ_EMPTY;
Branch: 1 branch
BranchTrueFalseTotal
if (i >= f->nslots) return SA_FZ_EMPTY; 0 22 22
272 22 s = sa_frozen_slot_at(f, i);
273  
274 22 sa_at_fence_acq();
275 22 ▶ if (len) *len = sa_at_load64_acq(&s->len);
Branch: 1 branch
BranchTrueFalseTotal
if (len) *len = sa_at_load64_acq(&s->len); 22 0 22
276 22 ▶ if (gen) *gen = sa_at_load64_acq(&s->gen);
Branch: 1 branch
BranchTrueFalseTotal
if (gen) *gen = sa_at_load64_acq(&s->gen); 21 1 22
277 22 ▶ if (slot) *slot = i;
Branch: 1 branch
BranchTrueFalseTotal
if (slot) *slot = i; 21 1 22
278 22 ▶ if (bytes) *bytes = sa_frozen_body_at(f, i);
Branch: 1 branch
BranchTrueFalseTotal
if (bytes) *bytes = sa_frozen_body_at(f, i); 22 0 22
279 22 return SA_FZ_OK;
280 #else
281 (void)f; (void)bytes; (void)len; (void)gen; (void)slot;
282 return SA_FZ_EMPTY;
283 #endif
284 }
285  
286 /* Whether a slot still holds the generation a reader opened it on.
287 *
288 * This is the whole of what a borrowed view can be told. It cannot be prevented
289 * from going stale - the bytes belong to the arena - but it can always find
290 * out, and a reader that checks after reading knows whether to read again. */
291 5 static int sa_frozen_fresh(sa_frozen *f, uint32_t slot, uint64_t gen) {
292 #if SA_HAVE_ATOMICS
293 5 ▶ if (slot >= f->nslots) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (slot >= f->nslots) return 0; 0 5 5
294 5 return sa_at_load64_acq(&sa_frozen_slot_at(f, slot)->gen) == gen;
295 #else
296 (void)f; (void)slot; (void)gen;
297 return 0;
298 #endif
299 }
300  
301 #endif /* SA_FROZEN_H */
« xs/abi.xs ↑ Summary include/sa/sa_map.h »