1 //===-- tsan_clock.h --------------------------------------------*- C++ -*-===//
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 #ifndef TSAN_CLOCK_H
14 #define TSAN_CLOCK_H
15 
16 #include "tsan_defs.h"
17 #include "tsan_dense_alloc.h"
18 
19 namespace __tsan {
20 
21 struct ClockElem {
22   u64 epoch  : kClkBits;
23   u64 reused : 64 - kClkBits;
24 };
25 
26 struct ClockBlock {
27   static const uptr kSize = 512;
28   static const uptr kTableSize = kSize / sizeof(u32);
29   static const uptr kClockCount = kSize / sizeof(ClockElem);
30 
31   union {
32     u32       table[kTableSize];
33     ClockElem clock[kClockCount];
34   };
35 
ClockBlockClockBlock36   ClockBlock() {
37   }
38 };
39 
40 typedef DenseSlabAlloc<ClockBlock, 1<<16, 1<<10> ClockAlloc;
41 typedef DenseSlabAllocCache ClockCache;
42 
43 // The clock that lives in sync variables (mutexes, atomics, etc).
44 class SyncClock {
45  public:
46   SyncClock();
47   ~SyncClock();
48 
size()49   uptr size() const {
50     return size_;
51   }
52 
get(unsigned tid)53   u64 get(unsigned tid) const {
54     return elem(tid).epoch;
55   }
56 
57   void Resize(ClockCache *c, uptr nclk);
58   void Reset(ClockCache *c);
59 
60   void DebugDump(int(*printf)(const char *s, ...));
61 
62  private:
63   friend struct ThreadClock;
64   static const uptr kDirtyTids = 2;
65 
66   unsigned release_store_tid_;
67   unsigned release_store_reused_;
68   unsigned dirty_tids_[kDirtyTids];
69   // tab_ contains indirect pointer to a 512b block using DenseSlabAlloc.
70   // If size_ <= 64, then tab_ points to an array with 64 ClockElem's.
71   // Otherwise, tab_ points to an array with 128 u32 elements,
72   // each pointing to the second-level 512b block with 64 ClockElem's.
73   ClockBlock *tab_;
74   u32 tab_idx_;
75   u32 size_;
76 
77   ClockElem &elem(unsigned tid) const;
78 };
79 
80 // The clock that lives in threads.
81 struct ThreadClock {
82  public:
83   typedef DenseSlabAllocCache Cache;
84 
85   explicit ThreadClock(unsigned tid, unsigned reused = 0);
86 
getThreadClock87   u64 get(unsigned tid) const {
88     DCHECK_LT(tid, kMaxTidInClock);
89     return clk_[tid].epoch;
90   }
91 
92   void set(unsigned tid, u64 v);
93 
setThreadClock94   void set(u64 v) {
95     DCHECK_GE(v, clk_[tid_].epoch);
96     clk_[tid_].epoch = v;
97   }
98 
tickThreadClock99   void tick() {
100     clk_[tid_].epoch++;
101   }
102 
sizeThreadClock103   uptr size() const {
104     return nclk_;
105   }
106 
107   void acquire(ClockCache *c, const SyncClock *src);
108   void release(ClockCache *c, SyncClock *dst) const;
109   void acq_rel(ClockCache *c, SyncClock *dst);
110   void ReleaseStore(ClockCache *c, SyncClock *dst) const;
111 
112   void DebugReset();
113   void DebugDump(int(*printf)(const char *s, ...));
114 
115  private:
116   static const uptr kDirtyTids = SyncClock::kDirtyTids;
117   const unsigned tid_;
118   const unsigned reused_;
119   u64 last_acquire_;
120   uptr nclk_;
121   ClockElem clk_[kMaxTidInClock];
122 
123   bool IsAlreadyAcquired(const SyncClock *src) const;
124   void UpdateCurrentThread(SyncClock *dst) const;
125 };
126 
127 }  // namespace __tsan
128 
129 #endif  // TSAN_CLOCK_H
130