tools/perf/util/hist.c

   1 #include "hist.h"
   2 #include "session.h"
   3 #include "sort.h"
   4
   5 struct callchain_param  callchain_param = {
   6         .mode   = CHAIN_GRAPH_REL,
   7         .min_percent = 0.5
   8 };
   9
  10 /*
  11  * histogram, sorted on item, collects counts
  12  */
  13
  14 struct hist_entry *__perf_session__add_hist_entry(struct perf_session *self,
  15                                                   struct addr_location *al,
  16                                                   struct symbol *sym_parent,
  17                                                   u64 count, bool *hit)
  18 {
  19         struct rb_node **p = &self->hists.rb_node;
  20         struct rb_node *parent = NULL;
  21         struct hist_entry *he;
  22         struct hist_entry entry = {
  23                 .thread = al->thread,
  24                 .map    = al->map,
  25                 .sym    = al->sym,
  26                 .ip     = al->addr,
  27                 .level  = al->level,
  28                 .count  = count,
  29                 .parent = sym_parent,
  30         };
  31         int cmp;
  32
  33         while (*p != NULL) {
  34                 parent = *p;
  35                 he = rb_entry(parent, struct hist_entry, rb_node);
  36
  37                 cmp = hist_entry__cmp(&entry, he);
  38
  39                 if (!cmp) {
  40                         *hit = true;
  41                         return he;
  42                 }
  43
  44                 if (cmp < 0)
  45                         p = &(*p)->rb_left;
  46                 else
  47                         p = &(*p)->rb_right;
  48         }
  49
  50         he = malloc(sizeof(*he));
  51         if (!he)
  52                 return NULL;
  53         *he = entry;
  54         rb_link_node(&he->rb_node, parent, p);
  55         rb_insert_color(&he->rb_node, &self->hists);
  56         *hit = false;
  57         return he;
  58 }
  59
  60 int64_t
  61 hist_entry__cmp(struct hist_entry *left, struct hist_entry *right)
  62 {
  63         struct sort_entry *se;
  64         int64_t cmp = 0;
  65
  66         list_for_each_entry(se, &hist_entry__sort_list, list) {
  67                 cmp = se->cmp(left, right);
  68                 if (cmp)
  69                         break;
  70         }
  71
  72         return cmp;
  73 }
  74
  75 int64_t
  76 hist_entry__collapse(struct hist_entry *left, struct hist_entry *right)
  77 {
  78         struct sort_entry *se;
  79         int64_t cmp = 0;
  80
  81         list_for_each_entry(se, &hist_entry__sort_list, list) {
  82                 int64_t (*f)(struct hist_entry *, struct hist_entry *);
  83
  84                 f = se->collapse ?: se->cmp;
  85
  86                 cmp = f(left, right);
  87                 if (cmp)
  88                         break;
  89         }
  90
  91         return cmp;
  92 }
  93
  94 void hist_entry__free(struct hist_entry *he)
  95 {
  96         free(he);
  97 }
  98
  99 /*
 100  * collapse the histogram
 101  */
 102
 103 static void collapse__insert_entry(struct rb_root *root, struct hist_entry *he)
 104 {
 105         struct rb_node **p = &root->rb_node;
 106         struct rb_node *parent = NULL;
 107         struct hist_entry *iter;
 108         int64_t cmp;
 109
 110         while (*p != NULL) {
 111                 parent = *p;
 112                 iter = rb_entry(parent, struct hist_entry, rb_node);
 113
 114                 cmp = hist_entry__collapse(iter, he);
 115
 116                 if (!cmp) {
 117                         iter->count += he->count;
 118                         hist_entry__free(he);
 119                         return;
 120                 }
 121
 122                 if (cmp < 0)
 123                         p = &(*p)->rb_left;
 124                 else
 125                         p = &(*p)->rb_right;
 126         }
 127
 128         rb_link_node(&he->rb_node, parent, p);
 129         rb_insert_color(&he->rb_node, root);
 130 }
 131
 132 void perf_session__collapse_resort(struct perf_session *self)
 133 {
 134         struct rb_root tmp;
 135         struct rb_node *next;
 136         struct hist_entry *n;
 137
 138         if (!sort__need_collapse)
 139                 return;
 140
 141         tmp = RB_ROOT;
 142         next = rb_first(&self->hists);
 143
 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, &self->hists);
 149                 collapse__insert_entry(&tmp, n);
 150         }
 151
 152         self->hists = tmp;
 153 }
 154
 155 /*
 156  * reverse the map, sort on count.
 157  */
 158
 159 static void perf_session__insert_output_hist_entry(struct perf_session *self,
 160                                                    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 (self->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
 186 void perf_session__output_resort(struct perf_session *self, 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(&self->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, &self->hists);
 204                 perf_session__insert_output_hist_entry(self, &tmp, n,
 205                                                        min_callchain_hits);
 206         }
 207
 208         self->hists = tmp;
 209 }