tools/perf/util/hist.c

   1 // SPDX-License-Identifier: GPL-2.0
   2 #include "callchain.h"
   3 #include "util.h"
   4 #include "build-id.h"
   5 #include "hist.h"
   6 #include "map.h"
   7 #include "session.h"
   8 #include "namespaces.h"
   9 #include "sort.h"
  10 #include "units.h"
  11 #include "evlist.h"
  12 #include "evsel.h"
  13 #include "annotate.h"
  14 #include "srcline.h"
  15 #include "symbol.h"
  16 #include "thread.h"
  17 #include "ui/progress.h"
  18 #include <errno.h>
  19 #include <math.h>
  20 #include <inttypes.h>
  21 #include <sys/param.h>
  22
  23 static bool hists__filter_entry_by_dso(struct hists *hists,
  24                                        struct hist_entry *he);
  25 static bool hists__filter_entry_by_thread(struct hists *hists,
  26                                           struct hist_entry *he);
  27 static bool hists__filter_entry_by_symbol(struct hists *hists,
  28                                           struct hist_entry *he);
  29 static bool hists__filter_entry_by_socket(struct hists *hists,
  30                                           struct hist_entry *he);
  31
  32 u16 hists__col_len(struct hists *hists, enum hist_column col)
  33 {
  34         return hists->col_len[col];
  35 }
  36
  37 void hists__set_col_len(struct hists *hists, enum hist_column col, u16 len)
  38 {
  39         hists->col_len[col] = len;
  40 }
  41
  42 bool hists__new_col_len(struct hists *hists, enum hist_column col, u16 len)
  43 {
  44         if (len > hists__col_len(hists, col)) {
  45                 hists__set_col_len(hists, col, len);
  46                 return true;
  47         }
  48         return false;
  49 }
  50
  51 void hists__reset_col_len(struct hists *hists)
  52 {
  53         enum hist_column col;
  54
  55         for (col = 0; col < HISTC_NR_COLS; ++col)
  56                 hists__set_col_len(hists, col, 0);
  57 }
  58
  59 static void hists__set_unres_dso_col_len(struct hists *hists, int dso)
  60 {
  61         const unsigned int unresolved_col_width = BITS_PER_LONG / 4;
  62
  63         if (hists__col_len(hists, dso) < unresolved_col_width &&
  64             !symbol_conf.col_width_list_str && !symbol_conf.field_sep &&
  65             !symbol_conf.dso_list)
  66                 hists__set_col_len(hists, dso, unresolved_col_width);
  67 }
  68
  69 void hists__calc_col_len(struct hists *hists, struct hist_entry *h)
  70 {
  71         const unsigned int unresolved_col_width = BITS_PER_LONG / 4;
  72         int symlen;
  73         u16 len;
  74
  75         /*
  76          * +4 accounts for '[x] ' priv level info
  77          * +2 accounts for 0x prefix on raw addresses
  78          * +3 accounts for ' y ' symtab origin info
  79          */
  80         if (h->ms.sym) {
  81                 symlen = h->ms.sym->namelen + 4;
  82                 if (verbose > 0)
  83                         symlen += BITS_PER_LONG / 4 + 2 + 3;
  84                 hists__new_col_len(hists, HISTC_SYMBOL, symlen);
  85         } else {
  86                 symlen = unresolved_col_width + 4 + 2;
  87                 hists__new_col_len(hists, HISTC_SYMBOL, symlen);
  88                 hists__set_unres_dso_col_len(hists, HISTC_DSO);
  89         }
  90
  91         len = thread__comm_len(h->thread);
  92         if (hists__new_col_len(hists, HISTC_COMM, len))
  93                 hists__set_col_len(hists, HISTC_THREAD, len + 8);
  94
  95         if (h->ms.map) {
  96                 len = dso__name_len(h->ms.map->dso);
  97                 hists__new_col_len(hists, HISTC_DSO, len);
  98         }
  99
 100         if (h->parent)
 101                 hists__new_col_len(hists, HISTC_PARENT, h->parent->namelen);
 102
 103         if (h->branch_info) {
 104                 if (h->branch_info->from.sym) {
 105                         symlen = (int)h->branch_info->from.sym->namelen + 4;
 106                         if (verbose > 0)
 107                                 symlen += BITS_PER_LONG / 4 + 2 + 3;
 108                         hists__new_col_len(hists, HISTC_SYMBOL_FROM, symlen);
 109
 110                         symlen = dso__name_len(h->branch_info->from.map->dso);
 111                         hists__new_col_len(hists, HISTC_DSO_FROM, symlen);
 112                 } else {
 113                         symlen = unresolved_col_width + 4 + 2;
 114                         hists__new_col_len(hists, HISTC_SYMBOL_FROM, symlen);
 115                         hists__set_unres_dso_col_len(hists, HISTC_DSO_FROM);
 116                 }
 117
 118                 if (h->branch_info->to.sym) {
 119                         symlen = (int)h->branch_info->to.sym->namelen + 4;
 120                         if (verbose > 0)
 121                                 symlen += BITS_PER_LONG / 4 + 2 + 3;
 122                         hists__new_col_len(hists, HISTC_SYMBOL_TO, symlen);
 123
 124                         symlen = dso__name_len(h->branch_info->to.map->dso);
 125                         hists__new_col_len(hists, HISTC_DSO_TO, symlen);
 126                 } else {
 127                         symlen = unresolved_col_width + 4 + 2;
 128                         hists__new_col_len(hists, HISTC_SYMBOL_TO, symlen);
 129                         hists__set_unres_dso_col_len(hists, HISTC_DSO_TO);
 130                 }
 131
 132                 if (h->branch_info->srcline_from)
 133                         hists__new_col_len(hists, HISTC_SRCLINE_FROM,
 134                                         strlen(h->branch_info->srcline_from));
 135                 if (h->branch_info->srcline_to)
 136                         hists__new_col_len(hists, HISTC_SRCLINE_TO,
 137                                         strlen(h->branch_info->srcline_to));
 138         }
 139
 140         if (h->mem_info) {
 141                 if (h->mem_info->daddr.sym) {
 142                         symlen = (int)h->mem_info->daddr.sym->namelen + 4
 143                                + unresolved_col_width + 2;
 144                         hists__new_col_len(hists, HISTC_MEM_DADDR_SYMBOL,
 145                                            symlen);
 146                         hists__new_col_len(hists, HISTC_MEM_DCACHELINE,
 147                                            symlen + 1);
 148                 } else {
 149                         symlen = unresolved_col_width + 4 + 2;
 150                         hists__new_col_len(hists, HISTC_MEM_DADDR_SYMBOL,
 151                                            symlen);
 152                         hists__new_col_len(hists, HISTC_MEM_DCACHELINE,
 153                                            symlen);
 154                 }
 155
 156                 if (h->mem_info->iaddr.sym) {
 157                         symlen = (int)h->mem_info->iaddr.sym->namelen + 4
 158                                + unresolved_col_width + 2;
 159                         hists__new_col_len(hists, HISTC_MEM_IADDR_SYMBOL,
 160                                            symlen);
 161                 } else {
 162                         symlen = unresolved_col_width + 4 + 2;
 163                         hists__new_col_len(hists, HISTC_MEM_IADDR_SYMBOL,
 164                                            symlen);
 165                 }
 166
 167                 if (h->mem_info->daddr.map) {
 168                         symlen = dso__name_len(h->mem_info->daddr.map->dso);
 169                         hists__new_col_len(hists, HISTC_MEM_DADDR_DSO,
 170                                            symlen);
 171                 } else {
 172                         symlen = unresolved_col_width + 4 + 2;
 173                         hists__set_unres_dso_col_len(hists, HISTC_MEM_DADDR_DSO);
 174                 }
 175
 176                 hists__new_col_len(hists, HISTC_MEM_PHYS_DADDR,
 177                                    unresolved_col_width + 4 + 2);
 178
 179         } else {
 180                 symlen = unresolved_col_width + 4 + 2;
 181                 hists__new_col_len(hists, HISTC_MEM_DADDR_SYMBOL, symlen);
 182                 hists__new_col_len(hists, HISTC_MEM_IADDR_SYMBOL, symlen);
 183                 hists__set_unres_dso_col_len(hists, HISTC_MEM_DADDR_DSO);
 184         }
 185
 186         hists__new_col_len(hists, HISTC_CGROUP_ID, 20);
 187         hists__new_col_len(hists, HISTC_CPU, 3);
 188         hists__new_col_len(hists, HISTC_SOCKET, 6);
 189         hists__new_col_len(hists, HISTC_MEM_LOCKED, 6);
 190         hists__new_col_len(hists, HISTC_MEM_TLB, 22);
 191         hists__new_col_len(hists, HISTC_MEM_SNOOP, 12);
 192         hists__new_col_len(hists, HISTC_MEM_LVL, 21 + 3);
 193         hists__new_col_len(hists, HISTC_LOCAL_WEIGHT, 12);
 194         hists__new_col_len(hists, HISTC_GLOBAL_WEIGHT, 12);
 195
 196         if (h->srcline) {
 197                 len = MAX(strlen(h->srcline), strlen(sort_srcline.se_header));
 198                 hists__new_col_len(hists, HISTC_SRCLINE, len);
 199         }
 200
 201         if (h->srcfile)
 202                 hists__new_col_len(hists, HISTC_SRCFILE, strlen(h->srcfile));
 203
 204         if (h->transaction)
 205                 hists__new_col_len(hists, HISTC_TRANSACTION,
 206                                    hist_entry__transaction_len());
 207
 208         if (h->trace_output)
 209                 hists__new_col_len(hists, HISTC_TRACE, strlen(h->trace_output));
 210 }
 211
 212 void hists__output_recalc_col_len(struct hists *hists, int max_rows)
 213 {
 214         struct rb_node *next = rb_first_cached(&hists->entries);
 215         struct hist_entry *n;
 216         int row = 0;
 217
 218         hists__reset_col_len(hists);
 219
 220         while (next && row++ < max_rows) {
 221                 n = rb_entry(next, struct hist_entry, rb_node);
 222                 if (!n->filtered)
 223                         hists__calc_col_len(hists, n);
 224                 next = rb_next(&n->rb_node);
 225         }
 226 }
 227
 228 static void he_stat__add_cpumode_period(struct he_stat *he_stat,
 229                                         unsigned int cpumode, u64 period)
 230 {
 231         switch (cpumode) {
 232         case PERF_RECORD_MISC_KERNEL:
 233                 he_stat->period_sys += period;
 234                 break;
 235         case PERF_RECORD_MISC_USER:
 236                 he_stat->period_us += period;
 237                 break;
 238         case PERF_RECORD_MISC_GUEST_KERNEL:
 239                 he_stat->period_guest_sys += period;
 240                 break;
 241         case PERF_RECORD_MISC_GUEST_USER:
 242                 he_stat->period_guest_us += period;
 243                 break;
 244         default:
 245                 break;
 246         }
 247 }
 248
 249 static void he_stat__add_period(struct he_stat *he_stat, u64 period,
 250                                 u64 weight)
 251 {
 252
 253         he_stat->period         += period;
 254         he_stat->weight         += weight;
 255         he_stat->nr_events      += 1;
 256 }
 257
 258 static void he_stat__add_stat(struct he_stat *dest, struct he_stat *src)
 259 {
 260         dest->period            += src->period;
 261         dest->period_sys        += src->period_sys;
 262         dest->period_us         += src->period_us;
 263         dest->period_guest_sys  += src->period_guest_sys;
 264         dest->period_guest_us   += src->period_guest_us;
 265         dest->nr_events         += src->nr_events;
 266         dest->weight            += src->weight;
 267 }
 268
 269 static void he_stat__decay(struct he_stat *he_stat)
 270 {
 271         he_stat->period = (he_stat->period * 7) / 8;
 272         he_stat->nr_events = (he_stat->nr_events * 7) / 8;
 273         /* XXX need decay for weight too? */
 274 }
 275
 276 static void hists__delete_entry(struct hists *hists, struct hist_entry *he);
 277
 278 static bool hists__decay_entry(struct hists *hists, struct hist_entry *he)
 279 {
 280         u64 prev_period = he->stat.period;
 281         u64 diff;
 282
 283         if (prev_period == 0)
 284                 return true;
 285
 286         he_stat__decay(&he->stat);
 287         if (symbol_conf.cumulate_callchain)
 288                 he_stat__decay(he->stat_acc);
 289         decay_callchain(he->callchain);
 290
 291         diff = prev_period - he->stat.period;
 292
 293         if (!he->depth) {
 294                 hists->stats.total_period -= diff;
 295                 if (!he->filtered)
 296                         hists->stats.total_non_filtered_period -= diff;
 297         }
 298
 299         if (!he->leaf) {
 300                 struct hist_entry *child;
 301                 struct rb_node *node = rb_first_cached(&he->hroot_out);
 302                 while (node) {
 303                         child = rb_entry(node, struct hist_entry, rb_node);
 304                         node = rb_next(node);
 305
 306                         if (hists__decay_entry(hists, child))
 307                                 hists__delete_entry(hists, child);
 308                 }
 309         }
 310
 311         return he->stat.period == 0;
 312 }
 313
 314 static void hists__delete_entry(struct hists *hists, struct hist_entry *he)
 315 {
 316         struct rb_root_cached *root_in;
 317         struct rb_root_cached *root_out;
 318
 319         if (he->parent_he) {
 320                 root_in  = &he->parent_he->hroot_in;
 321                 root_out = &he->parent_he->hroot_out;
 322         } else {
 323                 if (hists__has(hists, need_collapse))
 324                         root_in = &hists->entries_collapsed;
 325                 else
 326                         root_in = hists->entries_in;
 327                 root_out = &hists->entries;
 328         }
 329
 330         rb_erase_cached(&he->rb_node_in, root_in);
 331         rb_erase_cached(&he->rb_node, root_out);
 332
 333         --hists->nr_entries;
 334         if (!he->filtered)
 335                 --hists->nr_non_filtered_entries;
 336
 337         hist_entry__delete(he);
 338 }
 339
 340 void hists__decay_entries(struct hists *hists, bool zap_user, bool zap_kernel)
 341 {
 342         struct rb_node *next = rb_first_cached(&hists->entries);
 343         struct hist_entry *n;
 344
 345         while (next) {
 346                 n = rb_entry(next, struct hist_entry, rb_node);
 347                 next = rb_next(&n->rb_node);
 348                 if (((zap_user && n->level == '.') ||
 349                      (zap_kernel && n->level != '.') ||
 350                      hists__decay_entry(hists, n))) {
 351                         hists__delete_entry(hists, n);
 352                 }
 353         }
 354 }
 355
 356 void hists__delete_entries(struct hists *hists)
 357 {
 358         struct rb_node *next = rb_first_cached(&hists->entries);
 359         struct hist_entry *n;
 360
 361         while (next) {
 362                 n = rb_entry(next, struct hist_entry, rb_node);
 363                 next = rb_next(&n->rb_node);
 364
 365                 hists__delete_entry(hists, n);
 366         }
 367 }
 368
 369 /*
 370  * histogram, sorted on item, collects periods
 371  */
 372
 373 static int hist_entry__init(struct hist_entry *he,
 374                             struct hist_entry *template,
 375                             bool sample_self,
 376                             size_t callchain_size)
 377 {
 378         *he = *template;
 379         he->callchain_size = callchain_size;
 380
 381         if (symbol_conf.cumulate_callchain) {
 382                 he->stat_acc = malloc(sizeof(he->stat));
 383                 if (he->stat_acc == NULL)
 384                         return -ENOMEM;
 385                 memcpy(he->stat_acc, &he->stat, sizeof(he->stat));
 386                 if (!sample_self)
 387                         memset(&he->stat, 0, sizeof(he->stat));
 388         }
 389
 390         map__get(he->ms.map);
 391
 392         if (he->branch_info) {
 393                 /*
 394                  * This branch info is (a part of) allocated from
 395                  * sample__resolve_bstack() and will be freed after
 396                  * adding new entries.  So we need to save a copy.
 397                  */
 398                 he->branch_info = malloc(sizeof(*he->branch_info));
 399                 if (he->branch_info == NULL)
 400                         goto err;
 401
 402                 memcpy(he->branch_info, template->branch_info,
 403                        sizeof(*he->branch_info));
 404
 405                 map__get(he->branch_info->from.map);
 406                 map__get(he->branch_info->to.map);
 407         }
 408
 409         if (he->mem_info) {
 410                 map__get(he->mem_info->iaddr.map);
 411                 map__get(he->mem_info->daddr.map);
 412         }
 413
 414         if (hist_entry__has_callchains(he) && symbol_conf.use_callchain)
 415                 callchain_init(he->callchain);
 416
 417         if (he->raw_data) {
 418                 he->raw_data = memdup(he->raw_data, he->raw_size);
 419                 if (he->raw_data == NULL)
 420                         goto err_infos;
 421         }
 422         INIT_LIST_HEAD(&he->pairs.node);
 423         thread__get(he->thread);
 424         he->hroot_in  = RB_ROOT_CACHED;
 425         he->hroot_out = RB_ROOT_CACHED;
 426
 427         if (!symbol_conf.report_hierarchy)
 428                 he->leaf = true;
 429
 430         return 0;
 431
 432 err_infos:
 433         if (he->branch_info) {
 434                 map__put(he->branch_info->from.map);
 435                 map__put(he->branch_info->to.map);
 436                 free(he->branch_info);
 437         }
 438         if (he->mem_info) {
 439                 map__put(he->mem_info->iaddr.map);
 440                 map__put(he->mem_info->daddr.map);
 441         }
 442 err:
 443         map__zput(he->ms.map);
 444         free(he->stat_acc);
 445         return -ENOMEM;
 446 }
 447
 448 static void *hist_entry__zalloc(size_t size)
 449 {
 450         return zalloc(size + sizeof(struct hist_entry));
 451 }
 452
 453 static void hist_entry__free(void *ptr)
 454 {
 455         free(ptr);
 456 }
 457
 458 static struct hist_entry_ops default_ops = {
 459         .new    = hist_entry__zalloc,
 460         .free   = hist_entry__free,
 461 };
 462
 463 static struct hist_entry *hist_entry__new(struct hist_entry *template,
 464                                           bool sample_self)
 465 {
 466         struct hist_entry_ops *ops = template->ops;
 467         size_t callchain_size = 0;
 468         struct hist_entry *he;
 469         int err = 0;
 470
 471         if (!ops)
 472                 ops = template->ops = &default_ops;
 473
 474         if (symbol_conf.use_callchain)
 475                 callchain_size = sizeof(struct callchain_root);
 476
 477         he = ops->new(callchain_size);
 478         if (he) {
 479                 err = hist_entry__init(he, template, sample_self, callchain_size);
 480                 if (err) {
 481                         ops->free(he);
 482                         he = NULL;
 483                 }
 484         }
 485
 486         return he;
 487 }
 488
 489 static u8 symbol__parent_filter(const struct symbol *parent)
 490 {
 491         if (symbol_conf.exclude_other && parent == NULL)
 492                 return 1 << HIST_FILTER__PARENT;
 493         return 0;
 494 }
 495
 496 static void hist_entry__add_callchain_period(struct hist_entry *he, u64 period)
 497 {
 498         if (!hist_entry__has_callchains(he) || !symbol_conf.use_callchain)
 499                 return;
 500
 501         he->hists->callchain_period += period;
 502         if (!he->filtered)
 503                 he->hists->callchain_non_filtered_period += period;
 504 }
 505
 506 static struct hist_entry *hists__findnew_entry(struct hists *hists,
 507                                                struct hist_entry *entry,
 508                                                struct addr_location *al,
 509                                                bool sample_self)
 510 {
 511         struct rb_node **p;
 512         struct rb_node *parent = NULL;
 513         struct hist_entry *he;
 514         int64_t cmp;
 515         u64 period = entry->stat.period;
 516         u64 weight = entry->stat.weight;
 517         bool leftmost = true;
 518
 519         p = &hists->entries_in->rb_root.rb_node;
 520
 521         while (*p != NULL) {
 522                 parent = *p;
 523                 he = rb_entry(parent, struct hist_entry, rb_node_in);
 524
 525                 /*
 526                  * Make sure that it receives arguments in a same order as
 527                  * hist_entry__collapse() so that we can use an appropriate
 528                  * function when searching an entry regardless which sort
 529                  * keys were used.
 530                  */
 531                 cmp = hist_entry__cmp(he, entry);
 532
 533                 if (!cmp) {
 534                         if (sample_self) {
 535                                 he_stat__add_period(&he->stat, period, weight);
 536                                 hist_entry__add_callchain_period(he, period);
 537                         }
 538                         if (symbol_conf.cumulate_callchain)
 539                                 he_stat__add_period(he->stat_acc, period, weight);
 540
 541                         /*
 542                          * This mem info was allocated from sample__resolve_mem
 543                          * and will not be used anymore.
 544                          */
 545                         mem_info__zput(entry->mem_info);
 546
 547                         /* If the map of an existing hist_entry has
 548                          * become out-of-date due to an exec() or
 549                          * similar, update it.  Otherwise we will
 550                          * mis-adjust symbol addresses when computing
 551                          * the history counter to increment.
 552                          */
 553                         if (he->ms.map != entry->ms.map) {
 554                                 map__put(he->ms.map);
 555                                 he->ms.map = map__get(entry->ms.map);
 556                         }
 557                         goto out;
 558                 }
 559
 560                 if (cmp < 0)
 561                         p = &(*p)->rb_left;
 562                 else {
 563                         p = &(*p)->rb_right;
 564                         leftmost = false;
 565                 }
 566         }
 567
 568         he = hist_entry__new(entry, sample_self);
 569         if (!he)
 570                 return NULL;
 571
 572         if (sample_self)
 573                 hist_entry__add_callchain_period(he, period);
 574         hists->nr_entries++;
 575
 576         rb_link_node(&he->rb_node_in, parent, p);
 577         rb_insert_color_cached(&he->rb_node_in, hists->entries_in, leftmost);
 578 out:
 579         if (sample_self)
 580                 he_stat__add_cpumode_period(&he->stat, al->cpumode, period);
 581         if (symbol_conf.cumulate_callchain)
 582                 he_stat__add_cpumode_period(he->stat_acc, al->cpumode, period);
 583         return he;
 584 }
 585
 586 static struct hist_entry*
 587 __hists__add_entry(struct hists *hists,
 588                    struct addr_location *al,
 589                    struct symbol *sym_parent,
 590                    struct branch_info *bi,
 591                    struct mem_info *mi,
 592                    struct perf_sample *sample,
 593                    bool sample_self,
 594                    struct hist_entry_ops *ops)
 595 {
 596         struct namespaces *ns = thread__namespaces(al->thread);
 597         struct hist_entry entry = {
 598                 .thread = al->thread,
 599                 .comm = thread__comm(al->thread),
 600                 .cgroup_id = {
 601                         .dev = ns ? ns->link_info[CGROUP_NS_INDEX].dev : 0,
 602                         .ino = ns ? ns->link_info[CGROUP_NS_INDEX].ino : 0,
 603                 },
 604                 .ms = {
 605                         .map    = al->map,
 606                         .sym    = al->sym,
 607                 },
 608                 .srcline = al->srcline ? strdup(al->srcline) : NULL,
 609                 .socket  = al->socket,
 610                 .cpu     = al->cpu,
 611                 .cpumode = al->cpumode,
 612                 .ip      = al->addr,
 613                 .level   = al->level,
 614                 .stat = {
 615                         .nr_events = 1,
 616                         .period = sample->period,
 617                         .weight = sample->weight,
 618                 },
 619                 .parent = sym_parent,
 620                 .filtered = symbol__parent_filter(sym_parent) | al->filtered,
 621                 .hists  = hists,
 622                 .branch_info = bi,
 623                 .mem_info = mi,
 624                 .transaction = sample->transaction,
 625                 .raw_data = sample->raw_data,
 626                 .raw_size = sample->raw_size,
 627                 .ops = ops,
 628         }, *he = hists__findnew_entry(hists, &entry, al, sample_self);
 629
 630         if (!hists->has_callchains && he && he->callchain_size != 0)
 631                 hists->has_callchains = true;
 632         return he;
 633 }
 634
 635 struct hist_entry *hists__add_entry(struct hists *hists,
 636                                     struct addr_location *al,
 637                                     struct symbol *sym_parent,
 638                                     struct branch_info *bi,
 639                                     struct mem_info *mi,
 640                                     struct perf_sample *sample,
 641                                     bool sample_self)
 642 {
 643         return __hists__add_entry(hists, al, sym_parent, bi, mi,
 644                                   sample, sample_self, NULL);
 645 }
 646
 647 struct hist_entry *hists__add_entry_ops(struct hists *hists,
 648                                         struct hist_entry_ops *ops,
 649                                         struct addr_location *al,
 650                                         struct symbol *sym_parent,
 651                                         struct branch_info *bi,
 652                                         struct mem_info *mi,
 653                                         struct perf_sample *sample,
 654                                         bool sample_self)
 655 {
 656         return __hists__add_entry(hists, al, sym_parent, bi, mi,
 657                                   sample, sample_self, ops);
 658 }
 659
 660 static int
 661 iter_next_nop_entry(struct hist_entry_iter *iter __maybe_unused,
 662                     struct addr_location *al __maybe_unused)
 663 {
 664         return 0;
 665 }
 666
 667 static int
 668 iter_add_next_nop_entry(struct hist_entry_iter *iter __maybe_unused,
 669                         struct addr_location *al __maybe_unused)
 670 {
 671         return 0;
 672 }
 673
 674 static int
 675 iter_prepare_mem_entry(struct hist_entry_iter *iter, struct addr_location *al)
 676 {
 677         struct perf_sample *sample = iter->sample;
 678         struct mem_info *mi;
 679
 680         mi = sample__resolve_mem(sample, al);
 681         if (mi == NULL)
 682                 return -ENOMEM;
 683
 684         iter->priv = mi;
 685         return 0;
 686 }
 687
 688 static int
 689 iter_add_single_mem_entry(struct hist_entry_iter *iter, struct addr_location *al)
 690 {
 691         u64 cost;
 692         struct mem_info *mi = iter->priv;
 693         struct hists *hists = evsel__hists(iter->evsel);
 694         struct perf_sample *sample = iter->sample;
 695         struct hist_entry *he;
 696
 697         if (mi == NULL)
 698                 return -EINVAL;
 699
 700         cost = sample->weight;
 701         if (!cost)
 702                 cost = 1;
 703
 704         /*
 705          * must pass period=weight in order to get the correct
 706          * sorting from hists__collapse_resort() which is solely
 707          * based on periods. We want sorting be done on nr_events * weight
 708          * and this is indirectly achieved by passing period=weight here
 709          * and the he_stat__add_period() function.
 710          */
 711         sample->period = cost;
 712
 713         he = hists__add_entry(hists, al, iter->parent, NULL, mi,
 714                               sample, true);
 715         if (!he)
 716                 return -ENOMEM;
 717
 718         iter->he = he;
 719         return 0;
 720 }
 721
 722 static int
 723 iter_finish_mem_entry(struct hist_entry_iter *iter,
 724                       struct addr_location *al __maybe_unused)
 725 {
 726         struct perf_evsel *evsel = iter->evsel;
 727         struct hists *hists = evsel__hists(evsel);
 728         struct hist_entry *he = iter->he;
 729         int err = -EINVAL;
 730
 731         if (he == NULL)
 732                 goto out;
 733
 734         hists__inc_nr_samples(hists, he->filtered);
 735
 736         err = hist_entry__append_callchain(he, iter->sample);
 737
 738 out:
 739         /*
 740          * We don't need to free iter->priv (mem_info) here since the mem info
 741          * was either already freed in hists__findnew_entry() or passed to a
 742          * new hist entry by hist_entry__new().
 743          */
 744         iter->priv = NULL;
 745
 746         iter->he = NULL;
 747         return err;
 748 }
 749
 750 static int
 751 iter_prepare_branch_entry(struct hist_entry_iter *iter, struct addr_location *al)
 752 {
 753         struct branch_info *bi;
 754         struct perf_sample *sample = iter->sample;
 755
 756         bi = sample__resolve_bstack(sample, al);
 757         if (!bi)
 758                 return -ENOMEM;
 759
 760         iter->curr = 0;
 761         iter->total = sample->branch_stack->nr;
 762
 763         iter->priv = bi;
 764         return 0;
 765 }
 766
 767 static int
 768 iter_add_single_branch_entry(struct hist_entry_iter *iter __maybe_unused,
 769                              struct addr_location *al __maybe_unused)
 770 {
 771         return 0;
 772 }
 773
 774 static int
 775 iter_next_branch_entry(struct hist_entry_iter *iter, struct addr_location *al)
 776 {
 777         struct branch_info *bi = iter->priv;
 778         int i = iter->curr;
 779
 780         if (bi == NULL)
 781                 return 0;
 782
 783         if (iter->curr >= iter->total)
 784                 return 0;
 785
 786         al->map = bi[i].to.map;
 787         al->sym = bi[i].to.sym;
 788         al->addr = bi[i].to.addr;
 789         return 1;
 790 }
 791
 792 static int
 793 iter_add_next_branch_entry(struct hist_entry_iter *iter, struct addr_location *al)
 794 {
 795         struct branch_info *bi;
 796         struct perf_evsel *evsel = iter->evsel;
 797         struct hists *hists = evsel__hists(evsel);
 798         struct perf_sample *sample = iter->sample;
 799         struct hist_entry *he = NULL;
 800         int i = iter->curr;
 801         int err = 0;
 802
 803         bi = iter->priv;
 804
 805         if (iter->hide_unresolved && !(bi[i].from.sym && bi[i].to.sym))
 806                 goto out;
 807
 808         /*
 809          * The report shows the percentage of total branches captured
 810          * and not events sampled. Thus we use a pseudo period of 1.
 811          */
 812         sample->period = 1;
 813         sample->weight = bi->flags.cycles ? bi->flags.cycles : 1;
 814
 815         he = hists__add_entry(hists, al, iter->parent, &bi[i], NULL,
 816                               sample, true);
 817         if (he == NULL)
 818                 return -ENOMEM;
 819
 820         hists__inc_nr_samples(hists, he->filtered);
 821
 822 out:
 823         iter->he = he;
 824         iter->curr++;
 825         return err;
 826 }
 827
 828 static int
 829 iter_finish_branch_entry(struct hist_entry_iter *iter,
 830                          struct addr_location *al __maybe_unused)
 831 {
 832         zfree(&iter->priv);
 833         iter->he = NULL;
 834
 835         return iter->curr >= iter->total ? 0 : -1;
 836 }
 837
 838 static int
 839 iter_prepare_normal_entry(struct hist_entry_iter *iter __maybe_unused,
 840                           struct addr_location *al __maybe_unused)
 841 {
 842         return 0;
 843 }
 844
 845 static int
 846 iter_add_single_normal_entry(struct hist_entry_iter *iter, struct addr_location *al)
 847 {
 848         struct perf_evsel *evsel = iter->evsel;
 849         struct perf_sample *sample = iter->sample;
 850         struct hist_entry *he;
 851
 852         he = hists__add_entry(evsel__hists(evsel), al, iter->parent, NULL, NULL,
 853                               sample, true);
 854         if (he == NULL)
 855                 return -ENOMEM;
 856
 857         iter->he = he;
 858         return 0;
 859 }
 860
 861 static int
 862 iter_finish_normal_entry(struct hist_entry_iter *iter,
 863                          struct addr_location *al __maybe_unused)
 864 {
 865         struct hist_entry *he = iter->he;
 866         struct perf_evsel *evsel = iter->evsel;
 867         struct perf_sample *sample = iter->sample;
 868
 869         if (he == NULL)
 870                 return 0;
 871
 872         iter->he = NULL;
 873
 874         hists__inc_nr_samples(evsel__hists(evsel), he->filtered);
 875
 876         return hist_entry__append_callchain(he, sample);
 877 }
 878
 879 static int
 880 iter_prepare_cumulative_entry(struct hist_entry_iter *iter,
 881                               struct addr_location *al __maybe_unused)
 882 {
 883         struct hist_entry **he_cache;
 884
 885         callchain_cursor_commit(&callchain_cursor);
 886
 887         /*
 888          * This is for detecting cycles or recursions so that they're
 889          * cumulated only one time to prevent entries more than 100%
 890          * overhead.
 891          */
 892         he_cache = malloc(sizeof(*he_cache) * (callchain_cursor.nr + 1));
 893         if (he_cache == NULL)
 894                 return -ENOMEM;
 895
 896         iter->priv = he_cache;
 897         iter->curr = 0;
 898
 899         return 0;
 900 }
 901
 902 static int
 903 iter_add_single_cumulative_entry(struct hist_entry_iter *iter,
 904                                  struct addr_location *al)
 905 {
 906         struct perf_evsel *evsel = iter->evsel;
 907         struct hists *hists = evsel__hists(evsel);
 908         struct perf_sample *sample = iter->sample;
 909         struct hist_entry **he_cache = iter->priv;
 910         struct hist_entry *he;
 911         int err = 0;
 912
 913         he = hists__add_entry(hists, al, iter->parent, NULL, NULL,
 914                               sample, true);
 915         if (he == NULL)
 916                 return -ENOMEM;
 917
 918         iter->he = he;
 919         he_cache[iter->curr++] = he;
 920
 921         hist_entry__append_callchain(he, sample);
 922
 923         /*
 924          * We need to re-initialize the cursor since callchain_append()
 925          * advanced the cursor to the end.
 926          */
 927         callchain_cursor_commit(&callchain_cursor);
 928
 929         hists__inc_nr_samples(hists, he->filtered);
 930
 931         return err;
 932 }
 933
 934 static int
 935 iter_next_cumulative_entry(struct hist_entry_iter *iter,
 936                            struct addr_location *al)
 937 {
 938         struct callchain_cursor_node *node;
 939
 940         node = callchain_cursor_current(&callchain_cursor);
 941         if (node == NULL)
 942                 return 0;
 943
 944         return fill_callchain_info(al, node, iter->hide_unresolved);
 945 }
 946
 947 static int
 948 iter_add_next_cumulative_entry(struct hist_entry_iter *iter,
 949                                struct addr_location *al)
 950 {
 951         struct perf_evsel *evsel = iter->evsel;
 952         struct perf_sample *sample = iter->sample;
 953         struct hist_entry **he_cache = iter->priv;
 954         struct hist_entry *he;
 955         struct hist_entry he_tmp = {
 956                 .hists = evsel__hists(evsel),
 957                 .cpu = al->cpu,
 958                 .thread = al->thread,
 959                 .comm = thread__comm(al->thread),
 960                 .ip = al->addr,
 961                 .ms = {
 962                         .map = al->map,
 963                         .sym = al->sym,
 964                 },
 965                 .srcline = al->srcline ? strdup(al->srcline) : NULL,
 966                 .parent = iter->parent,
 967                 .raw_data = sample->raw_data,
 968                 .raw_size = sample->raw_size,
 969         };
 970         int i;
 971         struct callchain_cursor cursor;
 972
 973         callchain_cursor_snapshot(&cursor, &callchain_cursor);
 974
 975         callchain_cursor_advance(&callchain_cursor);
 976
 977         /*
 978          * Check if there's duplicate entries in the callchain.
 979          * It's possible that it has cycles or recursive calls.
 980          */
 981         for (i = 0; i < iter->curr; i++) {
 982                 if (hist_entry__cmp(he_cache[i], &he_tmp) == 0) {
 983                         /* to avoid calling callback function */
 984                         iter->he = NULL;
 985                         return 0;
 986                 }
 987         }
 988
 989         he = hists__add_entry(evsel__hists(evsel), al, iter->parent, NULL, NULL,
 990                               sample, false);
 991         if (he == NULL)
 992                 return -ENOMEM;
 993
 994         iter->he = he;
 995         he_cache[iter->curr++] = he;
 996
 997         if (hist_entry__has_callchains(he) && symbol_conf.use_callchain)
 998                 callchain_append(he->callchain, &cursor, sample->period);
 999         return 0;
1000 }
1001
1002 static int
1003 iter_finish_cumulative_entry(struct hist_entry_iter *iter,
1004                              struct addr_location *al __maybe_unused)
1005 {
1006         zfree(&iter->priv);
1007         iter->he = NULL;
1008
1009         return 0;
1010 }
1011
1012 const struct hist_iter_ops hist_iter_mem = {
1013         .prepare_entry          = iter_prepare_mem_entry,
1014         .add_single_entry       = iter_add_single_mem_entry,
1015         .next_entry             = iter_next_nop_entry,
1016         .add_next_entry         = iter_add_next_nop_entry,
1017         .finish_entry           = iter_finish_mem_entry,
1018 };
1019
1020 const struct hist_iter_ops hist_iter_branch = {
1021         .prepare_entry          = iter_prepare_branch_entry,
1022         .add_single_entry       = iter_add_single_branch_entry,
1023         .next_entry             = iter_next_branch_entry,
1024         .add_next_entry         = iter_add_next_branch_entry,
1025         .finish_entry           = iter_finish_branch_entry,
1026 };
1027
1028 const struct hist_iter_ops hist_iter_normal = {
1029         .prepare_entry          = iter_prepare_normal_entry,
1030         .add_single_entry       = iter_add_single_normal_entry,
1031         .next_entry             = iter_next_nop_entry,
1032         .add_next_entry         = iter_add_next_nop_entry,
1033         .finish_entry           = iter_finish_normal_entry,
1034 };
1035
1036 const struct hist_iter_ops hist_iter_cumulative = {
1037         .prepare_entry          = iter_prepare_cumulative_entry,
1038         .add_single_entry       = iter_add_single_cumulative_entry,
1039         .next_entry             = iter_next_cumulative_entry,
1040         .add_next_entry         = iter_add_next_cumulative_entry,
1041         .finish_entry           = iter_finish_cumulative_entry,
1042 };
1043
1044 int hist_entry_iter__add(struct hist_entry_iter *iter, struct addr_location *al,
1045                          int max_stack_depth, void *arg)
1046 {
1047         int err, err2;
1048         struct map *alm = NULL;
1049
1050         if (al)
1051                 alm = map__get(al->map);
1052
1053         err = sample__resolve_callchain(iter->sample, &callchain_cursor, &iter->parent,
1054                                         iter->evsel, al, max_stack_depth);
1055         if (err)
1056                 return err;
1057
1058         err = iter->ops->prepare_entry(iter, al);
1059         if (err)
1060                 goto out;
1061
1062         err = iter->ops->add_single_entry(iter, al);
1063         if (err)
1064                 goto out;
1065
1066         if (iter->he && iter->add_entry_cb) {
1067                 err = iter->add_entry_cb(iter, al, true, arg);
1068                 if (err)
1069                         goto out;
1070         }
1071
1072         while (iter->ops->next_entry(iter, al)) {
1073                 err = iter->ops->add_next_entry(iter, al);
1074                 if (err)
1075                         break;
1076
1077                 if (iter->he && iter->add_entry_cb) {
1078                         err = iter->add_entry_cb(iter, al, false, arg);
1079                         if (err)
1080                                 goto out;
1081                 }
1082         }
1083
1084 out:
1085         err2 = iter->ops->finish_entry(iter, al);
1086         if (!err)
1087                 err = err2;
1088
1089         map__put(alm);
1090
1091         return err;
1092 }
1093
1094 int64_t
1095 hist_entry__cmp(struct hist_entry *left, struct hist_entry *right)
1096 {
1097         struct hists *hists = left->hists;
1098         struct perf_hpp_fmt *fmt;
1099         int64_t cmp = 0;
1100
1101         hists__for_each_sort_list(hists, fmt) {
1102                 if (perf_hpp__is_dynamic_entry(fmt) &&
1103                     !perf_hpp__defined_dynamic_entry(fmt, hists))
1104                         continue;
1105
1106                 cmp = fmt->cmp(fmt, left, right);
1107                 if (cmp)
1108                         break;
1109         }
1110
1111         return cmp;
1112 }
1113
1114 int64_t
1115 hist_entry__collapse(struct hist_entry *left, struct hist_entry *right)
1116 {
1117         struct hists *hists = left->hists;
1118         struct perf_hpp_fmt *fmt;
1119         int64_t cmp = 0;
1120
1121         hists__for_each_sort_list(hists, fmt) {
1122                 if (perf_hpp__is_dynamic_entry(fmt) &&
1123                     !perf_hpp__defined_dynamic_entry(fmt, hists))
1124                         continue;
1125
1126                 cmp = fmt->collapse(fmt, left, right);
1127                 if (cmp)
1128                         break;
1129         }
1130
1131         return cmp;
1132 }
1133
1134 void hist_entry__delete(struct hist_entry *he)
1135 {
1136         struct hist_entry_ops *ops = he->ops;
1137
1138         thread__zput(he->thread);
1139         map__zput(he->ms.map);
1140
1141         if (he->branch_info) {
1142                 map__zput(he->branch_info->from.map);
1143                 map__zput(he->branch_info->to.map);
1144                 free_srcline(he->branch_info->srcline_from);
1145                 free_srcline(he->branch_info->srcline_to);
1146                 zfree(&he->branch_info);
1147         }
1148
1149         if (he->mem_info) {
1150                 map__zput(he->mem_info->iaddr.map);
1151                 map__zput(he->mem_info->daddr.map);
1152                 mem_info__zput(he->mem_info);
1153         }
1154
1155         zfree(&he->stat_acc);
1156         free_srcline(he->srcline);
1157         if (he->srcfile && he->srcfile[0])
1158                 free(he->srcfile);
1159         free_callchain(he->callchain);
1160         free(he->trace_output);
1161         free(he->raw_data);
1162         ops->free(he);
1163 }
1164
1165 /*
1166  * If this is not the last column, then we need to pad it according to the
1167  * pre-calculated max length for this column, otherwise don't bother adding
1168  * spaces because that would break viewing this with, for instance, 'less',
1169  * that would show tons of trailing spaces when a long C++ demangled method
1170  * names is sampled.
1171 */
1172 int hist_entry__snprintf_alignment(struct hist_entry *he, struct perf_hpp *hpp,
1173                                    struct perf_hpp_fmt *fmt, int printed)
1174 {
1175         if (!list_is_last(&fmt->list, &he->hists->hpp_list->fields)) {
1176                 const int width = fmt->width(fmt, hpp, he->hists);
1177                 if (printed < width) {
1178                         advance_hpp(hpp, printed);
1179                         printed = scnprintf(hpp->buf, hpp->size, "%-*s", width - printed, " ");
1180                 }
1181         }
1182
1183         return printed;
1184 }
1185
1186 /*
1187  * collapse the histogram
1188  */
1189
1190 static void hists__apply_filters(struct hists *hists, struct hist_entry *he);
1191 static void hists__remove_entry_filter(struct hists *hists, struct hist_entry *he,
1192                                        enum hist_filter type);
1193
1194 typedef bool (*fmt_chk_fn)(struct perf_hpp_fmt *fmt);
1195
1196 static bool check_thread_entry(struct perf_hpp_fmt *fmt)
1197 {
1198         return perf_hpp__is_thread_entry(fmt) || perf_hpp__is_comm_entry(fmt);
1199 }
1200
1201 static void hist_entry__check_and_remove_filter(struct hist_entry *he,
1202                                                 enum hist_filter type,
1203                                                 fmt_chk_fn check)
1204 {
1205         struct perf_hpp_fmt *fmt;
1206         bool type_match = false;
1207         struct hist_entry *parent = he->parent_he;
1208
1209         switch (type) {
1210         case HIST_FILTER__THREAD:
1211                 if (symbol_conf.comm_list == NULL &&
1212                     symbol_conf.pid_list == NULL &&
1213                     symbol_conf.tid_list == NULL)
1214                         return;
1215                 break;
1216         case HIST_FILTER__DSO:
1217                 if (symbol_conf.dso_list == NULL)
1218                         return;
1219                 break;
1220         case HIST_FILTER__SYMBOL:
1221                 if (symbol_conf.sym_list == NULL)
1222                         return;
1223                 break;
1224         case HIST_FILTER__PARENT:
1225         case HIST_FILTER__GUEST:
1226         case HIST_FILTER__HOST:
1227         case HIST_FILTER__SOCKET:
1228         case HIST_FILTER__C2C:
1229         default:
1230                 return;
1231         }
1232
1233         /* if it's filtered by own fmt, it has to have filter bits */
1234         perf_hpp_list__for_each_format(he->hpp_list, fmt) {
1235                 if (check(fmt)) {
1236                         type_match = true;
1237                         break;
1238                 }
1239         }
1240
1241         if (type_match) {
1242                 /*
1243                  * If the filter is for current level entry, propagate
1244                  * filter marker to parents.  The marker bit was
1245                  * already set by default so it only needs to clear
1246                  * non-filtered entries.
1247                  */
1248                 if (!(he->filtered & (1 << type))) {
1249                         while (parent) {
1250                                 parent->filtered &= ~(1 << type);
1251                                 parent = parent->parent_he;
1252                         }
1253                 }
1254         } else {
1255                 /*
1256                  * If current entry doesn't have matching formats, set
1257                  * filter marker for upper level entries.  it will be
1258                  * cleared if its lower level entries is not filtered.
1259                  *
1260                  * For lower-level entries, it inherits parent's
1261                  * filter bit so that lower level entries of a
1262                  * non-filtered entry won't set the filter marker.
1263                  */
1264                 if (parent == NULL)
1265                         he->filtered |= (1 << type);
1266                 else
1267                         he->filtered |= (parent->filtered & (1 << type));
1268         }
1269 }
1270
1271 static void hist_entry__apply_hierarchy_filters(struct hist_entry *he)
1272 {
1273         hist_entry__check_and_remove_filter(he, HIST_FILTER__THREAD,
1274                                             check_thread_entry);
1275
1276         hist_entry__check_and_remove_filter(he, HIST_FILTER__DSO,
1277                                             perf_hpp__is_dso_entry);
1278
1279         hist_entry__check_and_remove_filter(he, HIST_FILTER__SYMBOL,
1280                                             perf_hpp__is_sym_entry);
1281
1282         hists__apply_filters(he->hists, he);
1283 }
1284
1285 static struct hist_entry *hierarchy_insert_entry(struct hists *hists,
1286                                                  struct rb_root_cached *root,
1287                                                  struct hist_entry *he,
1288                                                  struct hist_entry *parent_he,
1289                                                  struct perf_hpp_list *hpp_list)
1290 {
1291         struct rb_node **p = &root->rb_root.rb_node;
1292         struct rb_node *parent = NULL;
1293         struct hist_entry *iter, *new;
1294         struct perf_hpp_fmt *fmt;
1295         int64_t cmp;
1296         bool leftmost = true;
1297
1298         while (*p != NULL) {
1299                 parent = *p;
1300                 iter = rb_entry(parent, struct hist_entry, rb_node_in);
1301
1302                 cmp = 0;
1303                 perf_hpp_list__for_each_sort_list(hpp_list, fmt) {
1304                         cmp = fmt->collapse(fmt, iter, he);
1305                         if (cmp)
1306                                 break;
1307                 }
1308
1309                 if (!cmp) {
1310                         he_stat__add_stat(&iter->stat, &he->stat);
1311                         return iter;
1312                 }
1313
1314                 if (cmp < 0)
1315                         p = &parent->rb_left;
1316                 else {
1317                         p = &parent->rb_right;
1318                         leftmost = false;
1319                 }
1320         }
1321
1322         new = hist_entry__new(he, true);
1323         if (new == NULL)
1324                 return NULL;
1325
1326         hists->nr_entries++;
1327
1328         /* save related format list for output */
1329         new->hpp_list = hpp_list;
1330         new->parent_he = parent_he;
1331
1332         hist_entry__apply_hierarchy_filters(new);
1333
1334         /* some fields are now passed to 'new' */
1335         perf_hpp_list__for_each_sort_list(hpp_list, fmt) {
1336                 if (perf_hpp__is_trace_entry(fmt) || perf_hpp__is_dynamic_entry(fmt))
1337                         he->trace_output = NULL;
1338                 else
1339                         new->trace_output = NULL;
1340
1341                 if (perf_hpp__is_srcline_entry(fmt))
1342                         he->srcline = NULL;
1343                 else
1344                         new->srcline = NULL;
1345
1346                 if (perf_hpp__is_srcfile_entry(fmt))
1347                         he->srcfile = NULL;
1348                 else
1349                         new->srcfile = NULL;
1350         }
1351
1352         rb_link_node(&new->rb_node_in, parent, p);
1353         rb_insert_color_cached(&new->rb_node_in, root, leftmost);
1354         return new;
1355 }
1356
1357 static int hists__hierarchy_insert_entry(struct hists *hists,
1358                                          struct rb_root_cached *root,
1359                                          struct hist_entry *he)
1360 {
1361         struct perf_hpp_list_node *node;
1362         struct hist_entry *new_he = NULL;
1363         struct hist_entry *parent = NULL;
1364         int depth = 0;
1365         int ret = 0;
1366
1367         list_for_each_entry(node, &hists->hpp_formats, list) {
1368                 /* skip period (overhead) and elided columns */
1369                 if (node->level == 0 || node->skip)
1370                         continue;
1371
1372                 /* insert copy of 'he' for each fmt into the hierarchy */
1373                 new_he = hierarchy_insert_entry(hists, root, he, parent, &node->hpp);
1374                 if (new_he == NULL) {
1375                         ret = -1;
1376                         break;
1377                 }
1378
1379                 root = &new_he->hroot_in;
1380                 new_he->depth = depth++;
1381                 parent = new_he;
1382         }
1383
1384         if (new_he) {
1385                 new_he->leaf = true;
1386
1387                 if (hist_entry__has_callchains(new_he) &&
1388                     symbol_conf.use_callchain) {
1389                         callchain_cursor_reset(&callchain_cursor);
1390                         if (callchain_merge(&callchain_cursor,
1391                                             new_he->callchain,
1392                                             he->callchain) < 0)
1393                                 ret = -1;
1394                 }
1395         }
1396
1397         /* 'he' is no longer used */
1398         hist_entry__delete(he);
1399
1400         /* return 0 (or -1) since it already applied filters */
1401         return ret;
1402 }
1403
1404 static int hists__collapse_insert_entry(struct hists *hists,
1405                                         struct rb_root_cached *root,
1406                                         struct hist_entry *he)
1407 {
1408         struct rb_node **p = &root->rb_root.rb_node;
1409         struct rb_node *parent = NULL;
1410         struct hist_entry *iter;
1411         int64_t cmp;
1412         bool leftmost = true;
1413
1414         if (symbol_conf.report_hierarchy)
1415                 return hists__hierarchy_insert_entry(hists, root, he);
1416
1417         while (*p != NULL) {
1418                 parent = *p;
1419                 iter = rb_entry(parent, struct hist_entry, rb_node_in);
1420
1421                 cmp = hist_entry__collapse(iter, he);
1422
1423                 if (!cmp) {
1424                         int ret = 0;
1425
1426                         he_stat__add_stat(&iter->stat, &he->stat);
1427                         if (symbol_conf.cumulate_callchain)
1428                                 he_stat__add_stat(iter->stat_acc, he->stat_acc);
1429
1430                         if (hist_entry__has_callchains(he) && symbol_conf.use_callchain) {
1431                                 callchain_cursor_reset(&callchain_cursor);
1432                                 if (callchain_merge(&callchain_cursor,
1433                                                     iter->callchain,
1434                                                     he->callchain) < 0)
1435                                         ret = -1;
1436                         }
1437                         hist_entry__delete(he);
1438                         return ret;
1439                 }
1440
1441                 if (cmp < 0)
1442                         p = &(*p)->rb_left;
1443                 else {
1444                         p = &(*p)->rb_right;
1445                         leftmost = false;
1446                 }
1447         }
1448         hists->nr_entries++;
1449
1450         rb_link_node(&he->rb_node_in, parent, p);
1451         rb_insert_color_cached(&he->rb_node_in, root, leftmost);
1452         return 1;
1453 }
1454
1455 struct rb_root_cached *hists__get_rotate_entries_in(struct hists *hists)
1456 {
1457         struct rb_root_cached *root;
1458
1459         pthread_mutex_lock(&hists->lock);
1460
1461         root = hists->entries_in;
1462         if (++hists->entries_in > &hists->entries_in_array[1])
1463                 hists->entries_in = &hists->entries_in_array[0];
1464
1465         pthread_mutex_unlock(&hists->lock);
1466
1467         return root;
1468 }
1469
1470 static void hists__apply_filters(struct hists *hists, struct hist_entry *he)
1471 {
1472         hists__filter_entry_by_dso(hists, he);
1473         hists__filter_entry_by_thread(hists, he);
1474         hists__filter_entry_by_symbol(hists, he);
1475         hists__filter_entry_by_socket(hists, he);
1476 }
1477
1478 int hists__collapse_resort(struct hists *hists, struct ui_progress *prog)
1479 {
1480         struct rb_root_cached *root;
1481         struct rb_node *next;
1482         struct hist_entry *n;
1483         int ret;
1484
1485         if (!hists__has(hists, need_collapse))
1486                 return 0;
1487
1488         hists->nr_entries = 0;
1489
1490         root = hists__get_rotate_entries_in(hists);
1491
1492         next = rb_first_cached(root);
1493
1494         while (next) {
1495                 if (session_done())
1496                         break;
1497                 n = rb_entry(next, struct hist_entry, rb_node_in);
1498                 next = rb_next(&n->rb_node_in);
1499
1500                 rb_erase_cached(&n->rb_node_in, root);
1501                 ret = hists__collapse_insert_entry(hists, &hists->entries_collapsed, n);
1502                 if (ret < 0)
1503                         return -1;
1504
1505                 if (ret) {
1506                         /*
1507                          * If it wasn't combined with one of the entries already
1508                          * collapsed, we need to apply the filters that may have
1509                          * been set by, say, the hist_browser.
1510                          */
1511                         hists__apply_filters(hists, n);
1512                 }
1513                 if (prog)
1514                         ui_progress__update(prog, 1);
1515         }
1516         return 0;
1517 }
1518
1519 static int hist_entry__sort(struct hist_entry *a, struct hist_entry *b)
1520 {
1521         struct hists *hists = a->hists;
1522         struct perf_hpp_fmt *fmt;
1523         int64_t cmp = 0;
1524
1525         hists__for_each_sort_list(hists, fmt) {
1526                 if (perf_hpp__should_skip(fmt, a->hists))
1527                         continue;
1528
1529                 cmp = fmt->sort(fmt, a, b);
1530                 if (cmp)
1531                         break;
1532         }
1533
1534         return cmp;
1535 }
1536
1537 static void hists__reset_filter_stats(struct hists *hists)
1538 {
1539         hists->nr_non_filtered_entries = 0;
1540         hists->stats.total_non_filtered_period = 0;
1541 }
1542
1543 void hists__reset_stats(struct hists *hists)
1544 {
1545         hists->nr_entries = 0;
1546         hists->stats.total_period = 0;
1547
1548         hists__reset_filter_stats(hists);
1549 }
1550
1551 static void hists__inc_filter_stats(struct hists *hists, struct hist_entry *h)
1552 {
1553         hists->nr_non_filtered_entries++;
1554         hists->stats.total_non_filtered_period += h->stat.period;
1555 }
1556
1557 void hists__inc_stats(struct hists *hists, struct hist_entry *h)
1558 {
1559         if (!h->filtered)
1560                 hists__inc_filter_stats(hists, h);
1561
1562         hists->nr_entries++;
1563         hists->stats.total_period += h->stat.period;
1564 }
1565
1566 static void hierarchy_recalc_total_periods(struct hists *hists)
1567 {
1568         struct rb_node *node;
1569         struct hist_entry *he;
1570
1571         node = rb_first_cached(&hists->entries);
1572
1573         hists->stats.total_period = 0;
1574         hists->stats.total_non_filtered_period = 0;
1575
1576         /*
1577          * recalculate total period using top-level entries only
1578          * since lower level entries only see non-filtered entries
1579          * but upper level entries have sum of both entries.
1580          */
1581         while (node) {
1582                 he = rb_entry(node, struct hist_entry, rb_node);
1583                 node = rb_next(node);
1584
1585                 hists->stats.total_period += he->stat.period;
1586                 if (!he->filtered)
1587                         hists->stats.total_non_filtered_period += he->stat.period;
1588         }
1589 }
1590
1591 static void hierarchy_insert_output_entry(struct rb_root_cached *root,
1592                                           struct hist_entry *he)
1593 {
1594         struct rb_node **p = &root->rb_root.rb_node;
1595         struct rb_node *parent = NULL;
1596         struct hist_entry *iter;
1597         struct perf_hpp_fmt *fmt;
1598         bool leftmost = true;
1599
1600         while (*p != NULL) {
1601                 parent = *p;
1602                 iter = rb_entry(parent, struct hist_entry, rb_node);
1603
1604                 if (hist_entry__sort(he, iter) > 0)
1605                         p = &parent->rb_left;
1606                 else {
1607                         p = &parent->rb_right;
1608                         leftmost = false;
1609                 }
1610         }
1611
1612         rb_link_node(&he->rb_node, parent, p);
1613         rb_insert_color_cached(&he->rb_node, root, leftmost);
1614
1615         /* update column width of dynamic entry */
1616         perf_hpp_list__for_each_sort_list(he->hpp_list, fmt) {
1617                 if (perf_hpp__is_dynamic_entry(fmt))
1618                         fmt->sort(fmt, he, NULL);
1619         }
1620 }
1621
1622 static void hists__hierarchy_output_resort(struct hists *hists,
1623                                            struct ui_progress *prog,
1624                                            struct rb_root_cached *root_in,
1625                                            struct rb_root_cached *root_out,
1626                                            u64 min_callchain_hits,
1627                                            bool use_callchain)
1628 {
1629         struct rb_node *node;
1630         struct hist_entry *he;
1631
1632         *root_out = RB_ROOT_CACHED;
1633         node = rb_first_cached(root_in);
1634
1635         while (node) {
1636                 he = rb_entry(node, struct hist_entry, rb_node_in);
1637                 node = rb_next(node);
1638
1639                 hierarchy_insert_output_entry(root_out, he);
1640
1641                 if (prog)
1642                         ui_progress__update(prog, 1);
1643
1644                 hists->nr_entries++;
1645                 if (!he->filtered) {
1646                         hists->nr_non_filtered_entries++;
1647                         hists__calc_col_len(hists, he);
1648                 }
1649
1650                 if (!he->leaf) {
1651                         hists__hierarchy_output_resort(hists, prog,
1652                                                        &he->hroot_in,
1653                                                        &he->hroot_out,
1654                                                        min_callchain_hits,
1655                                                        use_callchain);
1656                         continue;
1657                 }
1658
1659                 if (!use_callchain)
1660                         continue;
1661
1662                 if (callchain_param.mode == CHAIN_GRAPH_REL) {
1663                         u64 total = he->stat.period;
1664
1665                         if (symbol_conf.cumulate_callchain)
1666                                 total = he->stat_acc->period;
1667
1668                         min_callchain_hits = total * (callchain_param.min_percent / 100);
1669                 }
1670
1671                 callchain_param.sort(&he->sorted_chain, he->callchain,
1672                                      min_callchain_hits, &callchain_param);
1673         }
1674 }
1675
1676 static void __hists__insert_output_entry(struct rb_root_cached *entries,
1677                                          struct hist_entry *he,
1678                                          u64 min_callchain_hits,
1679                                          bool use_callchain)
1680 {
1681         struct rb_node **p = &entries->rb_root.rb_node;
1682         struct rb_node *parent = NULL;
1683         struct hist_entry *iter;
1684         struct perf_hpp_fmt *fmt;
1685         bool leftmost = true;
1686
1687         if (use_callchain) {
1688                 if (callchain_param.mode == CHAIN_GRAPH_REL) {
1689                         u64 total = he->stat.period;
1690
1691                         if (symbol_conf.cumulate_callchain)
1692                                 total = he->stat_acc->period;
1693
1694                         min_callchain_hits = total * (callchain_param.min_percent / 100);
1695                 }
1696                 callchain_param.sort(&he->sorted_chain, he->callchain,
1697                                       min_callchain_hits, &callchain_param);
1698         }
1699
1700         while (*p != NULL) {
1701                 parent = *p;
1702                 iter = rb_entry(parent, struct hist_entry, rb_node);
1703
1704                 if (hist_entry__sort(he, iter) > 0)
1705                         p = &(*p)->rb_left;
1706                 else {
1707                         p = &(*p)->rb_right;
1708                         leftmost = false;
1709                 }
1710         }
1711
1712         rb_link_node(&he->rb_node, parent, p);
1713         rb_insert_color_cached(&he->rb_node, entries, leftmost);
1714
1715         perf_hpp_list__for_each_sort_list(&perf_hpp_list, fmt) {
1716                 if (perf_hpp__is_dynamic_entry(fmt) &&
1717                     perf_hpp__defined_dynamic_entry(fmt, he->hists))
1718                         fmt->sort(fmt, he, NULL);  /* update column width */
1719         }
1720 }
1721
1722 static void output_resort(struct hists *hists, struct ui_progress *prog,
1723                           bool use_callchain, hists__resort_cb_t cb,
1724                           void *cb_arg)
1725 {
1726         struct rb_root_cached *root;
1727         struct rb_node *next;
1728         struct hist_entry *n;
1729         u64 callchain_total;
1730         u64 min_callchain_hits;
1731
1732         callchain_total = hists->callchain_period;
1733         if (symbol_conf.filter_relative)
1734                 callchain_total = hists->callchain_non_filtered_period;
1735
1736         min_callchain_hits = callchain_total * (callchain_param.min_percent / 100);
1737
1738         hists__reset_stats(hists);
1739         hists__reset_col_len(hists);
1740
1741         if (symbol_conf.report_hierarchy) {
1742                 hists__hierarchy_output_resort(hists, prog,
1743                                                &hists->entries_collapsed,
1744                                                &hists->entries,
1745                                                min_callchain_hits,
1746                                                use_callchain);
1747                 hierarchy_recalc_total_periods(hists);
1748                 return;
1749         }
1750
1751         if (hists__has(hists, need_collapse))
1752                 root = &hists->entries_collapsed;
1753         else
1754                 root = hists->entries_in;
1755
1756         next = rb_first_cached(root);
1757         hists->entries = RB_ROOT_CACHED;
1758
1759         while (next) {
1760                 n = rb_entry(next, struct hist_entry, rb_node_in);
1761                 next = rb_next(&n->rb_node_in);
1762
1763                 if (cb && cb(n, cb_arg))
1764                         continue;
1765
1766                 __hists__insert_output_entry(&hists->entries, n, min_callchain_hits, use_callchain);
1767                 hists__inc_stats(hists, n);
1768
1769                 if (!n->filtered)
1770                         hists__calc_col_len(hists, n);
1771
1772                 if (prog)
1773                         ui_progress__update(prog, 1);
1774         }
1775 }
1776
1777 void perf_evsel__output_resort_cb(struct perf_evsel *evsel, struct ui_progress *prog,
1778                                   hists__resort_cb_t cb, void *cb_arg)
1779 {
1780         bool use_callchain;
1781
1782         if (evsel && symbol_conf.use_callchain && !symbol_conf.show_ref_callgraph)
1783                 use_callchain = evsel__has_callchain(evsel);
1784         else
1785                 use_callchain = symbol_conf.use_callchain;
1786
1787         use_callchain |= symbol_conf.show_branchflag_count;
1788
1789         output_resort(evsel__hists(evsel), prog, use_callchain, cb, cb_arg);
1790 }
1791
1792 void perf_evsel__output_resort(struct perf_evsel *evsel, struct ui_progress *prog)
1793 {
1794         return perf_evsel__output_resort_cb(evsel, prog, NULL, NULL);
1795 }
1796
1797 void hists__output_resort(struct hists *hists, struct ui_progress *prog)
1798 {
1799         output_resort(hists, prog, symbol_conf.use_callchain, NULL, NULL);
1800 }
1801
1802 void hists__output_resort_cb(struct hists *hists, struct ui_progress *prog,
1803                              hists__resort_cb_t cb)
1804 {
1805         output_resort(hists, prog, symbol_conf.use_callchain, cb, NULL);
1806 }
1807
1808 static bool can_goto_child(struct hist_entry *he, enum hierarchy_move_dir hmd)
1809 {
1810         if (he->leaf || hmd == HMD_FORCE_SIBLING)
1811                 return false;
1812
1813         if (he->unfolded || hmd == HMD_FORCE_CHILD)
1814                 return true;
1815
1816         return false;
1817 }
1818
1819 struct rb_node *rb_hierarchy_last(struct rb_node *node)
1820 {
1821         struct hist_entry *he = rb_entry(node, struct hist_entry, rb_node);
1822
1823         while (can_goto_child(he, HMD_NORMAL)) {
1824                 node = rb_last(&he->hroot_out.rb_root);
1825                 he = rb_entry(node, struct hist_entry, rb_node);
1826         }
1827         return node;
1828 }
1829
1830 struct rb_node *__rb_hierarchy_next(struct rb_node *node, enum hierarchy_move_dir hmd)
1831 {
1832         struct hist_entry *he = rb_entry(node, struct hist_entry, rb_node);
1833
1834         if (can_goto_child(he, hmd))
1835                 node = rb_first_cached(&he->hroot_out);
1836         else
1837                 node = rb_next(node);
1838
1839         while (node == NULL) {
1840                 he = he->parent_he;
1841                 if (he == NULL)
1842                         break;
1843
1844                 node = rb_next(&he->rb_node);
1845         }
1846         return node;
1847 }
1848
1849 struct rb_node *rb_hierarchy_prev(struct rb_node *node)
1850 {
1851         struct hist_entry *he = rb_entry(node, struct hist_entry, rb_node);
1852
1853         node = rb_prev(node);
1854         if (node)
1855                 return rb_hierarchy_last(node);
1856
1857         he = he->parent_he;
1858         if (he == NULL)
1859                 return NULL;
1860
1861         return &he->rb_node;
1862 }
1863
1864 bool hist_entry__has_hierarchy_children(struct hist_entry *he, float limit)
1865 {
1866         struct rb_node *node;
1867         struct hist_entry *child;
1868         float percent;
1869
1870         if (he->leaf)
1871                 return false;
1872
1873         node = rb_first_cached(&he->hroot_out);
1874         child = rb_entry(node, struct hist_entry, rb_node);
1875
1876         while (node && child->filtered) {
1877                 node = rb_next(node);
1878                 child = rb_entry(node, struct hist_entry, rb_node);
1879         }
1880
1881         if (node)
1882                 percent = hist_entry__get_percent_limit(child);
1883         else
1884                 percent = 0;
1885
1886         return node && percent >= limit;
1887 }
1888
1889 static void hists__remove_entry_filter(struct hists *hists, struct hist_entry *h,
1890                                        enum hist_filter filter)
1891 {
1892         h->filtered &= ~(1 << filter);
1893
1894         if (symbol_conf.report_hierarchy) {
1895                 struct hist_entry *parent = h->parent_he;
1896
1897                 while (parent) {
1898                         he_stat__add_stat(&parent->stat, &h->stat);
1899
1900                         parent->filtered &= ~(1 << filter);
1901
1902                         if (parent->filtered)
1903                                 goto next;
1904
1905                         /* force fold unfiltered entry for simplicity */
1906                         parent->unfolded = false;
1907                         parent->has_no_entry = false;
1908                         parent->row_offset = 0;
1909                         parent->nr_rows = 0;
1910 next:
1911                         parent = parent->parent_he;
1912                 }
1913         }
1914
1915         if (h->filtered)
1916                 return;
1917
1918         /* force fold unfiltered entry for simplicity */
1919         h->unfolded = false;
1920         h->has_no_entry = false;
1921         h->row_offset = 0;
1922         h->nr_rows = 0;
1923
1924         hists->stats.nr_non_filtered_samples += h->stat.nr_events;
1925
1926         hists__inc_filter_stats(hists, h);
1927         hists__calc_col_len(hists, h);
1928 }
1929
1930
1931 static bool hists__filter_entry_by_dso(struct hists *hists,
1932                                        struct hist_entry *he)
1933 {
1934         if (hists->dso_filter != NULL &&
1935             (he->ms.map == NULL || he->ms.map->dso != hists->dso_filter)) {
1936                 he->filtered |= (1 << HIST_FILTER__DSO);
1937                 return true;
1938         }
1939
1940         return false;
1941 }
1942
1943 static bool hists__filter_entry_by_thread(struct hists *hists,
1944                                           struct hist_entry *he)
1945 {
1946         if (hists->thread_filter != NULL &&
1947             he->thread != hists->thread_filter) {
1948                 he->filtered |= (1 << HIST_FILTER__THREAD);
1949                 return true;
1950         }
1951
1952         return false;
1953 }
1954
1955 static bool hists__filter_entry_by_symbol(struct hists *hists,
1956                                           struct hist_entry *he)
1957 {
1958         if (hists->symbol_filter_str != NULL &&
1959             (!he->ms.sym || strstr(he->ms.sym->name,
1960                                    hists->symbol_filter_str) == NULL)) {
1961                 he->filtered |= (1 << HIST_FILTER__SYMBOL);
1962                 return true;
1963         }
1964
1965         return false;
1966 }
1967
1968 static bool hists__filter_entry_by_socket(struct hists *hists,
1969                                           struct hist_entry *he)
1970 {
1971         if ((hists->socket_filter > -1) &&
1972             (he->socket != hists->socket_filter)) {
1973                 he->filtered |= (1 << HIST_FILTER__SOCKET);
1974                 return true;
1975         }
1976
1977         return false;
1978 }
1979
1980 typedef bool (*filter_fn_t)(struct hists *hists, struct hist_entry *he);
1981
1982 static void hists__filter_by_type(struct hists *hists, int type, filter_fn_t filter)
1983 {
1984         struct rb_node *nd;
1985
1986         hists->stats.nr_non_filtered_samples = 0;
1987
1988         hists__reset_filter_stats(hists);
1989         hists__reset_col_len(hists);
1990
1991         for (nd = rb_first_cached(&hists->entries); nd; nd = rb_next(nd)) {
1992                 struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
1993
1994                 if (filter(hists, h))
1995                         continue;
1996
1997                 hists__remove_entry_filter(hists, h, type);
1998         }
1999 }
2000
2001 static void resort_filtered_entry(struct rb_root_cached *root,
2002                                   struct hist_entry *he)
2003 {
2004         struct rb_node **p = &root->rb_root.rb_node;
2005         struct rb_node *parent = NULL;
2006         struct hist_entry *iter;
2007         struct rb_root_cached new_root = RB_ROOT_CACHED;
2008         struct rb_node *nd;
2009         bool leftmost = true;
2010
2011         while (*p != NULL) {
2012                 parent = *p;
2013                 iter = rb_entry(parent, struct hist_entry, rb_node);
2014
2015                 if (hist_entry__sort(he, iter) > 0)
2016                         p = &(*p)->rb_left;
2017                 else {
2018                         p = &(*p)->rb_right;
2019                         leftmost = false;
2020                 }
2021         }
2022
2023         rb_link_node(&he->rb_node, parent, p);
2024         rb_insert_color_cached(&he->rb_node, root, leftmost);
2025
2026         if (he->leaf || he->filtered)
2027                 return;
2028
2029         nd = rb_first_cached(&he->hroot_out);
2030         while (nd) {
2031                 struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
2032
2033                 nd = rb_next(nd);
2034                 rb_erase_cached(&h->rb_node, &he->hroot_out);
2035
2036                 resort_filtered_entry(&new_root, h);
2037         }
2038
2039         he->hroot_out = new_root;
2040 }
2041
2042 static void hists__filter_hierarchy(struct hists *hists, int type, const void *arg)
2043 {
2044         struct rb_node *nd;
2045         struct rb_root_cached new_root = RB_ROOT_CACHED;
2046
2047         hists->stats.nr_non_filtered_samples = 0;
2048
2049         hists__reset_filter_stats(hists);
2050         hists__reset_col_len(hists);
2051
2052         nd = rb_first_cached(&hists->entries);
2053         while (nd) {
2054                 struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
2055                 int ret;
2056
2057                 ret = hist_entry__filter(h, type, arg);
2058
2059                 /*
2060                  * case 1. non-matching type
2061                  * zero out the period, set filter marker and move to child
2062                  */
2063                 if (ret < 0) {
2064                         memset(&h->stat, 0, sizeof(h->stat));
2065                         h->filtered |= (1 << type);
2066
2067                         nd = __rb_hierarchy_next(&h->rb_node, HMD_FORCE_CHILD);
2068                 }
2069                 /*
2070                  * case 2. matched type (filter out)
2071                  * set filter marker and move to next
2072                  */
2073                 else if (ret == 1) {
2074                         h->filtered |= (1 << type);
2075
2076                         nd = __rb_hierarchy_next(&h->rb_node, HMD_FORCE_SIBLING);
2077                 }
2078                 /*
2079                  * case 3. ok (not filtered)
2080                  * add period to hists and parents, erase the filter marker
2081                  * and move to next sibling
2082                  */
2083                 else {
2084                         hists__remove_entry_filter(hists, h, type);
2085
2086                         nd = __rb_hierarchy_next(&h->rb_node, HMD_FORCE_SIBLING);
2087                 }
2088         }
2089
2090         hierarchy_recalc_total_periods(hists);
2091
2092         /*
2093          * resort output after applying a new filter since filter in a lower
2094          * hierarchy can change periods in a upper hierarchy.
2095          */
2096         nd = rb_first_cached(&hists->entries);
2097         while (nd) {
2098                 struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
2099
2100                 nd = rb_next(nd);
2101                 rb_erase_cached(&h->rb_node, &hists->entries);
2102
2103                 resort_filtered_entry(&new_root, h);
2104         }
2105
2106         hists->entries = new_root;
2107 }
2108
2109 void hists__filter_by_thread(struct hists *hists)
2110 {
2111         if (symbol_conf.report_hierarchy)
2112                 hists__filter_hierarchy(hists, HIST_FILTER__THREAD,
2113                                         hists->thread_filter);
2114         else
2115                 hists__filter_by_type(hists, HIST_FILTER__THREAD,
2116                                       hists__filter_entry_by_thread);
2117 }
2118
2119 void hists__filter_by_dso(struct hists *hists)
2120 {
2121         if (symbol_conf.report_hierarchy)
2122                 hists__filter_hierarchy(hists, HIST_FILTER__DSO,
2123                                         hists->dso_filter);
2124         else
2125                 hists__filter_by_type(hists, HIST_FILTER__DSO,
2126                                       hists__filter_entry_by_dso);
2127 }
2128
2129 void hists__filter_by_symbol(struct hists *hists)
2130 {
2131         if (symbol_conf.report_hierarchy)
2132                 hists__filter_hierarchy(hists, HIST_FILTER__SYMBOL,
2133                                         hists->symbol_filter_str);
2134         else
2135                 hists__filter_by_type(hists, HIST_FILTER__SYMBOL,
2136                                       hists__filter_entry_by_symbol);
2137 }
2138
2139 void hists__filter_by_socket(struct hists *hists)
2140 {
2141         if (symbol_conf.report_hierarchy)
2142                 hists__filter_hierarchy(hists, HIST_FILTER__SOCKET,
2143                                         &hists->socket_filter);
2144         else
2145                 hists__filter_by_type(hists, HIST_FILTER__SOCKET,
2146                                       hists__filter_entry_by_socket);
2147 }
2148
2149 void events_stats__inc(struct events_stats *stats, u32 type)
2150 {
2151         ++stats->nr_events[0];
2152         ++stats->nr_events[type];
2153 }
2154
2155 void hists__inc_nr_events(struct hists *hists, u32 type)
2156 {
2157         events_stats__inc(&hists->stats, type);
2158 }
2159
2160 void hists__inc_nr_samples(struct hists *hists, bool filtered)
2161 {
2162         events_stats__inc(&hists->stats, PERF_RECORD_SAMPLE);
2163         if (!filtered)
2164                 hists->stats.nr_non_filtered_samples++;
2165 }
2166
2167 static struct hist_entry *hists__add_dummy_entry(struct hists *hists,
2168                                                  struct hist_entry *pair)
2169 {
2170         struct rb_root_cached *root;
2171         struct rb_node **p;
2172         struct rb_node *parent = NULL;
2173         struct hist_entry *he;
2174         int64_t cmp;
2175         bool leftmost = true;
2176
2177         if (hists__has(hists, need_collapse))
2178                 root = &hists->entries_collapsed;
2179         else
2180                 root = hists->entries_in;
2181
2182         p = &root->rb_root.rb_node;
2183
2184         while (*p != NULL) {
2185                 parent = *p;
2186                 he = rb_entry(parent, struct hist_entry, rb_node_in);
2187
2188                 cmp = hist_entry__collapse(he, pair);
2189
2190                 if (!cmp)
2191                         goto out;
2192
2193                 if (cmp < 0)
2194                         p = &(*p)->rb_left;
2195                 else {
2196                         p = &(*p)->rb_right;
2197                         leftmost = false;
2198                 }
2199         }
2200
2201         he = hist_entry__new(pair, true);
2202         if (he) {
2203                 memset(&he->stat, 0, sizeof(he->stat));
2204                 he->hists = hists;
2205                 if (symbol_conf.cumulate_callchain)
2206                         memset(he->stat_acc, 0, sizeof(he->stat));
2207                 rb_link_node(&he->rb_node_in, parent, p);
2208                 rb_insert_color_cached(&he->rb_node_in, root, leftmost);
2209                 hists__inc_stats(hists, he);
2210                 he->dummy = true;
2211         }
2212 out:
2213         return he;
2214 }
2215
2216 static struct hist_entry *add_dummy_hierarchy_entry(struct hists *hists,
2217                                                     struct rb_root_cached *root,
2218                                                     struct hist_entry *pair)
2219 {
2220         struct rb_node **p;
2221         struct rb_node *parent = NULL;
2222         struct hist_entry *he;
2223         struct perf_hpp_fmt *fmt;
2224         bool leftmost = true;
2225
2226         p = &root->rb_root.rb_node;
2227         while (*p != NULL) {
2228                 int64_t cmp = 0;
2229
2230                 parent = *p;
2231                 he = rb_entry(parent, struct hist_entry, rb_node_in);
2232
2233                 perf_hpp_list__for_each_sort_list(he->hpp_list, fmt) {
2234                         cmp = fmt->collapse(fmt, he, pair);
2235                         if (cmp)
2236                                 break;
2237                 }
2238                 if (!cmp)
2239                         goto out;
2240
2241                 if (cmp < 0)
2242                         p = &parent->rb_left;
2243                 else {
2244                         p = &parent->rb_right;
2245                         leftmost = false;
2246                 }
2247         }
2248
2249         he = hist_entry__new(pair, true);
2250         if (he) {
2251                 rb_link_node(&he->rb_node_in, parent, p);
2252                 rb_insert_color_cached(&he->rb_node_in, root, leftmost);
2253
2254                 he->dummy = true;
2255                 he->hists = hists;
2256                 memset(&he->stat, 0, sizeof(he->stat));
2257                 hists__inc_stats(hists, he);
2258         }
2259 out:
2260         return he;
2261 }
2262
2263 static struct hist_entry *hists__find_entry(struct hists *hists,
2264                                             struct hist_entry *he)
2265 {
2266         struct rb_node *n;
2267
2268         if (hists__has(hists, need_collapse))
2269                 n = hists->entries_collapsed.rb_root.rb_node;
2270         else
2271                 n = hists->entries_in->rb_root.rb_node;
2272
2273         while (n) {
2274                 struct hist_entry *iter = rb_entry(n, struct hist_entry, rb_node_in);
2275                 int64_t cmp = hist_entry__collapse(iter, he);
2276
2277                 if (cmp < 0)
2278                         n = n->rb_left;
2279                 else if (cmp > 0)
2280                         n = n->rb_right;
2281                 else
2282                         return iter;
2283         }
2284
2285         return NULL;
2286 }
2287
2288 static struct hist_entry *hists__find_hierarchy_entry(struct rb_root_cached *root,
2289                                                       struct hist_entry *he)
2290 {
2291         struct rb_node *n = root->rb_root.rb_node;
2292
2293         while (n) {
2294                 struct hist_entry *iter;
2295                 struct perf_hpp_fmt *fmt;
2296                 int64_t cmp = 0;
2297
2298                 iter = rb_entry(n, struct hist_entry, rb_node_in);
2299                 perf_hpp_list__for_each_sort_list(he->hpp_list, fmt) {
2300                         cmp = fmt->collapse(fmt, iter, he);
2301                         if (cmp)
2302                                 break;
2303                 }
2304
2305                 if (cmp < 0)
2306                         n = n->rb_left;
2307                 else if (cmp > 0)
2308                         n = n->rb_right;
2309                 else
2310                         return iter;
2311         }
2312
2313         return NULL;
2314 }
2315
2316 static void hists__match_hierarchy(struct rb_root_cached *leader_root,
2317                                    struct rb_root_cached *other_root)
2318 {
2319         struct rb_node *nd;
2320         struct hist_entry *pos, *pair;
2321
2322         for (nd = rb_first_cached(leader_root); nd; nd = rb_next(nd)) {
2323                 pos  = rb_entry(nd, struct hist_entry, rb_node_in);
2324                 pair = hists__find_hierarchy_entry(other_root, pos);
2325
2326                 if (pair) {
2327                         hist_entry__add_pair(pair, pos);
2328                         hists__match_hierarchy(&pos->hroot_in, &pair->hroot_in);
2329                 }
2330         }
2331 }
2332
2333 /*
2334  * Look for pairs to link to the leader buckets (hist_entries):
2335  */
2336 void hists__match(struct hists *leader, struct hists *other)
2337 {
2338         struct rb_root_cached *root;
2339         struct rb_node *nd;
2340         struct hist_entry *pos, *pair;
2341
2342         if (symbol_conf.report_hierarchy) {
2343                 /* hierarchy report always collapses entries */
2344                 return hists__match_hierarchy(&leader->entries_collapsed,
2345                                               &other->entries_collapsed);
2346         }
2347
2348         if (hists__has(leader, need_collapse))
2349                 root = &leader->entries_collapsed;
2350         else
2351                 root = leader->entries_in;
2352
2353         for (nd = rb_first_cached(root); nd; nd = rb_next(nd)) {
2354                 pos  = rb_entry(nd, struct hist_entry, rb_node_in);
2355                 pair = hists__find_entry(other, pos);
2356
2357                 if (pair)
2358                         hist_entry__add_pair(pair, pos);
2359         }
2360 }
2361
2362 static int hists__link_hierarchy(struct hists *leader_hists,
2363                                  struct hist_entry *parent,
2364                                  struct rb_root_cached *leader_root,
2365                                  struct rb_root_cached *other_root)
2366 {
2367         struct rb_node *nd;
2368         struct hist_entry *pos, *leader;
2369
2370         for (nd = rb_first_cached(other_root); nd; nd = rb_next(nd)) {
2371                 pos = rb_entry(nd, struct hist_entry, rb_node_in);
2372
2373                 if (hist_entry__has_pairs(pos)) {
2374                         bool found = false;
2375
2376                         list_for_each_entry(leader, &pos->pairs.head, pairs.node) {
2377                                 if (leader->hists == leader_hists) {
2378                                         found = true;
2379                                         break;
2380                                 }
2381                         }
2382                         if (!found)
2383                                 return -1;
2384                 } else {
2385                         leader = add_dummy_hierarchy_entry(leader_hists,
2386                                                            leader_root, pos);
2387                         if (leader == NULL)
2388                                 return -1;
2389
2390                         /* do not point parent in the pos */
2391                         leader->parent_he = parent;
2392
2393                         hist_entry__add_pair(pos, leader);
2394                 }
2395
2396                 if (!pos->leaf) {
2397                         if (hists__link_hierarchy(leader_hists, leader,
2398                                                   &leader->hroot_in,
2399                                                   &pos->hroot_in) < 0)
2400                                 return -1;
2401                 }
2402         }
2403         return 0;
2404 }
2405
2406 /*
2407  * Look for entries in the other hists that are not present in the leader, if
2408  * we find them, just add a dummy entry on the leader hists, with period=0,
2409  * nr_events=0, to serve as the list header.
2410  */
2411 int hists__link(struct hists *leader, struct hists *other)
2412 {
2413         struct rb_root_cached *root;
2414         struct rb_node *nd;
2415         struct hist_entry *pos, *pair;
2416
2417         if (symbol_conf.report_hierarchy) {
2418                 /* hierarchy report always collapses entries */
2419                 return hists__link_hierarchy(leader, NULL,
2420                                              &leader->entries_collapsed,
2421                                              &other->entries_collapsed);
2422         }
2423
2424         if (hists__has(other, need_collapse))
2425                 root = &other->entries_collapsed;
2426         else
2427                 root = other->entries_in;
2428
2429         for (nd = rb_first_cached(root); nd; nd = rb_next(nd)) {
2430                 pos = rb_entry(nd, struct hist_entry, rb_node_in);
2431
2432                 if (!hist_entry__has_pairs(pos)) {
2433                         pair = hists__add_dummy_entry(leader, pos);
2434                         if (pair == NULL)
2435                                 return -1;
2436                         hist_entry__add_pair(pos, pair);
2437                 }
2438         }
2439
2440         return 0;
2441 }
2442
2443 void hist__account_cycles(struct branch_stack *bs, struct addr_location *al,
2444                           struct perf_sample *sample, bool nonany_branch_mode)
2445 {
2446         struct branch_info *bi;
2447
2448         /* If we have branch cycles always annotate them. */
2449         if (bs && bs->nr && bs->entries[0].flags.cycles) {
2450                 int i;
2451
2452                 bi = sample__resolve_bstack(sample, al);
2453                 if (bi) {
2454                         struct addr_map_symbol *prev = NULL;
2455
2456                         /*
2457                          * Ignore errors, still want to process the
2458                          * other entries.
2459                          *
2460                          * For non standard branch modes always
2461                          * force no IPC (prev == NULL)
2462                          *
2463                          * Note that perf stores branches reversed from
2464                          * program order!
2465                          */
2466                         for (i = bs->nr - 1; i >= 0; i--) {
2467                                 addr_map_symbol__account_cycles(&bi[i].from,
2468                                         nonany_branch_mode ? NULL : prev,
2469                                         bi[i].flags.cycles);
2470                                 prev = &bi[i].to;
2471                         }
2472                         free(bi);
2473                 }
2474         }
2475 }
2476
2477 size_t perf_evlist__fprintf_nr_events(struct perf_evlist *evlist, FILE *fp)
2478 {
2479         struct perf_evsel *pos;
2480         size_t ret = 0;
2481
2482         evlist__for_each_entry(evlist, pos) {
2483                 ret += fprintf(fp, "%s stats:\n", perf_evsel__name(pos));
2484                 ret += events_stats__fprintf(&evsel__hists(pos)->stats, fp);
2485         }
2486
2487         return ret;
2488 }
2489
2490
2491 u64 hists__total_period(struct hists *hists)
2492 {
2493         return symbol_conf.filter_relative ? hists->stats.total_non_filtered_period :
2494                 hists->stats.total_period;
2495 }
2496
2497 int __hists__scnprintf_title(struct hists *hists, char *bf, size_t size, bool show_freq)
2498 {
2499         char unit;
2500         int printed;
2501         const struct dso *dso = hists->dso_filter;
2502         const struct thread *thread = hists->thread_filter;
2503         int socket_id = hists->socket_filter;
2504         unsigned long nr_samples = hists->stats.nr_events[PERF_RECORD_SAMPLE];
2505         u64 nr_events = hists->stats.total_period;
2506         struct perf_evsel *evsel = hists_to_evsel(hists);
2507         const char *ev_name = perf_evsel__name(evsel);
2508         char buf[512], sample_freq_str[64] = "";
2509         size_t buflen = sizeof(buf);
2510         char ref[30] = " show reference callgraph, ";
2511         bool enable_ref = false;
2512
2513         if (symbol_conf.filter_relative) {
2514                 nr_samples = hists->stats.nr_non_filtered_samples;
2515                 nr_events = hists->stats.total_non_filtered_period;
2516         }
2517
2518         if (perf_evsel__is_group_event(evsel)) {
2519                 struct perf_evsel *pos;
2520
2521                 perf_evsel__group_desc(evsel, buf, buflen);
2522                 ev_name = buf;
2523
2524                 for_each_group_member(pos, evsel) {
2525                         struct hists *pos_hists = evsel__hists(pos);
2526
2527                         if (symbol_conf.filter_relative) {
2528                                 nr_samples += pos_hists->stats.nr_non_filtered_samples;
2529                                 nr_events += pos_hists->stats.total_non_filtered_period;
2530                         } else {
2531                                 nr_samples += pos_hists->stats.nr_events[PERF_RECORD_SAMPLE];
2532                                 nr_events += pos_hists->stats.total_period;
2533                         }
2534                 }
2535         }
2536
2537         if (symbol_conf.show_ref_callgraph &&
2538             strstr(ev_name, "call-graph=no"))
2539                 enable_ref = true;
2540
2541         if (show_freq)
2542                 scnprintf(sample_freq_str, sizeof(sample_freq_str), " %d Hz,", evsel->attr.sample_freq);
2543
2544         nr_samples = convert_unit(nr_samples, &unit);
2545         printed = scnprintf(bf, size,
2546                            "Samples: %lu%c of event%s '%s',%s%sEvent count (approx.): %" PRIu64,
2547                            nr_samples, unit, evsel->nr_members > 1 ? "s" : "",
2548                            ev_name, sample_freq_str, enable_ref ? ref : " ", nr_events);
2549
2550
2551         if (hists->uid_filter_str)
2552                 printed += snprintf(bf + printed, size - printed,
2553                                     ", UID: %s", hists->uid_filter_str);
2554         if (thread) {
2555                 if (hists__has(hists, thread)) {
2556                         printed += scnprintf(bf + printed, size - printed,
2557                                     ", Thread: %s(%d)",
2558                                      (thread->comm_set ? thread__comm_str(thread) : ""),
2559                                     thread->tid);
2560                 } else {
2561                         printed += scnprintf(bf + printed, size - printed,
2562                                     ", Thread: %s",
2563                                      (thread->comm_set ? thread__comm_str(thread) : ""));
2564                 }
2565         }
2566         if (dso)
2567                 printed += scnprintf(bf + printed, size - printed,
2568                                     ", DSO: %s", dso->short_name);
2569         if (socket_id > -1)
2570                 printed += scnprintf(bf + printed, size - printed,
2571                                     ", Processor Socket: %d", socket_id);
2572
2573         return printed;
2574 }
2575
2576 int parse_filter_percentage(const struct option *opt __maybe_unused,
2577                             const char *arg, int unset __maybe_unused)
2578 {
2579         if (!strcmp(arg, "relative"))
2580                 symbol_conf.filter_relative = true;
2581         else if (!strcmp(arg, "absolute"))
2582                 symbol_conf.filter_relative = false;
2583         else {
2584                 pr_debug("Invalid percentage: %s\n", arg);
2585                 return -1;
2586         }
2587
2588         return 0;
2589 }
2590
2591 int perf_hist_config(const char *var, const char *value)
2592 {
2593         if (!strcmp(var, "hist.percentage"))
2594                 return parse_filter_percentage(NULL, value, 0);
2595
2596         return 0;
2597 }
2598
2599 int __hists__init(struct hists *hists, struct perf_hpp_list *hpp_list)
2600 {
2601         memset(hists, 0, sizeof(*hists));
2602         hists->entries_in_array[0] = hists->entries_in_array[1] = RB_ROOT_CACHED;
2603         hists->entries_in = &hists->entries_in_array[0];
2604         hists->entries_collapsed = RB_ROOT_CACHED;
2605         hists->entries = RB_ROOT_CACHED;
2606         pthread_mutex_init(&hists->lock, NULL);
2607         hists->socket_filter = -1;
2608         hists->hpp_list = hpp_list;
2609         INIT_LIST_HEAD(&hists->hpp_formats);
2610         return 0;
2611 }
2612
2613 static void hists__delete_remaining_entries(struct rb_root_cached *root)
2614 {
2615         struct rb_node *node;
2616         struct hist_entry *he;
2617
2618         while (!RB_EMPTY_ROOT(&root->rb_root)) {
2619                 node = rb_first_cached(root);
2620                 rb_erase_cached(node, root);
2621
2622                 he = rb_entry(node, struct hist_entry, rb_node_in);
2623                 hist_entry__delete(he);
2624         }
2625 }
2626
2627 static void hists__delete_all_entries(struct hists *hists)
2628 {
2629         hists__delete_entries(hists);
2630         hists__delete_remaining_entries(&hists->entries_in_array[0]);
2631         hists__delete_remaining_entries(&hists->entries_in_array[1]);
2632         hists__delete_remaining_entries(&hists->entries_collapsed);
2633 }
2634
2635 static void hists_evsel__exit(struct perf_evsel *evsel)
2636 {
2637         struct hists *hists = evsel__hists(evsel);
2638         struct perf_hpp_fmt *fmt, *pos;
2639         struct perf_hpp_list_node *node, *tmp;
2640
2641         hists__delete_all_entries(hists);
2642
2643         list_for_each_entry_safe(node, tmp, &hists->hpp_formats, list) {
2644                 perf_hpp_list__for_each_format_safe(&node->hpp, fmt, pos) {
2645                         list_del(&fmt->list);
2646                         free(fmt);
2647                 }
2648                 list_del(&node->list);
2649                 free(node);
2650         }
2651 }
2652
2653 static int hists_evsel__init(struct perf_evsel *evsel)
2654 {
2655         struct hists *hists = evsel__hists(evsel);
2656
2657         __hists__init(hists, &perf_hpp_list);
2658         return 0;
2659 }
2660
2661 /*
2662  * XXX We probably need a hists_evsel__exit() to free the hist_entries
2663  * stored in the rbtree...
2664  */
2665
2666 int hists__init(void)
2667 {
2668         int err = perf_evsel__object_config(sizeof(struct hists_evsel),
2669                                             hists_evsel__init,
2670                                             hists_evsel__exit);
2671         if (err)
2672                 fputs("FATAL ERROR: Couldn't setup hists class\n", stderr);
2673
2674         return err;
2675 }
2676
2677 void perf_hpp_list__init(struct perf_hpp_list *list)
2678 {
2679         INIT_LIST_HEAD(&list->fields);
2680         INIT_LIST_HEAD(&list->sorts);
2681 }