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