tools/perf/util/callchain.c

   1 /*
   2  * Copyright (C) 2009, 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
  17 #include "callchain.h"
  18
  19 #define chain_for_each_child(child, parent)     \
  20         list_for_each_entry(child, &parent->children, brothers)
  21
  22 static void
  23 rb_insert_callchain(struct rb_root *root, struct callchain_node *chain,
  24                     enum chain_mode mode)
  25 {
  26         struct rb_node **p = &root->rb_node;
  27         struct rb_node *parent = NULL;
  28         struct callchain_node *rnode;
  29
  30         while (*p) {
  31                 parent = *p;
  32                 rnode = rb_entry(parent, struct callchain_node, rb_node);
  33
  34                 switch (mode) {
  35                 case CHAIN_FLAT:
  36                         if (rnode->hit < chain->hit)
  37                                 p = &(*p)->rb_left;
  38                         else
  39                                 p = &(*p)->rb_right;
  40                         break;
  41                 case CHAIN_GRAPH_ABS: /* Falldown */
  42                 case CHAIN_GRAPH_REL:
  43                         if (rnode->cumul_hit < chain->cumul_hit)
  44                                 p = &(*p)->rb_left;
  45                         else
  46                                 p = &(*p)->rb_right;
  47                         break;
  48                 default:
  49                         break;
  50                 }
  51         }
  52
  53         rb_link_node(&chain->rb_node, parent, p);
  54         rb_insert_color(&chain->rb_node, root);
  55 }
  56
  57 static void
  58 __sort_chain_flat(struct rb_root *rb_root, struct callchain_node *node,
  59                   u64 min_hit)
  60 {
  61         struct callchain_node *child;
  62
  63         chain_for_each_child(child, node)
  64                 __sort_chain_flat(rb_root, child, min_hit);
  65
  66         if (node->hit && node->hit >= min_hit)
  67                 rb_insert_callchain(rb_root, node, CHAIN_FLAT);
  68 }
  69
  70 /*
  71  * Once we get every callchains from the stream, we can now
  72  * sort them by hit
  73  */
  74 static void
  75 sort_chain_flat(struct rb_root *rb_root, struct callchain_node *node,
  76                 u64 min_hit, struct callchain_param *param __used)
  77 {
  78         __sort_chain_flat(rb_root, node, min_hit);
  79 }
  80
  81 static void __sort_chain_graph_abs(struct callchain_node *node,
  82                                    u64 min_hit)
  83 {
  84         struct callchain_node *child;
  85
  86         node->rb_root = RB_ROOT;
  87
  88         chain_for_each_child(child, node) {
  89                 __sort_chain_graph_abs(child, min_hit);
  90                 if (child->cumul_hit >= min_hit)
  91                         rb_insert_callchain(&node->rb_root, child,
  92                                             CHAIN_GRAPH_ABS);
  93         }
  94 }
  95
  96 static void
  97 sort_chain_graph_abs(struct rb_root *rb_root, struct callchain_node *chain_root,
  98                      u64 min_hit, struct callchain_param *param __used)
  99 {
 100         __sort_chain_graph_abs(chain_root, min_hit);
 101         rb_root->rb_node = chain_root->rb_root.rb_node;
 102 }
 103
 104 static void __sort_chain_graph_rel(struct callchain_node *node,
 105                                    double min_percent)
 106 {
 107         struct callchain_node *child;
 108         u64 min_hit;
 109
 110         node->rb_root = RB_ROOT;
 111         min_hit = node->cumul_hit * min_percent / 100.0;
 112
 113         chain_for_each_child(child, node) {
 114                 __sort_chain_graph_rel(child, min_percent);
 115                 if (child->cumul_hit >= min_hit)
 116                         rb_insert_callchain(&node->rb_root, child,
 117                                             CHAIN_GRAPH_REL);
 118         }
 119 }
 120
 121 static void
 122 sort_chain_graph_rel(struct rb_root *rb_root, struct callchain_node *chain_root,
 123                      u64 min_hit __used, struct callchain_param *param)
 124 {
 125         __sort_chain_graph_rel(chain_root, param->min_percent);
 126         rb_root->rb_node = chain_root->rb_root.rb_node;
 127 }
 128
 129 int register_callchain_param(struct callchain_param *param)
 130 {
 131         switch (param->mode) {
 132         case CHAIN_GRAPH_ABS:
 133                 param->sort = sort_chain_graph_abs;
 134                 break;
 135         case CHAIN_GRAPH_REL:
 136                 param->sort = sort_chain_graph_rel;
 137                 break;
 138         case CHAIN_FLAT:
 139                 param->sort = sort_chain_flat;
 140                 break;
 141         default:
 142                 return -1;
 143         }
 144         return 0;
 145 }
 146
 147 /*
 148  * Create a child for a parent. If inherit_children, then the new child
 149  * will become the new parent of it's parent children
 150  */
 151 static struct callchain_node *
 152 create_child(struct callchain_node *parent, bool inherit_children)
 153 {
 154         struct callchain_node *new;
 155
 156         new = malloc(sizeof(*new));
 157         if (!new) {
 158                 perror("not enough memory to create child for code path tree");
 159                 return NULL;
 160         }
 161         new->parent = parent;
 162         INIT_LIST_HEAD(&new->children);
 163         INIT_LIST_HEAD(&new->val);
 164
 165         if (inherit_children) {
 166                 struct callchain_node *next;
 167
 168                 list_splice(&parent->children, &new->children);
 169                 INIT_LIST_HEAD(&parent->children);
 170
 171                 chain_for_each_child(next, new)
 172                         next->parent = new;
 173         }
 174         list_add_tail(&new->brothers, &parent->children);
 175
 176         return new;
 177 }
 178
 179 /*
 180  * Fill the node with callchain values
 181  */
 182 static void
 183 fill_node(struct callchain_node *node, struct ip_callchain *chain,
 184           int start, struct symbol **syms)
 185 {
 186         unsigned int i;
 187
 188         for (i = start; i < chain->nr; i++) {
 189                 struct callchain_list *call;
 190
 191                 call = malloc(sizeof(*call));
 192                 if (!call) {
 193                         perror("not enough memory for the code path tree");
 194                         return;
 195                 }
 196                 call->ip = chain->ips[i];
 197                 call->sym = syms[i];
 198                 list_add_tail(&call->list, &node->val);
 199         }
 200         node->val_nr = chain->nr - start;
 201         if (!node->val_nr)
 202                 printf("Warning: empty node in callchain tree\n");
 203 }
 204
 205 static void
 206 add_child(struct callchain_node *parent, struct ip_callchain *chain,
 207           int start, struct symbol **syms)
 208 {
 209         struct callchain_node *new;
 210
 211         new = create_child(parent, false);
 212         fill_node(new, chain, start, syms);
 213
 214         new->cumul_hit = new->hit = 1;
 215 }
 216
 217 /*
 218  * Split the parent in two parts (a new child is created) and
 219  * give a part of its callchain to the created child.
 220  * Then create another child to host the given callchain of new branch
 221  */
 222 static void
 223 split_add_child(struct callchain_node *parent, struct ip_callchain *chain,
 224                 struct callchain_list *to_split, int idx_parents, int idx_local,
 225                 struct symbol **syms)
 226 {
 227         struct callchain_node *new;
 228         struct list_head *old_tail;
 229         unsigned int idx_total = idx_parents + idx_local;
 230
 231         /* split */
 232         new = create_child(parent, true);
 233
 234         /* split the callchain and move a part to the new child */
 235         old_tail = parent->val.prev;
 236         list_del_range(&to_split->list, old_tail);
 237         new->val.next = &to_split->list;
 238         new->val.prev = old_tail;
 239         to_split->list.prev = &new->val;
 240         old_tail->next = &new->val;
 241
 242         /* split the hits */
 243         new->hit = parent->hit;
 244         new->cumul_hit = parent->cumul_hit;
 245         new->val_nr = parent->val_nr - idx_local;
 246         parent->val_nr = idx_local;
 247
 248         /* create a new child for the new branch if any */
 249         if (idx_total < chain->nr) {
 250                 parent->hit = 0;
 251                 add_child(parent, chain, idx_total, syms);
 252         } else {
 253                 parent->hit = 1;
 254         }
 255 }
 256
 257 static int
 258 __append_chain(struct callchain_node *root, struct ip_callchain *chain,
 259                unsigned int start, struct symbol **syms);
 260
 261 static void
 262 __append_chain_children(struct callchain_node *root, struct ip_callchain *chain,
 263                         struct symbol **syms, unsigned int start)
 264 {
 265         struct callchain_node *rnode;
 266
 267         /* lookup in childrens */
 268         chain_for_each_child(rnode, root) {
 269                 unsigned int ret = __append_chain(rnode, chain, start, syms);
 270
 271                 if (!ret)
 272                         goto cumul;
 273         }
 274         /* nothing in children, add to the current node */
 275         add_child(root, chain, start, syms);
 276
 277 cumul:
 278         root->cumul_hit++;
 279 }
 280
 281 static int
 282 __append_chain(struct callchain_node *root, struct ip_callchain *chain,
 283                unsigned int start, struct symbol **syms)
 284 {
 285         struct callchain_list *cnode;
 286         unsigned int i = start;
 287         bool found = false;
 288
 289         /*
 290          * Lookup in the current node
 291          * If we have a symbol, then compare the start to match
 292          * anywhere inside a function.
 293          */
 294         list_for_each_entry(cnode, &root->val, list) {
 295                 if (i == chain->nr)
 296                         break;
 297                 if (cnode->sym && syms[i]) {
 298                         if (cnode->sym->start != syms[i]->start)
 299                                 break;
 300                 } else if (cnode->ip != chain->ips[i])
 301                         break;
 302                 if (!found)
 303                         found = true;
 304                 i++;
 305         }
 306
 307         /* matches not, relay on the parent */
 308         if (!found)
 309                 return -1;
 310
 311         /* we match only a part of the node. Split it and add the new chain */
 312         if (i - start < root->val_nr) {
 313                 split_add_child(root, chain, cnode, start, i - start, syms);
 314                 return 0;
 315         }
 316
 317         /* we match 100% of the path, increment the hit */
 318         if (i - start == root->val_nr && i == chain->nr) {
 319                 root->hit++;
 320                 root->cumul_hit++;
 321
 322                 return 0;
 323         }
 324
 325         /* We match the node and still have a part remaining */
 326         __append_chain_children(root, chain, syms, i);
 327
 328         return 0;
 329 }
 330
 331 void append_chain(struct callchain_node *root, struct ip_callchain *chain,
 332                   struct symbol **syms)
 333 {
 334         __append_chain_children(root, chain, syms, 0);
 335 }