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