| 1 |
|
| /* po_query.h - the AST, and the column table that validates it. |
| 2 |
|
| * |
| 3 |
|
| * ONE LANGUAGE, THREE SOURCES. A source verb, then stages every signal |
| 4 |
|
| * shares: |
| 5 |
|
| * |
| 6 |
|
| * <source> [selector] | stage | stage | ... |
| 7 |
|
| * |
| 8 |
|
| * Every stage takes a row stream and returns a row stream. `where` filters, |
| 9 |
|
| * `by` groups, `count`/`p95` reduce - ONE implementation each, working on a |
| 10 |
|
| * log because a log line is a row and on a span because a span is a row. |
| 11 |
|
| * |
| 12 |
|
| * The signals differ only in WHICH COLUMNS EXIST, and checking that is this |
| 13 |
|
| * file's job. |
| 14 |
|
| * |
| 15 |
|
| * log | where duration > 5s |
| 16 |
|
| * |
| 17 |
|
| * is a parse error naming the column and the source. It is NOT an empty |
| 18 |
|
| * result - an empty result for a nonsensical query is the worst outcome |
| 19 |
|
| * available, because it looks like an answer. |
| 20 |
|
| */ |
| 21 |
|
| #ifndef PO_QUERY_H |
| 22 |
|
| #define PO_QUERY_H |
| 23 |
|
| |
| 24 |
|
| #include "punk_observe/po_compat.h" |
| 25 |
|
| #include "punk_observe/po_lex.h" |
| 26 |
|
| |
| 27 |
|
| /* sources */ |
| 28 |
|
| #define PO_SRC_METRIC 1 |
| 29 |
|
| #define PO_SRC_LOG 2 |
| 30 |
|
| #define PO_SRC_TRACE 3 |
| 31 |
|
| #define PO_SRC_SPAN 4 /* spans as rows, for span-level aggregation */ |
| 32 |
|
| |
| 33 |
|
| /* stages */ |
| 34 |
|
| #define PO_ST_WHERE 1 |
| 35 |
|
| #define PO_ST_SEARCH 2 |
| 36 |
|
| #define PO_ST_BY 3 |
| 37 |
|
| #define PO_ST_AGG 4 |
| 38 |
|
| #define PO_ST_RATE 5 |
| 39 |
|
| #define PO_ST_TOPN 6 |
| 40 |
|
| #define PO_ST_SLOWEST 7 |
| 41 |
|
| #define PO_ST_LIMIT 8 |
| 42 |
|
| #define PO_ST_SORT 9 |
| 43 |
|
| #define PO_ST_EXEMPLARS 10 |
| 44 |
|
| #define PO_ST_TRACES 11 |
| 45 |
|
| #define PO_ST_LOGS 12 |
| 46 |
|
| #define PO_ST_SPANS 13 |
| 47 |
|
| #define PO_ST_BUCKET 14 |
| 48 |
|
| |
| 49 |
|
| /* aggregates */ |
| 50 |
|
| #define PO_AGG_COUNT 1 |
| 51 |
|
| #define PO_AGG_SUM 2 |
| 52 |
|
| #define PO_AGG_AVG 3 |
| 53 |
|
| #define PO_AGG_MIN 4 |
| 54 |
|
| #define PO_AGG_MAX 5 |
| 55 |
|
| #define PO_AGG_P50 6 |
| 56 |
|
| #define PO_AGG_P90 7 |
| 57 |
|
| #define PO_AGG_P95 8 |
| 58 |
|
| #define PO_AGG_P99 9 |
| 59 |
|
| #define PO_AGG_DISTINCT 10 |
| 60 |
|
| |
| 61 |
|
| /* value kinds in a predicate */ |
| 62 |
|
| #define PO_V_STRING 1 |
| 63 |
|
| #define PO_V_NUMBER 2 |
| 64 |
|
| #define PO_V_DURATION 3 |
| 65 |
|
| #define PO_V_SEVERITY 4 |
| 66 |
|
| /* `null` - the absence test. A comparison against an absent field is false |
| 67 |
|
| * in BOTH directions, which is right and leaves no way to ask "does this row |
| 68 |
|
| * carry the attribute at all"; grouping then buries the answer in a (none) |
| 69 |
|
| * bucket. `x != null` is that question. Only = and != mean anything against |
| 70 |
|
| * absence, and every other consumer of a value kind ignores this one, which |
| 71 |
|
| * is what keeps the pushdown honest: there is no value here to prune on. */ |
| 72 |
|
| #define PO_V_NULL 5 |
| 73 |
|
| |
| 74 |
|
| /* expression node kinds */ |
| 75 |
|
| #define PO_E_AND 1 |
| 76 |
|
| #define PO_E_OR 2 |
| 77 |
|
| #define PO_E_NOT 3 |
| 78 |
|
| #define PO_E_CMP 4 |
| 79 |
|
| |
| 80 |
|
| typedef struct po_expr { |
| 81 |
|
| int kind; |
| 82 |
|
| struct po_expr *a, *b; /* AND/OR: both; NOT: a */ |
| 83 |
|
| /* CMP: */ |
| 84 |
|
| const char *field; size_t field_len; |
| 85 |
|
| int op; |
| 86 |
|
| int vkind; |
| 87 |
|
| const char *sval; size_t sval_len; |
| 88 |
|
| double nval; |
| 89 |
|
| po_u64 uval; /* duration ns, severity, or exact integer */ |
| 90 |
|
| } po_expr; |
| 91 |
|
| |
| 92 |
|
| typedef struct po_stage { |
| 93 |
|
| int kind; |
| 94 |
|
| struct po_stage *next; |
| 95 |
|
| |
| 96 |
|
| po_expr *expr; /* WHERE */ |
| 97 |
|
| const char *str; size_t str_len; /* SEARCH */ |
| 98 |
|
| int agg; /* AGG, TOPN, BUCKET, RATE */ |
| 99 |
|
| po_u64 dur; /* BUCKET and RATE window, ns */ |
| 100 |
|
| po_u64 num; /* LIMIT, TOPN, SLOWEST */ |
| 101 |
|
| const char *fields[8]; size_t field_lens[8]; int nfields; /* BY, SORT */ |
| 102 |
|
| int desc; /* SORT */ |
| 103 |
|
| } po_stage; |
| 104 |
|
| |
| 105 |
|
| /* A CHUNKED bump allocator, and the chunking is the point. |
| 106 |
|
| * |
| 107 |
|
| * The obvious move is to allocate nodes out of po_arena, which is what the |
| 108 |
|
| * first draft did. It is WRONG: po_arena reallocs as it grows, so every node |
| 109 |
|
| * handed out before a growth dangles the moment the tree gets big enough - |
| 110 |
|
| * and "big enough" means a real query rather than a test one. Exactly the |
| 111 |
|
| * bug phase 3 hit with JSON attributes pointing into a growing arena. |
| 112 |
|
| * |
| 113 |
|
| * Chunks are allocated and never moved. The whole tree still frees in one |
| 114 |
|
| * call, which is the property the arena was wanted for. */ |
| 115 |
|
| #define PO_BUMP_CHUNK 8192 |
| 116 |
|
| |
| 117 |
|
| typedef struct po_chunk { |
| 118 |
|
| struct po_chunk *next; |
| 119 |
|
| size_t used, cap; |
| 120 |
|
| char mem[1]; /* over-allocated */ |
| 121 |
|
| } po_chunk; |
| 122 |
|
| |
| 123 |
|
| typedef struct { po_chunk *head; } po_bump; |
| 124 |
|
| |
| 125 |
159445 |
| static void *po_bump_alloc(po_bump *b, size_t n) { |
| 126 |
159445 |
| n = (n + 7) & ~(size_t)7; /* 8-byte aligned */ |
| 127 |
159445 |
▶ | if (!b->head || b->head->used + n > b->head->cap) { |
Branch: 2 branches
| Branch | True | False | Total |
| if (!b->head || b->head->used + n > b->head->cap) { |
142617 |
16828 |
159445 |
| if (!b->head || b->head->used + n > b->head->cap) { |
0 |
142617 |
142617 |
|
| 128 |
16828 |
| size_t cap = n > PO_BUMP_CHUNK ? n : PO_BUMP_CHUNK; |
| 129 |
16828 |
| po_chunk *c = (po_chunk *)malloc(sizeof(po_chunk) + cap); |
| 130 |
16828 |
▶ | if (!c) return NULL; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!c) return NULL; |
0 |
16828 |
16828 |
|
| 131 |
16828 |
| c->next = b->head; |
| 132 |
16828 |
| c->used = 0; |
| 133 |
16828 |
| c->cap = cap; |
| 134 |
16828 |
| b->head = c; |
| 135 |
|
| } |
| 136 |
|
| { |
| 137 |
159445 |
| void *p = b->head->mem + b->head->used; |
| 138 |
159445 |
| b->head->used += n; |
| 139 |
159445 |
| memset(p, 0, n); |
| 140 |
159445 |
| return p; |
| 141 |
|
| } |
| 142 |
|
| } |
| 143 |
|
| |
| 144 |
16917 |
| static void po_bump_free(po_bump *b) { |
| 145 |
16917 |
| po_chunk *c = b->head; |
| 146 |
33732 |
▶ | while (c) { po_chunk *n = c->next; free(c); c = n; } |
Branch: 1 branch
| Branch | True | False | Total |
| while (c) { po_chunk *n = c->next; free(c); c = n; } |
16815 |
16917 |
33732 |
|
| 147 |
16917 |
| b->head = NULL; |
| 148 |
16917 |
| } |
| 149 |
|
| |
| 150 |
|
| typedef struct { |
| 151 |
|
| int source; |
| 152 |
|
| const char *name; size_t name_len; /* metric name */ |
| 153 |
|
| po_expr *selector; /* {a="b"} sugar, folded to a where */ |
| 154 |
|
| po_stage *stages; |
| 155 |
|
| /* `| viz bar` - HOW to draw the answer, which is why it is a field here |
| 156 |
|
| * and not a stage in the list above: every stage transforms rows, and a |
| 157 |
|
| * presentation hint transforms nothing. A stage kind the planner had no |
| 158 |
|
| * case for is exactly how `top N` shipped doing nothing. */ |
| 159 |
|
| const char *viz; size_t viz_len; |
| 160 |
|
| /* everything above is allocated in this bump and freed with it */ |
| 161 |
|
| po_bump bump; |
| 162 |
|
| char err[256]; |
| 163 |
|
| size_t err_off; |
| 164 |
|
| int failed; |
| 165 |
|
| } po_query; |
| 166 |
|
| |
| 167 |
16917 |
| static void po_query_free(po_query *q) { po_bump_free(&q->bump); } |
| 168 |
|
| |
| 169 |
|
| /* ---- the column table ------------------------------------------------------ |
| 170 |
|
| * |
| 171 |
|
| * Which columns exist on which source. This is the table from the plan, in |
| 172 |
|
| * code, and it is what turns a nonsensical query into a named error. |
| 173 |
|
| */ |
| 174 |
|
| #define PO_C_ANY 0x0F /* t, labels, attributes: every source */ |
| 175 |
|
| #define PO_C_METRIC 0x01 |
| 176 |
|
| #define PO_C_LOG 0x02 |
| 177 |
|
| #define PO_C_TRACE 0x04 |
| 178 |
|
| #define PO_C_SPAN 0x08 |
| 179 |
|
| |
| 180 |
|
| typedef struct { const char *name; int sources; } po_column; |
| 181 |
|
| |
| 182 |
|
| static const po_column PO_COLUMNS[] = { |
| 183 |
|
| { "t", PO_C_ANY }, |
| 184 |
|
| { "time", PO_C_ANY }, |
| 185 |
|
| { "service", PO_C_ANY }, |
| 186 |
|
| { "value", PO_C_METRIC }, |
| 187 |
|
| { "body", PO_C_LOG }, |
| 188 |
|
| { "severity", PO_C_LOG }, |
| 189 |
|
| { "duration", PO_C_TRACE | PO_C_SPAN }, |
| 190 |
|
| { "name", PO_C_TRACE | PO_C_SPAN }, |
| 191 |
|
| { "status", PO_C_TRACE | PO_C_SPAN }, |
| 192 |
|
| { "kind", PO_C_TRACE | PO_C_SPAN }, |
| 193 |
|
| { "trace_id", PO_C_LOG | PO_C_TRACE | PO_C_SPAN }, |
| 194 |
|
| { "span_id", PO_C_LOG | PO_C_TRACE | PO_C_SPAN }, |
| 195 |
|
| { NULL, 0 } |
| 196 |
|
| }; |
| 197 |
|
| |
| 198 |
15314 |
| static int po_src_bit(int src) { |
| 199 |
15314 |
| switch (src) { |
| 200 |
10013 |
| case PO_SRC_METRIC: return PO_C_METRIC; |
| 201 |
5218 |
| case PO_SRC_LOG: return PO_C_LOG; |
| 202 |
21 |
| case PO_SRC_TRACE: return PO_C_TRACE; |
| 203 |
62 |
| case PO_SRC_SPAN: return PO_C_SPAN; |
| 204 |
0 |
| default: return 0; |
| 205 |
|
| } |
| 206 |
|
| } |
| 207 |
|
| |
| 208 |
5183 |
| static const char *po_src_name(int src) { |
| 209 |
5183 |
| switch (src) { |
| 210 |
17 |
| case PO_SRC_METRIC: return "metric"; |
| 211 |
5084 |
| case PO_SRC_LOG: return "log"; |
| 212 |
20 |
| case PO_SRC_TRACE: return "trace"; |
| 213 |
62 |
| case PO_SRC_SPAN: return "spans"; |
| 214 |
0 |
| default: return "?"; |
| 215 |
|
| } |
| 216 |
|
| } |
| 217 |
|
| |
| 218 |
|
| /* Returns 1 if the column exists on this source, 0 if it exists on ANOTHER |
| 219 |
|
| * source (so the error can say which), -1 if it is not a known column at all. |
| 220 |
|
| * |
| 221 |
|
| * An unknown name is NOT an error: it is an attribute. Attributes are |
| 222 |
|
| * open-ended by nature, so only the RESERVED column names are checked. */ |
| 223 |
25389 |
| static int po_column_ok(const char *f, size_t len, int src, int *elsewhere) { |
| 224 |
|
| int i; |
| 225 |
25389 |
▶ | if (elsewhere) *elsewhere = 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (elsewhere) *elsewhere = 0; |
25389 |
0 |
25389 |
|
| 226 |
197531 |
▶ | for (i = 0; PO_COLUMNS[i].name; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; PO_COLUMNS[i].name; i++) { |
187456 |
10075 |
197531 |
|
| 227 |
187456 |
| size_t n = strlen(PO_COLUMNS[i].name); |
| 228 |
187456 |
▶ | if (n == len && memcmp(PO_COLUMNS[i].name, f, len) == 0) { |
Branch: 2 branches
| Branch | True | False | Total |
| if (n == len && memcmp(PO_COLUMNS[i].name, f, len) == 0) { |
20459 |
166997 |
187456 |
| if (n == len && memcmp(PO_COLUMNS[i].name, f, len) == 0) { |
15314 |
5145 |
20459 |
|
| 229 |
15314 |
▶ | if (PO_COLUMNS[i].sources & po_src_bit(src)) return 1; |
Branch: 1 branch
| Branch | True | False | Total |
| if (PO_COLUMNS[i].sources & po_src_bit(src)) return 1; |
10304 |
5010 |
15314 |
|
| 230 |
5010 |
▶ | if (elsewhere) *elsewhere = PO_COLUMNS[i].sources; |
Branch: 1 branch
| Branch | True | False | Total |
| if (elsewhere) *elsewhere = PO_COLUMNS[i].sources; |
5010 |
0 |
5010 |
|
| 231 |
5010 |
| return 0; |
| 232 |
|
| } |
| 233 |
|
| } |
| 234 |
10075 |
| return -1; /* an attribute; fine anywhere */ |
| 235 |
|
| } |
| 236 |
|
| |
| 237 |
|
| /* OTLP severity names, on the 24-point scale. `severity >= error` is a |
| 238 |
|
| * NUMERIC comparison, not a string match on a level name. */ |
| 239 |
246 |
| static int po_severity_value(const char *p, size_t len, po_u64 *out) { |
| 240 |
246 |
| struct { const char *n; int v; } S[] = { |
| 241 |
|
| { "trace", 1 }, { "debug", 5 }, { "info", 9 }, |
| 242 |
|
| { "warn", 13 }, { "warning", 13 }, |
| 243 |
|
| { "error", 17 }, { "fatal", 21 }, { NULL, 0 } |
| 244 |
|
| }; |
| 245 |
|
| int i; |
| 246 |
1102 |
▶ | for (i = 0; S[i].n; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; S[i].n; i++) { |
1099 |
3 |
1102 |
|
| 247 |
1099 |
| size_t n = strlen(S[i].n); |
| 248 |
1099 |
▶ | if (n == len) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (n == len) { |
539 |
560 |
1099 |
|
| 249 |
539 |
| size_t k; int eq = 1; |
| 250 |
1753 |
▶ | for (k = 0; k < len; k++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (k = 0; k < len; k++) { |
1510 |
243 |
1753 |
|
| 251 |
1510 |
| char a = p[k], b = S[i].n[k]; |
| 252 |
1510 |
▶ | if (a >= 'A' && a <= 'Z') a = (char)(a - 'A' + 'a'); |
Branch: 2 branches
| Branch | True | False | Total |
| if (a >= 'A' && a <= 'Z') a = (char)(a - 'A' + 'a'); |
1510 |
0 |
1510 |
| if (a >= 'A' && a <= 'Z') a = (char)(a - 'A' + 'a'); |
7 |
1503 |
1510 |
|
| 253 |
1510 |
▶ | if (a != b) { eq = 0; break; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (a != b) { eq = 0; break; } |
296 |
1214 |
1510 |
|
| 254 |
|
| } |
| 255 |
539 |
▶ | if (eq) { *out = (po_u64)S[i].v; return 1; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (eq) { *out = (po_u64)S[i].v; return 1; } |
243 |
296 |
539 |
|
| 256 |
|
| } |
| 257 |
|
| } |
| 258 |
3 |
| return 0; |
| 259 |
|
| } |
| 260 |
|
| |
| 261 |
|
| /* OTLP span status names. `status = error` is a NUMERIC comparison too. |
| 262 |
|
| * |
| 263 |
|
| * The scale is tiny and closed - unset, ok, error - and the names are what |
| 264 |
|
| * the screens print, so they are what a person types. Resolved at parse time |
| 265 |
|
| * to the number the row holds, exactly as the severity names are, and for the |
| 266 |
|
| * same reason: string-comparing a numeric column would make `status > "3"` |
| 267 |
|
| * mean something absurd, and would leave a typo silently matching nothing. |
| 268 |
|
| * |
| 269 |
|
| * `error` is BOTH a severity name and a status name. Which one a bare word |
| 270 |
|
| * means is decided by the column it is compared against, which the parser |
| 271 |
|
| * already knows by the time it reads the value. */ |
| 272 |
8 |
| static int po_status_value(const char *p, size_t len, po_u64 *out) { |
| 273 |
8 |
| struct { const char *n; int v; } S[] = { |
| 274 |
|
| { "unset", 0 }, { "ok", 1 }, { "error", 2 }, { NULL, 0 } |
| 275 |
|
| }; |
| 276 |
|
| int i; |
| 277 |
14 |
▶ | for (i = 0; S[i].n; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; S[i].n; i++) { |
14 |
0 |
14 |
|
| 278 |
14 |
| size_t n = strlen(S[i].n); |
| 279 |
14 |
▶ | if (n == len) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (n == len) { |
10 |
4 |
14 |
|
| 280 |
10 |
| size_t k; int eq = 1; |
| 281 |
44 |
▶ | for (k = 0; k < len; k++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (k = 0; k < len; k++) { |
36 |
8 |
44 |
|
| 282 |
36 |
| char a = p[k], b = S[i].n[k]; |
| 283 |
36 |
▶ | if (a >= 'A' && a <= 'Z') a = (char)(a - 'A' + 'a'); |
Branch: 2 branches
| Branch | True | False | Total |
| if (a >= 'A' && a <= 'Z') a = (char)(a - 'A' + 'a'); |
36 |
0 |
36 |
| if (a >= 'A' && a <= 'Z') a = (char)(a - 'A' + 'a'); |
0 |
36 |
36 |
|
| 284 |
36 |
▶ | if (a != b) { eq = 0; break; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (a != b) { eq = 0; break; } |
2 |
34 |
36 |
|
| 285 |
|
| } |
| 286 |
10 |
▶ | if (eq) { *out = (po_u64)S[i].v; return 1; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (eq) { *out = (po_u64)S[i].v; return 1; } |
8 |
2 |
10 |
|
| 287 |
|
| } |
| 288 |
|
| } |
| 289 |
0 |
| return 0; |
| 290 |
|
| } |
| 291 |
|
| |
| 292 |
|
| #endif /* PO_QUERY_H */ |