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/Function.h"
26 #include "llvm/IR/IRBuilder.h"
27 #include "llvm/IR/InlineAsm.h"
28 #include "llvm/IR/InstVisitor.h"
29 #include "llvm/IR/Instruction.h"
30 #include "llvm/IR/Instructions.h"
31 #include "llvm/IR/IntrinsicInst.h"
32 #include "llvm/IR/Intrinsics.h"
33 #include "llvm/IR/LLVMContext.h"
34 #include "llvm/IR/MDBuilder.h"
35 #include "llvm/IR/Module.h"
36 #include "llvm/IR/Type.h"
37 #include "llvm/IR/Value.h"
38 #include "llvm/Pass.h"
39 #include "llvm/Support/Casting.h"
40 #include "llvm/Support/CommandLine.h"
41 #include "llvm/Support/Debug.h"
42 #include "llvm/Support/raw_ostream.h"
43 #include "llvm/Transforms/Instrumentation.h"
44 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
45 #include "llvm/Transforms/Utils/ModuleUtils.h"
46 #include "llvm/Transforms/Utils/PromoteMemToReg.h"
47 
48 using namespace llvm;
49 
50 #define DEBUG_TYPE "hwasan"
51 
52 static const char *const kHwasanModuleCtorName = "hwasan.module_ctor";
53 static const char *const kHwasanInitName = "__hwasan_init";
54 
55 // Accesses sizes are powers of two: 1, 2, 4, 8, 16.
56 static const size_t kNumberOfAccessSizes = 5;
57 
58 static const size_t kShadowScale = 4;
59 static const unsigned kAllocaAlignment = 1U << kShadowScale;
60 static const unsigned kPointerTagShift = 56;
61 
62 static cl::opt<std::string> ClMemoryAccessCallbackPrefix(
63     "hwasan-memory-access-callback-prefix",
64     cl::desc("Prefix for memory access callbacks"), cl::Hidden,
65     cl::init("__hwasan_"));
66 
67 static cl::opt<bool>
68     ClInstrumentWithCalls("hwasan-instrument-with-calls",
69                 cl::desc("instrument reads and writes with callbacks"),
70                 cl::Hidden, cl::init(false));
71 
72 static cl::opt<bool> ClInstrumentReads("hwasan-instrument-reads",
73                                        cl::desc("instrument read instructions"),
74                                        cl::Hidden, cl::init(true));
75 
76 static cl::opt<bool> ClInstrumentWrites(
77     "hwasan-instrument-writes", cl::desc("instrument write instructions"),
78     cl::Hidden, cl::init(true));
79 
80 static cl::opt<bool> ClInstrumentAtomics(
81     "hwasan-instrument-atomics",
82     cl::desc("instrument atomic instructions (rmw, cmpxchg)"), cl::Hidden,
83     cl::init(true));
84 
85 static cl::opt<bool> ClRecover(
86     "hwasan-recover",
87     cl::desc("Enable recovery mode (continue-after-error)."),
88     cl::Hidden, cl::init(false));
89 
90 static cl::opt<bool> ClInstrumentStack("hwasan-instrument-stack",
91                                        cl::desc("instrument stack (allocas)"),
92                                        cl::Hidden, cl::init(true));
93 
94 static cl::opt<bool> ClGenerateTagsWithCalls(
95     "hwasan-generate-tags-with-calls",
96     cl::desc("generate new tags with runtime library calls"), cl::Hidden,
97     cl::init(false));
98 
99 static cl::opt<unsigned long long> ClMappingOffset(
100     "hwasan-mapping-offset",
101     cl::desc("offset of hwasan shadow mapping [EXPERIMENTAL]"), cl::Hidden,
102     cl::init(0));
103 
104 static cl::opt<int> ClMatchAllTag(
105     "hwasan-match-all-tag",
106     cl::desc("don't report bad accesses via pointers with this tag"), cl::Hidden,
107     cl::init(-1));
108 
109 static cl::opt<bool> ClEnableKhwasan(
110     "hwasan-kernel", cl::desc("Enable KernelHWAddressSanitizer instrumentation"),
111     cl::Hidden, cl::init(false));
112 
113 namespace {
114 
115 /// \brief An instrumentation pass implementing detection of addressability bugs
116 /// using tagged pointers.
117 class HWAddressSanitizer : public FunctionPass {
118 public:
119   // Pass identification, replacement for typeid.
120   static char ID;
121 
122   HWAddressSanitizer(bool Recover = false)
123       : FunctionPass(ID), Recover(Recover || ClRecover) {}
124 
125   StringRef getPassName() const override { return "HWAddressSanitizer"; }
126 
127   bool runOnFunction(Function &F) override;
128   bool doInitialization(Module &M) override;
129 
130   void initializeCallbacks(Module &M);
131   void untagPointerOperand(Instruction *I, Value *Addr);
132   void instrumentMemAccessInline(Value *PtrLong, bool IsWrite,
133                                  unsigned AccessSizeIndex,
134                                  Instruction *InsertBefore);
135   bool instrumentMemAccess(Instruction *I);
136   Value *isInterestingMemoryAccess(Instruction *I, bool *IsWrite,
137                                    uint64_t *TypeSize, unsigned *Alignment,
138                                    Value **MaybeMask);
139 
140   bool isInterestingAlloca(const AllocaInst &AI);
141   bool tagAlloca(IRBuilder<> &IRB, AllocaInst *AI, Value *Tag);
142   Value *tagPointer(IRBuilder<> &IRB, Type *Ty, Value *PtrLong, Value *Tag);
143   Value *untagPointer(IRBuilder<> &IRB, Value *PtrLong);
144   bool instrumentStack(SmallVectorImpl<AllocaInst *> &Allocas,
145                        SmallVectorImpl<Instruction *> &RetVec);
146   Value *getNextTagWithCall(IRBuilder<> &IRB);
147   Value *getStackBaseTag(IRBuilder<> &IRB);
148   Value *getAllocaTag(IRBuilder<> &IRB, Value *StackTag, AllocaInst *AI,
149                      unsigned AllocaNo);
150   Value *getUARTag(IRBuilder<> &IRB, Value *StackTag);
151 
152 private:
153   LLVMContext *C;
154   Triple TargetTriple;
155 
156   Type *IntptrTy;
157   Type *Int8Ty;
158 
159   bool Recover;
160 
161   Function *HwasanCtorFunction;
162 
163   Function *HwasanMemoryAccessCallback[2][kNumberOfAccessSizes];
164   Function *HwasanMemoryAccessCallbackSized[2];
165 
166   Function *HwasanTagMemoryFunc;
167   Function *HwasanGenerateTagFunc;
168 };
169 
170 } // end anonymous namespace
171 
172 char HWAddressSanitizer::ID = 0;
173 
174 INITIALIZE_PASS_BEGIN(
175     HWAddressSanitizer, "hwasan",
176     "HWAddressSanitizer: detect memory bugs using tagged addressing.", false, false)
177 INITIALIZE_PASS_END(
178     HWAddressSanitizer, "hwasan",
179     "HWAddressSanitizer: detect memory bugs using tagged addressing.", false, false)
180 
181 FunctionPass *llvm::createHWAddressSanitizerPass(bool Recover) {
182   return new HWAddressSanitizer(Recover);
183 }
184 
185 /// \brief Module-level initialization.
186 ///
187 /// inserts a call to __hwasan_init to the module's constructor list.
188 bool HWAddressSanitizer::doInitialization(Module &M) {
189   DEBUG(dbgs() << "Init " << M.getName() << "\n");
190   auto &DL = M.getDataLayout();
191 
192   TargetTriple = Triple(M.getTargetTriple());
193 
194   C = &(M.getContext());
195   IRBuilder<> IRB(*C);
196   IntptrTy = IRB.getIntPtrTy(DL);
197   Int8Ty = IRB.getInt8Ty();
198 
199   HwasanCtorFunction = nullptr;
200   if (!ClEnableKhwasan) {
201     std::tie(HwasanCtorFunction, std::ignore) =
202         createSanitizerCtorAndInitFunctions(M, kHwasanModuleCtorName,
203                                             kHwasanInitName,
204                                             /*InitArgTypes=*/{},
205                                             /*InitArgs=*/{});
206     appendToGlobalCtors(M, HwasanCtorFunction, 0);
207   }
208   return true;
209 }
210 
211 void HWAddressSanitizer::initializeCallbacks(Module &M) {
212   IRBuilder<> IRB(*C);
213   for (size_t AccessIsWrite = 0; AccessIsWrite <= 1; AccessIsWrite++) {
214     const std::string TypeStr = AccessIsWrite ? "store" : "load";
215     const std::string EndingStr = Recover ? "_noabort" : "";
216 
217     HwasanMemoryAccessCallbackSized[AccessIsWrite] =
218         checkSanitizerInterfaceFunction(M.getOrInsertFunction(
219             ClMemoryAccessCallbackPrefix + TypeStr + "N" + EndingStr,
220             FunctionType::get(IRB.getVoidTy(), {IntptrTy, IntptrTy}, false)));
221 
222     for (size_t AccessSizeIndex = 0; AccessSizeIndex < kNumberOfAccessSizes;
223          AccessSizeIndex++) {
224       HwasanMemoryAccessCallback[AccessIsWrite][AccessSizeIndex] =
225           checkSanitizerInterfaceFunction(M.getOrInsertFunction(
226               ClMemoryAccessCallbackPrefix + TypeStr +
227                   itostr(1ULL << AccessSizeIndex) + EndingStr,
228               FunctionType::get(IRB.getVoidTy(), {IntptrTy}, false)));
229     }
230   }
231 
232   HwasanTagMemoryFunc = checkSanitizerInterfaceFunction(M.getOrInsertFunction(
233       "__hwasan_tag_memory", IRB.getVoidTy(), IntptrTy, Int8Ty, IntptrTy));
234   HwasanGenerateTagFunc = checkSanitizerInterfaceFunction(
235       M.getOrInsertFunction("__hwasan_generate_tag", Int8Ty));
236 }
237 
238 Value *HWAddressSanitizer::isInterestingMemoryAccess(Instruction *I,
239                                                      bool *IsWrite,
240                                                      uint64_t *TypeSize,
241                                                      unsigned *Alignment,
242                                                      Value **MaybeMask) {
243   // Skip memory accesses inserted by another instrumentation.
244   if (I->getMetadata("nosanitize")) return nullptr;
245 
246   Value *PtrOperand = nullptr;
247   const DataLayout &DL = I->getModule()->getDataLayout();
248   if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
249     if (!ClInstrumentReads) return nullptr;
250     *IsWrite = false;
251     *TypeSize = DL.getTypeStoreSizeInBits(LI->getType());
252     *Alignment = LI->getAlignment();
253     PtrOperand = LI->getPointerOperand();
254   } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
255     if (!ClInstrumentWrites) return nullptr;
256     *IsWrite = true;
257     *TypeSize = DL.getTypeStoreSizeInBits(SI->getValueOperand()->getType());
258     *Alignment = SI->getAlignment();
259     PtrOperand = SI->getPointerOperand();
260   } else if (AtomicRMWInst *RMW = dyn_cast<AtomicRMWInst>(I)) {
261     if (!ClInstrumentAtomics) return nullptr;
262     *IsWrite = true;
263     *TypeSize = DL.getTypeStoreSizeInBits(RMW->getValOperand()->getType());
264     *Alignment = 0;
265     PtrOperand = RMW->getPointerOperand();
266   } else if (AtomicCmpXchgInst *XCHG = dyn_cast<AtomicCmpXchgInst>(I)) {
267     if (!ClInstrumentAtomics) return nullptr;
268     *IsWrite = true;
269     *TypeSize = DL.getTypeStoreSizeInBits(XCHG->getCompareOperand()->getType());
270     *Alignment = 0;
271     PtrOperand = XCHG->getPointerOperand();
272   }
273 
274   if (PtrOperand) {
275     // Do not instrument acesses from different address spaces; we cannot deal
276     // with them.
277     Type *PtrTy = cast<PointerType>(PtrOperand->getType()->getScalarType());
278     if (PtrTy->getPointerAddressSpace() != 0)
279       return nullptr;
280 
281     // Ignore swifterror addresses.
282     // swifterror memory addresses are mem2reg promoted by instruction
283     // selection. As such they cannot have regular uses like an instrumentation
284     // function and it makes no sense to track them as memory.
285     if (PtrOperand->isSwiftError())
286       return nullptr;
287   }
288 
289   return PtrOperand;
290 }
291 
292 static unsigned getPointerOperandIndex(Instruction *I) {
293   if (LoadInst *LI = dyn_cast<LoadInst>(I))
294     return LI->getPointerOperandIndex();
295   if (StoreInst *SI = dyn_cast<StoreInst>(I))
296     return SI->getPointerOperandIndex();
297   if (AtomicRMWInst *RMW = dyn_cast<AtomicRMWInst>(I))
298     return RMW->getPointerOperandIndex();
299   if (AtomicCmpXchgInst *XCHG = dyn_cast<AtomicCmpXchgInst>(I))
300     return XCHG->getPointerOperandIndex();
301   report_fatal_error("Unexpected instruction");
302   return -1;
303 }
304 
305 static size_t TypeSizeToSizeIndex(uint32_t TypeSize) {
306   size_t Res = countTrailingZeros(TypeSize / 8);
307   assert(Res < kNumberOfAccessSizes);
308   return Res;
309 }
310 
311 void HWAddressSanitizer::untagPointerOperand(Instruction *I, Value *Addr) {
312   if (TargetTriple.isAArch64())
313     return;
314 
315   IRBuilder<> IRB(I);
316   Value *AddrLong = IRB.CreatePointerCast(Addr, IntptrTy);
317   Value *UntaggedPtr =
318       IRB.CreateIntToPtr(untagPointer(IRB, AddrLong), Addr->getType());
319   I->setOperand(getPointerOperandIndex(I), UntaggedPtr);
320 }
321 
322 void HWAddressSanitizer::instrumentMemAccessInline(Value *PtrLong, bool IsWrite,
323                                                    unsigned AccessSizeIndex,
324                                                    Instruction *InsertBefore) {
325   IRBuilder<> IRB(InsertBefore);
326   Value *PtrTag = IRB.CreateTrunc(IRB.CreateLShr(PtrLong, kPointerTagShift),
327                                   IRB.getInt8Ty());
328   Value *AddrLong = untagPointer(IRB, PtrLong);
329   Value *ShadowLong = IRB.CreateLShr(AddrLong, kShadowScale);
330   if (ClMappingOffset)
331     ShadowLong = IRB.CreateAdd(
332         ShadowLong, ConstantInt::get(PtrLong->getType(), ClMappingOffset,
333                                      /*isSigned=*/false));
334   Value *MemTag =
335       IRB.CreateLoad(IRB.CreateIntToPtr(ShadowLong, IRB.getInt8PtrTy()));
336   Value *TagMismatch = IRB.CreateICmpNE(PtrTag, MemTag);
337 
338   if (ClMatchAllTag != -1) {
339     Value *TagNotIgnored = IRB.CreateICmpNE(PtrTag,
340         ConstantInt::get(PtrTag->getType(), ClMatchAllTag));
341     TagMismatch = IRB.CreateAnd(TagMismatch, TagNotIgnored);
342   }
343 
344   TerminatorInst *CheckTerm =
345       SplitBlockAndInsertIfThen(TagMismatch, InsertBefore, !Recover,
346                                 MDBuilder(*C).createBranchWeights(1, 100000));
347 
348   IRB.SetInsertPoint(CheckTerm);
349   const int64_t AccessInfo = Recover * 0x20 + IsWrite * 0x10 + AccessSizeIndex;
350   InlineAsm *Asm;
351   switch (TargetTriple.getArch()) {
352     case Triple::x86_64:
353       // The signal handler will find the data address in rdi.
354       Asm = InlineAsm::get(
355           FunctionType::get(IRB.getVoidTy(), {PtrLong->getType()}, false),
356           "int3\nnopl " + itostr(0x40 + AccessInfo) + "(%rax)",
357           "{rdi}",
358           /*hasSideEffects=*/true);
359       break;
360     case Triple::aarch64:
361     case Triple::aarch64_be:
362       // The signal handler will find the data address in x0.
363       Asm = InlineAsm::get(
364           FunctionType::get(IRB.getVoidTy(), {PtrLong->getType()}, false),
365           "brk #" + itostr(0x900 + AccessInfo),
366           "{x0}",
367           /*hasSideEffects=*/true);
368       break;
369     default:
370       report_fatal_error("unsupported architecture");
371   }
372   IRB.CreateCall(Asm, PtrLong);
373 }
374 
375 bool HWAddressSanitizer::instrumentMemAccess(Instruction *I) {
376   DEBUG(dbgs() << "Instrumenting: " << *I << "\n");
377   bool IsWrite = false;
378   unsigned Alignment = 0;
379   uint64_t TypeSize = 0;
380   Value *MaybeMask = nullptr;
381   Value *Addr =
382       isInterestingMemoryAccess(I, &IsWrite, &TypeSize, &Alignment, &MaybeMask);
383 
384   if (!Addr)
385     return false;
386 
387   if (MaybeMask)
388     return false; //FIXME
389 
390   IRBuilder<> IRB(I);
391   Value *AddrLong = IRB.CreatePointerCast(Addr, IntptrTy);
392   if (isPowerOf2_64(TypeSize) &&
393       (TypeSize / 8 <= (1UL << (kNumberOfAccessSizes - 1))) &&
394       (Alignment >= (1UL << kShadowScale) || Alignment == 0 ||
395        Alignment >= TypeSize / 8)) {
396     size_t AccessSizeIndex = TypeSizeToSizeIndex(TypeSize);
397     if (ClInstrumentWithCalls) {
398       IRB.CreateCall(HwasanMemoryAccessCallback[IsWrite][AccessSizeIndex],
399                      AddrLong);
400     } else {
401       instrumentMemAccessInline(AddrLong, IsWrite, AccessSizeIndex, I);
402     }
403   } else {
404     IRB.CreateCall(HwasanMemoryAccessCallbackSized[IsWrite],
405                    {AddrLong, ConstantInt::get(IntptrTy, TypeSize / 8)});
406   }
407   untagPointerOperand(I, Addr);
408 
409   return true;
410 }
411 
412 static uint64_t getAllocaSizeInBytes(const AllocaInst &AI) {
413   uint64_t ArraySize = 1;
414   if (AI.isArrayAllocation()) {
415     const ConstantInt *CI = dyn_cast<ConstantInt>(AI.getArraySize());
416     assert(CI && "non-constant array size");
417     ArraySize = CI->getZExtValue();
418   }
419   Type *Ty = AI.getAllocatedType();
420   uint64_t SizeInBytes = AI.getModule()->getDataLayout().getTypeAllocSize(Ty);
421   return SizeInBytes * ArraySize;
422 }
423 
424 bool HWAddressSanitizer::tagAlloca(IRBuilder<> &IRB, AllocaInst *AI,
425                                    Value *Tag) {
426   size_t Size = (getAllocaSizeInBytes(*AI) + kAllocaAlignment - 1) &
427                 ~(kAllocaAlignment - 1);
428 
429   Value *JustTag = IRB.CreateTrunc(Tag, IRB.getInt8Ty());
430   if (ClInstrumentWithCalls) {
431     IRB.CreateCall(HwasanTagMemoryFunc,
432                    {IRB.CreatePointerCast(AI, IntptrTy), JustTag,
433                     ConstantInt::get(IntptrTy, Size)});
434   } else {
435     size_t ShadowSize = Size >> kShadowScale;
436     Value *ShadowPtr = IRB.CreateIntToPtr(
437         IRB.CreateLShr(IRB.CreatePointerCast(AI, IntptrTy), kShadowScale),
438         IRB.getInt8PtrTy());
439     // If this memset is not inlined, it will be intercepted in the hwasan
440     // runtime library. That's OK, because the interceptor skips the checks if
441     // the address is in the shadow region.
442     // FIXME: the interceptor is not as fast as real memset. Consider lowering
443     // llvm.memset right here into either a sequence of stores, or a call to
444     // hwasan_tag_memory.
445     IRB.CreateMemSet(ShadowPtr, JustTag, ShadowSize, /*Align=*/1);
446   }
447   return true;
448 }
449 
450 static unsigned RetagMask(unsigned AllocaNo) {
451   // A list of 8-bit numbers that have at most one run of non-zero bits.
452   // x = x ^ (mask << 56) can be encoded as a single armv8 instruction for these
453   // masks.
454   // The list does not include the value 255, which is used for UAR.
455   static unsigned FastMasks[] = {
456       0,   1,   2,   3,   4,   6,   7,   8,   12,  14,  15, 16,  24,
457       28,  30,  31,  32,  48,  56,  60,  62,  63,  64,  96, 112, 120,
458       124, 126, 127, 128, 192, 224, 240, 248, 252, 254};
459   return FastMasks[AllocaNo % (sizeof(FastMasks) / sizeof(FastMasks[0]))];
460 }
461 
462 Value *HWAddressSanitizer::getNextTagWithCall(IRBuilder<> &IRB) {
463   return IRB.CreateZExt(IRB.CreateCall(HwasanGenerateTagFunc), IntptrTy);
464 }
465 
466 Value *HWAddressSanitizer::getStackBaseTag(IRBuilder<> &IRB) {
467   if (ClGenerateTagsWithCalls)
468     return nullptr;
469   // FIXME: use addressofreturnaddress (but implement it in aarch64 backend
470   // first).
471   Module *M = IRB.GetInsertBlock()->getParent()->getParent();
472   auto GetStackPointerFn =
473       Intrinsic::getDeclaration(M, Intrinsic::frameaddress);
474   Value *StackPointer = IRB.CreateCall(
475       GetStackPointerFn, {Constant::getNullValue(IRB.getInt32Ty())});
476 
477   // Extract some entropy from the stack pointer for the tags.
478   // Take bits 20..28 (ASLR entropy) and xor with bits 0..8 (these differ
479   // between functions).
480   Value *StackPointerLong = IRB.CreatePointerCast(StackPointer, IntptrTy);
481   Value *StackTag =
482       IRB.CreateXor(StackPointerLong, IRB.CreateLShr(StackPointerLong, 20),
483                     "hwasan.stack.base.tag");
484   return StackTag;
485 }
486 
487 Value *HWAddressSanitizer::getAllocaTag(IRBuilder<> &IRB, Value *StackTag,
488                                         AllocaInst *AI, unsigned AllocaNo) {
489   if (ClGenerateTagsWithCalls)
490     return getNextTagWithCall(IRB);
491   return IRB.CreateXor(StackTag,
492                        ConstantInt::get(IntptrTy, RetagMask(AllocaNo)));
493 }
494 
495 Value *HWAddressSanitizer::getUARTag(IRBuilder<> &IRB, Value *StackTag) {
496   if (ClGenerateTagsWithCalls)
497     return getNextTagWithCall(IRB);
498   return IRB.CreateXor(StackTag, ConstantInt::get(IntptrTy, 0xFFU));
499 }
500 
501 // Add a tag to an address.
502 Value *HWAddressSanitizer::tagPointer(IRBuilder<> &IRB, Type *Ty, Value *PtrLong,
503                                       Value *Tag) {
504   Value *TaggedPtrLong;
505   if (ClEnableKhwasan) {
506     // Kernel addresses have 0xFF in the most significant byte.
507     Value *ShiftedTag = IRB.CreateOr(
508         IRB.CreateShl(Tag, kPointerTagShift),
509         ConstantInt::get(IntptrTy, (1ULL << kPointerTagShift) - 1));
510     TaggedPtrLong = IRB.CreateAnd(PtrLong, ShiftedTag);
511   } else {
512     // Userspace can simply do OR (tag << 56);
513     Value *ShiftedTag = IRB.CreateShl(Tag, kPointerTagShift);
514     TaggedPtrLong = IRB.CreateOr(PtrLong, ShiftedTag);
515   }
516   return IRB.CreateIntToPtr(TaggedPtrLong, Ty);
517 }
518 
519 // Remove tag from an address.
520 Value *HWAddressSanitizer::untagPointer(IRBuilder<> &IRB, Value *PtrLong) {
521   Value *UntaggedPtrLong;
522   if (ClEnableKhwasan) {
523     // Kernel addresses have 0xFF in the most significant byte.
524     UntaggedPtrLong = IRB.CreateOr(PtrLong,
525         ConstantInt::get(PtrLong->getType(), 0xFFULL << kPointerTagShift));
526   } else {
527     // Userspace addresses have 0x00.
528     UntaggedPtrLong = IRB.CreateAnd(PtrLong,
529         ConstantInt::get(PtrLong->getType(), ~(0xFFULL << kPointerTagShift)));
530   }
531   return UntaggedPtrLong;
532 }
533 
534 bool HWAddressSanitizer::instrumentStack(
535     SmallVectorImpl<AllocaInst *> &Allocas,
536     SmallVectorImpl<Instruction *> &RetVec) {
537   Function *F = Allocas[0]->getParent()->getParent();
538   Instruction *InsertPt = &*F->getEntryBlock().begin();
539   IRBuilder<> IRB(InsertPt);
540 
541   Value *StackTag = getStackBaseTag(IRB);
542 
543   // Ideally, we want to calculate tagged stack base pointer, and rewrite all
544   // alloca addresses using that. Unfortunately, offsets are not known yet
545   // (unless we use ASan-style mega-alloca). Instead we keep the base tag in a
546   // temp, shift-OR it into each alloca address and xor with the retag mask.
547   // This generates one extra instruction per alloca use.
548   for (unsigned N = 0; N < Allocas.size(); ++N) {
549     auto *AI = Allocas[N];
550     IRB.SetInsertPoint(AI->getNextNode());
551 
552     // Replace uses of the alloca with tagged address.
553     Value *Tag = getAllocaTag(IRB, StackTag, AI, N);
554     Value *AILong = IRB.CreatePointerCast(AI, IntptrTy);
555     Value *Replacement = tagPointer(IRB, AI->getType(), AILong, Tag);
556     std::string Name =
557         AI->hasName() ? AI->getName().str() : "alloca." + itostr(N);
558     Replacement->setName(Name + ".hwasan");
559 
560     for (auto UI = AI->use_begin(), UE = AI->use_end(); UI != UE;) {
561       Use &U = *UI++;
562       if (U.getUser() != AILong)
563         U.set(Replacement);
564     }
565 
566     tagAlloca(IRB, AI, Tag);
567 
568     for (auto RI : RetVec) {
569       IRB.SetInsertPoint(RI);
570 
571       // Re-tag alloca memory with the special UAR tag.
572       Value *Tag = getUARTag(IRB, StackTag);
573       tagAlloca(IRB, AI, Tag);
574     }
575   }
576 
577   return true;
578 }
579 
580 bool HWAddressSanitizer::isInterestingAlloca(const AllocaInst &AI) {
581   return (AI.getAllocatedType()->isSized() &&
582           // FIXME: instrument dynamic allocas, too
583           AI.isStaticAlloca() &&
584           // alloca() may be called with 0 size, ignore it.
585           getAllocaSizeInBytes(AI) > 0 &&
586           // We are only interested in allocas not promotable to registers.
587           // Promotable allocas are common under -O0.
588           !isAllocaPromotable(&AI) &&
589           // inalloca allocas are not treated as static, and we don't want
590           // dynamic alloca instrumentation for them as well.
591           !AI.isUsedWithInAlloca() &&
592           // swifterror allocas are register promoted by ISel
593           !AI.isSwiftError());
594 }
595 
596 bool HWAddressSanitizer::runOnFunction(Function &F) {
597   if (&F == HwasanCtorFunction)
598     return false;
599 
600   if (!F.hasFnAttribute(Attribute::SanitizeHWAddress))
601     return false;
602 
603   DEBUG(dbgs() << "Function: " << F.getName() << "\n");
604 
605   initializeCallbacks(*F.getParent());
606 
607   bool Changed = false;
608   SmallVector<Instruction*, 16> ToInstrument;
609   SmallVector<AllocaInst*, 8> AllocasToInstrument;
610   SmallVector<Instruction*, 8> RetVec;
611   for (auto &BB : F) {
612     for (auto &Inst : BB) {
613       if (ClInstrumentStack)
614         if (AllocaInst *AI = dyn_cast<AllocaInst>(&Inst)) {
615           // Realign all allocas. We don't want small uninteresting allocas to
616           // hide in instrumented alloca's padding.
617           if (AI->getAlignment() < kAllocaAlignment)
618             AI->setAlignment(kAllocaAlignment);
619           // Instrument some of them.
620           if (isInterestingAlloca(*AI))
621             AllocasToInstrument.push_back(AI);
622           continue;
623         }
624 
625       if (isa<ReturnInst>(Inst) || isa<ResumeInst>(Inst) || isa<CleanupReturnInst>(Inst))
626         RetVec.push_back(&Inst);
627 
628       Value *MaybeMask = nullptr;
629       bool IsWrite;
630       unsigned Alignment;
631       uint64_t TypeSize;
632       Value *Addr = isInterestingMemoryAccess(&Inst, &IsWrite, &TypeSize,
633                                               &Alignment, &MaybeMask);
634       if (Addr || isa<MemIntrinsic>(Inst))
635         ToInstrument.push_back(&Inst);
636     }
637   }
638 
639   if (!AllocasToInstrument.empty())
640     Changed |= instrumentStack(AllocasToInstrument, RetVec);
641 
642   for (auto Inst : ToInstrument)
643     Changed |= instrumentMemAccess(Inst);
644 
645   return Changed;
646 }
647