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