| 1 |
|
| /* po_tattr.h - trace summaries, duration search, and segment pruning. |
| 2 |
|
| * |
| 3 |
|
| * "Find traces slower than 500ms with a 5xx" must not decompress spans to |
| 4 |
|
| * answer. Three structures, and the cheapest one runs first. |
| 5 |
|
| * |
| 6 |
|
| * 1. THE SEGMENT FOOTER. Per-segment min and max duration and whether any |
| 7 |
|
| * error span is present. A segment holding no error span is skipped for an |
| 8 |
|
| * error query without opening its index at all. |
| 9 |
|
| * |
| 10 |
|
| * 2. THE DURATION ORDINAL ARRAY. Trace summaries sorted BY DURATION, so |
| 11 |
|
| * `duration > 500ms` is a binary search plus a contiguous range rather |
| 12 |
|
| * than a scan. This single index is what makes "slow traces in the last |
| 13 |
|
| * hour" instant, and that is the question people actually come with. |
| 14 |
|
| * |
| 15 |
|
| * 3. THE SUMMARY ROW ITSELF, 48 bytes. A trace SEARCH never opens span data: |
| 16 |
|
| * the result list, the duration scatter and the service map are all |
| 17 |
|
| * computed from these rows. |
| 18 |
|
| */ |
| 19 |
|
| #ifndef PO_TATTR_H |
| 20 |
|
| #define PO_TATTR_H |
| 21 |
|
| |
| 22 |
|
| #include "punk_observe/po_compat.h" |
| 23 |
|
| #include "punk_observe/po_span.h" |
| 24 |
|
| |
| 25 |
|
| typedef struct { |
| 26 |
|
| po_u64 trace_hi, trace_lo; |
| 27 |
|
| po_u64 start_ns; |
| 28 |
|
| po_u64 dur_ns; /* the ROOT's duration: the request's latency */ |
| 29 |
|
| uint32_t root_name_sym; |
| 30 |
|
| uint32_t root_service_sym; |
| 31 |
|
| uint32_t spans; |
| 32 |
|
| uint32_t errors; |
| 33 |
|
| } po_tsummary; |
| 34 |
|
| |
| 35 |
|
| typedef struct { |
| 36 |
|
| po_tsummary *t; |
| 37 |
|
| uint32_t n, cap; |
| 38 |
|
| uint32_t *by_dur; /* ordinals into t, sorted by duration */ |
| 39 |
|
| } po_tsum_set; |
| 40 |
|
| |
| 41 |
81 |
| static int po_tsum_init(po_tsum_set *s) { |
| 42 |
81 |
| memset(s, 0, sizeof(*s)); |
| 43 |
81 |
| s->cap = 64; |
| 44 |
81 |
| s->t = (po_tsummary *)malloc(s->cap * sizeof(po_tsummary)); |
| 45 |
81 |
| return s->t != NULL; |
| 46 |
|
| } |
| 47 |
|
| |
| 48 |
81 |
| static void po_tsum_free(po_tsum_set *s) { |
| 49 |
81 |
| free(s->t); free(s->by_dur); |
| 50 |
81 |
| s->t = NULL; s->by_dur = NULL; s->n = s->cap = 0; |
| 51 |
81 |
| } |
| 52 |
|
| |
| 53 |
4304 |
| static int po_tsum_add(po_tsum_set *s, const po_tsummary *src) { |
| 54 |
4304 |
▶ | if (s->n == s->cap) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (s->n == s->cap) { |
29 |
4275 |
4304 |
|
| 55 |
29 |
| uint32_t want = s->cap * 2; |
| 56 |
29 |
| po_tsummary *nt = (po_tsummary *)realloc(s->t, want * sizeof(po_tsummary)); |
| 57 |
29 |
▶ | if (!nt) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!nt) return 0; |
0 |
29 |
29 |
|
| 58 |
29 |
| s->t = nt; s->cap = want; |
| 59 |
|
| } |
| 60 |
4304 |
| s->t[s->n++] = *src; |
| 61 |
4304 |
| return 1; |
| 62 |
|
| } |
| 63 |
|
| |
| 64 |
|
| /* Summarise a segment's spans into one row per trace. |
| 65 |
|
| * |
| 66 |
|
| * The root's duration is the trace's duration, because that is the request's |
| 67 |
|
| * latency. Using the MAX span duration instead would report an async |
| 68 |
|
| * background span as the request time, which is a plausible number and the |
| 69 |
|
| * wrong one. */ |
| 70 |
81 |
| static int po_tsum_build(po_tsum_set *s, const po_span *sp, uint32_t n) { |
| 71 |
81 |
| uint32_t i = 0; |
| 72 |
4385 |
▶ | while (i < n) { |
Branch: 1 branch
| Branch | True | False | Total |
| while (i < n) { |
4304 |
81 |
4385 |
|
| 73 |
4304 |
| uint32_t j = i + 1, k; |
| 74 |
|
| po_tsummary sum; |
| 75 |
|
| po_tree tree; |
| 76 |
|
| |
| 77 |
14271 |
▶ | while (j < n && sp[j].trace_hi == sp[i].trace_hi |
Branch: 1 branch
| Branch | True | False | Total |
| while (j < n && sp[j].trace_hi == sp[i].trace_hi |
9478 |
489 |
9967 |
|
| 78 |
13782 |
▶ | && sp[j].trace_lo == sp[i].trace_lo) j++; |
Branch: 2 branches
| Branch | True | False | Total |
| && sp[j].trace_lo == sp[i].trace_lo) j++; |
9967 |
80 |
10047 |
| && sp[j].trace_lo == sp[i].trace_lo) j++; |
5743 |
3735 |
9478 |
|
| 79 |
|
| |
| 80 |
4304 |
| memset(&sum, 0, sizeof(sum)); |
| 81 |
4304 |
| sum.trace_hi = sp[i].trace_hi; |
| 82 |
4304 |
| sum.trace_lo = sp[i].trace_lo; |
| 83 |
4304 |
| sum.start_ns = sp[i].start_ns; /* sorted by start within a trace */ |
| 84 |
4304 |
| sum.spans = j - i; |
| 85 |
|
| |
| 86 |
14351 |
▶ | for (k = i; k < j; k++) if (po_span_is_error(&sp[k])) sum.errors++; |
Branch: 2 branches
| Branch | True | False | Total |
| for (k = i; k < j; k++) if (po_span_is_error(&sp[k])) sum.errors++; |
46 |
10001 |
10047 |
| for (k = i; k < j; k++) if (po_span_is_error(&sp[k])) sum.errors++; |
10047 |
4304 |
14351 |
|
| 87 |
|
| |
| 88 |
|
| /* The root is found by assembling the trace, not by trusting |
| 89 |
|
| * parent_span_id == 0 on any single span. */ |
| 90 |
4304 |
▶ | if (po_tree_build(&tree, sp + i, j - i)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (po_tree_build(&tree, sp + i, j - i)) { |
4304 |
0 |
4304 |
|
| 91 |
|
| uint32_t r; |
| 92 |
4306 |
▶ | for (r = 0; r < tree.n; r++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (r = 0; r < tree.n; r++) { |
4305 |
1 |
4306 |
|
| 93 |
4305 |
▶ | if (tree.depth[r] == 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (tree.depth[r] == 0) { |
4303 |
2 |
4305 |
|
| 94 |
4303 |
| sum.dur_ns = sp[i + r].dur_ns; |
| 95 |
4303 |
| sum.root_name_sym = sp[i + r].name_sym; |
| 96 |
4303 |
| sum.root_service_sym = sp[i + r].service_sym; |
| 97 |
4303 |
| break; |
| 98 |
|
| } |
| 99 |
|
| } |
| 100 |
4304 |
| po_tree_free(&tree); |
| 101 |
|
| } |
| 102 |
4304 |
▶ | if (!po_tsum_add(s, &sum)) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!po_tsum_add(s, &sum)) return 0; |
0 |
4304 |
4304 |
|
| 103 |
4304 |
| i = j; |
| 104 |
|
| } |
| 105 |
81 |
| return 1; |
| 106 |
|
| } |
| 107 |
|
| |
| 108 |
|
| /* Build the by-duration ordinal array. Sorting ORDINALS rather than the rows |
| 109 |
|
| * keeps the summary array in trace order for everything else. */ |
| 110 |
|
| static const po_tsummary *po_dur_base; /* qsort has no user pointer in C89 */ |
| 111 |
|
| |
| 112 |
5383 |
| static int po_dur_ord_cmp(const void *va, const void *vb) { |
| 113 |
5383 |
| uint32_t a = *(const uint32_t *)va, b = *(const uint32_t *)vb; |
| 114 |
5383 |
| po_u64 da = po_dur_base[a].dur_ns, db = po_dur_base[b].dur_ns; |
| 115 |
5383 |
▶ | if (da != db) return da < db ? -1 : 1; |
Branch: 2 branches
| Branch | True | False | Total |
| if (da != db) return da < db ? -1 : 1; |
3174 |
2209 |
5383 |
| if (da != db) return da < db ? -1 : 1; |
3174 |
0 |
3174 |
|
| 116 |
|
| /* Total order, or a top-N is non-deterministic and the same query gives |
| 117 |
|
| * different answers on refresh. */ |
| 118 |
2209 |
▶ | if (po_dur_base[a].trace_hi != po_dur_base[b].trace_hi) |
Branch: 1 branch
| Branch | True | False | Total |
| if (po_dur_base[a].trace_hi != po_dur_base[b].trace_hi) |
997 |
1212 |
2209 |
|
| 119 |
997 |
▶ | return po_dur_base[a].trace_hi < po_dur_base[b].trace_hi ? -1 : 1; |
Branch: 1 branch
| Branch | True | False | Total |
| return po_dur_base[a].trace_hi < po_dur_base[b].trace_hi ? -1 : 1; |
997 |
0 |
997 |
|
| 120 |
1212 |
▶ | if (po_dur_base[a].trace_lo != po_dur_base[b].trace_lo) |
Branch: 1 branch
| Branch | True | False | Total |
| if (po_dur_base[a].trace_lo != po_dur_base[b].trace_lo) |
1212 |
0 |
1212 |
|
| 121 |
1212 |
▶ | return po_dur_base[a].trace_lo < po_dur_base[b].trace_lo ? -1 : 1; |
Branch: 1 branch
| Branch | True | False | Total |
| return po_dur_base[a].trace_lo < po_dur_base[b].trace_lo ? -1 : 1; |
1212 |
0 |
1212 |
|
| 122 |
0 |
| return 0; |
| 123 |
|
| } |
| 124 |
|
| |
| 125 |
55 |
| static int po_tsum_index(po_tsum_set *s) { |
| 126 |
|
| uint32_t i; |
| 127 |
55 |
| free(s->by_dur); |
| 128 |
55 |
▶ | s->by_dur = (uint32_t *)malloc((s->n ? s->n : 1) * sizeof(uint32_t)); |
Branch: 1 branch
| Branch | True | False | Total |
| s->by_dur = (uint32_t *)malloc((s->n ? s->n : 1) * sizeof(uint32_t)); |
54 |
1 |
55 |
|
| 129 |
55 |
▶ | if (!s->by_dur) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!s->by_dur) return 0; |
0 |
55 |
55 |
|
| 130 |
1733 |
▶ | for (i = 0; i < s->n; i++) s->by_dur[i] = i; |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < s->n; i++) s->by_dur[i] = i; |
1678 |
55 |
1733 |
|
| 131 |
55 |
| po_dur_base = s->t; |
| 132 |
55 |
▶ | if (s->n > 1) qsort(s->by_dur, s->n, sizeof(uint32_t), po_dur_ord_cmp); |
Branch: 1 branch
| Branch | True | False | Total |
| if (s->n > 1) qsort(s->by_dur, s->n, sizeof(uint32_t), po_dur_ord_cmp); |
38 |
17 |
55 |
|
| 133 |
55 |
| return 1; |
| 134 |
|
| } |
| 135 |
|
| |
| 136 |
|
| /* First ordinal whose duration is >= want. Binary search over the ordinal |
| 137 |
|
| * array; the answer is a contiguous range [lo, n) of everything slower. */ |
| 138 |
3 |
| static uint32_t po_tsum_lower_bound(const po_tsum_set *s, po_u64 want) { |
| 139 |
3 |
| uint32_t lo = 0, hi = s->n; |
| 140 |
17 |
▶ | while (lo < hi) { |
Branch: 1 branch
| Branch | True | False | Total |
| while (lo < hi) { |
14 |
3 |
17 |
|
| 141 |
14 |
| uint32_t mid = lo + (hi - lo) / 2; |
| 142 |
14 |
▶ | if (s->t[s->by_dur[mid]].dur_ns < want) lo = mid + 1; |
Branch: 1 branch
| Branch | True | False | Total |
| if (s->t[s->by_dur[mid]].dur_ns < want) lo = mid + 1; |
8 |
6 |
14 |
|
| 143 |
6 |
| else hi = mid; |
| 144 |
|
| } |
| 145 |
3 |
| return lo; |
| 146 |
|
| } |
| 147 |
|
| |
| 148 |
|
| /* ---- segment-level pruning ------------------------------------------------ */ |
| 149 |
|
| |
| 150 |
|
| typedef struct { |
| 151 |
|
| po_u64 t_min, t_max; |
| 152 |
|
| po_u64 dur_min, dur_max; |
| 153 |
|
| int any_error; |
| 154 |
|
| } po_seg_trace_stats; |
| 155 |
|
| |
| 156 |
|
| /* Can this segment possibly contain a matching trace? Answered from the |
| 157 |
|
| * footer alone, with no index and no mmap of the data. */ |
| 158 |
8 |
| static int po_seg_may_match(const po_seg_trace_stats *st, |
| 159 |
|
| po_u64 from, po_u64 to, |
| 160 |
|
| po_u64 min_dur, int want_error) { |
| 161 |
8 |
▶ | if (st->t_min > to || st->t_max < from) return 0; |
Branch: 2 branches
| Branch | True | False | Total |
| if (st->t_min > to || st->t_max < from) return 0; |
7 |
1 |
8 |
| if (st->t_min > to || st->t_max < from) return 0; |
1 |
6 |
7 |
|
| 162 |
6 |
▶ | if (min_dur && st->dur_max < min_dur) return 0; |
Branch: 2 branches
| Branch | True | False | Total |
| if (min_dur && st->dur_max < min_dur) return 0; |
2 |
4 |
6 |
| if (min_dur && st->dur_max < min_dur) return 0; |
1 |
1 |
2 |
|
| 163 |
5 |
▶ | if (want_error && !st->any_error) return 0; |
Branch: 2 branches
| Branch | True | False | Total |
| if (want_error && !st->any_error) return 0; |
2 |
3 |
5 |
| if (want_error && !st->any_error) return 0; |
1 |
1 |
2 |
|
| 164 |
4 |
| return 1; |
| 165 |
|
| } |
| 166 |
|
| |
| 167 |
|
| #endif /* PO_TATTR_H */ |