MemorySanitizer.cpp revision 36b56886974eae4f9c5ebc96befd3e7bfe5de338
1//===-- MemorySanitizer.cpp - detector of uninitialized reads -------------===// 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/// \file 10/// This file is a part of MemorySanitizer, a detector of uninitialized 11/// reads. 12/// 13/// Status: early prototype. 14/// 15/// The algorithm of the tool is similar to Memcheck 16/// (http://goo.gl/QKbem). We associate a few shadow bits with every 17/// byte of the application memory, poison the shadow of the malloc-ed 18/// or alloca-ed memory, load the shadow bits on every memory read, 19/// propagate the shadow bits through some of the arithmetic 20/// instruction (including MOV), store the shadow bits on every memory 21/// write, report a bug on some other instructions (e.g. JMP) if the 22/// associated shadow is poisoned. 23/// 24/// But there are differences too. The first and the major one: 25/// compiler instrumentation instead of binary instrumentation. This 26/// gives us much better register allocation, possible compiler 27/// optimizations and a fast start-up. But this brings the major issue 28/// as well: msan needs to see all program events, including system 29/// calls and reads/writes in system libraries, so we either need to 30/// compile *everything* with msan or use a binary translation 31/// component (e.g. DynamoRIO) to instrument pre-built libraries. 32/// Another difference from Memcheck is that we use 8 shadow bits per 33/// byte of application memory and use a direct shadow mapping. This 34/// greatly simplifies the instrumentation code and avoids races on 35/// shadow updates (Memcheck is single-threaded so races are not a 36/// concern there. Memcheck uses 2 shadow bits per byte with a slow 37/// path storage that uses 8 bits per byte). 38/// 39/// The default value of shadow is 0, which means "clean" (not poisoned). 40/// 41/// Every module initializer should call __msan_init to ensure that the 42/// shadow memory is ready. On error, __msan_warning is called. Since 43/// parameters and return values may be passed via registers, we have a 44/// specialized thread-local shadow for return values 45/// (__msan_retval_tls) and parameters (__msan_param_tls). 46/// 47/// Origin tracking. 48/// 49/// MemorySanitizer can track origins (allocation points) of all uninitialized 50/// values. This behavior is controlled with a flag (msan-track-origins) and is 51/// disabled by default. 52/// 53/// Origins are 4-byte values created and interpreted by the runtime library. 54/// They are stored in a second shadow mapping, one 4-byte value for 4 bytes 55/// of application memory. Propagation of origins is basically a bunch of 56/// "select" instructions that pick the origin of a dirty argument, if an 57/// instruction has one. 58/// 59/// Every 4 aligned, consecutive bytes of application memory have one origin 60/// value associated with them. If these bytes contain uninitialized data 61/// coming from 2 different allocations, the last store wins. Because of this, 62/// MemorySanitizer reports can show unrelated origins, but this is unlikely in 63/// practice. 64/// 65/// Origins are meaningless for fully initialized values, so MemorySanitizer 66/// avoids storing origin to memory when a fully initialized value is stored. 67/// This way it avoids needless overwritting origin of the 4-byte region on 68/// a short (i.e. 1 byte) clean store, and it is also good for performance. 69/// 70/// Atomic handling. 71/// 72/// Ideally, every atomic store of application value should update the 73/// corresponding shadow location in an atomic way. Unfortunately, atomic store 74/// of two disjoint locations can not be done without severe slowdown. 75/// 76/// Therefore, we implement an approximation that may err on the safe side. 77/// In this implementation, every atomically accessed location in the program 78/// may only change from (partially) uninitialized to fully initialized, but 79/// not the other way around. We load the shadow _after_ the application load, 80/// and we store the shadow _before_ the app store. Also, we always store clean 81/// shadow (if the application store is atomic). This way, if the store-load 82/// pair constitutes a happens-before arc, shadow store and load are correctly 83/// ordered such that the load will get either the value that was stored, or 84/// some later value (which is always clean). 85/// 86/// This does not work very well with Compare-And-Swap (CAS) and 87/// Read-Modify-Write (RMW) operations. To follow the above logic, CAS and RMW 88/// must store the new shadow before the app operation, and load the shadow 89/// after the app operation. Computers don't work this way. Current 90/// implementation ignores the load aspect of CAS/RMW, always returning a clean 91/// value. It implements the store part as a simple atomic store by storing a 92/// clean shadow. 93 94//===----------------------------------------------------------------------===// 95 96#define DEBUG_TYPE "msan" 97 98#include "llvm/Transforms/Instrumentation.h" 99#include "llvm/ADT/DepthFirstIterator.h" 100#include "llvm/ADT/SmallString.h" 101#include "llvm/ADT/SmallVector.h" 102#include "llvm/ADT/Triple.h" 103#include "llvm/IR/DataLayout.h" 104#include "llvm/IR/Function.h" 105#include "llvm/IR/IRBuilder.h" 106#include "llvm/IR/InlineAsm.h" 107#include "llvm/IR/InstVisitor.h" 108#include "llvm/IR/IntrinsicInst.h" 109#include "llvm/IR/LLVMContext.h" 110#include "llvm/IR/MDBuilder.h" 111#include "llvm/IR/Module.h" 112#include "llvm/IR/Type.h" 113#include "llvm/IR/ValueMap.h" 114#include "llvm/Support/CommandLine.h" 115#include "llvm/Support/Compiler.h" 116#include "llvm/Support/Debug.h" 117#include "llvm/Support/raw_ostream.h" 118#include "llvm/Transforms/Utils/BasicBlockUtils.h" 119#include "llvm/Transforms/Utils/Local.h" 120#include "llvm/Transforms/Utils/ModuleUtils.h" 121#include "llvm/Transforms/Utils/SpecialCaseList.h" 122 123using namespace llvm; 124 125static const uint64_t kShadowMask32 = 1ULL << 31; 126static const uint64_t kShadowMask64 = 1ULL << 46; 127static const uint64_t kOriginOffset32 = 1ULL << 30; 128static const uint64_t kOriginOffset64 = 1ULL << 45; 129static const unsigned kMinOriginAlignment = 4; 130static const unsigned kShadowTLSAlignment = 8; 131 132/// \brief Track origins of uninitialized values. 133/// 134/// Adds a section to MemorySanitizer report that points to the allocation 135/// (stack or heap) the uninitialized bits came from originally. 136static cl::opt<int> ClTrackOrigins("msan-track-origins", 137 cl::desc("Track origins (allocation sites) of poisoned memory"), 138 cl::Hidden, cl::init(0)); 139static cl::opt<bool> ClKeepGoing("msan-keep-going", 140 cl::desc("keep going after reporting a UMR"), 141 cl::Hidden, cl::init(false)); 142static cl::opt<bool> ClPoisonStack("msan-poison-stack", 143 cl::desc("poison uninitialized stack variables"), 144 cl::Hidden, cl::init(true)); 145static cl::opt<bool> ClPoisonStackWithCall("msan-poison-stack-with-call", 146 cl::desc("poison uninitialized stack variables with a call"), 147 cl::Hidden, cl::init(false)); 148static cl::opt<int> ClPoisonStackPattern("msan-poison-stack-pattern", 149 cl::desc("poison uninitialized stack variables with the given patter"), 150 cl::Hidden, cl::init(0xff)); 151static cl::opt<bool> ClPoisonUndef("msan-poison-undef", 152 cl::desc("poison undef temps"), 153 cl::Hidden, cl::init(true)); 154 155static cl::opt<bool> ClHandleICmp("msan-handle-icmp", 156 cl::desc("propagate shadow through ICmpEQ and ICmpNE"), 157 cl::Hidden, cl::init(true)); 158 159static cl::opt<bool> ClHandleICmpExact("msan-handle-icmp-exact", 160 cl::desc("exact handling of relational integer ICmp"), 161 cl::Hidden, cl::init(false)); 162 163// This flag controls whether we check the shadow of the address 164// operand of load or store. Such bugs are very rare, since load from 165// a garbage address typically results in SEGV, but still happen 166// (e.g. only lower bits of address are garbage, or the access happens 167// early at program startup where malloc-ed memory is more likely to 168// be zeroed. As of 2012-08-28 this flag adds 20% slowdown. 169static cl::opt<bool> ClCheckAccessAddress("msan-check-access-address", 170 cl::desc("report accesses through a pointer which has poisoned shadow"), 171 cl::Hidden, cl::init(true)); 172 173static cl::opt<bool> ClDumpStrictInstructions("msan-dump-strict-instructions", 174 cl::desc("print out instructions with default strict semantics"), 175 cl::Hidden, cl::init(false)); 176 177static cl::opt<std::string> ClBlacklistFile("msan-blacklist", 178 cl::desc("File containing the list of functions where MemorySanitizer " 179 "should not report bugs"), cl::Hidden); 180 181// Experimental. Wraps all indirect calls in the instrumented code with 182// a call to the given function. This is needed to assist the dynamic 183// helper tool (MSanDR) to regain control on transition between instrumented and 184// non-instrumented code. 185static cl::opt<std::string> ClWrapIndirectCalls("msan-wrap-indirect-calls", 186 cl::desc("Wrap indirect calls with a given function"), 187 cl::Hidden); 188 189static cl::opt<bool> ClWrapIndirectCallsFast("msan-wrap-indirect-calls-fast", 190 cl::desc("Do not wrap indirect calls with target in the same module"), 191 cl::Hidden, cl::init(true)); 192 193namespace { 194 195/// \brief An instrumentation pass implementing detection of uninitialized 196/// reads. 197/// 198/// MemorySanitizer: instrument the code in module to find 199/// uninitialized reads. 200class MemorySanitizer : public FunctionPass { 201 public: 202 MemorySanitizer(int TrackOrigins = 0, 203 StringRef BlacklistFile = StringRef()) 204 : FunctionPass(ID), 205 TrackOrigins(std::max(TrackOrigins, (int)ClTrackOrigins)), 206 DL(0), 207 WarningFn(0), 208 BlacklistFile(BlacklistFile.empty() ? ClBlacklistFile : BlacklistFile), 209 WrapIndirectCalls(!ClWrapIndirectCalls.empty()) {} 210 const char *getPassName() const override { return "MemorySanitizer"; } 211 bool runOnFunction(Function &F) override; 212 bool doInitialization(Module &M) override; 213 static char ID; // Pass identification, replacement for typeid. 214 215 private: 216 void initializeCallbacks(Module &M); 217 218 /// \brief Track origins (allocation points) of uninitialized values. 219 int TrackOrigins; 220 221 const DataLayout *DL; 222 LLVMContext *C; 223 Type *IntptrTy; 224 Type *OriginTy; 225 /// \brief Thread-local shadow storage for function parameters. 226 GlobalVariable *ParamTLS; 227 /// \brief Thread-local origin storage for function parameters. 228 GlobalVariable *ParamOriginTLS; 229 /// \brief Thread-local shadow storage for function return value. 230 GlobalVariable *RetvalTLS; 231 /// \brief Thread-local origin storage for function return value. 232 GlobalVariable *RetvalOriginTLS; 233 /// \brief Thread-local shadow storage for in-register va_arg function 234 /// parameters (x86_64-specific). 235 GlobalVariable *VAArgTLS; 236 /// \brief Thread-local shadow storage for va_arg overflow area 237 /// (x86_64-specific). 238 GlobalVariable *VAArgOverflowSizeTLS; 239 /// \brief Thread-local space used to pass origin value to the UMR reporting 240 /// function. 241 GlobalVariable *OriginTLS; 242 243 GlobalVariable *MsandrModuleStart; 244 GlobalVariable *MsandrModuleEnd; 245 246 /// \brief The run-time callback to print a warning. 247 Value *WarningFn; 248 /// \brief Run-time helper that generates a new origin value for a stack 249 /// allocation. 250 Value *MsanSetAllocaOrigin4Fn; 251 /// \brief Run-time helper that poisons stack on function entry. 252 Value *MsanPoisonStackFn; 253 /// \brief Run-time helper that records a store (or any event) of an 254 /// uninitialized value and returns an updated origin id encoding this info. 255 Value *MsanChainOriginFn; 256 /// \brief MSan runtime replacements for memmove, memcpy and memset. 257 Value *MemmoveFn, *MemcpyFn, *MemsetFn; 258 259 /// \brief Address mask used in application-to-shadow address calculation. 260 /// ShadowAddr is computed as ApplicationAddr & ~ShadowMask. 261 uint64_t ShadowMask; 262 /// \brief Offset of the origin shadow from the "normal" shadow. 263 /// OriginAddr is computed as (ShadowAddr + OriginOffset) & ~3ULL 264 uint64_t OriginOffset; 265 /// \brief Branch weights for error reporting. 266 MDNode *ColdCallWeights; 267 /// \brief Branch weights for origin store. 268 MDNode *OriginStoreWeights; 269 /// \brief Path to blacklist file. 270 SmallString<64> BlacklistFile; 271 /// \brief The blacklist. 272 std::unique_ptr<SpecialCaseList> BL; 273 /// \brief An empty volatile inline asm that prevents callback merge. 274 InlineAsm *EmptyAsm; 275 276 bool WrapIndirectCalls; 277 /// \brief Run-time wrapper for indirect calls. 278 Value *IndirectCallWrapperFn; 279 // Argument and return type of IndirectCallWrapperFn: void (*f)(void). 280 Type *AnyFunctionPtrTy; 281 282 friend struct MemorySanitizerVisitor; 283 friend struct VarArgAMD64Helper; 284}; 285} // namespace 286 287char MemorySanitizer::ID = 0; 288INITIALIZE_PASS(MemorySanitizer, "msan", 289 "MemorySanitizer: detects uninitialized reads.", 290 false, false) 291 292FunctionPass *llvm::createMemorySanitizerPass(int TrackOrigins, 293 StringRef BlacklistFile) { 294 return new MemorySanitizer(TrackOrigins, BlacklistFile); 295} 296 297/// \brief Create a non-const global initialized with the given string. 298/// 299/// Creates a writable global for Str so that we can pass it to the 300/// run-time lib. Runtime uses first 4 bytes of the string to store the 301/// frame ID, so the string needs to be mutable. 302static GlobalVariable *createPrivateNonConstGlobalForString(Module &M, 303 StringRef Str) { 304 Constant *StrConst = ConstantDataArray::getString(M.getContext(), Str); 305 return new GlobalVariable(M, StrConst->getType(), /*isConstant=*/false, 306 GlobalValue::PrivateLinkage, StrConst, ""); 307} 308 309 310/// \brief Insert extern declaration of runtime-provided functions and globals. 311void MemorySanitizer::initializeCallbacks(Module &M) { 312 // Only do this once. 313 if (WarningFn) 314 return; 315 316 IRBuilder<> IRB(*C); 317 // Create the callback. 318 // FIXME: this function should have "Cold" calling conv, 319 // which is not yet implemented. 320 StringRef WarningFnName = ClKeepGoing ? "__msan_warning" 321 : "__msan_warning_noreturn"; 322 WarningFn = M.getOrInsertFunction(WarningFnName, IRB.getVoidTy(), NULL); 323 324 MsanSetAllocaOrigin4Fn = M.getOrInsertFunction( 325 "__msan_set_alloca_origin4", IRB.getVoidTy(), IRB.getInt8PtrTy(), IntptrTy, 326 IRB.getInt8PtrTy(), IntptrTy, NULL); 327 MsanPoisonStackFn = M.getOrInsertFunction( 328 "__msan_poison_stack", IRB.getVoidTy(), IRB.getInt8PtrTy(), IntptrTy, NULL); 329 MsanChainOriginFn = M.getOrInsertFunction( 330 "__msan_chain_origin", IRB.getInt32Ty(), IRB.getInt32Ty(), NULL); 331 MemmoveFn = M.getOrInsertFunction( 332 "__msan_memmove", IRB.getInt8PtrTy(), IRB.getInt8PtrTy(), 333 IRB.getInt8PtrTy(), IntptrTy, NULL); 334 MemcpyFn = M.getOrInsertFunction( 335 "__msan_memcpy", IRB.getInt8PtrTy(), IRB.getInt8PtrTy(), IRB.getInt8PtrTy(), 336 IntptrTy, NULL); 337 MemsetFn = M.getOrInsertFunction( 338 "__msan_memset", IRB.getInt8PtrTy(), IRB.getInt8PtrTy(), IRB.getInt32Ty(), 339 IntptrTy, NULL); 340 341 // Create globals. 342 RetvalTLS = new GlobalVariable( 343 M, ArrayType::get(IRB.getInt64Ty(), 8), false, 344 GlobalVariable::ExternalLinkage, 0, "__msan_retval_tls", 0, 345 GlobalVariable::InitialExecTLSModel); 346 RetvalOriginTLS = new GlobalVariable( 347 M, OriginTy, false, GlobalVariable::ExternalLinkage, 0, 348 "__msan_retval_origin_tls", 0, GlobalVariable::InitialExecTLSModel); 349 350 ParamTLS = new GlobalVariable( 351 M, ArrayType::get(IRB.getInt64Ty(), 1000), false, 352 GlobalVariable::ExternalLinkage, 0, "__msan_param_tls", 0, 353 GlobalVariable::InitialExecTLSModel); 354 ParamOriginTLS = new GlobalVariable( 355 M, ArrayType::get(OriginTy, 1000), false, GlobalVariable::ExternalLinkage, 356 0, "__msan_param_origin_tls", 0, GlobalVariable::InitialExecTLSModel); 357 358 VAArgTLS = new GlobalVariable( 359 M, ArrayType::get(IRB.getInt64Ty(), 1000), false, 360 GlobalVariable::ExternalLinkage, 0, "__msan_va_arg_tls", 0, 361 GlobalVariable::InitialExecTLSModel); 362 VAArgOverflowSizeTLS = new GlobalVariable( 363 M, IRB.getInt64Ty(), false, GlobalVariable::ExternalLinkage, 0, 364 "__msan_va_arg_overflow_size_tls", 0, 365 GlobalVariable::InitialExecTLSModel); 366 OriginTLS = new GlobalVariable( 367 M, IRB.getInt32Ty(), false, GlobalVariable::ExternalLinkage, 0, 368 "__msan_origin_tls", 0, GlobalVariable::InitialExecTLSModel); 369 370 // We insert an empty inline asm after __msan_report* to avoid callback merge. 371 EmptyAsm = InlineAsm::get(FunctionType::get(IRB.getVoidTy(), false), 372 StringRef(""), StringRef(""), 373 /*hasSideEffects=*/true); 374 375 if (WrapIndirectCalls) { 376 AnyFunctionPtrTy = 377 PointerType::getUnqual(FunctionType::get(IRB.getVoidTy(), false)); 378 IndirectCallWrapperFn = M.getOrInsertFunction( 379 ClWrapIndirectCalls, AnyFunctionPtrTy, AnyFunctionPtrTy, NULL); 380 } 381 382 if (ClWrapIndirectCallsFast) { 383 MsandrModuleStart = new GlobalVariable( 384 M, IRB.getInt32Ty(), false, GlobalValue::ExternalLinkage, 385 0, "__executable_start"); 386 MsandrModuleStart->setVisibility(GlobalVariable::HiddenVisibility); 387 MsandrModuleEnd = new GlobalVariable( 388 M, IRB.getInt32Ty(), false, GlobalValue::ExternalLinkage, 389 0, "_end"); 390 MsandrModuleEnd->setVisibility(GlobalVariable::HiddenVisibility); 391 } 392} 393 394/// \brief Module-level initialization. 395/// 396/// inserts a call to __msan_init to the module's constructor list. 397bool MemorySanitizer::doInitialization(Module &M) { 398 DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>(); 399 if (!DLP) 400 return false; 401 DL = &DLP->getDataLayout(); 402 403 BL.reset(SpecialCaseList::createOrDie(BlacklistFile)); 404 C = &(M.getContext()); 405 unsigned PtrSize = DL->getPointerSizeInBits(/* AddressSpace */0); 406 switch (PtrSize) { 407 case 64: 408 ShadowMask = kShadowMask64; 409 OriginOffset = kOriginOffset64; 410 break; 411 case 32: 412 ShadowMask = kShadowMask32; 413 OriginOffset = kOriginOffset32; 414 break; 415 default: 416 report_fatal_error("unsupported pointer size"); 417 break; 418 } 419 420 IRBuilder<> IRB(*C); 421 IntptrTy = IRB.getIntPtrTy(DL); 422 OriginTy = IRB.getInt32Ty(); 423 424 ColdCallWeights = MDBuilder(*C).createBranchWeights(1, 1000); 425 OriginStoreWeights = MDBuilder(*C).createBranchWeights(1, 1000); 426 427 // Insert a call to __msan_init/__msan_track_origins into the module's CTORs. 428 appendToGlobalCtors(M, cast<Function>(M.getOrInsertFunction( 429 "__msan_init", IRB.getVoidTy(), NULL)), 0); 430 431 if (TrackOrigins) 432 new GlobalVariable(M, IRB.getInt32Ty(), true, GlobalValue::WeakODRLinkage, 433 IRB.getInt32(TrackOrigins), "__msan_track_origins"); 434 435 if (ClKeepGoing) 436 new GlobalVariable(M, IRB.getInt32Ty(), true, GlobalValue::WeakODRLinkage, 437 IRB.getInt32(ClKeepGoing), "__msan_keep_going"); 438 439 return true; 440} 441 442namespace { 443 444/// \brief A helper class that handles instrumentation of VarArg 445/// functions on a particular platform. 446/// 447/// Implementations are expected to insert the instrumentation 448/// necessary to propagate argument shadow through VarArg function 449/// calls. Visit* methods are called during an InstVisitor pass over 450/// the function, and should avoid creating new basic blocks. A new 451/// instance of this class is created for each instrumented function. 452struct VarArgHelper { 453 /// \brief Visit a CallSite. 454 virtual void visitCallSite(CallSite &CS, IRBuilder<> &IRB) = 0; 455 456 /// \brief Visit a va_start call. 457 virtual void visitVAStartInst(VAStartInst &I) = 0; 458 459 /// \brief Visit a va_copy call. 460 virtual void visitVACopyInst(VACopyInst &I) = 0; 461 462 /// \brief Finalize function instrumentation. 463 /// 464 /// This method is called after visiting all interesting (see above) 465 /// instructions in a function. 466 virtual void finalizeInstrumentation() = 0; 467 468 virtual ~VarArgHelper() {} 469}; 470 471struct MemorySanitizerVisitor; 472 473VarArgHelper* 474CreateVarArgHelper(Function &Func, MemorySanitizer &Msan, 475 MemorySanitizerVisitor &Visitor); 476 477/// This class does all the work for a given function. Store and Load 478/// instructions store and load corresponding shadow and origin 479/// values. Most instructions propagate shadow from arguments to their 480/// return values. Certain instructions (most importantly, BranchInst) 481/// test their argument shadow and print reports (with a runtime call) if it's 482/// non-zero. 483struct MemorySanitizerVisitor : public InstVisitor<MemorySanitizerVisitor> { 484 Function &F; 485 MemorySanitizer &MS; 486 SmallVector<PHINode *, 16> ShadowPHINodes, OriginPHINodes; 487 ValueMap<Value*, Value*> ShadowMap, OriginMap; 488 std::unique_ptr<VarArgHelper> VAHelper; 489 490 // The following flags disable parts of MSan instrumentation based on 491 // blacklist contents and command-line options. 492 bool InsertChecks; 493 bool LoadShadow; 494 bool PoisonStack; 495 bool PoisonUndef; 496 bool CheckReturnValue; 497 498 struct ShadowOriginAndInsertPoint { 499 Value *Shadow; 500 Value *Origin; 501 Instruction *OrigIns; 502 ShadowOriginAndInsertPoint(Value *S, Value *O, Instruction *I) 503 : Shadow(S), Origin(O), OrigIns(I) { } 504 }; 505 SmallVector<ShadowOriginAndInsertPoint, 16> InstrumentationList; 506 SmallVector<Instruction*, 16> StoreList; 507 SmallVector<CallSite, 16> IndirectCallList; 508 509 MemorySanitizerVisitor(Function &F, MemorySanitizer &MS) 510 : F(F), MS(MS), VAHelper(CreateVarArgHelper(F, MS, *this)) { 511 bool SanitizeFunction = !MS.BL->isIn(F) && F.getAttributes().hasAttribute( 512 AttributeSet::FunctionIndex, 513 Attribute::SanitizeMemory); 514 InsertChecks = SanitizeFunction; 515 LoadShadow = SanitizeFunction; 516 PoisonStack = SanitizeFunction && ClPoisonStack; 517 PoisonUndef = SanitizeFunction && ClPoisonUndef; 518 // FIXME: Consider using SpecialCaseList to specify a list of functions that 519 // must always return fully initialized values. For now, we hardcode "main". 520 CheckReturnValue = SanitizeFunction && (F.getName() == "main"); 521 522 DEBUG(if (!InsertChecks) 523 dbgs() << "MemorySanitizer is not inserting checks into '" 524 << F.getName() << "'\n"); 525 } 526 527 Value *updateOrigin(Value *V, IRBuilder<> &IRB) { 528 if (MS.TrackOrigins <= 1) return V; 529 return IRB.CreateCall(MS.MsanChainOriginFn, V); 530 } 531 532 void materializeStores() { 533 for (size_t i = 0, n = StoreList.size(); i < n; i++) { 534 StoreInst& I = *dyn_cast<StoreInst>(StoreList[i]); 535 536 IRBuilder<> IRB(&I); 537 Value *Val = I.getValueOperand(); 538 Value *Addr = I.getPointerOperand(); 539 Value *Shadow = I.isAtomic() ? getCleanShadow(Val) : getShadow(Val); 540 Value *ShadowPtr = getShadowPtr(Addr, Shadow->getType(), IRB); 541 542 StoreInst *NewSI = 543 IRB.CreateAlignedStore(Shadow, ShadowPtr, I.getAlignment()); 544 DEBUG(dbgs() << " STORE: " << *NewSI << "\n"); 545 (void)NewSI; 546 547 if (ClCheckAccessAddress) 548 insertShadowCheck(Addr, &I); 549 550 if (I.isAtomic()) 551 I.setOrdering(addReleaseOrdering(I.getOrdering())); 552 553 if (MS.TrackOrigins) { 554 unsigned Alignment = std::max(kMinOriginAlignment, I.getAlignment()); 555 if (isa<StructType>(Shadow->getType())) { 556 IRB.CreateAlignedStore(updateOrigin(getOrigin(Val), IRB), 557 getOriginPtr(Addr, IRB), Alignment); 558 } else { 559 Value *ConvertedShadow = convertToShadowTyNoVec(Shadow, IRB); 560 561 // TODO(eugenis): handle non-zero constant shadow by inserting an 562 // unconditional check (can not simply fail compilation as this could 563 // be in the dead code). 564 if (isa<Constant>(ConvertedShadow)) 565 continue; 566 567 Value *Cmp = IRB.CreateICmpNE(ConvertedShadow, 568 getCleanShadow(ConvertedShadow), "_mscmp"); 569 Instruction *CheckTerm = 570 SplitBlockAndInsertIfThen(Cmp, &I, false, MS.OriginStoreWeights); 571 IRBuilder<> IRBNew(CheckTerm); 572 IRBNew.CreateAlignedStore(updateOrigin(getOrigin(Val), IRBNew), 573 getOriginPtr(Addr, IRBNew), Alignment); 574 } 575 } 576 } 577 } 578 579 void materializeChecks() { 580 for (size_t i = 0, n = InstrumentationList.size(); i < n; i++) { 581 Value *Shadow = InstrumentationList[i].Shadow; 582 Instruction *OrigIns = InstrumentationList[i].OrigIns; 583 IRBuilder<> IRB(OrigIns); 584 DEBUG(dbgs() << " SHAD0 : " << *Shadow << "\n"); 585 Value *ConvertedShadow = convertToShadowTyNoVec(Shadow, IRB); 586 DEBUG(dbgs() << " SHAD1 : " << *ConvertedShadow << "\n"); 587 // See the comment in materializeStores(). 588 if (isa<Constant>(ConvertedShadow)) 589 continue; 590 Value *Cmp = IRB.CreateICmpNE(ConvertedShadow, 591 getCleanShadow(ConvertedShadow), "_mscmp"); 592 Instruction *CheckTerm = SplitBlockAndInsertIfThen( 593 Cmp, OrigIns, 594 /* Unreachable */ !ClKeepGoing, MS.ColdCallWeights); 595 596 IRB.SetInsertPoint(CheckTerm); 597 if (MS.TrackOrigins) { 598 Value *Origin = InstrumentationList[i].Origin; 599 IRB.CreateStore(Origin ? (Value*)Origin : (Value*)IRB.getInt32(0), 600 MS.OriginTLS); 601 } 602 IRB.CreateCall(MS.WarningFn); 603 IRB.CreateCall(MS.EmptyAsm); 604 DEBUG(dbgs() << " CHECK: " << *Cmp << "\n"); 605 } 606 DEBUG(dbgs() << "DONE:\n" << F); 607 } 608 609 void materializeIndirectCalls() { 610 for (size_t i = 0, n = IndirectCallList.size(); i < n; i++) { 611 CallSite CS = IndirectCallList[i]; 612 Instruction *I = CS.getInstruction(); 613 BasicBlock *B = I->getParent(); 614 IRBuilder<> IRB(I); 615 Value *Fn0 = CS.getCalledValue(); 616 Value *Fn = IRB.CreateBitCast(Fn0, MS.AnyFunctionPtrTy); 617 618 if (ClWrapIndirectCallsFast) { 619 // Check that call target is inside this module limits. 620 Value *Start = 621 IRB.CreateBitCast(MS.MsandrModuleStart, MS.AnyFunctionPtrTy); 622 Value *End = IRB.CreateBitCast(MS.MsandrModuleEnd, MS.AnyFunctionPtrTy); 623 624 Value *NotInThisModule = IRB.CreateOr(IRB.CreateICmpULT(Fn, Start), 625 IRB.CreateICmpUGE(Fn, End)); 626 627 PHINode *NewFnPhi = 628 IRB.CreatePHI(Fn0->getType(), 2, "msandr.indirect_target"); 629 630 Instruction *CheckTerm = SplitBlockAndInsertIfThen( 631 NotInThisModule, NewFnPhi, 632 /* Unreachable */ false, MS.ColdCallWeights); 633 634 IRB.SetInsertPoint(CheckTerm); 635 // Slow path: call wrapper function to possibly transform the call 636 // target. 637 Value *NewFn = IRB.CreateBitCast( 638 IRB.CreateCall(MS.IndirectCallWrapperFn, Fn), Fn0->getType()); 639 640 NewFnPhi->addIncoming(Fn0, B); 641 NewFnPhi->addIncoming(NewFn, dyn_cast<Instruction>(NewFn)->getParent()); 642 CS.setCalledFunction(NewFnPhi); 643 } else { 644 Value *NewFn = IRB.CreateBitCast( 645 IRB.CreateCall(MS.IndirectCallWrapperFn, Fn), Fn0->getType()); 646 CS.setCalledFunction(NewFn); 647 } 648 } 649 } 650 651 /// \brief Add MemorySanitizer instrumentation to a function. 652 bool runOnFunction() { 653 MS.initializeCallbacks(*F.getParent()); 654 if (!MS.DL) return false; 655 656 // In the presence of unreachable blocks, we may see Phi nodes with 657 // incoming nodes from such blocks. Since InstVisitor skips unreachable 658 // blocks, such nodes will not have any shadow value associated with them. 659 // It's easier to remove unreachable blocks than deal with missing shadow. 660 removeUnreachableBlocks(F); 661 662 // Iterate all BBs in depth-first order and create shadow instructions 663 // for all instructions (where applicable). 664 // For PHI nodes we create dummy shadow PHIs which will be finalized later. 665 for (df_iterator<BasicBlock*> DI = df_begin(&F.getEntryBlock()), 666 DE = df_end(&F.getEntryBlock()); DI != DE; ++DI) { 667 BasicBlock *BB = *DI; 668 visit(*BB); 669 } 670 671 // Finalize PHI nodes. 672 for (size_t i = 0, n = ShadowPHINodes.size(); i < n; i++) { 673 PHINode *PN = ShadowPHINodes[i]; 674 PHINode *PNS = cast<PHINode>(getShadow(PN)); 675 PHINode *PNO = MS.TrackOrigins ? cast<PHINode>(getOrigin(PN)) : 0; 676 size_t NumValues = PN->getNumIncomingValues(); 677 for (size_t v = 0; v < NumValues; v++) { 678 PNS->addIncoming(getShadow(PN, v), PN->getIncomingBlock(v)); 679 if (PNO) 680 PNO->addIncoming(getOrigin(PN, v), PN->getIncomingBlock(v)); 681 } 682 } 683 684 VAHelper->finalizeInstrumentation(); 685 686 // Delayed instrumentation of StoreInst. 687 // This may add new checks to be inserted later. 688 materializeStores(); 689 690 // Insert shadow value checks. 691 materializeChecks(); 692 693 // Wrap indirect calls. 694 materializeIndirectCalls(); 695 696 return true; 697 } 698 699 /// \brief Compute the shadow type that corresponds to a given Value. 700 Type *getShadowTy(Value *V) { 701 return getShadowTy(V->getType()); 702 } 703 704 /// \brief Compute the shadow type that corresponds to a given Type. 705 Type *getShadowTy(Type *OrigTy) { 706 if (!OrigTy->isSized()) { 707 return 0; 708 } 709 // For integer type, shadow is the same as the original type. 710 // This may return weird-sized types like i1. 711 if (IntegerType *IT = dyn_cast<IntegerType>(OrigTy)) 712 return IT; 713 if (VectorType *VT = dyn_cast<VectorType>(OrigTy)) { 714 uint32_t EltSize = MS.DL->getTypeSizeInBits(VT->getElementType()); 715 return VectorType::get(IntegerType::get(*MS.C, EltSize), 716 VT->getNumElements()); 717 } 718 if (StructType *ST = dyn_cast<StructType>(OrigTy)) { 719 SmallVector<Type*, 4> Elements; 720 for (unsigned i = 0, n = ST->getNumElements(); i < n; i++) 721 Elements.push_back(getShadowTy(ST->getElementType(i))); 722 StructType *Res = StructType::get(*MS.C, Elements, ST->isPacked()); 723 DEBUG(dbgs() << "getShadowTy: " << *ST << " ===> " << *Res << "\n"); 724 return Res; 725 } 726 uint32_t TypeSize = MS.DL->getTypeSizeInBits(OrigTy); 727 return IntegerType::get(*MS.C, TypeSize); 728 } 729 730 /// \brief Flatten a vector type. 731 Type *getShadowTyNoVec(Type *ty) { 732 if (VectorType *vt = dyn_cast<VectorType>(ty)) 733 return IntegerType::get(*MS.C, vt->getBitWidth()); 734 return ty; 735 } 736 737 /// \brief Convert a shadow value to it's flattened variant. 738 Value *convertToShadowTyNoVec(Value *V, IRBuilder<> &IRB) { 739 Type *Ty = V->getType(); 740 Type *NoVecTy = getShadowTyNoVec(Ty); 741 if (Ty == NoVecTy) return V; 742 return IRB.CreateBitCast(V, NoVecTy); 743 } 744 745 /// \brief Compute the shadow address that corresponds to a given application 746 /// address. 747 /// 748 /// Shadow = Addr & ~ShadowMask. 749 Value *getShadowPtr(Value *Addr, Type *ShadowTy, 750 IRBuilder<> &IRB) { 751 Value *ShadowLong = 752 IRB.CreateAnd(IRB.CreatePointerCast(Addr, MS.IntptrTy), 753 ConstantInt::get(MS.IntptrTy, ~MS.ShadowMask)); 754 return IRB.CreateIntToPtr(ShadowLong, PointerType::get(ShadowTy, 0)); 755 } 756 757 /// \brief Compute the origin address that corresponds to a given application 758 /// address. 759 /// 760 /// OriginAddr = (ShadowAddr + OriginOffset) & ~3ULL 761 Value *getOriginPtr(Value *Addr, IRBuilder<> &IRB) { 762 Value *ShadowLong = 763 IRB.CreateAnd(IRB.CreatePointerCast(Addr, MS.IntptrTy), 764 ConstantInt::get(MS.IntptrTy, ~MS.ShadowMask)); 765 Value *Add = 766 IRB.CreateAdd(ShadowLong, 767 ConstantInt::get(MS.IntptrTy, MS.OriginOffset)); 768 Value *SecondAnd = 769 IRB.CreateAnd(Add, ConstantInt::get(MS.IntptrTy, ~3ULL)); 770 return IRB.CreateIntToPtr(SecondAnd, PointerType::get(IRB.getInt32Ty(), 0)); 771 } 772 773 /// \brief Compute the shadow address for a given function argument. 774 /// 775 /// Shadow = ParamTLS+ArgOffset. 776 Value *getShadowPtrForArgument(Value *A, IRBuilder<> &IRB, 777 int ArgOffset) { 778 Value *Base = IRB.CreatePointerCast(MS.ParamTLS, MS.IntptrTy); 779 Base = IRB.CreateAdd(Base, ConstantInt::get(MS.IntptrTy, ArgOffset)); 780 return IRB.CreateIntToPtr(Base, PointerType::get(getShadowTy(A), 0), 781 "_msarg"); 782 } 783 784 /// \brief Compute the origin address for a given function argument. 785 Value *getOriginPtrForArgument(Value *A, IRBuilder<> &IRB, 786 int ArgOffset) { 787 if (!MS.TrackOrigins) return 0; 788 Value *Base = IRB.CreatePointerCast(MS.ParamOriginTLS, MS.IntptrTy); 789 Base = IRB.CreateAdd(Base, ConstantInt::get(MS.IntptrTy, ArgOffset)); 790 return IRB.CreateIntToPtr(Base, PointerType::get(MS.OriginTy, 0), 791 "_msarg_o"); 792 } 793 794 /// \brief Compute the shadow address for a retval. 795 Value *getShadowPtrForRetval(Value *A, IRBuilder<> &IRB) { 796 Value *Base = IRB.CreatePointerCast(MS.RetvalTLS, MS.IntptrTy); 797 return IRB.CreateIntToPtr(Base, PointerType::get(getShadowTy(A), 0), 798 "_msret"); 799 } 800 801 /// \brief Compute the origin address for a retval. 802 Value *getOriginPtrForRetval(IRBuilder<> &IRB) { 803 // We keep a single origin for the entire retval. Might be too optimistic. 804 return MS.RetvalOriginTLS; 805 } 806 807 /// \brief Set SV to be the shadow value for V. 808 void setShadow(Value *V, Value *SV) { 809 assert(!ShadowMap.count(V) && "Values may only have one shadow"); 810 ShadowMap[V] = SV; 811 } 812 813 /// \brief Set Origin to be the origin value for V. 814 void setOrigin(Value *V, Value *Origin) { 815 if (!MS.TrackOrigins) return; 816 assert(!OriginMap.count(V) && "Values may only have one origin"); 817 DEBUG(dbgs() << "ORIGIN: " << *V << " ==> " << *Origin << "\n"); 818 OriginMap[V] = Origin; 819 } 820 821 /// \brief Create a clean shadow value for a given value. 822 /// 823 /// Clean shadow (all zeroes) means all bits of the value are defined 824 /// (initialized). 825 Constant *getCleanShadow(Value *V) { 826 Type *ShadowTy = getShadowTy(V); 827 if (!ShadowTy) 828 return 0; 829 return Constant::getNullValue(ShadowTy); 830 } 831 832 /// \brief Create a dirty shadow of a given shadow type. 833 Constant *getPoisonedShadow(Type *ShadowTy) { 834 assert(ShadowTy); 835 if (isa<IntegerType>(ShadowTy) || isa<VectorType>(ShadowTy)) 836 return Constant::getAllOnesValue(ShadowTy); 837 StructType *ST = cast<StructType>(ShadowTy); 838 SmallVector<Constant *, 4> Vals; 839 for (unsigned i = 0, n = ST->getNumElements(); i < n; i++) 840 Vals.push_back(getPoisonedShadow(ST->getElementType(i))); 841 return ConstantStruct::get(ST, Vals); 842 } 843 844 /// \brief Create a dirty shadow for a given value. 845 Constant *getPoisonedShadow(Value *V) { 846 Type *ShadowTy = getShadowTy(V); 847 if (!ShadowTy) 848 return 0; 849 return getPoisonedShadow(ShadowTy); 850 } 851 852 /// \brief Create a clean (zero) origin. 853 Value *getCleanOrigin() { 854 return Constant::getNullValue(MS.OriginTy); 855 } 856 857 /// \brief Get the shadow value for a given Value. 858 /// 859 /// This function either returns the value set earlier with setShadow, 860 /// or extracts if from ParamTLS (for function arguments). 861 Value *getShadow(Value *V) { 862 if (Instruction *I = dyn_cast<Instruction>(V)) { 863 // For instructions the shadow is already stored in the map. 864 Value *Shadow = ShadowMap[V]; 865 if (!Shadow) { 866 DEBUG(dbgs() << "No shadow: " << *V << "\n" << *(I->getParent())); 867 (void)I; 868 assert(Shadow && "No shadow for a value"); 869 } 870 return Shadow; 871 } 872 if (UndefValue *U = dyn_cast<UndefValue>(V)) { 873 Value *AllOnes = PoisonUndef ? getPoisonedShadow(V) : getCleanShadow(V); 874 DEBUG(dbgs() << "Undef: " << *U << " ==> " << *AllOnes << "\n"); 875 (void)U; 876 return AllOnes; 877 } 878 if (Argument *A = dyn_cast<Argument>(V)) { 879 // For arguments we compute the shadow on demand and store it in the map. 880 Value **ShadowPtr = &ShadowMap[V]; 881 if (*ShadowPtr) 882 return *ShadowPtr; 883 Function *F = A->getParent(); 884 IRBuilder<> EntryIRB(F->getEntryBlock().getFirstNonPHI()); 885 unsigned ArgOffset = 0; 886 for (Function::arg_iterator AI = F->arg_begin(), AE = F->arg_end(); 887 AI != AE; ++AI) { 888 if (!AI->getType()->isSized()) { 889 DEBUG(dbgs() << "Arg is not sized\n"); 890 continue; 891 } 892 unsigned Size = AI->hasByValAttr() 893 ? MS.DL->getTypeAllocSize(AI->getType()->getPointerElementType()) 894 : MS.DL->getTypeAllocSize(AI->getType()); 895 if (A == AI) { 896 Value *Base = getShadowPtrForArgument(AI, EntryIRB, ArgOffset); 897 if (AI->hasByValAttr()) { 898 // ByVal pointer itself has clean shadow. We copy the actual 899 // argument shadow to the underlying memory. 900 // Figure out maximal valid memcpy alignment. 901 unsigned ArgAlign = AI->getParamAlignment(); 902 if (ArgAlign == 0) { 903 Type *EltType = A->getType()->getPointerElementType(); 904 ArgAlign = MS.DL->getABITypeAlignment(EltType); 905 } 906 unsigned CopyAlign = std::min(ArgAlign, kShadowTLSAlignment); 907 Value *Cpy = EntryIRB.CreateMemCpy( 908 getShadowPtr(V, EntryIRB.getInt8Ty(), EntryIRB), Base, Size, 909 CopyAlign); 910 DEBUG(dbgs() << " ByValCpy: " << *Cpy << "\n"); 911 (void)Cpy; 912 *ShadowPtr = getCleanShadow(V); 913 } else { 914 *ShadowPtr = EntryIRB.CreateAlignedLoad(Base, kShadowTLSAlignment); 915 } 916 DEBUG(dbgs() << " ARG: " << *AI << " ==> " << 917 **ShadowPtr << "\n"); 918 if (MS.TrackOrigins) { 919 Value* OriginPtr = getOriginPtrForArgument(AI, EntryIRB, ArgOffset); 920 setOrigin(A, EntryIRB.CreateLoad(OriginPtr)); 921 } 922 } 923 ArgOffset += DataLayout::RoundUpAlignment(Size, kShadowTLSAlignment); 924 } 925 assert(*ShadowPtr && "Could not find shadow for an argument"); 926 return *ShadowPtr; 927 } 928 // For everything else the shadow is zero. 929 return getCleanShadow(V); 930 } 931 932 /// \brief Get the shadow for i-th argument of the instruction I. 933 Value *getShadow(Instruction *I, int i) { 934 return getShadow(I->getOperand(i)); 935 } 936 937 /// \brief Get the origin for a value. 938 Value *getOrigin(Value *V) { 939 if (!MS.TrackOrigins) return 0; 940 if (isa<Instruction>(V) || isa<Argument>(V)) { 941 Value *Origin = OriginMap[V]; 942 if (!Origin) { 943 DEBUG(dbgs() << "NO ORIGIN: " << *V << "\n"); 944 Origin = getCleanOrigin(); 945 } 946 return Origin; 947 } 948 return getCleanOrigin(); 949 } 950 951 /// \brief Get the origin for i-th argument of the instruction I. 952 Value *getOrigin(Instruction *I, int i) { 953 return getOrigin(I->getOperand(i)); 954 } 955 956 /// \brief Remember the place where a shadow check should be inserted. 957 /// 958 /// This location will be later instrumented with a check that will print a 959 /// UMR warning in runtime if the shadow value is not 0. 960 void insertShadowCheck(Value *Shadow, Value *Origin, Instruction *OrigIns) { 961 assert(Shadow); 962 if (!InsertChecks) return; 963#ifndef NDEBUG 964 Type *ShadowTy = Shadow->getType(); 965 assert((isa<IntegerType>(ShadowTy) || isa<VectorType>(ShadowTy)) && 966 "Can only insert checks for integer and vector shadow types"); 967#endif 968 InstrumentationList.push_back( 969 ShadowOriginAndInsertPoint(Shadow, Origin, OrigIns)); 970 } 971 972 /// \brief Remember the place where a shadow check should be inserted. 973 /// 974 /// This location will be later instrumented with a check that will print a 975 /// UMR warning in runtime if the value is not fully defined. 976 void insertShadowCheck(Value *Val, Instruction *OrigIns) { 977 assert(Val); 978 Instruction *Shadow = dyn_cast_or_null<Instruction>(getShadow(Val)); 979 if (!Shadow) return; 980 Instruction *Origin = dyn_cast_or_null<Instruction>(getOrigin(Val)); 981 insertShadowCheck(Shadow, Origin, OrigIns); 982 } 983 984 AtomicOrdering addReleaseOrdering(AtomicOrdering a) { 985 switch (a) { 986 case NotAtomic: 987 return NotAtomic; 988 case Unordered: 989 case Monotonic: 990 case Release: 991 return Release; 992 case Acquire: 993 case AcquireRelease: 994 return AcquireRelease; 995 case SequentiallyConsistent: 996 return SequentiallyConsistent; 997 } 998 llvm_unreachable("Unknown ordering"); 999 } 1000 1001 AtomicOrdering addAcquireOrdering(AtomicOrdering a) { 1002 switch (a) { 1003 case NotAtomic: 1004 return NotAtomic; 1005 case Unordered: 1006 case Monotonic: 1007 case Acquire: 1008 return Acquire; 1009 case Release: 1010 case AcquireRelease: 1011 return AcquireRelease; 1012 case SequentiallyConsistent: 1013 return SequentiallyConsistent; 1014 } 1015 llvm_unreachable("Unknown ordering"); 1016 } 1017 1018 // ------------------- Visitors. 1019 1020 /// \brief Instrument LoadInst 1021 /// 1022 /// Loads the corresponding shadow and (optionally) origin. 1023 /// Optionally, checks that the load address is fully defined. 1024 void visitLoadInst(LoadInst &I) { 1025 assert(I.getType()->isSized() && "Load type must have size"); 1026 IRBuilder<> IRB(I.getNextNode()); 1027 Type *ShadowTy = getShadowTy(&I); 1028 Value *Addr = I.getPointerOperand(); 1029 if (LoadShadow) { 1030 Value *ShadowPtr = getShadowPtr(Addr, ShadowTy, IRB); 1031 setShadow(&I, 1032 IRB.CreateAlignedLoad(ShadowPtr, I.getAlignment(), "_msld")); 1033 } else { 1034 setShadow(&I, getCleanShadow(&I)); 1035 } 1036 1037 if (ClCheckAccessAddress) 1038 insertShadowCheck(I.getPointerOperand(), &I); 1039 1040 if (I.isAtomic()) 1041 I.setOrdering(addAcquireOrdering(I.getOrdering())); 1042 1043 if (MS.TrackOrigins) { 1044 if (LoadShadow) { 1045 unsigned Alignment = std::max(kMinOriginAlignment, I.getAlignment()); 1046 setOrigin(&I, 1047 IRB.CreateAlignedLoad(getOriginPtr(Addr, IRB), Alignment)); 1048 } else { 1049 setOrigin(&I, getCleanOrigin()); 1050 } 1051 } 1052 } 1053 1054 /// \brief Instrument StoreInst 1055 /// 1056 /// Stores the corresponding shadow and (optionally) origin. 1057 /// Optionally, checks that the store address is fully defined. 1058 void visitStoreInst(StoreInst &I) { 1059 StoreList.push_back(&I); 1060 } 1061 1062 void handleCASOrRMW(Instruction &I) { 1063 assert(isa<AtomicRMWInst>(I) || isa<AtomicCmpXchgInst>(I)); 1064 1065 IRBuilder<> IRB(&I); 1066 Value *Addr = I.getOperand(0); 1067 Value *ShadowPtr = getShadowPtr(Addr, I.getType(), IRB); 1068 1069 if (ClCheckAccessAddress) 1070 insertShadowCheck(Addr, &I); 1071 1072 // Only test the conditional argument of cmpxchg instruction. 1073 // The other argument can potentially be uninitialized, but we can not 1074 // detect this situation reliably without possible false positives. 1075 if (isa<AtomicCmpXchgInst>(I)) 1076 insertShadowCheck(I.getOperand(1), &I); 1077 1078 IRB.CreateStore(getCleanShadow(&I), ShadowPtr); 1079 1080 setShadow(&I, getCleanShadow(&I)); 1081 } 1082 1083 void visitAtomicRMWInst(AtomicRMWInst &I) { 1084 handleCASOrRMW(I); 1085 I.setOrdering(addReleaseOrdering(I.getOrdering())); 1086 } 1087 1088 void visitAtomicCmpXchgInst(AtomicCmpXchgInst &I) { 1089 handleCASOrRMW(I); 1090 I.setSuccessOrdering(addReleaseOrdering(I.getSuccessOrdering())); 1091 } 1092 1093 // Vector manipulation. 1094 void visitExtractElementInst(ExtractElementInst &I) { 1095 insertShadowCheck(I.getOperand(1), &I); 1096 IRBuilder<> IRB(&I); 1097 setShadow(&I, IRB.CreateExtractElement(getShadow(&I, 0), I.getOperand(1), 1098 "_msprop")); 1099 setOrigin(&I, getOrigin(&I, 0)); 1100 } 1101 1102 void visitInsertElementInst(InsertElementInst &I) { 1103 insertShadowCheck(I.getOperand(2), &I); 1104 IRBuilder<> IRB(&I); 1105 setShadow(&I, IRB.CreateInsertElement(getShadow(&I, 0), getShadow(&I, 1), 1106 I.getOperand(2), "_msprop")); 1107 setOriginForNaryOp(I); 1108 } 1109 1110 void visitShuffleVectorInst(ShuffleVectorInst &I) { 1111 insertShadowCheck(I.getOperand(2), &I); 1112 IRBuilder<> IRB(&I); 1113 setShadow(&I, IRB.CreateShuffleVector(getShadow(&I, 0), getShadow(&I, 1), 1114 I.getOperand(2), "_msprop")); 1115 setOriginForNaryOp(I); 1116 } 1117 1118 // Casts. 1119 void visitSExtInst(SExtInst &I) { 1120 IRBuilder<> IRB(&I); 1121 setShadow(&I, IRB.CreateSExt(getShadow(&I, 0), I.getType(), "_msprop")); 1122 setOrigin(&I, getOrigin(&I, 0)); 1123 } 1124 1125 void visitZExtInst(ZExtInst &I) { 1126 IRBuilder<> IRB(&I); 1127 setShadow(&I, IRB.CreateZExt(getShadow(&I, 0), I.getType(), "_msprop")); 1128 setOrigin(&I, getOrigin(&I, 0)); 1129 } 1130 1131 void visitTruncInst(TruncInst &I) { 1132 IRBuilder<> IRB(&I); 1133 setShadow(&I, IRB.CreateTrunc(getShadow(&I, 0), I.getType(), "_msprop")); 1134 setOrigin(&I, getOrigin(&I, 0)); 1135 } 1136 1137 void visitBitCastInst(BitCastInst &I) { 1138 IRBuilder<> IRB(&I); 1139 setShadow(&I, IRB.CreateBitCast(getShadow(&I, 0), getShadowTy(&I))); 1140 setOrigin(&I, getOrigin(&I, 0)); 1141 } 1142 1143 void visitPtrToIntInst(PtrToIntInst &I) { 1144 IRBuilder<> IRB(&I); 1145 setShadow(&I, IRB.CreateIntCast(getShadow(&I, 0), getShadowTy(&I), false, 1146 "_msprop_ptrtoint")); 1147 setOrigin(&I, getOrigin(&I, 0)); 1148 } 1149 1150 void visitIntToPtrInst(IntToPtrInst &I) { 1151 IRBuilder<> IRB(&I); 1152 setShadow(&I, IRB.CreateIntCast(getShadow(&I, 0), getShadowTy(&I), false, 1153 "_msprop_inttoptr")); 1154 setOrigin(&I, getOrigin(&I, 0)); 1155 } 1156 1157 void visitFPToSIInst(CastInst& I) { handleShadowOr(I); } 1158 void visitFPToUIInst(CastInst& I) { handleShadowOr(I); } 1159 void visitSIToFPInst(CastInst& I) { handleShadowOr(I); } 1160 void visitUIToFPInst(CastInst& I) { handleShadowOr(I); } 1161 void visitFPExtInst(CastInst& I) { handleShadowOr(I); } 1162 void visitFPTruncInst(CastInst& I) { handleShadowOr(I); } 1163 1164 /// \brief Propagate shadow for bitwise AND. 1165 /// 1166 /// This code is exact, i.e. if, for example, a bit in the left argument 1167 /// is defined and 0, then neither the value not definedness of the 1168 /// corresponding bit in B don't affect the resulting shadow. 1169 void visitAnd(BinaryOperator &I) { 1170 IRBuilder<> IRB(&I); 1171 // "And" of 0 and a poisoned value results in unpoisoned value. 1172 // 1&1 => 1; 0&1 => 0; p&1 => p; 1173 // 1&0 => 0; 0&0 => 0; p&0 => 0; 1174 // 1&p => p; 0&p => 0; p&p => p; 1175 // S = (S1 & S2) | (V1 & S2) | (S1 & V2) 1176 Value *S1 = getShadow(&I, 0); 1177 Value *S2 = getShadow(&I, 1); 1178 Value *V1 = I.getOperand(0); 1179 Value *V2 = I.getOperand(1); 1180 if (V1->getType() != S1->getType()) { 1181 V1 = IRB.CreateIntCast(V1, S1->getType(), false); 1182 V2 = IRB.CreateIntCast(V2, S2->getType(), false); 1183 } 1184 Value *S1S2 = IRB.CreateAnd(S1, S2); 1185 Value *V1S2 = IRB.CreateAnd(V1, S2); 1186 Value *S1V2 = IRB.CreateAnd(S1, V2); 1187 setShadow(&I, IRB.CreateOr(S1S2, IRB.CreateOr(V1S2, S1V2))); 1188 setOriginForNaryOp(I); 1189 } 1190 1191 void visitOr(BinaryOperator &I) { 1192 IRBuilder<> IRB(&I); 1193 // "Or" of 1 and a poisoned value results in unpoisoned value. 1194 // 1|1 => 1; 0|1 => 1; p|1 => 1; 1195 // 1|0 => 1; 0|0 => 0; p|0 => p; 1196 // 1|p => 1; 0|p => p; p|p => p; 1197 // S = (S1 & S2) | (~V1 & S2) | (S1 & ~V2) 1198 Value *S1 = getShadow(&I, 0); 1199 Value *S2 = getShadow(&I, 1); 1200 Value *V1 = IRB.CreateNot(I.getOperand(0)); 1201 Value *V2 = IRB.CreateNot(I.getOperand(1)); 1202 if (V1->getType() != S1->getType()) { 1203 V1 = IRB.CreateIntCast(V1, S1->getType(), false); 1204 V2 = IRB.CreateIntCast(V2, S2->getType(), false); 1205 } 1206 Value *S1S2 = IRB.CreateAnd(S1, S2); 1207 Value *V1S2 = IRB.CreateAnd(V1, S2); 1208 Value *S1V2 = IRB.CreateAnd(S1, V2); 1209 setShadow(&I, IRB.CreateOr(S1S2, IRB.CreateOr(V1S2, S1V2))); 1210 setOriginForNaryOp(I); 1211 } 1212 1213 /// \brief Default propagation of shadow and/or origin. 1214 /// 1215 /// This class implements the general case of shadow propagation, used in all 1216 /// cases where we don't know and/or don't care about what the operation 1217 /// actually does. It converts all input shadow values to a common type 1218 /// (extending or truncating as necessary), and bitwise OR's them. 1219 /// 1220 /// This is much cheaper than inserting checks (i.e. requiring inputs to be 1221 /// fully initialized), and less prone to false positives. 1222 /// 1223 /// This class also implements the general case of origin propagation. For a 1224 /// Nary operation, result origin is set to the origin of an argument that is 1225 /// not entirely initialized. If there is more than one such arguments, the 1226 /// rightmost of them is picked. It does not matter which one is picked if all 1227 /// arguments are initialized. 1228 template <bool CombineShadow> 1229 class Combiner { 1230 Value *Shadow; 1231 Value *Origin; 1232 IRBuilder<> &IRB; 1233 MemorySanitizerVisitor *MSV; 1234 1235 public: 1236 Combiner(MemorySanitizerVisitor *MSV, IRBuilder<> &IRB) : 1237 Shadow(0), Origin(0), IRB(IRB), MSV(MSV) {} 1238 1239 /// \brief Add a pair of shadow and origin values to the mix. 1240 Combiner &Add(Value *OpShadow, Value *OpOrigin) { 1241 if (CombineShadow) { 1242 assert(OpShadow); 1243 if (!Shadow) 1244 Shadow = OpShadow; 1245 else { 1246 OpShadow = MSV->CreateShadowCast(IRB, OpShadow, Shadow->getType()); 1247 Shadow = IRB.CreateOr(Shadow, OpShadow, "_msprop"); 1248 } 1249 } 1250 1251 if (MSV->MS.TrackOrigins) { 1252 assert(OpOrigin); 1253 if (!Origin) { 1254 Origin = OpOrigin; 1255 } else { 1256 Value *FlatShadow = MSV->convertToShadowTyNoVec(OpShadow, IRB); 1257 Value *Cond = IRB.CreateICmpNE(FlatShadow, 1258 MSV->getCleanShadow(FlatShadow)); 1259 Origin = IRB.CreateSelect(Cond, OpOrigin, Origin); 1260 } 1261 } 1262 return *this; 1263 } 1264 1265 /// \brief Add an application value to the mix. 1266 Combiner &Add(Value *V) { 1267 Value *OpShadow = MSV->getShadow(V); 1268 Value *OpOrigin = MSV->MS.TrackOrigins ? MSV->getOrigin(V) : 0; 1269 return Add(OpShadow, OpOrigin); 1270 } 1271 1272 /// \brief Set the current combined values as the given instruction's shadow 1273 /// and origin. 1274 void Done(Instruction *I) { 1275 if (CombineShadow) { 1276 assert(Shadow); 1277 Shadow = MSV->CreateShadowCast(IRB, Shadow, MSV->getShadowTy(I)); 1278 MSV->setShadow(I, Shadow); 1279 } 1280 if (MSV->MS.TrackOrigins) { 1281 assert(Origin); 1282 MSV->setOrigin(I, Origin); 1283 } 1284 } 1285 }; 1286 1287 typedef Combiner<true> ShadowAndOriginCombiner; 1288 typedef Combiner<false> OriginCombiner; 1289 1290 /// \brief Propagate origin for arbitrary operation. 1291 void setOriginForNaryOp(Instruction &I) { 1292 if (!MS.TrackOrigins) return; 1293 IRBuilder<> IRB(&I); 1294 OriginCombiner OC(this, IRB); 1295 for (Instruction::op_iterator OI = I.op_begin(); OI != I.op_end(); ++OI) 1296 OC.Add(OI->get()); 1297 OC.Done(&I); 1298 } 1299 1300 size_t VectorOrPrimitiveTypeSizeInBits(Type *Ty) { 1301 assert(!(Ty->isVectorTy() && Ty->getScalarType()->isPointerTy()) && 1302 "Vector of pointers is not a valid shadow type"); 1303 return Ty->isVectorTy() ? 1304 Ty->getVectorNumElements() * Ty->getScalarSizeInBits() : 1305 Ty->getPrimitiveSizeInBits(); 1306 } 1307 1308 /// \brief Cast between two shadow types, extending or truncating as 1309 /// necessary. 1310 Value *CreateShadowCast(IRBuilder<> &IRB, Value *V, Type *dstTy, 1311 bool Signed = false) { 1312 Type *srcTy = V->getType(); 1313 if (dstTy->isIntegerTy() && srcTy->isIntegerTy()) 1314 return IRB.CreateIntCast(V, dstTy, Signed); 1315 if (dstTy->isVectorTy() && srcTy->isVectorTy() && 1316 dstTy->getVectorNumElements() == srcTy->getVectorNumElements()) 1317 return IRB.CreateIntCast(V, dstTy, Signed); 1318 size_t srcSizeInBits = VectorOrPrimitiveTypeSizeInBits(srcTy); 1319 size_t dstSizeInBits = VectorOrPrimitiveTypeSizeInBits(dstTy); 1320 Value *V1 = IRB.CreateBitCast(V, Type::getIntNTy(*MS.C, srcSizeInBits)); 1321 Value *V2 = 1322 IRB.CreateIntCast(V1, Type::getIntNTy(*MS.C, dstSizeInBits), Signed); 1323 return IRB.CreateBitCast(V2, dstTy); 1324 // TODO: handle struct types. 1325 } 1326 1327 /// \brief Cast an application value to the type of its own shadow. 1328 Value *CreateAppToShadowCast(IRBuilder<> &IRB, Value *V) { 1329 Type *ShadowTy = getShadowTy(V); 1330 if (V->getType() == ShadowTy) 1331 return V; 1332 if (V->getType()->isPtrOrPtrVectorTy()) 1333 return IRB.CreatePtrToInt(V, ShadowTy); 1334 else 1335 return IRB.CreateBitCast(V, ShadowTy); 1336 } 1337 1338 /// \brief Propagate shadow for arbitrary operation. 1339 void handleShadowOr(Instruction &I) { 1340 IRBuilder<> IRB(&I); 1341 ShadowAndOriginCombiner SC(this, IRB); 1342 for (Instruction::op_iterator OI = I.op_begin(); OI != I.op_end(); ++OI) 1343 SC.Add(OI->get()); 1344 SC.Done(&I); 1345 } 1346 1347 void visitFAdd(BinaryOperator &I) { handleShadowOr(I); } 1348 void visitFSub(BinaryOperator &I) { handleShadowOr(I); } 1349 void visitFMul(BinaryOperator &I) { handleShadowOr(I); } 1350 void visitAdd(BinaryOperator &I) { handleShadowOr(I); } 1351 void visitSub(BinaryOperator &I) { handleShadowOr(I); } 1352 void visitXor(BinaryOperator &I) { handleShadowOr(I); } 1353 void visitMul(BinaryOperator &I) { handleShadowOr(I); } 1354 1355 void handleDiv(Instruction &I) { 1356 IRBuilder<> IRB(&I); 1357 // Strict on the second argument. 1358 insertShadowCheck(I.getOperand(1), &I); 1359 setShadow(&I, getShadow(&I, 0)); 1360 setOrigin(&I, getOrigin(&I, 0)); 1361 } 1362 1363 void visitUDiv(BinaryOperator &I) { handleDiv(I); } 1364 void visitSDiv(BinaryOperator &I) { handleDiv(I); } 1365 void visitFDiv(BinaryOperator &I) { handleDiv(I); } 1366 void visitURem(BinaryOperator &I) { handleDiv(I); } 1367 void visitSRem(BinaryOperator &I) { handleDiv(I); } 1368 void visitFRem(BinaryOperator &I) { handleDiv(I); } 1369 1370 /// \brief Instrument == and != comparisons. 1371 /// 1372 /// Sometimes the comparison result is known even if some of the bits of the 1373 /// arguments are not. 1374 void handleEqualityComparison(ICmpInst &I) { 1375 IRBuilder<> IRB(&I); 1376 Value *A = I.getOperand(0); 1377 Value *B = I.getOperand(1); 1378 Value *Sa = getShadow(A); 1379 Value *Sb = getShadow(B); 1380 1381 // Get rid of pointers and vectors of pointers. 1382 // For ints (and vectors of ints), types of A and Sa match, 1383 // and this is a no-op. 1384 A = IRB.CreatePointerCast(A, Sa->getType()); 1385 B = IRB.CreatePointerCast(B, Sb->getType()); 1386 1387 // A == B <==> (C = A^B) == 0 1388 // A != B <==> (C = A^B) != 0 1389 // Sc = Sa | Sb 1390 Value *C = IRB.CreateXor(A, B); 1391 Value *Sc = IRB.CreateOr(Sa, Sb); 1392 // Now dealing with i = (C == 0) comparison (or C != 0, does not matter now) 1393 // Result is defined if one of the following is true 1394 // * there is a defined 1 bit in C 1395 // * C is fully defined 1396 // Si = !(C & ~Sc) && Sc 1397 Value *Zero = Constant::getNullValue(Sc->getType()); 1398 Value *MinusOne = Constant::getAllOnesValue(Sc->getType()); 1399 Value *Si = 1400 IRB.CreateAnd(IRB.CreateICmpNE(Sc, Zero), 1401 IRB.CreateICmpEQ( 1402 IRB.CreateAnd(IRB.CreateXor(Sc, MinusOne), C), Zero)); 1403 Si->setName("_msprop_icmp"); 1404 setShadow(&I, Si); 1405 setOriginForNaryOp(I); 1406 } 1407 1408 /// \brief Build the lowest possible value of V, taking into account V's 1409 /// uninitialized bits. 1410 Value *getLowestPossibleValue(IRBuilder<> &IRB, Value *A, Value *Sa, 1411 bool isSigned) { 1412 if (isSigned) { 1413 // Split shadow into sign bit and other bits. 1414 Value *SaOtherBits = IRB.CreateLShr(IRB.CreateShl(Sa, 1), 1); 1415 Value *SaSignBit = IRB.CreateXor(Sa, SaOtherBits); 1416 // Maximise the undefined shadow bit, minimize other undefined bits. 1417 return 1418 IRB.CreateOr(IRB.CreateAnd(A, IRB.CreateNot(SaOtherBits)), SaSignBit); 1419 } else { 1420 // Minimize undefined bits. 1421 return IRB.CreateAnd(A, IRB.CreateNot(Sa)); 1422 } 1423 } 1424 1425 /// \brief Build the highest possible value of V, taking into account V's 1426 /// uninitialized bits. 1427 Value *getHighestPossibleValue(IRBuilder<> &IRB, Value *A, Value *Sa, 1428 bool isSigned) { 1429 if (isSigned) { 1430 // Split shadow into sign bit and other bits. 1431 Value *SaOtherBits = IRB.CreateLShr(IRB.CreateShl(Sa, 1), 1); 1432 Value *SaSignBit = IRB.CreateXor(Sa, SaOtherBits); 1433 // Minimise the undefined shadow bit, maximise other undefined bits. 1434 return 1435 IRB.CreateOr(IRB.CreateAnd(A, IRB.CreateNot(SaSignBit)), SaOtherBits); 1436 } else { 1437 // Maximize undefined bits. 1438 return IRB.CreateOr(A, Sa); 1439 } 1440 } 1441 1442 /// \brief Instrument relational comparisons. 1443 /// 1444 /// This function does exact shadow propagation for all relational 1445 /// comparisons of integers, pointers and vectors of those. 1446 /// FIXME: output seems suboptimal when one of the operands is a constant 1447 void handleRelationalComparisonExact(ICmpInst &I) { 1448 IRBuilder<> IRB(&I); 1449 Value *A = I.getOperand(0); 1450 Value *B = I.getOperand(1); 1451 Value *Sa = getShadow(A); 1452 Value *Sb = getShadow(B); 1453 1454 // Get rid of pointers and vectors of pointers. 1455 // For ints (and vectors of ints), types of A and Sa match, 1456 // and this is a no-op. 1457 A = IRB.CreatePointerCast(A, Sa->getType()); 1458 B = IRB.CreatePointerCast(B, Sb->getType()); 1459 1460 // Let [a0, a1] be the interval of possible values of A, taking into account 1461 // its undefined bits. Let [b0, b1] be the interval of possible values of B. 1462 // Then (A cmp B) is defined iff (a0 cmp b1) == (a1 cmp b0). 1463 bool IsSigned = I.isSigned(); 1464 Value *S1 = IRB.CreateICmp(I.getPredicate(), 1465 getLowestPossibleValue(IRB, A, Sa, IsSigned), 1466 getHighestPossibleValue(IRB, B, Sb, IsSigned)); 1467 Value *S2 = IRB.CreateICmp(I.getPredicate(), 1468 getHighestPossibleValue(IRB, A, Sa, IsSigned), 1469 getLowestPossibleValue(IRB, B, Sb, IsSigned)); 1470 Value *Si = IRB.CreateXor(S1, S2); 1471 setShadow(&I, Si); 1472 setOriginForNaryOp(I); 1473 } 1474 1475 /// \brief Instrument signed relational comparisons. 1476 /// 1477 /// Handle (x<0) and (x>=0) comparisons (essentially, sign bit tests) by 1478 /// propagating the highest bit of the shadow. Everything else is delegated 1479 /// to handleShadowOr(). 1480 void handleSignedRelationalComparison(ICmpInst &I) { 1481 Constant *constOp0 = dyn_cast<Constant>(I.getOperand(0)); 1482 Constant *constOp1 = dyn_cast<Constant>(I.getOperand(1)); 1483 Value* op = NULL; 1484 CmpInst::Predicate pre = I.getPredicate(); 1485 if (constOp0 && constOp0->isNullValue() && 1486 (pre == CmpInst::ICMP_SGT || pre == CmpInst::ICMP_SLE)) { 1487 op = I.getOperand(1); 1488 } else if (constOp1 && constOp1->isNullValue() && 1489 (pre == CmpInst::ICMP_SLT || pre == CmpInst::ICMP_SGE)) { 1490 op = I.getOperand(0); 1491 } 1492 if (op) { 1493 IRBuilder<> IRB(&I); 1494 Value* Shadow = 1495 IRB.CreateICmpSLT(getShadow(op), getCleanShadow(op), "_msprop_icmpslt"); 1496 setShadow(&I, Shadow); 1497 setOrigin(&I, getOrigin(op)); 1498 } else { 1499 handleShadowOr(I); 1500 } 1501 } 1502 1503 void visitICmpInst(ICmpInst &I) { 1504 if (!ClHandleICmp) { 1505 handleShadowOr(I); 1506 return; 1507 } 1508 if (I.isEquality()) { 1509 handleEqualityComparison(I); 1510 return; 1511 } 1512 1513 assert(I.isRelational()); 1514 if (ClHandleICmpExact) { 1515 handleRelationalComparisonExact(I); 1516 return; 1517 } 1518 if (I.isSigned()) { 1519 handleSignedRelationalComparison(I); 1520 return; 1521 } 1522 1523 assert(I.isUnsigned()); 1524 if ((isa<Constant>(I.getOperand(0)) || isa<Constant>(I.getOperand(1)))) { 1525 handleRelationalComparisonExact(I); 1526 return; 1527 } 1528 1529 handleShadowOr(I); 1530 } 1531 1532 void visitFCmpInst(FCmpInst &I) { 1533 handleShadowOr(I); 1534 } 1535 1536 void handleShift(BinaryOperator &I) { 1537 IRBuilder<> IRB(&I); 1538 // If any of the S2 bits are poisoned, the whole thing is poisoned. 1539 // Otherwise perform the same shift on S1. 1540 Value *S1 = getShadow(&I, 0); 1541 Value *S2 = getShadow(&I, 1); 1542 Value *S2Conv = IRB.CreateSExt(IRB.CreateICmpNE(S2, getCleanShadow(S2)), 1543 S2->getType()); 1544 Value *V2 = I.getOperand(1); 1545 Value *Shift = IRB.CreateBinOp(I.getOpcode(), S1, V2); 1546 setShadow(&I, IRB.CreateOr(Shift, S2Conv)); 1547 setOriginForNaryOp(I); 1548 } 1549 1550 void visitShl(BinaryOperator &I) { handleShift(I); } 1551 void visitAShr(BinaryOperator &I) { handleShift(I); } 1552 void visitLShr(BinaryOperator &I) { handleShift(I); } 1553 1554 /// \brief Instrument llvm.memmove 1555 /// 1556 /// At this point we don't know if llvm.memmove will be inlined or not. 1557 /// If we don't instrument it and it gets inlined, 1558 /// our interceptor will not kick in and we will lose the memmove. 1559 /// If we instrument the call here, but it does not get inlined, 1560 /// we will memove the shadow twice: which is bad in case 1561 /// of overlapping regions. So, we simply lower the intrinsic to a call. 1562 /// 1563 /// Similar situation exists for memcpy and memset. 1564 void visitMemMoveInst(MemMoveInst &I) { 1565 IRBuilder<> IRB(&I); 1566 IRB.CreateCall3( 1567 MS.MemmoveFn, 1568 IRB.CreatePointerCast(I.getArgOperand(0), IRB.getInt8PtrTy()), 1569 IRB.CreatePointerCast(I.getArgOperand(1), IRB.getInt8PtrTy()), 1570 IRB.CreateIntCast(I.getArgOperand(2), MS.IntptrTy, false)); 1571 I.eraseFromParent(); 1572 } 1573 1574 // Similar to memmove: avoid copying shadow twice. 1575 // This is somewhat unfortunate as it may slowdown small constant memcpys. 1576 // FIXME: consider doing manual inline for small constant sizes and proper 1577 // alignment. 1578 void visitMemCpyInst(MemCpyInst &I) { 1579 IRBuilder<> IRB(&I); 1580 IRB.CreateCall3( 1581 MS.MemcpyFn, 1582 IRB.CreatePointerCast(I.getArgOperand(0), IRB.getInt8PtrTy()), 1583 IRB.CreatePointerCast(I.getArgOperand(1), IRB.getInt8PtrTy()), 1584 IRB.CreateIntCast(I.getArgOperand(2), MS.IntptrTy, false)); 1585 I.eraseFromParent(); 1586 } 1587 1588 // Same as memcpy. 1589 void visitMemSetInst(MemSetInst &I) { 1590 IRBuilder<> IRB(&I); 1591 IRB.CreateCall3( 1592 MS.MemsetFn, 1593 IRB.CreatePointerCast(I.getArgOperand(0), IRB.getInt8PtrTy()), 1594 IRB.CreateIntCast(I.getArgOperand(1), IRB.getInt32Ty(), false), 1595 IRB.CreateIntCast(I.getArgOperand(2), MS.IntptrTy, false)); 1596 I.eraseFromParent(); 1597 } 1598 1599 void visitVAStartInst(VAStartInst &I) { 1600 VAHelper->visitVAStartInst(I); 1601 } 1602 1603 void visitVACopyInst(VACopyInst &I) { 1604 VAHelper->visitVACopyInst(I); 1605 } 1606 1607 enum IntrinsicKind { 1608 IK_DoesNotAccessMemory, 1609 IK_OnlyReadsMemory, 1610 IK_WritesMemory 1611 }; 1612 1613 static IntrinsicKind getIntrinsicKind(Intrinsic::ID iid) { 1614 const int DoesNotAccessMemory = IK_DoesNotAccessMemory; 1615 const int OnlyReadsArgumentPointees = IK_OnlyReadsMemory; 1616 const int OnlyReadsMemory = IK_OnlyReadsMemory; 1617 const int OnlyAccessesArgumentPointees = IK_WritesMemory; 1618 const int UnknownModRefBehavior = IK_WritesMemory; 1619#define GET_INTRINSIC_MODREF_BEHAVIOR 1620#define ModRefBehavior IntrinsicKind 1621#include "llvm/IR/Intrinsics.gen" 1622#undef ModRefBehavior 1623#undef GET_INTRINSIC_MODREF_BEHAVIOR 1624 } 1625 1626 /// \brief Handle vector store-like intrinsics. 1627 /// 1628 /// Instrument intrinsics that look like a simple SIMD store: writes memory, 1629 /// has 1 pointer argument and 1 vector argument, returns void. 1630 bool handleVectorStoreIntrinsic(IntrinsicInst &I) { 1631 IRBuilder<> IRB(&I); 1632 Value* Addr = I.getArgOperand(0); 1633 Value *Shadow = getShadow(&I, 1); 1634 Value *ShadowPtr = getShadowPtr(Addr, Shadow->getType(), IRB); 1635 1636 // We don't know the pointer alignment (could be unaligned SSE store!). 1637 // Have to assume to worst case. 1638 IRB.CreateAlignedStore(Shadow, ShadowPtr, 1); 1639 1640 if (ClCheckAccessAddress) 1641 insertShadowCheck(Addr, &I); 1642 1643 // FIXME: use ClStoreCleanOrigin 1644 // FIXME: factor out common code from materializeStores 1645 if (MS.TrackOrigins) 1646 IRB.CreateStore(getOrigin(&I, 1), getOriginPtr(Addr, IRB)); 1647 return true; 1648 } 1649 1650 /// \brief Handle vector load-like intrinsics. 1651 /// 1652 /// Instrument intrinsics that look like a simple SIMD load: reads memory, 1653 /// has 1 pointer argument, returns a vector. 1654 bool handleVectorLoadIntrinsic(IntrinsicInst &I) { 1655 IRBuilder<> IRB(&I); 1656 Value *Addr = I.getArgOperand(0); 1657 1658 Type *ShadowTy = getShadowTy(&I); 1659 if (LoadShadow) { 1660 Value *ShadowPtr = getShadowPtr(Addr, ShadowTy, IRB); 1661 // We don't know the pointer alignment (could be unaligned SSE load!). 1662 // Have to assume to worst case. 1663 setShadow(&I, IRB.CreateAlignedLoad(ShadowPtr, 1, "_msld")); 1664 } else { 1665 setShadow(&I, getCleanShadow(&I)); 1666 } 1667 1668 if (ClCheckAccessAddress) 1669 insertShadowCheck(Addr, &I); 1670 1671 if (MS.TrackOrigins) { 1672 if (LoadShadow) 1673 setOrigin(&I, IRB.CreateLoad(getOriginPtr(Addr, IRB))); 1674 else 1675 setOrigin(&I, getCleanOrigin()); 1676 } 1677 return true; 1678 } 1679 1680 /// \brief Handle (SIMD arithmetic)-like intrinsics. 1681 /// 1682 /// Instrument intrinsics with any number of arguments of the same type, 1683 /// equal to the return type. The type should be simple (no aggregates or 1684 /// pointers; vectors are fine). 1685 /// Caller guarantees that this intrinsic does not access memory. 1686 bool maybeHandleSimpleNomemIntrinsic(IntrinsicInst &I) { 1687 Type *RetTy = I.getType(); 1688 if (!(RetTy->isIntOrIntVectorTy() || 1689 RetTy->isFPOrFPVectorTy() || 1690 RetTy->isX86_MMXTy())) 1691 return false; 1692 1693 unsigned NumArgOperands = I.getNumArgOperands(); 1694 1695 for (unsigned i = 0; i < NumArgOperands; ++i) { 1696 Type *Ty = I.getArgOperand(i)->getType(); 1697 if (Ty != RetTy) 1698 return false; 1699 } 1700 1701 IRBuilder<> IRB(&I); 1702 ShadowAndOriginCombiner SC(this, IRB); 1703 for (unsigned i = 0; i < NumArgOperands; ++i) 1704 SC.Add(I.getArgOperand(i)); 1705 SC.Done(&I); 1706 1707 return true; 1708 } 1709 1710 /// \brief Heuristically instrument unknown intrinsics. 1711 /// 1712 /// The main purpose of this code is to do something reasonable with all 1713 /// random intrinsics we might encounter, most importantly - SIMD intrinsics. 1714 /// We recognize several classes of intrinsics by their argument types and 1715 /// ModRefBehaviour and apply special intrumentation when we are reasonably 1716 /// sure that we know what the intrinsic does. 1717 /// 1718 /// We special-case intrinsics where this approach fails. See llvm.bswap 1719 /// handling as an example of that. 1720 bool handleUnknownIntrinsic(IntrinsicInst &I) { 1721 unsigned NumArgOperands = I.getNumArgOperands(); 1722 if (NumArgOperands == 0) 1723 return false; 1724 1725 Intrinsic::ID iid = I.getIntrinsicID(); 1726 IntrinsicKind IK = getIntrinsicKind(iid); 1727 bool OnlyReadsMemory = IK == IK_OnlyReadsMemory; 1728 bool WritesMemory = IK == IK_WritesMemory; 1729 assert(!(OnlyReadsMemory && WritesMemory)); 1730 1731 if (NumArgOperands == 2 && 1732 I.getArgOperand(0)->getType()->isPointerTy() && 1733 I.getArgOperand(1)->getType()->isVectorTy() && 1734 I.getType()->isVoidTy() && 1735 WritesMemory) { 1736 // This looks like a vector store. 1737 return handleVectorStoreIntrinsic(I); 1738 } 1739 1740 if (NumArgOperands == 1 && 1741 I.getArgOperand(0)->getType()->isPointerTy() && 1742 I.getType()->isVectorTy() && 1743 OnlyReadsMemory) { 1744 // This looks like a vector load. 1745 return handleVectorLoadIntrinsic(I); 1746 } 1747 1748 if (!OnlyReadsMemory && !WritesMemory) 1749 if (maybeHandleSimpleNomemIntrinsic(I)) 1750 return true; 1751 1752 // FIXME: detect and handle SSE maskstore/maskload 1753 return false; 1754 } 1755 1756 void handleBswap(IntrinsicInst &I) { 1757 IRBuilder<> IRB(&I); 1758 Value *Op = I.getArgOperand(0); 1759 Type *OpType = Op->getType(); 1760 Function *BswapFunc = Intrinsic::getDeclaration( 1761 F.getParent(), Intrinsic::bswap, ArrayRef<Type*>(&OpType, 1)); 1762 setShadow(&I, IRB.CreateCall(BswapFunc, getShadow(Op))); 1763 setOrigin(&I, getOrigin(Op)); 1764 } 1765 1766 // \brief Instrument vector convert instrinsic. 1767 // 1768 // This function instruments intrinsics like cvtsi2ss: 1769 // %Out = int_xxx_cvtyyy(%ConvertOp) 1770 // or 1771 // %Out = int_xxx_cvtyyy(%CopyOp, %ConvertOp) 1772 // Intrinsic converts \p NumUsedElements elements of \p ConvertOp to the same 1773 // number \p Out elements, and (if has 2 arguments) copies the rest of the 1774 // elements from \p CopyOp. 1775 // In most cases conversion involves floating-point value which may trigger a 1776 // hardware exception when not fully initialized. For this reason we require 1777 // \p ConvertOp[0:NumUsedElements] to be fully initialized and trap otherwise. 1778 // We copy the shadow of \p CopyOp[NumUsedElements:] to \p 1779 // Out[NumUsedElements:]. This means that intrinsics without \p CopyOp always 1780 // return a fully initialized value. 1781 void handleVectorConvertIntrinsic(IntrinsicInst &I, int NumUsedElements) { 1782 IRBuilder<> IRB(&I); 1783 Value *CopyOp, *ConvertOp; 1784 1785 switch (I.getNumArgOperands()) { 1786 case 2: 1787 CopyOp = I.getArgOperand(0); 1788 ConvertOp = I.getArgOperand(1); 1789 break; 1790 case 1: 1791 ConvertOp = I.getArgOperand(0); 1792 CopyOp = NULL; 1793 break; 1794 default: 1795 llvm_unreachable("Cvt intrinsic with unsupported number of arguments."); 1796 } 1797 1798 // The first *NumUsedElements* elements of ConvertOp are converted to the 1799 // same number of output elements. The rest of the output is copied from 1800 // CopyOp, or (if not available) filled with zeroes. 1801 // Combine shadow for elements of ConvertOp that are used in this operation, 1802 // and insert a check. 1803 // FIXME: consider propagating shadow of ConvertOp, at least in the case of 1804 // int->any conversion. 1805 Value *ConvertShadow = getShadow(ConvertOp); 1806 Value *AggShadow = 0; 1807 if (ConvertOp->getType()->isVectorTy()) { 1808 AggShadow = IRB.CreateExtractElement( 1809 ConvertShadow, ConstantInt::get(IRB.getInt32Ty(), 0)); 1810 for (int i = 1; i < NumUsedElements; ++i) { 1811 Value *MoreShadow = IRB.CreateExtractElement( 1812 ConvertShadow, ConstantInt::get(IRB.getInt32Ty(), i)); 1813 AggShadow = IRB.CreateOr(AggShadow, MoreShadow); 1814 } 1815 } else { 1816 AggShadow = ConvertShadow; 1817 } 1818 assert(AggShadow->getType()->isIntegerTy()); 1819 insertShadowCheck(AggShadow, getOrigin(ConvertOp), &I); 1820 1821 // Build result shadow by zero-filling parts of CopyOp shadow that come from 1822 // ConvertOp. 1823 if (CopyOp) { 1824 assert(CopyOp->getType() == I.getType()); 1825 assert(CopyOp->getType()->isVectorTy()); 1826 Value *ResultShadow = getShadow(CopyOp); 1827 Type *EltTy = ResultShadow->getType()->getVectorElementType(); 1828 for (int i = 0; i < NumUsedElements; ++i) { 1829 ResultShadow = IRB.CreateInsertElement( 1830 ResultShadow, ConstantInt::getNullValue(EltTy), 1831 ConstantInt::get(IRB.getInt32Ty(), i)); 1832 } 1833 setShadow(&I, ResultShadow); 1834 setOrigin(&I, getOrigin(CopyOp)); 1835 } else { 1836 setShadow(&I, getCleanShadow(&I)); 1837 } 1838 } 1839 1840 // Given a scalar or vector, extract lower 64 bits (or less), and return all 1841 // zeroes if it is zero, and all ones otherwise. 1842 Value *Lower64ShadowExtend(IRBuilder<> &IRB, Value *S, Type *T) { 1843 if (S->getType()->isVectorTy()) 1844 S = CreateShadowCast(IRB, S, IRB.getInt64Ty(), /* Signed */ true); 1845 assert(S->getType()->getPrimitiveSizeInBits() <= 64); 1846 Value *S2 = IRB.CreateICmpNE(S, getCleanShadow(S)); 1847 return CreateShadowCast(IRB, S2, T, /* Signed */ true); 1848 } 1849 1850 Value *VariableShadowExtend(IRBuilder<> &IRB, Value *S) { 1851 Type *T = S->getType(); 1852 assert(T->isVectorTy()); 1853 Value *S2 = IRB.CreateICmpNE(S, getCleanShadow(S)); 1854 return IRB.CreateSExt(S2, T); 1855 } 1856 1857 // \brief Instrument vector shift instrinsic. 1858 // 1859 // This function instruments intrinsics like int_x86_avx2_psll_w. 1860 // Intrinsic shifts %In by %ShiftSize bits. 1861 // %ShiftSize may be a vector. In that case the lower 64 bits determine shift 1862 // size, and the rest is ignored. Behavior is defined even if shift size is 1863 // greater than register (or field) width. 1864 void handleVectorShiftIntrinsic(IntrinsicInst &I, bool Variable) { 1865 assert(I.getNumArgOperands() == 2); 1866 IRBuilder<> IRB(&I); 1867 // If any of the S2 bits are poisoned, the whole thing is poisoned. 1868 // Otherwise perform the same shift on S1. 1869 Value *S1 = getShadow(&I, 0); 1870 Value *S2 = getShadow(&I, 1); 1871 Value *S2Conv = Variable ? VariableShadowExtend(IRB, S2) 1872 : Lower64ShadowExtend(IRB, S2, getShadowTy(&I)); 1873 Value *V1 = I.getOperand(0); 1874 Value *V2 = I.getOperand(1); 1875 Value *Shift = IRB.CreateCall2(I.getCalledValue(), 1876 IRB.CreateBitCast(S1, V1->getType()), V2); 1877 Shift = IRB.CreateBitCast(Shift, getShadowTy(&I)); 1878 setShadow(&I, IRB.CreateOr(Shift, S2Conv)); 1879 setOriginForNaryOp(I); 1880 } 1881 1882 void visitIntrinsicInst(IntrinsicInst &I) { 1883 switch (I.getIntrinsicID()) { 1884 case llvm::Intrinsic::bswap: 1885 handleBswap(I); 1886 break; 1887 case llvm::Intrinsic::x86_avx512_cvtsd2usi64: 1888 case llvm::Intrinsic::x86_avx512_cvtsd2usi: 1889 case llvm::Intrinsic::x86_avx512_cvtss2usi64: 1890 case llvm::Intrinsic::x86_avx512_cvtss2usi: 1891 case llvm::Intrinsic::x86_avx512_cvttss2usi64: 1892 case llvm::Intrinsic::x86_avx512_cvttss2usi: 1893 case llvm::Intrinsic::x86_avx512_cvttsd2usi64: 1894 case llvm::Intrinsic::x86_avx512_cvttsd2usi: 1895 case llvm::Intrinsic::x86_avx512_cvtusi2sd: 1896 case llvm::Intrinsic::x86_avx512_cvtusi2ss: 1897 case llvm::Intrinsic::x86_avx512_cvtusi642sd: 1898 case llvm::Intrinsic::x86_avx512_cvtusi642ss: 1899 case llvm::Intrinsic::x86_sse2_cvtsd2si64: 1900 case llvm::Intrinsic::x86_sse2_cvtsd2si: 1901 case llvm::Intrinsic::x86_sse2_cvtsd2ss: 1902 case llvm::Intrinsic::x86_sse2_cvtsi2sd: 1903 case llvm::Intrinsic::x86_sse2_cvtsi642sd: 1904 case llvm::Intrinsic::x86_sse2_cvtss2sd: 1905 case llvm::Intrinsic::x86_sse2_cvttsd2si64: 1906 case llvm::Intrinsic::x86_sse2_cvttsd2si: 1907 case llvm::Intrinsic::x86_sse_cvtsi2ss: 1908 case llvm::Intrinsic::x86_sse_cvtsi642ss: 1909 case llvm::Intrinsic::x86_sse_cvtss2si64: 1910 case llvm::Intrinsic::x86_sse_cvtss2si: 1911 case llvm::Intrinsic::x86_sse_cvttss2si64: 1912 case llvm::Intrinsic::x86_sse_cvttss2si: 1913 handleVectorConvertIntrinsic(I, 1); 1914 break; 1915 case llvm::Intrinsic::x86_sse2_cvtdq2pd: 1916 case llvm::Intrinsic::x86_sse2_cvtps2pd: 1917 case llvm::Intrinsic::x86_sse_cvtps2pi: 1918 case llvm::Intrinsic::x86_sse_cvttps2pi: 1919 handleVectorConvertIntrinsic(I, 2); 1920 break; 1921 case llvm::Intrinsic::x86_avx512_psll_dq: 1922 case llvm::Intrinsic::x86_avx512_psrl_dq: 1923 case llvm::Intrinsic::x86_avx2_psll_w: 1924 case llvm::Intrinsic::x86_avx2_psll_d: 1925 case llvm::Intrinsic::x86_avx2_psll_q: 1926 case llvm::Intrinsic::x86_avx2_pslli_w: 1927 case llvm::Intrinsic::x86_avx2_pslli_d: 1928 case llvm::Intrinsic::x86_avx2_pslli_q: 1929 case llvm::Intrinsic::x86_avx2_psll_dq: 1930 case llvm::Intrinsic::x86_avx2_psrl_w: 1931 case llvm::Intrinsic::x86_avx2_psrl_d: 1932 case llvm::Intrinsic::x86_avx2_psrl_q: 1933 case llvm::Intrinsic::x86_avx2_psra_w: 1934 case llvm::Intrinsic::x86_avx2_psra_d: 1935 case llvm::Intrinsic::x86_avx2_psrli_w: 1936 case llvm::Intrinsic::x86_avx2_psrli_d: 1937 case llvm::Intrinsic::x86_avx2_psrli_q: 1938 case llvm::Intrinsic::x86_avx2_psrai_w: 1939 case llvm::Intrinsic::x86_avx2_psrai_d: 1940 case llvm::Intrinsic::x86_avx2_psrl_dq: 1941 case llvm::Intrinsic::x86_sse2_psll_w: 1942 case llvm::Intrinsic::x86_sse2_psll_d: 1943 case llvm::Intrinsic::x86_sse2_psll_q: 1944 case llvm::Intrinsic::x86_sse2_pslli_w: 1945 case llvm::Intrinsic::x86_sse2_pslli_d: 1946 case llvm::Intrinsic::x86_sse2_pslli_q: 1947 case llvm::Intrinsic::x86_sse2_psll_dq: 1948 case llvm::Intrinsic::x86_sse2_psrl_w: 1949 case llvm::Intrinsic::x86_sse2_psrl_d: 1950 case llvm::Intrinsic::x86_sse2_psrl_q: 1951 case llvm::Intrinsic::x86_sse2_psra_w: 1952 case llvm::Intrinsic::x86_sse2_psra_d: 1953 case llvm::Intrinsic::x86_sse2_psrli_w: 1954 case llvm::Intrinsic::x86_sse2_psrli_d: 1955 case llvm::Intrinsic::x86_sse2_psrli_q: 1956 case llvm::Intrinsic::x86_sse2_psrai_w: 1957 case llvm::Intrinsic::x86_sse2_psrai_d: 1958 case llvm::Intrinsic::x86_sse2_psrl_dq: 1959 case llvm::Intrinsic::x86_mmx_psll_w: 1960 case llvm::Intrinsic::x86_mmx_psll_d: 1961 case llvm::Intrinsic::x86_mmx_psll_q: 1962 case llvm::Intrinsic::x86_mmx_pslli_w: 1963 case llvm::Intrinsic::x86_mmx_pslli_d: 1964 case llvm::Intrinsic::x86_mmx_pslli_q: 1965 case llvm::Intrinsic::x86_mmx_psrl_w: 1966 case llvm::Intrinsic::x86_mmx_psrl_d: 1967 case llvm::Intrinsic::x86_mmx_psrl_q: 1968 case llvm::Intrinsic::x86_mmx_psra_w: 1969 case llvm::Intrinsic::x86_mmx_psra_d: 1970 case llvm::Intrinsic::x86_mmx_psrli_w: 1971 case llvm::Intrinsic::x86_mmx_psrli_d: 1972 case llvm::Intrinsic::x86_mmx_psrli_q: 1973 case llvm::Intrinsic::x86_mmx_psrai_w: 1974 case llvm::Intrinsic::x86_mmx_psrai_d: 1975 handleVectorShiftIntrinsic(I, /* Variable */ false); 1976 break; 1977 case llvm::Intrinsic::x86_avx2_psllv_d: 1978 case llvm::Intrinsic::x86_avx2_psllv_d_256: 1979 case llvm::Intrinsic::x86_avx2_psllv_q: 1980 case llvm::Intrinsic::x86_avx2_psllv_q_256: 1981 case llvm::Intrinsic::x86_avx2_psrlv_d: 1982 case llvm::Intrinsic::x86_avx2_psrlv_d_256: 1983 case llvm::Intrinsic::x86_avx2_psrlv_q: 1984 case llvm::Intrinsic::x86_avx2_psrlv_q_256: 1985 case llvm::Intrinsic::x86_avx2_psrav_d: 1986 case llvm::Intrinsic::x86_avx2_psrav_d_256: 1987 handleVectorShiftIntrinsic(I, /* Variable */ true); 1988 break; 1989 1990 // Byte shifts are not implemented. 1991 // case llvm::Intrinsic::x86_avx512_psll_dq_bs: 1992 // case llvm::Intrinsic::x86_avx512_psrl_dq_bs: 1993 // case llvm::Intrinsic::x86_avx2_psll_dq_bs: 1994 // case llvm::Intrinsic::x86_avx2_psrl_dq_bs: 1995 // case llvm::Intrinsic::x86_sse2_psll_dq_bs: 1996 // case llvm::Intrinsic::x86_sse2_psrl_dq_bs: 1997 1998 default: 1999 if (!handleUnknownIntrinsic(I)) 2000 visitInstruction(I); 2001 break; 2002 } 2003 } 2004 2005 void visitCallSite(CallSite CS) { 2006 Instruction &I = *CS.getInstruction(); 2007 assert((CS.isCall() || CS.isInvoke()) && "Unknown type of CallSite"); 2008 if (CS.isCall()) { 2009 CallInst *Call = cast<CallInst>(&I); 2010 2011 // For inline asm, do the usual thing: check argument shadow and mark all 2012 // outputs as clean. Note that any side effects of the inline asm that are 2013 // not immediately visible in its constraints are not handled. 2014 if (Call->isInlineAsm()) { 2015 visitInstruction(I); 2016 return; 2017 } 2018 2019 // Allow only tail calls with the same types, otherwise 2020 // we may have a false positive: shadow for a non-void RetVal 2021 // will get propagated to a void RetVal. 2022 if (Call->isTailCall() && Call->getType() != Call->getParent()->getType()) 2023 Call->setTailCall(false); 2024 2025 assert(!isa<IntrinsicInst>(&I) && "intrinsics are handled elsewhere"); 2026 2027 // We are going to insert code that relies on the fact that the callee 2028 // will become a non-readonly function after it is instrumented by us. To 2029 // prevent this code from being optimized out, mark that function 2030 // non-readonly in advance. 2031 if (Function *Func = Call->getCalledFunction()) { 2032 // Clear out readonly/readnone attributes. 2033 AttrBuilder B; 2034 B.addAttribute(Attribute::ReadOnly) 2035 .addAttribute(Attribute::ReadNone); 2036 Func->removeAttributes(AttributeSet::FunctionIndex, 2037 AttributeSet::get(Func->getContext(), 2038 AttributeSet::FunctionIndex, 2039 B)); 2040 } 2041 } 2042 IRBuilder<> IRB(&I); 2043 2044 if (MS.WrapIndirectCalls && !CS.getCalledFunction()) 2045 IndirectCallList.push_back(CS); 2046 2047 unsigned ArgOffset = 0; 2048 DEBUG(dbgs() << " CallSite: " << I << "\n"); 2049 for (CallSite::arg_iterator ArgIt = CS.arg_begin(), End = CS.arg_end(); 2050 ArgIt != End; ++ArgIt) { 2051 Value *A = *ArgIt; 2052 unsigned i = ArgIt - CS.arg_begin(); 2053 if (!A->getType()->isSized()) { 2054 DEBUG(dbgs() << "Arg " << i << " is not sized: " << I << "\n"); 2055 continue; 2056 } 2057 unsigned Size = 0; 2058 Value *Store = 0; 2059 // Compute the Shadow for arg even if it is ByVal, because 2060 // in that case getShadow() will copy the actual arg shadow to 2061 // __msan_param_tls. 2062 Value *ArgShadow = getShadow(A); 2063 Value *ArgShadowBase = getShadowPtrForArgument(A, IRB, ArgOffset); 2064 DEBUG(dbgs() << " Arg#" << i << ": " << *A << 2065 " Shadow: " << *ArgShadow << "\n"); 2066 if (CS.paramHasAttr(i + 1, Attribute::ByVal)) { 2067 assert(A->getType()->isPointerTy() && 2068 "ByVal argument is not a pointer!"); 2069 Size = MS.DL->getTypeAllocSize(A->getType()->getPointerElementType()); 2070 unsigned Alignment = CS.getParamAlignment(i + 1); 2071 Store = IRB.CreateMemCpy(ArgShadowBase, 2072 getShadowPtr(A, Type::getInt8Ty(*MS.C), IRB), 2073 Size, Alignment); 2074 } else { 2075 Size = MS.DL->getTypeAllocSize(A->getType()); 2076 Store = IRB.CreateAlignedStore(ArgShadow, ArgShadowBase, 2077 kShadowTLSAlignment); 2078 } 2079 if (MS.TrackOrigins) 2080 IRB.CreateStore(getOrigin(A), 2081 getOriginPtrForArgument(A, IRB, ArgOffset)); 2082 (void)Store; 2083 assert(Size != 0 && Store != 0); 2084 DEBUG(dbgs() << " Param:" << *Store << "\n"); 2085 ArgOffset += DataLayout::RoundUpAlignment(Size, 8); 2086 } 2087 DEBUG(dbgs() << " done with call args\n"); 2088 2089 FunctionType *FT = 2090 cast<FunctionType>(CS.getCalledValue()->getType()->getContainedType(0)); 2091 if (FT->isVarArg()) { 2092 VAHelper->visitCallSite(CS, IRB); 2093 } 2094 2095 // Now, get the shadow for the RetVal. 2096 if (!I.getType()->isSized()) return; 2097 IRBuilder<> IRBBefore(&I); 2098 // Until we have full dynamic coverage, make sure the retval shadow is 0. 2099 Value *Base = getShadowPtrForRetval(&I, IRBBefore); 2100 IRBBefore.CreateAlignedStore(getCleanShadow(&I), Base, kShadowTLSAlignment); 2101 Instruction *NextInsn = 0; 2102 if (CS.isCall()) { 2103 NextInsn = I.getNextNode(); 2104 } else { 2105 BasicBlock *NormalDest = cast<InvokeInst>(&I)->getNormalDest(); 2106 if (!NormalDest->getSinglePredecessor()) { 2107 // FIXME: this case is tricky, so we are just conservative here. 2108 // Perhaps we need to split the edge between this BB and NormalDest, 2109 // but a naive attempt to use SplitEdge leads to a crash. 2110 setShadow(&I, getCleanShadow(&I)); 2111 setOrigin(&I, getCleanOrigin()); 2112 return; 2113 } 2114 NextInsn = NormalDest->getFirstInsertionPt(); 2115 assert(NextInsn && 2116 "Could not find insertion point for retval shadow load"); 2117 } 2118 IRBuilder<> IRBAfter(NextInsn); 2119 Value *RetvalShadow = 2120 IRBAfter.CreateAlignedLoad(getShadowPtrForRetval(&I, IRBAfter), 2121 kShadowTLSAlignment, "_msret"); 2122 setShadow(&I, RetvalShadow); 2123 if (MS.TrackOrigins) 2124 setOrigin(&I, IRBAfter.CreateLoad(getOriginPtrForRetval(IRBAfter))); 2125 } 2126 2127 void visitReturnInst(ReturnInst &I) { 2128 IRBuilder<> IRB(&I); 2129 Value *RetVal = I.getReturnValue(); 2130 if (!RetVal) return; 2131 Value *ShadowPtr = getShadowPtrForRetval(RetVal, IRB); 2132 if (CheckReturnValue) { 2133 insertShadowCheck(RetVal, &I); 2134 Value *Shadow = getCleanShadow(RetVal); 2135 IRB.CreateAlignedStore(Shadow, ShadowPtr, kShadowTLSAlignment); 2136 } else { 2137 Value *Shadow = getShadow(RetVal); 2138 IRB.CreateAlignedStore(Shadow, ShadowPtr, kShadowTLSAlignment); 2139 // FIXME: make it conditional if ClStoreCleanOrigin==0 2140 if (MS.TrackOrigins) 2141 IRB.CreateStore(getOrigin(RetVal), getOriginPtrForRetval(IRB)); 2142 } 2143 } 2144 2145 void visitPHINode(PHINode &I) { 2146 IRBuilder<> IRB(&I); 2147 ShadowPHINodes.push_back(&I); 2148 setShadow(&I, IRB.CreatePHI(getShadowTy(&I), I.getNumIncomingValues(), 2149 "_msphi_s")); 2150 if (MS.TrackOrigins) 2151 setOrigin(&I, IRB.CreatePHI(MS.OriginTy, I.getNumIncomingValues(), 2152 "_msphi_o")); 2153 } 2154 2155 void visitAllocaInst(AllocaInst &I) { 2156 setShadow(&I, getCleanShadow(&I)); 2157 IRBuilder<> IRB(I.getNextNode()); 2158 uint64_t Size = MS.DL->getTypeAllocSize(I.getAllocatedType()); 2159 if (PoisonStack && ClPoisonStackWithCall) { 2160 IRB.CreateCall2(MS.MsanPoisonStackFn, 2161 IRB.CreatePointerCast(&I, IRB.getInt8PtrTy()), 2162 ConstantInt::get(MS.IntptrTy, Size)); 2163 } else { 2164 Value *ShadowBase = getShadowPtr(&I, Type::getInt8PtrTy(*MS.C), IRB); 2165 Value *PoisonValue = IRB.getInt8(PoisonStack ? ClPoisonStackPattern : 0); 2166 IRB.CreateMemSet(ShadowBase, PoisonValue, Size, I.getAlignment()); 2167 } 2168 2169 if (PoisonStack && MS.TrackOrigins) { 2170 setOrigin(&I, getCleanOrigin()); 2171 SmallString<2048> StackDescriptionStorage; 2172 raw_svector_ostream StackDescription(StackDescriptionStorage); 2173 // We create a string with a description of the stack allocation and 2174 // pass it into __msan_set_alloca_origin. 2175 // It will be printed by the run-time if stack-originated UMR is found. 2176 // The first 4 bytes of the string are set to '----' and will be replaced 2177 // by __msan_va_arg_overflow_size_tls at the first call. 2178 StackDescription << "----" << I.getName() << "@" << F.getName(); 2179 Value *Descr = 2180 createPrivateNonConstGlobalForString(*F.getParent(), 2181 StackDescription.str()); 2182 2183 IRB.CreateCall4(MS.MsanSetAllocaOrigin4Fn, 2184 IRB.CreatePointerCast(&I, IRB.getInt8PtrTy()), 2185 ConstantInt::get(MS.IntptrTy, Size), 2186 IRB.CreatePointerCast(Descr, IRB.getInt8PtrTy()), 2187 IRB.CreatePointerCast(&F, MS.IntptrTy)); 2188 } 2189 } 2190 2191 void visitSelectInst(SelectInst& I) { 2192 IRBuilder<> IRB(&I); 2193 // a = select b, c, d 2194 Value *B = I.getCondition(); 2195 Value *C = I.getTrueValue(); 2196 Value *D = I.getFalseValue(); 2197 Value *Sb = getShadow(B); 2198 Value *Sc = getShadow(C); 2199 Value *Sd = getShadow(D); 2200 2201 // Result shadow if condition shadow is 0. 2202 Value *Sa0 = IRB.CreateSelect(B, Sc, Sd); 2203 Value *Sa1; 2204 if (I.getType()->isAggregateType()) { 2205 // To avoid "sign extending" i1 to an arbitrary aggregate type, we just do 2206 // an extra "select". This results in much more compact IR. 2207 // Sa = select Sb, poisoned, (select b, Sc, Sd) 2208 Sa1 = getPoisonedShadow(getShadowTy(I.getType())); 2209 } else { 2210 // Sa = select Sb, [ (c^d) | Sc | Sd ], [ b ? Sc : Sd ] 2211 // If Sb (condition is poisoned), look for bits in c and d that are equal 2212 // and both unpoisoned. 2213 // If !Sb (condition is unpoisoned), simply pick one of Sc and Sd. 2214 2215 // Cast arguments to shadow-compatible type. 2216 C = CreateAppToShadowCast(IRB, C); 2217 D = CreateAppToShadowCast(IRB, D); 2218 2219 // Result shadow if condition shadow is 1. 2220 Sa1 = IRB.CreateOr(IRB.CreateXor(C, D), IRB.CreateOr(Sc, Sd)); 2221 } 2222 Value *Sa = IRB.CreateSelect(Sb, Sa1, Sa0, "_msprop_select"); 2223 setShadow(&I, Sa); 2224 if (MS.TrackOrigins) { 2225 // Origins are always i32, so any vector conditions must be flattened. 2226 // FIXME: consider tracking vector origins for app vectors? 2227 if (B->getType()->isVectorTy()) { 2228 Type *FlatTy = getShadowTyNoVec(B->getType()); 2229 B = IRB.CreateICmpNE(IRB.CreateBitCast(B, FlatTy), 2230 ConstantInt::getNullValue(FlatTy)); 2231 Sb = IRB.CreateICmpNE(IRB.CreateBitCast(Sb, FlatTy), 2232 ConstantInt::getNullValue(FlatTy)); 2233 } 2234 // a = select b, c, d 2235 // Oa = Sb ? Ob : (b ? Oc : Od) 2236 setOrigin(&I, IRB.CreateSelect( 2237 Sb, getOrigin(I.getCondition()), 2238 IRB.CreateSelect(B, getOrigin(C), getOrigin(D)))); 2239 } 2240 } 2241 2242 void visitLandingPadInst(LandingPadInst &I) { 2243 // Do nothing. 2244 // See http://code.google.com/p/memory-sanitizer/issues/detail?id=1 2245 setShadow(&I, getCleanShadow(&I)); 2246 setOrigin(&I, getCleanOrigin()); 2247 } 2248 2249 void visitGetElementPtrInst(GetElementPtrInst &I) { 2250 handleShadowOr(I); 2251 } 2252 2253 void visitExtractValueInst(ExtractValueInst &I) { 2254 IRBuilder<> IRB(&I); 2255 Value *Agg = I.getAggregateOperand(); 2256 DEBUG(dbgs() << "ExtractValue: " << I << "\n"); 2257 Value *AggShadow = getShadow(Agg); 2258 DEBUG(dbgs() << " AggShadow: " << *AggShadow << "\n"); 2259 Value *ResShadow = IRB.CreateExtractValue(AggShadow, I.getIndices()); 2260 DEBUG(dbgs() << " ResShadow: " << *ResShadow << "\n"); 2261 setShadow(&I, ResShadow); 2262 setOriginForNaryOp(I); 2263 } 2264 2265 void visitInsertValueInst(InsertValueInst &I) { 2266 IRBuilder<> IRB(&I); 2267 DEBUG(dbgs() << "InsertValue: " << I << "\n"); 2268 Value *AggShadow = getShadow(I.getAggregateOperand()); 2269 Value *InsShadow = getShadow(I.getInsertedValueOperand()); 2270 DEBUG(dbgs() << " AggShadow: " << *AggShadow << "\n"); 2271 DEBUG(dbgs() << " InsShadow: " << *InsShadow << "\n"); 2272 Value *Res = IRB.CreateInsertValue(AggShadow, InsShadow, I.getIndices()); 2273 DEBUG(dbgs() << " Res: " << *Res << "\n"); 2274 setShadow(&I, Res); 2275 setOriginForNaryOp(I); 2276 } 2277 2278 void dumpInst(Instruction &I) { 2279 if (CallInst *CI = dyn_cast<CallInst>(&I)) { 2280 errs() << "ZZZ call " << CI->getCalledFunction()->getName() << "\n"; 2281 } else { 2282 errs() << "ZZZ " << I.getOpcodeName() << "\n"; 2283 } 2284 errs() << "QQQ " << I << "\n"; 2285 } 2286 2287 void visitResumeInst(ResumeInst &I) { 2288 DEBUG(dbgs() << "Resume: " << I << "\n"); 2289 // Nothing to do here. 2290 } 2291 2292 void visitInstruction(Instruction &I) { 2293 // Everything else: stop propagating and check for poisoned shadow. 2294 if (ClDumpStrictInstructions) 2295 dumpInst(I); 2296 DEBUG(dbgs() << "DEFAULT: " << I << "\n"); 2297 for (size_t i = 0, n = I.getNumOperands(); i < n; i++) 2298 insertShadowCheck(I.getOperand(i), &I); 2299 setShadow(&I, getCleanShadow(&I)); 2300 setOrigin(&I, getCleanOrigin()); 2301 } 2302}; 2303 2304/// \brief AMD64-specific implementation of VarArgHelper. 2305struct VarArgAMD64Helper : public VarArgHelper { 2306 // An unfortunate workaround for asymmetric lowering of va_arg stuff. 2307 // See a comment in visitCallSite for more details. 2308 static const unsigned AMD64GpEndOffset = 48; // AMD64 ABI Draft 0.99.6 p3.5.7 2309 static const unsigned AMD64FpEndOffset = 176; 2310 2311 Function &F; 2312 MemorySanitizer &MS; 2313 MemorySanitizerVisitor &MSV; 2314 Value *VAArgTLSCopy; 2315 Value *VAArgOverflowSize; 2316 2317 SmallVector<CallInst*, 16> VAStartInstrumentationList; 2318 2319 VarArgAMD64Helper(Function &F, MemorySanitizer &MS, 2320 MemorySanitizerVisitor &MSV) 2321 : F(F), MS(MS), MSV(MSV), VAArgTLSCopy(0), VAArgOverflowSize(0) { } 2322 2323 enum ArgKind { AK_GeneralPurpose, AK_FloatingPoint, AK_Memory }; 2324 2325 ArgKind classifyArgument(Value* arg) { 2326 // A very rough approximation of X86_64 argument classification rules. 2327 Type *T = arg->getType(); 2328 if (T->isFPOrFPVectorTy() || T->isX86_MMXTy()) 2329 return AK_FloatingPoint; 2330 if (T->isIntegerTy() && T->getPrimitiveSizeInBits() <= 64) 2331 return AK_GeneralPurpose; 2332 if (T->isPointerTy()) 2333 return AK_GeneralPurpose; 2334 return AK_Memory; 2335 } 2336 2337 // For VarArg functions, store the argument shadow in an ABI-specific format 2338 // that corresponds to va_list layout. 2339 // We do this because Clang lowers va_arg in the frontend, and this pass 2340 // only sees the low level code that deals with va_list internals. 2341 // A much easier alternative (provided that Clang emits va_arg instructions) 2342 // would have been to associate each live instance of va_list with a copy of 2343 // MSanParamTLS, and extract shadow on va_arg() call in the argument list 2344 // order. 2345 void visitCallSite(CallSite &CS, IRBuilder<> &IRB) override { 2346 unsigned GpOffset = 0; 2347 unsigned FpOffset = AMD64GpEndOffset; 2348 unsigned OverflowOffset = AMD64FpEndOffset; 2349 for (CallSite::arg_iterator ArgIt = CS.arg_begin(), End = CS.arg_end(); 2350 ArgIt != End; ++ArgIt) { 2351 Value *A = *ArgIt; 2352 unsigned ArgNo = CS.getArgumentNo(ArgIt); 2353 bool IsByVal = CS.paramHasAttr(ArgNo + 1, Attribute::ByVal); 2354 if (IsByVal) { 2355 // ByVal arguments always go to the overflow area. 2356 assert(A->getType()->isPointerTy()); 2357 Type *RealTy = A->getType()->getPointerElementType(); 2358 uint64_t ArgSize = MS.DL->getTypeAllocSize(RealTy); 2359 Value *Base = getShadowPtrForVAArgument(RealTy, IRB, OverflowOffset); 2360 OverflowOffset += DataLayout::RoundUpAlignment(ArgSize, 8); 2361 IRB.CreateMemCpy(Base, MSV.getShadowPtr(A, IRB.getInt8Ty(), IRB), 2362 ArgSize, kShadowTLSAlignment); 2363 } else { 2364 ArgKind AK = classifyArgument(A); 2365 if (AK == AK_GeneralPurpose && GpOffset >= AMD64GpEndOffset) 2366 AK = AK_Memory; 2367 if (AK == AK_FloatingPoint && FpOffset >= AMD64FpEndOffset) 2368 AK = AK_Memory; 2369 Value *Base; 2370 switch (AK) { 2371 case AK_GeneralPurpose: 2372 Base = getShadowPtrForVAArgument(A->getType(), IRB, GpOffset); 2373 GpOffset += 8; 2374 break; 2375 case AK_FloatingPoint: 2376 Base = getShadowPtrForVAArgument(A->getType(), IRB, FpOffset); 2377 FpOffset += 16; 2378 break; 2379 case AK_Memory: 2380 uint64_t ArgSize = MS.DL->getTypeAllocSize(A->getType()); 2381 Base = getShadowPtrForVAArgument(A->getType(), IRB, OverflowOffset); 2382 OverflowOffset += DataLayout::RoundUpAlignment(ArgSize, 8); 2383 } 2384 IRB.CreateAlignedStore(MSV.getShadow(A), Base, kShadowTLSAlignment); 2385 } 2386 } 2387 Constant *OverflowSize = 2388 ConstantInt::get(IRB.getInt64Ty(), OverflowOffset - AMD64FpEndOffset); 2389 IRB.CreateStore(OverflowSize, MS.VAArgOverflowSizeTLS); 2390 } 2391 2392 /// \brief Compute the shadow address for a given va_arg. 2393 Value *getShadowPtrForVAArgument(Type *Ty, IRBuilder<> &IRB, 2394 int ArgOffset) { 2395 Value *Base = IRB.CreatePointerCast(MS.VAArgTLS, MS.IntptrTy); 2396 Base = IRB.CreateAdd(Base, ConstantInt::get(MS.IntptrTy, ArgOffset)); 2397 return IRB.CreateIntToPtr(Base, PointerType::get(MSV.getShadowTy(Ty), 0), 2398 "_msarg"); 2399 } 2400 2401 void visitVAStartInst(VAStartInst &I) override { 2402 IRBuilder<> IRB(&I); 2403 VAStartInstrumentationList.push_back(&I); 2404 Value *VAListTag = I.getArgOperand(0); 2405 Value *ShadowPtr = MSV.getShadowPtr(VAListTag, IRB.getInt8Ty(), IRB); 2406 2407 // Unpoison the whole __va_list_tag. 2408 // FIXME: magic ABI constants. 2409 IRB.CreateMemSet(ShadowPtr, Constant::getNullValue(IRB.getInt8Ty()), 2410 /* size */24, /* alignment */8, false); 2411 } 2412 2413 void visitVACopyInst(VACopyInst &I) override { 2414 IRBuilder<> IRB(&I); 2415 Value *VAListTag = I.getArgOperand(0); 2416 Value *ShadowPtr = MSV.getShadowPtr(VAListTag, IRB.getInt8Ty(), IRB); 2417 2418 // Unpoison the whole __va_list_tag. 2419 // FIXME: magic ABI constants. 2420 IRB.CreateMemSet(ShadowPtr, Constant::getNullValue(IRB.getInt8Ty()), 2421 /* size */24, /* alignment */8, false); 2422 } 2423 2424 void finalizeInstrumentation() override { 2425 assert(!VAArgOverflowSize && !VAArgTLSCopy && 2426 "finalizeInstrumentation called twice"); 2427 if (!VAStartInstrumentationList.empty()) { 2428 // If there is a va_start in this function, make a backup copy of 2429 // va_arg_tls somewhere in the function entry block. 2430 IRBuilder<> IRB(F.getEntryBlock().getFirstNonPHI()); 2431 VAArgOverflowSize = IRB.CreateLoad(MS.VAArgOverflowSizeTLS); 2432 Value *CopySize = 2433 IRB.CreateAdd(ConstantInt::get(MS.IntptrTy, AMD64FpEndOffset), 2434 VAArgOverflowSize); 2435 VAArgTLSCopy = IRB.CreateAlloca(Type::getInt8Ty(*MS.C), CopySize); 2436 IRB.CreateMemCpy(VAArgTLSCopy, MS.VAArgTLS, CopySize, 8); 2437 } 2438 2439 // Instrument va_start. 2440 // Copy va_list shadow from the backup copy of the TLS contents. 2441 for (size_t i = 0, n = VAStartInstrumentationList.size(); i < n; i++) { 2442 CallInst *OrigInst = VAStartInstrumentationList[i]; 2443 IRBuilder<> IRB(OrigInst->getNextNode()); 2444 Value *VAListTag = OrigInst->getArgOperand(0); 2445 2446 Value *RegSaveAreaPtrPtr = 2447 IRB.CreateIntToPtr( 2448 IRB.CreateAdd(IRB.CreatePtrToInt(VAListTag, MS.IntptrTy), 2449 ConstantInt::get(MS.IntptrTy, 16)), 2450 Type::getInt64PtrTy(*MS.C)); 2451 Value *RegSaveAreaPtr = IRB.CreateLoad(RegSaveAreaPtrPtr); 2452 Value *RegSaveAreaShadowPtr = 2453 MSV.getShadowPtr(RegSaveAreaPtr, IRB.getInt8Ty(), IRB); 2454 IRB.CreateMemCpy(RegSaveAreaShadowPtr, VAArgTLSCopy, 2455 AMD64FpEndOffset, 16); 2456 2457 Value *OverflowArgAreaPtrPtr = 2458 IRB.CreateIntToPtr( 2459 IRB.CreateAdd(IRB.CreatePtrToInt(VAListTag, MS.IntptrTy), 2460 ConstantInt::get(MS.IntptrTy, 8)), 2461 Type::getInt64PtrTy(*MS.C)); 2462 Value *OverflowArgAreaPtr = IRB.CreateLoad(OverflowArgAreaPtrPtr); 2463 Value *OverflowArgAreaShadowPtr = 2464 MSV.getShadowPtr(OverflowArgAreaPtr, IRB.getInt8Ty(), IRB); 2465 Value *SrcPtr = IRB.CreateConstGEP1_32(VAArgTLSCopy, AMD64FpEndOffset); 2466 IRB.CreateMemCpy(OverflowArgAreaShadowPtr, SrcPtr, VAArgOverflowSize, 16); 2467 } 2468 } 2469}; 2470 2471/// \brief A no-op implementation of VarArgHelper. 2472struct VarArgNoOpHelper : public VarArgHelper { 2473 VarArgNoOpHelper(Function &F, MemorySanitizer &MS, 2474 MemorySanitizerVisitor &MSV) {} 2475 2476 void visitCallSite(CallSite &CS, IRBuilder<> &IRB) override {} 2477 2478 void visitVAStartInst(VAStartInst &I) override {} 2479 2480 void visitVACopyInst(VACopyInst &I) override {} 2481 2482 void finalizeInstrumentation() override {} 2483}; 2484 2485VarArgHelper *CreateVarArgHelper(Function &Func, MemorySanitizer &Msan, 2486 MemorySanitizerVisitor &Visitor) { 2487 // VarArg handling is only implemented on AMD64. False positives are possible 2488 // on other platforms. 2489 llvm::Triple TargetTriple(Func.getParent()->getTargetTriple()); 2490 if (TargetTriple.getArch() == llvm::Triple::x86_64) 2491 return new VarArgAMD64Helper(Func, Msan, Visitor); 2492 else 2493 return new VarArgNoOpHelper(Func, Msan, Visitor); 2494} 2495 2496} // namespace 2497 2498bool MemorySanitizer::runOnFunction(Function &F) { 2499 MemorySanitizerVisitor Visitor(F, *this); 2500 2501 // Clear out readonly/readnone attributes. 2502 AttrBuilder B; 2503 B.addAttribute(Attribute::ReadOnly) 2504 .addAttribute(Attribute::ReadNone); 2505 F.removeAttributes(AttributeSet::FunctionIndex, 2506 AttributeSet::get(F.getContext(), 2507 AttributeSet::FunctionIndex, B)); 2508 2509 return Visitor.runOnFunction(); 2510} 2511