libsanitizer/sanitizer_common/sanitizer_stackdepot.cpp

   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
  22 namespace __sanitizer {
  23
  24 struct 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
  53 static StackStore stackStore;
  54
  55 // FIXME(dvyukov): this single reserved bit is used in TSan.
  56 typedef StackDepotBase<StackDepotNode, 1, StackDepotNode::kTabSizeLog>
  57     StackDepot;
  58 static StackDepot theDepot;
  59 // Keep mutable data out of frequently access nodes to improve caching
  60 // efficiency.
  61 static TwoLevelMap<atomic_uint32_t, StackDepot::kNodesSize1,
  62                    StackDepot::kNodesSize2>
  63     useCounts;
  64
  65 int StackDepotHandle::use_count() const {
  66   return atomic_load_relaxed(&useCounts[id_]);
  67 }
  68
  69 void StackDepotHandle::inc_use_count_unsafe() {
  70   atomic_fetch_add(&useCounts[id_], 1, memory_order_relaxed);
  71 }
  72
  73 uptr StackDepotNode::allocated() {
  74   return stackStore.Allocated() + useCounts.MemoryUsage();
  75 }
  76
  77 static 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
  92 namespace {
  93
  94 class 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
 124 static CompressThread compress_thread;
 125
 126 void 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
 151 void 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
 157 void 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
 173 void 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
 187 void CompressThread::Unlock() { mutex_.Unlock(); }
 188
 189 }  // namespace
 190
 191 void 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
 200 StackDepotNode::args_type StackDepotNode::load(u32 id) const {
 201   if (!store_id)
 202     return {};
 203   return stackStore.Load(store_id);
 204 }
 205
 206 StackDepotStats StackDepotGetStats() { return theDepot.GetStats(); }
 207
 208 u32 StackDepotPut(StackTrace stack) { return theDepot.Put(stack); }
 209
 210 StackDepotHandle StackDepotPut_WithHandle(StackTrace stack) {
 211   return StackDepotNode::get_handle(theDepot.Put(stack));
 212 }
 213
 214 StackTrace StackDepotGet(u32 id) {
 215   return theDepot.Get(id);
 216 }
 217
 218 void StackDepotLockAll() {
 219   theDepot.LockAll();
 220   compress_thread.LockAndStop();
 221   stackStore.LockAll();
 222 }
 223
 224 void StackDepotUnlockAll() {
 225   stackStore.UnlockAll();
 226   compress_thread.Unlock();
 227   theDepot.UnlockAll();
 228 }
 229
 230 void StackDepotPrintAll() {
 231 #if !SANITIZER_GO
 232   theDepot.PrintAll();
 233 #endif
 234 }
 235
 236 void StackDepotStopBackgroundThread() { compress_thread.Stop(); }
 237
 238 StackDepotHandle StackDepotNode::get_handle(u32 id) {
 239   return StackDepotHandle(&theDepot.nodes[id], id);
 240 }
 241
 242 void StackDepotTestOnlyUnmap() {
 243   theDepot.TestOnlyUnmap();
 244   stackStore.TestOnlyUnmap();
 245 }
 246
 247 } // namespace __sanitizer