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 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__ 150