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