Loading...
1/*
2 * Copyright (C) 2009-2011, Frederic Weisbecker <fweisbec@gmail.com>
3 *
4 * Handle the callchains from the stream in an ad-hoc radix tree and then
5 * sort them in an rbtree.
6 *
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 *
10 */
11
12#include <stdlib.h>
13#include <stdio.h>
14#include <stdbool.h>
15#include <errno.h>
16#include <math.h>
17
18#include "asm/bug.h"
19
20#include "hist.h"
21#include "util.h"
22#include "sort.h"
23#include "machine.h"
24#include "callchain.h"
25
26__thread struct callchain_cursor callchain_cursor;
27
28int parse_callchain_record_opt(const char *arg, struct callchain_param *param)
29{
30 return parse_callchain_record(arg, param);
31}
32
33static int parse_callchain_mode(const char *value)
34{
35 if (!strncmp(value, "graph", strlen(value))) {
36 callchain_param.mode = CHAIN_GRAPH_ABS;
37 return 0;
38 }
39 if (!strncmp(value, "flat", strlen(value))) {
40 callchain_param.mode = CHAIN_FLAT;
41 return 0;
42 }
43 if (!strncmp(value, "fractal", strlen(value))) {
44 callchain_param.mode = CHAIN_GRAPH_REL;
45 return 0;
46 }
47 if (!strncmp(value, "folded", strlen(value))) {
48 callchain_param.mode = CHAIN_FOLDED;
49 return 0;
50 }
51 return -1;
52}
53
54static int parse_callchain_order(const char *value)
55{
56 if (!strncmp(value, "caller", strlen(value))) {
57 callchain_param.order = ORDER_CALLER;
58 callchain_param.order_set = true;
59 return 0;
60 }
61 if (!strncmp(value, "callee", strlen(value))) {
62 callchain_param.order = ORDER_CALLEE;
63 callchain_param.order_set = true;
64 return 0;
65 }
66 return -1;
67}
68
69static int parse_callchain_sort_key(const char *value)
70{
71 if (!strncmp(value, "function", strlen(value))) {
72 callchain_param.key = CCKEY_FUNCTION;
73 return 0;
74 }
75 if (!strncmp(value, "address", strlen(value))) {
76 callchain_param.key = CCKEY_ADDRESS;
77 return 0;
78 }
79 if (!strncmp(value, "branch", strlen(value))) {
80 callchain_param.branch_callstack = 1;
81 return 0;
82 }
83 return -1;
84}
85
86static int parse_callchain_value(const char *value)
87{
88 if (!strncmp(value, "percent", strlen(value))) {
89 callchain_param.value = CCVAL_PERCENT;
90 return 0;
91 }
92 if (!strncmp(value, "period", strlen(value))) {
93 callchain_param.value = CCVAL_PERIOD;
94 return 0;
95 }
96 if (!strncmp(value, "count", strlen(value))) {
97 callchain_param.value = CCVAL_COUNT;
98 return 0;
99 }
100 return -1;
101}
102
103static int
104__parse_callchain_report_opt(const char *arg, bool allow_record_opt)
105{
106 char *tok;
107 char *endptr;
108 bool minpcnt_set = false;
109 bool record_opt_set = false;
110 bool try_stack_size = false;
111
112 symbol_conf.use_callchain = true;
113
114 if (!arg)
115 return 0;
116
117 while ((tok = strtok((char *)arg, ",")) != NULL) {
118 if (!strncmp(tok, "none", strlen(tok))) {
119 callchain_param.mode = CHAIN_NONE;
120 symbol_conf.use_callchain = false;
121 return 0;
122 }
123
124 if (!parse_callchain_mode(tok) ||
125 !parse_callchain_order(tok) ||
126 !parse_callchain_sort_key(tok) ||
127 !parse_callchain_value(tok)) {
128 /* parsing ok - move on to the next */
129 try_stack_size = false;
130 goto next;
131 } else if (allow_record_opt && !record_opt_set) {
132 if (parse_callchain_record(tok, &callchain_param))
133 goto try_numbers;
134
135 /* assume that number followed by 'dwarf' is stack size */
136 if (callchain_param.record_mode == CALLCHAIN_DWARF)
137 try_stack_size = true;
138
139 record_opt_set = true;
140 goto next;
141 }
142
143try_numbers:
144 if (try_stack_size) {
145 unsigned long size = 0;
146
147 if (get_stack_size(tok, &size) < 0)
148 return -1;
149 callchain_param.dump_size = size;
150 try_stack_size = false;
151 } else if (!minpcnt_set) {
152 /* try to get the min percent */
153 callchain_param.min_percent = strtod(tok, &endptr);
154 if (tok == endptr)
155 return -1;
156 minpcnt_set = true;
157 } else {
158 /* try print limit at last */
159 callchain_param.print_limit = strtoul(tok, &endptr, 0);
160 if (tok == endptr)
161 return -1;
162 }
163next:
164 arg = NULL;
165 }
166
167 if (callchain_register_param(&callchain_param) < 0) {
168 pr_err("Can't register callchain params\n");
169 return -1;
170 }
171 return 0;
172}
173
174int parse_callchain_report_opt(const char *arg)
175{
176 return __parse_callchain_report_opt(arg, false);
177}
178
179int parse_callchain_top_opt(const char *arg)
180{
181 return __parse_callchain_report_opt(arg, true);
182}
183
184int perf_callchain_config(const char *var, const char *value)
185{
186 char *endptr;
187
188 if (prefixcmp(var, "call-graph."))
189 return 0;
190 var += sizeof("call-graph.") - 1;
191
192 if (!strcmp(var, "record-mode"))
193 return parse_callchain_record_opt(value, &callchain_param);
194#ifdef HAVE_DWARF_UNWIND_SUPPORT
195 if (!strcmp(var, "dump-size")) {
196 unsigned long size = 0;
197 int ret;
198
199 ret = get_stack_size(value, &size);
200 callchain_param.dump_size = size;
201
202 return ret;
203 }
204#endif
205 if (!strcmp(var, "print-type"))
206 return parse_callchain_mode(value);
207 if (!strcmp(var, "order"))
208 return parse_callchain_order(value);
209 if (!strcmp(var, "sort-key"))
210 return parse_callchain_sort_key(value);
211 if (!strcmp(var, "threshold")) {
212 callchain_param.min_percent = strtod(value, &endptr);
213 if (value == endptr)
214 return -1;
215 }
216 if (!strcmp(var, "print-limit")) {
217 callchain_param.print_limit = strtod(value, &endptr);
218 if (value == endptr)
219 return -1;
220 }
221
222 return 0;
223}
224
225static void
226rb_insert_callchain(struct rb_root *root, struct callchain_node *chain,
227 enum chain_mode mode)
228{
229 struct rb_node **p = &root->rb_node;
230 struct rb_node *parent = NULL;
231 struct callchain_node *rnode;
232 u64 chain_cumul = callchain_cumul_hits(chain);
233
234 while (*p) {
235 u64 rnode_cumul;
236
237 parent = *p;
238 rnode = rb_entry(parent, struct callchain_node, rb_node);
239 rnode_cumul = callchain_cumul_hits(rnode);
240
241 switch (mode) {
242 case CHAIN_FLAT:
243 case CHAIN_FOLDED:
244 if (rnode->hit < chain->hit)
245 p = &(*p)->rb_left;
246 else
247 p = &(*p)->rb_right;
248 break;
249 case CHAIN_GRAPH_ABS: /* Falldown */
250 case CHAIN_GRAPH_REL:
251 if (rnode_cumul < chain_cumul)
252 p = &(*p)->rb_left;
253 else
254 p = &(*p)->rb_right;
255 break;
256 case CHAIN_NONE:
257 default:
258 break;
259 }
260 }
261
262 rb_link_node(&chain->rb_node, parent, p);
263 rb_insert_color(&chain->rb_node, root);
264}
265
266static void
267__sort_chain_flat(struct rb_root *rb_root, struct callchain_node *node,
268 u64 min_hit)
269{
270 struct rb_node *n;
271 struct callchain_node *child;
272
273 n = rb_first(&node->rb_root_in);
274 while (n) {
275 child = rb_entry(n, struct callchain_node, rb_node_in);
276 n = rb_next(n);
277
278 __sort_chain_flat(rb_root, child, min_hit);
279 }
280
281 if (node->hit && node->hit >= min_hit)
282 rb_insert_callchain(rb_root, node, CHAIN_FLAT);
283}
284
285/*
286 * Once we get every callchains from the stream, we can now
287 * sort them by hit
288 */
289static void
290sort_chain_flat(struct rb_root *rb_root, struct callchain_root *root,
291 u64 min_hit, struct callchain_param *param __maybe_unused)
292{
293 *rb_root = RB_ROOT;
294 __sort_chain_flat(rb_root, &root->node, min_hit);
295}
296
297static void __sort_chain_graph_abs(struct callchain_node *node,
298 u64 min_hit)
299{
300 struct rb_node *n;
301 struct callchain_node *child;
302
303 node->rb_root = RB_ROOT;
304 n = rb_first(&node->rb_root_in);
305
306 while (n) {
307 child = rb_entry(n, struct callchain_node, rb_node_in);
308 n = rb_next(n);
309
310 __sort_chain_graph_abs(child, min_hit);
311 if (callchain_cumul_hits(child) >= min_hit)
312 rb_insert_callchain(&node->rb_root, child,
313 CHAIN_GRAPH_ABS);
314 }
315}
316
317static void
318sort_chain_graph_abs(struct rb_root *rb_root, struct callchain_root *chain_root,
319 u64 min_hit, struct callchain_param *param __maybe_unused)
320{
321 __sort_chain_graph_abs(&chain_root->node, min_hit);
322 rb_root->rb_node = chain_root->node.rb_root.rb_node;
323}
324
325static void __sort_chain_graph_rel(struct callchain_node *node,
326 double min_percent)
327{
328 struct rb_node *n;
329 struct callchain_node *child;
330 u64 min_hit;
331
332 node->rb_root = RB_ROOT;
333 min_hit = ceil(node->children_hit * min_percent);
334
335 n = rb_first(&node->rb_root_in);
336 while (n) {
337 child = rb_entry(n, struct callchain_node, rb_node_in);
338 n = rb_next(n);
339
340 __sort_chain_graph_rel(child, min_percent);
341 if (callchain_cumul_hits(child) >= min_hit)
342 rb_insert_callchain(&node->rb_root, child,
343 CHAIN_GRAPH_REL);
344 }
345}
346
347static void
348sort_chain_graph_rel(struct rb_root *rb_root, struct callchain_root *chain_root,
349 u64 min_hit __maybe_unused, struct callchain_param *param)
350{
351 __sort_chain_graph_rel(&chain_root->node, param->min_percent / 100.0);
352 rb_root->rb_node = chain_root->node.rb_root.rb_node;
353}
354
355int callchain_register_param(struct callchain_param *param)
356{
357 switch (param->mode) {
358 case CHAIN_GRAPH_ABS:
359 param->sort = sort_chain_graph_abs;
360 break;
361 case CHAIN_GRAPH_REL:
362 param->sort = sort_chain_graph_rel;
363 break;
364 case CHAIN_FLAT:
365 case CHAIN_FOLDED:
366 param->sort = sort_chain_flat;
367 break;
368 case CHAIN_NONE:
369 default:
370 return -1;
371 }
372 return 0;
373}
374
375/*
376 * Create a child for a parent. If inherit_children, then the new child
377 * will become the new parent of it's parent children
378 */
379static struct callchain_node *
380create_child(struct callchain_node *parent, bool inherit_children)
381{
382 struct callchain_node *new;
383
384 new = zalloc(sizeof(*new));
385 if (!new) {
386 perror("not enough memory to create child for code path tree");
387 return NULL;
388 }
389 new->parent = parent;
390 INIT_LIST_HEAD(&new->val);
391 INIT_LIST_HEAD(&new->parent_val);
392
393 if (inherit_children) {
394 struct rb_node *n;
395 struct callchain_node *child;
396
397 new->rb_root_in = parent->rb_root_in;
398 parent->rb_root_in = RB_ROOT;
399
400 n = rb_first(&new->rb_root_in);
401 while (n) {
402 child = rb_entry(n, struct callchain_node, rb_node_in);
403 child->parent = new;
404 n = rb_next(n);
405 }
406
407 /* make it the first child */
408 rb_link_node(&new->rb_node_in, NULL, &parent->rb_root_in.rb_node);
409 rb_insert_color(&new->rb_node_in, &parent->rb_root_in);
410 }
411
412 return new;
413}
414
415
416/*
417 * Fill the node with callchain values
418 */
419static int
420fill_node(struct callchain_node *node, struct callchain_cursor *cursor)
421{
422 struct callchain_cursor_node *cursor_node;
423
424 node->val_nr = cursor->nr - cursor->pos;
425 if (!node->val_nr)
426 pr_warning("Warning: empty node in callchain tree\n");
427
428 cursor_node = callchain_cursor_current(cursor);
429
430 while (cursor_node) {
431 struct callchain_list *call;
432
433 call = zalloc(sizeof(*call));
434 if (!call) {
435 perror("not enough memory for the code path tree");
436 return -1;
437 }
438 call->ip = cursor_node->ip;
439 call->ms.sym = cursor_node->sym;
440 call->ms.map = cursor_node->map;
441 list_add_tail(&call->list, &node->val);
442
443 callchain_cursor_advance(cursor);
444 cursor_node = callchain_cursor_current(cursor);
445 }
446 return 0;
447}
448
449static struct callchain_node *
450add_child(struct callchain_node *parent,
451 struct callchain_cursor *cursor,
452 u64 period)
453{
454 struct callchain_node *new;
455
456 new = create_child(parent, false);
457 if (new == NULL)
458 return NULL;
459
460 if (fill_node(new, cursor) < 0) {
461 struct callchain_list *call, *tmp;
462
463 list_for_each_entry_safe(call, tmp, &new->val, list) {
464 list_del(&call->list);
465 free(call);
466 }
467 free(new);
468 return NULL;
469 }
470
471 new->children_hit = 0;
472 new->hit = period;
473 new->children_count = 0;
474 new->count = 1;
475 return new;
476}
477
478enum match_result {
479 MATCH_ERROR = -1,
480 MATCH_EQ,
481 MATCH_LT,
482 MATCH_GT,
483};
484
485static enum match_result match_chain(struct callchain_cursor_node *node,
486 struct callchain_list *cnode)
487{
488 struct symbol *sym = node->sym;
489 u64 left, right;
490
491 if (cnode->ms.sym && sym &&
492 callchain_param.key == CCKEY_FUNCTION) {
493 left = cnode->ms.sym->start;
494 right = sym->start;
495 } else {
496 left = cnode->ip;
497 right = node->ip;
498 }
499
500 if (left == right)
501 return MATCH_EQ;
502
503 return left > right ? MATCH_GT : MATCH_LT;
504}
505
506/*
507 * Split the parent in two parts (a new child is created) and
508 * give a part of its callchain to the created child.
509 * Then create another child to host the given callchain of new branch
510 */
511static int
512split_add_child(struct callchain_node *parent,
513 struct callchain_cursor *cursor,
514 struct callchain_list *to_split,
515 u64 idx_parents, u64 idx_local, u64 period)
516{
517 struct callchain_node *new;
518 struct list_head *old_tail;
519 unsigned int idx_total = idx_parents + idx_local;
520
521 /* split */
522 new = create_child(parent, true);
523 if (new == NULL)
524 return -1;
525
526 /* split the callchain and move a part to the new child */
527 old_tail = parent->val.prev;
528 list_del_range(&to_split->list, old_tail);
529 new->val.next = &to_split->list;
530 new->val.prev = old_tail;
531 to_split->list.prev = &new->val;
532 old_tail->next = &new->val;
533
534 /* split the hits */
535 new->hit = parent->hit;
536 new->children_hit = parent->children_hit;
537 parent->children_hit = callchain_cumul_hits(new);
538 new->val_nr = parent->val_nr - idx_local;
539 parent->val_nr = idx_local;
540 new->count = parent->count;
541 new->children_count = parent->children_count;
542 parent->children_count = callchain_cumul_counts(new);
543
544 /* create a new child for the new branch if any */
545 if (idx_total < cursor->nr) {
546 struct callchain_node *first;
547 struct callchain_list *cnode;
548 struct callchain_cursor_node *node;
549 struct rb_node *p, **pp;
550
551 parent->hit = 0;
552 parent->children_hit += period;
553 parent->count = 0;
554 parent->children_count += 1;
555
556 node = callchain_cursor_current(cursor);
557 new = add_child(parent, cursor, period);
558 if (new == NULL)
559 return -1;
560
561 /*
562 * This is second child since we moved parent's children
563 * to new (first) child above.
564 */
565 p = parent->rb_root_in.rb_node;
566 first = rb_entry(p, struct callchain_node, rb_node_in);
567 cnode = list_first_entry(&first->val, struct callchain_list,
568 list);
569
570 if (match_chain(node, cnode) == MATCH_LT)
571 pp = &p->rb_left;
572 else
573 pp = &p->rb_right;
574
575 rb_link_node(&new->rb_node_in, p, pp);
576 rb_insert_color(&new->rb_node_in, &parent->rb_root_in);
577 } else {
578 parent->hit = period;
579 parent->count = 1;
580 }
581 return 0;
582}
583
584static enum match_result
585append_chain(struct callchain_node *root,
586 struct callchain_cursor *cursor,
587 u64 period);
588
589static int
590append_chain_children(struct callchain_node *root,
591 struct callchain_cursor *cursor,
592 u64 period)
593{
594 struct callchain_node *rnode;
595 struct callchain_cursor_node *node;
596 struct rb_node **p = &root->rb_root_in.rb_node;
597 struct rb_node *parent = NULL;
598
599 node = callchain_cursor_current(cursor);
600 if (!node)
601 return -1;
602
603 /* lookup in childrens */
604 while (*p) {
605 enum match_result ret;
606
607 parent = *p;
608 rnode = rb_entry(parent, struct callchain_node, rb_node_in);
609
610 /* If at least first entry matches, rely to children */
611 ret = append_chain(rnode, cursor, period);
612 if (ret == MATCH_EQ)
613 goto inc_children_hit;
614 if (ret == MATCH_ERROR)
615 return -1;
616
617 if (ret == MATCH_LT)
618 p = &parent->rb_left;
619 else
620 p = &parent->rb_right;
621 }
622 /* nothing in children, add to the current node */
623 rnode = add_child(root, cursor, period);
624 if (rnode == NULL)
625 return -1;
626
627 rb_link_node(&rnode->rb_node_in, parent, p);
628 rb_insert_color(&rnode->rb_node_in, &root->rb_root_in);
629
630inc_children_hit:
631 root->children_hit += period;
632 root->children_count++;
633 return 0;
634}
635
636static enum match_result
637append_chain(struct callchain_node *root,
638 struct callchain_cursor *cursor,
639 u64 period)
640{
641 struct callchain_list *cnode;
642 u64 start = cursor->pos;
643 bool found = false;
644 u64 matches;
645 enum match_result cmp = MATCH_ERROR;
646
647 /*
648 * Lookup in the current node
649 * If we have a symbol, then compare the start to match
650 * anywhere inside a function, unless function
651 * mode is disabled.
652 */
653 list_for_each_entry(cnode, &root->val, list) {
654 struct callchain_cursor_node *node;
655
656 node = callchain_cursor_current(cursor);
657 if (!node)
658 break;
659
660 cmp = match_chain(node, cnode);
661 if (cmp != MATCH_EQ)
662 break;
663
664 found = true;
665
666 callchain_cursor_advance(cursor);
667 }
668
669 /* matches not, relay no the parent */
670 if (!found) {
671 WARN_ONCE(cmp == MATCH_ERROR, "Chain comparison error\n");
672 return cmp;
673 }
674
675 matches = cursor->pos - start;
676
677 /* we match only a part of the node. Split it and add the new chain */
678 if (matches < root->val_nr) {
679 if (split_add_child(root, cursor, cnode, start, matches,
680 period) < 0)
681 return MATCH_ERROR;
682
683 return MATCH_EQ;
684 }
685
686 /* we match 100% of the path, increment the hit */
687 if (matches == root->val_nr && cursor->pos == cursor->nr) {
688 root->hit += period;
689 root->count++;
690 return MATCH_EQ;
691 }
692
693 /* We match the node and still have a part remaining */
694 if (append_chain_children(root, cursor, period) < 0)
695 return MATCH_ERROR;
696
697 return MATCH_EQ;
698}
699
700int callchain_append(struct callchain_root *root,
701 struct callchain_cursor *cursor,
702 u64 period)
703{
704 if (!cursor->nr)
705 return 0;
706
707 callchain_cursor_commit(cursor);
708
709 if (append_chain_children(&root->node, cursor, period) < 0)
710 return -1;
711
712 if (cursor->nr > root->max_depth)
713 root->max_depth = cursor->nr;
714
715 return 0;
716}
717
718static int
719merge_chain_branch(struct callchain_cursor *cursor,
720 struct callchain_node *dst, struct callchain_node *src)
721{
722 struct callchain_cursor_node **old_last = cursor->last;
723 struct callchain_node *child;
724 struct callchain_list *list, *next_list;
725 struct rb_node *n;
726 int old_pos = cursor->nr;
727 int err = 0;
728
729 list_for_each_entry_safe(list, next_list, &src->val, list) {
730 callchain_cursor_append(cursor, list->ip,
731 list->ms.map, list->ms.sym);
732 list_del(&list->list);
733 free(list);
734 }
735
736 if (src->hit) {
737 callchain_cursor_commit(cursor);
738 if (append_chain_children(dst, cursor, src->hit) < 0)
739 return -1;
740 }
741
742 n = rb_first(&src->rb_root_in);
743 while (n) {
744 child = container_of(n, struct callchain_node, rb_node_in);
745 n = rb_next(n);
746 rb_erase(&child->rb_node_in, &src->rb_root_in);
747
748 err = merge_chain_branch(cursor, dst, child);
749 if (err)
750 break;
751
752 free(child);
753 }
754
755 cursor->nr = old_pos;
756 cursor->last = old_last;
757
758 return err;
759}
760
761int callchain_merge(struct callchain_cursor *cursor,
762 struct callchain_root *dst, struct callchain_root *src)
763{
764 return merge_chain_branch(cursor, &dst->node, &src->node);
765}
766
767int callchain_cursor_append(struct callchain_cursor *cursor,
768 u64 ip, struct map *map, struct symbol *sym)
769{
770 struct callchain_cursor_node *node = *cursor->last;
771
772 if (!node) {
773 node = calloc(1, sizeof(*node));
774 if (!node)
775 return -ENOMEM;
776
777 *cursor->last = node;
778 }
779
780 node->ip = ip;
781 node->map = map;
782 node->sym = sym;
783
784 cursor->nr++;
785
786 cursor->last = &node->next;
787
788 return 0;
789}
790
791int sample__resolve_callchain(struct perf_sample *sample, struct symbol **parent,
792 struct perf_evsel *evsel, struct addr_location *al,
793 int max_stack)
794{
795 if (sample->callchain == NULL)
796 return 0;
797
798 if (symbol_conf.use_callchain || symbol_conf.cumulate_callchain ||
799 sort__has_parent) {
800 return thread__resolve_callchain(al->thread, evsel, sample,
801 parent, al, max_stack);
802 }
803 return 0;
804}
805
806int hist_entry__append_callchain(struct hist_entry *he, struct perf_sample *sample)
807{
808 if (!symbol_conf.use_callchain || sample->callchain == NULL)
809 return 0;
810 return callchain_append(he->callchain, &callchain_cursor, sample->period);
811}
812
813int fill_callchain_info(struct addr_location *al, struct callchain_cursor_node *node,
814 bool hide_unresolved)
815{
816 al->map = node->map;
817 al->sym = node->sym;
818 if (node->map)
819 al->addr = node->map->map_ip(node->map, node->ip);
820 else
821 al->addr = node->ip;
822
823 if (al->sym == NULL) {
824 if (hide_unresolved)
825 return 0;
826 if (al->map == NULL)
827 goto out;
828 }
829
830 if (al->map->groups == &al->machine->kmaps) {
831 if (machine__is_host(al->machine)) {
832 al->cpumode = PERF_RECORD_MISC_KERNEL;
833 al->level = 'k';
834 } else {
835 al->cpumode = PERF_RECORD_MISC_GUEST_KERNEL;
836 al->level = 'g';
837 }
838 } else {
839 if (machine__is_host(al->machine)) {
840 al->cpumode = PERF_RECORD_MISC_USER;
841 al->level = '.';
842 } else if (perf_guest) {
843 al->cpumode = PERF_RECORD_MISC_GUEST_USER;
844 al->level = 'u';
845 } else {
846 al->cpumode = PERF_RECORD_MISC_HYPERVISOR;
847 al->level = 'H';
848 }
849 }
850
851out:
852 return 1;
853}
854
855char *callchain_list__sym_name(struct callchain_list *cl,
856 char *bf, size_t bfsize, bool show_dso)
857{
858 int printed;
859
860 if (cl->ms.sym) {
861 if (callchain_param.key == CCKEY_ADDRESS &&
862 cl->ms.map && !cl->srcline)
863 cl->srcline = get_srcline(cl->ms.map->dso,
864 map__rip_2objdump(cl->ms.map,
865 cl->ip),
866 cl->ms.sym, false);
867 if (cl->srcline)
868 printed = scnprintf(bf, bfsize, "%s %s",
869 cl->ms.sym->name, cl->srcline);
870 else
871 printed = scnprintf(bf, bfsize, "%s", cl->ms.sym->name);
872 } else
873 printed = scnprintf(bf, bfsize, "%#" PRIx64, cl->ip);
874
875 if (show_dso)
876 scnprintf(bf + printed, bfsize - printed, " %s",
877 cl->ms.map ?
878 cl->ms.map->dso->short_name :
879 "unknown");
880
881 return bf;
882}
883
884char *callchain_node__scnprintf_value(struct callchain_node *node,
885 char *bf, size_t bfsize, u64 total)
886{
887 double percent = 0.0;
888 u64 period = callchain_cumul_hits(node);
889 unsigned count = callchain_cumul_counts(node);
890
891 if (callchain_param.mode == CHAIN_FOLDED) {
892 period = node->hit;
893 count = node->count;
894 }
895
896 switch (callchain_param.value) {
897 case CCVAL_PERIOD:
898 scnprintf(bf, bfsize, "%"PRIu64, period);
899 break;
900 case CCVAL_COUNT:
901 scnprintf(bf, bfsize, "%u", count);
902 break;
903 case CCVAL_PERCENT:
904 default:
905 if (total)
906 percent = period * 100.0 / total;
907 scnprintf(bf, bfsize, "%.2f%%", percent);
908 break;
909 }
910 return bf;
911}
912
913int callchain_node__fprintf_value(struct callchain_node *node,
914 FILE *fp, u64 total)
915{
916 double percent = 0.0;
917 u64 period = callchain_cumul_hits(node);
918 unsigned count = callchain_cumul_counts(node);
919
920 if (callchain_param.mode == CHAIN_FOLDED) {
921 period = node->hit;
922 count = node->count;
923 }
924
925 switch (callchain_param.value) {
926 case CCVAL_PERIOD:
927 return fprintf(fp, "%"PRIu64, period);
928 case CCVAL_COUNT:
929 return fprintf(fp, "%u", count);
930 case CCVAL_PERCENT:
931 default:
932 if (total)
933 percent = period * 100.0 / total;
934 return percent_color_fprintf(fp, "%.2f%%", percent);
935 }
936 return 0;
937}
938
939static void free_callchain_node(struct callchain_node *node)
940{
941 struct callchain_list *list, *tmp;
942 struct callchain_node *child;
943 struct rb_node *n;
944
945 list_for_each_entry_safe(list, tmp, &node->parent_val, list) {
946 list_del(&list->list);
947 free(list);
948 }
949
950 list_for_each_entry_safe(list, tmp, &node->val, list) {
951 list_del(&list->list);
952 free(list);
953 }
954
955 n = rb_first(&node->rb_root_in);
956 while (n) {
957 child = container_of(n, struct callchain_node, rb_node_in);
958 n = rb_next(n);
959 rb_erase(&child->rb_node_in, &node->rb_root_in);
960
961 free_callchain_node(child);
962 free(child);
963 }
964}
965
966void free_callchain(struct callchain_root *root)
967{
968 if (!symbol_conf.use_callchain)
969 return;
970
971 free_callchain_node(&root->node);
972}
973
974static u64 decay_callchain_node(struct callchain_node *node)
975{
976 struct callchain_node *child;
977 struct rb_node *n;
978 u64 child_hits = 0;
979
980 n = rb_first(&node->rb_root_in);
981 while (n) {
982 child = container_of(n, struct callchain_node, rb_node_in);
983
984 child_hits += decay_callchain_node(child);
985 n = rb_next(n);
986 }
987
988 node->hit = (node->hit * 7) / 8;
989 node->children_hit = child_hits;
990
991 return node->hit;
992}
993
994void decay_callchain(struct callchain_root *root)
995{
996 if (!symbol_conf.use_callchain)
997 return;
998
999 decay_callchain_node(&root->node);
1000}
1001
1002int callchain_node__make_parent_list(struct callchain_node *node)
1003{
1004 struct callchain_node *parent = node->parent;
1005 struct callchain_list *chain, *new;
1006 LIST_HEAD(head);
1007
1008 while (parent) {
1009 list_for_each_entry_reverse(chain, &parent->val, list) {
1010 new = malloc(sizeof(*new));
1011 if (new == NULL)
1012 goto out;
1013 *new = *chain;
1014 new->has_children = false;
1015 list_add_tail(&new->list, &head);
1016 }
1017 parent = parent->parent;
1018 }
1019
1020 list_for_each_entry_safe_reverse(chain, new, &head, list)
1021 list_move_tail(&chain->list, &node->parent_val);
1022
1023 if (!list_empty(&node->parent_val)) {
1024 chain = list_first_entry(&node->parent_val, struct callchain_list, list);
1025 chain->has_children = rb_prev(&node->rb_node) || rb_next(&node->rb_node);
1026
1027 chain = list_first_entry(&node->val, struct callchain_list, list);
1028 chain->has_children = false;
1029 }
1030 return 0;
1031
1032out:
1033 list_for_each_entry_safe(chain, new, &head, list) {
1034 list_del(&chain->list);
1035 free(chain);
1036 }
1037 return -ENOMEM;
1038}
1/*
2 * Copyright (C) 2009-2011, Frederic Weisbecker <fweisbec@gmail.com>
3 *
4 * Handle the callchains from the stream in an ad-hoc radix tree and then
5 * sort them in an rbtree.
6 *
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 *
10 */
11
12#include <stdlib.h>
13#include <stdio.h>
14#include <stdbool.h>
15#include <errno.h>
16#include <math.h>
17
18#include "asm/bug.h"
19
20#include "hist.h"
21#include "util.h"
22#include "sort.h"
23#include "machine.h"
24#include "callchain.h"
25
26__thread struct callchain_cursor callchain_cursor;
27
28static void
29rb_insert_callchain(struct rb_root *root, struct callchain_node *chain,
30 enum chain_mode mode)
31{
32 struct rb_node **p = &root->rb_node;
33 struct rb_node *parent = NULL;
34 struct callchain_node *rnode;
35 u64 chain_cumul = callchain_cumul_hits(chain);
36
37 while (*p) {
38 u64 rnode_cumul;
39
40 parent = *p;
41 rnode = rb_entry(parent, struct callchain_node, rb_node);
42 rnode_cumul = callchain_cumul_hits(rnode);
43
44 switch (mode) {
45 case CHAIN_FLAT:
46 if (rnode->hit < chain->hit)
47 p = &(*p)->rb_left;
48 else
49 p = &(*p)->rb_right;
50 break;
51 case CHAIN_GRAPH_ABS: /* Falldown */
52 case CHAIN_GRAPH_REL:
53 if (rnode_cumul < chain_cumul)
54 p = &(*p)->rb_left;
55 else
56 p = &(*p)->rb_right;
57 break;
58 case CHAIN_NONE:
59 default:
60 break;
61 }
62 }
63
64 rb_link_node(&chain->rb_node, parent, p);
65 rb_insert_color(&chain->rb_node, root);
66}
67
68static void
69__sort_chain_flat(struct rb_root *rb_root, struct callchain_node *node,
70 u64 min_hit)
71{
72 struct rb_node *n;
73 struct callchain_node *child;
74
75 n = rb_first(&node->rb_root_in);
76 while (n) {
77 child = rb_entry(n, struct callchain_node, rb_node_in);
78 n = rb_next(n);
79
80 __sort_chain_flat(rb_root, child, min_hit);
81 }
82
83 if (node->hit && node->hit >= min_hit)
84 rb_insert_callchain(rb_root, node, CHAIN_FLAT);
85}
86
87/*
88 * Once we get every callchains from the stream, we can now
89 * sort them by hit
90 */
91static void
92sort_chain_flat(struct rb_root *rb_root, struct callchain_root *root,
93 u64 min_hit, struct callchain_param *param __maybe_unused)
94{
95 __sort_chain_flat(rb_root, &root->node, min_hit);
96}
97
98static void __sort_chain_graph_abs(struct callchain_node *node,
99 u64 min_hit)
100{
101 struct rb_node *n;
102 struct callchain_node *child;
103
104 node->rb_root = RB_ROOT;
105 n = rb_first(&node->rb_root_in);
106
107 while (n) {
108 child = rb_entry(n, struct callchain_node, rb_node_in);
109 n = rb_next(n);
110
111 __sort_chain_graph_abs(child, min_hit);
112 if (callchain_cumul_hits(child) >= min_hit)
113 rb_insert_callchain(&node->rb_root, child,
114 CHAIN_GRAPH_ABS);
115 }
116}
117
118static void
119sort_chain_graph_abs(struct rb_root *rb_root, struct callchain_root *chain_root,
120 u64 min_hit, struct callchain_param *param __maybe_unused)
121{
122 __sort_chain_graph_abs(&chain_root->node, min_hit);
123 rb_root->rb_node = chain_root->node.rb_root.rb_node;
124}
125
126static void __sort_chain_graph_rel(struct callchain_node *node,
127 double min_percent)
128{
129 struct rb_node *n;
130 struct callchain_node *child;
131 u64 min_hit;
132
133 node->rb_root = RB_ROOT;
134 min_hit = ceil(node->children_hit * min_percent);
135
136 n = rb_first(&node->rb_root_in);
137 while (n) {
138 child = rb_entry(n, struct callchain_node, rb_node_in);
139 n = rb_next(n);
140
141 __sort_chain_graph_rel(child, min_percent);
142 if (callchain_cumul_hits(child) >= min_hit)
143 rb_insert_callchain(&node->rb_root, child,
144 CHAIN_GRAPH_REL);
145 }
146}
147
148static void
149sort_chain_graph_rel(struct rb_root *rb_root, struct callchain_root *chain_root,
150 u64 min_hit __maybe_unused, struct callchain_param *param)
151{
152 __sort_chain_graph_rel(&chain_root->node, param->min_percent / 100.0);
153 rb_root->rb_node = chain_root->node.rb_root.rb_node;
154}
155
156int callchain_register_param(struct callchain_param *param)
157{
158 switch (param->mode) {
159 case CHAIN_GRAPH_ABS:
160 param->sort = sort_chain_graph_abs;
161 break;
162 case CHAIN_GRAPH_REL:
163 param->sort = sort_chain_graph_rel;
164 break;
165 case CHAIN_FLAT:
166 param->sort = sort_chain_flat;
167 break;
168 case CHAIN_NONE:
169 default:
170 return -1;
171 }
172 return 0;
173}
174
175/*
176 * Create a child for a parent. If inherit_children, then the new child
177 * will become the new parent of it's parent children
178 */
179static struct callchain_node *
180create_child(struct callchain_node *parent, bool inherit_children)
181{
182 struct callchain_node *new;
183
184 new = zalloc(sizeof(*new));
185 if (!new) {
186 perror("not enough memory to create child for code path tree");
187 return NULL;
188 }
189 new->parent = parent;
190 INIT_LIST_HEAD(&new->val);
191
192 if (inherit_children) {
193 struct rb_node *n;
194 struct callchain_node *child;
195
196 new->rb_root_in = parent->rb_root_in;
197 parent->rb_root_in = RB_ROOT;
198
199 n = rb_first(&new->rb_root_in);
200 while (n) {
201 child = rb_entry(n, struct callchain_node, rb_node_in);
202 child->parent = new;
203 n = rb_next(n);
204 }
205
206 /* make it the first child */
207 rb_link_node(&new->rb_node_in, NULL, &parent->rb_root_in.rb_node);
208 rb_insert_color(&new->rb_node_in, &parent->rb_root_in);
209 }
210
211 return new;
212}
213
214
215/*
216 * Fill the node with callchain values
217 */
218static void
219fill_node(struct callchain_node *node, struct callchain_cursor *cursor)
220{
221 struct callchain_cursor_node *cursor_node;
222
223 node->val_nr = cursor->nr - cursor->pos;
224 if (!node->val_nr)
225 pr_warning("Warning: empty node in callchain tree\n");
226
227 cursor_node = callchain_cursor_current(cursor);
228
229 while (cursor_node) {
230 struct callchain_list *call;
231
232 call = zalloc(sizeof(*call));
233 if (!call) {
234 perror("not enough memory for the code path tree");
235 return;
236 }
237 call->ip = cursor_node->ip;
238 call->ms.sym = cursor_node->sym;
239 call->ms.map = cursor_node->map;
240 list_add_tail(&call->list, &node->val);
241
242 callchain_cursor_advance(cursor);
243 cursor_node = callchain_cursor_current(cursor);
244 }
245}
246
247static struct callchain_node *
248add_child(struct callchain_node *parent,
249 struct callchain_cursor *cursor,
250 u64 period)
251{
252 struct callchain_node *new;
253
254 new = create_child(parent, false);
255 fill_node(new, cursor);
256
257 new->children_hit = 0;
258 new->hit = period;
259 return new;
260}
261
262static s64 match_chain(struct callchain_cursor_node *node,
263 struct callchain_list *cnode)
264{
265 struct symbol *sym = node->sym;
266
267 if (cnode->ms.sym && sym &&
268 callchain_param.key == CCKEY_FUNCTION)
269 return cnode->ms.sym->start - sym->start;
270 else
271 return cnode->ip - node->ip;
272}
273
274/*
275 * Split the parent in two parts (a new child is created) and
276 * give a part of its callchain to the created child.
277 * Then create another child to host the given callchain of new branch
278 */
279static void
280split_add_child(struct callchain_node *parent,
281 struct callchain_cursor *cursor,
282 struct callchain_list *to_split,
283 u64 idx_parents, u64 idx_local, u64 period)
284{
285 struct callchain_node *new;
286 struct list_head *old_tail;
287 unsigned int idx_total = idx_parents + idx_local;
288
289 /* split */
290 new = create_child(parent, true);
291
292 /* split the callchain and move a part to the new child */
293 old_tail = parent->val.prev;
294 list_del_range(&to_split->list, old_tail);
295 new->val.next = &to_split->list;
296 new->val.prev = old_tail;
297 to_split->list.prev = &new->val;
298 old_tail->next = &new->val;
299
300 /* split the hits */
301 new->hit = parent->hit;
302 new->children_hit = parent->children_hit;
303 parent->children_hit = callchain_cumul_hits(new);
304 new->val_nr = parent->val_nr - idx_local;
305 parent->val_nr = idx_local;
306
307 /* create a new child for the new branch if any */
308 if (idx_total < cursor->nr) {
309 struct callchain_node *first;
310 struct callchain_list *cnode;
311 struct callchain_cursor_node *node;
312 struct rb_node *p, **pp;
313
314 parent->hit = 0;
315 parent->children_hit += period;
316
317 node = callchain_cursor_current(cursor);
318 new = add_child(parent, cursor, period);
319
320 /*
321 * This is second child since we moved parent's children
322 * to new (first) child above.
323 */
324 p = parent->rb_root_in.rb_node;
325 first = rb_entry(p, struct callchain_node, rb_node_in);
326 cnode = list_first_entry(&first->val, struct callchain_list,
327 list);
328
329 if (match_chain(node, cnode) < 0)
330 pp = &p->rb_left;
331 else
332 pp = &p->rb_right;
333
334 rb_link_node(&new->rb_node_in, p, pp);
335 rb_insert_color(&new->rb_node_in, &parent->rb_root_in);
336 } else {
337 parent->hit = period;
338 }
339}
340
341static int
342append_chain(struct callchain_node *root,
343 struct callchain_cursor *cursor,
344 u64 period);
345
346static void
347append_chain_children(struct callchain_node *root,
348 struct callchain_cursor *cursor,
349 u64 period)
350{
351 struct callchain_node *rnode;
352 struct callchain_cursor_node *node;
353 struct rb_node **p = &root->rb_root_in.rb_node;
354 struct rb_node *parent = NULL;
355
356 node = callchain_cursor_current(cursor);
357 if (!node)
358 return;
359
360 /* lookup in childrens */
361 while (*p) {
362 s64 ret;
363
364 parent = *p;
365 rnode = rb_entry(parent, struct callchain_node, rb_node_in);
366
367 /* If at least first entry matches, rely to children */
368 ret = append_chain(rnode, cursor, period);
369 if (ret == 0)
370 goto inc_children_hit;
371
372 if (ret < 0)
373 p = &parent->rb_left;
374 else
375 p = &parent->rb_right;
376 }
377 /* nothing in children, add to the current node */
378 rnode = add_child(root, cursor, period);
379 rb_link_node(&rnode->rb_node_in, parent, p);
380 rb_insert_color(&rnode->rb_node_in, &root->rb_root_in);
381
382inc_children_hit:
383 root->children_hit += period;
384}
385
386static int
387append_chain(struct callchain_node *root,
388 struct callchain_cursor *cursor,
389 u64 period)
390{
391 struct callchain_list *cnode;
392 u64 start = cursor->pos;
393 bool found = false;
394 u64 matches;
395 int cmp = 0;
396
397 /*
398 * Lookup in the current node
399 * If we have a symbol, then compare the start to match
400 * anywhere inside a function, unless function
401 * mode is disabled.
402 */
403 list_for_each_entry(cnode, &root->val, list) {
404 struct callchain_cursor_node *node;
405
406 node = callchain_cursor_current(cursor);
407 if (!node)
408 break;
409
410 cmp = match_chain(node, cnode);
411 if (cmp)
412 break;
413
414 found = true;
415
416 callchain_cursor_advance(cursor);
417 }
418
419 /* matches not, relay no the parent */
420 if (!found) {
421 WARN_ONCE(!cmp, "Chain comparison error\n");
422 return cmp;
423 }
424
425 matches = cursor->pos - start;
426
427 /* we match only a part of the node. Split it and add the new chain */
428 if (matches < root->val_nr) {
429 split_add_child(root, cursor, cnode, start, matches, period);
430 return 0;
431 }
432
433 /* we match 100% of the path, increment the hit */
434 if (matches == root->val_nr && cursor->pos == cursor->nr) {
435 root->hit += period;
436 return 0;
437 }
438
439 /* We match the node and still have a part remaining */
440 append_chain_children(root, cursor, period);
441
442 return 0;
443}
444
445int callchain_append(struct callchain_root *root,
446 struct callchain_cursor *cursor,
447 u64 period)
448{
449 if (!cursor->nr)
450 return 0;
451
452 callchain_cursor_commit(cursor);
453
454 append_chain_children(&root->node, cursor, period);
455
456 if (cursor->nr > root->max_depth)
457 root->max_depth = cursor->nr;
458
459 return 0;
460}
461
462static int
463merge_chain_branch(struct callchain_cursor *cursor,
464 struct callchain_node *dst, struct callchain_node *src)
465{
466 struct callchain_cursor_node **old_last = cursor->last;
467 struct callchain_node *child;
468 struct callchain_list *list, *next_list;
469 struct rb_node *n;
470 int old_pos = cursor->nr;
471 int err = 0;
472
473 list_for_each_entry_safe(list, next_list, &src->val, list) {
474 callchain_cursor_append(cursor, list->ip,
475 list->ms.map, list->ms.sym);
476 list_del(&list->list);
477 free(list);
478 }
479
480 if (src->hit) {
481 callchain_cursor_commit(cursor);
482 append_chain_children(dst, cursor, src->hit);
483 }
484
485 n = rb_first(&src->rb_root_in);
486 while (n) {
487 child = container_of(n, struct callchain_node, rb_node_in);
488 n = rb_next(n);
489 rb_erase(&child->rb_node_in, &src->rb_root_in);
490
491 err = merge_chain_branch(cursor, dst, child);
492 if (err)
493 break;
494
495 free(child);
496 }
497
498 cursor->nr = old_pos;
499 cursor->last = old_last;
500
501 return err;
502}
503
504int callchain_merge(struct callchain_cursor *cursor,
505 struct callchain_root *dst, struct callchain_root *src)
506{
507 return merge_chain_branch(cursor, &dst->node, &src->node);
508}
509
510int callchain_cursor_append(struct callchain_cursor *cursor,
511 u64 ip, struct map *map, struct symbol *sym)
512{
513 struct callchain_cursor_node *node = *cursor->last;
514
515 if (!node) {
516 node = calloc(1, sizeof(*node));
517 if (!node)
518 return -ENOMEM;
519
520 *cursor->last = node;
521 }
522
523 node->ip = ip;
524 node->map = map;
525 node->sym = sym;
526
527 cursor->nr++;
528
529 cursor->last = &node->next;
530
531 return 0;
532}
533
534int sample__resolve_callchain(struct perf_sample *sample, struct symbol **parent,
535 struct perf_evsel *evsel, struct addr_location *al,
536 int max_stack)
537{
538 if (sample->callchain == NULL)
539 return 0;
540
541 if (symbol_conf.use_callchain || sort__has_parent) {
542 return machine__resolve_callchain(al->machine, evsel, al->thread,
543 sample, parent, al, max_stack);
544 }
545 return 0;
546}
547
548int hist_entry__append_callchain(struct hist_entry *he, struct perf_sample *sample)
549{
550 if (!symbol_conf.use_callchain)
551 return 0;
552 return callchain_append(he->callchain, &callchain_cursor, sample->period);
553}