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 | ||
cff6bb46 DZ |
112 | int |
113 | parse_callchain_report_opt(const char *arg) | |
114 | { | |
e8232f1a | 115 | char *tok; |
cff6bb46 | 116 | char *endptr; |
e8232f1a | 117 | bool minpcnt_set = false; |
cff6bb46 DZ |
118 | |
119 | symbol_conf.use_callchain = true; | |
120 | ||
121 | if (!arg) | |
122 | return 0; | |
123 | ||
e8232f1a NK |
124 | while ((tok = strtok((char *)arg, ",")) != NULL) { |
125 | if (!strncmp(tok, "none", strlen(tok))) { | |
126 | callchain_param.mode = CHAIN_NONE; | |
127 | symbol_conf.use_callchain = false; | |
128 | return 0; | |
129 | } | |
130 | ||
131 | /* try to get the output mode */ | |
132 | if (!strncmp(tok, "graph", strlen(tok))) | |
133 | callchain_param.mode = CHAIN_GRAPH_ABS; | |
134 | else if (!strncmp(tok, "flat", strlen(tok))) | |
135 | callchain_param.mode = CHAIN_FLAT; | |
136 | else if (!strncmp(tok, "fractal", strlen(tok))) | |
137 | callchain_param.mode = CHAIN_GRAPH_REL; | |
138 | /* try to get the call chain order */ | |
139 | else if (!strncmp(tok, "caller", strlen(tok))) | |
140 | callchain_param.order = ORDER_CALLER; | |
141 | else if (!strncmp(tok, "callee", strlen(tok))) | |
142 | callchain_param.order = ORDER_CALLEE; | |
143 | /* try to get the sort key */ | |
144 | else if (!strncmp(tok, "function", strlen(tok))) | |
145 | callchain_param.key = CCKEY_FUNCTION; | |
146 | else if (!strncmp(tok, "address", strlen(tok))) | |
147 | callchain_param.key = CCKEY_ADDRESS; | |
148 | /* try to get the min percent */ | |
149 | else if (!minpcnt_set) { | |
150 | callchain_param.min_percent = strtod(tok, &endptr); | |
151 | if (tok == endptr) | |
152 | return -1; | |
153 | minpcnt_set = true; | |
154 | } else { | |
155 | /* try print limit at last */ | |
156 | callchain_param.print_limit = strtoul(tok, &endptr, 0); | |
157 | if (tok == endptr) | |
158 | return -1; | |
159 | } | |
160 | ||
161 | arg = NULL; | |
cff6bb46 DZ |
162 | } |
163 | ||
cff6bb46 DZ |
164 | if (callchain_register_param(&callchain_param) < 0) { |
165 | pr_err("Can't register callchain params\n"); | |
166 | return -1; | |
167 | } | |
168 | return 0; | |
169 | } | |
170 | ||
deac911c | 171 | static void |
4eb3e478 FW |
172 | rb_insert_callchain(struct rb_root *root, struct callchain_node *chain, |
173 | enum chain_mode mode) | |
8cb76d99 FW |
174 | { |
175 | struct rb_node **p = &root->rb_node; | |
176 | struct rb_node *parent = NULL; | |
177 | struct callchain_node *rnode; | |
f08c3154 | 178 | u64 chain_cumul = callchain_cumul_hits(chain); |
8cb76d99 FW |
179 | |
180 | while (*p) { | |
1953287b FW |
181 | u64 rnode_cumul; |
182 | ||
8cb76d99 FW |
183 | parent = *p; |
184 | rnode = rb_entry(parent, struct callchain_node, rb_node); | |
f08c3154 | 185 | rnode_cumul = callchain_cumul_hits(rnode); |
8cb76d99 | 186 | |
4eb3e478 | 187 | switch (mode) { |
805d127d | 188 | case CHAIN_FLAT: |
4eb3e478 FW |
189 | if (rnode->hit < chain->hit) |
190 | p = &(*p)->rb_left; | |
191 | else | |
192 | p = &(*p)->rb_right; | |
193 | break; | |
805d127d FW |
194 | case CHAIN_GRAPH_ABS: /* Falldown */ |
195 | case CHAIN_GRAPH_REL: | |
1953287b | 196 | if (rnode_cumul < chain_cumul) |
4eb3e478 FW |
197 | p = &(*p)->rb_left; |
198 | else | |
199 | p = &(*p)->rb_right; | |
200 | break; | |
83a0944f | 201 | case CHAIN_NONE: |
4eb3e478 FW |
202 | default: |
203 | break; | |
204 | } | |
8cb76d99 FW |
205 | } |
206 | ||
207 | rb_link_node(&chain->rb_node, parent, p); | |
208 | rb_insert_color(&chain->rb_node, root); | |
209 | } | |
210 | ||
805d127d FW |
211 | static void |
212 | __sort_chain_flat(struct rb_root *rb_root, struct callchain_node *node, | |
213 | u64 min_hit) | |
214 | { | |
e369517c | 215 | struct rb_node *n; |
805d127d FW |
216 | struct callchain_node *child; |
217 | ||
e369517c NK |
218 | n = rb_first(&node->rb_root_in); |
219 | while (n) { | |
220 | child = rb_entry(n, struct callchain_node, rb_node_in); | |
221 | n = rb_next(n); | |
222 | ||
805d127d | 223 | __sort_chain_flat(rb_root, child, min_hit); |
e369517c | 224 | } |
805d127d FW |
225 | |
226 | if (node->hit && node->hit >= min_hit) | |
227 | rb_insert_callchain(rb_root, node, CHAIN_FLAT); | |
228 | } | |
229 | ||
8cb76d99 FW |
230 | /* |
231 | * Once we get every callchains from the stream, we can now | |
232 | * sort them by hit | |
233 | */ | |
805d127d | 234 | static void |
d2009c51 | 235 | sort_chain_flat(struct rb_root *rb_root, struct callchain_root *root, |
1d037ca1 | 236 | u64 min_hit, struct callchain_param *param __maybe_unused) |
805d127d | 237 | { |
d2009c51 | 238 | __sort_chain_flat(rb_root, &root->node, min_hit); |
805d127d FW |
239 | } |
240 | ||
241 | static void __sort_chain_graph_abs(struct callchain_node *node, | |
242 | u64 min_hit) | |
8cb76d99 | 243 | { |
e369517c | 244 | struct rb_node *n; |
8cb76d99 FW |
245 | struct callchain_node *child; |
246 | ||
805d127d | 247 | node->rb_root = RB_ROOT; |
e369517c NK |
248 | n = rb_first(&node->rb_root_in); |
249 | ||
250 | while (n) { | |
251 | child = rb_entry(n, struct callchain_node, rb_node_in); | |
252 | n = rb_next(n); | |
8cb76d99 | 253 | |
805d127d | 254 | __sort_chain_graph_abs(child, min_hit); |
f08c3154 | 255 | if (callchain_cumul_hits(child) >= min_hit) |
805d127d FW |
256 | rb_insert_callchain(&node->rb_root, child, |
257 | CHAIN_GRAPH_ABS); | |
258 | } | |
259 | } | |
260 | ||
261 | static void | |
d2009c51 | 262 | sort_chain_graph_abs(struct rb_root *rb_root, struct callchain_root *chain_root, |
1d037ca1 | 263 | u64 min_hit, struct callchain_param *param __maybe_unused) |
805d127d | 264 | { |
d2009c51 FW |
265 | __sort_chain_graph_abs(&chain_root->node, min_hit); |
266 | rb_root->rb_node = chain_root->node.rb_root.rb_node; | |
4eb3e478 FW |
267 | } |
268 | ||
805d127d FW |
269 | static void __sort_chain_graph_rel(struct callchain_node *node, |
270 | double min_percent) | |
4eb3e478 | 271 | { |
e369517c | 272 | struct rb_node *n; |
4eb3e478 | 273 | struct callchain_node *child; |
805d127d | 274 | u64 min_hit; |
4eb3e478 FW |
275 | |
276 | node->rb_root = RB_ROOT; | |
c0a8865e | 277 | min_hit = ceil(node->children_hit * min_percent); |
4eb3e478 | 278 | |
e369517c NK |
279 | n = rb_first(&node->rb_root_in); |
280 | while (n) { | |
281 | child = rb_entry(n, struct callchain_node, rb_node_in); | |
282 | n = rb_next(n); | |
283 | ||
805d127d | 284 | __sort_chain_graph_rel(child, min_percent); |
f08c3154 | 285 | if (callchain_cumul_hits(child) >= min_hit) |
805d127d FW |
286 | rb_insert_callchain(&node->rb_root, child, |
287 | CHAIN_GRAPH_REL); | |
4eb3e478 FW |
288 | } |
289 | } | |
290 | ||
805d127d | 291 | static void |
d2009c51 | 292 | sort_chain_graph_rel(struct rb_root *rb_root, struct callchain_root *chain_root, |
1d037ca1 | 293 | u64 min_hit __maybe_unused, struct callchain_param *param) |
4eb3e478 | 294 | { |
d2009c51 FW |
295 | __sort_chain_graph_rel(&chain_root->node, param->min_percent / 100.0); |
296 | rb_root->rb_node = chain_root->node.rb_root.rb_node; | |
8cb76d99 FW |
297 | } |
298 | ||
16537f13 | 299 | int callchain_register_param(struct callchain_param *param) |
805d127d FW |
300 | { |
301 | switch (param->mode) { | |
302 | case CHAIN_GRAPH_ABS: | |
303 | param->sort = sort_chain_graph_abs; | |
304 | break; | |
305 | case CHAIN_GRAPH_REL: | |
306 | param->sort = sort_chain_graph_rel; | |
307 | break; | |
308 | case CHAIN_FLAT: | |
309 | param->sort = sort_chain_flat; | |
310 | break; | |
83a0944f | 311 | case CHAIN_NONE: |
805d127d FW |
312 | default: |
313 | return -1; | |
314 | } | |
315 | return 0; | |
316 | } | |
317 | ||
deac911c FW |
318 | /* |
319 | * Create a child for a parent. If inherit_children, then the new child | |
320 | * will become the new parent of it's parent children | |
321 | */ | |
322 | static struct callchain_node * | |
323 | create_child(struct callchain_node *parent, bool inherit_children) | |
8cb76d99 FW |
324 | { |
325 | struct callchain_node *new; | |
326 | ||
cdd5b75b | 327 | new = zalloc(sizeof(*new)); |
8cb76d99 FW |
328 | if (!new) { |
329 | perror("not enough memory to create child for code path tree"); | |
330 | return NULL; | |
331 | } | |
332 | new->parent = parent; | |
8cb76d99 | 333 | INIT_LIST_HEAD(&new->val); |
deac911c FW |
334 | |
335 | if (inherit_children) { | |
e369517c NK |
336 | struct rb_node *n; |
337 | struct callchain_node *child; | |
338 | ||
339 | new->rb_root_in = parent->rb_root_in; | |
340 | parent->rb_root_in = RB_ROOT; | |
deac911c | 341 | |
e369517c NK |
342 | n = rb_first(&new->rb_root_in); |
343 | while (n) { | |
344 | child = rb_entry(n, struct callchain_node, rb_node_in); | |
345 | child->parent = new; | |
346 | n = rb_next(n); | |
347 | } | |
deac911c | 348 | |
e369517c NK |
349 | /* make it the first child */ |
350 | rb_link_node(&new->rb_node_in, NULL, &parent->rb_root_in.rb_node); | |
351 | rb_insert_color(&new->rb_node_in, &parent->rb_root_in); | |
deac911c | 352 | } |
8cb76d99 FW |
353 | |
354 | return new; | |
355 | } | |
356 | ||
301fde27 | 357 | |
deac911c FW |
358 | /* |
359 | * Fill the node with callchain values | |
360 | */ | |
8cb76d99 | 361 | static void |
1b3a0e95 | 362 | fill_node(struct callchain_node *node, struct callchain_cursor *cursor) |
8cb76d99 | 363 | { |
1b3a0e95 FW |
364 | struct callchain_cursor_node *cursor_node; |
365 | ||
366 | node->val_nr = cursor->nr - cursor->pos; | |
367 | if (!node->val_nr) | |
368 | pr_warning("Warning: empty node in callchain tree\n"); | |
8cb76d99 | 369 | |
1b3a0e95 FW |
370 | cursor_node = callchain_cursor_current(cursor); |
371 | ||
372 | while (cursor_node) { | |
8cb76d99 FW |
373 | struct callchain_list *call; |
374 | ||
cdd5b75b | 375 | call = zalloc(sizeof(*call)); |
8cb76d99 FW |
376 | if (!call) { |
377 | perror("not enough memory for the code path tree"); | |
378 | return; | |
379 | } | |
1b3a0e95 FW |
380 | call->ip = cursor_node->ip; |
381 | call->ms.sym = cursor_node->sym; | |
382 | call->ms.map = cursor_node->map; | |
8cb76d99 | 383 | list_add_tail(&call->list, &node->val); |
1b3a0e95 FW |
384 | |
385 | callchain_cursor_advance(cursor); | |
386 | cursor_node = callchain_cursor_current(cursor); | |
8cb76d99 | 387 | } |
8cb76d99 FW |
388 | } |
389 | ||
e369517c | 390 | static struct callchain_node * |
1b3a0e95 FW |
391 | add_child(struct callchain_node *parent, |
392 | struct callchain_cursor *cursor, | |
393 | u64 period) | |
8cb76d99 FW |
394 | { |
395 | struct callchain_node *new; | |
396 | ||
deac911c | 397 | new = create_child(parent, false); |
1b3a0e95 | 398 | fill_node(new, cursor); |
8cb76d99 | 399 | |
1953287b | 400 | new->children_hit = 0; |
108553e1 | 401 | new->hit = period; |
e369517c NK |
402 | return new; |
403 | } | |
404 | ||
405 | static s64 match_chain(struct callchain_cursor_node *node, | |
406 | struct callchain_list *cnode) | |
407 | { | |
408 | struct symbol *sym = node->sym; | |
409 | ||
410 | if (cnode->ms.sym && sym && | |
411 | callchain_param.key == CCKEY_FUNCTION) | |
412 | return cnode->ms.sym->start - sym->start; | |
413 | else | |
414 | return cnode->ip - node->ip; | |
8cb76d99 FW |
415 | } |
416 | ||
deac911c FW |
417 | /* |
418 | * Split the parent in two parts (a new child is created) and | |
419 | * give a part of its callchain to the created child. | |
420 | * Then create another child to host the given callchain of new branch | |
421 | */ | |
8cb76d99 | 422 | static void |
1b3a0e95 FW |
423 | split_add_child(struct callchain_node *parent, |
424 | struct callchain_cursor *cursor, | |
425 | struct callchain_list *to_split, | |
426 | u64 idx_parents, u64 idx_local, u64 period) | |
8cb76d99 FW |
427 | { |
428 | struct callchain_node *new; | |
deac911c | 429 | struct list_head *old_tail; |
f37a291c | 430 | unsigned int idx_total = idx_parents + idx_local; |
8cb76d99 FW |
431 | |
432 | /* split */ | |
deac911c FW |
433 | new = create_child(parent, true); |
434 | ||
435 | /* split the callchain and move a part to the new child */ | |
436 | old_tail = parent->val.prev; | |
437 | list_del_range(&to_split->list, old_tail); | |
438 | new->val.next = &to_split->list; | |
439 | new->val.prev = old_tail; | |
440 | to_split->list.prev = &new->val; | |
441 | old_tail->next = &new->val; | |
8cb76d99 | 442 | |
deac911c FW |
443 | /* split the hits */ |
444 | new->hit = parent->hit; | |
1953287b | 445 | new->children_hit = parent->children_hit; |
f08c3154 | 446 | parent->children_hit = callchain_cumul_hits(new); |
deac911c FW |
447 | new->val_nr = parent->val_nr - idx_local; |
448 | parent->val_nr = idx_local; | |
449 | ||
450 | /* create a new child for the new branch if any */ | |
1b3a0e95 | 451 | if (idx_total < cursor->nr) { |
e369517c NK |
452 | struct callchain_node *first; |
453 | struct callchain_list *cnode; | |
454 | struct callchain_cursor_node *node; | |
455 | struct rb_node *p, **pp; | |
456 | ||
deac911c | 457 | parent->hit = 0; |
108553e1 | 458 | parent->children_hit += period; |
e369517c NK |
459 | |
460 | node = callchain_cursor_current(cursor); | |
461 | new = add_child(parent, cursor, period); | |
462 | ||
463 | /* | |
464 | * This is second child since we moved parent's children | |
465 | * to new (first) child above. | |
466 | */ | |
467 | p = parent->rb_root_in.rb_node; | |
468 | first = rb_entry(p, struct callchain_node, rb_node_in); | |
469 | cnode = list_first_entry(&first->val, struct callchain_list, | |
470 | list); | |
471 | ||
472 | if (match_chain(node, cnode) < 0) | |
473 | pp = &p->rb_left; | |
474 | else | |
475 | pp = &p->rb_right; | |
476 | ||
477 | rb_link_node(&new->rb_node_in, p, pp); | |
478 | rb_insert_color(&new->rb_node_in, &parent->rb_root_in); | |
deac911c | 479 | } else { |
108553e1 | 480 | parent->hit = period; |
deac911c | 481 | } |
8cb76d99 FW |
482 | } |
483 | ||
484 | static int | |
1b3a0e95 FW |
485 | append_chain(struct callchain_node *root, |
486 | struct callchain_cursor *cursor, | |
487 | u64 period); | |
8cb76d99 | 488 | |
deac911c | 489 | static void |
1b3a0e95 FW |
490 | append_chain_children(struct callchain_node *root, |
491 | struct callchain_cursor *cursor, | |
492 | u64 period) | |
8cb76d99 FW |
493 | { |
494 | struct callchain_node *rnode; | |
e369517c NK |
495 | struct callchain_cursor_node *node; |
496 | struct rb_node **p = &root->rb_root_in.rb_node; | |
497 | struct rb_node *parent = NULL; | |
498 | ||
499 | node = callchain_cursor_current(cursor); | |
500 | if (!node) | |
501 | return; | |
8cb76d99 FW |
502 | |
503 | /* lookup in childrens */ | |
e369517c NK |
504 | while (*p) { |
505 | s64 ret; | |
f37a291c | 506 | |
e369517c NK |
507 | parent = *p; |
508 | rnode = rb_entry(parent, struct callchain_node, rb_node_in); | |
e369517c | 509 | |
b965bb41 FW |
510 | /* If at least first entry matches, rely to children */ |
511 | ret = append_chain(rnode, cursor, period); | |
512 | if (ret == 0) | |
1953287b | 513 | goto inc_children_hit; |
e369517c NK |
514 | |
515 | if (ret < 0) | |
516 | p = &parent->rb_left; | |
517 | else | |
518 | p = &parent->rb_right; | |
8cb76d99 | 519 | } |
deac911c | 520 | /* nothing in children, add to the current node */ |
e369517c NK |
521 | rnode = add_child(root, cursor, period); |
522 | rb_link_node(&rnode->rb_node_in, parent, p); | |
523 | rb_insert_color(&rnode->rb_node_in, &root->rb_root_in); | |
e05b876c | 524 | |
1953287b | 525 | inc_children_hit: |
108553e1 | 526 | root->children_hit += period; |
8cb76d99 FW |
527 | } |
528 | ||
529 | static int | |
1b3a0e95 FW |
530 | append_chain(struct callchain_node *root, |
531 | struct callchain_cursor *cursor, | |
532 | u64 period) | |
8cb76d99 FW |
533 | { |
534 | struct callchain_list *cnode; | |
1b3a0e95 | 535 | u64 start = cursor->pos; |
8cb76d99 | 536 | bool found = false; |
1b3a0e95 | 537 | u64 matches; |
b965bb41 | 538 | int cmp = 0; |
8cb76d99 | 539 | |
deac911c FW |
540 | /* |
541 | * Lookup in the current node | |
542 | * If we have a symbol, then compare the start to match | |
99571ab3 AK |
543 | * anywhere inside a function, unless function |
544 | * mode is disabled. | |
deac911c | 545 | */ |
8cb76d99 | 546 | list_for_each_entry(cnode, &root->val, list) { |
1b3a0e95 | 547 | struct callchain_cursor_node *node; |
301fde27 | 548 | |
1b3a0e95 FW |
549 | node = callchain_cursor_current(cursor); |
550 | if (!node) | |
deac911c | 551 | break; |
301fde27 | 552 | |
b965bb41 FW |
553 | cmp = match_chain(node, cnode); |
554 | if (cmp) | |
8cb76d99 | 555 | break; |
301fde27 | 556 | |
e369517c | 557 | found = true; |
1b3a0e95 FW |
558 | |
559 | callchain_cursor_advance(cursor); | |
8cb76d99 FW |
560 | } |
561 | ||
e369517c | 562 | /* matches not, relay no the parent */ |
1b3a0e95 | 563 | if (!found) { |
b965bb41 | 564 | WARN_ONCE(!cmp, "Chain comparison error\n"); |
b965bb41 | 565 | return cmp; |
1b3a0e95 FW |
566 | } |
567 | ||
568 | matches = cursor->pos - start; | |
8cb76d99 FW |
569 | |
570 | /* we match only a part of the node. Split it and add the new chain */ | |
1b3a0e95 FW |
571 | if (matches < root->val_nr) { |
572 | split_add_child(root, cursor, cnode, start, matches, period); | |
8cb76d99 FW |
573 | return 0; |
574 | } | |
575 | ||
576 | /* we match 100% of the path, increment the hit */ | |
1b3a0e95 | 577 | if (matches == root->val_nr && cursor->pos == cursor->nr) { |
108553e1 | 578 | root->hit += period; |
8cb76d99 FW |
579 | return 0; |
580 | } | |
581 | ||
deac911c | 582 | /* We match the node and still have a part remaining */ |
1b3a0e95 | 583 | append_chain_children(root, cursor, period); |
deac911c FW |
584 | |
585 | return 0; | |
8cb76d99 FW |
586 | } |
587 | ||
1b3a0e95 FW |
588 | int callchain_append(struct callchain_root *root, |
589 | struct callchain_cursor *cursor, | |
590 | u64 period) | |
8cb76d99 | 591 | { |
1b3a0e95 | 592 | if (!cursor->nr) |
301fde27 FW |
593 | return 0; |
594 | ||
1b3a0e95 | 595 | callchain_cursor_commit(cursor); |
301fde27 | 596 | |
1b3a0e95 | 597 | append_chain_children(&root->node, cursor, period); |
d2009c51 | 598 | |
1b3a0e95 FW |
599 | if (cursor->nr > root->max_depth) |
600 | root->max_depth = cursor->nr; | |
301fde27 FW |
601 | |
602 | return 0; | |
8cb76d99 | 603 | } |
612d4fd7 FW |
604 | |
605 | static int | |
1b3a0e95 FW |
606 | merge_chain_branch(struct callchain_cursor *cursor, |
607 | struct callchain_node *dst, struct callchain_node *src) | |
612d4fd7 | 608 | { |
1b3a0e95 | 609 | struct callchain_cursor_node **old_last = cursor->last; |
e369517c | 610 | struct callchain_node *child; |
612d4fd7 | 611 | struct callchain_list *list, *next_list; |
e369517c | 612 | struct rb_node *n; |
1b3a0e95 | 613 | int old_pos = cursor->nr; |
612d4fd7 FW |
614 | int err = 0; |
615 | ||
616 | list_for_each_entry_safe(list, next_list, &src->val, list) { | |
1b3a0e95 FW |
617 | callchain_cursor_append(cursor, list->ip, |
618 | list->ms.map, list->ms.sym); | |
612d4fd7 FW |
619 | list_del(&list->list); |
620 | free(list); | |
621 | } | |
622 | ||
1b3a0e95 FW |
623 | if (src->hit) { |
624 | callchain_cursor_commit(cursor); | |
625 | append_chain_children(dst, cursor, src->hit); | |
626 | } | |
612d4fd7 | 627 | |
e369517c NK |
628 | n = rb_first(&src->rb_root_in); |
629 | while (n) { | |
630 | child = container_of(n, struct callchain_node, rb_node_in); | |
631 | n = rb_next(n); | |
632 | rb_erase(&child->rb_node_in, &src->rb_root_in); | |
633 | ||
1b3a0e95 | 634 | err = merge_chain_branch(cursor, dst, child); |
612d4fd7 FW |
635 | if (err) |
636 | break; | |
637 | ||
612d4fd7 FW |
638 | free(child); |
639 | } | |
640 | ||
1b3a0e95 FW |
641 | cursor->nr = old_pos; |
642 | cursor->last = old_last; | |
612d4fd7 FW |
643 | |
644 | return err; | |
645 | } | |
646 | ||
1b3a0e95 FW |
647 | int callchain_merge(struct callchain_cursor *cursor, |
648 | struct callchain_root *dst, struct callchain_root *src) | |
649 | { | |
650 | return merge_chain_branch(cursor, &dst->node, &src->node); | |
651 | } | |
652 | ||
653 | int callchain_cursor_append(struct callchain_cursor *cursor, | |
654 | u64 ip, struct map *map, struct symbol *sym) | |
612d4fd7 | 655 | { |
1b3a0e95 | 656 | struct callchain_cursor_node *node = *cursor->last; |
612d4fd7 | 657 | |
1b3a0e95 | 658 | if (!node) { |
91b98804 | 659 | node = calloc(1, sizeof(*node)); |
1b3a0e95 FW |
660 | if (!node) |
661 | return -ENOMEM; | |
612d4fd7 | 662 | |
1b3a0e95 FW |
663 | *cursor->last = node; |
664 | } | |
612d4fd7 | 665 | |
1b3a0e95 FW |
666 | node->ip = ip; |
667 | node->map = map; | |
668 | node->sym = sym; | |
612d4fd7 | 669 | |
1b3a0e95 | 670 | cursor->nr++; |
612d4fd7 | 671 | |
1b3a0e95 FW |
672 | cursor->last = &node->next; |
673 | ||
674 | return 0; | |
612d4fd7 | 675 | } |
2dc9fb1a NK |
676 | |
677 | int sample__resolve_callchain(struct perf_sample *sample, struct symbol **parent, | |
678 | struct perf_evsel *evsel, struct addr_location *al, | |
679 | int max_stack) | |
680 | { | |
681 | if (sample->callchain == NULL) | |
682 | return 0; | |
683 | ||
7a13aa28 NK |
684 | if (symbol_conf.use_callchain || symbol_conf.cumulate_callchain || |
685 | sort__has_parent) { | |
2dc9fb1a NK |
686 | return machine__resolve_callchain(al->machine, evsel, al->thread, |
687 | sample, parent, al, max_stack); | |
688 | } | |
689 | return 0; | |
690 | } | |
691 | ||
692 | int hist_entry__append_callchain(struct hist_entry *he, struct perf_sample *sample) | |
693 | { | |
4d40b051 | 694 | if (!symbol_conf.use_callchain || sample->callchain == NULL) |
2dc9fb1a NK |
695 | return 0; |
696 | return callchain_append(he->callchain, &callchain_cursor, sample->period); | |
697 | } | |
c7405d85 NK |
698 | |
699 | int fill_callchain_info(struct addr_location *al, struct callchain_cursor_node *node, | |
700 | bool hide_unresolved) | |
701 | { | |
702 | al->map = node->map; | |
703 | al->sym = node->sym; | |
704 | if (node->map) | |
705 | al->addr = node->map->map_ip(node->map, node->ip); | |
706 | else | |
707 | al->addr = node->ip; | |
708 | ||
709 | if (al->sym == NULL) { | |
710 | if (hide_unresolved) | |
711 | return 0; | |
712 | if (al->map == NULL) | |
713 | goto out; | |
714 | } | |
715 | ||
716 | if (al->map->groups == &al->machine->kmaps) { | |
717 | if (machine__is_host(al->machine)) { | |
718 | al->cpumode = PERF_RECORD_MISC_KERNEL; | |
719 | al->level = 'k'; | |
720 | } else { | |
721 | al->cpumode = PERF_RECORD_MISC_GUEST_KERNEL; | |
722 | al->level = 'g'; | |
723 | } | |
724 | } else { | |
725 | if (machine__is_host(al->machine)) { | |
726 | al->cpumode = PERF_RECORD_MISC_USER; | |
727 | al->level = '.'; | |
728 | } else if (perf_guest) { | |
729 | al->cpumode = PERF_RECORD_MISC_GUEST_USER; | |
730 | al->level = 'u'; | |
731 | } else { | |
732 | al->cpumode = PERF_RECORD_MISC_HYPERVISOR; | |
733 | al->level = 'H'; | |
734 | } | |
735 | } | |
736 | ||
737 | out: | |
738 | return 1; | |
739 | } |