[RFC 0/5] perf: Create hist_entry groups

[RFC 0/5] perf: Create hist_entry groups

[Don Zickus]

This patchset creates a new layer of hist entry objects called
hist_entry_groups.  The purpose is to help organize the hist_entries
into groups before sorting them.  As a result you can gain a
new perspective on the data by organizing the groups into cpu, pid
or cacheline.  See patch 5 for sample output.

The main driver for this patchset is to find a way to sort and display
cacheline data in a way that is useful.  My previous attempts seemed
hackish until I realized cacheline sorting is really just a collection
of hist_entries.  Anyway that was my focus for doing this.

The overall idea looks like:

evlist
  evsel
    hists
        hist_entry_group  <<< new object
          hist_entry


Implementing this was not pretty.  I tried to seperate the patches the
best I could.  But in order for each patch to compile, patch 4 turned into
a 1400 line diff that is mostly noise.

Also, this patchset breaks most tools (mainly because I don't understand
all the interactions), hence the RFC.  I mostly tested with 'perf report
 --stdio' and 'perf mem report --stdio'.

Please let me know if this is an interesting idea to go forward with or not.

Don Zickus (5):
  perf: Wrap __hists__add_entry to prep for group entry change
  perf: Use macros to walk hist entries
  perf: Add in stub hist_entry_group code
  perf:  Switch to using hist_entry_group
  perf: Enable multiple hist_entry_group output

 tools/perf/builtin-annotate.c  |  13 +-
 tools/perf/builtin-diff.c      | 127 +++++-----
 tools/perf/builtin-report.c    |  14 +-
 tools/perf/builtin-top.c       |  22 +-
 tools/perf/tests/hists_link.c  | 124 ++++------
 tools/perf/ui/browsers/hists.c |  40 +++-
 tools/perf/ui/gtk/hists.c      |  80 ++++---
 tools/perf/ui/hist.c           |  29 ++-
 tools/perf/ui/stdio/hist.c     |  97 ++++++--
 tools/perf/util/evsel.c        |   7 +-
 tools/perf/util/hist.c         | 512 +++++++++++++++++++++++++++++------------
 tools/perf/util/hist.h         |  29 ++-
 tools/perf/util/sort.c         | 183 ++++++++++++++-
 tools/perf/util/sort.h         | 138 ++++++++++-
 14 files changed, 1017 insertions(+), 398 deletions(-)

-- 
1.7.11.7

[RFC 1/5] perf: Wrap __hists__add_entry to prep for group entry change

[Don Zickus]

This patch is mainly mechanical and just wraps __hists__add_entry with
hists__add_entry.  Later on, we can modify hists__add_entry to include group
entry changes without disturbing the builtin-* files.

Signed-off-by: Don Zickus <dzickus@redhat.com>
---
 tools/perf/builtin-annotate.c |  2 +-
 tools/perf/builtin-diff.c     | 14 +++++++-------
 tools/perf/builtin-report.c   | 12 ++++++------
 tools/perf/builtin-top.c      |  6 +++---
 tools/perf/tests/hists_link.c |  8 ++++----
 tools/perf/util/hist.c        | 25 +++++++++++++++++++------
 tools/perf/util/hist.h        | 12 ++++++------
 7 files changed, 46 insertions(+), 33 deletions(-)

diff --git a/tools/perf/builtin-annotate.c b/tools/perf/builtin-annotate.c
index 0da603b..0157787 100644
--- a/tools/perf/builtin-annotate.c
+++ b/tools/perf/builtin-annotate.c
@@ -65,7 +65,7 @@ static int perf_evsel__add_sample(struct perf_evsel *evsel,
 		return 0;
 	}
 
-	he = __hists__add_entry(&evsel->hists, al, NULL, NULL, NULL, 1, 1, 0);
+	he = hists__add_entry(&evsel->hists, al, NULL, NULL, NULL, 1, 1, 0);
 	if (he == NULL)
 		return -ENOMEM;
 
diff --git a/tools/perf/builtin-diff.c b/tools/perf/builtin-diff.c
index 204fffe..2e4857d 100644
--- a/tools/perf/builtin-diff.c
+++ b/tools/perf/builtin-diff.c
@@ -303,12 +303,12 @@ static int formula_fprintf(struct hist_entry *he, struct hist_entry *pair,
 	return -1;
 }
 
-static int hists__add_entry(struct hists *hists,
-			    struct addr_location *al, u64 period,
-			    u64 weight, u64 transaction)
+static int diff_hists__add_entry(struct hists *hists,
+				 struct addr_location *al, u64 period,
+				 u64 weight, u64 transaction)
 {
-	if (__hists__add_entry(hists, al, NULL, NULL, NULL, period, weight,
-			       transaction) != NULL)
+	if (hists__add_entry(hists, al, NULL, NULL, NULL, period, weight,
+			     transaction) != NULL)
 		return 0;
 	return -ENOMEM;
 }
@@ -330,8 +330,8 @@ static int diff__process_sample_event(struct perf_tool *tool __maybe_unused,
 	if (al.filtered)
 		return 0;
 
-	if (hists__add_entry(&evsel->hists, &al, sample->period,
-			     sample->weight, sample->transaction)) {
+	if (diff_hists__add_entry(&evsel->hists, &al, sample->period,
+				  sample->weight, sample->transaction)) {
 		pr_warning("problem incrementing symbol period, skipping event\n");
 		return -1;
 	}
diff --git a/tools/perf/builtin-report.c b/tools/perf/builtin-report.c
index c8f2113..51a37d6 100644
--- a/tools/perf/builtin-report.c
+++ b/tools/perf/builtin-report.c
@@ -105,8 +105,8 @@ static int report__add_mem_hist_entry(struct report *rep, struct addr_location *
 	 * and this is indirectly achieved by passing period=weight here
 	 * and the he_stat__add_period() function.
 	 */
-	he = __hists__add_entry(&evsel->hists, al, parent, NULL, mi,
-				cost, cost, 0);
+	he = hists__add_entry(&evsel->hists, al, parent, NULL, mi,
+			      cost, cost, 0);
 	if (!he)
 		return -ENOMEM;
 
@@ -158,8 +158,8 @@ static int report__add_branch_hist_entry(struct report *rep, struct addr_locatio
 		 * The report shows the percentage of total branches captured
 		 * and not events sampled. Thus we use a pseudo period of 1.
 		 */
-		he = __hists__add_entry(&evsel->hists, al, parent, &bi[i], NULL,
-					1, 1, 0);
+		he = hists__add_entry(&evsel->hists, al, parent, &bi[i], NULL,
+			 	      1, 1, 0);
 		if (he) {
 			if (ui__has_annotation()) {
 				bx = he->branch_info;
@@ -195,8 +195,8 @@ static int report__add_hist_entry(struct report *rep, struct perf_evsel *evsel,
 	if (err)
 		return err;
 
-	he = __hists__add_entry(&evsel->hists, al, parent, NULL, NULL,
-				sample->period, sample->weight,
+	he = hists__add_entry(&evsel->hists, al, parent, NULL, NULL,
+			      sample->period, sample->weight,
 				sample->transaction);
 	if (he == NULL)
 		return -ENOMEM;
diff --git a/tools/perf/builtin-top.c b/tools/perf/builtin-top.c
index 65aaa5b..e58b124 100644
--- a/tools/perf/builtin-top.c
+++ b/tools/perf/builtin-top.c
@@ -245,9 +245,9 @@ static struct hist_entry *perf_evsel__add_hist_entry(struct perf_evsel *evsel,
 	struct hist_entry *he;
 
 	pthread_mutex_lock(&evsel->hists.lock);
-	he = __hists__add_entry(&evsel->hists, al, NULL, NULL, NULL,
-				sample->period, sample->weight,
-				sample->transaction);
+	he = hists__add_entry(&evsel->hists, al, NULL, NULL, NULL,
+			      sample->period, sample->weight,
+			      sample->transaction);
 	pthread_mutex_unlock(&evsel->hists.lock);
 	if (he == NULL)
 		return NULL;
diff --git a/tools/perf/tests/hists_link.c b/tools/perf/tests/hists_link.c
index 7ccbc7b..bd851c6 100644
--- a/tools/perf/tests/hists_link.c
+++ b/tools/perf/tests/hists_link.c
@@ -223,8 +223,8 @@ static int add_hist_entries(struct perf_evlist *evlist, struct machine *machine)
 							  &sample) < 0)
 				goto out;
 
-			he = __hists__add_entry(&evsel->hists, &al, NULL,
-						NULL, NULL, 1, 1, 0);
+			he = hists__add_entry(&evsel->hists, &al, NULL,
+					      NULL, NULL, 1, 1, 0);
 			if (he == NULL)
 				goto out;
 
@@ -246,8 +246,8 @@ static int add_hist_entries(struct perf_evlist *evlist, struct machine *machine)
 							  &sample) < 0)
 				goto out;
 
-			he = __hists__add_entry(&evsel->hists, &al, NULL,
-						NULL, NULL, 1, 1, 0);
+			he = hists__add_entry(&evsel->hists, &al, NULL,
+					      NULL, NULL, 1, 1, 0);
 			if (he == NULL)
 				goto out;
 
diff --git a/tools/perf/util/hist.c b/tools/perf/util/hist.c
index f38590d..57545b3 100644
--- a/tools/perf/util/hist.c
+++ b/tools/perf/util/hist.c
@@ -399,12 +399,13 @@ out:
 	return he;
 }
 
-struct hist_entry *__hists__add_entry(struct hists *hists,
-				      struct addr_location *al,
-				      struct symbol *sym_parent,
-				      struct branch_info *bi,
-				      struct mem_info *mi,
-				      u64 period, u64 weight, u64 transaction)
+static struct hist_entry *__hists__add_entry(struct hists *hists,
+					     struct addr_location *al,
+					     struct symbol *sym_parent,
+					     struct branch_info *bi,
+					     struct mem_info *mi,
+					     u64 period, u64 weight,
+					     u64 transaction)
 {
 	struct hist_entry entry = {
 		.thread	= al->thread,
@@ -432,6 +433,18 @@ struct hist_entry *__hists__add_entry(struct hists *hists,
 	return add_hist_entry(hists, &entry, al);
 }
 
+struct hist_entry *hists__add_entry(struct hists *hists,
+				    struct addr_location *al,
+				    struct symbol *sym_parent,
+				    struct branch_info *bi,
+				    struct mem_info *mi,
+				    u64 period, u64 weight,
+				    u64 transaction)
+{
+	return __hists__add_entry(hists, al, sym_parent, bi, mi, period,
+				  weight, transaction);
+}
+
 int64_t
 hist_entry__cmp(struct hist_entry *left, struct hist_entry *right)
 {
diff --git a/tools/perf/util/hist.h b/tools/perf/util/hist.h
index 1f1f513..1d24c27 100644
--- a/tools/perf/util/hist.h
+++ b/tools/perf/util/hist.h
@@ -93,12 +93,12 @@ struct hists {
 	u16			col_len[HISTC_NR_COLS];
 };
 
-struct hist_entry *__hists__add_entry(struct hists *hists,
-				      struct addr_location *al,
-				      struct symbol *parent,
-				      struct branch_info *bi,
-				      struct mem_info *mi, u64 period,
-				      u64 weight, u64 transaction);
+struct hist_entry *hists__add_entry(struct hists *hists,
+				    struct addr_location *al,
+				    struct symbol *parent,
+				    struct branch_info *bi,
+				    struct mem_info *mi, u64 period,
+				    u64 weight, u64 transaction);
 int64_t hist_entry__cmp(struct hist_entry *left, struct hist_entry *right);
 int64_t hist_entry__collapse(struct hist_entry *left, struct hist_entry *right);
 int hist_entry__transaction_len(void);
-- 
1.7.11.7

[RFC 2/5] perf: Use macros to walk hist entries

[Don Zickus]

There is code copied everywhere to walk the hist entry list.  Turn this
into a macro to minimize errors later.  Also useful for converting to group
hist entries later.

New macros are:

hist__for_each_entry_in
hist__for_each_entry_in_safe
hist__for_each_entry_out

Most code that looks like this:

if (sort__neeed_collapse)
	root = &hists->entries_collapsed;
else
	root = hists->entries_in;

next = rb_first(root);
while (next != NULL) {
	struct hist_entry *he = rb_entry(....)
	next = rb_next(&he->rb_node_in);

and turns it into

hist__for_each_entry_in(he, hists) {

One advantage (besides smaller written code), is one doesn't have to remember
which struct fields are for input data or output data (entries_in vs. entries)
and their correspoding rb_node hook (rb_node_in vs. rb_node).

Most obvious places have been converted, some unusual cases stayed unchanged.

Should be a mostly mechanical change and nothing should change from a technical
perspective.

Signed-off-by: Don Zickus <dzickus@redhat.com>
---
 tools/perf/builtin-diff.c      | 48 ++++++----------------------------
 tools/perf/builtin-top.c       |  6 +----
 tools/perf/tests/hists_link.c  | 51 +++++-------------------------------
 tools/perf/ui/browsers/hists.c |  5 ++--
 tools/perf/ui/gtk/hists.c      |  5 ++--
 tools/perf/ui/stdio/hist.c     |  5 ++--
 tools/perf/util/hist.c         | 34 +++---------------------
 tools/perf/util/sort.h         | 59 ++++++++++++++++++++++++++++++++++++++++++
 8 files changed, 83 insertions(+), 130 deletions(-)

diff --git a/tools/perf/builtin-diff.c b/tools/perf/builtin-diff.c
index 2e4857d..837d0e2 100644
--- a/tools/perf/builtin-diff.c
+++ b/tools/perf/builtin-diff.c
@@ -400,21 +400,11 @@ get_pair_fmt(struct hist_entry *he, struct diff_hpp_fmt *dfmt)
 
 static void hists__baseline_only(struct hists *hists)
 {
-	struct rb_root *root;
-	struct rb_node *next;
+	struct hist_entry *he, *next;
 
-	if (sort__need_collapse)
-		root = &hists->entries_collapsed;
-	else
-		root = hists->entries_in;
-
-	next = rb_first(root);
-	while (next != NULL) {
-		struct hist_entry *he = rb_entry(next, struct hist_entry, rb_node_in);
-
-		next = rb_next(&he->rb_node_in);
+	hist__for_each_entry_in_safe(he, next, hists) {
 		if (!hist_entry__next_pair(he)) {
-			rb_erase(&he->rb_node_in, root);
+			rb_erase(&he->rb_node_in, hists__get_root(hists));
 			hist_entry__free(he);
 		}
 	}
@@ -422,20 +412,10 @@ static void hists__baseline_only(struct hists *hists)
 
 static void hists__precompute(struct hists *hists)
 {
-	struct rb_root *root;
-	struct rb_node *next;
-
-	if (sort__need_collapse)
-		root = &hists->entries_collapsed;
-	else
-		root = hists->entries_in;
-
-	next = rb_first(root);
-	while (next != NULL) {
-		struct hist_entry *he, *pair;
+	struct hist_entry *he;
 
-		he   = rb_entry(next, struct hist_entry, rb_node_in);
-		next = rb_next(&he->rb_node_in);
+	hist__for_each_entry_in(he, hists) {
+		struct hist_entry *pair;
 
 		pair = get_pair_data(he, &data__files[sort_compute]);
 		if (!pair)
@@ -553,27 +533,15 @@ static void insert_hist_entry_by_compute(struct rb_root *root,
 
 static void hists__compute_resort(struct hists *hists)
 {
-	struct rb_root *root;
-	struct rb_node *next;
-
-	if (sort__need_collapse)
-		root = &hists->entries_collapsed;
-	else
-		root = hists->entries_in;
+	struct hist_entry *he;
 
 	hists->entries = RB_ROOT;
-	next = rb_first(root);
 
 	hists->nr_entries = 0;
 	hists->stats.total_period = 0;
 	hists__reset_col_len(hists);
 
-	while (next != NULL) {
-		struct hist_entry *he;
-
-		he = rb_entry(next, struct hist_entry, rb_node_in);
-		next = rb_next(&he->rb_node_in);
-
+	hist__for_each_entry_in(he, hists) {
 		insert_hist_entry_by_compute(&hists->entries, he, compute);
 		hists__inc_nr_entries(hists, he);
 	}
diff --git a/tools/perf/builtin-top.c b/tools/perf/builtin-top.c
index e58b124..427f2e2 100644
--- a/tools/perf/builtin-top.c
+++ b/tools/perf/builtin-top.c
@@ -338,7 +338,6 @@ static void perf_top__prompt_symbol(struct perf_top *top, const char *msg)
 {
 	char *buf = malloc(0), *p;
 	struct hist_entry *syme = top->sym_filter_entry, *n, *found = NULL;
-	struct rb_node *next;
 	size_t dummy = 0;
 
 	/* zero counters of active symbol */
@@ -355,14 +354,11 @@ static void perf_top__prompt_symbol(struct perf_top *top, const char *msg)
 	if (p)
 		*p = 0;
 
-	next = rb_first(&top->sym_evsel->hists.entries);
-	while (next) {
-		n = rb_entry(next, struct hist_entry, rb_node);
+	hist__for_each_entry_out(n, (&top->sym_evsel->hists)) {
 		if (n->ms.sym && !strcmp(buf, n->ms.sym->name)) {
 			found = n;
 			break;
 		}
-		next = rb_next(&n->rb_node);
 	}
 
 	if (!found) {
diff --git a/tools/perf/tests/hists_link.c b/tools/perf/tests/hists_link.c
index bd851c6..a0def6b 100644
--- a/tools/perf/tests/hists_link.c
+++ b/tools/perf/tests/hists_link.c
@@ -280,23 +280,9 @@ static int find_sample(struct sample *samples, size_t nr_samples,
 static int __validate_match(struct hists *hists)
 {
 	size_t count = 0;
-	struct rb_root *root;
-	struct rb_node *node;
-
-	/*
-	 * Only entries from fake_common_samples should have a pair.
-	 */
-	if (sort__need_collapse)
-		root = &hists->entries_collapsed;
-	else
-		root = hists->entries_in;
-
-	node = rb_first(root);
-	while (node) {
-		struct hist_entry *he;
-
-		he = rb_entry(node, struct hist_entry, rb_node_in);
+	struct hist_entry *he;
 
+	hist__for_each_entry_in(he, hists) {
 		if (hist_entry__has_pairs(he)) {
 			if (find_sample(fake_common_samples,
 					ARRAY_SIZE(fake_common_samples),
@@ -307,8 +293,6 @@ static int __validate_match(struct hists *hists)
 				return -1;
 			}
 		}
-
-		node = rb_next(node);
 	}
 
 	if (count != ARRAY_SIZE(fake_common_samples)) {
@@ -330,25 +314,15 @@ static int __validate_link(struct hists *hists, int idx)
 	size_t count = 0;
 	size_t count_pair = 0;
 	size_t count_dummy = 0;
-	struct rb_root *root;
-	struct rb_node *node;
+	struct hist_entry *he;
 
 	/*
 	 * Leader hists (idx = 0) will have dummy entries from other,
 	 * and some entries will have no pair.  However every entry
 	 * in other hists should have (dummy) pair.
 	 */
-	if (sort__need_collapse)
-		root = &hists->entries_collapsed;
-	else
-		root = hists->entries_in;
-
-	node = rb_first(root);
-	while (node) {
-		struct hist_entry *he;
-
-		he = rb_entry(node, struct hist_entry, rb_node_in);
 
+	hist__for_each_entry_in(he, hists) {
 		if (hist_entry__has_pairs(he)) {
 			if (!find_sample(fake_common_samples,
 					 ARRAY_SIZE(fake_common_samples),
@@ -365,7 +339,6 @@ static int __validate_link(struct hists *hists, int idx)
 		}
 
 		count++;
-		node = rb_next(node);
 	}
 
 	/*
@@ -406,27 +379,15 @@ static int validate_link(struct hists *leader, struct hists *other)
 static void print_hists(struct hists *hists)
 {
 	int i = 0;
-	struct rb_root *root;
-	struct rb_node *node;
-
-	if (sort__need_collapse)
-		root = &hists->entries_collapsed;
-	else
-		root = hists->entries_in;
+	struct hist_entry *he;
 
 	pr_info("----- %s --------\n", __func__);
-	node = rb_first(root);
-	while (node) {
-		struct hist_entry *he;
-
-		he = rb_entry(node, struct hist_entry, rb_node_in);
-
+	hist__for_each_entry_in(he, hists) {
 		pr_info("%2d: entry: %-8s [%-8s] %20s: period = %"PRIu64"\n",
 			i, thread__comm_str(he->thread), he->ms.map->dso->short_name,
 			he->ms.sym->name, he->stat.period);
 
 		i++;
-		node = rb_next(node);
 	}
 }
 
diff --git a/tools/perf/ui/browsers/hists.c b/tools/perf/ui/browsers/hists.c
index 7ec871a..f2693f3 100644
--- a/tools/perf/ui/browsers/hists.c
+++ b/tools/perf/ui/browsers/hists.c
@@ -282,12 +282,11 @@ static void hist_entry__set_folding(struct hist_entry *he, bool unfold)
 
 static void hists__set_folding(struct hists *hists, bool unfold)
 {
-	struct rb_node *nd;
+	struct hist_entry *he;
 
 	hists->nr_entries = 0;
 
-	for (nd = rb_first(&hists->entries); nd; nd = rb_next(nd)) {
-		struct hist_entry *he = rb_entry(nd, struct hist_entry, rb_node);
+	hist__for_each_entry_out(he, hists) {
 		hist_entry__set_folding(he, unfold);
 		hists->nr_entries += 1 + he->nr_rows;
 	}
diff --git a/tools/perf/ui/gtk/hists.c b/tools/perf/ui/gtk/hists.c
index e395ef9..3df6c00a 100644
--- a/tools/perf/ui/gtk/hists.c
+++ b/tools/perf/ui/gtk/hists.c
@@ -155,12 +155,12 @@ static void perf_gtk__show_hists(GtkWidget *window, struct hists *hists,
 	GtkCellRenderer *renderer;
 	struct sort_entry *se;
 	GtkTreeStore *store;
-	struct rb_node *nd;
 	GtkWidget *view;
 	int col_idx;
 	int sym_col = -1;
 	int nr_cols;
 	char s[512];
+	struct hist_entry *h;
 
 	struct perf_hpp hpp = {
 		.buf		= s,
@@ -225,8 +225,7 @@ static void perf_gtk__show_hists(GtkWidget *window, struct hists *hists,
 
 	g_object_unref(GTK_TREE_MODEL(store));
 
-	for (nd = rb_first(&hists->entries); nd; nd = rb_next(nd)) {
-		struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
+	hist__for_each_entry_out(h, hists) {
 		GtkTreeIter iter;
 		float percent = h->stat.period * 100.0 /
 					hists->stats.total_period;
diff --git a/tools/perf/ui/stdio/hist.c b/tools/perf/ui/stdio/hist.c
index d59893e..96defa8 100644
--- a/tools/perf/ui/stdio/hist.c
+++ b/tools/perf/ui/stdio/hist.c
@@ -369,7 +369,6 @@ size_t hists__fprintf(struct hists *hists, bool show_header, int max_rows,
 {
 	struct perf_hpp_fmt *fmt;
 	struct sort_entry *se;
-	struct rb_node *nd;
 	size_t ret = 0;
 	unsigned int width;
 	const char *sep = symbol_conf.field_sep;
@@ -383,6 +382,7 @@ size_t hists__fprintf(struct hists *hists, bool show_header, int max_rows,
 	bool first = true;
 	size_t linesz;
 	char *line = NULL;
+	struct hist_entry *h;
 
 	init_rem_hits();
 
@@ -478,8 +478,7 @@ print_entries:
 		goto out;
 	}
 
-	for (nd = rb_first(&hists->entries); nd; nd = rb_next(nd)) {
-		struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
+	hist__for_each_entry_out(h, hists) {
 		float percent = h->stat.period * 100.0 /
 					hists->stats.total_period;
 
diff --git a/tools/perf/util/hist.c b/tools/perf/util/hist.c
index 57545b3..68eec0f 100644
--- a/tools/perf/util/hist.c
+++ b/tools/perf/util/hist.c
@@ -672,29 +672,18 @@ static void __hists__insert_output_entry(struct rb_root *entries,
 
 void hists__output_resort(struct hists *hists)
 {
-	struct rb_root *root;
-	struct rb_node *next;
 	struct hist_entry *n;
 	u64 min_callchain_hits;
 
 	min_callchain_hits = hists->stats.total_period * (callchain_param.min_percent / 100);
 
-	if (sort__need_collapse)
-		root = &hists->entries_collapsed;
-	else
-		root = hists->entries_in;
-
-	next = rb_first(root);
 	hists->entries = RB_ROOT;
 
 	hists->nr_entries = 0;
 	hists->stats.total_period = 0;
 	hists__reset_col_len(hists);
 
-	while (next) {
-		n = rb_entry(next, struct hist_entry, rb_node_in);
-		next = rb_next(&n->rb_node_in);
-
+	hist__for_each_entry_in(n, hists) {
 		__hists__insert_output_entry(&hists->entries, n, min_callchain_hits);
 		hists__inc_nr_entries(hists, n);
 	}
@@ -897,17 +886,9 @@ static struct hist_entry *hists__find_entry(struct hists *hists,
  */
 void hists__match(struct hists *leader, struct hists *other)
 {
-	struct rb_root *root;
-	struct rb_node *nd;
 	struct hist_entry *pos, *pair;
 
-	if (sort__need_collapse)
-		root = &leader->entries_collapsed;
-	else
-		root = leader->entries_in;
-
-	for (nd = rb_first(root); nd; nd = rb_next(nd)) {
-		pos  = rb_entry(nd, struct hist_entry, rb_node_in);
+	hist__for_each_entry_in(pos, leader) {
 		pair = hists__find_entry(other, pos);
 
 		if (pair)
@@ -922,18 +903,9 @@ void hists__match(struct hists *leader, struct hists *other)
  */
 int hists__link(struct hists *leader, struct hists *other)
 {
-	struct rb_root *root;
-	struct rb_node *nd;
 	struct hist_entry *pos, *pair;
 
-	if (sort__need_collapse)
-		root = &other->entries_collapsed;
-	else
-		root = other->entries_in;
-
-	for (nd = rb_first(root); nd; nd = rb_next(nd)) {
-		pos = rb_entry(nd, struct hist_entry, rb_node_in);
-
+	hist__for_each_entry_in(pos, other) {
 		if (!hist_entry__has_pairs(pos)) {
 			pair = hists__add_dummy_entry(leader, pos);
 			if (pair == NULL)
diff --git a/tools/perf/util/sort.h b/tools/perf/util/sort.h
index 43e5ff4..a089986 100644
--- a/tools/perf/util/sort.h
+++ b/tools/perf/util/sort.h
@@ -22,6 +22,7 @@
 #include "parse-events.h"
 
 #include "thread.h"
+#include "hist.h"
 
 extern regex_t parent_regex;
 extern const char *sort_order;
@@ -129,6 +130,64 @@ static inline void hist_entry__add_pair(struct hist_entry *pair,
 	list_add_tail(&pair->pairs.node, &he->pairs.head);
 }
 
+static inline struct rb_root *hists__get_root(struct hists *hists)
+{
+	if (sort__need_collapse)
+		return &hists->entries_collapsed;
+	else
+		return hists->entries_in;
+}
+
+
+/**
+ * __hist__for_each_entry - iterate thru all the entries in hist
+ * @entry:	struct hist_entry to use as a loop cursor
+ * @root:	struct rb_root that points to the top of an rbtree
+ * @field:	the name of the rb_node within the struct
+ */
+#define __hist__for_each_entry(entry, root, field)				\
+	for (entry = rb_entry_safe(rb_first(root), typeof(*entry), field);	\
+	     entry;								\
+	     entry = rb_entry_safe(rb_next(&entry->field), typeof(*entry), field))
+
+/**
+ * __hist__for_each_entry_safe - iterate thru all the entries in hist, safe against removal of entry
+ * @entry:	struct hist_entry to use as a loop cursor
+ * @next:	struct hist_entry to use as temporary storage
+ * @root:	struct rb_root that points to the top of an rbtree
+ * @field:	the name of the rb_node within the struct
+ */
+#define __hist__for_each_entry_safe(entry, next, root, field)			\
+	for (entry = rb_entry_safe(rb_first(root), typeof(*entry), field);	\
+	     entry && ({ next = rb_entry_safe(rb_next(&entry->field),		\
+			 typeof(*entry), field); 1; });				\
+	     entry = next)
+
+/**
+ * hist__for_each_entry_in - iterate thru all the input entries in hist
+ * @entry:	struct hist_entry to use as a loop cursor
+ * @hists:	struct hists entry that points to an rb_root tree
+ */
+#define hist__for_each_entry_in(entry, hists)					\
+	__hist__for_each_entry(entry, hists__get_root(hists), rb_node_in)
+
+/**
+ * hist__for_each_entry_in_safe - iterate thru all the input entries in hist, safe against removal of entry
+ * @entry:	struct hist_entry to use as a loop cursor
+ * @next:	struct hist_entry to use as temporary storage
+ * @hists:	struct hists entry that points to an rb_root tree
+ */
+#define hist__for_each_entry_in_safe(entry, next, hists)			\
+	__hist__for_each_entry_safe(entry, next, hists__get_root(hists), rb_node_in)
+
+/**
+ * hist__for_each_entry_out - iterate thru all the output entries in hist
+ * @entry:	struct hist_entry to use as a loop cursor
+ * @hists:	struct hists entry that points to an rb_root tree
+ */
+#define hist__for_each_entry_out(entry, hists)					\
+	__hist__for_each_entry(entry, (&hists->entries), rb_node)
+
 enum sort_mode {
 	SORT_MODE__NORMAL,
 	SORT_MODE__BRANCH,
-- 
1.7.11.7

[RFC 3/5] perf: Add in stub hist_entry_group code

[Don Zickus]

What is hist_entry_group?

The idea is to create a new abstract layer between struct hist
and struct hist_entry.  This new layer has the ability to 'group'
entries together and sort them independently for the entry sorting
routines.

For now only one group is created, so there is nothing to sort at the
group level.  Later on, patches will add the ability to sort on cpu,
pid, and cacheline.

In an example, normal sorting on cycles provides the hottest instruction
addresses at the top.  This is great if one particular instruction is
hot.  But when using groups and sorting on pid, one can see a whole
bunch of cycle addresses collectively making a pid hot.

This allows us to view data differently and possibly spot trends.

The main reason for this work is for cacheline sorting.  I needed a way
to organize data addresses into cachelines to do proper entry sorting
later.  This allows me to see the hottest cachelines and the biggest
abusers within that cacheline.

This patch is more an intermediate patch that compiles and
shows the core data structure and changes.  It does nothing
right now.  It doesn't even hook into struct hists yet.

The next patch will do the giant conversion.

Signed-off-by: Don Zickus <dzickus@redhat.com>
---
 tools/perf/util/hist.c | 135 +++++++++++++++++++++++++++++++++++++++++++++++++
 tools/perf/util/hist.h |   2 +
 tools/perf/util/sort.c |   2 +
 tools/perf/util/sort.h |  24 +++++++++
 4 files changed, 163 insertions(+)

diff --git a/tools/perf/util/hist.c b/tools/perf/util/hist.c
index 68eec0f..9b87a1f 100644
--- a/tools/perf/util/hist.c
+++ b/tools/perf/util/hist.c
@@ -317,6 +317,23 @@ static struct hist_entry *hist_entry__new(struct hist_entry *template)
 	return he;
 }
 
+static struct hist_entry_group *hist_group__new(struct hist_entry_group *template)
+{
+	struct hist_entry_group *hg = zalloc(sizeof(*hg));
+
+	if (hg != NULL) {
+		*hg = *template;
+
+		hg->entries_in_array[0] = hg->entries_in_array[1] = RB_ROOT;
+		hg->entries_in = &hg->entries_in_array[0];
+		hg->entries_collapsed = RB_ROOT;
+		hg->entries = RB_ROOT;
+		INIT_LIST_HEAD(&hg->entry.pairs.node);
+	}
+
+	return hg;
+}
+
 void hists__inc_nr_entries(struct hists *hists, struct hist_entry *h)
 {
 	if (!h->filtered) {
@@ -399,6 +416,55 @@ out:
 	return he;
 }
 
+static struct hist_entry_group *add_hist_group(struct hists *hists __maybe_unused,
+					       struct hist_entry_group *group)
+{
+	struct rb_node **p;
+	struct rb_node *parent = NULL;
+	struct hist_entry_group *hg;
+	int64_t cmp;
+	u64 period = group->entry.stat.period;
+	u64 weight = group->entry.stat.weight;
+
+	//p = &hists->groups_in->rb_node;
+	p = &parent;  //REMOVE when groups enabled
+
+	while (*p != NULL) {
+		parent = *p;
+		hg = rb_entry(parent, struct hist_entry_group, rb_node_in);
+
+		/*
+		 * Make sure that it receives arguments in a same order as
+		 * hist_entry__collapse() so that we can use an appropriate
+		 * function when searching an entry regardless which sort
+		 * keys were used.
+		 */
+		cmp = hist_group__cmp(&hg->entry, &group->entry);
+
+		if (!cmp) {
+
+			he_stat__add_period(&hg->entry.stat, period, weight);
+
+			goto out;
+		}
+
+		if (cmp < 0)
+			p = &(*p)->rb_left;
+		else
+			p = &(*p)->rb_right;
+	}
+
+	hg = hist_group__new(group);
+	if (!hg)
+		return NULL;
+
+	//hists->nr_entries++;
+	rb_link_node(&hg->rb_node_in, parent, p);
+	//rb_insert_color(&hg->rb_node_in, hists->groups_in);
+out:
+	return hg;
+};
+
 static struct hist_entry *__hists__add_entry(struct hists *hists,
 					     struct addr_location *al,
 					     struct symbol *sym_parent,
@@ -441,6 +507,41 @@ struct hist_entry *hists__add_entry(struct hists *hists,
 				    u64 period, u64 weight,
 				    u64 transaction)
 {
+	struct hist_entry_group *hg;
+
+	struct hist_entry_group group = {
+		.entry = {
+			.thread	= al->thread,
+			.comm = thread__comm(al->thread),
+			.ms = {
+				.map	= al->map,
+				.sym	= al->sym,
+			},
+			.cpu	 = al->cpu,
+			.ip	 = al->addr,
+			.level	 = al->level,
+			.stat = {
+				.nr_events = 1,
+				.period	= period,
+				.weight = weight,
+			},
+			.parent = sym_parent,
+			.filtered = symbol__parent_filter(sym_parent) | al->filtered,
+			.branch_info = bi,
+			.mem_info = mi,
+			.transaction = transaction,
+		},
+		.hists = hists,
+	};
+
+	/* create group first */
+	hg = add_hist_group(hists, &group);
+	if (!hg)
+		return NULL;
+
+	/* for outputing later */
+	hg->entry.groups = hg;
+
 	return __hists__add_entry(hists, al, sym_parent, bi, mi, period,
 				  weight, transaction);
 }
@@ -487,6 +588,40 @@ void hist_entry__free(struct hist_entry *he)
 	free(he);
 }
 
+int64_t
+hist_group__cmp(struct hist_entry *left, struct hist_entry *right)
+{
+	struct sort_entry *se;
+	int64_t cmp = 0;
+
+	list_for_each_entry(se, &hist_group__sort_list, list) {
+		cmp = se->se_cmp(left, right);
+		if (cmp)
+			break;
+	}
+
+	return cmp;
+}
+
+int64_t
+hist_group__collapse(struct hist_entry *left, struct hist_entry *right)
+{
+	struct sort_entry *se;
+	int64_t cmp = 0;
+
+	list_for_each_entry(se, &hist_group__sort_list, list) {
+		int64_t (*f)(struct hist_entry *, struct hist_entry *);
+
+		f = se->se_collapse ?: se->se_cmp;
+
+		cmp = f(left, right);
+		if (cmp)
+			break;
+	}
+
+	return cmp;
+}
+
 /*
  * collapse the histogram
  */
diff --git a/tools/perf/util/hist.h b/tools/perf/util/hist.h
index 1d24c27..618123b 100644
--- a/tools/perf/util/hist.h
+++ b/tools/perf/util/hist.h
@@ -101,6 +101,8 @@ struct hist_entry *hists__add_entry(struct hists *hists,
 				    u64 weight, u64 transaction);
 int64_t hist_entry__cmp(struct hist_entry *left, struct hist_entry *right);
 int64_t hist_entry__collapse(struct hist_entry *left, struct hist_entry *right);
+int64_t hist_group__cmp(struct hist_entry *left, struct hist_entry *right);
+int64_t hist_group__collapse(struct hist_entry *left, struct hist_entry *right);
 int hist_entry__transaction_len(void);
 int hist_entry__sort_snprintf(struct hist_entry *he, char *bf, size_t size,
 			      struct hists *hists);
diff --git a/tools/perf/util/sort.c b/tools/perf/util/sort.c
index 635cd8f..c292c78 100644
--- a/tools/perf/util/sort.c
+++ b/tools/perf/util/sort.c
@@ -14,11 +14,13 @@ int		sort__need_collapse = 0;
 int		sort__has_parent = 0;
 int		sort__has_sym = 0;
 int		sort__has_dso = 0;
+int		sort__has_group = 0;
 enum sort_mode	sort__mode = SORT_MODE__NORMAL;
 
 enum sort_type	sort__first_dimension;
 
 LIST_HEAD(hist_entry__sort_list);
+LIST_HEAD(hist_group__sort_list);
 
 static int repsep_snprintf(char *bf, size_t size, const char *fmt, ...)
 {
diff --git a/tools/perf/util/sort.h b/tools/perf/util/sort.h
index a089986..a40e856 100644
--- a/tools/perf/util/sort.h
+++ b/tools/perf/util/sort.h
@@ -34,6 +34,7 @@ extern int have_ignore_callees;
 extern int sort__need_collapse;
 extern int sort__has_parent;
 extern int sort__has_sym;
+extern int sort__has_group;
 extern enum sort_mode sort__mode;
 extern struct sort_entry sort_comm;
 extern struct sort_entry sort_dso;
@@ -68,6 +69,8 @@ struct hist_entry_diff {
 	s64	wdiff;
 };
 
+struct hist_entry_group;
+
 /**
  * struct hist_entry - histogram entry
  *
@@ -109,9 +112,29 @@ struct hist_entry {
 	struct branch_info	*branch_info;
 	struct hists		*hists;
 	struct mem_info		*mem_info;
+	struct hist_entry_group	*groups;
 	struct callchain_root	callchain[0]; /* must be last member */
 };
 
+struct hist_entry_group {
+	/* for struct hists */
+	struct rb_node		rb_node_in;
+	struct rb_node		rb_node;
+	struct hists		*hists;
+
+	/* for entries in group */
+	struct rb_root		entries_in_array[2];
+	struct rb_root		*entries_in;
+	struct rb_root		entries;
+	struct rb_root		entries_collapsed;
+	u64			nr_entries;
+
+	u64			event_stream;
+
+	/* embed to allow re-use of sorting code */
+	struct hist_entry	entry;
+};
+
 static inline bool hist_entry__has_pairs(struct hist_entry *he)
 {
 	return !list_empty(&he->pairs.node);
@@ -246,6 +269,7 @@ struct sort_entry {
 
 extern struct sort_entry sort_thread;
 extern struct list_head hist_entry__sort_list;
+extern struct list_head hist_group__sort_list;
 
 int setup_sorting(void);
 extern int sort_dimension__add(const char *);
-- 
1.7.11.7

[RFC 4/5] perf: Switch to using hist_entry_group

[Don Zickus]

This is the fully conversion to using hist_entry_group and having it compile.
The patch is huge because of all the little changes here and there required.

I have only implemented single group, so the output should look identical
to what is currently shown on the perf tool.  The next patch adds group
output.

I added a core set of macros to iterate through each group attached
to the hists rb_tree.  So a bunch of changes looks like:

	hists__for_each_entry_in(....) {

to
	struct hist_entry_group *g;

	hists__for_each_group_in(...) {
		hists_group__for_each_entry_in(...) {

		<tab everything over>

I tried to minimize all the subtle changes for better review, but some could
not be changed without breaking the compile.

A bunch of functions have:

	if (sort__has_group)
		return;

because it wasn't obvious to me how to traverse the group list and entry
list and still fulfill the spirit of the function (most of it was my lack of
understanding how the function works).

Signed-off-by: Don Zickus <dzickus@redhat.com>
---
 tools/perf/builtin-annotate.c  |  11 +-
 tools/perf/builtin-diff.c      |  77 ++++++----
 tools/perf/builtin-top.c       |  12 +-
 tools/perf/tests/hists_link.c  |  69 +++++----
 tools/perf/ui/browsers/hists.c |  37 ++++-
 tools/perf/ui/gtk/hists.c      |  67 +++++----
 tools/perf/ui/hist.c           |  10 +-
 tools/perf/ui/stdio/hist.c     |  33 +++--
 tools/perf/util/evsel.c        |   7 +-
 tools/perf/util/hist.c         | 325 +++++++++++++++++++++++++----------------
 tools/perf/util/hist.h         |  12 +-
 tools/perf/util/sort.h         |  89 ++++++++---
 12 files changed, 471 insertions(+), 278 deletions(-)

diff --git a/tools/perf/builtin-annotate.c b/tools/perf/builtin-annotate.c
index 0157787..98abdd2 100644
--- a/tools/perf/builtin-annotate.c
+++ b/tools/perf/builtin-annotate.c
@@ -114,9 +114,18 @@ static void hists__find_annotations(struct hists *hists,
 				    struct perf_evsel *evsel,
 				    struct perf_annotate *ann)
 {
-	struct rb_node *nd = rb_first(&hists->entries), *next;
+	struct rb_node *gnd = rb_first(&hists->groups);
+	struct rb_node *nd, *next;
+	struct hist_entry_group *hg;
 	int key = K_RIGHT;
 
+	/* only single group supported */
+	if (sort__has_group)
+		return;
+
+	hg = rb_entry(gnd, struct hist_entry_group, rb_node);
+	nd = rb_first(&hg->entries);
+
 	while (nd) {
 		struct hist_entry *he = rb_entry(nd, struct hist_entry, rb_node);
 		struct annotation *notes;
diff --git a/tools/perf/builtin-diff.c b/tools/perf/builtin-diff.c
index 837d0e2..79fd62e 100644
--- a/tools/perf/builtin-diff.c
+++ b/tools/perf/builtin-diff.c
@@ -220,7 +220,7 @@ static int setup_compute(const struct option *opt, const char *str,
 
 static double period_percent(struct hist_entry *he, u64 period)
 {
-	u64 total = he->hists->stats.total_period;
+	u64 total = he->groups->hists->stats.total_period;
 	return (period * 100.0) / total;
 }
 
@@ -262,8 +262,8 @@ static int formula_delta(struct hist_entry *he, struct hist_entry *pair,
 	return scnprintf(buf, size,
 			 "(%" PRIu64 " * 100 / %" PRIu64 ") - "
 			 "(%" PRIu64 " * 100 / %" PRIu64 ")",
-			  pair->stat.period, pair->hists->stats.total_period,
-			  he->stat.period, he->hists->stats.total_period);
+			  pair->stat.period, pair->groups->hists->stats.total_period,
+			  he->stat.period, he->groups->hists->stats.total_period);
 }
 
 static int formula_ratio(struct hist_entry *he, struct hist_entry *pair,
@@ -382,7 +382,7 @@ get_pair_data(struct hist_entry *he, struct data__file *d)
 		struct hist_entry *pair;
 
 		list_for_each_entry(pair, &he->pairs.head, pairs.node)
-			if (pair->hists == d->hists)
+			if (pair->groups->hists == d->hists)
 				return pair;
 	}
 
@@ -401,11 +401,14 @@ get_pair_fmt(struct hist_entry *he, struct diff_hpp_fmt *dfmt)
 static void hists__baseline_only(struct hists *hists)
 {
 	struct hist_entry *he, *next;
-
-	hist__for_each_entry_in_safe(he, next, hists) {
-		if (!hist_entry__next_pair(he)) {
-			rb_erase(&he->rb_node_in, hists__get_root(hists));
-			hist_entry__free(he);
+	struct hist_entry_group *hg, *gnext;
+
+	hist__for_each_group_in_safe(hg, gnext, hists) {
+		hist_group__for_each_entry_in_safe(he, next, hg) {
+			if (!hist_entry__next_pair(he)) {
+				rb_erase(&he->rb_node_in, hists__get_root(hg));
+				hist_entry__free(he);
+			}
 		}
 	}
 }
@@ -413,26 +416,29 @@ static void hists__baseline_only(struct hists *hists)
 static void hists__precompute(struct hists *hists)
 {
 	struct hist_entry *he;
+	struct hist_entry_group *hg;
 
-	hist__for_each_entry_in(he, hists) {
-		struct hist_entry *pair;
-
-		pair = get_pair_data(he, &data__files[sort_compute]);
-		if (!pair)
-			continue;
+	hist__for_each_group_in(hg, hists) {
+		hist_group__for_each_entry_in(he, hg) {
+			struct hist_entry *pair;
 
-		switch (compute) {
-		case COMPUTE_DELTA:
-			compute_delta(he, pair);
-			break;
-		case COMPUTE_RATIO:
-			compute_ratio(he, pair);
-			break;
-		case COMPUTE_WEIGHTED_DIFF:
-			compute_wdiff(he, pair);
-			break;
-		default:
-			BUG_ON(1);
+			pair = get_pair_data(he, &data__files[sort_compute]);
+			if (!pair)
+				continue;
+	
+			switch (compute) {
+			case COMPUTE_DELTA:
+				compute_delta(he, pair);
+				break;
+			case COMPUTE_RATIO:
+				compute_ratio(he, pair);
+				break;
+			case COMPUTE_WEIGHTED_DIFF:
+				compute_wdiff(he, pair);
+				break;
+			default:
+					BUG_ON(1);
+			}
 		}
 	}
 }
@@ -534,16 +540,23 @@ static void insert_hist_entry_by_compute(struct rb_root *root,
 static void hists__compute_resort(struct hists *hists)
 {
 	struct hist_entry *he;
+	struct hist_entry_group *hg;
 
-	hists->entries = RB_ROOT;
+	hists->groups = RB_ROOT;
 
 	hists->nr_entries = 0;
 	hists->stats.total_period = 0;
 	hists__reset_col_len(hists);
 
-	hist__for_each_entry_in(he, hists) {
-		insert_hist_entry_by_compute(&hists->entries, he, compute);
-		hists__inc_nr_entries(hists, he);
+	hist__for_each_group_in(hg, hists) {
+		hg->entries = RB_ROOT;
+		hg->nr_entries = 0;
+		hg->entry.stat.period = 0;
+
+		hist_group__for_each_entry_in(he, hg) {
+			insert_hist_entry_by_compute(&hg->entries, he, compute);
+			hists__inc_nr_entries(hg, he);
+		}
 	}
 }
 
@@ -705,7 +718,7 @@ static const struct option options[] = {
 
 static double baseline_percent(struct hist_entry *he)
 {
-	struct hists *hists = he->hists;
+	struct hists *hists = he->groups->hists;
 	return 100.0 * he->stat.period / hists->stats.total_period;
 }
 
diff --git a/tools/perf/builtin-top.c b/tools/perf/builtin-top.c
index 427f2e2..eda5df3 100644
--- a/tools/perf/builtin-top.c
+++ b/tools/perf/builtin-top.c
@@ -338,6 +338,7 @@ static void perf_top__prompt_symbol(struct perf_top *top, const char *msg)
 {
 	char *buf = malloc(0), *p;
 	struct hist_entry *syme = top->sym_filter_entry, *n, *found = NULL;
+	struct hist_entry_group *g;
 	size_t dummy = 0;
 
 	/* zero counters of active symbol */
@@ -354,13 +355,16 @@ static void perf_top__prompt_symbol(struct perf_top *top, const char *msg)
 	if (p)
 		*p = 0;
 
-	hist__for_each_entry_out(n, (&top->sym_evsel->hists)) {
-		if (n->ms.sym && !strcmp(buf, n->ms.sym->name)) {
-			found = n;
-			break;
+	hist__for_each_group_out(g, (&top->sym_evsel->hists)) {
+		hist_group__for_each_entry_out(n, g) {
+			if (n->ms.sym && !strcmp(buf, n->ms.sym->name)) {
+				found = n;
+				goto found;
+			}
 		}
 	}
 
+found:
 	if (!found) {
 		fprintf(stderr, "Sorry, %s is not active.\n", buf);
 		sleep(1);
diff --git a/tools/perf/tests/hists_link.c b/tools/perf/tests/hists_link.c
index a0def6b..8796e1f 100644
--- a/tools/perf/tests/hists_link.c
+++ b/tools/perf/tests/hists_link.c
@@ -281,16 +281,19 @@ static int __validate_match(struct hists *hists)
 {
 	size_t count = 0;
 	struct hist_entry *he;
-
-	hist__for_each_entry_in(he, hists) {
-		if (hist_entry__has_pairs(he)) {
-			if (find_sample(fake_common_samples,
-					ARRAY_SIZE(fake_common_samples),
-					he->thread, he->ms.map, he->ms.sym)) {
-				count++;
-			} else {
-				pr_debug("Can't find the matched entry\n");
-				return -1;
+	struct hist_entry_group *hg;
+
+	hist__for_each_group_in(hg, hists) {
+		hist_group__for_each_entry_in(he, hg) {
+			if (hist_entry__has_pairs(he)) {
+				if (find_sample(fake_common_samples,
+						ARRAY_SIZE(fake_common_samples),
+						he->thread, he->ms.map, he->ms.sym)) {
+					count++;
+				} else {
+					pr_debug("Can't find the matched entry\n");
+					return -1;
+				}
 			}
 		}
 	}
@@ -315,6 +318,7 @@ static int __validate_link(struct hists *hists, int idx)
 	size_t count_pair = 0;
 	size_t count_dummy = 0;
 	struct hist_entry *he;
+	struct hist_entry_group *hg;
 
 	/*
 	 * Leader hists (idx = 0) will have dummy entries from other,
@@ -322,23 +326,25 @@ static int __validate_link(struct hists *hists, int idx)
 	 * in other hists should have (dummy) pair.
 	 */
 
-	hist__for_each_entry_in(he, hists) {
-		if (hist_entry__has_pairs(he)) {
-			if (!find_sample(fake_common_samples,
-					 ARRAY_SIZE(fake_common_samples),
-					 he->thread, he->ms.map, he->ms.sym) &&
-			    !find_sample(fake_samples[idx],
-					 ARRAY_SIZE(fake_samples[idx]),
-					 he->thread, he->ms.map, he->ms.sym)) {
-				count_dummy++;
+	hist__for_each_group_in(hg, hists) {
+		hist_group__for_each_entry_in(he, hg) {
+			if (hist_entry__has_pairs(he)) {
+				if (!find_sample(fake_common_samples,
+						 ARRAY_SIZE(fake_common_samples),
+						 he->thread, he->ms.map, he->ms.sym) &&
+						 !find_sample(fake_samples[idx],
+						 ARRAY_SIZE(fake_samples[idx]),
+						 he->thread, he->ms.map, he->ms.sym)) {
+					count_dummy++;
+				}
+				count_pair++;
+			} else if (idx) {
+				pr_debug("A entry from the other hists should have pair\n");
+				return -1;
 			}
-			count_pair++;
-		} else if (idx) {
-			pr_debug("A entry from the other hists should have pair\n");
-			return -1;
-		}
 
-		count++;
+			count++;
+		}
 	}
 
 	/*
@@ -380,14 +386,17 @@ static void print_hists(struct hists *hists)
 {
 	int i = 0;
 	struct hist_entry *he;
+	struct hist_entry_group *hg;
 
 	pr_info("----- %s --------\n", __func__);
-	hist__for_each_entry_in(he, hists) {
-		pr_info("%2d: entry: %-8s [%-8s] %20s: period = %"PRIu64"\n",
-			i, thread__comm_str(he->thread), he->ms.map->dso->short_name,
-			he->ms.sym->name, he->stat.period);
+	hist__for_each_group_in(hg, hists) {
+		hist_group__for_each_entry_in(he, hg) {
+			pr_info("%2d: entry: %-8s [%-8s] %20s: period = %"PRIu64"\n",
+				i, thread__comm_str(he->thread), he->ms.map->dso->short_name,
+				he->ms.sym->name, he->stat.period);
 
-		i++;
+			i++;
+		}
 	}
 }
 
diff --git a/tools/perf/ui/browsers/hists.c b/tools/perf/ui/browsers/hists.c
index f2693f3..d1d0658 100644
--- a/tools/perf/ui/browsers/hists.c
+++ b/tools/perf/ui/browsers/hists.c
@@ -283,12 +283,15 @@ static void hist_entry__set_folding(struct hist_entry *he, bool unfold)
 static void hists__set_folding(struct hists *hists, bool unfold)
 {
 	struct hist_entry *he;
+	struct hist_entry_group *hg;
 
 	hists->nr_entries = 0;
 
-	hist__for_each_entry_out(he, hists) {
-		hist_entry__set_folding(he, unfold);
-		hists->nr_entries += 1 + he->nr_rows;
+	hist__for_each_group_out(hg, hists) {
+		hist_group__for_each_entry_out(he, hg) {
+			hist_entry__set_folding(he, unfold);
+			hists->nr_entries += 1 + he->nr_rows;
+		}
 	}
 }
 
@@ -317,9 +320,15 @@ static int hist_browser__run(struct hist_browser *browser, const char *ev_name,
 	int key;
 	char title[160];
 	int delay_secs = hbt ? hbt->refresh : 0;
+	struct hist_entry_group *g;
 
-	browser->b.entries = &browser->hists->entries;
-	browser->b.nr_entries = browser->hists->nr_entries;
+	if (sort__has_group)
+		return -1;
+
+	g = rb_entry_safe(rb_first(&browser->hists->groups), struct hist_entry_group, rb_node);
+
+	browser->b.entries = &g->entries;
+	browser->b.nr_entries = g->nr_entries;
 	if (browser->min_pcnt)
 		browser->b.nr_entries = browser->nr_pcnt_entries;
 
@@ -750,11 +759,17 @@ static int hist_browser__show_entry(struct hist_browser *browser,
 
 static void ui_browser__hists_init_top(struct ui_browser *browser)
 {
+	if (sort__has_group)
+		return;
+
 	if (browser->top == NULL) {
 		struct hist_browser *hb;
+		struct hist_entry_group *g;
 
 		hb = container_of(browser, struct hist_browser, b);
-		browser->top = rb_first(&hb->hists->entries);
+		g = rb_entry_safe(rb_first(&hb->hists->groups),
+				  struct hist_entry_group, rb_node);
+		browser->top = rb_first(&g->entries);
 	}
 }
 
@@ -1326,7 +1341,15 @@ close_file_and_continue:
 static void hist_browser__update_pcnt_entries(struct hist_browser *hb)
 {
 	u64 nr_entries = 0;
-	struct rb_node *nd = rb_first(&hb->hists->entries);
+	struct hist_entry_group *g;
+	struct rb_node *nd;
+
+	if (sort__has_group)
+		return;
+
+	g = rb_entry_safe(rb_first(&hb->hists->groups),
+			  struct hist_entry_group, rb_node);
+	nd = rb_first(&g->entries);
 
 	while (nd) {
 		nr_entries++;
diff --git a/tools/perf/ui/gtk/hists.c b/tools/perf/ui/gtk/hists.c
index 3df6c00a..befbf3b 100644
--- a/tools/perf/ui/gtk/hists.c
+++ b/tools/perf/ui/gtk/hists.c
@@ -161,6 +161,7 @@ static void perf_gtk__show_hists(GtkWidget *window, struct hists *hists,
 	int nr_cols;
 	char s[512];
 	struct hist_entry *h;
+	struct hist_entry_group *g;
 
 	struct perf_hpp hpp = {
 		.buf		= s,
@@ -225,50 +226,52 @@ static void perf_gtk__show_hists(GtkWidget *window, struct hists *hists,
 
 	g_object_unref(GTK_TREE_MODEL(store));
 
-	hist__for_each_entry_out(h, hists) {
-		GtkTreeIter iter;
-		float percent = h->stat.period * 100.0 /
-					hists->stats.total_period;
+	hist__for_each_group_out(g, hists) {
+		hist_group__for_each_entry_out(h, g) {
+			GtkTreeIter iter;
+			float percent = h->stat.period * 100.0 /
+						hists->stats.total_period;
 
-		if (h->filtered)
-			continue;
+			if (h->filtered)
+				continue;
 
-		if (percent < min_pcnt)
-			continue;
+			if (percent < min_pcnt)
+				continue;
 
-		gtk_tree_store_append(store, &iter, NULL);
+			gtk_tree_store_append(store, &iter, NULL);
 
-		col_idx = 0;
+			col_idx = 0;
 
-		perf_hpp__for_each_format(fmt) {
-			if (fmt->color)
-				fmt->color(fmt, &hpp, h);
-			else
-				fmt->entry(fmt, &hpp, h);
+			perf_hpp__for_each_format(fmt) {
+				if (fmt->color)
+					fmt->color(fmt, &hpp, h);
+				else
+					fmt->entry(fmt, &hpp, h);
 
-			gtk_tree_store_set(store, &iter, col_idx++, s, -1);
-		}
+				gtk_tree_store_set(store, &iter, col_idx++, s, -1);
+			}
 
-		list_for_each_entry(se, &hist_entry__sort_list, list) {
-			if (se->elide)
-				continue;
+			list_for_each_entry(se, &hist_entry__sort_list, list) {
+				if (se->elide)
+					continue;
 
-			se->se_snprintf(h, s, ARRAY_SIZE(s),
-					hists__col_len(hists, se->se_width_idx));
+				se->se_snprintf(h, s, ARRAY_SIZE(s),
+						hists__col_len(hists, se->se_width_idx));
 
-			gtk_tree_store_set(store, &iter, col_idx++, s, -1);
-		}
+				gtk_tree_store_set(store, &iter, col_idx++, s, -1);
+			}
 
-		if (symbol_conf.use_callchain && sort__has_sym) {
-			u64 total;
+			if (symbol_conf.use_callchain && sort__has_sym) {
+				u64 total;
 
-			if (callchain_param.mode == CHAIN_GRAPH_REL)
-				total = h->stat.period;
-			else
-				total = hists->stats.total_period;
+				if (callchain_param.mode == CHAIN_GRAPH_REL)
+					total = h->stat.period;
+				else
+					total = hists->stats.total_period;
 
-			perf_gtk__add_callchain(&h->sorted_chain, store, &iter,
-						sym_col, total);
+				perf_gtk__add_callchain(&h->sorted_chain, store, &iter,
+							sym_col, total);
+			}
 		}
 	}
 
diff --git a/tools/perf/ui/hist.c b/tools/perf/ui/hist.c
index 0f403b8..21c4e5c 100644
--- a/tools/perf/ui/hist.c
+++ b/tools/perf/ui/hist.c
@@ -20,7 +20,7 @@ int __hpp__fmt(struct perf_hpp *hpp, struct hist_entry *he,
 	       const char *fmt, hpp_snprint_fn print_fn, bool fmt_percent)
 {
 	int ret = 0;
-	struct hists *hists = he->hists;
+	struct hists *hists = he->groups->hists;
 	struct perf_evsel *evsel = hists_to_evsel(hists);
 	char *buf = hpp->buf;
 	size_t size = hpp->size;
@@ -33,9 +33,9 @@ int __hpp__fmt(struct perf_hpp *hpp, struct hist_entry *he,
 	if (fmt_percent) {
 		double percent = 0.0;
 
-		if (hists->stats.total_period)
+		if (hpp->total_period)
 			percent = 100.0 * get_field(he) /
-				  hists->stats.total_period;
+				  hpp->total_period;
 
 		ret += hpp__call_print_fn(hpp, print_fn, fmt, percent);
 	} else
@@ -50,12 +50,12 @@ int __hpp__fmt(struct perf_hpp *hpp, struct hist_entry *he,
 
 		list_for_each_entry(pair, &he->pairs.head, pairs.node) {
 			u64 period = get_field(pair);
-			u64 total = pair->hists->stats.total_period;
+			u64 total = hpp->total_period; //FIXME for pairs
 
 			if (!total)
 				continue;
 
-			evsel = hists_to_evsel(pair->hists);
+			evsel = hists_to_evsel(pair->groups->hists);
 			idx_delta = perf_evsel__group_idx(evsel) - prev_idx - 1;
 
 			while (idx_delta--) {
diff --git a/tools/perf/ui/stdio/hist.c b/tools/perf/ui/stdio/hist.c
index 96defa8..6c1a85a 100644
--- a/tools/perf/ui/stdio/hist.c
+++ b/tools/perf/ui/stdio/hist.c
@@ -348,6 +348,7 @@ static int hist_entry__fprintf(struct hist_entry *he, size_t size,
 	struct perf_hpp hpp = {
 		.buf		= bf,
 		.size		= size,
+		.total_period	= he->groups->entry.stat.period,
 	};
 
 	if (size == 0 || size > bfsz)
@@ -383,6 +384,7 @@ size_t hists__fprintf(struct hists *hists, bool show_header, int max_rows,
 	size_t linesz;
 	char *line = NULL;
 	struct hist_entry *h;
+	struct hist_entry_group *g;
 
 	init_rem_hits();
 
@@ -478,25 +480,28 @@ print_entries:
 		goto out;
 	}
 
-	hist__for_each_entry_out(h, hists) {
-		float percent = h->stat.period * 100.0 /
-					hists->stats.total_period;
+	hist__for_each_group_out(g, hists) {
+		hist_group__for_each_entry_out(h, g) {
 
-		if (h->filtered)
-			continue;
+			float percent = h->stat.period * 100.0 /
+					g->entry.stat.period;
 
-		if (percent < min_pcnt)
-			continue;
+			if (h->filtered)
+				continue;
+
+			if (percent < min_pcnt)
+				continue;
 
-		ret += hist_entry__fprintf(h, max_cols, hists, line, linesz, fp);
+			ret += hist_entry__fprintf(h, max_cols, hists, line, linesz, fp);
 
-		if (max_rows && ++nr_rows >= max_rows)
-			break;
+			if (max_rows && ++nr_rows >= max_rows)
+				break;
 
-		if (h->ms.map == NULL && verbose > 1) {
-			__map_groups__fprintf_maps(&h->thread->mg,
-						   MAP__FUNCTION, verbose, fp);
-			fprintf(fp, "%.10s end\n", graph_dotted_line);
+			if (h->ms.map == NULL && verbose > 1) {
+				__map_groups__fprintf_maps(&h->thread->mg,
+							   MAP__FUNCTION, verbose, fp);
+				fprintf(fp, "%.10s end\n", graph_dotted_line);
+			}
 		}
 	}
 
diff --git a/tools/perf/util/evsel.c b/tools/perf/util/evsel.c
index 5c28d82..16d46f2 100644
--- a/tools/perf/util/evsel.c
+++ b/tools/perf/util/evsel.c
@@ -118,10 +118,9 @@ void perf_evsel__calc_id_pos(struct perf_evsel *evsel)
 void hists__init(struct hists *hists)
 {
 	memset(hists, 0, sizeof(*hists));
-	hists->entries_in_array[0] = hists->entries_in_array[1] = RB_ROOT;
-	hists->entries_in = &hists->entries_in_array[0];
-	hists->entries_collapsed = RB_ROOT;
-	hists->entries = RB_ROOT;
+	hists->groups_in_array[0] = hists->groups_in_array[1] = RB_ROOT;
+	hists->groups_in = &hists->groups_in_array[0];
+	hists->groups = RB_ROOT;
 	pthread_mutex_init(&hists->lock, NULL);
 }
 
diff --git a/tools/perf/util/hist.c b/tools/perf/util/hist.c
index 9b87a1f..32cdc7a 100644
--- a/tools/perf/util/hist.c
+++ b/tools/perf/util/hist.c
@@ -160,17 +160,20 @@ void hists__calc_col_len(struct hists *hists, struct hist_entry *h)
 
 void hists__output_recalc_col_len(struct hists *hists, int max_rows)
 {
-	struct rb_node *next = rb_first(&hists->entries);
 	struct hist_entry *n;
+	struct hist_entry_group *g;
 	int row = 0;
 
 	hists__reset_col_len(hists);
 
-	while (next && row++ < max_rows) {
-		n = rb_entry(next, struct hist_entry, rb_node);
-		if (!n->filtered)
-			hists__calc_col_len(hists, n);
-		next = rb_next(&n->rb_node);
+	hist__for_each_group_out(g, hists) {
+		hist_group__for_each_entry_out(n, g) {
+			if (!n->filtered)
+				hists__calc_col_len(hists, n);
+
+			if (row++ >= max_rows)
+				return;
+		}
 	}
 }
 
@@ -222,7 +225,7 @@ static void he_stat__decay(struct he_stat *he_stat)
 	/* XXX need decay for weight too? */
 }
 
-static bool hists__decay_entry(struct hists *hists, struct hist_entry *he)
+static bool hists__decay_entry(struct hist_entry_group *hg, struct hist_entry *he)
 {
 	u64 prev_period = he->stat.period;
 
@@ -232,35 +235,35 @@ static bool hists__decay_entry(struct hists *hists, struct hist_entry *he)
 	he_stat__decay(&he->stat);
 
 	if (!he->filtered)
-		hists->stats.total_period -= prev_period - he->stat.period;
+		hg->entry.stat.period -= prev_period - he->stat.period;
 
 	return he->stat.period == 0;
 }
 
 void hists__decay_entries(struct hists *hists, bool zap_user, bool zap_kernel)
 {
-	struct rb_node *next = rb_first(&hists->entries);
 	struct hist_entry *n;
+	struct hist_entry_group *g;
 
-	while (next) {
-		n = rb_entry(next, struct hist_entry, rb_node);
-		next = rb_next(&n->rb_node);
-		/*
-		 * We may be annotating this, for instance, so keep it here in
-		 * case some it gets new samples, we'll eventually free it when
-		 * the user stops browsing and it agains gets fully decayed.
-		 */
-		if (((zap_user && n->level == '.') ||
-		     (zap_kernel && n->level != '.') ||
-		     hists__decay_entry(hists, n)) &&
-		    !n->used) {
-			rb_erase(&n->rb_node, &hists->entries);
-
-			if (sort__need_collapse)
-				rb_erase(&n->rb_node_in, &hists->entries_collapsed);
-
-			hist_entry__free(n);
-			--hists->nr_entries;
+	hist__for_each_group_out(g, hists) {
+		hist_group__for_each_entry_out(n, g) {
+			/*
+			 * We may be annotating this, for instance, so keep it here in
+			 * case some it gets new samples, we'll eventually free it when
+			 * the user stops browsing and it agains gets fully decayed.
+			 */
+			if (((zap_user && n->level == '.') ||
+			     (zap_kernel && n->level != '.') ||
+			     hists__decay_entry(g, n)) &&
+			    !n->used) {
+				rb_erase(&n->rb_node, &g->entries);
+	
+				if (sort__need_collapse)
+					rb_erase(&n->rb_node_in, &g->entries_collapsed);
+	
+				hist_entry__free(n);
+				--g->nr_entries;
+			}
 		}
 	}
 }
@@ -334,15 +337,21 @@ static struct hist_entry_group *hist_group__new(struct hist_entry_group *templat
 	return hg;
 }
 
-void hists__inc_nr_entries(struct hists *hists, struct hist_entry *h)
+void hists__inc_nr_entries(struct hist_entry_group *hg, struct hist_entry *h)
 {
 	if (!h->filtered) {
-		hists__calc_col_len(hists, h);
-		++hists->nr_entries;
-		hists->stats.total_period += h->stat.period;
+		hists__calc_col_len(hg->hists, h);
+		++hg->nr_entries;
+		hg->entry.stat.period += h->stat.period;
 	}
 }
 
+void hists__inc_nr_entry_groups(struct hists *hists, struct hist_entry_group *hg)
+{
+	++hists->nr_entries;
+	hists->stats.total_period += hg->entry.stat.period;
+}
+
 static u8 symbol__parent_filter(const struct symbol *parent)
 {
 	if (symbol_conf.exclude_other && parent == NULL)
@@ -350,7 +359,7 @@ static u8 symbol__parent_filter(const struct symbol *parent)
 	return 0;
 }
 
-static struct hist_entry *add_hist_entry(struct hists *hists,
+static struct hist_entry *add_hist_entry(struct hist_entry_group *hg,
 					 struct hist_entry *entry,
 					 struct addr_location *al)
 {
@@ -361,7 +370,7 @@ static struct hist_entry *add_hist_entry(struct hists *hists,
 	u64 period = entry->stat.period;
 	u64 weight = entry->stat.weight;
 
-	p = &hists->entries_in->rb_node;
+	p = &hg->entries_in->rb_node;
 
 	while (*p != NULL) {
 		parent = *p;
@@ -408,15 +417,15 @@ static struct hist_entry *add_hist_entry(struct hists *hists,
 	if (!he)
 		return NULL;
 
-	hists->nr_entries++;
+	hg->nr_entries++;
 	rb_link_node(&he->rb_node_in, parent, p);
-	rb_insert_color(&he->rb_node_in, hists->entries_in);
+	rb_insert_color(&he->rb_node_in, hg->entries_in);
 out:
 	he_stat__add_cpumode_period(&he->stat, al->cpumode, period);
 	return he;
 }
 
-static struct hist_entry_group *add_hist_group(struct hists *hists __maybe_unused,
+static struct hist_entry_group *add_hist_group(struct hists *hists,
 					       struct hist_entry_group *group)
 {
 	struct rb_node **p;
@@ -426,8 +435,7 @@ static struct hist_entry_group *add_hist_group(struct hists *hists __maybe_unuse
 	u64 period = group->entry.stat.period;
 	u64 weight = group->entry.stat.weight;
 
-	//p = &hists->groups_in->rb_node;
-	p = &parent;  //REMOVE when groups enabled
+	p = &hists->groups_in->rb_node;
 
 	while (*p != NULL) {
 		parent = *p;
@@ -458,14 +466,14 @@ static struct hist_entry_group *add_hist_group(struct hists *hists __maybe_unuse
 	if (!hg)
 		return NULL;
 
-	//hists->nr_entries++;
+	hists->nr_entries++;
 	rb_link_node(&hg->rb_node_in, parent, p);
-	//rb_insert_color(&hg->rb_node_in, hists->groups_in);
+	rb_insert_color(&hg->rb_node_in, hists->groups_in);
 out:
 	return hg;
 };
 
-static struct hist_entry *__hists__add_entry(struct hists *hists,
+static struct hist_entry *__hists__add_entry(struct hist_entry_group *hg,
 					     struct addr_location *al,
 					     struct symbol *sym_parent,
 					     struct branch_info *bi,
@@ -490,13 +498,13 @@ static struct hist_entry *__hists__add_entry(struct hists *hists,
 		},
 		.parent = sym_parent,
 		.filtered = symbol__parent_filter(sym_parent) | al->filtered,
-		.hists	= hists,
+		.groups = hg,
 		.branch_info = bi,
 		.mem_info = mi,
 		.transaction = transaction,
 	};
 
-	return add_hist_entry(hists, &entry, al);
+	return add_hist_entry(hg, &entry, al);
 }
 
 struct hist_entry *hists__add_entry(struct hists *hists,
@@ -542,7 +550,7 @@ struct hist_entry *hists__add_entry(struct hists *hists,
 	/* for outputing later */
 	hg->entry.groups = hg;
 
-	return __hists__add_entry(hists, al, sym_parent, bi, mi, period,
+	return __hists__add_entry(hg, al, sym_parent, bi, mi, period,
 				  weight, transaction);
 }
 
@@ -665,17 +673,17 @@ static bool hists__collapse_insert_entry(struct hists *hists __maybe_unused,
 	return true;
 }
 
-static struct rb_root *hists__get_rotate_entries_in(struct hists *hists)
+static struct rb_root *hists__get_rotate_entries_in(struct hist_entry_group *hg)
 {
 	struct rb_root *root;
 
-	pthread_mutex_lock(&hists->lock);
+	pthread_mutex_lock(&hg->hists->lock);
 
-	root = hists->entries_in;
-	if (++hists->entries_in > &hists->entries_in_array[1])
-		hists->entries_in = &hists->entries_in_array[0];
+	root = hg->entries_in;
+	if (++hg->entries_in > &hg->entries_in_array[1])
+		hg->entries_in = &hg->entries_in_array[0];
 
-	pthread_mutex_unlock(&hists->lock);
+	pthread_mutex_unlock(&hg->hists->lock);
 
 	return root;
 }
@@ -690,32 +698,31 @@ static void hists__apply_filters(struct hists *hists, struct hist_entry *he)
 void hists__collapse_resort(struct hists *hists, struct ui_progress *prog)
 {
 	struct rb_root *root;
-	struct rb_node *next;
-	struct hist_entry *n;
+	struct hist_entry *n, *next;
+	struct hist_entry_group *g;
 
 	if (!sort__need_collapse)
 		return;
 
-	root = hists__get_rotate_entries_in(hists);
-	next = rb_first(root);
-
-	while (next) {
-		if (session_done())
-			break;
-		n = rb_entry(next, struct hist_entry, rb_node_in);
-		next = rb_next(&n->rb_node_in);
-
-		rb_erase(&n->rb_node_in, root);
-		if (hists__collapse_insert_entry(hists, &hists->entries_collapsed, n)) {
-			/*
-			 * If it wasn't combined with one of the entries already
-			 * collapsed, we need to apply the filters that may have
-			 * been set by, say, the hist_browser.
-			 */
-			hists__apply_filters(hists, n);
+	hist__for_each_group_in(g, hists) {
+		root = hists__get_rotate_entries_in(g);
+
+		__hist_group__for_each_entry_safe(n, next, root, rb_node_in) {
+			if (session_done())
+				break;
+
+			rb_erase(&n->rb_node_in, root);
+			if (hists__collapse_insert_entry(hists, &g->entries_collapsed, n)) {
+				/*
+				 * If it wasn't combined with one of the entries already
+				 * collapsed, we need to apply the filters that may have
+				 * been set by, say, the hist_browser.
+				 */
+				hists__apply_filters(hists, n);
+			}
+			if (prog)
+				ui_progress__update(prog, 1);
 		}
-		if (prog)
-			ui_progress__update(prog, 1);
 	}
 }
 
@@ -745,7 +752,7 @@ static int hist_entry__sort_on_period(struct hist_entry *a,
 	if (ret || !symbol_conf.event_group)
 		return ret;
 
-	evsel = hists_to_evsel(a->hists);
+	evsel = hists_to_evsel(a->groups->hists);
 	nr_members = evsel->nr_members;
 	if (nr_members <= 1)
 		return ret;
@@ -757,12 +764,12 @@ static int hist_entry__sort_on_period(struct hist_entry *a,
 		goto out;
 
 	list_for_each_entry(pair, &a->pairs.head, pairs.node) {
-		evsel = hists_to_evsel(pair->hists);
+		evsel = hists_to_evsel(pair->groups->hists);
 		periods_a[perf_evsel__group_idx(evsel)] = pair->stat.period;
 	}
 
 	list_for_each_entry(pair, &b->pairs.head, pairs.node) {
-		evsel = hists_to_evsel(pair->hists);
+		evsel = hists_to_evsel(pair->groups->hists);
 		periods_b[perf_evsel__group_idx(evsel)] = pair->stat.period;
 	}
 
@@ -805,40 +812,64 @@ static void __hists__insert_output_entry(struct rb_root *entries,
 	rb_insert_color(&he->rb_node, entries);
 }
 
+static void __hists__insert_output_entry_group(struct rb_root *groups,
+					       struct hist_entry_group *hg)
+					       
+{
+	struct rb_node **p = &groups->rb_node;
+	struct rb_node *parent = NULL;
+
+	rb_link_node(&hg->rb_node, parent, p);
+	rb_insert_color(&hg->rb_node, groups);
+}
+
 void hists__output_resort(struct hists *hists)
 {
 	struct hist_entry *n;
+	struct hist_entry_group *g;
 	u64 min_callchain_hits;
 
 	min_callchain_hits = hists->stats.total_period * (callchain_param.min_percent / 100);
 
-	hists->entries = RB_ROOT;
+	hists->groups = RB_ROOT;
 
 	hists->nr_entries = 0;
 	hists->stats.total_period = 0;
 	hists__reset_col_len(hists);
 
-	hist__for_each_entry_in(n, hists) {
-		__hists__insert_output_entry(&hists->entries, n, min_callchain_hits);
-		hists__inc_nr_entries(hists, n);
+	hist__for_each_group_in(g, hists) {
+		g->entries = RB_ROOT;
+		g->nr_entries = 0;
+		g->entry.stat.period = 0;
+
+		hist_group__for_each_entry_in(n, g) {
+			__hists__insert_output_entry(&g->entries, n, min_callchain_hits);
+			hists__inc_nr_entries(g, n);
+		}
+
+		/* now that we recacluated entry stats, we can sort the group */ 
+		__hists__insert_output_entry_group(&hists->groups, g);
+		hists__inc_nr_entry_groups(hists, g);
 	}
 }
 
-static void hists__remove_entry_filter(struct hists *hists, struct hist_entry *h,
+static void hists__remove_entry_filter(struct hist_entry_group *hg,
+				       struct hist_entry *h,
 				       enum hist_filter filter)
 {
 	h->filtered &= ~(1 << filter);
 	if (h->filtered)
 		return;
 
-	++hists->nr_entries;
+	++hg->nr_entries;
 	if (h->ms.unfolded)
-		hists->nr_entries += h->nr_rows;
+		hg->nr_entries += h->nr_rows;
 	h->row_offset = 0;
-	hists->stats.total_period += h->stat.period;
-	hists->stats.nr_events[PERF_RECORD_SAMPLE] += h->stat.nr_events;
+	hg->entry.stat.period += h->stat.period;
+	hg->hists->stats.total_period += h->stat.period;
+	hg->entry.stat.nr_events += h->stat.nr_events;
 
-	hists__calc_col_len(hists, h);
+	hists__calc_col_len(hg->hists, h);
 }
 
 
@@ -856,22 +887,28 @@ static bool hists__filter_entry_by_dso(struct hists *hists,
 
 void hists__filter_by_dso(struct hists *hists)
 {
-	struct rb_node *nd;
+	struct hist_entry *h;
+	struct hist_entry_group *g;
 
 	hists->nr_entries = hists->stats.total_period = 0;
 	hists->stats.nr_events[PERF_RECORD_SAMPLE] = 0;
 	hists__reset_col_len(hists);
 
-	for (nd = rb_first(&hists->entries); nd; nd = rb_next(nd)) {
-		struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
+	hist__for_each_group_out(g, hists) {
 
-		if (symbol_conf.exclude_other && !h->parent)
-			continue;
+		g->nr_entries = g->entry.stat.period = 0;
+		g->entry.stat.nr_events = 0;
 
-		if (hists__filter_entry_by_dso(hists, h))
-			continue;
+		hist_group__for_each_entry_out(h, g) {
 
-		hists__remove_entry_filter(hists, h, HIST_FILTER__DSO);
+			if (symbol_conf.exclude_other && !h->parent)
+				continue;
+
+			if (hists__filter_entry_by_dso(hists, h))
+				continue;
+
+			hists__remove_entry_filter(g, h, HIST_FILTER__DSO);
+		}
 	}
 }
 
@@ -889,19 +926,28 @@ static bool hists__filter_entry_by_thread(struct hists *hists,
 
 void hists__filter_by_thread(struct hists *hists)
 {
-	struct rb_node *nd;
+	struct hist_entry *h;
+	struct hist_entry_group *g;
 
 	hists->nr_entries = hists->stats.total_period = 0;
 	hists->stats.nr_events[PERF_RECORD_SAMPLE] = 0;
 	hists__reset_col_len(hists);
 
-	for (nd = rb_first(&hists->entries); nd; nd = rb_next(nd)) {
-		struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
+	hist__for_each_group_out(g, hists) {
+
+		g->nr_entries = g->entry.stat.period = 0;
+		g->entry.stat.nr_events = 0;
+
+		hist_group__for_each_entry_out(h, g) {
+
+			if (symbol_conf.exclude_other && !h->parent)
+				continue;
 
-		if (hists__filter_entry_by_thread(hists, h))
-			continue;
+			if (hists__filter_entry_by_thread(hists, h))
+				continue;
 
-		hists__remove_entry_filter(hists, h, HIST_FILTER__THREAD);
+			hists__remove_entry_filter(g, h, HIST_FILTER__THREAD);
+		}
 	}
 }
 
@@ -920,19 +966,28 @@ static bool hists__filter_entry_by_symbol(struct hists *hists,
 
 void hists__filter_by_symbol(struct hists *hists)
 {
-	struct rb_node *nd;
+	struct hist_entry *h;
+	struct hist_entry_group *g;
 
 	hists->nr_entries = hists->stats.total_period = 0;
 	hists->stats.nr_events[PERF_RECORD_SAMPLE] = 0;
 	hists__reset_col_len(hists);
 
-	for (nd = rb_first(&hists->entries); nd; nd = rb_next(nd)) {
-		struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
+	hist__for_each_group_out(g, hists) {
+
+		g->nr_entries = g->entry.stat.period = 0;
+		g->entry.stat.nr_events = 0;
+
+		hist_group__for_each_entry_out(h, g) {
 
-		if (hists__filter_entry_by_symbol(hists, h))
-			continue;
+			if (symbol_conf.exclude_other && !h->parent)
+				continue;
 
-		hists__remove_entry_filter(hists, h, HIST_FILTER__SYMBOL);
+			if (hists__filter_entry_by_symbol(hists, h))
+				continue;
+
+			hists__remove_entry_filter(g, h, HIST_FILTER__SYMBOL);
+		}
 	}
 }
 
@@ -947,7 +1002,7 @@ void hists__inc_nr_events(struct hists *hists, u32 type)
 	events_stats__inc(&hists->stats, type);
 }
 
-static struct hist_entry *hists__add_dummy_entry(struct hists *hists,
+static struct hist_entry *hists__add_dummy_entry(struct hist_entry_group *groups,
 						 struct hist_entry *pair)
 {
 	struct rb_root *root;
@@ -957,9 +1012,9 @@ static struct hist_entry *hists__add_dummy_entry(struct hists *hists,
 	int64_t cmp;
 
 	if (sort__need_collapse)
-		root = &hists->entries_collapsed;
+		root = &groups->entries_collapsed;
 	else
-		root = hists->entries_in;
+		root = groups->entries_in;
 
 	p = &root->rb_node;
 
@@ -981,25 +1036,25 @@ static struct hist_entry *hists__add_dummy_entry(struct hists *hists,
 	he = hist_entry__new(pair);
 	if (he) {
 		memset(&he->stat, 0, sizeof(he->stat));
-		he->hists = hists;
+		he->groups = groups;
 		rb_link_node(&he->rb_node_in, parent, p);
 		rb_insert_color(&he->rb_node_in, root);
-		hists__inc_nr_entries(hists, he);
+		hists__inc_nr_entries(groups, he);
 		he->dummy = true;
 	}
 out:
 	return he;
 }
 
-static struct hist_entry *hists__find_entry(struct hists *hists,
+static struct hist_entry *hists__find_entry(struct hist_entry_group *hg,
 					    struct hist_entry *he)
 {
 	struct rb_node *n;
 
 	if (sort__need_collapse)
-		n = hists->entries_collapsed.rb_node;
+		n = hg->entries_collapsed.rb_node;
 	else
-		n = hists->entries_in->rb_node;
+		n = hg->entries_in->rb_node;
 
 	while (n) {
 		struct hist_entry *iter = rb_entry(n, struct hist_entry, rb_node_in);
@@ -1022,12 +1077,23 @@ static struct hist_entry *hists__find_entry(struct hists *hists,
 void hists__match(struct hists *leader, struct hists *other)
 {
 	struct hist_entry *pos, *pair;
+	struct hist_entry_group *hg, *ohg;
+
+	/* only single group supported */
+	if (sort__has_group)
+		return;
+
+	ohg = rb_entry_safe(rb_first(other->groups_in), struct hist_entry_group, rb_node_in);
+	if (!ohg)
+		return;
 
-	hist__for_each_entry_in(pos, leader) {
-		pair = hists__find_entry(other, pos);
+	hist__for_each_group_in(hg, leader) {
+		hist_group__for_each_entry_in(pos, hg) {
+			pair = hists__find_entry(ohg, pos);
 
-		if (pair)
-			hist_entry__add_pair(pair, pos);
+			if (pair)
+				hist_entry__add_pair(pair, pos);
+		}
 	}
 }
 
@@ -1039,13 +1105,24 @@ void hists__match(struct hists *leader, struct hists *other)
 int hists__link(struct hists *leader, struct hists *other)
 {
 	struct hist_entry *pos, *pair;
-
-	hist__for_each_entry_in(pos, other) {
-		if (!hist_entry__has_pairs(pos)) {
-			pair = hists__add_dummy_entry(leader, pos);
-			if (pair == NULL)
-				return -1;
-			hist_entry__add_pair(pos, pair);
+	struct hist_entry_group *hg, *lhg;
+
+	/* only single group supported */
+	if (sort__has_group)
+		return -ENOTSUP;
+
+	lhg = rb_entry_safe(rb_first(leader->groups_in), struct hist_entry_group, rb_node_in);
+	if (!lhg)
+		return 0;
+
+	hist__for_each_group_in(hg, other) {
+		hist_group__for_each_entry_in(pos, hg) {
+			if (!hist_entry__has_pairs(pos)) {
+				pair = hists__add_dummy_entry(lhg, pos);
+				if (pair == NULL)
+					return -1;
+				hist_entry__add_pair(pos, pair);
+			}
 		}
 	}
 
diff --git a/tools/perf/util/hist.h b/tools/perf/util/hist.h
index 618123b..1155397 100644
--- a/tools/perf/util/hist.h
+++ b/tools/perf/util/hist.h
@@ -11,6 +11,7 @@
 extern struct callchain_param callchain_param;
 
 struct hist_entry;
+struct hist_entry_group;
 struct addr_location;
 struct symbol;
 
@@ -78,10 +79,9 @@ struct thread;
 struct dso;
 
 struct hists {
-	struct rb_root		entries_in_array[2];
-	struct rb_root		*entries_in;
-	struct rb_root		entries;
-	struct rb_root		entries_collapsed;
+	struct rb_root		groups_in_array[2];
+	struct rb_root		*groups_in;
+	struct rb_root		groups;
 	u64			nr_entries;
 	const struct thread	*thread_filter;
 	const struct dso	*dso_filter;
@@ -114,7 +114,8 @@ void hists__collapse_resort(struct hists *hists, struct ui_progress *prog);
 void hists__decay_entries(struct hists *hists, bool zap_user, bool zap_kernel);
 void hists__output_recalc_col_len(struct hists *hists, int max_rows);
 
-void hists__inc_nr_entries(struct hists *hists, struct hist_entry *h);
+void hists__inc_nr_entries(struct hist_entry_group *hg, struct hist_entry *h);
+void hists__inc_nr_entry_groups(struct hists *hists, struct hist_entry_group *hg);
 void hists__inc_nr_events(struct hists *hists, u32 type);
 void events_stats__inc(struct events_stats *stats, u32 type);
 size_t events_stats__fprintf(struct events_stats *stats, FILE *fp);
@@ -140,6 +141,7 @@ struct perf_hpp {
 	size_t size;
 	const char *sep;
 	void *ptr;
+	u64 total_period;
 };
 
 struct perf_hpp_fmt {
diff --git a/tools/perf/util/sort.h b/tools/perf/util/sort.h
index a40e856..ff24050 100644
--- a/tools/perf/util/sort.h
+++ b/tools/perf/util/sort.h
@@ -110,7 +110,6 @@ struct hist_entry {
 	unsigned long		position;
 	struct rb_root		sorted_chain;
 	struct branch_info	*branch_info;
-	struct hists		*hists;
 	struct mem_info		*mem_info;
 	struct hist_entry_group	*groups;
 	struct callchain_root	callchain[0]; /* must be last member */
@@ -153,63 +152,113 @@ static inline void hist_entry__add_pair(struct hist_entry *pair,
 	list_add_tail(&pair->pairs.node, &he->pairs.head);
 }
 
-static inline struct rb_root *hists__get_root(struct hists *hists)
+static inline struct rb_root *hists__get_root(struct hist_entry_group *groups)
 {
 	if (sort__need_collapse)
-		return &hists->entries_collapsed;
+		return &groups->entries_collapsed;
 	else
-		return hists->entries_in;
+		return groups->entries_in;
 }
 
-
 /**
- * __hist__for_each_entry - iterate thru all the entries in hist
+ * __hist_group__for_each_entry - iterate thru all the entries in groups
  * @entry:	struct hist_entry to use as a loop cursor
  * @root:	struct rb_root that points to the top of an rbtree
  * @field:	the name of the rb_node within the struct
  */
-#define __hist__for_each_entry(entry, root, field)				\
-	for (entry = rb_entry_safe(rb_first(root), typeof(*entry), field);	\
-	     entry;								\
+#define __hist_group__for_each_entry(entry, root, field)					\
+	for (entry = rb_entry_safe(rb_first(root), typeof(*entry), field);			\
+	     entry;										\
 	     entry = rb_entry_safe(rb_next(&entry->field), typeof(*entry), field))
 
 /**
- * __hist__for_each_entry_safe - iterate thru all the entries in hist, safe against removal of entry
+ * __hist_group__for_each_entry_safe - iterate thru all the entries in groups,
+ * 				       safe against removal of entry
  * @entry:	struct hist_entry to use as a loop cursor
  * @next:	struct hist_entry to use as temporary storage
  * @root:	struct rb_root that points to the top of an rbtree
  * @field:	the name of the rb_node within the struct
  */
-#define __hist__for_each_entry_safe(entry, next, root, field)			\
+#define __hist_group__for_each_entry_safe(entry, next, root, field)			\
 	for (entry = rb_entry_safe(rb_first(root), typeof(*entry), field);	\
 	     entry && ({ next = rb_entry_safe(rb_next(&entry->field),		\
 			 typeof(*entry), field); 1; });				\
 	     entry = next)
 
 /**
- * hist__for_each_entry_in - iterate thru all the input entries in hist
+ * hist_group__for_each_entry_in - iterate thru all the input entries in groups
  * @entry:	struct hist_entry to use as a loop cursor
  * @hists:	struct hists entry that points to an rb_root tree
  */
-#define hist__for_each_entry_in(entry, hists)					\
-	__hist__for_each_entry(entry, hists__get_root(hists), rb_node_in)
+#define hist_group__for_each_entry_in(entry, groups)					\
+	__hist_group__for_each_entry(entry, hists__get_root(groups), rb_node_in)
 
 /**
- * hist__for_each_entry_in_safe - iterate thru all the input entries in hist, safe against removal of entry
+ * hist_group__for_each_entry_in_safe - iterate thru all the input entries in groups,
+ * 					safe against removal of entry
  * @entry:	struct hist_entry to use as a loop cursor
  * @next:	struct hist_entry to use as temporary storage
  * @hists:	struct hists entry that points to an rb_root tree
  */
-#define hist__for_each_entry_in_safe(entry, next, hists)			\
-	__hist__for_each_entry_safe(entry, next, hists__get_root(hists), rb_node_in)
+#define hist_group__for_each_entry_in_safe(entry, next, groups)			\
+	__hist_group__for_each_entry_safe(entry, next, hists__get_root(groups), rb_node_in)
 
 /**
- * hist__for_each_entry_out - iterate thru all the output entries in hist
+ * hist_group__for_each_entry_out - iterate thru all the output entries in groups
  * @entry:	struct hist_entry to use as a loop cursor
  * @hists:	struct hists entry that points to an rb_root tree
  */
-#define hist__for_each_entry_out(entry, hists)					\
-	__hist__for_each_entry(entry, (&hists->entries), rb_node)
+#define hist_group__for_each_entry_out(entry, groups)					\
+	__hist_group__for_each_entry(entry, (&groups->entries), rb_node)
+
+/**
+ * __hist__for_each_group - iterate thru all the groups in hist
+ * @group:	struct hist_entry_group to use as a loop cursor
+ * @root:	struct rb_root that points to the top of an rbtree
+ * @field:	the name of the rb_node within the struct
+ */
+#define __hist__for_each_group(group, root, field)					\
+	for (group = rb_entry_safe(rb_first(root), typeof(*group), field);			\
+	     group;										\
+	     group = rb_entry_safe(rb_next(&group->field), typeof(*group), field))
+
+/**
+ * __hist__for_each_group_safe - iterate thru all the groups in hist, safe against removal of group
+ * @group:	struct hist_entry_group to use as a loop cursor
+ * @next:	struct hist_entry_group to use as temporary storage
+ * @root:	struct rb_root that points to the top of an rbtree
+ * @field:	the name of the rb_node within the struct
+ */
+#define __hist__for_each_group_safe(group, next, root, field)			\
+	for (group = rb_entry_safe(rb_first(root), typeof(*group), field);	\
+	     group && ({ next = rb_entry_safe(rb_next(&group->field),		\
+			 typeof(*group), field); 1; });				\
+	     group = next)
+
+/**
+ * hist__for_each_group_in - iterate thru all the input groups in hist
+ * @group:	struct hist_entry_group to use as a loop cursor
+ * @hists:	struct hists entry that points to an rb_root tree
+ */
+#define hist__for_each_group_in(group, hists)					\
+	__hist__for_each_group(group, hists->groups_in, rb_node_in)
+
+/**
+ * hist__for_each_group_in_safe - iterate thru all the input groups in hist, safe against removal of group
+ * @group:	struct hist_entry_group to use as a loop cursor
+ * @next:	struct hist_entry_group to use as temporary storage
+ * @hists:	struct hists entry that points to an rb_root tree
+ */
+#define hist__for_each_group_in_safe(group, next, hists)			\
+	__hist__for_each_group_safe(group, next, hists->groups_in, rb_node_in)
+
+/**
+ * hist__for_each_group_in - iterate thru all the output groups in hist
+ * @group:	struct hist_entry_group to use as a loop cursor
+ * @hists:	struct hists entry that points to an rb_root tree
+ */
+#define hist__for_each_group_out(group, hists)					\
+	__hist__for_each_group(group, (&hists->groups), rb_node)
 
 enum sort_mode {
 	SORT_MODE__NORMAL,
-- 
1.7.11.7

[RFC 5/5] perf: Enable multiple hist_entry_group output

[Don Zickus]

Enable multiple hist_entry_group groups in the output based on a sort
method.

Currently only 'perf report' is hooked in with '--group-sort='.  The choices
are cpu, pid, and cacheline.  Only --stdio works right now.  I haven't figured
out how the other outputs work.

Sample output from 'perf mem record -a grep -r foo /* > /dev/null'

(normal) perf mem report --percent-limit=1.0 --stdio

 Overhead       Samples
  Local Weight             Memory access                                      Symbol
 ........  ............  ............  ........................  ........................

     4.13%             1  1759          Uncached hit              [k] ahci_scr_read
     1.16%             1  492           L1 hit                    [k] _raw_read_lock

(cpu groups) perf mem report --group-sort=cpu --percent-limit=1.0 --stdio

 Overhead       Samples  CPU
  Local Weight             Memory access                                      Symbol
 ........  ............  ............  ........................  ........................

    28.80%          1239   25
	     3.07%               377           L1 hit                    [k] complete_walk
	     2.76%               339           LFB hit                   [k] update_cfs_shares
	     2.66%               326           LFB hit                   [k] copy_user_enhanced_f
	     2.11%               259           Local RAM hit             [k] copy_user_enhanced_f
	     1.84%               226           LFB hit                   [k] copy_user_enhanced_f
	     1.74%               213           LFB hit                   [k] copy_user_enhanced_f
	     1.53%               187           LFB hit                   [k] copy_user_enhanced_f
	     1.04%               128           LFB hit                   [k] copy_user_enhanced_f
	     1.01%               124           LFB hit                   [k] copy_user_enhanced_f
    27.44%           990    7
	    15.06%               1759          Uncached hit              [k] ahci_scr_read
	     4.21%               492           L1 hit                    [k] _raw_read_lock
	     1.04%               122           LFB hit                   [k] find_busiest_group
	     1.02%            1  7             L1 hit                    [.] __gconv_transform_ut
    20.34%          1010    0
	     4.04%            5  7             L1 hit                    [k] poll_idle
	     3.56%               308           Local RAM hit             [k] copy_user_enhanced_f
	     2.59%               224           L3 hit                    [k] copy_user_enhanced_f
	     2.12%               184           Local RAM hit             [k] copy_user_enhanced_f
	     1.54%            1  7             L1 hit                    [.] __gconv_transform_ut

(pid groups) perf mem report --group-sort=pid --percent-limit=1.0 --stdio

 Overhead       Samples       Command:  Pid
  Local Weight             Memory access                                      Symbol
 ........  ............  ............  ........................  ........................

    67.98%          3023          grep:77842
	     1.70%               492           L1 hit                    [k] _raw_read_lock
	     1.30%               377           L1 hit                    [k] complete_walk
	     1.17%               339           LFB hit                   [k] update_cfs_shares
	     1.13%               326           LFB hit                   [k] copy_user_enhanced_f
	     1.09%            4  7             L1 hit                    [.] __gconv_transform_ut
	     1.06%               308           Local RAM hit             [k] copy_user_enhanced_f
    23.39%           660       swapper:    0
	    17.66%               1759          Uncached hit              [k] ahci_scr_read
	     4.17%               415           L1 hit                    [k] handle_irq
	     3.51%            5  7             L1 hit                    [k] poll_idle
	     3.34%               333           Remote Cache (1 hop) hit  [k] update_cfs_rq_blocke
	     2.79%               278           LFB hit                   [k] add_interrupt_random
	     2.69%               268           L1 hit                    [k] update_cpu_load_nohz
	     2.69%               268           Local RAM hit             [k] find_busiest_group
	     2.51%               250           LFB hit                   [k] ktime_get
	     2.45%               244           L1 hit                    [k] rcu_eqs_exit_common.
	     1.89%               188           LFB hit                   [k] ktime_get
	     1.25%               124           LFB hit                   [k] get_next_timer_inter
     5.90%           186     rcu_sched:    8
	     6.14%               154           L1 hit                    [k] _raw_spin_lock_irq
	     4.42%               111           L1 hit                    [k] _raw_spin_lock_irqsa
	     3.90%               49            L3 hit                    [k] find_busiest_group
	     3.11%               78            LFB hit                   [k] find_busiest_group
	     3.11%               78            LFB hit                   [k] find_busiest_group
	     2.39%               60            LFB hit                   [k] idle_cpu
	     2.27%               57            L3 hit                    [k] idle_cpu
	     2.27%               57            L3 hit                    [k] idle_cpu
	     2.19%               55            L3 hit                    [k] target_load

(cacheline groups) perf mem report --group-sort=cacheline --percent-limit=1.0 --stdio

 Overhead       Samples  Cacheline
  Local Weight             Memory access                                      Symbol
 ........  ............  ............  ........................  ........................

     4.67%           284  [.] 0x0000000000b030c0
	     1.76%               7             L1 hit                    [.] 0x0000000000008651
	     1.41%               7             L1 hit                    [.] 0x00000000000085cc
	     1.41%               7             L1 hit                    [.] 0x00000000000085e4
	     1.41%               7             L1 hit                    [.] 0x00000000000085e4
	     1.41%               7             L1 hit                    [.] 0x00000000000085f8
	     1.41%               7             L1 hit                    [.] 0x0000000000008624
	     1.06%               7             L1 hit                    [.] 0x00000000000085d8
	     1.06%               7             L1 hit                    [.] 0x00000000000085e4
	     1.06%               7             L1 hit                    [.] 0x00000000000085e4
	     1.06%               7             L1 hit                    [.] 0x0000000000008610
	     1.06%               7             L1 hit                    [.] 0x0000000000008610
	     1.06%               7             L1 hit                    [.] 0x0000000000008624
	     1.06%               7             L1 hit                    [.] 0x0000000000008624
	     1.06%               7             L1 hit                    [.] 0x0000000000008645
	     1.06%               7             L1 hit                    [.] 0x0000000000008645
	     1.06%               7             L1 hit                    [.] 0x0000000000008645
	     1.06%               7             L1 hit                    [.] 0x0000000000008651
	     1.06%               7             L1 hit                    [.] 0x0000000000008651
     4.26%           250  [.] 0x0000000000b03080
	     3.91%               71            L3 hit                    [.] 0x0000000000008651
	     1.54%               7             L1 hit                    [.] 0x00000000000085d8
	     1.16%               7             L1 hit                    [.] 0x00000000000085cc
	     1.16%               7             L1 hit                    [.] 0x00000000000085f8
	     1.16%               7             L1 hit                    [.] 0x0000000000008604
	     1.16%               7             L1 hit                    [.] 0x0000000000008624
	     1.16%               7             L1 hit                    [.] 0x0000000000008645
	     1.16%               7             L1 hit                    [.] 0x0000000000008645
	     1.16%               7             L1 hit                    [.] 0x0000000000008645
     4.13%             1  [k] 0xffffc90000062180
	   100.00%               1759          Uncached hit              [k] ahci_scr_read
     3.44%           209  [.] 0x0000000000b03040
	     6.70%            1  7             L1 hit                    [.] 0x00000000000085e4
	     6.22%            1  7             L1 hit                    [.] 0x0000000000008624
	     5.74%            1  7             L1 hit                    [.] 0x00000000000085cc
	     5.74%            1  7             L1 hit                    [.] 0x0000000000008610
	     5.74%            1  7             L1 hit                    [.] 0x0000000000008645
	     5.26%            1  7             L1 hit                    [.] 0x00000000000085d8
	     5.26%            1  7             L1 hit                    [.] 0x0000000000008651
	     4.78%            1  7             L1 hit                    [.] 0x00000000000085f8
	     4.78%            1  7             L1 hit                    [.] 0x0000000000008604
	     2.87%               7             L1 hit                    [.] 0x0000000000008630
	     1.44%               7             L1 hit                    [.] 0x00000000000085f8

Signed-off-by: Don Zickus <dzickus@redhat.com>
---
 tools/perf/builtin-report.c |   2 +
 tools/perf/ui/gtk/hists.c   |  10 +++
 tools/perf/ui/hist.c        |  19 +++++
 tools/perf/ui/stdio/hist.c  |  69 ++++++++++++++++-
 tools/perf/util/hist.c      |  17 +++++
 tools/perf/util/hist.h      |   3 +
 tools/perf/util/sort.c      | 181 +++++++++++++++++++++++++++++++++++++++++++-
 tools/perf/util/sort.h      |   4 +
 8 files changed, 301 insertions(+), 4 deletions(-)

diff --git a/tools/perf/builtin-report.c b/tools/perf/builtin-report.c
index 51a37d6..010271e 100644
--- a/tools/perf/builtin-report.c
+++ b/tools/perf/builtin-report.c
@@ -764,6 +764,8 @@ int cmd_report(int argc, const char **argv, const char *prefix __maybe_unused)
 		   " dso_to, dso_from, symbol_to, symbol_from, mispredict,"
 		   " weight, local_weight, mem, symbol_daddr, dso_daddr, tlb, "
 		   "snoop, locked, abort, in_tx, transaction"),
+	OPT_STRING(0, "group-sort", &group_sort_order, "key[,key2...]",
+		   "group sort by key(s): pid, cacheline"),
 	OPT_BOOLEAN(0, "showcpuutilization", &symbol_conf.show_cpu_utilization,
 		    "Show sample percentage for different cpu modes"),
 	OPT_STRING('p', "parent", &parent_pattern, "regex",
diff --git a/tools/perf/ui/gtk/hists.c b/tools/perf/ui/gtk/hists.c
index befbf3b..ab9c96a 100644
--- a/tools/perf/ui/gtk/hists.c
+++ b/tools/perf/ui/gtk/hists.c
@@ -200,6 +200,16 @@ static void perf_gtk__show_hists(GtkWidget *window, struct hists *hists,
 							    col_idx++, NULL);
 	}
 
+	list_for_each_entry(se, &hist_group__sort_list, list) {
+		if (se->elide)
+			continue;
+
+		gtk_tree_view_insert_column_with_attributes(GTK_TREE_VIEW(view),
+							    -1, se->se_header,
+							    renderer, "text",
+							    col_idx++, NULL);
+	}
+
 	list_for_each_entry(se, &hist_entry__sort_list, list) {
 		if (se->elide)
 			continue;
diff --git a/tools/perf/ui/hist.c b/tools/perf/ui/hist.c
index 21c4e5c..31c74b3 100644
--- a/tools/perf/ui/hist.c
+++ b/tools/perf/ui/hist.c
@@ -319,6 +319,25 @@ int hist_entry__sort_snprintf(struct hist_entry *he, char *s, size_t size,
 	return ret;
 }
 
+int hist_entry_group__sort_snprintf(struct hist_entry *he, char *s, size_t size,
+			      struct hists *hists)
+{
+	const char *sep = symbol_conf.field_sep;
+	struct sort_entry *se;
+	int ret = 0;
+
+	list_for_each_entry(se, &hist_group__sort_list, list) {
+		if (se->elide)
+			continue;
+
+		ret += scnprintf(s + ret, size - ret, "%s", sep ?: "  ");
+		ret += se->se_snprintf(he, s + ret, size - ret,
+				       hists__col_len(hists, se->se_width_idx));
+	}
+
+	return ret;
+}
+
 /*
  * See hists__fprintf to match the column widths
  */
diff --git a/tools/perf/ui/stdio/hist.c b/tools/perf/ui/stdio/hist.c
index 6c1a85a..c3d3c1b 100644
--- a/tools/perf/ui/stdio/hist.c
+++ b/tools/perf/ui/stdio/hist.c
@@ -354,6 +354,10 @@ static int hist_entry__fprintf(struct hist_entry *he, size_t size,
 	if (size == 0 || size > bfsz)
 		size = hpp.size = bfsz;
 
+	if (sort__has_group) {
+		*hpp.buf++ = '\t';
+		hpp.size--;
+	}
 	ret = hist_entry__period_snprintf(&hpp, he);
 	hist_entry__sort_snprintf(he, bf + ret, size - ret, hists);
 
@@ -365,6 +369,28 @@ static int hist_entry__fprintf(struct hist_entry *he, size_t size,
 	return ret;
 }
 
+static int hist_entry_group__fprintf(struct hist_entry *he, size_t size,
+				     struct hists *hists,
+				     char *bf, size_t bfsz, FILE *fp)
+{
+	int ret;
+	struct perf_hpp hpp = {
+		.buf		= bf,
+		.size		= size,
+		.total_period	= he->groups->hists->stats.total_period,
+	};
+
+	if (size == 0 || size > bfsz)
+		size = hpp.size = bfsz;
+
+	ret = hist_entry__period_snprintf(&hpp, he);
+	hist_entry_group__sort_snprintf(he, bf + ret, size - ret, hists);
+
+	ret = fprintf(fp, "%s\n", bf);
+
+	return ret;
+}
+
 size_t hists__fprintf(struct hists *hists, bool show_header, int max_rows,
 		      int max_cols, float min_pcnt, FILE *fp)
 {
@@ -403,6 +429,32 @@ size_t hists__fprintf(struct hists *hists, bool show_header, int max_rows,
 		fprintf(fp, "%s", bf);
 	}
 
+	list_for_each_entry(se, &hist_group__sort_list, list) {
+		if (se->elide)
+			continue;
+		if (sep) {
+			fprintf(fp, "%c%s", *sep, se->se_header);
+			continue;
+		}
+		width = strlen(se->se_header);
+		if (symbol_conf.col_width_list_str) {
+			if (col_width) {
+				hists__set_col_len(hists, se->se_width_idx,
+						   atoi(col_width));
+				col_width = strchr(col_width, ',');
+				if (col_width)
+					++col_width;
+			}
+		}
+		if (!hists__new_col_len(hists, se->se_width_idx, width))
+			width = hists__col_len(hists, se->se_width_idx);
+		fprintf(fp, "  %*s", width, se->se_header);
+	}
+
+	fprintf(fp, "\n");
+	if (max_rows && ++nr_rows >= max_rows)
+		goto out;
+
 	list_for_each_entry(se, &hist_entry__sort_list, list) {
 		if (se->elide)
 			continue;
@@ -481,9 +533,22 @@ print_entries:
 	}
 
 	hist__for_each_group_out(g, hists) {
-		hist_group__for_each_entry_out(h, g) {
+		float percent = g->entry.stat.period * 100.0 /
+					hists->stats.total_period;
+
+		if (percent < min_pcnt)
+			continue;
 
-			float percent = h->stat.period * 100.0 /
+		if (sort__has_group) {
+			ret += hist_entry_group__fprintf(&g->entry, max_cols, hists,
+							 line, linesz, fp);
+
+			if (max_rows && ++nr_rows >= max_rows)
+				break;
+		}
+
+		hist_group__for_each_entry_out(h, g) {
+			percent = h->stat.period * 100.0 /
 					g->entry.stat.period;
 
 			if (h->filtered)
diff --git a/tools/perf/util/hist.c b/tools/perf/util/hist.c
index 32cdc7a..f9735c4 100644
--- a/tools/perf/util/hist.c
+++ b/tools/perf/util/hist.c
@@ -786,6 +786,12 @@ out:
 	return ret;
 }
 
+static int hist_entry_group__sort_on_period(struct hist_entry_group *a,
+					    struct hist_entry_group *b)
+{
+	return period_cmp(a->entry.stat.period, b->entry.stat.period);
+}
+
 static void __hists__insert_output_entry(struct rb_root *entries,
 					 struct hist_entry *he,
 					 u64 min_callchain_hits)
@@ -818,6 +824,17 @@ static void __hists__insert_output_entry_group(struct rb_root *groups,
 {
 	struct rb_node **p = &groups->rb_node;
 	struct rb_node *parent = NULL;
+	struct hist_entry_group *iter;
+
+	while (*p != NULL) {
+		parent = *p;
+		iter = rb_entry(parent, struct hist_entry_group, rb_node);
+
+		if (hist_entry_group__sort_on_period(hg, iter) > 0)
+			p = &(*p)->rb_left;
+		else
+			p = &(*p)->rb_right;
+	}
 
 	rb_link_node(&hg->rb_node, parent, p);
 	rb_insert_color(&hg->rb_node, groups);
diff --git a/tools/perf/util/hist.h b/tools/perf/util/hist.h
index 1155397..75a041c 100644
--- a/tools/perf/util/hist.h
+++ b/tools/perf/util/hist.h
@@ -71,6 +71,7 @@ enum hist_column {
 	HISTC_MEM_TLB,
 	HISTC_MEM_LVL,
 	HISTC_MEM_SNOOP,
+	HISTC_MEM_CACHELINE,
 	HISTC_TRANSACTION,
 	HISTC_NR_COLS, /* Last entry */
 };
@@ -106,6 +107,8 @@ int64_t hist_group__collapse(struct hist_entry *left, struct hist_entry *right);
 int hist_entry__transaction_len(void);
 int hist_entry__sort_snprintf(struct hist_entry *he, char *bf, size_t size,
 			      struct hists *hists);
+int hist_entry_group__sort_snprintf(struct hist_entry *he, char *bf, size_t size,
+				    struct hists *hists);
 void hist_entry__free(struct hist_entry *);
 
 void hists__output_resort(struct hists *hists);
diff --git a/tools/perf/util/sort.c b/tools/perf/util/sort.c
index c292c78..bfb4a668 100644
--- a/tools/perf/util/sort.c
+++ b/tools/perf/util/sort.c
@@ -8,6 +8,8 @@ const char	default_parent_pattern[] = "^sys_|^do_page_fault";
 const char	*parent_pattern = default_parent_pattern;
 const char	default_sort_order[] = "comm,dso,symbol";
 const char	*sort_order = default_sort_order;
+const char	default_group_sort_order[] = "";
+const char	*group_sort_order = default_group_sort_order;
 regex_t		ignore_callees_regex;
 int		have_ignore_callees = 0;
 int		sort__need_collapse = 0;
@@ -61,7 +63,7 @@ static int64_t cmp_null(const void *l, const void *r)
 static int64_t
 sort__thread_cmp(struct hist_entry *left, struct hist_entry *right)
 {
-	return right->thread->tid - left->thread->tid;
+	return right->thread->pid_ - left->thread->pid_;
 }
 
 static int hist_entry__thread_snprintf(struct hist_entry *he, char *bf,
@@ -809,6 +811,94 @@ static int hist_entry__global_weight_snprintf(struct hist_entry *he, char *bf,
 	return repsep_snprintf(bf, size, "%-*llu", width, he->stat.weight);
 }
 
+#define L1_CACHE_BYTES 64
+#define CACHELINE_MASK (L1_CACHE_BYTES - 1)
+#define CL(x)  (x & ~CACHELINE_MASK)
+
+static int64_t
+sort__cacheline_cmp(struct hist_entry *left, struct hist_entry *right)
+{
+	u64 l, r;
+	struct map *l_map = left->mem_info->daddr.map;
+	struct map *r_map = right->mem_info->daddr.map;
+
+	/* store all NULL mem maps at the bottom */
+	/* shouldn't even need this check, should have stubs */
+	if (!left->mem_info->daddr.map || !right->mem_info->daddr.map)
+		return 1;
+
+	/* group event types together */
+	if (left->cpumode > right->cpumode) return -1;
+	if (left->cpumode < right->cpumode) return 1;
+
+	/*
+	 * Addresses with no major/minor numbers are assumed to be
+	 * anonymous in userspace.  Sort those on pid then address.
+	 *
+	 * The kernel and non-zero major/minor mapped areas are
+	 * assumed to be unity mapped.  Sort those on address then pid.
+	 */
+
+	if ((l_map->maj || l_map->min || l_map->ino || l_map-> ino_generation)) {
+		/* mmapped areas */
+
+		if (l_map->maj > r_map->maj) return -1;
+		if (l_map->maj < r_map->maj) return 1;
+
+		if (l_map->min > r_map->min) return -1;
+		if (l_map->min < r_map->min) return 1;
+
+		if (l_map->ino > r_map->ino) return -1;
+		if (l_map->ino < r_map->ino) return 1;
+
+		if (l_map->ino_generation > r_map->ino_generation) return -1;
+		if (l_map->ino_generation < r_map->ino_generation) return 1;
+
+	} else if (left->cpumode != PERF_RECORD_MISC_KERNEL) {
+		/* userspace anonymous */
+		if (left->thread->pid_ > right->thread->pid_) return -1;
+		if (left->thread->pid_ < right->thread->pid_) return 1;
+	}
+
+	/* al_addr does all the right addr - start + offset calculations */
+	l = left->mem_info->daddr.al_addr;
+	r = right->mem_info->daddr.al_addr;
+
+	if (CL(l) > CL(r)) return -1;
+	if (CL(l) < CL(r)) return 1;
+		
+	/* sanity check the maps; only mmaped areas should have different maps */
+	if ((left->mem_info->daddr.map != right->mem_info->daddr.map) &&
+	     !right->mem_info->daddr.map->maj && !right->mem_info->daddr.map->min)
+		pr_debug("mem_cacheline_cmp: Similar entries have different maps\n");
+
+	return 0;
+}
+
+static int hist_entry__cacheline_snprintf(struct hist_entry *he, char *bf,
+					    size_t size, unsigned int width)
+{
+	uint64_t addr = 0;
+	struct map *map = NULL;
+	struct symbol *sym = NULL;
+	char level = he->level;
+
+	if (he->mem_info) {
+		addr = CL(he->mem_info->daddr.al_addr);
+		map = he->mem_info->daddr.map;
+		sym = he->mem_info->daddr.sym;
+
+		/* print [s] for data mmaps */
+		if ((he->cpumode != PERF_RECORD_MISC_KERNEL) &&
+		     map && (map->type == MAP__VARIABLE) &&
+		    (map->maj || map->min || map->ino ||
+		     map-> ino_generation))
+			level = 's';
+	}
+
+	return _hist_entry__sym_snprintf(map, sym, addr, level, bf, size,
+					 width);
+}
 struct sort_entry sort_global_weight = {
 	.se_header	= "Weight",
 	.se_cmp		= sort__global_weight_cmp,
@@ -858,6 +948,13 @@ struct sort_entry sort_mem_snoop = {
 	.se_width_idx	= HISTC_MEM_SNOOP,
 };
 
+struct sort_entry sort_mem_cacheline = {
+	.se_header	= "Cacheline",
+	.se_cmp		= sort__cacheline_cmp,
+	.se_snprintf	= hist_entry__cacheline_snprintf,
+	.se_width_idx	= HISTC_MEM_CACHELINE,
+};
+
 static int64_t
 sort__abort_cmp(struct hist_entry *left, struct hist_entry *right)
 {
@@ -1000,6 +1097,11 @@ static struct sort_dimension common_sort_dimensions[] = {
 	DIM(SORT_TRANSACTION, "transaction", sort_transaction),
 };
 
+static struct sort_dimension common_group_sort_dimensions[] = {
+	DIM(0, "pid", sort_thread),
+	DIM(1, "cpu", sort_cpu),
+};
+
 #undef DIM
 
 #define DIM(d, n, func) [d - __SORT_BRANCH_STACK] = { .name = n, .entry = &(func) }
@@ -1027,6 +1129,12 @@ static struct sort_dimension memory_sort_dimensions[] = {
 	DIM(SORT_MEM_SNOOP, "snoop", sort_mem_snoop),
 };
 
+static struct sort_dimension memory_group_sort_dimensions[] = {
+	DIM(0 + __SORT_MEMORY_MODE, "cacheline", sort_mem_cacheline),
+	DIM(1 + __SORT_MEMORY_MODE, "mem", sort_mem_lvl),
+	DIM(2 + __SORT_MEMORY_MODE, "snoop", sort_mem_snoop),
+};
+
 #undef DIM
 
 static void __sort_dimension__add(struct sort_dimension *sd, enum sort_type idx)
@@ -1109,12 +1217,81 @@ int sort_dimension__add(const char *tok)
 	return -ESRCH;
 }
 
+static void __sort_dimension__add_group(struct sort_dimension *sd, enum sort_type idx)
+{
+	if (sd->taken)
+		return;
+
+	if (sd->entry->se_collapse)
+		sort__need_collapse = 1;
+
+	if (list_empty(&hist_group__sort_list))
+		sort__first_dimension = idx;
+
+	list_add_tail(&sd->entry->list, &hist_group__sort_list);
+	sd->taken = 1;
+}
+
+int sort_dimension__add_group(const char *tok)
+{
+	unsigned int i;
+
+	for (i = 0; i < ARRAY_SIZE(common_group_sort_dimensions); i++) {
+		struct sort_dimension *sd = &common_group_sort_dimensions[i];
+
+		if (strncasecmp(tok, sd->name, strlen(tok)))
+			continue;
+
+		sort__has_group = 1;
+
+		__sort_dimension__add_group(sd, i);
+		return 0;
+	}
+
+	for (i = 0; i < ARRAY_SIZE(memory_sort_dimensions); i++) {
+		struct sort_dimension *sd = &memory_group_sort_dimensions[i];
+
+		if (strncasecmp(tok, sd->name, strlen(tok)))
+			continue;
+
+		if (sort__mode != SORT_MODE__MEMORY)
+			return -EINVAL;
+
+		sort__has_group = 1;
+
+		__sort_dimension__add_group(sd, i + __SORT_MEMORY_MODE);
+		return 0;
+	}
+
+	return -ESRCH;
+}
+
 int setup_sorting(void)
 {
-	char *tmp, *tok, *str = strdup(sort_order);
+	char *tmp, *tok, *str = strdup(group_sort_order);
 	int ret = 0;
 
 	if (str == NULL) {
+		error("Not enough memory to setup group sort keys");
+		return -ENOMEM;
+	}
+
+	for (tok = strtok_r(str, ", ", &tmp);
+			tok; tok = strtok_r(NULL, ", ", &tmp)) {
+		ret = sort_dimension__add_group(tok);
+		if (ret == -EINVAL) {
+			error("Invalid --sort key: `%s'", tok);
+			break;
+		} else if (ret == -ESRCH) {
+			error("Unknown --sort key: `%s'", tok);
+			break;
+		}
+	}
+
+	free(str);
+	str = strdup(sort_order);
+
+	if (str == NULL) {
 		error("Not enough memory to setup sort keys");
 		return -ENOMEM;
 	}
diff --git a/tools/perf/util/sort.h b/tools/perf/util/sort.h
index ff24050..ad5001f 100644
--- a/tools/perf/util/sort.h
+++ b/tools/perf/util/sort.h
@@ -26,9 +26,11 @@
 
 extern regex_t parent_regex;
 extern const char *sort_order;
+extern const char *group_sort_order;
 extern const char default_parent_pattern[];
 extern const char *parent_pattern;
 extern const char default_sort_order[];
+extern const char default_group_sort_order[];
 extern regex_t ignore_callees_regex;
 extern int have_ignore_callees;
 extern int sort__need_collapse;
@@ -91,6 +93,7 @@ struct hist_entry {
 	u64			ip;
 	u64			transaction;
 	s32			cpu;
+	u8			cpumode;
 
 	struct hist_entry_diff	diff;
 
@@ -322,6 +325,7 @@ extern struct list_head hist_group__sort_list;
 
 int setup_sorting(void);
 extern int sort_dimension__add(const char *);
+extern int sort_dimension__add_group(const char *);
 void sort__setup_elide(FILE *fp);
 
 int report_parse_ignore_callees_opt(const struct option *opt, const char *arg, int unset);
-- 
1.7.11.7

Re: [RFC 5/5] perf: Enable multiple hist_entry_group output

[Jiri Olsa]

On Thu, Apr 10, 2014 at 04:11:01PM -0400, Don Zickus wrote:
> Enable multiple hist_entry_group groups in the output based on a sort
> method.
> 
> Currently only 'perf report' is hooked in with '--group-sort='.  The choices
> are cpu, pid, and cacheline.  Only --stdio works right now.  I haven't figured
> out how the other outputs work.
> 
> Sample output from 'perf mem record -a grep -r foo /* > /dev/null'
> 
> (normal) perf mem report --percent-limit=1.0 --stdio
> 
>  Overhead       Samples
>   Local Weight             Memory access                                      Symbol
>  ........  ............  ............  ........................  ........................
> 
>      4.13%             1  1759          Uncached hit              [k] ahci_scr_read
>      1.16%             1  492           L1 hit                    [k] _raw_read_lock
> 
> (cpu groups) perf mem report --group-sort=cpu --percent-limit=1.0 --stdio
> 
>  Overhead       Samples  CPU
>   Local Weight             Memory access                                      Symbol
>  ........  ............  ............  ........................  ........................
> 
>     28.80%          1239   25
> 	     3.07%               377           L1 hit                    [k] complete_walk
> 	     2.76%               339           LFB hit                   [k] update_cfs_shares
> 	     2.66%               326           LFB hit                   [k] copy_user_enhanced_f
> 	     2.11%               259           Local RAM hit             [k] copy_user_enhanced_f
> 	     1.84%               226           LFB hit                   [k] copy_user_enhanced_f
> 	     1.74%               213           LFB hit                   [k] copy_user_enhanced_f
> 	     1.53%               187           LFB hit                   [k] copy_user_enhanced_f
> 	     1.04%               128           LFB hit                   [k] copy_user_enhanced_f
> 	     1.01%               124           LFB hit                   [k] copy_user_enhanced_f
>     27.44%           990    7
> 	    15.06%               1759          Uncached hit              [k] ahci_scr_read
> 	     4.21%               492           L1 hit                    [k] _raw_read_lock
> 	     1.04%               122           LFB hit                   [k] find_busiest_group
> 	     1.02%            1  7             L1 hit                    [.] __gconv_transform_ut
>     20.34%          1010    0
> 	     4.04%            5  7             L1 hit                    [k] poll_idle
> 	     3.56%               308           Local RAM hit             [k] copy_user_enhanced_f
> 	     2.59%               224           L3 hit                    [k] copy_user_enhanced_f
> 	     2.12%               184           Local RAM hit             [k] copy_user_enhanced_f
> 	     1.54%            1  7             L1 hit                    [.] __gconv_transform_ut

nice, that looks very usefull

Correct me if I'm wrong, but your current design allows to define
just one group, right?

so, current code can do following CPU sorting:

   Overhead   CPU
   ........   ...
   90%        0
   10%        1


and with your changes we could do:

   Overhead   CPU  symbol
   ........   ...  ......
   90%        0
        50%        krava1
        20%        krava2
        30%        krava3

   10%        1
        50%        krava4
        50%        krava5
  

I wonder we could go more generic and allow more nested groups,
like eg allow group sort on cpu and pid (or more):

   Overhead   CPU  pid  symbol
   ........   ...  ...  ......
   90%        0
      50%          100
        50%             krava1
        20%             krava2
        30%             krava3
      50%          110
        50%             krava1
        20%             krava2
        30%             krava3

   10%        1
      100%         200
        50%             krava4
        50%             krava5


I glanced over the changes and I wonder we could do it
by chaining hists structs via 'struct hist_entry'

like adding 'struct hists' into 'struct hists_entry'
and making the sort_order local for each 'struct hists'

just first thoughts.. need to look at it closely ;-)

jirka

Re: [RFC 5/5] perf: Enable multiple hist_entry_group output

[Don Zickus]

On Fri, Apr 11, 2014 at 07:30:00PM +0200, Jiri Olsa wrote:
> On Thu, Apr 10, 2014 at 04:11:01PM -0400, Don Zickus wrote:
> > Enable multiple hist_entry_group groups in the output based on a sort
> > method.
> > 
> > Currently only 'perf report' is hooked in with '--group-sort='.  The choices
> > are cpu, pid, and cacheline.  Only --stdio works right now.  I haven't figured
> > out how the other outputs work.
> > 
> > Sample output from 'perf mem record -a grep -r foo /* > /dev/null'
> > 
> > (normal) perf mem report --percent-limit=1.0 --stdio
> > 
> >  Overhead       Samples
> >   Local Weight             Memory access                                      Symbol
> >  ........  ............  ............  ........................  ........................
> > 
> >      4.13%             1  1759          Uncached hit              [k] ahci_scr_read
> >      1.16%             1  492           L1 hit                    [k] _raw_read_lock
> > 
> > (cpu groups) perf mem report --group-sort=cpu --percent-limit=1.0 --stdio
> > 
> >  Overhead       Samples  CPU
> >   Local Weight             Memory access                                      Symbol
> >  ........  ............  ............  ........................  ........................
> > 
> >     28.80%          1239   25
> > 	     3.07%               377           L1 hit                    [k] complete_walk
> > 	     2.76%               339           LFB hit                   [k] update_cfs_shares
> > 	     2.66%               326           LFB hit                   [k] copy_user_enhanced_f
> > 	     2.11%               259           Local RAM hit             [k] copy_user_enhanced_f
> > 	     1.84%               226           LFB hit                   [k] copy_user_enhanced_f
> > 	     1.74%               213           LFB hit                   [k] copy_user_enhanced_f
> > 	     1.53%               187           LFB hit                   [k] copy_user_enhanced_f
> > 	     1.04%               128           LFB hit                   [k] copy_user_enhanced_f
> > 	     1.01%               124           LFB hit                   [k] copy_user_enhanced_f
> >     27.44%           990    7
> > 	    15.06%               1759          Uncached hit              [k] ahci_scr_read
> > 	     4.21%               492           L1 hit                    [k] _raw_read_lock
> > 	     1.04%               122           LFB hit                   [k] find_busiest_group
> > 	     1.02%            1  7             L1 hit                    [.] __gconv_transform_ut
> >     20.34%          1010    0
> > 	     4.04%            5  7             L1 hit                    [k] poll_idle
> > 	     3.56%               308           Local RAM hit             [k] copy_user_enhanced_f
> > 	     2.59%               224           L3 hit                    [k] copy_user_enhanced_f
> > 	     2.12%               184           Local RAM hit             [k] copy_user_enhanced_f
> > 	     1.54%            1  7             L1 hit                    [.] __gconv_transform_ut
> 
> nice, that looks very usefull

\o/  :-)

> 
> Correct me if I'm wrong, but your current design allows to define
> just one group, right?

No, you can do multiple groups, ie --group-sort=cpu,pid,cacheline
(exactly the same way --sort works, in fact it uses the same sorting
functions and routines [pid_cmp is the _same_ in sort and group-sort]).
However, that is different than what you are asking below.  In my current
design, the output mimics --sorts output, just add sorted columns for each
group added.

> 
> so, current code can do following CPU sorting:
> 
>    Overhead   CPU
>    ........   ...
>    90%        0
>    10%        1
> 
> 
> and with your changes we could do:
> 
>    Overhead   CPU  symbol
>    ........   ...  ......
>    90%        0
>         50%        krava1
>         20%        krava2
>         30%        krava3
> 
>    10%        1
>         50%        krava4
>         50%        krava5
>   
> 
> I wonder we could go more generic and allow more nested groups,
> like eg allow group sort on cpu and pid (or more):

I never thought about that because I went in a different direction (as
described above), but I like the nested idea.  Coding it up would be much
trickier I think.  I would need to wrap my brain around it.

> 
>    Overhead   CPU  pid  symbol
>    ........   ...  ...  ......
>    90%        0
>       50%          100
>         50%             krava1
>         20%             krava2
>         30%             krava3
>       50%          110
>         50%             krava1
>         20%             krava2
>         30%             krava3
> 
>    10%        1
>       100%         200
>         50%             krava4
>         50%             krava5
> 
> 
> I glanced over the changes and I wonder we could do it
> by chaining hists structs via 'struct hist_entry'
> 
> like adding 'struct hists' into 'struct hists_entry'
> and making the sort_order local for each 'struct hists'

Well 'struct hists' was in 'struct hists_entry' (until this patchset
removed it).  :-)

We might be able to chain 'struct hists' somehow, though I am not sure how
to tell when a traverse a 'struct hists' vs. using 'entries' because we
hit an endpoint.  And if we have to write new sorting routines.  Also I
was originally keeping 'struct hists' as the upper level gatekeeper of
high level data, like filter_str and locks, col_len, etc.

I am not opposed to chaining, just thinking 'struct hists' isn't the right
struct to do it with.  I could be wrong. :-)  Will have to think about it.
Gives me something to thinking about next week on a plane to SF. :-)

Thanks for looking.

Cheers,
Don

Re: [RFC 5/5] perf: Enable multiple hist_entry_group output

[Don Zickus]

On Fri, Apr 11, 2014 at 07:30:00PM +0200, Jiri Olsa wrote:
> On Thu, Apr 10, 2014 at 04:11:01PM -0400, Don Zickus wrote:
> > Enable multiple hist_entry_group groups in the output based on a sort
> > method.
> > 
> > Currently only 'perf report' is hooked in with '--group-sort='.  The choices
> > are cpu, pid, and cacheline.  Only --stdio works right now.  I haven't figured
> > out how the other outputs work.
> > 
> > Sample output from 'perf mem record -a grep -r foo /* > /dev/null'
> > 
> > (normal) perf mem report --percent-limit=1.0 --stdio
> > 
> >  Overhead       Samples
> >   Local Weight             Memory access                                      Symbol
> >  ........  ............  ............  ........................  ........................
> > 
> >      4.13%             1  1759          Uncached hit              [k] ahci_scr_read
> >      1.16%             1  492           L1 hit                    [k] _raw_read_lock
> > 
> > (cpu groups) perf mem report --group-sort=cpu --percent-limit=1.0 --stdio
> > 
> >  Overhead       Samples  CPU
> >   Local Weight             Memory access                                      Symbol
> >  ........  ............  ............  ........................  ........................
> > 
> >     28.80%          1239   25
> > 	     3.07%               377           L1 hit                    [k] complete_walk
> > 	     2.76%               339           LFB hit                   [k] update_cfs_shares
> > 	     2.66%               326           LFB hit                   [k] copy_user_enhanced_f
> > 	     2.11%               259           Local RAM hit             [k] copy_user_enhanced_f
> > 	     1.84%               226           LFB hit                   [k] copy_user_enhanced_f
> > 	     1.74%               213           LFB hit                   [k] copy_user_enhanced_f
> > 	     1.53%               187           LFB hit                   [k] copy_user_enhanced_f
> > 	     1.04%               128           LFB hit                   [k] copy_user_enhanced_f
> > 	     1.01%               124           LFB hit                   [k] copy_user_enhanced_f
> >     27.44%           990    7
> > 	    15.06%               1759          Uncached hit              [k] ahci_scr_read
> > 	     4.21%               492           L1 hit                    [k] _raw_read_lock
> > 	     1.04%               122           LFB hit                   [k] find_busiest_group
> > 	     1.02%            1  7             L1 hit                    [.] __gconv_transform_ut
> >     20.34%          1010    0
> > 	     4.04%            5  7             L1 hit                    [k] poll_idle
> > 	     3.56%               308           Local RAM hit             [k] copy_user_enhanced_f
> > 	     2.59%               224           L3 hit                    [k] copy_user_enhanced_f
> > 	     2.12%               184           Local RAM hit             [k] copy_user_enhanced_f
> > 	     1.54%            1  7             L1 hit                    [.] __gconv_transform_ut
> 
> nice, that looks very usefull
> 
> Correct me if I'm wrong, but your current design allows to define
> just one group, right?
> 
> so, current code can do following CPU sorting:
> 
>    Overhead   CPU
>    ........   ...
>    90%        0
>    10%        1
> 
> 
> and with your changes we could do:
> 
>    Overhead   CPU  symbol
>    ........   ...  ......
>    90%        0
>         50%        krava1
>         20%        krava2
>         30%        krava3
> 
>    10%        1
>         50%        krava4
>         50%        krava5
>   
> 
> I wonder we could go more generic and allow more nested groups,
> like eg allow group sort on cpu and pid (or more):
> 
>    Overhead   CPU  pid  symbol
>    ........   ...  ...  ......
>    90%        0
>       50%          100
>         50%             krava1
>         20%             krava2
>         30%             krava3
>       50%          110
>         50%             krava1
>         20%             krava2
>         30%             krava3
> 
>    10%        1
>       100%         200
>         50%             krava4
>         50%             krava5
> 
> 
> I glanced over the changes and I wonder we could do it
> by chaining hists structs via 'struct hist_entry'
> 
> like adding 'struct hists' into 'struct hists_entry'
> and making the sort_order local for each 'struct hists'

Unless you meant:

hists
 \- hist_entry
      \- hists
           \- hist_entry -> hist_entry -> hist_entry -> hist_entry
                              \- hists
                                   \- hist_entry -> hist_entry -> hist_entry

where each 'hists' represents a new group and a hist_entry->hists != NULL
is a group otherwise just a node?

Cheers,
Don

Re: [RFC 5/5] perf: Enable multiple hist_entry_group output

[Jiri Olsa]

On Fri, Apr 11, 2014 at 02:34:52PM -0400, Don Zickus wrote:
> On Fri, Apr 11, 2014 at 07:30:00PM +0200, Jiri Olsa wrote:

SNIP

> > and with your changes we could do:
> > 
> >    Overhead   CPU  symbol
> >    ........   ...  ......
> >    90%        0
> >         50%        krava1
> >         20%        krava2
> >         30%        krava3
> > 
> >    10%        1
> >         50%        krava4
> >         50%        krava5
> >   
> > 
> > I wonder we could go more generic and allow more nested groups,
> > like eg allow group sort on cpu and pid (or more):
> > 
> >    Overhead   CPU  pid  symbol
> >    ........   ...  ...  ......
> >    90%        0
> >       50%          100
> >         50%             krava1
> >         20%             krava2
> >         30%             krava3
> >       50%          110
> >         50%             krava1
> >         20%             krava2
> >         30%             krava3
> > 
> >    10%        1
> >       100%         200
> >         50%             krava4
> >         50%             krava5
> > 
> > 
> > I glanced over the changes and I wonder we could do it
> > by chaining hists structs via 'struct hist_entry'
> > 
> > like adding 'struct hists' into 'struct hists_entry'
> > and making the sort_order local for each 'struct hists'
> 
> Unless you meant:
> 
> hists
>  \- hist_entry
>       \- hists
>            \- hist_entry -> hist_entry -> hist_entry -> hist_entry
>                               \- hists
>                                    \- hist_entry -> hist_entry -> hist_entry
> 
> where each 'hists' represents a new group and a hist_entry->hists != NULL
> is a group otherwise just a node?

right, hist_entry is either node or leaf, I see it like this:

hists (A)
  \-hist_entry(A)->(hists B1)
                     \-hist_entry(B1)
                     \-hist_entry(B1)
                     \-hist_entry(B1)

  \-hist_entry(A)->(hists B2)
                     \-hist_entry(B2)

  \-hist_entry(A)->(hists B3)
                     \-hist_entry(B3)
                     \-hist_entry(B3)


hists (A)  - getting data groupped by CPU - hist_entry (A)
hists (BX) - getting data belonging to CPU group and groupped by symbol (hist_entry BX)

so hists(A) provides data for 1st column in Overhead,
and hists(BX) provides data for the 2nd one:

  Overhead   CPU  symbol
  ........   ...  ......
  90%        0
       50%        krava1
       20%        krava2
       30%        krava3

   5%        1
      100%        krava4

   5%        2
       50%        krava4
       50%        krava5


jirka

Re: [RFC 5/5] perf: Enable multiple hist_entry_group output

[Don Zickus]

On Mon, Apr 14, 2014 at 11:19:32AM +0200, Jiri Olsa wrote:
> On Fri, Apr 11, 2014 at 02:34:52PM -0400, Don Zickus wrote:
> > On Fri, Apr 11, 2014 at 07:30:00PM +0200, Jiri Olsa wrote:
> 
> SNIP
> 
> > > and with your changes we could do:
> > > 
> > >    Overhead   CPU  symbol
> > >    ........   ...  ......
> > >    90%        0
> > >         50%        krava1
> > >         20%        krava2
> > >         30%        krava3
> > > 
> > >    10%        1
> > >         50%        krava4
> > >         50%        krava5
> > >   
> > > 
> > > I wonder we could go more generic and allow more nested groups,
> > > like eg allow group sort on cpu and pid (or more):
> > > 
> > >    Overhead   CPU  pid  symbol
> > >    ........   ...  ...  ......
> > >    90%        0
> > >       50%          100
> > >         50%             krava1
> > >         20%             krava2
> > >         30%             krava3
> > >       50%          110
> > >         50%             krava1
> > >         20%             krava2
> > >         30%             krava3
> > > 
> > >    10%        1
> > >       100%         200
> > >         50%             krava4
> > >         50%             krava5
> > > 
> > > 
> > > I glanced over the changes and I wonder we could do it
> > > by chaining hists structs via 'struct hist_entry'
> > > 
> > > like adding 'struct hists' into 'struct hists_entry'
> > > and making the sort_order local for each 'struct hists'
> > 
> > Unless you meant:
> > 
> > hists
> >  \- hist_entry
> >       \- hists
> >            \- hist_entry -> hist_entry -> hist_entry -> hist_entry
> >                               \- hists
> >                                    \- hist_entry -> hist_entry -> hist_entry
> > 
> > where each 'hists' represents a new group and a hist_entry->hists != NULL
> > is a group otherwise just a node?
> 
> right, hist_entry is either node or leaf, I see it like this:
> 
> hists (A)
>   \-hist_entry(A)->(hists B1)
>                      \-hist_entry(B1)
>                      \-hist_entry(B1)
>                      \-hist_entry(B1)
> 
>   \-hist_entry(A)->(hists B2)
>                      \-hist_entry(B2)
> 
>   \-hist_entry(A)->(hists B3)
>                      \-hist_entry(B3)
>                      \-hist_entry(B3)
> 
> 
> hists (A)  - getting data groupped by CPU - hist_entry (A)
> hists (BX) - getting data belonging to CPU group and groupped by symbol (hist_entry BX)
> 
> so hists(A) provides data for 1st column in Overhead,
> and hists(BX) provides data for the 2nd one:
> 
>   Overhead   CPU  symbol
>   ........   ...  ......
>   90%        0
>        50%        krava1
>        20%        krava2
>        30%        krava3
> 
>    5%        1
>       100%        krava4
> 
>    5%        2
>        50%        krava4
>        50%        krava5

Ok.  That at least tries to re-use the structs hist and hist_entry which
is what I struggled with when creating hist_entry_group.  Walking the
entries list will be an interesting challenge and sorting it.  I'll poke
it at it some more and see how things fall out.

Are you ok with the macros from patch 2?  At least the idea, we can change
the names.  I think I would like to continue with the macros to make it
easier to handle these changes, otherwise the code blows up and becomes
difficult to read.

Though I still am not sure how to handle 'pairs' correctly.

Cheers,
Don

Re: [RFC 0/5] perf: Create hist_entry groups

[Namhyung Kim]

Hi Don,

On Thu, 10 Apr 2014 16:10:56 -0400, Don Zickus wrote:
> This patchset creates a new layer of hist entry objects called
> hist_entry_groups.  The purpose is to help organize the hist_entries
> into groups before sorting them.  As a result you can gain a
> new perspective on the data by organizing the groups into cpu, pid
> or cacheline.  See patch 5 for sample output.
>
> The main driver for this patchset is to find a way to sort and display
> cacheline data in a way that is useful.  My previous attempts seemed
> hackish until I realized cacheline sorting is really just a collection
> of hist_entries.  Anyway that was my focus for doing this.
>
> The overall idea looks like:
>
> evlist
>   evsel
>     hists
>         hist_entry_group  <<< new object
>           hist_entry
>
>
> Implementing this was not pretty.  I tried to seperate the patches the
> best I could.  But in order for each patch to compile, patch 4 turned into
> a 1400 line diff that is mostly noise.
>
> Also, this patchset breaks most tools (mainly because I don't understand
> all the interactions), hence the RFC.  I mostly tested with 'perf report
>  --stdio' and 'perf mem report --stdio'.
>
> Please let me know if this is an interesting idea to go forward with or not.

I'd like to show you my previous two patchsets.

The first one is for adding --field option and changing the sort
behavior little different [1].  I'm about to send a new version to the
list soon.

I think what you want to do is sorting output by an order of sort keys
not just by the overhead.  So with the patchset applied, you can do it
like:

  $ perf report --field overhead,pid,dso,sym --sort pid

  # Overhead         Command:  Pid      Shared Object                             
  # ........  ....................  .................  ...........................
  #
      32.93%         swapper:    0  [kernel.kallsyms]  [k] intel_idle             
       6.79%         swapper:    0  [kernel.kallsyms]  [k] enqueue_entity         
       1.42%         swapper:    0  [kernel.kallsyms]  [k] update_sd_lb_stats     
       1.30%         swapper:    0  [kernel.kallsyms]  [k] timekeeping_max_deferme
       1.18%         swapper:    0  [kernel.kallsyms]  [k] update_cfs_shares      
       1.07%         swapper:    0  [kernel.kallsyms]  [k] __irq_work_run         
       0.96%         swapper:    0  [kernel.kallsyms]  [k] rcu_check_callbacks    
       0.64%         swapper:    0  [kernel.kallsyms]  [k] irqtime_account_process
       0.50%         swapper:    0  [kernel.kallsyms]  [k] int_sqrt               
       0.47%         swapper:    0  [kernel.kallsyms]  [k] __tick_nohz_idle_enter 
       0.47%         swapper:    0  [kernel.kallsyms]  [k] menu_select            
       0.35%         swapper:    0  [kernel.kallsyms]  [k] run_timer_softirq      
       0.16%         swapper:    0  [kernel.kallsyms]  [k] __perf_event_enable    
       0.12%         swapper:    0  [kernel.kallsyms]  [k] rcu_eqs_exit_common.isr
       0.50%      watchdog/6:   37  [kernel.kallsyms]  [k] update_sd_lb_stats     
       3.45%            Xorg: 1335  [kernel.kallsyms]  [k] schedule               
       6.55%  gnome-terminal: 1903  libc-2.17.so       [.] __strcmp_sse42         
       1.59%         firefox: 2137  [kernel.kallsyms]  [k] cpuacct_charge         
       0.50%           emacs: 2473  emacs-24.1         [.] 0x000000000012241a     
       0.38%           emacs: 2473  emacs-24.1         [.] 0x00000000000bfbf7     
       0.31%           emacs: 2473  emacs-24.1         [.] 0x00000000001780dd     
       0.29%           emacs: 2473  emacs-24.1         [.] 0x000000000002eb48     
       4.40%     kworker/7:1:11028  [kernel.kallsyms]  [k] generic_exec_single    
       1.30%     kworker/0:0:25667  [kernel.kallsyms]  [k] generic_exec_single    
       5.93%     kworker/5:1:26447  [kernel.kallsyms]  [k] generic_exec_single    
       2.06%     kworker/1:2:26653  [kernel.kallsyms]  [k] generic_exec_single    

As you can see the output is now sorted by pid value (and then overhead,
dso, sym if previous key resulted in a same value), so swapper (pid 0)
comes first and then watchdog/6, Xorg, and so on..

But it's not guarantee that the hottest pid comes always first on the
output, it just sorted it by pid and it gets the result simply because
the system was idle mostly.  I think you can handle it in your c2c tool
properly though.

Another one I'd like to introduce is somewhat similar to your work.
It's called hierarchy view and groups each entries according to sort
keys [2].  But it only supported --gtk output at that time (in order not
to make the hands dirty unnecessarily ;-) and (thus?) didn't get much
review.  But I think the idea is same and requires less change by just
adding few fields (rb_root) to hist_entry instead of new data structure.

Thanks,
Namhyung


[1] https://lkml.org/lkml/2014/3/19/689
[2] https://lkml.org/lkml/2013/5/21/24

Re: [RFC 0/5] perf: Create hist_entry groups

[Jiri Olsa]

On Tue, Apr 15, 2014 at 12:01:50PM +0900, Namhyung Kim wrote:
> Hi Don,
> 

SBIP

> 
> Another one I'd like to introduce is somewhat similar to your work.
> It's called hierarchy view and groups each entries according to sort
> keys [2].  But it only supported --gtk output at that time (in order not
> to make the hands dirty unnecessarily ;-) and (thus?) didn't get much
> review.  But I think the idea is same and requires less change by just
> adding few fields (rb_root) to hist_entry instead of new data structure.

hi,
I dont recall seeing that [2], but it's one year back ;-) it looks like
what Don is talking about, do you have it in branch?

thanks,
jirka

Re: [RFC 0/5] perf: Create hist_entry groups

[Namhyung Kim]

Hi Jiri,

On Tue, Apr 15, 2014 at 6:40 PM, Jiri Olsa <jolsa@redhat.com> wrote:
> On Tue, Apr 15, 2014 at 12:01:50PM +0900, Namhyung Kim wrote:
>> Another one I'd like to introduce is somewhat similar to your work.
>> It's called hierarchy view and groups each entries according to sort
>> keys [2].  But it only supported --gtk output at that time (in order not
>> to make the hands dirty unnecessarily ;-) and (thus?) didn't get much
>> review.  But I think the idea is same and requires less change by just
>> adding few fields (rb_root) to hist_entry instead of new data structure.
>
> hi,
> I dont recall seeing that [2], but it's one year back ;-) it looks like
> what Don is talking about, do you have it in branch?

Yep, it's perf/hierarchy-v1.

Thanks,
Namhyung

Re: [RFC 0/5] perf: Create hist_entry groups

[Don Zickus]

On Tue, Apr 15, 2014 at 12:01:50PM +0900, Namhyung Kim wrote:
> Hi Don,
> 
> On Thu, 10 Apr 2014 16:10:56 -0400, Don Zickus wrote:
> > This patchset creates a new layer of hist entry objects called
> > hist_entry_groups.  The purpose is to help organize the hist_entries
> > into groups before sorting them.  As a result you can gain a
> > new perspective on the data by organizing the groups into cpu, pid
> > or cacheline.  See patch 5 for sample output.
> >
> > The main driver for this patchset is to find a way to sort and display
> > cacheline data in a way that is useful.  My previous attempts seemed
> > hackish until I realized cacheline sorting is really just a collection
> > of hist_entries.  Anyway that was my focus for doing this.
> >
> > The overall idea looks like:
> >
> > evlist
> >   evsel
> >     hists
> >         hist_entry_group  <<< new object
> >           hist_entry
> >
> >
> > Implementing this was not pretty.  I tried to seperate the patches the
> > best I could.  But in order for each patch to compile, patch 4 turned into
> > a 1400 line diff that is mostly noise.
> >
> > Also, this patchset breaks most tools (mainly because I don't understand
> > all the interactions), hence the RFC.  I mostly tested with 'perf report
> >  --stdio' and 'perf mem report --stdio'.
> >
> > Please let me know if this is an interesting idea to go forward with or not.
> 
> I'd like to show you my previous two patchsets.
> 
> The first one is for adding --field option and changing the sort
> behavior little different [1].  I'm about to send a new version to the
> list soon.
> 
> I think what you want to do is sorting output by an order of sort keys
> not just by the overhead.  So with the patchset applied, you can do it
> like:
> 
>   $ perf report --field overhead,pid,dso,sym --sort pid
> 
>   # Overhead         Command:  Pid      Shared Object                             
>   # ........  ....................  .................  ...........................
>   #
>       32.93%         swapper:    0  [kernel.kallsyms]  [k] intel_idle             
>        6.79%         swapper:    0  [kernel.kallsyms]  [k] enqueue_entity         
>        1.42%         swapper:    0  [kernel.kallsyms]  [k] update_sd_lb_stats     
>        1.30%         swapper:    0  [kernel.kallsyms]  [k] timekeeping_max_deferme
>        1.18%         swapper:    0  [kernel.kallsyms]  [k] update_cfs_shares      
>        1.07%         swapper:    0  [kernel.kallsyms]  [k] __irq_work_run         
>        0.96%         swapper:    0  [kernel.kallsyms]  [k] rcu_check_callbacks    
>        0.64%         swapper:    0  [kernel.kallsyms]  [k] irqtime_account_process
>        0.50%         swapper:    0  [kernel.kallsyms]  [k] int_sqrt               
>        0.47%         swapper:    0  [kernel.kallsyms]  [k] __tick_nohz_idle_enter 
>        0.47%         swapper:    0  [kernel.kallsyms]  [k] menu_select            
>        0.35%         swapper:    0  [kernel.kallsyms]  [k] run_timer_softirq      
>        0.16%         swapper:    0  [kernel.kallsyms]  [k] __perf_event_enable    
>        0.12%         swapper:    0  [kernel.kallsyms]  [k] rcu_eqs_exit_common.isr
>        0.50%      watchdog/6:   37  [kernel.kallsyms]  [k] update_sd_lb_stats     
>        3.45%            Xorg: 1335  [kernel.kallsyms]  [k] schedule               
>        6.55%  gnome-terminal: 1903  libc-2.17.so       [.] __strcmp_sse42         
>        1.59%         firefox: 2137  [kernel.kallsyms]  [k] cpuacct_charge         
>        0.50%           emacs: 2473  emacs-24.1         [.] 0x000000000012241a     
>        0.38%           emacs: 2473  emacs-24.1         [.] 0x00000000000bfbf7     
>        0.31%           emacs: 2473  emacs-24.1         [.] 0x00000000001780dd     
>        0.29%           emacs: 2473  emacs-24.1         [.] 0x000000000002eb48     
>        4.40%     kworker/7:1:11028  [kernel.kallsyms]  [k] generic_exec_single    
>        1.30%     kworker/0:0:25667  [kernel.kallsyms]  [k] generic_exec_single    
>        5.93%     kworker/5:1:26447  [kernel.kallsyms]  [k] generic_exec_single    
>        2.06%     kworker/1:2:26653  [kernel.kallsyms]  [k] generic_exec_single    
> 
> As you can see the output is now sorted by pid value (and then overhead,
> dso, sym if previous key resulted in a same value), so swapper (pid 0)
> comes first and then watchdog/6, Xorg, and so on..

This is probably a workable solution for our c2c tool.  I can play with
this some more.

> 
> But it's not guarantee that the hottest pid comes always first on the
> output, it just sorted it by pid and it gets the result simply because
> the system was idle mostly.  I think you can handle it in your c2c tool
> properly though.
> 
> Another one I'd like to introduce is somewhat similar to your work.
> It's called hierarchy view and groups each entries according to sort
> keys [2].  But it only supported --gtk output at that time (in order not
> to make the hands dirty unnecessarily ;-) and (thus?) didn't get much
> review.  But I think the idea is same and requires less change by just
> adding few fields (rb_root) to hist_entry instead of new data structure.

Looks promising.

I keep thinking with all these hist_entry hacks to support flexibility, if
we should just do some bigger changes to the design.  I was thinking along
the lines of combining hist_entries and callchain stuff and maybe output
changes into a unified heirarchy somehow.  This way we could re-use alot
of code and throw away all the silly callchain special cases and just
treat it like a sort_entry.

I am not sure how that would work (or if really possible), but I was
playing with ideas in my head based on Jiri's suggestion, of something
like a tree layout where 'struct hists' would be sorta like a directory
and would dictate the data type in the 'files' of 'struct hist_entry'.

The idea was 'struct hists' would normally have a HIST data type and
contain the specific sort_entry(ies) for its heirarchy.  The 'struct
hist_entries' below it would all be the normal HIST data type.  For
callchain support, there would be a 'struct hist' under each 'hist_entry'
that would be of data type CALLCHAIN and its sort specific rules.

This way we could add display a callchain anywhere in the heirarchy
(instead of the normal last position).

If you then split the entries and entries_in out of struct hist and
instead create two 'struct hists', one for input and one output.  Then
perhaps we could create a data type GTK_OUT for a gtk specific output sort
of entries.  This might help re-use/reduce some of the ui/ code.

Anyway, it is probably way to much thrashing, just some ideas to help
promote better data visibilty.

I was enjoying the ideas of 'groups' and how it can help re-arrange the
data and allow us to look at bottlenecks differently.  While --field and
--hierarchy can achieve similar things, I am wondering if the output is
still simple enough to interpret (and the commandline simple enough for
users to utilize).

My 2cents.  Time to jump on a plane.

Cheers,
Don

Re: [RFC 0/5] perf: Create hist_entry groups

[Namhyung Kim]

Hi Don,

On Tue, 15 Apr 2014 12:08:41 -0400, Don Zickus wrote:
> On Tue, Apr 15, 2014 at 12:01:50PM +0900, Namhyung Kim wrote:
>> Hi Don,
>> 
>> On Thu, 10 Apr 2014 16:10:56 -0400, Don Zickus wrote:
>> > This patchset creates a new layer of hist entry objects called
>> > hist_entry_groups.  The purpose is to help organize the hist_entries
>> > into groups before sorting them.  As a result you can gain a
>> > new perspective on the data by organizing the groups into cpu, pid
>> > or cacheline.  See patch 5 for sample output.
>> >
>> > The main driver for this patchset is to find a way to sort and display
>> > cacheline data in a way that is useful.  My previous attempts seemed
>> > hackish until I realized cacheline sorting is really just a collection
>> > of hist_entries.  Anyway that was my focus for doing this.
>> >
>> > The overall idea looks like:
>> >
>> > evlist
>> >   evsel
>> >     hists
>> >         hist_entry_group  <<< new object
>> >           hist_entry
>> >
>> >
>> > Implementing this was not pretty.  I tried to seperate the patches the
>> > best I could.  But in order for each patch to compile, patch 4 turned into
>> > a 1400 line diff that is mostly noise.
>> >
>> > Also, this patchset breaks most tools (mainly because I don't understand
>> > all the interactions), hence the RFC.  I mostly tested with 'perf report
>> >  --stdio' and 'perf mem report --stdio'.
>> >
>> > Please let me know if this is an interesting idea to go forward with or not.
>> 
>> I'd like to show you my previous two patchsets.
>> 
>> The first one is for adding --field option and changing the sort
>> behavior little different [1].  I'm about to send a new version to the
>> list soon.
>> 
>> I think what you want to do is sorting output by an order of sort keys
>> not just by the overhead.  So with the patchset applied, you can do it
>> like:
>> 
>>   $ perf report --field overhead,pid,dso,sym --sort pid
>> 
>>   # Overhead         Command:  Pid      Shared Object                             
>>   # ........  ....................  .................  ...........................
>>   #
>>       32.93%         swapper:    0  [kernel.kallsyms]  [k] intel_idle             
>>        6.79%         swapper:    0  [kernel.kallsyms]  [k] enqueue_entity         
>>        1.42%         swapper:    0  [kernel.kallsyms]  [k] update_sd_lb_stats     
>>        1.30%         swapper:    0  [kernel.kallsyms]  [k] timekeeping_max_deferme
>>        1.18%         swapper:    0  [kernel.kallsyms]  [k] update_cfs_shares      
>>        1.07%         swapper:    0  [kernel.kallsyms]  [k] __irq_work_run         
>>        0.96%         swapper:    0  [kernel.kallsyms]  [k] rcu_check_callbacks    
>>        0.64%         swapper:    0  [kernel.kallsyms]  [k] irqtime_account_process
>>        0.50%         swapper:    0  [kernel.kallsyms]  [k] int_sqrt               
>>        0.47%         swapper:    0  [kernel.kallsyms]  [k] __tick_nohz_idle_enter 
>>        0.47%         swapper:    0  [kernel.kallsyms]  [k] menu_select            
>>        0.35%         swapper:    0  [kernel.kallsyms]  [k] run_timer_softirq      
>>        0.16%         swapper:    0  [kernel.kallsyms]  [k] __perf_event_enable    
>>        0.12%         swapper:    0  [kernel.kallsyms]  [k] rcu_eqs_exit_common.isr
>>        0.50%      watchdog/6:   37  [kernel.kallsyms]  [k] update_sd_lb_stats     
>>        3.45%            Xorg: 1335  [kernel.kallsyms]  [k] schedule               
>>        6.55%  gnome-terminal: 1903  libc-2.17.so       [.] __strcmp_sse42         
>>        1.59%         firefox: 2137  [kernel.kallsyms]  [k] cpuacct_charge         
>>        0.50%           emacs: 2473  emacs-24.1         [.] 0x000000000012241a     
>>        0.38%           emacs: 2473  emacs-24.1         [.] 0x00000000000bfbf7     
>>        0.31%           emacs: 2473  emacs-24.1         [.] 0x00000000001780dd     
>>        0.29%           emacs: 2473  emacs-24.1         [.] 0x000000000002eb48     
>>        4.40%     kworker/7:1:11028  [kernel.kallsyms]  [k] generic_exec_single    
>>        1.30%     kworker/0:0:25667  [kernel.kallsyms]  [k] generic_exec_single    
>>        5.93%     kworker/5:1:26447  [kernel.kallsyms]  [k] generic_exec_single    
>>        2.06%     kworker/1:2:26653  [kernel.kallsyms]  [k] generic_exec_single    
>> 
>> As you can see the output is now sorted by pid value (and then overhead,
>> dso, sym if previous key resulted in a same value), so swapper (pid 0)
>> comes first and then watchdog/6, Xorg, and so on..
>
> This is probably a workable solution for our c2c tool.  I can play with
> this some more.

Cool. :)

>
>> 
>> But it's not guarantee that the hottest pid comes always first on the
>> output, it just sorted it by pid and it gets the result simply because
>> the system was idle mostly.  I think you can handle it in your c2c tool
>> properly though.
>> 
>> Another one I'd like to introduce is somewhat similar to your work.
>> It's called hierarchy view and groups each entries according to sort
>> keys [2].  But it only supported --gtk output at that time (in order not
>> to make the hands dirty unnecessarily ;-) and (thus?) didn't get much
>> review.  But I think the idea is same and requires less change by just
>> adding few fields (rb_root) to hist_entry instead of new data structure.
>
> Looks promising.
>
> I keep thinking with all these hist_entry hacks to support flexibility, if
> we should just do some bigger changes to the design.  I was thinking along
> the lines of combining hist_entries and callchain stuff and maybe output
> changes into a unified heirarchy somehow.  This way we could re-use alot
> of code and throw away all the silly callchain special cases and just
> treat it like a sort_entry.
>
> I am not sure how that would work (or if really possible), but I was
> playing with ideas in my head based on Jiri's suggestion, of something
> like a tree layout where 'struct hists' would be sorta like a directory
> and would dictate the data type in the 'files' of 'struct hist_entry'.
>
> The idea was 'struct hists' would normally have a HIST data type and
> contain the specific sort_entry(ies) for its heirarchy.  The 'struct
> hist_entries' below it would all be the normal HIST data type.  For
> callchain support, there would be a 'struct hist' under each 'hist_entry'
> that would be of data type CALLCHAIN and its sort specific rules.
>
> This way we could add display a callchain anywhere in the heirarchy
> (instead of the normal last position).

I don't understand what you want to do - having callchains in the middle
is not intuitive to me.  Btw, you may want to check my cumulative (or
children) work which adds callchains into normal output.

https://lkml.org/lkml/2014/3/20/50

>
> If you then split the entries and entries_in out of struct hist and
> instead create two 'struct hists', one for input and one output.  Then
> perhaps we could create a data type GTK_OUT for a gtk specific output sort
> of entries.  This might help re-use/reduce some of the ui/ code.
>
> Anyway, it is probably way to much thrashing, just some ideas to help
> promote better data visibilty.
>
> I was enjoying the ideas of 'groups' and how it can help re-arrange the
> data and allow us to look at bottlenecks differently.  While --field and
> --hierarchy can achieve similar things, I am wondering if the output is
> still simple enough to interpret (and the commandline simple enough for
> users to utilize).
>
> My 2cents.  Time to jump on a plane.

Thanks for your feedback and suggestion.  Yes, making output more simple
and intuitive is very important.  I'll think about how to improve it
too.

Have a nice flight.

Thanks,
Namhyung

Re: [RFC 0/5] perf: Create hist_entry groups

[Don Zickus]

On Wed, Apr 16, 2014 at 05:29:09PM +0900, Namhyung Kim wrote:
> Hi Don,
> 
> On Tue, 15 Apr 2014 12:08:41 -0400, Don Zickus wrote:
> > On Tue, Apr 15, 2014 at 12:01:50PM +0900, Namhyung Kim wrote:
> >> Hi Don,
> >> 
> >> On Thu, 10 Apr 2014 16:10:56 -0400, Don Zickus wrote:
> >> > This patchset creates a new layer of hist entry objects called
> >> > hist_entry_groups.  The purpose is to help organize the hist_entries
> >> > into groups before sorting them.  As a result you can gain a
> >> > new perspective on the data by organizing the groups into cpu, pid
> >> > or cacheline.  See patch 5 for sample output.
> >> >
> >> > The main driver for this patchset is to find a way to sort and display
> >> > cacheline data in a way that is useful.  My previous attempts seemed
> >> > hackish until I realized cacheline sorting is really just a collection
> >> > of hist_entries.  Anyway that was my focus for doing this.
> >> >
> >> > The overall idea looks like:
> >> >
> >> > evlist
> >> >   evsel
> >> >     hists
> >> >         hist_entry_group  <<< new object
> >> >           hist_entry
> >> >
> >> >
> >> > Implementing this was not pretty.  I tried to seperate the patches the
> >> > best I could.  But in order for each patch to compile, patch 4 turned into
> >> > a 1400 line diff that is mostly noise.
> >> >
> >> > Also, this patchset breaks most tools (mainly because I don't understand
> >> > all the interactions), hence the RFC.  I mostly tested with 'perf report
> >> >  --stdio' and 'perf mem report --stdio'.
> >> >
> >> > Please let me know if this is an interesting idea to go forward with or not.
> >> 
> >> I'd like to show you my previous two patchsets.
> >> 
> >> The first one is for adding --field option and changing the sort
> >> behavior little different [1].  I'm about to send a new version to the
> >> list soon.
> >> 
> >> I think what you want to do is sorting output by an order of sort keys
> >> not just by the overhead.  So with the patchset applied, you can do it
> >> like:
> >> 
> >>   $ perf report --field overhead,pid,dso,sym --sort pid
> >> 
> >>   # Overhead         Command:  Pid      Shared Object                             
> >>   # ........  ....................  .................  ...........................
> >>   #
> >>       32.93%         swapper:    0  [kernel.kallsyms]  [k] intel_idle             
> >>        6.79%         swapper:    0  [kernel.kallsyms]  [k] enqueue_entity         
> >>        1.42%         swapper:    0  [kernel.kallsyms]  [k] update_sd_lb_stats     
> >>        1.30%         swapper:    0  [kernel.kallsyms]  [k] timekeeping_max_deferme
> >>        1.18%         swapper:    0  [kernel.kallsyms]  [k] update_cfs_shares      
> >>        1.07%         swapper:    0  [kernel.kallsyms]  [k] __irq_work_run         
> >>        0.96%         swapper:    0  [kernel.kallsyms]  [k] rcu_check_callbacks    
> >>        0.64%         swapper:    0  [kernel.kallsyms]  [k] irqtime_account_process
> >>        0.50%         swapper:    0  [kernel.kallsyms]  [k] int_sqrt               
> >>        0.47%         swapper:    0  [kernel.kallsyms]  [k] __tick_nohz_idle_enter 
> >>        0.47%         swapper:    0  [kernel.kallsyms]  [k] menu_select            
> >>        0.35%         swapper:    0  [kernel.kallsyms]  [k] run_timer_softirq      
> >>        0.16%         swapper:    0  [kernel.kallsyms]  [k] __perf_event_enable    
> >>        0.12%         swapper:    0  [kernel.kallsyms]  [k] rcu_eqs_exit_common.isr
> >>        0.50%      watchdog/6:   37  [kernel.kallsyms]  [k] update_sd_lb_stats     
> >>        3.45%            Xorg: 1335  [kernel.kallsyms]  [k] schedule               
> >>        6.55%  gnome-terminal: 1903  libc-2.17.so       [.] __strcmp_sse42         
> >>        1.59%         firefox: 2137  [kernel.kallsyms]  [k] cpuacct_charge         
> >>        0.50%           emacs: 2473  emacs-24.1         [.] 0x000000000012241a     
> >>        0.38%           emacs: 2473  emacs-24.1         [.] 0x00000000000bfbf7     
> >>        0.31%           emacs: 2473  emacs-24.1         [.] 0x00000000001780dd     
> >>        0.29%           emacs: 2473  emacs-24.1         [.] 0x000000000002eb48     
> >>        4.40%     kworker/7:1:11028  [kernel.kallsyms]  [k] generic_exec_single    
> >>        1.30%     kworker/0:0:25667  [kernel.kallsyms]  [k] generic_exec_single    
> >>        5.93%     kworker/5:1:26447  [kernel.kallsyms]  [k] generic_exec_single    
> >>        2.06%     kworker/1:2:26653  [kernel.kallsyms]  [k] generic_exec_single    
> >> 
> >> As you can see the output is now sorted by pid value (and then overhead,
> >> dso, sym if previous key resulted in a same value), so swapper (pid 0)
> >> comes first and then watchdog/6, Xorg, and so on..
> >
> > This is probably a workable solution for our c2c tool.  I can play with
> > this some more.
> 
> Cool. :)

Sorry for the long delay, I was out last week at our summit.  Not much for
stable internet access...  Will try to test these patches tomorrow.

> 
> >
> >> 
> >> But it's not guarantee that the hottest pid comes always first on the
> >> output, it just sorted it by pid and it gets the result simply because
> >> the system was idle mostly.  I think you can handle it in your c2c tool
> >> properly though.
> >> 
> >> Another one I'd like to introduce is somewhat similar to your work.
> >> It's called hierarchy view and groups each entries according to sort
> >> keys [2].  But it only supported --gtk output at that time (in order not
> >> to make the hands dirty unnecessarily ;-) and (thus?) didn't get much
> >> review.  But I think the idea is same and requires less change by just
> >> adding few fields (rb_root) to hist_entry instead of new data structure.
> >
> > Looks promising.
> >
> > I keep thinking with all these hist_entry hacks to support flexibility, if
> > we should just do some bigger changes to the design.  I was thinking along
> > the lines of combining hist_entries and callchain stuff and maybe output
> > changes into a unified heirarchy somehow.  This way we could re-use alot
> > of code and throw away all the silly callchain special cases and just
> > treat it like a sort_entry.
> >
> > I am not sure how that would work (or if really possible), but I was
> > playing with ideas in my head based on Jiri's suggestion, of something
> > like a tree layout where 'struct hists' would be sorta like a directory
> > and would dictate the data type in the 'files' of 'struct hist_entry'.
> >
> > The idea was 'struct hists' would normally have a HIST data type and
> > contain the specific sort_entry(ies) for its heirarchy.  The 'struct
> > hist_entries' below it would all be the normal HIST data type.  For
> > callchain support, there would be a 'struct hist' under each 'hist_entry'
> > that would be of data type CALLCHAIN and its sort specific rules.
> >
> > This way we could add display a callchain anywhere in the heirarchy
> > (instead of the normal last position).
> 
> I don't understand what you want to do - having callchains in the middle
> is not intuitive to me.  Btw, you may want to check my cumulative (or
> children) work which adds callchains into normal output.

Callchains in the middle was to mimic what I did with our c2c tool.  First
we sorted with such granularity, there was basically few in any duplicate
entries.  So displaying a callchain with our tool would look messy.
Instead we were displaying on 'cachelines'.  As a result I 'merged' each
entries callchain (after filtering out non-HITMs but kept stores) into a
cacheline callchain and displayed that.

So the idea was to sort on a cacheline, sort on callchains, then sort on
additional granularity like iaddr, data source, tids, etc.. so if the user
wanted to display them, they look sorted.  But it wasn't going to affect
the overall output.

It may not be the most thought out idea, it was something we had with our
tool and I was going for flexibility.

> 
> https://lkml.org/lkml/2014/3/20/50

I think I understand what you are doing here, but I am confused because I
thought the original call graph percentages were the weighted percents of
each path.  But now your patch is adding those explicitly.  So I don't
understand the difference with the original behaviour. :-(

Cheers,
Don