SAFE public projects git trees. - safe/jmp/linux-2.6/blob - 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 FLAT:
  36                         if (rnode->hit < chain->hit)
  37                                 p = &(*p)->rb_left;
  38                         else
  39                                 p = &(*p)->rb_right;
  40                         break;
  41                 case GRAPH:
  42                         if (rnode->cumul_hit < chain->cumul_hit)
  43                                 p = &(*p)->rb_left;
  44                         else
  45                                 p = &(*p)->rb_right;
  46                         break;
  47                 default:
  48                         break;
  49                 }
  50         }
  51
  52         rb_link_node(&chain->rb_node, parent, p);
  53         rb_insert_color(&chain->rb_node, root);
  54 }
  55
  56 /*
  57  * Once we get every callchains from the stream, we can now
  58  * sort them by hit
  59  */
  60 void sort_chain_flat(struct rb_root *rb_root, struct callchain_node *node,
  61                      u64 min_hit)
  62 {
  63         struct callchain_node *child;
  64
  65         chain_for_each_child(child, node)
  66                 sort_chain_flat(rb_root, child, min_hit);
  67
  68         if (node->hit && node->hit >= min_hit)
  69                 rb_insert_callchain(rb_root, node, FLAT);
  70 }
  71
  72 static void __sort_chain_graph(struct callchain_node *node, u64 min_hit)
  73 {
  74         struct callchain_node *child;
  75
  76         node->rb_root = RB_ROOT;
  77         node->cumul_hit = node->hit;
  78
  79         chain_for_each_child(child, node) {
  80                 __sort_chain_graph(child, min_hit);
  81                 if (child->cumul_hit >= min_hit)
  82                         rb_insert_callchain(&node->rb_root, child, GRAPH);
  83                 node->cumul_hit += child->cumul_hit;
  84         }
  85 }
  86
  87 void
  88 sort_chain_graph(struct rb_root *rb_root, struct callchain_node *chain_root,
  89                  u64 min_hit)
  90 {
  91         __sort_chain_graph(chain_root, min_hit);
  92         rb_root->rb_node = chain_root->rb_root.rb_node;
  93 }
  94
  95 /*
  96  * Create a child for a parent. If inherit_children, then the new child
  97  * will become the new parent of it's parent children
  98  */
  99 static struct callchain_node *
 100 create_child(struct callchain_node *parent, bool inherit_children)
 101 {
 102         struct callchain_node *new;
 103
 104         new = malloc(sizeof(*new));
 105         if (!new) {
 106                 perror("not enough memory to create child for code path tree");
 107                 return NULL;
 108         }
 109         new->parent = parent;
 110         INIT_LIST_HEAD(&new->children);
 111         INIT_LIST_HEAD(&new->val);
 112
 113         if (inherit_children) {
 114                 struct callchain_node *next;
 115
 116                 list_splice(&parent->children, &new->children);
 117                 INIT_LIST_HEAD(&parent->children);
 118
 119                 chain_for_each_child(next, new)
 120                         next->parent = new;
 121         }
 122         list_add_tail(&new->brothers, &parent->children);
 123
 124         return new;
 125 }
 126
 127 /*
 128  * Fill the node with callchain values
 129  */
 130 static void
 131 fill_node(struct callchain_node *node, struct ip_callchain *chain,
 132           int start, struct symbol **syms)
 133 {
 134         unsigned int i;
 135
 136         for (i = start; i < chain->nr; i++) {
 137                 struct callchain_list *call;
 138
 139                 call = malloc(sizeof(*call));
 140                 if (!call) {
 141                         perror("not enough memory for the code path tree");
 142                         return;
 143                 }
 144                 call->ip = chain->ips[i];
 145                 call->sym = syms[i];
 146                 list_add_tail(&call->list, &node->val);
 147         }
 148         node->val_nr = chain->nr - start;
 149         if (!node->val_nr)
 150                 printf("Warning: empty node in callchain tree\n");
 151 }
 152
 153 static void
 154 add_child(struct callchain_node *parent, struct ip_callchain *chain,
 155           int start, struct symbol **syms)
 156 {
 157         struct callchain_node *new;
 158
 159         new = create_child(parent, false);
 160         fill_node(new, chain, start, syms);
 161
 162         new->hit = 1;
 163 }
 164
 165 /*
 166  * Split the parent in two parts (a new child is created) and
 167  * give a part of its callchain to the created child.
 168  * Then create another child to host the given callchain of new branch
 169  */
 170 static void
 171 split_add_child(struct callchain_node *parent, struct ip_callchain *chain,
 172                 struct callchain_list *to_split, int idx_parents, int idx_local,
 173                 struct symbol **syms)
 174 {
 175         struct callchain_node *new;
 176         struct list_head *old_tail;
 177         unsigned int idx_total = idx_parents + idx_local;
 178
 179         /* split */
 180         new = create_child(parent, true);
 181
 182         /* split the callchain and move a part to the new child */
 183         old_tail = parent->val.prev;
 184         list_del_range(&to_split->list, old_tail);
 185         new->val.next = &to_split->list;
 186         new->val.prev = old_tail;
 187         to_split->list.prev = &new->val;
 188         old_tail->next = &new->val;
 189
 190         /* split the hits */
 191         new->hit = parent->hit;
 192         new->val_nr = parent->val_nr - idx_local;
 193         parent->val_nr = idx_local;
 194
 195         /* create a new child for the new branch if any */
 196         if (idx_total < chain->nr) {
 197                 parent->hit = 0;
 198                 add_child(parent, chain, idx_total, syms);
 199         } else {
 200                 parent->hit = 1;
 201         }
 202 }
 203
 204 static int
 205 __append_chain(struct callchain_node *root, struct ip_callchain *chain,
 206                unsigned int start, struct symbol **syms);
 207
 208 static void
 209 __append_chain_children(struct callchain_node *root, struct ip_callchain *chain,
 210                         struct symbol **syms, unsigned int start)
 211 {
 212         struct callchain_node *rnode;
 213
 214         /* lookup in childrens */
 215         chain_for_each_child(rnode, root) {
 216                 unsigned int ret = __append_chain(rnode, chain, start, syms);
 217
 218                 if (!ret)
 219                         return;
 220         }
 221         /* nothing in children, add to the current node */
 222         add_child(root, chain, start, syms);
 223 }
 224
 225 static int
 226 __append_chain(struct callchain_node *root, struct ip_callchain *chain,
 227                unsigned int start, struct symbol **syms)
 228 {
 229         struct callchain_list *cnode;
 230         unsigned int i = start;
 231         bool found = false;
 232
 233         /*
 234          * Lookup in the current node
 235          * If we have a symbol, then compare the start to match
 236          * anywhere inside a function.
 237          */
 238         list_for_each_entry(cnode, &root->val, list) {
 239                 if (i == chain->nr)
 240                         break;
 241                 if (cnode->sym && syms[i]) {
 242                         if (cnode->sym->start != syms[i]->start)
 243                                 break;
 244                 } else if (cnode->ip != chain->ips[i])
 245                         break;
 246                 if (!found)
 247                         found = true;
 248                 i++;
 249         }
 250
 251         /* matches not, relay on the parent */
 252         if (!found)
 253                 return -1;
 254
 255         /* we match only a part of the node. Split it and add the new chain */
 256         if (i - start < root->val_nr) {
 257                 split_add_child(root, chain, cnode, start, i - start, syms);
 258                 return 0;
 259         }
 260
 261         /* we match 100% of the path, increment the hit */
 262         if (i - start == root->val_nr && i == chain->nr) {
 263                 root->hit++;
 264                 return 0;
 265         }
 266
 267         /* We match the node and still have a part remaining */
 268         __append_chain_children(root, chain, syms, i);
 269
 270         return 0;
 271 }
 272
 273 void append_chain(struct callchain_node *root, struct ip_callchain *chain,
 274                   struct symbol **syms)
 275 {
 276         __append_chain_children(root, chain, syms, 0);
 277 }