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