1 //===- HWAddressSanitizer.cpp - detector of uninitialized reads -------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 /// \file
11 /// This file is a part of HWAddressSanitizer, an address sanity checker
12 /// based on tagged addressing.
13 //===----------------------------------------------------------------------===//
14 
15 #include "llvm/ADT/SmallVector.h"
16 #include "llvm/ADT/StringExtras.h"
17 #include "llvm/ADT/StringRef.h"
18 #include "llvm/ADT/Triple.h"
19 #include "llvm/IR/Attributes.h"
20 #include "llvm/IR/BasicBlock.h"
21 #include "llvm/IR/Constant.h"
22 #include "llvm/IR/Constants.h"
23 #include "llvm/IR/DataLayout.h"
24 #include "llvm/IR/DerivedTypes.h"
25 #include "llvm/IR/MDBuilder.h"
26 #include "llvm/Support/raw_ostream.h"
27 #include "llvm/IR/Function.h"
28 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
29 #include "llvm/IR/IRBuilder.h"
30 #include "llvm/IR/InlineAsm.h"
31 #include "llvm/IR/InstVisitor.h"
32 #include "llvm/IR/Instruction.h"
33 #include "llvm/IR/Instructions.h"
34 #include "llvm/IR/IntrinsicInst.h"
35 #include "llvm/IR/Intrinsics.h"
36 #include "llvm/IR/LLVMContext.h"
37 #include "llvm/IR/Module.h"
38 #include "llvm/IR/Type.h"
39 #include "llvm/IR/Value.h"
40 #include "llvm/Pass.h"
41 #include "llvm/Support/Casting.h"
42 #include "llvm/Support/CommandLine.h"
43 #include "llvm/Support/Debug.h"
44 #include "llvm/Transforms/Instrumentation.h"
45 #include "llvm/Transforms/Utils/ModuleUtils.h"
46 
47 using namespace llvm;
48 
49 #define DEBUG_TYPE "hwasan"
50 
51 static const char *const kHwasanModuleCtorName = "hwasan.module_ctor";
52 static const char *const kHwasanInitName = "__hwasan_init";
53 
54 // Accesses sizes are powers of two: 1, 2, 4, 8, 16.
55 static const size_t kNumberOfAccessSizes = 5;
56 
57 static const size_t kShadowScale = 4;
58 static const unsigned kPointerTagShift = 56;
59 
60 static cl::opt<std::string> ClMemoryAccessCallbackPrefix(
61     "hwasan-memory-access-callback-prefix",
62     cl::desc("Prefix for memory access callbacks"), cl::Hidden,
63     cl::init("__hwasan_"));
64 
65 static cl::opt<bool>
66     ClInstrumentWithCalls("hwasan-instrument-with-calls",
67                 cl::desc("instrument reads and writes with callbacks"),
68                 cl::Hidden, cl::init(false));
69 
70 static cl::opt<bool> ClInstrumentReads("hwasan-instrument-reads",
71                                        cl::desc("instrument read instructions"),
72                                        cl::Hidden, cl::init(true));
73 
74 static cl::opt<bool> ClInstrumentWrites(
75     "hwasan-instrument-writes", cl::desc("instrument write instructions"),
76     cl::Hidden, cl::init(true));
77 
78 static cl::opt<bool> ClInstrumentAtomics(
79     "hwasan-instrument-atomics",
80     cl::desc("instrument atomic instructions (rmw, cmpxchg)"), cl::Hidden,
81     cl::init(true));
82 
83 static cl::opt<bool> ClRecover(
84     "hwasan-recover",
85     cl::desc("Enable recovery mode (continue-after-error)."),
86     cl::Hidden, cl::init(false));
87 
88 namespace {
89 
90 /// \brief An instrumentation pass implementing detection of addressability bugs
91 /// using tagged pointers.
92 class HWAddressSanitizer : public FunctionPass {
93 public:
94   // Pass identification, replacement for typeid.
95   static char ID;
96 
97   HWAddressSanitizer(bool Recover = false)
98       : FunctionPass(ID), Recover(Recover || ClRecover) {}
99 
100   StringRef getPassName() const override { return "HWAddressSanitizer"; }
101 
102   bool runOnFunction(Function &F) override;
103   bool doInitialization(Module &M) override;
104 
105   void initializeCallbacks(Module &M);
106   void instrumentMemAccessInline(Value *PtrLong, bool IsWrite,
107                                  unsigned AccessSizeIndex,
108                                  Instruction *InsertBefore);
109   bool instrumentMemAccess(Instruction *I);
110   Value *isInterestingMemoryAccess(Instruction *I, bool *IsWrite,
111                                    uint64_t *TypeSize, unsigned *Alignment,
112                                    Value **MaybeMask);
113 
114 private:
115   LLVMContext *C;
116   Type *IntptrTy;
117 
118   bool Recover;
119 
120   Function *HwasanCtorFunction;
121 
122   Function *HwasanMemoryAccessCallback[2][kNumberOfAccessSizes];
123   Function *HwasanMemoryAccessCallbackSized[2];
124 };
125 
126 } // end anonymous namespace
127 
128 char HWAddressSanitizer::ID = 0;
129 
130 INITIALIZE_PASS_BEGIN(
131     HWAddressSanitizer, "hwasan",
132     "HWAddressSanitizer: detect memory bugs using tagged addressing.", false, false)
133 INITIALIZE_PASS_END(
134     HWAddressSanitizer, "hwasan",
135     "HWAddressSanitizer: detect memory bugs using tagged addressing.", false, false)
136 
137 FunctionPass *llvm::createHWAddressSanitizerPass(bool Recover) {
138   return new HWAddressSanitizer(Recover);
139 }
140 
141 /// \brief Module-level initialization.
142 ///
143 /// inserts a call to __hwasan_init to the module's constructor list.
144 bool HWAddressSanitizer::doInitialization(Module &M) {
145   DEBUG(dbgs() << "Init " << M.getName() << "\n");
146   auto &DL = M.getDataLayout();
147 
148   Triple TargetTriple(M.getTargetTriple());
149 
150   C = &(M.getContext());
151   IRBuilder<> IRB(*C);
152   IntptrTy = IRB.getIntPtrTy(DL);
153 
154   std::tie(HwasanCtorFunction, std::ignore) =
155       createSanitizerCtorAndInitFunctions(M, kHwasanModuleCtorName,
156                                           kHwasanInitName,
157                                           /*InitArgTypes=*/{},
158                                           /*InitArgs=*/{});
159   appendToGlobalCtors(M, HwasanCtorFunction, 0);
160   return true;
161 }
162 
163 void HWAddressSanitizer::initializeCallbacks(Module &M) {
164   IRBuilder<> IRB(*C);
165   for (size_t AccessIsWrite = 0; AccessIsWrite <= 1; AccessIsWrite++) {
166     const std::string TypeStr = AccessIsWrite ? "store" : "load";
167     const std::string EndingStr = Recover ? "_noabort" : "";
168 
169     HwasanMemoryAccessCallbackSized[AccessIsWrite] =
170         checkSanitizerInterfaceFunction(M.getOrInsertFunction(
171             ClMemoryAccessCallbackPrefix + TypeStr + EndingStr,
172             FunctionType::get(IRB.getVoidTy(), {IntptrTy, IntptrTy}, false)));
173 
174     for (size_t AccessSizeIndex = 0; AccessSizeIndex < kNumberOfAccessSizes;
175          AccessSizeIndex++) {
176       HwasanMemoryAccessCallback[AccessIsWrite][AccessSizeIndex] =
177           checkSanitizerInterfaceFunction(M.getOrInsertFunction(
178               ClMemoryAccessCallbackPrefix + TypeStr +
179                   itostr(1ULL << AccessSizeIndex) + EndingStr,
180               FunctionType::get(IRB.getVoidTy(), {IntptrTy}, false)));
181     }
182   }
183 }
184 
185 Value *HWAddressSanitizer::isInterestingMemoryAccess(Instruction *I,
186                                                    bool *IsWrite,
187                                                    uint64_t *TypeSize,
188                                                    unsigned *Alignment,
189                                                    Value **MaybeMask) {
190   // Skip memory accesses inserted by another instrumentation.
191   if (I->getMetadata("nosanitize")) return nullptr;
192 
193   Value *PtrOperand = nullptr;
194   const DataLayout &DL = I->getModule()->getDataLayout();
195   if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
196     if (!ClInstrumentReads) return nullptr;
197     *IsWrite = false;
198     *TypeSize = DL.getTypeStoreSizeInBits(LI->getType());
199     *Alignment = LI->getAlignment();
200     PtrOperand = LI->getPointerOperand();
201   } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
202     if (!ClInstrumentWrites) return nullptr;
203     *IsWrite = true;
204     *TypeSize = DL.getTypeStoreSizeInBits(SI->getValueOperand()->getType());
205     *Alignment = SI->getAlignment();
206     PtrOperand = SI->getPointerOperand();
207   } else if (AtomicRMWInst *RMW = dyn_cast<AtomicRMWInst>(I)) {
208     if (!ClInstrumentAtomics) return nullptr;
209     *IsWrite = true;
210     *TypeSize = DL.getTypeStoreSizeInBits(RMW->getValOperand()->getType());
211     *Alignment = 0;
212     PtrOperand = RMW->getPointerOperand();
213   } else if (AtomicCmpXchgInst *XCHG = dyn_cast<AtomicCmpXchgInst>(I)) {
214     if (!ClInstrumentAtomics) return nullptr;
215     *IsWrite = true;
216     *TypeSize = DL.getTypeStoreSizeInBits(XCHG->getCompareOperand()->getType());
217     *Alignment = 0;
218     PtrOperand = XCHG->getPointerOperand();
219   }
220 
221   if (PtrOperand) {
222     // Do not instrument acesses from different address spaces; we cannot deal
223     // with them.
224     Type *PtrTy = cast<PointerType>(PtrOperand->getType()->getScalarType());
225     if (PtrTy->getPointerAddressSpace() != 0)
226       return nullptr;
227 
228     // Ignore swifterror addresses.
229     // swifterror memory addresses are mem2reg promoted by instruction
230     // selection. As such they cannot have regular uses like an instrumentation
231     // function and it makes no sense to track them as memory.
232     if (PtrOperand->isSwiftError())
233       return nullptr;
234   }
235 
236   return PtrOperand;
237 }
238 
239 static size_t TypeSizeToSizeIndex(uint32_t TypeSize) {
240   size_t Res = countTrailingZeros(TypeSize / 8);
241   assert(Res < kNumberOfAccessSizes);
242   return Res;
243 }
244 
245 void HWAddressSanitizer::instrumentMemAccessInline(Value *PtrLong, bool IsWrite,
246                                                    unsigned AccessSizeIndex,
247                                                    Instruction *InsertBefore) {
248   IRBuilder<> IRB(InsertBefore);
249   Value *PtrTag = IRB.CreateTrunc(IRB.CreateLShr(PtrLong, kPointerTagShift), IRB.getInt8Ty());
250   Value *AddrLong =
251       IRB.CreateAnd(PtrLong, ConstantInt::get(PtrLong->getType(),
252                                               ~(0xFFULL << kPointerTagShift)));
253   Value *ShadowLong = IRB.CreateLShr(AddrLong, kShadowScale);
254   Value *MemTag = IRB.CreateLoad(IRB.CreateIntToPtr(ShadowLong, IRB.getInt8PtrTy()));
255   Value *TagMismatch = IRB.CreateICmpNE(PtrTag, MemTag);
256 
257   TerminatorInst *CheckTerm =
258       SplitBlockAndInsertIfThen(TagMismatch, InsertBefore, !Recover,
259                                 MDBuilder(*C).createBranchWeights(1, 100000));
260 
261   IRB.SetInsertPoint(CheckTerm);
262   // The signal handler will find the data address in x0.
263   InlineAsm *Asm = InlineAsm::get(
264       FunctionType::get(IRB.getVoidTy(), {PtrLong->getType()}, false),
265       "hlt #" +
266           itostr(0x100 + Recover * 0x20 + IsWrite * 0x10 + AccessSizeIndex),
267       "{x0}",
268       /*hasSideEffects=*/true);
269   IRB.CreateCall(Asm, PtrLong);
270 }
271 
272 bool HWAddressSanitizer::instrumentMemAccess(Instruction *I) {
273   DEBUG(dbgs() << "Instrumenting: " << *I << "\n");
274   bool IsWrite = false;
275   unsigned Alignment = 0;
276   uint64_t TypeSize = 0;
277   Value *MaybeMask = nullptr;
278   Value *Addr =
279       isInterestingMemoryAccess(I, &IsWrite, &TypeSize, &Alignment, &MaybeMask);
280 
281   if (!Addr)
282     return false;
283 
284   if (MaybeMask)
285     return false; //FIXME
286 
287   IRBuilder<> IRB(I);
288   Value *AddrLong = IRB.CreatePointerCast(Addr, IntptrTy);
289   if (isPowerOf2_64(TypeSize) &&
290       (TypeSize / 8 <= (1UL << (kNumberOfAccessSizes - 1))) &&
291       (Alignment >= (1UL << kShadowScale) || Alignment == 0 ||
292        Alignment >= TypeSize / 8)) {
293     size_t AccessSizeIndex = TypeSizeToSizeIndex(TypeSize);
294     if (ClInstrumentWithCalls) {
295       IRB.CreateCall(HwasanMemoryAccessCallback[IsWrite][AccessSizeIndex],
296                      AddrLong);
297     } else {
298       instrumentMemAccessInline(AddrLong, IsWrite, AccessSizeIndex, I);
299     }
300   } else {
301     IRB.CreateCall(HwasanMemoryAccessCallbackSized[IsWrite],
302                    {AddrLong, ConstantInt::get(IntptrTy, TypeSize / 8)});
303   }
304 
305   return true;
306 }
307 
308 bool HWAddressSanitizer::runOnFunction(Function &F) {
309   if (&F == HwasanCtorFunction)
310     return false;
311 
312   if (!F.hasFnAttribute(Attribute::SanitizeHWAddress))
313     return false;
314 
315   DEBUG(dbgs() << "Function: " << F.getName() << "\n");
316 
317   initializeCallbacks(*F.getParent());
318 
319   bool Changed = false;
320   SmallVector<Instruction*, 16> ToInstrument;
321   for (auto &BB : F) {
322     for (auto &Inst : BB) {
323       Value *MaybeMask = nullptr;
324       bool IsWrite;
325       unsigned Alignment;
326       uint64_t TypeSize;
327       Value *Addr = isInterestingMemoryAccess(&Inst, &IsWrite, &TypeSize,
328                                               &Alignment, &MaybeMask);
329       if (Addr || isa<MemIntrinsic>(Inst))
330         ToInstrument.push_back(&Inst);
331     }
332   }
333 
334   for (auto Inst : ToInstrument)
335     Changed |= instrumentMemAccess(Inst);
336 
337   return Changed;
338 }
339