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