include/punk_observe/po_span.h

filter: Statementstmt 98.8% 84 / 85 Branchbran 85.9% 67 / 78 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 92.6% 151 / 163 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« include/punk_observe/po_panel.h ↑ Summary include/punk_observe/po_live.h »
1 /* po_span.h - spans, and the tree that is built when they are READ.
2 *
3 * A TRACE IS NEVER COMPLETE, so nothing may wait for one.
4 *
5 * The spans of one trace arrive from many processes, in many batches, out of
6 * order, across a window bounded only by the longest span. A backend that
7 * assembles traces at write time has to buffer them, decide when a trace is
8 * done, and be wrong.
9 *
10 * So spans are stored individually and a trace is assembled at read time. The
11 * consequences are all good ones: ingest never buffers, a span arriving an
12 * hour late still joins its trace, and there is no "trace timeout" setting
13 * for anyone to get wrong. The cost is that reading a trace is a lookup
14 * rather than a sequential read, which is what po_traceidx.h is for - and
15 * spans are SORTED at seal by (trace, start) so that once the lookup lands,
16 * the trace's spans are physically contiguous.
17 */
18 #ifndef PO_SPAN_H
19 #define PO_SPAN_H
20  
21 #include "punk_observe/po_compat.h"
22 #include "punk_observe/po_rec.h"
23 #include "punk_observe/po_hash.h"
24  
25 /* Span flags */
26 #define PO_SP_ROOT 0x0001 /* no parent AT ALL, decided at read time */
27 #define PO_SP_ERROR 0x0002
28 #define PO_SP_CLAMPED 0x0004 /* end < start; see phase 0's clock rule */
29  
30 /* Fixed 64 bytes: 8-byte members first, then 4, then 2, then 1, so the
31 * layout is stable across every ABI in the smoker matrix. */
32 typedef struct {
33 po_u64 trace_hi, trace_lo;
34 po_u64 span_id;
35 po_u64 parent_span_id;
36 po_u64 start_ns;
37 po_u64 dur_ns;
38 uint32_t name_sym; /* into the segment's symbol table */
39 uint32_t service_sym;
40 uint16_t flags;
41 uint8_t kind; /* OTLP SpanKind */
42 uint8_t status; /* OTLP StatusCode */
43 uint8_t pad[4];
44 } po_span;
45  
46 #define PO_SPAN_SIZE 64
47  
48 43595 static int po_span_is_error(const po_span *s) { return s->status == PO_ST_ERROR; }
49  
50 /* Sort key: trace first so a trace's spans are contiguous, then start time so
51 * they are already in waterfall order once found. */
52 138278 static int po_span_cmp(const void *va, const void *vb) {
53 138278 const po_span *a = (const po_span *)va, *b = (const po_span *)vb;
54 138278 ▶ if (a->trace_hi != b->trace_hi) return a->trace_hi < b->trace_hi ? -1 : 1;
Branch: 2 branches
BranchTrueFalseTotal
if (a->trace_hi != b->trace_hi) return a->trace_hi < b->trace_hi ? -1 : 1; 74164 64114 138278
if (a->trace_hi != b->trace_hi) return a->trace_hi < b->trace_hi ? -1 : 1; 48482 25682 74164
55 64114 ▶ if (a->trace_lo != b->trace_lo) return a->trace_lo < b->trace_lo ? -1 : 1;
Branch: 2 branches
BranchTrueFalseTotal
if (a->trace_lo != b->trace_lo) return a->trace_lo < b->trace_lo ? -1 : 1; 33005 31109 64114
if (a->trace_lo != b->trace_lo) return a->trace_lo < b->trace_lo ? -1 : 1; 32974 31 33005
56 31109 ▶ if (a->start_ns != b->start_ns) return a->start_ns < b->start_ns ? -1 : 1;
Branch: 2 branches
BranchTrueFalseTotal
if (a->start_ns != b->start_ns) return a->start_ns < b->start_ns ? -1 : 1; 31089 20 31109
if (a->start_ns != b->start_ns) return a->start_ns < b->start_ns ? -1 : 1; 31084 5 31089
57 /* A total order: two spans with the same trace and start need a tiebreak,
58 * or the sort is unstable and the same segment sealed twice differs. */
59 20 ▶ if (a->span_id != b->span_id) return a->span_id < b->span_id ? -1 : 1;
Branch: 2 branches
BranchTrueFalseTotal
if (a->span_id != b->span_id) return a->span_id < b->span_id ? -1 : 1; 1 19 20
if (a->span_id != b->span_id) return a->span_id < b->span_id ? -1 : 1; 1 0 1
60 19 return 0;
61 }
62  
63 /* ---- the writer ----------------------------------------------------------- */
64  
65 typedef struct {
66 po_span *s;
67 size_t n, cap;
68 po_u64 t_min, t_max;
69 po_u64 dur_min, dur_max;
70 int any_error; /* so a segment with no error span is never
71 * opened for an error query */
72 uint32_t clamped;
73 } po_span_w;
74  
75 186 static int po_span_w_init(po_span_w *w) {
76 186 memset(w, 0, sizeof(*w));
77 186 w->cap = 256;
78 186 w->s = (po_span *)malloc(w->cap * sizeof(po_span));
79 186 ▶ if (!w->s) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!w->s) return 0; 0 186 186
80 186 w->t_min = PO_U64_MAX;
81 186 w->dur_min = PO_U64_MAX;
82 186 return 1;
83 }
84  
85 186 static void po_span_w_free(po_span_w *w) { free(w->s); w->s = NULL; w->n = w->cap = 0; }
86  
87 22549 static int po_span_add(po_span_w *w, const po_span *src) {
88 po_span *d;
89 22549 ▶ if (w->n == w->cap) {
Branch: 1 branch
BranchTrueFalseTotal
if (w->n == w->cap) { 35 22514 22549
90 35 size_t want = w->cap * 2;
91 35 po_span *ns = (po_span *)realloc(w->s, want * sizeof(po_span));
92 35 ▶ if (!ns) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!ns) return 0; 0 35 35
93 35 w->s = ns; w->cap = want;
94 }
95 22549 d = &w->s[w->n++];
96 22549 *d = *src;
97  
98 22549 ▶ if (d->start_ns < w->t_min) w->t_min = d->start_ns;
Branch: 1 branch
BranchTrueFalseTotal
if (d->start_ns < w->t_min) w->t_min = d->start_ns; 120 22429 22549
99 22549 ▶ if (d->start_ns > w->t_max) w->t_max = d->start_ns;
Branch: 1 branch
BranchTrueFalseTotal
if (d->start_ns > w->t_max) w->t_max = d->start_ns; 21930 619 22549
100 22549 ▶ if (d->dur_ns < w->dur_min) w->dur_min = d->dur_ns;
Branch: 1 branch
BranchTrueFalseTotal
if (d->dur_ns < w->dur_min) w->dur_min = d->dur_ns; 238 22311 22549
101 22549 ▶ if (d->dur_ns > w->dur_max) w->dur_max = d->dur_ns;
Branch: 1 branch
BranchTrueFalseTotal
if (d->dur_ns > w->dur_max) w->dur_max = d->dur_ns; 3700 18849 22549
102 22549 ▶ if (po_span_is_error(d)) w->any_error = 1;
Branch: 1 branch
BranchTrueFalseTotal
if (po_span_is_error(d)) w->any_error = 1; 71 22478 22549
103 22549 ▶ if (d->flags & PO_SP_CLAMPED) w->clamped++;
Branch: 1 branch
BranchTrueFalseTotal
if (d->flags & PO_SP_CLAMPED) w->clamped++; 1 22548 22549
104 22549 return 1;
105 }
106  
107 186 static void po_span_w_seal(po_span_w *w) {
108 186 ▶ if (w->n > 1) qsort(w->s, w->n, sizeof(po_span), po_span_cmp);
Branch: 1 branch
BranchTrueFalseTotal
if (w->n > 1) qsort(w->s, w->n, sizeof(po_span), po_span_cmp); 103 83 186
109 186 }
110  
111 /* ---- the tree, built at READ time ----------------------------------------
112 *
113 * A hash join over the spans returned: span_id -> index, then each span's
114 * parent is looked up among them.
115 *
116 * TWO THINGS THAT LOOK LIKE DETAILS AND ARE NOT.
117 *
118 * 1. parent_span_id == 0 means root, but a span whose parent IS present in
119 * the trace and merely arrived in a later segment is NOT a root. So
120 * rootness is decided only after the whole trace is assembled - deciding
121 * it per span, at write time, makes every trace show several roots.
122 *
123 * 2. A cycle in the parent chain is possible from broken instrumentation, and
124 * a naive tree walk recurses forever on it. Bounded, and reported.
125 */
126 #define PO_TREE_MAX_DEPTH 256
127  
128 typedef struct {
129 const po_span *s;
130 uint32_t n;
131 int32_t *parent; /* index of the parent span, or -1 */
132 int32_t *depth; /* 0 for a root */
133 uint32_t roots;
134 uint32_t cycles; /* spans whose ancestry loops */
135 uint32_t orphans; /* parent named but not present */
136 } po_tree;
137  
138 8490 static void po_tree_free(po_tree *t) {
139 8490 free(t->parent); free(t->depth);
140 8490 t->parent = NULL; t->depth = NULL;
141 8490 }
142  
143 8490 static int po_tree_build(po_tree *t, const po_span *spans, uint32_t n) {
144 uint32_t i;
145 8490 uint32_t slots = 16, mask;
146 uint32_t *idx;
147  
148 8490 memset(t, 0, sizeof(*t));
149 8490 t->s = spans; t->n = n;
150 8490 ▶ if (n == 0) return 1;
Branch: 1 branch
BranchTrueFalseTotal
if (n == 0) return 1; 0 8490 8490
151  
152 8490 t->parent = (int32_t *)malloc((size_t)n * sizeof(int32_t));
153 8490 t->depth = (int32_t *)malloc((size_t)n * sizeof(int32_t));
154 8490 ▶ if (!t->parent || !t->depth) { po_tree_free(t); return 0; }
Branch: 2 branches
BranchTrueFalseTotal
if (!t->parent || !t->depth) { po_tree_free(t); return 0; } 8490 0 8490
if (!t->parent || !t->depth) { po_tree_free(t); return 0; } 0 8490 8490
155  
156 9102 ▶ while (slots < n * 2) slots <<= 1;
Branch: 1 branch
BranchTrueFalseTotal
while (slots < n * 2) slots <<= 1; 612 8490 9102
157 8490 mask = slots - 1;
158 8490 idx = (uint32_t *)calloc(slots, sizeof(uint32_t));
159 8490 ▶ if (!idx) { po_tree_free(t); return 0; }
Branch: 1 branch
BranchTrueFalseTotal
if (!idx) { po_tree_free(t); return 0; } 0 8490 8490
160  
161 29771 ▶ for (i = 0; i < n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n; i++) { 21281 8490 29771
162 21281 uint32_t h = (uint32_t)(spans[i].span_id) & mask;
163 21361 ▶ while (idx[h]) h = (h + 1) & mask;
Branch: 1 branch
BranchTrueFalseTotal
while (idx[h]) h = (h + 1) & mask; 80 21281 21361
164 21281 idx[h] = i + 1;
165 }
166  
167 29771 ▶ for (i = 0; i < n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n; i++) { 21281 8490 29771
168 21281 t->parent[i] = -1;
169 21281 t->depth[i] = -1;
170 21281 ▶ if (spans[i].parent_span_id) {
Branch: 1 branch
BranchTrueFalseTotal
if (spans[i].parent_span_id) { 4925 16356 21281
171 4925 uint32_t h = (uint32_t)(spans[i].parent_span_id) & mask;
172 4925 int found = 0;
173 4925 ▶ while (idx[h]) {
Branch: 1 branch
BranchTrueFalseTotal
while (idx[h]) { 4915 10 4925
174 4915 uint32_t j = idx[h] - 1;
175 4915 ▶ if (spans[j].span_id == spans[i].parent_span_id
Branch: 1 branch
BranchTrueFalseTotal
if (spans[j].span_id == spans[i].parent_span_id 4915 0 4915
176 4915 ▶ && spans[j].trace_hi == spans[i].trace_hi
Branch: 1 branch
BranchTrueFalseTotal
&& spans[j].trace_hi == spans[i].trace_hi 4915 0 4915
177 4915 ▶ && spans[j].trace_lo == spans[i].trace_lo) {
Branch: 1 branch
BranchTrueFalseTotal
&& spans[j].trace_lo == spans[i].trace_lo) { 4915 0 4915
178 4915 t->parent[i] = (int32_t)j;
179 4915 found = 1;
180 4915 break;
181 }
182 0 h = (h + 1) & mask;
183 }
184 /* A parent named but absent: the span is a root FOR NOW, and
185 * counted, because that count is how an operator sees that a
186 * trace is incomplete rather than genuinely shallow. */
187 4925 ▶ if (!found) t->orphans++;
Branch: 1 branch
BranchTrueFalseTotal
if (!found) t->orphans++; 10 4915 4925
188 }
189 }
190 8490 free(idx);
191  
192 /* Depths, with the cycle bound. */
193 29771 ▶ for (i = 0; i < n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n; i++) { 21281 8490 29771
194 21281 int32_t cur = (int32_t)i;
195 21281 int d = 0;
196 31927 ▶ while (cur >= 0 && d <= PO_TREE_MAX_DEPTH) {
Branch: 2 branches
BranchTrueFalseTotal
while (cur >= 0 && d <= PO_TREE_MAX_DEPTH) { 31927 0 31927
while (cur >= 0 && d <= PO_TREE_MAX_DEPTH) { 31921 6 31927
197 31921 ▶ if (t->parent[cur] < 0) break;
Branch: 1 branch
BranchTrueFalseTotal
if (t->parent[cur] < 0) break; 21275 10646 31921
198 10646 cur = t->parent[cur];
199 10646 d++;
200 }
201 21281 ▶ if (d > PO_TREE_MAX_DEPTH) { t->depth[i] = -1; t->cycles++; }
Branch: 1 branch
BranchTrueFalseTotal
if (d > PO_TREE_MAX_DEPTH) { t->depth[i] = -1; t->cycles++; } 6 21275 21281
202 21275 else t->depth[i] = d;
203 }
204  
205 29771 ▶ for (i = 0; i < n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n; i++) { 21281 8490 29771
206 21281 ▶ if (t->depth[i] == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (t->depth[i] == 0) { 16366 4915 21281
207 16366 t->roots++;
208 /* Rootness is set HERE, after assembly, not at write time. */
209 }
210 }
211 8490 return 1;
212 }
213  
214 #endif /* PO_SPAN_H */
« include/punk_observe/po_panel.h ↑ Summary include/punk_observe/po_live.h »