tools/perf/util/callchain.c

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