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