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