lib/Transforms/Instrumentation/SanitizerCoverage.cpp

   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 boolean variable with the same linkage
  14 // as the function and inject this code into the entry block (CoverageLevel=1)
  15 // or all blocks (CoverageLevel>=2):
  16 // if (*Guard) {
  17 //    __sanitizer_cov();
  18 //    *Guard = 1;
  19 // }
  20 // The accesses to Guard are atomic. The rest of the logic is
  21 // in __sanitizer_cov (it's fine to call it more than once).
  22 //
  23 // With CoverageLevel>=3 we also split critical edges this effectively
  24 // instrumenting all edges.
  25 //
  26 // CoverageLevel>=4 add indirect call profiling implented as a function call.
  27 //
  28 // This coverage implementation provides very limited data:
  29 // it only tells if a given function (block) was ever executed. No counters.
  30 // But for many use cases this is what we need and the added slowdown small.
  31 //
  32 //===----------------------------------------------------------------------===//
  33
  34 #include "llvm/Transforms/Instrumentation.h"
  35 #include "llvm/ADT/ArrayRef.h"
  36 #include "llvm/ADT/SmallVector.h"
  37 #include "llvm/IR/CallSite.h"
  38 #include "llvm/IR/DataLayout.h"
  39 #include "llvm/IR/Function.h"
  40 #include "llvm/IR/IRBuilder.h"
  41 #include "llvm/IR/LLVMContext.h"
  42 #include "llvm/IR/MDBuilder.h"
  43 #include "llvm/IR/Module.h"
  44 #include "llvm/IR/Type.h"
  45 #include "llvm/Support/CommandLine.h"
  46 #include "llvm/Support/Debug.h"
  47 #include "llvm/Support/raw_ostream.h"
  48 #include "llvm/Transforms/Scalar.h"
  49 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  50 #include "llvm/Transforms/Utils/ModuleUtils.h"
  51
  52 using namespace llvm;
  53
  54 #define DEBUG_TYPE "sancov"
  55
  56 static const char *const kSanCovModuleInitName = "__sanitizer_cov_module_init";
  57 static const char *const kSanCovName = "__sanitizer_cov";
  58 static const char *const kSanCovIndirCallName = "__sanitizer_cov_indir_call16";
  59 static const char *const kSanCovModuleCtorName = "sancov.module_ctor";
  60 static const uint64_t    kSanCtorAndDtorPriority = 1;
  61
  62 static cl::opt<int> ClCoverageLevel("sanitizer-coverage-level",
  63        cl::desc("Sanitizer Coverage. 0: none, 1: entry block, 2: all blocks, "
  64                 "3: all blocks and critical edges, "
  65                 "4: above plus indirect calls"),
  66        cl::Hidden, cl::init(0));
  67
  68 static cl::opt<int> ClCoverageBlockThreshold(
  69     "sanitizer-coverage-block-threshold",
  70     cl::desc("Add coverage instrumentation only to the entry block if there "
  71              "are more than this number of blocks."),
  72     cl::Hidden, cl::init(1500));
  73
  74 namespace {
  75
  76 class SanitizerCoverageModule : public ModulePass {
  77  public:
  78   SanitizerCoverageModule(int CoverageLevel = 0)
  79        : ModulePass(ID),
  80          CoverageLevel(std::max(CoverageLevel, (int)ClCoverageLevel)) {
  81     initializeBreakCriticalEdgesPass(*PassRegistry::getPassRegistry());
  82   }
  83   bool runOnModule(Module &M) override;
  84   bool runOnFunction(Function &F);
  85   static char ID;  // Pass identification, replacement for typeid
  86   const char *getPassName() const override {
  87     return "SanitizerCoverageModule";
  88   }
  89
  90   void getAnalysisUsage(AnalysisUsage &AU) const override {
  91     if (CoverageLevel >= 3)
  92       AU.addRequiredID(BreakCriticalEdgesID);
  93     AU.addRequired<DataLayoutPass>();
  94   }
  95
  96  private:
  97   void InjectCoverageForIndirectCalls(Function &F,
  98                                       ArrayRef<Instruction *> IndirCalls);
  99   bool InjectCoverage(Function &F, ArrayRef<BasicBlock *> AllBlocks,
 100                       ArrayRef<Instruction *> IndirCalls);
 101   void InjectCoverageAtBlock(Function &F, BasicBlock &BB);
 102   Function *SanCovFunction;
 103   Function *SanCovIndirCallFunction;
 104   Function *SanCovModuleInit;
 105   Type *IntptrTy;
 106   LLVMContext *C;
 107
 108   int CoverageLevel;
 109 };
 110
 111 }  // namespace
 112
 113 static Function *checkInterfaceFunction(Constant *FuncOrBitcast) {
 114   if (Function *F = dyn_cast<Function>(FuncOrBitcast))
 115      return F;
 116   std::string Err;
 117   raw_string_ostream Stream(Err);
 118   Stream << "SanitizerCoverage interface function redefined: "
 119          << *FuncOrBitcast;
 120   report_fatal_error(Err);
 121 }
 122
 123 bool SanitizerCoverageModule::runOnModule(Module &M) {
 124   if (!CoverageLevel) return false;
 125   C = &(M.getContext());
 126   DataLayoutPass *DLP = &getAnalysis<DataLayoutPass>();
 127   IntptrTy = Type::getIntNTy(*C, DLP->getDataLayout().getPointerSizeInBits());
 128   Type *VoidTy = Type::getVoidTy(*C);
 129
 130   Function *CtorFunc =
 131       Function::Create(FunctionType::get(VoidTy, false),
 132                        GlobalValue::InternalLinkage, kSanCovModuleCtorName, &M);
 133   ReturnInst::Create(*C, BasicBlock::Create(*C, "", CtorFunc));
 134   appendToGlobalCtors(M, CtorFunc, kSanCtorAndDtorPriority);
 135
 136   SanCovFunction =
 137       checkInterfaceFunction(M.getOrInsertFunction(kSanCovName, VoidTy, NULL));
 138   SanCovIndirCallFunction = checkInterfaceFunction(M.getOrInsertFunction(
 139       kSanCovIndirCallName, VoidTy, IntptrTy, IntptrTy, NULL));
 140   SanCovModuleInit = checkInterfaceFunction(M.getOrInsertFunction(
 141       kSanCovModuleInitName, Type::getVoidTy(*C), IntptrTy, NULL));
 142   SanCovModuleInit->setLinkage(Function::ExternalLinkage);
 143
 144   for (auto &F : M)
 145     runOnFunction(F);
 146
 147   IRBuilder<> IRB(CtorFunc->getEntryBlock().getTerminator());
 148   IRB.CreateCall(SanCovModuleInit,
 149                  ConstantInt::get(IntptrTy, SanCovFunction->getNumUses()));
 150   return true;
 151 }
 152
 153 bool SanitizerCoverageModule::runOnFunction(Function &F) {
 154   if (F.empty()) return false;
 155   // For now instrument only functions that will also be asan-instrumented.
 156   if (!F.hasFnAttribute(Attribute::SanitizeAddress))
 157     return false;
 158   SmallVector<Instruction*, 8> IndirCalls;
 159   SmallVector<BasicBlock*, 16> AllBlocks;
 160   for (auto &BB : F) {
 161     AllBlocks.push_back(&BB);
 162     if (CoverageLevel >= 4)
 163       for (auto &Inst : BB) {
 164         CallSite CS(&Inst);
 165         if (CS && !CS.getCalledFunction())
 166           IndirCalls.push_back(&Inst);
 167       }
 168   }
 169   InjectCoverage(F, AllBlocks, IndirCalls);
 170   return true;
 171 }
 172
 173 bool
 174 SanitizerCoverageModule::InjectCoverage(Function &F,
 175                                         ArrayRef<BasicBlock *> AllBlocks,
 176                                         ArrayRef<Instruction *> IndirCalls) {
 177   if (!CoverageLevel) return false;
 178
 179   if (CoverageLevel == 1 ||
 180       (unsigned)ClCoverageBlockThreshold < AllBlocks.size()) {
 181     InjectCoverageAtBlock(F, F.getEntryBlock());
 182   } else {
 183     for (auto BB : AllBlocks)
 184       InjectCoverageAtBlock(F, *BB);
 185   }
 186   InjectCoverageForIndirectCalls(F, IndirCalls);
 187   return true;
 188 }
 189
 190 // On every indirect call we call a run-time function
 191 // __sanitizer_cov_indir_call* with two parameters:
 192 //   - callee address,
 193 //   - global cache array that contains kCacheSize pointers (zero-initialized).
 194 //     The cache is used to speed up recording the caller-callee pairs.
 195 // The address of the caller is passed implicitly via caller PC.
 196 // kCacheSize is encoded in the name of the run-time function.
 197 void SanitizerCoverageModule::InjectCoverageForIndirectCalls(
 198     Function &F, ArrayRef<Instruction *> IndirCalls) {
 199   if (IndirCalls.empty()) return;
 200   const int kCacheSize = 16;
 201   const int kCacheAlignment = 64;  // Align for better performance.
 202   Type *Ty = ArrayType::get(IntptrTy, kCacheSize);
 203   for (auto I : IndirCalls) {
 204     IRBuilder<> IRB(I);
 205     CallSite CS(I);
 206     Value *Callee = CS.getCalledValue();
 207     if (dyn_cast<InlineAsm>(Callee)) continue;
 208     GlobalVariable *CalleeCache = new GlobalVariable(
 209         *F.getParent(), Ty, false, GlobalValue::PrivateLinkage,
 210         Constant::getNullValue(Ty), "__sancov_gen_callee_cache");
 211     CalleeCache->setAlignment(kCacheAlignment);
 212     IRB.CreateCall2(SanCovIndirCallFunction,
 213                     IRB.CreatePointerCast(Callee, IntptrTy),
 214                     IRB.CreatePointerCast(CalleeCache, IntptrTy));
 215   }
 216 }
 217
 218 void SanitizerCoverageModule::InjectCoverageAtBlock(Function &F,
 219                                                     BasicBlock &BB) {
 220   BasicBlock::iterator IP = BB.getFirstInsertionPt(), BE = BB.end();
 221   // Skip static allocas at the top of the entry block so they don't become
 222   // dynamic when we split the block.  If we used our optimized stack layout,
 223   // then there will only be one alloca and it will come first.
 224   for (; IP != BE; ++IP) {
 225     AllocaInst *AI = dyn_cast<AllocaInst>(IP);
 226     if (!AI || !AI->isStaticAlloca())
 227       break;
 228   }
 229
 230   DebugLoc EntryLoc = &BB == &F.getEntryBlock()
 231                           ? IP->getDebugLoc().getFnDebugLoc(*C)
 232                           : IP->getDebugLoc();
 233   IRBuilder<> IRB(IP);
 234   IRB.SetCurrentDebugLocation(EntryLoc);
 235   Type *Int8Ty = IRB.getInt8Ty();
 236   GlobalVariable *Guard = new GlobalVariable(
 237       *F.getParent(), Int8Ty, false, GlobalValue::PrivateLinkage,
 238       Constant::getNullValue(Int8Ty), "__sancov_gen_cov_" + F.getName());
 239   LoadInst *Load = IRB.CreateLoad(Guard);
 240   Load->setAtomic(Monotonic);
 241   Load->setAlignment(1);
 242   Value *Cmp = IRB.CreateICmpEQ(Constant::getNullValue(Int8Ty), Load);
 243   Instruction *Ins = SplitBlockAndInsertIfThen(
 244       Cmp, IP, false, MDBuilder(*C).createBranchWeights(1, 100000));
 245   IRB.SetInsertPoint(Ins);
 246   IRB.SetCurrentDebugLocation(EntryLoc);
 247   // __sanitizer_cov gets the PC of the instruction using GET_CALLER_PC.
 248   IRB.CreateCall(SanCovFunction);
 249   StoreInst *Store = IRB.CreateStore(ConstantInt::get(Int8Ty, 1), Guard);
 250   Store->setAtomic(Monotonic);
 251   Store->setAlignment(1);
 252 }
 253
 254 char SanitizerCoverageModule::ID = 0;
 255 INITIALIZE_PASS(SanitizerCoverageModule, "sancov",
 256     "SanitizerCoverage: TODO."
 257     "ModulePass", false, false)
 258 ModulePass *llvm::createSanitizerCoverageModulePass(int CoverageLevel) {
 259   return new SanitizerCoverageModule(CoverageLevel);
 260 }