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