diff options
Diffstat (limited to 'lib/Transforms/Instrumentation/SanitizerCoverage.cpp')
-rw-r--r-- | lib/Transforms/Instrumentation/SanitizerCoverage.cpp | 253 |
1 files changed, 171 insertions, 82 deletions
diff --git a/lib/Transforms/Instrumentation/SanitizerCoverage.cpp b/lib/Transforms/Instrumentation/SanitizerCoverage.cpp index 09de7a2cda2b..7d404473655d 100644 --- a/lib/Transforms/Instrumentation/SanitizerCoverage.cpp +++ b/lib/Transforms/Instrumentation/SanitizerCoverage.cpp @@ -28,13 +28,15 @@ // //===----------------------------------------------------------------------===// -#include "llvm/Transforms/Instrumentation.h" #include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/SmallVector.h" #include "llvm/Analysis/EHPersonalities.h" +#include "llvm/Analysis/PostDominators.h" +#include "llvm/IR/CFG.h" #include "llvm/IR/CallSite.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/DebugInfo.h" +#include "llvm/IR/Dominators.h" #include "llvm/IR/Function.h" #include "llvm/IR/IRBuilder.h" #include "llvm/IR/InlineAsm.h" @@ -45,6 +47,7 @@ #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" +#include "llvm/Transforms/Instrumentation.h" #include "llvm/Transforms/Scalar.h" #include "llvm/Transforms/Utils/BasicBlockUtils.h" #include "llvm/Transforms/Utils/ModuleUtils.h" @@ -53,22 +56,28 @@ using namespace llvm; #define DEBUG_TYPE "sancov" -static const char *const kSanCovModuleInitName = "__sanitizer_cov_module_init"; -static const char *const kSanCovName = "__sanitizer_cov"; -static const char *const kSanCovWithCheckName = "__sanitizer_cov_with_check"; -static const char *const kSanCovIndirCallName = "__sanitizer_cov_indir_call16"; -static const char *const kSanCovTraceEnter = "__sanitizer_cov_trace_func_enter"; -static const char *const kSanCovTraceBB = "__sanitizer_cov_trace_basic_block"; -static const char *const kSanCovTraceCmp = "__sanitizer_cov_trace_cmp"; -static const char *const kSanCovTraceSwitch = "__sanitizer_cov_trace_switch"; -static const char *const kSanCovModuleCtorName = "sancov.module_ctor"; -static const uint64_t kSanCtorAndDtorPriority = 2; - -static cl::opt<int> ClCoverageLevel("sanitizer-coverage-level", - cl::desc("Sanitizer Coverage. 0: none, 1: entry block, 2: all blocks, " - "3: all blocks and critical edges, " - "4: above plus indirect calls"), - cl::Hidden, cl::init(0)); +static const char *const SanCovModuleInitName = "__sanitizer_cov_module_init"; +static const char *const SanCovName = "__sanitizer_cov"; +static const char *const SanCovWithCheckName = "__sanitizer_cov_with_check"; +static const char *const SanCovIndirCallName = "__sanitizer_cov_indir_call16"; +static const char *const SanCovTracePCIndirName = + "__sanitizer_cov_trace_pc_indir"; +static const char *const SanCovTraceEnterName = + "__sanitizer_cov_trace_func_enter"; +static const char *const SanCovTraceBBName = + "__sanitizer_cov_trace_basic_block"; +static const char *const SanCovTracePCName = "__sanitizer_cov_trace_pc"; +static const char *const SanCovTraceCmpName = "__sanitizer_cov_trace_cmp"; +static const char *const SanCovTraceSwitchName = "__sanitizer_cov_trace_switch"; +static const char *const SanCovModuleCtorName = "sancov.module_ctor"; +static const uint64_t SanCtorAndDtorPriority = 2; + +static cl::opt<int> ClCoverageLevel( + "sanitizer-coverage-level", + cl::desc("Sanitizer Coverage. 0: none, 1: entry block, 2: all blocks, " + "3: all blocks and critical edges, " + "4: above plus indirect calls"), + cl::Hidden, cl::init(0)); static cl::opt<unsigned> ClCoverageBlockThreshold( "sanitizer-coverage-block-threshold", @@ -82,12 +91,21 @@ static cl::opt<bool> "callbacks at every basic block"), cl::Hidden, cl::init(false)); +static cl::opt<bool> ClExperimentalTracePC("sanitizer-coverage-trace-pc", + cl::desc("Experimental pc tracing"), + cl::Hidden, cl::init(false)); + static cl::opt<bool> ClExperimentalCMPTracing("sanitizer-coverage-experimental-trace-compares", cl::desc("Experimental tracing of CMP and similar " "instructions"), cl::Hidden, cl::init(false)); +static cl::opt<bool> + ClPruneBlocks("sanitizer-coverage-prune-blocks", + cl::desc("Reduce the number of instrumented blocks"), + cl::Hidden, cl::init(true)); + // Experimental 8-bit counters used as an additional search heuristic during // coverage-guided fuzzing. // The counters are not thread-friendly: @@ -131,22 +149,28 @@ SanitizerCoverageOptions OverrideFromCL(SanitizerCoverageOptions Options) { Options.TraceBB |= ClExperimentalTracing; Options.TraceCmp |= ClExperimentalCMPTracing; Options.Use8bitCounters |= ClUse8bitCounters; + Options.TracePC |= ClExperimentalTracePC; return Options; } class SanitizerCoverageModule : public ModulePass { - public: +public: SanitizerCoverageModule( const SanitizerCoverageOptions &Options = SanitizerCoverageOptions()) - : ModulePass(ID), Options(OverrideFromCL(Options)) {} + : ModulePass(ID), Options(OverrideFromCL(Options)) { + initializeSanitizerCoverageModulePass(*PassRegistry::getPassRegistry()); + } bool runOnModule(Module &M) override; bool runOnFunction(Function &F); - static char ID; // Pass identification, replacement for typeid - const char *getPassName() const override { - return "SanitizerCoverageModule"; + static char ID; // Pass identification, replacement for typeid + const char *getPassName() const override { return "SanitizerCoverageModule"; } + + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.addRequired<DominatorTreeWrapperPass>(); + AU.addRequired<PostDominatorTreeWrapperPass>(); } - private: +private: void InjectCoverageForIndirectCalls(Function &F, ArrayRef<Instruction *> IndirCalls); void InjectTraceForCmp(Function &F, ArrayRef<Instruction *> CmpTraceTargets); @@ -162,8 +186,8 @@ class SanitizerCoverageModule : public ModulePass { } Function *SanCovFunction; Function *SanCovWithCheckFunction; - Function *SanCovIndirCallFunction; - Function *SanCovTraceEnter, *SanCovTraceBB; + Function *SanCovIndirCallFunction, *SanCovTracePCIndir; + Function *SanCovTraceEnter, *SanCovTraceBB, *SanCovTracePC; Function *SanCovTraceCmpFunction; Function *SanCovTraceSwitchFunction; InlineAsm *EmptyAsm; @@ -178,7 +202,7 @@ class SanitizerCoverageModule : public ModulePass { SanitizerCoverageOptions Options; }; -} // namespace +} // namespace bool SanitizerCoverageModule::runOnModule(Module &M) { if (Options.CoverageType == SanitizerCoverageOptions::SCK_None) @@ -195,28 +219,32 @@ bool SanitizerCoverageModule::runOnModule(Module &M) { Int64Ty = IRB.getInt64Ty(); SanCovFunction = checkSanitizerInterfaceFunction( - M.getOrInsertFunction(kSanCovName, VoidTy, Int32PtrTy, nullptr)); + M.getOrInsertFunction(SanCovName, VoidTy, Int32PtrTy, nullptr)); SanCovWithCheckFunction = checkSanitizerInterfaceFunction( - M.getOrInsertFunction(kSanCovWithCheckName, VoidTy, Int32PtrTy, nullptr)); + M.getOrInsertFunction(SanCovWithCheckName, VoidTy, Int32PtrTy, nullptr)); + SanCovTracePCIndir = checkSanitizerInterfaceFunction( + M.getOrInsertFunction(SanCovTracePCIndirName, VoidTy, IntptrTy, nullptr)); SanCovIndirCallFunction = checkSanitizerInterfaceFunction(M.getOrInsertFunction( - kSanCovIndirCallName, VoidTy, IntptrTy, IntptrTy, nullptr)); + SanCovIndirCallName, VoidTy, IntptrTy, IntptrTy, nullptr)); SanCovTraceCmpFunction = checkSanitizerInterfaceFunction(M.getOrInsertFunction( - kSanCovTraceCmp, VoidTy, Int64Ty, Int64Ty, Int64Ty, nullptr)); + SanCovTraceCmpName, VoidTy, Int64Ty, Int64Ty, Int64Ty, nullptr)); SanCovTraceSwitchFunction = checkSanitizerInterfaceFunction(M.getOrInsertFunction( - kSanCovTraceSwitch, VoidTy, Int64Ty, Int64PtrTy, nullptr)); + SanCovTraceSwitchName, VoidTy, Int64Ty, Int64PtrTy, nullptr)); // We insert an empty inline asm after cov callbacks to avoid callback merge. EmptyAsm = InlineAsm::get(FunctionType::get(IRB.getVoidTy(), false), StringRef(""), StringRef(""), /*hasSideEffects=*/true); + SanCovTracePC = checkSanitizerInterfaceFunction( + M.getOrInsertFunction(SanCovTracePCName, VoidTy, nullptr)); SanCovTraceEnter = checkSanitizerInterfaceFunction( - M.getOrInsertFunction(kSanCovTraceEnter, VoidTy, Int32PtrTy, nullptr)); + M.getOrInsertFunction(SanCovTraceEnterName, VoidTy, Int32PtrTy, nullptr)); SanCovTraceBB = checkSanitizerInterfaceFunction( - M.getOrInsertFunction(kSanCovTraceBB, VoidTy, Int32PtrTy, nullptr)); + M.getOrInsertFunction(SanCovTraceBBName, VoidTy, Int32PtrTy, nullptr)); // At this point we create a dummy array of guards because we don't // know how many elements we will need. @@ -243,7 +271,6 @@ bool SanitizerCoverageModule::runOnModule(Module &M) { M, Int32ArrayNTy, false, GlobalValue::PrivateLinkage, Constant::getNullValue(Int32ArrayNTy), "__sancov_gen_cov"); - // Replace the dummy array with the real one. GuardArray->replaceAllUsesWith( IRB.CreatePointerCast(RealGuardArray, Int32PtrTy)); @@ -252,13 +279,12 @@ bool SanitizerCoverageModule::runOnModule(Module &M) { GlobalVariable *RealEightBitCounterArray; if (Options.Use8bitCounters) { // Make sure the array is 16-aligned. - static const int kCounterAlignment = 16; - Type *Int8ArrayNTy = - ArrayType::get(Int8Ty, RoundUpToAlignment(N, kCounterAlignment)); + static const int CounterAlignment = 16; + Type *Int8ArrayNTy = ArrayType::get(Int8Ty, alignTo(N, CounterAlignment)); RealEightBitCounterArray = new GlobalVariable( M, Int8ArrayNTy, false, GlobalValue::PrivateLinkage, Constant::getNullValue(Int8ArrayNTy), "__sancov_gen_cov_counter"); - RealEightBitCounterArray->setAlignment(kCounterAlignment); + RealEightBitCounterArray->setAlignment(CounterAlignment); EightBitCounterArray->replaceAllUsesWith( IRB.CreatePointerCast(RealEightBitCounterArray, Int8PtrTy)); EightBitCounterArray->eraseFromParent(); @@ -271,26 +297,64 @@ bool SanitizerCoverageModule::runOnModule(Module &M) { new GlobalVariable(M, ModNameStrConst->getType(), true, GlobalValue::PrivateLinkage, ModNameStrConst); - Function *CtorFunc; - std::tie(CtorFunc, std::ignore) = createSanitizerCtorAndInitFunctions( - M, kSanCovModuleCtorName, kSanCovModuleInitName, - {Int32PtrTy, IntptrTy, Int8PtrTy, Int8PtrTy}, - {IRB.CreatePointerCast(RealGuardArray, Int32PtrTy), - ConstantInt::get(IntptrTy, N), - Options.Use8bitCounters - ? IRB.CreatePointerCast(RealEightBitCounterArray, Int8PtrTy) - : Constant::getNullValue(Int8PtrTy), - IRB.CreatePointerCast(ModuleName, Int8PtrTy)}); + if (!Options.TracePC) { + Function *CtorFunc; + std::tie(CtorFunc, std::ignore) = createSanitizerCtorAndInitFunctions( + M, SanCovModuleCtorName, SanCovModuleInitName, + {Int32PtrTy, IntptrTy, Int8PtrTy, Int8PtrTy}, + {IRB.CreatePointerCast(RealGuardArray, Int32PtrTy), + ConstantInt::get(IntptrTy, N), + Options.Use8bitCounters + ? IRB.CreatePointerCast(RealEightBitCounterArray, Int8PtrTy) + : Constant::getNullValue(Int8PtrTy), + IRB.CreatePointerCast(ModuleName, Int8PtrTy)}); + + appendToGlobalCtors(M, CtorFunc, SanCtorAndDtorPriority); + } + + return true; +} + +// True if block has successors and it dominates all of them. +static bool isFullDominator(const BasicBlock *BB, const DominatorTree *DT) { + if (succ_begin(BB) == succ_end(BB)) + return false; + + for (const BasicBlock *SUCC : make_range(succ_begin(BB), succ_end(BB))) { + if (!DT->dominates(BB, SUCC)) + return false; + } + + return true; +} - appendToGlobalCtors(M, CtorFunc, kSanCtorAndDtorPriority); +// True if block has predecessors and it postdominates all of them. +static bool isFullPostDominator(const BasicBlock *BB, + const PostDominatorTree *PDT) { + if (pred_begin(BB) == pred_end(BB)) + return false; + + for (const BasicBlock *PRED : make_range(pred_begin(BB), pred_end(BB))) { + if (!PDT->dominates(BB, PRED)) + return false; + } return true; } +static bool shouldInstrumentBlock(const Function& F, const BasicBlock *BB, const DominatorTree *DT, + const PostDominatorTree *PDT) { + if (!ClPruneBlocks || &F.getEntryBlock() == BB) + return true; + + return !(isFullDominator(BB, DT) || isFullPostDominator(BB, PDT)); +} + bool SanitizerCoverageModule::runOnFunction(Function &F) { - if (F.empty()) return false; + if (F.empty()) + return false; if (F.getName().find(".module_ctor") != std::string::npos) - return false; // Should not instrument sanitizer init functions. + return false; // Should not instrument sanitizer init functions. // Don't instrument functions using SEH for now. Splitting basic blocks like // we do for coverage breaks WinEHPrepare. // FIXME: Remove this when SEH no longer uses landingpad pattern matching. @@ -299,12 +363,19 @@ bool SanitizerCoverageModule::runOnFunction(Function &F) { return false; if (Options.CoverageType >= SanitizerCoverageOptions::SCK_Edge) SplitAllCriticalEdges(F); - SmallVector<Instruction*, 8> IndirCalls; - SmallVector<BasicBlock*, 16> AllBlocks; - SmallVector<Instruction*, 8> CmpTraceTargets; - SmallVector<Instruction*, 8> SwitchTraceTargets; + SmallVector<Instruction *, 8> IndirCalls; + SmallVector<BasicBlock *, 16> BlocksToInstrument; + SmallVector<Instruction *, 8> CmpTraceTargets; + SmallVector<Instruction *, 8> SwitchTraceTargets; + + const DominatorTree *DT = + &getAnalysis<DominatorTreeWrapperPass>(F).getDomTree(); + const PostDominatorTree *PDT = + &getAnalysis<PostDominatorTreeWrapperPass>(F).getPostDomTree(); + for (auto &BB : F) { - AllBlocks.push_back(&BB); + if (shouldInstrumentBlock(F, &BB, DT, PDT)) + BlocksToInstrument.push_back(&BB); for (auto &Inst : BB) { if (Options.IndirectCalls) { CallSite CS(&Inst); @@ -319,7 +390,8 @@ bool SanitizerCoverageModule::runOnFunction(Function &F) { } } } - InjectCoverage(F, AllBlocks); + + InjectCoverage(F, BlocksToInstrument); InjectCoverageForIndirectCalls(F, IndirCalls); InjectTraceForCmp(F, CmpTraceTargets); InjectTraceForSwitch(F, SwitchTraceTargets); @@ -346,28 +418,34 @@ bool SanitizerCoverageModule::InjectCoverage(Function &F, // On every indirect call we call a run-time function // __sanitizer_cov_indir_call* with two parameters: // - callee address, -// - global cache array that contains kCacheSize pointers (zero-initialized). +// - global cache array that contains CacheSize pointers (zero-initialized). // The cache is used to speed up recording the caller-callee pairs. // The address of the caller is passed implicitly via caller PC. -// kCacheSize is encoded in the name of the run-time function. +// CacheSize is encoded in the name of the run-time function. void SanitizerCoverageModule::InjectCoverageForIndirectCalls( Function &F, ArrayRef<Instruction *> IndirCalls) { - if (IndirCalls.empty()) return; - const int kCacheSize = 16; - const int kCacheAlignment = 64; // Align for better performance. - Type *Ty = ArrayType::get(IntptrTy, kCacheSize); + if (IndirCalls.empty()) + return; + const int CacheSize = 16; + const int CacheAlignment = 64; // Align for better performance. + Type *Ty = ArrayType::get(IntptrTy, CacheSize); for (auto I : IndirCalls) { IRBuilder<> IRB(I); CallSite CS(I); Value *Callee = CS.getCalledValue(); - if (isa<InlineAsm>(Callee)) continue; + if (isa<InlineAsm>(Callee)) + continue; GlobalVariable *CalleeCache = new GlobalVariable( *F.getParent(), Ty, false, GlobalValue::PrivateLinkage, Constant::getNullValue(Ty), "__sancov_gen_callee_cache"); - CalleeCache->setAlignment(kCacheAlignment); - IRB.CreateCall(SanCovIndirCallFunction, - {IRB.CreatePointerCast(Callee, IntptrTy), - IRB.CreatePointerCast(CalleeCache, IntptrTy)}); + CalleeCache->setAlignment(CacheAlignment); + if (Options.TracePC) + IRB.CreateCall(SanCovTracePCIndir, + IRB.CreatePointerCast(Callee, IntptrTy)); + else + IRB.CreateCall(SanCovIndirCallFunction, + {IRB.CreatePointerCast(Callee, IntptrTy), + IRB.CreatePointerCast(CalleeCache, IntptrTy)}); } } @@ -376,7 +454,7 @@ void SanitizerCoverageModule::InjectCoverageForIndirectCalls( // {NumCases, ValueSizeInBits, Case0Value, Case1Value, Case2Value, ... }) void SanitizerCoverageModule::InjectTraceForSwitch( - Function &F, ArrayRef<Instruction *> SwitchTraceTargets) { + Function &, ArrayRef<Instruction *> SwitchTraceTargets) { for (auto I : SwitchTraceTargets) { if (SwitchInst *SI = dyn_cast<SwitchInst>(I)) { IRBuilder<> IRB(I); @@ -391,7 +469,7 @@ void SanitizerCoverageModule::InjectTraceForSwitch( if (Cond->getType()->getScalarSizeInBits() < Int64Ty->getScalarSizeInBits()) Cond = IRB.CreateIntCast(Cond, Int64Ty, false); - for (auto It: SI->cases()) { + for (auto It : SI->cases()) { Constant *C = It.getCaseValue(); if (C->getType()->getScalarSizeInBits() < Int64Ty->getScalarSizeInBits()) @@ -409,15 +487,15 @@ void SanitizerCoverageModule::InjectTraceForSwitch( } } - void SanitizerCoverageModule::InjectTraceForCmp( - Function &F, ArrayRef<Instruction *> CmpTraceTargets) { + Function &, ArrayRef<Instruction *> CmpTraceTargets) { for (auto I : CmpTraceTargets) { if (ICmpInst *ICMP = dyn_cast<ICmpInst>(I)) { IRBuilder<> IRB(ICMP); Value *A0 = ICMP->getOperand(0); Value *A1 = ICMP->getOperand(1); - if (!A0->getType()->isIntegerTy()) continue; + if (!A0->getType()->isIntegerTy()) + continue; uint64_t TypeSize = DL->getTypeStoreSizeInBits(A0->getType()); // __sanitizer_cov_trace_cmp((type_size << 32) | predicate, A0, A1); IRB.CreateCall( @@ -430,8 +508,8 @@ void SanitizerCoverageModule::InjectTraceForCmp( } void SanitizerCoverageModule::SetNoSanitizeMetadata(Instruction *I) { - I->setMetadata( - I->getModule()->getMDKindID("nosanitize"), MDNode::get(*C, None)); + I->setMetadata(I->getModule()->getMDKindID("nosanitize"), + MDNode::get(*C, None)); } void SanitizerCoverageModule::InjectCoverageAtBlock(Function &F, BasicBlock &BB, @@ -448,7 +526,7 @@ void SanitizerCoverageModule::InjectCoverageAtBlock(Function &F, BasicBlock &BB, bool IsEntryBB = &BB == &F.getEntryBlock(); DebugLoc EntryLoc; if (IsEntryBB) { - if (auto SP = getDISubprogram(&F)) + if (auto SP = F.getSubprogram()) EntryLoc = DebugLoc::get(SP->getScopeLine(), 0, SP); // Keep static allocas and llvm.localescape calls in the entry block. Even // if we aren't splitting the block, it's nice for allocas to be before @@ -465,16 +543,20 @@ void SanitizerCoverageModule::InjectCoverageAtBlock(Function &F, BasicBlock &BB, ConstantInt::get(IntptrTy, (1 + NumberOfInstrumentedBlocks()) * 4)); Type *Int32PtrTy = PointerType::getUnqual(IRB.getInt32Ty()); GuardP = IRB.CreateIntToPtr(GuardP, Int32PtrTy); - if (Options.TraceBB) { + if (Options.TracePC) { + IRB.CreateCall(SanCovTracePC); // gets the PC using GET_CALLER_PC. + IRB.CreateCall(EmptyAsm, {}); // Avoids callback merge. + } else if (Options.TraceBB) { IRB.CreateCall(IsEntryBB ? SanCovTraceEnter : SanCovTraceBB, GuardP); } else if (UseCalls) { IRB.CreateCall(SanCovWithCheckFunction, GuardP); } else { LoadInst *Load = IRB.CreateLoad(GuardP); - Load->setAtomic(Monotonic); + Load->setAtomic(AtomicOrdering::Monotonic); Load->setAlignment(4); SetNoSanitizeMetadata(Load); - Value *Cmp = IRB.CreateICmpSGE(Constant::getNullValue(Load->getType()), Load); + Value *Cmp = + IRB.CreateICmpSGE(Constant::getNullValue(Load->getType()), Load); Instruction *Ins = SplitBlockAndInsertIfThen( Cmp, &*IP, false, MDBuilder(*C).createBranchWeights(1, 100000)); IRB.SetInsertPoint(Ins); @@ -499,9 +581,16 @@ void SanitizerCoverageModule::InjectCoverageAtBlock(Function &F, BasicBlock &BB, } char SanitizerCoverageModule::ID = 0; -INITIALIZE_PASS(SanitizerCoverageModule, "sancov", - "SanitizerCoverage: TODO." - "ModulePass", false, false) +INITIALIZE_PASS_BEGIN(SanitizerCoverageModule, "sancov", + "SanitizerCoverage: TODO." + "ModulePass", + false, false) +INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) +INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass) +INITIALIZE_PASS_END(SanitizerCoverageModule, "sancov", + "SanitizerCoverage: TODO." + "ModulePass", + false, false) ModulePass *llvm::createSanitizerCoverageModulePass( const SanitizerCoverageOptions &Options) { return new SanitizerCoverageModule(Options); |