diff options
Diffstat (limited to 'contrib/llvm-project/compiler-rt/lib/tsan/rtl/tsan_clock.h')
-rw-r--r-- | contrib/llvm-project/compiler-rt/lib/tsan/rtl/tsan_clock.h | 225 |
1 files changed, 225 insertions, 0 deletions
diff --git a/contrib/llvm-project/compiler-rt/lib/tsan/rtl/tsan_clock.h b/contrib/llvm-project/compiler-rt/lib/tsan/rtl/tsan_clock.h new file mode 100644 index 000000000000..6a1d15a2a16d --- /dev/null +++ b/contrib/llvm-project/compiler-rt/lib/tsan/rtl/tsan_clock.h @@ -0,0 +1,225 @@ +//===-- tsan_clock.h --------------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file is a part of ThreadSanitizer (TSan), a race detector. +// +//===----------------------------------------------------------------------===// +#ifndef TSAN_CLOCK_H +#define TSAN_CLOCK_H + +#include "tsan_defs.h" +#include "tsan_dense_alloc.h" + +namespace __tsan { + +typedef DenseSlabAlloc<ClockBlock, 1<<16, 1<<10> ClockAlloc; +typedef DenseSlabAllocCache ClockCache; + +// The clock that lives in sync variables (mutexes, atomics, etc). +class SyncClock { + public: + SyncClock(); + ~SyncClock(); + + uptr size() const; + + // These are used only in tests. + u64 get(unsigned tid) const; + u64 get_clean(unsigned tid) const; + + void Resize(ClockCache *c, uptr nclk); + void Reset(ClockCache *c); + + void DebugDump(int(*printf)(const char *s, ...)); + + // Clock element iterator. + // Note: it iterates only over the table without regard to dirty entries. + class Iter { + public: + explicit Iter(SyncClock* parent); + Iter& operator++(); + bool operator!=(const Iter& other); + ClockElem &operator*(); + + private: + SyncClock *parent_; + // [pos_, end_) is the current continuous range of clock elements. + ClockElem *pos_; + ClockElem *end_; + int block_; // Current number of second level block. + + NOINLINE void Next(); + }; + + Iter begin(); + Iter end(); + + private: + friend class ThreadClock; + friend class Iter; + static const uptr kDirtyTids = 2; + + struct Dirty { + u64 epoch : kClkBits; + u64 tid : 64 - kClkBits; // kInvalidId if not active + }; + + unsigned release_store_tid_; + unsigned release_store_reused_; + Dirty dirty_[kDirtyTids]; + // If size_ is 0, tab_ is nullptr. + // If size <= 64 (kClockCount), tab_ contains pointer to an array with + // 64 ClockElem's (ClockBlock::clock). + // Otherwise, tab_ points to an array with up to 127 u32 elements, + // each pointing to the second-level 512b block with 64 ClockElem's. + // Unused space in the first level ClockBlock is used to store additional + // clock elements. + // The last u32 element in the first level ClockBlock is always used as + // reference counter. + // + // See the following scheme for details. + // All memory blocks are 512 bytes (allocated from ClockAlloc). + // Clock (clk) elements are 64 bits. + // Idx and ref are 32 bits. + // + // tab_ + // | + // \/ + // +----------------------------------------------------+ + // | clk128 | clk129 | ...unused... | idx1 | idx0 | ref | + // +----------------------------------------------------+ + // | | + // | \/ + // | +----------------+ + // | | clk0 ... clk63 | + // | +----------------+ + // \/ + // +------------------+ + // | clk64 ... clk127 | + // +------------------+ + // + // Note: dirty entries, if active, always override what's stored in the clock. + ClockBlock *tab_; + u32 tab_idx_; + u16 size_; + u16 blocks_; // Number of second level blocks. + + void Unshare(ClockCache *c); + bool IsShared() const; + bool Cachable() const; + void ResetImpl(); + void FlushDirty(); + uptr capacity() const; + u32 get_block(uptr bi) const; + void append_block(u32 idx); + ClockElem &elem(unsigned tid) const; +}; + +// The clock that lives in threads. +class ThreadClock { + public: + typedef DenseSlabAllocCache Cache; + + explicit ThreadClock(unsigned tid, unsigned reused = 0); + + u64 get(unsigned tid) const; + void set(ClockCache *c, unsigned tid, u64 v); + void set(u64 v); + void tick(); + uptr size() const; + + void acquire(ClockCache *c, SyncClock *src); + void release(ClockCache *c, SyncClock *dst); + void acq_rel(ClockCache *c, SyncClock *dst); + void ReleaseStore(ClockCache *c, SyncClock *dst); + void ResetCached(ClockCache *c); + + void DebugReset(); + void DebugDump(int(*printf)(const char *s, ...)); + + private: + static const uptr kDirtyTids = SyncClock::kDirtyTids; + // Index of the thread associated with he clock ("current thread"). + const unsigned tid_; + const unsigned reused_; // tid_ reuse count. + // Current thread time when it acquired something from other threads. + u64 last_acquire_; + + // Cached SyncClock (without dirty entries and release_store_tid_). + // We reuse it for subsequent store-release operations without intervening + // acquire operations. Since it is shared (and thus constant), clock value + // for the current thread is then stored in dirty entries in the SyncClock. + // We host a refernece to the table while it is cached here. + u32 cached_idx_; + u16 cached_size_; + u16 cached_blocks_; + + // Number of active elements in the clk_ table (the rest is zeros). + uptr nclk_; + u64 clk_[kMaxTidInClock]; // Fixed size vector clock. + + bool IsAlreadyAcquired(const SyncClock *src) const; + void UpdateCurrentThread(ClockCache *c, SyncClock *dst) const; +}; + +ALWAYS_INLINE u64 ThreadClock::get(unsigned tid) const { + DCHECK_LT(tid, kMaxTidInClock); + return clk_[tid]; +} + +ALWAYS_INLINE void ThreadClock::set(u64 v) { + DCHECK_GE(v, clk_[tid_]); + clk_[tid_] = v; +} + +ALWAYS_INLINE void ThreadClock::tick() { + clk_[tid_]++; +} + +ALWAYS_INLINE uptr ThreadClock::size() const { + return nclk_; +} + +ALWAYS_INLINE SyncClock::Iter SyncClock::begin() { + return Iter(this); +} + +ALWAYS_INLINE SyncClock::Iter SyncClock::end() { + return Iter(nullptr); +} + +ALWAYS_INLINE uptr SyncClock::size() const { + return size_; +} + +ALWAYS_INLINE SyncClock::Iter::Iter(SyncClock* parent) + : parent_(parent) + , pos_(nullptr) + , end_(nullptr) + , block_(-1) { + if (parent) + Next(); +} + +ALWAYS_INLINE SyncClock::Iter& SyncClock::Iter::operator++() { + pos_++; + if (UNLIKELY(pos_ >= end_)) + Next(); + return *this; +} + +ALWAYS_INLINE bool SyncClock::Iter::operator!=(const SyncClock::Iter& other) { + return parent_ != other.parent_; +} + +ALWAYS_INLINE ClockElem &SyncClock::Iter::operator*() { + return *pos_; +} +} // namespace __tsan + +#endif // TSAN_CLOCK_H |