| 1 |
|
| /* po_sgraph.h - the service graph, accumulated at seal. |
| 2 |
|
| * |
| 3 |
|
| * The service map needs edges: which service called which, how often, how |
| 4 |
|
| * fast, how often it failed. Computing that at QUERY time means scanning |
| 5 |
|
| * every span in the range on every page load, which makes the most-visited |
| 6 |
|
| * screen the most expensive one. |
| 7 |
|
| * |
| 8 |
|
| * The compactor already walks every span, so it also accumulates a small edge |
| 9 |
|
| * table. The table is tiny - services times services, not spans - so the |
| 10 |
|
| * service map reads a few kilobytes per segment and aggregates. |
| 11 |
|
| * |
| 12 |
|
| * THE EDGE RULE. A span whose parent belongs to a DIFFERENT service is a call |
| 13 |
|
| * across a service boundary. That is simpler than matching CLIENT spans to |
| 14 |
|
| * their SERVER children and it is more robust: it produces an edge whether or |
| 15 |
|
| * not both sides set span.kind, which plenty of instrumentation does not. |
| 16 |
|
| * |
| 17 |
|
| * A SPAN WHOSE PARENT IS ABSENT gets an edge from a synthetic root rather |
| 18 |
|
| * than being dropped. A request whose caller was not instrumented is exactly |
| 19 |
|
| * the thing a service map should SHOW - "traffic is arriving from somewhere I |
| 20 |
|
| * cannot see" is a finding, not a gap to hide. |
| 21 |
|
| */ |
| 22 |
|
| #ifndef PO_SGRAPH_H |
| 23 |
|
| #define PO_SGRAPH_H |
| 24 |
|
| |
| 25 |
|
| #include "punk_observe/po_compat.h" |
| 26 |
|
| #include "punk_observe/po_span.h" |
| 27 |
|
| |
| 28 |
|
| #define PO_SVC_UNKNOWN 0xFFFFFFFFu /* the synthetic root */ |
| 29 |
|
| |
| 30 |
|
| typedef struct { |
| 31 |
|
| uint32_t caller; /* service symbol, or PO_SVC_UNKNOWN */ |
| 32 |
|
| uint32_t callee; |
| 33 |
|
| po_u64 count; |
| 34 |
|
| po_u64 errors; |
| 35 |
|
| po_u64 dur_sum; /* nanoseconds; enough for a mean */ |
| 36 |
|
| po_u64 dur_max; |
| 37 |
|
| } po_edge; |
| 38 |
|
| |
| 39 |
|
| typedef struct { |
| 40 |
|
| po_edge *e; |
| 41 |
|
| uint32_t n, cap; |
| 42 |
|
| } po_sgraph; |
| 43 |
|
| |
| 44 |
154 |
| static int po_sgraph_init(po_sgraph *g) { |
| 45 |
154 |
| memset(g, 0, sizeof(*g)); |
| 46 |
154 |
| g->cap = 32; |
| 47 |
154 |
| g->e = (po_edge *)calloc(g->cap, sizeof(po_edge)); |
| 48 |
154 |
| return g->e != NULL; |
| 49 |
|
| } |
| 50 |
|
| |
| 51 |
154 |
| static void po_sgraph_free(po_sgraph *g) { |
| 52 |
154 |
| free(g->e); g->e = NULL; g->n = g->cap = 0; |
| 53 |
154 |
| } |
| 54 |
|
| |
| 55 |
11032 |
| static po_edge *po_sgraph_find(po_sgraph *g, uint32_t caller, uint32_t callee) { |
| 56 |
|
| uint32_t i; |
| 57 |
|
| /* Linear: the table is services-squared, which is tens, not thousands. |
| 58 |
|
| * A hash here would be more code than it saves. */ |
| 59 |
14946 |
▶ | for (i = 0; i < g->n; i++) |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < g->n; i++) |
14829 |
117 |
14946 |
|
| 60 |
14829 |
▶ | if (g->e[i].caller == caller && g->e[i].callee == callee) |
Branch: 2 branches
| Branch | True | False | Total |
| if (g->e[i].caller == caller && g->e[i].callee == callee) |
11605 |
3224 |
14829 |
| if (g->e[i].caller == caller && g->e[i].callee == callee) |
10915 |
690 |
11605 |
|
| 61 |
10915 |
| return &g->e[i]; |
| 62 |
117 |
▶ | if (g->n == g->cap) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (g->n == g->cap) { |
0 |
117 |
117 |
|
| 63 |
0 |
| uint32_t want = g->cap * 2; |
| 64 |
0 |
| po_edge *ne = (po_edge *)realloc(g->e, want * sizeof(po_edge)); |
| 65 |
0 |
▶ | if (!ne) return NULL; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!ne) return NULL; |
0 |
0 |
0 |
|
| 66 |
0 |
| memset(ne + g->cap, 0, (want - g->cap) * sizeof(po_edge)); |
| 67 |
0 |
| g->e = ne; g->cap = want; |
| 68 |
|
| } |
| 69 |
117 |
| g->e[g->n].caller = caller; |
| 70 |
117 |
| g->e[g->n].callee = callee; |
| 71 |
117 |
| return &g->e[g->n++]; |
| 72 |
|
| } |
| 73 |
|
| |
| 74 |
|
| /* Accumulate edges from one trace's spans, using the tree already built. |
| 75 |
|
| * |
| 76 |
|
| * Walks the assembled tree rather than raw parent ids, so a span whose parent |
| 77 |
|
| * is genuinely absent is distinguished from one whose parent simply has not |
| 78 |
|
| * been looked up yet. */ |
| 79 |
4144 |
| static int po_sgraph_add_trace(po_sgraph *g, const po_span *s, uint32_t n, |
| 80 |
|
| const po_tree *t) { |
| 81 |
|
| uint32_t i; |
| 82 |
15196 |
▶ | for (i = 0; i < n; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < n; i++) { |
11052 |
4144 |
15196 |
|
| 83 |
|
| uint32_t caller; |
| 84 |
|
| po_edge *e; |
| 85 |
|
| |
| 86 |
11052 |
▶ | if (t->parent[i] >= 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (t->parent[i] >= 0) { |
2989 |
8063 |
11052 |
|
| 87 |
2989 |
| uint32_t p = (uint32_t)t->parent[i]; |
| 88 |
|
| /* Same service: an internal call, not a graph edge. Counting it |
| 89 |
|
| * would make every service a self-loop dominating the map. */ |
| 90 |
2989 |
▶ | if (s[p].service_sym == s[i].service_sym) continue; |
Branch: 1 branch
| Branch | True | False | Total |
| if (s[p].service_sym == s[i].service_sym) continue; |
53 |
2936 |
2989 |
|
| 91 |
2936 |
| caller = s[p].service_sym; |
| 92 |
|
| } |
| 93 |
|
| else { |
| 94 |
|
| /* No parent in the trace. A true root is entry traffic; a span |
| 95 |
|
| * whose named parent is missing is traffic from something |
| 96 |
|
| * uninstrumented. Both are edges from the synthetic root, and |
| 97 |
|
| * both are worth seeing. */ |
| 98 |
8063 |
| caller = PO_SVC_UNKNOWN; |
| 99 |
|
| } |
| 100 |
|
| |
| 101 |
10999 |
| e = po_sgraph_find(g, caller, s[i].service_sym); |
| 102 |
10999 |
▶ | if (!e) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!e) return 0; |
0 |
10999 |
10999 |
|
| 103 |
10999 |
| e->count++; |
| 104 |
10999 |
▶ | if (po_span_is_error(&s[i])) e->errors++; |
Branch: 1 branch
| Branch | True | False | Total |
| if (po_span_is_error(&s[i])) e->errors++; |
35 |
10964 |
10999 |
|
| 105 |
10999 |
| e->dur_sum += s[i].dur_ns; |
| 106 |
10999 |
▶ | if (s[i].dur_ns > e->dur_max) e->dur_max = s[i].dur_ns; |
Branch: 1 branch
| Branch | True | False | Total |
| if (s[i].dur_ns > e->dur_max) e->dur_max = s[i].dur_ns; |
251 |
10748 |
10999 |
|
| 107 |
|
| } |
| 108 |
4144 |
| return 1; |
| 109 |
|
| } |
| 110 |
|
| |
| 111 |
|
| /* Build over a whole segment's sorted spans. */ |
| 112 |
49 |
| static int po_sgraph_build(po_sgraph *g, const po_span *s, uint32_t n) { |
| 113 |
49 |
| uint32_t i = 0; |
| 114 |
4193 |
▶ | while (i < n) { |
Branch: 1 branch
| Branch | True | False | Total |
| while (i < n) { |
4144 |
49 |
4193 |
|
| 115 |
4144 |
| uint32_t j = i + 1; |
| 116 |
|
| po_tree t; |
| 117 |
15148 |
▶ | while (j < n && s[j].trace_hi == s[i].trace_hi |
Branch: 1 branch
| Branch | True | False | Total |
| while (j < n && s[j].trace_hi == s[i].trace_hi |
10652 |
352 |
11004 |
|
| 118 |
14796 |
▶ | && s[j].trace_lo == s[i].trace_lo) j++; |
Branch: 2 branches
| Branch | True | False | Total |
| && s[j].trace_lo == s[i].trace_lo) j++; |
11004 |
48 |
11052 |
| && s[j].trace_lo == s[i].trace_lo) j++; |
6908 |
3744 |
10652 |
|
| 119 |
4144 |
▶ | if (!po_tree_build(&t, s + i, j - i)) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!po_tree_build(&t, s + i, j - i)) return 0; |
0 |
4144 |
4144 |
|
| 120 |
4144 |
▶ | if (!po_sgraph_add_trace(g, s + i, j - i, &t)) { po_tree_free(&t); return 0; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (!po_sgraph_add_trace(g, s + i, j - i, &t)) { po_tree_free(&t); return 0; } |
0 |
4144 |
4144 |
|
| 121 |
4144 |
| po_tree_free(&t); |
| 122 |
4144 |
| i = j; |
| 123 |
|
| } |
| 124 |
49 |
| return 1; |
| 125 |
|
| } |
| 126 |
|
| |
| 127 |
|
| #endif /* PO_SGRAPH_H */ |