include/punk_observe/po_shared.h

filter: Statementstmt 97.9% 97 / 99 Branchbran 65.6% 42 / 64 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 85.2% 139 / 163 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« include/punk_observe/po_flame.h ↑ Summary include/punk_observe/po_store.h »
1 /* po_shared.h - the fork-shared arena, and the cardinality cap in it.
2 *
3 * Cardinality is the failure mode that kills observability backends, and it
4 * always arrives the same way: somebody puts a user id, a request id or a
5 * full URL into an attribute, and the series count goes from thousands to
6 * millions in an afternoon. The limit therefore has to be a HARD CAP enforced
7 * at ingest, not a dashboard warning nobody is looking at.
8 *
9 * With phase 4's content-derived series ids there is no central assigner to
10 * hang the counter on, so it lives here: one MAP_SHARED|MAP_ANONYMOUS region,
11 * MAPPED BEFORE THE FORK, incremented atomically by every worker.
12 *
13 * THE ORDER MATTERS AND THE FAILURE IS SILENT. A region mapped AFTER the fork
14 * is private per worker: each one counts its own series, the effective limit
15 * becomes N times what was configured, and nothing anywhere reports a problem
16 * - the operator simply finds the cap did not hold. the tail's ring makes the same
17 * point about its own waker descriptors, and calls the symptom "delivery
18 * works to some workers", which is the same shape of bug.
19 */
20 #ifndef PO_SHARED_H
21 #define PO_SHARED_H
22  
23 #include "punk_observe/po_compat.h"
24 #include "punk_observe/po_time.h"
25  
26 #ifndef _WIN32
27 # include <sys/mman.h>
28 # include <unistd.h>
29 #endif
30  
31 #define PO_SHM_MAGIC 0x4D48534Fu /* "OSHM" */
32  
33 /* Deliberately small and flat. Anything that needs a variable-size shared
34 * structure needs a different mechanism; this is a fixed set of counters. */
35 typedef struct {
36 uint32_t magic;
37 uint32_t slots;
38 po_u64 pid_at_map; /* the process that created it, for the guard */
39 po_u64 series; /* distinct series admitted */
40 po_u64 series_cap; /* 0 = unlimited */
41 po_u64 rejected; /* series refused by the cap */
42 po_u64 overflow; /* records attributed to the overflow series */
43 po_u64 records; /* accepted */
44 po_u64 bytes; /* accepted, for metering */
45  
46 /* The ingest rate window, HERE rather than in each worker.
47 *
48 * A per-worker window on a four-worker box is four times the configured
49 * limit, and the symptom is a limiter that looks like it is not working
50 * rather than like a fork bug. Appended to this struct because the arena
51 * is already mapped before the fork and already carries the counters that
52 * have to be shared. */
53 po_u64 rate_window_start;
54 po_u64 rate_records;
55 po_u64 rate_bytes;
56  
57 po_u64 rate_rejected;
58  
59 /* Lines the live tail was lapped past, summed across workers. The
60 * per-process counter in Observe.xs is honest only to the one worker
61 * that drained; the status page renders in whichever worker got the
62 * request, so a number it can trust has to live here. APPENDED - after
63 * rate_rejected, which was the tail - like the rate window before it,
64 * because the arena is mapped before the fork. */
65 po_u64 live_gaps;
66  
67 /* The seen-series bloom filter, which is what makes `series` a number
68 * rather than a wish.
69 *
70 * THE COUNTER EXISTED FOR MONTHS AND NOTHING FED IT. A series id is
71 * derived - H128 of the canonical label block - precisely so every
72 * worker computes it with no authority and no lock, which also means
73 * there is no admission event to count: knowing a series is NEW needs
74 * the set of ids already seen. A flat page cannot hold a set, but it
75 * can hold a bloom filter over one - and with a second region for the
76 * REFUSED ids, that is enough for the gate as well as the count.
77 * The status page read the counter anyway and showed `0 of 100,000`
78 * over a third of a gigabyte of data: an all-clear nobody checked.
79 *
80 * A false positive reads a genuinely new series as already seen, so the
81 * count can run slightly LOW - the safe direction for a figure whose
82 * job is warning that a cap is near. Two workers racing the same new id
83 * can both count it, so it can also run a worker or two HIGH; the
84 * doctrine is po_shared_admit_series's, one field up: a guard rail, not
85 * an accounting boundary. What must be exact is that it MOVES.
86 * `bloom_words` is written once at map time, before the fork. */
87 po_u64 bloom_words;
88  
89 /* THE WINDOW, which is what clears the old so the new can load.
90 *
91 * A bloom filter can only add, so without this the admitted set was
92 * append-only for the life of the process: a series that stopped
93 * reporting weeks ago - its data long since retained away - still held
94 * one of the cap's slots until a restart. Eviction is still never the
95 * answer; LIVENESS is. Two admitted generations rotate every window_ns:
96 * an active series re-registers itself into the new generation the
97 * moment its next record arrives, and a dead one simply never does.
98 * `series` counts the current generation, so the page reads "active",
99 * not "ever". `rejected` and `overflow` stay monotonic. */
100 po_u64 window_ns;
101 po_u64 epoch_start;
102 po_u64 gen;
103 } po_shm;
104  
105 /* Three equal regions after the header: admitted generation A, admitted
106 * generation B, refused. Which of A/B is current is gen & 1. */
107 #define PO_SHM_BLOOM(m) ((po_u64 *)((char *)(m) + sizeof(po_shm)))
108 #define PO_SHM_REGION(m, i) (PO_SHM_BLOOM(m) + (i) * (m)->bloom_words)
109  
110 typedef struct {
111 po_shm *m;
112 size_t len;
113 int ok;
114 } po_shared;
115  
116 34 static int po_shared_init(po_shared *s, po_u64 series_cap) {
117 #ifndef _WIN32
118 void *p;
119 po_u64 entries, bloom_bytes;
120 34 memset(s, 0, sizeof(*s));
121  
122 /* ~16 bits per expected series at 4 probes keeps the false-positive
123 * rate low enough that the undercount is noise. Sized from the cap
124 * when there is one; a megabyte's worth when there is not, because a
125 * capless install still deserves the number. Anonymous shared pages are
126 * allocated on first touch, so a generous size costs address space and
127 * not resident memory until the series actually exist. */
128 34 ▶ entries = series_cap ? series_cap : 1000000;
Branch: 1 branch
BranchTrueFalseTotal
entries = series_cap ? series_cap : 1000000; 30 4 34
129 34 bloom_bytes = entries * 2; /* 16 bits per entry */
130 34 bloom_bytes = (bloom_bytes + 4095) & ~(po_u64)4095;
131 34 ▶ if (bloom_bytes < 4096) bloom_bytes = 4096;
Branch: 1 branch
BranchTrueFalseTotal
if (bloom_bytes < 4096) bloom_bytes = 4096; 0 34 34
132  
133 34 s->len = 4096 + (size_t)bloom_bytes * 3; /* admitted A, B, refused */
134 34 p = mmap(NULL, s->len, PROT_READ | PROT_WRITE,
135 MAP_SHARED | MAP_ANONYMOUS, -1, 0);
136 34 ▶ if (p == MAP_FAILED) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (p == MAP_FAILED) return 0; 0 34 34
137 34 s->m = (po_shm *)p;
138 34 memset(s->m, 0, sizeof(po_shm));
139 34 s->m->magic = PO_SHM_MAGIC;
140 34 s->m->pid_at_map = (po_u64)getpid();
141 34 s->m->series_cap = series_cap;
142 34 s->m->bloom_words = bloom_bytes / 8;
143 /* A day, unless the caller says otherwise. Long enough that a series
144 * quiet over a weekend deploy does not churn; short enough that last
145 * week's dead pods stop holding cap slots. */
146 34 s->m->window_ns = 86400ULL * 1000000000ULL;
147 34 s->m->epoch_start = po_now_ns();
148 34 s->ok = 1;
149 34 return 1;
150 #else
151 memset(s, 0, sizeof(*s));
152 (void)series_cap;
153 return 0;
154 #endif
155 }
156  
157 16 static void po_shared_free(po_shared *s) {
158 #ifndef _WIN32
159 16 ▶ if (s->m) munmap(s->m, s->len);
Branch: 1 branch
BranchTrueFalseTotal
if (s->m) munmap(s->m, s->len); 16 0 16
160 #endif
161 16 s->m = NULL; s->ok = 0;
162 16 }
163  
164 /* Admit a series, or refuse it.
165 *
166 * Returns 1 if the series may be created, 0 if the cap refuses it.
167 *
168 * OVER THE CAP, THE NEW SERIES IS DROPPED AND THE EXISTING ONES KEEP WORKING.
169 * The tempting alternative - evict something to make room - converts a
170 * cardinality problem into DATA LOSS on whichever series happens to be least
171 * recently used, which is very likely the one somebody has open on a
172 * dashboard right now. Dropping the new one is visible, bounded, and
173 * attributable; evicting an old one is none of those.
174 *
175 * The refusal is counted and the records are attributed to a named overflow
176 * series, in the shape Punk::OpenTelemetry already uses on the client
177 * (otel.metric.overflow), so the data says "you exceeded the cap" rather than
178 * going quietly missing. */
179 128 static int po_shared_admit_series(po_shared *s) {
180 po_u64 cap, cur;
181 128 ▶ if (!s->ok || !s->m) return 1; /* unconfigured: no cap */
Branch: 2 branches
BranchTrueFalseTotal
if (!s->ok || !s->m) return 1; /* unconfigured: no cap */ 128 0 128
if (!s->ok || !s->m) return 1; /* unconfigured: no cap */ 0 128 128
182 128 cap = s->m->series_cap;
183 128 ▶ if (!cap) { po_atomic_add(&s->m->series, 1); return 1; }
Branch: 1 branch
BranchTrueFalseTotal
if (!cap) { po_atomic_add(&s->m->series, 1); return 1; } 100 28 128
184  
185 28 cur = po_atomic_load(&s->m->series);
186 28 ▶ if (cur >= cap) {
Branch: 1 branch
BranchTrueFalseTotal
if (cur >= cap) { 15 13 28
187 15 po_atomic_add(&s->m->rejected, 1);
188 15 po_atomic_add(&s->m->overflow, 1);
189 15 return 0;
190 }
191 /* A racy check-then-increment can overshoot by at most the number of
192 * workers, which is bounded and harmless: the cap is a guard rail, not an
193 * accounting boundary. Making it exact would need a compare-and-swap loop
194 * on the ingest path, and the cost of that is not worth a difference of
195 * N series out of a million. What must be exact is that it STOPS. */
196 13 po_atomic_add(&s->m->series, 1);
197 13 return 1;
198 }
199  
200 #if defined(PO_HAVE_ATOMICS) && !defined(_WIN32)
201 /* region 0 = admitted, region 1 = refused. Two sets, because marking a
202 * REFUSED id in the admitted bloom would make its next record read as an
203 * existing series and sail through the cap it was just refused by. */
204 68 static int po_shm_bloom_test(const po_shm *m, int region,
205 po_u64 id_hi, po_u64 id_lo) {
206 68 const po_u64 *bloom = PO_SHM_REGION((po_shm *)m, region);
207 int k;
208 100 ▶ for (k = 0; k < 4; k++) {
Branch: 1 branch
BranchTrueFalseTotal
for (k = 0; k < 4; k++) { 92 8 100
209 /* Double hashing: probe_i = hi + i*lo, on the halves the id is. */
210 92 po_u64 bit = (id_hi + (po_u64)k * id_lo) % (m->bloom_words * 64);
211 92 po_u64 mask = (po_u64)1 << (bit & 63);
212 92 if (!(__atomic_load_n((po_u64 *)&bloom[bit >> 6], __ATOMIC_SEQ_CST)
213 92 ▶ & mask)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
& mask)) return 0; 60 32 92
214 }
215 8 return 1;
216 }
217  
218 22 static void po_shm_bloom_set(po_shm *m, int region, po_u64 id_hi, po_u64 id_lo) {
219 22 po_u64 *bloom = PO_SHM_REGION(m, region);
220 int k;
221 110 ▶ for (k = 0; k < 4; k++) {
Branch: 1 branch
BranchTrueFalseTotal
for (k = 0; k < 4; k++) { 88 22 110
222 88 po_u64 bit = (id_hi + (po_u64)k * id_lo) % (m->bloom_words * 64);
223 88 po_u64 mask = (po_u64)1 << (bit & 63);
224 88 (void)__atomic_fetch_or(&bloom[bit >> 6], mask, __ATOMIC_SEQ_CST);
225 }
226 22 }
227 #endif
228  
229 #if defined(PO_HAVE_ATOMICS) && !defined(_WIN32)
230 /* The rotation itself, taken by whoever wins the epoch CAS. The region that
231 * was `previous` becomes `current` and is cleared first; refused is cleared
232 * with it, so a series refused last window gets one fresh chance against the
233 * freed slots. Workers racing the memset can lose a just-set bit, which
234 * costs a recount later - the guard-rail doctrine, again. */
235 2 static void po_shm_rotate(po_shm *m) {
236 2 po_u64 next = m->gen + 1;
237 2 memset(PO_SHM_REGION(m, (int)(next & 1)), 0, (size_t)m->bloom_words * 8);
238 2 memset(PO_SHM_REGION(m, 2), 0, (size_t)m->bloom_words * 8);
239 2 po_atomic_store(&m->series, 0);
240 2 __atomic_store_n(&m->gen, next, __ATOMIC_SEQ_CST);
241 2 }
242  
243 28 static void po_shm_maybe_rotate(po_shm *m) {
244 po_u64 now, epoch;
245 56 ▶ if (!m->window_ns) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!m->window_ns) return; 0 28 28
246 28 now = po_now_ns();
247 28 epoch = __atomic_load_n(&m->epoch_start, __ATOMIC_SEQ_CST);
248 28 ▶ if (now < epoch || now - epoch < m->window_ns) return;
Branch: 2 branches
BranchTrueFalseTotal
if (now < epoch || now - epoch < m->window_ns) return; 28 0 28
if (now < epoch || now - epoch < m->window_ns) return; 28 0 28
249 /* One winner per window: the CAS on the epoch is the election. */
250 0 ▶ if (__atomic_compare_exchange_n(&m->epoch_start, &epoch, now, 0,
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_compare_exchange_n(&m->epoch_start, &epoch, now, 0, 0 0 0
251 __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST))
252 0 po_shm_rotate(m);
253 }
254 #endif
255  
256 /* Force one id into the admitted set, cap or no cap: the overflow series
257 * itself has to be admitted or attributing to it would loop. Counts it once. */
258 3 static void po_shared_series_force(po_shared *s, po_u64 id_hi, po_u64 id_lo) {
259 #if defined(PO_HAVE_ATOMICS) && !defined(_WIN32)
260 int cur;
261 3 ▶ if (!s->ok || !s->m || !s->m->bloom_words) return;
Branch: 3 branches
BranchTrueFalseTotal
if (!s->ok || !s->m || !s->m->bloom_words) return; 3 0 3
if (!s->ok || !s->m || !s->m->bloom_words) return; 3 0 3
if (!s->ok || !s->m || !s->m->bloom_words) return; 0 3 3
262 3 po_shm_maybe_rotate(s->m);
263 3 cur = (int)(__atomic_load_n(&s->m->gen, __ATOMIC_SEQ_CST) & 1);
264 3 ▶ if (po_shm_bloom_test(s->m, cur, id_hi, id_lo)) return;
Branch: 1 branch
BranchTrueFalseTotal
if (po_shm_bloom_test(s->m, cur, id_hi, id_lo)) return; 1 2 3
265 2 po_shm_bloom_set(s->m, cur, id_hi, id_lo);
266 2 po_atomic_add(&s->m->series, 1);
267 #else
268 (void)s; (void)id_hi; (void)id_lo;
269 #endif
270 }
271  
272 /* THE GATE. One series id, one answer:
273 *
274 * 1 admit - an existing series, or a new one with room under the cap
275 * 0 refuse - a new series past the cap; attribute the record to the
276 * overflow series and keep going
277 *
278 * OVER THE CAP, THE NEW SERIES IS REFUSED AND EVERY EXISTING ONE KEEPS
279 * WORKING. Eviction would convert a cardinality problem into data loss on
280 * whichever series is least recently used - very likely the one somebody has
281 * open on a dashboard during the incident that caused the explosion.
282 *
283 * `rejected` counts refused SERIES, once each (modulo bloom error);
284 * `overflow` counts refused RECORDS, every one, because that is the volume
285 * the overflow series carries. Races overshoot by at most the worker count -
286 * the guard-rail doctrine one field up. What must be exact is that it STOPS. */
287 25 static int po_shared_series_admit(po_shared *s, po_u64 id_hi, po_u64 id_lo) {
288 #if defined(PO_HAVE_ATOMICS) && !defined(_WIN32)
289 po_u64 cap, n;
290 int cur, prev;
291 25 ▶ if (!s->ok || !s->m || !s->m->bloom_words) return 1; /* no arena: no gate */
Branch: 3 branches
BranchTrueFalseTotal
if (!s->ok || !s->m || !s->m->bloom_words) return 1; /* no arena: no gate */ 25 0 25
if (!s->ok || !s->m || !s->m->bloom_words) return 1; /* no arena: no gate */ 25 0 25
if (!s->ok || !s->m || !s->m->bloom_words) return 1; /* no arena: no gate */ 0 25 25
292  
293 25 po_shm_maybe_rotate(s->m);
294 25 cur = (int)(__atomic_load_n(&s->m->gen, __ATOMIC_SEQ_CST) & 1);
295 25 prev = cur ^ 1;
296  
297 25 ▶ if (po_shm_bloom_test(s->m, cur, id_hi, id_lo)) return 1; /* this window */
Branch: 1 branch
BranchTrueFalseTotal
if (po_shm_bloom_test(s->m, cur, id_hi, id_lo)) return 1; /* this window */ 4 21 25
298  
299 /* ADMITTED LAST WINDOW AND STILL ALIVE: it re-registers into the new
300 * generation, uncapped. It was under the cap when it was admitted, and
301 * refusing an established series because newcomers filled the window
302 * first would be the eviction this design refuses, upside down. */
303 21 ▶ if (po_shm_bloom_test(s->m, prev, id_hi, id_lo)) {
Branch: 1 branch
BranchTrueFalseTotal
if (po_shm_bloom_test(s->m, prev, id_hi, id_lo)) { 2 19 21
304 2 po_shm_bloom_set(s->m, cur, id_hi, id_lo);
305 2 po_atomic_add(&s->m->series, 1);
306 2 return 1;
307 }
308  
309 19 ▶ if (po_shm_bloom_test(s->m, 2, id_hi, id_lo)) { /* already refused */
Branch: 1 branch
BranchTrueFalseTotal
if (po_shm_bloom_test(s->m, 2, id_hi, id_lo)) { /* already refused */ 1 18 19
310 1 po_atomic_add(&s->m->overflow, 1);
311 1 return 0;
312 }
313  
314 18 cap = s->m->series_cap;
315 18 n = po_atomic_load(&s->m->series);
316 18 ▶ if (!cap || n < cap) {
Branch: 2 branches
BranchTrueFalseTotal
if (!cap || n < cap) { 18 0 18
if (!cap || n < cap) { 14 4 18
317 14 po_shm_bloom_set(s->m, cur, id_hi, id_lo);
318 14 po_atomic_add(&s->m->series, 1);
319 14 return 1;
320 }
321  
322 4 po_shm_bloom_set(s->m, 2, id_hi, id_lo);
323 4 po_atomic_add(&s->m->rejected, 1);
324 4 po_atomic_add(&s->m->overflow, 1);
325 4 return 0;
326 #else
327 (void)s; (void)id_hi; (void)id_lo;
328 return 1;
329 #endif
330 }
331  
332 19 static void po_shared_record(po_shared *s, po_u64 n, po_u64 bytes) {
333 19 ▶ if (!s->ok || !s->m) return;
Branch: 2 branches
BranchTrueFalseTotal
if (!s->ok || !s->m) return; 19 0 19
if (!s->ok || !s->m) return; 0 19 19
334 19 po_atomic_add(&s->m->records, n);
335 19 po_atomic_add(&s->m->bytes, bytes);
336 }
337  
338 /* Is this actually shared? A test asserts a write in one process is visible
339 * in another; this is the cheap self-check for the boot diagnostic. */
340 52 static int po_shared_is_shared(const po_shared *s) {
341 #ifdef PO_HAVE_ATOMICS
342 52 ▶ return s->ok && s->m && s->m->magic == PO_SHM_MAGIC;
Branch: 3 branches
BranchTrueFalseTotal
return s->ok && s->m && s->m->magic == PO_SHM_MAGIC; 52 0 52
return s->ok && s->m && s->m->magic == PO_SHM_MAGIC; 52 0 52
return s->ok && s->m && s->m->magic == PO_SHM_MAGIC; 52 0 52
343 #else
344 /* Without atomics the region is shared but the counters are not safe to
345 * increment from several processes. Saying so is better than miscounting
346 * quietly, and phase 15 refuses a multi-worker configuration on it. */
347 return 0;
348 #endif
349 }
350  
351 #endif /* PO_SHARED_H */
« include/punk_observe/po_flame.h ↑ Summary include/punk_observe/po_store.h »