include/punk_observe/po_flame.h

filter: Statementstmt 92.8% 65 / 70 Branchbran 75.0% 39 / 52 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 85.2% 104 / 122 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« xs/tenant.xs ↑ Summary include/punk_observe/po_shared.h »
1 /* po_flame.h - the aggregated self-time tree.
2 *
3 * SELF TIME, NOT TOTAL TIME, is what a flamegraph is for. A root span that
4 * lasts five seconds because it waited on a database did not SPEND five
5 * seconds; the database did. Attributing total time to the parent makes every
6 * flamegraph say "the entry point is slow", which is true and useless.
7 *
8 * self = duration - (time covered by children)
9 *
10 * "Covered by", not "sum of": concurrent children overlap, and summing them
11 * can exceed the parent's duration and produce a negative self time. Merging
12 * the child intervals first is the difference between a correct graph and one
13 * with impossible bars in it.
14 */
15 #ifndef PO_FLAME_H
16 #define PO_FLAME_H
17  
18 #include "punk_observe/po_compat.h"
19 #include "punk_observe/po_span.h"
20  
21 #define PO_FLAME_MAX 4096
22  
23 typedef struct {
24 uint32_t name_sym;
25 uint32_t service_sym;
26 int32_t parent; /* index into the frame array, or -1 */
27 int32_t depth;
28 po_u64 total; /* summed across every trace merged in */
29 po_u64 self;
30 po_u64 count;
31 } po_frame;
32  
33 typedef struct {
34 po_frame *f;
35 uint32_t n, cap;
36 } po_flame;
37  
38 10 static int po_flame_init(po_flame *fl) {
39 10 memset(fl, 0, sizeof(*fl));
40 10 fl->cap = 64;
41 10 fl->f = (po_frame *)calloc(fl->cap, sizeof(po_frame));
42 10 return fl->f != NULL;
43 }
44  
45 10 static void po_flame_free(po_flame *fl) {
46 10 free(fl->f); fl->f = NULL; fl->n = fl->cap = 0;
47 10 }
48  
49 /* Frames are keyed by (parent, name, service), so the same function called
50 * from two places stays two frames - which is what makes a flamegraph a
51 * TREE rather than a bar chart of function names. */
52 43 static po_frame *po_flame_frame(po_flame *fl, int32_t parent,
53 uint32_t name, uint32_t service, int32_t depth) {
54 uint32_t i;
55 75 ▶ for (i = 0; i < fl->n; i++)
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < fl->n; i++) 50 25 75
56 50 ▶ if (fl->f[i].parent == parent && fl->f[i].name_sym == name
Branch: 2 branches
BranchTrueFalseTotal
if (fl->f[i].parent == parent && fl->f[i].name_sym == name 21 29 50
if (fl->f[i].parent == parent && fl->f[i].name_sym == name 18 3 21
57 18 ▶ && fl->f[i].service_sym == service) return &fl->f[i];
Branch: 1 branch
BranchTrueFalseTotal
&& fl->f[i].service_sym == service) return &fl->f[i]; 18 0 18
58 25 ▶ if (fl->n == fl->cap) {
Branch: 1 branch
BranchTrueFalseTotal
if (fl->n == fl->cap) { 0 25 25
59 0 uint32_t want = fl->cap * 2;
60 0 po_frame *nf = (po_frame *)realloc(fl->f, want * sizeof(po_frame));
61 0 ▶ if (!nf) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!nf) return NULL; 0 0 0
62 0 memset(nf + fl->cap, 0, (want - fl->cap) * sizeof(po_frame));
63 0 fl->f = nf; fl->cap = want;
64 }
65 25 fl->f[fl->n].parent = parent;
66 25 fl->f[fl->n].name_sym = name;
67 25 fl->f[fl->n].service_sym = service;
68 25 fl->f[fl->n].depth = depth;
69 25 return &fl->f[fl->n++];
70 }
71  
72 /* Merged length of a set of intervals. The merge is what stops concurrent
73 * children double-counting and driving self time negative. */
74 typedef struct { po_u64 a, b; } po_iv;
75  
76 3 static int po_iv_cmp(const void *x, const void *y) {
77 3 const po_iv *p = (const po_iv *)x, *q = (const po_iv *)y;
78 3 ▶ return p->a < q->a ? -1 : (p->a > q->a ? 1 : 0);
Branch: 1 branch
BranchTrueFalseTotal
return p->a < q->a ? -1 : (p->a > q->a ? 1 : 0); 0 3 3
79 }
80  
81 43 static po_u64 po_iv_covered(po_iv *v, uint32_t n) {
82 43 po_u64 total = 0, cur_a, cur_b;
83 uint32_t i;
84 43 ▶ if (!n) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!n) return 0; 22 21 43
85 21 qsort(v, n, sizeof(po_iv), po_iv_cmp);
86 21 cur_a = v[0].a; cur_b = v[0].b;
87 24 ▶ for (i = 1; i < n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 1; i < n; i++) { 3 21 24
88 3 ▶ if (v[i].a <= cur_b) { if (v[i].b > cur_b) cur_b = v[i].b; }
Branch: 2 branches
BranchTrueFalseTotal
if (v[i].a <= cur_b) { if (v[i].b > cur_b) cur_b = v[i].b; } 1 2 3
if (v[i].a <= cur_b) { if (v[i].b > cur_b) cur_b = v[i].b; } 1 0 1
89 2 else { total += cur_b - cur_a; cur_a = v[i].a; cur_b = v[i].b; }
90 }
91 21 total += cur_b - cur_a;
92 21 return total;
93 }
94  
95 /* Fold one assembled trace in. */
96 19 static int po_flame_add(po_flame *fl, const po_span *s, uint32_t n,
97 const po_tree *t) {
98 int32_t *map;
99 uint32_t i, d;
100 po_iv *kids;
101  
102 19 ▶ if (!n) return 1;
Branch: 1 branch
BranchTrueFalseTotal
if (!n) return 1; 0 19 19
103 19 map = (int32_t *)malloc((size_t)n * sizeof(int32_t));
104 19 kids = (po_iv *)malloc((size_t)n * sizeof(po_iv));
105 19 ▶ if (!map || !kids) { free(map); free(kids); return 0; }
Branch: 2 branches
BranchTrueFalseTotal
if (!map || !kids) { free(map); free(kids); return 0; } 19 0 19
if (!map || !kids) { free(map); free(kids); return 0; } 0 19 19
106 62 ▶ for (i = 0; i < n; i++) map[i] = -1;
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n; i++) map[i] = -1; 43 19 62
107  
108 /* Depth order, so a parent's frame exists before its children need it. */
109 58 ▶ for (d = 0; d < PO_TREE_MAX_DEPTH; d++) {
Branch: 1 branch
BranchTrueFalseTotal
for (d = 0; d < PO_TREE_MAX_DEPTH; d++) { 58 0 58
110 58 int any = 0;
111 192 ▶ for (i = 0; i < n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n; i++) { 134 58 192
112 po_frame *f;
113 int32_t parent_frame;
114 134 ▶ if (t->depth[i] != (int32_t)d) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (t->depth[i] != (int32_t)d) continue; 91 43 134
115 43 any = 1;
116 43 ▶ parent_frame = (t->parent[i] >= 0) ? map[t->parent[i]] : -1;
Branch: 1 branch
BranchTrueFalseTotal
parent_frame = (t->parent[i] >= 0) ? map[t->parent[i]] : -1; 24 19 43
117 43 f = po_flame_frame(fl, parent_frame, s[i].name_sym,
118 43 s[i].service_sym, (int32_t)d);
119 43 ▶ if (!f) { free(map); free(kids); return 0; }
Branch: 1 branch
BranchTrueFalseTotal
if (!f) { free(map); free(kids); return 0; } 0 43 43
120 43 map[i] = (int32_t)(f - fl->f);
121  
122 { /* self = duration minus the span COVERED by children */
123 43 uint32_t k, nk = 0;
124 150 ▶ for (k = 0; k < n; k++) {
Branch: 1 branch
BranchTrueFalseTotal
for (k = 0; k < n; k++) { 107 43 150
125 107 ▶ if (t->parent[k] != (int32_t)i) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (t->parent[k] != (int32_t)i) continue; 83 24 107
126 24 kids[nk].a = s[k].start_ns;
127 24 kids[nk].b = s[k].start_ns + s[k].dur_ns;
128 24 nk++;
129 }
130 {
131 43 po_u64 cov = po_iv_covered(kids, nk);
132 43 ▶ po_u64 self = s[i].dur_ns > cov ? s[i].dur_ns - cov : 0;
Branch: 1 branch
BranchTrueFalseTotal
po_u64 self = s[i].dur_ns > cov ? s[i].dur_ns - cov : 0; 43 0 43
133 43 f->total += s[i].dur_ns;
134 43 f->self += self;
135 43 f->count++;
136 }
137 }
138 }
139 58 ▶ if (!any && d > 0) break;
Branch: 2 branches
BranchTrueFalseTotal
if (!any && d > 0) break; 19 39 58
if (!any && d > 0) break; 19 0 19
140 }
141 19 free(map); free(kids);
142 19 return 1;
143 }
144  
145 10 static po_u64 po_flame_total_self(const po_flame *fl) {
146 10 po_u64 t = 0;
147 uint32_t i;
148 35 ▶ for (i = 0; i < fl->n; i++) t += fl->f[i].self;
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < fl->n; i++) t += fl->f[i].self; 25 10 35
149 10 return t;
150 }
151  
152 #endif /* PO_FLAME_H */
« xs/tenant.xs ↑ Summary include/punk_observe/po_shared.h »