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