contrib/compiler-rt/lib/tsan/rtl/tsan_clock.h

   1 //===-- tsan_clock.h --------------------------------------------*- C++ -*-===//
   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-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file is a part of ThreadSanitizer (TSan), a race detector.
  10 //
  11 //===----------------------------------------------------------------------===//
  12 #ifndef TSAN_CLOCK_H
  13 #define TSAN_CLOCK_H
  14
  15 #include "tsan_defs.h"
  16 #include "tsan_dense_alloc.h"
  17
  18 namespace __tsan {
  19
  20 typedef DenseSlabAlloc<ClockBlock, 1<<16, 1<<10> ClockAlloc;
  21 typedef DenseSlabAllocCache ClockCache;
  22
  23 // The clock that lives in sync variables (mutexes, atomics, etc).
  24 class SyncClock {
  25  public:
  26   SyncClock();
  27   ~SyncClock();
  28
  29   uptr size() const;
  30
  31   // These are used only in tests.
  32   u64 get(unsigned tid) const;
  33   u64 get_clean(unsigned tid) const;
  34
  35   void Resize(ClockCache *c, uptr nclk);
  36   void Reset(ClockCache *c);
  37
  38   void DebugDump(int(*printf)(const char *s, ...));
  39
  40   // Clock element iterator.
  41   // Note: it iterates only over the table without regard to dirty entries.
  42   class Iter {
  43    public:
  44     explicit Iter(SyncClock* parent);
  45     Iter& operator++();
  46     bool operator!=(const Iter& other);
  47     ClockElem &operator*();
  48
  49    private:
  50     SyncClock *parent_;
  51     // [pos_, end_) is the current continuous range of clock elements.
  52     ClockElem *pos_;
  53     ClockElem *end_;
  54     int block_;  // Current number of second level block.
  55
  56     NOINLINE void Next();
  57   };
  58
  59   Iter begin();
  60   Iter end();
  61
  62  private:
  63   friend class ThreadClock;
  64   friend class Iter;
  65   static const uptr kDirtyTids = 2;
  66
  67   struct Dirty {
  68     u64 epoch  : kClkBits;
  69     u64 tid : 64 - kClkBits;  // kInvalidId if not active
  70   };
  71
  72   unsigned release_store_tid_;
  73   unsigned release_store_reused_;
  74   Dirty dirty_[kDirtyTids];
  75   // If size_ is 0, tab_ is nullptr.
  76   // If size <= 64 (kClockCount), tab_ contains pointer to an array with
  77   // 64 ClockElem's (ClockBlock::clock).
  78   // Otherwise, tab_ points to an array with up to 127 u32 elements,
  79   // each pointing to the second-level 512b block with 64 ClockElem's.
  80   // Unused space in the first level ClockBlock is used to store additional
  81   // clock elements.
  82   // The last u32 element in the first level ClockBlock is always used as
  83   // reference counter.
  84   //
  85   // See the following scheme for details.
  86   // All memory blocks are 512 bytes (allocated from ClockAlloc).
  87   // Clock (clk) elements are 64 bits.
  88   // Idx and ref are 32 bits.
  89   //
  90   // tab_
  91   //    |
  92   //    \/
  93   //    +----------------------------------------------------+
  94   //    | clk128 | clk129 | ...unused... | idx1 | idx0 | ref |
  95   //    +----------------------------------------------------+
  96   //                                        |      |
  97   //                                        |      \/
  98   //                                        |      +----------------+
  99   //                                        |      | clk0 ... clk63 |
 100   //                                        |      +----------------+
 101   //                                        \/
 102   //                                        +------------------+
 103   //                                        | clk64 ... clk127 |
 104   //                                        +------------------+
 105   //
 106   // Note: dirty entries, if active, always override what's stored in the clock.
 107   ClockBlock *tab_;
 108   u32 tab_idx_;
 109   u16 size_;
 110   u16 blocks_;  // Number of second level blocks.
 111
 112   void Unshare(ClockCache *c);
 113   bool IsShared() const;
 114   bool Cachable() const;
 115   void ResetImpl();
 116   void FlushDirty();
 117   uptr capacity() const;
 118   u32 get_block(uptr bi) const;
 119   void append_block(u32 idx);
 120   ClockElem &elem(unsigned tid) const;
 121 };
 122
 123 // The clock that lives in threads.
 124 class ThreadClock {
 125  public:
 126   typedef DenseSlabAllocCache Cache;
 127
 128   explicit ThreadClock(unsigned tid, unsigned reused = 0);
 129
 130   u64 get(unsigned tid) const;
 131   void set(ClockCache *c, unsigned tid, u64 v);
 132   void set(u64 v);
 133   void tick();
 134   uptr size() const;
 135
 136   void acquire(ClockCache *c, SyncClock *src);
 137   void release(ClockCache *c, SyncClock *dst);
 138   void acq_rel(ClockCache *c, SyncClock *dst);
 139   void ReleaseStore(ClockCache *c, SyncClock *dst);
 140   void ResetCached(ClockCache *c);
 141
 142   void DebugReset();
 143   void DebugDump(int(*printf)(const char *s, ...));
 144
 145  private:
 146   static const uptr kDirtyTids = SyncClock::kDirtyTids;
 147   // Index of the thread associated with he clock ("current thread").
 148   const unsigned tid_;
 149   const unsigned reused_;  // tid_ reuse count.
 150   // Current thread time when it acquired something from other threads.
 151   u64 last_acquire_;
 152
 153   // Cached SyncClock (without dirty entries and release_store_tid_).
 154   // We reuse it for subsequent store-release operations without intervening
 155   // acquire operations. Since it is shared (and thus constant), clock value
 156   // for the current thread is then stored in dirty entries in the SyncClock.
 157   // We host a refernece to the table while it is cached here.
 158   u32 cached_idx_;
 159   u16 cached_size_;
 160   u16 cached_blocks_;
 161
 162   // Number of active elements in the clk_ table (the rest is zeros).
 163   uptr nclk_;
 164   u64 clk_[kMaxTidInClock];  // Fixed size vector clock.
 165
 166   bool IsAlreadyAcquired(const SyncClock *src) const;
 167   void UpdateCurrentThread(ClockCache *c, SyncClock *dst) const;
 168 };
 169
 170 ALWAYS_INLINE u64 ThreadClock::get(unsigned tid) const {
 171   DCHECK_LT(tid, kMaxTidInClock);
 172   return clk_[tid];
 173 }
 174
 175 ALWAYS_INLINE void ThreadClock::set(u64 v) {
 176   DCHECK_GE(v, clk_[tid_]);
 177   clk_[tid_] = v;
 178 }
 179
 180 ALWAYS_INLINE void ThreadClock::tick() {
 181   clk_[tid_]++;
 182 }
 183
 184 ALWAYS_INLINE uptr ThreadClock::size() const {
 185   return nclk_;
 186 }
 187
 188 ALWAYS_INLINE SyncClock::Iter SyncClock::begin() {
 189   return Iter(this);
 190 }
 191
 192 ALWAYS_INLINE SyncClock::Iter SyncClock::end() {
 193   return Iter(nullptr);
 194 }
 195
 196 ALWAYS_INLINE uptr SyncClock::size() const {
 197   return size_;
 198 }
 199
 200 ALWAYS_INLINE SyncClock::Iter::Iter(SyncClock* parent)
 201     : parent_(parent)
 202     , pos_(nullptr)
 203     , end_(nullptr)
 204     , block_(-1) {
 205   if (parent)
 206     Next();
 207 }
 208
 209 ALWAYS_INLINE SyncClock::Iter& SyncClock::Iter::operator++() {
 210   pos_++;
 211   if (UNLIKELY(pos_ >= end_))
 212     Next();
 213   return *this;
 214 }
 215
 216 ALWAYS_INLINE bool SyncClock::Iter::operator!=(const SyncClock::Iter& other) {
 217   return parent_ != other.parent_;
 218 }
 219
 220 ALWAYS_INLINE ClockElem &SyncClock::Iter::operator*() {
 221   return *pos_;
 222 }
 223 }  // namespace __tsan
 224
 225 #endif  // TSAN_CLOCK_H