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