Merge branch 'perf-urgent-for-linus' of git://git.kernel.org/pub/scm/linux/kernel...
[~shefty/rdma-dev.git] / tools / perf / util / ui / browsers / hists.c
1 #define _GNU_SOURCE
2 #include <stdio.h>
3 #undef _GNU_SOURCE
4 #include "../libslang.h"
5 #include <stdlib.h>
6 #include <string.h>
7 #include <newt.h>
8 #include <linux/rbtree.h>
9
10 #include "../../evsel.h"
11 #include "../../evlist.h"
12 #include "../../hist.h"
13 #include "../../pstack.h"
14 #include "../../sort.h"
15 #include "../../util.h"
16
17 #include "../browser.h"
18 #include "../helpline.h"
19 #include "../util.h"
20 #include "../ui.h"
21 #include "map.h"
22
23 struct hist_browser {
24         struct ui_browser   b;
25         struct hists        *hists;
26         struct hist_entry   *he_selection;
27         struct map_symbol   *selection;
28         bool                 has_symbols;
29 };
30
31 static int hists__browser_title(struct hists *self, char *bf, size_t size,
32                                 const char *ev_name);
33
34 static void hist_browser__refresh_dimensions(struct hist_browser *self)
35 {
36         /* 3 == +/- toggle symbol before actual hist_entry rendering */
37         self->b.width = 3 + (hists__sort_list_width(self->hists) +
38                              sizeof("[k]"));
39 }
40
41 static void hist_browser__reset(struct hist_browser *self)
42 {
43         self->b.nr_entries = self->hists->nr_entries;
44         hist_browser__refresh_dimensions(self);
45         ui_browser__reset_index(&self->b);
46 }
47
48 static char tree__folded_sign(bool unfolded)
49 {
50         return unfolded ? '-' : '+';
51 }
52
53 static char map_symbol__folded(const struct map_symbol *self)
54 {
55         return self->has_children ? tree__folded_sign(self->unfolded) : ' ';
56 }
57
58 static char hist_entry__folded(const struct hist_entry *self)
59 {
60         return map_symbol__folded(&self->ms);
61 }
62
63 static char callchain_list__folded(const struct callchain_list *self)
64 {
65         return map_symbol__folded(&self->ms);
66 }
67
68 static void map_symbol__set_folding(struct map_symbol *self, bool unfold)
69 {
70         self->unfolded = unfold ? self->has_children : false;
71 }
72
73 static int callchain_node__count_rows_rb_tree(struct callchain_node *self)
74 {
75         int n = 0;
76         struct rb_node *nd;
77
78         for (nd = rb_first(&self->rb_root); nd; nd = rb_next(nd)) {
79                 struct callchain_node *child = rb_entry(nd, struct callchain_node, rb_node);
80                 struct callchain_list *chain;
81                 char folded_sign = ' '; /* No children */
82
83                 list_for_each_entry(chain, &child->val, list) {
84                         ++n;
85                         /* We need this because we may not have children */
86                         folded_sign = callchain_list__folded(chain);
87                         if (folded_sign == '+')
88                                 break;
89                 }
90
91                 if (folded_sign == '-') /* Have children and they're unfolded */
92                         n += callchain_node__count_rows_rb_tree(child);
93         }
94
95         return n;
96 }
97
98 static int callchain_node__count_rows(struct callchain_node *node)
99 {
100         struct callchain_list *chain;
101         bool unfolded = false;
102         int n = 0;
103
104         list_for_each_entry(chain, &node->val, list) {
105                 ++n;
106                 unfolded = chain->ms.unfolded;
107         }
108
109         if (unfolded)
110                 n += callchain_node__count_rows_rb_tree(node);
111
112         return n;
113 }
114
115 static int callchain__count_rows(struct rb_root *chain)
116 {
117         struct rb_node *nd;
118         int n = 0;
119
120         for (nd = rb_first(chain); nd; nd = rb_next(nd)) {
121                 struct callchain_node *node = rb_entry(nd, struct callchain_node, rb_node);
122                 n += callchain_node__count_rows(node);
123         }
124
125         return n;
126 }
127
128 static bool map_symbol__toggle_fold(struct map_symbol *self)
129 {
130         if (!self->has_children)
131                 return false;
132
133         self->unfolded = !self->unfolded;
134         return true;
135 }
136
137 static void callchain_node__init_have_children_rb_tree(struct callchain_node *self)
138 {
139         struct rb_node *nd = rb_first(&self->rb_root);
140
141         for (nd = rb_first(&self->rb_root); nd; nd = rb_next(nd)) {
142                 struct callchain_node *child = rb_entry(nd, struct callchain_node, rb_node);
143                 struct callchain_list *chain;
144                 bool first = true;
145
146                 list_for_each_entry(chain, &child->val, list) {
147                         if (first) {
148                                 first = false;
149                                 chain->ms.has_children = chain->list.next != &child->val ||
150                                                          !RB_EMPTY_ROOT(&child->rb_root);
151                         } else
152                                 chain->ms.has_children = chain->list.next == &child->val &&
153                                                          !RB_EMPTY_ROOT(&child->rb_root);
154                 }
155
156                 callchain_node__init_have_children_rb_tree(child);
157         }
158 }
159
160 static void callchain_node__init_have_children(struct callchain_node *self)
161 {
162         struct callchain_list *chain;
163
164         list_for_each_entry(chain, &self->val, list)
165                 chain->ms.has_children = !RB_EMPTY_ROOT(&self->rb_root);
166
167         callchain_node__init_have_children_rb_tree(self);
168 }
169
170 static void callchain__init_have_children(struct rb_root *self)
171 {
172         struct rb_node *nd;
173
174         for (nd = rb_first(self); nd; nd = rb_next(nd)) {
175                 struct callchain_node *node = rb_entry(nd, struct callchain_node, rb_node);
176                 callchain_node__init_have_children(node);
177         }
178 }
179
180 static void hist_entry__init_have_children(struct hist_entry *self)
181 {
182         if (!self->init_have_children) {
183                 self->ms.has_children = !RB_EMPTY_ROOT(&self->sorted_chain);
184                 callchain__init_have_children(&self->sorted_chain);
185                 self->init_have_children = true;
186         }
187 }
188
189 static bool hist_browser__toggle_fold(struct hist_browser *self)
190 {
191         if (map_symbol__toggle_fold(self->selection)) {
192                 struct hist_entry *he = self->he_selection;
193
194                 hist_entry__init_have_children(he);
195                 self->hists->nr_entries -= he->nr_rows;
196
197                 if (he->ms.unfolded)
198                         he->nr_rows = callchain__count_rows(&he->sorted_chain);
199                 else
200                         he->nr_rows = 0;
201                 self->hists->nr_entries += he->nr_rows;
202                 self->b.nr_entries = self->hists->nr_entries;
203
204                 return true;
205         }
206
207         /* If it doesn't have children, no toggling performed */
208         return false;
209 }
210
211 static int callchain_node__set_folding_rb_tree(struct callchain_node *self, bool unfold)
212 {
213         int n = 0;
214         struct rb_node *nd;
215
216         for (nd = rb_first(&self->rb_root); nd; nd = rb_next(nd)) {
217                 struct callchain_node *child = rb_entry(nd, struct callchain_node, rb_node);
218                 struct callchain_list *chain;
219                 bool has_children = false;
220
221                 list_for_each_entry(chain, &child->val, list) {
222                         ++n;
223                         map_symbol__set_folding(&chain->ms, unfold);
224                         has_children = chain->ms.has_children;
225                 }
226
227                 if (has_children)
228                         n += callchain_node__set_folding_rb_tree(child, unfold);
229         }
230
231         return n;
232 }
233
234 static int callchain_node__set_folding(struct callchain_node *node, bool unfold)
235 {
236         struct callchain_list *chain;
237         bool has_children = false;
238         int n = 0;
239
240         list_for_each_entry(chain, &node->val, list) {
241                 ++n;
242                 map_symbol__set_folding(&chain->ms, unfold);
243                 has_children = chain->ms.has_children;
244         }
245
246         if (has_children)
247                 n += callchain_node__set_folding_rb_tree(node, unfold);
248
249         return n;
250 }
251
252 static int callchain__set_folding(struct rb_root *chain, bool unfold)
253 {
254         struct rb_node *nd;
255         int n = 0;
256
257         for (nd = rb_first(chain); nd; nd = rb_next(nd)) {
258                 struct callchain_node *node = rb_entry(nd, struct callchain_node, rb_node);
259                 n += callchain_node__set_folding(node, unfold);
260         }
261
262         return n;
263 }
264
265 static void hist_entry__set_folding(struct hist_entry *self, bool unfold)
266 {
267         hist_entry__init_have_children(self);
268         map_symbol__set_folding(&self->ms, unfold);
269
270         if (self->ms.has_children) {
271                 int n = callchain__set_folding(&self->sorted_chain, unfold);
272                 self->nr_rows = unfold ? n : 0;
273         } else
274                 self->nr_rows = 0;
275 }
276
277 static void hists__set_folding(struct hists *self, bool unfold)
278 {
279         struct rb_node *nd;
280
281         self->nr_entries = 0;
282
283         for (nd = rb_first(&self->entries); nd; nd = rb_next(nd)) {
284                 struct hist_entry *he = rb_entry(nd, struct hist_entry, rb_node);
285                 hist_entry__set_folding(he, unfold);
286                 self->nr_entries += 1 + he->nr_rows;
287         }
288 }
289
290 static void hist_browser__set_folding(struct hist_browser *self, bool unfold)
291 {
292         hists__set_folding(self->hists, unfold);
293         self->b.nr_entries = self->hists->nr_entries;
294         /* Go to the start, we may be way after valid entries after a collapse */
295         ui_browser__reset_index(&self->b);
296 }
297
298 static void ui_browser__warn_lost_events(struct ui_browser *browser)
299 {
300         ui_browser__warning(browser, 4,
301                 "Events are being lost, check IO/CPU overload!\n\n"
302                 "You may want to run 'perf' using a RT scheduler policy:\n\n"
303                 " perf top -r 80\n\n"
304                 "Or reduce the sampling frequency.");
305 }
306
307 static int hist_browser__run(struct hist_browser *self, const char *ev_name,
308                              void(*timer)(void *arg), void *arg, int delay_secs)
309 {
310         int key;
311         char title[160];
312
313         self->b.entries = &self->hists->entries;
314         self->b.nr_entries = self->hists->nr_entries;
315
316         hist_browser__refresh_dimensions(self);
317         hists__browser_title(self->hists, title, sizeof(title), ev_name);
318
319         if (ui_browser__show(&self->b, title,
320                              "Press '?' for help on key bindings") < 0)
321                 return -1;
322
323         while (1) {
324                 key = ui_browser__run(&self->b, delay_secs);
325
326                 switch (key) {
327                 case K_TIMER:
328                         timer(arg);
329                         ui_browser__update_nr_entries(&self->b, self->hists->nr_entries);
330
331                         if (self->hists->stats.nr_lost_warned !=
332                             self->hists->stats.nr_events[PERF_RECORD_LOST]) {
333                                 self->hists->stats.nr_lost_warned =
334                                         self->hists->stats.nr_events[PERF_RECORD_LOST];
335                                 ui_browser__warn_lost_events(&self->b);
336                         }
337
338                         hists__browser_title(self->hists, title, sizeof(title), ev_name);
339                         ui_browser__show_title(&self->b, title);
340                         continue;
341                 case 'D': { /* Debug */
342                         static int seq;
343                         struct hist_entry *h = rb_entry(self->b.top,
344                                                         struct hist_entry, rb_node);
345                         ui_helpline__pop();
346                         ui_helpline__fpush("%d: nr_ent=(%d,%d), height=%d, idx=%d, fve: idx=%d, row_off=%d, nrows=%d",
347                                            seq++, self->b.nr_entries,
348                                            self->hists->nr_entries,
349                                            self->b.height,
350                                            self->b.index,
351                                            self->b.top_idx,
352                                            h->row_offset, h->nr_rows);
353                 }
354                         break;
355                 case 'C':
356                         /* Collapse the whole world. */
357                         hist_browser__set_folding(self, false);
358                         break;
359                 case 'E':
360                         /* Expand the whole world. */
361                         hist_browser__set_folding(self, true);
362                         break;
363                 case K_ENTER:
364                         if (hist_browser__toggle_fold(self))
365                                 break;
366                         /* fall thru */
367                 default:
368                         goto out;
369                 }
370         }
371 out:
372         ui_browser__hide(&self->b);
373         return key;
374 }
375
376 static char *callchain_list__sym_name(struct callchain_list *self,
377                                       char *bf, size_t bfsize)
378 {
379         if (self->ms.sym)
380                 return self->ms.sym->name;
381
382         snprintf(bf, bfsize, "%#" PRIx64, self->ip);
383         return bf;
384 }
385
386 #define LEVEL_OFFSET_STEP 3
387
388 static int hist_browser__show_callchain_node_rb_tree(struct hist_browser *self,
389                                                      struct callchain_node *chain_node,
390                                                      u64 total, int level,
391                                                      unsigned short row,
392                                                      off_t *row_offset,
393                                                      bool *is_current_entry)
394 {
395         struct rb_node *node;
396         int first_row = row, width, offset = level * LEVEL_OFFSET_STEP;
397         u64 new_total, remaining;
398
399         if (callchain_param.mode == CHAIN_GRAPH_REL)
400                 new_total = chain_node->children_hit;
401         else
402                 new_total = total;
403
404         remaining = new_total;
405         node = rb_first(&chain_node->rb_root);
406         while (node) {
407                 struct callchain_node *child = rb_entry(node, struct callchain_node, rb_node);
408                 struct rb_node *next = rb_next(node);
409                 u64 cumul = callchain_cumul_hits(child);
410                 struct callchain_list *chain;
411                 char folded_sign = ' ';
412                 int first = true;
413                 int extra_offset = 0;
414
415                 remaining -= cumul;
416
417                 list_for_each_entry(chain, &child->val, list) {
418                         char ipstr[BITS_PER_LONG / 4 + 1], *alloc_str;
419                         const char *str;
420                         int color;
421                         bool was_first = first;
422
423                         if (first)
424                                 first = false;
425                         else
426                                 extra_offset = LEVEL_OFFSET_STEP;
427
428                         folded_sign = callchain_list__folded(chain);
429                         if (*row_offset != 0) {
430                                 --*row_offset;
431                                 goto do_next;
432                         }
433
434                         alloc_str = NULL;
435                         str = callchain_list__sym_name(chain, ipstr, sizeof(ipstr));
436                         if (was_first) {
437                                 double percent = cumul * 100.0 / new_total;
438
439                                 if (asprintf(&alloc_str, "%2.2f%% %s", percent, str) < 0)
440                                         str = "Not enough memory!";
441                                 else
442                                         str = alloc_str;
443                         }
444
445                         color = HE_COLORSET_NORMAL;
446                         width = self->b.width - (offset + extra_offset + 2);
447                         if (ui_browser__is_current_entry(&self->b, row)) {
448                                 self->selection = &chain->ms;
449                                 color = HE_COLORSET_SELECTED;
450                                 *is_current_entry = true;
451                         }
452
453                         ui_browser__set_color(&self->b, color);
454                         ui_browser__gotorc(&self->b, row, 0);
455                         slsmg_write_nstring(" ", offset + extra_offset);
456                         slsmg_printf("%c ", folded_sign);
457                         slsmg_write_nstring(str, width);
458                         free(alloc_str);
459
460                         if (++row == self->b.height)
461                                 goto out;
462 do_next:
463                         if (folded_sign == '+')
464                                 break;
465                 }
466
467                 if (folded_sign == '-') {
468                         const int new_level = level + (extra_offset ? 2 : 1);
469                         row += hist_browser__show_callchain_node_rb_tree(self, child, new_total,
470                                                                          new_level, row, row_offset,
471                                                                          is_current_entry);
472                 }
473                 if (row == self->b.height)
474                         goto out;
475                 node = next;
476         }
477 out:
478         return row - first_row;
479 }
480
481 static int hist_browser__show_callchain_node(struct hist_browser *self,
482                                              struct callchain_node *node,
483                                              int level, unsigned short row,
484                                              off_t *row_offset,
485                                              bool *is_current_entry)
486 {
487         struct callchain_list *chain;
488         int first_row = row,
489              offset = level * LEVEL_OFFSET_STEP,
490              width = self->b.width - offset;
491         char folded_sign = ' ';
492
493         list_for_each_entry(chain, &node->val, list) {
494                 char ipstr[BITS_PER_LONG / 4 + 1], *s;
495                 int color;
496
497                 folded_sign = callchain_list__folded(chain);
498
499                 if (*row_offset != 0) {
500                         --*row_offset;
501                         continue;
502                 }
503
504                 color = HE_COLORSET_NORMAL;
505                 if (ui_browser__is_current_entry(&self->b, row)) {
506                         self->selection = &chain->ms;
507                         color = HE_COLORSET_SELECTED;
508                         *is_current_entry = true;
509                 }
510
511                 s = callchain_list__sym_name(chain, ipstr, sizeof(ipstr));
512                 ui_browser__gotorc(&self->b, row, 0);
513                 ui_browser__set_color(&self->b, color);
514                 slsmg_write_nstring(" ", offset);
515                 slsmg_printf("%c ", folded_sign);
516                 slsmg_write_nstring(s, width - 2);
517
518                 if (++row == self->b.height)
519                         goto out;
520         }
521
522         if (folded_sign == '-')
523                 row += hist_browser__show_callchain_node_rb_tree(self, node,
524                                                                  self->hists->stats.total_period,
525                                                                  level + 1, row,
526                                                                  row_offset,
527                                                                  is_current_entry);
528 out:
529         return row - first_row;
530 }
531
532 static int hist_browser__show_callchain(struct hist_browser *self,
533                                         struct rb_root *chain,
534                                         int level, unsigned short row,
535                                         off_t *row_offset,
536                                         bool *is_current_entry)
537 {
538         struct rb_node *nd;
539         int first_row = row;
540
541         for (nd = rb_first(chain); nd; nd = rb_next(nd)) {
542                 struct callchain_node *node = rb_entry(nd, struct callchain_node, rb_node);
543
544                 row += hist_browser__show_callchain_node(self, node, level,
545                                                          row, row_offset,
546                                                          is_current_entry);
547                 if (row == self->b.height)
548                         break;
549         }
550
551         return row - first_row;
552 }
553
554 static int hist_browser__show_entry(struct hist_browser *self,
555                                     struct hist_entry *entry,
556                                     unsigned short row)
557 {
558         char s[256];
559         double percent;
560         int printed = 0;
561         int width = self->b.width - 6; /* The percentage */
562         char folded_sign = ' ';
563         bool current_entry = ui_browser__is_current_entry(&self->b, row);
564         off_t row_offset = entry->row_offset;
565
566         if (current_entry) {
567                 self->he_selection = entry;
568                 self->selection = &entry->ms;
569         }
570
571         if (symbol_conf.use_callchain) {
572                 hist_entry__init_have_children(entry);
573                 folded_sign = hist_entry__folded(entry);
574         }
575
576         if (row_offset == 0) {
577                 hist_entry__snprintf(entry, s, sizeof(s), self->hists);
578                 percent = (entry->period * 100.0) / self->hists->stats.total_period;
579
580                 ui_browser__set_percent_color(&self->b, percent, current_entry);
581                 ui_browser__gotorc(&self->b, row, 0);
582                 if (symbol_conf.use_callchain) {
583                         slsmg_printf("%c ", folded_sign);
584                         width -= 2;
585                 }
586
587                 slsmg_printf(" %5.2f%%", percent);
588
589                 /* The scroll bar isn't being used */
590                 if (!self->b.navkeypressed)
591                         width += 1;
592
593                 if (!current_entry || !self->b.navkeypressed)
594                         ui_browser__set_color(&self->b, HE_COLORSET_NORMAL);
595
596                 if (symbol_conf.show_nr_samples) {
597                         slsmg_printf(" %11u", entry->nr_events);
598                         width -= 12;
599                 }
600
601                 if (symbol_conf.show_total_period) {
602                         slsmg_printf(" %12" PRIu64, entry->period);
603                         width -= 13;
604                 }
605
606                 slsmg_write_nstring(s, width);
607                 ++row;
608                 ++printed;
609         } else
610                 --row_offset;
611
612         if (folded_sign == '-' && row != self->b.height) {
613                 printed += hist_browser__show_callchain(self, &entry->sorted_chain,
614                                                         1, row, &row_offset,
615                                                         &current_entry);
616                 if (current_entry)
617                         self->he_selection = entry;
618         }
619
620         return printed;
621 }
622
623 static void ui_browser__hists_init_top(struct ui_browser *browser)
624 {
625         if (browser->top == NULL) {
626                 struct hist_browser *hb;
627
628                 hb = container_of(browser, struct hist_browser, b);
629                 browser->top = rb_first(&hb->hists->entries);
630         }
631 }
632
633 static unsigned int hist_browser__refresh(struct ui_browser *self)
634 {
635         unsigned row = 0;
636         struct rb_node *nd;
637         struct hist_browser *hb = container_of(self, struct hist_browser, b);
638
639         ui_browser__hists_init_top(self);
640
641         for (nd = self->top; nd; nd = rb_next(nd)) {
642                 struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
643
644                 if (h->filtered)
645                         continue;
646
647                 row += hist_browser__show_entry(hb, h, row);
648                 if (row == self->height)
649                         break;
650         }
651
652         return row;
653 }
654
655 static struct rb_node *hists__filter_entries(struct rb_node *nd)
656 {
657         while (nd != NULL) {
658                 struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
659                 if (!h->filtered)
660                         return nd;
661
662                 nd = rb_next(nd);
663         }
664
665         return NULL;
666 }
667
668 static struct rb_node *hists__filter_prev_entries(struct rb_node *nd)
669 {
670         while (nd != NULL) {
671                 struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
672                 if (!h->filtered)
673                         return nd;
674
675                 nd = rb_prev(nd);
676         }
677
678         return NULL;
679 }
680
681 static void ui_browser__hists_seek(struct ui_browser *self,
682                                    off_t offset, int whence)
683 {
684         struct hist_entry *h;
685         struct rb_node *nd;
686         bool first = true;
687
688         if (self->nr_entries == 0)
689                 return;
690
691         ui_browser__hists_init_top(self);
692
693         switch (whence) {
694         case SEEK_SET:
695                 nd = hists__filter_entries(rb_first(self->entries));
696                 break;
697         case SEEK_CUR:
698                 nd = self->top;
699                 goto do_offset;
700         case SEEK_END:
701                 nd = hists__filter_prev_entries(rb_last(self->entries));
702                 first = false;
703                 break;
704         default:
705                 return;
706         }
707
708         /*
709          * Moves not relative to the first visible entry invalidates its
710          * row_offset:
711          */
712         h = rb_entry(self->top, struct hist_entry, rb_node);
713         h->row_offset = 0;
714
715         /*
716          * Here we have to check if nd is expanded (+), if it is we can't go
717          * the next top level hist_entry, instead we must compute an offset of
718          * what _not_ to show and not change the first visible entry.
719          *
720          * This offset increments when we are going from top to bottom and
721          * decreases when we're going from bottom to top.
722          *
723          * As we don't have backpointers to the top level in the callchains
724          * structure, we need to always print the whole hist_entry callchain,
725          * skipping the first ones that are before the first visible entry
726          * and stop when we printed enough lines to fill the screen.
727          */
728 do_offset:
729         if (offset > 0) {
730                 do {
731                         h = rb_entry(nd, struct hist_entry, rb_node);
732                         if (h->ms.unfolded) {
733                                 u16 remaining = h->nr_rows - h->row_offset;
734                                 if (offset > remaining) {
735                                         offset -= remaining;
736                                         h->row_offset = 0;
737                                 } else {
738                                         h->row_offset += offset;
739                                         offset = 0;
740                                         self->top = nd;
741                                         break;
742                                 }
743                         }
744                         nd = hists__filter_entries(rb_next(nd));
745                         if (nd == NULL)
746                                 break;
747                         --offset;
748                         self->top = nd;
749                 } while (offset != 0);
750         } else if (offset < 0) {
751                 while (1) {
752                         h = rb_entry(nd, struct hist_entry, rb_node);
753                         if (h->ms.unfolded) {
754                                 if (first) {
755                                         if (-offset > h->row_offset) {
756                                                 offset += h->row_offset;
757                                                 h->row_offset = 0;
758                                         } else {
759                                                 h->row_offset += offset;
760                                                 offset = 0;
761                                                 self->top = nd;
762                                                 break;
763                                         }
764                                 } else {
765                                         if (-offset > h->nr_rows) {
766                                                 offset += h->nr_rows;
767                                                 h->row_offset = 0;
768                                         } else {
769                                                 h->row_offset = h->nr_rows + offset;
770                                                 offset = 0;
771                                                 self->top = nd;
772                                                 break;
773                                         }
774                                 }
775                         }
776
777                         nd = hists__filter_prev_entries(rb_prev(nd));
778                         if (nd == NULL)
779                                 break;
780                         ++offset;
781                         self->top = nd;
782                         if (offset == 0) {
783                                 /*
784                                  * Last unfiltered hist_entry, check if it is
785                                  * unfolded, if it is then we should have
786                                  * row_offset at its last entry.
787                                  */
788                                 h = rb_entry(nd, struct hist_entry, rb_node);
789                                 if (h->ms.unfolded)
790                                         h->row_offset = h->nr_rows;
791                                 break;
792                         }
793                         first = false;
794                 }
795         } else {
796                 self->top = nd;
797                 h = rb_entry(nd, struct hist_entry, rb_node);
798                 h->row_offset = 0;
799         }
800 }
801
802 static struct hist_browser *hist_browser__new(struct hists *hists)
803 {
804         struct hist_browser *self = zalloc(sizeof(*self));
805
806         if (self) {
807                 self->hists = hists;
808                 self->b.refresh = hist_browser__refresh;
809                 self->b.seek = ui_browser__hists_seek;
810                 self->b.use_navkeypressed = true,
811                 self->has_symbols = sort_sym.list.next != NULL;
812         }
813
814         return self;
815 }
816
817 static void hist_browser__delete(struct hist_browser *self)
818 {
819         free(self);
820 }
821
822 static struct hist_entry *hist_browser__selected_entry(struct hist_browser *self)
823 {
824         return self->he_selection;
825 }
826
827 static struct thread *hist_browser__selected_thread(struct hist_browser *self)
828 {
829         return self->he_selection->thread;
830 }
831
832 static int hists__browser_title(struct hists *self, char *bf, size_t size,
833                                 const char *ev_name)
834 {
835         char unit;
836         int printed;
837         const struct dso *dso = self->dso_filter;
838         const struct thread *thread = self->thread_filter;
839         unsigned long nr_events = self->stats.nr_events[PERF_RECORD_SAMPLE];
840
841         nr_events = convert_unit(nr_events, &unit);
842         printed = snprintf(bf, size, "Events: %lu%c %s", nr_events, unit, ev_name);
843
844         if (thread)
845                 printed += snprintf(bf + printed, size - printed,
846                                     ", Thread: %s(%d)",
847                                     (thread->comm_set ? thread->comm : ""),
848                                     thread->pid);
849         if (dso)
850                 printed += snprintf(bf + printed, size - printed,
851                                     ", DSO: %s", dso->short_name);
852         return printed;
853 }
854
855 static int perf_evsel__hists_browse(struct perf_evsel *evsel, int nr_events,
856                                     const char *helpline, const char *ev_name,
857                                     bool left_exits,
858                                     void(*timer)(void *arg), void *arg,
859                                     int delay_secs)
860 {
861         struct hists *self = &evsel->hists;
862         struct hist_browser *browser = hist_browser__new(self);
863         struct pstack *fstack;
864         int key = -1;
865
866         if (browser == NULL)
867                 return -1;
868
869         fstack = pstack__new(2);
870         if (fstack == NULL)
871                 goto out;
872
873         ui_helpline__push(helpline);
874
875         while (1) {
876                 const struct thread *thread = NULL;
877                 const struct dso *dso = NULL;
878                 char *options[16];
879                 int nr_options = 0, choice = 0, i,
880                     annotate = -2, zoom_dso = -2, zoom_thread = -2,
881                     browse_map = -2;
882
883                 key = hist_browser__run(browser, ev_name, timer, arg, delay_secs);
884
885                 if (browser->he_selection != NULL) {
886                         thread = hist_browser__selected_thread(browser);
887                         dso = browser->selection->map ? browser->selection->map->dso : NULL;
888                 }
889
890                 switch (key) {
891                 case K_TAB:
892                 case K_UNTAB:
893                         if (nr_events == 1)
894                                 continue;
895                         /*
896                          * Exit the browser, let hists__browser_tree
897                          * go to the next or previous
898                          */
899                         goto out_free_stack;
900                 case 'a':
901                         if (!browser->has_symbols) {
902                                 ui_browser__warning(&browser->b, delay_secs * 2,
903                         "Annotation is only available for symbolic views, "
904                         "include \"sym\" in --sort to use it.");
905                                 continue;
906                         }
907
908                         if (browser->selection == NULL ||
909                             browser->selection->sym == NULL ||
910                             browser->selection->map->dso->annotate_warned)
911                                 continue;
912                         goto do_annotate;
913                 case 'd':
914                         goto zoom_dso;
915                 case 't':
916                         goto zoom_thread;
917                 case K_F1:
918                 case 'h':
919                 case '?':
920                         ui_browser__help_window(&browser->b,
921                                         "h/?/F1        Show this window\n"
922                                         "UP/DOWN/PGUP\n"
923                                         "PGDN/SPACE    Navigate\n"
924                                         "q/ESC/CTRL+C  Exit browser\n\n"
925                                         "For multiple event sessions:\n\n"
926                                         "TAB/UNTAB Switch events\n\n"
927                                         "For symbolic views (--sort has sym):\n\n"
928                                         "->            Zoom into DSO/Threads & Annotate current symbol\n"
929                                         "<-            Zoom out\n"
930                                         "a             Annotate current symbol\n"
931                                         "C             Collapse all callchains\n"
932                                         "E             Expand all callchains\n"
933                                         "d             Zoom into current DSO\n"
934                                         "t             Zoom into current Thread");
935                         continue;
936                 case K_ENTER:
937                 case K_RIGHT:
938                         /* menu */
939                         break;
940                 case K_LEFT: {
941                         const void *top;
942
943                         if (pstack__empty(fstack)) {
944                                 /*
945                                  * Go back to the perf_evsel_menu__run or other user
946                                  */
947                                 if (left_exits)
948                                         goto out_free_stack;
949                                 continue;
950                         }
951                         top = pstack__pop(fstack);
952                         if (top == &browser->hists->dso_filter)
953                                 goto zoom_out_dso;
954                         if (top == &browser->hists->thread_filter)
955                                 goto zoom_out_thread;
956                         continue;
957                 }
958                 case K_ESC:
959                         if (!left_exits &&
960                             !ui_browser__dialog_yesno(&browser->b,
961                                                "Do you really want to exit?"))
962                                 continue;
963                         /* Fall thru */
964                 case 'q':
965                 case CTRL('c'):
966                         goto out_free_stack;
967                 default:
968                         continue;
969                 }
970
971                 if (!browser->has_symbols)
972                         goto add_exit_option;
973
974                 if (browser->selection != NULL &&
975                     browser->selection->sym != NULL &&
976                     !browser->selection->map->dso->annotate_warned &&
977                     asprintf(&options[nr_options], "Annotate %s",
978                              browser->selection->sym->name) > 0)
979                         annotate = nr_options++;
980
981                 if (thread != NULL &&
982                     asprintf(&options[nr_options], "Zoom %s %s(%d) thread",
983                              (browser->hists->thread_filter ? "out of" : "into"),
984                              (thread->comm_set ? thread->comm : ""),
985                              thread->pid) > 0)
986                         zoom_thread = nr_options++;
987
988                 if (dso != NULL &&
989                     asprintf(&options[nr_options], "Zoom %s %s DSO",
990                              (browser->hists->dso_filter ? "out of" : "into"),
991                              (dso->kernel ? "the Kernel" : dso->short_name)) > 0)
992                         zoom_dso = nr_options++;
993
994                 if (browser->selection != NULL &&
995                     browser->selection->map != NULL &&
996                     asprintf(&options[nr_options], "Browse map details") > 0)
997                         browse_map = nr_options++;
998 add_exit_option:
999                 options[nr_options++] = (char *)"Exit";
1000
1001                 choice = ui__popup_menu(nr_options, options);
1002
1003                 for (i = 0; i < nr_options - 1; ++i)
1004                         free(options[i]);
1005
1006                 if (choice == nr_options - 1)
1007                         break;
1008
1009                 if (choice == -1)
1010                         continue;
1011
1012                 if (choice == annotate) {
1013                         struct hist_entry *he;
1014                         int err;
1015 do_annotate:
1016                         he = hist_browser__selected_entry(browser);
1017                         if (he == NULL)
1018                                 continue;
1019                         /*
1020                          * Don't let this be freed, say, by hists__decay_entry.
1021                          */
1022                         he->used = true;
1023                         err = hist_entry__tui_annotate(he, evsel->idx, nr_events,
1024                                                        timer, arg, delay_secs);
1025                         he->used = false;
1026                         ui_browser__update_nr_entries(&browser->b, browser->hists->nr_entries);
1027                         if (err)
1028                                 ui_browser__handle_resize(&browser->b);
1029                 } else if (choice == browse_map)
1030                         map__browse(browser->selection->map);
1031                 else if (choice == zoom_dso) {
1032 zoom_dso:
1033                         if (browser->hists->dso_filter) {
1034                                 pstack__remove(fstack, &browser->hists->dso_filter);
1035 zoom_out_dso:
1036                                 ui_helpline__pop();
1037                                 browser->hists->dso_filter = NULL;
1038                                 sort_dso.elide = false;
1039                         } else {
1040                                 if (dso == NULL)
1041                                         continue;
1042                                 ui_helpline__fpush("To zoom out press <- or -> + \"Zoom out of %s DSO\"",
1043                                                    dso->kernel ? "the Kernel" : dso->short_name);
1044                                 browser->hists->dso_filter = dso;
1045                                 sort_dso.elide = true;
1046                                 pstack__push(fstack, &browser->hists->dso_filter);
1047                         }
1048                         hists__filter_by_dso(self);
1049                         hist_browser__reset(browser);
1050                 } else if (choice == zoom_thread) {
1051 zoom_thread:
1052                         if (browser->hists->thread_filter) {
1053                                 pstack__remove(fstack, &browser->hists->thread_filter);
1054 zoom_out_thread:
1055                                 ui_helpline__pop();
1056                                 browser->hists->thread_filter = NULL;
1057                                 sort_thread.elide = false;
1058                         } else {
1059                                 ui_helpline__fpush("To zoom out press <- or -> + \"Zoom out of %s(%d) thread\"",
1060                                                    thread->comm_set ? thread->comm : "",
1061                                                    thread->pid);
1062                                 browser->hists->thread_filter = thread;
1063                                 sort_thread.elide = true;
1064                                 pstack__push(fstack, &browser->hists->thread_filter);
1065                         }
1066                         hists__filter_by_thread(self);
1067                         hist_browser__reset(browser);
1068                 }
1069         }
1070 out_free_stack:
1071         pstack__delete(fstack);
1072 out:
1073         hist_browser__delete(browser);
1074         return key;
1075 }
1076
1077 struct perf_evsel_menu {
1078         struct ui_browser b;
1079         struct perf_evsel *selection;
1080         bool lost_events, lost_events_warned;
1081 };
1082
1083 static void perf_evsel_menu__write(struct ui_browser *browser,
1084                                    void *entry, int row)
1085 {
1086         struct perf_evsel_menu *menu = container_of(browser,
1087                                                     struct perf_evsel_menu, b);
1088         struct perf_evsel *evsel = list_entry(entry, struct perf_evsel, node);
1089         bool current_entry = ui_browser__is_current_entry(browser, row);
1090         unsigned long nr_events = evsel->hists.stats.nr_events[PERF_RECORD_SAMPLE];
1091         const char *ev_name = event_name(evsel);
1092         char bf[256], unit;
1093         const char *warn = " ";
1094         size_t printed;
1095
1096         ui_browser__set_color(browser, current_entry ? HE_COLORSET_SELECTED :
1097                                                        HE_COLORSET_NORMAL);
1098
1099         nr_events = convert_unit(nr_events, &unit);
1100         printed = snprintf(bf, sizeof(bf), "%lu%c%s%s", nr_events,
1101                            unit, unit == ' ' ? "" : " ", ev_name);
1102         slsmg_printf("%s", bf);
1103
1104         nr_events = evsel->hists.stats.nr_events[PERF_RECORD_LOST];
1105         if (nr_events != 0) {
1106                 menu->lost_events = true;
1107                 if (!current_entry)
1108                         ui_browser__set_color(browser, HE_COLORSET_TOP);
1109                 nr_events = convert_unit(nr_events, &unit);
1110                 snprintf(bf, sizeof(bf), ": %ld%c%schunks LOST!", nr_events,
1111                          unit, unit == ' ' ? "" : " ");
1112                 warn = bf;
1113         }
1114
1115         slsmg_write_nstring(warn, browser->width - printed);
1116
1117         if (current_entry)
1118                 menu->selection = evsel;
1119 }
1120
1121 static int perf_evsel_menu__run(struct perf_evsel_menu *menu,
1122                                 int nr_events, const char *help,
1123                                 void(*timer)(void *arg), void *arg, int delay_secs)
1124 {
1125         struct perf_evlist *evlist = menu->b.priv;
1126         struct perf_evsel *pos;
1127         const char *ev_name, *title = "Available samples";
1128         int key;
1129
1130         if (ui_browser__show(&menu->b, title,
1131                              "ESC: exit, ENTER|->: Browse histograms") < 0)
1132                 return -1;
1133
1134         while (1) {
1135                 key = ui_browser__run(&menu->b, delay_secs);
1136
1137                 switch (key) {
1138                 case K_TIMER:
1139                         timer(arg);
1140
1141                         if (!menu->lost_events_warned && menu->lost_events) {
1142                                 ui_browser__warn_lost_events(&menu->b);
1143                                 menu->lost_events_warned = true;
1144                         }
1145                         continue;
1146                 case K_RIGHT:
1147                 case K_ENTER:
1148                         if (!menu->selection)
1149                                 continue;
1150                         pos = menu->selection;
1151 browse_hists:
1152                         perf_evlist__set_selected(evlist, pos);
1153                         /*
1154                          * Give the calling tool a chance to populate the non
1155                          * default evsel resorted hists tree.
1156                          */
1157                         if (timer)
1158                                 timer(arg);
1159                         ev_name = event_name(pos);
1160                         key = perf_evsel__hists_browse(pos, nr_events, help,
1161                                                        ev_name, true, timer,
1162                                                        arg, delay_secs);
1163                         ui_browser__show_title(&menu->b, title);
1164                         switch (key) {
1165                         case K_TAB:
1166                                 if (pos->node.next == &evlist->entries)
1167                                         pos = list_entry(evlist->entries.next, struct perf_evsel, node);
1168                                 else
1169                                         pos = list_entry(pos->node.next, struct perf_evsel, node);
1170                                 goto browse_hists;
1171                         case K_UNTAB:
1172                                 if (pos->node.prev == &evlist->entries)
1173                                         pos = list_entry(evlist->entries.prev, struct perf_evsel, node);
1174                                 else
1175                                         pos = list_entry(pos->node.prev, struct perf_evsel, node);
1176                                 goto browse_hists;
1177                         case K_ESC:
1178                                 if (!ui_browser__dialog_yesno(&menu->b,
1179                                                 "Do you really want to exit?"))
1180                                         continue;
1181                                 /* Fall thru */
1182                         case 'q':
1183                         case CTRL('c'):
1184                                 goto out;
1185                         default:
1186                                 continue;
1187                         }
1188                 case K_LEFT:
1189                         continue;
1190                 case K_ESC:
1191                         if (!ui_browser__dialog_yesno(&menu->b,
1192                                                "Do you really want to exit?"))
1193                                 continue;
1194                         /* Fall thru */
1195                 case 'q':
1196                 case CTRL('c'):
1197                         goto out;
1198                 default:
1199                         continue;
1200                 }
1201         }
1202
1203 out:
1204         ui_browser__hide(&menu->b);
1205         return key;
1206 }
1207
1208 static int __perf_evlist__tui_browse_hists(struct perf_evlist *evlist,
1209                                            const char *help,
1210                                            void(*timer)(void *arg), void *arg,
1211                                            int delay_secs)
1212 {
1213         struct perf_evsel *pos;
1214         struct perf_evsel_menu menu = {
1215                 .b = {
1216                         .entries    = &evlist->entries,
1217                         .refresh    = ui_browser__list_head_refresh,
1218                         .seek       = ui_browser__list_head_seek,
1219                         .write      = perf_evsel_menu__write,
1220                         .nr_entries = evlist->nr_entries,
1221                         .priv       = evlist,
1222                 },
1223         };
1224
1225         ui_helpline__push("Press ESC to exit");
1226
1227         list_for_each_entry(pos, &evlist->entries, node) {
1228                 const char *ev_name = event_name(pos);
1229                 size_t line_len = strlen(ev_name) + 7;
1230
1231                 if (menu.b.width < line_len)
1232                         menu.b.width = line_len;
1233                 /*
1234                  * Cache the evsel name, tracepoints have a _high_ cost per
1235                  * event_name() call.
1236                  */
1237                 if (pos->name == NULL)
1238                         pos->name = strdup(ev_name);
1239         }
1240
1241         return perf_evsel_menu__run(&menu, evlist->nr_entries, help, timer,
1242                                     arg, delay_secs);
1243 }
1244
1245 int perf_evlist__tui_browse_hists(struct perf_evlist *evlist, const char *help,
1246                                   void(*timer)(void *arg), void *arg,
1247                                   int delay_secs)
1248 {
1249
1250         if (evlist->nr_entries == 1) {
1251                 struct perf_evsel *first = list_entry(evlist->entries.next,
1252                                                       struct perf_evsel, node);
1253                 const char *ev_name = event_name(first);
1254                 return perf_evsel__hists_browse(first, evlist->nr_entries, help,
1255                                                 ev_name, false, timer, arg,
1256                                                 delay_secs);
1257         }
1258
1259         return __perf_evlist__tui_browse_hists(evlist, help,
1260                                                timer, arg, delay_secs);
1261 }