2 * Copyright (C) 2009, Frederic Weisbecker <fweisbec@gmail.com>
4 * Handle the callchains from the stream in an ad-hoc radix tree and then
5 * sort them in an rbtree.
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.
18 #include "callchain.h"
20 #define chain_for_each_child(child, parent) \
21 list_for_each_entry(child, &parent->children, brothers)
24 rb_insert_callchain(struct rb_root
*root
, struct callchain_node
*chain
,
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
);
36 rnode
= rb_entry(parent
, struct callchain_node
, rb_node
);
37 rnode_cumul
= cumul_hits(rnode
);
41 if (rnode
->hit
< chain
->hit
)
46 case CHAIN_GRAPH_ABS
: /* Falldown */
48 if (rnode_cumul
< chain_cumul
)
59 rb_link_node(&chain
->rb_node
, parent
, p
);
60 rb_insert_color(&chain
->rb_node
, root
);
64 __sort_chain_flat(struct rb_root
*rb_root
, struct callchain_node
*node
,
67 struct callchain_node
*child
;
69 chain_for_each_child(child
, node
)
70 __sort_chain_flat(rb_root
, child
, min_hit
);
72 if (node
->hit
&& node
->hit
>= min_hit
)
73 rb_insert_callchain(rb_root
, node
, CHAIN_FLAT
);
77 * Once we get every callchains from the stream, we can now
81 sort_chain_flat(struct rb_root
*rb_root
, struct callchain_node
*node
,
82 u64 min_hit
, struct callchain_param
*param __used
)
84 __sort_chain_flat(rb_root
, node
, min_hit
);
87 static void __sort_chain_graph_abs(struct callchain_node
*node
,
90 struct callchain_node
*child
;
92 node
->rb_root
= RB_ROOT
;
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
,
103 sort_chain_graph_abs(struct rb_root
*rb_root
, struct callchain_node
*chain_root
,
104 u64 min_hit
, struct callchain_param
*param __used
)
106 __sort_chain_graph_abs(chain_root
, min_hit
);
107 rb_root
->rb_node
= chain_root
->rb_root
.rb_node
;
110 static void __sort_chain_graph_rel(struct callchain_node
*node
,
113 struct callchain_node
*child
;
116 node
->rb_root
= RB_ROOT
;
117 min_hit
= ceil(node
->children_hit
* min_percent
);
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
,
128 sort_chain_graph_rel(struct rb_root
*rb_root
, struct callchain_node
*chain_root
,
129 u64 min_hit __used
, struct callchain_param
*param
)
131 __sort_chain_graph_rel(chain_root
, param
->min_percent
/ 100.0);
132 rb_root
->rb_node
= chain_root
->rb_root
.rb_node
;
135 int register_callchain_param(struct callchain_param
*param
)
137 switch (param
->mode
) {
138 case CHAIN_GRAPH_ABS
:
139 param
->sort
= sort_chain_graph_abs
;
141 case CHAIN_GRAPH_REL
:
142 param
->sort
= sort_chain_graph_rel
;
145 param
->sort
= sort_chain_flat
;
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
158 static struct callchain_node
*
159 create_child(struct callchain_node
*parent
, bool inherit_children
)
161 struct callchain_node
*new;
163 new = malloc(sizeof(*new));
165 perror("not enough memory to create child for code path tree");
168 new->parent
= parent
;
169 INIT_LIST_HEAD(&new->children
);
170 INIT_LIST_HEAD(&new->val
);
172 if (inherit_children
) {
173 struct callchain_node
*next
;
175 list_splice(&parent
->children
, &new->children
);
176 INIT_LIST_HEAD(&parent
->children
);
178 chain_for_each_child(next
, new)
181 list_add_tail(&new->brothers
, &parent
->children
);
187 * Fill the node with callchain values
190 fill_node(struct callchain_node
*node
, struct ip_callchain
*chain
,
191 int start
, struct symbol
**syms
)
195 for (i
= start
; i
< chain
->nr
; i
++) {
196 struct callchain_list
*call
;
198 call
= malloc(sizeof(*call
));
200 perror("not enough memory for the code path tree");
203 call
->ip
= chain
->ips
[i
];
205 list_add_tail(&call
->list
, &node
->val
);
207 node
->val_nr
= chain
->nr
- start
;
209 pr_warning("Warning: empty node in callchain tree\n");
213 add_child(struct callchain_node
*parent
, struct ip_callchain
*chain
,
214 int start
, struct symbol
**syms
)
216 struct callchain_node
*new;
218 new = create_child(parent
, false);
219 fill_node(new, chain
, start
, syms
);
221 new->children_hit
= 0;
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
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
)
235 struct callchain_node
*new;
236 struct list_head
*old_tail
;
237 unsigned int idx_total
= idx_parents
+ idx_local
;
240 new = create_child(parent
, true);
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
;
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
;
257 /* create a new child for the new branch if any */
258 if (idx_total
< chain
->nr
) {
260 add_child(parent
, chain
, idx_total
, syms
);
261 parent
->children_hit
++;
268 __append_chain(struct callchain_node
*root
, struct ip_callchain
*chain
,
269 unsigned int start
, struct symbol
**syms
);
272 __append_chain_children(struct callchain_node
*root
, struct ip_callchain
*chain
,
273 struct symbol
**syms
, unsigned int start
)
275 struct callchain_node
*rnode
;
277 /* lookup in childrens */
278 chain_for_each_child(rnode
, root
) {
279 unsigned int ret
= __append_chain(rnode
, chain
, start
, syms
);
282 goto inc_children_hit
;
284 /* nothing in children, add to the current node */
285 add_child(root
, chain
, start
, syms
);
288 root
->children_hit
++;
292 __append_chain(struct callchain_node
*root
, struct ip_callchain
*chain
,
293 unsigned int start
, struct symbol
**syms
)
295 struct callchain_list
*cnode
;
296 unsigned int i
= start
;
300 * Lookup in the current node
301 * If we have a symbol, then compare the start to match
302 * anywhere inside a function.
304 list_for_each_entry(cnode
, &root
->val
, list
) {
307 if (cnode
->sym
&& syms
[i
]) {
308 if (cnode
->sym
->start
!= syms
[i
]->start
)
310 } else if (cnode
->ip
!= chain
->ips
[i
])
317 /* matches not, relay on the parent */
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
);
327 /* we match 100% of the path, increment the hit */
328 if (i
- start
== root
->val_nr
&& i
== chain
->nr
) {
333 /* We match the node and still have a part remaining */
334 __append_chain_children(root
, chain
, syms
, i
);
339 void append_chain(struct callchain_node
*root
, struct ip_callchain
*chain
,
340 struct symbol
**syms
)
344 __append_chain_children(root
, chain
, syms
, 0);