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