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