contrib/compiler-rt/lib/sanitizer_common/sanitizer_stackdepot.cc

   1 //===-- sanitizer_stackdepot.cc -------------------------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file is shared between AddressSanitizer and ThreadSanitizer
  11 // run-time libraries.
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "sanitizer_stackdepot.h"
  15
  16 #include "sanitizer_common.h"
  17 #include "sanitizer_stackdepotbase.h"
  18
  19 namespace __sanitizer {
  20
  21 struct StackDepotNode {
  22   StackDepotNode *link;
  23   u32 id;
  24   atomic_uint32_t hash_and_use_count; // hash_bits : 12; use_count : 20;
  25   u32 size;
  26   u32 tag;
  27   uptr stack[1];  // [size]
  28
  29   static const u32 kTabSizeLog = 20;
  30   // Lower kTabSizeLog bits are equal for all items in one bucket.
  31   // We use these bits to store the per-stack use counter.
  32   static const u32 kUseCountBits = kTabSizeLog;
  33   static const u32 kMaxUseCount = 1 << kUseCountBits;
  34   static const u32 kUseCountMask = (1 << kUseCountBits) - 1;
  35   static const u32 kHashMask = ~kUseCountMask;
  36
  37   typedef StackTrace args_type;
  38   bool eq(u32 hash, const args_type &args) const {
  39     u32 hash_bits =
  40         atomic_load(&hash_and_use_count, memory_order_relaxed) & kHashMask;
  41     if ((hash & kHashMask) != hash_bits || args.size != size || args.tag != tag)
  42       return false;
  43     uptr i = 0;
  44     for (; i < size; i++) {
  45       if (stack[i] != args.trace[i]) return false;
  46     }
  47     return true;
  48   }
  49   static uptr storage_size(const args_type &args) {
  50     return sizeof(StackDepotNode) + (args.size - 1) * sizeof(uptr);
  51   }
  52   static u32 hash(const args_type &args) {
  53     // murmur2
  54     const u32 m = 0x5bd1e995;
  55     const u32 seed = 0x9747b28c;
  56     const u32 r = 24;
  57     u32 h = seed ^ (args.size * sizeof(uptr));
  58     for (uptr i = 0; i < args.size; i++) {
  59       u32 k = args.trace[i];
  60       k *= m;
  61       k ^= k >> r;
  62       k *= m;
  63       h *= m;
  64       h ^= k;
  65     }
  66     h ^= h >> 13;
  67     h *= m;
  68     h ^= h >> 15;
  69     return h;
  70   }
  71   static bool is_valid(const args_type &args) {
  72     return args.size > 0 && args.trace;
  73   }
  74   void store(const args_type &args, u32 hash) {
  75     atomic_store(&hash_and_use_count, hash & kHashMask, memory_order_relaxed);
  76     size = args.size;
  77     tag = args.tag;
  78     internal_memcpy(stack, args.trace, size * sizeof(uptr));
  79   }
  80   args_type load() const {
  81     return args_type(&stack[0], size, tag);
  82   }
  83   StackDepotHandle get_handle() { return StackDepotHandle(this); }
  84
  85   typedef StackDepotHandle handle_type;
  86 };
  87
  88 COMPILER_CHECK(StackDepotNode::kMaxUseCount == (u32)kStackDepotMaxUseCount);
  89
  90 u32 StackDepotHandle::id() { return node_->id; }
  91 int StackDepotHandle::use_count() {
  92   return atomic_load(&node_->hash_and_use_count, memory_order_relaxed) &
  93          StackDepotNode::kUseCountMask;
  94 }
  95 void StackDepotHandle::inc_use_count_unsafe() {
  96   u32 prev =
  97       atomic_fetch_add(&node_->hash_and_use_count, 1, memory_order_relaxed) &
  98       StackDepotNode::kUseCountMask;
  99   CHECK_LT(prev + 1, StackDepotNode::kMaxUseCount);
 100 }
 101
 102 // FIXME(dvyukov): this single reserved bit is used in TSan.
 103 typedef StackDepotBase<StackDepotNode, 1, StackDepotNode::kTabSizeLog>
 104     StackDepot;
 105 static StackDepot theDepot;
 106
 107 StackDepotStats *StackDepotGetStats() {
 108   return theDepot.GetStats();
 109 }
 110
 111 u32 StackDepotPut(StackTrace stack) {
 112   StackDepotHandle h = theDepot.Put(stack);
 113   return h.valid() ? h.id() : 0;
 114 }
 115
 116 StackDepotHandle StackDepotPut_WithHandle(StackTrace stack) {
 117   return theDepot.Put(stack);
 118 }
 119
 120 StackTrace StackDepotGet(u32 id) {
 121   return theDepot.Get(id);
 122 }
 123
 124 void StackDepotLockAll() {
 125   theDepot.LockAll();
 126 }
 127
 128 void StackDepotUnlockAll() {
 129   theDepot.UnlockAll();
 130 }
 131
 132 bool StackDepotReverseMap::IdDescPair::IdComparator(
 133     const StackDepotReverseMap::IdDescPair &a,
 134     const StackDepotReverseMap::IdDescPair &b) {
 135   return a.id < b.id;
 136 }
 137
 138 StackDepotReverseMap::StackDepotReverseMap() {
 139   map_.reserve(StackDepotGetStats()->n_uniq_ids + 100);
 140   for (int idx = 0; idx < StackDepot::kTabSize; idx++) {
 141     atomic_uintptr_t *p = &theDepot.tab[idx];
 142     uptr v = atomic_load(p, memory_order_consume);
 143     StackDepotNode *s = (StackDepotNode*)(v & ~1);
 144     for (; s; s = s->link) {
 145       IdDescPair pair = {s->id, s};
 146       map_.push_back(pair);
 147     }
 148   }
 149   Sort(map_.data(), map_.size(), &IdDescPair::IdComparator);
 150 }
 151
 152 StackTrace StackDepotReverseMap::Get(u32 id) {
 153   if (!map_.size())
 154     return StackTrace();
 155   IdDescPair pair = {id, nullptr};
 156   uptr idx =
 157       InternalLowerBound(map_, 0, map_.size(), pair, IdDescPair::IdComparator);
 158   if (idx > map_.size() || map_[idx].id != id)
 159     return StackTrace();
 160   return map_[idx].desc->load();
 161 }
 162
 163 } // namespace __sanitizer