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 = NULL; 625 char *right = NULL; 626 enum match_result ret = MATCH_EQ; 627 int cmp; 628 629 if (cnode->ms.map) 630 left = get_srcline(cnode->ms.map->dso, 631 map__rip_2objdump(cnode->ms.map, cnode->ip), 632 cnode->ms.sym, true, false); 633 if (node->map) 634 right = get_srcline(node->map->dso, 635 map__rip_2objdump(node->map, node->ip), 636 node->sym, true, false); 637 638 if (left && right) 639 cmp = strcmp(left, right); 640 else if (!left && right) 641 cmp = 1; 642 else if (left && !right) 643 cmp = -1; 644 else if (cnode->ip == node->ip) 645 cmp = 0; 646 else 647 cmp = (cnode->ip < node->ip) ? -1 : 1; 648 649 if (cmp != 0) 650 ret = cmp < 0 ? MATCH_LT : MATCH_GT; 651 652 free_srcline(left); 653 free_srcline(right); 654 return ret; 655 } 656 657 static enum match_result match_chain(struct callchain_cursor_node *node, 658 struct callchain_list *cnode) 659 { 660 struct symbol *sym = node->sym; 661 u64 left, right; 662 663 if (callchain_param.key == CCKEY_SRCLINE) { 664 enum match_result match = match_chain_srcline(node, cnode); 665 666 if (match != MATCH_ERROR) 667 return match; 668 } 669 670 if (cnode->ms.sym && sym && callchain_param.key == CCKEY_FUNCTION) { 671 left = cnode->ms.sym->start; 672 right = sym->start; 673 } else { 674 left = cnode->ip; 675 right = node->ip; 676 } 677 678 if (left == right) { 679 if (node->branch) { 680 cnode->branch_count++; 681 682 if (node->branch_flags.predicted) 683 cnode->predicted_count++; 684 685 if (node->branch_flags.abort) 686 cnode->abort_count++; 687 688 cnode->cycles_count += node->branch_flags.cycles; 689 cnode->iter_count += node->nr_loop_iter; 690 cnode->samples_count += node->samples; 691 } 692 693 return MATCH_EQ; 694 } 695 696 return left > right ? MATCH_GT : MATCH_LT; 697 } 698 699 /* 700 * Split the parent in two parts (a new child is created) and 701 * give a part of its callchain to the created child. 702 * Then create another child to host the given callchain of new branch 703 */ 704 static int 705 split_add_child(struct callchain_node *parent, 706 struct callchain_cursor *cursor, 707 struct callchain_list *to_split, 708 u64 idx_parents, u64 idx_local, u64 period) 709 { 710 struct callchain_node *new; 711 struct list_head *old_tail; 712 unsigned int idx_total = idx_parents + idx_local; 713 714 /* split */ 715 new = create_child(parent, true); 716 if (new == NULL) 717 return -1; 718 719 /* split the callchain and move a part to the new child */ 720 old_tail = parent->val.prev; 721 list_del_range(&to_split->list, old_tail); 722 new->val.next = &to_split->list; 723 new->val.prev = old_tail; 724 to_split->list.prev = &new->val; 725 old_tail->next = &new->val; 726 727 /* split the hits */ 728 new->hit = parent->hit; 729 new->children_hit = parent->children_hit; 730 parent->children_hit = callchain_cumul_hits(new); 731 new->val_nr = parent->val_nr - idx_local; 732 parent->val_nr = idx_local; 733 new->count = parent->count; 734 new->children_count = parent->children_count; 735 parent->children_count = callchain_cumul_counts(new); 736 737 /* create a new child for the new branch if any */ 738 if (idx_total < cursor->nr) { 739 struct callchain_node *first; 740 struct callchain_list *cnode; 741 struct callchain_cursor_node *node; 742 struct rb_node *p, **pp; 743 744 parent->hit = 0; 745 parent->children_hit += period; 746 parent->count = 0; 747 parent->children_count += 1; 748 749 node = callchain_cursor_current(cursor); 750 new = add_child(parent, cursor, period); 751 if (new == NULL) 752 return -1; 753 754 /* 755 * This is second child since we moved parent's children 756 * to new (first) child above. 757 */ 758 p = parent->rb_root_in.rb_node; 759 first = rb_entry(p, struct callchain_node, rb_node_in); 760 cnode = list_first_entry(&first->val, struct callchain_list, 761 list); 762 763 if (match_chain(node, cnode) == MATCH_LT) 764 pp = &p->rb_left; 765 else 766 pp = &p->rb_right; 767 768 rb_link_node(&new->rb_node_in, p, pp); 769 rb_insert_color(&new->rb_node_in, &parent->rb_root_in); 770 } else { 771 parent->hit = period; 772 parent->count = 1; 773 } 774 return 0; 775 } 776 777 static enum match_result 778 append_chain(struct callchain_node *root, 779 struct callchain_cursor *cursor, 780 u64 period); 781 782 static int 783 append_chain_children(struct callchain_node *root, 784 struct callchain_cursor *cursor, 785 u64 period) 786 { 787 struct callchain_node *rnode; 788 struct callchain_cursor_node *node; 789 struct rb_node **p = &root->rb_root_in.rb_node; 790 struct rb_node *parent = NULL; 791 792 node = callchain_cursor_current(cursor); 793 if (!node) 794 return -1; 795 796 /* lookup in childrens */ 797 while (*p) { 798 enum match_result ret; 799 800 parent = *p; 801 rnode = rb_entry(parent, struct callchain_node, rb_node_in); 802 803 /* If at least first entry matches, rely to children */ 804 ret = append_chain(rnode, cursor, period); 805 if (ret == MATCH_EQ) 806 goto inc_children_hit; 807 if (ret == MATCH_ERROR) 808 return -1; 809 810 if (ret == MATCH_LT) 811 p = &parent->rb_left; 812 else 813 p = &parent->rb_right; 814 } 815 /* nothing in children, add to the current node */ 816 rnode = add_child(root, cursor, period); 817 if (rnode == NULL) 818 return -1; 819 820 rb_link_node(&rnode->rb_node_in, parent, p); 821 rb_insert_color(&rnode->rb_node_in, &root->rb_root_in); 822 823 inc_children_hit: 824 root->children_hit += period; 825 root->children_count++; 826 return 0; 827 } 828 829 static enum match_result 830 append_chain(struct callchain_node *root, 831 struct callchain_cursor *cursor, 832 u64 period) 833 { 834 struct callchain_list *cnode; 835 u64 start = cursor->pos; 836 bool found = false; 837 u64 matches; 838 enum match_result cmp = MATCH_ERROR; 839 840 /* 841 * Lookup in the current node 842 * If we have a symbol, then compare the start to match 843 * anywhere inside a function, unless function 844 * mode is disabled. 845 */ 846 list_for_each_entry(cnode, &root->val, list) { 847 struct callchain_cursor_node *node; 848 849 node = callchain_cursor_current(cursor); 850 if (!node) 851 break; 852 853 cmp = match_chain(node, cnode); 854 if (cmp != MATCH_EQ) 855 break; 856 857 found = true; 858 859 callchain_cursor_advance(cursor); 860 } 861 862 /* matches not, relay no the parent */ 863 if (!found) { 864 WARN_ONCE(cmp == MATCH_ERROR, "Chain comparison error\n"); 865 return cmp; 866 } 867 868 matches = cursor->pos - start; 869 870 /* we match only a part of the node. Split it and add the new chain */ 871 if (matches < root->val_nr) { 872 if (split_add_child(root, cursor, cnode, start, matches, 873 period) < 0) 874 return MATCH_ERROR; 875 876 return MATCH_EQ; 877 } 878 879 /* we match 100% of the path, increment the hit */ 880 if (matches == root->val_nr && cursor->pos == cursor->nr) { 881 root->hit += period; 882 root->count++; 883 return MATCH_EQ; 884 } 885 886 /* We match the node and still have a part remaining */ 887 if (append_chain_children(root, cursor, period) < 0) 888 return MATCH_ERROR; 889 890 return MATCH_EQ; 891 } 892 893 int callchain_append(struct callchain_root *root, 894 struct callchain_cursor *cursor, 895 u64 period) 896 { 897 if (!cursor->nr) 898 return 0; 899 900 callchain_cursor_commit(cursor); 901 902 if (append_chain_children(&root->node, cursor, period) < 0) 903 return -1; 904 905 if (cursor->nr > root->max_depth) 906 root->max_depth = cursor->nr; 907 908 return 0; 909 } 910 911 static int 912 merge_chain_branch(struct callchain_cursor *cursor, 913 struct callchain_node *dst, struct callchain_node *src) 914 { 915 struct callchain_cursor_node **old_last = cursor->last; 916 struct callchain_node *child; 917 struct callchain_list *list, *next_list; 918 struct rb_node *n; 919 int old_pos = cursor->nr; 920 int err = 0; 921 922 list_for_each_entry_safe(list, next_list, &src->val, list) { 923 callchain_cursor_append(cursor, list->ip, 924 list->ms.map, list->ms.sym, 925 false, NULL, 0, 0); 926 list_del(&list->list); 927 map__zput(list->ms.map); 928 free(list); 929 } 930 931 if (src->hit) { 932 callchain_cursor_commit(cursor); 933 if (append_chain_children(dst, cursor, src->hit) < 0) 934 return -1; 935 } 936 937 n = rb_first(&src->rb_root_in); 938 while (n) { 939 child = container_of(n, struct callchain_node, rb_node_in); 940 n = rb_next(n); 941 rb_erase(&child->rb_node_in, &src->rb_root_in); 942 943 err = merge_chain_branch(cursor, dst, child); 944 if (err) 945 break; 946 947 free(child); 948 } 949 950 cursor->nr = old_pos; 951 cursor->last = old_last; 952 953 return err; 954 } 955 956 int callchain_merge(struct callchain_cursor *cursor, 957 struct callchain_root *dst, struct callchain_root *src) 958 { 959 return merge_chain_branch(cursor, &dst->node, &src->node); 960 } 961 962 int callchain_cursor_append(struct callchain_cursor *cursor, 963 u64 ip, struct map *map, struct symbol *sym, 964 bool branch, struct branch_flags *flags, 965 int nr_loop_iter, int samples) 966 { 967 struct callchain_cursor_node *node = *cursor->last; 968 969 if (!node) { 970 node = calloc(1, sizeof(*node)); 971 if (!node) 972 return -ENOMEM; 973 974 *cursor->last = node; 975 } 976 977 node->ip = ip; 978 map__zput(node->map); 979 node->map = map__get(map); 980 node->sym = sym; 981 node->branch = branch; 982 node->nr_loop_iter = nr_loop_iter; 983 node->samples = samples; 984 985 if (flags) 986 memcpy(&node->branch_flags, flags, 987 sizeof(struct branch_flags)); 988 989 cursor->nr++; 990 991 cursor->last = &node->next; 992 993 return 0; 994 } 995 996 int sample__resolve_callchain(struct perf_sample *sample, 997 struct callchain_cursor *cursor, struct symbol **parent, 998 struct perf_evsel *evsel, struct addr_location *al, 999 int max_stack) 1000 { 1001 if (sample->callchain == NULL) 1002 return 0; 1003 1004 if (symbol_conf.use_callchain || symbol_conf.cumulate_callchain || 1005 perf_hpp_list.parent) { 1006 return thread__resolve_callchain(al->thread, cursor, evsel, sample, 1007 parent, al, max_stack); 1008 } 1009 return 0; 1010 } 1011 1012 int hist_entry__append_callchain(struct hist_entry *he, struct perf_sample *sample) 1013 { 1014 if (!symbol_conf.use_callchain || sample->callchain == NULL) 1015 return 0; 1016 return callchain_append(he->callchain, &callchain_cursor, sample->period); 1017 } 1018 1019 int fill_callchain_info(struct addr_location *al, struct callchain_cursor_node *node, 1020 bool hide_unresolved) 1021 { 1022 al->map = node->map; 1023 al->sym = node->sym; 1024 if (node->map) 1025 al->addr = node->map->map_ip(node->map, node->ip); 1026 else 1027 al->addr = node->ip; 1028 1029 if (al->sym == NULL) { 1030 if (hide_unresolved) 1031 return 0; 1032 if (al->map == NULL) 1033 goto out; 1034 } 1035 1036 if (al->map->groups == &al->machine->kmaps) { 1037 if (machine__is_host(al->machine)) { 1038 al->cpumode = PERF_RECORD_MISC_KERNEL; 1039 al->level = 'k'; 1040 } else { 1041 al->cpumode = PERF_RECORD_MISC_GUEST_KERNEL; 1042 al->level = 'g'; 1043 } 1044 } else { 1045 if (machine__is_host(al->machine)) { 1046 al->cpumode = PERF_RECORD_MISC_USER; 1047 al->level = '.'; 1048 } else if (perf_guest) { 1049 al->cpumode = PERF_RECORD_MISC_GUEST_USER; 1050 al->level = 'u'; 1051 } else { 1052 al->cpumode = PERF_RECORD_MISC_HYPERVISOR; 1053 al->level = 'H'; 1054 } 1055 } 1056 1057 out: 1058 return 1; 1059 } 1060 1061 char *callchain_list__sym_name(struct callchain_list *cl, 1062 char *bf, size_t bfsize, bool show_dso) 1063 { 1064 bool show_addr = callchain_param.key == CCKEY_ADDRESS; 1065 bool show_srcline = show_addr || callchain_param.key == CCKEY_SRCLINE; 1066 int printed; 1067 1068 if (cl->ms.sym) { 1069 if (show_srcline && cl->ms.map && !cl->srcline) 1070 cl->srcline = get_srcline(cl->ms.map->dso, 1071 map__rip_2objdump(cl->ms.map, 1072 cl->ip), 1073 cl->ms.sym, false, show_addr); 1074 if (cl->srcline) 1075 printed = scnprintf(bf, bfsize, "%s %s", 1076 cl->ms.sym->name, cl->srcline); 1077 else 1078 printed = scnprintf(bf, bfsize, "%s", cl->ms.sym->name); 1079 } else 1080 printed = scnprintf(bf, bfsize, "%#" PRIx64, cl->ip); 1081 1082 if (show_dso) 1083 scnprintf(bf + printed, bfsize - printed, " %s", 1084 cl->ms.map ? 1085 cl->ms.map->dso->short_name : 1086 "unknown"); 1087 1088 return bf; 1089 } 1090 1091 char *callchain_node__scnprintf_value(struct callchain_node *node, 1092 char *bf, size_t bfsize, u64 total) 1093 { 1094 double percent = 0.0; 1095 u64 period = callchain_cumul_hits(node); 1096 unsigned count = callchain_cumul_counts(node); 1097 1098 if (callchain_param.mode == CHAIN_FOLDED) { 1099 period = node->hit; 1100 count = node->count; 1101 } 1102 1103 switch (callchain_param.value) { 1104 case CCVAL_PERIOD: 1105 scnprintf(bf, bfsize, "%"PRIu64, period); 1106 break; 1107 case CCVAL_COUNT: 1108 scnprintf(bf, bfsize, "%u", count); 1109 break; 1110 case CCVAL_PERCENT: 1111 default: 1112 if (total) 1113 percent = period * 100.0 / total; 1114 scnprintf(bf, bfsize, "%.2f%%", percent); 1115 break; 1116 } 1117 return bf; 1118 } 1119 1120 int callchain_node__fprintf_value(struct callchain_node *node, 1121 FILE *fp, u64 total) 1122 { 1123 double percent = 0.0; 1124 u64 period = callchain_cumul_hits(node); 1125 unsigned count = callchain_cumul_counts(node); 1126 1127 if (callchain_param.mode == CHAIN_FOLDED) { 1128 period = node->hit; 1129 count = node->count; 1130 } 1131 1132 switch (callchain_param.value) { 1133 case CCVAL_PERIOD: 1134 return fprintf(fp, "%"PRIu64, period); 1135 case CCVAL_COUNT: 1136 return fprintf(fp, "%u", count); 1137 case CCVAL_PERCENT: 1138 default: 1139 if (total) 1140 percent = period * 100.0 / total; 1141 return percent_color_fprintf(fp, "%.2f%%", percent); 1142 } 1143 return 0; 1144 } 1145 1146 static void callchain_counts_value(struct callchain_node *node, 1147 u64 *branch_count, u64 *predicted_count, 1148 u64 *abort_count, u64 *cycles_count) 1149 { 1150 struct callchain_list *clist; 1151 1152 list_for_each_entry(clist, &node->val, list) { 1153 if (branch_count) 1154 *branch_count += clist->branch_count; 1155 1156 if (predicted_count) 1157 *predicted_count += clist->predicted_count; 1158 1159 if (abort_count) 1160 *abort_count += clist->abort_count; 1161 1162 if (cycles_count) 1163 *cycles_count += clist->cycles_count; 1164 } 1165 } 1166 1167 static int callchain_node_branch_counts_cumul(struct callchain_node *node, 1168 u64 *branch_count, 1169 u64 *predicted_count, 1170 u64 *abort_count, 1171 u64 *cycles_count) 1172 { 1173 struct callchain_node *child; 1174 struct rb_node *n; 1175 1176 n = rb_first(&node->rb_root_in); 1177 while (n) { 1178 child = rb_entry(n, struct callchain_node, rb_node_in); 1179 n = rb_next(n); 1180 1181 callchain_node_branch_counts_cumul(child, branch_count, 1182 predicted_count, 1183 abort_count, 1184 cycles_count); 1185 1186 callchain_counts_value(child, branch_count, 1187 predicted_count, abort_count, 1188 cycles_count); 1189 } 1190 1191 return 0; 1192 } 1193 1194 int callchain_branch_counts(struct callchain_root *root, 1195 u64 *branch_count, u64 *predicted_count, 1196 u64 *abort_count, u64 *cycles_count) 1197 { 1198 if (branch_count) 1199 *branch_count = 0; 1200 1201 if (predicted_count) 1202 *predicted_count = 0; 1203 1204 if (abort_count) 1205 *abort_count = 0; 1206 1207 if (cycles_count) 1208 *cycles_count = 0; 1209 1210 return callchain_node_branch_counts_cumul(&root->node, 1211 branch_count, 1212 predicted_count, 1213 abort_count, 1214 cycles_count); 1215 } 1216 1217 static int counts_str_build(char *bf, int bfsize, 1218 u64 branch_count, u64 predicted_count, 1219 u64 abort_count, u64 cycles_count, 1220 u64 iter_count, u64 samples_count) 1221 { 1222 double predicted_percent = 0.0; 1223 const char *null_str = ""; 1224 char iter_str[32]; 1225 char cycle_str[32]; 1226 char *istr, *cstr; 1227 u64 cycles; 1228 1229 if (branch_count == 0) 1230 return scnprintf(bf, bfsize, " (calltrace)"); 1231 1232 cycles = cycles_count / branch_count; 1233 1234 if (iter_count && samples_count) { 1235 if (cycles > 0) 1236 scnprintf(iter_str, sizeof(iter_str), 1237 " iterations:%" PRId64 "", 1238 iter_count / samples_count); 1239 else 1240 scnprintf(iter_str, sizeof(iter_str), 1241 "iterations:%" PRId64 "", 1242 iter_count / samples_count); 1243 istr = iter_str; 1244 } else 1245 istr = (char *)null_str; 1246 1247 if (cycles > 0) { 1248 scnprintf(cycle_str, sizeof(cycle_str), 1249 "cycles:%" PRId64 "", cycles); 1250 cstr = cycle_str; 1251 } else 1252 cstr = (char *)null_str; 1253 1254 predicted_percent = predicted_count * 100.0 / branch_count; 1255 1256 if ((predicted_count == branch_count) && (abort_count == 0)) { 1257 if ((cycles > 0) || (istr != (char *)null_str)) 1258 return scnprintf(bf, bfsize, " (%s%s)", cstr, istr); 1259 else 1260 return scnprintf(bf, bfsize, "%s", (char *)null_str); 1261 } 1262 1263 if ((predicted_count < branch_count) && (abort_count == 0)) { 1264 if ((cycles > 0) || (istr != (char *)null_str)) 1265 return scnprintf(bf, bfsize, 1266 " (predicted:%.1f%% %s%s)", 1267 predicted_percent, cstr, istr); 1268 else { 1269 return scnprintf(bf, bfsize, 1270 " (predicted:%.1f%%)", 1271 predicted_percent); 1272 } 1273 } 1274 1275 if ((predicted_count == branch_count) && (abort_count > 0)) { 1276 if ((cycles > 0) || (istr != (char *)null_str)) 1277 return scnprintf(bf, bfsize, 1278 " (abort:%" PRId64 " %s%s)", 1279 abort_count, cstr, istr); 1280 else 1281 return scnprintf(bf, bfsize, 1282 " (abort:%" PRId64 ")", 1283 abort_count); 1284 } 1285 1286 if ((cycles > 0) || (istr != (char *)null_str)) 1287 return scnprintf(bf, bfsize, 1288 " (predicted:%.1f%% abort:%" PRId64 " %s%s)", 1289 predicted_percent, abort_count, cstr, istr); 1290 1291 return scnprintf(bf, bfsize, 1292 " (predicted:%.1f%% abort:%" PRId64 ")", 1293 predicted_percent, abort_count); 1294 } 1295 1296 static int callchain_counts_printf(FILE *fp, char *bf, int bfsize, 1297 u64 branch_count, u64 predicted_count, 1298 u64 abort_count, u64 cycles_count, 1299 u64 iter_count, u64 samples_count) 1300 { 1301 char str[128]; 1302 1303 counts_str_build(str, sizeof(str), branch_count, 1304 predicted_count, abort_count, cycles_count, 1305 iter_count, samples_count); 1306 1307 if (fp) 1308 return fprintf(fp, "%s", str); 1309 1310 return scnprintf(bf, bfsize, "%s", str); 1311 } 1312 1313 int callchain_list_counts__printf_value(struct callchain_node *node, 1314 struct callchain_list *clist, 1315 FILE *fp, char *bf, int bfsize) 1316 { 1317 u64 branch_count, predicted_count; 1318 u64 abort_count, cycles_count; 1319 u64 iter_count = 0, samples_count = 0; 1320 1321 branch_count = clist->branch_count; 1322 predicted_count = clist->predicted_count; 1323 abort_count = clist->abort_count; 1324 cycles_count = clist->cycles_count; 1325 1326 if (node) { 1327 struct callchain_list *call; 1328 1329 list_for_each_entry(call, &node->val, list) { 1330 iter_count += call->iter_count; 1331 samples_count += call->samples_count; 1332 } 1333 } 1334 1335 return callchain_counts_printf(fp, bf, bfsize, branch_count, 1336 predicted_count, abort_count, 1337 cycles_count, iter_count, samples_count); 1338 } 1339 1340 static void free_callchain_node(struct callchain_node *node) 1341 { 1342 struct callchain_list *list, *tmp; 1343 struct callchain_node *child; 1344 struct rb_node *n; 1345 1346 list_for_each_entry_safe(list, tmp, &node->parent_val, list) { 1347 list_del(&list->list); 1348 map__zput(list->ms.map); 1349 free(list); 1350 } 1351 1352 list_for_each_entry_safe(list, tmp, &node->val, list) { 1353 list_del(&list->list); 1354 map__zput(list->ms.map); 1355 free(list); 1356 } 1357 1358 n = rb_first(&node->rb_root_in); 1359 while (n) { 1360 child = container_of(n, struct callchain_node, rb_node_in); 1361 n = rb_next(n); 1362 rb_erase(&child->rb_node_in, &node->rb_root_in); 1363 1364 free_callchain_node(child); 1365 free(child); 1366 } 1367 } 1368 1369 void free_callchain(struct callchain_root *root) 1370 { 1371 if (!symbol_conf.use_callchain) 1372 return; 1373 1374 free_callchain_node(&root->node); 1375 } 1376 1377 static u64 decay_callchain_node(struct callchain_node *node) 1378 { 1379 struct callchain_node *child; 1380 struct rb_node *n; 1381 u64 child_hits = 0; 1382 1383 n = rb_first(&node->rb_root_in); 1384 while (n) { 1385 child = container_of(n, struct callchain_node, rb_node_in); 1386 1387 child_hits += decay_callchain_node(child); 1388 n = rb_next(n); 1389 } 1390 1391 node->hit = (node->hit * 7) / 8; 1392 node->children_hit = child_hits; 1393 1394 return node->hit; 1395 } 1396 1397 void decay_callchain(struct callchain_root *root) 1398 { 1399 if (!symbol_conf.use_callchain) 1400 return; 1401 1402 decay_callchain_node(&root->node); 1403 } 1404 1405 int callchain_node__make_parent_list(struct callchain_node *node) 1406 { 1407 struct callchain_node *parent = node->parent; 1408 struct callchain_list *chain, *new; 1409 LIST_HEAD(head); 1410 1411 while (parent) { 1412 list_for_each_entry_reverse(chain, &parent->val, list) { 1413 new = malloc(sizeof(*new)); 1414 if (new == NULL) 1415 goto out; 1416 *new = *chain; 1417 new->has_children = false; 1418 map__get(new->ms.map); 1419 list_add_tail(&new->list, &head); 1420 } 1421 parent = parent->parent; 1422 } 1423 1424 list_for_each_entry_safe_reverse(chain, new, &head, list) 1425 list_move_tail(&chain->list, &node->parent_val); 1426 1427 if (!list_empty(&node->parent_val)) { 1428 chain = list_first_entry(&node->parent_val, struct callchain_list, list); 1429 chain->has_children = rb_prev(&node->rb_node) || rb_next(&node->rb_node); 1430 1431 chain = list_first_entry(&node->val, struct callchain_list, list); 1432 chain->has_children = false; 1433 } 1434 return 0; 1435 1436 out: 1437 list_for_each_entry_safe(chain, new, &head, list) { 1438 list_del(&chain->list); 1439 map__zput(chain->ms.map); 1440 free(chain); 1441 } 1442 return -ENOMEM; 1443 } 1444 1445 int callchain_cursor__copy(struct callchain_cursor *dst, 1446 struct callchain_cursor *src) 1447 { 1448 int rc = 0; 1449 1450 callchain_cursor_reset(dst); 1451 callchain_cursor_commit(src); 1452 1453 while (true) { 1454 struct callchain_cursor_node *node; 1455 1456 node = callchain_cursor_current(src); 1457 if (node == NULL) 1458 break; 1459 1460 rc = callchain_cursor_append(dst, node->ip, node->map, node->sym, 1461 node->branch, &node->branch_flags, 1462 node->nr_loop_iter, node->samples); 1463 if (rc) 1464 break; 1465 1466 callchain_cursor_advance(src); 1467 } 1468 1469 return rc; 1470 } 1471