LKML Archive on lore.kernel.org
help / color / mirror / Atom feed
From: Jin Yao <yao.jin@linux.intel.com>
To: acme@kernel.org, jolsa@kernel.org, peterz@infradead.org,
	mingo@redhat.com, alexander.shishkin@linux.intel.com
Cc: Linux-kernel@vger.kernel.org, ak@linux.intel.com,
	kan.liang@intel.com, yao.jin@intel.com,
	Jin Yao <yao.jin@linux.intel.com>
Subject: [PATCH v1 02/14] perf util: Create streams for managing top N hottest callchains
Date: Tue, 10 Mar 2020 15:02:33 +0800	[thread overview]
Message-ID: <20200310070245.16314-3-yao.jin@linux.intel.com> (raw)
In-Reply-To: <20200310070245.16314-1-yao.jin@linux.intel.com>

We think the stream is a callchain which is aggregated by the LBR
records from samples. By browsing the stream, we can understand
the code flow.

The struct callchain_node represents one callchain and we use the
callchain_node->hit to measure the hot level of this callchain.
Higher is hotter.

Since in perf data file, there may be many callchains so we just
need to focus on the top N hottest callchains. N is a user defined
parameter or just a predefined default value.

This patch saves the top N hottest callchains in 'struct stream_node'
type array, which is defined in a per event 'struct callchain_streams'.

So now we can get the per-event top N hottest callchains.

Signed-off-by: Jin Yao <yao.jin@linux.intel.com>
---
 tools/perf/util/callchain.c | 125 ++++++++++++++++++++++++++++++++++++
 tools/perf/util/callchain.h |  16 +++++
 2 files changed, 141 insertions(+)

diff --git a/tools/perf/util/callchain.c b/tools/perf/util/callchain.c
index 818aa4efd386..d9c68a8e7619 100644
--- a/tools/perf/util/callchain.c
+++ b/tools/perf/util/callchain.c
@@ -31,6 +31,7 @@
 #include "callchain.h"
 #include "branch.h"
 #include "symbol.h"
+#include "evlist.h"
 #include "../perf.h"
 
 #define CALLCHAIN_PARAM_DEFAULT			\
@@ -1599,3 +1600,127 @@ void callchain_cursor_reset(struct callchain_cursor *cursor)
 	for (node = cursor->first; node != NULL; node = node->next)
 		map__zput(node->ms.map);
 }
+
+static void free_evsel_streams(struct callchain_streams *callchain_streams,
+			       int nr_evsel)
+{
+	for (int i = 0; i < nr_evsel; i++) {
+		if (callchain_streams[i].streams)
+			free(callchain_streams[i].streams);
+	}
+
+	free(callchain_streams);
+}
+
+static struct callchain_streams *create_evsel_streams(int nr_evsel,
+						      int nr_streams_max)
+{
+	struct callchain_streams *callchain_streams;
+
+	callchain_streams = calloc(nr_evsel, sizeof(struct callchain_streams));
+	if (!callchain_streams)
+		return NULL;
+
+	for (int i = 0; i < nr_evsel; i++) {
+		struct callchain_streams *s = &callchain_streams[i];
+
+		s->streams = calloc(nr_streams_max, sizeof(struct stream_node));
+		if (!s->streams)
+			goto err;
+
+		s->nr_streams_max = nr_streams_max;
+		s->evsel_idx = -1;
+	}
+
+	return callchain_streams;
+
+err:
+	free_evsel_streams(callchain_streams, nr_evsel);
+	return NULL;
+}
+
+/*
+ * The cnodes with high hit number are hot callchains.
+ */
+static void set_hot_cnode(struct callchain_streams *s,
+			  struct callchain_node *cnode)
+{
+	int i, idx = 0;
+	u64 hit;
+
+	if (s->nr_streams < s->nr_streams_max) {
+		i = s->nr_streams;
+		s->streams[i].cnode = cnode;
+		s->nr_streams++;
+		return;
+	}
+
+	/*
+	 * Since only a few number of hot streams, so only use simple
+	 * way to find the cnode with smallest hit number and replace.
+	 */
+	hit = (s->streams[0].cnode)->hit;
+	for (i = 1; i < s->nr_streams; i++) {
+		if ((s->streams[i].cnode)->hit < hit) {
+			hit = (s->streams[i].cnode)->hit;
+			idx = i;
+		}
+	}
+
+	if (cnode->hit > hit)
+		s->streams[idx].cnode = cnode;
+}
+
+static void update_hot_streams(struct hist_entry *he,
+			       struct callchain_streams *s)
+{
+	struct rb_root *root = &he->sorted_chain;
+	struct rb_node *rb_node = rb_first(root);
+	struct callchain_node *node;
+
+	while (rb_node) {
+		node = rb_entry(rb_node, struct callchain_node, rb_node);
+		set_hot_cnode(s, node);
+		rb_node = rb_next(rb_node);
+	}
+}
+
+static void get_hot_streams(struct hists *hists,
+			    struct callchain_streams *s)
+{
+	struct rb_node *next;
+
+	next = rb_first_cached(&hists->entries);
+	while (next) {
+		struct hist_entry *he;
+
+		he = rb_entry(next, struct hist_entry, rb_node);
+		update_hot_streams(he, s);
+		next = rb_next(&he->rb_node);
+	}
+}
+
+struct callchain_streams *callchain_evsel_streams_create(struct evlist *evlist,
+							 int nr_streams_max,
+							 int *nr_evsel_streams)
+{
+	int nr_evsel = evlist->core.nr_entries, i = 0;
+	struct callchain_streams *callchain_streams;
+	struct evsel *pos;
+
+	callchain_streams = create_evsel_streams(nr_evsel, nr_streams_max);
+	if (!callchain_streams)
+		return NULL;
+
+	evlist__for_each_entry(evlist, pos) {
+		struct hists *hists = evsel__hists(pos);
+
+		hists__output_resort(hists, NULL);
+		get_hot_streams(hists, &callchain_streams[i]);
+		callchain_streams[i].evsel_idx = pos->idx;
+		i++;
+	}
+
+	*nr_evsel_streams = nr_evsel;
+	return callchain_streams;
+}
diff --git a/tools/perf/util/callchain.h b/tools/perf/util/callchain.h
index 706bb7bbe1e1..5852990cdf60 100644
--- a/tools/perf/util/callchain.h
+++ b/tools/perf/util/callchain.h
@@ -13,6 +13,7 @@ struct ip_callchain;
 struct map;
 struct perf_sample;
 struct thread;
+struct evlist;
 
 #define HELP_PAD "\t\t\t\t"
 
@@ -159,6 +160,17 @@ struct callchain_cursor {
 	struct callchain_cursor_node	*curr;
 };
 
+struct stream_node {
+	struct callchain_node	*cnode;
+};
+
+struct callchain_streams {
+	struct stream_node	*streams;
+	int			nr_streams_max;
+	int			nr_streams;
+	int			evsel_idx;
+};
+
 extern __thread struct callchain_cursor callchain_cursor;
 
 static inline void callchain_init(struct callchain_root *root)
@@ -289,4 +301,8 @@ int callchain_branch_counts(struct callchain_root *root,
 			    u64 *branch_count, u64 *predicted_count,
 			    u64 *abort_count, u64 *cycles_count);
 
+struct callchain_streams *callchain_evsel_streams_create(struct evlist *evlist,
+							 int nr_streams_max,
+							 int *nr_evsel_streams);
+
 #endif	/* __PERF_CALLCHAIN_H */
-- 
2.17.1


  parent reply	other threads:[~2020-03-10  7:03 UTC|newest]

Thread overview: 23+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2020-03-10  7:02 [PATCH v1 00/14] perf: Stream comparison Jin Yao
2020-03-10  7:02 ` [PATCH v1 01/14] perf util: Create source line mapping table Jin Yao
2020-03-10 15:08   ` Arnaldo Carvalho de Melo
2020-03-11  5:33     ` Jin, Yao
2020-03-10  7:02 ` Jin Yao [this message]
2020-03-10 15:11   ` [PATCH v1 02/14] perf util: Create streams for managing top N hottest callchains Arnaldo Carvalho de Melo
2020-03-11  5:38     ` Jin, Yao
2020-03-10  7:02 ` [PATCH v1 03/14] perf util: Return per-event callchain streams Jin Yao
2020-03-10  7:02 ` [PATCH v1 04/14] perf util: Compare two streams Jin Yao
2020-03-10  7:02 ` [PATCH v1 05/14] perf util: Calculate the sum of all streams hits Jin Yao
2020-03-10 15:14   ` Arnaldo Carvalho de Melo
2020-03-11  5:44     ` Jin, Yao
2020-03-10  7:02 ` [PATCH v1 06/14] perf util: Report hot streams Jin Yao
2020-03-10  7:02 ` [PATCH v1 07/14] perf diff: Support hot streams comparison Jin Yao
2020-03-10  7:02 ` [PATCH v1 08/14] perf util: Add new block info functions for top N hot blocks comparison Jin Yao
2020-03-10 15:17   ` Arnaldo Carvalho de Melo
2020-03-11  5:47     ` Jin, Yao
2020-03-10  7:02 ` [PATCH v1 09/14] perf util: Add new block info fmts for showing " Jin Yao
2020-03-10  7:02 ` [PATCH v1 10/14] perf util: Enable block source line comparison Jin Yao
2020-03-10  7:02 ` [PATCH v1 11/14] perf diff: support hot blocks comparison Jin Yao
2020-03-10  7:02 ` [PATCH v1 12/14] perf util: Filter out streams by name of changed functions Jin Yao
2020-03-10  7:02 ` [PATCH v1 13/14] perf util: Filter out blocks " Jin Yao
2020-03-10  7:02 ` [PATCH v1 14/14] perf diff: Filter out streams by " Jin Yao

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20200310070245.16314-3-yao.jin@linux.intel.com \
    --to=yao.jin@linux.intel.com \
    --cc=Linux-kernel@vger.kernel.org \
    --cc=acme@kernel.org \
    --cc=ak@linux.intel.com \
    --cc=alexander.shishkin@linux.intel.com \
    --cc=jolsa@kernel.org \
    --cc=kan.liang@intel.com \
    --cc=mingo@redhat.com \
    --cc=peterz@infradead.org \
    --cc=yao.jin@intel.com \
    --subject='Re: [PATCH v1 02/14] perf util: Create streams for managing top N hottest callchains' \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).