fc4a2b3aa65e66913c5986d83768280f17a68359
[linux-2.6.git] / tools / perf / util / newt.c
1 #define _GNU_SOURCE
2 #include <stdio.h>
3 #undef _GNU_SOURCE
4 /*
5  * slang versions <= 2.0.6 have a "#if HAVE_LONG_LONG" that breaks
6  * the build if it isn't defined. Use the equivalent one that glibc
7  * has on features.h.
8  */
9 #include <features.h>
10 #ifndef HAVE_LONG_LONG
11 #define HAVE_LONG_LONG __GLIBC_HAVE_LONG_LONG
12 #endif
13 #include <slang.h>
14 #include <signal.h>
15 #include <stdlib.h>
16 #include <elf.h>
17 #include <newt.h>
18 #include <sys/ttydefaults.h>
19
20 #include "cache.h"
21 #include "hist.h"
22 #include "pstack.h"
23 #include "session.h"
24 #include "sort.h"
25 #include "symbol.h"
26
27 #if SLANG_VERSION < 20104
28 #define slsmg_printf(msg, args...) SLsmg_printf((char *)msg, ##args)
29 #define slsmg_write_nstring(msg, len) SLsmg_write_nstring((char *)msg, len)
30 #define sltt_set_color(obj, name, fg, bg) SLtt_set_color(obj,(char *)name,\
31                                                          (char *)fg, (char *)bg)
32 #else
33 #define slsmg_printf SLsmg_printf
34 #define slsmg_write_nstring SLsmg_write_nstring
35 #define sltt_set_color SLtt_set_color
36 #endif
37
38 struct ui_progress {
39         newtComponent form, scale;
40 };
41
42 struct ui_progress *ui_progress__new(const char *title, u64 total)
43 {
44         struct ui_progress *self = malloc(sizeof(*self));
45
46         if (self != NULL) {
47                 int cols;
48
49                 if (use_browser <= 0)   
50                         return self;
51                 newtGetScreenSize(&cols, NULL);
52                 cols -= 4;
53                 newtCenteredWindow(cols, 1, title);
54                 self->form  = newtForm(NULL, NULL, 0);
55                 if (self->form == NULL)
56                         goto out_free_self;
57                 self->scale = newtScale(0, 0, cols, total);
58                 if (self->scale == NULL)
59                         goto out_free_form;
60                 newtFormAddComponent(self->form, self->scale);
61                 newtRefresh();
62         }
63
64         return self;
65
66 out_free_form:
67         newtFormDestroy(self->form);
68 out_free_self:
69         free(self);
70         return NULL;
71 }
72
73 void ui_progress__update(struct ui_progress *self, u64 curr)
74 {
75         /*
76          * FIXME: We should have a per UI backend way of showing progress,
77          * stdio will just show a percentage as NN%, etc.
78          */
79         if (use_browser <= 0)
80                 return;
81         newtScaleSet(self->scale, curr);
82         newtRefresh();
83 }
84
85 void ui_progress__delete(struct ui_progress *self)
86 {
87         if (use_browser > 0) {
88                 newtFormDestroy(self->form);
89                 newtPopWindow();
90         }
91         free(self);
92 }
93
94 static void ui_helpline__pop(void)
95 {
96         newtPopHelpLine();
97 }
98
99 static void ui_helpline__push(const char *msg)
100 {
101         newtPushHelpLine(msg);
102 }
103
104 static void ui_helpline__vpush(const char *fmt, va_list ap)
105 {
106         char *s;
107
108         if (vasprintf(&s, fmt, ap) < 0)
109                 vfprintf(stderr, fmt, ap);
110         else {
111                 ui_helpline__push(s);
112                 free(s);
113         }
114 }
115
116 static void ui_helpline__fpush(const char *fmt, ...)
117 {
118         va_list ap;
119
120         va_start(ap, fmt);
121         ui_helpline__vpush(fmt, ap);
122         va_end(ap);
123 }
124
125 static void ui_helpline__puts(const char *msg)
126 {
127         ui_helpline__pop();
128         ui_helpline__push(msg);
129 }
130
131 static char browser__last_msg[1024];
132
133 int browser__show_help(const char *format, va_list ap)
134 {
135         int ret;
136         static int backlog;
137
138         ret = vsnprintf(browser__last_msg + backlog,
139                         sizeof(browser__last_msg) - backlog, format, ap);
140         backlog += ret;
141
142         if (browser__last_msg[backlog - 1] == '\n') {
143                 ui_helpline__puts(browser__last_msg);
144                 newtRefresh();
145                 backlog = 0;
146         }
147
148         return ret;
149 }
150
151 static void newt_form__set_exit_keys(newtComponent self)
152 {
153         newtFormAddHotKey(self, NEWT_KEY_LEFT);
154         newtFormAddHotKey(self, NEWT_KEY_ESCAPE);
155         newtFormAddHotKey(self, 'Q');
156         newtFormAddHotKey(self, 'q');
157         newtFormAddHotKey(self, CTRL('c'));
158 }
159
160 static newtComponent newt_form__new(void)
161 {
162         newtComponent self = newtForm(NULL, NULL, 0);
163         if (self)
164                 newt_form__set_exit_keys(self);
165         return self;
166 }
167
168 static int popup_menu(int argc, char * const argv[])
169 {
170         struct newtExitStruct es;
171         int i, rc = -1, max_len = 5;
172         newtComponent listbox, form = newt_form__new();
173
174         if (form == NULL)
175                 return -1;
176
177         listbox = newtListbox(0, 0, argc, NEWT_FLAG_RETURNEXIT);
178         if (listbox == NULL)
179                 goto out_destroy_form;
180
181         newtFormAddComponent(form, listbox);
182
183         for (i = 0; i < argc; ++i) {
184                 int len = strlen(argv[i]);
185                 if (len > max_len)
186                         max_len = len;
187                 if (newtListboxAddEntry(listbox, argv[i], (void *)(long)i))
188                         goto out_destroy_form;
189         }
190
191         newtCenteredWindow(max_len, argc, NULL);
192         newtFormRun(form, &es);
193         rc = newtListboxGetCurrent(listbox) - NULL;
194         if (es.reason == NEWT_EXIT_HOTKEY)
195                 rc = -1;
196         newtPopWindow();
197 out_destroy_form:
198         newtFormDestroy(form);
199         return rc;
200 }
201
202 static int ui__help_window(const char *text)
203 {
204         struct newtExitStruct es;
205         newtComponent tb, form = newt_form__new();
206         int rc = -1;
207         int max_len = 0, nr_lines = 0;
208         const char *t;
209
210         if (form == NULL)
211                 return -1;
212
213         t = text;
214         while (1) {
215                 const char *sep = strchr(t, '\n');
216                 int len;
217
218                 if (sep == NULL)
219                         sep = strchr(t, '\0');
220                 len = sep - t;
221                 if (max_len < len)
222                         max_len = len;
223                 ++nr_lines;
224                 if (*sep == '\0')
225                         break;
226                 t = sep + 1;
227         }
228
229         tb = newtTextbox(0, 0, max_len, nr_lines, 0);
230         if (tb == NULL)
231                 goto out_destroy_form;
232
233         newtTextboxSetText(tb, text);
234         newtFormAddComponent(form, tb);
235         newtCenteredWindow(max_len, nr_lines, NULL);
236         newtFormRun(form, &es);
237         newtPopWindow();
238         rc = 0;
239 out_destroy_form:
240         newtFormDestroy(form);
241         return rc;
242 }
243
244 static bool dialog_yesno(const char *msg)
245 {
246         /* newtWinChoice should really be accepting const char pointers... */
247         char yes[] = "Yes", no[] = "No";
248         return newtWinChoice(NULL, yes, no, (char *)msg) == 1;
249 }
250
251 static void ui__error_window(const char *fmt, ...)
252 {
253         va_list ap;
254
255         va_start(ap, fmt);
256         newtWinMessagev((char *)"Error", (char *)"Ok", (char *)fmt, ap);
257         va_end(ap);
258 }
259
260 #define HE_COLORSET_TOP         50
261 #define HE_COLORSET_MEDIUM      51
262 #define HE_COLORSET_NORMAL      52
263 #define HE_COLORSET_SELECTED    53
264 #define HE_COLORSET_CODE        54
265
266 static int ui_browser__percent_color(double percent, bool current)
267 {
268         if (current)
269                 return HE_COLORSET_SELECTED;
270         if (percent >= MIN_RED)
271                 return HE_COLORSET_TOP;
272         if (percent >= MIN_GREEN)
273                 return HE_COLORSET_MEDIUM;
274         return HE_COLORSET_NORMAL;
275 }
276
277 struct ui_browser {
278         newtComponent   form, sb;
279         u64             index, first_visible_entry_idx;
280         void            *first_visible_entry, *entries;
281         u16             top, left, width, height;
282         void            *priv;
283         unsigned int    (*refresh_entries)(struct ui_browser *self);
284         void            (*write)(struct ui_browser *self, void *entry, int row);
285         void            (*seek)(struct ui_browser *self,
286                                 off_t offset, int whence);
287         u32             nr_entries;
288 };
289
290 static void ui_browser__list_head_seek(struct ui_browser *self,
291                                        off_t offset, int whence)
292 {
293         struct list_head *head = self->entries;
294         struct list_head *pos;
295
296         switch (whence) {
297         case SEEK_SET:
298                 pos = head->next;
299                 break;
300         case SEEK_CUR:
301                 pos = self->first_visible_entry;
302                 break;
303         case SEEK_END:
304                 pos = head->prev;
305                 break;
306         default:
307                 return;
308         }
309
310         if (offset > 0) {
311                 while (offset-- != 0)
312                         pos = pos->next;
313         } else {
314                 while (offset++ != 0)
315                         pos = pos->prev;
316         }
317
318         self->first_visible_entry = pos;
319 }
320
321 static void ui_browser__rb_tree_seek(struct ui_browser *self,
322                                      off_t offset, int whence)
323 {
324         struct rb_root *root = self->entries;
325         struct rb_node *nd;
326
327         switch (whence) {
328         case SEEK_SET:
329                 nd = rb_first(root);
330                 break;
331         case SEEK_CUR:
332                 nd = self->first_visible_entry;
333                 break;
334         case SEEK_END:
335                 nd = rb_last(root);
336                 break;
337         default:
338                 return;
339         }
340
341         if (offset > 0) {
342                 while (offset-- != 0)
343                         nd = rb_next(nd);
344         } else {
345                 while (offset++ != 0)
346                         nd = rb_prev(nd);
347         }
348
349         self->first_visible_entry = nd;
350 }
351
352 static unsigned int ui_browser__rb_tree_refresh(struct ui_browser *self)
353 {
354         struct rb_node *nd;
355         int row = 0;
356
357         if (self->first_visible_entry == NULL)
358                 self->first_visible_entry = rb_first(self->entries);
359
360         nd = self->first_visible_entry;
361
362         while (nd != NULL) {
363                 SLsmg_gotorc(self->top + row, self->left);
364                 self->write(self, nd, row);
365                 if (++row == self->height)
366                         break;
367                 nd = rb_next(nd);
368         }
369
370         return row;
371 }
372
373 static bool ui_browser__is_current_entry(struct ui_browser *self, unsigned row)
374 {
375         return (self->first_visible_entry_idx + row) == self->index;
376 }
377
378 static void ui_browser__refresh_dimensions(struct ui_browser *self)
379 {
380         int cols, rows;
381         newtGetScreenSize(&cols, &rows);
382
383         if (self->width > cols - 4)
384                 self->width = cols - 4;
385         self->height = rows - 5;
386         if (self->height > self->nr_entries)
387                 self->height = self->nr_entries;
388         self->top  = (rows - self->height) / 2;
389         self->left = (cols - self->width) / 2;
390 }
391
392 static void ui_browser__reset_index(struct ui_browser *self)
393 {
394         self->index = self->first_visible_entry_idx = 0;
395         self->seek(self, 0, SEEK_SET);
396 }
397
398 static int ui_browser__show(struct ui_browser *self, const char *title)
399 {
400         if (self->form != NULL) {
401                 newtFormDestroy(self->form);
402                 newtPopWindow();
403         }
404         ui_browser__refresh_dimensions(self);
405         newtCenteredWindow(self->width, self->height, title);
406         self->form = newt_form__new();
407         if (self->form == NULL)
408                 return -1;
409
410         self->sb = newtVerticalScrollbar(self->width, 0, self->height,
411                                          HE_COLORSET_NORMAL,
412                                          HE_COLORSET_SELECTED);
413         if (self->sb == NULL)
414                 return -1;
415
416         newtFormAddHotKey(self->form, NEWT_KEY_UP);
417         newtFormAddHotKey(self->form, NEWT_KEY_DOWN);
418         newtFormAddHotKey(self->form, NEWT_KEY_PGUP);
419         newtFormAddHotKey(self->form, NEWT_KEY_PGDN);
420         newtFormAddHotKey(self->form, NEWT_KEY_HOME);
421         newtFormAddHotKey(self->form, NEWT_KEY_END);
422         newtFormAddComponent(self->form, self->sb);
423         return 0;
424 }
425
426 static int objdump_line__show(struct objdump_line *self, struct list_head *head,
427                               int width, struct hist_entry *he, int len,
428                               bool current_entry)
429 {
430         if (self->offset != -1) {
431                 struct symbol *sym = he->ms.sym;
432                 unsigned int hits = 0;
433                 double percent = 0.0;
434                 int color;
435                 struct sym_priv *priv = symbol__priv(sym);
436                 struct sym_ext *sym_ext = priv->ext;
437                 struct sym_hist *h = priv->hist;
438                 s64 offset = self->offset;
439                 struct objdump_line *next = objdump__get_next_ip_line(head, self);
440
441                 while (offset < (s64)len &&
442                        (next == NULL || offset < next->offset)) {
443                         if (sym_ext) {
444                                 percent += sym_ext[offset].percent;
445                         } else
446                                 hits += h->ip[offset];
447
448                         ++offset;
449                 }
450
451                 if (sym_ext == NULL && h->sum)
452                         percent = 100.0 * hits / h->sum;
453
454                 color = ui_browser__percent_color(percent, current_entry);
455                 SLsmg_set_color(color);
456                 slsmg_printf(" %7.2f ", percent);
457                 if (!current_entry)
458                         SLsmg_set_color(HE_COLORSET_CODE);
459         } else {
460                 int color = ui_browser__percent_color(0, current_entry);
461                 SLsmg_set_color(color);
462                 slsmg_write_nstring(" ", 9);
463         }
464
465         SLsmg_write_char(':');
466         slsmg_write_nstring(" ", 8);
467         if (!*self->line)
468                 slsmg_write_nstring(" ", width - 18);
469         else
470                 slsmg_write_nstring(self->line, width - 18);
471
472         return 0;
473 }
474
475 static int ui_browser__refresh_entries(struct ui_browser *self)
476 {
477         int row;
478
479         newtScrollbarSet(self->sb, self->index, self->nr_entries - 1);
480         row = self->refresh_entries(self);
481         SLsmg_set_color(HE_COLORSET_NORMAL);
482         SLsmg_fill_region(self->top + row, self->left,
483                           self->height - row, self->width, ' ');
484
485         return 0;
486 }
487
488 static int ui_browser__run(struct ui_browser *self, struct newtExitStruct *es)
489 {
490         if (ui_browser__refresh_entries(self) < 0)
491                 return -1;
492
493         while (1) {
494                 off_t offset;
495
496                 newtFormRun(self->form, es);
497
498                 if (es->reason != NEWT_EXIT_HOTKEY)
499                         break;
500                 if (is_exit_key(es->u.key))
501                         return es->u.key;
502                 switch (es->u.key) {
503                 case NEWT_KEY_DOWN:
504                         if (self->index == self->nr_entries - 1)
505                                 break;
506                         ++self->index;
507                         if (self->index == self->first_visible_entry_idx + self->height) {
508                                 ++self->first_visible_entry_idx;
509                                 self->seek(self, +1, SEEK_CUR);
510                         }
511                         break;
512                 case NEWT_KEY_UP:
513                         if (self->index == 0)
514                                 break;
515                         --self->index;
516                         if (self->index < self->first_visible_entry_idx) {
517                                 --self->first_visible_entry_idx;
518                                 self->seek(self, -1, SEEK_CUR);
519                         }
520                         break;
521                 case NEWT_KEY_PGDN:
522                 case ' ':
523                         if (self->first_visible_entry_idx + self->height > self->nr_entries - 1)
524                                 break;
525
526                         offset = self->height;
527                         if (self->index + offset > self->nr_entries - 1)
528                                 offset = self->nr_entries - 1 - self->index;
529                         self->index += offset;
530                         self->first_visible_entry_idx += offset;
531                         self->seek(self, +offset, SEEK_CUR);
532                         break;
533                 case NEWT_KEY_PGUP:
534                         if (self->first_visible_entry_idx == 0)
535                                 break;
536
537                         if (self->first_visible_entry_idx < self->height)
538                                 offset = self->first_visible_entry_idx;
539                         else
540                                 offset = self->height;
541
542                         self->index -= offset;
543                         self->first_visible_entry_idx -= offset;
544                         self->seek(self, -offset, SEEK_CUR);
545                         break;
546                 case NEWT_KEY_HOME:
547                         ui_browser__reset_index(self);
548                         break;
549                 case NEWT_KEY_END:
550                         offset = self->height - 1;
551                         if (offset >= self->nr_entries)
552                                 offset = self->nr_entries - 1;
553
554                         self->index = self->nr_entries - 1;
555                         self->first_visible_entry_idx = self->index - offset;
556                         self->seek(self, -offset, SEEK_END);
557                         break;
558                 default:
559                         return es->u.key;
560                 }
561                 if (ui_browser__refresh_entries(self) < 0)
562                         return -1;
563         }
564         return 0;
565 }
566
567 static char *callchain_list__sym_name(struct callchain_list *self,
568                                       char *bf, size_t bfsize)
569 {
570         if (self->ms.sym)
571                 return self->ms.sym->name;
572
573         snprintf(bf, bfsize, "%#Lx", self->ip);
574         return bf;
575 }
576
577 static unsigned int hist_entry__annotate_browser_refresh(struct ui_browser *self)
578 {
579         struct objdump_line *pos;
580         struct list_head *head = self->entries;
581         struct hist_entry *he = self->priv;
582         int row = 0;
583         int len = he->ms.sym->end - he->ms.sym->start;
584
585         if (self->first_visible_entry == NULL || self->first_visible_entry == self->entries)
586                 self->first_visible_entry = head->next;
587
588         pos = list_entry(self->first_visible_entry, struct objdump_line, node);
589
590         list_for_each_entry_from(pos, head, node) {
591                 bool current_entry = ui_browser__is_current_entry(self, row);
592                 SLsmg_gotorc(self->top + row, self->left);
593                 objdump_line__show(pos, head, self->width,
594                                    he, len, current_entry);
595                 if (++row == self->height)
596                         break;
597         }
598
599         return row;
600 }
601
602 int hist_entry__tui_annotate(struct hist_entry *self)
603 {
604         struct ui_browser browser;
605         struct newtExitStruct es;
606         struct objdump_line *pos, *n;
607         LIST_HEAD(head);
608         int ret;
609
610         if (self->ms.sym == NULL)
611                 return -1;
612
613         if (self->ms.map->dso->annotate_warned)
614                 return -1;
615
616         if (hist_entry__annotate(self, &head) < 0) {
617                 ui__error_window(browser__last_msg);
618                 return -1;
619         }
620
621         ui_helpline__push("Press <- or ESC to exit");
622
623         memset(&browser, 0, sizeof(browser));
624         browser.entries         = &head;
625         browser.refresh_entries = hist_entry__annotate_browser_refresh;
626         browser.seek            = ui_browser__list_head_seek;
627         browser.priv = self;
628         list_for_each_entry(pos, &head, node) {
629                 size_t line_len = strlen(pos->line);
630                 if (browser.width < line_len)
631                         browser.width = line_len;
632                 ++browser.nr_entries;
633         }
634
635         browser.width += 18; /* Percentage */
636         ui_browser__show(&browser, self->ms.sym->name);
637         newtFormAddHotKey(browser.form, ' ');
638         ret = ui_browser__run(&browser, &es);
639         newtFormDestroy(browser.form);
640         newtPopWindow();
641         list_for_each_entry_safe(pos, n, &head, node) {
642                 list_del(&pos->node);
643                 objdump_line__free(pos);
644         }
645         ui_helpline__pop();
646         return ret;
647 }
648
649 /* -------------------------------------------------------------------- */
650
651 struct map_browser {
652         struct ui_browser b;
653         struct map        *map;
654         u16               namelen;
655         u8                addrlen;
656 };
657
658 static void map_browser__write(struct ui_browser *self, void *nd, int row)
659 {
660         struct symbol *sym = rb_entry(nd, struct symbol, rb_node);
661         struct map_browser *mb = container_of(self, struct map_browser, b);
662         bool current_entry = ui_browser__is_current_entry(self, row);
663         int color = ui_browser__percent_color(0, current_entry);
664
665         SLsmg_set_color(color);
666         slsmg_printf("%*llx %*llx %c ",
667                      mb->addrlen, sym->start, mb->addrlen, sym->end,
668                      sym->binding == STB_GLOBAL ? 'g' :
669                      sym->binding == STB_LOCAL  ? 'l' : 'w');
670         slsmg_write_nstring(sym->name, mb->namelen);
671 }
672
673 static int map__browse(struct map *self)
674 {
675         struct map_browser mb = {
676                 .b = {
677                         .entries = &self->dso->symbols[self->type],
678                         .refresh_entries = ui_browser__rb_tree_refresh,
679                         .seek    = ui_browser__rb_tree_seek,
680                         .write   = map_browser__write,
681                 },
682         };
683         struct newtExitStruct es;
684         struct rb_node *nd;
685         char tmp[BITS_PER_LONG / 4];
686         u64 maxaddr = 0;
687         int ret;
688
689         ui_helpline__push("Press <- or ESC to exit");
690
691         for (nd = rb_first(mb.b.entries); nd; nd = rb_next(nd)) {
692                 struct symbol *pos = rb_entry(nd, struct symbol, rb_node);
693
694                 if (mb.namelen < pos->namelen)
695                         mb.namelen = pos->namelen;
696                 if (maxaddr < pos->end)
697                         maxaddr = pos->end;
698                 ++mb.b.nr_entries;
699         }
700
701         mb.addrlen = snprintf(tmp, sizeof(tmp), "%llx", maxaddr);
702         mb.b.width += mb.addrlen * 2 + 4 + mb.namelen;
703         ui_browser__show(&mb.b, self->dso->long_name);
704         ret = ui_browser__run(&mb.b, &es);
705         newtFormDestroy(mb.b.form);
706         newtPopWindow();
707         ui_helpline__pop();
708         return ret;
709 }
710
711 /* -------------------------------------------------------------------- */
712
713 struct hist_browser {
714         struct ui_browser   b;
715         struct hists        *hists;
716         struct hist_entry   *he_selection;
717         struct map_symbol   *selection;
718 };
719
720 static void hist_browser__reset(struct hist_browser *self);
721 static int hist_browser__run(struct hist_browser *self, const char *title,
722                              struct newtExitStruct *es);
723 static unsigned int hist_browser__refresh_entries(struct ui_browser *self);
724 static void ui_browser__hists_seek(struct ui_browser *self,
725                                    off_t offset, int whence);
726
727 static struct hist_browser *hist_browser__new(struct hists *hists)
728 {
729         struct hist_browser *self = zalloc(sizeof(*self));
730
731         if (self) {
732                 self->hists = hists;
733                 self->b.refresh_entries = hist_browser__refresh_entries;
734                 self->b.seek = ui_browser__hists_seek;
735         }
736
737         return self;
738 }
739
740 static void hist_browser__delete(struct hist_browser *self)
741 {
742         newtFormDestroy(self->b.form);
743         newtPopWindow();
744         free(self);
745 }
746
747 static struct hist_entry *hist_browser__selected_entry(struct hist_browser *self)
748 {
749         return self->he_selection;
750 }
751
752 static struct thread *hist_browser__selected_thread(struct hist_browser *self)
753 {
754         return self->he_selection->thread;
755 }
756
757 static int hist_browser__title(char *bf, size_t size, const char *ev_name,
758                                const struct dso *dso, const struct thread *thread)
759 {
760         int printed = 0;
761
762         if (thread)
763                 printed += snprintf(bf + printed, size - printed,
764                                     "Thread: %s(%d)",
765                                     (thread->comm_set ?  thread->comm : ""),
766                                     thread->pid);
767         if (dso)
768                 printed += snprintf(bf + printed, size - printed,
769                                     "%sDSO: %s", thread ? " " : "",
770                                     dso->short_name);
771         return printed ?: snprintf(bf, size, "Event: %s", ev_name);
772 }
773
774 int hists__browse(struct hists *self, const char *helpline, const char *ev_name)
775 {
776         struct hist_browser *browser = hist_browser__new(self);
777         struct pstack *fstack;
778         const struct thread *thread_filter = NULL;
779         const struct dso *dso_filter = NULL;
780         struct newtExitStruct es;
781         char msg[160];
782         int key = -1;
783
784         if (browser == NULL)
785                 return -1;
786
787         fstack = pstack__new(2);
788         if (fstack == NULL)
789                 goto out;
790
791         ui_helpline__push(helpline);
792
793         hist_browser__title(msg, sizeof(msg), ev_name,
794                             dso_filter, thread_filter);
795
796         while (1) {
797                 const struct thread *thread;
798                 const struct dso *dso;
799                 char *options[16];
800                 int nr_options = 0, choice = 0, i,
801                     annotate = -2, zoom_dso = -2, zoom_thread = -2,
802                     browse_map = -2;
803
804                 if (hist_browser__run(browser, msg, &es))
805                         break;
806
807                 thread = hist_browser__selected_thread(browser);
808                 dso = browser->selection->map ? browser->selection->map->dso : NULL;
809
810                 if (es.reason == NEWT_EXIT_HOTKEY) {
811                         key = es.u.key;
812
813                         switch (key) {
814                         case NEWT_KEY_F1:
815                                 goto do_help;
816                         case NEWT_KEY_TAB:
817                         case NEWT_KEY_UNTAB:
818                                 /*
819                                  * Exit the browser, let hists__browser_tree
820                                  * go to the next or previous
821                                  */
822                                 goto out_free_stack;
823                         default:;
824                         }
825
826                         key = toupper(key);
827                         switch (key) {
828                         case 'A':
829                                 if (browser->selection->map == NULL &&
830                                     browser->selection->map->dso->annotate_warned)
831                                         continue;
832                                 goto do_annotate;
833                         case 'D':
834                                 goto zoom_dso;
835                         case 'T':
836                                 goto zoom_thread;
837                         case 'H':
838                         case '?':
839 do_help:
840                                 ui__help_window("->        Zoom into DSO/Threads & Annotate current symbol\n"
841                                                 "<-        Zoom out\n"
842                                                 "a         Annotate current symbol\n"
843                                                 "h/?/F1    Show this window\n"
844                                                 "d         Zoom into current DSO\n"
845                                                 "t         Zoom into current Thread\n"
846                                                 "q/CTRL+C  Exit browser");
847                                 continue;
848                         default:;
849                         }
850                         if (is_exit_key(key)) {
851                                 if (key == NEWT_KEY_ESCAPE) {
852                                         if (dialog_yesno("Do you really want to exit?"))
853                                                 break;
854                                         else
855                                                 continue;
856                                 } else
857                                         break;
858                         }
859
860                         if (es.u.key == NEWT_KEY_LEFT) {
861                                 const void *top;
862
863                                 if (pstack__empty(fstack))
864                                         continue;
865                                 top = pstack__pop(fstack);
866                                 if (top == &dso_filter)
867                                         goto zoom_out_dso;
868                                 if (top == &thread_filter)
869                                         goto zoom_out_thread;
870                                 continue;
871                         }
872                 }
873
874                 if (browser->selection->sym != NULL &&
875                     !browser->selection->map->dso->annotate_warned &&
876                     asprintf(&options[nr_options], "Annotate %s",
877                              browser->selection->sym->name) > 0)
878                         annotate = nr_options++;
879
880                 if (thread != NULL &&
881                     asprintf(&options[nr_options], "Zoom %s %s(%d) thread",
882                              (thread_filter ? "out of" : "into"),
883                              (thread->comm_set ? thread->comm : ""),
884                              thread->pid) > 0)
885                         zoom_thread = nr_options++;
886
887                 if (dso != NULL &&
888                     asprintf(&options[nr_options], "Zoom %s %s DSO",
889                              (dso_filter ? "out of" : "into"),
890                              (dso->kernel ? "the Kernel" : dso->short_name)) > 0)
891                         zoom_dso = nr_options++;
892
893                 if (browser->selection->map != NULL &&
894                     asprintf(&options[nr_options], "Browse map details") > 0)
895                         browse_map = nr_options++;
896
897                 options[nr_options++] = (char *)"Exit";
898
899                 choice = popup_menu(nr_options, options);
900
901                 for (i = 0; i < nr_options - 1; ++i)
902                         free(options[i]);
903
904                 if (choice == nr_options - 1)
905                         break;
906
907                 if (choice == -1)
908                         continue;
909
910                 if (choice == annotate) {
911                         struct hist_entry *he;
912 do_annotate:
913                         if (browser->selection->map->dso->origin == DSO__ORIG_KERNEL) {
914                                 browser->selection->map->dso->annotate_warned = 1;
915                                 ui_helpline__puts("No vmlinux file found, can't "
916                                                  "annotate with just a "
917                                                  "kallsyms file");
918                                 continue;
919                         }
920
921                         he = hist_browser__selected_entry(browser);
922                         if (he == NULL)
923                                 continue;
924
925                         hist_entry__tui_annotate(he);
926                 } else if (choice == browse_map)
927                         map__browse(browser->selection->map);
928                 else if (choice == zoom_dso) {
929 zoom_dso:
930                         if (dso_filter) {
931                                 pstack__remove(fstack, &dso_filter);
932 zoom_out_dso:
933                                 ui_helpline__pop();
934                                 dso_filter = NULL;
935                         } else {
936                                 if (dso == NULL)
937                                         continue;
938                                 ui_helpline__fpush("To zoom out press <- or -> + \"Zoom out of %s DSO\"",
939                                                    dso->kernel ? "the Kernel" : dso->short_name);
940                                 dso_filter = dso;
941                                 pstack__push(fstack, &dso_filter);
942                         }
943                         hists__filter_by_dso(self, dso_filter);
944                         hist_browser__title(msg, sizeof(msg), ev_name,
945                                             dso_filter, thread_filter);
946                         hist_browser__reset(browser);
947                 } else if (choice == zoom_thread) {
948 zoom_thread:
949                         if (thread_filter) {
950                                 pstack__remove(fstack, &thread_filter);
951 zoom_out_thread:
952                                 ui_helpline__pop();
953                                 thread_filter = NULL;
954                         } else {
955                                 ui_helpline__fpush("To zoom out press <- or -> + \"Zoom out of %s(%d) thread\"",
956                                                    thread->comm_set ? thread->comm : "",
957                                                    thread->pid);
958                                 thread_filter = thread;
959                                 pstack__push(fstack, &thread_filter);
960                         }
961                         hists__filter_by_thread(self, thread_filter);
962                         hist_browser__title(msg, sizeof(msg), ev_name,
963                                             dso_filter, thread_filter);
964                         hist_browser__reset(browser);
965                 }
966         }
967 out_free_stack:
968         pstack__delete(fstack);
969 out:
970         hist_browser__delete(browser);
971         return key;
972 }
973
974 int hists__tui_browse_tree(struct rb_root *self, const char *help)
975 {
976         struct rb_node *first = rb_first(self), *nd = first, *next;
977         int key = 0;
978
979         while (nd) {
980                 struct hists *hists = rb_entry(nd, struct hists, rb_node);
981                 const char *ev_name = __event_name(hists->type, hists->config);
982
983                 key = hists__browse(hists, help, ev_name);
984
985                 if (is_exit_key(key))
986                         break;
987
988                 switch (key) {
989                 case NEWT_KEY_TAB:
990                         next = rb_next(nd);
991                         if (next)
992                                 nd = next;
993                         break;
994                 case NEWT_KEY_UNTAB:
995                         if (nd == first)
996                                 continue;
997                         nd = rb_prev(nd);
998                 default:
999                         break;
1000                 }
1001         }
1002
1003         return key;
1004 }
1005
1006 static struct newtPercentTreeColors {
1007         const char *topColorFg, *topColorBg;
1008         const char *mediumColorFg, *mediumColorBg;
1009         const char *normalColorFg, *normalColorBg;
1010         const char *selColorFg, *selColorBg;
1011         const char *codeColorFg, *codeColorBg;
1012 } defaultPercentTreeColors = {
1013         "red",       "lightgray",
1014         "green",     "lightgray",
1015         "black",     "lightgray",
1016         "lightgray", "magenta",
1017         "blue",      "lightgray",
1018 };
1019
1020 static void newt_suspend(void *d __used)
1021 {
1022         newtSuspend();
1023         raise(SIGTSTP);
1024         newtResume();
1025 }
1026
1027 void setup_browser(void)
1028 {
1029         struct newtPercentTreeColors *c = &defaultPercentTreeColors;
1030
1031         if (!isatty(1) || !use_browser || dump_trace) {
1032                 use_browser = 0;
1033                 setup_pager();
1034                 return;
1035         }
1036
1037         use_browser = 1;
1038         newtInit();
1039         newtCls();
1040         newtSetSuspendCallback(newt_suspend, NULL);
1041         ui_helpline__puts(" ");
1042         sltt_set_color(HE_COLORSET_TOP, NULL, c->topColorFg, c->topColorBg);
1043         sltt_set_color(HE_COLORSET_MEDIUM, NULL, c->mediumColorFg, c->mediumColorBg);
1044         sltt_set_color(HE_COLORSET_NORMAL, NULL, c->normalColorFg, c->normalColorBg);
1045         sltt_set_color(HE_COLORSET_SELECTED, NULL, c->selColorFg, c->selColorBg);
1046         sltt_set_color(HE_COLORSET_CODE, NULL, c->codeColorFg, c->codeColorBg);
1047 }
1048
1049 void exit_browser(bool wait_for_ok)
1050 {
1051         if (use_browser > 0) {
1052                 if (wait_for_ok) {
1053                         char title[] = "Fatal Error", ok[] = "Ok";
1054                         newtWinMessage(title, ok, browser__last_msg);
1055                 }
1056                 newtFinished();
1057         }
1058 }
1059
1060 static void hist_browser__refresh_dimensions(struct hist_browser *self)
1061 {
1062         /* 3 == +/- toggle symbol before actual hist_entry rendering */
1063         self->b.width = 3 + (hists__sort_list_width(self->hists) +
1064                              sizeof("[k]"));
1065 }
1066
1067 static void hist_browser__reset(struct hist_browser *self)
1068 {
1069         self->b.nr_entries = self->hists->nr_entries;
1070         hist_browser__refresh_dimensions(self);
1071         ui_browser__reset_index(&self->b);
1072 }
1073
1074 static char tree__folded_sign(bool unfolded)
1075 {
1076         return unfolded ? '-' : '+';
1077 }
1078
1079 static char map_symbol__folded(const struct map_symbol *self)
1080 {
1081         return self->has_children ? tree__folded_sign(self->unfolded) : ' ';
1082 }
1083
1084 static char hist_entry__folded(const struct hist_entry *self)
1085 {
1086         return map_symbol__folded(&self->ms);
1087 }
1088
1089 static char callchain_list__folded(const struct callchain_list *self)
1090 {
1091         return map_symbol__folded(&self->ms);
1092 }
1093
1094 static bool map_symbol__toggle_fold(struct map_symbol *self)
1095 {
1096         if (!self->has_children)
1097                 return false;
1098
1099         self->unfolded = !self->unfolded;
1100         return true;
1101 }
1102
1103 #define LEVEL_OFFSET_STEP 3
1104
1105 static int hist_browser__show_callchain_node_rb_tree(struct hist_browser *self,
1106                                                      struct callchain_node *chain_node,
1107                                                      u64 total, int level,
1108                                                      unsigned short row,
1109                                                      off_t *row_offset,
1110                                                      bool *is_current_entry)
1111 {
1112         struct rb_node *node;
1113         int first_row = row, width, offset = level * LEVEL_OFFSET_STEP;
1114         u64 new_total, remaining;
1115
1116         if (callchain_param.mode == CHAIN_GRAPH_REL)
1117                 new_total = chain_node->children_hit;
1118         else
1119                 new_total = total;
1120
1121         remaining = new_total;
1122         node = rb_first(&chain_node->rb_root);
1123         while (node) {
1124                 struct callchain_node *child = rb_entry(node, struct callchain_node, rb_node);
1125                 struct rb_node *next = rb_next(node);
1126                 u64 cumul = cumul_hits(child);
1127                 struct callchain_list *chain;
1128                 char folded_sign = ' ';
1129                 int first = true;
1130                 int extra_offset = 0;
1131
1132                 remaining -= cumul;
1133
1134                 list_for_each_entry(chain, &child->val, list) {
1135                         char ipstr[BITS_PER_LONG / 4 + 1], *alloc_str;
1136                         const char *str;
1137                         int color;
1138                         bool was_first = first;
1139
1140                         if (first) {
1141                                 first = false;
1142                                 chain->ms.has_children = chain->list.next != &child->val ||
1143                                                          rb_first(&child->rb_root) != NULL;
1144                         } else {
1145                                 extra_offset = LEVEL_OFFSET_STEP;
1146                                 chain->ms.has_children = chain->list.next == &child->val &&
1147                                                          rb_first(&child->rb_root) != NULL;
1148                         }
1149
1150                         folded_sign = callchain_list__folded(chain);
1151                         if (*row_offset != 0) {
1152                                 --*row_offset;
1153                                 goto do_next;
1154                         }
1155
1156                         alloc_str = NULL;
1157                         str = callchain_list__sym_name(chain, ipstr, sizeof(ipstr));
1158                         if (was_first) {
1159                                 double percent = cumul * 100.0 / new_total;
1160
1161                                 if (asprintf(&alloc_str, "%2.2f%% %s", percent, str) < 0)
1162                                         str = "Not enough memory!";
1163                                 else
1164                                         str = alloc_str;
1165                         }
1166
1167                         color = HE_COLORSET_NORMAL;
1168                         width = self->b.width - (offset + extra_offset + 2);
1169                         if (ui_browser__is_current_entry(&self->b, row)) {
1170                                 self->selection = &chain->ms;
1171                                 color = HE_COLORSET_SELECTED;
1172                                 *is_current_entry = true;
1173                         }
1174
1175                         SLsmg_set_color(color);
1176                         SLsmg_gotorc(self->b.top + row, self->b.left);
1177                         slsmg_write_nstring(" ", offset + extra_offset);
1178                         slsmg_printf("%c ", folded_sign);
1179                         slsmg_write_nstring(str, width);
1180                         free(alloc_str);
1181
1182                         if (++row == self->b.height)
1183                                 goto out;
1184 do_next:
1185                         if (folded_sign == '+')
1186                                 break;
1187                 }
1188
1189                 if (folded_sign == '-') {
1190                         const int new_level = level + (extra_offset ? 2 : 1);
1191                         row += hist_browser__show_callchain_node_rb_tree(self, child, new_total,
1192                                                                          new_level, row, row_offset,
1193                                                                          is_current_entry);
1194                 }
1195                 if (row == self->b.height)
1196                         goto out;
1197                 node = next;
1198         }
1199 out:
1200         return row - first_row;
1201 }
1202
1203 static int hist_browser__show_callchain_node(struct hist_browser *self,
1204                                              struct callchain_node *node,
1205                                              int level, unsigned short row,
1206                                              off_t *row_offset,
1207                                              bool *is_current_entry)
1208 {
1209         struct callchain_list *chain;
1210         int first_row = row,
1211              offset = level * LEVEL_OFFSET_STEP,
1212              width = self->b.width - offset;
1213         char folded_sign = ' ';
1214
1215         list_for_each_entry(chain, &node->val, list) {
1216                 char ipstr[BITS_PER_LONG / 4 + 1], *s;
1217                 int color;
1218                 /*
1219                  * FIXME: This should be moved to somewhere else,
1220                  * probably when the callchain is created, so as not to
1221                  * traverse it all over again
1222                  */
1223                 chain->ms.has_children = rb_first(&node->rb_root) != NULL;
1224                 folded_sign = callchain_list__folded(chain);
1225
1226                 if (*row_offset != 0) {
1227                         --*row_offset;
1228                         continue;
1229                 }
1230
1231                 color = HE_COLORSET_NORMAL;
1232                 if (ui_browser__is_current_entry(&self->b, row)) {
1233                         self->selection = &chain->ms;
1234                         color = HE_COLORSET_SELECTED;
1235                         *is_current_entry = true;
1236                 }
1237
1238                 s = callchain_list__sym_name(chain, ipstr, sizeof(ipstr));
1239                 SLsmg_gotorc(self->b.top + row, self->b.left);
1240                 SLsmg_set_color(color);
1241                 slsmg_write_nstring(" ", offset);
1242                 slsmg_printf("%c ", folded_sign);
1243                 slsmg_write_nstring(s, width - 2);
1244
1245                 if (++row == self->b.height)
1246                         goto out;
1247         }
1248
1249         if (folded_sign == '-')
1250                 row += hist_browser__show_callchain_node_rb_tree(self, node,
1251                                                                  self->hists->stats.total_period,
1252                                                                  level + 1, row,
1253                                                                  row_offset,
1254                                                                  is_current_entry);
1255 out:
1256         return row - first_row;
1257 }
1258
1259 static int hist_browser__show_callchain(struct hist_browser *self,
1260                                         struct rb_root *chain,
1261                                         int level, unsigned short row,
1262                                         off_t *row_offset,
1263                                         bool *is_current_entry)
1264 {
1265         struct rb_node *nd;
1266         int first_row = row;
1267
1268         for (nd = rb_first(chain); nd; nd = rb_next(nd)) {
1269                 struct callchain_node *node = rb_entry(nd, struct callchain_node, rb_node);
1270
1271                 row += hist_browser__show_callchain_node(self, node, level,
1272                                                          row, row_offset,
1273                                                          is_current_entry);
1274                 if (row == self->b.height)
1275                         break;
1276         }
1277
1278         return row - first_row;
1279 }
1280
1281 static int hist_browser__show_entry(struct hist_browser *self,
1282                                     struct hist_entry *entry,
1283                                     unsigned short row)
1284 {
1285         char s[256];
1286         double percent;
1287         int printed = 0;
1288         int color, width = self->b.width;
1289         char folded_sign = ' ';
1290         bool current_entry = ui_browser__is_current_entry(&self->b, row);
1291         off_t row_offset = entry->row_offset;
1292
1293         if (current_entry) {
1294                 self->he_selection = entry;
1295                 self->selection = &entry->ms;
1296         }
1297
1298         if (symbol_conf.use_callchain) {
1299                 entry->ms.has_children = !RB_EMPTY_ROOT(&entry->sorted_chain);
1300                 folded_sign = hist_entry__folded(entry);
1301         }
1302
1303         if (row_offset == 0) {
1304                 hist_entry__snprintf(entry, s, sizeof(s), self->hists, NULL, false,
1305                                      0, false, self->hists->stats.total_period);
1306                 percent = (entry->period * 100.0) / self->hists->stats.total_period;
1307
1308                 color = HE_COLORSET_SELECTED;
1309                 if (!current_entry) {
1310                         if (percent >= MIN_RED)
1311                                 color = HE_COLORSET_TOP;
1312                         else if (percent >= MIN_GREEN)
1313                                 color = HE_COLORSET_MEDIUM;
1314                         else
1315                                 color = HE_COLORSET_NORMAL;
1316                 }
1317
1318                 SLsmg_set_color(color);
1319                 SLsmg_gotorc(self->b.top + row, self->b.left);
1320                 if (symbol_conf.use_callchain) {
1321                         slsmg_printf("%c ", folded_sign);
1322                         width -= 2;
1323                 }
1324                 slsmg_write_nstring(s, width);
1325                 ++row;
1326                 ++printed;
1327         } else
1328                 --row_offset;
1329
1330         if (folded_sign == '-' && row != self->b.height) {
1331                 printed += hist_browser__show_callchain(self, &entry->sorted_chain,
1332                                                         1, row, &row_offset,
1333                                                         &current_entry);
1334                 if (current_entry)
1335                         self->he_selection = entry;
1336         }
1337
1338         return printed;
1339 }
1340
1341 static unsigned int hist_browser__refresh_entries(struct ui_browser *self)
1342 {
1343         unsigned row = 0;
1344         struct rb_node *nd;
1345         struct hist_browser *hb = container_of(self, struct hist_browser, b);
1346
1347         if (self->first_visible_entry == NULL)
1348                 self->first_visible_entry = rb_first(&hb->hists->entries);
1349
1350         for (nd = self->first_visible_entry; nd; nd = rb_next(nd)) {
1351                 struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
1352
1353                 if (h->filtered)
1354                         continue;
1355
1356                 row += hist_browser__show_entry(hb, h, row);
1357                 if (row == self->height)
1358                         break;
1359         }
1360
1361         return row;
1362 }
1363
1364 static void callchain_node__init_have_children_rb_tree(struct callchain_node *self)
1365 {
1366         struct rb_node *nd = rb_first(&self->rb_root);
1367
1368         for (nd = rb_first(&self->rb_root); nd; nd = rb_next(nd)) {
1369                 struct callchain_node *child = rb_entry(nd, struct callchain_node, rb_node);
1370                 struct callchain_list *chain;
1371                 int first = true;
1372
1373                 list_for_each_entry(chain, &child->val, list) {
1374                         if (first) {
1375                                 first = false;
1376                                 chain->ms.has_children = chain->list.next != &child->val ||
1377                                                          rb_first(&child->rb_root) != NULL;
1378                         } else
1379                                 chain->ms.has_children = chain->list.next == &child->val &&
1380                                                          rb_first(&child->rb_root) != NULL;
1381                 }
1382
1383                 callchain_node__init_have_children_rb_tree(child);
1384         }
1385 }
1386
1387 static void callchain_node__init_have_children(struct callchain_node *self)
1388 {
1389         struct callchain_list *chain;
1390
1391         list_for_each_entry(chain, &self->val, list)
1392                 chain->ms.has_children = rb_first(&self->rb_root) != NULL;
1393
1394         callchain_node__init_have_children_rb_tree(self);
1395 }
1396
1397 static void callchain__init_have_children(struct rb_root *self)
1398 {
1399         struct rb_node *nd;
1400
1401         for (nd = rb_first(self); nd; nd = rb_next(nd)) {
1402                 struct callchain_node *node = rb_entry(nd, struct callchain_node, rb_node);
1403                 callchain_node__init_have_children(node);
1404         }
1405 }
1406
1407 static void hist_entry__init_have_children(struct hist_entry *self)
1408 {
1409         if (!self->init_have_children) {
1410                 callchain__init_have_children(&self->sorted_chain);
1411                 self->init_have_children = true;
1412         }
1413 }
1414
1415 static struct rb_node *hists__filter_entries(struct rb_node *nd)
1416 {
1417         while (nd != NULL) {
1418                 struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
1419                 if (!h->filtered)
1420                         return nd;
1421
1422                 nd = rb_next(nd);
1423         }
1424
1425         return NULL;
1426 }
1427
1428 static struct rb_node *hists__filter_prev_entries(struct rb_node *nd)
1429 {
1430         while (nd != NULL) {
1431                 struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
1432                 if (!h->filtered)
1433                         return nd;
1434
1435                 nd = rb_prev(nd);
1436         }
1437
1438         return NULL;
1439 }
1440
1441 static void ui_browser__hists_seek(struct ui_browser *self,
1442                                    off_t offset, int whence)
1443 {
1444         struct hist_entry *h;
1445         struct rb_node *nd;
1446         bool first = true;
1447
1448         switch (whence) {
1449         case SEEK_SET:
1450                 nd = hists__filter_entries(rb_first(self->entries));
1451                 break;
1452         case SEEK_CUR:
1453                 nd = self->first_visible_entry;
1454                 goto do_offset;
1455         case SEEK_END:
1456                 nd = hists__filter_prev_entries(rb_last(self->entries));
1457                 first = false;
1458                 break;
1459         default:
1460                 return;
1461         }
1462
1463         /*
1464          * Moves not relative to the first visible entry invalidates its
1465          * row_offset:
1466          */
1467         h = rb_entry(self->first_visible_entry, struct hist_entry, rb_node);
1468         h->row_offset = 0;
1469
1470         /*
1471          * Here we have to check if nd is expanded (+), if it is we can't go
1472          * the next top level hist_entry, instead we must compute an offset of
1473          * what _not_ to show and not change the first visible entry.
1474          *
1475          * This offset increments when we are going from top to bottom and
1476          * decreases when we're going from bottom to top.
1477          *
1478          * As we don't have backpointers to the top level in the callchains
1479          * structure, we need to always print the whole hist_entry callchain,
1480          * skipping the first ones that are before the first visible entry
1481          * and stop when we printed enough lines to fill the screen.
1482          */
1483 do_offset:
1484         if (offset > 0) {
1485                 do {
1486                         h = rb_entry(nd, struct hist_entry, rb_node);
1487                         if (h->ms.unfolded) {
1488                                 u16 remaining = h->nr_rows - h->row_offset;
1489                                 if (offset > remaining) {
1490                                         offset -= remaining;
1491                                         h->row_offset = 0;
1492                                 } else {
1493                                         h->row_offset += offset;
1494                                         offset = 0;
1495                                         self->first_visible_entry = nd;
1496                                         break;
1497                                 }
1498                         }
1499                         nd = hists__filter_entries(rb_next(nd));
1500                         if (nd == NULL)
1501                                 break;
1502                         --offset;
1503                         self->first_visible_entry = nd;
1504                 } while (offset != 0);
1505         } else if (offset < 0) {
1506                 while (1) {
1507                         h = rb_entry(nd, struct hist_entry, rb_node);
1508                         if (h->ms.unfolded) {
1509                                 if (first) {
1510                                         if (-offset > h->row_offset) {
1511                                                 offset += h->row_offset;
1512                                                 h->row_offset = 0;
1513                                         } else {
1514                                                 h->row_offset += offset;
1515                                                 offset = 0;
1516                                                 self->first_visible_entry = nd;
1517                                                 break;
1518                                         }
1519                                 } else {
1520                                         if (-offset > h->nr_rows) {
1521                                                 offset += h->nr_rows;
1522                                                 h->row_offset = 0;
1523                                         } else {
1524                                                 h->row_offset = h->nr_rows + offset;
1525                                                 offset = 0;
1526                                                 self->first_visible_entry = nd;
1527                                                 break;
1528                                         }
1529                                 }
1530                         }
1531
1532                         nd = hists__filter_prev_entries(rb_prev(nd));
1533                         if (nd == NULL)
1534                                 break;
1535                         ++offset;
1536                         self->first_visible_entry = nd;
1537                         if (offset == 0) {
1538                                 /*
1539                                  * Last unfiltered hist_entry, check if it is
1540                                  * unfolded, if it is then we should have
1541                                  * row_offset at its last entry.
1542                                  */
1543                                 h = rb_entry(nd, struct hist_entry, rb_node);
1544                                 if (h->ms.unfolded)
1545                                         h->row_offset = h->nr_rows;
1546                                 break;
1547                         }
1548                         first = false;
1549                 }
1550         } else {
1551                 self->first_visible_entry = nd;
1552                 h = rb_entry(nd, struct hist_entry, rb_node);
1553                 h->row_offset = 0;
1554         }
1555 }
1556
1557 static int callchain_node__count_rows_rb_tree(struct callchain_node *self)
1558 {
1559         int n = 0;
1560         struct rb_node *nd;
1561
1562         for (nd = rb_first(&self->rb_root); nd; nd = rb_next(nd)) {
1563                 struct callchain_node *child = rb_entry(nd, struct callchain_node, rb_node);
1564                 struct callchain_list *chain;
1565                 char folded_sign = ' '; /* No children */
1566
1567                 list_for_each_entry(chain, &child->val, list) {
1568                         ++n;
1569                         /* We need this because we may not have children */
1570                         folded_sign = callchain_list__folded(chain);
1571                         if (folded_sign == '+')
1572                                 break;
1573                 }
1574
1575                 if (folded_sign == '-') /* Have children and they're unfolded */
1576                         n += callchain_node__count_rows_rb_tree(child);
1577         }
1578
1579         return n;
1580 }
1581
1582 static int callchain_node__count_rows(struct callchain_node *node)
1583 {
1584         struct callchain_list *chain;
1585         bool unfolded = false;
1586         int n = 0;
1587
1588         list_for_each_entry(chain, &node->val, list) {
1589                 ++n;
1590                 unfolded = chain->ms.unfolded;
1591         }
1592
1593         if (unfolded)
1594                 n += callchain_node__count_rows_rb_tree(node);
1595
1596         return n;
1597 }
1598
1599 static int callchain__count_rows(struct rb_root *chain)
1600 {
1601         struct rb_node *nd;
1602         int n = 0;
1603
1604         for (nd = rb_first(chain); nd; nd = rb_next(nd)) {
1605                 struct callchain_node *node = rb_entry(nd, struct callchain_node, rb_node);
1606                 n += callchain_node__count_rows(node);
1607         }
1608
1609         return n;
1610 }
1611
1612 static bool hist_browser__toggle_fold(struct hist_browser *self)
1613 {
1614         if (map_symbol__toggle_fold(self->selection)) {
1615                 struct hist_entry *he = self->he_selection;
1616
1617                 hist_entry__init_have_children(he);
1618                 self->hists->nr_entries -= he->nr_rows;
1619
1620                 if (he->ms.unfolded)
1621                         he->nr_rows = callchain__count_rows(&he->sorted_chain);
1622                 else
1623                         he->nr_rows = 0;
1624                 self->hists->nr_entries += he->nr_rows;
1625                 self->b.nr_entries = self->hists->nr_entries;
1626
1627                 return true;
1628         }
1629
1630         /* If it doesn't have children, no toggling performed */
1631         return false;
1632 }
1633
1634 static int hist_browser__run(struct hist_browser *self, const char *title,
1635                              struct newtExitStruct *es)
1636 {
1637         char str[256], unit;
1638         unsigned long nr_events = self->hists->stats.nr_events[PERF_RECORD_SAMPLE];
1639
1640         self->b.entries = &self->hists->entries;
1641         self->b.nr_entries = self->hists->nr_entries;
1642
1643         hist_browser__refresh_dimensions(self);
1644
1645         nr_events = convert_unit(nr_events, &unit);
1646         snprintf(str, sizeof(str), "Events: %lu%c                            ",
1647                  nr_events, unit);
1648         newtDrawRootText(0, 0, str);
1649
1650         if (ui_browser__show(&self->b, title) < 0)
1651                 return -1;
1652
1653         newtFormAddHotKey(self->b.form, 'A');
1654         newtFormAddHotKey(self->b.form, 'a');
1655         newtFormAddHotKey(self->b.form, '?');
1656         newtFormAddHotKey(self->b.form, 'h');
1657         newtFormAddHotKey(self->b.form, 'H');
1658         newtFormAddHotKey(self->b.form, 'd');
1659
1660         newtFormAddHotKey(self->b.form, NEWT_KEY_LEFT);
1661         newtFormAddHotKey(self->b.form, NEWT_KEY_RIGHT);
1662         newtFormAddHotKey(self->b.form, NEWT_KEY_ENTER);
1663
1664         while (1) {
1665                 ui_browser__run(&self->b, es);
1666
1667                 if (es->reason != NEWT_EXIT_HOTKEY)
1668                         break;
1669                 switch (es->u.key) {
1670                 case 'd': { /* Debug */
1671                         static int seq;
1672                         struct hist_entry *h = rb_entry(self->b.first_visible_entry,
1673                                                         struct hist_entry, rb_node);
1674                         ui_helpline__pop();
1675                         ui_helpline__fpush("%d: nr_ent=(%d,%d), height=%d, idx=%d, fve: idx=%d, row_off=%d, nrows=%d",
1676                                            seq++, self->b.nr_entries,
1677                                            self->hists->nr_entries,
1678                                            self->b.height,
1679                                            self->b.index,
1680                                            self->b.first_visible_entry_idx,
1681                                            h->row_offset, h->nr_rows);
1682                 }
1683                         continue;
1684                 case NEWT_KEY_ENTER:
1685                         if (hist_browser__toggle_fold(self))
1686                                 break;
1687                         /* fall thru */
1688                 default:
1689                         return 0;
1690                 }
1691         }
1692         return 0;
1693 }