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