| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (s->n >= PO_TRACESET_MAX) { s->overflowed = 1; return 0; } |
0 |
4114 |
4114 |
|
| 56 |
4114 |
▶ | if (s->n == s->cap) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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 */ |