aboutsummaryrefslogtreecommitdiffstats
path: root/tools/perf/util
diff options
context:
space:
mode:
authorArnaldo Carvalho de Melo <acme@redhat.com>2010-07-26 16:13:40 -0400
committerArnaldo Carvalho de Melo <acme@redhat.com>2010-07-27 10:24:31 -0400
commit0f0cbf7aa3d3460a3eb201a772326739a0c0210a (patch)
tree9e2f4186acfd62a1a813abe576ffe6a35df9120d /tools/perf/util
parent8d8c369f3d697e31e04133ca18b516952549ee33 (diff)
perf ui: New hists tree widget
The stock newt checkbox tree widget we were using was not really suitable for hist entry + callchain browsing. The problems with it were manifold: - We needed to traverse the whole hist_entry rb_tree to add each entry + callchains beforehand. - No control over the colors used for each row So a new tree widget, based mostly on slang, was written. It extends the ui_browser class already used for annotate to allow the user to fold/unfold branches in the callchains tree, using extra fields in the symbol_map class that is embedded in hist_entry and callchain_node instances to store the folding state and when changing this state calculates the number of rows that are produced when showing a particular hist_entry instance. This greatly speeds up browsing as we don't have to upfront touch all the entries and only calculate callchain related operations when some callchain branch is actually unfolded. The memory footprint is also reduced as the data structure is not duplicated, just some extra fields for controling callchain state and to simplify the process of seeking thru entries (nr_rows, row_offset) were added. Cc: Frederic Weisbecker <fweisbec@gmail.com> Cc: Mike Galbraith <efault@gmx.de> Cc: Peter Zijlstra <peterz@infradead.org> Cc: Stephane Eranian <eranian@google.com> LKML-Reference: <new-submission> Signed-off-by: Arnaldo Carvalho de Melo <acme@redhat.com>
Diffstat (limited to 'tools/perf/util')
-rw-r--r--tools/perf/util/hist.c3
-rw-r--r--tools/perf/util/newt.c972
-rw-r--r--tools/perf/util/sort.h12
-rw-r--r--tools/perf/util/symbol.h2
4 files changed, 678 insertions, 311 deletions
diff --git a/tools/perf/util/hist.c b/tools/perf/util/hist.c
index f93095ffaab0..d0f07f7bdf16 100644
--- a/tools/perf/util/hist.c
+++ b/tools/perf/util/hist.c
@@ -885,6 +885,9 @@ static void hists__remove_entry_filter(struct hists *self, struct hist_entry *h,
885 return; 885 return;
886 886
887 ++self->nr_entries; 887 ++self->nr_entries;
888 if (h->ms.unfolded)
889 self->nr_entries += h->nr_rows;
890 h->row_offset = 0;
888 self->stats.total_period += h->period; 891 self->stats.total_period += h->period;
889 self->stats.nr_events[PERF_RECORD_SAMPLE] += h->nr_events; 892 self->stats.nr_events[PERF_RECORD_SAMPLE] += h->nr_events;
890 893
diff --git a/tools/perf/util/newt.c b/tools/perf/util/newt.c
index cdd958eb68cf..28f74eb8fe7c 100644
--- a/tools/perf/util/newt.c
+++ b/tools/perf/util/newt.c
@@ -509,38 +509,6 @@ static int ui_browser__run(struct ui_browser *self, struct newtExitStruct *es)
509 return 0; 509 return 0;
510} 510}
511 511
512/*
513 * When debugging newt problems it was useful to be able to "unroll"
514 * the calls to newtCheckBoxTreeAdd{Array,Item}, so that we can generate
515 * a source file with the sequence of calls to these methods, to then
516 * tweak the arrays to get the intended results, so I'm keeping this code
517 * here, may be useful again in the future.
518 */
519#undef NEWT_DEBUG
520
521static void newt_checkbox_tree__add(newtComponent tree, const char *str,
522 void *priv, int *indexes)
523{
524#ifdef NEWT_DEBUG
525 /* Print the newtCheckboxTreeAddArray to tinker with its index arrays */
526 int i = 0, len = 40 - strlen(str);
527
528 fprintf(stderr,
529 "\tnewtCheckboxTreeAddItem(tree, %*.*s\"%s\", (void *)%p, 0, ",
530 len, len, " ", str, priv);
531 while (indexes[i] != NEWT_ARG_LAST) {
532 if (indexes[i] != NEWT_ARG_APPEND)
533 fprintf(stderr, " %d,", indexes[i]);
534 else
535 fprintf(stderr, " %s,", "NEWT_ARG_APPEND");
536 ++i;
537 }
538 fprintf(stderr, " %s", " NEWT_ARG_LAST);\n");
539 fflush(stderr);
540#endif
541 newtCheckboxTreeAddArray(tree, str, priv, 0, indexes);
542}
543
544static char *callchain_list__sym_name(struct callchain_list *self, 512static char *callchain_list__sym_name(struct callchain_list *self,
545 char *bf, size_t bfsize) 513 char *bf, size_t bfsize)
546{ 514{
@@ -576,147 +544,6 @@ static unsigned int hist_entry__annotate_browser_refresh(struct ui_browser *self
576 return row; 544 return row;
577} 545}
578 546
579static void __callchain__append_graph_browser(struct callchain_node *self,
580 newtComponent tree, u64 total,
581 int *indexes, int depth)
582{
583 struct rb_node *node;
584 u64 new_total, remaining;
585 int idx = 0;
586
587 if (callchain_param.mode == CHAIN_GRAPH_REL)
588 new_total = self->children_hit;
589 else
590 new_total = total;
591
592 remaining = new_total;
593 node = rb_first(&self->rb_root);
594 while (node) {
595 struct callchain_node *child = rb_entry(node, struct callchain_node, rb_node);
596 struct rb_node *next = rb_next(node);
597 u64 cumul = cumul_hits(child);
598 struct callchain_list *chain;
599 int first = true, printed = 0;
600 int chain_idx = -1;
601 remaining -= cumul;
602
603 indexes[depth] = NEWT_ARG_APPEND;
604 indexes[depth + 1] = NEWT_ARG_LAST;
605
606 list_for_each_entry(chain, &child->val, list) {
607 char ipstr[BITS_PER_LONG / 4 + 1],
608 *alloc_str = NULL;
609 const char *str = callchain_list__sym_name(chain, ipstr, sizeof(ipstr));
610
611 if (first) {
612 double percent = cumul * 100.0 / new_total;
613
614 first = false;
615 if (asprintf(&alloc_str, "%2.2f%% %s", percent, str) < 0)
616 str = "Not enough memory!";
617 else
618 str = alloc_str;
619 } else {
620 indexes[depth] = idx;
621 indexes[depth + 1] = NEWT_ARG_APPEND;
622 indexes[depth + 2] = NEWT_ARG_LAST;
623 ++chain_idx;
624 }
625 newt_checkbox_tree__add(tree, str, &chain->ms, indexes);
626 free(alloc_str);
627 ++printed;
628 }
629
630 indexes[depth] = idx;
631 if (chain_idx != -1)
632 indexes[depth + 1] = chain_idx;
633 if (printed != 0)
634 ++idx;
635 __callchain__append_graph_browser(child, tree, new_total, indexes,
636 depth + (chain_idx != -1 ? 2 : 1));
637 node = next;
638 }
639}
640
641static void callchain__append_graph_browser(struct callchain_node *self,
642 newtComponent tree, u64 total,
643 int *indexes, int parent_idx)
644{
645 struct callchain_list *chain;
646 int i = 0;
647
648 indexes[1] = NEWT_ARG_APPEND;
649 indexes[2] = NEWT_ARG_LAST;
650
651 list_for_each_entry(chain, &self->val, list) {
652 char ipstr[BITS_PER_LONG / 4 + 1], *str;
653
654 if (chain->ip >= PERF_CONTEXT_MAX)
655 continue;
656
657 if (!i++ && sort__first_dimension == SORT_SYM)
658 continue;
659
660 str = callchain_list__sym_name(chain, ipstr, sizeof(ipstr));
661 newt_checkbox_tree__add(tree, str, &chain->ms, indexes);
662 }
663
664 indexes[1] = parent_idx;
665 indexes[2] = NEWT_ARG_APPEND;
666 indexes[3] = NEWT_ARG_LAST;
667 __callchain__append_graph_browser(self, tree, total, indexes, 2);
668}
669
670static void hist_entry__append_callchain_browser(struct hist_entry *self,
671 newtComponent tree, u64 total, int parent_idx)
672{
673 struct rb_node *rb_node;
674 int indexes[1024] = { [0] = parent_idx, };
675 int idx = 0;
676 struct callchain_node *chain;
677
678 rb_node = rb_first(&self->sorted_chain);
679 while (rb_node) {
680 chain = rb_entry(rb_node, struct callchain_node, rb_node);
681 switch (callchain_param.mode) {
682 case CHAIN_FLAT:
683 break;
684 case CHAIN_GRAPH_ABS: /* falldown */
685 case CHAIN_GRAPH_REL:
686 callchain__append_graph_browser(chain, tree, total, indexes, idx++);
687 break;
688 case CHAIN_NONE:
689 default:
690 break;
691 }
692 rb_node = rb_next(rb_node);
693 }
694}
695
696static size_t hist_entry__append_browser(struct hist_entry *self,
697 newtComponent tree,
698 struct hists *hists)
699{
700 char s[256];
701 size_t ret;
702
703 if (symbol_conf.exclude_other && !self->parent)
704 return 0;
705
706 ret = hist_entry__snprintf(self, s, sizeof(s), hists, NULL,
707 false, 0, false, hists->stats.total_period);
708 if (symbol_conf.use_callchain) {
709 int indexes[2];
710
711 indexes[0] = NEWT_ARG_APPEND;
712 indexes[1] = NEWT_ARG_LAST;
713 newt_checkbox_tree__add(tree, s, &self->ms, indexes);
714 } else
715 newtListboxAppendEntry(tree, s, &self->ms);
716
717 return ret;
718}
719
720int hist_entry__tui_annotate(struct hist_entry *self) 547int hist_entry__tui_annotate(struct hist_entry *self)
721{ 548{
722 struct ui_browser browser; 549 struct ui_browser browser;
@@ -764,157 +591,48 @@ int hist_entry__tui_annotate(struct hist_entry *self)
764 return ret; 591 return ret;
765} 592}
766 593
767static const void *newt__symbol_tree_get_current(newtComponent self)
768{
769 if (symbol_conf.use_callchain)
770 return newtCheckboxTreeGetCurrent(self);
771 return newtListboxGetCurrent(self);
772}
773
774static void hist_browser__selection(newtComponent self, void *data)
775{
776 const struct map_symbol **symbol_ptr = data;
777 *symbol_ptr = newt__symbol_tree_get_current(self);
778}
779
780struct hist_browser { 594struct hist_browser {
781 newtComponent form, tree; 595 struct ui_browser b;
782 const struct map_symbol *selection; 596 struct hists *hists;
597 struct hist_entry *he_selection;
598 struct map_symbol *selection;
783}; 599};
784 600
785static struct hist_browser *hist_browser__new(void) 601static void hist_browser__reset(struct hist_browser *self);
602static int hist_browser__run(struct hist_browser *self, const char *title,
603 struct newtExitStruct *es);
604static unsigned int hist_browser__refresh_entries(struct ui_browser *self);
605static void ui_browser__hists_seek(struct ui_browser *self,
606 off_t offset, int whence);
607
608static struct hist_browser *hist_browser__new(struct hists *hists)
786{ 609{
787 struct hist_browser *self = malloc(sizeof(*self)); 610 struct hist_browser *self = zalloc(sizeof(*self));
788 611
789 if (self != NULL) 612 if (self) {
790 self->form = NULL; 613 self->hists = hists;
614 self->b.refresh_entries = hist_browser__refresh_entries;
615 self->b.seek = ui_browser__hists_seek;
616 }
791 617
792 return self; 618 return self;
793} 619}
794 620
795static void hist_browser__delete(struct hist_browser *self) 621static void hist_browser__delete(struct hist_browser *self)
796{ 622{
797 newtFormDestroy(self->form); 623 newtFormDestroy(self->b.form);
798 newtPopWindow(); 624 newtPopWindow();
799 free(self); 625 free(self);
800} 626}
801 627
802static int hist_browser__populate(struct hist_browser *self, struct hists *hists,
803 const char *title)
804{
805 int max_len = 0, idx, cols, rows;
806 struct ui_progress *progress;
807 struct rb_node *nd;
808 u64 curr_hist = 0;
809 char seq[] = ".", unit;
810 char str[256];
811 unsigned long nr_events = hists->stats.nr_events[PERF_RECORD_SAMPLE];
812
813 if (self->form) {
814 newtFormDestroy(self->form);
815 newtPopWindow();
816 }
817
818 nr_events = convert_unit(nr_events, &unit);
819 snprintf(str, sizeof(str), "Events: %lu%c ",
820 nr_events, unit);
821 newtDrawRootText(0, 0, str);
822
823 newtGetScreenSize(NULL, &rows);
824
825 if (symbol_conf.use_callchain)
826 self->tree = newtCheckboxTreeMulti(0, 0, rows - 5, seq,
827 NEWT_FLAG_SCROLL);
828 else
829 self->tree = newtListbox(0, 0, rows - 5,
830 (NEWT_FLAG_SCROLL |
831 NEWT_FLAG_RETURNEXIT));
832
833 newtComponentAddCallback(self->tree, hist_browser__selection,
834 &self->selection);
835
836 progress = ui_progress__new("Adding entries to the browser...",
837 hists->nr_entries);
838 if (progress == NULL)
839 return -1;
840
841 idx = 0;
842 for (nd = rb_first(&hists->entries); nd; nd = rb_next(nd)) {
843 struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
844 int len;
845
846 if (h->filtered)
847 continue;
848
849 len = hist_entry__append_browser(h, self->tree, hists);
850 if (len > max_len)
851 max_len = len;
852 if (symbol_conf.use_callchain)
853 hist_entry__append_callchain_browser(h, self->tree,
854 hists->stats.total_period, idx++);
855 ++curr_hist;
856 if (curr_hist % 5)
857 ui_progress__update(progress, curr_hist);
858 }
859
860 ui_progress__delete(progress);
861
862 newtGetScreenSize(&cols, &rows);
863
864 if (max_len > cols)
865 max_len = cols - 3;
866
867 if (!symbol_conf.use_callchain)
868 newtListboxSetWidth(self->tree, max_len);
869
870 newtCenteredWindow(max_len + (symbol_conf.use_callchain ? 5 : 0),
871 rows - 5, title);
872 self->form = newt_form__new();
873 if (self->form == NULL)
874 return -1;
875
876 newtFormAddHotKey(self->form, 'A');
877 newtFormAddHotKey(self->form, 'a');
878 newtFormAddHotKey(self->form, 'D');
879 newtFormAddHotKey(self->form, 'd');
880 newtFormAddHotKey(self->form, 'T');
881 newtFormAddHotKey(self->form, 't');
882 newtFormAddHotKey(self->form, '?');
883 newtFormAddHotKey(self->form, 'H');
884 newtFormAddHotKey(self->form, 'h');
885 newtFormAddHotKey(self->form, NEWT_KEY_F1);
886 newtFormAddHotKey(self->form, NEWT_KEY_RIGHT);
887 newtFormAddHotKey(self->form, NEWT_KEY_TAB);
888 newtFormAddHotKey(self->form, NEWT_KEY_UNTAB);
889 newtFormAddComponents(self->form, self->tree, NULL);
890 self->selection = newt__symbol_tree_get_current(self->tree);
891
892 return 0;
893}
894
895static struct hist_entry *hist_browser__selected_entry(struct hist_browser *self) 628static struct hist_entry *hist_browser__selected_entry(struct hist_browser *self)
896{ 629{
897 int *indexes; 630 return self->he_selection;
898
899 if (!symbol_conf.use_callchain)
900 goto out;
901
902 indexes = newtCheckboxTreeFindItem(self->tree, (void *)self->selection);
903 if (indexes) {
904 bool is_hist_entry = indexes[1] == NEWT_ARG_LAST;
905 free(indexes);
906 if (is_hist_entry)
907 goto out;
908 }
909 return NULL;
910out:
911 return container_of(self->selection, struct hist_entry, ms);
912} 631}
913 632
914static struct thread *hist_browser__selected_thread(struct hist_browser *self) 633static struct thread *hist_browser__selected_thread(struct hist_browser *self)
915{ 634{
916 struct hist_entry *he = hist_browser__selected_entry(self); 635 return self->he_selection->thread;
917 return he ? he->thread : NULL;
918} 636}
919 637
920static int hist_browser__title(char *bf, size_t size, const char *ev_name, 638static int hist_browser__title(char *bf, size_t size, const char *ev_name,
@@ -936,7 +654,7 @@ static int hist_browser__title(char *bf, size_t size, const char *ev_name,
936 654
937int hists__browse(struct hists *self, const char *helpline, const char *ev_name) 655int hists__browse(struct hists *self, const char *helpline, const char *ev_name)
938{ 656{
939 struct hist_browser *browser = hist_browser__new(); 657 struct hist_browser *browser = hist_browser__new(self);
940 struct pstack *fstack; 658 struct pstack *fstack;
941 const struct thread *thread_filter = NULL; 659 const struct thread *thread_filter = NULL;
942 const struct dso *dso_filter = NULL; 660 const struct dso *dso_filter = NULL;
@@ -955,8 +673,6 @@ int hists__browse(struct hists *self, const char *helpline, const char *ev_name)
955 673
956 hist_browser__title(msg, sizeof(msg), ev_name, 674 hist_browser__title(msg, sizeof(msg), ev_name,
957 dso_filter, thread_filter); 675 dso_filter, thread_filter);
958 if (hist_browser__populate(browser, self, msg) < 0)
959 goto out_free_stack;
960 676
961 while (1) { 677 while (1) {
962 const struct thread *thread; 678 const struct thread *thread;
@@ -965,7 +681,8 @@ int hists__browse(struct hists *self, const char *helpline, const char *ev_name)
965 int nr_options = 0, choice = 0, i, 681 int nr_options = 0, choice = 0, i,
966 annotate = -2, zoom_dso = -2, zoom_thread = -2; 682 annotate = -2, zoom_dso = -2, zoom_thread = -2;
967 683
968 newtFormRun(browser->form, &es); 684 if (hist_browser__run(browser, msg, &es))
685 break;
969 686
970 thread = hist_browser__selected_thread(browser); 687 thread = hist_browser__selected_thread(browser);
971 dso = browser->selection->map ? browser->selection->map->dso : NULL; 688 dso = browser->selection->map ? browser->selection->map->dso : NULL;
@@ -1100,8 +817,7 @@ zoom_out_dso:
1100 hists__filter_by_dso(self, dso_filter); 817 hists__filter_by_dso(self, dso_filter);
1101 hist_browser__title(msg, sizeof(msg), ev_name, 818 hist_browser__title(msg, sizeof(msg), ev_name,
1102 dso_filter, thread_filter); 819 dso_filter, thread_filter);
1103 if (hist_browser__populate(browser, self, msg) < 0) 820 hist_browser__reset(browser);
1104 goto out;
1105 } else if (choice == zoom_thread) { 821 } else if (choice == zoom_thread) {
1106zoom_thread: 822zoom_thread:
1107 if (thread_filter) { 823 if (thread_filter) {
@@ -1119,8 +835,7 @@ zoom_out_thread:
1119 hists__filter_by_thread(self, thread_filter); 835 hists__filter_by_thread(self, thread_filter);
1120 hist_browser__title(msg, sizeof(msg), ev_name, 836 hist_browser__title(msg, sizeof(msg), ev_name,
1121 dso_filter, thread_filter); 837 dso_filter, thread_filter);
1122 if (hist_browser__populate(browser, self, msg) < 0) 838 hist_browser__reset(browser);
1123 goto out;
1124 } 839 }
1125 } 840 }
1126out_free_stack: 841out_free_stack:
@@ -1207,3 +922,638 @@ void exit_browser(bool wait_for_ok)
1207 newtFinished(); 922 newtFinished();
1208 } 923 }
1209} 924}
925
926static void hist_browser__refresh_dimensions(struct hist_browser *self)
927{
928 /* 3 == +/- toggle symbol before actual hist_entry rendering */
929 self->b.width = 3 + (hists__sort_list_width(self->hists) +
930 sizeof("[k]"));
931}
932
933static void hist_browser__reset(struct hist_browser *self)
934{
935 self->b.nr_entries = self->hists->nr_entries;
936 hist_browser__refresh_dimensions(self);
937 ui_browser__reset_index(&self->b);
938}
939
940static char tree__folded_sign(bool unfolded)
941{
942 return unfolded ? '-' : '+';
943}
944
945static char map_symbol__folded(const struct map_symbol *self)
946{
947 return self->has_children ? tree__folded_sign(self->unfolded) : ' ';
948}
949
950static char hist_entry__folded(const struct hist_entry *self)
951{
952 return map_symbol__folded(&self->ms);
953}
954
955static char callchain_list__folded(const struct callchain_list *self)
956{
957 return map_symbol__folded(&self->ms);
958}
959
960static bool map_symbol__toggle_fold(struct map_symbol *self)
961{
962 if (!self->has_children)
963 return false;
964
965 self->unfolded = !self->unfolded;
966 return true;
967}
968
969#define LEVEL_OFFSET_STEP 3
970
971static int hist_browser__show_callchain_node_rb_tree(struct hist_browser *self,
972 struct callchain_node *chain_node,
973 u64 total, int level,
974 unsigned short row,
975 off_t *row_offset,
976 bool *is_current_entry)
977{
978 struct rb_node *node;
979 int first_row = row, width, offset = level * LEVEL_OFFSET_STEP;
980 u64 new_total, remaining;
981
982 if (callchain_param.mode == CHAIN_GRAPH_REL)
983 new_total = chain_node->children_hit;
984 else
985 new_total = total;
986
987 remaining = new_total;
988 node = rb_first(&chain_node->rb_root);
989 while (node) {
990 struct callchain_node *child = rb_entry(node, struct callchain_node, rb_node);
991 struct rb_node *next = rb_next(node);
992 u64 cumul = cumul_hits(child);
993 struct callchain_list *chain;
994 char folded_sign = ' ';
995 int first = true;
996 int extra_offset = 0;
997
998 remaining -= cumul;
999
1000 list_for_each_entry(chain, &child->val, list) {
1001 char ipstr[BITS_PER_LONG / 4 + 1], *alloc_str;
1002 const char *str;
1003 int color;
1004 bool was_first = first;
1005
1006 if (first) {
1007 first = false;
1008 chain->ms.has_children = chain->list.next != &child->val ||
1009 rb_first(&child->rb_root) != NULL;
1010 } else {
1011 extra_offset = LEVEL_OFFSET_STEP;
1012 chain->ms.has_children = chain->list.next == &child->val &&
1013 rb_first(&child->rb_root) != NULL;
1014 }
1015
1016 folded_sign = callchain_list__folded(chain);
1017 if (*row_offset != 0) {
1018 --*row_offset;
1019 goto do_next;
1020 }
1021
1022 alloc_str = NULL;
1023 str = callchain_list__sym_name(chain, ipstr, sizeof(ipstr));
1024 if (was_first) {
1025 double percent = cumul * 100.0 / new_total;
1026
1027 if (asprintf(&alloc_str, "%2.2f%% %s", percent, str) < 0)
1028 str = "Not enough memory!";
1029 else
1030 str = alloc_str;
1031 }
1032
1033 color = HE_COLORSET_NORMAL;
1034 width = self->b.width - (offset + extra_offset + 2);
1035 if (ui_browser__is_current_entry(&self->b, row)) {
1036 self->selection = &chain->ms;
1037 color = HE_COLORSET_SELECTED;
1038 *is_current_entry = true;
1039 }
1040
1041 SLsmg_set_color(color);
1042 SLsmg_gotorc(self->b.top + row, self->b.left);
1043 slsmg_write_nstring(" ", offset + extra_offset);
1044 slsmg_printf("%c ", folded_sign);
1045 slsmg_write_nstring(str, width);
1046 free(alloc_str);
1047
1048 if (++row == self->b.height)
1049 goto out;
1050do_next:
1051 if (folded_sign == '+')
1052 break;
1053 }
1054
1055 if (folded_sign == '-') {
1056 const int new_level = level + (extra_offset ? 2 : 1);
1057 row += hist_browser__show_callchain_node_rb_tree(self, child, new_total,
1058 new_level, row, row_offset,
1059 is_current_entry);
1060 }
1061 if (row == self->b.height)
1062 goto out;
1063 node = next;
1064 }
1065out:
1066 return row - first_row;
1067}
1068
1069static int hist_browser__show_callchain_node(struct hist_browser *self,
1070 struct callchain_node *node,
1071 int level, unsigned short row,
1072 off_t *row_offset,
1073 bool *is_current_entry)
1074{
1075 struct callchain_list *chain;
1076 int first_row = row,
1077 offset = level * LEVEL_OFFSET_STEP,
1078 width = self->b.width - offset;
1079 char folded_sign = ' ';
1080
1081 list_for_each_entry(chain, &node->val, list) {
1082 char ipstr[BITS_PER_LONG / 4 + 1], *s;
1083 int color;
1084 /*
1085 * FIXME: This should be moved to somewhere else,
1086 * probably when the callchain is created, so as not to
1087 * traverse it all over again
1088 */
1089 chain->ms.has_children = rb_first(&node->rb_root) != NULL;
1090 folded_sign = callchain_list__folded(chain);
1091
1092 if (*row_offset != 0) {
1093 --*row_offset;
1094 continue;
1095 }
1096
1097 color = HE_COLORSET_NORMAL;
1098 if (ui_browser__is_current_entry(&self->b, row)) {
1099 self->selection = &chain->ms;
1100 color = HE_COLORSET_SELECTED;
1101 *is_current_entry = true;
1102 }
1103
1104 s = callchain_list__sym_name(chain, ipstr, sizeof(ipstr));
1105 SLsmg_gotorc(self->b.top + row, self->b.left);
1106 SLsmg_set_color(color);
1107 slsmg_write_nstring(" ", offset);
1108 slsmg_printf("%c ", folded_sign);
1109 slsmg_write_nstring(s, width - 2);
1110
1111 if (++row == self->b.height)
1112 goto out;
1113 }
1114
1115 if (folded_sign == '-')
1116 row += hist_browser__show_callchain_node_rb_tree(self, node,
1117 self->hists->stats.total_period,
1118 level + 1, row,
1119 row_offset,
1120 is_current_entry);
1121out:
1122 return row - first_row;
1123}
1124
1125static int hist_browser__show_callchain(struct hist_browser *self,
1126 struct rb_root *chain,
1127 int level, unsigned short row,
1128 off_t *row_offset,
1129 bool *is_current_entry)
1130{
1131 struct rb_node *nd;
1132 int first_row = row;
1133
1134 for (nd = rb_first(chain); nd; nd = rb_next(nd)) {
1135 struct callchain_node *node = rb_entry(nd, struct callchain_node, rb_node);
1136
1137 row += hist_browser__show_callchain_node(self, node, level,
1138 row, row_offset,
1139 is_current_entry);
1140 if (row == self->b.height)
1141 break;
1142 }
1143
1144 return row - first_row;
1145}
1146
1147static int hist_browser__show_entry(struct hist_browser *self,
1148 struct hist_entry *entry,
1149 unsigned short row)
1150{
1151 char s[256];
1152 double percent;
1153 int printed = 0;
1154 int color, width = self->b.width;
1155 char folded_sign = ' ';
1156 bool current_entry = ui_browser__is_current_entry(&self->b, row);
1157 off_t row_offset = entry->row_offset;
1158
1159 if (current_entry) {
1160 self->he_selection = entry;
1161 self->selection = &entry->ms;
1162 }
1163
1164 if (symbol_conf.use_callchain) {
1165 entry->ms.has_children = !RB_EMPTY_ROOT(&entry->sorted_chain);
1166 folded_sign = hist_entry__folded(entry);
1167 }
1168
1169 if (row_offset == 0) {
1170 hist_entry__snprintf(entry, s, sizeof(s), self->hists, NULL, false,
1171 0, false, self->hists->stats.total_period);
1172 percent = (entry->period * 100.0) / self->hists->stats.total_period;
1173
1174 color = HE_COLORSET_SELECTED;
1175 if (!current_entry) {
1176 if (percent >= MIN_RED)
1177 color = HE_COLORSET_TOP;
1178 else if (percent >= MIN_GREEN)
1179 color = HE_COLORSET_MEDIUM;
1180 else
1181 color = HE_COLORSET_NORMAL;
1182 }
1183
1184 SLsmg_set_color(color);
1185 SLsmg_gotorc(self->b.top + row, self->b.left);
1186 if (symbol_conf.use_callchain) {
1187 slsmg_printf("%c ", folded_sign);
1188 width -= 2;
1189 }
1190 slsmg_write_nstring(s, width);
1191 ++row;
1192 ++printed;
1193 } else
1194 --row_offset;
1195
1196 if (folded_sign == '-' && row != self->b.height) {
1197 printed += hist_browser__show_callchain(self, &entry->sorted_chain,
1198 1, row, &row_offset,
1199 &current_entry);
1200 if (current_entry)
1201 self->he_selection = entry;
1202 }
1203
1204 return printed;
1205}
1206
1207static unsigned int hist_browser__refresh_entries(struct ui_browser *self)
1208{
1209 unsigned row = 0;
1210 struct rb_node *nd;
1211 struct hist_browser *hb = container_of(self, struct hist_browser, b);
1212
1213 if (self->first_visible_entry == NULL)
1214 self->first_visible_entry = rb_first(&hb->hists->entries);
1215
1216 for (nd = self->first_visible_entry; nd; nd = rb_next(nd)) {
1217 struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
1218
1219 if (h->filtered)
1220 continue;
1221
1222 row += hist_browser__show_entry(hb, h, row);
1223 if (row == self->height)
1224 break;
1225 }
1226
1227 return row;
1228}
1229
1230static void callchain_node__init_have_children_rb_tree(struct callchain_node *self)
1231{
1232 struct rb_node *nd = rb_first(&self->rb_root);
1233
1234 for (nd = rb_first(&self->rb_root); nd; nd = rb_next(nd)) {
1235 struct callchain_node *child = rb_entry(nd, struct callchain_node, rb_node);
1236 struct callchain_list *chain;
1237 int first = true;
1238
1239 list_for_each_entry(chain, &child->val, list) {
1240 if (first) {
1241 first = false;
1242 chain->ms.has_children = chain->list.next != &child->val ||
1243 rb_first(&child->rb_root) != NULL;
1244 } else
1245 chain->ms.has_children = chain->list.next == &child->val &&
1246 rb_first(&child->rb_root) != NULL;
1247 }
1248
1249 callchain_node__init_have_children_rb_tree(child);
1250 }
1251}
1252
1253static void callchain_node__init_have_children(struct callchain_node *self)
1254{
1255 struct callchain_list *chain;
1256
1257 list_for_each_entry(chain, &self->val, list)
1258 chain->ms.has_children = rb_first(&self->rb_root) != NULL;
1259
1260 callchain_node__init_have_children_rb_tree(self);
1261}
1262
1263static void callchain__init_have_children(struct rb_root *self)
1264{
1265 struct rb_node *nd;
1266
1267 for (nd = rb_first(self); nd; nd = rb_next(nd)) {
1268 struct callchain_node *node = rb_entry(nd, struct callchain_node, rb_node);
1269 callchain_node__init_have_children(node);
1270 }
1271}
1272
1273static void hist_entry__init_have_children(struct hist_entry *self)
1274{
1275 if (!self->init_have_children) {
1276 callchain__init_have_children(&self->sorted_chain);
1277 self->init_have_children = true;
1278 }
1279}
1280
1281static struct rb_node *hists__filter_entries(struct rb_node *nd)
1282{
1283 while (nd != NULL) {
1284 struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
1285 if (!h->filtered)
1286 return nd;
1287
1288 nd = rb_next(nd);
1289 }
1290
1291 return NULL;
1292}
1293
1294static struct rb_node *hists__filter_prev_entries(struct rb_node *nd)
1295{
1296 while (nd != NULL) {
1297 struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
1298 if (!h->filtered)
1299 return nd;
1300
1301 nd = rb_prev(nd);
1302 }
1303
1304 return NULL;
1305}
1306
1307static void ui_browser__hists_seek(struct ui_browser *self,
1308 off_t offset, int whence)
1309{
1310 struct hist_entry *h;
1311 struct rb_node *nd;
1312 bool first = true;
1313
1314 switch (whence) {
1315 case SEEK_SET:
1316 nd = hists__filter_entries(rb_first(self->entries));
1317 break;
1318 case SEEK_CUR:
1319 nd = self->first_visible_entry;
1320 goto do_offset;
1321 case SEEK_END:
1322 nd = hists__filter_prev_entries(rb_last(self->entries));
1323 first = false;
1324 break;
1325 default:
1326 return;
1327 }
1328
1329 /*
1330 * Moves not relative to the first visible entry invalidates its
1331 * row_offset:
1332 */
1333 h = rb_entry(self->first_visible_entry, struct hist_entry, rb_node);
1334 h->row_offset = 0;
1335
1336 /*
1337 * Here we have to check if nd is expanded (+), if it is we can't go
1338 * the next top level hist_entry, instead we must compute an offset of
1339 * what _not_ to show and not change the first visible entry.
1340 *
1341 * This offset increments when we are going from top to bottom and
1342 * decreases when we're going from bottom to top.
1343 *
1344 * As we don't have backpointers to the top level in the callchains
1345 * structure, we need to always print the whole hist_entry callchain,
1346 * skipping the first ones that are before the first visible entry
1347 * and stop when we printed enough lines to fill the screen.
1348 */
1349do_offset:
1350 if (offset > 0) {
1351 do {
1352 h = rb_entry(nd, struct hist_entry, rb_node);
1353 if (h->ms.unfolded) {
1354 u16 remaining = h->nr_rows - h->row_offset;
1355 if (offset > remaining) {
1356 offset -= remaining;
1357 h->row_offset = 0;
1358 } else {
1359 h->row_offset += offset;
1360 offset = 0;
1361 self->first_visible_entry = nd;
1362 break;
1363 }
1364 }
1365 nd = hists__filter_entries(rb_next(nd));
1366 if (nd == NULL)
1367 break;
1368 --offset;
1369 self->first_visible_entry = nd;
1370 } while (offset != 0);
1371 } else if (offset < 0) {
1372 while (1) {
1373 h = rb_entry(nd, struct hist_entry, rb_node);
1374 if (h->ms.unfolded) {
1375 if (first) {
1376 if (-offset > h->row_offset) {
1377 offset += h->row_offset;
1378 h->row_offset = 0;
1379 } else {
1380 h->row_offset += offset;
1381 offset = 0;
1382 self->first_visible_entry = nd;
1383 break;
1384 }
1385 } else {
1386 if (-offset > h->nr_rows) {
1387 offset += h->nr_rows;
1388 h->row_offset = 0;
1389 } else {
1390 h->row_offset = h->nr_rows + offset;
1391 offset = 0;
1392 self->first_visible_entry = nd;
1393 break;
1394 }
1395 }
1396 }
1397
1398 nd = hists__filter_prev_entries(rb_prev(nd));
1399 if (nd == NULL)
1400 break;
1401 ++offset;
1402 self->first_visible_entry = nd;
1403 if (offset == 0) {
1404 /*
1405 * Last unfiltered hist_entry, check if it is
1406 * unfolded, if it is then we should have
1407 * row_offset at its last entry.
1408 */
1409 h = rb_entry(nd, struct hist_entry, rb_node);
1410 if (h->ms.unfolded)
1411 h->row_offset = h->nr_rows;
1412 break;
1413 }
1414 first = false;
1415 }
1416 } else {
1417 self->first_visible_entry = nd;
1418 h = rb_entry(nd, struct hist_entry, rb_node);
1419 h->row_offset = 0;
1420 }
1421}
1422
1423static int callchain_node__count_rows_rb_tree(struct callchain_node *self)
1424{
1425 int n = 0;
1426 struct rb_node *nd;
1427
1428 for (nd = rb_first(&self->rb_root); nd; nd = rb_next(nd)) {
1429 struct callchain_node *child = rb_entry(nd, struct callchain_node, rb_node);
1430 struct callchain_list *chain;
1431 char folded_sign = ' '; /* No children */
1432
1433 list_for_each_entry(chain, &child->val, list) {
1434 ++n;
1435 /* We need this because we may not have children */
1436 folded_sign = callchain_list__folded(chain);
1437 if (folded_sign == '+')
1438 break;
1439 }
1440
1441 if (folded_sign == '-') /* Have children and they're unfolded */
1442 n += callchain_node__count_rows_rb_tree(child);
1443 }
1444
1445 return n;
1446}
1447
1448static int callchain_node__count_rows(struct callchain_node *node)
1449{
1450 struct callchain_list *chain;
1451 bool unfolded = false;
1452 int n = 0;
1453
1454 list_for_each_entry(chain, &node->val, list) {
1455 ++n;
1456 unfolded = chain->ms.unfolded;
1457 }
1458
1459 if (unfolded)
1460 n += callchain_node__count_rows_rb_tree(node);
1461
1462 return n;
1463}
1464
1465static int callchain__count_rows(struct rb_root *chain)
1466{
1467 struct rb_node *nd;
1468 int n = 0;
1469
1470 for (nd = rb_first(chain); nd; nd = rb_next(nd)) {
1471 struct callchain_node *node = rb_entry(nd, struct callchain_node, rb_node);
1472 n += callchain_node__count_rows(node);
1473 }
1474
1475 return n;
1476}
1477
1478static bool hist_browser__toggle_fold(struct hist_browser *self)
1479{
1480 if (map_symbol__toggle_fold(self->selection)) {
1481 struct hist_entry *he = self->he_selection;
1482
1483 hist_entry__init_have_children(he);
1484 self->hists->nr_entries -= he->nr_rows;
1485
1486 if (he->ms.unfolded)
1487 he->nr_rows = callchain__count_rows(&he->sorted_chain);
1488 else
1489 he->nr_rows = 0;
1490 self->hists->nr_entries += he->nr_rows;
1491 self->b.nr_entries = self->hists->nr_entries;
1492
1493 return true;
1494 }
1495
1496 /* If it doesn't have children, no toggling performed */
1497 return false;
1498}
1499
1500static int hist_browser__run(struct hist_browser *self, const char *title,
1501 struct newtExitStruct *es)
1502{
1503 char str[256], unit;
1504 unsigned long nr_events = self->hists->stats.nr_events[PERF_RECORD_SAMPLE];
1505
1506 self->b.entries = &self->hists->entries;
1507 self->b.nr_entries = self->hists->nr_entries;
1508
1509 hist_browser__refresh_dimensions(self);
1510
1511 nr_events = convert_unit(nr_events, &unit);
1512 snprintf(str, sizeof(str), "Events: %lu%c ",
1513 nr_events, unit);
1514 newtDrawRootText(0, 0, str);
1515
1516 if (ui_browser__show(&self->b, title) < 0)
1517 return -1;
1518
1519 newtFormAddHotKey(self->b.form, 'A');
1520 newtFormAddHotKey(self->b.form, 'a');
1521 newtFormAddHotKey(self->b.form, '?');
1522 newtFormAddHotKey(self->b.form, 'h');
1523 newtFormAddHotKey(self->b.form, 'H');
1524 newtFormAddHotKey(self->b.form, 'd');
1525
1526 newtFormAddHotKey(self->b.form, NEWT_KEY_LEFT);
1527 newtFormAddHotKey(self->b.form, NEWT_KEY_RIGHT);
1528 newtFormAddHotKey(self->b.form, NEWT_KEY_ENTER);
1529
1530 while (1) {
1531 ui_browser__run(&self->b, es);
1532
1533 if (es->reason != NEWT_EXIT_HOTKEY)
1534 break;
1535 switch (es->u.key) {
1536 case 'd': { /* Debug */
1537 static int seq;
1538 struct hist_entry *h = rb_entry(self->b.first_visible_entry,
1539 struct hist_entry, rb_node);
1540 ui_helpline__pop();
1541 ui_helpline__fpush("%d: nr_ent=(%d,%d), height=%d, idx=%d, fve: idx=%d, row_off=%d, nrows=%d",
1542 seq++, self->b.nr_entries,
1543 self->hists->nr_entries,
1544 self->b.height,
1545 self->b.index,
1546 self->b.first_visible_entry_idx,
1547 h->row_offset, h->nr_rows);
1548 }
1549 continue;
1550 case NEWT_KEY_ENTER:
1551 if (hist_browser__toggle_fold(self))
1552 break;
1553 /* fall thru */
1554 default:
1555 return 0;
1556 }
1557 }
1558 return 0;
1559}
diff --git a/tools/perf/util/sort.h b/tools/perf/util/sort.h
index 03a1722e6d02..46e531d09e8b 100644
--- a/tools/perf/util/sort.h
+++ b/tools/perf/util/sort.h
@@ -38,6 +38,12 @@ extern struct sort_entry sort_sym;
38extern struct sort_entry sort_parent; 38extern struct sort_entry sort_parent;
39extern enum sort_type sort__first_dimension; 39extern enum sort_type sort__first_dimension;
40 40
41/**
42 * struct hist_entry - histogram entry
43 *
44 * @row_offset - offset from the first callchain expanded to appear on screen
45 * @nr_rows - rows expanded in callchain, recalculated on folding/unfolding
46 */
41struct hist_entry { 47struct hist_entry {
42 struct rb_node rb_node; 48 struct rb_node rb_node;
43 u64 period; 49 u64 period;
@@ -50,6 +56,12 @@ struct hist_entry {
50 u64 ip; 56 u64 ip;
51 s32 cpu; 57 s32 cpu;
52 u32 nr_events; 58 u32 nr_events;
59
60 /* XXX These two should move to some tree widget lib */
61 u16 row_offset;
62 u16 nr_rows;
63
64 bool init_have_children;
53 char level; 65 char level;
54 u8 filtered; 66 u8 filtered;
55 struct symbol *parent; 67 struct symbol *parent;
diff --git a/tools/perf/util/symbol.h b/tools/perf/util/symbol.h
index d436ee3d3a73..bb1aab9fa34f 100644
--- a/tools/perf/util/symbol.h
+++ b/tools/perf/util/symbol.h
@@ -102,6 +102,8 @@ struct ref_reloc_sym {
102struct map_symbol { 102struct map_symbol {
103 struct map *map; 103 struct map *map;
104 struct symbol *sym; 104 struct symbol *sym;
105 bool unfolded;
106 bool has_children;
105}; 107};
106 108
107struct addr_location { 109struct addr_location {