include/punk_observe/po_result.h

filter: Statementstmt 100% 67 / 67 Branchbran 76.6% 46 / 60 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 88.9% 113 / 127 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« include/punk_observe/po_limit.h ↑ Summary xs/exec.xs »
1 /* po_result.h - one result shape, and metadata that is never optional.
2 *
3 * A TRUNCATED RESULT THAT LOOKS COMPLETE IS THE OBSERVABILITY EQUIVALENT OF A
4 * GREEN DASHBOARD OVER DROPPED SPANS.
5 *
6 * That is the failure this project exists to stop people having, so every
7 * result carries how much it scanned, whether a budget cut it short, and -
8 * for a percentile - whether the number is exact or estimated. A percentile
9 * whose method is unknown is a number nobody can act on.
10 */
11 #ifndef PO_RESULT_H
12 #define PO_RESULT_H
13  
14 #include "punk_observe/po_compat.h"
15 #include "punk_observe/po_row.h"
16  
17 #define PO_RES_ROWS 1 /* individual rows: logs, spans, traces */
18 #define PO_RES_SERIES 2 /* grouped aggregates */
19 #define PO_RES_SCALAR 3 /* one number */
20  
21 typedef struct {
22 char key[128]; /* the group key, or empty for a scalar */
23 size_t key_len;
24 double value;
25 po_u64 count;
26 /* for percentiles and averages the accumulator needs the samples */
27 double *samples;
28 uint32_t nsamp, csamp;
29 } po_group;
30  
31 typedef struct {
32 int shape;
33 po_group *g;
34 uint32_t ng, cg;
35  
36 po_row *row; /* PO_RES_ROWS */
37 uint32_t nrow, crow;
38  
39 /* The bucket width a `bucket(1m)` query asked for, carried out to the
40 * caller so a renderer knows the groups are a time series rather than a
41 * set of labels - and how wide each point is. Zero when the query did not
42 * bucket. */
43 po_u64 bucket_ns;
44  
45 /* meta - ALWAYS populated */
46 po_u64 scanned_rows;
47 po_u64 scanned_bytes;
48 po_u64 blocks;
49 po_u64 blocks_skipped;
50 int truncated; /* a budget cut the scan short */
51 int degraded; /* something was approximated */
52 int exact; /* percentile method: 1 exact, 0 estimated */
53 int steps; /* how many times the executor yielded */
54  
55 /* Too many distinct groups to answer. NOT a truncation: a bucketed chart
56 * missing its tail looks like a service that stopped reporting, so this
57 * is refused with advice instead of served short. */
58 int too_many_groups;
59  
60 /* THE EXEMPLAR IDS OF EVERY ROW THAT SURVIVED THE FILTERS, collected only
61 * when the query asked to re-key on them.
62 *
63 * An aggregate CONSUMES its rows: after `| bucket(5m) p99` there are
64 * buckets and no rows at all, so a cross-signal jump reading the result's
65 * rows finds nothing and joins to nothing - which is what the flagship
66 * expression did on its first run, silently and with `ok` true. The ids
67 * are therefore taken where a row passes the filters, before whatever
68 * happens to the row itself.
69 *
70 * `| exemplars` after an aggregate means "the traces behind the points
71 * this pipeline selected", which is the question somebody bucketing to a
72 * p99 is asking. It is not "the trace AT the p99" - that would need the
73 * percentile's own sample to carry an id, and claiming it without that
74 * would be a precise-sounding wrong answer. */
75 po_u64 *ex_hi, *ex_lo;
76 uint32_t nex, cap_ex;
77 int ex_overflow; /* past the cap; the caller refuses */
78 } po_result;
79  
80 /* The same ceiling po_traceset enforces, named once here so the executor can
81 * stop collecting rather than growing without bound. */
82 #define PO_MAX_EXEMPLARS 4096
83  
84 4217 static int po_result_exemplar(po_result *r, po_u64 hi, po_u64 lo) {
85 4217 ▶ if (!hi && !lo) return 1; /* no id: nothing to join to */
Branch: 2 branches
BranchTrueFalseTotal
if (!hi && !lo) return 1; /* no id: nothing to join to */ 7 4210 4217
if (!hi && !lo) return 1; /* no id: nothing to join to */ 7 0 7
86 4210 ▶ if (r->nex >= PO_MAX_EXEMPLARS) { r->ex_overflow = 1; return 1; }
Branch: 1 branch
BranchTrueFalseTotal
if (r->nex >= PO_MAX_EXEMPLARS) { r->ex_overflow = 1; return 1; } 104 4106 4210
87 4106 ▶ if (r->nex == r->cap_ex) {
Branch: 1 branch
BranchTrueFalseTotal
if (r->nex == r->cap_ex) { 12 4094 4106
88 12 ▶ uint32_t want = r->cap_ex ? r->cap_ex * 2 : 64;
Branch: 1 branch
BranchTrueFalseTotal
uint32_t want = r->cap_ex ? r->cap_ex * 2 : 64; 6 6 12
89 12 po_u64 *nh = (po_u64 *)realloc(r->ex_hi, want * sizeof(po_u64));
90 12 po_u64 *nl = (po_u64 *)realloc(r->ex_lo, want * sizeof(po_u64));
91 12 ▶ if (nh) r->ex_hi = nh;
Branch: 1 branch
BranchTrueFalseTotal
if (nh) r->ex_hi = nh; 12 0 12
92 12 ▶ if (nl) r->ex_lo = nl;
Branch: 1 branch
BranchTrueFalseTotal
if (nl) r->ex_lo = nl; 12 0 12
93 12 ▶ if (!nh || !nl) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (!nh || !nl) return 0; 12 0 12
if (!nh || !nl) return 0; 0 12 12
94 12 r->cap_ex = want;
95 }
96 4106 r->ex_hi[r->nex] = hi;
97 4106 r->ex_lo[r->nex] = lo;
98 4106 r->nex++;
99 4106 return 1;
100 }
101  
102 /* The ceiling on distinct groups.
103 *
104 * Two reasons, and the second is the load-bearing one. No chart can show more
105 * than a couple of thousand points, so a result past this is not something
106 * anybody can read - and po_result_group looks its key up by walking every
107 * group it has, so the cost of getting here is quadratic. `bucket(1ns)` over
108 * an hour is three and a half trillion groups, which is not a slow query, it
109 * is a hung worker. */
110 #define PO_MAX_GROUPS 10000
111  
112 1118 static void po_result_init(po_result *r) {
113 1118 memset(r, 0, sizeof(*r));
114 1118 r->exact = 1;
115 1118 }
116  
117 1118 static void po_result_free(po_result *r) {
118 uint32_t i;
119 12755 ▶ for (i = 0; i < r->ng; i++) free(r->g[i].samples);
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < r->ng; i++) free(r->g[i].samples); 11637 1118 12755
120 1118 free(r->ex_hi); free(r->ex_lo);
121 1118 free(r->g); free(r->row);
122 1118 r->g = NULL; r->row = NULL; r->ng = r->nrow = 0;
123 1118 }
124  
125 64467 static po_group *po_result_group(po_result *r, const char *key, size_t len) {
126 uint32_t i;
127 64467 ▶ if (len > sizeof(r->g[0].key)) len = sizeof(r->g[0].key);
Branch: 1 branch
BranchTrueFalseTotal
if (len > sizeof(r->g[0].key)) len = sizeof(r->g[0].key); 0 64467 64467
128 50226202 ▶ for (i = 0; i < r->ng; i++)
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < r->ng; i++) 50214558 11644 50226202
129 50214558 ▶ if (r->g[i].key_len == len &&
Branch: 2 branches
BranchTrueFalseTotal
if (r->g[i].key_len == len && 50163533 51025 50214558
if (r->g[i].key_len == len && 50162330 1203 50163533
130 50163533 ▶ (len == 0 || memcmp(r->g[i].key, key, len) == 0)) return &r->g[i];
Branch: 1 branch
BranchTrueFalseTotal
(len == 0 || memcmp(r->g[i].key, key, len) == 0)) return &r->g[i]; 51620 50110710 50162330
131 11644 ▶ if (r->ng == r->cg) {
Branch: 1 branch
BranchTrueFalseTotal
if (r->ng == r->cg) { 356 11288 11644
132 356 ▶ uint32_t want = r->cg ? r->cg * 2 : 8;
Branch: 1 branch
BranchTrueFalseTotal
uint32_t want = r->cg ? r->cg * 2 : 8; 74 282 356
133 356 po_group *ng = (po_group *)realloc(r->g, want * sizeof(po_group));
134 356 ▶ if (!ng) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!ng) return NULL; 0 356 356
135 356 memset(ng + r->cg, 0, (want - r->cg) * sizeof(po_group));
136 356 r->g = ng; r->cg = want;
137 }
138 11644 ▶ if (len) memcpy(r->g[r->ng].key, key, len);
Branch: 1 branch
BranchTrueFalseTotal
if (len) memcpy(r->g[r->ng].key, key, len); 11629 15 11644
139 11644 r->g[r->ng].key_len = len;
140 11644 return &r->g[r->ng++];
141 }
142  
143 4264 static int po_group_sample(po_group *g, double v) {
144 4264 ▶ if (g->nsamp == g->csamp) {
Branch: 1 branch
BranchTrueFalseTotal
if (g->nsamp == g->csamp) { 444 3820 4264
145 444 ▶ uint32_t want = g->csamp ? g->csamp * 2 : 16;
Branch: 1 branch
BranchTrueFalseTotal
uint32_t want = g->csamp ? g->csamp * 2 : 16; 75 369 444
146 444 double *ns = (double *)realloc(g->samples, want * sizeof(double));
147 444 ▶ if (!ns) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!ns) return 0; 0 444 444
148 444 g->samples = ns; g->csamp = want;
149 }
150 4264 g->samples[g->nsamp++] = v;
151 4264 return 1;
152 }
153  
154 15276 static int po_result_row(po_result *r, const po_row *src) {
155 15276 ▶ if (r->nrow == r->crow) {
Branch: 1 branch
BranchTrueFalseTotal
if (r->nrow == r->crow) { 232 15044 15276
156 232 ▶ uint32_t want = r->crow ? r->crow * 2 : 32;
Branch: 1 branch
BranchTrueFalseTotal
uint32_t want = r->crow ? r->crow * 2 : 32; 91 141 232
157 232 po_row *nr = (po_row *)realloc(r->row, want * sizeof(po_row));
158 232 ▶ if (!nr) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!nr) return 0; 0 232 232
159 232 r->row = nr; r->crow = want;
160 }
161 15276 r->row[r->nrow++] = *src;
162 15276 return 1;
163 }
164  
165 11613 static int po_dcmp(const void *a, const void *b) {
166 11613 double x = *(const double *)a, y = *(const double *)b;
167 11613 ▶ return x < y ? -1 : (x > y ? 1 : 0);
Branch: 1 branch
BranchTrueFalseTotal
return x < y ? -1 : (x > y ? 1 : 0); 11496 117 11613
168 }
169  
170 /* PERCENTILES: EXACT BELOW A THRESHOLD, ESTIMATED ABOVE, AND THE RESULT SAYS
171 * WHICH.
172 *
173 * Sorting a hundred thousand samples to answer a p99 is affordable; sorting a
174 * hundred million is not. Above the threshold the samples are decimated, and
175 * `exact` goes to 0 - because a percentile whose method the reader cannot
176 * know is a number they cannot act on. */
177 #define PO_EXACT_MAX 200000
178  
179 19 static double po_percentile(po_group *g, double q, int *exact) {
180 19 ▶ if (!g->nsamp) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!g->nsamp) return 0; 0 19 19
181 19 ▶ if (g->nsamp > PO_EXACT_MAX && exact) *exact = 0;
Branch: 2 branches
BranchTrueFalseTotal
if (g->nsamp > PO_EXACT_MAX && exact) *exact = 0; 0 19 19
if (g->nsamp > PO_EXACT_MAX && exact) *exact = 0; 0 0 0
182 19 qsort(g->samples, g->nsamp, sizeof(double), po_dcmp);
183 {
184 19 double idx = q * (double)(g->nsamp - 1);
185 19 uint32_t lo = (uint32_t)idx;
186 19 ▶ uint32_t hi = lo + 1 < g->nsamp ? lo + 1 : lo;
Branch: 1 branch
BranchTrueFalseTotal
uint32_t hi = lo + 1 < g->nsamp ? lo + 1 : lo; 19 0 19
187 19 double frac = idx - (double)lo;
188 19 return g->samples[lo] + (g->samples[hi] - g->samples[lo]) * frac;
189 }
190 }
191  
192 #endif /* PO_RESULT_H */
« include/punk_observe/po_limit.h ↑ Summary xs/exec.xs »