1
2
3
4
5
6
7
8
9
10
11
12
13#include <inttypes.h>
14#include <stdlib.h>
15#include <stdio.h>
16#include <stdbool.h>
17#include <errno.h>
18#include <math.h>
19
20#include "asm/bug.h"
21
22#include "hist.h"
23#include "util.h"
24#include "sort.h"
25#include "machine.h"
26#include "map.h"
27#include "callchain.h"
28#include "branch.h"
29#include "symbol.h"
30
31#define CALLCHAIN_PARAM_DEFAULT \
32 .mode = CHAIN_GRAPH_ABS, \
33 .min_percent = 0.5, \
34 .order = ORDER_CALLEE, \
35 .key = CCKEY_FUNCTION, \
36 .value = CCVAL_PERCENT, \
37
38struct callchain_param callchain_param = {
39 CALLCHAIN_PARAM_DEFAULT
40};
41
42
43
44
45
46
47
48
49bool dwarf_callchain_users;
50
51struct callchain_param callchain_param_default = {
52 CALLCHAIN_PARAM_DEFAULT
53};
54
55__thread struct callchain_cursor callchain_cursor;
56
57int parse_callchain_record_opt(const char *arg, struct callchain_param *param)
58{
59 return parse_callchain_record(arg, param);
60}
61
62static int parse_callchain_mode(const char *value)
63{
64 if (!strncmp(value, "graph", strlen(value))) {
65 callchain_param.mode = CHAIN_GRAPH_ABS;
66 return 0;
67 }
68 if (!strncmp(value, "flat", strlen(value))) {
69 callchain_param.mode = CHAIN_FLAT;
70 return 0;
71 }
72 if (!strncmp(value, "fractal", strlen(value))) {
73 callchain_param.mode = CHAIN_GRAPH_REL;
74 return 0;
75 }
76 if (!strncmp(value, "folded", strlen(value))) {
77 callchain_param.mode = CHAIN_FOLDED;
78 return 0;
79 }
80 return -1;
81}
82
83static int parse_callchain_order(const char *value)
84{
85 if (!strncmp(value, "caller", strlen(value))) {
86 callchain_param.order = ORDER_CALLER;
87 callchain_param.order_set = true;
88 return 0;
89 }
90 if (!strncmp(value, "callee", strlen(value))) {
91 callchain_param.order = ORDER_CALLEE;
92 callchain_param.order_set = true;
93 return 0;
94 }
95 return -1;
96}
97
98static int parse_callchain_sort_key(const char *value)
99{
100 if (!strncmp(value, "function", strlen(value))) {
101 callchain_param.key = CCKEY_FUNCTION;
102 return 0;
103 }
104 if (!strncmp(value, "address", strlen(value))) {
105 callchain_param.key = CCKEY_ADDRESS;
106 return 0;
107 }
108 if (!strncmp(value, "srcline", strlen(value))) {
109 callchain_param.key = CCKEY_SRCLINE;
110 return 0;
111 }
112 if (!strncmp(value, "branch", strlen(value))) {
113 callchain_param.branch_callstack = 1;
114 return 0;
115 }
116 return -1;
117}
118
119static int parse_callchain_value(const char *value)
120{
121 if (!strncmp(value, "percent", strlen(value))) {
122 callchain_param.value = CCVAL_PERCENT;
123 return 0;
124 }
125 if (!strncmp(value, "period", strlen(value))) {
126 callchain_param.value = CCVAL_PERIOD;
127 return 0;
128 }
129 if (!strncmp(value, "count", strlen(value))) {
130 callchain_param.value = CCVAL_COUNT;
131 return 0;
132 }
133 return -1;
134}
135
136static int get_stack_size(const char *str, unsigned long *_size)
137{
138 char *endptr;
139 unsigned long size;
140 unsigned long max_size = round_down(USHRT_MAX, sizeof(u64));
141
142 size = strtoul(str, &endptr, 0);
143
144 do {
145 if (*endptr)
146 break;
147
148 size = round_up(size, sizeof(u64));
149 if (!size || size > max_size)
150 break;
151
152 *_size = size;
153 return 0;
154
155 } while (0);
156
157 pr_err("callchain: Incorrect stack dump size (max %ld): %s\n",
158 max_size, str);
159 return -1;
160}
161
162static int
163__parse_callchain_report_opt(const char *arg, bool allow_record_opt)
164{
165 char *tok;
166 char *endptr, *saveptr = NULL;
167 bool minpcnt_set = false;
168 bool record_opt_set = false;
169 bool try_stack_size = false;
170
171 callchain_param.enabled = true;
172 symbol_conf.use_callchain = true;
173
174 if (!arg)
175 return 0;
176
177 while ((tok = strtok_r((char *)arg, ",", &saveptr)) != NULL) {
178 if (!strncmp(tok, "none", strlen(tok))) {
179 callchain_param.mode = CHAIN_NONE;
180 callchain_param.enabled = false;
181 symbol_conf.use_callchain = false;
182 return 0;
183 }
184
185 if (!parse_callchain_mode(tok) ||
186 !parse_callchain_order(tok) ||
187 !parse_callchain_sort_key(tok) ||
188 !parse_callchain_value(tok)) {
189
190 try_stack_size = false;
191 goto next;
192 } else if (allow_record_opt && !record_opt_set) {
193 if (parse_callchain_record(tok, &callchain_param))
194 goto try_numbers;
195
196
197 if (callchain_param.record_mode == CALLCHAIN_DWARF)
198 try_stack_size = true;
199
200 record_opt_set = true;
201 goto next;
202 }
203
204try_numbers:
205 if (try_stack_size) {
206 unsigned long size = 0;
207
208 if (get_stack_size(tok, &size) < 0)
209 return -1;
210 callchain_param.dump_size = size;
211 try_stack_size = false;
212 } else if (!minpcnt_set) {
213
214 callchain_param.min_percent = strtod(tok, &endptr);
215 if (tok == endptr)
216 return -1;
217 minpcnt_set = true;
218 } else {
219
220 callchain_param.print_limit = strtoul(tok, &endptr, 0);
221 if (tok == endptr)
222 return -1;
223 }
224next:
225 arg = NULL;
226 }
227
228 if (callchain_register_param(&callchain_param) < 0) {
229 pr_err("Can't register callchain params\n");
230 return -1;
231 }
232 return 0;
233}
234
235int parse_callchain_report_opt(const char *arg)
236{
237 return __parse_callchain_report_opt(arg, false);
238}
239
240int parse_callchain_top_opt(const char *arg)
241{
242 return __parse_callchain_report_opt(arg, true);
243}
244
245int parse_callchain_record(const char *arg, struct callchain_param *param)
246{
247 char *tok, *name, *saveptr = NULL;
248 char *buf;
249 int ret = -1;
250
251
252 buf = malloc(strlen(arg) + 1);
253 if (!buf)
254 return -ENOMEM;
255
256 strcpy(buf, arg);
257
258 tok = strtok_r((char *)buf, ",", &saveptr);
259 name = tok ? : (char *)buf;
260
261 do {
262
263 if (!strncmp(name, "fp", sizeof("fp"))) {
264 if (!strtok_r(NULL, ",", &saveptr)) {
265 param->record_mode = CALLCHAIN_FP;
266 ret = 0;
267 } else
268 pr_err("callchain: No more arguments "
269 "needed for --call-graph fp\n");
270 break;
271
272
273 } else if (!strncmp(name, "dwarf", sizeof("dwarf"))) {
274 const unsigned long default_stack_dump_size = 8192;
275
276 ret = 0;
277 param->record_mode = CALLCHAIN_DWARF;
278 param->dump_size = default_stack_dump_size;
279 dwarf_callchain_users = true;
280
281 tok = strtok_r(NULL, ",", &saveptr);
282 if (tok) {
283 unsigned long size = 0;
284
285 ret = get_stack_size(tok, &size);
286 param->dump_size = size;
287 }
288 } else if (!strncmp(name, "lbr", sizeof("lbr"))) {
289 if (!strtok_r(NULL, ",", &saveptr)) {
290 param->record_mode = CALLCHAIN_LBR;
291 ret = 0;
292 } else
293 pr_err("callchain: No more arguments "
294 "needed for --call-graph lbr\n");
295 break;
296 } else {
297 pr_err("callchain: Unknown --call-graph option "
298 "value: %s\n", arg);
299 break;
300 }
301
302 } while (0);
303
304 free(buf);
305 return ret;
306}
307
308int perf_callchain_config(const char *var, const char *value)
309{
310 char *endptr;
311
312 if (!strstarts(var, "call-graph."))
313 return 0;
314 var += sizeof("call-graph.") - 1;
315
316 if (!strcmp(var, "record-mode"))
317 return parse_callchain_record_opt(value, &callchain_param);
318 if (!strcmp(var, "dump-size")) {
319 unsigned long size = 0;
320 int ret;
321
322 ret = get_stack_size(value, &size);
323 callchain_param.dump_size = size;
324
325 return ret;
326 }
327 if (!strcmp(var, "print-type")){
328 int ret;
329 ret = parse_callchain_mode(value);
330 if (ret == -1)
331 pr_err("Invalid callchain mode: %s\n", value);
332 return ret;
333 }
334 if (!strcmp(var, "order")){
335 int ret;
336 ret = parse_callchain_order(value);
337 if (ret == -1)
338 pr_err("Invalid callchain order: %s\n", value);
339 return ret;
340 }
341 if (!strcmp(var, "sort-key")){
342 int ret;
343 ret = parse_callchain_sort_key(value);
344 if (ret == -1)
345 pr_err("Invalid callchain sort key: %s\n", value);
346 return ret;
347 }
348 if (!strcmp(var, "threshold")) {
349 callchain_param.min_percent = strtod(value, &endptr);
350 if (value == endptr) {
351 pr_err("Invalid callchain threshold: %s\n", value);
352 return -1;
353 }
354 }
355 if (!strcmp(var, "print-limit")) {
356 callchain_param.print_limit = strtod(value, &endptr);
357 if (value == endptr) {
358 pr_err("Invalid callchain print limit: %s\n", value);
359 return -1;
360 }
361 }
362
363 return 0;
364}
365
366static void
367rb_insert_callchain(struct rb_root *root, struct callchain_node *chain,
368 enum chain_mode mode)
369{
370 struct rb_node **p = &root->rb_node;
371 struct rb_node *parent = NULL;
372 struct callchain_node *rnode;
373 u64 chain_cumul = callchain_cumul_hits(chain);
374
375 while (*p) {
376 u64 rnode_cumul;
377
378 parent = *p;
379 rnode = rb_entry(parent, struct callchain_node, rb_node);
380 rnode_cumul = callchain_cumul_hits(rnode);
381
382 switch (mode) {
383 case CHAIN_FLAT:
384 case CHAIN_FOLDED:
385 if (rnode->hit < chain->hit)
386 p = &(*p)->rb_left;
387 else
388 p = &(*p)->rb_right;
389 break;
390 case CHAIN_GRAPH_ABS:
391 case CHAIN_GRAPH_REL:
392 if (rnode_cumul < chain_cumul)
393 p = &(*p)->rb_left;
394 else
395 p = &(*p)->rb_right;
396 break;
397 case CHAIN_NONE:
398 default:
399 break;
400 }
401 }
402
403 rb_link_node(&chain->rb_node, parent, p);
404 rb_insert_color(&chain->rb_node, root);
405}
406
407static void
408__sort_chain_flat(struct rb_root *rb_root, struct callchain_node *node,
409 u64 min_hit)
410{
411 struct rb_node *n;
412 struct callchain_node *child;
413
414 n = rb_first(&node->rb_root_in);
415 while (n) {
416 child = rb_entry(n, struct callchain_node, rb_node_in);
417 n = rb_next(n);
418
419 __sort_chain_flat(rb_root, child, min_hit);
420 }
421
422 if (node->hit && node->hit >= min_hit)
423 rb_insert_callchain(rb_root, node, CHAIN_FLAT);
424}
425
426
427
428
429
430static void
431sort_chain_flat(struct rb_root *rb_root, struct callchain_root *root,
432 u64 min_hit, struct callchain_param *param __maybe_unused)
433{
434 *rb_root = RB_ROOT;
435 __sort_chain_flat(rb_root, &root->node, min_hit);
436}
437
438static void __sort_chain_graph_abs(struct callchain_node *node,
439 u64 min_hit)
440{
441 struct rb_node *n;
442 struct callchain_node *child;
443
444 node->rb_root = RB_ROOT;
445 n = rb_first(&node->rb_root_in);
446
447 while (n) {
448 child = rb_entry(n, struct callchain_node, rb_node_in);
449 n = rb_next(n);
450
451 __sort_chain_graph_abs(child, min_hit);
452 if (callchain_cumul_hits(child) >= min_hit)
453 rb_insert_callchain(&node->rb_root, child,
454 CHAIN_GRAPH_ABS);
455 }
456}
457
458static void
459sort_chain_graph_abs(struct rb_root *rb_root, struct callchain_root *chain_root,
460 u64 min_hit, struct callchain_param *param __maybe_unused)
461{
462 __sort_chain_graph_abs(&chain_root->node, min_hit);
463 rb_root->rb_node = chain_root->node.rb_root.rb_node;
464}
465
466static void __sort_chain_graph_rel(struct callchain_node *node,
467 double min_percent)
468{
469 struct rb_node *n;
470 struct callchain_node *child;
471 u64 min_hit;
472
473 node->rb_root = RB_ROOT;
474 min_hit = ceil(node->children_hit * min_percent);
475
476 n = rb_first(&node->rb_root_in);
477 while (n) {
478 child = rb_entry(n, struct callchain_node, rb_node_in);
479 n = rb_next(n);
480
481 __sort_chain_graph_rel(child, min_percent);
482 if (callchain_cumul_hits(child) >= min_hit)
483 rb_insert_callchain(&node->rb_root, child,
484 CHAIN_GRAPH_REL);
485 }
486}
487
488static void
489sort_chain_graph_rel(struct rb_root *rb_root, struct callchain_root *chain_root,
490 u64 min_hit __maybe_unused, struct callchain_param *param)
491{
492 __sort_chain_graph_rel(&chain_root->node, param->min_percent / 100.0);
493 rb_root->rb_node = chain_root->node.rb_root.rb_node;
494}
495
496int callchain_register_param(struct callchain_param *param)
497{
498 switch (param->mode) {
499 case CHAIN_GRAPH_ABS:
500 param->sort = sort_chain_graph_abs;
501 break;
502 case CHAIN_GRAPH_REL:
503 param->sort = sort_chain_graph_rel;
504 break;
505 case CHAIN_FLAT:
506 case CHAIN_FOLDED:
507 param->sort = sort_chain_flat;
508 break;
509 case CHAIN_NONE:
510 default:
511 return -1;
512 }
513 return 0;
514}
515
516
517
518
519
520static struct callchain_node *
521create_child(struct callchain_node *parent, bool inherit_children)
522{
523 struct callchain_node *new;
524
525 new = zalloc(sizeof(*new));
526 if (!new) {
527 perror("not enough memory to create child for code path tree");
528 return NULL;
529 }
530 new->parent = parent;
531 INIT_LIST_HEAD(&new->val);
532 INIT_LIST_HEAD(&new->parent_val);
533
534 if (inherit_children) {
535 struct rb_node *n;
536 struct callchain_node *child;
537
538 new->rb_root_in = parent->rb_root_in;
539 parent->rb_root_in = RB_ROOT;
540
541 n = rb_first(&new->rb_root_in);
542 while (n) {
543 child = rb_entry(n, struct callchain_node, rb_node_in);
544 child->parent = new;
545 n = rb_next(n);
546 }
547
548
549 rb_link_node(&new->rb_node_in, NULL, &parent->rb_root_in.rb_node);
550 rb_insert_color(&new->rb_node_in, &parent->rb_root_in);
551 }
552
553 return new;
554}
555
556
557
558
559
560static int
561fill_node(struct callchain_node *node, struct callchain_cursor *cursor)
562{
563 struct callchain_cursor_node *cursor_node;
564
565 node->val_nr = cursor->nr - cursor->pos;
566 if (!node->val_nr)
567 pr_warning("Warning: empty node in callchain tree\n");
568
569 cursor_node = callchain_cursor_current(cursor);
570
571 while (cursor_node) {
572 struct callchain_list *call;
573
574 call = zalloc(sizeof(*call));
575 if (!call) {
576 perror("not enough memory for the code path tree");
577 return -1;
578 }
579 call->ip = cursor_node->ip;
580 call->ms.sym = cursor_node->sym;
581 call->ms.map = map__get(cursor_node->map);
582 call->srcline = cursor_node->srcline;
583
584 if (cursor_node->branch) {
585 call->branch_count = 1;
586
587 if (cursor_node->branch_from) {
588
589
590
591
592 call->brtype_stat.branch_to = true;
593
594 if (cursor_node->branch_flags.predicted)
595 call->predicted_count = 1;
596
597 if (cursor_node->branch_flags.abort)
598 call->abort_count = 1;
599
600 branch_type_count(&call->brtype_stat,
601 &cursor_node->branch_flags,
602 cursor_node->branch_from,
603 cursor_node->ip);
604 } else {
605
606
607
608 call->brtype_stat.branch_to = false;
609 call->cycles_count =
610 cursor_node->branch_flags.cycles;
611 call->iter_count = cursor_node->nr_loop_iter;
612 call->iter_cycles = cursor_node->iter_cycles;
613 }
614 }
615
616 list_add_tail(&call->list, &node->val);
617
618 callchain_cursor_advance(cursor);
619 cursor_node = callchain_cursor_current(cursor);
620 }
621 return 0;
622}
623
624static struct callchain_node *
625add_child(struct callchain_node *parent,
626 struct callchain_cursor *cursor,
627 u64 period)
628{
629 struct callchain_node *new;
630
631 new = create_child(parent, false);
632 if (new == NULL)
633 return NULL;
634
635 if (fill_node(new, cursor) < 0) {
636 struct callchain_list *call, *tmp;
637
638 list_for_each_entry_safe(call, tmp, &new->val, list) {
639 list_del(&call->list);
640 map__zput(call->ms.map);
641 free(call);
642 }
643 free(new);
644 return NULL;
645 }
646
647 new->children_hit = 0;
648 new->hit = period;
649 new->children_count = 0;
650 new->count = 1;
651 return new;
652}
653
654enum match_result {
655 MATCH_ERROR = -1,
656 MATCH_EQ,
657 MATCH_LT,
658 MATCH_GT,
659};
660
661static enum match_result match_chain_strings(const char *left,
662 const char *right)
663{
664 enum match_result ret = MATCH_EQ;
665 int cmp;
666
667 if (left && right)
668 cmp = strcmp(left, right);
669 else if (!left && right)
670 cmp = 1;
671 else if (left && !right)
672 cmp = -1;
673 else
674 return MATCH_ERROR;
675
676 if (cmp != 0)
677 ret = cmp < 0 ? MATCH_LT : MATCH_GT;
678
679 return ret;
680}
681
682
683
684
685
686
687
688
689
690static enum match_result match_chain_dso_addresses(struct map *left_map, u64 left_ip,
691 struct map *right_map, u64 right_ip)
692{
693 struct dso *left_dso = left_map ? left_map->dso : NULL;
694 struct dso *right_dso = right_map ? right_map->dso : NULL;
695
696 if (left_dso != right_dso)
697 return left_dso < right_dso ? MATCH_LT : MATCH_GT;
698
699 if (left_ip != right_ip)
700 return left_ip < right_ip ? MATCH_LT : MATCH_GT;
701
702 return MATCH_EQ;
703}
704
705static enum match_result match_chain(struct callchain_cursor_node *node,
706 struct callchain_list *cnode)
707{
708 enum match_result match = MATCH_ERROR;
709
710 switch (callchain_param.key) {
711 case CCKEY_SRCLINE:
712 match = match_chain_strings(cnode->srcline, node->srcline);
713 if (match != MATCH_ERROR)
714 break;
715
716 __fallthrough;
717 case CCKEY_FUNCTION:
718 if (node->sym && cnode->ms.sym) {
719
720
721
722
723
724
725 if (cnode->ms.sym->inlined || node->sym->inlined) {
726 match = match_chain_strings(cnode->ms.sym->name,
727 node->sym->name);
728 if (match != MATCH_ERROR)
729 break;
730 } else {
731 match = match_chain_dso_addresses(cnode->ms.map, cnode->ms.sym->start,
732 node->map, node->sym->start);
733 break;
734 }
735 }
736
737 __fallthrough;
738 case CCKEY_ADDRESS:
739 default:
740 match = match_chain_dso_addresses(cnode->ms.map, cnode->ip, node->map, node->ip);
741 break;
742 }
743
744 if (match == MATCH_EQ && node->branch) {
745 cnode->branch_count++;
746
747 if (node->branch_from) {
748
749
750
751 cnode->brtype_stat.branch_to = true;
752
753 if (node->branch_flags.predicted)
754 cnode->predicted_count++;
755
756 if (node->branch_flags.abort)
757 cnode->abort_count++;
758
759 branch_type_count(&cnode->brtype_stat,
760 &node->branch_flags,
761 node->branch_from,
762 node->ip);
763 } else {
764
765
766
767 cnode->brtype_stat.branch_to = false;
768 cnode->cycles_count += node->branch_flags.cycles;
769 cnode->iter_count += node->nr_loop_iter;
770 cnode->iter_cycles += node->iter_cycles;
771 cnode->from_count++;
772 }
773 }
774
775 return match;
776}
777
778
779
780
781
782
783static int
784split_add_child(struct callchain_node *parent,
785 struct callchain_cursor *cursor,
786 struct callchain_list *to_split,
787 u64 idx_parents, u64 idx_local, u64 period)
788{
789 struct callchain_node *new;
790 struct list_head *old_tail;
791 unsigned int idx_total = idx_parents + idx_local;
792
793
794 new = create_child(parent, true);
795 if (new == NULL)
796 return -1;
797
798
799 old_tail = parent->val.prev;
800 list_del_range(&to_split->list, old_tail);
801 new->val.next = &to_split->list;
802 new->val.prev = old_tail;
803 to_split->list.prev = &new->val;
804 old_tail->next = &new->val;
805
806
807 new->hit = parent->hit;
808 new->children_hit = parent->children_hit;
809 parent->children_hit = callchain_cumul_hits(new);
810 new->val_nr = parent->val_nr - idx_local;
811 parent->val_nr = idx_local;
812 new->count = parent->count;
813 new->children_count = parent->children_count;
814 parent->children_count = callchain_cumul_counts(new);
815
816
817 if (idx_total < cursor->nr) {
818 struct callchain_node *first;
819 struct callchain_list *cnode;
820 struct callchain_cursor_node *node;
821 struct rb_node *p, **pp;
822
823 parent->hit = 0;
824 parent->children_hit += period;
825 parent->count = 0;
826 parent->children_count += 1;
827
828 node = callchain_cursor_current(cursor);
829 new = add_child(parent, cursor, period);
830 if (new == NULL)
831 return -1;
832
833
834
835
836
837 p = parent->rb_root_in.rb_node;
838 first = rb_entry(p, struct callchain_node, rb_node_in);
839 cnode = list_first_entry(&first->val, struct callchain_list,
840 list);
841
842 if (match_chain(node, cnode) == MATCH_LT)
843 pp = &p->rb_left;
844 else
845 pp = &p->rb_right;
846
847 rb_link_node(&new->rb_node_in, p, pp);
848 rb_insert_color(&new->rb_node_in, &parent->rb_root_in);
849 } else {
850 parent->hit = period;
851 parent->count = 1;
852 }
853 return 0;
854}
855
856static enum match_result
857append_chain(struct callchain_node *root,
858 struct callchain_cursor *cursor,
859 u64 period);
860
861static int
862append_chain_children(struct callchain_node *root,
863 struct callchain_cursor *cursor,
864 u64 period)
865{
866 struct callchain_node *rnode;
867 struct callchain_cursor_node *node;
868 struct rb_node **p = &root->rb_root_in.rb_node;
869 struct rb_node *parent = NULL;
870
871 node = callchain_cursor_current(cursor);
872 if (!node)
873 return -1;
874
875
876 while (*p) {
877 enum match_result ret;
878
879 parent = *p;
880 rnode = rb_entry(parent, struct callchain_node, rb_node_in);
881
882
883 ret = append_chain(rnode, cursor, period);
884 if (ret == MATCH_EQ)
885 goto inc_children_hit;
886 if (ret == MATCH_ERROR)
887 return -1;
888
889 if (ret == MATCH_LT)
890 p = &parent->rb_left;
891 else
892 p = &parent->rb_right;
893 }
894
895 rnode = add_child(root, cursor, period);
896 if (rnode == NULL)
897 return -1;
898
899 rb_link_node(&rnode->rb_node_in, parent, p);
900 rb_insert_color(&rnode->rb_node_in, &root->rb_root_in);
901
902inc_children_hit:
903 root->children_hit += period;
904 root->children_count++;
905 return 0;
906}
907
908static enum match_result
909append_chain(struct callchain_node *root,
910 struct callchain_cursor *cursor,
911 u64 period)
912{
913 struct callchain_list *cnode;
914 u64 start = cursor->pos;
915 bool found = false;
916 u64 matches;
917 enum match_result cmp = MATCH_ERROR;
918
919
920
921
922
923
924
925 list_for_each_entry(cnode, &root->val, list) {
926 struct callchain_cursor_node *node;
927
928 node = callchain_cursor_current(cursor);
929 if (!node)
930 break;
931
932 cmp = match_chain(node, cnode);
933 if (cmp != MATCH_EQ)
934 break;
935
936 found = true;
937
938 callchain_cursor_advance(cursor);
939 }
940
941
942 if (!found) {
943 WARN_ONCE(cmp == MATCH_ERROR, "Chain comparison error\n");
944 return cmp;
945 }
946
947 matches = cursor->pos - start;
948
949
950 if (matches < root->val_nr) {
951 if (split_add_child(root, cursor, cnode, start, matches,
952 period) < 0)
953 return MATCH_ERROR;
954
955 return MATCH_EQ;
956 }
957
958
959 if (matches == root->val_nr && cursor->pos == cursor->nr) {
960 root->hit += period;
961 root->count++;
962 return MATCH_EQ;
963 }
964
965
966 if (append_chain_children(root, cursor, period) < 0)
967 return MATCH_ERROR;
968
969 return MATCH_EQ;
970}
971
972int callchain_append(struct callchain_root *root,
973 struct callchain_cursor *cursor,
974 u64 period)
975{
976 if (!cursor->nr)
977 return 0;
978
979 callchain_cursor_commit(cursor);
980
981 if (append_chain_children(&root->node, cursor, period) < 0)
982 return -1;
983
984 if (cursor->nr > root->max_depth)
985 root->max_depth = cursor->nr;
986
987 return 0;
988}
989
990static int
991merge_chain_branch(struct callchain_cursor *cursor,
992 struct callchain_node *dst, struct callchain_node *src)
993{
994 struct callchain_cursor_node **old_last = cursor->last;
995 struct callchain_node *child;
996 struct callchain_list *list, *next_list;
997 struct rb_node *n;
998 int old_pos = cursor->nr;
999 int err = 0;
1000
1001 list_for_each_entry_safe(list, next_list, &src->val, list) {
1002 callchain_cursor_append(cursor, list->ip,
1003 list->ms.map, list->ms.sym,
1004 false, NULL, 0, 0, 0, list->srcline);
1005 list_del(&list->list);
1006 map__zput(list->ms.map);
1007 free(list);
1008 }
1009
1010 if (src->hit) {
1011 callchain_cursor_commit(cursor);
1012 if (append_chain_children(dst, cursor, src->hit) < 0)
1013 return -1;
1014 }
1015
1016 n = rb_first(&src->rb_root_in);
1017 while (n) {
1018 child = container_of(n, struct callchain_node, rb_node_in);
1019 n = rb_next(n);
1020 rb_erase(&child->rb_node_in, &src->rb_root_in);
1021
1022 err = merge_chain_branch(cursor, dst, child);
1023 if (err)
1024 break;
1025
1026 free(child);
1027 }
1028
1029 cursor->nr = old_pos;
1030 cursor->last = old_last;
1031
1032 return err;
1033}
1034
1035int callchain_merge(struct callchain_cursor *cursor,
1036 struct callchain_root *dst, struct callchain_root *src)
1037{
1038 return merge_chain_branch(cursor, &dst->node, &src->node);
1039}
1040
1041int callchain_cursor_append(struct callchain_cursor *cursor,
1042 u64 ip, struct map *map, struct symbol *sym,
1043 bool branch, struct branch_flags *flags,
1044 int nr_loop_iter, u64 iter_cycles, u64 branch_from,
1045 const char *srcline)
1046{
1047 struct callchain_cursor_node *node = *cursor->last;
1048
1049 if (!node) {
1050 node = calloc(1, sizeof(*node));
1051 if (!node)
1052 return -ENOMEM;
1053
1054 *cursor->last = node;
1055 }
1056
1057 node->ip = ip;
1058 map__zput(node->map);
1059 node->map = map__get(map);
1060 node->sym = sym;
1061 node->branch = branch;
1062 node->nr_loop_iter = nr_loop_iter;
1063 node->iter_cycles = iter_cycles;
1064 node->srcline = srcline;
1065
1066 if (flags)
1067 memcpy(&node->branch_flags, flags,
1068 sizeof(struct branch_flags));
1069
1070 node->branch_from = branch_from;
1071 cursor->nr++;
1072
1073 cursor->last = &node->next;
1074
1075 return 0;
1076}
1077
1078int sample__resolve_callchain(struct perf_sample *sample,
1079 struct callchain_cursor *cursor, struct symbol **parent,
1080 struct perf_evsel *evsel, struct addr_location *al,
1081 int max_stack)
1082{
1083 if (sample->callchain == NULL && !symbol_conf.show_branchflag_count)
1084 return 0;
1085
1086 if (symbol_conf.use_callchain || symbol_conf.cumulate_callchain ||
1087 perf_hpp_list.parent || symbol_conf.show_branchflag_count) {
1088 return thread__resolve_callchain(al->thread, cursor, evsel, sample,
1089 parent, al, max_stack);
1090 }
1091 return 0;
1092}
1093
1094int hist_entry__append_callchain(struct hist_entry *he, struct perf_sample *sample)
1095{
1096 if ((!symbol_conf.use_callchain || sample->callchain == NULL) &&
1097 !symbol_conf.show_branchflag_count)
1098 return 0;
1099 return callchain_append(he->callchain, &callchain_cursor, sample->period);
1100}
1101
1102int fill_callchain_info(struct addr_location *al, struct callchain_cursor_node *node,
1103 bool hide_unresolved)
1104{
1105 al->map = node->map;
1106 al->sym = node->sym;
1107 al->srcline = node->srcline;
1108 al->addr = node->ip;
1109
1110 if (al->sym == NULL) {
1111 if (hide_unresolved)
1112 return 0;
1113 if (al->map == NULL)
1114 goto out;
1115 }
1116
1117 if (al->map->groups == &al->machine->kmaps) {
1118 if (machine__is_host(al->machine)) {
1119 al->cpumode = PERF_RECORD_MISC_KERNEL;
1120 al->level = 'k';
1121 } else {
1122 al->cpumode = PERF_RECORD_MISC_GUEST_KERNEL;
1123 al->level = 'g';
1124 }
1125 } else {
1126 if (machine__is_host(al->machine)) {
1127 al->cpumode = PERF_RECORD_MISC_USER;
1128 al->level = '.';
1129 } else if (perf_guest) {
1130 al->cpumode = PERF_RECORD_MISC_GUEST_USER;
1131 al->level = 'u';
1132 } else {
1133 al->cpumode = PERF_RECORD_MISC_HYPERVISOR;
1134 al->level = 'H';
1135 }
1136 }
1137
1138out:
1139 return 1;
1140}
1141
1142char *callchain_list__sym_name(struct callchain_list *cl,
1143 char *bf, size_t bfsize, bool show_dso)
1144{
1145 bool show_addr = callchain_param.key == CCKEY_ADDRESS;
1146 bool show_srcline = show_addr || callchain_param.key == CCKEY_SRCLINE;
1147 int printed;
1148
1149 if (cl->ms.sym) {
1150 const char *inlined = cl->ms.sym->inlined ? " (inlined)" : "";
1151
1152 if (show_srcline && cl->srcline)
1153 printed = scnprintf(bf, bfsize, "%s %s%s",
1154 cl->ms.sym->name, cl->srcline,
1155 inlined);
1156 else
1157 printed = scnprintf(bf, bfsize, "%s%s",
1158 cl->ms.sym->name, inlined);
1159 } else
1160 printed = scnprintf(bf, bfsize, "%#" PRIx64, cl->ip);
1161
1162 if (show_dso)
1163 scnprintf(bf + printed, bfsize - printed, " %s",
1164 cl->ms.map ?
1165 cl->ms.map->dso->short_name :
1166 "unknown");
1167
1168 return bf;
1169}
1170
1171char *callchain_node__scnprintf_value(struct callchain_node *node,
1172 char *bf, size_t bfsize, u64 total)
1173{
1174 double percent = 0.0;
1175 u64 period = callchain_cumul_hits(node);
1176 unsigned count = callchain_cumul_counts(node);
1177
1178 if (callchain_param.mode == CHAIN_FOLDED) {
1179 period = node->hit;
1180 count = node->count;
1181 }
1182
1183 switch (callchain_param.value) {
1184 case CCVAL_PERIOD:
1185 scnprintf(bf, bfsize, "%"PRIu64, period);
1186 break;
1187 case CCVAL_COUNT:
1188 scnprintf(bf, bfsize, "%u", count);
1189 break;
1190 case CCVAL_PERCENT:
1191 default:
1192 if (total)
1193 percent = period * 100.0 / total;
1194 scnprintf(bf, bfsize, "%.2f%%", percent);
1195 break;
1196 }
1197 return bf;
1198}
1199
1200int callchain_node__fprintf_value(struct callchain_node *node,
1201 FILE *fp, u64 total)
1202{
1203 double percent = 0.0;
1204 u64 period = callchain_cumul_hits(node);
1205 unsigned count = callchain_cumul_counts(node);
1206
1207 if (callchain_param.mode == CHAIN_FOLDED) {
1208 period = node->hit;
1209 count = node->count;
1210 }
1211
1212 switch (callchain_param.value) {
1213 case CCVAL_PERIOD:
1214 return fprintf(fp, "%"PRIu64, period);
1215 case CCVAL_COUNT:
1216 return fprintf(fp, "%u", count);
1217 case CCVAL_PERCENT:
1218 default:
1219 if (total)
1220 percent = period * 100.0 / total;
1221 return percent_color_fprintf(fp, "%.2f%%", percent);
1222 }
1223 return 0;
1224}
1225
1226static void callchain_counts_value(struct callchain_node *node,
1227 u64 *branch_count, u64 *predicted_count,
1228 u64 *abort_count, u64 *cycles_count)
1229{
1230 struct callchain_list *clist;
1231
1232 list_for_each_entry(clist, &node->val, list) {
1233 if (branch_count)
1234 *branch_count += clist->branch_count;
1235
1236 if (predicted_count)
1237 *predicted_count += clist->predicted_count;
1238
1239 if (abort_count)
1240 *abort_count += clist->abort_count;
1241
1242 if (cycles_count)
1243 *cycles_count += clist->cycles_count;
1244 }
1245}
1246
1247static int callchain_node_branch_counts_cumul(struct callchain_node *node,
1248 u64 *branch_count,
1249 u64 *predicted_count,
1250 u64 *abort_count,
1251 u64 *cycles_count)
1252{
1253 struct callchain_node *child;
1254 struct rb_node *n;
1255
1256 n = rb_first(&node->rb_root_in);
1257 while (n) {
1258 child = rb_entry(n, struct callchain_node, rb_node_in);
1259 n = rb_next(n);
1260
1261 callchain_node_branch_counts_cumul(child, branch_count,
1262 predicted_count,
1263 abort_count,
1264 cycles_count);
1265
1266 callchain_counts_value(child, branch_count,
1267 predicted_count, abort_count,
1268 cycles_count);
1269 }
1270
1271 return 0;
1272}
1273
1274int callchain_branch_counts(struct callchain_root *root,
1275 u64 *branch_count, u64 *predicted_count,
1276 u64 *abort_count, u64 *cycles_count)
1277{
1278 if (branch_count)
1279 *branch_count = 0;
1280
1281 if (predicted_count)
1282 *predicted_count = 0;
1283
1284 if (abort_count)
1285 *abort_count = 0;
1286
1287 if (cycles_count)
1288 *cycles_count = 0;
1289
1290 return callchain_node_branch_counts_cumul(&root->node,
1291 branch_count,
1292 predicted_count,
1293 abort_count,
1294 cycles_count);
1295}
1296
1297static int count_pri64_printf(int idx, const char *str, u64 value, char *bf, int bfsize)
1298{
1299 int printed;
1300
1301 printed = scnprintf(bf, bfsize, "%s%s:%" PRId64 "", (idx) ? " " : " (", str, value);
1302
1303 return printed;
1304}
1305
1306static int count_float_printf(int idx, const char *str, float value,
1307 char *bf, int bfsize, float threshold)
1308{
1309 int printed;
1310
1311 if (threshold != 0.0 && value < threshold)
1312 return 0;
1313
1314 printed = scnprintf(bf, bfsize, "%s%s:%.1f%%", (idx) ? " " : " (", str, value);
1315
1316 return printed;
1317}
1318
1319static int branch_to_str(char *bf, int bfsize,
1320 u64 branch_count, u64 predicted_count,
1321 u64 abort_count,
1322 struct branch_type_stat *brtype_stat)
1323{
1324 int printed, i = 0;
1325
1326 printed = branch_type_str(brtype_stat, bf, bfsize);
1327 if (printed)
1328 i++;
1329
1330 if (predicted_count < branch_count) {
1331 printed += count_float_printf(i++, "predicted",
1332 predicted_count * 100.0 / branch_count,
1333 bf + printed, bfsize - printed, 0.0);
1334 }
1335
1336 if (abort_count) {
1337 printed += count_float_printf(i++, "abort",
1338 abort_count * 100.0 / branch_count,
1339 bf + printed, bfsize - printed, 0.1);
1340 }
1341
1342 if (i)
1343 printed += scnprintf(bf + printed, bfsize - printed, ")");
1344
1345 return printed;
1346}
1347
1348static int branch_from_str(char *bf, int bfsize,
1349 u64 branch_count,
1350 u64 cycles_count, u64 iter_count,
1351 u64 iter_cycles, u64 from_count)
1352{
1353 int printed = 0, i = 0;
1354 u64 cycles, v = 0;
1355
1356 cycles = cycles_count / branch_count;
1357 if (cycles) {
1358 printed += count_pri64_printf(i++, "cycles",
1359 cycles,
1360 bf + printed, bfsize - printed);
1361 }
1362
1363 if (iter_count && from_count) {
1364 v = iter_count / from_count;
1365 if (v) {
1366 printed += count_pri64_printf(i++, "iter",
1367 v, bf + printed, bfsize - printed);
1368
1369 printed += count_pri64_printf(i++, "avg_cycles",
1370 iter_cycles / iter_count,
1371 bf + printed, bfsize - printed);
1372 }
1373 }
1374
1375 if (i)
1376 printed += scnprintf(bf + printed, bfsize - printed, ")");
1377
1378 return printed;
1379}
1380
1381static int counts_str_build(char *bf, int bfsize,
1382 u64 branch_count, u64 predicted_count,
1383 u64 abort_count, u64 cycles_count,
1384 u64 iter_count, u64 iter_cycles,
1385 u64 from_count,
1386 struct branch_type_stat *brtype_stat)
1387{
1388 int printed;
1389
1390 if (branch_count == 0)
1391 return scnprintf(bf, bfsize, " (calltrace)");
1392
1393 if (brtype_stat->branch_to) {
1394 printed = branch_to_str(bf, bfsize, branch_count,
1395 predicted_count, abort_count, brtype_stat);
1396 } else {
1397 printed = branch_from_str(bf, bfsize, branch_count,
1398 cycles_count, iter_count, iter_cycles,
1399 from_count);
1400 }
1401
1402 if (!printed)
1403 bf[0] = 0;
1404
1405 return printed;
1406}
1407
1408static int callchain_counts_printf(FILE *fp, char *bf, int bfsize,
1409 u64 branch_count, u64 predicted_count,
1410 u64 abort_count, u64 cycles_count,
1411 u64 iter_count, u64 iter_cycles,
1412 u64 from_count,
1413 struct branch_type_stat *brtype_stat)
1414{
1415 char str[256];
1416
1417 counts_str_build(str, sizeof(str), branch_count,
1418 predicted_count, abort_count, cycles_count,
1419 iter_count, iter_cycles, from_count, brtype_stat);
1420
1421 if (fp)
1422 return fprintf(fp, "%s", str);
1423
1424 return scnprintf(bf, bfsize, "%s", str);
1425}
1426
1427int callchain_list_counts__printf_value(struct callchain_list *clist,
1428 FILE *fp, char *bf, int bfsize)
1429{
1430 u64 branch_count, predicted_count;
1431 u64 abort_count, cycles_count;
1432 u64 iter_count, iter_cycles;
1433 u64 from_count;
1434
1435 branch_count = clist->branch_count;
1436 predicted_count = clist->predicted_count;
1437 abort_count = clist->abort_count;
1438 cycles_count = clist->cycles_count;
1439 iter_count = clist->iter_count;
1440 iter_cycles = clist->iter_cycles;
1441 from_count = clist->from_count;
1442
1443 return callchain_counts_printf(fp, bf, bfsize, branch_count,
1444 predicted_count, abort_count,
1445 cycles_count, iter_count, iter_cycles,
1446 from_count, &clist->brtype_stat);
1447}
1448
1449static void free_callchain_node(struct callchain_node *node)
1450{
1451 struct callchain_list *list, *tmp;
1452 struct callchain_node *child;
1453 struct rb_node *n;
1454
1455 list_for_each_entry_safe(list, tmp, &node->parent_val, list) {
1456 list_del(&list->list);
1457 map__zput(list->ms.map);
1458 free(list);
1459 }
1460
1461 list_for_each_entry_safe(list, tmp, &node->val, list) {
1462 list_del(&list->list);
1463 map__zput(list->ms.map);
1464 free(list);
1465 }
1466
1467 n = rb_first(&node->rb_root_in);
1468 while (n) {
1469 child = container_of(n, struct callchain_node, rb_node_in);
1470 n = rb_next(n);
1471 rb_erase(&child->rb_node_in, &node->rb_root_in);
1472
1473 free_callchain_node(child);
1474 free(child);
1475 }
1476}
1477
1478void free_callchain(struct callchain_root *root)
1479{
1480 if (!symbol_conf.use_callchain)
1481 return;
1482
1483 free_callchain_node(&root->node);
1484}
1485
1486static u64 decay_callchain_node(struct callchain_node *node)
1487{
1488 struct callchain_node *child;
1489 struct rb_node *n;
1490 u64 child_hits = 0;
1491
1492 n = rb_first(&node->rb_root_in);
1493 while (n) {
1494 child = container_of(n, struct callchain_node, rb_node_in);
1495
1496 child_hits += decay_callchain_node(child);
1497 n = rb_next(n);
1498 }
1499
1500 node->hit = (node->hit * 7) / 8;
1501 node->children_hit = child_hits;
1502
1503 return node->hit;
1504}
1505
1506void decay_callchain(struct callchain_root *root)
1507{
1508 if (!symbol_conf.use_callchain)
1509 return;
1510
1511 decay_callchain_node(&root->node);
1512}
1513
1514int callchain_node__make_parent_list(struct callchain_node *node)
1515{
1516 struct callchain_node *parent = node->parent;
1517 struct callchain_list *chain, *new;
1518 LIST_HEAD(head);
1519
1520 while (parent) {
1521 list_for_each_entry_reverse(chain, &parent->val, list) {
1522 new = malloc(sizeof(*new));
1523 if (new == NULL)
1524 goto out;
1525 *new = *chain;
1526 new->has_children = false;
1527 map__get(new->ms.map);
1528 list_add_tail(&new->list, &head);
1529 }
1530 parent = parent->parent;
1531 }
1532
1533 list_for_each_entry_safe_reverse(chain, new, &head, list)
1534 list_move_tail(&chain->list, &node->parent_val);
1535
1536 if (!list_empty(&node->parent_val)) {
1537 chain = list_first_entry(&node->parent_val, struct callchain_list, list);
1538 chain->has_children = rb_prev(&node->rb_node) || rb_next(&node->rb_node);
1539
1540 chain = list_first_entry(&node->val, struct callchain_list, list);
1541 chain->has_children = false;
1542 }
1543 return 0;
1544
1545out:
1546 list_for_each_entry_safe(chain, new, &head, list) {
1547 list_del(&chain->list);
1548 map__zput(chain->ms.map);
1549 free(chain);
1550 }
1551 return -ENOMEM;
1552}
1553
1554int callchain_cursor__copy(struct callchain_cursor *dst,
1555 struct callchain_cursor *src)
1556{
1557 int rc = 0;
1558
1559 callchain_cursor_reset(dst);
1560 callchain_cursor_commit(src);
1561
1562 while (true) {
1563 struct callchain_cursor_node *node;
1564
1565 node = callchain_cursor_current(src);
1566 if (node == NULL)
1567 break;
1568
1569 rc = callchain_cursor_append(dst, node->ip, node->map, node->sym,
1570 node->branch, &node->branch_flags,
1571 node->nr_loop_iter,
1572 node->iter_cycles,
1573 node->branch_from, node->srcline);
1574 if (rc)
1575 break;
1576
1577 callchain_cursor_advance(src);
1578 }
1579
1580 return rc;
1581}
1582
1583
1584
1585
1586
1587void callchain_cursor_reset(struct callchain_cursor *cursor)
1588{
1589 struct callchain_cursor_node *node;
1590
1591 cursor->nr = 0;
1592 cursor->last = &cursor->first;
1593
1594 for (node = cursor->first; node != NULL; node = node->next)
1595 map__zput(node->map);
1596}
1597
