| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (!idx) { po_tree_free(t); return 0; } |
0 |
8490 |
8490 |
|
| 160 |
|
| |
| 161 |
29771 |
▶ | for (i = 0; i < n; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| && spans[j].trace_hi == spans[i].trace_hi |
4915 |
0 |
4915 |
|
| 177 |
4915 |
▶ | && spans[j].trace_lo == spans[i].trace_lo) { |
Branch: 1 branch
| Branch | True | False | Total |
| && 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| for (i = 0; i < n; i++) { |
21281 |
8490 |
29771 |
|
| 206 |
21281 |
▶ | if (t->depth[i] == 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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 */ |