1 //===-- tsan_clock.h --------------------------------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file is a part of ThreadSanitizer (TSan), a race detector.
12 //===----------------------------------------------------------------------===//
16 #include "tsan_defs.h"
17 #include "tsan_dense_alloc.h"
21 typedef DenseSlabAlloc<ClockBlock, 1<<16, 1<<10> ClockAlloc;
22 typedef DenseSlabAllocCache ClockCache;
24 // The clock that lives in sync variables (mutexes, atomics, etc).
32 // These are used only in tests.
33 u64 get(unsigned tid) const;
34 u64 get_clean(unsigned tid) const;
36 void Resize(ClockCache *c, uptr nclk);
37 void Reset(ClockCache *c);
39 void DebugDump(int(*printf)(const char *s, ...));
41 // Clock element iterator.
42 // Note: it iterates only over the table without regard to dirty entries.
45 explicit Iter(SyncClock* parent);
47 bool operator!=(const Iter& other);
48 ClockElem &operator*();
52 // [pos_, end_) is the current continuous range of clock elements.
55 int block_; // Current number of second level block.
64 friend class ThreadClock;
66 static const uptr kDirtyTids = 2;
70 u64 tid : 64 - kClkBits; // kInvalidId if not active
73 unsigned release_store_tid_;
74 unsigned release_store_reused_;
75 Dirty dirty_[kDirtyTids];
76 // If size_ is 0, tab_ is nullptr.
77 // If size <= 64 (kClockCount), tab_ contains pointer to an array with
78 // 64 ClockElem's (ClockBlock::clock).
79 // Otherwise, tab_ points to an array with up to 127 u32 elements,
80 // each pointing to the second-level 512b block with 64 ClockElem's.
81 // Unused space in the first level ClockBlock is used to store additional
83 // The last u32 element in the first level ClockBlock is always used as
86 // See the following scheme for details.
87 // All memory blocks are 512 bytes (allocated from ClockAlloc).
88 // Clock (clk) elements are 64 bits.
89 // Idx and ref are 32 bits.
94 // +----------------------------------------------------+
95 // | clk128 | clk129 | ...unused... | idx1 | idx0 | ref |
96 // +----------------------------------------------------+
99 // | +----------------+
100 // | | clk0 ... clk63 |
101 // | +----------------+
103 // +------------------+
104 // | clk64 ... clk127 |
105 // +------------------+
107 // Note: dirty entries, if active, always override what's stored in the clock.
111 u16 blocks_; // Number of second level blocks.
113 void Unshare(ClockCache *c);
114 bool IsShared() const;
115 bool Cachable() const;
118 uptr capacity() const;
119 u32 get_block(uptr bi) const;
120 void append_block(u32 idx);
121 ClockElem &elem(unsigned tid) const;
124 // The clock that lives in threads.
127 typedef DenseSlabAllocCache Cache;
129 explicit ThreadClock(unsigned tid, unsigned reused = 0);
131 u64 get(unsigned tid) const;
132 void set(ClockCache *c, unsigned tid, u64 v);
137 void acquire(ClockCache *c, SyncClock *src);
138 void release(ClockCache *c, SyncClock *dst);
139 void acq_rel(ClockCache *c, SyncClock *dst);
140 void ReleaseStore(ClockCache *c, SyncClock *dst);
141 void ResetCached(ClockCache *c);
144 void DebugDump(int(*printf)(const char *s, ...));
147 static const uptr kDirtyTids = SyncClock::kDirtyTids;
148 // Index of the thread associated with he clock ("current thread").
150 const unsigned reused_; // tid_ reuse count.
151 // Current thread time when it acquired something from other threads.
154 // Cached SyncClock (without dirty entries and release_store_tid_).
155 // We reuse it for subsequent store-release operations without intervening
156 // acquire operations. Since it is shared (and thus constant), clock value
157 // for the current thread is then stored in dirty entries in the SyncClock.
158 // We host a refernece to the table while it is cached here.
163 // Number of active elements in the clk_ table (the rest is zeros).
165 u64 clk_[kMaxTidInClock]; // Fixed size vector clock.
167 bool IsAlreadyAcquired(const SyncClock *src) const;
168 void UpdateCurrentThread(ClockCache *c, SyncClock *dst) const;
171 ALWAYS_INLINE u64 ThreadClock::get(unsigned tid) const {
172 DCHECK_LT(tid, kMaxTidInClock);
176 ALWAYS_INLINE void ThreadClock::set(u64 v) {
177 DCHECK_GE(v, clk_[tid_]);
181 ALWAYS_INLINE void ThreadClock::tick() {
185 ALWAYS_INLINE uptr ThreadClock::size() const {
189 ALWAYS_INLINE SyncClock::Iter SyncClock::begin() {
193 ALWAYS_INLINE SyncClock::Iter SyncClock::end() {
194 return Iter(nullptr);
197 ALWAYS_INLINE uptr SyncClock::size() const {
201 ALWAYS_INLINE SyncClock::Iter::Iter(SyncClock* parent)
210 ALWAYS_INLINE SyncClock::Iter& SyncClock::Iter::operator++() {
212 if (UNLIKELY(pos_ >= end_))
217 ALWAYS_INLINE bool SyncClock::Iter::operator!=(const SyncClock::Iter& other) {
218 return parent_ != other.parent_;
221 ALWAYS_INLINE ClockElem &SyncClock::Iter::operator*() {
224 } // namespace __tsan
226 #endif // TSAN_CLOCK_H