Loading...
1/*
2 * Copyright (C) 2009-2011, Frederic Weisbecker <fweisbec@gmail.com>
3 *
4 * Handle the callchains from the stream in an ad-hoc radix tree and then
5 * sort them in an rbtree.
6 *
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 *
10 */
11
12#include <stdlib.h>
13#include <stdio.h>
14#include <stdbool.h>
15#include <errno.h>
16#include <math.h>
17
18#include "util.h"
19#include "callchain.h"
20
21__thread struct callchain_cursor callchain_cursor;
22
23bool ip_callchain__valid(struct ip_callchain *chain,
24 const union perf_event *event)
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
31#define chain_for_each_child(child, parent) \
32 list_for_each_entry(child, &parent->children, siblings)
33
34#define chain_for_each_child_safe(child, next, parent) \
35 list_for_each_entry_safe(child, next, &parent->children, siblings)
36
37static void
38rb_insert_callchain(struct rb_root *root, struct callchain_node *chain,
39 enum chain_mode mode)
40{
41 struct rb_node **p = &root->rb_node;
42 struct rb_node *parent = NULL;
43 struct callchain_node *rnode;
44 u64 chain_cumul = callchain_cumul_hits(chain);
45
46 while (*p) {
47 u64 rnode_cumul;
48
49 parent = *p;
50 rnode = rb_entry(parent, struct callchain_node, rb_node);
51 rnode_cumul = callchain_cumul_hits(rnode);
52
53 switch (mode) {
54 case CHAIN_FLAT:
55 if (rnode->hit < chain->hit)
56 p = &(*p)->rb_left;
57 else
58 p = &(*p)->rb_right;
59 break;
60 case CHAIN_GRAPH_ABS: /* Falldown */
61 case CHAIN_GRAPH_REL:
62 if (rnode_cumul < chain_cumul)
63 p = &(*p)->rb_left;
64 else
65 p = &(*p)->rb_right;
66 break;
67 case CHAIN_NONE:
68 default:
69 break;
70 }
71 }
72
73 rb_link_node(&chain->rb_node, parent, p);
74 rb_insert_color(&chain->rb_node, root);
75}
76
77static 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
90/*
91 * Once we get every callchains from the stream, we can now
92 * sort them by hit
93 */
94static void
95sort_chain_flat(struct rb_root *rb_root, struct callchain_root *root,
96 u64 min_hit, struct callchain_param *param __used)
97{
98 __sort_chain_flat(rb_root, &root->node, min_hit);
99}
100
101static void __sort_chain_graph_abs(struct callchain_node *node,
102 u64 min_hit)
103{
104 struct callchain_node *child;
105
106 node->rb_root = RB_ROOT;
107
108 chain_for_each_child(child, node) {
109 __sort_chain_graph_abs(child, min_hit);
110 if (callchain_cumul_hits(child) >= min_hit)
111 rb_insert_callchain(&node->rb_root, child,
112 CHAIN_GRAPH_ABS);
113 }
114}
115
116static void
117sort_chain_graph_abs(struct rb_root *rb_root, struct callchain_root *chain_root,
118 u64 min_hit, struct callchain_param *param __used)
119{
120 __sort_chain_graph_abs(&chain_root->node, min_hit);
121 rb_root->rb_node = chain_root->node.rb_root.rb_node;
122}
123
124static void __sort_chain_graph_rel(struct callchain_node *node,
125 double min_percent)
126{
127 struct callchain_node *child;
128 u64 min_hit;
129
130 node->rb_root = RB_ROOT;
131 min_hit = ceil(node->children_hit * min_percent);
132
133 chain_for_each_child(child, node) {
134 __sort_chain_graph_rel(child, min_percent);
135 if (callchain_cumul_hits(child) >= min_hit)
136 rb_insert_callchain(&node->rb_root, child,
137 CHAIN_GRAPH_REL);
138 }
139}
140
141static void
142sort_chain_graph_rel(struct rb_root *rb_root, struct callchain_root *chain_root,
143 u64 min_hit __used, struct callchain_param *param)
144{
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;
147}
148
149int callchain_register_param(struct callchain_param *param)
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;
161 case CHAIN_NONE:
162 default:
163 return -1;
164 }
165 return 0;
166}
167
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 */
172static struct callchain_node *
173create_child(struct callchain_node *parent, bool inherit_children)
174{
175 struct callchain_node *new;
176
177 new = zalloc(sizeof(*new));
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);
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
192 chain_for_each_child(next, new)
193 next->parent = new;
194 }
195 list_add_tail(&new->siblings, &parent->children);
196
197 return new;
198}
199
200
201/*
202 * Fill the node with callchain values
203 */
204static void
205fill_node(struct callchain_node *node, struct callchain_cursor *cursor)
206{
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");
212
213 cursor_node = callchain_cursor_current(cursor);
214
215 while (cursor_node) {
216 struct callchain_list *call;
217
218 call = zalloc(sizeof(*call));
219 if (!call) {
220 perror("not enough memory for the code path tree");
221 return;
222 }
223 call->ip = cursor_node->ip;
224 call->ms.sym = cursor_node->sym;
225 call->ms.map = cursor_node->map;
226 list_add_tail(&call->list, &node->val);
227
228 callchain_cursor_advance(cursor);
229 cursor_node = callchain_cursor_current(cursor);
230 }
231}
232
233static void
234add_child(struct callchain_node *parent,
235 struct callchain_cursor *cursor,
236 u64 period)
237{
238 struct callchain_node *new;
239
240 new = create_child(parent, false);
241 fill_node(new, cursor);
242
243 new->children_hit = 0;
244 new->hit = period;
245}
246
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 */
252static void
253split_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)
257{
258 struct callchain_node *new;
259 struct list_head *old_tail;
260 unsigned int idx_total = idx_parents + idx_local;
261
262 /* split */
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;
272
273 /* split the hits */
274 new->hit = parent->hit;
275 new->children_hit = parent->children_hit;
276 parent->children_hit = callchain_cumul_hits(new);
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 */
281 if (idx_total < cursor->nr) {
282 parent->hit = 0;
283 add_child(parent, cursor, period);
284 parent->children_hit += period;
285 } else {
286 parent->hit = period;
287 }
288}
289
290static int
291append_chain(struct callchain_node *root,
292 struct callchain_cursor *cursor,
293 u64 period);
294
295static void
296append_chain_children(struct callchain_node *root,
297 struct callchain_cursor *cursor,
298 u64 period)
299{
300 struct callchain_node *rnode;
301
302 /* lookup in childrens */
303 chain_for_each_child(rnode, root) {
304 unsigned int ret = append_chain(rnode, cursor, period);
305
306 if (!ret)
307 goto inc_children_hit;
308 }
309 /* nothing in children, add to the current node */
310 add_child(root, cursor, period);
311
312inc_children_hit:
313 root->children_hit += period;
314}
315
316static int
317append_chain(struct callchain_node *root,
318 struct callchain_cursor *cursor,
319 u64 period)
320{
321 struct callchain_cursor_node *curr_snap = cursor->curr;
322 struct callchain_list *cnode;
323 u64 start = cursor->pos;
324 bool found = false;
325 u64 matches;
326
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 */
332 list_for_each_entry(cnode, &root->val, list) {
333 struct callchain_cursor_node *node;
334 struct symbol *sym;
335
336 node = callchain_cursor_current(cursor);
337 if (!node)
338 break;
339
340 sym = node->sym;
341
342 if (cnode->ms.sym && sym) {
343 if (cnode->ms.sym->start != sym->start)
344 break;
345 } else if (cnode->ip != node->ip)
346 break;
347
348 if (!found)
349 found = true;
350
351 callchain_cursor_advance(cursor);
352 }
353
354 /* matches not, relay on the parent */
355 if (!found) {
356 cursor->curr = curr_snap;
357 cursor->pos = start;
358 return -1;
359 }
360
361 matches = cursor->pos - start;
362
363 /* we match only a part of the node. Split it and add the new chain */
364 if (matches < root->val_nr) {
365 split_add_child(root, cursor, cnode, start, matches, period);
366 return 0;
367 }
368
369 /* we match 100% of the path, increment the hit */
370 if (matches == root->val_nr && cursor->pos == cursor->nr) {
371 root->hit += period;
372 return 0;
373 }
374
375 /* We match the node and still have a part remaining */
376 append_chain_children(root, cursor, period);
377
378 return 0;
379}
380
381int callchain_append(struct callchain_root *root,
382 struct callchain_cursor *cursor,
383 u64 period)
384{
385 if (!cursor->nr)
386 return 0;
387
388 callchain_cursor_commit(cursor);
389
390 append_chain_children(&root->node, cursor, period);
391
392 if (cursor->nr > root->max_depth)
393 root->max_depth = cursor->nr;
394
395 return 0;
396}
397
398static int
399merge_chain_branch(struct callchain_cursor *cursor,
400 struct callchain_node *dst, struct callchain_node *src)
401{
402 struct callchain_cursor_node **old_last = cursor->last;
403 struct callchain_node *child, *next_child;
404 struct callchain_list *list, *next_list;
405 int old_pos = cursor->nr;
406 int err = 0;
407
408 list_for_each_entry_safe(list, next_list, &src->val, list) {
409 callchain_cursor_append(cursor, list->ip,
410 list->ms.map, list->ms.sym);
411 list_del(&list->list);
412 free(list);
413 }
414
415 if (src->hit) {
416 callchain_cursor_commit(cursor);
417 append_chain_children(dst, cursor, src->hit);
418 }
419
420 chain_for_each_child_safe(child, next_child, src) {
421 err = merge_chain_branch(cursor, dst, child);
422 if (err)
423 break;
424
425 list_del(&child->siblings);
426 free(child);
427 }
428
429 cursor->nr = old_pos;
430 cursor->last = old_last;
431
432 return err;
433}
434
435int 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
441int callchain_cursor_append(struct callchain_cursor *cursor,
442 u64 ip, struct map *map, struct symbol *sym)
443{
444 struct callchain_cursor_node *node = *cursor->last;
445
446 if (!node) {
447 node = calloc(sizeof(*node), 1);
448 if (!node)
449 return -ENOMEM;
450
451 *cursor->last = node;
452 }
453
454 node->ip = ip;
455 node->map = map;
456 node->sym = sym;
457
458 cursor->nr++;
459
460 cursor->last = &node->next;
461
462 return 0;
463}
1/*
2 * Copyright (C) 2009-2011, Frederic Weisbecker <fweisbec@gmail.com>
3 *
4 * Handle the callchains from the stream in an ad-hoc radix tree and then
5 * sort them in an rbtree.
6 *
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 *
10 */
11
12#include <stdlib.h>
13#include <stdio.h>
14#include <stdbool.h>
15#include <errno.h>
16#include <math.h>
17
18#include "asm/bug.h"
19
20#include "hist.h"
21#include "util.h"
22#include "sort.h"
23#include "machine.h"
24#include "callchain.h"
25
26__thread struct callchain_cursor callchain_cursor;
27
28int parse_callchain_record_opt(const char *arg, struct callchain_param *param)
29{
30 return parse_callchain_record(arg, param);
31}
32
33static int parse_callchain_mode(const char *value)
34{
35 if (!strncmp(value, "graph", strlen(value))) {
36 callchain_param.mode = CHAIN_GRAPH_ABS;
37 return 0;
38 }
39 if (!strncmp(value, "flat", strlen(value))) {
40 callchain_param.mode = CHAIN_FLAT;
41 return 0;
42 }
43 if (!strncmp(value, "fractal", strlen(value))) {
44 callchain_param.mode = CHAIN_GRAPH_REL;
45 return 0;
46 }
47 if (!strncmp(value, "folded", strlen(value))) {
48 callchain_param.mode = CHAIN_FOLDED;
49 return 0;
50 }
51 return -1;
52}
53
54static int parse_callchain_order(const char *value)
55{
56 if (!strncmp(value, "caller", strlen(value))) {
57 callchain_param.order = ORDER_CALLER;
58 callchain_param.order_set = true;
59 return 0;
60 }
61 if (!strncmp(value, "callee", strlen(value))) {
62 callchain_param.order = ORDER_CALLEE;
63 callchain_param.order_set = true;
64 return 0;
65 }
66 return -1;
67}
68
69static int parse_callchain_sort_key(const char *value)
70{
71 if (!strncmp(value, "function", strlen(value))) {
72 callchain_param.key = CCKEY_FUNCTION;
73 return 0;
74 }
75 if (!strncmp(value, "address", strlen(value))) {
76 callchain_param.key = CCKEY_ADDRESS;
77 return 0;
78 }
79 if (!strncmp(value, "branch", strlen(value))) {
80 callchain_param.branch_callstack = 1;
81 return 0;
82 }
83 return -1;
84}
85
86static int parse_callchain_value(const char *value)
87{
88 if (!strncmp(value, "percent", strlen(value))) {
89 callchain_param.value = CCVAL_PERCENT;
90 return 0;
91 }
92 if (!strncmp(value, "period", strlen(value))) {
93 callchain_param.value = CCVAL_PERIOD;
94 return 0;
95 }
96 if (!strncmp(value, "count", strlen(value))) {
97 callchain_param.value = CCVAL_COUNT;
98 return 0;
99 }
100 return -1;
101}
102
103static int
104__parse_callchain_report_opt(const char *arg, bool allow_record_opt)
105{
106 char *tok;
107 char *endptr;
108 bool minpcnt_set = false;
109 bool record_opt_set = false;
110 bool try_stack_size = false;
111
112 symbol_conf.use_callchain = true;
113
114 if (!arg)
115 return 0;
116
117 while ((tok = strtok((char *)arg, ",")) != NULL) {
118 if (!strncmp(tok, "none", strlen(tok))) {
119 callchain_param.mode = CHAIN_NONE;
120 symbol_conf.use_callchain = false;
121 return 0;
122 }
123
124 if (!parse_callchain_mode(tok) ||
125 !parse_callchain_order(tok) ||
126 !parse_callchain_sort_key(tok) ||
127 !parse_callchain_value(tok)) {
128 /* parsing ok - move on to the next */
129 try_stack_size = false;
130 goto next;
131 } else if (allow_record_opt && !record_opt_set) {
132 if (parse_callchain_record(tok, &callchain_param))
133 goto try_numbers;
134
135 /* assume that number followed by 'dwarf' is stack size */
136 if (callchain_param.record_mode == CALLCHAIN_DWARF)
137 try_stack_size = true;
138
139 record_opt_set = true;
140 goto next;
141 }
142
143try_numbers:
144 if (try_stack_size) {
145 unsigned long size = 0;
146
147 if (get_stack_size(tok, &size) < 0)
148 return -1;
149 callchain_param.dump_size = size;
150 try_stack_size = false;
151 } else if (!minpcnt_set) {
152 /* try to get the min percent */
153 callchain_param.min_percent = strtod(tok, &endptr);
154 if (tok == endptr)
155 return -1;
156 minpcnt_set = true;
157 } else {
158 /* try print limit at last */
159 callchain_param.print_limit = strtoul(tok, &endptr, 0);
160 if (tok == endptr)
161 return -1;
162 }
163next:
164 arg = NULL;
165 }
166
167 if (callchain_register_param(&callchain_param) < 0) {
168 pr_err("Can't register callchain params\n");
169 return -1;
170 }
171 return 0;
172}
173
174int parse_callchain_report_opt(const char *arg)
175{
176 return __parse_callchain_report_opt(arg, false);
177}
178
179int parse_callchain_top_opt(const char *arg)
180{
181 return __parse_callchain_report_opt(arg, true);
182}
183
184int perf_callchain_config(const char *var, const char *value)
185{
186 char *endptr;
187
188 if (prefixcmp(var, "call-graph."))
189 return 0;
190 var += sizeof("call-graph.") - 1;
191
192 if (!strcmp(var, "record-mode"))
193 return parse_callchain_record_opt(value, &callchain_param);
194#ifdef HAVE_DWARF_UNWIND_SUPPORT
195 if (!strcmp(var, "dump-size")) {
196 unsigned long size = 0;
197 int ret;
198
199 ret = get_stack_size(value, &size);
200 callchain_param.dump_size = size;
201
202 return ret;
203 }
204#endif
205 if (!strcmp(var, "print-type"))
206 return parse_callchain_mode(value);
207 if (!strcmp(var, "order"))
208 return parse_callchain_order(value);
209 if (!strcmp(var, "sort-key"))
210 return parse_callchain_sort_key(value);
211 if (!strcmp(var, "threshold")) {
212 callchain_param.min_percent = strtod(value, &endptr);
213 if (value == endptr)
214 return -1;
215 }
216 if (!strcmp(var, "print-limit")) {
217 callchain_param.print_limit = strtod(value, &endptr);
218 if (value == endptr)
219 return -1;
220 }
221
222 return 0;
223}
224
225static void
226rb_insert_callchain(struct rb_root *root, struct callchain_node *chain,
227 enum chain_mode mode)
228{
229 struct rb_node **p = &root->rb_node;
230 struct rb_node *parent = NULL;
231 struct callchain_node *rnode;
232 u64 chain_cumul = callchain_cumul_hits(chain);
233
234 while (*p) {
235 u64 rnode_cumul;
236
237 parent = *p;
238 rnode = rb_entry(parent, struct callchain_node, rb_node);
239 rnode_cumul = callchain_cumul_hits(rnode);
240
241 switch (mode) {
242 case CHAIN_FLAT:
243 case CHAIN_FOLDED:
244 if (rnode->hit < chain->hit)
245 p = &(*p)->rb_left;
246 else
247 p = &(*p)->rb_right;
248 break;
249 case CHAIN_GRAPH_ABS: /* Falldown */
250 case CHAIN_GRAPH_REL:
251 if (rnode_cumul < chain_cumul)
252 p = &(*p)->rb_left;
253 else
254 p = &(*p)->rb_right;
255 break;
256 case CHAIN_NONE:
257 default:
258 break;
259 }
260 }
261
262 rb_link_node(&chain->rb_node, parent, p);
263 rb_insert_color(&chain->rb_node, root);
264}
265
266static void
267__sort_chain_flat(struct rb_root *rb_root, struct callchain_node *node,
268 u64 min_hit)
269{
270 struct rb_node *n;
271 struct callchain_node *child;
272
273 n = rb_first(&node->rb_root_in);
274 while (n) {
275 child = rb_entry(n, struct callchain_node, rb_node_in);
276 n = rb_next(n);
277
278 __sort_chain_flat(rb_root, child, min_hit);
279 }
280
281 if (node->hit && node->hit >= min_hit)
282 rb_insert_callchain(rb_root, node, CHAIN_FLAT);
283}
284
285/*
286 * Once we get every callchains from the stream, we can now
287 * sort them by hit
288 */
289static void
290sort_chain_flat(struct rb_root *rb_root, struct callchain_root *root,
291 u64 min_hit, struct callchain_param *param __maybe_unused)
292{
293 *rb_root = RB_ROOT;
294 __sort_chain_flat(rb_root, &root->node, min_hit);
295}
296
297static void __sort_chain_graph_abs(struct callchain_node *node,
298 u64 min_hit)
299{
300 struct rb_node *n;
301 struct callchain_node *child;
302
303 node->rb_root = RB_ROOT;
304 n = rb_first(&node->rb_root_in);
305
306 while (n) {
307 child = rb_entry(n, struct callchain_node, rb_node_in);
308 n = rb_next(n);
309
310 __sort_chain_graph_abs(child, min_hit);
311 if (callchain_cumul_hits(child) >= min_hit)
312 rb_insert_callchain(&node->rb_root, child,
313 CHAIN_GRAPH_ABS);
314 }
315}
316
317static void
318sort_chain_graph_abs(struct rb_root *rb_root, struct callchain_root *chain_root,
319 u64 min_hit, struct callchain_param *param __maybe_unused)
320{
321 __sort_chain_graph_abs(&chain_root->node, min_hit);
322 rb_root->rb_node = chain_root->node.rb_root.rb_node;
323}
324
325static void __sort_chain_graph_rel(struct callchain_node *node,
326 double min_percent)
327{
328 struct rb_node *n;
329 struct callchain_node *child;
330 u64 min_hit;
331
332 node->rb_root = RB_ROOT;
333 min_hit = ceil(node->children_hit * min_percent);
334
335 n = rb_first(&node->rb_root_in);
336 while (n) {
337 child = rb_entry(n, struct callchain_node, rb_node_in);
338 n = rb_next(n);
339
340 __sort_chain_graph_rel(child, min_percent);
341 if (callchain_cumul_hits(child) >= min_hit)
342 rb_insert_callchain(&node->rb_root, child,
343 CHAIN_GRAPH_REL);
344 }
345}
346
347static void
348sort_chain_graph_rel(struct rb_root *rb_root, struct callchain_root *chain_root,
349 u64 min_hit __maybe_unused, struct callchain_param *param)
350{
351 __sort_chain_graph_rel(&chain_root->node, param->min_percent / 100.0);
352 rb_root->rb_node = chain_root->node.rb_root.rb_node;
353}
354
355int callchain_register_param(struct callchain_param *param)
356{
357 switch (param->mode) {
358 case CHAIN_GRAPH_ABS:
359 param->sort = sort_chain_graph_abs;
360 break;
361 case CHAIN_GRAPH_REL:
362 param->sort = sort_chain_graph_rel;
363 break;
364 case CHAIN_FLAT:
365 case CHAIN_FOLDED:
366 param->sort = sort_chain_flat;
367 break;
368 case CHAIN_NONE:
369 default:
370 return -1;
371 }
372 return 0;
373}
374
375/*
376 * Create a child for a parent. If inherit_children, then the new child
377 * will become the new parent of it's parent children
378 */
379static struct callchain_node *
380create_child(struct callchain_node *parent, bool inherit_children)
381{
382 struct callchain_node *new;
383
384 new = zalloc(sizeof(*new));
385 if (!new) {
386 perror("not enough memory to create child for code path tree");
387 return NULL;
388 }
389 new->parent = parent;
390 INIT_LIST_HEAD(&new->val);
391 INIT_LIST_HEAD(&new->parent_val);
392
393 if (inherit_children) {
394 struct rb_node *n;
395 struct callchain_node *child;
396
397 new->rb_root_in = parent->rb_root_in;
398 parent->rb_root_in = RB_ROOT;
399
400 n = rb_first(&new->rb_root_in);
401 while (n) {
402 child = rb_entry(n, struct callchain_node, rb_node_in);
403 child->parent = new;
404 n = rb_next(n);
405 }
406
407 /* make it the first child */
408 rb_link_node(&new->rb_node_in, NULL, &parent->rb_root_in.rb_node);
409 rb_insert_color(&new->rb_node_in, &parent->rb_root_in);
410 }
411
412 return new;
413}
414
415
416/*
417 * Fill the node with callchain values
418 */
419static int
420fill_node(struct callchain_node *node, struct callchain_cursor *cursor)
421{
422 struct callchain_cursor_node *cursor_node;
423
424 node->val_nr = cursor->nr - cursor->pos;
425 if (!node->val_nr)
426 pr_warning("Warning: empty node in callchain tree\n");
427
428 cursor_node = callchain_cursor_current(cursor);
429
430 while (cursor_node) {
431 struct callchain_list *call;
432
433 call = zalloc(sizeof(*call));
434 if (!call) {
435 perror("not enough memory for the code path tree");
436 return -1;
437 }
438 call->ip = cursor_node->ip;
439 call->ms.sym = cursor_node->sym;
440 call->ms.map = cursor_node->map;
441 list_add_tail(&call->list, &node->val);
442
443 callchain_cursor_advance(cursor);
444 cursor_node = callchain_cursor_current(cursor);
445 }
446 return 0;
447}
448
449static struct callchain_node *
450add_child(struct callchain_node *parent,
451 struct callchain_cursor *cursor,
452 u64 period)
453{
454 struct callchain_node *new;
455
456 new = create_child(parent, false);
457 if (new == NULL)
458 return NULL;
459
460 if (fill_node(new, cursor) < 0) {
461 struct callchain_list *call, *tmp;
462
463 list_for_each_entry_safe(call, tmp, &new->val, list) {
464 list_del(&call->list);
465 free(call);
466 }
467 free(new);
468 return NULL;
469 }
470
471 new->children_hit = 0;
472 new->hit = period;
473 new->children_count = 0;
474 new->count = 1;
475 return new;
476}
477
478enum match_result {
479 MATCH_ERROR = -1,
480 MATCH_EQ,
481 MATCH_LT,
482 MATCH_GT,
483};
484
485static enum match_result match_chain(struct callchain_cursor_node *node,
486 struct callchain_list *cnode)
487{
488 struct symbol *sym = node->sym;
489 u64 left, right;
490
491 if (cnode->ms.sym && sym &&
492 callchain_param.key == CCKEY_FUNCTION) {
493 left = cnode->ms.sym->start;
494 right = sym->start;
495 } else {
496 left = cnode->ip;
497 right = node->ip;
498 }
499
500 if (left == right)
501 return MATCH_EQ;
502
503 return left > right ? MATCH_GT : MATCH_LT;
504}
505
506/*
507 * Split the parent in two parts (a new child is created) and
508 * give a part of its callchain to the created child.
509 * Then create another child to host the given callchain of new branch
510 */
511static int
512split_add_child(struct callchain_node *parent,
513 struct callchain_cursor *cursor,
514 struct callchain_list *to_split,
515 u64 idx_parents, u64 idx_local, u64 period)
516{
517 struct callchain_node *new;
518 struct list_head *old_tail;
519 unsigned int idx_total = idx_parents + idx_local;
520
521 /* split */
522 new = create_child(parent, true);
523 if (new == NULL)
524 return -1;
525
526 /* split the callchain and move a part to the new child */
527 old_tail = parent->val.prev;
528 list_del_range(&to_split->list, old_tail);
529 new->val.next = &to_split->list;
530 new->val.prev = old_tail;
531 to_split->list.prev = &new->val;
532 old_tail->next = &new->val;
533
534 /* split the hits */
535 new->hit = parent->hit;
536 new->children_hit = parent->children_hit;
537 parent->children_hit = callchain_cumul_hits(new);
538 new->val_nr = parent->val_nr - idx_local;
539 parent->val_nr = idx_local;
540 new->count = parent->count;
541 new->children_count = parent->children_count;
542 parent->children_count = callchain_cumul_counts(new);
543
544 /* create a new child for the new branch if any */
545 if (idx_total < cursor->nr) {
546 struct callchain_node *first;
547 struct callchain_list *cnode;
548 struct callchain_cursor_node *node;
549 struct rb_node *p, **pp;
550
551 parent->hit = 0;
552 parent->children_hit += period;
553 parent->count = 0;
554 parent->children_count += 1;
555
556 node = callchain_cursor_current(cursor);
557 new = add_child(parent, cursor, period);
558 if (new == NULL)
559 return -1;
560
561 /*
562 * This is second child since we moved parent's children
563 * to new (first) child above.
564 */
565 p = parent->rb_root_in.rb_node;
566 first = rb_entry(p, struct callchain_node, rb_node_in);
567 cnode = list_first_entry(&first->val, struct callchain_list,
568 list);
569
570 if (match_chain(node, cnode) == MATCH_LT)
571 pp = &p->rb_left;
572 else
573 pp = &p->rb_right;
574
575 rb_link_node(&new->rb_node_in, p, pp);
576 rb_insert_color(&new->rb_node_in, &parent->rb_root_in);
577 } else {
578 parent->hit = period;
579 parent->count = 1;
580 }
581 return 0;
582}
583
584static enum match_result
585append_chain(struct callchain_node *root,
586 struct callchain_cursor *cursor,
587 u64 period);
588
589static int
590append_chain_children(struct callchain_node *root,
591 struct callchain_cursor *cursor,
592 u64 period)
593{
594 struct callchain_node *rnode;
595 struct callchain_cursor_node *node;
596 struct rb_node **p = &root->rb_root_in.rb_node;
597 struct rb_node *parent = NULL;
598
599 node = callchain_cursor_current(cursor);
600 if (!node)
601 return -1;
602
603 /* lookup in childrens */
604 while (*p) {
605 enum match_result ret;
606
607 parent = *p;
608 rnode = rb_entry(parent, struct callchain_node, rb_node_in);
609
610 /* If at least first entry matches, rely to children */
611 ret = append_chain(rnode, cursor, period);
612 if (ret == MATCH_EQ)
613 goto inc_children_hit;
614 if (ret == MATCH_ERROR)
615 return -1;
616
617 if (ret == MATCH_LT)
618 p = &parent->rb_left;
619 else
620 p = &parent->rb_right;
621 }
622 /* nothing in children, add to the current node */
623 rnode = add_child(root, cursor, period);
624 if (rnode == NULL)
625 return -1;
626
627 rb_link_node(&rnode->rb_node_in, parent, p);
628 rb_insert_color(&rnode->rb_node_in, &root->rb_root_in);
629
630inc_children_hit:
631 root->children_hit += period;
632 root->children_count++;
633 return 0;
634}
635
636static enum match_result
637append_chain(struct callchain_node *root,
638 struct callchain_cursor *cursor,
639 u64 period)
640{
641 struct callchain_list *cnode;
642 u64 start = cursor->pos;
643 bool found = false;
644 u64 matches;
645 enum match_result cmp = MATCH_ERROR;
646
647 /*
648 * Lookup in the current node
649 * If we have a symbol, then compare the start to match
650 * anywhere inside a function, unless function
651 * mode is disabled.
652 */
653 list_for_each_entry(cnode, &root->val, list) {
654 struct callchain_cursor_node *node;
655
656 node = callchain_cursor_current(cursor);
657 if (!node)
658 break;
659
660 cmp = match_chain(node, cnode);
661 if (cmp != MATCH_EQ)
662 break;
663
664 found = true;
665
666 callchain_cursor_advance(cursor);
667 }
668
669 /* matches not, relay no the parent */
670 if (!found) {
671 WARN_ONCE(cmp == MATCH_ERROR, "Chain comparison error\n");
672 return cmp;
673 }
674
675 matches = cursor->pos - start;
676
677 /* we match only a part of the node. Split it and add the new chain */
678 if (matches < root->val_nr) {
679 if (split_add_child(root, cursor, cnode, start, matches,
680 period) < 0)
681 return MATCH_ERROR;
682
683 return MATCH_EQ;
684 }
685
686 /* we match 100% of the path, increment the hit */
687 if (matches == root->val_nr && cursor->pos == cursor->nr) {
688 root->hit += period;
689 root->count++;
690 return MATCH_EQ;
691 }
692
693 /* We match the node and still have a part remaining */
694 if (append_chain_children(root, cursor, period) < 0)
695 return MATCH_ERROR;
696
697 return MATCH_EQ;
698}
699
700int callchain_append(struct callchain_root *root,
701 struct callchain_cursor *cursor,
702 u64 period)
703{
704 if (!cursor->nr)
705 return 0;
706
707 callchain_cursor_commit(cursor);
708
709 if (append_chain_children(&root->node, cursor, period) < 0)
710 return -1;
711
712 if (cursor->nr > root->max_depth)
713 root->max_depth = cursor->nr;
714
715 return 0;
716}
717
718static int
719merge_chain_branch(struct callchain_cursor *cursor,
720 struct callchain_node *dst, struct callchain_node *src)
721{
722 struct callchain_cursor_node **old_last = cursor->last;
723 struct callchain_node *child;
724 struct callchain_list *list, *next_list;
725 struct rb_node *n;
726 int old_pos = cursor->nr;
727 int err = 0;
728
729 list_for_each_entry_safe(list, next_list, &src->val, list) {
730 callchain_cursor_append(cursor, list->ip,
731 list->ms.map, list->ms.sym);
732 list_del(&list->list);
733 free(list);
734 }
735
736 if (src->hit) {
737 callchain_cursor_commit(cursor);
738 if (append_chain_children(dst, cursor, src->hit) < 0)
739 return -1;
740 }
741
742 n = rb_first(&src->rb_root_in);
743 while (n) {
744 child = container_of(n, struct callchain_node, rb_node_in);
745 n = rb_next(n);
746 rb_erase(&child->rb_node_in, &src->rb_root_in);
747
748 err = merge_chain_branch(cursor, dst, child);
749 if (err)
750 break;
751
752 free(child);
753 }
754
755 cursor->nr = old_pos;
756 cursor->last = old_last;
757
758 return err;
759}
760
761int callchain_merge(struct callchain_cursor *cursor,
762 struct callchain_root *dst, struct callchain_root *src)
763{
764 return merge_chain_branch(cursor, &dst->node, &src->node);
765}
766
767int callchain_cursor_append(struct callchain_cursor *cursor,
768 u64 ip, struct map *map, struct symbol *sym)
769{
770 struct callchain_cursor_node *node = *cursor->last;
771
772 if (!node) {
773 node = calloc(1, sizeof(*node));
774 if (!node)
775 return -ENOMEM;
776
777 *cursor->last = node;
778 }
779
780 node->ip = ip;
781 node->map = map;
782 node->sym = sym;
783
784 cursor->nr++;
785
786 cursor->last = &node->next;
787
788 return 0;
789}
790
791int sample__resolve_callchain(struct perf_sample *sample, struct symbol **parent,
792 struct perf_evsel *evsel, struct addr_location *al,
793 int max_stack)
794{
795 if (sample->callchain == NULL)
796 return 0;
797
798 if (symbol_conf.use_callchain || symbol_conf.cumulate_callchain ||
799 sort__has_parent) {
800 return thread__resolve_callchain(al->thread, evsel, sample,
801 parent, al, max_stack);
802 }
803 return 0;
804}
805
806int hist_entry__append_callchain(struct hist_entry *he, struct perf_sample *sample)
807{
808 if (!symbol_conf.use_callchain || sample->callchain == NULL)
809 return 0;
810 return callchain_append(he->callchain, &callchain_cursor, sample->period);
811}
812
813int fill_callchain_info(struct addr_location *al, struct callchain_cursor_node *node,
814 bool hide_unresolved)
815{
816 al->map = node->map;
817 al->sym = node->sym;
818 if (node->map)
819 al->addr = node->map->map_ip(node->map, node->ip);
820 else
821 al->addr = node->ip;
822
823 if (al->sym == NULL) {
824 if (hide_unresolved)
825 return 0;
826 if (al->map == NULL)
827 goto out;
828 }
829
830 if (al->map->groups == &al->machine->kmaps) {
831 if (machine__is_host(al->machine)) {
832 al->cpumode = PERF_RECORD_MISC_KERNEL;
833 al->level = 'k';
834 } else {
835 al->cpumode = PERF_RECORD_MISC_GUEST_KERNEL;
836 al->level = 'g';
837 }
838 } else {
839 if (machine__is_host(al->machine)) {
840 al->cpumode = PERF_RECORD_MISC_USER;
841 al->level = '.';
842 } else if (perf_guest) {
843 al->cpumode = PERF_RECORD_MISC_GUEST_USER;
844 al->level = 'u';
845 } else {
846 al->cpumode = PERF_RECORD_MISC_HYPERVISOR;
847 al->level = 'H';
848 }
849 }
850
851out:
852 return 1;
853}
854
855char *callchain_list__sym_name(struct callchain_list *cl,
856 char *bf, size_t bfsize, bool show_dso)
857{
858 int printed;
859
860 if (cl->ms.sym) {
861 if (callchain_param.key == CCKEY_ADDRESS &&
862 cl->ms.map && !cl->srcline)
863 cl->srcline = get_srcline(cl->ms.map->dso,
864 map__rip_2objdump(cl->ms.map,
865 cl->ip),
866 cl->ms.sym, false);
867 if (cl->srcline)
868 printed = scnprintf(bf, bfsize, "%s %s",
869 cl->ms.sym->name, cl->srcline);
870 else
871 printed = scnprintf(bf, bfsize, "%s", cl->ms.sym->name);
872 } else
873 printed = scnprintf(bf, bfsize, "%#" PRIx64, cl->ip);
874
875 if (show_dso)
876 scnprintf(bf + printed, bfsize - printed, " %s",
877 cl->ms.map ?
878 cl->ms.map->dso->short_name :
879 "unknown");
880
881 return bf;
882}
883
884char *callchain_node__scnprintf_value(struct callchain_node *node,
885 char *bf, size_t bfsize, u64 total)
886{
887 double percent = 0.0;
888 u64 period = callchain_cumul_hits(node);
889 unsigned count = callchain_cumul_counts(node);
890
891 if (callchain_param.mode == CHAIN_FOLDED) {
892 period = node->hit;
893 count = node->count;
894 }
895
896 switch (callchain_param.value) {
897 case CCVAL_PERIOD:
898 scnprintf(bf, bfsize, "%"PRIu64, period);
899 break;
900 case CCVAL_COUNT:
901 scnprintf(bf, bfsize, "%u", count);
902 break;
903 case CCVAL_PERCENT:
904 default:
905 if (total)
906 percent = period * 100.0 / total;
907 scnprintf(bf, bfsize, "%.2f%%", percent);
908 break;
909 }
910 return bf;
911}
912
913int callchain_node__fprintf_value(struct callchain_node *node,
914 FILE *fp, u64 total)
915{
916 double percent = 0.0;
917 u64 period = callchain_cumul_hits(node);
918 unsigned count = callchain_cumul_counts(node);
919
920 if (callchain_param.mode == CHAIN_FOLDED) {
921 period = node->hit;
922 count = node->count;
923 }
924
925 switch (callchain_param.value) {
926 case CCVAL_PERIOD:
927 return fprintf(fp, "%"PRIu64, period);
928 case CCVAL_COUNT:
929 return fprintf(fp, "%u", count);
930 case CCVAL_PERCENT:
931 default:
932 if (total)
933 percent = period * 100.0 / total;
934 return percent_color_fprintf(fp, "%.2f%%", percent);
935 }
936 return 0;
937}
938
939static void free_callchain_node(struct callchain_node *node)
940{
941 struct callchain_list *list, *tmp;
942 struct callchain_node *child;
943 struct rb_node *n;
944
945 list_for_each_entry_safe(list, tmp, &node->parent_val, list) {
946 list_del(&list->list);
947 free(list);
948 }
949
950 list_for_each_entry_safe(list, tmp, &node->val, list) {
951 list_del(&list->list);
952 free(list);
953 }
954
955 n = rb_first(&node->rb_root_in);
956 while (n) {
957 child = container_of(n, struct callchain_node, rb_node_in);
958 n = rb_next(n);
959 rb_erase(&child->rb_node_in, &node->rb_root_in);
960
961 free_callchain_node(child);
962 free(child);
963 }
964}
965
966void free_callchain(struct callchain_root *root)
967{
968 if (!symbol_conf.use_callchain)
969 return;
970
971 free_callchain_node(&root->node);
972}
973
974static u64 decay_callchain_node(struct callchain_node *node)
975{
976 struct callchain_node *child;
977 struct rb_node *n;
978 u64 child_hits = 0;
979
980 n = rb_first(&node->rb_root_in);
981 while (n) {
982 child = container_of(n, struct callchain_node, rb_node_in);
983
984 child_hits += decay_callchain_node(child);
985 n = rb_next(n);
986 }
987
988 node->hit = (node->hit * 7) / 8;
989 node->children_hit = child_hits;
990
991 return node->hit;
992}
993
994void decay_callchain(struct callchain_root *root)
995{
996 if (!symbol_conf.use_callchain)
997 return;
998
999 decay_callchain_node(&root->node);
1000}
1001
1002int callchain_node__make_parent_list(struct callchain_node *node)
1003{
1004 struct callchain_node *parent = node->parent;
1005 struct callchain_list *chain, *new;
1006 LIST_HEAD(head);
1007
1008 while (parent) {
1009 list_for_each_entry_reverse(chain, &parent->val, list) {
1010 new = malloc(sizeof(*new));
1011 if (new == NULL)
1012 goto out;
1013 *new = *chain;
1014 new->has_children = false;
1015 list_add_tail(&new->list, &head);
1016 }
1017 parent = parent->parent;
1018 }
1019
1020 list_for_each_entry_safe_reverse(chain, new, &head, list)
1021 list_move_tail(&chain->list, &node->parent_val);
1022
1023 if (!list_empty(&node->parent_val)) {
1024 chain = list_first_entry(&node->parent_val, struct callchain_list, list);
1025 chain->has_children = rb_prev(&node->rb_node) || rb_next(&node->rb_node);
1026
1027 chain = list_first_entry(&node->val, struct callchain_list, list);
1028 chain->has_children = false;
1029 }
1030 return 0;
1031
1032out:
1033 list_for_each_entry_safe(chain, new, &head, list) {
1034 list_del(&chain->list);
1035 free(chain);
1036 }
1037 return -ENOMEM;
1038}