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