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 "util.h"
19#include "callchain.h"
20
21bool ip_callchain__valid(struct ip_callchain *chain,
22			 const union perf_event *event)
23{
24	unsigned int chain_size = event->header.size;
25	chain_size -= (unsigned long)&event->ip.__more_data - (unsigned long)event;
26	return chain->nr * sizeof(u64) <= chain_size;
27}
28
29#define chain_for_each_child(child, parent)	\
30	list_for_each_entry(child, &parent->children, siblings)
31
32#define chain_for_each_child_safe(child, next, parent)	\
33	list_for_each_entry_safe(child, next, &parent->children, siblings)
34
35static void
36rb_insert_callchain(struct rb_root *root, struct callchain_node *chain,
37		    enum chain_mode mode)
38{
39	struct rb_node **p = &root->rb_node;
40	struct rb_node *parent = NULL;
41	struct callchain_node *rnode;
42	u64 chain_cumul = callchain_cumul_hits(chain);
43
44	while (*p) {
45		u64 rnode_cumul;
46
47		parent = *p;
48		rnode = rb_entry(parent, struct callchain_node, rb_node);
49		rnode_cumul = callchain_cumul_hits(rnode);
50
51		switch (mode) {
52		case CHAIN_FLAT:
53			if (rnode->hit < chain->hit)
54				p = &(*p)->rb_left;
55			else
56				p = &(*p)->rb_right;
57			break;
58		case CHAIN_GRAPH_ABS: /* Falldown */
59		case CHAIN_GRAPH_REL:
60			if (rnode_cumul < chain_cumul)
61				p = &(*p)->rb_left;
62			else
63				p = &(*p)->rb_right;
64			break;
65		case CHAIN_NONE:
66		default:
67			break;
68		}
69	}
70
71	rb_link_node(&chain->rb_node, parent, p);
72	rb_insert_color(&chain->rb_node, root);
73}
74
75static void
76__sort_chain_flat(struct rb_root *rb_root, struct callchain_node *node,
77		  u64 min_hit)
78{
79	struct callchain_node *child;
80
81	chain_for_each_child(child, node)
82		__sort_chain_flat(rb_root, child, min_hit);
83
84	if (node->hit && node->hit >= min_hit)
85		rb_insert_callchain(rb_root, node, CHAIN_FLAT);
86}
87
88/*
89 * Once we get every callchains from the stream, we can now
90 * sort them by hit
91 */
92static void
93sort_chain_flat(struct rb_root *rb_root, struct callchain_root *root,
94		u64 min_hit, struct callchain_param *param __used)
95{
96	__sort_chain_flat(rb_root, &root->node, min_hit);
97}
98
99static void __sort_chain_graph_abs(struct callchain_node *node,
100				   u64 min_hit)
101{
102	struct callchain_node *child;
103
104	node->rb_root = RB_ROOT;
105
106	chain_for_each_child(child, node) {
107		__sort_chain_graph_abs(child, min_hit);
108		if (callchain_cumul_hits(child) >= min_hit)
109			rb_insert_callchain(&node->rb_root, child,
110					    CHAIN_GRAPH_ABS);
111	}
112}
113
114static void
115sort_chain_graph_abs(struct rb_root *rb_root, struct callchain_root *chain_root,
116		     u64 min_hit, struct callchain_param *param __used)
117{
118	__sort_chain_graph_abs(&chain_root->node, min_hit);
119	rb_root->rb_node = chain_root->node.rb_root.rb_node;
120}
121
122static void __sort_chain_graph_rel(struct callchain_node *node,
123				   double min_percent)
124{
125	struct callchain_node *child;
126	u64 min_hit;
127
128	node->rb_root = RB_ROOT;
129	min_hit = ceil(node->children_hit * min_percent);
130
131	chain_for_each_child(child, node) {
132		__sort_chain_graph_rel(child, min_percent);
133		if (callchain_cumul_hits(child) >= min_hit)
134			rb_insert_callchain(&node->rb_root, child,
135					    CHAIN_GRAPH_REL);
136	}
137}
138
139static void
140sort_chain_graph_rel(struct rb_root *rb_root, struct callchain_root *chain_root,
141		     u64 min_hit __used, struct callchain_param *param)
142{
143	__sort_chain_graph_rel(&chain_root->node, param->min_percent / 100.0);
144	rb_root->rb_node = chain_root->node.rb_root.rb_node;
145}
146
147int callchain_register_param(struct callchain_param *param)
148{
149	switch (param->mode) {
150	case CHAIN_GRAPH_ABS:
151		param->sort = sort_chain_graph_abs;
152		break;
153	case CHAIN_GRAPH_REL:
154		param->sort = sort_chain_graph_rel;
155		break;
156	case CHAIN_FLAT:
157		param->sort = sort_chain_flat;
158		break;
159	case CHAIN_NONE:
160	default:
161		return -1;
162	}
163	return 0;
164}
165
166/*
167 * Create a child for a parent. If inherit_children, then the new child
168 * will become the new parent of it's parent children
169 */
170static struct callchain_node *
171create_child(struct callchain_node *parent, bool inherit_children)
172{
173	struct callchain_node *new;
174
175	new = zalloc(sizeof(*new));
176	if (!new) {
177		perror("not enough memory to create child for code path tree");
178		return NULL;
179	}
180	new->parent = parent;
181	INIT_LIST_HEAD(&new->children);
182	INIT_LIST_HEAD(&new->val);
183
184	if (inherit_children) {
185		struct callchain_node *next;
186
187		list_splice(&parent->children, &new->children);
188		INIT_LIST_HEAD(&parent->children);
189
190		chain_for_each_child(next, new)
191			next->parent = new;
192	}
193	list_add_tail(&new->siblings, &parent->children);
194
195	return new;
196}
197
198
199/*
200 * Fill the node with callchain values
201 */
202static void
203fill_node(struct callchain_node *node, struct callchain_cursor *cursor)
204{
205	struct callchain_cursor_node *cursor_node;
206
207	node->val_nr = cursor->nr - cursor->pos;
208	if (!node->val_nr)
209		pr_warning("Warning: empty node in callchain tree\n");
210
211	cursor_node = callchain_cursor_current(cursor);
212
213	while (cursor_node) {
214		struct callchain_list *call;
215
216		call = zalloc(sizeof(*call));
217		if (!call) {
218			perror("not enough memory for the code path tree");
219			return;
220		}
221		call->ip = cursor_node->ip;
222		call->ms.sym = cursor_node->sym;
223		call->ms.map = cursor_node->map;
224		list_add_tail(&call->list, &node->val);
225
226		callchain_cursor_advance(cursor);
227		cursor_node = callchain_cursor_current(cursor);
228	}
229}
230
231static void
232add_child(struct callchain_node *parent,
233	  struct callchain_cursor *cursor,
234	  u64 period)
235{
236	struct callchain_node *new;
237
238	new = create_child(parent, false);
239	fill_node(new, cursor);
240
241	new->children_hit = 0;
242	new->hit = period;
243}
244
245/*
246 * Split the parent in two parts (a new child is created) and
247 * give a part of its callchain to the created child.
248 * Then create another child to host the given callchain of new branch
249 */
250static void
251split_add_child(struct callchain_node *parent,
252		struct callchain_cursor *cursor,
253		struct callchain_list *to_split,
254		u64 idx_parents, u64 idx_local, u64 period)
255{
256	struct callchain_node *new;
257	struct list_head *old_tail;
258	unsigned int idx_total = idx_parents + idx_local;
259
260	/* split */
261	new = create_child(parent, true);
262
263	/* split the callchain and move a part to the new child */
264	old_tail = parent->val.prev;
265	list_del_range(&to_split->list, old_tail);
266	new->val.next = &to_split->list;
267	new->val.prev = old_tail;
268	to_split->list.prev = &new->val;
269	old_tail->next = &new->val;
270
271	/* split the hits */
272	new->hit = parent->hit;
273	new->children_hit = parent->children_hit;
274	parent->children_hit = callchain_cumul_hits(new);
275	new->val_nr = parent->val_nr - idx_local;
276	parent->val_nr = idx_local;
277
278	/* create a new child for the new branch if any */
279	if (idx_total < cursor->nr) {
280		parent->hit = 0;
281		add_child(parent, cursor, period);
282		parent->children_hit += period;
283	} else {
284		parent->hit = period;
285	}
286}
287
288static int
289append_chain(struct callchain_node *root,
290	     struct callchain_cursor *cursor,
291	     u64 period);
292
293static void
294append_chain_children(struct callchain_node *root,
295		      struct callchain_cursor *cursor,
296		      u64 period)
297{
298	struct callchain_node *rnode;
299
300	/* lookup in childrens */
301	chain_for_each_child(rnode, root) {
302		unsigned int ret = append_chain(rnode, cursor, period);
303
304		if (!ret)
305			goto inc_children_hit;
306	}
307	/* nothing in children, add to the current node */
308	add_child(root, cursor, period);
309
310inc_children_hit:
311	root->children_hit += period;
312}
313
314static int
315append_chain(struct callchain_node *root,
316	     struct callchain_cursor *cursor,
317	     u64 period)
318{
319	struct callchain_cursor_node *curr_snap = cursor->curr;
320	struct callchain_list *cnode;
321	u64 start = cursor->pos;
322	bool found = false;
323	u64 matches;
324
325	/*
326	 * Lookup in the current node
327	 * If we have a symbol, then compare the start to match
328	 * anywhere inside a function.
329	 */
330	list_for_each_entry(cnode, &root->val, list) {
331		struct callchain_cursor_node *node;
332		struct symbol *sym;
333
334		node = callchain_cursor_current(cursor);
335		if (!node)
336			break;
337
338		sym = node->sym;
339
340		if (cnode->ms.sym && sym) {
341			if (cnode->ms.sym->start != sym->start)
342				break;
343		} else if (cnode->ip != node->ip)
344			break;
345
346		if (!found)
347			found = true;
348
349		callchain_cursor_advance(cursor);
350	}
351
352	/* matches not, relay on the parent */
353	if (!found) {
354		cursor->curr = curr_snap;
355		cursor->pos = start;
356		return -1;
357	}
358
359	matches = cursor->pos - start;
360
361	/* we match only a part of the node. Split it and add the new chain */
362	if (matches < root->val_nr) {
363		split_add_child(root, cursor, cnode, start, matches, period);
364		return 0;
365	}
366
367	/* we match 100% of the path, increment the hit */
368	if (matches == root->val_nr && cursor->pos == cursor->nr) {
369		root->hit += period;
370		return 0;
371	}
372
373	/* We match the node and still have a part remaining */
374	append_chain_children(root, cursor, period);
375
376	return 0;
377}
378
379int callchain_append(struct callchain_root *root,
380		     struct callchain_cursor *cursor,
381		     u64 period)
382{
383	if (!cursor->nr)
384		return 0;
385
386	callchain_cursor_commit(cursor);
387
388	append_chain_children(&root->node, cursor, period);
389
390	if (cursor->nr > root->max_depth)
391		root->max_depth = cursor->nr;
392
393	return 0;
394}
395
396static int
397merge_chain_branch(struct callchain_cursor *cursor,
398		   struct callchain_node *dst, struct callchain_node *src)
399{
400	struct callchain_cursor_node **old_last = cursor->last;
401	struct callchain_node *child, *next_child;
402	struct callchain_list *list, *next_list;
403	int old_pos = cursor->nr;
404	int err = 0;
405
406	list_for_each_entry_safe(list, next_list, &src->val, list) {
407		callchain_cursor_append(cursor, list->ip,
408					list->ms.map, list->ms.sym);
409		list_del(&list->list);
410		free(list);
411	}
412
413	if (src->hit) {
414		callchain_cursor_commit(cursor);
415		append_chain_children(dst, cursor, src->hit);
416	}
417
418	chain_for_each_child_safe(child, next_child, src) {
419		err = merge_chain_branch(cursor, dst, child);
420		if (err)
421			break;
422
423		list_del(&child->siblings);
424		free(child);
425	}
426
427	cursor->nr = old_pos;
428	cursor->last = old_last;
429
430	return err;
431}
432
433int callchain_merge(struct callchain_cursor *cursor,
434		    struct callchain_root *dst, struct callchain_root *src)
435{
436	return merge_chain_branch(cursor, &dst->node, &src->node);
437}
438
439int callchain_cursor_append(struct callchain_cursor *cursor,
440			    u64 ip, struct map *map, struct symbol *sym)
441{
442	struct callchain_cursor_node *node = *cursor->last;
443
444	if (!node) {
445		node = calloc(sizeof(*node), 1);
446		if (!node)
447			return -ENOMEM;
448
449		*cursor->last = node;
450	}
451
452	node->ip = ip;
453	node->map = map;
454	node->sym = sym;
455
456	cursor->nr++;
457
458	cursor->last = &node->next;
459
460	return 0;
461}
462