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 basic correctness
11 /// checker based on tagged addressing.
12 //===----------------------------------------------------------------------===//
13 
14 #include "llvm/Transforms/Instrumentation/HWAddressSanitizer.h"
15 #include "llvm/ADT/MapVector.h"
16 #include "llvm/ADT/STLExtras.h"
17 #include "llvm/ADT/SmallVector.h"
18 #include "llvm/ADT/StringExtras.h"
19 #include "llvm/ADT/StringRef.h"
20 #include "llvm/ADT/Triple.h"
21 #include "llvm/Analysis/PostDominators.h"
22 #include "llvm/Analysis/StackSafetyAnalysis.h"
23 #include "llvm/Analysis/ValueTracking.h"
24 #include "llvm/BinaryFormat/Dwarf.h"
25 #include "llvm/BinaryFormat/ELF.h"
26 #include "llvm/IR/Attributes.h"
27 #include "llvm/IR/BasicBlock.h"
28 #include "llvm/IR/Constant.h"
29 #include "llvm/IR/Constants.h"
30 #include "llvm/IR/DataLayout.h"
31 #include "llvm/IR/DebugInfoMetadata.h"
32 #include "llvm/IR/DerivedTypes.h"
33 #include "llvm/IR/Dominators.h"
34 #include "llvm/IR/Function.h"
35 #include "llvm/IR/IRBuilder.h"
36 #include "llvm/IR/InlineAsm.h"
37 #include "llvm/IR/InstIterator.h"
38 #include "llvm/IR/Instruction.h"
39 #include "llvm/IR/Instructions.h"
40 #include "llvm/IR/IntrinsicInst.h"
41 #include "llvm/IR/Intrinsics.h"
42 #include "llvm/IR/LLVMContext.h"
43 #include "llvm/IR/MDBuilder.h"
44 #include "llvm/IR/Module.h"
45 #include "llvm/IR/Type.h"
46 #include "llvm/IR/Value.h"
47 #include "llvm/InitializePasses.h"
48 #include "llvm/Pass.h"
49 #include "llvm/PassRegistry.h"
50 #include "llvm/Support/Casting.h"
51 #include "llvm/Support/CommandLine.h"
52 #include "llvm/Support/Debug.h"
53 #include "llvm/Support/raw_ostream.h"
54 #include "llvm/Transforms/Instrumentation/AddressSanitizerCommon.h"
55 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
56 #include "llvm/Transforms/Utils/MemoryTaggingSupport.h"
57 #include "llvm/Transforms/Utils/ModuleUtils.h"
58 #include "llvm/Transforms/Utils/PromoteMemToReg.h"
59 
60 using namespace llvm;
61 
62 #define DEBUG_TYPE "hwasan"
63 
64 const char kHwasanModuleCtorName[] = "hwasan.module_ctor";
65 const char kHwasanNoteName[] = "hwasan.note";
66 const char kHwasanInitName[] = "__hwasan_init";
67 const char kHwasanPersonalityThunkName[] = "__hwasan_personality_thunk";
68 
69 const char kHwasanShadowMemoryDynamicAddress[] =
70     "__hwasan_shadow_memory_dynamic_address";
71 
72 // Accesses sizes are powers of two: 1, 2, 4, 8, 16.
73 static const size_t kNumberOfAccessSizes = 5;
74 
75 static const size_t kDefaultShadowScale = 4;
76 static const uint64_t kDynamicShadowSentinel =
77     std::numeric_limits<uint64_t>::max();
78 
79 static const unsigned kShadowBaseAlignment = 32;
80 
81 static cl::opt<std::string>
82     ClMemoryAccessCallbackPrefix("hwasan-memory-access-callback-prefix",
83                                  cl::desc("Prefix for memory access callbacks"),
84                                  cl::Hidden, cl::init("__hwasan_"));
85 
86 static cl::opt<bool> ClKasanMemIntrinCallbackPrefix(
87     "hwasan-kernel-mem-intrinsic-prefix",
88     cl::desc("Use prefix for memory intrinsics in KASAN mode"), cl::Hidden,
89     cl::init(false));
90 
91 static cl::opt<bool> ClInstrumentWithCalls(
92     "hwasan-instrument-with-calls",
93     cl::desc("instrument reads and writes with callbacks"), cl::Hidden,
94     cl::init(false));
95 
96 static cl::opt<bool> ClInstrumentReads("hwasan-instrument-reads",
97                                        cl::desc("instrument read instructions"),
98                                        cl::Hidden, cl::init(true));
99 
100 static cl::opt<bool>
101     ClInstrumentWrites("hwasan-instrument-writes",
102                        cl::desc("instrument write instructions"), cl::Hidden,
103                        cl::init(true));
104 
105 static cl::opt<bool> ClInstrumentAtomics(
106     "hwasan-instrument-atomics",
107     cl::desc("instrument atomic instructions (rmw, cmpxchg)"), cl::Hidden,
108     cl::init(true));
109 
110 static cl::opt<bool> ClInstrumentByval("hwasan-instrument-byval",
111                                        cl::desc("instrument byval arguments"),
112                                        cl::Hidden, cl::init(true));
113 
114 static cl::opt<bool>
115     ClRecover("hwasan-recover",
116               cl::desc("Enable recovery mode (continue-after-error)."),
117               cl::Hidden, cl::init(false));
118 
119 static cl::opt<bool> ClInstrumentStack("hwasan-instrument-stack",
120                                        cl::desc("instrument stack (allocas)"),
121                                        cl::Hidden, cl::init(true));
122 
123 static cl::opt<bool>
124     ClUseStackSafety("hwasan-use-stack-safety", cl::Hidden, cl::init(true),
125                      cl::Hidden, cl::desc("Use Stack Safety analysis results"),
126                      cl::Optional);
127 
128 static cl::opt<size_t> ClMaxLifetimes(
129     "hwasan-max-lifetimes-for-alloca", cl::Hidden, cl::init(3),
130     cl::ReallyHidden,
131     cl::desc("How many lifetime ends to handle for a single alloca."),
132     cl::Optional);
133 
134 static cl::opt<bool>
135     ClUseAfterScope("hwasan-use-after-scope",
136                     cl::desc("detect use after scope within function"),
137                     cl::Hidden, cl::init(false));
138 
139 static cl::opt<bool> ClUARRetagToZero(
140     "hwasan-uar-retag-to-zero",
141     cl::desc("Clear alloca tags before returning from the function to allow "
142              "non-instrumented and instrumented function calls mix. When set "
143              "to false, allocas are retagged before returning from the "
144              "function to detect use after return."),
145     cl::Hidden, cl::init(true));
146 
147 static cl::opt<bool> ClGenerateTagsWithCalls(
148     "hwasan-generate-tags-with-calls",
149     cl::desc("generate new tags with runtime library calls"), cl::Hidden,
150     cl::init(false));
151 
152 static cl::opt<bool> ClGlobals("hwasan-globals", cl::desc("Instrument globals"),
153                                cl::Hidden, cl::init(false), cl::ZeroOrMore);
154 
155 static cl::opt<int> ClMatchAllTag(
156     "hwasan-match-all-tag",
157     cl::desc("don't report bad accesses via pointers with this tag"),
158     cl::Hidden, cl::init(-1));
159 
160 static cl::opt<bool>
161     ClEnableKhwasan("hwasan-kernel",
162                     cl::desc("Enable KernelHWAddressSanitizer instrumentation"),
163                     cl::Hidden, cl::init(false));
164 
165 // These flags allow to change the shadow mapping and control how shadow memory
166 // is accessed. The shadow mapping looks like:
167 //    Shadow = (Mem >> scale) + offset
168 
169 static cl::opt<uint64_t>
170     ClMappingOffset("hwasan-mapping-offset",
171                     cl::desc("HWASan shadow mapping offset [EXPERIMENTAL]"),
172                     cl::Hidden, cl::init(0));
173 
174 static cl::opt<bool>
175     ClWithIfunc("hwasan-with-ifunc",
176                 cl::desc("Access dynamic shadow through an ifunc global on "
177                          "platforms that support this"),
178                 cl::Hidden, cl::init(false));
179 
180 static cl::opt<bool> ClWithTls(
181     "hwasan-with-tls",
182     cl::desc("Access dynamic shadow through an thread-local pointer on "
183              "platforms that support this"),
184     cl::Hidden, cl::init(true));
185 
186 static cl::opt<bool>
187     ClRecordStackHistory("hwasan-record-stack-history",
188                          cl::desc("Record stack frames with tagged allocations "
189                                   "in a thread-local ring buffer"),
190                          cl::Hidden, cl::init(true));
191 static cl::opt<bool>
192     ClInstrumentMemIntrinsics("hwasan-instrument-mem-intrinsics",
193                               cl::desc("instrument memory intrinsics"),
194                               cl::Hidden, cl::init(true));
195 
196 static cl::opt<bool>
197     ClInstrumentLandingPads("hwasan-instrument-landing-pads",
198                             cl::desc("instrument landing pads"), cl::Hidden,
199                             cl::init(false), cl::ZeroOrMore);
200 
201 static cl::opt<bool> ClUseShortGranules(
202     "hwasan-use-short-granules",
203     cl::desc("use short granules in allocas and outlined checks"), cl::Hidden,
204     cl::init(false), cl::ZeroOrMore);
205 
206 static cl::opt<bool> ClInstrumentPersonalityFunctions(
207     "hwasan-instrument-personality-functions",
208     cl::desc("instrument personality functions"), cl::Hidden, cl::init(false),
209     cl::ZeroOrMore);
210 
211 static cl::opt<bool> ClInlineAllChecks("hwasan-inline-all-checks",
212                                        cl::desc("inline all checks"),
213                                        cl::Hidden, cl::init(false));
214 
215 // Enabled from clang by "-fsanitize-hwaddress-experimental-aliasing".
216 static cl::opt<bool> ClUsePageAliases("hwasan-experimental-use-page-aliases",
217                                       cl::desc("Use page aliasing in HWASan"),
218                                       cl::Hidden, cl::init(false));
219 
220 namespace {
221 
222 bool shouldUsePageAliases(const Triple &TargetTriple) {
223   return ClUsePageAliases && TargetTriple.getArch() == Triple::x86_64;
224 }
225 
226 bool shouldInstrumentStack(const Triple &TargetTriple) {
227   return !shouldUsePageAliases(TargetTriple) && ClInstrumentStack;
228 }
229 
230 bool shouldInstrumentWithCalls(const Triple &TargetTriple) {
231   return ClInstrumentWithCalls || TargetTriple.getArch() == Triple::x86_64;
232 }
233 
234 bool mightUseStackSafetyAnalysis(bool DisableOptimization) {
235   return ClUseStackSafety.getNumOccurrences() ? ClUseStackSafety
236                                               : !DisableOptimization;
237 }
238 
239 bool shouldUseStackSafetyAnalysis(const Triple &TargetTriple,
240                                   bool DisableOptimization) {
241   return shouldInstrumentStack(TargetTriple) &&
242          mightUseStackSafetyAnalysis(DisableOptimization);
243 }
244 
245 bool shouldDetectUseAfterScope(const Triple &TargetTriple) {
246   return ClUseAfterScope && shouldInstrumentStack(TargetTriple);
247 }
248 
249 /// An instrumentation pass implementing detection of addressability bugs
250 /// using tagged pointers.
251 class HWAddressSanitizer {
252 public:
253   HWAddressSanitizer(Module &M, bool CompileKernel, bool Recover,
254                      const StackSafetyGlobalInfo *SSI)
255       : M(M), SSI(SSI) {
256     this->Recover = ClRecover.getNumOccurrences() > 0 ? ClRecover : Recover;
257     this->CompileKernel = ClEnableKhwasan.getNumOccurrences() > 0
258                               ? ClEnableKhwasan
259                               : CompileKernel;
260 
261     initializeModule();
262   }
263 
264   void setSSI(const StackSafetyGlobalInfo *S) { SSI = S; }
265 
266   bool sanitizeFunction(Function &F,
267                         llvm::function_ref<const DominatorTree &()> GetDT,
268                         llvm::function_ref<const PostDominatorTree &()> GetPDT);
269   void initializeModule();
270   void createHwasanCtorComdat();
271 
272   void initializeCallbacks(Module &M);
273 
274   Value *getOpaqueNoopCast(IRBuilder<> &IRB, Value *Val);
275 
276   Value *getDynamicShadowIfunc(IRBuilder<> &IRB);
277   Value *getShadowNonTls(IRBuilder<> &IRB);
278 
279   void untagPointerOperand(Instruction *I, Value *Addr);
280   Value *memToShadow(Value *Shadow, IRBuilder<> &IRB);
281 
282   int64_t getAccessInfo(bool IsWrite, unsigned AccessSizeIndex);
283   void instrumentMemAccessOutline(Value *Ptr, bool IsWrite,
284                                   unsigned AccessSizeIndex,
285                                   Instruction *InsertBefore);
286   void instrumentMemAccessInline(Value *Ptr, bool IsWrite,
287                                  unsigned AccessSizeIndex,
288                                  Instruction *InsertBefore);
289   bool ignoreMemIntrinsic(MemIntrinsic *MI);
290   void instrumentMemIntrinsic(MemIntrinsic *MI);
291   bool instrumentMemAccess(InterestingMemoryOperand &O);
292   bool ignoreAccess(Instruction *Inst, Value *Ptr);
293   void getInterestingMemoryOperands(
294       Instruction *I, SmallVectorImpl<InterestingMemoryOperand> &Interesting);
295 
296   bool isInterestingAlloca(const AllocaInst &AI);
297   void tagAlloca(IRBuilder<> &IRB, AllocaInst *AI, Value *Tag, size_t Size);
298   Value *tagPointer(IRBuilder<> &IRB, Type *Ty, Value *PtrLong, Value *Tag);
299   Value *untagPointer(IRBuilder<> &IRB, Value *PtrLong);
300   bool instrumentStack(memtag::StackInfo &Info, Value *StackTag,
301                        llvm::function_ref<const DominatorTree &()> GetDT,
302                        llvm::function_ref<const PostDominatorTree &()> GetPDT);
303   Value *readRegister(IRBuilder<> &IRB, StringRef Name);
304   bool instrumentLandingPads(SmallVectorImpl<Instruction *> &RetVec);
305   Value *getNextTagWithCall(IRBuilder<> &IRB);
306   Value *getStackBaseTag(IRBuilder<> &IRB);
307   Value *getAllocaTag(IRBuilder<> &IRB, Value *StackTag, AllocaInst *AI,
308                       unsigned AllocaNo);
309   Value *getUARTag(IRBuilder<> &IRB, Value *StackTag);
310 
311   Value *getHwasanThreadSlotPtr(IRBuilder<> &IRB, Type *Ty);
312   Value *applyTagMask(IRBuilder<> &IRB, Value *OldTag);
313   unsigned retagMask(unsigned AllocaNo);
314 
315   void emitPrologue(IRBuilder<> &IRB, bool WithFrameRecord);
316 
317   void instrumentGlobal(GlobalVariable *GV, uint8_t Tag);
318   void instrumentGlobals();
319 
320   void instrumentPersonalityFunctions();
321 
322 private:
323   LLVMContext *C;
324   Module &M;
325   const StackSafetyGlobalInfo *SSI;
326   Triple TargetTriple;
327   FunctionCallee HWAsanMemmove, HWAsanMemcpy, HWAsanMemset;
328   FunctionCallee HWAsanHandleVfork;
329 
330   /// This struct defines the shadow mapping using the rule:
331   ///   shadow = (mem >> Scale) + Offset.
332   /// If InGlobal is true, then
333   ///   extern char __hwasan_shadow[];
334   ///   shadow = (mem >> Scale) + &__hwasan_shadow
335   /// If InTls is true, then
336   ///   extern char *__hwasan_tls;
337   ///   shadow = (mem>>Scale) + align_up(__hwasan_shadow, kShadowBaseAlignment)
338   ///
339   /// If WithFrameRecord is true, then __hwasan_tls will be used to access the
340   /// ring buffer for storing stack allocations on targets that support it.
341   struct ShadowMapping {
342     int Scale;
343     uint64_t Offset;
344     bool InGlobal;
345     bool InTls;
346     bool WithFrameRecord;
347 
348     void init(Triple &TargetTriple, bool InstrumentWithCalls);
349     uint64_t getObjectAlignment() const { return 1ULL << Scale; }
350   };
351 
352   ShadowMapping Mapping;
353 
354   Type *VoidTy = Type::getVoidTy(M.getContext());
355   Type *IntptrTy;
356   Type *Int8PtrTy;
357   Type *Int8Ty;
358   Type *Int32Ty;
359   Type *Int64Ty = Type::getInt64Ty(M.getContext());
360 
361   bool CompileKernel;
362   bool Recover;
363   bool OutlinedChecks;
364   bool UseShortGranules;
365   bool InstrumentLandingPads;
366   bool InstrumentWithCalls;
367   bool InstrumentStack;
368   bool DetectUseAfterScope;
369   bool UsePageAliases;
370 
371   bool HasMatchAllTag = false;
372   uint8_t MatchAllTag = 0;
373 
374   unsigned PointerTagShift;
375   uint64_t TagMaskByte;
376 
377   Function *HwasanCtorFunction;
378 
379   FunctionCallee HwasanMemoryAccessCallback[2][kNumberOfAccessSizes];
380   FunctionCallee HwasanMemoryAccessCallbackSized[2];
381 
382   FunctionCallee HwasanTagMemoryFunc;
383   FunctionCallee HwasanGenerateTagFunc;
384 
385   Constant *ShadowGlobal;
386 
387   Value *ShadowBase = nullptr;
388   Value *StackBaseTag = nullptr;
389   GlobalValue *ThreadPtrGlobal = nullptr;
390 };
391 
392 class HWAddressSanitizerLegacyPass : public FunctionPass {
393 public:
394   // Pass identification, replacement for typeid.
395   static char ID;
396 
397   explicit HWAddressSanitizerLegacyPass(bool CompileKernel = false,
398                                         bool Recover = false,
399                                         bool DisableOptimization = false)
400       : FunctionPass(ID), CompileKernel(CompileKernel), Recover(Recover),
401         DisableOptimization(DisableOptimization) {
402     initializeHWAddressSanitizerLegacyPassPass(
403         *PassRegistry::getPassRegistry());
404   }
405 
406   StringRef getPassName() const override { return "HWAddressSanitizer"; }
407 
408   bool doInitialization(Module &M) override {
409     HWASan = std::make_unique<HWAddressSanitizer>(M, CompileKernel, Recover,
410                                                   /*SSI=*/nullptr);
411     return true;
412   }
413 
414   bool runOnFunction(Function &F) override {
415     auto TargetTriple = Triple(F.getParent()->getTargetTriple());
416     if (shouldUseStackSafetyAnalysis(TargetTriple, DisableOptimization)) {
417       // We cannot call getAnalysis in doInitialization, that would cause a
418       // crash as the required analyses are not initialized yet.
419       HWASan->setSSI(
420           &getAnalysis<StackSafetyGlobalInfoWrapperPass>().getResult());
421     }
422     return HWASan->sanitizeFunction(
423         F,
424         [&]() -> const DominatorTree & {
425           return getAnalysis<DominatorTreeWrapperPass>().getDomTree();
426         },
427         [&]() -> const PostDominatorTree & {
428           return getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
429         });
430   }
431 
432   bool doFinalization(Module &M) override {
433     HWASan.reset();
434     return false;
435   }
436 
437   void getAnalysisUsage(AnalysisUsage &AU) const override {
438     // This is an over-estimation of, in case we are building for an
439     // architecture that doesn't allow stack tagging we will still load the
440     // analysis.
441     // This is so we don't need to plumb TargetTriple all the way to here.
442     if (mightUseStackSafetyAnalysis(DisableOptimization))
443       AU.addRequired<StackSafetyGlobalInfoWrapperPass>();
444     AU.addRequired<DominatorTreeWrapperPass>();
445     AU.addRequired<PostDominatorTreeWrapperPass>();
446   }
447 
448 private:
449   std::unique_ptr<HWAddressSanitizer> HWASan;
450   bool CompileKernel;
451   bool Recover;
452   bool DisableOptimization;
453 };
454 
455 } // end anonymous namespace
456 
457 char HWAddressSanitizerLegacyPass::ID = 0;
458 
459 INITIALIZE_PASS_BEGIN(
460     HWAddressSanitizerLegacyPass, "hwasan",
461     "HWAddressSanitizer: detect memory bugs using tagged addressing.", false,
462     false)
463 INITIALIZE_PASS_DEPENDENCY(StackSafetyGlobalInfoWrapperPass)
464 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
465 INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
466 INITIALIZE_PASS_END(
467     HWAddressSanitizerLegacyPass, "hwasan",
468     "HWAddressSanitizer: detect memory bugs using tagged addressing.", false,
469     false)
470 
471 FunctionPass *
472 llvm::createHWAddressSanitizerLegacyPassPass(bool CompileKernel, bool Recover,
473                                              bool DisableOptimization) {
474   assert(!CompileKernel || Recover);
475   return new HWAddressSanitizerLegacyPass(CompileKernel, Recover,
476                                           DisableOptimization);
477 }
478 
479 PreservedAnalyses HWAddressSanitizerPass::run(Module &M,
480                                               ModuleAnalysisManager &MAM) {
481   const StackSafetyGlobalInfo *SSI = nullptr;
482   auto TargetTriple = llvm::Triple(M.getTargetTriple());
483   if (shouldUseStackSafetyAnalysis(TargetTriple, Options.DisableOptimization))
484     SSI = &MAM.getResult<StackSafetyGlobalAnalysis>(M);
485 
486   HWAddressSanitizer HWASan(M, Options.CompileKernel, Options.Recover, SSI);
487   bool Modified = false;
488   auto &FAM = MAM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
489   for (Function &F : M) {
490     Modified |= HWASan.sanitizeFunction(
491         F,
492         [&]() -> const DominatorTree & {
493           return FAM.getResult<DominatorTreeAnalysis>(F);
494         },
495         [&]() -> const PostDominatorTree & {
496           return FAM.getResult<PostDominatorTreeAnalysis>(F);
497         });
498   }
499   if (Modified)
500     return PreservedAnalyses::none();
501   return PreservedAnalyses::all();
502 }
503 void HWAddressSanitizerPass::printPipeline(
504     raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
505   static_cast<PassInfoMixin<HWAddressSanitizerPass> *>(this)->printPipeline(
506       OS, MapClassName2PassName);
507   OS << "<";
508   if (Options.CompileKernel)
509     OS << "kernel;";
510   if (Options.Recover)
511     OS << "recover";
512   OS << ">";
513 }
514 
515 void HWAddressSanitizer::createHwasanCtorComdat() {
516   std::tie(HwasanCtorFunction, std::ignore) =
517       getOrCreateSanitizerCtorAndInitFunctions(
518           M, kHwasanModuleCtorName, kHwasanInitName,
519           /*InitArgTypes=*/{},
520           /*InitArgs=*/{},
521           // This callback is invoked when the functions are created the first
522           // time. Hook them into the global ctors list in that case:
523           [&](Function *Ctor, FunctionCallee) {
524             Comdat *CtorComdat = M.getOrInsertComdat(kHwasanModuleCtorName);
525             Ctor->setComdat(CtorComdat);
526             appendToGlobalCtors(M, Ctor, 0, Ctor);
527           });
528 
529   // Create a note that contains pointers to the list of global
530   // descriptors. Adding a note to the output file will cause the linker to
531   // create a PT_NOTE program header pointing to the note that we can use to
532   // find the descriptor list starting from the program headers. A function
533   // provided by the runtime initializes the shadow memory for the globals by
534   // accessing the descriptor list via the note. The dynamic loader needs to
535   // call this function whenever a library is loaded.
536   //
537   // The reason why we use a note for this instead of a more conventional
538   // approach of having a global constructor pass a descriptor list pointer to
539   // the runtime is because of an order of initialization problem. With
540   // constructors we can encounter the following problematic scenario:
541   //
542   // 1) library A depends on library B and also interposes one of B's symbols
543   // 2) B's constructors are called before A's (as required for correctness)
544   // 3) during construction, B accesses one of its "own" globals (actually
545   //    interposed by A) and triggers a HWASAN failure due to the initialization
546   //    for A not having happened yet
547   //
548   // Even without interposition it is possible to run into similar situations in
549   // cases where two libraries mutually depend on each other.
550   //
551   // We only need one note per binary, so put everything for the note in a
552   // comdat. This needs to be a comdat with an .init_array section to prevent
553   // newer versions of lld from discarding the note.
554   //
555   // Create the note even if we aren't instrumenting globals. This ensures that
556   // binaries linked from object files with both instrumented and
557   // non-instrumented globals will end up with a note, even if a comdat from an
558   // object file with non-instrumented globals is selected. The note is harmless
559   // if the runtime doesn't support it, since it will just be ignored.
560   Comdat *NoteComdat = M.getOrInsertComdat(kHwasanModuleCtorName);
561 
562   Type *Int8Arr0Ty = ArrayType::get(Int8Ty, 0);
563   auto Start =
564       new GlobalVariable(M, Int8Arr0Ty, true, GlobalVariable::ExternalLinkage,
565                          nullptr, "__start_hwasan_globals");
566   Start->setVisibility(GlobalValue::HiddenVisibility);
567   Start->setDSOLocal(true);
568   auto Stop =
569       new GlobalVariable(M, Int8Arr0Ty, true, GlobalVariable::ExternalLinkage,
570                          nullptr, "__stop_hwasan_globals");
571   Stop->setVisibility(GlobalValue::HiddenVisibility);
572   Stop->setDSOLocal(true);
573 
574   // Null-terminated so actually 8 bytes, which are required in order to align
575   // the note properly.
576   auto *Name = ConstantDataArray::get(*C, "LLVM\0\0\0");
577 
578   auto *NoteTy = StructType::get(Int32Ty, Int32Ty, Int32Ty, Name->getType(),
579                                  Int32Ty, Int32Ty);
580   auto *Note =
581       new GlobalVariable(M, NoteTy, /*isConstant=*/true,
582                          GlobalValue::PrivateLinkage, nullptr, kHwasanNoteName);
583   Note->setSection(".note.hwasan.globals");
584   Note->setComdat(NoteComdat);
585   Note->setAlignment(Align(4));
586   Note->setDSOLocal(true);
587 
588   // The pointers in the note need to be relative so that the note ends up being
589   // placed in rodata, which is the standard location for notes.
590   auto CreateRelPtr = [&](Constant *Ptr) {
591     return ConstantExpr::getTrunc(
592         ConstantExpr::getSub(ConstantExpr::getPtrToInt(Ptr, Int64Ty),
593                              ConstantExpr::getPtrToInt(Note, Int64Ty)),
594         Int32Ty);
595   };
596   Note->setInitializer(ConstantStruct::getAnon(
597       {ConstantInt::get(Int32Ty, 8),                           // n_namesz
598        ConstantInt::get(Int32Ty, 8),                           // n_descsz
599        ConstantInt::get(Int32Ty, ELF::NT_LLVM_HWASAN_GLOBALS), // n_type
600        Name, CreateRelPtr(Start), CreateRelPtr(Stop)}));
601   appendToCompilerUsed(M, Note);
602 
603   // Create a zero-length global in hwasan_globals so that the linker will
604   // always create start and stop symbols.
605   auto Dummy = new GlobalVariable(
606       M, Int8Arr0Ty, /*isConstantGlobal*/ true, GlobalVariable::PrivateLinkage,
607       Constant::getNullValue(Int8Arr0Ty), "hwasan.dummy.global");
608   Dummy->setSection("hwasan_globals");
609   Dummy->setComdat(NoteComdat);
610   Dummy->setMetadata(LLVMContext::MD_associated,
611                      MDNode::get(*C, ValueAsMetadata::get(Note)));
612   appendToCompilerUsed(M, Dummy);
613 }
614 
615 /// Module-level initialization.
616 ///
617 /// inserts a call to __hwasan_init to the module's constructor list.
618 void HWAddressSanitizer::initializeModule() {
619   LLVM_DEBUG(dbgs() << "Init " << M.getName() << "\n");
620   auto &DL = M.getDataLayout();
621 
622   TargetTriple = Triple(M.getTargetTriple());
623 
624   // x86_64 currently has two modes:
625   // - Intel LAM (default)
626   // - pointer aliasing (heap only)
627   bool IsX86_64 = TargetTriple.getArch() == Triple::x86_64;
628   UsePageAliases = shouldUsePageAliases(TargetTriple);
629   InstrumentWithCalls = shouldInstrumentWithCalls(TargetTriple);
630   InstrumentStack = shouldInstrumentStack(TargetTriple);
631   DetectUseAfterScope = shouldDetectUseAfterScope(TargetTriple);
632   PointerTagShift = IsX86_64 ? 57 : 56;
633   TagMaskByte = IsX86_64 ? 0x3F : 0xFF;
634 
635   Mapping.init(TargetTriple, InstrumentWithCalls);
636 
637   C = &(M.getContext());
638   IRBuilder<> IRB(*C);
639   IntptrTy = IRB.getIntPtrTy(DL);
640   Int8PtrTy = IRB.getInt8PtrTy();
641   Int8Ty = IRB.getInt8Ty();
642   Int32Ty = IRB.getInt32Ty();
643 
644   HwasanCtorFunction = nullptr;
645 
646   // Older versions of Android do not have the required runtime support for
647   // short granules, global or personality function instrumentation. On other
648   // platforms we currently require using the latest version of the runtime.
649   bool NewRuntime =
650       !TargetTriple.isAndroid() || !TargetTriple.isAndroidVersionLT(30);
651 
652   UseShortGranules =
653       ClUseShortGranules.getNumOccurrences() ? ClUseShortGranules : NewRuntime;
654   OutlinedChecks =
655       TargetTriple.isAArch64() && TargetTriple.isOSBinFormatELF() &&
656       (ClInlineAllChecks.getNumOccurrences() ? !ClInlineAllChecks : !Recover);
657 
658   if (ClMatchAllTag.getNumOccurrences()) {
659     if (ClMatchAllTag != -1) {
660       HasMatchAllTag = true;
661       MatchAllTag = ClMatchAllTag & 0xFF;
662     }
663   } else if (CompileKernel) {
664     HasMatchAllTag = true;
665     MatchAllTag = 0xFF;
666   }
667 
668   // If we don't have personality function support, fall back to landing pads.
669   InstrumentLandingPads = ClInstrumentLandingPads.getNumOccurrences()
670                               ? ClInstrumentLandingPads
671                               : !NewRuntime;
672 
673   if (!CompileKernel) {
674     createHwasanCtorComdat();
675     bool InstrumentGlobals =
676         ClGlobals.getNumOccurrences() ? ClGlobals : NewRuntime;
677 
678     if (InstrumentGlobals && !UsePageAliases)
679       instrumentGlobals();
680 
681     bool InstrumentPersonalityFunctions =
682         ClInstrumentPersonalityFunctions.getNumOccurrences()
683             ? ClInstrumentPersonalityFunctions
684             : NewRuntime;
685     if (InstrumentPersonalityFunctions)
686       instrumentPersonalityFunctions();
687   }
688 
689   if (!TargetTriple.isAndroid()) {
690     Constant *C = M.getOrInsertGlobal("__hwasan_tls", IntptrTy, [&] {
691       auto *GV = new GlobalVariable(M, IntptrTy, /*isConstant=*/false,
692                                     GlobalValue::ExternalLinkage, nullptr,
693                                     "__hwasan_tls", nullptr,
694                                     GlobalVariable::InitialExecTLSModel);
695       appendToCompilerUsed(M, GV);
696       return GV;
697     });
698     ThreadPtrGlobal = cast<GlobalVariable>(C);
699   }
700 }
701 
702 void HWAddressSanitizer::initializeCallbacks(Module &M) {
703   IRBuilder<> IRB(*C);
704   for (size_t AccessIsWrite = 0; AccessIsWrite <= 1; AccessIsWrite++) {
705     const std::string TypeStr = AccessIsWrite ? "store" : "load";
706     const std::string EndingStr = Recover ? "_noabort" : "";
707 
708     HwasanMemoryAccessCallbackSized[AccessIsWrite] = M.getOrInsertFunction(
709         ClMemoryAccessCallbackPrefix + TypeStr + "N" + EndingStr,
710         FunctionType::get(IRB.getVoidTy(), {IntptrTy, IntptrTy}, false));
711 
712     for (size_t AccessSizeIndex = 0; AccessSizeIndex < kNumberOfAccessSizes;
713          AccessSizeIndex++) {
714       HwasanMemoryAccessCallback[AccessIsWrite][AccessSizeIndex] =
715           M.getOrInsertFunction(
716               ClMemoryAccessCallbackPrefix + TypeStr +
717                   itostr(1ULL << AccessSizeIndex) + EndingStr,
718               FunctionType::get(IRB.getVoidTy(), {IntptrTy}, false));
719     }
720   }
721 
722   HwasanTagMemoryFunc = M.getOrInsertFunction(
723       "__hwasan_tag_memory", IRB.getVoidTy(), Int8PtrTy, Int8Ty, IntptrTy);
724   HwasanGenerateTagFunc =
725       M.getOrInsertFunction("__hwasan_generate_tag", Int8Ty);
726 
727   ShadowGlobal = M.getOrInsertGlobal("__hwasan_shadow",
728                                      ArrayType::get(IRB.getInt8Ty(), 0));
729 
730   const std::string MemIntrinCallbackPrefix =
731       (CompileKernel && !ClKasanMemIntrinCallbackPrefix)
732           ? std::string("")
733           : ClMemoryAccessCallbackPrefix;
734   HWAsanMemmove = M.getOrInsertFunction(MemIntrinCallbackPrefix + "memmove",
735                                         IRB.getInt8PtrTy(), IRB.getInt8PtrTy(),
736                                         IRB.getInt8PtrTy(), IntptrTy);
737   HWAsanMemcpy = M.getOrInsertFunction(MemIntrinCallbackPrefix + "memcpy",
738                                        IRB.getInt8PtrTy(), IRB.getInt8PtrTy(),
739                                        IRB.getInt8PtrTy(), IntptrTy);
740   HWAsanMemset = M.getOrInsertFunction(MemIntrinCallbackPrefix + "memset",
741                                        IRB.getInt8PtrTy(), IRB.getInt8PtrTy(),
742                                        IRB.getInt32Ty(), IntptrTy);
743 
744   HWAsanHandleVfork =
745       M.getOrInsertFunction("__hwasan_handle_vfork", IRB.getVoidTy(), IntptrTy);
746 }
747 
748 Value *HWAddressSanitizer::getOpaqueNoopCast(IRBuilder<> &IRB, Value *Val) {
749   // An empty inline asm with input reg == output reg.
750   // An opaque no-op cast, basically.
751   // This prevents code bloat as a result of rematerializing trivial definitions
752   // such as constants or global addresses at every load and store.
753   InlineAsm *Asm =
754       InlineAsm::get(FunctionType::get(Int8PtrTy, {Val->getType()}, false),
755                      StringRef(""), StringRef("=r,0"),
756                      /*hasSideEffects=*/false);
757   return IRB.CreateCall(Asm, {Val}, ".hwasan.shadow");
758 }
759 
760 Value *HWAddressSanitizer::getDynamicShadowIfunc(IRBuilder<> &IRB) {
761   return getOpaqueNoopCast(IRB, ShadowGlobal);
762 }
763 
764 Value *HWAddressSanitizer::getShadowNonTls(IRBuilder<> &IRB) {
765   if (Mapping.Offset != kDynamicShadowSentinel)
766     return getOpaqueNoopCast(
767         IRB, ConstantExpr::getIntToPtr(
768                  ConstantInt::get(IntptrTy, Mapping.Offset), Int8PtrTy));
769 
770   if (Mapping.InGlobal) {
771     return getDynamicShadowIfunc(IRB);
772   } else {
773     Value *GlobalDynamicAddress =
774         IRB.GetInsertBlock()->getParent()->getParent()->getOrInsertGlobal(
775             kHwasanShadowMemoryDynamicAddress, Int8PtrTy);
776     return IRB.CreateLoad(Int8PtrTy, GlobalDynamicAddress);
777   }
778 }
779 
780 bool HWAddressSanitizer::ignoreAccess(Instruction *Inst, Value *Ptr) {
781   // Do not instrument acesses from different address spaces; we cannot deal
782   // with them.
783   Type *PtrTy = cast<PointerType>(Ptr->getType()->getScalarType());
784   if (PtrTy->getPointerAddressSpace() != 0)
785     return true;
786 
787   // Ignore swifterror addresses.
788   // swifterror memory addresses are mem2reg promoted by instruction
789   // selection. As such they cannot have regular uses like an instrumentation
790   // function and it makes no sense to track them as memory.
791   if (Ptr->isSwiftError())
792     return true;
793 
794   if (findAllocaForValue(Ptr)) {
795     if (!InstrumentStack)
796       return true;
797     if (SSI && SSI->stackAccessIsSafe(*Inst))
798       return true;
799   }
800   return false;
801 }
802 
803 void HWAddressSanitizer::getInterestingMemoryOperands(
804     Instruction *I, SmallVectorImpl<InterestingMemoryOperand> &Interesting) {
805   // Skip memory accesses inserted by another instrumentation.
806   if (I->hasMetadata("nosanitize"))
807     return;
808 
809   // Do not instrument the load fetching the dynamic shadow address.
810   if (ShadowBase == I)
811     return;
812 
813   if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
814     if (!ClInstrumentReads || ignoreAccess(I, LI->getPointerOperand()))
815       return;
816     Interesting.emplace_back(I, LI->getPointerOperandIndex(), false,
817                              LI->getType(), LI->getAlign());
818   } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
819     if (!ClInstrumentWrites || ignoreAccess(I, SI->getPointerOperand()))
820       return;
821     Interesting.emplace_back(I, SI->getPointerOperandIndex(), true,
822                              SI->getValueOperand()->getType(), SI->getAlign());
823   } else if (AtomicRMWInst *RMW = dyn_cast<AtomicRMWInst>(I)) {
824     if (!ClInstrumentAtomics || ignoreAccess(I, RMW->getPointerOperand()))
825       return;
826     Interesting.emplace_back(I, RMW->getPointerOperandIndex(), true,
827                              RMW->getValOperand()->getType(), None);
828   } else if (AtomicCmpXchgInst *XCHG = dyn_cast<AtomicCmpXchgInst>(I)) {
829     if (!ClInstrumentAtomics || ignoreAccess(I, XCHG->getPointerOperand()))
830       return;
831     Interesting.emplace_back(I, XCHG->getPointerOperandIndex(), true,
832                              XCHG->getCompareOperand()->getType(), None);
833   } else if (auto CI = dyn_cast<CallInst>(I)) {
834     for (unsigned ArgNo = 0; ArgNo < CI->arg_size(); ArgNo++) {
835       if (!ClInstrumentByval || !CI->isByValArgument(ArgNo) ||
836           ignoreAccess(I, CI->getArgOperand(ArgNo)))
837         continue;
838       Type *Ty = CI->getParamByValType(ArgNo);
839       Interesting.emplace_back(I, ArgNo, false, Ty, Align(1));
840     }
841   }
842 }
843 
844 static unsigned getPointerOperandIndex(Instruction *I) {
845   if (LoadInst *LI = dyn_cast<LoadInst>(I))
846     return LI->getPointerOperandIndex();
847   if (StoreInst *SI = dyn_cast<StoreInst>(I))
848     return SI->getPointerOperandIndex();
849   if (AtomicRMWInst *RMW = dyn_cast<AtomicRMWInst>(I))
850     return RMW->getPointerOperandIndex();
851   if (AtomicCmpXchgInst *XCHG = dyn_cast<AtomicCmpXchgInst>(I))
852     return XCHG->getPointerOperandIndex();
853   report_fatal_error("Unexpected instruction");
854   return -1;
855 }
856 
857 static size_t TypeSizeToSizeIndex(uint32_t TypeSize) {
858   size_t Res = countTrailingZeros(TypeSize / 8);
859   assert(Res < kNumberOfAccessSizes);
860   return Res;
861 }
862 
863 void HWAddressSanitizer::untagPointerOperand(Instruction *I, Value *Addr) {
864   if (TargetTriple.isAArch64() || TargetTriple.getArch() == Triple::x86_64)
865     return;
866 
867   IRBuilder<> IRB(I);
868   Value *AddrLong = IRB.CreatePointerCast(Addr, IntptrTy);
869   Value *UntaggedPtr =
870       IRB.CreateIntToPtr(untagPointer(IRB, AddrLong), Addr->getType());
871   I->setOperand(getPointerOperandIndex(I), UntaggedPtr);
872 }
873 
874 Value *HWAddressSanitizer::memToShadow(Value *Mem, IRBuilder<> &IRB) {
875   // Mem >> Scale
876   Value *Shadow = IRB.CreateLShr(Mem, Mapping.Scale);
877   if (Mapping.Offset == 0)
878     return IRB.CreateIntToPtr(Shadow, Int8PtrTy);
879   // (Mem >> Scale) + Offset
880   return IRB.CreateGEP(Int8Ty, ShadowBase, Shadow);
881 }
882 
883 int64_t HWAddressSanitizer::getAccessInfo(bool IsWrite,
884                                           unsigned AccessSizeIndex) {
885   return (CompileKernel << HWASanAccessInfo::CompileKernelShift) +
886          (HasMatchAllTag << HWASanAccessInfo::HasMatchAllShift) +
887          (MatchAllTag << HWASanAccessInfo::MatchAllShift) +
888          (Recover << HWASanAccessInfo::RecoverShift) +
889          (IsWrite << HWASanAccessInfo::IsWriteShift) +
890          (AccessSizeIndex << HWASanAccessInfo::AccessSizeShift);
891 }
892 
893 void HWAddressSanitizer::instrumentMemAccessOutline(Value *Ptr, bool IsWrite,
894                                                     unsigned AccessSizeIndex,
895                                                     Instruction *InsertBefore) {
896   assert(!UsePageAliases);
897   const int64_t AccessInfo = getAccessInfo(IsWrite, AccessSizeIndex);
898   IRBuilder<> IRB(InsertBefore);
899   Module *M = IRB.GetInsertBlock()->getParent()->getParent();
900   Ptr = IRB.CreateBitCast(Ptr, Int8PtrTy);
901   IRB.CreateCall(Intrinsic::getDeclaration(
902                      M, UseShortGranules
903                             ? Intrinsic::hwasan_check_memaccess_shortgranules
904                             : Intrinsic::hwasan_check_memaccess),
905                  {ShadowBase, Ptr, ConstantInt::get(Int32Ty, AccessInfo)});
906 }
907 
908 void HWAddressSanitizer::instrumentMemAccessInline(Value *Ptr, bool IsWrite,
909                                                    unsigned AccessSizeIndex,
910                                                    Instruction *InsertBefore) {
911   assert(!UsePageAliases);
912   const int64_t AccessInfo = getAccessInfo(IsWrite, AccessSizeIndex);
913   IRBuilder<> IRB(InsertBefore);
914 
915   Value *PtrLong = IRB.CreatePointerCast(Ptr, IntptrTy);
916   Value *PtrTag = IRB.CreateTrunc(IRB.CreateLShr(PtrLong, PointerTagShift),
917                                   IRB.getInt8Ty());
918   Value *AddrLong = untagPointer(IRB, PtrLong);
919   Value *Shadow = memToShadow(AddrLong, IRB);
920   Value *MemTag = IRB.CreateLoad(Int8Ty, Shadow);
921   Value *TagMismatch = IRB.CreateICmpNE(PtrTag, MemTag);
922 
923   if (HasMatchAllTag) {
924     Value *TagNotIgnored = IRB.CreateICmpNE(
925         PtrTag, ConstantInt::get(PtrTag->getType(), MatchAllTag));
926     TagMismatch = IRB.CreateAnd(TagMismatch, TagNotIgnored);
927   }
928 
929   Instruction *CheckTerm =
930       SplitBlockAndInsertIfThen(TagMismatch, InsertBefore, false,
931                                 MDBuilder(*C).createBranchWeights(1, 100000));
932 
933   IRB.SetInsertPoint(CheckTerm);
934   Value *OutOfShortGranuleTagRange =
935       IRB.CreateICmpUGT(MemTag, ConstantInt::get(Int8Ty, 15));
936   Instruction *CheckFailTerm =
937       SplitBlockAndInsertIfThen(OutOfShortGranuleTagRange, CheckTerm, !Recover,
938                                 MDBuilder(*C).createBranchWeights(1, 100000));
939 
940   IRB.SetInsertPoint(CheckTerm);
941   Value *PtrLowBits = IRB.CreateTrunc(IRB.CreateAnd(PtrLong, 15), Int8Ty);
942   PtrLowBits = IRB.CreateAdd(
943       PtrLowBits, ConstantInt::get(Int8Ty, (1 << AccessSizeIndex) - 1));
944   Value *PtrLowBitsOOB = IRB.CreateICmpUGE(PtrLowBits, MemTag);
945   SplitBlockAndInsertIfThen(PtrLowBitsOOB, CheckTerm, false,
946                             MDBuilder(*C).createBranchWeights(1, 100000),
947                             (DomTreeUpdater *)nullptr, nullptr,
948                             CheckFailTerm->getParent());
949 
950   IRB.SetInsertPoint(CheckTerm);
951   Value *InlineTagAddr = IRB.CreateOr(AddrLong, 15);
952   InlineTagAddr = IRB.CreateIntToPtr(InlineTagAddr, Int8PtrTy);
953   Value *InlineTag = IRB.CreateLoad(Int8Ty, InlineTagAddr);
954   Value *InlineTagMismatch = IRB.CreateICmpNE(PtrTag, InlineTag);
955   SplitBlockAndInsertIfThen(InlineTagMismatch, CheckTerm, false,
956                             MDBuilder(*C).createBranchWeights(1, 100000),
957                             (DomTreeUpdater *)nullptr, nullptr,
958                             CheckFailTerm->getParent());
959 
960   IRB.SetInsertPoint(CheckFailTerm);
961   InlineAsm *Asm;
962   switch (TargetTriple.getArch()) {
963   case Triple::x86_64:
964     // The signal handler will find the data address in rdi.
965     Asm = InlineAsm::get(
966         FunctionType::get(IRB.getVoidTy(), {PtrLong->getType()}, false),
967         "int3\nnopl " +
968             itostr(0x40 + (AccessInfo & HWASanAccessInfo::RuntimeMask)) +
969             "(%rax)",
970         "{rdi}",
971         /*hasSideEffects=*/true);
972     break;
973   case Triple::aarch64:
974   case Triple::aarch64_be:
975     // The signal handler will find the data address in x0.
976     Asm = InlineAsm::get(
977         FunctionType::get(IRB.getVoidTy(), {PtrLong->getType()}, false),
978         "brk #" + itostr(0x900 + (AccessInfo & HWASanAccessInfo::RuntimeMask)),
979         "{x0}",
980         /*hasSideEffects=*/true);
981     break;
982   default:
983     report_fatal_error("unsupported architecture");
984   }
985   IRB.CreateCall(Asm, PtrLong);
986   if (Recover)
987     cast<BranchInst>(CheckFailTerm)->setSuccessor(0, CheckTerm->getParent());
988 }
989 
990 bool HWAddressSanitizer::ignoreMemIntrinsic(MemIntrinsic *MI) {
991   if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI)) {
992     return (!ClInstrumentWrites || ignoreAccess(MTI, MTI->getDest())) &&
993            (!ClInstrumentReads || ignoreAccess(MTI, MTI->getSource()));
994   }
995   if (isa<MemSetInst>(MI))
996     return !ClInstrumentWrites || ignoreAccess(MI, MI->getDest());
997   return false;
998 }
999 
1000 void HWAddressSanitizer::instrumentMemIntrinsic(MemIntrinsic *MI) {
1001   IRBuilder<> IRB(MI);
1002   if (isa<MemTransferInst>(MI)) {
1003     IRB.CreateCall(
1004         isa<MemMoveInst>(MI) ? HWAsanMemmove : HWAsanMemcpy,
1005         {IRB.CreatePointerCast(MI->getOperand(0), IRB.getInt8PtrTy()),
1006          IRB.CreatePointerCast(MI->getOperand(1), IRB.getInt8PtrTy()),
1007          IRB.CreateIntCast(MI->getOperand(2), IntptrTy, false)});
1008   } else if (isa<MemSetInst>(MI)) {
1009     IRB.CreateCall(
1010         HWAsanMemset,
1011         {IRB.CreatePointerCast(MI->getOperand(0), IRB.getInt8PtrTy()),
1012          IRB.CreateIntCast(MI->getOperand(1), IRB.getInt32Ty(), false),
1013          IRB.CreateIntCast(MI->getOperand(2), IntptrTy, false)});
1014   }
1015   MI->eraseFromParent();
1016 }
1017 
1018 bool HWAddressSanitizer::instrumentMemAccess(InterestingMemoryOperand &O) {
1019   Value *Addr = O.getPtr();
1020 
1021   LLVM_DEBUG(dbgs() << "Instrumenting: " << O.getInsn() << "\n");
1022 
1023   if (O.MaybeMask)
1024     return false; // FIXME
1025 
1026   IRBuilder<> IRB(O.getInsn());
1027   if (isPowerOf2_64(O.TypeSize) &&
1028       (O.TypeSize / 8 <= (1ULL << (kNumberOfAccessSizes - 1))) &&
1029       (!O.Alignment || *O.Alignment >= (1ULL << Mapping.Scale) ||
1030        *O.Alignment >= O.TypeSize / 8)) {
1031     size_t AccessSizeIndex = TypeSizeToSizeIndex(O.TypeSize);
1032     if (InstrumentWithCalls) {
1033       IRB.CreateCall(HwasanMemoryAccessCallback[O.IsWrite][AccessSizeIndex],
1034                      IRB.CreatePointerCast(Addr, IntptrTy));
1035     } else if (OutlinedChecks) {
1036       instrumentMemAccessOutline(Addr, O.IsWrite, AccessSizeIndex, O.getInsn());
1037     } else {
1038       instrumentMemAccessInline(Addr, O.IsWrite, AccessSizeIndex, O.getInsn());
1039     }
1040   } else {
1041     IRB.CreateCall(HwasanMemoryAccessCallbackSized[O.IsWrite],
1042                    {IRB.CreatePointerCast(Addr, IntptrTy),
1043                     ConstantInt::get(IntptrTy, O.TypeSize / 8)});
1044   }
1045   untagPointerOperand(O.getInsn(), Addr);
1046 
1047   return true;
1048 }
1049 
1050 void HWAddressSanitizer::tagAlloca(IRBuilder<> &IRB, AllocaInst *AI, Value *Tag,
1051                                    size_t Size) {
1052   size_t AlignedSize = alignTo(Size, Mapping.getObjectAlignment());
1053   if (!UseShortGranules)
1054     Size = AlignedSize;
1055 
1056   Value *JustTag = IRB.CreateTrunc(Tag, IRB.getInt8Ty());
1057   if (InstrumentWithCalls) {
1058     IRB.CreateCall(HwasanTagMemoryFunc,
1059                    {IRB.CreatePointerCast(AI, Int8PtrTy), JustTag,
1060                     ConstantInt::get(IntptrTy, AlignedSize)});
1061   } else {
1062     size_t ShadowSize = Size >> Mapping.Scale;
1063     Value *ShadowPtr = memToShadow(IRB.CreatePointerCast(AI, IntptrTy), IRB);
1064     // If this memset is not inlined, it will be intercepted in the hwasan
1065     // runtime library. That's OK, because the interceptor skips the checks if
1066     // the address is in the shadow region.
1067     // FIXME: the interceptor is not as fast as real memset. Consider lowering
1068     // llvm.memset right here into either a sequence of stores, or a call to
1069     // hwasan_tag_memory.
1070     if (ShadowSize)
1071       IRB.CreateMemSet(ShadowPtr, JustTag, ShadowSize, Align(1));
1072     if (Size != AlignedSize) {
1073       IRB.CreateStore(
1074           ConstantInt::get(Int8Ty, Size % Mapping.getObjectAlignment()),
1075           IRB.CreateConstGEP1_32(Int8Ty, ShadowPtr, ShadowSize));
1076       IRB.CreateStore(JustTag, IRB.CreateConstGEP1_32(
1077                                    Int8Ty, IRB.CreateBitCast(AI, Int8PtrTy),
1078                                    AlignedSize - 1));
1079     }
1080   }
1081 }
1082 
1083 unsigned HWAddressSanitizer::retagMask(unsigned AllocaNo) {
1084   if (TargetTriple.getArch() == Triple::x86_64)
1085     return AllocaNo & TagMaskByte;
1086 
1087   // A list of 8-bit numbers that have at most one run of non-zero bits.
1088   // x = x ^ (mask << 56) can be encoded as a single armv8 instruction for these
1089   // masks.
1090   // The list does not include the value 255, which is used for UAR.
1091   //
1092   // Because we are more likely to use earlier elements of this list than later
1093   // ones, it is sorted in increasing order of probability of collision with a
1094   // mask allocated (temporally) nearby. The program that generated this list
1095   // can be found at:
1096   // https://github.com/google/sanitizers/blob/master/hwaddress-sanitizer/sort_masks.py
1097   static unsigned FastMasks[] = {0,  128, 64,  192, 32,  96,  224, 112, 240,
1098                                  48, 16,  120, 248, 56,  24,  8,   124, 252,
1099                                  60, 28,  12,  4,   126, 254, 62,  30,  14,
1100                                  6,  2,   127, 63,  31,  15,  7,   3,   1};
1101   return FastMasks[AllocaNo % (sizeof(FastMasks) / sizeof(FastMasks[0]))];
1102 }
1103 
1104 Value *HWAddressSanitizer::applyTagMask(IRBuilder<> &IRB, Value *OldTag) {
1105   if (TargetTriple.getArch() == Triple::x86_64) {
1106     Constant *TagMask = ConstantInt::get(IntptrTy, TagMaskByte);
1107     Value *NewTag = IRB.CreateAnd(OldTag, TagMask);
1108     return NewTag;
1109   }
1110   // aarch64 uses 8-bit tags, so no mask is needed.
1111   return OldTag;
1112 }
1113 
1114 Value *HWAddressSanitizer::getNextTagWithCall(IRBuilder<> &IRB) {
1115   return IRB.CreateZExt(IRB.CreateCall(HwasanGenerateTagFunc), IntptrTy);
1116 }
1117 
1118 Value *HWAddressSanitizer::getStackBaseTag(IRBuilder<> &IRB) {
1119   if (ClGenerateTagsWithCalls)
1120     return getNextTagWithCall(IRB);
1121   if (StackBaseTag)
1122     return StackBaseTag;
1123   // FIXME: use addressofreturnaddress (but implement it in aarch64 backend
1124   // first).
1125   Module *M = IRB.GetInsertBlock()->getParent()->getParent();
1126   auto GetStackPointerFn = Intrinsic::getDeclaration(
1127       M, Intrinsic::frameaddress,
1128       IRB.getInt8PtrTy(M->getDataLayout().getAllocaAddrSpace()));
1129   Value *StackPointer = IRB.CreateCall(
1130       GetStackPointerFn, {Constant::getNullValue(IRB.getInt32Ty())});
1131 
1132   // Extract some entropy from the stack pointer for the tags.
1133   // Take bits 20..28 (ASLR entropy) and xor with bits 0..8 (these differ
1134   // between functions).
1135   Value *StackPointerLong = IRB.CreatePointerCast(StackPointer, IntptrTy);
1136   Value *StackTag =
1137       applyTagMask(IRB, IRB.CreateXor(StackPointerLong,
1138                                       IRB.CreateLShr(StackPointerLong, 20)));
1139   StackTag->setName("hwasan.stack.base.tag");
1140   return StackTag;
1141 }
1142 
1143 Value *HWAddressSanitizer::getAllocaTag(IRBuilder<> &IRB, Value *StackTag,
1144                                         AllocaInst *AI, unsigned AllocaNo) {
1145   if (ClGenerateTagsWithCalls)
1146     return getNextTagWithCall(IRB);
1147   return IRB.CreateXor(StackTag,
1148                        ConstantInt::get(IntptrTy, retagMask(AllocaNo)));
1149 }
1150 
1151 Value *HWAddressSanitizer::getUARTag(IRBuilder<> &IRB, Value *StackTag) {
1152   if (ClUARRetagToZero)
1153     return ConstantInt::get(IntptrTy, 0);
1154   if (ClGenerateTagsWithCalls)
1155     return getNextTagWithCall(IRB);
1156   return IRB.CreateXor(StackTag, ConstantInt::get(IntptrTy, TagMaskByte));
1157 }
1158 
1159 // Add a tag to an address.
1160 Value *HWAddressSanitizer::tagPointer(IRBuilder<> &IRB, Type *Ty,
1161                                       Value *PtrLong, Value *Tag) {
1162   assert(!UsePageAliases);
1163   Value *TaggedPtrLong;
1164   if (CompileKernel) {
1165     // Kernel addresses have 0xFF in the most significant byte.
1166     Value *ShiftedTag =
1167         IRB.CreateOr(IRB.CreateShl(Tag, PointerTagShift),
1168                      ConstantInt::get(IntptrTy, (1ULL << PointerTagShift) - 1));
1169     TaggedPtrLong = IRB.CreateAnd(PtrLong, ShiftedTag);
1170   } else {
1171     // Userspace can simply do OR (tag << PointerTagShift);
1172     Value *ShiftedTag = IRB.CreateShl(Tag, PointerTagShift);
1173     TaggedPtrLong = IRB.CreateOr(PtrLong, ShiftedTag);
1174   }
1175   return IRB.CreateIntToPtr(TaggedPtrLong, Ty);
1176 }
1177 
1178 // Remove tag from an address.
1179 Value *HWAddressSanitizer::untagPointer(IRBuilder<> &IRB, Value *PtrLong) {
1180   assert(!UsePageAliases);
1181   Value *UntaggedPtrLong;
1182   if (CompileKernel) {
1183     // Kernel addresses have 0xFF in the most significant byte.
1184     UntaggedPtrLong =
1185         IRB.CreateOr(PtrLong, ConstantInt::get(PtrLong->getType(),
1186                                                0xFFULL << PointerTagShift));
1187   } else {
1188     // Userspace addresses have 0x00.
1189     UntaggedPtrLong =
1190         IRB.CreateAnd(PtrLong, ConstantInt::get(PtrLong->getType(),
1191                                                 ~(0xFFULL << PointerTagShift)));
1192   }
1193   return UntaggedPtrLong;
1194 }
1195 
1196 Value *HWAddressSanitizer::getHwasanThreadSlotPtr(IRBuilder<> &IRB, Type *Ty) {
1197   Module *M = IRB.GetInsertBlock()->getParent()->getParent();
1198   if (TargetTriple.isAArch64() && TargetTriple.isAndroid()) {
1199     // Android provides a fixed TLS slot for sanitizers. See TLS_SLOT_SANITIZER
1200     // in Bionic's libc/private/bionic_tls.h.
1201     Function *ThreadPointerFunc =
1202         Intrinsic::getDeclaration(M, Intrinsic::thread_pointer);
1203     Value *SlotPtr = IRB.CreatePointerCast(
1204         IRB.CreateConstGEP1_32(IRB.getInt8Ty(),
1205                                IRB.CreateCall(ThreadPointerFunc), 0x30),
1206         Ty->getPointerTo(0));
1207     return SlotPtr;
1208   }
1209   if (ThreadPtrGlobal)
1210     return ThreadPtrGlobal;
1211 
1212   return nullptr;
1213 }
1214 
1215 void HWAddressSanitizer::emitPrologue(IRBuilder<> &IRB, bool WithFrameRecord) {
1216   if (!Mapping.InTls)
1217     ShadowBase = getShadowNonTls(IRB);
1218   else if (!WithFrameRecord && TargetTriple.isAndroid())
1219     ShadowBase = getDynamicShadowIfunc(IRB);
1220 
1221   if (!WithFrameRecord && ShadowBase)
1222     return;
1223 
1224   Value *SlotPtr = getHwasanThreadSlotPtr(IRB, IntptrTy);
1225   assert(SlotPtr);
1226 
1227   Value *ThreadLong = IRB.CreateLoad(IntptrTy, SlotPtr);
1228   // Extract the address field from ThreadLong. Unnecessary on AArch64 with TBI.
1229   Value *ThreadLongMaybeUntagged =
1230       TargetTriple.isAArch64() ? ThreadLong : untagPointer(IRB, ThreadLong);
1231 
1232   if (WithFrameRecord) {
1233     Function *F = IRB.GetInsertBlock()->getParent();
1234     StackBaseTag = IRB.CreateAShr(ThreadLong, 3);
1235 
1236     // Prepare ring buffer data.
1237     Value *PC;
1238     if (TargetTriple.getArch() == Triple::aarch64)
1239       PC = readRegister(IRB, "pc");
1240     else
1241       PC = IRB.CreatePtrToInt(F, IntptrTy);
1242     Module *M = F->getParent();
1243     auto GetStackPointerFn = Intrinsic::getDeclaration(
1244         M, Intrinsic::frameaddress,
1245         IRB.getInt8PtrTy(M->getDataLayout().getAllocaAddrSpace()));
1246     Value *SP = IRB.CreatePtrToInt(
1247         IRB.CreateCall(GetStackPointerFn,
1248                        {Constant::getNullValue(IRB.getInt32Ty())}),
1249         IntptrTy);
1250     // Mix SP and PC.
1251     // Assumptions:
1252     // PC is 0x0000PPPPPPPPPPPP  (48 bits are meaningful, others are zero)
1253     // SP is 0xsssssssssssSSSS0  (4 lower bits are zero)
1254     // We only really need ~20 lower non-zero bits (SSSS), so we mix like this:
1255     //       0xSSSSPPPPPPPPPPPP
1256     SP = IRB.CreateShl(SP, 44);
1257 
1258     // Store data to ring buffer.
1259     Value *RecordPtr =
1260         IRB.CreateIntToPtr(ThreadLongMaybeUntagged, IntptrTy->getPointerTo(0));
1261     IRB.CreateStore(IRB.CreateOr(PC, SP), RecordPtr);
1262 
1263     // Update the ring buffer. Top byte of ThreadLong defines the size of the
1264     // buffer in pages, it must be a power of two, and the start of the buffer
1265     // must be aligned by twice that much. Therefore wrap around of the ring
1266     // buffer is simply Addr &= ~((ThreadLong >> 56) << 12).
1267     // The use of AShr instead of LShr is due to
1268     //   https://bugs.llvm.org/show_bug.cgi?id=39030
1269     // Runtime library makes sure not to use the highest bit.
1270     Value *WrapMask = IRB.CreateXor(
1271         IRB.CreateShl(IRB.CreateAShr(ThreadLong, 56), 12, "", true, true),
1272         ConstantInt::get(IntptrTy, (uint64_t)-1));
1273     Value *ThreadLongNew = IRB.CreateAnd(
1274         IRB.CreateAdd(ThreadLong, ConstantInt::get(IntptrTy, 8)), WrapMask);
1275     IRB.CreateStore(ThreadLongNew, SlotPtr);
1276   }
1277 
1278   if (!ShadowBase) {
1279     // Get shadow base address by aligning RecordPtr up.
1280     // Note: this is not correct if the pointer is already aligned.
1281     // Runtime library will make sure this never happens.
1282     ShadowBase = IRB.CreateAdd(
1283         IRB.CreateOr(
1284             ThreadLongMaybeUntagged,
1285             ConstantInt::get(IntptrTy, (1ULL << kShadowBaseAlignment) - 1)),
1286         ConstantInt::get(IntptrTy, 1), "hwasan.shadow");
1287     ShadowBase = IRB.CreateIntToPtr(ShadowBase, Int8PtrTy);
1288   }
1289 }
1290 
1291 Value *HWAddressSanitizer::readRegister(IRBuilder<> &IRB, StringRef Name) {
1292   Module *M = IRB.GetInsertBlock()->getParent()->getParent();
1293   Function *ReadRegister =
1294       Intrinsic::getDeclaration(M, Intrinsic::read_register, IntptrTy);
1295   MDNode *MD = MDNode::get(*C, {MDString::get(*C, Name)});
1296   Value *Args[] = {MetadataAsValue::get(*C, MD)};
1297   return IRB.CreateCall(ReadRegister, Args);
1298 }
1299 
1300 bool HWAddressSanitizer::instrumentLandingPads(
1301     SmallVectorImpl<Instruction *> &LandingPadVec) {
1302   for (auto *LP : LandingPadVec) {
1303     IRBuilder<> IRB(LP->getNextNode());
1304     IRB.CreateCall(
1305         HWAsanHandleVfork,
1306         {readRegister(IRB, (TargetTriple.getArch() == Triple::x86_64) ? "rsp"
1307                                                                       : "sp")});
1308   }
1309   return true;
1310 }
1311 
1312 static bool isLifetimeIntrinsic(Value *V) {
1313   auto *II = dyn_cast<IntrinsicInst>(V);
1314   return II && II->isLifetimeStartOrEnd();
1315 }
1316 
1317 bool HWAddressSanitizer::instrumentStack(
1318     memtag::StackInfo &SInfo, Value *StackTag,
1319     llvm::function_ref<const DominatorTree &()> GetDT,
1320     llvm::function_ref<const PostDominatorTree &()> GetPDT) {
1321   // Ideally, we want to calculate tagged stack base pointer, and rewrite all
1322   // alloca addresses using that. Unfortunately, offsets are not known yet
1323   // (unless we use ASan-style mega-alloca). Instead we keep the base tag in a
1324   // temp, shift-OR it into each alloca address and xor with the retag mask.
1325   // This generates one extra instruction per alloca use.
1326   unsigned int I = 0;
1327 
1328   for (auto &KV : SInfo.AllocasToInstrument) {
1329     auto N = I++;
1330     auto *AI = KV.first;
1331     memtag::AllocaInfo &Info = KV.second;
1332     IRBuilder<> IRB(AI->getNextNode());
1333 
1334     // Replace uses of the alloca with tagged address.
1335     Value *Tag = getAllocaTag(IRB, StackTag, AI, N);
1336     Value *AILong = IRB.CreatePointerCast(AI, IntptrTy);
1337     Value *Replacement = tagPointer(IRB, AI->getType(), AILong, Tag);
1338     std::string Name =
1339         AI->hasName() ? AI->getName().str() : "alloca." + itostr(N);
1340     Replacement->setName(Name + ".hwasan");
1341 
1342     size_t Size = memtag::getAllocaSizeInBytes(*AI);
1343     size_t AlignedSize = alignTo(Size, Mapping.getObjectAlignment());
1344 
1345     Value *AICast = IRB.CreatePointerCast(AI, Int8PtrTy);
1346 
1347     auto HandleLifetime = [&](IntrinsicInst *II) {
1348       // Set the lifetime intrinsic to cover the whole alloca. This reduces the
1349       // set of assumptions we need to make about the lifetime. Without this we
1350       // would need to ensure that we can track the lifetime pointer to a
1351       // constant offset from the alloca, and would still need to change the
1352       // size to include the extra alignment we use for the untagging to make
1353       // the size consistent.
1354       //
1355       // The check for standard lifetime below makes sure that we have exactly
1356       // one set of start / end in any execution (i.e. the ends are not
1357       // reachable from each other), so this will not cause any problems.
1358       II->setArgOperand(0, ConstantInt::get(Int64Ty, AlignedSize));
1359       II->setArgOperand(1, AICast);
1360     };
1361     llvm::for_each(Info.LifetimeStart, HandleLifetime);
1362     llvm::for_each(Info.LifetimeEnd, HandleLifetime);
1363 
1364     AI->replaceUsesWithIf(Replacement, [AICast, AILong](Use &U) {
1365       auto *User = U.getUser();
1366       return User != AILong && User != AICast && !isLifetimeIntrinsic(User);
1367     });
1368 
1369     for (auto *DDI : Info.DbgVariableIntrinsics) {
1370       // Prepend "tag_offset, N" to the dwarf expression.
1371       // Tag offset logically applies to the alloca pointer, and it makes sense
1372       // to put it at the beginning of the expression.
1373       SmallVector<uint64_t, 8> NewOps = {dwarf::DW_OP_LLVM_tag_offset,
1374                                          retagMask(N)};
1375       for (size_t LocNo = 0; LocNo < DDI->getNumVariableLocationOps(); ++LocNo)
1376         if (DDI->getVariableLocationOp(LocNo) == AI)
1377           DDI->setExpression(DIExpression::appendOpsToArg(DDI->getExpression(),
1378                                                           NewOps, LocNo));
1379     }
1380 
1381     auto TagEnd = [&](Instruction *Node) {
1382       IRB.SetInsertPoint(Node);
1383       Value *UARTag = getUARTag(IRB, StackTag);
1384       // When untagging, use the `AlignedSize` because we need to set the tags
1385       // for the entire alloca to zero. If we used `Size` here, we would
1386       // keep the last granule tagged, and store zero in the last byte of the
1387       // last granule, due to how short granules are implemented.
1388       tagAlloca(IRB, AI, UARTag, AlignedSize);
1389     };
1390     // Calls to functions that may return twice (e.g. setjmp) confuse the
1391     // postdominator analysis, and will leave us to keep memory tagged after
1392     // function return. Work around this by always untagging at every return
1393     // statement if return_twice functions are called.
1394     bool StandardLifetime =
1395         SInfo.UnrecognizedLifetimes.empty() &&
1396         memtag::isStandardLifetime(Info.LifetimeStart, Info.LifetimeEnd,
1397                                    &GetDT(), ClMaxLifetimes) &&
1398         !SInfo.CallsReturnTwice;
1399     if (DetectUseAfterScope && StandardLifetime) {
1400       IntrinsicInst *Start = Info.LifetimeStart[0];
1401       IRB.SetInsertPoint(Start->getNextNode());
1402       tagAlloca(IRB, AI, Tag, Size);
1403       if (!memtag::forAllReachableExits(GetDT(), GetPDT(), Start,
1404                                         Info.LifetimeEnd, SInfo.RetVec,
1405                                         TagEnd)) {
1406         for (auto *End : Info.LifetimeEnd)
1407           End->eraseFromParent();
1408       }
1409     } else {
1410       tagAlloca(IRB, AI, Tag, Size);
1411       for (auto *RI : SInfo.RetVec)
1412         TagEnd(RI);
1413       // We inserted tagging outside of the lifetimes, so we have to remove
1414       // them.
1415       for (auto &II : Info.LifetimeStart)
1416         II->eraseFromParent();
1417       for (auto &II : Info.LifetimeEnd)
1418         II->eraseFromParent();
1419     }
1420     memtag::alignAndPadAlloca(Info, Align(Mapping.getObjectAlignment()));
1421   }
1422   for (auto &I : SInfo.UnrecognizedLifetimes)
1423     I->eraseFromParent();
1424   return true;
1425 }
1426 
1427 bool HWAddressSanitizer::isInterestingAlloca(const AllocaInst &AI) {
1428   return (AI.getAllocatedType()->isSized() &&
1429           // FIXME: instrument dynamic allocas, too
1430           AI.isStaticAlloca() &&
1431           // alloca() may be called with 0 size, ignore it.
1432           memtag::getAllocaSizeInBytes(AI) > 0 &&
1433           // We are only interested in allocas not promotable to registers.
1434           // Promotable allocas are common under -O0.
1435           !isAllocaPromotable(&AI) &&
1436           // inalloca allocas are not treated as static, and we don't want
1437           // dynamic alloca instrumentation for them as well.
1438           !AI.isUsedWithInAlloca() &&
1439           // swifterror allocas are register promoted by ISel
1440           !AI.isSwiftError()) &&
1441          // safe allocas are not interesting
1442          !(SSI && SSI->isSafe(AI));
1443 }
1444 
1445 bool HWAddressSanitizer::sanitizeFunction(
1446     Function &F, llvm::function_ref<const DominatorTree &()> GetDT,
1447     llvm::function_ref<const PostDominatorTree &()> GetPDT) {
1448   if (&F == HwasanCtorFunction)
1449     return false;
1450 
1451   if (!F.hasFnAttribute(Attribute::SanitizeHWAddress))
1452     return false;
1453 
1454   LLVM_DEBUG(dbgs() << "Function: " << F.getName() << "\n");
1455 
1456   SmallVector<InterestingMemoryOperand, 16> OperandsToInstrument;
1457   SmallVector<MemIntrinsic *, 16> IntrinToInstrument;
1458   SmallVector<Instruction *, 8> LandingPadVec;
1459 
1460   memtag::StackInfoBuilder SIB(
1461       [this](const AllocaInst &AI) { return isInterestingAlloca(AI); });
1462   for (auto &Inst : instructions(F)) {
1463     if (InstrumentStack) {
1464       SIB.visit(Inst);
1465     }
1466 
1467     if (InstrumentLandingPads && isa<LandingPadInst>(Inst))
1468       LandingPadVec.push_back(&Inst);
1469 
1470     getInterestingMemoryOperands(&Inst, OperandsToInstrument);
1471 
1472     if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(&Inst))
1473       if (!ignoreMemIntrinsic(MI))
1474         IntrinToInstrument.push_back(MI);
1475   }
1476 
1477   memtag::StackInfo &SInfo = SIB.get();
1478 
1479   initializeCallbacks(*F.getParent());
1480 
1481   bool Changed = false;
1482 
1483   if (!LandingPadVec.empty())
1484     Changed |= instrumentLandingPads(LandingPadVec);
1485 
1486   if (SInfo.AllocasToInstrument.empty() && F.hasPersonalityFn() &&
1487       F.getPersonalityFn()->getName() == kHwasanPersonalityThunkName) {
1488     // __hwasan_personality_thunk is a no-op for functions without an
1489     // instrumented stack, so we can drop it.
1490     F.setPersonalityFn(nullptr);
1491     Changed = true;
1492   }
1493 
1494   if (SInfo.AllocasToInstrument.empty() && OperandsToInstrument.empty() &&
1495       IntrinToInstrument.empty())
1496     return Changed;
1497 
1498   assert(!ShadowBase);
1499 
1500   Instruction *InsertPt = &*F.getEntryBlock().begin();
1501   IRBuilder<> EntryIRB(InsertPt);
1502   emitPrologue(EntryIRB,
1503                /*WithFrameRecord*/ ClRecordStackHistory &&
1504                    Mapping.WithFrameRecord &&
1505                    !SInfo.AllocasToInstrument.empty());
1506 
1507   if (!SInfo.AllocasToInstrument.empty()) {
1508     Value *StackTag =
1509         ClGenerateTagsWithCalls ? nullptr : getStackBaseTag(EntryIRB);
1510     instrumentStack(SInfo, StackTag, GetDT, GetPDT);
1511   }
1512 
1513   // If we split the entry block, move any allocas that were originally in the
1514   // entry block back into the entry block so that they aren't treated as
1515   // dynamic allocas.
1516   if (EntryIRB.GetInsertBlock() != &F.getEntryBlock()) {
1517     InsertPt = &*F.getEntryBlock().begin();
1518     for (Instruction &I :
1519          llvm::make_early_inc_range(*EntryIRB.GetInsertBlock())) {
1520       if (auto *AI = dyn_cast<AllocaInst>(&I))
1521         if (isa<ConstantInt>(AI->getArraySize()))
1522           I.moveBefore(InsertPt);
1523     }
1524   }
1525 
1526   for (auto &Operand : OperandsToInstrument)
1527     instrumentMemAccess(Operand);
1528 
1529   if (ClInstrumentMemIntrinsics && !IntrinToInstrument.empty()) {
1530     for (auto Inst : IntrinToInstrument)
1531       instrumentMemIntrinsic(cast<MemIntrinsic>(Inst));
1532   }
1533 
1534   ShadowBase = nullptr;
1535   StackBaseTag = nullptr;
1536 
1537   return true;
1538 }
1539 
1540 void HWAddressSanitizer::instrumentGlobal(GlobalVariable *GV, uint8_t Tag) {
1541   assert(!UsePageAliases);
1542   Constant *Initializer = GV->getInitializer();
1543   uint64_t SizeInBytes =
1544       M.getDataLayout().getTypeAllocSize(Initializer->getType());
1545   uint64_t NewSize = alignTo(SizeInBytes, Mapping.getObjectAlignment());
1546   if (SizeInBytes != NewSize) {
1547     // Pad the initializer out to the next multiple of 16 bytes and add the
1548     // required short granule tag.
1549     std::vector<uint8_t> Init(NewSize - SizeInBytes, 0);
1550     Init.back() = Tag;
1551     Constant *Padding = ConstantDataArray::get(*C, Init);
1552     Initializer = ConstantStruct::getAnon({Initializer, Padding});
1553   }
1554 
1555   auto *NewGV = new GlobalVariable(M, Initializer->getType(), GV->isConstant(),
1556                                    GlobalValue::ExternalLinkage, Initializer,
1557                                    GV->getName() + ".hwasan");
1558   NewGV->copyAttributesFrom(GV);
1559   NewGV->setLinkage(GlobalValue::PrivateLinkage);
1560   NewGV->copyMetadata(GV, 0);
1561   NewGV->setAlignment(
1562       MaybeAlign(std::max(GV->getAlignment(), Mapping.getObjectAlignment())));
1563 
1564   // It is invalid to ICF two globals that have different tags. In the case
1565   // where the size of the global is a multiple of the tag granularity the
1566   // contents of the globals may be the same but the tags (i.e. symbol values)
1567   // may be different, and the symbols are not considered during ICF. In the
1568   // case where the size is not a multiple of the granularity, the short granule
1569   // tags would discriminate two globals with different tags, but there would
1570   // otherwise be nothing stopping such a global from being incorrectly ICF'd
1571   // with an uninstrumented (i.e. tag 0) global that happened to have the short
1572   // granule tag in the last byte.
1573   NewGV->setUnnamedAddr(GlobalValue::UnnamedAddr::None);
1574 
1575   // Descriptor format (assuming little-endian):
1576   // bytes 0-3: relative address of global
1577   // bytes 4-6: size of global (16MB ought to be enough for anyone, but in case
1578   // it isn't, we create multiple descriptors)
1579   // byte 7: tag
1580   auto *DescriptorTy = StructType::get(Int32Ty, Int32Ty);
1581   const uint64_t MaxDescriptorSize = 0xfffff0;
1582   for (uint64_t DescriptorPos = 0; DescriptorPos < SizeInBytes;
1583        DescriptorPos += MaxDescriptorSize) {
1584     auto *Descriptor =
1585         new GlobalVariable(M, DescriptorTy, true, GlobalValue::PrivateLinkage,
1586                            nullptr, GV->getName() + ".hwasan.descriptor");
1587     auto *GVRelPtr = ConstantExpr::getTrunc(
1588         ConstantExpr::getAdd(
1589             ConstantExpr::getSub(
1590                 ConstantExpr::getPtrToInt(NewGV, Int64Ty),
1591                 ConstantExpr::getPtrToInt(Descriptor, Int64Ty)),
1592             ConstantInt::get(Int64Ty, DescriptorPos)),
1593         Int32Ty);
1594     uint32_t Size = std::min(SizeInBytes - DescriptorPos, MaxDescriptorSize);
1595     auto *SizeAndTag = ConstantInt::get(Int32Ty, Size | (uint32_t(Tag) << 24));
1596     Descriptor->setComdat(NewGV->getComdat());
1597     Descriptor->setInitializer(ConstantStruct::getAnon({GVRelPtr, SizeAndTag}));
1598     Descriptor->setSection("hwasan_globals");
1599     Descriptor->setMetadata(LLVMContext::MD_associated,
1600                             MDNode::get(*C, ValueAsMetadata::get(NewGV)));
1601     appendToCompilerUsed(M, Descriptor);
1602   }
1603 
1604   Constant *Aliasee = ConstantExpr::getIntToPtr(
1605       ConstantExpr::getAdd(
1606           ConstantExpr::getPtrToInt(NewGV, Int64Ty),
1607           ConstantInt::get(Int64Ty, uint64_t(Tag) << PointerTagShift)),
1608       GV->getType());
1609   auto *Alias = GlobalAlias::create(GV->getValueType(), GV->getAddressSpace(),
1610                                     GV->getLinkage(), "", Aliasee, &M);
1611   Alias->setVisibility(GV->getVisibility());
1612   Alias->takeName(GV);
1613   GV->replaceAllUsesWith(Alias);
1614   GV->eraseFromParent();
1615 }
1616 
1617 static DenseSet<GlobalVariable *> getExcludedGlobals(Module &M) {
1618   NamedMDNode *Globals = M.getNamedMetadata("llvm.asan.globals");
1619   if (!Globals)
1620     return DenseSet<GlobalVariable *>();
1621   DenseSet<GlobalVariable *> Excluded(Globals->getNumOperands());
1622   for (auto MDN : Globals->operands()) {
1623     // Metadata node contains the global and the fields of "Entry".
1624     assert(MDN->getNumOperands() == 5);
1625     auto *V = mdconst::extract_or_null<Constant>(MDN->getOperand(0));
1626     // The optimizer may optimize away a global entirely.
1627     if (!V)
1628       continue;
1629     auto *StrippedV = V->stripPointerCasts();
1630     auto *GV = dyn_cast<GlobalVariable>(StrippedV);
1631     if (!GV)
1632       continue;
1633     ConstantInt *IsExcluded = mdconst::extract<ConstantInt>(MDN->getOperand(4));
1634     if (IsExcluded->isOne())
1635       Excluded.insert(GV);
1636   }
1637   return Excluded;
1638 }
1639 
1640 void HWAddressSanitizer::instrumentGlobals() {
1641   std::vector<GlobalVariable *> Globals;
1642   auto ExcludedGlobals = getExcludedGlobals(M);
1643   for (GlobalVariable &GV : M.globals()) {
1644     if (ExcludedGlobals.count(&GV))
1645       continue;
1646 
1647     if (GV.isDeclarationForLinker() || GV.getName().startswith("llvm.") ||
1648         GV.isThreadLocal())
1649       continue;
1650 
1651     // Common symbols can't have aliases point to them, so they can't be tagged.
1652     if (GV.hasCommonLinkage())
1653       continue;
1654 
1655     // Globals with custom sections may be used in __start_/__stop_ enumeration,
1656     // which would be broken both by adding tags and potentially by the extra
1657     // padding/alignment that we insert.
1658     if (GV.hasSection())
1659       continue;
1660 
1661     Globals.push_back(&GV);
1662   }
1663 
1664   MD5 Hasher;
1665   Hasher.update(M.getSourceFileName());
1666   MD5::MD5Result Hash;
1667   Hasher.final(Hash);
1668   uint8_t Tag = Hash[0];
1669 
1670   for (GlobalVariable *GV : Globals) {
1671     Tag &= TagMaskByte;
1672     // Skip tag 0 in order to avoid collisions with untagged memory.
1673     if (Tag == 0)
1674       Tag = 1;
1675     instrumentGlobal(GV, Tag++);
1676   }
1677 }
1678 
1679 void HWAddressSanitizer::instrumentPersonalityFunctions() {
1680   // We need to untag stack frames as we unwind past them. That is the job of
1681   // the personality function wrapper, which either wraps an existing
1682   // personality function or acts as a personality function on its own. Each
1683   // function that has a personality function or that can be unwound past has
1684   // its personality function changed to a thunk that calls the personality
1685   // function wrapper in the runtime.
1686   MapVector<Constant *, std::vector<Function *>> PersonalityFns;
1687   for (Function &F : M) {
1688     if (F.isDeclaration() || !F.hasFnAttribute(Attribute::SanitizeHWAddress))
1689       continue;
1690 
1691     if (F.hasPersonalityFn()) {
1692       PersonalityFns[F.getPersonalityFn()->stripPointerCasts()].push_back(&F);
1693     } else if (!F.hasFnAttribute(Attribute::NoUnwind)) {
1694       PersonalityFns[nullptr].push_back(&F);
1695     }
1696   }
1697 
1698   if (PersonalityFns.empty())
1699     return;
1700 
1701   FunctionCallee HwasanPersonalityWrapper = M.getOrInsertFunction(
1702       "__hwasan_personality_wrapper", Int32Ty, Int32Ty, Int32Ty, Int64Ty,
1703       Int8PtrTy, Int8PtrTy, Int8PtrTy, Int8PtrTy, Int8PtrTy);
1704   FunctionCallee UnwindGetGR = M.getOrInsertFunction("_Unwind_GetGR", VoidTy);
1705   FunctionCallee UnwindGetCFA = M.getOrInsertFunction("_Unwind_GetCFA", VoidTy);
1706 
1707   for (auto &P : PersonalityFns) {
1708     std::string ThunkName = kHwasanPersonalityThunkName;
1709     if (P.first)
1710       ThunkName += ("." + P.first->getName()).str();
1711     FunctionType *ThunkFnTy = FunctionType::get(
1712         Int32Ty, {Int32Ty, Int32Ty, Int64Ty, Int8PtrTy, Int8PtrTy}, false);
1713     bool IsLocal = P.first && (!isa<GlobalValue>(P.first) ||
1714                                cast<GlobalValue>(P.first)->hasLocalLinkage());
1715     auto *ThunkFn = Function::Create(ThunkFnTy,
1716                                      IsLocal ? GlobalValue::InternalLinkage
1717                                              : GlobalValue::LinkOnceODRLinkage,
1718                                      ThunkName, &M);
1719     if (!IsLocal) {
1720       ThunkFn->setVisibility(GlobalValue::HiddenVisibility);
1721       ThunkFn->setComdat(M.getOrInsertComdat(ThunkName));
1722     }
1723 
1724     auto *BB = BasicBlock::Create(*C, "entry", ThunkFn);
1725     IRBuilder<> IRB(BB);
1726     CallInst *WrapperCall = IRB.CreateCall(
1727         HwasanPersonalityWrapper,
1728         {ThunkFn->getArg(0), ThunkFn->getArg(1), ThunkFn->getArg(2),
1729          ThunkFn->getArg(3), ThunkFn->getArg(4),
1730          P.first ? IRB.CreateBitCast(P.first, Int8PtrTy)
1731                  : Constant::getNullValue(Int8PtrTy),
1732          IRB.CreateBitCast(UnwindGetGR.getCallee(), Int8PtrTy),
1733          IRB.CreateBitCast(UnwindGetCFA.getCallee(), Int8PtrTy)});
1734     WrapperCall->setTailCall();
1735     IRB.CreateRet(WrapperCall);
1736 
1737     for (Function *F : P.second)
1738       F->setPersonalityFn(ThunkFn);
1739   }
1740 }
1741 
1742 void HWAddressSanitizer::ShadowMapping::init(Triple &TargetTriple,
1743                                              bool InstrumentWithCalls) {
1744   Scale = kDefaultShadowScale;
1745   if (TargetTriple.isOSFuchsia()) {
1746     // Fuchsia is always PIE, which means that the beginning of the address
1747     // space is always available.
1748     InGlobal = false;
1749     InTls = false;
1750     Offset = 0;
1751     WithFrameRecord = true;
1752   } else if (ClMappingOffset.getNumOccurrences() > 0) {
1753     InGlobal = false;
1754     InTls = false;
1755     Offset = ClMappingOffset;
1756     WithFrameRecord = false;
1757   } else if (ClEnableKhwasan || InstrumentWithCalls) {
1758     InGlobal = false;
1759     InTls = false;
1760     Offset = 0;
1761     WithFrameRecord = false;
1762   } else if (ClWithIfunc) {
1763     InGlobal = true;
1764     InTls = false;
1765     Offset = kDynamicShadowSentinel;
1766     WithFrameRecord = false;
1767   } else if (ClWithTls) {
1768     InGlobal = false;
1769     InTls = true;
1770     Offset = kDynamicShadowSentinel;
1771     WithFrameRecord = true;
1772   } else {
1773     InGlobal = false;
1774     InTls = false;
1775     Offset = kDynamicShadowSentinel;
1776     WithFrameRecord = false;
1777   }
1778 }
1779