1//===-- ThreadSanitizer.cpp - race detector -------------------------------===//
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, a race detector.
10//
11// The tool is under development, for the details about previous versions see
12// http://code.google.com/p/data-race-test
13//
14// The instrumentation phase is quite simple:
15// - Insert calls to run-time library before every memory access.
16// - Optimizations may apply to avoid instrumenting some of the accesses.
17// - Insert calls at function entry/exit.
18// The rest is handled by the run-time library.
19//===----------------------------------------------------------------------===//
20
21#include "llvm/Transforms/Instrumentation/ThreadSanitizer.h"
22#include "llvm/ADT/DenseMap.h"
23#include "llvm/ADT/SmallString.h"
24#include "llvm/ADT/SmallVector.h"
25#include "llvm/ADT/Statistic.h"
26#include "llvm/ADT/StringExtras.h"
27#include "llvm/Analysis/CaptureTracking.h"
28#include "llvm/Analysis/TargetLibraryInfo.h"
29#include "llvm/Analysis/ValueTracking.h"
30#include "llvm/IR/DataLayout.h"
31#include "llvm/IR/Function.h"
32#include "llvm/IR/IRBuilder.h"
33#include "llvm/IR/Instructions.h"
34#include "llvm/IR/IntrinsicInst.h"
35#include "llvm/IR/Intrinsics.h"
36#include "llvm/IR/LLVMContext.h"
37#include "llvm/IR/Metadata.h"
38#include "llvm/IR/Module.h"
39#include "llvm/IR/Type.h"
40#include "llvm/ProfileData/InstrProf.h"
41#include "llvm/Support/CommandLine.h"
42#include "llvm/Support/Debug.h"
43#include "llvm/Support/MathExtras.h"
44#include "llvm/Support/raw_ostream.h"
45#include "llvm/Transforms/Instrumentation.h"
46#include "llvm/Transforms/Utils/EscapeEnumerator.h"
47#include "llvm/Transforms/Utils/Local.h"
48#include "llvm/Transforms/Utils/ModuleUtils.h"
49
50using namespace llvm;
51
52#define DEBUG_TYPE "tsan"
53
54static cl::opt<bool> ClInstrumentMemoryAccesses(
55 "tsan-instrument-memory-accesses", cl::init(Val: true),
56 cl::desc("Instrument memory accesses"), cl::Hidden);
57static cl::opt<bool>
58 ClInstrumentFuncEntryExit("tsan-instrument-func-entry-exit", cl::init(Val: true),
59 cl::desc("Instrument function entry and exit"),
60 cl::Hidden);
61static cl::opt<bool> ClHandleCxxExceptions(
62 "tsan-handle-cxx-exceptions", cl::init(Val: true),
63 cl::desc("Handle C++ exceptions (insert cleanup blocks for unwinding)"),
64 cl::Hidden);
65static cl::opt<bool> ClInstrumentAtomics("tsan-instrument-atomics",
66 cl::init(Val: true),
67 cl::desc("Instrument atomics"),
68 cl::Hidden);
69static cl::opt<bool> ClInstrumentMemIntrinsics(
70 "tsan-instrument-memintrinsics", cl::init(Val: true),
71 cl::desc("Instrument memintrinsics (memset/memcpy/memmove)"), cl::Hidden);
72static cl::opt<bool> ClDistinguishVolatile(
73 "tsan-distinguish-volatile", cl::init(Val: false),
74 cl::desc("Emit special instrumentation for accesses to volatiles"),
75 cl::Hidden);
76static cl::opt<bool> ClInstrumentReadBeforeWrite(
77 "tsan-instrument-read-before-write", cl::init(Val: false),
78 cl::desc("Do not eliminate read instrumentation for read-before-writes"),
79 cl::Hidden);
80static cl::opt<bool> ClCompoundReadBeforeWrite(
81 "tsan-compound-read-before-write", cl::init(Val: false),
82 cl::desc("Emit special compound instrumentation for reads-before-writes"),
83 cl::Hidden);
84
85STATISTIC(NumInstrumentedReads, "Number of instrumented reads");
86STATISTIC(NumInstrumentedWrites, "Number of instrumented writes");
87STATISTIC(NumOmittedReadsBeforeWrite,
88 "Number of reads ignored due to following writes");
89STATISTIC(NumAccessesWithBadSize, "Number of accesses with bad size");
90STATISTIC(NumInstrumentedVtableWrites, "Number of vtable ptr writes");
91STATISTIC(NumInstrumentedVtableReads, "Number of vtable ptr reads");
92STATISTIC(NumOmittedReadsFromConstantGlobals,
93 "Number of reads from constant globals");
94STATISTIC(NumOmittedReadsFromVtable, "Number of vtable reads");
95STATISTIC(NumOmittedNonCaptured, "Number of accesses ignored due to capturing");
96
97const char kTsanModuleCtorName[] = "tsan.module_ctor";
98const char kTsanInitName[] = "__tsan_init";
99
100namespace {
101
102/// ThreadSanitizer: instrument the code in module to find races.
103///
104/// Instantiating ThreadSanitizer inserts the tsan runtime library API function
105/// declarations into the module if they don't exist already. Instantiating
106/// ensures the __tsan_init function is in the list of global constructors for
107/// the module.
108struct ThreadSanitizer {
109 ThreadSanitizer() {
110 // Check options and warn user.
111 if (ClInstrumentReadBeforeWrite && ClCompoundReadBeforeWrite) {
112 errs()
113 << "warning: Option -tsan-compound-read-before-write has no effect "
114 "when -tsan-instrument-read-before-write is set.\n";
115 }
116 }
117
118 bool sanitizeFunction(Function &F, const TargetLibraryInfo &TLI);
119
120private:
121 // Internal Instruction wrapper that contains more information about the
122 // Instruction from prior analysis.
123 struct InstructionInfo {
124 // Instrumentation emitted for this instruction is for a compounded set of
125 // read and write operations in the same basic block.
126 static constexpr unsigned kCompoundRW = (1U << 0);
127
128 explicit InstructionInfo(Instruction *Inst) : Inst(Inst) {}
129
130 Instruction *Inst;
131 unsigned Flags = 0;
132 };
133
134 void initialize(Module &M, const TargetLibraryInfo &TLI);
135 bool instrumentLoadOrStore(const InstructionInfo &II, const DataLayout &DL);
136 bool instrumentAtomic(Instruction *I, const DataLayout &DL);
137 bool instrumentMemIntrinsic(Instruction *I);
138 void chooseInstructionsToInstrument(SmallVectorImpl<Instruction *> &Local,
139 SmallVectorImpl<InstructionInfo> &All,
140 const DataLayout &DL);
141 bool addrPointsToConstantData(Value *Addr);
142 int getMemoryAccessFuncIndex(Type *OrigTy, Value *Addr, const DataLayout &DL);
143 void InsertRuntimeIgnores(Function &F);
144
145 Type *IntptrTy;
146 FunctionCallee TsanFuncEntry;
147 FunctionCallee TsanFuncExit;
148 FunctionCallee TsanIgnoreBegin;
149 FunctionCallee TsanIgnoreEnd;
150 // Accesses sizes are powers of two: 1, 2, 4, 8, 16.
151 static const size_t kNumberOfAccessSizes = 5;
152 FunctionCallee TsanRead[kNumberOfAccessSizes];
153 FunctionCallee TsanWrite[kNumberOfAccessSizes];
154 FunctionCallee TsanUnalignedRead[kNumberOfAccessSizes];
155 FunctionCallee TsanUnalignedWrite[kNumberOfAccessSizes];
156 FunctionCallee TsanVolatileRead[kNumberOfAccessSizes];
157 FunctionCallee TsanVolatileWrite[kNumberOfAccessSizes];
158 FunctionCallee TsanUnalignedVolatileRead[kNumberOfAccessSizes];
159 FunctionCallee TsanUnalignedVolatileWrite[kNumberOfAccessSizes];
160 FunctionCallee TsanCompoundRW[kNumberOfAccessSizes];
161 FunctionCallee TsanUnalignedCompoundRW[kNumberOfAccessSizes];
162 FunctionCallee TsanAtomicLoad[kNumberOfAccessSizes];
163 FunctionCallee TsanAtomicStore[kNumberOfAccessSizes];
164 FunctionCallee TsanAtomicRMW[AtomicRMWInst::LAST_BINOP + 1]
165 [kNumberOfAccessSizes];
166 FunctionCallee TsanAtomicCAS[kNumberOfAccessSizes];
167 FunctionCallee TsanAtomicThreadFence;
168 FunctionCallee TsanAtomicSignalFence;
169 FunctionCallee TsanVptrUpdate;
170 FunctionCallee TsanVptrLoad;
171 FunctionCallee MemmoveFn, MemcpyFn, MemsetFn;
172};
173
174void insertModuleCtor(Module &M) {
175 getOrCreateSanitizerCtorAndInitFunctions(
176 M, CtorName: kTsanModuleCtorName, InitName: kTsanInitName, /*InitArgTypes=*/{},
177 /*InitArgs=*/{},
178 // This callback is invoked when the functions are created the first
179 // time. Hook them into the global ctors list in that case:
180 FunctionsCreatedCallback: [&](Function *Ctor, FunctionCallee) { appendToGlobalCtors(M, F: Ctor, Priority: 0); });
181}
182} // namespace
183
184PreservedAnalyses ThreadSanitizerPass::run(Function &F,
185 FunctionAnalysisManager &FAM) {
186 ThreadSanitizer TSan;
187 if (TSan.sanitizeFunction(F, TLI: FAM.getResult<TargetLibraryAnalysis>(IR&: F)))
188 return PreservedAnalyses::none();
189 return PreservedAnalyses::all();
190}
191
192PreservedAnalyses ModuleThreadSanitizerPass::run(Module &M,
193 ModuleAnalysisManager &MAM) {
194 insertModuleCtor(M);
195 return PreservedAnalyses::none();
196}
197void ThreadSanitizer::initialize(Module &M, const TargetLibraryInfo &TLI) {
198 const DataLayout &DL = M.getDataLayout();
199 LLVMContext &Ctx = M.getContext();
200 IntptrTy = DL.getIntPtrType(C&: Ctx);
201
202 IRBuilder<> IRB(Ctx);
203 AttributeList Attr;
204 Attr = Attr.addFnAttribute(C&: Ctx, Kind: Attribute::NoUnwind);
205 // Initialize the callbacks.
206 TsanFuncEntry = M.getOrInsertFunction(Name: "__tsan_func_entry", AttributeList: Attr,
207 RetTy: IRB.getVoidTy(), Args: IRB.getPtrTy());
208 TsanFuncExit =
209 M.getOrInsertFunction(Name: "__tsan_func_exit", AttributeList: Attr, RetTy: IRB.getVoidTy());
210 TsanIgnoreBegin = M.getOrInsertFunction(Name: "__tsan_ignore_thread_begin", AttributeList: Attr,
211 RetTy: IRB.getVoidTy());
212 TsanIgnoreEnd =
213 M.getOrInsertFunction(Name: "__tsan_ignore_thread_end", AttributeList: Attr, RetTy: IRB.getVoidTy());
214 IntegerType *OrdTy = IRB.getInt32Ty();
215 for (size_t i = 0; i < kNumberOfAccessSizes; ++i) {
216 const unsigned ByteSize = 1U << i;
217 const unsigned BitSize = ByteSize * 8;
218 std::string ByteSizeStr = utostr(X: ByteSize);
219 std::string BitSizeStr = utostr(X: BitSize);
220 SmallString<32> ReadName("__tsan_read" + ByteSizeStr);
221 TsanRead[i] = M.getOrInsertFunction(Name: ReadName, AttributeList: Attr, RetTy: IRB.getVoidTy(),
222 Args: IRB.getPtrTy());
223
224 SmallString<32> WriteName("__tsan_write" + ByteSizeStr);
225 TsanWrite[i] = M.getOrInsertFunction(Name: WriteName, AttributeList: Attr, RetTy: IRB.getVoidTy(),
226 Args: IRB.getPtrTy());
227
228 SmallString<64> UnalignedReadName("__tsan_unaligned_read" + ByteSizeStr);
229 TsanUnalignedRead[i] = M.getOrInsertFunction(
230 Name: UnalignedReadName, AttributeList: Attr, RetTy: IRB.getVoidTy(), Args: IRB.getPtrTy());
231
232 SmallString<64> UnalignedWriteName("__tsan_unaligned_write" + ByteSizeStr);
233 TsanUnalignedWrite[i] = M.getOrInsertFunction(
234 Name: UnalignedWriteName, AttributeList: Attr, RetTy: IRB.getVoidTy(), Args: IRB.getPtrTy());
235
236 SmallString<64> VolatileReadName("__tsan_volatile_read" + ByteSizeStr);
237 TsanVolatileRead[i] = M.getOrInsertFunction(
238 Name: VolatileReadName, AttributeList: Attr, RetTy: IRB.getVoidTy(), Args: IRB.getPtrTy());
239
240 SmallString<64> VolatileWriteName("__tsan_volatile_write" + ByteSizeStr);
241 TsanVolatileWrite[i] = M.getOrInsertFunction(
242 Name: VolatileWriteName, AttributeList: Attr, RetTy: IRB.getVoidTy(), Args: IRB.getPtrTy());
243
244 SmallString<64> UnalignedVolatileReadName("__tsan_unaligned_volatile_read" +
245 ByteSizeStr);
246 TsanUnalignedVolatileRead[i] = M.getOrInsertFunction(
247 Name: UnalignedVolatileReadName, AttributeList: Attr, RetTy: IRB.getVoidTy(), Args: IRB.getPtrTy());
248
249 SmallString<64> UnalignedVolatileWriteName(
250 "__tsan_unaligned_volatile_write" + ByteSizeStr);
251 TsanUnalignedVolatileWrite[i] = M.getOrInsertFunction(
252 Name: UnalignedVolatileWriteName, AttributeList: Attr, RetTy: IRB.getVoidTy(), Args: IRB.getPtrTy());
253
254 SmallString<64> CompoundRWName("__tsan_read_write" + ByteSizeStr);
255 TsanCompoundRW[i] = M.getOrInsertFunction(
256 Name: CompoundRWName, AttributeList: Attr, RetTy: IRB.getVoidTy(), Args: IRB.getPtrTy());
257
258 SmallString<64> UnalignedCompoundRWName("__tsan_unaligned_read_write" +
259 ByteSizeStr);
260 TsanUnalignedCompoundRW[i] = M.getOrInsertFunction(
261 Name: UnalignedCompoundRWName, AttributeList: Attr, RetTy: IRB.getVoidTy(), Args: IRB.getPtrTy());
262
263 Type *Ty = Type::getIntNTy(C&: Ctx, N: BitSize);
264 Type *PtrTy = PointerType::get(C&: Ctx, AddressSpace: 0);
265 SmallString<32> AtomicLoadName("__tsan_atomic" + BitSizeStr + "_load");
266 TsanAtomicLoad[i] =
267 M.getOrInsertFunction(Name: AtomicLoadName,
268 AttributeList: TLI.getAttrList(C: &Ctx, ArgNos: {1}, /*Signed=*/true,
269 /*Ret=*/BitSize <= 32, AL: Attr),
270 RetTy: Ty, Args: PtrTy, Args: OrdTy);
271
272 // Args of type Ty need extension only when BitSize is 32 or less.
273 using Idxs = std::vector<unsigned>;
274 Idxs Idxs2Or12 ((BitSize <= 32) ? Idxs({1, 2}) : Idxs({2}));
275 Idxs Idxs34Or1234((BitSize <= 32) ? Idxs({1, 2, 3, 4}) : Idxs({3, 4}));
276 SmallString<32> AtomicStoreName("__tsan_atomic" + BitSizeStr + "_store");
277 TsanAtomicStore[i] = M.getOrInsertFunction(
278 Name: AtomicStoreName,
279 AttributeList: TLI.getAttrList(C: &Ctx, ArgNos: Idxs2Or12, /*Signed=*/true, /*Ret=*/false, AL: Attr),
280 RetTy: IRB.getVoidTy(), Args: PtrTy, Args: Ty, Args: OrdTy);
281
282 for (unsigned Op = AtomicRMWInst::FIRST_BINOP;
283 Op <= AtomicRMWInst::LAST_BINOP; ++Op) {
284 TsanAtomicRMW[Op][i] = nullptr;
285 const char *NamePart = nullptr;
286 if (Op == AtomicRMWInst::Xchg)
287 NamePart = "_exchange";
288 else if (Op == AtomicRMWInst::Add)
289 NamePart = "_fetch_add";
290 else if (Op == AtomicRMWInst::Sub)
291 NamePart = "_fetch_sub";
292 else if (Op == AtomicRMWInst::And)
293 NamePart = "_fetch_and";
294 else if (Op == AtomicRMWInst::Or)
295 NamePart = "_fetch_or";
296 else if (Op == AtomicRMWInst::Xor)
297 NamePart = "_fetch_xor";
298 else if (Op == AtomicRMWInst::Nand)
299 NamePart = "_fetch_nand";
300 else
301 continue;
302 SmallString<32> RMWName("__tsan_atomic" + itostr(X: BitSize) + NamePart);
303 TsanAtomicRMW[Op][i] = M.getOrInsertFunction(
304 Name: RMWName,
305 AttributeList: TLI.getAttrList(C: &Ctx, ArgNos: Idxs2Or12, /*Signed=*/true,
306 /*Ret=*/BitSize <= 32, AL: Attr),
307 RetTy: Ty, Args: PtrTy, Args: Ty, Args: OrdTy);
308 }
309
310 SmallString<32> AtomicCASName("__tsan_atomic" + BitSizeStr +
311 "_compare_exchange_val");
312 TsanAtomicCAS[i] = M.getOrInsertFunction(
313 Name: AtomicCASName,
314 AttributeList: TLI.getAttrList(C: &Ctx, ArgNos: Idxs34Or1234, /*Signed=*/true,
315 /*Ret=*/BitSize <= 32, AL: Attr),
316 RetTy: Ty, Args: PtrTy, Args: Ty, Args: Ty, Args: OrdTy, Args: OrdTy);
317 }
318 TsanVptrUpdate =
319 M.getOrInsertFunction(Name: "__tsan_vptr_update", AttributeList: Attr, RetTy: IRB.getVoidTy(),
320 Args: IRB.getPtrTy(), Args: IRB.getPtrTy());
321 TsanVptrLoad = M.getOrInsertFunction(Name: "__tsan_vptr_read", AttributeList: Attr,
322 RetTy: IRB.getVoidTy(), Args: IRB.getPtrTy());
323 TsanAtomicThreadFence = M.getOrInsertFunction(
324 Name: "__tsan_atomic_thread_fence",
325 AttributeList: TLI.getAttrList(C: &Ctx, ArgNos: {0}, /*Signed=*/true, /*Ret=*/false, AL: Attr),
326 RetTy: IRB.getVoidTy(), Args: OrdTy);
327
328 TsanAtomicSignalFence = M.getOrInsertFunction(
329 Name: "__tsan_atomic_signal_fence",
330 AttributeList: TLI.getAttrList(C: &Ctx, ArgNos: {0}, /*Signed=*/true, /*Ret=*/false, AL: Attr),
331 RetTy: IRB.getVoidTy(), Args: OrdTy);
332
333 MemmoveFn =
334 M.getOrInsertFunction(Name: "__tsan_memmove", AttributeList: Attr, RetTy: IRB.getPtrTy(),
335 Args: IRB.getPtrTy(), Args: IRB.getPtrTy(), Args: IntptrTy);
336 MemcpyFn =
337 M.getOrInsertFunction(Name: "__tsan_memcpy", AttributeList: Attr, RetTy: IRB.getPtrTy(),
338 Args: IRB.getPtrTy(), Args: IRB.getPtrTy(), Args: IntptrTy);
339 MemsetFn = M.getOrInsertFunction(
340 Name: "__tsan_memset",
341 AttributeList: TLI.getAttrList(C: &Ctx, ArgNos: {1}, /*Signed=*/true, /*Ret=*/false, AL: Attr),
342 RetTy: IRB.getPtrTy(), Args: IRB.getPtrTy(), Args: IRB.getInt32Ty(), Args: IntptrTy);
343}
344
345static bool isVtableAccess(Instruction *I) {
346 if (MDNode *Tag = I->getMetadata(KindID: LLVMContext::MD_tbaa))
347 return Tag->isTBAAVtableAccess();
348 return false;
349}
350
351// Do not instrument known races/"benign races" that come from compiler
352// instrumentatin. The user has no way of suppressing them.
353static bool shouldInstrumentReadWriteFromAddress(const Module *M, Value *Addr) {
354 // Peel off GEPs and BitCasts.
355 Addr = Addr->stripInBoundsOffsets();
356
357 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Val: Addr)) {
358 if (GV->hasSection()) {
359 StringRef SectionName = GV->getSection();
360 // Check if the global is in the PGO counters section.
361 auto OF = Triple(M->getTargetTriple()).getObjectFormat();
362 if (SectionName.ends_with(
363 Suffix: getInstrProfSectionName(IPSK: IPSK_cnts, OF, /*AddSegmentInfo=*/false)))
364 return false;
365 }
366 }
367
368 // Do not instrument accesses from different address spaces; we cannot deal
369 // with them.
370 if (Addr) {
371 Type *PtrTy = cast<PointerType>(Val: Addr->getType()->getScalarType());
372 if (PtrTy->getPointerAddressSpace() != 0)
373 return false;
374 }
375
376 return true;
377}
378
379bool ThreadSanitizer::addrPointsToConstantData(Value *Addr) {
380 // If this is a GEP, just analyze its pointer operand.
381 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Val: Addr))
382 Addr = GEP->getPointerOperand();
383
384 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Val: Addr)) {
385 if (GV->isConstant()) {
386 // Reads from constant globals can not race with any writes.
387 NumOmittedReadsFromConstantGlobals++;
388 return true;
389 }
390 } else if (LoadInst *L = dyn_cast<LoadInst>(Val: Addr)) {
391 if (isVtableAccess(I: L)) {
392 // Reads from a vtable pointer can not race with any writes.
393 NumOmittedReadsFromVtable++;
394 return true;
395 }
396 }
397 return false;
398}
399
400// Instrumenting some of the accesses may be proven redundant.
401// Currently handled:
402// - read-before-write (within same BB, no calls between)
403// - not captured variables
404//
405// We do not handle some of the patterns that should not survive
406// after the classic compiler optimizations.
407// E.g. two reads from the same temp should be eliminated by CSE,
408// two writes should be eliminated by DSE, etc.
409//
410// 'Local' is a vector of insns within the same BB (no calls between).
411// 'All' is a vector of insns that will be instrumented.
412void ThreadSanitizer::chooseInstructionsToInstrument(
413 SmallVectorImpl<Instruction *> &Local,
414 SmallVectorImpl<InstructionInfo> &All, const DataLayout &DL) {
415 DenseMap<Value *, size_t> WriteTargets; // Map of addresses to index in All
416 // Iterate from the end.
417 for (Instruction *I : reverse(C&: Local)) {
418 const bool IsWrite = isa<StoreInst>(Val: *I);
419 Value *Addr = IsWrite ? cast<StoreInst>(Val: I)->getPointerOperand()
420 : cast<LoadInst>(Val: I)->getPointerOperand();
421
422 if (!shouldInstrumentReadWriteFromAddress(M: I->getModule(), Addr))
423 continue;
424
425 if (!IsWrite) {
426 const auto WriteEntry = WriteTargets.find(Val: Addr);
427 if (!ClInstrumentReadBeforeWrite && WriteEntry != WriteTargets.end()) {
428 auto &WI = All[WriteEntry->second];
429 // If we distinguish volatile accesses and if either the read or write
430 // is volatile, do not omit any instrumentation.
431 const bool AnyVolatile =
432 ClDistinguishVolatile && (cast<LoadInst>(Val: I)->isVolatile() ||
433 cast<StoreInst>(Val: WI.Inst)->isVolatile());
434 if (!AnyVolatile) {
435 // We will write to this temp, so no reason to analyze the read.
436 // Mark the write instruction as compound.
437 WI.Flags |= InstructionInfo::kCompoundRW;
438 NumOmittedReadsBeforeWrite++;
439 continue;
440 }
441 }
442
443 if (addrPointsToConstantData(Addr)) {
444 // Addr points to some constant data -- it can not race with any writes.
445 continue;
446 }
447 }
448
449 if (isa<AllocaInst>(Val: getUnderlyingObject(V: Addr)) &&
450 !PointerMayBeCaptured(V: Addr, ReturnCaptures: true, StoreCaptures: true)) {
451 // The variable is addressable but not captured, so it cannot be
452 // referenced from a different thread and participate in a data race
453 // (see llvm/Analysis/CaptureTracking.h for details).
454 NumOmittedNonCaptured++;
455 continue;
456 }
457
458 // Instrument this instruction.
459 All.emplace_back(Args&: I);
460 if (IsWrite) {
461 // For read-before-write and compound instrumentation we only need one
462 // write target, and we can override any previous entry if it exists.
463 WriteTargets[Addr] = All.size() - 1;
464 }
465 }
466 Local.clear();
467}
468
469static bool isTsanAtomic(const Instruction *I) {
470 // TODO: Ask TTI whether synchronization scope is between threads.
471 auto SSID = getAtomicSyncScopeID(I);
472 if (!SSID)
473 return false;
474 if (isa<LoadInst>(Val: I) || isa<StoreInst>(Val: I))
475 return *SSID != SyncScope::SingleThread;
476 return true;
477}
478
479void ThreadSanitizer::InsertRuntimeIgnores(Function &F) {
480 InstrumentationIRBuilder IRB(F.getEntryBlock().getFirstNonPHI());
481 IRB.CreateCall(Callee: TsanIgnoreBegin);
482 EscapeEnumerator EE(F, "tsan_ignore_cleanup", ClHandleCxxExceptions);
483 while (IRBuilder<> *AtExit = EE.Next()) {
484 InstrumentationIRBuilder::ensureDebugInfo(IRB&: *AtExit, F);
485 AtExit->CreateCall(Callee: TsanIgnoreEnd);
486 }
487}
488
489bool ThreadSanitizer::sanitizeFunction(Function &F,
490 const TargetLibraryInfo &TLI) {
491 // This is required to prevent instrumenting call to __tsan_init from within
492 // the module constructor.
493 if (F.getName() == kTsanModuleCtorName)
494 return false;
495 // Naked functions can not have prologue/epilogue
496 // (__tsan_func_entry/__tsan_func_exit) generated, so don't instrument them at
497 // all.
498 if (F.hasFnAttribute(Kind: Attribute::Naked))
499 return false;
500
501 // __attribute__(disable_sanitizer_instrumentation) prevents all kinds of
502 // instrumentation.
503 if (F.hasFnAttribute(Kind: Attribute::DisableSanitizerInstrumentation))
504 return false;
505
506 initialize(M&: *F.getParent(), TLI);
507 SmallVector<InstructionInfo, 8> AllLoadsAndStores;
508 SmallVector<Instruction*, 8> LocalLoadsAndStores;
509 SmallVector<Instruction*, 8> AtomicAccesses;
510 SmallVector<Instruction*, 8> MemIntrinCalls;
511 bool Res = false;
512 bool HasCalls = false;
513 bool SanitizeFunction = F.hasFnAttribute(Kind: Attribute::SanitizeThread);
514 const DataLayout &DL = F.getDataLayout();
515
516 // Traverse all instructions, collect loads/stores/returns, check for calls.
517 for (auto &BB : F) {
518 for (auto &Inst : BB) {
519 // Skip instructions inserted by another instrumentation.
520 if (Inst.hasMetadata(KindID: LLVMContext::MD_nosanitize))
521 continue;
522 if (isTsanAtomic(I: &Inst))
523 AtomicAccesses.push_back(Elt: &Inst);
524 else if (isa<LoadInst>(Val: Inst) || isa<StoreInst>(Val: Inst))
525 LocalLoadsAndStores.push_back(Elt: &Inst);
526 else if ((isa<CallInst>(Val: Inst) && !isa<DbgInfoIntrinsic>(Val: Inst)) ||
527 isa<InvokeInst>(Val: Inst)) {
528 if (CallInst *CI = dyn_cast<CallInst>(Val: &Inst))
529 maybeMarkSanitizerLibraryCallNoBuiltin(CI, TLI: &TLI);
530 if (isa<MemIntrinsic>(Val: Inst))
531 MemIntrinCalls.push_back(Elt: &Inst);
532 HasCalls = true;
533 chooseInstructionsToInstrument(Local&: LocalLoadsAndStores, All&: AllLoadsAndStores,
534 DL);
535 }
536 }
537 chooseInstructionsToInstrument(Local&: LocalLoadsAndStores, All&: AllLoadsAndStores, DL);
538 }
539
540 // We have collected all loads and stores.
541 // FIXME: many of these accesses do not need to be checked for races
542 // (e.g. variables that do not escape, etc).
543
544 // Instrument memory accesses only if we want to report bugs in the function.
545 if (ClInstrumentMemoryAccesses && SanitizeFunction)
546 for (const auto &II : AllLoadsAndStores) {
547 Res |= instrumentLoadOrStore(II, DL);
548 }
549
550 // Instrument atomic memory accesses in any case (they can be used to
551 // implement synchronization).
552 if (ClInstrumentAtomics)
553 for (auto *Inst : AtomicAccesses) {
554 Res |= instrumentAtomic(I: Inst, DL);
555 }
556
557 if (ClInstrumentMemIntrinsics && SanitizeFunction)
558 for (auto *Inst : MemIntrinCalls) {
559 Res |= instrumentMemIntrinsic(I: Inst);
560 }
561
562 if (F.hasFnAttribute(Kind: "sanitize_thread_no_checking_at_run_time")) {
563 assert(!F.hasFnAttribute(Attribute::SanitizeThread));
564 if (HasCalls)
565 InsertRuntimeIgnores(F);
566 }
567
568 // Instrument function entry/exit points if there were instrumented accesses.
569 if ((Res || HasCalls) && ClInstrumentFuncEntryExit) {
570 InstrumentationIRBuilder IRB(F.getEntryBlock().getFirstNonPHI());
571 Value *ReturnAddress = IRB.CreateCall(
572 Callee: Intrinsic::getDeclaration(M: F.getParent(), id: Intrinsic::returnaddress),
573 Args: IRB.getInt32(C: 0));
574 IRB.CreateCall(Callee: TsanFuncEntry, Args: ReturnAddress);
575
576 EscapeEnumerator EE(F, "tsan_cleanup", ClHandleCxxExceptions);
577 while (IRBuilder<> *AtExit = EE.Next()) {
578 InstrumentationIRBuilder::ensureDebugInfo(IRB&: *AtExit, F);
579 AtExit->CreateCall(Callee: TsanFuncExit, Args: {});
580 }
581 Res = true;
582 }
583 return Res;
584}
585
586bool ThreadSanitizer::instrumentLoadOrStore(const InstructionInfo &II,
587 const DataLayout &DL) {
588 InstrumentationIRBuilder IRB(II.Inst);
589 const bool IsWrite = isa<StoreInst>(Val: *II.Inst);
590 Value *Addr = IsWrite ? cast<StoreInst>(Val: II.Inst)->getPointerOperand()
591 : cast<LoadInst>(Val: II.Inst)->getPointerOperand();
592 Type *OrigTy = getLoadStoreType(I: II.Inst);
593
594 // swifterror memory addresses are mem2reg promoted by instruction selection.
595 // As such they cannot have regular uses like an instrumentation function and
596 // it makes no sense to track them as memory.
597 if (Addr->isSwiftError())
598 return false;
599
600 int Idx = getMemoryAccessFuncIndex(OrigTy, Addr, DL);
601 if (Idx < 0)
602 return false;
603 if (IsWrite && isVtableAccess(I: II.Inst)) {
604 LLVM_DEBUG(dbgs() << " VPTR : " << *II.Inst << "\n");
605 Value *StoredValue = cast<StoreInst>(Val: II.Inst)->getValueOperand();
606 // StoredValue may be a vector type if we are storing several vptrs at once.
607 // In this case, just take the first element of the vector since this is
608 // enough to find vptr races.
609 if (isa<VectorType>(Val: StoredValue->getType()))
610 StoredValue = IRB.CreateExtractElement(
611 Vec: StoredValue, Idx: ConstantInt::get(Ty: IRB.getInt32Ty(), V: 0));
612 if (StoredValue->getType()->isIntegerTy())
613 StoredValue = IRB.CreateIntToPtr(V: StoredValue, DestTy: IRB.getPtrTy());
614 // Call TsanVptrUpdate.
615 IRB.CreateCall(Callee: TsanVptrUpdate, Args: {Addr, StoredValue});
616 NumInstrumentedVtableWrites++;
617 return true;
618 }
619 if (!IsWrite && isVtableAccess(I: II.Inst)) {
620 IRB.CreateCall(Callee: TsanVptrLoad, Args: Addr);
621 NumInstrumentedVtableReads++;
622 return true;
623 }
624
625 const Align Alignment = IsWrite ? cast<StoreInst>(Val: II.Inst)->getAlign()
626 : cast<LoadInst>(Val: II.Inst)->getAlign();
627 const bool IsCompoundRW =
628 ClCompoundReadBeforeWrite && (II.Flags & InstructionInfo::kCompoundRW);
629 const bool IsVolatile = ClDistinguishVolatile &&
630 (IsWrite ? cast<StoreInst>(Val: II.Inst)->isVolatile()
631 : cast<LoadInst>(Val: II.Inst)->isVolatile());
632 assert((!IsVolatile || !IsCompoundRW) && "Compound volatile invalid!");
633
634 const uint32_t TypeSize = DL.getTypeStoreSizeInBits(Ty: OrigTy);
635 FunctionCallee OnAccessFunc = nullptr;
636 if (Alignment >= Align(8) || (Alignment.value() % (TypeSize / 8)) == 0) {
637 if (IsCompoundRW)
638 OnAccessFunc = TsanCompoundRW[Idx];
639 else if (IsVolatile)
640 OnAccessFunc = IsWrite ? TsanVolatileWrite[Idx] : TsanVolatileRead[Idx];
641 else
642 OnAccessFunc = IsWrite ? TsanWrite[Idx] : TsanRead[Idx];
643 } else {
644 if (IsCompoundRW)
645 OnAccessFunc = TsanUnalignedCompoundRW[Idx];
646 else if (IsVolatile)
647 OnAccessFunc = IsWrite ? TsanUnalignedVolatileWrite[Idx]
648 : TsanUnalignedVolatileRead[Idx];
649 else
650 OnAccessFunc = IsWrite ? TsanUnalignedWrite[Idx] : TsanUnalignedRead[Idx];
651 }
652 IRB.CreateCall(Callee: OnAccessFunc, Args: Addr);
653 if (IsCompoundRW || IsWrite)
654 NumInstrumentedWrites++;
655 if (IsCompoundRW || !IsWrite)
656 NumInstrumentedReads++;
657 return true;
658}
659
660static ConstantInt *createOrdering(IRBuilder<> *IRB, AtomicOrdering ord) {
661 uint32_t v = 0;
662 switch (ord) {
663 case AtomicOrdering::NotAtomic:
664 llvm_unreachable("unexpected atomic ordering!");
665 case AtomicOrdering::Unordered: [[fallthrough]];
666 case AtomicOrdering::Monotonic: v = 0; break;
667 // Not specified yet:
668 // case AtomicOrdering::Consume: v = 1; break;
669 case AtomicOrdering::Acquire: v = 2; break;
670 case AtomicOrdering::Release: v = 3; break;
671 case AtomicOrdering::AcquireRelease: v = 4; break;
672 case AtomicOrdering::SequentiallyConsistent: v = 5; break;
673 }
674 return IRB->getInt32(C: v);
675}
676
677// If a memset intrinsic gets inlined by the code gen, we will miss races on it.
678// So, we either need to ensure the intrinsic is not inlined, or instrument it.
679// We do not instrument memset/memmove/memcpy intrinsics (too complicated),
680// instead we simply replace them with regular function calls, which are then
681// intercepted by the run-time.
682// Since tsan is running after everyone else, the calls should not be
683// replaced back with intrinsics. If that becomes wrong at some point,
684// we will need to call e.g. __tsan_memset to avoid the intrinsics.
685bool ThreadSanitizer::instrumentMemIntrinsic(Instruction *I) {
686 InstrumentationIRBuilder IRB(I);
687 if (MemSetInst *M = dyn_cast<MemSetInst>(Val: I)) {
688 Value *Cast1 = IRB.CreateIntCast(V: M->getArgOperand(i: 1), DestTy: IRB.getInt32Ty(), isSigned: false);
689 Value *Cast2 = IRB.CreateIntCast(V: M->getArgOperand(i: 2), DestTy: IntptrTy, isSigned: false);
690 IRB.CreateCall(
691 Callee: MemsetFn,
692 Args: {M->getArgOperand(i: 0),
693 Cast1,
694 Cast2});
695 I->eraseFromParent();
696 } else if (MemTransferInst *M = dyn_cast<MemTransferInst>(Val: I)) {
697 IRB.CreateCall(
698 Callee: isa<MemCpyInst>(Val: M) ? MemcpyFn : MemmoveFn,
699 Args: {M->getArgOperand(i: 0),
700 M->getArgOperand(i: 1),
701 IRB.CreateIntCast(V: M->getArgOperand(i: 2), DestTy: IntptrTy, isSigned: false)});
702 I->eraseFromParent();
703 }
704 return false;
705}
706
707// Both llvm and ThreadSanitizer atomic operations are based on C++11/C1x
708// standards. For background see C++11 standard. A slightly older, publicly
709// available draft of the standard (not entirely up-to-date, but close enough
710// for casual browsing) is available here:
711// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2011/n3242.pdf
712// The following page contains more background information:
713// http://www.hpl.hp.com/personal/Hans_Boehm/c++mm/
714
715bool ThreadSanitizer::instrumentAtomic(Instruction *I, const DataLayout &DL) {
716 InstrumentationIRBuilder IRB(I);
717 if (LoadInst *LI = dyn_cast<LoadInst>(Val: I)) {
718 Value *Addr = LI->getPointerOperand();
719 Type *OrigTy = LI->getType();
720 int Idx = getMemoryAccessFuncIndex(OrigTy, Addr, DL);
721 if (Idx < 0)
722 return false;
723 Value *Args[] = {Addr,
724 createOrdering(IRB: &IRB, ord: LI->getOrdering())};
725 Value *C = IRB.CreateCall(Callee: TsanAtomicLoad[Idx], Args);
726 Value *Cast = IRB.CreateBitOrPointerCast(V: C, DestTy: OrigTy);
727 I->replaceAllUsesWith(V: Cast);
728 } else if (StoreInst *SI = dyn_cast<StoreInst>(Val: I)) {
729 Value *Addr = SI->getPointerOperand();
730 int Idx =
731 getMemoryAccessFuncIndex(OrigTy: SI->getValueOperand()->getType(), Addr, DL);
732 if (Idx < 0)
733 return false;
734 const unsigned ByteSize = 1U << Idx;
735 const unsigned BitSize = ByteSize * 8;
736 Type *Ty = Type::getIntNTy(C&: IRB.getContext(), N: BitSize);
737 Value *Args[] = {Addr,
738 IRB.CreateBitOrPointerCast(V: SI->getValueOperand(), DestTy: Ty),
739 createOrdering(IRB: &IRB, ord: SI->getOrdering())};
740 IRB.CreateCall(Callee: TsanAtomicStore[Idx], Args);
741 SI->eraseFromParent();
742 } else if (AtomicRMWInst *RMWI = dyn_cast<AtomicRMWInst>(Val: I)) {
743 Value *Addr = RMWI->getPointerOperand();
744 int Idx =
745 getMemoryAccessFuncIndex(OrigTy: RMWI->getValOperand()->getType(), Addr, DL);
746 if (Idx < 0)
747 return false;
748 FunctionCallee F = TsanAtomicRMW[RMWI->getOperation()][Idx];
749 if (!F)
750 return false;
751 const unsigned ByteSize = 1U << Idx;
752 const unsigned BitSize = ByteSize * 8;
753 Type *Ty = Type::getIntNTy(C&: IRB.getContext(), N: BitSize);
754 Value *Val = RMWI->getValOperand();
755 Value *Args[] = {Addr, IRB.CreateBitOrPointerCast(V: Val, DestTy: Ty),
756 createOrdering(IRB: &IRB, ord: RMWI->getOrdering())};
757 Value *C = IRB.CreateCall(Callee: F, Args);
758 I->replaceAllUsesWith(V: IRB.CreateBitOrPointerCast(V: C, DestTy: Val->getType()));
759 I->eraseFromParent();
760 } else if (AtomicCmpXchgInst *CASI = dyn_cast<AtomicCmpXchgInst>(Val: I)) {
761 Value *Addr = CASI->getPointerOperand();
762 Type *OrigOldValTy = CASI->getNewValOperand()->getType();
763 int Idx = getMemoryAccessFuncIndex(OrigTy: OrigOldValTy, Addr, DL);
764 if (Idx < 0)
765 return false;
766 const unsigned ByteSize = 1U << Idx;
767 const unsigned BitSize = ByteSize * 8;
768 Type *Ty = Type::getIntNTy(C&: IRB.getContext(), N: BitSize);
769 Value *CmpOperand =
770 IRB.CreateBitOrPointerCast(V: CASI->getCompareOperand(), DestTy: Ty);
771 Value *NewOperand =
772 IRB.CreateBitOrPointerCast(V: CASI->getNewValOperand(), DestTy: Ty);
773 Value *Args[] = {Addr,
774 CmpOperand,
775 NewOperand,
776 createOrdering(IRB: &IRB, ord: CASI->getSuccessOrdering()),
777 createOrdering(IRB: &IRB, ord: CASI->getFailureOrdering())};
778 CallInst *C = IRB.CreateCall(Callee: TsanAtomicCAS[Idx], Args);
779 Value *Success = IRB.CreateICmpEQ(LHS: C, RHS: CmpOperand);
780 Value *OldVal = C;
781 if (Ty != OrigOldValTy) {
782 // The value is a pointer, so we need to cast the return value.
783 OldVal = IRB.CreateIntToPtr(V: C, DestTy: OrigOldValTy);
784 }
785
786 Value *Res =
787 IRB.CreateInsertValue(Agg: PoisonValue::get(T: CASI->getType()), Val: OldVal, Idxs: 0);
788 Res = IRB.CreateInsertValue(Agg: Res, Val: Success, Idxs: 1);
789
790 I->replaceAllUsesWith(V: Res);
791 I->eraseFromParent();
792 } else if (FenceInst *FI = dyn_cast<FenceInst>(Val: I)) {
793 Value *Args[] = {createOrdering(IRB: &IRB, ord: FI->getOrdering())};
794 FunctionCallee F = FI->getSyncScopeID() == SyncScope::SingleThread
795 ? TsanAtomicSignalFence
796 : TsanAtomicThreadFence;
797 IRB.CreateCall(Callee: F, Args);
798 FI->eraseFromParent();
799 }
800 return true;
801}
802
803int ThreadSanitizer::getMemoryAccessFuncIndex(Type *OrigTy, Value *Addr,
804 const DataLayout &DL) {
805 assert(OrigTy->isSized());
806 if (OrigTy->isScalableTy()) {
807 // FIXME: support vscale.
808 return -1;
809 }
810 uint32_t TypeSize = DL.getTypeStoreSizeInBits(Ty: OrigTy);
811 if (TypeSize != 8 && TypeSize != 16 &&
812 TypeSize != 32 && TypeSize != 64 && TypeSize != 128) {
813 NumAccessesWithBadSize++;
814 // Ignore all unusual sizes.
815 return -1;
816 }
817 size_t Idx = llvm::countr_zero(Val: TypeSize / 8);
818 assert(Idx < kNumberOfAccessSizes);
819 return Idx;
820}
821