1603c4be006d8c53905d736bf1f19a49f5ce98276Alexey Samsonov//===-- tsan_clock.cc -----------------------------------------------------===// 27ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany// 37ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany// The LLVM Compiler Infrastructure 47ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany// 57ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany// This file is distributed under the University of Illinois Open Source 67ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany// License. See LICENSE.TXT for details. 77ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany// 87ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany//===----------------------------------------------------------------------===// 97ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany// 107ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany// This file is a part of ThreadSanitizer (TSan), a race detector. 117ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany// 127ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany//===----------------------------------------------------------------------===// 137ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany#include "tsan_clock.h" 147ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany#include "tsan_rtl.h" 157ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany 162d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// SyncClock and ThreadClock implement vector clocks for sync variables 172d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// (mutexes, atomic variables, file descriptors, etc) and threads, respectively. 182d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// ThreadClock contains fixed-size vector clock for maximum number of threads. 192d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// SyncClock contains growable vector clock for currently necessary number of 202d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// threads. 212d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// Together they implement very simple model of operations, namely: 222d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 232d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// void ThreadClock::acquire(const SyncClock *src) { 242d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// for (int i = 0; i < kMaxThreads; i++) 252d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// clock[i] = max(clock[i], src->clock[i]); 262d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// } 272d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 282d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// void ThreadClock::release(SyncClock *dst) const { 292d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// for (int i = 0; i < kMaxThreads; i++) 302d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// dst->clock[i] = max(dst->clock[i], clock[i]); 312d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// } 322d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 332d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// void ThreadClock::ReleaseStore(SyncClock *dst) const { 342d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// for (int i = 0; i < kMaxThreads; i++) 352d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// dst->clock[i] = clock[i]; 362d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// } 372d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 382d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// void ThreadClock::acq_rel(SyncClock *dst) { 392d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// acquire(dst); 402d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// release(dst); 417ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany// } 422d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 432d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// Conformance to this model is extensively verified in tsan_clock_test.cc. 442d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// However, the implementation is significantly more complex. The complexity 452d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// allows to implement important classes of use cases in O(1) instead of O(N). 462d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 472d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// The use cases are: 482d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 1. Singleton/once atomic that has a single release-store operation followed 492d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// by zillions of acquire-loads (the acquire-load is O(1)). 502d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 2. Thread-local mutex (both lock and unlock can be O(1)). 512d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 3. Leaf mutex (unlock is O(1)). 522d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 4. A mutex shared by 2 threads (both lock and unlock can be O(1)). 532d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 5. An atomic with a single writer (writes can be O(1)). 542d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// The implementation dynamically adopts to workload. So if an atomic is in 552d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// read-only phase, these reads will be O(1); if it later switches to read/write 562d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// phase, the implementation will correctly handle that by switching to O(N). 572d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 582d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// Thread-safety note: all const operations on SyncClock's are conducted under 592d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// a shared lock; all non-const operations on SyncClock's are conducted under 602d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// an exclusive lock; ThreadClock's are private to respective threads and so 612d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// do not need any protection. 622d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 632d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// Description of ThreadClock state: 642d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// clk_ - fixed size vector clock. 652d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// nclk_ - effective size of the vector clock (the rest is zeros). 662d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// tid_ - index of the thread associated with he clock ("current thread"). 672d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// last_acquire_ - current thread time when it acquired something from 682d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// other threads. 692d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 702d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// Description of SyncClock state: 712d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// clk_ - variable size vector clock, low kClkBits hold timestamp, 722d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// the remaining bits hold "acquired" flag (the actual value is thread's 732d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// reused counter); 742d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// if acquried == thr->reused_, then the respective thread has already 752d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// acquired this clock (except possibly dirty_tids_). 762d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// dirty_tids_ - holds up to two indeces in the vector clock that other threads 772d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// need to acquire regardless of "acquired" flag value; 782d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// release_store_tid_ - denotes that the clock state is a result of 792d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// release-store operation by the thread with release_store_tid_ index. 802d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// release_store_reused_ - reuse count of release_store_tid_. 812d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 822d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// We don't have ThreadState in these methods, so this is an ugly hack that 832d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// works only in C++. 842d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#ifndef TSAN_GO 852d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines# define CPP_STAT_INC(typ) StatInc(cur_thread(), typ) 862d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#else 872d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines# define CPP_STAT_INC(typ) (void)0 882d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#endif 897ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany 907ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryanynamespace __tsan { 917ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany 922d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesconst unsigned kInvalidTid = (unsigned)-1; 932d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 942d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen HinesThreadClock::ThreadClock(unsigned tid, unsigned reused) 952d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines : tid_(tid) 962d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines , reused_(reused + 1) { // 0 has special meaning 972d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CHECK_LT(tid, kMaxTidInClock); 982d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CHECK_EQ(reused_, ((u64)reused_ << kClkBits) >> kClkBits); 992d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines nclk_ = tid_ + 1; 1002d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines last_acquire_ = 0; 1012d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines internal_memset(clk_, 0, sizeof(clk_)); 1022d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines clk_[tid_].reused = reused_; 1037ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany} 1047ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany 1057ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryanyvoid ThreadClock::acquire(const SyncClock *src) { 1067ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany DCHECK(nclk_ <= kMaxTid); 1077ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany DCHECK(src->clk_.Size() <= kMaxTid); 1082d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CPP_STAT_INC(StatClockAcquire); 1097ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany 1102d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Check if it's empty -> no need to do anything. 1117ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany const uptr nclk = src->clk_.Size(); 1122d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (nclk == 0) { 1132d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CPP_STAT_INC(StatClockAcquireEmpty); 1147ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany return; 1152d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1162d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1172d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Check if we've already acquired src after the last release operation on src 1182d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool acquired = false; 1192d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (nclk > tid_) { 1202d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CPP_STAT_INC(StatClockAcquireLarge); 1212d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (src->clk_[tid_].reused == reused_) { 1222d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CPP_STAT_INC(StatClockAcquireRepeat); 1232d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (unsigned i = 0; i < kDirtyTids; i++) { 1242d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines unsigned tid = src->dirty_tids_[i]; 1252d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (tid != kInvalidTid) { 1262d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines u64 epoch = src->clk_[tid].epoch; 1272d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (clk_[tid].epoch < epoch) { 1282d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines clk_[tid].epoch = epoch; 1292d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines acquired = true; 1302d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1312d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1322d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1332d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (acquired) { 1342d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CPP_STAT_INC(StatClockAcquiredSomething); 1352d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines last_acquire_ = clk_[tid_].epoch; 1362d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1372d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return; 1382d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1392d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1402d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1412d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // O(N) acquire. 1422d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CPP_STAT_INC(StatClockAcquireFull); 1437ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany nclk_ = max(nclk_, nclk); 1447ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany for (uptr i = 0; i < nclk; i++) { 1452d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines u64 epoch = src->clk_[i].epoch; 1462d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (clk_[i].epoch < epoch) { 1472d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines clk_[i].epoch = epoch; 1482d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines acquired = true; 1492d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1502d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1512d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1522d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Remember that this thread has acquired this clock. 1532d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (nclk > tid_) 1542d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines src->clk_[tid_].reused = reused_; 1552d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1562d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (acquired) { 1572d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CPP_STAT_INC(StatClockAcquiredSomething); 1582d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines last_acquire_ = clk_[tid_].epoch; 1597ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany } 1607ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany} 1617ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany 1627ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryanyvoid ThreadClock::release(SyncClock *dst) const { 1632d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines DCHECK_LE(nclk_, kMaxTid); 1642d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines DCHECK_LE(dst->clk_.Size(), kMaxTid); 1657ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany 1662d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (dst->clk_.Size() == 0) { 1672d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // ReleaseStore will correctly set release_store_tid_, 1682d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // which can be important for future operations. 1692d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ReleaseStore(dst); 1702d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return; 1712d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1722d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1732d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CPP_STAT_INC(StatClockRelease); 1742d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Check if we need to resize dst. 1752d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (dst->clk_.Size() < nclk_) { 1762d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CPP_STAT_INC(StatClockReleaseResize); 1777ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany dst->clk_.Resize(nclk_); 1782d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1792d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1802d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Check if we had not acquired anything from other threads 1812d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // since the last release on dst. If so, we need to update 1822d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // only dst->clk_[tid_]. 1832d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (dst->clk_[tid_].epoch > last_acquire_) { 1842d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines UpdateCurrentThread(dst); 1852d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (dst->release_store_tid_ != tid_ || 1862d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines dst->release_store_reused_ != reused_) 1872d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines dst->release_store_tid_ = kInvalidTid; 1882d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return; 1892d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1902d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1912d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // O(N) release. 1922d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CPP_STAT_INC(StatClockReleaseFull); 1932d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // First, remember whether we've acquired dst. 1942d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool acquired = IsAlreadyAcquired(dst); 1952d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (acquired) 1962d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CPP_STAT_INC(StatClockReleaseAcquired); 1972d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Update dst->clk_. 1987ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany for (uptr i = 0; i < nclk_; i++) { 1992d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines dst->clk_[i].epoch = max(dst->clk_[i].epoch, clk_[i].epoch); 2002d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines dst->clk_[i].reused = 0; 2017ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany } 2022d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Clear 'acquired' flag in the remaining elements. 2032d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (nclk_ < dst->clk_.Size()) 2042d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CPP_STAT_INC(StatClockReleaseClearTail); 2052d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i = nclk_; i < dst->clk_.Size(); i++) 2062d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines dst->clk_[i].reused = 0; 2072d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (unsigned i = 0; i < kDirtyTids; i++) 2082d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines dst->dirty_tids_[i] = kInvalidTid; 2092d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines dst->release_store_tid_ = kInvalidTid; 2102d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines dst->release_store_reused_ = 0; 2112d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // If we've acquired dst, remember this fact, 2122d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // so that we don't need to acquire it on next acquire. 2132d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (acquired) 2142d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines dst->clk_[tid_].reused = reused_; 2157ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany} 2167ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany 2179d150bdb433ddd092073dabd87ba15aa176603a1Dmitry Vyukovvoid ThreadClock::ReleaseStore(SyncClock *dst) const { 2189d150bdb433ddd092073dabd87ba15aa176603a1Dmitry Vyukov DCHECK(nclk_ <= kMaxTid); 2199d150bdb433ddd092073dabd87ba15aa176603a1Dmitry Vyukov DCHECK(dst->clk_.Size() <= kMaxTid); 2202d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CPP_STAT_INC(StatClockStore); 2219d150bdb433ddd092073dabd87ba15aa176603a1Dmitry Vyukov 2222d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Check if we need to resize dst. 2232d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (dst->clk_.Size() < nclk_) { 2242d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CPP_STAT_INC(StatClockStoreResize); 2259d150bdb433ddd092073dabd87ba15aa176603a1Dmitry Vyukov dst->clk_.Resize(nclk_); 2262d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2272d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 2282d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (dst->release_store_tid_ == tid_ && 2292d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines dst->release_store_reused_ == reused_ && 2302d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines dst->clk_[tid_].epoch > last_acquire_) { 2312d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CPP_STAT_INC(StatClockStoreFast); 2322d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines UpdateCurrentThread(dst); 2332d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return; 2342d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2352d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 2362d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // O(N) release-store. 2372d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CPP_STAT_INC(StatClockStoreFull); 2382d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i = 0; i < nclk_; i++) { 2392d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines dst->clk_[i].epoch = clk_[i].epoch; 2402d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines dst->clk_[i].reused = 0; 2412d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2422d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Clear the tail of dst->clk_. 2432d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (nclk_ < dst->clk_.Size()) { 2442d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines internal_memset(&dst->clk_[nclk_], 0, 2452d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines (dst->clk_.Size() - nclk_) * sizeof(dst->clk_[0])); 2462d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CPP_STAT_INC(StatClockStoreTail); 2472d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2482d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (unsigned i = 0; i < kDirtyTids; i++) 2492d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines dst->dirty_tids_[i] = kInvalidTid; 2502d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines dst->release_store_tid_ = tid_; 2512d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines dst->release_store_reused_ = reused_; 2522d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Rememeber that we don't need to acquire it in future. 2532d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines dst->clk_[tid_].reused = reused_; 2549d150bdb433ddd092073dabd87ba15aa176603a1Dmitry Vyukov} 2559d150bdb433ddd092073dabd87ba15aa176603a1Dmitry Vyukov 2567ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryanyvoid ThreadClock::acq_rel(SyncClock *dst) { 2572d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CPP_STAT_INC(StatClockAcquireRelease); 2587ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany acquire(dst); 2592d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ReleaseStore(dst); 2602d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 2612d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 2622d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// Updates only single element related to the current thread in dst->clk_. 2632d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesvoid ThreadClock::UpdateCurrentThread(SyncClock *dst) const { 2642d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Update the threads time, but preserve 'acquired' flag. 2652d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines dst->clk_[tid_].epoch = clk_[tid_].epoch; 2662d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 2672d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (unsigned i = 0; i < kDirtyTids; i++) { 2682d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (dst->dirty_tids_[i] == tid_) { 2692d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CPP_STAT_INC(StatClockReleaseFast1); 2702d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return; 2712d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2722d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (dst->dirty_tids_[i] == kInvalidTid) { 2732d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CPP_STAT_INC(StatClockReleaseFast2); 2742d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines dst->dirty_tids_[i] = tid_; 2752d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return; 2762d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2772d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2782d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Reset all 'acquired' flags, O(N). 2792d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CPP_STAT_INC(StatClockReleaseSlow); 2802d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i = 0; i < dst->clk_.Size(); i++) { 2812d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines dst->clk_[i].reused = 0; 2822d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2832d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (unsigned i = 0; i < kDirtyTids; i++) 2842d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines dst->dirty_tids_[i] = kInvalidTid; 2852d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 2862d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 2872d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// Checks whether the current threads has already acquired src. 2882d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesbool ThreadClock::IsAlreadyAcquired(const SyncClock *src) const { 2892d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (src->clk_[tid_].reused != reused_) 2902d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return false; 2912d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (unsigned i = 0; i < kDirtyTids; i++) { 2922d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines unsigned tid = src->dirty_tids_[i]; 2932d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (tid != kInvalidTid) { 2942d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (clk_[tid].epoch < src->clk_[tid].epoch) 2952d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return false; 2962d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2972d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2982d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return true; 2992d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 3002d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3012d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// Sets a single element in the vector clock. 3022d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// This function is called only from weird places like AcquireGlobal. 3032d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesvoid ThreadClock::set(unsigned tid, u64 v) { 3042d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines DCHECK_LT(tid, kMaxTid); 3052d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines DCHECK_GE(v, clk_[tid].epoch); 3062d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines clk_[tid].epoch = v; 3072d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (nclk_ <= tid) 3082d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines nclk_ = tid + 1; 3092d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines last_acquire_ = clk_[tid_].epoch; 3102d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 3112d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3122d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesvoid ThreadClock::DebugDump(int(*printf)(const char *s, ...)) { 3132d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines printf("clock=["); 3142d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i = 0; i < nclk_; i++) 3152d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines printf("%s%llu", i == 0 ? "" : ",", clk_[i].epoch); 3162d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines printf("] reused=["); 3172d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i = 0; i < nclk_; i++) 3182d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines printf("%s%llu", i == 0 ? "" : ",", clk_[i].reused); 3192d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines printf("] tid=%u/%u last_acq=%llu", 3202d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines tid_, reused_, last_acquire_); 3217ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany} 3227ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany 3237ac41484ea322e0ea5774df681660269f5dc321eKostya SerebryanySyncClock::SyncClock() 3242d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines : clk_(MBlockClock) { 3252d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines release_store_tid_ = kInvalidTid; 3262d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines release_store_reused_ = 0; 3272d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i = 0; i < kDirtyTids; i++) 3282d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines dirty_tids_[i] = kInvalidTid; 3292d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 3302d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3312d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesvoid SyncClock::Reset() { 3322d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines clk_.Reset(); 3335d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines Zero(); 3345d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines} 3355d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines 3365d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hinesvoid SyncClock::Zero() { 3375d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines clk_.Resize(0); 3382d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines release_store_tid_ = kInvalidTid; 3392d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines release_store_reused_ = 0; 3402d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i = 0; i < kDirtyTids; i++) 3412d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines dirty_tids_[i] = kInvalidTid; 3422d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 3432d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3442d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesvoid SyncClock::DebugDump(int(*printf)(const char *s, ...)) { 3452d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines printf("clock=["); 3462d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i = 0; i < clk_.Size(); i++) 3472d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines printf("%s%llu", i == 0 ? "" : ",", clk_[i].epoch); 3482d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines printf("] reused=["); 3492d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i = 0; i < clk_.Size(); i++) 3502d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines printf("%s%llu", i == 0 ? "" : ",", clk_[i].reused); 3512d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines printf("] release_store_tid=%d/%d dirty_tids=%d/%d", 3522d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines release_store_tid_, release_store_reused_, 3532d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines dirty_tids_[0], dirty_tids_[1]); 3547ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany} 3557ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany} // namespace __tsan 356