| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| && fl->f[i].service_sym == service) return &fl->f[i]; |
18 |
0 |
18 |
|
| 58 |
25 |
▶ | if (fl->n == fl->cap) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| for (k = 0; k < n; k++) { |
107 |
43 |
150 |
|
| 125 |
107 |
▶ | if (t->parent[k] != (int32_t)i) continue; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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 */ |