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