1 // SPDX-License-Identifier: GPL-2.0 2 /* 3 * Copyright (C) 2009-2011, Frederic Weisbecker <fweisbec@gmail.com> 4 * 5 * Handle the callchains from the stream in an ad-hoc radix tree and then 6 * sort them in an rbtree. 7 * 8 * Using a radix for code path provides a fast retrieval and factorizes 9 * memory use. Also that lets us use the paths in a hierarchical graph view. 10 * 11 */ 12 13 #include <inttypes.h> 14 #include <stdlib.h> 15 #include <stdio.h> 16 #include <stdbool.h> 17 #include <errno.h> 18 #include <math.h> 19 #include <linux/string.h> 20 #include <linux/zalloc.h> 21 22 #include "asm/bug.h" 23 24 #include "debug.h" 25 #include "dso.h" 26 #include "event.h" 27 #include "hist.h" 28 #include "sort.h" 29 #include "machine.h" 30 #include "map.h" 31 #include "callchain.h" 32 #include "branch.h" 33 #include "symbol.h" 34 #include "util.h" 35 #include "../perf.h" 36 37 #define CALLCHAIN_PARAM_DEFAULT \ 38 .mode = CHAIN_GRAPH_ABS, \ 39 .min_percent = 0.5, \ 40 .order = ORDER_CALLEE, \ 41 .key = CCKEY_FUNCTION, \ 42 .value = CCVAL_PERCENT, \ 43 44 struct callchain_param callchain_param = { 45 CALLCHAIN_PARAM_DEFAULT 46 }; 47 48 /* 49 * Are there any events usind DWARF callchains? 50 * 51 * I.e. 52 * 53 * -e cycles/call-graph=dwarf/ 54 */ 55 bool dwarf_callchain_users; 56 57 struct callchain_param callchain_param_default = { 58 CALLCHAIN_PARAM_DEFAULT 59 }; 60 61 /* Used for thread-local struct callchain_cursor. */ 62 static pthread_key_t callchain_cursor; 63 64 int parse_callchain_record_opt(const char *arg, struct callchain_param *param) 65 { 66 return parse_callchain_record(arg, param); 67 } 68 69 static int parse_callchain_mode(const char *value) 70 { 71 if (!strncmp(value, "graph", strlen(value))) { 72 callchain_param.mode = CHAIN_GRAPH_ABS; 73 return 0; 74 } 75 if (!strncmp(value, "flat", strlen(value))) { 76 callchain_param.mode = CHAIN_FLAT; 77 return 0; 78 } 79 if (!strncmp(value, "fractal", strlen(value))) { 80 callchain_param.mode = CHAIN_GRAPH_REL; 81 return 0; 82 } 83 if (!strncmp(value, "folded", strlen(value))) { 84 callchain_param.mode = CHAIN_FOLDED; 85 return 0; 86 } 87 return -1; 88 } 89 90 static int parse_callchain_order(const char *value) 91 { 92 if (!strncmp(value, "caller", strlen(value))) { 93 callchain_param.order = ORDER_CALLER; 94 callchain_param.order_set = true; 95 return 0; 96 } 97 if (!strncmp(value, "callee", strlen(value))) { 98 callchain_param.order = ORDER_CALLEE; 99 callchain_param.order_set = true; 100 return 0; 101 } 102 return -1; 103 } 104 105 static int parse_callchain_sort_key(const char *value) 106 { 107 if (!strncmp(value, "function", strlen(value))) { 108 callchain_param.key = CCKEY_FUNCTION; 109 return 0; 110 } 111 if (!strncmp(value, "address", strlen(value))) { 112 callchain_param.key = CCKEY_ADDRESS; 113 return 0; 114 } 115 if (!strncmp(value, "srcline", strlen(value))) { 116 callchain_param.key = CCKEY_SRCLINE; 117 return 0; 118 } 119 if (!strncmp(value, "branch", strlen(value))) { 120 callchain_param.branch_callstack = 1; 121 return 0; 122 } 123 return -1; 124 } 125 126 static int parse_callchain_value(const char *value) 127 { 128 if (!strncmp(value, "percent", strlen(value))) { 129 callchain_param.value = CCVAL_PERCENT; 130 return 0; 131 } 132 if (!strncmp(value, "period", strlen(value))) { 133 callchain_param.value = CCVAL_PERIOD; 134 return 0; 135 } 136 if (!strncmp(value, "count", strlen(value))) { 137 callchain_param.value = CCVAL_COUNT; 138 return 0; 139 } 140 return -1; 141 } 142 143 static int get_stack_size(const char *str, unsigned long *_size) 144 { 145 char *endptr; 146 unsigned long size; 147 unsigned long max_size = round_down(USHRT_MAX, sizeof(u64)); 148 149 size = strtoul(str, &endptr, 0); 150 151 do { 152 if (*endptr) 153 break; 154 155 size = round_up(size, sizeof(u64)); 156 if (!size || size > max_size) 157 break; 158 159 *_size = size; 160 return 0; 161 162 } while (0); 163 164 pr_err("callchain: Incorrect stack dump size (max %ld): %s\n", 165 max_size, str); 166 return -1; 167 } 168 169 static int 170 __parse_callchain_report_opt(const char *arg, bool allow_record_opt) 171 { 172 char *tok; 173 char *endptr, *saveptr = NULL; 174 bool minpcnt_set = false; 175 bool record_opt_set = false; 176 bool try_stack_size = false; 177 178 callchain_param.enabled = true; 179 symbol_conf.use_callchain = true; 180 181 if (!arg) 182 return 0; 183 184 while ((tok = strtok_r((char *)arg, ",", &saveptr)) != NULL) { 185 if (!strncmp(tok, "none", strlen(tok))) { 186 callchain_param.mode = CHAIN_NONE; 187 callchain_param.enabled = false; 188 symbol_conf.use_callchain = false; 189 return 0; 190 } 191 192 if (!parse_callchain_mode(tok) || 193 !parse_callchain_order(tok) || 194 !parse_callchain_sort_key(tok) || 195 !parse_callchain_value(tok)) { 196 /* parsing ok - move on to the next */ 197 try_stack_size = false; 198 goto next; 199 } else if (allow_record_opt && !record_opt_set) { 200 if (parse_callchain_record(tok, &callchain_param)) 201 goto try_numbers; 202 203 /* assume that number followed by 'dwarf' is stack size */ 204 if (callchain_param.record_mode == CALLCHAIN_DWARF) 205 try_stack_size = true; 206 207 record_opt_set = true; 208 goto next; 209 } 210 211 try_numbers: 212 if (try_stack_size) { 213 unsigned long size = 0; 214 215 if (get_stack_size(tok, &size) < 0) 216 return -1; 217 callchain_param.dump_size = size; 218 try_stack_size = false; 219 } else if (!minpcnt_set) { 220 /* try to get the min percent */ 221 callchain_param.min_percent = strtod(tok, &endptr); 222 if (tok == endptr) 223 return -1; 224 minpcnt_set = true; 225 } else { 226 /* try print limit at last */ 227 callchain_param.print_limit = strtoul(tok, &endptr, 0); 228 if (tok == endptr) 229 return -1; 230 } 231 next: 232 arg = NULL; 233 } 234 235 if (callchain_register_param(&callchain_param) < 0) { 236 pr_err("Can't register callchain params\n"); 237 return -1; 238 } 239 return 0; 240 } 241 242 int parse_callchain_report_opt(const char *arg) 243 { 244 return __parse_callchain_report_opt(arg, false); 245 } 246 247 int parse_callchain_top_opt(const char *arg) 248 { 249 return __parse_callchain_report_opt(arg, true); 250 } 251 252 int parse_callchain_record(const char *arg, struct callchain_param *param) 253 { 254 char *tok, *name, *saveptr = NULL; 255 char *buf; 256 int ret = -1; 257 258 /* We need buffer that we know we can write to. */ 259 buf = malloc(strlen(arg) + 1); 260 if (!buf) 261 return -ENOMEM; 262 263 strcpy(buf, arg); 264 265 tok = strtok_r((char *)buf, ",", &saveptr); 266 name = tok ? : (char *)buf; 267 268 do { 269 /* Framepointer style */ 270 if (!strncmp(name, "fp", sizeof("fp"))) { 271 ret = 0; 272 param->record_mode = CALLCHAIN_FP; 273 274 tok = strtok_r(NULL, ",", &saveptr); 275 if (tok) { 276 unsigned long size; 277 278 if (!strncmp(tok, "defer", sizeof("defer"))) { 279 param->defer = true; 280 } else { 281 size = strtoul(tok, &name, 0); 282 if (size < (unsigned) sysctl__max_stack()) 283 param->max_stack = size; 284 } 285 } 286 break; 287 288 /* Dwarf style */ 289 } else if (!strncmp(name, "dwarf", sizeof("dwarf"))) { 290 const unsigned long default_stack_dump_size = 8192; 291 292 ret = 0; 293 param->record_mode = CALLCHAIN_DWARF; 294 param->dump_size = default_stack_dump_size; 295 dwarf_callchain_users = true; 296 297 tok = strtok_r(NULL, ",", &saveptr); 298 if (tok) { 299 unsigned long size = 0; 300 301 ret = get_stack_size(tok, &size); 302 param->dump_size = size; 303 } 304 } else if (!strncmp(name, "lbr", sizeof("lbr"))) { 305 if (!strtok_r(NULL, ",", &saveptr)) { 306 param->record_mode = CALLCHAIN_LBR; 307 ret = 0; 308 } else 309 pr_err("callchain: No more arguments " 310 "needed for --call-graph lbr\n"); 311 break; 312 } else { 313 pr_err("callchain: Unknown --call-graph option " 314 "value: %s\n", arg); 315 break; 316 } 317 318 } while (0); 319 320 free(buf); 321 322 if (param->defer && param->record_mode != CALLCHAIN_FP) { 323 pr_err("callchain: deferred callchain only works with FP\n"); 324 return -EINVAL; 325 } 326 327 return ret; 328 } 329 330 int perf_callchain_config(const char *var, const char *value) 331 { 332 char *endptr; 333 334 if (!strstarts(var, "call-graph.")) 335 return 0; 336 var += sizeof("call-graph.") - 1; 337 338 if (!strcmp(var, "record-mode")) 339 return parse_callchain_record_opt(value, &callchain_param); 340 if (!strcmp(var, "dump-size")) { 341 unsigned long size = 0; 342 int ret; 343 344 ret = get_stack_size(value, &size); 345 callchain_param.dump_size = size; 346 347 return ret; 348 } 349 if (!strcmp(var, "print-type")){ 350 int ret; 351 ret = parse_callchain_mode(value); 352 if (ret == -1) 353 pr_err("Invalid callchain mode: %s\n", value); 354 return ret; 355 } 356 if (!strcmp(var, "order")){ 357 int ret; 358 ret = parse_callchain_order(value); 359 if (ret == -1) 360 pr_err("Invalid callchain order: %s\n", value); 361 return ret; 362 } 363 if (!strcmp(var, "sort-key")){ 364 int ret; 365 ret = parse_callchain_sort_key(value); 366 if (ret == -1) 367 pr_err("Invalid callchain sort key: %s\n", value); 368 return ret; 369 } 370 if (!strcmp(var, "threshold")) { 371 callchain_param.min_percent = strtod(value, &endptr); 372 if (value == endptr) { 373 pr_err("Invalid callchain threshold: %s\n", value); 374 return -1; 375 } 376 } 377 if (!strcmp(var, "print-limit")) { 378 callchain_param.print_limit = strtod(value, &endptr); 379 if (value == endptr) { 380 pr_err("Invalid callchain print limit: %s\n", value); 381 return -1; 382 } 383 } 384 385 return 0; 386 } 387 388 static void 389 rb_insert_callchain(struct rb_root *root, struct callchain_node *chain, 390 enum chain_mode mode) 391 { 392 struct rb_node **p = &root->rb_node; 393 struct rb_node *parent = NULL; 394 struct callchain_node *rnode; 395 u64 chain_cumul = callchain_cumul_hits(chain); 396 397 while (*p) { 398 u64 rnode_cumul; 399 400 parent = *p; 401 rnode = rb_entry(parent, struct callchain_node, rb_node); 402 rnode_cumul = callchain_cumul_hits(rnode); 403 404 switch (mode) { 405 case CHAIN_FLAT: 406 case CHAIN_FOLDED: 407 if (rnode->hit < chain->hit) 408 p = &(*p)->rb_left; 409 else 410 p = &(*p)->rb_right; 411 break; 412 case CHAIN_GRAPH_ABS: /* Falldown */ 413 case CHAIN_GRAPH_REL: 414 if (rnode_cumul < chain_cumul) 415 p = &(*p)->rb_left; 416 else 417 p = &(*p)->rb_right; 418 break; 419 case CHAIN_NONE: 420 default: 421 break; 422 } 423 } 424 425 rb_link_node(&chain->rb_node, parent, p); 426 rb_insert_color(&chain->rb_node, root); 427 } 428 429 static void 430 __sort_chain_flat(struct rb_root *rb_root, struct callchain_node *node, 431 u64 min_hit) 432 { 433 struct rb_node *n; 434 struct callchain_node *child; 435 436 n = rb_first(&node->rb_root_in); 437 while (n) { 438 child = rb_entry(n, struct callchain_node, rb_node_in); 439 n = rb_next(n); 440 441 __sort_chain_flat(rb_root, child, min_hit); 442 } 443 444 if (node->hit && node->hit >= min_hit) 445 rb_insert_callchain(rb_root, node, CHAIN_FLAT); 446 } 447 448 /* 449 * Once we get every callchains from the stream, we can now 450 * sort them by hit 451 */ 452 static void 453 sort_chain_flat(struct rb_root *rb_root, struct callchain_root *root, 454 u64 min_hit, struct callchain_param *param __maybe_unused) 455 { 456 *rb_root = RB_ROOT; 457 __sort_chain_flat(rb_root, &root->node, min_hit); 458 } 459 460 static void __sort_chain_graph_abs(struct callchain_node *node, 461 u64 min_hit) 462 { 463 struct rb_node *n; 464 struct callchain_node *child; 465 466 node->rb_root = RB_ROOT; 467 n = rb_first(&node->rb_root_in); 468 469 while (n) { 470 child = rb_entry(n, struct callchain_node, rb_node_in); 471 n = rb_next(n); 472 473 __sort_chain_graph_abs(child, min_hit); 474 if (callchain_cumul_hits(child) >= min_hit) 475 rb_insert_callchain(&node->rb_root, child, 476 CHAIN_GRAPH_ABS); 477 } 478 } 479 480 static void 481 sort_chain_graph_abs(struct rb_root *rb_root, struct callchain_root *chain_root, 482 u64 min_hit, struct callchain_param *param __maybe_unused) 483 { 484 __sort_chain_graph_abs(&chain_root->node, min_hit); 485 rb_root->rb_node = chain_root->node.rb_root.rb_node; 486 } 487 488 static void __sort_chain_graph_rel(struct callchain_node *node, 489 double min_percent) 490 { 491 struct rb_node *n; 492 struct callchain_node *child; 493 u64 min_hit; 494 495 node->rb_root = RB_ROOT; 496 min_hit = ceil(node->children_hit * min_percent); 497 498 n = rb_first(&node->rb_root_in); 499 while (n) { 500 child = rb_entry(n, struct callchain_node, rb_node_in); 501 n = rb_next(n); 502 503 __sort_chain_graph_rel(child, min_percent); 504 if (callchain_cumul_hits(child) >= min_hit) 505 rb_insert_callchain(&node->rb_root, child, 506 CHAIN_GRAPH_REL); 507 } 508 } 509 510 static void 511 sort_chain_graph_rel(struct rb_root *rb_root, struct callchain_root *chain_root, 512 u64 min_hit __maybe_unused, struct callchain_param *param) 513 { 514 __sort_chain_graph_rel(&chain_root->node, param->min_percent / 100.0); 515 rb_root->rb_node = chain_root->node.rb_root.rb_node; 516 } 517 518 int callchain_register_param(struct callchain_param *param) 519 { 520 switch (param->mode) { 521 case CHAIN_GRAPH_ABS: 522 param->sort = sort_chain_graph_abs; 523 break; 524 case CHAIN_GRAPH_REL: 525 param->sort = sort_chain_graph_rel; 526 break; 527 case CHAIN_FLAT: 528 case CHAIN_FOLDED: 529 param->sort = sort_chain_flat; 530 break; 531 case CHAIN_NONE: 532 default: 533 return -1; 534 } 535 return 0; 536 } 537 538 /* 539 * Create a child for a parent. If inherit_children, then the new child 540 * will become the new parent of it's parent children 541 */ 542 static struct callchain_node * 543 create_child(struct callchain_node *parent, bool inherit_children) 544 { 545 struct callchain_node *new; 546 547 new = zalloc(sizeof(*new)); 548 if (!new) { 549 perror("not enough memory to create child for code path tree"); 550 return NULL; 551 } 552 new->parent = parent; 553 INIT_LIST_HEAD(&new->val); 554 INIT_LIST_HEAD(&new->parent_val); 555 556 if (inherit_children) { 557 struct rb_node *n; 558 struct callchain_node *child; 559 560 new->rb_root_in = parent->rb_root_in; 561 parent->rb_root_in = RB_ROOT; 562 563 n = rb_first(&new->rb_root_in); 564 while (n) { 565 child = rb_entry(n, struct callchain_node, rb_node_in); 566 child->parent = new; 567 n = rb_next(n); 568 } 569 570 /* make it the first child */ 571 rb_link_node(&new->rb_node_in, NULL, &parent->rb_root_in.rb_node); 572 rb_insert_color(&new->rb_node_in, &parent->rb_root_in); 573 } 574 575 return new; 576 } 577 578 579 /* 580 * Fill the node with callchain values 581 */ 582 static int 583 fill_node(struct callchain_node *node, struct callchain_cursor *cursor) 584 { 585 struct callchain_cursor_node *cursor_node; 586 587 node->val_nr = cursor->nr - cursor->pos; 588 if (!node->val_nr) 589 pr_warning("Warning: empty node in callchain tree\n"); 590 591 cursor_node = callchain_cursor_current(cursor); 592 593 while (cursor_node) { 594 struct callchain_list *call; 595 596 call = zalloc(sizeof(*call)); 597 if (!call) { 598 perror("not enough memory for the code path tree"); 599 return -ENOMEM; 600 } 601 call->ip = cursor_node->ip; 602 map_symbol__copy(&call->ms, &cursor_node->ms); 603 call->srcline = cursor_node->srcline; 604 605 if (cursor_node->branch) { 606 call->branch_count = 1; 607 608 if (cursor_node->branch_from) { 609 /* 610 * branch_from is set with value somewhere else 611 * to imply it's "to" of a branch. 612 */ 613 if (!call->brtype_stat) { 614 call->brtype_stat = zalloc(sizeof(*call->brtype_stat)); 615 if (!call->brtype_stat) { 616 perror("not enough memory for the code path branch statistics"); 617 zfree(&call->brtype_stat); 618 return -ENOMEM; 619 } 620 } 621 call->brtype_stat->branch_to = true; 622 623 if (cursor_node->branch_flags.predicted) 624 call->predicted_count = 1; 625 626 if (cursor_node->branch_flags.abort) 627 call->abort_count = 1; 628 629 branch_type_count(call->brtype_stat, 630 &cursor_node->branch_flags, 631 cursor_node->branch_from, 632 cursor_node->ip); 633 } else { 634 /* 635 * It's "from" of a branch 636 */ 637 if (call->brtype_stat && call->brtype_stat->branch_to) 638 call->brtype_stat->branch_to = false; 639 call->cycles_count = 640 cursor_node->branch_flags.cycles; 641 call->iter_count = cursor_node->nr_loop_iter; 642 call->iter_cycles = cursor_node->iter_cycles; 643 } 644 } 645 646 list_add_tail(&call->list, &node->val); 647 648 callchain_cursor_advance(cursor); 649 cursor_node = callchain_cursor_current(cursor); 650 } 651 return 0; 652 } 653 654 static struct callchain_node * 655 add_child(struct callchain_node *parent, 656 struct callchain_cursor *cursor, 657 u64 period) 658 { 659 struct callchain_node *new; 660 661 new = create_child(parent, false); 662 if (new == NULL) 663 return NULL; 664 665 if (fill_node(new, cursor) < 0) { 666 struct callchain_list *call, *tmp; 667 668 list_for_each_entry_safe(call, tmp, &new->val, list) { 669 list_del_init(&call->list); 670 map_symbol__exit(&call->ms); 671 zfree(&call->brtype_stat); 672 free(call); 673 } 674 free(new); 675 return NULL; 676 } 677 678 new->children_hit = 0; 679 new->hit = period; 680 new->children_count = 0; 681 new->count = 1; 682 return new; 683 } 684 685 enum match_result { 686 MATCH_ERROR = -1, 687 MATCH_EQ, 688 MATCH_LT, 689 MATCH_GT, 690 }; 691 692 static enum match_result match_chain_strings(const char *left, 693 const char *right) 694 { 695 enum match_result ret = MATCH_EQ; 696 int cmp; 697 698 if (left && right) 699 cmp = strcmp(left, right); 700 else if (!left && right) 701 cmp = 1; 702 else if (left && !right) 703 cmp = -1; 704 else 705 return MATCH_ERROR; 706 707 if (cmp != 0) 708 ret = cmp < 0 ? MATCH_LT : MATCH_GT; 709 710 return ret; 711 } 712 713 /* 714 * We need to always use relative addresses because we're aggregating 715 * callchains from multiple threads, i.e. different address spaces, so 716 * comparing absolute addresses make no sense as a symbol in a DSO may end up 717 * in a different address when used in a different binary or even the same 718 * binary but with some sort of address randomization technique, thus we need 719 * to compare just relative addresses. -acme 720 */ 721 static enum match_result match_chain_dso_addresses(struct map *left_map, u64 left_ip, 722 struct map *right_map, u64 right_ip) 723 { 724 struct dso *left_dso = left_map ? map__dso(left_map) : NULL; 725 struct dso *right_dso = right_map ? map__dso(right_map) : NULL; 726 727 if (left_dso != right_dso) 728 return left_dso < right_dso ? MATCH_LT : MATCH_GT; 729 730 if (left_ip != right_ip) 731 return left_ip < right_ip ? MATCH_LT : MATCH_GT; 732 733 return MATCH_EQ; 734 } 735 736 static enum match_result match_chain(struct callchain_cursor_node *node, 737 struct callchain_list *cnode) 738 { 739 enum match_result match = MATCH_ERROR; 740 741 switch (callchain_param.key) { 742 case CCKEY_SRCLINE: 743 match = match_chain_strings(cnode->srcline, node->srcline); 744 if (match != MATCH_ERROR) 745 break; 746 /* otherwise fall-back to symbol-based comparison below */ 747 fallthrough; 748 case CCKEY_FUNCTION: 749 if (node->ms.sym && cnode->ms.sym) { 750 /* 751 * Compare inlined frames based on their symbol name 752 * because different inlined frames will have the same 753 * symbol start. Otherwise do a faster comparison based 754 * on the symbol start address. 755 */ 756 if (cnode->ms.sym->inlined || node->ms.sym->inlined) { 757 match = match_chain_strings(cnode->ms.sym->name, 758 node->ms.sym->name); 759 if (match != MATCH_ERROR) 760 break; 761 } else { 762 match = match_chain_dso_addresses(cnode->ms.map, cnode->ms.sym->start, 763 node->ms.map, node->ms.sym->start); 764 break; 765 } 766 } 767 /* otherwise fall-back to IP-based comparison below */ 768 fallthrough; 769 case CCKEY_ADDRESS: 770 default: 771 match = match_chain_dso_addresses(cnode->ms.map, cnode->ip, node->ms.map, node->ip); 772 break; 773 } 774 775 if (match == MATCH_EQ && node->branch) { 776 cnode->branch_count++; 777 778 if (node->branch_from) { 779 /* 780 * It's "to" of a branch 781 */ 782 if (!cnode->brtype_stat) { 783 cnode->brtype_stat = zalloc(sizeof(*cnode->brtype_stat)); 784 if (!cnode->brtype_stat) { 785 perror("not enough memory for the code path branch statistics"); 786 return MATCH_ERROR; 787 } 788 } 789 cnode->brtype_stat->branch_to = true; 790 791 if (node->branch_flags.predicted) 792 cnode->predicted_count++; 793 794 if (node->branch_flags.abort) 795 cnode->abort_count++; 796 797 branch_type_count(cnode->brtype_stat, 798 &node->branch_flags, 799 node->branch_from, 800 node->ip); 801 } else { 802 /* 803 * It's "from" of a branch 804 */ 805 if (cnode->brtype_stat && cnode->brtype_stat->branch_to) 806 cnode->brtype_stat->branch_to = false; 807 cnode->cycles_count += node->branch_flags.cycles; 808 cnode->iter_count += node->nr_loop_iter; 809 cnode->iter_cycles += node->iter_cycles; 810 cnode->from_count++; 811 } 812 } 813 814 return match; 815 } 816 817 /* 818 * Split the parent in two parts (a new child is created) and 819 * give a part of its callchain to the created child. 820 * Then create another child to host the given callchain of new branch 821 */ 822 static int 823 split_add_child(struct callchain_node *parent, 824 struct callchain_cursor *cursor, 825 struct callchain_list *to_split, 826 u64 idx_parents, u64 idx_local, u64 period) 827 { 828 struct callchain_node *new; 829 struct list_head *old_tail; 830 unsigned int idx_total = idx_parents + idx_local; 831 832 /* split */ 833 new = create_child(parent, true); 834 if (new == NULL) 835 return -1; 836 837 /* split the callchain and move a part to the new child */ 838 old_tail = parent->val.prev; 839 list_del_range(&to_split->list, old_tail); 840 new->val.next = &to_split->list; 841 new->val.prev = old_tail; 842 to_split->list.prev = &new->val; 843 old_tail->next = &new->val; 844 845 /* split the hits */ 846 new->hit = parent->hit; 847 new->children_hit = parent->children_hit; 848 parent->children_hit = callchain_cumul_hits(new); 849 new->val_nr = parent->val_nr - idx_local; 850 parent->val_nr = idx_local; 851 new->count = parent->count; 852 new->children_count = parent->children_count; 853 parent->children_count = callchain_cumul_counts(new); 854 855 /* create a new child for the new branch if any */ 856 if (idx_total < cursor->nr) { 857 struct callchain_node *first; 858 struct callchain_list *cnode; 859 struct callchain_cursor_node *node; 860 struct rb_node *p, **pp; 861 862 parent->hit = 0; 863 parent->children_hit += period; 864 parent->count = 0; 865 parent->children_count += 1; 866 867 node = callchain_cursor_current(cursor); 868 new = add_child(parent, cursor, period); 869 if (new == NULL) 870 return -1; 871 872 /* 873 * This is second child since we moved parent's children 874 * to new (first) child above. 875 */ 876 p = parent->rb_root_in.rb_node; 877 first = rb_entry(p, struct callchain_node, rb_node_in); 878 cnode = list_first_entry(&first->val, struct callchain_list, 879 list); 880 881 if (match_chain(node, cnode) == MATCH_LT) 882 pp = &p->rb_left; 883 else 884 pp = &p->rb_right; 885 886 rb_link_node(&new->rb_node_in, p, pp); 887 rb_insert_color(&new->rb_node_in, &parent->rb_root_in); 888 } else { 889 parent->hit = period; 890 parent->count = 1; 891 } 892 return 0; 893 } 894 895 static enum match_result 896 append_chain(struct callchain_node *root, 897 struct callchain_cursor *cursor, 898 u64 period); 899 900 static int 901 append_chain_children(struct callchain_node *root, 902 struct callchain_cursor *cursor, 903 u64 period) 904 { 905 struct callchain_node *rnode; 906 struct callchain_cursor_node *node; 907 struct rb_node **p = &root->rb_root_in.rb_node; 908 struct rb_node *parent = NULL; 909 910 node = callchain_cursor_current(cursor); 911 if (!node) 912 return -1; 913 914 /* lookup in children */ 915 while (*p) { 916 enum match_result ret; 917 918 parent = *p; 919 rnode = rb_entry(parent, struct callchain_node, rb_node_in); 920 921 /* If at least first entry matches, rely to children */ 922 ret = append_chain(rnode, cursor, period); 923 if (ret == MATCH_EQ) 924 goto inc_children_hit; 925 if (ret == MATCH_ERROR) 926 return -1; 927 928 if (ret == MATCH_LT) 929 p = &parent->rb_left; 930 else 931 p = &parent->rb_right; 932 } 933 /* nothing in children, add to the current node */ 934 rnode = add_child(root, cursor, period); 935 if (rnode == NULL) 936 return -1; 937 938 rb_link_node(&rnode->rb_node_in, parent, p); 939 rb_insert_color(&rnode->rb_node_in, &root->rb_root_in); 940 941 inc_children_hit: 942 root->children_hit += period; 943 root->children_count++; 944 return 0; 945 } 946 947 static enum match_result 948 append_chain(struct callchain_node *root, 949 struct callchain_cursor *cursor, 950 u64 period) 951 { 952 struct callchain_list *cnode; 953 u64 start = cursor->pos; 954 bool found = false; 955 u64 matches; 956 enum match_result cmp = MATCH_ERROR; 957 958 /* 959 * Lookup in the current node 960 * If we have a symbol, then compare the start to match 961 * anywhere inside a function, unless function 962 * mode is disabled. 963 */ 964 list_for_each_entry(cnode, &root->val, list) { 965 struct callchain_cursor_node *node; 966 967 node = callchain_cursor_current(cursor); 968 if (!node) 969 break; 970 971 cmp = match_chain(node, cnode); 972 if (cmp != MATCH_EQ) 973 break; 974 975 found = true; 976 977 callchain_cursor_advance(cursor); 978 } 979 980 /* matches not, relay no the parent */ 981 if (!found) { 982 WARN_ONCE(cmp == MATCH_ERROR, "Chain comparison error\n"); 983 return cmp; 984 } 985 986 matches = cursor->pos - start; 987 988 /* we match only a part of the node. Split it and add the new chain */ 989 if (matches < root->val_nr) { 990 if (split_add_child(root, cursor, cnode, start, matches, 991 period) < 0) 992 return MATCH_ERROR; 993 994 return MATCH_EQ; 995 } 996 997 /* we match 100% of the path, increment the hit */ 998 if (matches == root->val_nr && cursor->pos == cursor->nr) { 999 root->hit += period; 1000 root->count++; 1001 return MATCH_EQ; 1002 } 1003 1004 /* We match the node and still have a part remaining */ 1005 if (append_chain_children(root, cursor, period) < 0) 1006 return MATCH_ERROR; 1007 1008 return MATCH_EQ; 1009 } 1010 1011 int callchain_append(struct callchain_root *root, 1012 struct callchain_cursor *cursor, 1013 u64 period) 1014 { 1015 if (cursor == NULL) 1016 return -1; 1017 1018 if (!cursor->nr) 1019 return 0; 1020 1021 callchain_cursor_commit(cursor); 1022 1023 if (append_chain_children(&root->node, cursor, period) < 0) 1024 return -1; 1025 1026 if (cursor->nr > root->max_depth) 1027 root->max_depth = cursor->nr; 1028 1029 return 0; 1030 } 1031 1032 static int 1033 merge_chain_branch(struct callchain_cursor *cursor, 1034 struct callchain_node *dst, struct callchain_node *src) 1035 { 1036 struct callchain_cursor_node **old_last = cursor->last; 1037 struct callchain_node *child; 1038 struct callchain_list *list, *next_list; 1039 struct rb_node *n; 1040 int old_pos = cursor->nr; 1041 int err = 0; 1042 1043 list_for_each_entry_safe(list, next_list, &src->val, list) { 1044 struct map_symbol ms = { 1045 .maps = maps__get(list->ms.maps), 1046 .map = map__get(list->ms.map), 1047 }; 1048 callchain_cursor_append(cursor, list->ip, &ms, false, NULL, 0, 0, 0, list->srcline); 1049 list_del_init(&list->list); 1050 map_symbol__exit(&ms); 1051 map_symbol__exit(&list->ms); 1052 zfree(&list->brtype_stat); 1053 free(list); 1054 } 1055 1056 if (src->hit) { 1057 callchain_cursor_commit(cursor); 1058 if (append_chain_children(dst, cursor, src->hit) < 0) 1059 return -1; 1060 } 1061 1062 n = rb_first(&src->rb_root_in); 1063 while (n) { 1064 child = container_of(n, struct callchain_node, rb_node_in); 1065 n = rb_next(n); 1066 rb_erase(&child->rb_node_in, &src->rb_root_in); 1067 1068 err = merge_chain_branch(cursor, dst, child); 1069 if (err) 1070 break; 1071 1072 free(child); 1073 } 1074 1075 cursor->nr = old_pos; 1076 cursor->last = old_last; 1077 1078 return err; 1079 } 1080 1081 int callchain_merge(struct callchain_cursor *cursor, 1082 struct callchain_root *dst, struct callchain_root *src) 1083 { 1084 return merge_chain_branch(cursor, &dst->node, &src->node); 1085 } 1086 1087 int callchain_cursor_append(struct callchain_cursor *cursor, 1088 u64 ip, struct map_symbol *ms, 1089 bool branch, struct branch_flags *flags, 1090 int nr_loop_iter, u64 iter_cycles, u64 branch_from, 1091 const char *srcline) 1092 { 1093 struct callchain_cursor_node *node = *cursor->last; 1094 1095 if (!node) { 1096 node = calloc(1, sizeof(*node)); 1097 if (!node) 1098 return -ENOMEM; 1099 1100 *cursor->last = node; 1101 } 1102 1103 node->ip = ip; 1104 map_symbol__exit(&node->ms); 1105 map_symbol__copy(&node->ms, ms); 1106 node->branch = branch; 1107 node->nr_loop_iter = nr_loop_iter; 1108 node->iter_cycles = iter_cycles; 1109 node->srcline = srcline; 1110 1111 if (flags) 1112 memcpy(&node->branch_flags, flags, 1113 sizeof(struct branch_flags)); 1114 1115 node->branch_from = branch_from; 1116 cursor->nr++; 1117 1118 cursor->last = &node->next; 1119 1120 return 0; 1121 } 1122 1123 int sample__resolve_callchain(struct perf_sample *sample, 1124 struct callchain_cursor *cursor, struct symbol **parent, 1125 struct evsel *evsel, struct addr_location *al, 1126 int max_stack) 1127 { 1128 if (sample->callchain == NULL && !symbol_conf.show_branchflag_count) 1129 return 0; 1130 1131 if (symbol_conf.use_callchain || symbol_conf.cumulate_callchain || 1132 perf_hpp_list.parent || symbol_conf.show_branchflag_count) { 1133 return thread__resolve_callchain(al->thread, cursor, evsel, sample, 1134 parent, al, max_stack); 1135 } 1136 return 0; 1137 } 1138 1139 int hist_entry__append_callchain(struct hist_entry *he, struct perf_sample *sample) 1140 { 1141 if ((!symbol_conf.use_callchain || sample->callchain == NULL) && 1142 !symbol_conf.show_branchflag_count) 1143 return 0; 1144 return callchain_append(he->callchain, get_tls_callchain_cursor(), sample->period); 1145 } 1146 1147 int fill_callchain_info(struct addr_location *al, struct callchain_cursor_node *node, 1148 bool hide_unresolved) 1149 { 1150 struct machine *machine = node->ms.maps ? maps__machine(node->ms.maps) : NULL; 1151 1152 maps__put(al->maps); 1153 al->maps = maps__get(node->ms.maps); 1154 map__put(al->map); 1155 al->map = map__get(node->ms.map); 1156 al->sym = node->ms.sym; 1157 al->srcline = node->srcline; 1158 al->addr = node->ip; 1159 1160 if (al->sym == NULL) { 1161 if (hide_unresolved) 1162 return 0; 1163 if (al->map == NULL) 1164 goto out; 1165 } 1166 if (maps__equal(al->maps, machine__kernel_maps(machine))) { 1167 if (machine__is_host(machine)) { 1168 al->cpumode = PERF_RECORD_MISC_KERNEL; 1169 al->level = 'k'; 1170 } else { 1171 al->cpumode = PERF_RECORD_MISC_GUEST_KERNEL; 1172 al->level = 'g'; 1173 } 1174 } else { 1175 if (machine__is_host(machine)) { 1176 al->cpumode = PERF_RECORD_MISC_USER; 1177 al->level = '.'; 1178 } else if (perf_guest) { 1179 al->cpumode = PERF_RECORD_MISC_GUEST_USER; 1180 al->level = 'u'; 1181 } else { 1182 al->cpumode = PERF_RECORD_MISC_HYPERVISOR; 1183 al->level = 'H'; 1184 } 1185 } 1186 1187 out: 1188 return 1; 1189 } 1190 1191 char *callchain_list__sym_name(struct callchain_list *cl, 1192 char *bf, size_t bfsize, bool show_dso) 1193 { 1194 bool show_addr = callchain_param.key == CCKEY_ADDRESS; 1195 bool show_srcline = show_addr || callchain_param.key == CCKEY_SRCLINE; 1196 int printed; 1197 1198 if (cl->ms.sym) { 1199 const char *inlined = cl->ms.sym->inlined ? " (inlined)" : ""; 1200 1201 if (show_srcline && cl->srcline) 1202 printed = scnprintf(bf, bfsize, "%s %s%s", 1203 cl->ms.sym->name, cl->srcline, 1204 inlined); 1205 else 1206 printed = scnprintf(bf, bfsize, "%s%s", 1207 cl->ms.sym->name, inlined); 1208 } else 1209 printed = scnprintf(bf, bfsize, "%#" PRIx64, cl->ip); 1210 1211 if (show_dso) 1212 scnprintf(bf + printed, bfsize - printed, " %s", 1213 cl->ms.map ? 1214 dso__short_name(map__dso(cl->ms.map)) : 1215 "unknown"); 1216 1217 return bf; 1218 } 1219 1220 char *callchain_node__scnprintf_value(struct callchain_node *node, 1221 char *bf, size_t bfsize, u64 total) 1222 { 1223 double percent = 0.0; 1224 u64 period = callchain_cumul_hits(node); 1225 unsigned count = callchain_cumul_counts(node); 1226 1227 if (callchain_param.mode == CHAIN_FOLDED) { 1228 period = node->hit; 1229 count = node->count; 1230 } 1231 1232 switch (callchain_param.value) { 1233 case CCVAL_PERIOD: 1234 scnprintf(bf, bfsize, "%"PRIu64, period); 1235 break; 1236 case CCVAL_COUNT: 1237 scnprintf(bf, bfsize, "%u", count); 1238 break; 1239 case CCVAL_PERCENT: 1240 default: 1241 if (total) 1242 percent = period * 100.0 / total; 1243 scnprintf(bf, bfsize, "%.2f%%", percent); 1244 break; 1245 } 1246 return bf; 1247 } 1248 1249 int callchain_node__fprintf_value(struct callchain_node *node, 1250 FILE *fp, u64 total) 1251 { 1252 double percent = 0.0; 1253 u64 period = callchain_cumul_hits(node); 1254 unsigned count = callchain_cumul_counts(node); 1255 1256 if (callchain_param.mode == CHAIN_FOLDED) { 1257 period = node->hit; 1258 count = node->count; 1259 } 1260 1261 switch (callchain_param.value) { 1262 case CCVAL_PERIOD: 1263 return fprintf(fp, "%"PRIu64, period); 1264 case CCVAL_COUNT: 1265 return fprintf(fp, "%u", count); 1266 case CCVAL_PERCENT: 1267 default: 1268 if (total) 1269 percent = period * 100.0 / total; 1270 return percent_color_fprintf(fp, "%.2f%%", percent); 1271 } 1272 return 0; 1273 } 1274 1275 static void callchain_counts_value(struct callchain_node *node, 1276 u64 *branch_count, u64 *predicted_count, 1277 u64 *abort_count, u64 *cycles_count) 1278 { 1279 struct callchain_list *clist; 1280 1281 list_for_each_entry(clist, &node->val, list) { 1282 if (branch_count) 1283 *branch_count += clist->branch_count; 1284 1285 if (predicted_count) 1286 *predicted_count += clist->predicted_count; 1287 1288 if (abort_count) 1289 *abort_count += clist->abort_count; 1290 1291 if (cycles_count) 1292 *cycles_count += clist->cycles_count; 1293 } 1294 } 1295 1296 static int callchain_node_branch_counts_cumul(struct callchain_node *node, 1297 u64 *branch_count, 1298 u64 *predicted_count, 1299 u64 *abort_count, 1300 u64 *cycles_count) 1301 { 1302 struct callchain_node *child; 1303 struct rb_node *n; 1304 1305 n = rb_first(&node->rb_root_in); 1306 while (n) { 1307 child = rb_entry(n, struct callchain_node, rb_node_in); 1308 n = rb_next(n); 1309 1310 callchain_node_branch_counts_cumul(child, branch_count, 1311 predicted_count, 1312 abort_count, 1313 cycles_count); 1314 1315 callchain_counts_value(child, branch_count, 1316 predicted_count, abort_count, 1317 cycles_count); 1318 } 1319 1320 return 0; 1321 } 1322 1323 int callchain_branch_counts(struct callchain_root *root, 1324 u64 *branch_count, u64 *predicted_count, 1325 u64 *abort_count, u64 *cycles_count) 1326 { 1327 if (branch_count) 1328 *branch_count = 0; 1329 1330 if (predicted_count) 1331 *predicted_count = 0; 1332 1333 if (abort_count) 1334 *abort_count = 0; 1335 1336 if (cycles_count) 1337 *cycles_count = 0; 1338 1339 return callchain_node_branch_counts_cumul(&root->node, 1340 branch_count, 1341 predicted_count, 1342 abort_count, 1343 cycles_count); 1344 } 1345 1346 static int count_pri64_printf(int idx, const char *str, u64 value, char *bf, int bfsize) 1347 { 1348 return scnprintf(bf, bfsize, "%s%s:%" PRId64 "", (idx) ? " " : " (", str, value); 1349 } 1350 1351 static int count_float_printf(int idx, const char *str, float value, 1352 char *bf, int bfsize, float threshold) 1353 { 1354 if (threshold != 0.0 && value < threshold) 1355 return 0; 1356 1357 return scnprintf(bf, bfsize, "%s%s:%.1f%%", (idx) ? " " : " (", str, value); 1358 } 1359 1360 static int branch_to_str(char *bf, int bfsize, 1361 u64 branch_count, u64 predicted_count, 1362 u64 abort_count, 1363 const struct branch_type_stat *brtype_stat) 1364 { 1365 int printed, i = 0; 1366 1367 printed = branch_type_str(brtype_stat, bf, bfsize); 1368 if (printed) 1369 i++; 1370 1371 if (predicted_count < branch_count) { 1372 printed += count_float_printf(i++, "predicted", 1373 predicted_count * 100.0 / branch_count, 1374 bf + printed, bfsize - printed, 0.0); 1375 } 1376 1377 if (abort_count) { 1378 printed += count_float_printf(i++, "abort", 1379 abort_count * 100.0 / branch_count, 1380 bf + printed, bfsize - printed, 0.1); 1381 } 1382 1383 if (i) 1384 printed += scnprintf(bf + printed, bfsize - printed, ")"); 1385 1386 return printed; 1387 } 1388 1389 static int branch_from_str(char *bf, int bfsize, 1390 u64 branch_count, 1391 u64 cycles_count, u64 iter_count, 1392 u64 iter_cycles, u64 from_count) 1393 { 1394 int printed = 0, i = 0; 1395 u64 cycles, v = 0; 1396 1397 cycles = cycles_count / branch_count; 1398 if (cycles) { 1399 printed += count_pri64_printf(i++, "cycles", 1400 cycles, 1401 bf + printed, bfsize - printed); 1402 } 1403 1404 if (iter_count && from_count) { 1405 v = iter_count / from_count; 1406 if (v) { 1407 printed += count_pri64_printf(i++, "iter", 1408 v, bf + printed, bfsize - printed); 1409 1410 printed += count_pri64_printf(i++, "avg_cycles", 1411 iter_cycles / iter_count, 1412 bf + printed, bfsize - printed); 1413 } 1414 } 1415 1416 if (i) 1417 printed += scnprintf(bf + printed, bfsize - printed, ")"); 1418 1419 return printed; 1420 } 1421 1422 static int counts_str_build(char *bf, int bfsize, 1423 u64 branch_count, u64 predicted_count, 1424 u64 abort_count, u64 cycles_count, 1425 u64 iter_count, u64 iter_cycles, 1426 u64 from_count, 1427 const struct branch_type_stat *brtype_stat) 1428 { 1429 int printed; 1430 1431 if (branch_count == 0) 1432 return scnprintf(bf, bfsize, " (calltrace)"); 1433 1434 if (brtype_stat->branch_to) { 1435 printed = branch_to_str(bf, bfsize, branch_count, 1436 predicted_count, abort_count, brtype_stat); 1437 } else { 1438 printed = branch_from_str(bf, bfsize, branch_count, 1439 cycles_count, iter_count, iter_cycles, 1440 from_count); 1441 } 1442 1443 if (!printed) 1444 bf[0] = 0; 1445 1446 return printed; 1447 } 1448 1449 static int callchain_counts_printf(FILE *fp, char *bf, int bfsize, 1450 u64 branch_count, u64 predicted_count, 1451 u64 abort_count, u64 cycles_count, 1452 u64 iter_count, u64 iter_cycles, 1453 u64 from_count, 1454 const struct branch_type_stat *brtype_stat) 1455 { 1456 char str[256]; 1457 1458 counts_str_build(str, sizeof(str), branch_count, 1459 predicted_count, abort_count, cycles_count, 1460 iter_count, iter_cycles, from_count, brtype_stat); 1461 1462 if (fp) 1463 return fprintf(fp, "%s", str); 1464 1465 return scnprintf(bf, bfsize, "%s", str); 1466 } 1467 1468 int callchain_list_counts__printf_value(struct callchain_list *clist, 1469 FILE *fp, char *bf, int bfsize) 1470 { 1471 static const struct branch_type_stat empty_brtype_stat = {}; 1472 const struct branch_type_stat *brtype_stat; 1473 u64 branch_count, predicted_count; 1474 u64 abort_count, cycles_count; 1475 u64 iter_count, iter_cycles; 1476 u64 from_count; 1477 1478 brtype_stat = clist->brtype_stat ?: &empty_brtype_stat; 1479 branch_count = clist->branch_count; 1480 predicted_count = clist->predicted_count; 1481 abort_count = clist->abort_count; 1482 cycles_count = clist->cycles_count; 1483 iter_count = clist->iter_count; 1484 iter_cycles = clist->iter_cycles; 1485 from_count = clist->from_count; 1486 1487 return callchain_counts_printf(fp, bf, bfsize, branch_count, 1488 predicted_count, abort_count, 1489 cycles_count, iter_count, iter_cycles, 1490 from_count, brtype_stat); 1491 } 1492 1493 static void free_callchain_node(struct callchain_node *node) 1494 { 1495 struct callchain_list *list, *tmp; 1496 struct callchain_node *child; 1497 struct rb_node *n; 1498 1499 list_for_each_entry_safe(list, tmp, &node->parent_val, list) { 1500 list_del_init(&list->list); 1501 map_symbol__exit(&list->ms); 1502 zfree(&list->brtype_stat); 1503 free(list); 1504 } 1505 1506 list_for_each_entry_safe(list, tmp, &node->val, list) { 1507 list_del_init(&list->list); 1508 map_symbol__exit(&list->ms); 1509 zfree(&list->brtype_stat); 1510 free(list); 1511 } 1512 1513 n = rb_first(&node->rb_root_in); 1514 while (n) { 1515 child = container_of(n, struct callchain_node, rb_node_in); 1516 n = rb_next(n); 1517 rb_erase(&child->rb_node_in, &node->rb_root_in); 1518 1519 free_callchain_node(child); 1520 free(child); 1521 } 1522 } 1523 1524 void free_callchain(struct callchain_root *root) 1525 { 1526 if (!symbol_conf.use_callchain) 1527 return; 1528 1529 free_callchain_node(&root->node); 1530 } 1531 1532 static u64 decay_callchain_node(struct callchain_node *node) 1533 { 1534 struct callchain_node *child; 1535 struct rb_node *n; 1536 u64 child_hits = 0; 1537 1538 n = rb_first(&node->rb_root_in); 1539 while (n) { 1540 child = container_of(n, struct callchain_node, rb_node_in); 1541 1542 child_hits += decay_callchain_node(child); 1543 n = rb_next(n); 1544 } 1545 1546 node->hit = (node->hit * 7) / 8; 1547 node->children_hit = child_hits; 1548 1549 return node->hit; 1550 } 1551 1552 void decay_callchain(struct callchain_root *root) 1553 { 1554 if (!symbol_conf.use_callchain) 1555 return; 1556 1557 decay_callchain_node(&root->node); 1558 } 1559 1560 int callchain_node__make_parent_list(struct callchain_node *node) 1561 { 1562 struct callchain_node *parent = node->parent; 1563 struct callchain_list *chain, *new; 1564 LIST_HEAD(head); 1565 1566 while (parent) { 1567 list_for_each_entry_reverse(chain, &parent->val, list) { 1568 new = malloc(sizeof(*new)); 1569 if (new == NULL) 1570 goto out; 1571 *new = *chain; 1572 new->has_children = false; 1573 map_symbol__copy(&new->ms, &chain->ms); 1574 list_add_tail(&new->list, &head); 1575 } 1576 parent = parent->parent; 1577 } 1578 1579 list_for_each_entry_safe_reverse(chain, new, &head, list) 1580 list_move_tail(&chain->list, &node->parent_val); 1581 1582 if (!list_empty(&node->parent_val)) { 1583 chain = list_first_entry(&node->parent_val, struct callchain_list, list); 1584 chain->has_children = rb_prev(&node->rb_node) || rb_next(&node->rb_node); 1585 1586 chain = list_first_entry(&node->val, struct callchain_list, list); 1587 chain->has_children = false; 1588 } 1589 return 0; 1590 1591 out: 1592 list_for_each_entry_safe(chain, new, &head, list) { 1593 list_del_init(&chain->list); 1594 map_symbol__exit(&chain->ms); 1595 zfree(&chain->brtype_stat); 1596 free(chain); 1597 } 1598 return -ENOMEM; 1599 } 1600 1601 static void callchain_cursor__delete(void *vcursor) 1602 { 1603 struct callchain_cursor *cursor = vcursor; 1604 struct callchain_cursor_node *node, *next; 1605 1606 callchain_cursor_reset(cursor); 1607 for (node = cursor->first; node != NULL; node = next) { 1608 next = node->next; 1609 free(node); 1610 } 1611 free(cursor); 1612 } 1613 1614 static void init_callchain_cursor_key(void) 1615 { 1616 if (pthread_key_create(&callchain_cursor, callchain_cursor__delete)) { 1617 pr_err("callchain cursor creation failed"); 1618 abort(); 1619 } 1620 } 1621 1622 struct callchain_cursor *get_tls_callchain_cursor(void) 1623 { 1624 static pthread_once_t once_control = PTHREAD_ONCE_INIT; 1625 struct callchain_cursor *cursor; 1626 1627 pthread_once(&once_control, init_callchain_cursor_key); 1628 cursor = pthread_getspecific(callchain_cursor); 1629 if (!cursor) { 1630 cursor = zalloc(sizeof(*cursor)); 1631 if (!cursor) 1632 pr_debug3("%s: not enough memory\n", __func__); 1633 pthread_setspecific(callchain_cursor, cursor); 1634 } 1635 return cursor; 1636 } 1637 1638 int callchain_cursor__copy(struct callchain_cursor *dst, 1639 struct callchain_cursor *src) 1640 { 1641 int rc = 0; 1642 1643 callchain_cursor_reset(dst); 1644 callchain_cursor_commit(src); 1645 1646 while (true) { 1647 struct callchain_cursor_node *node; 1648 1649 node = callchain_cursor_current(src); 1650 if (node == NULL) 1651 break; 1652 1653 rc = callchain_cursor_append(dst, node->ip, &node->ms, 1654 node->branch, &node->branch_flags, 1655 node->nr_loop_iter, 1656 node->iter_cycles, 1657 node->branch_from, node->srcline); 1658 if (rc) 1659 break; 1660 1661 callchain_cursor_advance(src); 1662 } 1663 1664 return rc; 1665 } 1666 1667 /* 1668 * Initialize a cursor before adding entries inside, but keep 1669 * the previously allocated entries as a cache. 1670 */ 1671 void callchain_cursor_reset(struct callchain_cursor *cursor) 1672 { 1673 struct callchain_cursor_node *node; 1674 1675 cursor->nr = 0; 1676 cursor->last = &cursor->first; 1677 1678 for (node = cursor->first; node != NULL; node = node->next) 1679 map_symbol__exit(&node->ms); 1680 } 1681 1682 void callchain_param_setup(u64 sample_type, const char *arch) 1683 { 1684 if (symbol_conf.use_callchain || symbol_conf.cumulate_callchain) { 1685 if ((sample_type & PERF_SAMPLE_REGS_USER) && 1686 (sample_type & PERF_SAMPLE_STACK_USER)) { 1687 callchain_param.record_mode = CALLCHAIN_DWARF; 1688 dwarf_callchain_users = true; 1689 } else if (sample_type & PERF_SAMPLE_BRANCH_STACK) 1690 callchain_param.record_mode = CALLCHAIN_LBR; 1691 else 1692 callchain_param.record_mode = CALLCHAIN_FP; 1693 } 1694 1695 /* 1696 * It's necessary to use libunwind to reliably determine the caller of 1697 * a leaf function on aarch64, as otherwise we cannot know whether to 1698 * start from the LR or FP. 1699 * 1700 * Always starting from the LR can result in duplicate or entirely 1701 * erroneous entries. Always skipping the LR and starting from the FP 1702 * can result in missing entries. 1703 */ 1704 if (callchain_param.record_mode == CALLCHAIN_FP && !strcmp(arch, "arm64")) 1705 dwarf_callchain_users = true; 1706 } 1707 1708 static bool chain_match(struct callchain_list *base_chain, 1709 struct callchain_list *pair_chain) 1710 { 1711 enum match_result match; 1712 1713 match = match_chain_strings(base_chain->srcline, 1714 pair_chain->srcline); 1715 if (match != MATCH_ERROR) 1716 return match == MATCH_EQ; 1717 1718 match = match_chain_dso_addresses(base_chain->ms.map, 1719 base_chain->ip, 1720 pair_chain->ms.map, 1721 pair_chain->ip); 1722 1723 return match == MATCH_EQ; 1724 } 1725 1726 bool callchain_cnode_matched(struct callchain_node *base_cnode, 1727 struct callchain_node *pair_cnode) 1728 { 1729 struct callchain_list *base_chain, *pair_chain; 1730 bool match = false; 1731 1732 pair_chain = list_first_entry(&pair_cnode->val, 1733 struct callchain_list, 1734 list); 1735 1736 list_for_each_entry(base_chain, &base_cnode->val, list) { 1737 if (&pair_chain->list == &pair_cnode->val) 1738 return false; 1739 1740 if (!base_chain->srcline || !pair_chain->srcline) { 1741 pair_chain = list_next_entry(pair_chain, list); 1742 continue; 1743 } 1744 1745 match = chain_match(base_chain, pair_chain); 1746 if (!match) 1747 return false; 1748 1749 pair_chain = list_next_entry(pair_chain, list); 1750 } 1751 1752 /* 1753 * Say chain1 is ABC, chain2 is ABCD, we consider they are 1754 * not fully matched. 1755 */ 1756 if (pair_chain && (&pair_chain->list != &pair_cnode->val)) 1757 return false; 1758 1759 return match; 1760 } 1761 1762 static u64 count_callchain_hits(struct hist_entry *he) 1763 { 1764 struct rb_root *root = &he->sorted_chain; 1765 struct rb_node *rb_node = rb_first(root); 1766 struct callchain_node *node; 1767 u64 chain_hits = 0; 1768 1769 while (rb_node) { 1770 node = rb_entry(rb_node, struct callchain_node, rb_node); 1771 chain_hits += node->hit; 1772 rb_node = rb_next(rb_node); 1773 } 1774 1775 return chain_hits; 1776 } 1777 1778 u64 callchain_total_hits(struct hists *hists) 1779 { 1780 struct rb_node *next = rb_first_cached(&hists->entries); 1781 u64 chain_hits = 0; 1782 1783 while (next) { 1784 struct hist_entry *he = rb_entry(next, struct hist_entry, 1785 rb_node); 1786 1787 chain_hits += count_callchain_hits(he); 1788 next = rb_next(&he->rb_node); 1789 } 1790 1791 return chain_hits; 1792 } 1793 1794 s64 callchain_avg_cycles(struct callchain_node *cnode) 1795 { 1796 struct callchain_list *chain; 1797 s64 cycles = 0; 1798 1799 list_for_each_entry(chain, &cnode->val, list) { 1800 if (chain->srcline && chain->branch_count) 1801 cycles += chain->cycles_count / chain->branch_count; 1802 } 1803 1804 return cycles; 1805 } 1806 1807 int sample__for_each_callchain_node(struct thread *thread, struct evsel *evsel, 1808 struct perf_sample *sample, int max_stack, 1809 bool symbols, callchain_iter_fn cb, void *data) 1810 { 1811 struct callchain_cursor *cursor = get_tls_callchain_cursor(); 1812 int ret; 1813 1814 if (!cursor) 1815 return -ENOMEM; 1816 1817 /* Fill in the callchain. */ 1818 ret = __thread__resolve_callchain(thread, cursor, evsel, sample, 1819 /*parent=*/NULL, /*root_al=*/NULL, 1820 max_stack, symbols); 1821 if (ret) 1822 return ret; 1823 1824 /* Switch from writing the callchain to reading it. */ 1825 callchain_cursor_commit(cursor); 1826 1827 while (1) { 1828 struct callchain_cursor_node *node = callchain_cursor_current(cursor); 1829 1830 if (!node) 1831 break; 1832 1833 ret = cb(node, data); 1834 if (ret) 1835 return ret; 1836 1837 callchain_cursor_advance(cursor); 1838 } 1839 return 0; 1840 } 1841 1842 /* 1843 * This function merges earlier samples (@sample_orig) waiting for deferred 1844 * user callchains with the matching callchain record (@sample_callchain) 1845 * which is delivered now. The @sample_orig->callchain should be released 1846 * after use if ->deferred_callchain is set. 1847 */ 1848 int sample__merge_deferred_callchain(struct perf_sample *sample_orig, 1849 struct perf_sample *sample_callchain) 1850 { 1851 u64 nr_orig = sample_orig->callchain->nr - 1; 1852 u64 nr_deferred = sample_callchain->callchain->nr; 1853 struct ip_callchain *callchain; 1854 1855 if (sample_orig->callchain->nr < 2) { 1856 sample_orig->deferred_callchain = false; 1857 return -EINVAL; 1858 } 1859 1860 callchain = calloc(1 + nr_orig + nr_deferred, sizeof(u64)); 1861 if (callchain == NULL) { 1862 sample_orig->deferred_callchain = false; 1863 return -ENOMEM; 1864 } 1865 1866 callchain->nr = nr_orig + nr_deferred; 1867 /* copy original including PERF_CONTEXT_USER_DEFERRED (but the cookie) */ 1868 memcpy(callchain->ips, sample_orig->callchain->ips, nr_orig * sizeof(u64)); 1869 /* copy deferred user callchains */ 1870 memcpy(&callchain->ips[nr_orig], sample_callchain->callchain->ips, 1871 nr_deferred * sizeof(u64)); 1872 1873 sample_orig->callchain = callchain; 1874 return 0; 1875 } 1876