1 //===-- tsan_rtl.h ----------------------------------------------*- C++ -*-===//
3 // This file is distributed under the University of Illinois Open Source
4 // License. See LICENSE.TXT for details.
6 //===----------------------------------------------------------------------===//
8 // This file is a part of ThreadSanitizer (TSan), a race detector.
10 // Main internal TSan header file.
13 // - C++ run-time should not be used (static CTORs, RTTI, exceptions, static
14 // function-scope locals)
15 // - All functions/classes/etc reside in namespace __tsan, except for those
16 // declared in tsan_interface.h.
17 // - Platform-specific files should be used instead of ifdefs (*).
18 // - No system headers included in header files (*).
19 // - Platform specific headres included only into platform-specific files (*).
21 // (*) Except when inlining is critical for performance.
22 //===----------------------------------------------------------------------===//
27 #include "sanitizer_common/sanitizer_common.h"
28 #include "sanitizer_common/sanitizer_allocator.h"
29 #include "tsan_clock.h"
30 #include "tsan_defs.h"
31 #include "tsan_flags.h"
32 #include "tsan_sync.h"
33 #include "tsan_trace.h"
34 #include "tsan_vector.h"
35 #include "tsan_report.h"
36 #include "tsan_platform.h"
37 #include "tsan_mutexset.h"
39 #if SANITIZER_WORDSIZE != 64
40 # error "ThreadSanitizer is supported only on 64-bit platforms"
45 // Descriptor of user's memory block.
54 : mtx(MutexTypeMBlock
, StatMtxMBlock
) {
59 #if defined(TSAN_COMPAT_SHADOW) && TSAN_COMPAT_SHADOW
60 const uptr kAllocatorSpace
= 0x7d0000000000ULL
;
62 const uptr kAllocatorSpace
= 0x7d0000000000ULL
;
64 const uptr kAllocatorSize
= 0x10000000000ULL
; // 1T.
66 struct TsanMapUnmapCallback
{
67 void OnMap(uptr p
, uptr size
) const { }
68 void OnUnmap(uptr p
, uptr size
) const {
69 // We are about to unmap a chunk of user memory.
70 // Mark the corresponding shadow memory as not needed.
71 uptr shadow_beg
= MemToShadow(p
);
72 uptr shadow_end
= MemToShadow(p
+ size
);
73 CHECK(IsAligned(shadow_end
|shadow_beg
, GetPageSizeCached()));
74 FlushUnneededShadowMemory(shadow_beg
, shadow_end
- shadow_beg
);
78 typedef SizeClassAllocator64
<kAllocatorSpace
, kAllocatorSize
, sizeof(MBlock
),
79 DefaultSizeClassMap
> PrimaryAllocator
;
80 typedef SizeClassAllocatorLocalCache
<PrimaryAllocator
> AllocatorCache
;
81 typedef LargeMmapAllocator
<TsanMapUnmapCallback
> SecondaryAllocator
;
82 typedef CombinedAllocator
<PrimaryAllocator
, AllocatorCache
,
83 SecondaryAllocator
> Allocator
;
84 Allocator
*allocator();
87 void TsanCheckFailed(const char *file
, int line
, const char *cond
,
90 // FastState (from most significant bit):
98 FastState(u64 tid
, u64 epoch
) {
99 x_
= tid
<< kTidShift
;
100 x_
|= epoch
<< kClkShift
;
101 DCHECK_EQ(tid
, this->tid());
102 DCHECK_EQ(epoch
, this->epoch());
103 DCHECK_EQ(GetIgnoreBit(), false);
106 explicit FastState(u64 x
)
115 u64 res
= (x_
& ~kIgnoreBit
) >> kTidShift
;
119 u64
TidWithIgnore() const {
120 u64 res
= x_
>> kTidShift
;
125 u64 res
= (x_
<< (kTidBits
+ 1)) >> (64 - kClkBits
);
129 void IncrementEpoch() {
130 u64 old_epoch
= epoch();
131 x_
+= 1 << kClkShift
;
132 DCHECK_EQ(old_epoch
+ 1, epoch());
136 void SetIgnoreBit() { x_
|= kIgnoreBit
; }
137 void ClearIgnoreBit() { x_
&= ~kIgnoreBit
; }
138 bool GetIgnoreBit() const { return (s64
)x_
< 0; }
140 void SetHistorySize(int hs
) {
146 int GetHistorySize() const {
147 return (int)(x_
& 7);
150 void ClearHistorySize() {
154 u64
GetTracePos() const {
155 const int hs
= GetHistorySize();
156 // When hs == 0, the trace consists of 2 parts.
157 const u64 mask
= (1ull << (kTracePartSizeBits
+ hs
+ 1)) - 1;
158 return epoch() & mask
;
163 static const int kTidShift
= 64 - kTidBits
- 1;
164 static const int kClkShift
= kTidShift
- kClkBits
;
165 static const u64 kIgnoreBit
= 1ull << 63;
166 static const u64 kFreedBit
= 1ull << 63;
170 // Shadow (from most significant bit):
178 class Shadow
: public FastState
{
180 explicit Shadow(u64 x
)
184 explicit Shadow(const FastState
&s
)
189 void SetAddr0AndSizeLog(u64 addr0
, unsigned kAccessSizeLog
) {
190 DCHECK_EQ(x_
& 31, 0);
192 DCHECK_LE(kAccessSizeLog
, 3);
193 x_
|= (kAccessSizeLog
<< 3) | addr0
;
194 DCHECK_EQ(kAccessSizeLog
, size_log());
195 DCHECK_EQ(addr0
, this->addr0());
198 void SetWrite(unsigned kAccessIsWrite
) {
199 DCHECK_EQ(x_
& kReadBit
, 0);
202 DCHECK_EQ(kAccessIsWrite
, IsWrite());
205 void SetAtomic(bool kIsAtomic
) {
209 DCHECK_EQ(IsAtomic(), kIsAtomic
);
212 bool IsAtomic() const {
213 return x_
& kAtomicBit
;
216 bool IsZero() const {
220 static inline bool TidsAreEqual(const Shadow s1
, const Shadow s2
) {
221 u64 shifted_xor
= (s1
.x_
^ s2
.x_
) >> kTidShift
;
222 DCHECK_EQ(shifted_xor
== 0, s1
.TidWithIgnore() == s2
.TidWithIgnore());
223 return shifted_xor
== 0;
226 static inline bool Addr0AndSizeAreEqual(const Shadow s1
, const Shadow s2
) {
227 u64 masked_xor
= (s1
.x_
^ s2
.x_
) & 31;
228 return masked_xor
== 0;
231 static inline bool TwoRangesIntersect(Shadow s1
, Shadow s2
,
232 unsigned kS2AccessSize
) {
234 u64 diff
= s1
.addr0() - s2
.addr0();
235 if ((s64
)diff
< 0) { // s1.addr0 < s2.addr0 // NOLINT
236 // if (s1.addr0() + size1) > s2.addr0()) return true;
237 if (s1
.size() > -diff
) res
= true;
239 // if (s2.addr0() + kS2AccessSize > s1.addr0()) return true;
240 if (kS2AccessSize
> diff
) res
= true;
242 DCHECK_EQ(res
, TwoRangesIntersectSLOW(s1
, s2
));
243 DCHECK_EQ(res
, TwoRangesIntersectSLOW(s2
, s1
));
247 // The idea behind the offset is as follows.
248 // Consider that we have 8 bool's contained within a single 8-byte block
249 // (mapped to a single shadow "cell"). Now consider that we write to the bools
250 // from a single thread (which we consider the common case).
251 // W/o offsetting each access will have to scan 4 shadow values at average
252 // to find the corresponding shadow value for the bool.
253 // With offsetting we start scanning shadow with the offset so that
254 // each access hits necessary shadow straight off (at least in an expected
256 // This logic works seamlessly for any layout of user data. For example,
257 // if user data is {int, short, char, char}, then accesses to the int are
258 // offsetted to 0, short - 4, 1st char - 6, 2nd char - 7. Hopefully, accesses
259 // from a single thread won't need to scan all 8 shadow values.
260 unsigned ComputeSearchOffset() {
263 u64
addr0() const { return x_
& 7; }
264 u64
size() const { return 1ull << size_log(); }
265 bool IsWrite() const { return !IsRead(); }
266 bool IsRead() const { return x_
& kReadBit
; }
268 // The idea behind the freed bit is as follows.
269 // When the memory is freed (or otherwise unaccessible) we write to the shadow
270 // values with tid/epoch related to the free and the freed bit set.
271 // During memory accesses processing the freed bit is considered
272 // as msb of tid. So any access races with shadow with freed bit set
273 // (it is as if write from a thread with which we never synchronized before).
274 // This allows us to detect accesses to freed memory w/o additional
275 // overheads in memory access processing and at the same time restore
276 // tid/epoch of free.
281 bool IsFreed() const {
282 return x_
& kFreedBit
;
285 bool GetFreedAndReset() {
286 bool res
= x_
& kFreedBit
;
291 bool IsBothReadsOrAtomic(bool kIsWrite
, bool kIsAtomic
) const {
292 // analyzes 5-th bit (is_read) and 6-th bit (is_atomic)
293 bool v
= x_
& u64(((kIsWrite
^ 1) << kReadShift
)
294 | (kIsAtomic
<< kAtomicShift
));
295 DCHECK_EQ(v
, (!IsWrite() && !kIsWrite
) || (IsAtomic() && kIsAtomic
));
299 bool IsRWNotWeaker(bool kIsWrite
, bool kIsAtomic
) const {
300 bool v
= ((x_
>> kReadShift
) & 3)
301 <= u64((kIsWrite
^ 1) | (kIsAtomic
<< 1));
302 DCHECK_EQ(v
, (IsAtomic() < kIsAtomic
) ||
303 (IsAtomic() == kIsAtomic
&& !IsWrite() <= !kIsWrite
));
307 bool IsRWWeakerOrEqual(bool kIsWrite
, bool kIsAtomic
) const {
308 bool v
= ((x_
>> kReadShift
) & 3)
309 >= u64((kIsWrite
^ 1) | (kIsAtomic
<< 1));
310 DCHECK_EQ(v
, (IsAtomic() > kIsAtomic
) ||
311 (IsAtomic() == kIsAtomic
&& !IsWrite() >= !kIsWrite
));
316 static const u64 kReadShift
= 5;
317 static const u64 kReadBit
= 1ull << kReadShift
;
318 static const u64 kAtomicShift
= 6;
319 static const u64 kAtomicBit
= 1ull << kAtomicShift
;
321 u64
size_log() const { return (x_
>> 3) & 3; }
323 static bool TwoRangesIntersectSLOW(const Shadow s1
, const Shadow s2
) {
324 if (s1
.addr0() == s2
.addr0()) return true;
325 if (s1
.addr0() < s2
.addr0() && s1
.addr0() + s1
.size() > s2
.addr0())
327 if (s2
.addr0() < s1
.addr0() && s2
.addr0() + s2
.size() > s1
.addr0())
333 struct SignalContext
;
335 // This struct is stored in TLS.
337 FastState fast_state
;
338 // Synch epoch represents the threads's epoch before the last synchronization
339 // action. It allows to reduce number of shadow state updates.
340 // For example, fast_synch_epoch=100, last write to addr X was at epoch=150,
341 // if we are processing write to X from the same thread at epoch=200,
342 // we do nothing, because both writes happen in the same 'synch epoch'.
343 // That is, if another memory access does not race with the former write,
344 // it does not race with the latter as well.
345 // QUESTION: can we can squeeze this into ThreadState::Fast?
346 // E.g. ThreadState::Fast is a 44-bit, 32 are taken by synch_epoch and 12 are
347 // taken by epoch between synchs.
348 // This way we can save one load from tls.
349 u64 fast_synch_epoch
;
350 // This is a slow path flag. On fast path, fast_state.GetIgnoreBit() is read.
351 // We do not distinguish beteween ignoring reads and writes
352 // for better performance.
353 int ignore_reads_and_writes
;
354 uptr
*shadow_stack_pos
;
355 u64
*racy_shadow_addr
;
359 // C/C++ uses embed shadow stack of fixed size.
360 uptr shadow_stack
[kShadowStackSize
];
362 // Go uses satellite shadow stack with dynamic size.
364 uptr
*shadow_stack_end
;
369 AllocatorCache alloc_cache
;
383 DeadlockDetector deadlock_detector
;
385 bool in_signal_handler
;
386 SignalContext
*signal_ctx
;
389 u32 last_sleep_stack_id
;
390 ThreadClock last_sleep_clock
;
393 // Set in regions of runtime that must be signal-safe and fork-safe.
394 // If set, malloc must not be called.
397 explicit ThreadState(Context
*ctx
, int tid
, int unique_id
, u64 epoch
,
398 uptr stk_addr
, uptr stk_size
,
399 uptr tls_addr
, uptr tls_size
);
405 extern THREADLOCAL
char cur_thread_placeholder
[];
406 INLINE ThreadState
*cur_thread() {
407 return reinterpret_cast<ThreadState
*>(&cur_thread_placeholder
);
412 ThreadStatusInvalid
, // Non-existent thread, data is invalid.
413 ThreadStatusCreated
, // Created but not yet running.
414 ThreadStatusRunning
, // The thread is currently running.
415 ThreadStatusFinished
, // Joinable thread is finished but not yet joined.
416 ThreadStatusDead
// Joined, but some info (trace) is still alive.
419 // An info about a thread that is hold for some time after its termination.
420 struct ThreadDeadInfo
{
424 struct ThreadContext
{
426 int unique_id
; // Non-rolling thread id.
428 uptr user_id
; // Some opaque user thread id (e.g. pthread_t).
434 // Epoch at which the thread had started.
435 // If we see an event from the thread stamped by an older epoch,
436 // the event is from a dead thread that shared tid with this thread.
439 StackTrace creation_stack
;
441 ThreadDeadInfo
*dead_info
;
442 ThreadContext
*dead_next
; // In dead thread list.
443 char *name
; // As annotated by user.
445 explicit ThreadContext(int tid
);
450 bool operator==(const RacyStacks
&other
) const {
451 if (hash
[0] == other
.hash
[0] && hash
[1] == other
.hash
[1])
453 if (hash
[0] == other
.hash
[1] && hash
[1] == other
.hash
[0])
464 struct FiredSuppression
{
478 int nmissed_expected
;
482 unsigned unique_thread_seq
;
484 int max_alive_threads
;
485 ThreadContext
*threads
[kMaxTid
];
487 ThreadContext
* dead_list_head
;
488 ThreadContext
* dead_list_tail
;
490 Vector
<RacyStacks
> racy_stacks
;
491 Vector
<RacyAddress
> racy_addresses
;
492 Vector
<FiredSuppression
> fired_suppressions
;
497 u64 int_alloc_cnt
[MBlockTypeCount
];
498 u64 int_alloc_siz
[MBlockTypeCount
];
513 explicit ScopedReport(ReportType typ
);
516 void AddStack(const StackTrace
*stack
);
517 void AddMemoryAccess(uptr addr
, Shadow s
, const StackTrace
*stack
,
518 const MutexSet
*mset
);
519 void AddThread(const ThreadContext
*tctx
);
520 void AddMutex(const SyncVar
*s
);
521 void AddLocation(uptr addr
, uptr size
);
522 void AddSleep(u32 stack_id
);
524 const ReportDesc
*GetReport() const;
530 void AddMutex(u64 id
);
532 ScopedReport(const ScopedReport
&);
533 void operator = (const ScopedReport
&);
536 void RestoreStack(int tid
, const u64 epoch
, StackTrace
*stk
, MutexSet
*mset
);
538 void StatAggregate(u64
*dst
, u64
*src
);
539 void StatOutput(u64
*stat
);
540 void ALWAYS_INLINE INLINE
StatInc(ThreadState
*thr
, StatType typ
, u64 n
= 1) {
545 void MapShadow(uptr addr
, uptr size
);
546 void MapThreadTrace(uptr addr
, uptr size
);
547 void InitializeShadowMemory();
548 void InitializeInterceptors();
549 void InitializeDynamicAnnotations();
551 void ReportRace(ThreadState
*thr
);
552 bool OutputReport(Context
*ctx
,
553 const ScopedReport
&srep
,
554 const ReportStack
*suppress_stack1
= 0,
555 const ReportStack
*suppress_stack2
= 0);
556 bool IsFiredSuppression(Context
*ctx
,
557 const ScopedReport
&srep
,
558 const StackTrace
&trace
);
559 bool IsExpectedReport(uptr addr
, uptr size
);
560 bool FrameIsInternal(const ReportStack
*frame
);
561 ReportStack
*SkipTsanInternalFrames(ReportStack
*ent
);
563 #if defined(TSAN_DEBUG_OUTPUT) && TSAN_DEBUG_OUTPUT >= 1
564 # define DPrintf Printf
566 # define DPrintf(...)
569 #if defined(TSAN_DEBUG_OUTPUT) && TSAN_DEBUG_OUTPUT >= 2
570 # define DPrintf2 Printf
572 # define DPrintf2(...)
575 u32
CurrentStackId(ThreadState
*thr
, uptr pc
);
576 void PrintCurrentStack(ThreadState
*thr
, uptr pc
);
577 void PrintCurrentStackSlow(); // uses libunwind
579 void Initialize(ThreadState
*thr
);
580 int Finalize(ThreadState
*thr
);
582 SyncVar
* GetJavaSync(ThreadState
*thr
, uptr pc
, uptr addr
,
583 bool write_lock
, bool create
);
584 SyncVar
* GetAndRemoveJavaSync(ThreadState
*thr
, uptr pc
, uptr addr
);
586 void MemoryAccess(ThreadState
*thr
, uptr pc
, uptr addr
,
587 int kAccessSizeLog
, bool kAccessIsWrite
, bool kIsAtomic
);
588 void MemoryAccessImpl(ThreadState
*thr
, uptr addr
,
589 int kAccessSizeLog
, bool kAccessIsWrite
, bool kIsAtomic
,
590 u64
*shadow_mem
, Shadow cur
);
591 void MemoryAccessRange(ThreadState
*thr
, uptr pc
, uptr addr
,
592 uptr size
, bool is_write
);
593 void MemoryAccessRangeStep(ThreadState
*thr
, uptr pc
, uptr addr
,
594 uptr size
, uptr step
, bool is_write
);
596 const int kSizeLog1
= 0;
597 const int kSizeLog2
= 1;
598 const int kSizeLog4
= 2;
599 const int kSizeLog8
= 3;
601 void ALWAYS_INLINE INLINE
MemoryRead(ThreadState
*thr
, uptr pc
,
602 uptr addr
, int kAccessSizeLog
) {
603 MemoryAccess(thr
, pc
, addr
, kAccessSizeLog
, false, false);
606 void ALWAYS_INLINE INLINE
MemoryWrite(ThreadState
*thr
, uptr pc
,
607 uptr addr
, int kAccessSizeLog
) {
608 MemoryAccess(thr
, pc
, addr
, kAccessSizeLog
, true, false);
611 void ALWAYS_INLINE INLINE
MemoryReadAtomic(ThreadState
*thr
, uptr pc
,
612 uptr addr
, int kAccessSizeLog
) {
613 MemoryAccess(thr
, pc
, addr
, kAccessSizeLog
, false, true);
616 void ALWAYS_INLINE INLINE
MemoryWriteAtomic(ThreadState
*thr
, uptr pc
,
617 uptr addr
, int kAccessSizeLog
) {
618 MemoryAccess(thr
, pc
, addr
, kAccessSizeLog
, true, true);
621 void MemoryResetRange(ThreadState
*thr
, uptr pc
, uptr addr
, uptr size
);
622 void MemoryRangeFreed(ThreadState
*thr
, uptr pc
, uptr addr
, uptr size
);
623 void MemoryRangeImitateWrite(ThreadState
*thr
, uptr pc
, uptr addr
, uptr size
);
624 void IgnoreCtl(ThreadState
*thr
, bool write
, bool begin
);
626 void FuncEntry(ThreadState
*thr
, uptr pc
);
627 void FuncExit(ThreadState
*thr
);
629 int ThreadCreate(ThreadState
*thr
, uptr pc
, uptr uid
, bool detached
);
630 void ThreadStart(ThreadState
*thr
, int tid
, uptr os_id
);
631 void ThreadFinish(ThreadState
*thr
);
632 int ThreadTid(ThreadState
*thr
, uptr pc
, uptr uid
);
633 void ThreadJoin(ThreadState
*thr
, uptr pc
, int tid
);
634 void ThreadDetach(ThreadState
*thr
, uptr pc
, int tid
);
635 void ThreadFinalize(ThreadState
*thr
);
636 void ThreadSetName(ThreadState
*thr
, const char *name
);
637 int ThreadCount(ThreadState
*thr
);
638 void ProcessPendingSignals(ThreadState
*thr
);
640 void MutexCreate(ThreadState
*thr
, uptr pc
, uptr addr
,
641 bool rw
, bool recursive
, bool linker_init
);
642 void MutexDestroy(ThreadState
*thr
, uptr pc
, uptr addr
);
643 void MutexLock(ThreadState
*thr
, uptr pc
, uptr addr
);
644 void MutexUnlock(ThreadState
*thr
, uptr pc
, uptr addr
);
645 void MutexReadLock(ThreadState
*thr
, uptr pc
, uptr addr
);
646 void MutexReadUnlock(ThreadState
*thr
, uptr pc
, uptr addr
);
647 void MutexReadOrWriteUnlock(ThreadState
*thr
, uptr pc
, uptr addr
);
649 void Acquire(ThreadState
*thr
, uptr pc
, uptr addr
);
650 void AcquireGlobal(ThreadState
*thr
, uptr pc
);
651 void Release(ThreadState
*thr
, uptr pc
, uptr addr
);
652 void ReleaseStore(ThreadState
*thr
, uptr pc
, uptr addr
);
653 void AfterSleep(ThreadState
*thr
, uptr pc
);
655 // The hacky call uses custom calling convention and an assembly thunk.
656 // It is considerably faster that a normal call for the caller
657 // if it is not executed (it is intended for slow paths from hot functions).
658 // The trick is that the call preserves all registers and the compiler
659 // does not treat it as a call.
660 // If it does not work for you, use normal call.
662 // The caller may not create the stack frame for itself at all,
663 // so we create a reserve stack frame for it (1024b must be enough).
664 #define HACKY_CALL(f) \
665 __asm__ __volatile__("sub $1024, %%rsp;" \
666 "/*.cfi_adjust_cfa_offset 1024;*/" \
667 ".hidden " #f "_thunk;" \
668 "call " #f "_thunk;" \
669 "add $1024, %%rsp;" \
670 "/*.cfi_adjust_cfa_offset -1024;*/" \
673 #define HACKY_CALL(f) f()
676 void TraceSwitch(ThreadState
*thr
);
677 uptr
TraceTopPC(ThreadState
*thr
);
681 extern "C" void __tsan_trace_switch();
682 void ALWAYS_INLINE INLINE
TraceAddEvent(ThreadState
*thr
, FastState fs
,
683 EventType typ
, u64 addr
) {
684 DCHECK_GE((int)typ
, 0);
685 DCHECK_LE((int)typ
, 7);
686 DCHECK_EQ(GetLsb(addr
, 61), addr
);
687 StatInc(thr
, StatEvents
);
688 u64 pos
= fs
.GetTracePos();
689 if (UNLIKELY((pos
% kTracePartSize
) == 0)) {
691 HACKY_CALL(__tsan_trace_switch
);
696 Event
*trace
= (Event
*)GetThreadTrace(fs
.tid());
697 Event
*evp
= &trace
[pos
];
698 Event ev
= (u64
)addr
| ((u64
)typ
<< 61);
702 } // namespace __tsan