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