tools/perf/util/callchain.c

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