xref: /openbmc/linux/tools/perf/util/callchain.c (revision d2999e1b)
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
29 parse_callchain_report_opt(const char *arg)
30 {
31 	char *tok, *tok2;
32 	char *endptr;
33 
34 	symbol_conf.use_callchain = true;
35 
36 	if (!arg)
37 		return 0;
38 
39 	tok = strtok((char *)arg, ",");
40 	if (!tok)
41 		return -1;
42 
43 	/* get the output mode */
44 	if (!strncmp(tok, "graph", strlen(arg))) {
45 		callchain_param.mode = CHAIN_GRAPH_ABS;
46 
47 	} else if (!strncmp(tok, "flat", strlen(arg))) {
48 		callchain_param.mode = CHAIN_FLAT;
49 	} else if (!strncmp(tok, "fractal", strlen(arg))) {
50 		callchain_param.mode = CHAIN_GRAPH_REL;
51 	} else if (!strncmp(tok, "none", strlen(arg))) {
52 		callchain_param.mode = CHAIN_NONE;
53 		symbol_conf.use_callchain = false;
54 		return 0;
55 	} else {
56 		return -1;
57 	}
58 
59 	/* get the min percentage */
60 	tok = strtok(NULL, ",");
61 	if (!tok)
62 		goto setup;
63 
64 	callchain_param.min_percent = strtod(tok, &endptr);
65 	if (tok == endptr)
66 		return -1;
67 
68 	/* get the print limit */
69 	tok2 = strtok(NULL, ",");
70 	if (!tok2)
71 		goto setup;
72 
73 	if (tok2[0] != 'c') {
74 		callchain_param.print_limit = strtoul(tok2, &endptr, 0);
75 		tok2 = strtok(NULL, ",");
76 		if (!tok2)
77 			goto setup;
78 	}
79 
80 	/* get the call chain order */
81 	if (!strncmp(tok2, "caller", strlen("caller")))
82 		callchain_param.order = ORDER_CALLER;
83 	else if (!strncmp(tok2, "callee", strlen("callee")))
84 		callchain_param.order = ORDER_CALLEE;
85 	else
86 		return -1;
87 
88 	/* Get the sort key */
89 	tok2 = strtok(NULL, ",");
90 	if (!tok2)
91 		goto setup;
92 	if (!strncmp(tok2, "function", strlen("function")))
93 		callchain_param.key = CCKEY_FUNCTION;
94 	else if (!strncmp(tok2, "address", strlen("address")))
95 		callchain_param.key = CCKEY_ADDRESS;
96 	else
97 		return -1;
98 setup:
99 	if (callchain_register_param(&callchain_param) < 0) {
100 		pr_err("Can't register callchain params\n");
101 		return -1;
102 	}
103 	return 0;
104 }
105 
106 static void
107 rb_insert_callchain(struct rb_root *root, struct callchain_node *chain,
108 		    enum chain_mode mode)
109 {
110 	struct rb_node **p = &root->rb_node;
111 	struct rb_node *parent = NULL;
112 	struct callchain_node *rnode;
113 	u64 chain_cumul = callchain_cumul_hits(chain);
114 
115 	while (*p) {
116 		u64 rnode_cumul;
117 
118 		parent = *p;
119 		rnode = rb_entry(parent, struct callchain_node, rb_node);
120 		rnode_cumul = callchain_cumul_hits(rnode);
121 
122 		switch (mode) {
123 		case CHAIN_FLAT:
124 			if (rnode->hit < chain->hit)
125 				p = &(*p)->rb_left;
126 			else
127 				p = &(*p)->rb_right;
128 			break;
129 		case CHAIN_GRAPH_ABS: /* Falldown */
130 		case CHAIN_GRAPH_REL:
131 			if (rnode_cumul < chain_cumul)
132 				p = &(*p)->rb_left;
133 			else
134 				p = &(*p)->rb_right;
135 			break;
136 		case CHAIN_NONE:
137 		default:
138 			break;
139 		}
140 	}
141 
142 	rb_link_node(&chain->rb_node, parent, p);
143 	rb_insert_color(&chain->rb_node, root);
144 }
145 
146 static void
147 __sort_chain_flat(struct rb_root *rb_root, struct callchain_node *node,
148 		  u64 min_hit)
149 {
150 	struct rb_node *n;
151 	struct callchain_node *child;
152 
153 	n = rb_first(&node->rb_root_in);
154 	while (n) {
155 		child = rb_entry(n, struct callchain_node, rb_node_in);
156 		n = rb_next(n);
157 
158 		__sort_chain_flat(rb_root, child, min_hit);
159 	}
160 
161 	if (node->hit && node->hit >= min_hit)
162 		rb_insert_callchain(rb_root, node, CHAIN_FLAT);
163 }
164 
165 /*
166  * Once we get every callchains from the stream, we can now
167  * sort them by hit
168  */
169 static void
170 sort_chain_flat(struct rb_root *rb_root, struct callchain_root *root,
171 		u64 min_hit, struct callchain_param *param __maybe_unused)
172 {
173 	__sort_chain_flat(rb_root, &root->node, min_hit);
174 }
175 
176 static void __sort_chain_graph_abs(struct callchain_node *node,
177 				   u64 min_hit)
178 {
179 	struct rb_node *n;
180 	struct callchain_node *child;
181 
182 	node->rb_root = RB_ROOT;
183 	n = rb_first(&node->rb_root_in);
184 
185 	while (n) {
186 		child = rb_entry(n, struct callchain_node, rb_node_in);
187 		n = rb_next(n);
188 
189 		__sort_chain_graph_abs(child, min_hit);
190 		if (callchain_cumul_hits(child) >= min_hit)
191 			rb_insert_callchain(&node->rb_root, child,
192 					    CHAIN_GRAPH_ABS);
193 	}
194 }
195 
196 static void
197 sort_chain_graph_abs(struct rb_root *rb_root, struct callchain_root *chain_root,
198 		     u64 min_hit, struct callchain_param *param __maybe_unused)
199 {
200 	__sort_chain_graph_abs(&chain_root->node, min_hit);
201 	rb_root->rb_node = chain_root->node.rb_root.rb_node;
202 }
203 
204 static void __sort_chain_graph_rel(struct callchain_node *node,
205 				   double min_percent)
206 {
207 	struct rb_node *n;
208 	struct callchain_node *child;
209 	u64 min_hit;
210 
211 	node->rb_root = RB_ROOT;
212 	min_hit = ceil(node->children_hit * min_percent);
213 
214 	n = rb_first(&node->rb_root_in);
215 	while (n) {
216 		child = rb_entry(n, struct callchain_node, rb_node_in);
217 		n = rb_next(n);
218 
219 		__sort_chain_graph_rel(child, min_percent);
220 		if (callchain_cumul_hits(child) >= min_hit)
221 			rb_insert_callchain(&node->rb_root, child,
222 					    CHAIN_GRAPH_REL);
223 	}
224 }
225 
226 static void
227 sort_chain_graph_rel(struct rb_root *rb_root, struct callchain_root *chain_root,
228 		     u64 min_hit __maybe_unused, struct callchain_param *param)
229 {
230 	__sort_chain_graph_rel(&chain_root->node, param->min_percent / 100.0);
231 	rb_root->rb_node = chain_root->node.rb_root.rb_node;
232 }
233 
234 int callchain_register_param(struct callchain_param *param)
235 {
236 	switch (param->mode) {
237 	case CHAIN_GRAPH_ABS:
238 		param->sort = sort_chain_graph_abs;
239 		break;
240 	case CHAIN_GRAPH_REL:
241 		param->sort = sort_chain_graph_rel;
242 		break;
243 	case CHAIN_FLAT:
244 		param->sort = sort_chain_flat;
245 		break;
246 	case CHAIN_NONE:
247 	default:
248 		return -1;
249 	}
250 	return 0;
251 }
252 
253 /*
254  * Create a child for a parent. If inherit_children, then the new child
255  * will become the new parent of it's parent children
256  */
257 static struct callchain_node *
258 create_child(struct callchain_node *parent, bool inherit_children)
259 {
260 	struct callchain_node *new;
261 
262 	new = zalloc(sizeof(*new));
263 	if (!new) {
264 		perror("not enough memory to create child for code path tree");
265 		return NULL;
266 	}
267 	new->parent = parent;
268 	INIT_LIST_HEAD(&new->val);
269 
270 	if (inherit_children) {
271 		struct rb_node *n;
272 		struct callchain_node *child;
273 
274 		new->rb_root_in = parent->rb_root_in;
275 		parent->rb_root_in = RB_ROOT;
276 
277 		n = rb_first(&new->rb_root_in);
278 		while (n) {
279 			child = rb_entry(n, struct callchain_node, rb_node_in);
280 			child->parent = new;
281 			n = rb_next(n);
282 		}
283 
284 		/* make it the first child */
285 		rb_link_node(&new->rb_node_in, NULL, &parent->rb_root_in.rb_node);
286 		rb_insert_color(&new->rb_node_in, &parent->rb_root_in);
287 	}
288 
289 	return new;
290 }
291 
292 
293 /*
294  * Fill the node with callchain values
295  */
296 static void
297 fill_node(struct callchain_node *node, struct callchain_cursor *cursor)
298 {
299 	struct callchain_cursor_node *cursor_node;
300 
301 	node->val_nr = cursor->nr - cursor->pos;
302 	if (!node->val_nr)
303 		pr_warning("Warning: empty node in callchain tree\n");
304 
305 	cursor_node = callchain_cursor_current(cursor);
306 
307 	while (cursor_node) {
308 		struct callchain_list *call;
309 
310 		call = zalloc(sizeof(*call));
311 		if (!call) {
312 			perror("not enough memory for the code path tree");
313 			return;
314 		}
315 		call->ip = cursor_node->ip;
316 		call->ms.sym = cursor_node->sym;
317 		call->ms.map = cursor_node->map;
318 		list_add_tail(&call->list, &node->val);
319 
320 		callchain_cursor_advance(cursor);
321 		cursor_node = callchain_cursor_current(cursor);
322 	}
323 }
324 
325 static struct callchain_node *
326 add_child(struct callchain_node *parent,
327 	  struct callchain_cursor *cursor,
328 	  u64 period)
329 {
330 	struct callchain_node *new;
331 
332 	new = create_child(parent, false);
333 	fill_node(new, cursor);
334 
335 	new->children_hit = 0;
336 	new->hit = period;
337 	return new;
338 }
339 
340 static s64 match_chain(struct callchain_cursor_node *node,
341 		      struct callchain_list *cnode)
342 {
343 	struct symbol *sym = node->sym;
344 
345 	if (cnode->ms.sym && sym &&
346 	    callchain_param.key == CCKEY_FUNCTION)
347 		return cnode->ms.sym->start - sym->start;
348 	else
349 		return cnode->ip - node->ip;
350 }
351 
352 /*
353  * Split the parent in two parts (a new child is created) and
354  * give a part of its callchain to the created child.
355  * Then create another child to host the given callchain of new branch
356  */
357 static void
358 split_add_child(struct callchain_node *parent,
359 		struct callchain_cursor *cursor,
360 		struct callchain_list *to_split,
361 		u64 idx_parents, u64 idx_local, u64 period)
362 {
363 	struct callchain_node *new;
364 	struct list_head *old_tail;
365 	unsigned int idx_total = idx_parents + idx_local;
366 
367 	/* split */
368 	new = create_child(parent, true);
369 
370 	/* split the callchain and move a part to the new child */
371 	old_tail = parent->val.prev;
372 	list_del_range(&to_split->list, old_tail);
373 	new->val.next = &to_split->list;
374 	new->val.prev = old_tail;
375 	to_split->list.prev = &new->val;
376 	old_tail->next = &new->val;
377 
378 	/* split the hits */
379 	new->hit = parent->hit;
380 	new->children_hit = parent->children_hit;
381 	parent->children_hit = callchain_cumul_hits(new);
382 	new->val_nr = parent->val_nr - idx_local;
383 	parent->val_nr = idx_local;
384 
385 	/* create a new child for the new branch if any */
386 	if (idx_total < cursor->nr) {
387 		struct callchain_node *first;
388 		struct callchain_list *cnode;
389 		struct callchain_cursor_node *node;
390 		struct rb_node *p, **pp;
391 
392 		parent->hit = 0;
393 		parent->children_hit += period;
394 
395 		node = callchain_cursor_current(cursor);
396 		new = add_child(parent, cursor, period);
397 
398 		/*
399 		 * This is second child since we moved parent's children
400 		 * to new (first) child above.
401 		 */
402 		p = parent->rb_root_in.rb_node;
403 		first = rb_entry(p, struct callchain_node, rb_node_in);
404 		cnode = list_first_entry(&first->val, struct callchain_list,
405 					 list);
406 
407 		if (match_chain(node, cnode) < 0)
408 			pp = &p->rb_left;
409 		else
410 			pp = &p->rb_right;
411 
412 		rb_link_node(&new->rb_node_in, p, pp);
413 		rb_insert_color(&new->rb_node_in, &parent->rb_root_in);
414 	} else {
415 		parent->hit = period;
416 	}
417 }
418 
419 static int
420 append_chain(struct callchain_node *root,
421 	     struct callchain_cursor *cursor,
422 	     u64 period);
423 
424 static void
425 append_chain_children(struct callchain_node *root,
426 		      struct callchain_cursor *cursor,
427 		      u64 period)
428 {
429 	struct callchain_node *rnode;
430 	struct callchain_cursor_node *node;
431 	struct rb_node **p = &root->rb_root_in.rb_node;
432 	struct rb_node *parent = NULL;
433 
434 	node = callchain_cursor_current(cursor);
435 	if (!node)
436 		return;
437 
438 	/* lookup in childrens */
439 	while (*p) {
440 		s64 ret;
441 
442 		parent = *p;
443 		rnode = rb_entry(parent, struct callchain_node, rb_node_in);
444 
445 		/* If at least first entry matches, rely to children */
446 		ret = append_chain(rnode, cursor, period);
447 		if (ret == 0)
448 			goto inc_children_hit;
449 
450 		if (ret < 0)
451 			p = &parent->rb_left;
452 		else
453 			p = &parent->rb_right;
454 	}
455 	/* nothing in children, add to the current node */
456 	rnode = add_child(root, cursor, period);
457 	rb_link_node(&rnode->rb_node_in, parent, p);
458 	rb_insert_color(&rnode->rb_node_in, &root->rb_root_in);
459 
460 inc_children_hit:
461 	root->children_hit += period;
462 }
463 
464 static int
465 append_chain(struct callchain_node *root,
466 	     struct callchain_cursor *cursor,
467 	     u64 period)
468 {
469 	struct callchain_list *cnode;
470 	u64 start = cursor->pos;
471 	bool found = false;
472 	u64 matches;
473 	int cmp = 0;
474 
475 	/*
476 	 * Lookup in the current node
477 	 * If we have a symbol, then compare the start to match
478 	 * anywhere inside a function, unless function
479 	 * mode is disabled.
480 	 */
481 	list_for_each_entry(cnode, &root->val, list) {
482 		struct callchain_cursor_node *node;
483 
484 		node = callchain_cursor_current(cursor);
485 		if (!node)
486 			break;
487 
488 		cmp = match_chain(node, cnode);
489 		if (cmp)
490 			break;
491 
492 		found = true;
493 
494 		callchain_cursor_advance(cursor);
495 	}
496 
497 	/* matches not, relay no the parent */
498 	if (!found) {
499 		WARN_ONCE(!cmp, "Chain comparison error\n");
500 		return cmp;
501 	}
502 
503 	matches = cursor->pos - start;
504 
505 	/* we match only a part of the node. Split it and add the new chain */
506 	if (matches < root->val_nr) {
507 		split_add_child(root, cursor, cnode, start, matches, period);
508 		return 0;
509 	}
510 
511 	/* we match 100% of the path, increment the hit */
512 	if (matches == root->val_nr && cursor->pos == cursor->nr) {
513 		root->hit += period;
514 		return 0;
515 	}
516 
517 	/* We match the node and still have a part remaining */
518 	append_chain_children(root, cursor, period);
519 
520 	return 0;
521 }
522 
523 int callchain_append(struct callchain_root *root,
524 		     struct callchain_cursor *cursor,
525 		     u64 period)
526 {
527 	if (!cursor->nr)
528 		return 0;
529 
530 	callchain_cursor_commit(cursor);
531 
532 	append_chain_children(&root->node, cursor, period);
533 
534 	if (cursor->nr > root->max_depth)
535 		root->max_depth = cursor->nr;
536 
537 	return 0;
538 }
539 
540 static int
541 merge_chain_branch(struct callchain_cursor *cursor,
542 		   struct callchain_node *dst, struct callchain_node *src)
543 {
544 	struct callchain_cursor_node **old_last = cursor->last;
545 	struct callchain_node *child;
546 	struct callchain_list *list, *next_list;
547 	struct rb_node *n;
548 	int old_pos = cursor->nr;
549 	int err = 0;
550 
551 	list_for_each_entry_safe(list, next_list, &src->val, list) {
552 		callchain_cursor_append(cursor, list->ip,
553 					list->ms.map, list->ms.sym);
554 		list_del(&list->list);
555 		free(list);
556 	}
557 
558 	if (src->hit) {
559 		callchain_cursor_commit(cursor);
560 		append_chain_children(dst, cursor, src->hit);
561 	}
562 
563 	n = rb_first(&src->rb_root_in);
564 	while (n) {
565 		child = container_of(n, struct callchain_node, rb_node_in);
566 		n = rb_next(n);
567 		rb_erase(&child->rb_node_in, &src->rb_root_in);
568 
569 		err = merge_chain_branch(cursor, dst, child);
570 		if (err)
571 			break;
572 
573 		free(child);
574 	}
575 
576 	cursor->nr = old_pos;
577 	cursor->last = old_last;
578 
579 	return err;
580 }
581 
582 int callchain_merge(struct callchain_cursor *cursor,
583 		    struct callchain_root *dst, struct callchain_root *src)
584 {
585 	return merge_chain_branch(cursor, &dst->node, &src->node);
586 }
587 
588 int callchain_cursor_append(struct callchain_cursor *cursor,
589 			    u64 ip, struct map *map, struct symbol *sym)
590 {
591 	struct callchain_cursor_node *node = *cursor->last;
592 
593 	if (!node) {
594 		node = calloc(1, sizeof(*node));
595 		if (!node)
596 			return -ENOMEM;
597 
598 		*cursor->last = node;
599 	}
600 
601 	node->ip = ip;
602 	node->map = map;
603 	node->sym = sym;
604 
605 	cursor->nr++;
606 
607 	cursor->last = &node->next;
608 
609 	return 0;
610 }
611 
612 int sample__resolve_callchain(struct perf_sample *sample, struct symbol **parent,
613 			      struct perf_evsel *evsel, struct addr_location *al,
614 			      int max_stack)
615 {
616 	if (sample->callchain == NULL)
617 		return 0;
618 
619 	if (symbol_conf.use_callchain || symbol_conf.cumulate_callchain ||
620 	    sort__has_parent) {
621 		return machine__resolve_callchain(al->machine, evsel, al->thread,
622 						  sample, parent, al, max_stack);
623 	}
624 	return 0;
625 }
626 
627 int hist_entry__append_callchain(struct hist_entry *he, struct perf_sample *sample)
628 {
629 	if (!symbol_conf.use_callchain)
630 		return 0;
631 	return callchain_append(he->callchain, &callchain_cursor, sample->period);
632 }
633 
634 int fill_callchain_info(struct addr_location *al, struct callchain_cursor_node *node,
635 			bool hide_unresolved)
636 {
637 	al->map = node->map;
638 	al->sym = node->sym;
639 	if (node->map)
640 		al->addr = node->map->map_ip(node->map, node->ip);
641 	else
642 		al->addr = node->ip;
643 
644 	if (al->sym == NULL) {
645 		if (hide_unresolved)
646 			return 0;
647 		if (al->map == NULL)
648 			goto out;
649 	}
650 
651 	if (al->map->groups == &al->machine->kmaps) {
652 		if (machine__is_host(al->machine)) {
653 			al->cpumode = PERF_RECORD_MISC_KERNEL;
654 			al->level = 'k';
655 		} else {
656 			al->cpumode = PERF_RECORD_MISC_GUEST_KERNEL;
657 			al->level = 'g';
658 		}
659 	} else {
660 		if (machine__is_host(al->machine)) {
661 			al->cpumode = PERF_RECORD_MISC_USER;
662 			al->level = '.';
663 		} else if (perf_guest) {
664 			al->cpumode = PERF_RECORD_MISC_GUEST_USER;
665 			al->level = 'u';
666 		} else {
667 			al->cpumode = PERF_RECORD_MISC_HYPERVISOR;
668 			al->level = 'H';
669 		}
670 	}
671 
672 out:
673 	return 1;
674 }
675