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 --call-graph 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 if (!strncmp(value, "branch", strlen(value))) { 153 callchain_param.branch_callstack = 1; 154 return 0; 155 } 156 return -1; 157 } 158 159 int 160 parse_callchain_report_opt(const char *arg) 161 { 162 char *tok; 163 char *endptr; 164 bool minpcnt_set = false; 165 166 symbol_conf.use_callchain = true; 167 168 if (!arg) 169 return 0; 170 171 while ((tok = strtok((char *)arg, ",")) != NULL) { 172 if (!strncmp(tok, "none", strlen(tok))) { 173 callchain_param.mode = CHAIN_NONE; 174 symbol_conf.use_callchain = false; 175 return 0; 176 } 177 178 if (!parse_callchain_mode(tok) || 179 !parse_callchain_order(tok) || 180 !parse_callchain_sort_key(tok)) { 181 /* parsing ok - move on to the next */ 182 } else if (!minpcnt_set) { 183 /* try to get the min percent */ 184 callchain_param.min_percent = strtod(tok, &endptr); 185 if (tok == endptr) 186 return -1; 187 minpcnt_set = true; 188 } else { 189 /* try print limit at last */ 190 callchain_param.print_limit = strtoul(tok, &endptr, 0); 191 if (tok == endptr) 192 return -1; 193 } 194 195 arg = NULL; 196 } 197 198 if (callchain_register_param(&callchain_param) < 0) { 199 pr_err("Can't register callchain params\n"); 200 return -1; 201 } 202 return 0; 203 } 204 205 int perf_callchain_config(const char *var, const char *value) 206 { 207 char *endptr; 208 209 if (prefixcmp(var, "call-graph.")) 210 return 0; 211 var += sizeof("call-graph.") - 1; 212 213 if (!strcmp(var, "record-mode")) 214 return parse_callchain_record_opt(value); 215 #ifdef HAVE_DWARF_UNWIND_SUPPORT 216 if (!strcmp(var, "dump-size")) { 217 unsigned long size = 0; 218 int ret; 219 220 ret = get_stack_size(value, &size); 221 callchain_param.dump_size = size; 222 223 return ret; 224 } 225 #endif 226 if (!strcmp(var, "print-type")) 227 return parse_callchain_mode(value); 228 if (!strcmp(var, "order")) 229 return parse_callchain_order(value); 230 if (!strcmp(var, "sort-key")) 231 return parse_callchain_sort_key(value); 232 if (!strcmp(var, "threshold")) { 233 callchain_param.min_percent = strtod(value, &endptr); 234 if (value == endptr) 235 return -1; 236 } 237 if (!strcmp(var, "print-limit")) { 238 callchain_param.print_limit = strtod(value, &endptr); 239 if (value == endptr) 240 return -1; 241 } 242 243 return 0; 244 } 245 246 static void 247 rb_insert_callchain(struct rb_root *root, struct callchain_node *chain, 248 enum chain_mode mode) 249 { 250 struct rb_node **p = &root->rb_node; 251 struct rb_node *parent = NULL; 252 struct callchain_node *rnode; 253 u64 chain_cumul = callchain_cumul_hits(chain); 254 255 while (*p) { 256 u64 rnode_cumul; 257 258 parent = *p; 259 rnode = rb_entry(parent, struct callchain_node, rb_node); 260 rnode_cumul = callchain_cumul_hits(rnode); 261 262 switch (mode) { 263 case CHAIN_FLAT: 264 if (rnode->hit < chain->hit) 265 p = &(*p)->rb_left; 266 else 267 p = &(*p)->rb_right; 268 break; 269 case CHAIN_GRAPH_ABS: /* Falldown */ 270 case CHAIN_GRAPH_REL: 271 if (rnode_cumul < chain_cumul) 272 p = &(*p)->rb_left; 273 else 274 p = &(*p)->rb_right; 275 break; 276 case CHAIN_NONE: 277 default: 278 break; 279 } 280 } 281 282 rb_link_node(&chain->rb_node, parent, p); 283 rb_insert_color(&chain->rb_node, root); 284 } 285 286 static void 287 __sort_chain_flat(struct rb_root *rb_root, struct callchain_node *node, 288 u64 min_hit) 289 { 290 struct rb_node *n; 291 struct callchain_node *child; 292 293 n = rb_first(&node->rb_root_in); 294 while (n) { 295 child = rb_entry(n, struct callchain_node, rb_node_in); 296 n = rb_next(n); 297 298 __sort_chain_flat(rb_root, child, min_hit); 299 } 300 301 if (node->hit && node->hit >= min_hit) 302 rb_insert_callchain(rb_root, node, CHAIN_FLAT); 303 } 304 305 /* 306 * Once we get every callchains from the stream, we can now 307 * sort them by hit 308 */ 309 static void 310 sort_chain_flat(struct rb_root *rb_root, struct callchain_root *root, 311 u64 min_hit, struct callchain_param *param __maybe_unused) 312 { 313 __sort_chain_flat(rb_root, &root->node, min_hit); 314 } 315 316 static void __sort_chain_graph_abs(struct callchain_node *node, 317 u64 min_hit) 318 { 319 struct rb_node *n; 320 struct callchain_node *child; 321 322 node->rb_root = RB_ROOT; 323 n = rb_first(&node->rb_root_in); 324 325 while (n) { 326 child = rb_entry(n, struct callchain_node, rb_node_in); 327 n = rb_next(n); 328 329 __sort_chain_graph_abs(child, min_hit); 330 if (callchain_cumul_hits(child) >= min_hit) 331 rb_insert_callchain(&node->rb_root, child, 332 CHAIN_GRAPH_ABS); 333 } 334 } 335 336 static void 337 sort_chain_graph_abs(struct rb_root *rb_root, struct callchain_root *chain_root, 338 u64 min_hit, struct callchain_param *param __maybe_unused) 339 { 340 __sort_chain_graph_abs(&chain_root->node, min_hit); 341 rb_root->rb_node = chain_root->node.rb_root.rb_node; 342 } 343 344 static void __sort_chain_graph_rel(struct callchain_node *node, 345 double min_percent) 346 { 347 struct rb_node *n; 348 struct callchain_node *child; 349 u64 min_hit; 350 351 node->rb_root = RB_ROOT; 352 min_hit = ceil(node->children_hit * min_percent); 353 354 n = rb_first(&node->rb_root_in); 355 while (n) { 356 child = rb_entry(n, struct callchain_node, rb_node_in); 357 n = rb_next(n); 358 359 __sort_chain_graph_rel(child, min_percent); 360 if (callchain_cumul_hits(child) >= min_hit) 361 rb_insert_callchain(&node->rb_root, child, 362 CHAIN_GRAPH_REL); 363 } 364 } 365 366 static void 367 sort_chain_graph_rel(struct rb_root *rb_root, struct callchain_root *chain_root, 368 u64 min_hit __maybe_unused, struct callchain_param *param) 369 { 370 __sort_chain_graph_rel(&chain_root->node, param->min_percent / 100.0); 371 rb_root->rb_node = chain_root->node.rb_root.rb_node; 372 } 373 374 int callchain_register_param(struct callchain_param *param) 375 { 376 switch (param->mode) { 377 case CHAIN_GRAPH_ABS: 378 param->sort = sort_chain_graph_abs; 379 break; 380 case CHAIN_GRAPH_REL: 381 param->sort = sort_chain_graph_rel; 382 break; 383 case CHAIN_FLAT: 384 param->sort = sort_chain_flat; 385 break; 386 case CHAIN_NONE: 387 default: 388 return -1; 389 } 390 return 0; 391 } 392 393 /* 394 * Create a child for a parent. If inherit_children, then the new child 395 * will become the new parent of it's parent children 396 */ 397 static struct callchain_node * 398 create_child(struct callchain_node *parent, bool inherit_children) 399 { 400 struct callchain_node *new; 401 402 new = zalloc(sizeof(*new)); 403 if (!new) { 404 perror("not enough memory to create child for code path tree"); 405 return NULL; 406 } 407 new->parent = parent; 408 INIT_LIST_HEAD(&new->val); 409 410 if (inherit_children) { 411 struct rb_node *n; 412 struct callchain_node *child; 413 414 new->rb_root_in = parent->rb_root_in; 415 parent->rb_root_in = RB_ROOT; 416 417 n = rb_first(&new->rb_root_in); 418 while (n) { 419 child = rb_entry(n, struct callchain_node, rb_node_in); 420 child->parent = new; 421 n = rb_next(n); 422 } 423 424 /* make it the first child */ 425 rb_link_node(&new->rb_node_in, NULL, &parent->rb_root_in.rb_node); 426 rb_insert_color(&new->rb_node_in, &parent->rb_root_in); 427 } 428 429 return new; 430 } 431 432 433 /* 434 * Fill the node with callchain values 435 */ 436 static void 437 fill_node(struct callchain_node *node, struct callchain_cursor *cursor) 438 { 439 struct callchain_cursor_node *cursor_node; 440 441 node->val_nr = cursor->nr - cursor->pos; 442 if (!node->val_nr) 443 pr_warning("Warning: empty node in callchain tree\n"); 444 445 cursor_node = callchain_cursor_current(cursor); 446 447 while (cursor_node) { 448 struct callchain_list *call; 449 450 call = zalloc(sizeof(*call)); 451 if (!call) { 452 perror("not enough memory for the code path tree"); 453 return; 454 } 455 call->ip = cursor_node->ip; 456 call->ms.sym = cursor_node->sym; 457 call->ms.map = cursor_node->map; 458 list_add_tail(&call->list, &node->val); 459 460 callchain_cursor_advance(cursor); 461 cursor_node = callchain_cursor_current(cursor); 462 } 463 } 464 465 static struct callchain_node * 466 add_child(struct callchain_node *parent, 467 struct callchain_cursor *cursor, 468 u64 period) 469 { 470 struct callchain_node *new; 471 472 new = create_child(parent, false); 473 fill_node(new, cursor); 474 475 new->children_hit = 0; 476 new->hit = period; 477 return new; 478 } 479 480 static s64 match_chain(struct callchain_cursor_node *node, 481 struct callchain_list *cnode) 482 { 483 struct symbol *sym = node->sym; 484 485 if (cnode->ms.sym && sym && 486 callchain_param.key == CCKEY_FUNCTION) 487 return cnode->ms.sym->start - sym->start; 488 else 489 return cnode->ip - node->ip; 490 } 491 492 /* 493 * Split the parent in two parts (a new child is created) and 494 * give a part of its callchain to the created child. 495 * Then create another child to host the given callchain of new branch 496 */ 497 static void 498 split_add_child(struct callchain_node *parent, 499 struct callchain_cursor *cursor, 500 struct callchain_list *to_split, 501 u64 idx_parents, u64 idx_local, u64 period) 502 { 503 struct callchain_node *new; 504 struct list_head *old_tail; 505 unsigned int idx_total = idx_parents + idx_local; 506 507 /* split */ 508 new = create_child(parent, true); 509 510 /* split the callchain and move a part to the new child */ 511 old_tail = parent->val.prev; 512 list_del_range(&to_split->list, old_tail); 513 new->val.next = &to_split->list; 514 new->val.prev = old_tail; 515 to_split->list.prev = &new->val; 516 old_tail->next = &new->val; 517 518 /* split the hits */ 519 new->hit = parent->hit; 520 new->children_hit = parent->children_hit; 521 parent->children_hit = callchain_cumul_hits(new); 522 new->val_nr = parent->val_nr - idx_local; 523 parent->val_nr = idx_local; 524 525 /* create a new child for the new branch if any */ 526 if (idx_total < cursor->nr) { 527 struct callchain_node *first; 528 struct callchain_list *cnode; 529 struct callchain_cursor_node *node; 530 struct rb_node *p, **pp; 531 532 parent->hit = 0; 533 parent->children_hit += period; 534 535 node = callchain_cursor_current(cursor); 536 new = add_child(parent, cursor, period); 537 538 /* 539 * This is second child since we moved parent's children 540 * to new (first) child above. 541 */ 542 p = parent->rb_root_in.rb_node; 543 first = rb_entry(p, struct callchain_node, rb_node_in); 544 cnode = list_first_entry(&first->val, struct callchain_list, 545 list); 546 547 if (match_chain(node, cnode) < 0) 548 pp = &p->rb_left; 549 else 550 pp = &p->rb_right; 551 552 rb_link_node(&new->rb_node_in, p, pp); 553 rb_insert_color(&new->rb_node_in, &parent->rb_root_in); 554 } else { 555 parent->hit = period; 556 } 557 } 558 559 static int 560 append_chain(struct callchain_node *root, 561 struct callchain_cursor *cursor, 562 u64 period); 563 564 static void 565 append_chain_children(struct callchain_node *root, 566 struct callchain_cursor *cursor, 567 u64 period) 568 { 569 struct callchain_node *rnode; 570 struct callchain_cursor_node *node; 571 struct rb_node **p = &root->rb_root_in.rb_node; 572 struct rb_node *parent = NULL; 573 574 node = callchain_cursor_current(cursor); 575 if (!node) 576 return; 577 578 /* lookup in childrens */ 579 while (*p) { 580 s64 ret; 581 582 parent = *p; 583 rnode = rb_entry(parent, struct callchain_node, rb_node_in); 584 585 /* If at least first entry matches, rely to children */ 586 ret = append_chain(rnode, cursor, period); 587 if (ret == 0) 588 goto inc_children_hit; 589 590 if (ret < 0) 591 p = &parent->rb_left; 592 else 593 p = &parent->rb_right; 594 } 595 /* nothing in children, add to the current node */ 596 rnode = add_child(root, cursor, period); 597 rb_link_node(&rnode->rb_node_in, parent, p); 598 rb_insert_color(&rnode->rb_node_in, &root->rb_root_in); 599 600 inc_children_hit: 601 root->children_hit += period; 602 } 603 604 static int 605 append_chain(struct callchain_node *root, 606 struct callchain_cursor *cursor, 607 u64 period) 608 { 609 struct callchain_list *cnode; 610 u64 start = cursor->pos; 611 bool found = false; 612 u64 matches; 613 int cmp = 0; 614 615 /* 616 * Lookup in the current node 617 * If we have a symbol, then compare the start to match 618 * anywhere inside a function, unless function 619 * mode is disabled. 620 */ 621 list_for_each_entry(cnode, &root->val, list) { 622 struct callchain_cursor_node *node; 623 624 node = callchain_cursor_current(cursor); 625 if (!node) 626 break; 627 628 cmp = match_chain(node, cnode); 629 if (cmp) 630 break; 631 632 found = true; 633 634 callchain_cursor_advance(cursor); 635 } 636 637 /* matches not, relay no the parent */ 638 if (!found) { 639 WARN_ONCE(!cmp, "Chain comparison error\n"); 640 return cmp; 641 } 642 643 matches = cursor->pos - start; 644 645 /* we match only a part of the node. Split it and add the new chain */ 646 if (matches < root->val_nr) { 647 split_add_child(root, cursor, cnode, start, matches, period); 648 return 0; 649 } 650 651 /* we match 100% of the path, increment the hit */ 652 if (matches == root->val_nr && cursor->pos == cursor->nr) { 653 root->hit += period; 654 return 0; 655 } 656 657 /* We match the node and still have a part remaining */ 658 append_chain_children(root, cursor, period); 659 660 return 0; 661 } 662 663 int callchain_append(struct callchain_root *root, 664 struct callchain_cursor *cursor, 665 u64 period) 666 { 667 if (!cursor->nr) 668 return 0; 669 670 callchain_cursor_commit(cursor); 671 672 append_chain_children(&root->node, cursor, period); 673 674 if (cursor->nr > root->max_depth) 675 root->max_depth = cursor->nr; 676 677 return 0; 678 } 679 680 static int 681 merge_chain_branch(struct callchain_cursor *cursor, 682 struct callchain_node *dst, struct callchain_node *src) 683 { 684 struct callchain_cursor_node **old_last = cursor->last; 685 struct callchain_node *child; 686 struct callchain_list *list, *next_list; 687 struct rb_node *n; 688 int old_pos = cursor->nr; 689 int err = 0; 690 691 list_for_each_entry_safe(list, next_list, &src->val, list) { 692 callchain_cursor_append(cursor, list->ip, 693 list->ms.map, list->ms.sym); 694 list_del(&list->list); 695 free(list); 696 } 697 698 if (src->hit) { 699 callchain_cursor_commit(cursor); 700 append_chain_children(dst, cursor, src->hit); 701 } 702 703 n = rb_first(&src->rb_root_in); 704 while (n) { 705 child = container_of(n, struct callchain_node, rb_node_in); 706 n = rb_next(n); 707 rb_erase(&child->rb_node_in, &src->rb_root_in); 708 709 err = merge_chain_branch(cursor, dst, child); 710 if (err) 711 break; 712 713 free(child); 714 } 715 716 cursor->nr = old_pos; 717 cursor->last = old_last; 718 719 return err; 720 } 721 722 int callchain_merge(struct callchain_cursor *cursor, 723 struct callchain_root *dst, struct callchain_root *src) 724 { 725 return merge_chain_branch(cursor, &dst->node, &src->node); 726 } 727 728 int callchain_cursor_append(struct callchain_cursor *cursor, 729 u64 ip, struct map *map, struct symbol *sym) 730 { 731 struct callchain_cursor_node *node = *cursor->last; 732 733 if (!node) { 734 node = calloc(1, sizeof(*node)); 735 if (!node) 736 return -ENOMEM; 737 738 *cursor->last = node; 739 } 740 741 node->ip = ip; 742 node->map = map; 743 node->sym = sym; 744 745 cursor->nr++; 746 747 cursor->last = &node->next; 748 749 return 0; 750 } 751 752 int sample__resolve_callchain(struct perf_sample *sample, struct symbol **parent, 753 struct perf_evsel *evsel, struct addr_location *al, 754 int max_stack) 755 { 756 if (sample->callchain == NULL) 757 return 0; 758 759 if (symbol_conf.use_callchain || symbol_conf.cumulate_callchain || 760 sort__has_parent) { 761 return thread__resolve_callchain(al->thread, evsel, sample, 762 parent, al, max_stack); 763 } 764 return 0; 765 } 766 767 int hist_entry__append_callchain(struct hist_entry *he, struct perf_sample *sample) 768 { 769 if (!symbol_conf.use_callchain || sample->callchain == NULL) 770 return 0; 771 return callchain_append(he->callchain, &callchain_cursor, sample->period); 772 } 773 774 int fill_callchain_info(struct addr_location *al, struct callchain_cursor_node *node, 775 bool hide_unresolved) 776 { 777 al->map = node->map; 778 al->sym = node->sym; 779 if (node->map) 780 al->addr = node->map->map_ip(node->map, node->ip); 781 else 782 al->addr = node->ip; 783 784 if (al->sym == NULL) { 785 if (hide_unresolved) 786 return 0; 787 if (al->map == NULL) 788 goto out; 789 } 790 791 if (al->map->groups == &al->machine->kmaps) { 792 if (machine__is_host(al->machine)) { 793 al->cpumode = PERF_RECORD_MISC_KERNEL; 794 al->level = 'k'; 795 } else { 796 al->cpumode = PERF_RECORD_MISC_GUEST_KERNEL; 797 al->level = 'g'; 798 } 799 } else { 800 if (machine__is_host(al->machine)) { 801 al->cpumode = PERF_RECORD_MISC_USER; 802 al->level = '.'; 803 } else if (perf_guest) { 804 al->cpumode = PERF_RECORD_MISC_GUEST_USER; 805 al->level = 'u'; 806 } else { 807 al->cpumode = PERF_RECORD_MISC_HYPERVISOR; 808 al->level = 'H'; 809 } 810 } 811 812 out: 813 return 1; 814 } 815 816 char *callchain_list__sym_name(struct callchain_list *cl, 817 char *bf, size_t bfsize, bool show_dso) 818 { 819 int printed; 820 821 if (cl->ms.sym) { 822 if (callchain_param.key == CCKEY_ADDRESS && 823 cl->ms.map && !cl->srcline) 824 cl->srcline = get_srcline(cl->ms.map->dso, 825 map__rip_2objdump(cl->ms.map, 826 cl->ip), 827 cl->ms.sym, false); 828 if (cl->srcline) 829 printed = scnprintf(bf, bfsize, "%s %s", 830 cl->ms.sym->name, cl->srcline); 831 else 832 printed = scnprintf(bf, bfsize, "%s", cl->ms.sym->name); 833 } else 834 printed = scnprintf(bf, bfsize, "%#" PRIx64, cl->ip); 835 836 if (show_dso) 837 scnprintf(bf + printed, bfsize - printed, " %s", 838 cl->ms.map ? 839 cl->ms.map->dso->short_name : 840 "unknown"); 841 842 return bf; 843 } 844 845 static void free_callchain_node(struct callchain_node *node) 846 { 847 struct callchain_list *list, *tmp; 848 struct callchain_node *child; 849 struct rb_node *n; 850 851 list_for_each_entry_safe(list, tmp, &node->val, list) { 852 list_del(&list->list); 853 free(list); 854 } 855 856 n = rb_first(&node->rb_root_in); 857 while (n) { 858 child = container_of(n, struct callchain_node, rb_node_in); 859 n = rb_next(n); 860 rb_erase(&child->rb_node_in, &node->rb_root_in); 861 862 free_callchain_node(child); 863 free(child); 864 } 865 } 866 867 void free_callchain(struct callchain_root *root) 868 { 869 if (!symbol_conf.use_callchain) 870 return; 871 872 free_callchain_node(&root->node); 873 } 874