tsan_clock.cc revision 603c4be006d8c53905d736bf1f19a49f5ce98276
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 57namespace __tsan { 58 59ThreadClock::ThreadClock() { 60 nclk_ = 0; 61 for (uptr i = 0; i < (uptr)kMaxTidInClock; i++) 62 clk_[i] = 0; 63} 64 65void 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 79void 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 91void ThreadClock::acq_rel(SyncClock *dst) { 92 acquire(dst); 93 release(dst); 94} 95 96SyncClock::SyncClock() 97 : clk_(MBlockClock) { 98} 99} // namespace __tsan 100