libsanitizer/sanitizer_common/sanitizer_stackdepot.cc

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