tools/perf/util/callchain.c

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