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.
26 #include "callchain.h"
29 #define CALLCHAIN_PARAM_DEFAULT \
30 .mode = CHAIN_GRAPH_ABS, \
32 .order = ORDER_CALLEE, \
33 .key = CCKEY_FUNCTION, \
34 .value = CCVAL_PERCENT, \
36 struct callchain_param callchain_param = {
37 CALLCHAIN_PARAM_DEFAULT
41 * Are there any events usind DWARF callchains?
45 * -e cycles/call-graph=dwarf/
47 bool dwarf_callchain_users;
49 struct callchain_param callchain_param_default = {
50 CALLCHAIN_PARAM_DEFAULT
53 __thread struct callchain_cursor callchain_cursor;
55 int parse_callchain_record_opt(const char *arg, struct callchain_param *param)
57 return parse_callchain_record(arg, param);
60 static int parse_callchain_mode(const char *value)
62 if (!strncmp(value, "graph", strlen(value))) {
63 callchain_param.mode = CHAIN_GRAPH_ABS;
66 if (!strncmp(value, "flat", strlen(value))) {
67 callchain_param.mode = CHAIN_FLAT;
70 if (!strncmp(value, "fractal", strlen(value))) {
71 callchain_param.mode = CHAIN_GRAPH_REL;
74 if (!strncmp(value, "folded", strlen(value))) {
75 callchain_param.mode = CHAIN_FOLDED;
81 static int parse_callchain_order(const char *value)
83 if (!strncmp(value, "caller", strlen(value))) {
84 callchain_param.order = ORDER_CALLER;
85 callchain_param.order_set = true;
88 if (!strncmp(value, "callee", strlen(value))) {
89 callchain_param.order = ORDER_CALLEE;
90 callchain_param.order_set = true;
96 static int parse_callchain_sort_key(const char *value)
98 if (!strncmp(value, "function", strlen(value))) {
99 callchain_param.key = CCKEY_FUNCTION;
102 if (!strncmp(value, "address", strlen(value))) {
103 callchain_param.key = CCKEY_ADDRESS;
106 if (!strncmp(value, "srcline", strlen(value))) {
107 callchain_param.key = CCKEY_SRCLINE;
110 if (!strncmp(value, "branch", strlen(value))) {
111 callchain_param.branch_callstack = 1;
117 static int parse_callchain_value(const char *value)
119 if (!strncmp(value, "percent", strlen(value))) {
120 callchain_param.value = CCVAL_PERCENT;
123 if (!strncmp(value, "period", strlen(value))) {
124 callchain_param.value = CCVAL_PERIOD;
127 if (!strncmp(value, "count", strlen(value))) {
128 callchain_param.value = CCVAL_COUNT;
134 static int get_stack_size(const char *str, unsigned long *_size)
138 unsigned long max_size = round_down(USHRT_MAX, sizeof(u64));
140 size = strtoul(str, &endptr, 0);
146 size = round_up(size, sizeof(u64));
147 if (!size || size > max_size)
155 pr_err("callchain: Incorrect stack dump size (max %ld): %s\n",
161 __parse_callchain_report_opt(const char *arg, bool allow_record_opt)
164 char *endptr, *saveptr = NULL;
165 bool minpcnt_set = false;
166 bool record_opt_set = false;
167 bool try_stack_size = false;
169 callchain_param.enabled = true;
170 symbol_conf.use_callchain = true;
175 while ((tok = strtok_r((char *)arg, ",", &saveptr)) != NULL) {
176 if (!strncmp(tok, "none", strlen(tok))) {
177 callchain_param.mode = CHAIN_NONE;
178 callchain_param.enabled = false;
179 symbol_conf.use_callchain = false;
183 if (!parse_callchain_mode(tok) ||
184 !parse_callchain_order(tok) ||
185 !parse_callchain_sort_key(tok) ||
186 !parse_callchain_value(tok)) {
187 /* parsing ok - move on to the next */
188 try_stack_size = false;
190 } else if (allow_record_opt && !record_opt_set) {
191 if (parse_callchain_record(tok, &callchain_param))
194 /* assume that number followed by 'dwarf' is stack size */
195 if (callchain_param.record_mode == CALLCHAIN_DWARF)
196 try_stack_size = true;
198 record_opt_set = true;
203 if (try_stack_size) {
204 unsigned long size = 0;
206 if (get_stack_size(tok, &size) < 0)
208 callchain_param.dump_size = size;
209 try_stack_size = false;
210 } else if (!minpcnt_set) {
211 /* try to get the min percent */
212 callchain_param.min_percent = strtod(tok, &endptr);
217 /* try print limit at last */
218 callchain_param.print_limit = strtoul(tok, &endptr, 0);
226 if (callchain_register_param(&callchain_param) < 0) {
227 pr_err("Can't register callchain params\n");
233 int parse_callchain_report_opt(const char *arg)
235 return __parse_callchain_report_opt(arg, false);
238 int parse_callchain_top_opt(const char *arg)
240 return __parse_callchain_report_opt(arg, true);
243 int parse_callchain_record(const char *arg, struct callchain_param *param)
245 char *tok, *name, *saveptr = NULL;
249 /* We need buffer that we know we can write to. */
250 buf = malloc(strlen(arg) + 1);
256 tok = strtok_r((char *)buf, ",", &saveptr);
257 name = tok ? : (char *)buf;
260 /* Framepointer style */
261 if (!strncmp(name, "fp", sizeof("fp"))) {
262 if (!strtok_r(NULL, ",", &saveptr)) {
263 param->record_mode = CALLCHAIN_FP;
266 pr_err("callchain: No more arguments "
267 "needed for --call-graph fp\n");
271 } else if (!strncmp(name, "dwarf", sizeof("dwarf"))) {
272 const unsigned long default_stack_dump_size = 8192;
275 param->record_mode = CALLCHAIN_DWARF;
276 param->dump_size = default_stack_dump_size;
277 dwarf_callchain_users = true;
279 tok = strtok_r(NULL, ",", &saveptr);
281 unsigned long size = 0;
283 ret = get_stack_size(tok, &size);
284 param->dump_size = size;
286 } else if (!strncmp(name, "lbr", sizeof("lbr"))) {
287 if (!strtok_r(NULL, ",", &saveptr)) {
288 param->record_mode = CALLCHAIN_LBR;
291 pr_err("callchain: No more arguments "
292 "needed for --call-graph lbr\n");
295 pr_err("callchain: Unknown --call-graph option "
306 int perf_callchain_config(const char *var, const char *value)
310 if (!strstarts(var, "call-graph."))
312 var += sizeof("call-graph.") - 1;
314 if (!strcmp(var, "record-mode"))
315 return parse_callchain_record_opt(value, &callchain_param);
316 if (!strcmp(var, "dump-size")) {
317 unsigned long size = 0;
320 ret = get_stack_size(value, &size);
321 callchain_param.dump_size = size;
325 if (!strcmp(var, "print-type")){
327 ret = parse_callchain_mode(value);
329 pr_err("Invalid callchain mode: %s\n", value);
332 if (!strcmp(var, "order")){
334 ret = parse_callchain_order(value);
336 pr_err("Invalid callchain order: %s\n", value);
339 if (!strcmp(var, "sort-key")){
341 ret = parse_callchain_sort_key(value);
343 pr_err("Invalid callchain sort key: %s\n", value);
346 if (!strcmp(var, "threshold")) {
347 callchain_param.min_percent = strtod(value, &endptr);
348 if (value == endptr) {
349 pr_err("Invalid callchain threshold: %s\n", value);
353 if (!strcmp(var, "print-limit")) {
354 callchain_param.print_limit = strtod(value, &endptr);
355 if (value == endptr) {
356 pr_err("Invalid callchain print limit: %s\n", value);
365 rb_insert_callchain(struct rb_root *root, struct callchain_node *chain,
366 enum chain_mode mode)
368 struct rb_node **p = &root->rb_node;
369 struct rb_node *parent = NULL;
370 struct callchain_node *rnode;
371 u64 chain_cumul = callchain_cumul_hits(chain);
377 rnode = rb_entry(parent, struct callchain_node, rb_node);
378 rnode_cumul = callchain_cumul_hits(rnode);
383 if (rnode->hit < chain->hit)
388 case CHAIN_GRAPH_ABS: /* Falldown */
389 case CHAIN_GRAPH_REL:
390 if (rnode_cumul < chain_cumul)
401 rb_link_node(&chain->rb_node, parent, p);
402 rb_insert_color(&chain->rb_node, root);
406 __sort_chain_flat(struct rb_root *rb_root, struct callchain_node *node,
410 struct callchain_node *child;
412 n = rb_first(&node->rb_root_in);
414 child = rb_entry(n, struct callchain_node, rb_node_in);
417 __sort_chain_flat(rb_root, child, min_hit);
420 if (node->hit && node->hit >= min_hit)
421 rb_insert_callchain(rb_root, node, CHAIN_FLAT);
425 * Once we get every callchains from the stream, we can now
429 sort_chain_flat(struct rb_root *rb_root, struct callchain_root *root,
430 u64 min_hit, struct callchain_param *param __maybe_unused)
433 __sort_chain_flat(rb_root, &root->node, min_hit);
436 static void __sort_chain_graph_abs(struct callchain_node *node,
440 struct callchain_node *child;
442 node->rb_root = RB_ROOT;
443 n = rb_first(&node->rb_root_in);
446 child = rb_entry(n, struct callchain_node, rb_node_in);
449 __sort_chain_graph_abs(child, min_hit);
450 if (callchain_cumul_hits(child) >= min_hit)
451 rb_insert_callchain(&node->rb_root, child,
457 sort_chain_graph_abs(struct rb_root *rb_root, struct callchain_root *chain_root,
458 u64 min_hit, struct callchain_param *param __maybe_unused)
460 __sort_chain_graph_abs(&chain_root->node, min_hit);
461 rb_root->rb_node = chain_root->node.rb_root.rb_node;
464 static void __sort_chain_graph_rel(struct callchain_node *node,
468 struct callchain_node *child;
471 node->rb_root = RB_ROOT;
472 min_hit = ceil(node->children_hit * min_percent);
474 n = rb_first(&node->rb_root_in);
476 child = rb_entry(n, struct callchain_node, rb_node_in);
479 __sort_chain_graph_rel(child, min_percent);
480 if (callchain_cumul_hits(child) >= min_hit)
481 rb_insert_callchain(&node->rb_root, child,
487 sort_chain_graph_rel(struct rb_root *rb_root, struct callchain_root *chain_root,
488 u64 min_hit __maybe_unused, struct callchain_param *param)
490 __sort_chain_graph_rel(&chain_root->node, param->min_percent / 100.0);
491 rb_root->rb_node = chain_root->node.rb_root.rb_node;
494 int callchain_register_param(struct callchain_param *param)
496 switch (param->mode) {
497 case CHAIN_GRAPH_ABS:
498 param->sort = sort_chain_graph_abs;
500 case CHAIN_GRAPH_REL:
501 param->sort = sort_chain_graph_rel;
505 param->sort = sort_chain_flat;
515 * Create a child for a parent. If inherit_children, then the new child
516 * will become the new parent of it's parent children
518 static struct callchain_node *
519 create_child(struct callchain_node *parent, bool inherit_children)
521 struct callchain_node *new;
523 new = zalloc(sizeof(*new));
525 perror("not enough memory to create child for code path tree");
528 new->parent = parent;
529 INIT_LIST_HEAD(&new->val);
530 INIT_LIST_HEAD(&new->parent_val);
532 if (inherit_children) {
534 struct callchain_node *child;
536 new->rb_root_in = parent->rb_root_in;
537 parent->rb_root_in = RB_ROOT;
539 n = rb_first(&new->rb_root_in);
541 child = rb_entry(n, struct callchain_node, rb_node_in);
546 /* make it the first child */
547 rb_link_node(&new->rb_node_in, NULL, &parent->rb_root_in.rb_node);
548 rb_insert_color(&new->rb_node_in, &parent->rb_root_in);
556 * Fill the node with callchain values
559 fill_node(struct callchain_node *node, struct callchain_cursor *cursor)
561 struct callchain_cursor_node *cursor_node;
563 node->val_nr = cursor->nr - cursor->pos;
565 pr_warning("Warning: empty node in callchain tree\n");
567 cursor_node = callchain_cursor_current(cursor);
569 while (cursor_node) {
570 struct callchain_list *call;
572 call = zalloc(sizeof(*call));
574 perror("not enough memory for the code path tree");
577 call->ip = cursor_node->ip;
578 call->ms.sym = cursor_node->sym;
579 call->ms.map = map__get(cursor_node->map);
581 if (cursor_node->branch) {
582 call->branch_count = 1;
584 if (cursor_node->branch_from) {
586 * branch_from is set with value somewhere else
587 * to imply it's "to" of a branch.
589 call->brtype_stat.branch_to = true;
591 if (cursor_node->branch_flags.predicted)
592 call->predicted_count = 1;
594 if (cursor_node->branch_flags.abort)
595 call->abort_count = 1;
597 branch_type_count(&call->brtype_stat,
598 &cursor_node->branch_flags,
599 cursor_node->branch_from,
603 * It's "from" of a branch
605 call->brtype_stat.branch_to = false;
607 cursor_node->branch_flags.cycles;
608 call->iter_count = cursor_node->nr_loop_iter;
609 call->iter_cycles = cursor_node->iter_cycles;
613 list_add_tail(&call->list, &node->val);
615 callchain_cursor_advance(cursor);
616 cursor_node = callchain_cursor_current(cursor);
621 static struct callchain_node *
622 add_child(struct callchain_node *parent,
623 struct callchain_cursor *cursor,
626 struct callchain_node *new;
628 new = create_child(parent, false);
632 if (fill_node(new, cursor) < 0) {
633 struct callchain_list *call, *tmp;
635 list_for_each_entry_safe(call, tmp, &new->val, list) {
636 list_del(&call->list);
637 map__zput(call->ms.map);
644 new->children_hit = 0;
646 new->children_count = 0;
658 static enum match_result match_chain_srcline(struct callchain_cursor_node *node,
659 struct callchain_list *cnode)
663 enum match_result ret = MATCH_EQ;
667 left = get_srcline(cnode->ms.map->dso,
668 map__rip_2objdump(cnode->ms.map, cnode->ip),
669 cnode->ms.sym, true, false);
671 right = get_srcline(node->map->dso,
672 map__rip_2objdump(node->map, node->ip),
673 node->sym, true, false);
676 cmp = strcmp(left, right);
677 else if (!left && right)
679 else if (left && !right)
681 else if (cnode->ip == node->ip)
684 cmp = (cnode->ip < node->ip) ? -1 : 1;
687 ret = cmp < 0 ? MATCH_LT : MATCH_GT;
694 static enum match_result match_chain(struct callchain_cursor_node *node,
695 struct callchain_list *cnode)
697 struct symbol *sym = node->sym;
699 struct dso *left_dso = NULL;
700 struct dso *right_dso = NULL;
702 if (callchain_param.key == CCKEY_SRCLINE) {
703 enum match_result match = match_chain_srcline(node, cnode);
705 if (match != MATCH_ERROR)
709 if (cnode->ms.sym && sym && callchain_param.key == CCKEY_FUNCTION) {
710 left = cnode->ms.sym->start;
712 left_dso = cnode->ms.map->dso;
713 right_dso = node->map->dso;
719 if (left == right && left_dso == right_dso) {
721 cnode->branch_count++;
723 if (node->branch_from) {
725 * It's "to" of a branch
727 cnode->brtype_stat.branch_to = true;
729 if (node->branch_flags.predicted)
730 cnode->predicted_count++;
732 if (node->branch_flags.abort)
733 cnode->abort_count++;
735 branch_type_count(&cnode->brtype_stat,
741 * It's "from" of a branch
743 cnode->brtype_stat.branch_to = false;
744 cnode->cycles_count +=
745 node->branch_flags.cycles;
746 cnode->iter_count += node->nr_loop_iter;
747 cnode->iter_cycles += node->iter_cycles;
754 return left > right ? MATCH_GT : MATCH_LT;
758 * Split the parent in two parts (a new child is created) and
759 * give a part of its callchain to the created child.
760 * Then create another child to host the given callchain of new branch
763 split_add_child(struct callchain_node *parent,
764 struct callchain_cursor *cursor,
765 struct callchain_list *to_split,
766 u64 idx_parents, u64 idx_local, u64 period)
768 struct callchain_node *new;
769 struct list_head *old_tail;
770 unsigned int idx_total = idx_parents + idx_local;
773 new = create_child(parent, true);
777 /* split the callchain and move a part to the new child */
778 old_tail = parent->val.prev;
779 list_del_range(&to_split->list, old_tail);
780 new->val.next = &to_split->list;
781 new->val.prev = old_tail;
782 to_split->list.prev = &new->val;
783 old_tail->next = &new->val;
786 new->hit = parent->hit;
787 new->children_hit = parent->children_hit;
788 parent->children_hit = callchain_cumul_hits(new);
789 new->val_nr = parent->val_nr - idx_local;
790 parent->val_nr = idx_local;
791 new->count = parent->count;
792 new->children_count = parent->children_count;
793 parent->children_count = callchain_cumul_counts(new);
795 /* create a new child for the new branch if any */
796 if (idx_total < cursor->nr) {
797 struct callchain_node *first;
798 struct callchain_list *cnode;
799 struct callchain_cursor_node *node;
800 struct rb_node *p, **pp;
803 parent->children_hit += period;
805 parent->children_count += 1;
807 node = callchain_cursor_current(cursor);
808 new = add_child(parent, cursor, period);
813 * This is second child since we moved parent's children
814 * to new (first) child above.
816 p = parent->rb_root_in.rb_node;
817 first = rb_entry(p, struct callchain_node, rb_node_in);
818 cnode = list_first_entry(&first->val, struct callchain_list,
821 if (match_chain(node, cnode) == MATCH_LT)
826 rb_link_node(&new->rb_node_in, p, pp);
827 rb_insert_color(&new->rb_node_in, &parent->rb_root_in);
829 parent->hit = period;
835 static enum match_result
836 append_chain(struct callchain_node *root,
837 struct callchain_cursor *cursor,
841 append_chain_children(struct callchain_node *root,
842 struct callchain_cursor *cursor,
845 struct callchain_node *rnode;
846 struct callchain_cursor_node *node;
847 struct rb_node **p = &root->rb_root_in.rb_node;
848 struct rb_node *parent = NULL;
850 node = callchain_cursor_current(cursor);
854 /* lookup in childrens */
856 enum match_result ret;
859 rnode = rb_entry(parent, struct callchain_node, rb_node_in);
861 /* If at least first entry matches, rely to children */
862 ret = append_chain(rnode, cursor, period);
864 goto inc_children_hit;
865 if (ret == MATCH_ERROR)
869 p = &parent->rb_left;
871 p = &parent->rb_right;
873 /* nothing in children, add to the current node */
874 rnode = add_child(root, cursor, period);
878 rb_link_node(&rnode->rb_node_in, parent, p);
879 rb_insert_color(&rnode->rb_node_in, &root->rb_root_in);
882 root->children_hit += period;
883 root->children_count++;
887 static enum match_result
888 append_chain(struct callchain_node *root,
889 struct callchain_cursor *cursor,
892 struct callchain_list *cnode;
893 u64 start = cursor->pos;
896 enum match_result cmp = MATCH_ERROR;
899 * Lookup in the current node
900 * If we have a symbol, then compare the start to match
901 * anywhere inside a function, unless function
904 list_for_each_entry(cnode, &root->val, list) {
905 struct callchain_cursor_node *node;
907 node = callchain_cursor_current(cursor);
911 cmp = match_chain(node, cnode);
917 callchain_cursor_advance(cursor);
920 /* matches not, relay no the parent */
922 WARN_ONCE(cmp == MATCH_ERROR, "Chain comparison error\n");
926 matches = cursor->pos - start;
928 /* we match only a part of the node. Split it and add the new chain */
929 if (matches < root->val_nr) {
930 if (split_add_child(root, cursor, cnode, start, matches,
937 /* we match 100% of the path, increment the hit */
938 if (matches == root->val_nr && cursor->pos == cursor->nr) {
944 /* We match the node and still have a part remaining */
945 if (append_chain_children(root, cursor, period) < 0)
951 int callchain_append(struct callchain_root *root,
952 struct callchain_cursor *cursor,
958 callchain_cursor_commit(cursor);
960 if (append_chain_children(&root->node, cursor, period) < 0)
963 if (cursor->nr > root->max_depth)
964 root->max_depth = cursor->nr;
970 merge_chain_branch(struct callchain_cursor *cursor,
971 struct callchain_node *dst, struct callchain_node *src)
973 struct callchain_cursor_node **old_last = cursor->last;
974 struct callchain_node *child;
975 struct callchain_list *list, *next_list;
977 int old_pos = cursor->nr;
980 list_for_each_entry_safe(list, next_list, &src->val, list) {
981 callchain_cursor_append(cursor, list->ip,
982 list->ms.map, list->ms.sym,
983 false, NULL, 0, 0, 0);
984 list_del(&list->list);
985 map__zput(list->ms.map);
990 callchain_cursor_commit(cursor);
991 if (append_chain_children(dst, cursor, src->hit) < 0)
995 n = rb_first(&src->rb_root_in);
997 child = container_of(n, struct callchain_node, rb_node_in);
999 rb_erase(&child->rb_node_in, &src->rb_root_in);
1001 err = merge_chain_branch(cursor, dst, child);
1008 cursor->nr = old_pos;
1009 cursor->last = old_last;
1014 int callchain_merge(struct callchain_cursor *cursor,
1015 struct callchain_root *dst, struct callchain_root *src)
1017 return merge_chain_branch(cursor, &dst->node, &src->node);
1020 int callchain_cursor_append(struct callchain_cursor *cursor,
1021 u64 ip, struct map *map, struct symbol *sym,
1022 bool branch, struct branch_flags *flags,
1023 int nr_loop_iter, u64 iter_cycles, u64 branch_from)
1025 struct callchain_cursor_node *node = *cursor->last;
1028 node = calloc(1, sizeof(*node));
1032 *cursor->last = node;
1036 map__zput(node->map);
1037 node->map = map__get(map);
1039 node->branch = branch;
1040 node->nr_loop_iter = nr_loop_iter;
1041 node->iter_cycles = iter_cycles;
1044 memcpy(&node->branch_flags, flags,
1045 sizeof(struct branch_flags));
1047 node->branch_from = branch_from;
1050 cursor->last = &node->next;
1055 int sample__resolve_callchain(struct perf_sample *sample,
1056 struct callchain_cursor *cursor, struct symbol **parent,
1057 struct perf_evsel *evsel, struct addr_location *al,
1060 if (sample->callchain == NULL && !symbol_conf.show_branchflag_count)
1063 if (symbol_conf.use_callchain || symbol_conf.cumulate_callchain ||
1064 perf_hpp_list.parent || symbol_conf.show_branchflag_count) {
1065 return thread__resolve_callchain(al->thread, cursor, evsel, sample,
1066 parent, al, max_stack);
1071 int hist_entry__append_callchain(struct hist_entry *he, struct perf_sample *sample)
1073 if ((!symbol_conf.use_callchain || sample->callchain == NULL) &&
1074 !symbol_conf.show_branchflag_count)
1076 return callchain_append(he->callchain, &callchain_cursor, sample->period);
1079 int fill_callchain_info(struct addr_location *al, struct callchain_cursor_node *node,
1080 bool hide_unresolved)
1082 al->map = node->map;
1083 al->sym = node->sym;
1085 al->addr = node->map->map_ip(node->map, node->ip);
1087 al->addr = node->ip;
1089 if (al->sym == NULL) {
1090 if (hide_unresolved)
1092 if (al->map == NULL)
1096 if (al->map->groups == &al->machine->kmaps) {
1097 if (machine__is_host(al->machine)) {
1098 al->cpumode = PERF_RECORD_MISC_KERNEL;
1101 al->cpumode = PERF_RECORD_MISC_GUEST_KERNEL;
1105 if (machine__is_host(al->machine)) {
1106 al->cpumode = PERF_RECORD_MISC_USER;
1108 } else if (perf_guest) {
1109 al->cpumode = PERF_RECORD_MISC_GUEST_USER;
1112 al->cpumode = PERF_RECORD_MISC_HYPERVISOR;
1121 char *callchain_list__sym_name(struct callchain_list *cl,
1122 char *bf, size_t bfsize, bool show_dso)
1124 bool show_addr = callchain_param.key == CCKEY_ADDRESS;
1125 bool show_srcline = show_addr || callchain_param.key == CCKEY_SRCLINE;
1129 if (show_srcline && cl->ms.map && !cl->srcline)
1130 cl->srcline = get_srcline(cl->ms.map->dso,
1131 map__rip_2objdump(cl->ms.map,
1133 cl->ms.sym, false, show_addr);
1135 printed = scnprintf(bf, bfsize, "%s %s",
1136 cl->ms.sym->name, cl->srcline);
1138 printed = scnprintf(bf, bfsize, "%s", cl->ms.sym->name);
1140 printed = scnprintf(bf, bfsize, "%#" PRIx64, cl->ip);
1143 scnprintf(bf + printed, bfsize - printed, " %s",
1145 cl->ms.map->dso->short_name :
1151 char *callchain_node__scnprintf_value(struct callchain_node *node,
1152 char *bf, size_t bfsize, u64 total)
1154 double percent = 0.0;
1155 u64 period = callchain_cumul_hits(node);
1156 unsigned count = callchain_cumul_counts(node);
1158 if (callchain_param.mode == CHAIN_FOLDED) {
1160 count = node->count;
1163 switch (callchain_param.value) {
1165 scnprintf(bf, bfsize, "%"PRIu64, period);
1168 scnprintf(bf, bfsize, "%u", count);
1173 percent = period * 100.0 / total;
1174 scnprintf(bf, bfsize, "%.2f%%", percent);
1180 int callchain_node__fprintf_value(struct callchain_node *node,
1181 FILE *fp, u64 total)
1183 double percent = 0.0;
1184 u64 period = callchain_cumul_hits(node);
1185 unsigned count = callchain_cumul_counts(node);
1187 if (callchain_param.mode == CHAIN_FOLDED) {
1189 count = node->count;
1192 switch (callchain_param.value) {
1194 return fprintf(fp, "%"PRIu64, period);
1196 return fprintf(fp, "%u", count);
1200 percent = period * 100.0 / total;
1201 return percent_color_fprintf(fp, "%.2f%%", percent);
1206 static void callchain_counts_value(struct callchain_node *node,
1207 u64 *branch_count, u64 *predicted_count,
1208 u64 *abort_count, u64 *cycles_count)
1210 struct callchain_list *clist;
1212 list_for_each_entry(clist, &node->val, list) {
1214 *branch_count += clist->branch_count;
1216 if (predicted_count)
1217 *predicted_count += clist->predicted_count;
1220 *abort_count += clist->abort_count;
1223 *cycles_count += clist->cycles_count;
1227 static int callchain_node_branch_counts_cumul(struct callchain_node *node,
1229 u64 *predicted_count,
1233 struct callchain_node *child;
1236 n = rb_first(&node->rb_root_in);
1238 child = rb_entry(n, struct callchain_node, rb_node_in);
1241 callchain_node_branch_counts_cumul(child, branch_count,
1246 callchain_counts_value(child, branch_count,
1247 predicted_count, abort_count,
1254 int callchain_branch_counts(struct callchain_root *root,
1255 u64 *branch_count, u64 *predicted_count,
1256 u64 *abort_count, u64 *cycles_count)
1261 if (predicted_count)
1262 *predicted_count = 0;
1270 return callchain_node_branch_counts_cumul(&root->node,
1277 static int count_pri64_printf(int idx, const char *str, u64 value, char *bf, int bfsize)
1281 printed = scnprintf(bf, bfsize, "%s%s:%" PRId64 "", (idx) ? " " : " (", str, value);
1286 static int count_float_printf(int idx, const char *str, float value,
1287 char *bf, int bfsize, float threshold)
1291 if (threshold != 0.0 && value < threshold)
1294 printed = scnprintf(bf, bfsize, "%s%s:%.1f%%", (idx) ? " " : " (", str, value);
1299 static int branch_to_str(char *bf, int bfsize,
1300 u64 branch_count, u64 predicted_count,
1302 struct branch_type_stat *brtype_stat)
1306 printed = branch_type_str(brtype_stat, bf, bfsize);
1310 if (predicted_count < branch_count) {
1311 printed += count_float_printf(i++, "predicted",
1312 predicted_count * 100.0 / branch_count,
1313 bf + printed, bfsize - printed, 0.0);
1317 printed += count_float_printf(i++, "abort",
1318 abort_count * 100.0 / branch_count,
1319 bf + printed, bfsize - printed, 0.1);
1323 printed += scnprintf(bf + printed, bfsize - printed, ")");
1328 static int branch_from_str(char *bf, int bfsize,
1330 u64 cycles_count, u64 iter_count,
1333 int printed = 0, i = 0;
1336 cycles = cycles_count / branch_count;
1338 printed += count_pri64_printf(i++, "cycles",
1340 bf + printed, bfsize - printed);
1344 printed += count_pri64_printf(i++, "iter",
1346 bf + printed, bfsize - printed);
1348 printed += count_pri64_printf(i++, "avg_cycles",
1349 iter_cycles / iter_count,
1350 bf + printed, bfsize - printed);
1354 printed += scnprintf(bf + printed, bfsize - printed, ")");
1359 static int counts_str_build(char *bf, int bfsize,
1360 u64 branch_count, u64 predicted_count,
1361 u64 abort_count, u64 cycles_count,
1362 u64 iter_count, u64 iter_cycles,
1363 struct branch_type_stat *brtype_stat)
1367 if (branch_count == 0)
1368 return scnprintf(bf, bfsize, " (calltrace)");
1370 if (brtype_stat->branch_to) {
1371 printed = branch_to_str(bf, bfsize, branch_count,
1372 predicted_count, abort_count, brtype_stat);
1374 printed = branch_from_str(bf, bfsize, branch_count,
1375 cycles_count, iter_count, iter_cycles);
1384 static int callchain_counts_printf(FILE *fp, char *bf, int bfsize,
1385 u64 branch_count, u64 predicted_count,
1386 u64 abort_count, u64 cycles_count,
1387 u64 iter_count, u64 iter_cycles,
1388 struct branch_type_stat *brtype_stat)
1392 counts_str_build(str, sizeof(str), branch_count,
1393 predicted_count, abort_count, cycles_count,
1394 iter_count, iter_cycles, brtype_stat);
1397 return fprintf(fp, "%s", str);
1399 return scnprintf(bf, bfsize, "%s", str);
1402 int callchain_list_counts__printf_value(struct callchain_list *clist,
1403 FILE *fp, char *bf, int bfsize)
1405 u64 branch_count, predicted_count;
1406 u64 abort_count, cycles_count;
1407 u64 iter_count, iter_cycles;
1409 branch_count = clist->branch_count;
1410 predicted_count = clist->predicted_count;
1411 abort_count = clist->abort_count;
1412 cycles_count = clist->cycles_count;
1413 iter_count = clist->iter_count;
1414 iter_cycles = clist->iter_cycles;
1416 return callchain_counts_printf(fp, bf, bfsize, branch_count,
1417 predicted_count, abort_count,
1418 cycles_count, iter_count, iter_cycles,
1419 &clist->brtype_stat);
1422 static void free_callchain_node(struct callchain_node *node)
1424 struct callchain_list *list, *tmp;
1425 struct callchain_node *child;
1428 list_for_each_entry_safe(list, tmp, &node->parent_val, list) {
1429 list_del(&list->list);
1430 map__zput(list->ms.map);
1434 list_for_each_entry_safe(list, tmp, &node->val, list) {
1435 list_del(&list->list);
1436 map__zput(list->ms.map);
1440 n = rb_first(&node->rb_root_in);
1442 child = container_of(n, struct callchain_node, rb_node_in);
1444 rb_erase(&child->rb_node_in, &node->rb_root_in);
1446 free_callchain_node(child);
1451 void free_callchain(struct callchain_root *root)
1453 if (!symbol_conf.use_callchain)
1456 free_callchain_node(&root->node);
1459 static u64 decay_callchain_node(struct callchain_node *node)
1461 struct callchain_node *child;
1465 n = rb_first(&node->rb_root_in);
1467 child = container_of(n, struct callchain_node, rb_node_in);
1469 child_hits += decay_callchain_node(child);
1473 node->hit = (node->hit * 7) / 8;
1474 node->children_hit = child_hits;
1479 void decay_callchain(struct callchain_root *root)
1481 if (!symbol_conf.use_callchain)
1484 decay_callchain_node(&root->node);
1487 int callchain_node__make_parent_list(struct callchain_node *node)
1489 struct callchain_node *parent = node->parent;
1490 struct callchain_list *chain, *new;
1494 list_for_each_entry_reverse(chain, &parent->val, list) {
1495 new = malloc(sizeof(*new));
1499 new->has_children = false;
1500 map__get(new->ms.map);
1501 list_add_tail(&new->list, &head);
1503 parent = parent->parent;
1506 list_for_each_entry_safe_reverse(chain, new, &head, list)
1507 list_move_tail(&chain->list, &node->parent_val);
1509 if (!list_empty(&node->parent_val)) {
1510 chain = list_first_entry(&node->parent_val, struct callchain_list, list);
1511 chain->has_children = rb_prev(&node->rb_node) || rb_next(&node->rb_node);
1513 chain = list_first_entry(&node->val, struct callchain_list, list);
1514 chain->has_children = false;
1519 list_for_each_entry_safe(chain, new, &head, list) {
1520 list_del(&chain->list);
1521 map__zput(chain->ms.map);
1527 int callchain_cursor__copy(struct callchain_cursor *dst,
1528 struct callchain_cursor *src)
1532 callchain_cursor_reset(dst);
1533 callchain_cursor_commit(src);
1536 struct callchain_cursor_node *node;
1538 node = callchain_cursor_current(src);
1542 rc = callchain_cursor_append(dst, node->ip, node->map, node->sym,
1543 node->branch, &node->branch_flags,
1550 callchain_cursor_advance(src);