[PATCHSET 00/23] perf tools: Add support for hierachy view (v5)

[PATCHSET 00/23] perf tools: Add support for hierachy view (v5)

[Namhyung Kim]

Hello,

This patchset implements a new feature that collects hist entries in a
hierachical manner.  That means lower-level entries belong to an
upper-level entry.  The entry hierachy is built on the sort keys
given, so users can set it whatever they want.  It only shows
top-level entries first, and user can expand/collapse it dynamically.

 * Changes from v4)
  - rebased onto the current acme/perf/core
  - fix memory leak on callchian_merge error path  (Arnaldo)
  - fix a bug on perf-top regarding percent calculation
  - split hierarchy filtering code
 
 * Changes from v3)
  - rebased onto the percent limit patchset v2

 * Changes from v2)
  - check memory allocation failure in hists__hierarchy_insert_entry  (Jiri)
  - remove unused rb_hierarchy_first()  (Arnaldo)
  - support callchain percent limit  (Andi)
  - break TUI context menu cleanup  (Arnaldo)
  

This time I implemented it for every output browser including TUI.
A screenshot on TUI looks like below:

For normal output:

  $ perf report --tui
  Samples: 3K of event 'cycles:pp', Event count (approx.): 1695979674
    Overhead  Command        Shared Object         Symbol
  ------------------------------------------------------------------------
  -    7.57%  swapper        [kernel.vmlinux]      [k] intel_idle
       intel_idle
       cpuidle_enter_state
       cpuidle_enter
       call_cpuidle
     + cpu_startup_entry
  +    1.16   firefox        firefox               [.] 0x00000000000019433
  +    0.97%  firefox        libpthread-2.22.so    [.] pthread_mutex_lock
  ...


With hierarchy view,

  $ perf report --tui --hierarchy
  Samples: 3K of event 'cycles:pp', Event count (approx.): 1695979674
   Overhead        Command / Shared Object / Symbol
  -------------------------------------------------------------------
  +  76.30%        firefox
  -   9.95%        swapper
     -   9.51%        [kernel.vmlinux]
        -   7.57         [k] intel_idle
	     intel_idle
	     cpuidle_enter_state
	     cpuidle_enter
	     call_cpuidle
	   + cpu_startup_entry
	+   0.15%        [k] __schedule
	+   0.12%        [k] menu_select
	...
     +   0.34%        [sdhci]
     +   0.06%        [e1000e]
     ...
 +    5.65%        Xorg
 +    5.42%        Socket Thread
 ...

As you can see, overhead of an upper level entry is the sum of
overhead of lower level entries.  The entries are aligned by its order
of matching sort keys.

This is available from 'perf/hierarchy-v5' branch in my tree:

  git://git.kernel.org/pub/scm/linux/kernel/git/namhyung/linux-perf.git


Any comments are welcome, thanks!
Namhyung


Cc: Don Zickus <dzickus@redhat.com>
Cc: Pekka Enberg <penberg@kernel.org>
Cc: Moinuddin Quadri <moin18@gmail.com>


[1] https://lkml.org/lkml/2013/5/21/24


Namhyung Kim (23):
  perf hists browser: Fix percentage update on key press
  perf callchain: Check return value of add_child()
  perf callchain: Check return value of fill_node()
  perf callchain: Add enum match_result for match_chain()
  perf callchain: Check return value of split_add_child()
  perf callchain: Check return value of append_chain_children()
  perf hists: Return error from hists__collapse_resort()
  perf report: Check error during report__collapse_hists()
  perf hists: Basic support of hierarchical report view
  perf hists: Resort hist entries with hierarchy
  perf hists: Add helper functions for hierarchy mode
  perf hists: Introduce hist_entry__filter()
  perf hists: Support filtering in hierarchy mode
  perf ui/stdio: Implement hierarchy output mode
  perf ui/stdio: Align column header for hierarchy output
  perf hists browser: Count number of hierarchy entries
  perf hists browser: Support collapsing/expanding whole entries in
    hierarchy
  perf hists browser: Implement hierarchy output
  perf hists browser: Align column header in hierarchy mode
  perf ui/gtk: Implement hierarchy output mode
  perf report: Add --hierarchy option
  perf hists: Support decaying in hierarchy mode
  perf top: Add --hierarchy option

 tools/perf/Documentation/perf-report.txt |   3 +
 tools/perf/Documentation/perf-top.txt    |   3 +
 tools/perf/Documentation/tips.txt        |   1 +
 tools/perf/builtin-report.c              |  31 +-
 tools/perf/builtin-top.c                 |  15 +
 tools/perf/ui/browsers/hists.c           | 488 ++++++++++++++++++++++++++++---
 tools/perf/ui/gtk/hists.c                | 161 +++++++++-
 tools/perf/ui/hist.c                     |  14 +
 tools/perf/ui/stdio/hist.c               | 184 +++++++++++-
 tools/perf/util/callchain.c              | 102 +++++--
 tools/perf/util/hist.c                   | 463 ++++++++++++++++++++++++++---
 tools/perf/util/hist.h                   |  16 +-
 tools/perf/util/sort.c                   | 113 +++++++
 tools/perf/util/sort.h                   |  14 +-
 tools/perf/util/symbol.h                 |   3 +-
 15 files changed, 1493 insertions(+), 118 deletions(-)

-- 
2.7.0

[PATCH 01/23] perf hists browser: Fix percentage update on key press

[Namhyung Kim]

Currently 'perf top --tui' decrements percentage of all entries on any
key press.  This is because it adds total period as new samples are
added to hists.  As perf-top does it currently but added samples are not
passed to the display thread, the percentages are decresing
continuously.

So separate total period stat into a different variable so that it
cannot affect the output total period.  This new total period stats are
used only for calcualating callchain percent limit.

Signed-off-by: Namhyung Kim <namhyung@kernel.org>
---
 tools/perf/util/hist.c | 26 +++++++++++++++++++-------
 tools/perf/util/hist.h |  2 ++
 2 files changed, 21 insertions(+), 7 deletions(-)

diff --git a/tools/perf/util/hist.c b/tools/perf/util/hist.c
index 12f2d794dc28..f6bdb827e6fb 100644
--- a/tools/perf/util/hist.c
+++ b/tools/perf/util/hist.c
@@ -405,6 +405,16 @@ static u8 symbol__parent_filter(const struct symbol *parent)
 	return 0;
 }
 
+static void hist_entry__add_callchain_period(struct hist_entry *he, u64 period)
+{
+	if (!symbol_conf.use_callchain)
+		return;
+
+	he->hists->callchain_period += period;
+	if (!he->filtered)
+		he->hists->callchain_non_filtered_period += period;
+}
+
 static struct hist_entry *hists__findnew_entry(struct hists *hists,
 					       struct hist_entry *entry,
 					       struct addr_location *al,
@@ -434,9 +444,7 @@ static struct hist_entry *hists__findnew_entry(struct hists *hists,
 		if (!cmp) {
 			if (sample_self) {
 				he_stat__add_period(&he->stat, period, weight);
-				hists->stats.total_period += period;
-				if (!he->filtered)
-					hists->stats.total_non_filtered_period += period;
+				hist_entry__add_callchain_period(he, period);
 			}
 			if (symbol_conf.cumulate_callchain)
 				he_stat__add_period(he->stat_acc, period, weight);
@@ -471,9 +479,8 @@ static struct hist_entry *hists__findnew_entry(struct hists *hists,
 		return NULL;
 
 	if (sample_self)
-		hists__inc_stats(hists, he);
-	else
-		hists->nr_entries++;
+		hist_entry__add_callchain_period(he, period);
+	hists->nr_entries++;
 
 	rb_link_node(&he->rb_node_in, parent, p);
 	rb_insert_color(&he->rb_node_in, hists->entries_in);
@@ -1206,9 +1213,14 @@ static void output_resort(struct hists *hists, struct ui_progress *prog,
 	struct rb_root *root;
 	struct rb_node *next;
 	struct hist_entry *n;
+	u64 callchain_total;
 	u64 min_callchain_hits;
 
-	min_callchain_hits = hists__total_period(hists) * (callchain_param.min_percent / 100);
+	callchain_total = hists->callchain_period;
+	if (symbol_conf.filter_relative)
+		callchain_total = hists->callchain_non_filtered_period;
+
+	min_callchain_hits = callchain_total * (callchain_param.min_percent / 100);
 
 	if (sort__need_collapse)
 		root = &hists->entries_collapsed;
diff --git a/tools/perf/util/hist.h b/tools/perf/util/hist.h
index 1c7544a8fe1a..21c1bc4661e3 100644
--- a/tools/perf/util/hist.h
+++ b/tools/perf/util/hist.h
@@ -66,6 +66,8 @@ struct hists {
 	struct rb_root		entries_collapsed;
 	u64			nr_entries;
 	u64			nr_non_filtered_entries;
+	u64			callchain_period;
+	u64			callchain_non_filtered_period;
 	struct thread		*thread_filter;
 	const struct dso	*dso_filter;
 	const char		*uid_filter_str;
-- 
2.7.0

[PATCH 02/23] perf callchain: Check return value of add_child()

[Namhyung Kim]

The create_child() in add_child() can return NULL in case of memory
allocation failure.  So check the return value and bail out.  The proper
error handling will be added later.

Acked-by: Jiri Olsa <jolsa@kernel.org>
Cc: Frederic Weisbecker <fweisbec@gmail.com>
Signed-off-by: Namhyung Kim <namhyung@kernel.org>
---
 tools/perf/util/callchain.c | 8 ++++++++
 1 file changed, 8 insertions(+)

diff --git a/tools/perf/util/callchain.c b/tools/perf/util/callchain.c
index 53c43eb9489e..134d88b33fc1 100644
--- a/tools/perf/util/callchain.c
+++ b/tools/perf/util/callchain.c
@@ -453,6 +453,9 @@ add_child(struct callchain_node *parent,
 	struct callchain_node *new;
 
 	new = create_child(parent, false);
+	if (new == NULL)
+		return NULL;
+
 	fill_node(new, cursor);
 
 	new->children_hit = 0;
@@ -524,6 +527,8 @@ split_add_child(struct callchain_node *parent,
 
 		node = callchain_cursor_current(cursor);
 		new = add_child(parent, cursor, period);
+		if (new == NULL)
+			return;
 
 		/*
 		 * This is second child since we moved parent's children
@@ -585,6 +590,9 @@ append_chain_children(struct callchain_node *root,
 	}
 	/* nothing in children, add to the current node */
 	rnode = add_child(root, cursor, period);
+	if (rnode == NULL)
+		return;
+
 	rb_link_node(&rnode->rb_node_in, parent, p);
 	rb_insert_color(&rnode->rb_node_in, &root->rb_root_in);
 
-- 
2.7.0

[PATCH 03/23] perf callchain: Check return value of fill_node()

[Namhyung Kim]

Memory allocation in the fill_node() can fail so change its return type
to int and check it in add_child() too.

Acked-by: Jiri Olsa <jolsa@kernel.org>
Cc: Frederic Weisbecker <fweisbec@gmail.com>
Signed-off-by: Namhyung Kim <namhyung@kernel.org>
---
 tools/perf/util/callchain.c | 16 +++++++++++++---
 1 file changed, 13 insertions(+), 3 deletions(-)

diff --git a/tools/perf/util/callchain.c b/tools/perf/util/callchain.c
index 134d88b33fc1..a82ea6f6fc0f 100644
--- a/tools/perf/util/callchain.c
+++ b/tools/perf/util/callchain.c
@@ -416,7 +416,7 @@ create_child(struct callchain_node *parent, bool inherit_children)
 /*
  * Fill the node with callchain values
  */
-static void
+static int
 fill_node(struct callchain_node *node, struct callchain_cursor *cursor)
 {
 	struct callchain_cursor_node *cursor_node;
@@ -433,7 +433,7 @@ fill_node(struct callchain_node *node, struct callchain_cursor *cursor)
 		call = zalloc(sizeof(*call));
 		if (!call) {
 			perror("not enough memory for the code path tree");
-			return;
+			return -1;
 		}
 		call->ip = cursor_node->ip;
 		call->ms.sym = cursor_node->sym;
@@ -443,6 +443,7 @@ fill_node(struct callchain_node *node, struct callchain_cursor *cursor)
 		callchain_cursor_advance(cursor);
 		cursor_node = callchain_cursor_current(cursor);
 	}
+	return 0;
 }
 
 static struct callchain_node *
@@ -456,7 +457,16 @@ add_child(struct callchain_node *parent,
 	if (new == NULL)
 		return NULL;
 
-	fill_node(new, cursor);
+	if (fill_node(new, cursor) < 0) {
+		struct callchain_list *call, *tmp;
+
+		list_for_each_entry_safe(call, tmp, &new->val, list) {
+			list_del(&call->list);
+			free(call);
+		}
+		free(new);
+		return NULL;
+	}
 
 	new->children_hit = 0;
 	new->hit = period;
-- 
2.7.0

[PATCH 04/23] perf callchain: Add enum match_result for match_chain()

[Namhyung Kim]

The append_chain() might return either result of match_chain() or
other (error) code.  But match_chain() can return any value in s64 type
so it's hard to check the error case.  Add new enum match_result and
make match_chain() return non-negative values only so that we can check
the error cases.

Acked-by: Jiri Olsa <jolsa@kernel.org>
Cc: Frederic Weisbecker <fweisbec@gmail.com>
Signed-off-by: Namhyung Kim <namhyung@kernel.org>
---
 tools/perf/util/callchain.c | 52 +++++++++++++++++++++++++++++----------------
 1 file changed, 34 insertions(+), 18 deletions(-)

diff --git a/tools/perf/util/callchain.c b/tools/perf/util/callchain.c
index a82ea6f6fc0f..dab2c1f1e86b 100644
--- a/tools/perf/util/callchain.c
+++ b/tools/perf/util/callchain.c
@@ -475,16 +475,32 @@ add_child(struct callchain_node *parent,
 	return new;
 }
 
-static s64 match_chain(struct callchain_cursor_node *node,
-		      struct callchain_list *cnode)
+enum match_result {
+	MATCH_ERROR  = -1,
+	MATCH_EQ,
+	MATCH_LT,
+	MATCH_GT,
+};
+
+static enum match_result match_chain(struct callchain_cursor_node *node,
+				     struct callchain_list *cnode)
 {
 	struct symbol *sym = node->sym;
+	u64 left, right;
 
 	if (cnode->ms.sym && sym &&
-	    callchain_param.key == CCKEY_FUNCTION)
-		return cnode->ms.sym->start - sym->start;
-	else
-		return cnode->ip - node->ip;
+	    callchain_param.key == CCKEY_FUNCTION) {
+		left = cnode->ms.sym->start;
+		right = sym->start;
+	} else {
+		left = cnode->ip;
+		right = node->ip;
+	}
+
+	if (left == right)
+		return MATCH_EQ;
+
+	return left > right ? MATCH_GT : MATCH_LT;
 }
 
 /*
@@ -549,7 +565,7 @@ split_add_child(struct callchain_node *parent,
 		cnode = list_first_entry(&first->val, struct callchain_list,
 					 list);
 
-		if (match_chain(node, cnode) < 0)
+		if (match_chain(node, cnode) == MATCH_LT)
 			pp = &p->rb_left;
 		else
 			pp = &p->rb_right;
@@ -562,7 +578,7 @@ split_add_child(struct callchain_node *parent,
 	}
 }
 
-static int
+static enum match_result
 append_chain(struct callchain_node *root,
 	     struct callchain_cursor *cursor,
 	     u64 period);
@@ -583,17 +599,17 @@ append_chain_children(struct callchain_node *root,
 
 	/* lookup in childrens */
 	while (*p) {
-		s64 ret;
+		enum match_result ret;
 
 		parent = *p;
 		rnode = rb_entry(parent, struct callchain_node, rb_node_in);
 
 		/* If at least first entry matches, rely to children */
 		ret = append_chain(rnode, cursor, period);
-		if (ret == 0)
+		if (ret == MATCH_EQ)
 			goto inc_children_hit;
 
-		if (ret < 0)
+		if (ret == MATCH_LT)
 			p = &parent->rb_left;
 		else
 			p = &parent->rb_right;
@@ -611,7 +627,7 @@ inc_children_hit:
 	root->children_count++;
 }
 
-static int
+static enum match_result
 append_chain(struct callchain_node *root,
 	     struct callchain_cursor *cursor,
 	     u64 period)
@@ -620,7 +636,7 @@ append_chain(struct callchain_node *root,
 	u64 start = cursor->pos;
 	bool found = false;
 	u64 matches;
-	int cmp = 0;
+	enum match_result cmp = MATCH_ERROR;
 
 	/*
 	 * Lookup in the current node
@@ -636,7 +652,7 @@ append_chain(struct callchain_node *root,
 			break;
 
 		cmp = match_chain(node, cnode);
-		if (cmp)
+		if (cmp != MATCH_EQ)
 			break;
 
 		found = true;
@@ -646,7 +662,7 @@ append_chain(struct callchain_node *root,
 
 	/* matches not, relay no the parent */
 	if (!found) {
-		WARN_ONCE(!cmp, "Chain comparison error\n");
+		WARN_ONCE(cmp == MATCH_ERROR, "Chain comparison error\n");
 		return cmp;
 	}
 
@@ -655,20 +671,20 @@ append_chain(struct callchain_node *root,
 	/* we match only a part of the node. Split it and add the new chain */
 	if (matches < root->val_nr) {
 		split_add_child(root, cursor, cnode, start, matches, period);
-		return 0;
+		return MATCH_EQ;
 	}
 
 	/* we match 100% of the path, increment the hit */
 	if (matches == root->val_nr && cursor->pos == cursor->nr) {
 		root->hit += period;
 		root->count++;
-		return 0;
+		return MATCH_EQ;
 	}
 
 	/* We match the node and still have a part remaining */
 	append_chain_children(root, cursor, period);
 
-	return 0;
+	return MATCH_EQ;
 }
 
 int callchain_append(struct callchain_root *root,
-- 
2.7.0

[PATCH 05/23] perf callchain: Check return value of split_add_child()

[Namhyung Kim]

Now create_child() and add_child() return errors so check and pass it
to the caller.

Acked-by: Jiri Olsa <jolsa@kernel.org>
Cc: Frederic Weisbecker <fweisbec@gmail.com>
Signed-off-by: Namhyung Kim <namhyung@kernel.org>
---
 tools/perf/util/callchain.c | 12 +++++++++---
 1 file changed, 9 insertions(+), 3 deletions(-)

diff --git a/tools/perf/util/callchain.c b/tools/perf/util/callchain.c
index dab2c1f1e86b..5259379892e1 100644
--- a/tools/perf/util/callchain.c
+++ b/tools/perf/util/callchain.c
@@ -508,7 +508,7 @@ static enum match_result match_chain(struct callchain_cursor_node *node,
  * give a part of its callchain to the created child.
  * Then create another child to host the given callchain of new branch
  */
-static void
+static int
 split_add_child(struct callchain_node *parent,
 		struct callchain_cursor *cursor,
 		struct callchain_list *to_split,
@@ -520,6 +520,8 @@ split_add_child(struct callchain_node *parent,
 
 	/* split */
 	new = create_child(parent, true);
+	if (new == NULL)
+		return -1;
 
 	/* split the callchain and move a part to the new child */
 	old_tail = parent->val.prev;
@@ -554,7 +556,7 @@ split_add_child(struct callchain_node *parent,
 		node = callchain_cursor_current(cursor);
 		new = add_child(parent, cursor, period);
 		if (new == NULL)
-			return;
+			return -1;
 
 		/*
 		 * This is second child since we moved parent's children
@@ -576,6 +578,7 @@ split_add_child(struct callchain_node *parent,
 		parent->hit = period;
 		parent->count = 1;
 	}
+	return 0;
 }
 
 static enum match_result
@@ -670,7 +673,10 @@ append_chain(struct callchain_node *root,
 
 	/* we match only a part of the node. Split it and add the new chain */
 	if (matches < root->val_nr) {
-		split_add_child(root, cursor, cnode, start, matches, period);
+		if (split_add_child(root, cursor, cnode, start, matches,
+				    period) < 0)
+			return MATCH_ERROR;
+
 		return MATCH_EQ;
 	}
 
-- 
2.7.0

[PATCH 06/23] perf callchain: Check return value of append_chain_children()

[Namhyung Kim]

Now it can check the error case, so check and pass it to the caller.

Acked-by: Jiri Olsa <jolsa@kernel.org>
Cc: Frederic Weisbecker <fweisbec@gmail.com>
Signed-off-by: Namhyung Kim <namhyung@kernel.org>
---
 tools/perf/util/callchain.c | 18 ++++++++++++------
 1 file changed, 12 insertions(+), 6 deletions(-)

diff --git a/tools/perf/util/callchain.c b/tools/perf/util/callchain.c
index 5259379892e1..24b4bd0d7754 100644
--- a/tools/perf/util/callchain.c
+++ b/tools/perf/util/callchain.c
@@ -586,7 +586,7 @@ append_chain(struct callchain_node *root,
 	     struct callchain_cursor *cursor,
 	     u64 period);
 
-static void
+static int
 append_chain_children(struct callchain_node *root,
 		      struct callchain_cursor *cursor,
 		      u64 period)
@@ -598,7 +598,7 @@ append_chain_children(struct callchain_node *root,
 
 	node = callchain_cursor_current(cursor);
 	if (!node)
-		return;
+		return -1;
 
 	/* lookup in childrens */
 	while (*p) {
@@ -611,6 +611,8 @@ append_chain_children(struct callchain_node *root,
 		ret = append_chain(rnode, cursor, period);
 		if (ret == MATCH_EQ)
 			goto inc_children_hit;
+		if (ret == MATCH_ERROR)
+			return -1;
 
 		if (ret == MATCH_LT)
 			p = &parent->rb_left;
@@ -620,7 +622,7 @@ append_chain_children(struct callchain_node *root,
 	/* nothing in children, add to the current node */
 	rnode = add_child(root, cursor, period);
 	if (rnode == NULL)
-		return;
+		return -1;
 
 	rb_link_node(&rnode->rb_node_in, parent, p);
 	rb_insert_color(&rnode->rb_node_in, &root->rb_root_in);
@@ -628,6 +630,7 @@ append_chain_children(struct callchain_node *root,
 inc_children_hit:
 	root->children_hit += period;
 	root->children_count++;
+	return 0;
 }
 
 static enum match_result
@@ -688,7 +691,8 @@ append_chain(struct callchain_node *root,
 	}
 
 	/* We match the node and still have a part remaining */
-	append_chain_children(root, cursor, period);
+	if (append_chain_children(root, cursor, period) < 0)
+		return MATCH_ERROR;
 
 	return MATCH_EQ;
 }
@@ -702,7 +706,8 @@ int callchain_append(struct callchain_root *root,
 
 	callchain_cursor_commit(cursor);
 
-	append_chain_children(&root->node, cursor, period);
+	if (append_chain_children(&root->node, cursor, period) < 0)
+		return -1;
 
 	if (cursor->nr > root->max_depth)
 		root->max_depth = cursor->nr;
@@ -730,7 +735,8 @@ merge_chain_branch(struct callchain_cursor *cursor,
 
 	if (src->hit) {
 		callchain_cursor_commit(cursor);
-		append_chain_children(dst, cursor, src->hit);
+		if (append_chain_children(dst, cursor, src->hit) < 0)
+			return -1;
 	}
 
 	n = rb_first(&src->rb_root_in);
-- 
2.7.0

[PATCH 07/23] perf hists: Return error from hists__collapse_resort()

[Namhyung Kim]

Currently hists__collapse_resort() and hists__collapse_insert_entry()
don't return error code. Now callchain_merge() can check error case,
abort and pass the error to the user.  Later patch can add more work
which can be failed too.

Acked-by: Jiri Olsa <jolsa@kernel.org>
Signed-off-by: Namhyung Kim <namhyung@kernel.org>
---
 tools/perf/util/hist.c | 29 +++++++++++++++++++----------
 tools/perf/util/hist.h |  4 ++--
 2 files changed, 21 insertions(+), 12 deletions(-)

diff --git a/tools/perf/util/hist.c b/tools/perf/util/hist.c
index f6bdb827e6fb..b4157d5d5252 100644
--- a/tools/perf/util/hist.c
+++ b/tools/perf/util/hist.c
@@ -1025,8 +1025,8 @@ void hist_entry__delete(struct hist_entry *he)
  * collapse the histogram
  */
 
-bool hists__collapse_insert_entry(struct hists *hists __maybe_unused,
-				  struct rb_root *root, struct hist_entry *he)
+int hists__collapse_insert_entry(struct hists *hists, struct rb_root *root,
+				 struct hist_entry *he)
 {
 	struct rb_node **p = &root->rb_node;
 	struct rb_node *parent = NULL;
@@ -1040,18 +1040,21 @@ bool hists__collapse_insert_entry(struct hists *hists __maybe_unused,
 		cmp = hist_entry__collapse(iter, he);
 
 		if (!cmp) {
+			int ret = 0;
+
 			he_stat__add_stat(&iter->stat, &he->stat);
 			if (symbol_conf.cumulate_callchain)
 				he_stat__add_stat(iter->stat_acc, he->stat_acc);
 
 			if (symbol_conf.use_callchain) {
 				callchain_cursor_reset(&callchain_cursor);
-				callchain_merge(&callchain_cursor,
-						iter->callchain,
-						he->callchain);
+				if (callchain_merge(&callchain_cursor,
+						    iter->callchain,
+						    he->callchain) < 0)
+					ret = -1;
 			}
 			hist_entry__delete(he);
-			return false;
+			return ret;
 		}
 
 		if (cmp < 0)
@@ -1063,7 +1066,7 @@ bool hists__collapse_insert_entry(struct hists *hists __maybe_unused,
 
 	rb_link_node(&he->rb_node_in, parent, p);
 	rb_insert_color(&he->rb_node_in, root);
-	return true;
+	return 1;
 }
 
 struct rb_root *hists__get_rotate_entries_in(struct hists *hists)
@@ -1089,14 +1092,15 @@ static void hists__apply_filters(struct hists *hists, struct hist_entry *he)
 	hists__filter_entry_by_socket(hists, he);
 }
 
-void hists__collapse_resort(struct hists *hists, struct ui_progress *prog)
+int hists__collapse_resort(struct hists *hists, struct ui_progress *prog)
 {
 	struct rb_root *root;
 	struct rb_node *next;
 	struct hist_entry *n;
+	int ret;
 
 	if (!sort__need_collapse)
-		return;
+		return 0;
 
 	hists->nr_entries = 0;
 
@@ -1111,7 +1115,11 @@ void hists__collapse_resort(struct hists *hists, struct ui_progress *prog)
 		next = rb_next(&n->rb_node_in);
 
 		rb_erase(&n->rb_node_in, root);
-		if (hists__collapse_insert_entry(hists, &hists->entries_collapsed, n)) {
+		ret = hists__collapse_insert_entry(hists, &hists->entries_collapsed, n);
+		if (ret < 0)
+			return -1;
+
+		if (ret) {
 			/*
 			 * If it wasn't combined with one of the entries already
 			 * collapsed, we need to apply the filters that may have
@@ -1122,6 +1130,7 @@ void hists__collapse_resort(struct hists *hists, struct ui_progress *prog)
 		if (prog)
 			ui_progress__update(prog, 1);
 	}
+	return 0;
 }
 
 static int hist_entry__sort(struct hist_entry *a, struct hist_entry *b)
diff --git a/tools/perf/util/hist.h b/tools/perf/util/hist.h
index 21c1bc4661e3..b86c98c6dffd 100644
--- a/tools/perf/util/hist.h
+++ b/tools/perf/util/hist.h
@@ -133,7 +133,7 @@ void hist_entry__delete(struct hist_entry *he);
 
 void perf_evsel__output_resort(struct perf_evsel *evsel, struct ui_progress *prog);
 void hists__output_resort(struct hists *hists, struct ui_progress *prog);
-void hists__collapse_resort(struct hists *hists, struct ui_progress *prog);
+int 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__delete_entries(struct hists *hists);
@@ -192,7 +192,7 @@ int hists__init(void);
 int __hists__init(struct hists *hists, struct perf_hpp_list *hpp_list);
 
 struct rb_root *hists__get_rotate_entries_in(struct hists *hists);
-bool hists__collapse_insert_entry(struct hists *hists __maybe_unused,
+int hists__collapse_insert_entry(struct hists *hists,
 				  struct rb_root *root, struct hist_entry *he);
 
 struct perf_hpp {
-- 
2.7.0

[PATCH 08/23] perf report: Check error during report__collapse_hists()

[Namhyung Kim]

If it returns an error, warn user and bail out instead of silently
ignoring.

Acked-by: Jiri Olsa <jolsa@kernel.org>
Signed-off-by: Namhyung Kim <namhyung@kernel.org>
---
 tools/perf/builtin-report.c | 14 +++++++++++---
 1 file changed, 11 insertions(+), 3 deletions(-)

diff --git a/tools/perf/builtin-report.c b/tools/perf/builtin-report.c
index 1eab50ac1ef6..760e886ca9d9 100644
--- a/tools/perf/builtin-report.c
+++ b/tools/perf/builtin-report.c
@@ -469,10 +469,11 @@ static int report__browse_hists(struct report *rep)
 	return ret;
 }
 
-static void report__collapse_hists(struct report *rep)
+static int report__collapse_hists(struct report *rep)
 {
 	struct ui_progress prog;
 	struct perf_evsel *pos;
+	int ret = 0;
 
 	ui_progress__init(&prog, rep->nr_entries, "Merging related events...");
 
@@ -484,7 +485,9 @@ static void report__collapse_hists(struct report *rep)
 
 		hists->socket_filter = rep->socket_filter;
 
-		hists__collapse_resort(hists, &prog);
+		ret = hists__collapse_resort(hists, &prog);
+		if (ret < 0)
+			break;
 
 		/* Non-group events are considered as leader */
 		if (symbol_conf.event_group &&
@@ -497,6 +500,7 @@ static void report__collapse_hists(struct report *rep)
 	}
 
 	ui_progress__finish();
+	return ret;
 }
 
 static void report__output_resort(struct report *rep)
@@ -564,7 +568,11 @@ static int __cmd_report(struct report *rep)
 		}
 	}
 
-	report__collapse_hists(rep);
+	ret = report__collapse_hists(rep);
+	if (ret) {
+		ui__error("failed to process hist entry\n");
+		return ret;
+	}
 
 	if (session_done())
 		return 0;
-- 
2.7.0

[PATCH 09/23] perf hists: Basic support of hierarchical report view

[Namhyung Kim]

In the hierarchical view, entries will be grouped and sorted on the
first key, and then second key, and so on.  Add he->hroot_{in,out} field
to keep lower level entries. Actually this can be shared with callchain
sorted_root since the hroots are only used by non-leaf entries and
callchain is only used by leaf entries.

It also adds parent_he and depth fields which can be used by browsers.

This patch only implements collapsing part which creates internal
entries for each sort key.  These need to be sorted by output_sort stage
and to be displayed properly in the later patch(es).

Acked-by: Pekka Enberg <penberg@kernel.org>
Signed-off-by: Namhyung Kim <namhyung@kernel.org>
---
 tools/perf/util/hist.c   | 97 ++++++++++++++++++++++++++++++++++++++++++++++++
 tools/perf/util/sort.h   | 13 ++++++-
 tools/perf/util/symbol.h |  3 +-
 3 files changed, 111 insertions(+), 2 deletions(-)

diff --git a/tools/perf/util/hist.c b/tools/perf/util/hist.c
index b4157d5d5252..cbf30d246204 100644
--- a/tools/perf/util/hist.c
+++ b/tools/perf/util/hist.c
@@ -1025,6 +1025,99 @@ void hist_entry__delete(struct hist_entry *he)
  * collapse the histogram
  */
 
+static void hists__apply_filters(struct hists *hists, struct hist_entry *he);
+
+static struct hist_entry *hierarchy_insert_entry(struct hists *hists,
+						 struct rb_root *root,
+						 struct hist_entry *he,
+						 struct perf_hpp_fmt *fmt)
+{
+	struct rb_node **p = &root->rb_node;
+	struct rb_node *parent = NULL;
+	struct hist_entry *iter, *new;
+	int64_t cmp;
+
+	while (*p != NULL) {
+		parent = *p;
+		iter = rb_entry(parent, struct hist_entry, rb_node_in);
+
+		cmp = fmt->collapse(fmt, iter, he);
+		if (!cmp) {
+			he_stat__add_stat(&iter->stat, &he->stat);
+			return iter;
+		}
+
+		if (cmp < 0)
+			p = &parent->rb_left;
+		else
+			p = &parent->rb_right;
+	}
+
+	new = hist_entry__new(he, true);
+	if (new == NULL)
+		return NULL;
+
+	hists__apply_filters(hists, new);
+	hists->nr_entries++;
+
+	/* save related format for output */
+	new->fmt = fmt;
+
+	/* it's now passed to 'new' */
+	he->trace_output = NULL;
+
+	rb_link_node(&new->rb_node_in, parent, p);
+	rb_insert_color(&new->rb_node_in, root);
+	return new;
+}
+
+static int hists__hierarchy_insert_entry(struct hists *hists,
+					 struct rb_root *root,
+					 struct hist_entry *he)
+{
+	struct perf_hpp_fmt *fmt;
+	struct hist_entry *new_he = NULL;
+	struct hist_entry *parent = NULL;
+	int depth = 0;
+	int ret = 0;
+
+	hists__for_each_sort_list(hists, fmt) {
+		if (!perf_hpp__is_sort_entry(fmt) &&
+		    !perf_hpp__is_dynamic_entry(fmt))
+			continue;
+
+		/* insert copy of 'he' for each fmt into the hierarchy */
+		new_he = hierarchy_insert_entry(hists, root, he, fmt);
+		if (new_he == NULL) {
+			ret = -1;
+			break;
+		}
+
+		root = &new_he->hroot_in;
+		new_he->parent_he = parent;
+		new_he->depth = depth++;
+		parent = new_he;
+	}
+
+	if (new_he) {
+		new_he->leaf = true;
+
+		if (symbol_conf.use_callchain) {
+			callchain_cursor_reset(&callchain_cursor);
+			if (callchain_merge(&callchain_cursor,
+					    new_he->callchain,
+					    he->callchain) < 0)
+				ret = -1;
+		}
+	}
+
+	/* 'he' is no longer used */
+	hist_entry__delete(he);
+
+	/* return 0 (or -1) since it already applied filters */
+	return ret;
+}
+
 int hists__collapse_insert_entry(struct hists *hists, struct rb_root *root,
 				 struct hist_entry *he)
 {
@@ -1033,6 +1126,9 @@ int hists__collapse_insert_entry(struct hists *hists, struct rb_root *root,
 	struct hist_entry *iter;
 	int64_t cmp;
 
+	if (symbol_conf.report_hierarchy)
+		return hists__hierarchy_insert_entry(hists, root, he);
+
 	while (*p != NULL) {
 		parent = *p;
 		iter = rb_entry(parent, struct hist_entry, rb_node_in);
@@ -1063,6 +1159,7 @@ int hists__collapse_insert_entry(struct hists *hists, struct rb_root *root,
 			p = &(*p)->rb_right;
 	}
 	hists->nr_entries++;
+	he->leaf = true;
 
 	rb_link_node(&he->rb_node_in, parent, p);
 	rb_insert_color(&he->rb_node_in, root);
diff --git a/tools/perf/util/sort.h b/tools/perf/util/sort.h
index 89a1273fd2da..0cdfd0cfe783 100644
--- a/tools/perf/util/sort.h
+++ b/tools/perf/util/sort.h
@@ -96,9 +96,11 @@ struct hist_entry {
 	s32			socket;
 	s32			cpu;
 	u8			cpumode;
+	u8			depth;
 
 	/* We are added by hists__add_dummy_entry. */
 	bool			dummy;
+	bool			leaf;
 
 	char			level;
 	u8			filtered;
@@ -120,13 +122,22 @@ struct hist_entry {
 	char			*srcline;
 	char			*srcfile;
 	struct symbol		*parent;
-	struct rb_root		sorted_chain;
 	struct branch_info	*branch_info;
 	struct hists		*hists;
 	struct mem_info		*mem_info;
 	void			*raw_data;
 	u32			raw_size;
 	void			*trace_output;
+	struct perf_hpp_fmt	*fmt;
+	struct hist_entry	*parent_he;
+	union {
+		/* this is for hierarchical entry structure */
+		struct {
+			struct rb_root	hroot_in;
+			struct rb_root  hroot_out;
+		};				/* non-leaf entries */
+		struct rb_root	sorted_chain;	/* leaf entry has callchains */
+	};
 	struct callchain_root	callchain[0]; /* must be last member */
 };
 
diff --git a/tools/perf/util/symbol.h b/tools/perf/util/symbol.h
index ccd1caa40e11..a937053a0ae0 100644
--- a/tools/perf/util/symbol.h
+++ b/tools/perf/util/symbol.h
@@ -110,7 +110,8 @@ struct symbol_conf {
 			has_filter,
 			show_ref_callgraph,
 			hide_unresolved,
-			raw_trace;
+			raw_trace,
+			report_hierarchy;
 	const char	*vmlinux_name,
 			*kallsyms_name,
 			*source_prefix,
-- 
2.7.0

[PATCH 10/23] perf hists: Resort hist entries with hierarchy

[Namhyung Kim]

For hierarchical output, each entries should be sorted in their
rbtree (hroot) properly.  Add hists__hierarchy_output_resort() to do the
job.  Note that those hierarchy entries share the period counts, it'd be
important to update the hists->stats only once (for leaves).

Acked-by: Pekka Enberg <penberg@kernel.org>
Signed-off-by: Namhyung Kim <namhyung@kernel.org>
---
 tools/perf/util/hist.c | 92 ++++++++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 89 insertions(+), 3 deletions(-)

diff --git a/tools/perf/util/hist.c b/tools/perf/util/hist.c
index cbf30d246204..c00183558e22 100644
--- a/tools/perf/util/hist.c
+++ b/tools/perf/util/hist.c
@@ -1277,6 +1277,84 @@ void hists__inc_stats(struct hists *hists, struct hist_entry *h)
 	hists->stats.total_period += h->stat.period;
 }
 
+static void hierarchy_insert_output_entry(struct rb_root *root,
+					  struct hist_entry *he)
+{
+	struct rb_node **p = &root->rb_node;
+	struct rb_node *parent = NULL;
+	struct hist_entry *iter;
+
+	while (*p != NULL) {
+		parent = *p;
+		iter = rb_entry(parent, struct hist_entry, rb_node);
+
+		if (hist_entry__sort(he, iter) > 0)
+			p = &parent->rb_left;
+		else
+			p = &parent->rb_right;
+	}
+
+	rb_link_node(&he->rb_node, parent, p);
+	rb_insert_color(&he->rb_node, root);
+}
+
+static void hists__hierarchy_output_resort(struct hists *hists,
+					   struct ui_progress *prog,
+					   struct rb_root *root_in,
+					   struct rb_root *root_out,
+					   u64 min_callchain_hits,
+					   bool use_callchain)
+{
+	struct rb_node *node;
+	struct hist_entry *he;
+
+	*root_out = RB_ROOT;
+	node = rb_first(root_in);
+
+	while (node) {
+		he = rb_entry(node, struct hist_entry, rb_node_in);
+		node = rb_next(node);
+
+		hierarchy_insert_output_entry(root_out, he);
+
+		if (prog)
+			ui_progress__update(prog, 1);
+
+		if (!he->leaf) {
+			hists__hierarchy_output_resort(hists, prog,
+						       &he->hroot_in,
+						       &he->hroot_out,
+						       min_callchain_hits,
+						       use_callchain);
+			hists->nr_entries++;
+			if (!he->filtered)
+				hists->nr_non_filtered_entries++;
+
+			continue;
+		}
+
+		/* only update stat for leaf entries to avoid duplication */
+		hists__inc_stats(hists, he);
+		if (!he->filtered)
+			hists__calc_col_len(hists, he);
+
+		if (!use_callchain)
+			continue;
+
+		if (callchain_param.mode == CHAIN_GRAPH_REL) {
+			u64 total = he->stat.period;
+
+			if (symbol_conf.cumulate_callchain)
+				total = he->stat_acc->period;
+
+			min_callchain_hits = total * (callchain_param.min_percent / 100);
+		}
+
+		callchain_param.sort(&he->sorted_chain, he->callchain,
+				     min_callchain_hits, &callchain_param);
+	}
+}
+
 static void __hists__insert_output_entry(struct rb_root *entries,
 					 struct hist_entry *he,
 					 u64 min_callchain_hits,
@@ -1328,6 +1406,17 @@ static void output_resort(struct hists *hists, struct ui_progress *prog,
 
 	min_callchain_hits = callchain_total * (callchain_param.min_percent / 100);
 
+	hists__reset_stats(hists);
+	hists__reset_col_len(hists);
+
+	if (symbol_conf.report_hierarchy) {
+		return hists__hierarchy_output_resort(hists, prog,
+						      &hists->entries_collapsed,
+						      &hists->entries,
+						      min_callchain_hits,
+						      use_callchain);
+	}
+
 	if (sort__need_collapse)
 		root = &hists->entries_collapsed;
 	else
@@ -1336,9 +1425,6 @@ static void output_resort(struct hists *hists, struct ui_progress *prog,
 	next = rb_first(root);
 	hists->entries = RB_ROOT;
 
-	hists__reset_stats(hists);
-	hists__reset_col_len(hists);
-
 	while (next) {
 		n = rb_entry(next, struct hist_entry, rb_node_in);
 		next = rb_next(&n->rb_node_in);
-- 
2.7.0

[PATCH 11/23] perf hists: Add helper functions for hierarchy mode

[Namhyung Kim]

The rb_hierarchy_{next,prev,last} functions are to traverse all
hist entries in a hierarchy.  They will be used by various function
which supports hierarchy output.

Acked-by: Pekka Enberg <penberg@kernel.org>
Signed-off-by: Namhyung Kim <namhyung@kernel.org>
---
 tools/perf/util/hist.c | 46 ++++++++++++++++++++++++++++++++++++++++++++++
 tools/perf/util/hist.h |  4 ++++
 2 files changed, 50 insertions(+)

diff --git a/tools/perf/util/hist.c b/tools/perf/util/hist.c
index c00183558e22..def0120d57ab 100644
--- a/tools/perf/util/hist.c
+++ b/tools/perf/util/hist.c
@@ -1440,6 +1440,7 @@ static void output_resort(struct hists *hists, struct ui_progress *prog,
 	}
 }
 
+
 void perf_evsel__output_resort(struct perf_evsel *evsel, struct ui_progress *prog)
 {
 	bool use_callchain;
@@ -1457,6 +1458,51 @@ void hists__output_resort(struct hists *hists, struct ui_progress *prog)
 	output_resort(hists, prog, symbol_conf.use_callchain);
 }
 
+struct rb_node *rb_hierarchy_last(struct rb_node *node)
+{
+	struct hist_entry *he = rb_entry(node, struct hist_entry, rb_node);
+
+	while (he->unfolded && !he->leaf) {
+		node = rb_last(&he->hroot_out);
+		he = rb_entry(node, struct hist_entry, rb_node);
+	}
+	return node;
+}
+
+struct rb_node *rb_hierarchy_next(struct rb_node *node)
+{
+	struct hist_entry *he = rb_entry(node, struct hist_entry, rb_node);
+
+	if (!he->leaf && he->unfolded)
+		node = rb_first(&he->hroot_out);
+	else
+		node = rb_next(node);
+
+	while (node == NULL) {
+		he = he->parent_he;
+		if (he == NULL)
+			break;
+
+		node = rb_next(&he->rb_node);
+	}
+	return node;
+}
+
+struct rb_node *rb_hierarchy_prev(struct rb_node *node)
+{
+	struct hist_entry *he = rb_entry(node, struct hist_entry, rb_node);
+
+	node = rb_prev(node);
+	if (node)
+		return rb_hierarchy_last(node);
+
+	he = he->parent_he;
+	if (he == NULL)
+		return NULL;
+
+	return &he->rb_node;
+}
+
 static void hists__remove_entry_filter(struct hists *hists, struct hist_entry *h,
 				       enum hist_filter filter)
 {
diff --git a/tools/perf/util/hist.h b/tools/perf/util/hist.h
index b86c98c6dffd..adfc9931e186 100644
--- a/tools/perf/util/hist.h
+++ b/tools/perf/util/hist.h
@@ -410,4 +410,8 @@ int perf_hist_config(const char *var, const char *value);
 
 void perf_hpp_list__init(struct perf_hpp_list *list);
 
+struct rb_node *rb_hierarchy_last(struct rb_node *node);
+struct rb_node *rb_hierarchy_next(struct rb_node *node);
+struct rb_node *rb_hierarchy_prev(struct rb_node *node);
+
 #endif	/* __PERF_HIST_H */
-- 
2.7.0

[PATCH 12/23] perf hists: Introduce hist_entry__filter()

[Namhyung Kim]

The hist_entry__filter() function is to filter hist entries using
sort key relatd info.  This is needed to support hierarchy mode since
each hist entry will be associated with a hpp fmt which has a sort key.
So each entry should compare to only matching type of filters.

To do that, add the ->se_filter callback field to struct sort_entry.
This callback takes 'type' argument which determines whether it's
matching sort key or not.  It returns -1 for non-matching type, 0 for
filtered entry and 1 for not filtered entries.

Acked-by: Pekka Enberg <penberg@kernel.org>
Signed-off-by: Namhyung Kim <namhyung@kernel.org>
---
 tools/perf/util/hist.h |   2 +
 tools/perf/util/sort.c | 113 +++++++++++++++++++++++++++++++++++++++++++++++++
 tools/perf/util/sort.h |   1 +
 3 files changed, 116 insertions(+)

diff --git a/tools/perf/util/hist.h b/tools/perf/util/hist.h
index adfc9931e186..0bf60c3bf895 100644
--- a/tools/perf/util/hist.h
+++ b/tools/perf/util/hist.h
@@ -297,6 +297,8 @@ bool perf_hpp__is_sort_entry(struct perf_hpp_fmt *format);
 bool perf_hpp__is_dynamic_entry(struct perf_hpp_fmt *format);
 bool perf_hpp__defined_dynamic_entry(struct perf_hpp_fmt *fmt, struct hists *hists);
 
+int hist_entry__filter(struct hist_entry *he, int type, const void *arg);
+
 static inline bool perf_hpp__should_skip(struct perf_hpp_fmt *format,
 					 struct hists *hists)
 {
diff --git a/tools/perf/util/sort.c b/tools/perf/util/sort.c
index de620f7f40f4..cef3b6329a35 100644
--- a/tools/perf/util/sort.c
+++ b/tools/perf/util/sort.c
@@ -81,10 +81,21 @@ static int hist_entry__thread_snprintf(struct hist_entry *he, char *bf,
 			       width, width, comm ?: "");
 }
 
+static int hist_entry__thread_filter(struct hist_entry *he, int type, const void *arg)
+{
+	const struct thread *th = arg;
+
+	if (type != HIST_FILTER__THREAD)
+		return -1;
+
+	return th && he->thread != th;
+}
+
 struct sort_entry sort_thread = {
 	.se_header	= "  Pid:Command",
 	.se_cmp		= sort__thread_cmp,
 	.se_snprintf	= hist_entry__thread_snprintf,
+	.se_filter	= hist_entry__thread_filter,
 	.se_width_idx	= HISTC_THREAD,
 };
 
@@ -122,6 +133,7 @@ struct sort_entry sort_comm = {
 	.se_collapse	= sort__comm_collapse,
 	.se_sort	= sort__comm_sort,
 	.se_snprintf	= hist_entry__comm_snprintf,
+	.se_filter	= hist_entry__thread_filter,
 	.se_width_idx	= HISTC_COMM,
 };
 
@@ -171,10 +183,21 @@ static int hist_entry__dso_snprintf(struct hist_entry *he, char *bf,
 	return _hist_entry__dso_snprintf(he->ms.map, bf, size, width);
 }
 
+static int hist_entry__dso_filter(struct hist_entry *he, int type, const void *arg)
+{
+	const struct dso *dso = arg;
+
+	if (type != HIST_FILTER__DSO)
+		return -1;
+
+	return dso && (!he->ms.map || he->ms.map->dso != dso);
+}
+
 struct sort_entry sort_dso = {
 	.se_header	= "Shared Object",
 	.se_cmp		= sort__dso_cmp,
 	.se_snprintf	= hist_entry__dso_snprintf,
+	.se_filter	= hist_entry__dso_filter,
 	.se_width_idx	= HISTC_DSO,
 };
 
@@ -275,11 +298,22 @@ static int hist_entry__sym_snprintf(struct hist_entry *he, char *bf,
 					 he->level, bf, size, width);
 }
 
+static int hist_entry__sym_filter(struct hist_entry *he, int type, const void *arg)
+{
+	const char *sym = arg;
+
+	if (type != HIST_FILTER__SYMBOL)
+		return -1;
+
+	return sym && (!he->ms.sym || !strstr(he->ms.sym->name, sym));
+}
+
 struct sort_entry sort_sym = {
 	.se_header	= "Symbol",
 	.se_cmp		= sort__sym_cmp,
 	.se_sort	= sort__sym_sort,
 	.se_snprintf	= hist_entry__sym_snprintf,
+	.se_filter	= hist_entry__sym_filter,
 	.se_width_idx	= HISTC_SYMBOL,
 };
 
@@ -440,10 +474,21 @@ static int hist_entry__socket_snprintf(struct hist_entry *he, char *bf,
 	return repsep_snprintf(bf, size, "%*.*d", width, width-3, he->socket);
 }
 
+static int hist_entry__socket_filter(struct hist_entry *he, int type, const void *arg)
+{
+	int socket = *(const int *)arg;
+
+	if (type != HIST_FILTER__SOCKET)
+		return -1;
+
+	return socket >= 0 && he->socket != socket;
+}
+
 struct sort_entry sort_socket = {
 	.se_header      = "Socket",
 	.se_cmp	        = sort__socket_cmp,
 	.se_snprintf    = hist_entry__socket_snprintf,
+	.se_filter      = hist_entry__socket_filter,
 	.se_width_idx	= HISTC_SOCKET,
 };
 
@@ -533,6 +578,18 @@ static int hist_entry__dso_from_snprintf(struct hist_entry *he, char *bf,
 		return repsep_snprintf(bf, size, "%-*.*s", width, width, "N/A");
 }
 
+static int hist_entry__dso_from_filter(struct hist_entry *he, int type,
+				       const void *arg)
+{
+	const struct dso *dso = arg;
+
+	if (type != HIST_FILTER__DSO)
+		return -1;
+
+	return dso && (!he->branch_info || !he->branch_info->from.map ||
+		       he->branch_info->from.map->dso != dso);
+}
+
 static int64_t
 sort__dso_to_cmp(struct hist_entry *left, struct hist_entry *right)
 {
@@ -553,6 +610,18 @@ static int hist_entry__dso_to_snprintf(struct hist_entry *he, char *bf,
 		return repsep_snprintf(bf, size, "%-*.*s", width, width, "N/A");
 }
 
+static int hist_entry__dso_to_filter(struct hist_entry *he, int type,
+				     const void *arg)
+{
+	const struct dso *dso = arg;
+
+	if (type != HIST_FILTER__DSO)
+		return -1;
+
+	return dso && (!he->branch_info || !he->branch_info->to.map ||
+		       he->branch_info->to.map->dso != dso);
+}
+
 static int64_t
 sort__sym_from_cmp(struct hist_entry *left, struct hist_entry *right)
 {
@@ -614,10 +683,35 @@ static int hist_entry__sym_to_snprintf(struct hist_entry *he, char *bf,
 	return repsep_snprintf(bf, size, "%-*.*s", width, width, "N/A");
 }
 
+static int hist_entry__sym_from_filter(struct hist_entry *he, int type,
+				       const void *arg)
+{
+	const char *sym = arg;
+
+	if (type != HIST_FILTER__SYMBOL)
+		return -1;
+
+	return sym && !(he->branch_info && he->branch_info->from.sym &&
+			strstr(he->branch_info->from.sym->name, sym));
+}
+
+static int hist_entry__sym_to_filter(struct hist_entry *he, int type,
+				       const void *arg)
+{
+	const char *sym = arg;
+
+	if (type != HIST_FILTER__SYMBOL)
+		return -1;
+
+	return sym && !(he->branch_info && he->branch_info->to.sym &&
+		        strstr(he->branch_info->to.sym->name, sym));
+}
+
 struct sort_entry sort_dso_from = {
 	.se_header	= "Source Shared Object",
 	.se_cmp		= sort__dso_from_cmp,
 	.se_snprintf	= hist_entry__dso_from_snprintf,
+	.se_filter	= hist_entry__dso_from_filter,
 	.se_width_idx	= HISTC_DSO_FROM,
 };
 
@@ -625,6 +719,7 @@ struct sort_entry sort_dso_to = {
 	.se_header	= "Target Shared Object",
 	.se_cmp		= sort__dso_to_cmp,
 	.se_snprintf	= hist_entry__dso_to_snprintf,
+	.se_filter	= hist_entry__dso_to_filter,
 	.se_width_idx	= HISTC_DSO_TO,
 };
 
@@ -632,6 +727,7 @@ struct sort_entry sort_sym_from = {
 	.se_header	= "Source Symbol",
 	.se_cmp		= sort__sym_from_cmp,
 	.se_snprintf	= hist_entry__sym_from_snprintf,
+	.se_filter	= hist_entry__sym_from_filter,
 	.se_width_idx	= HISTC_SYMBOL_FROM,
 };
 
@@ -639,6 +735,7 @@ struct sort_entry sort_sym_to = {
 	.se_header	= "Target Symbol",
 	.se_cmp		= sort__sym_to_cmp,
 	.se_snprintf	= hist_entry__sym_to_snprintf,
+	.se_filter	= hist_entry__sym_to_filter,
 	.se_width_idx	= HISTC_SYMBOL_TO,
 };
 
@@ -1605,6 +1702,22 @@ static struct perf_hpp_fmt *__hpp_dimension__alloc_hpp(struct hpp_dimension *hd)
 	return fmt;
 }
 
+int hist_entry__filter(struct hist_entry *he, int type, const void *arg)
+{
+	struct perf_hpp_fmt *fmt;
+	struct hpp_sort_entry *hse;
+
+	fmt = he->fmt;
+	if (fmt == NULL || !perf_hpp__is_sort_entry(fmt))
+		return -1;
+
+	hse = container_of(fmt, struct hpp_sort_entry, hpp);
+	if (hse->se->se_filter == NULL)
+		return -1;
+
+	return hse->se->se_filter(he, type, arg);
+}
+
 static int __sort_dimension__add_hpp_sort(struct sort_dimension *sd)
 {
 	struct hpp_sort_entry *hse = __sort_dimension__alloc_hpp(sd);
diff --git a/tools/perf/util/sort.h b/tools/perf/util/sort.h
index 0cdfd0cfe783..ce962743c087 100644
--- a/tools/perf/util/sort.h
+++ b/tools/perf/util/sort.h
@@ -234,6 +234,7 @@ struct sort_entry {
 	int64_t	(*se_sort)(struct hist_entry *, struct hist_entry *);
 	int	(*se_snprintf)(struct hist_entry *he, char *bf, size_t size,
 			       unsigned int width);
+	int	(*se_filter)(struct hist_entry *he, int type, const void *arg);
 	u8	se_width_idx;
 };
 
-- 
2.7.0

[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@kernel.org>
Signed-off-by: Namhyung Kim <namhyung@kernel.org>
---
 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

[PATCH 14/23] perf ui/stdio: Implement hierarchy output mode

[Namhyung Kim]

The hierarchy output mode is to group entries for each level so that
user can see higher level picture more easily.  It also helps to find
out which component is most costly.  The output will look like below:

      15.11%     swapper
         14.97%     [kernel.vmlinux]
          0.09%     [libahci]
          0.05%     [iwlwifi]
      10.29%     irq/33-iwlwifi
          6.45%     [kernel.vmlinux]
          1.41%     [mac80211]
          1.15%     [iwldvm]
          1.14%     [iwlwifi]
          0.14%     [cfg80211]
       4.81%     firefox
          3.92%     libxul.so
          0.34%     [kernel.vmlinux]

Acked-by: Pekka Enberg <penberg@kernel.org>
Signed-off-by: Namhyung Kim <namhyung@kernel.org>
---
 tools/perf/ui/hist.c       | 14 +++++++++
 tools/perf/ui/stdio/hist.c | 77 +++++++++++++++++++++++++++++++++++++++++++++-
 tools/perf/util/hist.h     |  4 +++
 3 files changed, 94 insertions(+), 1 deletion(-)

diff --git a/tools/perf/ui/hist.c b/tools/perf/ui/hist.c
index 1ba4117d9c2d..c398ce288615 100644
--- a/tools/perf/ui/hist.c
+++ b/tools/perf/ui/hist.c
@@ -687,3 +687,17 @@ void perf_hpp__set_user_width(const char *width_list_str)
 			break;
 	}
 }
+
+int perf_hpp__count_sort_keys(void)
+{
+	int nr_sort = 0;
+	struct perf_hpp_fmt *fmt;
+
+	perf_hpp_list__for_each_format(&perf_hpp_list, fmt) {
+		if (perf_hpp__is_sort_entry(fmt) ||
+		    perf_hpp__is_dynamic_entry(fmt))
+			nr_sort++;
+	}
+
+	return nr_sort;
+}
diff --git a/tools/perf/ui/stdio/hist.c b/tools/perf/ui/stdio/hist.c
index 1a6e8f7f38c4..b58f718a6afc 100644
--- a/tools/perf/ui/stdio/hist.c
+++ b/tools/perf/ui/stdio/hist.c
@@ -409,6 +409,71 @@ static int hist_entry__snprintf(struct hist_entry *he, struct perf_hpp *hpp)
 	return hpp->buf - start;
 }
 
+static int hist_entry__hierarchy_fprintf(struct hist_entry *he,
+					 struct perf_hpp *hpp,
+					 int nr_sort_key, struct hists *hists,
+					 FILE *fp)
+{
+	const char *sep = symbol_conf.field_sep;
+	struct perf_hpp_fmt *fmt;
+	char *buf = hpp->buf;
+	int ret, printed = 0;
+	bool first = true;
+
+	if (symbol_conf.exclude_other && !he->parent)
+		return 0;
+
+	ret = scnprintf(hpp->buf, hpp->size, "%*s", he->depth * HIERARCHY_INDENT, "");
+	advance_hpp(hpp, ret);
+
+	hists__for_each_format(he->hists, fmt) {
+		if (perf_hpp__is_sort_entry(fmt) || perf_hpp__is_dynamic_entry(fmt))
+			break;
+
+		/*
+		 * If there's no field_sep, we still need
+		 * to display initial '  '.
+		 */
+		if (!sep || !first) {
+			ret = scnprintf(hpp->buf, hpp->size, "%s", sep ?: "  ");
+			advance_hpp(hpp, ret);
+		} else
+			first = false;
+
+		if (perf_hpp__use_color() && fmt->color)
+			ret = fmt->color(fmt, hpp, he);
+		else
+			ret = fmt->entry(fmt, hpp, he);
+
+		advance_hpp(hpp, ret);
+	}
+
+	if (sep)
+		ret = scnprintf(hpp->buf, hpp->size, "%s", sep);
+	else
+		ret = scnprintf(hpp->buf, hpp->size, "%*s",
+				(nr_sort_key - 1) * HIERARCHY_INDENT + 2, "");
+	advance_hpp(hpp, ret);
+
+	fmt = he->fmt;
+	if (perf_hpp__use_color() && fmt->color)
+		fmt->color(fmt, hpp, he);
+	else
+		fmt->entry(fmt, hpp, he);
+
+	printed += fprintf(fp, "%s\n", buf);
+
+	if (symbol_conf.use_callchain && he->leaf) {
+		u64 total = hists__total_period(hists);
+
+		printed += hist_entry_callchain__fprintf(he, total, 0, fp);
+		goto out;
+	}
+
+out:
+	return printed;
+}
+
 static int hist_entry__fprintf(struct hist_entry *he, size_t size,
 			       struct hists *hists,
 			       char *bf, size_t bfsz, FILE *fp)
@@ -423,6 +488,13 @@ static int hist_entry__fprintf(struct hist_entry *he, size_t size,
 	if (size == 0 || size > bfsz)
 		size = hpp.size = bfsz;
 
+	if (symbol_conf.report_hierarchy) {
+		int nr_sort = perf_hpp__count_sort_keys();
+
+		return hist_entry__hierarchy_fprintf(he, &hpp, nr_sort,
+						     hists, fp);
+	}
+
 	hist_entry__snprintf(he, &hpp);
 
 	ret = fprintf(fp, "%s\n", bf);
@@ -521,7 +593,7 @@ print_entries:
 		goto out;
 	}
 
-	for (nd = rb_first(&hists->entries); nd; nd = rb_next(nd)) {
+	for (nd = rb_first(&hists->entries); nd; nd = rb_hierarchy_next(nd)) {
 		struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
 		float percent;
 
@@ -542,6 +614,9 @@ print_entries:
 						   MAP__FUNCTION, fp);
 			fprintf(fp, "%.10s end\n", graph_dotted_line);
 		}
+
+		if (symbol_conf.report_hierarchy)
+			h->unfolded = true;
 	}
 
 	free(line);
diff --git a/tools/perf/util/hist.h b/tools/perf/util/hist.h
index 0bf60c3bf895..1ccab10302d2 100644
--- a/tools/perf/util/hist.h
+++ b/tools/perf/util/hist.h
@@ -416,4 +416,8 @@ struct rb_node *rb_hierarchy_last(struct rb_node *node);
 struct rb_node *rb_hierarchy_next(struct rb_node *node);
 struct rb_node *rb_hierarchy_prev(struct rb_node *node);
 
+#define HIERARCHY_INDENT  3
+
+int perf_hpp__count_sort_keys(void);
+
 #endif	/* __PERF_HIST_H */
-- 
2.7.0

[PATCH 15/23] perf ui/stdio: Align column header for hierarchy output

[Namhyung Kim]

The hierarchy output mode is to group entries so the existing columns
won't fit to the new output.  Treat all sort keys as a single column and
separate headers by "/".

  #    Overhead  Command / Shared Object
  # ...........  ................................
  #
      15.11%     swapper
         14.97%     [kernel.vmlinux]
          0.09%     [libahci]
          0.05%     [iwlwifi]
  ...

Acked-by: Pekka Enberg <penberg@kernel.org>
Signed-off-by: Namhyung Kim <namhyung@kernel.org>
---
 tools/perf/ui/stdio/hist.c | 107 +++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 107 insertions(+)

diff --git a/tools/perf/ui/stdio/hist.c b/tools/perf/ui/stdio/hist.c
index b58f718a6afc..4bdab3cf1b6c 100644
--- a/tools/perf/ui/stdio/hist.c
+++ b/tools/perf/ui/stdio/hist.c
@@ -505,6 +505,108 @@ static int hist_entry__fprintf(struct hist_entry *he, size_t size,
 	return ret;
 }
 
+static int print_hierarchy_indent(const char *sep, int nr_sort,
+				  const char *line, FILE *fp)
+{
+	if (sep != NULL || nr_sort < 1)
+		return 0;
+
+	return fprintf(fp, "%-.*s", (nr_sort - 1) * HIERARCHY_INDENT, line);
+}
+
+static int print_hierarchy_header(struct hists *hists, struct perf_hpp *hpp,
+				  const char *sep, FILE *fp)
+{
+	bool first = true;
+	int nr_sort;
+	unsigned width = 0;
+	unsigned header_width = 0;
+	struct perf_hpp_fmt *fmt;
+	const char spaces[] = "                                               "
+	"                                                                     "
+	"                                                                     ";
+	const char dots[] = "................................................."
+	"....................................................................."
+	".....................................................................";
+
+	nr_sort = perf_hpp__count_sort_keys();
+
+	/* preserve max indent depth for column headers */
+	print_hierarchy_indent(sep, nr_sort, spaces, fp);
+
+	hists__for_each_format(hists, fmt) {
+		if (perf_hpp__is_sort_entry(fmt) || perf_hpp__is_dynamic_entry(fmt))
+			break;
+
+		if (!first)
+			fprintf(fp, "%s", sep ?: "  ");
+		else
+			first = false;
+
+		fmt->header(fmt, hpp, hists_to_evsel(hists));
+		fprintf(fp, "%s", hpp->buf);
+	}
+
+	/* combine sort headers with ' / ' */
+	first = true;
+	hists__for_each_format(hists, fmt) {
+		if (!perf_hpp__is_sort_entry(fmt) && !perf_hpp__is_dynamic_entry(fmt))
+			continue;
+
+		if (!first)
+			header_width += fprintf(fp, " / ");
+		else {
+			header_width += fprintf(fp, "%s", sep ?: "  ");
+			first = false;
+		}
+
+		fmt->header(fmt, hpp, hists_to_evsel(hists));
+		rtrim(hpp->buf);
+
+		header_width += fprintf(fp, "%s", hpp->buf);
+	}
+
+	/* preserve max indent depth for combined sort headers */
+	print_hierarchy_indent(sep, nr_sort, spaces, fp);
+
+	fprintf(fp, "\n# ");
+
+	/* preserve max indent depth for initial dots */
+	print_hierarchy_indent(sep, nr_sort, dots, fp);
+
+	first = true;
+	hists__for_each_format(hists, fmt) {
+		if (perf_hpp__is_sort_entry(fmt) || perf_hpp__is_dynamic_entry(fmt))
+			break;
+
+		if (!first)
+			fprintf(fp, "%s", sep ?: "  ");
+		else
+			first = false;
+
+		width = fmt->width(fmt, hpp, hists_to_evsel(hists));
+		fprintf(fp, "%.*s", width, dots);
+	}
+
+	hists__for_each_format(hists, fmt) {
+		if (!perf_hpp__is_sort_entry(fmt) && !perf_hpp__is_dynamic_entry(fmt))
+			continue;
+
+		width = fmt->width(fmt, hpp, hists_to_evsel(hists));
+		if (width > header_width)
+			header_width = width;
+	}
+
+	fprintf(fp, "%s%-.*s", sep ?: "  ", header_width, dots);
+
+	/* preserve max indent depth for dots under sort headers */
+	print_hierarchy_indent(sep, nr_sort, dots, fp);
+
+	fprintf(fp, "\n#\n");
+
+	return 2;
+}
+
 size_t hists__fprintf(struct hists *hists, bool show_header, int max_rows,
 		      int max_cols, float min_pcnt, FILE *fp)
 {
@@ -536,6 +638,11 @@ size_t hists__fprintf(struct hists *hists, bool show_header, int max_rows,
 
 	fprintf(fp, "# ");
 
+	if (symbol_conf.report_hierarchy) {
+		nr_rows += print_hierarchy_header(hists, &dummy_hpp, sep, fp);
+		goto print_entries;
+	}
+
 	hists__for_each_format(hists, fmt) {
 		if (perf_hpp__should_skip(fmt, hists))
 			continue;
-- 
2.7.0

[PATCH 16/23] perf hists browser: Count number of hierarchy entries

[Namhyung Kim]

Add nr_hierarchy_entries field to keep current number of (unfolded) hist
entries.  And the hist_entry->nr_rows carries number of direct children.
But in the hierarchy mode, entry can have grand children and callchains.
So update the number properly using hierarchy_count_rows() when toggling
the folded state (by pressing ENTER key).

Acked-by: Pekka Enberg <penberg@kernel.org>
Signed-off-by: Namhyung Kim <namhyung@kernel.org>
---
 tools/perf/ui/browsers/hists.c | 85 ++++++++++++++++++++++++++++++++++++------
 1 file changed, 74 insertions(+), 11 deletions(-)

diff --git a/tools/perf/ui/browsers/hists.c b/tools/perf/ui/browsers/hists.c
index a5a5390476ac..bf005e3662c4 100644
--- a/tools/perf/ui/browsers/hists.c
+++ b/tools/perf/ui/browsers/hists.c
@@ -32,6 +32,7 @@ struct hist_browser {
 	bool		     show_headers;
 	float		     min_pcnt;
 	u64		     nr_non_filtered_entries;
+	u64		     nr_hierarchy_entries;
 	u64		     nr_callchain_rows;
 };
 
@@ -58,11 +59,11 @@ static int hist_browser__get_folding(struct hist_browser *browser)
 
 	for (nd = rb_first(&hists->entries);
 	     (nd = hists__filter_entries(nd, browser->min_pcnt)) != NULL;
-	     nd = rb_next(nd)) {
+	     nd = rb_hierarchy_next(nd)) {
 		struct hist_entry *he =
 			rb_entry(nd, struct hist_entry, rb_node);
 
-		if (he->unfolded)
+		if (he->leaf && he->unfolded)
 			unfolded_rows += he->nr_rows;
 	}
 	return unfolded_rows;
@@ -72,7 +73,9 @@ static u32 hist_browser__nr_entries(struct hist_browser *hb)
 {
 	u32 nr_entries;
 
-	if (hist_browser__has_filter(hb))
+	if (symbol_conf.report_hierarchy)
+		nr_entries = hb->nr_hierarchy_entries;
+	else if (hist_browser__has_filter(hb))
 		nr_entries = hb->nr_non_filtered_entries;
 	else
 		nr_entries = hb->hists->nr_entries;
@@ -247,6 +250,35 @@ static int callchain__count_rows(struct rb_root *chain)
 	return n;
 }
 
+static int hierarchy_count_rows(struct hist_browser *hb, struct hist_entry *he,
+				bool include_children)
+{
+	int count = 0;
+	struct rb_node *node;
+	struct hist_entry *child;
+
+	if (he->leaf)
+		return callchain__count_rows(&he->sorted_chain);
+
+	node = rb_first(&he->hroot_out);
+	while (node) {
+		float percent;
+
+		child = rb_entry(node, struct hist_entry, rb_node);
+		percent = hist_entry__get_percent_limit(child);
+
+		if (!child->filtered && percent >= hb->min_pcnt) {
+			count++;
+
+			if (include_children && child->unfolded)
+				count += hierarchy_count_rows(hb, child, true);
+		}
+
+		node = rb_next(node);
+	}
+	return count;
+}
+
 static bool hist_entry__toggle_fold(struct hist_entry *he)
 {
 	if (!he)
@@ -326,11 +358,17 @@ static void callchain__init_have_children(struct rb_root *root)
 
 static void hist_entry__init_have_children(struct hist_entry *he)
 {
-	if (!he->init_have_children) {
+	if (he->init_have_children)
+		return;
+
+	if (he->leaf) {
 		he->has_children = !RB_EMPTY_ROOT(&he->sorted_chain);
 		callchain__init_have_children(&he->sorted_chain);
-		he->init_have_children = true;
+	} else {
+		he->has_children = !RB_EMPTY_ROOT(&he->hroot_out);
 	}
+
+	he->init_have_children = true;
 }
 
 static bool hist_browser__toggle_fold(struct hist_browser *browser)
@@ -349,17 +387,41 @@ static bool hist_browser__toggle_fold(struct hist_browser *browser)
 		has_children = callchain_list__toggle_fold(cl);
 
 	if (has_children) {
+		int child_rows = 0;
+
 		hist_entry__init_have_children(he);
 		browser->b.nr_entries -= he->nr_rows;
-		browser->nr_callchain_rows -= he->nr_rows;
 
-		if (he->unfolded)
-			he->nr_rows = callchain__count_rows(&he->sorted_chain);
+		if (he->leaf)
+			browser->nr_callchain_rows -= he->nr_rows;
 		else
+			browser->nr_hierarchy_entries -= he->nr_rows;
+
+		if (symbol_conf.report_hierarchy)
+			child_rows = hierarchy_count_rows(browser, he, true);
+
+		if (he->unfolded) {
+			if (he->leaf)
+				he->nr_rows = callchain__count_rows(&he->sorted_chain);
+			else
+				he->nr_rows = hierarchy_count_rows(browser, he, false);
+
+			/* account grand children */
+			if (symbol_conf.report_hierarchy)
+				browser->b.nr_entries += child_rows - he->nr_rows;
+		} else {
+			if (symbol_conf.report_hierarchy)
+				browser->b.nr_entries -= child_rows - he->nr_rows;
+
 			he->nr_rows = 0;
+		}
 
 		browser->b.nr_entries += he->nr_rows;
-		browser->nr_callchain_rows += he->nr_rows;
+
+		if (he->leaf)
+			browser->nr_callchain_rows += he->nr_rows;
+		else
+			browser->nr_hierarchy_entries += he->nr_rows;
 
 		return true;
 	}
@@ -2016,17 +2078,18 @@ static void hist_browser__update_nr_entries(struct hist_browser *hb)
 	u64 nr_entries = 0;
 	struct rb_node *nd = rb_first(&hb->hists->entries);
 
-	if (hb->min_pcnt == 0) {
+	if (hb->min_pcnt == 0 && !symbol_conf.report_hierarchy) {
 		hb->nr_non_filtered_entries = hb->hists->nr_non_filtered_entries;
 		return;
 	}
 
 	while ((nd = hists__filter_entries(nd, hb->min_pcnt)) != NULL) {
 		nr_entries++;
-		nd = rb_next(nd);
+		nd = rb_hierarchy_next(nd);
 	}
 
 	hb->nr_non_filtered_entries = nr_entries;
+	hb->nr_hierarchy_entries = nr_entries;
 }
 
 static void hist_browser__update_percent_limit(struct hist_browser *hb,
-- 
2.7.0

[PATCH 17/23] perf hists browser: Support collapsing/expanding whole entries in hierarchy

[Namhyung Kim]

The 'C' and 'E' keys are to collapse/expand all hist entries.  Update
nr_hierarchy_entries properly in this case.

Acked-by: Pekka Enberg <penberg@kernel.org>
Signed-off-by: Namhyung Kim <namhyung@kernel.org>
---
 tools/perf/ui/browsers/hists.c | 65 +++++++++++++++++++++++++++++++++++-------
 1 file changed, 54 insertions(+), 11 deletions(-)

diff --git a/tools/perf/ui/browsers/hists.c b/tools/perf/ui/browsers/hists.c
index bf005e3662c4..e42ed634e722 100644
--- a/tools/perf/ui/browsers/hists.c
+++ b/tools/perf/ui/browsers/hists.c
@@ -484,13 +484,37 @@ static int callchain__set_folding(struct rb_root *chain, bool unfold)
 	return n;
 }
 
-static void hist_entry__set_folding(struct hist_entry *he, bool unfold)
+static int hierarchy_set_folding(struct hist_browser *hb, struct hist_entry *he,
+				 bool unfold __maybe_unused)
+{
+	float percent;
+	struct rb_node *nd;
+	struct hist_entry *child;
+	int n = 0;
+
+	for (nd = rb_first(&he->hroot_out); nd; nd = rb_next(nd)) {
+		child = rb_entry(nd, struct hist_entry, rb_node);
+		percent = hist_entry__get_percent_limit(child);
+		if (!child->filtered && percent >= hb->min_pcnt)
+			n++;
+	}
+
+	return n;
+}
+
+static void hist_entry__set_folding(struct hist_entry *he,
+				    struct hist_browser *hb, bool unfold)
 {
-	hist_entry__init_have_children(he);
 	he->unfolded = unfold ? he->has_children : false;
 
 	if (he->has_children) {
-		int n = callchain__set_folding(&he->sorted_chain, unfold);
+		int n;
+
+		if (he->leaf)
+			n = callchain__set_folding(&he->sorted_chain, unfold);
+		else
+			n = hierarchy_set_folding(hb, he, unfold);
+
 		he->nr_rows = unfold ? n : 0;
 	} else
 		he->nr_rows = 0;
@@ -500,19 +524,38 @@ static void
 __hist_browser__set_folding(struct hist_browser *browser, bool unfold)
 {
 	struct rb_node *nd;
-	struct hists *hists = browser->hists;
+	struct hist_entry *he;
+	double percent;
 
-	for (nd = rb_first(&hists->entries);
-	     (nd = hists__filter_entries(nd, browser->min_pcnt)) != NULL;
-	     nd = rb_next(nd)) {
-		struct hist_entry *he = rb_entry(nd, struct hist_entry, rb_node);
-		hist_entry__set_folding(he, unfold);
-		browser->nr_callchain_rows += he->nr_rows;
+	nd = rb_first(&browser->hists->entries);
+	while (nd) {
+		he = rb_entry(nd, struct hist_entry, rb_node);
+
+		hist_entry__init_have_children(he);
+
+		/*
+		 * Tentatively set unfolded so that the rb_hierarchy_next()
+		 * can toggle children of folded entries too.
+		 */
+		he->unfolded = he->has_children;
+		nd = rb_hierarchy_next(nd);
+
+		hist_entry__set_folding(he, browser, unfold);
+
+		percent = hist_entry__get_percent_limit(he);
+		if (he->filtered || percent < browser->min_pcnt)
+			continue;
+
+		if (!he->depth || unfold)
+			browser->nr_hierarchy_entries++;
+		if (he->leaf)
+			browser->nr_callchain_rows += he->nr_rows;
 	}
 }
 
 static void hist_browser__set_folding(struct hist_browser *browser, bool unfold)
 {
+	browser->nr_hierarchy_entries = 0;
 	browser->nr_callchain_rows = 0;
 	__hist_browser__set_folding(browser, unfold);
 
@@ -2122,7 +2165,7 @@ static void hist_browser__update_percent_limit(struct hist_browser *hb,
 
 		/* force to re-evaluate folding state of callchains */
 		he->init_have_children = false;
-		hist_entry__set_folding(he, false);
+		hist_entry__set_folding(he, hb, false);
 
 		nd = rb_next(nd);
 	}
-- 
2.7.0

[PATCH 18/23] perf hists browser: Implement hierarchy output

[Namhyung Kim]

Implement hierarchy mode in TUI.  The output is look like stdio but it
also supports to fold/unfold children dynamically.

Acked-by: Pekka Enberg <penberg@kernel.org>
Signed-off-by: Namhyung Kim <namhyung@kernel.org>
---
 tools/perf/ui/browsers/hists.c | 269 +++++++++++++++++++++++++++++++++++++----
 1 file changed, 247 insertions(+), 22 deletions(-)

diff --git a/tools/perf/ui/browsers/hists.c b/tools/perf/ui/browsers/hists.c
index e42ed634e722..8eeaa3d66bda 100644
--- a/tools/perf/ui/browsers/hists.c
+++ b/tools/perf/ui/browsers/hists.c
@@ -1257,6 +1257,137 @@ static int hist_browser__show_entry(struct hist_browser *browser,
 	return printed;
 }
 
+static int hist_browser__show_hierarchy_entry(struct hist_browser *browser,
+					      struct hist_entry *entry,
+					      unsigned short row,
+					      int level, int nr_sort_keys)
+{
+	char s[256];
+	int printed = 0;
+	int width = browser->b.width;
+	char folded_sign = ' ';
+	bool current_entry = ui_browser__is_current_entry(&browser->b, row);
+	off_t row_offset = entry->row_offset;
+	bool first = true;
+	struct perf_hpp_fmt *fmt;
+	struct hpp_arg arg = {
+		.b		= &browser->b,
+		.current_entry	= current_entry,
+	};
+	struct perf_hpp hpp = {
+		.buf		= s,
+		.size		= sizeof(s),
+		.ptr		= &arg,
+	};
+	int column = 0;
+	int hierarchy_indent = (nr_sort_keys - 1) * HIERARCHY_INDENT;
+
+	if (current_entry) {
+		browser->he_selection = entry;
+		browser->selection = &entry->ms;
+	}
+
+	hist_entry__init_have_children(entry);
+	folded_sign = hist_entry__folded(entry);
+	arg.folded_sign = folded_sign;
+
+	if (entry->leaf && row_offset) {
+		row_offset--;
+		goto show_callchain;
+	}
+
+	hist_browser__gotorc(browser, row, 0);
+
+	if (current_entry && browser->b.navkeypressed)
+		ui_browser__set_color(&browser->b, HE_COLORSET_SELECTED);
+	else
+		ui_browser__set_color(&browser->b, HE_COLORSET_NORMAL);
+
+	ui_browser__write_nstring(&browser->b, "", level * HIERARCHY_INDENT);
+	width -= level * HIERARCHY_INDENT;
+
+	hists__for_each_format(entry->hists, fmt) {
+		if (perf_hpp__should_skip(fmt, entry->hists) ||
+		    column++ < browser->b.horiz_scroll)
+			continue;
+
+		if (perf_hpp__is_sort_entry(fmt) ||
+		    perf_hpp__is_dynamic_entry(fmt))
+			break;
+
+		if (current_entry && browser->b.navkeypressed) {
+			ui_browser__set_color(&browser->b,
+					      HE_COLORSET_SELECTED);
+		} else {
+			ui_browser__set_color(&browser->b,
+					      HE_COLORSET_NORMAL);
+		}
+
+		if (first) {
+			ui_browser__printf(&browser->b, "%c", folded_sign);
+			width--;
+			first = false;
+		} else {
+			ui_browser__printf(&browser->b, "  ");
+			width -= 2;
+		}
+
+		if (fmt->color) {
+			width -= fmt->color(fmt, &hpp, entry);
+		} else {
+			width -= fmt->entry(fmt, &hpp, entry);
+			ui_browser__printf(&browser->b, "%s", s);
+		}
+	}
+
+	ui_browser__write_nstring(&browser->b, "", hierarchy_indent);
+	width -= hierarchy_indent;
+
+	if (column >= browser->b.horiz_scroll) {
+		if (current_entry && browser->b.navkeypressed) {
+			ui_browser__set_color(&browser->b,
+					      HE_COLORSET_SELECTED);
+		} else {
+			ui_browser__set_color(&browser->b,
+					      HE_COLORSET_NORMAL);
+		}
+
+		ui_browser__write_nstring(&browser->b, "", 2);
+		width -= 2;
+
+		fmt = entry->fmt;
+		if (fmt->color) {
+			width -= fmt->color(fmt, &hpp, entry);
+		} else {
+			width -= fmt->entry(fmt, &hpp, entry);
+			ui_browser__printf(&browser->b, "%s", s);
+		}
+	}
+
+	/* The scroll bar isn't being used */
+	if (!browser->b.navkeypressed)
+		width += 1;
+
+	ui_browser__write_nstring(&browser->b, "", width);
+
+	++row;
+	++printed;
+
+show_callchain:
+	if (entry->leaf && folded_sign == '-' && row != browser->b.rows) {
+		struct callchain_print_arg carg = {
+			.row_offset = row_offset,
+		};
+
+		printed += hist_browser__show_callchain(browser, entry,
+					level + 1, row,
+					hist_browser__show_callchain_entry, &carg,
+					hist_browser__check_output_full);
+	}
+
+	return printed;
+}
+
 static int advance_hpp_check(struct perf_hpp *hpp, int inc)
 {
 	advance_hpp(hpp, inc);
@@ -1322,6 +1453,7 @@ static unsigned int hist_browser__refresh(struct ui_browser *browser)
 	u16 header_offset = 0;
 	struct rb_node *nd;
 	struct hist_browser *hb = container_of(browser, struct hist_browser, b);
+	int nr_sort = perf_hpp__count_sort_keys();
 
 	if (hb->show_headers) {
 		hist_browser__show_headers(hb);
@@ -1332,18 +1464,28 @@ static unsigned int hist_browser__refresh(struct ui_browser *browser)
 	hb->he_selection = NULL;
 	hb->selection = NULL;
 
-	for (nd = browser->top; nd; nd = rb_next(nd)) {
+	for (nd = browser->top; nd; nd = rb_hierarchy_next(nd)) {
 		struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
 		float percent;
 
-		if (h->filtered)
+		if (h->filtered) {
+			/* let it move to sibling */
+			h->unfolded = false;
 			continue;
+		}
 
 		percent = hist_entry__get_percent_limit(h);
 		if (percent < hb->min_pcnt)
 			continue;
 
-		row += hist_browser__show_entry(hb, h, row);
+		if (symbol_conf.report_hierarchy) {
+			row += hist_browser__show_hierarchy_entry(hb, h, row,
+								  h->depth,
+								  nr_sort);
+		} else {
+			row += hist_browser__show_entry(hb, h, row);
+		}
+
 		if (row == browser->rows)
 			break;
 	}
@@ -1361,7 +1503,14 @@ static struct rb_node *hists__filter_entries(struct rb_node *nd,
 		if (!h->filtered && percent >= min_pcnt)
 			return nd;
 
-		nd = rb_next(nd);
+		/*
+		 * If it's filtered, its all children also were filtered.
+		 * So move to sibling node.
+		 */
+		if (rb_next(nd))
+			nd = rb_next(nd);
+		else
+			nd = rb_hierarchy_next(nd);
 	}
 
 	return NULL;
@@ -1377,7 +1526,7 @@ static struct rb_node *hists__filter_prev_entries(struct rb_node *nd,
 		if (!h->filtered && percent >= min_pcnt)
 			return nd;
 
-		nd = rb_prev(nd);
+		nd = rb_hierarchy_prev(nd);
 	}
 
 	return NULL;
@@ -1407,8 +1556,8 @@ static void ui_browser__hists_seek(struct ui_browser *browser,
 		nd = browser->top;
 		goto do_offset;
 	case SEEK_END:
-		nd = hists__filter_prev_entries(rb_last(browser->entries),
-						hb->min_pcnt);
+		nd = rb_hierarchy_last(rb_last(browser->entries));
+		nd = hists__filter_prev_entries(nd, hb->min_pcnt);
 		first = false;
 		break;
 	default:
@@ -1442,7 +1591,7 @@ do_offset:
 	if (offset > 0) {
 		do {
 			h = rb_entry(nd, struct hist_entry, rb_node);
-			if (h->unfolded) {
+			if (h->unfolded && h->leaf) {
 				u16 remaining = h->nr_rows - h->row_offset;
 				if (offset > remaining) {
 					offset -= remaining;
@@ -1454,7 +1603,8 @@ do_offset:
 					break;
 				}
 			}
-			nd = hists__filter_entries(rb_next(nd), hb->min_pcnt);
+			nd = hists__filter_entries(rb_hierarchy_next(nd),
+						   hb->min_pcnt);
 			if (nd == NULL)
 				break;
 			--offset;
@@ -1463,7 +1613,7 @@ do_offset:
 	} else if (offset < 0) {
 		while (1) {
 			h = rb_entry(nd, struct hist_entry, rb_node);
-			if (h->unfolded) {
+			if (h->unfolded && h->leaf) {
 				if (first) {
 					if (-offset > h->row_offset) {
 						offset += h->row_offset;
@@ -1487,7 +1637,7 @@ do_offset:
 				}
 			}
 
-			nd = hists__filter_prev_entries(rb_prev(nd),
+			nd = hists__filter_prev_entries(rb_hierarchy_prev(nd),
 							hb->min_pcnt);
 			if (nd == NULL)
 				break;
@@ -1500,7 +1650,7 @@ do_offset:
 				 * row_offset at its last entry.
 				 */
 				h = rb_entry(nd, struct hist_entry, rb_node);
-				if (h->unfolded)
+				if (h->unfolded && h->leaf)
 					h->row_offset = h->nr_rows;
 				break;
 			}
@@ -1514,13 +1664,14 @@ do_offset:
 }
 
 static int hist_browser__fprintf_callchain(struct hist_browser *browser,
-					   struct hist_entry *he, FILE *fp)
+					   struct hist_entry *he, FILE *fp,
+					   int level)
 {
 	struct callchain_print_arg arg  = {
 		.fp = fp,
 	};
 
-	hist_browser__show_callchain(browser, he, 1, 0,
+	hist_browser__show_callchain(browser, he, level, 0,
 				     hist_browser__fprintf_callchain_entry, &arg,
 				     hist_browser__check_dump_full);
 	return arg.printed;
@@ -1562,7 +1713,65 @@ static int hist_browser__fprintf_entry(struct hist_browser *browser,
 	printed += fprintf(fp, "%s\n", rtrim(s));
 
 	if (folded_sign == '-')
-		printed += hist_browser__fprintf_callchain(browser, he, fp);
+		printed += hist_browser__fprintf_callchain(browser, he, fp, 1);
+
+	return printed;
+}
+
+
+static int hist_browser__fprintf_hierarchy_entry(struct hist_browser *browser,
+						 struct hist_entry *he,
+						 FILE *fp, int level,
+						 int nr_sort_keys)
+{
+	char s[8192];
+	int printed = 0;
+	char folded_sign = ' ';
+	struct perf_hpp hpp = {
+		.buf = s,
+		.size = sizeof(s),
+	};
+	struct perf_hpp_fmt *fmt;
+	bool first = true;
+	int ret;
+	int hierarchy_indent = (nr_sort_keys + 1) * HIERARCHY_INDENT;
+
+	printed = fprintf(fp, "%*s", level * HIERARCHY_INDENT, "");
+
+	folded_sign = hist_entry__folded(he);
+	printed += fprintf(fp, "%c", folded_sign);
+
+	hists__for_each_format(he->hists, fmt) {
+		if (perf_hpp__should_skip(fmt, he->hists))
+			continue;
+
+		if (perf_hpp__is_sort_entry(fmt) ||
+		    perf_hpp__is_dynamic_entry(fmt))
+			break;
+
+		if (!first) {
+			ret = scnprintf(hpp.buf, hpp.size, "  ");
+			advance_hpp(&hpp, ret);
+		} else
+			first = false;
+
+		ret = fmt->entry(fmt, &hpp, he);
+		advance_hpp(&hpp, ret);
+	}
+
+	ret = scnprintf(hpp.buf, hpp.size, "%*s", hierarchy_indent, "");
+	advance_hpp(&hpp, ret);
+
+	fmt = he->fmt;
+	ret = fmt->entry(fmt, &hpp, he);
+	advance_hpp(&hpp, ret);
+
+	printed += fprintf(fp, "%s\n", rtrim(s));
+
+	if (he->leaf && folded_sign == '-') {
+		printed += hist_browser__fprintf_callchain(browser, he, fp,
+							   he->depth + 1);
+	}
 
 	return printed;
 }
@@ -1572,12 +1781,22 @@ static int hist_browser__fprintf(struct hist_browser *browser, FILE *fp)
 	struct rb_node *nd = hists__filter_entries(rb_first(browser->b.entries),
 						   browser->min_pcnt);
 	int printed = 0;
+	int nr_sort = perf_hpp__count_sort_keys();
 
 	while (nd) {
 		struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
 
-		printed += hist_browser__fprintf_entry(browser, h, fp);
-		nd = hists__filter_entries(rb_next(nd), browser->min_pcnt);
+		if (symbol_conf.report_hierarchy) {
+			printed += hist_browser__fprintf_hierarchy_entry(browser,
+									 h, fp,
+									 h->depth,
+									 nr_sort);
+		} else {
+			printed += hist_browser__fprintf_entry(browser, h, fp);
+		}
+
+		nd = hists__filter_entries(rb_hierarchy_next(nd),
+					   browser->min_pcnt);
 	}
 
 	return printed;
@@ -2145,12 +2364,12 @@ static void hist_browser__update_percent_limit(struct hist_browser *hb,
 
 	hb->min_pcnt = callchain_param.min_percent = percent;
 
-	if (!symbol_conf.use_callchain)
-		return;
-
 	while ((nd = hists__filter_entries(nd, hb->min_pcnt)) != NULL) {
 		he = rb_entry(nd, struct hist_entry, rb_node);
 
+		if (!he->leaf || !symbol_conf.use_callchain)
+			goto next;
+
 		if (callchain_param.mode == CHAIN_GRAPH_REL) {
 			total = he->stat.period;
 
@@ -2163,11 +2382,17 @@ static void hist_browser__update_percent_limit(struct hist_browser *hb,
 		callchain_param.sort(&he->sorted_chain, he->callchain,
 				     min_callchain_hits, &callchain_param);
 
+next:
+		/*
+		 * Tentatively set unfolded so that the rb_hierarchy_next()
+		 * can toggle children of folded entries too.
+		 */
+		he->unfolded = he->has_children;
+		nd = rb_hierarchy_next(nd);
+
 		/* force to re-evaluate folding state of callchains */
 		he->init_have_children = false;
 		hist_entry__set_folding(he, hb, false);
-
-		nd = rb_next(nd);
 	}
 }
 
-- 
2.7.0

[PATCH 19/23] perf hists browser: Align column header in hierarchy mode

[Namhyung Kim]

Like in stdio, fit column header to hierarchy output.  Merge column
headers with "/" as a separator.

   Overhead        Command / Shared Object / Symbol
  ...
  +   0.09%        dwm
  +   0.06%        emacs
  -   0.05%        perf
     -   0.05%        [kernel.vmlinux]
        +   0.03%        [k] memcpy_orig
        +   0.01%        [k] unmap_single_vma
        +   0.01%        [k] smp_call_function_single
        +   0.00%        [k] native_irq_return_iret
        +   0.00%        [k] arch_trigger_all_cpu_backtrace_handler
        +   0.00%        [k] native_write_msr_safe

Acked-by: Pekka Enberg <penberg@kernel.org>
Signed-off-by: Namhyung Kim <namhyung@kernel.org>
---
 tools/perf/ui/browsers/hists.c | 69 +++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 68 insertions(+), 1 deletion(-)

diff --git a/tools/perf/ui/browsers/hists.c b/tools/perf/ui/browsers/hists.c
index 8eeaa3d66bda..d8955c6657f5 100644
--- a/tools/perf/ui/browsers/hists.c
+++ b/tools/perf/ui/browsers/hists.c
@@ -1427,11 +1427,78 @@ static int hists_browser__scnprintf_headers(struct hist_browser *browser, char *
 	return ret;
 }
 
+static int hists_browser__scnprintf_hierarchy_headers(struct hist_browser *browser, char *buf, size_t size)
+{
+	struct hists *hists = browser->hists;
+	struct perf_hpp dummy_hpp = {
+		.buf    = buf,
+		.size   = size,
+	};
+	struct perf_hpp_fmt *fmt;
+	size_t ret = 0;
+	int column = 0;
+	int nr_sort_keys = perf_hpp__count_sort_keys();
+	bool first = true;
+
+	ret = scnprintf(buf, size, " ");
+	if (advance_hpp_check(&dummy_hpp, ret))
+		return ret;
+
+	hists__for_each_format(hists, fmt) {
+		if (column++ < browser->b.horiz_scroll)
+			continue;
+
+		if (perf_hpp__is_sort_entry(fmt) || perf_hpp__is_dynamic_entry(fmt))
+			break;
+
+		ret = fmt->header(fmt, &dummy_hpp, hists_to_evsel(hists));
+		if (advance_hpp_check(&dummy_hpp, ret))
+			break;
+
+		ret = scnprintf(dummy_hpp.buf, dummy_hpp.size, "  ");
+		if (advance_hpp_check(&dummy_hpp, ret))
+			break;
+	}
+
+	ret = scnprintf(dummy_hpp.buf, dummy_hpp.size, "%*s",
+			(nr_sort_keys - 1) * HIERARCHY_INDENT, "");
+	if (advance_hpp_check(&dummy_hpp, ret))
+		return ret;
+
+	hists__for_each_format(hists, fmt) {
+		if (!perf_hpp__is_sort_entry(fmt) && !perf_hpp__is_dynamic_entry(fmt))
+			continue;
+
+		if (first) {
+			first = false;
+		} else {
+			ret = scnprintf(dummy_hpp.buf, dummy_hpp.size, " / ");
+			if (advance_hpp_check(&dummy_hpp, ret))
+				break;
+		}
+
+		ret = fmt->header(fmt, &dummy_hpp, hists_to_evsel(hists));
+		dummy_hpp.buf[ret] = '\0';
+		rtrim(dummy_hpp.buf);
+
+		ret = strlen(dummy_hpp.buf);
+		if (advance_hpp_check(&dummy_hpp, ret))
+			break;
+	}
+
+	return ret;
+}
+
 static void hist_browser__show_headers(struct hist_browser *browser)
 {
 	char headers[1024];
 
-	hists_browser__scnprintf_headers(browser, headers, sizeof(headers));
+	if (symbol_conf.report_hierarchy)
+		hists_browser__scnprintf_hierarchy_headers(browser, headers,
+							   sizeof(headers));
+	else
+		hists_browser__scnprintf_headers(browser, headers,
+						 sizeof(headers));
 	ui_browser__gotorc(&browser->b, 0, 0);
 	ui_browser__set_color(&browser->b, HE_COLORSET_ROOT);
 	ui_browser__write_nstring(&browser->b, headers, browser->b.width + 1);
-- 
2.7.0

[PATCH 20/23] perf ui/gtk: Implement hierarchy output mode

[Namhyung Kim]

The hierarchy output mode is to group entries for each level so that
user can see higher level picture more easily.

Acked-by: Pekka Enberg <penberg@kernel.org>
Signed-off-by: Namhyung Kim <namhyung@kernel.org>
---
 tools/perf/ui/gtk/hists.c | 161 +++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 160 insertions(+), 1 deletion(-)

diff --git a/tools/perf/ui/gtk/hists.c b/tools/perf/ui/gtk/hists.c
index 32cc38a5b57f..803676545fc0 100644
--- a/tools/perf/ui/gtk/hists.c
+++ b/tools/perf/ui/gtk/hists.c
@@ -396,6 +396,162 @@ static void perf_gtk__show_hists(GtkWidget *window, struct hists *hists,
 	gtk_container_add(GTK_CONTAINER(window), view);
 }
 
+static void perf_gtk__add_hierarchy_entries(struct hists *hists,
+					    struct rb_root *root,
+					    GtkTreeStore *store,
+					    GtkTreeIter *parent,
+					    struct perf_hpp *hpp,
+					    float min_pcnt)
+{
+	int col_idx = 0;
+	struct rb_node *node;
+	struct hist_entry *he;
+	struct perf_hpp_fmt *fmt;
+	u64 total = hists__total_period(hists);
+
+	for (node = rb_first(root); node; node = rb_next(node)) {
+		GtkTreeIter iter;
+		float percent;
+
+		he = rb_entry(node, struct hist_entry, rb_node);
+		if (he->filtered)
+			continue;
+
+		percent = hist_entry__get_percent_limit(he);
+		if (percent < min_pcnt)
+			continue;
+
+		gtk_tree_store_append(store, &iter, parent);
+
+		col_idx = 0;
+		hists__for_each_format(hists, fmt) {
+			if (perf_hpp__is_sort_entry(fmt) ||
+			    perf_hpp__is_dynamic_entry(fmt))
+				break;
+
+			if (fmt->color)
+				fmt->color(fmt, hpp, he);
+			else
+				fmt->entry(fmt, hpp, he);
+
+			gtk_tree_store_set(store, &iter, col_idx++, hpp->buf, -1);
+		}
+
+		fmt = he->fmt;
+		if (fmt->color)
+			fmt->color(fmt, hpp, he);
+		else
+			fmt->entry(fmt, hpp, he);
+
+		gtk_tree_store_set(store, &iter, col_idx, rtrim(hpp->buf), -1);
+
+		if (!he->leaf) {
+			perf_gtk__add_hierarchy_entries(hists, &he->hroot_out,
+							store, &iter, hpp,
+							min_pcnt);
+		}
+
+		if (symbol_conf.use_callchain && he->leaf) {
+			if (callchain_param.mode == CHAIN_GRAPH_REL)
+				total = symbol_conf.cumulate_callchain ?
+					he->stat_acc->period : he->stat.period;
+
+			perf_gtk__add_callchain(&he->sorted_chain, store, &iter,
+						col_idx, total);
+		}
+	}
+
+}
+
+static void perf_gtk__show_hierarchy(GtkWidget *window, struct hists *hists,
+				     float min_pcnt)
+{
+	struct perf_hpp_fmt *fmt;
+	GType col_types[MAX_COLUMNS];
+	GtkCellRenderer *renderer;
+	GtkTreeStore *store;
+	GtkWidget *view;
+	int col_idx;
+	int nr_cols = 0;
+	char s[512];
+	char buf[512];
+	bool first = true;
+	struct perf_hpp hpp = {
+		.buf		= s,
+		.size		= sizeof(s),
+	};
+
+	hists__for_each_format(hists, fmt) {
+		if (perf_hpp__is_sort_entry(fmt) ||
+		    perf_hpp__is_dynamic_entry(fmt))
+			break;
+
+		col_types[nr_cols++] = G_TYPE_STRING;
+	}
+	col_types[nr_cols++] = G_TYPE_STRING;
+
+	store = gtk_tree_store_newv(nr_cols, col_types);
+	view = gtk_tree_view_new();
+	renderer = gtk_cell_renderer_text_new();
+
+	col_idx = 0;
+	hists__for_each_format(hists, fmt) {
+		if (perf_hpp__is_sort_entry(fmt) ||
+		    perf_hpp__is_dynamic_entry(fmt))
+			break;
+
+		gtk_tree_view_insert_column_with_attributes(GTK_TREE_VIEW(view),
+							    -1, fmt->name,
+							    renderer, "markup",
+							    col_idx++, NULL);
+	}
+
+	/* construct merged column header since sort keys share single column */
+	buf[0] = '\0';
+	hists__for_each_format(hists ,fmt) {
+		if (!perf_hpp__is_sort_entry(fmt) &&
+		    !perf_hpp__is_dynamic_entry(fmt))
+			continue;
+
+		if (first)
+			first = false;
+		else
+			strcat(buf, " / ");
+
+		fmt->header(fmt, &hpp, hists_to_evsel(hists));
+		strcat(buf, rtrim(hpp.buf));
+	}
+
+	gtk_tree_view_insert_column_with_attributes(GTK_TREE_VIEW(view),
+						    -1, buf,
+						    renderer, "markup",
+						    col_idx++, NULL);
+
+	for (col_idx = 0; col_idx < nr_cols; col_idx++) {
+		GtkTreeViewColumn *column;
+
+		column = gtk_tree_view_get_column(GTK_TREE_VIEW(view), col_idx);
+		gtk_tree_view_column_set_resizable(column, TRUE);
+
+		if (col_idx == 0) {
+			gtk_tree_view_set_expander_column(GTK_TREE_VIEW(view),
+							  column);
+		}
+	}
+
+	gtk_tree_view_set_model(GTK_TREE_VIEW(view), GTK_TREE_MODEL(store));
+	g_object_unref(GTK_TREE_MODEL(store));
+
+	perf_gtk__add_hierarchy_entries(hists, &hists->entries, store,
+					NULL, &hpp, min_pcnt);
+
+	gtk_tree_view_set_rules_hint(GTK_TREE_VIEW(view), TRUE);
+
+	g_signal_connect(view, "row-activated",
+			 G_CALLBACK(on_row_activated), NULL);
+	gtk_container_add(GTK_CONTAINER(window), view);
+}
+
 int perf_evlist__gtk_browse_hists(struct perf_evlist *evlist,
 				  const char *help,
 				  struct hist_browser_timer *hbt __maybe_unused,
@@ -463,7 +619,10 @@ int perf_evlist__gtk_browse_hists(struct perf_evlist *evlist,
 							GTK_POLICY_AUTOMATIC,
 							GTK_POLICY_AUTOMATIC);
 
-		perf_gtk__show_hists(scrolled_window, hists, min_pcnt);
+		if (symbol_conf.report_hierarchy)
+			perf_gtk__show_hierarchy(scrolled_window, hists, min_pcnt);
+		else
+			perf_gtk__show_hists(scrolled_window, hists, min_pcnt);
 
 		tab_label = gtk_label_new(evname);
 
-- 
2.7.0

[PATCH 21/23] perf report: Add --hierarchy option

[Namhyung Kim]

The --hierarchy option is to show output in hierarchy mode.  It extends
folding/unfolding in the TUI and GTK browsers to support sort items as
well as callchains.  Users can toggle the items to see the performance
result at wanted level.

  $ perf report --hierarchy --tui
   Overhead        Command / Shared Object / Symbol
  +  32.96%        gnome-shell
  -  15.11%        swapper
     -  14.97%        [kernel.vmlinux]
            6.82%        [k] intel_idle
	    0.66%        [k] menu_select
	    0.43%        [k] __hrtimer_start_range_ns
  ...

Acked-by: Pekka Enberg <penberg@kernel.org>
Signed-off-by: Namhyung Kim <namhyung@kernel.org>
---
 tools/perf/Documentation/perf-report.txt |  3 +++
 tools/perf/Documentation/tips.txt        |  1 +
 tools/perf/builtin-report.c              | 17 +++++++++++++++++
 3 files changed, 21 insertions(+)

diff --git a/tools/perf/Documentation/perf-report.txt b/tools/perf/Documentation/perf-report.txt
index 89cab84e92fd..12113992ac9d 100644
--- a/tools/perf/Documentation/perf-report.txt
+++ b/tools/perf/Documentation/perf-report.txt
@@ -401,6 +401,9 @@ include::itrace.txt[]
 --raw-trace::
 	When displaying traceevent output, do not use print fmt or plugins.
 
+--hierarchy::
+	Enable hierarchical output.
+
 include::callchain-overhead-calculation.txt[]
 
 SEE ALSO
diff --git a/tools/perf/Documentation/tips.txt b/tools/perf/Documentation/tips.txt
index e0ce9573b79b..5950b5a24efd 100644
--- a/tools/perf/Documentation/tips.txt
+++ b/tools/perf/Documentation/tips.txt
@@ -27,3 +27,4 @@ Skip collecing build-id when recording: perf record -B
 To change sampling frequency to 100 Hz: perf record -F 100
 See assembly instructions with percentage: perf annotate <symbol>
 If you prefer Intel style assembly, try: perf annotate -M intel
+For hierarchical output, try: perf report --hierarchy
diff --git a/tools/perf/builtin-report.c b/tools/perf/builtin-report.c
index 760e886ca9d9..f4d8244449ca 100644
--- a/tools/perf/builtin-report.c
+++ b/tools/perf/builtin-report.c
@@ -811,6 +811,8 @@ int cmd_report(int argc, const char **argv, const char *prefix __maybe_unused)
 		    "only show processor socket that match with this filter"),
 	OPT_BOOLEAN(0, "raw-trace", &symbol_conf.raw_trace,
 		    "Show raw trace event output (do not use print fmt or plugins)"),
+	OPT_BOOLEAN(0, "hierarchy", &symbol_conf.report_hierarchy,
+		    "Show entries in a hierarchy"),
 	OPT_END()
 	};
 	struct perf_data_file file = {
@@ -920,6 +922,21 @@ repeat:
 		symbol_conf.cumulate_callchain = false;
 	}
 
+	if (symbol_conf.report_hierarchy) {
+		/* disable incompatible options */
+		symbol_conf.event_group = false;
+		symbol_conf.cumulate_callchain = false;
+
+		if (field_order) {
+			pr_err("Error: --hierarchy and --fields options cannot be used together\n");
+			parse_options_usage(report_usage, options, "F", 1);
+			parse_options_usage(NULL, options, "hierarchy", 0);
+			goto error;
+		}
+
+		sort__need_collapse = true;
+	}
+
 	/* Force tty output for header output and per-thread stat. */
 	if (report.header || report.header_only || report.show_threads)
 		use_browser = 0;
-- 
2.7.0

[PATCH 22/23] perf hists: Support decaying in hierarchy mode

[Namhyung Kim]

In the hierarchy mode, hist entries should decay their children too.
Also update hists__delete_entry() to be able to free child entries.

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

diff --git a/tools/perf/util/hist.c b/tools/perf/util/hist.c
index a9ba90baac62..4d81f29966ef 100644
--- a/tools/perf/util/hist.c
+++ b/tools/perf/util/hist.c
@@ -245,6 +245,8 @@ static void he_stat__decay(struct he_stat *he_stat)
 	/* XXX need decay for weight too? */
 }
 
+static void hists__delete_entry(struct hists *hists, struct hist_entry *he);
+
 static bool hists__decay_entry(struct hists *hists, struct hist_entry *he)
 {
 	u64 prev_period = he->stat.period;
@@ -260,21 +262,45 @@ static bool hists__decay_entry(struct hists *hists, struct hist_entry *he)
 
 	diff = prev_period - he->stat.period;
 
-	hists->stats.total_period -= diff;
-	if (!he->filtered)
-		hists->stats.total_non_filtered_period -= diff;
+	if (!he->depth) {
+		hists->stats.total_period -= diff;
+		if (!he->filtered)
+			hists->stats.total_non_filtered_period -= diff;
+	}
+
+	if (!he->leaf) {
+		struct hist_entry *child;
+		struct rb_node *node = rb_first(&he->hroot_out);
+		while (node) {
+			child = rb_entry(node, struct hist_entry, rb_node);
+			node = rb_next(node);
+
+			if (hists__decay_entry(hists, child))
+				hists__delete_entry(hists, child);
+		}
+	}
 
 	return he->stat.period == 0;
 }
 
 static void hists__delete_entry(struct hists *hists, struct hist_entry *he)
 {
-	rb_erase(&he->rb_node, &hists->entries);
+	struct rb_root *root_in;
+	struct rb_root *root_out;
 
-	if (sort__need_collapse)
-		rb_erase(&he->rb_node_in, &hists->entries_collapsed);
-	else
-		rb_erase(&he->rb_node_in, hists->entries_in);
+	if (he->parent_he) {
+		root_in  = &he->parent_he->hroot_in;
+		root_out = &he->parent_he->hroot_out;
+	} else {
+		if (sort__need_collapse)
+			root_in = &hists->entries_collapsed;
+		else
+			root_in = hists->entries_in;
+		root_out = &hists->entries;
+	}
+
+	rb_erase(&he->rb_node_in, root_in);
+	rb_erase(&he->rb_node, root_out);
 
 	--hists->nr_entries;
 	if (!he->filtered)
-- 
2.7.0

[PATCH 23/23] perf top: Add --hierarchy option

[Namhyung Kim]

Support hierarchy output for perf-top using --hierarchy option.

Acked-by: Pekka Enberg <penberg@kernel.org>
Signed-off-by: Namhyung Kim <namhyung@kernel.org>
---
 tools/perf/Documentation/perf-top.txt |  3 +++
 tools/perf/builtin-top.c              | 15 +++++++++++++++
 2 files changed, 18 insertions(+)

diff --git a/tools/perf/Documentation/perf-top.txt b/tools/perf/Documentation/perf-top.txt
index b0e60e17db38..19f046f027cd 100644
--- a/tools/perf/Documentation/perf-top.txt
+++ b/tools/perf/Documentation/perf-top.txt
@@ -233,6 +233,9 @@ Default is to monitor all CPUS.
 --raw-trace::
 	When displaying traceevent output, do not use print fmt or plugins.
 
+--hierarchy::
+	Enable hierarchy output.
+
 INTERACTIVE PROMPTING KEYS
 --------------------------
 
diff --git a/tools/perf/builtin-top.c b/tools/perf/builtin-top.c
index a75de3940b97..b86b623e8799 100644
--- a/tools/perf/builtin-top.c
+++ b/tools/perf/builtin-top.c
@@ -1214,6 +1214,8 @@ int cmd_top(int argc, const char **argv, const char *prefix __maybe_unused)
 		     parse_branch_stack),
 	OPT_BOOLEAN(0, "raw-trace", &symbol_conf.raw_trace,
 		    "Show raw trace event output (do not use print fmt or plugins)"),
+	OPT_BOOLEAN(0, "hierarchy", &symbol_conf.report_hierarchy,
+		    "Show entries in a hierarchy"),
 	OPT_END()
 	};
 	const char * const top_usage[] = {
@@ -1241,6 +1243,19 @@ int cmd_top(int argc, const char **argv, const char *prefix __maybe_unused)
 		goto out_delete_evlist;
 	}
 
+	if (symbol_conf.report_hierarchy) {
+		/* disable incompatible options */
+		symbol_conf.event_group = false;
+		symbol_conf.cumulate_callchain = false;
+
+		if (field_order) {
+			pr_err("Error: --hierarchy and --fields options cannot be used together\n");
+			parse_options_usage(top_usage, options, "fields", 0);
+			parse_options_usage(NULL, options, "hierarchy", 0);
+			goto out_delete_evlist;
+		}
+	}
+
 	sort__mode = SORT_MODE__TOP;
 	/* display thread wants entries to be collapsed in a different tree */
 	sort__need_collapse = 1;
-- 
2.7.0

Re: [PATCH 14/23] perf ui/stdio: Implement hierarchy output mode

[Jiri Olsa]

On Fri, Feb 05, 2016 at 10:01:46PM +0900, Namhyung Kim wrote:
> The hierarchy output mode is to group entries for each level so that
> user can see higher level picture more easily.  It also helps to find
> out which component is most costly.  The output will look like below:
> 
>       15.11%     swapper
>          14.97%     [kernel.vmlinux]
>           0.09%     [libahci]
>           0.05%     [iwlwifi]
>       10.29%     irq/33-iwlwifi
>           6.45%     [kernel.vmlinux]
>           1.41%     [mac80211]
>           1.15%     [iwldvm]
>           1.14%     [iwlwifi]
>           0.14%     [cfg80211]
>        4.81%     firefox
>           3.92%     libxul.so
>           0.34%     [kernel.vmlinux]
> 
> Acked-by: Pekka Enberg <penberg@kernel.org>
> Signed-off-by: Namhyung Kim <namhyung@kernel.org>
> ---
>  tools/perf/ui/hist.c       | 14 +++++++++
>  tools/perf/ui/stdio/hist.c | 77 +++++++++++++++++++++++++++++++++++++++++++++-
>  tools/perf/util/hist.h     |  4 +++
>  3 files changed, 94 insertions(+), 1 deletion(-)
> 
> diff --git a/tools/perf/ui/hist.c b/tools/perf/ui/hist.c
> index 1ba4117d9c2d..c398ce288615 100644
> --- a/tools/perf/ui/hist.c
> +++ b/tools/perf/ui/hist.c
> @@ -687,3 +687,17 @@ void perf_hpp__set_user_width(const char *width_list_str)
>  			break;
>  	}
>  }
> +
> +int perf_hpp__count_sort_keys(void)
> +{
> +	int nr_sort = 0;
> +	struct perf_hpp_fmt *fmt;
> +
> +	perf_hpp_list__for_each_format(&perf_hpp_list, fmt) {
> +		if (perf_hpp__is_sort_entry(fmt) ||
> +		    perf_hpp__is_dynamic_entry(fmt))
> +			nr_sort++;
> +	}
> +
> +	return nr_sort;
> +}

hum, this seems expensive..  also we should do that
in generic way per perf_hpp_list struct

we could hold number of sort entries in struct perf_hpp_list
and count it in:
  perf_hpp_list__register_sort_field

thanks,
jirka

Re: [PATCH 23/23] perf top: Add --hierarchy option

[Jiri Olsa]

On Fri, Feb 05, 2016 at 10:01:55PM +0900, Namhyung Kim wrote:
> Support hierarchy output for perf-top using --hierarchy option.
> 
> Acked-by: Pekka Enberg <penberg@kernel.org>
> Signed-off-by: Namhyung Kim <namhyung@kernel.org>
> ---
>  tools/perf/Documentation/perf-top.txt |  3 +++
>  tools/perf/builtin-top.c              | 15 +++++++++++++++
>  2 files changed, 18 insertions(+)
> 
> diff --git a/tools/perf/Documentation/perf-top.txt b/tools/perf/Documentation/perf-top.txt
> index b0e60e17db38..19f046f027cd 100644
> --- a/tools/perf/Documentation/perf-top.txt
> +++ b/tools/perf/Documentation/perf-top.txt
> @@ -233,6 +233,9 @@ Default is to monitor all CPUS.
>  --raw-trace::
>  	When displaying traceevent output, do not use print fmt or plugins.
>  
> +--hierarchy::
> +	Enable hierarchy output.
> +
>  INTERACTIVE PROMPTING KEYS
>  --------------------------
>  
> diff --git a/tools/perf/builtin-top.c b/tools/perf/builtin-top.c
> index a75de3940b97..b86b623e8799 100644
> --- a/tools/perf/builtin-top.c
> +++ b/tools/perf/builtin-top.c
> @@ -1214,6 +1214,8 @@ int cmd_top(int argc, const char **argv, const char *prefix __maybe_unused)
>  		     parse_branch_stack),
>  	OPT_BOOLEAN(0, "raw-trace", &symbol_conf.raw_trace,
>  		    "Show raw trace event output (do not use print fmt or plugins)"),
> +	OPT_BOOLEAN(0, "hierarchy", &symbol_conf.report_hierarchy,
> +		    "Show entries in a hierarchy"),
>  	OPT_END()
>  	};
>  	const char * const top_usage[] = {
> @@ -1241,6 +1243,19 @@ int cmd_top(int argc, const char **argv, const char *prefix __maybe_unused)
>  		goto out_delete_evlist;
>  	}
>  
> +	if (symbol_conf.report_hierarchy) {
> +		/* disable incompatible options */
> +		symbol_conf.event_group = false;
> +		symbol_conf.cumulate_callchain = false;
> +
> +		if (field_order) {
> +			pr_err("Error: --hierarchy and --fields options cannot be used together\n");
> +			parse_options_usage(top_usage, options, "fields", 0);
> +			parse_options_usage(NULL, options, "hierarchy", 0);
> +			goto out_delete_evlist;
> +		}
> +	}

I was wondering about this when I was going through the patchset ;-)

jirka

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

[Jiri Olsa]

On Fri, Feb 05, 2016 at 10:01:45PM +0900, Namhyung Kim wrote:

SNIP

> +			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) {

slightly confused in here.. so ret == 1 means we matched
but for example hist_entry__sym_filter:

+       return sym && (!he->ms.sym || !strstr(he->ms.sym->name, sym));

returns 1 if we DONT match the symbol

I always got confused by non/filtered stuff.. I think we should change
the those names, but haven't come with anything so far..

jirka

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

[Jiri Olsa]

On Fri, Feb 05, 2016 at 10:01:45PM +0900, Namhyung Kim wrote:

SNIP

> +			/* 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);
> +	}

what's the purpose of this resort? the only affect I see
is to recalculate callchains

thanks,
jirka

Re: [PATCH 14/23] perf ui/stdio: Implement hierarchy output mode

[Jiri Olsa]

On Fri, Feb 05, 2016 at 10:01:46PM +0900, Namhyung Kim wrote:

SNIP

> +	printed += fprintf(fp, "%s\n", buf);
> +
> +	if (symbol_conf.use_callchain && he->leaf) {
> +		u64 total = hists__total_period(hists);
> +
> +		printed += hist_entry_callchain__fprintf(he, total, 0, fp);
> +		goto out;
> +	}
> +
> +out:
> +	return printed;
> +}
> +
>  static int hist_entry__fprintf(struct hist_entry *he, size_t size,
>  			       struct hists *hists,
>  			       char *bf, size_t bfsz, FILE *fp)
> @@ -423,6 +488,13 @@ static int hist_entry__fprintf(struct hist_entry *he, size_t size,
>  	if (size == 0 || size > bfsz)
>  		size = hpp.size = bfsz;
>  
> +	if (symbol_conf.report_hierarchy) {

it'd be great for review to have symbol_conf.report_hierarchy already
present, so I could try it early in the patchset like with this change

jirka

Re: [PATCH 14/23] perf ui/stdio: Implement hierarchy output mode

[Jiri Olsa]

On Fri, Feb 05, 2016 at 10:01:46PM +0900, Namhyung Kim wrote:

SNIP

>  
> -	for (nd = rb_first(&hists->entries); nd; nd = rb_next(nd)) {
> +	for (nd = rb_first(&hists->entries); nd; nd = rb_hierarchy_next(nd)) {
>  		struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
>  		float percent;
>  
> @@ -542,6 +614,9 @@ print_entries:
>  						   MAP__FUNCTION, fp);
>  			fprintf(fp, "%.10s end\n", graph_dotted_line);
>  		}
> +
> +		if (symbol_conf.report_hierarchy)
> +			h->unfolded = true;

what's this for?

thanks,
jirka

Re: [PATCH 14/23] perf ui/stdio: Implement hierarchy output mode

[Jiri Olsa]

On Wed, Feb 10, 2016 at 01:23:45PM +0100, Jiri Olsa wrote:
> On Fri, Feb 05, 2016 at 10:01:46PM +0900, Namhyung Kim wrote:
> 
> SNIP
> 
> >  
> > -	for (nd = rb_first(&hists->entries); nd; nd = rb_next(nd)) {
> > +	for (nd = rb_first(&hists->entries); nd; nd = rb_hierarchy_next(nd)) {
> >  		struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
> >  		float percent;
> >  
> > @@ -542,6 +614,9 @@ print_entries:
> >  						   MAP__FUNCTION, fp);
> >  			fprintf(fp, "%.10s end\n", graph_dotted_line);
> >  		}
> > +
> > +		if (symbol_conf.report_hierarchy)
> > +			h->unfolded = true;
> 
> what's this for?
> 

ah it's stdio, we need to show everything.. ok ;-)

I was thinking of putting this 'force un/fold' logic into the
rb_hierarchy_next interface, because it's also not nice in
hists__filter_hierarchy function..

maybe having extra argument telling the walk preference
would be easier to read, like:

  rb_hierarchy_next(&h->rb_node, FORCE_UNFOLD);
  rb_hierarchy_next(&h->rb_node, FORCE_FOLD);
  rb_hierarchy_next(&h->rb_node, DEFAULT);

with some better names of course

just an idea.. it might turn horrible as well ;-)

thanks,
jirka

Re: [PATCH 15/23] perf ui/stdio: Align column header for hierarchy output

[Jiri Olsa]

On Fri, Feb 05, 2016 at 10:01:47PM +0900, Namhyung Kim wrote:
> The hierarchy output mode is to group entries so the existing columns
> won't fit to the new output.  Treat all sort keys as a single column and
> separate headers by "/".
> 
>   #    Overhead  Command / Shared Object
>   # ...........  ................................
>   #
>       15.11%     swapper
>          14.97%     [kernel.vmlinux]
>           0.09%     [libahci]
>           0.05%     [iwlwifi]
>   ...
> 
> Acked-by: Pekka Enberg <penberg@kernel.org>
> Signed-off-by: Namhyung Kim <namhyung@kernel.org>
> ---
>  tools/perf/ui/stdio/hist.c | 107 +++++++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 107 insertions(+)
> 
> diff --git a/tools/perf/ui/stdio/hist.c b/tools/perf/ui/stdio/hist.c
> index b58f718a6afc..4bdab3cf1b6c 100644
> --- a/tools/perf/ui/stdio/hist.c
> +++ b/tools/perf/ui/stdio/hist.c
> @@ -505,6 +505,108 @@ static int hist_entry__fprintf(struct hist_entry *he, size_t size,
>  	return ret;
>  }
>  
> +static int print_hierarchy_indent(const char *sep, int nr_sort,
> +				  const char *line, FILE *fp)
> +{
> +	if (sep != NULL || nr_sort < 1)
> +		return 0;
> +
> +	return fprintf(fp, "%-.*s", (nr_sort - 1) * HIERARCHY_INDENT, line);

hum, could you use   fprintf(fp, "%*c", nr_sort..., '.');

with the same effect to get rid of those dots and spaces strings..

jirka

> +}
> +
> +static int print_hierarchy_header(struct hists *hists, struct perf_hpp *hpp,
> +				  const char *sep, FILE *fp)
> +{
> +	bool first = true;
> +	int nr_sort;
> +	unsigned width = 0;
> +	unsigned header_width = 0;
> +	struct perf_hpp_fmt *fmt;
> +	const char spaces[] = "                                               "
> +	"                                                                     "
> +	"                                                                     ";
> +	const char dots[] = "................................................."
> +	"....................................................................."
> +	".....................................................................";

SNIP

Re: [PATCH 16/23] perf hists browser: Count number of hierarchy entries

[Jiri Olsa]

On Fri, Feb 05, 2016 at 10:01:48PM +0900, Namhyung Kim wrote:

SNIP

> +static int hierarchy_count_rows(struct hist_browser *hb, struct hist_entry *he,
> +				bool include_children)
> +{
> +	int count = 0;
> +	struct rb_node *node;
> +	struct hist_entry *child;
> +
> +	if (he->leaf)
> +		return callchain__count_rows(&he->sorted_chain);
> +
> +	node = rb_first(&he->hroot_out);
> +	while (node) {
> +		float percent;
> +
> +		child = rb_entry(node, struct hist_entry, rb_node);
> +		percent = hist_entry__get_percent_limit(child);
> +
> +		if (!child->filtered && percent >= hb->min_pcnt) {
> +			count++;
> +
> +			if (include_children && child->unfolded)
> +				count += hierarchy_count_rows(hb, child, true);
> +		}
> +
> +		node = rb_next(node);
> +	}
> +	return count;
> +}

SNIP

> +		if (he->leaf)
> +			browser->nr_callchain_rows -= he->nr_rows;
>  		else
> +			browser->nr_hierarchy_entries -= he->nr_rows;
> +
> +		if (symbol_conf.report_hierarchy)
> +			child_rows = hierarchy_count_rows(browser, he, true);
> +
> +		if (he->unfolded) {
> +			if (he->leaf)
> +				he->nr_rows = callchain__count_rows(&he->sorted_chain);
> +			else
> +				he->nr_rows = hierarchy_count_rows(browser, he, false);

looks like above condition could go to just following call:

			he->nr_rows = hierarchy_count_rows(browser, he, false);

because there's same condtiion in the hierarchy_count_rows function

thanks,
jirka

Re: [PATCH 23/23] perf top: Add --hierarchy option

[Jiri Olsa]

On Tue, Feb 09, 2016 at 11:37:10PM +0100, Jiri Olsa wrote:
> On Fri, Feb 05, 2016 at 10:01:55PM +0900, Namhyung Kim wrote:
> > Support hierarchy output for perf-top using --hierarchy option.
> > 
> > Acked-by: Pekka Enberg <penberg@kernel.org>
> > Signed-off-by: Namhyung Kim <namhyung@kernel.org>
> > ---
> >  tools/perf/Documentation/perf-top.txt |  3 +++
> >  tools/perf/builtin-top.c              | 15 +++++++++++++++
> >  2 files changed, 18 insertions(+)
> > 
> > diff --git a/tools/perf/Documentation/perf-top.txt b/tools/perf/Documentation/perf-top.txt
> > index b0e60e17db38..19f046f027cd 100644
> > --- a/tools/perf/Documentation/perf-top.txt
> > +++ b/tools/perf/Documentation/perf-top.txt
> > @@ -233,6 +233,9 @@ Default is to monitor all CPUS.
> >  --raw-trace::
> >  	When displaying traceevent output, do not use print fmt or plugins.
> >  
> > +--hierarchy::
> > +	Enable hierarchy output.
> > +
> >  INTERACTIVE PROMPTING KEYS
> >  --------------------------
> >  
> > diff --git a/tools/perf/builtin-top.c b/tools/perf/builtin-top.c
> > index a75de3940b97..b86b623e8799 100644
> > --- a/tools/perf/builtin-top.c
> > +++ b/tools/perf/builtin-top.c
> > @@ -1214,6 +1214,8 @@ int cmd_top(int argc, const char **argv, const char *prefix __maybe_unused)
> >  		     parse_branch_stack),
> >  	OPT_BOOLEAN(0, "raw-trace", &symbol_conf.raw_trace,
> >  		    "Show raw trace event output (do not use print fmt or plugins)"),
> > +	OPT_BOOLEAN(0, "hierarchy", &symbol_conf.report_hierarchy,
> > +		    "Show entries in a hierarchy"),
> >  	OPT_END()
> >  	};
> >  	const char * const top_usage[] = {
> > @@ -1241,6 +1243,19 @@ int cmd_top(int argc, const char **argv, const char *prefix __maybe_unused)
> >  		goto out_delete_evlist;
> >  	}
> >  
> > +	if (symbol_conf.report_hierarchy) {
> > +		/* disable incompatible options */
> > +		symbol_conf.event_group = false;
> > +		symbol_conf.cumulate_callchain = false;
> > +
> > +		if (field_order) {
> > +			pr_err("Error: --hierarchy and --fields options cannot be used together\n");
> > +			parse_options_usage(top_usage, options, "fields", 0);
> > +			parse_options_usage(NULL, options, "hierarchy", 0);
> > +			goto out_delete_evlist;
> > +		}
> > +	}
> 
> I was wondering about this when I was going through the patchset ;-)

but isn't that too restricting? hows about fields like
overhead_sys/us, samples, period 

jirka

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

[Namhyung Kim]

Hi Jiri,

2016-02-10 (수), 12:51 +0100, Jiri Olsa:
> On Fri, Feb 05, 2016 at 10:01:45PM +0900, Namhyung Kim wrote:
> 
> SNIP
> 
> > +			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) {
> 
> slightly confused in here.. so ret == 1 means we matched
> but for example hist_entry__sym_filter:
> 
> +       return sym && (!he->ms.sym || !strstr(he->ms.sym->name, sym));
> 
> returns 1 if we DONT match the symbol

Yes, this was confusing.  I meant it's a matching *type* but
the filter is not matched.


> 
> I always got confused by non/filtered stuff.. I think we should change
> the those names, but haven't come with anything so far..

Yeah, me too.. Filter can have both semantics - opt-in and opt-out.
It also made me hard to choose a good name.

Thanks,
Namhyung

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

[Namhyung Kim]

On Wed, Feb 10, 2016 at 01:11:19PM +0100, Jiri Olsa wrote:
> On Fri, Feb 05, 2016 at 10:01:45PM +0900, Namhyung Kim wrote:
> 
> SNIP
> 
> > +			/* 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);
> > +	}
> 
> what's the purpose of this resort? the only affect I see
> is to recalculate callchains

Filter can change parent entries' period so we need to resort after
applying a filter and this is why I pass 'false' for the
'use_callchain' param.

For example, let's say there're two top-level entries: A and B.  The A
has 40% overhead and the B has 30%.  But after applying filter the A
can have 10% and the B can have 15%.  So output should be changed to
put the B before the A.

I'll add a comment for this.

Thanks,
Namhyung

Re: [PATCH 14/23] perf ui/stdio: Implement hierarchy output mode

[Namhyung Kim]

On Tue, Feb 09, 2016 at 11:01:17PM +0100, Jiri Olsa wrote:
> On Fri, Feb 05, 2016 at 10:01:46PM +0900, Namhyung Kim wrote:
> > The hierarchy output mode is to group entries for each level so that
> > user can see higher level picture more easily.  It also helps to find
> > out which component is most costly.  The output will look like below:
> > 
> >       15.11%     swapper
> >          14.97%     [kernel.vmlinux]
> >           0.09%     [libahci]
> >           0.05%     [iwlwifi]
> >       10.29%     irq/33-iwlwifi
> >           6.45%     [kernel.vmlinux]
> >           1.41%     [mac80211]
> >           1.15%     [iwldvm]
> >           1.14%     [iwlwifi]
> >           0.14%     [cfg80211]
> >        4.81%     firefox
> >           3.92%     libxul.so
> >           0.34%     [kernel.vmlinux]
> > 
> > Acked-by: Pekka Enberg <penberg@kernel.org>
> > Signed-off-by: Namhyung Kim <namhyung@kernel.org>
> > ---
> >  tools/perf/ui/hist.c       | 14 +++++++++
> >  tools/perf/ui/stdio/hist.c | 77 +++++++++++++++++++++++++++++++++++++++++++++-
> >  tools/perf/util/hist.h     |  4 +++
> >  3 files changed, 94 insertions(+), 1 deletion(-)
> > 
> > diff --git a/tools/perf/ui/hist.c b/tools/perf/ui/hist.c
> > index 1ba4117d9c2d..c398ce288615 100644
> > --- a/tools/perf/ui/hist.c
> > +++ b/tools/perf/ui/hist.c
> > @@ -687,3 +687,17 @@ void perf_hpp__set_user_width(const char *width_list_str)
> >  			break;
> >  	}
> >  }
> > +
> > +int perf_hpp__count_sort_keys(void)
> > +{
> > +	int nr_sort = 0;
> > +	struct perf_hpp_fmt *fmt;
> > +
> > +	perf_hpp_list__for_each_format(&perf_hpp_list, fmt) {
> > +		if (perf_hpp__is_sort_entry(fmt) ||
> > +		    perf_hpp__is_dynamic_entry(fmt))
> > +			nr_sort++;
> > +	}
> > +
> > +	return nr_sort;
> > +}
> 
> hum, this seems expensive..  also we should do that
> in generic way per perf_hpp_list struct

OK.  But this is not called frequently though..

> 
> we could hold number of sort entries in struct perf_hpp_list
> and count it in:
>   perf_hpp_list__register_sort_field

OK.

Thanks,
Namhyung

Re: [PATCH 14/23] perf ui/stdio: Implement hierarchy output mode

[Namhyung Kim]

On Wed, Feb 10, 2016 at 01:13:35PM +0100, Jiri Olsa wrote:
> On Fri, Feb 05, 2016 at 10:01:46PM +0900, Namhyung Kim wrote:
> 
> SNIP
> 
> > +	printed += fprintf(fp, "%s\n", buf);
> > +
> > +	if (symbol_conf.use_callchain && he->leaf) {
> > +		u64 total = hists__total_period(hists);
> > +
> > +		printed += hist_entry_callchain__fprintf(he, total, 0, fp);
> > +		goto out;
> > +	}
> > +
> > +out:
> > +	return printed;
> > +}
> > +
> >  static int hist_entry__fprintf(struct hist_entry *he, size_t size,
> >  			       struct hists *hists,
> >  			       char *bf, size_t bfsz, FILE *fp)
> > @@ -423,6 +488,13 @@ static int hist_entry__fprintf(struct hist_entry *he, size_t size,
> >  	if (size == 0 || size > bfsz)
> >  		size = hpp.size = bfsz;
> >  
> > +	if (symbol_conf.report_hierarchy) {
> 
> it'd be great for review to have symbol_conf.report_hierarchy already
> present, so I could try it early in the patchset like with this change

I'm okay with it and that's what I do during the development.  But
introducing the option prior to implementing all feature/UI caused
some troubles/crashes.  So I put it after the implementation.

Thanks,
Namhyung

Re: [PATCH 14/23] perf ui/stdio: Implement hierarchy output mode

[Namhyung Kim]

On Wed, Feb 10, 2016 at 01:29:31PM +0100, Jiri Olsa wrote:
> On Wed, Feb 10, 2016 at 01:23:45PM +0100, Jiri Olsa wrote:
> > On Fri, Feb 05, 2016 at 10:01:46PM +0900, Namhyung Kim wrote:
> > 
> > SNIP
> > 
> > >  
> > > -	for (nd = rb_first(&hists->entries); nd; nd = rb_next(nd)) {
> > > +	for (nd = rb_first(&hists->entries); nd; nd = rb_hierarchy_next(nd)) {
> > >  		struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
> > >  		float percent;
> > >  
> > > @@ -542,6 +614,9 @@ print_entries:
> > >  						   MAP__FUNCTION, fp);
> > >  			fprintf(fp, "%.10s end\n", graph_dotted_line);
> > >  		}
> > > +
> > > +		if (symbol_conf.report_hierarchy)
> > > +			h->unfolded = true;
> > 
> > what's this for?
> > 
> 
> ah it's stdio, we need to show everything.. ok ;-)

Right. :)

> 
> I was thinking of putting this 'force un/fold' logic into the
> rb_hierarchy_next interface, because it's also not nice in
> hists__filter_hierarchy function..
> 
> maybe having extra argument telling the walk preference
> would be easier to read, like:
> 
>   rb_hierarchy_next(&h->rb_node, FORCE_UNFOLD);
>   rb_hierarchy_next(&h->rb_node, FORCE_FOLD);
>   rb_hierarchy_next(&h->rb_node, DEFAULT);
> 
> with some better names of course
> 
> just an idea.. it might turn horrible as well ;-)

Seems like a good idea.  I'll think about it in the next spin.

Thanks,
Namhyung

Re: [PATCH 15/23] perf ui/stdio: Align column header for hierarchy output

[Namhyung Kim]

On Wed, Feb 10, 2016 at 01:40:03PM +0100, Jiri Olsa wrote:
> On Fri, Feb 05, 2016 at 10:01:47PM +0900, Namhyung Kim wrote:
> > The hierarchy output mode is to group entries so the existing columns
> > won't fit to the new output.  Treat all sort keys as a single column and
> > separate headers by "/".
> > 
> >   #    Overhead  Command / Shared Object
> >   # ...........  ................................
> >   #
> >       15.11%     swapper
> >          14.97%     [kernel.vmlinux]
> >           0.09%     [libahci]
> >           0.05%     [iwlwifi]
> >   ...
> > 
> > Acked-by: Pekka Enberg <penberg@kernel.org>
> > Signed-off-by: Namhyung Kim <namhyung@kernel.org>
> > ---
> >  tools/perf/ui/stdio/hist.c | 107 +++++++++++++++++++++++++++++++++++++++++++++
> >  1 file changed, 107 insertions(+)
> > 
> > diff --git a/tools/perf/ui/stdio/hist.c b/tools/perf/ui/stdio/hist.c
> > index b58f718a6afc..4bdab3cf1b6c 100644
> > --- a/tools/perf/ui/stdio/hist.c
> > +++ b/tools/perf/ui/stdio/hist.c
> > @@ -505,6 +505,108 @@ static int hist_entry__fprintf(struct hist_entry *he, size_t size,
> >  	return ret;
> >  }
> >  
> > +static int print_hierarchy_indent(const char *sep, int nr_sort,
> > +				  const char *line, FILE *fp)
> > +{
> > +	if (sep != NULL || nr_sort < 1)
> > +		return 0;
> > +
> > +	return fprintf(fp, "%-.*s", (nr_sort - 1) * HIERARCHY_INDENT, line);
> 
> hum, could you use   fprintf(fp, "%*c", nr_sort..., '.');
> 
> with the same effect to get rid of those dots and spaces strings..

Is it possible?  I already tried but it failed with the dots..

  $ cat dot.c
  #include <stdio.h>
  
  int main(void)
  {
    printf("%*c\n", 5, '.');
    return 0;
  }
  
  $ gcc dot.c
  $ ./a.out
      .
  $


Thanks,
Namhyung

Re: [PATCH 16/23] perf hists browser: Count number of hierarchy entries

[Namhyung Kim]

On Wed, Feb 10, 2016 at 01:52:08PM +0100, Jiri Olsa wrote:
> On Fri, Feb 05, 2016 at 10:01:48PM +0900, Namhyung Kim wrote:
> 
> SNIP
> 
> > +static int hierarchy_count_rows(struct hist_browser *hb, struct hist_entry *he,
> > +				bool include_children)
> > +{
> > +	int count = 0;
> > +	struct rb_node *node;
> > +	struct hist_entry *child;
> > +
> > +	if (he->leaf)
> > +		return callchain__count_rows(&he->sorted_chain);
> > +
> > +	node = rb_first(&he->hroot_out);
> > +	while (node) {
> > +		float percent;
> > +
> > +		child = rb_entry(node, struct hist_entry, rb_node);
> > +		percent = hist_entry__get_percent_limit(child);
> > +
> > +		if (!child->filtered && percent >= hb->min_pcnt) {
> > +			count++;
> > +
> > +			if (include_children && child->unfolded)
> > +				count += hierarchy_count_rows(hb, child, true);
> > +		}
> > +
> > +		node = rb_next(node);
> > +	}
> > +	return count;
> > +}
> 
> SNIP
> 
> > +		if (he->leaf)
> > +			browser->nr_callchain_rows -= he->nr_rows;
> >  		else
> > +			browser->nr_hierarchy_entries -= he->nr_rows;
> > +
> > +		if (symbol_conf.report_hierarchy)
> > +			child_rows = hierarchy_count_rows(browser, he, true);
> > +
> > +		if (he->unfolded) {
> > +			if (he->leaf)
> > +				he->nr_rows = callchain__count_rows(&he->sorted_chain);
> > +			else
> > +				he->nr_rows = hierarchy_count_rows(browser, he, false);
> 
> looks like above condition could go to just following call:
> 
> 			he->nr_rows = hierarchy_count_rows(browser, he, false);
> 
> because there's same condtiion in the hierarchy_count_rows function

That's true.  But I wrote it that way since it's aligned with other
part of the code.

Thanks,
Namhyung

Re: [PATCH 23/23] perf top: Add --hierarchy option

[Namhyung Kim]

On Wed, Feb 10, 2016 at 02:19:40PM +0100, Jiri Olsa wrote:
> On Tue, Feb 09, 2016 at 11:37:10PM +0100, Jiri Olsa wrote:
> > On Fri, Feb 05, 2016 at 10:01:55PM +0900, Namhyung Kim wrote:
> > > Support hierarchy output for perf-top using --hierarchy option.
> > > 
> > > Acked-by: Pekka Enberg <penberg@kernel.org>
> > > Signed-off-by: Namhyung Kim <namhyung@kernel.org>
> > > ---
> > >  tools/perf/Documentation/perf-top.txt |  3 +++
> > >  tools/perf/builtin-top.c              | 15 +++++++++++++++
> > >  2 files changed, 18 insertions(+)
> > > 
> > > diff --git a/tools/perf/Documentation/perf-top.txt b/tools/perf/Documentation/perf-top.txt
> > > index b0e60e17db38..19f046f027cd 100644
> > > --- a/tools/perf/Documentation/perf-top.txt
> > > +++ b/tools/perf/Documentation/perf-top.txt
> > > @@ -233,6 +233,9 @@ Default is to monitor all CPUS.
> > >  --raw-trace::
> > >  	When displaying traceevent output, do not use print fmt or plugins.
> > >  
> > > +--hierarchy::
> > > +	Enable hierarchy output.
> > > +
> > >  INTERACTIVE PROMPTING KEYS
> > >  --------------------------
> > >  
> > > diff --git a/tools/perf/builtin-top.c b/tools/perf/builtin-top.c
> > > index a75de3940b97..b86b623e8799 100644
> > > --- a/tools/perf/builtin-top.c
> > > +++ b/tools/perf/builtin-top.c
> > > @@ -1214,6 +1214,8 @@ int cmd_top(int argc, const char **argv, const char *prefix __maybe_unused)
> > >  		     parse_branch_stack),
> > >  	OPT_BOOLEAN(0, "raw-trace", &symbol_conf.raw_trace,
> > >  		    "Show raw trace event output (do not use print fmt or plugins)"),
> > > +	OPT_BOOLEAN(0, "hierarchy", &symbol_conf.report_hierarchy,
> > > +		    "Show entries in a hierarchy"),
> > >  	OPT_END()
> > >  	};
> > >  	const char * const top_usage[] = {
> > > @@ -1241,6 +1243,19 @@ int cmd_top(int argc, const char **argv, const char *prefix __maybe_unused)
> > >  		goto out_delete_evlist;
> > >  	}
> > >  
> > > +	if (symbol_conf.report_hierarchy) {
> > > +		/* disable incompatible options */
> > > +		symbol_conf.event_group = false;
> > > +		symbol_conf.cumulate_callchain = false;
> > > +
> > > +		if (field_order) {
> > > +			pr_err("Error: --hierarchy and --fields options cannot be used together\n");
> > > +			parse_options_usage(top_usage, options, "fields", 0);
> > > +			parse_options_usage(NULL, options, "hierarchy", 0);
> > > +			goto out_delete_evlist;
> > > +		}
> > > +	}
> > 
> > I was wondering about this when I was going through the patchset ;-)
> 
> but isn't that too restricting? hows about fields like
> overhead_sys/us, samples, period 

Allowing -F/--fields option cannot ensure the hierarchy mode working
correctly.  Those fields can be shown with following options anyway..

  -n, --show-nr-samples
                        Show a column with the number of samples
      --show-cpu-utilization
                        Show sample percentage for different cpu modes
      --show-total-period
                        Show a column with the sum of periods

Thanks,
Namhyung