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