1 //===-- stack_depot.h -------------------------------------------*- C++ -*-===// 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 //===----------------------------------------------------------------------===// 8 9 #ifndef SCUDO_STACK_DEPOT_H_ 10 #define SCUDO_STACK_DEPOT_H_ 11 12 #include "atomic_helpers.h" 13 #include "mutex.h" 14 15 namespace scudo { 16 17 class MurMur2HashBuilder { 18 static const u32 M = 0x5bd1e995; 19 static const u32 Seed = 0x9747b28c; 20 static const u32 R = 24; 21 u32 H; 22 23 public: 24 explicit MurMur2HashBuilder(u32 Init = 0) { H = Seed ^ Init; } 25 void add(u32 K) { 26 K *= M; 27 K ^= K >> R; 28 K *= M; 29 H *= M; 30 H ^= K; 31 } 32 u32 get() { 33 u32 X = H; 34 X ^= X >> 13; 35 X *= M; 36 X ^= X >> 15; 37 return X; 38 } 39 }; 40 41 class StackDepot { 42 HybridMutex RingEndMu; 43 u32 RingEnd = 0; 44 45 // This data structure stores a stack trace for each allocation and 46 // deallocation when stack trace recording is enabled, that may be looked up 47 // using a hash of the stack trace. The lower bits of the hash are an index 48 // into the Tab array, which stores an index into the Ring array where the 49 // stack traces are stored. As the name implies, Ring is a ring buffer, so a 50 // stack trace may wrap around to the start of the array. 51 // 52 // Each stack trace in Ring is prefixed by a stack trace marker consisting of 53 // a fixed 1 bit in bit 0 (this allows disambiguation between stack frames 54 // and stack trace markers in the case where instruction pointers are 4-byte 55 // aligned, as they are on arm64), the stack trace hash in bits 1-32, and the 56 // size of the stack trace in bits 33-63. 57 // 58 // The insert() function is potentially racy in its accesses to the Tab and 59 // Ring arrays, but find() is resilient to races in the sense that, barring 60 // hash collisions, it will either return the correct stack trace or no stack 61 // trace at all, even if two instances of insert() raced with one another. 62 // This is achieved by re-checking the hash of the stack trace before 63 // returning the trace. 64 65 #if SCUDO_SMALL_STACK_DEPOT 66 static const uptr TabBits = 4; 67 #else 68 static const uptr TabBits = 16; 69 #endif 70 static const uptr TabSize = 1 << TabBits; 71 static const uptr TabMask = TabSize - 1; 72 atomic_u32 Tab[TabSize] = {}; 73 74 #if SCUDO_SMALL_STACK_DEPOT 75 static const uptr RingBits = 4; 76 #else 77 static const uptr RingBits = 19; 78 #endif 79 static const uptr RingSize = 1 << RingBits; 80 static const uptr RingMask = RingSize - 1; 81 atomic_u64 Ring[RingSize] = {}; 82 83 public: 84 // Insert hash of the stack trace [Begin, End) into the stack depot, and 85 // return the hash. 86 u32 insert(uptr *Begin, uptr *End) { 87 MurMur2HashBuilder B; 88 for (uptr *I = Begin; I != End; ++I) 89 B.add(u32(*I) >> 2); 90 u32 Hash = B.get(); 91 92 u32 Pos = Hash & TabMask; 93 u32 RingPos = atomic_load_relaxed(&Tab[Pos]); 94 u64 Entry = atomic_load_relaxed(&Ring[RingPos]); 95 u64 Id = (u64(End - Begin) << 33) | (u64(Hash) << 1) | 1; 96 if (Entry == Id) 97 return Hash; 98 99 ScopedLock Lock(RingEndMu); 100 RingPos = RingEnd; 101 atomic_store_relaxed(&Tab[Pos], RingPos); 102 atomic_store_relaxed(&Ring[RingPos], Id); 103 for (uptr *I = Begin; I != End; ++I) { 104 RingPos = (RingPos + 1) & RingMask; 105 atomic_store_relaxed(&Ring[RingPos], *I); 106 } 107 RingEnd = (RingPos + 1) & RingMask; 108 return Hash; 109 } 110 111 // Look up a stack trace by hash. Returns true if successful. The trace may be 112 // accessed via operator[] passing indexes between *RingPosPtr and 113 // *RingPosPtr + *SizePtr. 114 bool find(u32 Hash, uptr *RingPosPtr, uptr *SizePtr) const { 115 u32 Pos = Hash & TabMask; 116 u32 RingPos = atomic_load_relaxed(&Tab[Pos]); 117 if (RingPos >= RingSize) 118 return false; 119 u64 Entry = atomic_load_relaxed(&Ring[RingPos]); 120 u64 HashWithTagBit = (u64(Hash) << 1) | 1; 121 if ((Entry & 0x1ffffffff) != HashWithTagBit) 122 return false; 123 u32 Size = u32(Entry >> 33); 124 if (Size >= RingSize) 125 return false; 126 *RingPosPtr = (RingPos + 1) & RingMask; 127 *SizePtr = Size; 128 MurMur2HashBuilder B; 129 for (uptr I = 0; I != Size; ++I) { 130 RingPos = (RingPos + 1) & RingMask; 131 B.add(u32(atomic_load_relaxed(&Ring[RingPos])) >> 2); 132 } 133 return B.get() == Hash; 134 } 135 136 u64 operator[](uptr RingPos) const { 137 return atomic_load_relaxed(&Ring[RingPos & RingMask]); 138 } 139 }; 140 141 } // namespace scudo 142 143 #endif // SCUDO_STACK_DEPOT_H_ 144