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