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