include/punk_observe/po_maplayout.h

filter: Statementstmt 98.3% 58 / 59 Branchbran 85.1% 63 / 74 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 90.9% 121 / 133 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« include/punk_observe/po_query.h ↑ Summary include/punk_observe/po_tenant.h »
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
if (m->node[b].layer <= m->node[a].layer) { 43 31 74
82 43 ▶ if (round < m->n) {
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
for (i = 0; i < m->n; i++) { 42 14 56
100 42 ▶ if (m->node[i].layer >= PO_MAP_MAX_LAYER)
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
for (i = 0; i < m->n; i++) { 119 33 152
132 119 ▶ if (m->node[i].service == caller) a = i;
Branch: 1 branch
BranchTrueFalseTotal
if (m->node[i].service == caller) a = i; 33 86 119
133 119 ▶ if (m->node[i].service == callee) b = i;
Branch: 1 branch
BranchTrueFalseTotal
if (m->node[i].service == callee) b = i; 33 86 119
134 }
135 33 ▶ if (a < 0 || b < 0) return 0;
Branch: 2 branches
BranchTrueFalseTotal
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 */
« include/punk_observe/po_query.h ↑ Summary include/punk_observe/po_tenant.h »