contrib/compiler-rt/lib/tsan/rtl/tsan_sync.cc

   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
  18 namespace __tsan {
  19
  20 void DDMutexInit(ThreadState *thr, uptr pc, SyncVar *s);
  21
  22 SyncVar::SyncVar()
  23     : mtx(MutexTypeSyncVar, StatMtxSyncVar) {
  24   Reset(0);
  25 }
  26
  27 void 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 (kCppMode)  // 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
  39 void SyncVar::Reset(ThreadState *thr) {
  40   uid = 0;
  41   creation_stack_id = 0;
  42   owner_tid = kInvalidTid;
  43   last_lock = 0;
  44   recursion = 0;
  45   is_rw = 0;
  46   is_recursive = 0;
  47   is_broken = 0;
  48   is_linker_init = 0;
  49
  50   if (thr == 0) {
  51     CHECK_EQ(clock.size(), 0);
  52     CHECK_EQ(read_clock.size(), 0);
  53   } else {
  54     clock.Reset(&thr->clock_cache);
  55     read_clock.Reset(&thr->clock_cache);
  56   }
  57 }
  58
  59 MetaMap::MetaMap() {
  60   atomic_store(&uid_gen_, 0, memory_order_relaxed);
  61 }
  62
  63 void MetaMap::AllocBlock(ThreadState *thr, uptr pc, uptr p, uptr sz) {
  64   u32 idx = block_alloc_.Alloc(&thr->block_cache);
  65   MBlock *b = block_alloc_.Map(idx);
  66   b->siz = sz;
  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
  74 uptr MetaMap::FreeBlock(ThreadState *thr, uptr pc, uptr p) {
  75   MBlock* b = GetBlock(p);
  76   if (b == 0)
  77     return 0;
  78   uptr sz = RoundUpTo(b->siz, kMetaShadowCell);
  79   FreeRange(thr, pc, p, sz);
  80   return sz;
  81 }
  82
  83 void MetaMap::FreeRange(ThreadState *thr, uptr pc, uptr p, uptr sz) {
  84   u32 *meta = MemToMeta(p);
  85   u32 *end = MemToMeta(p + sz);
  86   if (end == meta)
  87     end++;
  88   for (; meta < end; meta++) {
  89     u32 idx = *meta;
  90     *meta = 0;
  91     for (;;) {
  92       if (idx == 0)
  93         break;
  94       if (idx & kFlagBlock) {
  95         block_alloc_.Free(&thr->block_cache, idx & ~kFlagMask);
  96         break;
  97       } else if (idx & kFlagSync) {
  98         DCHECK(idx & kFlagSync);
  99         SyncVar *s = sync_alloc_.Map(idx & ~kFlagMask);
 100         u32 next = s->next;
 101         s->Reset(thr);
 102         sync_alloc_.Free(&thr->sync_cache, idx & ~kFlagMask);
 103         idx = next;
 104       } else {
 105         CHECK(0);
 106       }
 107     }
 108   }
 109 }
 110
 111 MBlock* MetaMap::GetBlock(uptr p) {
 112   u32 *meta = MemToMeta(p);
 113   u32 idx = *meta;
 114   for (;;) {
 115     if (idx == 0)
 116       return 0;
 117     if (idx & kFlagBlock)
 118       return block_alloc_.Map(idx & ~kFlagMask);
 119     DCHECK(idx & kFlagSync);
 120     SyncVar * s = sync_alloc_.Map(idx & ~kFlagMask);
 121     idx = s->next;
 122   }
 123 }
 124
 125 SyncVar* MetaMap::GetOrCreateAndLock(ThreadState *thr, uptr pc,
 126                               uptr addr, bool write_lock) {
 127   return GetAndLock(thr, pc, addr, write_lock, true);
 128 }
 129
 130 SyncVar* MetaMap::GetIfExistsAndLock(uptr addr) {
 131   return GetAndLock(0, 0, addr, true, false);
 132 }
 133
 134 SyncVar* MetaMap::GetAndLock(ThreadState *thr, uptr pc,
 135                              uptr addr, bool write_lock, bool create) {
 136   u32 *meta = MemToMeta(addr);
 137   u32 idx0 = *meta;
 138   u32 myidx = 0;
 139   SyncVar *mys = 0;
 140   for (;;) {
 141     u32 idx = idx0;
 142     for (;;) {
 143       if (idx == 0)
 144         break;
 145       if (idx & kFlagBlock)
 146         break;
 147       DCHECK(idx & kFlagSync);
 148       SyncVar * s = sync_alloc_.Map(idx & ~kFlagMask);
 149       if (s->addr == addr) {
 150         if (myidx != 0) {
 151           mys->Reset(thr);
 152           sync_alloc_.Free(&thr->sync_cache, myidx);
 153         }
 154         if (write_lock)
 155           s->mtx.Lock();
 156         else
 157           s->mtx.ReadLock();
 158         return s;
 159       }
 160       idx = s->next;
 161     }
 162     if (!create)
 163       return 0;
 164     if (*meta != idx0) {
 165       idx0 = *meta;
 166       continue;
 167     }
 168
 169     if (myidx == 0) {
 170       const u64 uid = atomic_fetch_add(&uid_gen_, 1, memory_order_relaxed);
 171       myidx = sync_alloc_.Alloc(&thr->sync_cache);
 172       mys = sync_alloc_.Map(myidx);
 173       mys->Init(thr, pc, addr, uid);
 174     }
 175     mys->next = idx0;
 176     if (atomic_compare_exchange_strong((atomic_uint32_t*)meta, &idx0,
 177         myidx | kFlagSync, memory_order_release)) {
 178       if (write_lock)
 179         mys->mtx.Lock();
 180       else
 181         mys->mtx.ReadLock();
 182       return mys;
 183     }
 184   }
 185 }
 186
 187 void MetaMap::MoveMemory(uptr src, uptr dst, uptr sz) {
 188   // src and dst can overlap,
 189   // there are no concurrent accesses to the regions (e.g. stop-the-world).
 190   CHECK_NE(src, dst);
 191   CHECK_NE(sz, 0);
 192   uptr diff = dst - src;
 193   u32 *src_meta = MemToMeta(src);
 194   u32 *dst_meta = MemToMeta(dst);
 195   u32 *src_meta_end = MemToMeta(src + sz);
 196   uptr inc = 1;
 197   if (dst > src) {
 198     src_meta = MemToMeta(src + sz) - 1;
 199     dst_meta = MemToMeta(dst + sz) - 1;
 200     src_meta_end = MemToMeta(src) - 1;
 201     inc = -1;
 202   }
 203   for (; src_meta != src_meta_end; src_meta += inc, dst_meta += inc) {
 204     CHECK_EQ(*dst_meta, 0);
 205     u32 idx = *src_meta;
 206     *src_meta = 0;
 207     *dst_meta = idx;
 208     // Patch the addresses in sync objects.
 209     while (idx != 0) {
 210       if (idx & kFlagBlock)
 211         break;
 212       CHECK(idx & kFlagSync);
 213       SyncVar *s = sync_alloc_.Map(idx & ~kFlagMask);
 214       s->addr += diff;
 215       idx = s->next;
 216     }
 217   }
 218 }
 219
 220 void MetaMap::OnThreadIdle(ThreadState *thr) {
 221   block_alloc_.FlushCache(&thr->block_cache);
 222   sync_alloc_.FlushCache(&thr->sync_cache);
 223 }
 224
 225 }  // namespace __tsan