Home | History | Annotate | Download | only in sanitizer_common 
      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_(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   InternalSort(&map_, 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 = InternalBinarySearch(map_, 0, map_.size(), pair,
    157                                   IdDescPair::IdComparator);
    158   if (idx > map_.size())
    159     return StackTrace();
    160   return map_[idx].desc->load();
    161 }
    162 
    163 } // namespace __sanitizer
    164