File: | compiler-rt/lib/tsan/rtl/tsan_clock.cpp |
Warning: | line 606, column 16 Access to field 'blocks_' results in a dereference of a null pointer (loaded from field 'parent_') |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | //===-- tsan_clock.cpp ----------------------------------------------------===// | |||
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 | #include "tsan_clock.h" | |||
13 | #include "tsan_rtl.h" | |||
14 | #include "sanitizer_common/sanitizer_placement_new.h" | |||
15 | ||||
16 | // SyncClock and ThreadClock implement vector clocks for sync variables | |||
17 | // (mutexes, atomic variables, file descriptors, etc) and threads, respectively. | |||
18 | // ThreadClock contains fixed-size vector clock for maximum number of threads. | |||
19 | // SyncClock contains growable vector clock for currently necessary number of | |||
20 | // threads. | |||
21 | // Together they implement very simple model of operations, namely: | |||
22 | // | |||
23 | // void ThreadClock::acquire(const SyncClock *src) { | |||
24 | // for (int i = 0; i < kMaxThreads; i++) | |||
25 | // clock[i] = max(clock[i], src->clock[i]); | |||
26 | // } | |||
27 | // | |||
28 | // void ThreadClock::release(SyncClock *dst) const { | |||
29 | // for (int i = 0; i < kMaxThreads; i++) | |||
30 | // dst->clock[i] = max(dst->clock[i], clock[i]); | |||
31 | // } | |||
32 | // | |||
33 | // void ThreadClock::releaseStoreAcquire(SyncClock *sc) const { | |||
34 | // for (int i = 0; i < kMaxThreads; i++) { | |||
35 | // tmp = clock[i]; | |||
36 | // clock[i] = max(clock[i], sc->clock[i]); | |||
37 | // sc->clock[i] = tmp; | |||
38 | // } | |||
39 | // } | |||
40 | // | |||
41 | // void ThreadClock::ReleaseStore(SyncClock *dst) const { | |||
42 | // for (int i = 0; i < kMaxThreads; i++) | |||
43 | // dst->clock[i] = clock[i]; | |||
44 | // } | |||
45 | // | |||
46 | // void ThreadClock::acq_rel(SyncClock *dst) { | |||
47 | // acquire(dst); | |||
48 | // release(dst); | |||
49 | // } | |||
50 | // | |||
51 | // Conformance to this model is extensively verified in tsan_clock_test.cpp. | |||
52 | // However, the implementation is significantly more complex. The complexity | |||
53 | // allows to implement important classes of use cases in O(1) instead of O(N). | |||
54 | // | |||
55 | // The use cases are: | |||
56 | // 1. Singleton/once atomic that has a single release-store operation followed | |||
57 | // by zillions of acquire-loads (the acquire-load is O(1)). | |||
58 | // 2. Thread-local mutex (both lock and unlock can be O(1)). | |||
59 | // 3. Leaf mutex (unlock is O(1)). | |||
60 | // 4. A mutex shared by 2 threads (both lock and unlock can be O(1)). | |||
61 | // 5. An atomic with a single writer (writes can be O(1)). | |||
62 | // The implementation dynamically adopts to workload. So if an atomic is in | |||
63 | // read-only phase, these reads will be O(1); if it later switches to read/write | |||
64 | // phase, the implementation will correctly handle that by switching to O(N). | |||
65 | // | |||
66 | // Thread-safety note: all const operations on SyncClock's are conducted under | |||
67 | // a shared lock; all non-const operations on SyncClock's are conducted under | |||
68 | // an exclusive lock; ThreadClock's are private to respective threads and so | |||
69 | // do not need any protection. | |||
70 | // | |||
71 | // Description of SyncClock state: | |||
72 | // clk_ - variable size vector clock, low kClkBits hold timestamp, | |||
73 | // the remaining bits hold "acquired" flag (the actual value is thread's | |||
74 | // reused counter); | |||
75 | // if acquired == thr->reused_, then the respective thread has already | |||
76 | // acquired this clock (except possibly for dirty elements). | |||
77 | // dirty_ - holds up to two indices in the vector clock that other threads | |||
78 | // need to acquire regardless of "acquired" flag value; | |||
79 | // release_store_tid_ - denotes that the clock state is a result of | |||
80 | // release-store operation by the thread with release_store_tid_ index. | |||
81 | // release_store_reused_ - reuse count of release_store_tid_. | |||
82 | ||||
83 | namespace __tsan { | |||
84 | ||||
85 | static atomic_uint32_t *ref_ptr(ClockBlock *cb) { | |||
86 | return reinterpret_cast<atomic_uint32_t *>(&cb->table[ClockBlock::kRefIdx]); | |||
87 | } | |||
88 | ||||
89 | // Drop reference to the first level block idx. | |||
90 | static void UnrefClockBlock(ClockCache *c, u32 idx, uptr blocks) { | |||
91 | ClockBlock *cb = ctx->clock_alloc.Map(idx); | |||
92 | atomic_uint32_t *ref = ref_ptr(cb); | |||
93 | u32 v = atomic_load(ref, memory_order_acquire); | |||
94 | for (;;) { | |||
95 | CHECK_GT(v, 0)do { __sanitizer::u64 v1 = (__sanitizer::u64)((v)); __sanitizer ::u64 v2 = (__sanitizer::u64)((0)); if (__builtin_expect(!!(! (v1 > v2)), 0)) __sanitizer::CheckFailed("/build/llvm-toolchain-snapshot-14~++20211110111138+cffbfd01e37b/compiler-rt/lib/tsan/rtl/tsan_clock.cpp" , 95, "(" "(v)" ") " ">" " (" "(0)" ")", v1, v2); } while ( false); | |||
96 | if (v == 1) | |||
97 | break; | |||
98 | if (atomic_compare_exchange_strong(ref, &v, v - 1, memory_order_acq_rel)) | |||
99 | return; | |||
100 | } | |||
101 | // First level block owns second level blocks, so them as well. | |||
102 | for (uptr i = 0; i < blocks; i++) | |||
103 | ctx->clock_alloc.Free(c, cb->table[ClockBlock::kBlockIdx - i]); | |||
104 | ctx->clock_alloc.Free(c, idx); | |||
105 | } | |||
106 | ||||
107 | ThreadClock::ThreadClock(unsigned tid, unsigned reused) | |||
108 | : tid_(tid) | |||
109 | , reused_(reused + 1) // 0 has special meaning | |||
110 | , last_acquire_() | |||
111 | , global_acquire_() | |||
112 | , cached_idx_() | |||
113 | , cached_size_() | |||
114 | , cached_blocks_() { | |||
115 | CHECK_LT(tid, kMaxTidInClock)do { __sanitizer::u64 v1 = (__sanitizer::u64)((tid)); __sanitizer ::u64 v2 = (__sanitizer::u64)((kMaxTidInClock)); if (__builtin_expect (!!(!(v1 < v2)), 0)) __sanitizer::CheckFailed("/build/llvm-toolchain-snapshot-14~++20211110111138+cffbfd01e37b/compiler-rt/lib/tsan/rtl/tsan_clock.cpp" , 115, "(" "(tid)" ") " "<" " (" "(kMaxTidInClock)" ")", v1 , v2); } while (false); | |||
116 | CHECK_EQ(reused_, ((u64)reused_ << kClkBits) >> kClkBits)do { __sanitizer::u64 v1 = (__sanitizer::u64)((reused_)); __sanitizer ::u64 v2 = (__sanitizer::u64)((((u64)reused_ << kClkBits ) >> kClkBits)); if (__builtin_expect(!!(!(v1 == v2)), 0 )) __sanitizer::CheckFailed("/build/llvm-toolchain-snapshot-14~++20211110111138+cffbfd01e37b/compiler-rt/lib/tsan/rtl/tsan_clock.cpp" , 116, "(" "(reused_)" ") " "==" " (" "(((u64)reused_ << kClkBits) >> kClkBits)" ")", v1, v2); } while (false); | |||
117 | nclk_ = tid_ + 1; | |||
118 | internal_memset(clk_, 0, sizeof(clk_)); | |||
119 | } | |||
120 | ||||
121 | void ThreadClock::ResetCached(ClockCache *c) { | |||
122 | if (cached_idx_) { | |||
123 | UnrefClockBlock(c, cached_idx_, cached_blocks_); | |||
124 | cached_idx_ = 0; | |||
125 | cached_size_ = 0; | |||
126 | cached_blocks_ = 0; | |||
127 | } | |||
128 | } | |||
129 | ||||
130 | void ThreadClock::acquire(ClockCache *c, SyncClock *src) { | |||
131 | DCHECK_LE(nclk_, kMaxTid); | |||
132 | DCHECK_LE(src->size_, kMaxTid); | |||
133 | ||||
134 | // Check if it's empty -> no need to do anything. | |||
135 | const uptr nclk = src->size_; | |||
136 | if (nclk == 0) | |||
137 | return; | |||
138 | ||||
139 | bool acquired = false; | |||
140 | for (unsigned i = 0; i < kDirtyTids; i++) { | |||
141 | SyncClock::Dirty dirty = src->dirty_[i]; | |||
142 | unsigned tid = dirty.tid(); | |||
143 | if (tid != kInvalidTid) { | |||
144 | if (clk_[tid] < dirty.epoch) { | |||
145 | clk_[tid] = dirty.epoch; | |||
146 | acquired = true; | |||
147 | } | |||
148 | } | |||
149 | } | |||
150 | ||||
151 | // Check if we've already acquired src after the last release operation on src | |||
152 | if (tid_ >= nclk || src->elem(tid_).reused != reused_) { | |||
153 | // O(N) acquire. | |||
154 | nclk_ = max(nclk_, nclk); | |||
155 | u64 *dst_pos = &clk_[0]; | |||
156 | for (ClockElem &src_elem : *src) { | |||
157 | u64 epoch = src_elem.epoch; | |||
158 | if (*dst_pos < epoch) { | |||
159 | *dst_pos = epoch; | |||
160 | acquired = true; | |||
161 | } | |||
162 | dst_pos++; | |||
163 | } | |||
164 | ||||
165 | // Remember that this thread has acquired this clock. | |||
166 | if (nclk > tid_) | |||
167 | src->elem(tid_).reused = reused_; | |||
168 | } | |||
169 | ||||
170 | if (acquired) { | |||
171 | last_acquire_ = clk_[tid_]; | |||
172 | ResetCached(c); | |||
173 | } | |||
174 | } | |||
175 | ||||
176 | void ThreadClock::releaseStoreAcquire(ClockCache *c, SyncClock *sc) { | |||
177 | DCHECK_LE(nclk_, kMaxTid); | |||
178 | DCHECK_LE(sc->size_, kMaxTid); | |||
179 | ||||
180 | if (sc->size_ == 0) { | |||
181 | // ReleaseStore will correctly set release_store_tid_, | |||
182 | // which can be important for future operations. | |||
183 | ReleaseStore(c, sc); | |||
184 | return; | |||
185 | } | |||
186 | ||||
187 | nclk_ = max(nclk_, (uptr) sc->size_); | |||
188 | ||||
189 | // Check if we need to resize sc. | |||
190 | if (sc->size_ < nclk_) | |||
191 | sc->Resize(c, nclk_); | |||
192 | ||||
193 | bool acquired = false; | |||
194 | ||||
195 | sc->Unshare(c); | |||
196 | // Update sc->clk_. | |||
197 | sc->FlushDirty(); | |||
198 | uptr i = 0; | |||
199 | for (ClockElem &ce : *sc) { | |||
200 | u64 tmp = clk_[i]; | |||
201 | if (clk_[i] < ce.epoch) { | |||
202 | clk_[i] = ce.epoch; | |||
203 | acquired = true; | |||
204 | } | |||
205 | ce.epoch = tmp; | |||
206 | ce.reused = 0; | |||
207 | i++; | |||
208 | } | |||
209 | sc->release_store_tid_ = kInvalidTid; | |||
210 | sc->release_store_reused_ = 0; | |||
211 | ||||
212 | if (acquired) { | |||
213 | last_acquire_ = clk_[tid_]; | |||
214 | ResetCached(c); | |||
215 | } | |||
216 | } | |||
217 | ||||
218 | void ThreadClock::release(ClockCache *c, SyncClock *dst) { | |||
219 | DCHECK_LE(nclk_, kMaxTid); | |||
220 | DCHECK_LE(dst->size_, kMaxTid); | |||
221 | ||||
222 | if (dst->size_ == 0) { | |||
| ||||
223 | // ReleaseStore will correctly set release_store_tid_, | |||
224 | // which can be important for future operations. | |||
225 | ReleaseStore(c, dst); | |||
226 | return; | |||
227 | } | |||
228 | ||||
229 | // Check if we need to resize dst. | |||
230 | if (dst->size_ < nclk_) | |||
231 | dst->Resize(c, nclk_); | |||
232 | ||||
233 | // Check if we had not acquired anything from other threads | |||
234 | // since the last release on dst. If so, we need to update | |||
235 | // only dst->elem(tid_). | |||
236 | if (!HasAcquiredAfterRelease(dst)) { | |||
237 | UpdateCurrentThread(c, dst); | |||
238 | if (dst->release_store_tid_ != tid_ || | |||
239 | dst->release_store_reused_ != reused_) | |||
240 | dst->release_store_tid_ = kInvalidTid; | |||
241 | return; | |||
242 | } | |||
243 | ||||
244 | // O(N) release. | |||
245 | dst->Unshare(c); | |||
246 | // First, remember whether we've acquired dst. | |||
247 | bool acquired = IsAlreadyAcquired(dst); | |||
248 | // Update dst->clk_. | |||
249 | dst->FlushDirty(); | |||
250 | uptr i = 0; | |||
251 | for (ClockElem &ce : *dst) { | |||
252 | ce.epoch = max(ce.epoch, clk_[i]); | |||
253 | ce.reused = 0; | |||
254 | i++; | |||
255 | } | |||
256 | // Clear 'acquired' flag in the remaining elements. | |||
257 | dst->release_store_tid_ = kInvalidTid; | |||
258 | dst->release_store_reused_ = 0; | |||
259 | // If we've acquired dst, remember this fact, | |||
260 | // so that we don't need to acquire it on next acquire. | |||
261 | if (acquired) | |||
262 | dst->elem(tid_).reused = reused_; | |||
263 | } | |||
264 | ||||
265 | void ThreadClock::ReleaseStore(ClockCache *c, SyncClock *dst) { | |||
266 | DCHECK_LE(nclk_, kMaxTid); | |||
267 | DCHECK_LE(dst->size_, kMaxTid); | |||
268 | ||||
269 | if (dst->size_ == 0 && cached_idx_ != 0) { | |||
270 | // Reuse the cached clock. | |||
271 | // Note: we could reuse/cache the cached clock in more cases: | |||
272 | // we could update the existing clock and cache it, or replace it with the | |||
273 | // currently cached clock and release the old one. And for a shared | |||
274 | // existing clock, we could replace it with the currently cached; | |||
275 | // or unshare, update and cache. But, for simplicity, we currently reuse | |||
276 | // cached clock only when the target clock is empty. | |||
277 | dst->tab_ = ctx->clock_alloc.Map(cached_idx_); | |||
278 | dst->tab_idx_ = cached_idx_; | |||
279 | dst->size_ = cached_size_; | |||
280 | dst->blocks_ = cached_blocks_; | |||
281 | CHECK_EQ(dst->dirty_[0].tid(), kInvalidTid)do { __sanitizer::u64 v1 = (__sanitizer::u64)((dst->dirty_ [0].tid())); __sanitizer::u64 v2 = (__sanitizer::u64)((kInvalidTid )); if (__builtin_expect(!!(!(v1 == v2)), 0)) __sanitizer::CheckFailed ("/build/llvm-toolchain-snapshot-14~++20211110111138+cffbfd01e37b/compiler-rt/lib/tsan/rtl/tsan_clock.cpp" , 281, "(" "(dst->dirty_[0].tid())" ") " "==" " (" "(kInvalidTid)" ")", v1, v2); } while (false); | |||
282 | // The cached clock is shared (immutable), | |||
283 | // so this is where we store the current clock. | |||
284 | dst->dirty_[0].set_tid(tid_); | |||
285 | dst->dirty_[0].epoch = clk_[tid_]; | |||
286 | dst->release_store_tid_ = tid_; | |||
287 | dst->release_store_reused_ = reused_; | |||
288 | // Remember that we don't need to acquire it in future. | |||
289 | dst->elem(tid_).reused = reused_; | |||
290 | // Grab a reference. | |||
291 | atomic_fetch_add(ref_ptr(dst->tab_), 1, memory_order_relaxed); | |||
292 | return; | |||
293 | } | |||
294 | ||||
295 | // Check if we need to resize dst. | |||
296 | if (dst->size_ < nclk_) | |||
297 | dst->Resize(c, nclk_); | |||
298 | ||||
299 | if (dst->release_store_tid_ == tid_ && | |||
300 | dst->release_store_reused_ == reused_ && | |||
301 | !HasAcquiredAfterRelease(dst)) { | |||
302 | UpdateCurrentThread(c, dst); | |||
303 | return; | |||
304 | } | |||
305 | ||||
306 | // O(N) release-store. | |||
307 | dst->Unshare(c); | |||
308 | // Note: dst can be larger than this ThreadClock. | |||
309 | // This is fine since clk_ beyond size is all zeros. | |||
310 | uptr i = 0; | |||
311 | for (ClockElem &ce : *dst) { | |||
312 | ce.epoch = clk_[i]; | |||
313 | ce.reused = 0; | |||
314 | i++; | |||
315 | } | |||
316 | for (uptr i = 0; i < kDirtyTids; i++) dst->dirty_[i].set_tid(kInvalidTid); | |||
317 | dst->release_store_tid_ = tid_; | |||
318 | dst->release_store_reused_ = reused_; | |||
319 | // Remember that we don't need to acquire it in future. | |||
320 | dst->elem(tid_).reused = reused_; | |||
321 | ||||
322 | // If the resulting clock is cachable, cache it for future release operations. | |||
323 | // The clock is always cachable if we released to an empty sync object. | |||
324 | if (cached_idx_ == 0 && dst->Cachable()) { | |||
325 | // Grab a reference to the ClockBlock. | |||
326 | atomic_uint32_t *ref = ref_ptr(dst->tab_); | |||
327 | if (atomic_load(ref, memory_order_acquire) == 1) | |||
328 | atomic_store_relaxed(ref, 2); | |||
329 | else | |||
330 | atomic_fetch_add(ref_ptr(dst->tab_), 1, memory_order_relaxed); | |||
331 | cached_idx_ = dst->tab_idx_; | |||
332 | cached_size_ = dst->size_; | |||
333 | cached_blocks_ = dst->blocks_; | |||
334 | } | |||
335 | } | |||
336 | ||||
337 | void ThreadClock::acq_rel(ClockCache *c, SyncClock *dst) { | |||
338 | acquire(c, dst); | |||
339 | ReleaseStore(c, dst); | |||
340 | } | |||
341 | ||||
342 | // Updates only single element related to the current thread in dst->clk_. | |||
343 | void ThreadClock::UpdateCurrentThread(ClockCache *c, SyncClock *dst) const { | |||
344 | // Update the threads time, but preserve 'acquired' flag. | |||
345 | for (unsigned i = 0; i < kDirtyTids; i++) { | |||
346 | SyncClock::Dirty *dirty = &dst->dirty_[i]; | |||
347 | const unsigned tid = dirty->tid(); | |||
348 | if (tid == tid_ || tid == kInvalidTid) { | |||
349 | dirty->set_tid(tid_); | |||
350 | dirty->epoch = clk_[tid_]; | |||
351 | return; | |||
352 | } | |||
353 | } | |||
354 | // Reset all 'acquired' flags, O(N). | |||
355 | // We are going to touch dst elements, so we need to unshare it. | |||
356 | dst->Unshare(c); | |||
357 | dst->elem(tid_).epoch = clk_[tid_]; | |||
358 | for (uptr i = 0; i < dst->size_; i++) | |||
359 | dst->elem(i).reused = 0; | |||
360 | dst->FlushDirty(); | |||
361 | } | |||
362 | ||||
363 | // Checks whether the current thread has already acquired src. | |||
364 | bool ThreadClock::IsAlreadyAcquired(const SyncClock *src) const { | |||
365 | if (src->elem(tid_).reused != reused_) | |||
366 | return false; | |||
367 | for (unsigned i = 0; i < kDirtyTids; i++) { | |||
368 | SyncClock::Dirty dirty = src->dirty_[i]; | |||
369 | if (dirty.tid() != kInvalidTid) { | |||
370 | if (clk_[dirty.tid()] < dirty.epoch) | |||
371 | return false; | |||
372 | } | |||
373 | } | |||
374 | return true; | |||
375 | } | |||
376 | ||||
377 | // Checks whether the current thread has acquired anything | |||
378 | // from other clocks after releasing to dst (directly or indirectly). | |||
379 | bool ThreadClock::HasAcquiredAfterRelease(const SyncClock *dst) const { | |||
380 | const u64 my_epoch = dst->elem(tid_).epoch; | |||
381 | return my_epoch <= last_acquire_ || | |||
382 | my_epoch <= atomic_load_relaxed(&global_acquire_); | |||
383 | } | |||
384 | ||||
385 | // Sets a single element in the vector clock. | |||
386 | // This function is called only from weird places like AcquireGlobal. | |||
387 | void ThreadClock::set(ClockCache *c, unsigned tid, u64 v) { | |||
388 | DCHECK_LT(tid, kMaxTid); | |||
389 | DCHECK_GE(v, clk_[tid]); | |||
390 | clk_[tid] = v; | |||
391 | if (nclk_ <= tid) | |||
392 | nclk_ = tid + 1; | |||
393 | last_acquire_ = clk_[tid_]; | |||
394 | ResetCached(c); | |||
395 | } | |||
396 | ||||
397 | void ThreadClock::DebugDump(int(*printf)(const char *s, ...)) { | |||
398 | printf("clock=["); | |||
399 | for (uptr i = 0; i < nclk_; i++) | |||
400 | printf("%s%llu", i == 0 ? "" : ",", clk_[i]); | |||
401 | printf("] tid=%u/%u last_acq=%llu", tid_, reused_, last_acquire_); | |||
402 | } | |||
403 | ||||
404 | SyncClock::SyncClock() { | |||
405 | ResetImpl(); | |||
406 | } | |||
407 | ||||
408 | SyncClock::~SyncClock() { | |||
409 | // Reset must be called before dtor. | |||
410 | CHECK_EQ(size_, 0)do { __sanitizer::u64 v1 = (__sanitizer::u64)((size_)); __sanitizer ::u64 v2 = (__sanitizer::u64)((0)); if (__builtin_expect(!!(! (v1 == v2)), 0)) __sanitizer::CheckFailed("/build/llvm-toolchain-snapshot-14~++20211110111138+cffbfd01e37b/compiler-rt/lib/tsan/rtl/tsan_clock.cpp" , 410, "(" "(size_)" ") " "==" " (" "(0)" ")", v1, v2); } while (false); | |||
411 | CHECK_EQ(blocks_, 0)do { __sanitizer::u64 v1 = (__sanitizer::u64)((blocks_)); __sanitizer ::u64 v2 = (__sanitizer::u64)((0)); if (__builtin_expect(!!(! (v1 == v2)), 0)) __sanitizer::CheckFailed("/build/llvm-toolchain-snapshot-14~++20211110111138+cffbfd01e37b/compiler-rt/lib/tsan/rtl/tsan_clock.cpp" , 411, "(" "(blocks_)" ") " "==" " (" "(0)" ")", v1, v2); } while (false); | |||
412 | CHECK_EQ(tab_, 0)do { __sanitizer::u64 v1 = (__sanitizer::u64)((tab_)); __sanitizer ::u64 v2 = (__sanitizer::u64)((0)); if (__builtin_expect(!!(! (v1 == v2)), 0)) __sanitizer::CheckFailed("/build/llvm-toolchain-snapshot-14~++20211110111138+cffbfd01e37b/compiler-rt/lib/tsan/rtl/tsan_clock.cpp" , 412, "(" "(tab_)" ") " "==" " (" "(0)" ")", v1, v2); } while (false); | |||
413 | CHECK_EQ(tab_idx_, 0)do { __sanitizer::u64 v1 = (__sanitizer::u64)((tab_idx_)); __sanitizer ::u64 v2 = (__sanitizer::u64)((0)); if (__builtin_expect(!!(! (v1 == v2)), 0)) __sanitizer::CheckFailed("/build/llvm-toolchain-snapshot-14~++20211110111138+cffbfd01e37b/compiler-rt/lib/tsan/rtl/tsan_clock.cpp" , 413, "(" "(tab_idx_)" ") " "==" " (" "(0)" ")", v1, v2); } while (false); | |||
414 | } | |||
415 | ||||
416 | void SyncClock::Reset(ClockCache *c) { | |||
417 | if (size_) | |||
418 | UnrefClockBlock(c, tab_idx_, blocks_); | |||
419 | ResetImpl(); | |||
420 | } | |||
421 | ||||
422 | void SyncClock::ResetImpl() { | |||
423 | tab_ = 0; | |||
424 | tab_idx_ = 0; | |||
425 | size_ = 0; | |||
426 | blocks_ = 0; | |||
427 | release_store_tid_ = kInvalidTid; | |||
428 | release_store_reused_ = 0; | |||
429 | for (uptr i = 0; i < kDirtyTids; i++) dirty_[i].set_tid(kInvalidTid); | |||
430 | } | |||
431 | ||||
432 | void SyncClock::Resize(ClockCache *c, uptr nclk) { | |||
433 | Unshare(c); | |||
434 | if (nclk <= capacity()) { | |||
435 | // Memory is already allocated, just increase the size. | |||
436 | size_ = nclk; | |||
437 | return; | |||
438 | } | |||
439 | if (size_ == 0) { | |||
440 | // Grow from 0 to one-level table. | |||
441 | CHECK_EQ(size_, 0)do { __sanitizer::u64 v1 = (__sanitizer::u64)((size_)); __sanitizer ::u64 v2 = (__sanitizer::u64)((0)); if (__builtin_expect(!!(! (v1 == v2)), 0)) __sanitizer::CheckFailed("/build/llvm-toolchain-snapshot-14~++20211110111138+cffbfd01e37b/compiler-rt/lib/tsan/rtl/tsan_clock.cpp" , 441, "(" "(size_)" ") " "==" " (" "(0)" ")", v1, v2); } while (false); | |||
442 | CHECK_EQ(blocks_, 0)do { __sanitizer::u64 v1 = (__sanitizer::u64)((blocks_)); __sanitizer ::u64 v2 = (__sanitizer::u64)((0)); if (__builtin_expect(!!(! (v1 == v2)), 0)) __sanitizer::CheckFailed("/build/llvm-toolchain-snapshot-14~++20211110111138+cffbfd01e37b/compiler-rt/lib/tsan/rtl/tsan_clock.cpp" , 442, "(" "(blocks_)" ") " "==" " (" "(0)" ")", v1, v2); } while (false); | |||
443 | CHECK_EQ(tab_, 0)do { __sanitizer::u64 v1 = (__sanitizer::u64)((tab_)); __sanitizer ::u64 v2 = (__sanitizer::u64)((0)); if (__builtin_expect(!!(! (v1 == v2)), 0)) __sanitizer::CheckFailed("/build/llvm-toolchain-snapshot-14~++20211110111138+cffbfd01e37b/compiler-rt/lib/tsan/rtl/tsan_clock.cpp" , 443, "(" "(tab_)" ") " "==" " (" "(0)" ")", v1, v2); } while (false); | |||
444 | CHECK_EQ(tab_idx_, 0)do { __sanitizer::u64 v1 = (__sanitizer::u64)((tab_idx_)); __sanitizer ::u64 v2 = (__sanitizer::u64)((0)); if (__builtin_expect(!!(! (v1 == v2)), 0)) __sanitizer::CheckFailed("/build/llvm-toolchain-snapshot-14~++20211110111138+cffbfd01e37b/compiler-rt/lib/tsan/rtl/tsan_clock.cpp" , 444, "(" "(tab_idx_)" ") " "==" " (" "(0)" ")", v1, v2); } while (false); | |||
445 | tab_idx_ = ctx->clock_alloc.Alloc(c); | |||
446 | tab_ = ctx->clock_alloc.Map(tab_idx_); | |||
447 | internal_memset(tab_, 0, sizeof(*tab_)); | |||
448 | atomic_store_relaxed(ref_ptr(tab_), 1); | |||
449 | size_ = 1; | |||
450 | } else if (size_ > blocks_ * ClockBlock::kClockCount) { | |||
451 | u32 idx = ctx->clock_alloc.Alloc(c); | |||
452 | ClockBlock *new_cb = ctx->clock_alloc.Map(idx); | |||
453 | uptr top = size_ - blocks_ * ClockBlock::kClockCount; | |||
454 | CHECK_LT(top, ClockBlock::kClockCount)do { __sanitizer::u64 v1 = (__sanitizer::u64)((top)); __sanitizer ::u64 v2 = (__sanitizer::u64)((ClockBlock::kClockCount)); if ( __builtin_expect(!!(!(v1 < v2)), 0)) __sanitizer::CheckFailed ("/build/llvm-toolchain-snapshot-14~++20211110111138+cffbfd01e37b/compiler-rt/lib/tsan/rtl/tsan_clock.cpp" , 454, "(" "(top)" ") " "<" " (" "(ClockBlock::kClockCount)" ")", v1, v2); } while (false); | |||
455 | const uptr move = top * sizeof(tab_->clock[0]); | |||
456 | internal_memcpy(&new_cb->clock[0], tab_->clock, move); | |||
457 | internal_memset(&new_cb->clock[top], 0, sizeof(*new_cb) - move); | |||
458 | internal_memset(tab_->clock, 0, move); | |||
459 | append_block(idx); | |||
460 | } | |||
461 | // At this point we have first level table allocated and all clock elements | |||
462 | // are evacuated from it to a second level block. | |||
463 | // Add second level tables as necessary. | |||
464 | while (nclk > capacity()) { | |||
465 | u32 idx = ctx->clock_alloc.Alloc(c); | |||
466 | ClockBlock *cb = ctx->clock_alloc.Map(idx); | |||
467 | internal_memset(cb, 0, sizeof(*cb)); | |||
468 | append_block(idx); | |||
469 | } | |||
470 | size_ = nclk; | |||
471 | } | |||
472 | ||||
473 | // Flushes all dirty elements into the main clock array. | |||
474 | void SyncClock::FlushDirty() { | |||
475 | for (unsigned i = 0; i < kDirtyTids; i++) { | |||
476 | Dirty *dirty = &dirty_[i]; | |||
477 | if (dirty->tid() != kInvalidTid) { | |||
478 | CHECK_LT(dirty->tid(), size_)do { __sanitizer::u64 v1 = (__sanitizer::u64)((dirty->tid( ))); __sanitizer::u64 v2 = (__sanitizer::u64)((size_)); if (__builtin_expect (!!(!(v1 < v2)), 0)) __sanitizer::CheckFailed("/build/llvm-toolchain-snapshot-14~++20211110111138+cffbfd01e37b/compiler-rt/lib/tsan/rtl/tsan_clock.cpp" , 478, "(" "(dirty->tid())" ") " "<" " (" "(size_)" ")" , v1, v2); } while (false); | |||
479 | elem(dirty->tid()).epoch = dirty->epoch; | |||
480 | dirty->set_tid(kInvalidTid); | |||
481 | } | |||
482 | } | |||
483 | } | |||
484 | ||||
485 | bool SyncClock::IsShared() const { | |||
486 | if (size_ == 0) | |||
487 | return false; | |||
488 | atomic_uint32_t *ref = ref_ptr(tab_); | |||
489 | u32 v = atomic_load(ref, memory_order_acquire); | |||
490 | CHECK_GT(v, 0)do { __sanitizer::u64 v1 = (__sanitizer::u64)((v)); __sanitizer ::u64 v2 = (__sanitizer::u64)((0)); if (__builtin_expect(!!(! (v1 > v2)), 0)) __sanitizer::CheckFailed("/build/llvm-toolchain-snapshot-14~++20211110111138+cffbfd01e37b/compiler-rt/lib/tsan/rtl/tsan_clock.cpp" , 490, "(" "(v)" ") " ">" " (" "(0)" ")", v1, v2); } while (false); | |||
491 | return v > 1; | |||
492 | } | |||
493 | ||||
494 | // Unshares the current clock if it's shared. | |||
495 | // Shared clocks are immutable, so they need to be unshared before any updates. | |||
496 | // Note: this does not apply to dirty entries as they are not shared. | |||
497 | void SyncClock::Unshare(ClockCache *c) { | |||
498 | if (!IsShared()) | |||
499 | return; | |||
500 | // First, copy current state into old. | |||
501 | SyncClock old; | |||
502 | old.tab_ = tab_; | |||
503 | old.tab_idx_ = tab_idx_; | |||
504 | old.size_ = size_; | |||
505 | old.blocks_ = blocks_; | |||
506 | old.release_store_tid_ = release_store_tid_; | |||
507 | old.release_store_reused_ = release_store_reused_; | |||
508 | for (unsigned i = 0; i < kDirtyTids; i++) | |||
509 | old.dirty_[i] = dirty_[i]; | |||
510 | // Then, clear current object. | |||
511 | ResetImpl(); | |||
512 | // Allocate brand new clock in the current object. | |||
513 | Resize(c, old.size_); | |||
514 | // Now copy state back into this object. | |||
515 | Iter old_iter(&old); | |||
516 | for (ClockElem &ce : *this) { | |||
517 | ce = *old_iter; | |||
518 | ++old_iter; | |||
519 | } | |||
520 | release_store_tid_ = old.release_store_tid_; | |||
521 | release_store_reused_ = old.release_store_reused_; | |||
522 | for (unsigned i = 0; i < kDirtyTids; i++) | |||
523 | dirty_[i] = old.dirty_[i]; | |||
524 | // Drop reference to old and delete if necessary. | |||
525 | old.Reset(c); | |||
526 | } | |||
527 | ||||
528 | // Can we cache this clock for future release operations? | |||
529 | ALWAYS_INLINEinline __attribute__((always_inline)) bool SyncClock::Cachable() const { | |||
530 | if (size_ == 0) | |||
531 | return false; | |||
532 | for (unsigned i = 0; i < kDirtyTids; i++) { | |||
533 | if (dirty_[i].tid() != kInvalidTid) | |||
534 | return false; | |||
535 | } | |||
536 | return atomic_load_relaxed(ref_ptr(tab_)) == 1; | |||
537 | } | |||
538 | ||||
539 | // elem linearizes the two-level structure into linear array. | |||
540 | // Note: this is used only for one time accesses, vector operations use | |||
541 | // the iterator as it is much faster. | |||
542 | ALWAYS_INLINEinline __attribute__((always_inline)) ClockElem &SyncClock::elem(unsigned tid) const { | |||
543 | DCHECK_LT(tid, size_); | |||
544 | const uptr block = tid / ClockBlock::kClockCount; | |||
545 | DCHECK_LE(block, blocks_); | |||
546 | tid %= ClockBlock::kClockCount; | |||
547 | if (block == blocks_) | |||
548 | return tab_->clock[tid]; | |||
549 | u32 idx = get_block(block); | |||
550 | ClockBlock *cb = ctx->clock_alloc.Map(idx); | |||
551 | return cb->clock[tid]; | |||
552 | } | |||
553 | ||||
554 | ALWAYS_INLINEinline __attribute__((always_inline)) uptr SyncClock::capacity() const { | |||
555 | if (size_ == 0) | |||
556 | return 0; | |||
557 | uptr ratio = sizeof(ClockBlock::clock[0]) / sizeof(ClockBlock::table[0]); | |||
558 | // How many clock elements we can fit into the first level block. | |||
559 | // +1 for ref counter. | |||
560 | uptr top = ClockBlock::kClockCount - RoundUpTo(blocks_ + 1, ratio) / ratio; | |||
561 | return blocks_ * ClockBlock::kClockCount + top; | |||
562 | } | |||
563 | ||||
564 | ALWAYS_INLINEinline __attribute__((always_inline)) u32 SyncClock::get_block(uptr bi) const { | |||
565 | DCHECK(size_); | |||
566 | DCHECK_LT(bi, blocks_); | |||
567 | return tab_->table[ClockBlock::kBlockIdx - bi]; | |||
568 | } | |||
569 | ||||
570 | ALWAYS_INLINEinline __attribute__((always_inline)) void SyncClock::append_block(u32 idx) { | |||
571 | uptr bi = blocks_++; | |||
572 | CHECK_EQ(get_block(bi), 0)do { __sanitizer::u64 v1 = (__sanitizer::u64)((get_block(bi)) ); __sanitizer::u64 v2 = (__sanitizer::u64)((0)); if (__builtin_expect (!!(!(v1 == v2)), 0)) __sanitizer::CheckFailed("/build/llvm-toolchain-snapshot-14~++20211110111138+cffbfd01e37b/compiler-rt/lib/tsan/rtl/tsan_clock.cpp" , 572, "(" "(get_block(bi))" ") " "==" " (" "(0)" ")", v1, v2 ); } while (false); | |||
573 | tab_->table[ClockBlock::kBlockIdx - bi] = idx; | |||
574 | } | |||
575 | ||||
576 | // Used only by tests. | |||
577 | u64 SyncClock::get(unsigned tid) const { | |||
578 | for (unsigned i = 0; i < kDirtyTids; i++) { | |||
579 | Dirty dirty = dirty_[i]; | |||
580 | if (dirty.tid() == tid) | |||
581 | return dirty.epoch; | |||
582 | } | |||
583 | return elem(tid).epoch; | |||
584 | } | |||
585 | ||||
586 | // Used only by Iter test. | |||
587 | u64 SyncClock::get_clean(unsigned tid) const { | |||
588 | return elem(tid).epoch; | |||
589 | } | |||
590 | ||||
591 | void SyncClock::DebugDump(int(*printf)(const char *s, ...)) { | |||
592 | printf("clock=["); | |||
593 | for (uptr i = 0; i < size_; i++) | |||
594 | printf("%s%llu", i == 0 ? "" : ",", elem(i).epoch); | |||
595 | printf("] reused=["); | |||
596 | for (uptr i = 0; i < size_; i++) | |||
597 | printf("%s%llu", i == 0 ? "" : ",", elem(i).reused); | |||
598 | printf("] release_store_tid=%d/%d dirty_tids=%d[%llu]/%d[%llu]", | |||
599 | release_store_tid_, release_store_reused_, dirty_[0].tid(), | |||
600 | dirty_[0].epoch, dirty_[1].tid(), dirty_[1].epoch); | |||
601 | } | |||
602 | ||||
603 | void SyncClock::Iter::Next() { | |||
604 | // Finished with the current block, move on to the next one. | |||
605 | block_++; | |||
606 | if (block_ < parent_->blocks_) { | |||
| ||||
607 | // Iterate over the next second level block. | |||
608 | u32 idx = parent_->get_block(block_); | |||
609 | ClockBlock *cb = ctx->clock_alloc.Map(idx); | |||
610 | pos_ = &cb->clock[0]; | |||
611 | end_ = pos_ + min(parent_->size_ - block_ * ClockBlock::kClockCount, | |||
612 | ClockBlock::kClockCount); | |||
613 | return; | |||
614 | } | |||
615 | if (block_ == parent_->blocks_ && | |||
616 | parent_->size_ > parent_->blocks_ * ClockBlock::kClockCount) { | |||
617 | // Iterate over elements in the first level block. | |||
618 | pos_ = &parent_->tab_->clock[0]; | |||
619 | end_ = pos_ + min(parent_->size_ - block_ * ClockBlock::kClockCount, | |||
620 | ClockBlock::kClockCount); | |||
621 | return; | |||
622 | } | |||
623 | parent_ = nullptr; // denotes end | |||
624 | } | |||
625 | } // namespace __tsan |
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 << 22, 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__attribute__((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 | u32 tid() const { return tid_ == kShortInvalidTid ? kInvalidTid : tid_; } |
69 | void set_tid(u32 tid) { |
70 | tid_ = tid == kInvalidTid ? kShortInvalidTid : tid; |
71 | } |
72 | u64 epoch : kClkBits; |
73 | |
74 | private: |
75 | // Full kInvalidTid won't fit into Dirty::tid. |
76 | static const u64 kShortInvalidTid = (1ull << (64 - kClkBits)) - 1; |
77 | u64 tid_ : 64 - kClkBits; // kInvalidId if not active |
78 | }; |
79 | |
80 | static_assert(sizeof(Dirty) == 8, "Dirty is not 64bit"); |
81 | |
82 | unsigned release_store_tid_; |
83 | unsigned release_store_reused_; |
84 | Dirty dirty_[kDirtyTids]; |
85 | // If size_ is 0, tab_ is nullptr. |
86 | // If size <= 64 (kClockCount), tab_ contains pointer to an array with |
87 | // 64 ClockElem's (ClockBlock::clock). |
88 | // Otherwise, tab_ points to an array with up to 127 u32 elements, |
89 | // each pointing to the second-level 512b block with 64 ClockElem's. |
90 | // Unused space in the first level ClockBlock is used to store additional |
91 | // clock elements. |
92 | // The last u32 element in the first level ClockBlock is always used as |
93 | // reference counter. |
94 | // |
95 | // See the following scheme for details. |
96 | // All memory blocks are 512 bytes (allocated from ClockAlloc). |
97 | // Clock (clk) elements are 64 bits. |
98 | // Idx and ref are 32 bits. |
99 | // |
100 | // tab_ |
101 | // | |
102 | // \/ |
103 | // +----------------------------------------------------+ |
104 | // | clk128 | clk129 | ...unused... | idx1 | idx0 | ref | |
105 | // +----------------------------------------------------+ |
106 | // | | |
107 | // | \/ |
108 | // | +----------------+ |
109 | // | | clk0 ... clk63 | |
110 | // | +----------------+ |
111 | // \/ |
112 | // +------------------+ |
113 | // | clk64 ... clk127 | |
114 | // +------------------+ |
115 | // |
116 | // Note: dirty entries, if active, always override what's stored in the clock. |
117 | ClockBlock *tab_; |
118 | u32 tab_idx_; |
119 | u16 size_; |
120 | u16 blocks_; // Number of second level blocks. |
121 | |
122 | void Unshare(ClockCache *c); |
123 | bool IsShared() const; |
124 | bool Cachable() const; |
125 | void ResetImpl(); |
126 | void FlushDirty(); |
127 | uptr capacity() const; |
128 | u32 get_block(uptr bi) const; |
129 | void append_block(u32 idx); |
130 | ClockElem &elem(unsigned tid) const; |
131 | }; |
132 | |
133 | // The clock that lives in threads. |
134 | class ThreadClock { |
135 | public: |
136 | typedef DenseSlabAllocCache Cache; |
137 | |
138 | explicit ThreadClock(unsigned tid, unsigned reused = 0); |
139 | |
140 | u64 get(unsigned tid) const; |
141 | void set(ClockCache *c, unsigned tid, u64 v); |
142 | void set(u64 v); |
143 | void tick(); |
144 | uptr size() const; |
145 | |
146 | void acquire(ClockCache *c, SyncClock *src); |
147 | void releaseStoreAcquire(ClockCache *c, SyncClock *src); |
148 | void release(ClockCache *c, SyncClock *dst); |
149 | void acq_rel(ClockCache *c, SyncClock *dst); |
150 | void ReleaseStore(ClockCache *c, SyncClock *dst); |
151 | void ResetCached(ClockCache *c); |
152 | void NoteGlobalAcquire(u64 v); |
153 | |
154 | void DebugReset(); |
155 | void DebugDump(int(*printf)(const char *s, ...)); |
156 | |
157 | private: |
158 | static const uptr kDirtyTids = SyncClock::kDirtyTids; |
159 | // Index of the thread associated with he clock ("current thread"). |
160 | const unsigned tid_; |
161 | const unsigned reused_; // tid_ reuse count. |
162 | // Current thread time when it acquired something from other threads. |
163 | u64 last_acquire_; |
164 | |
165 | // Last time another thread has done a global acquire of this thread's clock. |
166 | // It helps to avoid problem described in: |
167 | // https://github.com/golang/go/issues/39186 |
168 | // See test/tsan/java_finalizer2.cpp for a regression test. |
169 | // Note the failuire is _extremely_ hard to hit, so if you are trying |
170 | // to reproduce it, you may want to run something like: |
171 | // $ go get golang.org/x/tools/cmd/stress |
172 | // $ stress -p=64 ./a.out |
173 | // |
174 | // The crux of the problem is roughly as follows. |
175 | // A number of O(1) optimizations in the clocks algorithm assume proper |
176 | // transitive cumulative propagation of clock values. The AcquireGlobal |
177 | // operation may produce an inconsistent non-linearazable view of |
178 | // thread clocks. Namely, it may acquire a later value from a thread |
179 | // with a higher ID, but fail to acquire an earlier value from a thread |
180 | // with a lower ID. If a thread that executed AcquireGlobal then releases |
181 | // to a sync clock, it will spoil the sync clock with the inconsistent |
182 | // values. If another thread later releases to the sync clock, the optimized |
183 | // algorithm may break. |
184 | // |
185 | // The exact sequence of events that leads to the failure. |
186 | // - thread 1 executes AcquireGlobal |
187 | // - thread 1 acquires value 1 for thread 2 |
188 | // - thread 2 increments clock to 2 |
189 | // - thread 2 releases to sync object 1 |
190 | // - thread 3 at time 1 |
191 | // - thread 3 acquires from sync object 1 |
192 | // - thread 3 increments clock to 2 |
193 | // - thread 1 acquires value 2 for thread 3 |
194 | // - thread 1 releases to sync object 2 |
195 | // - sync object 2 clock has 1 for thread 2 and 2 for thread 3 |
196 | // - thread 3 releases to sync object 2 |
197 | // - thread 3 sees value 2 in the clock for itself |
198 | // and decides that it has already released to the clock |
199 | // and did not acquire anything from other threads after that |
200 | // (the last_acquire_ check in release operation) |
201 | // - thread 3 does not update the value for thread 2 in the clock from 1 to 2 |
202 | // - thread 4 acquires from sync object 2 |
203 | // - thread 4 detects a false race with thread 2 |
204 | // as it should have been synchronized with thread 2 up to time 2, |
205 | // but because of the broken clock it is now synchronized only up to time 1 |
206 | // |
207 | // The global_acquire_ value helps to prevent this scenario. |
208 | // Namely, thread 3 will not trust any own clock values up to global_acquire_ |
209 | // for the purposes of the last_acquire_ optimization. |
210 | atomic_uint64_t global_acquire_; |
211 | |
212 | // Cached SyncClock (without dirty entries and release_store_tid_). |
213 | // We reuse it for subsequent store-release operations without intervening |
214 | // acquire operations. Since it is shared (and thus constant), clock value |
215 | // for the current thread is then stored in dirty entries in the SyncClock. |
216 | // We host a reference to the table while it is cached here. |
217 | u32 cached_idx_; |
218 | u16 cached_size_; |
219 | u16 cached_blocks_; |
220 | |
221 | // Number of active elements in the clk_ table (the rest is zeros). |
222 | uptr nclk_; |
223 | u64 clk_[kMaxTidInClock]; // Fixed size vector clock. |
224 | |
225 | bool IsAlreadyAcquired(const SyncClock *src) const; |
226 | bool HasAcquiredAfterRelease(const SyncClock *dst) const; |
227 | void UpdateCurrentThread(ClockCache *c, SyncClock *dst) const; |
228 | }; |
229 | |
230 | ALWAYS_INLINEinline __attribute__((always_inline)) u64 ThreadClock::get(unsigned tid) const { |
231 | DCHECK_LT(tid, kMaxTidInClock); |
232 | return clk_[tid]; |
233 | } |
234 | |
235 | ALWAYS_INLINEinline __attribute__((always_inline)) void ThreadClock::set(u64 v) { |
236 | DCHECK_GE(v, clk_[tid_]); |
237 | clk_[tid_] = v; |
238 | } |
239 | |
240 | ALWAYS_INLINEinline __attribute__((always_inline)) void ThreadClock::tick() { |
241 | clk_[tid_]++; |
242 | } |
243 | |
244 | ALWAYS_INLINEinline __attribute__((always_inline)) uptr ThreadClock::size() const { |
245 | return nclk_; |
246 | } |
247 | |
248 | ALWAYS_INLINEinline __attribute__((always_inline)) void ThreadClock::NoteGlobalAcquire(u64 v) { |
249 | // Here we rely on the fact that AcquireGlobal is protected by |
250 | // ThreadRegistryLock, thus only one thread at a time executes it |
251 | // and values passed to this function should not go backwards. |
252 | CHECK_LE(atomic_load_relaxed(&global_acquire_), v)do { __sanitizer::u64 v1 = (__sanitizer::u64)((atomic_load_relaxed (&global_acquire_))); __sanitizer::u64 v2 = (__sanitizer:: u64)((v)); if (__builtin_expect(!!(!(v1 <= v2)), 0)) __sanitizer ::CheckFailed("/build/llvm-toolchain-snapshot-14~++20211110111138+cffbfd01e37b/compiler-rt/lib/tsan/rtl/tsan_clock.h" , 252, "(" "(atomic_load_relaxed(&global_acquire_))" ") " "<=" " (" "(v)" ")", v1, v2); } while (false); |
253 | atomic_store_relaxed(&global_acquire_, v); |
254 | } |
255 | |
256 | ALWAYS_INLINEinline __attribute__((always_inline)) SyncClock::Iter SyncClock::begin() { |
257 | return Iter(this); |
258 | } |
259 | |
260 | ALWAYS_INLINEinline __attribute__((always_inline)) SyncClock::Iter SyncClock::end() { |
261 | return Iter(nullptr); |
262 | } |
263 | |
264 | ALWAYS_INLINEinline __attribute__((always_inline)) uptr SyncClock::size() const { |
265 | return size_; |
266 | } |
267 | |
268 | ALWAYS_INLINEinline __attribute__((always_inline)) SyncClock::Iter::Iter(SyncClock* parent) |
269 | : parent_(parent) |
270 | , pos_(nullptr) |
271 | , end_(nullptr) |
272 | , block_(-1) { |
273 | if (parent) |
274 | Next(); |
275 | } |
276 | |
277 | ALWAYS_INLINEinline __attribute__((always_inline)) SyncClock::Iter& SyncClock::Iter::operator++() { |
278 | pos_++; |
279 | if (UNLIKELY(pos_ >= end_)__builtin_expect(!!(pos_ >= end_), 0)) |
280 | Next(); |
281 | return *this; |
282 | } |
283 | |
284 | ALWAYS_INLINEinline __attribute__((always_inline)) bool SyncClock::Iter::operator!=(const SyncClock::Iter& other) { |
285 | return parent_ != other.parent_; |
286 | } |
287 | |
288 | ALWAYS_INLINEinline __attribute__((always_inline)) ClockElem &SyncClock::Iter::operator*() { |
289 | return *pos_; |
290 | } |
291 | } // namespace __tsan |
292 | |
293 | #endif // TSAN_CLOCK_H |