Pileus Git - ~andy/linux/blob - tools/perf/util/ui/browsers/hists.c

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