1//===-- sanitizer_stackdepot.cpp ------------------------------------------===//
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// This file is shared between AddressSanitizer and ThreadSanitizer
10// run-time libraries.
11//===----------------------------------------------------------------------===//
12
13#include "sanitizer_stackdepot.h"
14
15#include "sanitizer_atomic.h"
16#include "sanitizer_common.h"
17#include "sanitizer_hash.h"
18#include "sanitizer_mutex.h"
19#include "sanitizer_stack_store.h"
20#include "sanitizer_stackdepotbase.h"
21
22namespace __sanitizer {
23
24struct StackDepotNode {
25  using hash_type = u64;
26  hash_type stack_hash;
27  u32 link;
28  StackStore::Id store_id;
29
30  static const u32 kTabSizeLog = SANITIZER_ANDROID ? 16 : 20;
31
32  typedef StackTrace args_type;
33  bool eq(hash_type hash, const args_type &args) const {
34    return hash == stack_hash;
35  }
36  static uptr allocated();
37  static hash_type hash(const args_type &args) {
38    MurMur2Hash64Builder H(args.size * sizeof(uptr));
39    for (uptr i = 0; i < args.size; i++) H.add(args.trace[i]);
40    H.add(args.tag);
41    return H.get();
42  }
43  static bool is_valid(const args_type &args) {
44    return args.size > 0 && args.trace;
45  }
46  void store(u32 id, const args_type &args, hash_type hash);
47  args_type load(u32 id) const;
48  static StackDepotHandle get_handle(u32 id);
49
50  typedef StackDepotHandle handle_type;
51};
52
53static StackStore stackStore;
54
55// FIXME(dvyukov): this single reserved bit is used in TSan.
56typedef StackDepotBase<StackDepotNode, 1, StackDepotNode::kTabSizeLog>
57    StackDepot;
58static StackDepot theDepot;
59// Keep mutable data out of frequently access nodes to improve caching
60// efficiency.
61static TwoLevelMap<atomic_uint32_t, StackDepot::kNodesSize1,
62                   StackDepot::kNodesSize2>
63    useCounts;
64
65int StackDepotHandle::use_count() const {
66  return atomic_load_relaxed(&useCounts[id_]);
67}
68
69void StackDepotHandle::inc_use_count_unsafe() {
70  atomic_fetch_add(&useCounts[id_], 1, memory_order_relaxed);
71}
72
73uptr StackDepotNode::allocated() {
74  return stackStore.Allocated() + useCounts.MemoryUsage();
75}
76
77static void CompressStackStore() {
78  u64 start = Verbosity() >= 1 ? MonotonicNanoTime() : 0;
79  uptr diff = stackStore.Pack(static_cast<StackStore::Compression>(
80      Abs(common_flags()->compress_stack_depot)));
81  if (!diff)
82    return;
83  if (Verbosity() >= 1) {
84    u64 finish = MonotonicNanoTime();
85    uptr total_before = theDepot.GetStats().allocated + diff;
86    VPrintf(1, "%s: StackDepot released %zu KiB out of %zu KiB in %llu ms\n",
87            SanitizerToolName, diff >> 10, total_before >> 10,
88            (finish - start) / 1000000);
89  }
90}
91
92namespace {
93
94class CompressThread {
95 public:
96  constexpr CompressThread() = default;
97  void NewWorkNotify();
98  void Stop();
99  void LockAndStop() SANITIZER_NO_THREAD_SAFETY_ANALYSIS;
100  void Unlock() SANITIZER_NO_THREAD_SAFETY_ANALYSIS;
101
102 private:
103  enum class State {
104    NotStarted = 0,
105    Started,
106    Failed,
107    Stopped,
108  };
109
110  void Run();
111
112  bool WaitForWork() {
113    semaphore_.Wait();
114    return atomic_load(&run_, memory_order_acquire);
115  }
116
117  Semaphore semaphore_ = {};
118  StaticSpinMutex mutex_ = {};
119  State state_ SANITIZER_GUARDED_BY(mutex_) = State::NotStarted;
120  void *thread_ SANITIZER_GUARDED_BY(mutex_) = nullptr;
121  atomic_uint8_t run_ = {};
122};
123
124static CompressThread compress_thread;
125
126void CompressThread::NewWorkNotify() {
127  int compress = common_flags()->compress_stack_depot;
128  if (!compress)
129    return;
130  if (compress > 0 /* for testing or debugging */) {
131    SpinMutexLock l(&mutex_);
132    if (state_ == State::NotStarted) {
133      atomic_store(&run_, 1, memory_order_release);
134      CHECK_EQ(nullptr, thread_);
135      thread_ = internal_start_thread(
136          [](void *arg) -> void * {
137            reinterpret_cast<CompressThread *>(arg)->Run();
138            return nullptr;
139          },
140          this);
141      state_ = thread_ ? State::Started : State::Failed;
142    }
143    if (state_ == State::Started) {
144      semaphore_.Post();
145      return;
146    }
147  }
148  CompressStackStore();
149}
150
151void CompressThread::Run() {
152  VPrintf(1, "%s: StackDepot compression thread started\n", SanitizerToolName);
153  while (WaitForWork()) CompressStackStore();
154  VPrintf(1, "%s: StackDepot compression thread stopped\n", SanitizerToolName);
155}
156
157void CompressThread::Stop() {
158  void *t = nullptr;
159  {
160    SpinMutexLock l(&mutex_);
161    if (state_ != State::Started)
162      return;
163    state_ = State::Stopped;
164    CHECK_NE(nullptr, thread_);
165    t = thread_;
166    thread_ = nullptr;
167  }
168  atomic_store(&run_, 0, memory_order_release);
169  semaphore_.Post();
170  internal_join_thread(t);
171}
172
173void CompressThread::LockAndStop() {
174  mutex_.Lock();
175  if (state_ != State::Started)
176    return;
177  CHECK_NE(nullptr, thread_);
178
179  atomic_store(&run_, 0, memory_order_release);
180  semaphore_.Post();
181  internal_join_thread(thread_);
182  // Allow to restart after Unlock() if needed.
183  state_ = State::NotStarted;
184  thread_ = nullptr;
185}
186
187void CompressThread::Unlock() { mutex_.Unlock(); }
188
189}  // namespace
190
191void StackDepotNode::store(u32 id, const args_type &args, hash_type hash) {
192  stack_hash = hash;
193  uptr pack = 0;
194  store_id = stackStore.Store(args, &pack);
195  if (LIKELY(!pack))
196    return;
197  compress_thread.NewWorkNotify();
198}
199
200StackDepotNode::args_type StackDepotNode::load(u32 id) const {
201  if (!store_id)
202    return {};
203  return stackStore.Load(store_id);
204}
205
206StackDepotStats StackDepotGetStats() { return theDepot.GetStats(); }
207
208u32 StackDepotPut(StackTrace stack) { return theDepot.Put(stack); }
209
210StackDepotHandle StackDepotPut_WithHandle(StackTrace stack) {
211  return StackDepotNode::get_handle(theDepot.Put(stack));
212}
213
214StackTrace StackDepotGet(u32 id) {
215  return theDepot.Get(id);
216}
217
218void StackDepotLockBeforeFork() {
219  theDepot.LockBeforeFork();
220  compress_thread.LockAndStop();
221  stackStore.LockAll();
222}
223
224void StackDepotUnlockAfterFork(bool fork_child) {
225  stackStore.UnlockAll();
226  compress_thread.Unlock();
227  theDepot.UnlockAfterFork(fork_child);
228}
229
230void StackDepotPrintAll() {
231#if !SANITIZER_GO
232  theDepot.PrintAll();
233#endif
234}
235
236void StackDepotStopBackgroundThread() { compress_thread.Stop(); }
237
238StackDepotHandle StackDepotNode::get_handle(u32 id) {
239  return StackDepotHandle(&theDepot.nodes[id], id);
240}
241
242void StackDepotTestOnlyUnmap() {
243  theDepot.TestOnlyUnmap();
244  stackStore.TestOnlyUnmap();
245}
246
247} // namespace __sanitizer
248