307 lines · 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-exception6//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 17namespace __tsan {18 19void DDMutexInit(ThreadState *thr, uptr pc, SyncVar *s);20 21SyncVar::SyncVar() : mtx(MutexTypeSyncVar) { Reset(); }22 23void 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 them28 creation_stack_id = CurrentStackId(thr, pc);29 if (common_flags()->detect_deadlocks)30 DDMutexInit(thr, pc, this);31}32 33void 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 44MetaMap::MetaMap()45 : block_alloc_("heap block allocator"), sync_alloc_("sync allocator") {}46 47void 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 59uptr 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 68bool 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 wrt104// freeing of meta objects, because we don't want to page in the whole range105// which can be huge. The function probes pages one-by-one until it finds a page106// without meta objects, at this point it stops freeing meta objects. Because107// thread stacks grow top-down, we do the same starting from end as well.108void 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 region153 // (if it is a stack). The very end of the stack is TLS and tsan increases154 // 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 just159 // freed). Note: we can't simply madvise, because we need to leave a zeroed160 // range (otherwise __tsan_java_move can crash if it encounters a left-over161 // 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 169void MetaMap::ResetClocks() {170 // This can be called from the background thread171 // 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 190MBlock* 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 204SyncVar *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 244void 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 250 // The current MoveMemory implementation behaves incorrectly when src, dst,251 // and sz are not aligned to kMetaShadowCell.252 // For example, with kMetaShadowCell == 8:253 // - src = 4: unexpectedly clears the metadata for the range [0, 4).254 // - src = 16, dst = 4, size = 8: A sync variable for addr = 20, which should255 // be moved to the metadata for address 8, is incorrectly moved to the256 // metadata for address 0 instead.257 // - src = 0, sz = 4: fails to move the tail metadata.258 // Therefore, the following assertions is needed.259 DCHECK_EQ(src % kMetaShadowCell, 0);260 DCHECK_EQ(dst % kMetaShadowCell, 0);261 DCHECK_EQ(sz % kMetaShadowCell, 0);262 263 uptr diff = dst - src;264 u32 *src_meta, *dst_meta, *src_meta_end;265 uptr inc;266 if (dst < src) {267 src_meta = MemToMeta(src);268 dst_meta = MemToMeta(dst);269 src_meta_end = MemToMeta(src + sz);270 inc = 1;271 } else {272 src_meta = MemToMeta(src + sz) - 1;273 dst_meta = MemToMeta(dst + sz) - 1;274 src_meta_end = MemToMeta(src) - 1;275 inc = -1;276 }277 for (; src_meta != src_meta_end; src_meta += inc, dst_meta += inc) {278 CHECK_EQ(*dst_meta, 0);279 u32 idx = *src_meta;280 *src_meta = 0;281 *dst_meta = idx;282 // Patch the addresses in sync objects.283 while (idx != 0) {284 if (idx & kFlagBlock)285 break;286 CHECK(idx & kFlagSync);287 SyncVar *s = sync_alloc_.Map(idx & ~kFlagMask);288 s->addr += diff;289 idx = s->next;290 }291 }292}293 294void MetaMap::OnProcIdle(Processor *proc) {295 block_alloc_.FlushCache(&proc->block_cache);296 sync_alloc_.FlushCache(&proc->sync_cache);297}298 299MetaMap::MemoryStats MetaMap::GetMemoryStats() const {300 MemoryStats stats;301 stats.mem_block = block_alloc_.AllocatedMemory();302 stats.sync_obj = sync_alloc_.AllocatedMemory();303 return stats;304}305 306} // namespace __tsan307