]>
Commit | Line | Data |
---|---|---|
8cb76d99 | 1 | /* |
1b3a0e95 | 2 | * Copyright (C) 2009-2011, Frederic Weisbecker <fweisbec@gmail.com> |
8cb76d99 FW |
3 | * |
4 | * Handle the callchains from the stream in an ad-hoc radix tree and then | |
5 | * sort them in an rbtree. | |
6 | * | |
deac911c FW |
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 | * | |
8cb76d99 FW |
10 | */ |
11 | ||
12 | #include <stdlib.h> | |
13 | #include <stdio.h> | |
14 | #include <stdbool.h> | |
15 | #include <errno.h> | |
c0a8865e | 16 | #include <math.h> |
8cb76d99 | 17 | |
b36f19d5 | 18 | #include "util.h" |
8cb76d99 FW |
19 | #include "callchain.h" |
20 | ||
8115d60c ACM |
21 | bool ip_callchain__valid(struct ip_callchain *chain, |
22 | const union perf_event *event) | |
139633c6 ACM |
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 | ||
14f4654c | 29 | #define chain_for_each_child(child, parent) \ |
529363b7 | 30 | list_for_each_entry(child, &parent->children, siblings) |
14f4654c | 31 | |
612d4fd7 | 32 | #define chain_for_each_child_safe(child, next, parent) \ |
529363b7 | 33 | list_for_each_entry_safe(child, next, &parent->children, siblings) |
612d4fd7 | 34 | |
deac911c | 35 | static void |
4eb3e478 FW |
36 | rb_insert_callchain(struct rb_root *root, struct callchain_node *chain, |
37 | enum chain_mode mode) | |
8cb76d99 FW |
38 | { |
39 | struct rb_node **p = &root->rb_node; | |
40 | struct rb_node *parent = NULL; | |
41 | struct callchain_node *rnode; | |
f08c3154 | 42 | u64 chain_cumul = callchain_cumul_hits(chain); |
8cb76d99 FW |
43 | |
44 | while (*p) { | |
1953287b FW |
45 | u64 rnode_cumul; |
46 | ||
8cb76d99 FW |
47 | parent = *p; |
48 | rnode = rb_entry(parent, struct callchain_node, rb_node); | |
f08c3154 | 49 | rnode_cumul = callchain_cumul_hits(rnode); |
8cb76d99 | 50 | |
4eb3e478 | 51 | switch (mode) { |
805d127d | 52 | case CHAIN_FLAT: |
4eb3e478 FW |
53 | if (rnode->hit < chain->hit) |
54 | p = &(*p)->rb_left; | |
55 | else | |
56 | p = &(*p)->rb_right; | |
57 | break; | |
805d127d FW |
58 | case CHAIN_GRAPH_ABS: /* Falldown */ |
59 | case CHAIN_GRAPH_REL: | |
1953287b | 60 | if (rnode_cumul < chain_cumul) |
4eb3e478 FW |
61 | p = &(*p)->rb_left; |
62 | else | |
63 | p = &(*p)->rb_right; | |
64 | break; | |
83a0944f | 65 | case CHAIN_NONE: |
4eb3e478 FW |
66 | default: |
67 | break; | |
68 | } | |
8cb76d99 FW |
69 | } |
70 | ||
71 | rb_link_node(&chain->rb_node, parent, p); | |
72 | rb_insert_color(&chain->rb_node, root); | |
73 | } | |
74 | ||
805d127d FW |
75 | static 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 | ||
8cb76d99 FW |
88 | /* |
89 | * Once we get every callchains from the stream, we can now | |
90 | * sort them by hit | |
91 | */ | |
805d127d | 92 | static void |
d2009c51 | 93 | sort_chain_flat(struct rb_root *rb_root, struct callchain_root *root, |
805d127d FW |
94 | u64 min_hit, struct callchain_param *param __used) |
95 | { | |
d2009c51 | 96 | __sort_chain_flat(rb_root, &root->node, min_hit); |
805d127d FW |
97 | } |
98 | ||
99 | static void __sort_chain_graph_abs(struct callchain_node *node, | |
100 | u64 min_hit) | |
8cb76d99 FW |
101 | { |
102 | struct callchain_node *child; | |
103 | ||
805d127d | 104 | node->rb_root = RB_ROOT; |
8cb76d99 | 105 | |
805d127d FW |
106 | chain_for_each_child(child, node) { |
107 | __sort_chain_graph_abs(child, min_hit); | |
f08c3154 | 108 | if (callchain_cumul_hits(child) >= min_hit) |
805d127d FW |
109 | rb_insert_callchain(&node->rb_root, child, |
110 | CHAIN_GRAPH_ABS); | |
111 | } | |
112 | } | |
113 | ||
114 | static void | |
d2009c51 | 115 | sort_chain_graph_abs(struct rb_root *rb_root, struct callchain_root *chain_root, |
805d127d FW |
116 | u64 min_hit, struct callchain_param *param __used) |
117 | { | |
d2009c51 FW |
118 | __sort_chain_graph_abs(&chain_root->node, min_hit); |
119 | rb_root->rb_node = chain_root->node.rb_root.rb_node; | |
4eb3e478 FW |
120 | } |
121 | ||
805d127d FW |
122 | static void __sort_chain_graph_rel(struct callchain_node *node, |
123 | double min_percent) | |
4eb3e478 FW |
124 | { |
125 | struct callchain_node *child; | |
805d127d | 126 | u64 min_hit; |
4eb3e478 FW |
127 | |
128 | node->rb_root = RB_ROOT; | |
c0a8865e | 129 | min_hit = ceil(node->children_hit * min_percent); |
4eb3e478 FW |
130 | |
131 | chain_for_each_child(child, node) { | |
805d127d | 132 | __sort_chain_graph_rel(child, min_percent); |
f08c3154 | 133 | if (callchain_cumul_hits(child) >= min_hit) |
805d127d FW |
134 | rb_insert_callchain(&node->rb_root, child, |
135 | CHAIN_GRAPH_REL); | |
4eb3e478 FW |
136 | } |
137 | } | |
138 | ||
805d127d | 139 | static void |
d2009c51 | 140 | sort_chain_graph_rel(struct rb_root *rb_root, struct callchain_root *chain_root, |
805d127d | 141 | u64 min_hit __used, struct callchain_param *param) |
4eb3e478 | 142 | { |
d2009c51 FW |
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; | |
8cb76d99 FW |
145 | } |
146 | ||
16537f13 | 147 | int callchain_register_param(struct callchain_param *param) |
805d127d FW |
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; | |
83a0944f | 159 | case CHAIN_NONE: |
805d127d FW |
160 | default: |
161 | return -1; | |
162 | } | |
163 | return 0; | |
164 | } | |
165 | ||
deac911c FW |
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 | */ | |
170 | static struct callchain_node * | |
171 | create_child(struct callchain_node *parent, bool inherit_children) | |
8cb76d99 FW |
172 | { |
173 | struct callchain_node *new; | |
174 | ||
cdd5b75b | 175 | new = zalloc(sizeof(*new)); |
8cb76d99 FW |
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); | |
deac911c FW |
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 | ||
14f4654c | 190 | chain_for_each_child(next, new) |
deac911c FW |
191 | next->parent = new; |
192 | } | |
529363b7 | 193 | list_add_tail(&new->siblings, &parent->children); |
8cb76d99 FW |
194 | |
195 | return new; | |
196 | } | |
197 | ||
301fde27 | 198 | |
deac911c FW |
199 | /* |
200 | * Fill the node with callchain values | |
201 | */ | |
8cb76d99 | 202 | static void |
1b3a0e95 | 203 | fill_node(struct callchain_node *node, struct callchain_cursor *cursor) |
8cb76d99 | 204 | { |
1b3a0e95 FW |
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"); | |
8cb76d99 | 210 | |
1b3a0e95 FW |
211 | cursor_node = callchain_cursor_current(cursor); |
212 | ||
213 | while (cursor_node) { | |
8cb76d99 FW |
214 | struct callchain_list *call; |
215 | ||
cdd5b75b | 216 | call = zalloc(sizeof(*call)); |
8cb76d99 FW |
217 | if (!call) { |
218 | perror("not enough memory for the code path tree"); | |
219 | return; | |
220 | } | |
1b3a0e95 FW |
221 | call->ip = cursor_node->ip; |
222 | call->ms.sym = cursor_node->sym; | |
223 | call->ms.map = cursor_node->map; | |
8cb76d99 | 224 | list_add_tail(&call->list, &node->val); |
1b3a0e95 FW |
225 | |
226 | callchain_cursor_advance(cursor); | |
227 | cursor_node = callchain_cursor_current(cursor); | |
8cb76d99 | 228 | } |
8cb76d99 FW |
229 | } |
230 | ||
deac911c | 231 | static void |
1b3a0e95 FW |
232 | add_child(struct callchain_node *parent, |
233 | struct callchain_cursor *cursor, | |
234 | u64 period) | |
8cb76d99 FW |
235 | { |
236 | struct callchain_node *new; | |
237 | ||
deac911c | 238 | new = create_child(parent, false); |
1b3a0e95 | 239 | fill_node(new, cursor); |
8cb76d99 | 240 | |
1953287b | 241 | new->children_hit = 0; |
108553e1 | 242 | new->hit = period; |
8cb76d99 FW |
243 | } |
244 | ||
deac911c FW |
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 | */ | |
8cb76d99 | 250 | static void |
1b3a0e95 FW |
251 | split_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) | |
8cb76d99 FW |
255 | { |
256 | struct callchain_node *new; | |
deac911c | 257 | struct list_head *old_tail; |
f37a291c | 258 | unsigned int idx_total = idx_parents + idx_local; |
8cb76d99 FW |
259 | |
260 | /* split */ | |
deac911c FW |
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; | |
8cb76d99 | 270 | |
deac911c FW |
271 | /* split the hits */ |
272 | new->hit = parent->hit; | |
1953287b | 273 | new->children_hit = parent->children_hit; |
f08c3154 | 274 | parent->children_hit = callchain_cumul_hits(new); |
deac911c FW |
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 */ | |
1b3a0e95 | 279 | if (idx_total < cursor->nr) { |
deac911c | 280 | parent->hit = 0; |
1b3a0e95 | 281 | add_child(parent, cursor, period); |
108553e1 | 282 | parent->children_hit += period; |
deac911c | 283 | } else { |
108553e1 | 284 | parent->hit = period; |
deac911c | 285 | } |
8cb76d99 FW |
286 | } |
287 | ||
288 | static int | |
1b3a0e95 FW |
289 | append_chain(struct callchain_node *root, |
290 | struct callchain_cursor *cursor, | |
291 | u64 period); | |
8cb76d99 | 292 | |
deac911c | 293 | static void |
1b3a0e95 FW |
294 | append_chain_children(struct callchain_node *root, |
295 | struct callchain_cursor *cursor, | |
296 | u64 period) | |
8cb76d99 FW |
297 | { |
298 | struct callchain_node *rnode; | |
299 | ||
300 | /* lookup in childrens */ | |
14f4654c | 301 | chain_for_each_child(rnode, root) { |
1b3a0e95 | 302 | unsigned int ret = append_chain(rnode, cursor, period); |
f37a291c | 303 | |
8cb76d99 | 304 | if (!ret) |
1953287b | 305 | goto inc_children_hit; |
8cb76d99 | 306 | } |
deac911c | 307 | /* nothing in children, add to the current node */ |
1b3a0e95 | 308 | add_child(root, cursor, period); |
e05b876c | 309 | |
1953287b | 310 | inc_children_hit: |
108553e1 | 311 | root->children_hit += period; |
8cb76d99 FW |
312 | } |
313 | ||
314 | static int | |
1b3a0e95 FW |
315 | append_chain(struct callchain_node *root, |
316 | struct callchain_cursor *cursor, | |
317 | u64 period) | |
8cb76d99 | 318 | { |
1b3a0e95 | 319 | struct callchain_cursor_node *curr_snap = cursor->curr; |
8cb76d99 | 320 | struct callchain_list *cnode; |
1b3a0e95 | 321 | u64 start = cursor->pos; |
8cb76d99 | 322 | bool found = false; |
1b3a0e95 | 323 | u64 matches; |
8cb76d99 | 324 | |
deac911c FW |
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 | */ | |
8cb76d99 | 330 | list_for_each_entry(cnode, &root->val, list) { |
1b3a0e95 | 331 | struct callchain_cursor_node *node; |
301fde27 FW |
332 | struct symbol *sym; |
333 | ||
1b3a0e95 FW |
334 | node = callchain_cursor_current(cursor); |
335 | if (!node) | |
deac911c | 336 | break; |
301fde27 | 337 | |
1b3a0e95 | 338 | sym = node->sym; |
301fde27 | 339 | |
b3c9ac08 ACM |
340 | if (cnode->ms.sym && sym) { |
341 | if (cnode->ms.sym->start != sym->start) | |
deac911c | 342 | break; |
1b3a0e95 | 343 | } else if (cnode->ip != node->ip) |
8cb76d99 | 344 | break; |
301fde27 | 345 | |
8cb76d99 FW |
346 | if (!found) |
347 | found = true; | |
1b3a0e95 FW |
348 | |
349 | callchain_cursor_advance(cursor); | |
8cb76d99 FW |
350 | } |
351 | ||
352 | /* matches not, relay on the parent */ | |
1b3a0e95 FW |
353 | if (!found) { |
354 | cursor->curr = curr_snap; | |
355 | cursor->pos = start; | |
8cb76d99 | 356 | return -1; |
1b3a0e95 FW |
357 | } |
358 | ||
359 | matches = cursor->pos - start; | |
8cb76d99 FW |
360 | |
361 | /* we match only a part of the node. Split it and add the new chain */ | |
1b3a0e95 FW |
362 | if (matches < root->val_nr) { |
363 | split_add_child(root, cursor, cnode, start, matches, period); | |
8cb76d99 FW |
364 | return 0; |
365 | } | |
366 | ||
367 | /* we match 100% of the path, increment the hit */ | |
1b3a0e95 | 368 | if (matches == root->val_nr && cursor->pos == cursor->nr) { |
108553e1 | 369 | root->hit += period; |
8cb76d99 FW |
370 | return 0; |
371 | } | |
372 | ||
deac911c | 373 | /* We match the node and still have a part remaining */ |
1b3a0e95 | 374 | append_chain_children(root, cursor, period); |
deac911c FW |
375 | |
376 | return 0; | |
8cb76d99 FW |
377 | } |
378 | ||
1b3a0e95 FW |
379 | int callchain_append(struct callchain_root *root, |
380 | struct callchain_cursor *cursor, | |
381 | u64 period) | |
8cb76d99 | 382 | { |
1b3a0e95 | 383 | if (!cursor->nr) |
301fde27 FW |
384 | return 0; |
385 | ||
1b3a0e95 | 386 | callchain_cursor_commit(cursor); |
301fde27 | 387 | |
1b3a0e95 | 388 | append_chain_children(&root->node, cursor, period); |
d2009c51 | 389 | |
1b3a0e95 FW |
390 | if (cursor->nr > root->max_depth) |
391 | root->max_depth = cursor->nr; | |
301fde27 FW |
392 | |
393 | return 0; | |
8cb76d99 | 394 | } |
612d4fd7 FW |
395 | |
396 | static int | |
1b3a0e95 FW |
397 | merge_chain_branch(struct callchain_cursor *cursor, |
398 | struct callchain_node *dst, struct callchain_node *src) | |
612d4fd7 | 399 | { |
1b3a0e95 | 400 | struct callchain_cursor_node **old_last = cursor->last; |
612d4fd7 FW |
401 | struct callchain_node *child, *next_child; |
402 | struct callchain_list *list, *next_list; | |
1b3a0e95 | 403 | int old_pos = cursor->nr; |
612d4fd7 FW |
404 | int err = 0; |
405 | ||
406 | list_for_each_entry_safe(list, next_list, &src->val, list) { | |
1b3a0e95 FW |
407 | callchain_cursor_append(cursor, list->ip, |
408 | list->ms.map, list->ms.sym); | |
612d4fd7 FW |
409 | list_del(&list->list); |
410 | free(list); | |
411 | } | |
412 | ||
1b3a0e95 FW |
413 | if (src->hit) { |
414 | callchain_cursor_commit(cursor); | |
415 | append_chain_children(dst, cursor, src->hit); | |
416 | } | |
612d4fd7 FW |
417 | |
418 | chain_for_each_child_safe(child, next_child, src) { | |
1b3a0e95 | 419 | err = merge_chain_branch(cursor, dst, child); |
612d4fd7 FW |
420 | if (err) |
421 | break; | |
422 | ||
529363b7 | 423 | list_del(&child->siblings); |
612d4fd7 FW |
424 | free(child); |
425 | } | |
426 | ||
1b3a0e95 FW |
427 | cursor->nr = old_pos; |
428 | cursor->last = old_last; | |
612d4fd7 FW |
429 | |
430 | return err; | |
431 | } | |
432 | ||
1b3a0e95 FW |
433 | int 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 | ||
439 | int callchain_cursor_append(struct callchain_cursor *cursor, | |
440 | u64 ip, struct map *map, struct symbol *sym) | |
612d4fd7 | 441 | { |
1b3a0e95 | 442 | struct callchain_cursor_node *node = *cursor->last; |
612d4fd7 | 443 | |
1b3a0e95 FW |
444 | if (!node) { |
445 | node = calloc(sizeof(*node), 1); | |
446 | if (!node) | |
447 | return -ENOMEM; | |
612d4fd7 | 448 | |
1b3a0e95 FW |
449 | *cursor->last = node; |
450 | } | |
612d4fd7 | 451 | |
1b3a0e95 FW |
452 | node->ip = ip; |
453 | node->map = map; | |
454 | node->sym = sym; | |
612d4fd7 | 455 | |
1b3a0e95 | 456 | cursor->nr++; |
612d4fd7 | 457 | |
1b3a0e95 FW |
458 | cursor->last = &node->next; |
459 | ||
460 | return 0; | |
612d4fd7 | 461 | } |