DataFlowSanitizer.cpp revision 263508
1//===-- DataFlowSanitizer.cpp - dynamic data flow analysis ----------------===// 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 DataFlowSanitizer, a generalised dynamic data flow 11/// analysis. 12/// 13/// Unlike other Sanitizer tools, this tool is not designed to detect a specific 14/// class of bugs on its own. Instead, it provides a generic dynamic data flow 15/// analysis framework to be used by clients to help detect application-specific 16/// issues within their own code. 17/// 18/// The analysis is based on automatic propagation of data flow labels (also 19/// known as taint labels) through a program as it performs computation. Each 20/// byte of application memory is backed by two bytes of shadow memory which 21/// hold the label. On Linux/x86_64, memory is laid out as follows: 22/// 23/// +--------------------+ 0x800000000000 (top of memory) 24/// | application memory | 25/// +--------------------+ 0x700000008000 (kAppAddr) 26/// | | 27/// | unused | 28/// | | 29/// +--------------------+ 0x200200000000 (kUnusedAddr) 30/// | union table | 31/// +--------------------+ 0x200000000000 (kUnionTableAddr) 32/// | shadow memory | 33/// +--------------------+ 0x000000010000 (kShadowAddr) 34/// | reserved by kernel | 35/// +--------------------+ 0x000000000000 36/// 37/// To derive a shadow memory address from an application memory address, 38/// bits 44-46 are cleared to bring the address into the range 39/// [0x000000008000,0x100000000000). Then the address is shifted left by 1 to 40/// account for the double byte representation of shadow labels and move the 41/// address into the shadow memory range. See the function 42/// DataFlowSanitizer::getShadowAddress below. 43/// 44/// For more information, please refer to the design document: 45/// http://clang.llvm.org/docs/DataFlowSanitizerDesign.html 46 47#include "llvm/Transforms/Instrumentation.h" 48#include "llvm/ADT/DenseMap.h" 49#include "llvm/ADT/DenseSet.h" 50#include "llvm/ADT/DepthFirstIterator.h" 51#include "llvm/ADT/StringExtras.h" 52#include "llvm/Analysis/ValueTracking.h" 53#include "llvm/IR/InlineAsm.h" 54#include "llvm/IR/IRBuilder.h" 55#include "llvm/IR/LLVMContext.h" 56#include "llvm/IR/MDBuilder.h" 57#include "llvm/IR/Type.h" 58#include "llvm/IR/Value.h" 59#include "llvm/InstVisitor.h" 60#include "llvm/Pass.h" 61#include "llvm/Support/CommandLine.h" 62#include "llvm/Transforms/Utils/BasicBlockUtils.h" 63#include "llvm/Transforms/Utils/Local.h" 64#include "llvm/Transforms/Utils/SpecialCaseList.h" 65#include <iterator> 66 67using namespace llvm; 68 69// The -dfsan-preserve-alignment flag controls whether this pass assumes that 70// alignment requirements provided by the input IR are correct. For example, 71// if the input IR contains a load with alignment 8, this flag will cause 72// the shadow load to have alignment 16. This flag is disabled by default as 73// we have unfortunately encountered too much code (including Clang itself; 74// see PR14291) which performs misaligned access. 75static cl::opt<bool> ClPreserveAlignment( 76 "dfsan-preserve-alignment", 77 cl::desc("respect alignment requirements provided by input IR"), cl::Hidden, 78 cl::init(false)); 79 80// The ABI list file controls how shadow parameters are passed. The pass treats 81// every function labelled "uninstrumented" in the ABI list file as conforming 82// to the "native" (i.e. unsanitized) ABI. Unless the ABI list contains 83// additional annotations for those functions, a call to one of those functions 84// will produce a warning message, as the labelling behaviour of the function is 85// unknown. The other supported annotations are "functional" and "discard", 86// which are described below under DataFlowSanitizer::WrapperKind. 87static cl::opt<std::string> ClABIListFile( 88 "dfsan-abilist", 89 cl::desc("File listing native ABI functions and how the pass treats them"), 90 cl::Hidden); 91 92// Controls whether the pass uses IA_Args or IA_TLS as the ABI for instrumented 93// functions (see DataFlowSanitizer::InstrumentedABI below). 94static cl::opt<bool> ClArgsABI( 95 "dfsan-args-abi", 96 cl::desc("Use the argument ABI rather than the TLS ABI"), 97 cl::Hidden); 98 99static cl::opt<bool> ClDebugNonzeroLabels( 100 "dfsan-debug-nonzero-labels", 101 cl::desc("Insert calls to __dfsan_nonzero_label on observing a parameter, " 102 "load or return with a nonzero label"), 103 cl::Hidden); 104 105namespace { 106 107class DataFlowSanitizer : public ModulePass { 108 friend struct DFSanFunction; 109 friend class DFSanVisitor; 110 111 enum { 112 ShadowWidth = 16 113 }; 114 115 /// Which ABI should be used for instrumented functions? 116 enum InstrumentedABI { 117 /// Argument and return value labels are passed through additional 118 /// arguments and by modifying the return type. 119 IA_Args, 120 121 /// Argument and return value labels are passed through TLS variables 122 /// __dfsan_arg_tls and __dfsan_retval_tls. 123 IA_TLS 124 }; 125 126 /// How should calls to uninstrumented functions be handled? 127 enum WrapperKind { 128 /// This function is present in an uninstrumented form but we don't know 129 /// how it should be handled. Print a warning and call the function anyway. 130 /// Don't label the return value. 131 WK_Warning, 132 133 /// This function does not write to (user-accessible) memory, and its return 134 /// value is unlabelled. 135 WK_Discard, 136 137 /// This function does not write to (user-accessible) memory, and the label 138 /// of its return value is the union of the label of its arguments. 139 WK_Functional, 140 141 /// Instead of calling the function, a custom wrapper __dfsw_F is called, 142 /// where F is the name of the function. This function may wrap the 143 /// original function or provide its own implementation. This is similar to 144 /// the IA_Args ABI, except that IA_Args uses a struct return type to 145 /// pass the return value shadow in a register, while WK_Custom uses an 146 /// extra pointer argument to return the shadow. This allows the wrapped 147 /// form of the function type to be expressed in C. 148 WK_Custom 149 }; 150 151 DataLayout *DL; 152 Module *Mod; 153 LLVMContext *Ctx; 154 IntegerType *ShadowTy; 155 PointerType *ShadowPtrTy; 156 IntegerType *IntptrTy; 157 ConstantInt *ZeroShadow; 158 ConstantInt *ShadowPtrMask; 159 ConstantInt *ShadowPtrMul; 160 Constant *ArgTLS; 161 Constant *RetvalTLS; 162 void *(*GetArgTLSPtr)(); 163 void *(*GetRetvalTLSPtr)(); 164 Constant *GetArgTLS; 165 Constant *GetRetvalTLS; 166 FunctionType *DFSanUnionFnTy; 167 FunctionType *DFSanUnionLoadFnTy; 168 FunctionType *DFSanUnimplementedFnTy; 169 FunctionType *DFSanSetLabelFnTy; 170 FunctionType *DFSanNonzeroLabelFnTy; 171 Constant *DFSanUnionFn; 172 Constant *DFSanUnionLoadFn; 173 Constant *DFSanUnimplementedFn; 174 Constant *DFSanSetLabelFn; 175 Constant *DFSanNonzeroLabelFn; 176 MDNode *ColdCallWeights; 177 OwningPtr<SpecialCaseList> ABIList; 178 DenseMap<Value *, Function *> UnwrappedFnMap; 179 AttributeSet ReadOnlyNoneAttrs; 180 181 Value *getShadowAddress(Value *Addr, Instruction *Pos); 182 Value *combineShadows(Value *V1, Value *V2, Instruction *Pos); 183 bool isInstrumented(const Function *F); 184 bool isInstrumented(const GlobalAlias *GA); 185 FunctionType *getArgsFunctionType(FunctionType *T); 186 FunctionType *getTrampolineFunctionType(FunctionType *T); 187 FunctionType *getCustomFunctionType(FunctionType *T); 188 InstrumentedABI getInstrumentedABI(); 189 WrapperKind getWrapperKind(Function *F); 190 void addGlobalNamePrefix(GlobalValue *GV); 191 Function *buildWrapperFunction(Function *F, StringRef NewFName, 192 GlobalValue::LinkageTypes NewFLink, 193 FunctionType *NewFT); 194 Constant *getOrBuildTrampolineFunction(FunctionType *FT, StringRef FName); 195 196 public: 197 DataFlowSanitizer(StringRef ABIListFile = StringRef(), 198 void *(*getArgTLS)() = 0, void *(*getRetValTLS)() = 0); 199 static char ID; 200 bool doInitialization(Module &M); 201 bool runOnModule(Module &M); 202}; 203 204struct DFSanFunction { 205 DataFlowSanitizer &DFS; 206 Function *F; 207 DataFlowSanitizer::InstrumentedABI IA; 208 bool IsNativeABI; 209 Value *ArgTLSPtr; 210 Value *RetvalTLSPtr; 211 AllocaInst *LabelReturnAlloca; 212 DenseMap<Value *, Value *> ValShadowMap; 213 DenseMap<AllocaInst *, AllocaInst *> AllocaShadowMap; 214 std::vector<std::pair<PHINode *, PHINode *> > PHIFixups; 215 DenseSet<Instruction *> SkipInsts; 216 DenseSet<Value *> NonZeroChecks; 217 218 DFSanFunction(DataFlowSanitizer &DFS, Function *F, bool IsNativeABI) 219 : DFS(DFS), F(F), IA(DFS.getInstrumentedABI()), 220 IsNativeABI(IsNativeABI), ArgTLSPtr(0), RetvalTLSPtr(0), 221 LabelReturnAlloca(0) {} 222 Value *getArgTLSPtr(); 223 Value *getArgTLS(unsigned Index, Instruction *Pos); 224 Value *getRetvalTLS(); 225 Value *getShadow(Value *V); 226 void setShadow(Instruction *I, Value *Shadow); 227 Value *combineOperandShadows(Instruction *Inst); 228 Value *loadShadow(Value *ShadowAddr, uint64_t Size, uint64_t Align, 229 Instruction *Pos); 230 void storeShadow(Value *Addr, uint64_t Size, uint64_t Align, Value *Shadow, 231 Instruction *Pos); 232}; 233 234class DFSanVisitor : public InstVisitor<DFSanVisitor> { 235 public: 236 DFSanFunction &DFSF; 237 DFSanVisitor(DFSanFunction &DFSF) : DFSF(DFSF) {} 238 239 void visitOperandShadowInst(Instruction &I); 240 241 void visitBinaryOperator(BinaryOperator &BO); 242 void visitCastInst(CastInst &CI); 243 void visitCmpInst(CmpInst &CI); 244 void visitGetElementPtrInst(GetElementPtrInst &GEPI); 245 void visitLoadInst(LoadInst &LI); 246 void visitStoreInst(StoreInst &SI); 247 void visitReturnInst(ReturnInst &RI); 248 void visitCallSite(CallSite CS); 249 void visitPHINode(PHINode &PN); 250 void visitExtractElementInst(ExtractElementInst &I); 251 void visitInsertElementInst(InsertElementInst &I); 252 void visitShuffleVectorInst(ShuffleVectorInst &I); 253 void visitExtractValueInst(ExtractValueInst &I); 254 void visitInsertValueInst(InsertValueInst &I); 255 void visitAllocaInst(AllocaInst &I); 256 void visitSelectInst(SelectInst &I); 257 void visitMemSetInst(MemSetInst &I); 258 void visitMemTransferInst(MemTransferInst &I); 259}; 260 261} 262 263char DataFlowSanitizer::ID; 264INITIALIZE_PASS(DataFlowSanitizer, "dfsan", 265 "DataFlowSanitizer: dynamic data flow analysis.", false, false) 266 267ModulePass *llvm::createDataFlowSanitizerPass(StringRef ABIListFile, 268 void *(*getArgTLS)(), 269 void *(*getRetValTLS)()) { 270 return new DataFlowSanitizer(ABIListFile, getArgTLS, getRetValTLS); 271} 272 273DataFlowSanitizer::DataFlowSanitizer(StringRef ABIListFile, 274 void *(*getArgTLS)(), 275 void *(*getRetValTLS)()) 276 : ModulePass(ID), GetArgTLSPtr(getArgTLS), GetRetvalTLSPtr(getRetValTLS), 277 ABIList(SpecialCaseList::createOrDie(ABIListFile.empty() ? ClABIListFile 278 : ABIListFile)) { 279} 280 281FunctionType *DataFlowSanitizer::getArgsFunctionType(FunctionType *T) { 282 llvm::SmallVector<Type *, 4> ArgTypes; 283 std::copy(T->param_begin(), T->param_end(), std::back_inserter(ArgTypes)); 284 for (unsigned i = 0, e = T->getNumParams(); i != e; ++i) 285 ArgTypes.push_back(ShadowTy); 286 if (T->isVarArg()) 287 ArgTypes.push_back(ShadowPtrTy); 288 Type *RetType = T->getReturnType(); 289 if (!RetType->isVoidTy()) 290 RetType = StructType::get(RetType, ShadowTy, (Type *)0); 291 return FunctionType::get(RetType, ArgTypes, T->isVarArg()); 292} 293 294FunctionType *DataFlowSanitizer::getTrampolineFunctionType(FunctionType *T) { 295 assert(!T->isVarArg()); 296 llvm::SmallVector<Type *, 4> ArgTypes; 297 ArgTypes.push_back(T->getPointerTo()); 298 std::copy(T->param_begin(), T->param_end(), std::back_inserter(ArgTypes)); 299 for (unsigned i = 0, e = T->getNumParams(); i != e; ++i) 300 ArgTypes.push_back(ShadowTy); 301 Type *RetType = T->getReturnType(); 302 if (!RetType->isVoidTy()) 303 ArgTypes.push_back(ShadowPtrTy); 304 return FunctionType::get(T->getReturnType(), ArgTypes, false); 305} 306 307FunctionType *DataFlowSanitizer::getCustomFunctionType(FunctionType *T) { 308 assert(!T->isVarArg()); 309 llvm::SmallVector<Type *, 4> ArgTypes; 310 for (FunctionType::param_iterator i = T->param_begin(), e = T->param_end(); 311 i != e; ++i) { 312 FunctionType *FT; 313 if (isa<PointerType>(*i) && (FT = dyn_cast<FunctionType>(cast<PointerType>( 314 *i)->getElementType()))) { 315 ArgTypes.push_back(getTrampolineFunctionType(FT)->getPointerTo()); 316 ArgTypes.push_back(Type::getInt8PtrTy(*Ctx)); 317 } else { 318 ArgTypes.push_back(*i); 319 } 320 } 321 for (unsigned i = 0, e = T->getNumParams(); i != e; ++i) 322 ArgTypes.push_back(ShadowTy); 323 Type *RetType = T->getReturnType(); 324 if (!RetType->isVoidTy()) 325 ArgTypes.push_back(ShadowPtrTy); 326 return FunctionType::get(T->getReturnType(), ArgTypes, false); 327} 328 329bool DataFlowSanitizer::doInitialization(Module &M) { 330 DL = getAnalysisIfAvailable<DataLayout>(); 331 if (!DL) 332 return false; 333 334 Mod = &M; 335 Ctx = &M.getContext(); 336 ShadowTy = IntegerType::get(*Ctx, ShadowWidth); 337 ShadowPtrTy = PointerType::getUnqual(ShadowTy); 338 IntptrTy = DL->getIntPtrType(*Ctx); 339 ZeroShadow = ConstantInt::getSigned(ShadowTy, 0); 340 ShadowPtrMask = ConstantInt::getSigned(IntptrTy, ~0x700000000000LL); 341 ShadowPtrMul = ConstantInt::getSigned(IntptrTy, ShadowWidth / 8); 342 343 Type *DFSanUnionArgs[2] = { ShadowTy, ShadowTy }; 344 DFSanUnionFnTy = 345 FunctionType::get(ShadowTy, DFSanUnionArgs, /*isVarArg=*/ false); 346 Type *DFSanUnionLoadArgs[2] = { ShadowPtrTy, IntptrTy }; 347 DFSanUnionLoadFnTy = 348 FunctionType::get(ShadowTy, DFSanUnionLoadArgs, /*isVarArg=*/ false); 349 DFSanUnimplementedFnTy = FunctionType::get( 350 Type::getVoidTy(*Ctx), Type::getInt8PtrTy(*Ctx), /*isVarArg=*/false); 351 Type *DFSanSetLabelArgs[3] = { ShadowTy, Type::getInt8PtrTy(*Ctx), IntptrTy }; 352 DFSanSetLabelFnTy = FunctionType::get(Type::getVoidTy(*Ctx), 353 DFSanSetLabelArgs, /*isVarArg=*/false); 354 DFSanNonzeroLabelFnTy = FunctionType::get( 355 Type::getVoidTy(*Ctx), ArrayRef<Type *>(), /*isVarArg=*/false); 356 357 if (GetArgTLSPtr) { 358 Type *ArgTLSTy = ArrayType::get(ShadowTy, 64); 359 ArgTLS = 0; 360 GetArgTLS = ConstantExpr::getIntToPtr( 361 ConstantInt::get(IntptrTy, uintptr_t(GetArgTLSPtr)), 362 PointerType::getUnqual( 363 FunctionType::get(PointerType::getUnqual(ArgTLSTy), (Type *)0))); 364 } 365 if (GetRetvalTLSPtr) { 366 RetvalTLS = 0; 367 GetRetvalTLS = ConstantExpr::getIntToPtr( 368 ConstantInt::get(IntptrTy, uintptr_t(GetRetvalTLSPtr)), 369 PointerType::getUnqual( 370 FunctionType::get(PointerType::getUnqual(ShadowTy), (Type *)0))); 371 } 372 373 ColdCallWeights = MDBuilder(*Ctx).createBranchWeights(1, 1000); 374 return true; 375} 376 377bool DataFlowSanitizer::isInstrumented(const Function *F) { 378 return !ABIList->isIn(*F, "uninstrumented"); 379} 380 381bool DataFlowSanitizer::isInstrumented(const GlobalAlias *GA) { 382 return !ABIList->isIn(*GA, "uninstrumented"); 383} 384 385DataFlowSanitizer::InstrumentedABI DataFlowSanitizer::getInstrumentedABI() { 386 return ClArgsABI ? IA_Args : IA_TLS; 387} 388 389DataFlowSanitizer::WrapperKind DataFlowSanitizer::getWrapperKind(Function *F) { 390 if (ABIList->isIn(*F, "functional")) 391 return WK_Functional; 392 if (ABIList->isIn(*F, "discard")) 393 return WK_Discard; 394 if (ABIList->isIn(*F, "custom")) 395 return WK_Custom; 396 397 return WK_Warning; 398} 399 400void DataFlowSanitizer::addGlobalNamePrefix(GlobalValue *GV) { 401 std::string GVName = GV->getName(), Prefix = "dfs$"; 402 GV->setName(Prefix + GVName); 403 404 // Try to change the name of the function in module inline asm. We only do 405 // this for specific asm directives, currently only ".symver", to try to avoid 406 // corrupting asm which happens to contain the symbol name as a substring. 407 // Note that the substitution for .symver assumes that the versioned symbol 408 // also has an instrumented name. 409 std::string Asm = GV->getParent()->getModuleInlineAsm(); 410 std::string SearchStr = ".symver " + GVName + ","; 411 size_t Pos = Asm.find(SearchStr); 412 if (Pos != std::string::npos) { 413 Asm.replace(Pos, SearchStr.size(), 414 ".symver " + Prefix + GVName + "," + Prefix); 415 GV->getParent()->setModuleInlineAsm(Asm); 416 } 417} 418 419Function * 420DataFlowSanitizer::buildWrapperFunction(Function *F, StringRef NewFName, 421 GlobalValue::LinkageTypes NewFLink, 422 FunctionType *NewFT) { 423 FunctionType *FT = F->getFunctionType(); 424 Function *NewF = Function::Create(NewFT, NewFLink, NewFName, 425 F->getParent()); 426 NewF->copyAttributesFrom(F); 427 NewF->removeAttributes( 428 AttributeSet::ReturnIndex, 429 AttributeFuncs::typeIncompatible(NewFT->getReturnType(), 430 AttributeSet::ReturnIndex)); 431 432 BasicBlock *BB = BasicBlock::Create(*Ctx, "entry", NewF); 433 std::vector<Value *> Args; 434 unsigned n = FT->getNumParams(); 435 for (Function::arg_iterator ai = NewF->arg_begin(); n != 0; ++ai, --n) 436 Args.push_back(&*ai); 437 CallInst *CI = CallInst::Create(F, Args, "", BB); 438 if (FT->getReturnType()->isVoidTy()) 439 ReturnInst::Create(*Ctx, BB); 440 else 441 ReturnInst::Create(*Ctx, CI, BB); 442 443 return NewF; 444} 445 446Constant *DataFlowSanitizer::getOrBuildTrampolineFunction(FunctionType *FT, 447 StringRef FName) { 448 FunctionType *FTT = getTrampolineFunctionType(FT); 449 Constant *C = Mod->getOrInsertFunction(FName, FTT); 450 Function *F = dyn_cast<Function>(C); 451 if (F && F->isDeclaration()) { 452 F->setLinkage(GlobalValue::LinkOnceODRLinkage); 453 BasicBlock *BB = BasicBlock::Create(*Ctx, "entry", F); 454 std::vector<Value *> Args; 455 Function::arg_iterator AI = F->arg_begin(); ++AI; 456 for (unsigned N = FT->getNumParams(); N != 0; ++AI, --N) 457 Args.push_back(&*AI); 458 CallInst *CI = 459 CallInst::Create(&F->getArgumentList().front(), Args, "", BB); 460 ReturnInst *RI; 461 if (FT->getReturnType()->isVoidTy()) 462 RI = ReturnInst::Create(*Ctx, BB); 463 else 464 RI = ReturnInst::Create(*Ctx, CI, BB); 465 466 DFSanFunction DFSF(*this, F, /*IsNativeABI=*/true); 467 Function::arg_iterator ValAI = F->arg_begin(), ShadowAI = AI; ++ValAI; 468 for (unsigned N = FT->getNumParams(); N != 0; ++ValAI, ++ShadowAI, --N) 469 DFSF.ValShadowMap[ValAI] = ShadowAI; 470 DFSanVisitor(DFSF).visitCallInst(*CI); 471 if (!FT->getReturnType()->isVoidTy()) 472 new StoreInst(DFSF.getShadow(RI->getReturnValue()), 473 &F->getArgumentList().back(), RI); 474 } 475 476 return C; 477} 478 479bool DataFlowSanitizer::runOnModule(Module &M) { 480 if (!DL) 481 return false; 482 483 if (ABIList->isIn(M, "skip")) 484 return false; 485 486 if (!GetArgTLSPtr) { 487 Type *ArgTLSTy = ArrayType::get(ShadowTy, 64); 488 ArgTLS = Mod->getOrInsertGlobal("__dfsan_arg_tls", ArgTLSTy); 489 if (GlobalVariable *G = dyn_cast<GlobalVariable>(ArgTLS)) 490 G->setThreadLocalMode(GlobalVariable::InitialExecTLSModel); 491 } 492 if (!GetRetvalTLSPtr) { 493 RetvalTLS = Mod->getOrInsertGlobal("__dfsan_retval_tls", ShadowTy); 494 if (GlobalVariable *G = dyn_cast<GlobalVariable>(RetvalTLS)) 495 G->setThreadLocalMode(GlobalVariable::InitialExecTLSModel); 496 } 497 498 DFSanUnionFn = Mod->getOrInsertFunction("__dfsan_union", DFSanUnionFnTy); 499 if (Function *F = dyn_cast<Function>(DFSanUnionFn)) { 500 F->addAttribute(AttributeSet::FunctionIndex, Attribute::ReadNone); 501 F->addAttribute(AttributeSet::ReturnIndex, Attribute::ZExt); 502 F->addAttribute(1, Attribute::ZExt); 503 F->addAttribute(2, Attribute::ZExt); 504 } 505 DFSanUnionLoadFn = 506 Mod->getOrInsertFunction("__dfsan_union_load", DFSanUnionLoadFnTy); 507 if (Function *F = dyn_cast<Function>(DFSanUnionLoadFn)) { 508 F->addAttribute(AttributeSet::ReturnIndex, Attribute::ZExt); 509 } 510 DFSanUnimplementedFn = 511 Mod->getOrInsertFunction("__dfsan_unimplemented", DFSanUnimplementedFnTy); 512 DFSanSetLabelFn = 513 Mod->getOrInsertFunction("__dfsan_set_label", DFSanSetLabelFnTy); 514 if (Function *F = dyn_cast<Function>(DFSanSetLabelFn)) { 515 F->addAttribute(1, Attribute::ZExt); 516 } 517 DFSanNonzeroLabelFn = 518 Mod->getOrInsertFunction("__dfsan_nonzero_label", DFSanNonzeroLabelFnTy); 519 520 std::vector<Function *> FnsToInstrument; 521 llvm::SmallPtrSet<Function *, 2> FnsWithNativeABI; 522 for (Module::iterator i = M.begin(), e = M.end(); i != e; ++i) { 523 if (!i->isIntrinsic() && 524 i != DFSanUnionFn && 525 i != DFSanUnionLoadFn && 526 i != DFSanUnimplementedFn && 527 i != DFSanSetLabelFn && 528 i != DFSanNonzeroLabelFn) 529 FnsToInstrument.push_back(&*i); 530 } 531 532 // Give function aliases prefixes when necessary, and build wrappers where the 533 // instrumentedness is inconsistent. 534 for (Module::alias_iterator i = M.alias_begin(), e = M.alias_end(); i != e;) { 535 GlobalAlias *GA = &*i; 536 ++i; 537 // Don't stop on weak. We assume people aren't playing games with the 538 // instrumentedness of overridden weak aliases. 539 if (Function *F = dyn_cast<Function>( 540 GA->resolveAliasedGlobal(/*stopOnWeak=*/false))) { 541 bool GAInst = isInstrumented(GA), FInst = isInstrumented(F); 542 if (GAInst && FInst) { 543 addGlobalNamePrefix(GA); 544 } else if (GAInst != FInst) { 545 // Non-instrumented alias of an instrumented function, or vice versa. 546 // Replace the alias with a native-ABI wrapper of the aliasee. The pass 547 // below will take care of instrumenting it. 548 Function *NewF = 549 buildWrapperFunction(F, "", GA->getLinkage(), F->getFunctionType()); 550 GA->replaceAllUsesWith(NewF); 551 NewF->takeName(GA); 552 GA->eraseFromParent(); 553 FnsToInstrument.push_back(NewF); 554 } 555 } 556 } 557 558 AttrBuilder B; 559 B.addAttribute(Attribute::ReadOnly).addAttribute(Attribute::ReadNone); 560 ReadOnlyNoneAttrs = AttributeSet::get(*Ctx, AttributeSet::FunctionIndex, B); 561 562 // First, change the ABI of every function in the module. ABI-listed 563 // functions keep their original ABI and get a wrapper function. 564 for (std::vector<Function *>::iterator i = FnsToInstrument.begin(), 565 e = FnsToInstrument.end(); 566 i != e; ++i) { 567 Function &F = **i; 568 FunctionType *FT = F.getFunctionType(); 569 570 bool IsZeroArgsVoidRet = (FT->getNumParams() == 0 && !FT->isVarArg() && 571 FT->getReturnType()->isVoidTy()); 572 573 if (isInstrumented(&F)) { 574 // Instrumented functions get a 'dfs$' prefix. This allows us to more 575 // easily identify cases of mismatching ABIs. 576 if (getInstrumentedABI() == IA_Args && !IsZeroArgsVoidRet) { 577 FunctionType *NewFT = getArgsFunctionType(FT); 578 Function *NewF = Function::Create(NewFT, F.getLinkage(), "", &M); 579 NewF->copyAttributesFrom(&F); 580 NewF->removeAttributes( 581 AttributeSet::ReturnIndex, 582 AttributeFuncs::typeIncompatible(NewFT->getReturnType(), 583 AttributeSet::ReturnIndex)); 584 for (Function::arg_iterator FArg = F.arg_begin(), 585 NewFArg = NewF->arg_begin(), 586 FArgEnd = F.arg_end(); 587 FArg != FArgEnd; ++FArg, ++NewFArg) { 588 FArg->replaceAllUsesWith(NewFArg); 589 } 590 NewF->getBasicBlockList().splice(NewF->begin(), F.getBasicBlockList()); 591 592 for (Function::use_iterator ui = F.use_begin(), ue = F.use_end(); 593 ui != ue;) { 594 BlockAddress *BA = dyn_cast<BlockAddress>(ui.getUse().getUser()); 595 ++ui; 596 if (BA) { 597 BA->replaceAllUsesWith( 598 BlockAddress::get(NewF, BA->getBasicBlock())); 599 delete BA; 600 } 601 } 602 F.replaceAllUsesWith( 603 ConstantExpr::getBitCast(NewF, PointerType::getUnqual(FT))); 604 NewF->takeName(&F); 605 F.eraseFromParent(); 606 *i = NewF; 607 addGlobalNamePrefix(NewF); 608 } else { 609 addGlobalNamePrefix(&F); 610 } 611 // Hopefully, nobody will try to indirectly call a vararg 612 // function... yet. 613 } else if (FT->isVarArg()) { 614 UnwrappedFnMap[&F] = &F; 615 *i = 0; 616 } else if (!IsZeroArgsVoidRet || getWrapperKind(&F) == WK_Custom) { 617 // Build a wrapper function for F. The wrapper simply calls F, and is 618 // added to FnsToInstrument so that any instrumentation according to its 619 // WrapperKind is done in the second pass below. 620 FunctionType *NewFT = getInstrumentedABI() == IA_Args 621 ? getArgsFunctionType(FT) 622 : FT; 623 Function *NewF = buildWrapperFunction( 624 &F, std::string("dfsw$") + std::string(F.getName()), 625 GlobalValue::LinkOnceODRLinkage, NewFT); 626 if (getInstrumentedABI() == IA_TLS) 627 NewF->removeAttributes(AttributeSet::FunctionIndex, ReadOnlyNoneAttrs); 628 629 Value *WrappedFnCst = 630 ConstantExpr::getBitCast(NewF, PointerType::getUnqual(FT)); 631 F.replaceAllUsesWith(WrappedFnCst); 632 UnwrappedFnMap[WrappedFnCst] = &F; 633 *i = NewF; 634 635 if (!F.isDeclaration()) { 636 // This function is probably defining an interposition of an 637 // uninstrumented function and hence needs to keep the original ABI. 638 // But any functions it may call need to use the instrumented ABI, so 639 // we instrument it in a mode which preserves the original ABI. 640 FnsWithNativeABI.insert(&F); 641 642 // This code needs to rebuild the iterators, as they may be invalidated 643 // by the push_back, taking care that the new range does not include 644 // any functions added by this code. 645 size_t N = i - FnsToInstrument.begin(), 646 Count = e - FnsToInstrument.begin(); 647 FnsToInstrument.push_back(&F); 648 i = FnsToInstrument.begin() + N; 649 e = FnsToInstrument.begin() + Count; 650 } 651 } 652 } 653 654 for (std::vector<Function *>::iterator i = FnsToInstrument.begin(), 655 e = FnsToInstrument.end(); 656 i != e; ++i) { 657 if (!*i || (*i)->isDeclaration()) 658 continue; 659 660 removeUnreachableBlocks(**i); 661 662 DFSanFunction DFSF(*this, *i, FnsWithNativeABI.count(*i)); 663 664 // DFSanVisitor may create new basic blocks, which confuses df_iterator. 665 // Build a copy of the list before iterating over it. 666 llvm::SmallVector<BasicBlock *, 4> BBList; 667 std::copy(df_begin(&(*i)->getEntryBlock()), df_end(&(*i)->getEntryBlock()), 668 std::back_inserter(BBList)); 669 670 for (llvm::SmallVector<BasicBlock *, 4>::iterator i = BBList.begin(), 671 e = BBList.end(); 672 i != e; ++i) { 673 Instruction *Inst = &(*i)->front(); 674 while (1) { 675 // DFSanVisitor may split the current basic block, changing the current 676 // instruction's next pointer and moving the next instruction to the 677 // tail block from which we should continue. 678 Instruction *Next = Inst->getNextNode(); 679 // DFSanVisitor may delete Inst, so keep track of whether it was a 680 // terminator. 681 bool IsTerminator = isa<TerminatorInst>(Inst); 682 if (!DFSF.SkipInsts.count(Inst)) 683 DFSanVisitor(DFSF).visit(Inst); 684 if (IsTerminator) 685 break; 686 Inst = Next; 687 } 688 } 689 690 // We will not necessarily be able to compute the shadow for every phi node 691 // until we have visited every block. Therefore, the code that handles phi 692 // nodes adds them to the PHIFixups list so that they can be properly 693 // handled here. 694 for (std::vector<std::pair<PHINode *, PHINode *> >::iterator 695 i = DFSF.PHIFixups.begin(), 696 e = DFSF.PHIFixups.end(); 697 i != e; ++i) { 698 for (unsigned val = 0, n = i->first->getNumIncomingValues(); val != n; 699 ++val) { 700 i->second->setIncomingValue( 701 val, DFSF.getShadow(i->first->getIncomingValue(val))); 702 } 703 } 704 705 // -dfsan-debug-nonzero-labels will split the CFG in all kinds of crazy 706 // places (i.e. instructions in basic blocks we haven't even begun visiting 707 // yet). To make our life easier, do this work in a pass after the main 708 // instrumentation. 709 if (ClDebugNonzeroLabels) { 710 for (DenseSet<Value *>::iterator i = DFSF.NonZeroChecks.begin(), 711 e = DFSF.NonZeroChecks.end(); 712 i != e; ++i) { 713 Instruction *Pos; 714 if (Instruction *I = dyn_cast<Instruction>(*i)) 715 Pos = I->getNextNode(); 716 else 717 Pos = DFSF.F->getEntryBlock().begin(); 718 while (isa<PHINode>(Pos) || isa<AllocaInst>(Pos)) 719 Pos = Pos->getNextNode(); 720 IRBuilder<> IRB(Pos); 721 Instruction *NeInst = cast<Instruction>( 722 IRB.CreateICmpNE(*i, DFSF.DFS.ZeroShadow)); 723 BranchInst *BI = cast<BranchInst>(SplitBlockAndInsertIfThen( 724 NeInst, /*Unreachable=*/ false, ColdCallWeights)); 725 IRBuilder<> ThenIRB(BI); 726 ThenIRB.CreateCall(DFSF.DFS.DFSanNonzeroLabelFn); 727 } 728 } 729 } 730 731 return false; 732} 733 734Value *DFSanFunction::getArgTLSPtr() { 735 if (ArgTLSPtr) 736 return ArgTLSPtr; 737 if (DFS.ArgTLS) 738 return ArgTLSPtr = DFS.ArgTLS; 739 740 IRBuilder<> IRB(F->getEntryBlock().begin()); 741 return ArgTLSPtr = IRB.CreateCall(DFS.GetArgTLS); 742} 743 744Value *DFSanFunction::getRetvalTLS() { 745 if (RetvalTLSPtr) 746 return RetvalTLSPtr; 747 if (DFS.RetvalTLS) 748 return RetvalTLSPtr = DFS.RetvalTLS; 749 750 IRBuilder<> IRB(F->getEntryBlock().begin()); 751 return RetvalTLSPtr = IRB.CreateCall(DFS.GetRetvalTLS); 752} 753 754Value *DFSanFunction::getArgTLS(unsigned Idx, Instruction *Pos) { 755 IRBuilder<> IRB(Pos); 756 return IRB.CreateConstGEP2_64(getArgTLSPtr(), 0, Idx); 757} 758 759Value *DFSanFunction::getShadow(Value *V) { 760 if (!isa<Argument>(V) && !isa<Instruction>(V)) 761 return DFS.ZeroShadow; 762 Value *&Shadow = ValShadowMap[V]; 763 if (!Shadow) { 764 if (Argument *A = dyn_cast<Argument>(V)) { 765 if (IsNativeABI) 766 return DFS.ZeroShadow; 767 switch (IA) { 768 case DataFlowSanitizer::IA_TLS: { 769 Value *ArgTLSPtr = getArgTLSPtr(); 770 Instruction *ArgTLSPos = 771 DFS.ArgTLS ? &*F->getEntryBlock().begin() 772 : cast<Instruction>(ArgTLSPtr)->getNextNode(); 773 IRBuilder<> IRB(ArgTLSPos); 774 Shadow = IRB.CreateLoad(getArgTLS(A->getArgNo(), ArgTLSPos)); 775 break; 776 } 777 case DataFlowSanitizer::IA_Args: { 778 unsigned ArgIdx = A->getArgNo() + F->getArgumentList().size() / 2; 779 Function::arg_iterator i = F->arg_begin(); 780 while (ArgIdx--) 781 ++i; 782 Shadow = i; 783 assert(Shadow->getType() == DFS.ShadowTy); 784 break; 785 } 786 } 787 NonZeroChecks.insert(Shadow); 788 } else { 789 Shadow = DFS.ZeroShadow; 790 } 791 } 792 return Shadow; 793} 794 795void DFSanFunction::setShadow(Instruction *I, Value *Shadow) { 796 assert(!ValShadowMap.count(I)); 797 assert(Shadow->getType() == DFS.ShadowTy); 798 ValShadowMap[I] = Shadow; 799} 800 801Value *DataFlowSanitizer::getShadowAddress(Value *Addr, Instruction *Pos) { 802 assert(Addr != RetvalTLS && "Reinstrumenting?"); 803 IRBuilder<> IRB(Pos); 804 return IRB.CreateIntToPtr( 805 IRB.CreateMul( 806 IRB.CreateAnd(IRB.CreatePtrToInt(Addr, IntptrTy), ShadowPtrMask), 807 ShadowPtrMul), 808 ShadowPtrTy); 809} 810 811// Generates IR to compute the union of the two given shadows, inserting it 812// before Pos. Returns the computed union Value. 813Value *DataFlowSanitizer::combineShadows(Value *V1, Value *V2, 814 Instruction *Pos) { 815 if (V1 == ZeroShadow) 816 return V2; 817 if (V2 == ZeroShadow) 818 return V1; 819 if (V1 == V2) 820 return V1; 821 IRBuilder<> IRB(Pos); 822 BasicBlock *Head = Pos->getParent(); 823 Value *Ne = IRB.CreateICmpNE(V1, V2); 824 Instruction *NeInst = dyn_cast<Instruction>(Ne); 825 if (NeInst) { 826 BranchInst *BI = cast<BranchInst>(SplitBlockAndInsertIfThen( 827 NeInst, /*Unreachable=*/ false, ColdCallWeights)); 828 IRBuilder<> ThenIRB(BI); 829 CallInst *Call = ThenIRB.CreateCall2(DFSanUnionFn, V1, V2); 830 Call->addAttribute(AttributeSet::ReturnIndex, Attribute::ZExt); 831 Call->addAttribute(1, Attribute::ZExt); 832 Call->addAttribute(2, Attribute::ZExt); 833 834 BasicBlock *Tail = BI->getSuccessor(0); 835 PHINode *Phi = PHINode::Create(ShadowTy, 2, "", Tail->begin()); 836 Phi->addIncoming(Call, Call->getParent()); 837 Phi->addIncoming(V1, Head); 838 Pos = Phi; 839 return Phi; 840 } else { 841 assert(0 && "todo"); 842 return 0; 843 } 844} 845 846// A convenience function which folds the shadows of each of the operands 847// of the provided instruction Inst, inserting the IR before Inst. Returns 848// the computed union Value. 849Value *DFSanFunction::combineOperandShadows(Instruction *Inst) { 850 if (Inst->getNumOperands() == 0) 851 return DFS.ZeroShadow; 852 853 Value *Shadow = getShadow(Inst->getOperand(0)); 854 for (unsigned i = 1, n = Inst->getNumOperands(); i != n; ++i) { 855 Shadow = DFS.combineShadows(Shadow, getShadow(Inst->getOperand(i)), Inst); 856 } 857 return Shadow; 858} 859 860void DFSanVisitor::visitOperandShadowInst(Instruction &I) { 861 Value *CombinedShadow = DFSF.combineOperandShadows(&I); 862 DFSF.setShadow(&I, CombinedShadow); 863} 864 865// Generates IR to load shadow corresponding to bytes [Addr, Addr+Size), where 866// Addr has alignment Align, and take the union of each of those shadows. 867Value *DFSanFunction::loadShadow(Value *Addr, uint64_t Size, uint64_t Align, 868 Instruction *Pos) { 869 if (AllocaInst *AI = dyn_cast<AllocaInst>(Addr)) { 870 llvm::DenseMap<AllocaInst *, AllocaInst *>::iterator i = 871 AllocaShadowMap.find(AI); 872 if (i != AllocaShadowMap.end()) { 873 IRBuilder<> IRB(Pos); 874 return IRB.CreateLoad(i->second); 875 } 876 } 877 878 uint64_t ShadowAlign = Align * DFS.ShadowWidth / 8; 879 SmallVector<Value *, 2> Objs; 880 GetUnderlyingObjects(Addr, Objs, DFS.DL); 881 bool AllConstants = true; 882 for (SmallVector<Value *, 2>::iterator i = Objs.begin(), e = Objs.end(); 883 i != e; ++i) { 884 if (isa<Function>(*i) || isa<BlockAddress>(*i)) 885 continue; 886 if (isa<GlobalVariable>(*i) && cast<GlobalVariable>(*i)->isConstant()) 887 continue; 888 889 AllConstants = false; 890 break; 891 } 892 if (AllConstants) 893 return DFS.ZeroShadow; 894 895 Value *ShadowAddr = DFS.getShadowAddress(Addr, Pos); 896 switch (Size) { 897 case 0: 898 return DFS.ZeroShadow; 899 case 1: { 900 LoadInst *LI = new LoadInst(ShadowAddr, "", Pos); 901 LI->setAlignment(ShadowAlign); 902 return LI; 903 } 904 case 2: { 905 IRBuilder<> IRB(Pos); 906 Value *ShadowAddr1 = 907 IRB.CreateGEP(ShadowAddr, ConstantInt::get(DFS.IntptrTy, 1)); 908 return DFS.combineShadows(IRB.CreateAlignedLoad(ShadowAddr, ShadowAlign), 909 IRB.CreateAlignedLoad(ShadowAddr1, ShadowAlign), 910 Pos); 911 } 912 } 913 if (Size % (64 / DFS.ShadowWidth) == 0) { 914 // Fast path for the common case where each byte has identical shadow: load 915 // shadow 64 bits at a time, fall out to a __dfsan_union_load call if any 916 // shadow is non-equal. 917 BasicBlock *FallbackBB = BasicBlock::Create(*DFS.Ctx, "", F); 918 IRBuilder<> FallbackIRB(FallbackBB); 919 CallInst *FallbackCall = FallbackIRB.CreateCall2( 920 DFS.DFSanUnionLoadFn, ShadowAddr, ConstantInt::get(DFS.IntptrTy, Size)); 921 FallbackCall->addAttribute(AttributeSet::ReturnIndex, Attribute::ZExt); 922 923 // Compare each of the shadows stored in the loaded 64 bits to each other, 924 // by computing (WideShadow rotl ShadowWidth) == WideShadow. 925 IRBuilder<> IRB(Pos); 926 Value *WideAddr = 927 IRB.CreateBitCast(ShadowAddr, Type::getInt64PtrTy(*DFS.Ctx)); 928 Value *WideShadow = IRB.CreateAlignedLoad(WideAddr, ShadowAlign); 929 Value *TruncShadow = IRB.CreateTrunc(WideShadow, DFS.ShadowTy); 930 Value *ShlShadow = IRB.CreateShl(WideShadow, DFS.ShadowWidth); 931 Value *ShrShadow = IRB.CreateLShr(WideShadow, 64 - DFS.ShadowWidth); 932 Value *RotShadow = IRB.CreateOr(ShlShadow, ShrShadow); 933 Value *ShadowsEq = IRB.CreateICmpEQ(WideShadow, RotShadow); 934 935 BasicBlock *Head = Pos->getParent(); 936 BasicBlock *Tail = Head->splitBasicBlock(Pos); 937 // In the following code LastBr will refer to the previous basic block's 938 // conditional branch instruction, whose true successor is fixed up to point 939 // to the next block during the loop below or to the tail after the final 940 // iteration. 941 BranchInst *LastBr = BranchInst::Create(FallbackBB, FallbackBB, ShadowsEq); 942 ReplaceInstWithInst(Head->getTerminator(), LastBr); 943 944 for (uint64_t Ofs = 64 / DFS.ShadowWidth; Ofs != Size; 945 Ofs += 64 / DFS.ShadowWidth) { 946 BasicBlock *NextBB = BasicBlock::Create(*DFS.Ctx, "", F); 947 IRBuilder<> NextIRB(NextBB); 948 WideAddr = NextIRB.CreateGEP(WideAddr, ConstantInt::get(DFS.IntptrTy, 1)); 949 Value *NextWideShadow = NextIRB.CreateAlignedLoad(WideAddr, ShadowAlign); 950 ShadowsEq = NextIRB.CreateICmpEQ(WideShadow, NextWideShadow); 951 LastBr->setSuccessor(0, NextBB); 952 LastBr = NextIRB.CreateCondBr(ShadowsEq, FallbackBB, FallbackBB); 953 } 954 955 LastBr->setSuccessor(0, Tail); 956 FallbackIRB.CreateBr(Tail); 957 PHINode *Shadow = PHINode::Create(DFS.ShadowTy, 2, "", &Tail->front()); 958 Shadow->addIncoming(FallbackCall, FallbackBB); 959 Shadow->addIncoming(TruncShadow, LastBr->getParent()); 960 return Shadow; 961 } 962 963 IRBuilder<> IRB(Pos); 964 CallInst *FallbackCall = IRB.CreateCall2( 965 DFS.DFSanUnionLoadFn, ShadowAddr, ConstantInt::get(DFS.IntptrTy, Size)); 966 FallbackCall->addAttribute(AttributeSet::ReturnIndex, Attribute::ZExt); 967 return FallbackCall; 968} 969 970void DFSanVisitor::visitLoadInst(LoadInst &LI) { 971 uint64_t Size = DFSF.DFS.DL->getTypeStoreSize(LI.getType()); 972 uint64_t Align; 973 if (ClPreserveAlignment) { 974 Align = LI.getAlignment(); 975 if (Align == 0) 976 Align = DFSF.DFS.DL->getABITypeAlignment(LI.getType()); 977 } else { 978 Align = 1; 979 } 980 IRBuilder<> IRB(&LI); 981 Value *LoadedShadow = 982 DFSF.loadShadow(LI.getPointerOperand(), Size, Align, &LI); 983 Value *PtrShadow = DFSF.getShadow(LI.getPointerOperand()); 984 Value *CombinedShadow = DFSF.DFS.combineShadows(LoadedShadow, PtrShadow, &LI); 985 if (CombinedShadow != DFSF.DFS.ZeroShadow) 986 DFSF.NonZeroChecks.insert(CombinedShadow); 987 988 DFSF.setShadow(&LI, CombinedShadow); 989} 990 991void DFSanFunction::storeShadow(Value *Addr, uint64_t Size, uint64_t Align, 992 Value *Shadow, Instruction *Pos) { 993 if (AllocaInst *AI = dyn_cast<AllocaInst>(Addr)) { 994 llvm::DenseMap<AllocaInst *, AllocaInst *>::iterator i = 995 AllocaShadowMap.find(AI); 996 if (i != AllocaShadowMap.end()) { 997 IRBuilder<> IRB(Pos); 998 IRB.CreateStore(Shadow, i->second); 999 return; 1000 } 1001 } 1002 1003 uint64_t ShadowAlign = Align * DFS.ShadowWidth / 8; 1004 IRBuilder<> IRB(Pos); 1005 Value *ShadowAddr = DFS.getShadowAddress(Addr, Pos); 1006 if (Shadow == DFS.ZeroShadow) { 1007 IntegerType *ShadowTy = IntegerType::get(*DFS.Ctx, Size * DFS.ShadowWidth); 1008 Value *ExtZeroShadow = ConstantInt::get(ShadowTy, 0); 1009 Value *ExtShadowAddr = 1010 IRB.CreateBitCast(ShadowAddr, PointerType::getUnqual(ShadowTy)); 1011 IRB.CreateAlignedStore(ExtZeroShadow, ExtShadowAddr, ShadowAlign); 1012 return; 1013 } 1014 1015 const unsigned ShadowVecSize = 128 / DFS.ShadowWidth; 1016 uint64_t Offset = 0; 1017 if (Size >= ShadowVecSize) { 1018 VectorType *ShadowVecTy = VectorType::get(DFS.ShadowTy, ShadowVecSize); 1019 Value *ShadowVec = UndefValue::get(ShadowVecTy); 1020 for (unsigned i = 0; i != ShadowVecSize; ++i) { 1021 ShadowVec = IRB.CreateInsertElement( 1022 ShadowVec, Shadow, ConstantInt::get(Type::getInt32Ty(*DFS.Ctx), i)); 1023 } 1024 Value *ShadowVecAddr = 1025 IRB.CreateBitCast(ShadowAddr, PointerType::getUnqual(ShadowVecTy)); 1026 do { 1027 Value *CurShadowVecAddr = IRB.CreateConstGEP1_32(ShadowVecAddr, Offset); 1028 IRB.CreateAlignedStore(ShadowVec, CurShadowVecAddr, ShadowAlign); 1029 Size -= ShadowVecSize; 1030 ++Offset; 1031 } while (Size >= ShadowVecSize); 1032 Offset *= ShadowVecSize; 1033 } 1034 while (Size > 0) { 1035 Value *CurShadowAddr = IRB.CreateConstGEP1_32(ShadowAddr, Offset); 1036 IRB.CreateAlignedStore(Shadow, CurShadowAddr, ShadowAlign); 1037 --Size; 1038 ++Offset; 1039 } 1040} 1041 1042void DFSanVisitor::visitStoreInst(StoreInst &SI) { 1043 uint64_t Size = 1044 DFSF.DFS.DL->getTypeStoreSize(SI.getValueOperand()->getType()); 1045 uint64_t Align; 1046 if (ClPreserveAlignment) { 1047 Align = SI.getAlignment(); 1048 if (Align == 0) 1049 Align = DFSF.DFS.DL->getABITypeAlignment(SI.getValueOperand()->getType()); 1050 } else { 1051 Align = 1; 1052 } 1053 DFSF.storeShadow(SI.getPointerOperand(), Size, Align, 1054 DFSF.getShadow(SI.getValueOperand()), &SI); 1055} 1056 1057void DFSanVisitor::visitBinaryOperator(BinaryOperator &BO) { 1058 visitOperandShadowInst(BO); 1059} 1060 1061void DFSanVisitor::visitCastInst(CastInst &CI) { visitOperandShadowInst(CI); } 1062 1063void DFSanVisitor::visitCmpInst(CmpInst &CI) { visitOperandShadowInst(CI); } 1064 1065void DFSanVisitor::visitGetElementPtrInst(GetElementPtrInst &GEPI) { 1066 visitOperandShadowInst(GEPI); 1067} 1068 1069void DFSanVisitor::visitExtractElementInst(ExtractElementInst &I) { 1070 visitOperandShadowInst(I); 1071} 1072 1073void DFSanVisitor::visitInsertElementInst(InsertElementInst &I) { 1074 visitOperandShadowInst(I); 1075} 1076 1077void DFSanVisitor::visitShuffleVectorInst(ShuffleVectorInst &I) { 1078 visitOperandShadowInst(I); 1079} 1080 1081void DFSanVisitor::visitExtractValueInst(ExtractValueInst &I) { 1082 visitOperandShadowInst(I); 1083} 1084 1085void DFSanVisitor::visitInsertValueInst(InsertValueInst &I) { 1086 visitOperandShadowInst(I); 1087} 1088 1089void DFSanVisitor::visitAllocaInst(AllocaInst &I) { 1090 bool AllLoadsStores = true; 1091 for (Instruction::use_iterator i = I.use_begin(), e = I.use_end(); i != e; 1092 ++i) { 1093 if (isa<LoadInst>(*i)) 1094 continue; 1095 1096 if (StoreInst *SI = dyn_cast<StoreInst>(*i)) { 1097 if (SI->getPointerOperand() == &I) 1098 continue; 1099 } 1100 1101 AllLoadsStores = false; 1102 break; 1103 } 1104 if (AllLoadsStores) { 1105 IRBuilder<> IRB(&I); 1106 DFSF.AllocaShadowMap[&I] = IRB.CreateAlloca(DFSF.DFS.ShadowTy); 1107 } 1108 DFSF.setShadow(&I, DFSF.DFS.ZeroShadow); 1109} 1110 1111void DFSanVisitor::visitSelectInst(SelectInst &I) { 1112 Value *CondShadow = DFSF.getShadow(I.getCondition()); 1113 Value *TrueShadow = DFSF.getShadow(I.getTrueValue()); 1114 Value *FalseShadow = DFSF.getShadow(I.getFalseValue()); 1115 1116 if (isa<VectorType>(I.getCondition()->getType())) { 1117 DFSF.setShadow( 1118 &I, DFSF.DFS.combineShadows( 1119 CondShadow, 1120 DFSF.DFS.combineShadows(TrueShadow, FalseShadow, &I), &I)); 1121 } else { 1122 Value *ShadowSel; 1123 if (TrueShadow == FalseShadow) { 1124 ShadowSel = TrueShadow; 1125 } else { 1126 ShadowSel = 1127 SelectInst::Create(I.getCondition(), TrueShadow, FalseShadow, "", &I); 1128 } 1129 DFSF.setShadow(&I, DFSF.DFS.combineShadows(CondShadow, ShadowSel, &I)); 1130 } 1131} 1132 1133void DFSanVisitor::visitMemSetInst(MemSetInst &I) { 1134 IRBuilder<> IRB(&I); 1135 Value *ValShadow = DFSF.getShadow(I.getValue()); 1136 IRB.CreateCall3( 1137 DFSF.DFS.DFSanSetLabelFn, ValShadow, 1138 IRB.CreateBitCast(I.getDest(), Type::getInt8PtrTy(*DFSF.DFS.Ctx)), 1139 IRB.CreateZExtOrTrunc(I.getLength(), DFSF.DFS.IntptrTy)); 1140} 1141 1142void DFSanVisitor::visitMemTransferInst(MemTransferInst &I) { 1143 IRBuilder<> IRB(&I); 1144 Value *DestShadow = DFSF.DFS.getShadowAddress(I.getDest(), &I); 1145 Value *SrcShadow = DFSF.DFS.getShadowAddress(I.getSource(), &I); 1146 Value *LenShadow = IRB.CreateMul( 1147 I.getLength(), 1148 ConstantInt::get(I.getLength()->getType(), DFSF.DFS.ShadowWidth / 8)); 1149 Value *AlignShadow; 1150 if (ClPreserveAlignment) { 1151 AlignShadow = IRB.CreateMul(I.getAlignmentCst(), 1152 ConstantInt::get(I.getAlignmentCst()->getType(), 1153 DFSF.DFS.ShadowWidth / 8)); 1154 } else { 1155 AlignShadow = ConstantInt::get(I.getAlignmentCst()->getType(), 1156 DFSF.DFS.ShadowWidth / 8); 1157 } 1158 Type *Int8Ptr = Type::getInt8PtrTy(*DFSF.DFS.Ctx); 1159 DestShadow = IRB.CreateBitCast(DestShadow, Int8Ptr); 1160 SrcShadow = IRB.CreateBitCast(SrcShadow, Int8Ptr); 1161 IRB.CreateCall5(I.getCalledValue(), DestShadow, SrcShadow, LenShadow, 1162 AlignShadow, I.getVolatileCst()); 1163} 1164 1165void DFSanVisitor::visitReturnInst(ReturnInst &RI) { 1166 if (!DFSF.IsNativeABI && RI.getReturnValue()) { 1167 switch (DFSF.IA) { 1168 case DataFlowSanitizer::IA_TLS: { 1169 Value *S = DFSF.getShadow(RI.getReturnValue()); 1170 IRBuilder<> IRB(&RI); 1171 IRB.CreateStore(S, DFSF.getRetvalTLS()); 1172 break; 1173 } 1174 case DataFlowSanitizer::IA_Args: { 1175 IRBuilder<> IRB(&RI); 1176 Type *RT = DFSF.F->getFunctionType()->getReturnType(); 1177 Value *InsVal = 1178 IRB.CreateInsertValue(UndefValue::get(RT), RI.getReturnValue(), 0); 1179 Value *InsShadow = 1180 IRB.CreateInsertValue(InsVal, DFSF.getShadow(RI.getReturnValue()), 1); 1181 RI.setOperand(0, InsShadow); 1182 break; 1183 } 1184 } 1185 } 1186} 1187 1188void DFSanVisitor::visitCallSite(CallSite CS) { 1189 Function *F = CS.getCalledFunction(); 1190 if ((F && F->isIntrinsic()) || isa<InlineAsm>(CS.getCalledValue())) { 1191 visitOperandShadowInst(*CS.getInstruction()); 1192 return; 1193 } 1194 1195 IRBuilder<> IRB(CS.getInstruction()); 1196 1197 DenseMap<Value *, Function *>::iterator i = 1198 DFSF.DFS.UnwrappedFnMap.find(CS.getCalledValue()); 1199 if (i != DFSF.DFS.UnwrappedFnMap.end()) { 1200 Function *F = i->second; 1201 switch (DFSF.DFS.getWrapperKind(F)) { 1202 case DataFlowSanitizer::WK_Warning: { 1203 CS.setCalledFunction(F); 1204 IRB.CreateCall(DFSF.DFS.DFSanUnimplementedFn, 1205 IRB.CreateGlobalStringPtr(F->getName())); 1206 DFSF.setShadow(CS.getInstruction(), DFSF.DFS.ZeroShadow); 1207 return; 1208 } 1209 case DataFlowSanitizer::WK_Discard: { 1210 CS.setCalledFunction(F); 1211 DFSF.setShadow(CS.getInstruction(), DFSF.DFS.ZeroShadow); 1212 return; 1213 } 1214 case DataFlowSanitizer::WK_Functional: { 1215 CS.setCalledFunction(F); 1216 visitOperandShadowInst(*CS.getInstruction()); 1217 return; 1218 } 1219 case DataFlowSanitizer::WK_Custom: { 1220 // Don't try to handle invokes of custom functions, it's too complicated. 1221 // Instead, invoke the dfsw$ wrapper, which will in turn call the __dfsw_ 1222 // wrapper. 1223 if (CallInst *CI = dyn_cast<CallInst>(CS.getInstruction())) { 1224 FunctionType *FT = F->getFunctionType(); 1225 FunctionType *CustomFT = DFSF.DFS.getCustomFunctionType(FT); 1226 std::string CustomFName = "__dfsw_"; 1227 CustomFName += F->getName(); 1228 Constant *CustomF = 1229 DFSF.DFS.Mod->getOrInsertFunction(CustomFName, CustomFT); 1230 if (Function *CustomFn = dyn_cast<Function>(CustomF)) { 1231 CustomFn->copyAttributesFrom(F); 1232 1233 // Custom functions returning non-void will write to the return label. 1234 if (!FT->getReturnType()->isVoidTy()) { 1235 CustomFn->removeAttributes(AttributeSet::FunctionIndex, 1236 DFSF.DFS.ReadOnlyNoneAttrs); 1237 } 1238 } 1239 1240 std::vector<Value *> Args; 1241 1242 CallSite::arg_iterator i = CS.arg_begin(); 1243 for (unsigned n = FT->getNumParams(); n != 0; ++i, --n) { 1244 Type *T = (*i)->getType(); 1245 FunctionType *ParamFT; 1246 if (isa<PointerType>(T) && 1247 (ParamFT = dyn_cast<FunctionType>( 1248 cast<PointerType>(T)->getElementType()))) { 1249 std::string TName = "dfst"; 1250 TName += utostr(FT->getNumParams() - n); 1251 TName += "$"; 1252 TName += F->getName(); 1253 Constant *T = DFSF.DFS.getOrBuildTrampolineFunction(ParamFT, TName); 1254 Args.push_back(T); 1255 Args.push_back( 1256 IRB.CreateBitCast(*i, Type::getInt8PtrTy(*DFSF.DFS.Ctx))); 1257 } else { 1258 Args.push_back(*i); 1259 } 1260 } 1261 1262 i = CS.arg_begin(); 1263 for (unsigned n = FT->getNumParams(); n != 0; ++i, --n) 1264 Args.push_back(DFSF.getShadow(*i)); 1265 1266 if (!FT->getReturnType()->isVoidTy()) { 1267 if (!DFSF.LabelReturnAlloca) { 1268 DFSF.LabelReturnAlloca = 1269 new AllocaInst(DFSF.DFS.ShadowTy, "labelreturn", 1270 DFSF.F->getEntryBlock().begin()); 1271 } 1272 Args.push_back(DFSF.LabelReturnAlloca); 1273 } 1274 1275 CallInst *CustomCI = IRB.CreateCall(CustomF, Args); 1276 CustomCI->setCallingConv(CI->getCallingConv()); 1277 CustomCI->setAttributes(CI->getAttributes()); 1278 1279 if (!FT->getReturnType()->isVoidTy()) { 1280 LoadInst *LabelLoad = IRB.CreateLoad(DFSF.LabelReturnAlloca); 1281 DFSF.setShadow(CustomCI, LabelLoad); 1282 } 1283 1284 CI->replaceAllUsesWith(CustomCI); 1285 CI->eraseFromParent(); 1286 return; 1287 } 1288 break; 1289 } 1290 } 1291 } 1292 1293 FunctionType *FT = cast<FunctionType>( 1294 CS.getCalledValue()->getType()->getPointerElementType()); 1295 if (DFSF.DFS.getInstrumentedABI() == DataFlowSanitizer::IA_TLS) { 1296 for (unsigned i = 0, n = FT->getNumParams(); i != n; ++i) { 1297 IRB.CreateStore(DFSF.getShadow(CS.getArgument(i)), 1298 DFSF.getArgTLS(i, CS.getInstruction())); 1299 } 1300 } 1301 1302 Instruction *Next = 0; 1303 if (!CS.getType()->isVoidTy()) { 1304 if (InvokeInst *II = dyn_cast<InvokeInst>(CS.getInstruction())) { 1305 if (II->getNormalDest()->getSinglePredecessor()) { 1306 Next = II->getNormalDest()->begin(); 1307 } else { 1308 BasicBlock *NewBB = 1309 SplitEdge(II->getParent(), II->getNormalDest(), &DFSF.DFS); 1310 Next = NewBB->begin(); 1311 } 1312 } else { 1313 Next = CS->getNextNode(); 1314 } 1315 1316 if (DFSF.DFS.getInstrumentedABI() == DataFlowSanitizer::IA_TLS) { 1317 IRBuilder<> NextIRB(Next); 1318 LoadInst *LI = NextIRB.CreateLoad(DFSF.getRetvalTLS()); 1319 DFSF.SkipInsts.insert(LI); 1320 DFSF.setShadow(CS.getInstruction(), LI); 1321 DFSF.NonZeroChecks.insert(LI); 1322 } 1323 } 1324 1325 // Do all instrumentation for IA_Args down here to defer tampering with the 1326 // CFG in a way that SplitEdge may be able to detect. 1327 if (DFSF.DFS.getInstrumentedABI() == DataFlowSanitizer::IA_Args) { 1328 FunctionType *NewFT = DFSF.DFS.getArgsFunctionType(FT); 1329 Value *Func = 1330 IRB.CreateBitCast(CS.getCalledValue(), PointerType::getUnqual(NewFT)); 1331 std::vector<Value *> Args; 1332 1333 CallSite::arg_iterator i = CS.arg_begin(), e = CS.arg_end(); 1334 for (unsigned n = FT->getNumParams(); n != 0; ++i, --n) 1335 Args.push_back(*i); 1336 1337 i = CS.arg_begin(); 1338 for (unsigned n = FT->getNumParams(); n != 0; ++i, --n) 1339 Args.push_back(DFSF.getShadow(*i)); 1340 1341 if (FT->isVarArg()) { 1342 unsigned VarArgSize = CS.arg_size() - FT->getNumParams(); 1343 ArrayType *VarArgArrayTy = ArrayType::get(DFSF.DFS.ShadowTy, VarArgSize); 1344 AllocaInst *VarArgShadow = 1345 new AllocaInst(VarArgArrayTy, "", DFSF.F->getEntryBlock().begin()); 1346 Args.push_back(IRB.CreateConstGEP2_32(VarArgShadow, 0, 0)); 1347 for (unsigned n = 0; i != e; ++i, ++n) { 1348 IRB.CreateStore(DFSF.getShadow(*i), 1349 IRB.CreateConstGEP2_32(VarArgShadow, 0, n)); 1350 Args.push_back(*i); 1351 } 1352 } 1353 1354 CallSite NewCS; 1355 if (InvokeInst *II = dyn_cast<InvokeInst>(CS.getInstruction())) { 1356 NewCS = IRB.CreateInvoke(Func, II->getNormalDest(), II->getUnwindDest(), 1357 Args); 1358 } else { 1359 NewCS = IRB.CreateCall(Func, Args); 1360 } 1361 NewCS.setCallingConv(CS.getCallingConv()); 1362 NewCS.setAttributes(CS.getAttributes().removeAttributes( 1363 *DFSF.DFS.Ctx, AttributeSet::ReturnIndex, 1364 AttributeFuncs::typeIncompatible(NewCS.getInstruction()->getType(), 1365 AttributeSet::ReturnIndex))); 1366 1367 if (Next) { 1368 ExtractValueInst *ExVal = 1369 ExtractValueInst::Create(NewCS.getInstruction(), 0, "", Next); 1370 DFSF.SkipInsts.insert(ExVal); 1371 ExtractValueInst *ExShadow = 1372 ExtractValueInst::Create(NewCS.getInstruction(), 1, "", Next); 1373 DFSF.SkipInsts.insert(ExShadow); 1374 DFSF.setShadow(ExVal, ExShadow); 1375 DFSF.NonZeroChecks.insert(ExShadow); 1376 1377 CS.getInstruction()->replaceAllUsesWith(ExVal); 1378 } 1379 1380 CS.getInstruction()->eraseFromParent(); 1381 } 1382} 1383 1384void DFSanVisitor::visitPHINode(PHINode &PN) { 1385 PHINode *ShadowPN = 1386 PHINode::Create(DFSF.DFS.ShadowTy, PN.getNumIncomingValues(), "", &PN); 1387 1388 // Give the shadow phi node valid predecessors to fool SplitEdge into working. 1389 Value *UndefShadow = UndefValue::get(DFSF.DFS.ShadowTy); 1390 for (PHINode::block_iterator i = PN.block_begin(), e = PN.block_end(); i != e; 1391 ++i) { 1392 ShadowPN->addIncoming(UndefShadow, *i); 1393 } 1394 1395 DFSF.PHIFixups.push_back(std::make_pair(&PN, ShadowPN)); 1396 DFSF.setShadow(&PN, ShadowPN); 1397} 1398