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