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