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 int parse_callchain_record_opt(const char *arg, struct callchain_param *param) 29 { 30 return parse_callchain_record(arg, param); 31 } 32 33 static int parse_callchain_mode(const char *value) 34 { 35 if (!strncmp(value, "graph", strlen(value))) { 36 callchain_param.mode = CHAIN_GRAPH_ABS; 37 return 0; 38 } 39 if (!strncmp(value, "flat", strlen(value))) { 40 callchain_param.mode = CHAIN_FLAT; 41 return 0; 42 } 43 if (!strncmp(value, "fractal", strlen(value))) { 44 callchain_param.mode = CHAIN_GRAPH_REL; 45 return 0; 46 } 47 if (!strncmp(value, "folded", strlen(value))) { 48 callchain_param.mode = CHAIN_FOLDED; 49 return 0; 50 } 51 return -1; 52 } 53 54 static int parse_callchain_order(const char *value) 55 { 56 if (!strncmp(value, "caller", strlen(value))) { 57 callchain_param.order = ORDER_CALLER; 58 callchain_param.order_set = true; 59 return 0; 60 } 61 if (!strncmp(value, "callee", strlen(value))) { 62 callchain_param.order = ORDER_CALLEE; 63 callchain_param.order_set = true; 64 return 0; 65 } 66 return -1; 67 } 68 69 static int parse_callchain_sort_key(const char *value) 70 { 71 if (!strncmp(value, "function", strlen(value))) { 72 callchain_param.key = CCKEY_FUNCTION; 73 return 0; 74 } 75 if (!strncmp(value, "address", strlen(value))) { 76 callchain_param.key = CCKEY_ADDRESS; 77 return 0; 78 } 79 if (!strncmp(value, "branch", strlen(value))) { 80 callchain_param.branch_callstack = 1; 81 return 0; 82 } 83 return -1; 84 } 85 86 static int parse_callchain_value(const char *value) 87 { 88 if (!strncmp(value, "percent", strlen(value))) { 89 callchain_param.value = CCVAL_PERCENT; 90 return 0; 91 } 92 if (!strncmp(value, "period", strlen(value))) { 93 callchain_param.value = CCVAL_PERIOD; 94 return 0; 95 } 96 if (!strncmp(value, "count", strlen(value))) { 97 callchain_param.value = CCVAL_COUNT; 98 return 0; 99 } 100 return -1; 101 } 102 103 static int 104 __parse_callchain_report_opt(const char *arg, bool allow_record_opt) 105 { 106 char *tok; 107 char *endptr; 108 bool minpcnt_set = false; 109 bool record_opt_set = false; 110 bool try_stack_size = false; 111 112 callchain_param.enabled = true; 113 symbol_conf.use_callchain = true; 114 115 if (!arg) 116 return 0; 117 118 while ((tok = strtok((char *)arg, ",")) != NULL) { 119 if (!strncmp(tok, "none", strlen(tok))) { 120 callchain_param.mode = CHAIN_NONE; 121 callchain_param.enabled = false; 122 symbol_conf.use_callchain = false; 123 return 0; 124 } 125 126 if (!parse_callchain_mode(tok) || 127 !parse_callchain_order(tok) || 128 !parse_callchain_sort_key(tok) || 129 !parse_callchain_value(tok)) { 130 /* parsing ok - move on to the next */ 131 try_stack_size = false; 132 goto next; 133 } else if (allow_record_opt && !record_opt_set) { 134 if (parse_callchain_record(tok, &callchain_param)) 135 goto try_numbers; 136 137 /* assume that number followed by 'dwarf' is stack size */ 138 if (callchain_param.record_mode == CALLCHAIN_DWARF) 139 try_stack_size = true; 140 141 record_opt_set = true; 142 goto next; 143 } 144 145 try_numbers: 146 if (try_stack_size) { 147 unsigned long size = 0; 148 149 if (get_stack_size(tok, &size) < 0) 150 return -1; 151 callchain_param.dump_size = size; 152 try_stack_size = false; 153 } else if (!minpcnt_set) { 154 /* try to get the min percent */ 155 callchain_param.min_percent = strtod(tok, &endptr); 156 if (tok == endptr) 157 return -1; 158 minpcnt_set = true; 159 } else { 160 /* try print limit at last */ 161 callchain_param.print_limit = strtoul(tok, &endptr, 0); 162 if (tok == endptr) 163 return -1; 164 } 165 next: 166 arg = NULL; 167 } 168 169 if (callchain_register_param(&callchain_param) < 0) { 170 pr_err("Can't register callchain params\n"); 171 return -1; 172 } 173 return 0; 174 } 175 176 int parse_callchain_report_opt(const char *arg) 177 { 178 return __parse_callchain_report_opt(arg, false); 179 } 180 181 int parse_callchain_top_opt(const char *arg) 182 { 183 return __parse_callchain_report_opt(arg, true); 184 } 185 186 int perf_callchain_config(const char *var, const char *value) 187 { 188 char *endptr; 189 190 if (prefixcmp(var, "call-graph.")) 191 return 0; 192 var += sizeof("call-graph.") - 1; 193 194 if (!strcmp(var, "record-mode")) 195 return parse_callchain_record_opt(value, &callchain_param); 196 #ifdef HAVE_DWARF_UNWIND_SUPPORT 197 if (!strcmp(var, "dump-size")) { 198 unsigned long size = 0; 199 int ret; 200 201 ret = get_stack_size(value, &size); 202 callchain_param.dump_size = size; 203 204 return ret; 205 } 206 #endif 207 if (!strcmp(var, "print-type")) 208 return parse_callchain_mode(value); 209 if (!strcmp(var, "order")) 210 return parse_callchain_order(value); 211 if (!strcmp(var, "sort-key")) 212 return parse_callchain_sort_key(value); 213 if (!strcmp(var, "threshold")) { 214 callchain_param.min_percent = strtod(value, &endptr); 215 if (value == endptr) 216 return -1; 217 } 218 if (!strcmp(var, "print-limit")) { 219 callchain_param.print_limit = strtod(value, &endptr); 220 if (value == endptr) 221 return -1; 222 } 223 224 return 0; 225 } 226 227 static void 228 rb_insert_callchain(struct rb_root *root, struct callchain_node *chain, 229 enum chain_mode mode) 230 { 231 struct rb_node **p = &root->rb_node; 232 struct rb_node *parent = NULL; 233 struct callchain_node *rnode; 234 u64 chain_cumul = callchain_cumul_hits(chain); 235 236 while (*p) { 237 u64 rnode_cumul; 238 239 parent = *p; 240 rnode = rb_entry(parent, struct callchain_node, rb_node); 241 rnode_cumul = callchain_cumul_hits(rnode); 242 243 switch (mode) { 244 case CHAIN_FLAT: 245 case CHAIN_FOLDED: 246 if (rnode->hit < chain->hit) 247 p = &(*p)->rb_left; 248 else 249 p = &(*p)->rb_right; 250 break; 251 case CHAIN_GRAPH_ABS: /* Falldown */ 252 case CHAIN_GRAPH_REL: 253 if (rnode_cumul < chain_cumul) 254 p = &(*p)->rb_left; 255 else 256 p = &(*p)->rb_right; 257 break; 258 case CHAIN_NONE: 259 default: 260 break; 261 } 262 } 263 264 rb_link_node(&chain->rb_node, parent, p); 265 rb_insert_color(&chain->rb_node, root); 266 } 267 268 static void 269 __sort_chain_flat(struct rb_root *rb_root, struct callchain_node *node, 270 u64 min_hit) 271 { 272 struct rb_node *n; 273 struct callchain_node *child; 274 275 n = rb_first(&node->rb_root_in); 276 while (n) { 277 child = rb_entry(n, struct callchain_node, rb_node_in); 278 n = rb_next(n); 279 280 __sort_chain_flat(rb_root, child, min_hit); 281 } 282 283 if (node->hit && node->hit >= min_hit) 284 rb_insert_callchain(rb_root, node, CHAIN_FLAT); 285 } 286 287 /* 288 * Once we get every callchains from the stream, we can now 289 * sort them by hit 290 */ 291 static void 292 sort_chain_flat(struct rb_root *rb_root, struct callchain_root *root, 293 u64 min_hit, struct callchain_param *param __maybe_unused) 294 { 295 *rb_root = RB_ROOT; 296 __sort_chain_flat(rb_root, &root->node, min_hit); 297 } 298 299 static void __sort_chain_graph_abs(struct callchain_node *node, 300 u64 min_hit) 301 { 302 struct rb_node *n; 303 struct callchain_node *child; 304 305 node->rb_root = RB_ROOT; 306 n = rb_first(&node->rb_root_in); 307 308 while (n) { 309 child = rb_entry(n, struct callchain_node, rb_node_in); 310 n = rb_next(n); 311 312 __sort_chain_graph_abs(child, min_hit); 313 if (callchain_cumul_hits(child) >= min_hit) 314 rb_insert_callchain(&node->rb_root, child, 315 CHAIN_GRAPH_ABS); 316 } 317 } 318 319 static void 320 sort_chain_graph_abs(struct rb_root *rb_root, struct callchain_root *chain_root, 321 u64 min_hit, struct callchain_param *param __maybe_unused) 322 { 323 __sort_chain_graph_abs(&chain_root->node, min_hit); 324 rb_root->rb_node = chain_root->node.rb_root.rb_node; 325 } 326 327 static void __sort_chain_graph_rel(struct callchain_node *node, 328 double min_percent) 329 { 330 struct rb_node *n; 331 struct callchain_node *child; 332 u64 min_hit; 333 334 node->rb_root = RB_ROOT; 335 min_hit = ceil(node->children_hit * min_percent); 336 337 n = rb_first(&node->rb_root_in); 338 while (n) { 339 child = rb_entry(n, struct callchain_node, rb_node_in); 340 n = rb_next(n); 341 342 __sort_chain_graph_rel(child, min_percent); 343 if (callchain_cumul_hits(child) >= min_hit) 344 rb_insert_callchain(&node->rb_root, child, 345 CHAIN_GRAPH_REL); 346 } 347 } 348 349 static void 350 sort_chain_graph_rel(struct rb_root *rb_root, struct callchain_root *chain_root, 351 u64 min_hit __maybe_unused, struct callchain_param *param) 352 { 353 __sort_chain_graph_rel(&chain_root->node, param->min_percent / 100.0); 354 rb_root->rb_node = chain_root->node.rb_root.rb_node; 355 } 356 357 int callchain_register_param(struct callchain_param *param) 358 { 359 switch (param->mode) { 360 case CHAIN_GRAPH_ABS: 361 param->sort = sort_chain_graph_abs; 362 break; 363 case CHAIN_GRAPH_REL: 364 param->sort = sort_chain_graph_rel; 365 break; 366 case CHAIN_FLAT: 367 case CHAIN_FOLDED: 368 param->sort = sort_chain_flat; 369 break; 370 case CHAIN_NONE: 371 default: 372 return -1; 373 } 374 return 0; 375 } 376 377 /* 378 * Create a child for a parent. If inherit_children, then the new child 379 * will become the new parent of it's parent children 380 */ 381 static struct callchain_node * 382 create_child(struct callchain_node *parent, bool inherit_children) 383 { 384 struct callchain_node *new; 385 386 new = zalloc(sizeof(*new)); 387 if (!new) { 388 perror("not enough memory to create child for code path tree"); 389 return NULL; 390 } 391 new->parent = parent; 392 INIT_LIST_HEAD(&new->val); 393 INIT_LIST_HEAD(&new->parent_val); 394 395 if (inherit_children) { 396 struct rb_node *n; 397 struct callchain_node *child; 398 399 new->rb_root_in = parent->rb_root_in; 400 parent->rb_root_in = RB_ROOT; 401 402 n = rb_first(&new->rb_root_in); 403 while (n) { 404 child = rb_entry(n, struct callchain_node, rb_node_in); 405 child->parent = new; 406 n = rb_next(n); 407 } 408 409 /* make it the first child */ 410 rb_link_node(&new->rb_node_in, NULL, &parent->rb_root_in.rb_node); 411 rb_insert_color(&new->rb_node_in, &parent->rb_root_in); 412 } 413 414 return new; 415 } 416 417 418 /* 419 * Fill the node with callchain values 420 */ 421 static int 422 fill_node(struct callchain_node *node, struct callchain_cursor *cursor) 423 { 424 struct callchain_cursor_node *cursor_node; 425 426 node->val_nr = cursor->nr - cursor->pos; 427 if (!node->val_nr) 428 pr_warning("Warning: empty node in callchain tree\n"); 429 430 cursor_node = callchain_cursor_current(cursor); 431 432 while (cursor_node) { 433 struct callchain_list *call; 434 435 call = zalloc(sizeof(*call)); 436 if (!call) { 437 perror("not enough memory for the code path tree"); 438 return -1; 439 } 440 call->ip = cursor_node->ip; 441 call->ms.sym = cursor_node->sym; 442 call->ms.map = cursor_node->map; 443 list_add_tail(&call->list, &node->val); 444 445 callchain_cursor_advance(cursor); 446 cursor_node = callchain_cursor_current(cursor); 447 } 448 return 0; 449 } 450 451 static struct callchain_node * 452 add_child(struct callchain_node *parent, 453 struct callchain_cursor *cursor, 454 u64 period) 455 { 456 struct callchain_node *new; 457 458 new = create_child(parent, false); 459 if (new == NULL) 460 return NULL; 461 462 if (fill_node(new, cursor) < 0) { 463 struct callchain_list *call, *tmp; 464 465 list_for_each_entry_safe(call, tmp, &new->val, list) { 466 list_del(&call->list); 467 free(call); 468 } 469 free(new); 470 return NULL; 471 } 472 473 new->children_hit = 0; 474 new->hit = period; 475 new->children_count = 0; 476 new->count = 1; 477 return new; 478 } 479 480 enum match_result { 481 MATCH_ERROR = -1, 482 MATCH_EQ, 483 MATCH_LT, 484 MATCH_GT, 485 }; 486 487 static enum match_result match_chain(struct callchain_cursor_node *node, 488 struct callchain_list *cnode) 489 { 490 struct symbol *sym = node->sym; 491 u64 left, right; 492 493 if (cnode->ms.sym && sym && 494 callchain_param.key == CCKEY_FUNCTION) { 495 left = cnode->ms.sym->start; 496 right = sym->start; 497 } else { 498 left = cnode->ip; 499 right = node->ip; 500 } 501 502 if (left == right) 503 return MATCH_EQ; 504 505 return left > right ? MATCH_GT : MATCH_LT; 506 } 507 508 /* 509 * Split the parent in two parts (a new child is created) and 510 * give a part of its callchain to the created child. 511 * Then create another child to host the given callchain of new branch 512 */ 513 static int 514 split_add_child(struct callchain_node *parent, 515 struct callchain_cursor *cursor, 516 struct callchain_list *to_split, 517 u64 idx_parents, u64 idx_local, u64 period) 518 { 519 struct callchain_node *new; 520 struct list_head *old_tail; 521 unsigned int idx_total = idx_parents + idx_local; 522 523 /* split */ 524 new = create_child(parent, true); 525 if (new == NULL) 526 return -1; 527 528 /* split the callchain and move a part to the new child */ 529 old_tail = parent->val.prev; 530 list_del_range(&to_split->list, old_tail); 531 new->val.next = &to_split->list; 532 new->val.prev = old_tail; 533 to_split->list.prev = &new->val; 534 old_tail->next = &new->val; 535 536 /* split the hits */ 537 new->hit = parent->hit; 538 new->children_hit = parent->children_hit; 539 parent->children_hit = callchain_cumul_hits(new); 540 new->val_nr = parent->val_nr - idx_local; 541 parent->val_nr = idx_local; 542 new->count = parent->count; 543 new->children_count = parent->children_count; 544 parent->children_count = callchain_cumul_counts(new); 545 546 /* create a new child for the new branch if any */ 547 if (idx_total < cursor->nr) { 548 struct callchain_node *first; 549 struct callchain_list *cnode; 550 struct callchain_cursor_node *node; 551 struct rb_node *p, **pp; 552 553 parent->hit = 0; 554 parent->children_hit += period; 555 parent->count = 0; 556 parent->children_count += 1; 557 558 node = callchain_cursor_current(cursor); 559 new = add_child(parent, cursor, period); 560 if (new == NULL) 561 return -1; 562 563 /* 564 * This is second child since we moved parent's children 565 * to new (first) child above. 566 */ 567 p = parent->rb_root_in.rb_node; 568 first = rb_entry(p, struct callchain_node, rb_node_in); 569 cnode = list_first_entry(&first->val, struct callchain_list, 570 list); 571 572 if (match_chain(node, cnode) == MATCH_LT) 573 pp = &p->rb_left; 574 else 575 pp = &p->rb_right; 576 577 rb_link_node(&new->rb_node_in, p, pp); 578 rb_insert_color(&new->rb_node_in, &parent->rb_root_in); 579 } else { 580 parent->hit = period; 581 parent->count = 1; 582 } 583 return 0; 584 } 585 586 static enum match_result 587 append_chain(struct callchain_node *root, 588 struct callchain_cursor *cursor, 589 u64 period); 590 591 static int 592 append_chain_children(struct callchain_node *root, 593 struct callchain_cursor *cursor, 594 u64 period) 595 { 596 struct callchain_node *rnode; 597 struct callchain_cursor_node *node; 598 struct rb_node **p = &root->rb_root_in.rb_node; 599 struct rb_node *parent = NULL; 600 601 node = callchain_cursor_current(cursor); 602 if (!node) 603 return -1; 604 605 /* lookup in childrens */ 606 while (*p) { 607 enum match_result ret; 608 609 parent = *p; 610 rnode = rb_entry(parent, struct callchain_node, rb_node_in); 611 612 /* If at least first entry matches, rely to children */ 613 ret = append_chain(rnode, cursor, period); 614 if (ret == MATCH_EQ) 615 goto inc_children_hit; 616 if (ret == MATCH_ERROR) 617 return -1; 618 619 if (ret == MATCH_LT) 620 p = &parent->rb_left; 621 else 622 p = &parent->rb_right; 623 } 624 /* nothing in children, add to the current node */ 625 rnode = add_child(root, cursor, period); 626 if (rnode == NULL) 627 return -1; 628 629 rb_link_node(&rnode->rb_node_in, parent, p); 630 rb_insert_color(&rnode->rb_node_in, &root->rb_root_in); 631 632 inc_children_hit: 633 root->children_hit += period; 634 root->children_count++; 635 return 0; 636 } 637 638 static enum match_result 639 append_chain(struct callchain_node *root, 640 struct callchain_cursor *cursor, 641 u64 period) 642 { 643 struct callchain_list *cnode; 644 u64 start = cursor->pos; 645 bool found = false; 646 u64 matches; 647 enum match_result cmp = MATCH_ERROR; 648 649 /* 650 * Lookup in the current node 651 * If we have a symbol, then compare the start to match 652 * anywhere inside a function, unless function 653 * mode is disabled. 654 */ 655 list_for_each_entry(cnode, &root->val, list) { 656 struct callchain_cursor_node *node; 657 658 node = callchain_cursor_current(cursor); 659 if (!node) 660 break; 661 662 cmp = match_chain(node, cnode); 663 if (cmp != MATCH_EQ) 664 break; 665 666 found = true; 667 668 callchain_cursor_advance(cursor); 669 } 670 671 /* matches not, relay no the parent */ 672 if (!found) { 673 WARN_ONCE(cmp == MATCH_ERROR, "Chain comparison error\n"); 674 return cmp; 675 } 676 677 matches = cursor->pos - start; 678 679 /* we match only a part of the node. Split it and add the new chain */ 680 if (matches < root->val_nr) { 681 if (split_add_child(root, cursor, cnode, start, matches, 682 period) < 0) 683 return MATCH_ERROR; 684 685 return MATCH_EQ; 686 } 687 688 /* we match 100% of the path, increment the hit */ 689 if (matches == root->val_nr && cursor->pos == cursor->nr) { 690 root->hit += period; 691 root->count++; 692 return MATCH_EQ; 693 } 694 695 /* We match the node and still have a part remaining */ 696 if (append_chain_children(root, cursor, period) < 0) 697 return MATCH_ERROR; 698 699 return MATCH_EQ; 700 } 701 702 int callchain_append(struct callchain_root *root, 703 struct callchain_cursor *cursor, 704 u64 period) 705 { 706 if (!cursor->nr) 707 return 0; 708 709 callchain_cursor_commit(cursor); 710 711 if (append_chain_children(&root->node, cursor, period) < 0) 712 return -1; 713 714 if (cursor->nr > root->max_depth) 715 root->max_depth = cursor->nr; 716 717 return 0; 718 } 719 720 static int 721 merge_chain_branch(struct callchain_cursor *cursor, 722 struct callchain_node *dst, struct callchain_node *src) 723 { 724 struct callchain_cursor_node **old_last = cursor->last; 725 struct callchain_node *child; 726 struct callchain_list *list, *next_list; 727 struct rb_node *n; 728 int old_pos = cursor->nr; 729 int err = 0; 730 731 list_for_each_entry_safe(list, next_list, &src->val, list) { 732 callchain_cursor_append(cursor, list->ip, 733 list->ms.map, list->ms.sym); 734 list_del(&list->list); 735 free(list); 736 } 737 738 if (src->hit) { 739 callchain_cursor_commit(cursor); 740 if (append_chain_children(dst, cursor, src->hit) < 0) 741 return -1; 742 } 743 744 n = rb_first(&src->rb_root_in); 745 while (n) { 746 child = container_of(n, struct callchain_node, rb_node_in); 747 n = rb_next(n); 748 rb_erase(&child->rb_node_in, &src->rb_root_in); 749 750 err = merge_chain_branch(cursor, dst, child); 751 if (err) 752 break; 753 754 free(child); 755 } 756 757 cursor->nr = old_pos; 758 cursor->last = old_last; 759 760 return err; 761 } 762 763 int callchain_merge(struct callchain_cursor *cursor, 764 struct callchain_root *dst, struct callchain_root *src) 765 { 766 return merge_chain_branch(cursor, &dst->node, &src->node); 767 } 768 769 int callchain_cursor_append(struct callchain_cursor *cursor, 770 u64 ip, struct map *map, struct symbol *sym) 771 { 772 struct callchain_cursor_node *node = *cursor->last; 773 774 if (!node) { 775 node = calloc(1, sizeof(*node)); 776 if (!node) 777 return -ENOMEM; 778 779 *cursor->last = node; 780 } 781 782 node->ip = ip; 783 node->map = map; 784 node->sym = sym; 785 786 cursor->nr++; 787 788 cursor->last = &node->next; 789 790 return 0; 791 } 792 793 int sample__resolve_callchain(struct perf_sample *sample, 794 struct callchain_cursor *cursor, struct symbol **parent, 795 struct perf_evsel *evsel, struct addr_location *al, 796 int max_stack) 797 { 798 if (sample->callchain == NULL) 799 return 0; 800 801 if (symbol_conf.use_callchain || symbol_conf.cumulate_callchain || 802 perf_hpp_list.parent) { 803 return thread__resolve_callchain(al->thread, cursor, evsel, sample, 804 parent, al, max_stack); 805 } 806 return 0; 807 } 808 809 int hist_entry__append_callchain(struct hist_entry *he, struct perf_sample *sample) 810 { 811 if (!symbol_conf.use_callchain || sample->callchain == NULL) 812 return 0; 813 return callchain_append(he->callchain, &callchain_cursor, sample->period); 814 } 815 816 int fill_callchain_info(struct addr_location *al, struct callchain_cursor_node *node, 817 bool hide_unresolved) 818 { 819 al->map = node->map; 820 al->sym = node->sym; 821 if (node->map) 822 al->addr = node->map->map_ip(node->map, node->ip); 823 else 824 al->addr = node->ip; 825 826 if (al->sym == NULL) { 827 if (hide_unresolved) 828 return 0; 829 if (al->map == NULL) 830 goto out; 831 } 832 833 if (al->map->groups == &al->machine->kmaps) { 834 if (machine__is_host(al->machine)) { 835 al->cpumode = PERF_RECORD_MISC_KERNEL; 836 al->level = 'k'; 837 } else { 838 al->cpumode = PERF_RECORD_MISC_GUEST_KERNEL; 839 al->level = 'g'; 840 } 841 } else { 842 if (machine__is_host(al->machine)) { 843 al->cpumode = PERF_RECORD_MISC_USER; 844 al->level = '.'; 845 } else if (perf_guest) { 846 al->cpumode = PERF_RECORD_MISC_GUEST_USER; 847 al->level = 'u'; 848 } else { 849 al->cpumode = PERF_RECORD_MISC_HYPERVISOR; 850 al->level = 'H'; 851 } 852 } 853 854 out: 855 return 1; 856 } 857 858 char *callchain_list__sym_name(struct callchain_list *cl, 859 char *bf, size_t bfsize, bool show_dso) 860 { 861 int printed; 862 863 if (cl->ms.sym) { 864 if (callchain_param.key == CCKEY_ADDRESS && 865 cl->ms.map && !cl->srcline) 866 cl->srcline = get_srcline(cl->ms.map->dso, 867 map__rip_2objdump(cl->ms.map, 868 cl->ip), 869 cl->ms.sym, false); 870 if (cl->srcline) 871 printed = scnprintf(bf, bfsize, "%s %s", 872 cl->ms.sym->name, cl->srcline); 873 else 874 printed = scnprintf(bf, bfsize, "%s", cl->ms.sym->name); 875 } else 876 printed = scnprintf(bf, bfsize, "%#" PRIx64, cl->ip); 877 878 if (show_dso) 879 scnprintf(bf + printed, bfsize - printed, " %s", 880 cl->ms.map ? 881 cl->ms.map->dso->short_name : 882 "unknown"); 883 884 return bf; 885 } 886 887 char *callchain_node__scnprintf_value(struct callchain_node *node, 888 char *bf, size_t bfsize, u64 total) 889 { 890 double percent = 0.0; 891 u64 period = callchain_cumul_hits(node); 892 unsigned count = callchain_cumul_counts(node); 893 894 if (callchain_param.mode == CHAIN_FOLDED) { 895 period = node->hit; 896 count = node->count; 897 } 898 899 switch (callchain_param.value) { 900 case CCVAL_PERIOD: 901 scnprintf(bf, bfsize, "%"PRIu64, period); 902 break; 903 case CCVAL_COUNT: 904 scnprintf(bf, bfsize, "%u", count); 905 break; 906 case CCVAL_PERCENT: 907 default: 908 if (total) 909 percent = period * 100.0 / total; 910 scnprintf(bf, bfsize, "%.2f%%", percent); 911 break; 912 } 913 return bf; 914 } 915 916 int callchain_node__fprintf_value(struct callchain_node *node, 917 FILE *fp, u64 total) 918 { 919 double percent = 0.0; 920 u64 period = callchain_cumul_hits(node); 921 unsigned count = callchain_cumul_counts(node); 922 923 if (callchain_param.mode == CHAIN_FOLDED) { 924 period = node->hit; 925 count = node->count; 926 } 927 928 switch (callchain_param.value) { 929 case CCVAL_PERIOD: 930 return fprintf(fp, "%"PRIu64, period); 931 case CCVAL_COUNT: 932 return fprintf(fp, "%u", count); 933 case CCVAL_PERCENT: 934 default: 935 if (total) 936 percent = period * 100.0 / total; 937 return percent_color_fprintf(fp, "%.2f%%", percent); 938 } 939 return 0; 940 } 941 942 static void free_callchain_node(struct callchain_node *node) 943 { 944 struct callchain_list *list, *tmp; 945 struct callchain_node *child; 946 struct rb_node *n; 947 948 list_for_each_entry_safe(list, tmp, &node->parent_val, list) { 949 list_del(&list->list); 950 free(list); 951 } 952 953 list_for_each_entry_safe(list, tmp, &node->val, list) { 954 list_del(&list->list); 955 free(list); 956 } 957 958 n = rb_first(&node->rb_root_in); 959 while (n) { 960 child = container_of(n, struct callchain_node, rb_node_in); 961 n = rb_next(n); 962 rb_erase(&child->rb_node_in, &node->rb_root_in); 963 964 free_callchain_node(child); 965 free(child); 966 } 967 } 968 969 void free_callchain(struct callchain_root *root) 970 { 971 if (!symbol_conf.use_callchain) 972 return; 973 974 free_callchain_node(&root->node); 975 } 976 977 static u64 decay_callchain_node(struct callchain_node *node) 978 { 979 struct callchain_node *child; 980 struct rb_node *n; 981 u64 child_hits = 0; 982 983 n = rb_first(&node->rb_root_in); 984 while (n) { 985 child = container_of(n, struct callchain_node, rb_node_in); 986 987 child_hits += decay_callchain_node(child); 988 n = rb_next(n); 989 } 990 991 node->hit = (node->hit * 7) / 8; 992 node->children_hit = child_hits; 993 994 return node->hit; 995 } 996 997 void decay_callchain(struct callchain_root *root) 998 { 999 if (!symbol_conf.use_callchain) 1000 return; 1001 1002 decay_callchain_node(&root->node); 1003 } 1004 1005 int callchain_node__make_parent_list(struct callchain_node *node) 1006 { 1007 struct callchain_node *parent = node->parent; 1008 struct callchain_list *chain, *new; 1009 LIST_HEAD(head); 1010 1011 while (parent) { 1012 list_for_each_entry_reverse(chain, &parent->val, list) { 1013 new = malloc(sizeof(*new)); 1014 if (new == NULL) 1015 goto out; 1016 *new = *chain; 1017 new->has_children = false; 1018 list_add_tail(&new->list, &head); 1019 } 1020 parent = parent->parent; 1021 } 1022 1023 list_for_each_entry_safe_reverse(chain, new, &head, list) 1024 list_move_tail(&chain->list, &node->parent_val); 1025 1026 if (!list_empty(&node->parent_val)) { 1027 chain = list_first_entry(&node->parent_val, struct callchain_list, list); 1028 chain->has_children = rb_prev(&node->rb_node) || rb_next(&node->rb_node); 1029 1030 chain = list_first_entry(&node->val, struct callchain_list, list); 1031 chain->has_children = false; 1032 } 1033 return 0; 1034 1035 out: 1036 list_for_each_entry_safe(chain, new, &head, list) { 1037 list_del(&chain->list); 1038 free(chain); 1039 } 1040 return -ENOMEM; 1041 } 1042