libunwind/src/FrameHeaderCache.hpp

   1 //===-FrameHeaderCache.hpp ------------------------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 // Cache the elf program headers necessary to unwind the stack more efficiently
   8 // in the presence of many dsos.
   9 //
  10 //===----------------------------------------------------------------------===//
  11
  12 #ifndef __FRAMEHEADER_CACHE_HPP__
  13 #define __FRAMEHEADER_CACHE_HPP__
  14
  15 #include "config.h"
  16 #include <limits.h>
  17
  18 #ifdef _LIBUNWIND_DEBUG_FRAMEHEADER_CACHE
  19 #define _LIBUNWIND_FRAMEHEADERCACHE_TRACE0(x) _LIBUNWIND_LOG0(x)
  20 #define _LIBUNWIND_FRAMEHEADERCACHE_TRACE(msg, ...)                            \
  21   _LIBUNWIND_LOG(msg, __VA_ARGS__)
  22 #else
  23 #define _LIBUNWIND_FRAMEHEADERCACHE_TRACE0(x)
  24 #define _LIBUNWIND_FRAMEHEADERCACHE_TRACE(msg, ...)
  25 #endif
  26
  27 // This cache should only be be used from within a dl_iterate_phdr callback.
  28 // dl_iterate_phdr does the necessary synchronization to prevent problems
  29 // with concurrent access via the libc load lock. Adding synchronization
  30 // for other uses is possible, but not currently done.
  31
  32 class _LIBUNWIND_HIDDEN FrameHeaderCache {
  33   struct CacheEntry {
  34     uintptr_t LowPC() { return Info.dso_base; }
  35     uintptr_t HighPC() { return Info.dso_base + Info.text_segment_length; }
  36     UnwindInfoSections Info;
  37     CacheEntry *Next;
  38   };
  39
  40   static const size_t kCacheEntryCount = 8;
  41
  42   // Can't depend on the C++ standard library in libunwind, so use an array to
  43   // allocate the entries, and two linked lists for ordering unused and recently
  44   // used entries.  FIXME: Would the extra memory for a doubly-linked list
  45   // be better than the runtime cost of traversing a very short singly-linked
  46   // list on a cache miss? The entries themselves are all small and consecutive,
  47   // so unlikely to cause page faults when following the pointers. The memory
  48   // spent on additional pointers could also be spent on more entries.
  49
  50   CacheEntry Entries[kCacheEntryCount];
  51   CacheEntry *MostRecentlyUsed;
  52   CacheEntry *Unused;
  53
  54   void resetCache() {
  55     _LIBUNWIND_FRAMEHEADERCACHE_TRACE0("FrameHeaderCache reset");
  56     MostRecentlyUsed = nullptr;
  57     Unused = &Entries[0];
  58     for (size_t i = 0; i < kCacheEntryCount - 1; i++) {
  59       Entries[i].Next = &Entries[i + 1];
  60     }
  61     Entries[kCacheEntryCount - 1].Next = nullptr;
  62   }
  63
  64   bool cacheNeedsReset(dl_phdr_info *PInfo) {
  65     // C libraries increment dl_phdr_info.adds and dl_phdr_info.subs when
  66     // loading and unloading shared libraries. If these values change between
  67     // iterations of dl_iterate_phdr, then invalidate the cache.
  68
  69     // These are static to avoid needing an initializer, and unsigned long long
  70     // because that is their type within the extended dl_phdr_info.  Initialize
  71     // these to something extremely unlikely to be found upon the first call to
  72     // dl_iterate_phdr.
  73     static unsigned long long LastAdds = ULLONG_MAX;
  74     static unsigned long long LastSubs = ULLONG_MAX;
  75     if (PInfo->dlpi_adds != LastAdds || PInfo->dlpi_subs != LastSubs) {
  76       // Resetting the entire cache is a big hammer, but this path is rare--
  77       // usually just on the very first call, when the cache is empty anyway--so
  78       // added complexity doesn't buy much.
  79       LastAdds = PInfo->dlpi_adds;
  80       LastSubs = PInfo->dlpi_subs;
  81       resetCache();
  82       return true;
  83     }
  84     return false;
  85   }
  86
  87 public:
  88   bool find(dl_phdr_info *PInfo, size_t, void *data) {
  89     if (cacheNeedsReset(PInfo) || MostRecentlyUsed == nullptr)
  90       return false;
  91
  92     auto *CBData = static_cast<dl_iterate_cb_data *>(data);
  93     CacheEntry *Current = MostRecentlyUsed;
  94     CacheEntry *Previous = nullptr;
  95     while (Current != nullptr) {
  96       _LIBUNWIND_FRAMEHEADERCACHE_TRACE(
  97           "FrameHeaderCache check %lx in [%lx - %lx)", CBData->targetAddr,
  98           Current->LowPC(), Current->HighPC());
  99       if (Current->LowPC() <= CBData->targetAddr &&
 100           CBData->targetAddr < Current->HighPC()) {
 101         _LIBUNWIND_FRAMEHEADERCACHE_TRACE(
 102             "FrameHeaderCache hit %lx in [%lx - %lx)", CBData->targetAddr,
 103             Current->LowPC(), Current->HighPC());
 104         if (Previous) {
 105           // If there is no Previous, then Current is already the
 106           // MostRecentlyUsed, and no need to move it up.
 107           Previous->Next = Current->Next;
 108           Current->Next = MostRecentlyUsed;
 109           MostRecentlyUsed = Current;
 110         }
 111         *CBData->sects = Current->Info;
 112         return true;
 113       }
 114       Previous = Current;
 115       Current = Current->Next;
 116     }
 117     _LIBUNWIND_FRAMEHEADERCACHE_TRACE("FrameHeaderCache miss for address %lx",
 118                                       CBData->targetAddr);
 119     return false;
 120   }
 121
 122   void add(const UnwindInfoSections *UIS) {
 123     CacheEntry *Current = nullptr;
 124
 125     if (Unused != nullptr) {
 126       Current = Unused;
 127       Unused = Unused->Next;
 128     } else {
 129       Current = MostRecentlyUsed;
 130       CacheEntry *Previous = nullptr;
 131       while (Current->Next != nullptr) {
 132         Previous = Current;
 133         Current = Current->Next;
 134       }
 135       Previous->Next = nullptr;
 136       _LIBUNWIND_FRAMEHEADERCACHE_TRACE("FrameHeaderCache evict [%lx - %lx)",
 137                                         Current->LowPC(), Current->HighPC());
 138     }
 139
 140     Current->Info = *UIS;
 141     Current->Next = MostRecentlyUsed;
 142     MostRecentlyUsed = Current;
 143     _LIBUNWIND_FRAMEHEADERCACHE_TRACE("FrameHeaderCache add [%lx - %lx)",
 144                                       MostRecentlyUsed->LowPC(),
 145                                       MostRecentlyUsed->HighPC());
 146   }
 147 };
 148
 149 #endif // __FRAMEHEADER_CACHE_HPP__