321 lines · 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-exception6//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 33using namespace llvm;34 35#define DEBUG_TYPE "bounds-checking"36 37static cl::opt<bool> SingleTrapBB("bounds-checking-single-trap",38 cl::desc("Use one trap block per function"));39 40STATISTIC(ChecksAdded, "Bounds checks added");41STATISTIC(ChecksSkipped, "Bounds checks skipped");42STATISTIC(ChecksUnable, "Bounds checks unable to add");43 44class BuilderTy : public IRBuilder<TargetFolder> {45public: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 either55/// the result from the load or the value being stored. It is used to determine56/// the size of memory block that is touched.57///58/// Returns the condition under which the access will overflow.59static 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 check91 // FIXME: add NSW/NUW here? -- we dont care if the subtraction overflows92 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 111static CallInst *InsertTrap(BuilderTy &IRB, bool DebugTrapBB,112 std::optional<int8_t> GuardKind) {113 if (!DebugTrapBB)114 return IRB.CreateIntrinsic(Intrinsic::trap, {});115 116 return IRB.CreateIntrinsic(117 Intrinsic::ubsantrap,118 ConstantInt::get(IRB.getInt8Ty(),119 GuardKind.has_value()120 ? GuardKind.value()121 : IRB.GetInsertBlock()->getParent()->size()));122}123 124static CallInst *InsertCall(BuilderTy &IRB, bool MayReturn, StringRef Name) {125 Function *Fn = IRB.GetInsertBlock()->getParent();126 LLVMContext &Ctx = Fn->getContext();127 llvm::AttrBuilder B(Ctx);128 B.addAttribute(llvm::Attribute::NoUnwind);129 if (!MayReturn)130 B.addAttribute(llvm::Attribute::NoReturn);131 FunctionCallee Callee = Fn->getParent()->getOrInsertFunction(132 Name,133 llvm::AttributeList::get(Ctx, llvm::AttributeList::FunctionIndex, B),134 Type::getVoidTy(Ctx));135 return IRB.CreateCall(Callee);136}137 138/// Adds run-time bounds checks to memory accessing instructions.139///140/// \p Or is the condition that should guard the trap.141///142/// \p GetTrapBB is a callable that returns the trap BB to use on failure.143template <typename GetTrapBBT>144static void insertBoundsCheck(Value *Or, BuilderTy &IRB, GetTrapBBT GetTrapBB) {145 // check if the comparison is always false146 ConstantInt *C = dyn_cast_or_null<ConstantInt>(Or);147 if (C) {148 ++ChecksSkipped;149 // If non-zero, nothing to do.150 if (!C->getZExtValue())151 return;152 }153 ++ChecksAdded;154 155 BasicBlock::iterator SplitI = IRB.GetInsertPoint();156 BasicBlock *OldBB = SplitI->getParent();157 BasicBlock *Cont = OldBB->splitBasicBlock(SplitI);158 OldBB->getTerminator()->eraseFromParent();159 160 BasicBlock *TrapBB = GetTrapBB(IRB, Cont);161 162 if (C) {163 // If we have a constant zero, unconditionally branch.164 // FIXME: We should really handle this differently to bypass the splitting165 // the block.166 BranchInst::Create(TrapBB, OldBB);167 return;168 }169 170 // Create the conditional branch.171 BranchInst::Create(TrapBB, Cont, Or, OldBB);172}173 174static std::string175getRuntimeCallName(const BoundsCheckingPass::Options::Runtime &Opts) {176 std::string Name = "__ubsan_handle_local_out_of_bounds";177 if (Opts.MinRuntime)178 Name += "_minimal";179 if (!Opts.MayReturn)180 Name += "_abort";181 else if (Opts.HandlerPreserveAllRegs)182 Name += "_preserve";183 return Name;184}185 186static bool addBoundsChecking(Function &F, TargetLibraryInfo &TLI,187 ScalarEvolution &SE,188 const BoundsCheckingPass::Options &Opts) {189 if (F.hasFnAttribute(Attribute::NoSanitizeBounds))190 return false;191 192 const DataLayout &DL = F.getDataLayout();193 ObjectSizeOpts EvalOpts;194 EvalOpts.RoundToAlign = true;195 EvalOpts.EvalMode = ObjectSizeOpts::Mode::ExactUnderlyingSizeAndOffset;196 ObjectSizeOffsetEvaluator ObjSizeEval(DL, &TLI, F.getContext(), EvalOpts);197 198 // check HANDLE_MEMORY_INST in include/llvm/Instruction.def for memory199 // touching instructions200 SmallVector<std::pair<Instruction *, Value *>, 4> TrapInfo;201 for (Instruction &I : instructions(F)) {202 Value *Or = nullptr;203 BuilderTy IRB(I.getParent(), BasicBlock::iterator(&I), TargetFolder(DL));204 if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {205 if (!LI->isVolatile())206 Or = getBoundsCheckCond(LI->getPointerOperand(), LI, DL, TLI,207 ObjSizeEval, IRB, SE);208 } else if (StoreInst *SI = dyn_cast<StoreInst>(&I)) {209 if (!SI->isVolatile())210 Or = getBoundsCheckCond(SI->getPointerOperand(), SI->getValueOperand(),211 DL, TLI, ObjSizeEval, IRB, SE);212 } else if (AtomicCmpXchgInst *AI = dyn_cast<AtomicCmpXchgInst>(&I)) {213 if (!AI->isVolatile())214 Or =215 getBoundsCheckCond(AI->getPointerOperand(), AI->getCompareOperand(),216 DL, TLI, ObjSizeEval, IRB, SE);217 } else if (AtomicRMWInst *AI = dyn_cast<AtomicRMWInst>(&I)) {218 if (!AI->isVolatile())219 Or = getBoundsCheckCond(AI->getPointerOperand(), AI->getValOperand(),220 DL, TLI, ObjSizeEval, IRB, SE);221 }222 if (Or) {223 if (Opts.GuardKind) {224 llvm::Value *Allow = IRB.CreateIntrinsic(225 IRB.getInt1Ty(), Intrinsic::allow_ubsan_check,226 {llvm::ConstantInt::getSigned(IRB.getInt8Ty(), *Opts.GuardKind)});227 Or = IRB.CreateAnd(Or, Allow);228 }229 TrapInfo.push_back(std::make_pair(&I, Or));230 }231 }232 233 std::string Name;234 if (Opts.Rt)235 Name = getRuntimeCallName(*Opts.Rt);236 237 // Create a trapping basic block on demand using a callback. Depending on238 // flags, this will either create a single block for the entire function or239 // will create a fresh block every time it is called.240 BasicBlock *ReuseTrapBB = nullptr;241 auto GetTrapBB = [&ReuseTrapBB, &Opts, &Name](BuilderTy &IRB,242 BasicBlock *Cont) {243 Function *Fn = IRB.GetInsertBlock()->getParent();244 auto DebugLoc = IRB.getCurrentDebugLocation();245 IRBuilder<>::InsertPointGuard Guard(IRB);246 247 // Create a trapping basic block on demand using a callback. Depending on248 // flags, this will either create a single block for the entire function or249 // will create a fresh block every time it is called.250 if (ReuseTrapBB)251 return ReuseTrapBB;252 253 BasicBlock *TrapBB = BasicBlock::Create(Fn->getContext(), "trap", Fn);254 IRB.SetInsertPoint(TrapBB);255 256 bool DebugTrapBB = !Opts.Merge;257 CallInst *TrapCall = Opts.Rt ? InsertCall(IRB, Opts.Rt->MayReturn, Name)258 : InsertTrap(IRB, DebugTrapBB, Opts.GuardKind);259 if (DebugTrapBB)260 TrapCall->addFnAttr(llvm::Attribute::NoMerge);261 262 TrapCall->setDoesNotThrow();263 TrapCall->setDebugLoc(DebugLoc);264 265 bool MayReturn = Opts.Rt && Opts.Rt->MayReturn;266 if (MayReturn) {267 IRB.CreateBr(Cont);268 } else {269 TrapCall->setDoesNotReturn();270 IRB.CreateUnreachable();271 }272 // The preserve-all logic is somewhat duplicated in CGExpr.cpp for273 // local-bounds. Make sure to change that too.274 if (Opts.Rt && Opts.Rt->HandlerPreserveAllRegs && MayReturn)275 TrapCall->setCallingConv(CallingConv::PreserveAll);276 if (!MayReturn && SingleTrapBB && !DebugTrapBB)277 ReuseTrapBB = TrapBB;278 279 return TrapBB;280 };281 282 for (const auto &Entry : TrapInfo) {283 Instruction *Inst = Entry.first;284 BuilderTy IRB(Inst->getParent(), BasicBlock::iterator(Inst), TargetFolder(DL));285 insertBoundsCheck(Entry.second, IRB, GetTrapBB);286 }287 288 return !TrapInfo.empty();289}290 291PreservedAnalyses BoundsCheckingPass::run(Function &F, FunctionAnalysisManager &AM) {292 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);293 auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F);294 295 if (!addBoundsChecking(F, TLI, SE, Opts))296 return PreservedAnalyses::all();297 298 return PreservedAnalyses::none();299}300 301void BoundsCheckingPass::printPipeline(302 raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {303 static_cast<PassInfoMixin<BoundsCheckingPass> *>(this)->printPipeline(304 OS, MapClassName2PassName);305 OS << "<";306 if (Opts.Rt) {307 if (Opts.Rt->MinRuntime)308 OS << "min-";309 OS << "rt";310 if (!Opts.Rt->MayReturn)311 OS << "-abort";312 } else {313 OS << "trap";314 }315 if (Opts.Merge)316 OS << ";merge";317 if (Opts.GuardKind)318 OS << ";guard=" << static_cast<int>(*Opts.GuardKind);319 OS << ">";320}321