contrib/compiler-rt/lib/tsan/rtl/tsan_sync.cc

   1 //===-- tsan_sync.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 a part of ThreadSanitizer (TSan), a race detector.
  11 //
  12 //===----------------------------------------------------------------------===//
  13 #include "sanitizer_common/sanitizer_placement_new.h"
  14 #include "tsan_sync.h"
  15 #include "tsan_rtl.h"
  16 #include "tsan_mman.h"
  17
  18 namespace __tsan {
  19
  20 void DDMutexInit(ThreadState *thr, uptr pc, SyncVar *s);
  21
  22 SyncVar::SyncVar()
  23     : mtx(MutexTypeSyncVar, StatMtxSyncVar) {
  24   Reset(0);
  25 }
  26
  27 void SyncVar::Init(ThreadState *thr, uptr pc, uptr addr, u64 uid) {
  28   this->addr = addr;
  29   this->uid = uid;
  30   this->next = 0;
  31
  32   creation_stack_id = 0;
  33   if (!SANITIZER_GO)  // Go does not use them
  34     creation_stack_id = CurrentStackId(thr, pc);
  35   if (common_flags()->detect_deadlocks)
  36     DDMutexInit(thr, pc, this);
  37 }
  38
  39 void SyncVar::Reset(Processor *proc) {
  40   uid = 0;
  41   creation_stack_id = 0;
  42   owner_tid = kInvalidTid;
  43   last_lock = 0;
  44   recursion = 0;
  45   atomic_store_relaxed(&flags, 0);
  46
  47   if (proc == 0) {
  48     CHECK_EQ(clock.size(), 0);
  49     CHECK_EQ(read_clock.size(), 0);
  50   } else {
  51     clock.Reset(&proc->clock_cache);
  52     read_clock.Reset(&proc->clock_cache);
  53   }
  54 }
  55
  56 MetaMap::MetaMap()
  57     : block_alloc_("heap block allocator")
  58     , sync_alloc_("sync allocator") {
  59   atomic_store(&uid_gen_, 0, memory_order_relaxed);
  60 }
  61
  62 void MetaMap::AllocBlock(ThreadState *thr, uptr pc, uptr p, uptr sz) {
  63   u32 idx = block_alloc_.Alloc(&thr->proc()->block_cache);
  64   MBlock *b = block_alloc_.Map(idx);
  65   b->siz = sz;
  66   b->tag = 0;
  67   b->tid = thr->tid;
  68   b->stk = CurrentStackId(thr, pc);
  69   u32 *meta = MemToMeta(p);
  70   DCHECK_EQ(*meta, 0);
  71   *meta = idx | kFlagBlock;
  72 }
  73
  74 uptr MetaMap::FreeBlock(Processor *proc, uptr p) {
  75   MBlock* b = GetBlock(p);
  76   if (b == 0)
  77     return 0;
  78   uptr sz = RoundUpTo(b->siz, kMetaShadowCell);
  79   FreeRange(proc, p, sz);
  80   return sz;
  81 }
  82
  83 bool MetaMap::FreeRange(Processor *proc, uptr p, uptr sz) {
  84   bool has_something = false;
  85   u32 *meta = MemToMeta(p);
  86   u32 *end = MemToMeta(p + sz);
  87   if (end == meta)
  88     end++;
  89   for (; meta < end; meta++) {
  90     u32 idx = *meta;
  91     if (idx == 0) {
  92       // Note: don't write to meta in this case -- the block can be huge.
  93       continue;
  94     }
  95     *meta = 0;
  96     has_something = true;
  97     while (idx != 0) {
  98       if (idx & kFlagBlock) {
  99         block_alloc_.Free(&proc->block_cache, idx & ~kFlagMask);
 100         break;
 101       } else if (idx & kFlagSync) {
 102         DCHECK(idx & kFlagSync);
 103         SyncVar *s = sync_alloc_.Map(idx & ~kFlagMask);
 104         u32 next = s->next;
 105         s->Reset(proc);
 106         sync_alloc_.Free(&proc->sync_cache, idx & ~kFlagMask);
 107         idx = next;
 108       } else {
 109         CHECK(0);
 110       }
 111     }
 112   }
 113   return has_something;
 114 }
 115
 116 // ResetRange removes all meta objects from the range.
 117 // It is called for large mmap-ed regions. The function is best-effort wrt
 118 // freeing of meta objects, because we don't want to page in the whole range
 119 // which can be huge. The function probes pages one-by-one until it finds a page
 120 // without meta objects, at this point it stops freeing meta objects. Because
 121 // thread stacks grow top-down, we do the same starting from end as well.
 122 void MetaMap::ResetRange(Processor *proc, uptr p, uptr sz) {
 123   if (SANITIZER_GO) {
 124     // UnmapOrDie/MmapFixedNoReserve does not work on Windows,
 125     // so we do the optimization only for C/C++.
 126     FreeRange(proc, p, sz);
 127     return;
 128   }
 129   const uptr kMetaRatio = kMetaShadowCell / kMetaShadowSize;
 130   const uptr kPageSize = GetPageSizeCached() * kMetaRatio;
 131   if (sz <= 4 * kPageSize) {
 132     // If the range is small, just do the normal free procedure.
 133     FreeRange(proc, p, sz);
 134     return;
 135   }
 136   // First, round both ends of the range to page size.
 137   uptr diff = RoundUp(p, kPageSize) - p;
 138   if (diff != 0) {
 139     FreeRange(proc, p, diff);
 140     p += diff;
 141     sz -= diff;
 142   }
 143   diff = p + sz - RoundDown(p + sz, kPageSize);
 144   if (diff != 0) {
 145     FreeRange(proc, p + sz - diff, diff);
 146     sz -= diff;
 147   }
 148   // Now we must have a non-empty page-aligned range.
 149   CHECK_GT(sz, 0);
 150   CHECK_EQ(p, RoundUp(p, kPageSize));
 151   CHECK_EQ(sz, RoundUp(sz, kPageSize));
 152   const uptr p0 = p;
 153   const uptr sz0 = sz;
 154   // Probe start of the range.
 155   for (uptr checked = 0; sz > 0; checked += kPageSize) {
 156     bool has_something = FreeRange(proc, p, kPageSize);
 157     p += kPageSize;
 158     sz -= kPageSize;
 159     if (!has_something && checked > (128 << 10))
 160       break;
 161   }
 162   // Probe end of the range.
 163   for (uptr checked = 0; sz > 0; checked += kPageSize) {
 164     bool has_something = FreeRange(proc, p + sz - kPageSize, kPageSize);
 165     sz -= kPageSize;
 166     // Stacks grow down, so sync object are most likely at the end of the region
 167     // (if it is a stack). The very end of the stack is TLS and tsan increases
 168     // TLS by at least 256K, so check at least 512K.
 169     if (!has_something && checked > (512 << 10))
 170       break;
 171   }
 172   // Finally, page out the whole range (including the parts that we've just
 173   // freed). Note: we can't simply madvise, because we need to leave a zeroed
 174   // range (otherwise __tsan_java_move can crash if it encounters a left-over
 175   // meta objects in java heap).
 176   uptr metap = (uptr)MemToMeta(p0);
 177   uptr metasz = sz0 / kMetaRatio;
 178   UnmapOrDie((void*)metap, metasz);
 179   if (!MmapFixedNoReserve(metap, metasz))
 180     Die();
 181 }
 182
 183 MBlock* MetaMap::GetBlock(uptr p) {
 184   u32 *meta = MemToMeta(p);
 185   u32 idx = *meta;
 186   for (;;) {
 187     if (idx == 0)
 188       return 0;
 189     if (idx & kFlagBlock)
 190       return block_alloc_.Map(idx & ~kFlagMask);
 191     DCHECK(idx & kFlagSync);
 192     SyncVar * s = sync_alloc_.Map(idx & ~kFlagMask);
 193     idx = s->next;
 194   }
 195 }
 196
 197 SyncVar* MetaMap::GetOrCreateAndLock(ThreadState *thr, uptr pc,
 198                               uptr addr, bool write_lock) {
 199   return GetAndLock(thr, pc, addr, write_lock, true);
 200 }
 201
 202 SyncVar* MetaMap::GetIfExistsAndLock(uptr addr, bool write_lock) {
 203   return GetAndLock(0, 0, addr, write_lock, false);
 204 }
 205
 206 SyncVar* MetaMap::GetAndLock(ThreadState *thr, uptr pc,
 207                              uptr addr, bool write_lock, bool create) {
 208   u32 *meta = MemToMeta(addr);
 209   u32 idx0 = *meta;
 210   u32 myidx = 0;
 211   SyncVar *mys = 0;
 212   for (;;) {
 213     u32 idx = idx0;
 214     for (;;) {
 215       if (idx == 0)
 216         break;
 217       if (idx & kFlagBlock)
 218         break;
 219       DCHECK(idx & kFlagSync);
 220       SyncVar * s = sync_alloc_.Map(idx & ~kFlagMask);
 221       if (s->addr == addr) {
 222         if (myidx != 0) {
 223           mys->Reset(thr->proc());
 224           sync_alloc_.Free(&thr->proc()->sync_cache, myidx);
 225         }
 226         if (write_lock)
 227           s->mtx.Lock();
 228         else
 229           s->mtx.ReadLock();
 230         return s;
 231       }
 232       idx = s->next;
 233     }
 234     if (!create)
 235       return 0;
 236     if (*meta != idx0) {
 237       idx0 = *meta;
 238       continue;
 239     }
 240
 241     if (myidx == 0) {
 242       const u64 uid = atomic_fetch_add(&uid_gen_, 1, memory_order_relaxed);
 243       myidx = sync_alloc_.Alloc(&thr->proc()->sync_cache);
 244       mys = sync_alloc_.Map(myidx);
 245       mys->Init(thr, pc, addr, uid);
 246     }
 247     mys->next = idx0;
 248     if (atomic_compare_exchange_strong((atomic_uint32_t*)meta, &idx0,
 249         myidx | kFlagSync, memory_order_release)) {
 250       if (write_lock)
 251         mys->mtx.Lock();
 252       else
 253         mys->mtx.ReadLock();
 254       return mys;
 255     }
 256   }
 257 }
 258
 259 void MetaMap::MoveMemory(uptr src, uptr dst, uptr sz) {
 260   // src and dst can overlap,
 261   // there are no concurrent accesses to the regions (e.g. stop-the-world).
 262   CHECK_NE(src, dst);
 263   CHECK_NE(sz, 0);
 264   uptr diff = dst - src;
 265   u32 *src_meta = MemToMeta(src);
 266   u32 *dst_meta = MemToMeta(dst);
 267   u32 *src_meta_end = MemToMeta(src + sz);
 268   uptr inc = 1;
 269   if (dst > src) {
 270     src_meta = MemToMeta(src + sz) - 1;
 271     dst_meta = MemToMeta(dst + sz) - 1;
 272     src_meta_end = MemToMeta(src) - 1;
 273     inc = -1;
 274   }
 275   for (; src_meta != src_meta_end; src_meta += inc, dst_meta += inc) {
 276     CHECK_EQ(*dst_meta, 0);
 277     u32 idx = *src_meta;
 278     *src_meta = 0;
 279     *dst_meta = idx;
 280     // Patch the addresses in sync objects.
 281     while (idx != 0) {
 282       if (idx & kFlagBlock)
 283         break;
 284       CHECK(idx & kFlagSync);
 285       SyncVar *s = sync_alloc_.Map(idx & ~kFlagMask);
 286       s->addr += diff;
 287       idx = s->next;
 288     }
 289   }
 290 }
 291
 292 void MetaMap::OnProcIdle(Processor *proc) {
 293   block_alloc_.FlushCache(&proc->block_cache);
 294   sync_alloc_.FlushCache(&proc->sync_cache);
 295 }
 296
 297 }  // namespace __tsan