projects/linux·blob master · refs

1943 lines · 45.6 KiB

1// SPDX-License-Identifier: GPL-2.0
2/*
3 * Copyright (C) 2009-2011, Frederic Weisbecker <[email protected]>
4 *
5 * Handle the callchains from the stream in an ad-hoc radix tree and then
6 * sort them in an rbtree.
7 *
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.
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#include <linux/string.h>
20#include <linux/zalloc.h>
21
22#include "asm/bug.h"
23
24#include "debug.h"
25#include "dso.h"
26#include "event.h"
27#include "hist.h"
28#include "sort.h"
29#include "machine.h"
30#include "map.h"
31#include "callchain.h"
32#include "branch.h"
33#include "record.h"
34#include "symbol.h"
35#include "thread.h"
36#include "util.h"
37#include "../perf.h"
38
39#define CALLCHAIN_PARAM_DEFAULT \
40 .mode = CHAIN_GRAPH_ABS, \
41 .min_percent = 0.5, \
42 .order = ORDER_CALLEE, \
43 .key = CCKEY_FUNCTION, \
44 .value = CCVAL_PERCENT, \
45
46struct callchain_param callchain_param = {
47 CALLCHAIN_PARAM_DEFAULT
48};
49
50/*
51 * Are there any events usind DWARF callchains?
52 *
53 * I.e.
54 *
55 * -e cycles/call-graph=dwarf/
56 */
57bool dwarf_callchain_users;
58
59struct callchain_param callchain_param_default = {
60 CALLCHAIN_PARAM_DEFAULT
61};
62
63/* Used for thread-local struct callchain_cursor. */
64static pthread_key_t callchain_cursor;
65
66int parse_callchain_record_opt(const char *arg, struct callchain_param *param)
67{
68 return parse_callchain_record(arg, param);
69}
70
71static int parse_callchain_mode(const char *value)
72{
73 if (!strncmp(value, "graph", strlen(value))) {
74 callchain_param.mode = CHAIN_GRAPH_ABS;
75 return 0;
76 }
77 if (!strncmp(value, "flat", strlen(value))) {
78 callchain_param.mode = CHAIN_FLAT;
79 return 0;
80 }
81 if (!strncmp(value, "fractal", strlen(value))) {
82 callchain_param.mode = CHAIN_GRAPH_REL;
83 return 0;
84 }
85 if (!strncmp(value, "folded", strlen(value))) {
86 callchain_param.mode = CHAIN_FOLDED;
87 return 0;
88 }
89 return -1;
90}
91
92static int parse_callchain_order(const char *value)
93{
94 if (!strncmp(value, "caller", strlen(value))) {
95 callchain_param.order = ORDER_CALLER;
96 callchain_param.order_set = true;
97 return 0;
98 }
99 if (!strncmp(value, "callee", strlen(value))) {
100 callchain_param.order = ORDER_CALLEE;
101 callchain_param.order_set = true;
102 return 0;
103 }
104 return -1;
105}
106
107static int parse_callchain_sort_key(const char *value)
108{
109 if (!strncmp(value, "function", strlen(value))) {
110 callchain_param.key = CCKEY_FUNCTION;
111 return 0;
112 }
113 if (!strncmp(value, "address", strlen(value))) {
114 callchain_param.key = CCKEY_ADDRESS;
115 return 0;
116 }
117 if (!strncmp(value, "srcline", strlen(value))) {
118 callchain_param.key = CCKEY_SRCLINE;
119 return 0;
120 }
121 if (!strncmp(value, "branch", strlen(value))) {
122 callchain_param.branch_callstack = 1;
123 return 0;
124 }
125 return -1;
126}
127
128static int parse_callchain_value(const char *value)
129{
130 if (!strncmp(value, "percent", strlen(value))) {
131 callchain_param.value = CCVAL_PERCENT;
132 return 0;
133 }
134 if (!strncmp(value, "period", strlen(value))) {
135 callchain_param.value = CCVAL_PERIOD;
136 return 0;
137 }
138 if (!strncmp(value, "count", strlen(value))) {
139 callchain_param.value = CCVAL_COUNT;
140 return 0;
141 }
142 return -1;
143}
144
145static int get_stack_size(const char *str, unsigned long *_size)
146{
147 char *endptr;
148 unsigned long size;
149 unsigned long max_size = round_down(USHRT_MAX, sizeof(u64));
150
151 size = strtoul(str, &endptr, 0);
152
153 do {
154 if (*endptr)
155 break;
156
157 size = round_up(size, sizeof(u64));
158 if (!size || size > max_size)
159 break;
160
161 *_size = size;
162 return 0;
163
164 } while (0);
165
166 pr_err("callchain: Incorrect stack dump size (max %ld): %s\n",
167 max_size, str);
168 return -1;
169}
170
171static int
172__parse_callchain_report_opt(const char *arg, bool allow_record_opt)
173{
174 char *tok, *arg_copy;
175 char *endptr, *saveptr = NULL;
176 bool minpcnt_set = false;
177 bool record_opt_set = false;
178 bool try_stack_size = false;
179
180 callchain_param.enabled = true;
181 symbol_conf.use_callchain = true;
182
183 if (!arg)
184 return 0;
185
186 arg_copy = strdup(arg);
187 if (!arg_copy)
188 return -ENOMEM;
189
190 tok = strtok_r(arg_copy, ",", &saveptr);
191 while (tok) {
192 if (!strncmp(tok, "none", strlen(tok))) {
193 callchain_param.mode = CHAIN_NONE;
194 callchain_param.enabled = false;
195 symbol_conf.use_callchain = false;
196 goto out;
197 }
198
199 if (!parse_callchain_mode(tok) ||
200 !parse_callchain_order(tok) ||
201 !parse_callchain_sort_key(tok) ||
202 !parse_callchain_value(tok)) {
203 /* parsing ok - move on to the next */
204 try_stack_size = false;
205 goto next;
206 } else if (allow_record_opt && !record_opt_set) {
207 if (parse_callchain_record(tok, &callchain_param))
208 goto try_numbers;
209
210 /* assume that number followed by 'dwarf' is stack size */
211 if (callchain_param.record_mode == CALLCHAIN_DWARF)
212 try_stack_size = true;
213
214 record_opt_set = true;
215 goto next;
216 }
217
218try_numbers:
219 if (try_stack_size) {
220 unsigned long size = 0;
221
222 if (get_stack_size(tok, &size) < 0)
223 goto err_out;
224 callchain_param.dump_size = size;
225 try_stack_size = false;
226 } else if (!minpcnt_set) {
227 /* try to get the min percent */
228 callchain_param.min_percent = strtod(tok, &endptr);
229 if (tok == endptr)
230 goto err_out;
231 minpcnt_set = true;
232 } else {
233 /* try print limit at last */
234 callchain_param.print_limit = strtoul(tok, &endptr, 0);
235 if (tok == endptr)
236 goto err_out;
237 }
238next:
239 tok = strtok_r(NULL, ",", &saveptr);
240 }
241
242 if (callchain_register_param(&callchain_param) < 0) {
243 pr_err("Can't register callchain params\n");
244 goto err_out;
245 }
246out:
247 free(arg_copy);
248 return 0;
249err_out:
250 free(arg_copy);
251 return -1;
252}
253
254int parse_callchain_report_opt(const char *arg)
255{
256 return __parse_callchain_report_opt(arg, false);
257}
258
259int parse_callchain_top_opt(const char *arg)
260{
261 return __parse_callchain_report_opt(arg, true);
262}
263
264int parse_callchain_record(const char *arg, struct callchain_param *param)
265{
266 char *tok, *name, *saveptr = NULL;
267 char *buf;
268 int ret = -1;
269
270 /* We need buffer that we know we can write to. */
271 buf = strdup(arg);
272 if (!buf)
273 return -ENOMEM;
274
275 tok = strtok_r(buf, ",", &saveptr);
276 name = tok ? : buf;
277
278 do {
279 /* Framepointer style */
280 if (!strncmp(name, "fp", sizeof("fp"))) {
281 ret = 0;
282 param->record_mode = CALLCHAIN_FP;
283
284 tok = strtok_r(NULL, ",", &saveptr);
285 if (tok) {
286 unsigned long size;
287
288 if (!strncmp(tok, "defer", sizeof("defer"))) {
289 param->defer = true;
290 } else {
291 size = strtoul(tok, &name, 0);
292 if (size < (unsigned) sysctl__max_stack())
293 param->max_stack = size;
294 }
295 }
296 break;
297
298 /* Dwarf style */
299 } else if (!strncmp(name, "dwarf", sizeof("dwarf"))) {
300 const unsigned long default_stack_dump_size = 8192;
301
302 ret = 0;
303 param->record_mode = CALLCHAIN_DWARF;
304 param->dump_size = default_stack_dump_size;
305 dwarf_callchain_users = true;
306
307 tok = strtok_r(NULL, ",", &saveptr);
308 if (tok) {
309 unsigned long size = 0;
310
311 ret = get_stack_size(tok, &size);
312 param->dump_size = size;
313 }
314 } else if (!strncmp(name, "lbr", sizeof("lbr"))) {
315 if (!strtok_r(NULL, ",", &saveptr)) {
316 param->record_mode = CALLCHAIN_LBR;
317 ret = 0;
318 } else
319 pr_err("callchain: No more arguments "
320 "needed for --call-graph lbr\n");
321 break;
322 } else {
323 pr_err("callchain: Unknown --call-graph option "
324 "value: %s\n", arg);
325 break;
326 }
327
328 } while (0);
329
330 free(buf);
331
332 if (param->defer && param->record_mode != CALLCHAIN_FP) {
333 pr_err("callchain: deferred callchain only works with FP\n");
334 return -EINVAL;
335 }
336
337 return ret;
338}
339
340static void callchain_debug(const struct callchain_param *callchain)
341{
342 static const char *str[CALLCHAIN_MAX] = { "NONE", "FP", "DWARF", "LBR" };
343
344 pr_debug("callchain: type %s\n", str[callchain->record_mode]);
345
346 if (callchain->record_mode == CALLCHAIN_DWARF)
347 pr_debug("callchain: stack dump size %d\n",
348 callchain->dump_size);
349}
350
351int record_opts__parse_callchain(struct record_opts *record,
352 struct callchain_param *callchain,
353 const char *arg, bool unset)
354{
355 int ret;
356
357 callchain->enabled = !unset;
358
359 /* --no-call-graph */
360 if (unset) {
361 callchain->record_mode = CALLCHAIN_NONE;
362 pr_debug("callchain: disabled\n");
363 return 0;
364 }
365
366 ret = parse_callchain_record_opt(arg, callchain);
367 if (!ret) {
368 /* Enable data address sampling for DWARF unwind. */
369 if (callchain->record_mode == CALLCHAIN_DWARF &&
370 !record->record_data_mmap_set)
371 record->record_data_mmap = true;
372 callchain_debug(callchain);
373 }
374
375 return ret;
376}
377
378int perf_callchain_config(const char *var, const char *value)
379{
380 char *endptr;
381
382 if (!strstarts(var, "call-graph."))
383 return 0;
384 var += sizeof("call-graph.") - 1;
385
386 if (!strcmp(var, "record-mode"))
387 return parse_callchain_record_opt(value, &callchain_param);
388 if (!strcmp(var, "dump-size")) {
389 unsigned long size = 0;
390 int ret;
391
392 ret = get_stack_size(value, &size);
393 callchain_param.dump_size = size;
394
395 return ret;
396 }
397 if (!strcmp(var, "print-type")){
398 int ret;
399 ret = parse_callchain_mode(value);
400 if (ret == -1)
401 pr_err("Invalid callchain mode: %s\n", value);
402 return ret;
403 }
404 if (!strcmp(var, "order")){
405 int ret;
406 ret = parse_callchain_order(value);
407 if (ret == -1)
408 pr_err("Invalid callchain order: %s\n", value);
409 return ret;
410 }
411 if (!strcmp(var, "sort-key")){
412 int ret;
413 ret = parse_callchain_sort_key(value);
414 if (ret == -1)
415 pr_err("Invalid callchain sort key: %s\n", value);
416 return ret;
417 }
418 if (!strcmp(var, "threshold")) {
419 callchain_param.min_percent = strtod(value, &endptr);
420 if (value == endptr) {
421 pr_err("Invalid callchain threshold: %s\n", value);
422 return -1;
423 }
424 }
425 if (!strcmp(var, "print-limit")) {
426 callchain_param.print_limit = strtod(value, &endptr);
427 if (value == endptr) {
428 pr_err("Invalid callchain print limit: %s\n", value);
429 return -1;
430 }
431 }
432
433 return 0;
434}
435
436static void
437rb_insert_callchain(struct rb_root *root, struct callchain_node *chain,
438 enum chain_mode mode)
439{
440 struct rb_node **p = &root->rb_node;
441 struct rb_node *parent = NULL;
442 struct callchain_node *rnode;
443 u64 chain_cumul = callchain_cumul_hits(chain);
444
445 while (*p) {
446 u64 rnode_cumul;
447
448 parent = *p;
449 rnode = rb_entry(parent, struct callchain_node, rb_node);
450 rnode_cumul = callchain_cumul_hits(rnode);
451
452 switch (mode) {
453 case CHAIN_FLAT:
454 case CHAIN_FOLDED:
455 if (rnode->hit < chain->hit)
456 p = &(*p)->rb_left;
457 else
458 p = &(*p)->rb_right;
459 break;
460 case CHAIN_GRAPH_ABS: /* Falldown */
461 case CHAIN_GRAPH_REL:
462 if (rnode_cumul < chain_cumul)
463 p = &(*p)->rb_left;
464 else
465 p = &(*p)->rb_right;
466 break;
467 case CHAIN_NONE:
468 default:
469 break;
470 }
471 }
472
473 rb_link_node(&chain->rb_node, parent, p);
474 rb_insert_color(&chain->rb_node, root);
475}
476
477static void
478__sort_chain_flat(struct rb_root *rb_root, struct callchain_node *node,
479 u64 min_hit)
480{
481 struct rb_node *n;
482 struct callchain_node *child;
483
484 n = rb_first(&node->rb_root_in);
485 while (n) {
486 child = rb_entry(n, struct callchain_node, rb_node_in);
487 n = rb_next(n);
488
489 __sort_chain_flat(rb_root, child, min_hit);
490 }
491
492 if (node->hit && node->hit >= min_hit)
493 rb_insert_callchain(rb_root, node, CHAIN_FLAT);
494}
495
496/*
497 * Once we get every callchains from the stream, we can now
498 * sort them by hit
499 */
500static void
501sort_chain_flat(struct rb_root *rb_root, struct callchain_root *root,
502 u64 min_hit, struct callchain_param *param __maybe_unused)
503{
504 *rb_root = RB_ROOT;
505 __sort_chain_flat(rb_root, &root->node, min_hit);
506}
507
508static void __sort_chain_graph_abs(struct callchain_node *node,
509 u64 min_hit)
510{
511 struct rb_node *n;
512 struct callchain_node *child;
513
514 node->rb_root = RB_ROOT;
515 n = rb_first(&node->rb_root_in);
516
517 while (n) {
518 child = rb_entry(n, struct callchain_node, rb_node_in);
519 n = rb_next(n);
520
521 __sort_chain_graph_abs(child, min_hit);
522 if (callchain_cumul_hits(child) >= min_hit)
523 rb_insert_callchain(&node->rb_root, child,
524 CHAIN_GRAPH_ABS);
525 }
526}
527
528static void
529sort_chain_graph_abs(struct rb_root *rb_root, struct callchain_root *chain_root,
530 u64 min_hit, struct callchain_param *param __maybe_unused)
531{
532 __sort_chain_graph_abs(&chain_root->node, min_hit);
533 rb_root->rb_node = chain_root->node.rb_root.rb_node;
534}
535
536static void __sort_chain_graph_rel(struct callchain_node *node,
537 double min_percent)
538{
539 struct rb_node *n;
540 struct callchain_node *child;
541 u64 min_hit;
542
543 node->rb_root = RB_ROOT;
544 min_hit = ceil(node->children_hit * min_percent);
545
546 n = rb_first(&node->rb_root_in);
547 while (n) {
548 child = rb_entry(n, struct callchain_node, rb_node_in);
549 n = rb_next(n);
550
551 __sort_chain_graph_rel(child, min_percent);
552 if (callchain_cumul_hits(child) >= min_hit)
553 rb_insert_callchain(&node->rb_root, child,
554 CHAIN_GRAPH_REL);
555 }
556}
557
558static void
559sort_chain_graph_rel(struct rb_root *rb_root, struct callchain_root *chain_root,
560 u64 min_hit __maybe_unused, struct callchain_param *param)
561{
562 __sort_chain_graph_rel(&chain_root->node, param->min_percent / 100.0);
563 rb_root->rb_node = chain_root->node.rb_root.rb_node;
564}
565
566int callchain_register_param(struct callchain_param *param)
567{
568 switch (param->mode) {
569 case CHAIN_GRAPH_ABS:
570 param->sort = sort_chain_graph_abs;
571 break;
572 case CHAIN_GRAPH_REL:
573 param->sort = sort_chain_graph_rel;
574 break;
575 case CHAIN_FLAT:
576 case CHAIN_FOLDED:
577 param->sort = sort_chain_flat;
578 break;
579 case CHAIN_NONE:
580 default:
581 return -1;
582 }
583 return 0;
584}
585
586/*
587 * Create a child for a parent. If inherit_children, then the new child
588 * will become the new parent of it's parent children
589 */
590static struct callchain_node *
591create_child(struct callchain_node *parent, bool inherit_children)
592{
593 struct callchain_node *new;
594
595 new = zalloc(sizeof(*new));
596 if (!new) {
597 perror("not enough memory to create child for code path tree");
598 return NULL;
599 }
600 new->parent = parent;
601 INIT_LIST_HEAD(&new->val);
602 INIT_LIST_HEAD(&new->parent_val);
603
604 if (inherit_children) {
605 struct rb_node *n;
606 struct callchain_node *child;
607
608 new->rb_root_in = parent->rb_root_in;
609 parent->rb_root_in = RB_ROOT;
610
611 n = rb_first(&new->rb_root_in);
612 while (n) {
613 child = rb_entry(n, struct callchain_node, rb_node_in);
614 child->parent = new;
615 n = rb_next(n);
616 }
617
618 /* make it the first child */
619 rb_link_node(&new->rb_node_in, NULL, &parent->rb_root_in.rb_node);
620 rb_insert_color(&new->rb_node_in, &parent->rb_root_in);
621 }
622
623 return new;
624}
625
626
627/*
628 * Fill the node with callchain values
629 */
630static int
631fill_node(struct callchain_node *node, struct callchain_cursor *cursor)
632{
633 struct callchain_cursor_node *cursor_node;
634
635 node->val_nr = cursor->nr - cursor->pos;
636 if (!node->val_nr)
637 pr_warning("Warning: empty node in callchain tree\n");
638
639 cursor_node = callchain_cursor_current(cursor);
640
641 while (cursor_node) {
642 struct callchain_list *call;
643
644 call = zalloc(sizeof(*call));
645 if (!call) {
646 perror("not enough memory for the code path tree");
647 return -ENOMEM;
648 }
649 call->ip = cursor_node->ip;
650 map_symbol__copy(&call->ms, &cursor_node->ms);
651 call->srcline = cursor_node->srcline;
652
653 if (cursor_node->branch) {
654 call->branch_count = 1;
655
656 if (cursor_node->branch_from) {
657 /*
658 * branch_from is set with value somewhere else
659 * to imply it's "to" of a branch.
660 */
661 if (!call->brtype_stat) {
662 call->brtype_stat = zalloc(sizeof(*call->brtype_stat));
663 if (!call->brtype_stat) {
664 perror("not enough memory for the code path branch statistics");
665 zfree(&call->brtype_stat);
666 return -ENOMEM;
667 }
668 }
669 call->brtype_stat->branch_to = true;
670
671 if (cursor_node->branch_flags.predicted)
672 call->predicted_count = 1;
673
674 if (cursor_node->branch_flags.abort)
675 call->abort_count = 1;
676
677 branch_type_count(call->brtype_stat,
678 &cursor_node->branch_flags,
679 cursor_node->branch_from,
680 cursor_node->ip);
681 } else {
682 /*
683 * It's "from" of a branch
684 */
685 if (call->brtype_stat && call->brtype_stat->branch_to)
686 call->brtype_stat->branch_to = false;
687 call->cycles_count =
688 cursor_node->branch_flags.cycles;
689 call->iter_count = cursor_node->nr_loop_iter;
690 call->iter_cycles = cursor_node->iter_cycles;
691 }
692 }
693
694 list_add_tail(&call->list, &node->val);
695
696 callchain_cursor_advance(cursor);
697 cursor_node = callchain_cursor_current(cursor);
698 }
699 return 0;
700}
701
702static struct callchain_node *
703add_child(struct callchain_node *parent,
704 struct callchain_cursor *cursor,
705 u64 period)
706{
707 struct callchain_node *new;
708
709 new = create_child(parent, false);
710 if (new == NULL)
711 return NULL;
712
713 if (fill_node(new, cursor) < 0) {
714 struct callchain_list *call, *tmp;
715
716 list_for_each_entry_safe(call, tmp, &new->val, list) {
717 list_del_init(&call->list);
718 map_symbol__exit(&call->ms);
719 zfree(&call->brtype_stat);
720 free(call);
721 }
722 free(new);
723 return NULL;
724 }
725
726 new->children_hit = 0;
727 new->hit = period;
728 new->children_count = 0;
729 new->count = 1;
730 return new;
731}
732
733enum match_result {
734 MATCH_ERROR = -1,
735 MATCH_EQ,
736 MATCH_LT,
737 MATCH_GT,
738};
739
740static enum match_result match_chain_strings(const char *left,
741 const char *right)
742{
743 enum match_result ret = MATCH_EQ;
744 int cmp;
745
746 if (left && right)
747 cmp = strcmp(left, right);
748 else if (!left && right)
749 cmp = 1;
750 else if (left && !right)
751 cmp = -1;
752 else
753 return MATCH_ERROR;
754
755 if (cmp != 0)
756 ret = cmp < 0 ? MATCH_LT : MATCH_GT;
757
758 return ret;
759}
760
761/*
762 * We need to always use relative addresses because we're aggregating
763 * callchains from multiple threads, i.e. different address spaces, so
764 * comparing absolute addresses make no sense as a symbol in a DSO may end up
765 * in a different address when used in a different binary or even the same
766 * binary but with some sort of address randomization technique, thus we need
767 * to compare just relative addresses. -acme
768 */
769static enum match_result match_chain_dso_addresses(struct map *left_map, u64 left_ip,
770 struct map *right_map, u64 right_ip)
771{
772 struct dso *left_dso = left_map ? map__dso(left_map) : NULL;
773 struct dso *right_dso = right_map ? map__dso(right_map) : NULL;
774
775 if (left_dso != right_dso)
776 return left_dso < right_dso ? MATCH_LT : MATCH_GT;
777
778 if (left_ip != right_ip)
779 return left_ip < right_ip ? MATCH_LT : MATCH_GT;
780
781 return MATCH_EQ;
782}
783
784static enum match_result match_chain(struct callchain_cursor_node *node,
785 struct callchain_list *cnode)
786{
787 enum match_result match = MATCH_ERROR;
788
789 switch (callchain_param.key) {
790 case CCKEY_SRCLINE:
791 match = match_chain_strings(cnode->srcline, node->srcline);
792 if (match != MATCH_ERROR)
793 break;
794 /* otherwise fall-back to symbol-based comparison below */
795 fallthrough;
796 case CCKEY_FUNCTION:
797 if (node->ms.sym && cnode->ms.sym) {
798 /*
799 * Compare inlined frames based on their symbol name
800 * because different inlined frames will have the same
801 * symbol start. Otherwise do a faster comparison based
802 * on the symbol start address.
803 */
804 if (symbol__inlined(cnode->ms.sym) || symbol__inlined(node->ms.sym)) {
805 match = match_chain_strings(cnode->ms.sym->name,
806 node->ms.sym->name);
807 if (match != MATCH_ERROR)
808 break;
809 } else {
810 match = match_chain_dso_addresses(cnode->ms.map, cnode->ms.sym->start,
811 node->ms.map, node->ms.sym->start);
812 break;
813 }
814 }
815 /* otherwise fall-back to IP-based comparison below */
816 fallthrough;
817 case CCKEY_ADDRESS:
818 default:
819 match = match_chain_dso_addresses(cnode->ms.map, cnode->ip, node->ms.map, node->ip);
820 break;
821 }
822
823 if (match == MATCH_EQ && node->branch) {
824 cnode->branch_count++;
825
826 if (node->branch_from) {
827 /*
828 * It's "to" of a branch
829 */
830 if (!cnode->brtype_stat) {
831 cnode->brtype_stat = zalloc(sizeof(*cnode->brtype_stat));
832 if (!cnode->brtype_stat) {
833 perror("not enough memory for the code path branch statistics");
834 return MATCH_ERROR;
835 }
836 }
837 cnode->brtype_stat->branch_to = true;
838
839 if (node->branch_flags.predicted)
840 cnode->predicted_count++;
841
842 if (node->branch_flags.abort)
843 cnode->abort_count++;
844
845 branch_type_count(cnode->brtype_stat,
846 &node->branch_flags,
847 node->branch_from,
848 node->ip);
849 } else {
850 /*
851 * It's "from" of a branch
852 */
853 if (cnode->brtype_stat && cnode->brtype_stat->branch_to)
854 cnode->brtype_stat->branch_to = false;
855 cnode->cycles_count += node->branch_flags.cycles;
856 cnode->iter_count += node->nr_loop_iter;
857 cnode->iter_cycles += node->iter_cycles;
858 cnode->from_count++;
859 }
860 }
861
862 return match;
863}
864
865/*
866 * Split the parent in two parts (a new child is created) and
867 * give a part of its callchain to the created child.
868 * Then create another child to host the given callchain of new branch
869 */
870static int
871split_add_child(struct callchain_node *parent,
872 struct callchain_cursor *cursor,
873 struct callchain_list *to_split,
874 u64 idx_parents, u64 idx_local, u64 period)
875{
876 struct callchain_node *new;
877 struct list_head *old_tail;
878 unsigned int idx_total = idx_parents + idx_local;
879
880 /* split */
881 new = create_child(parent, true);
882 if (new == NULL)
883 return -1;
884
885 /* split the callchain and move a part to the new child */
886 old_tail = parent->val.prev;
887 list_del_range(&to_split->list, old_tail);
888 new->val.next = &to_split->list;
889 new->val.prev = old_tail;
890 to_split->list.prev = &new->val;
891 old_tail->next = &new->val;
892
893 /* split the hits */
894 new->hit = parent->hit;
895 new->children_hit = parent->children_hit;
896 parent->children_hit = callchain_cumul_hits(new);
897 new->val_nr = parent->val_nr - idx_local;
898 parent->val_nr = idx_local;
899 new->count = parent->count;
900 new->children_count = parent->children_count;
901 parent->children_count = callchain_cumul_counts(new);
902
903 /* create a new child for the new branch if any */
904 if (idx_total < cursor->nr) {
905 struct callchain_node *first;
906 struct callchain_list *cnode;
907 struct callchain_cursor_node *node;
908 struct rb_node *p, **pp;
909
910 parent->hit = 0;
911 parent->children_hit += period;
912 parent->count = 0;
913 parent->children_count += 1;
914
915 node = callchain_cursor_current(cursor);
916 new = add_child(parent, cursor, period);
917 if (new == NULL)
918 return -1;
919
920 /*
921 * This is second child since we moved parent's children
922 * to new (first) child above.
923 */
924 p = parent->rb_root_in.rb_node;
925 first = rb_entry(p, struct callchain_node, rb_node_in);
926 cnode = list_first_entry(&first->val, struct callchain_list,
927 list);
928
929 if (match_chain(node, cnode) == MATCH_LT)
930 pp = &p->rb_left;
931 else
932 pp = &p->rb_right;
933
934 rb_link_node(&new->rb_node_in, p, pp);
935 rb_insert_color(&new->rb_node_in, &parent->rb_root_in);
936 } else {
937 parent->hit = period;
938 parent->count = 1;
939 }
940 return 0;
941}
942
943static enum match_result
944append_chain(struct callchain_node *root,
945 struct callchain_cursor *cursor,
946 u64 period);
947
948static int
949append_chain_children(struct callchain_node *root,
950 struct callchain_cursor *cursor,
951 u64 period)
952{
953 struct callchain_node *rnode;
954 struct callchain_cursor_node *node;
955 struct rb_node **p = &root->rb_root_in.rb_node;
956 struct rb_node *parent = NULL;
957
958 node = callchain_cursor_current(cursor);
959 if (!node)
960 return -1;
961
962 /* lookup in children */
963 while (*p) {
964 enum match_result ret;
965
966 parent = *p;
967 rnode = rb_entry(parent, struct callchain_node, rb_node_in);
968
969 /* If at least first entry matches, rely to children */
970 ret = append_chain(rnode, cursor, period);
971 if (ret == MATCH_EQ)
972 goto inc_children_hit;
973 if (ret == MATCH_ERROR)
974 return -1;
975
976 if (ret == MATCH_LT)
977 p = &parent->rb_left;
978 else
979 p = &parent->rb_right;
980 }
981 /* nothing in children, add to the current node */
982 rnode = add_child(root, cursor, period);
983 if (rnode == NULL)
984 return -1;
985
986 rb_link_node(&rnode->rb_node_in, parent, p);
987 rb_insert_color(&rnode->rb_node_in, &root->rb_root_in);
988
989inc_children_hit:
990 root->children_hit += period;
991 root->children_count++;
992 return 0;
993}
994
995static enum match_result
996append_chain(struct callchain_node *root,
997 struct callchain_cursor *cursor,
998 u64 period)
999{
1000 struct callchain_list *cnode;
1001 u64 start = cursor->pos;
1002 bool found = false;
1003 u64 matches;
1004 enum match_result cmp = MATCH_ERROR;
1005
1006 /*
1007 * Lookup in the current node
1008 * If we have a symbol, then compare the start to match
1009 * anywhere inside a function, unless function
1010 * mode is disabled.
1011 */
1012 list_for_each_entry(cnode, &root->val, list) {
1013 struct callchain_cursor_node *node;
1014
1015 node = callchain_cursor_current(cursor);
1016 if (!node)
1017 break;
1018
1019 cmp = match_chain(node, cnode);
1020 if (cmp != MATCH_EQ)
1021 break;
1022
1023 found = true;
1024
1025 callchain_cursor_advance(cursor);
1026 }
1027
1028 /* matches not, relay no the parent */
1029 if (!found) {
1030 WARN_ONCE(cmp == MATCH_ERROR, "Chain comparison error\n");
1031 return cmp;
1032 }
1033
1034 matches = cursor->pos - start;
1035
1036 /* we match only a part of the node. Split it and add the new chain */
1037 if (matches < root->val_nr) {
1038 if (split_add_child(root, cursor, cnode, start, matches,
1039 period) < 0)
1040 return MATCH_ERROR;
1041
1042 return MATCH_EQ;
1043 }
1044
1045 /* we match 100% of the path, increment the hit */
1046 if (matches == root->val_nr && cursor->pos == cursor->nr) {
1047 root->hit += period;
1048 root->count++;
1049 return MATCH_EQ;
1050 }
1051
1052 /* We match the node and still have a part remaining */
1053 if (append_chain_children(root, cursor, period) < 0)
1054 return MATCH_ERROR;
1055
1056 return MATCH_EQ;
1057}
1058
1059int callchain_append(struct callchain_root *root,
1060 struct callchain_cursor *cursor,
1061 u64 period)
1062{
1063 if (cursor == NULL)
1064 return -1;
1065
1066 if (!cursor->nr)
1067 return 0;
1068
1069 callchain_cursor_commit(cursor);
1070
1071 if (append_chain_children(&root->node, cursor, period) < 0)
1072 return -1;
1073
1074 if (cursor->nr > root->max_depth)
1075 root->max_depth = cursor->nr;
1076
1077 return 0;
1078}
1079
1080static int
1081merge_chain_branch(struct callchain_cursor *cursor,
1082 struct callchain_node *dst, struct callchain_node *src)
1083{
1084 struct callchain_cursor_node **old_last = cursor->last;
1085 struct callchain_node *child;
1086 struct callchain_list *list, *next_list;
1087 struct rb_node *n;
1088 int old_pos = cursor->nr;
1089 int err = 0;
1090
1091 list_for_each_entry_safe(list, next_list, &src->val, list) {
1092 struct map_symbol ms = {
1093 .thread = thread__get(list->ms.thread),
1094 .map = map__get(list->ms.map),
1095 };
1096 callchain_cursor_append(cursor, list->ip, &ms, false, NULL, 0, 0, 0, list->srcline);
1097 list_del_init(&list->list);
1098 map_symbol__exit(&ms);
1099 map_symbol__exit(&list->ms);
1100 zfree(&list->brtype_stat);
1101 free(list);
1102 }
1103
1104 if (src->hit) {
1105 callchain_cursor_commit(cursor);
1106 if (append_chain_children(dst, cursor, src->hit) < 0)
1107 return -1;
1108 }
1109
1110 n = rb_first(&src->rb_root_in);
1111 while (n) {
1112 child = container_of(n, struct callchain_node, rb_node_in);
1113 n = rb_next(n);
1114 rb_erase(&child->rb_node_in, &src->rb_root_in);
1115
1116 err = merge_chain_branch(cursor, dst, child);
1117 if (err)
1118 break;
1119
1120 free(child);
1121 }
1122
1123 cursor->nr = old_pos;
1124 cursor->last = old_last;
1125
1126 return err;
1127}
1128
1129int callchain_merge(struct callchain_cursor *cursor,
1130 struct callchain_root *dst, struct callchain_root *src)
1131{
1132 return merge_chain_branch(cursor, &dst->node, &src->node);
1133}
1134
1135int callchain_cursor_append(struct callchain_cursor *cursor,
1136 u64 ip, struct map_symbol *ms,
1137 bool branch, struct branch_flags *flags,
1138 int nr_loop_iter, u64 iter_cycles, u64 branch_from,
1139 const char *srcline)
1140{
1141 struct callchain_cursor_node *node = *cursor->last;
1142
1143 if (!node) {
1144 node = calloc(1, sizeof(*node));
1145 if (!node)
1146 return -ENOMEM;
1147
1148 *cursor->last = node;
1149 }
1150
1151 node->ip = ip;
1152 map_symbol__exit(&node->ms);
1153 map_symbol__copy(&node->ms, ms);
1154 node->branch = branch;
1155 node->nr_loop_iter = nr_loop_iter;
1156 node->iter_cycles = iter_cycles;
1157 node->srcline = srcline;
1158
1159 if (flags)
1160 memcpy(&node->branch_flags, flags,
1161 sizeof(struct branch_flags));
1162
1163 node->branch_from = branch_from;
1164 cursor->nr++;
1165
1166 cursor->last = &node->next;
1167
1168 return 0;
1169}
1170
1171int sample__resolve_callchain(struct perf_sample *sample,
1172 struct callchain_cursor *cursor, struct symbol **parent,
1173 struct addr_location *al,
1174 int max_stack)
1175{
1176 if (sample->callchain == NULL && !symbol_conf.show_branchflag_count)
1177 return 0;
1178
1179 if (symbol_conf.use_callchain || symbol_conf.cumulate_callchain ||
1180 perf_hpp_list.parent || symbol_conf.show_branchflag_count) {
1181 return thread__resolve_callchain(al->thread, cursor, sample,
1182 parent, al, max_stack);
1183 }
1184 return 0;
1185}
1186
1187int hist_entry__append_callchain(struct hist_entry *he, struct perf_sample *sample)
1188{
1189 if ((!symbol_conf.use_callchain || sample->callchain == NULL) &&
1190 !symbol_conf.show_branchflag_count)
1191 return 0;
1192 return callchain_append(he->callchain, get_tls_callchain_cursor(), sample->period);
1193}
1194
1195int fill_callchain_info(struct addr_location *al, struct callchain_cursor_node *node,
1196 bool hide_unresolved)
1197{
1198 struct machine *machine = NULL;
1199
1200 if (node->ms.thread)
1201 machine = maps__machine(thread__maps(node->ms.thread));
1202
1203 map__put(al->map);
1204 al->map = map__get(node->ms.map);
1205 al->sym = node->ms.sym;
1206 al->srcline = node->srcline;
1207 al->addr = node->ip;
1208
1209 if (al->sym == NULL) {
1210 if (hide_unresolved)
1211 return 0;
1212 if (al->map == NULL)
1213 goto out;
1214 }
1215 if (maps__equal(thread__maps(al->thread), machine__kernel_maps(machine))) {
1216 if (machine__is_host(machine)) {
1217 al->cpumode = PERF_RECORD_MISC_KERNEL;
1218 al->level = 'k';
1219 } else {
1220 al->cpumode = PERF_RECORD_MISC_GUEST_KERNEL;
1221 al->level = 'g';
1222 }
1223 } else {
1224 if (machine__is_host(machine)) {
1225 al->cpumode = PERF_RECORD_MISC_USER;
1226 al->level = '.';
1227 } else if (perf_guest) {
1228 al->cpumode = PERF_RECORD_MISC_GUEST_USER;
1229 al->level = 'u';
1230 } else {
1231 al->cpumode = PERF_RECORD_MISC_HYPERVISOR;
1232 al->level = 'H';
1233 }
1234 }
1235
1236out:
1237 return 1;
1238}
1239
1240char *callchain_list__sym_name(struct callchain_list *cl,
1241 char *bf, size_t bfsize, bool show_dso)
1242{
1243 bool show_addr = callchain_param.key == CCKEY_ADDRESS;
1244 bool show_srcline = show_addr || callchain_param.key == CCKEY_SRCLINE;
1245 int printed;
1246
1247 if (cl->ms.sym) {
1248 const char *inlined = symbol__inlined(cl->ms.sym) ? " (inlined)" : "";
1249
1250 if (show_srcline && cl->srcline)
1251 printed = scnprintf(bf, bfsize, "%s %s%s",
1252 cl->ms.sym->name, cl->srcline,
1253 inlined);
1254 else
1255 printed = scnprintf(bf, bfsize, "%s%s",
1256 cl->ms.sym->name, inlined);
1257 } else
1258 printed = scnprintf(bf, bfsize, "%#" PRIx64, cl->ip);
1259
1260 if (show_dso)
1261 scnprintf(bf + printed, bfsize - printed, " %s",
1262 cl->ms.map ?
1263 dso__short_name(map__dso(cl->ms.map)) :
1264 "unknown");
1265
1266 return bf;
1267}
1268
1269char *callchain_node__scnprintf_value(struct callchain_node *node,
1270 char *bf, size_t bfsize, u64 total)
1271{
1272 double percent = 0.0;
1273 u64 period = callchain_cumul_hits(node);
1274 unsigned count = callchain_cumul_counts(node);
1275
1276 if (callchain_param.mode == CHAIN_FOLDED) {
1277 period = node->hit;
1278 count = node->count;
1279 }
1280
1281 switch (callchain_param.value) {
1282 case CCVAL_PERIOD:
1283 scnprintf(bf, bfsize, "%"PRIu64, period);
1284 break;
1285 case CCVAL_COUNT:
1286 scnprintf(bf, bfsize, "%u", count);
1287 break;
1288 case CCVAL_PERCENT:
1289 default:
1290 if (total)
1291 percent = period * 100.0 / total;
1292 scnprintf(bf, bfsize, "%.2f%%", percent);
1293 break;
1294 }
1295 return bf;
1296}
1297
1298int callchain_node__fprintf_value(struct callchain_node *node,
1299 FILE *fp, u64 total)
1300{
1301 double percent = 0.0;
1302 u64 period = callchain_cumul_hits(node);
1303 unsigned count = callchain_cumul_counts(node);
1304
1305 if (callchain_param.mode == CHAIN_FOLDED) {
1306 period = node->hit;
1307 count = node->count;
1308 }
1309
1310 switch (callchain_param.value) {
1311 case CCVAL_PERIOD:
1312 return fprintf(fp, "%"PRIu64, period);
1313 case CCVAL_COUNT:
1314 return fprintf(fp, "%u", count);
1315 case CCVAL_PERCENT:
1316 default:
1317 if (total)
1318 percent = period * 100.0 / total;
1319 return percent_color_fprintf(fp, "%.2f%%", percent);
1320 }
1321 return 0;
1322}
1323
1324static void callchain_counts_value(struct callchain_node *node,
1325 u64 *branch_count, u64 *predicted_count,
1326 u64 *abort_count, u64 *cycles_count)
1327{
1328 struct callchain_list *clist;
1329
1330 list_for_each_entry(clist, &node->val, list) {
1331 if (branch_count)
1332 *branch_count += clist->branch_count;
1333
1334 if (predicted_count)
1335 *predicted_count += clist->predicted_count;
1336
1337 if (abort_count)
1338 *abort_count += clist->abort_count;
1339
1340 if (cycles_count)
1341 *cycles_count += clist->cycles_count;
1342 }
1343}
1344
1345static int callchain_node_branch_counts_cumul(struct callchain_node *node,
1346 u64 *branch_count,
1347 u64 *predicted_count,
1348 u64 *abort_count,
1349 u64 *cycles_count)
1350{
1351 struct callchain_node *child;
1352 struct rb_node *n;
1353
1354 n = rb_first(&node->rb_root_in);
1355 while (n) {
1356 child = rb_entry(n, struct callchain_node, rb_node_in);
1357 n = rb_next(n);
1358
1359 callchain_node_branch_counts_cumul(child, branch_count,
1360 predicted_count,
1361 abort_count,
1362 cycles_count);
1363
1364 callchain_counts_value(child, branch_count,
1365 predicted_count, abort_count,
1366 cycles_count);
1367 }
1368
1369 return 0;
1370}
1371
1372int callchain_branch_counts(struct callchain_root *root,
1373 u64 *branch_count, u64 *predicted_count,
1374 u64 *abort_count, u64 *cycles_count)
1375{
1376 if (branch_count)
1377 *branch_count = 0;
1378
1379 if (predicted_count)
1380 *predicted_count = 0;
1381
1382 if (abort_count)
1383 *abort_count = 0;
1384
1385 if (cycles_count)
1386 *cycles_count = 0;
1387
1388 return callchain_node_branch_counts_cumul(&root->node,
1389 branch_count,
1390 predicted_count,
1391 abort_count,
1392 cycles_count);
1393}
1394
1395static int count_pri64_printf(int idx, const char *str, u64 value, char *bf, int bfsize)
1396{
1397 return scnprintf(bf, bfsize, "%s%s:%" PRId64 "", (idx) ? " " : " (", str, value);
1398}
1399
1400static int count_float_printf(int idx, const char *str, float value,
1401 char *bf, int bfsize, float threshold)
1402{
1403 if (threshold != 0.0 && value < threshold)
1404 return 0;
1405
1406 return scnprintf(bf, bfsize, "%s%s:%.1f%%", (idx) ? " " : " (", str, value);
1407}
1408
1409static int branch_to_str(char *bf, int bfsize,
1410 u64 branch_count, u64 predicted_count,
1411 u64 abort_count,
1412 const struct branch_type_stat *brtype_stat)
1413{
1414 int printed, i = 0;
1415
1416 printed = branch_type_str(brtype_stat, bf, bfsize);
1417 if (printed)
1418 i++;
1419
1420 if (predicted_count < branch_count) {
1421 printed += count_float_printf(i++, "predicted",
1422 predicted_count * 100.0 / branch_count,
1423 bf + printed, bfsize - printed, 0.0);
1424 }
1425
1426 if (abort_count) {
1427 printed += count_float_printf(i++, "abort",
1428 abort_count * 100.0 / branch_count,
1429 bf + printed, bfsize - printed, 0.1);
1430 }
1431
1432 if (i)
1433 printed += scnprintf(bf + printed, bfsize - printed, ")");
1434
1435 return printed;
1436}
1437
1438static int branch_from_str(char *bf, int bfsize,
1439 u64 branch_count,
1440 u64 cycles_count, u64 iter_count,
1441 u64 iter_cycles, u64 from_count)
1442{
1443 int printed = 0, i = 0;
1444 u64 cycles, v = 0;
1445
1446 cycles = cycles_count / branch_count;
1447 if (cycles) {
1448 printed += count_pri64_printf(i++, "cycles",
1449 cycles,
1450 bf + printed, bfsize - printed);
1451 }
1452
1453 if (iter_count && from_count) {
1454 v = iter_count / from_count;
1455 if (v) {
1456 printed += count_pri64_printf(i++, "iter",
1457 v, bf + printed, bfsize - printed);
1458
1459 printed += count_pri64_printf(i++, "avg_cycles",
1460 iter_cycles / iter_count,
1461 bf + printed, bfsize - printed);
1462 }
1463 }
1464
1465 if (i)
1466 printed += scnprintf(bf + printed, bfsize - printed, ")");
1467
1468 return printed;
1469}
1470
1471static int counts_str_build(char *bf, int bfsize,
1472 u64 branch_count, u64 predicted_count,
1473 u64 abort_count, u64 cycles_count,
1474 u64 iter_count, u64 iter_cycles,
1475 u64 from_count,
1476 const struct branch_type_stat *brtype_stat)
1477{
1478 int printed;
1479
1480 if (branch_count == 0)
1481 return scnprintf(bf, bfsize, " (calltrace)");
1482
1483 if (brtype_stat->branch_to) {
1484 printed = branch_to_str(bf, bfsize, branch_count,
1485 predicted_count, abort_count, brtype_stat);
1486 } else {
1487 printed = branch_from_str(bf, bfsize, branch_count,
1488 cycles_count, iter_count, iter_cycles,
1489 from_count);
1490 }
1491
1492 if (!printed)
1493 bf[0] = 0;
1494
1495 return printed;
1496}
1497
1498static int callchain_counts_printf(FILE *fp, char *bf, int bfsize,
1499 u64 branch_count, u64 predicted_count,
1500 u64 abort_count, u64 cycles_count,
1501 u64 iter_count, u64 iter_cycles,
1502 u64 from_count,
1503 const struct branch_type_stat *brtype_stat)
1504{
1505 char str[256];
1506
1507 counts_str_build(str, sizeof(str), branch_count,
1508 predicted_count, abort_count, cycles_count,
1509 iter_count, iter_cycles, from_count, brtype_stat);
1510
1511 if (fp)
1512 return fprintf(fp, "%s", str);
1513
1514 return scnprintf(bf, bfsize, "%s", str);
1515}
1516
1517int callchain_list_counts__printf_value(struct callchain_list *clist,
1518 FILE *fp, char *bf, int bfsize)
1519{
1520 static const struct branch_type_stat empty_brtype_stat = {};
1521 const struct branch_type_stat *brtype_stat;
1522 u64 branch_count, predicted_count;
1523 u64 abort_count, cycles_count;
1524 u64 iter_count, iter_cycles;
1525 u64 from_count;
1526
1527 brtype_stat = clist->brtype_stat ?: &empty_brtype_stat;
1528 branch_count = clist->branch_count;
1529 predicted_count = clist->predicted_count;
1530 abort_count = clist->abort_count;
1531 cycles_count = clist->cycles_count;
1532 iter_count = clist->iter_count;
1533 iter_cycles = clist->iter_cycles;
1534 from_count = clist->from_count;
1535
1536 return callchain_counts_printf(fp, bf, bfsize, branch_count,
1537 predicted_count, abort_count,
1538 cycles_count, iter_count, iter_cycles,
1539 from_count, brtype_stat);
1540}
1541
1542static void free_callchain_node(struct callchain_node *node)
1543{
1544 struct callchain_list *list, *tmp;
1545 struct callchain_node *child;
1546 struct rb_node *n;
1547
1548 list_for_each_entry_safe(list, tmp, &node->parent_val, list) {
1549 list_del_init(&list->list);
1550 map_symbol__exit(&list->ms);
1551 zfree(&list->brtype_stat);
1552 free(list);
1553 }
1554
1555 list_for_each_entry_safe(list, tmp, &node->val, list) {
1556 list_del_init(&list->list);
1557 map_symbol__exit(&list->ms);
1558 zfree(&list->brtype_stat);
1559 free(list);
1560 }
1561
1562 n = rb_first(&node->rb_root_in);
1563 while (n) {
1564 child = container_of(n, struct callchain_node, rb_node_in);
1565 n = rb_next(n);
1566 rb_erase(&child->rb_node_in, &node->rb_root_in);
1567
1568 free_callchain_node(child);
1569 free(child);
1570 }
1571}
1572
1573void free_callchain(struct callchain_root *root)
1574{
1575 if (!symbol_conf.use_callchain)
1576 return;
1577
1578 free_callchain_node(&root->node);
1579}
1580
1581void callchain_cursor_cleanup(struct callchain_cursor *cursor)
1582{
1583 struct callchain_cursor_node *node, *next;
1584
1585 callchain_cursor_reset(cursor);
1586
1587 for (node = cursor->first; node; node = next) {
1588 next = node->next;
1589 free(node);
1590 }
1591 cursor->first = NULL;
1592 cursor->last = &cursor->first;
1593 cursor->curr = NULL;
1594}
1595
1596static u64 decay_callchain_node(struct callchain_node *node)
1597{
1598 struct callchain_node *child;
1599 struct rb_node *n;
1600 u64 child_hits = 0;
1601
1602 n = rb_first(&node->rb_root_in);
1603 while (n) {
1604 child = container_of(n, struct callchain_node, rb_node_in);
1605
1606 child_hits += decay_callchain_node(child);
1607 n = rb_next(n);
1608 }
1609
1610 node->hit = (node->hit * 7) / 8;
1611 node->children_hit = child_hits;
1612
1613 return node->hit;
1614}
1615
1616void decay_callchain(struct callchain_root *root)
1617{
1618 if (!symbol_conf.use_callchain)
1619 return;
1620
1621 decay_callchain_node(&root->node);
1622}
1623
1624int callchain_node__make_parent_list(struct callchain_node *node)
1625{
1626 struct callchain_node *parent = node->parent;
1627 struct callchain_list *chain, *new;
1628 LIST_HEAD(head);
1629
1630 while (parent) {
1631 list_for_each_entry_reverse(chain, &parent->val, list) {
1632 new = malloc(sizeof(*new));
1633 if (new == NULL)
1634 goto out;
1635 *new = *chain;
1636 new->has_children = false;
1637 map_symbol__copy(&new->ms, &chain->ms);
1638 list_add_tail(&new->list, &head);
1639 }
1640 parent = parent->parent;
1641 }
1642
1643 list_for_each_entry_safe_reverse(chain, new, &head, list)
1644 list_move_tail(&chain->list, &node->parent_val);
1645
1646 if (!list_empty(&node->parent_val)) {
1647 chain = list_first_entry(&node->parent_val, struct callchain_list, list);
1648 chain->has_children = rb_prev(&node->rb_node) || rb_next(&node->rb_node);
1649
1650 chain = list_first_entry(&node->val, struct callchain_list, list);
1651 chain->has_children = false;
1652 }
1653 return 0;
1654
1655out:
1656 list_for_each_entry_safe(chain, new, &head, list) {
1657 list_del_init(&chain->list);
1658 map_symbol__exit(&chain->ms);
1659 zfree(&chain->brtype_stat);
1660 free(chain);
1661 }
1662 return -ENOMEM;
1663}
1664
1665static void callchain_cursor__delete(void *vcursor)
1666{
1667 struct callchain_cursor *cursor = vcursor;
1668 struct callchain_cursor_node *node, *next;
1669
1670 callchain_cursor_reset(cursor);
1671 for (node = cursor->first; node != NULL; node = next) {
1672 next = node->next;
1673 free(node);
1674 }
1675 free(cursor);
1676}
1677
1678static void init_callchain_cursor_key(void)
1679{
1680 if (pthread_key_create(&callchain_cursor, callchain_cursor__delete)) {
1681 pr_err("callchain cursor creation failed");
1682 abort();
1683 }
1684}
1685
1686struct callchain_cursor *get_tls_callchain_cursor(void)
1687{
1688 static pthread_once_t once_control = PTHREAD_ONCE_INIT;
1689 struct callchain_cursor *cursor;
1690
1691 pthread_once(&once_control, init_callchain_cursor_key);
1692 cursor = pthread_getspecific(callchain_cursor);
1693 if (!cursor) {
1694 cursor = zalloc(sizeof(*cursor));
1695 if (!cursor)
1696 pr_debug3("%s: not enough memory\n", __func__);
1697 pthread_setspecific(callchain_cursor, cursor);
1698 }
1699 return cursor;
1700}
1701
1702int callchain_cursor__copy(struct callchain_cursor *dst,
1703 struct callchain_cursor *src)
1704{
1705 int rc = 0;
1706
1707 callchain_cursor_reset(dst);
1708 callchain_cursor_commit(src);
1709
1710 while (true) {
1711 struct callchain_cursor_node *node;
1712
1713 node = callchain_cursor_current(src);
1714 if (node == NULL)
1715 break;
1716
1717 rc = callchain_cursor_append(dst, node->ip, &node->ms,
1718 node->branch, &node->branch_flags,
1719 node->nr_loop_iter,
1720 node->iter_cycles,
1721 node->branch_from, node->srcline);
1722 if (rc)
1723 break;
1724
1725 callchain_cursor_advance(src);
1726 }
1727
1728 return rc;
1729}
1730
1731/*
1732 * Initialize a cursor before adding entries inside, but keep
1733 * the previously allocated entries as a cache.
1734 */
1735void callchain_cursor_reset(struct callchain_cursor *cursor)
1736{
1737 struct callchain_cursor_node *node;
1738
1739 cursor->nr = 0;
1740 cursor->last = &cursor->first;
1741
1742 for (node = cursor->first; node != NULL; node = node->next)
1743 map_symbol__exit(&node->ms);
1744}
1745
1746void callchain_param_setup(u64 sample_type, uint16_t e_machine)
1747{
1748 if (symbol_conf.use_callchain || symbol_conf.cumulate_callchain) {
1749 if ((sample_type & PERF_SAMPLE_REGS_USER) &&
1750 (sample_type & PERF_SAMPLE_STACK_USER)) {
1751 callchain_param.record_mode = CALLCHAIN_DWARF;
1752 dwarf_callchain_users = true;
1753 } else if (sample_type & PERF_SAMPLE_BRANCH_STACK)
1754 callchain_param.record_mode = CALLCHAIN_LBR;
1755 else
1756 callchain_param.record_mode = CALLCHAIN_FP;
1757 }
1758
1759 /*
1760 * It's necessary to use libunwind to reliably determine the caller of
1761 * a leaf function on aarch64, as otherwise we cannot know whether to
1762 * start from the LR or FP.
1763 *
1764 * Always starting from the LR can result in duplicate or entirely
1765 * erroneous entries. Always skipping the LR and starting from the FP
1766 * can result in missing entries.
1767 */
1768 if (callchain_param.record_mode == CALLCHAIN_FP && e_machine == EM_AARCH64)
1769 dwarf_callchain_users = true;
1770}
1771
1772static bool chain_match(struct callchain_list *base_chain,
1773 struct callchain_list *pair_chain)
1774{
1775 enum match_result match;
1776
1777 match = match_chain_strings(base_chain->srcline,
1778 pair_chain->srcline);
1779 if (match != MATCH_ERROR)
1780 return match == MATCH_EQ;
1781
1782 match = match_chain_dso_addresses(base_chain->ms.map,
1783 base_chain->ip,
1784 pair_chain->ms.map,
1785 pair_chain->ip);
1786
1787 return match == MATCH_EQ;
1788}
1789
1790bool callchain_cnode_matched(struct callchain_node *base_cnode,
1791 struct callchain_node *pair_cnode)
1792{
1793 struct callchain_list *base_chain, *pair_chain;
1794 bool match = false;
1795
1796 pair_chain = list_first_entry(&pair_cnode->val,
1797 struct callchain_list,
1798 list);
1799
1800 list_for_each_entry(base_chain, &base_cnode->val, list) {
1801 if (&pair_chain->list == &pair_cnode->val)
1802 return false;
1803
1804 if (!base_chain->srcline || !pair_chain->srcline) {
1805 pair_chain = list_next_entry(pair_chain, list);
1806 continue;
1807 }
1808
1809 match = chain_match(base_chain, pair_chain);
1810 if (!match)
1811 return false;
1812
1813 pair_chain = list_next_entry(pair_chain, list);
1814 }
1815
1816 /*
1817 * Say chain1 is ABC, chain2 is ABCD, we consider they are
1818 * not fully matched.
1819 */
1820 if (pair_chain && (&pair_chain->list != &pair_cnode->val))
1821 return false;
1822
1823 return match;
1824}
1825
1826static u64 count_callchain_hits(struct hist_entry *he)
1827{
1828 struct rb_root *root = &he->sorted_chain;
1829 struct rb_node *rb_node = rb_first(root);
1830 struct callchain_node *node;
1831 u64 chain_hits = 0;
1832
1833 while (rb_node) {
1834 node = rb_entry(rb_node, struct callchain_node, rb_node);
1835 chain_hits += node->hit;
1836 rb_node = rb_next(rb_node);
1837 }
1838
1839 return chain_hits;
1840}
1841
1842u64 callchain_total_hits(struct hists *hists)
1843{
1844 struct rb_node *next = rb_first_cached(&hists->entries);
1845 u64 chain_hits = 0;
1846
1847 while (next) {
1848 struct hist_entry *he = rb_entry(next, struct hist_entry,
1849 rb_node);
1850
1851 chain_hits += count_callchain_hits(he);
1852 next = rb_next(&he->rb_node);
1853 }
1854
1855 return chain_hits;
1856}
1857
1858s64 callchain_avg_cycles(struct callchain_node *cnode)
1859{
1860 struct callchain_list *chain;
1861 s64 cycles = 0;
1862
1863 list_for_each_entry(chain, &cnode->val, list) {
1864 if (chain->srcline && chain->branch_count)
1865 cycles += chain->cycles_count / chain->branch_count;
1866 }
1867
1868 return cycles;
1869}
1870
1871int sample__for_each_callchain_node(struct thread *thread,
1872 struct perf_sample *sample, int max_stack,
1873 bool symbols, callchain_iter_fn cb, void *data)
1874{
1875 struct callchain_cursor *cursor = get_tls_callchain_cursor();
1876 int ret;
1877
1878 if (!cursor)
1879 return -ENOMEM;
1880
1881 /* Fill in the callchain. */
1882 ret = __thread__resolve_callchain(thread, cursor, sample,
1883 /*parent=*/NULL, /*root_al=*/NULL,
1884 max_stack, symbols);
1885 if (ret)
1886 return ret;
1887
1888 /* Switch from writing the callchain to reading it. */
1889 callchain_cursor_commit(cursor);
1890
1891 while (1) {
1892 struct callchain_cursor_node *node = callchain_cursor_current(cursor);
1893
1894 if (!node)
1895 break;
1896
1897 ret = cb(node, data);
1898 if (ret)
1899 return ret;
1900
1901 callchain_cursor_advance(cursor);
1902 }
1903 return 0;
1904}
1905
1906/*
1907 * This function merges earlier samples (@sample_orig) waiting for deferred
1908 * user callchains with the matching callchain record (@sample_callchain)
1909 * which is delivered now. The @sample_orig->callchain should be released
1910 * after use if ->deferred_callchain is set.
1911 */
1912int sample__merge_deferred_callchain(struct perf_sample *sample_orig,
1913 struct perf_sample *sample_callchain)
1914{
1915 u64 nr_orig = sample_orig->callchain->nr - 1;
1916 u64 nr_deferred = sample_callchain->callchain->nr;
1917 struct ip_callchain *callchain;
1918
1919 if (sample_orig->merged_callchain) {
1920 /* Already merged. */
1921 return -EINVAL;
1922 }
1923
1924 if (sample_orig->callchain->nr < 2) {
1925 sample_orig->deferred_callchain = false;
1926 return -EINVAL;
1927 }
1928
1929 callchain = calloc(1 + nr_orig + nr_deferred, sizeof(u64));
1930 if (callchain == NULL)
1931 return -ENOMEM;
1932
1933 callchain->nr = nr_orig + nr_deferred;
1934 /* copy original including PERF_CONTEXT_USER_DEFERRED (but the cookie) */
1935 memcpy(callchain->ips, sample_orig->callchain->ips, nr_orig * sizeof(u64));
1936 /* copy deferred user callchains */
1937 memcpy(&callchain->ips[nr_orig], sample_callchain->callchain->ips,
1938 nr_deferred * sizeof(u64));
1939
1940 sample_orig->merged_callchain = true;
1941 sample_orig->callchain = callchain;
1942 return 0;
1943}