Back to home page

OSCL-LXR
 
 

     

0001 // SPDX-License-Identifier: GPL-2.0
0002 /*
0003  * Copyright (C) 2009-2011, Frederic Weisbecker <fweisbec@gmail.com>
0004  *
0005  * Handle the callchains from the stream in an ad-hoc radix tree and then
0006  * sort them in an rbtree.
0007  *
0008  * Using a radix for code path provides a fast retrieval and factorizes
0009  * memory use. Also that lets us use the paths in a hierarchical graph view.
0010  *
0011  */
0012 
0013 #include <inttypes.h>
0014 #include <stdlib.h>
0015 #include <stdio.h>
0016 #include <stdbool.h>
0017 #include <errno.h>
0018 #include <math.h>
0019 #include <linux/string.h>
0020 #include <linux/zalloc.h>
0021 
0022 #include "asm/bug.h"
0023 
0024 #include "debug.h"
0025 #include "dso.h"
0026 #include "event.h"
0027 #include "hist.h"
0028 #include "sort.h"
0029 #include "machine.h"
0030 #include "map.h"
0031 #include "callchain.h"
0032 #include "branch.h"
0033 #include "symbol.h"
0034 #include "util.h"
0035 #include "../perf.h"
0036 
0037 #define CALLCHAIN_PARAM_DEFAULT         \
0038     .mode       = CHAIN_GRAPH_ABS,  \
0039     .min_percent    = 0.5,          \
0040     .order      = ORDER_CALLEE,     \
0041     .key        = CCKEY_FUNCTION,   \
0042     .value      = CCVAL_PERCENT,    \
0043 
0044 struct callchain_param callchain_param = {
0045     CALLCHAIN_PARAM_DEFAULT
0046 };
0047 
0048 /*
0049  * Are there any events usind DWARF callchains?
0050  *
0051  * I.e.
0052  *
0053  * -e cycles/call-graph=dwarf/
0054  */
0055 bool dwarf_callchain_users;
0056 
0057 struct callchain_param callchain_param_default = {
0058     CALLCHAIN_PARAM_DEFAULT
0059 };
0060 
0061 __thread struct callchain_cursor callchain_cursor;
0062 
0063 int parse_callchain_record_opt(const char *arg, struct callchain_param *param)
0064 {
0065     return parse_callchain_record(arg, param);
0066 }
0067 
0068 static int parse_callchain_mode(const char *value)
0069 {
0070     if (!strncmp(value, "graph", strlen(value))) {
0071         callchain_param.mode = CHAIN_GRAPH_ABS;
0072         return 0;
0073     }
0074     if (!strncmp(value, "flat", strlen(value))) {
0075         callchain_param.mode = CHAIN_FLAT;
0076         return 0;
0077     }
0078     if (!strncmp(value, "fractal", strlen(value))) {
0079         callchain_param.mode = CHAIN_GRAPH_REL;
0080         return 0;
0081     }
0082     if (!strncmp(value, "folded", strlen(value))) {
0083         callchain_param.mode = CHAIN_FOLDED;
0084         return 0;
0085     }
0086     return -1;
0087 }
0088 
0089 static int parse_callchain_order(const char *value)
0090 {
0091     if (!strncmp(value, "caller", strlen(value))) {
0092         callchain_param.order = ORDER_CALLER;
0093         callchain_param.order_set = true;
0094         return 0;
0095     }
0096     if (!strncmp(value, "callee", strlen(value))) {
0097         callchain_param.order = ORDER_CALLEE;
0098         callchain_param.order_set = true;
0099         return 0;
0100     }
0101     return -1;
0102 }
0103 
0104 static int parse_callchain_sort_key(const char *value)
0105 {
0106     if (!strncmp(value, "function", strlen(value))) {
0107         callchain_param.key = CCKEY_FUNCTION;
0108         return 0;
0109     }
0110     if (!strncmp(value, "address", strlen(value))) {
0111         callchain_param.key = CCKEY_ADDRESS;
0112         return 0;
0113     }
0114     if (!strncmp(value, "srcline", strlen(value))) {
0115         callchain_param.key = CCKEY_SRCLINE;
0116         return 0;
0117     }
0118     if (!strncmp(value, "branch", strlen(value))) {
0119         callchain_param.branch_callstack = 1;
0120         return 0;
0121     }
0122     return -1;
0123 }
0124 
0125 static int parse_callchain_value(const char *value)
0126 {
0127     if (!strncmp(value, "percent", strlen(value))) {
0128         callchain_param.value = CCVAL_PERCENT;
0129         return 0;
0130     }
0131     if (!strncmp(value, "period", strlen(value))) {
0132         callchain_param.value = CCVAL_PERIOD;
0133         return 0;
0134     }
0135     if (!strncmp(value, "count", strlen(value))) {
0136         callchain_param.value = CCVAL_COUNT;
0137         return 0;
0138     }
0139     return -1;
0140 }
0141 
0142 static int get_stack_size(const char *str, unsigned long *_size)
0143 {
0144     char *endptr;
0145     unsigned long size;
0146     unsigned long max_size = round_down(USHRT_MAX, sizeof(u64));
0147 
0148     size = strtoul(str, &endptr, 0);
0149 
0150     do {
0151         if (*endptr)
0152             break;
0153 
0154         size = round_up(size, sizeof(u64));
0155         if (!size || size > max_size)
0156             break;
0157 
0158         *_size = size;
0159         return 0;
0160 
0161     } while (0);
0162 
0163     pr_err("callchain: Incorrect stack dump size (max %ld): %s\n",
0164            max_size, str);
0165     return -1;
0166 }
0167 
0168 static int
0169 __parse_callchain_report_opt(const char *arg, bool allow_record_opt)
0170 {
0171     char *tok;
0172     char *endptr, *saveptr = NULL;
0173     bool minpcnt_set = false;
0174     bool record_opt_set = false;
0175     bool try_stack_size = false;
0176 
0177     callchain_param.enabled = true;
0178     symbol_conf.use_callchain = true;
0179 
0180     if (!arg)
0181         return 0;
0182 
0183     while ((tok = strtok_r((char *)arg, ",", &saveptr)) != NULL) {
0184         if (!strncmp(tok, "none", strlen(tok))) {
0185             callchain_param.mode = CHAIN_NONE;
0186             callchain_param.enabled = false;
0187             symbol_conf.use_callchain = false;
0188             return 0;
0189         }
0190 
0191         if (!parse_callchain_mode(tok) ||
0192             !parse_callchain_order(tok) ||
0193             !parse_callchain_sort_key(tok) ||
0194             !parse_callchain_value(tok)) {
0195             /* parsing ok - move on to the next */
0196             try_stack_size = false;
0197             goto next;
0198         } else if (allow_record_opt && !record_opt_set) {
0199             if (parse_callchain_record(tok, &callchain_param))
0200                 goto try_numbers;
0201 
0202             /* assume that number followed by 'dwarf' is stack size */
0203             if (callchain_param.record_mode == CALLCHAIN_DWARF)
0204                 try_stack_size = true;
0205 
0206             record_opt_set = true;
0207             goto next;
0208         }
0209 
0210 try_numbers:
0211         if (try_stack_size) {
0212             unsigned long size = 0;
0213 
0214             if (get_stack_size(tok, &size) < 0)
0215                 return -1;
0216             callchain_param.dump_size = size;
0217             try_stack_size = false;
0218         } else if (!minpcnt_set) {
0219             /* try to get the min percent */
0220             callchain_param.min_percent = strtod(tok, &endptr);
0221             if (tok == endptr)
0222                 return -1;
0223             minpcnt_set = true;
0224         } else {
0225             /* try print limit at last */
0226             callchain_param.print_limit = strtoul(tok, &endptr, 0);
0227             if (tok == endptr)
0228                 return -1;
0229         }
0230 next:
0231         arg = NULL;
0232     }
0233 
0234     if (callchain_register_param(&callchain_param) < 0) {
0235         pr_err("Can't register callchain params\n");
0236         return -1;
0237     }
0238     return 0;
0239 }
0240 
0241 int parse_callchain_report_opt(const char *arg)
0242 {
0243     return __parse_callchain_report_opt(arg, false);
0244 }
0245 
0246 int parse_callchain_top_opt(const char *arg)
0247 {
0248     return __parse_callchain_report_opt(arg, true);
0249 }
0250 
0251 int parse_callchain_record(const char *arg, struct callchain_param *param)
0252 {
0253     char *tok, *name, *saveptr = NULL;
0254     char *buf;
0255     int ret = -1;
0256 
0257     /* We need buffer that we know we can write to. */
0258     buf = malloc(strlen(arg) + 1);
0259     if (!buf)
0260         return -ENOMEM;
0261 
0262     strcpy(buf, arg);
0263 
0264     tok = strtok_r((char *)buf, ",", &saveptr);
0265     name = tok ? : (char *)buf;
0266 
0267     do {
0268         /* Framepointer style */
0269         if (!strncmp(name, "fp", sizeof("fp"))) {
0270             ret = 0;
0271             param->record_mode = CALLCHAIN_FP;
0272 
0273             tok = strtok_r(NULL, ",", &saveptr);
0274             if (tok) {
0275                 unsigned long size;
0276 
0277                 size = strtoul(tok, &name, 0);
0278                 if (size < (unsigned) sysctl__max_stack())
0279                     param->max_stack = size;
0280             }
0281             break;
0282 
0283         /* Dwarf style */
0284         } else if (!strncmp(name, "dwarf", sizeof("dwarf"))) {
0285             const unsigned long default_stack_dump_size = 8192;
0286 
0287             ret = 0;
0288             param->record_mode = CALLCHAIN_DWARF;
0289             param->dump_size = default_stack_dump_size;
0290             dwarf_callchain_users = true;
0291 
0292             tok = strtok_r(NULL, ",", &saveptr);
0293             if (tok) {
0294                 unsigned long size = 0;
0295 
0296                 ret = get_stack_size(tok, &size);
0297                 param->dump_size = size;
0298             }
0299         } else if (!strncmp(name, "lbr", sizeof("lbr"))) {
0300             if (!strtok_r(NULL, ",", &saveptr)) {
0301                 param->record_mode = CALLCHAIN_LBR;
0302                 ret = 0;
0303             } else
0304                 pr_err("callchain: No more arguments "
0305                     "needed for --call-graph lbr\n");
0306             break;
0307         } else {
0308             pr_err("callchain: Unknown --call-graph option "
0309                    "value: %s\n", arg);
0310             break;
0311         }
0312 
0313     } while (0);
0314 
0315     free(buf);
0316     return ret;
0317 }
0318 
0319 int perf_callchain_config(const char *var, const char *value)
0320 {
0321     char *endptr;
0322 
0323     if (!strstarts(var, "call-graph."))
0324         return 0;
0325     var += sizeof("call-graph.") - 1;
0326 
0327     if (!strcmp(var, "record-mode"))
0328         return parse_callchain_record_opt(value, &callchain_param);
0329     if (!strcmp(var, "dump-size")) {
0330         unsigned long size = 0;
0331         int ret;
0332 
0333         ret = get_stack_size(value, &size);
0334         callchain_param.dump_size = size;
0335 
0336         return ret;
0337     }
0338     if (!strcmp(var, "print-type")){
0339         int ret;
0340         ret = parse_callchain_mode(value);
0341         if (ret == -1)
0342             pr_err("Invalid callchain mode: %s\n", value);
0343         return ret;
0344     }
0345     if (!strcmp(var, "order")){
0346         int ret;
0347         ret = parse_callchain_order(value);
0348         if (ret == -1)
0349             pr_err("Invalid callchain order: %s\n", value);
0350         return ret;
0351     }
0352     if (!strcmp(var, "sort-key")){
0353         int ret;
0354         ret = parse_callchain_sort_key(value);
0355         if (ret == -1)
0356             pr_err("Invalid callchain sort key: %s\n", value);
0357         return ret;
0358     }
0359     if (!strcmp(var, "threshold")) {
0360         callchain_param.min_percent = strtod(value, &endptr);
0361         if (value == endptr) {
0362             pr_err("Invalid callchain threshold: %s\n", value);
0363             return -1;
0364         }
0365     }
0366     if (!strcmp(var, "print-limit")) {
0367         callchain_param.print_limit = strtod(value, &endptr);
0368         if (value == endptr) {
0369             pr_err("Invalid callchain print limit: %s\n", value);
0370             return -1;
0371         }
0372     }
0373 
0374     return 0;
0375 }
0376 
0377 static void
0378 rb_insert_callchain(struct rb_root *root, struct callchain_node *chain,
0379             enum chain_mode mode)
0380 {
0381     struct rb_node **p = &root->rb_node;
0382     struct rb_node *parent = NULL;
0383     struct callchain_node *rnode;
0384     u64 chain_cumul = callchain_cumul_hits(chain);
0385 
0386     while (*p) {
0387         u64 rnode_cumul;
0388 
0389         parent = *p;
0390         rnode = rb_entry(parent, struct callchain_node, rb_node);
0391         rnode_cumul = callchain_cumul_hits(rnode);
0392 
0393         switch (mode) {
0394         case CHAIN_FLAT:
0395         case CHAIN_FOLDED:
0396             if (rnode->hit < chain->hit)
0397                 p = &(*p)->rb_left;
0398             else
0399                 p = &(*p)->rb_right;
0400             break;
0401         case CHAIN_GRAPH_ABS: /* Falldown */
0402         case CHAIN_GRAPH_REL:
0403             if (rnode_cumul < chain_cumul)
0404                 p = &(*p)->rb_left;
0405             else
0406                 p = &(*p)->rb_right;
0407             break;
0408         case CHAIN_NONE:
0409         default:
0410             break;
0411         }
0412     }
0413 
0414     rb_link_node(&chain->rb_node, parent, p);
0415     rb_insert_color(&chain->rb_node, root);
0416 }
0417 
0418 static void
0419 __sort_chain_flat(struct rb_root *rb_root, struct callchain_node *node,
0420           u64 min_hit)
0421 {
0422     struct rb_node *n;
0423     struct callchain_node *child;
0424 
0425     n = rb_first(&node->rb_root_in);
0426     while (n) {
0427         child = rb_entry(n, struct callchain_node, rb_node_in);
0428         n = rb_next(n);
0429 
0430         __sort_chain_flat(rb_root, child, min_hit);
0431     }
0432 
0433     if (node->hit && node->hit >= min_hit)
0434         rb_insert_callchain(rb_root, node, CHAIN_FLAT);
0435 }
0436 
0437 /*
0438  * Once we get every callchains from the stream, we can now
0439  * sort them by hit
0440  */
0441 static void
0442 sort_chain_flat(struct rb_root *rb_root, struct callchain_root *root,
0443         u64 min_hit, struct callchain_param *param __maybe_unused)
0444 {
0445     *rb_root = RB_ROOT;
0446     __sort_chain_flat(rb_root, &root->node, min_hit);
0447 }
0448 
0449 static void __sort_chain_graph_abs(struct callchain_node *node,
0450                    u64 min_hit)
0451 {
0452     struct rb_node *n;
0453     struct callchain_node *child;
0454 
0455     node->rb_root = RB_ROOT;
0456     n = rb_first(&node->rb_root_in);
0457 
0458     while (n) {
0459         child = rb_entry(n, struct callchain_node, rb_node_in);
0460         n = rb_next(n);
0461 
0462         __sort_chain_graph_abs(child, min_hit);
0463         if (callchain_cumul_hits(child) >= min_hit)
0464             rb_insert_callchain(&node->rb_root, child,
0465                         CHAIN_GRAPH_ABS);
0466     }
0467 }
0468 
0469 static void
0470 sort_chain_graph_abs(struct rb_root *rb_root, struct callchain_root *chain_root,
0471              u64 min_hit, struct callchain_param *param __maybe_unused)
0472 {
0473     __sort_chain_graph_abs(&chain_root->node, min_hit);
0474     rb_root->rb_node = chain_root->node.rb_root.rb_node;
0475 }
0476 
0477 static void __sort_chain_graph_rel(struct callchain_node *node,
0478                    double min_percent)
0479 {
0480     struct rb_node *n;
0481     struct callchain_node *child;
0482     u64 min_hit;
0483 
0484     node->rb_root = RB_ROOT;
0485     min_hit = ceil(node->children_hit * min_percent);
0486 
0487     n = rb_first(&node->rb_root_in);
0488     while (n) {
0489         child = rb_entry(n, struct callchain_node, rb_node_in);
0490         n = rb_next(n);
0491 
0492         __sort_chain_graph_rel(child, min_percent);
0493         if (callchain_cumul_hits(child) >= min_hit)
0494             rb_insert_callchain(&node->rb_root, child,
0495                         CHAIN_GRAPH_REL);
0496     }
0497 }
0498 
0499 static void
0500 sort_chain_graph_rel(struct rb_root *rb_root, struct callchain_root *chain_root,
0501              u64 min_hit __maybe_unused, struct callchain_param *param)
0502 {
0503     __sort_chain_graph_rel(&chain_root->node, param->min_percent / 100.0);
0504     rb_root->rb_node = chain_root->node.rb_root.rb_node;
0505 }
0506 
0507 int callchain_register_param(struct callchain_param *param)
0508 {
0509     switch (param->mode) {
0510     case CHAIN_GRAPH_ABS:
0511         param->sort = sort_chain_graph_abs;
0512         break;
0513     case CHAIN_GRAPH_REL:
0514         param->sort = sort_chain_graph_rel;
0515         break;
0516     case CHAIN_FLAT:
0517     case CHAIN_FOLDED:
0518         param->sort = sort_chain_flat;
0519         break;
0520     case CHAIN_NONE:
0521     default:
0522         return -1;
0523     }
0524     return 0;
0525 }
0526 
0527 /*
0528  * Create a child for a parent. If inherit_children, then the new child
0529  * will become the new parent of it's parent children
0530  */
0531 static struct callchain_node *
0532 create_child(struct callchain_node *parent, bool inherit_children)
0533 {
0534     struct callchain_node *new;
0535 
0536     new = zalloc(sizeof(*new));
0537     if (!new) {
0538         perror("not enough memory to create child for code path tree");
0539         return NULL;
0540     }
0541     new->parent = parent;
0542     INIT_LIST_HEAD(&new->val);
0543     INIT_LIST_HEAD(&new->parent_val);
0544 
0545     if (inherit_children) {
0546         struct rb_node *n;
0547         struct callchain_node *child;
0548 
0549         new->rb_root_in = parent->rb_root_in;
0550         parent->rb_root_in = RB_ROOT;
0551 
0552         n = rb_first(&new->rb_root_in);
0553         while (n) {
0554             child = rb_entry(n, struct callchain_node, rb_node_in);
0555             child->parent = new;
0556             n = rb_next(n);
0557         }
0558 
0559         /* make it the first child */
0560         rb_link_node(&new->rb_node_in, NULL, &parent->rb_root_in.rb_node);
0561         rb_insert_color(&new->rb_node_in, &parent->rb_root_in);
0562     }
0563 
0564     return new;
0565 }
0566 
0567 
0568 /*
0569  * Fill the node with callchain values
0570  */
0571 static int
0572 fill_node(struct callchain_node *node, struct callchain_cursor *cursor)
0573 {
0574     struct callchain_cursor_node *cursor_node;
0575 
0576     node->val_nr = cursor->nr - cursor->pos;
0577     if (!node->val_nr)
0578         pr_warning("Warning: empty node in callchain tree\n");
0579 
0580     cursor_node = callchain_cursor_current(cursor);
0581 
0582     while (cursor_node) {
0583         struct callchain_list *call;
0584 
0585         call = zalloc(sizeof(*call));
0586         if (!call) {
0587             perror("not enough memory for the code path tree");
0588             return -1;
0589         }
0590         call->ip = cursor_node->ip;
0591         call->ms = cursor_node->ms;
0592         map__get(call->ms.map);
0593         call->srcline = cursor_node->srcline;
0594 
0595         if (cursor_node->branch) {
0596             call->branch_count = 1;
0597 
0598             if (cursor_node->branch_from) {
0599                 /*
0600                  * branch_from is set with value somewhere else
0601                  * to imply it's "to" of a branch.
0602                  */
0603                 call->brtype_stat.branch_to = true;
0604 
0605                 if (cursor_node->branch_flags.predicted)
0606                     call->predicted_count = 1;
0607 
0608                 if (cursor_node->branch_flags.abort)
0609                     call->abort_count = 1;
0610 
0611                 branch_type_count(&call->brtype_stat,
0612                           &cursor_node->branch_flags,
0613                           cursor_node->branch_from,
0614                           cursor_node->ip);
0615             } else {
0616                 /*
0617                  * It's "from" of a branch
0618                  */
0619                 call->brtype_stat.branch_to = false;
0620                 call->cycles_count =
0621                     cursor_node->branch_flags.cycles;
0622                 call->iter_count = cursor_node->nr_loop_iter;
0623                 call->iter_cycles = cursor_node->iter_cycles;
0624             }
0625         }
0626 
0627         list_add_tail(&call->list, &node->val);
0628 
0629         callchain_cursor_advance(cursor);
0630         cursor_node = callchain_cursor_current(cursor);
0631     }
0632     return 0;
0633 }
0634 
0635 static struct callchain_node *
0636 add_child(struct callchain_node *parent,
0637       struct callchain_cursor *cursor,
0638       u64 period)
0639 {
0640     struct callchain_node *new;
0641 
0642     new = create_child(parent, false);
0643     if (new == NULL)
0644         return NULL;
0645 
0646     if (fill_node(new, cursor) < 0) {
0647         struct callchain_list *call, *tmp;
0648 
0649         list_for_each_entry_safe(call, tmp, &new->val, list) {
0650             list_del_init(&call->list);
0651             map__zput(call->ms.map);
0652             free(call);
0653         }
0654         free(new);
0655         return NULL;
0656     }
0657 
0658     new->children_hit = 0;
0659     new->hit = period;
0660     new->children_count = 0;
0661     new->count = 1;
0662     return new;
0663 }
0664 
0665 enum match_result {
0666     MATCH_ERROR  = -1,
0667     MATCH_EQ,
0668     MATCH_LT,
0669     MATCH_GT,
0670 };
0671 
0672 static enum match_result match_chain_strings(const char *left,
0673                          const char *right)
0674 {
0675     enum match_result ret = MATCH_EQ;
0676     int cmp;
0677 
0678     if (left && right)
0679         cmp = strcmp(left, right);
0680     else if (!left && right)
0681         cmp = 1;
0682     else if (left && !right)
0683         cmp = -1;
0684     else
0685         return MATCH_ERROR;
0686 
0687     if (cmp != 0)
0688         ret = cmp < 0 ? MATCH_LT : MATCH_GT;
0689 
0690     return ret;
0691 }
0692 
0693 /*
0694  * We need to always use relative addresses because we're aggregating
0695  * callchains from multiple threads, i.e. different address spaces, so
0696  * comparing absolute addresses make no sense as a symbol in a DSO may end up
0697  * in a different address when used in a different binary or even the same
0698  * binary but with some sort of address randomization technique, thus we need
0699  * to compare just relative addresses. -acme
0700  */
0701 static enum match_result match_chain_dso_addresses(struct map *left_map, u64 left_ip,
0702                            struct map *right_map, u64 right_ip)
0703 {
0704     struct dso *left_dso = left_map ? left_map->dso : NULL;
0705     struct dso *right_dso = right_map ? right_map->dso : NULL;
0706 
0707     if (left_dso != right_dso)
0708         return left_dso < right_dso ? MATCH_LT : MATCH_GT;
0709 
0710     if (left_ip != right_ip)
0711         return left_ip < right_ip ? MATCH_LT : MATCH_GT;
0712 
0713     return MATCH_EQ;
0714 }
0715 
0716 static enum match_result match_chain(struct callchain_cursor_node *node,
0717                      struct callchain_list *cnode)
0718 {
0719     enum match_result match = MATCH_ERROR;
0720 
0721     switch (callchain_param.key) {
0722     case CCKEY_SRCLINE:
0723         match = match_chain_strings(cnode->srcline, node->srcline);
0724         if (match != MATCH_ERROR)
0725             break;
0726         /* otherwise fall-back to symbol-based comparison below */
0727         __fallthrough;
0728     case CCKEY_FUNCTION:
0729         if (node->ms.sym && cnode->ms.sym) {
0730             /*
0731              * Compare inlined frames based on their symbol name
0732              * because different inlined frames will have the same
0733              * symbol start. Otherwise do a faster comparison based
0734              * on the symbol start address.
0735              */
0736             if (cnode->ms.sym->inlined || node->ms.sym->inlined) {
0737                 match = match_chain_strings(cnode->ms.sym->name,
0738                                 node->ms.sym->name);
0739                 if (match != MATCH_ERROR)
0740                     break;
0741             } else {
0742                 match = match_chain_dso_addresses(cnode->ms.map, cnode->ms.sym->start,
0743                                   node->ms.map, node->ms.sym->start);
0744                 break;
0745             }
0746         }
0747         /* otherwise fall-back to IP-based comparison below */
0748         __fallthrough;
0749     case CCKEY_ADDRESS:
0750     default:
0751         match = match_chain_dso_addresses(cnode->ms.map, cnode->ip, node->ms.map, node->ip);
0752         break;
0753     }
0754 
0755     if (match == MATCH_EQ && node->branch) {
0756         cnode->branch_count++;
0757 
0758         if (node->branch_from) {
0759             /*
0760              * It's "to" of a branch
0761              */
0762             cnode->brtype_stat.branch_to = true;
0763 
0764             if (node->branch_flags.predicted)
0765                 cnode->predicted_count++;
0766 
0767             if (node->branch_flags.abort)
0768                 cnode->abort_count++;
0769 
0770             branch_type_count(&cnode->brtype_stat,
0771                       &node->branch_flags,
0772                       node->branch_from,
0773                       node->ip);
0774         } else {
0775             /*
0776              * It's "from" of a branch
0777              */
0778             cnode->brtype_stat.branch_to = false;
0779             cnode->cycles_count += node->branch_flags.cycles;
0780             cnode->iter_count += node->nr_loop_iter;
0781             cnode->iter_cycles += node->iter_cycles;
0782             cnode->from_count++;
0783         }
0784     }
0785 
0786     return match;
0787 }
0788 
0789 /*
0790  * Split the parent in two parts (a new child is created) and
0791  * give a part of its callchain to the created child.
0792  * Then create another child to host the given callchain of new branch
0793  */
0794 static int
0795 split_add_child(struct callchain_node *parent,
0796         struct callchain_cursor *cursor,
0797         struct callchain_list *to_split,
0798         u64 idx_parents, u64 idx_local, u64 period)
0799 {
0800     struct callchain_node *new;
0801     struct list_head *old_tail;
0802     unsigned int idx_total = idx_parents + idx_local;
0803 
0804     /* split */
0805     new = create_child(parent, true);
0806     if (new == NULL)
0807         return -1;
0808 
0809     /* split the callchain and move a part to the new child */
0810     old_tail = parent->val.prev;
0811     list_del_range(&to_split->list, old_tail);
0812     new->val.next = &to_split->list;
0813     new->val.prev = old_tail;
0814     to_split->list.prev = &new->val;
0815     old_tail->next = &new->val;
0816 
0817     /* split the hits */
0818     new->hit = parent->hit;
0819     new->children_hit = parent->children_hit;
0820     parent->children_hit = callchain_cumul_hits(new);
0821     new->val_nr = parent->val_nr - idx_local;
0822     parent->val_nr = idx_local;
0823     new->count = parent->count;
0824     new->children_count = parent->children_count;
0825     parent->children_count = callchain_cumul_counts(new);
0826 
0827     /* create a new child for the new branch if any */
0828     if (idx_total < cursor->nr) {
0829         struct callchain_node *first;
0830         struct callchain_list *cnode;
0831         struct callchain_cursor_node *node;
0832         struct rb_node *p, **pp;
0833 
0834         parent->hit = 0;
0835         parent->children_hit += period;
0836         parent->count = 0;
0837         parent->children_count += 1;
0838 
0839         node = callchain_cursor_current(cursor);
0840         new = add_child(parent, cursor, period);
0841         if (new == NULL)
0842             return -1;
0843 
0844         /*
0845          * This is second child since we moved parent's children
0846          * to new (first) child above.
0847          */
0848         p = parent->rb_root_in.rb_node;
0849         first = rb_entry(p, struct callchain_node, rb_node_in);
0850         cnode = list_first_entry(&first->val, struct callchain_list,
0851                      list);
0852 
0853         if (match_chain(node, cnode) == MATCH_LT)
0854             pp = &p->rb_left;
0855         else
0856             pp = &p->rb_right;
0857 
0858         rb_link_node(&new->rb_node_in, p, pp);
0859         rb_insert_color(&new->rb_node_in, &parent->rb_root_in);
0860     } else {
0861         parent->hit = period;
0862         parent->count = 1;
0863     }
0864     return 0;
0865 }
0866 
0867 static enum match_result
0868 append_chain(struct callchain_node *root,
0869          struct callchain_cursor *cursor,
0870          u64 period);
0871 
0872 static int
0873 append_chain_children(struct callchain_node *root,
0874               struct callchain_cursor *cursor,
0875               u64 period)
0876 {
0877     struct callchain_node *rnode;
0878     struct callchain_cursor_node *node;
0879     struct rb_node **p = &root->rb_root_in.rb_node;
0880     struct rb_node *parent = NULL;
0881 
0882     node = callchain_cursor_current(cursor);
0883     if (!node)
0884         return -1;
0885 
0886     /* lookup in children */
0887     while (*p) {
0888         enum match_result ret;
0889 
0890         parent = *p;
0891         rnode = rb_entry(parent, struct callchain_node, rb_node_in);
0892 
0893         /* If at least first entry matches, rely to children */
0894         ret = append_chain(rnode, cursor, period);
0895         if (ret == MATCH_EQ)
0896             goto inc_children_hit;
0897         if (ret == MATCH_ERROR)
0898             return -1;
0899 
0900         if (ret == MATCH_LT)
0901             p = &parent->rb_left;
0902         else
0903             p = &parent->rb_right;
0904     }
0905     /* nothing in children, add to the current node */
0906     rnode = add_child(root, cursor, period);
0907     if (rnode == NULL)
0908         return -1;
0909 
0910     rb_link_node(&rnode->rb_node_in, parent, p);
0911     rb_insert_color(&rnode->rb_node_in, &root->rb_root_in);
0912 
0913 inc_children_hit:
0914     root->children_hit += period;
0915     root->children_count++;
0916     return 0;
0917 }
0918 
0919 static enum match_result
0920 append_chain(struct callchain_node *root,
0921          struct callchain_cursor *cursor,
0922          u64 period)
0923 {
0924     struct callchain_list *cnode;
0925     u64 start = cursor->pos;
0926     bool found = false;
0927     u64 matches;
0928     enum match_result cmp = MATCH_ERROR;
0929 
0930     /*
0931      * Lookup in the current node
0932      * If we have a symbol, then compare the start to match
0933      * anywhere inside a function, unless function
0934      * mode is disabled.
0935      */
0936     list_for_each_entry(cnode, &root->val, list) {
0937         struct callchain_cursor_node *node;
0938 
0939         node = callchain_cursor_current(cursor);
0940         if (!node)
0941             break;
0942 
0943         cmp = match_chain(node, cnode);
0944         if (cmp != MATCH_EQ)
0945             break;
0946 
0947         found = true;
0948 
0949         callchain_cursor_advance(cursor);
0950     }
0951 
0952     /* matches not, relay no the parent */
0953     if (!found) {
0954         WARN_ONCE(cmp == MATCH_ERROR, "Chain comparison error\n");
0955         return cmp;
0956     }
0957 
0958     matches = cursor->pos - start;
0959 
0960     /* we match only a part of the node. Split it and add the new chain */
0961     if (matches < root->val_nr) {
0962         if (split_add_child(root, cursor, cnode, start, matches,
0963                     period) < 0)
0964             return MATCH_ERROR;
0965 
0966         return MATCH_EQ;
0967     }
0968 
0969     /* we match 100% of the path, increment the hit */
0970     if (matches == root->val_nr && cursor->pos == cursor->nr) {
0971         root->hit += period;
0972         root->count++;
0973         return MATCH_EQ;
0974     }
0975 
0976     /* We match the node and still have a part remaining */
0977     if (append_chain_children(root, cursor, period) < 0)
0978         return MATCH_ERROR;
0979 
0980     return MATCH_EQ;
0981 }
0982 
0983 int callchain_append(struct callchain_root *root,
0984              struct callchain_cursor *cursor,
0985              u64 period)
0986 {
0987     if (!cursor->nr)
0988         return 0;
0989 
0990     callchain_cursor_commit(cursor);
0991 
0992     if (append_chain_children(&root->node, cursor, period) < 0)
0993         return -1;
0994 
0995     if (cursor->nr > root->max_depth)
0996         root->max_depth = cursor->nr;
0997 
0998     return 0;
0999 }
1000 
1001 static int
1002 merge_chain_branch(struct callchain_cursor *cursor,
1003            struct callchain_node *dst, struct callchain_node *src)
1004 {
1005     struct callchain_cursor_node **old_last = cursor->last;
1006     struct callchain_node *child;
1007     struct callchain_list *list, *next_list;
1008     struct rb_node *n;
1009     int old_pos = cursor->nr;
1010     int err = 0;
1011 
1012     list_for_each_entry_safe(list, next_list, &src->val, list) {
1013         callchain_cursor_append(cursor, list->ip, &list->ms,
1014                     false, NULL, 0, 0, 0, list->srcline);
1015         list_del_init(&list->list);
1016         map__zput(list->ms.map);
1017         free(list);
1018     }
1019 
1020     if (src->hit) {
1021         callchain_cursor_commit(cursor);
1022         if (append_chain_children(dst, cursor, src->hit) < 0)
1023             return -1;
1024     }
1025 
1026     n = rb_first(&src->rb_root_in);
1027     while (n) {
1028         child = container_of(n, struct callchain_node, rb_node_in);
1029         n = rb_next(n);
1030         rb_erase(&child->rb_node_in, &src->rb_root_in);
1031 
1032         err = merge_chain_branch(cursor, dst, child);
1033         if (err)
1034             break;
1035 
1036         free(child);
1037     }
1038 
1039     cursor->nr = old_pos;
1040     cursor->last = old_last;
1041 
1042     return err;
1043 }
1044 
1045 int callchain_merge(struct callchain_cursor *cursor,
1046             struct callchain_root *dst, struct callchain_root *src)
1047 {
1048     return merge_chain_branch(cursor, &dst->node, &src->node);
1049 }
1050 
1051 int callchain_cursor_append(struct callchain_cursor *cursor,
1052                 u64 ip, struct map_symbol *ms,
1053                 bool branch, struct branch_flags *flags,
1054                 int nr_loop_iter, u64 iter_cycles, u64 branch_from,
1055                 const char *srcline)
1056 {
1057     struct callchain_cursor_node *node = *cursor->last;
1058 
1059     if (!node) {
1060         node = calloc(1, sizeof(*node));
1061         if (!node)
1062             return -ENOMEM;
1063 
1064         *cursor->last = node;
1065     }
1066 
1067     node->ip = ip;
1068     map__zput(node->ms.map);
1069     node->ms = *ms;
1070     map__get(node->ms.map);
1071     node->branch = branch;
1072     node->nr_loop_iter = nr_loop_iter;
1073     node->iter_cycles = iter_cycles;
1074     node->srcline = srcline;
1075 
1076     if (flags)
1077         memcpy(&node->branch_flags, flags,
1078             sizeof(struct branch_flags));
1079 
1080     node->branch_from = branch_from;
1081     cursor->nr++;
1082 
1083     cursor->last = &node->next;
1084 
1085     return 0;
1086 }
1087 
1088 int sample__resolve_callchain(struct perf_sample *sample,
1089                   struct callchain_cursor *cursor, struct symbol **parent,
1090                   struct evsel *evsel, struct addr_location *al,
1091                   int max_stack)
1092 {
1093     if (sample->callchain == NULL && !symbol_conf.show_branchflag_count)
1094         return 0;
1095 
1096     if (symbol_conf.use_callchain || symbol_conf.cumulate_callchain ||
1097         perf_hpp_list.parent || symbol_conf.show_branchflag_count) {
1098         return thread__resolve_callchain(al->thread, cursor, evsel, sample,
1099                          parent, al, max_stack);
1100     }
1101     return 0;
1102 }
1103 
1104 int hist_entry__append_callchain(struct hist_entry *he, struct perf_sample *sample)
1105 {
1106     if ((!symbol_conf.use_callchain || sample->callchain == NULL) &&
1107         !symbol_conf.show_branchflag_count)
1108         return 0;
1109     return callchain_append(he->callchain, &callchain_cursor, sample->period);
1110 }
1111 
1112 int fill_callchain_info(struct addr_location *al, struct callchain_cursor_node *node,
1113             bool hide_unresolved)
1114 {
1115     al->maps = node->ms.maps;
1116     al->map = node->ms.map;
1117     al->sym = node->ms.sym;
1118     al->srcline = node->srcline;
1119     al->addr = node->ip;
1120 
1121     if (al->sym == NULL) {
1122         if (hide_unresolved)
1123             return 0;
1124         if (al->map == NULL)
1125             goto out;
1126     }
1127 
1128     if (al->maps == machine__kernel_maps(al->maps->machine)) {
1129         if (machine__is_host(al->maps->machine)) {
1130             al->cpumode = PERF_RECORD_MISC_KERNEL;
1131             al->level = 'k';
1132         } else {
1133             al->cpumode = PERF_RECORD_MISC_GUEST_KERNEL;
1134             al->level = 'g';
1135         }
1136     } else {
1137         if (machine__is_host(al->maps->machine)) {
1138             al->cpumode = PERF_RECORD_MISC_USER;
1139             al->level = '.';
1140         } else if (perf_guest) {
1141             al->cpumode = PERF_RECORD_MISC_GUEST_USER;
1142             al->level = 'u';
1143         } else {
1144             al->cpumode = PERF_RECORD_MISC_HYPERVISOR;
1145             al->level = 'H';
1146         }
1147     }
1148 
1149 out:
1150     return 1;
1151 }
1152 
1153 char *callchain_list__sym_name(struct callchain_list *cl,
1154                    char *bf, size_t bfsize, bool show_dso)
1155 {
1156     bool show_addr = callchain_param.key == CCKEY_ADDRESS;
1157     bool show_srcline = show_addr || callchain_param.key == CCKEY_SRCLINE;
1158     int printed;
1159 
1160     if (cl->ms.sym) {
1161         const char *inlined = cl->ms.sym->inlined ? " (inlined)" : "";
1162 
1163         if (show_srcline && cl->srcline)
1164             printed = scnprintf(bf, bfsize, "%s %s%s",
1165                         cl->ms.sym->name, cl->srcline,
1166                         inlined);
1167         else
1168             printed = scnprintf(bf, bfsize, "%s%s",
1169                         cl->ms.sym->name, inlined);
1170     } else
1171         printed = scnprintf(bf, bfsize, "%#" PRIx64, cl->ip);
1172 
1173     if (show_dso)
1174         scnprintf(bf + printed, bfsize - printed, " %s",
1175               cl->ms.map ?
1176               cl->ms.map->dso->short_name :
1177               "unknown");
1178 
1179     return bf;
1180 }
1181 
1182 char *callchain_node__scnprintf_value(struct callchain_node *node,
1183                       char *bf, size_t bfsize, u64 total)
1184 {
1185     double percent = 0.0;
1186     u64 period = callchain_cumul_hits(node);
1187     unsigned count = callchain_cumul_counts(node);
1188 
1189     if (callchain_param.mode == CHAIN_FOLDED) {
1190         period = node->hit;
1191         count = node->count;
1192     }
1193 
1194     switch (callchain_param.value) {
1195     case CCVAL_PERIOD:
1196         scnprintf(bf, bfsize, "%"PRIu64, period);
1197         break;
1198     case CCVAL_COUNT:
1199         scnprintf(bf, bfsize, "%u", count);
1200         break;
1201     case CCVAL_PERCENT:
1202     default:
1203         if (total)
1204             percent = period * 100.0 / total;
1205         scnprintf(bf, bfsize, "%.2f%%", percent);
1206         break;
1207     }
1208     return bf;
1209 }
1210 
1211 int callchain_node__fprintf_value(struct callchain_node *node,
1212                  FILE *fp, u64 total)
1213 {
1214     double percent = 0.0;
1215     u64 period = callchain_cumul_hits(node);
1216     unsigned count = callchain_cumul_counts(node);
1217 
1218     if (callchain_param.mode == CHAIN_FOLDED) {
1219         period = node->hit;
1220         count = node->count;
1221     }
1222 
1223     switch (callchain_param.value) {
1224     case CCVAL_PERIOD:
1225         return fprintf(fp, "%"PRIu64, period);
1226     case CCVAL_COUNT:
1227         return fprintf(fp, "%u", count);
1228     case CCVAL_PERCENT:
1229     default:
1230         if (total)
1231             percent = period * 100.0 / total;
1232         return percent_color_fprintf(fp, "%.2f%%", percent);
1233     }
1234     return 0;
1235 }
1236 
1237 static void callchain_counts_value(struct callchain_node *node,
1238                    u64 *branch_count, u64 *predicted_count,
1239                    u64 *abort_count, u64 *cycles_count)
1240 {
1241     struct callchain_list *clist;
1242 
1243     list_for_each_entry(clist, &node->val, list) {
1244         if (branch_count)
1245             *branch_count += clist->branch_count;
1246 
1247         if (predicted_count)
1248             *predicted_count += clist->predicted_count;
1249 
1250         if (abort_count)
1251             *abort_count += clist->abort_count;
1252 
1253         if (cycles_count)
1254             *cycles_count += clist->cycles_count;
1255     }
1256 }
1257 
1258 static int callchain_node_branch_counts_cumul(struct callchain_node *node,
1259                           u64 *branch_count,
1260                           u64 *predicted_count,
1261                           u64 *abort_count,
1262                           u64 *cycles_count)
1263 {
1264     struct callchain_node *child;
1265     struct rb_node *n;
1266 
1267     n = rb_first(&node->rb_root_in);
1268     while (n) {
1269         child = rb_entry(n, struct callchain_node, rb_node_in);
1270         n = rb_next(n);
1271 
1272         callchain_node_branch_counts_cumul(child, branch_count,
1273                            predicted_count,
1274                            abort_count,
1275                            cycles_count);
1276 
1277         callchain_counts_value(child, branch_count,
1278                        predicted_count, abort_count,
1279                        cycles_count);
1280     }
1281 
1282     return 0;
1283 }
1284 
1285 int callchain_branch_counts(struct callchain_root *root,
1286                 u64 *branch_count, u64 *predicted_count,
1287                 u64 *abort_count, u64 *cycles_count)
1288 {
1289     if (branch_count)
1290         *branch_count = 0;
1291 
1292     if (predicted_count)
1293         *predicted_count = 0;
1294 
1295     if (abort_count)
1296         *abort_count = 0;
1297 
1298     if (cycles_count)
1299         *cycles_count = 0;
1300 
1301     return callchain_node_branch_counts_cumul(&root->node,
1302                           branch_count,
1303                           predicted_count,
1304                           abort_count,
1305                           cycles_count);
1306 }
1307 
1308 static int count_pri64_printf(int idx, const char *str, u64 value, char *bf, int bfsize)
1309 {
1310     int printed;
1311 
1312     printed = scnprintf(bf, bfsize, "%s%s:%" PRId64 "", (idx) ? " " : " (", str, value);
1313 
1314     return printed;
1315 }
1316 
1317 static int count_float_printf(int idx, const char *str, float value,
1318                   char *bf, int bfsize, float threshold)
1319 {
1320     int printed;
1321 
1322     if (threshold != 0.0 && value < threshold)
1323         return 0;
1324 
1325     printed = scnprintf(bf, bfsize, "%s%s:%.1f%%", (idx) ? " " : " (", str, value);
1326 
1327     return printed;
1328 }
1329 
1330 static int branch_to_str(char *bf, int bfsize,
1331              u64 branch_count, u64 predicted_count,
1332              u64 abort_count,
1333              struct branch_type_stat *brtype_stat)
1334 {
1335     int printed, i = 0;
1336 
1337     printed = branch_type_str(brtype_stat, bf, bfsize);
1338     if (printed)
1339         i++;
1340 
1341     if (predicted_count < branch_count) {
1342         printed += count_float_printf(i++, "predicted",
1343                 predicted_count * 100.0 / branch_count,
1344                 bf + printed, bfsize - printed, 0.0);
1345     }
1346 
1347     if (abort_count) {
1348         printed += count_float_printf(i++, "abort",
1349                 abort_count * 100.0 / branch_count,
1350                 bf + printed, bfsize - printed, 0.1);
1351     }
1352 
1353     if (i)
1354         printed += scnprintf(bf + printed, bfsize - printed, ")");
1355 
1356     return printed;
1357 }
1358 
1359 static int branch_from_str(char *bf, int bfsize,
1360                u64 branch_count,
1361                u64 cycles_count, u64 iter_count,
1362                u64 iter_cycles, u64 from_count)
1363 {
1364     int printed = 0, i = 0;
1365     u64 cycles, v = 0;
1366 
1367     cycles = cycles_count / branch_count;
1368     if (cycles) {
1369         printed += count_pri64_printf(i++, "cycles",
1370                 cycles,
1371                 bf + printed, bfsize - printed);
1372     }
1373 
1374     if (iter_count && from_count) {
1375         v = iter_count / from_count;
1376         if (v) {
1377             printed += count_pri64_printf(i++, "iter",
1378                     v, bf + printed, bfsize - printed);
1379 
1380             printed += count_pri64_printf(i++, "avg_cycles",
1381                     iter_cycles / iter_count,
1382                     bf + printed, bfsize - printed);
1383         }
1384     }
1385 
1386     if (i)
1387         printed += scnprintf(bf + printed, bfsize - printed, ")");
1388 
1389     return printed;
1390 }
1391 
1392 static int counts_str_build(char *bf, int bfsize,
1393                  u64 branch_count, u64 predicted_count,
1394                  u64 abort_count, u64 cycles_count,
1395                  u64 iter_count, u64 iter_cycles,
1396                  u64 from_count,
1397                  struct branch_type_stat *brtype_stat)
1398 {
1399     int printed;
1400 
1401     if (branch_count == 0)
1402         return scnprintf(bf, bfsize, " (calltrace)");
1403 
1404     if (brtype_stat->branch_to) {
1405         printed = branch_to_str(bf, bfsize, branch_count,
1406                 predicted_count, abort_count, brtype_stat);
1407     } else {
1408         printed = branch_from_str(bf, bfsize, branch_count,
1409                 cycles_count, iter_count, iter_cycles,
1410                 from_count);
1411     }
1412 
1413     if (!printed)
1414         bf[0] = 0;
1415 
1416     return printed;
1417 }
1418 
1419 static int callchain_counts_printf(FILE *fp, char *bf, int bfsize,
1420                    u64 branch_count, u64 predicted_count,
1421                    u64 abort_count, u64 cycles_count,
1422                    u64 iter_count, u64 iter_cycles,
1423                    u64 from_count,
1424                    struct branch_type_stat *brtype_stat)
1425 {
1426     char str[256];
1427 
1428     counts_str_build(str, sizeof(str), branch_count,
1429              predicted_count, abort_count, cycles_count,
1430              iter_count, iter_cycles, from_count, brtype_stat);
1431 
1432     if (fp)
1433         return fprintf(fp, "%s", str);
1434 
1435     return scnprintf(bf, bfsize, "%s", str);
1436 }
1437 
1438 int callchain_list_counts__printf_value(struct callchain_list *clist,
1439                     FILE *fp, char *bf, int bfsize)
1440 {
1441     u64 branch_count, predicted_count;
1442     u64 abort_count, cycles_count;
1443     u64 iter_count, iter_cycles;
1444     u64 from_count;
1445 
1446     branch_count = clist->branch_count;
1447     predicted_count = clist->predicted_count;
1448     abort_count = clist->abort_count;
1449     cycles_count = clist->cycles_count;
1450     iter_count = clist->iter_count;
1451     iter_cycles = clist->iter_cycles;
1452     from_count = clist->from_count;
1453 
1454     return callchain_counts_printf(fp, bf, bfsize, branch_count,
1455                        predicted_count, abort_count,
1456                        cycles_count, iter_count, iter_cycles,
1457                        from_count, &clist->brtype_stat);
1458 }
1459 
1460 static void free_callchain_node(struct callchain_node *node)
1461 {
1462     struct callchain_list *list, *tmp;
1463     struct callchain_node *child;
1464     struct rb_node *n;
1465 
1466     list_for_each_entry_safe(list, tmp, &node->parent_val, list) {
1467         list_del_init(&list->list);
1468         map__zput(list->ms.map);
1469         free(list);
1470     }
1471 
1472     list_for_each_entry_safe(list, tmp, &node->val, list) {
1473         list_del_init(&list->list);
1474         map__zput(list->ms.map);
1475         free(list);
1476     }
1477 
1478     n = rb_first(&node->rb_root_in);
1479     while (n) {
1480         child = container_of(n, struct callchain_node, rb_node_in);
1481         n = rb_next(n);
1482         rb_erase(&child->rb_node_in, &node->rb_root_in);
1483 
1484         free_callchain_node(child);
1485         free(child);
1486     }
1487 }
1488 
1489 void free_callchain(struct callchain_root *root)
1490 {
1491     if (!symbol_conf.use_callchain)
1492         return;
1493 
1494     free_callchain_node(&root->node);
1495 }
1496 
1497 static u64 decay_callchain_node(struct callchain_node *node)
1498 {
1499     struct callchain_node *child;
1500     struct rb_node *n;
1501     u64 child_hits = 0;
1502 
1503     n = rb_first(&node->rb_root_in);
1504     while (n) {
1505         child = container_of(n, struct callchain_node, rb_node_in);
1506 
1507         child_hits += decay_callchain_node(child);
1508         n = rb_next(n);
1509     }
1510 
1511     node->hit = (node->hit * 7) / 8;
1512     node->children_hit = child_hits;
1513 
1514     return node->hit;
1515 }
1516 
1517 void decay_callchain(struct callchain_root *root)
1518 {
1519     if (!symbol_conf.use_callchain)
1520         return;
1521 
1522     decay_callchain_node(&root->node);
1523 }
1524 
1525 int callchain_node__make_parent_list(struct callchain_node *node)
1526 {
1527     struct callchain_node *parent = node->parent;
1528     struct callchain_list *chain, *new;
1529     LIST_HEAD(head);
1530 
1531     while (parent) {
1532         list_for_each_entry_reverse(chain, &parent->val, list) {
1533             new = malloc(sizeof(*new));
1534             if (new == NULL)
1535                 goto out;
1536             *new = *chain;
1537             new->has_children = false;
1538             map__get(new->ms.map);
1539             list_add_tail(&new->list, &head);
1540         }
1541         parent = parent->parent;
1542     }
1543 
1544     list_for_each_entry_safe_reverse(chain, new, &head, list)
1545         list_move_tail(&chain->list, &node->parent_val);
1546 
1547     if (!list_empty(&node->parent_val)) {
1548         chain = list_first_entry(&node->parent_val, struct callchain_list, list);
1549         chain->has_children = rb_prev(&node->rb_node) || rb_next(&node->rb_node);
1550 
1551         chain = list_first_entry(&node->val, struct callchain_list, list);
1552         chain->has_children = false;
1553     }
1554     return 0;
1555 
1556 out:
1557     list_for_each_entry_safe(chain, new, &head, list) {
1558         list_del_init(&chain->list);
1559         map__zput(chain->ms.map);
1560         free(chain);
1561     }
1562     return -ENOMEM;
1563 }
1564 
1565 int callchain_cursor__copy(struct callchain_cursor *dst,
1566                struct callchain_cursor *src)
1567 {
1568     int rc = 0;
1569 
1570     callchain_cursor_reset(dst);
1571     callchain_cursor_commit(src);
1572 
1573     while (true) {
1574         struct callchain_cursor_node *node;
1575 
1576         node = callchain_cursor_current(src);
1577         if (node == NULL)
1578             break;
1579 
1580         rc = callchain_cursor_append(dst, node->ip, &node->ms,
1581                          node->branch, &node->branch_flags,
1582                          node->nr_loop_iter,
1583                          node->iter_cycles,
1584                          node->branch_from, node->srcline);
1585         if (rc)
1586             break;
1587 
1588         callchain_cursor_advance(src);
1589     }
1590 
1591     return rc;
1592 }
1593 
1594 /*
1595  * Initialize a cursor before adding entries inside, but keep
1596  * the previously allocated entries as a cache.
1597  */
1598 void callchain_cursor_reset(struct callchain_cursor *cursor)
1599 {
1600     struct callchain_cursor_node *node;
1601 
1602     cursor->nr = 0;
1603     cursor->last = &cursor->first;
1604 
1605     for (node = cursor->first; node != NULL; node = node->next)
1606         map__zput(node->ms.map);
1607 }
1608 
1609 void callchain_param_setup(u64 sample_type, const char *arch)
1610 {
1611     if (symbol_conf.use_callchain || symbol_conf.cumulate_callchain) {
1612         if ((sample_type & PERF_SAMPLE_REGS_USER) &&
1613             (sample_type & PERF_SAMPLE_STACK_USER)) {
1614             callchain_param.record_mode = CALLCHAIN_DWARF;
1615             dwarf_callchain_users = true;
1616         } else if (sample_type & PERF_SAMPLE_BRANCH_STACK)
1617             callchain_param.record_mode = CALLCHAIN_LBR;
1618         else
1619             callchain_param.record_mode = CALLCHAIN_FP;
1620     }
1621 
1622     /*
1623      * It's necessary to use libunwind to reliably determine the caller of
1624      * a leaf function on aarch64, as otherwise we cannot know whether to
1625      * start from the LR or FP.
1626      *
1627      * Always starting from the LR can result in duplicate or entirely
1628      * erroneous entries. Always skipping the LR and starting from the FP
1629      * can result in missing entries.
1630      */
1631     if (callchain_param.record_mode == CALLCHAIN_FP && !strcmp(arch, "arm64"))
1632         dwarf_callchain_users = true;
1633 }
1634 
1635 static bool chain_match(struct callchain_list *base_chain,
1636             struct callchain_list *pair_chain)
1637 {
1638     enum match_result match;
1639 
1640     match = match_chain_strings(base_chain->srcline,
1641                     pair_chain->srcline);
1642     if (match != MATCH_ERROR)
1643         return match == MATCH_EQ;
1644 
1645     match = match_chain_dso_addresses(base_chain->ms.map,
1646                       base_chain->ip,
1647                       pair_chain->ms.map,
1648                       pair_chain->ip);
1649 
1650     return match == MATCH_EQ;
1651 }
1652 
1653 bool callchain_cnode_matched(struct callchain_node *base_cnode,
1654                  struct callchain_node *pair_cnode)
1655 {
1656     struct callchain_list *base_chain, *pair_chain;
1657     bool match = false;
1658 
1659     pair_chain = list_first_entry(&pair_cnode->val,
1660                       struct callchain_list,
1661                       list);
1662 
1663     list_for_each_entry(base_chain, &base_cnode->val, list) {
1664         if (&pair_chain->list == &pair_cnode->val)
1665             return false;
1666 
1667         if (!base_chain->srcline || !pair_chain->srcline) {
1668             pair_chain = list_next_entry(pair_chain, list);
1669             continue;
1670         }
1671 
1672         match = chain_match(base_chain, pair_chain);
1673         if (!match)
1674             return false;
1675 
1676         pair_chain = list_next_entry(pair_chain, list);
1677     }
1678 
1679     /*
1680      * Say chain1 is ABC, chain2 is ABCD, we consider they are
1681      * not fully matched.
1682      */
1683     if (pair_chain && (&pair_chain->list != &pair_cnode->val))
1684         return false;
1685 
1686     return match;
1687 }
1688 
1689 static u64 count_callchain_hits(struct hist_entry *he)
1690 {
1691     struct rb_root *root = &he->sorted_chain;
1692     struct rb_node *rb_node = rb_first(root);
1693     struct callchain_node *node;
1694     u64 chain_hits = 0;
1695 
1696     while (rb_node) {
1697         node = rb_entry(rb_node, struct callchain_node, rb_node);
1698         chain_hits += node->hit;
1699         rb_node = rb_next(rb_node);
1700     }
1701 
1702     return chain_hits;
1703 }
1704 
1705 u64 callchain_total_hits(struct hists *hists)
1706 {
1707     struct rb_node *next = rb_first_cached(&hists->entries);
1708     u64 chain_hits = 0;
1709 
1710     while (next) {
1711         struct hist_entry *he = rb_entry(next, struct hist_entry,
1712                          rb_node);
1713 
1714         chain_hits += count_callchain_hits(he);
1715         next = rb_next(&he->rb_node);
1716     }
1717 
1718     return chain_hits;
1719 }
1720 
1721 s64 callchain_avg_cycles(struct callchain_node *cnode)
1722 {
1723     struct callchain_list *chain;
1724     s64 cycles = 0;
1725 
1726     list_for_each_entry(chain, &cnode->val, list) {
1727         if (chain->srcline && chain->branch_count)
1728             cycles += chain->cycles_count / chain->branch_count;
1729     }
1730 
1731     return cycles;
1732 }
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.1.0 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!