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

681

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

157

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

536

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

546

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

575

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

536

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

536

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

536

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

536

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

536

Oh, Align is 32, of course.

[kcc]

lib/Transforms/Instrumentation/AddressSanitizer.cpp

536

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

472

what is the middle rz?

476

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.

480

space before =

559

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

585

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

650

no constants here.

656

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

6

use CHECK-NOALLOCA here

test/asan/TestCases/alloca_instruments_all_paddings.cc

11

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

16

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

656

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

656

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

108

static

531

Constant::getNullValue

550

This deserves a comment: what exactly you are computing.

574

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

576

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

582

Constant::getNullValue

592

two lines should be enough here

[ygribov]

lib/Transforms/Instrumentation/AddressSanitizer.cpp

656

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

472

remove "partial" from comment

555

rephrase somehow, e.g.

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

1912

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.

1933

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

2010

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;
 
+const unsigned kAllocaRzSize = 32;
+
 // 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, middle and right redzone shadow addresses for dynamic alloca.
+  struct DynamicAllocaCall {
+    AllocaInst *AI;
+    Value *LeftRzAddr;
+    Value *PartialRzAddr;
+    Value *RightRzAddr;
+    explicit DynamicAllocaCall(AllocaInst *AI,
+                      Value *LeftRzAddr = nullptr,
+                      Value *PartialRzAddr= nullptr,
+                      Value *RightRzAddr = nullptr)
+      : AI(AI), LeftRzAddr(LeftRzAddr), PartialRzAddr(PartialRzAddr),
+        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
   // 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);
   }
 
+  // (Un)poison memory starting on Address with value Val.
+  void poisonAddrForAlloca(Value *Address, IRBuilder<> &IRB,
+                           const unsigned Val) {
+    PointerType *Int32PtrTy = PointerType::getUnqual(IRB.getInt32Ty());
+    Value *ShadowBase = IRB.CreateIntToPtr(ASan.memToShadow(Address, IRB),
+                                           Int32PtrTy);
+    IRB.CreateStore(ConstantInt::get(IRB.getInt32Ty(), Val), ShadowBase);
+  }
+
+  // Inserts __asan_unpoison_alloca for given nonstatic alloca before each ret
+  // instruction.
+  void unpoisonDynamicAlloca(DynamicAllocaCall &AllocaCall,
+                             IRBuilder<> IRBRet) {
+    poisonAddrForAlloca(AllocaCall.LeftRzAddr, IRBRet, 0);
+    poisonAddrForAlloca(AllocaCall.PartialRzAddr, IRBRet, 0);
+    poisonAddrForAlloca(AllocaCall.RightRzAddr, IRBRet, 0);
+  }
+
+  // Right shift for BigEndian and left shift for LittleEndian.
+  inline Instruction *shiftAllocaMagic(Value *Val, IRBuilder<> &IRB,
+                                       Value *Shift) {
+    if (ASan.DL->isLittleEndian())
+      return cast<Instruction>(IRB.CreateShl(Val, Shift));
+    else
+      return cast<Instruction>(IRB.CreateLShr(Val, Shift));
+  }
+
+  // Calculate PartialRzMagic.
+  Value *calculatePartialRzMagic(Value *PartialSize, IRBuilder<> &IRB) {
+    PartialSize = IRB.CreateIntCast(PartialSize, IRB.getInt32Ty(),
+                                    false);
+    Value *Shift = IRB.CreateAnd(PartialSize, IRB.getInt32(~7));
+    unsigned Val1Int = 0xcbcbcb00;
+    unsigned Val2Int = 0x000000cb;
+    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));
+    Value *Cond = IRB.CreateICmpNE(PartialBits, IRB.getInt32(0));
+    // For BigEndian get 0x000000YZ -> 0xYZ000000
+    if (ASan.DL->isBigEndian())
+      PartialBits = IRB.CreateShl(PartialBits, IRB.getInt32(24));
+    Instruction *Val2 = shiftAllocaMagic(PartialBits, IRB, Shift);
+    SelectInst *Partial = SelectInst::Create(Cond, PartialBits,
+                                             IRB.getInt32(Val2Int),
+                                             "partial_bits", Val2);
+    Val2->setOperand(0, Partial);
+    return IRB.CreateOr(Val1, Val2);
+  }
+
+  void 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 unsigned long AllocaRedzoneMask = kAllocaRzSize - 1;
+
+    Value *Zero = ConstantInt::get(IntptrTy, 0);
+    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);
+    SelectInst *PartialPadding = SelectInst::Create(Cond, Misalign, Zero,
+                                                    "additional_size", AI);
+
+    // 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.
+    poisonAddrForAlloca(LeftRzAddress, IRB, 0xcacacacaU);
+    Value *PartialRzAddr = IRB.CreateAdd(NewAddress, OldSize);
+    AllocaCall.LeftRzAddr = LeftRzAddress;
+
+    // PartialRzAligned = PartialRzAddr & ~AllocaRzMask
+    Value *PartialRzAligned = IRB.CreateAnd(PartialRzAddr, NotAllocaRzMask);
+    AllocaCall.PartialRzAddr = PartialRzAligned;
+
+    // RightRzAddress
+    //   =  (PartialRzAddr + AllocaRzMask) & ~AllocaRzMask
+    Value *RightRzAddress = IRB.CreateAnd(IRB.CreateAdd(PartialRzAddr,
+                                                        AllocaRzMask),
+                                          NotAllocaRzMask);
+
+    // Poisoning right redzone.
+    poisonAddrForAlloca(RightRzAddress, IRB, 0xcbcbcbcbU);
+    AllocaCall.RightRzAddr = RightRzAddress;
+
+    Value *PartialRzShadowBase = ASan.memToShadow(PartialRzAligned, IRB);
+    Value *PartialRzShadowBasePtr = IRB.CreateIntToPtr(PartialRzShadowBase,
+                                                       Int32PtrTy);
+    // if (PartialSize) {
+    //   PartialRzMagic = calculatePartialRzMagic(PartialSize);
+    //   ShadowBase = ASan.memToShadow(PartialRzAligned);
+    //   *ShadowBase = PartialRzMagic;
+    // }
+    Value *Cmp = IRB.CreateICmpNE(PartialSize, Zero);
+    Instruction *Term = SplitBlockAndInsertIfThen(Cmp, AI, false);
+    IRBuilder<> IRBIf(Term);
+    Value *PartialRzMagic = calculatePartialRzMagic(PartialSize, IRBIf);
+    IRBIf.CreateStore(PartialRzMagic, PartialRzShadowBasePtr);
+
+    // 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();
+  }
+
   /// \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 &&
void visitIntrinsicInst(IntrinsicInst &II) {
     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;

 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) {
         // For larger frames call __asan_stack_free_*.
         IRBPoison.CreateCall3(AsanStackFreeFunc[StackMallocIdx], LocalStackBase,
                               ConstantInt::get(IntptrTy, LocalStackSize),
                               OrigStackBase);
       }
 
       IRBuilder<> IRBElse(ElseTerm);
       poisonRedZones(L.ShadowBytes, IRBElse, ShadowBase, false);
-    } else if (HavePoisonedAllocas) {
+    } else {
+      if (ClInstrumentAllocas)
+        // Unpoison dynamic allocas.
+        for (auto AllocaCall : DynamicAllocaVec)
+          unpoisonDynamicAlloca(AllocaCall, IRBRet);
+
+      if (HavePoisonedAllocas) {
         // If we poisoned some allocas in llvm.lifetime analysis,
         // unpoison whole stack frame now.
         assert(LocalStackBase == OrigStackBase);
         poisonAlloca(LocalStackBase, LocalStackSize, IRBRet, false);
       } else {
         poisonRedZones(L.ShadowBytes, IRBRet, ShadowBase, false);
       }
     }
+  }
 
   // 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 (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
       if (IncValueAI == nullptr || (Res != nullptr && IncValueAI != Res))
         return nullptr;
       Res = IncValueAI;
     }
   }
   if (Res)
     AllocaForValue[V] = Res;
   return Res;
 }

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-DEFAULT
+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: %additional_size = select
+; CHECK-ALLOCA: %partial_bits = select
+; CHECK-NOALLOCA-NOT: %additional_size = select
+; CHECK-NOALLOCA-NOT: %partial_bits = select
+; CHECK-DEFAULT-NOT: %additional_size = select
+; CHECK-DEFAULT-NOT: %partial_bits = select
+  %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 + index, 64 - index);
+  assert(q && ((q - str) == index));
+}
+
+int main(int argc, char **argv) {
+  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;
+}