Re: [Libunwind-devel] interval based cache?

[Dave Watson]

On 04/11/17 05:24 PM, Doug Moore wrote:
> The libunwind cache is based on hashing an instruction pointer (IP) value.  
> On a cache miss, the exploration for the right stack-popping info may come 
> down to a search of intervals defined by an eh_frame_hdr, so that the 
> interval found to include this IP could also include lots of neighboring 
> instructions, which would also lead to cache misses, if we ever looked them 
> up.  I’m wondering whether it's worth considering a change to the caching 
> mechanism so that instead of using a hash table, it used some ordered data 
> structure (binary tree, skip list, etc) of intervals, not IPs, so that there 
> would be at most one cache miss per interval.
> 
> Is there a problem in my thinking here?  If not, is the libunwind world 
> generally friendly or hostile to such a change?

I agree that a dwarf cache miss is so much more expensive, that we
could probably stand to make a hit slightly slower to avoid them. On
the other hand, I haven't run in to case where making it an ordered
datastructure would help, although I'm sure cases exist.  Some example
production hit/miss rates might be helpful here vs. an ordered
alternative.  A radix tree might also be a good choice.

Things we *have* run in to in prod:

* dwarf cache too small.  Hence the patches to make the cache size
  configurable.

* IIRC, the cache isn't lru, but just evicts the oldest entry.
  Probably not the best choice for walking the whole stack, since we'd
  almost never want to evict the topmost entries like main, etc.

* Too many calls to sigprocmask.  We could probably make this
  automatic just at the start/end of tracing for unw_backtrace, but
  unw_step users still have to do it directly (using
  --enable-block-signals=false).  The only alternative I can think of
  is making the cache lock-free somehow.

* dwarf_make_proc_info doesn't currently have a cache, while the
  original equivalent code in the IA64 version did have a cache here.
  Particularly important for exception unwinding since we have to call
  this at each step.

Anyways just a braindump of thoughts, there's definitely improvements
that can be made