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 { 111 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 130 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 { 177 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 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 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 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) 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 225 void ThreadSanitizerLegacyPass::getAnalysisUsage(AnalysisUsage &AU) const { 226 AU.addRequired<TargetLibraryInfoWrapperPass>(); 227 } 228 229 bool ThreadSanitizerLegacyPass::doInitialization(Module &M) { 230 insertModuleCtor(M); 231 TSan.emplace(); 232 return true; 233 } 234 235 bool ThreadSanitizerLegacyPass::runOnFunction(Function &F) { 236 auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F); 237 TSan->sanitizeFunction(F, TLI); 238 return true; 239 } 240 241 FunctionPass *llvm::createThreadSanitizerLegacyPassPass() { 242 return new ThreadSanitizerLegacyPass(); 243 } 244 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 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. 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 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. 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 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 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 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 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 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. 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 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 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