ThreadSanitizer.cpp revision 243830 
1//===-- ThreadSanitizer.cpp - race detector -------------------------------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file is a part of ThreadSanitizer, a race detector.
11//
12// The tool is under development, for the details about previous versions see
13// http://code.google.com/p/data-race-test
14//
15// The instrumentation phase is quite simple:
16//   - Insert calls to run-time library before every memory access.
17//      - Optimizations may apply to avoid instrumenting some of the accesses.
18//   - Insert calls at function entry/exit.
19// The rest is handled by the run-time library.
20//===----------------------------------------------------------------------===//
21
22#define DEBUG_TYPE "tsan"
23
24#include "BlackList.h"
25#include "llvm/Function.h"
26#include "llvm/IRBuilder.h"
27#include "llvm/Intrinsics.h"
28#include "llvm/LLVMContext.h"
29#include "llvm/Metadata.h"
30#include "llvm/Module.h"
31#include "llvm/Type.h"
32#include "llvm/ADT/SmallSet.h"
33#include "llvm/ADT/SmallString.h"
34#include "llvm/ADT/SmallVector.h"
35#include "llvm/ADT/Statistic.h"
36#include "llvm/ADT/StringExtras.h"
37#include "llvm/Support/CommandLine.h"
38#include "llvm/Support/Debug.h"
39#include "llvm/Support/MathExtras.h"
40#include "llvm/Support/raw_ostream.h"
41#include "llvm/DataLayout.h"
42#include "llvm/Transforms/Instrumentation.h"
43#include "llvm/Transforms/Utils/BasicBlockUtils.h"
44#include "llvm/Transforms/Utils/ModuleUtils.h"
45
46using namespace llvm;
47
48static cl::opt<std::string>  ClBlackListFile("tsan-blacklist",
49       cl::desc("Blacklist file"), cl::Hidden);
50static cl::opt<bool>  ClInstrumentMemoryAccesses(
51    "tsan-instrument-memory-accesses", cl::init(true),
52    cl::desc("Instrument memory accesses"), cl::Hidden);
53static cl::opt<bool>  ClInstrumentFuncEntryExit(
54    "tsan-instrument-func-entry-exit", cl::init(true),
55    cl::desc("Instrument function entry and exit"), cl::Hidden);
56static cl::opt<bool>  ClInstrumentAtomics(
57    "tsan-instrument-atomics", cl::init(true),
58    cl::desc("Instrument atomics"), cl::Hidden);
59
60STATISTIC(NumInstrumentedReads, "Number of instrumented reads");
61STATISTIC(NumInstrumentedWrites, "Number of instrumented writes");
62STATISTIC(NumOmittedReadsBeforeWrite,
63          "Number of reads ignored due to following writes");
64STATISTIC(NumAccessesWithBadSize, "Number of accesses with bad size");
65STATISTIC(NumInstrumentedVtableWrites, "Number of vtable ptr writes");
66STATISTIC(NumOmittedReadsFromConstantGlobals,
67          "Number of reads from constant globals");
68STATISTIC(NumOmittedReadsFromVtable, "Number of vtable reads");
69
70namespace {
71
72/// ThreadSanitizer: instrument the code in module to find races.
73struct ThreadSanitizer : public FunctionPass {
74  ThreadSanitizer();
75  const char *getPassName() const;
76  bool runOnFunction(Function &F);
77  bool doInitialization(Module &M);
78  static char ID;  // Pass identification, replacement for typeid.
79
80 private:
81  bool instrumentLoadOrStore(Instruction *I);
82  bool instrumentAtomic(Instruction *I);
83  void chooseInstructionsToInstrument(SmallVectorImpl<Instruction*> &Local,
84                                      SmallVectorImpl<Instruction*> &All);
85  bool addrPointsToConstantData(Value *Addr);
86  int getMemoryAccessFuncIndex(Value *Addr);
87
88  DataLayout *TD;
89  OwningPtr<BlackList> BL;
90  IntegerType *OrdTy;
91  // Callbacks to run-time library are computed in doInitialization.
92  Function *TsanFuncEntry;
93  Function *TsanFuncExit;
94  // Accesses sizes are powers of two: 1, 2, 4, 8, 16.
95  static const size_t kNumberOfAccessSizes = 5;
96  Function *TsanRead[kNumberOfAccessSizes];
97  Function *TsanWrite[kNumberOfAccessSizes];
98  Function *TsanAtomicLoad[kNumberOfAccessSizes];
99  Function *TsanAtomicStore[kNumberOfAccessSizes];
100  Function *TsanAtomicRMW[AtomicRMWInst::LAST_BINOP + 1][kNumberOfAccessSizes];
101  Function *TsanAtomicCAS[kNumberOfAccessSizes];
102  Function *TsanAtomicThreadFence;
103  Function *TsanAtomicSignalFence;
104  Function *TsanVptrUpdate;
105};
106}  // namespace
107
108char ThreadSanitizer::ID = 0;
109INITIALIZE_PASS(ThreadSanitizer, "tsan",
110    "ThreadSanitizer: detects data races.",
111    false, false)
112
113const char *ThreadSanitizer::getPassName() const {
114  return "ThreadSanitizer";
115}
116
117ThreadSanitizer::ThreadSanitizer()
118  : FunctionPass(ID),
119  TD(NULL) {
120}
121
122FunctionPass *llvm::createThreadSanitizerPass() {
123  return new ThreadSanitizer();
124}
125
126static Function *checkInterfaceFunction(Constant *FuncOrBitcast) {
127  if (Function *F = dyn_cast<Function>(FuncOrBitcast))
128     return F;
129  FuncOrBitcast->dump();
130  report_fatal_error("ThreadSanitizer interface function redefined");
131}
132
133bool ThreadSanitizer::doInitialization(Module &M) {
134  TD = getAnalysisIfAvailable<DataLayout>();
135  if (!TD)
136    return false;
137  BL.reset(new BlackList(ClBlackListFile));
138
139  // Always insert a call to __tsan_init into the module's CTORs.
140  IRBuilder<> IRB(M.getContext());
141  Value *TsanInit = M.getOrInsertFunction("__tsan_init",
142                                          IRB.getVoidTy(), NULL);
143  appendToGlobalCtors(M, cast<Function>(TsanInit), 0);
144
145  // Initialize the callbacks.
146  TsanFuncEntry = checkInterfaceFunction(M.getOrInsertFunction(
147      "__tsan_func_entry", IRB.getVoidTy(), IRB.getInt8PtrTy(), NULL));
148  TsanFuncExit = checkInterfaceFunction(M.getOrInsertFunction(
149      "__tsan_func_exit", IRB.getVoidTy(), NULL));
150  OrdTy = IRB.getInt32Ty();
151  for (size_t i = 0; i < kNumberOfAccessSizes; ++i) {
152    const size_t ByteSize = 1 << i;
153    const size_t BitSize = ByteSize * 8;
154    SmallString<32> ReadName("__tsan_read" + itostr(ByteSize));
155    TsanRead[i] = checkInterfaceFunction(M.getOrInsertFunction(
156        ReadName, IRB.getVoidTy(), IRB.getInt8PtrTy(), NULL));
157
158    SmallString<32> WriteName("__tsan_write" + itostr(ByteSize));
159    TsanWrite[i] = checkInterfaceFunction(M.getOrInsertFunction(
160        WriteName, IRB.getVoidTy(), IRB.getInt8PtrTy(), NULL));
161
162    Type *Ty = Type::getIntNTy(M.getContext(), BitSize);
163    Type *PtrTy = Ty->getPointerTo();
164    SmallString<32> AtomicLoadName("__tsan_atomic" + itostr(BitSize) +
165                                   "_load");
166    TsanAtomicLoad[i] = checkInterfaceFunction(M.getOrInsertFunction(
167        AtomicLoadName, Ty, PtrTy, OrdTy, NULL));
168
169    SmallString<32> AtomicStoreName("__tsan_atomic" + itostr(BitSize) +
170                                    "_store");
171    TsanAtomicStore[i] = checkInterfaceFunction(M.getOrInsertFunction(
172        AtomicStoreName, IRB.getVoidTy(), PtrTy, Ty, OrdTy,
173        NULL));
174
175    for (int op = AtomicRMWInst::FIRST_BINOP;
176        op <= AtomicRMWInst::LAST_BINOP; ++op) {
177      TsanAtomicRMW[op][i] = NULL;
178      const char *NamePart = NULL;
179      if (op == AtomicRMWInst::Xchg)
180        NamePart = "_exchange";
181      else if (op == AtomicRMWInst::Add)
182        NamePart = "_fetch_add";
183      else if (op == AtomicRMWInst::Sub)
184        NamePart = "_fetch_sub";
185      else if (op == AtomicRMWInst::And)
186        NamePart = "_fetch_and";
187      else if (op == AtomicRMWInst::Or)
188        NamePart = "_fetch_or";
189      else if (op == AtomicRMWInst::Xor)
190        NamePart = "_fetch_xor";
191      else
192        continue;
193      SmallString<32> RMWName("__tsan_atomic" + itostr(BitSize) + NamePart);
194      TsanAtomicRMW[op][i] = checkInterfaceFunction(M.getOrInsertFunction(
195          RMWName, Ty, PtrTy, Ty, OrdTy, NULL));
196    }
197
198    SmallString<32> AtomicCASName("__tsan_atomic" + itostr(BitSize) +
199                                  "_compare_exchange_val");
200    TsanAtomicCAS[i] = checkInterfaceFunction(M.getOrInsertFunction(
201        AtomicCASName, Ty, PtrTy, Ty, Ty, OrdTy, NULL));
202  }
203  TsanVptrUpdate = checkInterfaceFunction(M.getOrInsertFunction(
204      "__tsan_vptr_update", IRB.getVoidTy(), IRB.getInt8PtrTy(),
205      IRB.getInt8PtrTy(), NULL));
206  TsanAtomicThreadFence = checkInterfaceFunction(M.getOrInsertFunction(
207      "__tsan_atomic_thread_fence", IRB.getVoidTy(), OrdTy, NULL));
208  TsanAtomicSignalFence = checkInterfaceFunction(M.getOrInsertFunction(
209      "__tsan_atomic_signal_fence", IRB.getVoidTy(), OrdTy, NULL));
210  return true;
211}
212
213static bool isVtableAccess(Instruction *I) {
214  if (MDNode *Tag = I->getMetadata(LLVMContext::MD_tbaa)) {
215    if (Tag->getNumOperands() < 1) return false;
216    if (MDString *Tag1 = dyn_cast<MDString>(Tag->getOperand(0))) {
217      if (Tag1->getString() == "vtable pointer") return true;
218    }
219  }
220  return false;
221}
222
223bool ThreadSanitizer::addrPointsToConstantData(Value *Addr) {
224  // If this is a GEP, just analyze its pointer operand.
225  if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Addr))
226    Addr = GEP->getPointerOperand();
227
228  if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Addr)) {
229    if (GV->isConstant()) {
230      // Reads from constant globals can not race with any writes.
231      NumOmittedReadsFromConstantGlobals++;
232      return true;
233    }
234  } else if (LoadInst *L = dyn_cast<LoadInst>(Addr)) {
235    if (isVtableAccess(L)) {
236      // Reads from a vtable pointer can not race with any writes.
237      NumOmittedReadsFromVtable++;
238      return true;
239    }
240  }
241  return false;
242}
243
244// Instrumenting some of the accesses may be proven redundant.
245// Currently handled:
246//  - read-before-write (within same BB, no calls between)
247//
248// We do not handle some of the patterns that should not survive
249// after the classic compiler optimizations.
250// E.g. two reads from the same temp should be eliminated by CSE,
251// two writes should be eliminated by DSE, etc.
252//
253// 'Local' is a vector of insns within the same BB (no calls between).
254// 'All' is a vector of insns that will be instrumented.
255void ThreadSanitizer::chooseInstructionsToInstrument(
256    SmallVectorImpl<Instruction*> &Local,
257    SmallVectorImpl<Instruction*> &All) {
258  SmallSet<Value*, 8> WriteTargets;
259  // Iterate from the end.
260  for (SmallVectorImpl<Instruction*>::reverse_iterator It = Local.rbegin(),
261       E = Local.rend(); It != E; ++It) {
262    Instruction *I = *It;
263    if (StoreInst *Store = dyn_cast<StoreInst>(I)) {
264      WriteTargets.insert(Store->getPointerOperand());
265    } else {
266      LoadInst *Load = cast<LoadInst>(I);
267      Value *Addr = Load->getPointerOperand();
268      if (WriteTargets.count(Addr)) {
269        // We will write to this temp, so no reason to analyze the read.
270        NumOmittedReadsBeforeWrite++;
271        continue;
272      }
273      if (addrPointsToConstantData(Addr)) {
274        // Addr points to some constant data -- it can not race with any writes.
275        continue;
276      }
277    }
278    All.push_back(I);
279  }
280  Local.clear();
281}
282
283static bool isAtomic(Instruction *I) {
284  if (LoadInst *LI = dyn_cast<LoadInst>(I))
285    return LI->isAtomic() && LI->getSynchScope() == CrossThread;
286  if (StoreInst *SI = dyn_cast<StoreInst>(I))
287    return SI->isAtomic() && SI->getSynchScope() == CrossThread;
288  if (isa<AtomicRMWInst>(I))
289    return true;
290  if (isa<AtomicCmpXchgInst>(I))
291    return true;
292  if (isa<FenceInst>(I))
293    return true;
294  return false;
295}
296
297bool ThreadSanitizer::runOnFunction(Function &F) {
298  if (!TD) return false;
299  if (BL->isIn(F)) return false;
300  SmallVector<Instruction*, 8> RetVec;
301  SmallVector<Instruction*, 8> AllLoadsAndStores;
302  SmallVector<Instruction*, 8> LocalLoadsAndStores;
303  SmallVector<Instruction*, 8> AtomicAccesses;
304  bool Res = false;
305  bool HasCalls = false;
306
307  // Traverse all instructions, collect loads/stores/returns, check for calls.
308  for (Function::iterator FI = F.begin(), FE = F.end();
309       FI != FE; ++FI) {
310    BasicBlock &BB = *FI;
311    for (BasicBlock::iterator BI = BB.begin(), BE = BB.end();
312         BI != BE; ++BI) {
313      if (isAtomic(BI))
314        AtomicAccesses.push_back(BI);
315      else if (isa<LoadInst>(BI) || isa<StoreInst>(BI))
316        LocalLoadsAndStores.push_back(BI);
317      else if (isa<ReturnInst>(BI))
318        RetVec.push_back(BI);
319      else if (isa<CallInst>(BI) || isa<InvokeInst>(BI)) {
320        HasCalls = true;
321        chooseInstructionsToInstrument(LocalLoadsAndStores, AllLoadsAndStores);
322      }
323    }
324    chooseInstructionsToInstrument(LocalLoadsAndStores, AllLoadsAndStores);
325  }
326
327  // We have collected all loads and stores.
328  // FIXME: many of these accesses do not need to be checked for races
329  // (e.g. variables that do not escape, etc).
330
331  // Instrument memory accesses.
332  if (ClInstrumentMemoryAccesses)
333    for (size_t i = 0, n = AllLoadsAndStores.size(); i < n; ++i) {
334      Res |= instrumentLoadOrStore(AllLoadsAndStores[i]);
335    }
336
337  // Instrument atomic memory accesses.
338  if (ClInstrumentAtomics)
339    for (size_t i = 0, n = AtomicAccesses.size(); i < n; ++i) {
340      Res |= instrumentAtomic(AtomicAccesses[i]);
341    }
342
343  // Instrument function entry/exit points if there were instrumented accesses.
344  if ((Res || HasCalls) && ClInstrumentFuncEntryExit) {
345    IRBuilder<> IRB(F.getEntryBlock().getFirstNonPHI());
346    Value *ReturnAddress = IRB.CreateCall(
347        Intrinsic::getDeclaration(F.getParent(), Intrinsic::returnaddress),
348        IRB.getInt32(0));
349    IRB.CreateCall(TsanFuncEntry, ReturnAddress);
350    for (size_t i = 0, n = RetVec.size(); i < n; ++i) {
351      IRBuilder<> IRBRet(RetVec[i]);
352      IRBRet.CreateCall(TsanFuncExit);
353    }
354    Res = true;
355  }
356  return Res;
357}
358
359bool ThreadSanitizer::instrumentLoadOrStore(Instruction *I) {
360  IRBuilder<> IRB(I);
361  bool IsWrite = isa<StoreInst>(*I);
362  Value *Addr = IsWrite
363      ? cast<StoreInst>(I)->getPointerOperand()
364      : cast<LoadInst>(I)->getPointerOperand();
365  int Idx = getMemoryAccessFuncIndex(Addr);
366  if (Idx < 0)
367    return false;
368  if (IsWrite && isVtableAccess(I)) {
369    DEBUG(dbgs() << "  VPTR : " << *I << "\n");
370    Value *StoredValue = cast<StoreInst>(I)->getValueOperand();
371    // StoredValue does not necessary have a pointer type.
372    if (isa<IntegerType>(StoredValue->getType()))
373      StoredValue = IRB.CreateIntToPtr(StoredValue, IRB.getInt8PtrTy());
374    // Call TsanVptrUpdate.
375    IRB.CreateCall2(TsanVptrUpdate,
376                    IRB.CreatePointerCast(Addr, IRB.getInt8PtrTy()),
377                    IRB.CreatePointerCast(StoredValue, IRB.getInt8PtrTy()));
378    NumInstrumentedVtableWrites++;
379    return true;
380  }
381  Value *OnAccessFunc = IsWrite ? TsanWrite[Idx] : TsanRead[Idx];
382  IRB.CreateCall(OnAccessFunc, IRB.CreatePointerCast(Addr, IRB.getInt8PtrTy()));
383  if (IsWrite) NumInstrumentedWrites++;
384  else         NumInstrumentedReads++;
385  return true;
386}
387
388static ConstantInt *createOrdering(IRBuilder<> *IRB, AtomicOrdering ord) {
389  uint32_t v = 0;
390  switch (ord) {
391    case NotAtomic:              assert(false);
392    case Unordered:              // Fall-through.
393    case Monotonic:              v = 0; break;
394 // case Consume:                v = 1; break;  // Not specified yet.
395    case Acquire:                v = 2; break;
396    case Release:                v = 3; break;
397    case AcquireRelease:         v = 4; break;
398    case SequentiallyConsistent: v = 5; break;
399  }
400  return IRB->getInt32(v);
401}
402
403bool ThreadSanitizer::instrumentAtomic(Instruction *I) {
404  IRBuilder<> IRB(I);
405  if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
406    Value *Addr = LI->getPointerOperand();
407    int Idx = getMemoryAccessFuncIndex(Addr);
408    if (Idx < 0)
409      return false;
410    const size_t ByteSize = 1 << Idx;
411    const size_t BitSize = ByteSize * 8;
412    Type *Ty = Type::getIntNTy(IRB.getContext(), BitSize);
413    Type *PtrTy = Ty->getPointerTo();
414    Value *Args[] = {IRB.CreatePointerCast(Addr, PtrTy),
415                     createOrdering(&IRB, LI->getOrdering())};
416    CallInst *C = CallInst::Create(TsanAtomicLoad[Idx],
417                                   ArrayRef<Value*>(Args));
418    ReplaceInstWithInst(I, C);
419
420  } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
421    Value *Addr = SI->getPointerOperand();
422    int Idx = getMemoryAccessFuncIndex(Addr);
423    if (Idx < 0)
424      return false;
425    const size_t ByteSize = 1 << Idx;
426    const size_t BitSize = ByteSize * 8;
427    Type *Ty = Type::getIntNTy(IRB.getContext(), BitSize);
428    Type *PtrTy = Ty->getPointerTo();
429    Value *Args[] = {IRB.CreatePointerCast(Addr, PtrTy),
430                     IRB.CreateIntCast(SI->getValueOperand(), Ty, false),
431                     createOrdering(&IRB, SI->getOrdering())};
432    CallInst *C = CallInst::Create(TsanAtomicStore[Idx],
433                                   ArrayRef<Value*>(Args));
434    ReplaceInstWithInst(I, C);
435  } else if (AtomicRMWInst *RMWI = dyn_cast<AtomicRMWInst>(I)) {
436    Value *Addr = RMWI->getPointerOperand();
437    int Idx = getMemoryAccessFuncIndex(Addr);
438    if (Idx < 0)
439      return false;
440    Function *F = TsanAtomicRMW[RMWI->getOperation()][Idx];
441    if (F == NULL)
442      return false;
443    const size_t ByteSize = 1 << Idx;
444    const size_t BitSize = ByteSize * 8;
445    Type *Ty = Type::getIntNTy(IRB.getContext(), BitSize);
446    Type *PtrTy = Ty->getPointerTo();
447    Value *Args[] = {IRB.CreatePointerCast(Addr, PtrTy),
448                     IRB.CreateIntCast(RMWI->getValOperand(), Ty, false),
449                     createOrdering(&IRB, RMWI->getOrdering())};
450    CallInst *C = CallInst::Create(F, ArrayRef<Value*>(Args));
451    ReplaceInstWithInst(I, C);
452  } else if (AtomicCmpXchgInst *CASI = dyn_cast<AtomicCmpXchgInst>(I)) {
453    Value *Addr = CASI->getPointerOperand();
454    int Idx = getMemoryAccessFuncIndex(Addr);
455    if (Idx < 0)
456      return false;
457    const size_t ByteSize = 1 << Idx;
458    const size_t BitSize = ByteSize * 8;
459    Type *Ty = Type::getIntNTy(IRB.getContext(), BitSize);
460    Type *PtrTy = Ty->getPointerTo();
461    Value *Args[] = {IRB.CreatePointerCast(Addr, PtrTy),
462                     IRB.CreateIntCast(CASI->getCompareOperand(), Ty, false),
463                     IRB.CreateIntCast(CASI->getNewValOperand(), Ty, false),
464                     createOrdering(&IRB, CASI->getOrdering())};
465    CallInst *C = CallInst::Create(TsanAtomicCAS[Idx], ArrayRef<Value*>(Args));
466    ReplaceInstWithInst(I, C);
467  } else if (FenceInst *FI = dyn_cast<FenceInst>(I)) {
468    Value *Args[] = {createOrdering(&IRB, FI->getOrdering())};
469    Function *F = FI->getSynchScope() == SingleThread ?
470        TsanAtomicSignalFence : TsanAtomicThreadFence;
471    CallInst *C = CallInst::Create(F, ArrayRef<Value*>(Args));
472    ReplaceInstWithInst(I, C);
473  }
474  return true;
475}
476
477int ThreadSanitizer::getMemoryAccessFuncIndex(Value *Addr) {
478  Type *OrigPtrTy = Addr->getType();
479  Type *OrigTy = cast<PointerType>(OrigPtrTy)->getElementType();
480  assert(OrigTy->isSized());
481  uint32_t TypeSize = TD->getTypeStoreSizeInBits(OrigTy);
482  if (TypeSize != 8  && TypeSize != 16 &&
483      TypeSize != 32 && TypeSize != 64 && TypeSize != 128) {
484    NumAccessesWithBadSize++;
485    // Ignore all unusual sizes.
486    return -1;
487  }
488  size_t Idx = CountTrailingZeros_32(TypeSize / 8);
489  assert(Idx < kNumberOfAccessSizes);
490  return Idx;
491}
492