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 16namespace __tsan { 17 18void DDMutexInit(ThreadState *thr, uptr pc, SyncVar *s); 19 20SyncVar::SyncVar() 21 : mtx(MutexTypeSyncVar, StatMtxSyncVar) { 22 Reset(0); 23} 24 25void 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 37void 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 54MetaMap::MetaMap() 55 : block_alloc_("heap block allocator") 56 , sync_alloc_("sync allocator") { 57 atomic_store(&uid_gen_, 0, memory_order_relaxed); 58} 59 60void 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 72uptr 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 81bool 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. 120void 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 if (!MmapFixedNoReserve(metap, metasz)) 178 Die(); 179} 180 181MBlock* MetaMap::GetBlock(uptr p) { 182 u32 *meta = MemToMeta(p); 183 u32 idx = *meta; 184 for (;;) { 185 if (idx == 0) 186 return 0; 187 if (idx & kFlagBlock) 188 return block_alloc_.Map(idx & ~kFlagMask); 189 DCHECK(idx & kFlagSync); 190 SyncVar * s = sync_alloc_.Map(idx & ~kFlagMask); 191 idx = s->next; 192 } 193} 194 195SyncVar* MetaMap::GetOrCreateAndLock(ThreadState *thr, uptr pc, 196 uptr addr, bool write_lock) { 197 return GetAndLock(thr, pc, addr, write_lock, true); 198} 199 200SyncVar* MetaMap::GetIfExistsAndLock(uptr addr, bool write_lock) { 201 return GetAndLock(0, 0, addr, write_lock, false); 202} 203 204SyncVar* MetaMap::GetAndLock(ThreadState *thr, uptr pc, 205 uptr addr, bool write_lock, bool create) { 206 u32 *meta = MemToMeta(addr); 207 u32 idx0 = *meta; 208 u32 myidx = 0; 209 SyncVar *mys = 0; 210 for (;;) { 211 u32 idx = idx0; 212 for (;;) { 213 if (idx == 0) 214 break; 215 if (idx & kFlagBlock) 216 break; 217 DCHECK(idx & kFlagSync); 218 SyncVar * s = sync_alloc_.Map(idx & ~kFlagMask); 219 if (s->addr == addr) { 220 if (myidx != 0) { 221 mys->Reset(thr->proc()); 222 sync_alloc_.Free(&thr->proc()->sync_cache, myidx); 223 } 224 if (write_lock) 225 s->mtx.Lock(); 226 else 227 s->mtx.ReadLock(); 228 return s; 229 } 230 idx = s->next; 231 } 232 if (!create) 233 return 0; 234 if (*meta != idx0) { 235 idx0 = *meta; 236 continue; 237 } 238 239 if (myidx == 0) { 240 const u64 uid = atomic_fetch_add(&uid_gen_, 1, memory_order_relaxed); 241 myidx = sync_alloc_.Alloc(&thr->proc()->sync_cache); 242 mys = sync_alloc_.Map(myidx); 243 mys->Init(thr, pc, addr, uid); 244 } 245 mys->next = idx0; 246 if (atomic_compare_exchange_strong((atomic_uint32_t*)meta, &idx0, 247 myidx | kFlagSync, memory_order_release)) { 248 if (write_lock) 249 mys->mtx.Lock(); 250 else 251 mys->mtx.ReadLock(); 252 return mys; 253 } 254 } 255} 256 257void MetaMap::MoveMemory(uptr src, uptr dst, uptr sz) { 258 // src and dst can overlap, 259 // there are no concurrent accesses to the regions (e.g. stop-the-world). 260 CHECK_NE(src, dst); 261 CHECK_NE(sz, 0); 262 uptr diff = dst - src; 263 u32 *src_meta = MemToMeta(src); 264 u32 *dst_meta = MemToMeta(dst); 265 u32 *src_meta_end = MemToMeta(src + sz); 266 uptr inc = 1; 267 if (dst > src) { 268 src_meta = MemToMeta(src + sz) - 1; 269 dst_meta = MemToMeta(dst + sz) - 1; 270 src_meta_end = MemToMeta(src) - 1; 271 inc = -1; 272 } 273 for (; src_meta != src_meta_end; src_meta += inc, dst_meta += inc) { 274 CHECK_EQ(*dst_meta, 0); 275 u32 idx = *src_meta; 276 *src_meta = 0; 277 *dst_meta = idx; 278 // Patch the addresses in sync objects. 279 while (idx != 0) { 280 if (idx & kFlagBlock) 281 break; 282 CHECK(idx & kFlagSync); 283 SyncVar *s = sync_alloc_.Map(idx & ~kFlagMask); 284 s->addr += diff; 285 idx = s->next; 286 } 287 } 288} 289 290void MetaMap::OnProcIdle(Processor *proc) { 291 block_alloc_.FlushCache(&proc->block_cache); 292 sync_alloc_.FlushCache(&proc->sync_cache); 293} 294 295} // namespace __tsan 296