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