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