blob: 146683b1c28d2005298b000e8621ebc8e8d31b32 [file] [log] [blame]
Greg Kroah-Hartmanb2441312017-11-01 15:07:57 +01001// SPDX-License-Identifier: GPL-2.0
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +02002/*
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +01003 * Copyright (C) 2009-2011, Frederic Weisbecker <fweisbec@gmail.com>
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +02004 *
5 * Handle the callchains from the stream in an ad-hoc radix tree and then
6 * sort them in an rbtree.
7 *
Frederic Weisbeckerdeac9112009-07-01 05:35:15 +02008 * Using a radix for code path provides a fast retrieval and factorizes
9 * memory use. Also that lets us use the paths in a hierarchical graph view.
10 *
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +020011 */
12
Arnaldo Carvalho de Melofd20e812017-04-17 15:23:08 -030013#include <inttypes.h>
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +020014#include <stdlib.h>
15#include <stdio.h>
16#include <stdbool.h>
17#include <errno.h>
Frederic Weisbeckerc0a88652009-08-09 04:19:15 +020018#include <math.h>
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +020019
Frederic Weisbeckerb965bb42014-01-14 16:37:15 +010020#include "asm/bug.h"
21
Andi Kleen99571ab2013-07-18 15:33:57 -070022#include "hist.h"
Arnaldo Carvalho de Melob36f19d2010-05-20 12:15:33 -030023#include "util.h"
Namhyung Kim2dc9fb12014-01-14 14:25:35 +090024#include "sort.h"
25#include "machine.h"
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +020026#include "callchain.h"
Jin Yaob851dd42017-07-18 20:13:15 +080027#include "branch.h"
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +020028
Arnaldo Carvalho de Melo56e2e052017-04-19 18:38:33 -030029#define CALLCHAIN_PARAM_DEFAULT \
30 .mode = CHAIN_GRAPH_ABS, \
31 .min_percent = 0.5, \
32 .order = ORDER_CALLEE, \
33 .key = CCKEY_FUNCTION, \
34 .value = CCVAL_PERCENT, \
35
36struct callchain_param callchain_param = {
37 CALLCHAIN_PARAM_DEFAULT
38};
39
Arnaldo Carvalho de Melo0eda4d02018-01-15 16:48:46 -030040/*
41 * Are there any events usind DWARF callchains?
42 *
43 * I.e.
44 *
45 * -e cycles/call-graph=dwarf/
46 */
47bool dwarf_callchain_users;
48
Arnaldo Carvalho de Melo56e2e052017-04-19 18:38:33 -030049struct callchain_param callchain_param_default = {
50 CALLCHAIN_PARAM_DEFAULT
51};
52
Namhyung Kim47260642012-05-31 14:43:26 +090053__thread struct callchain_cursor callchain_cursor;
54
Kan Liangc3a6a8c2015-08-04 04:30:20 -040055int parse_callchain_record_opt(const char *arg, struct callchain_param *param)
Namhyung Kimf7f084f2014-09-23 10:01:42 +090056{
Kan Liang076a30c2015-08-06 15:44:52 -040057 return parse_callchain_record(arg, param);
Namhyung Kimf7f084f2014-09-23 10:01:42 +090058}
59
Namhyung Kim2b9240c2014-09-23 10:01:43 +090060static int parse_callchain_mode(const char *value)
61{
62 if (!strncmp(value, "graph", strlen(value))) {
63 callchain_param.mode = CHAIN_GRAPH_ABS;
64 return 0;
65 }
66 if (!strncmp(value, "flat", strlen(value))) {
67 callchain_param.mode = CHAIN_FLAT;
68 return 0;
69 }
70 if (!strncmp(value, "fractal", strlen(value))) {
71 callchain_param.mode = CHAIN_GRAPH_REL;
72 return 0;
73 }
Namhyung Kim26e77922015-11-09 14:45:37 +090074 if (!strncmp(value, "folded", strlen(value))) {
75 callchain_param.mode = CHAIN_FOLDED;
76 return 0;
77 }
Namhyung Kim2b9240c2014-09-23 10:01:43 +090078 return -1;
79}
80
81static int parse_callchain_order(const char *value)
82{
83 if (!strncmp(value, "caller", strlen(value))) {
84 callchain_param.order = ORDER_CALLER;
Namhyung Kim792aeaf2015-10-22 16:45:46 +090085 callchain_param.order_set = true;
Namhyung Kim2b9240c2014-09-23 10:01:43 +090086 return 0;
87 }
88 if (!strncmp(value, "callee", strlen(value))) {
89 callchain_param.order = ORDER_CALLEE;
Namhyung Kim792aeaf2015-10-22 16:45:46 +090090 callchain_param.order_set = true;
Namhyung Kim2b9240c2014-09-23 10:01:43 +090091 return 0;
92 }
93 return -1;
94}
95
96static int parse_callchain_sort_key(const char *value)
97{
98 if (!strncmp(value, "function", strlen(value))) {
99 callchain_param.key = CCKEY_FUNCTION;
100 return 0;
101 }
102 if (!strncmp(value, "address", strlen(value))) {
103 callchain_param.key = CCKEY_ADDRESS;
104 return 0;
105 }
Milian Wolff5dfa2102017-03-18 22:49:28 +0100106 if (!strncmp(value, "srcline", strlen(value))) {
107 callchain_param.key = CCKEY_SRCLINE;
108 return 0;
109 }
Andi Kleen8b7bad52014-11-12 18:05:20 -0800110 if (!strncmp(value, "branch", strlen(value))) {
111 callchain_param.branch_callstack = 1;
112 return 0;
113 }
Namhyung Kim2b9240c2014-09-23 10:01:43 +0900114 return -1;
115}
116
Namhyung Kimf2af0082015-11-09 14:45:41 +0900117static int parse_callchain_value(const char *value)
118{
119 if (!strncmp(value, "percent", strlen(value))) {
120 callchain_param.value = CCVAL_PERCENT;
121 return 0;
122 }
123 if (!strncmp(value, "period", strlen(value))) {
124 callchain_param.value = CCVAL_PERIOD;
125 return 0;
126 }
127 if (!strncmp(value, "count", strlen(value))) {
128 callchain_param.value = CCVAL_COUNT;
129 return 0;
130 }
131 return -1;
132}
133
Arnaldo Carvalho de Melo56e2e052017-04-19 18:38:33 -0300134static int get_stack_size(const char *str, unsigned long *_size)
135{
136 char *endptr;
137 unsigned long size;
138 unsigned long max_size = round_down(USHRT_MAX, sizeof(u64));
139
140 size = strtoul(str, &endptr, 0);
141
142 do {
143 if (*endptr)
144 break;
145
146 size = round_up(size, sizeof(u64));
147 if (!size || size > max_size)
148 break;
149
150 *_size = size;
151 return 0;
152
153 } while (0);
154
155 pr_err("callchain: Incorrect stack dump size (max %ld): %s\n",
156 max_size, str);
157 return -1;
158}
159
Namhyung Kima2c10d32015-10-22 15:28:49 +0900160static int
161__parse_callchain_report_opt(const char *arg, bool allow_record_opt)
Don Zickuscff6bb42014-04-07 14:55:24 -0400162{
Namhyung Kime8232f12014-08-14 15:01:38 +0900163 char *tok;
Arnaldo Carvalho de Melodadafc32017-04-05 11:38:10 -0300164 char *endptr, *saveptr = NULL;
Namhyung Kime8232f12014-08-14 15:01:38 +0900165 bool minpcnt_set = false;
Namhyung Kima2c10d32015-10-22 15:28:49 +0900166 bool record_opt_set = false;
167 bool try_stack_size = false;
Don Zickuscff6bb42014-04-07 14:55:24 -0400168
Arnaldo Carvalho de Melo30234f02016-04-18 11:53:07 -0300169 callchain_param.enabled = true;
Don Zickuscff6bb42014-04-07 14:55:24 -0400170 symbol_conf.use_callchain = true;
171
172 if (!arg)
173 return 0;
174
Arnaldo Carvalho de Melodadafc32017-04-05 11:38:10 -0300175 while ((tok = strtok_r((char *)arg, ",", &saveptr)) != NULL) {
Namhyung Kime8232f12014-08-14 15:01:38 +0900176 if (!strncmp(tok, "none", strlen(tok))) {
177 callchain_param.mode = CHAIN_NONE;
Arnaldo Carvalho de Melo30234f02016-04-18 11:53:07 -0300178 callchain_param.enabled = false;
Namhyung Kime8232f12014-08-14 15:01:38 +0900179 symbol_conf.use_callchain = false;
180 return 0;
181 }
Don Zickuscff6bb42014-04-07 14:55:24 -0400182
Namhyung Kim2b9240c2014-09-23 10:01:43 +0900183 if (!parse_callchain_mode(tok) ||
184 !parse_callchain_order(tok) ||
Namhyung Kimf2af0082015-11-09 14:45:41 +0900185 !parse_callchain_sort_key(tok) ||
186 !parse_callchain_value(tok)) {
Namhyung Kim2b9240c2014-09-23 10:01:43 +0900187 /* parsing ok - move on to the next */
Namhyung Kima2c10d32015-10-22 15:28:49 +0900188 try_stack_size = false;
189 goto next;
190 } else if (allow_record_opt && !record_opt_set) {
191 if (parse_callchain_record(tok, &callchain_param))
192 goto try_numbers;
193
194 /* assume that number followed by 'dwarf' is stack size */
195 if (callchain_param.record_mode == CALLCHAIN_DWARF)
196 try_stack_size = true;
197
198 record_opt_set = true;
199 goto next;
200 }
201
202try_numbers:
203 if (try_stack_size) {
204 unsigned long size = 0;
205
206 if (get_stack_size(tok, &size) < 0)
207 return -1;
208 callchain_param.dump_size = size;
209 try_stack_size = false;
Namhyung Kim2b9240c2014-09-23 10:01:43 +0900210 } else if (!minpcnt_set) {
211 /* try to get the min percent */
Namhyung Kime8232f12014-08-14 15:01:38 +0900212 callchain_param.min_percent = strtod(tok, &endptr);
213 if (tok == endptr)
214 return -1;
215 minpcnt_set = true;
216 } else {
217 /* try print limit at last */
218 callchain_param.print_limit = strtoul(tok, &endptr, 0);
219 if (tok == endptr)
220 return -1;
221 }
Namhyung Kima2c10d32015-10-22 15:28:49 +0900222next:
Namhyung Kime8232f12014-08-14 15:01:38 +0900223 arg = NULL;
Don Zickuscff6bb42014-04-07 14:55:24 -0400224 }
225
Don Zickuscff6bb42014-04-07 14:55:24 -0400226 if (callchain_register_param(&callchain_param) < 0) {
227 pr_err("Can't register callchain params\n");
228 return -1;
229 }
230 return 0;
231}
232
Namhyung Kima2c10d32015-10-22 15:28:49 +0900233int parse_callchain_report_opt(const char *arg)
234{
235 return __parse_callchain_report_opt(arg, false);
236}
237
238int parse_callchain_top_opt(const char *arg)
239{
240 return __parse_callchain_report_opt(arg, true);
241}
242
Arnaldo Carvalho de Melo56e2e052017-04-19 18:38:33 -0300243int parse_callchain_record(const char *arg, struct callchain_param *param)
244{
245 char *tok, *name, *saveptr = NULL;
246 char *buf;
247 int ret = -1;
248
249 /* We need buffer that we know we can write to. */
250 buf = malloc(strlen(arg) + 1);
251 if (!buf)
252 return -ENOMEM;
253
254 strcpy(buf, arg);
255
256 tok = strtok_r((char *)buf, ",", &saveptr);
257 name = tok ? : (char *)buf;
258
259 do {
260 /* Framepointer style */
261 if (!strncmp(name, "fp", sizeof("fp"))) {
262 if (!strtok_r(NULL, ",", &saveptr)) {
263 param->record_mode = CALLCHAIN_FP;
264 ret = 0;
265 } else
266 pr_err("callchain: No more arguments "
267 "needed for --call-graph fp\n");
268 break;
269
270 /* Dwarf style */
271 } else if (!strncmp(name, "dwarf", sizeof("dwarf"))) {
272 const unsigned long default_stack_dump_size = 8192;
273
274 ret = 0;
275 param->record_mode = CALLCHAIN_DWARF;
276 param->dump_size = default_stack_dump_size;
Arnaldo Carvalho de Melo0eda4d02018-01-15 16:48:46 -0300277 dwarf_callchain_users = true;
Arnaldo Carvalho de Melo56e2e052017-04-19 18:38:33 -0300278
279 tok = strtok_r(NULL, ",", &saveptr);
280 if (tok) {
281 unsigned long size = 0;
282
283 ret = get_stack_size(tok, &size);
284 param->dump_size = size;
285 }
286 } else if (!strncmp(name, "lbr", sizeof("lbr"))) {
287 if (!strtok_r(NULL, ",", &saveptr)) {
288 param->record_mode = CALLCHAIN_LBR;
289 ret = 0;
290 } else
291 pr_err("callchain: No more arguments "
292 "needed for --call-graph lbr\n");
293 break;
294 } else {
295 pr_err("callchain: Unknown --call-graph option "
296 "value: %s\n", arg);
297 break;
298 }
299
300 } while (0);
301
302 free(buf);
303 return ret;
304}
305
Namhyung Kim2b9240c2014-09-23 10:01:43 +0900306int perf_callchain_config(const char *var, const char *value)
307{
308 char *endptr;
309
Arnaldo Carvalho de Melo8e99b6d2017-07-20 15:27:39 -0300310 if (!strstarts(var, "call-graph."))
Namhyung Kim2b9240c2014-09-23 10:01:43 +0900311 return 0;
312 var += sizeof("call-graph.") - 1;
313
314 if (!strcmp(var, "record-mode"))
Kan Liangc3a6a8c2015-08-04 04:30:20 -0400315 return parse_callchain_record_opt(value, &callchain_param);
Namhyung Kim2b9240c2014-09-23 10:01:43 +0900316 if (!strcmp(var, "dump-size")) {
317 unsigned long size = 0;
318 int ret;
319
320 ret = get_stack_size(value, &size);
321 callchain_param.dump_size = size;
322
323 return ret;
324 }
Mengting Zhang9789e7e2017-09-23 16:18:14 +0800325 if (!strcmp(var, "print-type")){
326 int ret;
327 ret = parse_callchain_mode(value);
328 if (ret == -1)
329 pr_err("Invalid callchain mode: %s\n", value);
330 return ret;
331 }
332 if (!strcmp(var, "order")){
333 int ret;
334 ret = parse_callchain_order(value);
335 if (ret == -1)
336 pr_err("Invalid callchain order: %s\n", value);
337 return ret;
338 }
339 if (!strcmp(var, "sort-key")){
340 int ret;
341 ret = parse_callchain_sort_key(value);
342 if (ret == -1)
343 pr_err("Invalid callchain sort key: %s\n", value);
344 return ret;
345 }
Namhyung Kim2b9240c2014-09-23 10:01:43 +0900346 if (!strcmp(var, "threshold")) {
347 callchain_param.min_percent = strtod(value, &endptr);
Arnaldo Carvalho de Meloecc4c562017-01-24 13:44:10 -0300348 if (value == endptr) {
349 pr_err("Invalid callchain threshold: %s\n", value);
Namhyung Kim2b9240c2014-09-23 10:01:43 +0900350 return -1;
Arnaldo Carvalho de Meloecc4c562017-01-24 13:44:10 -0300351 }
Namhyung Kim2b9240c2014-09-23 10:01:43 +0900352 }
353 if (!strcmp(var, "print-limit")) {
354 callchain_param.print_limit = strtod(value, &endptr);
Arnaldo Carvalho de Meloecc4c562017-01-24 13:44:10 -0300355 if (value == endptr) {
356 pr_err("Invalid callchain print limit: %s\n", value);
Namhyung Kim2b9240c2014-09-23 10:01:43 +0900357 return -1;
Arnaldo Carvalho de Meloecc4c562017-01-24 13:44:10 -0300358 }
Namhyung Kim2b9240c2014-09-23 10:01:43 +0900359 }
360
361 return 0;
362}
363
Frederic Weisbeckerdeac9112009-07-01 05:35:15 +0200364static void
Frederic Weisbecker4eb3e472009-07-02 17:58:21 +0200365rb_insert_callchain(struct rb_root *root, struct callchain_node *chain,
366 enum chain_mode mode)
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200367{
368 struct rb_node **p = &root->rb_node;
369 struct rb_node *parent = NULL;
370 struct callchain_node *rnode;
Frederic Weisbeckerf08c3152011-01-14 04:51:59 +0100371 u64 chain_cumul = callchain_cumul_hits(chain);
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200372
373 while (*p) {
Frederic Weisbecker19532872009-08-07 07:11:05 +0200374 u64 rnode_cumul;
375
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200376 parent = *p;
377 rnode = rb_entry(parent, struct callchain_node, rb_node);
Frederic Weisbeckerf08c3152011-01-14 04:51:59 +0100378 rnode_cumul = callchain_cumul_hits(rnode);
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200379
Frederic Weisbecker4eb3e472009-07-02 17:58:21 +0200380 switch (mode) {
Frederic Weisbecker805d1272009-07-05 07:39:21 +0200381 case CHAIN_FLAT:
Namhyung Kim26e77922015-11-09 14:45:37 +0900382 case CHAIN_FOLDED:
Frederic Weisbecker4eb3e472009-07-02 17:58:21 +0200383 if (rnode->hit < chain->hit)
384 p = &(*p)->rb_left;
385 else
386 p = &(*p)->rb_right;
387 break;
Frederic Weisbecker805d1272009-07-05 07:39:21 +0200388 case CHAIN_GRAPH_ABS: /* Falldown */
389 case CHAIN_GRAPH_REL:
Frederic Weisbecker19532872009-08-07 07:11:05 +0200390 if (rnode_cumul < chain_cumul)
Frederic Weisbecker4eb3e472009-07-02 17:58:21 +0200391 p = &(*p)->rb_left;
392 else
393 p = &(*p)->rb_right;
394 break;
Ingo Molnar83a09442009-08-15 12:26:57 +0200395 case CHAIN_NONE:
Frederic Weisbecker4eb3e472009-07-02 17:58:21 +0200396 default:
397 break;
398 }
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200399 }
400
401 rb_link_node(&chain->rb_node, parent, p);
402 rb_insert_color(&chain->rb_node, root);
403}
404
Frederic Weisbecker805d1272009-07-05 07:39:21 +0200405static void
406__sort_chain_flat(struct rb_root *rb_root, struct callchain_node *node,
407 u64 min_hit)
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200408{
Namhyung Kime3695172013-10-11 14:15:36 +0900409 struct rb_node *n;
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200410 struct callchain_node *child;
411
Namhyung Kime3695172013-10-11 14:15:36 +0900412 n = rb_first(&node->rb_root_in);
413 while (n) {
414 child = rb_entry(n, struct callchain_node, rb_node_in);
415 n = rb_next(n);
416
Frederic Weisbecker805d1272009-07-05 07:39:21 +0200417 __sort_chain_flat(rb_root, child, min_hit);
Namhyung Kime3695172013-10-11 14:15:36 +0900418 }
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200419
Frederic Weisbeckerc20ab372009-07-02 20:14:33 +0200420 if (node->hit && node->hit >= min_hit)
Frederic Weisbecker805d1272009-07-05 07:39:21 +0200421 rb_insert_callchain(rb_root, node, CHAIN_FLAT);
Frederic Weisbecker4eb3e472009-07-02 17:58:21 +0200422}
423
Frederic Weisbecker805d1272009-07-05 07:39:21 +0200424/*
425 * Once we get every callchains from the stream, we can now
426 * sort them by hit
427 */
428static void
Frederic Weisbeckerd2009c52010-08-22 20:05:22 +0200429sort_chain_flat(struct rb_root *rb_root, struct callchain_root *root,
Irina Tirdea1d037ca2012-09-11 01:15:03 +0300430 u64 min_hit, struct callchain_param *param __maybe_unused)
Frederic Weisbecker805d1272009-07-05 07:39:21 +0200431{
Namhyung Kim03562182015-11-26 16:08:18 +0900432 *rb_root = RB_ROOT;
Frederic Weisbeckerd2009c52010-08-22 20:05:22 +0200433 __sort_chain_flat(rb_root, &root->node, min_hit);
Frederic Weisbecker805d1272009-07-05 07:39:21 +0200434}
435
436static void __sort_chain_graph_abs(struct callchain_node *node,
437 u64 min_hit)
Frederic Weisbecker4eb3e472009-07-02 17:58:21 +0200438{
Namhyung Kime3695172013-10-11 14:15:36 +0900439 struct rb_node *n;
Frederic Weisbecker4eb3e472009-07-02 17:58:21 +0200440 struct callchain_node *child;
441
442 node->rb_root = RB_ROOT;
Namhyung Kime3695172013-10-11 14:15:36 +0900443 n = rb_first(&node->rb_root_in);
Frederic Weisbecker4eb3e472009-07-02 17:58:21 +0200444
Namhyung Kime3695172013-10-11 14:15:36 +0900445 while (n) {
446 child = rb_entry(n, struct callchain_node, rb_node_in);
447 n = rb_next(n);
448
Frederic Weisbecker805d1272009-07-05 07:39:21 +0200449 __sort_chain_graph_abs(child, min_hit);
Frederic Weisbeckerf08c3152011-01-14 04:51:59 +0100450 if (callchain_cumul_hits(child) >= min_hit)
Frederic Weisbecker805d1272009-07-05 07:39:21 +0200451 rb_insert_callchain(&node->rb_root, child,
452 CHAIN_GRAPH_ABS);
Frederic Weisbecker4eb3e472009-07-02 17:58:21 +0200453 }
454}
455
Frederic Weisbecker805d1272009-07-05 07:39:21 +0200456static void
Frederic Weisbeckerd2009c52010-08-22 20:05:22 +0200457sort_chain_graph_abs(struct rb_root *rb_root, struct callchain_root *chain_root,
Irina Tirdea1d037ca2012-09-11 01:15:03 +0300458 u64 min_hit, struct callchain_param *param __maybe_unused)
Frederic Weisbecker4eb3e472009-07-02 17:58:21 +0200459{
Frederic Weisbeckerd2009c52010-08-22 20:05:22 +0200460 __sort_chain_graph_abs(&chain_root->node, min_hit);
461 rb_root->rb_node = chain_root->node.rb_root.rb_node;
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200462}
463
Frederic Weisbecker805d1272009-07-05 07:39:21 +0200464static void __sort_chain_graph_rel(struct callchain_node *node,
465 double min_percent)
466{
Namhyung Kime3695172013-10-11 14:15:36 +0900467 struct rb_node *n;
Frederic Weisbecker805d1272009-07-05 07:39:21 +0200468 struct callchain_node *child;
469 u64 min_hit;
470
471 node->rb_root = RB_ROOT;
Frederic Weisbeckerc0a88652009-08-09 04:19:15 +0200472 min_hit = ceil(node->children_hit * min_percent);
Frederic Weisbecker805d1272009-07-05 07:39:21 +0200473
Namhyung Kime3695172013-10-11 14:15:36 +0900474 n = rb_first(&node->rb_root_in);
475 while (n) {
476 child = rb_entry(n, struct callchain_node, rb_node_in);
477 n = rb_next(n);
478
Frederic Weisbecker805d1272009-07-05 07:39:21 +0200479 __sort_chain_graph_rel(child, min_percent);
Frederic Weisbeckerf08c3152011-01-14 04:51:59 +0100480 if (callchain_cumul_hits(child) >= min_hit)
Frederic Weisbecker805d1272009-07-05 07:39:21 +0200481 rb_insert_callchain(&node->rb_root, child,
482 CHAIN_GRAPH_REL);
483 }
484}
485
486static void
Frederic Weisbeckerd2009c52010-08-22 20:05:22 +0200487sort_chain_graph_rel(struct rb_root *rb_root, struct callchain_root *chain_root,
Irina Tirdea1d037ca2012-09-11 01:15:03 +0300488 u64 min_hit __maybe_unused, struct callchain_param *param)
Frederic Weisbecker805d1272009-07-05 07:39:21 +0200489{
Frederic Weisbeckerd2009c52010-08-22 20:05:22 +0200490 __sort_chain_graph_rel(&chain_root->node, param->min_percent / 100.0);
491 rb_root->rb_node = chain_root->node.rb_root.rb_node;
Frederic Weisbecker805d1272009-07-05 07:39:21 +0200492}
493
Frederic Weisbecker16537f12011-01-14 04:52:00 +0100494int callchain_register_param(struct callchain_param *param)
Frederic Weisbecker805d1272009-07-05 07:39:21 +0200495{
496 switch (param->mode) {
497 case CHAIN_GRAPH_ABS:
498 param->sort = sort_chain_graph_abs;
499 break;
500 case CHAIN_GRAPH_REL:
501 param->sort = sort_chain_graph_rel;
502 break;
503 case CHAIN_FLAT:
Namhyung Kim26e77922015-11-09 14:45:37 +0900504 case CHAIN_FOLDED:
Frederic Weisbecker805d1272009-07-05 07:39:21 +0200505 param->sort = sort_chain_flat;
506 break;
Ingo Molnar83a09442009-08-15 12:26:57 +0200507 case CHAIN_NONE:
Frederic Weisbecker805d1272009-07-05 07:39:21 +0200508 default:
509 return -1;
510 }
511 return 0;
512}
513
Frederic Weisbeckerdeac9112009-07-01 05:35:15 +0200514/*
515 * Create a child for a parent. If inherit_children, then the new child
516 * will become the new parent of it's parent children
517 */
518static struct callchain_node *
519create_child(struct callchain_node *parent, bool inherit_children)
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200520{
521 struct callchain_node *new;
522
Arnaldo Carvalho de Melocdd5b75b2010-05-10 10:56:50 -0300523 new = zalloc(sizeof(*new));
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200524 if (!new) {
525 perror("not enough memory to create child for code path tree");
526 return NULL;
527 }
528 new->parent = parent;
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200529 INIT_LIST_HEAD(&new->val);
Namhyung Kim4b3a3212015-11-09 14:45:43 +0900530 INIT_LIST_HEAD(&new->parent_val);
Frederic Weisbeckerdeac9112009-07-01 05:35:15 +0200531
532 if (inherit_children) {
Namhyung Kime3695172013-10-11 14:15:36 +0900533 struct rb_node *n;
534 struct callchain_node *child;
Frederic Weisbeckerdeac9112009-07-01 05:35:15 +0200535
Namhyung Kime3695172013-10-11 14:15:36 +0900536 new->rb_root_in = parent->rb_root_in;
537 parent->rb_root_in = RB_ROOT;
Frederic Weisbeckerdeac9112009-07-01 05:35:15 +0200538
Namhyung Kime3695172013-10-11 14:15:36 +0900539 n = rb_first(&new->rb_root_in);
540 while (n) {
541 child = rb_entry(n, struct callchain_node, rb_node_in);
542 child->parent = new;
543 n = rb_next(n);
544 }
545
546 /* make it the first child */
547 rb_link_node(&new->rb_node_in, NULL, &parent->rb_root_in.rb_node);
548 rb_insert_color(&new->rb_node_in, &parent->rb_root_in);
Frederic Weisbeckerdeac9112009-07-01 05:35:15 +0200549 }
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200550
551 return new;
552}
553
Frederic Weisbecker301fde22010-03-22 13:09:33 -0300554
Frederic Weisbeckerdeac9112009-07-01 05:35:15 +0200555/*
556 * Fill the node with callchain values
557 */
Namhyung Kim8451cbb2016-02-16 23:08:21 +0900558static int
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100559fill_node(struct callchain_node *node, struct callchain_cursor *cursor)
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200560{
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100561 struct callchain_cursor_node *cursor_node;
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200562
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100563 node->val_nr = cursor->nr - cursor->pos;
564 if (!node->val_nr)
565 pr_warning("Warning: empty node in callchain tree\n");
566
567 cursor_node = callchain_cursor_current(cursor);
568
569 while (cursor_node) {
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200570 struct callchain_list *call;
571
Arnaldo Carvalho de Melocdd5b75b2010-05-10 10:56:50 -0300572 call = zalloc(sizeof(*call));
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200573 if (!call) {
574 perror("not enough memory for the code path tree");
Namhyung Kim8451cbb2016-02-16 23:08:21 +0900575 return -1;
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200576 }
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100577 call->ip = cursor_node->ip;
578 call->ms.sym = cursor_node->sym;
Krister Johansen9c68ae92017-01-05 22:23:31 -0800579 call->ms.map = map__get(cursor_node->map);
Jin Yao3dd029e2016-10-31 09:19:51 +0800580
581 if (cursor_node->branch) {
582 call->branch_count = 1;
583
Jin Yaoa1a8bed2017-07-24 19:09:07 +0800584 if (cursor_node->branch_from) {
585 /*
586 * branch_from is set with value somewhere else
587 * to imply it's "to" of a branch.
588 */
589 call->brtype_stat.branch_to = true;
Jin Yao3dd029e2016-10-31 09:19:51 +0800590
Jin Yaoa1a8bed2017-07-24 19:09:07 +0800591 if (cursor_node->branch_flags.predicted)
592 call->predicted_count = 1;
Jin Yao3dd029e2016-10-31 09:19:51 +0800593
Jin Yaoa1a8bed2017-07-24 19:09:07 +0800594 if (cursor_node->branch_flags.abort)
595 call->abort_count = 1;
Jin Yaob851dd42017-07-18 20:13:15 +0800596
Jin Yaoa1a8bed2017-07-24 19:09:07 +0800597 branch_type_count(&call->brtype_stat,
598 &cursor_node->branch_flags,
599 cursor_node->branch_from,
600 cursor_node->ip);
601 } else {
602 /*
603 * It's "from" of a branch
604 */
605 call->brtype_stat.branch_to = false;
606 call->cycles_count =
607 cursor_node->branch_flags.cycles;
608 call->iter_count = cursor_node->nr_loop_iter;
Jin Yaoc4ee0622017-08-07 21:05:15 +0800609 call->iter_cycles = cursor_node->iter_cycles;
Jin Yaoa1a8bed2017-07-24 19:09:07 +0800610 }
Jin Yao3dd029e2016-10-31 09:19:51 +0800611 }
612
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200613 list_add_tail(&call->list, &node->val);
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100614
615 callchain_cursor_advance(cursor);
616 cursor_node = callchain_cursor_current(cursor);
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200617 }
Namhyung Kim8451cbb2016-02-16 23:08:21 +0900618 return 0;
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200619}
620
Namhyung Kime3695172013-10-11 14:15:36 +0900621static struct callchain_node *
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100622add_child(struct callchain_node *parent,
623 struct callchain_cursor *cursor,
624 u64 period)
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200625{
626 struct callchain_node *new;
627
Frederic Weisbeckerdeac9112009-07-01 05:35:15 +0200628 new = create_child(parent, false);
Namhyung Kim7565bd32016-02-16 23:08:20 +0900629 if (new == NULL)
630 return NULL;
631
Namhyung Kim8451cbb2016-02-16 23:08:21 +0900632 if (fill_node(new, cursor) < 0) {
633 struct callchain_list *call, *tmp;
634
635 list_for_each_entry_safe(call, tmp, &new->val, list) {
636 list_del(&call->list);
Krister Johansen9c68ae92017-01-05 22:23:31 -0800637 map__zput(call->ms.map);
Namhyung Kim8451cbb2016-02-16 23:08:21 +0900638 free(call);
639 }
640 free(new);
641 return NULL;
642 }
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200643
Frederic Weisbecker19532872009-08-07 07:11:05 +0200644 new->children_hit = 0;
Frederic Weisbecker108553e2010-07-08 03:41:46 +0200645 new->hit = period;
Namhyung Kim5e47f8f2015-11-09 14:45:40 +0900646 new->children_count = 0;
647 new->count = 1;
Namhyung Kime3695172013-10-11 14:15:36 +0900648 return new;
649}
650
Namhyung Kim2d713b82016-02-16 23:08:22 +0900651enum match_result {
652 MATCH_ERROR = -1,
653 MATCH_EQ,
654 MATCH_LT,
655 MATCH_GT,
656};
657
Milian Wolff5dfa2102017-03-18 22:49:28 +0100658static enum match_result match_chain_srcline(struct callchain_cursor_node *node,
659 struct callchain_list *cnode)
660{
Milian Wolff7d4df082017-05-24 15:21:23 +0900661 char *left = NULL;
662 char *right = NULL;
Milian Wolff5dfa2102017-03-18 22:49:28 +0100663 enum match_result ret = MATCH_EQ;
664 int cmp;
665
Milian Wolff7d4df082017-05-24 15:21:23 +0900666 if (cnode->ms.map)
667 left = get_srcline(cnode->ms.map->dso,
668 map__rip_2objdump(cnode->ms.map, cnode->ip),
669 cnode->ms.sym, true, false);
670 if (node->map)
671 right = get_srcline(node->map->dso,
672 map__rip_2objdump(node->map, node->ip),
673 node->sym, true, false);
674
Milian Wolff5dfa2102017-03-18 22:49:28 +0100675 if (left && right)
676 cmp = strcmp(left, right);
677 else if (!left && right)
678 cmp = 1;
679 else if (left && !right)
680 cmp = -1;
681 else if (cnode->ip == node->ip)
682 cmp = 0;
683 else
684 cmp = (cnode->ip < node->ip) ? -1 : 1;
685
686 if (cmp != 0)
687 ret = cmp < 0 ? MATCH_LT : MATCH_GT;
688
689 free_srcline(left);
690 free_srcline(right);
691 return ret;
692}
693
Namhyung Kim2d713b82016-02-16 23:08:22 +0900694static enum match_result match_chain(struct callchain_cursor_node *node,
695 struct callchain_list *cnode)
Namhyung Kime3695172013-10-11 14:15:36 +0900696{
697 struct symbol *sym = node->sym;
Namhyung Kim2d713b82016-02-16 23:08:22 +0900698 u64 left, right;
Ravi Bangoriac1fbc0c2017-10-05 14:42:34 +0530699 struct dso *left_dso = NULL;
700 struct dso *right_dso = NULL;
Namhyung Kime3695172013-10-11 14:15:36 +0900701
Milian Wolff5dfa2102017-03-18 22:49:28 +0100702 if (callchain_param.key == CCKEY_SRCLINE) {
703 enum match_result match = match_chain_srcline(node, cnode);
704
705 if (match != MATCH_ERROR)
706 return match;
707 }
708
709 if (cnode->ms.sym && sym && callchain_param.key == CCKEY_FUNCTION) {
Namhyung Kim2d713b82016-02-16 23:08:22 +0900710 left = cnode->ms.sym->start;
711 right = sym->start;
Ravi Bangoriac1fbc0c2017-10-05 14:42:34 +0530712 left_dso = cnode->ms.map->dso;
713 right_dso = node->map->dso;
Namhyung Kim2d713b82016-02-16 23:08:22 +0900714 } else {
715 left = cnode->ip;
716 right = node->ip;
717 }
718
Ravi Bangoriac1fbc0c2017-10-05 14:42:34 +0530719 if (left == right && left_dso == right_dso) {
Jin Yao3dd029e2016-10-31 09:19:51 +0800720 if (node->branch) {
721 cnode->branch_count++;
722
Jin Yaoa1a8bed2017-07-24 19:09:07 +0800723 if (node->branch_from) {
724 /*
725 * It's "to" of a branch
726 */
727 cnode->brtype_stat.branch_to = true;
Jin Yao3dd029e2016-10-31 09:19:51 +0800728
Jin Yaoa1a8bed2017-07-24 19:09:07 +0800729 if (node->branch_flags.predicted)
730 cnode->predicted_count++;
Jin Yao3dd029e2016-10-31 09:19:51 +0800731
Jin Yaoa1a8bed2017-07-24 19:09:07 +0800732 if (node->branch_flags.abort)
733 cnode->abort_count++;
Jin Yaob851dd42017-07-18 20:13:15 +0800734
Jin Yaoa1a8bed2017-07-24 19:09:07 +0800735 branch_type_count(&cnode->brtype_stat,
736 &node->branch_flags,
737 node->branch_from,
738 node->ip);
739 } else {
740 /*
741 * It's "from" of a branch
742 */
743 cnode->brtype_stat.branch_to = false;
744 cnode->cycles_count +=
745 node->branch_flags.cycles;
746 cnode->iter_count += node->nr_loop_iter;
Jin Yaoc4ee0622017-08-07 21:05:15 +0800747 cnode->iter_cycles += node->iter_cycles;
Jin Yaoa1a8bed2017-07-24 19:09:07 +0800748 }
Jin Yao3dd029e2016-10-31 09:19:51 +0800749 }
750
Namhyung Kim2d713b82016-02-16 23:08:22 +0900751 return MATCH_EQ;
Jin Yao3dd029e2016-10-31 09:19:51 +0800752 }
Namhyung Kim2d713b82016-02-16 23:08:22 +0900753
754 return left > right ? MATCH_GT : MATCH_LT;
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200755}
756
Frederic Weisbeckerdeac9112009-07-01 05:35:15 +0200757/*
758 * Split the parent in two parts (a new child is created) and
759 * give a part of its callchain to the created child.
760 * Then create another child to host the given callchain of new branch
761 */
Namhyung Kimf2bb4c52016-02-16 23:08:23 +0900762static int
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100763split_add_child(struct callchain_node *parent,
764 struct callchain_cursor *cursor,
765 struct callchain_list *to_split,
766 u64 idx_parents, u64 idx_local, u64 period)
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200767{
768 struct callchain_node *new;
Frederic Weisbeckerdeac9112009-07-01 05:35:15 +0200769 struct list_head *old_tail;
Ingo Molnarf37a2912009-07-01 12:37:06 +0200770 unsigned int idx_total = idx_parents + idx_local;
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200771
772 /* split */
Frederic Weisbeckerdeac9112009-07-01 05:35:15 +0200773 new = create_child(parent, true);
Namhyung Kimf2bb4c52016-02-16 23:08:23 +0900774 if (new == NULL)
775 return -1;
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200776
Frederic Weisbeckerdeac9112009-07-01 05:35:15 +0200777 /* split the callchain and move a part to the new child */
778 old_tail = parent->val.prev;
779 list_del_range(&to_split->list, old_tail);
780 new->val.next = &to_split->list;
781 new->val.prev = old_tail;
782 to_split->list.prev = &new->val;
783 old_tail->next = &new->val;
784
785 /* split the hits */
786 new->hit = parent->hit;
Frederic Weisbecker19532872009-08-07 07:11:05 +0200787 new->children_hit = parent->children_hit;
Frederic Weisbeckerf08c3152011-01-14 04:51:59 +0100788 parent->children_hit = callchain_cumul_hits(new);
Frederic Weisbeckerdeac9112009-07-01 05:35:15 +0200789 new->val_nr = parent->val_nr - idx_local;
790 parent->val_nr = idx_local;
Namhyung Kim5e47f8f2015-11-09 14:45:40 +0900791 new->count = parent->count;
792 new->children_count = parent->children_count;
793 parent->children_count = callchain_cumul_counts(new);
Frederic Weisbeckerdeac9112009-07-01 05:35:15 +0200794
795 /* create a new child for the new branch if any */
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100796 if (idx_total < cursor->nr) {
Namhyung Kime3695172013-10-11 14:15:36 +0900797 struct callchain_node *first;
798 struct callchain_list *cnode;
799 struct callchain_cursor_node *node;
800 struct rb_node *p, **pp;
801
Frederic Weisbeckerdeac9112009-07-01 05:35:15 +0200802 parent->hit = 0;
Frederic Weisbecker108553e2010-07-08 03:41:46 +0200803 parent->children_hit += period;
Namhyung Kim5e47f8f2015-11-09 14:45:40 +0900804 parent->count = 0;
805 parent->children_count += 1;
Namhyung Kime3695172013-10-11 14:15:36 +0900806
807 node = callchain_cursor_current(cursor);
808 new = add_child(parent, cursor, period);
Namhyung Kim7565bd32016-02-16 23:08:20 +0900809 if (new == NULL)
Namhyung Kimf2bb4c52016-02-16 23:08:23 +0900810 return -1;
Namhyung Kime3695172013-10-11 14:15:36 +0900811
812 /*
813 * This is second child since we moved parent's children
814 * to new (first) child above.
815 */
816 p = parent->rb_root_in.rb_node;
817 first = rb_entry(p, struct callchain_node, rb_node_in);
818 cnode = list_first_entry(&first->val, struct callchain_list,
819 list);
820
Namhyung Kim2d713b82016-02-16 23:08:22 +0900821 if (match_chain(node, cnode) == MATCH_LT)
Namhyung Kime3695172013-10-11 14:15:36 +0900822 pp = &p->rb_left;
823 else
824 pp = &p->rb_right;
825
826 rb_link_node(&new->rb_node_in, p, pp);
827 rb_insert_color(&new->rb_node_in, &parent->rb_root_in);
Frederic Weisbeckerdeac9112009-07-01 05:35:15 +0200828 } else {
Frederic Weisbecker108553e2010-07-08 03:41:46 +0200829 parent->hit = period;
Namhyung Kim5e47f8f2015-11-09 14:45:40 +0900830 parent->count = 1;
Frederic Weisbeckerdeac9112009-07-01 05:35:15 +0200831 }
Namhyung Kimf2bb4c52016-02-16 23:08:23 +0900832 return 0;
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200833}
834
Namhyung Kim2d713b82016-02-16 23:08:22 +0900835static enum match_result
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100836append_chain(struct callchain_node *root,
837 struct callchain_cursor *cursor,
838 u64 period);
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200839
Namhyung Kimdca0d122016-02-16 23:08:24 +0900840static int
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100841append_chain_children(struct callchain_node *root,
842 struct callchain_cursor *cursor,
843 u64 period)
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200844{
845 struct callchain_node *rnode;
Namhyung Kime3695172013-10-11 14:15:36 +0900846 struct callchain_cursor_node *node;
847 struct rb_node **p = &root->rb_root_in.rb_node;
848 struct rb_node *parent = NULL;
849
850 node = callchain_cursor_current(cursor);
851 if (!node)
Namhyung Kimdca0d122016-02-16 23:08:24 +0900852 return -1;
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200853
854 /* lookup in childrens */
Namhyung Kime3695172013-10-11 14:15:36 +0900855 while (*p) {
Namhyung Kim2d713b82016-02-16 23:08:22 +0900856 enum match_result ret;
Ingo Molnarf37a2912009-07-01 12:37:06 +0200857
Namhyung Kime3695172013-10-11 14:15:36 +0900858 parent = *p;
859 rnode = rb_entry(parent, struct callchain_node, rb_node_in);
Namhyung Kime3695172013-10-11 14:15:36 +0900860
Frederic Weisbeckerb965bb42014-01-14 16:37:15 +0100861 /* If at least first entry matches, rely to children */
862 ret = append_chain(rnode, cursor, period);
Namhyung Kim2d713b82016-02-16 23:08:22 +0900863 if (ret == MATCH_EQ)
Frederic Weisbecker19532872009-08-07 07:11:05 +0200864 goto inc_children_hit;
Namhyung Kimdca0d122016-02-16 23:08:24 +0900865 if (ret == MATCH_ERROR)
866 return -1;
Namhyung Kime3695172013-10-11 14:15:36 +0900867
Namhyung Kim2d713b82016-02-16 23:08:22 +0900868 if (ret == MATCH_LT)
Namhyung Kime3695172013-10-11 14:15:36 +0900869 p = &parent->rb_left;
870 else
871 p = &parent->rb_right;
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200872 }
Frederic Weisbeckerdeac9112009-07-01 05:35:15 +0200873 /* nothing in children, add to the current node */
Namhyung Kime3695172013-10-11 14:15:36 +0900874 rnode = add_child(root, cursor, period);
Namhyung Kim7565bd32016-02-16 23:08:20 +0900875 if (rnode == NULL)
Namhyung Kimdca0d122016-02-16 23:08:24 +0900876 return -1;
Namhyung Kim7565bd32016-02-16 23:08:20 +0900877
Namhyung Kime3695172013-10-11 14:15:36 +0900878 rb_link_node(&rnode->rb_node_in, parent, p);
879 rb_insert_color(&rnode->rb_node_in, &root->rb_root_in);
Frederic Weisbeckere05b8762009-07-05 07:39:20 +0200880
Frederic Weisbecker19532872009-08-07 07:11:05 +0200881inc_children_hit:
Frederic Weisbecker108553e2010-07-08 03:41:46 +0200882 root->children_hit += period;
Namhyung Kim5e47f8f2015-11-09 14:45:40 +0900883 root->children_count++;
Namhyung Kimdca0d122016-02-16 23:08:24 +0900884 return 0;
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200885}
886
Namhyung Kim2d713b82016-02-16 23:08:22 +0900887static enum match_result
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100888append_chain(struct callchain_node *root,
889 struct callchain_cursor *cursor,
890 u64 period)
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200891{
892 struct callchain_list *cnode;
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100893 u64 start = cursor->pos;
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200894 bool found = false;
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100895 u64 matches;
Namhyung Kim2d713b82016-02-16 23:08:22 +0900896 enum match_result cmp = MATCH_ERROR;
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200897
Frederic Weisbeckerdeac9112009-07-01 05:35:15 +0200898 /*
899 * Lookup in the current node
900 * If we have a symbol, then compare the start to match
Andi Kleen99571ab2013-07-18 15:33:57 -0700901 * anywhere inside a function, unless function
902 * mode is disabled.
Frederic Weisbeckerdeac9112009-07-01 05:35:15 +0200903 */
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200904 list_for_each_entry(cnode, &root->val, list) {
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100905 struct callchain_cursor_node *node;
Frederic Weisbecker301fde22010-03-22 13:09:33 -0300906
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100907 node = callchain_cursor_current(cursor);
908 if (!node)
Frederic Weisbeckerdeac9112009-07-01 05:35:15 +0200909 break;
Frederic Weisbecker301fde22010-03-22 13:09:33 -0300910
Frederic Weisbeckerb965bb42014-01-14 16:37:15 +0100911 cmp = match_chain(node, cnode);
Namhyung Kim2d713b82016-02-16 23:08:22 +0900912 if (cmp != MATCH_EQ)
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200913 break;
Frederic Weisbecker301fde22010-03-22 13:09:33 -0300914
Namhyung Kime3695172013-10-11 14:15:36 +0900915 found = true;
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100916
917 callchain_cursor_advance(cursor);
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200918 }
919
Namhyung Kime3695172013-10-11 14:15:36 +0900920 /* matches not, relay no the parent */
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100921 if (!found) {
Namhyung Kim2d713b82016-02-16 23:08:22 +0900922 WARN_ONCE(cmp == MATCH_ERROR, "Chain comparison error\n");
Frederic Weisbeckerb965bb42014-01-14 16:37:15 +0100923 return cmp;
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100924 }
925
926 matches = cursor->pos - start;
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200927
928 /* we match only a part of the node. Split it and add the new chain */
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100929 if (matches < root->val_nr) {
Namhyung Kimf2bb4c52016-02-16 23:08:23 +0900930 if (split_add_child(root, cursor, cnode, start, matches,
931 period) < 0)
932 return MATCH_ERROR;
933
Namhyung Kim2d713b82016-02-16 23:08:22 +0900934 return MATCH_EQ;
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200935 }
936
937 /* we match 100% of the path, increment the hit */
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100938 if (matches == root->val_nr && cursor->pos == cursor->nr) {
Frederic Weisbecker108553e2010-07-08 03:41:46 +0200939 root->hit += period;
Namhyung Kim5e47f8f2015-11-09 14:45:40 +0900940 root->count++;
Namhyung Kim2d713b82016-02-16 23:08:22 +0900941 return MATCH_EQ;
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200942 }
943
Frederic Weisbeckerdeac9112009-07-01 05:35:15 +0200944 /* We match the node and still have a part remaining */
Namhyung Kimdca0d122016-02-16 23:08:24 +0900945 if (append_chain_children(root, cursor, period) < 0)
946 return MATCH_ERROR;
Frederic Weisbeckerdeac9112009-07-01 05:35:15 +0200947
Namhyung Kim2d713b82016-02-16 23:08:22 +0900948 return MATCH_EQ;
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200949}
950
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100951int callchain_append(struct callchain_root *root,
952 struct callchain_cursor *cursor,
953 u64 period)
Frederic Weisbecker301fde22010-03-22 13:09:33 -0300954{
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100955 if (!cursor->nr)
Frederic Weisbecker301fde22010-03-22 13:09:33 -0300956 return 0;
957
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100958 callchain_cursor_commit(cursor);
Frederic Weisbecker301fde22010-03-22 13:09:33 -0300959
Namhyung Kimdca0d122016-02-16 23:08:24 +0900960 if (append_chain_children(&root->node, cursor, period) < 0)
961 return -1;
Frederic Weisbecker301fde22010-03-22 13:09:33 -0300962
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100963 if (cursor->nr > root->max_depth)
964 root->max_depth = cursor->nr;
Frederic Weisbecker301fde22010-03-22 13:09:33 -0300965
966 return 0;
Frederic Weisbecker8cb76d92009-06-26 16:28:00 +0200967}
Frederic Weisbecker612d4fd2010-08-22 21:10:35 +0200968
969static int
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100970merge_chain_branch(struct callchain_cursor *cursor,
971 struct callchain_node *dst, struct callchain_node *src)
Frederic Weisbecker612d4fd2010-08-22 21:10:35 +0200972{
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100973 struct callchain_cursor_node **old_last = cursor->last;
Namhyung Kime3695172013-10-11 14:15:36 +0900974 struct callchain_node *child;
Frederic Weisbecker612d4fd2010-08-22 21:10:35 +0200975 struct callchain_list *list, *next_list;
Namhyung Kime3695172013-10-11 14:15:36 +0900976 struct rb_node *n;
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100977 int old_pos = cursor->nr;
Frederic Weisbecker612d4fd2010-08-22 21:10:35 +0200978 int err = 0;
979
980 list_for_each_entry_safe(list, next_list, &src->val, list) {
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100981 callchain_cursor_append(cursor, list->ip,
Jin Yao410024d2016-10-31 09:19:49 +0800982 list->ms.map, list->ms.sym,
Jin Yaob851dd42017-07-18 20:13:15 +0800983 false, NULL, 0, 0, 0);
Frederic Weisbecker612d4fd2010-08-22 21:10:35 +0200984 list_del(&list->list);
Krister Johansen9c68ae92017-01-05 22:23:31 -0800985 map__zput(list->ms.map);
Frederic Weisbecker612d4fd2010-08-22 21:10:35 +0200986 free(list);
987 }
988
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100989 if (src->hit) {
990 callchain_cursor_commit(cursor);
Namhyung Kimdca0d122016-02-16 23:08:24 +0900991 if (append_chain_children(dst, cursor, src->hit) < 0)
992 return -1;
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +0100993 }
Frederic Weisbecker612d4fd2010-08-22 21:10:35 +0200994
Namhyung Kime3695172013-10-11 14:15:36 +0900995 n = rb_first(&src->rb_root_in);
996 while (n) {
997 child = container_of(n, struct callchain_node, rb_node_in);
998 n = rb_next(n);
999 rb_erase(&child->rb_node_in, &src->rb_root_in);
1000
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +01001001 err = merge_chain_branch(cursor, dst, child);
Frederic Weisbecker612d4fd2010-08-22 21:10:35 +02001002 if (err)
1003 break;
1004
Frederic Weisbecker612d4fd2010-08-22 21:10:35 +02001005 free(child);
1006 }
1007
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +01001008 cursor->nr = old_pos;
1009 cursor->last = old_last;
Frederic Weisbecker612d4fd2010-08-22 21:10:35 +02001010
1011 return err;
1012}
1013
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +01001014int callchain_merge(struct callchain_cursor *cursor,
1015 struct callchain_root *dst, struct callchain_root *src)
Frederic Weisbecker612d4fd2010-08-22 21:10:35 +02001016{
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +01001017 return merge_chain_branch(cursor, &dst->node, &src->node);
1018}
Frederic Weisbecker612d4fd2010-08-22 21:10:35 +02001019
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +01001020int callchain_cursor_append(struct callchain_cursor *cursor,
Jin Yao410024d2016-10-31 09:19:49 +08001021 u64 ip, struct map *map, struct symbol *sym,
1022 bool branch, struct branch_flags *flags,
Jin Yaoc4ee0622017-08-07 21:05:15 +08001023 int nr_loop_iter, u64 iter_cycles, u64 branch_from)
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +01001024{
1025 struct callchain_cursor_node *node = *cursor->last;
Frederic Weisbecker612d4fd2010-08-22 21:10:35 +02001026
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +01001027 if (!node) {
Paul Gortmaker91b98802013-01-30 20:05:49 -05001028 node = calloc(1, sizeof(*node));
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +01001029 if (!node)
1030 return -ENOMEM;
Frederic Weisbecker612d4fd2010-08-22 21:10:35 +02001031
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +01001032 *cursor->last = node;
1033 }
Frederic Weisbecker612d4fd2010-08-22 21:10:35 +02001034
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +01001035 node->ip = ip;
Krister Johansen9c68ae92017-01-05 22:23:31 -08001036 map__zput(node->map);
1037 node->map = map__get(map);
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +01001038 node->sym = sym;
Jin Yao410024d2016-10-31 09:19:49 +08001039 node->branch = branch;
1040 node->nr_loop_iter = nr_loop_iter;
Jin Yaoc4ee0622017-08-07 21:05:15 +08001041 node->iter_cycles = iter_cycles;
Jin Yao410024d2016-10-31 09:19:49 +08001042
1043 if (flags)
1044 memcpy(&node->branch_flags, flags,
1045 sizeof(struct branch_flags));
Frederic Weisbecker612d4fd2010-08-22 21:10:35 +02001046
Jin Yaob851dd42017-07-18 20:13:15 +08001047 node->branch_from = branch_from;
Frederic Weisbecker1b3a0e92011-01-14 04:51:58 +01001048 cursor->nr++;
1049
1050 cursor->last = &node->next;
1051
1052 return 0;
Frederic Weisbecker612d4fd2010-08-22 21:10:35 +02001053}
Namhyung Kim2dc9fb12014-01-14 14:25:35 +09001054
Arnaldo Carvalho de Melo91d7b2d2016-04-14 14:48:07 -03001055int sample__resolve_callchain(struct perf_sample *sample,
1056 struct callchain_cursor *cursor, struct symbol **parent,
Namhyung Kim2dc9fb12014-01-14 14:25:35 +09001057 struct perf_evsel *evsel, struct addr_location *al,
1058 int max_stack)
1059{
Jin Yaob49a8212017-05-08 18:43:02 +08001060 if (sample->callchain == NULL && !symbol_conf.show_branchflag_count)
Namhyung Kim2dc9fb12014-01-14 14:25:35 +09001061 return 0;
1062
Namhyung Kim7a13aa22012-09-11 14:13:04 +09001063 if (symbol_conf.use_callchain || symbol_conf.cumulate_callchain ||
Jin Yaob49a8212017-05-08 18:43:02 +08001064 perf_hpp_list.parent || symbol_conf.show_branchflag_count) {
Arnaldo Carvalho de Melo91d7b2d2016-04-14 14:48:07 -03001065 return thread__resolve_callchain(al->thread, cursor, evsel, sample,
Arnaldo Carvalho de Melocc8b7c22014-10-23 15:26:17 -03001066 parent, al, max_stack);
Namhyung Kim2dc9fb12014-01-14 14:25:35 +09001067 }
1068 return 0;
1069}
1070
1071int hist_entry__append_callchain(struct hist_entry *he, struct perf_sample *sample)
1072{
Jin Yaob49a8212017-05-08 18:43:02 +08001073 if ((!symbol_conf.use_callchain || sample->callchain == NULL) &&
1074 !symbol_conf.show_branchflag_count)
Namhyung Kim2dc9fb12014-01-14 14:25:35 +09001075 return 0;
1076 return callchain_append(he->callchain, &callchain_cursor, sample->period);
1077}
Namhyung Kimc7405d82013-10-31 13:58:30 +09001078
1079int fill_callchain_info(struct addr_location *al, struct callchain_cursor_node *node,
1080 bool hide_unresolved)
1081{
1082 al->map = node->map;
1083 al->sym = node->sym;
1084 if (node->map)
1085 al->addr = node->map->map_ip(node->map, node->ip);
1086 else
1087 al->addr = node->ip;
1088
1089 if (al->sym == NULL) {
1090 if (hide_unresolved)
1091 return 0;
1092 if (al->map == NULL)
1093 goto out;
1094 }
1095
1096 if (al->map->groups == &al->machine->kmaps) {
1097 if (machine__is_host(al->machine)) {
1098 al->cpumode = PERF_RECORD_MISC_KERNEL;
1099 al->level = 'k';
1100 } else {
1101 al->cpumode = PERF_RECORD_MISC_GUEST_KERNEL;
1102 al->level = 'g';
1103 }
1104 } else {
1105 if (machine__is_host(al->machine)) {
1106 al->cpumode = PERF_RECORD_MISC_USER;
1107 al->level = '.';
1108 } else if (perf_guest) {
1109 al->cpumode = PERF_RECORD_MISC_GUEST_USER;
1110 al->level = 'u';
1111 } else {
1112 al->cpumode = PERF_RECORD_MISC_HYPERVISOR;
1113 al->level = 'H';
1114 }
1115 }
1116
1117out:
1118 return 1;
1119}
Andi Kleen2989cca2014-11-12 18:05:23 -08001120
1121char *callchain_list__sym_name(struct callchain_list *cl,
1122 char *bf, size_t bfsize, bool show_dso)
1123{
Milian Wolff5dfa2102017-03-18 22:49:28 +01001124 bool show_addr = callchain_param.key == CCKEY_ADDRESS;
1125 bool show_srcline = show_addr || callchain_param.key == CCKEY_SRCLINE;
Andi Kleen2989cca2014-11-12 18:05:23 -08001126 int printed;
1127
1128 if (cl->ms.sym) {
Milian Wolff5dfa2102017-03-18 22:49:28 +01001129 if (show_srcline && cl->ms.map && !cl->srcline)
Andi Kleen23f09812014-11-12 18:05:24 -08001130 cl->srcline = get_srcline(cl->ms.map->dso,
1131 map__rip_2objdump(cl->ms.map,
Andi Kleen85c116a2014-11-12 18:05:27 -08001132 cl->ip),
Milian Wolff5dfa2102017-03-18 22:49:28 +01001133 cl->ms.sym, false, show_addr);
Andi Kleen23f09812014-11-12 18:05:24 -08001134 if (cl->srcline)
1135 printed = scnprintf(bf, bfsize, "%s %s",
1136 cl->ms.sym->name, cl->srcline);
1137 else
1138 printed = scnprintf(bf, bfsize, "%s", cl->ms.sym->name);
Andi Kleen2989cca2014-11-12 18:05:23 -08001139 } else
1140 printed = scnprintf(bf, bfsize, "%#" PRIx64, cl->ip);
1141
1142 if (show_dso)
1143 scnprintf(bf + printed, bfsize - printed, " %s",
1144 cl->ms.map ?
1145 cl->ms.map->dso->short_name :
1146 "unknown");
1147
1148 return bf;
1149}
Namhyung Kimd1149602014-12-30 14:38:13 +09001150
Namhyung Kim5ab250c2015-11-09 14:45:39 +09001151char *callchain_node__scnprintf_value(struct callchain_node *node,
1152 char *bf, size_t bfsize, u64 total)
1153{
1154 double percent = 0.0;
1155 u64 period = callchain_cumul_hits(node);
Namhyung Kimf2af0082015-11-09 14:45:41 +09001156 unsigned count = callchain_cumul_counts(node);
Namhyung Kim5ab250c2015-11-09 14:45:39 +09001157
Namhyung Kimf2af0082015-11-09 14:45:41 +09001158 if (callchain_param.mode == CHAIN_FOLDED) {
Namhyung Kim5ab250c2015-11-09 14:45:39 +09001159 period = node->hit;
Namhyung Kimf2af0082015-11-09 14:45:41 +09001160 count = node->count;
1161 }
Namhyung Kim5ab250c2015-11-09 14:45:39 +09001162
Namhyung Kimf2af0082015-11-09 14:45:41 +09001163 switch (callchain_param.value) {
1164 case CCVAL_PERIOD:
1165 scnprintf(bf, bfsize, "%"PRIu64, period);
1166 break;
1167 case CCVAL_COUNT:
1168 scnprintf(bf, bfsize, "%u", count);
1169 break;
1170 case CCVAL_PERCENT:
1171 default:
1172 if (total)
1173 percent = period * 100.0 / total;
1174 scnprintf(bf, bfsize, "%.2f%%", percent);
1175 break;
1176 }
Namhyung Kim5ab250c2015-11-09 14:45:39 +09001177 return bf;
1178}
1179
1180int callchain_node__fprintf_value(struct callchain_node *node,
1181 FILE *fp, u64 total)
1182{
1183 double percent = 0.0;
1184 u64 period = callchain_cumul_hits(node);
Namhyung Kimf2af0082015-11-09 14:45:41 +09001185 unsigned count = callchain_cumul_counts(node);
Namhyung Kim5ab250c2015-11-09 14:45:39 +09001186
Namhyung Kimf2af0082015-11-09 14:45:41 +09001187 if (callchain_param.mode == CHAIN_FOLDED) {
Namhyung Kim5ab250c2015-11-09 14:45:39 +09001188 period = node->hit;
Namhyung Kimf2af0082015-11-09 14:45:41 +09001189 count = node->count;
1190 }
Namhyung Kim5ab250c2015-11-09 14:45:39 +09001191
Namhyung Kimf2af0082015-11-09 14:45:41 +09001192 switch (callchain_param.value) {
1193 case CCVAL_PERIOD:
1194 return fprintf(fp, "%"PRIu64, period);
1195 case CCVAL_COUNT:
1196 return fprintf(fp, "%u", count);
1197 case CCVAL_PERCENT:
1198 default:
1199 if (total)
1200 percent = period * 100.0 / total;
1201 return percent_color_fprintf(fp, "%.2f%%", percent);
1202 }
1203 return 0;
Namhyung Kim5ab250c2015-11-09 14:45:39 +09001204}
1205
Jin Yao3dd029e2016-10-31 09:19:51 +08001206static void callchain_counts_value(struct callchain_node *node,
1207 u64 *branch_count, u64 *predicted_count,
1208 u64 *abort_count, u64 *cycles_count)
1209{
1210 struct callchain_list *clist;
1211
1212 list_for_each_entry(clist, &node->val, list) {
1213 if (branch_count)
1214 *branch_count += clist->branch_count;
1215
1216 if (predicted_count)
1217 *predicted_count += clist->predicted_count;
1218
1219 if (abort_count)
1220 *abort_count += clist->abort_count;
1221
1222 if (cycles_count)
1223 *cycles_count += clist->cycles_count;
1224 }
1225}
1226
1227static int callchain_node_branch_counts_cumul(struct callchain_node *node,
1228 u64 *branch_count,
1229 u64 *predicted_count,
1230 u64 *abort_count,
1231 u64 *cycles_count)
1232{
1233 struct callchain_node *child;
1234 struct rb_node *n;
1235
1236 n = rb_first(&node->rb_root_in);
1237 while (n) {
1238 child = rb_entry(n, struct callchain_node, rb_node_in);
1239 n = rb_next(n);
1240
1241 callchain_node_branch_counts_cumul(child, branch_count,
1242 predicted_count,
1243 abort_count,
1244 cycles_count);
1245
1246 callchain_counts_value(child, branch_count,
1247 predicted_count, abort_count,
1248 cycles_count);
1249 }
1250
1251 return 0;
1252}
1253
1254int callchain_branch_counts(struct callchain_root *root,
1255 u64 *branch_count, u64 *predicted_count,
1256 u64 *abort_count, u64 *cycles_count)
1257{
1258 if (branch_count)
1259 *branch_count = 0;
1260
1261 if (predicted_count)
1262 *predicted_count = 0;
1263
1264 if (abort_count)
1265 *abort_count = 0;
1266
1267 if (cycles_count)
1268 *cycles_count = 0;
1269
1270 return callchain_node_branch_counts_cumul(&root->node,
1271 branch_count,
1272 predicted_count,
1273 abort_count,
1274 cycles_count);
1275}
1276
Jin Yao8d517352017-07-18 20:13:12 +08001277static int count_pri64_printf(int idx, const char *str, u64 value, char *bf, int bfsize)
1278{
1279 int printed;
1280
1281 printed = scnprintf(bf, bfsize, "%s%s:%" PRId64 "", (idx) ? " " : " (", str, value);
1282
1283 return printed;
1284}
1285
Jin Yaoa1a8bed2017-07-24 19:09:07 +08001286static int count_float_printf(int idx, const char *str, float value,
1287 char *bf, int bfsize, float threshold)
Jin Yao8d517352017-07-18 20:13:12 +08001288{
1289 int printed;
1290
Jin Yaoa1a8bed2017-07-24 19:09:07 +08001291 if (threshold != 0.0 && value < threshold)
1292 return 0;
1293
Jin Yao8d517352017-07-18 20:13:12 +08001294 printed = scnprintf(bf, bfsize, "%s%s:%.1f%%", (idx) ? " " : " (", str, value);
1295
1296 return printed;
1297}
1298
Jin Yaoa1a8bed2017-07-24 19:09:07 +08001299static int branch_to_str(char *bf, int bfsize,
1300 u64 branch_count, u64 predicted_count,
1301 u64 abort_count,
1302 struct branch_type_stat *brtype_stat)
Jin Yaoc1dfcfa2017-03-09 16:06:26 +08001303{
Jin Yaob851dd42017-07-18 20:13:15 +08001304 int printed, i = 0;
Jin Yaoc1dfcfa2017-03-09 16:06:26 +08001305
Jin Yaob851dd42017-07-18 20:13:15 +08001306 printed = branch_type_str(brtype_stat, bf, bfsize);
1307 if (printed)
1308 i++;
1309
Jin Yao8d517352017-07-18 20:13:12 +08001310 if (predicted_count < branch_count) {
1311 printed += count_float_printf(i++, "predicted",
1312 predicted_count * 100.0 / branch_count,
Jin Yaoa1a8bed2017-07-24 19:09:07 +08001313 bf + printed, bfsize - printed, 0.0);
Jin Yao8d517352017-07-18 20:13:12 +08001314 }
1315
1316 if (abort_count) {
1317 printed += count_float_printf(i++, "abort",
1318 abort_count * 100.0 / branch_count,
Jin Yaoa1a8bed2017-07-24 19:09:07 +08001319 bf + printed, bfsize - printed, 0.1);
Jin Yao8d517352017-07-18 20:13:12 +08001320 }
1321
Jin Yaoa1a8bed2017-07-24 19:09:07 +08001322 if (i)
1323 printed += scnprintf(bf + printed, bfsize - printed, ")");
1324
1325 return printed;
1326}
1327
1328static int branch_from_str(char *bf, int bfsize,
1329 u64 branch_count,
1330 u64 cycles_count, u64 iter_count,
Jin Yaoc4ee0622017-08-07 21:05:15 +08001331 u64 iter_cycles)
Jin Yaoa1a8bed2017-07-24 19:09:07 +08001332{
1333 int printed = 0, i = 0;
1334 u64 cycles;
1335
Jin Yaoc1dfcfa2017-03-09 16:06:26 +08001336 cycles = cycles_count / branch_count;
Jin Yao8d517352017-07-18 20:13:12 +08001337 if (cycles) {
1338 printed += count_pri64_printf(i++, "cycles",
1339 cycles,
1340 bf + printed, bfsize - printed);
1341 }
Jin Yaoc1dfcfa2017-03-09 16:06:26 +08001342
Jin Yaoc4ee0622017-08-07 21:05:15 +08001343 if (iter_count) {
1344 printed += count_pri64_printf(i++, "iter",
1345 iter_count,
1346 bf + printed, bfsize - printed);
1347
1348 printed += count_pri64_printf(i++, "avg_cycles",
1349 iter_cycles / iter_count,
Jin Yao8d517352017-07-18 20:13:12 +08001350 bf + printed, bfsize - printed);
Jin Yaoc1dfcfa2017-03-09 16:06:26 +08001351 }
1352
Jin Yao8d517352017-07-18 20:13:12 +08001353 if (i)
Jin Yaoa1a8bed2017-07-24 19:09:07 +08001354 printed += scnprintf(bf + printed, bfsize - printed, ")");
Jin Yaoc1dfcfa2017-03-09 16:06:26 +08001355
Jin Yaoa1a8bed2017-07-24 19:09:07 +08001356 return printed;
1357}
1358
1359static int counts_str_build(char *bf, int bfsize,
1360 u64 branch_count, u64 predicted_count,
1361 u64 abort_count, u64 cycles_count,
Jin Yaoc4ee0622017-08-07 21:05:15 +08001362 u64 iter_count, u64 iter_cycles,
Jin Yaoa1a8bed2017-07-24 19:09:07 +08001363 struct branch_type_stat *brtype_stat)
1364{
1365 int printed;
1366
1367 if (branch_count == 0)
1368 return scnprintf(bf, bfsize, " (calltrace)");
1369
1370 if (brtype_stat->branch_to) {
1371 printed = branch_to_str(bf, bfsize, branch_count,
1372 predicted_count, abort_count, brtype_stat);
1373 } else {
1374 printed = branch_from_str(bf, bfsize, branch_count,
Jin Yaoc4ee0622017-08-07 21:05:15 +08001375 cycles_count, iter_count, iter_cycles);
Jin Yaoa1a8bed2017-07-24 19:09:07 +08001376 }
1377
1378 if (!printed)
1379 bf[0] = 0;
1380
1381 return printed;
Jin Yaoc1dfcfa2017-03-09 16:06:26 +08001382}
1383
Jin Yao3dd029e2016-10-31 09:19:51 +08001384static int callchain_counts_printf(FILE *fp, char *bf, int bfsize,
1385 u64 branch_count, u64 predicted_count,
1386 u64 abort_count, u64 cycles_count,
Jin Yaoc4ee0622017-08-07 21:05:15 +08001387 u64 iter_count, u64 iter_cycles,
Jin Yaob851dd42017-07-18 20:13:15 +08001388 struct branch_type_stat *brtype_stat)
Jin Yao3dd029e2016-10-31 09:19:51 +08001389{
Jin Yaob851dd42017-07-18 20:13:15 +08001390 char str[256];
Jin Yao3dd029e2016-10-31 09:19:51 +08001391
Jin Yaoc1dfcfa2017-03-09 16:06:26 +08001392 counts_str_build(str, sizeof(str), branch_count,
1393 predicted_count, abort_count, cycles_count,
Jin Yaoc4ee0622017-08-07 21:05:15 +08001394 iter_count, iter_cycles, brtype_stat);
Jin Yao3dd029e2016-10-31 09:19:51 +08001395
1396 if (fp)
Jin Yaoc1dfcfa2017-03-09 16:06:26 +08001397 return fprintf(fp, "%s", str);
Jin Yao3dd029e2016-10-31 09:19:51 +08001398
Jin Yaoc1dfcfa2017-03-09 16:06:26 +08001399 return scnprintf(bf, bfsize, "%s", str);
Jin Yao3dd029e2016-10-31 09:19:51 +08001400}
1401
Jin Yaoc4ee0622017-08-07 21:05:15 +08001402int callchain_list_counts__printf_value(struct callchain_list *clist,
Jin Yao3dd029e2016-10-31 09:19:51 +08001403 FILE *fp, char *bf, int bfsize)
1404{
1405 u64 branch_count, predicted_count;
1406 u64 abort_count, cycles_count;
Jin Yaoc4ee0622017-08-07 21:05:15 +08001407 u64 iter_count, iter_cycles;
Jin Yao3dd029e2016-10-31 09:19:51 +08001408
1409 branch_count = clist->branch_count;
1410 predicted_count = clist->predicted_count;
1411 abort_count = clist->abort_count;
1412 cycles_count = clist->cycles_count;
Jin Yaoc4ee0622017-08-07 21:05:15 +08001413 iter_count = clist->iter_count;
1414 iter_cycles = clist->iter_cycles;
Jin Yao3dd029e2016-10-31 09:19:51 +08001415
1416 return callchain_counts_printf(fp, bf, bfsize, branch_count,
1417 predicted_count, abort_count,
Jin Yaoc4ee0622017-08-07 21:05:15 +08001418 cycles_count, iter_count, iter_cycles,
Jin Yaob851dd42017-07-18 20:13:15 +08001419 &clist->brtype_stat);
Jin Yao3dd029e2016-10-31 09:19:51 +08001420}
1421
Namhyung Kimd1149602014-12-30 14:38:13 +09001422static void free_callchain_node(struct callchain_node *node)
1423{
1424 struct callchain_list *list, *tmp;
1425 struct callchain_node *child;
1426 struct rb_node *n;
1427
Namhyung Kim4b3a3212015-11-09 14:45:43 +09001428 list_for_each_entry_safe(list, tmp, &node->parent_val, list) {
1429 list_del(&list->list);
Krister Johansen9c68ae92017-01-05 22:23:31 -08001430 map__zput(list->ms.map);
Namhyung Kim4b3a3212015-11-09 14:45:43 +09001431 free(list);
1432 }
1433
Namhyung Kimd1149602014-12-30 14:38:13 +09001434 list_for_each_entry_safe(list, tmp, &node->val, list) {
1435 list_del(&list->list);
Krister Johansen9c68ae92017-01-05 22:23:31 -08001436 map__zput(list->ms.map);
Namhyung Kimd1149602014-12-30 14:38:13 +09001437 free(list);
1438 }
1439
1440 n = rb_first(&node->rb_root_in);
1441 while (n) {
1442 child = container_of(n, struct callchain_node, rb_node_in);
1443 n = rb_next(n);
1444 rb_erase(&child->rb_node_in, &node->rb_root_in);
1445
1446 free_callchain_node(child);
1447 free(child);
1448 }
1449}
1450
1451void free_callchain(struct callchain_root *root)
1452{
1453 if (!symbol_conf.use_callchain)
1454 return;
1455
1456 free_callchain_node(&root->node);
1457}
Namhyung Kim4b3a3212015-11-09 14:45:43 +09001458
Namhyung Kim42b276a2016-01-05 12:06:00 +09001459static u64 decay_callchain_node(struct callchain_node *node)
1460{
1461 struct callchain_node *child;
1462 struct rb_node *n;
1463 u64 child_hits = 0;
1464
1465 n = rb_first(&node->rb_root_in);
1466 while (n) {
1467 child = container_of(n, struct callchain_node, rb_node_in);
1468
1469 child_hits += decay_callchain_node(child);
1470 n = rb_next(n);
1471 }
1472
1473 node->hit = (node->hit * 7) / 8;
1474 node->children_hit = child_hits;
1475
1476 return node->hit;
1477}
1478
1479void decay_callchain(struct callchain_root *root)
1480{
1481 if (!symbol_conf.use_callchain)
1482 return;
1483
1484 decay_callchain_node(&root->node);
1485}
1486
Namhyung Kim4b3a3212015-11-09 14:45:43 +09001487int callchain_node__make_parent_list(struct callchain_node *node)
1488{
1489 struct callchain_node *parent = node->parent;
1490 struct callchain_list *chain, *new;
1491 LIST_HEAD(head);
1492
1493 while (parent) {
1494 list_for_each_entry_reverse(chain, &parent->val, list) {
1495 new = malloc(sizeof(*new));
1496 if (new == NULL)
1497 goto out;
1498 *new = *chain;
1499 new->has_children = false;
Krister Johansen9c68ae92017-01-05 22:23:31 -08001500 map__get(new->ms.map);
Namhyung Kim4b3a3212015-11-09 14:45:43 +09001501 list_add_tail(&new->list, &head);
1502 }
1503 parent = parent->parent;
1504 }
1505
1506 list_for_each_entry_safe_reverse(chain, new, &head, list)
1507 list_move_tail(&chain->list, &node->parent_val);
1508
1509 if (!list_empty(&node->parent_val)) {
1510 chain = list_first_entry(&node->parent_val, struct callchain_list, list);
1511 chain->has_children = rb_prev(&node->rb_node) || rb_next(&node->rb_node);
1512
1513 chain = list_first_entry(&node->val, struct callchain_list, list);
1514 chain->has_children = false;
1515 }
1516 return 0;
1517
1518out:
1519 list_for_each_entry_safe(chain, new, &head, list) {
1520 list_del(&chain->list);
Krister Johansen9c68ae92017-01-05 22:23:31 -08001521 map__zput(chain->ms.map);
Namhyung Kim4b3a3212015-11-09 14:45:43 +09001522 free(chain);
1523 }
1524 return -ENOMEM;
1525}
Namhyung Kim571f1eb2016-12-06 12:40:02 +09001526
1527int callchain_cursor__copy(struct callchain_cursor *dst,
1528 struct callchain_cursor *src)
1529{
1530 int rc = 0;
1531
1532 callchain_cursor_reset(dst);
1533 callchain_cursor_commit(src);
1534
1535 while (true) {
1536 struct callchain_cursor_node *node;
1537
1538 node = callchain_cursor_current(src);
1539 if (node == NULL)
1540 break;
1541
1542 rc = callchain_cursor_append(dst, node->ip, node->map, node->sym,
1543 node->branch, &node->branch_flags,
Jin Yaoc4ee0622017-08-07 21:05:15 +08001544 node->nr_loop_iter,
1545 node->iter_cycles,
Jin Yaob851dd42017-07-18 20:13:15 +08001546 node->branch_from);
Namhyung Kim571f1eb2016-12-06 12:40:02 +09001547 if (rc)
1548 break;
1549
1550 callchain_cursor_advance(src);
1551 }
1552
1553 return rc;
1554}