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