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