Cache uwnind frame headers as they are found.

[saugustine]

Summary

This improves unwind performance quite substantially, and follows
a somewhat similar approach used in libgcc_s as described in the
thread here:

https://gcc.gnu.org/ml/gcc/2005-02/msg00625.html

On certain extremely exception heavy internal tests, the time
drops from about 80 minutes to about five minutes.

[saugustine]

I have some tests nearing completion, but want to get started with the feedback now.

[jgorbe]

libunwind/src/FrameHeaderCache.hpp

46

Do we need any synchronization here if there are multiple threads?

122

This line is redundant, Current has just been initialized to Unused. Did you want to explicitly set Current on each branch? If so, maybe something like this would be clearer?

CacheEntry *Current = nullptr;

if (Unused != nullptr) {
  Current = Unused;
  Unused = Unused->Next;
} else {
  Current = MostRecentlyUsed;
  // ... etc ...
}

in any case, I think changing the condition to Unused != nullptr would be a win, because at least to me it reads more easily as "it there are unused entries...".

[saugustine]

Update for upstream comments.

[saugustine]

libunwind/src/FrameHeaderCache.hpp

46

Good question. We don't because dl_iterate_phdr already holds the load lock and therefore does all the synchronization for us. That isn't obvious at all from reading the code, so adding a comment to that effect.

[saugustine]

Add missing comment.

[jgorbe]

I think it looks good now. My only issue is that it seems to rely on a couple of glibc-specific features: glibc modifying the fields adds and subs in dl_phdr_info when loading/unloading libraries (which this patch uses to know when to invalidate the cache), and dl_iterate_phdr holding a lock (which the patch relies on to avoid races while accessing the cache). What other libc implementations do we support? Do they share these behaviors we rely on here?

[saugustine]

In D75954#1917512, @jgorbe wrote:

I think it looks good now. My only issue is that it seems to rely on a couple of glibc-specific features: glibc modifying the fields adds and subs in dl_phdr_info when loading/unloading libraries (which this patch uses to know when to invalidate the cache), and dl_iterate_phdr holding a lock (which the patch relies on to avoid races while accessing the cache). What other libc implementations do we support? Do they share these behaviors we rely on here?

Freebsd has the dlpi_adds and dlpi_subs are both in freebsd since at least 2012, and musl too. I'm pretty sure the provide equal synchronization guarantees, otherwise they wouldn't be compatible with glibc. And looking at the similar libgcc code, it appears that libgcc also relies on such synchronization.

So I do believe we are OK from that perspective. If it comes to it, we could add a configure-time option, but I'm hoping to avoid that.

[saugustine]

Add tests, and minor formatting changes.

[saugustine]

Update test to only run when relevant.

[jgorbe]

Thanks for doing the extra work of adding a test. Just one final nit.

libunwind/test/frameheadercache_test.pass.cpp

3

I think referring to AddressSpace.hpp for the reasoning behind the ugly #ifdef chain is fine, but I'd add a note about the intention. Suggestion:

// Run the test only in configurations where the caching system is used.
// This #if chain...

[saugustine]

Correct the "do not run" cases to match the logic in AddressSpace.hpp.

[saugustine]

fix comment

[vvereschaka]

Hello @saugustine,

here is failed libunwind test on Aarch64 toolchain builder
http://lab.llvm.org:8011/builders/llvm-clang-win-x-aarch64/builds/5660

• FAIL: libunwind:: frameheadercache_test.pass.cpp

with a set of similar errors:

C:\buildbot\as-builder-2\llvm-clang-win-x-aarch64\llvm-project\libunwind\test/../src/Registers.hpp:3158:59: error: unused parameter 'regNum' [-Werror,-Wunused-parameter]

inline bool Registers_mips_newabi::validFloatRegister(int regNum) const {

would you take care of it?

[dim]

It seems that after this change, I'm getting sporadic lld segfaults in libunwind, which look like:

Core was generated by `/usr/obj/share/dim/src/freebsd/clang1100-import/amd64.amd64/tmp/usr/bin/ld --sys'.
Program terminated with signal SIGSEGV, Segmentation fault.
#0  0x0000000002479166 in libunwind::findUnwindSectionsByPhdr(dl_phdr_info*, unsigned long, void*) ()
[Current thread is 1 (LWP 100282)]
(gdb) bt
#0  0x0000000002479166 in libunwind::findUnwindSectionsByPhdr(dl_phdr_info*, unsigned long, void*) ()
#1  0x000000000247a67c in libunwind::UnwindCursor<libunwind::LocalAddressSpace, libunwind::Registers_x86_64>::setInfoBasedOnIPRegister(bool) ()
#2  0x000000000247927a in unw_init_local ()
#3  0x0000000002477ba8 in _Unwind_Backtrace ()
#4  0x0000000002416bb1 in backtrace ()
#5  0x0000000001097c83 in llvm::sys::PrintStackTrace(llvm::raw_ostream&) ()
#6  0x0000000001096105 in llvm::sys::RunSignalHandlers() ()
#7  0x0000000001098676 in SignalHandler(int) ()
#8  0x0000000002437c70 in handle_signal ()
#9  0x0000000002437248 in thr_sighandler ()
#10 <signal handler called>
#11 0x0000000002479166 in libunwind::findUnwindSectionsByPhdr(dl_phdr_info*, unsigned long, void*) ()
#12 0x000000000247a67c in libunwind::UnwindCursor<libunwind::LocalAddressSpace, libunwind::Registers_x86_64>::setInfoBasedOnIPRegister(bool) ()
#13 0x000000000247927a in unw_init_local ()
#14 0x000000000247884c in unwind_phase2_forced ()
#15 0x0000000002478b43 in _Unwind_ForcedUnwind ()
#16 0x00000000024421b6 in thread_unwind ()
#17 0x000000000244211f in _pthread_exit_mask ()
#18 0x000000000244208b in pthread_exit ()
#19 0x000000000243fcf3 in thread_start ()
#20 0x0000000000000000 in ?? ()
Backtrace stopped: Cannot access memory at address 0x7fffdfbfc000

When I look at the code, it appears that it has inlined FrameHeaderCache::add(), and goes into the else part:

Current = MostRecentlyUsed;
CacheEntry *Previous = nullptr;
while (Current->Next != nullptr) {
  Previous = Current;
  Current = Current->Next;
}

However, it enters that part with MostRecentlyUsed being nullptr, and this causes a segfault in the expression while (Current->Next != nullptr).

Would it make sense for MostRecentlyUsed to ever be null at this point, and if so, shouldn't the code be mitigating this? And if MostRecentlyUsed should never be null, what could be the reason that it is?

[dim]

I turned on _LIBUNWIND_DEBUG_FRAMEHEADER_CACHE, and indeed such segfaults appear immediately after the message libunwind: FrameHeaderCache reset. That means FrameHeaderCache::MostRecentlyUsed has just been set to nullptr ...

[dim]

Hm, the static FrameHeaderCache ProcessFrameHeaderCache; is biting us here, at least in a multithreaded process like lld, which is the process that is crashing for me all the time now. I added some instrumentation, which shows the problem by adding a thread ID to each log message, and by adding an assert in FrameHeaderCache::add() that MostRecentlyUsed != nullptr:

cc -target x86_64-unknown-freebsd13.0 --sysroot=/usr/obj/usr/src/amd64.amd64/tmp -B/usr/obj/usr/src/amd64.amd64/tmp/usr/bin -Wl,--no-undefined -Wl,--version-script=/usr/src/contrib/com_err/version-script.map   -fstack-protector-strong -shared -Wl,-x -Wl,--fatal-warnings -Wl,--warn-shared-textrel  -o libcom_err.so.5.full -Wl,-soname,libcom_err.so.5  `NM='nm' NMFLAGS='' lorder com_err.pico error.pico |  tsort -q`
libunwind FrameHeaderCache.hpp(57)[tid=0x803805a00]: FrameHeaderCache reset
libunwind FrameHeaderCache.hpp(130)[tid=0x803805000]: UIS=0x7fffdfdfc9e0
libunwind FrameHeaderCache.hpp(130)[tid=0x803805500]: UIS=0x7fffdfbfb9e0
libunwind FrameHeaderCache.hpp(140)[tid=0x803805500]: Unused == nullptr, MostRecentlyUsed=0x0
libunwind FrameHeaderCache.hpp(140)[tid=0x803805000]: Unused == nullptr, MostRecentlyUsed=0x0
Assertion failed: (MostRecentlyUsed != nullptr), function add, file FrameHeaderCache.hpp, line 141.
libunwind FrameHeaderCache.hpp(130)[tid=0x803805a00]: UIS=0x7fffdf9fa9e0
libunwind FrameHeaderCache.hpp(134)[tid=0x803805a00]: Unused != nullptr
PLEASE submit a bug report to https://bugs.freebsd.org/submit/ and include the crash backtrace.
libunwind FrameHeaderCache.hpp(161)[tid=0x803805a00]: FrameHeaderCache add [b060b0 - 256ec70)
cc: error: unable to execute command: Segmentation fault (core dumped)
cc: error: linker command failed due to signal (use -v to see invocation)

So what you see here is that thread 0x803805a00 resets, then thread 0x803805000 and 0x803805500 simultaneously invoke FrameHeaderCache::add(), and that leads to both Unused and MostRecentlyUsed being nulllptr, resulting in the crash.

It looks like the need for some locking in this FrameHeaderCache was completely overlooked? Or at least, having a cache per thread would make locking unnecessary, but it would cost more memory.

@hans in the state this is in now, I would suggest this to be reverted for 11.0, otherwise you will end up with a seriously broken release for multi-threaded programs.

[saugustine]

In D75954#2219870, @dim wrote:

It looks like the need for some locking in this FrameHeaderCache was completely overlooked? Or at least, having a cache per thread would make locking unnecessary, but it would cost more memory.

Well, not _completely_ overlooked. Looks like glibc locks things and other libc's don't. Should be easy to add a lock here for non glibc targets.

[hans]

In D75954#2220392, @saugustine wrote:

In D75954#2219870, @dim wrote:

It looks like the need for some locking in this FrameHeaderCache was completely overlooked? Or at least, having a cache per thread would make locking unnecessary, but it would cost more memory.

Well, not _completely_ overlooked. Looks like glibc locks things and other libc's don't. Should be easy to add a lock here for non glibc targets.

Sterling, do you think this will be fixed soon so we can get it in the llvm 11 release?

[saugustine]

In D75954#2223238, @hans wrote:

In D75954#2220392, @saugustine wrote:

In D75954#2219870, @dim wrote:

It looks like the need for some locking in this FrameHeaderCache was completely overlooked? Or at least, having a cache per thread would make locking unnecessary, but it would cost more memory.

Well, not _completely_ overlooked. Looks like glibc locks things and other libc's don't. Should be easy to add a lock here for non glibc targets.

Sterling, do you think this will be fixed soon so we can get it in the llvm 11 release?

It works great right now for glibc-based systems--in fact, Google uses it internally in production systems right now, today.

I am sending a patch shortly to allow enabling and disabling this cache at configure time.

[hans]

Sterling, do you think this will be fixed soon so we can get it in the llvm 11 release?

It works great right now for glibc-based systems--in fact, Google uses it internally in production systems right now, today.

I am sending a patch shortly to allow enabling and disabling this cache at configure time.

That was https://reviews.llvm.org/D86163 and it's been cherry-picked to 11.x.

libunwind/src/AddressSpace.hpp

struct _LIBUNWIND_HIDDEN dl_iterate_cb_data {
   uintptr_t targetAddr;
 };
 
 #if defined(_LIBUNWIND_SUPPORT_DWARF_UNWIND)
   #if !defined(_LIBUNWIND_SUPPORT_DWARF_INDEX)
     #error "_LIBUNWIND_SUPPORT_DWARF_UNWIND requires _LIBUNWIND_SUPPORT_DWARF_INDEX on this platform."
   #endif
 
+#include "FrameHeaderCache.hpp"
+
+// There should be just one of these per process.
+static FrameHeaderCache ProcessFrameHeaderCache;
+
 static bool checkAddrInSegment(const Elf_Phdr *phdr, size_t image_base,
                                dl_iterate_cb_data *cbdata) {
   if (phdr->p_type == PT_LOAD) {
     uintptr_t begin = image_base + phdr->p_vaddr;
     uintptr_t end = begin + phdr->p_memsz;
     if (cbdata->targetAddr >= begin && cbdata->targetAddr < end) {
       cbdata->sects->dso_base = begin;
       cbdata->sects->dwarf_section_length = phdr->p_memsz;
       return true;
     }
   }
   return false;
 }
 
-int findUnwindSectionsByPhdr(struct dl_phdr_info *pinfo, size_t, void *data) {
+int findUnwindSectionsByPhdr(struct dl_phdr_info *pinfo, size_t pinfo_size,
+                             void *data) {
   auto cbdata = static_cast<dl_iterate_cb_data *>(data);
   if (pinfo->dlpi_phnum == 0 || cbdata->targetAddr < pinfo->dlpi_addr)
     return 0;
+  if (ProcessFrameHeaderCache.find(pinfo, pinfo_size, data))
+    return 1;
 
   Elf_Addr image_base = calculateImageBase(pinfo);
   bool found_obj = false;
   bool found_hdr = false;
 
   // Third phdr is usually the executable phdr.
   if (pinfo->dlpi_phnum > 2)
     found_obj = checkAddrInSegment(&pinfo->dlpi_phdr[2], image_base, cbdata);
if (!found_hdr && phdr->p_type == PT_GNU_EH_FRAME) {
       found_hdr = EHHeaderParser<LocalAddressSpace>::decodeEHHdr(
           *cbdata->addressSpace, eh_frame_hdr_start, phdr->p_memsz,
           hdrInfo);
       if (found_hdr)
         cbdata->sects->dwarf_section = hdrInfo.eh_frame_ptr;
     } else if (!found_obj) {
       found_obj = checkAddrInSegment(phdr, image_base, cbdata);
     }
-    if (found_obj && found_hdr)
+    if (found_obj && found_hdr) {
+      ProcessFrameHeaderCache.add(cbdata->sects);
       return 1;
     }
+  }
   cbdata->sects->dwarf_section_length = 0;
   return 0;
 }
 
 #else  // defined(LIBUNWIND_SUPPORT_DWARF_UNWIND)
 // Given all the #ifdef's above, the code here is for
 // defined(LIBUNWIND_ARM_EHABI)
 

libunwind/src/FrameHeaderCache.hpp

+//===-FrameHeaderCache.hpp ------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+// Cache the elf program headers necessary to unwind the stack more efficiently
+// in the presence of many dsos.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef __FRAMEHEADER_CACHE_HPP__
+#define __FRAMEHEADER_CACHE_HPP__
+
+#include "config.h"
+#include <limits.h>
+
+#ifdef _LIBUNWIND_DEBUG_FRAMEHEADER_CACHE
+#define _LIBUNWIND_FRAMEHEADERCACHE_TRACE0(x) _LIBUNWIND_LOG0(x)
+#define _LIBUNWIND_FRAMEHEADERCACHE_TRACE(msg, ...)                            \
+  _LIBUNWIND_LOG(msg, __VA_ARGS__)
+#else
+#define _LIBUNWIND_FRAMEHEADERCACHE_TRACE0(x)
+#define _LIBUNWIND_FRAMEHEADERCACHE_TRACE(msg, ...)
+#endif
+
+// This cache should only be be used from within a dl_iterate_phdr callback.
+// dl_iterate_phdr does the necessary synchronization to prevent problems
+// with concurrent access via the libc load lock. Adding synchronization
+// for other uses is possible, but not currently done.
+
+class _LIBUNWIND_HIDDEN FrameHeaderCache {
+  struct CacheEntry {
+    uintptr_t LowPC() { return Info.dso_base; };
+    uintptr_t HighPC() { return Info.dso_base + Info.dwarf_section_length; };
+    UnwindInfoSections Info;
+    CacheEntry *Next;
+  };
+
+  static const size_t kCacheEntryCount = 8;
+
+  // Can't depend on the C++ standard library in libunwind, so use an array to
+  // allocate the entries, and two linked lists for ordering unused and recently
+  // used entries.  FIXME: Would the the extra memory for a doubly-linked list
+  // be better than the runtime cost of traversing a very short singly-linked
+  // list on a cache miss? The entries themselves are all small and consecutive,
+  // so unlikely to cause page faults when following the pointers. The memory
+  // spent on additional pointers could also be spent on more entries.
+
+  CacheEntry Entries[kCacheEntryCount];
+  CacheEntry *MostRecentlyUsed;
+  CacheEntry *Unused;
+
+  void resetCache() {
+    _LIBUNWIND_FRAMEHEADERCACHE_TRACE0("FrameHeaderCache reset");
+    MostRecentlyUsed = nullptr;
+    Unused = &Entries[0];
+    for (size_t i = 0; i < kCacheEntryCount - 1; i++) {
+      Entries[i].Next = &Entries[i + 1];
+    }
+    Entries[kCacheEntryCount - 1].Next = nullptr;
+  }
+
+  bool cacheNeedsReset(dl_phdr_info *PInfo) {
+    // C libraries increment dl_phdr_info.adds and dl_phdr_info.subs when
+    // loading and unloading shared libraries. If these values change between
+    // iterations of dl_iterate_phdr, then invalidate the cache.
+
+    // These are static to avoid needing an initializer, and unsigned long long
+    // because that is their type within the extended dl_phdr_info.  Initialize
+    // these to something extremely unlikely to be found upon the first call to
+    // dl_iterate_phdr.
+    static unsigned long long LastAdds = ULLONG_MAX;
+    static unsigned long long LastSubs = ULLONG_MAX;
+    if (PInfo->dlpi_adds != LastAdds || PInfo->dlpi_subs != LastSubs) {
+      // Resetting the entire cache is a big hammer, but this path is rare--
+      // usually just on the very first call, when the cache is empty anyway--so
+      // added complexity doesn't buy much.
+      LastAdds = PInfo->dlpi_adds;
+      LastSubs = PInfo->dlpi_subs;
+      resetCache();
+      return true;
+    }
+    return false;
+  }
+
+public:
+  bool find(dl_phdr_info *PInfo, size_t, void *data) {
+    if (cacheNeedsReset(PInfo) || MostRecentlyUsed == nullptr)
+      return false;
+
+    auto *CBData = static_cast<dl_iterate_cb_data *>(data);
+    CacheEntry *Current = MostRecentlyUsed;
+    CacheEntry *Previous = nullptr;
+    while (Current != nullptr) {
+      _LIBUNWIND_FRAMEHEADERCACHE_TRACE(
+          "FrameHeaderCache check %lx in [%lx - %lx)", CBData->targetAddr,
+          Current->LowPC(), Current->HighPC());
+      if (Current->LowPC() <= CBData->targetAddr &&
+          CBData->targetAddr < Current->HighPC()) {
+        _LIBUNWIND_FRAMEHEADERCACHE_TRACE(
+            "FrameHeaderCache hit %lx in [%lx - %lx)", CBData->targetAddr,
+            Current->LowPC(), Current->HighPC());
+        if (Previous) {
+          // If there is no Previous, then Current is already the
+          // MostRecentlyUsed, and no need to move it up.
+          Previous->Next = Current->Next;
+          Current->Next = MostRecentlyUsed;
+          MostRecentlyUsed = Current;
+        }
+        *CBData->sects = Current->Info;
+        return true;
+      }
+      Previous = Current;
+      Current = Current->Next;
+    }
+    _LIBUNWIND_FRAMEHEADERCACHE_TRACE("FrameHeaderCache miss for address %lx",
+                                      CBData->targetAddr);
+    return false;
+  }
+
+  void add(const UnwindInfoSections *UIS) {
+    CacheEntry *Current = nullptr;
+
+    if (Unused != nullptr) {
+      Current = Unused;
+      Unused = Unused->Next;
+    } else {
+      Current = MostRecentlyUsed;
+      CacheEntry *Previous = nullptr;
+      while (Current->Next != nullptr) {
+        Previous = Current;
+        Current = Current->Next;
+      }
+      Previous->Next = nullptr;
+      _LIBUNWIND_FRAMEHEADERCACHE_TRACE("FrameHeaderCache evict [%lx - %lx)",
+                                        Current->LowPC(), Current->HighPC());
+    }
+
+    Current->Info = *UIS;
+    Current->Next = MostRecentlyUsed;
+    MostRecentlyUsed = Current;
+    _LIBUNWIND_FRAMEHEADERCACHE_TRACE("FrameHeaderCache add [%lx - %lx)",
+                                      MostRecentlyUsed->LowPC(),
+                                      MostRecentlyUsed->HighPC());
+  }
+};
+
+#endif // __FRAMEHEADER_CACHE_HPP__

libunwind/test/frameheadercache_test.pass.cpp

+// The other libunwind tests don't test internal interfaces, so the include path
+// is a little wonky.
+#include "../src/config.h"
+
+// Only run this test under supported configurations.
+// This #if chain is ugly, but see the comments in AddressSpace.hpp for
+// the reasoning.
+
+#ifdef __APPLE__
+int main() { return 0; }
+#elif defined(_LIBUNWIND_SUPPORT_DWARF_UNWIND) && defined(_LIBUNWIND_IS_BAREMETAL)
+int main() { return 0; }
+#elif defined(_LIBUNWIND_ARM_EHABI) && defined(_LIBUNWIND_IS_BAREMETAL)
+int main() { return 0; }
+#elif defined(_LIBUNWIND_SUPPORT_DWARF_UNWIND) && defined(_WIN32)
+int main() { return 0; }
+#elif defined(_LIBUNWIND_SUPPORT_SEH_UNWIND) && defined(_WIN32)
+int main() { return 0; }
+#elif defined(_LIBUNWIND_ARM_EHABI) && defined(__BIONIC__)
+int main() { return 0; }
+#elif defined(_LIBUNWIND_ARM_EHABI) || defined(_LIBUNWIND_SUPPORT_DWARF_UNWIND)
+
+#include <link.h>
+#include <stdio.h>
+
+// This file defines several of the data structures needed here,
+// and includes FrameHeaderCache.hpp as well.
+#include "../src/AddressSpace.hpp"
+
+#define kBaseAddr 0xFFF000
+#define kDwarfSectionLength 0xFF
+
+using namespace libunwind;
+
+int main() {
+  FrameHeaderCache FHC;
+  struct dl_phdr_info PInfo;
+  memset(&PInfo, 0, sizeof(PInfo));
+  // The cache itself should only care about these two fields--they
+  // tell the cache to invalidate or not; everything else is handled
+  // by AddressSpace.hpp.
+  PInfo.dlpi_adds = 6;
+  PInfo.dlpi_subs = 7;
+
+  UnwindInfoSections UIS;
+  UIS.dso_base = kBaseAddr;
+  UIS.dwarf_section_length = kDwarfSectionLength;
+  dl_iterate_cb_data CBData;
+  // Unused by the cache.
+  CBData.addressSpace = nullptr;
+  CBData.sects = &UIS;
+  CBData.targetAddr = kBaseAddr + 1;
+
+  // Nothing present, shouldn't find.
+  if (FHC.find(&PInfo, 0, &CBData))
+    abort();
+  FHC.add(&UIS);
+  // Just added. Should find.
+  if (!FHC.find(&PInfo, 0, &CBData))
+    abort();
+  // Cache is invalid. Shouldn't find.
+  PInfo.dlpi_adds++;
+  if (FHC.find(&PInfo, 0, &CBData))
+    abort();
+
+  FHC.add(&UIS);
+  CBData.targetAddr = kBaseAddr - 1;
+  // Shouldn't find something outside of the addresses.
+  if (FHC.find(&PInfo, 0, &CBData))
+    abort();
+  // Add enough things to the cache that the entry is evicted.
+  for (int i = 0; i < 9; i++) {
+    UIS.dso_base = kBaseAddr + (kDwarfSectionLength * i);
+    FHC.add(&UIS);
+  }
+  CBData.targetAddr = kBaseAddr;
+  // Should have been evicted.
+  if (FHC.find(&PInfo, 0, &CBData))
+    abort();
+  return 0;
+}
+#endif