Linux Perf
callchain.c
Go to the documentation of this file.
1 // SPDX-License-Identifier: GPL-2.0
2 /*
3  * Copyright (C) 2009-2011, Frederic Weisbecker <fweisbec@gmail.com>
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 
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 
38 };
39 
40 /*
41  * Are there any events usind DWARF callchains?
42  *
43  * I.e.
44  *
45  * -e cycles/call-graph=dwarf/
46  */
48 
49 struct callchain_param callchain_param_default = {
51 };
52 
54 
55 int parse_callchain_record_opt(const char *arg, struct callchain_param *param)
56 {
57  return parse_callchain_record(arg, param);
58 }
59 
60 static 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 
81 static 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 
96 static 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 
117 static 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 
134 static 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 
160 static 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  /* parsing ok - move on to the next */
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  /* assume that number followed by 'dwarf' is stack size */
195  if (callchain_param.record_mode == CALLCHAIN_DWARF)
196  try_stack_size = true;
197 
198  record_opt_set = true;
199  goto next;
200  }
201 
202 try_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  /* try to get the min percent */
212  callchain_param.min_percent = strtod(tok, &endptr);
213  if (tok == endptr)
214  return -1;
215  minpcnt_set = true;
216  } else {
217  /* try print limit at last */
218  callchain_param.print_limit = strtoul(tok, &endptr, 0);
219  if (tok == endptr)
220  return -1;
221  }
222 next:
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 
233 int parse_callchain_report_opt(const char *arg)
234 {
235  return __parse_callchain_report_opt(arg, false);
236 }
237 
238 int parse_callchain_top_opt(const char *arg)
239 {
240  return __parse_callchain_report_opt(arg, true);
241 }
242 
243 int 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  /* We need buffer that we know we can write to. */
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  /* Framepointer style */
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  /* Dwarf style */
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 
306 int 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 
364 static void
365 rb_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: /* Falldown */
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 
405 static void
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  * Once we get every callchains from the stream, we can now
426  * sort them by hit
427  */
428 static void
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 
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,
453  }
454 }
455 
456 static void
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 
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,
483  }
484 }
485 
486 static void
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 
494 int 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  * Create a child for a parent. If inherit_children, then the new child
516  * will become the new parent of it's parent children
517  */
518 static struct callchain_node *
519 create_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  /* make it the first child */
547  rb_link_node(&new->rb_node_in, NULL, &parent->rb_root_in.rb_node);
548  rb_insert_color(&new->rb_node_in, &parent->rb_root_in);
549  }
550 
551  return new;
552 }
553 
554 
555 /*
556  * Fill the node with callchain values
557  */
558 static int
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  * branch_from is set with value somewhere else
588  * to imply it's "to" of a branch.
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 
599  &cursor_node->branch_flags,
600  cursor_node->branch_from,
601  cursor_node->ip);
602  } else {
603  /*
604  * It's "from" of a branch
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 
622 static struct callchain_node *
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 
657 };
658 
659 static 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  * We need to always use relative addresses because we're aggregating
682  * callchains from multiple threads, i.e. different address spaces, so
683  * comparing absolute addresses make no sense as a symbol in a DSO may end up
684  * in a different address when used in a different binary or even the same
685  * binary but with some sort of address randomization technique, thus we need
686  * to compare just relative addresses. -acme
687  */
688 static 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 
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  /* otherwise fall-back to symbol-based comparison below */
714  __fallthrough;
715  case CCKEY_FUNCTION:
716  if (node->sym && cnode->ms.sym) {
717  /*
718  * Compare inlined frames based on their symbol name
719  * because different inlined frames will have the same
720  * symbol start. Otherwise do a faster comparison based
721  * on the symbol start address.
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  /* otherwise fall-back to IP-based comparison below */
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  * It's "to" of a branch
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 
758  &node->branch_flags,
759  node->branch_from,
760  node->ip);
761  } else {
762  /*
763  * It's "from" of a branch
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  * Split the parent in two parts (a new child is created) and
777  * give a part of its callchain to the created child.
778  * Then create another child to host the given callchain of new branch
779  */
780 static int
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  /* split */
791  new = create_child(parent, true);
792  if (new == NULL)
793  return -1;
794 
795  /* split the callchain and move a part to the new child */
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  /* split the hits */
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  /* create a new child for the new branch if any */
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  * This is second child since we moved parent's children
832  * to new (first) child above.
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 
853 static enum match_result
855  struct callchain_cursor *cursor,
856  u64 period);
857 
858 static int
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  /* lookup in childrens */
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  /* If at least first entry matches, rely to children */
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  /* nothing in children, add to the current node */
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 
899 inc_children_hit:
900  root->children_hit += period;
901  root->children_count++;
902  return 0;
903 }
904 
905 static enum match_result
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  * Lookup in the current node
918  * If we have a symbol, then compare the start to match
919  * anywhere inside a function, unless function
920  * mode is disabled.
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  /* matches not, relay no the parent */
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  /* we match only a part of the node. Split it and add the new chain */
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  /* we match 100% of the path, increment the hit */
956  if (matches == root->val_nr && cursor->pos == cursor->nr) {
957  root->hit += period;
958  root->count++;
959  return MATCH_EQ;
960  }
961 
962  /* We match the node and still have a part remaining */
963  if (append_chain_children(root, cursor, period) < 0)
964  return MATCH_ERROR;
965 
966  return MATCH_EQ;
967 }
968 
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 
987 static int
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 
1033  struct callchain_root *dst, struct callchain_root *src)
1034 {
1035  return merge_chain_branch(cursor, &dst->node, &src->node);
1036 }
1037 
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 
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 
1085  return thread__resolve_callchain(al->thread, cursor, evsel, sample,
1086  parent, al, max_stack);
1087  }
1088  return 0;
1089 }
1090 
1092 {
1093  if ((!symbol_conf.use_callchain || sample->callchain == NULL) &&
1095  return 0;
1096  return callchain_append(he->callchain, &callchain_cursor, sample->period);
1097 }
1098 
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 
1135 out:
1136  return 1;
1137 }
1138 
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 
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 
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 
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 
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 
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 
1288  branch_count,
1289  predicted_count,
1290  abort_count,
1291  cycles_count);
1292 }
1293 
1294 static 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 
1303 static 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 
1316 static 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 
1345 static 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 
1376 static 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 
1401 static 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 
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 
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 
1468 void free_callchain(struct callchain_root *root)
1469 {
1471  return;
1472 
1473  free_callchain_node(&root->node);
1474 }
1475 
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 
1497 {
1499  return;
1500 
1501  decay_callchain_node(&root->node);
1502 }
1503 
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 
1535 out:
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 
1545  struct callchain_cursor *src)
1546 {
1547  int rc = 0;
1548 
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 
1568  }
1569 
1570  return rc;
1571 }
static int merge_chain_branch(struct callchain_cursor *cursor, struct callchain_node *dst, struct callchain_node *src)
Definition: callchain.c:988
static struct callchain_node * create_child(struct callchain_node *parent, bool inherit_children)
Definition: callchain.c:519
struct list_head val
Definition: callchain.h:57
int callchain_node__fprintf_value(struct callchain_node *node, FILE *fp, u64 total)
Definition: callchain.c:1197
unsigned int val_nr
Definition: callchain.h:63
int branch_type_str(struct branch_type_stat *st, char *bf, int size)
Definition: branch.c:115
struct list_head list
Definition: callchain.h:128
const char * srcline
Definition: callchain.h:141
Definition: mem2node.c:7
int value
Definition: python.c:1143
void decay_callchain(struct callchain_root *root)
Definition: callchain.c:1496
struct rb_node rb_node
Definition: callchain.h:60
static enum match_result match_chain(struct callchain_cursor_node *node, struct callchain_list *cnode)
Definition: callchain.c:703
int callchain_cursor__copy(struct callchain_cursor *dst, struct callchain_cursor *src)
Definition: callchain.c:1544
static LIST_HEAD(page_alloc_sort_input)
bool cumulate_callchain
Definition: symbol.h:93
match_result
Definition: callchain.c:652
size_t size
Definition: evsel.c:60
static bool machine__is_host(struct machine *machine)
Definition: machine.h:187
#define CALLCHAIN_PARAM_DEFAULT
Definition: callchain.c:29
static void callchain_cursor_reset(struct callchain_cursor *cursor)
Definition: callchain.h:194
static int __parse_callchain_report_opt(const char *arg, bool allow_record_opt)
Definition: callchain.c:161
struct symbol * sym
Definition: symbol.h:181
static void __sort_chain_graph_abs(struct callchain_node *node, u64 min_hit)
Definition: callchain.c:436
struct map * map
Definition: symbol.h:180
int fill_callchain_info(struct addr_location *al, struct callchain_cursor_node *node, bool hide_unresolved)
Definition: callchain.c:1099
static void sort_chain_graph_rel(struct rb_root *rb_root, struct callchain_root *chain_root, u64 min_hit __maybe_unused, struct callchain_param *param)
Definition: callchain.c:487
struct ip_callchain * callchain
Definition: event.h:211
int int err
Definition: 5sec.c:44
char * callchain_list__sym_name(struct callchain_list *cl, char *bf, size_t bfsize, bool show_dso)
Definition: callchain.c:1139
struct symbol * sym
Definition: callchain.h:140
struct rb_root root
Definition: block-range.c:6
static int count_pri64_printf(int idx, const char *str, u64 value, char *bf, int bfsize)
Definition: callchain.c:1294
static enum match_result append_chain(struct callchain_node *root, struct callchain_cursor *cursor, u64 period)
Definition: callchain.c:906
enum perf_call_graph_mode record_mode
Definition: callchain.h:96
enum chain_value value
Definition: callchain.h:107
static void callchain_counts_value(struct callchain_node *node, u64 *branch_count, u64 *predicted_count, u64 *abort_count, u64 *cycles_count)
Definition: callchain.c:1223
struct rb_root rb_root_in
Definition: callchain.h:61
struct callchain_cursor_node * next
Definition: callchain.h:147
u64 cycles
Definition: event.h:145
struct branch_type_stat brtype_stat
Definition: callchain.h:126
static void callchain_cursor_commit(struct callchain_cursor *cursor)
Definition: callchain.h:212
static enum match_result match_chain_strings(const char *left, const char *right)
Definition: callchain.c:659
struct callchain_node node
Definition: callchain.h:72
static unsigned callchain_cumul_counts(struct callchain_node *node)
Definition: callchain.h:177
u64 predicted_count
Definition: callchain.h:121
static enum match_result match_chain_dso_addresses(struct map *left_map, u64 left_ip, struct map *right_map, u64 right_ip)
Definition: callchain.c:688
#define pr_err(fmt,...)
Definition: json.h:21
struct callchain_root callchain[0]
Definition: sort.h:151
static int counts_str_build(char *bf, int bfsize, u64 branch_count, u64 predicted_count, u64 abort_count, u64 cycles_count, u64 iter_count, u64 iter_cycles, struct branch_type_stat *brtype_stat)
Definition: callchain.c:1376
int callchain_list_counts__printf_value(struct callchain_list *clist, FILE *fp, char *bf, int bfsize)
Definition: callchain.c:1419
struct machine * machine
Definition: symbol.h:208
Definition: sort.h:89
struct callchain_param callchain_param_default
Definition: callchain.c:49
int sample__resolve_callchain(struct perf_sample *sample, struct callchain_cursor *cursor, struct symbol **parent, struct perf_evsel *evsel, struct addr_location *al, int max_stack)
Definition: callchain.c:1075
bool has_children
Definition: callchain.h:118
bool branch_callstack
Definition: callchain.h:106
enum chain_mode mode
Definition: callchain.h:98
void * malloc(YYSIZE_T)
unsigned int count
Definition: callchain.h:64
struct map * map
Definition: symbol.h:210
const char * name
char level
Definition: symbol.h:214
bool dwarf_callchain_users
Definition: callchain.c:47
struct map_groups * groups
Definition: map.h:46
bool perf_guest
Definition: util.c:81
static int count_float_printf(int idx, const char *str, float value, char *bf, int bfsize, float threshold)
Definition: callchain.c:1303
int parse_callchain_report_opt(const char *arg)
Definition: callchain.c:233
u64 start
Definition: symbol.h:57
int parse_callchain_record(const char *arg, struct callchain_param *param)
Definition: callchain.c:243
static void callchain_cursor_advance(struct callchain_cursor *cursor)
Definition: callchain.h:228
struct map_groups kmaps
Definition: machine.h:51
#define map__zput(map)
Definition: map.h:167
static u64 decay_callchain_node(struct callchain_node *node)
Definition: callchain.c:1476
struct dso * dso
Definition: map.h:45
struct callchain_node * parent
Definition: callchain.h:56
static void sort_chain_graph_abs(struct rb_root *rb_root, struct callchain_root *chain_root, u64 min_hit, struct callchain_param *param __maybe_unused)
Definition: callchain.c:457
sort_chain_func_t sort
Definition: callchain.h:102
void free_callchain(struct callchain_root *root)
Definition: callchain.c:1468
u64 period
Definition: event.h:198
static int branch_from_str(char *bf, int bfsize, u64 branch_count, u64 cycles_count, u64 iter_count, u64 iter_cycles)
Definition: callchain.c:1345
u64 predicted
Definition: event.h:142
static int str(yyscan_t scanner, int token)
int percent_color_fprintf(FILE *fp, const char *fmt, double percent)
Definition: color.c:180
char name[0]
Definition: symbol.h:66
u64 children_hit
Definition: callchain.h:67
static void __sort_chain_flat(struct rb_root *rb_root, struct callchain_node *node, u64 min_hit)
Definition: callchain.c:406
int callchain_merge(struct callchain_cursor *cursor, struct callchain_root *dst, struct callchain_root *src)
Definition: callchain.c:1032
struct symbol * sym
Definition: symbol.h:211
struct rb_node rb_node_in
Definition: callchain.h:59
int callchain_append(struct callchain_root *root, struct callchain_cursor *cursor, u64 period)
Definition: callchain.c:969
#define new
Definition: util-cxx.h:20
Definition: dso.h:138
unsigned int children_count
Definition: callchain.h:65
int parent
Definition: hist.h:275
int callchain_cursor_append(struct callchain_cursor *cursor, u64 ip, struct map *map, struct symbol *sym, bool branch, struct branch_flags *flags, int nr_loop_iter, u64 iter_cycles, u64 branch_from, const char *srcline)
Definition: callchain.c:1038
struct map * map
Definition: callchain.h:139
x86 movsq based memcpy() in arch/x86/lib/memcpy_64.S") MEMCPY_FN(memcpy_erms
struct thread * thread
Definition: symbol.h:209
chain_mode
Definition: callchain.h:42
static int append_chain_children(struct callchain_node *root, struct callchain_cursor *cursor, u64 period)
Definition: callchain.c:859
double min_percent
Definition: callchain.h:101
const char * srcline
Definition: callchain.h:127
static struct map * map__get(struct map *map)
Definition: map.h:152
void branch_type_count(struct branch_type_stat *st, struct branch_flags *flags, u64 from, u64 to)
Definition: branch.c:19
static int parse_callchain_value(const char *value)
Definition: callchain.c:117
static int callchain_counts_printf(FILE *fp, char *bf, int bfsize, u64 branch_count, u64 predicted_count, u64 abort_count, u64 cycles_count, u64 iter_count, u64 iter_cycles, struct branch_type_stat *brtype_stat)
Definition: callchain.c:1401
static int get_stack_size(const char *str, unsigned long *_size)
Definition: callchain.c:134
static void free_callchain_node(struct callchain_node *node)
Definition: callchain.c:1439
u64 start
Definition: hists_common.c:25
static void __sort_chain_graph_rel(struct callchain_node *node, double min_percent)
Definition: callchain.c:464
Definition: jevents.c:228
bool use_callchain
Definition: symbol.h:93
struct branch_flags branch_flags
Definition: callchain.h:143
static int split_add_child(struct callchain_node *parent, struct callchain_cursor *cursor, struct callchain_list *to_split, u64 idx_parents, u64 idx_local, u64 period)
Definition: callchain.c:781
static int parse_callchain_order(const char *value)
Definition: callchain.c:81
enum chain_order order
Definition: callchain.h:103
static int sym(yyscan_t scanner, int type, int config)
u32 flags
bool show_branchflag_count
Definition: symbol.h:93
static int parse_callchain_sort_key(const char *value)
Definition: callchain.c:96
int hist_entry__append_callchain(struct hist_entry *he, struct perf_sample *sample)
Definition: callchain.c:1091
static double percent(int st, int tot)
Definition: builtin-c2c.c:899
void free(void *)
struct rb_root rb_root
Definition: callchain.h:62
static int fill_node(struct callchain_node *node, struct callchain_cursor *cursor)
Definition: callchain.c:559
struct callchain_cursor_node ** last
Definition: callchain.h:153
static int callchain_node_branch_counts_cumul(struct callchain_node *node, u64 *branch_count, u64 *predicted_count, u64 *abort_count, u64 *cycles_count)
Definition: callchain.c:1244
bool branch_to
Definition: branch.h:8
Definition: symbol.h:55
int thread__resolve_callchain(struct thread *thread, struct callchain_cursor *cursor, struct perf_evsel *evsel, struct perf_sample *sample, struct symbol **parent, struct addr_location *root_al, int max_stack)
Definition: machine.c:2308
int perf_callchain_config(const char *var, const char *value)
Definition: callchain.c:306
int callchain_node__make_parent_list(struct callchain_node *node)
Definition: callchain.c:1504
struct map_symbol ms
Definition: callchain.h:115
u8 inlined
Definition: symbol.h:64
int callchain_branch_counts(struct callchain_root *root, u64 *branch_count, u64 *predicted_count, u64 *abort_count, u64 *cycles_count)
Definition: callchain.c:1271
#define pr_warning(fmt,...)
Definition: debug.h:25
static int branch_to_str(char *bf, int bfsize, u64 branch_count, u64 predicted_count, u64 abort_count, struct branch_type_stat *brtype_stat)
Definition: callchain.c:1316
int parse_callchain_record_opt(const char *arg, struct callchain_param *param)
Definition: callchain.c:55
static u64 callchain_cumul_hits(struct callchain_node *node)
Definition: callchain.h:172
static void rb_insert_callchain(struct rb_root *root, struct callchain_node *chain, enum chain_mode mode)
Definition: callchain.c:365
const char * srcline
Definition: symbol.h:212
static void sort_chain_flat(struct rb_root *rb_root, struct callchain_root *root, u64 min_hit, struct callchain_param *param __maybe_unused)
Definition: callchain.c:429
int callchain_register_param(struct callchain_param *param)
Definition: callchain.c:494
struct list_head parent_val
Definition: callchain.h:58
const char * short_name
Definition: dso.h:172
static int parse_callchain_mode(const char *value)
Definition: callchain.c:60
u64 abort
Definition: event.h:144
static struct callchain_node * add_child(struct callchain_node *parent, struct callchain_cursor *cursor, u64 period)
Definition: callchain.c:623
enum chain_key key
Definition: callchain.h:105
int parse_callchain_top_opt(const char *arg)
Definition: callchain.c:238
static struct callchain_cursor_node * callchain_cursor_current(struct callchain_cursor *cursor)
Definition: callchain.h:220
char * callchain_node__scnprintf_value(struct callchain_node *node, char *bf, size_t bfsize, u64 total)
Definition: callchain.c:1168
void static void * zalloc(size_t size)
Definition: util.h:20