xref: /openbmc/linux/tools/perf/util/callchain.c (revision b6dcefde)
1 /*
2  * Copyright (C) 2009, 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 "callchain.h"
19 
20 #define chain_for_each_child(child, parent)	\
21 	list_for_each_entry(child, &parent->children, brothers)
22 
23 static void
24 rb_insert_callchain(struct rb_root *root, struct callchain_node *chain,
25 		    enum chain_mode mode)
26 {
27 	struct rb_node **p = &root->rb_node;
28 	struct rb_node *parent = NULL;
29 	struct callchain_node *rnode;
30 	u64 chain_cumul = cumul_hits(chain);
31 
32 	while (*p) {
33 		u64 rnode_cumul;
34 
35 		parent = *p;
36 		rnode = rb_entry(parent, struct callchain_node, rb_node);
37 		rnode_cumul = cumul_hits(rnode);
38 
39 		switch (mode) {
40 		case CHAIN_FLAT:
41 			if (rnode->hit < chain->hit)
42 				p = &(*p)->rb_left;
43 			else
44 				p = &(*p)->rb_right;
45 			break;
46 		case CHAIN_GRAPH_ABS: /* Falldown */
47 		case CHAIN_GRAPH_REL:
48 			if (rnode_cumul < chain_cumul)
49 				p = &(*p)->rb_left;
50 			else
51 				p = &(*p)->rb_right;
52 			break;
53 		case CHAIN_NONE:
54 		default:
55 			break;
56 		}
57 	}
58 
59 	rb_link_node(&chain->rb_node, parent, p);
60 	rb_insert_color(&chain->rb_node, root);
61 }
62 
63 static void
64 __sort_chain_flat(struct rb_root *rb_root, struct callchain_node *node,
65 		  u64 min_hit)
66 {
67 	struct callchain_node *child;
68 
69 	chain_for_each_child(child, node)
70 		__sort_chain_flat(rb_root, child, min_hit);
71 
72 	if (node->hit && node->hit >= min_hit)
73 		rb_insert_callchain(rb_root, node, CHAIN_FLAT);
74 }
75 
76 /*
77  * Once we get every callchains from the stream, we can now
78  * sort them by hit
79  */
80 static void
81 sort_chain_flat(struct rb_root *rb_root, struct callchain_node *node,
82 		u64 min_hit, struct callchain_param *param __used)
83 {
84 	__sort_chain_flat(rb_root, node, min_hit);
85 }
86 
87 static void __sort_chain_graph_abs(struct callchain_node *node,
88 				   u64 min_hit)
89 {
90 	struct callchain_node *child;
91 
92 	node->rb_root = RB_ROOT;
93 
94 	chain_for_each_child(child, node) {
95 		__sort_chain_graph_abs(child, min_hit);
96 		if (cumul_hits(child) >= min_hit)
97 			rb_insert_callchain(&node->rb_root, child,
98 					    CHAIN_GRAPH_ABS);
99 	}
100 }
101 
102 static void
103 sort_chain_graph_abs(struct rb_root *rb_root, struct callchain_node *chain_root,
104 		     u64 min_hit, struct callchain_param *param __used)
105 {
106 	__sort_chain_graph_abs(chain_root, min_hit);
107 	rb_root->rb_node = chain_root->rb_root.rb_node;
108 }
109 
110 static void __sort_chain_graph_rel(struct callchain_node *node,
111 				   double min_percent)
112 {
113 	struct callchain_node *child;
114 	u64 min_hit;
115 
116 	node->rb_root = RB_ROOT;
117 	min_hit = ceil(node->children_hit * min_percent);
118 
119 	chain_for_each_child(child, node) {
120 		__sort_chain_graph_rel(child, min_percent);
121 		if (cumul_hits(child) >= min_hit)
122 			rb_insert_callchain(&node->rb_root, child,
123 					    CHAIN_GRAPH_REL);
124 	}
125 }
126 
127 static void
128 sort_chain_graph_rel(struct rb_root *rb_root, struct callchain_node *chain_root,
129 		     u64 min_hit __used, struct callchain_param *param)
130 {
131 	__sort_chain_graph_rel(chain_root, param->min_percent / 100.0);
132 	rb_root->rb_node = chain_root->rb_root.rb_node;
133 }
134 
135 int register_callchain_param(struct callchain_param *param)
136 {
137 	switch (param->mode) {
138 	case CHAIN_GRAPH_ABS:
139 		param->sort = sort_chain_graph_abs;
140 		break;
141 	case CHAIN_GRAPH_REL:
142 		param->sort = sort_chain_graph_rel;
143 		break;
144 	case CHAIN_FLAT:
145 		param->sort = sort_chain_flat;
146 		break;
147 	case CHAIN_NONE:
148 	default:
149 		return -1;
150 	}
151 	return 0;
152 }
153 
154 /*
155  * Create a child for a parent. If inherit_children, then the new child
156  * will become the new parent of it's parent children
157  */
158 static struct callchain_node *
159 create_child(struct callchain_node *parent, bool inherit_children)
160 {
161 	struct callchain_node *new;
162 
163 	new = malloc(sizeof(*new));
164 	if (!new) {
165 		perror("not enough memory to create child for code path tree");
166 		return NULL;
167 	}
168 	new->parent = parent;
169 	INIT_LIST_HEAD(&new->children);
170 	INIT_LIST_HEAD(&new->val);
171 
172 	if (inherit_children) {
173 		struct callchain_node *next;
174 
175 		list_splice(&parent->children, &new->children);
176 		INIT_LIST_HEAD(&parent->children);
177 
178 		chain_for_each_child(next, new)
179 			next->parent = new;
180 	}
181 	list_add_tail(&new->brothers, &parent->children);
182 
183 	return new;
184 }
185 
186 /*
187  * Fill the node with callchain values
188  */
189 static void
190 fill_node(struct callchain_node *node, struct ip_callchain *chain,
191 	  int start, struct symbol **syms)
192 {
193 	unsigned int i;
194 
195 	for (i = start; i < chain->nr; i++) {
196 		struct callchain_list *call;
197 
198 		call = malloc(sizeof(*call));
199 		if (!call) {
200 			perror("not enough memory for the code path tree");
201 			return;
202 		}
203 		call->ip = chain->ips[i];
204 		call->sym = syms[i];
205 		list_add_tail(&call->list, &node->val);
206 	}
207 	node->val_nr = chain->nr - start;
208 	if (!node->val_nr)
209 		pr_warning("Warning: empty node in callchain tree\n");
210 }
211 
212 static void
213 add_child(struct callchain_node *parent, struct ip_callchain *chain,
214 	  int start, struct symbol **syms)
215 {
216 	struct callchain_node *new;
217 
218 	new = create_child(parent, false);
219 	fill_node(new, chain, start, syms);
220 
221 	new->children_hit = 0;
222 	new->hit = 1;
223 }
224 
225 /*
226  * Split the parent in two parts (a new child is created) and
227  * give a part of its callchain to the created child.
228  * Then create another child to host the given callchain of new branch
229  */
230 static void
231 split_add_child(struct callchain_node *parent, struct ip_callchain *chain,
232 		struct callchain_list *to_split, int idx_parents, int idx_local,
233 		struct symbol **syms)
234 {
235 	struct callchain_node *new;
236 	struct list_head *old_tail;
237 	unsigned int idx_total = idx_parents + idx_local;
238 
239 	/* split */
240 	new = create_child(parent, true);
241 
242 	/* split the callchain and move a part to the new child */
243 	old_tail = parent->val.prev;
244 	list_del_range(&to_split->list, old_tail);
245 	new->val.next = &to_split->list;
246 	new->val.prev = old_tail;
247 	to_split->list.prev = &new->val;
248 	old_tail->next = &new->val;
249 
250 	/* split the hits */
251 	new->hit = parent->hit;
252 	new->children_hit = parent->children_hit;
253 	parent->children_hit = cumul_hits(new);
254 	new->val_nr = parent->val_nr - idx_local;
255 	parent->val_nr = idx_local;
256 
257 	/* create a new child for the new branch if any */
258 	if (idx_total < chain->nr) {
259 		parent->hit = 0;
260 		add_child(parent, chain, idx_total, syms);
261 		parent->children_hit++;
262 	} else {
263 		parent->hit = 1;
264 	}
265 }
266 
267 static int
268 __append_chain(struct callchain_node *root, struct ip_callchain *chain,
269 	       unsigned int start, struct symbol **syms);
270 
271 static void
272 __append_chain_children(struct callchain_node *root, struct ip_callchain *chain,
273 			struct symbol **syms, unsigned int start)
274 {
275 	struct callchain_node *rnode;
276 
277 	/* lookup in childrens */
278 	chain_for_each_child(rnode, root) {
279 		unsigned int ret = __append_chain(rnode, chain, start, syms);
280 
281 		if (!ret)
282 			goto inc_children_hit;
283 	}
284 	/* nothing in children, add to the current node */
285 	add_child(root, chain, start, syms);
286 
287 inc_children_hit:
288 	root->children_hit++;
289 }
290 
291 static int
292 __append_chain(struct callchain_node *root, struct ip_callchain *chain,
293 	       unsigned int start, struct symbol **syms)
294 {
295 	struct callchain_list *cnode;
296 	unsigned int i = start;
297 	bool found = false;
298 
299 	/*
300 	 * Lookup in the current node
301 	 * If we have a symbol, then compare the start to match
302 	 * anywhere inside a function.
303 	 */
304 	list_for_each_entry(cnode, &root->val, list) {
305 		if (i == chain->nr)
306 			break;
307 		if (cnode->sym && syms[i]) {
308 			if (cnode->sym->start != syms[i]->start)
309 				break;
310 		} else if (cnode->ip != chain->ips[i])
311 			break;
312 		if (!found)
313 			found = true;
314 		i++;
315 	}
316 
317 	/* matches not, relay on the parent */
318 	if (!found)
319 		return -1;
320 
321 	/* we match only a part of the node. Split it and add the new chain */
322 	if (i - start < root->val_nr) {
323 		split_add_child(root, chain, cnode, start, i - start, syms);
324 		return 0;
325 	}
326 
327 	/* we match 100% of the path, increment the hit */
328 	if (i - start == root->val_nr && i == chain->nr) {
329 		root->hit++;
330 		return 0;
331 	}
332 
333 	/* We match the node and still have a part remaining */
334 	__append_chain_children(root, chain, syms, i);
335 
336 	return 0;
337 }
338 
339 void append_chain(struct callchain_node *root, struct ip_callchain *chain,
340 		  struct symbol **syms)
341 {
342 	if (!chain->nr)
343 		return;
344 	__append_chain_children(root, chain, syms, 0);
345 }
346