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 18namespace __tsan { 19 20void DDMutexInit(ThreadState *thr, uptr pc, SyncVar *s); 21 22SyncVar::SyncVar() 23 : mtx(MutexTypeSyncVar, StatMtxSyncVar) { 24 Reset(0); 25} 26 27void 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 39void 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 56MetaMap::MetaMap() 57 : block_alloc_("heap block allocator") 58 , sync_alloc_("sync allocator") { 59 atomic_store(&uid_gen_, 0, memory_order_relaxed); 60} 61 62void 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 74uptr 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 83bool 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. 122void 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 183MBlock* 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 197SyncVar* MetaMap::GetOrCreateAndLock(ThreadState *thr, uptr pc, 198 uptr addr, bool write_lock) { 199 return GetAndLock(thr, pc, addr, write_lock, true); 200} 201 202SyncVar* MetaMap::GetIfExistsAndLock(uptr addr, bool write_lock) { 203 return GetAndLock(0, 0, addr, write_lock, false); 204} 205 206SyncVar* 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 259void 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 292void MetaMap::OnProcIdle(Processor *proc) { 293 block_alloc_.FlushCache(&proc->block_cache); 294 sync_alloc_.FlushCache(&proc->sync_cache); 295} 296 297} // namespace __tsan 298