[PATCH 13/23] perf hists: Support filtering in hierarchy mode

[Namhyung Kim]

The hists__filter_hierarchy() function implements filtering in hierarchy
mode.  Now we have hist_entry__filter() so use it for entries in the
hierarchy.  It returns 3 kind of values.

A negative value means that it's not filtered by this type.  It marks
current entry as filtered tentatively so if a lower level entry removes
the filter it also removes the all parent so that we can find the entry
in the output.

Zero means it's filtered out by this type and positive value means it's
not filtered so it removes the filter.  In these cases, it moves to next
entry since lower level entry won't match by this type of filter
anymore.  Thus all children will be filtered or not together.

Acked-by: Pekka Enberg <penberg@xxxxxxxxxx>
Signed-off-by: Namhyung Kim <namhyung@xxxxxxxxxx>
---
 tools/perf/util/hist.c | 131 ++++++++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 123 insertions(+), 8 deletions(-)

diff --git a/tools/perf/util/hist.c b/tools/perf/util/hist.c
index def0120d57ab..a9ba90baac62 100644
--- a/tools/perf/util/hist.c
+++ b/tools/perf/util/hist.c
@@ -1507,6 +1507,27 @@ static void hists__remove_entry_filter(struct hists *hists, struct hist_entry *h
 				       enum hist_filter filter)
 {
 	h->filtered &= ~(1 << filter);
+
+	if (symbol_conf.report_hierarchy) {
+		struct hist_entry *parent = h->parent_he;
+
+		while (parent) {
+			he_stat__add_stat(&parent->stat, &h->stat);
+
+			parent->filtered &= ~(1 << filter);
+
+			if (parent->filtered)
+				goto next;
+
+			/* force fold unfiltered entry for simplicity */
+			parent->unfolded = false;
+			parent->row_offset = 0;
+			parent->nr_rows = 0;
+next:
+			parent = parent->parent_he;
+		}
+	}
+
 	if (h->filtered)
 		return;
 
@@ -1592,28 +1613,122 @@ static void hists__filter_by_type(struct hists *hists, int type, filter_fn_t fil
 	}
 }
 
+static void hists__filter_hierarchy(struct hists *hists, int type, const void *arg)
+{
+	struct rb_node *nd;
+	struct rb_root tmp = RB_ROOT;
+	bool saved_unfolded;
+
+	hists->stats.nr_non_filtered_samples = 0;
+
+	hists__reset_filter_stats(hists);
+	hists__reset_col_len(hists);
+
+	nd = rb_first(&hists->entries);
+	while (nd) {
+		struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
+		int ret;
+
+		ret = hist_entry__filter(h, type, arg);
+
+		/*
+		 * case 1. non-matching type
+		 * zero out the period, set filtered and move to child
+		 */
+		if (ret < 0) {
+			memset(&h->stat, 0, sizeof(h->stat));
+			h->filtered |= (1 << type);
+
+			/* force to go down in the hierarchy */
+			saved_unfolded = h->unfolded;
+			h->unfolded = true;
+
+			nd = rb_hierarchy_next(&h->rb_node);
+			h->unfolded = saved_unfolded;
+		}
+		/*
+		 * case 2. matched (filter out)
+		 * set filtered and move to next
+		 */
+		else if (ret == 1) {
+			h->filtered |= (1 << type);
+
+			/* force to go to sibling in the hierarchy */
+			saved_unfolded = h->unfolded;
+			h->unfolded = false;
+
+			nd = rb_hierarchy_next(&h->rb_node);
+			h->unfolded = saved_unfolded;
+		}
+		/*
+		 * case 3. ok (not filtered)
+		 * add period to hists and parents, erase filtered
+		 * and move to next
+		 */
+		else {
+			hists__remove_entry_filter(hists, h, type);
+
+			/* force to go to sibling in the hierarchy */
+			saved_unfolded = h->unfolded;
+			h->unfolded = false;
+
+			nd = rb_hierarchy_next(&h->rb_node);
+			h->unfolded = saved_unfolded;
+		}
+	}
+
+	/* resort output (top-level entries only) */
+	nd = rb_first(&hists->entries);
+	while (nd) {
+		struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
+
+		nd = rb_next(nd);
+		rb_erase(&h->rb_node, &hists->entries);
+
+		__hists__insert_output_entry(&tmp, h, 0, false);
+	}
+
+	hists->entries = tmp;
+}
+
 void hists__filter_by_thread(struct hists *hists)
 {
-	hists__filter_by_type(hists, HIST_FILTER__THREAD,
-			      hists__filter_entry_by_thread);
+	if (symbol_conf.report_hierarchy)
+		hists__filter_hierarchy(hists, HIST_FILTER__THREAD,
+					hists->thread_filter);
+	else
+		hists__filter_by_type(hists, HIST_FILTER__THREAD,
+				      hists__filter_entry_by_thread);
 }
 
 void hists__filter_by_dso(struct hists *hists)
 {
-	hists__filter_by_type(hists, HIST_FILTER__DSO,
-			      hists__filter_entry_by_dso);
+	if (symbol_conf.report_hierarchy)
+		hists__filter_hierarchy(hists, HIST_FILTER__DSO,
+					hists->dso_filter);
+	else
+		hists__filter_by_type(hists, HIST_FILTER__DSO,
+				      hists__filter_entry_by_dso);
 }
 
 void hists__filter_by_symbol(struct hists *hists)
 {
-	hists__filter_by_type(hists, HIST_FILTER__SYMBOL,
-			      hists__filter_entry_by_symbol);
+	if (symbol_conf.report_hierarchy)
+		hists__filter_hierarchy(hists, HIST_FILTER__SYMBOL,
+					hists->symbol_filter_str);
+	else
+		hists__filter_by_type(hists, HIST_FILTER__SYMBOL,
+				      hists__filter_entry_by_symbol);
 }
 
 void hists__filter_by_socket(struct hists *hists)
 {
-	hists__filter_by_type(hists, HIST_FILTER__SOCKET,
-			      hists__filter_entry_by_socket);
+	if (symbol_conf.report_hierarchy)
+		hists__filter_hierarchy(hists, HIST_FILTER__SOCKET,
+					&hists->socket_filter);
+	else
+		hists__filter_by_type(hists, HIST_FILTER__SOCKET,
+				      hists__filter_entry_by_socket);
 }
 
 void events_stats__inc(struct events_stats *stats, u32 type)
-- 
2.7.0