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