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