#include "tsan_clock.h"
#include "tsan_rtl.h"
#include "sanitizer_common/sanitizer_placement_new.h"
#ifndef SANITIZER_GO
# define CPP_STAT_INC(typ) StatInc(cur_thread(), typ)
#else
# define CPP_STAT_INC(typ) (void)0
#endif
namespace __tsan {
const unsigned kInvalidTid = (unsigned)-1;
ThreadClock::ThreadClock(unsigned tid, unsigned reused)
: tid_(tid)
, reused_(reused + 1) { CHECK_LT(tid, kMaxTidInClock);
CHECK_EQ(reused_, ((u64)reused_ << kClkBits) >> kClkBits);
nclk_ = tid_ + 1;
last_acquire_ = 0;
internal_memset(clk_, 0, sizeof(clk_));
clk_[tid_].reused = reused_;
}
void ThreadClock::acquire(ClockCache *c, const SyncClock *src) {
DCHECK_LE(nclk_, kMaxTid);
DCHECK_LE(src->size_, kMaxTid);
CPP_STAT_INC(StatClockAcquire);
const uptr nclk = src->size_;
if (nclk == 0) {
CPP_STAT_INC(StatClockAcquireEmpty);
return;
}
bool acquired = false;
if (nclk > tid_) {
CPP_STAT_INC(StatClockAcquireLarge);
if (src->elem(tid_).reused == reused_) {
CPP_STAT_INC(StatClockAcquireRepeat);
for (unsigned i = 0; i < kDirtyTids; i++) {
unsigned tid = src->dirty_tids_[i];
if (tid != kInvalidTid) {
u64 epoch = src->elem(tid).epoch;
if (clk_[tid].epoch < epoch) {
clk_[tid].epoch = epoch;
acquired = true;
}
}
}
if (acquired) {
CPP_STAT_INC(StatClockAcquiredSomething);
last_acquire_ = clk_[tid_].epoch;
}
return;
}
}
CPP_STAT_INC(StatClockAcquireFull);
nclk_ = max(nclk_, nclk);
for (uptr i = 0; i < nclk; i++) {
u64 epoch = src->elem(i).epoch;
if (clk_[i].epoch < epoch) {
clk_[i].epoch = epoch;
acquired = true;
}
}
if (nclk > tid_)
src->elem(tid_).reused = reused_;
if (acquired) {
CPP_STAT_INC(StatClockAcquiredSomething);
last_acquire_ = clk_[tid_].epoch;
}
}
void ThreadClock::release(ClockCache *c, SyncClock *dst) const {
DCHECK_LE(nclk_, kMaxTid);
DCHECK_LE(dst->size_, kMaxTid);
if (dst->size_ == 0) {
ReleaseStore(c, dst);
return;
}
CPP_STAT_INC(StatClockRelease);
if (dst->size_ < nclk_)
dst->Resize(c, nclk_);
if (dst->elem(tid_).epoch > last_acquire_) {
UpdateCurrentThread(dst);
if (dst->release_store_tid_ != tid_ ||
dst->release_store_reused_ != reused_)
dst->release_store_tid_ = kInvalidTid;
return;
}
CPP_STAT_INC(StatClockReleaseFull);
bool acquired = IsAlreadyAcquired(dst);
if (acquired)
CPP_STAT_INC(StatClockReleaseAcquired);
for (uptr i = 0; i < nclk_; i++) {
ClockElem &ce = dst->elem(i);
ce.epoch = max(ce.epoch, clk_[i].epoch);
ce.reused = 0;
}
if (nclk_ < dst->size_)
CPP_STAT_INC(StatClockReleaseClearTail);
for (uptr i = nclk_; i < dst->size_; i++)
dst->elem(i).reused = 0;
for (unsigned i = 0; i < kDirtyTids; i++)
dst->dirty_tids_[i] = kInvalidTid;
dst->release_store_tid_ = kInvalidTid;
dst->release_store_reused_ = 0;
if (acquired)
dst->elem(tid_).reused = reused_;
}
void ThreadClock::ReleaseStore(ClockCache *c, SyncClock *dst) const {
DCHECK_LE(nclk_, kMaxTid);
DCHECK_LE(dst->size_, kMaxTid);
CPP_STAT_INC(StatClockStore);
if (dst->size_ < nclk_)
dst->Resize(c, nclk_);
if (dst->release_store_tid_ == tid_ &&
dst->release_store_reused_ == reused_ &&
dst->elem(tid_).epoch > last_acquire_) {
CPP_STAT_INC(StatClockStoreFast);
UpdateCurrentThread(dst);
return;
}
CPP_STAT_INC(StatClockStoreFull);
for (uptr i = 0; i < nclk_; i++) {
ClockElem &ce = dst->elem(i);
ce.epoch = clk_[i].epoch;
ce.reused = 0;
}
if (nclk_ < dst->size_) {
for (uptr i = nclk_; i < dst->size_; i++) {
ClockElem &ce = dst->elem(i);
ce.epoch = 0;
ce.reused = 0;
}
CPP_STAT_INC(StatClockStoreTail);
}
for (unsigned i = 0; i < kDirtyTids; i++)
dst->dirty_tids_[i] = kInvalidTid;
dst->release_store_tid_ = tid_;
dst->release_store_reused_ = reused_;
dst->elem(tid_).reused = reused_;
}
void ThreadClock::acq_rel(ClockCache *c, SyncClock *dst) {
CPP_STAT_INC(StatClockAcquireRelease);
acquire(c, dst);
ReleaseStore(c, dst);
}
void ThreadClock::UpdateCurrentThread(SyncClock *dst) const {
dst->elem(tid_).epoch = clk_[tid_].epoch;
for (unsigned i = 0; i < kDirtyTids; i++) {
if (dst->dirty_tids_[i] == tid_) {
CPP_STAT_INC(StatClockReleaseFast1);
return;
}
if (dst->dirty_tids_[i] == kInvalidTid) {
CPP_STAT_INC(StatClockReleaseFast2);
dst->dirty_tids_[i] = tid_;
return;
}
}
CPP_STAT_INC(StatClockReleaseSlow);
for (uptr i = 0; i < dst->size_; i++)
dst->elem(i).reused = 0;
for (unsigned i = 0; i < kDirtyTids; i++)
dst->dirty_tids_[i] = kInvalidTid;
}
bool ThreadClock::IsAlreadyAcquired(const SyncClock *src) const {
if (src->elem(tid_).reused != reused_)
return false;
for (unsigned i = 0; i < kDirtyTids; i++) {
unsigned tid = src->dirty_tids_[i];
if (tid != kInvalidTid) {
if (clk_[tid].epoch < src->elem(tid).epoch)
return false;
}
}
return true;
}
void SyncClock::Resize(ClockCache *c, uptr nclk) {
CPP_STAT_INC(StatClockReleaseResize);
if (RoundUpTo(nclk, ClockBlock::kClockCount) <=
RoundUpTo(size_, ClockBlock::kClockCount)) {
size_ = nclk;
return;
}
if (nclk <= ClockBlock::kClockCount) {
CHECK_EQ(size_, 0);
CHECK_EQ(tab_, 0);
CHECK_EQ(tab_idx_, 0);
size_ = nclk;
tab_idx_ = ctx->clock_alloc.Alloc(c);
tab_ = ctx->clock_alloc.Map(tab_idx_);
internal_memset(tab_, 0, sizeof(*tab_));
return;
}
if (size_ == 0) {
tab_idx_ = ctx->clock_alloc.Alloc(c);
tab_ = ctx->clock_alloc.Map(tab_idx_);
internal_memset(tab_, 0, sizeof(*tab_));
} else if (size_ <= ClockBlock::kClockCount) {
u32 old = tab_idx_;
tab_idx_ = ctx->clock_alloc.Alloc(c);
tab_ = ctx->clock_alloc.Map(tab_idx_);
internal_memset(tab_, 0, sizeof(*tab_));
tab_->table[0] = old;
}
for (uptr i = RoundUpTo(size_, ClockBlock::kClockCount);
i < nclk; i += ClockBlock::kClockCount) {
u32 idx = ctx->clock_alloc.Alloc(c);
ClockBlock *cb = ctx->clock_alloc.Map(idx);
internal_memset(cb, 0, sizeof(*cb));
CHECK_EQ(tab_->table[i/ClockBlock::kClockCount], 0);
tab_->table[i/ClockBlock::kClockCount] = idx;
}
size_ = nclk;
}
void ThreadClock::set(unsigned tid, u64 v) {
DCHECK_LT(tid, kMaxTid);
DCHECK_GE(v, clk_[tid].epoch);
clk_[tid].epoch = v;
if (nclk_ <= tid)
nclk_ = tid + 1;
last_acquire_ = clk_[tid_].epoch;
}
void ThreadClock::DebugDump(int(*printf)(const char *s, ...)) {
printf("clock=[");
for (uptr i = 0; i < nclk_; i++)
printf("%s%llu", i == 0 ? "" : ",", clk_[i].epoch);
printf("] reused=[");
for (uptr i = 0; i < nclk_; i++)
printf("%s%llu", i == 0 ? "" : ",", clk_[i].reused);
printf("] tid=%u/%u last_acq=%llu",
tid_, reused_, last_acquire_);
}
SyncClock::SyncClock()
: release_store_tid_(kInvalidTid)
, release_store_reused_()
, tab_()
, tab_idx_()
, size_() {
for (uptr i = 0; i < kDirtyTids; i++)
dirty_tids_[i] = kInvalidTid;
}
SyncClock::~SyncClock() {
CHECK_EQ(size_, 0);
CHECK_EQ(tab_, 0);
CHECK_EQ(tab_idx_, 0);
}
void SyncClock::Reset(ClockCache *c) {
if (size_ == 0) {
} else if (size_ <= ClockBlock::kClockCount) {
ctx->clock_alloc.Free(c, tab_idx_);
} else {
for (uptr i = 0; i < size_; i += ClockBlock::kClockCount)
ctx->clock_alloc.Free(c, tab_->table[i / ClockBlock::kClockCount]);
ctx->clock_alloc.Free(c, tab_idx_);
}
tab_ = 0;
tab_idx_ = 0;
size_ = 0;
release_store_tid_ = kInvalidTid;
release_store_reused_ = 0;
for (uptr i = 0; i < kDirtyTids; i++)
dirty_tids_[i] = kInvalidTid;
}
ClockElem &SyncClock::elem(unsigned tid) const {
DCHECK_LT(tid, size_);
if (size_ <= ClockBlock::kClockCount)
return tab_->clock[tid];
u32 idx = tab_->table[tid / ClockBlock::kClockCount];
ClockBlock *cb = ctx->clock_alloc.Map(idx);
return cb->clock[tid % ClockBlock::kClockCount];
}
void SyncClock::DebugDump(int(*printf)(const char *s, ...)) {
printf("clock=[");
for (uptr i = 0; i < size_; i++)
printf("%s%llu", i == 0 ? "" : ",", elem(i).epoch);
printf("] reused=[");
for (uptr i = 0; i < size_; i++)
printf("%s%llu", i == 0 ? "" : ",", elem(i).reused);
printf("] release_store_tid=%d/%d dirty_tids=%d/%d",
release_store_tid_, release_store_reused_,
dirty_tids_[0], dirty_tids_[1]);
}
}