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.
24 #include "callchain.h"
26 __thread
struct callchain_cursor callchain_cursor
;
29 parse_callchain_report_opt(const char *arg
)
34 symbol_conf
.use_callchain
= true;
39 tok
= strtok((char *)arg
, ",");
43 /* get the output mode */
44 if (!strncmp(tok
, "graph", strlen(arg
))) {
45 callchain_param
.mode
= CHAIN_GRAPH_ABS
;
47 } else if (!strncmp(tok
, "flat", strlen(arg
))) {
48 callchain_param
.mode
= CHAIN_FLAT
;
49 } else if (!strncmp(tok
, "fractal", strlen(arg
))) {
50 callchain_param
.mode
= CHAIN_GRAPH_REL
;
51 } else if (!strncmp(tok
, "none", strlen(arg
))) {
52 callchain_param
.mode
= CHAIN_NONE
;
53 symbol_conf
.use_callchain
= false;
59 /* get the min percentage */
60 tok
= strtok(NULL
, ",");
64 callchain_param
.min_percent
= strtod(tok
, &endptr
);
68 /* get the print limit */
69 tok2
= strtok(NULL
, ",");
74 callchain_param
.print_limit
= strtoul(tok2
, &endptr
, 0);
75 tok2
= strtok(NULL
, ",");
80 /* get the call chain order */
81 if (!strncmp(tok2
, "caller", strlen("caller")))
82 callchain_param
.order
= ORDER_CALLER
;
83 else if (!strncmp(tok2
, "callee", strlen("callee")))
84 callchain_param
.order
= ORDER_CALLEE
;
88 /* Get the sort key */
89 tok2
= strtok(NULL
, ",");
92 if (!strncmp(tok2
, "function", strlen("function")))
93 callchain_param
.key
= CCKEY_FUNCTION
;
94 else if (!strncmp(tok2
, "address", strlen("address")))
95 callchain_param
.key
= CCKEY_ADDRESS
;
99 if (callchain_register_param(&callchain_param
) < 0) {
100 pr_err("Can't register callchain params\n");
107 rb_insert_callchain(struct rb_root
*root
, struct callchain_node
*chain
,
108 enum chain_mode mode
)
110 struct rb_node
**p
= &root
->rb_node
;
111 struct rb_node
*parent
= NULL
;
112 struct callchain_node
*rnode
;
113 u64 chain_cumul
= callchain_cumul_hits(chain
);
119 rnode
= rb_entry(parent
, struct callchain_node
, rb_node
);
120 rnode_cumul
= callchain_cumul_hits(rnode
);
124 if (rnode
->hit
< chain
->hit
)
129 case CHAIN_GRAPH_ABS
: /* Falldown */
130 case CHAIN_GRAPH_REL
:
131 if (rnode_cumul
< chain_cumul
)
142 rb_link_node(&chain
->rb_node
, parent
, p
);
143 rb_insert_color(&chain
->rb_node
, root
);
147 __sort_chain_flat(struct rb_root
*rb_root
, struct callchain_node
*node
,
151 struct callchain_node
*child
;
153 n
= rb_first(&node
->rb_root_in
);
155 child
= rb_entry(n
, struct callchain_node
, rb_node_in
);
158 __sort_chain_flat(rb_root
, child
, min_hit
);
161 if (node
->hit
&& node
->hit
>= min_hit
)
162 rb_insert_callchain(rb_root
, node
, CHAIN_FLAT
);
166 * Once we get every callchains from the stream, we can now
170 sort_chain_flat(struct rb_root
*rb_root
, struct callchain_root
*root
,
171 u64 min_hit
, struct callchain_param
*param __maybe_unused
)
173 __sort_chain_flat(rb_root
, &root
->node
, min_hit
);
176 static void __sort_chain_graph_abs(struct callchain_node
*node
,
180 struct callchain_node
*child
;
182 node
->rb_root
= RB_ROOT
;
183 n
= rb_first(&node
->rb_root_in
);
186 child
= rb_entry(n
, struct callchain_node
, rb_node_in
);
189 __sort_chain_graph_abs(child
, min_hit
);
190 if (callchain_cumul_hits(child
) >= min_hit
)
191 rb_insert_callchain(&node
->rb_root
, child
,
197 sort_chain_graph_abs(struct rb_root
*rb_root
, struct callchain_root
*chain_root
,
198 u64 min_hit
, struct callchain_param
*param __maybe_unused
)
200 __sort_chain_graph_abs(&chain_root
->node
, min_hit
);
201 rb_root
->rb_node
= chain_root
->node
.rb_root
.rb_node
;
204 static void __sort_chain_graph_rel(struct callchain_node
*node
,
208 struct callchain_node
*child
;
211 node
->rb_root
= RB_ROOT
;
212 min_hit
= ceil(node
->children_hit
* min_percent
);
214 n
= rb_first(&node
->rb_root_in
);
216 child
= rb_entry(n
, struct callchain_node
, rb_node_in
);
219 __sort_chain_graph_rel(child
, min_percent
);
220 if (callchain_cumul_hits(child
) >= min_hit
)
221 rb_insert_callchain(&node
->rb_root
, child
,
227 sort_chain_graph_rel(struct rb_root
*rb_root
, struct callchain_root
*chain_root
,
228 u64 min_hit __maybe_unused
, struct callchain_param
*param
)
230 __sort_chain_graph_rel(&chain_root
->node
, param
->min_percent
/ 100.0);
231 rb_root
->rb_node
= chain_root
->node
.rb_root
.rb_node
;
234 int callchain_register_param(struct callchain_param
*param
)
236 switch (param
->mode
) {
237 case CHAIN_GRAPH_ABS
:
238 param
->sort
= sort_chain_graph_abs
;
240 case CHAIN_GRAPH_REL
:
241 param
->sort
= sort_chain_graph_rel
;
244 param
->sort
= sort_chain_flat
;
254 * Create a child for a parent. If inherit_children, then the new child
255 * will become the new parent of it's parent children
257 static struct callchain_node
*
258 create_child(struct callchain_node
*parent
, bool inherit_children
)
260 struct callchain_node
*new;
262 new = zalloc(sizeof(*new));
264 perror("not enough memory to create child for code path tree");
267 new->parent
= parent
;
268 INIT_LIST_HEAD(&new->val
);
270 if (inherit_children
) {
272 struct callchain_node
*child
;
274 new->rb_root_in
= parent
->rb_root_in
;
275 parent
->rb_root_in
= RB_ROOT
;
277 n
= rb_first(&new->rb_root_in
);
279 child
= rb_entry(n
, struct callchain_node
, rb_node_in
);
284 /* make it the first child */
285 rb_link_node(&new->rb_node_in
, NULL
, &parent
->rb_root_in
.rb_node
);
286 rb_insert_color(&new->rb_node_in
, &parent
->rb_root_in
);
294 * Fill the node with callchain values
297 fill_node(struct callchain_node
*node
, struct callchain_cursor
*cursor
)
299 struct callchain_cursor_node
*cursor_node
;
301 node
->val_nr
= cursor
->nr
- cursor
->pos
;
303 pr_warning("Warning: empty node in callchain tree\n");
305 cursor_node
= callchain_cursor_current(cursor
);
307 while (cursor_node
) {
308 struct callchain_list
*call
;
310 call
= zalloc(sizeof(*call
));
312 perror("not enough memory for the code path tree");
315 call
->ip
= cursor_node
->ip
;
316 call
->ms
.sym
= cursor_node
->sym
;
317 call
->ms
.map
= cursor_node
->map
;
318 list_add_tail(&call
->list
, &node
->val
);
320 callchain_cursor_advance(cursor
);
321 cursor_node
= callchain_cursor_current(cursor
);
325 static struct callchain_node
*
326 add_child(struct callchain_node
*parent
,
327 struct callchain_cursor
*cursor
,
330 struct callchain_node
*new;
332 new = create_child(parent
, false);
333 fill_node(new, cursor
);
335 new->children_hit
= 0;
340 static s64
match_chain(struct callchain_cursor_node
*node
,
341 struct callchain_list
*cnode
)
343 struct symbol
*sym
= node
->sym
;
345 if (cnode
->ms
.sym
&& sym
&&
346 callchain_param
.key
== CCKEY_FUNCTION
)
347 return cnode
->ms
.sym
->start
- sym
->start
;
349 return cnode
->ip
- node
->ip
;
353 * Split the parent in two parts (a new child is created) and
354 * give a part of its callchain to the created child.
355 * Then create another child to host the given callchain of new branch
358 split_add_child(struct callchain_node
*parent
,
359 struct callchain_cursor
*cursor
,
360 struct callchain_list
*to_split
,
361 u64 idx_parents
, u64 idx_local
, u64 period
)
363 struct callchain_node
*new;
364 struct list_head
*old_tail
;
365 unsigned int idx_total
= idx_parents
+ idx_local
;
368 new = create_child(parent
, true);
370 /* split the callchain and move a part to the new child */
371 old_tail
= parent
->val
.prev
;
372 list_del_range(&to_split
->list
, old_tail
);
373 new->val
.next
= &to_split
->list
;
374 new->val
.prev
= old_tail
;
375 to_split
->list
.prev
= &new->val
;
376 old_tail
->next
= &new->val
;
379 new->hit
= parent
->hit
;
380 new->children_hit
= parent
->children_hit
;
381 parent
->children_hit
= callchain_cumul_hits(new);
382 new->val_nr
= parent
->val_nr
- idx_local
;
383 parent
->val_nr
= idx_local
;
385 /* create a new child for the new branch if any */
386 if (idx_total
< cursor
->nr
) {
387 struct callchain_node
*first
;
388 struct callchain_list
*cnode
;
389 struct callchain_cursor_node
*node
;
390 struct rb_node
*p
, **pp
;
393 parent
->children_hit
+= period
;
395 node
= callchain_cursor_current(cursor
);
396 new = add_child(parent
, cursor
, period
);
399 * This is second child since we moved parent's children
400 * to new (first) child above.
402 p
= parent
->rb_root_in
.rb_node
;
403 first
= rb_entry(p
, struct callchain_node
, rb_node_in
);
404 cnode
= list_first_entry(&first
->val
, struct callchain_list
,
407 if (match_chain(node
, cnode
) < 0)
412 rb_link_node(&new->rb_node_in
, p
, pp
);
413 rb_insert_color(&new->rb_node_in
, &parent
->rb_root_in
);
415 parent
->hit
= period
;
420 append_chain(struct callchain_node
*root
,
421 struct callchain_cursor
*cursor
,
425 append_chain_children(struct callchain_node
*root
,
426 struct callchain_cursor
*cursor
,
429 struct callchain_node
*rnode
;
430 struct callchain_cursor_node
*node
;
431 struct rb_node
**p
= &root
->rb_root_in
.rb_node
;
432 struct rb_node
*parent
= NULL
;
434 node
= callchain_cursor_current(cursor
);
438 /* lookup in childrens */
443 rnode
= rb_entry(parent
, struct callchain_node
, rb_node_in
);
445 /* If at least first entry matches, rely to children */
446 ret
= append_chain(rnode
, cursor
, period
);
448 goto inc_children_hit
;
451 p
= &parent
->rb_left
;
453 p
= &parent
->rb_right
;
455 /* nothing in children, add to the current node */
456 rnode
= add_child(root
, cursor
, period
);
457 rb_link_node(&rnode
->rb_node_in
, parent
, p
);
458 rb_insert_color(&rnode
->rb_node_in
, &root
->rb_root_in
);
461 root
->children_hit
+= period
;
465 append_chain(struct callchain_node
*root
,
466 struct callchain_cursor
*cursor
,
469 struct callchain_list
*cnode
;
470 u64 start
= cursor
->pos
;
476 * Lookup in the current node
477 * If we have a symbol, then compare the start to match
478 * anywhere inside a function, unless function
481 list_for_each_entry(cnode
, &root
->val
, list
) {
482 struct callchain_cursor_node
*node
;
484 node
= callchain_cursor_current(cursor
);
488 cmp
= match_chain(node
, cnode
);
494 callchain_cursor_advance(cursor
);
497 /* matches not, relay no the parent */
499 WARN_ONCE(!cmp
, "Chain comparison error\n");
503 matches
= cursor
->pos
- start
;
505 /* we match only a part of the node. Split it and add the new chain */
506 if (matches
< root
->val_nr
) {
507 split_add_child(root
, cursor
, cnode
, start
, matches
, period
);
511 /* we match 100% of the path, increment the hit */
512 if (matches
== root
->val_nr
&& cursor
->pos
== cursor
->nr
) {
517 /* We match the node and still have a part remaining */
518 append_chain_children(root
, cursor
, period
);
523 int callchain_append(struct callchain_root
*root
,
524 struct callchain_cursor
*cursor
,
530 callchain_cursor_commit(cursor
);
532 append_chain_children(&root
->node
, cursor
, period
);
534 if (cursor
->nr
> root
->max_depth
)
535 root
->max_depth
= cursor
->nr
;
541 merge_chain_branch(struct callchain_cursor
*cursor
,
542 struct callchain_node
*dst
, struct callchain_node
*src
)
544 struct callchain_cursor_node
**old_last
= cursor
->last
;
545 struct callchain_node
*child
;
546 struct callchain_list
*list
, *next_list
;
548 int old_pos
= cursor
->nr
;
551 list_for_each_entry_safe(list
, next_list
, &src
->val
, list
) {
552 callchain_cursor_append(cursor
, list
->ip
,
553 list
->ms
.map
, list
->ms
.sym
);
554 list_del(&list
->list
);
559 callchain_cursor_commit(cursor
);
560 append_chain_children(dst
, cursor
, src
->hit
);
563 n
= rb_first(&src
->rb_root_in
);
565 child
= container_of(n
, struct callchain_node
, rb_node_in
);
567 rb_erase(&child
->rb_node_in
, &src
->rb_root_in
);
569 err
= merge_chain_branch(cursor
, dst
, child
);
576 cursor
->nr
= old_pos
;
577 cursor
->last
= old_last
;
582 int callchain_merge(struct callchain_cursor
*cursor
,
583 struct callchain_root
*dst
, struct callchain_root
*src
)
585 return merge_chain_branch(cursor
, &dst
->node
, &src
->node
);
588 int callchain_cursor_append(struct callchain_cursor
*cursor
,
589 u64 ip
, struct map
*map
, struct symbol
*sym
)
591 struct callchain_cursor_node
*node
= *cursor
->last
;
594 node
= calloc(1, sizeof(*node
));
598 *cursor
->last
= node
;
607 cursor
->last
= &node
->next
;
612 int sample__resolve_callchain(struct perf_sample
*sample
, struct symbol
**parent
,
613 struct perf_evsel
*evsel
, struct addr_location
*al
,
616 if (sample
->callchain
== NULL
)
619 if (symbol_conf
.use_callchain
|| symbol_conf
.cumulate_callchain
||
621 return machine__resolve_callchain(al
->machine
, evsel
, al
->thread
,
622 sample
, parent
, al
, max_stack
);
627 int hist_entry__append_callchain(struct hist_entry
*he
, struct perf_sample
*sample
)
629 if (!symbol_conf
.use_callchain
|| sample
->callchain
== NULL
)
631 return callchain_append(he
->callchain
, &callchain_cursor
, sample
->period
);
634 int fill_callchain_info(struct addr_location
*al
, struct callchain_cursor_node
*node
,
635 bool hide_unresolved
)
640 al
->addr
= node
->map
->map_ip(node
->map
, node
->ip
);
644 if (al
->sym
== NULL
) {
651 if (al
->map
->groups
== &al
->machine
->kmaps
) {
652 if (machine__is_host(al
->machine
)) {
653 al
->cpumode
= PERF_RECORD_MISC_KERNEL
;
656 al
->cpumode
= PERF_RECORD_MISC_GUEST_KERNEL
;
660 if (machine__is_host(al
->machine
)) {
661 al
->cpumode
= PERF_RECORD_MISC_USER
;
663 } else if (perf_guest
) {
664 al
->cpumode
= PERF_RECORD_MISC_GUEST_USER
;
667 al
->cpumode
= PERF_RECORD_MISC_HYPERVISOR
;