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