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