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 namespace {
84 
85 /// \brief An instrumentation pass implementing detection of addressability bugs
86 /// using tagged pointers.
87 class HWAddressSanitizer : public FunctionPass {
88 public:
89   // Pass identification, replacement for typeid.
90   static char ID;
91 
92   HWAddressSanitizer() : FunctionPass(ID) {}
93 
94   StringRef getPassName() const override { return "HWAddressSanitizer"; }
95 
96   bool runOnFunction(Function &F) override;
97   bool doInitialization(Module &M) override;
98 
99   void initializeCallbacks(Module &M);
100   void instrumentMemAccessInline(Value *PtrLong, bool IsWrite,
101                                  unsigned AccessSizeIndex,
102                                  Instruction *InsertBefore);
103   bool instrumentMemAccess(Instruction *I);
104   Value *isInterestingMemoryAccess(Instruction *I, bool *IsWrite,
105                                    uint64_t *TypeSize, unsigned *Alignment,
106                                    Value **MaybeMask);
107 
108 private:
109   LLVMContext *C;
110   Type *IntptrTy;
111 
112   Function *HwasanCtorFunction;
113 
114   Function *HwasanMemoryAccessCallback[2][kNumberOfAccessSizes];
115   Function *HwasanMemoryAccessCallbackSized[2];
116 };
117 
118 } // end anonymous namespace
119 
120 char HWAddressSanitizer::ID = 0;
121 
122 INITIALIZE_PASS_BEGIN(
123     HWAddressSanitizer, "hwasan",
124     "HWAddressSanitizer: detect memory bugs using tagged addressing.", false, false)
125 INITIALIZE_PASS_END(
126     HWAddressSanitizer, "hwasan",
127     "HWAddressSanitizer: detect memory bugs using tagged addressing.", false, false)
128 
129 FunctionPass *llvm::createHWAddressSanitizerPass() {
130   return new HWAddressSanitizer();
131 }
132 
133 /// \brief Module-level initialization.
134 ///
135 /// inserts a call to __hwasan_init to the module's constructor list.
136 bool HWAddressSanitizer::doInitialization(Module &M) {
137   DEBUG(dbgs() << "Init " << M.getName() << "\n");
138   auto &DL = M.getDataLayout();
139 
140   Triple TargetTriple(M.getTargetTriple());
141 
142   C = &(M.getContext());
143   IRBuilder<> IRB(*C);
144   IntptrTy = IRB.getIntPtrTy(DL);
145 
146   std::tie(HwasanCtorFunction, std::ignore) =
147       createSanitizerCtorAndInitFunctions(M, kHwasanModuleCtorName,
148                                           kHwasanInitName,
149                                           /*InitArgTypes=*/{},
150                                           /*InitArgs=*/{});
151   appendToGlobalCtors(M, HwasanCtorFunction, 0);
152   return true;
153 }
154 
155 void HWAddressSanitizer::initializeCallbacks(Module &M) {
156   IRBuilder<> IRB(*C);
157   for (size_t AccessIsWrite = 0; AccessIsWrite <= 1; AccessIsWrite++) {
158     const std::string TypeStr = AccessIsWrite ? "store" : "load";
159 
160     HwasanMemoryAccessCallbackSized[AccessIsWrite] =
161         checkSanitizerInterfaceFunction(M.getOrInsertFunction(
162             ClMemoryAccessCallbackPrefix + TypeStr,
163             FunctionType::get(IRB.getVoidTy(), {IntptrTy, IntptrTy}, false)));
164 
165     for (size_t AccessSizeIndex = 0; AccessSizeIndex < kNumberOfAccessSizes;
166          AccessSizeIndex++) {
167       HwasanMemoryAccessCallback[AccessIsWrite][AccessSizeIndex] =
168           checkSanitizerInterfaceFunction(M.getOrInsertFunction(
169               ClMemoryAccessCallbackPrefix + TypeStr +
170                   itostr(1ULL << AccessSizeIndex),
171               FunctionType::get(IRB.getVoidTy(), {IntptrTy}, false)));
172     }
173   }
174 }
175 
176 Value *HWAddressSanitizer::isInterestingMemoryAccess(Instruction *I,
177                                                    bool *IsWrite,
178                                                    uint64_t *TypeSize,
179                                                    unsigned *Alignment,
180                                                    Value **MaybeMask) {
181   // Skip memory accesses inserted by another instrumentation.
182   if (I->getMetadata("nosanitize")) return nullptr;
183 
184   Value *PtrOperand = nullptr;
185   const DataLayout &DL = I->getModule()->getDataLayout();
186   if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
187     if (!ClInstrumentReads) return nullptr;
188     *IsWrite = false;
189     *TypeSize = DL.getTypeStoreSizeInBits(LI->getType());
190     *Alignment = LI->getAlignment();
191     PtrOperand = LI->getPointerOperand();
192   } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
193     if (!ClInstrumentWrites) return nullptr;
194     *IsWrite = true;
195     *TypeSize = DL.getTypeStoreSizeInBits(SI->getValueOperand()->getType());
196     *Alignment = SI->getAlignment();
197     PtrOperand = SI->getPointerOperand();
198   } else if (AtomicRMWInst *RMW = dyn_cast<AtomicRMWInst>(I)) {
199     if (!ClInstrumentAtomics) return nullptr;
200     *IsWrite = true;
201     *TypeSize = DL.getTypeStoreSizeInBits(RMW->getValOperand()->getType());
202     *Alignment = 0;
203     PtrOperand = RMW->getPointerOperand();
204   } else if (AtomicCmpXchgInst *XCHG = dyn_cast<AtomicCmpXchgInst>(I)) {
205     if (!ClInstrumentAtomics) return nullptr;
206     *IsWrite = true;
207     *TypeSize = DL.getTypeStoreSizeInBits(XCHG->getCompareOperand()->getType());
208     *Alignment = 0;
209     PtrOperand = XCHG->getPointerOperand();
210   }
211 
212   if (PtrOperand) {
213     // Do not instrument acesses from different address spaces; we cannot deal
214     // with them.
215     Type *PtrTy = cast<PointerType>(PtrOperand->getType()->getScalarType());
216     if (PtrTy->getPointerAddressSpace() != 0)
217       return nullptr;
218 
219     // Ignore swifterror addresses.
220     // swifterror memory addresses are mem2reg promoted by instruction
221     // selection. As such they cannot have regular uses like an instrumentation
222     // function and it makes no sense to track them as memory.
223     if (PtrOperand->isSwiftError())
224       return nullptr;
225   }
226 
227   return PtrOperand;
228 }
229 
230 static size_t TypeSizeToSizeIndex(uint32_t TypeSize) {
231   size_t Res = countTrailingZeros(TypeSize / 8);
232   assert(Res < kNumberOfAccessSizes);
233   return Res;
234 }
235 
236 void HWAddressSanitizer::instrumentMemAccessInline(Value *PtrLong, bool IsWrite,
237                                                    unsigned AccessSizeIndex,
238                                                    Instruction *InsertBefore) {
239   IRBuilder<> IRB(InsertBefore);
240   Value *PtrTag = IRB.CreateTrunc(IRB.CreateLShr(PtrLong, kPointerTagShift), IRB.getInt8Ty());
241   Value *AddrLong =
242       IRB.CreateAnd(PtrLong, ConstantInt::get(PtrLong->getType(),
243                                               ~(0xFFULL << kPointerTagShift)));
244   Value *ShadowLong = IRB.CreateLShr(AddrLong, kShadowScale);
245   Value *MemTag = IRB.CreateLoad(IRB.CreateIntToPtr(ShadowLong, IRB.getInt8PtrTy()));
246   Value *TagMismatch = IRB.CreateICmpNE(PtrTag, MemTag);
247 
248   TerminatorInst *CheckTerm =
249       SplitBlockAndInsertIfThen(TagMismatch, InsertBefore, false,
250                                 MDBuilder(*C).createBranchWeights(1, 100000));
251 
252   IRB.SetInsertPoint(CheckTerm);
253   // The signal handler will find the data address in x0.
254   InlineAsm *Asm = InlineAsm::get(
255       FunctionType::get(IRB.getVoidTy(), {PtrLong->getType()}, false),
256       "hlt #" + itostr(0x100 + IsWrite * 0x10 + AccessSizeIndex), "{x0}",
257       /*hasSideEffects=*/true);
258   IRB.CreateCall(Asm, PtrLong);
259 }
260 
261 bool HWAddressSanitizer::instrumentMemAccess(Instruction *I) {
262   DEBUG(dbgs() << "Instrumenting: " << *I << "\n");
263   bool IsWrite = false;
264   unsigned Alignment = 0;
265   uint64_t TypeSize = 0;
266   Value *MaybeMask = nullptr;
267   Value *Addr =
268       isInterestingMemoryAccess(I, &IsWrite, &TypeSize, &Alignment, &MaybeMask);
269 
270   if (!Addr)
271     return false;
272 
273   if (MaybeMask)
274     return false; //FIXME
275 
276   IRBuilder<> IRB(I);
277   Value *AddrLong = IRB.CreatePointerCast(Addr, IntptrTy);
278   if (isPowerOf2_64(TypeSize) &&
279       (TypeSize / 8 <= (1UL << (kNumberOfAccessSizes - 1))) &&
280       (Alignment >= (1UL << kShadowScale) || Alignment == 0 ||
281        Alignment >= TypeSize / 8)) {
282     size_t AccessSizeIndex = TypeSizeToSizeIndex(TypeSize);
283     if (ClInstrumentWithCalls) {
284       IRB.CreateCall(HwasanMemoryAccessCallback[IsWrite][AccessSizeIndex],
285                      AddrLong);
286     } else {
287       instrumentMemAccessInline(AddrLong, IsWrite, AccessSizeIndex, I);
288     }
289   } else {
290     IRB.CreateCall(HwasanMemoryAccessCallbackSized[IsWrite],
291                    {AddrLong, ConstantInt::get(IntptrTy, TypeSize / 8)});
292   }
293 
294   return true;
295 }
296 
297 bool HWAddressSanitizer::runOnFunction(Function &F) {
298   if (&F == HwasanCtorFunction)
299     return false;
300 
301   if (!F.hasFnAttribute(Attribute::SanitizeHWAddress))
302     return false;
303 
304   DEBUG(dbgs() << "Function: " << F.getName() << "\n");
305 
306   initializeCallbacks(*F.getParent());
307 
308   bool Changed = false;
309   SmallVector<Instruction*, 16> ToInstrument;
310   for (auto &BB : F) {
311     for (auto &Inst : BB) {
312       Value *MaybeMask = nullptr;
313       bool IsWrite;
314       unsigned Alignment;
315       uint64_t TypeSize;
316       Value *Addr = isInterestingMemoryAccess(&Inst, &IsWrite, &TypeSize,
317                                               &Alignment, &MaybeMask);
318       if (Addr || isa<MemIntrinsic>(Inst))
319         ToInstrument.push_back(&Inst);
320     }
321   }
322 
323   for (auto Inst : ToInstrument)
324     Changed |= instrumentMemAccess(Inst);
325 
326   return Changed;
327 }
328