From 40f98e75f75f5690a3d811ade515507fdd9e81bc Mon Sep 17 00:00:00 2001 From: Milian Wolff Date: Sat, 20 Sep 2014 19:08:01 +0200 Subject: [PATCH] Make DWARF cache size configurable via unw_set_cache_size. By default, a cache size of 128 is set (log size of 7). The user can now increase this value by calling unw_set_cache_size(as, 1024) or similar. In my benchmarks, this can give a significant performance gain on repeated DWARF-based unwinding. --- include/dwarf.h | 22 +--- include/libunwind-common.h.in | 2 + include/tdep-aarch64/libunwind_i.h | 2 +- include/tdep-arm/libunwind_i.h | 2 +- include/tdep-hppa/libunwind_i.h | 2 +- include/tdep-mips/libunwind_i.h | 2 +- include/tdep-ppc32/libunwind_i.h | 2 +- include/tdep-ppc64/libunwind_i.h | 2 +- include/tdep-sh/libunwind_i.h | 2 +- include/tdep-x86/libunwind_i.h | 2 +- include/tdep-x86_64/libunwind_i.h | 2 +- src/dwarf/Gparser.c | 231 +++++++++++++++++++++++++++++++++---- src/mi/Gset_caching_policy.c | 22 ++++ tests/check-namespace.sh.in | 2 + 14 files changed, 247 insertions(+), 50 deletions(-) diff --git a/include/dwarf.h b/include/dwarf.h index 633868b..eebebab 100644 --- a/include/dwarf.h +++ b/include/dwarf.h @@ -325,29 +325,11 @@ typedef struct dwarf_cursor } dwarf_cursor_t; -#define DWARF_LOG_UNW_CACHE_SIZE 7 -#define DWARF_UNW_CACHE_SIZE (1 << DWARF_LOG_UNW_CACHE_SIZE) - -#define DWARF_LOG_UNW_HASH_SIZE (DWARF_LOG_UNW_CACHE_SIZE + 1) -#define DWARF_UNW_HASH_SIZE (1 << DWARF_LOG_UNW_HASH_SIZE) +/* default logarithmic cache size for the internal dwarf_rs_cache */ +#define DWARF_DEFAULT_LOG_UNW_CACHE_SIZE 7 typedef unsigned char unw_hash_index_t; -struct dwarf_rs_cache - { - pthread_mutex_t lock; - unsigned short lru_head; /* index of lead-recently used rs */ - unsigned short lru_tail; /* index of most-recently used rs */ - - /* hash table that maps instruction pointer to rs index: */ - unsigned short hash[DWARF_UNW_HASH_SIZE]; - - uint32_t generation; /* generation number */ - - /* rs cache: */ - dwarf_reg_state_t buckets[DWARF_UNW_CACHE_SIZE]; - }; - /* A list of descriptors for loaded .debug_frame sections. */ struct unw_debug_frame_list diff --git a/include/libunwind-common.h.in b/include/libunwind-common.h.in index fa753ba..cd2dac6 100644 --- a/include/libunwind-common.h.in +++ b/include/libunwind-common.h.in @@ -225,6 +225,7 @@ unw_save_loc_t; #define unw_handle_signal_frame UNW_OBJ(handle_signal_frame) #define unw_get_proc_name UNW_OBJ(get_proc_name) #define unw_set_caching_policy UNW_OBJ(set_caching_policy) +#define unw_set_cache_size UNW_OBJ(set_cache_size) #define unw_regname UNW_ARCH_OBJ(regname) #define unw_flush_cache UNW_ARCH_OBJ(flush_cache) #define unw_strerror UNW_ARCH_OBJ(strerror) @@ -234,6 +235,7 @@ extern void unw_destroy_addr_space (unw_addr_space_t); extern unw_accessors_t *unw_get_accessors (unw_addr_space_t); extern void unw_flush_cache (unw_addr_space_t, unw_word_t, unw_word_t); extern int unw_set_caching_policy (unw_addr_space_t, unw_caching_policy_t); +extern int unw_set_cache_size (unw_addr_space_t, unsigned); extern const char *unw_regname (unw_regnum_t); extern int unw_init_local (unw_cursor_t *, unw_context_t *); diff --git a/include/tdep-aarch64/libunwind_i.h b/include/tdep-aarch64/libunwind_i.h index ca28155..c8dadf2 100644 --- a/include/tdep-aarch64/libunwind_i.h +++ b/include/tdep-aarch64/libunwind_i.h @@ -85,7 +85,7 @@ struct unw_addr_space #endif unw_word_t dyn_generation; /* see dyn-common.h */ unw_word_t dyn_info_list_addr; /* (cached) dyn_info_list_addr */ - struct dwarf_rs_cache global_cache; + unsigned short cache_log_size; struct unw_debug_frame_list *debug_frames; }; diff --git a/include/tdep-arm/libunwind_i.h b/include/tdep-arm/libunwind_i.h index d3a279c..482df46 100644 --- a/include/tdep-arm/libunwind_i.h +++ b/include/tdep-arm/libunwind_i.h @@ -70,7 +70,7 @@ struct unw_addr_space #endif unw_word_t dyn_generation; /* see dyn-common.h */ unw_word_t dyn_info_list_addr; /* (cached) dyn_info_list_addr */ - struct dwarf_rs_cache global_cache; + unsigned short cache_log_size; struct unw_debug_frame_list *debug_frames; }; diff --git a/include/tdep-hppa/libunwind_i.h b/include/tdep-hppa/libunwind_i.h index d5cc1b9..3c4f0a7 100644 --- a/include/tdep-hppa/libunwind_i.h +++ b/include/tdep-hppa/libunwind_i.h @@ -53,7 +53,7 @@ struct unw_addr_space #endif unw_word_t dyn_generation; /* see dyn-common.h */ unw_word_t dyn_info_list_addr; /* (cached) dyn_info_list_addr */ - struct dwarf_rs_cache global_cache; + unsigned short cache_log_size; struct unw_debug_frame_list *debug_frames; }; diff --git a/include/tdep-mips/libunwind_i.h b/include/tdep-mips/libunwind_i.h index d11894d..f280093 100644 --- a/include/tdep-mips/libunwind_i.h +++ b/include/tdep-mips/libunwind_i.h @@ -61,7 +61,7 @@ struct unw_addr_space #endif unw_word_t dyn_generation; /* see dyn-common.h */ unw_word_t dyn_info_list_addr; /* (cached) dyn_info_list_addr */ - struct dwarf_rs_cache global_cache; + unsigned short cache_log_size; struct unw_debug_frame_list *debug_frames; }; diff --git a/include/tdep-ppc32/libunwind_i.h b/include/tdep-ppc32/libunwind_i.h index cc113c5..63dbd6f 100644 --- a/include/tdep-ppc32/libunwind_i.h +++ b/include/tdep-ppc32/libunwind_i.h @@ -59,7 +59,7 @@ struct unw_addr_space #endif unw_word_t dyn_generation; /* see dyn-common.h */ unw_word_t dyn_info_list_addr; /* (cached) dyn_info_list_addr */ - struct dwarf_rs_cache global_cache; + unsigned short cache_log_size; struct unw_debug_frame_list *debug_frames; int validate; }; diff --git a/include/tdep-ppc64/libunwind_i.h b/include/tdep-ppc64/libunwind_i.h index 5a5bddb..b3d90d3 100644 --- a/include/tdep-ppc64/libunwind_i.h +++ b/include/tdep-ppc64/libunwind_i.h @@ -61,7 +61,7 @@ struct unw_addr_space #endif unw_word_t dyn_generation; /* see dyn-common.h */ unw_word_t dyn_info_list_addr; /* (cached) dyn_info_list_addr */ - struct dwarf_rs_cache global_cache; + unsigned short cache_log_size; struct unw_debug_frame_list *debug_frames; int validate; }; diff --git a/include/tdep-sh/libunwind_i.h b/include/tdep-sh/libunwind_i.h index 7bbb29b..bd439b4 100644 --- a/include/tdep-sh/libunwind_i.h +++ b/include/tdep-sh/libunwind_i.h @@ -54,7 +54,7 @@ struct unw_addr_space #endif unw_word_t dyn_generation; /* see dyn-common.h */ unw_word_t dyn_info_list_addr; /* (cached) dyn_info_list_addr */ - struct dwarf_rs_cache global_cache; + unsigned short cache_log_size; struct unw_debug_frame_list *debug_frames; }; diff --git a/include/tdep-x86/libunwind_i.h b/include/tdep-x86/libunwind_i.h index b1c8b98..157e509 100644 --- a/include/tdep-x86/libunwind_i.h +++ b/include/tdep-x86/libunwind_i.h @@ -53,7 +53,7 @@ struct unw_addr_space #endif unw_word_t dyn_generation; /* see dyn-common.h */ unw_word_t dyn_info_list_addr; /* (cached) dyn_info_list_addr */ - struct dwarf_rs_cache global_cache; + unsigned short cache_log_size; struct unw_debug_frame_list *debug_frames; }; diff --git a/include/tdep-x86_64/libunwind_i.h b/include/tdep-x86_64/libunwind_i.h index d19c705..9627196 100644 --- a/include/tdep-x86_64/libunwind_i.h +++ b/include/tdep-x86_64/libunwind_i.h @@ -70,7 +70,7 @@ struct unw_addr_space #endif unw_word_t dyn_generation; /* see dyn-common.h */ unw_word_t dyn_info_list_addr; /* (cached) dyn_info_list_addr */ - struct dwarf_rs_cache global_cache; + unsigned short cache_log_size; struct unw_debug_frame_list *debug_frames; }; diff --git a/src/dwarf/Gparser.c b/src/dwarf/Gparser.c index 3a47255..9fc354c 100644 --- a/src/dwarf/Gparser.c +++ b/src/dwarf/Gparser.c @@ -23,13 +23,49 @@ LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ -#include #include "dwarf_i.h" #include "libunwind_i.h" +#include +#include + +#pragma weak pthread_once +#pragma weak pthread_key_create +#pragma weak pthread_getspecific +#pragma weak pthread_setspecific #define alloc_reg_state() (mempool_alloc (&dwarf_reg_state_pool)) #define free_reg_state(rs) (mempool_free (&dwarf_reg_state_pool, rs)) +#define DWARF_UNW_CACHE_SIZE(log_size) (1 << log_size) +#define DWARF_UNW_HASH_SIZE(log_size) (1 << (log_size + 1)) + +typedef struct dwarf_rs_cache +{ + pthread_mutex_t lock; + unsigned short lru_head; /* index of lead-recently used rs */ + unsigned short lru_tail; /* index of most-recently used rs */ + + unsigned short log_size; + /* hash table that maps instruction pointer to rs index: */ + unsigned short* hash; + + uint32_t generation; /* generation number */ + + size_t dtor_count; /* Counts how many times our destructor has already + been called. */ + + /* rs cache: */ + dwarf_reg_state_t* buckets; +} dwarf_rs_cache_t; + +static define_lock (rs_init_lock); +static pthread_once_t rs_cache_once = PTHREAD_ONCE_INIT; +static sig_atomic_t rs_cache_once_happen; +static pthread_key_t rs_cache_key; +static struct mempool rs_cache_pool; +static __thread dwarf_rs_cache_t *tls_rs_cache; +static __thread int tls_rs_cache_destroyed; + static inline int read_regnum (unw_addr_space_t as, unw_accessors_t *a, unw_word_t *addr, unw_word_t *valp, void *arg) @@ -509,14 +545,14 @@ parse_fde (struct dwarf_cursor *c, unw_word_t ip, dwarf_state_record_t *sr) } static inline void -flush_rs_cache (struct dwarf_rs_cache *cache) +flush_rs_cache (dwarf_rs_cache_t *cache) { int i; - cache->lru_head = DWARF_UNW_CACHE_SIZE - 1; + cache->lru_head = DWARF_UNW_CACHE_SIZE(cache->log_size) - 1; cache->lru_tail = 0; - for (i = 0; i < DWARF_UNW_CACHE_SIZE; ++i) + for (i = 0; i < DWARF_UNW_CACHE_SIZE(cache->log_size); ++i) { if (i > 0) cache->buckets[i].lru_chain = (i - 1); @@ -524,19 +560,170 @@ flush_rs_cache (struct dwarf_rs_cache *cache) cache->buckets[i].ip = 0; cache->buckets[i].valid = 0; } - for (i = 0; ilog_size); ++i) cache->hash[i] = -1; } -static inline struct dwarf_rs_cache * +/* Free memory for a dwarf_rs_cache. */ +static void +rs_cache_free (void *arg) +{ + dwarf_rs_cache_t *cache = arg; + if (++cache->dtor_count < PTHREAD_DESTRUCTOR_ITERATIONS) + { + /* Not yet our turn to get destroyed. Re-install ourselves into the key. */ + pthread_setspecific(rs_cache_key, cache); + Debug(5, "delayed freeing cache %p (%zx to go)\n", cache, + PTHREAD_DESTRUCTOR_ITERATIONS - cache->dtor_count); + return; + } + tls_rs_cache_destroyed = 1; + tls_rs_cache = NULL; + munmap (cache->buckets, DWARF_UNW_CACHE_SIZE(cache->log_size) * sizeof(dwarf_reg_state_t)); + munmap (cache->hash, DWARF_UNW_HASH_SIZE(cache->log_size) * sizeof(short unsigned)); + mempool_free (&rs_cache_pool, cache); + Debug(5, "freed cache %p\n", cache); +} + +/* Initialise dwarf rs cache for threaded use. */ +static void +rs_cache_init_once (void) +{ + pthread_key_create (&rs_cache_key, &rs_cache_free); + mempool_init (&rs_cache_pool, sizeof (dwarf_rs_cache_t), 0); + rs_cache_once_happen = 1; +} + +static dwarf_reg_state_t * +rs_cache_buckets (size_t n) +{ + dwarf_reg_state_t *buckets; + GET_MEMORY(buckets, n * sizeof (dwarf_reg_state_t)); + // TODO: init? currently done in e.g. init.h -> common_init + return buckets; +} + +static unsigned short * +rs_cache_hashes (size_t n) +{ + unsigned short *hashes; + GET_MEMORY(hashes, n * sizeof (unsigned short)); + // TODO: init? currently done in flush_rs_cache? + return hashes; +} + +/* Allocate and initialise hash table for rs cache lookups. + Returns the cache initialised with (1u << HASH_LOW_BITS) hash + buckets, or NULL if there was a memory allocation problem. */ +static dwarf_rs_cache_t * +rs_cache_create (unw_addr_space_t as) +{ + dwarf_rs_cache_t *cache; + short unsigned int cache_log_size = as->cache_log_size; + + if (tls_rs_cache_destroyed) + { + /* The current thread is in the process of exiting. Don't recreate + cache, as we wouldn't have another chance to free it. */ + Debug(5, "refusing to reallocate cache: " + "thread-locals are being deallocated\n"); + return NULL; + } + + if (unlikely (cache_log_size == 0)) + cache_log_size = DWARF_DEFAULT_LOG_UNW_CACHE_SIZE; + + if (! (cache = mempool_alloc(&rs_cache_pool))) + { + Debug(5, "failed to allocate cache\n"); + return NULL; + } + + if (! (cache->buckets = rs_cache_buckets(1u << as->cache_log_size))) + { + Debug(5, "failed to allocate buckets\n"); + mempool_free(&rs_cache_pool, cache); + return NULL; + } + + if (! (cache->hash = rs_cache_hashes(1u << (as->cache_log_size + 1)))) + { + Debug(5, "failed to allocate hashes\n"); + mempool_free(&rs_cache_pool, cache); + return NULL; + } + + cache->log_size = as->cache_log_size; + cache->dtor_count = 0; + lock_init(&cache->lock); + + flush_rs_cache (cache); + cache->generation = as->cache_generation; + + tls_rs_cache_destroyed = 0; /* Paranoia: should already be 0. */ + Debug(5, "allocated cache %p of log size %u\n", cache, cache->log_size); + return cache; +} + +static dwarf_rs_cache_t * +rs_cache_get_unthreaded (unw_addr_space_t as) +{ + dwarf_rs_cache_t *cache; + intrmask_t saved_mask; + static dwarf_rs_cache_t *global_cache = NULL; + lock_acquire (&rs_init_lock, saved_mask); + if (! global_cache) + { + mempool_init (&rs_cache_pool, sizeof (dwarf_rs_cache_t), 0); + global_cache = rs_cache_create (as); + } + cache = global_cache; + lock_release (&rs_init_lock, saved_mask); + Debug(5, "using cache %p\n", cache); + return cache; +} + +/* Get the frame cache for the current thread. Create it if there is none. */ +static dwarf_rs_cache_t * +rs_cache_get (unw_addr_space_t as) +{ + dwarf_rs_cache_t *cache; + if (likely (pthread_once != NULL)) + { + pthread_once(&rs_cache_once, &rs_cache_init_once); + if (!rs_cache_once_happen) + { + return rs_cache_get_unthreaded(as); + } + if (! (cache = tls_rs_cache)) + { + cache = rs_cache_create(as); + pthread_setspecific(rs_cache_key, cache); + tls_rs_cache = cache; + } + Debug(5, "using cache %p\n", cache); + return cache; + } + else + { + return rs_cache_get_unthreaded(as); + } +} + + +static inline dwarf_rs_cache_t * get_rs_cache (unw_addr_space_t as, intrmask_t *saved_maskp) { - struct dwarf_rs_cache *cache = &as->global_cache; + dwarf_rs_cache_t *cache; unw_caching_policy_t caching = as->caching_policy; if (caching == UNW_CACHE_NONE) return NULL; + cache = rs_cache_get(as); + if (unlikely (cache == NULL)) + return NULL; + if (likely (caching == UNW_CACHE_GLOBAL)) { Debug (16, "acquiring lock\n"); @@ -553,7 +740,7 @@ get_rs_cache (unw_addr_space_t as, intrmask_t *saved_maskp) } static inline void -put_rs_cache (unw_addr_space_t as, struct dwarf_rs_cache *cache, +put_rs_cache (unw_addr_space_t as, dwarf_rs_cache_t *cache, intrmask_t *saved_maskp) { assert (as->caching_policy != UNW_CACHE_NONE); @@ -564,12 +751,12 @@ put_rs_cache (unw_addr_space_t as, struct dwarf_rs_cache *cache, } static inline unw_hash_index_t CONST_ATTR -hash (unw_word_t ip) +hash (unw_word_t ip, unsigned short log_size) { /* based on (sqrt(5)/2-1)*2^64 */ # define magic ((unw_word_t) 0x9e3779b97f4a7c16ULL) - return ip * magic >> ((sizeof(unw_word_t) * 8) - DWARF_LOG_UNW_HASH_SIZE); + return ip * magic >> ((sizeof(unw_word_t) * 8) - (log_size + 1)); } static inline long @@ -581,7 +768,7 @@ cache_match (dwarf_reg_state_t *rs, unw_word_t ip) } static dwarf_reg_state_t * -rs_lookup (struct dwarf_rs_cache *cache, struct dwarf_cursor *c) +rs_lookup (dwarf_rs_cache_t *cache, struct dwarf_cursor *c) { dwarf_reg_state_t *rs = cache->buckets + c->hint; unsigned short index; @@ -592,8 +779,8 @@ rs_lookup (struct dwarf_rs_cache *cache, struct dwarf_cursor *c) if (cache_match (rs, ip)) return rs; - index = cache->hash[hash (ip)]; - if (index >= DWARF_UNW_CACHE_SIZE) + index = cache->hash[hash (ip, cache->log_size)]; + if (index >= DWARF_UNW_CACHE_SIZE(cache->log_size)) return NULL; rs = cache->buckets + index; @@ -606,14 +793,14 @@ rs_lookup (struct dwarf_rs_cache *cache, struct dwarf_cursor *c) (rs - cache->buckets); return rs; } - if (rs->coll_chain >= DWARF_UNW_HASH_SIZE) + if (rs->coll_chain >= DWARF_UNW_HASH_SIZE(cache->log_size)) return NULL; rs = cache->buckets + rs->coll_chain; } } static inline dwarf_reg_state_t * -rs_new (struct dwarf_rs_cache *cache, struct dwarf_cursor * c) +rs_new (dwarf_rs_cache_t *cache, struct dwarf_cursor * c) { dwarf_reg_state_t *rs, *prev, *tmp; unw_hash_index_t index; @@ -630,7 +817,7 @@ rs_new (struct dwarf_rs_cache *cache, struct dwarf_cursor * c) /* remove the old rs from the hash table (if it's there): */ if (rs->ip) { - index = hash (rs->ip); + index = hash (rs->ip, cache->log_size); tmp = cache->buckets + cache->hash[index]; prev = NULL; while (1) @@ -645,7 +832,7 @@ rs_new (struct dwarf_rs_cache *cache, struct dwarf_cursor * c) } else prev = tmp; - if (tmp->coll_chain >= DWARF_UNW_CACHE_SIZE) + if (tmp->coll_chain >= DWARF_UNW_CACHE_SIZE(cache->log_size)) /* old rs wasn't in the hash-table */ break; tmp = cache->buckets + tmp->coll_chain; @@ -653,7 +840,7 @@ rs_new (struct dwarf_rs_cache *cache, struct dwarf_cursor * c) } /* enter new rs in the hash table */ - index = hash (c->ip); + index = hash (c->ip, cache->log_size); rs->coll_chain = cache->hash[index]; cache->hash[index] = rs - cache->buckets; @@ -865,14 +1052,16 @@ dwarf_find_save_locs (struct dwarf_cursor *c) { dwarf_state_record_t sr; dwarf_reg_state_t *rs, rs_copy; - struct dwarf_rs_cache *cache; + dwarf_rs_cache_t *cache = NULL; int ret = 0; intrmask_t saved_mask; - if (c->as->caching_policy == UNW_CACHE_NONE) + if (c->as->caching_policy != UNW_CACHE_NONE) + cache = get_rs_cache(c->as, &saved_mask); + + if (!cache) return uncached_dwarf_find_save_locs (c); - cache = get_rs_cache(c->as, &saved_mask); rs = rs_lookup(cache, c); if (rs) diff --git a/src/mi/Gset_caching_policy.c b/src/mi/Gset_caching_policy.c index 45ba100..a1a03f0 100644 --- a/src/mi/Gset_caching_policy.c +++ b/src/mi/Gset_caching_policy.c @@ -44,3 +44,25 @@ unw_set_caching_policy (unw_addr_space_t as, unw_caching_policy_t policy) unw_flush_cache (as, 0, 0); return 0; } + +PROTECTED int +unw_set_cache_size (unw_addr_space_t as, unsigned size) +{ + if (!tdep_init_done) + tdep_init (); + + unsigned short cache_log_size = 1; + while (size > 2) { + size /= 2; + ++cache_log_size; + } + + if (cache_log_size == as->cache_log_size) + return 0; /* no change */ + + as->cache_log_size = cache_log_size; + + /* Ensure caches are empty (and initialized). */ + unw_flush_cache (as, 0, 0); + return 0; +} diff --git a/tests/check-namespace.sh.in b/tests/check-namespace.sh.in index 1ef74ab..1ae8121 100644 --- a/tests/check-namespace.sh.in +++ b/tests/check-namespace.sh.in @@ -103,6 +103,7 @@ check_local_unw_abi () { match _UL${plat}_local_addr_space match _UL${plat}_resume match _UL${plat}_set_caching_policy + match _UL${plat}_set_cache_size match _UL${plat}_set_reg match _UL${plat}_set_fpreg match _UL${plat}_step @@ -199,6 +200,7 @@ check_generic_unw_abi () { match _U${plat}_regname match _U${plat}_resume match _U${plat}_set_caching_policy + match _U${plat}_set_cache_size match _U${plat}_set_fpreg match _U${plat}_set_reg match _U${plat}_step -- 2.5.3