libsanitizer/tsan/tsan_sync.cpp

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