2 * Copyright (C) 2009-2011, Frederic Weisbecker <fweisbec@gmail.com>
4 * Handle the callchains from the stream in an ad-hoc radix tree and then
5 * sort them in an rbtree.
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.
20 #include "callchain.h"
22 __thread struct callchain_cursor callchain_cursor;
25 rb_insert_callchain(struct rb_root *root, struct callchain_node *chain,
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);
37 rnode = rb_entry(parent, struct callchain_node, rb_node);
38 rnode_cumul = callchain_cumul_hits(rnode);
42 if (rnode->hit < chain->hit)
47 case CHAIN_GRAPH_ABS: /* Falldown */
49 if (rnode_cumul < chain_cumul)
60 rb_link_node(&chain->rb_node, parent, p);
61 rb_insert_color(&chain->rb_node, root);
65 __sort_chain_flat(struct rb_root *rb_root, struct callchain_node *node,
69 struct callchain_node *child;
71 n = rb_first(&node->rb_root_in);
73 child = rb_entry(n, struct callchain_node, rb_node_in);
76 __sort_chain_flat(rb_root, child, min_hit);
79 if (node->hit && node->hit >= min_hit)
80 rb_insert_callchain(rb_root, node, CHAIN_FLAT);
84 * Once we get every callchains from the stream, we can now
88 sort_chain_flat(struct rb_root *rb_root, struct callchain_root *root,
89 u64 min_hit, struct callchain_param *param __maybe_unused)
91 __sort_chain_flat(rb_root, &root->node, min_hit);
94 static void __sort_chain_graph_abs(struct callchain_node *node,
98 struct callchain_node *child;
100 node->rb_root = RB_ROOT;
101 n = rb_first(&node->rb_root_in);
104 child = rb_entry(n, struct callchain_node, rb_node_in);
107 __sort_chain_graph_abs(child, min_hit);
108 if (callchain_cumul_hits(child) >= min_hit)
109 rb_insert_callchain(&node->rb_root, child,
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)
118 __sort_chain_graph_abs(&chain_root->node, min_hit);
119 rb_root->rb_node = chain_root->node.rb_root.rb_node;
122 static void __sort_chain_graph_rel(struct callchain_node *node,
126 struct callchain_node *child;
129 node->rb_root = RB_ROOT;
130 min_hit = ceil(node->children_hit * min_percent);
132 n = rb_first(&node->rb_root_in);
134 child = rb_entry(n, struct callchain_node, rb_node_in);
137 __sort_chain_graph_rel(child, min_percent);
138 if (callchain_cumul_hits(child) >= min_hit)
139 rb_insert_callchain(&node->rb_root, child,
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)
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;
152 int callchain_register_param(struct callchain_param *param)
154 switch (param->mode) {
155 case CHAIN_GRAPH_ABS:
156 param->sort = sort_chain_graph_abs;
158 case CHAIN_GRAPH_REL:
159 param->sort = sort_chain_graph_rel;
162 param->sort = sort_chain_flat;
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
175 static struct callchain_node *
176 create_child(struct callchain_node *parent, bool inherit_children)
178 struct callchain_node *new;
180 new = zalloc(sizeof(*new));
182 perror("not enough memory to create child for code path tree");
185 new->parent = parent;
186 INIT_LIST_HEAD(&new->val);
188 if (inherit_children) {
190 struct callchain_node *child;
192 new->rb_root_in = parent->rb_root_in;
193 parent->rb_root_in = RB_ROOT;
195 n = rb_first(&new->rb_root_in);
197 child = rb_entry(n, struct callchain_node, rb_node_in);
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);
212 * Fill the node with callchain values
215 fill_node(struct callchain_node *node, struct callchain_cursor *cursor)
217 struct callchain_cursor_node *cursor_node;
219 node->val_nr = cursor->nr - cursor->pos;
221 pr_warning("Warning: empty node in callchain tree\n");
223 cursor_node = callchain_cursor_current(cursor);
225 while (cursor_node) {
226 struct callchain_list *call;
228 call = zalloc(sizeof(*call));
230 perror("not enough memory for the code path tree");
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);
238 callchain_cursor_advance(cursor);
239 cursor_node = callchain_cursor_current(cursor);
243 static struct callchain_node *
244 add_child(struct callchain_node *parent,
245 struct callchain_cursor *cursor,
248 struct callchain_node *new;
250 new = create_child(parent, false);
251 fill_node(new, cursor);
253 new->children_hit = 0;
258 static s64 match_chain(struct callchain_cursor_node *node,
259 struct callchain_list *cnode)
261 struct symbol *sym = node->sym;
263 if (cnode->ms.sym && sym &&
264 callchain_param.key == CCKEY_FUNCTION)
265 return cnode->ms.sym->start - sym->start;
267 return cnode->ip - node->ip;
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
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)
281 struct callchain_node *new;
282 struct list_head *old_tail;
283 unsigned int idx_total = idx_parents + idx_local;
286 new = create_child(parent, true);
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;
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;
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;
311 parent->children_hit += period;
313 node = callchain_cursor_current(cursor);
314 new = add_child(parent, cursor, period);
317 * This is second child since we moved parent's children
318 * to new (first) child above.
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,
325 if (match_chain(node, cnode) < 0)
330 rb_link_node(&new->rb_node_in, p, pp);
331 rb_insert_color(&new->rb_node_in, &parent->rb_root_in);
333 parent->hit = period;
338 append_chain(struct callchain_node *root,
339 struct callchain_cursor *cursor,
343 append_chain_children(struct callchain_node *root,
344 struct callchain_cursor *cursor,
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;
352 node = callchain_cursor_current(cursor);
356 /* lookup in childrens */
359 struct callchain_list *cnode;
362 rnode = rb_entry(parent, struct callchain_node, rb_node_in);
363 cnode = list_first_entry(&rnode->val, struct callchain_list,
366 /* just check first entry */
367 ret = match_chain(node, cnode);
369 append_chain(rnode, cursor, period);
370 goto inc_children_hit;
374 p = &parent->rb_left;
376 p = &parent->rb_right;
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);
384 root->children_hit += period;
388 append_chain(struct callchain_node *root,
389 struct callchain_cursor *cursor,
392 struct callchain_cursor_node *curr_snap = cursor->curr;
393 struct callchain_list *cnode;
394 u64 start = cursor->pos;
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
404 list_for_each_entry(cnode, &root->val, list) {
405 struct callchain_cursor_node *node;
407 node = callchain_cursor_current(cursor);
411 if (match_chain(node, cnode) != 0)
416 callchain_cursor_advance(cursor);
419 /* matches not, relay no the parent */
421 cursor->curr = curr_snap;
426 matches = cursor->pos - start;
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);
434 /* we match 100% of the path, increment the hit */
435 if (matches == root->val_nr && cursor->pos == cursor->nr) {
440 /* We match the node and still have a part remaining */
441 append_chain_children(root, cursor, period);
446 int callchain_append(struct callchain_root *root,
447 struct callchain_cursor *cursor,
453 callchain_cursor_commit(cursor);
455 append_chain_children(&root->node, cursor, period);
457 if (cursor->nr > root->max_depth)
458 root->max_depth = cursor->nr;
464 merge_chain_branch(struct callchain_cursor *cursor,
465 struct callchain_node *dst, struct callchain_node *src)
467 struct callchain_cursor_node **old_last = cursor->last;
468 struct callchain_node *child;
469 struct callchain_list *list, *next_list;
471 int old_pos = cursor->nr;
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);
482 callchain_cursor_commit(cursor);
483 append_chain_children(dst, cursor, src->hit);
486 n = rb_first(&src->rb_root_in);
488 child = container_of(n, struct callchain_node, rb_node_in);
490 rb_erase(&child->rb_node_in, &src->rb_root_in);
492 err = merge_chain_branch(cursor, dst, child);
499 cursor->nr = old_pos;
500 cursor->last = old_last;
505 int callchain_merge(struct callchain_cursor *cursor,
506 struct callchain_root *dst, struct callchain_root *src)
508 return merge_chain_branch(cursor, &dst->node, &src->node);
511 int callchain_cursor_append(struct callchain_cursor *cursor,
512 u64 ip, struct map *map, struct symbol *sym)
514 struct callchain_cursor_node *node = *cursor->last;
517 node = calloc(1, sizeof(*node));
521 *cursor->last = node;
530 cursor->last = &node->next;