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 #include "sanitizer_common.h"
  16 #include "sanitizer_internal_defs.h"
  17 #include "sanitizer_mutex.h"
  18 #include "sanitizer_atomic.h"
  19
  20 namespace __sanitizer {
  21
  22 const int kTabSize = 1024 * 1024;  // Hash table size.
  23 const int kPartBits = 8;
  24 const int kPartShift = sizeof(u32) * 8 - kPartBits - 1;
  25 const int kPartCount = 1 << kPartBits;  // Number of subparts in the table.
  26 const int kPartSize = kTabSize / kPartCount;
  27 const int kMaxId = 1 << kPartShift;
  28
  29 struct StackDesc {
  30   StackDesc *link;
  31   u32 id;
  32   u32 hash;
  33   uptr size;
  34   uptr stack[1];  // [size]
  35 };
  36
  37 static struct {
  38   StaticSpinMutex mtx;  // Protects alloc of new blocks for region allocator.
  39   atomic_uintptr_t region_pos;  // Region allocator for StackDesc's.
  40   atomic_uintptr_t region_end;
  41   atomic_uintptr_t tab[kTabSize];  // Hash table of StackDesc's.
  42   atomic_uint32_t seq[kPartCount];  // Unique id generators.
  43 } depot;
  44
  45 static StackDepotStats stats;
  46
  47 StackDepotStats *StackDepotGetStats() {
  48   return &stats;
  49 }
  50
  51 static u32 hash(const uptr *stack, uptr size) {
  52   // murmur2
  53   const u32 m = 0x5bd1e995;
  54   const u32 seed = 0x9747b28c;
  55   const u32 r = 24;
  56   u32 h = seed ^ (size * sizeof(uptr));
  57   for (uptr i = 0; i < size; i++) {
  58     u32 k = stack[i];
  59     k *= m;
  60     k ^= k >> r;
  61     k *= m;
  62     h *= m;
  63     h ^= k;
  64   }
  65   h ^= h >> 13;
  66   h *= m;
  67   h ^= h >> 15;
  68   return h;
  69 }
  70
  71 static StackDesc *tryallocDesc(uptr memsz) {
  72   // Optimisic lock-free allocation, essentially try to bump the region ptr.
  73   for (;;) {
  74     uptr cmp = atomic_load(&depot.region_pos, memory_order_acquire);
  75     uptr end = atomic_load(&depot.region_end, memory_order_acquire);
  76     if (cmp == 0 || cmp + memsz > end)
  77       return 0;
  78     if (atomic_compare_exchange_weak(
  79         &depot.region_pos, &cmp, cmp + memsz,
  80         memory_order_acquire))
  81       return (StackDesc*)cmp;
  82   }
  83 }
  84
  85 static StackDesc *allocDesc(uptr size) {
  86   // First, try to allocate optimisitically.
  87   uptr memsz = sizeof(StackDesc) + (size - 1) * sizeof(uptr);
  88   StackDesc *s = tryallocDesc(memsz);
  89   if (s)
  90     return s;
  91   // If failed, lock, retry and alloc new superblock.
  92   SpinMutexLock l(&depot.mtx);
  93   for (;;) {
  94     s = tryallocDesc(memsz);
  95     if (s)
  96       return s;
  97     atomic_store(&depot.region_pos, 0, memory_order_relaxed);
  98     uptr allocsz = 64 * 1024;
  99     if (allocsz < memsz)
 100       allocsz = memsz;
 101     uptr mem = (uptr)MmapOrDie(allocsz, "stack depot");
 102     stats.mapped += allocsz;
 103     atomic_store(&depot.region_end, mem + allocsz, memory_order_release);
 104     atomic_store(&depot.region_pos, mem, memory_order_release);
 105   }
 106 }
 107
 108 static u32 find(StackDesc *s, const uptr *stack, uptr size, u32 hash) {
 109   // Searches linked list s for the stack, returns its id.
 110   for (; s; s = s->link) {
 111     if (s->hash == hash && s->size == size) {
 112       uptr i = 0;
 113       for (; i < size; i++) {
 114         if (stack[i] != s->stack[i])
 115           break;
 116       }
 117       if (i == size)
 118         return s->id;
 119     }
 120   }
 121   return 0;
 122 }
 123
 124 static StackDesc *lock(atomic_uintptr_t *p) {
 125   // Uses the pointer lsb as mutex.
 126   for (int i = 0;; i++) {
 127     uptr cmp = atomic_load(p, memory_order_relaxed);
 128     if ((cmp & 1) == 0
 129         && atomic_compare_exchange_weak(p, &cmp, cmp | 1,
 130                                         memory_order_acquire))
 131       return (StackDesc*)cmp;
 132     if (i < 10)
 133       proc_yield(10);
 134     else
 135       internal_sched_yield();
 136   }
 137 }
 138
 139 static void unlock(atomic_uintptr_t *p, StackDesc *s) {
 140   DCHECK_EQ((uptr)s & 1, 0);
 141   atomic_store(p, (uptr)s, memory_order_release);
 142 }
 143
 144 u32 StackDepotPut(const uptr *stack, uptr size) {
 145   if (stack == 0 || size == 0)
 146     return 0;
 147   uptr h = hash(stack, size);
 148   atomic_uintptr_t *p = &depot.tab[h % kTabSize];
 149   uptr v = atomic_load(p, memory_order_consume);
 150   StackDesc *s = (StackDesc*)(v & ~1);
 151   // First, try to find the existing stack.
 152   u32 id = find(s, stack, size, h);
 153   if (id)
 154     return id;
 155   // If failed, lock, retry and insert new.
 156   StackDesc *s2 = lock(p);
 157   if (s2 != s) {
 158     id = find(s2, stack, size, h);
 159     if (id) {
 160       unlock(p, s2);
 161       return id;
 162     }
 163   }
 164   uptr part = (h % kTabSize) / kPartSize;
 165   id = atomic_fetch_add(&depot.seq[part], 1, memory_order_relaxed) + 1;
 166   stats.n_uniq_ids++;
 167   CHECK_LT(id, kMaxId);
 168   id |= part << kPartShift;
 169   CHECK_NE(id, 0);
 170   CHECK_EQ(id & (1u << 31), 0);
 171   s = allocDesc(size);
 172   s->id = id;
 173   s->hash = h;
 174   s->size = size;
 175   internal_memcpy(s->stack, stack, size * sizeof(uptr));
 176   s->link = s2;
 177   unlock(p, s);
 178   return id;
 179 }
 180
 181 const uptr *StackDepotGet(u32 id, uptr *size) {
 182   if (id == 0)
 183     return 0;
 184   CHECK_EQ(id & (1u << 31), 0);
 185   // High kPartBits contain part id, so we need to scan at most kPartSize lists.
 186   uptr part = id >> kPartShift;
 187   for (int i = 0; i != kPartSize; i++) {
 188     uptr idx = part * kPartSize + i;
 189     CHECK_LT(idx, kTabSize);
 190     atomic_uintptr_t *p = &depot.tab[idx];
 191     uptr v = atomic_load(p, memory_order_consume);
 192     StackDesc *s = (StackDesc*)(v & ~1);
 193     for (; s; s = s->link) {
 194       if (s->id == id) {
 195         *size = s->size;
 196         return s->stack;
 197       }
 198     }
 199   }
 200   *size = 0;
 201   return 0;
 202 }
 203
 204 bool StackDepotReverseMap::IdDescPair::IdComparator(
 205     const StackDepotReverseMap::IdDescPair &a,
 206     const StackDepotReverseMap::IdDescPair &b) {
 207   return a.id < b.id;
 208 }
 209
 210 StackDepotReverseMap::StackDepotReverseMap()
 211     : map_(StackDepotGetStats()->n_uniq_ids + 100) {
 212   for (int idx = 0; idx < kTabSize; idx++) {
 213     atomic_uintptr_t *p = &depot.tab[idx];
 214     uptr v = atomic_load(p, memory_order_consume);
 215     StackDesc *s = (StackDesc*)(v & ~1);
 216     for (; s; s = s->link) {
 217       IdDescPair pair = {s->id, s};
 218       map_.push_back(pair);
 219     }
 220   }
 221   InternalSort(&map_, map_.size(), IdDescPair::IdComparator);
 222 }
 223
 224 const uptr *StackDepotReverseMap::Get(u32 id, uptr *size) {
 225   if (!map_.size()) return 0;
 226   IdDescPair pair = {id, 0};
 227   uptr idx = InternalBinarySearch(map_, 0, map_.size(), pair,
 228                                   IdDescPair::IdComparator);
 229   if (idx > map_.size()) {
 230     *size = 0;
 231     return 0;
 232   }
 233   StackDesc *desc = map_[idx].desc;
 234   *size = desc->size;
 235   return desc->stack;
 236 }
 237
 238 }  // namespace __sanitizer