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