1 #include "util.h" 2 #include "build-id.h" 3 #include "hist.h" 4 #include "session.h" 5 #include "sort.h" 6 #include "evsel.h" 7 #include <math.h> 8 9 static bool hists__filter_entry_by_dso(struct hists *hists, 10 struct hist_entry *he); 11 static bool hists__filter_entry_by_thread(struct hists *hists, 12 struct hist_entry *he); 13 static bool hists__filter_entry_by_symbol(struct hists *hists, 14 struct hist_entry *he); 15 16 struct callchain_param callchain_param = { 17 .mode = CHAIN_GRAPH_REL, 18 .min_percent = 0.5, 19 .order = ORDER_CALLEE, 20 .key = CCKEY_FUNCTION 21 }; 22 23 u16 hists__col_len(struct hists *hists, enum hist_column col) 24 { 25 return hists->col_len[col]; 26 } 27 28 void hists__set_col_len(struct hists *hists, enum hist_column col, u16 len) 29 { 30 hists->col_len[col] = len; 31 } 32 33 bool hists__new_col_len(struct hists *hists, enum hist_column col, u16 len) 34 { 35 if (len > hists__col_len(hists, col)) { 36 hists__set_col_len(hists, col, len); 37 return true; 38 } 39 return false; 40 } 41 42 void hists__reset_col_len(struct hists *hists) 43 { 44 enum hist_column col; 45 46 for (col = 0; col < HISTC_NR_COLS; ++col) 47 hists__set_col_len(hists, col, 0); 48 } 49 50 static void hists__set_unres_dso_col_len(struct hists *hists, int dso) 51 { 52 const unsigned int unresolved_col_width = BITS_PER_LONG / 4; 53 54 if (hists__col_len(hists, dso) < unresolved_col_width && 55 !symbol_conf.col_width_list_str && !symbol_conf.field_sep && 56 !symbol_conf.dso_list) 57 hists__set_col_len(hists, dso, unresolved_col_width); 58 } 59 60 void hists__calc_col_len(struct hists *hists, struct hist_entry *h) 61 { 62 const unsigned int unresolved_col_width = BITS_PER_LONG / 4; 63 int symlen; 64 u16 len; 65 66 /* 67 * +4 accounts for '[x] ' priv level info 68 * +2 accounts for 0x prefix on raw addresses 69 * +3 accounts for ' y ' symtab origin info 70 */ 71 if (h->ms.sym) { 72 symlen = h->ms.sym->namelen + 4; 73 if (verbose) 74 symlen += BITS_PER_LONG / 4 + 2 + 3; 75 hists__new_col_len(hists, HISTC_SYMBOL, symlen); 76 } else { 77 symlen = unresolved_col_width + 4 + 2; 78 hists__new_col_len(hists, HISTC_SYMBOL, symlen); 79 hists__set_unres_dso_col_len(hists, HISTC_DSO); 80 } 81 82 len = thread__comm_len(h->thread); 83 if (hists__new_col_len(hists, HISTC_COMM, len)) 84 hists__set_col_len(hists, HISTC_THREAD, len + 6); 85 86 if (h->ms.map) { 87 len = dso__name_len(h->ms.map->dso); 88 hists__new_col_len(hists, HISTC_DSO, len); 89 } 90 91 if (h->parent) 92 hists__new_col_len(hists, HISTC_PARENT, h->parent->namelen); 93 94 if (h->branch_info) { 95 if (h->branch_info->from.sym) { 96 symlen = (int)h->branch_info->from.sym->namelen + 4; 97 if (verbose) 98 symlen += BITS_PER_LONG / 4 + 2 + 3; 99 hists__new_col_len(hists, HISTC_SYMBOL_FROM, symlen); 100 101 symlen = dso__name_len(h->branch_info->from.map->dso); 102 hists__new_col_len(hists, HISTC_DSO_FROM, symlen); 103 } else { 104 symlen = unresolved_col_width + 4 + 2; 105 hists__new_col_len(hists, HISTC_SYMBOL_FROM, symlen); 106 hists__set_unres_dso_col_len(hists, HISTC_DSO_FROM); 107 } 108 109 if (h->branch_info->to.sym) { 110 symlen = (int)h->branch_info->to.sym->namelen + 4; 111 if (verbose) 112 symlen += BITS_PER_LONG / 4 + 2 + 3; 113 hists__new_col_len(hists, HISTC_SYMBOL_TO, symlen); 114 115 symlen = dso__name_len(h->branch_info->to.map->dso); 116 hists__new_col_len(hists, HISTC_DSO_TO, symlen); 117 } else { 118 symlen = unresolved_col_width + 4 + 2; 119 hists__new_col_len(hists, HISTC_SYMBOL_TO, symlen); 120 hists__set_unres_dso_col_len(hists, HISTC_DSO_TO); 121 } 122 } 123 124 if (h->mem_info) { 125 if (h->mem_info->daddr.sym) { 126 symlen = (int)h->mem_info->daddr.sym->namelen + 4 127 + unresolved_col_width + 2; 128 hists__new_col_len(hists, HISTC_MEM_DADDR_SYMBOL, 129 symlen); 130 } else { 131 symlen = unresolved_col_width + 4 + 2; 132 hists__new_col_len(hists, HISTC_MEM_DADDR_SYMBOL, 133 symlen); 134 } 135 if (h->mem_info->daddr.map) { 136 symlen = dso__name_len(h->mem_info->daddr.map->dso); 137 hists__new_col_len(hists, HISTC_MEM_DADDR_DSO, 138 symlen); 139 } else { 140 symlen = unresolved_col_width + 4 + 2; 141 hists__set_unres_dso_col_len(hists, HISTC_MEM_DADDR_DSO); 142 } 143 } else { 144 symlen = unresolved_col_width + 4 + 2; 145 hists__new_col_len(hists, HISTC_MEM_DADDR_SYMBOL, symlen); 146 hists__set_unres_dso_col_len(hists, HISTC_MEM_DADDR_DSO); 147 } 148 149 hists__new_col_len(hists, HISTC_MEM_LOCKED, 6); 150 hists__new_col_len(hists, HISTC_MEM_TLB, 22); 151 hists__new_col_len(hists, HISTC_MEM_SNOOP, 12); 152 hists__new_col_len(hists, HISTC_MEM_LVL, 21 + 3); 153 hists__new_col_len(hists, HISTC_LOCAL_WEIGHT, 12); 154 hists__new_col_len(hists, HISTC_GLOBAL_WEIGHT, 12); 155 156 if (h->transaction) 157 hists__new_col_len(hists, HISTC_TRANSACTION, 158 hist_entry__transaction_len()); 159 } 160 161 void hists__output_recalc_col_len(struct hists *hists, int max_rows) 162 { 163 struct rb_node *next = rb_first(&hists->entries); 164 struct hist_entry *n; 165 int row = 0; 166 167 hists__reset_col_len(hists); 168 169 while (next && row++ < max_rows) { 170 n = rb_entry(next, struct hist_entry, rb_node); 171 if (!n->filtered) 172 hists__calc_col_len(hists, n); 173 next = rb_next(&n->rb_node); 174 } 175 } 176 177 static void he_stat__add_cpumode_period(struct he_stat *he_stat, 178 unsigned int cpumode, u64 period) 179 { 180 switch (cpumode) { 181 case PERF_RECORD_MISC_KERNEL: 182 he_stat->period_sys += period; 183 break; 184 case PERF_RECORD_MISC_USER: 185 he_stat->period_us += period; 186 break; 187 case PERF_RECORD_MISC_GUEST_KERNEL: 188 he_stat->period_guest_sys += period; 189 break; 190 case PERF_RECORD_MISC_GUEST_USER: 191 he_stat->period_guest_us += period; 192 break; 193 default: 194 break; 195 } 196 } 197 198 static void he_stat__add_period(struct he_stat *he_stat, u64 period, 199 u64 weight) 200 { 201 202 he_stat->period += period; 203 he_stat->weight += weight; 204 he_stat->nr_events += 1; 205 } 206 207 static void he_stat__add_stat(struct he_stat *dest, struct he_stat *src) 208 { 209 dest->period += src->period; 210 dest->period_sys += src->period_sys; 211 dest->period_us += src->period_us; 212 dest->period_guest_sys += src->period_guest_sys; 213 dest->period_guest_us += src->period_guest_us; 214 dest->nr_events += src->nr_events; 215 dest->weight += src->weight; 216 } 217 218 static void he_stat__decay(struct he_stat *he_stat) 219 { 220 he_stat->period = (he_stat->period * 7) / 8; 221 he_stat->nr_events = (he_stat->nr_events * 7) / 8; 222 /* XXX need decay for weight too? */ 223 } 224 225 static bool hists__decay_entry(struct hists *hists, struct hist_entry *he) 226 { 227 u64 prev_period = he->stat.period; 228 229 if (prev_period == 0) 230 return true; 231 232 he_stat__decay(&he->stat); 233 234 if (!he->filtered) 235 hists->stats.total_period -= prev_period - he->stat.period; 236 237 return he->stat.period == 0; 238 } 239 240 void hists__decay_entries(struct hists *hists, bool zap_user, bool zap_kernel) 241 { 242 struct rb_node *next = rb_first(&hists->entries); 243 struct hist_entry *n; 244 245 while (next) { 246 n = rb_entry(next, struct hist_entry, rb_node); 247 next = rb_next(&n->rb_node); 248 /* 249 * We may be annotating this, for instance, so keep it here in 250 * case some it gets new samples, we'll eventually free it when 251 * the user stops browsing and it agains gets fully decayed. 252 */ 253 if (((zap_user && n->level == '.') || 254 (zap_kernel && n->level != '.') || 255 hists__decay_entry(hists, n)) && 256 !n->used) { 257 rb_erase(&n->rb_node, &hists->entries); 258 259 if (sort__need_collapse) 260 rb_erase(&n->rb_node_in, &hists->entries_collapsed); 261 262 hist_entry__free(n); 263 --hists->nr_entries; 264 } 265 } 266 } 267 268 /* 269 * histogram, sorted on item, collects periods 270 */ 271 272 static struct hist_entry *hist_entry__new(struct hist_entry *template) 273 { 274 size_t callchain_size = symbol_conf.use_callchain ? sizeof(struct callchain_root) : 0; 275 struct hist_entry *he = zalloc(sizeof(*he) + callchain_size); 276 277 if (he != NULL) { 278 *he = *template; 279 280 if (he->ms.map) 281 he->ms.map->referenced = true; 282 283 if (he->branch_info) { 284 /* 285 * This branch info is (a part of) allocated from 286 * sample__resolve_bstack() and will be freed after 287 * adding new entries. So we need to save a copy. 288 */ 289 he->branch_info = malloc(sizeof(*he->branch_info)); 290 if (he->branch_info == NULL) { 291 free(he); 292 return NULL; 293 } 294 295 memcpy(he->branch_info, template->branch_info, 296 sizeof(*he->branch_info)); 297 298 if (he->branch_info->from.map) 299 he->branch_info->from.map->referenced = true; 300 if (he->branch_info->to.map) 301 he->branch_info->to.map->referenced = true; 302 } 303 304 if (he->mem_info) { 305 if (he->mem_info->iaddr.map) 306 he->mem_info->iaddr.map->referenced = true; 307 if (he->mem_info->daddr.map) 308 he->mem_info->daddr.map->referenced = true; 309 } 310 311 if (symbol_conf.use_callchain) 312 callchain_init(he->callchain); 313 314 INIT_LIST_HEAD(&he->pairs.node); 315 } 316 317 return he; 318 } 319 320 void hists__inc_nr_entries(struct hists *hists, struct hist_entry *h) 321 { 322 if (!h->filtered) { 323 hists__calc_col_len(hists, h); 324 ++hists->nr_entries; 325 hists->stats.total_period += h->stat.period; 326 } 327 } 328 329 static u8 symbol__parent_filter(const struct symbol *parent) 330 { 331 if (symbol_conf.exclude_other && parent == NULL) 332 return 1 << HIST_FILTER__PARENT; 333 return 0; 334 } 335 336 static struct hist_entry *add_hist_entry(struct hists *hists, 337 struct hist_entry *entry, 338 struct addr_location *al) 339 { 340 struct rb_node **p; 341 struct rb_node *parent = NULL; 342 struct hist_entry *he; 343 int64_t cmp; 344 u64 period = entry->stat.period; 345 u64 weight = entry->stat.weight; 346 347 p = &hists->entries_in->rb_node; 348 349 while (*p != NULL) { 350 parent = *p; 351 he = rb_entry(parent, struct hist_entry, rb_node_in); 352 353 /* 354 * Make sure that it receives arguments in a same order as 355 * hist_entry__collapse() so that we can use an appropriate 356 * function when searching an entry regardless which sort 357 * keys were used. 358 */ 359 cmp = hist_entry__cmp(he, entry); 360 361 if (!cmp) { 362 he_stat__add_period(&he->stat, period, weight); 363 364 /* 365 * This mem info was allocated from sample__resolve_mem 366 * and will not be used anymore. 367 */ 368 zfree(&entry->mem_info); 369 370 /* If the map of an existing hist_entry has 371 * become out-of-date due to an exec() or 372 * similar, update it. Otherwise we will 373 * mis-adjust symbol addresses when computing 374 * the history counter to increment. 375 */ 376 if (he->ms.map != entry->ms.map) { 377 he->ms.map = entry->ms.map; 378 if (he->ms.map) 379 he->ms.map->referenced = true; 380 } 381 goto out; 382 } 383 384 if (cmp < 0) 385 p = &(*p)->rb_left; 386 else 387 p = &(*p)->rb_right; 388 } 389 390 he = hist_entry__new(entry); 391 if (!he) 392 return NULL; 393 394 hists->nr_entries++; 395 rb_link_node(&he->rb_node_in, parent, p); 396 rb_insert_color(&he->rb_node_in, hists->entries_in); 397 out: 398 he_stat__add_cpumode_period(&he->stat, al->cpumode, period); 399 return he; 400 } 401 402 struct hist_entry *__hists__add_entry(struct hists *hists, 403 struct addr_location *al, 404 struct symbol *sym_parent, 405 struct branch_info *bi, 406 struct mem_info *mi, 407 u64 period, u64 weight, u64 transaction) 408 { 409 struct hist_entry entry = { 410 .thread = al->thread, 411 .comm = thread__comm(al->thread), 412 .ms = { 413 .map = al->map, 414 .sym = al->sym, 415 }, 416 .cpu = al->cpu, 417 .ip = al->addr, 418 .level = al->level, 419 .stat = { 420 .nr_events = 1, 421 .period = period, 422 .weight = weight, 423 }, 424 .parent = sym_parent, 425 .filtered = symbol__parent_filter(sym_parent) | al->filtered, 426 .hists = hists, 427 .branch_info = bi, 428 .mem_info = mi, 429 .transaction = transaction, 430 }; 431 432 return add_hist_entry(hists, &entry, al); 433 } 434 435 int64_t 436 hist_entry__cmp(struct hist_entry *left, struct hist_entry *right) 437 { 438 struct sort_entry *se; 439 int64_t cmp = 0; 440 441 list_for_each_entry(se, &hist_entry__sort_list, list) { 442 cmp = se->se_cmp(left, right); 443 if (cmp) 444 break; 445 } 446 447 return cmp; 448 } 449 450 int64_t 451 hist_entry__collapse(struct hist_entry *left, struct hist_entry *right) 452 { 453 struct sort_entry *se; 454 int64_t cmp = 0; 455 456 list_for_each_entry(se, &hist_entry__sort_list, list) { 457 int64_t (*f)(struct hist_entry *, struct hist_entry *); 458 459 f = se->se_collapse ?: se->se_cmp; 460 461 cmp = f(left, right); 462 if (cmp) 463 break; 464 } 465 466 return cmp; 467 } 468 469 void hist_entry__free(struct hist_entry *he) 470 { 471 zfree(&he->branch_info); 472 zfree(&he->mem_info); 473 free_srcline(he->srcline); 474 free(he); 475 } 476 477 /* 478 * collapse the histogram 479 */ 480 481 static bool hists__collapse_insert_entry(struct hists *hists __maybe_unused, 482 struct rb_root *root, 483 struct hist_entry *he) 484 { 485 struct rb_node **p = &root->rb_node; 486 struct rb_node *parent = NULL; 487 struct hist_entry *iter; 488 int64_t cmp; 489 490 while (*p != NULL) { 491 parent = *p; 492 iter = rb_entry(parent, struct hist_entry, rb_node_in); 493 494 cmp = hist_entry__collapse(iter, he); 495 496 if (!cmp) { 497 he_stat__add_stat(&iter->stat, &he->stat); 498 499 if (symbol_conf.use_callchain) { 500 callchain_cursor_reset(&callchain_cursor); 501 callchain_merge(&callchain_cursor, 502 iter->callchain, 503 he->callchain); 504 } 505 hist_entry__free(he); 506 return false; 507 } 508 509 if (cmp < 0) 510 p = &(*p)->rb_left; 511 else 512 p = &(*p)->rb_right; 513 } 514 515 rb_link_node(&he->rb_node_in, parent, p); 516 rb_insert_color(&he->rb_node_in, root); 517 return true; 518 } 519 520 static struct rb_root *hists__get_rotate_entries_in(struct hists *hists) 521 { 522 struct rb_root *root; 523 524 pthread_mutex_lock(&hists->lock); 525 526 root = hists->entries_in; 527 if (++hists->entries_in > &hists->entries_in_array[1]) 528 hists->entries_in = &hists->entries_in_array[0]; 529 530 pthread_mutex_unlock(&hists->lock); 531 532 return root; 533 } 534 535 static void hists__apply_filters(struct hists *hists, struct hist_entry *he) 536 { 537 hists__filter_entry_by_dso(hists, he); 538 hists__filter_entry_by_thread(hists, he); 539 hists__filter_entry_by_symbol(hists, he); 540 } 541 542 void hists__collapse_resort(struct hists *hists, struct ui_progress *prog) 543 { 544 struct rb_root *root; 545 struct rb_node *next; 546 struct hist_entry *n; 547 548 if (!sort__need_collapse) 549 return; 550 551 root = hists__get_rotate_entries_in(hists); 552 next = rb_first(root); 553 554 while (next) { 555 if (session_done()) 556 break; 557 n = rb_entry(next, struct hist_entry, rb_node_in); 558 next = rb_next(&n->rb_node_in); 559 560 rb_erase(&n->rb_node_in, root); 561 if (hists__collapse_insert_entry(hists, &hists->entries_collapsed, n)) { 562 /* 563 * If it wasn't combined with one of the entries already 564 * collapsed, we need to apply the filters that may have 565 * been set by, say, the hist_browser. 566 */ 567 hists__apply_filters(hists, n); 568 } 569 if (prog) 570 ui_progress__update(prog, 1); 571 } 572 } 573 574 /* 575 * reverse the map, sort on period. 576 */ 577 578 static int period_cmp(u64 period_a, u64 period_b) 579 { 580 if (period_a > period_b) 581 return 1; 582 if (period_a < period_b) 583 return -1; 584 return 0; 585 } 586 587 static int hist_entry__sort_on_period(struct hist_entry *a, 588 struct hist_entry *b) 589 { 590 int ret; 591 int i, nr_members; 592 struct perf_evsel *evsel; 593 struct hist_entry *pair; 594 u64 *periods_a, *periods_b; 595 596 ret = period_cmp(a->stat.period, b->stat.period); 597 if (ret || !symbol_conf.event_group) 598 return ret; 599 600 evsel = hists_to_evsel(a->hists); 601 nr_members = evsel->nr_members; 602 if (nr_members <= 1) 603 return ret; 604 605 periods_a = zalloc(sizeof(periods_a) * nr_members); 606 periods_b = zalloc(sizeof(periods_b) * nr_members); 607 608 if (!periods_a || !periods_b) 609 goto out; 610 611 list_for_each_entry(pair, &a->pairs.head, pairs.node) { 612 evsel = hists_to_evsel(pair->hists); 613 periods_a[perf_evsel__group_idx(evsel)] = pair->stat.period; 614 } 615 616 list_for_each_entry(pair, &b->pairs.head, pairs.node) { 617 evsel = hists_to_evsel(pair->hists); 618 periods_b[perf_evsel__group_idx(evsel)] = pair->stat.period; 619 } 620 621 for (i = 1; i < nr_members; i++) { 622 ret = period_cmp(periods_a[i], periods_b[i]); 623 if (ret) 624 break; 625 } 626 627 out: 628 free(periods_a); 629 free(periods_b); 630 631 return ret; 632 } 633 634 static void __hists__insert_output_entry(struct rb_root *entries, 635 struct hist_entry *he, 636 u64 min_callchain_hits) 637 { 638 struct rb_node **p = &entries->rb_node; 639 struct rb_node *parent = NULL; 640 struct hist_entry *iter; 641 642 if (symbol_conf.use_callchain) 643 callchain_param.sort(&he->sorted_chain, he->callchain, 644 min_callchain_hits, &callchain_param); 645 646 while (*p != NULL) { 647 parent = *p; 648 iter = rb_entry(parent, struct hist_entry, rb_node); 649 650 if (hist_entry__sort_on_period(he, iter) > 0) 651 p = &(*p)->rb_left; 652 else 653 p = &(*p)->rb_right; 654 } 655 656 rb_link_node(&he->rb_node, parent, p); 657 rb_insert_color(&he->rb_node, entries); 658 } 659 660 void hists__output_resort(struct hists *hists) 661 { 662 struct rb_root *root; 663 struct rb_node *next; 664 struct hist_entry *n; 665 u64 min_callchain_hits; 666 667 min_callchain_hits = hists->stats.total_period * (callchain_param.min_percent / 100); 668 669 if (sort__need_collapse) 670 root = &hists->entries_collapsed; 671 else 672 root = hists->entries_in; 673 674 next = rb_first(root); 675 hists->entries = RB_ROOT; 676 677 hists->nr_entries = 0; 678 hists->stats.total_period = 0; 679 hists__reset_col_len(hists); 680 681 while (next) { 682 n = rb_entry(next, struct hist_entry, rb_node_in); 683 next = rb_next(&n->rb_node_in); 684 685 __hists__insert_output_entry(&hists->entries, n, min_callchain_hits); 686 hists__inc_nr_entries(hists, n); 687 } 688 } 689 690 static void hists__remove_entry_filter(struct hists *hists, struct hist_entry *h, 691 enum hist_filter filter) 692 { 693 h->filtered &= ~(1 << filter); 694 if (h->filtered) 695 return; 696 697 ++hists->nr_entries; 698 if (h->ms.unfolded) 699 hists->nr_entries += h->nr_rows; 700 h->row_offset = 0; 701 hists->stats.total_period += h->stat.period; 702 hists->stats.nr_events[PERF_RECORD_SAMPLE] += h->stat.nr_events; 703 704 hists__calc_col_len(hists, h); 705 } 706 707 708 static bool hists__filter_entry_by_dso(struct hists *hists, 709 struct hist_entry *he) 710 { 711 if (hists->dso_filter != NULL && 712 (he->ms.map == NULL || he->ms.map->dso != hists->dso_filter)) { 713 he->filtered |= (1 << HIST_FILTER__DSO); 714 return true; 715 } 716 717 return false; 718 } 719 720 void hists__filter_by_dso(struct hists *hists) 721 { 722 struct rb_node *nd; 723 724 hists->nr_entries = hists->stats.total_period = 0; 725 hists->stats.nr_events[PERF_RECORD_SAMPLE] = 0; 726 hists__reset_col_len(hists); 727 728 for (nd = rb_first(&hists->entries); nd; nd = rb_next(nd)) { 729 struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node); 730 731 if (symbol_conf.exclude_other && !h->parent) 732 continue; 733 734 if (hists__filter_entry_by_dso(hists, h)) 735 continue; 736 737 hists__remove_entry_filter(hists, h, HIST_FILTER__DSO); 738 } 739 } 740 741 static bool hists__filter_entry_by_thread(struct hists *hists, 742 struct hist_entry *he) 743 { 744 if (hists->thread_filter != NULL && 745 he->thread != hists->thread_filter) { 746 he->filtered |= (1 << HIST_FILTER__THREAD); 747 return true; 748 } 749 750 return false; 751 } 752 753 void hists__filter_by_thread(struct hists *hists) 754 { 755 struct rb_node *nd; 756 757 hists->nr_entries = hists->stats.total_period = 0; 758 hists->stats.nr_events[PERF_RECORD_SAMPLE] = 0; 759 hists__reset_col_len(hists); 760 761 for (nd = rb_first(&hists->entries); nd; nd = rb_next(nd)) { 762 struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node); 763 764 if (hists__filter_entry_by_thread(hists, h)) 765 continue; 766 767 hists__remove_entry_filter(hists, h, HIST_FILTER__THREAD); 768 } 769 } 770 771 static bool hists__filter_entry_by_symbol(struct hists *hists, 772 struct hist_entry *he) 773 { 774 if (hists->symbol_filter_str != NULL && 775 (!he->ms.sym || strstr(he->ms.sym->name, 776 hists->symbol_filter_str) == NULL)) { 777 he->filtered |= (1 << HIST_FILTER__SYMBOL); 778 return true; 779 } 780 781 return false; 782 } 783 784 void hists__filter_by_symbol(struct hists *hists) 785 { 786 struct rb_node *nd; 787 788 hists->nr_entries = hists->stats.total_period = 0; 789 hists->stats.nr_events[PERF_RECORD_SAMPLE] = 0; 790 hists__reset_col_len(hists); 791 792 for (nd = rb_first(&hists->entries); nd; nd = rb_next(nd)) { 793 struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node); 794 795 if (hists__filter_entry_by_symbol(hists, h)) 796 continue; 797 798 hists__remove_entry_filter(hists, h, HIST_FILTER__SYMBOL); 799 } 800 } 801 802 void events_stats__inc(struct events_stats *stats, u32 type) 803 { 804 ++stats->nr_events[0]; 805 ++stats->nr_events[type]; 806 } 807 808 void hists__inc_nr_events(struct hists *hists, u32 type) 809 { 810 events_stats__inc(&hists->stats, type); 811 } 812 813 static struct hist_entry *hists__add_dummy_entry(struct hists *hists, 814 struct hist_entry *pair) 815 { 816 struct rb_root *root; 817 struct rb_node **p; 818 struct rb_node *parent = NULL; 819 struct hist_entry *he; 820 int64_t cmp; 821 822 if (sort__need_collapse) 823 root = &hists->entries_collapsed; 824 else 825 root = hists->entries_in; 826 827 p = &root->rb_node; 828 829 while (*p != NULL) { 830 parent = *p; 831 he = rb_entry(parent, struct hist_entry, rb_node_in); 832 833 cmp = hist_entry__collapse(he, pair); 834 835 if (!cmp) 836 goto out; 837 838 if (cmp < 0) 839 p = &(*p)->rb_left; 840 else 841 p = &(*p)->rb_right; 842 } 843 844 he = hist_entry__new(pair); 845 if (he) { 846 memset(&he->stat, 0, sizeof(he->stat)); 847 he->hists = hists; 848 rb_link_node(&he->rb_node_in, parent, p); 849 rb_insert_color(&he->rb_node_in, root); 850 hists__inc_nr_entries(hists, he); 851 he->dummy = true; 852 } 853 out: 854 return he; 855 } 856 857 static struct hist_entry *hists__find_entry(struct hists *hists, 858 struct hist_entry *he) 859 { 860 struct rb_node *n; 861 862 if (sort__need_collapse) 863 n = hists->entries_collapsed.rb_node; 864 else 865 n = hists->entries_in->rb_node; 866 867 while (n) { 868 struct hist_entry *iter = rb_entry(n, struct hist_entry, rb_node_in); 869 int64_t cmp = hist_entry__collapse(iter, he); 870 871 if (cmp < 0) 872 n = n->rb_left; 873 else if (cmp > 0) 874 n = n->rb_right; 875 else 876 return iter; 877 } 878 879 return NULL; 880 } 881 882 /* 883 * Look for pairs to link to the leader buckets (hist_entries): 884 */ 885 void hists__match(struct hists *leader, struct hists *other) 886 { 887 struct rb_root *root; 888 struct rb_node *nd; 889 struct hist_entry *pos, *pair; 890 891 if (sort__need_collapse) 892 root = &leader->entries_collapsed; 893 else 894 root = leader->entries_in; 895 896 for (nd = rb_first(root); nd; nd = rb_next(nd)) { 897 pos = rb_entry(nd, struct hist_entry, rb_node_in); 898 pair = hists__find_entry(other, pos); 899 900 if (pair) 901 hist_entry__add_pair(pair, pos); 902 } 903 } 904 905 /* 906 * Look for entries in the other hists that are not present in the leader, if 907 * we find them, just add a dummy entry on the leader hists, with period=0, 908 * nr_events=0, to serve as the list header. 909 */ 910 int hists__link(struct hists *leader, struct hists *other) 911 { 912 struct rb_root *root; 913 struct rb_node *nd; 914 struct hist_entry *pos, *pair; 915 916 if (sort__need_collapse) 917 root = &other->entries_collapsed; 918 else 919 root = other->entries_in; 920 921 for (nd = rb_first(root); nd; nd = rb_next(nd)) { 922 pos = rb_entry(nd, struct hist_entry, rb_node_in); 923 924 if (!hist_entry__has_pairs(pos)) { 925 pair = hists__add_dummy_entry(leader, pos); 926 if (pair == NULL) 927 return -1; 928 hist_entry__add_pair(pos, pair); 929 } 930 } 931 932 return 0; 933 } 934