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