include/punk_observe/po_tattr.h

filter: Statementstmt 98.5% 68 / 69 Branchbran 86.6% 52 / 60 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 93.0% 120 / 129 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« include/punk_observe/po_parse.h ↑ Summary include/punk_observe/po_merge.h »
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
&& 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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
for (r = 0; r < tree.n; r++) { 4305 1 4306
93 4305 ▶ if (tree.depth[r] == 0) {
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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 */
« include/punk_observe/po_parse.h ↑ Summary include/punk_observe/po_merge.h »