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