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 <stdlib.h> 13 #include <stdio.h> 14 #include <stdbool.h> 15 #include <errno.h> 16 #include <math.h> 17 18 #include "asm/bug.h" 19 20 #include "hist.h" 21 #include "util.h" 22 #include "sort.h" 23 #include "machine.h" 24 #include "callchain.h" 25 26 __thread struct callchain_cursor callchain_cursor; 27 28 #ifdef HAVE_DWARF_UNWIND_SUPPORT 29 static int get_stack_size(const char *str, unsigned long *_size) 30 { 31 char *endptr; 32 unsigned long size; 33 unsigned long max_size = round_down(USHRT_MAX, sizeof(u64)); 34 35 size = strtoul(str, &endptr, 0); 36 37 do { 38 if (*endptr) 39 break; 40 41 size = round_up(size, sizeof(u64)); 42 if (!size || size > max_size) 43 break; 44 45 *_size = size; 46 return 0; 47 48 } while (0); 49 50 pr_err("callchain: Incorrect stack dump size (max %ld): %s\n", 51 max_size, str); 52 return -1; 53 } 54 #endif /* HAVE_DWARF_UNWIND_SUPPORT */ 55 56 int parse_callchain_record_opt(const char *arg) 57 { 58 char *tok, *name, *saveptr = NULL; 59 char *buf; 60 int ret = -1; 61 62 /* We need buffer that we know we can write to. */ 63 buf = malloc(strlen(arg) + 1); 64 if (!buf) 65 return -ENOMEM; 66 67 strcpy(buf, arg); 68 69 tok = strtok_r((char *)buf, ",", &saveptr); 70 name = tok ? : (char *)buf; 71 72 do { 73 /* Framepointer style */ 74 if (!strncmp(name, "fp", sizeof("fp"))) { 75 if (!strtok_r(NULL, ",", &saveptr)) { 76 callchain_param.record_mode = CALLCHAIN_FP; 77 ret = 0; 78 } else 79 pr_err("callchain: No more arguments " 80 "needed for -g fp\n"); 81 break; 82 83 #ifdef HAVE_DWARF_UNWIND_SUPPORT 84 /* Dwarf style */ 85 } else if (!strncmp(name, "dwarf", sizeof("dwarf"))) { 86 const unsigned long default_stack_dump_size = 8192; 87 88 ret = 0; 89 callchain_param.record_mode = CALLCHAIN_DWARF; 90 callchain_param.dump_size = default_stack_dump_size; 91 92 tok = strtok_r(NULL, ",", &saveptr); 93 if (tok) { 94 unsigned long size = 0; 95 96 ret = get_stack_size(tok, &size); 97 callchain_param.dump_size = size; 98 } 99 #endif /* HAVE_DWARF_UNWIND_SUPPORT */ 100 } else { 101 pr_err("callchain: Unknown --call-graph option " 102 "value: %s\n", arg); 103 break; 104 } 105 106 } while (0); 107 108 free(buf); 109 return ret; 110 } 111 112 static int parse_callchain_mode(const char *value) 113 { 114 if (!strncmp(value, "graph", strlen(value))) { 115 callchain_param.mode = CHAIN_GRAPH_ABS; 116 return 0; 117 } 118 if (!strncmp(value, "flat", strlen(value))) { 119 callchain_param.mode = CHAIN_FLAT; 120 return 0; 121 } 122 if (!strncmp(value, "fractal", strlen(value))) { 123 callchain_param.mode = CHAIN_GRAPH_REL; 124 return 0; 125 } 126 return -1; 127 } 128 129 static int parse_callchain_order(const char *value) 130 { 131 if (!strncmp(value, "caller", strlen(value))) { 132 callchain_param.order = ORDER_CALLER; 133 return 0; 134 } 135 if (!strncmp(value, "callee", strlen(value))) { 136 callchain_param.order = ORDER_CALLEE; 137 return 0; 138 } 139 return -1; 140 } 141 142 static int parse_callchain_sort_key(const char *value) 143 { 144 if (!strncmp(value, "function", strlen(value))) { 145 callchain_param.key = CCKEY_FUNCTION; 146 return 0; 147 } 148 if (!strncmp(value, "address", strlen(value))) { 149 callchain_param.key = CCKEY_ADDRESS; 150 return 0; 151 } 152 return -1; 153 } 154 155 int 156 parse_callchain_report_opt(const char *arg) 157 { 158 char *tok; 159 char *endptr; 160 bool minpcnt_set = false; 161 162 symbol_conf.use_callchain = true; 163 164 if (!arg) 165 return 0; 166 167 while ((tok = strtok((char *)arg, ",")) != NULL) { 168 if (!strncmp(tok, "none", strlen(tok))) { 169 callchain_param.mode = CHAIN_NONE; 170 symbol_conf.use_callchain = false; 171 return 0; 172 } 173 174 if (!parse_callchain_mode(tok) || 175 !parse_callchain_order(tok) || 176 !parse_callchain_sort_key(tok)) { 177 /* parsing ok - move on to the next */ 178 } else if (!minpcnt_set) { 179 /* try to get the min percent */ 180 callchain_param.min_percent = strtod(tok, &endptr); 181 if (tok == endptr) 182 return -1; 183 minpcnt_set = true; 184 } else { 185 /* try print limit at last */ 186 callchain_param.print_limit = strtoul(tok, &endptr, 0); 187 if (tok == endptr) 188 return -1; 189 } 190 191 arg = NULL; 192 } 193 194 if (callchain_register_param(&callchain_param) < 0) { 195 pr_err("Can't register callchain params\n"); 196 return -1; 197 } 198 return 0; 199 } 200 201 int perf_callchain_config(const char *var, const char *value) 202 { 203 char *endptr; 204 205 if (prefixcmp(var, "call-graph.")) 206 return 0; 207 var += sizeof("call-graph.") - 1; 208 209 if (!strcmp(var, "record-mode")) 210 return parse_callchain_record_opt(value); 211 #ifdef HAVE_DWARF_UNWIND_SUPPORT 212 if (!strcmp(var, "dump-size")) { 213 unsigned long size = 0; 214 int ret; 215 216 ret = get_stack_size(value, &size); 217 callchain_param.dump_size = size; 218 219 return ret; 220 } 221 #endif 222 if (!strcmp(var, "print-type")) 223 return parse_callchain_mode(value); 224 if (!strcmp(var, "order")) 225 return parse_callchain_order(value); 226 if (!strcmp(var, "sort-key")) 227 return parse_callchain_sort_key(value); 228 if (!strcmp(var, "threshold")) { 229 callchain_param.min_percent = strtod(value, &endptr); 230 if (value == endptr) 231 return -1; 232 } 233 if (!strcmp(var, "print-limit")) { 234 callchain_param.print_limit = strtod(value, &endptr); 235 if (value == endptr) 236 return -1; 237 } 238 239 return 0; 240 } 241 242 static void 243 rb_insert_callchain(struct rb_root *root, struct callchain_node *chain, 244 enum chain_mode mode) 245 { 246 struct rb_node **p = &root->rb_node; 247 struct rb_node *parent = NULL; 248 struct callchain_node *rnode; 249 u64 chain_cumul = callchain_cumul_hits(chain); 250 251 while (*p) { 252 u64 rnode_cumul; 253 254 parent = *p; 255 rnode = rb_entry(parent, struct callchain_node, rb_node); 256 rnode_cumul = callchain_cumul_hits(rnode); 257 258 switch (mode) { 259 case CHAIN_FLAT: 260 if (rnode->hit < chain->hit) 261 p = &(*p)->rb_left; 262 else 263 p = &(*p)->rb_right; 264 break; 265 case CHAIN_GRAPH_ABS: /* Falldown */ 266 case CHAIN_GRAPH_REL: 267 if (rnode_cumul < chain_cumul) 268 p = &(*p)->rb_left; 269 else 270 p = &(*p)->rb_right; 271 break; 272 case CHAIN_NONE: 273 default: 274 break; 275 } 276 } 277 278 rb_link_node(&chain->rb_node, parent, p); 279 rb_insert_color(&chain->rb_node, root); 280 } 281 282 static void 283 __sort_chain_flat(struct rb_root *rb_root, struct callchain_node *node, 284 u64 min_hit) 285 { 286 struct rb_node *n; 287 struct callchain_node *child; 288 289 n = rb_first(&node->rb_root_in); 290 while (n) { 291 child = rb_entry(n, struct callchain_node, rb_node_in); 292 n = rb_next(n); 293 294 __sort_chain_flat(rb_root, child, min_hit); 295 } 296 297 if (node->hit && node->hit >= min_hit) 298 rb_insert_callchain(rb_root, node, CHAIN_FLAT); 299 } 300 301 /* 302 * Once we get every callchains from the stream, we can now 303 * sort them by hit 304 */ 305 static void 306 sort_chain_flat(struct rb_root *rb_root, struct callchain_root *root, 307 u64 min_hit, struct callchain_param *param __maybe_unused) 308 { 309 __sort_chain_flat(rb_root, &root->node, min_hit); 310 } 311 312 static void __sort_chain_graph_abs(struct callchain_node *node, 313 u64 min_hit) 314 { 315 struct rb_node *n; 316 struct callchain_node *child; 317 318 node->rb_root = RB_ROOT; 319 n = rb_first(&node->rb_root_in); 320 321 while (n) { 322 child = rb_entry(n, struct callchain_node, rb_node_in); 323 n = rb_next(n); 324 325 __sort_chain_graph_abs(child, min_hit); 326 if (callchain_cumul_hits(child) >= min_hit) 327 rb_insert_callchain(&node->rb_root, child, 328 CHAIN_GRAPH_ABS); 329 } 330 } 331 332 static void 333 sort_chain_graph_abs(struct rb_root *rb_root, struct callchain_root *chain_root, 334 u64 min_hit, struct callchain_param *param __maybe_unused) 335 { 336 __sort_chain_graph_abs(&chain_root->node, min_hit); 337 rb_root->rb_node = chain_root->node.rb_root.rb_node; 338 } 339 340 static void __sort_chain_graph_rel(struct callchain_node *node, 341 double min_percent) 342 { 343 struct rb_node *n; 344 struct callchain_node *child; 345 u64 min_hit; 346 347 node->rb_root = RB_ROOT; 348 min_hit = ceil(node->children_hit * min_percent); 349 350 n = rb_first(&node->rb_root_in); 351 while (n) { 352 child = rb_entry(n, struct callchain_node, rb_node_in); 353 n = rb_next(n); 354 355 __sort_chain_graph_rel(child, min_percent); 356 if (callchain_cumul_hits(child) >= min_hit) 357 rb_insert_callchain(&node->rb_root, child, 358 CHAIN_GRAPH_REL); 359 } 360 } 361 362 static void 363 sort_chain_graph_rel(struct rb_root *rb_root, struct callchain_root *chain_root, 364 u64 min_hit __maybe_unused, struct callchain_param *param) 365 { 366 __sort_chain_graph_rel(&chain_root->node, param->min_percent / 100.0); 367 rb_root->rb_node = chain_root->node.rb_root.rb_node; 368 } 369 370 int callchain_register_param(struct callchain_param *param) 371 { 372 switch (param->mode) { 373 case CHAIN_GRAPH_ABS: 374 param->sort = sort_chain_graph_abs; 375 break; 376 case CHAIN_GRAPH_REL: 377 param->sort = sort_chain_graph_rel; 378 break; 379 case CHAIN_FLAT: 380 param->sort = sort_chain_flat; 381 break; 382 case CHAIN_NONE: 383 default: 384 return -1; 385 } 386 return 0; 387 } 388 389 /* 390 * Create a child for a parent. If inherit_children, then the new child 391 * will become the new parent of it's parent children 392 */ 393 static struct callchain_node * 394 create_child(struct callchain_node *parent, bool inherit_children) 395 { 396 struct callchain_node *new; 397 398 new = zalloc(sizeof(*new)); 399 if (!new) { 400 perror("not enough memory to create child for code path tree"); 401 return NULL; 402 } 403 new->parent = parent; 404 INIT_LIST_HEAD(&new->val); 405 406 if (inherit_children) { 407 struct rb_node *n; 408 struct callchain_node *child; 409 410 new->rb_root_in = parent->rb_root_in; 411 parent->rb_root_in = RB_ROOT; 412 413 n = rb_first(&new->rb_root_in); 414 while (n) { 415 child = rb_entry(n, struct callchain_node, rb_node_in); 416 child->parent = new; 417 n = rb_next(n); 418 } 419 420 /* make it the first child */ 421 rb_link_node(&new->rb_node_in, NULL, &parent->rb_root_in.rb_node); 422 rb_insert_color(&new->rb_node_in, &parent->rb_root_in); 423 } 424 425 return new; 426 } 427 428 429 /* 430 * Fill the node with callchain values 431 */ 432 static void 433 fill_node(struct callchain_node *node, struct callchain_cursor *cursor) 434 { 435 struct callchain_cursor_node *cursor_node; 436 437 node->val_nr = cursor->nr - cursor->pos; 438 if (!node->val_nr) 439 pr_warning("Warning: empty node in callchain tree\n"); 440 441 cursor_node = callchain_cursor_current(cursor); 442 443 while (cursor_node) { 444 struct callchain_list *call; 445 446 call = zalloc(sizeof(*call)); 447 if (!call) { 448 perror("not enough memory for the code path tree"); 449 return; 450 } 451 call->ip = cursor_node->ip; 452 call->ms.sym = cursor_node->sym; 453 call->ms.map = cursor_node->map; 454 list_add_tail(&call->list, &node->val); 455 456 callchain_cursor_advance(cursor); 457 cursor_node = callchain_cursor_current(cursor); 458 } 459 } 460 461 static struct callchain_node * 462 add_child(struct callchain_node *parent, 463 struct callchain_cursor *cursor, 464 u64 period) 465 { 466 struct callchain_node *new; 467 468 new = create_child(parent, false); 469 fill_node(new, cursor); 470 471 new->children_hit = 0; 472 new->hit = period; 473 return new; 474 } 475 476 static s64 match_chain(struct callchain_cursor_node *node, 477 struct callchain_list *cnode) 478 { 479 struct symbol *sym = node->sym; 480 481 if (cnode->ms.sym && sym && 482 callchain_param.key == CCKEY_FUNCTION) 483 return cnode->ms.sym->start - sym->start; 484 else 485 return cnode->ip - node->ip; 486 } 487 488 /* 489 * Split the parent in two parts (a new child is created) and 490 * give a part of its callchain to the created child. 491 * Then create another child to host the given callchain of new branch 492 */ 493 static void 494 split_add_child(struct callchain_node *parent, 495 struct callchain_cursor *cursor, 496 struct callchain_list *to_split, 497 u64 idx_parents, u64 idx_local, u64 period) 498 { 499 struct callchain_node *new; 500 struct list_head *old_tail; 501 unsigned int idx_total = idx_parents + idx_local; 502 503 /* split */ 504 new = create_child(parent, true); 505 506 /* split the callchain and move a part to the new child */ 507 old_tail = parent->val.prev; 508 list_del_range(&to_split->list, old_tail); 509 new->val.next = &to_split->list; 510 new->val.prev = old_tail; 511 to_split->list.prev = &new->val; 512 old_tail->next = &new->val; 513 514 /* split the hits */ 515 new->hit = parent->hit; 516 new->children_hit = parent->children_hit; 517 parent->children_hit = callchain_cumul_hits(new); 518 new->val_nr = parent->val_nr - idx_local; 519 parent->val_nr = idx_local; 520 521 /* create a new child for the new branch if any */ 522 if (idx_total < cursor->nr) { 523 struct callchain_node *first; 524 struct callchain_list *cnode; 525 struct callchain_cursor_node *node; 526 struct rb_node *p, **pp; 527 528 parent->hit = 0; 529 parent->children_hit += period; 530 531 node = callchain_cursor_current(cursor); 532 new = add_child(parent, cursor, period); 533 534 /* 535 * This is second child since we moved parent's children 536 * to new (first) child above. 537 */ 538 p = parent->rb_root_in.rb_node; 539 first = rb_entry(p, struct callchain_node, rb_node_in); 540 cnode = list_first_entry(&first->val, struct callchain_list, 541 list); 542 543 if (match_chain(node, cnode) < 0) 544 pp = &p->rb_left; 545 else 546 pp = &p->rb_right; 547 548 rb_link_node(&new->rb_node_in, p, pp); 549 rb_insert_color(&new->rb_node_in, &parent->rb_root_in); 550 } else { 551 parent->hit = period; 552 } 553 } 554 555 static int 556 append_chain(struct callchain_node *root, 557 struct callchain_cursor *cursor, 558 u64 period); 559 560 static void 561 append_chain_children(struct callchain_node *root, 562 struct callchain_cursor *cursor, 563 u64 period) 564 { 565 struct callchain_node *rnode; 566 struct callchain_cursor_node *node; 567 struct rb_node **p = &root->rb_root_in.rb_node; 568 struct rb_node *parent = NULL; 569 570 node = callchain_cursor_current(cursor); 571 if (!node) 572 return; 573 574 /* lookup in childrens */ 575 while (*p) { 576 s64 ret; 577 578 parent = *p; 579 rnode = rb_entry(parent, struct callchain_node, rb_node_in); 580 581 /* If at least first entry matches, rely to children */ 582 ret = append_chain(rnode, cursor, period); 583 if (ret == 0) 584 goto inc_children_hit; 585 586 if (ret < 0) 587 p = &parent->rb_left; 588 else 589 p = &parent->rb_right; 590 } 591 /* nothing in children, add to the current node */ 592 rnode = add_child(root, cursor, period); 593 rb_link_node(&rnode->rb_node_in, parent, p); 594 rb_insert_color(&rnode->rb_node_in, &root->rb_root_in); 595 596 inc_children_hit: 597 root->children_hit += period; 598 } 599 600 static int 601 append_chain(struct callchain_node *root, 602 struct callchain_cursor *cursor, 603 u64 period) 604 { 605 struct callchain_list *cnode; 606 u64 start = cursor->pos; 607 bool found = false; 608 u64 matches; 609 int cmp = 0; 610 611 /* 612 * Lookup in the current node 613 * If we have a symbol, then compare the start to match 614 * anywhere inside a function, unless function 615 * mode is disabled. 616 */ 617 list_for_each_entry(cnode, &root->val, list) { 618 struct callchain_cursor_node *node; 619 620 node = callchain_cursor_current(cursor); 621 if (!node) 622 break; 623 624 cmp = match_chain(node, cnode); 625 if (cmp) 626 break; 627 628 found = true; 629 630 callchain_cursor_advance(cursor); 631 } 632 633 /* matches not, relay no the parent */ 634 if (!found) { 635 WARN_ONCE(!cmp, "Chain comparison error\n"); 636 return cmp; 637 } 638 639 matches = cursor->pos - start; 640 641 /* we match only a part of the node. Split it and add the new chain */ 642 if (matches < root->val_nr) { 643 split_add_child(root, cursor, cnode, start, matches, period); 644 return 0; 645 } 646 647 /* we match 100% of the path, increment the hit */ 648 if (matches == root->val_nr && cursor->pos == cursor->nr) { 649 root->hit += period; 650 return 0; 651 } 652 653 /* We match the node and still have a part remaining */ 654 append_chain_children(root, cursor, period); 655 656 return 0; 657 } 658 659 int callchain_append(struct callchain_root *root, 660 struct callchain_cursor *cursor, 661 u64 period) 662 { 663 if (!cursor->nr) 664 return 0; 665 666 callchain_cursor_commit(cursor); 667 668 append_chain_children(&root->node, cursor, period); 669 670 if (cursor->nr > root->max_depth) 671 root->max_depth = cursor->nr; 672 673 return 0; 674 } 675 676 static int 677 merge_chain_branch(struct callchain_cursor *cursor, 678 struct callchain_node *dst, struct callchain_node *src) 679 { 680 struct callchain_cursor_node **old_last = cursor->last; 681 struct callchain_node *child; 682 struct callchain_list *list, *next_list; 683 struct rb_node *n; 684 int old_pos = cursor->nr; 685 int err = 0; 686 687 list_for_each_entry_safe(list, next_list, &src->val, list) { 688 callchain_cursor_append(cursor, list->ip, 689 list->ms.map, list->ms.sym); 690 list_del(&list->list); 691 free(list); 692 } 693 694 if (src->hit) { 695 callchain_cursor_commit(cursor); 696 append_chain_children(dst, cursor, src->hit); 697 } 698 699 n = rb_first(&src->rb_root_in); 700 while (n) { 701 child = container_of(n, struct callchain_node, rb_node_in); 702 n = rb_next(n); 703 rb_erase(&child->rb_node_in, &src->rb_root_in); 704 705 err = merge_chain_branch(cursor, dst, child); 706 if (err) 707 break; 708 709 free(child); 710 } 711 712 cursor->nr = old_pos; 713 cursor->last = old_last; 714 715 return err; 716 } 717 718 int callchain_merge(struct callchain_cursor *cursor, 719 struct callchain_root *dst, struct callchain_root *src) 720 { 721 return merge_chain_branch(cursor, &dst->node, &src->node); 722 } 723 724 int callchain_cursor_append(struct callchain_cursor *cursor, 725 u64 ip, struct map *map, struct symbol *sym) 726 { 727 struct callchain_cursor_node *node = *cursor->last; 728 729 if (!node) { 730 node = calloc(1, sizeof(*node)); 731 if (!node) 732 return -ENOMEM; 733 734 *cursor->last = node; 735 } 736 737 node->ip = ip; 738 node->map = map; 739 node->sym = sym; 740 741 cursor->nr++; 742 743 cursor->last = &node->next; 744 745 return 0; 746 } 747 748 int sample__resolve_callchain(struct perf_sample *sample, struct symbol **parent, 749 struct perf_evsel *evsel, struct addr_location *al, 750 int max_stack) 751 { 752 if (sample->callchain == NULL) 753 return 0; 754 755 if (symbol_conf.use_callchain || symbol_conf.cumulate_callchain || 756 sort__has_parent) { 757 return machine__resolve_callchain(al->machine, evsel, al->thread, 758 sample, parent, al, max_stack); 759 } 760 return 0; 761 } 762 763 int hist_entry__append_callchain(struct hist_entry *he, struct perf_sample *sample) 764 { 765 if (!symbol_conf.use_callchain || sample->callchain == NULL) 766 return 0; 767 return callchain_append(he->callchain, &callchain_cursor, sample->period); 768 } 769 770 int fill_callchain_info(struct addr_location *al, struct callchain_cursor_node *node, 771 bool hide_unresolved) 772 { 773 al->map = node->map; 774 al->sym = node->sym; 775 if (node->map) 776 al->addr = node->map->map_ip(node->map, node->ip); 777 else 778 al->addr = node->ip; 779 780 if (al->sym == NULL) { 781 if (hide_unresolved) 782 return 0; 783 if (al->map == NULL) 784 goto out; 785 } 786 787 if (al->map->groups == &al->machine->kmaps) { 788 if (machine__is_host(al->machine)) { 789 al->cpumode = PERF_RECORD_MISC_KERNEL; 790 al->level = 'k'; 791 } else { 792 al->cpumode = PERF_RECORD_MISC_GUEST_KERNEL; 793 al->level = 'g'; 794 } 795 } else { 796 if (machine__is_host(al->machine)) { 797 al->cpumode = PERF_RECORD_MISC_USER; 798 al->level = '.'; 799 } else if (perf_guest) { 800 al->cpumode = PERF_RECORD_MISC_GUEST_USER; 801 al->level = 'u'; 802 } else { 803 al->cpumode = PERF_RECORD_MISC_HYPERVISOR; 804 al->level = 'H'; 805 } 806 } 807 808 out: 809 return 1; 810 } 811