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 #ifdef SCUDO_FUZZ
66   // Use smaller table sizes for fuzzing in order to reduce input size.
67   static const uptr TabBits = 4;
68 #else
69   static const uptr TabBits = 16;
70 #endif
71   static const uptr TabSize = 1 << TabBits;
72   static const uptr TabMask = TabSize - 1;
73   atomic_u32 Tab[TabSize] = {};
74 
75 #ifdef SCUDO_FUZZ
76   static const uptr RingBits = 4;
77 #else
78   static const uptr RingBits = 19;
79 #endif
80   static const uptr RingSize = 1 << RingBits;
81   static const uptr RingMask = RingSize - 1;
82   atomic_u64 Ring[RingSize] = {};
83 
84 public:
85   // Insert hash of the stack trace [Begin, End) into the stack depot, and
86   // return the hash.
87   u32 insert(uptr *Begin, uptr *End) {
88     MurMur2HashBuilder B;
89     for (uptr *I = Begin; I != End; ++I)
90       B.add(u32(*I) >> 2);
91     u32 Hash = B.get();
92 
93     u32 Pos = Hash & TabMask;
94     u32 RingPos = atomic_load_relaxed(&Tab[Pos]);
95     u64 Entry = atomic_load_relaxed(&Ring[RingPos]);
96     u64 Id = (u64(End - Begin) << 33) | (u64(Hash) << 1) | 1;
97     if (Entry == Id)
98       return Hash;
99 
100     ScopedLock Lock(RingEndMu);
101     RingPos = RingEnd;
102     atomic_store_relaxed(&Tab[Pos], RingPos);
103     atomic_store_relaxed(&Ring[RingPos], Id);
104     for (uptr *I = Begin; I != End; ++I) {
105       RingPos = (RingPos + 1) & RingMask;
106       atomic_store_relaxed(&Ring[RingPos], *I);
107     }
108     RingEnd = (RingPos + 1) & RingMask;
109     return Hash;
110   }
111 
112   // Look up a stack trace by hash. Returns true if successful. The trace may be
113   // accessed via operator[] passing indexes between *RingPosPtr and
114   // *RingPosPtr + *SizePtr.
115   bool find(u32 Hash, uptr *RingPosPtr, uptr *SizePtr) const {
116     u32 Pos = Hash & TabMask;
117     u32 RingPos = atomic_load_relaxed(&Tab[Pos]);
118     if (RingPos >= RingSize)
119       return false;
120     u64 Entry = atomic_load_relaxed(&Ring[RingPos]);
121     u64 HashWithTagBit = (u64(Hash) << 1) | 1;
122     if ((Entry & 0x1ffffffff) != HashWithTagBit)
123       return false;
124     u32 Size = u32(Entry >> 33);
125     if (Size >= RingSize)
126       return false;
127     *RingPosPtr = (RingPos + 1) & RingMask;
128     *SizePtr = Size;
129     MurMur2HashBuilder B;
130     for (uptr I = 0; I != Size; ++I) {
131       RingPos = (RingPos + 1) & RingMask;
132       B.add(u32(atomic_load_relaxed(&Ring[RingPos])) >> 2);
133     }
134     return B.get() == Hash;
135   }
136 
137   u64 operator[](uptr RingPos) const {
138     return atomic_load_relaxed(&Ring[RingPos & RingMask]);
139   }
140 };
141 
142 } // namespace scudo
143 
144 #endif // SCUDO_STACK_DEPOT_H_
145