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