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