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 "../../evsel.h"
  11 #include "../../evlist.h"
  12 #include "../../hist.h"
  13 #include "../../pstack.h"
  14 #include "../../sort.h"
  15 #include "../../util.h"
  16
  17 #include "../browser.h"
  18 #include "../helpline.h"
  19 #include "../util.h"
  20 #include "map.h"
  21
  22 struct hist_browser {
  23         struct ui_browser   b;
  24         struct hists        *hists;
  25         struct hist_entry   *he_selection;
  26         struct map_symbol   *selection;
  27         bool                 has_symbols;
  28 };
  29
  30 static int hists__browser_title(struct hists *self, char *bf, size_t size,
  31                                 const char *ev_name);
  32
  33 static void hist_browser__refresh_dimensions(struct hist_browser *self)
  34 {
  35         /* 3 == +/- toggle symbol before actual hist_entry rendering */
  36         self->b.width = 3 + (hists__sort_list_width(self->hists) +
  37                              sizeof("[k]"));
  38 }
  39
  40 static void hist_browser__reset(struct hist_browser *self)
  41 {
  42         self->b.nr_entries = self->hists->nr_entries;
  43         hist_browser__refresh_dimensions(self);
  44         ui_browser__reset_index(&self->b);
  45 }
  46
  47 static char tree__folded_sign(bool unfolded)
  48 {
  49         return unfolded ? '-' : '+';
  50 }
  51
  52 static char map_symbol__folded(const struct map_symbol *self)
  53 {
  54         return self->has_children ? tree__folded_sign(self->unfolded) : ' ';
  55 }
  56
  57 static char hist_entry__folded(const struct hist_entry *self)
  58 {
  59         return map_symbol__folded(&self->ms);
  60 }
  61
  62 static char callchain_list__folded(const struct callchain_list *self)
  63 {
  64         return map_symbol__folded(&self->ms);
  65 }
  66
  67 static void map_symbol__set_folding(struct map_symbol *self, bool unfold)
  68 {
  69         self->unfolded = unfold ? self->has_children : false;
  70 }
  71
  72 static int callchain_node__count_rows_rb_tree(struct callchain_node *self)
  73 {
  74         int n = 0;
  75         struct rb_node *nd;
  76
  77         for (nd = rb_first(&self->rb_root); nd; nd = rb_next(nd)) {
  78                 struct callchain_node *child = rb_entry(nd, struct callchain_node, rb_node);
  79                 struct callchain_list *chain;
  80                 char folded_sign = ' '; /* No children */
  81
  82                 list_for_each_entry(chain, &child->val, list) {
  83                         ++n;
  84                         /* We need this because we may not have children */
  85                         folded_sign = callchain_list__folded(chain);
  86                         if (folded_sign == '+')
  87                                 break;
  88                 }
  89
  90                 if (folded_sign == '-') /* Have children and they're unfolded */
  91                         n += callchain_node__count_rows_rb_tree(child);
  92         }
  93
  94         return n;
  95 }
  96
  97 static int callchain_node__count_rows(struct callchain_node *node)
  98 {
  99         struct callchain_list *chain;
 100         bool unfolded = false;
 101         int n = 0;
 102
 103         list_for_each_entry(chain, &node->val, list) {
 104                 ++n;
 105                 unfolded = chain->ms.unfolded;
 106         }
 107
 108         if (unfolded)
 109                 n += callchain_node__count_rows_rb_tree(node);
 110
 111         return n;
 112 }
 113
 114 static int callchain__count_rows(struct rb_root *chain)
 115 {
 116         struct rb_node *nd;
 117         int n = 0;
 118
 119         for (nd = rb_first(chain); nd; nd = rb_next(nd)) {
 120                 struct callchain_node *node = rb_entry(nd, struct callchain_node, rb_node);
 121                 n += callchain_node__count_rows(node);
 122         }
 123
 124         return n;
 125 }
 126
 127 static bool map_symbol__toggle_fold(struct map_symbol *self)
 128 {
 129         if (!self->has_children)
 130                 return false;
 131
 132         self->unfolded = !self->unfolded;
 133         return true;
 134 }
 135
 136 static void callchain_node__init_have_children_rb_tree(struct callchain_node *self)
 137 {
 138         struct rb_node *nd = rb_first(&self->rb_root);
 139
 140         for (nd = rb_first(&self->rb_root); nd; nd = rb_next(nd)) {
 141                 struct callchain_node *child = rb_entry(nd, struct callchain_node, rb_node);
 142                 struct callchain_list *chain;
 143                 bool first = true;
 144
 145                 list_for_each_entry(chain, &child->val, list) {
 146                         if (first) {
 147                                 first = false;
 148                                 chain->ms.has_children = chain->list.next != &child->val ||
 149                                                          !RB_EMPTY_ROOT(&child->rb_root);
 150                         } else
 151                                 chain->ms.has_children = chain->list.next == &child->val &&
 152                                                          !RB_EMPTY_ROOT(&child->rb_root);
 153                 }
 154
 155                 callchain_node__init_have_children_rb_tree(child);
 156         }
 157 }
 158
 159 static void callchain_node__init_have_children(struct callchain_node *self)
 160 {
 161         struct callchain_list *chain;
 162
 163         list_for_each_entry(chain, &self->val, list)
 164                 chain->ms.has_children = !RB_EMPTY_ROOT(&self->rb_root);
 165
 166         callchain_node__init_have_children_rb_tree(self);
 167 }
 168
 169 static void callchain__init_have_children(struct rb_root *self)
 170 {
 171         struct rb_node *nd;
 172
 173         for (nd = rb_first(self); nd; nd = rb_next(nd)) {
 174                 struct callchain_node *node = rb_entry(nd, struct callchain_node, rb_node);
 175                 callchain_node__init_have_children(node);
 176         }
 177 }
 178
 179 static void hist_entry__init_have_children(struct hist_entry *self)
 180 {
 181         if (!self->init_have_children) {
 182                 self->ms.has_children = !RB_EMPTY_ROOT(&self->sorted_chain);
 183                 callchain__init_have_children(&self->sorted_chain);
 184                 self->init_have_children = true;
 185         }
 186 }
 187
 188 static bool hist_browser__toggle_fold(struct hist_browser *self)
 189 {
 190         if (map_symbol__toggle_fold(self->selection)) {
 191                 struct hist_entry *he = self->he_selection;
 192
 193                 hist_entry__init_have_children(he);
 194                 self->hists->nr_entries -= he->nr_rows;
 195
 196                 if (he->ms.unfolded)
 197                         he->nr_rows = callchain__count_rows(&he->sorted_chain);
 198                 else
 199                         he->nr_rows = 0;
 200                 self->hists->nr_entries += he->nr_rows;
 201                 self->b.nr_entries = self->hists->nr_entries;
 202
 203                 return true;
 204         }
 205
 206         /* If it doesn't have children, no toggling performed */
 207         return false;
 208 }
 209
 210 static int callchain_node__set_folding_rb_tree(struct callchain_node *self, bool unfold)
 211 {
 212         int n = 0;
 213         struct rb_node *nd;
 214
 215         for (nd = rb_first(&self->rb_root); nd; nd = rb_next(nd)) {
 216                 struct callchain_node *child = rb_entry(nd, struct callchain_node, rb_node);
 217                 struct callchain_list *chain;
 218                 bool has_children = false;
 219
 220                 list_for_each_entry(chain, &child->val, list) {
 221                         ++n;
 222                         map_symbol__set_folding(&chain->ms, unfold);
 223                         has_children = chain->ms.has_children;
 224                 }
 225
 226                 if (has_children)
 227                         n += callchain_node__set_folding_rb_tree(child, unfold);
 228         }
 229
 230         return n;
 231 }
 232
 233 static int callchain_node__set_folding(struct callchain_node *node, bool unfold)
 234 {
 235         struct callchain_list *chain;
 236         bool has_children = false;
 237         int n = 0;
 238
 239         list_for_each_entry(chain, &node->val, list) {
 240                 ++n;
 241                 map_symbol__set_folding(&chain->ms, unfold);
 242                 has_children = chain->ms.has_children;
 243         }
 244
 245         if (has_children)
 246                 n += callchain_node__set_folding_rb_tree(node, unfold);
 247
 248         return n;
 249 }
 250
 251 static int callchain__set_folding(struct rb_root *chain, bool unfold)
 252 {
 253         struct rb_node *nd;
 254         int n = 0;
 255
 256         for (nd = rb_first(chain); nd; nd = rb_next(nd)) {
 257                 struct callchain_node *node = rb_entry(nd, struct callchain_node, rb_node);
 258                 n += callchain_node__set_folding(node, unfold);
 259         }
 260
 261         return n;
 262 }
 263
 264 static void hist_entry__set_folding(struct hist_entry *self, bool unfold)
 265 {
 266         hist_entry__init_have_children(self);
 267         map_symbol__set_folding(&self->ms, unfold);
 268
 269         if (self->ms.has_children) {
 270                 int n = callchain__set_folding(&self->sorted_chain, unfold);
 271                 self->nr_rows = unfold ? n : 0;
 272         } else
 273                 self->nr_rows = 0;
 274 }
 275
 276 static void hists__set_folding(struct hists *self, bool unfold)
 277 {
 278         struct rb_node *nd;
 279
 280         self->nr_entries = 0;
 281
 282         for (nd = rb_first(&self->entries); nd; nd = rb_next(nd)) {
 283                 struct hist_entry *he = rb_entry(nd, struct hist_entry, rb_node);
 284                 hist_entry__set_folding(he, unfold);
 285                 self->nr_entries += 1 + he->nr_rows;
 286         }
 287 }
 288
 289 static void hist_browser__set_folding(struct hist_browser *self, bool unfold)
 290 {
 291         hists__set_folding(self->hists, unfold);
 292         self->b.nr_entries = self->hists->nr_entries;
 293         /* Go to the start, we may be way after valid entries after a collapse */
 294         ui_browser__reset_index(&self->b);
 295 }
 296
 297 static int hist_browser__run(struct hist_browser *self, const char *ev_name,
 298                              void(*timer)(void *arg), void *arg, int delay_secs)
 299 {
 300         int key;
 301         char title[160];
 302
 303         self->b.entries = &self->hists->entries;
 304         self->b.nr_entries = self->hists->nr_entries;
 305
 306         hist_browser__refresh_dimensions(self);
 307         hists__browser_title(self->hists, title, sizeof(title), ev_name);
 308
 309         if (ui_browser__show(&self->b, title,
 310                              "Press '?' for help on key bindings") < 0)
 311                 return -1;
 312
 313         while (1) {
 314                 key = ui_browser__run(&self->b, delay_secs);
 315
 316                 switch (key) {
 317                 case -1:
 318                         /* FIXME we need to check if it was es.reason == NEWT_EXIT_TIMER */
 319                         timer(arg);
 320                         ui_browser__update_nr_entries(&self->b, self->hists->nr_entries);
 321                         hists__browser_title(self->hists, title, sizeof(title),
 322                                              ev_name);
 323                         ui_browser__show_title(&self->b, title);
 324                         continue;
 325                 case 'D': { /* Debug */
 326                         static int seq;
 327                         struct hist_entry *h = rb_entry(self->b.top,
 328                                                         struct hist_entry, rb_node);
 329                         ui_helpline__pop();
 330                         ui_helpline__fpush("%d: nr_ent=(%d,%d), height=%d, idx=%d, fve: idx=%d, row_off=%d, nrows=%d",
 331                                            seq++, self->b.nr_entries,
 332                                            self->hists->nr_entries,
 333                                            self->b.height,
 334                                            self->b.index,
 335                                            self->b.top_idx,
 336                                            h->row_offset, h->nr_rows);
 337                 }
 338                         break;
 339                 case 'C':
 340                         /* Collapse the whole world. */
 341                         hist_browser__set_folding(self, false);
 342                         break;
 343                 case 'E':
 344                         /* Expand the whole world. */
 345                         hist_browser__set_folding(self, true);
 346                         break;
 347                 case K_ENTER:
 348                         if (hist_browser__toggle_fold(self))
 349                                 break;
 350                         /* fall thru */
 351                 default:
 352                         goto out;
 353                 }
 354         }
 355 out:
 356         ui_browser__hide(&self->b);
 357         return key;
 358 }
 359
 360 static char *callchain_list__sym_name(struct callchain_list *self,
 361                                       char *bf, size_t bfsize)
 362 {
 363         if (self->ms.sym)
 364                 return self->ms.sym->name;
 365
 366         snprintf(bf, bfsize, "%#" PRIx64, self->ip);
 367         return bf;
 368 }
 369
 370 #define LEVEL_OFFSET_STEP 3
 371
 372 static int hist_browser__show_callchain_node_rb_tree(struct hist_browser *self,
 373                                                      struct callchain_node *chain_node,
 374                                                      u64 total, int level,
 375                                                      unsigned short row,
 376                                                      off_t *row_offset,
 377                                                      bool *is_current_entry)
 378 {
 379         struct rb_node *node;
 380         int first_row = row, width, offset = level * LEVEL_OFFSET_STEP;
 381         u64 new_total, remaining;
 382
 383         if (callchain_param.mode == CHAIN_GRAPH_REL)
 384                 new_total = chain_node->children_hit;
 385         else
 386                 new_total = total;
 387
 388         remaining = new_total;
 389         node = rb_first(&chain_node->rb_root);
 390         while (node) {
 391                 struct callchain_node *child = rb_entry(node, struct callchain_node, rb_node);
 392                 struct rb_node *next = rb_next(node);
 393                 u64 cumul = callchain_cumul_hits(child);
 394                 struct callchain_list *chain;
 395                 char folded_sign = ' ';
 396                 int first = true;
 397                 int extra_offset = 0;
 398
 399                 remaining -= cumul;
 400
 401                 list_for_each_entry(chain, &child->val, list) {
 402                         char ipstr[BITS_PER_LONG / 4 + 1], *alloc_str;
 403                         const char *str;
 404                         int color;
 405                         bool was_first = first;
 406
 407                         if (first)
 408                                 first = false;
 409                         else
 410                                 extra_offset = LEVEL_OFFSET_STEP;
 411
 412                         folded_sign = callchain_list__folded(chain);
 413                         if (*row_offset != 0) {
 414                                 --*row_offset;
 415                                 goto do_next;
 416                         }
 417
 418                         alloc_str = NULL;
 419                         str = callchain_list__sym_name(chain, ipstr, sizeof(ipstr));
 420                         if (was_first) {
 421                                 double percent = cumul * 100.0 / new_total;
 422
 423                                 if (asprintf(&alloc_str, "%2.2f%% %s", percent, str) < 0)
 424                                         str = "Not enough memory!";
 425                                 else
 426                                         str = alloc_str;
 427                         }
 428
 429                         color = HE_COLORSET_NORMAL;
 430                         width = self->b.width - (offset + extra_offset + 2);
 431                         if (ui_browser__is_current_entry(&self->b, row)) {
 432                                 self->selection = &chain->ms;
 433                                 color = HE_COLORSET_SELECTED;
 434                                 *is_current_entry = true;
 435                         }
 436
 437                         ui_browser__set_color(&self->b, color);
 438                         ui_browser__gotorc(&self->b, row, 0);
 439                         slsmg_write_nstring(" ", offset + extra_offset);
 440                         slsmg_printf("%c ", folded_sign);
 441                         slsmg_write_nstring(str, width);
 442                         free(alloc_str);
 443
 444                         if (++row == self->b.height)
 445                                 goto out;
 446 do_next:
 447                         if (folded_sign == '+')
 448                                 break;
 449                 }
 450
 451                 if (folded_sign == '-') {
 452                         const int new_level = level + (extra_offset ? 2 : 1);
 453                         row += hist_browser__show_callchain_node_rb_tree(self, child, new_total,
 454                                                                          new_level, row, row_offset,
 455                                                                          is_current_entry);
 456                 }
 457                 if (row == self->b.height)
 458                         goto out;
 459                 node = next;
 460         }
 461 out:
 462         return row - first_row;
 463 }
 464
 465 static int hist_browser__show_callchain_node(struct hist_browser *self,
 466                                              struct callchain_node *node,
 467                                              int level, unsigned short row,
 468                                              off_t *row_offset,
 469                                              bool *is_current_entry)
 470 {
 471         struct callchain_list *chain;
 472         int first_row = row,
 473              offset = level * LEVEL_OFFSET_STEP,
 474              width = self->b.width - offset;
 475         char folded_sign = ' ';
 476
 477         list_for_each_entry(chain, &node->val, list) {
 478                 char ipstr[BITS_PER_LONG / 4 + 1], *s;
 479                 int color;
 480
 481                 folded_sign = callchain_list__folded(chain);
 482
 483                 if (*row_offset != 0) {
 484                         --*row_offset;
 485                         continue;
 486                 }
 487
 488                 color = HE_COLORSET_NORMAL;
 489                 if (ui_browser__is_current_entry(&self->b, row)) {
 490                         self->selection = &chain->ms;
 491                         color = HE_COLORSET_SELECTED;
 492                         *is_current_entry = true;
 493                 }
 494
 495                 s = callchain_list__sym_name(chain, ipstr, sizeof(ipstr));
 496                 ui_browser__gotorc(&self->b, row, 0);
 497                 ui_browser__set_color(&self->b, color);
 498                 slsmg_write_nstring(" ", offset);
 499                 slsmg_printf("%c ", folded_sign);
 500                 slsmg_write_nstring(s, width - 2);
 501
 502                 if (++row == self->b.height)
 503                         goto out;
 504         }
 505
 506         if (folded_sign == '-')
 507                 row += hist_browser__show_callchain_node_rb_tree(self, node,
 508                                                                  self->hists->stats.total_period,
 509                                                                  level + 1, row,
 510                                                                  row_offset,
 511                                                                  is_current_entry);
 512 out:
 513         return row - first_row;
 514 }
 515
 516 static int hist_browser__show_callchain(struct hist_browser *self,
 517                                         struct rb_root *chain,
 518                                         int level, unsigned short row,
 519                                         off_t *row_offset,
 520                                         bool *is_current_entry)
 521 {
 522         struct rb_node *nd;
 523         int first_row = row;
 524
 525         for (nd = rb_first(chain); nd; nd = rb_next(nd)) {
 526                 struct callchain_node *node = rb_entry(nd, struct callchain_node, rb_node);
 527
 528                 row += hist_browser__show_callchain_node(self, node, level,
 529                                                          row, row_offset,
 530                                                          is_current_entry);
 531                 if (row == self->b.height)
 532                         break;
 533         }
 534
 535         return row - first_row;
 536 }
 537
 538 static int hist_browser__show_entry(struct hist_browser *self,
 539                                     struct hist_entry *entry,
 540                                     unsigned short row)
 541 {
 542         char s[256];
 543         double percent;
 544         int printed = 0;
 545         int width = self->b.width - 6; /* The percentage */
 546         char folded_sign = ' ';
 547         bool current_entry = ui_browser__is_current_entry(&self->b, row);
 548         off_t row_offset = entry->row_offset;
 549
 550         if (current_entry) {
 551                 self->he_selection = entry;
 552                 self->selection = &entry->ms;
 553         }
 554
 555         if (symbol_conf.use_callchain) {
 556                 hist_entry__init_have_children(entry);
 557                 folded_sign = hist_entry__folded(entry);
 558         }
 559
 560         if (row_offset == 0) {
 561                 hist_entry__snprintf(entry, s, sizeof(s), self->hists);
 562                 percent = (entry->period * 100.0) / self->hists->stats.total_period;
 563
 564                 ui_browser__set_percent_color(&self->b, percent, current_entry);
 565                 ui_browser__gotorc(&self->b, row, 0);
 566                 if (symbol_conf.use_callchain) {
 567                         slsmg_printf("%c ", folded_sign);
 568                         width -= 2;
 569                 }
 570
 571                 slsmg_printf(" %5.2f%%", percent);
 572
 573                 /* The scroll bar isn't being used */
 574                 if (!self->b.navkeypressed)
 575                         width += 1;
 576
 577                 if (!current_entry || !self->b.navkeypressed)
 578                         ui_browser__set_color(&self->b, HE_COLORSET_NORMAL);
 579
 580                 if (symbol_conf.show_nr_samples) {
 581                         slsmg_printf(" %11u", entry->nr_events);
 582                         width -= 12;
 583                 }
 584
 585                 if (symbol_conf.show_total_period) {
 586                         slsmg_printf(" %12" PRIu64, entry->period);
 587                         width -= 13;
 588                 }
 589
 590                 slsmg_write_nstring(s, width);
 591                 ++row;
 592                 ++printed;
 593         } else
 594                 --row_offset;
 595
 596         if (folded_sign == '-' && row != self->b.height) {
 597                 printed += hist_browser__show_callchain(self, &entry->sorted_chain,
 598                                                         1, row, &row_offset,
 599                                                         &current_entry);
 600                 if (current_entry)
 601                         self->he_selection = entry;
 602         }
 603
 604         return printed;
 605 }
 606
 607 static void ui_browser__hists_init_top(struct ui_browser *browser)
 608 {
 609         if (browser->top == NULL) {
 610                 struct hist_browser *hb;
 611
 612                 hb = container_of(browser, struct hist_browser, b);
 613                 browser->top = rb_first(&hb->hists->entries);
 614         }
 615 }
 616
 617 static unsigned int hist_browser__refresh(struct ui_browser *self)
 618 {
 619         unsigned row = 0;
 620         struct rb_node *nd;
 621         struct hist_browser *hb = container_of(self, struct hist_browser, b);
 622
 623         ui_browser__hists_init_top(self);
 624
 625         for (nd = self->top; nd; nd = rb_next(nd)) {
 626                 struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
 627
 628                 if (h->filtered)
 629                         continue;
 630
 631                 row += hist_browser__show_entry(hb, h, row);
 632                 if (row == self->height)
 633                         break;
 634         }
 635
 636         return row;
 637 }
 638
 639 static struct rb_node *hists__filter_entries(struct rb_node *nd)
 640 {
 641         while (nd != NULL) {
 642                 struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
 643                 if (!h->filtered)
 644                         return nd;
 645
 646                 nd = rb_next(nd);
 647         }
 648
 649         return NULL;
 650 }
 651
 652 static struct rb_node *hists__filter_prev_entries(struct rb_node *nd)
 653 {
 654         while (nd != NULL) {
 655                 struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
 656                 if (!h->filtered)
 657                         return nd;
 658
 659                 nd = rb_prev(nd);
 660         }
 661
 662         return NULL;
 663 }
 664
 665 static void ui_browser__hists_seek(struct ui_browser *self,
 666                                    off_t offset, int whence)
 667 {
 668         struct hist_entry *h;
 669         struct rb_node *nd;
 670         bool first = true;
 671
 672         if (self->nr_entries == 0)
 673                 return;
 674
 675         ui_browser__hists_init_top(self);
 676
 677         switch (whence) {
 678         case SEEK_SET:
 679                 nd = hists__filter_entries(rb_first(self->entries));
 680                 break;
 681         case SEEK_CUR:
 682                 nd = self->top;
 683                 goto do_offset;
 684         case SEEK_END:
 685                 nd = hists__filter_prev_entries(rb_last(self->entries));
 686                 first = false;
 687                 break;
 688         default:
 689                 return;
 690         }
 691
 692         /*
 693          * Moves not relative to the first visible entry invalidates its
 694          * row_offset:
 695          */
 696         h = rb_entry(self->top, struct hist_entry, rb_node);
 697         h->row_offset = 0;
 698
 699         /*
 700          * Here we have to check if nd is expanded (+), if it is we can't go
 701          * the next top level hist_entry, instead we must compute an offset of
 702          * what _not_ to show and not change the first visible entry.
 703          *
 704          * This offset increments when we are going from top to bottom and
 705          * decreases when we're going from bottom to top.
 706          *
 707          * As we don't have backpointers to the top level in the callchains
 708          * structure, we need to always print the whole hist_entry callchain,
 709          * skipping the first ones that are before the first visible entry
 710          * and stop when we printed enough lines to fill the screen.
 711          */
 712 do_offset:
 713         if (offset > 0) {
 714                 do {
 715                         h = rb_entry(nd, struct hist_entry, rb_node);
 716                         if (h->ms.unfolded) {
 717                                 u16 remaining = h->nr_rows - h->row_offset;
 718                                 if (offset > remaining) {
 719                                         offset -= remaining;
 720                                         h->row_offset = 0;
 721                                 } else {
 722                                         h->row_offset += offset;
 723                                         offset = 0;
 724                                         self->top = nd;
 725                                         break;
 726                                 }
 727                         }
 728                         nd = hists__filter_entries(rb_next(nd));
 729                         if (nd == NULL)
 730                                 break;
 731                         --offset;
 732                         self->top = nd;
 733                 } while (offset != 0);
 734         } else if (offset < 0) {
 735                 while (1) {
 736                         h = rb_entry(nd, struct hist_entry, rb_node);
 737                         if (h->ms.unfolded) {
 738                                 if (first) {
 739                                         if (-offset > h->row_offset) {
 740                                                 offset += h->row_offset;
 741                                                 h->row_offset = 0;
 742                                         } else {
 743                                                 h->row_offset += offset;
 744                                                 offset = 0;
 745                                                 self->top = nd;
 746                                                 break;
 747                                         }
 748                                 } else {
 749                                         if (-offset > h->nr_rows) {
 750                                                 offset += h->nr_rows;
 751                                                 h->row_offset = 0;
 752                                         } else {
 753                                                 h->row_offset = h->nr_rows + offset;
 754                                                 offset = 0;
 755                                                 self->top = nd;
 756                                                 break;
 757                                         }
 758                                 }
 759                         }
 760
 761                         nd = hists__filter_prev_entries(rb_prev(nd));
 762                         if (nd == NULL)
 763                                 break;
 764                         ++offset;
 765                         self->top = nd;
 766                         if (offset == 0) {
 767                                 /*
 768                                  * Last unfiltered hist_entry, check if it is
 769                                  * unfolded, if it is then we should have
 770                                  * row_offset at its last entry.
 771                                  */
 772                                 h = rb_entry(nd, struct hist_entry, rb_node);
 773                                 if (h->ms.unfolded)
 774                                         h->row_offset = h->nr_rows;
 775                                 break;
 776                         }
 777                         first = false;
 778                 }
 779         } else {
 780                 self->top = nd;
 781                 h = rb_entry(nd, struct hist_entry, rb_node);
 782                 h->row_offset = 0;
 783         }
 784 }
 785
 786 static struct hist_browser *hist_browser__new(struct hists *hists)
 787 {
 788         struct hist_browser *self = zalloc(sizeof(*self));
 789
 790         if (self) {
 791                 self->hists = hists;
 792                 self->b.refresh = hist_browser__refresh;
 793                 self->b.seek = ui_browser__hists_seek;
 794                 self->b.use_navkeypressed = true,
 795                 self->has_symbols = sort_sym.list.next != NULL;
 796         }
 797
 798         return self;
 799 }
 800
 801 static void hist_browser__delete(struct hist_browser *self)
 802 {
 803         free(self);
 804 }
 805
 806 static struct hist_entry *hist_browser__selected_entry(struct hist_browser *self)
 807 {
 808         return self->he_selection;
 809 }
 810
 811 static struct thread *hist_browser__selected_thread(struct hist_browser *self)
 812 {
 813         return self->he_selection->thread;
 814 }
 815
 816 static int hists__browser_title(struct hists *self, char *bf, size_t size,
 817                                 const char *ev_name)
 818 {
 819         char unit;
 820         int printed;
 821         const struct dso *dso = self->dso_filter;
 822         const struct thread *thread = self->thread_filter;
 823         unsigned long nr_events = self->stats.nr_events[PERF_RECORD_SAMPLE];
 824
 825         nr_events = convert_unit(nr_events, &unit);
 826         printed = snprintf(bf, size, "Events: %lu%c %s", nr_events, unit, ev_name);
 827
 828         if (thread)
 829                 printed += snprintf(bf + printed, size - printed,
 830                                     ", Thread: %s(%d)",
 831                                     (thread->comm_set ? thread->comm : ""),
 832                                     thread->pid);
 833         if (dso)
 834                 printed += snprintf(bf + printed, size - printed,
 835                                     ", DSO: %s", dso->short_name);
 836         return printed;
 837 }
 838
 839 static int perf_evsel__hists_browse(struct perf_evsel *evsel, int nr_events,
 840                                     const char *helpline, const char *ev_name,
 841                                     bool left_exits,
 842                                     void(*timer)(void *arg), void *arg,
 843                                     int delay_secs)
 844 {
 845         struct hists *self = &evsel->hists;
 846         struct hist_browser *browser = hist_browser__new(self);
 847         struct pstack *fstack;
 848         int key = -1;
 849
 850         if (browser == NULL)
 851                 return -1;
 852
 853         fstack = pstack__new(2);
 854         if (fstack == NULL)
 855                 goto out;
 856
 857         ui_helpline__push(helpline);
 858
 859         while (1) {
 860                 const struct thread *thread = NULL;
 861                 const struct dso *dso = NULL;
 862                 char *options[16];
 863                 int nr_options = 0, choice = 0, i,
 864                     annotate = -2, zoom_dso = -2, zoom_thread = -2,
 865                     browse_map = -2;
 866
 867                 key = hist_browser__run(browser, ev_name, timer, arg, delay_secs);
 868
 869                 if (browser->he_selection != NULL) {
 870                         thread = hist_browser__selected_thread(browser);
 871                         dso = browser->selection->map ? browser->selection->map->dso : NULL;
 872                 }
 873
 874                 switch (key) {
 875                 case K_TAB:
 876                 case K_UNTAB:
 877                         if (nr_events == 1)
 878                                 continue;
 879                         /*
 880                          * Exit the browser, let hists__browser_tree
 881                          * go to the next or previous
 882                          */
 883                         goto out_free_stack;
 884                 case 'a':
 885                         if (!browser->has_symbols) {
 886                                 ui__warning(
 887                         "Annotation is only available for symbolic views, "
 888                         "include \"sym\" in --sort to use it.");
 889                                 continue;
 890                         }
 891
 892                         if (browser->selection == NULL ||
 893                             browser->selection->sym == NULL ||
 894                             browser->selection->map->dso->annotate_warned)
 895                                 continue;
 896                         goto do_annotate;
 897                 case 'd':
 898                         goto zoom_dso;
 899                 case 't':
 900                         goto zoom_thread;
 901                 case K_F1:
 902                 case 'h':
 903                 case '?':
 904                         ui__help_window("h/?/F1        Show this window\n"
 905                                         "UP/DOWN/PGUP\n"
 906                                         "PGDN/SPACE    Navigate\n"
 907                                         "q/ESC/CTRL+C  Exit browser\n\n"
 908                                         "For multiple event sessions:\n\n"
 909                                         "TAB/UNTAB Switch events\n\n"
 910                                         "For symbolic views (--sort has sym):\n\n"
 911                                         "->            Zoom into DSO/Threads & Annotate current symbol\n"
 912                                         "<-            Zoom out\n"
 913                                         "a             Annotate current symbol\n"
 914                                         "C             Collapse all callchains\n"
 915                                         "E             Expand all callchains\n"
 916                                         "d             Zoom into current DSO\n"
 917                                         "t             Zoom into current Thread\n");
 918                         continue;
 919                 case K_ENTER:
 920                 case K_RIGHT:
 921                         /* menu */
 922                         break;
 923                 case K_LEFT: {
 924                         const void *top;
 925
 926                         if (pstack__empty(fstack)) {
 927                                 /*
 928                                  * Go back to the perf_evsel_menu__run or other user
 929                                  */
 930                                 if (left_exits)
 931                                         goto out_free_stack;
 932                                 continue;
 933                         }
 934                         top = pstack__pop(fstack);
 935                         if (top == &browser->hists->dso_filter)
 936                                 goto zoom_out_dso;
 937                         if (top == &browser->hists->thread_filter)
 938                                 goto zoom_out_thread;
 939                         continue;
 940                 }
 941                 case K_ESC:
 942                         if (!left_exits &&
 943                             !ui__dialog_yesno("Do you really want to exit?"))
 944                                 continue;
 945                         /* Fall thru */
 946                 case 'q':
 947                 case CTRL('c'):
 948                         goto out_free_stack;
 949                 default:
 950                         continue;
 951                 }
 952
 953                 if (!browser->has_symbols)
 954                         goto add_exit_option;
 955
 956                 if (browser->selection != NULL &&
 957                     browser->selection->sym != NULL &&
 958                     !browser->selection->map->dso->annotate_warned &&
 959                     asprintf(&options[nr_options], "Annotate %s",
 960                              browser->selection->sym->name) > 0)
 961                         annotate = nr_options++;
 962
 963                 if (thread != NULL &&
 964                     asprintf(&options[nr_options], "Zoom %s %s(%d) thread",
 965                              (browser->hists->thread_filter ? "out of" : "into"),
 966                              (thread->comm_set ? thread->comm : ""),
 967                              thread->pid) > 0)
 968                         zoom_thread = nr_options++;
 969
 970                 if (dso != NULL &&
 971                     asprintf(&options[nr_options], "Zoom %s %s DSO",
 972                              (browser->hists->dso_filter ? "out of" : "into"),
 973                              (dso->kernel ? "the Kernel" : dso->short_name)) > 0)
 974                         zoom_dso = nr_options++;
 975
 976                 if (browser->selection != NULL &&
 977                     browser->selection->map != NULL &&
 978                     asprintf(&options[nr_options], "Browse map details") > 0)
 979                         browse_map = nr_options++;
 980 add_exit_option:
 981                 options[nr_options++] = (char *)"Exit";
 982
 983                 choice = ui__popup_menu(nr_options, options);
 984
 985                 for (i = 0; i < nr_options - 1; ++i)
 986                         free(options[i]);
 987
 988                 if (choice == nr_options - 1)
 989                         break;
 990
 991                 if (choice == -1)
 992                         continue;
 993
 994                 if (choice == annotate) {
 995                         struct hist_entry *he;
 996 do_annotate:
 997                         he = hist_browser__selected_entry(browser);
 998                         if (he == NULL)
 999                                 continue;
1000                         /*
1001                          * Don't let this be freed, say, by hists__decay_entry.
1002                          */
1003                         he->used = true;
1004                         hist_entry__tui_annotate(he, evsel->idx, nr_events,
1005                                                  timer, arg, delay_secs);
1006                         he->used = false;
1007                         ui_browser__update_nr_entries(&browser->b, browser->hists->nr_entries);
1008                 } else if (choice == browse_map)
1009                         map__browse(browser->selection->map);
1010                 else if (choice == zoom_dso) {
1011 zoom_dso:
1012                         if (browser->hists->dso_filter) {
1013                                 pstack__remove(fstack, &browser->hists->dso_filter);
1014 zoom_out_dso:
1015                                 ui_helpline__pop();
1016                                 browser->hists->dso_filter = NULL;
1017                                 sort_dso.elide = false;
1018                         } else {
1019                                 if (dso == NULL)
1020                                         continue;
1021                                 ui_helpline__fpush("To zoom out press <- or -> + \"Zoom out of %s DSO\"",
1022                                                    dso->kernel ? "the Kernel" : dso->short_name);
1023                                 browser->hists->dso_filter = dso;
1024                                 sort_dso.elide = true;
1025                                 pstack__push(fstack, &browser->hists->dso_filter);
1026                         }
1027                         hists__filter_by_dso(self);
1028                         hist_browser__reset(browser);
1029                 } else if (choice == zoom_thread) {
1030 zoom_thread:
1031                         if (browser->hists->thread_filter) {
1032                                 pstack__remove(fstack, &browser->hists->thread_filter);
1033 zoom_out_thread:
1034                                 ui_helpline__pop();
1035                                 browser->hists->thread_filter = NULL;
1036                                 sort_thread.elide = false;
1037                         } else {
1038                                 ui_helpline__fpush("To zoom out press <- or -> + \"Zoom out of %s(%d) thread\"",
1039                                                    thread->comm_set ? thread->comm : "",
1040                                                    thread->pid);
1041                                 browser->hists->thread_filter = thread;
1042                                 sort_thread.elide = true;
1043                                 pstack__push(fstack, &browser->hists->thread_filter);
1044                         }
1045                         hists__filter_by_thread(self);
1046                         hist_browser__reset(browser);
1047                 }
1048         }
1049 out_free_stack:
1050         pstack__delete(fstack);
1051 out:
1052         hist_browser__delete(browser);
1053         return key;
1054 }
1055
1056 struct perf_evsel_menu {
1057         struct ui_browser b;
1058         struct perf_evsel *selection;
1059 };
1060
1061 static void perf_evsel_menu__write(struct ui_browser *browser,
1062                                    void *entry, int row)
1063 {
1064         struct perf_evsel_menu *menu = container_of(browser,
1065                                                     struct perf_evsel_menu, b);
1066         struct perf_evsel *evsel = list_entry(entry, struct perf_evsel, node);
1067         bool current_entry = ui_browser__is_current_entry(browser, row);
1068         unsigned long nr_events = evsel->hists.stats.nr_events[PERF_RECORD_SAMPLE];
1069         const char *ev_name = event_name(evsel);
1070         char bf[256], unit;
1071
1072         ui_browser__set_color(browser, current_entry ? HE_COLORSET_SELECTED :
1073                                                        HE_COLORSET_NORMAL);
1074
1075         nr_events = convert_unit(nr_events, &unit);
1076         snprintf(bf, sizeof(bf), "%lu%c%s%s", nr_events,
1077                  unit, unit == ' ' ? "" : " ", ev_name);
1078         slsmg_write_nstring(bf, browser->width);
1079
1080         if (current_entry)
1081                 menu->selection = evsel;
1082 }
1083
1084 static int perf_evsel_menu__run(struct perf_evsel_menu *menu,
1085                                 int nr_events, const char *help,
1086                                 void(*timer)(void *arg), void *arg, int delay_secs)
1087 {
1088         struct perf_evlist *evlist = menu->b.priv;
1089         struct perf_evsel *pos;
1090         const char *ev_name, *title = "Available samples";
1091         int key;
1092
1093         if (ui_browser__show(&menu->b, title,
1094                              "ESC: exit, ENTER|->: Browse histograms") < 0)
1095                 return -1;
1096
1097         while (1) {
1098                 key = ui_browser__run(&menu->b, delay_secs);
1099
1100                 switch (key) {
1101                 case K_TIMER:
1102                         timer(arg);
1103                         continue;
1104                 case K_RIGHT:
1105                 case K_ENTER:
1106                         if (!menu->selection)
1107                                 continue;
1108                         pos = menu->selection;
1109 browse_hists:
1110                         perf_evlist__set_selected(evlist, pos);
1111                         /*
1112                          * Give the calling tool a chance to populate the non
1113                          * default evsel resorted hists tree.
1114                          */
1115                         if (timer)
1116                                 timer(arg);
1117                         ev_name = event_name(pos);
1118                         key = perf_evsel__hists_browse(pos, nr_events, help,
1119                                                        ev_name, true, timer,
1120                                                        arg, delay_secs);
1121                         ui_browser__show_title(&menu->b, title);
1122                         switch (key) {
1123                         case K_TAB:
1124                                 if (pos->node.next == &evlist->entries)
1125                                         pos = list_entry(evlist->entries.next, struct perf_evsel, node);
1126                                 else
1127                                         pos = list_entry(pos->node.next, struct perf_evsel, node);
1128                                 goto browse_hists;
1129                         case K_UNTAB:
1130                                 if (pos->node.prev == &evlist->entries)
1131                                         pos = list_entry(evlist->entries.prev, struct perf_evsel, node);
1132                                 else
1133                                         pos = list_entry(pos->node.prev, struct perf_evsel, node);
1134                                 goto browse_hists;
1135                         case K_ESC:
1136                                 if (!ui__dialog_yesno("Do you really want to exit?"))
1137                                         continue;
1138                                 /* Fall thru */
1139                         case 'q':
1140                         case CTRL('c'):
1141                                 goto out;
1142                         default:
1143                                 continue;
1144                         }
1145                 case K_LEFT:
1146                         continue;
1147                 case K_ESC:
1148                         if (!ui__dialog_yesno("Do you really want to exit?"))
1149                                 continue;
1150                         /* Fall thru */
1151                 case 'q':
1152                 case CTRL('c'):
1153                         goto out;
1154                 default:
1155                         continue;
1156                 }
1157         }
1158
1159 out:
1160         ui_browser__hide(&menu->b);
1161         return key;
1162 }
1163
1164 static int __perf_evlist__tui_browse_hists(struct perf_evlist *evlist,
1165                                            const char *help,
1166                                            void(*timer)(void *arg), void *arg,
1167                                            int delay_secs)
1168 {
1169         struct perf_evsel *pos;
1170         struct perf_evsel_menu menu = {
1171                 .b = {
1172                         .entries    = &evlist->entries,
1173                         .refresh    = ui_browser__list_head_refresh,
1174                         .seek       = ui_browser__list_head_seek,
1175                         .write      = perf_evsel_menu__write,
1176                         .nr_entries = evlist->nr_entries,
1177                         .priv       = evlist,
1178                 },
1179         };
1180
1181         ui_helpline__push("Press ESC to exit");
1182
1183         list_for_each_entry(pos, &evlist->entries, node) {
1184                 const char *ev_name = event_name(pos);
1185                 size_t line_len = strlen(ev_name) + 7;
1186
1187                 if (menu.b.width < line_len)
1188                         menu.b.width = line_len;
1189                 /*
1190                  * Cache the evsel name, tracepoints have a _high_ cost per
1191                  * event_name() call.
1192                  */
1193                 if (pos->name == NULL)
1194                         pos->name = strdup(ev_name);
1195         }
1196
1197         return perf_evsel_menu__run(&menu, evlist->nr_entries, help, timer,
1198                                     arg, delay_secs);
1199 }
1200
1201 int perf_evlist__tui_browse_hists(struct perf_evlist *evlist, const char *help,
1202                                   void(*timer)(void *arg), void *arg,
1203                                   int delay_secs)
1204 {
1205
1206         if (evlist->nr_entries == 1) {
1207                 struct perf_evsel *first = list_entry(evlist->entries.next,
1208                                                       struct perf_evsel, node);
1209                 const char *ev_name = event_name(first);
1210                 return perf_evsel__hists_browse(first, evlist->nr_entries, help,
1211                                                 ev_name, false, timer, arg,
1212                                                 delay_secs);
1213         }
1214
1215         return __perf_evlist__tui_browse_hists(evlist, help,
1216                                                timer, arg, delay_secs);
1217 }