150 lines · plain
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-exception6//7// Cache the elf program headers necessary to unwind the stack more efficiently8// 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_CACHE19#define _LIBUNWIND_FRAMEHEADERCACHE_TRACE0(x) _LIBUNWIND_LOG0(x)20#define _LIBUNWIND_FRAMEHEADERCACHE_TRACE(msg, ...) \21 _LIBUNWIND_LOG(msg, __VA_ARGS__)22#else23#define _LIBUNWIND_FRAMEHEADERCACHE_TRACE0(x)24#define _LIBUNWIND_FRAMEHEADERCACHE_TRACE(msg, ...)25#endif26 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 problems29// with concurrent access via the libc load lock. Adding synchronization30// for other uses is possible, but not currently done.31 32class _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 to43 // allocate the entries, and two linked lists for ordering unused and recently44 // used entries. FIXME: Would the extra memory for a doubly-linked list45 // be better than the runtime cost of traversing a very short singly-linked46 // 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 memory48 // 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 when66 // loading and unloading shared libraries. If these values change between67 // iterations of dl_iterate_phdr, then invalidate the cache.68 69 // These are static to avoid needing an initializer, and unsigned long long70 // because that is their type within the extended dl_phdr_info. Initialize71 // these to something extremely unlikely to be found upon the first call to72 // 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--so78 // 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 87public: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 the106 // 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