tools/perf/util/hist.c

   1 #include "hist.h"
   2
   3 struct rb_root hist;
   4 struct rb_root collapse_hists;
   5 struct rb_root output_hists;
   6 int callchain;
   7
   8 struct callchain_param  callchain_param = {
   9         .mode   = CHAIN_GRAPH_REL,
  10         .min_percent = 0.5
  11 };
  12
  13 /*
  14  * histogram, sorted on item, collects counts
  15  */
  16
  17 struct hist_entry *__hist_entry__add(struct addr_location *al,
  18                                      struct symbol *sym_parent,
  19                                      u64 count, bool *hit)
  20 {
  21         struct rb_node **p = &hist.rb_node;
  22         struct rb_node *parent = NULL;
  23         struct hist_entry *he;
  24         struct hist_entry entry = {
  25                 .thread = al->thread,
  26                 .map    = al->map,
  27                 .sym    = al->sym,
  28                 .ip     = al->addr,
  29                 .level  = al->level,
  30                 .count  = count,
  31                 .parent = sym_parent,
  32         };
  33         int cmp;
  34
  35         while (*p != NULL) {
  36                 parent = *p;
  37                 he = rb_entry(parent, struct hist_entry, rb_node);
  38
  39                 cmp = hist_entry__cmp(&entry, he);
  40
  41                 if (!cmp) {
  42                         *hit = true;
  43                         return he;
  44                 }
  45
  46                 if (cmp < 0)
  47                         p = &(*p)->rb_left;
  48                 else
  49                         p = &(*p)->rb_right;
  50         }
  51
  52         he = malloc(sizeof(*he));
  53         if (!he)
  54                 return NULL;
  55         *he = entry;
  56         rb_link_node(&he->rb_node, parent, p);
  57         rb_insert_color(&he->rb_node, &hist);
  58         *hit = false;
  59         return he;
  60 }
  61
  62 int64_t
  63 hist_entry__cmp(struct hist_entry *left, struct hist_entry *right)
  64 {
  65         struct sort_entry *se;
  66         int64_t cmp = 0;
  67
  68         list_for_each_entry(se, &hist_entry__sort_list, list) {
  69                 cmp = se->cmp(left, right);
  70                 if (cmp)
  71                         break;
  72         }
  73
  74         return cmp;
  75 }
  76
  77 int64_t
  78 hist_entry__collapse(struct hist_entry *left, struct hist_entry *right)
  79 {
  80         struct sort_entry *se;
  81         int64_t cmp = 0;
  82
  83         list_for_each_entry(se, &hist_entry__sort_list, list) {
  84                 int64_t (*f)(struct hist_entry *, struct hist_entry *);
  85
  86                 f = se->collapse ?: se->cmp;
  87
  88                 cmp = f(left, right);
  89                 if (cmp)
  90                         break;
  91         }
  92
  93         return cmp;
  94 }
  95
  96 void hist_entry__free(struct hist_entry *he)
  97 {
  98         free(he);
  99 }
 100
 101 /*
 102  * collapse the histogram
 103  */
 104
 105 void collapse__insert_entry(struct hist_entry *he)
 106 {
 107         struct rb_node **p = &collapse_hists.rb_node;
 108         struct rb_node *parent = NULL;
 109         struct hist_entry *iter;
 110         int64_t cmp;
 111
 112         while (*p != NULL) {
 113                 parent = *p;
 114                 iter = rb_entry(parent, struct hist_entry, rb_node);
 115
 116                 cmp = hist_entry__collapse(iter, he);
 117
 118                 if (!cmp) {
 119                         iter->count += he->count;
 120                         hist_entry__free(he);
 121                         return;
 122                 }
 123
 124                 if (cmp < 0)
 125                         p = &(*p)->rb_left;
 126                 else
 127                         p = &(*p)->rb_right;
 128         }
 129
 130         rb_link_node(&he->rb_node, parent, p);
 131         rb_insert_color(&he->rb_node, &collapse_hists);
 132 }
 133
 134 void collapse__resort(void)
 135 {
 136         struct rb_node *next;
 137         struct hist_entry *n;
 138
 139         if (!sort__need_collapse)
 140                 return;
 141
 142         next = rb_first(&hist);
 143         while (next) {
 144                 n = rb_entry(next, struct hist_entry, rb_node);
 145                 next = rb_next(&n->rb_node);
 146
 147                 rb_erase(&n->rb_node, &hist);
 148                 collapse__insert_entry(n);
 149         }
 150 }
 151
 152 /*
 153  * reverse the map, sort on count.
 154  */
 155
 156 void output__insert_entry(struct hist_entry *he, u64 min_callchain_hits)
 157 {
 158         struct rb_node **p = &output_hists.rb_node;
 159         struct rb_node *parent = NULL;
 160         struct hist_entry *iter;
 161
 162         if (callchain)
 163                 callchain_param.sort(&he->sorted_chain, &he->callchain,
 164                                       min_callchain_hits, &callchain_param);
 165
 166         while (*p != NULL) {
 167                 parent = *p;
 168                 iter = rb_entry(parent, struct hist_entry, rb_node);
 169
 170                 if (he->count > iter->count)
 171                         p = &(*p)->rb_left;
 172                 else
 173                         p = &(*p)->rb_right;
 174         }
 175
 176         rb_link_node(&he->rb_node, parent, p);
 177         rb_insert_color(&he->rb_node, &output_hists);
 178 }
 179
 180 void output__resort(u64 total_samples)
 181 {
 182         struct rb_node *next;
 183         struct hist_entry *n;
 184         struct rb_root *tree = &hist;
 185         u64 min_callchain_hits;
 186
 187         min_callchain_hits =
 188                 total_samples * (callchain_param.min_percent / 100);
 189
 190         if (sort__need_collapse)
 191                 tree = &collapse_hists;
 192
 193         next = rb_first(tree);
 194
 195         while (next) {
 196                 n = rb_entry(next, struct hist_entry, rb_node);
 197                 next = rb_next(&n->rb_node);
 198
 199                 rb_erase(&n->rb_node, tree);
 200                 output__insert_entry(n, min_callchain_hits);
 201         }
 202 }