1 // SPDX-License-Identifier: GPL-2.0
3 * Copyright (C) 2009-2011, Frederic Weisbecker <fweisbec@gmail.com>
5 * Handle the callchains from the stream in an ad-hoc radix tree and then
6 * sort them in an rbtree.
8 * Using a radix for code path provides a fast retrieval and factorizes
9 * memory use. Also that lets us use the paths in a hierarchical graph view.
19 #include <linux/string.h>
20 #include <linux/zalloc.h>
31 #include "callchain.h"
36 #define CALLCHAIN_PARAM_DEFAULT \
37 .mode = CHAIN_GRAPH_ABS, \
39 .order = ORDER_CALLEE, \
40 .key = CCKEY_FUNCTION, \
41 .value = CCVAL_PERCENT, \
43 struct callchain_param callchain_param = {
44 CALLCHAIN_PARAM_DEFAULT
48 * Are there any events usind DWARF callchains?
52 * -e cycles/call-graph=dwarf/
54 bool dwarf_callchain_users
;
56 struct callchain_param callchain_param_default
= {
57 CALLCHAIN_PARAM_DEFAULT
60 __thread
struct callchain_cursor callchain_cursor
;
62 int parse_callchain_record_opt(const char *arg
, struct callchain_param
*param
)
64 return parse_callchain_record(arg
, param
);
67 static int parse_callchain_mode(const char *value
)
69 if (!strncmp(value
, "graph", strlen(value
))) {
70 callchain_param
.mode
= CHAIN_GRAPH_ABS
;
73 if (!strncmp(value
, "flat", strlen(value
))) {
74 callchain_param
.mode
= CHAIN_FLAT
;
77 if (!strncmp(value
, "fractal", strlen(value
))) {
78 callchain_param
.mode
= CHAIN_GRAPH_REL
;
81 if (!strncmp(value
, "folded", strlen(value
))) {
82 callchain_param
.mode
= CHAIN_FOLDED
;
88 static int parse_callchain_order(const char *value
)
90 if (!strncmp(value
, "caller", strlen(value
))) {
91 callchain_param
.order
= ORDER_CALLER
;
92 callchain_param
.order_set
= true;
95 if (!strncmp(value
, "callee", strlen(value
))) {
96 callchain_param
.order
= ORDER_CALLEE
;
97 callchain_param
.order_set
= true;
103 static int parse_callchain_sort_key(const char *value
)
105 if (!strncmp(value
, "function", strlen(value
))) {
106 callchain_param
.key
= CCKEY_FUNCTION
;
109 if (!strncmp(value
, "address", strlen(value
))) {
110 callchain_param
.key
= CCKEY_ADDRESS
;
113 if (!strncmp(value
, "srcline", strlen(value
))) {
114 callchain_param
.key
= CCKEY_SRCLINE
;
117 if (!strncmp(value
, "branch", strlen(value
))) {
118 callchain_param
.branch_callstack
= 1;
124 static int parse_callchain_value(const char *value
)
126 if (!strncmp(value
, "percent", strlen(value
))) {
127 callchain_param
.value
= CCVAL_PERCENT
;
130 if (!strncmp(value
, "period", strlen(value
))) {
131 callchain_param
.value
= CCVAL_PERIOD
;
134 if (!strncmp(value
, "count", strlen(value
))) {
135 callchain_param
.value
= CCVAL_COUNT
;
141 static int get_stack_size(const char *str
, unsigned long *_size
)
145 unsigned long max_size
= round_down(USHRT_MAX
, sizeof(u64
));
147 size
= strtoul(str
, &endptr
, 0);
153 size
= round_up(size
, sizeof(u64
));
154 if (!size
|| size
> max_size
)
162 pr_err("callchain: Incorrect stack dump size (max %ld): %s\n",
168 __parse_callchain_report_opt(const char *arg
, bool allow_record_opt
)
171 char *endptr
, *saveptr
= NULL
;
172 bool minpcnt_set
= false;
173 bool record_opt_set
= false;
174 bool try_stack_size
= false;
176 callchain_param
.enabled
= true;
177 symbol_conf
.use_callchain
= true;
182 while ((tok
= strtok_r((char *)arg
, ",", &saveptr
)) != NULL
) {
183 if (!strncmp(tok
, "none", strlen(tok
))) {
184 callchain_param
.mode
= CHAIN_NONE
;
185 callchain_param
.enabled
= false;
186 symbol_conf
.use_callchain
= false;
190 if (!parse_callchain_mode(tok
) ||
191 !parse_callchain_order(tok
) ||
192 !parse_callchain_sort_key(tok
) ||
193 !parse_callchain_value(tok
)) {
194 /* parsing ok - move on to the next */
195 try_stack_size
= false;
197 } else if (allow_record_opt
&& !record_opt_set
) {
198 if (parse_callchain_record(tok
, &callchain_param
))
201 /* assume that number followed by 'dwarf' is stack size */
202 if (callchain_param
.record_mode
== CALLCHAIN_DWARF
)
203 try_stack_size
= true;
205 record_opt_set
= true;
210 if (try_stack_size
) {
211 unsigned long size
= 0;
213 if (get_stack_size(tok
, &size
) < 0)
215 callchain_param
.dump_size
= size
;
216 try_stack_size
= false;
217 } else if (!minpcnt_set
) {
218 /* try to get the min percent */
219 callchain_param
.min_percent
= strtod(tok
, &endptr
);
224 /* try print limit at last */
225 callchain_param
.print_limit
= strtoul(tok
, &endptr
, 0);
233 if (callchain_register_param(&callchain_param
) < 0) {
234 pr_err("Can't register callchain params\n");
240 int parse_callchain_report_opt(const char *arg
)
242 return __parse_callchain_report_opt(arg
, false);
245 int parse_callchain_top_opt(const char *arg
)
247 return __parse_callchain_report_opt(arg
, true);
250 int parse_callchain_record(const char *arg
, struct callchain_param
*param
)
252 char *tok
, *name
, *saveptr
= NULL
;
256 /* We need buffer that we know we can write to. */
257 buf
= malloc(strlen(arg
) + 1);
263 tok
= strtok_r((char *)buf
, ",", &saveptr
);
264 name
= tok
? : (char *)buf
;
267 /* Framepointer style */
268 if (!strncmp(name
, "fp", sizeof("fp"))) {
269 if (!strtok_r(NULL
, ",", &saveptr
)) {
270 param
->record_mode
= CALLCHAIN_FP
;
273 pr_err("callchain: No more arguments "
274 "needed for --call-graph fp\n");
278 } else if (!strncmp(name
, "dwarf", sizeof("dwarf"))) {
279 const unsigned long default_stack_dump_size
= 8192;
282 param
->record_mode
= CALLCHAIN_DWARF
;
283 param
->dump_size
= default_stack_dump_size
;
284 dwarf_callchain_users
= true;
286 tok
= strtok_r(NULL
, ",", &saveptr
);
288 unsigned long size
= 0;
290 ret
= get_stack_size(tok
, &size
);
291 param
->dump_size
= size
;
293 } else if (!strncmp(name
, "lbr", sizeof("lbr"))) {
294 if (!strtok_r(NULL
, ",", &saveptr
)) {
295 param
->record_mode
= CALLCHAIN_LBR
;
298 pr_err("callchain: No more arguments "
299 "needed for --call-graph lbr\n");
302 pr_err("callchain: Unknown --call-graph option "
313 int perf_callchain_config(const char *var
, const char *value
)
317 if (!strstarts(var
, "call-graph."))
319 var
+= sizeof("call-graph.") - 1;
321 if (!strcmp(var
, "record-mode"))
322 return parse_callchain_record_opt(value
, &callchain_param
);
323 if (!strcmp(var
, "dump-size")) {
324 unsigned long size
= 0;
327 ret
= get_stack_size(value
, &size
);
328 callchain_param
.dump_size
= size
;
332 if (!strcmp(var
, "print-type")){
334 ret
= parse_callchain_mode(value
);
336 pr_err("Invalid callchain mode: %s\n", value
);
339 if (!strcmp(var
, "order")){
341 ret
= parse_callchain_order(value
);
343 pr_err("Invalid callchain order: %s\n", value
);
346 if (!strcmp(var
, "sort-key")){
348 ret
= parse_callchain_sort_key(value
);
350 pr_err("Invalid callchain sort key: %s\n", value
);
353 if (!strcmp(var
, "threshold")) {
354 callchain_param
.min_percent
= strtod(value
, &endptr
);
355 if (value
== endptr
) {
356 pr_err("Invalid callchain threshold: %s\n", value
);
360 if (!strcmp(var
, "print-limit")) {
361 callchain_param
.print_limit
= strtod(value
, &endptr
);
362 if (value
== endptr
) {
363 pr_err("Invalid callchain print limit: %s\n", value
);
372 rb_insert_callchain(struct rb_root
*root
, struct callchain_node
*chain
,
373 enum chain_mode mode
)
375 struct rb_node
**p
= &root
->rb_node
;
376 struct rb_node
*parent
= NULL
;
377 struct callchain_node
*rnode
;
378 u64 chain_cumul
= callchain_cumul_hits(chain
);
384 rnode
= rb_entry(parent
, struct callchain_node
, rb_node
);
385 rnode_cumul
= callchain_cumul_hits(rnode
);
390 if (rnode
->hit
< chain
->hit
)
395 case CHAIN_GRAPH_ABS
: /* Falldown */
396 case CHAIN_GRAPH_REL
:
397 if (rnode_cumul
< chain_cumul
)
408 rb_link_node(&chain
->rb_node
, parent
, p
);
409 rb_insert_color(&chain
->rb_node
, root
);
413 __sort_chain_flat(struct rb_root
*rb_root
, struct callchain_node
*node
,
417 struct callchain_node
*child
;
419 n
= rb_first(&node
->rb_root_in
);
421 child
= rb_entry(n
, struct callchain_node
, rb_node_in
);
424 __sort_chain_flat(rb_root
, child
, min_hit
);
427 if (node
->hit
&& node
->hit
>= min_hit
)
428 rb_insert_callchain(rb_root
, node
, CHAIN_FLAT
);
432 * Once we get every callchains from the stream, we can now
436 sort_chain_flat(struct rb_root
*rb_root
, struct callchain_root
*root
,
437 u64 min_hit
, struct callchain_param
*param __maybe_unused
)
440 __sort_chain_flat(rb_root
, &root
->node
, min_hit
);
443 static void __sort_chain_graph_abs(struct callchain_node
*node
,
447 struct callchain_node
*child
;
449 node
->rb_root
= RB_ROOT
;
450 n
= rb_first(&node
->rb_root_in
);
453 child
= rb_entry(n
, struct callchain_node
, rb_node_in
);
456 __sort_chain_graph_abs(child
, min_hit
);
457 if (callchain_cumul_hits(child
) >= min_hit
)
458 rb_insert_callchain(&node
->rb_root
, child
,
464 sort_chain_graph_abs(struct rb_root
*rb_root
, struct callchain_root
*chain_root
,
465 u64 min_hit
, struct callchain_param
*param __maybe_unused
)
467 __sort_chain_graph_abs(&chain_root
->node
, min_hit
);
468 rb_root
->rb_node
= chain_root
->node
.rb_root
.rb_node
;
471 static void __sort_chain_graph_rel(struct callchain_node
*node
,
475 struct callchain_node
*child
;
478 node
->rb_root
= RB_ROOT
;
479 min_hit
= ceil(node
->children_hit
* min_percent
);
481 n
= rb_first(&node
->rb_root_in
);
483 child
= rb_entry(n
, struct callchain_node
, rb_node_in
);
486 __sort_chain_graph_rel(child
, min_percent
);
487 if (callchain_cumul_hits(child
) >= min_hit
)
488 rb_insert_callchain(&node
->rb_root
, child
,
494 sort_chain_graph_rel(struct rb_root
*rb_root
, struct callchain_root
*chain_root
,
495 u64 min_hit __maybe_unused
, struct callchain_param
*param
)
497 __sort_chain_graph_rel(&chain_root
->node
, param
->min_percent
/ 100.0);
498 rb_root
->rb_node
= chain_root
->node
.rb_root
.rb_node
;
501 int callchain_register_param(struct callchain_param
*param
)
503 switch (param
->mode
) {
504 case CHAIN_GRAPH_ABS
:
505 param
->sort
= sort_chain_graph_abs
;
507 case CHAIN_GRAPH_REL
:
508 param
->sort
= sort_chain_graph_rel
;
512 param
->sort
= sort_chain_flat
;
522 * Create a child for a parent. If inherit_children, then the new child
523 * will become the new parent of it's parent children
525 static struct callchain_node
*
526 create_child(struct callchain_node
*parent
, bool inherit_children
)
528 struct callchain_node
*new;
530 new = zalloc(sizeof(*new));
532 perror("not enough memory to create child for code path tree");
535 new->parent
= parent
;
536 INIT_LIST_HEAD(&new->val
);
537 INIT_LIST_HEAD(&new->parent_val
);
539 if (inherit_children
) {
541 struct callchain_node
*child
;
543 new->rb_root_in
= parent
->rb_root_in
;
544 parent
->rb_root_in
= RB_ROOT
;
546 n
= rb_first(&new->rb_root_in
);
548 child
= rb_entry(n
, struct callchain_node
, rb_node_in
);
553 /* make it the first child */
554 rb_link_node(&new->rb_node_in
, NULL
, &parent
->rb_root_in
.rb_node
);
555 rb_insert_color(&new->rb_node_in
, &parent
->rb_root_in
);
563 * Fill the node with callchain values
566 fill_node(struct callchain_node
*node
, struct callchain_cursor
*cursor
)
568 struct callchain_cursor_node
*cursor_node
;
570 node
->val_nr
= cursor
->nr
- cursor
->pos
;
572 pr_warning("Warning: empty node in callchain tree\n");
574 cursor_node
= callchain_cursor_current(cursor
);
576 while (cursor_node
) {
577 struct callchain_list
*call
;
579 call
= zalloc(sizeof(*call
));
581 perror("not enough memory for the code path tree");
584 call
->ip
= cursor_node
->ip
;
585 call
->ms
= cursor_node
->ms
;
586 map__get(call
->ms
.map
);
587 call
->srcline
= cursor_node
->srcline
;
589 if (cursor_node
->branch
) {
590 call
->branch_count
= 1;
592 if (cursor_node
->branch_from
) {
594 * branch_from is set with value somewhere else
595 * to imply it's "to" of a branch.
597 call
->brtype_stat
.branch_to
= true;
599 if (cursor_node
->branch_flags
.predicted
)
600 call
->predicted_count
= 1;
602 if (cursor_node
->branch_flags
.abort
)
603 call
->abort_count
= 1;
605 branch_type_count(&call
->brtype_stat
,
606 &cursor_node
->branch_flags
,
607 cursor_node
->branch_from
,
611 * It's "from" of a branch
613 call
->brtype_stat
.branch_to
= false;
615 cursor_node
->branch_flags
.cycles
;
616 call
->iter_count
= cursor_node
->nr_loop_iter
;
617 call
->iter_cycles
= cursor_node
->iter_cycles
;
621 list_add_tail(&call
->list
, &node
->val
);
623 callchain_cursor_advance(cursor
);
624 cursor_node
= callchain_cursor_current(cursor
);
629 static struct callchain_node
*
630 add_child(struct callchain_node
*parent
,
631 struct callchain_cursor
*cursor
,
634 struct callchain_node
*new;
636 new = create_child(parent
, false);
640 if (fill_node(new, cursor
) < 0) {
641 struct callchain_list
*call
, *tmp
;
643 list_for_each_entry_safe(call
, tmp
, &new->val
, list
) {
644 list_del_init(&call
->list
);
645 map__zput(call
->ms
.map
);
652 new->children_hit
= 0;
654 new->children_count
= 0;
666 static enum match_result
match_chain_strings(const char *left
,
669 enum match_result ret
= MATCH_EQ
;
673 cmp
= strcmp(left
, right
);
674 else if (!left
&& right
)
676 else if (left
&& !right
)
682 ret
= cmp
< 0 ? MATCH_LT
: MATCH_GT
;
688 * We need to always use relative addresses because we're aggregating
689 * callchains from multiple threads, i.e. different address spaces, so
690 * comparing absolute addresses make no sense as a symbol in a DSO may end up
691 * in a different address when used in a different binary or even the same
692 * binary but with some sort of address randomization technique, thus we need
693 * to compare just relative addresses. -acme
695 static enum match_result
match_chain_dso_addresses(struct map
*left_map
, u64 left_ip
,
696 struct map
*right_map
, u64 right_ip
)
698 struct dso
*left_dso
= left_map
? left_map
->dso
: NULL
;
699 struct dso
*right_dso
= right_map
? right_map
->dso
: NULL
;
701 if (left_dso
!= right_dso
)
702 return left_dso
< right_dso
? MATCH_LT
: MATCH_GT
;
704 if (left_ip
!= right_ip
)
705 return left_ip
< right_ip
? MATCH_LT
: MATCH_GT
;
710 static enum match_result
match_chain(struct callchain_cursor_node
*node
,
711 struct callchain_list
*cnode
)
713 enum match_result match
= MATCH_ERROR
;
715 switch (callchain_param
.key
) {
717 match
= match_chain_strings(cnode
->srcline
, node
->srcline
);
718 if (match
!= MATCH_ERROR
)
720 /* otherwise fall-back to symbol-based comparison below */
723 if (node
->ms
.sym
&& cnode
->ms
.sym
) {
725 * Compare inlined frames based on their symbol name
726 * because different inlined frames will have the same
727 * symbol start. Otherwise do a faster comparison based
728 * on the symbol start address.
730 if (cnode
->ms
.sym
->inlined
|| node
->ms
.sym
->inlined
) {
731 match
= match_chain_strings(cnode
->ms
.sym
->name
,
733 if (match
!= MATCH_ERROR
)
736 match
= match_chain_dso_addresses(cnode
->ms
.map
, cnode
->ms
.sym
->start
,
737 node
->ms
.map
, node
->ms
.sym
->start
);
741 /* otherwise fall-back to IP-based comparison below */
745 match
= match_chain_dso_addresses(cnode
->ms
.map
, cnode
->ip
, node
->ms
.map
, node
->ip
);
749 if (match
== MATCH_EQ
&& node
->branch
) {
750 cnode
->branch_count
++;
752 if (node
->branch_from
) {
754 * It's "to" of a branch
756 cnode
->brtype_stat
.branch_to
= true;
758 if (node
->branch_flags
.predicted
)
759 cnode
->predicted_count
++;
761 if (node
->branch_flags
.abort
)
762 cnode
->abort_count
++;
764 branch_type_count(&cnode
->brtype_stat
,
770 * It's "from" of a branch
772 cnode
->brtype_stat
.branch_to
= false;
773 cnode
->cycles_count
+= node
->branch_flags
.cycles
;
774 cnode
->iter_count
+= node
->nr_loop_iter
;
775 cnode
->iter_cycles
+= node
->iter_cycles
;
784 * Split the parent in two parts (a new child is created) and
785 * give a part of its callchain to the created child.
786 * Then create another child to host the given callchain of new branch
789 split_add_child(struct callchain_node
*parent
,
790 struct callchain_cursor
*cursor
,
791 struct callchain_list
*to_split
,
792 u64 idx_parents
, u64 idx_local
, u64 period
)
794 struct callchain_node
*new;
795 struct list_head
*old_tail
;
796 unsigned int idx_total
= idx_parents
+ idx_local
;
799 new = create_child(parent
, true);
803 /* split the callchain and move a part to the new child */
804 old_tail
= parent
->val
.prev
;
805 list_del_range(&to_split
->list
, old_tail
);
806 new->val
.next
= &to_split
->list
;
807 new->val
.prev
= old_tail
;
808 to_split
->list
.prev
= &new->val
;
809 old_tail
->next
= &new->val
;
812 new->hit
= parent
->hit
;
813 new->children_hit
= parent
->children_hit
;
814 parent
->children_hit
= callchain_cumul_hits(new);
815 new->val_nr
= parent
->val_nr
- idx_local
;
816 parent
->val_nr
= idx_local
;
817 new->count
= parent
->count
;
818 new->children_count
= parent
->children_count
;
819 parent
->children_count
= callchain_cumul_counts(new);
821 /* create a new child for the new branch if any */
822 if (idx_total
< cursor
->nr
) {
823 struct callchain_node
*first
;
824 struct callchain_list
*cnode
;
825 struct callchain_cursor_node
*node
;
826 struct rb_node
*p
, **pp
;
829 parent
->children_hit
+= period
;
831 parent
->children_count
+= 1;
833 node
= callchain_cursor_current(cursor
);
834 new = add_child(parent
, cursor
, period
);
839 * This is second child since we moved parent's children
840 * to new (first) child above.
842 p
= parent
->rb_root_in
.rb_node
;
843 first
= rb_entry(p
, struct callchain_node
, rb_node_in
);
844 cnode
= list_first_entry(&first
->val
, struct callchain_list
,
847 if (match_chain(node
, cnode
) == MATCH_LT
)
852 rb_link_node(&new->rb_node_in
, p
, pp
);
853 rb_insert_color(&new->rb_node_in
, &parent
->rb_root_in
);
855 parent
->hit
= period
;
861 static enum match_result
862 append_chain(struct callchain_node
*root
,
863 struct callchain_cursor
*cursor
,
867 append_chain_children(struct callchain_node
*root
,
868 struct callchain_cursor
*cursor
,
871 struct callchain_node
*rnode
;
872 struct callchain_cursor_node
*node
;
873 struct rb_node
**p
= &root
->rb_root_in
.rb_node
;
874 struct rb_node
*parent
= NULL
;
876 node
= callchain_cursor_current(cursor
);
880 /* lookup in childrens */
882 enum match_result ret
;
885 rnode
= rb_entry(parent
, struct callchain_node
, rb_node_in
);
887 /* If at least first entry matches, rely to children */
888 ret
= append_chain(rnode
, cursor
, period
);
890 goto inc_children_hit
;
891 if (ret
== MATCH_ERROR
)
895 p
= &parent
->rb_left
;
897 p
= &parent
->rb_right
;
899 /* nothing in children, add to the current node */
900 rnode
= add_child(root
, cursor
, period
);
904 rb_link_node(&rnode
->rb_node_in
, parent
, p
);
905 rb_insert_color(&rnode
->rb_node_in
, &root
->rb_root_in
);
908 root
->children_hit
+= period
;
909 root
->children_count
++;
913 static enum match_result
914 append_chain(struct callchain_node
*root
,
915 struct callchain_cursor
*cursor
,
918 struct callchain_list
*cnode
;
919 u64 start
= cursor
->pos
;
922 enum match_result cmp
= MATCH_ERROR
;
925 * Lookup in the current node
926 * If we have a symbol, then compare the start to match
927 * anywhere inside a function, unless function
930 list_for_each_entry(cnode
, &root
->val
, list
) {
931 struct callchain_cursor_node
*node
;
933 node
= callchain_cursor_current(cursor
);
937 cmp
= match_chain(node
, cnode
);
943 callchain_cursor_advance(cursor
);
946 /* matches not, relay no the parent */
948 WARN_ONCE(cmp
== MATCH_ERROR
, "Chain comparison error\n");
952 matches
= cursor
->pos
- start
;
954 /* we match only a part of the node. Split it and add the new chain */
955 if (matches
< root
->val_nr
) {
956 if (split_add_child(root
, cursor
, cnode
, start
, matches
,
963 /* we match 100% of the path, increment the hit */
964 if (matches
== root
->val_nr
&& cursor
->pos
== cursor
->nr
) {
970 /* We match the node and still have a part remaining */
971 if (append_chain_children(root
, cursor
, period
) < 0)
977 int callchain_append(struct callchain_root
*root
,
978 struct callchain_cursor
*cursor
,
984 callchain_cursor_commit(cursor
);
986 if (append_chain_children(&root
->node
, cursor
, period
) < 0)
989 if (cursor
->nr
> root
->max_depth
)
990 root
->max_depth
= cursor
->nr
;
996 merge_chain_branch(struct callchain_cursor
*cursor
,
997 struct callchain_node
*dst
, struct callchain_node
*src
)
999 struct callchain_cursor_node
**old_last
= cursor
->last
;
1000 struct callchain_node
*child
;
1001 struct callchain_list
*list
, *next_list
;
1003 int old_pos
= cursor
->nr
;
1006 list_for_each_entry_safe(list
, next_list
, &src
->val
, list
) {
1007 callchain_cursor_append(cursor
, list
->ip
, &list
->ms
,
1008 false, NULL
, 0, 0, 0, list
->srcline
);
1009 list_del_init(&list
->list
);
1010 map__zput(list
->ms
.map
);
1015 callchain_cursor_commit(cursor
);
1016 if (append_chain_children(dst
, cursor
, src
->hit
) < 0)
1020 n
= rb_first(&src
->rb_root_in
);
1022 child
= container_of(n
, struct callchain_node
, rb_node_in
);
1024 rb_erase(&child
->rb_node_in
, &src
->rb_root_in
);
1026 err
= merge_chain_branch(cursor
, dst
, child
);
1033 cursor
->nr
= old_pos
;
1034 cursor
->last
= old_last
;
1039 int callchain_merge(struct callchain_cursor
*cursor
,
1040 struct callchain_root
*dst
, struct callchain_root
*src
)
1042 return merge_chain_branch(cursor
, &dst
->node
, &src
->node
);
1045 int callchain_cursor_append(struct callchain_cursor
*cursor
,
1046 u64 ip
, struct map_symbol
*ms
,
1047 bool branch
, struct branch_flags
*flags
,
1048 int nr_loop_iter
, u64 iter_cycles
, u64 branch_from
,
1049 const char *srcline
)
1051 struct callchain_cursor_node
*node
= *cursor
->last
;
1054 node
= calloc(1, sizeof(*node
));
1058 *cursor
->last
= node
;
1062 map__zput(node
->ms
.map
);
1064 map__get(node
->ms
.map
);
1065 node
->branch
= branch
;
1066 node
->nr_loop_iter
= nr_loop_iter
;
1067 node
->iter_cycles
= iter_cycles
;
1068 node
->srcline
= srcline
;
1071 memcpy(&node
->branch_flags
, flags
,
1072 sizeof(struct branch_flags
));
1074 node
->branch_from
= branch_from
;
1077 cursor
->last
= &node
->next
;
1082 int sample__resolve_callchain(struct perf_sample
*sample
,
1083 struct callchain_cursor
*cursor
, struct symbol
**parent
,
1084 struct evsel
*evsel
, struct addr_location
*al
,
1087 if (sample
->callchain
== NULL
&& !symbol_conf
.show_branchflag_count
)
1090 if (symbol_conf
.use_callchain
|| symbol_conf
.cumulate_callchain
||
1091 perf_hpp_list
.parent
|| symbol_conf
.show_branchflag_count
) {
1092 return thread__resolve_callchain(al
->thread
, cursor
, evsel
, sample
,
1093 parent
, al
, max_stack
);
1098 int hist_entry__append_callchain(struct hist_entry
*he
, struct perf_sample
*sample
)
1100 if ((!symbol_conf
.use_callchain
|| sample
->callchain
== NULL
) &&
1101 !symbol_conf
.show_branchflag_count
)
1103 return callchain_append(he
->callchain
, &callchain_cursor
, sample
->period
);
1106 int fill_callchain_info(struct addr_location
*al
, struct callchain_cursor_node
*node
,
1107 bool hide_unresolved
)
1109 al
->maps
= node
->ms
.maps
;
1110 al
->map
= node
->ms
.map
;
1111 al
->sym
= node
->ms
.sym
;
1112 al
->srcline
= node
->srcline
;
1113 al
->addr
= node
->ip
;
1115 if (al
->sym
== NULL
) {
1116 if (hide_unresolved
)
1118 if (al
->map
== NULL
)
1122 if (al
->maps
== &al
->maps
->machine
->kmaps
) {
1123 if (machine__is_host(al
->maps
->machine
)) {
1124 al
->cpumode
= PERF_RECORD_MISC_KERNEL
;
1127 al
->cpumode
= PERF_RECORD_MISC_GUEST_KERNEL
;
1131 if (machine__is_host(al
->maps
->machine
)) {
1132 al
->cpumode
= PERF_RECORD_MISC_USER
;
1134 } else if (perf_guest
) {
1135 al
->cpumode
= PERF_RECORD_MISC_GUEST_USER
;
1138 al
->cpumode
= PERF_RECORD_MISC_HYPERVISOR
;
1147 char *callchain_list__sym_name(struct callchain_list
*cl
,
1148 char *bf
, size_t bfsize
, bool show_dso
)
1150 bool show_addr
= callchain_param
.key
== CCKEY_ADDRESS
;
1151 bool show_srcline
= show_addr
|| callchain_param
.key
== CCKEY_SRCLINE
;
1155 const char *inlined
= cl
->ms
.sym
->inlined
? " (inlined)" : "";
1157 if (show_srcline
&& cl
->srcline
)
1158 printed
= scnprintf(bf
, bfsize
, "%s %s%s",
1159 cl
->ms
.sym
->name
, cl
->srcline
,
1162 printed
= scnprintf(bf
, bfsize
, "%s%s",
1163 cl
->ms
.sym
->name
, inlined
);
1165 printed
= scnprintf(bf
, bfsize
, "%#" PRIx64
, cl
->ip
);
1168 scnprintf(bf
+ printed
, bfsize
- printed
, " %s",
1170 cl
->ms
.map
->dso
->short_name
:
1176 char *callchain_node__scnprintf_value(struct callchain_node
*node
,
1177 char *bf
, size_t bfsize
, u64 total
)
1179 double percent
= 0.0;
1180 u64 period
= callchain_cumul_hits(node
);
1181 unsigned count
= callchain_cumul_counts(node
);
1183 if (callchain_param
.mode
== CHAIN_FOLDED
) {
1185 count
= node
->count
;
1188 switch (callchain_param
.value
) {
1190 scnprintf(bf
, bfsize
, "%"PRIu64
, period
);
1193 scnprintf(bf
, bfsize
, "%u", count
);
1198 percent
= period
* 100.0 / total
;
1199 scnprintf(bf
, bfsize
, "%.2f%%", percent
);
1205 int callchain_node__fprintf_value(struct callchain_node
*node
,
1206 FILE *fp
, u64 total
)
1208 double percent
= 0.0;
1209 u64 period
= callchain_cumul_hits(node
);
1210 unsigned count
= callchain_cumul_counts(node
);
1212 if (callchain_param
.mode
== CHAIN_FOLDED
) {
1214 count
= node
->count
;
1217 switch (callchain_param
.value
) {
1219 return fprintf(fp
, "%"PRIu64
, period
);
1221 return fprintf(fp
, "%u", count
);
1225 percent
= period
* 100.0 / total
;
1226 return percent_color_fprintf(fp
, "%.2f%%", percent
);
1231 static void callchain_counts_value(struct callchain_node
*node
,
1232 u64
*branch_count
, u64
*predicted_count
,
1233 u64
*abort_count
, u64
*cycles_count
)
1235 struct callchain_list
*clist
;
1237 list_for_each_entry(clist
, &node
->val
, list
) {
1239 *branch_count
+= clist
->branch_count
;
1241 if (predicted_count
)
1242 *predicted_count
+= clist
->predicted_count
;
1245 *abort_count
+= clist
->abort_count
;
1248 *cycles_count
+= clist
->cycles_count
;
1252 static int callchain_node_branch_counts_cumul(struct callchain_node
*node
,
1254 u64
*predicted_count
,
1258 struct callchain_node
*child
;
1261 n
= rb_first(&node
->rb_root_in
);
1263 child
= rb_entry(n
, struct callchain_node
, rb_node_in
);
1266 callchain_node_branch_counts_cumul(child
, branch_count
,
1271 callchain_counts_value(child
, branch_count
,
1272 predicted_count
, abort_count
,
1279 int callchain_branch_counts(struct callchain_root
*root
,
1280 u64
*branch_count
, u64
*predicted_count
,
1281 u64
*abort_count
, u64
*cycles_count
)
1286 if (predicted_count
)
1287 *predicted_count
= 0;
1295 return callchain_node_branch_counts_cumul(&root
->node
,
1302 static int count_pri64_printf(int idx
, const char *str
, u64 value
, char *bf
, int bfsize
)
1306 printed
= scnprintf(bf
, bfsize
, "%s%s:%" PRId64
"", (idx
) ? " " : " (", str
, value
);
1311 static int count_float_printf(int idx
, const char *str
, float value
,
1312 char *bf
, int bfsize
, float threshold
)
1316 if (threshold
!= 0.0 && value
< threshold
)
1319 printed
= scnprintf(bf
, bfsize
, "%s%s:%.1f%%", (idx
) ? " " : " (", str
, value
);
1324 static int branch_to_str(char *bf
, int bfsize
,
1325 u64 branch_count
, u64 predicted_count
,
1327 struct branch_type_stat
*brtype_stat
)
1331 printed
= branch_type_str(brtype_stat
, bf
, bfsize
);
1335 if (predicted_count
< branch_count
) {
1336 printed
+= count_float_printf(i
++, "predicted",
1337 predicted_count
* 100.0 / branch_count
,
1338 bf
+ printed
, bfsize
- printed
, 0.0);
1342 printed
+= count_float_printf(i
++, "abort",
1343 abort_count
* 100.0 / branch_count
,
1344 bf
+ printed
, bfsize
- printed
, 0.1);
1348 printed
+= scnprintf(bf
+ printed
, bfsize
- printed
, ")");
1353 static int branch_from_str(char *bf
, int bfsize
,
1355 u64 cycles_count
, u64 iter_count
,
1356 u64 iter_cycles
, u64 from_count
)
1358 int printed
= 0, i
= 0;
1361 cycles
= cycles_count
/ branch_count
;
1363 printed
+= count_pri64_printf(i
++, "cycles",
1365 bf
+ printed
, bfsize
- printed
);
1368 if (iter_count
&& from_count
) {
1369 v
= iter_count
/ from_count
;
1371 printed
+= count_pri64_printf(i
++, "iter",
1372 v
, bf
+ printed
, bfsize
- printed
);
1374 printed
+= count_pri64_printf(i
++, "avg_cycles",
1375 iter_cycles
/ iter_count
,
1376 bf
+ printed
, bfsize
- printed
);
1381 printed
+= scnprintf(bf
+ printed
, bfsize
- printed
, ")");
1386 static int counts_str_build(char *bf
, int bfsize
,
1387 u64 branch_count
, u64 predicted_count
,
1388 u64 abort_count
, u64 cycles_count
,
1389 u64 iter_count
, u64 iter_cycles
,
1391 struct branch_type_stat
*brtype_stat
)
1395 if (branch_count
== 0)
1396 return scnprintf(bf
, bfsize
, " (calltrace)");
1398 if (brtype_stat
->branch_to
) {
1399 printed
= branch_to_str(bf
, bfsize
, branch_count
,
1400 predicted_count
, abort_count
, brtype_stat
);
1402 printed
= branch_from_str(bf
, bfsize
, branch_count
,
1403 cycles_count
, iter_count
, iter_cycles
,
1413 static int callchain_counts_printf(FILE *fp
, char *bf
, int bfsize
,
1414 u64 branch_count
, u64 predicted_count
,
1415 u64 abort_count
, u64 cycles_count
,
1416 u64 iter_count
, u64 iter_cycles
,
1418 struct branch_type_stat
*brtype_stat
)
1422 counts_str_build(str
, sizeof(str
), branch_count
,
1423 predicted_count
, abort_count
, cycles_count
,
1424 iter_count
, iter_cycles
, from_count
, brtype_stat
);
1427 return fprintf(fp
, "%s", str
);
1429 return scnprintf(bf
, bfsize
, "%s", str
);
1432 int callchain_list_counts__printf_value(struct callchain_list
*clist
,
1433 FILE *fp
, char *bf
, int bfsize
)
1435 u64 branch_count
, predicted_count
;
1436 u64 abort_count
, cycles_count
;
1437 u64 iter_count
, iter_cycles
;
1440 branch_count
= clist
->branch_count
;
1441 predicted_count
= clist
->predicted_count
;
1442 abort_count
= clist
->abort_count
;
1443 cycles_count
= clist
->cycles_count
;
1444 iter_count
= clist
->iter_count
;
1445 iter_cycles
= clist
->iter_cycles
;
1446 from_count
= clist
->from_count
;
1448 return callchain_counts_printf(fp
, bf
, bfsize
, branch_count
,
1449 predicted_count
, abort_count
,
1450 cycles_count
, iter_count
, iter_cycles
,
1451 from_count
, &clist
->brtype_stat
);
1454 static void free_callchain_node(struct callchain_node
*node
)
1456 struct callchain_list
*list
, *tmp
;
1457 struct callchain_node
*child
;
1460 list_for_each_entry_safe(list
, tmp
, &node
->parent_val
, list
) {
1461 list_del_init(&list
->list
);
1462 map__zput(list
->ms
.map
);
1466 list_for_each_entry_safe(list
, tmp
, &node
->val
, list
) {
1467 list_del_init(&list
->list
);
1468 map__zput(list
->ms
.map
);
1472 n
= rb_first(&node
->rb_root_in
);
1474 child
= container_of(n
, struct callchain_node
, rb_node_in
);
1476 rb_erase(&child
->rb_node_in
, &node
->rb_root_in
);
1478 free_callchain_node(child
);
1483 void free_callchain(struct callchain_root
*root
)
1485 if (!symbol_conf
.use_callchain
)
1488 free_callchain_node(&root
->node
);
1491 static u64
decay_callchain_node(struct callchain_node
*node
)
1493 struct callchain_node
*child
;
1497 n
= rb_first(&node
->rb_root_in
);
1499 child
= container_of(n
, struct callchain_node
, rb_node_in
);
1501 child_hits
+= decay_callchain_node(child
);
1505 node
->hit
= (node
->hit
* 7) / 8;
1506 node
->children_hit
= child_hits
;
1511 void decay_callchain(struct callchain_root
*root
)
1513 if (!symbol_conf
.use_callchain
)
1516 decay_callchain_node(&root
->node
);
1519 int callchain_node__make_parent_list(struct callchain_node
*node
)
1521 struct callchain_node
*parent
= node
->parent
;
1522 struct callchain_list
*chain
, *new;
1526 list_for_each_entry_reverse(chain
, &parent
->val
, list
) {
1527 new = malloc(sizeof(*new));
1531 new->has_children
= false;
1532 map__get(new->ms
.map
);
1533 list_add_tail(&new->list
, &head
);
1535 parent
= parent
->parent
;
1538 list_for_each_entry_safe_reverse(chain
, new, &head
, list
)
1539 list_move_tail(&chain
->list
, &node
->parent_val
);
1541 if (!list_empty(&node
->parent_val
)) {
1542 chain
= list_first_entry(&node
->parent_val
, struct callchain_list
, list
);
1543 chain
->has_children
= rb_prev(&node
->rb_node
) || rb_next(&node
->rb_node
);
1545 chain
= list_first_entry(&node
->val
, struct callchain_list
, list
);
1546 chain
->has_children
= false;
1551 list_for_each_entry_safe(chain
, new, &head
, list
) {
1552 list_del_init(&chain
->list
);
1553 map__zput(chain
->ms
.map
);
1559 int callchain_cursor__copy(struct callchain_cursor
*dst
,
1560 struct callchain_cursor
*src
)
1564 callchain_cursor_reset(dst
);
1565 callchain_cursor_commit(src
);
1568 struct callchain_cursor_node
*node
;
1570 node
= callchain_cursor_current(src
);
1574 rc
= callchain_cursor_append(dst
, node
->ip
, &node
->ms
,
1575 node
->branch
, &node
->branch_flags
,
1578 node
->branch_from
, node
->srcline
);
1582 callchain_cursor_advance(src
);
1589 * Initialize a cursor before adding entries inside, but keep
1590 * the previously allocated entries as a cache.
1592 void callchain_cursor_reset(struct callchain_cursor
*cursor
)
1594 struct callchain_cursor_node
*node
;
1597 cursor
->last
= &cursor
->first
;
1599 for (node
= cursor
->first
; node
!= NULL
; node
= node
->next
)
1600 map__zput(node
->ms
.map
);
1603 void callchain_param_setup(u64 sample_type
)
1605 if (symbol_conf
.use_callchain
|| symbol_conf
.cumulate_callchain
) {
1606 if ((sample_type
& PERF_SAMPLE_REGS_USER
) &&
1607 (sample_type
& PERF_SAMPLE_STACK_USER
)) {
1608 callchain_param
.record_mode
= CALLCHAIN_DWARF
;
1609 dwarf_callchain_users
= true;
1610 } else if (sample_type
& PERF_SAMPLE_BRANCH_STACK
)
1611 callchain_param
.record_mode
= CALLCHAIN_LBR
;
1613 callchain_param
.record_mode
= CALLCHAIN_FP
;