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 51 using namespace llvm; 52 53 #define DEBUG_TYPE "tsan" 54 55 static cl::opt<bool> ClInstrumentMemoryAccesses( 56 "tsan-instrument-memory-accesses", cl::init(true), 57 cl::desc("Instrument memory accesses"), cl::Hidden); 58 static cl::opt<bool> 59 ClInstrumentFuncEntryExit("tsan-instrument-func-entry-exit", cl::init(true), 60 cl::desc("Instrument function entry and exit"), 61 cl::Hidden); 62 static 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); 66 static cl::opt<bool> ClInstrumentAtomics("tsan-instrument-atomics", 67 cl::init(true), 68 cl::desc("Instrument atomics"), 69 cl::Hidden); 70 static cl::opt<bool> ClInstrumentMemIntrinsics( 71 "tsan-instrument-memintrinsics", cl::init(true), 72 cl::desc("Instrument memintrinsics (memset/memcpy/memmove)"), cl::Hidden); 73 static cl::opt<bool> ClDistinguishVolatile( 74 "tsan-distinguish-volatile", cl::init(false), 75 cl::desc("Emit special instrumentation for accesses to volatiles"), 76 cl::Hidden); 77 static 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); 81 static 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 86 STATISTIC(NumInstrumentedReads, "Number of instrumented reads"); 87 STATISTIC(NumInstrumentedWrites, "Number of instrumented writes"); 88 STATISTIC(NumOmittedReadsBeforeWrite, 89 "Number of reads ignored due to following writes"); 90 STATISTIC(NumAccessesWithBadSize, "Number of accesses with bad size"); 91 STATISTIC(NumInstrumentedVtableWrites, "Number of vtable ptr writes"); 92 STATISTIC(NumInstrumentedVtableReads, "Number of vtable ptr reads"); 93 STATISTIC(NumOmittedReadsFromConstantGlobals, 94 "Number of reads from constant globals"); 95 STATISTIC(NumOmittedReadsFromVtable, "Number of vtable reads"); 96 STATISTIC(NumOmittedNonCaptured, "Number of accesses ignored due to capturing"); 97 98 const char kTsanModuleCtorName[] = "tsan.module_ctor"; 99 const char kTsanInitName[] = "__tsan_init"; 100 101 namespace { 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. 109 struct 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 121 private: 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 175 void 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 185 PreservedAnalyses 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 193 PreservedAnalyses ModuleThreadSanitizerPass::run(Module &M, 194 ModuleAnalysisManager &MAM) { 195 insertModuleCtor(M); 196 return PreservedAnalyses::none(); 197 } 198 void 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 346 static 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. 354 static 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 385 bool 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. 418 void 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 475 static 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 485 void 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 495 bool 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 589 bool 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 666 static 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. 691 bool ThreadSanitizer::instrumentMemIntrinsic(Instruction *I) { 692 InstrumentationIRBuilder 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 719 bool 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 813 int ThreadSanitizer::getMemoryAccessFuncIndex(Type *OrigTy, Value *Addr, 814 const DataLayout &DL) { 815 assert(OrigTy->isSized()); 816 uint32_t TypeSize = DL.getTypeStoreSizeInBits(OrigTy); 817 if (TypeSize != 8 && TypeSize != 16 && 818 TypeSize != 32 && TypeSize != 64 && TypeSize != 128) { 819 NumAccessesWithBadSize++; 820 // Ignore all unusual sizes. 821 return -1; 822 } 823 size_t Idx = llvm::countr_zero(TypeSize / 8); 824 assert(Idx < kNumberOfAccessSizes); 825 return Idx; 826 } 827