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
15namespace scudo {
16
17class MurMur2HashBuilder {
18  static const u32 M = 0x5bd1e995;
19  static const u32 Seed = 0x9747b28c;
20  static const u32 R = 24;
21  u32 H;
22
23public:
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
41class 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
84public:
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