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 = get_srcline(cnode->ms.map->dso,
 625                                  map__rip_2objdump(cnode->ms.map, cnode->ip),
 626                                  cnode->ms.sym, true, false);
 627         char *right = get_srcline(node->map->dso,
 628                                   map__rip_2objdump(node->map, node->ip),
 629                                   node->sym, true, false);
 630         enum match_result ret = MATCH_EQ;
 631         int cmp;
 632
 633         if (left && right)
 634                 cmp = strcmp(left, right);
 635         else if (!left && right)
 636                 cmp = 1;
 637         else if (left && !right)
 638                 cmp = -1;
 639         else if (cnode->ip == node->ip)
 640                 cmp = 0;
 641         else
 642                 cmp = (cnode->ip < node->ip) ? -1 : 1;
 643
 644         if (cmp != 0)
 645                 ret = cmp < 0 ? MATCH_LT : MATCH_GT;
 646
 647         free_srcline(left);
 648         free_srcline(right);
 649         return ret;
 650 }
 651
 652 static enum match_result match_chain(struct callchain_cursor_node *node,
 653                                      struct callchain_list *cnode)
 654 {
 655         struct symbol *sym = node->sym;
 656         u64 left, right;
 657
 658         if (callchain_param.key == CCKEY_SRCLINE) {
 659                 enum match_result match = match_chain_srcline(node, cnode);
 660
 661                 if (match != MATCH_ERROR)
 662                         return match;
 663         }
 664
 665         if (cnode->ms.sym && sym && callchain_param.key == CCKEY_FUNCTION) {
 666                 left = cnode->ms.sym->start;
 667                 right = sym->start;
 668         } else {
 669                 left = cnode->ip;
 670                 right = node->ip;
 671         }
 672
 673         if (left == right) {
 674                 if (node->branch) {
 675                         cnode->branch_count++;
 676
 677                         if (node->branch_flags.predicted)
 678                                 cnode->predicted_count++;
 679
 680                         if (node->branch_flags.abort)
 681                                 cnode->abort_count++;
 682
 683                         cnode->cycles_count += node->branch_flags.cycles;
 684                         cnode->iter_count += node->nr_loop_iter;
 685                         cnode->samples_count += node->samples;
 686                 }
 687
 688                 return MATCH_EQ;
 689         }
 690
 691         return left > right ? MATCH_GT : MATCH_LT;
 692 }
 693
 694 /*
 695  * Split the parent in two parts (a new child is created) and
 696  * give a part of its callchain to the created child.
 697  * Then create another child to host the given callchain of new branch
 698  */
 699 static int
 700 split_add_child(struct callchain_node *parent,
 701                 struct callchain_cursor *cursor,
 702                 struct callchain_list *to_split,
 703                 u64 idx_parents, u64 idx_local, u64 period)
 704 {
 705         struct callchain_node *new;
 706         struct list_head *old_tail;
 707         unsigned int idx_total = idx_parents + idx_local;
 708
 709         /* split */
 710         new = create_child(parent, true);
 711         if (new == NULL)
 712                 return -1;
 713
 714         /* split the callchain and move a part to the new child */
 715         old_tail = parent->val.prev;
 716         list_del_range(&to_split->list, old_tail);
 717         new->val.next = &to_split->list;
 718         new->val.prev = old_tail;
 719         to_split->list.prev = &new->val;
 720         old_tail->next = &new->val;
 721
 722         /* split the hits */
 723         new->hit = parent->hit;
 724         new->children_hit = parent->children_hit;
 725         parent->children_hit = callchain_cumul_hits(new);
 726         new->val_nr = parent->val_nr - idx_local;
 727         parent->val_nr = idx_local;
 728         new->count = parent->count;
 729         new->children_count = parent->children_count;
 730         parent->children_count = callchain_cumul_counts(new);
 731
 732         /* create a new child for the new branch if any */
 733         if (idx_total < cursor->nr) {
 734                 struct callchain_node *first;
 735                 struct callchain_list *cnode;
 736                 struct callchain_cursor_node *node;
 737                 struct rb_node *p, **pp;
 738
 739                 parent->hit = 0;
 740                 parent->children_hit += period;
 741                 parent->count = 0;
 742                 parent->children_count += 1;
 743
 744                 node = callchain_cursor_current(cursor);
 745                 new = add_child(parent, cursor, period);
 746                 if (new == NULL)
 747                         return -1;
 748
 749                 /*
 750                  * This is second child since we moved parent's children
 751                  * to new (first) child above.
 752                  */
 753                 p = parent->rb_root_in.rb_node;
 754                 first = rb_entry(p, struct callchain_node, rb_node_in);
 755                 cnode = list_first_entry(&first->val, struct callchain_list,
 756                                          list);
 757
 758                 if (match_chain(node, cnode) == MATCH_LT)
 759                         pp = &p->rb_left;
 760                 else
 761                         pp = &p->rb_right;
 762
 763                 rb_link_node(&new->rb_node_in, p, pp);
 764                 rb_insert_color(&new->rb_node_in, &parent->rb_root_in);
 765         } else {
 766                 parent->hit = period;
 767                 parent->count = 1;
 768         }
 769         return 0;
 770 }
 771
 772 static enum match_result
 773 append_chain(struct callchain_node *root,
 774              struct callchain_cursor *cursor,
 775              u64 period);
 776
 777 static int
 778 append_chain_children(struct callchain_node *root,
 779                       struct callchain_cursor *cursor,
 780                       u64 period)
 781 {
 782         struct callchain_node *rnode;
 783         struct callchain_cursor_node *node;
 784         struct rb_node **p = &root->rb_root_in.rb_node;
 785         struct rb_node *parent = NULL;
 786
 787         node = callchain_cursor_current(cursor);
 788         if (!node)
 789                 return -1;
 790
 791         /* lookup in childrens */
 792         while (*p) {
 793                 enum match_result ret;
 794
 795                 parent = *p;
 796                 rnode = rb_entry(parent, struct callchain_node, rb_node_in);
 797
 798                 /* If at least first entry matches, rely to children */
 799                 ret = append_chain(rnode, cursor, period);
 800                 if (ret == MATCH_EQ)
 801                         goto inc_children_hit;
 802                 if (ret == MATCH_ERROR)
 803                         return -1;
 804
 805                 if (ret == MATCH_LT)
 806                         p = &parent->rb_left;
 807                 else
 808                         p = &parent->rb_right;
 809         }
 810         /* nothing in children, add to the current node */
 811         rnode = add_child(root, cursor, period);
 812         if (rnode == NULL)
 813                 return -1;
 814
 815         rb_link_node(&rnode->rb_node_in, parent, p);
 816         rb_insert_color(&rnode->rb_node_in, &root->rb_root_in);
 817
 818 inc_children_hit:
 819         root->children_hit += period;
 820         root->children_count++;
 821         return 0;
 822 }
 823
 824 static enum match_result
 825 append_chain(struct callchain_node *root,
 826              struct callchain_cursor *cursor,
 827              u64 period)
 828 {
 829         struct callchain_list *cnode;
 830         u64 start = cursor->pos;
 831         bool found = false;
 832         u64 matches;
 833         enum match_result cmp = MATCH_ERROR;
 834
 835         /*
 836          * Lookup in the current node
 837          * If we have a symbol, then compare the start to match
 838          * anywhere inside a function, unless function
 839          * mode is disabled.
 840          */
 841         list_for_each_entry(cnode, &root->val, list) {
 842                 struct callchain_cursor_node *node;
 843
 844                 node = callchain_cursor_current(cursor);
 845                 if (!node)
 846                         break;
 847
 848                 cmp = match_chain(node, cnode);
 849                 if (cmp != MATCH_EQ)
 850                         break;
 851
 852                 found = true;
 853
 854                 callchain_cursor_advance(cursor);
 855         }
 856
 857         /* matches not, relay no the parent */
 858         if (!found) {
 859                 WARN_ONCE(cmp == MATCH_ERROR, "Chain comparison error\n");
 860                 return cmp;
 861         }
 862
 863         matches = cursor->pos - start;
 864
 865         /* we match only a part of the node. Split it and add the new chain */
 866         if (matches < root->val_nr) {
 867                 if (split_add_child(root, cursor, cnode, start, matches,
 868                                     period) < 0)
 869                         return MATCH_ERROR;
 870
 871                 return MATCH_EQ;
 872         }
 873
 874         /* we match 100% of the path, increment the hit */
 875         if (matches == root->val_nr && cursor->pos == cursor->nr) {
 876                 root->hit += period;
 877                 root->count++;
 878                 return MATCH_EQ;
 879         }
 880
 881         /* We match the node and still have a part remaining */
 882         if (append_chain_children(root, cursor, period) < 0)
 883                 return MATCH_ERROR;
 884
 885         return MATCH_EQ;
 886 }
 887
 888 int callchain_append(struct callchain_root *root,
 889                      struct callchain_cursor *cursor,
 890                      u64 period)
 891 {
 892         if (!cursor->nr)
 893                 return 0;
 894
 895         callchain_cursor_commit(cursor);
 896
 897         if (append_chain_children(&root->node, cursor, period) < 0)
 898                 return -1;
 899
 900         if (cursor->nr > root->max_depth)
 901                 root->max_depth = cursor->nr;
 902
 903         return 0;
 904 }
 905
 906 static int
 907 merge_chain_branch(struct callchain_cursor *cursor,
 908                    struct callchain_node *dst, struct callchain_node *src)
 909 {
 910         struct callchain_cursor_node **old_last = cursor->last;
 911         struct callchain_node *child;
 912         struct callchain_list *list, *next_list;
 913         struct rb_node *n;
 914         int old_pos = cursor->nr;
 915         int err = 0;
 916
 917         list_for_each_entry_safe(list, next_list, &src->val, list) {
 918                 callchain_cursor_append(cursor, list->ip,
 919                                         list->ms.map, list->ms.sym,
 920                                         false, NULL, 0, 0);
 921                 list_del(&list->list);
 922                 map__zput(list->ms.map);
 923                 free(list);
 924         }
 925
 926         if (src->hit) {
 927                 callchain_cursor_commit(cursor);
 928                 if (append_chain_children(dst, cursor, src->hit) < 0)
 929                         return -1;
 930         }
 931
 932         n = rb_first(&src->rb_root_in);
 933         while (n) {
 934                 child = container_of(n, struct callchain_node, rb_node_in);
 935                 n = rb_next(n);
 936                 rb_erase(&child->rb_node_in, &src->rb_root_in);
 937
 938                 err = merge_chain_branch(cursor, dst, child);
 939                 if (err)
 940                         break;
 941
 942                 free(child);
 943         }
 944
 945         cursor->nr = old_pos;
 946         cursor->last = old_last;
 947
 948         return err;
 949 }
 950
 951 int callchain_merge(struct callchain_cursor *cursor,
 952                     struct callchain_root *dst, struct callchain_root *src)
 953 {
 954         return merge_chain_branch(cursor, &dst->node, &src->node);
 955 }
 956
 957 int callchain_cursor_append(struct callchain_cursor *cursor,
 958                             u64 ip, struct map *map, struct symbol *sym,
 959                             bool branch, struct branch_flags *flags,
 960                             int nr_loop_iter, int samples)
 961 {
 962         struct callchain_cursor_node *node = *cursor->last;
 963
 964         if (!node) {
 965                 node = calloc(1, sizeof(*node));
 966                 if (!node)
 967                         return -ENOMEM;
 968
 969                 *cursor->last = node;
 970         }
 971
 972         node->ip = ip;
 973         map__zput(node->map);
 974         node->map = map__get(map);
 975         node->sym = sym;
 976         node->branch = branch;
 977         node->nr_loop_iter = nr_loop_iter;
 978         node->samples = samples;
 979
 980         if (flags)
 981                 memcpy(&node->branch_flags, flags,
 982                         sizeof(struct branch_flags));
 983
 984         cursor->nr++;
 985
 986         cursor->last = &node->next;
 987
 988         return 0;
 989 }
 990
 991 int sample__resolve_callchain(struct perf_sample *sample,
 992                               struct callchain_cursor *cursor, struct symbol **parent,
 993                               struct perf_evsel *evsel, struct addr_location *al,
 994                               int max_stack)
 995 {
 996         if (sample->callchain == NULL)
 997                 return 0;
 998
 999         if (symbol_conf.use_callchain || symbol_conf.cumulate_callchain ||
1000             perf_hpp_list.parent) {
1001                 return thread__resolve_callchain(al->thread, cursor, evsel, sample,
1002                                                  parent, al, max_stack);
1003         }
1004         return 0;
1005 }
1006
1007 int hist_entry__append_callchain(struct hist_entry *he, struct perf_sample *sample)
1008 {
1009         if (!symbol_conf.use_callchain || sample->callchain == NULL)
1010                 return 0;
1011         return callchain_append(he->callchain, &callchain_cursor, sample->period);
1012 }
1013
1014 int fill_callchain_info(struct addr_location *al, struct callchain_cursor_node *node,
1015                         bool hide_unresolved)
1016 {
1017         al->map = node->map;
1018         al->sym = node->sym;
1019         if (node->map)
1020                 al->addr = node->map->map_ip(node->map, node->ip);
1021         else
1022                 al->addr = node->ip;
1023
1024         if (al->sym == NULL) {
1025                 if (hide_unresolved)
1026                         return 0;
1027                 if (al->map == NULL)
1028                         goto out;
1029         }
1030
1031         if (al->map->groups == &al->machine->kmaps) {
1032                 if (machine__is_host(al->machine)) {
1033                         al->cpumode = PERF_RECORD_MISC_KERNEL;
1034                         al->level = 'k';
1035                 } else {
1036                         al->cpumode = PERF_RECORD_MISC_GUEST_KERNEL;
1037                         al->level = 'g';
1038                 }
1039         } else {
1040                 if (machine__is_host(al->machine)) {
1041                         al->cpumode = PERF_RECORD_MISC_USER;
1042                         al->level = '.';
1043                 } else if (perf_guest) {
1044                         al->cpumode = PERF_RECORD_MISC_GUEST_USER;
1045                         al->level = 'u';
1046                 } else {
1047                         al->cpumode = PERF_RECORD_MISC_HYPERVISOR;
1048                         al->level = 'H';
1049                 }
1050         }
1051
1052 out:
1053         return 1;
1054 }
1055
1056 char *callchain_list__sym_name(struct callchain_list *cl,
1057                                char *bf, size_t bfsize, bool show_dso)
1058 {
1059         bool show_addr = callchain_param.key == CCKEY_ADDRESS;
1060         bool show_srcline = show_addr || callchain_param.key == CCKEY_SRCLINE;
1061         int printed;
1062
1063         if (cl->ms.sym) {
1064                 if (show_srcline && cl->ms.map && !cl->srcline)
1065                         cl->srcline = get_srcline(cl->ms.map->dso,
1066                                                   map__rip_2objdump(cl->ms.map,
1067                                                                     cl->ip),
1068                                                   cl->ms.sym, false, show_addr);
1069                 if (cl->srcline)
1070                         printed = scnprintf(bf, bfsize, "%s %s",
1071                                         cl->ms.sym->name, cl->srcline);
1072                 else
1073                         printed = scnprintf(bf, bfsize, "%s", cl->ms.sym->name);
1074         } else
1075                 printed = scnprintf(bf, bfsize, "%#" PRIx64, cl->ip);
1076
1077         if (show_dso)
1078                 scnprintf(bf + printed, bfsize - printed, " %s",
1079                           cl->ms.map ?
1080                           cl->ms.map->dso->short_name :
1081                           "unknown");
1082
1083         return bf;
1084 }
1085
1086 char *callchain_node__scnprintf_value(struct callchain_node *node,
1087                                       char *bf, size_t bfsize, u64 total)
1088 {
1089         double percent = 0.0;
1090         u64 period = callchain_cumul_hits(node);
1091         unsigned count = callchain_cumul_counts(node);
1092
1093         if (callchain_param.mode == CHAIN_FOLDED) {
1094                 period = node->hit;
1095                 count = node->count;
1096         }
1097
1098         switch (callchain_param.value) {
1099         case CCVAL_PERIOD:
1100                 scnprintf(bf, bfsize, "%"PRIu64, period);
1101                 break;
1102         case CCVAL_COUNT:
1103                 scnprintf(bf, bfsize, "%u", count);
1104                 break;
1105         case CCVAL_PERCENT:
1106         default:
1107                 if (total)
1108                         percent = period * 100.0 / total;
1109                 scnprintf(bf, bfsize, "%.2f%%", percent);
1110                 break;
1111         }
1112         return bf;
1113 }
1114
1115 int callchain_node__fprintf_value(struct callchain_node *node,
1116                                  FILE *fp, u64 total)
1117 {
1118         double percent = 0.0;
1119         u64 period = callchain_cumul_hits(node);
1120         unsigned count = callchain_cumul_counts(node);
1121
1122         if (callchain_param.mode == CHAIN_FOLDED) {
1123                 period = node->hit;
1124                 count = node->count;
1125         }
1126
1127         switch (callchain_param.value) {
1128         case CCVAL_PERIOD:
1129                 return fprintf(fp, "%"PRIu64, period);
1130         case CCVAL_COUNT:
1131                 return fprintf(fp, "%u", count);
1132         case CCVAL_PERCENT:
1133         default:
1134                 if (total)
1135                         percent = period * 100.0 / total;
1136                 return percent_color_fprintf(fp, "%.2f%%", percent);
1137         }
1138         return 0;
1139 }
1140
1141 static void callchain_counts_value(struct callchain_node *node,
1142                                    u64 *branch_count, u64 *predicted_count,
1143                                    u64 *abort_count, u64 *cycles_count)
1144 {
1145         struct callchain_list *clist;
1146
1147         list_for_each_entry(clist, &node->val, list) {
1148                 if (branch_count)
1149                         *branch_count += clist->branch_count;
1150
1151                 if (predicted_count)
1152                         *predicted_count += clist->predicted_count;
1153
1154                 if (abort_count)
1155                         *abort_count += clist->abort_count;
1156
1157                 if (cycles_count)
1158                         *cycles_count += clist->cycles_count;
1159         }
1160 }
1161
1162 static int callchain_node_branch_counts_cumul(struct callchain_node *node,
1163                                               u64 *branch_count,
1164                                               u64 *predicted_count,
1165                                               u64 *abort_count,
1166                                               u64 *cycles_count)
1167 {
1168         struct callchain_node *child;
1169         struct rb_node *n;
1170
1171         n = rb_first(&node->rb_root_in);
1172         while (n) {
1173                 child = rb_entry(n, struct callchain_node, rb_node_in);
1174                 n = rb_next(n);
1175
1176                 callchain_node_branch_counts_cumul(child, branch_count,
1177                                                    predicted_count,
1178                                                    abort_count,
1179                                                    cycles_count);
1180
1181                 callchain_counts_value(child, branch_count,
1182                                        predicted_count, abort_count,
1183                                        cycles_count);
1184         }
1185
1186         return 0;
1187 }
1188
1189 int callchain_branch_counts(struct callchain_root *root,
1190                             u64 *branch_count, u64 *predicted_count,
1191                             u64 *abort_count, u64 *cycles_count)
1192 {
1193         if (branch_count)
1194                 *branch_count = 0;
1195
1196         if (predicted_count)
1197                 *predicted_count = 0;
1198
1199         if (abort_count)
1200                 *abort_count = 0;
1201
1202         if (cycles_count)
1203                 *cycles_count = 0;
1204
1205         return callchain_node_branch_counts_cumul(&root->node,
1206                                                   branch_count,
1207                                                   predicted_count,
1208                                                   abort_count,
1209                                                   cycles_count);
1210 }
1211
1212 static int counts_str_build(char *bf, int bfsize,
1213                              u64 branch_count, u64 predicted_count,
1214                              u64 abort_count, u64 cycles_count,
1215                              u64 iter_count, u64 samples_count)
1216 {
1217         double predicted_percent = 0.0;
1218         const char *null_str = "";
1219         char iter_str[32];
1220         char cycle_str[32];
1221         char *istr, *cstr;
1222         u64 cycles;
1223
1224         if (branch_count == 0)
1225                 return scnprintf(bf, bfsize, " (calltrace)");
1226
1227         cycles = cycles_count / branch_count;
1228
1229         if (iter_count && samples_count) {
1230                 if (cycles > 0)
1231                         scnprintf(iter_str, sizeof(iter_str),
1232                                  " iterations:%" PRId64 "",
1233                                  iter_count / samples_count);
1234                 else
1235                         scnprintf(iter_str, sizeof(iter_str),
1236                                  "iterations:%" PRId64 "",
1237                                  iter_count / samples_count);
1238                 istr = iter_str;
1239         } else
1240                 istr = (char *)null_str;
1241
1242         if (cycles > 0) {
1243                 scnprintf(cycle_str, sizeof(cycle_str),
1244                           "cycles:%" PRId64 "", cycles);
1245                 cstr = cycle_str;
1246         } else
1247                 cstr = (char *)null_str;
1248
1249         predicted_percent = predicted_count * 100.0 / branch_count;
1250
1251         if ((predicted_count == branch_count) && (abort_count == 0)) {
1252                 if ((cycles > 0) || (istr != (char *)null_str))
1253                         return scnprintf(bf, bfsize, " (%s%s)", cstr, istr);
1254                 else
1255                         return scnprintf(bf, bfsize, "%s", (char *)null_str);
1256         }
1257
1258         if ((predicted_count < branch_count) && (abort_count == 0)) {
1259                 if ((cycles > 0) || (istr != (char *)null_str))
1260                         return scnprintf(bf, bfsize,
1261                                 " (predicted:%.1f%% %s%s)",
1262                                 predicted_percent, cstr, istr);
1263                 else {
1264                         return scnprintf(bf, bfsize,
1265                                 " (predicted:%.1f%%)",
1266                                 predicted_percent);
1267                 }
1268         }
1269
1270         if ((predicted_count == branch_count) && (abort_count > 0)) {
1271                 if ((cycles > 0) || (istr != (char *)null_str))
1272                         return scnprintf(bf, bfsize,
1273                                 " (abort:%" PRId64 " %s%s)",
1274                                 abort_count, cstr, istr);
1275                 else
1276                         return scnprintf(bf, bfsize,
1277                                 " (abort:%" PRId64 ")",
1278                                 abort_count);
1279         }
1280
1281         if ((cycles > 0) || (istr != (char *)null_str))
1282                 return scnprintf(bf, bfsize,
1283                         " (predicted:%.1f%% abort:%" PRId64 " %s%s)",
1284                         predicted_percent, abort_count, cstr, istr);
1285
1286         return scnprintf(bf, bfsize,
1287                         " (predicted:%.1f%% abort:%" PRId64 ")",
1288                         predicted_percent, abort_count);
1289 }
1290
1291 static int callchain_counts_printf(FILE *fp, char *bf, int bfsize,
1292                                    u64 branch_count, u64 predicted_count,
1293                                    u64 abort_count, u64 cycles_count,
1294                                    u64 iter_count, u64 samples_count)
1295 {
1296         char str[128];
1297
1298         counts_str_build(str, sizeof(str), branch_count,
1299                          predicted_count, abort_count, cycles_count,
1300                          iter_count, samples_count);
1301
1302         if (fp)
1303                 return fprintf(fp, "%s", str);
1304
1305         return scnprintf(bf, bfsize, "%s", str);
1306 }
1307
1308 int callchain_list_counts__printf_value(struct callchain_node *node,
1309                                         struct callchain_list *clist,
1310                                         FILE *fp, char *bf, int bfsize)
1311 {
1312         u64 branch_count, predicted_count;
1313         u64 abort_count, cycles_count;
1314         u64 iter_count = 0, samples_count = 0;
1315
1316         branch_count = clist->branch_count;
1317         predicted_count = clist->predicted_count;
1318         abort_count = clist->abort_count;
1319         cycles_count = clist->cycles_count;
1320
1321         if (node) {
1322                 struct callchain_list *call;
1323
1324                 list_for_each_entry(call, &node->val, list) {
1325                         iter_count += call->iter_count;
1326                         samples_count += call->samples_count;
1327                 }
1328         }
1329
1330         return callchain_counts_printf(fp, bf, bfsize, branch_count,
1331                                        predicted_count, abort_count,
1332                                        cycles_count, iter_count, samples_count);
1333 }
1334
1335 static void free_callchain_node(struct callchain_node *node)
1336 {
1337         struct callchain_list *list, *tmp;
1338         struct callchain_node *child;
1339         struct rb_node *n;
1340
1341         list_for_each_entry_safe(list, tmp, &node->parent_val, list) {
1342                 list_del(&list->list);
1343                 map__zput(list->ms.map);
1344                 free(list);
1345         }
1346
1347         list_for_each_entry_safe(list, tmp, &node->val, list) {
1348                 list_del(&list->list);
1349                 map__zput(list->ms.map);
1350                 free(list);
1351         }
1352
1353         n = rb_first(&node->rb_root_in);
1354         while (n) {
1355                 child = container_of(n, struct callchain_node, rb_node_in);
1356                 n = rb_next(n);
1357                 rb_erase(&child->rb_node_in, &node->rb_root_in);
1358
1359                 free_callchain_node(child);
1360                 free(child);
1361         }
1362 }
1363
1364 void free_callchain(struct callchain_root *root)
1365 {
1366         if (!symbol_conf.use_callchain)
1367                 return;
1368
1369         free_callchain_node(&root->node);
1370 }
1371
1372 static u64 decay_callchain_node(struct callchain_node *node)
1373 {
1374         struct callchain_node *child;
1375         struct rb_node *n;
1376         u64 child_hits = 0;
1377
1378         n = rb_first(&node->rb_root_in);
1379         while (n) {
1380                 child = container_of(n, struct callchain_node, rb_node_in);
1381
1382                 child_hits += decay_callchain_node(child);
1383                 n = rb_next(n);
1384         }
1385
1386         node->hit = (node->hit * 7) / 8;
1387         node->children_hit = child_hits;
1388
1389         return node->hit;
1390 }
1391
1392 void decay_callchain(struct callchain_root *root)
1393 {
1394         if (!symbol_conf.use_callchain)
1395                 return;
1396
1397         decay_callchain_node(&root->node);
1398 }
1399
1400 int callchain_node__make_parent_list(struct callchain_node *node)
1401 {
1402         struct callchain_node *parent = node->parent;
1403         struct callchain_list *chain, *new;
1404         LIST_HEAD(head);
1405
1406         while (parent) {
1407                 list_for_each_entry_reverse(chain, &parent->val, list) {
1408                         new = malloc(sizeof(*new));
1409                         if (new == NULL)
1410                                 goto out;
1411                         *new = *chain;
1412                         new->has_children = false;
1413                         map__get(new->ms.map);
1414                         list_add_tail(&new->list, &head);
1415                 }
1416                 parent = parent->parent;
1417         }
1418
1419         list_for_each_entry_safe_reverse(chain, new, &head, list)
1420                 list_move_tail(&chain->list, &node->parent_val);
1421
1422         if (!list_empty(&node->parent_val)) {
1423                 chain = list_first_entry(&node->parent_val, struct callchain_list, list);
1424                 chain->has_children = rb_prev(&node->rb_node) || rb_next(&node->rb_node);
1425
1426                 chain = list_first_entry(&node->val, struct callchain_list, list);
1427                 chain->has_children = false;
1428         }
1429         return 0;
1430
1431 out:
1432         list_for_each_entry_safe(chain, new, &head, list) {
1433                 list_del(&chain->list);
1434                 map__zput(chain->ms.map);
1435                 free(chain);
1436         }
1437         return -ENOMEM;
1438 }
1439
1440 int callchain_cursor__copy(struct callchain_cursor *dst,
1441                            struct callchain_cursor *src)
1442 {
1443         int rc = 0;
1444
1445         callchain_cursor_reset(dst);
1446         callchain_cursor_commit(src);
1447
1448         while (true) {
1449                 struct callchain_cursor_node *node;
1450
1451                 node = callchain_cursor_current(src);
1452                 if (node == NULL)
1453                         break;
1454
1455                 rc = callchain_cursor_append(dst, node->ip, node->map, node->sym,
1456                                              node->branch, &node->branch_flags,
1457                                              node->nr_loop_iter, node->samples);
1458                 if (rc)
1459                         break;
1460
1461                 callchain_cursor_advance(src);
1462         }
1463
1464         return rc;
1465 }