1603c4be006d8c53905d736bf1f19a49f5ce98276Alexey Samsonov//===-- tsan_sync.cc ------------------------------------------------------===// 27ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany// 37ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany// The LLVM Compiler Infrastructure 47ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany// 57ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany// This file is distributed under the University of Illinois Open Source 67ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany// License. See LICENSE.TXT for details. 77ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany// 87ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany//===----------------------------------------------------------------------===// 97ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany// 107ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany// This file is a part of ThreadSanitizer (TSan), a race detector. 117ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany// 127ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany//===----------------------------------------------------------------------===// 1347b1634df012507799eb39aa17d4022d748ba67bAlexey Samsonov#include "sanitizer_common/sanitizer_placement_new.h" 147ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany#include "tsan_sync.h" 157ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany#include "tsan_rtl.h" 167ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany#include "tsan_mman.h" 177ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany 187ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryanynamespace __tsan { 197ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany 202d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesvoid DDMutexInit(ThreadState *thr, uptr pc, SyncVar *s); 212d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 225d71de26cedae3dafc17449fe0182045c0bd20e8Stephen HinesSyncVar::SyncVar() 235d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines : mtx(MutexTypeSyncVar, StatMtxSyncVar) { 245d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines Reset(); 257ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany} 267ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany 275d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hinesvoid SyncVar::Init(ThreadState *thr, uptr pc, uptr addr, u64 uid) { 285d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines this->addr = addr; 295d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines this->uid = uid; 305d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines this->next = 0; 317ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany 325d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines creation_stack_id = 0; 335d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines if (kCppMode) // Go does not use them 345d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines creation_stack_id = CurrentStackId(thr, pc); 355d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines if (flags()->detect_deadlocks) 365d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines DDMutexInit(thr, pc, this); 377ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany} 387ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany 395d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hinesvoid SyncVar::Reset() { 405d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines uid = 0; 415d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines creation_stack_id = 0; 425d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines owner_tid = kInvalidTid; 435d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines last_lock = 0; 445d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines recursion = 0; 455d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines is_rw = 0; 465d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines is_recursive = 0; 475d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines is_broken = 0; 485d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines is_linker_init = 0; 497ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany 505d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines clock.Zero(); 515d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines read_clock.Reset(); 52ad9da372f962495b3487685232d09390be841b1cDmitry Vyukov} 53ad9da372f962495b3487685232d09390be841b1cDmitry Vyukov 545d71de26cedae3dafc17449fe0182045c0bd20e8Stephen HinesMetaMap::MetaMap() { 555d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines atomic_store(&uid_gen_, 0, memory_order_relaxed); 56ad9da372f962495b3487685232d09390be841b1cDmitry Vyukov} 57ad9da372f962495b3487685232d09390be841b1cDmitry Vyukov 585d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hinesvoid MetaMap::AllocBlock(ThreadState *thr, uptr pc, uptr p, uptr sz) { 595d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines u32 idx = block_alloc_.Alloc(&thr->block_cache); 605d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines MBlock *b = block_alloc_.Map(idx); 615d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines b->siz = sz; 625d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines b->tid = thr->tid; 635d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines b->stk = CurrentStackId(thr, pc); 645d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines u32 *meta = MemToMeta(p); 655d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines DCHECK_EQ(*meta, 0); 665d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines *meta = idx | kFlagBlock; 6721cc85db95b8fa85a9ff7a403c8a24e345d73bafDmitry Vyukov} 6821cc85db95b8fa85a9ff7a403c8a24e345d73bafDmitry Vyukov 695d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hinesuptr MetaMap::FreeBlock(ThreadState *thr, uptr pc, uptr p) { 705d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines MBlock* b = GetBlock(p); 715d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines if (b == 0) 72ad9da372f962495b3487685232d09390be841b1cDmitry Vyukov return 0; 735d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines uptr sz = RoundUpTo(b->siz, kMetaShadowCell); 745d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines FreeRange(thr, pc, p, sz); 755d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines return sz; 765d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines} 775d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines 785d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hinesvoid MetaMap::FreeRange(ThreadState *thr, uptr pc, uptr p, uptr sz) { 795d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines u32 *meta = MemToMeta(p); 805d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines u32 *end = MemToMeta(p + sz); 815d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines if (end == meta) 825d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines end++; 835d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines for (; meta < end; meta++) { 845d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines u32 idx = *meta; 855d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines *meta = 0; 865d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines for (;;) { 875d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines if (idx == 0) 887ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany break; 895d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines if (idx & kFlagBlock) { 905d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines block_alloc_.Free(&thr->block_cache, idx & ~kFlagMask); 917ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany break; 925d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines } else if (idx & kFlagSync) { 935d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines DCHECK(idx & kFlagSync); 945d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines SyncVar *s = sync_alloc_.Map(idx & ~kFlagMask); 955d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines u32 next = s->next; 965d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines s->Reset(); 975d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines sync_alloc_.Free(&thr->sync_cache, idx & ~kFlagMask); 985d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines idx = next; 995d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines } else { 1005d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines CHECK(0); 1017ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany } 1027ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany } 1037ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany } 1047ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany} 1057ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany 1065d71de26cedae3dafc17449fe0182045c0bd20e8Stephen HinesMBlock* MetaMap::GetBlock(uptr p) { 1075d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines u32 *meta = MemToMeta(p); 1085d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines u32 idx = *meta; 1095d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines for (;;) { 1105d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines if (idx == 0) 1115d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines return 0; 1125d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines if (idx & kFlagBlock) 1135d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines return block_alloc_.Map(idx & ~kFlagMask); 1145d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines DCHECK(idx & kFlagSync); 1155d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines SyncVar * s = sync_alloc_.Map(idx & ~kFlagMask); 1165d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines idx = s->next; 1175d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines } 1187ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany} 1197ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany 1205d71de26cedae3dafc17449fe0182045c0bd20e8Stephen HinesSyncVar* MetaMap::GetOrCreateAndLock(ThreadState *thr, uptr pc, 1215d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines uptr addr, bool write_lock) { 1225d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines return GetAndLock(thr, pc, addr, write_lock, true); 1239ad7c32720dfa1287f8cfd481e5d583435178caeDmitry Vyukov} 1249ad7c32720dfa1287f8cfd481e5d583435178caeDmitry Vyukov 1255d71de26cedae3dafc17449fe0182045c0bd20e8Stephen HinesSyncVar* MetaMap::GetIfExistsAndLock(uptr addr) { 1265d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines return GetAndLock(0, 0, addr, true, false); 1277ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany} 1287ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany 1295d71de26cedae3dafc17449fe0182045c0bd20e8Stephen HinesSyncVar* MetaMap::GetAndLock(ThreadState *thr, uptr pc, 1305d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines uptr addr, bool write_lock, bool create) { 1315d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines u32 *meta = MemToMeta(addr); 1325d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines u32 idx0 = *meta; 1335d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines u32 myidx = 0; 1345d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines SyncVar *mys = 0; 1355d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines for (;;) { 1365d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines u32 idx = idx0; 1375d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines for (;;) { 1385d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines if (idx == 0) 1395d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines break; 1405d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines if (idx & kFlagBlock) 1415d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines break; 1425d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines DCHECK(idx & kFlagSync); 1435d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines SyncVar * s = sync_alloc_.Map(idx & ~kFlagMask); 1445d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines if (s->addr == addr) { 1455d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines if (myidx != 0) { 1465d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines mys->Reset(); 1475d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines sync_alloc_.Free(&thr->sync_cache, myidx); 1485d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines } 1495d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines if (write_lock) 1505d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines s->mtx.Lock(); 1515d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines else 1525d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines s->mtx.ReadLock(); 1535d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines return s; 1545d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines } 1555d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines idx = s->next; 1565d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines } 1575d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines if (!create) 1585d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines return 0; 1595d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines if (*meta != idx0) { 1605d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines idx0 = *meta; 1615d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines continue; 1625d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines } 1637ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany 1645d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines if (myidx == 0) { 1655d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines const u64 uid = atomic_fetch_add(&uid_gen_, 1, memory_order_relaxed); 1665d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines myidx = sync_alloc_.Alloc(&thr->sync_cache); 1675d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines mys = sync_alloc_.Map(myidx); 1685d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines mys->Init(thr, pc, addr, uid); 1695d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines } 1705d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines mys->next = idx0; 1715d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines if (atomic_compare_exchange_strong((atomic_uint32_t*)meta, &idx0, 1725d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines myidx | kFlagSync, memory_order_release)) { 1735d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines if (write_lock) 1745d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines mys->mtx.Lock(); 1755d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines else 1765d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines mys->mtx.ReadLock(); 1775d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines return mys; 1785d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines } 1797ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany } 1807ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany} 1817ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany 1825d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hinesvoid MetaMap::MoveMemory(uptr src, uptr dst, uptr sz) { 1835d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines // src and dst can overlap, 1845d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines // there are no concurrent accesses to the regions (e.g. stop-the-world). 1855d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines CHECK_NE(src, dst); 1865d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines CHECK_NE(sz, 0); 1875d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines uptr diff = dst - src; 1885d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines u32 *src_meta = MemToMeta(src); 1895d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines u32 *dst_meta = MemToMeta(dst); 1905d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines u32 *src_meta_end = MemToMeta(src + sz); 1915d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines uptr inc = 1; 1925d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines if (dst > src) { 1935d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines src_meta = MemToMeta(src + sz) - 1; 1945d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines dst_meta = MemToMeta(dst + sz) - 1; 1955d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines src_meta_end = MemToMeta(src) - 1; 1965d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines inc = -1; 1979ad7c32720dfa1287f8cfd481e5d583435178caeDmitry Vyukov } 1985d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines for (; src_meta != src_meta_end; src_meta += inc, dst_meta += inc) { 1995d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines CHECK_EQ(*dst_meta, 0); 2005d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines u32 idx = *src_meta; 2015d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines *src_meta = 0; 2025d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines *dst_meta = idx; 2035d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines // Patch the addresses in sync objects. 2045d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines while (idx != 0) { 2055d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines if (idx & kFlagBlock) 2065d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines break; 2075d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines CHECK(idx & kFlagSync); 2085d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines SyncVar *s = sync_alloc_.Map(idx & ~kFlagMask); 2095d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines s->addr += diff; 2105d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines idx = s->next; 21101a7ce809bf7cc627d73c045c70bcca9891f632cDmitry Vyukov } 2129ad7c32720dfa1287f8cfd481e5d583435178caeDmitry Vyukov } 2137ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany} 2147ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany 2155d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hinesvoid MetaMap::OnThreadIdle(ThreadState *thr) { 2165d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines block_alloc_.FlushCache(&thr->block_cache); 2175d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines sync_alloc_.FlushCache(&thr->sync_cache); 2187ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany} 2197ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany 2207ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany} // namespace __tsan 221