hwasan: Use bits [3..11) of the ring buffer entry address as the base stack tag.

[pcc]

Summary

This saves roughly 32 bytes of instructions per function with stack objects
and causes us to preserve enough information that we can recover the original
tags of all stack variables.

Now that stack tags are deterministic, we no longer need to pass
-hwasan-generate-tags-with-calls during check-hwasan. This also means that the
new stack tag generation mechanism is exercised by check-hwasan.

Depends on D63119

[eugenis]

llvm/lib/Transforms/Instrumentation/HWAddressSanitizer.cpp

1007

We are losing a lot of entropy by allowing these zero bits in the base tag. Single-alloca functions, for example, will only have 32 different tags.

How about using bits 3 .. 11 ?

[pcc]

• Address review comments

[pcc]

llvm/lib/Transforms/Instrumentation/HWAddressSanitizer.cpp

1007

Done. Now tag 0 is as likely as any other tag.

To fix the tests that were assuming that they would never get tag 0, I've added a call to a helper function that bumps the base tag to 128 to the tests that would otherwise fail.

[eugenis]

We can make the tags undeterministic again by starting each ring buffer at a random index.

[pcc]

• Sort FastMasks by increasing probability of collisions

[eugenis]

compiler-rt/test/hwasan/TestCases/random-align-right.c

30 ↗

(On Diff #205130)

why did you copy this line?

compiler-rt/test/hwasan/TestCases/stack-history-length.c

20 ↗

(On Diff #205130)

I don't understand this. How does a single additional call to FUNC help guarantee that property?

[pcc]

compiler-rt/test/hwasan/TestCases/random-align-right.c

30 ↗

(On Diff #205130)

Because the additional call to GenerateRandomTag in InitRandomState causes the values that we assign to tail_magic in HwasanAllocatorInit to change in such a way that we catch the second bad access and not the first one. Without copying this line the CHECK?-NEXT lines fail to match because the failure doesn't happen on the line after the first message.

compiler-rt/test/hwasan/TestCases/stack-history-length.c

20 ↗

(On Diff #205130)

In the case where there are 2046 calls to FUNC we have:

• tag 1 for FUNC0
• tag 2..2047 (mod 256) for FUNC1
• tag 2048 (mod 256) for OOB (i.e. 0)

Adding the call to FUNC shifts all of the tags by 1 so that OOB gets tag 1.

[eugenis]

compiler-rt/test/hwasan/TestCases/random-align-right.c

30 ↗

(On Diff #205130)

Wait, so the comment above the loop lies? We are testing for the bug on the first iteration, not an any iteration. Maybe remove -NEXT?

compiler-rt/test/hwasan/TestCases/stack-history-length.c

20 ↗

(On Diff #205130)

Could we call OOB twice instead? And weaken the test a bit so that it is ok with result being off by 1 or 2 in any direction?

[pcc]

• Address review comments

compiler-rt/test/hwasan/TestCases/random-align-right.c

30 ↗

(On Diff #205130)

Yeah, looks like a mistake in the test. The intent here was apparently that we'd let any access fail, but the test actually only lets the first access fail (and because of determinism that is always what happens).

We can't just remove -NEXT because it would prevent the test from determining which access found the bug. So I've rewritten this test a bit so that we can do that.

compiler-rt/test/hwasan/TestCases/stack-history-length.c

20 ↗

(On Diff #205130)

Works for me, done.

[eugenis]

LGTM

compiler-rt/test/hwasan/lit.cfg

 # -*- Python -*-
 
 import os
 
 # Setup config name.
 config.name = 'HWAddressSanitizer' + getattr(config, 'name_suffix', 'default')
 
 # Setup source root.
 config.test_source_root = os.path.dirname(__file__)
 
 # Setup default compiler flags used with -fsanitize=memory option.
 clang_cflags = [config.target_cflags] + config.debug_info_flags
 clang_cxxflags = config.cxx_mode_flags + clang_cflags
-clang_hwasan_cflags = ["-fsanitize=hwaddress", "-mllvm", "-hwasan-generate-tags-with-calls"] + clang_cflags
+clang_hwasan_cflags = ["-fsanitize=hwaddress"] + clang_cflags
 clang_hwasan_cxxflags = config.cxx_mode_flags + clang_hwasan_cflags
 
 def build_invocation(compile_flags):
   return " " + " ".join([config.clang] + compile_flags) + " "
 
 config.substitutions.append( ("%clangxx ", build_invocation(clang_cxxflags)) )
 config.substitutions.append( ("%clang_hwasan ", build_invocation(clang_hwasan_cflags)) )
 config.substitutions.append( ("%clangxx_hwasan ", build_invocation(clang_hwasan_cxxflags)) )

llvm/lib/Transforms/Instrumentation/HWAddressSanitizer.cpp

public:
   bool instrumentLandingPads(SmallVectorImpl<Instruction *> &RetVec);
   Value *getNextTagWithCall(IRBuilder<> &IRB);
   Value *getStackBaseTag(IRBuilder<> &IRB);
   Value *getAllocaTag(IRBuilder<> &IRB, Value *StackTag, AllocaInst *AI,
                      unsigned AllocaNo);
   Value *getUARTag(IRBuilder<> &IRB, Value *StackTag);
 
   Value *getHwasanThreadSlotPtr(IRBuilder<> &IRB, Type *Ty);
-  Value *emitPrologue(IRBuilder<> &IRB, bool WithFrameRecord);
+  void emitPrologue(IRBuilder<> &IRB, bool WithFrameRecord);
 
 private:
   LLVMContext *C;
   std::string CurModuleUniqueId;
   Triple TargetTriple;
   FunctionCallee HWAsanMemmove, HWAsanMemcpy, HWAsanMemset;
   FunctionCallee HWAsanHandleVfork;
 
private:
 
   FunctionCallee HwasanTagMemoryFunc;
   FunctionCallee HwasanGenerateTagFunc;
   FunctionCallee HwasanThreadEnterFunc;
 
   Constant *ShadowGlobal;
 
   Value *LocalDynamicShadow = nullptr;
+  Value *StackBaseTag = nullptr;
   GlobalValue *ThreadPtrGlobal = nullptr;
 };
 
 class HWAddressSanitizerLegacyPass : public FunctionPass {
 public:
   // Pass identification, replacement for typeid.
   static char ID;
 

 
 Value *HWAddressSanitizer::getNextTagWithCall(IRBuilder<> &IRB) {
   return IRB.CreateZExt(IRB.CreateCall(HwasanGenerateTagFunc), IntptrTy);
 }
 
 Value *HWAddressSanitizer::getStackBaseTag(IRBuilder<> &IRB) {
   if (ClGenerateTagsWithCalls)
     return getNextTagWithCall(IRB);
+  if (StackBaseTag)
+    return StackBaseTag;
   // FIXME: use addressofreturnaddress (but implement it in aarch64 backend
   // first).
   Module *M = IRB.GetInsertBlock()->getParent()->getParent();
   auto GetStackPointerFn =
       Intrinsic::getDeclaration(M, Intrinsic::frameaddress);
   Value *StackPointer = IRB.CreateCall(
       GetStackPointerFn, {Constant::getNullValue(IRB.getInt32Ty())});
 
void HWAddressSanitizer::createFrameGlobal(Function &F,
   GV->setSection(getFrameSection());
   appendToCompilerUsed(M, GV);
   // Put GV into the F's Comadat so that if F is deleted GV can be deleted too.
   if (auto Comdat =
           GetOrCreateFunctionComdat(F, TargetTriple, CurModuleUniqueId))
     GV->setComdat(Comdat);
 }
 
-Value *HWAddressSanitizer::emitPrologue(IRBuilder<> &IRB,
-                                        bool WithFrameRecord) {
-  if (!Mapping.InTls)
-    return getDynamicShadowNonTls(IRB);
+void HWAddressSanitizer::emitPrologue(IRBuilder<> &IRB, bool WithFrameRecord) {
+  if (!Mapping.InTls) {
+    LocalDynamicShadow = getDynamicShadowNonTls(IRB);
+    return;
+  }
 
-  if (!WithFrameRecord && TargetTriple.isAndroid())
-    return getDynamicShadowIfunc(IRB);
+  if (!WithFrameRecord && TargetTriple.isAndroid()) {
+    LocalDynamicShadow = getDynamicShadowIfunc(IRB);
+    return;
+  }
 
   Value *SlotPtr = getHwasanThreadSlotPtr(IRB, IntptrTy);
   assert(SlotPtr);
 
   Instruction *ThreadLong = IRB.CreateLoad(IntptrTy, SlotPtr);
 
   Function *F = IRB.GetInsertBlock()->getParent();
   if (F->getFnAttribute("hwasan-abi").getValueAsString() == "interceptor") {
if (F->getFnAttribute("hwasan-abi").getValueAsString() == "interceptor") {
     ThreadLong = ThreadLongPhi;
   }
 
   // Extract the address field from ThreadLong. Unnecessary on AArch64 with TBI.
   Value *ThreadLongMaybeUntagged =
       TargetTriple.isAArch64() ? ThreadLong : untagPointer(IRB, ThreadLong);
 
   if (WithFrameRecord) {
+    StackBaseTag = ThreadLong;
+
     // Prepare ring buffer data.
     auto PC = IRB.CreatePtrToInt(F, IntptrTy);
     auto GetStackPointerFn =
         Intrinsic::getDeclaration(F->getParent(), Intrinsic::frameaddress);
     Value *SP = IRB.CreatePtrToInt(
         IRB.CreateCall(GetStackPointerFn,
                        {Constant::getNullValue(IRB.getInt32Ty())}),
         IntptrTy);
-    // Mix SP and PC. TODO: also add the tag to the mix.
+    // Mix SP and PC.
     // Assumptions:
     // PC is 0x0000PPPPPPPPPPPP  (48 bits are meaningful, others are zero)
     // SP is 0xsssssssssssSSSS0  (4 lower bits are zero)
     // We only really need ~20 lower non-zero bits (SSSS), so we mix like this:
     //       0xSSSSPPPPPPPPPPPP
     SP = IRB.CreateShl(SP, 44);
 
     // Store data to ring buffer.
if (WithFrameRecord) {
     Value *ThreadLongNew = IRB.CreateAnd(
         IRB.CreateAdd(ThreadLong, ConstantInt::get(IntptrTy, 8)), WrapMask);
     IRB.CreateStore(ThreadLongNew, SlotPtr);
   }
 
   // Get shadow base address by aligning RecordPtr up.
   // Note: this is not correct if the pointer is already aligned.
   // Runtime library will make sure this never happens.
-  Value *ShadowBase = IRB.CreateAdd(
+  LocalDynamicShadow = IRB.CreateAdd(
       IRB.CreateOr(
           ThreadLongMaybeUntagged,
           ConstantInt::get(IntptrTy, (1ULL << kShadowBaseAlignment) - 1)),
       ConstantInt::get(IntptrTy, 1), "hwasan.shadow");
-  ShadowBase = IRB.CreateIntToPtr(ShadowBase, Int8PtrTy);
-  return ShadowBase;
+  LocalDynamicShadow = IRB.CreateIntToPtr(LocalDynamicShadow, Int8PtrTy);
 }
 
 bool HWAddressSanitizer::instrumentLandingPads(
     SmallVectorImpl<Instruction *> &LandingPadVec) {
   Module *M = LandingPadVec[0]->getModule();
   Function *ReadRegister =
       Intrinsic::getDeclaration(M, Intrinsic::read_register, IntptrTy);
   const char *RegName =
bool HWAddressSanitizer::instrumentStack(
     SmallVectorImpl<AllocaInst *> &Allocas,
     DenseMap<AllocaInst *, std::vector<DbgDeclareInst *>> &AllocaDeclareMap,
     SmallVectorImpl<Instruction *> &RetVec, Value *StackTag) {
   // Ideally, we want to calculate tagged stack base pointer, and rewrite all
   // alloca addresses using that. Unfortunately, offsets are not known yet
   // (unless we use ASan-style mega-alloca). Instead we keep the base tag in a
   // temp, shift-OR it into each alloca address and xor with the retag mask.
   // This generates one extra instruction per alloca use.
-  for (unsigned N = 0; N < Allocas.size(); ++N) {
-    auto *AI = Allocas[N];
+  uint8_t TagOffset = 0;
+  for (AllocaInst *AI : Allocas) {
+    // The base tag will be a multiple of 8, so we should avoid using tags with
+    // lower bits clear so that we don't end up with a final tag of 0.
+    ++TagOffset;
+    if ((TagOffset & 7) == 0)
+      ++TagOffset;
+
     IRBuilder<> IRB(AI->getNextNode());
 
     // Replace uses of the alloca with tagged address.
-    Value *Tag = getAllocaTag(IRB, StackTag, AI, N);
+    Value *Tag = getAllocaTag(IRB, StackTag, AI, TagOffset);
     Value *AILong = IRB.CreatePointerCast(AI, IntptrTy);
     Value *Replacement = tagPointer(IRB, AI->getType(), AILong, Tag);
     std::string Name =
-        AI->hasName() ? AI->getName().str() : "alloca." + itostr(N);
+        AI->hasName() ? AI->getName().str() : "alloca." + itostr(TagOffset);
     Replacement->setName(Name + ".hwasan");
 
     for (auto UI = AI->use_begin(), UE = AI->use_end(); UI != UE;) {
       Use &U = *UI++;
       if (U.getUser() != AILong)
         U.set(Replacement);
     }
 
     for (auto *DDI : AllocaDeclareMap.lookup(AI)) {
       DIExpression *OldExpr = DDI->getExpression();
-      DIExpression *NewExpr =
-          DIExpression::append(OldExpr, {dwarf::DW_OP_LLVM_tag_offset, N});
+      DIExpression *NewExpr = DIExpression::append(
+          OldExpr, {dwarf::DW_OP_LLVM_tag_offset, TagOffset});
       DDI->setArgOperand(2, MetadataAsValue::get(*C, NewExpr));
     }
 
     tagAlloca(IRB, AI, Tag);
 
     for (auto RI : RetVec) {
       IRB.SetInsertPoint(RI);
 
bool HWAddressSanitizer::sanitizeFunction(Function &F) {
   if (ClCreateFrameDescriptions && !AllocasToInstrument.empty())
     createFrameGlobal(F, createFrameString(AllocasToInstrument));
 
 
   assert(!LocalDynamicShadow);
 
   Instruction *InsertPt = &*F.getEntryBlock().begin();
   IRBuilder<> EntryIRB(InsertPt);
-  LocalDynamicShadow = emitPrologue(EntryIRB,
-                                    /*WithFrameRecord*/ ClRecordStackHistory &&
-                                        !AllocasToInstrument.empty());
+  emitPrologue(EntryIRB,
 
   bool Changed = false;
   if (!AllocasToInstrument.empty()) {
     Value *StackTag =
         ClGenerateTagsWithCalls ? nullptr : getStackBaseTag(EntryIRB);
     Changed |= instrumentStack(AllocasToInstrument, AllocaDeclareMap, RetVec,
                                StackTag);
   }
for (auto II = EntryIRB.GetInsertBlock()->begin(),
           I->moveBefore(InsertPt);
     }
   }
 
   for (auto Inst : ToInstrument)
     Changed |= instrumentMemAccess(Inst);
 
   LocalDynamicShadow = nullptr;
+  StackBaseTag = nullptr;
 
   return Changed;
 }
 
 void HWAddressSanitizer::ShadowMapping::init(Triple &TargetTriple) {
   Scale = kDefaultShadowScale;
   if (ClMappingOffset.getNumOccurrences() > 0) {
     InGlobal = false;

llvm/test/Instrumentation/HWAddressSanitizer/alloca.ll

 define void @test_alloca() sanitize_hwaddress {
 ; CHECK-LABEL: @test_alloca(
 ; CHECK: %[[FP:[^ ]*]] = call i8* @llvm.frameaddress(i32 0)
 ; CHECK: %[[A:[^ ]*]] = ptrtoint i8* %[[FP]] to i64
 ; CHECK: %[[B:[^ ]*]] = lshr i64 %[[A]], 20
 ; CHECK: %[[BASE_TAG:[^ ]*]] = xor i64 %[[A]], %[[B]]
 
 ; CHECK: %[[X:[^ ]*]] = alloca i32, align 16
-; CHECK: %[[X_TAG:[^ ]*]] = xor i64 %[[BASE_TAG]], 0
+; CHECK: %[[X_TAG:[^ ]*]] = xor i64 %[[BASE_TAG]], 1
 ; CHECK: %[[X1:[^ ]*]] = ptrtoint i32* %[[X]] to i64
 ; CHECK: %[[C:[^ ]*]] = shl i64 %[[X_TAG]], 56
 ; CHECK: %[[D:[^ ]*]] = or i64 %[[X1]], %[[C]]
 ; CHECK: %[[X_HWASAN:[^ ]*]] = inttoptr i64 %[[D]] to i32*
 
 ; CHECK: %[[X_TAG2:[^ ]*]] = trunc i64 %[[X_TAG]] to i8
 ; CHECK: %[[E:[^ ]*]] = ptrtoint i32* %[[X]] to i64
 ; CHECK: %[[F:[^ ]*]] = lshr i64 %[[E]], 4

llvm/test/Instrumentation/HWAddressSanitizer/dbg-declare-tag-offset.ll

 ; RUN: opt -hwasan -S -o - %s | FileCheck %s
 
 target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
 target triple = "aarch64--linux-android"
 
 declare void @g(i8**, i8**)
 
 define void @f() sanitize_hwaddress !dbg !6 {
 entry:
   %a = alloca i8*
   %b = alloca i8*
-  ; CHECK: @llvm.dbg.declare{{.*}} !DIExpression(DW_OP_LLVM_tag_offset, 0)
-  call void @llvm.dbg.declare(metadata i8** %a, metadata !12, metadata !DIExpression()), !dbg !14
-  ; CHECK: @llvm.dbg.declare{{.*}} !DIExpression(DW_OP_LLVM_tag_offset, 0)
+  ; CHECK: @llvm.dbg.declare{{.*}} !DIExpression(DW_OP_LLVM_tag_offset, 1)
   call void @llvm.dbg.declare(metadata i8** %a, metadata !12, metadata !DIExpression()), !dbg !14
   ; CHECK: @llvm.dbg.declare{{.*}} !DIExpression(DW_OP_LLVM_tag_offset, 1)
+  call void @llvm.dbg.declare(metadata i8** %a, metadata !12, metadata !DIExpression()), !dbg !14
+  ; CHECK: @llvm.dbg.declare{{.*}} !DIExpression(DW_OP_LLVM_tag_offset, 2)
   call void @llvm.dbg.declare(metadata i8** %b, metadata !13, metadata !DIExpression()), !dbg !14
-  ; CHECK: @llvm.dbg.declare{{.*}} !DIExpression(DW_OP_LLVM_tag_offset, 1)
+  ; CHECK: @llvm.dbg.declare{{.*}} !DIExpression(DW_OP_LLVM_tag_offset, 2)
   call void @llvm.dbg.declare(metadata i8** %b, metadata !13, metadata !DIExpression()), !dbg !14
   call void @g(i8** %a, i8** %b)
   ret void, !dbg !15
 }
 
 declare void @llvm.dbg.declare(metadata, metadata, metadata)
 
 !llvm.dbg.cu = !{!0}

llvm/test/Instrumentation/HWAddressSanitizer/kernel-alloca.ll

 define void @test_alloca() sanitize_hwaddress {
 ; CHECK-LABEL: @test_alloca(
 ; CHECK: %[[FP:[^ ]*]] = call i8* @llvm.frameaddress(i32 0)
 ; CHECK: %[[A:[^ ]*]] = ptrtoint i8* %[[FP]] to i64
 ; CHECK: %[[B:[^ ]*]] = lshr i64 %[[A]], 20
 ; CHECK: %[[BASE_TAG:[^ ]*]] = xor i64 %[[A]], %[[B]]
 
 ; CHECK: %[[X:[^ ]*]] = alloca i32, align 16
-; CHECK: %[[X_TAG:[^ ]*]] = xor i64 %[[BASE_TAG]], 0
+; CHECK: %[[X_TAG:[^ ]*]] = xor i64 %[[BASE_TAG]], 1
 ; CHECK: %[[X1:[^ ]*]] = ptrtoint i32* %[[X]] to i64
 ; CHECK: %[[C:[^ ]*]] = shl i64 %[[X_TAG]], 56
 ; CHECK: %[[D:[^ ]*]] = or i64 %[[C]], 72057594037927935
 ; CHECK: %[[E:[^ ]*]] = and i64 %[[X1]], %[[D]]
 ; CHECK: %[[X_HWASAN:[^ ]*]] = inttoptr i64 %[[E]] to i32*
 
 entry:
   %x = alloca i32, align 4
   call void @use32(i32* nonnull %x)
   ret void
 }

llvm/test/Instrumentation/HWAddressSanitizer/prologue.ll

 ; CHECK-HISTORY: %[[D3:[^ ]*]] = xor i64 %[[D2]], -1
 ; CHECK-HISTORY: %[[D4:[^ ]*]] = add i64 %[[D]], 8
 ; CHECK-HISTORY: %[[D5:[^ ]*]] = and i64 %[[D4]], %[[D3]]
 ; CHECK-HISTORY: store i64 %[[D5]], i64* %[[C]]
 
 ; CHECK-TLS:   %[[E:[^ ]*]] = or i64 %[[D]], 4294967295
 ; CHECK-TLS:   = add i64 %[[E]], 1
 
+; CHECK-HISTORY: = xor i64 %[[D]], 1
+
 ; CHECK-NOHISTORY-NOT: store i64
 
 
 entry:
   %x = alloca i32, align 4
   call void @use(i32* %x)
   ret void
 }