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
  29 parse_callchain_report_opt(const char *arg)
  30 {
  31         char *tok, *tok2;
  32         char *endptr;
  33
  34         symbol_conf.use_callchain = true;
  35
  36         if (!arg)
  37                 return 0;
  38
  39         tok = strtok((char *)arg, ",");
  40         if (!tok)
  41                 return -1;
  42
  43         /* get the output mode */
  44         if (!strncmp(tok, "graph", strlen(arg))) {
  45                 callchain_param.mode = CHAIN_GRAPH_ABS;
  46
  47         } else if (!strncmp(tok, "flat", strlen(arg))) {
  48                 callchain_param.mode = CHAIN_FLAT;
  49         } else if (!strncmp(tok, "fractal", strlen(arg))) {
  50                 callchain_param.mode = CHAIN_GRAPH_REL;
  51         } else if (!strncmp(tok, "none", strlen(arg))) {
  52                 callchain_param.mode = CHAIN_NONE;
  53                 symbol_conf.use_callchain = false;
  54                 return 0;
  55         } else {
  56                 return -1;
  57         }
  58
  59         /* get the min percentage */
  60         tok = strtok(NULL, ",");
  61         if (!tok)
  62                 goto setup;
  63
  64         callchain_param.min_percent = strtod(tok, &endptr);
  65         if (tok == endptr)
  66                 return -1;
  67
  68         /* get the print limit */
  69         tok2 = strtok(NULL, ",");
  70         if (!tok2)
  71                 goto setup;
  72
  73         if (tok2[0] != 'c') {
  74                 callchain_param.print_limit = strtoul(tok2, &endptr, 0);
  75                 tok2 = strtok(NULL, ",");
  76                 if (!tok2)
  77                         goto setup;
  78         }
  79
  80         /* get the call chain order */
  81         if (!strncmp(tok2, "caller", strlen("caller")))
  82                 callchain_param.order = ORDER_CALLER;
  83         else if (!strncmp(tok2, "callee", strlen("callee")))
  84                 callchain_param.order = ORDER_CALLEE;
  85         else
  86                 return -1;
  87
  88         /* Get the sort key */
  89         tok2 = strtok(NULL, ",");
  90         if (!tok2)
  91                 goto setup;
  92         if (!strncmp(tok2, "function", strlen("function")))
  93                 callchain_param.key = CCKEY_FUNCTION;
  94         else if (!strncmp(tok2, "address", strlen("address")))
  95                 callchain_param.key = CCKEY_ADDRESS;
  96         else
  97                 return -1;
  98 setup:
  99         if (callchain_register_param(&callchain_param) < 0) {
 100                 pr_err("Can't register callchain params\n");
 101                 return -1;
 102         }
 103         return 0;
 104 }
 105
 106 static void
 107 rb_insert_callchain(struct rb_root *root, struct callchain_node *chain,
 108                     enum chain_mode mode)
 109 {
 110         struct rb_node **p = &root->rb_node;
 111         struct rb_node *parent = NULL;
 112         struct callchain_node *rnode;
 113         u64 chain_cumul = callchain_cumul_hits(chain);
 114
 115         while (*p) {
 116                 u64 rnode_cumul;
 117
 118                 parent = *p;
 119                 rnode = rb_entry(parent, struct callchain_node, rb_node);
 120                 rnode_cumul = callchain_cumul_hits(rnode);
 121
 122                 switch (mode) {
 123                 case CHAIN_FLAT:
 124                         if (rnode->hit < chain->hit)
 125                                 p = &(*p)->rb_left;
 126                         else
 127                                 p = &(*p)->rb_right;
 128                         break;
 129                 case CHAIN_GRAPH_ABS: /* Falldown */
 130                 case CHAIN_GRAPH_REL:
 131                         if (rnode_cumul < chain_cumul)
 132                                 p = &(*p)->rb_left;
 133                         else
 134                                 p = &(*p)->rb_right;
 135                         break;
 136                 case CHAIN_NONE:
 137                 default:
 138                         break;
 139                 }
 140         }
 141
 142         rb_link_node(&chain->rb_node, parent, p);
 143         rb_insert_color(&chain->rb_node, root);
 144 }
 145
 146 static void
 147 __sort_chain_flat(struct rb_root *rb_root, struct callchain_node *node,
 148                   u64 min_hit)
 149 {
 150         struct rb_node *n;
 151         struct callchain_node *child;
 152
 153         n = rb_first(&node->rb_root_in);
 154         while (n) {
 155                 child = rb_entry(n, struct callchain_node, rb_node_in);
 156                 n = rb_next(n);
 157
 158                 __sort_chain_flat(rb_root, child, min_hit);
 159         }
 160
 161         if (node->hit && node->hit >= min_hit)
 162                 rb_insert_callchain(rb_root, node, CHAIN_FLAT);
 163 }
 164
 165 /*
 166  * Once we get every callchains from the stream, we can now
 167  * sort them by hit
 168  */
 169 static void
 170 sort_chain_flat(struct rb_root *rb_root, struct callchain_root *root,
 171                 u64 min_hit, struct callchain_param *param __maybe_unused)
 172 {
 173         __sort_chain_flat(rb_root, &root->node, min_hit);
 174 }
 175
 176 static void __sort_chain_graph_abs(struct callchain_node *node,
 177                                    u64 min_hit)
 178 {
 179         struct rb_node *n;
 180         struct callchain_node *child;
 181
 182         node->rb_root = RB_ROOT;
 183         n = rb_first(&node->rb_root_in);
 184
 185         while (n) {
 186                 child = rb_entry(n, struct callchain_node, rb_node_in);
 187                 n = rb_next(n);
 188
 189                 __sort_chain_graph_abs(child, min_hit);
 190                 if (callchain_cumul_hits(child) >= min_hit)
 191                         rb_insert_callchain(&node->rb_root, child,
 192                                             CHAIN_GRAPH_ABS);
 193         }
 194 }
 195
 196 static void
 197 sort_chain_graph_abs(struct rb_root *rb_root, struct callchain_root *chain_root,
 198                      u64 min_hit, struct callchain_param *param __maybe_unused)
 199 {
 200         __sort_chain_graph_abs(&chain_root->node, min_hit);
 201         rb_root->rb_node = chain_root->node.rb_root.rb_node;
 202 }
 203
 204 static void __sort_chain_graph_rel(struct callchain_node *node,
 205                                    double min_percent)
 206 {
 207         struct rb_node *n;
 208         struct callchain_node *child;
 209         u64 min_hit;
 210
 211         node->rb_root = RB_ROOT;
 212         min_hit = ceil(node->children_hit * min_percent);
 213
 214         n = rb_first(&node->rb_root_in);
 215         while (n) {
 216                 child = rb_entry(n, struct callchain_node, rb_node_in);
 217                 n = rb_next(n);
 218
 219                 __sort_chain_graph_rel(child, min_percent);
 220                 if (callchain_cumul_hits(child) >= min_hit)
 221                         rb_insert_callchain(&node->rb_root, child,
 222                                             CHAIN_GRAPH_REL);
 223         }
 224 }
 225
 226 static void
 227 sort_chain_graph_rel(struct rb_root *rb_root, struct callchain_root *chain_root,
 228                      u64 min_hit __maybe_unused, struct callchain_param *param)
 229 {
 230         __sort_chain_graph_rel(&chain_root->node, param->min_percent / 100.0);
 231         rb_root->rb_node = chain_root->node.rb_root.rb_node;
 232 }
 233
 234 int callchain_register_param(struct callchain_param *param)
 235 {
 236         switch (param->mode) {
 237         case CHAIN_GRAPH_ABS:
 238                 param->sort = sort_chain_graph_abs;
 239                 break;
 240         case CHAIN_GRAPH_REL:
 241                 param->sort = sort_chain_graph_rel;
 242                 break;
 243         case CHAIN_FLAT:
 244                 param->sort = sort_chain_flat;
 245                 break;
 246         case CHAIN_NONE:
 247         default:
 248                 return -1;
 249         }
 250         return 0;
 251 }
 252
 253 /*
 254  * Create a child for a parent. If inherit_children, then the new child
 255  * will become the new parent of it's parent children
 256  */
 257 static struct callchain_node *
 258 create_child(struct callchain_node *parent, bool inherit_children)
 259 {
 260         struct callchain_node *new;
 261
 262         new = zalloc(sizeof(*new));
 263         if (!new) {
 264                 perror("not enough memory to create child for code path tree");
 265                 return NULL;
 266         }
 267         new->parent = parent;
 268         INIT_LIST_HEAD(&new->val);
 269
 270         if (inherit_children) {
 271                 struct rb_node *n;
 272                 struct callchain_node *child;
 273
 274                 new->rb_root_in = parent->rb_root_in;
 275                 parent->rb_root_in = RB_ROOT;
 276
 277                 n = rb_first(&new->rb_root_in);
 278                 while (n) {
 279                         child = rb_entry(n, struct callchain_node, rb_node_in);
 280                         child->parent = new;
 281                         n = rb_next(n);
 282                 }
 283
 284                 /* make it the first child */
 285                 rb_link_node(&new->rb_node_in, NULL, &parent->rb_root_in.rb_node);
 286                 rb_insert_color(&new->rb_node_in, &parent->rb_root_in);
 287         }
 288
 289         return new;
 290 }
 291
 292
 293 /*
 294  * Fill the node with callchain values
 295  */
 296 static void
 297 fill_node(struct callchain_node *node, struct callchain_cursor *cursor)
 298 {
 299         struct callchain_cursor_node *cursor_node;
 300
 301         node->val_nr = cursor->nr - cursor->pos;
 302         if (!node->val_nr)
 303                 pr_warning("Warning: empty node in callchain tree\n");
 304
 305         cursor_node = callchain_cursor_current(cursor);
 306
 307         while (cursor_node) {
 308                 struct callchain_list *call;
 309
 310                 call = zalloc(sizeof(*call));
 311                 if (!call) {
 312                         perror("not enough memory for the code path tree");
 313                         return;
 314                 }
 315                 call->ip = cursor_node->ip;
 316                 call->ms.sym = cursor_node->sym;
 317                 call->ms.map = cursor_node->map;
 318                 list_add_tail(&call->list, &node->val);
 319
 320                 callchain_cursor_advance(cursor);
 321                 cursor_node = callchain_cursor_current(cursor);
 322         }
 323 }
 324
 325 static struct callchain_node *
 326 add_child(struct callchain_node *parent,
 327           struct callchain_cursor *cursor,
 328           u64 period)
 329 {
 330         struct callchain_node *new;
 331
 332         new = create_child(parent, false);
 333         fill_node(new, cursor);
 334
 335         new->children_hit = 0;
 336         new->hit = period;
 337         return new;
 338 }
 339
 340 static s64 match_chain(struct callchain_cursor_node *node,
 341                       struct callchain_list *cnode)
 342 {
 343         struct symbol *sym = node->sym;
 344
 345         if (cnode->ms.sym && sym &&
 346             callchain_param.key == CCKEY_FUNCTION)
 347                 return cnode->ms.sym->start - sym->start;
 348         else
 349                 return cnode->ip - node->ip;
 350 }
 351
 352 /*
 353  * Split the parent in two parts (a new child is created) and
 354  * give a part of its callchain to the created child.
 355  * Then create another child to host the given callchain of new branch
 356  */
 357 static void
 358 split_add_child(struct callchain_node *parent,
 359                 struct callchain_cursor *cursor,
 360                 struct callchain_list *to_split,
 361                 u64 idx_parents, u64 idx_local, u64 period)
 362 {
 363         struct callchain_node *new;
 364         struct list_head *old_tail;
 365         unsigned int idx_total = idx_parents + idx_local;
 366
 367         /* split */
 368         new = create_child(parent, true);
 369
 370         /* split the callchain and move a part to the new child */
 371         old_tail = parent->val.prev;
 372         list_del_range(&to_split->list, old_tail);
 373         new->val.next = &to_split->list;
 374         new->val.prev = old_tail;
 375         to_split->list.prev = &new->val;
 376         old_tail->next = &new->val;
 377
 378         /* split the hits */
 379         new->hit = parent->hit;
 380         new->children_hit = parent->children_hit;
 381         parent->children_hit = callchain_cumul_hits(new);
 382         new->val_nr = parent->val_nr - idx_local;
 383         parent->val_nr = idx_local;
 384
 385         /* create a new child for the new branch if any */
 386         if (idx_total < cursor->nr) {
 387                 struct callchain_node *first;
 388                 struct callchain_list *cnode;
 389                 struct callchain_cursor_node *node;
 390                 struct rb_node *p, **pp;
 391
 392                 parent->hit = 0;
 393                 parent->children_hit += period;
 394
 395                 node = callchain_cursor_current(cursor);
 396                 new = add_child(parent, cursor, period);
 397
 398                 /*
 399                  * This is second child since we moved parent's children
 400                  * to new (first) child above.
 401                  */
 402                 p = parent->rb_root_in.rb_node;
 403                 first = rb_entry(p, struct callchain_node, rb_node_in);
 404                 cnode = list_first_entry(&first->val, struct callchain_list,
 405                                          list);
 406
 407                 if (match_chain(node, cnode) < 0)
 408                         pp = &p->rb_left;
 409                 else
 410                         pp = &p->rb_right;
 411
 412                 rb_link_node(&new->rb_node_in, p, pp);
 413                 rb_insert_color(&new->rb_node_in, &parent->rb_root_in);
 414         } else {
 415                 parent->hit = period;
 416         }
 417 }
 418
 419 static int
 420 append_chain(struct callchain_node *root,
 421              struct callchain_cursor *cursor,
 422              u64 period);
 423
 424 static void
 425 append_chain_children(struct callchain_node *root,
 426                       struct callchain_cursor *cursor,
 427                       u64 period)
 428 {
 429         struct callchain_node *rnode;
 430         struct callchain_cursor_node *node;
 431         struct rb_node **p = &root->rb_root_in.rb_node;
 432         struct rb_node *parent = NULL;
 433
 434         node = callchain_cursor_current(cursor);
 435         if (!node)
 436                 return;
 437
 438         /* lookup in childrens */
 439         while (*p) {
 440                 s64 ret;
 441
 442                 parent = *p;
 443                 rnode = rb_entry(parent, struct callchain_node, rb_node_in);
 444
 445                 /* If at least first entry matches, rely to children */
 446                 ret = append_chain(rnode, cursor, period);
 447                 if (ret == 0)
 448                         goto inc_children_hit;
 449
 450                 if (ret < 0)
 451                         p = &parent->rb_left;
 452                 else
 453                         p = &parent->rb_right;
 454         }
 455         /* nothing in children, add to the current node */
 456         rnode = add_child(root, cursor, period);
 457         rb_link_node(&rnode->rb_node_in, parent, p);
 458         rb_insert_color(&rnode->rb_node_in, &root->rb_root_in);
 459
 460 inc_children_hit:
 461         root->children_hit += period;
 462 }
 463
 464 static int
 465 append_chain(struct callchain_node *root,
 466              struct callchain_cursor *cursor,
 467              u64 period)
 468 {
 469         struct callchain_list *cnode;
 470         u64 start = cursor->pos;
 471         bool found = false;
 472         u64 matches;
 473         int cmp = 0;
 474
 475         /*
 476          * Lookup in the current node
 477          * If we have a symbol, then compare the start to match
 478          * anywhere inside a function, unless function
 479          * mode is disabled.
 480          */
 481         list_for_each_entry(cnode, &root->val, list) {
 482                 struct callchain_cursor_node *node;
 483
 484                 node = callchain_cursor_current(cursor);
 485                 if (!node)
 486                         break;
 487
 488                 cmp = match_chain(node, cnode);
 489                 if (cmp)
 490                         break;
 491
 492                 found = true;
 493
 494                 callchain_cursor_advance(cursor);
 495         }
 496
 497         /* matches not, relay no the parent */
 498         if (!found) {
 499                 WARN_ONCE(!cmp, "Chain comparison error\n");
 500                 return cmp;
 501         }
 502
 503         matches = cursor->pos - start;
 504
 505         /* we match only a part of the node. Split it and add the new chain */
 506         if (matches < root->val_nr) {
 507                 split_add_child(root, cursor, cnode, start, matches, period);
 508                 return 0;
 509         }
 510
 511         /* we match 100% of the path, increment the hit */
 512         if (matches == root->val_nr && cursor->pos == cursor->nr) {
 513                 root->hit += period;
 514                 return 0;
 515         }
 516
 517         /* We match the node and still have a part remaining */
 518         append_chain_children(root, cursor, period);
 519
 520         return 0;
 521 }
 522
 523 int callchain_append(struct callchain_root *root,
 524                      struct callchain_cursor *cursor,
 525                      u64 period)
 526 {
 527         if (!cursor->nr)
 528                 return 0;
 529
 530         callchain_cursor_commit(cursor);
 531
 532         append_chain_children(&root->node, cursor, period);
 533
 534         if (cursor->nr > root->max_depth)
 535                 root->max_depth = cursor->nr;
 536
 537         return 0;
 538 }
 539
 540 static int
 541 merge_chain_branch(struct callchain_cursor *cursor,
 542                    struct callchain_node *dst, struct callchain_node *src)
 543 {
 544         struct callchain_cursor_node **old_last = cursor->last;
 545         struct callchain_node *child;
 546         struct callchain_list *list, *next_list;
 547         struct rb_node *n;
 548         int old_pos = cursor->nr;
 549         int err = 0;
 550
 551         list_for_each_entry_safe(list, next_list, &src->val, list) {
 552                 callchain_cursor_append(cursor, list->ip,
 553                                         list->ms.map, list->ms.sym);
 554                 list_del(&list->list);
 555                 free(list);
 556         }
 557
 558         if (src->hit) {
 559                 callchain_cursor_commit(cursor);
 560                 append_chain_children(dst, cursor, src->hit);
 561         }
 562
 563         n = rb_first(&src->rb_root_in);
 564         while (n) {
 565                 child = container_of(n, struct callchain_node, rb_node_in);
 566                 n = rb_next(n);
 567                 rb_erase(&child->rb_node_in, &src->rb_root_in);
 568
 569                 err = merge_chain_branch(cursor, dst, child);
 570                 if (err)
 571                         break;
 572
 573                 free(child);
 574         }
 575
 576         cursor->nr = old_pos;
 577         cursor->last = old_last;
 578
 579         return err;
 580 }
 581
 582 int callchain_merge(struct callchain_cursor *cursor,
 583                     struct callchain_root *dst, struct callchain_root *src)
 584 {
 585         return merge_chain_branch(cursor, &dst->node, &src->node);
 586 }
 587
 588 int callchain_cursor_append(struct callchain_cursor *cursor,
 589                             u64 ip, struct map *map, struct symbol *sym)
 590 {
 591         struct callchain_cursor_node *node = *cursor->last;
 592
 593         if (!node) {
 594                 node = calloc(1, sizeof(*node));
 595                 if (!node)
 596                         return -ENOMEM;
 597
 598                 *cursor->last = node;
 599         }
 600
 601         node->ip = ip;
 602         node->map = map;
 603         node->sym = sym;
 604
 605         cursor->nr++;
 606
 607         cursor->last = &node->next;
 608
 609         return 0;
 610 }
 611
 612 int sample__resolve_callchain(struct perf_sample *sample, struct symbol **parent,
 613                               struct perf_evsel *evsel, struct addr_location *al,
 614                               int max_stack)
 615 {
 616         if (sample->callchain == NULL)
 617                 return 0;
 618
 619         if (symbol_conf.use_callchain || symbol_conf.cumulate_callchain ||
 620             sort__has_parent) {
 621                 return machine__resolve_callchain(al->machine, evsel, al->thread,
 622                                                   sample, parent, al, max_stack);
 623         }
 624         return 0;
 625 }
 626
 627 int hist_entry__append_callchain(struct hist_entry *he, struct perf_sample *sample)
 628 {
 629         if (!symbol_conf.use_callchain)
 630                 return 0;
 631         return callchain_append(he->callchain, &callchain_cursor, sample->period);
 632 }
 633
 634 int fill_callchain_info(struct addr_location *al, struct callchain_cursor_node *node,
 635                         bool hide_unresolved)
 636 {
 637         al->map = node->map;
 638         al->sym = node->sym;
 639         if (node->map)
 640                 al->addr = node->map->map_ip(node->map, node->ip);
 641         else
 642                 al->addr = node->ip;
 643
 644         if (al->sym == NULL) {
 645                 if (hide_unresolved)
 646                         return 0;
 647                 if (al->map == NULL)
 648                         goto out;
 649         }
 650
 651         if (al->map->groups == &al->machine->kmaps) {
 652                 if (machine__is_host(al->machine)) {
 653                         al->cpumode = PERF_RECORD_MISC_KERNEL;
 654                         al->level = 'k';
 655                 } else {
 656                         al->cpumode = PERF_RECORD_MISC_GUEST_KERNEL;
 657                         al->level = 'g';
 658                 }
 659         } else {
 660                 if (machine__is_host(al->machine)) {
 661                         al->cpumode = PERF_RECORD_MISC_USER;
 662                         al->level = '.';
 663                 } else if (perf_guest) {
 664                         al->cpumode = PERF_RECORD_MISC_GUEST_USER;
 665                         al->level = 'u';
 666                 } else {
 667                         al->cpumode = PERF_RECORD_MISC_HYPERVISOR;
 668                         al->level = 'H';
 669                 }
 670         }
 671
 672 out:
 673         return 1;
 674 }