~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/tools/perf/util/callchain.c

Version: ~ [ linux-5.8-rc4 ] ~ [ linux-5.7.7 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.50 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.131 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.187 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.229 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.229 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.140 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.85 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  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 
 36 struct callchain_param callchain_param = {
 37         CALLCHAIN_PARAM_DEFAULT
 38 };
 39 
 40 /*
 41  * Are there any events usind DWARF callchains?
 42  *
 43  * I.e.
 44  *
 45  * -e cycles/call-graph=dwarf/
 46  */
 47 bool dwarf_callchain_users;
 48 
 49 struct callchain_param callchain_param_default = {
 50         CALLCHAIN_PARAM_DEFAULT
 51 };
 52 
 53 __thread struct callchain_cursor callchain_cursor;
 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
406 __sort_chain_flat(struct rb_root *rb_root, struct callchain_node *node,
407                   u64 min_hit)
408 {
409         struct rb_node *n;
410         struct callchain_node *child;
411 
412         n = rb_first(&node->rb_root_in);
413         while (n) {
414                 child = rb_entry(n, struct callchain_node, rb_node_in);
415                 n = rb_next(n);
416 
417                 __sort_chain_flat(rb_root, child, min_hit);
418         }
419 
420         if (node->hit && node->hit >= min_hit)
421                 rb_insert_callchain(rb_root, node, CHAIN_FLAT);
422 }
423 
424 /*
425  * Once we get every callchains from the stream, we can now
426  * sort them by hit
427  */
428 static void
429 sort_chain_flat(struct rb_root *rb_root, struct callchain_root *root,
430                 u64 min_hit, struct callchain_param *param __maybe_unused)
431 {
432         *rb_root = RB_ROOT;
433         __sort_chain_flat(rb_root, &root->node, min_hit);
434 }
435 
436 static void __sort_chain_graph_abs(struct callchain_node *node,
437                                    u64 min_hit)
438 {
439         struct rb_node *n;
440         struct callchain_node *child;
441 
442         node->rb_root = RB_ROOT;
443         n = rb_first(&node->rb_root_in);
444 
445         while (n) {
446                 child = rb_entry(n, struct callchain_node, rb_node_in);
447                 n = rb_next(n);
448 
449                 __sort_chain_graph_abs(child, min_hit);
450                 if (callchain_cumul_hits(child) >= min_hit)
451                         rb_insert_callchain(&node->rb_root, child,
452                                             CHAIN_GRAPH_ABS);
453         }
454 }
455 
456 static void
457 sort_chain_graph_abs(struct rb_root *rb_root, struct callchain_root *chain_root,
458                      u64 min_hit, struct callchain_param *param __maybe_unused)
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 
464 static void __sort_chain_graph_rel(struct callchain_node *node,
465                                    double min_percent)
466 {
467         struct rb_node *n;
468         struct callchain_node *child;
469         u64 min_hit;
470 
471         node->rb_root = RB_ROOT;
472         min_hit = ceil(node->children_hit * min_percent);
473 
474         n = rb_first(&node->rb_root_in);
475         while (n) {
476                 child = rb_entry(n, struct callchain_node, rb_node_in);
477                 n = rb_next(n);
478 
479                 __sort_chain_graph_rel(child, min_percent);
480                 if (callchain_cumul_hits(child) >= min_hit)
481                         rb_insert_callchain(&node->rb_root, child,
482                                             CHAIN_GRAPH_REL);
483         }
484 }
485 
486 static void
487 sort_chain_graph_rel(struct rb_root *rb_root, struct callchain_root *chain_root,
488                      u64 min_hit __maybe_unused, struct callchain_param *param)
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
559 fill_node(struct callchain_node *node, struct callchain_cursor *cursor)
560 {
561         struct callchain_cursor_node *cursor_node;
562 
563         node->val_nr = cursor->nr - cursor->pos;
564         if (!node->val_nr)
565                 pr_warning("Warning: empty node in callchain tree\n");
566 
567         cursor_node = callchain_cursor_current(cursor);
568 
569         while (cursor_node) {
570                 struct callchain_list *call;
571 
572                 call = zalloc(sizeof(*call));
573                 if (!call) {
574                         perror("not enough memory for the code path tree");
575                         return -1;
576                 }
577                 call->ip = cursor_node->ip;
578                 call->ms.sym = cursor_node->sym;
579                 call->ms.map = map__get(cursor_node->map);
580                 call->srcline = cursor_node->srcline;
581 
582                 if (cursor_node->branch) {
583                         call->branch_count = 1;
584 
585                         if (cursor_node->branch_from) {
586                                 /*
587                                  * 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 
598                                 branch_type_count(&call->brtype_stat,
599                                                   &cursor_node->branch_flags,
600                                                   cursor_node->branch_from,
601                                                   cursor_node->ip);
602                         } else {
603                                 /*
604                                  * 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 *
623 add_child(struct callchain_node *parent,
624           struct callchain_cursor *cursor,
625           u64 period)
626 {
627         struct callchain_node *new;
628 
629         new = create_child(parent, false);
630         if (new == NULL)
631                 return NULL;
632 
633         if (fill_node(new, cursor) < 0) {
634                 struct callchain_list *call, *tmp;
635 
636                 list_for_each_entry_safe(call, tmp, &new->val, list) {
637                         list_del(&call->list);
638                         map__zput(call->ms.map);
639                         free(call);
640                 }
641                 free(new);
642                 return NULL;
643         }
644 
645         new->children_hit = 0;
646         new->hit = period;
647         new->children_count = 0;
648         new->count = 1;
649         return new;
650 }
651 
652 enum match_result {
653         MATCH_ERROR  = -1,
654         MATCH_EQ,
655         MATCH_LT,
656         MATCH_GT,
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 
703 static enum match_result match_chain(struct callchain_cursor_node *node,
704                                      struct callchain_list *cnode)
705 {
706         enum match_result match = MATCH_ERROR;
707 
708         switch (callchain_param.key) {
709         case CCKEY_SRCLINE:
710                 match = match_chain_strings(cnode->srcline, node->srcline);
711                 if (match != MATCH_ERROR)
712                         break;
713                 /* 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 
757                         branch_type_count(&cnode->brtype_stat,
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
781 split_add_child(struct callchain_node *parent,
782                 struct callchain_cursor *cursor,
783                 struct callchain_list *to_split,
784                 u64 idx_parents, u64 idx_local, u64 period)
785 {
786         struct callchain_node *new;
787         struct list_head *old_tail;
788         unsigned int idx_total = idx_parents + idx_local;
789 
790         /* 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
854 append_chain(struct callchain_node *root,
855              struct callchain_cursor *cursor,
856              u64 period);
857 
858 static int
859 append_chain_children(struct callchain_node *root,
860                       struct callchain_cursor *cursor,
861                       u64 period)
862 {
863         struct callchain_node *rnode;
864         struct callchain_cursor_node *node;
865         struct rb_node **p = &root->rb_root_in.rb_node;
866         struct rb_node *parent = NULL;
867 
868         node = callchain_cursor_current(cursor);
869         if (!node)
870                 return -1;
871 
872         /* 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
906 append_chain(struct callchain_node *root,
907              struct callchain_cursor *cursor,
908              u64 period)
909 {
910         struct callchain_list *cnode;
911         u64 start = cursor->pos;
912         bool found = false;
913         u64 matches;
914         enum match_result cmp = MATCH_ERROR;
915 
916         /*
917          * 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 
969 int callchain_append(struct callchain_root *root,
970                      struct callchain_cursor *cursor,
971                      u64 period)
972 {
973         if (!cursor->nr)
974                 return 0;
975 
976         callchain_cursor_commit(cursor);
977 
978         if (append_chain_children(&root->node, cursor, period) < 0)
979                 return -1;
980 
981         if (cursor->nr > root->max_depth)
982                 root->max_depth = cursor->nr;
983 
984         return 0;
985 }
986 
987 static int
988 merge_chain_branch(struct callchain_cursor *cursor,
989                    struct callchain_node *dst, struct callchain_node *src)
990 {
991         struct callchain_cursor_node **old_last = cursor->last;
992         struct callchain_node *child;
993         struct callchain_list *list, *next_list;
994         struct rb_node *n;
995         int old_pos = cursor->nr;
996         int err = 0;
997 
998         list_for_each_entry_safe(list, next_list, &src->val, list) {
999                 callchain_cursor_append(cursor, list->ip,
1000                                         list->ms.map, list->ms.sym,
1001                                         false, NULL, 0, 0, 0, list->srcline);
1002                 list_del(&list->list);
1003                 map__zput(list->ms.map);
1004                 free(list);
1005         }
1006 
1007         if (src->hit) {
1008                 callchain_cursor_commit(cursor);
1009                 if (append_chain_children(dst, cursor, src->hit) < 0)
1010                         return -1;
1011         }
1012 
1013         n = rb_first(&src->rb_root_in);
1014         while (n) {
1015                 child = container_of(n, struct callchain_node, rb_node_in);
1016                 n = rb_next(n);
1017                 rb_erase(&child->rb_node_in, &src->rb_root_in);
1018 
1019                 err = merge_chain_branch(cursor, dst, child);
1020                 if (err)
1021                         break;
1022 
1023                 free(child);
1024         }
1025 
1026         cursor->nr = old_pos;
1027         cursor->last = old_last;
1028 
1029         return err;
1030 }
1031 
1032 int callchain_merge(struct callchain_cursor *cursor,
1033                     struct callchain_root *dst, struct callchain_root *src)
1034 {
1035         return merge_chain_branch(cursor, &dst->node, &src->node);
1036 }
1037 
1038 int callchain_cursor_append(struct callchain_cursor *cursor,
1039                             u64 ip, struct map *map, struct symbol *sym,
1040                             bool branch, struct branch_flags *flags,
1041                             int nr_loop_iter, u64 iter_cycles, u64 branch_from,
1042                             const char *srcline)
1043 {
1044         struct callchain_cursor_node *node = *cursor->last;
1045 
1046         if (!node) {
1047                 node = calloc(1, sizeof(*node));
1048                 if (!node)
1049                         return -ENOMEM;
1050 
1051                 *cursor->last = node;
1052         }
1053 
1054         node->ip = ip;
1055         map__zput(node->map);
1056         node->map = map__get(map);
1057         node->sym = sym;
1058         node->branch = branch;
1059         node->nr_loop_iter = nr_loop_iter;
1060         node->iter_cycles = iter_cycles;
1061         node->srcline = srcline;
1062 
1063         if (flags)
1064                 memcpy(&node->branch_flags, flags,
1065                         sizeof(struct branch_flags));
1066 
1067         node->branch_from = branch_from;
1068         cursor->nr++;
1069 
1070         cursor->last = &node->next;
1071 
1072         return 0;
1073 }
1074 
1075 int sample__resolve_callchain(struct perf_sample *sample,
1076                               struct callchain_cursor *cursor, struct symbol **parent,
1077                               struct perf_evsel *evsel, struct addr_location *al,
1078                               int max_stack)
1079 {
1080         if (sample->callchain == NULL && !symbol_conf.show_branchflag_count)
1081                 return 0;
1082 
1083         if (symbol_conf.use_callchain || symbol_conf.cumulate_callchain ||
1084             perf_hpp_list.parent || symbol_conf.show_branchflag_count) {
1085                 return thread__resolve_callchain(al->thread, cursor, evsel, sample,
1086                                                  parent, al, max_stack);
1087         }
1088         return 0;
1089 }
1090 
1091 int hist_entry__append_callchain(struct hist_entry *he, struct perf_sample *sample)
1092 {
1093         if ((!symbol_conf.use_callchain || sample->callchain == NULL) &&
1094                 !symbol_conf.show_branchflag_count)
1095                 return 0;
1096         return callchain_append(he->callchain, &callchain_cursor, sample->period);
1097 }
1098 
1099 int fill_callchain_info(struct addr_location *al, struct callchain_cursor_node *node,
1100                         bool hide_unresolved)
1101 {
1102         al->map = node->map;
1103         al->sym = node->sym;
1104         al->srcline = node->srcline;
1105         al->addr = node->ip;
1106 
1107         if (al->sym == NULL) {
1108                 if (hide_unresolved)
1109                         return 0;
1110                 if (al->map == NULL)
1111                         goto out;
1112         }
1113 
1114         if (al->map->groups == &al->machine->kmaps) {
1115                 if (machine__is_host(al->machine)) {
1116                         al->cpumode = PERF_RECORD_MISC_KERNEL;
1117                         al->level = 'k';
1118                 } else {
1119                         al->cpumode = PERF_RECORD_MISC_GUEST_KERNEL;
1120                         al->level = 'g';
1121                 }
1122         } else {
1123                 if (machine__is_host(al->machine)) {
1124                         al->cpumode = PERF_RECORD_MISC_USER;
1125                         al->level = '.';
1126                 } else if (perf_guest) {
1127                         al->cpumode = PERF_RECORD_MISC_GUEST_USER;
1128                         al->level = 'u';
1129                 } else {
1130                         al->cpumode = PERF_RECORD_MISC_HYPERVISOR;
1131                         al->level = 'H';
1132                 }
1133         }
1134 
1135 out:
1136         return 1;
1137 }
1138 
1139 char *callchain_list__sym_name(struct callchain_list *cl,
1140                                char *bf, size_t bfsize, bool show_dso)
1141 {
1142         bool show_addr = callchain_param.key == CCKEY_ADDRESS;
1143         bool show_srcline = show_addr || callchain_param.key == CCKEY_SRCLINE;
1144         int printed;
1145 
1146         if (cl->ms.sym) {
1147                 const char *inlined = cl->ms.sym->inlined ? " (inlined)" : "";
1148 
1149                 if (show_srcline && cl->srcline)
1150                         printed = scnprintf(bf, bfsize, "%s %s%s",
1151                                             cl->ms.sym->name, cl->srcline,
1152                                             inlined);
1153                 else
1154                         printed = scnprintf(bf, bfsize, "%s%s",
1155                                             cl->ms.sym->name, inlined);
1156         } else
1157                 printed = scnprintf(bf, bfsize, "%#" PRIx64, cl->ip);
1158 
1159         if (show_dso)
1160                 scnprintf(bf + printed, bfsize - printed, " %s",
1161                           cl->ms.map ?
1162                           cl->ms.map->dso->short_name :
1163                           "unknown");
1164 
1165         return bf;
1166 }
1167 
1168 char *callchain_node__scnprintf_value(struct callchain_node *node,
1169                                       char *bf, size_t bfsize, u64 total)
1170 {
1171         double percent = 0.0;
1172         u64 period = callchain_cumul_hits(node);
1173         unsigned count = callchain_cumul_counts(node);
1174 
1175         if (callchain_param.mode == CHAIN_FOLDED) {
1176                 period = node->hit;
1177                 count = node->count;
1178         }
1179 
1180         switch (callchain_param.value) {
1181         case CCVAL_PERIOD:
1182                 scnprintf(bf, bfsize, "%"PRIu64, period);
1183                 break;
1184         case CCVAL_COUNT:
1185                 scnprintf(bf, bfsize, "%u", count);
1186                 break;
1187         case CCVAL_PERCENT:
1188         default:
1189                 if (total)
1190                         percent = period * 100.0 / total;
1191                 scnprintf(bf, bfsize, "%.2f%%", percent);
1192                 break;
1193         }
1194         return bf;
1195 }
1196 
1197 int callchain_node__fprintf_value(struct callchain_node *node,
1198                                  FILE *fp, u64 total)
1199 {
1200         double percent = 0.0;
1201         u64 period = callchain_cumul_hits(node);
1202         unsigned count = callchain_cumul_counts(node);
1203 
1204         if (callchain_param.mode == CHAIN_FOLDED) {
1205                 period = node->hit;
1206                 count = node->count;
1207         }
1208 
1209         switch (callchain_param.value) {
1210         case CCVAL_PERIOD:
1211                 return fprintf(fp, "%"PRIu64, period);
1212         case CCVAL_COUNT:
1213                 return fprintf(fp, "%u", count);
1214         case CCVAL_PERCENT:
1215         default:
1216                 if (total)
1217                         percent = period * 100.0 / total;
1218                 return percent_color_fprintf(fp, "%.2f%%", percent);
1219         }
1220         return 0;
1221 }
1222 
1223 static void callchain_counts_value(struct callchain_node *node,
1224                                    u64 *branch_count, u64 *predicted_count,
1225                                    u64 *abort_count, u64 *cycles_count)
1226 {
1227         struct callchain_list *clist;
1228 
1229         list_for_each_entry(clist, &node->val, list) {
1230                 if (branch_count)
1231                         *branch_count += clist->branch_count;
1232 
1233                 if (predicted_count)
1234                         *predicted_count += clist->predicted_count;
1235 
1236                 if (abort_count)
1237                         *abort_count += clist->abort_count;
1238 
1239                 if (cycles_count)
1240                         *cycles_count += clist->cycles_count;
1241         }
1242 }
1243 
1244 static int callchain_node_branch_counts_cumul(struct callchain_node *node,
1245                                               u64 *branch_count,
1246                                               u64 *predicted_count,
1247                                               u64 *abort_count,
1248                                               u64 *cycles_count)
1249 {
1250         struct callchain_node *child;
1251         struct rb_node *n;
1252 
1253         n = rb_first(&node->rb_root_in);
1254         while (n) {
1255                 child = rb_entry(n, struct callchain_node, rb_node_in);
1256                 n = rb_next(n);
1257 
1258                 callchain_node_branch_counts_cumul(child, branch_count,
1259                                                    predicted_count,
1260                                                    abort_count,
1261                                                    cycles_count);
1262 
1263                 callchain_counts_value(child, branch_count,
1264                                        predicted_count, abort_count,
1265                                        cycles_count);
1266         }
1267 
1268         return 0;
1269 }
1270 
1271 int callchain_branch_counts(struct callchain_root *root,
1272                             u64 *branch_count, u64 *predicted_count,
1273                             u64 *abort_count, u64 *cycles_count)
1274 {
1275         if (branch_count)
1276                 *branch_count = 0;
1277 
1278         if (predicted_count)
1279                 *predicted_count = 0;
1280 
1281         if (abort_count)
1282                 *abort_count = 0;
1283 
1284         if (cycles_count)
1285                 *cycles_count = 0;
1286 
1287         return callchain_node_branch_counts_cumul(&root->node,
1288                                                   branch_count,
1289                                                   predicted_count,
1290                                                   abort_count,
1291                                                   cycles_count);
1292 }
1293 
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 
1419 int callchain_list_counts__printf_value(struct callchain_list *clist,
1420                                         FILE *fp, char *bf, int bfsize)
1421 {
1422         u64 branch_count, predicted_count;
1423         u64 abort_count, cycles_count;
1424         u64 iter_count, iter_cycles;
1425 
1426         branch_count = clist->branch_count;
1427         predicted_count = clist->predicted_count;
1428         abort_count = clist->abort_count;
1429         cycles_count = clist->cycles_count;
1430         iter_count = clist->iter_count;
1431         iter_cycles = clist->iter_cycles;
1432 
1433         return callchain_counts_printf(fp, bf, bfsize, branch_count,
1434                                        predicted_count, abort_count,
1435                                        cycles_count, iter_count, iter_cycles,
1436                                        &clist->brtype_stat);
1437 }
1438 
1439 static void free_callchain_node(struct callchain_node *node)
1440 {
1441         struct callchain_list *list, *tmp;
1442         struct callchain_node *child;
1443         struct rb_node *n;
1444 
1445         list_for_each_entry_safe(list, tmp, &node->parent_val, list) {
1446                 list_del(&list->list);
1447                 map__zput(list->ms.map);
1448                 free(list);
1449         }
1450 
1451         list_for_each_entry_safe(list, tmp, &node->val, list) {
1452                 list_del(&list->list);
1453                 map__zput(list->ms.map);
1454                 free(list);
1455         }
1456 
1457         n = rb_first(&node->rb_root_in);
1458         while (n) {
1459                 child = container_of(n, struct callchain_node, rb_node_in);
1460                 n = rb_next(n);
1461                 rb_erase(&child->rb_node_in, &node->rb_root_in);
1462 
1463                 free_callchain_node(child);
1464                 free(child);
1465         }
1466 }
1467 
1468 void free_callchain(struct callchain_root *root)
1469 {
1470         if (!symbol_conf.use_callchain)
1471                 return;
1472 
1473         free_callchain_node(&root->node);
1474 }
1475 
1476 static u64 decay_callchain_node(struct callchain_node *node)
1477 {
1478         struct callchain_node *child;
1479         struct rb_node *n;
1480         u64 child_hits = 0;
1481 
1482         n = rb_first(&node->rb_root_in);
1483         while (n) {
1484                 child = container_of(n, struct callchain_node, rb_node_in);
1485 
1486                 child_hits += decay_callchain_node(child);
1487                 n = rb_next(n);
1488         }
1489 
1490         node->hit = (node->hit * 7) / 8;
1491         node->children_hit = child_hits;
1492 
1493         return node->hit;
1494 }
1495 
1496 void decay_callchain(struct callchain_root *root)
1497 {
1498         if (!symbol_conf.use_callchain)
1499                 return;
1500 
1501         decay_callchain_node(&root->node);
1502 }
1503 
1504 int callchain_node__make_parent_list(struct callchain_node *node)
1505 {
1506         struct callchain_node *parent = node->parent;
1507         struct callchain_list *chain, *new;
1508         LIST_HEAD(head);
1509 
1510         while (parent) {
1511                 list_for_each_entry_reverse(chain, &parent->val, list) {
1512                         new = malloc(sizeof(*new));
1513                         if (new == NULL)
1514                                 goto out;
1515                         *new = *chain;
1516                         new->has_children = false;
1517                         map__get(new->ms.map);
1518                         list_add_tail(&new->list, &head);
1519                 }
1520                 parent = parent->parent;
1521         }
1522 
1523         list_for_each_entry_safe_reverse(chain, new, &head, list)
1524                 list_move_tail(&chain->list, &node->parent_val);
1525 
1526         if (!list_empty(&node->parent_val)) {
1527                 chain = list_first_entry(&node->parent_val, struct callchain_list, list);
1528                 chain->has_children = rb_prev(&node->rb_node) || rb_next(&node->rb_node);
1529 
1530                 chain = list_first_entry(&node->val, struct callchain_list, list);
1531                 chain->has_children = false;
1532         }
1533         return 0;
1534 
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 
1544 int callchain_cursor__copy(struct callchain_cursor *dst,
1545                            struct callchain_cursor *src)
1546 {
1547         int rc = 0;
1548 
1549         callchain_cursor_reset(dst);
1550         callchain_cursor_commit(src);
1551 
1552         while (true) {
1553                 struct callchain_cursor_node *node;
1554 
1555                 node = callchain_cursor_current(src);
1556                 if (node == NULL)
1557                         break;
1558 
1559                 rc = callchain_cursor_append(dst, node->ip, node->map, node->sym,
1560                                              node->branch, &node->branch_flags,
1561                                              node->nr_loop_iter,
1562                                              node->iter_cycles,
1563                                              node->branch_from, node->srcline);
1564                 if (rc)
1565                         break;
1566 
1567                 callchain_cursor_advance(src);
1568         }
1569 
1570         return rc;
1571 }
1572 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp