lib/Transforms/Instrumentation/AddressSanitizer.cpp

   1 //===-- AddressSanitizer.cpp - memory error detector ------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file is a part of AddressSanitizer, an address sanity checker.
  11 // Details of the algorithm:
  12 //  http://code.google.com/p/address-sanitizer/wiki/AddressSanitizerAlgorithm
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #define DEBUG_TYPE "asan"
  17
  18 #include "FunctionBlackList.h"
  19 #include "llvm/Function.h"
  20 #include "llvm/IRBuilder.h"
  21 #include "llvm/IntrinsicInst.h"
  22 #include "llvm/LLVMContext.h"
  23 #include "llvm/Module.h"
  24 #include "llvm/Type.h"
  25 #include "llvm/ADT/ArrayRef.h"
  26 #include "llvm/ADT/OwningPtr.h"
  27 #include "llvm/ADT/SmallSet.h"
  28 #include "llvm/ADT/SmallString.h"
  29 #include "llvm/ADT/SmallVector.h"
  30 #include "llvm/ADT/StringExtras.h"
  31 #include "llvm/ADT/Triple.h"
  32 #include "llvm/Support/CommandLine.h"
  33 #include "llvm/Support/DataTypes.h"
  34 #include "llvm/Support/Debug.h"
  35 #include "llvm/Support/raw_ostream.h"
  36 #include "llvm/Support/system_error.h"
  37 #include "llvm/Target/TargetData.h"
  38 #include "llvm/Target/TargetMachine.h"
  39 #include "llvm/Transforms/Instrumentation.h"
  40 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  41 #include "llvm/Transforms/Utils/ModuleUtils.h"
  42
  43 #include <string>
  44 #include <algorithm>
  45
  46 using namespace llvm;
  47
  48 static const uint64_t kDefaultShadowScale = 3;
  49 static const uint64_t kDefaultShadowOffset32 = 1ULL << 29;
  50 static const uint64_t kDefaultShadowOffset64 = 1ULL << 44;
  51 static const uint64_t kDefaultShadowOffsetAndroid = 0;
  52
  53 static const size_t kMaxStackMallocSize = 1 << 16;  // 64K
  54 static const uintptr_t kCurrentStackFrameMagic = 0x41B58AB3;
  55 static const uintptr_t kRetiredStackFrameMagic = 0x45E0360E;
  56
  57 static const char *kAsanModuleCtorName = "asan.module_ctor";
  58 static const char *kAsanModuleDtorName = "asan.module_dtor";
  59 static const int   kAsanCtorAndCtorPriority = 1;
  60 static const char *kAsanReportErrorTemplate = "__asan_report_";
  61 static const char *kAsanRegisterGlobalsName = "__asan_register_globals";
  62 static const char *kAsanUnregisterGlobalsName = "__asan_unregister_globals";
  63 static const char *kAsanInitName = "__asan_init";
  64 static const char *kAsanHandleNoReturnName = "__asan_handle_no_return";
  65 static const char *kAsanMappingOffsetName = "__asan_mapping_offset";
  66 static const char *kAsanMappingScaleName = "__asan_mapping_scale";
  67 static const char *kAsanStackMallocName = "__asan_stack_malloc";
  68 static const char *kAsanStackFreeName = "__asan_stack_free";
  69
  70 static const int kAsanStackLeftRedzoneMagic = 0xf1;
  71 static const int kAsanStackMidRedzoneMagic = 0xf2;
  72 static const int kAsanStackRightRedzoneMagic = 0xf3;
  73 static const int kAsanStackPartialRedzoneMagic = 0xf4;
  74
  75 // Accesses sizes are powers of two: 1, 2, 4, 8, 16.
  76 static const size_t kNumberOfAccessSizes = 5;
  77
  78 // Command-line flags.
  79
  80 // This flag may need to be replaced with -f[no-]asan-reads.
  81 static cl::opt<bool> ClInstrumentReads("asan-instrument-reads",
  82        cl::desc("instrument read instructions"), cl::Hidden, cl::init(true));
  83 static cl::opt<bool> ClInstrumentWrites("asan-instrument-writes",
  84        cl::desc("instrument write instructions"), cl::Hidden, cl::init(true));
  85 static cl::opt<bool> ClInstrumentAtomics("asan-instrument-atomics",
  86        cl::desc("instrument atomic instructions (rmw, cmpxchg)"),
  87        cl::Hidden, cl::init(true));
  88 static cl::opt<bool> ClMergeCallbacks("asan-merge-callbacks",
  89        cl::desc("merge __asan_report_ callbacks to create fewer BBs"),
  90        cl::Hidden, cl::init(false));
  91 // This flag limits the number of instructions to be instrumented
  92 // in any given BB. Normally, this should be set to unlimited (INT_MAX),
  93 // but due to http://llvm.org/bugs/show_bug.cgi?id=12652 we temporary
  94 // set it to 10000.
  95 static cl::opt<int> ClMaxInsnsToInstrumentPerBB("asan-max-ins-per-bb",
  96        cl::init(10000),
  97        cl::desc("maximal number of instructions to instrument in any given BB"),
  98        cl::Hidden);
  99 // This flag may need to be replaced with -f[no]asan-stack.
 100 static cl::opt<bool> ClStack("asan-stack",
 101        cl::desc("Handle stack memory"), cl::Hidden, cl::init(true));
 102 // This flag may need to be replaced with -f[no]asan-use-after-return.
 103 static cl::opt<bool> ClUseAfterReturn("asan-use-after-return",
 104        cl::desc("Check return-after-free"), cl::Hidden, cl::init(false));
 105 // This flag may need to be replaced with -f[no]asan-globals.
 106 static cl::opt<bool> ClGlobals("asan-globals",
 107        cl::desc("Handle global objects"), cl::Hidden, cl::init(true));
 108 static cl::opt<bool> ClMemIntrin("asan-memintrin",
 109        cl::desc("Handle memset/memcpy/memmove"), cl::Hidden, cl::init(true));
 110 // This flag may need to be replaced with -fasan-blacklist.
 111 static cl::opt<std::string>  ClBlackListFile("asan-blacklist",
 112        cl::desc("File containing the list of functions to ignore "
 113                 "during instrumentation"), cl::Hidden);
 114
 115 // These flags allow to change the shadow mapping.
 116 // The shadow mapping looks like
 117 //    Shadow = (Mem >> scale) + (1 << offset_log)
 118 static cl::opt<int> ClMappingScale("asan-mapping-scale",
 119        cl::desc("scale of asan shadow mapping"), cl::Hidden, cl::init(0));
 120 static cl::opt<int> ClMappingOffsetLog("asan-mapping-offset-log",
 121        cl::desc("offset of asan shadow mapping"), cl::Hidden, cl::init(-1));
 122
 123 // Optimization flags. Not user visible, used mostly for testing
 124 // and benchmarking the tool.
 125 static cl::opt<bool> ClOpt("asan-opt",
 126        cl::desc("Optimize instrumentation"), cl::Hidden, cl::init(true));
 127 static cl::opt<bool> ClOptSameTemp("asan-opt-same-temp",
 128        cl::desc("Instrument the same temp just once"), cl::Hidden,
 129        cl::init(true));
 130 static cl::opt<bool> ClOptGlobals("asan-opt-globals",
 131        cl::desc("Don't instrument scalar globals"), cl::Hidden, cl::init(true));
 132
 133 // Debug flags.
 134 static cl::opt<int> ClDebug("asan-debug", cl::desc("debug"), cl::Hidden,
 135                             cl::init(0));
 136 static cl::opt<int> ClDebugStack("asan-debug-stack", cl::desc("debug stack"),
 137                                  cl::Hidden, cl::init(0));
 138 static cl::opt<std::string> ClDebugFunc("asan-debug-func",
 139                                         cl::Hidden, cl::desc("Debug func"));
 140 static cl::opt<int> ClDebugMin("asan-debug-min", cl::desc("Debug min inst"),
 141                                cl::Hidden, cl::init(-1));
 142 static cl::opt<int> ClDebugMax("asan-debug-max", cl::desc("Debug man inst"),
 143                                cl::Hidden, cl::init(-1));
 144
 145 namespace {
 146
 147 /// An object of this type is created while instrumenting every function.
 148 struct AsanFunctionContext {
 149   AsanFunctionContext(Function &Function) : F(Function), CrashBlock() { }
 150
 151   Function &F;
 152   // These are initially zero. If we require at least one call to
 153   // __asan_report_{read,write}{1,2,4,8,16}, an appropriate BB is created.
 154   BasicBlock *CrashBlock[2][kNumberOfAccessSizes];
 155 };
 156
 157 /// AddressSanitizer: instrument the code in module to find memory bugs.
 158 struct AddressSanitizer : public ModulePass {
 159   AddressSanitizer();
 160   virtual const char *getPassName() const;
 161   void instrumentMop(AsanFunctionContext &AFC, Instruction *I);
 162   void instrumentAddress(AsanFunctionContext &AFC,
 163                          Instruction *OrigIns, IRBuilder<> &IRB,
 164                          Value *Addr, uint32_t TypeSize, bool IsWrite);
 165   Value *createSlowPathCmp(IRBuilder<> &IRB, Value *AddrLong,
 166                            Value *ShadowValue, uint32_t TypeSize);
 167   Instruction *generateCrashCode(BasicBlock *BB, Value *Addr,
 168                                  bool IsWrite, size_t AccessSizeIndex);
 169   bool instrumentMemIntrinsic(AsanFunctionContext &AFC, MemIntrinsic *MI);
 170   void instrumentMemIntrinsicParam(AsanFunctionContext &AFC,
 171                                    Instruction *OrigIns, Value *Addr,
 172                                    Value *Size,
 173                                    Instruction *InsertBefore, bool IsWrite);
 174   Value *memToShadow(Value *Shadow, IRBuilder<> &IRB);
 175   bool handleFunction(Module &M, Function &F);
 176   bool maybeInsertAsanInitAtFunctionEntry(Function &F);
 177   bool poisonStackInFunction(Module &M, Function &F);
 178   virtual bool runOnModule(Module &M);
 179   bool insertGlobalRedzones(Module &M);
 180   static char ID;  // Pass identification, replacement for typeid
 181
 182  private:
 183
 184   uint64_t getAllocaSizeInBytes(AllocaInst *AI) {
 185     Type *Ty = AI->getAllocatedType();
 186     uint64_t SizeInBytes = TD->getTypeAllocSize(Ty);
 187     return SizeInBytes;
 188   }
 189   uint64_t getAlignedSize(uint64_t SizeInBytes) {
 190     return ((SizeInBytes + RedzoneSize - 1)
 191             / RedzoneSize) * RedzoneSize;
 192   }
 193   uint64_t getAlignedAllocaSize(AllocaInst *AI) {
 194     uint64_t SizeInBytes = getAllocaSizeInBytes(AI);
 195     return getAlignedSize(SizeInBytes);
 196   }
 197
 198   Function *checkInterfaceFunction(Constant *FuncOrBitcast);
 199   void PoisonStack(const ArrayRef<AllocaInst*> &AllocaVec, IRBuilder<> IRB,
 200                    Value *ShadowBase, bool DoPoison);
 201   bool LooksLikeCodeInBug11395(Instruction *I);
 202
 203   LLVMContext *C;
 204   TargetData *TD;
 205   uint64_t MappingOffset;
 206   int MappingScale;
 207   size_t RedzoneSize;
 208   int LongSize;
 209   Type *IntptrTy;
 210   Type *IntptrPtrTy;
 211   Function *AsanCtorFunction;
 212   Function *AsanInitFunction;
 213   Instruction *CtorInsertBefore;
 214   OwningPtr<FunctionBlackList> BL;
 215   // This array is indexed by AccessIsWrite and log2(AccessSize).
 216   Function *AsanErrorCallback[2][kNumberOfAccessSizes];
 217 };
 218
 219 }  // namespace
 220
 221 char AddressSanitizer::ID = 0;
 222 INITIALIZE_PASS(AddressSanitizer, "asan",
 223     "AddressSanitizer: detects use-after-free and out-of-bounds bugs.",
 224     false, false)
 225 AddressSanitizer::AddressSanitizer() : ModulePass(ID) { }
 226 ModulePass *llvm::createAddressSanitizerPass() {
 227   return new AddressSanitizer();
 228 }
 229
 230 const char *AddressSanitizer::getPassName() const {
 231   return "AddressSanitizer";
 232 }
 233
 234 static size_t TypeSizeToSizeIndex(uint32_t TypeSize) {
 235   size_t Res = CountTrailingZeros_32(TypeSize / 8);
 236   assert(Res < kNumberOfAccessSizes);
 237   return Res;
 238 }
 239
 240 // Create a constant for Str so that we can pass it to the run-time lib.
 241 static GlobalVariable *createPrivateGlobalForString(Module &M, StringRef Str) {
 242   Constant *StrConst = ConstantDataArray::getString(M.getContext(), Str);
 243   return new GlobalVariable(M, StrConst->getType(), true,
 244                             GlobalValue::PrivateLinkage, StrConst, "");
 245 }
 246
 247 // Split the basic block and insert an if-then code.
 248 // Before:
 249 //   Head
 250 //   Cmp
 251 //   Tail
 252 // After:
 253 //   Head
 254 //   if (Cmp)
 255 //     ThenBlock
 256 //   Tail
 257 //
 258 // If ThenBlock is zero, a new block is created and its terminator is returned.
 259 // Otherwize 0 is returned.
 260 static BranchInst *splitBlockAndInsertIfThen(Value *Cmp,
 261                                              BasicBlock *ThenBlock = 0) {
 262   Instruction *SplitBefore = cast<Instruction>(Cmp)->getNextNode();
 263   BasicBlock *Head = SplitBefore->getParent();
 264   BasicBlock *Tail = Head->splitBasicBlock(SplitBefore);
 265   TerminatorInst *HeadOldTerm = Head->getTerminator();
 266   BranchInst *CheckTerm = 0;
 267   if (!ThenBlock) {
 268     LLVMContext &C = Head->getParent()->getParent()->getContext();
 269     ThenBlock = BasicBlock::Create(C, "", Head->getParent());
 270     CheckTerm = BranchInst::Create(Tail, ThenBlock);
 271   }
 272   BranchInst *HeadNewTerm =
 273     BranchInst::Create(/*ifTrue*/ThenBlock, /*ifFalse*/Tail, Cmp);
 274   ReplaceInstWithInst(HeadOldTerm, HeadNewTerm);
 275
 276   return CheckTerm;
 277 }
 278
 279 Value *AddressSanitizer::memToShadow(Value *Shadow, IRBuilder<> &IRB) {
 280   // Shadow >> scale
 281   Shadow = IRB.CreateLShr(Shadow, MappingScale);
 282   if (MappingOffset == 0)
 283     return Shadow;
 284   // (Shadow >> scale) | offset
 285   return IRB.CreateOr(Shadow, ConstantInt::get(IntptrTy,
 286                                                MappingOffset));
 287 }
 288
 289 void AddressSanitizer::instrumentMemIntrinsicParam(
 290     AsanFunctionContext &AFC, Instruction *OrigIns,
 291     Value *Addr, Value *Size, Instruction *InsertBefore, bool IsWrite) {
 292   // Check the first byte.
 293   {
 294     IRBuilder<> IRB(InsertBefore);
 295     instrumentAddress(AFC, OrigIns, IRB, Addr, 8, IsWrite);
 296   }
 297   // Check the last byte.
 298   {
 299     IRBuilder<> IRB(InsertBefore);
 300     Value *SizeMinusOne = IRB.CreateSub(
 301         Size, ConstantInt::get(Size->getType(), 1));
 302     SizeMinusOne = IRB.CreateIntCast(SizeMinusOne, IntptrTy, false);
 303     Value *AddrLong = IRB.CreatePointerCast(Addr, IntptrTy);
 304     Value *AddrPlusSizeMinisOne = IRB.CreateAdd(AddrLong, SizeMinusOne);
 305     instrumentAddress(AFC, OrigIns, IRB, AddrPlusSizeMinisOne, 8, IsWrite);
 306   }
 307 }
 308
 309 // Instrument memset/memmove/memcpy
 310 bool AddressSanitizer::instrumentMemIntrinsic(AsanFunctionContext &AFC,
 311                                               MemIntrinsic *MI) {
 312   Value *Dst = MI->getDest();
 313   MemTransferInst *MemTran = dyn_cast<MemTransferInst>(MI);
 314   Value *Src = MemTran ? MemTran->getSource() : 0;
 315   Value *Length = MI->getLength();
 316
 317   Constant *ConstLength = dyn_cast<Constant>(Length);
 318   Instruction *InsertBefore = MI;
 319   if (ConstLength) {
 320     if (ConstLength->isNullValue()) return false;
 321   } else {
 322     // The size is not a constant so it could be zero -- check at run-time.
 323     IRBuilder<> IRB(InsertBefore);
 324
 325     Value *Cmp = IRB.CreateICmpNE(Length,
 326                                   Constant::getNullValue(Length->getType()));
 327     InsertBefore = splitBlockAndInsertIfThen(Cmp);
 328   }
 329
 330   instrumentMemIntrinsicParam(AFC, MI, Dst, Length, InsertBefore, true);
 331   if (Src)
 332     instrumentMemIntrinsicParam(AFC, MI, Src, Length, InsertBefore, false);
 333   return true;
 334 }
 335
 336 // If I is an interesting memory access, return the PointerOperand
 337 // and set IsWrite. Otherwise return NULL.
 338 static Value *isInterestingMemoryAccess(Instruction *I, bool *IsWrite) {
 339   if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
 340     if (!ClInstrumentReads) return NULL;
 341     *IsWrite = false;
 342     return LI->getPointerOperand();
 343   }
 344   if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
 345     if (!ClInstrumentWrites) return NULL;
 346     *IsWrite = true;
 347     return SI->getPointerOperand();
 348   }
 349   if (AtomicRMWInst *RMW = dyn_cast<AtomicRMWInst>(I)) {
 350     if (!ClInstrumentAtomics) return NULL;
 351     *IsWrite = true;
 352     return RMW->getPointerOperand();
 353   }
 354   if (AtomicCmpXchgInst *XCHG = dyn_cast<AtomicCmpXchgInst>(I)) {
 355     if (!ClInstrumentAtomics) return NULL;
 356     *IsWrite = true;
 357     return XCHG->getPointerOperand();
 358   }
 359   return NULL;
 360 }
 361
 362 void AddressSanitizer::instrumentMop(AsanFunctionContext &AFC, Instruction *I) {
 363   bool IsWrite;
 364   Value *Addr = isInterestingMemoryAccess(I, &IsWrite);
 365   assert(Addr);
 366   if (ClOpt && ClOptGlobals && isa<GlobalVariable>(Addr)) {
 367     // We are accessing a global scalar variable. Nothing to catch here.
 368     return;
 369   }
 370   Type *OrigPtrTy = Addr->getType();
 371   Type *OrigTy = cast<PointerType>(OrigPtrTy)->getElementType();
 372
 373   assert(OrigTy->isSized());
 374   uint32_t TypeSize = TD->getTypeStoreSizeInBits(OrigTy);
 375
 376   if (TypeSize != 8  && TypeSize != 16 &&
 377       TypeSize != 32 && TypeSize != 64 && TypeSize != 128) {
 378     // Ignore all unusual sizes.
 379     return;
 380   }
 381
 382   IRBuilder<> IRB(I);
 383   instrumentAddress(AFC, I, IRB, Addr, TypeSize, IsWrite);
 384 }
 385
 386 // Validate the result of Module::getOrInsertFunction called for an interface
 387 // function of AddressSanitizer. If the instrumented module defines a function
 388 // with the same name, their prototypes must match, otherwise
 389 // getOrInsertFunction returns a bitcast.
 390 Function *AddressSanitizer::checkInterfaceFunction(Constant *FuncOrBitcast) {
 391   if (isa<Function>(FuncOrBitcast)) return cast<Function>(FuncOrBitcast);
 392   FuncOrBitcast->dump();
 393   report_fatal_error("trying to redefine an AddressSanitizer "
 394                      "interface function");
 395 }
 396
 397 Instruction *AddressSanitizer::generateCrashCode(
 398     BasicBlock *BB, Value *Addr, bool IsWrite, size_t AccessSizeIndex) {
 399   IRBuilder<> IRB(BB->getFirstNonPHI());
 400   CallInst *Call = IRB.CreateCall(AsanErrorCallback[IsWrite][AccessSizeIndex],
 401                                   Addr);
 402   Call->setDoesNotReturn();
 403   return Call;
 404 }
 405
 406 Value *AddressSanitizer::createSlowPathCmp(IRBuilder<> &IRB, Value *AddrLong,
 407                                             Value *ShadowValue,
 408                                             uint32_t TypeSize) {
 409   size_t Granularity = 1 << MappingScale;
 410   // Addr & (Granularity - 1)
 411   Value *LastAccessedByte = IRB.CreateAnd(
 412       AddrLong, ConstantInt::get(IntptrTy, Granularity - 1));
 413   // (Addr & (Granularity - 1)) + size - 1
 414   if (TypeSize / 8 > 1)
 415     LastAccessedByte = IRB.CreateAdd(
 416         LastAccessedByte, ConstantInt::get(IntptrTy, TypeSize / 8 - 1));
 417   // (uint8_t) ((Addr & (Granularity-1)) + size - 1)
 418   LastAccessedByte = IRB.CreateIntCast(
 419       LastAccessedByte, IRB.getInt8Ty(), false);
 420   // ((uint8_t) ((Addr & (Granularity-1)) + size - 1)) >= ShadowValue
 421   return IRB.CreateICmpSGE(LastAccessedByte, ShadowValue);
 422 }
 423
 424 void AddressSanitizer::instrumentAddress(AsanFunctionContext &AFC,
 425                                          Instruction *OrigIns,
 426                                          IRBuilder<> &IRB, Value *Addr,
 427                                          uint32_t TypeSize, bool IsWrite) {
 428   Value *AddrLong = IRB.CreatePointerCast(Addr, IntptrTy);
 429
 430   Type *ShadowTy  = IntegerType::get(
 431       *C, std::max(8U, TypeSize >> MappingScale));
 432   Type *ShadowPtrTy = PointerType::get(ShadowTy, 0);
 433   Value *ShadowPtr = memToShadow(AddrLong, IRB);
 434   Value *CmpVal = Constant::getNullValue(ShadowTy);
 435   Value *ShadowValue = IRB.CreateLoad(
 436       IRB.CreateIntToPtr(ShadowPtr, ShadowPtrTy));
 437
 438   Value *Cmp = IRB.CreateICmpNE(ShadowValue, CmpVal);
 439
 440   BasicBlock *CrashBlock = 0;
 441   if (ClMergeCallbacks) {
 442     BasicBlock **Cached =
 443         &AFC.CrashBlock[IsWrite][TypeSizeToSizeIndex(TypeSize)];
 444     if (!*Cached) {
 445       BasicBlock *BB = BasicBlock::Create(*C, "crash_bb", &AFC.F);
 446       new UnreachableInst(*C, BB);
 447       *Cached = BB;
 448     }
 449     CrashBlock = *Cached;
 450   } else {
 451     CrashBlock = BasicBlock::Create(*C, "crash_bb", &AFC.F);
 452     new UnreachableInst(*C, CrashBlock);
 453     size_t AccessSizeIndex = TypeSizeToSizeIndex(TypeSize);
 454     Instruction *Crash =
 455         generateCrashCode(CrashBlock, AddrLong, IsWrite, AccessSizeIndex);
 456     Crash->setDebugLoc(OrigIns->getDebugLoc());
 457   }
 458
 459   size_t Granularity = 1 << MappingScale;
 460   if (TypeSize < 8 * Granularity) {
 461     Instruction *CheckTerm = splitBlockAndInsertIfThen(Cmp);
 462     IRB.SetInsertPoint(CheckTerm);
 463     Value *Cmp2 = createSlowPathCmp(IRB, AddrLong, ShadowValue, TypeSize);
 464     splitBlockAndInsertIfThen(Cmp2, CrashBlock);
 465   } else {
 466     splitBlockAndInsertIfThen(Cmp, CrashBlock);
 467   }
 468 }
 469
 470 // This function replaces all global variables with new variables that have
 471 // trailing redzones. It also creates a function that poisons
 472 // redzones and inserts this function into llvm.global_ctors.
 473 bool AddressSanitizer::insertGlobalRedzones(Module &M) {
 474   SmallVector<GlobalVariable *, 16> GlobalsToChange;
 475
 476   for (Module::GlobalListType::iterator G = M.getGlobalList().begin(),
 477        E = M.getGlobalList().end(); G != E; ++G) {
 478     Type *Ty = cast<PointerType>(G->getType())->getElementType();
 479     DEBUG(dbgs() << "GLOBAL: " << *G);
 480
 481     if (!Ty->isSized()) continue;
 482     if (!G->hasInitializer()) continue;
 483     // Touch only those globals that will not be defined in other modules.
 484     // Don't handle ODR type linkages since other modules may be built w/o asan.
 485     if (G->getLinkage() != GlobalVariable::ExternalLinkage &&
 486         G->getLinkage() != GlobalVariable::PrivateLinkage &&
 487         G->getLinkage() != GlobalVariable::InternalLinkage)
 488       continue;
 489     // Two problems with thread-locals:
 490     //   - The address of the main thread's copy can't be computed at link-time.
 491     //   - Need to poison all copies, not just the main thread's one.
 492     if (G->isThreadLocal())
 493       continue;
 494     // For now, just ignore this Alloca if the alignment is large.
 495     if (G->getAlignment() > RedzoneSize) continue;
 496
 497     // Ignore all the globals with the names starting with "\01L_OBJC_".
 498     // Many of those are put into the .cstring section. The linker compresses
 499     // that section by removing the spare \0s after the string terminator, so
 500     // our redzones get broken.
 501     if ((G->getName().find("\01L_OBJC_") == 0) ||
 502         (G->getName().find("\01l_OBJC_") == 0)) {
 503       DEBUG(dbgs() << "Ignoring \\01L_OBJC_* global: " << *G);
 504       continue;
 505     }
 506
 507     if (G->hasSection()) {
 508       StringRef Section(G->getSection());
 509       // Ignore the globals from the __OBJC section. The ObjC runtime assumes
 510       // those conform to /usr/lib/objc/runtime.h, so we can't add redzones to
 511       // them.
 512       if ((Section.find("__OBJC,") == 0) ||
 513           (Section.find("__DATA, __objc_") == 0)) {
 514         DEBUG(dbgs() << "Ignoring ObjC runtime global: " << *G);
 515         continue;
 516       }
 517       // See http://code.google.com/p/address-sanitizer/issues/detail?id=32
 518       // Constant CFString instances are compiled in the following way:
 519       //  -- the string buffer is emitted into
 520       //     __TEXT,__cstring,cstring_literals
 521       //  -- the constant NSConstantString structure referencing that buffer
 522       //     is placed into __DATA,__cfstring
 523       // Therefore there's no point in placing redzones into __DATA,__cfstring.
 524       // Moreover, it causes the linker to crash on OS X 10.7
 525       if (Section.find("__DATA,__cfstring") == 0) {
 526         DEBUG(dbgs() << "Ignoring CFString: " << *G);
 527         continue;
 528       }
 529     }
 530
 531     GlobalsToChange.push_back(G);
 532   }
 533
 534   size_t n = GlobalsToChange.size();
 535   if (n == 0) return false;
 536
 537   // A global is described by a structure
 538   //   size_t beg;
 539   //   size_t size;
 540   //   size_t size_with_redzone;
 541   //   const char *name;
 542   // We initialize an array of such structures and pass it to a run-time call.
 543   StructType *GlobalStructTy = StructType::get(IntptrTy, IntptrTy,
 544                                                IntptrTy, IntptrTy, NULL);
 545   SmallVector<Constant *, 16> Initializers(n);
 546
 547   IRBuilder<> IRB(CtorInsertBefore);
 548
 549   for (size_t i = 0; i < n; i++) {
 550     GlobalVariable *G = GlobalsToChange[i];
 551     PointerType *PtrTy = cast<PointerType>(G->getType());
 552     Type *Ty = PtrTy->getElementType();
 553     uint64_t SizeInBytes = TD->getTypeAllocSize(Ty);
 554     uint64_t RightRedzoneSize = RedzoneSize +
 555         (RedzoneSize - (SizeInBytes % RedzoneSize));
 556     Type *RightRedZoneTy = ArrayType::get(IRB.getInt8Ty(), RightRedzoneSize);
 557
 558     StructType *NewTy = StructType::get(Ty, RightRedZoneTy, NULL);
 559     Constant *NewInitializer = ConstantStruct::get(
 560         NewTy, G->getInitializer(),
 561         Constant::getNullValue(RightRedZoneTy), NULL);
 562
 563     SmallString<2048> DescriptionOfGlobal = G->getName();
 564     DescriptionOfGlobal += " (";
 565     DescriptionOfGlobal += M.getModuleIdentifier();
 566     DescriptionOfGlobal += ")";
 567     GlobalVariable *Name = createPrivateGlobalForString(M, DescriptionOfGlobal);
 568
 569     // Create a new global variable with enough space for a redzone.
 570     GlobalVariable *NewGlobal = new GlobalVariable(
 571         M, NewTy, G->isConstant(), G->getLinkage(),
 572         NewInitializer, "", G, G->getThreadLocalMode());
 573     NewGlobal->copyAttributesFrom(G);
 574     NewGlobal->setAlignment(RedzoneSize);
 575
 576     Value *Indices2[2];
 577     Indices2[0] = IRB.getInt32(0);
 578     Indices2[1] = IRB.getInt32(0);
 579
 580     G->replaceAllUsesWith(
 581         ConstantExpr::getGetElementPtr(NewGlobal, Indices2, true));
 582     NewGlobal->takeName(G);
 583     G->eraseFromParent();
 584
 585     Initializers[i] = ConstantStruct::get(
 586         GlobalStructTy,
 587         ConstantExpr::getPointerCast(NewGlobal, IntptrTy),
 588         ConstantInt::get(IntptrTy, SizeInBytes),
 589         ConstantInt::get(IntptrTy, SizeInBytes + RightRedzoneSize),
 590         ConstantExpr::getPointerCast(Name, IntptrTy),
 591         NULL);
 592     DEBUG(dbgs() << "NEW GLOBAL:\n" << *NewGlobal);
 593   }
 594
 595   ArrayType *ArrayOfGlobalStructTy = ArrayType::get(GlobalStructTy, n);
 596   GlobalVariable *AllGlobals = new GlobalVariable(
 597       M, ArrayOfGlobalStructTy, false, GlobalVariable::PrivateLinkage,
 598       ConstantArray::get(ArrayOfGlobalStructTy, Initializers), "");
 599
 600   Function *AsanRegisterGlobals = checkInterfaceFunction(M.getOrInsertFunction(
 601       kAsanRegisterGlobalsName, IRB.getVoidTy(), IntptrTy, IntptrTy, NULL));
 602   AsanRegisterGlobals->setLinkage(Function::ExternalLinkage);
 603
 604   IRB.CreateCall2(AsanRegisterGlobals,
 605                   IRB.CreatePointerCast(AllGlobals, IntptrTy),
 606                   ConstantInt::get(IntptrTy, n));
 607
 608   // We also need to unregister globals at the end, e.g. when a shared library
 609   // gets closed.
 610   Function *AsanDtorFunction = Function::Create(
 611       FunctionType::get(Type::getVoidTy(*C), false),
 612       GlobalValue::InternalLinkage, kAsanModuleDtorName, &M);
 613   BasicBlock *AsanDtorBB = BasicBlock::Create(*C, "", AsanDtorFunction);
 614   IRBuilder<> IRB_Dtor(ReturnInst::Create(*C, AsanDtorBB));
 615   Function *AsanUnregisterGlobals =
 616       checkInterfaceFunction(M.getOrInsertFunction(
 617           kAsanUnregisterGlobalsName,
 618           IRB.getVoidTy(), IntptrTy, IntptrTy, NULL));
 619   AsanUnregisterGlobals->setLinkage(Function::ExternalLinkage);
 620
 621   IRB_Dtor.CreateCall2(AsanUnregisterGlobals,
 622                        IRB.CreatePointerCast(AllGlobals, IntptrTy),
 623                        ConstantInt::get(IntptrTy, n));
 624   appendToGlobalDtors(M, AsanDtorFunction, kAsanCtorAndCtorPriority);
 625
 626   DEBUG(dbgs() << M);
 627   return true;
 628 }
 629
 630 // virtual
 631 bool AddressSanitizer::runOnModule(Module &M) {
 632   // Initialize the private fields. No one has accessed them before.
 633   TD = getAnalysisIfAvailable<TargetData>();
 634   if (!TD)
 635     return false;
 636   BL.reset(new FunctionBlackList(ClBlackListFile));
 637
 638   C = &(M.getContext());
 639   LongSize = TD->getPointerSizeInBits();
 640   IntptrTy = Type::getIntNTy(*C, LongSize);
 641   IntptrPtrTy = PointerType::get(IntptrTy, 0);
 642
 643   AsanCtorFunction = Function::Create(
 644       FunctionType::get(Type::getVoidTy(*C), false),
 645       GlobalValue::InternalLinkage, kAsanModuleCtorName, &M);
 646   BasicBlock *AsanCtorBB = BasicBlock::Create(*C, "", AsanCtorFunction);
 647   CtorInsertBefore = ReturnInst::Create(*C, AsanCtorBB);
 648
 649   // call __asan_init in the module ctor.
 650   IRBuilder<> IRB(CtorInsertBefore);
 651   AsanInitFunction = checkInterfaceFunction(
 652       M.getOrInsertFunction(kAsanInitName, IRB.getVoidTy(), NULL));
 653   AsanInitFunction->setLinkage(Function::ExternalLinkage);
 654   IRB.CreateCall(AsanInitFunction);
 655
 656   // Create __asan_report* callbacks.
 657   for (size_t AccessIsWrite = 0; AccessIsWrite <= 1; AccessIsWrite++) {
 658     for (size_t AccessSizeIndex = 0; AccessSizeIndex < kNumberOfAccessSizes;
 659          AccessSizeIndex++) {
 660       // IsWrite and TypeSize are encoded in the function name.
 661       std::string FunctionName = std::string(kAsanReportErrorTemplate) +
 662           (AccessIsWrite ? "store" : "load") + itostr(1 << AccessSizeIndex);
 663       AsanErrorCallback[AccessIsWrite][AccessSizeIndex] = cast<Function>(
 664         M.getOrInsertFunction(FunctionName, IRB.getVoidTy(), IntptrTy, NULL));
 665     }
 666   }
 667
 668   llvm::Triple targetTriple(M.getTargetTriple());
 669   bool isAndroid = targetTriple.getEnvironment() == llvm::Triple::ANDROIDEABI;
 670
 671   MappingOffset = isAndroid ? kDefaultShadowOffsetAndroid :
 672     (LongSize == 32 ? kDefaultShadowOffset32 : kDefaultShadowOffset64);
 673   if (ClMappingOffsetLog >= 0) {
 674     if (ClMappingOffsetLog == 0) {
 675       // special case
 676       MappingOffset = 0;
 677     } else {
 678       MappingOffset = 1ULL << ClMappingOffsetLog;
 679     }
 680   }
 681   MappingScale = kDefaultShadowScale;
 682   if (ClMappingScale) {
 683     MappingScale = ClMappingScale;
 684   }
 685   // Redzone used for stack and globals is at least 32 bytes.
 686   // For scales 6 and 7, the redzone has to be 64 and 128 bytes respectively.
 687   RedzoneSize = std::max(32, (int)(1 << MappingScale));
 688
 689   bool Res = false;
 690
 691   if (ClGlobals)
 692     Res |= insertGlobalRedzones(M);
 693
 694   if (ClMappingOffsetLog >= 0) {
 695     // Tell the run-time the current values of mapping offset and scale.
 696     GlobalValue *asan_mapping_offset =
 697         new GlobalVariable(M, IntptrTy, true, GlobalValue::LinkOnceODRLinkage,
 698                        ConstantInt::get(IntptrTy, MappingOffset),
 699                        kAsanMappingOffsetName);
 700     // Read the global, otherwise it may be optimized away.
 701     IRB.CreateLoad(asan_mapping_offset, true);
 702   }
 703   if (ClMappingScale) {
 704     GlobalValue *asan_mapping_scale =
 705         new GlobalVariable(M, IntptrTy, true, GlobalValue::LinkOnceODRLinkage,
 706                            ConstantInt::get(IntptrTy, MappingScale),
 707                            kAsanMappingScaleName);
 708     // Read the global, otherwise it may be optimized away.
 709     IRB.CreateLoad(asan_mapping_scale, true);
 710   }
 711
 712
 713   for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) {
 714     if (F->isDeclaration()) continue;
 715     Res |= handleFunction(M, *F);
 716   }
 717
 718   appendToGlobalCtors(M, AsanCtorFunction, kAsanCtorAndCtorPriority);
 719
 720   return Res;
 721 }
 722
 723 bool AddressSanitizer::maybeInsertAsanInitAtFunctionEntry(Function &F) {
 724   // For each NSObject descendant having a +load method, this method is invoked
 725   // by the ObjC runtime before any of the static constructors is called.
 726   // Therefore we need to instrument such methods with a call to __asan_init
 727   // at the beginning in order to initialize our runtime before any access to
 728   // the shadow memory.
 729   // We cannot just ignore these methods, because they may call other
 730   // instrumented functions.
 731   if (F.getName().find(" load]") != std::string::npos) {
 732     IRBuilder<> IRB(F.begin()->begin());
 733     IRB.CreateCall(AsanInitFunction);
 734     return true;
 735   }
 736   return false;
 737 }
 738
 739 bool AddressSanitizer::handleFunction(Module &M, Function &F) {
 740   if (BL->isIn(F)) return false;
 741   if (&F == AsanCtorFunction) return false;
 742
 743   // If needed, insert __asan_init before checking for AddressSafety attr.
 744   maybeInsertAsanInitAtFunctionEntry(F);
 745
 746   if (!F.hasFnAttr(Attribute::AddressSafety)) return false;
 747
 748   if (!ClDebugFunc.empty() && ClDebugFunc != F.getName())
 749     return false;
 750   // We want to instrument every address only once per basic block
 751   // (unless there are calls between uses).
 752   SmallSet<Value*, 16> TempsToInstrument;
 753   SmallVector<Instruction*, 16> ToInstrument;
 754   SmallVector<Instruction*, 8> NoReturnCalls;
 755   bool IsWrite;
 756
 757   // Fill the set of memory operations to instrument.
 758   for (Function::iterator FI = F.begin(), FE = F.end();
 759        FI != FE; ++FI) {
 760     TempsToInstrument.clear();
 761     int NumInsnsPerBB = 0;
 762     for (BasicBlock::iterator BI = FI->begin(), BE = FI->end();
 763          BI != BE; ++BI) {
 764       if (LooksLikeCodeInBug11395(BI)) return false;
 765       if (Value *Addr = isInterestingMemoryAccess(BI, &IsWrite)) {
 766         if (ClOpt && ClOptSameTemp) {
 767           if (!TempsToInstrument.insert(Addr))
 768             continue;  // We've seen this temp in the current BB.
 769         }
 770       } else if (isa<MemIntrinsic>(BI) && ClMemIntrin) {
 771         // ok, take it.
 772       } else {
 773         if (CallInst *CI = dyn_cast<CallInst>(BI)) {
 774           // A call inside BB.
 775           TempsToInstrument.clear();
 776           if (CI->doesNotReturn()) {
 777             NoReturnCalls.push_back(CI);
 778           }
 779         }
 780         continue;
 781       }
 782       ToInstrument.push_back(BI);
 783       NumInsnsPerBB++;
 784       if (NumInsnsPerBB >= ClMaxInsnsToInstrumentPerBB)
 785         break;
 786     }
 787   }
 788
 789   AsanFunctionContext AFC(F);
 790
 791   // Instrument.
 792   int NumInstrumented = 0;
 793   for (size_t i = 0, n = ToInstrument.size(); i != n; i++) {
 794     Instruction *Inst = ToInstrument[i];
 795     if (ClDebugMin < 0 || ClDebugMax < 0 ||
 796         (NumInstrumented >= ClDebugMin && NumInstrumented <= ClDebugMax)) {
 797       if (isInterestingMemoryAccess(Inst, &IsWrite))
 798         instrumentMop(AFC, Inst);
 799       else
 800         instrumentMemIntrinsic(AFC, cast<MemIntrinsic>(Inst));
 801     }
 802     NumInstrumented++;
 803   }
 804
 805   if (NumInstrumented) {
 806     for (size_t IsWrite = 0; IsWrite <= 1; IsWrite++) {
 807       for (size_t AccessSizeIndex = 0; AccessSizeIndex < kNumberOfAccessSizes;
 808            AccessSizeIndex++) {
 809         BasicBlock *BB = AFC.CrashBlock[IsWrite][AccessSizeIndex];
 810         if (!BB) continue;
 811         generateCrashCode(BB, ConstantInt::get(IntptrTy, 0),
 812                           IsWrite, AccessSizeIndex);
 813       }
 814     }
 815   }
 816
 817   DEBUG(dbgs() << F);
 818
 819   bool ChangedStack = poisonStackInFunction(M, F);
 820
 821   // We must unpoison the stack before every NoReturn call (throw, _exit, etc).
 822   // See e.g. http://code.google.com/p/address-sanitizer/issues/detail?id=37
 823   for (size_t i = 0, n = NoReturnCalls.size(); i != n; i++) {
 824     Instruction *CI = NoReturnCalls[i];
 825     IRBuilder<> IRB(CI);
 826     IRB.CreateCall(M.getOrInsertFunction(kAsanHandleNoReturnName,
 827                                          IRB.getVoidTy(), NULL));
 828   }
 829
 830   return NumInstrumented > 0 || ChangedStack || !NoReturnCalls.empty();
 831 }
 832
 833 static uint64_t ValueForPoison(uint64_t PoisonByte, size_t ShadowRedzoneSize) {
 834   if (ShadowRedzoneSize == 1) return PoisonByte;
 835   if (ShadowRedzoneSize == 2) return (PoisonByte << 8) + PoisonByte;
 836   if (ShadowRedzoneSize == 4)
 837     return (PoisonByte << 24) + (PoisonByte << 16) +
 838         (PoisonByte << 8) + (PoisonByte);
 839   llvm_unreachable("ShadowRedzoneSize is either 1, 2 or 4");
 840 }
 841
 842 static void PoisonShadowPartialRightRedzone(uint8_t *Shadow,
 843                                             size_t Size,
 844                                             size_t RedzoneSize,
 845                                             size_t ShadowGranularity,
 846                                             uint8_t Magic) {
 847   for (size_t i = 0; i < RedzoneSize;
 848        i+= ShadowGranularity, Shadow++) {
 849     if (i + ShadowGranularity <= Size) {
 850       *Shadow = 0;  // fully addressable
 851     } else if (i >= Size) {
 852       *Shadow = Magic;  // unaddressable
 853     } else {
 854       *Shadow = Size - i;  // first Size-i bytes are addressable
 855     }
 856   }
 857 }
 858
 859 void AddressSanitizer::PoisonStack(const ArrayRef<AllocaInst*> &AllocaVec,
 860                                    IRBuilder<> IRB,
 861                                    Value *ShadowBase, bool DoPoison) {
 862   size_t ShadowRZSize = RedzoneSize >> MappingScale;
 863   assert(ShadowRZSize >= 1 && ShadowRZSize <= 4);
 864   Type *RZTy = Type::getIntNTy(*C, ShadowRZSize * 8);
 865   Type *RZPtrTy = PointerType::get(RZTy, 0);
 866
 867   Value *PoisonLeft  = ConstantInt::get(RZTy,
 868     ValueForPoison(DoPoison ? kAsanStackLeftRedzoneMagic : 0LL, ShadowRZSize));
 869   Value *PoisonMid   = ConstantInt::get(RZTy,
 870     ValueForPoison(DoPoison ? kAsanStackMidRedzoneMagic : 0LL, ShadowRZSize));
 871   Value *PoisonRight = ConstantInt::get(RZTy,
 872     ValueForPoison(DoPoison ? kAsanStackRightRedzoneMagic : 0LL, ShadowRZSize));
 873
 874   // poison the first red zone.
 875   IRB.CreateStore(PoisonLeft, IRB.CreateIntToPtr(ShadowBase, RZPtrTy));
 876
 877   // poison all other red zones.
 878   uint64_t Pos = RedzoneSize;
 879   for (size_t i = 0, n = AllocaVec.size(); i < n; i++) {
 880     AllocaInst *AI = AllocaVec[i];
 881     uint64_t SizeInBytes = getAllocaSizeInBytes(AI);
 882     uint64_t AlignedSize = getAlignedAllocaSize(AI);
 883     assert(AlignedSize - SizeInBytes < RedzoneSize);
 884     Value *Ptr = NULL;
 885
 886     Pos += AlignedSize;
 887
 888     assert(ShadowBase->getType() == IntptrTy);
 889     if (SizeInBytes < AlignedSize) {
 890       // Poison the partial redzone at right
 891       Ptr = IRB.CreateAdd(
 892           ShadowBase, ConstantInt::get(IntptrTy,
 893                                        (Pos >> MappingScale) - ShadowRZSize));
 894       size_t AddressableBytes = RedzoneSize - (AlignedSize - SizeInBytes);
 895       uint32_t Poison = 0;
 896       if (DoPoison) {
 897         PoisonShadowPartialRightRedzone((uint8_t*)&Poison, AddressableBytes,
 898                                         RedzoneSize,
 899                                         1ULL << MappingScale,
 900                                         kAsanStackPartialRedzoneMagic);
 901       }
 902       Value *PartialPoison = ConstantInt::get(RZTy, Poison);
 903       IRB.CreateStore(PartialPoison, IRB.CreateIntToPtr(Ptr, RZPtrTy));
 904     }
 905
 906     // Poison the full redzone at right.
 907     Ptr = IRB.CreateAdd(ShadowBase,
 908                         ConstantInt::get(IntptrTy, Pos >> MappingScale));
 909     Value *Poison = i == AllocaVec.size() - 1 ? PoisonRight : PoisonMid;
 910     IRB.CreateStore(Poison, IRB.CreateIntToPtr(Ptr, RZPtrTy));
 911
 912     Pos += RedzoneSize;
 913   }
 914 }
 915
 916 // Workaround for bug 11395: we don't want to instrument stack in functions
 917 // with large assembly blobs (32-bit only), otherwise reg alloc may crash.
 918 // FIXME: remove once the bug 11395 is fixed.
 919 bool AddressSanitizer::LooksLikeCodeInBug11395(Instruction *I) {
 920   if (LongSize != 32) return false;
 921   CallInst *CI = dyn_cast<CallInst>(I);
 922   if (!CI || !CI->isInlineAsm()) return false;
 923   if (CI->getNumArgOperands() <= 5) return false;
 924   // We have inline assembly with quite a few arguments.
 925   return true;
 926 }
 927
 928 // Find all static Alloca instructions and put
 929 // poisoned red zones around all of them.
 930 // Then unpoison everything back before the function returns.
 931 //
 932 // Stack poisoning does not play well with exception handling.
 933 // When an exception is thrown, we essentially bypass the code
 934 // that unpoisones the stack. This is why the run-time library has
 935 // to intercept __cxa_throw (as well as longjmp, etc) and unpoison the entire
 936 // stack in the interceptor. This however does not work inside the
 937 // actual function which catches the exception. Most likely because the
 938 // compiler hoists the load of the shadow value somewhere too high.
 939 // This causes asan to report a non-existing bug on 453.povray.
 940 // It sounds like an LLVM bug.
 941 bool AddressSanitizer::poisonStackInFunction(Module &M, Function &F) {
 942   if (!ClStack) return false;
 943   SmallVector<AllocaInst*, 16> AllocaVec;
 944   SmallVector<Instruction*, 8> RetVec;
 945   uint64_t TotalSize = 0;
 946
 947   // Filter out Alloca instructions we want (and can) handle.
 948   // Collect Ret instructions.
 949   for (Function::iterator FI = F.begin(), FE = F.end();
 950        FI != FE; ++FI) {
 951     BasicBlock &BB = *FI;
 952     for (BasicBlock::iterator BI = BB.begin(), BE = BB.end();
 953          BI != BE; ++BI) {
 954       if (isa<ReturnInst>(BI)) {
 955           RetVec.push_back(BI);
 956           continue;
 957       }
 958
 959       AllocaInst *AI = dyn_cast<AllocaInst>(BI);
 960       if (!AI) continue;
 961       if (AI->isArrayAllocation()) continue;
 962       if (!AI->isStaticAlloca()) continue;
 963       if (!AI->getAllocatedType()->isSized()) continue;
 964       if (AI->getAlignment() > RedzoneSize) continue;
 965       AllocaVec.push_back(AI);
 966       uint64_t AlignedSize =  getAlignedAllocaSize(AI);
 967       TotalSize += AlignedSize;
 968     }
 969   }
 970
 971   if (AllocaVec.empty()) return false;
 972
 973   uint64_t LocalStackSize = TotalSize + (AllocaVec.size() + 1) * RedzoneSize;
 974
 975   bool DoStackMalloc = ClUseAfterReturn
 976       && LocalStackSize <= kMaxStackMallocSize;
 977
 978   Instruction *InsBefore = AllocaVec[0];
 979   IRBuilder<> IRB(InsBefore);
 980
 981
 982   Type *ByteArrayTy = ArrayType::get(IRB.getInt8Ty(), LocalStackSize);
 983   AllocaInst *MyAlloca =
 984       new AllocaInst(ByteArrayTy, "MyAlloca", InsBefore);
 985   MyAlloca->setAlignment(RedzoneSize);
 986   assert(MyAlloca->isStaticAlloca());
 987   Value *OrigStackBase = IRB.CreatePointerCast(MyAlloca, IntptrTy);
 988   Value *LocalStackBase = OrigStackBase;
 989
 990   if (DoStackMalloc) {
 991     Value *AsanStackMallocFunc = M.getOrInsertFunction(
 992         kAsanStackMallocName, IntptrTy, IntptrTy, IntptrTy, NULL);
 993     LocalStackBase = IRB.CreateCall2(AsanStackMallocFunc,
 994         ConstantInt::get(IntptrTy, LocalStackSize), OrigStackBase);
 995   }
 996
 997   // This string will be parsed by the run-time (DescribeStackAddress).
 998   SmallString<2048> StackDescriptionStorage;
 999   raw_svector_ostream StackDescription(StackDescriptionStorage);
1000   StackDescription << F.getName() << " " << AllocaVec.size() << " ";
1001
1002   uint64_t Pos = RedzoneSize;
1003   // Replace Alloca instructions with base+offset.
1004   for (size_t i = 0, n = AllocaVec.size(); i < n; i++) {
1005     AllocaInst *AI = AllocaVec[i];
1006     uint64_t SizeInBytes = getAllocaSizeInBytes(AI);
1007     StringRef Name = AI->getName();
1008     StackDescription << Pos << " " << SizeInBytes << " "
1009                      << Name.size() << " " << Name << " ";
1010     uint64_t AlignedSize = getAlignedAllocaSize(AI);
1011     assert((AlignedSize % RedzoneSize) == 0);
1012     AI->replaceAllUsesWith(
1013         IRB.CreateIntToPtr(
1014             IRB.CreateAdd(LocalStackBase, ConstantInt::get(IntptrTy, Pos)),
1015             AI->getType()));
1016     Pos += AlignedSize + RedzoneSize;
1017   }
1018   assert(Pos == LocalStackSize);
1019
1020   // Write the Magic value and the frame description constant to the redzone.
1021   Value *BasePlus0 = IRB.CreateIntToPtr(LocalStackBase, IntptrPtrTy);
1022   IRB.CreateStore(ConstantInt::get(IntptrTy, kCurrentStackFrameMagic),
1023                   BasePlus0);
1024   Value *BasePlus1 = IRB.CreateAdd(LocalStackBase,
1025                                    ConstantInt::get(IntptrTy, LongSize/8));
1026   BasePlus1 = IRB.CreateIntToPtr(BasePlus1, IntptrPtrTy);
1027   Value *Description = IRB.CreatePointerCast(
1028       createPrivateGlobalForString(M, StackDescription.str()),
1029       IntptrTy);
1030   IRB.CreateStore(Description, BasePlus1);
1031
1032   // Poison the stack redzones at the entry.
1033   Value *ShadowBase = memToShadow(LocalStackBase, IRB);
1034   PoisonStack(ArrayRef<AllocaInst*>(AllocaVec), IRB, ShadowBase, true);
1035
1036   Value *AsanStackFreeFunc = NULL;
1037   if (DoStackMalloc) {
1038     AsanStackFreeFunc = M.getOrInsertFunction(
1039         kAsanStackFreeName, IRB.getVoidTy(),
1040         IntptrTy, IntptrTy, IntptrTy, NULL);
1041   }
1042
1043   // Unpoison the stack before all ret instructions.
1044   for (size_t i = 0, n = RetVec.size(); i < n; i++) {
1045     Instruction *Ret = RetVec[i];
1046     IRBuilder<> IRBRet(Ret);
1047
1048     // Mark the current frame as retired.
1049     IRBRet.CreateStore(ConstantInt::get(IntptrTy, kRetiredStackFrameMagic),
1050                        BasePlus0);
1051     // Unpoison the stack.
1052     PoisonStack(ArrayRef<AllocaInst*>(AllocaVec), IRBRet, ShadowBase, false);
1053
1054     if (DoStackMalloc) {
1055       IRBRet.CreateCall3(AsanStackFreeFunc, LocalStackBase,
1056                          ConstantInt::get(IntptrTy, LocalStackSize),
1057                          OrigStackBase);
1058     }
1059   }
1060
1061   if (ClDebugStack) {
1062     DEBUG(dbgs() << F);
1063   }
1064
1065   return true;
1066 }