libsanitizer/tsan/tsan_sync.cc

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