Greg Kroah-Hartman | b244131 | 2017-11-01 15:07:57 +0100 | [diff] [blame] | 1 | // SPDX-License-Identifier: GPL-2.0 |
Frederic Weisbecker | 8cb76d9 | 2009-06-26 16:28:00 +0200 | [diff] [blame] | 2 | /* |
Frederic Weisbecker | 1b3a0e9 | 2011-01-14 04:51:58 +0100 | [diff] [blame] | 3 | * Copyright (C) 2009-2011, Frederic Weisbecker <fweisbec@gmail.com> |
Frederic Weisbecker | 8cb76d9 | 2009-06-26 16:28:00 +0200 | [diff] [blame] | 4 | * |
| 5 | * Handle the callchains from the stream in an ad-hoc radix tree and then |
| 6 | * sort them in an rbtree. |
| 7 | * |
Frederic Weisbecker | deac911 | 2009-07-01 05:35:15 +0200 | [diff] [blame] | 8 | * Using a radix for code path provides a fast retrieval and factorizes |
| 9 | * memory use. Also that lets us use the paths in a hierarchical graph view. |
| 10 | * |
Frederic Weisbecker | 8cb76d9 | 2009-06-26 16:28:00 +0200 | [diff] [blame] | 11 | */ |
| 12 | |
Arnaldo Carvalho de Melo | fd20e81 | 2017-04-17 15:23:08 -0300 | [diff] [blame] | 13 | #include <inttypes.h> |
Frederic Weisbecker | 8cb76d9 | 2009-06-26 16:28:00 +0200 | [diff] [blame] | 14 | #include <stdlib.h> |
| 15 | #include <stdio.h> |
| 16 | #include <stdbool.h> |
| 17 | #include <errno.h> |
Frederic Weisbecker | c0a8865 | 2009-08-09 04:19:15 +0200 | [diff] [blame] | 18 | #include <math.h> |
Frederic Weisbecker | 8cb76d9 | 2009-06-26 16:28:00 +0200 | [diff] [blame] | 19 | |
Frederic Weisbecker | b965bb4 | 2014-01-14 16:37:15 +0100 | [diff] [blame] | 20 | #include "asm/bug.h" |
| 21 | |
Andi Kleen | 99571ab | 2013-07-18 15:33:57 -0700 | [diff] [blame] | 22 | #include "hist.h" |
Arnaldo Carvalho de Melo | b36f19d | 2010-05-20 12:15:33 -0300 | [diff] [blame] | 23 | #include "util.h" |
Namhyung Kim | 2dc9fb1 | 2014-01-14 14:25:35 +0900 | [diff] [blame] | 24 | #include "sort.h" |
| 25 | #include "machine.h" |
Frederic Weisbecker | 8cb76d9 | 2009-06-26 16:28:00 +0200 | [diff] [blame] | 26 | #include "callchain.h" |
Jin Yao | b851dd4 | 2017-07-18 20:13:15 +0800 | [diff] [blame] | 27 | #include "branch.h" |
Frederic Weisbecker | 8cb76d9 | 2009-06-26 16:28:00 +0200 | [diff] [blame] | 28 | |
Arnaldo Carvalho de Melo | 56e2e05 | 2017-04-19 18:38:33 -0300 | [diff] [blame] | 29 | #define CALLCHAIN_PARAM_DEFAULT \ |
| 30 | .mode = CHAIN_GRAPH_ABS, \ |
| 31 | .min_percent = 0.5, \ |
| 32 | .order = ORDER_CALLEE, \ |
| 33 | .key = CCKEY_FUNCTION, \ |
| 34 | .value = CCVAL_PERCENT, \ |
| 35 | |
| 36 | struct callchain_param callchain_param = { |
| 37 | CALLCHAIN_PARAM_DEFAULT |
| 38 | }; |
| 39 | |
Arnaldo Carvalho de Melo | 0eda4d0 | 2018-01-15 16:48:46 -0300 | [diff] [blame] | 40 | /* |
| 41 | * Are there any events usind DWARF callchains? |
| 42 | * |
| 43 | * I.e. |
| 44 | * |
| 45 | * -e cycles/call-graph=dwarf/ |
| 46 | */ |
| 47 | bool dwarf_callchain_users; |
| 48 | |
Arnaldo Carvalho de Melo | 56e2e05 | 2017-04-19 18:38:33 -0300 | [diff] [blame] | 49 | struct callchain_param callchain_param_default = { |
| 50 | CALLCHAIN_PARAM_DEFAULT |
| 51 | }; |
| 52 | |
Namhyung Kim | 4726064 | 2012-05-31 14:43:26 +0900 | [diff] [blame] | 53 | __thread struct callchain_cursor callchain_cursor; |
| 54 | |
Kan Liang | c3a6a8c | 2015-08-04 04:30:20 -0400 | [diff] [blame] | 55 | int parse_callchain_record_opt(const char *arg, struct callchain_param *param) |
Namhyung Kim | f7f084f | 2014-09-23 10:01:42 +0900 | [diff] [blame] | 56 | { |
Kan Liang | 076a30c | 2015-08-06 15:44:52 -0400 | [diff] [blame] | 57 | return parse_callchain_record(arg, param); |
Namhyung Kim | f7f084f | 2014-09-23 10:01:42 +0900 | [diff] [blame] | 58 | } |
| 59 | |
Namhyung Kim | 2b9240c | 2014-09-23 10:01:43 +0900 | [diff] [blame] | 60 | static int parse_callchain_mode(const char *value) |
| 61 | { |
| 62 | if (!strncmp(value, "graph", strlen(value))) { |
| 63 | callchain_param.mode = CHAIN_GRAPH_ABS; |
| 64 | return 0; |
| 65 | } |
| 66 | if (!strncmp(value, "flat", strlen(value))) { |
| 67 | callchain_param.mode = CHAIN_FLAT; |
| 68 | return 0; |
| 69 | } |
| 70 | if (!strncmp(value, "fractal", strlen(value))) { |
| 71 | callchain_param.mode = CHAIN_GRAPH_REL; |
| 72 | return 0; |
| 73 | } |
Namhyung Kim | 26e7792 | 2015-11-09 14:45:37 +0900 | [diff] [blame] | 74 | if (!strncmp(value, "folded", strlen(value))) { |
| 75 | callchain_param.mode = CHAIN_FOLDED; |
| 76 | return 0; |
| 77 | } |
Namhyung Kim | 2b9240c | 2014-09-23 10:01:43 +0900 | [diff] [blame] | 78 | return -1; |
| 79 | } |
| 80 | |
| 81 | static int parse_callchain_order(const char *value) |
| 82 | { |
| 83 | if (!strncmp(value, "caller", strlen(value))) { |
| 84 | callchain_param.order = ORDER_CALLER; |
Namhyung Kim | 792aeaf | 2015-10-22 16:45:46 +0900 | [diff] [blame] | 85 | callchain_param.order_set = true; |
Namhyung Kim | 2b9240c | 2014-09-23 10:01:43 +0900 | [diff] [blame] | 86 | return 0; |
| 87 | } |
| 88 | if (!strncmp(value, "callee", strlen(value))) { |
| 89 | callchain_param.order = ORDER_CALLEE; |
Namhyung Kim | 792aeaf | 2015-10-22 16:45:46 +0900 | [diff] [blame] | 90 | callchain_param.order_set = true; |
Namhyung Kim | 2b9240c | 2014-09-23 10:01:43 +0900 | [diff] [blame] | 91 | return 0; |
| 92 | } |
| 93 | return -1; |
| 94 | } |
| 95 | |
| 96 | static int parse_callchain_sort_key(const char *value) |
| 97 | { |
| 98 | if (!strncmp(value, "function", strlen(value))) { |
| 99 | callchain_param.key = CCKEY_FUNCTION; |
| 100 | return 0; |
| 101 | } |
| 102 | if (!strncmp(value, "address", strlen(value))) { |
| 103 | callchain_param.key = CCKEY_ADDRESS; |
| 104 | return 0; |
| 105 | } |
Milian Wolff | 5dfa210 | 2017-03-18 22:49:28 +0100 | [diff] [blame] | 106 | if (!strncmp(value, "srcline", strlen(value))) { |
| 107 | callchain_param.key = CCKEY_SRCLINE; |
| 108 | return 0; |
| 109 | } |
Andi Kleen | 8b7bad5 | 2014-11-12 18:05:20 -0800 | [diff] [blame] | 110 | if (!strncmp(value, "branch", strlen(value))) { |
| 111 | callchain_param.branch_callstack = 1; |
| 112 | return 0; |
| 113 | } |
Namhyung Kim | 2b9240c | 2014-09-23 10:01:43 +0900 | [diff] [blame] | 114 | return -1; |
| 115 | } |
| 116 | |
Namhyung Kim | f2af008 | 2015-11-09 14:45:41 +0900 | [diff] [blame] | 117 | static int parse_callchain_value(const char *value) |
| 118 | { |
| 119 | if (!strncmp(value, "percent", strlen(value))) { |
| 120 | callchain_param.value = CCVAL_PERCENT; |
| 121 | return 0; |
| 122 | } |
| 123 | if (!strncmp(value, "period", strlen(value))) { |
| 124 | callchain_param.value = CCVAL_PERIOD; |
| 125 | return 0; |
| 126 | } |
| 127 | if (!strncmp(value, "count", strlen(value))) { |
| 128 | callchain_param.value = CCVAL_COUNT; |
| 129 | return 0; |
| 130 | } |
| 131 | return -1; |
| 132 | } |
| 133 | |
Arnaldo Carvalho de Melo | 56e2e05 | 2017-04-19 18:38:33 -0300 | [diff] [blame] | 134 | static int get_stack_size(const char *str, unsigned long *_size) |
| 135 | { |
| 136 | char *endptr; |
| 137 | unsigned long size; |
| 138 | unsigned long max_size = round_down(USHRT_MAX, sizeof(u64)); |
| 139 | |
| 140 | size = strtoul(str, &endptr, 0); |
| 141 | |
| 142 | do { |
| 143 | if (*endptr) |
| 144 | break; |
| 145 | |
| 146 | size = round_up(size, sizeof(u64)); |
| 147 | if (!size || size > max_size) |
| 148 | break; |
| 149 | |
| 150 | *_size = size; |
| 151 | return 0; |
| 152 | |
| 153 | } while (0); |
| 154 | |
| 155 | pr_err("callchain: Incorrect stack dump size (max %ld): %s\n", |
| 156 | max_size, str); |
| 157 | return -1; |
| 158 | } |
| 159 | |
Namhyung Kim | a2c10d3 | 2015-10-22 15:28:49 +0900 | [diff] [blame] | 160 | static int |
| 161 | __parse_callchain_report_opt(const char *arg, bool allow_record_opt) |
Don Zickus | cff6bb4 | 2014-04-07 14:55:24 -0400 | [diff] [blame] | 162 | { |
Namhyung Kim | e8232f1 | 2014-08-14 15:01:38 +0900 | [diff] [blame] | 163 | char *tok; |
Arnaldo Carvalho de Melo | dadafc3 | 2017-04-05 11:38:10 -0300 | [diff] [blame] | 164 | char *endptr, *saveptr = NULL; |
Namhyung Kim | e8232f1 | 2014-08-14 15:01:38 +0900 | [diff] [blame] | 165 | bool minpcnt_set = false; |
Namhyung Kim | a2c10d3 | 2015-10-22 15:28:49 +0900 | [diff] [blame] | 166 | bool record_opt_set = false; |
| 167 | bool try_stack_size = false; |
Don Zickus | cff6bb4 | 2014-04-07 14:55:24 -0400 | [diff] [blame] | 168 | |
Arnaldo Carvalho de Melo | 30234f0 | 2016-04-18 11:53:07 -0300 | [diff] [blame] | 169 | callchain_param.enabled = true; |
Don Zickus | cff6bb4 | 2014-04-07 14:55:24 -0400 | [diff] [blame] | 170 | symbol_conf.use_callchain = true; |
| 171 | |
| 172 | if (!arg) |
| 173 | return 0; |
| 174 | |
Arnaldo Carvalho de Melo | dadafc3 | 2017-04-05 11:38:10 -0300 | [diff] [blame] | 175 | while ((tok = strtok_r((char *)arg, ",", &saveptr)) != NULL) { |
Namhyung Kim | e8232f1 | 2014-08-14 15:01:38 +0900 | [diff] [blame] | 176 | if (!strncmp(tok, "none", strlen(tok))) { |
| 177 | callchain_param.mode = CHAIN_NONE; |
Arnaldo Carvalho de Melo | 30234f0 | 2016-04-18 11:53:07 -0300 | [diff] [blame] | 178 | callchain_param.enabled = false; |
Namhyung Kim | e8232f1 | 2014-08-14 15:01:38 +0900 | [diff] [blame] | 179 | symbol_conf.use_callchain = false; |
| 180 | return 0; |
| 181 | } |
Don Zickus | cff6bb4 | 2014-04-07 14:55:24 -0400 | [diff] [blame] | 182 | |
Namhyung Kim | 2b9240c | 2014-09-23 10:01:43 +0900 | [diff] [blame] | 183 | if (!parse_callchain_mode(tok) || |
| 184 | !parse_callchain_order(tok) || |
Namhyung Kim | f2af008 | 2015-11-09 14:45:41 +0900 | [diff] [blame] | 185 | !parse_callchain_sort_key(tok) || |
| 186 | !parse_callchain_value(tok)) { |
Namhyung Kim | 2b9240c | 2014-09-23 10:01:43 +0900 | [diff] [blame] | 187 | /* parsing ok - move on to the next */ |
Namhyung Kim | a2c10d3 | 2015-10-22 15:28:49 +0900 | [diff] [blame] | 188 | try_stack_size = false; |
| 189 | goto next; |
| 190 | } else if (allow_record_opt && !record_opt_set) { |
| 191 | if (parse_callchain_record(tok, &callchain_param)) |
| 192 | goto try_numbers; |
| 193 | |
| 194 | /* assume that number followed by 'dwarf' is stack size */ |
| 195 | if (callchain_param.record_mode == CALLCHAIN_DWARF) |
| 196 | try_stack_size = true; |
| 197 | |
| 198 | record_opt_set = true; |
| 199 | goto next; |
| 200 | } |
| 201 | |
| 202 | try_numbers: |
| 203 | if (try_stack_size) { |
| 204 | unsigned long size = 0; |
| 205 | |
| 206 | if (get_stack_size(tok, &size) < 0) |
| 207 | return -1; |
| 208 | callchain_param.dump_size = size; |
| 209 | try_stack_size = false; |
Namhyung Kim | 2b9240c | 2014-09-23 10:01:43 +0900 | [diff] [blame] | 210 | } else if (!minpcnt_set) { |
| 211 | /* try to get the min percent */ |
Namhyung Kim | e8232f1 | 2014-08-14 15:01:38 +0900 | [diff] [blame] | 212 | callchain_param.min_percent = strtod(tok, &endptr); |
| 213 | if (tok == endptr) |
| 214 | return -1; |
| 215 | minpcnt_set = true; |
| 216 | } else { |
| 217 | /* try print limit at last */ |
| 218 | callchain_param.print_limit = strtoul(tok, &endptr, 0); |
| 219 | if (tok == endptr) |
| 220 | return -1; |
| 221 | } |
Namhyung Kim | a2c10d3 | 2015-10-22 15:28:49 +0900 | [diff] [blame] | 222 | next: |
Namhyung Kim | e8232f1 | 2014-08-14 15:01:38 +0900 | [diff] [blame] | 223 | arg = NULL; |
Don Zickus | cff6bb4 | 2014-04-07 14:55:24 -0400 | [diff] [blame] | 224 | } |
| 225 | |
Don Zickus | cff6bb4 | 2014-04-07 14:55:24 -0400 | [diff] [blame] | 226 | if (callchain_register_param(&callchain_param) < 0) { |
| 227 | pr_err("Can't register callchain params\n"); |
| 228 | return -1; |
| 229 | } |
| 230 | return 0; |
| 231 | } |
| 232 | |
Namhyung Kim | a2c10d3 | 2015-10-22 15:28:49 +0900 | [diff] [blame] | 233 | int parse_callchain_report_opt(const char *arg) |
| 234 | { |
| 235 | return __parse_callchain_report_opt(arg, false); |
| 236 | } |
| 237 | |
| 238 | int parse_callchain_top_opt(const char *arg) |
| 239 | { |
| 240 | return __parse_callchain_report_opt(arg, true); |
| 241 | } |
| 242 | |
Arnaldo Carvalho de Melo | 56e2e05 | 2017-04-19 18:38:33 -0300 | [diff] [blame] | 243 | int parse_callchain_record(const char *arg, struct callchain_param *param) |
| 244 | { |
| 245 | char *tok, *name, *saveptr = NULL; |
| 246 | char *buf; |
| 247 | int ret = -1; |
| 248 | |
| 249 | /* We need buffer that we know we can write to. */ |
| 250 | buf = malloc(strlen(arg) + 1); |
| 251 | if (!buf) |
| 252 | return -ENOMEM; |
| 253 | |
| 254 | strcpy(buf, arg); |
| 255 | |
| 256 | tok = strtok_r((char *)buf, ",", &saveptr); |
| 257 | name = tok ? : (char *)buf; |
| 258 | |
| 259 | do { |
| 260 | /* Framepointer style */ |
| 261 | if (!strncmp(name, "fp", sizeof("fp"))) { |
| 262 | if (!strtok_r(NULL, ",", &saveptr)) { |
| 263 | param->record_mode = CALLCHAIN_FP; |
| 264 | ret = 0; |
| 265 | } else |
| 266 | pr_err("callchain: No more arguments " |
| 267 | "needed for --call-graph fp\n"); |
| 268 | break; |
| 269 | |
| 270 | /* Dwarf style */ |
| 271 | } else if (!strncmp(name, "dwarf", sizeof("dwarf"))) { |
| 272 | const unsigned long default_stack_dump_size = 8192; |
| 273 | |
| 274 | ret = 0; |
| 275 | param->record_mode = CALLCHAIN_DWARF; |
| 276 | param->dump_size = default_stack_dump_size; |
Arnaldo Carvalho de Melo | 0eda4d0 | 2018-01-15 16:48:46 -0300 | [diff] [blame] | 277 | dwarf_callchain_users = true; |
Arnaldo Carvalho de Melo | 56e2e05 | 2017-04-19 18:38:33 -0300 | [diff] [blame] | 278 | |
| 279 | tok = strtok_r(NULL, ",", &saveptr); |
| 280 | if (tok) { |
| 281 | unsigned long size = 0; |
| 282 | |
| 283 | ret = get_stack_size(tok, &size); |
| 284 | param->dump_size = size; |
| 285 | } |
| 286 | } else if (!strncmp(name, "lbr", sizeof("lbr"))) { |
| 287 | if (!strtok_r(NULL, ",", &saveptr)) { |
| 288 | param->record_mode = CALLCHAIN_LBR; |
| 289 | ret = 0; |
| 290 | } else |
| 291 | pr_err("callchain: No more arguments " |
| 292 | "needed for --call-graph lbr\n"); |
| 293 | break; |
| 294 | } else { |
| 295 | pr_err("callchain: Unknown --call-graph option " |
| 296 | "value: %s\n", arg); |
| 297 | break; |
| 298 | } |
| 299 | |
| 300 | } while (0); |
| 301 | |
| 302 | free(buf); |
| 303 | return ret; |
| 304 | } |
| 305 | |
Namhyung Kim | 2b9240c | 2014-09-23 10:01:43 +0900 | [diff] [blame] | 306 | int perf_callchain_config(const char *var, const char *value) |
| 307 | { |
| 308 | char *endptr; |
| 309 | |
Arnaldo Carvalho de Melo | 8e99b6d | 2017-07-20 15:27:39 -0300 | [diff] [blame] | 310 | if (!strstarts(var, "call-graph.")) |
Namhyung Kim | 2b9240c | 2014-09-23 10:01:43 +0900 | [diff] [blame] | 311 | return 0; |
| 312 | var += sizeof("call-graph.") - 1; |
| 313 | |
| 314 | if (!strcmp(var, "record-mode")) |
Kan Liang | c3a6a8c | 2015-08-04 04:30:20 -0400 | [diff] [blame] | 315 | return parse_callchain_record_opt(value, &callchain_param); |
Namhyung Kim | 2b9240c | 2014-09-23 10:01:43 +0900 | [diff] [blame] | 316 | if (!strcmp(var, "dump-size")) { |
| 317 | unsigned long size = 0; |
| 318 | int ret; |
| 319 | |
| 320 | ret = get_stack_size(value, &size); |
| 321 | callchain_param.dump_size = size; |
| 322 | |
| 323 | return ret; |
| 324 | } |
Mengting Zhang | 9789e7e | 2017-09-23 16:18:14 +0800 | [diff] [blame] | 325 | if (!strcmp(var, "print-type")){ |
| 326 | int ret; |
| 327 | ret = parse_callchain_mode(value); |
| 328 | if (ret == -1) |
| 329 | pr_err("Invalid callchain mode: %s\n", value); |
| 330 | return ret; |
| 331 | } |
| 332 | if (!strcmp(var, "order")){ |
| 333 | int ret; |
| 334 | ret = parse_callchain_order(value); |
| 335 | if (ret == -1) |
| 336 | pr_err("Invalid callchain order: %s\n", value); |
| 337 | return ret; |
| 338 | } |
| 339 | if (!strcmp(var, "sort-key")){ |
| 340 | int ret; |
| 341 | ret = parse_callchain_sort_key(value); |
| 342 | if (ret == -1) |
| 343 | pr_err("Invalid callchain sort key: %s\n", value); |
| 344 | return ret; |
| 345 | } |
Namhyung Kim | 2b9240c | 2014-09-23 10:01:43 +0900 | [diff] [blame] | 346 | if (!strcmp(var, "threshold")) { |
| 347 | callchain_param.min_percent = strtod(value, &endptr); |
Arnaldo Carvalho de Melo | ecc4c56 | 2017-01-24 13:44:10 -0300 | [diff] [blame] | 348 | if (value == endptr) { |
| 349 | pr_err("Invalid callchain threshold: %s\n", value); |
Namhyung Kim | 2b9240c | 2014-09-23 10:01:43 +0900 | [diff] [blame] | 350 | return -1; |
Arnaldo Carvalho de Melo | ecc4c56 | 2017-01-24 13:44:10 -0300 | [diff] [blame] | 351 | } |
Namhyung Kim | 2b9240c | 2014-09-23 10:01:43 +0900 | [diff] [blame] | 352 | } |
| 353 | if (!strcmp(var, "print-limit")) { |
| 354 | callchain_param.print_limit = strtod(value, &endptr); |
Arnaldo Carvalho de Melo | ecc4c56 | 2017-01-24 13:44:10 -0300 | [diff] [blame] | 355 | if (value == endptr) { |
| 356 | pr_err("Invalid callchain print limit: %s\n", value); |
Namhyung Kim | 2b9240c | 2014-09-23 10:01:43 +0900 | [diff] [blame] | 357 | return -1; |
Arnaldo Carvalho de Melo | ecc4c56 | 2017-01-24 13:44:10 -0300 | [diff] [blame] | 358 | } |
Namhyung Kim | 2b9240c | 2014-09-23 10:01:43 +0900 | [diff] [blame] | 359 | } |
| 360 | |
| 361 | return 0; |
| 362 | } |
| 363 | |
Frederic Weisbecker | deac911 | 2009-07-01 05:35:15 +0200 | [diff] [blame] | 364 | static void |
Frederic Weisbecker | 4eb3e47 | 2009-07-02 17:58:21 +0200 | [diff] [blame] | 365 | rb_insert_callchain(struct rb_root *root, struct callchain_node *chain, |
| 366 | enum chain_mode mode) |
Frederic Weisbecker | 8cb76d9 | 2009-06-26 16:28:00 +0200 | [diff] [blame] | 367 | { |
| 368 | struct rb_node **p = &root->rb_node; |
| 369 | struct rb_node *parent = NULL; |
| 370 | struct callchain_node *rnode; |
Frederic Weisbecker | f08c315 | 2011-01-14 04:51:59 +0100 | [diff] [blame] | 371 | u64 chain_cumul = callchain_cumul_hits(chain); |
Frederic Weisbecker | 8cb76d9 | 2009-06-26 16:28:00 +0200 | [diff] [blame] | 372 | |
| 373 | while (*p) { |
Frederic Weisbecker | 1953287 | 2009-08-07 07:11:05 +0200 | [diff] [blame] | 374 | u64 rnode_cumul; |
| 375 | |
Frederic Weisbecker | 8cb76d9 | 2009-06-26 16:28:00 +0200 | [diff] [blame] | 376 | parent = *p; |
| 377 | rnode = rb_entry(parent, struct callchain_node, rb_node); |
Frederic Weisbecker | f08c315 | 2011-01-14 04:51:59 +0100 | [diff] [blame] | 378 | rnode_cumul = callchain_cumul_hits(rnode); |
Frederic Weisbecker | 8cb76d9 | 2009-06-26 16:28:00 +0200 | [diff] [blame] | 379 | |
Frederic Weisbecker | 4eb3e47 | 2009-07-02 17:58:21 +0200 | [diff] [blame] | 380 | switch (mode) { |
Frederic Weisbecker | 805d127 | 2009-07-05 07:39:21 +0200 | [diff] [blame] | 381 | case CHAIN_FLAT: |
Namhyung Kim | 26e7792 | 2015-11-09 14:45:37 +0900 | [diff] [blame] | 382 | case CHAIN_FOLDED: |
Frederic Weisbecker | 4eb3e47 | 2009-07-02 17:58:21 +0200 | [diff] [blame] | 383 | if (rnode->hit < chain->hit) |
| 384 | p = &(*p)->rb_left; |
| 385 | else |
| 386 | p = &(*p)->rb_right; |
| 387 | break; |
Frederic Weisbecker | 805d127 | 2009-07-05 07:39:21 +0200 | [diff] [blame] | 388 | case CHAIN_GRAPH_ABS: /* Falldown */ |
| 389 | case CHAIN_GRAPH_REL: |
Frederic Weisbecker | 1953287 | 2009-08-07 07:11:05 +0200 | [diff] [blame] | 390 | if (rnode_cumul < chain_cumul) |
Frederic Weisbecker | 4eb3e47 | 2009-07-02 17:58:21 +0200 | [diff] [blame] | 391 | p = &(*p)->rb_left; |
| 392 | else |
| 393 | p = &(*p)->rb_right; |
| 394 | break; |
Ingo Molnar | 83a0944 | 2009-08-15 12:26:57 +0200 | [diff] [blame] | 395 | case CHAIN_NONE: |
Frederic Weisbecker | 4eb3e47 | 2009-07-02 17:58:21 +0200 | [diff] [blame] | 396 | default: |
| 397 | break; |
| 398 | } |
Frederic Weisbecker | 8cb76d9 | 2009-06-26 16:28:00 +0200 | [diff] [blame] | 399 | } |
| 400 | |
| 401 | rb_link_node(&chain->rb_node, parent, p); |
| 402 | rb_insert_color(&chain->rb_node, root); |
| 403 | } |
| 404 | |
Frederic Weisbecker | 805d127 | 2009-07-05 07:39:21 +0200 | [diff] [blame] | 405 | static void |
| 406 | __sort_chain_flat(struct rb_root *rb_root, struct callchain_node *node, |
| 407 | u64 min_hit) |
Frederic Weisbecker | 8cb76d9 | 2009-06-26 16:28:00 +0200 | [diff] [blame] | 408 | { |
Namhyung Kim | e369517 | 2013-10-11 14:15:36 +0900 | [diff] [blame] | 409 | struct rb_node *n; |
Frederic Weisbecker | 8cb76d9 | 2009-06-26 16:28:00 +0200 | [diff] [blame] | 410 | struct callchain_node *child; |
| 411 | |
Namhyung Kim | e369517 | 2013-10-11 14:15:36 +0900 | [diff] [blame] | 412 | n = rb_first(&node->rb_root_in); |
| 413 | while (n) { |
| 414 | child = rb_entry(n, struct callchain_node, rb_node_in); |
| 415 | n = rb_next(n); |
| 416 | |
Frederic Weisbecker | 805d127 | 2009-07-05 07:39:21 +0200 | [diff] [blame] | 417 | __sort_chain_flat(rb_root, child, min_hit); |
Namhyung Kim | e369517 | 2013-10-11 14:15:36 +0900 | [diff] [blame] | 418 | } |
Frederic Weisbecker | 8cb76d9 | 2009-06-26 16:28:00 +0200 | [diff] [blame] | 419 | |
Frederic Weisbecker | c20ab37 | 2009-07-02 20:14:33 +0200 | [diff] [blame] | 420 | if (node->hit && node->hit >= min_hit) |
Frederic Weisbecker | 805d127 | 2009-07-05 07:39:21 +0200 | [diff] [blame] | 421 | rb_insert_callchain(rb_root, node, CHAIN_FLAT); |
Frederic Weisbecker | 4eb3e47 | 2009-07-02 17:58:21 +0200 | [diff] [blame] | 422 | } |
| 423 | |
Frederic Weisbecker | 805d127 | 2009-07-05 07:39:21 +0200 | [diff] [blame] | 424 | /* |
| 425 | * Once we get every callchains from the stream, we can now |
| 426 | * sort them by hit |
| 427 | */ |
| 428 | static void |
Frederic Weisbecker | d2009c5 | 2010-08-22 20:05:22 +0200 | [diff] [blame] | 429 | sort_chain_flat(struct rb_root *rb_root, struct callchain_root *root, |
Irina Tirdea | 1d037ca | 2012-09-11 01:15:03 +0300 | [diff] [blame] | 430 | u64 min_hit, struct callchain_param *param __maybe_unused) |
Frederic Weisbecker | 805d127 | 2009-07-05 07:39:21 +0200 | [diff] [blame] | 431 | { |
Namhyung Kim | 0356218 | 2015-11-26 16:08:18 +0900 | [diff] [blame] | 432 | *rb_root = RB_ROOT; |
Frederic Weisbecker | d2009c5 | 2010-08-22 20:05:22 +0200 | [diff] [blame] | 433 | __sort_chain_flat(rb_root, &root->node, min_hit); |
Frederic Weisbecker | 805d127 | 2009-07-05 07:39:21 +0200 | [diff] [blame] | 434 | } |
| 435 | |
| 436 | static void __sort_chain_graph_abs(struct callchain_node *node, |
| 437 | u64 min_hit) |
Frederic Weisbecker | 4eb3e47 | 2009-07-02 17:58:21 +0200 | [diff] [blame] | 438 | { |
Namhyung Kim | e369517 | 2013-10-11 14:15:36 +0900 | [diff] [blame] | 439 | struct rb_node *n; |
Frederic Weisbecker | 4eb3e47 | 2009-07-02 17:58:21 +0200 | [diff] [blame] | 440 | struct callchain_node *child; |
| 441 | |
| 442 | node->rb_root = RB_ROOT; |
Namhyung Kim | e369517 | 2013-10-11 14:15:36 +0900 | [diff] [blame] | 443 | n = rb_first(&node->rb_root_in); |
Frederic Weisbecker | 4eb3e47 | 2009-07-02 17:58:21 +0200 | [diff] [blame] | 444 | |
Namhyung Kim | e369517 | 2013-10-11 14:15:36 +0900 | [diff] [blame] | 445 | while (n) { |
| 446 | child = rb_entry(n, struct callchain_node, rb_node_in); |
| 447 | n = rb_next(n); |
| 448 | |
Frederic Weisbecker | 805d127 | 2009-07-05 07:39:21 +0200 | [diff] [blame] | 449 | __sort_chain_graph_abs(child, min_hit); |
Frederic Weisbecker | f08c315 | 2011-01-14 04:51:59 +0100 | [diff] [blame] | 450 | if (callchain_cumul_hits(child) >= min_hit) |
Frederic Weisbecker | 805d127 | 2009-07-05 07:39:21 +0200 | [diff] [blame] | 451 | rb_insert_callchain(&node->rb_root, child, |
| 452 | CHAIN_GRAPH_ABS); |
Frederic Weisbecker | 4eb3e47 | 2009-07-02 17:58:21 +0200 | [diff] [blame] | 453 | } |
| 454 | } |
| 455 | |
Frederic Weisbecker | 805d127 | 2009-07-05 07:39:21 +0200 | [diff] [blame] | 456 | static void |
Frederic Weisbecker | d2009c5 | 2010-08-22 20:05:22 +0200 | [diff] [blame] | 457 | sort_chain_graph_abs(struct rb_root *rb_root, struct callchain_root *chain_root, |
Irina Tirdea | 1d037ca | 2012-09-11 01:15:03 +0300 | [diff] [blame] | 458 | u64 min_hit, struct callchain_param *param __maybe_unused) |
Frederic Weisbecker | 4eb3e47 | 2009-07-02 17:58:21 +0200 | [diff] [blame] | 459 | { |
Frederic Weisbecker | d2009c5 | 2010-08-22 20:05:22 +0200 | [diff] [blame] | 460 | __sort_chain_graph_abs(&chain_root->node, min_hit); |
| 461 | rb_root->rb_node = chain_root->node.rb_root.rb_node; |
Frederic Weisbecker | 8cb76d9 | 2009-06-26 16:28:00 +0200 | [diff] [blame] | 462 | } |
| 463 | |
Frederic Weisbecker | 805d127 | 2009-07-05 07:39:21 +0200 | [diff] [blame] | 464 | static void __sort_chain_graph_rel(struct callchain_node *node, |
| 465 | double min_percent) |
| 466 | { |
Namhyung Kim | e369517 | 2013-10-11 14:15:36 +0900 | [diff] [blame] | 467 | struct rb_node *n; |
Frederic Weisbecker | 805d127 | 2009-07-05 07:39:21 +0200 | [diff] [blame] | 468 | struct callchain_node *child; |
| 469 | u64 min_hit; |
| 470 | |
| 471 | node->rb_root = RB_ROOT; |
Frederic Weisbecker | c0a8865 | 2009-08-09 04:19:15 +0200 | [diff] [blame] | 472 | min_hit = ceil(node->children_hit * min_percent); |
Frederic Weisbecker | 805d127 | 2009-07-05 07:39:21 +0200 | [diff] [blame] | 473 | |
Namhyung Kim | e369517 | 2013-10-11 14:15:36 +0900 | [diff] [blame] | 474 | n = rb_first(&node->rb_root_in); |
| 475 | while (n) { |
| 476 | child = rb_entry(n, struct callchain_node, rb_node_in); |
| 477 | n = rb_next(n); |
| 478 | |
Frederic Weisbecker | 805d127 | 2009-07-05 07:39:21 +0200 | [diff] [blame] | 479 | __sort_chain_graph_rel(child, min_percent); |
Frederic Weisbecker | f08c315 | 2011-01-14 04:51:59 +0100 | [diff] [blame] | 480 | if (callchain_cumul_hits(child) >= min_hit) |
Frederic Weisbecker | 805d127 | 2009-07-05 07:39:21 +0200 | [diff] [blame] | 481 | rb_insert_callchain(&node->rb_root, child, |
| 482 | CHAIN_GRAPH_REL); |
| 483 | } |
| 484 | } |
| 485 | |
| 486 | static void |
Frederic Weisbecker | d2009c5 | 2010-08-22 20:05:22 +0200 | [diff] [blame] | 487 | sort_chain_graph_rel(struct rb_root *rb_root, struct callchain_root *chain_root, |
Irina Tirdea | 1d037ca | 2012-09-11 01:15:03 +0300 | [diff] [blame] | 488 | u64 min_hit __maybe_unused, struct callchain_param *param) |
Frederic Weisbecker | 805d127 | 2009-07-05 07:39:21 +0200 | [diff] [blame] | 489 | { |
Frederic Weisbecker | d2009c5 | 2010-08-22 20:05:22 +0200 | [diff] [blame] | 490 | __sort_chain_graph_rel(&chain_root->node, param->min_percent / 100.0); |
| 491 | rb_root->rb_node = chain_root->node.rb_root.rb_node; |
Frederic Weisbecker | 805d127 | 2009-07-05 07:39:21 +0200 | [diff] [blame] | 492 | } |
| 493 | |
Frederic Weisbecker | 16537f1 | 2011-01-14 04:52:00 +0100 | [diff] [blame] | 494 | int callchain_register_param(struct callchain_param *param) |
Frederic Weisbecker | 805d127 | 2009-07-05 07:39:21 +0200 | [diff] [blame] | 495 | { |
| 496 | switch (param->mode) { |
| 497 | case CHAIN_GRAPH_ABS: |
| 498 | param->sort = sort_chain_graph_abs; |
| 499 | break; |
| 500 | case CHAIN_GRAPH_REL: |
| 501 | param->sort = sort_chain_graph_rel; |
| 502 | break; |
| 503 | case CHAIN_FLAT: |
Namhyung Kim | 26e7792 | 2015-11-09 14:45:37 +0900 | [diff] [blame] | 504 | case CHAIN_FOLDED: |
Frederic Weisbecker | 805d127 | 2009-07-05 07:39:21 +0200 | [diff] [blame] | 505 | param->sort = sort_chain_flat; |
| 506 | break; |
Ingo Molnar | 83a0944 | 2009-08-15 12:26:57 +0200 | [diff] [blame] | 507 | case CHAIN_NONE: |
Frederic Weisbecker | 805d127 | 2009-07-05 07:39:21 +0200 | [diff] [blame] | 508 | default: |
| 509 | return -1; |
| 510 | } |
| 511 | return 0; |
| 512 | } |
| 513 | |
Frederic Weisbecker | deac911 | 2009-07-01 05:35:15 +0200 | [diff] [blame] | 514 | /* |
| 515 | * Create a child for a parent. If inherit_children, then the new child |
| 516 | * will become the new parent of it's parent children |
| 517 | */ |
| 518 | static struct callchain_node * |
| 519 | create_child(struct callchain_node *parent, bool inherit_children) |
Frederic Weisbecker | 8cb76d9 | 2009-06-26 16:28:00 +0200 | [diff] [blame] | 520 | { |
| 521 | struct callchain_node *new; |
| 522 | |
Arnaldo Carvalho de Melo | cdd5b75b | 2010-05-10 10:56:50 -0300 | [diff] [blame] | 523 | new = zalloc(sizeof(*new)); |
Frederic Weisbecker | 8cb76d9 | 2009-06-26 16:28:00 +0200 | [diff] [blame] | 524 | if (!new) { |
| 525 | perror("not enough memory to create child for code path tree"); |
| 526 | return NULL; |
| 527 | } |
| 528 | new->parent = parent; |
Frederic Weisbecker | 8cb76d9 | 2009-06-26 16:28:00 +0200 | [diff] [blame] | 529 | INIT_LIST_HEAD(&new->val); |
Namhyung Kim | 4b3a321 | 2015-11-09 14:45:43 +0900 | [diff] [blame] | 530 | INIT_LIST_HEAD(&new->parent_val); |
Frederic Weisbecker | deac911 | 2009-07-01 05:35:15 +0200 | [diff] [blame] | 531 | |
| 532 | if (inherit_children) { |
Namhyung Kim | e369517 | 2013-10-11 14:15:36 +0900 | [diff] [blame] | 533 | struct rb_node *n; |
| 534 | struct callchain_node *child; |
Frederic Weisbecker | deac911 | 2009-07-01 05:35:15 +0200 | [diff] [blame] | 535 | |
Namhyung Kim | e369517 | 2013-10-11 14:15:36 +0900 | [diff] [blame] | 536 | new->rb_root_in = parent->rb_root_in; |
| 537 | parent->rb_root_in = RB_ROOT; |
Frederic Weisbecker | deac911 | 2009-07-01 05:35:15 +0200 | [diff] [blame] | 538 | |
Namhyung Kim | e369517 | 2013-10-11 14:15:36 +0900 | [diff] [blame] | 539 | n = rb_first(&new->rb_root_in); |
| 540 | while (n) { |
| 541 | child = rb_entry(n, struct callchain_node, rb_node_in); |
| 542 | child->parent = new; |
| 543 | n = rb_next(n); |
| 544 | } |
| 545 | |
| 546 | /* make it the first child */ |
| 547 | rb_link_node(&new->rb_node_in, NULL, &parent->rb_root_in.rb_node); |
| 548 | rb_insert_color(&new->rb_node_in, &parent->rb_root_in); |
Frederic Weisbecker | deac911 | 2009-07-01 05:35:15 +0200 | [diff] [blame] | 549 | } |
Frederic Weisbecker | 8cb76d9 | 2009-06-26 16:28:00 +0200 | [diff] [blame] | 550 | |
| 551 | return new; |
| 552 | } |
| 553 | |
Frederic Weisbecker | 301fde2 | 2010-03-22 13:09:33 -0300 | [diff] [blame] | 554 | |
Frederic Weisbecker | deac911 | 2009-07-01 05:35:15 +0200 | [diff] [blame] | 555 | /* |
| 556 | * Fill the node with callchain values |
| 557 | */ |
Namhyung Kim | 8451cbb | 2016-02-16 23:08:21 +0900 | [diff] [blame] | 558 | static int |
Frederic Weisbecker | 1b3a0e9 | 2011-01-14 04:51:58 +0100 | [diff] [blame] | 559 | fill_node(struct callchain_node *node, struct callchain_cursor *cursor) |
Frederic Weisbecker | 8cb76d9 | 2009-06-26 16:28:00 +0200 | [diff] [blame] | 560 | { |
Frederic Weisbecker | 1b3a0e9 | 2011-01-14 04:51:58 +0100 | [diff] [blame] | 561 | struct callchain_cursor_node *cursor_node; |
Frederic Weisbecker | 8cb76d9 | 2009-06-26 16:28:00 +0200 | [diff] [blame] | 562 | |
Frederic Weisbecker | 1b3a0e9 | 2011-01-14 04:51:58 +0100 | [diff] [blame] | 563 | node->val_nr = cursor->nr - cursor->pos; |
| 564 | if (!node->val_nr) |
| 565 | pr_warning("Warning: empty node in callchain tree\n"); |
| 566 | |
| 567 | cursor_node = callchain_cursor_current(cursor); |
| 568 | |
| 569 | while (cursor_node) { |
Frederic Weisbecker | 8cb76d9 | 2009-06-26 16:28:00 +0200 | [diff] [blame] | 570 | struct callchain_list *call; |
| 571 | |
Arnaldo Carvalho de Melo | cdd5b75b | 2010-05-10 10:56:50 -0300 | [diff] [blame] | 572 | call = zalloc(sizeof(*call)); |
Frederic Weisbecker | 8cb76d9 | 2009-06-26 16:28:00 +0200 | [diff] [blame] | 573 | if (!call) { |
| 574 | perror("not enough memory for the code path tree"); |
Namhyung Kim | 8451cbb | 2016-02-16 23:08:21 +0900 | [diff] [blame] | 575 | return -1; |
Frederic Weisbecker | 8cb76d9 | 2009-06-26 16:28:00 +0200 | [diff] [blame] | 576 | } |
Frederic Weisbecker | 1b3a0e9 | 2011-01-14 04:51:58 +0100 | [diff] [blame] | 577 | call->ip = cursor_node->ip; |
| 578 | call->ms.sym = cursor_node->sym; |
Krister Johansen | 9c68ae9 | 2017-01-05 22:23:31 -0800 | [diff] [blame] | 579 | call->ms.map = map__get(cursor_node->map); |
Jin Yao | 3dd029e | 2016-10-31 09:19:51 +0800 | [diff] [blame] | 580 | |
| 581 | if (cursor_node->branch) { |
| 582 | call->branch_count = 1; |
| 583 | |
Jin Yao | a1a8bed | 2017-07-24 19:09:07 +0800 | [diff] [blame] | 584 | 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 Yao | 3dd029e | 2016-10-31 09:19:51 +0800 | [diff] [blame] | 590 | |
Jin Yao | a1a8bed | 2017-07-24 19:09:07 +0800 | [diff] [blame] | 591 | if (cursor_node->branch_flags.predicted) |
| 592 | call->predicted_count = 1; |
Jin Yao | 3dd029e | 2016-10-31 09:19:51 +0800 | [diff] [blame] | 593 | |
Jin Yao | a1a8bed | 2017-07-24 19:09:07 +0800 | [diff] [blame] | 594 | if (cursor_node->branch_flags.abort) |
| 595 | call->abort_count = 1; |
Jin Yao | b851dd4 | 2017-07-18 20:13:15 +0800 | [diff] [blame] | 596 | |
Jin Yao | a1a8bed | 2017-07-24 19:09:07 +0800 | [diff] [blame] | 597 | 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 Yao | c4ee062 | 2017-08-07 21:05:15 +0800 | [diff] [blame] | 609 | call->iter_cycles = cursor_node->iter_cycles; |
Jin Yao | a1a8bed | 2017-07-24 19:09:07 +0800 | [diff] [blame] | 610 | } |
Jin Yao | 3dd029e | 2016-10-31 09:19:51 +0800 | [diff] [blame] | 611 | } |
| 612 | |
Frederic Weisbecker | 8cb76d9 | 2009-06-26 16:28:00 +0200 | [diff] [blame] | 613 | list_add_tail(&call->list, &node->val); |
Frederic Weisbecker | 1b3a0e9 | 2011-01-14 04:51:58 +0100 | [diff] [blame] | 614 | |
| 615 | callchain_cursor_advance(cursor); |
| 616 | cursor_node = callchain_cursor_current(cursor); |
Frederic Weisbecker | 8cb76d9 | 2009-06-26 16:28:00 +0200 | [diff] [blame] | 617 | } |
Namhyung Kim | 8451cbb | 2016-02-16 23:08:21 +0900 | [diff] [blame] | 618 | return 0; |
Frederic Weisbecker | 8cb76d9 | 2009-06-26 16:28:00 +0200 | [diff] [blame] | 619 | } |
| 620 | |
Namhyung Kim | e369517 | 2013-10-11 14:15:36 +0900 | [diff] [blame] | 621 | static struct callchain_node * |
Frederic Weisbecker | 1b3a0e9 | 2011-01-14 04:51:58 +0100 | [diff] [blame] | 622 | add_child(struct callchain_node *parent, |
| 623 | struct callchain_cursor *cursor, |
| 624 | u64 period) |
Frederic Weisbecker | 8cb76d9 | 2009-06-26 16:28:00 +0200 | [diff] [blame] | 625 | { |
| 626 | struct callchain_node *new; |
| 627 | |
Frederic Weisbecker | deac911 | 2009-07-01 05:35:15 +0200 | [diff] [blame] | 628 | new = create_child(parent, false); |
Namhyung Kim | 7565bd3 | 2016-02-16 23:08:20 +0900 | [diff] [blame] | 629 | if (new == NULL) |
| 630 | return NULL; |
| 631 | |
Namhyung Kim | 8451cbb | 2016-02-16 23:08:21 +0900 | [diff] [blame] | 632 | 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 Johansen | 9c68ae9 | 2017-01-05 22:23:31 -0800 | [diff] [blame] | 637 | map__zput(call->ms.map); |
Namhyung Kim | 8451cbb | 2016-02-16 23:08:21 +0900 | [diff] [blame] | 638 | free(call); |
| 639 | } |
| 640 | free(new); |
| 641 | return NULL; |
| 642 | } |
Frederic Weisbecker | 8cb76d9 | 2009-06-26 16:28:00 +0200 | [diff] [blame] | 643 | |
Frederic Weisbecker | 1953287 | 2009-08-07 07:11:05 +0200 | [diff] [blame] | 644 | new->children_hit = 0; |
Frederic Weisbecker | 108553e | 2010-07-08 03:41:46 +0200 | [diff] [blame] | 645 | new->hit = period; |
Namhyung Kim | 5e47f8f | 2015-11-09 14:45:40 +0900 | [diff] [blame] | 646 | new->children_count = 0; |
| 647 | new->count = 1; |
Namhyung Kim | e369517 | 2013-10-11 14:15:36 +0900 | [diff] [blame] | 648 | return new; |
| 649 | } |
| 650 | |
Namhyung Kim | 2d713b8 | 2016-02-16 23:08:22 +0900 | [diff] [blame] | 651 | enum match_result { |
| 652 | MATCH_ERROR = -1, |
| 653 | MATCH_EQ, |
| 654 | MATCH_LT, |
| 655 | MATCH_GT, |
| 656 | }; |
| 657 | |
Milian Wolff | 5dfa210 | 2017-03-18 22:49:28 +0100 | [diff] [blame] | 658 | static enum match_result match_chain_srcline(struct callchain_cursor_node *node, |
| 659 | struct callchain_list *cnode) |
| 660 | { |
Milian Wolff | 7d4df08 | 2017-05-24 15:21:23 +0900 | [diff] [blame] | 661 | char *left = NULL; |
| 662 | char *right = NULL; |
Milian Wolff | 5dfa210 | 2017-03-18 22:49:28 +0100 | [diff] [blame] | 663 | enum match_result ret = MATCH_EQ; |
| 664 | int cmp; |
| 665 | |
Milian Wolff | 7d4df08 | 2017-05-24 15:21:23 +0900 | [diff] [blame] | 666 | 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 Wolff | 5dfa210 | 2017-03-18 22:49:28 +0100 | [diff] [blame] | 675 | 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 Kim | 2d713b8 | 2016-02-16 23:08:22 +0900 | [diff] [blame] | 694 | static enum match_result match_chain(struct callchain_cursor_node *node, |
| 695 | struct callchain_list *cnode) |
Namhyung Kim | e369517 | 2013-10-11 14:15:36 +0900 | [diff] [blame] | 696 | { |
| 697 | struct symbol *sym = node->sym; |
Namhyung Kim | 2d713b8 | 2016-02-16 23:08:22 +0900 | [diff] [blame] | 698 | u64 left, right; |
Ravi Bangoria | c1fbc0c | 2017-10-05 14:42:34 +0530 | [diff] [blame] | 699 | struct dso *left_dso = NULL; |
| 700 | struct dso *right_dso = NULL; |
Namhyung Kim | e369517 | 2013-10-11 14:15:36 +0900 | [diff] [blame] | 701 | |
Milian Wolff | 5dfa210 | 2017-03-18 22:49:28 +0100 | [diff] [blame] | 702 | 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 Kim | 2d713b8 | 2016-02-16 23:08:22 +0900 | [diff] [blame] | 710 | left = cnode->ms.sym->start; |
| 711 | right = sym->start; |
Ravi Bangoria | c1fbc0c | 2017-10-05 14:42:34 +0530 | [diff] [blame] | 712 | left_dso = cnode->ms.map->dso; |
| 713 | right_dso = node->map->dso; |
Namhyung Kim | 2d713b8 | 2016-02-16 23:08:22 +0900 | [diff] [blame] | 714 | } else { |
| 715 | left = cnode->ip; |
| 716 | right = node->ip; |
| 717 | } |
| 718 | |
Ravi Bangoria | c1fbc0c | 2017-10-05 14:42:34 +0530 | [diff] [blame] | 719 | if (left == right && left_dso == right_dso) { |
Jin Yao | 3dd029e | 2016-10-31 09:19:51 +0800 | [diff] [blame] | 720 | if (node->branch) { |
| 721 | cnode->branch_count++; |
| 722 | |
Jin Yao | a1a8bed | 2017-07-24 19:09:07 +0800 | [diff] [blame] | 723 | if (node->branch_from) { |
| 724 | /* |
| 725 | * It's "to" of a branch |
| 726 | */ |
| 727 | cnode->brtype_stat.branch_to = true; |
Jin Yao | 3dd029e | 2016-10-31 09:19:51 +0800 | [diff] [blame] | 728 | |
Jin Yao | a1a8bed | 2017-07-24 19:09:07 +0800 | [diff] [blame] | 729 | if (node->branch_flags.predicted) |
| 730 | cnode->predicted_count++; |
Jin Yao | 3dd029e | 2016-10-31 09:19:51 +0800 | [diff] [blame] | 731 | |
Jin Yao | a1a8bed | 2017-07-24 19:09:07 +0800 | [diff] [blame] | 732 | if (node->branch_flags.abort) |
| 733 | cnode->abort_count++; |
Jin Yao | b851dd4 | 2017-07-18 20:13:15 +0800 | [diff] [blame] | 734 | |
Jin Yao | a1a8bed | 2017-07-24 19:09:07 +0800 | [diff] [blame] | 735 | 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 Yao | c4ee062 | 2017-08-07 21:05:15 +0800 | [diff] [blame] | 747 | cnode->iter_cycles += node->iter_cycles; |
Jin Yao | a1a8bed | 2017-07-24 19:09:07 +0800 | [diff] [blame] | 748 | } |
Jin Yao | 3dd029e | 2016-10-31 09:19:51 +0800 | [diff] [blame] | 749 | } |
| 750 | |
Namhyung Kim | 2d713b8 | 2016-02-16 23:08:22 +0900 | [diff] [blame] | 751 | return MATCH_EQ; |
Jin Yao | 3dd029e | 2016-10-31 09:19:51 +0800 | [diff] [blame] | 752 | } |
Namhyung Kim | 2d713b8 | 2016-02-16 23:08:22 +0900 | [diff] [blame] | 753 | |
| 754 | return left > right ? MATCH_GT : MATCH_LT; |
Frederic Weisbecker | 8cb76d9 | 2009-06-26 16:28:00 +0200 | [diff] [blame] | 755 | } |
| 756 | |
Frederic Weisbecker | deac911 | 2009-07-01 05:35:15 +0200 | [diff] [blame] | 757 | /* |
| 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 Kim | f2bb4c5 | 2016-02-16 23:08:23 +0900 | [diff] [blame] | 762 | static int |
Frederic Weisbecker | 1b3a0e9 | 2011-01-14 04:51:58 +0100 | [diff] [blame] | 763 | split_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 Weisbecker | 8cb76d9 | 2009-06-26 16:28:00 +0200 | [diff] [blame] | 767 | { |
| 768 | struct callchain_node *new; |
Frederic Weisbecker | deac911 | 2009-07-01 05:35:15 +0200 | [diff] [blame] | 769 | struct list_head *old_tail; |
Ingo Molnar | f37a291 | 2009-07-01 12:37:06 +0200 | [diff] [blame] | 770 | unsigned int idx_total = idx_parents + idx_local; |
Frederic Weisbecker | 8cb76d9 | 2009-06-26 16:28:00 +0200 | [diff] [blame] | 771 | |
| 772 | /* split */ |
Frederic Weisbecker | deac911 | 2009-07-01 05:35:15 +0200 | [diff] [blame] | 773 | new = create_child(parent, true); |
Namhyung Kim | f2bb4c5 | 2016-02-16 23:08:23 +0900 | [diff] [blame] | 774 | if (new == NULL) |
| 775 | return -1; |
Frederic Weisbecker | 8cb76d9 | 2009-06-26 16:28:00 +0200 | [diff] [blame] | 776 | |
Frederic Weisbecker | deac911 | 2009-07-01 05:35:15 +0200 | [diff] [blame] | 777 | /* 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 Weisbecker | 1953287 | 2009-08-07 07:11:05 +0200 | [diff] [blame] | 787 | new->children_hit = parent->children_hit; |
Frederic Weisbecker | f08c315 | 2011-01-14 04:51:59 +0100 | [diff] [blame] | 788 | parent->children_hit = callchain_cumul_hits(new); |
Frederic Weisbecker | deac911 | 2009-07-01 05:35:15 +0200 | [diff] [blame] | 789 | new->val_nr = parent->val_nr - idx_local; |
| 790 | parent->val_nr = idx_local; |
Namhyung Kim | 5e47f8f | 2015-11-09 14:45:40 +0900 | [diff] [blame] | 791 | new->count = parent->count; |
| 792 | new->children_count = parent->children_count; |
| 793 | parent->children_count = callchain_cumul_counts(new); |
Frederic Weisbecker | deac911 | 2009-07-01 05:35:15 +0200 | [diff] [blame] | 794 | |
| 795 | /* create a new child for the new branch if any */ |
Frederic Weisbecker | 1b3a0e9 | 2011-01-14 04:51:58 +0100 | [diff] [blame] | 796 | if (idx_total < cursor->nr) { |
Namhyung Kim | e369517 | 2013-10-11 14:15:36 +0900 | [diff] [blame] | 797 | struct callchain_node *first; |
| 798 | struct callchain_list *cnode; |
| 799 | struct callchain_cursor_node *node; |
| 800 | struct rb_node *p, **pp; |
| 801 | |
Frederic Weisbecker | deac911 | 2009-07-01 05:35:15 +0200 | [diff] [blame] | 802 | parent->hit = 0; |
Frederic Weisbecker | 108553e | 2010-07-08 03:41:46 +0200 | [diff] [blame] | 803 | parent->children_hit += period; |
Namhyung Kim | 5e47f8f | 2015-11-09 14:45:40 +0900 | [diff] [blame] | 804 | parent->count = 0; |
| 805 | parent->children_count += 1; |
Namhyung Kim | e369517 | 2013-10-11 14:15:36 +0900 | [diff] [blame] | 806 | |
| 807 | node = callchain_cursor_current(cursor); |
| 808 | new = add_child(parent, cursor, period); |
Namhyung Kim | 7565bd3 | 2016-02-16 23:08:20 +0900 | [diff] [blame] | 809 | if (new == NULL) |
Namhyung Kim | f2bb4c5 | 2016-02-16 23:08:23 +0900 | [diff] [blame] | 810 | return -1; |
Namhyung Kim | e369517 | 2013-10-11 14:15:36 +0900 | [diff] [blame] | 811 | |
| 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 Kim | 2d713b8 | 2016-02-16 23:08:22 +0900 | [diff] [blame] | 821 | if (match_chain(node, cnode) == MATCH_LT) |
Namhyung Kim | e369517 | 2013-10-11 14:15:36 +0900 | [diff] [blame] | 822 | 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 Weisbecker | deac911 | 2009-07-01 05:35:15 +0200 | [diff] [blame] | 828 | } else { |
Frederic Weisbecker | 108553e | 2010-07-08 03:41:46 +0200 | [diff] [blame] | 829 | parent->hit = period; |
Namhyung Kim | 5e47f8f | 2015-11-09 14:45:40 +0900 | [diff] [blame] | 830 | parent->count = 1; |
Frederic Weisbecker | deac911 | 2009-07-01 05:35:15 +0200 | [diff] [blame] | 831 | } |
Namhyung Kim | f2bb4c5 | 2016-02-16 23:08:23 +0900 | [diff] [blame] | 832 | return 0; |
Frederic Weisbecker | 8cb76d9 | 2009-06-26 16:28:00 +0200 | [diff] [blame] | 833 | } |
| 834 | |
Namhyung Kim | 2d713b8 | 2016-02-16 23:08:22 +0900 | [diff] [blame] | 835 | static enum match_result |
Frederic Weisbecker | 1b3a0e9 | 2011-01-14 04:51:58 +0100 | [diff] [blame] | 836 | append_chain(struct callchain_node *root, |
| 837 | struct callchain_cursor *cursor, |
| 838 | u64 period); |
Frederic Weisbecker | 8cb76d9 | 2009-06-26 16:28:00 +0200 | [diff] [blame] | 839 | |
Namhyung Kim | dca0d12 | 2016-02-16 23:08:24 +0900 | [diff] [blame] | 840 | static int |
Frederic Weisbecker | 1b3a0e9 | 2011-01-14 04:51:58 +0100 | [diff] [blame] | 841 | append_chain_children(struct callchain_node *root, |
| 842 | struct callchain_cursor *cursor, |
| 843 | u64 period) |
Frederic Weisbecker | 8cb76d9 | 2009-06-26 16:28:00 +0200 | [diff] [blame] | 844 | { |
| 845 | struct callchain_node *rnode; |
Namhyung Kim | e369517 | 2013-10-11 14:15:36 +0900 | [diff] [blame] | 846 | 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 Kim | dca0d12 | 2016-02-16 23:08:24 +0900 | [diff] [blame] | 852 | return -1; |
Frederic Weisbecker | 8cb76d9 | 2009-06-26 16:28:00 +0200 | [diff] [blame] | 853 | |
| 854 | /* lookup in childrens */ |
Namhyung Kim | e369517 | 2013-10-11 14:15:36 +0900 | [diff] [blame] | 855 | while (*p) { |
Namhyung Kim | 2d713b8 | 2016-02-16 23:08:22 +0900 | [diff] [blame] | 856 | enum match_result ret; |
Ingo Molnar | f37a291 | 2009-07-01 12:37:06 +0200 | [diff] [blame] | 857 | |
Namhyung Kim | e369517 | 2013-10-11 14:15:36 +0900 | [diff] [blame] | 858 | parent = *p; |
| 859 | rnode = rb_entry(parent, struct callchain_node, rb_node_in); |
Namhyung Kim | e369517 | 2013-10-11 14:15:36 +0900 | [diff] [blame] | 860 | |
Frederic Weisbecker | b965bb4 | 2014-01-14 16:37:15 +0100 | [diff] [blame] | 861 | /* If at least first entry matches, rely to children */ |
| 862 | ret = append_chain(rnode, cursor, period); |
Namhyung Kim | 2d713b8 | 2016-02-16 23:08:22 +0900 | [diff] [blame] | 863 | if (ret == MATCH_EQ) |
Frederic Weisbecker | 1953287 | 2009-08-07 07:11:05 +0200 | [diff] [blame] | 864 | goto inc_children_hit; |
Namhyung Kim | dca0d12 | 2016-02-16 23:08:24 +0900 | [diff] [blame] | 865 | if (ret == MATCH_ERROR) |
| 866 | return -1; |
Namhyung Kim | e369517 | 2013-10-11 14:15:36 +0900 | [diff] [blame] | 867 | |
Namhyung Kim | 2d713b8 | 2016-02-16 23:08:22 +0900 | [diff] [blame] | 868 | if (ret == MATCH_LT) |
Namhyung Kim | e369517 | 2013-10-11 14:15:36 +0900 | [diff] [blame] | 869 | p = &parent->rb_left; |
| 870 | else |
| 871 | p = &parent->rb_right; |
Frederic Weisbecker | 8cb76d9 | 2009-06-26 16:28:00 +0200 | [diff] [blame] | 872 | } |
Frederic Weisbecker | deac911 | 2009-07-01 05:35:15 +0200 | [diff] [blame] | 873 | /* nothing in children, add to the current node */ |
Namhyung Kim | e369517 | 2013-10-11 14:15:36 +0900 | [diff] [blame] | 874 | rnode = add_child(root, cursor, period); |
Namhyung Kim | 7565bd3 | 2016-02-16 23:08:20 +0900 | [diff] [blame] | 875 | if (rnode == NULL) |
Namhyung Kim | dca0d12 | 2016-02-16 23:08:24 +0900 | [diff] [blame] | 876 | return -1; |
Namhyung Kim | 7565bd3 | 2016-02-16 23:08:20 +0900 | [diff] [blame] | 877 | |
Namhyung Kim | e369517 | 2013-10-11 14:15:36 +0900 | [diff] [blame] | 878 | rb_link_node(&rnode->rb_node_in, parent, p); |
| 879 | rb_insert_color(&rnode->rb_node_in, &root->rb_root_in); |
Frederic Weisbecker | e05b876 | 2009-07-05 07:39:20 +0200 | [diff] [blame] | 880 | |
Frederic Weisbecker | 1953287 | 2009-08-07 07:11:05 +0200 | [diff] [blame] | 881 | inc_children_hit: |
Frederic Weisbecker | 108553e | 2010-07-08 03:41:46 +0200 | [diff] [blame] | 882 | root->children_hit += period; |
Namhyung Kim | 5e47f8f | 2015-11-09 14:45:40 +0900 | [diff] [blame] | 883 | root->children_count++; |
Namhyung Kim | dca0d12 | 2016-02-16 23:08:24 +0900 | [diff] [blame] | 884 | return 0; |
Frederic Weisbecker | 8cb76d9 | 2009-06-26 16:28:00 +0200 | [diff] [blame] | 885 | } |
| 886 | |
Namhyung Kim | 2d713b8 | 2016-02-16 23:08:22 +0900 | [diff] [blame] | 887 | static enum match_result |
Frederic Weisbecker | 1b3a0e9 | 2011-01-14 04:51:58 +0100 | [diff] [blame] | 888 | append_chain(struct callchain_node *root, |
| 889 | struct callchain_cursor *cursor, |
| 890 | u64 period) |
Frederic Weisbecker | 8cb76d9 | 2009-06-26 16:28:00 +0200 | [diff] [blame] | 891 | { |
| 892 | struct callchain_list *cnode; |
Frederic Weisbecker | 1b3a0e9 | 2011-01-14 04:51:58 +0100 | [diff] [blame] | 893 | u64 start = cursor->pos; |
Frederic Weisbecker | 8cb76d9 | 2009-06-26 16:28:00 +0200 | [diff] [blame] | 894 | bool found = false; |
Frederic Weisbecker | 1b3a0e9 | 2011-01-14 04:51:58 +0100 | [diff] [blame] | 895 | u64 matches; |
Namhyung Kim | 2d713b8 | 2016-02-16 23:08:22 +0900 | [diff] [blame] | 896 | enum match_result cmp = MATCH_ERROR; |
Frederic Weisbecker | 8cb76d9 | 2009-06-26 16:28:00 +0200 | [diff] [blame] | 897 | |
Frederic Weisbecker | deac911 | 2009-07-01 05:35:15 +0200 | [diff] [blame] | 898 | /* |
| 899 | * Lookup in the current node |
| 900 | * If we have a symbol, then compare the start to match |
Andi Kleen | 99571ab | 2013-07-18 15:33:57 -0700 | [diff] [blame] | 901 | * anywhere inside a function, unless function |
| 902 | * mode is disabled. |
Frederic Weisbecker | deac911 | 2009-07-01 05:35:15 +0200 | [diff] [blame] | 903 | */ |
Frederic Weisbecker | 8cb76d9 | 2009-06-26 16:28:00 +0200 | [diff] [blame] | 904 | list_for_each_entry(cnode, &root->val, list) { |
Frederic Weisbecker | 1b3a0e9 | 2011-01-14 04:51:58 +0100 | [diff] [blame] | 905 | struct callchain_cursor_node *node; |
Frederic Weisbecker | 301fde2 | 2010-03-22 13:09:33 -0300 | [diff] [blame] | 906 | |
Frederic Weisbecker | 1b3a0e9 | 2011-01-14 04:51:58 +0100 | [diff] [blame] | 907 | node = callchain_cursor_current(cursor); |
| 908 | if (!node) |
Frederic Weisbecker | deac911 | 2009-07-01 05:35:15 +0200 | [diff] [blame] | 909 | break; |
Frederic Weisbecker | 301fde2 | 2010-03-22 13:09:33 -0300 | [diff] [blame] | 910 | |
Frederic Weisbecker | b965bb4 | 2014-01-14 16:37:15 +0100 | [diff] [blame] | 911 | cmp = match_chain(node, cnode); |
Namhyung Kim | 2d713b8 | 2016-02-16 23:08:22 +0900 | [diff] [blame] | 912 | if (cmp != MATCH_EQ) |
Frederic Weisbecker | 8cb76d9 | 2009-06-26 16:28:00 +0200 | [diff] [blame] | 913 | break; |
Frederic Weisbecker | 301fde2 | 2010-03-22 13:09:33 -0300 | [diff] [blame] | 914 | |
Namhyung Kim | e369517 | 2013-10-11 14:15:36 +0900 | [diff] [blame] | 915 | found = true; |
Frederic Weisbecker | 1b3a0e9 | 2011-01-14 04:51:58 +0100 | [diff] [blame] | 916 | |
| 917 | callchain_cursor_advance(cursor); |
Frederic Weisbecker | 8cb76d9 | 2009-06-26 16:28:00 +0200 | [diff] [blame] | 918 | } |
| 919 | |
Namhyung Kim | e369517 | 2013-10-11 14:15:36 +0900 | [diff] [blame] | 920 | /* matches not, relay no the parent */ |
Frederic Weisbecker | 1b3a0e9 | 2011-01-14 04:51:58 +0100 | [diff] [blame] | 921 | if (!found) { |
Namhyung Kim | 2d713b8 | 2016-02-16 23:08:22 +0900 | [diff] [blame] | 922 | WARN_ONCE(cmp == MATCH_ERROR, "Chain comparison error\n"); |
Frederic Weisbecker | b965bb4 | 2014-01-14 16:37:15 +0100 | [diff] [blame] | 923 | return cmp; |
Frederic Weisbecker | 1b3a0e9 | 2011-01-14 04:51:58 +0100 | [diff] [blame] | 924 | } |
| 925 | |
| 926 | matches = cursor->pos - start; |
Frederic Weisbecker | 8cb76d9 | 2009-06-26 16:28:00 +0200 | [diff] [blame] | 927 | |
| 928 | /* we match only a part of the node. Split it and add the new chain */ |
Frederic Weisbecker | 1b3a0e9 | 2011-01-14 04:51:58 +0100 | [diff] [blame] | 929 | if (matches < root->val_nr) { |
Namhyung Kim | f2bb4c5 | 2016-02-16 23:08:23 +0900 | [diff] [blame] | 930 | if (split_add_child(root, cursor, cnode, start, matches, |
| 931 | period) < 0) |
| 932 | return MATCH_ERROR; |
| 933 | |
Namhyung Kim | 2d713b8 | 2016-02-16 23:08:22 +0900 | [diff] [blame] | 934 | return MATCH_EQ; |
Frederic Weisbecker | 8cb76d9 | 2009-06-26 16:28:00 +0200 | [diff] [blame] | 935 | } |
| 936 | |
| 937 | /* we match 100% of the path, increment the hit */ |
Frederic Weisbecker | 1b3a0e9 | 2011-01-14 04:51:58 +0100 | [diff] [blame] | 938 | if (matches == root->val_nr && cursor->pos == cursor->nr) { |
Frederic Weisbecker | 108553e | 2010-07-08 03:41:46 +0200 | [diff] [blame] | 939 | root->hit += period; |
Namhyung Kim | 5e47f8f | 2015-11-09 14:45:40 +0900 | [diff] [blame] | 940 | root->count++; |
Namhyung Kim | 2d713b8 | 2016-02-16 23:08:22 +0900 | [diff] [blame] | 941 | return MATCH_EQ; |
Frederic Weisbecker | 8cb76d9 | 2009-06-26 16:28:00 +0200 | [diff] [blame] | 942 | } |
| 943 | |
Frederic Weisbecker | deac911 | 2009-07-01 05:35:15 +0200 | [diff] [blame] | 944 | /* We match the node and still have a part remaining */ |
Namhyung Kim | dca0d12 | 2016-02-16 23:08:24 +0900 | [diff] [blame] | 945 | if (append_chain_children(root, cursor, period) < 0) |
| 946 | return MATCH_ERROR; |
Frederic Weisbecker | deac911 | 2009-07-01 05:35:15 +0200 | [diff] [blame] | 947 | |
Namhyung Kim | 2d713b8 | 2016-02-16 23:08:22 +0900 | [diff] [blame] | 948 | return MATCH_EQ; |
Frederic Weisbecker | 8cb76d9 | 2009-06-26 16:28:00 +0200 | [diff] [blame] | 949 | } |
| 950 | |
Frederic Weisbecker | 1b3a0e9 | 2011-01-14 04:51:58 +0100 | [diff] [blame] | 951 | int callchain_append(struct callchain_root *root, |
| 952 | struct callchain_cursor *cursor, |
| 953 | u64 period) |
Frederic Weisbecker | 301fde2 | 2010-03-22 13:09:33 -0300 | [diff] [blame] | 954 | { |
Frederic Weisbecker | 1b3a0e9 | 2011-01-14 04:51:58 +0100 | [diff] [blame] | 955 | if (!cursor->nr) |
Frederic Weisbecker | 301fde2 | 2010-03-22 13:09:33 -0300 | [diff] [blame] | 956 | return 0; |
| 957 | |
Frederic Weisbecker | 1b3a0e9 | 2011-01-14 04:51:58 +0100 | [diff] [blame] | 958 | callchain_cursor_commit(cursor); |
Frederic Weisbecker | 301fde2 | 2010-03-22 13:09:33 -0300 | [diff] [blame] | 959 | |
Namhyung Kim | dca0d12 | 2016-02-16 23:08:24 +0900 | [diff] [blame] | 960 | if (append_chain_children(&root->node, cursor, period) < 0) |
| 961 | return -1; |
Frederic Weisbecker | 301fde2 | 2010-03-22 13:09:33 -0300 | [diff] [blame] | 962 | |
Frederic Weisbecker | 1b3a0e9 | 2011-01-14 04:51:58 +0100 | [diff] [blame] | 963 | if (cursor->nr > root->max_depth) |
| 964 | root->max_depth = cursor->nr; |
Frederic Weisbecker | 301fde2 | 2010-03-22 13:09:33 -0300 | [diff] [blame] | 965 | |
| 966 | return 0; |
Frederic Weisbecker | 8cb76d9 | 2009-06-26 16:28:00 +0200 | [diff] [blame] | 967 | } |
Frederic Weisbecker | 612d4fd | 2010-08-22 21:10:35 +0200 | [diff] [blame] | 968 | |
| 969 | static int |
Frederic Weisbecker | 1b3a0e9 | 2011-01-14 04:51:58 +0100 | [diff] [blame] | 970 | merge_chain_branch(struct callchain_cursor *cursor, |
| 971 | struct callchain_node *dst, struct callchain_node *src) |
Frederic Weisbecker | 612d4fd | 2010-08-22 21:10:35 +0200 | [diff] [blame] | 972 | { |
Frederic Weisbecker | 1b3a0e9 | 2011-01-14 04:51:58 +0100 | [diff] [blame] | 973 | struct callchain_cursor_node **old_last = cursor->last; |
Namhyung Kim | e369517 | 2013-10-11 14:15:36 +0900 | [diff] [blame] | 974 | struct callchain_node *child; |
Frederic Weisbecker | 612d4fd | 2010-08-22 21:10:35 +0200 | [diff] [blame] | 975 | struct callchain_list *list, *next_list; |
Namhyung Kim | e369517 | 2013-10-11 14:15:36 +0900 | [diff] [blame] | 976 | struct rb_node *n; |
Frederic Weisbecker | 1b3a0e9 | 2011-01-14 04:51:58 +0100 | [diff] [blame] | 977 | int old_pos = cursor->nr; |
Frederic Weisbecker | 612d4fd | 2010-08-22 21:10:35 +0200 | [diff] [blame] | 978 | int err = 0; |
| 979 | |
| 980 | list_for_each_entry_safe(list, next_list, &src->val, list) { |
Frederic Weisbecker | 1b3a0e9 | 2011-01-14 04:51:58 +0100 | [diff] [blame] | 981 | callchain_cursor_append(cursor, list->ip, |
Jin Yao | 410024d | 2016-10-31 09:19:49 +0800 | [diff] [blame] | 982 | list->ms.map, list->ms.sym, |
Jin Yao | b851dd4 | 2017-07-18 20:13:15 +0800 | [diff] [blame] | 983 | false, NULL, 0, 0, 0); |
Frederic Weisbecker | 612d4fd | 2010-08-22 21:10:35 +0200 | [diff] [blame] | 984 | list_del(&list->list); |
Krister Johansen | 9c68ae9 | 2017-01-05 22:23:31 -0800 | [diff] [blame] | 985 | map__zput(list->ms.map); |
Frederic Weisbecker | 612d4fd | 2010-08-22 21:10:35 +0200 | [diff] [blame] | 986 | free(list); |
| 987 | } |
| 988 | |
Frederic Weisbecker | 1b3a0e9 | 2011-01-14 04:51:58 +0100 | [diff] [blame] | 989 | if (src->hit) { |
| 990 | callchain_cursor_commit(cursor); |
Namhyung Kim | dca0d12 | 2016-02-16 23:08:24 +0900 | [diff] [blame] | 991 | if (append_chain_children(dst, cursor, src->hit) < 0) |
| 992 | return -1; |
Frederic Weisbecker | 1b3a0e9 | 2011-01-14 04:51:58 +0100 | [diff] [blame] | 993 | } |
Frederic Weisbecker | 612d4fd | 2010-08-22 21:10:35 +0200 | [diff] [blame] | 994 | |
Namhyung Kim | e369517 | 2013-10-11 14:15:36 +0900 | [diff] [blame] | 995 | 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 Weisbecker | 1b3a0e9 | 2011-01-14 04:51:58 +0100 | [diff] [blame] | 1001 | err = merge_chain_branch(cursor, dst, child); |
Frederic Weisbecker | 612d4fd | 2010-08-22 21:10:35 +0200 | [diff] [blame] | 1002 | if (err) |
| 1003 | break; |
| 1004 | |
Frederic Weisbecker | 612d4fd | 2010-08-22 21:10:35 +0200 | [diff] [blame] | 1005 | free(child); |
| 1006 | } |
| 1007 | |
Frederic Weisbecker | 1b3a0e9 | 2011-01-14 04:51:58 +0100 | [diff] [blame] | 1008 | cursor->nr = old_pos; |
| 1009 | cursor->last = old_last; |
Frederic Weisbecker | 612d4fd | 2010-08-22 21:10:35 +0200 | [diff] [blame] | 1010 | |
| 1011 | return err; |
| 1012 | } |
| 1013 | |
Frederic Weisbecker | 1b3a0e9 | 2011-01-14 04:51:58 +0100 | [diff] [blame] | 1014 | int callchain_merge(struct callchain_cursor *cursor, |
| 1015 | struct callchain_root *dst, struct callchain_root *src) |
Frederic Weisbecker | 612d4fd | 2010-08-22 21:10:35 +0200 | [diff] [blame] | 1016 | { |
Frederic Weisbecker | 1b3a0e9 | 2011-01-14 04:51:58 +0100 | [diff] [blame] | 1017 | return merge_chain_branch(cursor, &dst->node, &src->node); |
| 1018 | } |
Frederic Weisbecker | 612d4fd | 2010-08-22 21:10:35 +0200 | [diff] [blame] | 1019 | |
Frederic Weisbecker | 1b3a0e9 | 2011-01-14 04:51:58 +0100 | [diff] [blame] | 1020 | int callchain_cursor_append(struct callchain_cursor *cursor, |
Jin Yao | 410024d | 2016-10-31 09:19:49 +0800 | [diff] [blame] | 1021 | u64 ip, struct map *map, struct symbol *sym, |
| 1022 | bool branch, struct branch_flags *flags, |
Jin Yao | c4ee062 | 2017-08-07 21:05:15 +0800 | [diff] [blame] | 1023 | int nr_loop_iter, u64 iter_cycles, u64 branch_from) |
Frederic Weisbecker | 1b3a0e9 | 2011-01-14 04:51:58 +0100 | [diff] [blame] | 1024 | { |
| 1025 | struct callchain_cursor_node *node = *cursor->last; |
Frederic Weisbecker | 612d4fd | 2010-08-22 21:10:35 +0200 | [diff] [blame] | 1026 | |
Frederic Weisbecker | 1b3a0e9 | 2011-01-14 04:51:58 +0100 | [diff] [blame] | 1027 | if (!node) { |
Paul Gortmaker | 91b9880 | 2013-01-30 20:05:49 -0500 | [diff] [blame] | 1028 | node = calloc(1, sizeof(*node)); |
Frederic Weisbecker | 1b3a0e9 | 2011-01-14 04:51:58 +0100 | [diff] [blame] | 1029 | if (!node) |
| 1030 | return -ENOMEM; |
Frederic Weisbecker | 612d4fd | 2010-08-22 21:10:35 +0200 | [diff] [blame] | 1031 | |
Frederic Weisbecker | 1b3a0e9 | 2011-01-14 04:51:58 +0100 | [diff] [blame] | 1032 | *cursor->last = node; |
| 1033 | } |
Frederic Weisbecker | 612d4fd | 2010-08-22 21:10:35 +0200 | [diff] [blame] | 1034 | |
Frederic Weisbecker | 1b3a0e9 | 2011-01-14 04:51:58 +0100 | [diff] [blame] | 1035 | node->ip = ip; |
Krister Johansen | 9c68ae9 | 2017-01-05 22:23:31 -0800 | [diff] [blame] | 1036 | map__zput(node->map); |
| 1037 | node->map = map__get(map); |
Frederic Weisbecker | 1b3a0e9 | 2011-01-14 04:51:58 +0100 | [diff] [blame] | 1038 | node->sym = sym; |
Jin Yao | 410024d | 2016-10-31 09:19:49 +0800 | [diff] [blame] | 1039 | node->branch = branch; |
| 1040 | node->nr_loop_iter = nr_loop_iter; |
Jin Yao | c4ee062 | 2017-08-07 21:05:15 +0800 | [diff] [blame] | 1041 | node->iter_cycles = iter_cycles; |
Jin Yao | 410024d | 2016-10-31 09:19:49 +0800 | [diff] [blame] | 1042 | |
| 1043 | if (flags) |
| 1044 | memcpy(&node->branch_flags, flags, |
| 1045 | sizeof(struct branch_flags)); |
Frederic Weisbecker | 612d4fd | 2010-08-22 21:10:35 +0200 | [diff] [blame] | 1046 | |
Jin Yao | b851dd4 | 2017-07-18 20:13:15 +0800 | [diff] [blame] | 1047 | node->branch_from = branch_from; |
Frederic Weisbecker | 1b3a0e9 | 2011-01-14 04:51:58 +0100 | [diff] [blame] | 1048 | cursor->nr++; |
| 1049 | |
| 1050 | cursor->last = &node->next; |
| 1051 | |
| 1052 | return 0; |
Frederic Weisbecker | 612d4fd | 2010-08-22 21:10:35 +0200 | [diff] [blame] | 1053 | } |
Namhyung Kim | 2dc9fb1 | 2014-01-14 14:25:35 +0900 | [diff] [blame] | 1054 | |
Arnaldo Carvalho de Melo | 91d7b2d | 2016-04-14 14:48:07 -0300 | [diff] [blame] | 1055 | int sample__resolve_callchain(struct perf_sample *sample, |
| 1056 | struct callchain_cursor *cursor, struct symbol **parent, |
Namhyung Kim | 2dc9fb1 | 2014-01-14 14:25:35 +0900 | [diff] [blame] | 1057 | struct perf_evsel *evsel, struct addr_location *al, |
| 1058 | int max_stack) |
| 1059 | { |
Jin Yao | b49a821 | 2017-05-08 18:43:02 +0800 | [diff] [blame] | 1060 | if (sample->callchain == NULL && !symbol_conf.show_branchflag_count) |
Namhyung Kim | 2dc9fb1 | 2014-01-14 14:25:35 +0900 | [diff] [blame] | 1061 | return 0; |
| 1062 | |
Namhyung Kim | 7a13aa2 | 2012-09-11 14:13:04 +0900 | [diff] [blame] | 1063 | if (symbol_conf.use_callchain || symbol_conf.cumulate_callchain || |
Jin Yao | b49a821 | 2017-05-08 18:43:02 +0800 | [diff] [blame] | 1064 | perf_hpp_list.parent || symbol_conf.show_branchflag_count) { |
Arnaldo Carvalho de Melo | 91d7b2d | 2016-04-14 14:48:07 -0300 | [diff] [blame] | 1065 | return thread__resolve_callchain(al->thread, cursor, evsel, sample, |
Arnaldo Carvalho de Melo | cc8b7c2 | 2014-10-23 15:26:17 -0300 | [diff] [blame] | 1066 | parent, al, max_stack); |
Namhyung Kim | 2dc9fb1 | 2014-01-14 14:25:35 +0900 | [diff] [blame] | 1067 | } |
| 1068 | return 0; |
| 1069 | } |
| 1070 | |
| 1071 | int hist_entry__append_callchain(struct hist_entry *he, struct perf_sample *sample) |
| 1072 | { |
Jin Yao | b49a821 | 2017-05-08 18:43:02 +0800 | [diff] [blame] | 1073 | if ((!symbol_conf.use_callchain || sample->callchain == NULL) && |
| 1074 | !symbol_conf.show_branchflag_count) |
Namhyung Kim | 2dc9fb1 | 2014-01-14 14:25:35 +0900 | [diff] [blame] | 1075 | return 0; |
| 1076 | return callchain_append(he->callchain, &callchain_cursor, sample->period); |
| 1077 | } |
Namhyung Kim | c7405d8 | 2013-10-31 13:58:30 +0900 | [diff] [blame] | 1078 | |
| 1079 | int 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 | |
| 1117 | out: |
| 1118 | return 1; |
| 1119 | } |
Andi Kleen | 2989cca | 2014-11-12 18:05:23 -0800 | [diff] [blame] | 1120 | |
| 1121 | char *callchain_list__sym_name(struct callchain_list *cl, |
| 1122 | char *bf, size_t bfsize, bool show_dso) |
| 1123 | { |
Milian Wolff | 5dfa210 | 2017-03-18 22:49:28 +0100 | [diff] [blame] | 1124 | bool show_addr = callchain_param.key == CCKEY_ADDRESS; |
| 1125 | bool show_srcline = show_addr || callchain_param.key == CCKEY_SRCLINE; |
Andi Kleen | 2989cca | 2014-11-12 18:05:23 -0800 | [diff] [blame] | 1126 | int printed; |
| 1127 | |
| 1128 | if (cl->ms.sym) { |
Milian Wolff | 5dfa210 | 2017-03-18 22:49:28 +0100 | [diff] [blame] | 1129 | if (show_srcline && cl->ms.map && !cl->srcline) |
Andi Kleen | 23f0981 | 2014-11-12 18:05:24 -0800 | [diff] [blame] | 1130 | cl->srcline = get_srcline(cl->ms.map->dso, |
| 1131 | map__rip_2objdump(cl->ms.map, |
Andi Kleen | 85c116a | 2014-11-12 18:05:27 -0800 | [diff] [blame] | 1132 | cl->ip), |
Milian Wolff | 5dfa210 | 2017-03-18 22:49:28 +0100 | [diff] [blame] | 1133 | cl->ms.sym, false, show_addr); |
Andi Kleen | 23f0981 | 2014-11-12 18:05:24 -0800 | [diff] [blame] | 1134 | 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 Kleen | 2989cca | 2014-11-12 18:05:23 -0800 | [diff] [blame] | 1139 | } 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 Kim | d114960 | 2014-12-30 14:38:13 +0900 | [diff] [blame] | 1150 | |
Namhyung Kim | 5ab250c | 2015-11-09 14:45:39 +0900 | [diff] [blame] | 1151 | char *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 Kim | f2af008 | 2015-11-09 14:45:41 +0900 | [diff] [blame] | 1156 | unsigned count = callchain_cumul_counts(node); |
Namhyung Kim | 5ab250c | 2015-11-09 14:45:39 +0900 | [diff] [blame] | 1157 | |
Namhyung Kim | f2af008 | 2015-11-09 14:45:41 +0900 | [diff] [blame] | 1158 | if (callchain_param.mode == CHAIN_FOLDED) { |
Namhyung Kim | 5ab250c | 2015-11-09 14:45:39 +0900 | [diff] [blame] | 1159 | period = node->hit; |
Namhyung Kim | f2af008 | 2015-11-09 14:45:41 +0900 | [diff] [blame] | 1160 | count = node->count; |
| 1161 | } |
Namhyung Kim | 5ab250c | 2015-11-09 14:45:39 +0900 | [diff] [blame] | 1162 | |
Namhyung Kim | f2af008 | 2015-11-09 14:45:41 +0900 | [diff] [blame] | 1163 | 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 Kim | 5ab250c | 2015-11-09 14:45:39 +0900 | [diff] [blame] | 1177 | return bf; |
| 1178 | } |
| 1179 | |
| 1180 | int 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 Kim | f2af008 | 2015-11-09 14:45:41 +0900 | [diff] [blame] | 1185 | unsigned count = callchain_cumul_counts(node); |
Namhyung Kim | 5ab250c | 2015-11-09 14:45:39 +0900 | [diff] [blame] | 1186 | |
Namhyung Kim | f2af008 | 2015-11-09 14:45:41 +0900 | [diff] [blame] | 1187 | if (callchain_param.mode == CHAIN_FOLDED) { |
Namhyung Kim | 5ab250c | 2015-11-09 14:45:39 +0900 | [diff] [blame] | 1188 | period = node->hit; |
Namhyung Kim | f2af008 | 2015-11-09 14:45:41 +0900 | [diff] [blame] | 1189 | count = node->count; |
| 1190 | } |
Namhyung Kim | 5ab250c | 2015-11-09 14:45:39 +0900 | [diff] [blame] | 1191 | |
Namhyung Kim | f2af008 | 2015-11-09 14:45:41 +0900 | [diff] [blame] | 1192 | 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 Kim | 5ab250c | 2015-11-09 14:45:39 +0900 | [diff] [blame] | 1204 | } |
| 1205 | |
Jin Yao | 3dd029e | 2016-10-31 09:19:51 +0800 | [diff] [blame] | 1206 | static 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 | |
| 1227 | static 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 | |
| 1254 | int 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 Yao | 8d51735 | 2017-07-18 20:13:12 +0800 | [diff] [blame] | 1277 | static 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 Yao | a1a8bed | 2017-07-24 19:09:07 +0800 | [diff] [blame] | 1286 | static int count_float_printf(int idx, const char *str, float value, |
| 1287 | char *bf, int bfsize, float threshold) |
Jin Yao | 8d51735 | 2017-07-18 20:13:12 +0800 | [diff] [blame] | 1288 | { |
| 1289 | int printed; |
| 1290 | |
Jin Yao | a1a8bed | 2017-07-24 19:09:07 +0800 | [diff] [blame] | 1291 | if (threshold != 0.0 && value < threshold) |
| 1292 | return 0; |
| 1293 | |
Jin Yao | 8d51735 | 2017-07-18 20:13:12 +0800 | [diff] [blame] | 1294 | printed = scnprintf(bf, bfsize, "%s%s:%.1f%%", (idx) ? " " : " (", str, value); |
| 1295 | |
| 1296 | return printed; |
| 1297 | } |
| 1298 | |
Jin Yao | a1a8bed | 2017-07-24 19:09:07 +0800 | [diff] [blame] | 1299 | static 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 Yao | c1dfcfa | 2017-03-09 16:06:26 +0800 | [diff] [blame] | 1303 | { |
Jin Yao | b851dd4 | 2017-07-18 20:13:15 +0800 | [diff] [blame] | 1304 | int printed, i = 0; |
Jin Yao | c1dfcfa | 2017-03-09 16:06:26 +0800 | [diff] [blame] | 1305 | |
Jin Yao | b851dd4 | 2017-07-18 20:13:15 +0800 | [diff] [blame] | 1306 | printed = branch_type_str(brtype_stat, bf, bfsize); |
| 1307 | if (printed) |
| 1308 | i++; |
| 1309 | |
Jin Yao | 8d51735 | 2017-07-18 20:13:12 +0800 | [diff] [blame] | 1310 | if (predicted_count < branch_count) { |
| 1311 | printed += count_float_printf(i++, "predicted", |
| 1312 | predicted_count * 100.0 / branch_count, |
Jin Yao | a1a8bed | 2017-07-24 19:09:07 +0800 | [diff] [blame] | 1313 | bf + printed, bfsize - printed, 0.0); |
Jin Yao | 8d51735 | 2017-07-18 20:13:12 +0800 | [diff] [blame] | 1314 | } |
| 1315 | |
| 1316 | if (abort_count) { |
| 1317 | printed += count_float_printf(i++, "abort", |
| 1318 | abort_count * 100.0 / branch_count, |
Jin Yao | a1a8bed | 2017-07-24 19:09:07 +0800 | [diff] [blame] | 1319 | bf + printed, bfsize - printed, 0.1); |
Jin Yao | 8d51735 | 2017-07-18 20:13:12 +0800 | [diff] [blame] | 1320 | } |
| 1321 | |
Jin Yao | a1a8bed | 2017-07-24 19:09:07 +0800 | [diff] [blame] | 1322 | if (i) |
| 1323 | printed += scnprintf(bf + printed, bfsize - printed, ")"); |
| 1324 | |
| 1325 | return printed; |
| 1326 | } |
| 1327 | |
| 1328 | static int branch_from_str(char *bf, int bfsize, |
| 1329 | u64 branch_count, |
| 1330 | u64 cycles_count, u64 iter_count, |
Jin Yao | c4ee062 | 2017-08-07 21:05:15 +0800 | [diff] [blame] | 1331 | u64 iter_cycles) |
Jin Yao | a1a8bed | 2017-07-24 19:09:07 +0800 | [diff] [blame] | 1332 | { |
| 1333 | int printed = 0, i = 0; |
| 1334 | u64 cycles; |
| 1335 | |
Jin Yao | c1dfcfa | 2017-03-09 16:06:26 +0800 | [diff] [blame] | 1336 | cycles = cycles_count / branch_count; |
Jin Yao | 8d51735 | 2017-07-18 20:13:12 +0800 | [diff] [blame] | 1337 | if (cycles) { |
| 1338 | printed += count_pri64_printf(i++, "cycles", |
| 1339 | cycles, |
| 1340 | bf + printed, bfsize - printed); |
| 1341 | } |
Jin Yao | c1dfcfa | 2017-03-09 16:06:26 +0800 | [diff] [blame] | 1342 | |
Jin Yao | c4ee062 | 2017-08-07 21:05:15 +0800 | [diff] [blame] | 1343 | 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 Yao | 8d51735 | 2017-07-18 20:13:12 +0800 | [diff] [blame] | 1350 | bf + printed, bfsize - printed); |
Jin Yao | c1dfcfa | 2017-03-09 16:06:26 +0800 | [diff] [blame] | 1351 | } |
| 1352 | |
Jin Yao | 8d51735 | 2017-07-18 20:13:12 +0800 | [diff] [blame] | 1353 | if (i) |
Jin Yao | a1a8bed | 2017-07-24 19:09:07 +0800 | [diff] [blame] | 1354 | printed += scnprintf(bf + printed, bfsize - printed, ")"); |
Jin Yao | c1dfcfa | 2017-03-09 16:06:26 +0800 | [diff] [blame] | 1355 | |
Jin Yao | a1a8bed | 2017-07-24 19:09:07 +0800 | [diff] [blame] | 1356 | return printed; |
| 1357 | } |
| 1358 | |
| 1359 | static int counts_str_build(char *bf, int bfsize, |
| 1360 | u64 branch_count, u64 predicted_count, |
| 1361 | u64 abort_count, u64 cycles_count, |
Jin Yao | c4ee062 | 2017-08-07 21:05:15 +0800 | [diff] [blame] | 1362 | u64 iter_count, u64 iter_cycles, |
Jin Yao | a1a8bed | 2017-07-24 19:09:07 +0800 | [diff] [blame] | 1363 | 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 Yao | c4ee062 | 2017-08-07 21:05:15 +0800 | [diff] [blame] | 1375 | cycles_count, iter_count, iter_cycles); |
Jin Yao | a1a8bed | 2017-07-24 19:09:07 +0800 | [diff] [blame] | 1376 | } |
| 1377 | |
| 1378 | if (!printed) |
| 1379 | bf[0] = 0; |
| 1380 | |
| 1381 | return printed; |
Jin Yao | c1dfcfa | 2017-03-09 16:06:26 +0800 | [diff] [blame] | 1382 | } |
| 1383 | |
Jin Yao | 3dd029e | 2016-10-31 09:19:51 +0800 | [diff] [blame] | 1384 | static 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 Yao | c4ee062 | 2017-08-07 21:05:15 +0800 | [diff] [blame] | 1387 | u64 iter_count, u64 iter_cycles, |
Jin Yao | b851dd4 | 2017-07-18 20:13:15 +0800 | [diff] [blame] | 1388 | struct branch_type_stat *brtype_stat) |
Jin Yao | 3dd029e | 2016-10-31 09:19:51 +0800 | [diff] [blame] | 1389 | { |
Jin Yao | b851dd4 | 2017-07-18 20:13:15 +0800 | [diff] [blame] | 1390 | char str[256]; |
Jin Yao | 3dd029e | 2016-10-31 09:19:51 +0800 | [diff] [blame] | 1391 | |
Jin Yao | c1dfcfa | 2017-03-09 16:06:26 +0800 | [diff] [blame] | 1392 | counts_str_build(str, sizeof(str), branch_count, |
| 1393 | predicted_count, abort_count, cycles_count, |
Jin Yao | c4ee062 | 2017-08-07 21:05:15 +0800 | [diff] [blame] | 1394 | iter_count, iter_cycles, brtype_stat); |
Jin Yao | 3dd029e | 2016-10-31 09:19:51 +0800 | [diff] [blame] | 1395 | |
| 1396 | if (fp) |
Jin Yao | c1dfcfa | 2017-03-09 16:06:26 +0800 | [diff] [blame] | 1397 | return fprintf(fp, "%s", str); |
Jin Yao | 3dd029e | 2016-10-31 09:19:51 +0800 | [diff] [blame] | 1398 | |
Jin Yao | c1dfcfa | 2017-03-09 16:06:26 +0800 | [diff] [blame] | 1399 | return scnprintf(bf, bfsize, "%s", str); |
Jin Yao | 3dd029e | 2016-10-31 09:19:51 +0800 | [diff] [blame] | 1400 | } |
| 1401 | |
Jin Yao | c4ee062 | 2017-08-07 21:05:15 +0800 | [diff] [blame] | 1402 | int callchain_list_counts__printf_value(struct callchain_list *clist, |
Jin Yao | 3dd029e | 2016-10-31 09:19:51 +0800 | [diff] [blame] | 1403 | FILE *fp, char *bf, int bfsize) |
| 1404 | { |
| 1405 | u64 branch_count, predicted_count; |
| 1406 | u64 abort_count, cycles_count; |
Jin Yao | c4ee062 | 2017-08-07 21:05:15 +0800 | [diff] [blame] | 1407 | u64 iter_count, iter_cycles; |
Jin Yao | 3dd029e | 2016-10-31 09:19:51 +0800 | [diff] [blame] | 1408 | |
| 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 Yao | c4ee062 | 2017-08-07 21:05:15 +0800 | [diff] [blame] | 1413 | iter_count = clist->iter_count; |
| 1414 | iter_cycles = clist->iter_cycles; |
Jin Yao | 3dd029e | 2016-10-31 09:19:51 +0800 | [diff] [blame] | 1415 | |
| 1416 | return callchain_counts_printf(fp, bf, bfsize, branch_count, |
| 1417 | predicted_count, abort_count, |
Jin Yao | c4ee062 | 2017-08-07 21:05:15 +0800 | [diff] [blame] | 1418 | cycles_count, iter_count, iter_cycles, |
Jin Yao | b851dd4 | 2017-07-18 20:13:15 +0800 | [diff] [blame] | 1419 | &clist->brtype_stat); |
Jin Yao | 3dd029e | 2016-10-31 09:19:51 +0800 | [diff] [blame] | 1420 | } |
| 1421 | |
Namhyung Kim | d114960 | 2014-12-30 14:38:13 +0900 | [diff] [blame] | 1422 | static 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 Kim | 4b3a321 | 2015-11-09 14:45:43 +0900 | [diff] [blame] | 1428 | list_for_each_entry_safe(list, tmp, &node->parent_val, list) { |
| 1429 | list_del(&list->list); |
Krister Johansen | 9c68ae9 | 2017-01-05 22:23:31 -0800 | [diff] [blame] | 1430 | map__zput(list->ms.map); |
Namhyung Kim | 4b3a321 | 2015-11-09 14:45:43 +0900 | [diff] [blame] | 1431 | free(list); |
| 1432 | } |
| 1433 | |
Namhyung Kim | d114960 | 2014-12-30 14:38:13 +0900 | [diff] [blame] | 1434 | list_for_each_entry_safe(list, tmp, &node->val, list) { |
| 1435 | list_del(&list->list); |
Krister Johansen | 9c68ae9 | 2017-01-05 22:23:31 -0800 | [diff] [blame] | 1436 | map__zput(list->ms.map); |
Namhyung Kim | d114960 | 2014-12-30 14:38:13 +0900 | [diff] [blame] | 1437 | 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 | |
| 1451 | void free_callchain(struct callchain_root *root) |
| 1452 | { |
| 1453 | if (!symbol_conf.use_callchain) |
| 1454 | return; |
| 1455 | |
| 1456 | free_callchain_node(&root->node); |
| 1457 | } |
Namhyung Kim | 4b3a321 | 2015-11-09 14:45:43 +0900 | [diff] [blame] | 1458 | |
Namhyung Kim | 42b276a | 2016-01-05 12:06:00 +0900 | [diff] [blame] | 1459 | static 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 | |
| 1479 | void 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 Kim | 4b3a321 | 2015-11-09 14:45:43 +0900 | [diff] [blame] | 1487 | int 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 Johansen | 9c68ae9 | 2017-01-05 22:23:31 -0800 | [diff] [blame] | 1500 | map__get(new->ms.map); |
Namhyung Kim | 4b3a321 | 2015-11-09 14:45:43 +0900 | [diff] [blame] | 1501 | 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 | |
| 1518 | out: |
| 1519 | list_for_each_entry_safe(chain, new, &head, list) { |
| 1520 | list_del(&chain->list); |
Krister Johansen | 9c68ae9 | 2017-01-05 22:23:31 -0800 | [diff] [blame] | 1521 | map__zput(chain->ms.map); |
Namhyung Kim | 4b3a321 | 2015-11-09 14:45:43 +0900 | [diff] [blame] | 1522 | free(chain); |
| 1523 | } |
| 1524 | return -ENOMEM; |
| 1525 | } |
Namhyung Kim | 571f1eb | 2016-12-06 12:40:02 +0900 | [diff] [blame] | 1526 | |
| 1527 | int 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 Yao | c4ee062 | 2017-08-07 21:05:15 +0800 | [diff] [blame] | 1544 | node->nr_loop_iter, |
| 1545 | node->iter_cycles, |
Jin Yao | b851dd4 | 2017-07-18 20:13:15 +0800 | [diff] [blame] | 1546 | node->branch_from); |
Namhyung Kim | 571f1eb | 2016-12-06 12:40:02 +0900 | [diff] [blame] | 1547 | if (rc) |
| 1548 | break; |
| 1549 | |
| 1550 | callchain_cursor_advance(src); |
| 1551 | } |
| 1552 | |
| 1553 | return rc; |
| 1554 | } |