llvm/lib/Transforms/Instrumentation/BoundsChecking.cpp

   1 //===- BoundsChecking.cpp - Instrumentation for run-time bounds checking --===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "llvm/Transforms/Instrumentation/BoundsChecking.h"
  10 #include "llvm/ADT/Statistic.h"
  11 #include "llvm/ADT/StringRef.h"
  12 #include "llvm/ADT/Twine.h"
  13 #include "llvm/Analysis/MemoryBuiltins.h"
  14 #include "llvm/Analysis/ScalarEvolution.h"
  15 #include "llvm/Analysis/TargetFolder.h"
  16 #include "llvm/Analysis/TargetLibraryInfo.h"
  17 #include "llvm/IR/BasicBlock.h"
  18 #include "llvm/IR/Constants.h"
  19 #include "llvm/IR/DataLayout.h"
  20 #include "llvm/IR/Function.h"
  21 #include "llvm/IR/IRBuilder.h"
  22 #include "llvm/IR/InstIterator.h"
  23 #include "llvm/IR/Instruction.h"
  24 #include "llvm/IR/Instructions.h"
  25 #include "llvm/IR/Intrinsics.h"
  26 #include "llvm/IR/Value.h"
  27 #include "llvm/Support/Casting.h"
  28 #include "llvm/Support/CommandLine.h"
  29 #include "llvm/Support/Debug.h"
  30 #include "llvm/Support/raw_ostream.h"
  31 #include <utility>
  32
  33 using namespace llvm;
  34
  35 #define DEBUG_TYPE "bounds-checking"
  36
  37 static cl::opt<bool> SingleTrapBB("bounds-checking-single-trap",
  38                                   cl::desc("Use one trap block per function"));
  39
  40 STATISTIC(ChecksAdded, "Bounds checks added");
  41 STATISTIC(ChecksSkipped, "Bounds checks skipped");
  42 STATISTIC(ChecksUnable, "Bounds checks unable to add");
  43
  44 class BuilderTy : public IRBuilder<TargetFolder> {
  45 public:
  46   BuilderTy(BasicBlock *TheBB, BasicBlock::iterator IP, TargetFolder Folder)
  47       : IRBuilder<TargetFolder>(TheBB, IP, Folder) {
  48     SetNoSanitizeMetadata();
  49   }
  50 };
  51
  52 /// Gets the conditions under which memory accessing instructions will overflow.
  53 ///
  54 /// \p Ptr is the pointer that will be read/written, and \p InstVal is either
  55 /// the result from the load or the value being stored. It is used to determine
  56 /// the size of memory block that is touched.
  57 ///
  58 /// Returns the condition under which the access will overflow.
  59 static Value *getBoundsCheckCond(Value *Ptr, Value *InstVal,
  60                                  const DataLayout &DL, TargetLibraryInfo &TLI,
  61                                  ObjectSizeOffsetEvaluator &ObjSizeEval,
  62                                  BuilderTy &IRB, ScalarEvolution &SE) {
  63   TypeSize NeededSize = DL.getTypeStoreSize(InstVal->getType());
  64   LLVM_DEBUG(dbgs() << "Instrument " << *Ptr << " for " << Twine(NeededSize)
  65                     << " bytes\n");
  66
  67   SizeOffsetValue SizeOffset = ObjSizeEval.compute(Ptr);
  68
  69   if (!SizeOffset.bothKnown()) {
  70     ++ChecksUnable;
  71     return nullptr;
  72   }
  73
  74   Value *Size = SizeOffset.Size;
  75   Value *Offset = SizeOffset.Offset;
  76   ConstantInt *SizeCI = dyn_cast<ConstantInt>(Size);
  77
  78   Type *IndexTy = DL.getIndexType(Ptr->getType());
  79   Value *NeededSizeVal = IRB.CreateTypeSize(IndexTy, NeededSize);
  80
  81   auto SizeRange = SE.getUnsignedRange(SE.getSCEV(Size));
  82   auto OffsetRange = SE.getUnsignedRange(SE.getSCEV(Offset));
  83   auto NeededSizeRange = SE.getUnsignedRange(SE.getSCEV(NeededSizeVal));
  84
  85   // three checks are required to ensure safety:
  86   // . Offset >= 0  (since the offset is given from the base ptr)
  87   // . Size >= Offset  (unsigned)
  88   // . Size - Offset >= NeededSize  (unsigned)
  89   //
  90   // optimization: if Size >= 0 (signed), skip 1st check
  91   // FIXME: add NSW/NUW here?  -- we dont care if the subtraction overflows
  92   Value *ObjSize = IRB.CreateSub(Size, Offset);
  93   Value *Cmp2 = SizeRange.getUnsignedMin().uge(OffsetRange.getUnsignedMax())
  94                     ? ConstantInt::getFalse(Ptr->getContext())
  95                     : IRB.CreateICmpULT(Size, Offset);
  96   Value *Cmp3 = SizeRange.sub(OffsetRange)
  97                         .getUnsignedMin()
  98                         .uge(NeededSizeRange.getUnsignedMax())
  99                     ? ConstantInt::getFalse(Ptr->getContext())
 100                     : IRB.CreateICmpULT(ObjSize, NeededSizeVal);
 101   Value *Or = IRB.CreateOr(Cmp2, Cmp3);
 102   if ((!SizeCI || SizeCI->getValue().slt(0)) &&
 103       !SizeRange.getSignedMin().isNonNegative()) {
 104     Value *Cmp1 = IRB.CreateICmpSLT(Offset, ConstantInt::get(IndexTy, 0));
 105     Or = IRB.CreateOr(Cmp1, Or);
 106   }
 107
 108   return Or;
 109 }
 110
 111 static CallInst *InsertTrap(BuilderTy &IRB, bool DebugTrapBB) {
 112   if (!DebugTrapBB)
 113     return IRB.CreateIntrinsic(Intrinsic::trap, {}, {});
 114   // FIXME: Ideally we would use the SanitizerHandler::OutOfBounds constant.
 115   return IRB.CreateIntrinsic(
 116       Intrinsic::ubsantrap, {},
 117       ConstantInt::get(IRB.getInt8Ty(),
 118                        IRB.GetInsertBlock()->getParent()->size()));
 119 }
 120
 121 static CallInst *InsertCall(BuilderTy &IRB, bool MayReturn, StringRef Name) {
 122   Function *Fn = IRB.GetInsertBlock()->getParent();
 123   LLVMContext &Ctx = Fn->getContext();
 124   llvm::AttrBuilder B(Ctx);
 125   B.addAttribute(llvm::Attribute::NoUnwind);
 126   if (!MayReturn)
 127     B.addAttribute(llvm::Attribute::NoReturn);
 128   FunctionCallee Callee = Fn->getParent()->getOrInsertFunction(
 129       Name,
 130       llvm::AttributeList::get(Ctx, llvm::AttributeList::FunctionIndex, B),
 131       Type::getVoidTy(Ctx));
 132   return IRB.CreateCall(Callee);
 133 }
 134
 135 /// Adds run-time bounds checks to memory accessing instructions.
 136 ///
 137 /// \p Or is the condition that should guard the trap.
 138 ///
 139 /// \p GetTrapBB is a callable that returns the trap BB to use on failure.
 140 template <typename GetTrapBBT>
 141 static void insertBoundsCheck(Value *Or, BuilderTy &IRB, GetTrapBBT GetTrapBB) {
 142   // check if the comparison is always false
 143   ConstantInt *C = dyn_cast_or_null<ConstantInt>(Or);
 144   if (C) {
 145     ++ChecksSkipped;
 146     // If non-zero, nothing to do.
 147     if (!C->getZExtValue())
 148       return;
 149   }
 150   ++ChecksAdded;
 151
 152   BasicBlock::iterator SplitI = IRB.GetInsertPoint();
 153   BasicBlock *OldBB = SplitI->getParent();
 154   BasicBlock *Cont = OldBB->splitBasicBlock(SplitI);
 155   OldBB->getTerminator()->eraseFromParent();
 156
 157   BasicBlock *TrapBB = GetTrapBB(IRB, Cont);
 158
 159   if (C) {
 160     // If we have a constant zero, unconditionally branch.
 161     // FIXME: We should really handle this differently to bypass the splitting
 162     // the block.
 163     BranchInst::Create(TrapBB, OldBB);
 164     return;
 165   }
 166
 167   // Create the conditional branch.
 168   BranchInst::Create(TrapBB, Cont, Or, OldBB);
 169 }
 170
 171 static std::string
 172 getRuntimeCallName(const BoundsCheckingPass::Options::Runtime &Opts) {
 173   std::string Name = "__ubsan_handle_local_out_of_bounds";
 174   if (Opts.MinRuntime)
 175     Name += "_minimal";
 176   if (!Opts.MayReturn)
 177     Name += "_abort";
 178   return Name;
 179 }
 180
 181 static bool addBoundsChecking(Function &F, TargetLibraryInfo &TLI,
 182                               ScalarEvolution &SE,
 183                               const BoundsCheckingPass::Options &Opts) {
 184   if (F.hasFnAttribute(Attribute::NoSanitizeBounds))
 185     return false;
 186
 187   const DataLayout &DL = F.getDataLayout();
 188   ObjectSizeOpts EvalOpts;
 189   EvalOpts.RoundToAlign = true;
 190   EvalOpts.EvalMode = ObjectSizeOpts::Mode::ExactUnderlyingSizeAndOffset;
 191   ObjectSizeOffsetEvaluator ObjSizeEval(DL, &TLI, F.getContext(), EvalOpts);
 192
 193   // check HANDLE_MEMORY_INST in include/llvm/Instruction.def for memory
 194   // touching instructions
 195   SmallVector<std::pair<Instruction *, Value *>, 4> TrapInfo;
 196   for (Instruction &I : instructions(F)) {
 197     Value *Or = nullptr;
 198     BuilderTy IRB(I.getParent(), BasicBlock::iterator(&I), TargetFolder(DL));
 199     if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {
 200       if (!LI->isVolatile())
 201         Or = getBoundsCheckCond(LI->getPointerOperand(), LI, DL, TLI,
 202                                 ObjSizeEval, IRB, SE);
 203     } else if (StoreInst *SI = dyn_cast<StoreInst>(&I)) {
 204       if (!SI->isVolatile())
 205         Or = getBoundsCheckCond(SI->getPointerOperand(), SI->getValueOperand(),
 206                                 DL, TLI, ObjSizeEval, IRB, SE);
 207     } else if (AtomicCmpXchgInst *AI = dyn_cast<AtomicCmpXchgInst>(&I)) {
 208       if (!AI->isVolatile())
 209         Or =
 210             getBoundsCheckCond(AI->getPointerOperand(), AI->getCompareOperand(),
 211                                DL, TLI, ObjSizeEval, IRB, SE);
 212     } else if (AtomicRMWInst *AI = dyn_cast<AtomicRMWInst>(&I)) {
 213       if (!AI->isVolatile())
 214         Or = getBoundsCheckCond(AI->getPointerOperand(), AI->getValOperand(),
 215                                 DL, TLI, ObjSizeEval, IRB, SE);
 216     }
 217     if (Or) {
 218       if (Opts.GuardKind) {
 219         llvm::Value *Allow = IRB.CreateIntrinsic(
 220             IRB.getInt1Ty(), Intrinsic::allow_ubsan_check,
 221             {llvm::ConstantInt::getSigned(IRB.getInt8Ty(), *Opts.GuardKind)});
 222         Or = IRB.CreateAnd(Or, Allow);
 223       }
 224       TrapInfo.push_back(std::make_pair(&I, Or));
 225     }
 226   }
 227
 228   std::string Name;
 229   if (Opts.Rt)
 230     Name = getRuntimeCallName(*Opts.Rt);
 231
 232   // Create a trapping basic block on demand using a callback. Depending on
 233   // flags, this will either create a single block for the entire function or
 234   // will create a fresh block every time it is called.
 235   BasicBlock *ReuseTrapBB = nullptr;
 236   auto GetTrapBB = [&ReuseTrapBB, &Opts, &Name](BuilderTy &IRB,
 237                                                 BasicBlock *Cont) {
 238     Function *Fn = IRB.GetInsertBlock()->getParent();
 239     auto DebugLoc = IRB.getCurrentDebugLocation();
 240     IRBuilder<>::InsertPointGuard Guard(IRB);
 241
 242     // Create a trapping basic block on demand using a callback. Depending on
 243     // flags, this will either create a single block for the entire function or
 244     // will create a fresh block every time it is called.
 245     if (ReuseTrapBB)
 246       return ReuseTrapBB;
 247
 248     BasicBlock *TrapBB = BasicBlock::Create(Fn->getContext(), "trap", Fn);
 249     IRB.SetInsertPoint(TrapBB);
 250
 251     bool DebugTrapBB = !Opts.Merge;
 252     CallInst *TrapCall = Opts.Rt ? InsertCall(IRB, Opts.Rt->MayReturn, Name)
 253                                  : InsertTrap(IRB, DebugTrapBB);
 254     if (DebugTrapBB)
 255       TrapCall->addFnAttr(llvm::Attribute::NoMerge);
 256
 257     TrapCall->setDoesNotThrow();
 258     TrapCall->setDebugLoc(DebugLoc);
 259
 260     bool MayReturn = Opts.Rt && Opts.Rt->MayReturn;
 261     if (MayReturn) {
 262       IRB.CreateBr(Cont);
 263     } else {
 264       TrapCall->setDoesNotReturn();
 265       IRB.CreateUnreachable();
 266     }
 267
 268     if (!MayReturn && SingleTrapBB && !DebugTrapBB)
 269       ReuseTrapBB = TrapBB;
 270
 271     return TrapBB;
 272   };
 273
 274   for (const auto &Entry : TrapInfo) {
 275     Instruction *Inst = Entry.first;
 276     BuilderTy IRB(Inst->getParent(), BasicBlock::iterator(Inst), TargetFolder(DL));
 277     insertBoundsCheck(Entry.second, IRB, GetTrapBB);
 278   }
 279
 280   return !TrapInfo.empty();
 281 }
 282
 283 PreservedAnalyses BoundsCheckingPass::run(Function &F, FunctionAnalysisManager &AM) {
 284   auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
 285   auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F);
 286
 287   if (!addBoundsChecking(F, TLI, SE, Opts))
 288     return PreservedAnalyses::all();
 289
 290   return PreservedAnalyses::none();
 291 }
 292
 293 void BoundsCheckingPass::printPipeline(
 294     raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
 295   static_cast<PassInfoMixin<BoundsCheckingPass> *>(this)->printPipeline(
 296       OS, MapClassName2PassName);
 297   OS << "<";
 298   if (Opts.Rt) {
 299     if (Opts.Rt->MinRuntime)
 300       OS << "min-";
 301     OS << "rt";
 302     if (!Opts.Rt->MayReturn)
 303       OS << "-abort";
 304   } else {
 305     OS << "trap";
 306   }
 307   if (Opts.Merge)
 308     OS << ";merge";
 309   if (Opts.GuardKind)
 310     OS << ";guard=" << static_cast<int>(*Opts.GuardKind);
 311   OS << ">";
 312 }