From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1756764AbbEFDCq (ORCPT ); Tue, 5 May 2015 23:02:46 -0400 Received: from terminus.zytor.com ([198.137.202.10]:35776 "EHLO terminus.zytor.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1756523AbbEFDCo (ORCPT ); Tue, 5 May 2015 23:02:44 -0400 Date: Tue, 5 May 2015 20:02:12 -0700 From: tip-bot for Adrian Hunter Message-ID: Cc: dsahern@gmail.com, hpa@zytor.com, peterz@infradead.org, eranian@google.com, adrian.hunter@intel.com, mingo@kernel.org, fweisbec@gmail.com, jolsa@redhat.com, acme@redhat.com, linux-kernel@vger.kernel.org, namhyung@gmail.com, tglx@linutronix.de Reply-To: eranian@google.com, dsahern@gmail.com, hpa@zytor.com, peterz@infradead.org, jolsa@redhat.com, tglx@linutronix.de, acme@redhat.com, namhyung@gmail.com, linux-kernel@vger.kernel.org, adrian.hunter@intel.com, fweisbec@gmail.com, mingo@kernel.org In-Reply-To: <1428594864-29309-15-git-send-email-adrian.hunter@intel.com> References: <1428594864-29309-15-git-send-email-adrian.hunter@intel.com> To: linux-tip-commits@vger.kernel.org Subject: [tip:perf/core] perf auxtrace: Add a hashtable for caching Git-Commit-ID: c3278f0231e833c6030c3aeab510415fdbbfd353 X-Mailer: tip-git-log-daemon Robot-ID: Robot-Unsubscribe: Contact to get blacklisted from these emails MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Content-Type: text/plain; charset=UTF-8 Content-Disposition: inline Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Commit-ID: c3278f0231e833c6030c3aeab510415fdbbfd353 Gitweb: http://git.kernel.org/tip/c3278f0231e833c6030c3aeab510415fdbbfd353 Author: Adrian Hunter AuthorDate: Thu, 9 Apr 2015 18:53:54 +0300 Committer: Arnaldo Carvalho de Melo CommitDate: Wed, 29 Apr 2015 10:37:55 -0300 perf auxtrace: Add a hashtable for caching 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 Cc: David Ahern Cc: Frederic Weisbecker Cc: Jiri Olsa Cc: Namhyung Kim Cc: Peter Zijlstra Cc: Stephane Eranian Link: http://lkml.kernel.org/r/1428594864-29309-15-git-send-email-adrian.hunter@intel.com Signed-off-by: Arnaldo Carvalho de Melo --- 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 c4515e1..3cd89ec 100644 --- a/tools/perf/util/auxtrace.c +++ b/tools/perf/util/auxtrace.c @@ -40,6 +40,8 @@ #include "asm/bug.h" #include "auxtrace.h" +#include + #include "event.h" #include "session.h" #include "debug.h" @@ -944,3 +946,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 ba78d82..53b60a6 100644 --- a/tools/perf/util/auxtrace.h +++ b/tools/perf/util/auxtrace.h @@ -333,6 +333,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);