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
29static 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
56int 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
120static 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
137static 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
150static 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
167int
168parse_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
213int 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
254static void
255rb_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
294static 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 */
317static void
318sort_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
324static 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
344static void
345sort_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
352static 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
374static void
375sort_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
382int 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 */
405static struct callchain_node *
406create_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 */
444static void
445fill_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
473static struct callchain_node *
474add_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
488static 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 */
505static void
506split_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
567static int
568append_chain(struct callchain_node *root,
569	     struct callchain_cursor *cursor,
570	     u64 period);
571
572static void
573append_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
608inc_children_hit:
609	root->children_hit += period;
610}
611
612static int
613append_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
671int 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
688static int
689merge_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
730int 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
736int 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
760int 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
775int 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
782int 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
820out:
821	return 1;
822}
823
824char *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
853static 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
875void free_callchain(struct callchain_root *root)
876{
877	if (!symbol_conf.use_callchain)
878		return;
879
880	free_callchain_node(&root->node);
881}
882