tools/perf/util/callchain.c

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