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