2 * Copyright (C) 2009-2010, 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 bool ip_callchain__valid(struct ip_callchain
*chain
, event_t
*event
)
22 unsigned int chain_size
= event
->header
.size
;
23 chain_size
-= (unsigned long)&event
->ip
.__more_data
- (unsigned long)event
;
24 return chain
->nr
* sizeof(u64
) <= chain_size
;
27 #define chain_for_each_child(child, parent) \
28 list_for_each_entry(child, &parent->children, brothers)
31 rb_insert_callchain(struct rb_root
*root
, struct callchain_node
*chain
,
34 struct rb_node
**p
= &root
->rb_node
;
35 struct rb_node
*parent
= NULL
;
36 struct callchain_node
*rnode
;
37 u64 chain_cumul
= cumul_hits(chain
);
43 rnode
= rb_entry(parent
, struct callchain_node
, rb_node
);
44 rnode_cumul
= cumul_hits(rnode
);
48 if (rnode
->hit
< chain
->hit
)
53 case CHAIN_GRAPH_ABS
: /* Falldown */
55 if (rnode_cumul
< chain_cumul
)
66 rb_link_node(&chain
->rb_node
, parent
, p
);
67 rb_insert_color(&chain
->rb_node
, root
);
71 __sort_chain_flat(struct rb_root
*rb_root
, struct callchain_node
*node
,
74 struct callchain_node
*child
;
76 chain_for_each_child(child
, node
)
77 __sort_chain_flat(rb_root
, child
, min_hit
);
79 if (node
->hit
&& node
->hit
>= min_hit
)
80 rb_insert_callchain(rb_root
, node
, CHAIN_FLAT
);
84 * Once we get every callchains from the stream, we can now
88 sort_chain_flat(struct rb_root
*rb_root
, struct callchain_node
*node
,
89 u64 min_hit
, struct callchain_param
*param __used
)
91 __sort_chain_flat(rb_root
, node
, min_hit
);
94 static void __sort_chain_graph_abs(struct callchain_node
*node
,
97 struct callchain_node
*child
;
99 node
->rb_root
= RB_ROOT
;
101 chain_for_each_child(child
, node
) {
102 __sort_chain_graph_abs(child
, min_hit
);
103 if (cumul_hits(child
) >= min_hit
)
104 rb_insert_callchain(&node
->rb_root
, child
,
110 sort_chain_graph_abs(struct rb_root
*rb_root
, struct callchain_node
*chain_root
,
111 u64 min_hit
, struct callchain_param
*param __used
)
113 __sort_chain_graph_abs(chain_root
, min_hit
);
114 rb_root
->rb_node
= chain_root
->rb_root
.rb_node
;
117 static void __sort_chain_graph_rel(struct callchain_node
*node
,
120 struct callchain_node
*child
;
123 node
->rb_root
= RB_ROOT
;
124 min_hit
= ceil(node
->children_hit
* min_percent
);
126 chain_for_each_child(child
, node
) {
127 __sort_chain_graph_rel(child
, min_percent
);
128 if (cumul_hits(child
) >= min_hit
)
129 rb_insert_callchain(&node
->rb_root
, child
,
135 sort_chain_graph_rel(struct rb_root
*rb_root
, struct callchain_node
*chain_root
,
136 u64 min_hit __used
, struct callchain_param
*param
)
138 __sort_chain_graph_rel(chain_root
, param
->min_percent
/ 100.0);
139 rb_root
->rb_node
= chain_root
->rb_root
.rb_node
;
142 int register_callchain_param(struct callchain_param
*param
)
144 switch (param
->mode
) {
145 case CHAIN_GRAPH_ABS
:
146 param
->sort
= sort_chain_graph_abs
;
148 case CHAIN_GRAPH_REL
:
149 param
->sort
= sort_chain_graph_rel
;
152 param
->sort
= sort_chain_flat
;
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
165 static struct callchain_node
*
166 create_child(struct callchain_node
*parent
, bool inherit_children
)
168 struct callchain_node
*new;
170 new = malloc(sizeof(*new));
172 perror("not enough memory to create child for code path tree");
175 new->parent
= parent
;
176 INIT_LIST_HEAD(&new->children
);
177 INIT_LIST_HEAD(&new->val
);
179 if (inherit_children
) {
180 struct callchain_node
*next
;
182 list_splice(&parent
->children
, &new->children
);
183 INIT_LIST_HEAD(&parent
->children
);
185 chain_for_each_child(next
, new)
188 list_add_tail(&new->brothers
, &parent
->children
);
196 struct map_symbol ms
;
199 struct resolved_chain
{
201 struct resolved_ip ips
[0];
206 * Fill the node with callchain values
209 fill_node(struct callchain_node
*node
, struct resolved_chain
*chain
, int start
)
213 for (i
= start
; i
< chain
->nr
; i
++) {
214 struct callchain_list
*call
;
216 call
= malloc(sizeof(*call
));
218 perror("not enough memory for the code path tree");
221 call
->ip
= chain
->ips
[i
].ip
;
222 call
->ms
= chain
->ips
[i
].ms
;
223 list_add_tail(&call
->list
, &node
->val
);
225 node
->val_nr
= chain
->nr
- start
;
227 pr_warning("Warning: empty node in callchain tree\n");
231 add_child(struct callchain_node
*parent
, struct resolved_chain
*chain
,
234 struct callchain_node
*new;
236 new = create_child(parent
, false);
237 fill_node(new, chain
, start
);
239 new->children_hit
= 0;
244 * Split the parent in two parts (a new child is created) and
245 * give a part of its callchain to the created child.
246 * Then create another child to host the given callchain of new branch
249 split_add_child(struct callchain_node
*parent
, struct resolved_chain
*chain
,
250 struct callchain_list
*to_split
, int idx_parents
, int idx_local
)
252 struct callchain_node
*new;
253 struct list_head
*old_tail
;
254 unsigned int idx_total
= idx_parents
+ idx_local
;
257 new = create_child(parent
, true);
259 /* split the callchain and move a part to the new child */
260 old_tail
= parent
->val
.prev
;
261 list_del_range(&to_split
->list
, old_tail
);
262 new->val
.next
= &to_split
->list
;
263 new->val
.prev
= old_tail
;
264 to_split
->list
.prev
= &new->val
;
265 old_tail
->next
= &new->val
;
268 new->hit
= parent
->hit
;
269 new->children_hit
= parent
->children_hit
;
270 parent
->children_hit
= cumul_hits(new);
271 new->val_nr
= parent
->val_nr
- idx_local
;
272 parent
->val_nr
= idx_local
;
274 /* create a new child for the new branch if any */
275 if (idx_total
< chain
->nr
) {
277 add_child(parent
, chain
, idx_total
);
278 parent
->children_hit
++;
285 __append_chain(struct callchain_node
*root
, struct resolved_chain
*chain
,
289 __append_chain_children(struct callchain_node
*root
,
290 struct resolved_chain
*chain
,
293 struct callchain_node
*rnode
;
295 /* lookup in childrens */
296 chain_for_each_child(rnode
, root
) {
297 unsigned int ret
= __append_chain(rnode
, chain
, start
);
300 goto inc_children_hit
;
302 /* nothing in children, add to the current node */
303 add_child(root
, chain
, start
);
306 root
->children_hit
++;
310 __append_chain(struct callchain_node
*root
, struct resolved_chain
*chain
,
313 struct callchain_list
*cnode
;
314 unsigned int i
= start
;
318 * Lookup in the current node
319 * If we have a symbol, then compare the start to match
320 * anywhere inside a function.
322 list_for_each_entry(cnode
, &root
->val
, list
) {
328 sym
= chain
->ips
[i
].ms
.sym
;
330 if (cnode
->ms
.sym
&& sym
) {
331 if (cnode
->ms
.sym
->start
!= sym
->start
)
333 } else if (cnode
->ip
!= chain
->ips
[i
].ip
)
341 /* matches not, relay on the parent */
345 /* we match only a part of the node. Split it and add the new chain */
346 if (i
- start
< root
->val_nr
) {
347 split_add_child(root
, chain
, cnode
, start
, i
- start
);
351 /* we match 100% of the path, increment the hit */
352 if (i
- start
== root
->val_nr
&& i
== chain
->nr
) {
357 /* We match the node and still have a part remaining */
358 __append_chain_children(root
, chain
, i
);
363 static void filter_context(struct ip_callchain
*old
, struct resolved_chain
*new,
364 struct map_symbol
*syms
)
368 for (i
= 0; i
< (int)old
->nr
; i
++) {
369 if (old
->ips
[i
] >= PERF_CONTEXT_MAX
)
372 new->ips
[j
].ip
= old
->ips
[i
];
373 new->ips
[j
].ms
= syms
[i
];
381 int append_chain(struct callchain_node
*root
, struct ip_callchain
*chain
,
382 struct map_symbol
*syms
)
384 struct resolved_chain
*filtered
;
389 filtered
= malloc(sizeof(*filtered
) +
390 chain
->nr
* sizeof(struct resolved_ip
));
394 filter_context(chain
, filtered
, syms
);
399 __append_chain_children(root
, filtered
, 0);
This page took 0.048751 seconds and 5 git commands to generate.