Commit | Line | Data |
---|---|---|
8cb76d99 | 1 | /* |
1b3a0e95 | 2 | * Copyright (C) 2009-2011, Frederic Weisbecker <fweisbec@gmail.com> |
8cb76d99 FW |
3 | * |
4 | * Handle the callchains from the stream in an ad-hoc radix tree and then | |
5 | * sort them in an rbtree. | |
6 | * | |
deac911c FW |
7 | * Using a radix for code path provides a fast retrieval and factorizes |
8 | * memory use. Also that lets us use the paths in a hierarchical graph view. | |
9 | * | |
8cb76d99 FW |
10 | */ |
11 | ||
12 | #include <stdlib.h> | |
13 | #include <stdio.h> | |
14 | #include <stdbool.h> | |
15 | #include <errno.h> | |
c0a8865e | 16 | #include <math.h> |
8cb76d99 | 17 | |
b965bb41 FW |
18 | #include "asm/bug.h" |
19 | ||
99571ab3 | 20 | #include "hist.h" |
b36f19d5 | 21 | #include "util.h" |
2dc9fb1a NK |
22 | #include "sort.h" |
23 | #include "machine.h" | |
8cb76d99 FW |
24 | #include "callchain.h" |
25 | ||
47260645 NK |
26 | __thread struct callchain_cursor callchain_cursor; |
27 | ||
f7f084f4 NK |
28 | #ifdef HAVE_DWARF_UNWIND_SUPPORT |
29 | static int get_stack_size(const char *str, unsigned long *_size) | |
30 | { | |
31 | char *endptr; | |
32 | unsigned long size; | |
33 | unsigned long max_size = round_down(USHRT_MAX, sizeof(u64)); | |
34 | ||
35 | size = strtoul(str, &endptr, 0); | |
36 | ||
37 | do { | |
38 | if (*endptr) | |
39 | break; | |
40 | ||
41 | size = round_up(size, sizeof(u64)); | |
42 | if (!size || size > max_size) | |
43 | break; | |
44 | ||
45 | *_size = size; | |
46 | return 0; | |
47 | ||
48 | } while (0); | |
49 | ||
50 | pr_err("callchain: Incorrect stack dump size (max %ld): %s\n", | |
51 | max_size, str); | |
52 | return -1; | |
53 | } | |
54 | #endif /* HAVE_DWARF_UNWIND_SUPPORT */ | |
55 | ||
56 | int parse_callchain_record_opt(const char *arg) | |
57 | { | |
58 | char *tok, *name, *saveptr = NULL; | |
59 | char *buf; | |
60 | int ret = -1; | |
61 | ||
62 | /* We need buffer that we know we can write to. */ | |
63 | buf = malloc(strlen(arg) + 1); | |
64 | if (!buf) | |
65 | return -ENOMEM; | |
66 | ||
67 | strcpy(buf, arg); | |
68 | ||
69 | tok = strtok_r((char *)buf, ",", &saveptr); | |
70 | name = tok ? : (char *)buf; | |
71 | ||
72 | do { | |
73 | /* Framepointer style */ | |
74 | if (!strncmp(name, "fp", sizeof("fp"))) { | |
75 | if (!strtok_r(NULL, ",", &saveptr)) { | |
76 | callchain_param.record_mode = CALLCHAIN_FP; | |
77 | ret = 0; | |
78 | } else | |
79 | pr_err("callchain: No more arguments " | |
80 | "needed for -g fp\n"); | |
81 | break; | |
82 | ||
83 | #ifdef HAVE_DWARF_UNWIND_SUPPORT | |
84 | /* Dwarf style */ | |
85 | } else if (!strncmp(name, "dwarf", sizeof("dwarf"))) { | |
86 | const unsigned long default_stack_dump_size = 8192; | |
87 | ||
88 | ret = 0; | |
89 | callchain_param.record_mode = CALLCHAIN_DWARF; | |
90 | callchain_param.dump_size = default_stack_dump_size; | |
91 | ||
92 | tok = strtok_r(NULL, ",", &saveptr); | |
93 | if (tok) { | |
94 | unsigned long size = 0; | |
95 | ||
96 | ret = get_stack_size(tok, &size); | |
97 | callchain_param.dump_size = size; | |
98 | } | |
99 | #endif /* HAVE_DWARF_UNWIND_SUPPORT */ | |
100 | } else { | |
101 | pr_err("callchain: Unknown --call-graph option " | |
102 | "value: %s\n", arg); | |
103 | break; | |
104 | } | |
105 | ||
106 | } while (0); | |
107 | ||
108 | free(buf); | |
109 | return ret; | |
110 | } | |
111 | ||
2b9240ca NK |
112 | static int parse_callchain_mode(const char *value) |
113 | { | |
114 | if (!strncmp(value, "graph", strlen(value))) { | |
115 | callchain_param.mode = CHAIN_GRAPH_ABS; | |
116 | return 0; | |
117 | } | |
118 | if (!strncmp(value, "flat", strlen(value))) { | |
119 | callchain_param.mode = CHAIN_FLAT; | |
120 | return 0; | |
121 | } | |
122 | if (!strncmp(value, "fractal", strlen(value))) { | |
123 | callchain_param.mode = CHAIN_GRAPH_REL; | |
124 | return 0; | |
125 | } | |
126 | return -1; | |
127 | } | |
128 | ||
129 | static int parse_callchain_order(const char *value) | |
130 | { | |
131 | if (!strncmp(value, "caller", strlen(value))) { | |
132 | callchain_param.order = ORDER_CALLER; | |
133 | return 0; | |
134 | } | |
135 | if (!strncmp(value, "callee", strlen(value))) { | |
136 | callchain_param.order = ORDER_CALLEE; | |
137 | return 0; | |
138 | } | |
139 | return -1; | |
140 | } | |
141 | ||
142 | static int parse_callchain_sort_key(const char *value) | |
143 | { | |
144 | if (!strncmp(value, "function", strlen(value))) { | |
145 | callchain_param.key = CCKEY_FUNCTION; | |
146 | return 0; | |
147 | } | |
148 | if (!strncmp(value, "address", strlen(value))) { | |
149 | callchain_param.key = CCKEY_ADDRESS; | |
150 | return 0; | |
151 | } | |
152 | return -1; | |
153 | } | |
154 | ||
cff6bb46 DZ |
155 | int |
156 | parse_callchain_report_opt(const char *arg) | |
157 | { | |
e8232f1a | 158 | char *tok; |
cff6bb46 | 159 | char *endptr; |
e8232f1a | 160 | bool minpcnt_set = false; |
cff6bb46 DZ |
161 | |
162 | symbol_conf.use_callchain = true; | |
163 | ||
164 | if (!arg) | |
165 | return 0; | |
166 | ||
e8232f1a NK |
167 | while ((tok = strtok((char *)arg, ",")) != NULL) { |
168 | if (!strncmp(tok, "none", strlen(tok))) { | |
169 | callchain_param.mode = CHAIN_NONE; | |
170 | symbol_conf.use_callchain = false; | |
171 | return 0; | |
172 | } | |
173 | ||
2b9240ca NK |
174 | if (!parse_callchain_mode(tok) || |
175 | !parse_callchain_order(tok) || | |
176 | !parse_callchain_sort_key(tok)) { | |
177 | /* parsing ok - move on to the next */ | |
178 | } else if (!minpcnt_set) { | |
179 | /* try to get the min percent */ | |
e8232f1a NK |
180 | callchain_param.min_percent = strtod(tok, &endptr); |
181 | if (tok == endptr) | |
182 | return -1; | |
183 | minpcnt_set = true; | |
184 | } else { | |
185 | /* try print limit at last */ | |
186 | callchain_param.print_limit = strtoul(tok, &endptr, 0); | |
187 | if (tok == endptr) | |
188 | return -1; | |
189 | } | |
190 | ||
191 | arg = NULL; | |
cff6bb46 DZ |
192 | } |
193 | ||
cff6bb46 DZ |
194 | if (callchain_register_param(&callchain_param) < 0) { |
195 | pr_err("Can't register callchain params\n"); | |
196 | return -1; | |
197 | } | |
198 | return 0; | |
199 | } | |
200 | ||
2b9240ca NK |
201 | int perf_callchain_config(const char *var, const char *value) |
202 | { | |
203 | char *endptr; | |
204 | ||
205 | if (prefixcmp(var, "call-graph.")) | |
206 | return 0; | |
207 | var += sizeof("call-graph.") - 1; | |
208 | ||
209 | if (!strcmp(var, "record-mode")) | |
210 | return parse_callchain_record_opt(value); | |
211 | #ifdef HAVE_DWARF_UNWIND_SUPPORT | |
212 | if (!strcmp(var, "dump-size")) { | |
213 | unsigned long size = 0; | |
214 | int ret; | |
215 | ||
216 | ret = get_stack_size(value, &size); | |
217 | callchain_param.dump_size = size; | |
218 | ||
219 | return ret; | |
220 | } | |
221 | #endif | |
222 | if (!strcmp(var, "print-type")) | |
223 | return parse_callchain_mode(value); | |
224 | if (!strcmp(var, "order")) | |
225 | return parse_callchain_order(value); | |
226 | if (!strcmp(var, "sort-key")) | |
227 | return parse_callchain_sort_key(value); | |
228 | if (!strcmp(var, "threshold")) { | |
229 | callchain_param.min_percent = strtod(value, &endptr); | |
230 | if (value == endptr) | |
231 | return -1; | |
232 | } | |
233 | if (!strcmp(var, "print-limit")) { | |
234 | callchain_param.print_limit = strtod(value, &endptr); | |
235 | if (value == endptr) | |
236 | return -1; | |
237 | } | |
238 | ||
239 | return 0; | |
240 | } | |
241 | ||
deac911c | 242 | static void |
4eb3e478 FW |
243 | rb_insert_callchain(struct rb_root *root, struct callchain_node *chain, |
244 | enum chain_mode mode) | |
8cb76d99 FW |
245 | { |
246 | struct rb_node **p = &root->rb_node; | |
247 | struct rb_node *parent = NULL; | |
248 | struct callchain_node *rnode; | |
f08c3154 | 249 | u64 chain_cumul = callchain_cumul_hits(chain); |
8cb76d99 FW |
250 | |
251 | while (*p) { | |
1953287b FW |
252 | u64 rnode_cumul; |
253 | ||
8cb76d99 FW |
254 | parent = *p; |
255 | rnode = rb_entry(parent, struct callchain_node, rb_node); | |
f08c3154 | 256 | rnode_cumul = callchain_cumul_hits(rnode); |
8cb76d99 | 257 | |
4eb3e478 | 258 | switch (mode) { |
805d127d | 259 | case CHAIN_FLAT: |
4eb3e478 FW |
260 | if (rnode->hit < chain->hit) |
261 | p = &(*p)->rb_left; | |
262 | else | |
263 | p = &(*p)->rb_right; | |
264 | break; | |
805d127d FW |
265 | case CHAIN_GRAPH_ABS: /* Falldown */ |
266 | case CHAIN_GRAPH_REL: | |
1953287b | 267 | if (rnode_cumul < chain_cumul) |
4eb3e478 FW |
268 | p = &(*p)->rb_left; |
269 | else | |
270 | p = &(*p)->rb_right; | |
271 | break; | |
83a0944f | 272 | case CHAIN_NONE: |
4eb3e478 FW |
273 | default: |
274 | break; | |
275 | } | |
8cb76d99 FW |
276 | } |
277 | ||
278 | rb_link_node(&chain->rb_node, parent, p); | |
279 | rb_insert_color(&chain->rb_node, root); | |
280 | } | |
281 | ||
805d127d FW |
282 | static void |
283 | __sort_chain_flat(struct rb_root *rb_root, struct callchain_node *node, | |
284 | u64 min_hit) | |
285 | { | |
e369517c | 286 | struct rb_node *n; |
805d127d FW |
287 | struct callchain_node *child; |
288 | ||
e369517c NK |
289 | n = rb_first(&node->rb_root_in); |
290 | while (n) { | |
291 | child = rb_entry(n, struct callchain_node, rb_node_in); | |
292 | n = rb_next(n); | |
293 | ||
805d127d | 294 | __sort_chain_flat(rb_root, child, min_hit); |
e369517c | 295 | } |
805d127d FW |
296 | |
297 | if (node->hit && node->hit >= min_hit) | |
298 | rb_insert_callchain(rb_root, node, CHAIN_FLAT); | |
299 | } | |
300 | ||
8cb76d99 FW |
301 | /* |
302 | * Once we get every callchains from the stream, we can now | |
303 | * sort them by hit | |
304 | */ | |
805d127d | 305 | static void |
d2009c51 | 306 | sort_chain_flat(struct rb_root *rb_root, struct callchain_root *root, |
1d037ca1 | 307 | u64 min_hit, struct callchain_param *param __maybe_unused) |
805d127d | 308 | { |
d2009c51 | 309 | __sort_chain_flat(rb_root, &root->node, min_hit); |
805d127d FW |
310 | } |
311 | ||
312 | static void __sort_chain_graph_abs(struct callchain_node *node, | |
313 | u64 min_hit) | |
8cb76d99 | 314 | { |
e369517c | 315 | struct rb_node *n; |
8cb76d99 FW |
316 | struct callchain_node *child; |
317 | ||
805d127d | 318 | node->rb_root = RB_ROOT; |
e369517c NK |
319 | n = rb_first(&node->rb_root_in); |
320 | ||
321 | while (n) { | |
322 | child = rb_entry(n, struct callchain_node, rb_node_in); | |
323 | n = rb_next(n); | |
8cb76d99 | 324 | |
805d127d | 325 | __sort_chain_graph_abs(child, min_hit); |
f08c3154 | 326 | if (callchain_cumul_hits(child) >= min_hit) |
805d127d FW |
327 | rb_insert_callchain(&node->rb_root, child, |
328 | CHAIN_GRAPH_ABS); | |
329 | } | |
330 | } | |
331 | ||
332 | static void | |
d2009c51 | 333 | sort_chain_graph_abs(struct rb_root *rb_root, struct callchain_root *chain_root, |
1d037ca1 | 334 | u64 min_hit, struct callchain_param *param __maybe_unused) |
805d127d | 335 | { |
d2009c51 FW |
336 | __sort_chain_graph_abs(&chain_root->node, min_hit); |
337 | rb_root->rb_node = chain_root->node.rb_root.rb_node; | |
4eb3e478 FW |
338 | } |
339 | ||
805d127d FW |
340 | static void __sort_chain_graph_rel(struct callchain_node *node, |
341 | double min_percent) | |
4eb3e478 | 342 | { |
e369517c | 343 | struct rb_node *n; |
4eb3e478 | 344 | struct callchain_node *child; |
805d127d | 345 | u64 min_hit; |
4eb3e478 FW |
346 | |
347 | node->rb_root = RB_ROOT; | |
c0a8865e | 348 | min_hit = ceil(node->children_hit * min_percent); |
4eb3e478 | 349 | |
e369517c NK |
350 | n = rb_first(&node->rb_root_in); |
351 | while (n) { | |
352 | child = rb_entry(n, struct callchain_node, rb_node_in); | |
353 | n = rb_next(n); | |
354 | ||
805d127d | 355 | __sort_chain_graph_rel(child, min_percent); |
f08c3154 | 356 | if (callchain_cumul_hits(child) >= min_hit) |
805d127d FW |
357 | rb_insert_callchain(&node->rb_root, child, |
358 | CHAIN_GRAPH_REL); | |
4eb3e478 FW |
359 | } |
360 | } | |
361 | ||
805d127d | 362 | static void |
d2009c51 | 363 | sort_chain_graph_rel(struct rb_root *rb_root, struct callchain_root *chain_root, |
1d037ca1 | 364 | u64 min_hit __maybe_unused, struct callchain_param *param) |
4eb3e478 | 365 | { |
d2009c51 FW |
366 | __sort_chain_graph_rel(&chain_root->node, param->min_percent / 100.0); |
367 | rb_root->rb_node = chain_root->node.rb_root.rb_node; | |
8cb76d99 FW |
368 | } |
369 | ||
16537f13 | 370 | int callchain_register_param(struct callchain_param *param) |
805d127d FW |
371 | { |
372 | switch (param->mode) { | |
373 | case CHAIN_GRAPH_ABS: | |
374 | param->sort = sort_chain_graph_abs; | |
375 | break; | |
376 | case CHAIN_GRAPH_REL: | |
377 | param->sort = sort_chain_graph_rel; | |
378 | break; | |
379 | case CHAIN_FLAT: | |
380 | param->sort = sort_chain_flat; | |
381 | break; | |
83a0944f | 382 | case CHAIN_NONE: |
805d127d FW |
383 | default: |
384 | return -1; | |
385 | } | |
386 | return 0; | |
387 | } | |
388 | ||
deac911c FW |
389 | /* |
390 | * Create a child for a parent. If inherit_children, then the new child | |
391 | * will become the new parent of it's parent children | |
392 | */ | |
393 | static struct callchain_node * | |
394 | create_child(struct callchain_node *parent, bool inherit_children) | |
8cb76d99 FW |
395 | { |
396 | struct callchain_node *new; | |
397 | ||
cdd5b75b | 398 | new = zalloc(sizeof(*new)); |
8cb76d99 FW |
399 | if (!new) { |
400 | perror("not enough memory to create child for code path tree"); | |
401 | return NULL; | |
402 | } | |
403 | new->parent = parent; | |
8cb76d99 | 404 | INIT_LIST_HEAD(&new->val); |
deac911c FW |
405 | |
406 | if (inherit_children) { | |
e369517c NK |
407 | struct rb_node *n; |
408 | struct callchain_node *child; | |
409 | ||
410 | new->rb_root_in = parent->rb_root_in; | |
411 | parent->rb_root_in = RB_ROOT; | |
deac911c | 412 | |
e369517c NK |
413 | n = rb_first(&new->rb_root_in); |
414 | while (n) { | |
415 | child = rb_entry(n, struct callchain_node, rb_node_in); | |
416 | child->parent = new; | |
417 | n = rb_next(n); | |
418 | } | |
deac911c | 419 | |
e369517c NK |
420 | /* make it the first child */ |
421 | rb_link_node(&new->rb_node_in, NULL, &parent->rb_root_in.rb_node); | |
422 | rb_insert_color(&new->rb_node_in, &parent->rb_root_in); | |
deac911c | 423 | } |
8cb76d99 FW |
424 | |
425 | return new; | |
426 | } | |
427 | ||
301fde27 | 428 | |
deac911c FW |
429 | /* |
430 | * Fill the node with callchain values | |
431 | */ | |
8cb76d99 | 432 | static void |
1b3a0e95 | 433 | fill_node(struct callchain_node *node, struct callchain_cursor *cursor) |
8cb76d99 | 434 | { |
1b3a0e95 FW |
435 | struct callchain_cursor_node *cursor_node; |
436 | ||
437 | node->val_nr = cursor->nr - cursor->pos; | |
438 | if (!node->val_nr) | |
439 | pr_warning("Warning: empty node in callchain tree\n"); | |
8cb76d99 | 440 | |
1b3a0e95 FW |
441 | cursor_node = callchain_cursor_current(cursor); |
442 | ||
443 | while (cursor_node) { | |
8cb76d99 FW |
444 | struct callchain_list *call; |
445 | ||
cdd5b75b | 446 | call = zalloc(sizeof(*call)); |
8cb76d99 FW |
447 | if (!call) { |
448 | perror("not enough memory for the code path tree"); | |
449 | return; | |
450 | } | |
1b3a0e95 FW |
451 | call->ip = cursor_node->ip; |
452 | call->ms.sym = cursor_node->sym; | |
453 | call->ms.map = cursor_node->map; | |
8cb76d99 | 454 | list_add_tail(&call->list, &node->val); |
1b3a0e95 FW |
455 | |
456 | callchain_cursor_advance(cursor); | |
457 | cursor_node = callchain_cursor_current(cursor); | |
8cb76d99 | 458 | } |
8cb76d99 FW |
459 | } |
460 | ||
e369517c | 461 | static struct callchain_node * |
1b3a0e95 FW |
462 | add_child(struct callchain_node *parent, |
463 | struct callchain_cursor *cursor, | |
464 | u64 period) | |
8cb76d99 FW |
465 | { |
466 | struct callchain_node *new; | |
467 | ||
deac911c | 468 | new = create_child(parent, false); |
1b3a0e95 | 469 | fill_node(new, cursor); |
8cb76d99 | 470 | |
1953287b | 471 | new->children_hit = 0; |
108553e1 | 472 | new->hit = period; |
e369517c NK |
473 | return new; |
474 | } | |
475 | ||
476 | static s64 match_chain(struct callchain_cursor_node *node, | |
477 | struct callchain_list *cnode) | |
478 | { | |
479 | struct symbol *sym = node->sym; | |
480 | ||
481 | if (cnode->ms.sym && sym && | |
482 | callchain_param.key == CCKEY_FUNCTION) | |
483 | return cnode->ms.sym->start - sym->start; | |
484 | else | |
485 | return cnode->ip - node->ip; | |
8cb76d99 FW |
486 | } |
487 | ||
deac911c FW |
488 | /* |
489 | * Split the parent in two parts (a new child is created) and | |
490 | * give a part of its callchain to the created child. | |
491 | * Then create another child to host the given callchain of new branch | |
492 | */ | |
8cb76d99 | 493 | static void |
1b3a0e95 FW |
494 | split_add_child(struct callchain_node *parent, |
495 | struct callchain_cursor *cursor, | |
496 | struct callchain_list *to_split, | |
497 | u64 idx_parents, u64 idx_local, u64 period) | |
8cb76d99 FW |
498 | { |
499 | struct callchain_node *new; | |
deac911c | 500 | struct list_head *old_tail; |
f37a291c | 501 | unsigned int idx_total = idx_parents + idx_local; |
8cb76d99 FW |
502 | |
503 | /* split */ | |
deac911c FW |
504 | new = create_child(parent, true); |
505 | ||
506 | /* split the callchain and move a part to the new child */ | |
507 | old_tail = parent->val.prev; | |
508 | list_del_range(&to_split->list, old_tail); | |
509 | new->val.next = &to_split->list; | |
510 | new->val.prev = old_tail; | |
511 | to_split->list.prev = &new->val; | |
512 | old_tail->next = &new->val; | |
8cb76d99 | 513 | |
deac911c FW |
514 | /* split the hits */ |
515 | new->hit = parent->hit; | |
1953287b | 516 | new->children_hit = parent->children_hit; |
f08c3154 | 517 | parent->children_hit = callchain_cumul_hits(new); |
deac911c FW |
518 | new->val_nr = parent->val_nr - idx_local; |
519 | parent->val_nr = idx_local; | |
520 | ||
521 | /* create a new child for the new branch if any */ | |
1b3a0e95 | 522 | if (idx_total < cursor->nr) { |
e369517c NK |
523 | struct callchain_node *first; |
524 | struct callchain_list *cnode; | |
525 | struct callchain_cursor_node *node; | |
526 | struct rb_node *p, **pp; | |
527 | ||
deac911c | 528 | parent->hit = 0; |
108553e1 | 529 | parent->children_hit += period; |
e369517c NK |
530 | |
531 | node = callchain_cursor_current(cursor); | |
532 | new = add_child(parent, cursor, period); | |
533 | ||
534 | /* | |
535 | * This is second child since we moved parent's children | |
536 | * to new (first) child above. | |
537 | */ | |
538 | p = parent->rb_root_in.rb_node; | |
539 | first = rb_entry(p, struct callchain_node, rb_node_in); | |
540 | cnode = list_first_entry(&first->val, struct callchain_list, | |
541 | list); | |
542 | ||
543 | if (match_chain(node, cnode) < 0) | |
544 | pp = &p->rb_left; | |
545 | else | |
546 | pp = &p->rb_right; | |
547 | ||
548 | rb_link_node(&new->rb_node_in, p, pp); | |
549 | rb_insert_color(&new->rb_node_in, &parent->rb_root_in); | |
deac911c | 550 | } else { |
108553e1 | 551 | parent->hit = period; |
deac911c | 552 | } |
8cb76d99 FW |
553 | } |
554 | ||
555 | static int | |
1b3a0e95 FW |
556 | append_chain(struct callchain_node *root, |
557 | struct callchain_cursor *cursor, | |
558 | u64 period); | |
8cb76d99 | 559 | |
deac911c | 560 | static void |
1b3a0e95 FW |
561 | append_chain_children(struct callchain_node *root, |
562 | struct callchain_cursor *cursor, | |
563 | u64 period) | |
8cb76d99 FW |
564 | { |
565 | struct callchain_node *rnode; | |
e369517c NK |
566 | struct callchain_cursor_node *node; |
567 | struct rb_node **p = &root->rb_root_in.rb_node; | |
568 | struct rb_node *parent = NULL; | |
569 | ||
570 | node = callchain_cursor_current(cursor); | |
571 | if (!node) | |
572 | return; | |
8cb76d99 FW |
573 | |
574 | /* lookup in childrens */ | |
e369517c NK |
575 | while (*p) { |
576 | s64 ret; | |
f37a291c | 577 | |
e369517c NK |
578 | parent = *p; |
579 | rnode = rb_entry(parent, struct callchain_node, rb_node_in); | |
e369517c | 580 | |
b965bb41 FW |
581 | /* If at least first entry matches, rely to children */ |
582 | ret = append_chain(rnode, cursor, period); | |
583 | if (ret == 0) | |
1953287b | 584 | goto inc_children_hit; |
e369517c NK |
585 | |
586 | if (ret < 0) | |
587 | p = &parent->rb_left; | |
588 | else | |
589 | p = &parent->rb_right; | |
8cb76d99 | 590 | } |
deac911c | 591 | /* nothing in children, add to the current node */ |
e369517c NK |
592 | rnode = add_child(root, cursor, period); |
593 | rb_link_node(&rnode->rb_node_in, parent, p); | |
594 | rb_insert_color(&rnode->rb_node_in, &root->rb_root_in); | |
e05b876c | 595 | |
1953287b | 596 | inc_children_hit: |
108553e1 | 597 | root->children_hit += period; |
8cb76d99 FW |
598 | } |
599 | ||
600 | static int | |
1b3a0e95 FW |
601 | append_chain(struct callchain_node *root, |
602 | struct callchain_cursor *cursor, | |
603 | u64 period) | |
8cb76d99 FW |
604 | { |
605 | struct callchain_list *cnode; | |
1b3a0e95 | 606 | u64 start = cursor->pos; |
8cb76d99 | 607 | bool found = false; |
1b3a0e95 | 608 | u64 matches; |
b965bb41 | 609 | int cmp = 0; |
8cb76d99 | 610 | |
deac911c FW |
611 | /* |
612 | * Lookup in the current node | |
613 | * If we have a symbol, then compare the start to match | |
99571ab3 AK |
614 | * anywhere inside a function, unless function |
615 | * mode is disabled. | |
deac911c | 616 | */ |
8cb76d99 | 617 | list_for_each_entry(cnode, &root->val, list) { |
1b3a0e95 | 618 | struct callchain_cursor_node *node; |
301fde27 | 619 | |
1b3a0e95 FW |
620 | node = callchain_cursor_current(cursor); |
621 | if (!node) | |
deac911c | 622 | break; |
301fde27 | 623 | |
b965bb41 FW |
624 | cmp = match_chain(node, cnode); |
625 | if (cmp) | |
8cb76d99 | 626 | break; |
301fde27 | 627 | |
e369517c | 628 | found = true; |
1b3a0e95 FW |
629 | |
630 | callchain_cursor_advance(cursor); | |
8cb76d99 FW |
631 | } |
632 | ||
e369517c | 633 | /* matches not, relay no the parent */ |
1b3a0e95 | 634 | if (!found) { |
b965bb41 | 635 | WARN_ONCE(!cmp, "Chain comparison error\n"); |
b965bb41 | 636 | return cmp; |
1b3a0e95 FW |
637 | } |
638 | ||
639 | matches = cursor->pos - start; | |
8cb76d99 FW |
640 | |
641 | /* we match only a part of the node. Split it and add the new chain */ | |
1b3a0e95 FW |
642 | if (matches < root->val_nr) { |
643 | split_add_child(root, cursor, cnode, start, matches, period); | |
8cb76d99 FW |
644 | return 0; |
645 | } | |
646 | ||
647 | /* we match 100% of the path, increment the hit */ | |
1b3a0e95 | 648 | if (matches == root->val_nr && cursor->pos == cursor->nr) { |
108553e1 | 649 | root->hit += period; |
8cb76d99 FW |
650 | return 0; |
651 | } | |
652 | ||
deac911c | 653 | /* We match the node and still have a part remaining */ |
1b3a0e95 | 654 | append_chain_children(root, cursor, period); |
deac911c FW |
655 | |
656 | return 0; | |
8cb76d99 FW |
657 | } |
658 | ||
1b3a0e95 FW |
659 | int callchain_append(struct callchain_root *root, |
660 | struct callchain_cursor *cursor, | |
661 | u64 period) | |
8cb76d99 | 662 | { |
1b3a0e95 | 663 | if (!cursor->nr) |
301fde27 FW |
664 | return 0; |
665 | ||
1b3a0e95 | 666 | callchain_cursor_commit(cursor); |
301fde27 | 667 | |
1b3a0e95 | 668 | append_chain_children(&root->node, cursor, period); |
d2009c51 | 669 | |
1b3a0e95 FW |
670 | if (cursor->nr > root->max_depth) |
671 | root->max_depth = cursor->nr; | |
301fde27 FW |
672 | |
673 | return 0; | |
8cb76d99 | 674 | } |
612d4fd7 FW |
675 | |
676 | static int | |
1b3a0e95 FW |
677 | merge_chain_branch(struct callchain_cursor *cursor, |
678 | struct callchain_node *dst, struct callchain_node *src) | |
612d4fd7 | 679 | { |
1b3a0e95 | 680 | struct callchain_cursor_node **old_last = cursor->last; |
e369517c | 681 | struct callchain_node *child; |
612d4fd7 | 682 | struct callchain_list *list, *next_list; |
e369517c | 683 | struct rb_node *n; |
1b3a0e95 | 684 | int old_pos = cursor->nr; |
612d4fd7 FW |
685 | int err = 0; |
686 | ||
687 | list_for_each_entry_safe(list, next_list, &src->val, list) { | |
1b3a0e95 FW |
688 | callchain_cursor_append(cursor, list->ip, |
689 | list->ms.map, list->ms.sym); | |
612d4fd7 FW |
690 | list_del(&list->list); |
691 | free(list); | |
692 | } | |
693 | ||
1b3a0e95 FW |
694 | if (src->hit) { |
695 | callchain_cursor_commit(cursor); | |
696 | append_chain_children(dst, cursor, src->hit); | |
697 | } | |
612d4fd7 | 698 | |
e369517c NK |
699 | n = rb_first(&src->rb_root_in); |
700 | while (n) { | |
701 | child = container_of(n, struct callchain_node, rb_node_in); | |
702 | n = rb_next(n); | |
703 | rb_erase(&child->rb_node_in, &src->rb_root_in); | |
704 | ||
1b3a0e95 | 705 | err = merge_chain_branch(cursor, dst, child); |
612d4fd7 FW |
706 | if (err) |
707 | break; | |
708 | ||
612d4fd7 FW |
709 | free(child); |
710 | } | |
711 | ||
1b3a0e95 FW |
712 | cursor->nr = old_pos; |
713 | cursor->last = old_last; | |
612d4fd7 FW |
714 | |
715 | return err; | |
716 | } | |
717 | ||
1b3a0e95 FW |
718 | int callchain_merge(struct callchain_cursor *cursor, |
719 | struct callchain_root *dst, struct callchain_root *src) | |
720 | { | |
721 | return merge_chain_branch(cursor, &dst->node, &src->node); | |
722 | } | |
723 | ||
724 | int callchain_cursor_append(struct callchain_cursor *cursor, | |
725 | u64 ip, struct map *map, struct symbol *sym) | |
612d4fd7 | 726 | { |
1b3a0e95 | 727 | struct callchain_cursor_node *node = *cursor->last; |
612d4fd7 | 728 | |
1b3a0e95 | 729 | if (!node) { |
91b98804 | 730 | node = calloc(1, sizeof(*node)); |
1b3a0e95 FW |
731 | if (!node) |
732 | return -ENOMEM; | |
612d4fd7 | 733 | |
1b3a0e95 FW |
734 | *cursor->last = node; |
735 | } | |
612d4fd7 | 736 | |
1b3a0e95 FW |
737 | node->ip = ip; |
738 | node->map = map; | |
739 | node->sym = sym; | |
612d4fd7 | 740 | |
1b3a0e95 | 741 | cursor->nr++; |
612d4fd7 | 742 | |
1b3a0e95 FW |
743 | cursor->last = &node->next; |
744 | ||
745 | return 0; | |
612d4fd7 | 746 | } |
2dc9fb1a NK |
747 | |
748 | int sample__resolve_callchain(struct perf_sample *sample, struct symbol **parent, | |
749 | struct perf_evsel *evsel, struct addr_location *al, | |
750 | int max_stack) | |
751 | { | |
752 | if (sample->callchain == NULL) | |
753 | return 0; | |
754 | ||
7a13aa28 NK |
755 | if (symbol_conf.use_callchain || symbol_conf.cumulate_callchain || |
756 | sort__has_parent) { | |
2dc9fb1a NK |
757 | return machine__resolve_callchain(al->machine, evsel, al->thread, |
758 | sample, parent, al, max_stack); | |
759 | } | |
760 | return 0; | |
761 | } | |
762 | ||
763 | int hist_entry__append_callchain(struct hist_entry *he, struct perf_sample *sample) | |
764 | { | |
4d40b051 | 765 | if (!symbol_conf.use_callchain || sample->callchain == NULL) |
2dc9fb1a NK |
766 | return 0; |
767 | return callchain_append(he->callchain, &callchain_cursor, sample->period); | |
768 | } | |
c7405d85 NK |
769 | |
770 | int fill_callchain_info(struct addr_location *al, struct callchain_cursor_node *node, | |
771 | bool hide_unresolved) | |
772 | { | |
773 | al->map = node->map; | |
774 | al->sym = node->sym; | |
775 | if (node->map) | |
776 | al->addr = node->map->map_ip(node->map, node->ip); | |
777 | else | |
778 | al->addr = node->ip; | |
779 | ||
780 | if (al->sym == NULL) { | |
781 | if (hide_unresolved) | |
782 | return 0; | |
783 | if (al->map == NULL) | |
784 | goto out; | |
785 | } | |
786 | ||
787 | if (al->map->groups == &al->machine->kmaps) { | |
788 | if (machine__is_host(al->machine)) { | |
789 | al->cpumode = PERF_RECORD_MISC_KERNEL; | |
790 | al->level = 'k'; | |
791 | } else { | |
792 | al->cpumode = PERF_RECORD_MISC_GUEST_KERNEL; | |
793 | al->level = 'g'; | |
794 | } | |
795 | } else { | |
796 | if (machine__is_host(al->machine)) { | |
797 | al->cpumode = PERF_RECORD_MISC_USER; | |
798 | al->level = '.'; | |
799 | } else if (perf_guest) { | |
800 | al->cpumode = PERF_RECORD_MISC_GUEST_USER; | |
801 | al->level = 'u'; | |
802 | } else { | |
803 | al->cpumode = PERF_RECORD_MISC_HYPERVISOR; | |
804 | al->level = 'H'; | |
805 | } | |
806 | } | |
807 | ||
808 | out: | |
809 | return 1; | |
810 | } |