tools/perf/util/ui/browsers/hists.c

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