Commit | Line | Data |
---|---|---|
3d1d07ec | 1 | #include "hist.h" |
4e4f06e4 ACM |
2 | #include "session.h" |
3 | #include "sort.h" | |
3d1d07ec JK |
4 | |
5 | struct callchain_param callchain_param = { | |
6 | .mode = CHAIN_GRAPH_REL, | |
7 | .min_percent = 0.5 | |
8 | }; | |
9 | ||
3d1d07ec JK |
10 | /* |
11 | * histogram, sorted on item, collects counts | |
12 | */ | |
13 | ||
4e4f06e4 ACM |
14 | struct hist_entry *__perf_session__add_hist_entry(struct perf_session *self, |
15 | struct addr_location *al, | |
16 | struct symbol *sym_parent, | |
17 | u64 count, bool *hit) | |
9735abf1 | 18 | { |
4e4f06e4 | 19 | struct rb_node **p = &self->hists.rb_node; |
9735abf1 ACM |
20 | struct rb_node *parent = NULL; |
21 | struct hist_entry *he; | |
22 | struct hist_entry entry = { | |
1ed091c4 ACM |
23 | .thread = al->thread, |
24 | .map = al->map, | |
25 | .sym = al->sym, | |
26 | .ip = al->addr, | |
27 | .level = al->level, | |
9735abf1 ACM |
28 | .count = count, |
29 | .parent = sym_parent, | |
30 | }; | |
31 | int cmp; | |
32 | ||
33 | while (*p != NULL) { | |
34 | parent = *p; | |
35 | he = rb_entry(parent, struct hist_entry, rb_node); | |
36 | ||
37 | cmp = hist_entry__cmp(&entry, he); | |
38 | ||
39 | if (!cmp) { | |
40 | *hit = true; | |
41 | return he; | |
42 | } | |
43 | ||
44 | if (cmp < 0) | |
45 | p = &(*p)->rb_left; | |
46 | else | |
47 | p = &(*p)->rb_right; | |
48 | } | |
49 | ||
50 | he = malloc(sizeof(*he)); | |
51 | if (!he) | |
52 | return NULL; | |
53 | *he = entry; | |
54 | rb_link_node(&he->rb_node, parent, p); | |
4e4f06e4 | 55 | rb_insert_color(&he->rb_node, &self->hists); |
9735abf1 ACM |
56 | *hit = false; |
57 | return he; | |
58 | } | |
59 | ||
3d1d07ec JK |
60 | int64_t |
61 | hist_entry__cmp(struct hist_entry *left, struct hist_entry *right) | |
62 | { | |
63 | struct sort_entry *se; | |
64 | int64_t cmp = 0; | |
65 | ||
66 | list_for_each_entry(se, &hist_entry__sort_list, list) { | |
67 | cmp = se->cmp(left, right); | |
68 | if (cmp) | |
69 | break; | |
70 | } | |
71 | ||
72 | return cmp; | |
73 | } | |
74 | ||
75 | int64_t | |
76 | hist_entry__collapse(struct hist_entry *left, struct hist_entry *right) | |
77 | { | |
78 | struct sort_entry *se; | |
79 | int64_t cmp = 0; | |
80 | ||
81 | list_for_each_entry(se, &hist_entry__sort_list, list) { | |
82 | int64_t (*f)(struct hist_entry *, struct hist_entry *); | |
83 | ||
84 | f = se->collapse ?: se->cmp; | |
85 | ||
86 | cmp = f(left, right); | |
87 | if (cmp) | |
88 | break; | |
89 | } | |
90 | ||
91 | return cmp; | |
92 | } | |
93 | ||
94 | void hist_entry__free(struct hist_entry *he) | |
95 | { | |
96 | free(he); | |
97 | } | |
98 | ||
99 | /* | |
100 | * collapse the histogram | |
101 | */ | |
102 | ||
b9bf0892 | 103 | static void collapse__insert_entry(struct rb_root *root, struct hist_entry *he) |
3d1d07ec | 104 | { |
b9bf0892 | 105 | struct rb_node **p = &root->rb_node; |
3d1d07ec JK |
106 | struct rb_node *parent = NULL; |
107 | struct hist_entry *iter; | |
108 | int64_t cmp; | |
109 | ||
110 | while (*p != NULL) { | |
111 | parent = *p; | |
112 | iter = rb_entry(parent, struct hist_entry, rb_node); | |
113 | ||
114 | cmp = hist_entry__collapse(iter, he); | |
115 | ||
116 | if (!cmp) { | |
117 | iter->count += he->count; | |
118 | hist_entry__free(he); | |
119 | return; | |
120 | } | |
121 | ||
122 | if (cmp < 0) | |
123 | p = &(*p)->rb_left; | |
124 | else | |
125 | p = &(*p)->rb_right; | |
126 | } | |
127 | ||
128 | rb_link_node(&he->rb_node, parent, p); | |
b9bf0892 | 129 | rb_insert_color(&he->rb_node, root); |
3d1d07ec JK |
130 | } |
131 | ||
4e4f06e4 | 132 | void perf_session__collapse_resort(struct perf_session *self) |
3d1d07ec | 133 | { |
b9bf0892 | 134 | struct rb_root tmp; |
3d1d07ec JK |
135 | struct rb_node *next; |
136 | struct hist_entry *n; | |
137 | ||
138 | if (!sort__need_collapse) | |
139 | return; | |
140 | ||
b9bf0892 | 141 | tmp = RB_ROOT; |
4e4f06e4 | 142 | next = rb_first(&self->hists); |
b9bf0892 | 143 | |
3d1d07ec JK |
144 | while (next) { |
145 | n = rb_entry(next, struct hist_entry, rb_node); | |
146 | next = rb_next(&n->rb_node); | |
147 | ||
4e4f06e4 | 148 | rb_erase(&n->rb_node, &self->hists); |
b9bf0892 | 149 | collapse__insert_entry(&tmp, n); |
3d1d07ec | 150 | } |
b9bf0892 | 151 | |
4e4f06e4 | 152 | self->hists = tmp; |
3d1d07ec JK |
153 | } |
154 | ||
155 | /* | |
156 | * reverse the map, sort on count. | |
157 | */ | |
158 | ||
d599db3f | 159 | static void perf_session__insert_output_hist_entry(struct rb_root *root, |
4e4f06e4 ACM |
160 | struct hist_entry *he, |
161 | u64 min_callchain_hits) | |
3d1d07ec | 162 | { |
b9bf0892 | 163 | struct rb_node **p = &root->rb_node; |
3d1d07ec JK |
164 | struct rb_node *parent = NULL; |
165 | struct hist_entry *iter; | |
166 | ||
d599db3f | 167 | if (symbol_conf.use_callchain) |
3d1d07ec JK |
168 | callchain_param.sort(&he->sorted_chain, &he->callchain, |
169 | min_callchain_hits, &callchain_param); | |
170 | ||
171 | while (*p != NULL) { | |
172 | parent = *p; | |
173 | iter = rb_entry(parent, struct hist_entry, rb_node); | |
174 | ||
175 | if (he->count > iter->count) | |
176 | p = &(*p)->rb_left; | |
177 | else | |
178 | p = &(*p)->rb_right; | |
179 | } | |
180 | ||
181 | rb_link_node(&he->rb_node, parent, p); | |
b9bf0892 | 182 | rb_insert_color(&he->rb_node, root); |
3d1d07ec JK |
183 | } |
184 | ||
4e4f06e4 | 185 | void perf_session__output_resort(struct perf_session *self, u64 total_samples) |
3d1d07ec | 186 | { |
b9bf0892 | 187 | struct rb_root tmp; |
3d1d07ec JK |
188 | struct rb_node *next; |
189 | struct hist_entry *n; | |
3d1d07ec JK |
190 | u64 min_callchain_hits; |
191 | ||
192 | min_callchain_hits = | |
193 | total_samples * (callchain_param.min_percent / 100); | |
194 | ||
b9bf0892 | 195 | tmp = RB_ROOT; |
4e4f06e4 | 196 | next = rb_first(&self->hists); |
3d1d07ec JK |
197 | |
198 | while (next) { | |
199 | n = rb_entry(next, struct hist_entry, rb_node); | |
200 | next = rb_next(&n->rb_node); | |
201 | ||
4e4f06e4 | 202 | rb_erase(&n->rb_node, &self->hists); |
d599db3f | 203 | perf_session__insert_output_hist_entry(&tmp, n, |
4e4f06e4 | 204 | min_callchain_hits); |
3d1d07ec | 205 | } |
b9bf0892 | 206 | |
4e4f06e4 | 207 | self->hists = tmp; |
3d1d07ec | 208 | } |
4ecf84d0 ACM |
209 | |
210 | static size_t callchain__fprintf_left_margin(FILE *fp, int left_margin) | |
211 | { | |
212 | int i; | |
213 | int ret = fprintf(fp, " "); | |
214 | ||
215 | for (i = 0; i < left_margin; i++) | |
216 | ret += fprintf(fp, " "); | |
217 | ||
218 | return ret; | |
219 | } | |
220 | ||
221 | static size_t ipchain__fprintf_graph_line(FILE *fp, int depth, int depth_mask, | |
222 | int left_margin) | |
223 | { | |
224 | int i; | |
225 | size_t ret = callchain__fprintf_left_margin(fp, left_margin); | |
226 | ||
227 | for (i = 0; i < depth; i++) | |
228 | if (depth_mask & (1 << i)) | |
229 | ret += fprintf(fp, "| "); | |
230 | else | |
231 | ret += fprintf(fp, " "); | |
232 | ||
233 | ret += fprintf(fp, "\n"); | |
234 | ||
235 | return ret; | |
236 | } | |
237 | ||
238 | static size_t ipchain__fprintf_graph(FILE *fp, struct callchain_list *chain, | |
239 | int depth, int depth_mask, int count, | |
240 | u64 total_samples, int hits, | |
241 | int left_margin) | |
242 | { | |
243 | int i; | |
244 | size_t ret = 0; | |
245 | ||
246 | ret += callchain__fprintf_left_margin(fp, left_margin); | |
247 | for (i = 0; i < depth; i++) { | |
248 | if (depth_mask & (1 << i)) | |
249 | ret += fprintf(fp, "|"); | |
250 | else | |
251 | ret += fprintf(fp, " "); | |
252 | if (!count && i == depth - 1) { | |
253 | double percent; | |
254 | ||
255 | percent = hits * 100.0 / total_samples; | |
256 | ret += percent_color_fprintf(fp, "--%2.2f%%-- ", percent); | |
257 | } else | |
258 | ret += fprintf(fp, "%s", " "); | |
259 | } | |
260 | if (chain->sym) | |
261 | ret += fprintf(fp, "%s\n", chain->sym->name); | |
262 | else | |
263 | ret += fprintf(fp, "%p\n", (void *)(long)chain->ip); | |
264 | ||
265 | return ret; | |
266 | } | |
267 | ||
268 | static struct symbol *rem_sq_bracket; | |
269 | static struct callchain_list rem_hits; | |
270 | ||
271 | static void init_rem_hits(void) | |
272 | { | |
273 | rem_sq_bracket = malloc(sizeof(*rem_sq_bracket) + 6); | |
274 | if (!rem_sq_bracket) { | |
275 | fprintf(stderr, "Not enough memory to display remaining hits\n"); | |
276 | return; | |
277 | } | |
278 | ||
279 | strcpy(rem_sq_bracket->name, "[...]"); | |
280 | rem_hits.sym = rem_sq_bracket; | |
281 | } | |
282 | ||
283 | static size_t __callchain__fprintf_graph(FILE *fp, struct callchain_node *self, | |
284 | u64 total_samples, int depth, | |
285 | int depth_mask, int left_margin) | |
286 | { | |
287 | struct rb_node *node, *next; | |
288 | struct callchain_node *child; | |
289 | struct callchain_list *chain; | |
290 | int new_depth_mask = depth_mask; | |
291 | u64 new_total; | |
292 | u64 remaining; | |
293 | size_t ret = 0; | |
294 | int i; | |
295 | ||
296 | if (callchain_param.mode == CHAIN_GRAPH_REL) | |
297 | new_total = self->children_hit; | |
298 | else | |
299 | new_total = total_samples; | |
300 | ||
301 | remaining = new_total; | |
302 | ||
303 | node = rb_first(&self->rb_root); | |
304 | while (node) { | |
305 | u64 cumul; | |
306 | ||
307 | child = rb_entry(node, struct callchain_node, rb_node); | |
308 | cumul = cumul_hits(child); | |
309 | remaining -= cumul; | |
310 | ||
311 | /* | |
312 | * The depth mask manages the output of pipes that show | |
313 | * the depth. We don't want to keep the pipes of the current | |
314 | * level for the last child of this depth. | |
315 | * Except if we have remaining filtered hits. They will | |
316 | * supersede the last child | |
317 | */ | |
318 | next = rb_next(node); | |
319 | if (!next && (callchain_param.mode != CHAIN_GRAPH_REL || !remaining)) | |
320 | new_depth_mask &= ~(1 << (depth - 1)); | |
321 | ||
322 | /* | |
323 | * But we keep the older depth mask for the line seperator | |
324 | * to keep the level link until we reach the last child | |
325 | */ | |
326 | ret += ipchain__fprintf_graph_line(fp, depth, depth_mask, | |
327 | left_margin); | |
328 | i = 0; | |
329 | list_for_each_entry(chain, &child->val, list) { | |
330 | if (chain->ip >= PERF_CONTEXT_MAX) | |
331 | continue; | |
332 | ret += ipchain__fprintf_graph(fp, chain, depth, | |
333 | new_depth_mask, i++, | |
334 | new_total, | |
335 | cumul, | |
336 | left_margin); | |
337 | } | |
338 | ret += __callchain__fprintf_graph(fp, child, new_total, | |
339 | depth + 1, | |
340 | new_depth_mask | (1 << depth), | |
341 | left_margin); | |
342 | node = next; | |
343 | } | |
344 | ||
345 | if (callchain_param.mode == CHAIN_GRAPH_REL && | |
346 | remaining && remaining != new_total) { | |
347 | ||
348 | if (!rem_sq_bracket) | |
349 | return ret; | |
350 | ||
351 | new_depth_mask &= ~(1 << (depth - 1)); | |
352 | ||
353 | ret += ipchain__fprintf_graph(fp, &rem_hits, depth, | |
354 | new_depth_mask, 0, new_total, | |
355 | remaining, left_margin); | |
356 | } | |
357 | ||
358 | return ret; | |
359 | } | |
360 | ||
361 | static size_t callchain__fprintf_graph(FILE *fp, struct callchain_node *self, | |
362 | u64 total_samples, int left_margin) | |
363 | { | |
364 | struct callchain_list *chain; | |
365 | bool printed = false; | |
366 | int i = 0; | |
367 | int ret = 0; | |
368 | ||
369 | list_for_each_entry(chain, &self->val, list) { | |
370 | if (chain->ip >= PERF_CONTEXT_MAX) | |
371 | continue; | |
372 | ||
373 | if (!i++ && sort__first_dimension == SORT_SYM) | |
374 | continue; | |
375 | ||
376 | if (!printed) { | |
377 | ret += callchain__fprintf_left_margin(fp, left_margin); | |
378 | ret += fprintf(fp, "|\n"); | |
379 | ret += callchain__fprintf_left_margin(fp, left_margin); | |
380 | ret += fprintf(fp, "---"); | |
381 | ||
382 | left_margin += 3; | |
383 | printed = true; | |
384 | } else | |
385 | ret += callchain__fprintf_left_margin(fp, left_margin); | |
386 | ||
387 | if (chain->sym) | |
388 | ret += fprintf(fp, " %s\n", chain->sym->name); | |
389 | else | |
390 | ret += fprintf(fp, " %p\n", (void *)(long)chain->ip); | |
391 | } | |
392 | ||
393 | ret += __callchain__fprintf_graph(fp, self, total_samples, 1, 1, left_margin); | |
394 | ||
395 | return ret; | |
396 | } | |
397 | ||
398 | static size_t callchain__fprintf_flat(FILE *fp, struct callchain_node *self, | |
399 | u64 total_samples) | |
400 | { | |
401 | struct callchain_list *chain; | |
402 | size_t ret = 0; | |
403 | ||
404 | if (!self) | |
405 | return 0; | |
406 | ||
407 | ret += callchain__fprintf_flat(fp, self->parent, total_samples); | |
408 | ||
409 | ||
410 | list_for_each_entry(chain, &self->val, list) { | |
411 | if (chain->ip >= PERF_CONTEXT_MAX) | |
412 | continue; | |
413 | if (chain->sym) | |
414 | ret += fprintf(fp, " %s\n", chain->sym->name); | |
415 | else | |
416 | ret += fprintf(fp, " %p\n", | |
417 | (void *)(long)chain->ip); | |
418 | } | |
419 | ||
420 | return ret; | |
421 | } | |
422 | ||
423 | static size_t hist_entry_callchain__fprintf(FILE *fp, struct hist_entry *self, | |
424 | u64 total_samples, int left_margin) | |
425 | { | |
426 | struct rb_node *rb_node; | |
427 | struct callchain_node *chain; | |
428 | size_t ret = 0; | |
429 | ||
430 | rb_node = rb_first(&self->sorted_chain); | |
431 | while (rb_node) { | |
432 | double percent; | |
433 | ||
434 | chain = rb_entry(rb_node, struct callchain_node, rb_node); | |
435 | percent = chain->hit * 100.0 / total_samples; | |
436 | switch (callchain_param.mode) { | |
437 | case CHAIN_FLAT: | |
438 | ret += percent_color_fprintf(fp, " %6.2f%%\n", | |
439 | percent); | |
440 | ret += callchain__fprintf_flat(fp, chain, total_samples); | |
441 | break; | |
442 | case CHAIN_GRAPH_ABS: /* Falldown */ | |
443 | case CHAIN_GRAPH_REL: | |
444 | ret += callchain__fprintf_graph(fp, chain, total_samples, | |
445 | left_margin); | |
446 | case CHAIN_NONE: | |
447 | default: | |
448 | break; | |
449 | } | |
450 | ret += fprintf(fp, "\n"); | |
451 | rb_node = rb_next(rb_node); | |
452 | } | |
453 | ||
454 | return ret; | |
455 | } | |
456 | ||
457 | static size_t hist_entry__fprintf(FILE *fp, struct hist_entry *self, | |
458 | struct perf_session *session) | |
459 | { | |
460 | struct sort_entry *se; | |
461 | size_t ret; | |
462 | ||
463 | if (symbol_conf.exclude_other && !self->parent) | |
464 | return 0; | |
465 | ||
466 | if (session->events_stats.total) | |
467 | ret = percent_color_fprintf(fp, | |
468 | symbol_conf.field_sep ? "%.2f" : " %6.2f%%", | |
469 | (self->count * 100.0) / session->events_stats.total); | |
470 | else | |
471 | ret = fprintf(fp, symbol_conf.field_sep ? "%lld" : "%12lld ", self->count); | |
472 | ||
473 | if (symbol_conf.show_nr_samples) { | |
474 | if (symbol_conf.field_sep) | |
475 | fprintf(fp, "%c%lld", *symbol_conf.field_sep, self->count); | |
476 | else | |
477 | fprintf(fp, "%11lld", self->count); | |
478 | } | |
479 | ||
480 | list_for_each_entry(se, &hist_entry__sort_list, list) { | |
481 | if (se->elide) | |
482 | continue; | |
483 | ||
484 | fprintf(fp, "%s", symbol_conf.field_sep ?: " "); | |
485 | ret += se->print(fp, self, se->width ? *se->width : 0); | |
486 | } | |
487 | ||
488 | ret += fprintf(fp, "\n"); | |
489 | ||
490 | if (symbol_conf.use_callchain) { | |
491 | int left_margin = 0; | |
492 | ||
493 | if (sort__first_dimension == SORT_COMM) { | |
494 | se = list_first_entry(&hist_entry__sort_list, typeof(*se), | |
495 | list); | |
496 | left_margin = se->width ? *se->width : 0; | |
497 | left_margin -= thread__comm_len(self->thread); | |
498 | } | |
499 | ||
500 | hist_entry_callchain__fprintf(fp, self, session->events_stats.total, | |
501 | left_margin); | |
502 | } | |
503 | ||
504 | return ret; | |
505 | } | |
506 | ||
507 | size_t perf_session__fprintf_hists(struct perf_session *self, FILE *fp) | |
508 | { | |
509 | struct hist_entry *pos; | |
510 | struct sort_entry *se; | |
511 | struct rb_node *nd; | |
512 | size_t ret = 0; | |
513 | unsigned int width; | |
514 | char *col_width = symbol_conf.col_width_list_str; | |
515 | ||
516 | init_rem_hits(); | |
517 | ||
4ecf84d0 ACM |
518 | fprintf(fp, "# Overhead"); |
519 | if (symbol_conf.show_nr_samples) { | |
520 | if (symbol_conf.field_sep) | |
521 | fprintf(fp, "%cSamples", *symbol_conf.field_sep); | |
522 | else | |
523 | fputs(" Samples ", fp); | |
524 | } | |
525 | list_for_each_entry(se, &hist_entry__sort_list, list) { | |
526 | if (se->elide) | |
527 | continue; | |
528 | if (symbol_conf.field_sep) { | |
529 | fprintf(fp, "%c%s", *symbol_conf.field_sep, se->header); | |
530 | continue; | |
531 | } | |
532 | width = strlen(se->header); | |
533 | if (se->width) { | |
534 | if (symbol_conf.col_width_list_str) { | |
535 | if (col_width) { | |
536 | *se->width = atoi(col_width); | |
537 | col_width = strchr(col_width, ','); | |
538 | if (col_width) | |
539 | ++col_width; | |
540 | } | |
541 | } | |
542 | width = *se->width = max(*se->width, width); | |
543 | } | |
544 | fprintf(fp, " %*s", width, se->header); | |
545 | } | |
546 | fprintf(fp, "\n"); | |
547 | ||
548 | if (symbol_conf.field_sep) | |
549 | goto print_entries; | |
550 | ||
551 | fprintf(fp, "# ........"); | |
552 | if (symbol_conf.show_nr_samples) | |
553 | fprintf(fp, " .........."); | |
554 | list_for_each_entry(se, &hist_entry__sort_list, list) { | |
555 | unsigned int i; | |
556 | ||
557 | if (se->elide) | |
558 | continue; | |
559 | ||
560 | fprintf(fp, " "); | |
561 | if (se->width) | |
562 | width = *se->width; | |
563 | else | |
564 | width = strlen(se->header); | |
565 | for (i = 0; i < width; i++) | |
566 | fprintf(fp, "."); | |
567 | } | |
568 | fprintf(fp, "\n"); | |
569 | ||
570 | fprintf(fp, "#\n"); | |
571 | ||
572 | print_entries: | |
573 | for (nd = rb_first(&self->hists); nd; nd = rb_next(nd)) { | |
574 | pos = rb_entry(nd, struct hist_entry, rb_node); | |
575 | ret += hist_entry__fprintf(fp, pos, self); | |
576 | } | |
577 | ||
4ecf84d0 ACM |
578 | free(rem_sq_bracket); |
579 | ||
580 | return ret; | |
581 | } |