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