216 lines · c
1//===-- tsan_trace.h --------------------------------------------*- C++ -*-===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This file is a part of ThreadSanitizer (TSan), a race detector.10//11//===----------------------------------------------------------------------===//12#ifndef TSAN_TRACE_H13#define TSAN_TRACE_H14 15#include "tsan_defs.h"16#include "tsan_ilist.h"17#include "tsan_mutexset.h"18#include "tsan_stack_trace.h"19 20namespace __tsan {21 22enum class EventType : u64 {23 kAccessExt,24 kAccessRange,25 kLock,26 kRLock,27 kUnlock,28 kTime,29};30 31// "Base" type for all events for type dispatch.32struct Event {33 // We use variable-length type encoding to give more bits to some event34 // types that need them. If is_access is set, this is EventAccess.35 // Otherwise, if is_func is set, this is EventFunc.36 // Otherwise type denotes the type.37 u64 is_access : 1;38 u64 is_func : 1;39 EventType type : 3;40 u64 _ : 59;41};42static_assert(sizeof(Event) == 8, "bad Event size");43 44// Nop event used as padding and does not affect state during replay.45static constexpr Event NopEvent = {1, 0, EventType::kAccessExt, 0};46 47// Compressed memory access can represent only some events with PCs48// close enough to each other. Otherwise we fall back to EventAccessExt.49struct EventAccess {50 static constexpr uptr kPCBits = 15;51 static_assert(kPCBits + kCompressedAddrBits + 5 == 64,52 "unused bits in EventAccess");53 54 u64 is_access : 1; // = 155 u64 is_read : 1;56 u64 is_atomic : 1;57 u64 size_log : 2;58 u64 pc_delta : kPCBits; // signed delta from the previous memory access PC59 u64 addr : kCompressedAddrBits;60};61static_assert(sizeof(EventAccess) == 8, "bad EventAccess size");62 63// Function entry (pc != 0) or exit (pc == 0).64struct EventFunc {65 u64 is_access : 1; // = 066 u64 is_func : 1; // = 167 u64 pc : 62;68};69static_assert(sizeof(EventFunc) == 8, "bad EventFunc size");70 71// Extended memory access with full PC.72struct EventAccessExt {73 // Note: precisely specifying the unused parts of the bitfield is critical for74 // performance. If we don't specify them, compiler will generate code to load75 // the old value and shuffle it to extract the unused bits to apply to the new76 // value. If we specify the unused part and store 0 in there, all that77 // unnecessary code goes away (store of the 0 const is combined with other78 // constant parts).79 static constexpr uptr kUnusedBits = 11;80 static_assert(kCompressedAddrBits + kUnusedBits + 9 == 64,81 "unused bits in EventAccessExt");82 83 u64 is_access : 1; // = 084 u64 is_func : 1; // = 085 EventType type : 3; // = EventType::kAccessExt86 u64 is_read : 1;87 u64 is_atomic : 1;88 u64 size_log : 2;89 u64 _ : kUnusedBits;90 u64 addr : kCompressedAddrBits;91 u64 pc;92};93static_assert(sizeof(EventAccessExt) == 16, "bad EventAccessExt size");94 95// Access to a memory range.96struct EventAccessRange {97 static constexpr uptr kSizeLoBits = 13;98 static_assert(kCompressedAddrBits + kSizeLoBits + 7 == 64,99 "unused bits in EventAccessRange");100 101 u64 is_access : 1; // = 0102 u64 is_func : 1; // = 0103 EventType type : 3; // = EventType::kAccessRange104 u64 is_read : 1;105 u64 is_free : 1;106 u64 size_lo : kSizeLoBits;107 u64 pc : kCompressedAddrBits;108 u64 addr : kCompressedAddrBits;109 u64 size_hi : 64 - kCompressedAddrBits;110};111static_assert(sizeof(EventAccessRange) == 16, "bad EventAccessRange size");112 113// Mutex lock.114struct EventLock {115 static constexpr uptr kStackIDLoBits = 15;116 static constexpr uptr kStackIDHiBits =117 sizeof(StackID) * kByteBits - kStackIDLoBits;118 static constexpr uptr kUnusedBits = 3;119 static_assert(kCompressedAddrBits + kStackIDLoBits + 5 == 64,120 "unused bits in EventLock");121 static_assert(kCompressedAddrBits + kStackIDHiBits + kUnusedBits == 64,122 "unused bits in EventLock");123 124 u64 is_access : 1; // = 0125 u64 is_func : 1; // = 0126 EventType type : 3; // = EventType::kLock or EventType::kRLock127 u64 pc : kCompressedAddrBits;128 u64 stack_lo : kStackIDLoBits;129 u64 stack_hi : sizeof(StackID) * kByteBits - kStackIDLoBits;130 u64 _ : kUnusedBits;131 u64 addr : kCompressedAddrBits;132};133static_assert(sizeof(EventLock) == 16, "bad EventLock size");134 135// Mutex unlock.136struct EventUnlock {137 static constexpr uptr kUnusedBits = 15;138 static_assert(kCompressedAddrBits + kUnusedBits + 5 == 64,139 "unused bits in EventUnlock");140 141 u64 is_access : 1; // = 0142 u64 is_func : 1; // = 0143 EventType type : 3; // = EventType::kUnlock144 u64 _ : kUnusedBits;145 u64 addr : kCompressedAddrBits;146};147static_assert(sizeof(EventUnlock) == 8, "bad EventUnlock size");148 149// Time change event.150struct EventTime {151 static constexpr uptr kUnusedBits = 37;152 static_assert(kUnusedBits + sizeof(Sid) * kByteBits + kEpochBits + 5 == 64,153 "unused bits in EventTime");154 155 u64 is_access : 1; // = 0156 u64 is_func : 1; // = 0157 EventType type : 3; // = EventType::kTime158 u64 sid : sizeof(Sid) * kByteBits;159 u64 epoch : kEpochBits;160 u64 _ : kUnusedBits;161};162static_assert(sizeof(EventTime) == 8, "bad EventTime size");163 164struct Trace;165 166struct TraceHeader {167 Trace* trace = nullptr; // back-pointer to Trace containing this part168 INode trace_parts; // in Trace::parts169 INode global; // in Contex::trace_part_recycle170};171 172struct TracePart : TraceHeader {173 // There are a lot of goroutines in Go, so we use smaller parts.174 static constexpr uptr kByteSize = (SANITIZER_GO ? 128 : 256) << 10;175 static constexpr uptr kSize =176 (kByteSize - sizeof(TraceHeader)) / sizeof(Event);177 // TraceAcquire does a fast event pointer overflow check by comparing178 // pointer into TracePart::events with kAlignment mask. Since TracePart's179 // are allocated page-aligned, this check detects end of the array180 // (it also have false positives in the middle that are filtered separately).181 // This also requires events to be the last field.182 static constexpr uptr kAlignment = 0xff0;183 Event events[kSize];184 185 TracePart() {}186};187static_assert(sizeof(TracePart) == TracePart::kByteSize, "bad TracePart size");188 189struct Trace {190 Mutex mtx;191 IList<TraceHeader, &TraceHeader::trace_parts, TracePart> parts;192 // First node non-queued into ctx->trace_part_recycle.193 TracePart* local_head;194 // Final position in the last part for finished threads.195 Event* final_pos = nullptr;196 // Number of trace parts allocated on behalf of this trace specifically.197 // Total number of parts in this trace can be larger if we retake some198 // parts from other traces.199 uptr parts_allocated = 0;200 201 Trace() : mtx(MutexTypeTrace) {}202 203 // We need at least 3 parts per thread, because we want to keep at last204 // 2 parts per thread that are not queued into ctx->trace_part_recycle205 // (the current one being filled and one full part that ensures that206 // we always have at least one part worth of previous memory accesses).207 static constexpr uptr kMinParts = 3;208 209 static constexpr uptr kFinishedThreadLo = 16;210 static constexpr uptr kFinishedThreadHi = 64;211};212 213} // namespace __tsan214 215#endif // TSAN_TRACE_H216