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 <inttypes.h>
  13 #include <stdlib.h>
  14 #include <stdio.h>
  15 #include <stdbool.h>
  16 #include <errno.h>
  17 #include <math.h>
  18
  19 #include "asm/bug.h"
  20
  21 #include "hist.h"
  22 #include "util.h"
  23 #include "sort.h"
  24 #include "machine.h"
  25 #include "callchain.h"
  26
  27 #define CALLCHAIN_PARAM_DEFAULT                 \
  28         .mode           = CHAIN_GRAPH_ABS,      \
  29         .min_percent    = 0.5,                  \
  30         .order          = ORDER_CALLEE,         \
  31         .key            = CCKEY_FUNCTION,       \
  32         .value          = CCVAL_PERCENT,        \
  33
  34 struct callchain_param callchain_param = {
  35         CALLCHAIN_PARAM_DEFAULT
  36 };
  37
  38 struct callchain_param callchain_param_default = {
  39         CALLCHAIN_PARAM_DEFAULT
  40 };
  41
  42 __thread struct callchain_cursor callchain_cursor;
  43
  44 int parse_callchain_record_opt(const char *arg, struct callchain_param *param)
  45 {
  46         return parse_callchain_record(arg, param);
  47 }
  48
  49 static int parse_callchain_mode(const char *value)
  50 {
  51         if (!strncmp(value, "graph", strlen(value))) {
  52                 callchain_param.mode = CHAIN_GRAPH_ABS;
  53                 return 0;
  54         }
  55         if (!strncmp(value, "flat", strlen(value))) {
  56                 callchain_param.mode = CHAIN_FLAT;
  57                 return 0;
  58         }
  59         if (!strncmp(value, "fractal", strlen(value))) {
  60                 callchain_param.mode = CHAIN_GRAPH_REL;
  61                 return 0;
  62         }
  63         if (!strncmp(value, "folded", strlen(value))) {
  64                 callchain_param.mode = CHAIN_FOLDED;
  65                 return 0;
  66         }
  67
  68         pr_err("Invalid callchain mode: %s\n", value);
  69         return -1;
  70 }
  71
  72 static int parse_callchain_order(const char *value)
  73 {
  74         if (!strncmp(value, "caller", strlen(value))) {
  75                 callchain_param.order = ORDER_CALLER;
  76                 callchain_param.order_set = true;
  77                 return 0;
  78         }
  79         if (!strncmp(value, "callee", strlen(value))) {
  80                 callchain_param.order = ORDER_CALLEE;
  81                 callchain_param.order_set = true;
  82                 return 0;
  83         }
  84
  85         pr_err("Invalid callchain order: %s\n", value);
  86         return -1;
  87 }
  88
  89 static int parse_callchain_sort_key(const char *value)
  90 {
  91         if (!strncmp(value, "function", strlen(value))) {
  92                 callchain_param.key = CCKEY_FUNCTION;
  93                 return 0;
  94         }
  95         if (!strncmp(value, "address", strlen(value))) {
  96                 callchain_param.key = CCKEY_ADDRESS;
  97                 return 0;
  98         }
  99         if (!strncmp(value, "srcline", strlen(value))) {
 100                 callchain_param.key = CCKEY_SRCLINE;
 101                 return 0;
 102         }
 103         if (!strncmp(value, "branch", strlen(value))) {
 104                 callchain_param.branch_callstack = 1;
 105                 return 0;
 106         }
 107
 108         pr_err("Invalid callchain sort key: %s\n", value);
 109         return -1;
 110 }
 111
 112 static int parse_callchain_value(const char *value)
 113 {
 114         if (!strncmp(value, "percent", strlen(value))) {
 115                 callchain_param.value = CCVAL_PERCENT;
 116                 return 0;
 117         }
 118         if (!strncmp(value, "period", strlen(value))) {
 119                 callchain_param.value = CCVAL_PERIOD;
 120                 return 0;
 121         }
 122         if (!strncmp(value, "count", strlen(value))) {
 123                 callchain_param.value = CCVAL_COUNT;
 124                 return 0;
 125         }
 126
 127         pr_err("Invalid callchain config key: %s\n", value);
 128         return -1;
 129 }
 130
 131 static int get_stack_size(const char *str, unsigned long *_size)
 132 {
 133         char *endptr;
 134         unsigned long size;
 135         unsigned long max_size = round_down(USHRT_MAX, sizeof(u64));
 136
 137         size = strtoul(str, &endptr, 0);
 138
 139         do {
 140                 if (*endptr)
 141                         break;
 142
 143                 size = round_up(size, sizeof(u64));
 144                 if (!size || size > max_size)
 145                         break;
 146
 147                 *_size = size;
 148                 return 0;
 149
 150         } while (0);
 151
 152         pr_err("callchain: Incorrect stack dump size (max %ld): %s\n",
 153                max_size, str);
 154         return -1;
 155 }
 156
 157 static int
 158 __parse_callchain_report_opt(const char *arg, bool allow_record_opt)
 159 {
 160         char *tok;
 161         char *endptr, *saveptr = NULL;
 162         bool minpcnt_set = false;
 163         bool record_opt_set = false;
 164         bool try_stack_size = false;
 165
 166         callchain_param.enabled = true;
 167         symbol_conf.use_callchain = true;
 168
 169         if (!arg)
 170                 return 0;
 171
 172         while ((tok = strtok_r((char *)arg, ",", &saveptr)) != NULL) {
 173                 if (!strncmp(tok, "none", strlen(tok))) {
 174                         callchain_param.mode = CHAIN_NONE;
 175                         callchain_param.enabled = false;
 176                         symbol_conf.use_callchain = false;
 177                         return 0;
 178                 }
 179
 180                 if (!parse_callchain_mode(tok) ||
 181                     !parse_callchain_order(tok) ||
 182                     !parse_callchain_sort_key(tok) ||
 183                     !parse_callchain_value(tok)) {
 184                         /* parsing ok - move on to the next */
 185                         try_stack_size = false;
 186                         goto next;
 187                 } else if (allow_record_opt && !record_opt_set) {
 188                         if (parse_callchain_record(tok, &callchain_param))
 189                                 goto try_numbers;
 190
 191                         /* assume that number followed by 'dwarf' is stack size */
 192                         if (callchain_param.record_mode == CALLCHAIN_DWARF)
 193                                 try_stack_size = true;
 194
 195                         record_opt_set = true;
 196                         goto next;
 197                 }
 198
 199 try_numbers:
 200                 if (try_stack_size) {
 201                         unsigned long size = 0;
 202
 203                         if (get_stack_size(tok, &size) < 0)
 204                                 return -1;
 205                         callchain_param.dump_size = size;
 206                         try_stack_size = false;
 207                 } else if (!minpcnt_set) {
 208                         /* try to get the min percent */
 209                         callchain_param.min_percent = strtod(tok, &endptr);
 210                         if (tok == endptr)
 211                                 return -1;
 212                         minpcnt_set = true;
 213                 } else {
 214                         /* try print limit at last */
 215                         callchain_param.print_limit = strtoul(tok, &endptr, 0);
 216                         if (tok == endptr)
 217                                 return -1;
 218                 }
 219 next:
 220                 arg = NULL;
 221         }
 222
 223         if (callchain_register_param(&callchain_param) < 0) {
 224                 pr_err("Can't register callchain params\n");
 225                 return -1;
 226         }
 227         return 0;
 228 }
 229
 230 int parse_callchain_report_opt(const char *arg)
 231 {
 232         return __parse_callchain_report_opt(arg, false);
 233 }
 234
 235 int parse_callchain_top_opt(const char *arg)
 236 {
 237         return __parse_callchain_report_opt(arg, true);
 238 }
 239
 240 int parse_callchain_record(const char *arg, struct callchain_param *param)
 241 {
 242         char *tok, *name, *saveptr = NULL;
 243         char *buf;
 244         int ret = -1;
 245
 246         /* We need buffer that we know we can write to. */
 247         buf = malloc(strlen(arg) + 1);
 248         if (!buf)
 249                 return -ENOMEM;
 250
 251         strcpy(buf, arg);
 252
 253         tok = strtok_r((char *)buf, ",", &saveptr);
 254         name = tok ? : (char *)buf;
 255
 256         do {
 257                 /* Framepointer style */
 258                 if (!strncmp(name, "fp", sizeof("fp"))) {
 259                         if (!strtok_r(NULL, ",", &saveptr)) {
 260                                 param->record_mode = CALLCHAIN_FP;
 261                                 ret = 0;
 262                         } else
 263                                 pr_err("callchain: No more arguments "
 264                                        "needed for --call-graph fp\n");
 265                         break;
 266
 267                 /* Dwarf style */
 268                 } else if (!strncmp(name, "dwarf", sizeof("dwarf"))) {
 269                         const unsigned long default_stack_dump_size = 8192;
 270
 271                         ret = 0;
 272                         param->record_mode = CALLCHAIN_DWARF;
 273                         param->dump_size = default_stack_dump_size;
 274
 275                         tok = strtok_r(NULL, ",", &saveptr);
 276                         if (tok) {
 277                                 unsigned long size = 0;
 278
 279                                 ret = get_stack_size(tok, &size);
 280                                 param->dump_size = size;
 281                         }
 282                 } else if (!strncmp(name, "lbr", sizeof("lbr"))) {
 283                         if (!strtok_r(NULL, ",", &saveptr)) {
 284                                 param->record_mode = CALLCHAIN_LBR;
 285                                 ret = 0;
 286                         } else
 287                                 pr_err("callchain: No more arguments "
 288                                         "needed for --call-graph lbr\n");
 289                         break;
 290                 } else {
 291                         pr_err("callchain: Unknown --call-graph option "
 292                                "value: %s\n", arg);
 293                         break;
 294                 }
 295
 296         } while (0);
 297
 298         free(buf);
 299         return ret;
 300 }
 301
 302 int perf_callchain_config(const char *var, const char *value)
 303 {
 304         char *endptr;
 305
 306         if (prefixcmp(var, "call-graph."))
 307                 return 0;
 308         var += sizeof("call-graph.") - 1;
 309
 310         if (!strcmp(var, "record-mode"))
 311                 return parse_callchain_record_opt(value, &callchain_param);
 312         if (!strcmp(var, "dump-size")) {
 313                 unsigned long size = 0;
 314                 int ret;
 315
 316                 ret = get_stack_size(value, &size);
 317                 callchain_param.dump_size = size;
 318
 319                 return ret;
 320         }
 321         if (!strcmp(var, "print-type"))
 322                 return parse_callchain_mode(value);
 323         if (!strcmp(var, "order"))
 324                 return parse_callchain_order(value);
 325         if (!strcmp(var, "sort-key"))
 326                 return parse_callchain_sort_key(value);
 327         if (!strcmp(var, "threshold")) {
 328                 callchain_param.min_percent = strtod(value, &endptr);
 329                 if (value == endptr) {
 330                         pr_err("Invalid callchain threshold: %s\n", value);
 331                         return -1;
 332                 }
 333         }
 334         if (!strcmp(var, "print-limit")) {
 335                 callchain_param.print_limit = strtod(value, &endptr);
 336                 if (value == endptr) {
 337                         pr_err("Invalid callchain print limit: %s\n", value);
 338                         return -1;
 339                 }
 340         }
 341
 342         return 0;
 343 }
 344
 345 static void
 346 rb_insert_callchain(struct rb_root *root, struct callchain_node *chain,
 347                     enum chain_mode mode)
 348 {
 349         struct rb_node **p = &root->rb_node;
 350         struct rb_node *parent = NULL;
 351         struct callchain_node *rnode;
 352         u64 chain_cumul = callchain_cumul_hits(chain);
 353
 354         while (*p) {
 355                 u64 rnode_cumul;
 356
 357                 parent = *p;
 358                 rnode = rb_entry(parent, struct callchain_node, rb_node);
 359                 rnode_cumul = callchain_cumul_hits(rnode);
 360
 361                 switch (mode) {
 362                 case CHAIN_FLAT:
 363                 case CHAIN_FOLDED:
 364                         if (rnode->hit < chain->hit)
 365                                 p = &(*p)->rb_left;
 366                         else
 367                                 p = &(*p)->rb_right;
 368                         break;
 369                 case CHAIN_GRAPH_ABS: /* Falldown */
 370                 case CHAIN_GRAPH_REL:
 371                         if (rnode_cumul < chain_cumul)
 372                                 p = &(*p)->rb_left;
 373                         else
 374                                 p = &(*p)->rb_right;
 375                         break;
 376                 case CHAIN_NONE:
 377                 default:
 378                         break;
 379                 }
 380         }
 381
 382         rb_link_node(&chain->rb_node, parent, p);
 383         rb_insert_color(&chain->rb_node, root);
 384 }
 385
 386 static void
 387 __sort_chain_flat(struct rb_root *rb_root, struct callchain_node *node,
 388                   u64 min_hit)
 389 {
 390         struct rb_node *n;
 391         struct callchain_node *child;
 392
 393         n = rb_first(&node->rb_root_in);
 394         while (n) {
 395                 child = rb_entry(n, struct callchain_node, rb_node_in);
 396                 n = rb_next(n);
 397
 398                 __sort_chain_flat(rb_root, child, min_hit);
 399         }
 400
 401         if (node->hit && node->hit >= min_hit)
 402                 rb_insert_callchain(rb_root, node, CHAIN_FLAT);
 403 }
 404
 405 /*
 406  * Once we get every callchains from the stream, we can now
 407  * sort them by hit
 408  */
 409 static void
 410 sort_chain_flat(struct rb_root *rb_root, struct callchain_root *root,
 411                 u64 min_hit, struct callchain_param *param __maybe_unused)
 412 {
 413         *rb_root = RB_ROOT;
 414         __sort_chain_flat(rb_root, &root->node, min_hit);
 415 }
 416
 417 static void __sort_chain_graph_abs(struct callchain_node *node,
 418                                    u64 min_hit)
 419 {
 420         struct rb_node *n;
 421         struct callchain_node *child;
 422
 423         node->rb_root = RB_ROOT;
 424         n = rb_first(&node->rb_root_in);
 425
 426         while (n) {
 427                 child = rb_entry(n, struct callchain_node, rb_node_in);
 428                 n = rb_next(n);
 429
 430                 __sort_chain_graph_abs(child, min_hit);
 431                 if (callchain_cumul_hits(child) >= min_hit)
 432                         rb_insert_callchain(&node->rb_root, child,
 433                                             CHAIN_GRAPH_ABS);
 434         }
 435 }
 436
 437 static void
 438 sort_chain_graph_abs(struct rb_root *rb_root, struct callchain_root *chain_root,
 439                      u64 min_hit, struct callchain_param *param __maybe_unused)
 440 {
 441         __sort_chain_graph_abs(&chain_root->node, min_hit);
 442         rb_root->rb_node = chain_root->node.rb_root.rb_node;
 443 }
 444
 445 static void __sort_chain_graph_rel(struct callchain_node *node,
 446                                    double min_percent)
 447 {
 448         struct rb_node *n;
 449         struct callchain_node *child;
 450         u64 min_hit;
 451
 452         node->rb_root = RB_ROOT;
 453         min_hit = ceil(node->children_hit * min_percent);
 454
 455         n = rb_first(&node->rb_root_in);
 456         while (n) {
 457                 child = rb_entry(n, struct callchain_node, rb_node_in);
 458                 n = rb_next(n);
 459
 460                 __sort_chain_graph_rel(child, min_percent);
 461                 if (callchain_cumul_hits(child) >= min_hit)
 462                         rb_insert_callchain(&node->rb_root, child,
 463                                             CHAIN_GRAPH_REL);
 464         }
 465 }
 466
 467 static void
 468 sort_chain_graph_rel(struct rb_root *rb_root, struct callchain_root *chain_root,
 469                      u64 min_hit __maybe_unused, struct callchain_param *param)
 470 {
 471         __sort_chain_graph_rel(&chain_root->node, param->min_percent / 100.0);
 472         rb_root->rb_node = chain_root->node.rb_root.rb_node;
 473 }
 474
 475 int callchain_register_param(struct callchain_param *param)
 476 {
 477         switch (param->mode) {
 478         case CHAIN_GRAPH_ABS:
 479                 param->sort = sort_chain_graph_abs;
 480                 break;
 481         case CHAIN_GRAPH_REL:
 482                 param->sort = sort_chain_graph_rel;
 483                 break;
 484         case CHAIN_FLAT:
 485         case CHAIN_FOLDED:
 486                 param->sort = sort_chain_flat;
 487                 break;
 488         case CHAIN_NONE:
 489         default:
 490                 return -1;
 491         }
 492         return 0;
 493 }
 494
 495 /*
 496  * Create a child for a parent. If inherit_children, then the new child
 497  * will become the new parent of it's parent children
 498  */
 499 static struct callchain_node *
 500 create_child(struct callchain_node *parent, bool inherit_children)
 501 {
 502         struct callchain_node *new;
 503
 504         new = zalloc(sizeof(*new));
 505         if (!new) {
 506                 perror("not enough memory to create child for code path tree");
 507                 return NULL;
 508         }
 509         new->parent = parent;
 510         INIT_LIST_HEAD(&new->val);
 511         INIT_LIST_HEAD(&new->parent_val);
 512
 513         if (inherit_children) {
 514                 struct rb_node *n;
 515                 struct callchain_node *child;
 516
 517                 new->rb_root_in = parent->rb_root_in;
 518                 parent->rb_root_in = RB_ROOT;
 519
 520                 n = rb_first(&new->rb_root_in);
 521                 while (n) {
 522                         child = rb_entry(n, struct callchain_node, rb_node_in);
 523                         child->parent = new;
 524                         n = rb_next(n);
 525                 }
 526
 527                 /* make it the first child */
 528                 rb_link_node(&new->rb_node_in, NULL, &parent->rb_root_in.rb_node);
 529                 rb_insert_color(&new->rb_node_in, &parent->rb_root_in);
 530         }
 531
 532         return new;
 533 }
 534
 535
 536 /*
 537  * Fill the node with callchain values
 538  */
 539 static int
 540 fill_node(struct callchain_node *node, struct callchain_cursor *cursor)
 541 {
 542         struct callchain_cursor_node *cursor_node;
 543
 544         node->val_nr = cursor->nr - cursor->pos;
 545         if (!node->val_nr)
 546                 pr_warning("Warning: empty node in callchain tree\n");
 547
 548         cursor_node = callchain_cursor_current(cursor);
 549
 550         while (cursor_node) {
 551                 struct callchain_list *call;
 552
 553                 call = zalloc(sizeof(*call));
 554                 if (!call) {
 555                         perror("not enough memory for the code path tree");
 556                         return -1;
 557                 }
 558                 call->ip = cursor_node->ip;
 559                 call->ms.sym = cursor_node->sym;
 560                 call->ms.map = map__get(cursor_node->map);
 561
 562                 if (cursor_node->branch) {
 563                         call->branch_count = 1;
 564
 565                         if (cursor_node->branch_flags.predicted)
 566                                 call->predicted_count = 1;
 567
 568                         if (cursor_node->branch_flags.abort)
 569                                 call->abort_count = 1;
 570
 571                         call->cycles_count = cursor_node->branch_flags.cycles;
 572                         call->iter_count = cursor_node->nr_loop_iter;
 573                         call->samples_count = cursor_node->samples;
 574                 }
 575
 576                 list_add_tail(&call->list, &node->val);
 577
 578                 callchain_cursor_advance(cursor);
 579                 cursor_node = callchain_cursor_current(cursor);
 580         }
 581         return 0;
 582 }
 583
 584 static struct callchain_node *
 585 add_child(struct callchain_node *parent,
 586           struct callchain_cursor *cursor,
 587           u64 period)
 588 {
 589         struct callchain_node *new;
 590
 591         new = create_child(parent, false);
 592         if (new == NULL)
 593                 return NULL;
 594
 595         if (fill_node(new, cursor) < 0) {
 596                 struct callchain_list *call, *tmp;
 597
 598                 list_for_each_entry_safe(call, tmp, &new->val, list) {
 599                         list_del(&call->list);
 600                         map__zput(call->ms.map);
 601                         free(call);
 602                 }
 603                 free(new);
 604                 return NULL;
 605         }
 606
 607         new->children_hit = 0;
 608         new->hit = period;
 609         new->children_count = 0;
 610         new->count = 1;
 611         return new;
 612 }
 613
 614 enum match_result {
 615         MATCH_ERROR  = -1,
 616         MATCH_EQ,
 617         MATCH_LT,
 618         MATCH_GT,
 619 };
 620
 621 static enum match_result match_chain_srcline(struct callchain_cursor_node *node,
 622                                              struct callchain_list *cnode)
 623 {
 624         char *left = NULL;
 625         char *right = NULL;
 626         enum match_result ret = MATCH_EQ;
 627         int cmp;
 628
 629         if (cnode->ms.map)
 630                 left = get_srcline(cnode->ms.map->dso,
 631                                  map__rip_2objdump(cnode->ms.map, cnode->ip),
 632                                  cnode->ms.sym, true, false);
 633         if (node->map)
 634                 right = get_srcline(node->map->dso,
 635                                   map__rip_2objdump(node->map, node->ip),
 636                                   node->sym, true, false);
 637
 638         if (left && right)
 639                 cmp = strcmp(left, right);
 640         else if (!left && right)
 641                 cmp = 1;
 642         else if (left && !right)
 643                 cmp = -1;
 644         else if (cnode->ip == node->ip)
 645                 cmp = 0;
 646         else
 647                 cmp = (cnode->ip < node->ip) ? -1 : 1;
 648
 649         if (cmp != 0)
 650                 ret = cmp < 0 ? MATCH_LT : MATCH_GT;
 651
 652         free_srcline(left);
 653         free_srcline(right);
 654         return ret;
 655 }
 656
 657 static enum match_result match_chain(struct callchain_cursor_node *node,
 658                                      struct callchain_list *cnode)
 659 {
 660         struct symbol *sym = node->sym;
 661         u64 left, right;
 662
 663         if (callchain_param.key == CCKEY_SRCLINE) {
 664                 enum match_result match = match_chain_srcline(node, cnode);
 665
 666                 if (match != MATCH_ERROR)
 667                         return match;
 668         }
 669
 670         if (cnode->ms.sym && sym && callchain_param.key == CCKEY_FUNCTION) {
 671                 left = cnode->ms.sym->start;
 672                 right = sym->start;
 673         } else {
 674                 left = cnode->ip;
 675                 right = node->ip;
 676         }
 677
 678         if (left == right) {
 679                 if (node->branch) {
 680                         cnode->branch_count++;
 681
 682                         if (node->branch_flags.predicted)
 683                                 cnode->predicted_count++;
 684
 685                         if (node->branch_flags.abort)
 686                                 cnode->abort_count++;
 687
 688                         cnode->cycles_count += node->branch_flags.cycles;
 689                         cnode->iter_count += node->nr_loop_iter;
 690                         cnode->samples_count += node->samples;
 691                 }
 692
 693                 return MATCH_EQ;
 694         }
 695
 696         return left > right ? MATCH_GT : MATCH_LT;
 697 }
 698
 699 /*
 700  * Split the parent in two parts (a new child is created) and
 701  * give a part of its callchain to the created child.
 702  * Then create another child to host the given callchain of new branch
 703  */
 704 static int
 705 split_add_child(struct callchain_node *parent,
 706                 struct callchain_cursor *cursor,
 707                 struct callchain_list *to_split,
 708                 u64 idx_parents, u64 idx_local, u64 period)
 709 {
 710         struct callchain_node *new;
 711         struct list_head *old_tail;
 712         unsigned int idx_total = idx_parents + idx_local;
 713
 714         /* split */
 715         new = create_child(parent, true);
 716         if (new == NULL)
 717                 return -1;
 718
 719         /* split the callchain and move a part to the new child */
 720         old_tail = parent->val.prev;
 721         list_del_range(&to_split->list, old_tail);
 722         new->val.next = &to_split->list;
 723         new->val.prev = old_tail;
 724         to_split->list.prev = &new->val;
 725         old_tail->next = &new->val;
 726
 727         /* split the hits */
 728         new->hit = parent->hit;
 729         new->children_hit = parent->children_hit;
 730         parent->children_hit = callchain_cumul_hits(new);
 731         new->val_nr = parent->val_nr - idx_local;
 732         parent->val_nr = idx_local;
 733         new->count = parent->count;
 734         new->children_count = parent->children_count;
 735         parent->children_count = callchain_cumul_counts(new);
 736
 737         /* create a new child for the new branch if any */
 738         if (idx_total < cursor->nr) {
 739                 struct callchain_node *first;
 740                 struct callchain_list *cnode;
 741                 struct callchain_cursor_node *node;
 742                 struct rb_node *p, **pp;
 743
 744                 parent->hit = 0;
 745                 parent->children_hit += period;
 746                 parent->count = 0;
 747                 parent->children_count += 1;
 748
 749                 node = callchain_cursor_current(cursor);
 750                 new = add_child(parent, cursor, period);
 751                 if (new == NULL)
 752                         return -1;
 753
 754                 /*
 755                  * This is second child since we moved parent's children
 756                  * to new (first) child above.
 757                  */
 758                 p = parent->rb_root_in.rb_node;
 759                 first = rb_entry(p, struct callchain_node, rb_node_in);
 760                 cnode = list_first_entry(&first->val, struct callchain_list,
 761                                          list);
 762
 763                 if (match_chain(node, cnode) == MATCH_LT)
 764                         pp = &p->rb_left;
 765                 else
 766                         pp = &p->rb_right;
 767
 768                 rb_link_node(&new->rb_node_in, p, pp);
 769                 rb_insert_color(&new->rb_node_in, &parent->rb_root_in);
 770         } else {
 771                 parent->hit = period;
 772                 parent->count = 1;
 773         }
 774         return 0;
 775 }
 776
 777 static enum match_result
 778 append_chain(struct callchain_node *root,
 779              struct callchain_cursor *cursor,
 780              u64 period);
 781
 782 static int
 783 append_chain_children(struct callchain_node *root,
 784                       struct callchain_cursor *cursor,
 785                       u64 period)
 786 {
 787         struct callchain_node *rnode;
 788         struct callchain_cursor_node *node;
 789         struct rb_node **p = &root->rb_root_in.rb_node;
 790         struct rb_node *parent = NULL;
 791
 792         node = callchain_cursor_current(cursor);
 793         if (!node)
 794                 return -1;
 795
 796         /* lookup in childrens */
 797         while (*p) {
 798                 enum match_result ret;
 799
 800                 parent = *p;
 801                 rnode = rb_entry(parent, struct callchain_node, rb_node_in);
 802
 803                 /* If at least first entry matches, rely to children */
 804                 ret = append_chain(rnode, cursor, period);
 805                 if (ret == MATCH_EQ)
 806                         goto inc_children_hit;
 807                 if (ret == MATCH_ERROR)
 808                         return -1;
 809
 810                 if (ret == MATCH_LT)
 811                         p = &parent->rb_left;
 812                 else
 813                         p = &parent->rb_right;
 814         }
 815         /* nothing in children, add to the current node */
 816         rnode = add_child(root, cursor, period);
 817         if (rnode == NULL)
 818                 return -1;
 819
 820         rb_link_node(&rnode->rb_node_in, parent, p);
 821         rb_insert_color(&rnode->rb_node_in, &root->rb_root_in);
 822
 823 inc_children_hit:
 824         root->children_hit += period;
 825         root->children_count++;
 826         return 0;
 827 }
 828
 829 static enum match_result
 830 append_chain(struct callchain_node *root,
 831              struct callchain_cursor *cursor,
 832              u64 period)
 833 {
 834         struct callchain_list *cnode;
 835         u64 start = cursor->pos;
 836         bool found = false;
 837         u64 matches;
 838         enum match_result cmp = MATCH_ERROR;
 839
 840         /*
 841          * Lookup in the current node
 842          * If we have a symbol, then compare the start to match
 843          * anywhere inside a function, unless function
 844          * mode is disabled.
 845          */
 846         list_for_each_entry(cnode, &root->val, list) {
 847                 struct callchain_cursor_node *node;
 848
 849                 node = callchain_cursor_current(cursor);
 850                 if (!node)
 851                         break;
 852
 853                 cmp = match_chain(node, cnode);
 854                 if (cmp != MATCH_EQ)
 855                         break;
 856
 857                 found = true;
 858
 859                 callchain_cursor_advance(cursor);
 860         }
 861
 862         /* matches not, relay no the parent */
 863         if (!found) {
 864                 WARN_ONCE(cmp == MATCH_ERROR, "Chain comparison error\n");
 865                 return cmp;
 866         }
 867
 868         matches = cursor->pos - start;
 869
 870         /* we match only a part of the node. Split it and add the new chain */
 871         if (matches < root->val_nr) {
 872                 if (split_add_child(root, cursor, cnode, start, matches,
 873                                     period) < 0)
 874                         return MATCH_ERROR;
 875
 876                 return MATCH_EQ;
 877         }
 878
 879         /* we match 100% of the path, increment the hit */
 880         if (matches == root->val_nr && cursor->pos == cursor->nr) {
 881                 root->hit += period;
 882                 root->count++;
 883                 return MATCH_EQ;
 884         }
 885
 886         /* We match the node and still have a part remaining */
 887         if (append_chain_children(root, cursor, period) < 0)
 888                 return MATCH_ERROR;
 889
 890         return MATCH_EQ;
 891 }
 892
 893 int callchain_append(struct callchain_root *root,
 894                      struct callchain_cursor *cursor,
 895                      u64 period)
 896 {
 897         if (!cursor->nr)
 898                 return 0;
 899
 900         callchain_cursor_commit(cursor);
 901
 902         if (append_chain_children(&root->node, cursor, period) < 0)
 903                 return -1;
 904
 905         if (cursor->nr > root->max_depth)
 906                 root->max_depth = cursor->nr;
 907
 908         return 0;
 909 }
 910
 911 static int
 912 merge_chain_branch(struct callchain_cursor *cursor,
 913                    struct callchain_node *dst, struct callchain_node *src)
 914 {
 915         struct callchain_cursor_node **old_last = cursor->last;
 916         struct callchain_node *child;
 917         struct callchain_list *list, *next_list;
 918         struct rb_node *n;
 919         int old_pos = cursor->nr;
 920         int err = 0;
 921
 922         list_for_each_entry_safe(list, next_list, &src->val, list) {
 923                 callchain_cursor_append(cursor, list->ip,
 924                                         list->ms.map, list->ms.sym,
 925                                         false, NULL, 0, 0);
 926                 list_del(&list->list);
 927                 map__zput(list->ms.map);
 928                 free(list);
 929         }
 930
 931         if (src->hit) {
 932                 callchain_cursor_commit(cursor);
 933                 if (append_chain_children(dst, cursor, src->hit) < 0)
 934                         return -1;
 935         }
 936
 937         n = rb_first(&src->rb_root_in);
 938         while (n) {
 939                 child = container_of(n, struct callchain_node, rb_node_in);
 940                 n = rb_next(n);
 941                 rb_erase(&child->rb_node_in, &src->rb_root_in);
 942
 943                 err = merge_chain_branch(cursor, dst, child);
 944                 if (err)
 945                         break;
 946
 947                 free(child);
 948         }
 949
 950         cursor->nr = old_pos;
 951         cursor->last = old_last;
 952
 953         return err;
 954 }
 955
 956 int callchain_merge(struct callchain_cursor *cursor,
 957                     struct callchain_root *dst, struct callchain_root *src)
 958 {
 959         return merge_chain_branch(cursor, &dst->node, &src->node);
 960 }
 961
 962 int callchain_cursor_append(struct callchain_cursor *cursor,
 963                             u64 ip, struct map *map, struct symbol *sym,
 964                             bool branch, struct branch_flags *flags,
 965                             int nr_loop_iter, int samples)
 966 {
 967         struct callchain_cursor_node *node = *cursor->last;
 968
 969         if (!node) {
 970                 node = calloc(1, sizeof(*node));
 971                 if (!node)
 972                         return -ENOMEM;
 973
 974                 *cursor->last = node;
 975         }
 976
 977         node->ip = ip;
 978         map__zput(node->map);
 979         node->map = map__get(map);
 980         node->sym = sym;
 981         node->branch = branch;
 982         node->nr_loop_iter = nr_loop_iter;
 983         node->samples = samples;
 984
 985         if (flags)
 986                 memcpy(&node->branch_flags, flags,
 987                         sizeof(struct branch_flags));
 988
 989         cursor->nr++;
 990
 991         cursor->last = &node->next;
 992
 993         return 0;
 994 }
 995
 996 int sample__resolve_callchain(struct perf_sample *sample,
 997                               struct callchain_cursor *cursor, struct symbol **parent,
 998                               struct perf_evsel *evsel, struct addr_location *al,
 999                               int max_stack)
1000 {
1001         if (sample->callchain == NULL)
1002                 return 0;
1003
1004         if (symbol_conf.use_callchain || symbol_conf.cumulate_callchain ||
1005             perf_hpp_list.parent) {
1006                 return thread__resolve_callchain(al->thread, cursor, evsel, sample,
1007                                                  parent, al, max_stack);
1008         }
1009         return 0;
1010 }
1011
1012 int hist_entry__append_callchain(struct hist_entry *he, struct perf_sample *sample)
1013 {
1014         if (!symbol_conf.use_callchain || sample->callchain == NULL)
1015                 return 0;
1016         return callchain_append(he->callchain, &callchain_cursor, sample->period);
1017 }
1018
1019 int fill_callchain_info(struct addr_location *al, struct callchain_cursor_node *node,
1020                         bool hide_unresolved)
1021 {
1022         al->map = node->map;
1023         al->sym = node->sym;
1024         if (node->map)
1025                 al->addr = node->map->map_ip(node->map, node->ip);
1026         else
1027                 al->addr = node->ip;
1028
1029         if (al->sym == NULL) {
1030                 if (hide_unresolved)
1031                         return 0;
1032                 if (al->map == NULL)
1033                         goto out;
1034         }
1035
1036         if (al->map->groups == &al->machine->kmaps) {
1037                 if (machine__is_host(al->machine)) {
1038                         al->cpumode = PERF_RECORD_MISC_KERNEL;
1039                         al->level = 'k';
1040                 } else {
1041                         al->cpumode = PERF_RECORD_MISC_GUEST_KERNEL;
1042                         al->level = 'g';
1043                 }
1044         } else {
1045                 if (machine__is_host(al->machine)) {
1046                         al->cpumode = PERF_RECORD_MISC_USER;
1047                         al->level = '.';
1048                 } else if (perf_guest) {
1049                         al->cpumode = PERF_RECORD_MISC_GUEST_USER;
1050                         al->level = 'u';
1051                 } else {
1052                         al->cpumode = PERF_RECORD_MISC_HYPERVISOR;
1053                         al->level = 'H';
1054                 }
1055         }
1056
1057 out:
1058         return 1;
1059 }
1060
1061 char *callchain_list__sym_name(struct callchain_list *cl,
1062                                char *bf, size_t bfsize, bool show_dso)
1063 {
1064         bool show_addr = callchain_param.key == CCKEY_ADDRESS;
1065         bool show_srcline = show_addr || callchain_param.key == CCKEY_SRCLINE;
1066         int printed;
1067
1068         if (cl->ms.sym) {
1069                 if (show_srcline && cl->ms.map && !cl->srcline)
1070                         cl->srcline = get_srcline(cl->ms.map->dso,
1071                                                   map__rip_2objdump(cl->ms.map,
1072                                                                     cl->ip),
1073                                                   cl->ms.sym, false, show_addr);
1074                 if (cl->srcline)
1075                         printed = scnprintf(bf, bfsize, "%s %s",
1076                                         cl->ms.sym->name, cl->srcline);
1077                 else
1078                         printed = scnprintf(bf, bfsize, "%s", cl->ms.sym->name);
1079         } else
1080                 printed = scnprintf(bf, bfsize, "%#" PRIx64, cl->ip);
1081
1082         if (show_dso)
1083                 scnprintf(bf + printed, bfsize - printed, " %s",
1084                           cl->ms.map ?
1085                           cl->ms.map->dso->short_name :
1086                           "unknown");
1087
1088         return bf;
1089 }
1090
1091 char *callchain_node__scnprintf_value(struct callchain_node *node,
1092                                       char *bf, size_t bfsize, u64 total)
1093 {
1094         double percent = 0.0;
1095         u64 period = callchain_cumul_hits(node);
1096         unsigned count = callchain_cumul_counts(node);
1097
1098         if (callchain_param.mode == CHAIN_FOLDED) {
1099                 period = node->hit;
1100                 count = node->count;
1101         }
1102
1103         switch (callchain_param.value) {
1104         case CCVAL_PERIOD:
1105                 scnprintf(bf, bfsize, "%"PRIu64, period);
1106                 break;
1107         case CCVAL_COUNT:
1108                 scnprintf(bf, bfsize, "%u", count);
1109                 break;
1110         case CCVAL_PERCENT:
1111         default:
1112                 if (total)
1113                         percent = period * 100.0 / total;
1114                 scnprintf(bf, bfsize, "%.2f%%", percent);
1115                 break;
1116         }
1117         return bf;
1118 }
1119
1120 int callchain_node__fprintf_value(struct callchain_node *node,
1121                                  FILE *fp, u64 total)
1122 {
1123         double percent = 0.0;
1124         u64 period = callchain_cumul_hits(node);
1125         unsigned count = callchain_cumul_counts(node);
1126
1127         if (callchain_param.mode == CHAIN_FOLDED) {
1128                 period = node->hit;
1129                 count = node->count;
1130         }
1131
1132         switch (callchain_param.value) {
1133         case CCVAL_PERIOD:
1134                 return fprintf(fp, "%"PRIu64, period);
1135         case CCVAL_COUNT:
1136                 return fprintf(fp, "%u", count);
1137         case CCVAL_PERCENT:
1138         default:
1139                 if (total)
1140                         percent = period * 100.0 / total;
1141                 return percent_color_fprintf(fp, "%.2f%%", percent);
1142         }
1143         return 0;
1144 }
1145
1146 static void callchain_counts_value(struct callchain_node *node,
1147                                    u64 *branch_count, u64 *predicted_count,
1148                                    u64 *abort_count, u64 *cycles_count)
1149 {
1150         struct callchain_list *clist;
1151
1152         list_for_each_entry(clist, &node->val, list) {
1153                 if (branch_count)
1154                         *branch_count += clist->branch_count;
1155
1156                 if (predicted_count)
1157                         *predicted_count += clist->predicted_count;
1158
1159                 if (abort_count)
1160                         *abort_count += clist->abort_count;
1161
1162                 if (cycles_count)
1163                         *cycles_count += clist->cycles_count;
1164         }
1165 }
1166
1167 static int callchain_node_branch_counts_cumul(struct callchain_node *node,
1168                                               u64 *branch_count,
1169                                               u64 *predicted_count,
1170                                               u64 *abort_count,
1171                                               u64 *cycles_count)
1172 {
1173         struct callchain_node *child;
1174         struct rb_node *n;
1175
1176         n = rb_first(&node->rb_root_in);
1177         while (n) {
1178                 child = rb_entry(n, struct callchain_node, rb_node_in);
1179                 n = rb_next(n);
1180
1181                 callchain_node_branch_counts_cumul(child, branch_count,
1182                                                    predicted_count,
1183                                                    abort_count,
1184                                                    cycles_count);
1185
1186                 callchain_counts_value(child, branch_count,
1187                                        predicted_count, abort_count,
1188                                        cycles_count);
1189         }
1190
1191         return 0;
1192 }
1193
1194 int callchain_branch_counts(struct callchain_root *root,
1195                             u64 *branch_count, u64 *predicted_count,
1196                             u64 *abort_count, u64 *cycles_count)
1197 {
1198         if (branch_count)
1199                 *branch_count = 0;
1200
1201         if (predicted_count)
1202                 *predicted_count = 0;
1203
1204         if (abort_count)
1205                 *abort_count = 0;
1206
1207         if (cycles_count)
1208                 *cycles_count = 0;
1209
1210         return callchain_node_branch_counts_cumul(&root->node,
1211                                                   branch_count,
1212                                                   predicted_count,
1213                                                   abort_count,
1214                                                   cycles_count);
1215 }
1216
1217 static int counts_str_build(char *bf, int bfsize,
1218                              u64 branch_count, u64 predicted_count,
1219                              u64 abort_count, u64 cycles_count,
1220                              u64 iter_count, u64 samples_count)
1221 {
1222         double predicted_percent = 0.0;
1223         const char *null_str = "";
1224         char iter_str[32];
1225         char cycle_str[32];
1226         char *istr, *cstr;
1227         u64 cycles;
1228
1229         if (branch_count == 0)
1230                 return scnprintf(bf, bfsize, " (calltrace)");
1231
1232         cycles = cycles_count / branch_count;
1233
1234         if (iter_count && samples_count) {
1235                 if (cycles > 0)
1236                         scnprintf(iter_str, sizeof(iter_str),
1237                                  " iterations:%" PRId64 "",
1238                                  iter_count / samples_count);
1239                 else
1240                         scnprintf(iter_str, sizeof(iter_str),
1241                                  "iterations:%" PRId64 "",
1242                                  iter_count / samples_count);
1243                 istr = iter_str;
1244         } else
1245                 istr = (char *)null_str;
1246
1247         if (cycles > 0) {
1248                 scnprintf(cycle_str, sizeof(cycle_str),
1249                           "cycles:%" PRId64 "", cycles);
1250                 cstr = cycle_str;
1251         } else
1252                 cstr = (char *)null_str;
1253
1254         predicted_percent = predicted_count * 100.0 / branch_count;
1255
1256         if ((predicted_count == branch_count) && (abort_count == 0)) {
1257                 if ((cycles > 0) || (istr != (char *)null_str))
1258                         return scnprintf(bf, bfsize, " (%s%s)", cstr, istr);
1259                 else
1260                         return scnprintf(bf, bfsize, "%s", (char *)null_str);
1261         }
1262
1263         if ((predicted_count < branch_count) && (abort_count == 0)) {
1264                 if ((cycles > 0) || (istr != (char *)null_str))
1265                         return scnprintf(bf, bfsize,
1266                                 " (predicted:%.1f%% %s%s)",
1267                                 predicted_percent, cstr, istr);
1268                 else {
1269                         return scnprintf(bf, bfsize,
1270                                 " (predicted:%.1f%%)",
1271                                 predicted_percent);
1272                 }
1273         }
1274
1275         if ((predicted_count == branch_count) && (abort_count > 0)) {
1276                 if ((cycles > 0) || (istr != (char *)null_str))
1277                         return scnprintf(bf, bfsize,
1278                                 " (abort:%" PRId64 " %s%s)",
1279                                 abort_count, cstr, istr);
1280                 else
1281                         return scnprintf(bf, bfsize,
1282                                 " (abort:%" PRId64 ")",
1283                                 abort_count);
1284         }
1285
1286         if ((cycles > 0) || (istr != (char *)null_str))
1287                 return scnprintf(bf, bfsize,
1288                         " (predicted:%.1f%% abort:%" PRId64 " %s%s)",
1289                         predicted_percent, abort_count, cstr, istr);
1290
1291         return scnprintf(bf, bfsize,
1292                         " (predicted:%.1f%% abort:%" PRId64 ")",
1293                         predicted_percent, abort_count);
1294 }
1295
1296 static int callchain_counts_printf(FILE *fp, char *bf, int bfsize,
1297                                    u64 branch_count, u64 predicted_count,
1298                                    u64 abort_count, u64 cycles_count,
1299                                    u64 iter_count, u64 samples_count)
1300 {
1301         char str[128];
1302
1303         counts_str_build(str, sizeof(str), branch_count,
1304                          predicted_count, abort_count, cycles_count,
1305                          iter_count, samples_count);
1306
1307         if (fp)
1308                 return fprintf(fp, "%s", str);
1309
1310         return scnprintf(bf, bfsize, "%s", str);
1311 }
1312
1313 int callchain_list_counts__printf_value(struct callchain_node *node,
1314                                         struct callchain_list *clist,
1315                                         FILE *fp, char *bf, int bfsize)
1316 {
1317         u64 branch_count, predicted_count;
1318         u64 abort_count, cycles_count;
1319         u64 iter_count = 0, samples_count = 0;
1320
1321         branch_count = clist->branch_count;
1322         predicted_count = clist->predicted_count;
1323         abort_count = clist->abort_count;
1324         cycles_count = clist->cycles_count;
1325
1326         if (node) {
1327                 struct callchain_list *call;
1328
1329                 list_for_each_entry(call, &node->val, list) {
1330                         iter_count += call->iter_count;
1331                         samples_count += call->samples_count;
1332                 }
1333         }
1334
1335         return callchain_counts_printf(fp, bf, bfsize, branch_count,
1336                                        predicted_count, abort_count,
1337                                        cycles_count, iter_count, samples_count);
1338 }
1339
1340 static void free_callchain_node(struct callchain_node *node)
1341 {
1342         struct callchain_list *list, *tmp;
1343         struct callchain_node *child;
1344         struct rb_node *n;
1345
1346         list_for_each_entry_safe(list, tmp, &node->parent_val, list) {
1347                 list_del(&list->list);
1348                 map__zput(list->ms.map);
1349                 free(list);
1350         }
1351
1352         list_for_each_entry_safe(list, tmp, &node->val, list) {
1353                 list_del(&list->list);
1354                 map__zput(list->ms.map);
1355                 free(list);
1356         }
1357
1358         n = rb_first(&node->rb_root_in);
1359         while (n) {
1360                 child = container_of(n, struct callchain_node, rb_node_in);
1361                 n = rb_next(n);
1362                 rb_erase(&child->rb_node_in, &node->rb_root_in);
1363
1364                 free_callchain_node(child);
1365                 free(child);
1366         }
1367 }
1368
1369 void free_callchain(struct callchain_root *root)
1370 {
1371         if (!symbol_conf.use_callchain)
1372                 return;
1373
1374         free_callchain_node(&root->node);
1375 }
1376
1377 static u64 decay_callchain_node(struct callchain_node *node)
1378 {
1379         struct callchain_node *child;
1380         struct rb_node *n;
1381         u64 child_hits = 0;
1382
1383         n = rb_first(&node->rb_root_in);
1384         while (n) {
1385                 child = container_of(n, struct callchain_node, rb_node_in);
1386
1387                 child_hits += decay_callchain_node(child);
1388                 n = rb_next(n);
1389         }
1390
1391         node->hit = (node->hit * 7) / 8;
1392         node->children_hit = child_hits;
1393
1394         return node->hit;
1395 }
1396
1397 void decay_callchain(struct callchain_root *root)
1398 {
1399         if (!symbol_conf.use_callchain)
1400                 return;
1401
1402         decay_callchain_node(&root->node);
1403 }
1404
1405 int callchain_node__make_parent_list(struct callchain_node *node)
1406 {
1407         struct callchain_node *parent = node->parent;
1408         struct callchain_list *chain, *new;
1409         LIST_HEAD(head);
1410
1411         while (parent) {
1412                 list_for_each_entry_reverse(chain, &parent->val, list) {
1413                         new = malloc(sizeof(*new));
1414                         if (new == NULL)
1415                                 goto out;
1416                         *new = *chain;
1417                         new->has_children = false;
1418                         map__get(new->ms.map);
1419                         list_add_tail(&new->list, &head);
1420                 }
1421                 parent = parent->parent;
1422         }
1423
1424         list_for_each_entry_safe_reverse(chain, new, &head, list)
1425                 list_move_tail(&chain->list, &node->parent_val);
1426
1427         if (!list_empty(&node->parent_val)) {
1428                 chain = list_first_entry(&node->parent_val, struct callchain_list, list);
1429                 chain->has_children = rb_prev(&node->rb_node) || rb_next(&node->rb_node);
1430
1431                 chain = list_first_entry(&node->val, struct callchain_list, list);
1432                 chain->has_children = false;
1433         }
1434         return 0;
1435
1436 out:
1437         list_for_each_entry_safe(chain, new, &head, list) {
1438                 list_del(&chain->list);
1439                 map__zput(chain->ms.map);
1440                 free(chain);
1441         }
1442         return -ENOMEM;
1443 }
1444
1445 int callchain_cursor__copy(struct callchain_cursor *dst,
1446                            struct callchain_cursor *src)
1447 {
1448         int rc = 0;
1449
1450         callchain_cursor_reset(dst);
1451         callchain_cursor_commit(src);
1452
1453         while (true) {
1454                 struct callchain_cursor_node *node;
1455
1456                 node = callchain_cursor_current(src);
1457                 if (node == NULL)
1458                         break;
1459
1460                 rc = callchain_cursor_append(dst, node->ip, node->map, node->sym,
1461                                              node->branch, &node->branch_flags,
1462                                              node->nr_loop_iter, node->samples);
1463                 if (rc)
1464                         break;
1465
1466                 callchain_cursor_advance(src);
1467         }
1468
1469         return rc;
1470 }