Linux Kernel  3.7.1
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
callchain.c
Go to the documentation of this file.
1 /*
2  * Copyright (C) 2009-2011, Frederic Weisbecker <[email protected]>
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 
22 
24  const union perf_event *event)
25 {
26  unsigned int chain_size = event->header.size;
27  chain_size -= (unsigned long)&event->ip.__more_data - (unsigned long)event;
28  return chain->nr * sizeof(u64) <= chain_size;
29 }
30 
31 #define chain_for_each_child(child, parent) \
32  list_for_each_entry(child, &parent->children, siblings)
33 
34 #define chain_for_each_child_safe(child, next, parent) \
35  list_for_each_entry_safe(child, next, &parent->children, siblings)
36 
37 static void
38 rb_insert_callchain(struct rb_root *root, struct callchain_node *chain,
39  enum chain_mode mode)
40 {
41  struct rb_node **p = &root->rb_node;
42  struct rb_node *parent = NULL;
43  struct callchain_node *rnode;
44  u64 chain_cumul = callchain_cumul_hits(chain);
45 
46  while (*p) {
47  u64 rnode_cumul;
48 
49  parent = *p;
50  rnode = rb_entry(parent, struct callchain_node, rb_node);
51  rnode_cumul = callchain_cumul_hits(rnode);
52 
53  switch (mode) {
54  case CHAIN_FLAT:
55  if (rnode->hit < chain->hit)
56  p = &(*p)->rb_left;
57  else
58  p = &(*p)->rb_right;
59  break;
60  case CHAIN_GRAPH_ABS: /* Falldown */
61  case CHAIN_GRAPH_REL:
62  if (rnode_cumul < chain_cumul)
63  p = &(*p)->rb_left;
64  else
65  p = &(*p)->rb_right;
66  break;
67  case CHAIN_NONE:
68  default:
69  break;
70  }
71  }
72 
73  rb_link_node(&chain->rb_node, parent, p);
74  rb_insert_color(&chain->rb_node, root);
75 }
76 
77 static void
78 __sort_chain_flat(struct rb_root *rb_root, struct callchain_node *node,
79  u64 min_hit)
80 {
81  struct callchain_node *child;
82 
83  chain_for_each_child(child, node)
84  __sort_chain_flat(rb_root, child, min_hit);
85 
86  if (node->hit && node->hit >= min_hit)
87  rb_insert_callchain(rb_root, node, CHAIN_FLAT);
88 }
89 
90 /*
91  * Once we get every callchains from the stream, we can now
92  * sort them by hit
93  */
94 static void
95 sort_chain_flat(struct rb_root *rb_root, struct callchain_root *root,
97 {
98  __sort_chain_flat(rb_root, &root->node, min_hit);
99 }
100 
101 static void __sort_chain_graph_abs(struct callchain_node *node,
102  u64 min_hit)
103 {
104  struct callchain_node *child;
105 
106  node->rb_root = RB_ROOT;
107 
108  chain_for_each_child(child, node) {
109  __sort_chain_graph_abs(child, min_hit);
110  if (callchain_cumul_hits(child) >= min_hit)
111  rb_insert_callchain(&node->rb_root, child,
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 callchain_node *child;
128  u64 min_hit;
129 
130  node->rb_root = RB_ROOT;
131  min_hit = ceil(node->children_hit * min_percent);
132 
133  chain_for_each_child(child, node) {
134  __sort_chain_graph_rel(child, min_percent);
135  if (callchain_cumul_hits(child) >= min_hit)
136  rb_insert_callchain(&node->rb_root, child,
138  }
139 }
140 
141 static void
142 sort_chain_graph_rel(struct rb_root *rb_root, struct callchain_root *chain_root,
143  u64 min_hit __maybe_unused, struct callchain_param *param)
144 {
145  __sort_chain_graph_rel(&chain_root->node, param->min_percent / 100.0);
146  rb_root->rb_node = chain_root->node.rb_root.rb_node;
147 }
148 
150 {
151  switch (param->mode) {
152  case CHAIN_GRAPH_ABS:
153  param->sort = sort_chain_graph_abs;
154  break;
155  case CHAIN_GRAPH_REL:
156  param->sort = sort_chain_graph_rel;
157  break;
158  case CHAIN_FLAT:
159  param->sort = sort_chain_flat;
160  break;
161  case CHAIN_NONE:
162  default:
163  return -1;
164  }
165  return 0;
166 }
167 
168 /*
169  * Create a child for a parent. If inherit_children, then the new child
170  * will become the new parent of it's parent children
171  */
172 static struct callchain_node *
173 create_child(struct callchain_node *parent, bool inherit_children)
174 {
175  struct callchain_node *new;
176 
177  new = zalloc(sizeof(*new));
178  if (!new) {
179  perror("not enough memory to create child for code path tree");
180  return NULL;
181  }
182  new->parent = parent;
183  INIT_LIST_HEAD(&new->children);
184  INIT_LIST_HEAD(&new->val);
185 
186  if (inherit_children) {
187  struct callchain_node *next;
188 
189  list_splice(&parent->children, &new->children);
190  INIT_LIST_HEAD(&parent->children);
191 
192  chain_for_each_child(next, new)
193  next->parent = new;
194  }
195  list_add_tail(&new->siblings, &parent->children);
196 
197  return new;
198 }
199 
200 
201 /*
202  * Fill the node with callchain values
203  */
204 static void
205 fill_node(struct callchain_node *node, struct callchain_cursor *cursor)
206 {
207  struct callchain_cursor_node *cursor_node;
208 
209  node->val_nr = cursor->nr - cursor->pos;
210  if (!node->val_nr)
211  pr_warning("Warning: empty node in callchain tree\n");
212 
213  cursor_node = callchain_cursor_current(cursor);
214 
215  while (cursor_node) {
216  struct callchain_list *call;
217 
218  call = zalloc(sizeof(*call));
219  if (!call) {
220  perror("not enough memory for the code path tree");
221  return;
222  }
223  call->ip = cursor_node->ip;
224  call->ms.sym = cursor_node->sym;
225  call->ms.map = cursor_node->map;
226  list_add_tail(&call->list, &node->val);
227 
228  callchain_cursor_advance(cursor);
229  cursor_node = callchain_cursor_current(cursor);
230  }
231 }
232 
233 static void
234 add_child(struct callchain_node *parent,
235  struct callchain_cursor *cursor,
236  u64 period)
237 {
238  struct callchain_node *new;
239 
240  new = create_child(parent, false);
241  fill_node(new, cursor);
242 
243  new->children_hit = 0;
244  new->hit = period;
245 }
246 
247 /*
248  * Split the parent in two parts (a new child is created) and
249  * give a part of its callchain to the created child.
250  * Then create another child to host the given callchain of new branch
251  */
252 static void
253 split_add_child(struct callchain_node *parent,
254  struct callchain_cursor *cursor,
255  struct callchain_list *to_split,
256  u64 idx_parents, u64 idx_local, u64 period)
257 {
258  struct callchain_node *new;
259  struct list_head *old_tail;
260  unsigned int idx_total = idx_parents + idx_local;
261 
262  /* split */
263  new = create_child(parent, true);
264 
265  /* split the callchain and move a part to the new child */
266  old_tail = parent->val.prev;
267  list_del_range(&to_split->list, old_tail);
268  new->val.next = &to_split->list;
269  new->val.prev = old_tail;
270  to_split->list.prev = &new->val;
271  old_tail->next = &new->val;
272 
273  /* split the hits */
274  new->hit = parent->hit;
275  new->children_hit = parent->children_hit;
276  parent->children_hit = callchain_cumul_hits(new);
277  new->val_nr = parent->val_nr - idx_local;
278  parent->val_nr = idx_local;
279 
280  /* create a new child for the new branch if any */
281  if (idx_total < cursor->nr) {
282  parent->hit = 0;
283  add_child(parent, cursor, period);
284  parent->children_hit += period;
285  } else {
286  parent->hit = period;
287  }
288 }
289 
290 static int
291 append_chain(struct callchain_node *root,
292  struct callchain_cursor *cursor,
293  u64 period);
294 
295 static void
296 append_chain_children(struct callchain_node *root,
297  struct callchain_cursor *cursor,
298  u64 period)
299 {
300  struct callchain_node *rnode;
301 
302  /* lookup in childrens */
303  chain_for_each_child(rnode, root) {
304  unsigned int ret = append_chain(rnode, cursor, period);
305 
306  if (!ret)
307  goto inc_children_hit;
308  }
309  /* nothing in children, add to the current node */
310  add_child(root, cursor, period);
311 
312 inc_children_hit:
313  root->children_hit += period;
314 }
315 
316 static int
317 append_chain(struct callchain_node *root,
318  struct callchain_cursor *cursor,
319  u64 period)
320 {
321  struct callchain_cursor_node *curr_snap = cursor->curr;
322  struct callchain_list *cnode;
323  u64 start = cursor->pos;
324  bool found = false;
325  u64 matches;
326 
327  /*
328  * Lookup in the current node
329  * If we have a symbol, then compare the start to match
330  * anywhere inside a function.
331  */
332  list_for_each_entry(cnode, &root->val, list) {
333  struct callchain_cursor_node *node;
334  struct symbol *sym;
335 
336  node = callchain_cursor_current(cursor);
337  if (!node)
338  break;
339 
340  sym = node->sym;
341 
342  if (cnode->ms.sym && sym) {
343  if (cnode->ms.sym->start != sym->start)
344  break;
345  } else if (cnode->ip != node->ip)
346  break;
347 
348  if (!found)
349  found = true;
350 
351  callchain_cursor_advance(cursor);
352  }
353 
354  /* matches not, relay on the parent */
355  if (!found) {
356  cursor->curr = curr_snap;
357  cursor->pos = start;
358  return -1;
359  }
360 
361  matches = cursor->pos - start;
362 
363  /* we match only a part of the node. Split it and add the new chain */
364  if (matches < root->val_nr) {
365  split_add_child(root, cursor, cnode, start, matches, period);
366  return 0;
367  }
368 
369  /* we match 100% of the path, increment the hit */
370  if (matches == root->val_nr && cursor->pos == cursor->nr) {
371  root->hit += period;
372  return 0;
373  }
374 
375  /* We match the node and still have a part remaining */
376  append_chain_children(root, cursor, period);
377 
378  return 0;
379 }
380 
382  struct callchain_cursor *cursor,
383  u64 period)
384 {
385  if (!cursor->nr)
386  return 0;
387 
388  callchain_cursor_commit(cursor);
389 
390  append_chain_children(&root->node, cursor, period);
391 
392  if (cursor->nr > root->max_depth)
393  root->max_depth = cursor->nr;
394 
395  return 0;
396 }
397 
398 static int
399 merge_chain_branch(struct callchain_cursor *cursor,
400  struct callchain_node *dst, struct callchain_node *src)
401 {
402  struct callchain_cursor_node **old_last = cursor->last;
403  struct callchain_node *child, *next_child;
404  struct callchain_list *list, *next_list;
405  int old_pos = cursor->nr;
406  int err = 0;
407 
408  list_for_each_entry_safe(list, next_list, &src->val, list) {
409  callchain_cursor_append(cursor, list->ip,
410  list->ms.map, list->ms.sym);
411  list_del(&list->list);
412  free(list);
413  }
414 
415  if (src->hit) {
416  callchain_cursor_commit(cursor);
417  append_chain_children(dst, cursor, src->hit);
418  }
419 
420  chain_for_each_child_safe(child, next_child, src) {
421  err = merge_chain_branch(cursor, dst, child);
422  if (err)
423  break;
424 
425  list_del(&child->siblings);
426  free(child);
427  }
428 
429  cursor->nr = old_pos;
430  cursor->last = old_last;
431 
432  return err;
433 }
434 
436  struct callchain_root *dst, struct callchain_root *src)
437 {
438  return merge_chain_branch(cursor, &dst->node, &src->node);
439 }
440 
442  u64 ip, struct map *map, struct symbol *sym)
443 {
444  struct callchain_cursor_node *node = *cursor->last;
445 
446  if (!node) {
447  node = calloc(sizeof(*node), 1);
448  if (!node)
449  return -ENOMEM;
450 
451  *cursor->last = node;
452  }
453 
454  node->ip = ip;
455  node->map = map;
456  node->sym = sym;
457 
458  cursor->nr++;
459 
460  cursor->last = &node->next;
461 
462  return 0;
463 }