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:
BuilderTy(BasicBlock * TheBB,BasicBlock::iterator IP,TargetFolder Folder)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.
getBoundsCheckCond(Value * Ptr,Value * InstVal,const DataLayout & DL,TargetLibraryInfo & TLI,ObjectSizeOffsetEvaluator & ObjSizeEval,BuilderTy & IRB,ScalarEvolution & SE)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
InsertTrap(BuilderTy & IRB,bool DebugTrapBB,std::optional<int8_t> GuardKind)111 static 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
InsertCall(BuilderTy & IRB,bool MayReturn,StringRef Name)124 static 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.
143 template <typename GetTrapBBT>
insertBoundsCheck(Value * Or,BuilderTy & IRB,GetTrapBBT GetTrapBB)144 static void insertBoundsCheck(Value *Or, BuilderTy &IRB, GetTrapBBT GetTrapBB) {
145 // check if the comparison is always false
146 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 splitting
165 // 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
174 static std::string
getRuntimeCallName(const BoundsCheckingPass::Options::Runtime & Opts)175 getRuntimeCallName(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 return Name;
182 }
183
addBoundsChecking(Function & F,TargetLibraryInfo & TLI,ScalarEvolution & SE,const BoundsCheckingPass::Options & Opts)184 static bool addBoundsChecking(Function &F, TargetLibraryInfo &TLI,
185 ScalarEvolution &SE,
186 const BoundsCheckingPass::Options &Opts) {
187 if (F.hasFnAttribute(Attribute::NoSanitizeBounds))
188 return false;
189
190 const DataLayout &DL = F.getDataLayout();
191 ObjectSizeOpts EvalOpts;
192 EvalOpts.RoundToAlign = true;
193 EvalOpts.EvalMode = ObjectSizeOpts::Mode::ExactUnderlyingSizeAndOffset;
194 ObjectSizeOffsetEvaluator ObjSizeEval(DL, &TLI, F.getContext(), EvalOpts);
195
196 // check HANDLE_MEMORY_INST in include/llvm/Instruction.def for memory
197 // touching instructions
198 SmallVector<std::pair<Instruction *, Value *>, 4> TrapInfo;
199 for (Instruction &I : instructions(F)) {
200 Value *Or = nullptr;
201 BuilderTy IRB(I.getParent(), BasicBlock::iterator(&I), TargetFolder(DL));
202 if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {
203 if (!LI->isVolatile())
204 Or = getBoundsCheckCond(LI->getPointerOperand(), LI, DL, TLI,
205 ObjSizeEval, IRB, SE);
206 } else if (StoreInst *SI = dyn_cast<StoreInst>(&I)) {
207 if (!SI->isVolatile())
208 Or = getBoundsCheckCond(SI->getPointerOperand(), SI->getValueOperand(),
209 DL, TLI, ObjSizeEval, IRB, SE);
210 } else if (AtomicCmpXchgInst *AI = dyn_cast<AtomicCmpXchgInst>(&I)) {
211 if (!AI->isVolatile())
212 Or =
213 getBoundsCheckCond(AI->getPointerOperand(), AI->getCompareOperand(),
214 DL, TLI, ObjSizeEval, IRB, SE);
215 } else if (AtomicRMWInst *AI = dyn_cast<AtomicRMWInst>(&I)) {
216 if (!AI->isVolatile())
217 Or = getBoundsCheckCond(AI->getPointerOperand(), AI->getValOperand(),
218 DL, TLI, ObjSizeEval, IRB, SE);
219 }
220 if (Or) {
221 if (Opts.GuardKind) {
222 llvm::Value *Allow = IRB.CreateIntrinsic(
223 IRB.getInt1Ty(), Intrinsic::allow_ubsan_check,
224 {llvm::ConstantInt::getSigned(IRB.getInt8Ty(), *Opts.GuardKind)});
225 Or = IRB.CreateAnd(Or, Allow);
226 }
227 TrapInfo.push_back(std::make_pair(&I, Or));
228 }
229 }
230
231 std::string Name;
232 if (Opts.Rt)
233 Name = getRuntimeCallName(*Opts.Rt);
234
235 // Create a trapping basic block on demand using a callback. Depending on
236 // flags, this will either create a single block for the entire function or
237 // will create a fresh block every time it is called.
238 BasicBlock *ReuseTrapBB = nullptr;
239 auto GetTrapBB = [&ReuseTrapBB, &Opts, &Name](BuilderTy &IRB,
240 BasicBlock *Cont) {
241 Function *Fn = IRB.GetInsertBlock()->getParent();
242 auto DebugLoc = IRB.getCurrentDebugLocation();
243 IRBuilder<>::InsertPointGuard Guard(IRB);
244
245 // Create a trapping basic block on demand using a callback. Depending on
246 // flags, this will either create a single block for the entire function or
247 // will create a fresh block every time it is called.
248 if (ReuseTrapBB)
249 return ReuseTrapBB;
250
251 BasicBlock *TrapBB = BasicBlock::Create(Fn->getContext(), "trap", Fn);
252 IRB.SetInsertPoint(TrapBB);
253
254 bool DebugTrapBB = !Opts.Merge;
255 CallInst *TrapCall = Opts.Rt ? InsertCall(IRB, Opts.Rt->MayReturn, Name)
256 : InsertTrap(IRB, DebugTrapBB, Opts.GuardKind);
257 if (DebugTrapBB)
258 TrapCall->addFnAttr(llvm::Attribute::NoMerge);
259
260 TrapCall->setDoesNotThrow();
261 TrapCall->setDebugLoc(DebugLoc);
262
263 bool MayReturn = Opts.Rt && Opts.Rt->MayReturn;
264 if (MayReturn) {
265 IRB.CreateBr(Cont);
266 } else {
267 TrapCall->setDoesNotReturn();
268 IRB.CreateUnreachable();
269 }
270
271 if (!MayReturn && SingleTrapBB && !DebugTrapBB)
272 ReuseTrapBB = TrapBB;
273
274 return TrapBB;
275 };
276
277 for (const auto &Entry : TrapInfo) {
278 Instruction *Inst = Entry.first;
279 BuilderTy IRB(Inst->getParent(), BasicBlock::iterator(Inst), TargetFolder(DL));
280 insertBoundsCheck(Entry.second, IRB, GetTrapBB);
281 }
282
283 return !TrapInfo.empty();
284 }
285
run(Function & F,FunctionAnalysisManager & AM)286 PreservedAnalyses BoundsCheckingPass::run(Function &F, FunctionAnalysisManager &AM) {
287 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
288 auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F);
289
290 if (!addBoundsChecking(F, TLI, SE, Opts))
291 return PreservedAnalyses::all();
292
293 return PreservedAnalyses::none();
294 }
295
printPipeline(raw_ostream & OS,function_ref<StringRef (StringRef)> MapClassName2PassName)296 void BoundsCheckingPass::printPipeline(
297 raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
298 static_cast<PassInfoMixin<BoundsCheckingPass> *>(this)->printPipeline(
299 OS, MapClassName2PassName);
300 OS << "<";
301 if (Opts.Rt) {
302 if (Opts.Rt->MinRuntime)
303 OS << "min-";
304 OS << "rt";
305 if (!Opts.Rt->MayReturn)
306 OS << "-abort";
307 } else {
308 OS << "trap";
309 }
310 if (Opts.Merge)
311 OS << ";merge";
312 if (Opts.GuardKind)
313 OS << ";guard=" << static_cast<int>(*Opts.GuardKind);
314 OS << ">";
315 }
316