Implement variable-sized alloca instrumentation.

[m.ostapenko]

Summary

This patch implements variable-sized alloca instrumentation (https://code.google.com/p/address-sanitizer/issues/detail?id=138).

[kcc]

This does not handle stack-use-after-return for alloca, right?
I don't insist you implement that now, but consider for the next patch.

lib/Transforms/Instrumentation/AddressSanitizer.cpp

585

Please do it under a flag, off by default for now.

lib/asan/asan_interface_internal.h

181 ↗

(On Diff #15616)

indent

lib/asan/asan_internal.h

140

I think kAsanAllocaPartialMagic is redundant, just use kAsanAllocaRightMagic
(we may want to get rid of kAsanStackPartialRedzoneMagic separately)

lib/asan/asan_report.cc

990

Maybe dynamic-stack-buffer-overflow (for both left and right cases)?

[ygribov]

lib/asan/asan_report.cc

990

I think Max did underflow to match messages for ordinary stack.

[kcc]

lib/asan/asan_report.cc

990

Yea... I think the "underflow" was not very useful.
For this new thing I'd just go with a single dynamic-stack-buffer-overflow

[m.ostapenko]

Updated according to Konstantin's notes.

[kcc]

lib/Transforms/Instrumentation/AddressSanitizer.cpp

162

Please add a test for this flag in test/Instrumentation/AddressSanitizer/
to check asan-instrument-alloca=0, asan-instrument-alloca=1, and default setting
Similar to test/Instrumentation/AddressSanitizer/instrumentation-with-call-threshold.ll

541

This will not create a left red zone, right?
And even if it will (due to alignment) it will not poison it.

I would prefer to create both left and right redzones and [un]poison them inline with one 4-byte store for the left rz and one or two 4-byte stores for the right one.
Make sure to make the new size 0 mod 32

551

do you really need to always align this by 32?
Maybe use max(ClRealignStack, AllocaAlign)?

580

A cleaner way is to create a new AllocaInst, just like we do in another place in this file.
Then do eraseFromParent on the old one.

lib/asan/asan_fake_stack.cc

240 ↗

(On Diff #15842)

We probably don't need these at all if we inline the poisoning and unpoisoning.

[ygribov]

lib/Transforms/Instrumentation/AddressSanitizer.cpp

541

I think Max's idea was to create thricely left, right and partial. As for inlining, it would be a mess for partial redzone - it's size is unknown until runtime so we won't be able to use 4-byte stores and will have to use an ugly loop instead.

[kcc]

lib/Transforms/Instrumentation/AddressSanitizer.cpp

541

A loop? Come on, I am sure you can construct the appropriate 32-bit constant to poison the partial 32-byte zon just using arithmetic (masks and shifts)

[ygribov]

lib/Transforms/Instrumentation/AddressSanitizer.cpp

541

I wonder if this can be less ugly? We don't want to emit this mess in codegen, do we?

Tail = OldSize & 5; // Get length of 32-byte unaligned part
if (Tail >= 24) {

sh = 24;
shadow_word = 0;

} else if (Tail >= 16) {

sh = 16;
shadow_word = 0xcb000000;  // 0xcb is right magic

} else if (Tail >= 8) {

sh = 8;
shadow_word = 0xcbcb0000;  // 0xcb is right magic

} else {

sh = 0;
shadow_word = 0xcbcbcb00;  // 0xcb is right magic

}
Tail8 = Tail - sh;
shadow_byte = Tail8 == 8 ? 0 : Tail8 ? Tail8 : 0xcb;
shadow_word |= shadow_byte << sh;

[m.ostapenko]

lib/Transforms/Instrumentation/AddressSanitizer.cpp

541

Hm, perhaps something like this would be preferable:

padding = OldSize & (Align - 1) // get padding
if (padding) {
  shift = padding & ~7; // the number of bits we need to shift to access first chunk in shadow memory, containing nonzero bytes
  // Example:
  // padding = 21                       padding = 16
  // Shadow:  |00|00|05|cb|          Shadow:  |00|00|cb|cb|         
  //                ^                               ^
  //                |                               |
  // shift = 21 & ~7 = 16            shift = 16 & ~7 = 16
  val1 = 0xcbcbcbcb << (shift + 8);
  partialBits = padding & 7;
  if (!partialBits) partialBits = 0xcb;
  val2 = partialBits << shift;
  result = val1 | val2;
}

if (!partialBits) partialBits = 0xcb; looks ugly, but right now I don't see any convenient way to avoid it.

[m.ostapenko]

lib/Transforms/Instrumentation/AddressSanitizer.cpp

541

Oh, Align is 32, of course.

[kcc]

lib/Transforms/Instrumentation/AddressSanitizer.cpp

541

Yep, something along these lines. Cool.

Please make sure to have a test for all 32 values of padding.
You may use __asan_region_is_poisoned call in such test

Don't forget about little- vs big- endian

if (!partialBits) partialBits = 0xcb;

This should be fine actually, you can use SelectInst to avoid creating new BB

[m.ostapenko]

Updated patch. Major changes are:

1. (Un)poisoning is inline now.
2. Added test to check instrumentation (with/without alloca instrumentation, default behavior).
3. Add test to check that all 32 values of padding are handled correctly.
4. Big-endian is now "supported", but I unable to test it, sorry.

[kcc]

lib/Transforms/Instrumentation/AddressSanitizer.cpp

477

what is the middle rz?

481

add a comment describing the 3 redzones.
What is PartialRz, is it always non-empty?

I think you should store the pointers to the shadow here, not the pointers to the app memory.

485

space before =

564

no constants here, please.
Define kAsanAllocaLeftMagic/kAsanAllocaRightMagic at the top of the file

590

why long?
If it has to be 64-bit use uint64_t

655

no constants here.

661

instead of creating a new BB for partial RZ, I would do this:
make sure that PartialSize is never zero, i.e. instead of being in 0..31 it is in 1..32
This is better as we will not need to keep both pointers (PartialRz and RightRz) alive throughout the procedure.

test/Instrumentation/AddressSanitizer/instrument-dynamic-allocas.ll

7

use CHECK-NOALLOCA here

test/asan/TestCases/alloca_instruments_all_paddings.cc

12

Can you replace "str+index" with &str[0]?
This wya we will ensure that the valid memory is unpoisoned.

17

run this loop twice to ensure that we properly unpoison the stack

[m.ostapenko]

Updated according to last review, major changes are:

1. Removed redundant new BB creation.
2. Added small fixes for tests.
3. Defined new constants on top of the AddressSanitizer.cpp.

[m.ostapenko]

lib/Transforms/Instrumentation/AddressSanitizer.cpp

661

Yes, this is a good idea to avoid new BB creation. But we still need both PartialRz and RightRz, because in case of PartialSize == 32 PartialRz points the same address as RightRz, otherwise RightRz == PartialSize + 32, isn't it?

Or maybe I've misunderstood something?

[kcc]

lib/Transforms/Instrumentation/AddressSanitizer.cpp

661

But we still need both PartialRz and RightRz, because in case of PartialSize == 32 PartialRz points the same address as RightRz, otherwise RightRz == PartialSize + 32, isn't it?

There are two ways to implement this:

1. in case of PartialSize == 32 PartialRz points the same address as RightRz, otherwise RightRz == PartialSize + 32

In this case, we need to poison both PartialRz and RightRz and we need to keep this value in the register for the entire function.

2. PartialRz is always strictly before RightRz.

In this case we always unpoison RightRz and RightRz-32 and so we don't need to keep PartialRz around.

It's hard to tell which is better w/o measuring on a good benchmark, also there is a memory-vs-cpu tradeoff (larger redzones vs larger register pressure).
But the second way sounds slightly better to me.

[kcc]

lib/Transforms/Instrumentation/AddressSanitizer.cpp

109

static

536

Constant::getNullValue

555

This deserves a comment: what exactly you are computing.

579

These new functions are probably too big and should be placed outside of the class decl.

581

write a function-level comment with the expression you are computing

587

Constant::getNullValue

597

two lines should be enough here

[ygribov]

lib/Transforms/Instrumentation/AddressSanitizer.cpp

661

in case of PartialSize == 32 PartialRz points the same address as RightRz, otherwise RightRz == PartialSize + 32

In this case ... we need to keep this value in the register for the entire function

Not really, we can do the same as in your case 2 i.e. zero out RightRz - 32. Worst case (when PartialRz = RightRz) we'll do a redundant write.

As for benchmarking I'm not sure it matters that much - allocas are quite rare anyway.

[m.ostapenko]

Updated according to last review.

Now we don't keep PartialRzAddr until the end of function, we can just unpoison RightRzAddr and RightRzAddr - 32 with two stores into RightRzAddrShadow and RightRzAddrShadow - 4.
If PartialRzAddr == RightRzAddr we will perform one redundant store into user's memory shadow during unpoisoning, but perhaps this should be actually fine.

[kcc]

lib/Transforms/Instrumentation/AddressSanitizer.cpp

477

remove "partial" from comment

560

rephrase somehow, e.g.

... it would contain the value that we will use to poison the partial redzone

1817

please add a comment similar to the comment before handleDynamicAllocaCall
explaining what exactly and how you compute here, because this part is nto completely trivial.

1838

I tried hard, but I don't understand this :(
Try to avoid setOperand, instead create new Instruction objects when needed.

1915

two lines, please.
(You will like clang-format if you try it)

[m.ostapenko]

Updated. Added new comments, fixed code style.

[kcc]

LGTM
Thanks for working on this!
If you don't yet have commit access ask Yuri to commit (mentioning you as the author).

Next steps would be to enable the flag by default (we'll do our part of testing too).
And then it may be interesting to enable use-after-return for allocas.

[ygribov]

Next steps would be to enable the flag by default (we'll do our part of testing too).
And then it may be interesting to enable use-after-return for allocas.

And we also need to store metadata (probably just variable name) in redzone for user-friendlier reports.

[ygribov]

Done in r222519 and r222520.

[kcc]

In D6055#35, @ygribov wrote:

Next steps would be to enable the flag by default (we'll do our part of testing too).
And then it may be interesting to enable use-after-return for allocas.

And we also need to store metadata (probably just variable name) in redzone for user-friendlier reports.

Indeed so, the diagnostics could be improved.
Let's do it before enabling the feature by default

[kcc]

I've run the new feature on the chromium sources and it produced a compiler failure:

reduced test:
% cat a.c
int a;
int b;
int c;
void fn3(int *, int);
void fn1 () {

int d = b && c;
int e[a];
int f;
if (d)
  fn3 (&f, sizeof 0 * (&c - e));

}
% clang -fsanitize=address -mllvm -asan-instrument-allocas -O2 a.c
Instruction does not dominate all uses!

%54 = add i64 %53, 2147450880
%68 = sub i64 %54, 4

Instruction does not dominate all uses!

%35 = add i64 %34, 2147450880
%69 = inttoptr i64 %35 to i32*

Instruction does not dominate all uses!

%54 = add i64 %53, 2147450880
%71 = inttoptr i64 %54 to i32*

fatal error: error in backend: Broken function found, compilation aborted!
clang-3.6: error: clang frontend command failed with exit code 70 (use -v to see invocation)
clang version 3.6.0 (trunk 222567)
Target: x86_64-unknown-linux-gnu
Thread model: posix
clang-3.6: note: diagnostic msg: PLEASE submit a bug report to http://llvm.org/bugs/ and include the crash backtrace, preprocessed source, and associated run script.
clang-3.6: note: diagnostic msg:

---

PLEASE ATTACH THE FOLLOWING FILES TO THE BUG REPORT:
Preprocessed source(s) and associated run script(s) are located at:
clang-3.6: note: diagnostic msg: /tmp/a-2b96e4.c
clang-3.6: note: diagnostic msg: /tmp/a-2b96e4.sh
clang-3.6: note: diagnostic msg:

---

[kcc]

Interesting.
The dynamic alloca in this case is moved to a basic block outside of main path and hence it does not dominate
all exits. So, we can not unpoison it at the RET statements, instead we should do it in the end of the alloca's scope.
This is starting to resemble use-after-scope... Alexey, any comments?

[ygribov]

So we basically need to find all blocks dominated by alloca, then all exits from those to non-dominated blocks and then insert unpoison calls prior to these exits?

[ygribov]

Or maybe use dominance frontiers to make whole process more efficient: insert unpoisons at those predecessors of blocks from alloca dominance frontier which are dominated by alloca.

[kcc]

I am afraid this is not that simple.
It is legal to call alloca manually inside an if-statement and then use it until the function exit.
/me pondering...
(And will be OOO most of this week, don't expect prompt replies until next Mon)

[ygribov]

Right. Frankly I'm mostly interested in VLAs so worst case we can simply remove such pathological cases. I think they can be detected by checking if alloca is argument of some phi?

[ygribov]

I think they can be detected by checking if alloca is argument of some phi?

Hm, not really - alloca result could also escape.

[kcc]

We may start from checking that alloca dominates all exits (the most common case, probably).

[m.ostapenko]

Handling nontrivial cases may be quite tricky. Perhaps we can implement something like linked list of "bad " allocas, storing the address and size of next/previous alloca in the left redzone and marking the last/first one with some magic value. Then, before each ret instruction, we can iterate over this list and unpoison these allocas.

[ygribov]

Or we could just memset shadow for dynamic part of stack to 0. This wouldn't work with use-after-return though.

[kcc]

I see you've committed r222991 which checks that alloca dominates the exits.
Let's polish this thing first and enable it by default, then we may return to more complicated cases.

[ygribov]

Actually exit domination wouldn't save the day. E.g.

void f() {
  char *p;
  ...
  do {
    p = alloca(100);
    g(p);
  } while(whatever);
  ...
}

[kcc]

Fun!

lib/Transforms/Instrumentation/AddressSanitizer.cpp

 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/MDBuilder.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/Type.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/DataTypes.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/Endian.h"
+#include "llvm/Support/SwapByteOrder.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Utils/ASanStackFrameLayout.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/Cloning.h"
 #include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Transforms/Utils/ModuleUtils.h"
 #include <algorithm>
 #include <string>

 
 #ifndef NDEBUG
 static const int kAsanStackAfterReturnMagic = 0xf5;
 #endif
 
 // Accesses sizes are powers of two: 1, 2, 4, 8, 16.
 static const size_t kNumberOfAccessSizes = 5;
 
+static const unsigned kAllocaRzSize = 32;
+static const unsigned kAsanAllocaLeftMagic = 0xcacacacaU;
+static const unsigned kAsanAllocaRightMagic = 0xcbcbcbcbU;
+static const unsigned kAsanAllocaPartialVal1 = 0xcbcbcb00U;
+static const unsigned kAsanAllocaPartialVal2 = 0x000000cbU;
+
 // Command-line flags.
 
 // This flag may need to be replaced with -f[no-]asan-reads.
 static cl::opt<bool> ClInstrumentReads("asan-instrument-reads",
        cl::desc("instrument read instructions"), cl::Hidden, cl::init(true));
 static cl::opt<bool> ClInstrumentWrites("asan-instrument-writes",
        cl::desc("instrument write instructions"), cl::Hidden, cl::init(true));
 static cl::opt<bool> ClInstrumentAtomics("asan-instrument-atomics",
"asan-instrumentation-with-call-threshold",
        cl::desc("If the function being instrumented contains more than "
                 "this number of memory accesses, use callbacks instead of "
                 "inline checks (-1 means never use callbacks)."),
        cl::Hidden, cl::init(7000));
 static cl::opt<std::string> ClMemoryAccessCallbackPrefix(
        "asan-memory-access-callback-prefix",
        cl::desc("Prefix for memory access callbacks"), cl::Hidden,
        cl::init("__asan_"));
+static cl::opt<bool> ClInstrumentAllocas("asan-instrument-allocas",
+       cl::desc("instrument dynamic allocas"), cl::Hidden, cl::init(false));
 
 // This is an experimental feature that will allow to choose between
 // instrumented and non-instrumented code at link-time.
 // If this option is on, just before instrumenting a function we create its
 // clone; if the function is not changed by asan the clone is deleted.
 // If we end up with a clone, we put the instrumented function into a section
 // called "ASAN" and the uninstrumented function into a section called "NOASAN".
 //
struct FunctionStackPoisoner : public InstVisitor<FunctionStackPoisoner> {
   struct AllocaPoisonCall {
     IntrinsicInst *InsBefore;
     AllocaInst *AI;
     uint64_t Size;
     bool DoPoison;
   };
   SmallVector<AllocaPoisonCall, 8> AllocaPoisonCallVec;
 
+  // Stores left and right redzone shadow addresses for dynamic alloca
+  // and pointer to alloca instruction itself.
+  // LeftRzAddr is a shadow address for alloca left redzone.
+  // RightRzAddr is a shadow address for alloca right redzone.
+  struct DynamicAllocaCall {
+    AllocaInst *AI;
+    Value *LeftRzAddr;
+    Value *RightRzAddr;
+    explicit DynamicAllocaCall(AllocaInst *AI,
+                      Value *LeftRzAddr = nullptr,
+                      Value *RightRzAddr = nullptr)
+      : AI(AI), LeftRzAddr(LeftRzAddr), RightRzAddr(RightRzAddr)
+    {}
+  };
+  SmallVector<DynamicAllocaCall, 1> DynamicAllocaVec;
+
   // Maps Value to an AllocaInst from which the Value is originated.
   typedef DenseMap<Value*, AllocaInst*> AllocaForValueMapTy;
   AllocaForValueMapTy AllocaForValue;
 
   FunctionStackPoisoner(Function &F, AddressSanitizer &ASan)
       : F(F), ASan(ASan), DIB(*F.getParent()), C(ASan.C),
         IntptrTy(ASan.IntptrTy), IntptrPtrTy(PointerType::get(IntptrTy, 0)),
         Mapping(ASan.Mapping),
         StackAlignment(1 << Mapping.Scale) {}
 
   bool runOnFunction() {
     if (!ClStack) return false;
     // Collect alloca, ret, lifetime instructions etc.
     for (BasicBlock *BB : depth_first(&F.getEntryBlock()))
       visit(*BB);
 
-    if (AllocaVec.empty()) return false;
+    if (AllocaVec.empty() && DynamicAllocaVec.empty()) return false;
 
     initializeCallbacks(*F.getParent());
 
     poisonStack();
 
     if (ClDebugStack) {
       DEBUG(dbgs() << F);
     }
     return true;
   }
 
-  // Finds all static Alloca instructions and puts
+  // Finds all Alloca instructions and puts
   // poisoned red zones around all of them.
   // Then unpoison everything back before the function returns.
   void poisonStack();
 
   // ----------------------- Visitors.
   /// \brief Collect all Ret instructions.
   void visitReturnInst(ReturnInst &RI) {
     RetVec.push_back(&RI);
   }
 
+  // Unpoison dynamic allocas redzones.
+  void unpoisonDynamicAlloca(DynamicAllocaCall &AllocaCall) {
+    for (auto Ret : RetVec) {
+      IRBuilder<> IRBRet(Ret);
+      PointerType *Int32PtrTy = PointerType::getUnqual(IRBRet.getInt32Ty());
+      Value *Zero = Constant::getNullValue(IRBRet.getInt32Ty());
+      Value *PartialRzAddr = IRBRet.CreateSub(AllocaCall.RightRzAddr,
+                                              ConstantInt::get(IntptrTy, 4));
+      IRBRet.CreateStore(Zero, IRBRet.CreateIntToPtr(AllocaCall.LeftRzAddr,
+                                                     Int32PtrTy));
+      IRBRet.CreateStore(Zero, IRBRet.CreateIntToPtr(PartialRzAddr,
+                                                     Int32PtrTy));
+      IRBRet.CreateStore(Zero, IRBRet.CreateIntToPtr(AllocaCall.RightRzAddr,
+                                                     Int32PtrTy));
+    }
+  }
+
+  // Right shift for BigEndian and left shift for LittleEndian.
+  Value *shiftAllocaMagic(Value *Val, IRBuilder<> &IRB, Value *Shift) {
+    return ASan.DL->isLittleEndian() ? IRB.CreateShl(Val, Shift)
+                                     : IRB.CreateLShr(Val, Shift);
+  }
+
+  // Compute PartialRzMagic for dynamic alloca call. Since we don't know the
+  // size of requested memory until runtime, we should compute it dynamically.
+  // If PartialSize is 0, PartialRzMagic would contain kAsanAllocaRightMagic,
+  // otherwise it would contain the value that we will use to poison the
+  // partial redzone for alloca call.
+  Value *computePartialRzMagic(Value *PartialSize, IRBuilder<> &IRB);
+
+  // Deploy and poison redzones around dynamic alloca call. To do this, we
+  // should replace this call with another one with changed parameters and
+  // replace all its uses with new address, so
+  //   addr = alloca type, old_size, align
+  // is replaced by
+  //   new_size = (old_size + additional_size) * sizeof(type)
+  //   tmp = alloca i8, new_size, max(align, 32)
+  //   addr = tmp + 32 (first 32 bytes are for the left redzone).
+  // Additional_size is added to make new memory allocation contain not only
+  // requested memory, but also left, partial and right redzones.
+  // After that, we should poison redzones:
+  // (1) Left redzone with kAsanAllocaLeftMagic.
+  // (2) Partial redzone with the value, computed in runtime by
+  //     computePartialRzMagic function.
+  // (3) Right redzone with kAsanAllocaRightMagic.
+  void handleDynamicAllocaCall(DynamicAllocaCall &AllocaCall);
+
   /// \brief Collect Alloca instructions we want (and can) handle.
   void visitAllocaInst(AllocaInst &AI) {
     if (!isInterestingAlloca(AI)) return;
 
     StackAlignment = std::max(StackAlignment, AI.getAlignment());
+    if (isDynamicAlloca(AI))
+      DynamicAllocaVec.push_back(DynamicAllocaCall(&AI));
+    else
       AllocaVec.push_back(&AI);
   }
 
   /// \brief Collect lifetime intrinsic calls to check for use-after-scope
   /// errors.
   void visitIntrinsicInst(IntrinsicInst &II) {
     if (!ClCheckLifetime) return;
     Intrinsic::ID ID = II.getIntrinsicID();
     if (ID != Intrinsic::lifetime_start &&
         ID != Intrinsic::lifetime_end)
       return;
     // Found lifetime intrinsic, add ASan instrumentation if necessary.
     ConstantInt *Size = dyn_cast<ConstantInt>(II.getArgOperand(0));
     // If size argument is undefined, don't do anything.
     if (Size->isMinusOne()) return;
     // Check that size doesn't saturate uint64_t and can
     // be stored in IntptrTy.
     const uint64_t SizeValue = Size->getValue().getLimitedValue();
     if (SizeValue == ~0ULL ||
         !ConstantInt::isValueValidForType(IntptrTy, SizeValue))
       return;
     // Find alloca instruction that corresponds to llvm.lifetime argument.
     AllocaInst *AI = findAllocaForValue(II.getArgOperand(1));
     if (!AI) return;
     bool DoPoison = (ID == Intrinsic::lifetime_end);
     AllocaPoisonCall APC = {&II, AI, SizeValue, DoPoison};
     AllocaPoisonCallVec.push_back(APC);
   }
 
   // ---------------------- Helpers.
   void initializeCallbacks(Module &M);
 
+  bool isDynamicAlloca(AllocaInst &AI) const {
+    return AI.isArrayAllocation() || !AI.isStaticAlloca();
+  }
+
   // Check if we want (and can) handle this alloca.
   bool isInterestingAlloca(AllocaInst &AI) const {
-    return (!AI.isArrayAllocation() && AI.isStaticAlloca() &&
-            AI.getAllocatedType()->isSized() &&
+    return (AI.getAllocatedType()->isSized() &&
             // alloca() may be called with 0 size, ignore it.
             getAllocaSizeInBytes(&AI) > 0);
   }
 
   uint64_t getAllocaSizeInBytes(AllocaInst *AI) const {
     Type *Ty = AI->getAllocatedType();
     uint64_t SizeInBytes = ASan.DL->getTypeAllocSize(Ty);
     return SizeInBytes;

 char AddressSanitizer::ID = 0;
 INITIALIZE_PASS(AddressSanitizer, "asan",
     "AddressSanitizer: detects use-after-free and out-of-bounds bugs.",
     false, false)
 FunctionPass *llvm::createAddressSanitizerFunctionPass() {
   return new AddressSanitizer();
 }
 
 char AddressSanitizerModule::ID = 0;
 INITIALIZE_PASS(AddressSanitizerModule, "asan-module",
     "AddressSanitizer: detects use-after-free and out-of-bounds bugs."
     "ModulePass", false, false)
 ModulePass *llvm::createAddressSanitizerModulePass() {
   return new AddressSanitizerModule();
 }
 
 static size_t TypeSizeToSizeIndex(uint32_t TypeSize) {
   size_t Res = countTrailingZeros(TypeSize / 8);
   assert(Res < kNumberOfAccessSizes);
   return Res;
 }
 
 // \brief Create a constant for Str so that we can pass it to the run-time lib.

 static DebugLoc getFunctionEntryDebugLocation(Function &F) {
   for (const auto &Inst : F.getEntryBlock())
     if (!isa<AllocaInst>(Inst))
       return Inst.getDebugLoc();
   return DebugLoc();
 }
 
 void FunctionStackPoisoner::poisonStack() {
+  assert(AllocaVec.size() > 0 || DynamicAllocaVec.size() > 0);
+
+  if (ClInstrumentAllocas)
+    // Handle dynamic allocas.
+    for (auto &AllocaCall : DynamicAllocaVec)
+      handleDynamicAllocaCall(AllocaCall);
+
+  if (AllocaVec.size() == 0) return;
+
   int StackMallocIdx = -1;
   DebugLoc EntryDebugLocation = getFunctionEntryDebugLocation(F);
 
-  assert(AllocaVec.size() > 0);
   Instruction *InsBefore = AllocaVec[0];
   IRBuilder<> IRB(InsBefore);
   IRB.SetCurrentDebugLocation(EntryDebugLocation);
 
   SmallVector<ASanStackVariableDescription, 16> SVD;
   SVD.reserve(AllocaVec.size());
   for (AllocaInst *AI : AllocaVec) {
     ASanStackVariableDescription D = { AI->getName().data(),
if (DoStackMalloc) {
       // unpoison whole stack frame now.
       assert(LocalStackBase == OrigStackBase);
       poisonAlloca(LocalStackBase, LocalStackSize, IRBRet, false);
     } else {
       poisonRedZones(L.ShadowBytes, IRBRet, ShadowBase, false);
     }
   }
 
+  if (ClInstrumentAllocas)
+    // Unpoison dynamic allocas.
+    for (auto &AllocaCall : DynamicAllocaVec)
+      unpoisonDynamicAlloca(AllocaCall);
+
   // We are done. Remove the old unused alloca instructions.
   for (auto AI : AllocaVec)
     AI->eraseFromParent();
 }
 
 void FunctionStackPoisoner::poisonAlloca(Value *V, uint64_t Size,
                                          IRBuilder<> &IRB, bool DoPoison) {
   // For now just insert the call to ASan runtime.
for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
         return nullptr;
       Res = IncValueAI;
     }
   }
   if (Res)
     AllocaForValue[V] = Res;
   return Res;
 }
+
+// Compute PartialRzMagic for dynamic alloca call. PartialRzMagic is
+// constructed from two separate 32-bit numbers: PartialRzMagic = Val1 | Val2.
+// (1) Val1 is resposible for forming base value for PartialRzMagic, containing
+//     only 00 for fully addressable and 0xcb for fully poisoned bytes for each
+//     8-byte chunk of user memory respectively.
+// (2) Val2 forms the value for marking first poisoned byte in shadow memory
+//     with appropriate value (0x01 - 0x07 or 0xcb if Padding % 8 == 0).
+
+// Shift = Padding & ~7; // the number of bits we need to shift to access first
+//                          chunk in shadow memory, containing nonzero bytes.
+// Example:
+// Padding = 21                       Padding = 16
+// Shadow:  |00|00|05|cb|          Shadow:  |00|00|cb|cb|
+//                ^                               ^
+//                |                               |
+// Shift = 21 & ~7 = 16            Shift = 16 & ~7 = 16
+//
+// Val1 = 0xcbcbcbcb << Shift;
+// PartialBits = Padding ? Padding & 7 : 0xcb;
+// Val2 = PartialBits << Shift;
+// Result = Val1 | Val2;
+Value *FunctionStackPoisoner::computePartialRzMagic(Value *PartialSize,
+                                                    IRBuilder<> &IRB) {
+  PartialSize = IRB.CreateIntCast(PartialSize, IRB.getInt32Ty(), false);
+  Value *Shift = IRB.CreateAnd(PartialSize, IRB.getInt32(~7));
+  unsigned Val1Int = kAsanAllocaPartialVal1;
+  unsigned Val2Int = kAsanAllocaPartialVal2;
+  if (!ASan.DL->isLittleEndian()) {
+    Val1Int = sys::getSwappedBytes(Val1Int);
+    Val2Int = sys::getSwappedBytes(Val2Int);
+  }
+  Value *Val1 = shiftAllocaMagic(IRB.getInt32(Val1Int), IRB, Shift);
+  Value *PartialBits = IRB.CreateAnd(PartialSize, IRB.getInt32(7));
+  // For BigEndian get 0x000000YZ -> 0xYZ000000.
+  if (ASan.DL->isBigEndian())
+    PartialBits = IRB.CreateShl(PartialBits, IRB.getInt32(24));
+  Value *Val2 = IRB.getInt32(Val2Int);
+  Value *Cond =
+      IRB.CreateICmpNE(PartialBits, Constant::getNullValue(IRB.getInt32Ty()));
+  Val2 = IRB.CreateSelect(Cond, shiftAllocaMagic(PartialBits, IRB, Shift),
+                          shiftAllocaMagic(Val2, IRB, Shift));
+  return IRB.CreateOr(Val1, Val2);
+}
+
+void FunctionStackPoisoner::handleDynamicAllocaCall(
+    DynamicAllocaCall &AllocaCall) {
+  AllocaInst *AI = AllocaCall.AI;
+  IRBuilder<> IRB(AI);
+
+  PointerType *Int32PtrTy = PointerType::getUnqual(IRB.getInt32Ty());
+  const unsigned Align = std::max(kAllocaRzSize, AI->getAlignment());
+  const uint64_t AllocaRedzoneMask = kAllocaRzSize - 1;
+
+  Value *Zero = Constant::getNullValue(IntptrTy);
+  Value *AllocaRzSize = ConstantInt::get(IntptrTy, kAllocaRzSize);
+  Value *AllocaRzMask = ConstantInt::get(IntptrTy, AllocaRedzoneMask);
+  Value *NotAllocaRzMask = ConstantInt::get(IntptrTy, ~AllocaRedzoneMask);
+
+  // Since we need to extend alloca with additional memory to locate
+  // redzones, and OldSize is number of allocated blocks with
+  // ElementSize size, get allocated memory size in bytes by
+  // OldSize * ElementSize.
+  unsigned ElementSize = ASan.DL->getTypeAllocSize(AI->getAllocatedType());
+  Value *OldSize = IRB.CreateMul(AI->getArraySize(),
+                                 ConstantInt::get(IntptrTy, ElementSize));
+
+  // PartialSize = OldSize % 32
+  Value *PartialSize = IRB.CreateAnd(OldSize, AllocaRzMask);
+
+  // Misalign = kAllocaRzSize - PartialSize;
+  Value *Misalign = IRB.CreateSub(AllocaRzSize, PartialSize);
+
+  // PartialPadding = Misalign != kAllocaRzSize ? Misalign : 0;
+  Value *Cond = IRB.CreateICmpNE(Misalign, AllocaRzSize);
+  Value *PartialPadding = IRB.CreateSelect(Cond, Misalign, Zero);
+
+  // AdditionalChunkSize = Align + PartialPadding + kAllocaRzSize
+  // Align is added to locate left redzone, PartialPadding for possible
+  // partial redzone and kAllocaRzSize for right redzone respectively.
+  Value *AdditionalChunkSize = IRB.CreateAdd(
+      ConstantInt::get(IntptrTy, Align + kAllocaRzSize), PartialPadding);
+
+  Value *NewSize = IRB.CreateAdd(OldSize, AdditionalChunkSize);
+
+  // Insert new alloca with new NewSize and Align params.
+  AllocaInst *NewAlloca = IRB.CreateAlloca(IRB.getInt8Ty(), NewSize);
+  NewAlloca->setAlignment(Align);
+
+  // NewAddress = Address + Align
+  Value *NewAddress = IRB.CreateAdd(IRB.CreatePtrToInt(NewAlloca, IntptrTy),
+                                    ConstantInt::get(IntptrTy, Align));
+
+  Value *NewAddressPtr = IRB.CreateIntToPtr(NewAddress, AI->getType());
+
+  // LeftRzAddress = NewAddress - kAllocaRzSize
+  Value *LeftRzAddress = IRB.CreateSub(NewAddress, AllocaRzSize);
+
+  // Poisoning left redzone.
+  AllocaCall.LeftRzAddr = ASan.memToShadow(LeftRzAddress, IRB);
+  IRB.CreateStore(ConstantInt::get(IRB.getInt32Ty(), kAsanAllocaLeftMagic),
+                  IRB.CreateIntToPtr(AllocaCall.LeftRzAddr, Int32PtrTy));
+
+  // PartialRzAligned = PartialRzAddr & ~AllocaRzMask
+  Value *PartialRzAddr = IRB.CreateAdd(NewAddress, OldSize);
+  Value *PartialRzAligned = IRB.CreateAnd(PartialRzAddr, NotAllocaRzMask);
+
+  // Poisoning partial redzone.
+  Value *PartialRzMagic = computePartialRzMagic(PartialSize, IRB);
+  Value *PartialRzShadowAddr = ASan.memToShadow(PartialRzAligned, IRB);
+  IRB.CreateStore(PartialRzMagic,
+                  IRB.CreateIntToPtr(PartialRzShadowAddr, Int32PtrTy));
+
+  // RightRzAddress
+  //   =  (PartialRzAddr + AllocaRzMask) & ~AllocaRzMask
+  Value *RightRzAddress = IRB.CreateAnd(
+      IRB.CreateAdd(PartialRzAddr, AllocaRzMask), NotAllocaRzMask);
+
+  // Poisoning right redzone.
+  AllocaCall.RightRzAddr = ASan.memToShadow(RightRzAddress, IRB);
+  IRB.CreateStore(ConstantInt::get(IRB.getInt32Ty(), kAsanAllocaRightMagic),
+                  IRB.CreateIntToPtr(AllocaCall.RightRzAddr, Int32PtrTy));
+
+  // Replace all uses of AddessReturnedByAlloca with NewAddress.
+  AI->replaceAllUsesWith(NewAddressPtr);
+
+  // We are done. Erase old alloca and store left, partial and right redzones
+  // shadow addresses for future unpoisoning.
+  AI->eraseFromParent();
+}

lib/asan/asan_internal.h

 const int kAsanInitializationOrderMagic = 0xf6;
 const int kAsanUserPoisonedMemoryMagic = 0xf7;
 const int kAsanContiguousContainerOOBMagic = 0xfc;
 const int kAsanStackUseAfterScopeMagic = 0xf8;
 const int kAsanGlobalRedzoneMagic = 0xf9;
 const int kAsanInternalHeapMagic = 0xfe;
 const int kAsanArrayCookieMagic = 0xac;
 const int kAsanIntraObjectRedzone = 0xbb;
+const int kAsanAllocaLeftMagic = 0xca;
+const int kAsanAllocaRightMagic = 0xcb;
 
 static const uptr kCurrentStackFrameMagic = 0x41B58AB3;
 static const uptr kRetiredStackFrameMagic = 0x45E0360E;
 
 }  // namespace __asan
 
 #endif  // ASAN_INTERNAL_H

lib/asan/asan_report.cc

switch (byte) {
       case kAsanStackPartialRedzoneMagic:
         return Red();
       case kAsanStackAfterReturnMagic:
         return Magenta();
       case kAsanInitializationOrderMagic:
         return Cyan();
       case kAsanUserPoisonedMemoryMagic:
       case kAsanContiguousContainerOOBMagic:
+      case kAsanAllocaLeftMagic:
+      case kAsanAllocaRightMagic:
         return Blue();
       case kAsanStackUseAfterScopeMagic:
         return Magenta();
       case kAsanGlobalRedzoneMagic:
         return Red();
       case kAsanInternalHeapMagic:
         return Yellow();
       case kAsanIntraObjectRedzone:
PrintShadowByte(str, "  Poisoned by user:        ",
                   kAsanUserPoisonedMemoryMagic);
   PrintShadowByte(str, "  Container overflow:      ",
                   kAsanContiguousContainerOOBMagic);
   PrintShadowByte(str, "  Array cookie:            ",
                   kAsanArrayCookieMagic);
   PrintShadowByte(str, "  Intra object redzone:    ",
                   kAsanIntraObjectRedzone);
   PrintShadowByte(str, "  ASan internal:           ", kAsanInternalHeapMagic);
+  PrintShadowByte(str, "  Left alloca redzone:     ", kAsanAllocaLeftMagic);
+  PrintShadowByte(str, "  Right alloca redzone:    ", kAsanAllocaRightMagic);
 }
 
 void MaybeDumpInstructionBytes(uptr pc) {
   if (!flags()->dump_instruction_bytes || (pc < GetPageSizeCached()))
     return;
   InternalScopedString str(1024);
   str.append("First 16 instruction bytes at pc: ");
   if (IsAccessibleMemoryRange(pc, 16)) {
switch (*shadow_addr) {
         bug_descr = "stack-use-after-scope";
         break;
       case kAsanGlobalRedzoneMagic:
         bug_descr = "global-buffer-overflow";
         break;
       case kAsanIntraObjectRedzone:
         bug_descr = "intra-object-overflow";
         break;
+      case kAsanAllocaLeftMagic:
+      case kAsanAllocaRightMagic:
+        bug_descr = "dynamic-stack-buffer-overflow";
+        break;
     }
   }
 
   ReportData report = { pc, sp, bp, addr, (bool)is_write, access_size,
                         bug_descr };
   ScopedInErrorReport in_report(&report);
 
   Decorator d;

test/Instrumentation/AddressSanitizer/instrument-dynamic-allocas.ll

+; Test asan internal compiler flags:
+;   -asan-instrument-allocas=1
+
+; RUN: opt < %s -asan -asan-module -asan-instrument-allocas=1 -S | FileCheck %s --check-prefix=CHECK-ALLOCA
+; RUN: opt < %s -asan -asan-module -asan-instrument-allocas=0 -S | FileCheck %s --check-prefix=CHECK-NOALLOCA
+; RUN: opt < %s -asan -asan-module -S | FileCheck %s --check-prefix=CHECK-NOALLOCA
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
+target triple = "x86_64-unknown-linux-gnu"
+
+define void @foo(i32 %len) sanitize_address {
+entry:
+; CHECK-ALLOCA: store i32 -892679478
+; CHECK-ALLOCA: store i32 -875836469
+; CHECK-NOALLOCA-NOT: store i32 -892679478
+; CHECK-NOALLOCA-NOT: store i32 -875836469
+  %0 = alloca i32, align 4
+  %1 = alloca i8*
+  store i32 %len, i32* %0, align 4
+  %2 = load i32* %0, align 4
+  %3 = zext i32 %2 to i64
+  %4 = alloca i8, i64 %3, align 32
+  ret void
+}
+
+

test/asan/TestCases/alloca_big_alignment.cc

+// RUN: %clangxx_asan -O0 -mllvm -asan-instrument-allocas %s -o %t
+// RUN: not %run %t 2>&1 | FileCheck %s
+//
+
+#include <assert.h>
+
+__attribute__((noinline)) void foo(int index, int len) {
+  volatile char str[len] __attribute__((aligned(128)));
+  assert(!(reinterpret_cast<long>(str) & 127L));
+  str[index] = '1'; // BOOM
+// CHECK: ERROR: AddressSanitizer: dynamic-stack-buffer-overflow on address [[ADDR:0x[0-9a-f]+]]
+// CHECK: WRITE of size 1 at [[ADDR]] thread T0
+}
+
+int main(int argc, char **argv) {
+  foo(10, 10);
+  return 0;
+}

test/asan/TestCases/alloca_detect_custom_size_.cc

+// RUN: %clangxx_asan -O0 -mllvm -asan-instrument-allocas %s -o %t
+// RUN: not %run %t 2>&1 | FileCheck %s
+//
+
+#include <assert.h>
+
+struct A {
+  char a[3];
+  int b[3];
+};
+
+__attribute__((noinline)) void foo(int index, int len) {
+  volatile struct A str[len] __attribute__((aligned(32)));
+  assert(!(reinterpret_cast<long>(str) & 31L));
+  str[index].a[0] = '1'; // BOOM
+// CHECK: ERROR: AddressSanitizer: dynamic-stack-buffer-overflow on address [[ADDR:0x[0-9a-f]+]]
+// CHECK: WRITE of size 1 at [[ADDR]] thread T0
+}
+
+int main(int argc, char **argv) {
+  foo(10, 10);
+  return 0;
+}

test/asan/TestCases/alloca_instruments_all_paddings.cc

+// RUN: %clangxx_asan -O0 -mllvm -asan-instrument-allocas %s -o %t
+// RUN: %run %t 2>&1
+//
+
+#include "sanitizer/asan_interface.h"
+#include <assert.h>
+
+__attribute__((noinline)) void foo(int index, int len) {
+  volatile char str[len] __attribute__((aligned(32)));
+  assert(!(reinterpret_cast<long>(str) & 31L));
+  char *q = (char *)__asan_region_is_poisoned((char *)str, 64);
+  assert(q && ((q - str) == index));
+}
+
+int main(int argc, char **argv) {
+  for (int i = 1; i < 33; ++i)
+    foo(i, i);
+
+  for (int i = 1; i < 33; ++i)
+    foo(i, i);
+
+  return 0;
+}

test/asan/TestCases/alloca_overflow_partial.cc

+// RUN: %clangxx_asan -O0 -mllvm -asan-instrument-allocas %s -o %t
+// RUN: not %run %t 2>&1 | FileCheck %s
+//
+
+#include <assert.h>
+
+__attribute__((noinline)) void foo(int index, int len) {
+  volatile char str[len] __attribute__((aligned(32)));
+  assert(!(reinterpret_cast<long>(str) & 31L));
+  str[index] = '1'; // BOOM
+// CHECK: ERROR: AddressSanitizer: dynamic-stack-buffer-overflow on address [[ADDR:0x[0-9a-f]+]]
+// CHECK: WRITE of size 1 at [[ADDR]] thread T0
+}
+
+int main(int argc, char **argv) {
+  foo(10, 10);
+  return 0;
+}

test/asan/TestCases/alloca_overflow_right.cc

+// RUN: %clangxx_asan -O0 -mllvm -asan-instrument-allocas %s -o %t
+// RUN: not %run %t 2>&1 | FileCheck %s
+//
+
+#include <assert.h>
+
+__attribute__((noinline)) void foo(int index, int len) {
+  volatile char str[len] __attribute__((aligned(32)));
+  assert(!(reinterpret_cast<long>(str) & 31L));
+  str[index] = '1'; // BOOM
+// CHECK: ERROR: AddressSanitizer: dynamic-stack-buffer-overflow on address [[ADDR:0x[0-9a-f]+]]
+// CHECK: WRITE of size 1 at [[ADDR]] thread T0
+}
+
+int main(int argc, char **argv) {
+  foo(33, 10);
+  return 0;
+}

test/asan/TestCases/alloca_safe_access.cc

+// RUN: %clangxx_asan -O0 -mllvm -asan-instrument-allocas %s -o %t
+// RUN: %run %t 2>&1
+//
+
+#include <assert.h>
+
+__attribute__((noinline)) void foo(int index, int len) {
+  volatile char str[len] __attribute__((aligned(32)));
+  assert(!(reinterpret_cast<long>(str) & 31L));
+  str[index] = '1';
+}
+
+int main(int argc, char **argv) {
+  foo(4, 5);
+  foo(39, 40);
+  return 0;
+}

test/asan/TestCases/alloca_underflow_left.cc

+// RUN: %clangxx_asan -O0 -mllvm -asan-instrument-allocas %s -o %t
+// RUN: not %run %t 2>&1 | FileCheck %s
+//
+
+#include <assert.h>
+
+__attribute__((noinline)) void foo(int index, int len) {
+  volatile char str[len] __attribute__((aligned(32)));
+  assert(!(reinterpret_cast<long>(str) & 31L));
+  str[index] = '1'; // BOOM
+// CHECK: ERROR: AddressSanitizer: dynamic-stack-buffer-overflow on address [[ADDR:0x[0-9a-f]+]]
+// CHECK: WRITE of size 1 at [[ADDR]] thread T0
+}
+
+int main(int argc, char **argv) {
+  foo(-1, 10);
+  return 0;
+}