[PATCH 1/7] perf hists: Basic support of hierarchical view

[Namhyung Kim]

From: Namhyung Kim <namhyung.kim@xxxxxxx>

In a hierarchical view, the events sorted and grouped on first key,
and then second key, and so on.  Now each hist entry has 3 of hroots
to save it's children entries.

Signed-off-by: Namhyung Kim <namhyung@xxxxxxxxxx>
---
 tools/perf/util/hist.c   | 325 +++++++++++++++++++++++++++++++++++++++++------
 tools/perf/util/sort.h   |   3 +
 tools/perf/util/symbol.h |   3 +-
 3 files changed, 291 insertions(+), 40 deletions(-)

diff --git a/tools/perf/util/hist.c b/tools/perf/util/hist.c
index 72b4eec820c3..80b981d52582 100644
--- a/tools/perf/util/hist.c
+++ b/tools/perf/util/hist.c
@@ -348,7 +348,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 hists *hists,
 				      struct hist_entry *entry,
 				      struct addr_location *al,
 				      u64 period,
@@ -417,6 +417,96 @@ out_unlock:
 	return he;
 }
 
+static struct hist_entry *__add_hist_entry_hierarchy(struct hists *hists,
+						     struct hist_entry *entry,
+						     struct addr_location *al,
+						     u64 period, u64 weight)
+{
+	struct rb_root *root;
+	struct rb_node **p;
+	struct rb_node *parent = NULL;
+	struct hist_entry *he = NULL;
+	struct sort_entry *se;
+	int cmp;
+
+	pthread_mutex_lock(&hists->lock);
+
+	root = hists->entries_in;
+	p = &root->rb_node;
+
+	list_for_each_entry(se, &hist_entry__sort_list, list) {
+		while (*p != NULL) {
+			parent = *p;
+			he = rb_entry(parent, struct hist_entry, 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 = se->se_cmp(he, entry);
+
+			if (!cmp) {
+				he_stat__add_period(&he->stat, period, weight);
+
+				/*
+				 * This mem info was allocated from machine__resolve_mem
+				 * and will not be used anymore.
+				 */
+				free(entry->mem_info);
+
+				/* If the map of an existing hist_entry has
+				 * become out-of-date due to an exec() or
+				 * similar, update it.  Otherwise we will
+				 * mis-adjust symbol addresses when computing
+				 * the history counter to increment.
+				 */
+				if (he->ms.map != entry->ms.map) {
+					he->ms.map = entry->ms.map;
+					if (he->ms.map)
+						he->ms.map->referenced = true;
+				}
+				goto next;
+			}
+
+			if (cmp < 0)
+				p = &(*p)->rb_left;
+			else
+				p = &(*p)->rb_right;
+		}
+
+		he = hist_entry__new(entry);
+		if (!he)
+			goto out_unlock;
+
+		rb_link_node(&he->rb_node_in, parent, p);
+		rb_insert_color(&he->rb_node_in, root);
+next:
+		hist_entry__add_cpumode_period(he, al->cpumode, period);
+
+		root = &he->rb_hroot_in;
+		p = &root->rb_node;
+		parent = NULL;
+	}
+
+out_unlock:
+	pthread_mutex_unlock(&hists->lock);
+	return he;
+}
+
+static struct hist_entry *add_hist_entry(struct hists *hists,
+				      struct hist_entry *entry,
+				      struct addr_location *al,
+				      u64 period,
+				      u64 weight)
+{
+	if (!symbol_conf.hierarchy)
+		return __add_hist_entry(hists, entry, al, period, weight);
+
+	return __add_hist_entry_hierarchy(hists, entry, al, period, weight);
+}
+
 struct hist_entry *__hists__add_mem_entry(struct hists *self,
 					  struct addr_location *al,
 					  struct symbol *sym_parent,
@@ -548,6 +638,8 @@ void hist_entry__free(struct hist_entry *he)
 	free(he);
 }
 
+static void hists__apply_filters(struct hists *hists, struct hist_entry *he);
+
 /*
  * collapse the histogram
  */
@@ -591,56 +683,148 @@ 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 void hists__collapse_resort_entries(struct hists *hists,
+					   struct rb_root *root_in,
+					   struct rb_root *root)
 {
-	struct rb_root *root;
-
-	pthread_mutex_lock(&hists->lock);
+	struct rb_node *next;
+	struct hist_entry *he;
 
-	root = hists->entries_in;
-	if (++hists->entries_in > &hists->entries_in_array[1])
-		hists->entries_in = &hists->entries_in_array[0];
+	next = rb_first(root_in);
 
-	pthread_mutex_unlock(&hists->lock);
+	while (next) {
+		he = rb_entry(next, struct hist_entry, rb_node_in);
+		next = rb_next(&he->rb_node_in);
 
-	return root;
+		rb_erase(&he->rb_node_in, root_in);
+		if (hists__collapse_insert_entry(hists, root, he)) {
+			/*
+			 * 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, he);
+		}
+	}
 }
 
-static void hists__apply_filters(struct hists *hists, struct hist_entry *he)
+static struct hist_entry *
+__collapse_insert_entry_hierarchy(struct rb_root *root, struct hist_entry *he,
+				  struct sort_entry *se)
 {
-	hists__filter_entry_by_dso(hists, he);
-	hists__filter_entry_by_thread(hists, he);
-	hists__filter_entry_by_symbol(hists, he);
+	struct rb_node **p = &root->rb_node;
+	struct rb_node *parent = NULL;
+	struct hist_entry *iter;
+	int64_t cmp;
+
+	while (*p != NULL) {
+		int64_t (*f)(struct hist_entry *, struct hist_entry *);
+		f = se->se_collapse ?: se->se_cmp;
+
+		parent = *p;
+		iter = rb_entry(parent, struct hist_entry, rb_node_in);
+
+		cmp = f(iter, he);
+
+		if (!cmp) {
+			he_stat__add_stat(&iter->stat, &he->stat);
+
+			if (symbol_conf.use_callchain) {
+				callchain_cursor_reset(&callchain_cursor);
+				callchain_merge(&callchain_cursor,
+						iter->callchain,
+						he->callchain);
+			}
+			return iter;
+		}
+
+		if (cmp < 0)
+			p = &(*p)->rb_left;
+		else
+			p = &(*p)->rb_right;
+	}
+
+	rb_link_node(&he->rb_node_in, parent, p);
+	rb_insert_color(&he->rb_node_in, root);
+	return he;
 }
 
-static void __hists__collapse_resort(struct hists *hists, bool threaded)
+static void
+hists__collapse_resort_entries_hierarchy(struct hists *hists,
+					 struct rb_root *root_in,
+					 struct rb_root *root,
+					 struct sort_entry *se)
 {
-	struct rb_root *root;
 	struct rb_node *next;
-	struct hist_entry *n;
+	struct hist_entry *he;
+	struct sort_entry *se_next;
 
-	if (!sort__need_collapse && !threaded)
+	next = rb_first(root_in);
+	if (next == NULL)
 		return;
 
-	root = hists__get_rotate_entries_in(hists);
-	next = rb_first(root);
+	BUG_ON(&se->list == &hist_entry__sort_list);
+	se_next = list_entry(se->list.next, struct sort_entry, list);
 
 	while (next) {
-		n = rb_entry(next, struct hist_entry, rb_node_in);
-		next = rb_next(&n->rb_node_in);
+		struct hist_entry *he_new;
+
+		he = rb_entry(next, struct hist_entry, rb_node_in);
+		next = rb_next(&he->rb_node_in);
 
-		rb_erase(&n->rb_node_in, root);
-		if (hists__collapse_insert_entry(hists, &hists->entries_collapsed, n)) {
+		rb_erase(&he->rb_node_in, root_in);
+		he_new = __collapse_insert_entry_hierarchy(root, he, se);
+		if (he == he_new) {
 			/*
 			 * 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);
+			hists__apply_filters(hists, he);
 		}
+
+		hists__collapse_resort_entries_hierarchy(hists, &he->rb_hroot_in,
+					&he_new->rb_hroot_collapsed, se_next);
+
+		if (he != he_new)
+			hist_entry__free(he);
 	}
 }
 
+static struct rb_root *hists__get_rotate_entries_in(struct hists *hists)
+{
+	struct rb_root *root;
+
+	pthread_mutex_lock(&hists->lock);
+
+	root = hists->entries_in;
+	if (++hists->entries_in > &hists->entries_in_array[1])
+		hists->entries_in = &hists->entries_in_array[0];
+
+	pthread_mutex_unlock(&hists->lock);
+
+	return root;
+}
+
+static void __hists__collapse_resort(struct hists *hists, bool threaded)
+{
+	struct rb_root *root_in;
+	struct rb_root *root;
+	struct sort_entry *se;
+
+	if (!sort__need_collapse && !threaded)
+		return;
+
+	root_in = hists__get_rotate_entries_in(hists);
+	root = &hists->entries_collapsed;
+
+	if (!symbol_conf.hierarchy)
+		return hists__collapse_resort_entries(hists, root_in, root);
+
+	se = list_first_entry(&hist_entry__sort_list, struct sort_entry, list);
+	hists__collapse_resort_entries_hierarchy(hists, root_in, root, se);
+}
+
 void hists__collapse_resort(struct hists *hists)
 {
 	return __hists__collapse_resort(hists, false);
@@ -711,11 +895,11 @@ out:
 	return ret;
 }
 
-static void __hists__insert_output_entry(struct rb_root *entries,
+static void __hists__insert_output_entry(struct rb_root *root,
 					 struct hist_entry *he,
 					 u64 min_callchain_hits)
 {
-	struct rb_node **p = &entries->rb_node;
+	struct rb_node **p = &root->rb_node;
 	struct rb_node *parent = NULL;
 	struct hist_entry *iter;
 
@@ -734,37 +918,92 @@ static void __hists__insert_output_entry(struct rb_root *entries,
 	}
 
 	rb_link_node(&he->rb_node, parent, p);
-	rb_insert_color(&he->rb_node, entries);
+	rb_insert_color(&he->rb_node, root);
+}
+
+static void hists__output_resort_entries(struct hists *hists,
+					 struct rb_root *root_in,
+					 struct rb_root *root,
+					 u64 min_callchain_hits)
+{
+	struct rb_node *next;
+	struct hist_entry *he;
+
+	next = rb_first(root_in);
+
+	while (next) {
+		he = rb_entry(next, struct hist_entry, rb_node_in);
+		next = rb_next(&he->rb_node_in);
+
+		__hists__insert_output_entry(root, he, min_callchain_hits);
+		hists__inc_nr_entries(hists, he);
+	}
+}
+
+static void hists__output_resort_entries_hierarchy(struct hists *hists,
+						   struct rb_root *root_in,
+						   struct rb_root *root,
+						   u64 min_callchain_hits,
+						   bool threaded)
+{
+	struct rb_node *next;
+	struct hist_entry *he;
+	struct rb_root *hroot_in;
+
+	next = rb_first(root_in);
+
+	if (next == NULL) {
+		he = list_entry(root, struct hist_entry, rb_hroot);
+		/* only count leaf nodes */
+		hists__inc_nr_entries(hists, he);
+		return;
+	}
+
+	while (next) {
+		he = rb_entry(next, struct hist_entry, rb_node_in);
+		next = rb_next(&he->rb_node_in);
+
+		__hists__insert_output_entry(root, he, min_callchain_hits);
+
+		if (sort__need_collapse || threaded)
+			hroot_in = &he->rb_hroot_collapsed;
+		else
+			hroot_in = &he->rb_hroot_in;
+
+		hists__output_resort_entries_hierarchy(hists, hroot_in,
+						       &he->rb_hroot,
+						       min_callchain_hits,
+						       threaded);
+	}
 }
 
 static void __hists__output_resort(struct hists *hists, bool threaded)
 {
+	struct rb_root *root_in;
 	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 || threaded)
-		root = &hists->entries_collapsed;
+		root_in = &hists->entries_collapsed;
 	else
-		root = hists->entries_in;
+		root_in = hists->entries_in;
 
-	next = rb_first(root);
 	hists->entries = RB_ROOT;
+	root = &hists->entries;
 
 	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);
-
-		__hists__insert_output_entry(&hists->entries, n, min_callchain_hits);
-		hists__inc_nr_entries(hists, n);
+	if (!symbol_conf.hierarchy) {
+		return hists__output_resort_entries(hists, root_in, root,
+						    min_callchain_hits);
 	}
+
+	hists__output_resort_entries_hierarchy(hists, root_in, root,
+					       min_callchain_hits, threaded);
 }
 
 void hists__output_resort(struct hists *hists)
@@ -889,6 +1128,14 @@ void hists__filter_by_symbol(struct hists *hists)
 	}
 }
 
+static void hists__apply_filters(struct hists *hists, struct hist_entry *he)
+{
+	hists__filter_entry_by_dso(hists, he);
+	hists__filter_entry_by_thread(hists, he);
+	hists__filter_entry_by_symbol(hists, he);
+}
+
+
 int hist_entry__inc_addr_samples(struct hist_entry *he, int evidx, u64 ip)
 {
 	return symbol__inc_addr_samples(he->ms.sym, he->ms.map, evidx, ip);
diff --git a/tools/perf/util/sort.h b/tools/perf/util/sort.h
index 51f1b5a854e7..6c2ba362ca05 100644
--- a/tools/perf/util/sort.h
+++ b/tools/perf/util/sort.h
@@ -75,6 +75,9 @@ struct hist_entry_diff {
 struct hist_entry {
 	struct rb_node		rb_node_in;
 	struct rb_node		rb_node;
+	struct rb_root		rb_hroot_in;
+	struct rb_root		rb_hroot_collapsed;
+	struct rb_root		rb_hroot;
 	union {
 		struct list_head node;
 		struct list_head head;
diff --git a/tools/perf/util/symbol.h b/tools/perf/util/symbol.h
index 5f720dc076da..ee0cfd8b785e 100644
--- a/tools/perf/util/symbol.h
+++ b/tools/perf/util/symbol.h
@@ -98,7 +98,8 @@ struct symbol_conf {
 			annotate_asm_raw,
 			annotate_src,
 			event_group,
-			demangle;
+			demangle,
+			hierarchy;
 	const char	*vmlinux_name,
 			*kallsyms_name,
 			*source_prefix,
-- 
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/