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 __thread
struct callchain_cursor callchain_cursor
;
23 bool ip_callchain__valid(struct ip_callchain
*chain
,
24 const union perf_event
*event
)
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
;
31 #define chain_for_each_child(child, parent) \
32 list_for_each_entry(child, &parent->children, siblings)
34 #define chain_for_each_child_safe(child, next, parent) \
35 list_for_each_entry_safe(child, next, &parent->children, siblings)
38 rb_insert_callchain(struct rb_root
*root
, struct callchain_node
*chain
,
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
);
50 rnode
= rb_entry(parent
, struct callchain_node
, rb_node
);
51 rnode_cumul
= callchain_cumul_hits(rnode
);
55 if (rnode
->hit
< chain
->hit
)
60 case CHAIN_GRAPH_ABS
: /* Falldown */
62 if (rnode_cumul
< chain_cumul
)
73 rb_link_node(&chain
->rb_node
, parent
, p
);
74 rb_insert_color(&chain
->rb_node
, root
);
78 __sort_chain_flat(struct rb_root
*rb_root
, struct callchain_node
*node
,
81 struct callchain_node
*child
;
83 chain_for_each_child(child
, node
)
84 __sort_chain_flat(rb_root
, child
, min_hit
);
86 if (node
->hit
&& node
->hit
>= min_hit
)
87 rb_insert_callchain(rb_root
, node
, CHAIN_FLAT
);
91 * Once we get every callchains from the stream, we can now
95 sort_chain_flat(struct rb_root
*rb_root
, struct callchain_root
*root
,
96 u64 min_hit
, struct callchain_param
*param __maybe_unused
)
98 __sort_chain_flat(rb_root
, &root
->node
, min_hit
);
101 static void __sort_chain_graph_abs(struct callchain_node
*node
,
104 struct callchain_node
*child
;
106 node
->rb_root
= RB_ROOT
;
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
,
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
)
120 __sort_chain_graph_abs(&chain_root
->node
, min_hit
);
121 rb_root
->rb_node
= chain_root
->node
.rb_root
.rb_node
;
124 static void __sort_chain_graph_rel(struct callchain_node
*node
,
127 struct callchain_node
*child
;
130 node
->rb_root
= RB_ROOT
;
131 min_hit
= ceil(node
->children_hit
* min_percent
);
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
,
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
)
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
;
149 int callchain_register_param(struct callchain_param
*param
)
151 switch (param
->mode
) {
152 case CHAIN_GRAPH_ABS
:
153 param
->sort
= sort_chain_graph_abs
;
155 case CHAIN_GRAPH_REL
:
156 param
->sort
= sort_chain_graph_rel
;
159 param
->sort
= sort_chain_flat
;
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
172 static struct callchain_node
*
173 create_child(struct callchain_node
*parent
, bool inherit_children
)
175 struct callchain_node
*new;
177 new = zalloc(sizeof(*new));
179 perror("not enough memory to create child for code path tree");
182 new->parent
= parent
;
183 INIT_LIST_HEAD(&new->children
);
184 INIT_LIST_HEAD(&new->val
);
186 if (inherit_children
) {
187 struct callchain_node
*next
;
189 list_splice(&parent
->children
, &new->children
);
190 INIT_LIST_HEAD(&parent
->children
);
192 chain_for_each_child(next
, new)
195 list_add_tail(&new->siblings
, &parent
->children
);
202 * Fill the node with callchain values
205 fill_node(struct callchain_node
*node
, struct callchain_cursor
*cursor
)
207 struct callchain_cursor_node
*cursor_node
;
209 node
->val_nr
= cursor
->nr
- cursor
->pos
;
211 pr_warning("Warning: empty node in callchain tree\n");
213 cursor_node
= callchain_cursor_current(cursor
);
215 while (cursor_node
) {
216 struct callchain_list
*call
;
218 call
= zalloc(sizeof(*call
));
220 perror("not enough memory for the code path tree");
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
);
228 callchain_cursor_advance(cursor
);
229 cursor_node
= callchain_cursor_current(cursor
);
234 add_child(struct callchain_node
*parent
,
235 struct callchain_cursor
*cursor
,
238 struct callchain_node
*new;
240 new = create_child(parent
, false);
241 fill_node(new, cursor
);
243 new->children_hit
= 0;
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
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
)
258 struct callchain_node
*new;
259 struct list_head
*old_tail
;
260 unsigned int idx_total
= idx_parents
+ idx_local
;
263 new = create_child(parent
, true);
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
;
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
;
280 /* create a new child for the new branch if any */
281 if (idx_total
< cursor
->nr
) {
283 add_child(parent
, cursor
, period
);
284 parent
->children_hit
+= period
;
286 parent
->hit
= period
;
291 append_chain(struct callchain_node
*root
,
292 struct callchain_cursor
*cursor
,
296 append_chain_children(struct callchain_node
*root
,
297 struct callchain_cursor
*cursor
,
300 struct callchain_node
*rnode
;
302 /* lookup in childrens */
303 chain_for_each_child(rnode
, root
) {
304 unsigned int ret
= append_chain(rnode
, cursor
, period
);
307 goto inc_children_hit
;
309 /* nothing in children, add to the current node */
310 add_child(root
, cursor
, period
);
313 root
->children_hit
+= period
;
317 append_chain(struct callchain_node
*root
,
318 struct callchain_cursor
*cursor
,
321 struct callchain_cursor_node
*curr_snap
= cursor
->curr
;
322 struct callchain_list
*cnode
;
323 u64 start
= cursor
->pos
;
328 * Lookup in the current node
329 * If we have a symbol, then compare the start to match
330 * anywhere inside a function.
332 list_for_each_entry(cnode
, &root
->val
, list
) {
333 struct callchain_cursor_node
*node
;
336 node
= callchain_cursor_current(cursor
);
342 if (cnode
->ms
.sym
&& sym
) {
343 if (cnode
->ms
.sym
->start
!= sym
->start
)
345 } else if (cnode
->ip
!= node
->ip
)
351 callchain_cursor_advance(cursor
);
354 /* matches not, relay on the parent */
356 cursor
->curr
= curr_snap
;
361 matches
= cursor
->pos
- start
;
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
);
369 /* we match 100% of the path, increment the hit */
370 if (matches
== root
->val_nr
&& cursor
->pos
== cursor
->nr
) {
375 /* We match the node and still have a part remaining */
376 append_chain_children(root
, cursor
, period
);
381 int callchain_append(struct callchain_root
*root
,
382 struct callchain_cursor
*cursor
,
388 callchain_cursor_commit(cursor
);
390 append_chain_children(&root
->node
, cursor
, period
);
392 if (cursor
->nr
> root
->max_depth
)
393 root
->max_depth
= cursor
->nr
;
399 merge_chain_branch(struct callchain_cursor
*cursor
,
400 struct callchain_node
*dst
, struct callchain_node
*src
)
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
;
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
);
416 callchain_cursor_commit(cursor
);
417 append_chain_children(dst
, cursor
, src
->hit
);
420 chain_for_each_child_safe(child
, next_child
, src
) {
421 err
= merge_chain_branch(cursor
, dst
, child
);
425 list_del(&child
->siblings
);
429 cursor
->nr
= old_pos
;
430 cursor
->last
= old_last
;
435 int callchain_merge(struct callchain_cursor
*cursor
,
436 struct callchain_root
*dst
, struct callchain_root
*src
)
438 return merge_chain_branch(cursor
, &dst
->node
, &src
->node
);
441 int callchain_cursor_append(struct callchain_cursor
*cursor
,
442 u64 ip
, struct map
*map
, struct symbol
*sym
)
444 struct callchain_cursor_node
*node
= *cursor
->last
;
447 node
= calloc(sizeof(*node
), 1);
451 *cursor
->last
= node
;
460 cursor
->last
= &node
->next
;