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