| 1 |
|
| /* po_maplayout.h - the service map, laid out in C at request time. |
| 2 |
|
| * |
| 3 |
|
| * A layered DAG of fewer than a couple of hundred nodes is trivial |
| 4 |
|
| * arithmetic: assign layers by longest path from the roots, order within a |
| 5 |
|
| * layer to reduce crossings, place, emit. Doing it server-side means no |
| 6 |
|
| * layout library, no client-side reflow, and a map that is in the HTML. |
| 7 |
|
| * |
| 8 |
|
| * A CYCLE IN THE CALL GRAPH IS REAL, NOT CORRUPTION. |
| 9 |
|
| * |
| 10 |
|
| * Services genuinely call each other back - a gateway calls auth, auth calls |
| 11 |
|
| * the gateway's token endpoint. A longest-path layering loops forever on |
| 12 |
|
| * that. So back edges are DETECTED and drawn differently rather than being |
| 13 |
|
| * treated as an error or, worse, silently dropped: an edge that exists and is |
| 14 |
|
| * not on the map is a lie about the topology. |
| 15 |
|
| * |
| 16 |
|
| * (This is a different thing from phase 7's parent-pointer cycle, which IS |
| 17 |
|
| * corruption. Both are bounded; only one is legitimate.) |
| 18 |
|
| */ |
| 19 |
|
| #ifndef PO_MAPLAYOUT_H |
| 20 |
|
| #define PO_MAPLAYOUT_H |
| 21 |
|
| |
| 22 |
|
| #include "punk_observe/po_compat.h" |
| 23 |
|
| #include "punk_observe/po_sgraph.h" |
| 24 |
|
| |
| 25 |
|
| #define PO_MAP_MAX_NODES 256 |
| 26 |
|
| #define PO_MAP_MAX_LAYER 32 |
| 27 |
|
| |
| 28 |
|
| typedef struct { |
| 29 |
|
| uint32_t service; /* symbol id, or PO_SVC_UNKNOWN for the root */ |
| 30 |
|
| int layer; |
| 31 |
|
| int slot; /* position within the layer */ |
| 32 |
|
| po_u64 in_count, out_count, errors; |
| 33 |
|
| } po_map_node; |
| 34 |
|
| |
| 35 |
|
| typedef struct { |
| 36 |
|
| po_map_node node[PO_MAP_MAX_NODES]; |
| 37 |
|
| int n; |
| 38 |
|
| int layer_count; |
| 39 |
|
| int back_edges; /* edges that close a cycle */ |
| 40 |
|
| } po_map; |
| 41 |
|
| |
| 42 |
280 |
| static int po_map_find(po_map *m, uint32_t svc) { |
| 43 |
|
| int i; |
| 44 |
618 |
▶ | for (i = 0; i < m->n; i++) if (m->node[i].service == svc) return i; |
Branch: 2 branches
| Branch | True | False | Total |
| for (i = 0; i < m->n; i++) if (m->node[i].service == svc) return i; |
238 |
338 |
576 |
| for (i = 0; i < m->n; i++) if (m->node[i].service == svc) return i; |
576 |
42 |
618 |
|
| 45 |
42 |
▶ | if (m->n >= PO_MAP_MAX_NODES) return -1; |
Branch: 1 branch
| Branch | True | False | Total |
| if (m->n >= PO_MAP_MAX_NODES) return -1; |
0 |
42 |
42 |
|
| 46 |
42 |
| m->node[m->n].service = svc; |
| 47 |
42 |
| m->node[m->n].layer = -1; |
| 48 |
42 |
| return m->n++; |
| 49 |
|
| } |
| 50 |
|
| |
| 51 |
|
| /* Longest-path layering, iterated to a fixed point with a bound. |
| 52 |
|
| * |
| 53 |
|
| * The bound is what makes a cycle terminate: with N nodes, no honest longest |
| 54 |
|
| * path exceeds N, so anything still moving after N rounds is going round a |
| 55 |
|
| * loop. Those edges are counted and the node keeps the layer it had. */ |
| 56 |
14 |
| static int po_map_layout(po_map *m, const po_sgraph *g) { |
| 57 |
14 |
| int i, round, moved = 1; |
| 58 |
|
| |
| 59 |
14 |
| memset(m, 0, sizeof(*m)); |
| 60 |
47 |
▶ | for (i = 0; i < (int)g->n; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < (int)g->n; i++) { |
33 |
14 |
47 |
|
| 61 |
33 |
| int a = po_map_find(m, g->e[i].caller); |
| 62 |
33 |
| int b = po_map_find(m, g->e[i].callee); |
| 63 |
33 |
▶ | if (a < 0 || b < 0) return 0; |
Branch: 2 branches
| Branch | True | False | Total |
| if (a < 0 || b < 0) return 0; |
33 |
0 |
33 |
| if (a < 0 || b < 0) return 0; |
0 |
33 |
33 |
|
| 64 |
33 |
| m->node[a].out_count += g->e[i].count; |
| 65 |
33 |
| m->node[b].in_count += g->e[i].count; |
| 66 |
33 |
| m->node[b].errors += g->e[i].errors; |
| 67 |
|
| } |
| 68 |
|
| |
| 69 |
|
| /* The synthetic root, and anything nothing calls, starts at layer 0. */ |
| 70 |
56 |
▶ | for (i = 0; i < m->n; i++) |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < m->n; i++) |
42 |
14 |
56 |
|
| 71 |
42 |
▶ | if (m->node[i].service == PO_SVC_UNKNOWN || m->node[i].in_count == 0) |
Branch: 2 branches
| Branch | True | False | Total |
| if (m->node[i].service == PO_SVC_UNKNOWN || m->node[i].in_count == 0) |
32 |
10 |
42 |
| if (m->node[i].service == PO_SVC_UNKNOWN || m->node[i].in_count == 0) |
0 |
32 |
32 |
|
| 72 |
10 |
| m->node[i].layer = 0; |
| 73 |
56 |
▶ | for (i = 0; i < m->n; i++) if (m->node[i].layer < 0) m->node[i].layer = 0; |
Branch: 2 branches
| Branch | True | False | Total |
| for (i = 0; i < m->n; i++) if (m->node[i].layer < 0) m->node[i].layer = 0; |
32 |
10 |
42 |
| for (i = 0; i < m->n; i++) if (m->node[i].layer < 0) m->node[i].layer = 0; |
42 |
14 |
56 |
|
| 74 |
|
| |
| 75 |
44 |
▶ | for (round = 0; round < m->n + 1 && moved; round++) { |
Branch: 2 branches
| Branch | True | False | Total |
| for (round = 0; round < m->n + 1 && moved; round++) { |
40 |
4 |
44 |
| for (round = 0; round < m->n + 1 && moved; round++) { |
30 |
10 |
40 |
|
| 76 |
30 |
| moved = 0; |
| 77 |
104 |
▶ | for (i = 0; i < (int)g->n; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < (int)g->n; i++) { |
74 |
30 |
104 |
|
| 78 |
74 |
| int a = po_map_find(m, g->e[i].caller); |
| 79 |
74 |
| int b = po_map_find(m, g->e[i].callee); |
| 80 |
74 |
▶ | if (a < 0 || b < 0) continue; |
Branch: 2 branches
| Branch | True | False | Total |
| if (a < 0 || b < 0) continue; |
74 |
0 |
74 |
| if (a < 0 || b < 0) continue; |
0 |
74 |
74 |
|
| 81 |
74 |
▶ | if (m->node[b].layer <= m->node[a].layer) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (m->node[b].layer <= m->node[a].layer) { |
43 |
31 |
74 |
|
| 82 |
43 |
▶ | if (round < m->n) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (round < m->n) { |
40 |
3 |
43 |
|
| 83 |
40 |
| m->node[b].layer = m->node[a].layer + 1; |
| 84 |
40 |
| moved = 1; |
| 85 |
|
| } |
| 86 |
|
| } |
| 87 |
|
| } |
| 88 |
|
| } |
| 89 |
|
| |
| 90 |
|
| /* Anything still violating the layering after the bound closes a cycle. |
| 91 |
|
| * Counted, and the caller draws those edges differently. */ |
| 92 |
47 |
▶ | for (i = 0; i < (int)g->n; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < (int)g->n; i++) { |
33 |
14 |
47 |
|
| 93 |
33 |
| int a = po_map_find(m, g->e[i].caller); |
| 94 |
33 |
| int b = po_map_find(m, g->e[i].callee); |
| 95 |
33 |
▶ | if (a >= 0 && b >= 0 && m->node[b].layer <= m->node[a].layer) |
Branch: 3 branches
| Branch | True | False | Total |
| if (a >= 0 && b >= 0 && m->node[b].layer <= m->node[a].layer) |
33 |
0 |
33 |
| if (a >= 0 && b >= 0 && m->node[b].layer <= m->node[a].layer) |
33 |
0 |
33 |
| if (a >= 0 && b >= 0 && m->node[b].layer <= m->node[a].layer) |
3 |
30 |
33 |
|
| 96 |
3 |
| m->back_edges++; |
| 97 |
|
| } |
| 98 |
|
| |
| 99 |
56 |
▶ | for (i = 0; i < m->n; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < m->n; i++) { |
42 |
14 |
56 |
|
| 100 |
42 |
▶ | if (m->node[i].layer >= PO_MAP_MAX_LAYER) |
Branch: 1 branch
| Branch | True | False | Total |
| if (m->node[i].layer >= PO_MAP_MAX_LAYER) |
0 |
42 |
42 |
|
| 101 |
0 |
| m->node[i].layer = PO_MAP_MAX_LAYER - 1; |
| 102 |
42 |
▶ | if (m->node[i].layer + 1 > m->layer_count) |
Branch: 1 branch
| Branch | True | False | Total |
| if (m->node[i].layer + 1 > m->layer_count) |
34 |
8 |
42 |
|
| 103 |
34 |
| m->layer_count = m->node[i].layer + 1; |
| 104 |
|
| } |
| 105 |
|
| |
| 106 |
|
| /* Slot within the layer: busiest first, so the eye lands on the service |
| 107 |
|
| * carrying the traffic rather than on whichever one readdir found. */ |
| 108 |
|
| { |
| 109 |
|
| int l; |
| 110 |
62 |
▶ | for (l = 0; l < m->layer_count; l++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (l = 0; l < m->layer_count; l++) { |
48 |
14 |
62 |
|
| 111 |
48 |
| int slot = 0, j; |
| 112 |
42 |
| for (;;) { |
| 113 |
90 |
| int best = -1; |
| 114 |
90 |
| po_u64 bestc = 0; |
| 115 |
395 |
▶ | for (j = 0; j < m->n; j++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (j = 0; j < m->n; j++) { |
305 |
90 |
395 |
|
| 116 |
305 |
▶ | if (m->node[j].layer != l || m->node[j].slot) continue; |
Branch: 2 branches
| Branch | True | False | Total |
| if (m->node[j].layer != l || m->node[j].slot) continue; |
98 |
207 |
305 |
| if (m->node[j].layer != l || m->node[j].slot) continue; |
49 |
49 |
98 |
|
| 117 |
49 |
▶ | if (best < 0 || m->node[j].in_count > bestc) { |
Branch: 2 branches
| Branch | True | False | Total |
| if (best < 0 || m->node[j].in_count > bestc) { |
7 |
42 |
49 |
| if (best < 0 || m->node[j].in_count > bestc) { |
2 |
5 |
7 |
|
| 118 |
44 |
| best = j; bestc = m->node[j].in_count; |
| 119 |
|
| } |
| 120 |
|
| } |
| 121 |
90 |
▶ | if (best < 0) break; |
Branch: 1 branch
| Branch | True | False | Total |
| if (best < 0) break; |
48 |
42 |
90 |
|
| 122 |
42 |
| m->node[best].slot = ++slot; |
| 123 |
|
| } |
| 124 |
|
| } |
| 125 |
|
| } |
| 126 |
14 |
| return 1; |
| 127 |
|
| } |
| 128 |
|
| |
| 129 |
33 |
| static int po_map_is_back_edge(const po_map *m, uint32_t caller, uint32_t callee) { |
| 130 |
33 |
| int a = -1, b = -1, i; |
| 131 |
152 |
▶ | for (i = 0; i < m->n; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < m->n; i++) { |
119 |
33 |
152 |
|
| 132 |
119 |
▶ | if (m->node[i].service == caller) a = i; |
Branch: 1 branch
| Branch | True | False | Total |
| if (m->node[i].service == caller) a = i; |
33 |
86 |
119 |
|
| 133 |
119 |
▶ | if (m->node[i].service == callee) b = i; |
Branch: 1 branch
| Branch | True | False | Total |
| if (m->node[i].service == callee) b = i; |
33 |
86 |
119 |
|
| 134 |
|
| } |
| 135 |
33 |
▶ | if (a < 0 || b < 0) return 0; |
Branch: 2 branches
| Branch | True | False | Total |
| if (a < 0 || b < 0) return 0; |
33 |
0 |
33 |
| if (a < 0 || b < 0) return 0; |
0 |
33 |
33 |
|
| 136 |
33 |
| return m->node[b].layer <= m->node[a].layer; |
| 137 |
|
| } |
| 138 |
|
| |
| 139 |
|
| #endif /* PO_MAPLAYOUT_H */ |