Messages in this thread Patch in this message | | | From | Adrian Hunter <> | Subject | [PATCH V2 14/22] perf itrace: Add a hashtable for caching decoded instructions | Date | Thu, 20 Nov 2014 15:23:20 +0200 |
| |
Decoding Instruction Trace data may involve walking object code. Rather than repetitively decoding the same instructions, a cache can be used to cache the results.
Signed-off-by: Adrian Hunter <adrian.hunter@intel.com> --- tools/perf/util/itrace.c | 123 +++++++++++++++++++++++++++++++++++++++++++++++ tools/perf/util/itrace.h | 14 ++++++ 2 files changed, 137 insertions(+)
diff --git a/tools/perf/util/itrace.c b/tools/perf/util/itrace.c index eb43a7f..fd67a9a 100644 --- a/tools/perf/util/itrace.c +++ b/tools/perf/util/itrace.c @@ -37,6 +37,8 @@ #include "thread_map.h" #include "itrace.h" +#include <linux/hash.h> + #include "event.h" #include "session.h" #include "debug.h" @@ -916,3 +918,124 @@ int itrace_mmap__read(struct itrace_mmap *mm, struct itrace_record *itr, return 1; } + +/** + * struct itrace_cache - hash table to cache decoded instruction blocks + * @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 itrace_cache { + struct hlist_head *hashtable; + size_t sz; + size_t entry_size; + size_t limit; + size_t cnt; + unsigned int bits; +}; + +struct itrace_cache *itrace_cache__new(unsigned int bits, size_t entry_size, + unsigned int limit_percent) +{ + struct itrace_cache *c; + struct hlist_head *ht; + size_t sz, i; + + c = zalloc(sizeof(struct itrace_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 itrace_cache__drop(struct itrace_cache *c) +{ + struct itrace_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); + itrace_cache__free_entry(c, entry); + } + } + + c->cnt = 0; +} + +void itrace_cache__free(struct itrace_cache *c) +{ + if (!c) + return; + + itrace_cache__drop(c); + free(c->hashtable); + free(c); +} + +void *itrace_cache__alloc_entry(struct itrace_cache *c) +{ + return malloc(c->entry_size); +} + +void itrace_cache__free_entry(struct itrace_cache *c __maybe_unused, + void *entry) +{ + free(entry); +} + +int itrace_cache__add(struct itrace_cache *c, u32 key, + struct itrace_cache_entry *entry) +{ + if (c->limit && ++c->cnt > c->limit) + itrace_cache__drop(c); + + entry->key = key; + hlist_add_head(&entry->hash, &c->hashtable[hash_32(key, c->bits)]); + + return 0; +} + +void *itrace_cache__lookup(struct itrace_cache *c, u32 key) +{ + struct itrace_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/itrace.h b/tools/perf/util/itrace.h index 575037c..e67fa34 100644 --- a/tools/perf/util/itrace.h +++ b/tools/perf/util/itrace.h @@ -316,6 +316,20 @@ int itrace_heap__add(struct itrace_heap *heap, unsigned int queue_nr, void itrace_heap__pop(struct itrace_heap *heap); void itrace_heap__free(struct itrace_heap *heap); +struct itrace_cache_entry { + struct hlist_node hash; + u32 key; +}; + +struct itrace_cache *itrace_cache__new(unsigned int bits, size_t entry_size, + unsigned int limit_percent); +void itrace_cache__free(struct itrace_cache *itrace_cache); +void *itrace_cache__alloc_entry(struct itrace_cache *c); +void itrace_cache__free_entry(struct itrace_cache *c, void *entry); +int itrace_cache__add(struct itrace_cache *c, u32 key, + struct itrace_cache_entry *entry); +void *itrace_cache__lookup(struct itrace_cache *c, u32 key); + struct itrace_record *itrace_record__init(int *err); int itrace_record__options(struct itrace_record *itr, -- 1.9.1
| |