Implement variable-sized alloca instrumentation (take 2).

[m.ostapenko]

Summary

This patch introduces new way for dynamic allocas unpoisoning. Here, all dynamic allocas are linked in a linked list (each alloca stores pointer to previous one in left redzone), pointer to last alloca is stored in a special memory cell called DynamicAllocaLayout (however we are going to get rid of it and locate this pointer on register).

We introduce new __asan_unroll_alloca function, which unpoisons dynamic allocas before each Ret and StackRestore instructions (this probably should be inlined thought). This implementation does not support systems with upgrowing stack now.

[kcc]

OMG. I am curious, if you really have targets for which testing alloca is important...
Do we really need a list here?
Can't we handle the task with an integer indicating the combined sizes of allocas?

[ygribov]

OMG. I am curious, if you really have targets for which testing alloca is important...

Well, bugs do pop up in various OSS projects. Alloca is surprisingly widespread.

Do we really need a list here?
Can't we handle the task with an integer indicating the combined sizes of allocas?

We could simply memset(0) all shadow memory corresponding to dynamic part of stack. But this wouldn't scale to use-after-return (as I understand alloca regions will not be consecutive in this case).

[ygribov]

lib/Transforms/Instrumentation/AddressSanitizer.cpp

1969–1971

Why not unsigned btw?

[ygribov]

Kostya, so what's your call on this? The code isn't that complicated and I'm not sure there is an easier complete solution to dynamic stack variables. And dynamic stack arrays are indeed frequent.

[kcc]

I did not give much thought to dynamic allocas, but what if we simply replace them with run-time calls somehow?
Maybe we could reuse the FakeStack here somehow?

Alexey, you've been touching the Alloca's recently, and was going to touch them more. Thoughts?

[ygribov]

I did not give much thought to dynamic allocas, but what if we simply replace them with run-time calls somehow?

We could hide Max's linked lists behind an internal API, something like

// Poison redzones and store metadata for new_alloca
void asan_poison_alloca(uptr new_alloca, uptr size, uptr prev_alloca);

// Unpoison all allocas below bound
uptr asan_unpoison_allocas(uptr prev_alloca, uptr bound);

The ugly bound parameter is necessary to model the equally ugly alloca/VLA interwork. From https://gcc.gnu.org/onlinedocs/gcc/Variable-Length.html :

If you use both variable-length arrays and alloca in the same function, deallocation of a variable-length array also deallocates anything more recently allocated with alloca.

[m.ostapenko]

I did not give much thought to dynamic allocas, but what if we simply replace them with run-time calls somehow?

We could hide Max's linked lists behind an internal API, something like

// Poison redzones and store metadata for new_alloca
void asan_poison_alloca(uptr new_alloca, uptr size, uptr prev_alloca);

// Unpoison all allocas below bound
uptr asan_unpoison_allocas(uptr prev_alloca, uptr bound);

I think this is exactly what we want to do in UAR case. Since we don't know number of allocated regions until runtime (in general), we still need some dynamically growing structure (e.g. linked list) to store allocated regions to be unpoisoned before each ret instruction. We can hide this structure behind internal API, in runtime library, thought. For non-UAR case we can use memset for dynamic section indeed, but I'm not sure this is preferable way.

[kcc]

I'd prefer to hide as much as possible inside the run-time and have simplest possible compiler changes.
Also, whenever possible, I prefer not to have linked lists. I am pretty sure we can solve this problem with an array.

[rnk]

+1

ASan should replace dynamic allocas with runtime calls that delegate to
malloc. Poisoning will work out of the box with no changes.

We will need additional runtime handling to deal with VLAs, which use
llvm.stacksave / llvm.stackrestore.

[kcc]

Well, you clearly can not just use malloc, because then you have to call free() somewhere.
But something like asan's fake stack -- yes.

[rnk]

It occurs to me that ASan would need to add exceptional cleanups, if we
want this to cleanup after exception.

[kcc]

In D7098#130041, @rnk wrote:

It occurs to me that ASan would need to add exceptional cleanups, if we
want this to cleanup after exception.

Not necessary.
E.g. fake stack does garbage collection in the run-time lib.

[ygribov]

Also, whenever possible, I prefer not to have linked lists. I am pretty sure we can solve this problem with an array.

Note that number of allocas is not known statically so in general you'll need a dynamically growing array.

[kcc]

Note that number of allocas is not known statically so in general you'll need a dynamically growing array.

Haha, no.
While you don't know the number of allocas, their total size is limited by the size of the stack,
so you can pre-allocate an array at the thread start up.

dynamically growing array in a hot spot in asan is not wise.
We better allocate a bit extra space (maybe with MAP_NORESERVE)

So, maybe we simply use the existing fake stack (in use-after-return mode, or maybe even by default?) to simulate dynamic alloca?

[ygribov]

While you don't know the number of allocas, their total size is limited by the size of the stack,
so you can pre-allocate an array at the thread start up.
dynamically growing array in a hot spot in asan is not wise.

Right, that's why we originally proposed lists. Wouldn't this be much simpler?

So, maybe we simply use the existing fake stack (in use-after-return mode, or maybe even by default?) to simulate dynamic alloca?

I'd oppose to that - fake stacks pose unacceptable RAM overheads for mobile devices.

[kcc]

Right, that's why we originally proposed lists. Wouldn't this be much simpler?

There is nothing simpler than a non-resizable array :)
I still urge you to find a solution w/o lists, I think it's possible.
If nothing good shows up, ok, let's do lists, but in the asan-runtime (as opposed to compiler module)

try to minimize the amount of compiler changes. something like

1. all dynamic alloca() are replaced with __asan_dynamic_alloca which will use fake stack in use-after-return mode and real stack (with redzones) in base mode.
2. at all RET instructions __asan_release_dynamic_allocas is called, but in presence of exceptions/longjmp there is a backup recovery mechanism.

So, maybe we simply use the existing fake stack (in use-after-return mode, or maybe even by default?) to simulate dynamic alloca?

I'd oppose to that - fake stacks pose unacceptable RAM overheads for mobile devices.

Fair enough.

[m.ostapenko]

Hi!
I'm sorry for delay.
Here are some approaches we can follow for dynamic allocas:

1. We can instrument all allocas with runtime call for both UAR/non-UARcases (for non-UAR we'll just perform poisoning, for UAR allocate allocas using fake stacks). But this will lead to complex logic into unpoisoning functionality, since allocated memory chunks for UAR will not be consecutive.
2. We probably can allocate single memory chunk for dynamic stack area via asan_stack_malloc similarly to static stack area and use memset for unpoisoning, but since we don't know total size of dynamic area, this might be unfriendly for memory consumption.
3. We can ignore UAR detection for now and always allocate dynamic allocas on stack for both cases. This is the simplest solution, the only trick here is how to get a size parameter for memset, that would perform unpoisoning stuff before each ret and llvm.stackrestore instructions.

Generally, I don't see a convenient way to deal with UAR detection without code mess, perhaps we can skip it for now? Right now, I'm testing a patch for non-UAR case, it seems to be quite simple.

[m.ostapenko]

I would like to ping the patch. Updated with small nits fixed. All tests passed for x86_64-unknown-linux-gnu.

[kcc]

I am sorry for the delay -- I was OOO for the last 4 weeks. Will try to respond this week.

[kcc]

LGTM
Looks simple enough.
This is still off by default, right? Did you test it on something huge?

test/asan/TestCases/alloca_vla_interact.cc

12

Does it have to be a macro?

[m.ostapenko]

Konstantin, thank you for review!

In D7098#169544, @kcc wrote:

LGTM
Looks simple enough.
This is still off by default, right? Did you test it on something huge?

Yes, it's off by default. I've managed to build Firefox with dynamic allocas instrumentation enabled, is it big enough? I'm also found a "bug" there and I'm trying to understand if it's a real bug (not just unpoisoning error or something like that).

[kcc]

I've managed to build Firefox with dynamic allocas instrumentation enabled, is it big enough?

Yea, it's big, and I expect it to have quite a few allocas/VLAs

I'm also found a "bug" there and I'm trying to understand if it's a real bug (not just unpoisoning error or something like that).

Let us know how it goes.

I think you may commit this in the meantime.

[ygribov]

I'm also found a "bug" there and I'm trying to understand if it's a real bug (not just unpoisoning error or something like that).

Let us know how it goes.

That one turned out to be false positive - JS engine was allocating frame for asm stub via alloca, then freeing and re-using it inside the stub.

[m.ostapenko]

Sorry for delay, I was on vacation last week.

Proceeding Firefox testing, I've ran to several tests failures due to reasons pretty much similar to described above by Yura (allocating stack frame via alloca and some asm magic with deallocating after). After I'd worked around these allocas (asan_blacklist.txt was very helpful here), none of new test failures were popped up.

So, Konstantin, if you don't mind, I'll ask Yura to land this revision after retesting complete.

[kcc]

Yes, go ahead.
We'll need to also test it on chromium before enabling the flag by default.
Thanks!

[LeoneChen]

This comment was removed by LeoneChen.

lib/Transforms/Instrumentation/AddressSanitizer.cpp

 static const char *const kAsanPoisonStackMemoryName =
     "__asan_poison_stack_memory";
 static const char *const kAsanUnpoisonStackMemoryName =
     "__asan_unpoison_stack_memory";
 
 static const char *const kAsanOptionDetectUAR =
     "__asan_option_detect_stack_use_after_return";
 
+static const char *const kAsanAllocaPoison =
+    "__asan_alloca_poison";
+static const char *const kAsanAllocasUnpoison =
+    "__asan_allocas_unpoison";
+
 // 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(
static cl::opt<std::string> ClDebugFunc("asan-debug-func", cl::Hidden,
                                         cl::desc("Debug func"));
 static cl::opt<int> ClDebugMin("asan-debug-min", cl::desc("Debug min inst"),
                                cl::Hidden, cl::init(-1));
 static cl::opt<int> ClDebugMax("asan-debug-max", cl::desc("Debug man inst"),
                                cl::Hidden, cl::init(-1));
 
 STATISTIC(NumInstrumentedReads, "Number of instrumented reads");
 STATISTIC(NumInstrumentedWrites, "Number of instrumented writes");
-STATISTIC(NumInstrumentedDynamicAllocas,
-          "Number of instrumented dynamic allocas");
 STATISTIC(NumOptimizedAccessesToGlobalVar,
           "Number of optimized accesses to global vars");
 STATISTIC(NumOptimizedAccessesToStackVar,
           "Number of optimized accesses to stack vars");
 
 namespace {
 /// Frontend-provided metadata for source location.
 struct LocationMetadata {
struct AddressSanitizer : public FunctionPass {
   uint64_t getAllocaSizeInBytes(AllocaInst *AI) const {
     Type *Ty = AI->getAllocatedType();
     uint64_t SizeInBytes =
         AI->getModule()->getDataLayout().getTypeAllocSize(Ty);
     return SizeInBytes;
   }
   /// Check if we want (and can) handle this alloca.
   bool isInterestingAlloca(AllocaInst &AI);
+
+  // Check if we have dynamic alloca.
+  bool isDynamicAlloca(AllocaInst &AI) const {
+    return AI.isArrayAllocation() || !AI.isStaticAlloca();
+  }
+
   /// If it is an interesting memory access, return the PointerOperand
   /// and set IsWrite/Alignment. Otherwise return nullptr.
   Value *isInterestingMemoryAccess(Instruction *I, bool *IsWrite,
                                    uint64_t *TypeSize,
                                    unsigned *Alignment);
   void instrumentMop(ObjectSizeOffsetVisitor &ObjSizeVis, Instruction *I,
                      bool UseCalls, const DataLayout &DL);
   void instrumentPointerComparisonOrSubtraction(Instruction *I);
struct FunctionStackPoisoner : public InstVisitor<FunctionStackPoisoner> {
 
   SmallVector<AllocaInst *, 16> AllocaVec;
   SmallVector<Instruction *, 8> RetVec;
   unsigned StackAlignment;
 
   Function *AsanStackMallocFunc[kMaxAsanStackMallocSizeClass + 1],
       *AsanStackFreeFunc[kMaxAsanStackMallocSizeClass + 1];
   Function *AsanPoisonStackMemoryFunc, *AsanUnpoisonStackMemoryFunc;
+  Function *AsanAllocaPoisonFunc, *AsanAllocasUnpoisonFunc;
 
   // Stores a place and arguments of poisoning/unpoisoning call for alloca.
   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;
-    bool Poison;
-    explicit DynamicAllocaCall(AllocaInst *AI, Value *LeftRzAddr = nullptr,
-                               Value *RightRzAddr = nullptr)
-        : AI(AI),
-          LeftRzAddr(LeftRzAddr),
-          RightRzAddr(RightRzAddr),
-          Poison(true) {}
-  };
-  SmallVector<DynamicAllocaCall, 1> DynamicAllocaVec;
+  SmallVector<AllocaInst *, 1> DynamicAllocaVec;
+  SmallVector<IntrinsicInst *, 1> StackRestoreVec;
+  AllocaInst *DynamicAllocaLayout = nullptr;
 
   // Maps Value to an AllocaInst from which the Value is originated.
   typedef DenseMap<Value *, AllocaInst *> AllocaForValueMapTy;
   AllocaForValueMapTy AllocaForValue;
 
   bool HasNonEmptyInlineAsm;
   std::unique_ptr<CallInst> EmptyInlineAsm;
 
bool runOnFunction() {
     return true;
   }
 
   // Finds all Alloca instructions and puts
   // poisoned red zones around all of them.
   // Then unpoison everything back before the function returns.
   void poisonStack();
 
+  void createDynamicAllocasInitStorage();
+
   // ----------------------- Visitors.
   /// \brief Collect all Ret instructions.
   void visitReturnInst(ReturnInst &RI) { RetVec.push_back(&RI); }
 
-  // Unpoison dynamic allocas redzones.
-  void unpoisonDynamicAlloca(DynamicAllocaCall &AllocaCall) {
-    if (!AllocaCall.Poison) return;
-    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));
-    }
+  void unpoisonDynamicAllocasBeforeInst(Instruction *InstBefore,
+                                        Value *SavedStack) {
+    IRBuilder<> IRB(InstBefore);
+    IRB.CreateCall2(AsanAllocasUnpoisonFunc,
+                    IRB.CreateLoad(DynamicAllocaLayout),
+                    IRB.CreatePtrToInt(SavedStack, IntptrTy));
   }
 
-  // Right shift for BigEndian and left shift for LittleEndian.
-  Value *shiftAllocaMagic(Value *Val, IRBuilder<> &IRB, Value *Shift) {
-    auto &DL = F.getParent()->getDataLayout();
-    return 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);
+  // Unpoison dynamic allocas redzones.
+  void unpoisonDynamicAllocas() {
+    for (auto &Ret : RetVec)
+      unpoisonDynamicAllocasBeforeInst(Ret, DynamicAllocaLayout);
+
+    for (auto &StackRestoreInst : StackRestoreVec)
+      unpoisonDynamicAllocasBeforeInst(StackRestoreInst,
+                                       StackRestoreInst->getOperand(0));
+  }
 
   // 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);
+  void handleDynamicAllocaCall(AllocaInst *AI);
 
   /// \brief Collect Alloca instructions we want (and can) handle.
   void visitAllocaInst(AllocaInst &AI) {
     if (!ASan.isInterestingAlloca(AI)) return;
 
     StackAlignment = std::max(StackAlignment, AI.getAlignment());
-    if (isDynamicAlloca(AI))
-      DynamicAllocaVec.push_back(DynamicAllocaCall(&AI));
+    if (ASan.isDynamicAlloca(AI))
+      DynamicAllocaVec.push_back(&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::stackrestore) StackRestoreVec.push_back(&II);
+    if (!ClCheckLifetime) return;
     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.
struct FunctionStackPoisoner : public InstVisitor<FunctionStackPoisoner> {
 
   bool doesDominateAllExits(const Instruction *I) const {
     for (auto Ret : RetVec) {
       if (!ASan.getDominatorTree().dominates(I, Ret)) return false;
     }
     return true;
   }
 
-  bool isDynamicAlloca(AllocaInst &AI) const {
-    return AI.isArrayAllocation() || !AI.isStaticAlloca();
-  }
   /// Finds alloca where the value comes from.
   AllocaInst *findAllocaForValue(Value *V);
   void poisonRedZones(ArrayRef<uint8_t> ShadowBytes, IRBuilder<> &IRB,
                       Value *ShadowBase, bool DoPoison);
   void poisonAlloca(Value *V, uint64_t Size, IRBuilder<> &IRB, bool DoPoison);
 
   void SetShadowToStackAfterReturnInlined(IRBuilder<> &IRB, Value *ShadowBase,
                                           int Size);

 
 /// Check if we want (and can) handle this alloca.
 bool AddressSanitizer::isInterestingAlloca(AllocaInst &AI) {
   auto PreviouslySeenAllocaInfo = ProcessedAllocas.find(&AI);
 
   if (PreviouslySeenAllocaInfo != ProcessedAllocas.end())
     return PreviouslySeenAllocaInfo->getSecond();
 
-  bool IsInteresting = (AI.getAllocatedType()->isSized() &&
+  bool IsInteresting =
+      (AI.getAllocatedType()->isSized() &&
        // alloca() may be called with 0 size, ignore it.
        getAllocaSizeInBytes(&AI) > 0 &&
        // We are only interested in allocas not promotable to registers.
        // Promotable allocas are common under -O0.
-    (!ClSkipPromotableAllocas || !isAllocaPromotable(&AI)));
+       (!ClSkipPromotableAllocas || !isAllocaPromotable(&AI) ||
+        isDynamicAlloca(AI)));
 
   ProcessedAllocas[&AI] = IsInteresting;
   return IsInteresting;
 }
 
 /// If I is an interesting memory access, return the PointerOperand
 /// and set IsWrite/Alignment. Otherwise return nullptr.
 Value *AddressSanitizer::isInterestingMemoryAccess(Instruction *I,
AsanStackFreeFunc[i] = checkSanitizerInterfaceFunction(
                               IRB.getVoidTy(), IntptrTy, IntptrTy, nullptr));
   }
   AsanPoisonStackMemoryFunc = checkSanitizerInterfaceFunction(
       M.getOrInsertFunction(kAsanPoisonStackMemoryName, IRB.getVoidTy(),
                             IntptrTy, IntptrTy, nullptr));
   AsanUnpoisonStackMemoryFunc = checkSanitizerInterfaceFunction(
       M.getOrInsertFunction(kAsanUnpoisonStackMemoryName, IRB.getVoidTy(),
                             IntptrTy, IntptrTy, nullptr));
+  AsanAllocaPoisonFunc = checkSanitizerInterfaceFunction(M.getOrInsertFunction(
+      kAsanAllocaPoison, IRB.getVoidTy(), IntptrTy, IntptrTy, nullptr));
+  AsanAllocasUnpoisonFunc =
+      checkSanitizerInterfaceFunction(M.getOrInsertFunction(
+          kAsanAllocasUnpoison, IRB.getVoidTy(), IntptrTy, IntptrTy, nullptr));
 }
 
 void FunctionStackPoisoner::poisonRedZones(ArrayRef<uint8_t> ShadowBytes,
                                            IRBuilder<> &IRB, Value *ShadowBase,
                                            bool DoPoison) {
   size_t n = ShadowBytes.size();
   size_t i = 0;
   // We need to (un)poison n bytes of stack shadow. Poison as many as we can
if (Dynamic) {
     assert(Alloca->isStaticAlloca());
   }
   assert((ClRealignStack & (ClRealignStack - 1)) == 0);
   size_t FrameAlignment = std::max(L.FrameAlignment, (size_t)ClRealignStack);
   Alloca->setAlignment(FrameAlignment);
   return IRB.CreatePointerCast(Alloca, IntptrTy);
 }
 
+void FunctionStackPoisoner::createDynamicAllocasInitStorage() {
+  BasicBlock &FirstBB = *F.begin();
+  IRBuilder<> IRB(dyn_cast<Instruction>(FirstBB.begin()));
+  DynamicAllocaLayout = IRB.CreateAlloca(IntptrTy, nullptr);
+  IRB.CreateStore(Constant::getNullValue(IntptrTy), DynamicAllocaLayout);
+  DynamicAllocaLayout->setAlignment(32);
+}
+
 void FunctionStackPoisoner::poisonStack() {
   assert(AllocaVec.size() > 0 || DynamicAllocaVec.size() > 0);
 
-  if (ClInstrumentAllocas) {
+  if (ClInstrumentAllocas && DynamicAllocaVec.size() > 0) {
     // Handle dynamic allocas.
-    for (auto &AllocaCall : DynamicAllocaVec) {
-      handleDynamicAllocaCall(AllocaCall);
-      unpoisonDynamicAlloca(AllocaCall);
-    }
+    createDynamicAllocasInitStorage();
+    for (auto &AI : DynamicAllocaVec)
+      handleDynamicAllocaCall(AI);
+
+    unpoisonDynamicAllocas();
   }
 
   if (AllocaVec.size() == 0) return;
 
   int StackMallocIdx = -1;
   DebugLoc EntryDebugLocation = getFunctionEntryDebugLocation(F);
 
   Instruction *InsBefore = AllocaVec[0];
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 (!F.getParent()->getDataLayout().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 (F.getParent()->getDataLayout().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;
-  if (!doesDominateAllExits(AI)) {
-    // We do not yet handle complex allocas
-    AllocaCall.Poison = false;
-    return;
-  }
-
+void FunctionStackPoisoner::handleDynamicAllocaCall(AllocaInst *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 =
+  const unsigned ElementSize =
       F.getParent()->getDataLayout().getTypeAllocSize(AI->getAllocatedType());
-  Value *OldSize = IRB.CreateMul(AI->getArraySize(),
-                                 ConstantInt::get(IntptrTy, ElementSize));
+  Value *OldSize =
+      IRB.CreateMul(IRB.CreateIntCast(AI->getArraySize(), IntptrTy, false),
 
   // PartialSize = OldSize % 32
   Value *PartialSize = IRB.CreateAnd(OldSize, AllocaRzMask);
 
   // Misalign = kAllocaRzSize - PartialSize;
   Value *Misalign = IRB.CreateSub(AllocaRzSize, PartialSize);
 
   // PartialPadding = Misalign != kAllocaRzSize ? Misalign : 0;
void FunctionStackPoisoner::handleDynamicAllocaCall(AllocaInst *AI) {
   // 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());
+  // Insert __asan_alloca_poison call for new created alloca.
+  IRB.CreateCall2(AsanAllocaPoisonFunc, NewAddress, OldSize);
 
-  // LeftRzAddress = NewAddress - kAllocaRzSize
-  Value *LeftRzAddress = IRB.CreateSub(NewAddress, AllocaRzSize);
+  // Store the last alloca's address to DynamicAllocaLayout. We'll need this
+  // for unpoisoning stuff.
+  IRB.CreateStore(IRB.CreatePtrToInt(NewAlloca, IntptrTy), DynamicAllocaLayout);
 
-  // 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));
+  Value *NewAddressPtr = IRB.CreateIntToPtr(NewAddress, AI->getType());
 
-  // Replace all uses of AddessReturnedByAlloca with NewAddress.
+  // Replace all uses of AddessReturnedByAlloca with NewAddressPtr.
   AI->replaceAllUsesWith(NewAddressPtr);
 
-  // We are done. Erase old alloca and store left, partial and right redzones
-  // shadow addresses for future unpoisoning.
+  // We are done. Erase old alloca from parent.
   AI->eraseFromParent();
-  NumInstrumentedDynamicAllocas++;
 }
 
 // isSafeAccess returns true if Addr is always inbounds with respect to its
 // base object. For example, it is a field access or an array access with
 // constant inbounds index.
 bool AddressSanitizer::isSafeAccess(ObjectSizeOffsetVisitor &ObjSizeVis,
                                     Value *Addr, uint64_t TypeSize) const {
   SizeOffsetType SizeOffset = ObjSizeVis.compute(Addr);

lib/asan/asan_fake_stack.cc

 
 namespace __asan {
 
 static const u64 kMagic1 = kAsanStackAfterReturnMagic;
 static const u64 kMagic2 = (kMagic1 << 8) | kMagic1;
 static const u64 kMagic4 = (kMagic2 << 16) | kMagic2;
 static const u64 kMagic8 = (kMagic4 << 32) | kMagic4;
 
+static const u64 kAllocaRedzoneSize = 32UL;
+static const u64 kAllocaRedzoneMask = 31UL;
+
 // For small size classes inline PoisonShadow for better performance.
 ALWAYS_INLINE void SetShadow(uptr ptr, uptr size, uptr class_id, u64 magic) {
   CHECK_EQ(SHADOW_SCALE, 3);  // This code expects SHADOW_SCALE=3.
   u64 *shadow = reinterpret_cast<u64*>(MemToShadow(ptr));
   if (class_id <= 6) {
     for (uptr i = 0; i < (1U << class_id); i++) {
       shadow[i] = magic;
       SanitizerBreakOptimization(0);  // Make sure this does not become memset.
FakeFrame *frame = reinterpret_cast<FakeFrame *>(fs->AddrIsInFakeStack(
       reinterpret_cast<uptr>(addr), &frame_beg, &frame_end));
   if (!frame) return 0;
   if (frame->magic != kCurrentStackFrameMagic)
     return 0;
   if (beg) *beg = reinterpret_cast<void*>(frame_beg);
   if (end) *end = reinterpret_cast<void*>(frame_end);
   return reinterpret_cast<void*>(frame->real_stack);
 }
+
+SANITIZER_INTERFACE_ATTRIBUTE
+void __asan_alloca_poison(uptr addr, uptr size) {
+  uptr LeftRedzoneAddr = addr - kAllocaRedzoneSize;
+  uptr PartialRzAddr = addr + size;
+  uptr RightRzAddr = (PartialRzAddr + kAllocaRedzoneMask) & ~kAllocaRedzoneMask;
+  uptr PartialRzAligned = PartialRzAddr & ~(SHADOW_GRANULARITY - 1);
+  FastPoisonShadow(LeftRedzoneAddr, kAllocaRedzoneSize, kAsanAllocaLeftMagic);
+  FastPoisonShadowPartialRightRedzone(
+      PartialRzAligned, PartialRzAddr % SHADOW_GRANULARITY,
+      RightRzAddr - PartialRzAligned, kAsanAllocaRightMagic);
+  FastPoisonShadow(RightRzAddr, kAllocaRedzoneSize, kAsanAllocaRightMagic);
+}
+
+SANITIZER_INTERFACE_ATTRIBUTE
+void __asan_allocas_unpoison(uptr top, uptr bottom) {
+  if ((!top) || (top > bottom)) return;
+  REAL(memset)(reinterpret_cast<void*>(MemToShadow(top)), 0,
+               (bottom - top) / SHADOW_GRANULARITY);
+}
 }  // extern "C"

lib/asan/asan_interface_internal.h

extern "C" {
   SANITIZER_INTERFACE_ATTRIBUTE
   void __asan_poison_cxx_array_cookie(uptr p);
   SANITIZER_INTERFACE_ATTRIBUTE
   uptr __asan_load_cxx_array_cookie(uptr *p);
   SANITIZER_INTERFACE_ATTRIBUTE
   void __asan_poison_intra_object_redzone(uptr p, uptr size);
   SANITIZER_INTERFACE_ATTRIBUTE
   void __asan_unpoison_intra_object_redzone(uptr p, uptr size);
+  SANITIZER_INTERFACE_ATTRIBUTE
+  void __asan_alloca_poison(uptr addr, uptr size);
+  SANITIZER_INTERFACE_ATTRIBUTE
+  void __asan_allocas_unpoison(uptr top, uptr bottom);
 }  // extern "C"
 
 #endif  // ASAN_INTERFACE_INTERNAL_H

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
+; CHECK-ALLOCA: __asan_alloca_poison
+; CHECK-ALLOCA: __asan_allocas_unpoison
   %0 = alloca i32, align 4
   %1 = alloca i8*
   store volatile i32 %len, i32* %0, align 4
   %2 = load i32, i32* %0, align 4
   %3 = zext i32 %2 to i64
   %4 = alloca i8, i64 %3, align 32
   store volatile i8 0, i8* %4
   ret void
 }
 

test/asan/TestCases/Linux/interface_symbols_linux.c

 // RUN: echo __asan_report_exp_store2 >> %t.interface
 // RUN: echo __asan_report_exp_store4 >> %t.interface
 // RUN: echo __asan_report_exp_store8 >> %t.interface
 // RUN: echo __asan_report_exp_store16 >> %t.interface
 // RUN: echo __asan_report_exp_load_n >> %t.interface
 // RUN: echo __asan_report_exp_store_n >> %t.interface
 // RUN: echo __asan_get_current_fake_stack >> %t.interface
 // RUN: echo __asan_addr_is_in_fake_stack >> %t.interface
+// RUN: echo __asan_alloca_poison >> %t.interface
+// RUN: echo __asan_allocas_unpoison >> %t.interface
 // RUN: cat %t.interface | sort -u | diff %t.symbols -
 
 // FIXME: nm -D on powerpc somewhy shows ASan interface symbols residing
 // in "initialized data section".
 // REQUIRES: x86_64-supported-target,i386-supported-target,asan-static-runtime
 
 int main() { return 0; }

test/asan/TestCases/alloca_loop_unpoisoning.cc

+// RUN: %clangxx_asan -O0 -mllvm -asan-instrument-allocas %s -o %t
+// RUN: %run %t 2>&1
+//
+
+// This testcase checks that allocas and VLAs inside loop are correctly unpoisoned.
+
+#include <assert.h>
+#include <alloca.h>
+#include <stdint.h>
+#include "sanitizer/asan_interface.h"
+
+void *top, *bot;
+
+__attribute__((noinline)) void foo(int len) {
+  char x;
+  top = &x;
+  char array[len];  // NOLINT
+  assert(!(reinterpret_cast<uintptr_t>(array) & 31L));
+  alloca(len);
+  for (int i = 0; i < 32; ++i) {
+    char array[i];  // NOLINT
+    bot = alloca(i);
+    assert(!(reinterpret_cast<uintptr_t>(bot) & 31L));
+  }
+}
+
+int main(int argc, char **argv) {
+  foo(32);
+  void *q = __asan_region_is_poisoned(bot, (char *)top - (char *)bot);
+  assert(!q);
+  return 0;
+}

test/asan/TestCases/alloca_vla_interact.cc

+// RUN: %clangxx_asan -O0 -mllvm -asan-instrument-allocas %s -o %t
+// RUN: %run %t 2>&1
+//
+
+// This testcase checks correct interaction between VLAs and allocas.
+
+#include <assert.h>
+#include <alloca.h>
+#include <stdint.h>
+#include "sanitizer/asan_interface.h"
+
+#define RZ 32
+
+__attribute__((noinline)) void foo(int len) {
+  char *top, *bot;
+  // This alloca call should live until the end of foo.
+  char *alloca1 = (char *)alloca(len);
+  assert(!(reinterpret_cast<uintptr_t>(alloca1) & 31L));
+  // This should be first poisoned address after loop.
+  top = alloca1 - RZ;
+  for (int i = 0; i < 32; ++i) {
+    // Check that previous alloca was unpoisoned at the end of iteration.
+    if (i) assert(!__asan_region_is_poisoned(bot, 96));
+    // VLA is unpoisoned at the end of iteration.
+    volatile char array[i];
+    assert(!(reinterpret_cast<uintptr_t>(array) & 31L));
+    // Alloca is unpoisoned at the end of iteration,
+    // because dominated by VLA.
+    bot = (char *)alloca(i) - RZ;
+  }
+  // Check that all allocas from loop were unpoisoned correctly.
+  void *q = __asan_region_is_poisoned(bot, (char *)top - (char *)bot + 1);
+  assert(q == top);
+}
+
+int main(int argc, char **argv) {
+  foo(32);
+  return 0;
+}

test/asan/TestCases/vla_chrome_testcase.cc

+// RUN: %clangxx_asan -O0 -mllvm -asan-instrument-allocas %s -o %t
+// RUN: not %run %t 2>&1 | FileCheck %s
+//
+
+// This is reduced testcase based on Chromium code.
+// See http://reviews.llvm.org/D6055?vs=on&id=15616&whitespace=ignore-all#toc.
+
+#include <stdint.h>
+#include <assert.h>
+
+int a = 7;
+int b;
+int c;
+int *p;
+
+__attribute__((noinline)) void fn3(int *first, int second) {
+}
+
+int main() {
+  int d = b && c;
+  int e[a]; // NOLINT
+  assert(!(reinterpret_cast<uintptr_t>(e) & 31L));
+  int f;
+  if (d)
+    fn3(&f, sizeof 0 * (&c - e));
+  e[a] = 0;
+// CHECK: ERROR: AddressSanitizer: dynamic-stack-buffer-overflow on address [[ADDR:0x[0-9a-f]+]]
+// CHECK: WRITE of size 4 at [[ADDR]] thread T0
+  return 0;
+}

test/asan/TestCases/vla_condition_overflow.cc

+// RUN: %clangxx_asan -O0 -mllvm -asan-instrument-allocas %s -o %t
+// RUN: not %run %t 2>&1 | FileCheck %s
+//
+
+#include <assert.h>
+#include <stdint.h>
+
+__attribute__((noinline)) void foo(int index, int len) {
+  if (index > len) {
+    char str[len]; //NOLINT
+    assert(!(reinterpret_cast<uintptr_t>(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/vla_loop_overfow.cc

+// RUN: %clangxx_asan -O0 -mllvm -asan-instrument-allocas %s -o %t
+// RUN: not %run %t 2>&1 | FileCheck %s
+//
+
+#include <assert.h>
+#include <stdint.h>
+
+void foo(int index, int len) {
+  for (int i = 1; i < len; ++i) {
+    char array[len]; // NOLINT
+    assert(!(reinterpret_cast<uintptr_t>(array) & 31L));
+    array[index + i] = 0;
+// 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(9, 21);
+  return 0;
+}