Home | History | Annotate | Download | only in rtl 
      1 //===-- tsan_clock.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 "tsan_clock.h"
     14 #include "tsan_rtl.h"
     15 
     16 // It's possible to optimize clock operations for some important cases
     17 // so that they are O(1). The cases include singletons, once's, local mutexes.
     18 // First, SyncClock must be re-implemented to allow indexing by tid.
     19 // It must not necessarily be a full vector clock, though. For example it may
     20 // be a multi-level table.
     21 // Then, each slot in SyncClock must contain a dirty bit (it's united with
     22 // the clock value, so no space increase). The acquire algorithm looks
     23 // as follows:
     24 // void acquire(thr, tid, thr_clock, sync_clock) {
     25 //   if (!sync_clock[tid].dirty)
     26 //     return;  // No new info to acquire.
     27 //              // This handles constant reads of singleton pointers and
     28 //              // stop-flags.
     29 //   acquire_impl(thr_clock, sync_clock);  // As usual, O(N).
     30 //   sync_clock[tid].dirty = false;
     31 //   sync_clock.dirty_count--;
     32 // }
     33 // The release operation looks as follows:
     34 // void release(thr, tid, thr_clock, sync_clock) {
     35 //   // thr->sync_cache is a simple fixed-size hash-based cache that holds
     36 //   // several previous sync_clock's.
     37 //   if (thr->sync_cache[sync_clock] >= thr->last_acquire_epoch) {
     38 //     // The thread did no acquire operations since last release on this clock.
     39 //     // So update only the thread's slot (other slots can't possibly change).
     40 //     sync_clock[tid].clock = thr->epoch;
     41 //     if (sync_clock.dirty_count == sync_clock.cnt
     42 //         || (sync_clock.dirty_count == sync_clock.cnt - 1
     43 //           && sync_clock[tid].dirty == false))
     44 //       // All dirty flags are set, bail out.
     45 //       return;
     46 //     set all dirty bits, but preserve the thread's bit.  // O(N)
     47 //     update sync_clock.dirty_count;
     48 //     return;
     49 //   }
     50 //   release_impl(thr_clock, sync_clock);  // As usual, O(N).
     51 //   set all dirty bits, but preserve the thread's bit.
     52 //   // The previous step is combined with release_impl(), so that
     53 //   // we scan the arrays only once.
     54 //   update sync_clock.dirty_count;
     55 // }
     56 
     57 namespace __tsan {
     58 
     59 ThreadClock::ThreadClock() {
     60   nclk_ = 0;
     61   for (uptr i = 0; i < (uptr)kMaxTidInClock; i++)
     62     clk_[i] = 0;
     63 }
     64 
     65 void ThreadClock::acquire(const SyncClock *src) {
     66   DCHECK(nclk_ <= kMaxTid);
     67   DCHECK(src->clk_.Size() <= kMaxTid);
     68 
     69   const uptr nclk = src->clk_.Size();
     70   if (nclk == 0)
     71     return;
     72   nclk_ = max(nclk_, nclk);
     73   for (uptr i = 0; i < nclk; i++) {
     74     if (clk_[i] < src->clk_[i])
     75       clk_[i] = src->clk_[i];
     76   }
     77 }
     78 
     79 void ThreadClock::release(SyncClock *dst) const {
     80   DCHECK(nclk_ <= kMaxTid);
     81   DCHECK(dst->clk_.Size() <= kMaxTid);
     82 
     83   if (dst->clk_.Size() < nclk_)
     84     dst->clk_.Resize(nclk_);
     85   for (uptr i = 0; i < nclk_; i++) {
     86     if (dst->clk_[i] < clk_[i])
     87       dst->clk_[i] = clk_[i];
     88   }
     89 }
     90 
     91 void ThreadClock::ReleaseStore(SyncClock *dst) const {
     92   DCHECK(nclk_ <= kMaxTid);
     93   DCHECK(dst->clk_.Size() <= kMaxTid);
     94 
     95   if (dst->clk_.Size() < nclk_)
     96     dst->clk_.Resize(nclk_);
     97   for (uptr i = 0; i < nclk_; i++)
     98     dst->clk_[i] = clk_[i];
     99   for (uptr i = nclk_; i < dst->clk_.Size(); i++)
    100     dst->clk_[i] = 0;
    101 }
    102 
    103 void ThreadClock::acq_rel(SyncClock *dst) {
    104   acquire(dst);
    105   release(dst);
    106 }
    107 
    108 SyncClock::SyncClock()
    109   : clk_(MBlockClock) {
    110 }
    111 }  // namespace __tsan
    112