Root/tools/perf/util/hist.c

1#include "hist.h"
2#include "session.h"
3#include "sort.h"
4#include <math.h>
5
6struct callchain_param callchain_param = {
7    .mode = CHAIN_GRAPH_REL,
8    .min_percent = 0.5
9};
10
11/*
12 * histogram, sorted on item, collects counts
13 */
14
15struct hist_entry *__perf_session__add_hist_entry(struct rb_root *hists,
16                          struct addr_location *al,
17                          struct symbol *sym_parent,
18                          u64 count, bool *hit)
19{
20    struct rb_node **p = &hists->rb_node;
21    struct rb_node *parent = NULL;
22    struct hist_entry *he;
23    struct hist_entry entry = {
24        .thread = al->thread,
25        .map = al->map,
26        .sym = al->sym,
27        .ip = al->addr,
28        .level = al->level,
29        .count = count,
30        .parent = sym_parent,
31    };
32    int cmp;
33
34    while (*p != NULL) {
35        parent = *p;
36        he = rb_entry(parent, struct hist_entry, rb_node);
37
38        cmp = hist_entry__cmp(&entry, he);
39
40        if (!cmp) {
41            *hit = true;
42            return he;
43        }
44
45        if (cmp < 0)
46            p = &(*p)->rb_left;
47        else
48            p = &(*p)->rb_right;
49    }
50
51    he = malloc(sizeof(*he));
52    if (!he)
53        return NULL;
54    *he = entry;
55    rb_link_node(&he->rb_node, parent, p);
56    rb_insert_color(&he->rb_node, hists);
57    *hit = false;
58    return he;
59}
60
61int64_t
62hist_entry__cmp(struct hist_entry *left, struct hist_entry *right)
63{
64    struct sort_entry *se;
65    int64_t cmp = 0;
66
67    list_for_each_entry(se, &hist_entry__sort_list, list) {
68        cmp = se->cmp(left, right);
69        if (cmp)
70            break;
71    }
72
73    return cmp;
74}
75
76int64_t
77hist_entry__collapse(struct hist_entry *left, struct hist_entry *right)
78{
79    struct sort_entry *se;
80    int64_t cmp = 0;
81
82    list_for_each_entry(se, &hist_entry__sort_list, list) {
83        int64_t (*f)(struct hist_entry *, struct hist_entry *);
84
85        f = se->collapse ?: se->cmp;
86
87        cmp = f(left, right);
88        if (cmp)
89            break;
90    }
91
92    return cmp;
93}
94
95void hist_entry__free(struct hist_entry *he)
96{
97    free(he);
98}
99
100/*
101 * collapse the histogram
102 */
103
104static void collapse__insert_entry(struct rb_root *root, struct hist_entry *he)
105{
106    struct rb_node **p = &root->rb_node;
107    struct rb_node *parent = NULL;
108    struct hist_entry *iter;
109    int64_t cmp;
110
111    while (*p != NULL) {
112        parent = *p;
113        iter = rb_entry(parent, struct hist_entry, rb_node);
114
115        cmp = hist_entry__collapse(iter, he);
116
117        if (!cmp) {
118            iter->count += he->count;
119            hist_entry__free(he);
120            return;
121        }
122
123        if (cmp < 0)
124            p = &(*p)->rb_left;
125        else
126            p = &(*p)->rb_right;
127    }
128
129    rb_link_node(&he->rb_node, parent, p);
130    rb_insert_color(&he->rb_node, root);
131}
132
133void perf_session__collapse_resort(struct rb_root *hists)
134{
135    struct rb_root tmp;
136    struct rb_node *next;
137    struct hist_entry *n;
138
139    if (!sort__need_collapse)
140        return;
141
142    tmp = RB_ROOT;
143    next = rb_first(hists);
144
145    while (next) {
146        n = rb_entry(next, struct hist_entry, rb_node);
147        next = rb_next(&n->rb_node);
148
149        rb_erase(&n->rb_node, hists);
150        collapse__insert_entry(&tmp, n);
151    }
152
153    *hists = tmp;
154}
155
156/*
157 * reverse the map, sort on count.
158 */
159
160static void perf_session__insert_output_hist_entry(struct rb_root *root,
161                           struct hist_entry *he,
162                           u64 min_callchain_hits)
163{
164    struct rb_node **p = &root->rb_node;
165    struct rb_node *parent = NULL;
166    struct hist_entry *iter;
167
168    if (symbol_conf.use_callchain)
169        callchain_param.sort(&he->sorted_chain, &he->callchain,
170                      min_callchain_hits, &callchain_param);
171
172    while (*p != NULL) {
173        parent = *p;
174        iter = rb_entry(parent, struct hist_entry, rb_node);
175
176        if (he->count > iter->count)
177            p = &(*p)->rb_left;
178        else
179            p = &(*p)->rb_right;
180    }
181
182    rb_link_node(&he->rb_node, parent, p);
183    rb_insert_color(&he->rb_node, root);
184}
185
186void perf_session__output_resort(struct rb_root *hists, u64 total_samples)
187{
188    struct rb_root tmp;
189    struct rb_node *next;
190    struct hist_entry *n;
191    u64 min_callchain_hits;
192
193    min_callchain_hits =
194        total_samples * (callchain_param.min_percent / 100);
195
196    tmp = RB_ROOT;
197    next = rb_first(hists);
198
199    while (next) {
200        n = rb_entry(next, struct hist_entry, rb_node);
201        next = rb_next(&n->rb_node);
202
203        rb_erase(&n->rb_node, hists);
204        perf_session__insert_output_hist_entry(&tmp, n,
205                               min_callchain_hits);
206    }
207
208    *hists = tmp;
209}
210
211static size_t callchain__fprintf_left_margin(FILE *fp, int left_margin)
212{
213    int i;
214    int ret = fprintf(fp, " ");
215
216    for (i = 0; i < left_margin; i++)
217        ret += fprintf(fp, " ");
218
219    return ret;
220}
221
222static size_t ipchain__fprintf_graph_line(FILE *fp, int depth, int depth_mask,
223                      int left_margin)
224{
225    int i;
226    size_t ret = callchain__fprintf_left_margin(fp, left_margin);
227
228    for (i = 0; i < depth; i++)
229        if (depth_mask & (1 << i))
230            ret += fprintf(fp, "| ");
231        else
232            ret += fprintf(fp, " ");
233
234    ret += fprintf(fp, "\n");
235
236    return ret;
237}
238
239static size_t ipchain__fprintf_graph(FILE *fp, struct callchain_list *chain,
240                     int depth, int depth_mask, int count,
241                     u64 total_samples, int hits,
242                     int left_margin)
243{
244    int i;
245    size_t ret = 0;
246
247    ret += callchain__fprintf_left_margin(fp, left_margin);
248    for (i = 0; i < depth; i++) {
249        if (depth_mask & (1 << i))
250            ret += fprintf(fp, "|");
251        else
252            ret += fprintf(fp, " ");
253        if (!count && i == depth - 1) {
254            double percent;
255
256            percent = hits * 100.0 / total_samples;
257            ret += percent_color_fprintf(fp, "--%2.2f%%-- ", percent);
258        } else
259            ret += fprintf(fp, "%s", " ");
260    }
261    if (chain->sym)
262        ret += fprintf(fp, "%s\n", chain->sym->name);
263    else
264        ret += fprintf(fp, "%p\n", (void *)(long)chain->ip);
265
266    return ret;
267}
268
269static struct symbol *rem_sq_bracket;
270static struct callchain_list rem_hits;
271
272static void init_rem_hits(void)
273{
274    rem_sq_bracket = malloc(sizeof(*rem_sq_bracket) + 6);
275    if (!rem_sq_bracket) {
276        fprintf(stderr, "Not enough memory to display remaining hits\n");
277        return;
278    }
279
280    strcpy(rem_sq_bracket->name, "[...]");
281    rem_hits.sym = rem_sq_bracket;
282}
283
284static size_t __callchain__fprintf_graph(FILE *fp, struct callchain_node *self,
285                     u64 total_samples, int depth,
286                     int depth_mask, int left_margin)
287{
288    struct rb_node *node, *next;
289    struct callchain_node *child;
290    struct callchain_list *chain;
291    int new_depth_mask = depth_mask;
292    u64 new_total;
293    u64 remaining;
294    size_t ret = 0;
295    int i;
296
297    if (callchain_param.mode == CHAIN_GRAPH_REL)
298        new_total = self->children_hit;
299    else
300        new_total = total_samples;
301
302    remaining = new_total;
303
304    node = rb_first(&self->rb_root);
305    while (node) {
306        u64 cumul;
307
308        child = rb_entry(node, struct callchain_node, rb_node);
309        cumul = cumul_hits(child);
310        remaining -= cumul;
311
312        /*
313         * The depth mask manages the output of pipes that show
314         * the depth. We don't want to keep the pipes of the current
315         * level for the last child of this depth.
316         * Except if we have remaining filtered hits. They will
317         * supersede the last child
318         */
319        next = rb_next(node);
320        if (!next && (callchain_param.mode != CHAIN_GRAPH_REL || !remaining))
321            new_depth_mask &= ~(1 << (depth - 1));
322
323        /*
324         * But we keep the older depth mask for the line separator
325         * to keep the level link until we reach the last child
326         */
327        ret += ipchain__fprintf_graph_line(fp, depth, depth_mask,
328                           left_margin);
329        i = 0;
330        list_for_each_entry(chain, &child->val, list) {
331            if (chain->ip >= PERF_CONTEXT_MAX)
332                continue;
333            ret += ipchain__fprintf_graph(fp, chain, depth,
334                              new_depth_mask, i++,
335                              new_total,
336                              cumul,
337                              left_margin);
338        }
339        ret += __callchain__fprintf_graph(fp, child, new_total,
340                          depth + 1,
341                          new_depth_mask | (1 << depth),
342                          left_margin);
343        node = next;
344    }
345
346    if (callchain_param.mode == CHAIN_GRAPH_REL &&
347        remaining && remaining != new_total) {
348
349        if (!rem_sq_bracket)
350            return ret;
351
352        new_depth_mask &= ~(1 << (depth - 1));
353
354        ret += ipchain__fprintf_graph(fp, &rem_hits, depth,
355                          new_depth_mask, 0, new_total,
356                          remaining, left_margin);
357    }
358
359    return ret;
360}
361
362static size_t callchain__fprintf_graph(FILE *fp, struct callchain_node *self,
363                       u64 total_samples, int left_margin)
364{
365    struct callchain_list *chain;
366    bool printed = false;
367    int i = 0;
368    int ret = 0;
369
370    list_for_each_entry(chain, &self->val, list) {
371        if (chain->ip >= PERF_CONTEXT_MAX)
372            continue;
373
374        if (!i++ && sort__first_dimension == SORT_SYM)
375            continue;
376
377        if (!printed) {
378            ret += callchain__fprintf_left_margin(fp, left_margin);
379            ret += fprintf(fp, "|\n");
380            ret += callchain__fprintf_left_margin(fp, left_margin);
381            ret += fprintf(fp, "---");
382
383            left_margin += 3;
384            printed = true;
385        } else
386            ret += callchain__fprintf_left_margin(fp, left_margin);
387
388        if (chain->sym)
389            ret += fprintf(fp, " %s\n", chain->sym->name);
390        else
391            ret += fprintf(fp, " %p\n", (void *)(long)chain->ip);
392    }
393
394    ret += __callchain__fprintf_graph(fp, self, total_samples, 1, 1, left_margin);
395
396    return ret;
397}
398
399static size_t callchain__fprintf_flat(FILE *fp, struct callchain_node *self,
400                      u64 total_samples)
401{
402    struct callchain_list *chain;
403    size_t ret = 0;
404
405    if (!self)
406        return 0;
407
408    ret += callchain__fprintf_flat(fp, self->parent, total_samples);
409
410
411    list_for_each_entry(chain, &self->val, list) {
412        if (chain->ip >= PERF_CONTEXT_MAX)
413            continue;
414        if (chain->sym)
415            ret += fprintf(fp, " %s\n", chain->sym->name);
416        else
417            ret += fprintf(fp, " %p\n",
418                    (void *)(long)chain->ip);
419    }
420
421    return ret;
422}
423
424static size_t hist_entry_callchain__fprintf(FILE *fp, struct hist_entry *self,
425                        u64 total_samples, int left_margin)
426{
427    struct rb_node *rb_node;
428    struct callchain_node *chain;
429    size_t ret = 0;
430
431    rb_node = rb_first(&self->sorted_chain);
432    while (rb_node) {
433        double percent;
434
435        chain = rb_entry(rb_node, struct callchain_node, rb_node);
436        percent = chain->hit * 100.0 / total_samples;
437        switch (callchain_param.mode) {
438        case CHAIN_FLAT:
439            ret += percent_color_fprintf(fp, " %6.2f%%\n",
440                             percent);
441            ret += callchain__fprintf_flat(fp, chain, total_samples);
442            break;
443        case CHAIN_GRAPH_ABS: /* Falldown */
444        case CHAIN_GRAPH_REL:
445            ret += callchain__fprintf_graph(fp, chain, total_samples,
446                            left_margin);
447        case CHAIN_NONE:
448        default:
449            break;
450        }
451        ret += fprintf(fp, "\n");
452        rb_node = rb_next(rb_node);
453    }
454
455    return ret;
456}
457
458static size_t hist_entry__fprintf(struct hist_entry *self,
459                  struct perf_session *pair_session,
460                  bool show_displacement,
461                  long displacement, FILE *fp,
462                  u64 session_total)
463{
464    struct sort_entry *se;
465    u64 count, total;
466    const char *sep = symbol_conf.field_sep;
467    size_t ret;
468
469    if (symbol_conf.exclude_other && !self->parent)
470        return 0;
471
472    if (pair_session) {
473        count = self->pair ? self->pair->count : 0;
474        total = pair_session->events_stats.total;
475    } else {
476        count = self->count;
477        total = session_total;
478    }
479
480    if (total)
481        ret = percent_color_fprintf(fp, sep ? "%.2f" : " %6.2f%%",
482                        (count * 100.0) / total);
483    else
484        ret = fprintf(fp, sep ? "%lld" : "%12lld ", count);
485
486    if (symbol_conf.show_nr_samples) {
487        if (sep)
488            fprintf(fp, "%c%lld", *sep, count);
489        else
490            fprintf(fp, "%11lld", count);
491    }
492
493    if (pair_session) {
494        char bf[32];
495        double old_percent = 0, new_percent = 0, diff;
496
497        if (total > 0)
498            old_percent = (count * 100.0) / total;
499        if (session_total > 0)
500            new_percent = (self->count * 100.0) / session_total;
501
502        diff = new_percent - old_percent;
503
504        if (fabs(diff) >= 0.01)
505            snprintf(bf, sizeof(bf), "%+4.2F%%", diff);
506        else
507            snprintf(bf, sizeof(bf), " ");
508
509        if (sep)
510            ret += fprintf(fp, "%c%s", *sep, bf);
511        else
512            ret += fprintf(fp, "%11.11s", bf);
513
514        if (show_displacement) {
515            if (displacement)
516                snprintf(bf, sizeof(bf), "%+4ld", displacement);
517            else
518                snprintf(bf, sizeof(bf), " ");
519
520            if (sep)
521                fprintf(fp, "%c%s", *sep, bf);
522            else
523                fprintf(fp, "%6.6s", bf);
524        }
525    }
526
527    list_for_each_entry(se, &hist_entry__sort_list, list) {
528        if (se->elide)
529            continue;
530
531        fprintf(fp, "%s", sep ?: " ");
532        ret += se->print(fp, self, se->width ? *se->width : 0);
533    }
534
535    ret += fprintf(fp, "\n");
536
537    if (symbol_conf.use_callchain) {
538        int left_margin = 0;
539
540        if (sort__first_dimension == SORT_COMM) {
541            se = list_first_entry(&hist_entry__sort_list, typeof(*se),
542                        list);
543            left_margin = se->width ? *se->width : 0;
544            left_margin -= thread__comm_len(self->thread);
545        }
546
547        hist_entry_callchain__fprintf(fp, self, session_total,
548                          left_margin);
549    }
550
551    return ret;
552}
553
554size_t perf_session__fprintf_hists(struct rb_root *hists,
555                   struct perf_session *pair,
556                   bool show_displacement, FILE *fp,
557                   u64 session_total)
558{
559    struct sort_entry *se;
560    struct rb_node *nd;
561    size_t ret = 0;
562    unsigned long position = 1;
563    long displacement = 0;
564    unsigned int width;
565    const char *sep = symbol_conf.field_sep;
566    char *col_width = symbol_conf.col_width_list_str;
567
568    init_rem_hits();
569
570    fprintf(fp, "# %s", pair ? "Baseline" : "Overhead");
571
572    if (symbol_conf.show_nr_samples) {
573        if (sep)
574            fprintf(fp, "%cSamples", *sep);
575        else
576            fputs(" Samples ", fp);
577    }
578
579    if (pair) {
580        if (sep)
581            ret += fprintf(fp, "%cDelta", *sep);
582        else
583            ret += fprintf(fp, " Delta ");
584
585        if (show_displacement) {
586            if (sep)
587                ret += fprintf(fp, "%cDisplacement", *sep);
588            else
589                ret += fprintf(fp, " Displ");
590        }
591    }
592
593    list_for_each_entry(se, &hist_entry__sort_list, list) {
594        if (se->elide)
595            continue;
596        if (sep) {
597            fprintf(fp, "%c%s", *sep, se->header);
598            continue;
599        }
600        width = strlen(se->header);
601        if (se->width) {
602            if (symbol_conf.col_width_list_str) {
603                if (col_width) {
604                    *se->width = atoi(col_width);
605                    col_width = strchr(col_width, ',');
606                    if (col_width)
607                        ++col_width;
608                }
609            }
610            width = *se->width = max(*se->width, width);
611        }
612        fprintf(fp, " %*s", width, se->header);
613    }
614    fprintf(fp, "\n");
615
616    if (sep)
617        goto print_entries;
618
619    fprintf(fp, "# ........");
620    if (symbol_conf.show_nr_samples)
621        fprintf(fp, " ..........");
622    if (pair) {
623        fprintf(fp, " ..........");
624        if (show_displacement)
625            fprintf(fp, " .....");
626    }
627    list_for_each_entry(se, &hist_entry__sort_list, list) {
628        unsigned int i;
629
630        if (se->elide)
631            continue;
632
633        fprintf(fp, " ");
634        if (se->width)
635            width = *se->width;
636        else
637            width = strlen(se->header);
638        for (i = 0; i < width; i++)
639            fprintf(fp, ".");
640    }
641
642    fprintf(fp, "\n#\n");
643
644print_entries:
645    for (nd = rb_first(hists); nd; nd = rb_next(nd)) {
646        struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
647
648        if (show_displacement) {
649            if (h->pair != NULL)
650                displacement = ((long)h->pair->position -
651                            (long)position);
652            else
653                displacement = 0;
654            ++position;
655        }
656        ret += hist_entry__fprintf(h, pair, show_displacement,
657                       displacement, fp, session_total);
658        if (h->map == NULL && verbose > 1) {
659            __map_groups__fprintf_maps(&h->thread->mg,
660                           MAP__FUNCTION, fp);
661            fprintf(fp, "%.10s end\n", graph_dotted_line);
662        }
663    }
664
665    free(rem_sq_bracket);
666
667    return ret;
668}
669

Archive Download this file



interactive