[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@xxxxxxxxxx>
---
 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

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/