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.
19 #include "callchain.h"
21 bool ip_callchain__valid(struct ip_callchain
*chain
, const event_t
*event
)
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
;
28 #define chain_for_each_child(child, parent) \
29 list_for_each_entry(child, &parent->children, brothers)
31 #define chain_for_each_child_safe(child, next, parent) \
32 list_for_each_entry_safe(child, next, &parent->children, brothers)
35 rb_insert_callchain(struct rb_root
*root
, struct callchain_node
*chain
,
38 struct rb_node
**p
= &root
->rb_node
;
39 struct rb_node
*parent
= NULL
;
40 struct callchain_node
*rnode
;
41 u64 chain_cumul
= cumul_hits(chain
);
47 rnode
= rb_entry(parent
, struct callchain_node
, rb_node
);
48 rnode_cumul
= cumul_hits(rnode
);
52 if (rnode
->hit
< chain
->hit
)
57 case CHAIN_GRAPH_ABS
: /* Falldown */
59 if (rnode_cumul
< chain_cumul
)
70 rb_link_node(&chain
->rb_node
, parent
, p
);
71 rb_insert_color(&chain
->rb_node
, root
);
75 __sort_chain_flat(struct rb_root
*rb_root
, struct callchain_node
*node
,
78 struct callchain_node
*child
;
80 chain_for_each_child(child
, node
)
81 __sort_chain_flat(rb_root
, child
, min_hit
);
83 if (node
->hit
&& node
->hit
>= min_hit
)
84 rb_insert_callchain(rb_root
, node
, CHAIN_FLAT
);
88 * Once we get every callchains from the stream, we can now
92 sort_chain_flat(struct rb_root
*rb_root
, struct callchain_root
*root
,
93 u64 min_hit
, struct callchain_param
*param __used
)
95 __sort_chain_flat(rb_root
, &root
->node
, min_hit
);
98 static void __sort_chain_graph_abs(struct callchain_node
*node
,
101 struct callchain_node
*child
;
103 node
->rb_root
= RB_ROOT
;
105 chain_for_each_child(child
, node
) {
106 __sort_chain_graph_abs(child
, min_hit
);
107 if (cumul_hits(child
) >= min_hit
)
108 rb_insert_callchain(&node
->rb_root
, child
,
114 sort_chain_graph_abs(struct rb_root
*rb_root
, struct callchain_root
*chain_root
,
115 u64 min_hit
, struct callchain_param
*param __used
)
117 __sort_chain_graph_abs(&chain_root
->node
, min_hit
);
118 rb_root
->rb_node
= chain_root
->node
.rb_root
.rb_node
;
121 static void __sort_chain_graph_rel(struct callchain_node
*node
,
124 struct callchain_node
*child
;
127 node
->rb_root
= RB_ROOT
;
128 min_hit
= ceil(node
->children_hit
* min_percent
);
130 chain_for_each_child(child
, node
) {
131 __sort_chain_graph_rel(child
, min_percent
);
132 if (cumul_hits(child
) >= min_hit
)
133 rb_insert_callchain(&node
->rb_root
, child
,
139 sort_chain_graph_rel(struct rb_root
*rb_root
, struct callchain_root
*chain_root
,
140 u64 min_hit __used
, struct callchain_param
*param
)
142 __sort_chain_graph_rel(&chain_root
->node
, param
->min_percent
/ 100.0);
143 rb_root
->rb_node
= chain_root
->node
.rb_root
.rb_node
;
146 int register_callchain_param(struct callchain_param
*param
)
148 switch (param
->mode
) {
149 case CHAIN_GRAPH_ABS
:
150 param
->sort
= sort_chain_graph_abs
;
152 case CHAIN_GRAPH_REL
:
153 param
->sort
= sort_chain_graph_rel
;
156 param
->sort
= sort_chain_flat
;
166 * Create a child for a parent. If inherit_children, then the new child
167 * will become the new parent of it's parent children
169 static struct callchain_node
*
170 create_child(struct callchain_node
*parent
, bool inherit_children
)
172 struct callchain_node
*new;
174 new = zalloc(sizeof(*new));
176 perror("not enough memory to create child for code path tree");
179 new->parent
= parent
;
180 INIT_LIST_HEAD(&new->children
);
181 INIT_LIST_HEAD(&new->val
);
183 if (inherit_children
) {
184 struct callchain_node
*next
;
186 list_splice(&parent
->children
, &new->children
);
187 INIT_LIST_HEAD(&parent
->children
);
189 chain_for_each_child(next
, new)
192 list_add_tail(&new->brothers
, &parent
->children
);
199 * Fill the node with callchain values
202 fill_node(struct callchain_node
*node
, struct callchain_cursor
*cursor
)
204 struct callchain_cursor_node
*cursor_node
;
206 node
->val_nr
= cursor
->nr
- cursor
->pos
;
208 pr_warning("Warning: empty node in callchain tree\n");
210 cursor_node
= callchain_cursor_current(cursor
);
212 while (cursor_node
) {
213 struct callchain_list
*call
;
215 call
= zalloc(sizeof(*call
));
217 perror("not enough memory for the code path tree");
220 call
->ip
= cursor_node
->ip
;
221 call
->ms
.sym
= cursor_node
->sym
;
222 call
->ms
.map
= cursor_node
->map
;
223 list_add_tail(&call
->list
, &node
->val
);
225 callchain_cursor_advance(cursor
);
226 cursor_node
= callchain_cursor_current(cursor
);
231 add_child(struct callchain_node
*parent
,
232 struct callchain_cursor
*cursor
,
235 struct callchain_node
*new;
237 new = create_child(parent
, false);
238 fill_node(new, cursor
);
240 new->children_hit
= 0;
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
250 split_add_child(struct callchain_node
*parent
,
251 struct callchain_cursor
*cursor
,
252 struct callchain_list
*to_split
,
253 u64 idx_parents
, u64 idx_local
, u64 period
)
255 struct callchain_node
*new;
256 struct list_head
*old_tail
;
257 unsigned int idx_total
= idx_parents
+ idx_local
;
260 new = create_child(parent
, true);
262 /* split the callchain and move a part to the new child */
263 old_tail
= parent
->val
.prev
;
264 list_del_range(&to_split
->list
, old_tail
);
265 new->val
.next
= &to_split
->list
;
266 new->val
.prev
= old_tail
;
267 to_split
->list
.prev
= &new->val
;
268 old_tail
->next
= &new->val
;
271 new->hit
= parent
->hit
;
272 new->children_hit
= parent
->children_hit
;
273 parent
->children_hit
= cumul_hits(new);
274 new->val_nr
= parent
->val_nr
- idx_local
;
275 parent
->val_nr
= idx_local
;
277 /* create a new child for the new branch if any */
278 if (idx_total
< cursor
->nr
) {
280 add_child(parent
, cursor
, period
);
281 parent
->children_hit
+= period
;
283 parent
->hit
= period
;
288 append_chain(struct callchain_node
*root
,
289 struct callchain_cursor
*cursor
,
293 append_chain_children(struct callchain_node
*root
,
294 struct callchain_cursor
*cursor
,
297 struct callchain_node
*rnode
;
299 /* lookup in childrens */
300 chain_for_each_child(rnode
, root
) {
301 unsigned int ret
= append_chain(rnode
, cursor
, period
);
304 goto inc_children_hit
;
306 /* nothing in children, add to the current node */
307 add_child(root
, cursor
, period
);
310 root
->children_hit
+= period
;
314 append_chain(struct callchain_node
*root
,
315 struct callchain_cursor
*cursor
,
318 struct callchain_cursor_node
*curr_snap
= cursor
->curr
;
319 struct callchain_list
*cnode
;
320 u64 start
= cursor
->pos
;
325 * Lookup in the current node
326 * If we have a symbol, then compare the start to match
327 * anywhere inside a function.
329 list_for_each_entry(cnode
, &root
->val
, list
) {
330 struct callchain_cursor_node
*node
;
333 node
= callchain_cursor_current(cursor
);
339 if (cnode
->ms
.sym
&& sym
) {
340 if (cnode
->ms
.sym
->start
!= sym
->start
)
342 } else if (cnode
->ip
!= node
->ip
)
348 callchain_cursor_advance(cursor
);
351 /* matches not, relay on the parent */
353 cursor
->curr
= curr_snap
;
358 matches
= cursor
->pos
- start
;
360 /* we match only a part of the node. Split it and add the new chain */
361 if (matches
< root
->val_nr
) {
362 split_add_child(root
, cursor
, cnode
, start
, matches
, period
);
366 /* we match 100% of the path, increment the hit */
367 if (matches
== root
->val_nr
&& cursor
->pos
== cursor
->nr
) {
372 /* We match the node and still have a part remaining */
373 append_chain_children(root
, cursor
, period
);
378 int callchain_append(struct callchain_root
*root
,
379 struct callchain_cursor
*cursor
,
385 callchain_cursor_commit(cursor
);
387 append_chain_children(&root
->node
, cursor
, period
);
389 if (cursor
->nr
> root
->max_depth
)
390 root
->max_depth
= cursor
->nr
;
396 merge_chain_branch(struct callchain_cursor
*cursor
,
397 struct callchain_node
*dst
, struct callchain_node
*src
)
399 struct callchain_cursor_node
**old_last
= cursor
->last
;
400 struct callchain_node
*child
, *next_child
;
401 struct callchain_list
*list
, *next_list
;
402 int old_pos
= cursor
->nr
;
405 list_for_each_entry_safe(list
, next_list
, &src
->val
, list
) {
406 callchain_cursor_append(cursor
, list
->ip
,
407 list
->ms
.map
, list
->ms
.sym
);
408 list_del(&list
->list
);
413 callchain_cursor_commit(cursor
);
414 append_chain_children(dst
, cursor
, src
->hit
);
417 chain_for_each_child_safe(child
, next_child
, src
) {
418 err
= merge_chain_branch(cursor
, dst
, child
);
422 list_del(&child
->brothers
);
426 cursor
->nr
= old_pos
;
427 cursor
->last
= old_last
;
432 int callchain_merge(struct callchain_cursor
*cursor
,
433 struct callchain_root
*dst
, struct callchain_root
*src
)
435 return merge_chain_branch(cursor
, &dst
->node
, &src
->node
);
438 int callchain_cursor_append(struct callchain_cursor
*cursor
,
439 u64 ip
, struct map
*map
, struct symbol
*sym
)
441 struct callchain_cursor_node
*node
= *cursor
->last
;
444 node
= calloc(sizeof(*node
), 1);
448 *cursor
->last
= node
;
457 cursor
->last
= &node
->next
;