1238901Sandrew//===-- tsan_sync.cc ------------------------------------------------------===// 2238901Sandrew// 3238901Sandrew// The LLVM Compiler Infrastructure 4238901Sandrew// 5238901Sandrew// This file is distributed under the University of Illinois Open Source 6238901Sandrew// License. See LICENSE.TXT for details. 7238901Sandrew// 8238901Sandrew//===----------------------------------------------------------------------===// 9238901Sandrew// 10238901Sandrew// This file is a part of ThreadSanitizer (TSan), a race detector. 11238901Sandrew// 12238901Sandrew//===----------------------------------------------------------------------===// 13238901Sandrew#include "sanitizer_common/sanitizer_placement_new.h" 14238901Sandrew#include "tsan_sync.h" 15238901Sandrew#include "tsan_rtl.h" 16238901Sandrew#include "tsan_mman.h" 17238901Sandrew 18238901Sandrewnamespace __tsan { 19238901Sandrew 20276789Sdimvoid DDMutexInit(ThreadState *thr, uptr pc, SyncVar *s); 21238901Sandrew 22276789SdimSyncVar::SyncVar() 23276789Sdim : mtx(MutexTypeSyncVar, StatMtxSyncVar) { 24276789Sdim Reset(0); 25238901Sandrew} 26238901Sandrew 27276789Sdimvoid SyncVar::Init(ThreadState *thr, uptr pc, uptr addr, u64 uid) { 28276789Sdim this->addr = addr; 29276789Sdim this->uid = uid; 30276789Sdim this->next = 0; 31276789Sdim 32276789Sdim creation_stack_id = 0; 33276789Sdim if (kCppMode) // Go does not use them 34276789Sdim creation_stack_id = CurrentStackId(thr, pc); 35276789Sdim if (common_flags()->detect_deadlocks) 36276789Sdim DDMutexInit(thr, pc, this); 37238901Sandrew} 38238901Sandrew 39276789Sdimvoid SyncVar::Reset(ThreadState *thr) { 40276789Sdim uid = 0; 41276789Sdim creation_stack_id = 0; 42276789Sdim owner_tid = kInvalidTid; 43276789Sdim last_lock = 0; 44276789Sdim recursion = 0; 45276789Sdim is_rw = 0; 46276789Sdim is_recursive = 0; 47276789Sdim is_broken = 0; 48276789Sdim is_linker_init = 0; 49276789Sdim 50276789Sdim if (thr == 0) { 51276789Sdim CHECK_EQ(clock.size(), 0); 52276789Sdim CHECK_EQ(read_clock.size(), 0); 53276789Sdim } else { 54276789Sdim clock.Reset(&thr->clock_cache); 55276789Sdim read_clock.Reset(&thr->clock_cache); 56238901Sandrew } 57238901Sandrew} 58238901Sandrew 59276789SdimMetaMap::MetaMap() { 60276789Sdim atomic_store(&uid_gen_, 0, memory_order_relaxed); 61245614Sandrew} 62245614Sandrew 63276789Sdimvoid MetaMap::AllocBlock(ThreadState *thr, uptr pc, uptr p, uptr sz) { 64276789Sdim u32 idx = block_alloc_.Alloc(&thr->block_cache); 65276789Sdim MBlock *b = block_alloc_.Map(idx); 66276789Sdim b->siz = sz; 67276789Sdim b->tid = thr->tid; 68276789Sdim b->stk = CurrentStackId(thr, pc); 69276789Sdim u32 *meta = MemToMeta(p); 70276789Sdim DCHECK_EQ(*meta, 0); 71276789Sdim *meta = idx | kFlagBlock; 72245614Sandrew} 73245614Sandrew 74276789Sdimuptr MetaMap::FreeBlock(ThreadState *thr, uptr pc, uptr p) { 75276789Sdim MBlock* b = GetBlock(p); 76276789Sdim if (b == 0) 77276789Sdim return 0; 78276789Sdim uptr sz = RoundUpTo(b->siz, kMetaShadowCell); 79276789Sdim FreeRange(thr, pc, p, sz); 80276789Sdim return sz; 81245614Sandrew} 82245614Sandrew 83288943Sdimbool MetaMap::FreeRange(ThreadState *thr, uptr pc, uptr p, uptr sz) { 84288943Sdim bool has_something = false; 85276789Sdim u32 *meta = MemToMeta(p); 86276789Sdim u32 *end = MemToMeta(p + sz); 87276789Sdim if (end == meta) 88276789Sdim end++; 89276789Sdim for (; meta < end; meta++) { 90276789Sdim u32 idx = *meta; 91288943Sdim if (idx == 0) { 92288943Sdim // Note: don't write to meta in this case -- the block can be huge. 93288943Sdim continue; 94288943Sdim } 95276789Sdim *meta = 0; 96288943Sdim has_something = true; 97288943Sdim while (idx != 0) { 98276789Sdim if (idx & kFlagBlock) { 99276789Sdim block_alloc_.Free(&thr->block_cache, idx & ~kFlagMask); 100276789Sdim break; 101276789Sdim } else if (idx & kFlagSync) { 102276789Sdim DCHECK(idx & kFlagSync); 103276789Sdim SyncVar *s = sync_alloc_.Map(idx & ~kFlagMask); 104276789Sdim u32 next = s->next; 105276789Sdim s->Reset(thr); 106276789Sdim sync_alloc_.Free(&thr->sync_cache, idx & ~kFlagMask); 107276789Sdim idx = next; 108276789Sdim } else { 109276789Sdim CHECK(0); 110238901Sandrew } 111238901Sandrew } 112238901Sandrew } 113288943Sdim return has_something; 114238901Sandrew} 115238901Sandrew 116288943Sdim// ResetRange removes all meta objects from the range. 117288943Sdim// It is called for large mmap-ed regions. The function is best-effort wrt 118288943Sdim// freeing of meta objects, because we don't want to page in the whole range 119288943Sdim// which can be huge. The function probes pages one-by-one until it finds a page 120288943Sdim// without meta objects, at this point it stops freeing meta objects. Because 121288943Sdim// thread stacks grow top-down, we do the same starting from end as well. 122288943Sdimvoid MetaMap::ResetRange(ThreadState *thr, uptr pc, uptr p, uptr sz) { 123288943Sdim const uptr kMetaRatio = kMetaShadowCell / kMetaShadowSize; 124288943Sdim const uptr kPageSize = GetPageSizeCached() * kMetaRatio; 125288943Sdim if (sz <= 4 * kPageSize) { 126288943Sdim // If the range is small, just do the normal free procedure. 127288943Sdim FreeRange(thr, pc, p, sz); 128288943Sdim return; 129288943Sdim } 130288943Sdim // First, round both ends of the range to page size. 131288943Sdim uptr diff = RoundUp(p, kPageSize) - p; 132288943Sdim if (diff != 0) { 133288943Sdim FreeRange(thr, pc, p, diff); 134288943Sdim p += diff; 135288943Sdim sz -= diff; 136288943Sdim } 137288943Sdim diff = p + sz - RoundDown(p + sz, kPageSize); 138288943Sdim if (diff != 0) { 139288943Sdim FreeRange(thr, pc, p + sz - diff, diff); 140288943Sdim sz -= diff; 141288943Sdim } 142288943Sdim // Now we must have a non-empty page-aligned range. 143288943Sdim CHECK_GT(sz, 0); 144288943Sdim CHECK_EQ(p, RoundUp(p, kPageSize)); 145288943Sdim CHECK_EQ(sz, RoundUp(sz, kPageSize)); 146288943Sdim const uptr p0 = p; 147288943Sdim const uptr sz0 = sz; 148288943Sdim // Probe start of the range. 149288943Sdim while (sz > 0) { 150288943Sdim bool has_something = FreeRange(thr, pc, p, kPageSize); 151288943Sdim p += kPageSize; 152288943Sdim sz -= kPageSize; 153288943Sdim if (!has_something) 154288943Sdim break; 155288943Sdim } 156288943Sdim // Probe end of the range. 157288943Sdim while (sz > 0) { 158288943Sdim bool has_something = FreeRange(thr, pc, p - kPageSize, kPageSize); 159288943Sdim sz -= kPageSize; 160288943Sdim if (!has_something) 161288943Sdim break; 162288943Sdim } 163288943Sdim // Finally, page out the whole range (including the parts that we've just 164288943Sdim // freed). Note: we can't simply madvise, because we need to leave a zeroed 165288943Sdim // range (otherwise __tsan_java_move can crash if it encounters a left-over 166288943Sdim // meta objects in java heap). 167288943Sdim uptr metap = (uptr)MemToMeta(p0); 168288943Sdim uptr metasz = sz0 / kMetaRatio; 169288943Sdim UnmapOrDie((void*)metap, metasz); 170288943Sdim MmapFixedNoReserve(metap, metasz); 171288943Sdim} 172288943Sdim 173276789SdimMBlock* MetaMap::GetBlock(uptr p) { 174276789Sdim u32 *meta = MemToMeta(p); 175276789Sdim u32 idx = *meta; 176276789Sdim for (;;) { 177276789Sdim if (idx == 0) 178276789Sdim return 0; 179276789Sdim if (idx & kFlagBlock) 180276789Sdim return block_alloc_.Map(idx & ~kFlagMask); 181276789Sdim DCHECK(idx & kFlagSync); 182276789Sdim SyncVar * s = sync_alloc_.Map(idx & ~kFlagMask); 183276789Sdim idx = s->next; 184245614Sandrew } 185238901Sandrew} 186238901Sandrew 187276789SdimSyncVar* MetaMap::GetOrCreateAndLock(ThreadState *thr, uptr pc, 188276789Sdim uptr addr, bool write_lock) { 189276789Sdim return GetAndLock(thr, pc, addr, write_lock, true); 190238901Sandrew} 191238901Sandrew 192276789SdimSyncVar* MetaMap::GetIfExistsAndLock(uptr addr) { 193276789Sdim return GetAndLock(0, 0, addr, true, false); 194238901Sandrew} 195238901Sandrew 196276789SdimSyncVar* MetaMap::GetAndLock(ThreadState *thr, uptr pc, 197276789Sdim uptr addr, bool write_lock, bool create) { 198276789Sdim u32 *meta = MemToMeta(addr); 199276789Sdim u32 idx0 = *meta; 200276789Sdim u32 myidx = 0; 201276789Sdim SyncVar *mys = 0; 202276789Sdim for (;;) { 203276789Sdim u32 idx = idx0; 204276789Sdim for (;;) { 205276789Sdim if (idx == 0) 206276789Sdim break; 207276789Sdim if (idx & kFlagBlock) 208276789Sdim break; 209276789Sdim DCHECK(idx & kFlagSync); 210276789Sdim SyncVar * s = sync_alloc_.Map(idx & ~kFlagMask); 211276789Sdim if (s->addr == addr) { 212276789Sdim if (myidx != 0) { 213276789Sdim mys->Reset(thr); 214276789Sdim sync_alloc_.Free(&thr->sync_cache, myidx); 215276789Sdim } 216276789Sdim if (write_lock) 217276789Sdim s->mtx.Lock(); 218276789Sdim else 219276789Sdim s->mtx.ReadLock(); 220276789Sdim return s; 221276789Sdim } 222276789Sdim idx = s->next; 223276789Sdim } 224276789Sdim if (!create) 225276789Sdim return 0; 226276789Sdim if (*meta != idx0) { 227276789Sdim idx0 = *meta; 228276789Sdim continue; 229276789Sdim } 230238901Sandrew 231276789Sdim if (myidx == 0) { 232276789Sdim const u64 uid = atomic_fetch_add(&uid_gen_, 1, memory_order_relaxed); 233276789Sdim myidx = sync_alloc_.Alloc(&thr->sync_cache); 234276789Sdim mys = sync_alloc_.Map(myidx); 235276789Sdim mys->Init(thr, pc, addr, uid); 236276789Sdim } 237276789Sdim mys->next = idx0; 238276789Sdim if (atomic_compare_exchange_strong((atomic_uint32_t*)meta, &idx0, 239276789Sdim myidx | kFlagSync, memory_order_release)) { 240276789Sdim if (write_lock) 241276789Sdim mys->mtx.Lock(); 242276789Sdim else 243276789Sdim mys->mtx.ReadLock(); 244276789Sdim return mys; 245276789Sdim } 246238901Sandrew } 247238901Sandrew} 248238901Sandrew 249276789Sdimvoid MetaMap::MoveMemory(uptr src, uptr dst, uptr sz) { 250276789Sdim // src and dst can overlap, 251276789Sdim // there are no concurrent accesses to the regions (e.g. stop-the-world). 252276789Sdim CHECK_NE(src, dst); 253276789Sdim CHECK_NE(sz, 0); 254276789Sdim uptr diff = dst - src; 255276789Sdim u32 *src_meta = MemToMeta(src); 256276789Sdim u32 *dst_meta = MemToMeta(dst); 257276789Sdim u32 *src_meta_end = MemToMeta(src + sz); 258276789Sdim uptr inc = 1; 259276789Sdim if (dst > src) { 260276789Sdim src_meta = MemToMeta(src + sz) - 1; 261276789Sdim dst_meta = MemToMeta(dst + sz) - 1; 262276789Sdim src_meta_end = MemToMeta(src) - 1; 263276789Sdim inc = -1; 264238901Sandrew } 265276789Sdim for (; src_meta != src_meta_end; src_meta += inc, dst_meta += inc) { 266276789Sdim CHECK_EQ(*dst_meta, 0); 267276789Sdim u32 idx = *src_meta; 268276789Sdim *src_meta = 0; 269276789Sdim *dst_meta = idx; 270276789Sdim // Patch the addresses in sync objects. 271276789Sdim while (idx != 0) { 272276789Sdim if (idx & kFlagBlock) 273276789Sdim break; 274276789Sdim CHECK(idx & kFlagSync); 275276789Sdim SyncVar *s = sync_alloc_.Map(idx & ~kFlagMask); 276276789Sdim s->addr += diff; 277276789Sdim idx = s->next; 278245614Sandrew } 279238901Sandrew } 280238901Sandrew} 281238901Sandrew 282276789Sdimvoid MetaMap::OnThreadIdle(ThreadState *thr) { 283276789Sdim block_alloc_.FlushCache(&thr->block_cache); 284276789Sdim sync_alloc_.FlushCache(&thr->sync_cache); 285238901Sandrew} 286238901Sandrew 287238901Sandrew} // namespace __tsan 288