LKML Archive on lore.kernel.org
help / color / mirror / Atom feed
From: Adrian Hunter <adrian.hunter@intel.com>
To: Peter Zijlstra <peterz@infradead.org>,
	Arnaldo Carvalho de Melo <acme@kernel.org>
Cc: linux-kernel@vger.kernel.org, David Ahern <dsahern@gmail.com>,
	Frederic Weisbecker <fweisbec@gmail.com>,
	Jiri Olsa <jolsa@redhat.com>, Namhyung Kim <namhyung@gmail.com>,
	Paul Mackerras <paulus@samba.org>,
	Stephane Eranian <eranian@google.com>,
	Alexander Shishkin <alexander.shishkin@linux.intel.com>,
	Andi Kleen <ak@linux.intel.com>
Subject: [PATCH V6 14/25] perf auxtrace: Add a hashtable for caching
Date: Mon, 16 Mar 2015 14:41:36 +0200	[thread overview]
Message-ID: <1426509707-24961-15-git-send-email-adrian.hunter@intel.com> (raw)
In-Reply-To: <1426509707-24961-1-git-send-email-adrian.hunter@intel.com>

Decoding AUX area data may involve walking object
code.  Rather than repetitively decoding the same
instructions, a cache can be used to cache the results.

This patch implements a fairly generic hashtable
with a 32-bit key that could be used for other
purposes as well.

Signed-off-by: Adrian Hunter <adrian.hunter@intel.com>
---
 tools/perf/util/auxtrace.c | 123 +++++++++++++++++++++++++++++++++++++++++++++
 tools/perf/util/auxtrace.h |  14 ++++++
 2 files changed, 137 insertions(+)

diff --git a/tools/perf/util/auxtrace.c b/tools/perf/util/auxtrace.c
index 1c49a6c..e1499c5 100644
--- a/tools/perf/util/auxtrace.c
+++ b/tools/perf/util/auxtrace.c
@@ -39,6 +39,8 @@
 #include "thread_map.h"
 #include "auxtrace.h"
 
+#include <linux/hash.h>
+
 #include "event.h"
 #include "session.h"
 #include "debug.h"
@@ -949,3 +951,124 @@ int auxtrace_mmap__read(struct auxtrace_mmap *mm, struct auxtrace_record *itr,
 
 	return 1;
 }
+
+/**
+ * struct auxtrace_cache - hash table to implement a cache
+ * @hashtable: the hashtable
+ * @sz: hashtable size (number of hlists)
+ * @entry_size: size of an entry
+ * @limit: limit the number of entries to this maximum, when reached the cache
+ *         is dropped and caching begins again with an empty cache
+ * @cnt: current number of entries
+ * @bits: hashtable size (@sz = 2^@bits)
+ */
+struct auxtrace_cache {
+	struct hlist_head *hashtable;
+	size_t sz;
+	size_t entry_size;
+	size_t limit;
+	size_t cnt;
+	unsigned int bits;
+};
+
+struct auxtrace_cache *auxtrace_cache__new(unsigned int bits, size_t entry_size,
+					   unsigned int limit_percent)
+{
+	struct auxtrace_cache *c;
+	struct hlist_head *ht;
+	size_t sz, i;
+
+	c = zalloc(sizeof(struct auxtrace_cache));
+	if (!c)
+		return NULL;
+
+	sz = 1UL << bits;
+
+	ht = calloc(sz, sizeof(struct hlist_head));
+	if (!ht)
+		goto out_free;
+
+	for (i = 0; i < sz; i++)
+		INIT_HLIST_HEAD(&ht[i]);
+
+	c->hashtable = ht;
+	c->sz = sz;
+	c->entry_size = entry_size;
+	c->limit = (c->sz * limit_percent) / 100;
+	c->bits = bits;
+
+	return c;
+
+out_free:
+	free(c);
+	return NULL;
+}
+
+static void auxtrace_cache__drop(struct auxtrace_cache *c)
+{
+	struct auxtrace_cache_entry *entry;
+	struct hlist_node *tmp;
+	size_t i;
+
+	if (!c)
+		return;
+
+	for (i = 0; i < c->sz; i++) {
+		hlist_for_each_entry_safe(entry, tmp, &c->hashtable[i], hash) {
+			hlist_del(&entry->hash);
+			auxtrace_cache__free_entry(c, entry);
+		}
+	}
+
+	c->cnt = 0;
+}
+
+void auxtrace_cache__free(struct auxtrace_cache *c)
+{
+	if (!c)
+		return;
+
+	auxtrace_cache__drop(c);
+	free(c->hashtable);
+	free(c);
+}
+
+void *auxtrace_cache__alloc_entry(struct auxtrace_cache *c)
+{
+	return malloc(c->entry_size);
+}
+
+void auxtrace_cache__free_entry(struct auxtrace_cache *c __maybe_unused,
+				void *entry)
+{
+	free(entry);
+}
+
+int auxtrace_cache__add(struct auxtrace_cache *c, u32 key,
+			struct auxtrace_cache_entry *entry)
+{
+	if (c->limit && ++c->cnt > c->limit)
+		auxtrace_cache__drop(c);
+
+	entry->key = key;
+	hlist_add_head(&entry->hash, &c->hashtable[hash_32(key, c->bits)]);
+
+	return 0;
+}
+
+void *auxtrace_cache__lookup(struct auxtrace_cache *c, u32 key)
+{
+	struct auxtrace_cache_entry *entry;
+	struct hlist_head *hlist;
+
+	if (!c)
+		return NULL;
+
+	hlist = &c->hashtable[hash_32(key, c->bits)];
+	hlist_for_each_entry(entry, hlist, hash) {
+		if (entry->key == key)
+			return entry;
+	}
+
+	return NULL;
+}
diff --git a/tools/perf/util/auxtrace.h b/tools/perf/util/auxtrace.h
index 882fb35..5dfa05a 100644
--- a/tools/perf/util/auxtrace.h
+++ b/tools/perf/util/auxtrace.h
@@ -313,6 +313,20 @@ int auxtrace_heap__add(struct auxtrace_heap *heap, unsigned int queue_nr,
 void auxtrace_heap__pop(struct auxtrace_heap *heap);
 void auxtrace_heap__free(struct auxtrace_heap *heap);
 
+struct auxtrace_cache_entry {
+	struct hlist_node hash;
+	u32 key;
+};
+
+struct auxtrace_cache *auxtrace_cache__new(unsigned int bits, size_t entry_size,
+					   unsigned int limit_percent);
+void auxtrace_cache__free(struct auxtrace_cache *auxtrace_cache);
+void *auxtrace_cache__alloc_entry(struct auxtrace_cache *c);
+void auxtrace_cache__free_entry(struct auxtrace_cache *c, void *entry);
+int auxtrace_cache__add(struct auxtrace_cache *c, u32 key,
+			struct auxtrace_cache_entry *entry);
+void *auxtrace_cache__lookup(struct auxtrace_cache *c, u32 key);
+
 struct auxtrace_record *auxtrace_record__init(struct perf_evlist *evlist,
 					      int *err);
 
-- 
1.9.1


  parent reply	other threads:[~2015-03-16 12:44 UTC|newest]

Thread overview: 33+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2015-03-16 12:41 [PATCH V6 00/25] perf tools: Introduce an abstraction for AUX Area and Instruction Tracing Adrian Hunter
2015-03-16 12:41 ` [PATCH V6 01/25] perf header: Add AUX area tracing feature Adrian Hunter
2015-03-16 12:41 ` [PATCH V6 02/25] perf evlist: Add initial support for mmapping an AUX area buffer Adrian Hunter
2015-03-24 11:07   ` Jiri Olsa
2015-03-31  9:09     ` Adrian Hunter
2015-03-24 11:07   ` Jiri Olsa
2015-03-16 12:41 ` [PATCH V6 03/25] perf tools: Add user events for AUX area tracing Adrian Hunter
2015-03-16 12:41 ` [PATCH V6 04/25] perf tools: Add support for AUX area recording Adrian Hunter
2015-03-24 11:07   ` Jiri Olsa
2015-03-24 11:07   ` Jiri Olsa
2015-03-16 12:41 ` [PATCH V6 05/25] perf record: Add basic AUX area tracing support Adrian Hunter
2015-03-24 11:07   ` Jiri Olsa
2015-03-16 12:41 ` [PATCH V6 06/25] perf record: Extend -m option for AUX area tracing mmap pages Adrian Hunter
2015-03-24 11:08   ` Jiri Olsa
2015-03-16 12:41 ` [PATCH V6 07/25] perf tools: Add a user event for AUX area tracing errors Adrian Hunter
2015-03-16 12:41 ` [PATCH V6 08/25] perf session: Add hooks to allow transparent decoding of AUX area tracing data Adrian Hunter
2015-03-16 12:41 ` [PATCH V6 09/25] perf session: Add instruction tracing options Adrian Hunter
2015-03-16 12:41 ` [PATCH V6 10/25] perf auxtrace: Add helpers for AUX area tracing errors Adrian Hunter
2015-03-16 12:41 ` [PATCH V6 11/25] perf auxtrace: Add helpers for queuing AUX area tracing data Adrian Hunter
2015-03-16 12:41 ` [PATCH V6 12/25] perf auxtrace: Add a heap for sorting AUX area tracing queues Adrian Hunter
2015-03-16 12:41 ` [PATCH V6 13/25] perf auxtrace: Add processing for AUX area tracing events Adrian Hunter
2015-03-16 12:41 ` Adrian Hunter [this message]
2015-03-16 12:41 ` [PATCH V6 15/25] perf tools: Add member to struct dso for an instruction cache Adrian Hunter
2015-03-16 12:41 ` [PATCH V6 16/25] perf script: Add Instruction Tracing support Adrian Hunter
2015-03-16 12:41 ` [PATCH V6 17/25] perf script: Always allow fields 'addr' and 'cpu' for auxtrace Adrian Hunter
2015-03-16 12:41 ` [PATCH V6 18/25] perf report: Add Instruction Tracing support Adrian Hunter
2015-03-16 12:41 ` [PATCH V6 19/25] perf inject: Re-pipe AUX area tracing events Adrian Hunter
2015-03-16 12:41 ` [PATCH V6 20/25] perf inject: Add Instruction Tracing support Adrian Hunter
2015-03-16 12:41 ` [PATCH V6 21/25] perf tools: Add AUX area tracing index Adrian Hunter
2015-03-16 12:41 ` [PATCH V6 22/25] perf tools: Hit all build ids when AUX area tracing Adrian Hunter
2015-03-16 12:41 ` [PATCH V6 23/25] perf tools: Add build option NO_AUXTRACE to exclude " Adrian Hunter
2015-03-16 12:41 ` [PATCH V6 24/25] perf auxtrace: Add option to synthesize events for transactions Adrian Hunter
2015-03-16 12:41 ` [PATCH V6 25/25] perf script: Add field option 'flags' to print sample flags Adrian Hunter

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=1426509707-24961-15-git-send-email-adrian.hunter@intel.com \
    --to=adrian.hunter@intel.com \
    --cc=acme@kernel.org \
    --cc=ak@linux.intel.com \
    --cc=alexander.shishkin@linux.intel.com \
    --cc=dsahern@gmail.com \
    --cc=eranian@google.com \
    --cc=fweisbec@gmail.com \
    --cc=jolsa@redhat.com \
    --cc=linux-kernel@vger.kernel.org \
    --cc=namhyung@gmail.com \
    --cc=paulus@samba.org \
    --cc=peterz@infradead.org \
    --subject='Re: [PATCH V6 14/25] perf auxtrace: Add a hashtable for caching' \
    /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).