1 //===-- tsan_clock.h --------------------------------------------*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
9 // This file is a part of ThreadSanitizer (TSan), a race detector.
11 //===----------------------------------------------------------------------===//
15 #include "tsan_defs.h"
16 #include "tsan_dense_alloc.h"
20 typedef DenseSlabAlloc
<ClockBlock
, 1<<16, 1<<10> ClockAlloc
;
21 typedef DenseSlabAllocCache ClockCache
;
23 // The clock that lives in sync variables (mutexes, atomics, etc).
31 // These are used only in tests.
32 u64
get(unsigned tid
) const;
33 u64
get_clean(unsigned tid
) const;
35 void Resize(ClockCache
*c
, uptr nclk
);
36 void Reset(ClockCache
*c
);
38 void DebugDump(int(*printf
)(const char *s
, ...));
40 // Clock element iterator.
41 // Note: it iterates only over the table without regard to dirty entries.
44 explicit Iter(SyncClock
* parent
);
46 bool operator!=(const Iter
& other
);
47 ClockElem
&operator*();
51 // [pos_, end_) is the current continuous range of clock elements.
54 int block_
; // Current number of second level block.
63 friend class ThreadClock
;
65 static const uptr kDirtyTids
= 2;
69 u64 tid
: 64 - kClkBits
; // kInvalidId if not active
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
82 // The last u32 element in the first level ClockBlock is always used as
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.
93 // +----------------------------------------------------+
94 // | clk128 | clk129 | ...unused... | idx1 | idx0 | ref |
95 // +----------------------------------------------------+
98 // | +----------------+
99 // | | clk0 ... clk63 |
100 // | +----------------+
102 // +------------------+
103 // | clk64 ... clk127 |
104 // +------------------+
106 // Note: dirty entries, if active, always override what's stored in the clock.
110 u16 blocks_
; // Number of second level blocks.
112 void Unshare(ClockCache
*c
);
113 bool IsShared() const;
114 bool Cachable() const;
117 uptr
capacity() const;
118 u32
get_block(uptr bi
) const;
119 void append_block(u32 idx
);
120 ClockElem
&elem(unsigned tid
) const;
123 // The clock that lives in threads.
126 typedef DenseSlabAllocCache Cache
;
128 explicit ThreadClock(unsigned tid
, unsigned reused
= 0);
130 u64
get(unsigned tid
) const;
131 void set(ClockCache
*c
, unsigned tid
, u64 v
);
136 void acquire(ClockCache
*c
, SyncClock
*src
);
137 void releaseStoreAcquire(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
);
142 void NoteGlobalAcquire(u64 v
);
145 void DebugDump(int(*printf
)(const char *s
, ...));
148 static const uptr kDirtyTids
= SyncClock::kDirtyTids
;
149 // Index of the thread associated with he clock ("current thread").
151 const unsigned reused_
; // tid_ reuse count.
152 // Current thread time when it acquired something from other threads.
155 // Last time another thread has done a global acquire of this thread's clock.
156 // It helps to avoid problem described in:
157 // https://github.com/golang/go/issues/39186
158 // See test/tsan/java_finalizer2.cpp for a regression test.
159 // Note the failuire is _extremely_ hard to hit, so if you are trying
160 // to reproduce it, you may want to run something like:
161 // $ go get golang.org/x/tools/cmd/stress
162 // $ stress -p=64 ./a.out
164 // The crux of the problem is roughly as follows.
165 // A number of O(1) optimizations in the clocks algorithm assume proper
166 // transitive cumulative propagation of clock values. The AcquireGlobal
167 // operation may produce an inconsistent non-linearazable view of
168 // thread clocks. Namely, it may acquire a later value from a thread
169 // with a higher ID, but fail to acquire an earlier value from a thread
170 // with a lower ID. If a thread that executed AcquireGlobal then releases
171 // to a sync clock, it will spoil the sync clock with the inconsistent
172 // values. If another thread later releases to the sync clock, the optimized
173 // algorithm may break.
175 // The exact sequence of events that leads to the failure.
176 // - thread 1 executes AcquireGlobal
177 // - thread 1 acquires value 1 for thread 2
178 // - thread 2 increments clock to 2
179 // - thread 2 releases to sync object 1
180 // - thread 3 at time 1
181 // - thread 3 acquires from sync object 1
182 // - thread 3 increments clock to 2
183 // - thread 1 acquires value 2 for thread 3
184 // - thread 1 releases to sync object 2
185 // - sync object 2 clock has 1 for thread 2 and 2 for thread 3
186 // - thread 3 releases to sync object 2
187 // - thread 3 sees value 2 in the clock for itself
188 // and decides that it has already released to the clock
189 // and did not acquire anything from other threads after that
190 // (the last_acquire_ check in release operation)
191 // - thread 3 does not update the value for thread 2 in the clock from 1 to 2
192 // - thread 4 acquires from sync object 2
193 // - thread 4 detects a false race with thread 2
194 // as it should have been synchronized with thread 2 up to time 2,
195 // but because of the broken clock it is now synchronized only up to time 1
197 // The global_acquire_ value helps to prevent this scenario.
198 // Namely, thread 3 will not trust any own clock values up to global_acquire_
199 // for the purposes of the last_acquire_ optimization.
200 atomic_uint64_t global_acquire_
;
202 // Cached SyncClock (without dirty entries and release_store_tid_).
203 // We reuse it for subsequent store-release operations without intervening
204 // acquire operations. Since it is shared (and thus constant), clock value
205 // for the current thread is then stored in dirty entries in the SyncClock.
206 // We host a refernece to the table while it is cached here.
211 // Number of active elements in the clk_ table (the rest is zeros).
213 u64 clk_
[kMaxTidInClock
]; // Fixed size vector clock.
215 bool IsAlreadyAcquired(const SyncClock
*src
) const;
216 bool HasAcquiredAfterRelease(const SyncClock
*dst
) const;
217 void UpdateCurrentThread(ClockCache
*c
, SyncClock
*dst
) const;
220 ALWAYS_INLINE u64
ThreadClock::get(unsigned tid
) const {
221 DCHECK_LT(tid
, kMaxTidInClock
);
225 ALWAYS_INLINE
void ThreadClock::set(u64 v
) {
226 DCHECK_GE(v
, clk_
[tid_
]);
230 ALWAYS_INLINE
void ThreadClock::tick() {
234 ALWAYS_INLINE uptr
ThreadClock::size() const {
238 ALWAYS_INLINE
void ThreadClock::NoteGlobalAcquire(u64 v
) {
239 // Here we rely on the fact that AcquireGlobal is protected by
240 // ThreadRegistryLock, thus only one thread at a time executes it
241 // and values passed to this function should not go backwards.
242 CHECK_LE(atomic_load_relaxed(&global_acquire_
), v
);
243 atomic_store_relaxed(&global_acquire_
, v
);
246 ALWAYS_INLINE
SyncClock::Iter
SyncClock::begin() {
250 ALWAYS_INLINE
SyncClock::Iter
SyncClock::end() {
251 return Iter(nullptr);
254 ALWAYS_INLINE uptr
SyncClock::size() const {
258 ALWAYS_INLINE
SyncClock::Iter::Iter(SyncClock
* parent
)
267 ALWAYS_INLINE
SyncClock::Iter
& SyncClock::Iter::operator++() {
269 if (UNLIKELY(pos_
>= end_
))
274 ALWAYS_INLINE
bool SyncClock::Iter::operator!=(const SyncClock::Iter
& other
) {
275 return parent_
!= other
.parent_
;
278 ALWAYS_INLINE ClockElem
&SyncClock::Iter::operator*() {
281 } // namespace __tsan
283 #endif // TSAN_CLOCK_H