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