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
ThreadClock()59 ThreadClock::ThreadClock() {
60 nclk_ = 0;
61 for (uptr i = 0; i < (uptr)kMaxTidInClock; i++)
62 clk_[i] = 0;
63 }
64
acquire(const SyncClock * src)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
release(SyncClock * dst) const79 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
ReleaseStore(SyncClock * dst) const91 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
acq_rel(SyncClock * dst)103 void ThreadClock::acq_rel(SyncClock *dst) {
104 acquire(dst);
105 release(dst);
106 }
107
SyncClock()108 SyncClock::SyncClock()
109 : clk_(MBlockClock) {
110 }
111 } // namespace __tsan
112