[Libunwind-devel] [PATCH V2] Configurable cache size

[Dave Watson]

This is a re-spin of Milian's last patch:
http://lists.nongnu.org/archive/html/libunwind-devel/2014-10/msg00006.html

Changes:

* Use item size and round up to nearest power of 2.

* Initial cache still exists in BSS.  Without this, it means we would fail
  backtrace when out of memory.  The test-mem test fails without this

* Drop the threading changes.  Unfortunately, in glibc, neither __thread
  (tls_get_addr) nor pthread_setspecific are async-signal-safe.  We've
  actually had issues with the Gtrace code because of this, and in some
  cases have to fallback to unw_step.  It could be made to only work
  in PER_THREAD caching case as a non-default, but it still seems
  like it's against the spirit of async-signal-safe code.

Alternativly to threading, a simple rw-lock would help, or even better,
a lock-free or RCU style cache.
---
 include/dwarf.h               | 21 ++++++++++-----
 include/libunwind-common.h.in |  2 ++
 src/Makefile.am               |  6 +++--
 src/dwarf/Gparser.c           | 62 ++++++++++++++++++++++++++++++++-----------
 src/mi/Gset_cache_size.c      | 58 ++++++++++++++++++++++++++++++++++++++++
 src/mi/Lset_cache_size.c      |  5 ++++
 tests/check-namespace.sh.in   |  2 ++
 tests/test-flush-cache.c      |  1 +
 8 files changed, 133 insertions(+), 24 deletions(-)
 create mode 100644 src/mi/Gset_cache_size.c
 create mode 100644 src/mi/Lset_cache_size.c

diff --git a/include/dwarf.h b/include/dwarf.h
index 633868b..615c8a9 100644
--- a/include/dwarf.h
+++ b/include/dwarf.h
@@ -325,11 +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_DEFAULT_LOG_UNW_CACHE_SIZE        7
+#define DWARF_DEFAULT_UNW_CACHE_SIZE    (1 << DWARF_DEFAULT_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)
+#define DWARF_DEFAULT_LOG_UNW_HASH_SIZE (DWARF_DEFAULT_LOG_UNW_CACHE_SIZE + 1)
+#define DWARF_DEFAULT_UNW_HASH_SIZE     (1 << DWARF_DEFAULT_LOG_UNW_HASH_SIZE)
 
 typedef unsigned char unw_hash_index_t;
 
@@ -339,13 +339,20 @@ struct dwarf_rs_cache
     unsigned short lru_head;    /* index of lead-recently used rs */
     unsigned short lru_tail;    /* index of most-recently used rs */
 
+    unsigned short log_size;
+    unsigned short prev_log_size;
+
     /* hash table that maps instruction pointer to rs index: */
-    unsigned short hash[DWARF_UNW_HASH_SIZE];
+    unsigned short *hash;
 
     uint32_t generation;        /* generation number */
 
     /* rs cache: */
-    dwarf_reg_state_t buckets[DWARF_UNW_CACHE_SIZE];
+    dwarf_reg_state_t *buckets;
+
+    /* default memory, loaded in BSS segment */
+    unsigned short default_hash[DWARF_DEFAULT_UNW_HASH_SIZE];
+    dwarf_reg_state_t default_buckets[DWARF_DEFAULT_UNW_CACHE_SIZE];
   };
 
 /* A list of descriptors for loaded .debug_frame sections.  */
@@ -394,6 +401,7 @@ struct dwarf_callback_data
 #define dwarf_make_proc_info            UNW_OBJ (dwarf_make_proc_info)
 #define dwarf_read_encoded_pointer      UNW_OBJ (dwarf_read_encoded_pointer)
 #define dwarf_step                      UNW_OBJ (dwarf_step)
+#define dwarf_flush_rs_cache            UNW_OBJ (dwarf_flush_rs_cache)
 
 extern int dwarf_init (void);
 #ifndef UNW_REMOTE_ONLY
@@ -438,5 +446,6 @@ extern int dwarf_read_encoded_pointer (unw_addr_space_t as,
                                        const unw_proc_info_t *pi,
                                        unw_word_t *valp, void *arg);
 extern int dwarf_step (struct dwarf_cursor *c);
+extern int dwarf_flush_rs_cache (struct dwarf_rs_cache *cache);
 
 #endif /* dwarf_h */
diff --git a/include/libunwind-common.h.in b/include/libunwind-common.h.in
index fa753ba..97a799a 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, size_t);
 extern const char *unw_regname (unw_regnum_t);
 
 extern int unw_init_local (unw_cursor_t *, unw_context_t *);
diff --git a/src/Makefile.am b/src/Makefile.am
index 5d87475..bcdb01f 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -109,7 +109,8 @@ libunwind_la_SOURCES_generic =                              
                \
        mi/Gput_dynamic_unwind_info.c mi/Gdestroy_addr_space.c          \
        mi/Gget_reg.c mi/Gset_reg.c                                     \
        mi/Gget_fpreg.c mi/Gset_fpreg.c                                 \
-       mi/Gset_caching_policy.c
+       mi/Gset_caching_policy.c                                        \
+       mi/Gset_cache_size.c
 
 if SUPPORT_CXX_EXCEPTIONS
 libunwind_la_SOURCES_local_unwind =                                    \
@@ -137,7 +138,8 @@ libunwind_la_SOURCES_local_nounwind =                       
                \
        mi/Lput_dynamic_unwind_info.c mi/Ldestroy_addr_space.c          \
        mi/Lget_reg.c   mi/Lset_reg.c                                   \
        mi/Lget_fpreg.c mi/Lset_fpreg.c                                 \
-       mi/Lset_caching_policy.c
+       mi/Lset_caching_policy.c                                        \
+       mi/Lset_cache_size.c
 
 libunwind_la_SOURCES_local =                                           \
        $(libunwind_la_SOURCES_local_nounwind)                          \
diff --git a/src/dwarf/Gparser.c b/src/dwarf/Gparser.c
index 3a47255..a34301d 100644
--- a/src/dwarf/Gparser.c
+++ b/src/dwarf/Gparser.c
@@ -23,13 +23,17 @@ 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 <stddef.h>
 #include "dwarf_i.h"
 #include "libunwind_i.h"
+#include <stddef.h>
+#include <limits.h>
 
 #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))
+
 static inline int
 read_regnum (unw_addr_space_t as, unw_accessors_t *a, unw_word_t *addr,
              unw_word_t *valp, void *arg)
@@ -508,15 +512,37 @@ parse_fde (struct dwarf_cursor *c, unw_word_t ip, 
dwarf_state_record_t *sr)
   return 0;
 }
 
-static inline void
-flush_rs_cache (struct dwarf_rs_cache *cache)
+HIDDEN int
+dwarf_flush_rs_cache (struct dwarf_rs_cache *cache)
 {
   int i;
 
-  cache->lru_head = DWARF_UNW_CACHE_SIZE - 1;
+  if (cache->log_size == DWARF_DEFAULT_LOG_UNW_CACHE_SIZE
+      || !cache->hash) {
+    cache->hash = cache->default_hash;
+    cache->buckets = cache->default_buckets;
+    cache->log_size = DWARF_DEFAULT_LOG_UNW_CACHE_SIZE;
+  } else {
+    if (cache->hash && cache->hash != cache->default_hash)
+      munmap(cache->hash, DWARF_UNW_HASH_SIZE(cache->prev_log_size));
+    if (cache->buckets && cache->buckets != cache->default_buckets)
+      munmap(cache->buckets, DWARF_UNW_CACHE_SIZE(cache->prev_log_size));
+    GET_MEMORY(cache->hash, DWARF_UNW_HASH_SIZE(cache->log_size)
+                             * sizeof (cache->hash[0]));
+    GET_MEMORY(cache->buckets, DWARF_UNW_CACHE_SIZE(cache->log_size)
+                                * sizeof (cache->buckets[0]));
+    if (!cache->hash || !cache->buckets)
+      {
+        Debug (5, "Unable to allocate cache memory");
+        return -1;
+      }
+    cache->prev_log_size = cache->log_size;
+  }
+
+  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,8 +550,10 @@ flush_rs_cache (struct dwarf_rs_cache *cache)
       cache->buckets[i].ip = 0;
       cache->buckets[i].valid = 0;
     }
-  for (i = 0; i<DWARF_UNW_HASH_SIZE; ++i)
+  for (i = 0; i< DWARF_UNW_HASH_SIZE(cache->log_size); ++i)
     cache->hash[i] = -1;
+
+  return 0;
 }
 
 static inline struct dwarf_rs_cache *
@@ -543,9 +571,11 @@ get_rs_cache (unw_addr_space_t as, intrmask_t *saved_maskp)
       lock_acquire (&cache->lock, *saved_maskp);
     }
 
-  if (atomic_read (&as->cache_generation) != atomic_read (&cache->generation))
+  if ((atomic_read (&as->cache_generation) != atomic_read (&cache->generation))
+       || !cache->hash)
     {
-      flush_rs_cache (cache);
+      if (dwarf_flush_rs_cache (cache) < 0)
+        return NULL;
       cache->generation = as->cache_generation;
     }
 
@@ -564,12 +594,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
@@ -592,8 +622,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,7 +636,7 @@ 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;
     }
@@ -630,7 +660,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 +675,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 +683,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;
 
diff --git a/src/mi/Gset_cache_size.c b/src/mi/Gset_cache_size.c
new file mode 100644
index 0000000..895cd49
--- /dev/null
+++ b/src/mi/Gset_cache_size.c
@@ -0,0 +1,58 @@
+/* libunwind - a platform-independent unwind library
+   Copyright (C) 2014
+        Contributed by Milian Wolff <address@hidden>
+
+This file is part of libunwind.
+
+Permission is hereby granted, free of charge, to any person obtaining
+a copy of this software and associated documentation files (the
+"Software"), to deal in the Software without restriction, including
+without limitation the rights to use, copy, modify, merge, publish,
+distribute, sublicense, and/or sell copies of the Software, and to
+permit persons to whom the Software is furnished to do so, subject to
+the following conditions:
+
+The above copyright notice and this permission notice shall be
+included in all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
+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 "libunwind_i.h"
+
+PROTECTED int
+unw_set_cache_size (unw_addr_space_t as, size_t size)
+{
+  if (!tdep_init_done)
+    tdep_init ();
+
+  /* Round up to next power of two, slowly but portably */
+  size_t power = 1;
+  unsigned short log_size = 0;
+  while(power < size) {
+    power *= 2;
+    log_size++;
+    /* Largest size currently supported by rs_cache */
+    if (log_size >= 15)
+      break;
+  }
+
+  if (log_size == as->global_cache.log_size)
+    return 0;   /* no change */
+
+  as->global_cache.log_size = log_size;
+
+  /* Ensure caches are empty (and initialized).  */
+  unw_flush_cache (as, 0, 0);
+#ifdef __ia64__
+  return 0;
+#else
+  /* Synchronously purge cache, to ensure memory is allocated */
+  dwarf_flush_rs_cache(&as->global_cache);
+#endif
+}
diff --git a/src/mi/Lset_cache_size.c b/src/mi/Lset_cache_size.c
new file mode 100644
index 0000000..670f64d
--- /dev/null
+++ b/src/mi/Lset_cache_size.c
@@ -0,0 +1,5 @@
+#define UNW_LOCAL_ONLY
+#include <libunwind.h>
+#if defined(UNW_LOCAL_ONLY) && !defined(UNW_REMOTE_ONLY)
+#include "Gset_cache_size.c"
+#endif
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
diff --git a/tests/test-flush-cache.c b/tests/test-flush-cache.c
index 592162c..5a24fee 100644
--- a/tests/test-flush-cache.c
+++ b/tests/test-flush-cache.c
@@ -46,6 +46,7 @@ f257 (void)
     for (i = 0; i < n; ++i)
       printf ("[%d] ip=%p\n", i, buffer[i]);
 
+  unw_set_cache_size (unw_local_addr_space, 1023);
   unw_flush_cache (unw_local_addr_space, 0, 0);
 
   if (verbose)
-- 
2.8.0-rc2