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