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