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
;
28 #ifdef HAVE_DWARF_UNWIND_SUPPORT
29 static int get_stack_size(const char *str
, unsigned long *_size
)
33 unsigned long max_size
= round_down(USHRT_MAX
, sizeof(u64
));
35 size
= strtoul(str
, &endptr
, 0);
41 size
= round_up(size
, sizeof(u64
));
42 if (!size
|| size
> max_size
)
50 pr_err("callchain: Incorrect stack dump size (max %ld): %s\n",
54 #endif /* HAVE_DWARF_UNWIND_SUPPORT */
56 int parse_callchain_record_opt(const char *arg
)
58 char *tok
, *name
, *saveptr
= NULL
;
62 /* We need buffer that we know we can write to. */
63 buf
= malloc(strlen(arg
) + 1);
69 tok
= strtok_r((char *)buf
, ",", &saveptr
);
70 name
= tok
? : (char *)buf
;
73 /* Framepointer style */
74 if (!strncmp(name
, "fp", sizeof("fp"))) {
75 if (!strtok_r(NULL
, ",", &saveptr
)) {
76 callchain_param
.record_mode
= CALLCHAIN_FP
;
79 pr_err("callchain: No more arguments "
80 "needed for --call-graph fp\n");
83 #ifdef HAVE_DWARF_UNWIND_SUPPORT
85 } else if (!strncmp(name
, "dwarf", sizeof("dwarf"))) {
86 const unsigned long default_stack_dump_size
= 8192;
89 callchain_param
.record_mode
= CALLCHAIN_DWARF
;
90 callchain_param
.dump_size
= default_stack_dump_size
;
92 tok
= strtok_r(NULL
, ",", &saveptr
);
94 unsigned long size
= 0;
96 ret
= get_stack_size(tok
, &size
);
97 callchain_param
.dump_size
= size
;
99 #endif /* HAVE_DWARF_UNWIND_SUPPORT */
100 } else if (!strncmp(name
, "lbr", sizeof("lbr"))) {
101 if (!strtok_r(NULL
, ",", &saveptr
)) {
102 callchain_param
.record_mode
= CALLCHAIN_LBR
;
105 pr_err("callchain: No more arguments "
106 "needed for --call-graph lbr\n");
109 pr_err("callchain: Unknown --call-graph option "
120 static int parse_callchain_mode(const char *value
)
122 if (!strncmp(value
, "graph", strlen(value
))) {
123 callchain_param
.mode
= CHAIN_GRAPH_ABS
;
126 if (!strncmp(value
, "flat", strlen(value
))) {
127 callchain_param
.mode
= CHAIN_FLAT
;
130 if (!strncmp(value
, "fractal", strlen(value
))) {
131 callchain_param
.mode
= CHAIN_GRAPH_REL
;
137 static int parse_callchain_order(const char *value
)
139 if (!strncmp(value
, "caller", strlen(value
))) {
140 callchain_param
.order
= ORDER_CALLER
;
143 if (!strncmp(value
, "callee", strlen(value
))) {
144 callchain_param
.order
= ORDER_CALLEE
;
150 static int parse_callchain_sort_key(const char *value
)
152 if (!strncmp(value
, "function", strlen(value
))) {
153 callchain_param
.key
= CCKEY_FUNCTION
;
156 if (!strncmp(value
, "address", strlen(value
))) {
157 callchain_param
.key
= CCKEY_ADDRESS
;
160 if (!strncmp(value
, "branch", strlen(value
))) {
161 callchain_param
.branch_callstack
= 1;
168 parse_callchain_report_opt(const char *arg
)
172 bool minpcnt_set
= false;
174 symbol_conf
.use_callchain
= true;
179 while ((tok
= strtok((char *)arg
, ",")) != NULL
) {
180 if (!strncmp(tok
, "none", strlen(tok
))) {
181 callchain_param
.mode
= CHAIN_NONE
;
182 symbol_conf
.use_callchain
= false;
186 if (!parse_callchain_mode(tok
) ||
187 !parse_callchain_order(tok
) ||
188 !parse_callchain_sort_key(tok
)) {
189 /* parsing ok - move on to the next */
190 } else if (!minpcnt_set
) {
191 /* try to get the min percent */
192 callchain_param
.min_percent
= strtod(tok
, &endptr
);
197 /* try print limit at last */
198 callchain_param
.print_limit
= strtoul(tok
, &endptr
, 0);
206 if (callchain_register_param(&callchain_param
) < 0) {
207 pr_err("Can't register callchain params\n");
213 int perf_callchain_config(const char *var
, const char *value
)
217 if (prefixcmp(var
, "call-graph."))
219 var
+= sizeof("call-graph.") - 1;
221 if (!strcmp(var
, "record-mode"))
222 return parse_callchain_record_opt(value
);
223 #ifdef HAVE_DWARF_UNWIND_SUPPORT
224 if (!strcmp(var
, "dump-size")) {
225 unsigned long size
= 0;
228 ret
= get_stack_size(value
, &size
);
229 callchain_param
.dump_size
= size
;
234 if (!strcmp(var
, "print-type"))
235 return parse_callchain_mode(value
);
236 if (!strcmp(var
, "order"))
237 return parse_callchain_order(value
);
238 if (!strcmp(var
, "sort-key"))
239 return parse_callchain_sort_key(value
);
240 if (!strcmp(var
, "threshold")) {
241 callchain_param
.min_percent
= strtod(value
, &endptr
);
245 if (!strcmp(var
, "print-limit")) {
246 callchain_param
.print_limit
= strtod(value
, &endptr
);
255 rb_insert_callchain(struct rb_root
*root
, struct callchain_node
*chain
,
256 enum chain_mode mode
)
258 struct rb_node
**p
= &root
->rb_node
;
259 struct rb_node
*parent
= NULL
;
260 struct callchain_node
*rnode
;
261 u64 chain_cumul
= callchain_cumul_hits(chain
);
267 rnode
= rb_entry(parent
, struct callchain_node
, rb_node
);
268 rnode_cumul
= callchain_cumul_hits(rnode
);
272 if (rnode
->hit
< chain
->hit
)
277 case CHAIN_GRAPH_ABS
: /* Falldown */
278 case CHAIN_GRAPH_REL
:
279 if (rnode_cumul
< chain_cumul
)
290 rb_link_node(&chain
->rb_node
, parent
, p
);
291 rb_insert_color(&chain
->rb_node
, root
);
295 __sort_chain_flat(struct rb_root
*rb_root
, struct callchain_node
*node
,
299 struct callchain_node
*child
;
301 n
= rb_first(&node
->rb_root_in
);
303 child
= rb_entry(n
, struct callchain_node
, rb_node_in
);
306 __sort_chain_flat(rb_root
, child
, min_hit
);
309 if (node
->hit
&& node
->hit
>= min_hit
)
310 rb_insert_callchain(rb_root
, node
, CHAIN_FLAT
);
314 * Once we get every callchains from the stream, we can now
318 sort_chain_flat(struct rb_root
*rb_root
, struct callchain_root
*root
,
319 u64 min_hit
, struct callchain_param
*param __maybe_unused
)
321 __sort_chain_flat(rb_root
, &root
->node
, min_hit
);
324 static void __sort_chain_graph_abs(struct callchain_node
*node
,
328 struct callchain_node
*child
;
330 node
->rb_root
= RB_ROOT
;
331 n
= rb_first(&node
->rb_root_in
);
334 child
= rb_entry(n
, struct callchain_node
, rb_node_in
);
337 __sort_chain_graph_abs(child
, min_hit
);
338 if (callchain_cumul_hits(child
) >= min_hit
)
339 rb_insert_callchain(&node
->rb_root
, child
,
345 sort_chain_graph_abs(struct rb_root
*rb_root
, struct callchain_root
*chain_root
,
346 u64 min_hit
, struct callchain_param
*param __maybe_unused
)
348 __sort_chain_graph_abs(&chain_root
->node
, min_hit
);
349 rb_root
->rb_node
= chain_root
->node
.rb_root
.rb_node
;
352 static void __sort_chain_graph_rel(struct callchain_node
*node
,
356 struct callchain_node
*child
;
359 node
->rb_root
= RB_ROOT
;
360 min_hit
= ceil(node
->children_hit
* min_percent
);
362 n
= rb_first(&node
->rb_root_in
);
364 child
= rb_entry(n
, struct callchain_node
, rb_node_in
);
367 __sort_chain_graph_rel(child
, min_percent
);
368 if (callchain_cumul_hits(child
) >= min_hit
)
369 rb_insert_callchain(&node
->rb_root
, child
,
375 sort_chain_graph_rel(struct rb_root
*rb_root
, struct callchain_root
*chain_root
,
376 u64 min_hit __maybe_unused
, struct callchain_param
*param
)
378 __sort_chain_graph_rel(&chain_root
->node
, param
->min_percent
/ 100.0);
379 rb_root
->rb_node
= chain_root
->node
.rb_root
.rb_node
;
382 int callchain_register_param(struct callchain_param
*param
)
384 switch (param
->mode
) {
385 case CHAIN_GRAPH_ABS
:
386 param
->sort
= sort_chain_graph_abs
;
388 case CHAIN_GRAPH_REL
:
389 param
->sort
= sort_chain_graph_rel
;
392 param
->sort
= sort_chain_flat
;
402 * Create a child for a parent. If inherit_children, then the new child
403 * will become the new parent of it's parent children
405 static struct callchain_node
*
406 create_child(struct callchain_node
*parent
, bool inherit_children
)
408 struct callchain_node
*new;
410 new = zalloc(sizeof(*new));
412 perror("not enough memory to create child for code path tree");
415 new->parent
= parent
;
416 INIT_LIST_HEAD(&new->val
);
418 if (inherit_children
) {
420 struct callchain_node
*child
;
422 new->rb_root_in
= parent
->rb_root_in
;
423 parent
->rb_root_in
= RB_ROOT
;
425 n
= rb_first(&new->rb_root_in
);
427 child
= rb_entry(n
, struct callchain_node
, rb_node_in
);
432 /* make it the first child */
433 rb_link_node(&new->rb_node_in
, NULL
, &parent
->rb_root_in
.rb_node
);
434 rb_insert_color(&new->rb_node_in
, &parent
->rb_root_in
);
442 * Fill the node with callchain values
445 fill_node(struct callchain_node
*node
, struct callchain_cursor
*cursor
)
447 struct callchain_cursor_node
*cursor_node
;
449 node
->val_nr
= cursor
->nr
- cursor
->pos
;
451 pr_warning("Warning: empty node in callchain tree\n");
453 cursor_node
= callchain_cursor_current(cursor
);
455 while (cursor_node
) {
456 struct callchain_list
*call
;
458 call
= zalloc(sizeof(*call
));
460 perror("not enough memory for the code path tree");
463 call
->ip
= cursor_node
->ip
;
464 call
->ms
.sym
= cursor_node
->sym
;
465 call
->ms
.map
= cursor_node
->map
;
466 list_add_tail(&call
->list
, &node
->val
);
468 callchain_cursor_advance(cursor
);
469 cursor_node
= callchain_cursor_current(cursor
);
473 static struct callchain_node
*
474 add_child(struct callchain_node
*parent
,
475 struct callchain_cursor
*cursor
,
478 struct callchain_node
*new;
480 new = create_child(parent
, false);
481 fill_node(new, cursor
);
483 new->children_hit
= 0;
488 static s64
match_chain(struct callchain_cursor_node
*node
,
489 struct callchain_list
*cnode
)
491 struct symbol
*sym
= node
->sym
;
493 if (cnode
->ms
.sym
&& sym
&&
494 callchain_param
.key
== CCKEY_FUNCTION
)
495 return cnode
->ms
.sym
->start
- sym
->start
;
497 return cnode
->ip
- node
->ip
;
501 * Split the parent in two parts (a new child is created) and
502 * give a part of its callchain to the created child.
503 * Then create another child to host the given callchain of new branch
506 split_add_child(struct callchain_node
*parent
,
507 struct callchain_cursor
*cursor
,
508 struct callchain_list
*to_split
,
509 u64 idx_parents
, u64 idx_local
, u64 period
)
511 struct callchain_node
*new;
512 struct list_head
*old_tail
;
513 unsigned int idx_total
= idx_parents
+ idx_local
;
516 new = create_child(parent
, true);
518 /* split the callchain and move a part to the new child */
519 old_tail
= parent
->val
.prev
;
520 list_del_range(&to_split
->list
, old_tail
);
521 new->val
.next
= &to_split
->list
;
522 new->val
.prev
= old_tail
;
523 to_split
->list
.prev
= &new->val
;
524 old_tail
->next
= &new->val
;
527 new->hit
= parent
->hit
;
528 new->children_hit
= parent
->children_hit
;
529 parent
->children_hit
= callchain_cumul_hits(new);
530 new->val_nr
= parent
->val_nr
- idx_local
;
531 parent
->val_nr
= idx_local
;
533 /* create a new child for the new branch if any */
534 if (idx_total
< cursor
->nr
) {
535 struct callchain_node
*first
;
536 struct callchain_list
*cnode
;
537 struct callchain_cursor_node
*node
;
538 struct rb_node
*p
, **pp
;
541 parent
->children_hit
+= period
;
543 node
= callchain_cursor_current(cursor
);
544 new = add_child(parent
, cursor
, period
);
547 * This is second child since we moved parent's children
548 * to new (first) child above.
550 p
= parent
->rb_root_in
.rb_node
;
551 first
= rb_entry(p
, struct callchain_node
, rb_node_in
);
552 cnode
= list_first_entry(&first
->val
, struct callchain_list
,
555 if (match_chain(node
, cnode
) < 0)
560 rb_link_node(&new->rb_node_in
, p
, pp
);
561 rb_insert_color(&new->rb_node_in
, &parent
->rb_root_in
);
563 parent
->hit
= period
;
568 append_chain(struct callchain_node
*root
,
569 struct callchain_cursor
*cursor
,
573 append_chain_children(struct callchain_node
*root
,
574 struct callchain_cursor
*cursor
,
577 struct callchain_node
*rnode
;
578 struct callchain_cursor_node
*node
;
579 struct rb_node
**p
= &root
->rb_root_in
.rb_node
;
580 struct rb_node
*parent
= NULL
;
582 node
= callchain_cursor_current(cursor
);
586 /* lookup in childrens */
591 rnode
= rb_entry(parent
, struct callchain_node
, rb_node_in
);
593 /* If at least first entry matches, rely to children */
594 ret
= append_chain(rnode
, cursor
, period
);
596 goto inc_children_hit
;
599 p
= &parent
->rb_left
;
601 p
= &parent
->rb_right
;
603 /* nothing in children, add to the current node */
604 rnode
= add_child(root
, cursor
, period
);
605 rb_link_node(&rnode
->rb_node_in
, parent
, p
);
606 rb_insert_color(&rnode
->rb_node_in
, &root
->rb_root_in
);
609 root
->children_hit
+= period
;
613 append_chain(struct callchain_node
*root
,
614 struct callchain_cursor
*cursor
,
617 struct callchain_list
*cnode
;
618 u64 start
= cursor
->pos
;
624 * Lookup in the current node
625 * If we have a symbol, then compare the start to match
626 * anywhere inside a function, unless function
629 list_for_each_entry(cnode
, &root
->val
, list
) {
630 struct callchain_cursor_node
*node
;
632 node
= callchain_cursor_current(cursor
);
636 cmp
= match_chain(node
, cnode
);
642 callchain_cursor_advance(cursor
);
645 /* matches not, relay no the parent */
647 WARN_ONCE(!cmp
, "Chain comparison error\n");
651 matches
= cursor
->pos
- start
;
653 /* we match only a part of the node. Split it and add the new chain */
654 if (matches
< root
->val_nr
) {
655 split_add_child(root
, cursor
, cnode
, start
, matches
, period
);
659 /* we match 100% of the path, increment the hit */
660 if (matches
== root
->val_nr
&& cursor
->pos
== cursor
->nr
) {
665 /* We match the node and still have a part remaining */
666 append_chain_children(root
, cursor
, period
);
671 int callchain_append(struct callchain_root
*root
,
672 struct callchain_cursor
*cursor
,
678 callchain_cursor_commit(cursor
);
680 append_chain_children(&root
->node
, cursor
, period
);
682 if (cursor
->nr
> root
->max_depth
)
683 root
->max_depth
= cursor
->nr
;
689 merge_chain_branch(struct callchain_cursor
*cursor
,
690 struct callchain_node
*dst
, struct callchain_node
*src
)
692 struct callchain_cursor_node
**old_last
= cursor
->last
;
693 struct callchain_node
*child
;
694 struct callchain_list
*list
, *next_list
;
696 int old_pos
= cursor
->nr
;
699 list_for_each_entry_safe(list
, next_list
, &src
->val
, list
) {
700 callchain_cursor_append(cursor
, list
->ip
,
701 list
->ms
.map
, list
->ms
.sym
);
702 list_del(&list
->list
);
707 callchain_cursor_commit(cursor
);
708 append_chain_children(dst
, cursor
, src
->hit
);
711 n
= rb_first(&src
->rb_root_in
);
713 child
= container_of(n
, struct callchain_node
, rb_node_in
);
715 rb_erase(&child
->rb_node_in
, &src
->rb_root_in
);
717 err
= merge_chain_branch(cursor
, dst
, child
);
724 cursor
->nr
= old_pos
;
725 cursor
->last
= old_last
;
730 int callchain_merge(struct callchain_cursor
*cursor
,
731 struct callchain_root
*dst
, struct callchain_root
*src
)
733 return merge_chain_branch(cursor
, &dst
->node
, &src
->node
);
736 int callchain_cursor_append(struct callchain_cursor
*cursor
,
737 u64 ip
, struct map
*map
, struct symbol
*sym
)
739 struct callchain_cursor_node
*node
= *cursor
->last
;
742 node
= calloc(1, sizeof(*node
));
746 *cursor
->last
= node
;
755 cursor
->last
= &node
->next
;
760 int sample__resolve_callchain(struct perf_sample
*sample
, struct symbol
**parent
,
761 struct perf_evsel
*evsel
, struct addr_location
*al
,
764 if (sample
->callchain
== NULL
)
767 if (symbol_conf
.use_callchain
|| symbol_conf
.cumulate_callchain
||
769 return thread__resolve_callchain(al
->thread
, evsel
, sample
,
770 parent
, al
, max_stack
);
775 int hist_entry__append_callchain(struct hist_entry
*he
, struct perf_sample
*sample
)
777 if (!symbol_conf
.use_callchain
|| sample
->callchain
== NULL
)
779 return callchain_append(he
->callchain
, &callchain_cursor
, sample
->period
);
782 int fill_callchain_info(struct addr_location
*al
, struct callchain_cursor_node
*node
,
783 bool hide_unresolved
)
788 al
->addr
= node
->map
->map_ip(node
->map
, node
->ip
);
792 if (al
->sym
== NULL
) {
799 if (al
->map
->groups
== &al
->machine
->kmaps
) {
800 if (machine__is_host(al
->machine
)) {
801 al
->cpumode
= PERF_RECORD_MISC_KERNEL
;
804 al
->cpumode
= PERF_RECORD_MISC_GUEST_KERNEL
;
808 if (machine__is_host(al
->machine
)) {
809 al
->cpumode
= PERF_RECORD_MISC_USER
;
811 } else if (perf_guest
) {
812 al
->cpumode
= PERF_RECORD_MISC_GUEST_USER
;
815 al
->cpumode
= PERF_RECORD_MISC_HYPERVISOR
;
824 char *callchain_list__sym_name(struct callchain_list
*cl
,
825 char *bf
, size_t bfsize
, bool show_dso
)
830 if (callchain_param
.key
== CCKEY_ADDRESS
&&
831 cl
->ms
.map
&& !cl
->srcline
)
832 cl
->srcline
= get_srcline(cl
->ms
.map
->dso
,
833 map__rip_2objdump(cl
->ms
.map
,
837 printed
= scnprintf(bf
, bfsize
, "%s %s",
838 cl
->ms
.sym
->name
, cl
->srcline
);
840 printed
= scnprintf(bf
, bfsize
, "%s", cl
->ms
.sym
->name
);
842 printed
= scnprintf(bf
, bfsize
, "%#" PRIx64
, cl
->ip
);
845 scnprintf(bf
+ printed
, bfsize
- printed
, " %s",
847 cl
->ms
.map
->dso
->short_name
:
853 static void free_callchain_node(struct callchain_node
*node
)
855 struct callchain_list
*list
, *tmp
;
856 struct callchain_node
*child
;
859 list_for_each_entry_safe(list
, tmp
, &node
->val
, list
) {
860 list_del(&list
->list
);
864 n
= rb_first(&node
->rb_root_in
);
866 child
= container_of(n
, struct callchain_node
, rb_node_in
);
868 rb_erase(&child
->rb_node_in
, &node
->rb_root_in
);
870 free_callchain_node(child
);
875 void free_callchain(struct callchain_root
*root
)
877 if (!symbol_conf
.use_callchain
)
880 free_callchain_node(&root
->node
);