blob: 24b4bd0d77545e7bb9f95e83222eb103c92f5151 [file] [log] [blame]
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +02001/*
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +01002 * Copyright (C) 2009-2011, Frederic Weisbecker <fweisbec@gmail.com>
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +02003 *
4 * Handle the callchains from the stream in an ad-hoc radix tree and then
5 * sort them in an rbtree.
6 *
Frederic Weisbeckerdeac9112009-07-01 05:35:15 +02007 * Using a radix for code path provides a fast retrieval and factorizes
8 * memory use. Also that lets us use the paths in a hierarchical graph view.
9 *
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +020010 */
11
12#include <stdlib.h>
13#include <stdio.h>
14#include <stdbool.h>
15#include <errno.h>
Frederic Weisbeckerc0a88652009-08-09 04:19:15 +020016#include <math.h>
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +020017
Frederic Weisbeckerb965bb42014-01-14 16:37:15 +010018#include "asm/bug.h"
19
Andi Kleen99571ab2013-07-18 15:33:57 -070020#include "hist.h"
Arnaldo Carvalho de Melob36f19d2010-05-20 12:15:33 -030021#include "util.h"
Namhyung Kim2dc9fb12014-01-14 14:25:35 +090022#include "sort.h"
23#include "machine.h"
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +020024#include "callchain.h"
25
Namhyung Kim47260642012-05-31 14:43:26 +090026__thread struct callchain_cursor callchain_cursor;
27
Kan Liangc3a6a8c2015-08-04 04:30:20 -040028int parse_callchain_record_opt(const char *arg, struct callchain_param *param)
Namhyung Kimf7f084f2014-09-23 10:01:42 +090029{
Kan Liang076a30c2015-08-06 15:44:52 -040030 return parse_callchain_record(arg, param);
Namhyung Kimf7f084f2014-09-23 10:01:42 +090031}
32
Namhyung Kim2b9240c2014-09-23 10:01:43 +090033static int parse_callchain_mode(const char *value)
34{
35 if (!strncmp(value, "graph", strlen(value))) {
36 callchain_param.mode = CHAIN_GRAPH_ABS;
37 return 0;
38 }
39 if (!strncmp(value, "flat", strlen(value))) {
40 callchain_param.mode = CHAIN_FLAT;
41 return 0;
42 }
43 if (!strncmp(value, "fractal", strlen(value))) {
44 callchain_param.mode = CHAIN_GRAPH_REL;
45 return 0;
46 }
Namhyung Kim26e77922015-11-09 14:45:37 +090047 if (!strncmp(value, "folded", strlen(value))) {
48 callchain_param.mode = CHAIN_FOLDED;
49 return 0;
50 }
Namhyung Kim2b9240c2014-09-23 10:01:43 +090051 return -1;
52}
53
54static int parse_callchain_order(const char *value)
55{
56 if (!strncmp(value, "caller", strlen(value))) {
57 callchain_param.order = ORDER_CALLER;
Namhyung Kim792aeaf2015-10-22 16:45:46 +090058 callchain_param.order_set = true;
Namhyung Kim2b9240c2014-09-23 10:01:43 +090059 return 0;
60 }
61 if (!strncmp(value, "callee", strlen(value))) {
62 callchain_param.order = ORDER_CALLEE;
Namhyung Kim792aeaf2015-10-22 16:45:46 +090063 callchain_param.order_set = true;
Namhyung Kim2b9240c2014-09-23 10:01:43 +090064 return 0;
65 }
66 return -1;
67}
68
69static int parse_callchain_sort_key(const char *value)
70{
71 if (!strncmp(value, "function", strlen(value))) {
72 callchain_param.key = CCKEY_FUNCTION;
73 return 0;
74 }
75 if (!strncmp(value, "address", strlen(value))) {
76 callchain_param.key = CCKEY_ADDRESS;
77 return 0;
78 }
Andi Kleen8b7bad52014-11-12 18:05:20 -080079 if (!strncmp(value, "branch", strlen(value))) {
80 callchain_param.branch_callstack = 1;
81 return 0;
82 }
Namhyung Kim2b9240c2014-09-23 10:01:43 +090083 return -1;
84}
85
Namhyung Kimf2af0082015-11-09 14:45:41 +090086static int parse_callchain_value(const char *value)
87{
88 if (!strncmp(value, "percent", strlen(value))) {
89 callchain_param.value = CCVAL_PERCENT;
90 return 0;
91 }
92 if (!strncmp(value, "period", strlen(value))) {
93 callchain_param.value = CCVAL_PERIOD;
94 return 0;
95 }
96 if (!strncmp(value, "count", strlen(value))) {
97 callchain_param.value = CCVAL_COUNT;
98 return 0;
99 }
100 return -1;
101}
102
Namhyung Kima2c10d32015-10-22 15:28:49 +0900103static int
104__parse_callchain_report_opt(const char *arg, bool allow_record_opt)
Don Zickuscff6bb42014-04-07 14:55:24 -0400105{
Namhyung Kime8232f12014-08-14 15:01:38 +0900106 char *tok;
Don Zickuscff6bb42014-04-07 14:55:24 -0400107 char *endptr;
Namhyung Kime8232f12014-08-14 15:01:38 +0900108 bool minpcnt_set = false;
Namhyung Kima2c10d32015-10-22 15:28:49 +0900109 bool record_opt_set = false;
110 bool try_stack_size = false;
Don Zickuscff6bb42014-04-07 14:55:24 -0400111
112 symbol_conf.use_callchain = true;
113
114 if (!arg)
115 return 0;
116
Namhyung Kime8232f12014-08-14 15:01:38 +0900117 while ((tok = strtok((char *)arg, ",")) != NULL) {
118 if (!strncmp(tok, "none", strlen(tok))) {
119 callchain_param.mode = CHAIN_NONE;
120 symbol_conf.use_callchain = false;
121 return 0;
122 }
Don Zickuscff6bb42014-04-07 14:55:24 -0400123
Namhyung Kim2b9240c2014-09-23 10:01:43 +0900124 if (!parse_callchain_mode(tok) ||
125 !parse_callchain_order(tok) ||
Namhyung Kimf2af0082015-11-09 14:45:41 +0900126 !parse_callchain_sort_key(tok) ||
127 !parse_callchain_value(tok)) {
Namhyung Kim2b9240c2014-09-23 10:01:43 +0900128 /* parsing ok - move on to the next */
Namhyung Kima2c10d32015-10-22 15:28:49 +0900129 try_stack_size = false;
130 goto next;
131 } else if (allow_record_opt && !record_opt_set) {
132 if (parse_callchain_record(tok, &callchain_param))
133 goto try_numbers;
134
135 /* assume that number followed by 'dwarf' is stack size */
136 if (callchain_param.record_mode == CALLCHAIN_DWARF)
137 try_stack_size = true;
138
139 record_opt_set = true;
140 goto next;
141 }
142
143try_numbers:
144 if (try_stack_size) {
145 unsigned long size = 0;
146
147 if (get_stack_size(tok, &size) < 0)
148 return -1;
149 callchain_param.dump_size = size;
150 try_stack_size = false;
Namhyung Kim2b9240c2014-09-23 10:01:43 +0900151 } else if (!minpcnt_set) {
152 /* try to get the min percent */
Namhyung Kime8232f12014-08-14 15:01:38 +0900153 callchain_param.min_percent = strtod(tok, &endptr);
154 if (tok == endptr)
155 return -1;
156 minpcnt_set = true;
157 } else {
158 /* try print limit at last */
159 callchain_param.print_limit = strtoul(tok, &endptr, 0);
160 if (tok == endptr)
161 return -1;
162 }
Namhyung Kima2c10d32015-10-22 15:28:49 +0900163next:
Namhyung Kime8232f12014-08-14 15:01:38 +0900164 arg = NULL;
Don Zickuscff6bb42014-04-07 14:55:24 -0400165 }
166
Don Zickuscff6bb42014-04-07 14:55:24 -0400167 if (callchain_register_param(&callchain_param) < 0) {
168 pr_err("Can't register callchain params\n");
169 return -1;
170 }
171 return 0;
172}
173
Namhyung Kima2c10d32015-10-22 15:28:49 +0900174int parse_callchain_report_opt(const char *arg)
175{
176 return __parse_callchain_report_opt(arg, false);
177}
178
179int parse_callchain_top_opt(const char *arg)
180{
181 return __parse_callchain_report_opt(arg, true);
182}
183
Namhyung Kim2b9240c2014-09-23 10:01:43 +0900184int perf_callchain_config(const char *var, const char *value)
185{
186 char *endptr;
187
188 if (prefixcmp(var, "call-graph."))
189 return 0;
190 var += sizeof("call-graph.") - 1;
191
192 if (!strcmp(var, "record-mode"))
Kan Liangc3a6a8c2015-08-04 04:30:20 -0400193 return parse_callchain_record_opt(value, &callchain_param);
Namhyung Kim2b9240c2014-09-23 10:01:43 +0900194#ifdef HAVE_DWARF_UNWIND_SUPPORT
195 if (!strcmp(var, "dump-size")) {
196 unsigned long size = 0;
197 int ret;
198
199 ret = get_stack_size(value, &size);
200 callchain_param.dump_size = size;
201
202 return ret;
203 }
204#endif
205 if (!strcmp(var, "print-type"))
206 return parse_callchain_mode(value);
207 if (!strcmp(var, "order"))
208 return parse_callchain_order(value);
209 if (!strcmp(var, "sort-key"))
210 return parse_callchain_sort_key(value);
211 if (!strcmp(var, "threshold")) {
212 callchain_param.min_percent = strtod(value, &endptr);
213 if (value == endptr)
214 return -1;
215 }
216 if (!strcmp(var, "print-limit")) {
217 callchain_param.print_limit = strtod(value, &endptr);
218 if (value == endptr)
219 return -1;
220 }
221
222 return 0;
223}
224
Frederic Weisbeckerdeac9112009-07-01 05:35:15 +0200225static void
Frederic Weisbecker4eb3e472009-07-02 17:58:21 +0200226rb_insert_callchain(struct rb_root *root, struct callchain_node *chain,
227 enum chain_mode mode)
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200228{
229 struct rb_node **p = &root->rb_node;
230 struct rb_node *parent = NULL;
231 struct callchain_node *rnode;
Frederic Weisbeckerf08c3152011-01-14 04:51:59 +0100232 u64 chain_cumul = callchain_cumul_hits(chain);
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200233
234 while (*p) {
Frederic Weisbecker19532872009-08-07 07:11:05 +0200235 u64 rnode_cumul;
236
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200237 parent = *p;
238 rnode = rb_entry(parent, struct callchain_node, rb_node);
Frederic Weisbeckerf08c3152011-01-14 04:51:59 +0100239 rnode_cumul = callchain_cumul_hits(rnode);
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200240
Frederic Weisbecker4eb3e472009-07-02 17:58:21 +0200241 switch (mode) {
Frederic Weisbecker805d1272009-07-05 07:39:21 +0200242 case CHAIN_FLAT:
Namhyung Kim26e77922015-11-09 14:45:37 +0900243 case CHAIN_FOLDED:
Frederic Weisbecker4eb3e472009-07-02 17:58:21 +0200244 if (rnode->hit < chain->hit)
245 p = &(*p)->rb_left;
246 else
247 p = &(*p)->rb_right;
248 break;
Frederic Weisbecker805d1272009-07-05 07:39:21 +0200249 case CHAIN_GRAPH_ABS: /* Falldown */
250 case CHAIN_GRAPH_REL:
Frederic Weisbecker19532872009-08-07 07:11:05 +0200251 if (rnode_cumul < chain_cumul)
Frederic Weisbecker4eb3e472009-07-02 17:58:21 +0200252 p = &(*p)->rb_left;
253 else
254 p = &(*p)->rb_right;
255 break;
Ingo Molnar83a09442009-08-15 12:26:57 +0200256 case CHAIN_NONE:
Frederic Weisbecker4eb3e472009-07-02 17:58:21 +0200257 default:
258 break;
259 }
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200260 }
261
262 rb_link_node(&chain->rb_node, parent, p);
263 rb_insert_color(&chain->rb_node, root);
264}
265
Frederic Weisbecker805d1272009-07-05 07:39:21 +0200266static void
267__sort_chain_flat(struct rb_root *rb_root, struct callchain_node *node,
268 u64 min_hit)
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200269{
Namhyung Kime3695172013-10-11 14:15:36 +0900270 struct rb_node *n;
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200271 struct callchain_node *child;
272
Namhyung Kime3695172013-10-11 14:15:36 +0900273 n = rb_first(&node->rb_root_in);
274 while (n) {
275 child = rb_entry(n, struct callchain_node, rb_node_in);
276 n = rb_next(n);
277
Frederic Weisbecker805d1272009-07-05 07:39:21 +0200278 __sort_chain_flat(rb_root, child, min_hit);
Namhyung Kime3695172013-10-11 14:15:36 +0900279 }
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200280
Frederic Weisbeckerc20ab372009-07-02 20:14:33 +0200281 if (node->hit && node->hit >= min_hit)
Frederic Weisbecker805d1272009-07-05 07:39:21 +0200282 rb_insert_callchain(rb_root, node, CHAIN_FLAT);
Frederic Weisbecker4eb3e472009-07-02 17:58:21 +0200283}
284
Frederic Weisbecker805d1272009-07-05 07:39:21 +0200285/*
286 * Once we get every callchains from the stream, we can now
287 * sort them by hit
288 */
289static void
Frederic Weisbeckerd2009c52010-08-22 20:05:22 +0200290sort_chain_flat(struct rb_root *rb_root, struct callchain_root *root,
Irina Tirdea1d037ca2012-09-11 01:15:03 +0300291 u64 min_hit, struct callchain_param *param __maybe_unused)
Frederic Weisbecker805d1272009-07-05 07:39:21 +0200292{
Namhyung Kim03562182015-11-26 16:08:18 +0900293 *rb_root = RB_ROOT;
Frederic Weisbeckerd2009c52010-08-22 20:05:22 +0200294 __sort_chain_flat(rb_root, &root->node, min_hit);
Frederic Weisbecker805d1272009-07-05 07:39:21 +0200295}
296
297static void __sort_chain_graph_abs(struct callchain_node *node,
298 u64 min_hit)
Frederic Weisbecker4eb3e472009-07-02 17:58:21 +0200299{
Namhyung Kime3695172013-10-11 14:15:36 +0900300 struct rb_node *n;
Frederic Weisbecker4eb3e472009-07-02 17:58:21 +0200301 struct callchain_node *child;
302
303 node->rb_root = RB_ROOT;
Namhyung Kime3695172013-10-11 14:15:36 +0900304 n = rb_first(&node->rb_root_in);
Frederic Weisbecker4eb3e472009-07-02 17:58:21 +0200305
Namhyung Kime3695172013-10-11 14:15:36 +0900306 while (n) {
307 child = rb_entry(n, struct callchain_node, rb_node_in);
308 n = rb_next(n);
309
Frederic Weisbecker805d1272009-07-05 07:39:21 +0200310 __sort_chain_graph_abs(child, min_hit);
Frederic Weisbeckerf08c3152011-01-14 04:51:59 +0100311 if (callchain_cumul_hits(child) >= min_hit)
Frederic Weisbecker805d1272009-07-05 07:39:21 +0200312 rb_insert_callchain(&node->rb_root, child,
313 CHAIN_GRAPH_ABS);
Frederic Weisbecker4eb3e472009-07-02 17:58:21 +0200314 }
315}
316
Frederic Weisbecker805d1272009-07-05 07:39:21 +0200317static void
Frederic Weisbeckerd2009c52010-08-22 20:05:22 +0200318sort_chain_graph_abs(struct rb_root *rb_root, struct callchain_root *chain_root,
Irina Tirdea1d037ca2012-09-11 01:15:03 +0300319 u64 min_hit, struct callchain_param *param __maybe_unused)
Frederic Weisbecker4eb3e472009-07-02 17:58:21 +0200320{
Frederic Weisbeckerd2009c52010-08-22 20:05:22 +0200321 __sort_chain_graph_abs(&chain_root->node, min_hit);
322 rb_root->rb_node = chain_root->node.rb_root.rb_node;
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200323}
324
Frederic Weisbecker805d1272009-07-05 07:39:21 +0200325static void __sort_chain_graph_rel(struct callchain_node *node,
326 double min_percent)
327{
Namhyung Kime3695172013-10-11 14:15:36 +0900328 struct rb_node *n;
Frederic Weisbecker805d1272009-07-05 07:39:21 +0200329 struct callchain_node *child;
330 u64 min_hit;
331
332 node->rb_root = RB_ROOT;
Frederic Weisbeckerc0a88652009-08-09 04:19:15 +0200333 min_hit = ceil(node->children_hit * min_percent);
Frederic Weisbecker805d1272009-07-05 07:39:21 +0200334
Namhyung Kime3695172013-10-11 14:15:36 +0900335 n = rb_first(&node->rb_root_in);
336 while (n) {
337 child = rb_entry(n, struct callchain_node, rb_node_in);
338 n = rb_next(n);
339
Frederic Weisbecker805d1272009-07-05 07:39:21 +0200340 __sort_chain_graph_rel(child, min_percent);
Frederic Weisbeckerf08c3152011-01-14 04:51:59 +0100341 if (callchain_cumul_hits(child) >= min_hit)
Frederic Weisbecker805d1272009-07-05 07:39:21 +0200342 rb_insert_callchain(&node->rb_root, child,
343 CHAIN_GRAPH_REL);
344 }
345}
346
347static void
Frederic Weisbeckerd2009c52010-08-22 20:05:22 +0200348sort_chain_graph_rel(struct rb_root *rb_root, struct callchain_root *chain_root,
Irina Tirdea1d037ca2012-09-11 01:15:03 +0300349 u64 min_hit __maybe_unused, struct callchain_param *param)
Frederic Weisbecker805d1272009-07-05 07:39:21 +0200350{
Frederic Weisbeckerd2009c52010-08-22 20:05:22 +0200351 __sort_chain_graph_rel(&chain_root->node, param->min_percent / 100.0);
352 rb_root->rb_node = chain_root->node.rb_root.rb_node;
Frederic Weisbecker805d1272009-07-05 07:39:21 +0200353}
354
Frederic Weisbecker16537f12011-01-14 04:52:00 +0100355int callchain_register_param(struct callchain_param *param)
Frederic Weisbecker805d1272009-07-05 07:39:21 +0200356{
357 switch (param->mode) {
358 case CHAIN_GRAPH_ABS:
359 param->sort = sort_chain_graph_abs;
360 break;
361 case CHAIN_GRAPH_REL:
362 param->sort = sort_chain_graph_rel;
363 break;
364 case CHAIN_FLAT:
Namhyung Kim26e77922015-11-09 14:45:37 +0900365 case CHAIN_FOLDED:
Frederic Weisbecker805d1272009-07-05 07:39:21 +0200366 param->sort = sort_chain_flat;
367 break;
Ingo Molnar83a09442009-08-15 12:26:57 +0200368 case CHAIN_NONE:
Frederic Weisbecker805d1272009-07-05 07:39:21 +0200369 default:
370 return -1;
371 }
372 return 0;
373}
374
Frederic Weisbeckerdeac9112009-07-01 05:35:15 +0200375/*
376 * Create a child for a parent. If inherit_children, then the new child
377 * will become the new parent of it's parent children
378 */
379static struct callchain_node *
380create_child(struct callchain_node *parent, bool inherit_children)
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200381{
382 struct callchain_node *new;
383
Arnaldo Carvalho de Melocdd5b75b2010-05-10 10:56:50 -0300384 new = zalloc(sizeof(*new));
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200385 if (!new) {
386 perror("not enough memory to create child for code path tree");
387 return NULL;
388 }
389 new->parent = parent;
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200390 INIT_LIST_HEAD(&new->val);
Namhyung Kim4b3a3212015-11-09 14:45:43 +0900391 INIT_LIST_HEAD(&new->parent_val);
Frederic Weisbeckerdeac9112009-07-01 05:35:15 +0200392
393 if (inherit_children) {
Namhyung Kime3695172013-10-11 14:15:36 +0900394 struct rb_node *n;
395 struct callchain_node *child;
Frederic Weisbeckerdeac9112009-07-01 05:35:15 +0200396
Namhyung Kime3695172013-10-11 14:15:36 +0900397 new->rb_root_in = parent->rb_root_in;
398 parent->rb_root_in = RB_ROOT;
Frederic Weisbeckerdeac9112009-07-01 05:35:15 +0200399
Namhyung Kime3695172013-10-11 14:15:36 +0900400 n = rb_first(&new->rb_root_in);
401 while (n) {
402 child = rb_entry(n, struct callchain_node, rb_node_in);
403 child->parent = new;
404 n = rb_next(n);
405 }
406
407 /* make it the first child */
408 rb_link_node(&new->rb_node_in, NULL, &parent->rb_root_in.rb_node);
409 rb_insert_color(&new->rb_node_in, &parent->rb_root_in);
Frederic Weisbeckerdeac9112009-07-01 05:35:15 +0200410 }
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200411
412 return new;
413}
414
Frederic Weisbecker301fde22010-03-22 13:09:33 -0300415
Frederic Weisbeckerdeac9112009-07-01 05:35:15 +0200416/*
417 * Fill the node with callchain values
418 */
Namhyung Kim8451cbb2016-02-16 23:08:21 +0900419static int
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100420fill_node(struct callchain_node *node, struct callchain_cursor *cursor)
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200421{
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100422 struct callchain_cursor_node *cursor_node;
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200423
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100424 node->val_nr = cursor->nr - cursor->pos;
425 if (!node->val_nr)
426 pr_warning("Warning: empty node in callchain tree\n");
427
428 cursor_node = callchain_cursor_current(cursor);
429
430 while (cursor_node) {
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200431 struct callchain_list *call;
432
Arnaldo Carvalho de Melocdd5b75b2010-05-10 10:56:50 -0300433 call = zalloc(sizeof(*call));
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200434 if (!call) {
435 perror("not enough memory for the code path tree");
Namhyung Kim8451cbb2016-02-16 23:08:21 +0900436 return -1;
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200437 }
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100438 call->ip = cursor_node->ip;
439 call->ms.sym = cursor_node->sym;
440 call->ms.map = cursor_node->map;
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200441 list_add_tail(&call->list, &node->val);
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100442
443 callchain_cursor_advance(cursor);
444 cursor_node = callchain_cursor_current(cursor);
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200445 }
Namhyung Kim8451cbb2016-02-16 23:08:21 +0900446 return 0;
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200447}
448
Namhyung Kime3695172013-10-11 14:15:36 +0900449static struct callchain_node *
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100450add_child(struct callchain_node *parent,
451 struct callchain_cursor *cursor,
452 u64 period)
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200453{
454 struct callchain_node *new;
455
Frederic Weisbeckerdeac9112009-07-01 05:35:15 +0200456 new = create_child(parent, false);
Namhyung Kim7565bd32016-02-16 23:08:20 +0900457 if (new == NULL)
458 return NULL;
459
Namhyung Kim8451cbb2016-02-16 23:08:21 +0900460 if (fill_node(new, cursor) < 0) {
461 struct callchain_list *call, *tmp;
462
463 list_for_each_entry_safe(call, tmp, &new->val, list) {
464 list_del(&call->list);
465 free(call);
466 }
467 free(new);
468 return NULL;
469 }
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200470
Frederic Weisbecker19532872009-08-07 07:11:05 +0200471 new->children_hit = 0;
Frederic Weisbecker108553e2010-07-08 03:41:46 +0200472 new->hit = period;
Namhyung Kim5e47f8f2015-11-09 14:45:40 +0900473 new->children_count = 0;
474 new->count = 1;
Namhyung Kime3695172013-10-11 14:15:36 +0900475 return new;
476}
477
Namhyung Kim2d713b82016-02-16 23:08:22 +0900478enum match_result {
479 MATCH_ERROR = -1,
480 MATCH_EQ,
481 MATCH_LT,
482 MATCH_GT,
483};
484
485static enum match_result match_chain(struct callchain_cursor_node *node,
486 struct callchain_list *cnode)
Namhyung Kime3695172013-10-11 14:15:36 +0900487{
488 struct symbol *sym = node->sym;
Namhyung Kim2d713b82016-02-16 23:08:22 +0900489 u64 left, right;
Namhyung Kime3695172013-10-11 14:15:36 +0900490
491 if (cnode->ms.sym && sym &&
Namhyung Kim2d713b82016-02-16 23:08:22 +0900492 callchain_param.key == CCKEY_FUNCTION) {
493 left = cnode->ms.sym->start;
494 right = sym->start;
495 } else {
496 left = cnode->ip;
497 right = node->ip;
498 }
499
500 if (left == right)
501 return MATCH_EQ;
502
503 return left > right ? MATCH_GT : MATCH_LT;
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200504}
505
Frederic Weisbeckerdeac9112009-07-01 05:35:15 +0200506/*
507 * Split the parent in two parts (a new child is created) and
508 * give a part of its callchain to the created child.
509 * Then create another child to host the given callchain of new branch
510 */
Namhyung Kimf2bb4c52016-02-16 23:08:23 +0900511static int
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100512split_add_child(struct callchain_node *parent,
513 struct callchain_cursor *cursor,
514 struct callchain_list *to_split,
515 u64 idx_parents, u64 idx_local, u64 period)
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200516{
517 struct callchain_node *new;
Frederic Weisbeckerdeac9112009-07-01 05:35:15 +0200518 struct list_head *old_tail;
Ingo Molnarf37a2912009-07-01 12:37:06 +0200519 unsigned int idx_total = idx_parents + idx_local;
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200520
521 /* split */
Frederic Weisbeckerdeac9112009-07-01 05:35:15 +0200522 new = create_child(parent, true);
Namhyung Kimf2bb4c52016-02-16 23:08:23 +0900523 if (new == NULL)
524 return -1;
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200525
Frederic Weisbeckerdeac9112009-07-01 05:35:15 +0200526 /* split the callchain and move a part to the new child */
527 old_tail = parent->val.prev;
528 list_del_range(&to_split->list, old_tail);
529 new->val.next = &to_split->list;
530 new->val.prev = old_tail;
531 to_split->list.prev = &new->val;
532 old_tail->next = &new->val;
533
534 /* split the hits */
535 new->hit = parent->hit;
Frederic Weisbecker19532872009-08-07 07:11:05 +0200536 new->children_hit = parent->children_hit;
Frederic Weisbeckerf08c3152011-01-14 04:51:59 +0100537 parent->children_hit = callchain_cumul_hits(new);
Frederic Weisbeckerdeac9112009-07-01 05:35:15 +0200538 new->val_nr = parent->val_nr - idx_local;
539 parent->val_nr = idx_local;
Namhyung Kim5e47f8f2015-11-09 14:45:40 +0900540 new->count = parent->count;
541 new->children_count = parent->children_count;
542 parent->children_count = callchain_cumul_counts(new);
Frederic Weisbeckerdeac9112009-07-01 05:35:15 +0200543
544 /* create a new child for the new branch if any */
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100545 if (idx_total < cursor->nr) {
Namhyung Kime3695172013-10-11 14:15:36 +0900546 struct callchain_node *first;
547 struct callchain_list *cnode;
548 struct callchain_cursor_node *node;
549 struct rb_node *p, **pp;
550
Frederic Weisbeckerdeac9112009-07-01 05:35:15 +0200551 parent->hit = 0;
Frederic Weisbecker108553e2010-07-08 03:41:46 +0200552 parent->children_hit += period;
Namhyung Kim5e47f8f2015-11-09 14:45:40 +0900553 parent->count = 0;
554 parent->children_count += 1;
Namhyung Kime3695172013-10-11 14:15:36 +0900555
556 node = callchain_cursor_current(cursor);
557 new = add_child(parent, cursor, period);
Namhyung Kim7565bd32016-02-16 23:08:20 +0900558 if (new == NULL)
Namhyung Kimf2bb4c52016-02-16 23:08:23 +0900559 return -1;
Namhyung Kime3695172013-10-11 14:15:36 +0900560
561 /*
562 * This is second child since we moved parent's children
563 * to new (first) child above.
564 */
565 p = parent->rb_root_in.rb_node;
566 first = rb_entry(p, struct callchain_node, rb_node_in);
567 cnode = list_first_entry(&first->val, struct callchain_list,
568 list);
569
Namhyung Kim2d713b82016-02-16 23:08:22 +0900570 if (match_chain(node, cnode) == MATCH_LT)
Namhyung Kime3695172013-10-11 14:15:36 +0900571 pp = &p->rb_left;
572 else
573 pp = &p->rb_right;
574
575 rb_link_node(&new->rb_node_in, p, pp);
576 rb_insert_color(&new->rb_node_in, &parent->rb_root_in);
Frederic Weisbeckerdeac9112009-07-01 05:35:15 +0200577 } else {
Frederic Weisbecker108553e2010-07-08 03:41:46 +0200578 parent->hit = period;
Namhyung Kim5e47f8f2015-11-09 14:45:40 +0900579 parent->count = 1;
Frederic Weisbeckerdeac9112009-07-01 05:35:15 +0200580 }
Namhyung Kimf2bb4c52016-02-16 23:08:23 +0900581 return 0;
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200582}
583
Namhyung Kim2d713b82016-02-16 23:08:22 +0900584static enum match_result
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100585append_chain(struct callchain_node *root,
586 struct callchain_cursor *cursor,
587 u64 period);
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200588
Namhyung Kimdca0d122016-02-16 23:08:24 +0900589static int
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100590append_chain_children(struct callchain_node *root,
591 struct callchain_cursor *cursor,
592 u64 period)
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200593{
594 struct callchain_node *rnode;
Namhyung Kime3695172013-10-11 14:15:36 +0900595 struct callchain_cursor_node *node;
596 struct rb_node **p = &root->rb_root_in.rb_node;
597 struct rb_node *parent = NULL;
598
599 node = callchain_cursor_current(cursor);
600 if (!node)
Namhyung Kimdca0d122016-02-16 23:08:24 +0900601 return -1;
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200602
603 /* lookup in childrens */
Namhyung Kime3695172013-10-11 14:15:36 +0900604 while (*p) {
Namhyung Kim2d713b82016-02-16 23:08:22 +0900605 enum match_result ret;
Ingo Molnarf37a2912009-07-01 12:37:06 +0200606
Namhyung Kime3695172013-10-11 14:15:36 +0900607 parent = *p;
608 rnode = rb_entry(parent, struct callchain_node, rb_node_in);
Namhyung Kime3695172013-10-11 14:15:36 +0900609
Frederic Weisbeckerb965bb42014-01-14 16:37:15 +0100610 /* If at least first entry matches, rely to children */
611 ret = append_chain(rnode, cursor, period);
Namhyung Kim2d713b82016-02-16 23:08:22 +0900612 if (ret == MATCH_EQ)
Frederic Weisbecker19532872009-08-07 07:11:05 +0200613 goto inc_children_hit;
Namhyung Kimdca0d122016-02-16 23:08:24 +0900614 if (ret == MATCH_ERROR)
615 return -1;
Namhyung Kime3695172013-10-11 14:15:36 +0900616
Namhyung Kim2d713b82016-02-16 23:08:22 +0900617 if (ret == MATCH_LT)
Namhyung Kime3695172013-10-11 14:15:36 +0900618 p = &parent->rb_left;
619 else
620 p = &parent->rb_right;
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200621 }
Frederic Weisbeckerdeac9112009-07-01 05:35:15 +0200622 /* nothing in children, add to the current node */
Namhyung Kime3695172013-10-11 14:15:36 +0900623 rnode = add_child(root, cursor, period);
Namhyung Kim7565bd32016-02-16 23:08:20 +0900624 if (rnode == NULL)
Namhyung Kimdca0d122016-02-16 23:08:24 +0900625 return -1;
Namhyung Kim7565bd32016-02-16 23:08:20 +0900626
Namhyung Kime3695172013-10-11 14:15:36 +0900627 rb_link_node(&rnode->rb_node_in, parent, p);
628 rb_insert_color(&rnode->rb_node_in, &root->rb_root_in);
Frederic Weisbeckere05b8762009-07-05 07:39:20 +0200629
Frederic Weisbecker19532872009-08-07 07:11:05 +0200630inc_children_hit:
Frederic Weisbecker108553e2010-07-08 03:41:46 +0200631 root->children_hit += period;
Namhyung Kim5e47f8f2015-11-09 14:45:40 +0900632 root->children_count++;
Namhyung Kimdca0d122016-02-16 23:08:24 +0900633 return 0;
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200634}
635
Namhyung Kim2d713b82016-02-16 23:08:22 +0900636static enum match_result
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100637append_chain(struct callchain_node *root,
638 struct callchain_cursor *cursor,
639 u64 period)
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200640{
641 struct callchain_list *cnode;
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100642 u64 start = cursor->pos;
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200643 bool found = false;
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100644 u64 matches;
Namhyung Kim2d713b82016-02-16 23:08:22 +0900645 enum match_result cmp = MATCH_ERROR;
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200646
Frederic Weisbeckerdeac9112009-07-01 05:35:15 +0200647 /*
648 * Lookup in the current node
649 * If we have a symbol, then compare the start to match
Andi Kleen99571ab2013-07-18 15:33:57 -0700650 * anywhere inside a function, unless function
651 * mode is disabled.
Frederic Weisbeckerdeac9112009-07-01 05:35:15 +0200652 */
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200653 list_for_each_entry(cnode, &root->val, list) {
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100654 struct callchain_cursor_node *node;
Frederic Weisbecker301fde22010-03-22 13:09:33 -0300655
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100656 node = callchain_cursor_current(cursor);
657 if (!node)
Frederic Weisbeckerdeac9112009-07-01 05:35:15 +0200658 break;
Frederic Weisbecker301fde22010-03-22 13:09:33 -0300659
Frederic Weisbeckerb965bb42014-01-14 16:37:15 +0100660 cmp = match_chain(node, cnode);
Namhyung Kim2d713b82016-02-16 23:08:22 +0900661 if (cmp != MATCH_EQ)
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200662 break;
Frederic Weisbecker301fde22010-03-22 13:09:33 -0300663
Namhyung Kime3695172013-10-11 14:15:36 +0900664 found = true;
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100665
666 callchain_cursor_advance(cursor);
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200667 }
668
Namhyung Kime3695172013-10-11 14:15:36 +0900669 /* matches not, relay no the parent */
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100670 if (!found) {
Namhyung Kim2d713b82016-02-16 23:08:22 +0900671 WARN_ONCE(cmp == MATCH_ERROR, "Chain comparison error\n");
Frederic Weisbeckerb965bb42014-01-14 16:37:15 +0100672 return cmp;
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100673 }
674
675 matches = cursor->pos - start;
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200676
677 /* we match only a part of the node. Split it and add the new chain */
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100678 if (matches < root->val_nr) {
Namhyung Kimf2bb4c52016-02-16 23:08:23 +0900679 if (split_add_child(root, cursor, cnode, start, matches,
680 period) < 0)
681 return MATCH_ERROR;
682
Namhyung Kim2d713b82016-02-16 23:08:22 +0900683 return MATCH_EQ;
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200684 }
685
686 /* we match 100% of the path, increment the hit */
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100687 if (matches == root->val_nr && cursor->pos == cursor->nr) {
Frederic Weisbecker108553e2010-07-08 03:41:46 +0200688 root->hit += period;
Namhyung Kim5e47f8f2015-11-09 14:45:40 +0900689 root->count++;
Namhyung Kim2d713b82016-02-16 23:08:22 +0900690 return MATCH_EQ;
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200691 }
692
Frederic Weisbeckerdeac9112009-07-01 05:35:15 +0200693 /* We match the node and still have a part remaining */
Namhyung Kimdca0d122016-02-16 23:08:24 +0900694 if (append_chain_children(root, cursor, period) < 0)
695 return MATCH_ERROR;
Frederic Weisbeckerdeac9112009-07-01 05:35:15 +0200696
Namhyung Kim2d713b82016-02-16 23:08:22 +0900697 return MATCH_EQ;
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200698}
699
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100700int callchain_append(struct callchain_root *root,
701 struct callchain_cursor *cursor,
702 u64 period)
Frederic Weisbecker301fde22010-03-22 13:09:33 -0300703{
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100704 if (!cursor->nr)
Frederic Weisbecker301fde22010-03-22 13:09:33 -0300705 return 0;
706
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100707 callchain_cursor_commit(cursor);
Frederic Weisbecker301fde22010-03-22 13:09:33 -0300708
Namhyung Kimdca0d122016-02-16 23:08:24 +0900709 if (append_chain_children(&root->node, cursor, period) < 0)
710 return -1;
Frederic Weisbecker301fde22010-03-22 13:09:33 -0300711
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100712 if (cursor->nr > root->max_depth)
713 root->max_depth = cursor->nr;
Frederic Weisbecker301fde22010-03-22 13:09:33 -0300714
715 return 0;
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200716}
Frederic Weisbecker612d4fd2010-08-22 21:10:35 +0200717
718static int
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100719merge_chain_branch(struct callchain_cursor *cursor,
720 struct callchain_node *dst, struct callchain_node *src)
Frederic Weisbecker612d4fd2010-08-22 21:10:35 +0200721{
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100722 struct callchain_cursor_node **old_last = cursor->last;
Namhyung Kime3695172013-10-11 14:15:36 +0900723 struct callchain_node *child;
Frederic Weisbecker612d4fd2010-08-22 21:10:35 +0200724 struct callchain_list *list, *next_list;
Namhyung Kime3695172013-10-11 14:15:36 +0900725 struct rb_node *n;
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100726 int old_pos = cursor->nr;
Frederic Weisbecker612d4fd2010-08-22 21:10:35 +0200727 int err = 0;
728
729 list_for_each_entry_safe(list, next_list, &src->val, list) {
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100730 callchain_cursor_append(cursor, list->ip,
731 list->ms.map, list->ms.sym);
Frederic Weisbecker612d4fd2010-08-22 21:10:35 +0200732 list_del(&list->list);
733 free(list);
734 }
735
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100736 if (src->hit) {
737 callchain_cursor_commit(cursor);
Namhyung Kimdca0d122016-02-16 23:08:24 +0900738 if (append_chain_children(dst, cursor, src->hit) < 0)
739 return -1;
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100740 }
Frederic Weisbecker612d4fd2010-08-22 21:10:35 +0200741
Namhyung Kime3695172013-10-11 14:15:36 +0900742 n = rb_first(&src->rb_root_in);
743 while (n) {
744 child = container_of(n, struct callchain_node, rb_node_in);
745 n = rb_next(n);
746 rb_erase(&child->rb_node_in, &src->rb_root_in);
747
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100748 err = merge_chain_branch(cursor, dst, child);
Frederic Weisbecker612d4fd2010-08-22 21:10:35 +0200749 if (err)
750 break;
751
Frederic Weisbecker612d4fd2010-08-22 21:10:35 +0200752 free(child);
753 }
754
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100755 cursor->nr = old_pos;
756 cursor->last = old_last;
Frederic Weisbecker612d4fd2010-08-22 21:10:35 +0200757
758 return err;
759}
760
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100761int callchain_merge(struct callchain_cursor *cursor,
762 struct callchain_root *dst, struct callchain_root *src)
Frederic Weisbecker612d4fd2010-08-22 21:10:35 +0200763{
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100764 return merge_chain_branch(cursor, &dst->node, &src->node);
765}
Frederic Weisbecker612d4fd2010-08-22 21:10:35 +0200766
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100767int callchain_cursor_append(struct callchain_cursor *cursor,
768 u64 ip, struct map *map, struct symbol *sym)
769{
770 struct callchain_cursor_node *node = *cursor->last;
Frederic Weisbecker612d4fd2010-08-22 21:10:35 +0200771
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100772 if (!node) {
Paul Gortmaker91b98802013-01-30 20:05:49 -0500773 node = calloc(1, sizeof(*node));
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100774 if (!node)
775 return -ENOMEM;
Frederic Weisbecker612d4fd2010-08-22 21:10:35 +0200776
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100777 *cursor->last = node;
778 }
Frederic Weisbecker612d4fd2010-08-22 21:10:35 +0200779
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100780 node->ip = ip;
781 node->map = map;
782 node->sym = sym;
Frederic Weisbecker612d4fd2010-08-22 21:10:35 +0200783
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100784 cursor->nr++;
785
786 cursor->last = &node->next;
787
788 return 0;
Frederic Weisbecker612d4fd2010-08-22 21:10:35 +0200789}
Namhyung Kim2dc9fb12014-01-14 14:25:35 +0900790
791int sample__resolve_callchain(struct perf_sample *sample, struct symbol **parent,
792 struct perf_evsel *evsel, struct addr_location *al,
793 int max_stack)
794{
795 if (sample->callchain == NULL)
796 return 0;
797
Namhyung Kim7a13aa22012-09-11 14:13:04 +0900798 if (symbol_conf.use_callchain || symbol_conf.cumulate_callchain ||
799 sort__has_parent) {
Arnaldo Carvalho de Melocc8b7c22014-10-23 15:26:17 -0300800 return thread__resolve_callchain(al->thread, evsel, sample,
801 parent, al, max_stack);
Namhyung Kim2dc9fb12014-01-14 14:25:35 +0900802 }
803 return 0;
804}
805
806int hist_entry__append_callchain(struct hist_entry *he, struct perf_sample *sample)
807{
Adrian Hunter4d40b052014-07-14 13:02:35 +0300808 if (!symbol_conf.use_callchain || sample->callchain == NULL)
Namhyung Kim2dc9fb12014-01-14 14:25:35 +0900809 return 0;
810 return callchain_append(he->callchain, &callchain_cursor, sample->period);
811}
Namhyung Kimc7405d82013-10-31 13:58:30 +0900812
813int fill_callchain_info(struct addr_location *al, struct callchain_cursor_node *node,
814 bool hide_unresolved)
815{
816 al->map = node->map;
817 al->sym = node->sym;
818 if (node->map)
819 al->addr = node->map->map_ip(node->map, node->ip);
820 else
821 al->addr = node->ip;
822
823 if (al->sym == NULL) {
824 if (hide_unresolved)
825 return 0;
826 if (al->map == NULL)
827 goto out;
828 }
829
830 if (al->map->groups == &al->machine->kmaps) {
831 if (machine__is_host(al->machine)) {
832 al->cpumode = PERF_RECORD_MISC_KERNEL;
833 al->level = 'k';
834 } else {
835 al->cpumode = PERF_RECORD_MISC_GUEST_KERNEL;
836 al->level = 'g';
837 }
838 } else {
839 if (machine__is_host(al->machine)) {
840 al->cpumode = PERF_RECORD_MISC_USER;
841 al->level = '.';
842 } else if (perf_guest) {
843 al->cpumode = PERF_RECORD_MISC_GUEST_USER;
844 al->level = 'u';
845 } else {
846 al->cpumode = PERF_RECORD_MISC_HYPERVISOR;
847 al->level = 'H';
848 }
849 }
850
851out:
852 return 1;
853}
Andi Kleen2989cca2014-11-12 18:05:23 -0800854
855char *callchain_list__sym_name(struct callchain_list *cl,
856 char *bf, size_t bfsize, bool show_dso)
857{
858 int printed;
859
860 if (cl->ms.sym) {
Andi Kleen23f09812014-11-12 18:05:24 -0800861 if (callchain_param.key == CCKEY_ADDRESS &&
862 cl->ms.map && !cl->srcline)
863 cl->srcline = get_srcline(cl->ms.map->dso,
864 map__rip_2objdump(cl->ms.map,
Andi Kleen85c116a2014-11-12 18:05:27 -0800865 cl->ip),
866 cl->ms.sym, false);
Andi Kleen23f09812014-11-12 18:05:24 -0800867 if (cl->srcline)
868 printed = scnprintf(bf, bfsize, "%s %s",
869 cl->ms.sym->name, cl->srcline);
870 else
871 printed = scnprintf(bf, bfsize, "%s", cl->ms.sym->name);
Andi Kleen2989cca2014-11-12 18:05:23 -0800872 } else
873 printed = scnprintf(bf, bfsize, "%#" PRIx64, cl->ip);
874
875 if (show_dso)
876 scnprintf(bf + printed, bfsize - printed, " %s",
877 cl->ms.map ?
878 cl->ms.map->dso->short_name :
879 "unknown");
880
881 return bf;
882}
Namhyung Kimd1149602014-12-30 14:38:13 +0900883
Namhyung Kim5ab250c2015-11-09 14:45:39 +0900884char *callchain_node__scnprintf_value(struct callchain_node *node,
885 char *bf, size_t bfsize, u64 total)
886{
887 double percent = 0.0;
888 u64 period = callchain_cumul_hits(node);
Namhyung Kimf2af0082015-11-09 14:45:41 +0900889 unsigned count = callchain_cumul_counts(node);
Namhyung Kim5ab250c2015-11-09 14:45:39 +0900890
Namhyung Kimf2af0082015-11-09 14:45:41 +0900891 if (callchain_param.mode == CHAIN_FOLDED) {
Namhyung Kim5ab250c2015-11-09 14:45:39 +0900892 period = node->hit;
Namhyung Kimf2af0082015-11-09 14:45:41 +0900893 count = node->count;
894 }
Namhyung Kim5ab250c2015-11-09 14:45:39 +0900895
Namhyung Kimf2af0082015-11-09 14:45:41 +0900896 switch (callchain_param.value) {
897 case CCVAL_PERIOD:
898 scnprintf(bf, bfsize, "%"PRIu64, period);
899 break;
900 case CCVAL_COUNT:
901 scnprintf(bf, bfsize, "%u", count);
902 break;
903 case CCVAL_PERCENT:
904 default:
905 if (total)
906 percent = period * 100.0 / total;
907 scnprintf(bf, bfsize, "%.2f%%", percent);
908 break;
909 }
Namhyung Kim5ab250c2015-11-09 14:45:39 +0900910 return bf;
911}
912
913int callchain_node__fprintf_value(struct callchain_node *node,
914 FILE *fp, u64 total)
915{
916 double percent = 0.0;
917 u64 period = callchain_cumul_hits(node);
Namhyung Kimf2af0082015-11-09 14:45:41 +0900918 unsigned count = callchain_cumul_counts(node);
Namhyung Kim5ab250c2015-11-09 14:45:39 +0900919
Namhyung Kimf2af0082015-11-09 14:45:41 +0900920 if (callchain_param.mode == CHAIN_FOLDED) {
Namhyung Kim5ab250c2015-11-09 14:45:39 +0900921 period = node->hit;
Namhyung Kimf2af0082015-11-09 14:45:41 +0900922 count = node->count;
923 }
Namhyung Kim5ab250c2015-11-09 14:45:39 +0900924
Namhyung Kimf2af0082015-11-09 14:45:41 +0900925 switch (callchain_param.value) {
926 case CCVAL_PERIOD:
927 return fprintf(fp, "%"PRIu64, period);
928 case CCVAL_COUNT:
929 return fprintf(fp, "%u", count);
930 case CCVAL_PERCENT:
931 default:
932 if (total)
933 percent = period * 100.0 / total;
934 return percent_color_fprintf(fp, "%.2f%%", percent);
935 }
936 return 0;
Namhyung Kim5ab250c2015-11-09 14:45:39 +0900937}
938
Namhyung Kimd1149602014-12-30 14:38:13 +0900939static void free_callchain_node(struct callchain_node *node)
940{
941 struct callchain_list *list, *tmp;
942 struct callchain_node *child;
943 struct rb_node *n;
944
Namhyung Kim4b3a3212015-11-09 14:45:43 +0900945 list_for_each_entry_safe(list, tmp, &node->parent_val, list) {
946 list_del(&list->list);
947 free(list);
948 }
949
Namhyung Kimd1149602014-12-30 14:38:13 +0900950 list_for_each_entry_safe(list, tmp, &node->val, list) {
951 list_del(&list->list);
952 free(list);
953 }
954
955 n = rb_first(&node->rb_root_in);
956 while (n) {
957 child = container_of(n, struct callchain_node, rb_node_in);
958 n = rb_next(n);
959 rb_erase(&child->rb_node_in, &node->rb_root_in);
960
961 free_callchain_node(child);
962 free(child);
963 }
964}
965
966void free_callchain(struct callchain_root *root)
967{
968 if (!symbol_conf.use_callchain)
969 return;
970
971 free_callchain_node(&root->node);
972}
Namhyung Kim4b3a3212015-11-09 14:45:43 +0900973
Namhyung Kim42b276a2016-01-05 12:06:00 +0900974static u64 decay_callchain_node(struct callchain_node *node)
975{
976 struct callchain_node *child;
977 struct rb_node *n;
978 u64 child_hits = 0;
979
980 n = rb_first(&node->rb_root_in);
981 while (n) {
982 child = container_of(n, struct callchain_node, rb_node_in);
983
984 child_hits += decay_callchain_node(child);
985 n = rb_next(n);
986 }
987
988 node->hit = (node->hit * 7) / 8;
989 node->children_hit = child_hits;
990
991 return node->hit;
992}
993
994void decay_callchain(struct callchain_root *root)
995{
996 if (!symbol_conf.use_callchain)
997 return;
998
999 decay_callchain_node(&root->node);
1000}
1001
Namhyung Kim4b3a3212015-11-09 14:45:43 +09001002int callchain_node__make_parent_list(struct callchain_node *node)
1003{
1004 struct callchain_node *parent = node->parent;
1005 struct callchain_list *chain, *new;
1006 LIST_HEAD(head);
1007
1008 while (parent) {
1009 list_for_each_entry_reverse(chain, &parent->val, list) {
1010 new = malloc(sizeof(*new));
1011 if (new == NULL)
1012 goto out;
1013 *new = *chain;
1014 new->has_children = false;
1015 list_add_tail(&new->list, &head);
1016 }
1017 parent = parent->parent;
1018 }
1019
1020 list_for_each_entry_safe_reverse(chain, new, &head, list)
1021 list_move_tail(&chain->list, &node->parent_val);
1022
1023 if (!list_empty(&node->parent_val)) {
1024 chain = list_first_entry(&node->parent_val, struct callchain_list, list);
1025 chain->has_children = rb_prev(&node->rb_node) || rb_next(&node->rb_node);
1026
1027 chain = list_first_entry(&node->val, struct callchain_list, list);
1028 chain->has_children = false;
1029 }
1030 return 0;
1031
1032out:
1033 list_for_each_entry_safe(chain, new, &head, list) {
1034 list_del(&chain->list);
1035 free(chain);
1036 }
1037 return -ENOMEM;
1038}