Pileus Git - ~andy/linux/blob - 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 }