diff --git a/libunwind/src/AddressSpace.hpp b/libunwind/src/AddressSpace.hpp --- a/libunwind/src/AddressSpace.hpp +++ b/libunwind/src/AddressSpace.hpp @@ -452,6 +452,11 @@ #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) { @@ -466,10 +471,13 @@ 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(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; @@ -496,8 +504,10 @@ } 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; diff --git a/libunwind/src/FrameHeaderCache.hpp b/libunwind/src/FrameHeaderCache.hpp new file mode 100644 --- /dev/null +++ b/libunwind/src/FrameHeaderCache.hpp @@ -0,0 +1,149 @@ +//===-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 + +#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 glibc 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 travsersing 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) { + // glibc increments 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(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__