1 //===- HWAddressSanitizer.cpp - detector of uninitialized reads -------===//
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 /// \file
10 /// This file is a part of HWAddressSanitizer, an address sanity checker
11 /// based on tagged addressing.
12 //===----------------------------------------------------------------------===//
13 
14 #include "llvm/Transforms/Instrumentation/HWAddressSanitizer.h"
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/DebugInfoMetadata.h"
25 #include "llvm/IR/DerivedTypes.h"
26 #include "llvm/IR/Function.h"
27 #include "llvm/IR/IRBuilder.h"
28 #include "llvm/IR/InlineAsm.h"
29 #include "llvm/IR/InstVisitor.h"
30 #include "llvm/IR/Instruction.h"
31 #include "llvm/IR/Instructions.h"
32 #include "llvm/IR/IntrinsicInst.h"
33 #include "llvm/IR/Intrinsics.h"
34 #include "llvm/IR/LLVMContext.h"
35 #include "llvm/IR/MDBuilder.h"
36 #include "llvm/IR/Module.h"
37 #include "llvm/IR/Type.h"
38 #include "llvm/IR/Value.h"
39 #include "llvm/Pass.h"
40 #include "llvm/Support/Casting.h"
41 #include "llvm/Support/CommandLine.h"
42 #include "llvm/Support/Debug.h"
43 #include "llvm/Support/raw_ostream.h"
44 #include "llvm/Transforms/Instrumentation.h"
45 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
46 #include "llvm/Transforms/Utils/ModuleUtils.h"
47 #include "llvm/Transforms/Utils/PromoteMemToReg.h"
48 #include <sstream>
49 
50 using namespace llvm;
51 
52 #define DEBUG_TYPE "hwasan"
53 
54 static const char *const kHwasanModuleCtorName = "hwasan.module_ctor";
55 static const char *const kHwasanInitName = "__hwasan_init";
56 
57 static const char *const kHwasanShadowMemoryDynamicAddress =
58     "__hwasan_shadow_memory_dynamic_address";
59 
60 // Accesses sizes are powers of two: 1, 2, 4, 8, 16.
61 static const size_t kNumberOfAccessSizes = 5;
62 
63 static const size_t kDefaultShadowScale = 4;
64 static const uint64_t kDynamicShadowSentinel =
65     std::numeric_limits<uint64_t>::max();
66 static const unsigned kPointerTagShift = 56;
67 
68 static const unsigned kShadowBaseAlignment = 32;
69 
70 static cl::opt<std::string> ClMemoryAccessCallbackPrefix(
71     "hwasan-memory-access-callback-prefix",
72     cl::desc("Prefix for memory access callbacks"), cl::Hidden,
73     cl::init("__hwasan_"));
74 
75 static cl::opt<bool>
76     ClInstrumentWithCalls("hwasan-instrument-with-calls",
77                 cl::desc("instrument reads and writes with callbacks"),
78                 cl::Hidden, cl::init(false));
79 
80 static cl::opt<bool> ClInstrumentReads("hwasan-instrument-reads",
81                                        cl::desc("instrument read instructions"),
82                                        cl::Hidden, cl::init(true));
83 
84 static cl::opt<bool> ClInstrumentWrites(
85     "hwasan-instrument-writes", cl::desc("instrument write instructions"),
86     cl::Hidden, cl::init(true));
87 
88 static cl::opt<bool> ClInstrumentAtomics(
89     "hwasan-instrument-atomics",
90     cl::desc("instrument atomic instructions (rmw, cmpxchg)"), cl::Hidden,
91     cl::init(true));
92 
93 static cl::opt<bool> ClRecover(
94     "hwasan-recover",
95     cl::desc("Enable recovery mode (continue-after-error)."),
96     cl::Hidden, cl::init(false));
97 
98 static cl::opt<bool> ClInstrumentStack("hwasan-instrument-stack",
99                                        cl::desc("instrument stack (allocas)"),
100                                        cl::Hidden, cl::init(true));
101 
102 static cl::opt<bool> ClUARRetagToZero(
103     "hwasan-uar-retag-to-zero",
104     cl::desc("Clear alloca tags before returning from the function to allow "
105              "non-instrumented and instrumented function calls mix. When set "
106              "to false, allocas are retagged before returning from the "
107              "function to detect use after return."),
108     cl::Hidden, cl::init(true));
109 
110 static cl::opt<bool> ClGenerateTagsWithCalls(
111     "hwasan-generate-tags-with-calls",
112     cl::desc("generate new tags with runtime library calls"), cl::Hidden,
113     cl::init(false));
114 
115 static cl::opt<int> ClMatchAllTag(
116     "hwasan-match-all-tag",
117     cl::desc("don't report bad accesses via pointers with this tag"),
118     cl::Hidden, cl::init(-1));
119 
120 static cl::opt<bool> ClEnableKhwasan(
121     "hwasan-kernel",
122     cl::desc("Enable KernelHWAddressSanitizer instrumentation"),
123     cl::Hidden, cl::init(false));
124 
125 // These flags allow to change the shadow mapping and control how shadow memory
126 // is accessed. The shadow mapping looks like:
127 //    Shadow = (Mem >> scale) + offset
128 
129 static cl::opt<uint64_t>
130     ClMappingOffset("hwasan-mapping-offset",
131                     cl::desc("HWASan shadow mapping offset [EXPERIMENTAL]"),
132                     cl::Hidden, cl::init(0));
133 
134 static cl::opt<bool>
135     ClWithIfunc("hwasan-with-ifunc",
136                 cl::desc("Access dynamic shadow through an ifunc global on "
137                          "platforms that support this"),
138                 cl::Hidden, cl::init(false));
139 
140 static cl::opt<bool> ClWithTls(
141     "hwasan-with-tls",
142     cl::desc("Access dynamic shadow through an thread-local pointer on "
143              "platforms that support this"),
144     cl::Hidden, cl::init(true));
145 
146 static cl::opt<bool>
147     ClRecordStackHistory("hwasan-record-stack-history",
148                          cl::desc("Record stack frames with tagged allocations "
149                                   "in a thread-local ring buffer"),
150                          cl::Hidden, cl::init(true));
151 static cl::opt<bool>
152     ClInstrumentMemIntrinsics("hwasan-instrument-mem-intrinsics",
153                               cl::desc("instrument memory intrinsics"),
154                               cl::Hidden, cl::init(true));
155 
156 static cl::opt<bool>
157     ClInstrumentLandingPads("hwasan-instrument-landing-pads",
158                               cl::desc("instrument landing pads"), cl::Hidden,
159                               cl::init(true));
160 
161 static cl::opt<bool> ClInlineAllChecks("hwasan-inline-all-checks",
162                                        cl::desc("inline all checks"),
163                                        cl::Hidden, cl::init(false));
164 
165 namespace {
166 
167 /// An instrumentation pass implementing detection of addressability bugs
168 /// using tagged pointers.
169 class HWAddressSanitizer {
170 public:
171   explicit HWAddressSanitizer(Module &M, bool CompileKernel = false,
172                               bool Recover = false) {
173     this->Recover = ClRecover.getNumOccurrences() > 0 ? ClRecover : Recover;
174     this->CompileKernel = ClEnableKhwasan.getNumOccurrences() > 0 ?
175         ClEnableKhwasan : CompileKernel;
176 
177     initializeModule(M);
178   }
179 
180   bool sanitizeFunction(Function &F);
181   void initializeModule(Module &M);
182 
183   void initializeCallbacks(Module &M);
184 
185   Value *getDynamicShadowIfunc(IRBuilder<> &IRB);
186   Value *getDynamicShadowNonTls(IRBuilder<> &IRB);
187 
188   void untagPointerOperand(Instruction *I, Value *Addr);
189   Value *shadowBase();
190   Value *memToShadow(Value *Shadow, IRBuilder<> &IRB);
191   void instrumentMemAccessInline(Value *Ptr, bool IsWrite,
192                                  unsigned AccessSizeIndex,
193                                  Instruction *InsertBefore);
194   void instrumentMemIntrinsic(MemIntrinsic *MI);
195   bool instrumentMemAccess(Instruction *I);
196   Value *isInterestingMemoryAccess(Instruction *I, bool *IsWrite,
197                                    uint64_t *TypeSize, unsigned *Alignment,
198                                    Value **MaybeMask);
199 
200   bool isInterestingAlloca(const AllocaInst &AI);
201   bool tagAlloca(IRBuilder<> &IRB, AllocaInst *AI, Value *Tag, size_t Size);
202   Value *tagPointer(IRBuilder<> &IRB, Type *Ty, Value *PtrLong, Value *Tag);
203   Value *untagPointer(IRBuilder<> &IRB, Value *PtrLong);
204   bool instrumentStack(
205       SmallVectorImpl<AllocaInst *> &Allocas,
206       DenseMap<AllocaInst *, std::vector<DbgDeclareInst *>> &AllocaDeclareMap,
207       SmallVectorImpl<Instruction *> &RetVec, Value *StackTag);
208   Value *readRegister(IRBuilder<> &IRB, StringRef Name);
209   bool instrumentLandingPads(SmallVectorImpl<Instruction *> &RetVec);
210   Value *getNextTagWithCall(IRBuilder<> &IRB);
211   Value *getStackBaseTag(IRBuilder<> &IRB);
212   Value *getAllocaTag(IRBuilder<> &IRB, Value *StackTag, AllocaInst *AI,
213                      unsigned AllocaNo);
214   Value *getUARTag(IRBuilder<> &IRB, Value *StackTag);
215 
216   Value *getHwasanThreadSlotPtr(IRBuilder<> &IRB, Type *Ty);
217   void emitPrologue(IRBuilder<> &IRB, bool WithFrameRecord);
218 
219 private:
220   LLVMContext *C;
221   Triple TargetTriple;
222   FunctionCallee HWAsanMemmove, HWAsanMemcpy, HWAsanMemset;
223   FunctionCallee HWAsanHandleVfork;
224 
225   /// This struct defines the shadow mapping using the rule:
226   ///   shadow = (mem >> Scale) + Offset.
227   /// If InGlobal is true, then
228   ///   extern char __hwasan_shadow[];
229   ///   shadow = (mem >> Scale) + &__hwasan_shadow
230   /// If InTls is true, then
231   ///   extern char *__hwasan_tls;
232   ///   shadow = (mem>>Scale) + align_up(__hwasan_shadow, kShadowBaseAlignment)
233   struct ShadowMapping {
234     int Scale;
235     uint64_t Offset;
236     bool InGlobal;
237     bool InTls;
238 
239     void init(Triple &TargetTriple);
240     unsigned getAllocaAlignment() const { return 1U << Scale; }
241   };
242   ShadowMapping Mapping;
243 
244   Type *IntptrTy;
245   Type *Int8PtrTy;
246   Type *Int8Ty;
247   Type *Int32Ty;
248 
249   bool CompileKernel;
250   bool Recover;
251 
252   Function *HwasanCtorFunction;
253 
254   FunctionCallee HwasanMemoryAccessCallback[2][kNumberOfAccessSizes];
255   FunctionCallee HwasanMemoryAccessCallbackSized[2];
256 
257   FunctionCallee HwasanTagMemoryFunc;
258   FunctionCallee HwasanGenerateTagFunc;
259   FunctionCallee HwasanThreadEnterFunc;
260 
261   Constant *ShadowGlobal;
262 
263   Value *LocalDynamicShadow = nullptr;
264   Value *StackBaseTag = nullptr;
265   GlobalValue *ThreadPtrGlobal = nullptr;
266 };
267 
268 class HWAddressSanitizerLegacyPass : public FunctionPass {
269 public:
270   // Pass identification, replacement for typeid.
271   static char ID;
272 
273   explicit HWAddressSanitizerLegacyPass(bool CompileKernel = false,
274                                         bool Recover = false)
275       : FunctionPass(ID), CompileKernel(CompileKernel), Recover(Recover) {}
276 
277   StringRef getPassName() const override { return "HWAddressSanitizer"; }
278 
279   bool doInitialization(Module &M) override {
280     HWASan = llvm::make_unique<HWAddressSanitizer>(M, CompileKernel, Recover);
281     return true;
282   }
283 
284   bool runOnFunction(Function &F) override {
285     return HWASan->sanitizeFunction(F);
286   }
287 
288   bool doFinalization(Module &M) override {
289     HWASan.reset();
290     return false;
291   }
292 
293 private:
294   std::unique_ptr<HWAddressSanitizer> HWASan;
295   bool CompileKernel;
296   bool Recover;
297 };
298 
299 } // end anonymous namespace
300 
301 char HWAddressSanitizerLegacyPass::ID = 0;
302 
303 INITIALIZE_PASS_BEGIN(
304     HWAddressSanitizerLegacyPass, "hwasan",
305     "HWAddressSanitizer: detect memory bugs using tagged addressing.", false,
306     false)
307 INITIALIZE_PASS_END(
308     HWAddressSanitizerLegacyPass, "hwasan",
309     "HWAddressSanitizer: detect memory bugs using tagged addressing.", false,
310     false)
311 
312 FunctionPass *llvm::createHWAddressSanitizerLegacyPassPass(bool CompileKernel,
313                                                            bool Recover) {
314   assert(!CompileKernel || Recover);
315   return new HWAddressSanitizerLegacyPass(CompileKernel, Recover);
316 }
317 
318 HWAddressSanitizerPass::HWAddressSanitizerPass(bool CompileKernel, bool Recover)
319     : CompileKernel(CompileKernel), Recover(Recover) {}
320 
321 PreservedAnalyses HWAddressSanitizerPass::run(Module &M,
322                                               ModuleAnalysisManager &MAM) {
323   HWAddressSanitizer HWASan(M, CompileKernel, Recover);
324   bool Modified = false;
325   for (Function &F : M)
326     Modified |= HWASan.sanitizeFunction(F);
327   if (Modified)
328     return PreservedAnalyses::none();
329   return PreservedAnalyses::all();
330 }
331 
332 /// Module-level initialization.
333 ///
334 /// inserts a call to __hwasan_init to the module's constructor list.
335 void HWAddressSanitizer::initializeModule(Module &M) {
336   LLVM_DEBUG(dbgs() << "Init " << M.getName() << "\n");
337   auto &DL = M.getDataLayout();
338 
339   TargetTriple = Triple(M.getTargetTriple());
340 
341   Mapping.init(TargetTriple);
342 
343   C = &(M.getContext());
344   IRBuilder<> IRB(*C);
345   IntptrTy = IRB.getIntPtrTy(DL);
346   Int8PtrTy = IRB.getInt8PtrTy();
347   Int8Ty = IRB.getInt8Ty();
348   Int32Ty = IRB.getInt32Ty();
349 
350   HwasanCtorFunction = nullptr;
351   if (!CompileKernel) {
352     std::tie(HwasanCtorFunction, std::ignore) =
353         getOrCreateSanitizerCtorAndInitFunctions(
354             M, kHwasanModuleCtorName, kHwasanInitName,
355             /*InitArgTypes=*/{},
356             /*InitArgs=*/{},
357             // This callback is invoked when the functions are created the first
358             // time. Hook them into the global ctors list in that case:
359             [&](Function *Ctor, FunctionCallee) {
360               Comdat *CtorComdat = M.getOrInsertComdat(kHwasanModuleCtorName);
361               Ctor->setComdat(CtorComdat);
362               appendToGlobalCtors(M, Ctor, 0, Ctor);
363             });
364   }
365 
366   if (!TargetTriple.isAndroid()) {
367     Constant *C = M.getOrInsertGlobal("__hwasan_tls", IntptrTy, [&] {
368       auto *GV = new GlobalVariable(M, IntptrTy, /*isConstant=*/false,
369                                     GlobalValue::ExternalLinkage, nullptr,
370                                     "__hwasan_tls", nullptr,
371                                     GlobalVariable::InitialExecTLSModel);
372       appendToCompilerUsed(M, GV);
373       return GV;
374     });
375     ThreadPtrGlobal = cast<GlobalVariable>(C);
376   }
377 }
378 
379 void HWAddressSanitizer::initializeCallbacks(Module &M) {
380   IRBuilder<> IRB(*C);
381   for (size_t AccessIsWrite = 0; AccessIsWrite <= 1; AccessIsWrite++) {
382     const std::string TypeStr = AccessIsWrite ? "store" : "load";
383     const std::string EndingStr = Recover ? "_noabort" : "";
384 
385     HwasanMemoryAccessCallbackSized[AccessIsWrite] = M.getOrInsertFunction(
386         ClMemoryAccessCallbackPrefix + TypeStr + "N" + EndingStr,
387         FunctionType::get(IRB.getVoidTy(), {IntptrTy, IntptrTy}, false));
388 
389     for (size_t AccessSizeIndex = 0; AccessSizeIndex < kNumberOfAccessSizes;
390          AccessSizeIndex++) {
391       HwasanMemoryAccessCallback[AccessIsWrite][AccessSizeIndex] =
392           M.getOrInsertFunction(
393               ClMemoryAccessCallbackPrefix + TypeStr +
394                   itostr(1ULL << AccessSizeIndex) + EndingStr,
395               FunctionType::get(IRB.getVoidTy(), {IntptrTy}, false));
396     }
397   }
398 
399   HwasanTagMemoryFunc = M.getOrInsertFunction(
400       "__hwasan_tag_memory", IRB.getVoidTy(), Int8PtrTy, Int8Ty, IntptrTy);
401   HwasanGenerateTagFunc =
402       M.getOrInsertFunction("__hwasan_generate_tag", Int8Ty);
403 
404   ShadowGlobal = M.getOrInsertGlobal("__hwasan_shadow",
405                                      ArrayType::get(IRB.getInt8Ty(), 0));
406 
407   const std::string MemIntrinCallbackPrefix =
408       CompileKernel ? std::string("") : ClMemoryAccessCallbackPrefix;
409   HWAsanMemmove = M.getOrInsertFunction(MemIntrinCallbackPrefix + "memmove",
410                                         IRB.getInt8PtrTy(), IRB.getInt8PtrTy(),
411                                         IRB.getInt8PtrTy(), IntptrTy);
412   HWAsanMemcpy = M.getOrInsertFunction(MemIntrinCallbackPrefix + "memcpy",
413                                        IRB.getInt8PtrTy(), IRB.getInt8PtrTy(),
414                                        IRB.getInt8PtrTy(), IntptrTy);
415   HWAsanMemset = M.getOrInsertFunction(MemIntrinCallbackPrefix + "memset",
416                                        IRB.getInt8PtrTy(), IRB.getInt8PtrTy(),
417                                        IRB.getInt32Ty(), IntptrTy);
418 
419   HWAsanHandleVfork =
420       M.getOrInsertFunction("__hwasan_handle_vfork", IRB.getVoidTy(), IntptrTy);
421 
422   HwasanThreadEnterFunc =
423       M.getOrInsertFunction("__hwasan_thread_enter", IRB.getVoidTy());
424 }
425 
426 Value *HWAddressSanitizer::getDynamicShadowIfunc(IRBuilder<> &IRB) {
427   // An empty inline asm with input reg == output reg.
428   // An opaque no-op cast, basically.
429   InlineAsm *Asm = InlineAsm::get(
430       FunctionType::get(Int8PtrTy, {ShadowGlobal->getType()}, false),
431       StringRef(""), StringRef("=r,0"),
432       /*hasSideEffects=*/false);
433   return IRB.CreateCall(Asm, {ShadowGlobal}, ".hwasan.shadow");
434 }
435 
436 Value *HWAddressSanitizer::getDynamicShadowNonTls(IRBuilder<> &IRB) {
437   // Generate code only when dynamic addressing is needed.
438   if (Mapping.Offset != kDynamicShadowSentinel)
439     return nullptr;
440 
441   if (Mapping.InGlobal) {
442     return getDynamicShadowIfunc(IRB);
443   } else {
444     Value *GlobalDynamicAddress =
445         IRB.GetInsertBlock()->getParent()->getParent()->getOrInsertGlobal(
446             kHwasanShadowMemoryDynamicAddress, Int8PtrTy);
447     return IRB.CreateLoad(Int8PtrTy, GlobalDynamicAddress);
448   }
449 }
450 
451 Value *HWAddressSanitizer::isInterestingMemoryAccess(Instruction *I,
452                                                      bool *IsWrite,
453                                                      uint64_t *TypeSize,
454                                                      unsigned *Alignment,
455                                                      Value **MaybeMask) {
456   // Skip memory accesses inserted by another instrumentation.
457   if (I->getMetadata("nosanitize")) return nullptr;
458 
459   // Do not instrument the load fetching the dynamic shadow address.
460   if (LocalDynamicShadow == I)
461     return nullptr;
462 
463   Value *PtrOperand = nullptr;
464   const DataLayout &DL = I->getModule()->getDataLayout();
465   if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
466     if (!ClInstrumentReads) return nullptr;
467     *IsWrite = false;
468     *TypeSize = DL.getTypeStoreSizeInBits(LI->getType());
469     *Alignment = LI->getAlignment();
470     PtrOperand = LI->getPointerOperand();
471   } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
472     if (!ClInstrumentWrites) return nullptr;
473     *IsWrite = true;
474     *TypeSize = DL.getTypeStoreSizeInBits(SI->getValueOperand()->getType());
475     *Alignment = SI->getAlignment();
476     PtrOperand = SI->getPointerOperand();
477   } else if (AtomicRMWInst *RMW = dyn_cast<AtomicRMWInst>(I)) {
478     if (!ClInstrumentAtomics) return nullptr;
479     *IsWrite = true;
480     *TypeSize = DL.getTypeStoreSizeInBits(RMW->getValOperand()->getType());
481     *Alignment = 0;
482     PtrOperand = RMW->getPointerOperand();
483   } else if (AtomicCmpXchgInst *XCHG = dyn_cast<AtomicCmpXchgInst>(I)) {
484     if (!ClInstrumentAtomics) return nullptr;
485     *IsWrite = true;
486     *TypeSize = DL.getTypeStoreSizeInBits(XCHG->getCompareOperand()->getType());
487     *Alignment = 0;
488     PtrOperand = XCHG->getPointerOperand();
489   }
490 
491   if (PtrOperand) {
492     // Do not instrument accesses from different address spaces; we cannot deal
493     // with them.
494     Type *PtrTy = cast<PointerType>(PtrOperand->getType()->getScalarType());
495     if (PtrTy->getPointerAddressSpace() != 0)
496       return nullptr;
497 
498     // Ignore swifterror addresses.
499     // swifterror memory addresses are mem2reg promoted by instruction
500     // selection. As such they cannot have regular uses like an instrumentation
501     // function and it makes no sense to track them as memory.
502     if (PtrOperand->isSwiftError())
503       return nullptr;
504   }
505 
506   return PtrOperand;
507 }
508 
509 static unsigned getPointerOperandIndex(Instruction *I) {
510   if (LoadInst *LI = dyn_cast<LoadInst>(I))
511     return LI->getPointerOperandIndex();
512   if (StoreInst *SI = dyn_cast<StoreInst>(I))
513     return SI->getPointerOperandIndex();
514   if (AtomicRMWInst *RMW = dyn_cast<AtomicRMWInst>(I))
515     return RMW->getPointerOperandIndex();
516   if (AtomicCmpXchgInst *XCHG = dyn_cast<AtomicCmpXchgInst>(I))
517     return XCHG->getPointerOperandIndex();
518   report_fatal_error("Unexpected instruction");
519   return -1;
520 }
521 
522 static size_t TypeSizeToSizeIndex(uint32_t TypeSize) {
523   size_t Res = countTrailingZeros(TypeSize / 8);
524   assert(Res < kNumberOfAccessSizes);
525   return Res;
526 }
527 
528 void HWAddressSanitizer::untagPointerOperand(Instruction *I, Value *Addr) {
529   if (TargetTriple.isAArch64())
530     return;
531 
532   IRBuilder<> IRB(I);
533   Value *AddrLong = IRB.CreatePointerCast(Addr, IntptrTy);
534   Value *UntaggedPtr =
535       IRB.CreateIntToPtr(untagPointer(IRB, AddrLong), Addr->getType());
536   I->setOperand(getPointerOperandIndex(I), UntaggedPtr);
537 }
538 
539 Value *HWAddressSanitizer::shadowBase() {
540   if (LocalDynamicShadow)
541     return LocalDynamicShadow;
542   return ConstantExpr::getIntToPtr(ConstantInt::get(IntptrTy, Mapping.Offset),
543                                    Int8PtrTy);
544 }
545 
546 Value *HWAddressSanitizer::memToShadow(Value *Mem, IRBuilder<> &IRB) {
547   // Mem >> Scale
548   Value *Shadow = IRB.CreateLShr(Mem, Mapping.Scale);
549   if (Mapping.Offset == 0)
550     return IRB.CreateIntToPtr(Shadow, Int8PtrTy);
551   // (Mem >> Scale) + Offset
552   return IRB.CreateGEP(Int8Ty, shadowBase(), Shadow);
553 }
554 
555 void HWAddressSanitizer::instrumentMemAccessInline(Value *Ptr, bool IsWrite,
556                                                    unsigned AccessSizeIndex,
557                                                    Instruction *InsertBefore) {
558   const int64_t AccessInfo = Recover * 0x20 + IsWrite * 0x10 + AccessSizeIndex;
559   IRBuilder<> IRB(InsertBefore);
560 
561   if (!ClInlineAllChecks && TargetTriple.isAArch64() &&
562       TargetTriple.isOSBinFormatELF() && !Recover) {
563     Module *M = IRB.GetInsertBlock()->getParent()->getParent();
564     Ptr = IRB.CreateBitCast(Ptr, Int8PtrTy);
565     IRB.CreateCall(
566         Intrinsic::getDeclaration(M, Intrinsic::hwasan_check_memaccess),
567         {shadowBase(), Ptr, ConstantInt::get(Int32Ty, AccessInfo)});
568     return;
569   }
570 
571   Value *PtrLong = IRB.CreatePointerCast(Ptr, IntptrTy);
572   Value *PtrTag = IRB.CreateTrunc(IRB.CreateLShr(PtrLong, kPointerTagShift),
573                                   IRB.getInt8Ty());
574   Value *AddrLong = untagPointer(IRB, PtrLong);
575   Value *Shadow = memToShadow(AddrLong, IRB);
576   Value *MemTag = IRB.CreateLoad(Int8Ty, Shadow);
577   Value *TagMismatch = IRB.CreateICmpNE(PtrTag, MemTag);
578 
579   int matchAllTag = ClMatchAllTag.getNumOccurrences() > 0 ?
580       ClMatchAllTag : (CompileKernel ? 0xFF : -1);
581   if (matchAllTag != -1) {
582     Value *TagNotIgnored = IRB.CreateICmpNE(PtrTag,
583         ConstantInt::get(PtrTag->getType(), matchAllTag));
584     TagMismatch = IRB.CreateAnd(TagMismatch, TagNotIgnored);
585   }
586 
587   Instruction *CheckTerm =
588       SplitBlockAndInsertIfThen(TagMismatch, InsertBefore, false,
589                                 MDBuilder(*C).createBranchWeights(1, 100000));
590 
591   IRB.SetInsertPoint(CheckTerm);
592   Value *OutOfShortGranuleTagRange =
593       IRB.CreateICmpUGT(MemTag, ConstantInt::get(Int8Ty, 15));
594   Instruction *CheckFailTerm =
595       SplitBlockAndInsertIfThen(OutOfShortGranuleTagRange, CheckTerm, !Recover,
596                                 MDBuilder(*C).createBranchWeights(1, 100000));
597 
598   IRB.SetInsertPoint(CheckTerm);
599   Value *PtrLowBits = IRB.CreateTrunc(IRB.CreateAnd(PtrLong, 15), Int8Ty);
600   PtrLowBits = IRB.CreateAdd(
601       PtrLowBits, ConstantInt::get(Int8Ty, (1 << AccessSizeIndex) - 1));
602   Value *PtrLowBitsOOB = IRB.CreateICmpUGE(PtrLowBits, MemTag);
603   SplitBlockAndInsertIfThen(PtrLowBitsOOB, CheckTerm, false,
604                             MDBuilder(*C).createBranchWeights(1, 100000),
605                             nullptr, nullptr, CheckFailTerm->getParent());
606 
607   IRB.SetInsertPoint(CheckTerm);
608   Value *InlineTagAddr = IRB.CreateOr(AddrLong, 15);
609   InlineTagAddr = IRB.CreateIntToPtr(InlineTagAddr, Int8PtrTy);
610   Value *InlineTag = IRB.CreateLoad(Int8Ty, InlineTagAddr);
611   Value *InlineTagMismatch = IRB.CreateICmpNE(PtrTag, InlineTag);
612   SplitBlockAndInsertIfThen(InlineTagMismatch, CheckTerm, false,
613                             MDBuilder(*C).createBranchWeights(1, 100000),
614                             nullptr, nullptr, CheckFailTerm->getParent());
615 
616   IRB.SetInsertPoint(CheckFailTerm);
617   InlineAsm *Asm;
618   switch (TargetTriple.getArch()) {
619     case Triple::x86_64:
620       // The signal handler will find the data address in rdi.
621       Asm = InlineAsm::get(
622           FunctionType::get(IRB.getVoidTy(), {PtrLong->getType()}, false),
623           "int3\nnopl " + itostr(0x40 + AccessInfo) + "(%rax)",
624           "{rdi}",
625           /*hasSideEffects=*/true);
626       break;
627     case Triple::aarch64:
628     case Triple::aarch64_be:
629       // The signal handler will find the data address in x0.
630       Asm = InlineAsm::get(
631           FunctionType::get(IRB.getVoidTy(), {PtrLong->getType()}, false),
632           "brk #" + itostr(0x900 + AccessInfo),
633           "{x0}",
634           /*hasSideEffects=*/true);
635       break;
636     default:
637       report_fatal_error("unsupported architecture");
638   }
639   IRB.CreateCall(Asm, PtrLong);
640   if (Recover)
641     cast<BranchInst>(CheckFailTerm)->setSuccessor(0, CheckTerm->getParent());
642 }
643 
644 void HWAddressSanitizer::instrumentMemIntrinsic(MemIntrinsic *MI) {
645   IRBuilder<> IRB(MI);
646   if (isa<MemTransferInst>(MI)) {
647     IRB.CreateCall(
648         isa<MemMoveInst>(MI) ? HWAsanMemmove : HWAsanMemcpy,
649         {IRB.CreatePointerCast(MI->getOperand(0), IRB.getInt8PtrTy()),
650          IRB.CreatePointerCast(MI->getOperand(1), IRB.getInt8PtrTy()),
651          IRB.CreateIntCast(MI->getOperand(2), IntptrTy, false)});
652   } else if (isa<MemSetInst>(MI)) {
653     IRB.CreateCall(
654         HWAsanMemset,
655         {IRB.CreatePointerCast(MI->getOperand(0), IRB.getInt8PtrTy()),
656          IRB.CreateIntCast(MI->getOperand(1), IRB.getInt32Ty(), false),
657          IRB.CreateIntCast(MI->getOperand(2), IntptrTy, false)});
658   }
659   MI->eraseFromParent();
660 }
661 
662 bool HWAddressSanitizer::instrumentMemAccess(Instruction *I) {
663   LLVM_DEBUG(dbgs() << "Instrumenting: " << *I << "\n");
664   bool IsWrite = false;
665   unsigned Alignment = 0;
666   uint64_t TypeSize = 0;
667   Value *MaybeMask = nullptr;
668 
669   if (ClInstrumentMemIntrinsics && isa<MemIntrinsic>(I)) {
670     instrumentMemIntrinsic(cast<MemIntrinsic>(I));
671     return true;
672   }
673 
674   Value *Addr =
675       isInterestingMemoryAccess(I, &IsWrite, &TypeSize, &Alignment, &MaybeMask);
676 
677   if (!Addr)
678     return false;
679 
680   if (MaybeMask)
681     return false; //FIXME
682 
683   IRBuilder<> IRB(I);
684   if (isPowerOf2_64(TypeSize) &&
685       (TypeSize / 8 <= (1UL << (kNumberOfAccessSizes - 1))) &&
686       (Alignment >= (1UL << Mapping.Scale) || Alignment == 0 ||
687        Alignment >= TypeSize / 8)) {
688     size_t AccessSizeIndex = TypeSizeToSizeIndex(TypeSize);
689     if (ClInstrumentWithCalls) {
690       IRB.CreateCall(HwasanMemoryAccessCallback[IsWrite][AccessSizeIndex],
691                      IRB.CreatePointerCast(Addr, IntptrTy));
692     } else {
693       instrumentMemAccessInline(Addr, IsWrite, AccessSizeIndex, I);
694     }
695   } else {
696     IRB.CreateCall(HwasanMemoryAccessCallbackSized[IsWrite],
697                    {IRB.CreatePointerCast(Addr, IntptrTy),
698                     ConstantInt::get(IntptrTy, TypeSize / 8)});
699   }
700   untagPointerOperand(I, Addr);
701 
702   return true;
703 }
704 
705 static uint64_t getAllocaSizeInBytes(const AllocaInst &AI) {
706   uint64_t ArraySize = 1;
707   if (AI.isArrayAllocation()) {
708     const ConstantInt *CI = dyn_cast<ConstantInt>(AI.getArraySize());
709     assert(CI && "non-constant array size");
710     ArraySize = CI->getZExtValue();
711   }
712   Type *Ty = AI.getAllocatedType();
713   uint64_t SizeInBytes = AI.getModule()->getDataLayout().getTypeAllocSize(Ty);
714   return SizeInBytes * ArraySize;
715 }
716 
717 bool HWAddressSanitizer::tagAlloca(IRBuilder<> &IRB, AllocaInst *AI,
718                                    Value *Tag, size_t Size) {
719   size_t AlignedSize = alignTo(Size, Mapping.getAllocaAlignment());
720 
721   Value *JustTag = IRB.CreateTrunc(Tag, IRB.getInt8Ty());
722   if (ClInstrumentWithCalls) {
723     IRB.CreateCall(HwasanTagMemoryFunc,
724                    {IRB.CreatePointerCast(AI, Int8PtrTy), JustTag,
725                     ConstantInt::get(IntptrTy, AlignedSize)});
726   } else {
727     size_t ShadowSize = Size >> Mapping.Scale;
728     Value *ShadowPtr = memToShadow(IRB.CreatePointerCast(AI, IntptrTy), IRB);
729     // If this memset is not inlined, it will be intercepted in the hwasan
730     // runtime library. That's OK, because the interceptor skips the checks if
731     // the address is in the shadow region.
732     // FIXME: the interceptor is not as fast as real memset. Consider lowering
733     // llvm.memset right here into either a sequence of stores, or a call to
734     // hwasan_tag_memory.
735     if (ShadowSize)
736       IRB.CreateMemSet(ShadowPtr, JustTag, ShadowSize, /*Align=*/1);
737     if (Size != AlignedSize) {
738       IRB.CreateStore(
739           ConstantInt::get(Int8Ty, Size % Mapping.getAllocaAlignment()),
740           IRB.CreateConstGEP1_32(Int8Ty, ShadowPtr, ShadowSize));
741       IRB.CreateStore(JustTag, IRB.CreateConstGEP1_32(
742                                    Int8Ty, IRB.CreateBitCast(AI, Int8PtrTy),
743                                    AlignedSize - 1));
744     }
745   }
746   return true;
747 }
748 
749 static unsigned RetagMask(unsigned AllocaNo) {
750   // A list of 8-bit numbers that have at most one run of non-zero bits.
751   // x = x ^ (mask << 56) can be encoded as a single armv8 instruction for these
752   // masks.
753   // The list does not include the value 255, which is used for UAR.
754   //
755   // Because we are more likely to use earlier elements of this list than later
756   // ones, it is sorted in increasing order of probability of collision with a
757   // mask allocated (temporally) nearby. The program that generated this list
758   // can be found at:
759   // https://github.com/google/sanitizers/blob/master/hwaddress-sanitizer/sort_masks.py
760   static unsigned FastMasks[] = {0,  128, 64,  192, 32,  96,  224, 112, 240,
761                                  48, 16,  120, 248, 56,  24,  8,   124, 252,
762                                  60, 28,  12,  4,   126, 254, 62,  30,  14,
763                                  6,  2,   127, 63,  31,  15,  7,   3,   1};
764   return FastMasks[AllocaNo % (sizeof(FastMasks) / sizeof(FastMasks[0]))];
765 }
766 
767 Value *HWAddressSanitizer::getNextTagWithCall(IRBuilder<> &IRB) {
768   return IRB.CreateZExt(IRB.CreateCall(HwasanGenerateTagFunc), IntptrTy);
769 }
770 
771 Value *HWAddressSanitizer::getStackBaseTag(IRBuilder<> &IRB) {
772   if (ClGenerateTagsWithCalls)
773     return getNextTagWithCall(IRB);
774   if (StackBaseTag)
775     return StackBaseTag;
776   // FIXME: use addressofreturnaddress (but implement it in aarch64 backend
777   // first).
778   Module *M = IRB.GetInsertBlock()->getParent()->getParent();
779   auto GetStackPointerFn = Intrinsic::getDeclaration(
780       M, Intrinsic::frameaddress,
781       IRB.getInt8PtrTy(M->getDataLayout().getAllocaAddrSpace()));
782   Value *StackPointer = IRB.CreateCall(
783       GetStackPointerFn, {Constant::getNullValue(IRB.getInt32Ty())});
784 
785   // Extract some entropy from the stack pointer for the tags.
786   // Take bits 20..28 (ASLR entropy) and xor with bits 0..8 (these differ
787   // between functions).
788   Value *StackPointerLong = IRB.CreatePointerCast(StackPointer, IntptrTy);
789   Value *StackTag =
790       IRB.CreateXor(StackPointerLong, IRB.CreateLShr(StackPointerLong, 20),
791                     "hwasan.stack.base.tag");
792   return StackTag;
793 }
794 
795 Value *HWAddressSanitizer::getAllocaTag(IRBuilder<> &IRB, Value *StackTag,
796                                         AllocaInst *AI, unsigned AllocaNo) {
797   if (ClGenerateTagsWithCalls)
798     return getNextTagWithCall(IRB);
799   return IRB.CreateXor(StackTag,
800                        ConstantInt::get(IntptrTy, RetagMask(AllocaNo)));
801 }
802 
803 Value *HWAddressSanitizer::getUARTag(IRBuilder<> &IRB, Value *StackTag) {
804   if (ClUARRetagToZero)
805     return ConstantInt::get(IntptrTy, 0);
806   if (ClGenerateTagsWithCalls)
807     return getNextTagWithCall(IRB);
808   return IRB.CreateXor(StackTag, ConstantInt::get(IntptrTy, 0xFFU));
809 }
810 
811 // Add a tag to an address.
812 Value *HWAddressSanitizer::tagPointer(IRBuilder<> &IRB, Type *Ty,
813                                       Value *PtrLong, Value *Tag) {
814   Value *TaggedPtrLong;
815   if (CompileKernel) {
816     // Kernel addresses have 0xFF in the most significant byte.
817     Value *ShiftedTag = IRB.CreateOr(
818         IRB.CreateShl(Tag, kPointerTagShift),
819         ConstantInt::get(IntptrTy, (1ULL << kPointerTagShift) - 1));
820     TaggedPtrLong = IRB.CreateAnd(PtrLong, ShiftedTag);
821   } else {
822     // Userspace can simply do OR (tag << 56);
823     Value *ShiftedTag = IRB.CreateShl(Tag, kPointerTagShift);
824     TaggedPtrLong = IRB.CreateOr(PtrLong, ShiftedTag);
825   }
826   return IRB.CreateIntToPtr(TaggedPtrLong, Ty);
827 }
828 
829 // Remove tag from an address.
830 Value *HWAddressSanitizer::untagPointer(IRBuilder<> &IRB, Value *PtrLong) {
831   Value *UntaggedPtrLong;
832   if (CompileKernel) {
833     // Kernel addresses have 0xFF in the most significant byte.
834     UntaggedPtrLong = IRB.CreateOr(PtrLong,
835         ConstantInt::get(PtrLong->getType(), 0xFFULL << kPointerTagShift));
836   } else {
837     // Userspace addresses have 0x00.
838     UntaggedPtrLong = IRB.CreateAnd(PtrLong,
839         ConstantInt::get(PtrLong->getType(), ~(0xFFULL << kPointerTagShift)));
840   }
841   return UntaggedPtrLong;
842 }
843 
844 Value *HWAddressSanitizer::getHwasanThreadSlotPtr(IRBuilder<> &IRB, Type *Ty) {
845   Module *M = IRB.GetInsertBlock()->getParent()->getParent();
846   if (TargetTriple.isAArch64() && TargetTriple.isAndroid()) {
847     // Android provides a fixed TLS slot for sanitizers. See TLS_SLOT_SANITIZER
848     // in Bionic's libc/private/bionic_tls.h.
849     Function *ThreadPointerFunc =
850         Intrinsic::getDeclaration(M, Intrinsic::thread_pointer);
851     Value *SlotPtr = IRB.CreatePointerCast(
852         IRB.CreateConstGEP1_32(IRB.getInt8Ty(),
853                                IRB.CreateCall(ThreadPointerFunc), 0x30),
854         Ty->getPointerTo(0));
855     return SlotPtr;
856   }
857   if (ThreadPtrGlobal)
858     return ThreadPtrGlobal;
859 
860 
861   return nullptr;
862 }
863 
864 void HWAddressSanitizer::emitPrologue(IRBuilder<> &IRB, bool WithFrameRecord) {
865   if (!Mapping.InTls) {
866     LocalDynamicShadow = getDynamicShadowNonTls(IRB);
867     return;
868   }
869 
870   if (!WithFrameRecord && TargetTriple.isAndroid()) {
871     LocalDynamicShadow = getDynamicShadowIfunc(IRB);
872     return;
873   }
874 
875   Value *SlotPtr = getHwasanThreadSlotPtr(IRB, IntptrTy);
876   assert(SlotPtr);
877 
878   Instruction *ThreadLong = IRB.CreateLoad(IntptrTy, SlotPtr);
879 
880   Function *F = IRB.GetInsertBlock()->getParent();
881   if (F->getFnAttribute("hwasan-abi").getValueAsString() == "interceptor") {
882     Value *ThreadLongEqZero =
883         IRB.CreateICmpEQ(ThreadLong, ConstantInt::get(IntptrTy, 0));
884     auto *Br = cast<BranchInst>(SplitBlockAndInsertIfThen(
885         ThreadLongEqZero, cast<Instruction>(ThreadLongEqZero)->getNextNode(),
886         false, MDBuilder(*C).createBranchWeights(1, 100000)));
887 
888     IRB.SetInsertPoint(Br);
889     // FIXME: This should call a new runtime function with a custom calling
890     // convention to avoid needing to spill all arguments here.
891     IRB.CreateCall(HwasanThreadEnterFunc);
892     LoadInst *ReloadThreadLong = IRB.CreateLoad(IntptrTy, SlotPtr);
893 
894     IRB.SetInsertPoint(&*Br->getSuccessor(0)->begin());
895     PHINode *ThreadLongPhi = IRB.CreatePHI(IntptrTy, 2);
896     ThreadLongPhi->addIncoming(ThreadLong, ThreadLong->getParent());
897     ThreadLongPhi->addIncoming(ReloadThreadLong, ReloadThreadLong->getParent());
898     ThreadLong = ThreadLongPhi;
899   }
900 
901   // Extract the address field from ThreadLong. Unnecessary on AArch64 with TBI.
902   Value *ThreadLongMaybeUntagged =
903       TargetTriple.isAArch64() ? ThreadLong : untagPointer(IRB, ThreadLong);
904 
905   if (WithFrameRecord) {
906     StackBaseTag = IRB.CreateAShr(ThreadLong, 3);
907 
908     // Prepare ring buffer data.
909     Value *PC;
910     if (TargetTriple.getArch() == Triple::aarch64)
911       PC = readRegister(IRB, "pc");
912     else
913       PC = IRB.CreatePtrToInt(F, IntptrTy);
914     Module *M = F->getParent();
915     auto GetStackPointerFn = Intrinsic::getDeclaration(
916         M, Intrinsic::frameaddress,
917         IRB.getInt8PtrTy(M->getDataLayout().getAllocaAddrSpace()));
918     Value *SP = IRB.CreatePtrToInt(
919         IRB.CreateCall(GetStackPointerFn,
920                        {Constant::getNullValue(IRB.getInt32Ty())}),
921         IntptrTy);
922     // Mix SP and PC.
923     // Assumptions:
924     // PC is 0x0000PPPPPPPPPPPP  (48 bits are meaningful, others are zero)
925     // SP is 0xsssssssssssSSSS0  (4 lower bits are zero)
926     // We only really need ~20 lower non-zero bits (SSSS), so we mix like this:
927     //       0xSSSSPPPPPPPPPPPP
928     SP = IRB.CreateShl(SP, 44);
929 
930     // Store data to ring buffer.
931     Value *RecordPtr =
932         IRB.CreateIntToPtr(ThreadLongMaybeUntagged, IntptrTy->getPointerTo(0));
933     IRB.CreateStore(IRB.CreateOr(PC, SP), RecordPtr);
934 
935     // Update the ring buffer. Top byte of ThreadLong defines the size of the
936     // buffer in pages, it must be a power of two, and the start of the buffer
937     // must be aligned by twice that much. Therefore wrap around of the ring
938     // buffer is simply Addr &= ~((ThreadLong >> 56) << 12).
939     // The use of AShr instead of LShr is due to
940     //   https://bugs.llvm.org/show_bug.cgi?id=39030
941     // Runtime library makes sure not to use the highest bit.
942     Value *WrapMask = IRB.CreateXor(
943         IRB.CreateShl(IRB.CreateAShr(ThreadLong, 56), 12, "", true, true),
944         ConstantInt::get(IntptrTy, (uint64_t)-1));
945     Value *ThreadLongNew = IRB.CreateAnd(
946         IRB.CreateAdd(ThreadLong, ConstantInt::get(IntptrTy, 8)), WrapMask);
947     IRB.CreateStore(ThreadLongNew, SlotPtr);
948   }
949 
950   // Get shadow base address by aligning RecordPtr up.
951   // Note: this is not correct if the pointer is already aligned.
952   // Runtime library will make sure this never happens.
953   LocalDynamicShadow = IRB.CreateAdd(
954       IRB.CreateOr(
955           ThreadLongMaybeUntagged,
956           ConstantInt::get(IntptrTy, (1ULL << kShadowBaseAlignment) - 1)),
957       ConstantInt::get(IntptrTy, 1), "hwasan.shadow");
958   LocalDynamicShadow = IRB.CreateIntToPtr(LocalDynamicShadow, Int8PtrTy);
959 }
960 
961 Value *HWAddressSanitizer::readRegister(IRBuilder<> &IRB, StringRef Name) {
962   Module *M = IRB.GetInsertBlock()->getParent()->getParent();
963   Function *ReadRegister =
964       Intrinsic::getDeclaration(M, Intrinsic::read_register, IntptrTy);
965   MDNode *MD = MDNode::get(*C, {MDString::get(*C, Name)});
966   Value *Args[] = {MetadataAsValue::get(*C, MD)};
967   return IRB.CreateCall(ReadRegister, Args);
968 }
969 
970 bool HWAddressSanitizer::instrumentLandingPads(
971     SmallVectorImpl<Instruction *> &LandingPadVec) {
972   for (auto *LP : LandingPadVec) {
973     IRBuilder<> IRB(LP->getNextNode());
974     IRB.CreateCall(
975         HWAsanHandleVfork,
976         {readRegister(IRB, (TargetTriple.getArch() == Triple::x86_64) ? "rsp"
977                                                                       : "sp")});
978   }
979   return true;
980 }
981 
982 bool HWAddressSanitizer::instrumentStack(
983     SmallVectorImpl<AllocaInst *> &Allocas,
984     DenseMap<AllocaInst *, std::vector<DbgDeclareInst *>> &AllocaDeclareMap,
985     SmallVectorImpl<Instruction *> &RetVec, Value *StackTag) {
986   // Ideally, we want to calculate tagged stack base pointer, and rewrite all
987   // alloca addresses using that. Unfortunately, offsets are not known yet
988   // (unless we use ASan-style mega-alloca). Instead we keep the base tag in a
989   // temp, shift-OR it into each alloca address and xor with the retag mask.
990   // This generates one extra instruction per alloca use.
991   for (unsigned N = 0; N < Allocas.size(); ++N) {
992     auto *AI = Allocas[N];
993     IRBuilder<> IRB(AI->getNextNode());
994 
995     // Replace uses of the alloca with tagged address.
996     Value *Tag = getAllocaTag(IRB, StackTag, AI, N);
997     Value *AILong = IRB.CreatePointerCast(AI, IntptrTy);
998     Value *Replacement = tagPointer(IRB, AI->getType(), AILong, Tag);
999     std::string Name =
1000         AI->hasName() ? AI->getName().str() : "alloca." + itostr(N);
1001     Replacement->setName(Name + ".hwasan");
1002 
1003     AI->replaceUsesWithIf(Replacement,
1004                           [AILong](Use &U) { return U.getUser() != AILong; });
1005 
1006     for (auto *DDI : AllocaDeclareMap.lookup(AI)) {
1007       DIExpression *OldExpr = DDI->getExpression();
1008       DIExpression *NewExpr = DIExpression::append(
1009           OldExpr, {dwarf::DW_OP_LLVM_tag_offset, RetagMask(N)});
1010       DDI->setArgOperand(2, MetadataAsValue::get(*C, NewExpr));
1011     }
1012 
1013     size_t Size = getAllocaSizeInBytes(*AI);
1014     tagAlloca(IRB, AI, Tag, Size);
1015 
1016     for (auto RI : RetVec) {
1017       IRB.SetInsertPoint(RI);
1018 
1019       // Re-tag alloca memory with the special UAR tag.
1020       Value *Tag = getUARTag(IRB, StackTag);
1021       tagAlloca(IRB, AI, Tag, alignTo(Size, Mapping.getAllocaAlignment()));
1022     }
1023   }
1024 
1025   return true;
1026 }
1027 
1028 bool HWAddressSanitizer::isInterestingAlloca(const AllocaInst &AI) {
1029   return (AI.getAllocatedType()->isSized() &&
1030           // FIXME: instrument dynamic allocas, too
1031           AI.isStaticAlloca() &&
1032           // alloca() may be called with 0 size, ignore it.
1033           getAllocaSizeInBytes(AI) > 0 &&
1034           // We are only interested in allocas not promotable to registers.
1035           // Promotable allocas are common under -O0.
1036           !isAllocaPromotable(&AI) &&
1037           // inalloca allocas are not treated as static, and we don't want
1038           // dynamic alloca instrumentation for them as well.
1039           !AI.isUsedWithInAlloca() &&
1040           // swifterror allocas are register promoted by ISel
1041           !AI.isSwiftError());
1042 }
1043 
1044 bool HWAddressSanitizer::sanitizeFunction(Function &F) {
1045   if (&F == HwasanCtorFunction)
1046     return false;
1047 
1048   if (!F.hasFnAttribute(Attribute::SanitizeHWAddress))
1049     return false;
1050 
1051   LLVM_DEBUG(dbgs() << "Function: " << F.getName() << "\n");
1052 
1053   SmallVector<Instruction*, 16> ToInstrument;
1054   SmallVector<AllocaInst*, 8> AllocasToInstrument;
1055   SmallVector<Instruction*, 8> RetVec;
1056   SmallVector<Instruction*, 8> LandingPadVec;
1057   DenseMap<AllocaInst *, std::vector<DbgDeclareInst *>> AllocaDeclareMap;
1058   for (auto &BB : F) {
1059     for (auto &Inst : BB) {
1060       if (ClInstrumentStack)
1061         if (AllocaInst *AI = dyn_cast<AllocaInst>(&Inst)) {
1062           if (isInterestingAlloca(*AI))
1063             AllocasToInstrument.push_back(AI);
1064           continue;
1065         }
1066 
1067       if (isa<ReturnInst>(Inst) || isa<ResumeInst>(Inst) ||
1068           isa<CleanupReturnInst>(Inst))
1069         RetVec.push_back(&Inst);
1070 
1071       if (auto *DDI = dyn_cast<DbgDeclareInst>(&Inst))
1072         if (auto *Alloca = dyn_cast_or_null<AllocaInst>(DDI->getAddress()))
1073           AllocaDeclareMap[Alloca].push_back(DDI);
1074 
1075       if (ClInstrumentLandingPads && isa<LandingPadInst>(Inst))
1076         LandingPadVec.push_back(&Inst);
1077 
1078       Value *MaybeMask = nullptr;
1079       bool IsWrite;
1080       unsigned Alignment;
1081       uint64_t TypeSize;
1082       Value *Addr = isInterestingMemoryAccess(&Inst, &IsWrite, &TypeSize,
1083                                               &Alignment, &MaybeMask);
1084       if (Addr || isa<MemIntrinsic>(Inst))
1085         ToInstrument.push_back(&Inst);
1086     }
1087   }
1088 
1089   initializeCallbacks(*F.getParent());
1090 
1091   if (!LandingPadVec.empty())
1092     instrumentLandingPads(LandingPadVec);
1093 
1094   if (AllocasToInstrument.empty() && ToInstrument.empty())
1095     return false;
1096 
1097   assert(!LocalDynamicShadow);
1098 
1099   Instruction *InsertPt = &*F.getEntryBlock().begin();
1100   IRBuilder<> EntryIRB(InsertPt);
1101   emitPrologue(EntryIRB,
1102                /*WithFrameRecord*/ ClRecordStackHistory &&
1103                    !AllocasToInstrument.empty());
1104 
1105   bool Changed = false;
1106   if (!AllocasToInstrument.empty()) {
1107     Value *StackTag =
1108         ClGenerateTagsWithCalls ? nullptr : getStackBaseTag(EntryIRB);
1109     Changed |= instrumentStack(AllocasToInstrument, AllocaDeclareMap, RetVec,
1110                                StackTag);
1111   }
1112 
1113   // Pad and align each of the allocas that we instrumented to stop small
1114   // uninteresting allocas from hiding in instrumented alloca's padding and so
1115   // that we have enough space to store real tags for short granules.
1116   DenseMap<AllocaInst *, AllocaInst *> AllocaToPaddedAllocaMap;
1117   for (AllocaInst *AI : AllocasToInstrument) {
1118     uint64_t Size = getAllocaSizeInBytes(*AI);
1119     uint64_t AlignedSize = alignTo(Size, Mapping.getAllocaAlignment());
1120     AI->setAlignment(std::max(AI->getAlignment(), 16u));
1121     if (Size != AlignedSize) {
1122       Type *AllocatedType = AI->getAllocatedType();
1123       if (AI->isArrayAllocation()) {
1124         uint64_t ArraySize =
1125             cast<ConstantInt>(AI->getArraySize())->getZExtValue();
1126         AllocatedType = ArrayType::get(AllocatedType, ArraySize);
1127       }
1128       Type *TypeWithPadding = StructType::get(
1129           AllocatedType, ArrayType::get(Int8Ty, AlignedSize - Size));
1130       auto *NewAI = new AllocaInst(
1131           TypeWithPadding, AI->getType()->getAddressSpace(), nullptr, "", AI);
1132       NewAI->takeName(AI);
1133       NewAI->setAlignment(AI->getAlignment());
1134       NewAI->setUsedWithInAlloca(AI->isUsedWithInAlloca());
1135       NewAI->setSwiftError(AI->isSwiftError());
1136       NewAI->copyMetadata(*AI);
1137       auto *Bitcast = new BitCastInst(NewAI, AI->getType(), "", AI);
1138       AI->replaceAllUsesWith(Bitcast);
1139       AllocaToPaddedAllocaMap[AI] = NewAI;
1140     }
1141   }
1142 
1143   if (!AllocaToPaddedAllocaMap.empty()) {
1144     for (auto &BB : F)
1145       for (auto &Inst : BB)
1146         if (auto *DVI = dyn_cast<DbgVariableIntrinsic>(&Inst))
1147           if (auto *AI =
1148                   dyn_cast_or_null<AllocaInst>(DVI->getVariableLocation()))
1149             if (auto *NewAI = AllocaToPaddedAllocaMap.lookup(AI))
1150               DVI->setArgOperand(
1151                   0, MetadataAsValue::get(*C, LocalAsMetadata::get(NewAI)));
1152     for (auto &P : AllocaToPaddedAllocaMap)
1153       P.first->eraseFromParent();
1154   }
1155 
1156   // If we split the entry block, move any allocas that were originally in the
1157   // entry block back into the entry block so that they aren't treated as
1158   // dynamic allocas.
1159   if (EntryIRB.GetInsertBlock() != &F.getEntryBlock()) {
1160     InsertPt = &*F.getEntryBlock().begin();
1161     for (auto II = EntryIRB.GetInsertBlock()->begin(),
1162               IE = EntryIRB.GetInsertBlock()->end();
1163          II != IE;) {
1164       Instruction *I = &*II++;
1165       if (auto *AI = dyn_cast<AllocaInst>(I))
1166         if (isa<ConstantInt>(AI->getArraySize()))
1167           I->moveBefore(InsertPt);
1168     }
1169   }
1170 
1171   for (auto Inst : ToInstrument)
1172     Changed |= instrumentMemAccess(Inst);
1173 
1174   LocalDynamicShadow = nullptr;
1175   StackBaseTag = nullptr;
1176 
1177   return Changed;
1178 }
1179 
1180 void HWAddressSanitizer::ShadowMapping::init(Triple &TargetTriple) {
1181   Scale = kDefaultShadowScale;
1182   if (ClMappingOffset.getNumOccurrences() > 0) {
1183     InGlobal = false;
1184     InTls = false;
1185     Offset = ClMappingOffset;
1186   } else if (ClEnableKhwasan || ClInstrumentWithCalls) {
1187     InGlobal = false;
1188     InTls = false;
1189     Offset = 0;
1190   } else if (ClWithIfunc) {
1191     InGlobal = true;
1192     InTls = false;
1193     Offset = kDynamicShadowSentinel;
1194   } else if (ClWithTls) {
1195     InGlobal = false;
1196     InTls = true;
1197     Offset = kDynamicShadowSentinel;
1198   } else {
1199     InGlobal = false;
1200     InTls = false;
1201     Offset = kDynamicShadowSentinel;
1202   }
1203 }
1204