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-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file is a part of ThreadSanitizer (TSan), a race detector.
10//
11//===----------------------------------------------------------------------===//
12#ifndef TSAN_TRACE_H
13#define TSAN_TRACE_H
14
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 event
34 // 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 = {.is_access: 1, .is_func: 0, .type: EventType::kAccessExt, ._: 0};
46
47// Compressed memory access can represent only some events with PCs
48// 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; // = 1
55 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 PC
59 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; // = 0
66 u64 is_func : 1; // = 1
67 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 for
74 // performance. If we don't specify them, compiler will generate code to load
75 // the old value and shuffle it to extract the unused bits to apply to the new
76 // value. If we specify the unused part and store 0 in there, all that
77 // unnecessary code goes away (store of the 0 const is combined with other
78 // 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; // = 0
84 u64 is_func : 1; // = 0
85 EventType type : 3; // = EventType::kAccessExt
86 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; // = 0
102 u64 is_func : 1; // = 0
103 EventType type : 3; // = EventType::kAccessRange
104 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; // = 0
125 u64 is_func : 1; // = 0
126 EventType type : 3; // = EventType::kLock or EventType::kRLock
127 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; // = 0
142 u64 is_func : 1; // = 0
143 EventType type : 3; // = EventType::kUnlock
144 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; // = 0
156 u64 is_func : 1; // = 0
157 EventType type : 3; // = EventType::kTime
158 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 part
168 INode trace_parts; // in Trace::parts
169 INode global; // in Contex::trace_part_recycle
170};
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 comparing
178 // pointer into TracePart::events with kAlignment mask. Since TracePart's
179 // are allocated page-aligned, this check detects end of the array
180 // (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 some
198 // 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 last
204 // 2 parts per thread that are not queued into ctx->trace_part_recycle
205 // (the current one being filled and one full part that ensures that
206 // 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 __tsan
214
215#endif // TSAN_TRACE_H
216