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