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