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
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 NoSanitizeInserter final : public IRBuilderDefaultInserter {
45 mutable MDNode *NoSanitizeMD = nullptr;
46
47public:
48 NoSanitizeInserter() = default;
49
50 void InsertHelper(Instruction *I, const Twine &Name,
51 BasicBlock::iterator InsertPt) const override {
52 IRBuilderDefaultInserter::InsertHelper(I, Name, InsertPt);
53 if (!NoSanitizeMD)
54 NoSanitizeMD = MDNode::get(Context&: I->getContext(), MDs: {});
55 I->setMetadata(KindID: LLVMContext::MD_nosanitize, Node: NoSanitizeMD);
56 }
57};
58
59using BuilderTy = IRBuilder<TargetFolder, NoSanitizeInserter>;
60
61/// Gets the conditions under which memory accessing instructions will overflow.
62///
63/// \p Ptr is the pointer that will be read/written, and \p InstVal is either
64/// the result from the load or the value being stored. It is used to determine
65/// the size of memory block that is touched.
66///
67/// Returns the condition under which the access will overflow.
68static Value *getBoundsCheckCond(Value *Ptr, Value *InstVal,
69 const DataLayout &DL, TargetLibraryInfo &TLI,
70 ObjectSizeOffsetEvaluator &ObjSizeEval,
71 BuilderTy &IRB, ScalarEvolution &SE) {
72 TypeSize NeededSize = DL.getTypeStoreSize(Ty: InstVal->getType());
73 LLVM_DEBUG(dbgs() << "Instrument " << *Ptr << " for " << Twine(NeededSize)
74 << " bytes\n");
75
76 SizeOffsetValue SizeOffset = ObjSizeEval.compute(V: Ptr);
77
78 if (!SizeOffset.bothKnown()) {
79 ++ChecksUnable;
80 return nullptr;
81 }
82
83 Value *Size = SizeOffset.Size;
84 Value *Offset = SizeOffset.Offset;
85 ConstantInt *SizeCI = dyn_cast<ConstantInt>(Val: Size);
86
87 Type *IndexTy = DL.getIndexType(PtrTy: Ptr->getType());
88 Value *NeededSizeVal = IRB.CreateTypeSize(Ty: IndexTy, Size: NeededSize);
89
90 auto SizeRange = SE.getUnsignedRange(S: SE.getSCEV(V: Size));
91 auto OffsetRange = SE.getUnsignedRange(S: SE.getSCEV(V: Offset));
92 auto NeededSizeRange = SE.getUnsignedRange(S: SE.getSCEV(V: NeededSizeVal));
93
94 // three checks are required to ensure safety:
95 // . Offset >= 0 (since the offset is given from the base ptr)
96 // . Size >= Offset (unsigned)
97 // . Size - Offset >= NeededSize (unsigned)
98 //
99 // optimization: if Size >= 0 (signed), skip 1st check
100 // FIXME: add NSW/NUW here? -- we dont care if the subtraction overflows
101 Value *ObjSize = IRB.CreateSub(LHS: Size, RHS: Offset);
102 Value *Cmp2 = SizeRange.getUnsignedMin().uge(RHS: OffsetRange.getUnsignedMax())
103 ? ConstantInt::getFalse(Context&: Ptr->getContext())
104 : IRB.CreateICmpULT(LHS: Size, RHS: Offset);
105 Value *Cmp3 = SizeRange.sub(Other: OffsetRange)
106 .getUnsignedMin()
107 .uge(RHS: NeededSizeRange.getUnsignedMax())
108 ? ConstantInt::getFalse(Context&: Ptr->getContext())
109 : IRB.CreateICmpULT(LHS: ObjSize, RHS: NeededSizeVal);
110 Value *Or = IRB.CreateOr(LHS: Cmp2, RHS: Cmp3);
111 if ((!SizeCI || SizeCI->getValue().slt(RHS: 0)) &&
112 !SizeRange.getSignedMin().isNonNegative()) {
113 Value *Cmp1 = IRB.CreateICmpSLT(LHS: Offset, RHS: ConstantInt::get(Ty: IndexTy, V: 0));
114 Or = IRB.CreateOr(LHS: Cmp1, RHS: Or);
115 }
116
117 return Or;
118}
119
120static CallInst *InsertTrap(BuilderTy &IRB, bool DebugTrapBB,
121 std::optional<int8_t> GuardKind) {
122 if (!DebugTrapBB)
123 return IRB.CreateIntrinsicWithoutFolding(ID: Intrinsic::trap, Args: {});
124
125 uint64_t ImmArg = GuardKind.has_value()
126 ? GuardKind.value()
127 : IRB.GetInsertBlock()->getParent()->size();
128 // Ensure we constrain ImmArg to fitting within a 8-but unsigned integer to
129 // prevent overflow.
130 if (ImmArg > 255)
131 ImmArg = 255;
132
133 return IRB.CreateIntrinsicWithoutFolding(
134 ID: Intrinsic::ubsantrap, Args: ConstantInt::get(Ty: IRB.getInt8Ty(), V: ImmArg));
135}
136
137static CallInst *InsertCall(BuilderTy &IRB, bool MayReturn, StringRef Name) {
138 Function *Fn = IRB.GetInsertBlock()->getParent();
139 LLVMContext &Ctx = Fn->getContext();
140 llvm::AttrBuilder B(Ctx);
141 B.addAttribute(Val: llvm::Attribute::NoUnwind);
142 if (!MayReturn)
143 B.addAttribute(Val: llvm::Attribute::NoReturn);
144 FunctionCallee Callee = Fn->getParent()->getOrInsertFunction(
145 Name,
146 AttributeList: llvm::AttributeList::get(C&: Ctx, Index: llvm::AttributeList::FunctionIndex, B),
147 RetTy: Type::getVoidTy(C&: Ctx));
148 return IRB.CreateCall(Callee);
149}
150
151/// Adds run-time bounds checks to memory accessing instructions.
152///
153/// \p Or is the condition that should guard the trap.
154///
155/// \p GetTrapBB is a callable that returns the trap BB to use on failure.
156template <typename GetTrapBBT>
157static void insertBoundsCheck(Value *Or, BuilderTy &IRB, GetTrapBBT GetTrapBB) {
158 // check if the comparison is always false
159 ConstantInt *C = dyn_cast_or_null<ConstantInt>(Val: Or);
160 if (C) {
161 ++ChecksSkipped;
162 // If non-zero, nothing to do.
163 if (!C->getZExtValue())
164 return;
165 }
166 ++ChecksAdded;
167
168 BasicBlock::iterator SplitI = IRB.GetInsertPoint();
169 BasicBlock *OldBB = SplitI->getParent();
170 BasicBlock *Cont = OldBB->splitBasicBlock(I: SplitI);
171 OldBB->getTerminator()->eraseFromParent();
172
173 BasicBlock *TrapBB = GetTrapBB(IRB, Cont);
174
175 if (C) {
176 // If we have a constant zero, unconditionally branch.
177 // FIXME: We should really handle this differently to bypass the splitting
178 // the block.
179 UncondBrInst::Create(Target: TrapBB, InsertBefore: OldBB);
180 return;
181 }
182
183 // Create the conditional branch.
184 CondBrInst::Create(Cond: Or, IfTrue: TrapBB, IfFalse: Cont, InsertBefore: OldBB);
185}
186
187static std::string
188getRuntimeCallName(const BoundsCheckingPass::Options::Runtime &Opts) {
189 std::string Name = "__ubsan_handle_local_out_of_bounds";
190 if (Opts.MinRuntime)
191 Name += "_minimal";
192 if (!Opts.MayReturn)
193 Name += "_abort";
194 else if (Opts.HandlerPreserveAllRegs)
195 Name += "_preserve";
196 return Name;
197}
198
199static bool addBoundsChecking(Function &F, TargetLibraryInfo &TLI,
200 ScalarEvolution &SE,
201 const BoundsCheckingPass::Options &Opts) {
202 if (F.hasFnAttribute(Kind: Attribute::NoSanitizeBounds))
203 return false;
204
205 const DataLayout &DL = F.getDataLayout();
206 ObjectSizeOpts EvalOpts;
207 EvalOpts.RoundToAlign = true;
208 EvalOpts.EvalMode = ObjectSizeOpts::Mode::ExactUnderlyingSizeAndOffset;
209 ObjectSizeOffsetEvaluator ObjSizeEval(DL, &TLI, F.getContext(), EvalOpts);
210
211 // check HANDLE_MEMORY_INST in include/llvm/Instruction.def for memory
212 // touching instructions
213 SmallVector<std::pair<Instruction *, Value *>, 4> TrapInfo;
214 for (Instruction &I : instructions(F)) {
215 Value *Or = nullptr;
216 BuilderTy IRB(I.getParent(), BasicBlock::iterator(&I), TargetFolder(DL));
217 if (LoadInst *LI = dyn_cast<LoadInst>(Val: &I)) {
218 if (!LI->isVolatile())
219 Or = getBoundsCheckCond(Ptr: LI->getPointerOperand(), InstVal: LI, DL, TLI,
220 ObjSizeEval, IRB, SE);
221 } else if (StoreInst *SI = dyn_cast<StoreInst>(Val: &I)) {
222 if (!SI->isVolatile())
223 Or = getBoundsCheckCond(Ptr: SI->getPointerOperand(), InstVal: SI->getValueOperand(),
224 DL, TLI, ObjSizeEval, IRB, SE);
225 } else if (AtomicCmpXchgInst *AI = dyn_cast<AtomicCmpXchgInst>(Val: &I)) {
226 if (!AI->isVolatile())
227 Or =
228 getBoundsCheckCond(Ptr: AI->getPointerOperand(), InstVal: AI->getCompareOperand(),
229 DL, TLI, ObjSizeEval, IRB, SE);
230 } else if (AtomicRMWInst *AI = dyn_cast<AtomicRMWInst>(Val: &I)) {
231 if (!AI->isVolatile())
232 Or = getBoundsCheckCond(Ptr: AI->getPointerOperand(), InstVal: AI->getValOperand(),
233 DL, TLI, ObjSizeEval, IRB, SE);
234 }
235 if (Or) {
236 if (Opts.GuardKind) {
237 llvm::Value *Allow = IRB.CreateIntrinsic(
238 RetTy: IRB.getInt1Ty(), ID: Intrinsic::allow_ubsan_check,
239 Args: {llvm::ConstantInt::getSigned(Ty: IRB.getInt8Ty(), V: *Opts.GuardKind)});
240 Or = IRB.CreateAnd(LHS: Or, RHS: Allow);
241 }
242 TrapInfo.push_back(Elt: std::make_pair(x: &I, y&: Or));
243 }
244 }
245
246 std::string Name;
247 if (Opts.Rt)
248 Name = getRuntimeCallName(Opts: *Opts.Rt);
249
250 // Create a trapping basic block on demand using a callback. Depending on
251 // flags, this will either create a single block for the entire function or
252 // will create a fresh block every time it is called.
253 BasicBlock *ReuseTrapBB = nullptr;
254 auto GetTrapBB = [&ReuseTrapBB, &Opts, &Name](BuilderTy &IRB,
255 BasicBlock *Cont) {
256 Function *Fn = IRB.GetInsertBlock()->getParent();
257 auto DebugLoc = IRB.getCurrentDebugLocation();
258 IRBuilder<>::InsertPointGuard Guard(IRB);
259
260 // Create a trapping basic block on demand using a callback. Depending on
261 // flags, this will either create a single block for the entire function or
262 // will create a fresh block every time it is called.
263 if (ReuseTrapBB)
264 return ReuseTrapBB;
265
266 BasicBlock *TrapBB = BasicBlock::Create(Context&: Fn->getContext(), Name: "trap", Parent: Fn);
267 IRB.SetInsertPoint(TrapBB);
268
269 bool DebugTrapBB = !Opts.Merge;
270 CallInst *TrapCall = Opts.Rt ? InsertCall(IRB, MayReturn: Opts.Rt->MayReturn, Name)
271 : InsertTrap(IRB, DebugTrapBB, GuardKind: Opts.GuardKind);
272 if (DebugTrapBB)
273 TrapCall->addFnAttr(Kind: llvm::Attribute::NoMerge);
274
275 TrapCall->setDoesNotThrow();
276 TrapCall->setDebugLoc(DebugLoc);
277
278 bool MayReturn = Opts.Rt && Opts.Rt->MayReturn;
279 if (MayReturn) {
280 IRB.CreateBr(Dest: Cont);
281 } else {
282 TrapCall->setDoesNotReturn();
283 IRB.CreateUnreachable();
284 }
285 // The preserve-all logic is somewhat duplicated in CGExpr.cpp for
286 // local-bounds. Make sure to change that too.
287 if (Opts.Rt && Opts.Rt->HandlerPreserveAllRegs && MayReturn)
288 TrapCall->setCallingConv(CallingConv::PreserveAll);
289 if (!MayReturn && SingleTrapBB && !DebugTrapBB)
290 ReuseTrapBB = TrapBB;
291
292 return TrapBB;
293 };
294
295 for (const auto &Entry : TrapInfo) {
296 Instruction *Inst = Entry.first;
297 BuilderTy IRB(Inst->getParent(), BasicBlock::iterator(Inst), TargetFolder(DL));
298 insertBoundsCheck(Or: Entry.second, IRB, GetTrapBB);
299 }
300
301 return !TrapInfo.empty();
302}
303
304PreservedAnalyses BoundsCheckingPass::run(Function &F, FunctionAnalysisManager &AM) {
305 auto &TLI = AM.getResult<TargetLibraryAnalysis>(IR&: F);
306 auto &SE = AM.getResult<ScalarEvolutionAnalysis>(IR&: F);
307
308 if (!addBoundsChecking(F, TLI, SE, Opts))
309 return PreservedAnalyses::all();
310
311 return PreservedAnalyses::none();
312}
313
314void BoundsCheckingPass::printPipeline(
315 raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
316 static_cast<PassInfoMixin<BoundsCheckingPass> *>(this)->printPipeline(
317 OS, MapClassName2PassName);
318 OS << "<";
319 if (Opts.Rt) {
320 if (Opts.Rt->MinRuntime)
321 OS << "min-";
322 OS << "rt";
323 if (!Opts.Rt->MayReturn)
324 OS << "-abort";
325 } else {
326 OS << "trap";
327 }
328 if (Opts.Merge)
329 OS << ";merge";
330 if (Opts.GuardKind)
331 OS << ";guard=" << static_cast<int>(*Opts.GuardKind);
332 OS << ">";
333}
334