aboutsummaryrefslogtreecommitdiffstats
path: root/contrib/libs/libunwind/src/FrameHeaderCache.hpp
blob: 54d5d33c3cd7edea5d9021886d7a6d75d2957258 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
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 <limits.h>

#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 libc 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.text_segment_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 traversing 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) {
    // C libraries increment 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<dl_iterate_cb_data *>(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__