1 //===-- SanitizerCoverage.cpp - coverage instrumentation for sanitizers ---===// 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 // Coverage instrumentation that works with AddressSanitizer 11 // and potentially with other Sanitizers. 12 // 13 // We create a Guard variable with the same linkage 14 // as the function and inject this code into the entry block (SCK_Function) 15 // or all blocks (SCK_BB): 16 // if (Guard < 0) { 17 // __sanitizer_cov(&Guard); 18 // } 19 // The accesses to Guard are atomic. The rest of the logic is 20 // in __sanitizer_cov (it's fine to call it more than once). 21 // 22 // With SCK_Edge we also split critical edges this effectively 23 // instrumenting all edges. 24 // 25 // This coverage implementation provides very limited data: 26 // it only tells if a given function (block) was ever executed. No counters. 27 // But for many use cases this is what we need and the added slowdown small. 28 // 29 //===----------------------------------------------------------------------===// 30 31 #include "llvm/ADT/ArrayRef.h" 32 #include "llvm/ADT/SmallVector.h" 33 #include "llvm/Analysis/EHPersonalities.h" 34 #include "llvm/Analysis/PostDominators.h" 35 #include "llvm/IR/CFG.h" 36 #include "llvm/IR/CallSite.h" 37 #include "llvm/IR/DataLayout.h" 38 #include "llvm/IR/DebugInfo.h" 39 #include "llvm/IR/Dominators.h" 40 #include "llvm/IR/Function.h" 41 #include "llvm/IR/IRBuilder.h" 42 #include "llvm/IR/InlineAsm.h" 43 #include "llvm/IR/LLVMContext.h" 44 #include "llvm/IR/MDBuilder.h" 45 #include "llvm/IR/Module.h" 46 #include "llvm/IR/Type.h" 47 #include "llvm/Support/CommandLine.h" 48 #include "llvm/Support/Debug.h" 49 #include "llvm/Support/raw_ostream.h" 50 #include "llvm/Transforms/Instrumentation.h" 51 #include "llvm/Transforms/Scalar.h" 52 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 53 #include "llvm/Transforms/Utils/ModuleUtils.h" 54 55 using namespace llvm; 56 57 #define DEBUG_TYPE "sancov" 58 59 static const char *const SanCovModuleInitName = "__sanitizer_cov_module_init"; 60 static const char *const SanCovName = "__sanitizer_cov"; 61 static const char *const SanCovWithCheckName = "__sanitizer_cov_with_check"; 62 static const char *const SanCovIndirCallName = "__sanitizer_cov_indir_call16"; 63 static const char *const SanCovTracePCIndirName = 64 "__sanitizer_cov_trace_pc_indir"; 65 static const char *const SanCovTraceEnterName = 66 "__sanitizer_cov_trace_func_enter"; 67 static const char *const SanCovTraceBBName = 68 "__sanitizer_cov_trace_basic_block"; 69 static const char *const SanCovTracePCName = "__sanitizer_cov_trace_pc"; 70 static const char *const SanCovTraceCmp1 = "__sanitizer_cov_trace_cmp1"; 71 static const char *const SanCovTraceCmp2 = "__sanitizer_cov_trace_cmp2"; 72 static const char *const SanCovTraceCmp4 = "__sanitizer_cov_trace_cmp4"; 73 static const char *const SanCovTraceCmp8 = "__sanitizer_cov_trace_cmp8"; 74 static const char *const SanCovTraceDiv4 = "__sanitizer_cov_trace_div4"; 75 static const char *const SanCovTraceDiv8 = "__sanitizer_cov_trace_div8"; 76 static const char *const SanCovTraceGep = "__sanitizer_cov_trace_gep"; 77 static const char *const SanCovTraceSwitchName = "__sanitizer_cov_trace_switch"; 78 static const char *const SanCovModuleCtorName = "sancov.module_ctor"; 79 static const uint64_t SanCtorAndDtorPriority = 2; 80 81 static const char *const SanCovTracePCGuardName = 82 "__sanitizer_cov_trace_pc_guard"; 83 static const char *const SanCovTracePCGuardInitName = 84 "__sanitizer_cov_trace_pc_guard_init"; 85 86 static cl::opt<int> ClCoverageLevel( 87 "sanitizer-coverage-level", 88 cl::desc("Sanitizer Coverage. 0: none, 1: entry block, 2: all blocks, " 89 "3: all blocks and critical edges, " 90 "4: above plus indirect calls"), 91 cl::Hidden, cl::init(0)); 92 93 static cl::opt<unsigned> ClCoverageBlockThreshold( 94 "sanitizer-coverage-block-threshold", 95 cl::desc("Use a callback with a guard check inside it if there are" 96 " more than this number of blocks."), 97 cl::Hidden, cl::init(0)); 98 99 static cl::opt<bool> 100 ClExperimentalTracing("sanitizer-coverage-experimental-tracing", 101 cl::desc("Experimental basic-block tracing: insert " 102 "callbacks at every basic block"), 103 cl::Hidden, cl::init(false)); 104 105 static cl::opt<bool> ClExperimentalTracePC("sanitizer-coverage-trace-pc", 106 cl::desc("Experimental pc tracing"), 107 cl::Hidden, cl::init(false)); 108 109 static cl::opt<bool> ClTracePCGuard("sanitizer-coverage-trace-pc-guard", 110 cl::desc("pc tracing with a guard"), 111 cl::Hidden, cl::init(false)); 112 113 static cl::opt<bool> 114 ClCMPTracing("sanitizer-coverage-trace-compares", 115 cl::desc("Tracing of CMP and similar instructions"), 116 cl::Hidden, cl::init(false)); 117 118 static cl::opt<bool> ClDIVTracing("sanitizer-coverage-trace-divs", 119 cl::desc("Tracing of DIV instructions"), 120 cl::Hidden, cl::init(false)); 121 122 static cl::opt<bool> ClGEPTracing("sanitizer-coverage-trace-geps", 123 cl::desc("Tracing of GEP instructions"), 124 cl::Hidden, cl::init(false)); 125 126 static cl::opt<bool> 127 ClPruneBlocks("sanitizer-coverage-prune-blocks", 128 cl::desc("Reduce the number of instrumented blocks"), 129 cl::Hidden, cl::init(true)); 130 131 // Experimental 8-bit counters used as an additional search heuristic during 132 // coverage-guided fuzzing. 133 // The counters are not thread-friendly: 134 // - contention on these counters may cause significant slowdown; 135 // - the counter updates are racy and the results may be inaccurate. 136 // They are also inaccurate due to 8-bit integer overflow. 137 static cl::opt<bool> ClUse8bitCounters("sanitizer-coverage-8bit-counters", 138 cl::desc("Experimental 8-bit counters"), 139 cl::Hidden, cl::init(false)); 140 141 namespace { 142 143 SanitizerCoverageOptions getOptions(int LegacyCoverageLevel) { 144 SanitizerCoverageOptions Res; 145 switch (LegacyCoverageLevel) { 146 case 0: 147 Res.CoverageType = SanitizerCoverageOptions::SCK_None; 148 break; 149 case 1: 150 Res.CoverageType = SanitizerCoverageOptions::SCK_Function; 151 break; 152 case 2: 153 Res.CoverageType = SanitizerCoverageOptions::SCK_BB; 154 break; 155 case 3: 156 Res.CoverageType = SanitizerCoverageOptions::SCK_Edge; 157 break; 158 case 4: 159 Res.CoverageType = SanitizerCoverageOptions::SCK_Edge; 160 Res.IndirectCalls = true; 161 break; 162 } 163 return Res; 164 } 165 166 SanitizerCoverageOptions OverrideFromCL(SanitizerCoverageOptions Options) { 167 // Sets CoverageType and IndirectCalls. 168 SanitizerCoverageOptions CLOpts = getOptions(ClCoverageLevel); 169 Options.CoverageType = std::max(Options.CoverageType, CLOpts.CoverageType); 170 Options.IndirectCalls |= CLOpts.IndirectCalls; 171 Options.TraceBB |= ClExperimentalTracing; 172 Options.TraceCmp |= ClCMPTracing; 173 Options.TraceDiv |= ClDIVTracing; 174 Options.TraceGep |= ClGEPTracing; 175 Options.Use8bitCounters |= ClUse8bitCounters; 176 Options.TracePC |= ClExperimentalTracePC; 177 Options.TracePCGuard |= ClTracePCGuard; 178 return Options; 179 } 180 181 class SanitizerCoverageModule : public ModulePass { 182 public: 183 SanitizerCoverageModule( 184 const SanitizerCoverageOptions &Options = SanitizerCoverageOptions()) 185 : ModulePass(ID), Options(OverrideFromCL(Options)) { 186 initializeSanitizerCoverageModulePass(*PassRegistry::getPassRegistry()); 187 } 188 bool runOnModule(Module &M) override; 189 bool runOnFunction(Function &F); 190 static char ID; // Pass identification, replacement for typeid 191 StringRef getPassName() const override { return "SanitizerCoverageModule"; } 192 193 void getAnalysisUsage(AnalysisUsage &AU) const override { 194 AU.addRequired<DominatorTreeWrapperPass>(); 195 AU.addRequired<PostDominatorTreeWrapperPass>(); 196 } 197 198 private: 199 void InjectCoverageForIndirectCalls(Function &F, 200 ArrayRef<Instruction *> IndirCalls); 201 void InjectTraceForCmp(Function &F, ArrayRef<Instruction *> CmpTraceTargets); 202 void InjectTraceForDiv(Function &F, 203 ArrayRef<BinaryOperator *> DivTraceTargets); 204 void InjectTraceForGep(Function &F, 205 ArrayRef<GetElementPtrInst *> GepTraceTargets); 206 void InjectTraceForSwitch(Function &F, 207 ArrayRef<Instruction *> SwitchTraceTargets); 208 bool InjectCoverage(Function &F, ArrayRef<BasicBlock *> AllBlocks); 209 void CreateFunctionGuardArray(size_t NumGuards, Function &F); 210 void SetNoSanitizeMetadata(Instruction *I); 211 void InjectCoverageAtBlock(Function &F, BasicBlock &BB, size_t Idx, 212 bool UseCalls); 213 unsigned NumberOfInstrumentedBlocks() { 214 return SanCovFunction->getNumUses() + 215 SanCovWithCheckFunction->getNumUses() + SanCovTraceBB->getNumUses() + 216 SanCovTraceEnter->getNumUses(); 217 } 218 StringRef getSanCovTracePCGuardSection() const; 219 StringRef getSanCovTracePCGuardSectionStart() const; 220 StringRef getSanCovTracePCGuardSectionEnd() const; 221 Function *SanCovFunction; 222 Function *SanCovWithCheckFunction; 223 Function *SanCovIndirCallFunction, *SanCovTracePCIndir; 224 Function *SanCovTraceEnter, *SanCovTraceBB, *SanCovTracePC, *SanCovTracePCGuard; 225 Function *SanCovTraceCmpFunction[4]; 226 Function *SanCovTraceDivFunction[2]; 227 Function *SanCovTraceGepFunction; 228 Function *SanCovTraceSwitchFunction; 229 InlineAsm *EmptyAsm; 230 Type *IntptrTy, *IntptrPtrTy, *Int64Ty, *Int64PtrTy, *Int32Ty, *Int32PtrTy; 231 Module *CurModule; 232 Triple TargetTriple; 233 LLVMContext *C; 234 const DataLayout *DL; 235 236 GlobalVariable *GuardArray; 237 GlobalVariable *FunctionGuardArray; // for trace-pc-guard. 238 GlobalVariable *EightBitCounterArray; 239 bool HasSancovGuardsSection; 240 241 SanitizerCoverageOptions Options; 242 }; 243 244 } // namespace 245 246 bool SanitizerCoverageModule::runOnModule(Module &M) { 247 if (Options.CoverageType == SanitizerCoverageOptions::SCK_None) 248 return false; 249 C = &(M.getContext()); 250 DL = &M.getDataLayout(); 251 CurModule = &M; 252 TargetTriple = Triple(M.getTargetTriple()); 253 HasSancovGuardsSection = false; 254 IntptrTy = Type::getIntNTy(*C, DL->getPointerSizeInBits()); 255 IntptrPtrTy = PointerType::getUnqual(IntptrTy); 256 Type *VoidTy = Type::getVoidTy(*C); 257 IRBuilder<> IRB(*C); 258 Type *Int8PtrTy = PointerType::getUnqual(IRB.getInt8Ty()); 259 Int64PtrTy = PointerType::getUnqual(IRB.getInt64Ty()); 260 Int32PtrTy = PointerType::getUnqual(IRB.getInt32Ty()); 261 Int64Ty = IRB.getInt64Ty(); 262 Int32Ty = IRB.getInt32Ty(); 263 264 SanCovFunction = checkSanitizerInterfaceFunction( 265 M.getOrInsertFunction(SanCovName, VoidTy, Int32PtrTy, nullptr)); 266 SanCovWithCheckFunction = checkSanitizerInterfaceFunction( 267 M.getOrInsertFunction(SanCovWithCheckName, VoidTy, Int32PtrTy, nullptr)); 268 SanCovTracePCIndir = checkSanitizerInterfaceFunction( 269 M.getOrInsertFunction(SanCovTracePCIndirName, VoidTy, IntptrTy, nullptr)); 270 SanCovIndirCallFunction = 271 checkSanitizerInterfaceFunction(M.getOrInsertFunction( 272 SanCovIndirCallName, VoidTy, IntptrTy, IntptrTy, nullptr)); 273 SanCovTraceCmpFunction[0] = 274 checkSanitizerInterfaceFunction(M.getOrInsertFunction( 275 SanCovTraceCmp1, VoidTy, IRB.getInt8Ty(), IRB.getInt8Ty(), nullptr)); 276 SanCovTraceCmpFunction[1] = checkSanitizerInterfaceFunction( 277 M.getOrInsertFunction(SanCovTraceCmp2, VoidTy, IRB.getInt16Ty(), 278 IRB.getInt16Ty(), nullptr)); 279 SanCovTraceCmpFunction[2] = checkSanitizerInterfaceFunction( 280 M.getOrInsertFunction(SanCovTraceCmp4, VoidTy, IRB.getInt32Ty(), 281 IRB.getInt32Ty(), nullptr)); 282 SanCovTraceCmpFunction[3] = 283 checkSanitizerInterfaceFunction(M.getOrInsertFunction( 284 SanCovTraceCmp8, VoidTy, Int64Ty, Int64Ty, nullptr)); 285 286 SanCovTraceDivFunction[0] = 287 checkSanitizerInterfaceFunction(M.getOrInsertFunction( 288 SanCovTraceDiv4, VoidTy, IRB.getInt32Ty(), nullptr)); 289 SanCovTraceDivFunction[1] = 290 checkSanitizerInterfaceFunction(M.getOrInsertFunction( 291 SanCovTraceDiv8, VoidTy, Int64Ty, nullptr)); 292 SanCovTraceGepFunction = 293 checkSanitizerInterfaceFunction(M.getOrInsertFunction( 294 SanCovTraceGep, VoidTy, IntptrTy, nullptr)); 295 SanCovTraceSwitchFunction = 296 checkSanitizerInterfaceFunction(M.getOrInsertFunction( 297 SanCovTraceSwitchName, VoidTy, Int64Ty, Int64PtrTy, nullptr)); 298 299 // We insert an empty inline asm after cov callbacks to avoid callback merge. 300 EmptyAsm = InlineAsm::get(FunctionType::get(IRB.getVoidTy(), false), 301 StringRef(""), StringRef(""), 302 /*hasSideEffects=*/true); 303 304 SanCovTracePC = checkSanitizerInterfaceFunction( 305 M.getOrInsertFunction(SanCovTracePCName, VoidTy, nullptr)); 306 SanCovTracePCGuard = checkSanitizerInterfaceFunction(M.getOrInsertFunction( 307 SanCovTracePCGuardName, VoidTy, Int32PtrTy, nullptr)); 308 SanCovTraceEnter = checkSanitizerInterfaceFunction( 309 M.getOrInsertFunction(SanCovTraceEnterName, VoidTy, Int32PtrTy, nullptr)); 310 SanCovTraceBB = checkSanitizerInterfaceFunction( 311 M.getOrInsertFunction(SanCovTraceBBName, VoidTy, Int32PtrTy, nullptr)); 312 313 // At this point we create a dummy array of guards because we don't 314 // know how many elements we will need. 315 Type *Int32Ty = IRB.getInt32Ty(); 316 Type *Int8Ty = IRB.getInt8Ty(); 317 318 if (!Options.TracePCGuard) 319 GuardArray = 320 new GlobalVariable(M, Int32Ty, false, GlobalValue::ExternalLinkage, 321 nullptr, "__sancov_gen_cov_tmp"); 322 if (Options.Use8bitCounters) 323 EightBitCounterArray = 324 new GlobalVariable(M, Int8Ty, false, GlobalVariable::ExternalLinkage, 325 nullptr, "__sancov_gen_cov_tmp"); 326 327 for (auto &F : M) 328 runOnFunction(F); 329 330 auto N = NumberOfInstrumentedBlocks(); 331 332 GlobalVariable *RealGuardArray = nullptr; 333 if (!Options.TracePCGuard) { 334 // Now we know how many elements we need. Create an array of guards 335 // with one extra element at the beginning for the size. 336 Type *Int32ArrayNTy = ArrayType::get(Int32Ty, N + 1); 337 RealGuardArray = new GlobalVariable( 338 M, Int32ArrayNTy, false, GlobalValue::PrivateLinkage, 339 Constant::getNullValue(Int32ArrayNTy), "__sancov_gen_cov"); 340 341 // Replace the dummy array with the real one. 342 GuardArray->replaceAllUsesWith( 343 IRB.CreatePointerCast(RealGuardArray, Int32PtrTy)); 344 GuardArray->eraseFromParent(); 345 } 346 347 GlobalVariable *RealEightBitCounterArray; 348 if (Options.Use8bitCounters) { 349 // Make sure the array is 16-aligned. 350 static const int CounterAlignment = 16; 351 Type *Int8ArrayNTy = ArrayType::get(Int8Ty, alignTo(N, CounterAlignment)); 352 RealEightBitCounterArray = new GlobalVariable( 353 M, Int8ArrayNTy, false, GlobalValue::PrivateLinkage, 354 Constant::getNullValue(Int8ArrayNTy), "__sancov_gen_cov_counter"); 355 RealEightBitCounterArray->setAlignment(CounterAlignment); 356 EightBitCounterArray->replaceAllUsesWith( 357 IRB.CreatePointerCast(RealEightBitCounterArray, Int8PtrTy)); 358 EightBitCounterArray->eraseFromParent(); 359 } 360 361 // Create variable for module (compilation unit) name 362 Constant *ModNameStrConst = 363 ConstantDataArray::getString(M.getContext(), M.getName(), true); 364 GlobalVariable *ModuleName = new GlobalVariable( 365 M, ModNameStrConst->getType(), true, GlobalValue::PrivateLinkage, 366 ModNameStrConst, "__sancov_gen_modname"); 367 if (Options.TracePCGuard) { 368 if (HasSancovGuardsSection) { 369 Function *CtorFunc; 370 GlobalVariable *SecStart = new GlobalVariable( 371 M, Int32PtrTy, false, GlobalVariable::ExternalLinkage, nullptr, 372 getSanCovTracePCGuardSectionStart()); 373 SecStart->setVisibility(GlobalValue::HiddenVisibility); 374 GlobalVariable *SecEnd = new GlobalVariable( 375 M, Int32PtrTy, false, GlobalVariable::ExternalLinkage, nullptr, 376 getSanCovTracePCGuardSectionEnd()); 377 SecEnd->setVisibility(GlobalValue::HiddenVisibility); 378 379 std::tie(CtorFunc, std::ignore) = createSanitizerCtorAndInitFunctions( 380 M, SanCovModuleCtorName, SanCovTracePCGuardInitName, 381 {Int32PtrTy, Int32PtrTy}, 382 {IRB.CreatePointerCast(SecStart, Int32PtrTy), 383 IRB.CreatePointerCast(SecEnd, Int32PtrTy)}); 384 385 if (TargetTriple.supportsCOMDAT()) { 386 // Use comdat to dedup CtorFunc. 387 CtorFunc->setComdat(M.getOrInsertComdat(SanCovModuleCtorName)); 388 appendToGlobalCtors(M, CtorFunc, SanCtorAndDtorPriority, CtorFunc); 389 } else { 390 appendToGlobalCtors(M, CtorFunc, SanCtorAndDtorPriority); 391 } 392 } 393 } else if (!Options.TracePC) { 394 Function *CtorFunc; 395 std::tie(CtorFunc, std::ignore) = createSanitizerCtorAndInitFunctions( 396 M, SanCovModuleCtorName, SanCovModuleInitName, 397 {Int32PtrTy, IntptrTy, Int8PtrTy, Int8PtrTy}, 398 {IRB.CreatePointerCast(RealGuardArray, Int32PtrTy), 399 ConstantInt::get(IntptrTy, N), 400 Options.Use8bitCounters 401 ? IRB.CreatePointerCast(RealEightBitCounterArray, Int8PtrTy) 402 : Constant::getNullValue(Int8PtrTy), 403 IRB.CreatePointerCast(ModuleName, Int8PtrTy)}); 404 405 appendToGlobalCtors(M, CtorFunc, SanCtorAndDtorPriority); 406 } 407 408 return true; 409 } 410 411 // True if block has successors and it dominates all of them. 412 static bool isFullDominator(const BasicBlock *BB, const DominatorTree *DT) { 413 if (succ_begin(BB) == succ_end(BB)) 414 return false; 415 416 for (const BasicBlock *SUCC : make_range(succ_begin(BB), succ_end(BB))) { 417 if (!DT->dominates(BB, SUCC)) 418 return false; 419 } 420 421 return true; 422 } 423 424 // True if block has predecessors and it postdominates all of them. 425 static bool isFullPostDominator(const BasicBlock *BB, 426 const PostDominatorTree *PDT) { 427 if (pred_begin(BB) == pred_end(BB)) 428 return false; 429 430 for (const BasicBlock *PRED : make_range(pred_begin(BB), pred_end(BB))) { 431 if (!PDT->dominates(BB, PRED)) 432 return false; 433 } 434 435 return true; 436 } 437 438 static bool shouldInstrumentBlock(const Function& F, const BasicBlock *BB, const DominatorTree *DT, 439 const PostDominatorTree *PDT) { 440 // Don't insert coverage for unreachable blocks: we will never call 441 // __sanitizer_cov() for them, so counting them in 442 // NumberOfInstrumentedBlocks() might complicate calculation of code coverage 443 // percentage. Also, unreachable instructions frequently have no debug 444 // locations. 445 if (isa<UnreachableInst>(BB->getTerminator())) 446 return false; 447 448 if (!ClPruneBlocks || &F.getEntryBlock() == BB) 449 return true; 450 451 return !(isFullDominator(BB, DT) || isFullPostDominator(BB, PDT)); 452 } 453 454 bool SanitizerCoverageModule::runOnFunction(Function &F) { 455 if (F.empty()) 456 return false; 457 if (F.getName().find(".module_ctor") != std::string::npos) 458 return false; // Should not instrument sanitizer init functions. 459 if (F.getName().startswith("__sanitizer_")) 460 return false; // Don't instrument __sanitizer_* callbacks. 461 // Don't instrument MSVC CRT configuration helpers. They may run before normal 462 // initialization. 463 if (F.getName() == "__local_stdio_printf_options" || 464 F.getName() == "__local_stdio_scanf_options") 465 return false; 466 // Don't instrument functions using SEH for now. Splitting basic blocks like 467 // we do for coverage breaks WinEHPrepare. 468 // FIXME: Remove this when SEH no longer uses landingpad pattern matching. 469 if (F.hasPersonalityFn() && 470 isAsynchronousEHPersonality(classifyEHPersonality(F.getPersonalityFn()))) 471 return false; 472 if (Options.CoverageType >= SanitizerCoverageOptions::SCK_Edge) 473 SplitAllCriticalEdges(F); 474 SmallVector<Instruction *, 8> IndirCalls; 475 SmallVector<BasicBlock *, 16> BlocksToInstrument; 476 SmallVector<Instruction *, 8> CmpTraceTargets; 477 SmallVector<Instruction *, 8> SwitchTraceTargets; 478 SmallVector<BinaryOperator *, 8> DivTraceTargets; 479 SmallVector<GetElementPtrInst *, 8> GepTraceTargets; 480 481 const DominatorTree *DT = 482 &getAnalysis<DominatorTreeWrapperPass>(F).getDomTree(); 483 const PostDominatorTree *PDT = 484 &getAnalysis<PostDominatorTreeWrapperPass>(F).getPostDomTree(); 485 486 for (auto &BB : F) { 487 if (shouldInstrumentBlock(F, &BB, DT, PDT)) 488 BlocksToInstrument.push_back(&BB); 489 for (auto &Inst : BB) { 490 if (Options.IndirectCalls) { 491 CallSite CS(&Inst); 492 if (CS && !CS.getCalledFunction()) 493 IndirCalls.push_back(&Inst); 494 } 495 if (Options.TraceCmp) { 496 if (isa<ICmpInst>(&Inst)) 497 CmpTraceTargets.push_back(&Inst); 498 if (isa<SwitchInst>(&Inst)) 499 SwitchTraceTargets.push_back(&Inst); 500 } 501 if (Options.TraceDiv) 502 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(&Inst)) 503 if (BO->getOpcode() == Instruction::SDiv || 504 BO->getOpcode() == Instruction::UDiv) 505 DivTraceTargets.push_back(BO); 506 if (Options.TraceGep) 507 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(&Inst)) 508 GepTraceTargets.push_back(GEP); 509 } 510 } 511 512 InjectCoverage(F, BlocksToInstrument); 513 InjectCoverageForIndirectCalls(F, IndirCalls); 514 InjectTraceForCmp(F, CmpTraceTargets); 515 InjectTraceForSwitch(F, SwitchTraceTargets); 516 InjectTraceForDiv(F, DivTraceTargets); 517 InjectTraceForGep(F, GepTraceTargets); 518 return true; 519 } 520 void SanitizerCoverageModule::CreateFunctionGuardArray(size_t NumGuards, 521 Function &F) { 522 if (!Options.TracePCGuard) return; 523 HasSancovGuardsSection = true; 524 ArrayType *ArrayOfInt32Ty = ArrayType::get(Int32Ty, NumGuards); 525 FunctionGuardArray = new GlobalVariable( 526 *CurModule, ArrayOfInt32Ty, false, GlobalVariable::PrivateLinkage, 527 Constant::getNullValue(ArrayOfInt32Ty), "__sancov_gen_"); 528 if (auto Comdat = F.getComdat()) 529 FunctionGuardArray->setComdat(Comdat); 530 FunctionGuardArray->setSection(getSanCovTracePCGuardSection()); 531 } 532 533 bool SanitizerCoverageModule::InjectCoverage(Function &F, 534 ArrayRef<BasicBlock *> AllBlocks) { 535 if (AllBlocks.empty()) return false; 536 switch (Options.CoverageType) { 537 case SanitizerCoverageOptions::SCK_None: 538 return false; 539 case SanitizerCoverageOptions::SCK_Function: 540 CreateFunctionGuardArray(1, F); 541 InjectCoverageAtBlock(F, F.getEntryBlock(), 0, false); 542 return true; 543 default: { 544 bool UseCalls = ClCoverageBlockThreshold < AllBlocks.size(); 545 CreateFunctionGuardArray(AllBlocks.size(), F); 546 for (size_t i = 0, N = AllBlocks.size(); i < N; i++) 547 InjectCoverageAtBlock(F, *AllBlocks[i], i, UseCalls); 548 return true; 549 } 550 } 551 } 552 553 // On every indirect call we call a run-time function 554 // __sanitizer_cov_indir_call* with two parameters: 555 // - callee address, 556 // - global cache array that contains CacheSize pointers (zero-initialized). 557 // The cache is used to speed up recording the caller-callee pairs. 558 // The address of the caller is passed implicitly via caller PC. 559 // CacheSize is encoded in the name of the run-time function. 560 void SanitizerCoverageModule::InjectCoverageForIndirectCalls( 561 Function &F, ArrayRef<Instruction *> IndirCalls) { 562 if (IndirCalls.empty()) 563 return; 564 const int CacheSize = 16; 565 const int CacheAlignment = 64; // Align for better performance. 566 Type *Ty = ArrayType::get(IntptrTy, CacheSize); 567 for (auto I : IndirCalls) { 568 IRBuilder<> IRB(I); 569 CallSite CS(I); 570 Value *Callee = CS.getCalledValue(); 571 if (isa<InlineAsm>(Callee)) 572 continue; 573 GlobalVariable *CalleeCache = new GlobalVariable( 574 *F.getParent(), Ty, false, GlobalValue::PrivateLinkage, 575 Constant::getNullValue(Ty), "__sancov_gen_callee_cache"); 576 CalleeCache->setAlignment(CacheAlignment); 577 if (Options.TracePC || Options.TracePCGuard) 578 IRB.CreateCall(SanCovTracePCIndir, 579 IRB.CreatePointerCast(Callee, IntptrTy)); 580 else 581 IRB.CreateCall(SanCovIndirCallFunction, 582 {IRB.CreatePointerCast(Callee, IntptrTy), 583 IRB.CreatePointerCast(CalleeCache, IntptrTy)}); 584 } 585 } 586 587 // For every switch statement we insert a call: 588 // __sanitizer_cov_trace_switch(CondValue, 589 // {NumCases, ValueSizeInBits, Case0Value, Case1Value, Case2Value, ... }) 590 591 void SanitizerCoverageModule::InjectTraceForSwitch( 592 Function &, ArrayRef<Instruction *> SwitchTraceTargets) { 593 for (auto I : SwitchTraceTargets) { 594 if (SwitchInst *SI = dyn_cast<SwitchInst>(I)) { 595 IRBuilder<> IRB(I); 596 SmallVector<Constant *, 16> Initializers; 597 Value *Cond = SI->getCondition(); 598 if (Cond->getType()->getScalarSizeInBits() > 599 Int64Ty->getScalarSizeInBits()) 600 continue; 601 Initializers.push_back(ConstantInt::get(Int64Ty, SI->getNumCases())); 602 Initializers.push_back( 603 ConstantInt::get(Int64Ty, Cond->getType()->getScalarSizeInBits())); 604 if (Cond->getType()->getScalarSizeInBits() < 605 Int64Ty->getScalarSizeInBits()) 606 Cond = IRB.CreateIntCast(Cond, Int64Ty, false); 607 for (auto It : SI->cases()) { 608 Constant *C = It.getCaseValue(); 609 if (C->getType()->getScalarSizeInBits() < 610 Int64Ty->getScalarSizeInBits()) 611 C = ConstantExpr::getCast(CastInst::ZExt, It.getCaseValue(), Int64Ty); 612 Initializers.push_back(C); 613 } 614 std::sort(Initializers.begin() + 2, Initializers.end(), 615 [](const Constant *A, const Constant *B) { 616 return cast<ConstantInt>(A)->getLimitedValue() < 617 cast<ConstantInt>(B)->getLimitedValue(); 618 }); 619 ArrayType *ArrayOfInt64Ty = ArrayType::get(Int64Ty, Initializers.size()); 620 GlobalVariable *GV = new GlobalVariable( 621 *CurModule, ArrayOfInt64Ty, false, GlobalVariable::InternalLinkage, 622 ConstantArray::get(ArrayOfInt64Ty, Initializers), 623 "__sancov_gen_cov_switch_values"); 624 IRB.CreateCall(SanCovTraceSwitchFunction, 625 {Cond, IRB.CreatePointerCast(GV, Int64PtrTy)}); 626 } 627 } 628 } 629 630 void SanitizerCoverageModule::InjectTraceForDiv( 631 Function &, ArrayRef<BinaryOperator *> DivTraceTargets) { 632 for (auto BO : DivTraceTargets) { 633 IRBuilder<> IRB(BO); 634 Value *A1 = BO->getOperand(1); 635 if (isa<ConstantInt>(A1)) continue; 636 if (!A1->getType()->isIntegerTy()) 637 continue; 638 uint64_t TypeSize = DL->getTypeStoreSizeInBits(A1->getType()); 639 int CallbackIdx = TypeSize == 32 ? 0 : 640 TypeSize == 64 ? 1 : -1; 641 if (CallbackIdx < 0) continue; 642 auto Ty = Type::getIntNTy(*C, TypeSize); 643 IRB.CreateCall(SanCovTraceDivFunction[CallbackIdx], 644 {IRB.CreateIntCast(A1, Ty, true)}); 645 } 646 } 647 648 void SanitizerCoverageModule::InjectTraceForGep( 649 Function &, ArrayRef<GetElementPtrInst *> GepTraceTargets) { 650 for (auto GEP : GepTraceTargets) { 651 IRBuilder<> IRB(GEP); 652 for (auto I = GEP->idx_begin(); I != GEP->idx_end(); ++I) 653 if (!isa<ConstantInt>(*I) && (*I)->getType()->isIntegerTy()) 654 IRB.CreateCall(SanCovTraceGepFunction, 655 {IRB.CreateIntCast(*I, IntptrTy, true)}); 656 } 657 } 658 659 void SanitizerCoverageModule::InjectTraceForCmp( 660 Function &, ArrayRef<Instruction *> CmpTraceTargets) { 661 for (auto I : CmpTraceTargets) { 662 if (ICmpInst *ICMP = dyn_cast<ICmpInst>(I)) { 663 IRBuilder<> IRB(ICMP); 664 Value *A0 = ICMP->getOperand(0); 665 Value *A1 = ICMP->getOperand(1); 666 if (!A0->getType()->isIntegerTy()) 667 continue; 668 uint64_t TypeSize = DL->getTypeStoreSizeInBits(A0->getType()); 669 int CallbackIdx = TypeSize == 8 ? 0 : 670 TypeSize == 16 ? 1 : 671 TypeSize == 32 ? 2 : 672 TypeSize == 64 ? 3 : -1; 673 if (CallbackIdx < 0) continue; 674 // __sanitizer_cov_trace_cmp((type_size << 32) | predicate, A0, A1); 675 auto Ty = Type::getIntNTy(*C, TypeSize); 676 IRB.CreateCall( 677 SanCovTraceCmpFunction[CallbackIdx], 678 {IRB.CreateIntCast(A0, Ty, true), IRB.CreateIntCast(A1, Ty, true)}); 679 } 680 } 681 } 682 683 void SanitizerCoverageModule::SetNoSanitizeMetadata(Instruction *I) { 684 I->setMetadata(I->getModule()->getMDKindID("nosanitize"), 685 MDNode::get(*C, None)); 686 } 687 688 void SanitizerCoverageModule::InjectCoverageAtBlock(Function &F, BasicBlock &BB, 689 size_t Idx, bool UseCalls) { 690 BasicBlock::iterator IP = BB.getFirstInsertionPt(); 691 bool IsEntryBB = &BB == &F.getEntryBlock(); 692 DebugLoc EntryLoc; 693 if (IsEntryBB) { 694 if (auto SP = F.getSubprogram()) 695 EntryLoc = DebugLoc::get(SP->getScopeLine(), 0, SP); 696 // Keep static allocas and llvm.localescape calls in the entry block. Even 697 // if we aren't splitting the block, it's nice for allocas to be before 698 // calls. 699 IP = PrepareToSplitEntryBlock(BB, IP); 700 } else { 701 EntryLoc = IP->getDebugLoc(); 702 } 703 704 IRBuilder<> IRB(&*IP); 705 IRB.SetCurrentDebugLocation(EntryLoc); 706 if (Options.TracePC) { 707 IRB.CreateCall(SanCovTracePC); // gets the PC using GET_CALLER_PC. 708 IRB.CreateCall(EmptyAsm, {}); // Avoids callback merge. 709 } else if (Options.TracePCGuard) { 710 auto GuardPtr = IRB.CreateIntToPtr( 711 IRB.CreateAdd(IRB.CreatePointerCast(FunctionGuardArray, IntptrTy), 712 ConstantInt::get(IntptrTy, Idx * 4)), 713 Int32PtrTy); 714 if (!UseCalls) { 715 auto GuardLoad = IRB.CreateLoad(GuardPtr); 716 GuardLoad->setAtomic(AtomicOrdering::Monotonic); 717 GuardLoad->setAlignment(8); 718 SetNoSanitizeMetadata(GuardLoad); // Don't instrument with e.g. asan. 719 auto Cmp = IRB.CreateICmpNE( 720 GuardLoad, Constant::getNullValue(GuardLoad->getType())); 721 auto Ins = SplitBlockAndInsertIfThen( 722 Cmp, &*IP, false, MDBuilder(*C).createBranchWeights(1, 100000)); 723 IRB.SetInsertPoint(Ins); 724 IRB.SetCurrentDebugLocation(EntryLoc); 725 } 726 IRB.CreateCall(SanCovTracePCGuard, GuardPtr); 727 IRB.CreateCall(EmptyAsm, {}); // Avoids callback merge. 728 } else { 729 Value *GuardP = IRB.CreateAdd( 730 IRB.CreatePointerCast(GuardArray, IntptrTy), 731 ConstantInt::get(IntptrTy, (1 + NumberOfInstrumentedBlocks()) * 4)); 732 GuardP = IRB.CreateIntToPtr(GuardP, Int32PtrTy); 733 if (Options.TraceBB) { 734 IRB.CreateCall(IsEntryBB ? SanCovTraceEnter : SanCovTraceBB, GuardP); 735 } else if (UseCalls) { 736 IRB.CreateCall(SanCovWithCheckFunction, GuardP); 737 } else { 738 LoadInst *Load = IRB.CreateLoad(GuardP); 739 Load->setAtomic(AtomicOrdering::Monotonic); 740 Load->setAlignment(4); 741 SetNoSanitizeMetadata(Load); 742 Value *Cmp = 743 IRB.CreateICmpSGE(Constant::getNullValue(Load->getType()), Load); 744 Instruction *Ins = SplitBlockAndInsertIfThen( 745 Cmp, &*IP, false, MDBuilder(*C).createBranchWeights(1, 100000)); 746 IRB.SetInsertPoint(Ins); 747 IRB.SetCurrentDebugLocation(EntryLoc); 748 // __sanitizer_cov gets the PC of the instruction using GET_CALLER_PC. 749 IRB.CreateCall(SanCovFunction, GuardP); 750 IRB.CreateCall(EmptyAsm, {}); // Avoids callback merge. 751 } 752 } 753 754 if (Options.Use8bitCounters) { 755 IRB.SetInsertPoint(&*IP); 756 Value *P = IRB.CreateAdd( 757 IRB.CreatePointerCast(EightBitCounterArray, IntptrTy), 758 ConstantInt::get(IntptrTy, NumberOfInstrumentedBlocks() - 1)); 759 P = IRB.CreateIntToPtr(P, IRB.getInt8PtrTy()); 760 LoadInst *LI = IRB.CreateLoad(P); 761 Value *Inc = IRB.CreateAdd(LI, ConstantInt::get(IRB.getInt8Ty(), 1)); 762 StoreInst *SI = IRB.CreateStore(Inc, P); 763 SetNoSanitizeMetadata(LI); 764 SetNoSanitizeMetadata(SI); 765 } 766 } 767 768 StringRef SanitizerCoverageModule::getSanCovTracePCGuardSection() const { 769 if (TargetTriple.getObjectFormat() == Triple::COFF) 770 return ".SCOV$M"; 771 if (TargetTriple.isOSBinFormatMachO()) 772 return "__DATA,__sancov_guards"; 773 return "__sancov_guards"; 774 } 775 776 StringRef SanitizerCoverageModule::getSanCovTracePCGuardSectionStart() const { 777 if (TargetTriple.isOSBinFormatMachO()) 778 return "\1section$start$__DATA$__sancov_guards"; 779 return "__start___sancov_guards"; 780 } 781 782 StringRef SanitizerCoverageModule::getSanCovTracePCGuardSectionEnd() const { 783 if (TargetTriple.isOSBinFormatMachO()) 784 return "\1section$end$__DATA$__sancov_guards"; 785 return "__stop___sancov_guards"; 786 } 787 788 789 char SanitizerCoverageModule::ID = 0; 790 INITIALIZE_PASS_BEGIN(SanitizerCoverageModule, "sancov", 791 "SanitizerCoverage: TODO." 792 "ModulePass", 793 false, false) 794 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 795 INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass) 796 INITIALIZE_PASS_END(SanitizerCoverageModule, "sancov", 797 "SanitizerCoverage: TODO." 798 "ModulePass", 799 false, false) 800 ModulePass *llvm::createSanitizerCoverageModulePass( 801 const SanitizerCoverageOptions &Options) { 802 return new SanitizerCoverageModule(Options); 803 } 804