include/punk_observe/po_traceset.h

filter: Statementstmt 95.1% 39 / 41 Branchbran 55.5% 20 / 36 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 76.6% 59 / 77 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« include/punk_observe/po_otlp_in.h ↑ Summary xs/retain.xs »
1 /* po_traceset.h - a set of trace ids, and the join key it makes.
2 *
3 * THE CROSS-SIGNAL PIPELINE IS A JOIN, and this is its key. `metric ... |
4 * exemplars | traces | logs` runs the metric side, collects the trace ids the
5 * surviving points carried, and reads the log side filtered to that SET. The
6 * single-id filter has always existed - it is how the trace page shows a
7 * trace's own log lines - and this is the same operation for more than one.
8 *
9 * SORTED ARRAY, BINARY SEARCH, NOT A HASH. The set is built once and then
10 * tested against every row of a scan, which is the ratio a hash is the wrong
11 * shape for: the build is one qsort, the test is a handful of comparisons
12 * with no pointer chasing, and the whole thing is contiguous in a scan that
13 * is already memory-bound. A thousand ids is ten comparisons per row.
14 *
15 * The set is BOUNDED, and the bound is a refusal rather than a degradation -
16 * a join whose left side produced more traces than this cannot be answered by
17 * scanning, and answering it approximately would be the silent-wrong-rows
18 * failure the whole query layer refuses elsewhere.
19 */
20 #ifndef PO_TRACESET_H
21 #define PO_TRACESET_H
22  
23 #include "punk_observe/po_compat.h"
24  
25 /* Above this, the join refuses and says so. Sized from what a join can
26 * usefully return rather than from what fits: a person reading the logs of
27 * four thousand traces is not reading anything, and the query that produced
28 * them wanted an aggregate. */
29 #define PO_TRACESET_MAX 4096
30  
31 typedef struct { po_u64 hi, lo; } po_traceid;
32  
33 typedef struct {
34 po_traceid *id;
35 uint32_t n, cap;
36 int overflowed; /* hit PO_TRACESET_MAX; the caller refuses */
37 } po_traceset;
38  
39 14 static int po_traceset_init(po_traceset *s) {
40 14 memset(s, 0, sizeof(*s));
41 14 s->cap = 64;
42 14 s->id = (po_traceid *)malloc(s->cap * sizeof(po_traceid));
43 14 return s->id != NULL;
44 }
45  
46 14 static void po_traceset_free(po_traceset *s) {
47 14 free(s->id); s->id = NULL; s->n = s->cap = 0;
48 14 }
49  
50 /* Appended, not inserted: duplicates are expected - every point of a spiky
51 * series may carry the same exemplar - and are removed once by the sort
52 * rather than searched for on every add. */
53 4114 static int po_traceset_add(po_traceset *s, po_u64 hi, po_u64 lo) {
54 4114 ▶ if (!po_trace_id_valid(hi, lo)) return 1; /* nothing to join to */
Branch: 2 branches
BranchTrueFalseTotal
if (!po_trace_id_valid(hi, lo)) return 1; /* nothing to join to */ 0 4114 4114
if (!po_trace_id_valid(hi, lo)) return 1; /* nothing to join to */ 0 0 0
55 4114 ▶ if (s->n >= PO_TRACESET_MAX) { s->overflowed = 1; return 0; }
Branch: 1 branch
BranchTrueFalseTotal
if (s->n >= PO_TRACESET_MAX) { s->overflowed = 1; return 0; } 0 4114 4114
56 4114 ▶ if (s->n == s->cap) {
Branch: 1 branch
BranchTrueFalseTotal
if (s->n == s->cap) { 6 4108 4114
57 6 uint32_t want = s->cap * 2;
58 6 po_traceid *ni = (po_traceid *)realloc(s->id, want * sizeof(po_traceid));
59 6 ▶ if (!ni) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!ni) return 0; 0 6 6
60 6 s->id = ni; s->cap = want;
61 }
62 4114 s->id[s->n].hi = hi;
63 4114 s->id[s->n].lo = lo;
64 4114 s->n++;
65 4114 return 1;
66 }
67  
68 18 static int po_traceid_cmp(const void *a, const void *b) {
69 18 const po_traceid *x = (const po_traceid *)a, *y = (const po_traceid *)b;
70 18 ▶ if (x->hi != y->hi) return x->hi < y->hi ? -1 : 1;
Branch: 2 branches
BranchTrueFalseTotal
if (x->hi != y->hi) return x->hi < y->hi ? -1 : 1; 18 0 18
if (x->hi != y->hi) return x->hi < y->hi ? -1 : 1; 0 18 18
71 0 ▶ if (x->lo != y->lo) return x->lo < y->lo ? -1 : 1;
Branch: 2 branches
BranchTrueFalseTotal
if (x->lo != y->lo) return x->lo < y->lo ? -1 : 1; 0 0 0
if (x->lo != y->lo) return x->lo < y->lo ? -1 : 1; 0 0 0
72 0 return 0;
73 }
74  
75 /* Sort and unique, in place. Called once, after the whole left side is in. */
76 13 static void po_traceset_seal(po_traceset *s) {
77 uint32_t i, k;
78 13 ▶ if (s->n < 2) return;
Branch: 1 branch
BranchTrueFalseTotal
if (s->n < 2) return; 4 9 13
79 9 qsort(s->id, (size_t)s->n, sizeof(po_traceid), po_traceid_cmp);
80 18 ▶ for (i = 1, k = 1; i < s->n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 1, k = 1; i < s->n; i++) { 9 9 18
81 9 ▶ if (po_traceid_cmp(&s->id[i], &s->id[k - 1]) == 0) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (po_traceid_cmp(&s->id[i], &s->id[k - 1]) == 0) continue; 0 9 9
82 9 s->id[k++] = s->id[i];
83 }
84 9 s->n = k;
85 }
86  
87 12 static int po_traceset_has(const po_traceset *s, po_u64 hi, po_u64 lo) {
88 12 uint32_t lo_i = 0, hi_i = s->n;
89 20 ▶ while (lo_i < hi_i) {
Branch: 1 branch
BranchTrueFalseTotal
while (lo_i < hi_i) { 16 4 20
90 16 uint32_t mid = lo_i + (hi_i - lo_i) / 2;
91 16 const po_traceid *m = &s->id[mid];
92 16 ▶ if (m->hi == hi && m->lo == lo) return 1;
Branch: 2 branches
BranchTrueFalseTotal
if (m->hi == hi && m->lo == lo) return 1; 8 8 16
if (m->hi == hi && m->lo == lo) return 1; 8 0 8
93 8 ▶ if (m->hi < hi || (m->hi == hi && m->lo < lo)) lo_i = mid + 1;
Branch: 3 branches
BranchTrueFalseTotal
if (m->hi < hi || (m->hi == hi && m->lo < lo)) lo_i = mid + 1; 4 4 8
if (m->hi < hi || (m->hi == hi && m->lo < lo)) lo_i = mid + 1; 0 4 4
if (m->hi < hi || (m->hi == hi && m->lo < lo)) lo_i = mid + 1; 0 0 0
94 4 else hi_i = mid;
95 }
96 4 return 0;
97 }
98  
99 #endif /* PO_TRACESET_H */
« include/punk_observe/po_otlp_in.h ↑ Summary xs/retain.xs »