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.
17 #include "callchain.h"
19 #define chain_for_each_child(child, parent) \
20 list_for_each_entry(child, &parent->children, brothers)
23 rb_insert_callchain(struct rb_root
*root
, struct callchain_node
*chain
,
26 struct rb_node
**p
= &root
->rb_node
;
27 struct rb_node
*parent
= NULL
;
28 struct callchain_node
*rnode
;
29 u64 chain_cumul
= cumul_hits(chain
);
35 rnode
= rb_entry(parent
, struct callchain_node
, rb_node
);
36 rnode_cumul
= cumul_hits(rnode
);
40 if (rnode
->hit
< chain
->hit
)
45 case CHAIN_GRAPH_ABS
: /* Falldown */
47 if (rnode_cumul
< chain_cumul
)
57 rb_link_node(&chain
->rb_node
, parent
, p
);
58 rb_insert_color(&chain
->rb_node
, root
);
62 __sort_chain_flat(struct rb_root
*rb_root
, struct callchain_node
*node
,
65 struct callchain_node
*child
;
67 chain_for_each_child(child
, node
)
68 __sort_chain_flat(rb_root
, child
, min_hit
);
70 if (node
->hit
&& node
->hit
>= min_hit
)
71 rb_insert_callchain(rb_root
, node
, CHAIN_FLAT
);
75 * Once we get every callchains from the stream, we can now
79 sort_chain_flat(struct rb_root
*rb_root
, struct callchain_node
*node
,
80 u64 min_hit
, struct callchain_param
*param __used
)
82 __sort_chain_flat(rb_root
, node
, min_hit
);
85 static void __sort_chain_graph_abs(struct callchain_node
*node
,
88 struct callchain_node
*child
;
90 node
->rb_root
= RB_ROOT
;
92 chain_for_each_child(child
, node
) {
93 __sort_chain_graph_abs(child
, min_hit
);
94 if (cumul_hits(child
) >= min_hit
)
95 rb_insert_callchain(&node
->rb_root
, child
,
101 sort_chain_graph_abs(struct rb_root
*rb_root
, struct callchain_node
*chain_root
,
102 u64 min_hit
, struct callchain_param
*param __used
)
104 __sort_chain_graph_abs(chain_root
, min_hit
);
105 rb_root
->rb_node
= chain_root
->rb_root
.rb_node
;
108 static void __sort_chain_graph_rel(struct callchain_node
*node
,
111 struct callchain_node
*child
;
114 node
->rb_root
= RB_ROOT
;
115 min_hit
= node
->children_hit
* min_percent
/ 100.0;
117 chain_for_each_child(child
, node
) {
118 __sort_chain_graph_rel(child
, min_percent
);
119 if (cumul_hits(child
) >= min_hit
)
120 rb_insert_callchain(&node
->rb_root
, child
,
126 sort_chain_graph_rel(struct rb_root
*rb_root
, struct callchain_node
*chain_root
,
127 u64 min_hit __used
, struct callchain_param
*param
)
129 __sort_chain_graph_rel(chain_root
, param
->min_percent
);
130 rb_root
->rb_node
= chain_root
->rb_root
.rb_node
;
133 int register_callchain_param(struct callchain_param
*param
)
135 switch (param
->mode
) {
136 case CHAIN_GRAPH_ABS
:
137 param
->sort
= sort_chain_graph_abs
;
139 case CHAIN_GRAPH_REL
:
140 param
->sort
= sort_chain_graph_rel
;
143 param
->sort
= sort_chain_flat
;
152 * Create a child for a parent. If inherit_children, then the new child
153 * will become the new parent of it's parent children
155 static struct callchain_node
*
156 create_child(struct callchain_node
*parent
, bool inherit_children
)
158 struct callchain_node
*new;
160 new = malloc(sizeof(*new));
162 perror("not enough memory to create child for code path tree");
165 new->parent
= parent
;
166 INIT_LIST_HEAD(&new->children
);
167 INIT_LIST_HEAD(&new->val
);
169 if (inherit_children
) {
170 struct callchain_node
*next
;
172 list_splice(&parent
->children
, &new->children
);
173 INIT_LIST_HEAD(&parent
->children
);
175 chain_for_each_child(next
, new)
178 list_add_tail(&new->brothers
, &parent
->children
);
184 * Fill the node with callchain values
187 fill_node(struct callchain_node
*node
, struct ip_callchain
*chain
,
188 int start
, struct symbol
**syms
)
192 for (i
= start
; i
< chain
->nr
; i
++) {
193 struct callchain_list
*call
;
195 call
= malloc(sizeof(*call
));
197 perror("not enough memory for the code path tree");
200 call
->ip
= chain
->ips
[i
];
202 list_add_tail(&call
->list
, &node
->val
);
204 node
->val_nr
= chain
->nr
- start
;
206 printf("Warning: empty node in callchain tree\n");
210 add_child(struct callchain_node
*parent
, struct ip_callchain
*chain
,
211 int start
, struct symbol
**syms
)
213 struct callchain_node
*new;
215 new = create_child(parent
, false);
216 fill_node(new, chain
, start
, syms
);
218 new->children_hit
= 0;
223 * Split the parent in two parts (a new child is created) and
224 * give a part of its callchain to the created child.
225 * Then create another child to host the given callchain of new branch
228 split_add_child(struct callchain_node
*parent
, struct ip_callchain
*chain
,
229 struct callchain_list
*to_split
, int idx_parents
, int idx_local
,
230 struct symbol
**syms
)
232 struct callchain_node
*new;
233 struct list_head
*old_tail
;
234 unsigned int idx_total
= idx_parents
+ idx_local
;
237 new = create_child(parent
, true);
239 /* split the callchain and move a part to the new child */
240 old_tail
= parent
->val
.prev
;
241 list_del_range(&to_split
->list
, old_tail
);
242 new->val
.next
= &to_split
->list
;
243 new->val
.prev
= old_tail
;
244 to_split
->list
.prev
= &new->val
;
245 old_tail
->next
= &new->val
;
248 new->hit
= parent
->hit
;
249 new->children_hit
= parent
->children_hit
;
250 parent
->children_hit
= cumul_hits(new);
251 new->val_nr
= parent
->val_nr
- idx_local
;
252 parent
->val_nr
= idx_local
;
254 /* create a new child for the new branch if any */
255 if (idx_total
< chain
->nr
) {
257 add_child(parent
, chain
, idx_total
, syms
);
258 parent
->children_hit
++;
265 __append_chain(struct callchain_node
*root
, struct ip_callchain
*chain
,
266 unsigned int start
, struct symbol
**syms
);
269 __append_chain_children(struct callchain_node
*root
, struct ip_callchain
*chain
,
270 struct symbol
**syms
, unsigned int start
)
272 struct callchain_node
*rnode
;
274 /* lookup in childrens */
275 chain_for_each_child(rnode
, root
) {
276 unsigned int ret
= __append_chain(rnode
, chain
, start
, syms
);
279 goto inc_children_hit
;
281 /* nothing in children, add to the current node */
282 add_child(root
, chain
, start
, syms
);
285 root
->children_hit
++;
289 __append_chain(struct callchain_node
*root
, struct ip_callchain
*chain
,
290 unsigned int start
, struct symbol
**syms
)
292 struct callchain_list
*cnode
;
293 unsigned int i
= start
;
297 * Lookup in the current node
298 * If we have a symbol, then compare the start to match
299 * anywhere inside a function.
301 list_for_each_entry(cnode
, &root
->val
, list
) {
304 if (cnode
->sym
&& syms
[i
]) {
305 if (cnode
->sym
->start
!= syms
[i
]->start
)
307 } else if (cnode
->ip
!= chain
->ips
[i
])
314 /* matches not, relay on the parent */
318 /* we match only a part of the node. Split it and add the new chain */
319 if (i
- start
< root
->val_nr
) {
320 split_add_child(root
, chain
, cnode
, start
, i
- start
, syms
);
324 /* we match 100% of the path, increment the hit */
325 if (i
- start
== root
->val_nr
&& i
== chain
->nr
) {
330 /* We match the node and still have a part remaining */
331 __append_chain_children(root
, chain
, syms
, i
);
336 void append_chain(struct callchain_node
*root
, struct ip_callchain
*chain
,
337 struct symbol
**syms
)
341 __append_chain_children(root
, chain
, syms
, 0);
This page took 0.077278 seconds and 5 git commands to generate.