diff options
Diffstat (limited to 'llvm/lib/Transforms/Instrumentation/DataFlowSanitizer.cpp')
| -rw-r--r-- | llvm/lib/Transforms/Instrumentation/DataFlowSanitizer.cpp | 2251 |
1 files changed, 1630 insertions, 621 deletions
diff --git a/llvm/lib/Transforms/Instrumentation/DataFlowSanitizer.cpp b/llvm/lib/Transforms/Instrumentation/DataFlowSanitizer.cpp index 1b14b8d56994..63aa84e4a77c 100644 --- a/llvm/lib/Transforms/Instrumentation/DataFlowSanitizer.cpp +++ b/llvm/lib/Transforms/Instrumentation/DataFlowSanitizer.cpp @@ -16,30 +16,40 @@ /// issues within their own code. /// /// The analysis is based on automatic propagation of data flow labels (also -/// known as taint labels) through a program as it performs computation. Each -/// byte of application memory is backed by two bytes of shadow memory which -/// hold the label. On Linux/x86_64, memory is laid out as follows: +/// known as taint labels) through a program as it performs computation. +/// +/// Each byte of application memory is backed by a shadow memory byte. The +/// shadow byte can represent up to 8 labels. On Linux/x86_64, memory is then +/// laid out as follows: /// /// +--------------------+ 0x800000000000 (top of memory) -/// | application memory | -/// +--------------------+ 0x700000008000 (kAppAddr) -/// | | -/// | unused | -/// | | -/// +--------------------+ 0x200200000000 (kUnusedAddr) -/// | union table | -/// +--------------------+ 0x200000000000 (kUnionTableAddr) -/// | shadow memory | -/// +--------------------+ 0x000000010000 (kShadowAddr) -/// | reserved by kernel | +/// | application 3 | +/// +--------------------+ 0x700000000000 +/// | invalid | +/// +--------------------+ 0x610000000000 +/// | origin 1 | +/// +--------------------+ 0x600000000000 +/// | application 2 | +/// +--------------------+ 0x510000000000 +/// | shadow 1 | +/// +--------------------+ 0x500000000000 +/// | invalid | +/// +--------------------+ 0x400000000000 +/// | origin 3 | +/// +--------------------+ 0x300000000000 +/// | shadow 3 | +/// +--------------------+ 0x200000000000 +/// | origin 2 | +/// +--------------------+ 0x110000000000 +/// | invalid | +/// +--------------------+ 0x100000000000 +/// | shadow 2 | +/// +--------------------+ 0x010000000000 +/// | application 1 | /// +--------------------+ 0x000000000000 /// -/// To derive a shadow memory address from an application memory address, -/// bits 44-46 are cleared to bring the address into the range -/// [0x000000008000,0x100000000000). Then the address is shifted left by 1 to -/// account for the double byte representation of shadow labels and move the -/// address into the shadow memory range. See the function -/// DataFlowSanitizer::getShadowAddress below. +/// MEM_TO_SHADOW(mem) = mem ^ 0x500000000000 +/// SHADOW_TO_ORIGIN(shadow) = shadow + 0x100000000000 /// /// For more information, please refer to the design document: /// http://clang.llvm.org/docs/DataFlowSanitizerDesign.html @@ -56,6 +66,7 @@ #include "llvm/ADT/StringExtras.h" #include "llvm/ADT/StringRef.h" #include "llvm/ADT/Triple.h" +#include "llvm/ADT/iterator.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/Argument.h" #include "llvm/IR/Attributes.h" @@ -85,6 +96,7 @@ #include "llvm/IR/Value.h" #include "llvm/InitializePasses.h" #include "llvm/Pass.h" +#include "llvm/Support/Alignment.h" #include "llvm/Support/Casting.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/ErrorHandling.h" @@ -107,17 +119,14 @@ using namespace llvm; // This must be consistent with ShadowWidthBits. -static const Align kShadowTLSAlignment = Align(2); +static const Align ShadowTLSAlignment = Align(2); + +static const Align MinOriginAlignment = Align(4); // The size of TLS variables. These constants must be kept in sync with the ones // in dfsan.cpp. -static const unsigned kArgTLSSize = 800; -static const unsigned kRetvalTLSSize = 800; - -// External symbol to be used when generating the shadow address for -// architectures with multiple VMAs. Instead of using a constant integer -// the runtime will set the external mask based on the VMA range. -const char kDFSanExternShadowPtrMask[] = "__dfsan_shadow_ptr_mask"; +static const unsigned ArgTLSSize = 800; +static const unsigned RetvalTLSSize = 800; // The -dfsan-preserve-alignment flag controls whether this pass assumes that // alignment requirements provided by the input IR are correct. For example, @@ -144,10 +153,10 @@ static cl::list<std::string> ClABIListFiles( // Controls whether the pass uses IA_Args or IA_TLS as the ABI for instrumented // functions (see DataFlowSanitizer::InstrumentedABI below). -static cl::opt<bool> ClArgsABI( - "dfsan-args-abi", - cl::desc("Use the argument ABI rather than the TLS ABI"), - cl::Hidden); +static cl::opt<bool> + ClArgsABI("dfsan-args-abi", + cl::desc("Use the argument ABI rather than the TLS ABI"), + cl::Hidden); // Controls whether the pass includes or ignores the labels of pointers in load // instructions. @@ -165,6 +174,14 @@ static cl::opt<bool> ClCombinePointerLabelsOnStore( "storing in memory."), cl::Hidden, cl::init(false)); +// Controls whether the pass propagates labels of offsets in GEP instructions. +static cl::opt<bool> ClCombineOffsetLabelsOnGEP( + "dfsan-combine-offset-labels-on-gep", + cl::desc( + "Combine the label of the offset with the label of the pointer when " + "doing pointer arithmetic."), + cl::Hidden, cl::init(true)); + static cl::opt<bool> ClDebugNonzeroLabels( "dfsan-debug-nonzero-labels", cl::desc("Insert calls to __dfsan_nonzero_label on observing a parameter, " @@ -186,14 +203,6 @@ static cl::opt<bool> ClEventCallbacks( cl::desc("Insert calls to __dfsan_*_callback functions on data events."), cl::Hidden, cl::init(false)); -// Use a distinct bit for each base label, enabling faster unions with less -// instrumentation. Limits the max number of base labels to 16. -static cl::opt<bool> ClFast16Labels( - "dfsan-fast-16-labels", - cl::desc("Use more efficient instrumentation, limiting the number of " - "labels to 16."), - cl::Hidden, cl::init(false)); - // Controls whether the pass tracks the control flow of select instructions. static cl::opt<bool> ClTrackSelectControlFlow( "dfsan-track-select-control-flow", @@ -201,7 +210,24 @@ static cl::opt<bool> ClTrackSelectControlFlow( "to results."), cl::Hidden, cl::init(true)); -static StringRef GetGlobalTypeString(const GlobalValue &G) { +// TODO: This default value follows MSan. DFSan may use a different value. +static cl::opt<int> ClInstrumentWithCallThreshold( + "dfsan-instrument-with-call-threshold", + cl::desc("If the function being instrumented requires more than " + "this number of origin stores, use callbacks instead of " + "inline checks (-1 means never use callbacks)."), + cl::Hidden, cl::init(3500)); + +// Controls how to track origins. +// * 0: do not track origins. +// * 1: track origins at memory store operations. +// * 2: track origins at memory load and store operations. +// TODO: track callsites. +static cl::opt<int> ClTrackOrigins("dfsan-track-origins", + cl::desc("Track origins of labels"), + cl::Hidden, cl::init(0)); + +static StringRef getGlobalTypeString(const GlobalValue &G) { // Types of GlobalVariables are always pointer types. Type *GType = G.getValueType(); // For now we support excluding struct types only. @@ -214,10 +240,34 @@ static StringRef GetGlobalTypeString(const GlobalValue &G) { namespace { +// Memory map parameters used in application-to-shadow address calculation. +// Offset = (Addr & ~AndMask) ^ XorMask +// Shadow = ShadowBase + Offset +// Origin = (OriginBase + Offset) & ~3ULL +struct MemoryMapParams { + uint64_t AndMask; + uint64_t XorMask; + uint64_t ShadowBase; + uint64_t OriginBase; +}; + +} // end anonymous namespace + +// x86_64 Linux +// NOLINTNEXTLINE(readability-identifier-naming) +static const MemoryMapParams Linux_X86_64_MemoryMapParams = { + 0, // AndMask (not used) + 0x500000000000, // XorMask + 0, // ShadowBase (not used) + 0x100000000000, // OriginBase +}; + +namespace { + class DFSanABIList { std::unique_ptr<SpecialCaseList> SCL; - public: +public: DFSanABIList() = default; void set(std::unique_ptr<SpecialCaseList> List) { SCL = std::move(List); } @@ -241,7 +291,7 @@ class DFSanABIList { return SCL->inSection("dataflow", "fun", GA.getName(), Category); return SCL->inSection("dataflow", "global", GA.getName(), Category) || - SCL->inSection("dataflow", "type", GetGlobalTypeString(GA), + SCL->inSection("dataflow", "type", getGlobalTypeString(GA), Category); } @@ -255,20 +305,18 @@ class DFSanABIList { /// function type into another. This struct is immutable. It holds metadata /// useful for updating calls of the old function to the new type. struct TransformedFunction { - TransformedFunction(FunctionType* OriginalType, - FunctionType* TransformedType, + TransformedFunction(FunctionType *OriginalType, FunctionType *TransformedType, std::vector<unsigned> ArgumentIndexMapping) - : OriginalType(OriginalType), - TransformedType(TransformedType), + : OriginalType(OriginalType), TransformedType(TransformedType), ArgumentIndexMapping(ArgumentIndexMapping) {} // Disallow copies. - TransformedFunction(const TransformedFunction&) = delete; - TransformedFunction& operator=(const TransformedFunction&) = delete; + TransformedFunction(const TransformedFunction &) = delete; + TransformedFunction &operator=(const TransformedFunction &) = delete; // Allow moves. - TransformedFunction(TransformedFunction&&) = default; - TransformedFunction& operator=(TransformedFunction&&) = default; + TransformedFunction(TransformedFunction &&) = default; + TransformedFunction &operator=(TransformedFunction &&) = default; /// Type of the function before the transformation. FunctionType *OriginalType; @@ -287,9 +335,9 @@ struct TransformedFunction { /// Given function attributes from a call site for the original function, /// return function attributes appropriate for a call to the transformed /// function. -AttributeList TransformFunctionAttributes( - const TransformedFunction& TransformedFunction, - LLVMContext& Ctx, AttributeList CallSiteAttrs) { +AttributeList +transformFunctionAttributes(const TransformedFunction &TransformedFunction, + LLVMContext &Ctx, AttributeList CallSiteAttrs) { // Construct a vector of AttributeSet for each function argument. std::vector<llvm::AttributeSet> ArgumentAttributes( @@ -298,30 +346,31 @@ AttributeList TransformFunctionAttributes( // Copy attributes from the parameter of the original function to the // transformed version. 'ArgumentIndexMapping' holds the mapping from // old argument position to new. - for (unsigned i=0, ie = TransformedFunction.ArgumentIndexMapping.size(); - i < ie; ++i) { - unsigned TransformedIndex = TransformedFunction.ArgumentIndexMapping[i]; - ArgumentAttributes[TransformedIndex] = CallSiteAttrs.getParamAttributes(i); + for (unsigned I = 0, IE = TransformedFunction.ArgumentIndexMapping.size(); + I < IE; ++I) { + unsigned TransformedIndex = TransformedFunction.ArgumentIndexMapping[I]; + ArgumentAttributes[TransformedIndex] = CallSiteAttrs.getParamAttributes(I); } // Copy annotations on varargs arguments. - for (unsigned i = TransformedFunction.OriginalType->getNumParams(), - ie = CallSiteAttrs.getNumAttrSets(); i<ie; ++i) { - ArgumentAttributes.push_back(CallSiteAttrs.getParamAttributes(i)); + for (unsigned I = TransformedFunction.OriginalType->getNumParams(), + IE = CallSiteAttrs.getNumAttrSets(); + I < IE; ++I) { + ArgumentAttributes.push_back(CallSiteAttrs.getParamAttributes(I)); } - return AttributeList::get( - Ctx, - CallSiteAttrs.getFnAttributes(), - CallSiteAttrs.getRetAttributes(), - llvm::makeArrayRef(ArgumentAttributes)); + return AttributeList::get(Ctx, CallSiteAttrs.getFnAttributes(), + CallSiteAttrs.getRetAttributes(), + llvm::makeArrayRef(ArgumentAttributes)); } class DataFlowSanitizer { friend struct DFSanFunction; friend class DFSanVisitor; - enum { ShadowWidthBits = 16, ShadowWidthBytes = ShadowWidthBits / 8 }; + enum { ShadowWidthBits = 8, ShadowWidthBytes = ShadowWidthBits / 8 }; + + enum { OriginWidthBits = 32, OriginWidthBytes = OriginWidthBits / 8 }; /// Which ABI should be used for instrumented functions? enum InstrumentedABI { @@ -362,18 +411,21 @@ class DataFlowSanitizer { Module *Mod; LLVMContext *Ctx; Type *Int8Ptr; + IntegerType *OriginTy; + PointerType *OriginPtrTy; + ConstantInt *ZeroOrigin; /// The shadow type for all primitive types and vector types. IntegerType *PrimitiveShadowTy; PointerType *PrimitiveShadowPtrTy; IntegerType *IntptrTy; ConstantInt *ZeroPrimitiveShadow; - ConstantInt *ShadowPtrMask; - ConstantInt *ShadowPtrMul; Constant *ArgTLS; + ArrayType *ArgOriginTLSTy; + Constant *ArgOriginTLS; Constant *RetvalTLS; - Constant *ExternalShadowMask; - FunctionType *DFSanUnionFnTy; + Constant *RetvalOriginTLS; FunctionType *DFSanUnionLoadFnTy; + FunctionType *DFSanLoadLabelAndOriginFnTy; FunctionType *DFSanUnimplementedFnTy; FunctionType *DFSanSetLabelFnTy; FunctionType *DFSanNonzeroLabelFnTy; @@ -381,10 +433,12 @@ class DataFlowSanitizer { FunctionType *DFSanCmpCallbackFnTy; FunctionType *DFSanLoadStoreCallbackFnTy; FunctionType *DFSanMemTransferCallbackFnTy; - FunctionCallee DFSanUnionFn; - FunctionCallee DFSanCheckedUnionFn; + FunctionType *DFSanChainOriginFnTy; + FunctionType *DFSanChainOriginIfTaintedFnTy; + FunctionType *DFSanMemOriginTransferFnTy; + FunctionType *DFSanMaybeStoreOriginFnTy; FunctionCallee DFSanUnionLoadFn; - FunctionCallee DFSanUnionLoadFast16LabelsFn; + FunctionCallee DFSanLoadLabelAndOriginFn; FunctionCallee DFSanUnimplementedFn; FunctionCallee DFSanSetLabelFn; FunctionCallee DFSanNonzeroLabelFn; @@ -393,13 +447,26 @@ class DataFlowSanitizer { FunctionCallee DFSanStoreCallbackFn; FunctionCallee DFSanMemTransferCallbackFn; FunctionCallee DFSanCmpCallbackFn; + FunctionCallee DFSanChainOriginFn; + FunctionCallee DFSanChainOriginIfTaintedFn; + FunctionCallee DFSanMemOriginTransferFn; + FunctionCallee DFSanMaybeStoreOriginFn; + SmallPtrSet<Value *, 16> DFSanRuntimeFunctions; MDNode *ColdCallWeights; + MDNode *OriginStoreWeights; DFSanABIList ABIList; DenseMap<Value *, Function *> UnwrappedFnMap; AttrBuilder ReadOnlyNoneAttrs; - bool DFSanRuntimeShadowMask = false; + /// Memory map parameters used in calculation mapping application addresses + /// to shadow addresses and origin addresses. + const MemoryMapParams *MapParams; + + Value *getShadowOffset(Value *Addr, IRBuilder<> &IRB); Value *getShadowAddress(Value *Addr, Instruction *Pos); + Value *getShadowAddress(Value *Addr, Instruction *Pos, Value *ShadowOffset); + std::pair<Value *, Value *> + getShadowOriginAddress(Value *Addr, Align InstAlignment, Instruction *Pos); bool isInstrumented(const Function *F); bool isInstrumented(const GlobalAlias *GA); FunctionType *getArgsFunctionType(FunctionType *T); @@ -407,18 +474,30 @@ class DataFlowSanitizer { TransformedFunction getCustomFunctionType(FunctionType *T); InstrumentedABI getInstrumentedABI(); WrapperKind getWrapperKind(Function *F); - void addGlobalNamePrefix(GlobalValue *GV); + void addGlobalNameSuffix(GlobalValue *GV); Function *buildWrapperFunction(Function *F, StringRef NewFName, GlobalValue::LinkageTypes NewFLink, FunctionType *NewFT); Constant *getOrBuildTrampolineFunction(FunctionType *FT, StringRef FName); void initializeCallbackFunctions(Module &M); void initializeRuntimeFunctions(Module &M); + void injectMetadataGlobals(Module &M); + bool initializeModule(Module &M); - bool init(Module &M); + /// Advances \p OriginAddr to point to the next 32-bit origin and then loads + /// from it. Returns the origin's loaded value. + Value *loadNextOrigin(Instruction *Pos, Align OriginAlign, + Value **OriginAddr); + + /// Returns whether the given load byte size is amenable to inlined + /// optimization patterns. + bool hasLoadSizeForFastPath(uint64_t Size); + + /// Returns whether the pass tracks origins. Supports only TLS ABI mode. + bool shouldTrackOrigins(); /// Returns whether the pass tracks labels for struct fields and array - /// indices. Support only fast16 mode in TLS ABI mode. + /// indices. Supports only TLS ABI mode. bool shouldTrackFieldsAndIndices(); /// Returns a zero constant with the shadow type of OrigTy. @@ -448,6 +527,8 @@ class DataFlowSanitizer { /// Returns the shadow type of of V's type. Type *getShadowTy(Value *V); + const uint64_t NumOfElementsInArgOrgTLS = ArgTLSSize / OriginWidthBytes; + public: DataFlowSanitizer(const std::vector<std::string> &ABIListFiles); @@ -461,12 +542,21 @@ struct DFSanFunction { DataFlowSanitizer::InstrumentedABI IA; bool IsNativeABI; AllocaInst *LabelReturnAlloca = nullptr; + AllocaInst *OriginReturnAlloca = nullptr; DenseMap<Value *, Value *> ValShadowMap; + DenseMap<Value *, Value *> ValOriginMap; DenseMap<AllocaInst *, AllocaInst *> AllocaShadowMap; - std::vector<std::pair<PHINode *, PHINode *>> PHIFixups; + DenseMap<AllocaInst *, AllocaInst *> AllocaOriginMap; + + struct PHIFixupElement { + PHINode *Phi; + PHINode *ShadowPhi; + PHINode *OriginPhi; + }; + std::vector<PHIFixupElement> PHIFixups; + DenseSet<Instruction *> SkipInsts; std::vector<Value *> NonZeroChecks; - bool AvoidNewBlocks; struct CachedShadow { BasicBlock *Block; // The block where Shadow is defined. @@ -484,9 +574,6 @@ struct DFSanFunction { DFSanFunction(DataFlowSanitizer &DFS, Function *F, bool IsNativeABI) : DFS(DFS), F(F), IA(DFS.getInstrumentedABI()), IsNativeABI(IsNativeABI) { DT.recalculate(*F); - // FIXME: Need to track down the register allocator issue which causes poor - // performance in pathological cases with large numbers of basic blocks. - AvoidNewBlocks = F->size() > 1000; } /// Computes the shadow address for a given function argument. @@ -494,9 +581,31 @@ struct DFSanFunction { /// Shadow = ArgTLS+ArgOffset. Value *getArgTLS(Type *T, unsigned ArgOffset, IRBuilder<> &IRB); - /// Computes the shadow address for a retval. + /// Computes the shadow address for a return value. Value *getRetvalTLS(Type *T, IRBuilder<> &IRB); + /// Computes the origin address for a given function argument. + /// + /// Origin = ArgOriginTLS[ArgNo]. + Value *getArgOriginTLS(unsigned ArgNo, IRBuilder<> &IRB); + + /// Computes the origin address for a return value. + Value *getRetvalOriginTLS(); + + Value *getOrigin(Value *V); + void setOrigin(Instruction *I, Value *Origin); + /// Generates IR to compute the origin of the last operand with a taint label. + Value *combineOperandOrigins(Instruction *Inst); + /// Before the instruction Pos, generates IR to compute the last origin with a + /// taint label. Labels and origins are from vectors Shadows and Origins + /// correspondingly. The generated IR is like + /// Sn-1 != Zero ? On-1: ... S2 != Zero ? O2: S1 != Zero ? O1: O0 + /// When Zero is nullptr, it uses ZeroPrimitiveShadow. Otherwise it can be + /// zeros with other bitwidths. + Value *combineOrigins(const std::vector<Value *> &Shadows, + const std::vector<Value *> &Origins, Instruction *Pos, + ConstantInt *Zero = nullptr); + Value *getShadow(Value *V); void setShadow(Instruction *I, Value *Shadow); /// Generates IR to compute the union of the two given shadows, inserting it @@ -507,10 +616,21 @@ struct DFSanFunction { Value *combineShadowsThenConvert(Type *T, Value *V1, Value *V2, Instruction *Pos); Value *combineOperandShadows(Instruction *Inst); - Value *loadShadow(Value *ShadowAddr, uint64_t Size, uint64_t Align, - Instruction *Pos); - void storePrimitiveShadow(Value *Addr, uint64_t Size, Align Alignment, - Value *PrimitiveShadow, Instruction *Pos); + + /// Generates IR to load shadow and origin corresponding to bytes [\p + /// Addr, \p Addr + \p Size), where addr has alignment \p + /// InstAlignment, and take the union of each of those shadows. The returned + /// shadow always has primitive type. + /// + /// When tracking loads is enabled, the returned origin is a chain at the + /// current stack if the returned shadow is tainted. + std::pair<Value *, Value *> loadShadowOrigin(Value *Addr, uint64_t Size, + Align InstAlignment, + Instruction *Pos); + + void storePrimitiveShadowOrigin(Value *Addr, uint64_t Size, + Align InstAlignment, Value *PrimitiveShadow, + Value *Origin, Instruction *Pos); /// Applies PrimitiveShadow to all primitive subtypes of T, returning /// the expanded shadow value. /// @@ -528,6 +648,11 @@ struct DFSanFunction { /// CTP(other types, PS) = PS Value *collapseToPrimitiveShadow(Value *Shadow, Instruction *Pos); + void storeZeroPrimitiveShadow(Value *Addr, uint64_t Size, Align ShadowAlign, + Instruction *Pos); + + Align getShadowAlign(Align InstAlignment); + private: /// Collapses the shadow with aggregate type into a single primitive shadow /// value. @@ -539,6 +664,63 @@ private: /// Returns the shadow value of an argument A. Value *getShadowForTLSArgument(Argument *A); + + /// The fast path of loading shadows. + std::pair<Value *, Value *> + loadShadowFast(Value *ShadowAddr, Value *OriginAddr, uint64_t Size, + Align ShadowAlign, Align OriginAlign, Value *FirstOrigin, + Instruction *Pos); + + Align getOriginAlign(Align InstAlignment); + + /// Because 4 contiguous bytes share one 4-byte origin, the most accurate load + /// is __dfsan_load_label_and_origin. This function returns the union of all + /// labels and the origin of the first taint label. However this is an + /// additional call with many instructions. To ensure common cases are fast, + /// checks if it is possible to load labels and origins without using the + /// callback function. + /// + /// When enabling tracking load instructions, we always use + /// __dfsan_load_label_and_origin to reduce code size. + bool useCallbackLoadLabelAndOrigin(uint64_t Size, Align InstAlignment); + + /// Returns a chain at the current stack with previous origin V. + Value *updateOrigin(Value *V, IRBuilder<> &IRB); + + /// Returns a chain at the current stack with previous origin V if Shadow is + /// tainted. + Value *updateOriginIfTainted(Value *Shadow, Value *Origin, IRBuilder<> &IRB); + + /// Creates an Intptr = Origin | Origin << 32 if Intptr's size is 64. Returns + /// Origin otherwise. + Value *originToIntptr(IRBuilder<> &IRB, Value *Origin); + + /// Stores Origin into the address range [StoreOriginAddr, StoreOriginAddr + + /// Size). + void paintOrigin(IRBuilder<> &IRB, Value *Origin, Value *StoreOriginAddr, + uint64_t StoreOriginSize, Align Alignment); + + /// Stores Origin in terms of its Shadow value. + /// * Do not write origins for zero shadows because we do not trace origins + /// for untainted sinks. + /// * Use __dfsan_maybe_store_origin if there are too many origin store + /// instrumentations. + void storeOrigin(Instruction *Pos, Value *Addr, uint64_t Size, Value *Shadow, + Value *Origin, Value *StoreOriginAddr, Align InstAlignment); + + /// Convert a scalar value to an i1 by comparing with 0. + Value *convertToBool(Value *V, IRBuilder<> &IRB, const Twine &Name = ""); + + bool shouldInstrumentWithCall(); + + /// Generates IR to load shadow and origin corresponding to bytes [\p + /// Addr, \p Addr + \p Size), where addr has alignment \p + /// InstAlignment, and take the union of each of those shadows. The returned + /// shadow always has primitive type. + std::pair<Value *, Value *> + loadShadowOriginSansLoadTracking(Value *Addr, uint64_t Size, + Align InstAlignment, Instruction *Pos); + int NumOriginStores = 0; }; class DFSanVisitor : public InstVisitor<DFSanVisitor> { @@ -551,17 +733,20 @@ public: return DFSF.F->getParent()->getDataLayout(); } - // Combines shadow values for all of I's operands. Returns the combined shadow - // value. - Value *visitOperandShadowInst(Instruction &I); + // Combines shadow values and origins for all of I's operands. + void visitInstOperands(Instruction &I); void visitUnaryOperator(UnaryOperator &UO); void visitBinaryOperator(BinaryOperator &BO); + void visitBitCastInst(BitCastInst &BCI); void visitCastInst(CastInst &CI); void visitCmpInst(CmpInst &CI); + void visitLandingPadInst(LandingPadInst &LPI); void visitGetElementPtrInst(GetElementPtrInst &GEPI); void visitLoadInst(LoadInst &LI); void visitStoreInst(StoreInst &SI); + void visitAtomicRMWInst(AtomicRMWInst &I); + void visitAtomicCmpXchgInst(AtomicCmpXchgInst &I); void visitReturnInst(ReturnInst &RI); void visitCallBase(CallBase &CB); void visitPHINode(PHINode &PN); @@ -574,6 +759,21 @@ public: void visitSelectInst(SelectInst &I); void visitMemSetInst(MemSetInst &I); void visitMemTransferInst(MemTransferInst &I); + +private: + void visitCASOrRMW(Align InstAlignment, Instruction &I); + + // Returns false when this is an invoke of a custom function. + bool visitWrappedCallBase(Function &F, CallBase &CB); + + // Combines origins for all of I's operands. + void visitInstOperandOrigins(Instruction &I); + + void addShadowArguments(Function &F, CallBase &CB, std::vector<Value *> &Args, + IRBuilder<> &IRB); + + void addOriginArguments(Function &F, CallBase &CB, std::vector<Value *> &Args, + IRBuilder<> &IRB); }; } // end anonymous namespace @@ -607,6 +807,13 @@ FunctionType *DataFlowSanitizer::getTrampolineFunctionType(FunctionType *T) { Type *RetType = T->getReturnType(); if (!RetType->isVoidTy()) ArgTypes.push_back(PrimitiveShadowPtrTy); + + if (shouldTrackOrigins()) { + ArgTypes.append(T->getNumParams(), OriginTy); + if (!RetType->isVoidTy()) + ArgTypes.push_back(OriginPtrTy); + } + return FunctionType::get(T->getReturnType(), ArgTypes, false); } @@ -618,26 +825,36 @@ TransformedFunction DataFlowSanitizer::getCustomFunctionType(FunctionType *T) { // parameters of the custom function, so that parameter attributes // at call sites can be updated. std::vector<unsigned> ArgumentIndexMapping; - for (unsigned i = 0, ie = T->getNumParams(); i != ie; ++i) { - Type* param_type = T->getParamType(i); + for (unsigned I = 0, E = T->getNumParams(); I != E; ++I) { + Type *ParamType = T->getParamType(I); FunctionType *FT; - if (isa<PointerType>(param_type) && (FT = dyn_cast<FunctionType>( - cast<PointerType>(param_type)->getElementType()))) { + if (isa<PointerType>(ParamType) && + (FT = dyn_cast<FunctionType>(ParamType->getPointerElementType()))) { ArgumentIndexMapping.push_back(ArgTypes.size()); ArgTypes.push_back(getTrampolineFunctionType(FT)->getPointerTo()); ArgTypes.push_back(Type::getInt8PtrTy(*Ctx)); } else { ArgumentIndexMapping.push_back(ArgTypes.size()); - ArgTypes.push_back(param_type); + ArgTypes.push_back(ParamType); } } - for (unsigned i = 0, e = T->getNumParams(); i != e; ++i) + for (unsigned I = 0, E = T->getNumParams(); I != E; ++I) ArgTypes.push_back(PrimitiveShadowTy); if (T->isVarArg()) ArgTypes.push_back(PrimitiveShadowPtrTy); Type *RetType = T->getReturnType(); if (!RetType->isVoidTy()) ArgTypes.push_back(PrimitiveShadowPtrTy); + + if (shouldTrackOrigins()) { + for (unsigned I = 0, E = T->getNumParams(); I != E; ++I) + ArgTypes.push_back(OriginTy); + if (T->isVarArg()) + ArgTypes.push_back(OriginPtrTy); + if (!RetType->isVoidTy()) + ArgTypes.push_back(OriginPtrTy); + } + return TransformedFunction( T, FunctionType::get(T->getReturnType(), ArgTypes, T->isVarArg()), ArgumentIndexMapping); @@ -657,8 +874,19 @@ bool DataFlowSanitizer::isZeroShadow(Value *V) { return isa<ConstantAggregateZero>(V); } +bool DataFlowSanitizer::hasLoadSizeForFastPath(uint64_t Size) { + uint64_t ShadowSize = Size * ShadowWidthBytes; + return ShadowSize % 8 == 0 || ShadowSize == 4; +} + +bool DataFlowSanitizer::shouldTrackOrigins() { + static const bool ShouldTrackOrigins = + ClTrackOrigins && getInstrumentedABI() == DataFlowSanitizer::IA_TLS; + return ShouldTrackOrigins; +} + bool DataFlowSanitizer::shouldTrackFieldsAndIndices() { - return getInstrumentedABI() == DataFlowSanitizer::IA_TLS && ClFast16Labels; + return getInstrumentedABI() == DataFlowSanitizer::IA_TLS; } Constant *DataFlowSanitizer::getZeroShadow(Type *OrigTy) { @@ -703,6 +931,11 @@ static Value *expandFromPrimitiveShadowRecursive( llvm_unreachable("Unexpected shadow type"); } +bool DFSanFunction::shouldInstrumentWithCall() { + return ClInstrumentWithCallThreshold >= 0 && + NumOriginStores >= ClInstrumentWithCallThreshold; +} + Value *DFSanFunction::expandFromPrimitiveShadow(Type *T, Value *PrimitiveShadow, Instruction *Pos) { Type *ShadowTy = DFS.getShadowTy(T); @@ -799,43 +1032,38 @@ Type *DataFlowSanitizer::getShadowTy(Value *V) { return getShadowTy(V->getType()); } -bool DataFlowSanitizer::init(Module &M) { +bool DataFlowSanitizer::initializeModule(Module &M) { Triple TargetTriple(M.getTargetTriple()); - bool IsX86_64 = TargetTriple.getArch() == Triple::x86_64; - bool IsMIPS64 = TargetTriple.isMIPS64(); - bool IsAArch64 = TargetTriple.getArch() == Triple::aarch64 || - TargetTriple.getArch() == Triple::aarch64_be; - const DataLayout &DL = M.getDataLayout(); + if (TargetTriple.getOS() != Triple::Linux) + report_fatal_error("unsupported operating system"); + if (TargetTriple.getArch() != Triple::x86_64) + report_fatal_error("unsupported architecture"); + MapParams = &Linux_X86_64_MemoryMapParams; + Mod = &M; Ctx = &M.getContext(); Int8Ptr = Type::getInt8PtrTy(*Ctx); + OriginTy = IntegerType::get(*Ctx, OriginWidthBits); + OriginPtrTy = PointerType::getUnqual(OriginTy); PrimitiveShadowTy = IntegerType::get(*Ctx, ShadowWidthBits); PrimitiveShadowPtrTy = PointerType::getUnqual(PrimitiveShadowTy); IntptrTy = DL.getIntPtrType(*Ctx); ZeroPrimitiveShadow = ConstantInt::getSigned(PrimitiveShadowTy, 0); - ShadowPtrMul = ConstantInt::getSigned(IntptrTy, ShadowWidthBytes); - if (IsX86_64) - ShadowPtrMask = ConstantInt::getSigned(IntptrTy, ~0x700000000000LL); - else if (IsMIPS64) - ShadowPtrMask = ConstantInt::getSigned(IntptrTy, ~0xF000000000LL); - // AArch64 supports multiple VMAs and the shadow mask is set at runtime. - else if (IsAArch64) - DFSanRuntimeShadowMask = true; - else - report_fatal_error("unsupported triple"); + ZeroOrigin = ConstantInt::getSigned(OriginTy, 0); - Type *DFSanUnionArgs[2] = {PrimitiveShadowTy, PrimitiveShadowTy}; - DFSanUnionFnTy = - FunctionType::get(PrimitiveShadowTy, DFSanUnionArgs, /*isVarArg=*/false); Type *DFSanUnionLoadArgs[2] = {PrimitiveShadowPtrTy, IntptrTy}; DFSanUnionLoadFnTy = FunctionType::get(PrimitiveShadowTy, DFSanUnionLoadArgs, /*isVarArg=*/false); + Type *DFSanLoadLabelAndOriginArgs[2] = {Int8Ptr, IntptrTy}; + DFSanLoadLabelAndOriginFnTy = + FunctionType::get(IntegerType::get(*Ctx, 64), DFSanLoadLabelAndOriginArgs, + /*isVarArg=*/false); DFSanUnimplementedFnTy = FunctionType::get( Type::getVoidTy(*Ctx), Type::getInt8PtrTy(*Ctx), /*isVarArg=*/false); - Type *DFSanSetLabelArgs[3] = {PrimitiveShadowTy, Type::getInt8PtrTy(*Ctx), - IntptrTy}; + Type *DFSanSetLabelArgs[4] = {PrimitiveShadowTy, OriginTy, + Type::getInt8PtrTy(*Ctx), IntptrTy}; DFSanSetLabelFnTy = FunctionType::get(Type::getVoidTy(*Ctx), DFSanSetLabelArgs, /*isVarArg=*/false); DFSanNonzeroLabelFnTy = @@ -845,6 +1073,18 @@ bool DataFlowSanitizer::init(Module &M) { DFSanCmpCallbackFnTy = FunctionType::get(Type::getVoidTy(*Ctx), PrimitiveShadowTy, /*isVarArg=*/false); + DFSanChainOriginFnTy = + FunctionType::get(OriginTy, OriginTy, /*isVarArg=*/false); + Type *DFSanChainOriginIfTaintedArgs[2] = {PrimitiveShadowTy, OriginTy}; + DFSanChainOriginIfTaintedFnTy = FunctionType::get( + OriginTy, DFSanChainOriginIfTaintedArgs, /*isVarArg=*/false); + Type *DFSanMaybeStoreOriginArgs[4] = {IntegerType::get(*Ctx, ShadowWidthBits), + Int8Ptr, IntptrTy, OriginTy}; + DFSanMaybeStoreOriginFnTy = FunctionType::get( + Type::getVoidTy(*Ctx), DFSanMaybeStoreOriginArgs, /*isVarArg=*/false); + Type *DFSanMemOriginTransferArgs[3] = {Int8Ptr, Int8Ptr, IntptrTy}; + DFSanMemOriginTransferFnTy = FunctionType::get( + Type::getVoidTy(*Ctx), DFSanMemOriginTransferArgs, /*isVarArg=*/false); Type *DFSanLoadStoreCallbackArgs[2] = {PrimitiveShadowTy, Int8Ptr}; DFSanLoadStoreCallbackFnTy = FunctionType::get(Type::getVoidTy(*Ctx), DFSanLoadStoreCallbackArgs, @@ -855,6 +1095,7 @@ bool DataFlowSanitizer::init(Module &M) { /*isVarArg=*/false); ColdCallWeights = MDBuilder(*Ctx).createBranchWeights(1, 1000); + OriginStoreWeights = MDBuilder(*Ctx).createBranchWeights(1, 1000); return true; } @@ -881,9 +1122,9 @@ DataFlowSanitizer::WrapperKind DataFlowSanitizer::getWrapperKind(Function *F) { return WK_Warning; } -void DataFlowSanitizer::addGlobalNamePrefix(GlobalValue *GV) { - std::string GVName = std::string(GV->getName()), Prefix = "dfs$"; - GV->setName(Prefix + GVName); +void DataFlowSanitizer::addGlobalNameSuffix(GlobalValue *GV) { + std::string GVName = std::string(GV->getName()), Suffix = ".dfsan"; + GV->setName(GVName + Suffix); // Try to change the name of the function in module inline asm. We only do // this for specific asm directives, currently only ".symver", to try to avoid @@ -894,8 +1135,13 @@ void DataFlowSanitizer::addGlobalNamePrefix(GlobalValue *GV) { std::string SearchStr = ".symver " + GVName + ","; size_t Pos = Asm.find(SearchStr); if (Pos != std::string::npos) { - Asm.replace(Pos, SearchStr.size(), - ".symver " + Prefix + GVName + "," + Prefix); + Asm.replace(Pos, SearchStr.size(), ".symver " + GVName + Suffix + ","); + Pos = Asm.find("@"); + + if (Pos == std::string::npos) + report_fatal_error("unsupported .symver: " + Asm); + + Asm.replace(Pos, 1, Suffix + "@"); GV->getParent()->setModuleInlineAsm(Asm); } } @@ -921,10 +1167,9 @@ DataFlowSanitizer::buildWrapperFunction(Function *F, StringRef NewFName, BB); new UnreachableInst(*Ctx, BB); } else { - std::vector<Value *> Args; - unsigned n = FT->getNumParams(); - for (Function::arg_iterator ai = NewF->arg_begin(); n != 0; ++ai, --n) - Args.push_back(&*ai); + auto ArgIt = pointer_iterator<Argument *>(NewF->arg_begin()); + std::vector<Value *> Args(ArgIt, ArgIt + FT->getNumParams()); + CallInst *CI = CallInst::Create(F, Args, "", BB); if (FT->getReturnType()->isVoidTy()) ReturnInst::Create(*Ctx, BB); @@ -944,30 +1189,45 @@ Constant *DataFlowSanitizer::getOrBuildTrampolineFunction(FunctionType *FT, F->setLinkage(GlobalValue::LinkOnceODRLinkage); BasicBlock *BB = BasicBlock::Create(*Ctx, "entry", F); std::vector<Value *> Args; - Function::arg_iterator AI = F->arg_begin(); ++AI; + Function::arg_iterator AI = F->arg_begin() + 1; for (unsigned N = FT->getNumParams(); N != 0; ++AI, --N) Args.push_back(&*AI); CallInst *CI = CallInst::Create(FT, &*F->arg_begin(), Args, "", BB); - ReturnInst *RI; - if (FT->getReturnType()->isVoidTy()) - RI = ReturnInst::Create(*Ctx, BB); - else - RI = ReturnInst::Create(*Ctx, CI, BB); + Type *RetType = FT->getReturnType(); + ReturnInst *RI = RetType->isVoidTy() ? ReturnInst::Create(*Ctx, BB) + : ReturnInst::Create(*Ctx, CI, BB); // F is called by a wrapped custom function with primitive shadows. So // its arguments and return value need conversion. DFSanFunction DFSF(*this, F, /*IsNativeABI=*/true); - Function::arg_iterator ValAI = F->arg_begin(), ShadowAI = AI; ++ValAI; + Function::arg_iterator ValAI = F->arg_begin(), ShadowAI = AI; + ++ValAI; for (unsigned N = FT->getNumParams(); N != 0; ++ValAI, ++ShadowAI, --N) { Value *Shadow = DFSF.expandFromPrimitiveShadow(ValAI->getType(), &*ShadowAI, CI); DFSF.ValShadowMap[&*ValAI] = Shadow; } + Function::arg_iterator RetShadowAI = ShadowAI; + const bool ShouldTrackOrigins = shouldTrackOrigins(); + if (ShouldTrackOrigins) { + ValAI = F->arg_begin(); + ++ValAI; + Function::arg_iterator OriginAI = ShadowAI; + if (!RetType->isVoidTy()) + ++OriginAI; + for (unsigned N = FT->getNumParams(); N != 0; ++ValAI, ++OriginAI, --N) { + DFSF.ValOriginMap[&*ValAI] = &*OriginAI; + } + } DFSanVisitor(DFSF).visitCallInst(*CI); - if (!FT->getReturnType()->isVoidTy()) { + if (!RetType->isVoidTy()) { Value *PrimitiveShadow = DFSF.collapseToPrimitiveShadow( DFSF.getShadow(RI->getReturnValue()), RI); - new StoreInst(PrimitiveShadow, &*std::prev(F->arg_end()), RI); + new StoreInst(PrimitiveShadow, &*RetShadowAI, RI); + if (ShouldTrackOrigins) { + Value *Origin = DFSF.getOrigin(RI->getReturnValue()); + new StoreInst(Origin, &*std::prev(F->arg_end()), RI); + } } } @@ -981,32 +1241,6 @@ void DataFlowSanitizer::initializeRuntimeFunctions(Module &M) { AL = AL.addAttribute(M.getContext(), AttributeList::FunctionIndex, Attribute::NoUnwind); AL = AL.addAttribute(M.getContext(), AttributeList::FunctionIndex, - Attribute::ReadNone); - AL = AL.addAttribute(M.getContext(), AttributeList::ReturnIndex, - Attribute::ZExt); - AL = AL.addParamAttribute(M.getContext(), 0, Attribute::ZExt); - AL = AL.addParamAttribute(M.getContext(), 1, Attribute::ZExt); - DFSanUnionFn = - Mod->getOrInsertFunction("__dfsan_union", DFSanUnionFnTy, AL); - } - { - AttributeList AL; - AL = AL.addAttribute(M.getContext(), AttributeList::FunctionIndex, - Attribute::NoUnwind); - AL = AL.addAttribute(M.getContext(), AttributeList::FunctionIndex, - Attribute::ReadNone); - AL = AL.addAttribute(M.getContext(), AttributeList::ReturnIndex, - Attribute::ZExt); - AL = AL.addParamAttribute(M.getContext(), 0, Attribute::ZExt); - AL = AL.addParamAttribute(M.getContext(), 1, Attribute::ZExt); - DFSanCheckedUnionFn = - Mod->getOrInsertFunction("dfsan_union", DFSanUnionFnTy, AL); - } - { - AttributeList AL; - AL = AL.addAttribute(M.getContext(), AttributeList::FunctionIndex, - Attribute::NoUnwind); - AL = AL.addAttribute(M.getContext(), AttributeList::FunctionIndex, Attribute::ReadOnly); AL = AL.addAttribute(M.getContext(), AttributeList::ReturnIndex, Attribute::ZExt); @@ -1021,14 +1255,15 @@ void DataFlowSanitizer::initializeRuntimeFunctions(Module &M) { Attribute::ReadOnly); AL = AL.addAttribute(M.getContext(), AttributeList::ReturnIndex, Attribute::ZExt); - DFSanUnionLoadFast16LabelsFn = Mod->getOrInsertFunction( - "__dfsan_union_load_fast16labels", DFSanUnionLoadFnTy, AL); + DFSanLoadLabelAndOriginFn = Mod->getOrInsertFunction( + "__dfsan_load_label_and_origin", DFSanLoadLabelAndOriginFnTy, AL); } DFSanUnimplementedFn = Mod->getOrInsertFunction("__dfsan_unimplemented", DFSanUnimplementedFnTy); { AttributeList AL; AL = AL.addParamAttribute(M.getContext(), 0, Attribute::ZExt); + AL = AL.addParamAttribute(M.getContext(), 1, Attribute::ZExt); DFSanSetLabelFn = Mod->getOrInsertFunction("__dfsan_set_label", DFSanSetLabelFnTy, AL); } @@ -1036,6 +1271,62 @@ void DataFlowSanitizer::initializeRuntimeFunctions(Module &M) { Mod->getOrInsertFunction("__dfsan_nonzero_label", DFSanNonzeroLabelFnTy); DFSanVarargWrapperFn = Mod->getOrInsertFunction("__dfsan_vararg_wrapper", DFSanVarargWrapperFnTy); + { + AttributeList AL; + AL = AL.addParamAttribute(M.getContext(), 0, Attribute::ZExt); + AL = AL.addAttribute(M.getContext(), AttributeList::ReturnIndex, + Attribute::ZExt); + DFSanChainOriginFn = Mod->getOrInsertFunction("__dfsan_chain_origin", + DFSanChainOriginFnTy, AL); + } + { + AttributeList AL; + AL = AL.addParamAttribute(M.getContext(), 0, Attribute::ZExt); + AL = AL.addParamAttribute(M.getContext(), 1, Attribute::ZExt); + AL = AL.addAttribute(M.getContext(), AttributeList::ReturnIndex, + Attribute::ZExt); + DFSanChainOriginIfTaintedFn = Mod->getOrInsertFunction( + "__dfsan_chain_origin_if_tainted", DFSanChainOriginIfTaintedFnTy, AL); + } + DFSanMemOriginTransferFn = Mod->getOrInsertFunction( + "__dfsan_mem_origin_transfer", DFSanMemOriginTransferFnTy); + + { + AttributeList AL; + AL = AL.addParamAttribute(M.getContext(), 0, Attribute::ZExt); + AL = AL.addParamAttribute(M.getContext(), 3, Attribute::ZExt); + DFSanMaybeStoreOriginFn = Mod->getOrInsertFunction( + "__dfsan_maybe_store_origin", DFSanMaybeStoreOriginFnTy, AL); + } + + DFSanRuntimeFunctions.insert( + DFSanUnionLoadFn.getCallee()->stripPointerCasts()); + DFSanRuntimeFunctions.insert( + DFSanLoadLabelAndOriginFn.getCallee()->stripPointerCasts()); + DFSanRuntimeFunctions.insert( + DFSanUnimplementedFn.getCallee()->stripPointerCasts()); + DFSanRuntimeFunctions.insert( + DFSanSetLabelFn.getCallee()->stripPointerCasts()); + DFSanRuntimeFunctions.insert( + DFSanNonzeroLabelFn.getCallee()->stripPointerCasts()); + DFSanRuntimeFunctions.insert( + DFSanVarargWrapperFn.getCallee()->stripPointerCasts()); + DFSanRuntimeFunctions.insert( + DFSanLoadCallbackFn.getCallee()->stripPointerCasts()); + DFSanRuntimeFunctions.insert( + DFSanStoreCallbackFn.getCallee()->stripPointerCasts()); + DFSanRuntimeFunctions.insert( + DFSanMemTransferCallbackFn.getCallee()->stripPointerCasts()); + DFSanRuntimeFunctions.insert( + DFSanCmpCallbackFn.getCallee()->stripPointerCasts()); + DFSanRuntimeFunctions.insert( + DFSanChainOriginFn.getCallee()->stripPointerCasts()); + DFSanRuntimeFunctions.insert( + DFSanChainOriginIfTaintedFn.getCallee()->stripPointerCasts()); + DFSanRuntimeFunctions.insert( + DFSanMemOriginTransferFn.getCallee()->stripPointerCasts()); + DFSanRuntimeFunctions.insert( + DFSanMaybeStoreOriginFn.getCallee()->stripPointerCasts()); } // Initializes event callback functions and declare them in the module @@ -1050,8 +1341,28 @@ void DataFlowSanitizer::initializeCallbackFunctions(Module &M) { Mod->getOrInsertFunction("__dfsan_cmp_callback", DFSanCmpCallbackFnTy); } +void DataFlowSanitizer::injectMetadataGlobals(Module &M) { + // These variables can be used: + // - by the runtime (to discover what the shadow width was, during + // compilation) + // - in testing (to avoid hardcoding the shadow width and type but instead + // extract them by pattern matching) + Type *IntTy = Type::getInt32Ty(*Ctx); + (void)Mod->getOrInsertGlobal("__dfsan_shadow_width_bits", IntTy, [&] { + return new GlobalVariable( + M, IntTy, /*isConstant=*/true, GlobalValue::WeakODRLinkage, + ConstantInt::get(IntTy, ShadowWidthBits), "__dfsan_shadow_width_bits"); + }); + (void)Mod->getOrInsertGlobal("__dfsan_shadow_width_bytes", IntTy, [&] { + return new GlobalVariable(M, IntTy, /*isConstant=*/true, + GlobalValue::WeakODRLinkage, + ConstantInt::get(IntTy, ShadowWidthBytes), + "__dfsan_shadow_width_bytes"); + }); +} + bool DataFlowSanitizer::runImpl(Module &M) { - init(M); + initializeModule(M); if (ABIList.isIn(M, "skip")) return false; @@ -1061,67 +1372,72 @@ bool DataFlowSanitizer::runImpl(Module &M) { bool Changed = false; - Type *ArgTLSTy = ArrayType::get(Type::getInt64Ty(*Ctx), kArgTLSSize / 8); - ArgTLS = Mod->getOrInsertGlobal("__dfsan_arg_tls", ArgTLSTy); - if (GlobalVariable *G = dyn_cast<GlobalVariable>(ArgTLS)) { - Changed |= G->getThreadLocalMode() != GlobalVariable::InitialExecTLSModel; - G->setThreadLocalMode(GlobalVariable::InitialExecTLSModel); - } - Type *RetvalTLSTy = - ArrayType::get(Type::getInt64Ty(*Ctx), kRetvalTLSSize / 8); - RetvalTLS = Mod->getOrInsertGlobal("__dfsan_retval_tls", RetvalTLSTy); - if (GlobalVariable *G = dyn_cast<GlobalVariable>(RetvalTLS)) { - Changed |= G->getThreadLocalMode() != GlobalVariable::InitialExecTLSModel; - G->setThreadLocalMode(GlobalVariable::InitialExecTLSModel); - } + auto GetOrInsertGlobal = [this, &Changed](StringRef Name, + Type *Ty) -> Constant * { + Constant *C = Mod->getOrInsertGlobal(Name, Ty); + if (GlobalVariable *G = dyn_cast<GlobalVariable>(C)) { + Changed |= G->getThreadLocalMode() != GlobalVariable::InitialExecTLSModel; + G->setThreadLocalMode(GlobalVariable::InitialExecTLSModel); + } + return C; + }; + + // These globals must be kept in sync with the ones in dfsan.cpp. + ArgTLS = + GetOrInsertGlobal("__dfsan_arg_tls", + ArrayType::get(Type::getInt64Ty(*Ctx), ArgTLSSize / 8)); + RetvalTLS = GetOrInsertGlobal( + "__dfsan_retval_tls", + ArrayType::get(Type::getInt64Ty(*Ctx), RetvalTLSSize / 8)); + ArgOriginTLSTy = ArrayType::get(OriginTy, NumOfElementsInArgOrgTLS); + ArgOriginTLS = GetOrInsertGlobal("__dfsan_arg_origin_tls", ArgOriginTLSTy); + RetvalOriginTLS = GetOrInsertGlobal("__dfsan_retval_origin_tls", OriginTy); - ExternalShadowMask = - Mod->getOrInsertGlobal(kDFSanExternShadowPtrMask, IntptrTy); + (void)Mod->getOrInsertGlobal("__dfsan_track_origins", OriginTy, [&] { + Changed = true; + return new GlobalVariable( + M, OriginTy, true, GlobalValue::WeakODRLinkage, + ConstantInt::getSigned(OriginTy, + shouldTrackOrigins() ? ClTrackOrigins : 0), + "__dfsan_track_origins"); + }); + + injectMetadataGlobals(M); initializeCallbackFunctions(M); initializeRuntimeFunctions(M); std::vector<Function *> FnsToInstrument; SmallPtrSet<Function *, 2> FnsWithNativeABI; - for (Function &i : M) { - if (!i.isIntrinsic() && - &i != DFSanUnionFn.getCallee()->stripPointerCasts() && - &i != DFSanCheckedUnionFn.getCallee()->stripPointerCasts() && - &i != DFSanUnionLoadFn.getCallee()->stripPointerCasts() && - &i != DFSanUnionLoadFast16LabelsFn.getCallee()->stripPointerCasts() && - &i != DFSanUnimplementedFn.getCallee()->stripPointerCasts() && - &i != DFSanSetLabelFn.getCallee()->stripPointerCasts() && - &i != DFSanNonzeroLabelFn.getCallee()->stripPointerCasts() && - &i != DFSanVarargWrapperFn.getCallee()->stripPointerCasts() && - &i != DFSanLoadCallbackFn.getCallee()->stripPointerCasts() && - &i != DFSanStoreCallbackFn.getCallee()->stripPointerCasts() && - &i != DFSanMemTransferCallbackFn.getCallee()->stripPointerCasts() && - &i != DFSanCmpCallbackFn.getCallee()->stripPointerCasts()) - FnsToInstrument.push_back(&i); - } + for (Function &F : M) + if (!F.isIntrinsic() && !DFSanRuntimeFunctions.contains(&F)) + FnsToInstrument.push_back(&F); // Give function aliases prefixes when necessary, and build wrappers where the // instrumentedness is inconsistent. - for (Module::alias_iterator i = M.alias_begin(), e = M.alias_end(); i != e;) { - GlobalAlias *GA = &*i; - ++i; + for (Module::alias_iterator AI = M.alias_begin(), AE = M.alias_end(); + AI != AE;) { + GlobalAlias *GA = &*AI; + ++AI; // Don't stop on weak. We assume people aren't playing games with the // instrumentedness of overridden weak aliases. - if (auto F = dyn_cast<Function>(GA->getBaseObject())) { - bool GAInst = isInstrumented(GA), FInst = isInstrumented(F); - if (GAInst && FInst) { - addGlobalNamePrefix(GA); - } else if (GAInst != FInst) { - // Non-instrumented alias of an instrumented function, or vice versa. - // Replace the alias with a native-ABI wrapper of the aliasee. The pass - // below will take care of instrumenting it. - Function *NewF = - buildWrapperFunction(F, "", GA->getLinkage(), F->getFunctionType()); - GA->replaceAllUsesWith(ConstantExpr::getBitCast(NewF, GA->getType())); - NewF->takeName(GA); - GA->eraseFromParent(); - FnsToInstrument.push_back(NewF); - } + auto *F = dyn_cast<Function>(GA->getBaseObject()); + if (!F) + continue; + + bool GAInst = isInstrumented(GA), FInst = isInstrumented(F); + if (GAInst && FInst) { + addGlobalNameSuffix(GA); + } else if (GAInst != FInst) { + // Non-instrumented alias of an instrumented function, or vice versa. + // Replace the alias with a native-ABI wrapper of the aliasee. The pass + // below will take care of instrumenting it. + Function *NewF = + buildWrapperFunction(F, "", GA->getLinkage(), F->getFunctionType()); + GA->replaceAllUsesWith(ConstantExpr::getBitCast(NewF, GA->getType())); + NewF->takeName(GA); + GA->eraseFromParent(); + FnsToInstrument.push_back(NewF); } } @@ -1130,18 +1446,19 @@ bool DataFlowSanitizer::runImpl(Module &M) { // First, change the ABI of every function in the module. ABI-listed // functions keep their original ABI and get a wrapper function. - for (std::vector<Function *>::iterator i = FnsToInstrument.begin(), - e = FnsToInstrument.end(); - i != e; ++i) { - Function &F = **i; + for (std::vector<Function *>::iterator FI = FnsToInstrument.begin(), + FE = FnsToInstrument.end(); + FI != FE; ++FI) { + Function &F = **FI; FunctionType *FT = F.getFunctionType(); bool IsZeroArgsVoidRet = (FT->getNumParams() == 0 && !FT->isVarArg() && FT->getReturnType()->isVoidTy()); if (isInstrumented(&F)) { - // Instrumented functions get a 'dfs$' prefix. This allows us to more - // easily identify cases of mismatching ABIs. + // Instrumented functions get a '.dfsan' suffix. This allows us to more + // easily identify cases of mismatching ABIs. This naming scheme is + // mangling-compatible (see Itanium ABI), using a vendor-specific suffix. if (getInstrumentedABI() == IA_Args && !IsZeroArgsVoidRet) { FunctionType *NewFT = getArgsFunctionType(FT); Function *NewF = Function::Create(NewFT, F.getLinkage(), @@ -1172,29 +1489,29 @@ bool DataFlowSanitizer::runImpl(Module &M) { ConstantExpr::getBitCast(NewF, PointerType::getUnqual(FT))); NewF->takeName(&F); F.eraseFromParent(); - *i = NewF; - addGlobalNamePrefix(NewF); + *FI = NewF; + addGlobalNameSuffix(NewF); } else { - addGlobalNamePrefix(&F); + addGlobalNameSuffix(&F); } } else if (!IsZeroArgsVoidRet || getWrapperKind(&F) == WK_Custom) { // Build a wrapper function for F. The wrapper simply calls F, and is // added to FnsToInstrument so that any instrumentation according to its // WrapperKind is done in the second pass below. - FunctionType *NewFT = getInstrumentedABI() == IA_Args - ? getArgsFunctionType(FT) - : FT; + FunctionType *NewFT = + getInstrumentedABI() == IA_Args ? getArgsFunctionType(FT) : FT; // If the function being wrapped has local linkage, then preserve the // function's linkage in the wrapper function. - GlobalValue::LinkageTypes wrapperLinkage = - F.hasLocalLinkage() - ? F.getLinkage() - : GlobalValue::LinkOnceODRLinkage; + GlobalValue::LinkageTypes WrapperLinkage = + F.hasLocalLinkage() ? F.getLinkage() + : GlobalValue::LinkOnceODRLinkage; Function *NewF = buildWrapperFunction( - &F, std::string("dfsw$") + std::string(F.getName()), - wrapperLinkage, NewFT); + &F, + (shouldTrackOrigins() ? std::string("dfso$") : std::string("dfsw$")) + + std::string(F.getName()), + WrapperLinkage, NewFT); if (getInstrumentedABI() == IA_TLS) NewF->removeAttributes(AttributeList::FunctionIndex, ReadOnlyNoneAttrs); @@ -1203,7 +1520,7 @@ bool DataFlowSanitizer::runImpl(Module &M) { F.replaceAllUsesWith(WrappedFnCst); UnwrappedFnMap[WrappedFnCst] = &F; - *i = NewF; + *FI = NewF; if (!F.isDeclaration()) { // This function is probably defining an interposition of an @@ -1215,34 +1532,34 @@ bool DataFlowSanitizer::runImpl(Module &M) { // This code needs to rebuild the iterators, as they may be invalidated // by the push_back, taking care that the new range does not include // any functions added by this code. - size_t N = i - FnsToInstrument.begin(), - Count = e - FnsToInstrument.begin(); + size_t N = FI - FnsToInstrument.begin(), + Count = FE - FnsToInstrument.begin(); FnsToInstrument.push_back(&F); - i = FnsToInstrument.begin() + N; - e = FnsToInstrument.begin() + Count; + FI = FnsToInstrument.begin() + N; + FE = FnsToInstrument.begin() + Count; } - // Hopefully, nobody will try to indirectly call a vararg - // function... yet. + // Hopefully, nobody will try to indirectly call a vararg + // function... yet. } else if (FT->isVarArg()) { UnwrappedFnMap[&F] = &F; - *i = nullptr; + *FI = nullptr; } } - for (Function *i : FnsToInstrument) { - if (!i || i->isDeclaration()) + for (Function *F : FnsToInstrument) { + if (!F || F->isDeclaration()) continue; - removeUnreachableBlocks(*i); + removeUnreachableBlocks(*F); - DFSanFunction DFSF(*this, i, FnsWithNativeABI.count(i)); + DFSanFunction DFSF(*this, F, FnsWithNativeABI.count(F)); // DFSanVisitor may create new basic blocks, which confuses df_iterator. // Build a copy of the list before iterating over it. - SmallVector<BasicBlock *, 4> BBList(depth_first(&i->getEntryBlock())); + SmallVector<BasicBlock *, 4> BBList(depth_first(&F->getEntryBlock())); - for (BasicBlock *i : BBList) { - Instruction *Inst = &i->front(); + for (BasicBlock *BB : BBList) { + Instruction *Inst = &BB->front(); while (true) { // DFSanVisitor may split the current basic block, changing the current // instruction's next pointer and moving the next instruction to the @@ -1263,14 +1580,14 @@ bool DataFlowSanitizer::runImpl(Module &M) { // until we have visited every block. Therefore, the code that handles phi // nodes adds them to the PHIFixups list so that they can be properly // handled here. - for (std::vector<std::pair<PHINode *, PHINode *>>::iterator - i = DFSF.PHIFixups.begin(), - e = DFSF.PHIFixups.end(); - i != e; ++i) { - for (unsigned val = 0, n = i->first->getNumIncomingValues(); val != n; - ++val) { - i->second->setIncomingValue( - val, DFSF.getShadow(i->first->getIncomingValue(val))); + for (DFSanFunction::PHIFixupElement &P : DFSF.PHIFixups) { + for (unsigned Val = 0, N = P.Phi->getNumIncomingValues(); Val != N; + ++Val) { + P.ShadowPhi->setIncomingValue( + Val, DFSF.getShadow(P.Phi->getIncomingValue(Val))); + if (P.OriginPhi) + P.OriginPhi->setIncomingValue( + Val, DFSF.getOrigin(P.Phi->getIncomingValue(Val))); } } @@ -1316,6 +1633,55 @@ Value *DFSanFunction::getRetvalTLS(Type *T, IRBuilder<> &IRB) { DFS.RetvalTLS, PointerType::get(DFS.getShadowTy(T), 0), "_dfsret"); } +Value *DFSanFunction::getRetvalOriginTLS() { return DFS.RetvalOriginTLS; } + +Value *DFSanFunction::getArgOriginTLS(unsigned ArgNo, IRBuilder<> &IRB) { + return IRB.CreateConstGEP2_64(DFS.ArgOriginTLSTy, DFS.ArgOriginTLS, 0, ArgNo, + "_dfsarg_o"); +} + +Value *DFSanFunction::getOrigin(Value *V) { + assert(DFS.shouldTrackOrigins()); + if (!isa<Argument>(V) && !isa<Instruction>(V)) + return DFS.ZeroOrigin; + Value *&Origin = ValOriginMap[V]; + if (!Origin) { + if (Argument *A = dyn_cast<Argument>(V)) { + if (IsNativeABI) + return DFS.ZeroOrigin; + switch (IA) { + case DataFlowSanitizer::IA_TLS: { + if (A->getArgNo() < DFS.NumOfElementsInArgOrgTLS) { + Instruction *ArgOriginTLSPos = &*F->getEntryBlock().begin(); + IRBuilder<> IRB(ArgOriginTLSPos); + Value *ArgOriginPtr = getArgOriginTLS(A->getArgNo(), IRB); + Origin = IRB.CreateLoad(DFS.OriginTy, ArgOriginPtr); + } else { + // Overflow + Origin = DFS.ZeroOrigin; + } + break; + } + case DataFlowSanitizer::IA_Args: { + Origin = DFS.ZeroOrigin; + break; + } + } + } else { + Origin = DFS.ZeroOrigin; + } + } + return Origin; +} + +void DFSanFunction::setOrigin(Instruction *I, Value *Origin) { + if (!DFS.shouldTrackOrigins()) + return; + assert(!ValOriginMap.count(I)); + assert(Origin->getType() == DFS.OriginTy); + ValOriginMap[I] = Origin; +} + Value *DFSanFunction::getShadowForTLSArgument(Argument *A) { unsigned ArgOffset = 0; const DataLayout &DL = F->getParent()->getDataLayout(); @@ -1328,20 +1694,20 @@ Value *DFSanFunction::getShadowForTLSArgument(Argument *A) { unsigned Size = DL.getTypeAllocSize(DFS.getShadowTy(&FArg)); if (A != &FArg) { - ArgOffset += alignTo(Size, kShadowTLSAlignment); - if (ArgOffset > kArgTLSSize) + ArgOffset += alignTo(Size, ShadowTLSAlignment); + if (ArgOffset > ArgTLSSize) break; // ArgTLS overflows, uses a zero shadow. continue; } - if (ArgOffset + Size > kArgTLSSize) + if (ArgOffset + Size > ArgTLSSize) break; // ArgTLS overflows, uses a zero shadow. Instruction *ArgTLSPos = &*F->getEntryBlock().begin(); IRBuilder<> IRB(ArgTLSPos); Value *ArgShadowPtr = getArgTLS(FArg.getType(), ArgOffset, IRB); return IRB.CreateAlignedLoad(DFS.getShadowTy(&FArg), ArgShadowPtr, - kShadowTLSAlignment); + ShadowTLSAlignment); } return DFS.getZeroShadow(A); @@ -1362,10 +1728,9 @@ Value *DFSanFunction::getShadow(Value *V) { } case DataFlowSanitizer::IA_Args: { unsigned ArgIdx = A->getArgNo() + F->arg_size() / 2; - Function::arg_iterator i = F->arg_begin(); - while (ArgIdx--) - ++i; - Shadow = &*i; + Function::arg_iterator Arg = F->arg_begin(); + std::advance(Arg, ArgIdx); + Shadow = &*Arg; assert(Shadow->getType() == DFS.PrimitiveShadowTy); break; } @@ -1385,20 +1750,69 @@ void DFSanFunction::setShadow(Instruction *I, Value *Shadow) { ValShadowMap[I] = Shadow; } -Value *DataFlowSanitizer::getShadowAddress(Value *Addr, Instruction *Pos) { +/// Compute the integer shadow offset that corresponds to a given +/// application address. +/// +/// Offset = (Addr & ~AndMask) ^ XorMask +Value *DataFlowSanitizer::getShadowOffset(Value *Addr, IRBuilder<> &IRB) { assert(Addr != RetvalTLS && "Reinstrumenting?"); + Value *OffsetLong = IRB.CreatePointerCast(Addr, IntptrTy); + + uint64_t AndMask = MapParams->AndMask; + if (AndMask) + OffsetLong = + IRB.CreateAnd(OffsetLong, ConstantInt::get(IntptrTy, ~AndMask)); + + uint64_t XorMask = MapParams->XorMask; + if (XorMask) + OffsetLong = IRB.CreateXor(OffsetLong, ConstantInt::get(IntptrTy, XorMask)); + return OffsetLong; +} + +std::pair<Value *, Value *> +DataFlowSanitizer::getShadowOriginAddress(Value *Addr, Align InstAlignment, + Instruction *Pos) { + // Returns ((Addr & shadow_mask) + origin_base - shadow_base) & ~4UL + IRBuilder<> IRB(Pos); + Value *ShadowOffset = getShadowOffset(Addr, IRB); + Value *ShadowLong = ShadowOffset; + uint64_t ShadowBase = MapParams->ShadowBase; + if (ShadowBase != 0) { + ShadowLong = + IRB.CreateAdd(ShadowLong, ConstantInt::get(IntptrTy, ShadowBase)); + } + IntegerType *ShadowTy = IntegerType::get(*Ctx, ShadowWidthBits); + Value *ShadowPtr = + IRB.CreateIntToPtr(ShadowLong, PointerType::get(ShadowTy, 0)); + Value *OriginPtr = nullptr; + if (shouldTrackOrigins()) { + Value *OriginLong = ShadowOffset; + uint64_t OriginBase = MapParams->OriginBase; + if (OriginBase != 0) + OriginLong = + IRB.CreateAdd(OriginLong, ConstantInt::get(IntptrTy, OriginBase)); + const Align Alignment = llvm::assumeAligned(InstAlignment.value()); + // When alignment is >= 4, Addr must be aligned to 4, otherwise it is UB. + // So Mask is unnecessary. + if (Alignment < MinOriginAlignment) { + uint64_t Mask = MinOriginAlignment.value() - 1; + OriginLong = IRB.CreateAnd(OriginLong, ConstantInt::get(IntptrTy, ~Mask)); + } + OriginPtr = IRB.CreateIntToPtr(OriginLong, OriginPtrTy); + } + return std::make_pair(ShadowPtr, OriginPtr); +} + +Value *DataFlowSanitizer::getShadowAddress(Value *Addr, Instruction *Pos, + Value *ShadowOffset) { IRBuilder<> IRB(Pos); - Value *ShadowPtrMaskValue; - if (DFSanRuntimeShadowMask) - ShadowPtrMaskValue = IRB.CreateLoad(IntptrTy, ExternalShadowMask); - else - ShadowPtrMaskValue = ShadowPtrMask; - return IRB.CreateIntToPtr( - IRB.CreateMul( - IRB.CreateAnd(IRB.CreatePtrToInt(Addr, IntptrTy), - IRB.CreatePtrToInt(ShadowPtrMaskValue, IntptrTy)), - ShadowPtrMul), - PrimitiveShadowPtrTy); + return IRB.CreateIntToPtr(ShadowOffset, PrimitiveShadowPtrTy); +} + +Value *DataFlowSanitizer::getShadowAddress(Value *Addr, Instruction *Pos) { + IRBuilder<> IRB(Pos); + Value *ShadowOffset = getShadowOffset(Addr, IRB); + return getShadowAddress(Addr, Pos, ShadowOffset); } Value *DFSanFunction::combineShadowsThenConvert(Type *T, Value *V1, Value *V2, @@ -1423,8 +1837,9 @@ Value *DFSanFunction::combineShadows(Value *V1, Value *V2, Instruction *Pos) { if (std::includes(V1Elems->second.begin(), V1Elems->second.end(), V2Elems->second.begin(), V2Elems->second.end())) { return collapseToPrimitiveShadow(V1, Pos); - } else if (std::includes(V2Elems->second.begin(), V2Elems->second.end(), - V1Elems->second.begin(), V1Elems->second.end())) { + } + if (std::includes(V2Elems->second.begin(), V2Elems->second.end(), + V1Elems->second.begin(), V1Elems->second.end())) { return collapseToPrimitiveShadow(V2, Pos); } } else if (V1Elems != ShadowElements.end()) { @@ -1447,37 +1862,8 @@ Value *DFSanFunction::combineShadows(Value *V1, Value *V2, Instruction *Pos) { Value *PV2 = collapseToPrimitiveShadow(V2, Pos); IRBuilder<> IRB(Pos); - if (ClFast16Labels) { - CCS.Block = Pos->getParent(); - CCS.Shadow = IRB.CreateOr(PV1, PV2); - } else if (AvoidNewBlocks) { - CallInst *Call = IRB.CreateCall(DFS.DFSanCheckedUnionFn, {PV1, PV2}); - Call->addAttribute(AttributeList::ReturnIndex, Attribute::ZExt); - Call->addParamAttr(0, Attribute::ZExt); - Call->addParamAttr(1, Attribute::ZExt); - - CCS.Block = Pos->getParent(); - CCS.Shadow = Call; - } else { - BasicBlock *Head = Pos->getParent(); - Value *Ne = IRB.CreateICmpNE(PV1, PV2); - BranchInst *BI = cast<BranchInst>(SplitBlockAndInsertIfThen( - Ne, Pos, /*Unreachable=*/false, DFS.ColdCallWeights, &DT)); - IRBuilder<> ThenIRB(BI); - CallInst *Call = ThenIRB.CreateCall(DFS.DFSanUnionFn, {PV1, PV2}); - Call->addAttribute(AttributeList::ReturnIndex, Attribute::ZExt); - Call->addParamAttr(0, Attribute::ZExt); - Call->addParamAttr(1, Attribute::ZExt); - - BasicBlock *Tail = BI->getSuccessor(0); - PHINode *Phi = - PHINode::Create(DFS.PrimitiveShadowTy, 2, "", &Tail->front()); - Phi->addIncoming(Call, Call->getParent()); - Phi->addIncoming(PV1, Head); - - CCS.Block = Tail; - CCS.Shadow = Phi; - } + CCS.Block = Pos->getParent(); + CCS.Shadow = IRB.CreateOr(PV1, PV2); std::set<Value *> UnionElems; if (V1Elems != ShadowElements.end()) { @@ -1503,32 +1889,212 @@ Value *DFSanFunction::combineOperandShadows(Instruction *Inst) { return DFS.getZeroShadow(Inst); Value *Shadow = getShadow(Inst->getOperand(0)); - for (unsigned i = 1, n = Inst->getNumOperands(); i != n; ++i) { - Shadow = combineShadows(Shadow, getShadow(Inst->getOperand(i)), Inst); - } + for (unsigned I = 1, N = Inst->getNumOperands(); I < N; ++I) + Shadow = combineShadows(Shadow, getShadow(Inst->getOperand(I)), Inst); + return expandFromPrimitiveShadow(Inst->getType(), Shadow, Inst); } -Value *DFSanVisitor::visitOperandShadowInst(Instruction &I) { +void DFSanVisitor::visitInstOperands(Instruction &I) { Value *CombinedShadow = DFSF.combineOperandShadows(&I); DFSF.setShadow(&I, CombinedShadow); - return CombinedShadow; + visitInstOperandOrigins(I); +} + +Value *DFSanFunction::combineOrigins(const std::vector<Value *> &Shadows, + const std::vector<Value *> &Origins, + Instruction *Pos, ConstantInt *Zero) { + assert(Shadows.size() == Origins.size()); + size_t Size = Origins.size(); + if (Size == 0) + return DFS.ZeroOrigin; + Value *Origin = nullptr; + if (!Zero) + Zero = DFS.ZeroPrimitiveShadow; + for (size_t I = 0; I != Size; ++I) { + Value *OpOrigin = Origins[I]; + Constant *ConstOpOrigin = dyn_cast<Constant>(OpOrigin); + if (ConstOpOrigin && ConstOpOrigin->isNullValue()) + continue; + if (!Origin) { + Origin = OpOrigin; + continue; + } + Value *OpShadow = Shadows[I]; + Value *PrimitiveShadow = collapseToPrimitiveShadow(OpShadow, Pos); + IRBuilder<> IRB(Pos); + Value *Cond = IRB.CreateICmpNE(PrimitiveShadow, Zero); + Origin = IRB.CreateSelect(Cond, OpOrigin, Origin); + } + return Origin ? Origin : DFS.ZeroOrigin; +} + +Value *DFSanFunction::combineOperandOrigins(Instruction *Inst) { + size_t Size = Inst->getNumOperands(); + std::vector<Value *> Shadows(Size); + std::vector<Value *> Origins(Size); + for (unsigned I = 0; I != Size; ++I) { + Shadows[I] = getShadow(Inst->getOperand(I)); + Origins[I] = getOrigin(Inst->getOperand(I)); + } + return combineOrigins(Shadows, Origins, Inst); +} + +void DFSanVisitor::visitInstOperandOrigins(Instruction &I) { + if (!DFSF.DFS.shouldTrackOrigins()) + return; + Value *CombinedOrigin = DFSF.combineOperandOrigins(&I); + DFSF.setOrigin(&I, CombinedOrigin); +} + +Align DFSanFunction::getShadowAlign(Align InstAlignment) { + const Align Alignment = ClPreserveAlignment ? InstAlignment : Align(1); + return Align(Alignment.value() * DFS.ShadowWidthBytes); +} + +Align DFSanFunction::getOriginAlign(Align InstAlignment) { + const Align Alignment = llvm::assumeAligned(InstAlignment.value()); + return Align(std::max(MinOriginAlignment, Alignment)); +} + +bool DFSanFunction::useCallbackLoadLabelAndOrigin(uint64_t Size, + Align InstAlignment) { + // When enabling tracking load instructions, we always use + // __dfsan_load_label_and_origin to reduce code size. + if (ClTrackOrigins == 2) + return true; + + assert(Size != 0); + // * if Size == 1, it is sufficient to load its origin aligned at 4. + // * if Size == 2, we assume most cases Addr % 2 == 0, so it is sufficient to + // load its origin aligned at 4. If not, although origins may be lost, it + // should not happen very often. + // * if align >= 4, Addr must be aligned to 4, otherwise it is UB. When + // Size % 4 == 0, it is more efficient to load origins without callbacks. + // * Otherwise we use __dfsan_load_label_and_origin. + // This should ensure that common cases run efficiently. + if (Size <= 2) + return false; + + const Align Alignment = llvm::assumeAligned(InstAlignment.value()); + return Alignment < MinOriginAlignment || !DFS.hasLoadSizeForFastPath(Size); +} + +Value *DataFlowSanitizer::loadNextOrigin(Instruction *Pos, Align OriginAlign, + Value **OriginAddr) { + IRBuilder<> IRB(Pos); + *OriginAddr = + IRB.CreateGEP(OriginTy, *OriginAddr, ConstantInt::get(IntptrTy, 1)); + return IRB.CreateAlignedLoad(OriginTy, *OriginAddr, OriginAlign); +} + +std::pair<Value *, Value *> DFSanFunction::loadShadowFast( + Value *ShadowAddr, Value *OriginAddr, uint64_t Size, Align ShadowAlign, + Align OriginAlign, Value *FirstOrigin, Instruction *Pos) { + const bool ShouldTrackOrigins = DFS.shouldTrackOrigins(); + const uint64_t ShadowSize = Size * DFS.ShadowWidthBytes; + + assert(Size >= 4 && "Not large enough load size for fast path!"); + + // Used for origin tracking. + std::vector<Value *> Shadows; + std::vector<Value *> Origins; + + // Load instructions in LLVM can have arbitrary byte sizes (e.g., 3, 12, 20) + // but this function is only used in a subset of cases that make it possible + // to optimize the instrumentation. + // + // Specifically, when the shadow size in bytes (i.e., loaded bytes x shadow + // per byte) is either: + // - a multiple of 8 (common) + // - equal to 4 (only for load32) + // + // For the second case, we can fit the wide shadow in a 32-bit integer. In all + // other cases, we use a 64-bit integer to hold the wide shadow. + Type *WideShadowTy = + ShadowSize == 4 ? Type::getInt32Ty(*DFS.Ctx) : Type::getInt64Ty(*DFS.Ctx); + + IRBuilder<> IRB(Pos); + Value *WideAddr = IRB.CreateBitCast(ShadowAddr, WideShadowTy->getPointerTo()); + Value *CombinedWideShadow = + IRB.CreateAlignedLoad(WideShadowTy, WideAddr, ShadowAlign); + + unsigned WideShadowBitWidth = WideShadowTy->getIntegerBitWidth(); + const uint64_t BytesPerWideShadow = WideShadowBitWidth / DFS.ShadowWidthBits; + + auto AppendWideShadowAndOrigin = [&](Value *WideShadow, Value *Origin) { + if (BytesPerWideShadow > 4) { + assert(BytesPerWideShadow == 8); + // The wide shadow relates to two origin pointers: one for the first four + // application bytes, and one for the latest four. We use a left shift to + // get just the shadow bytes that correspond to the first origin pointer, + // and then the entire shadow for the second origin pointer (which will be + // chosen by combineOrigins() iff the least-significant half of the wide + // shadow was empty but the other half was not). + Value *WideShadowLo = IRB.CreateShl( + WideShadow, ConstantInt::get(WideShadowTy, WideShadowBitWidth / 2)); + Shadows.push_back(WideShadow); + Origins.push_back(DFS.loadNextOrigin(Pos, OriginAlign, &OriginAddr)); + + Shadows.push_back(WideShadowLo); + Origins.push_back(Origin); + } else { + Shadows.push_back(WideShadow); + Origins.push_back(Origin); + } + }; + + if (ShouldTrackOrigins) + AppendWideShadowAndOrigin(CombinedWideShadow, FirstOrigin); + + // First OR all the WideShadows (i.e., 64bit or 32bit shadow chunks) linearly; + // then OR individual shadows within the combined WideShadow by binary ORing. + // This is fewer instructions than ORing shadows individually, since it + // needs logN shift/or instructions (N being the bytes of the combined wide + // shadow). + for (uint64_t ByteOfs = BytesPerWideShadow; ByteOfs < Size; + ByteOfs += BytesPerWideShadow) { + WideAddr = IRB.CreateGEP(WideShadowTy, WideAddr, + ConstantInt::get(DFS.IntptrTy, 1)); + Value *NextWideShadow = + IRB.CreateAlignedLoad(WideShadowTy, WideAddr, ShadowAlign); + CombinedWideShadow = IRB.CreateOr(CombinedWideShadow, NextWideShadow); + if (ShouldTrackOrigins) { + Value *NextOrigin = DFS.loadNextOrigin(Pos, OriginAlign, &OriginAddr); + AppendWideShadowAndOrigin(NextWideShadow, NextOrigin); + } + } + for (unsigned Width = WideShadowBitWidth / 2; Width >= DFS.ShadowWidthBits; + Width >>= 1) { + Value *ShrShadow = IRB.CreateLShr(CombinedWideShadow, Width); + CombinedWideShadow = IRB.CreateOr(CombinedWideShadow, ShrShadow); + } + return {IRB.CreateTrunc(CombinedWideShadow, DFS.PrimitiveShadowTy), + ShouldTrackOrigins + ? combineOrigins(Shadows, Origins, Pos, + ConstantInt::getSigned(IRB.getInt64Ty(), 0)) + : DFS.ZeroOrigin}; } -// Generates IR to load shadow corresponding to bytes [Addr, Addr+Size), where -// Addr has alignment Align, and take the union of each of those shadows. The -// returned shadow always has primitive type. -Value *DFSanFunction::loadShadow(Value *Addr, uint64_t Size, uint64_t Align, - Instruction *Pos) { +std::pair<Value *, Value *> DFSanFunction::loadShadowOriginSansLoadTracking( + Value *Addr, uint64_t Size, Align InstAlignment, Instruction *Pos) { + const bool ShouldTrackOrigins = DFS.shouldTrackOrigins(); + + // Non-escaped loads. if (AllocaInst *AI = dyn_cast<AllocaInst>(Addr)) { - const auto i = AllocaShadowMap.find(AI); - if (i != AllocaShadowMap.end()) { + const auto SI = AllocaShadowMap.find(AI); + if (SI != AllocaShadowMap.end()) { IRBuilder<> IRB(Pos); - return IRB.CreateLoad(DFS.PrimitiveShadowTy, i->second); + Value *ShadowLI = IRB.CreateLoad(DFS.PrimitiveShadowTy, SI->second); + const auto OI = AllocaOriginMap.find(AI); + assert(!ShouldTrackOrigins || OI != AllocaOriginMap.end()); + return {ShadowLI, ShouldTrackOrigins + ? IRB.CreateLoad(DFS.OriginTy, OI->second) + : nullptr}; } } - const llvm::Align ShadowAlign(Align * DFS.ShadowWidthBytes); + // Load from constant addresses. SmallVector<const Value *, 2> Objs; getUnderlyingObjects(Addr, Objs); bool AllConstants = true; @@ -1542,124 +2108,106 @@ Value *DFSanFunction::loadShadow(Value *Addr, uint64_t Size, uint64_t Align, break; } if (AllConstants) - return DFS.ZeroPrimitiveShadow; + return {DFS.ZeroPrimitiveShadow, + ShouldTrackOrigins ? DFS.ZeroOrigin : nullptr}; - Value *ShadowAddr = DFS.getShadowAddress(Addr, Pos); + if (Size == 0) + return {DFS.ZeroPrimitiveShadow, + ShouldTrackOrigins ? DFS.ZeroOrigin : nullptr}; + + // Use callback to load if this is not an optimizable case for origin + // tracking. + if (ShouldTrackOrigins && + useCallbackLoadLabelAndOrigin(Size, InstAlignment)) { + IRBuilder<> IRB(Pos); + CallInst *Call = + IRB.CreateCall(DFS.DFSanLoadLabelAndOriginFn, + {IRB.CreatePointerCast(Addr, IRB.getInt8PtrTy()), + ConstantInt::get(DFS.IntptrTy, Size)}); + Call->addAttribute(AttributeList::ReturnIndex, Attribute::ZExt); + return {IRB.CreateTrunc(IRB.CreateLShr(Call, DFS.OriginWidthBits), + DFS.PrimitiveShadowTy), + IRB.CreateTrunc(Call, DFS.OriginTy)}; + } + + // Other cases that support loading shadows or origins in a fast way. + Value *ShadowAddr, *OriginAddr; + std::tie(ShadowAddr, OriginAddr) = + DFS.getShadowOriginAddress(Addr, InstAlignment, Pos); + + const Align ShadowAlign = getShadowAlign(InstAlignment); + const Align OriginAlign = getOriginAlign(InstAlignment); + Value *Origin = nullptr; + if (ShouldTrackOrigins) { + IRBuilder<> IRB(Pos); + Origin = IRB.CreateAlignedLoad(DFS.OriginTy, OriginAddr, OriginAlign); + } + + // When the byte size is small enough, we can load the shadow directly with + // just a few instructions. switch (Size) { - case 0: - return DFS.ZeroPrimitiveShadow; case 1: { LoadInst *LI = new LoadInst(DFS.PrimitiveShadowTy, ShadowAddr, "", Pos); LI->setAlignment(ShadowAlign); - return LI; + return {LI, Origin}; } case 2: { IRBuilder<> IRB(Pos); Value *ShadowAddr1 = IRB.CreateGEP(DFS.PrimitiveShadowTy, ShadowAddr, ConstantInt::get(DFS.IntptrTy, 1)); - return combineShadows( - IRB.CreateAlignedLoad(DFS.PrimitiveShadowTy, ShadowAddr, ShadowAlign), - IRB.CreateAlignedLoad(DFS.PrimitiveShadowTy, ShadowAddr1, ShadowAlign), - Pos); + Value *Load = + IRB.CreateAlignedLoad(DFS.PrimitiveShadowTy, ShadowAddr, ShadowAlign); + Value *Load1 = + IRB.CreateAlignedLoad(DFS.PrimitiveShadowTy, ShadowAddr1, ShadowAlign); + return {combineShadows(Load, Load1, Pos), Origin}; } } + bool HasSizeForFastPath = DFS.hasLoadSizeForFastPath(Size); - if (ClFast16Labels && Size % (64 / DFS.ShadowWidthBits) == 0) { - // First OR all the WideShadows, then OR individual shadows within the - // combined WideShadow. This is fewer instructions than ORing shadows - // individually. - IRBuilder<> IRB(Pos); - Value *WideAddr = - IRB.CreateBitCast(ShadowAddr, Type::getInt64PtrTy(*DFS.Ctx)); - Value *CombinedWideShadow = - IRB.CreateAlignedLoad(IRB.getInt64Ty(), WideAddr, ShadowAlign); - for (uint64_t Ofs = 64 / DFS.ShadowWidthBits; Ofs != Size; - Ofs += 64 / DFS.ShadowWidthBits) { - WideAddr = IRB.CreateGEP(Type::getInt64Ty(*DFS.Ctx), WideAddr, - ConstantInt::get(DFS.IntptrTy, 1)); - Value *NextWideShadow = - IRB.CreateAlignedLoad(IRB.getInt64Ty(), WideAddr, ShadowAlign); - CombinedWideShadow = IRB.CreateOr(CombinedWideShadow, NextWideShadow); - } - for (unsigned Width = 32; Width >= DFS.ShadowWidthBits; Width >>= 1) { - Value *ShrShadow = IRB.CreateLShr(CombinedWideShadow, Width); - CombinedWideShadow = IRB.CreateOr(CombinedWideShadow, ShrShadow); - } - return IRB.CreateTrunc(CombinedWideShadow, DFS.PrimitiveShadowTy); - } - if (!AvoidNewBlocks && Size % (64 / DFS.ShadowWidthBits) == 0) { - // Fast path for the common case where each byte has identical shadow: load - // shadow 64 bits at a time, fall out to a __dfsan_union_load call if any - // shadow is non-equal. - BasicBlock *FallbackBB = BasicBlock::Create(*DFS.Ctx, "", F); - IRBuilder<> FallbackIRB(FallbackBB); - CallInst *FallbackCall = FallbackIRB.CreateCall( - DFS.DFSanUnionLoadFn, - {ShadowAddr, ConstantInt::get(DFS.IntptrTy, Size)}); - FallbackCall->addAttribute(AttributeList::ReturnIndex, Attribute::ZExt); - - // Compare each of the shadows stored in the loaded 64 bits to each other, - // by computing (WideShadow rotl ShadowWidthBits) == WideShadow. - IRBuilder<> IRB(Pos); - Value *WideAddr = - IRB.CreateBitCast(ShadowAddr, Type::getInt64PtrTy(*DFS.Ctx)); - Value *WideShadow = - IRB.CreateAlignedLoad(IRB.getInt64Ty(), WideAddr, ShadowAlign); - Value *TruncShadow = IRB.CreateTrunc(WideShadow, DFS.PrimitiveShadowTy); - Value *ShlShadow = IRB.CreateShl(WideShadow, DFS.ShadowWidthBits); - Value *ShrShadow = IRB.CreateLShr(WideShadow, 64 - DFS.ShadowWidthBits); - Value *RotShadow = IRB.CreateOr(ShlShadow, ShrShadow); - Value *ShadowsEq = IRB.CreateICmpEQ(WideShadow, RotShadow); - - BasicBlock *Head = Pos->getParent(); - BasicBlock *Tail = Head->splitBasicBlock(Pos->getIterator()); - - if (DomTreeNode *OldNode = DT.getNode(Head)) { - std::vector<DomTreeNode *> Children(OldNode->begin(), OldNode->end()); - - DomTreeNode *NewNode = DT.addNewBlock(Tail, Head); - for (auto Child : Children) - DT.changeImmediateDominator(Child, NewNode); - } + if (HasSizeForFastPath) + return loadShadowFast(ShadowAddr, OriginAddr, Size, ShadowAlign, + OriginAlign, Origin, Pos); - // In the following code LastBr will refer to the previous basic block's - // conditional branch instruction, whose true successor is fixed up to point - // to the next block during the loop below or to the tail after the final - // iteration. - BranchInst *LastBr = BranchInst::Create(FallbackBB, FallbackBB, ShadowsEq); - ReplaceInstWithInst(Head->getTerminator(), LastBr); - DT.addNewBlock(FallbackBB, Head); + IRBuilder<> IRB(Pos); + CallInst *FallbackCall = IRB.CreateCall( + DFS.DFSanUnionLoadFn, {ShadowAddr, ConstantInt::get(DFS.IntptrTy, Size)}); + FallbackCall->addAttribute(AttributeList::ReturnIndex, Attribute::ZExt); + return {FallbackCall, Origin}; +} - for (uint64_t Ofs = 64 / DFS.ShadowWidthBits; Ofs != Size; - Ofs += 64 / DFS.ShadowWidthBits) { - BasicBlock *NextBB = BasicBlock::Create(*DFS.Ctx, "", F); - DT.addNewBlock(NextBB, LastBr->getParent()); - IRBuilder<> NextIRB(NextBB); - WideAddr = NextIRB.CreateGEP(Type::getInt64Ty(*DFS.Ctx), WideAddr, - ConstantInt::get(DFS.IntptrTy, 1)); - Value *NextWideShadow = NextIRB.CreateAlignedLoad(NextIRB.getInt64Ty(), - WideAddr, ShadowAlign); - ShadowsEq = NextIRB.CreateICmpEQ(WideShadow, NextWideShadow); - LastBr->setSuccessor(0, NextBB); - LastBr = NextIRB.CreateCondBr(ShadowsEq, FallbackBB, FallbackBB); +std::pair<Value *, Value *> DFSanFunction::loadShadowOrigin(Value *Addr, + uint64_t Size, + Align InstAlignment, + Instruction *Pos) { + Value *PrimitiveShadow, *Origin; + std::tie(PrimitiveShadow, Origin) = + loadShadowOriginSansLoadTracking(Addr, Size, InstAlignment, Pos); + if (DFS.shouldTrackOrigins()) { + if (ClTrackOrigins == 2) { + IRBuilder<> IRB(Pos); + auto *ConstantShadow = dyn_cast<Constant>(PrimitiveShadow); + if (!ConstantShadow || !ConstantShadow->isZeroValue()) + Origin = updateOriginIfTainted(PrimitiveShadow, Origin, IRB); } - - LastBr->setSuccessor(0, Tail); - FallbackIRB.CreateBr(Tail); - PHINode *Shadow = - PHINode::Create(DFS.PrimitiveShadowTy, 2, "", &Tail->front()); - Shadow->addIncoming(FallbackCall, FallbackBB); - Shadow->addIncoming(TruncShadow, LastBr->getParent()); - return Shadow; } + return {PrimitiveShadow, Origin}; +} - IRBuilder<> IRB(Pos); - FunctionCallee &UnionLoadFn = - ClFast16Labels ? DFS.DFSanUnionLoadFast16LabelsFn : DFS.DFSanUnionLoadFn; - CallInst *FallbackCall = IRB.CreateCall( - UnionLoadFn, {ShadowAddr, ConstantInt::get(DFS.IntptrTy, Size)}); - FallbackCall->addAttribute(AttributeList::ReturnIndex, Attribute::ZExt); - return FallbackCall; +static AtomicOrdering addAcquireOrdering(AtomicOrdering AO) { + switch (AO) { + case AtomicOrdering::NotAtomic: + return AtomicOrdering::NotAtomic; + case AtomicOrdering::Unordered: + case AtomicOrdering::Monotonic: + case AtomicOrdering::Acquire: + return AtomicOrdering::Acquire; + case AtomicOrdering::Release: + case AtomicOrdering::AcquireRelease: + return AtomicOrdering::AcquireRelease; + case AtomicOrdering::SequentiallyConsistent: + return AtomicOrdering::SequentiallyConsistent; + } + llvm_unreachable("Unknown ordering"); } void DFSanVisitor::visitLoadInst(LoadInst &LI) { @@ -1667,65 +2215,218 @@ void DFSanVisitor::visitLoadInst(LoadInst &LI) { uint64_t Size = DL.getTypeStoreSize(LI.getType()); if (Size == 0) { DFSF.setShadow(&LI, DFSF.DFS.getZeroShadow(&LI)); + DFSF.setOrigin(&LI, DFSF.DFS.ZeroOrigin); return; } - Align Alignment = ClPreserveAlignment ? LI.getAlign() : Align(1); - Value *PrimitiveShadow = - DFSF.loadShadow(LI.getPointerOperand(), Size, Alignment.value(), &LI); + // When an application load is atomic, increase atomic ordering between + // atomic application loads and stores to ensure happen-before order; load + // shadow data after application data; store zero shadow data before + // application data. This ensure shadow loads return either labels of the + // initial application data or zeros. + if (LI.isAtomic()) + LI.setOrdering(addAcquireOrdering(LI.getOrdering())); + + Instruction *Pos = LI.isAtomic() ? LI.getNextNode() : &LI; + std::vector<Value *> Shadows; + std::vector<Value *> Origins; + Value *PrimitiveShadow, *Origin; + std::tie(PrimitiveShadow, Origin) = + DFSF.loadShadowOrigin(LI.getPointerOperand(), Size, LI.getAlign(), Pos); + const bool ShouldTrackOrigins = DFSF.DFS.shouldTrackOrigins(); + if (ShouldTrackOrigins) { + Shadows.push_back(PrimitiveShadow); + Origins.push_back(Origin); + } if (ClCombinePointerLabelsOnLoad) { Value *PtrShadow = DFSF.getShadow(LI.getPointerOperand()); - PrimitiveShadow = DFSF.combineShadows(PrimitiveShadow, PtrShadow, &LI); + PrimitiveShadow = DFSF.combineShadows(PrimitiveShadow, PtrShadow, Pos); + if (ShouldTrackOrigins) { + Shadows.push_back(PtrShadow); + Origins.push_back(DFSF.getOrigin(LI.getPointerOperand())); + } } if (!DFSF.DFS.isZeroShadow(PrimitiveShadow)) DFSF.NonZeroChecks.push_back(PrimitiveShadow); Value *Shadow = - DFSF.expandFromPrimitiveShadow(LI.getType(), PrimitiveShadow, &LI); + DFSF.expandFromPrimitiveShadow(LI.getType(), PrimitiveShadow, Pos); DFSF.setShadow(&LI, Shadow); + + if (ShouldTrackOrigins) { + DFSF.setOrigin(&LI, DFSF.combineOrigins(Shadows, Origins, Pos)); + } + if (ClEventCallbacks) { - IRBuilder<> IRB(&LI); + IRBuilder<> IRB(Pos); Value *Addr8 = IRB.CreateBitCast(LI.getPointerOperand(), DFSF.DFS.Int8Ptr); IRB.CreateCall(DFSF.DFS.DFSanLoadCallbackFn, {PrimitiveShadow, Addr8}); } } -void DFSanFunction::storePrimitiveShadow(Value *Addr, uint64_t Size, - Align Alignment, - Value *PrimitiveShadow, - Instruction *Pos) { +Value *DFSanFunction::updateOriginIfTainted(Value *Shadow, Value *Origin, + IRBuilder<> &IRB) { + assert(DFS.shouldTrackOrigins()); + return IRB.CreateCall(DFS.DFSanChainOriginIfTaintedFn, {Shadow, Origin}); +} + +Value *DFSanFunction::updateOrigin(Value *V, IRBuilder<> &IRB) { + if (!DFS.shouldTrackOrigins()) + return V; + return IRB.CreateCall(DFS.DFSanChainOriginFn, V); +} + +Value *DFSanFunction::originToIntptr(IRBuilder<> &IRB, Value *Origin) { + const unsigned OriginSize = DataFlowSanitizer::OriginWidthBytes; + const DataLayout &DL = F->getParent()->getDataLayout(); + unsigned IntptrSize = DL.getTypeStoreSize(DFS.IntptrTy); + if (IntptrSize == OriginSize) + return Origin; + assert(IntptrSize == OriginSize * 2); + Origin = IRB.CreateIntCast(Origin, DFS.IntptrTy, /* isSigned */ false); + return IRB.CreateOr(Origin, IRB.CreateShl(Origin, OriginSize * 8)); +} + +void DFSanFunction::paintOrigin(IRBuilder<> &IRB, Value *Origin, + Value *StoreOriginAddr, + uint64_t StoreOriginSize, Align Alignment) { + const unsigned OriginSize = DataFlowSanitizer::OriginWidthBytes; + const DataLayout &DL = F->getParent()->getDataLayout(); + const Align IntptrAlignment = DL.getABITypeAlign(DFS.IntptrTy); + unsigned IntptrSize = DL.getTypeStoreSize(DFS.IntptrTy); + assert(IntptrAlignment >= MinOriginAlignment); + assert(IntptrSize >= OriginSize); + + unsigned Ofs = 0; + Align CurrentAlignment = Alignment; + if (Alignment >= IntptrAlignment && IntptrSize > OriginSize) { + Value *IntptrOrigin = originToIntptr(IRB, Origin); + Value *IntptrStoreOriginPtr = IRB.CreatePointerCast( + StoreOriginAddr, PointerType::get(DFS.IntptrTy, 0)); + for (unsigned I = 0; I < StoreOriginSize / IntptrSize; ++I) { + Value *Ptr = + I ? IRB.CreateConstGEP1_32(DFS.IntptrTy, IntptrStoreOriginPtr, I) + : IntptrStoreOriginPtr; + IRB.CreateAlignedStore(IntptrOrigin, Ptr, CurrentAlignment); + Ofs += IntptrSize / OriginSize; + CurrentAlignment = IntptrAlignment; + } + } + + for (unsigned I = Ofs; I < (StoreOriginSize + OriginSize - 1) / OriginSize; + ++I) { + Value *GEP = I ? IRB.CreateConstGEP1_32(DFS.OriginTy, StoreOriginAddr, I) + : StoreOriginAddr; + IRB.CreateAlignedStore(Origin, GEP, CurrentAlignment); + CurrentAlignment = MinOriginAlignment; + } +} + +Value *DFSanFunction::convertToBool(Value *V, IRBuilder<> &IRB, + const Twine &Name) { + Type *VTy = V->getType(); + assert(VTy->isIntegerTy()); + if (VTy->getIntegerBitWidth() == 1) + // Just converting a bool to a bool, so do nothing. + return V; + return IRB.CreateICmpNE(V, ConstantInt::get(VTy, 0), Name); +} + +void DFSanFunction::storeOrigin(Instruction *Pos, Value *Addr, uint64_t Size, + Value *Shadow, Value *Origin, + Value *StoreOriginAddr, Align InstAlignment) { + // Do not write origins for zero shadows because we do not trace origins for + // untainted sinks. + const Align OriginAlignment = getOriginAlign(InstAlignment); + Value *CollapsedShadow = collapseToPrimitiveShadow(Shadow, Pos); + IRBuilder<> IRB(Pos); + if (auto *ConstantShadow = dyn_cast<Constant>(CollapsedShadow)) { + if (!ConstantShadow->isZeroValue()) + paintOrigin(IRB, updateOrigin(Origin, IRB), StoreOriginAddr, Size, + OriginAlignment); + return; + } + + if (shouldInstrumentWithCall()) { + IRB.CreateCall(DFS.DFSanMaybeStoreOriginFn, + {CollapsedShadow, + IRB.CreatePointerCast(Addr, IRB.getInt8PtrTy()), + ConstantInt::get(DFS.IntptrTy, Size), Origin}); + } else { + Value *Cmp = convertToBool(CollapsedShadow, IRB, "_dfscmp"); + Instruction *CheckTerm = SplitBlockAndInsertIfThen( + Cmp, &*IRB.GetInsertPoint(), false, DFS.OriginStoreWeights, &DT); + IRBuilder<> IRBNew(CheckTerm); + paintOrigin(IRBNew, updateOrigin(Origin, IRBNew), StoreOriginAddr, Size, + OriginAlignment); + ++NumOriginStores; + } +} + +void DFSanFunction::storeZeroPrimitiveShadow(Value *Addr, uint64_t Size, + Align ShadowAlign, + Instruction *Pos) { + IRBuilder<> IRB(Pos); + IntegerType *ShadowTy = + IntegerType::get(*DFS.Ctx, Size * DFS.ShadowWidthBits); + Value *ExtZeroShadow = ConstantInt::get(ShadowTy, 0); + Value *ShadowAddr = DFS.getShadowAddress(Addr, Pos); + Value *ExtShadowAddr = + IRB.CreateBitCast(ShadowAddr, PointerType::getUnqual(ShadowTy)); + IRB.CreateAlignedStore(ExtZeroShadow, ExtShadowAddr, ShadowAlign); + // Do not write origins for 0 shadows because we do not trace origins for + // untainted sinks. +} + +void DFSanFunction::storePrimitiveShadowOrigin(Value *Addr, uint64_t Size, + Align InstAlignment, + Value *PrimitiveShadow, + Value *Origin, + Instruction *Pos) { + const bool ShouldTrackOrigins = DFS.shouldTrackOrigins() && Origin; + if (AllocaInst *AI = dyn_cast<AllocaInst>(Addr)) { - const auto i = AllocaShadowMap.find(AI); - if (i != AllocaShadowMap.end()) { + const auto SI = AllocaShadowMap.find(AI); + if (SI != AllocaShadowMap.end()) { IRBuilder<> IRB(Pos); - IRB.CreateStore(PrimitiveShadow, i->second); + IRB.CreateStore(PrimitiveShadow, SI->second); + + // Do not write origins for 0 shadows because we do not trace origins for + // untainted sinks. + if (ShouldTrackOrigins && !DFS.isZeroShadow(PrimitiveShadow)) { + const auto OI = AllocaOriginMap.find(AI); + assert(OI != AllocaOriginMap.end() && Origin); + IRB.CreateStore(Origin, OI->second); + } return; } } - const Align ShadowAlign(Alignment.value() * DFS.ShadowWidthBytes); - IRBuilder<> IRB(Pos); - Value *ShadowAddr = DFS.getShadowAddress(Addr, Pos); + const Align ShadowAlign = getShadowAlign(InstAlignment); if (DFS.isZeroShadow(PrimitiveShadow)) { - IntegerType *ShadowTy = - IntegerType::get(*DFS.Ctx, Size * DFS.ShadowWidthBits); - Value *ExtZeroShadow = ConstantInt::get(ShadowTy, 0); - Value *ExtShadowAddr = - IRB.CreateBitCast(ShadowAddr, PointerType::getUnqual(ShadowTy)); - IRB.CreateAlignedStore(ExtZeroShadow, ExtShadowAddr, ShadowAlign); + storeZeroPrimitiveShadow(Addr, Size, ShadowAlign, Pos); return; } - const unsigned ShadowVecSize = 128 / DFS.ShadowWidthBits; + IRBuilder<> IRB(Pos); + Value *ShadowAddr, *OriginAddr; + std::tie(ShadowAddr, OriginAddr) = + DFS.getShadowOriginAddress(Addr, InstAlignment, Pos); + + const unsigned ShadowVecSize = 8; + assert(ShadowVecSize * DFS.ShadowWidthBits <= 128 && + "Shadow vector is too large!"); + uint64_t Offset = 0; - if (Size >= ShadowVecSize) { + uint64_t LeftSize = Size; + if (LeftSize >= ShadowVecSize) { auto *ShadowVecTy = FixedVectorType::get(DFS.PrimitiveShadowTy, ShadowVecSize); Value *ShadowVec = UndefValue::get(ShadowVecTy); - for (unsigned i = 0; i != ShadowVecSize; ++i) { + for (unsigned I = 0; I != ShadowVecSize; ++I) { ShadowVec = IRB.CreateInsertElement( ShadowVec, PrimitiveShadow, - ConstantInt::get(Type::getInt32Ty(*DFS.Ctx), i)); + ConstantInt::get(Type::getInt32Ty(*DFS.Ctx), I)); } Value *ShadowVecAddr = IRB.CreateBitCast(ShadowAddr, PointerType::getUnqual(ShadowVecTy)); @@ -1733,38 +2434,86 @@ void DFSanFunction::storePrimitiveShadow(Value *Addr, uint64_t Size, Value *CurShadowVecAddr = IRB.CreateConstGEP1_32(ShadowVecTy, ShadowVecAddr, Offset); IRB.CreateAlignedStore(ShadowVec, CurShadowVecAddr, ShadowAlign); - Size -= ShadowVecSize; + LeftSize -= ShadowVecSize; ++Offset; - } while (Size >= ShadowVecSize); + } while (LeftSize >= ShadowVecSize); Offset *= ShadowVecSize; } - while (Size > 0) { + while (LeftSize > 0) { Value *CurShadowAddr = IRB.CreateConstGEP1_32(DFS.PrimitiveShadowTy, ShadowAddr, Offset); IRB.CreateAlignedStore(PrimitiveShadow, CurShadowAddr, ShadowAlign); - --Size; + --LeftSize; ++Offset; } + + if (ShouldTrackOrigins) { + storeOrigin(Pos, Addr, Size, PrimitiveShadow, Origin, OriginAddr, + InstAlignment); + } +} + +static AtomicOrdering addReleaseOrdering(AtomicOrdering AO) { + switch (AO) { + case AtomicOrdering::NotAtomic: + return AtomicOrdering::NotAtomic; + case AtomicOrdering::Unordered: + case AtomicOrdering::Monotonic: + case AtomicOrdering::Release: + return AtomicOrdering::Release; + case AtomicOrdering::Acquire: + case AtomicOrdering::AcquireRelease: + return AtomicOrdering::AcquireRelease; + case AtomicOrdering::SequentiallyConsistent: + return AtomicOrdering::SequentiallyConsistent; + } + llvm_unreachable("Unknown ordering"); } void DFSanVisitor::visitStoreInst(StoreInst &SI) { auto &DL = SI.getModule()->getDataLayout(); - uint64_t Size = DL.getTypeStoreSize(SI.getValueOperand()->getType()); + Value *Val = SI.getValueOperand(); + uint64_t Size = DL.getTypeStoreSize(Val->getType()); if (Size == 0) return; - const Align Alignment = ClPreserveAlignment ? SI.getAlign() : Align(1); + // When an application store is atomic, increase atomic ordering between + // atomic application loads and stores to ensure happen-before order; load + // shadow data after application data; store zero shadow data before + // application data. This ensure shadow loads return either labels of the + // initial application data or zeros. + if (SI.isAtomic()) + SI.setOrdering(addReleaseOrdering(SI.getOrdering())); + + const bool ShouldTrackOrigins = + DFSF.DFS.shouldTrackOrigins() && !SI.isAtomic(); + std::vector<Value *> Shadows; + std::vector<Value *> Origins; + + Value *Shadow = + SI.isAtomic() ? DFSF.DFS.getZeroShadow(Val) : DFSF.getShadow(Val); + + if (ShouldTrackOrigins) { + Shadows.push_back(Shadow); + Origins.push_back(DFSF.getOrigin(Val)); + } - Value* Shadow = DFSF.getShadow(SI.getValueOperand()); Value *PrimitiveShadow; if (ClCombinePointerLabelsOnStore) { Value *PtrShadow = DFSF.getShadow(SI.getPointerOperand()); + if (ShouldTrackOrigins) { + Shadows.push_back(PtrShadow); + Origins.push_back(DFSF.getOrigin(SI.getPointerOperand())); + } PrimitiveShadow = DFSF.combineShadows(Shadow, PtrShadow, &SI); } else { PrimitiveShadow = DFSF.collapseToPrimitiveShadow(Shadow, &SI); } - DFSF.storePrimitiveShadow(SI.getPointerOperand(), Size, Alignment, - PrimitiveShadow, &SI); + Value *Origin = nullptr; + if (ShouldTrackOrigins) + Origin = DFSF.combineOrigins(Shadows, Origins, &SI); + DFSF.storePrimitiveShadowOrigin(SI.getPointerOperand(), Size, SI.getAlign(), + PrimitiveShadow, Origin, &SI); if (ClEventCallbacks) { IRBuilder<> IRB(&SI); Value *Addr8 = IRB.CreateBitCast(SI.getPointerOperand(), DFSF.DFS.Int8Ptr); @@ -1772,43 +2521,116 @@ void DFSanVisitor::visitStoreInst(StoreInst &SI) { } } +void DFSanVisitor::visitCASOrRMW(Align InstAlignment, Instruction &I) { + assert(isa<AtomicRMWInst>(I) || isa<AtomicCmpXchgInst>(I)); + + Value *Val = I.getOperand(1); + const auto &DL = I.getModule()->getDataLayout(); + uint64_t Size = DL.getTypeStoreSize(Val->getType()); + if (Size == 0) + return; + + // Conservatively set data at stored addresses and return with zero shadow to + // prevent shadow data races. + IRBuilder<> IRB(&I); + Value *Addr = I.getOperand(0); + const Align ShadowAlign = DFSF.getShadowAlign(InstAlignment); + DFSF.storeZeroPrimitiveShadow(Addr, Size, ShadowAlign, &I); + DFSF.setShadow(&I, DFSF.DFS.getZeroShadow(&I)); + DFSF.setOrigin(&I, DFSF.DFS.ZeroOrigin); +} + +void DFSanVisitor::visitAtomicRMWInst(AtomicRMWInst &I) { + visitCASOrRMW(I.getAlign(), I); + // TODO: The ordering change follows MSan. It is possible not to change + // ordering because we always set and use 0 shadows. + I.setOrdering(addReleaseOrdering(I.getOrdering())); +} + +void DFSanVisitor::visitAtomicCmpXchgInst(AtomicCmpXchgInst &I) { + visitCASOrRMW(I.getAlign(), I); + // TODO: The ordering change follows MSan. It is possible not to change + // ordering because we always set and use 0 shadows. + I.setSuccessOrdering(addReleaseOrdering(I.getSuccessOrdering())); +} + void DFSanVisitor::visitUnaryOperator(UnaryOperator &UO) { - visitOperandShadowInst(UO); + visitInstOperands(UO); } void DFSanVisitor::visitBinaryOperator(BinaryOperator &BO) { - visitOperandShadowInst(BO); + visitInstOperands(BO); +} + +void DFSanVisitor::visitBitCastInst(BitCastInst &BCI) { + if (DFSF.DFS.getInstrumentedABI() == DataFlowSanitizer::IA_TLS) { + // Special case: if this is the bitcast (there is exactly 1 allowed) between + // a musttail call and a ret, don't instrument. New instructions are not + // allowed after a musttail call. + if (auto *CI = dyn_cast<CallInst>(BCI.getOperand(0))) + if (CI->isMustTailCall()) + return; + } + // TODO: handle musttail call returns for IA_Args. + visitInstOperands(BCI); } -void DFSanVisitor::visitCastInst(CastInst &CI) { visitOperandShadowInst(CI); } +void DFSanVisitor::visitCastInst(CastInst &CI) { visitInstOperands(CI); } void DFSanVisitor::visitCmpInst(CmpInst &CI) { - Value *CombinedShadow = visitOperandShadowInst(CI); + visitInstOperands(CI); if (ClEventCallbacks) { IRBuilder<> IRB(&CI); + Value *CombinedShadow = DFSF.getShadow(&CI); IRB.CreateCall(DFSF.DFS.DFSanCmpCallbackFn, CombinedShadow); } } +void DFSanVisitor::visitLandingPadInst(LandingPadInst &LPI) { + // We do not need to track data through LandingPadInst. + // + // For the C++ exceptions, if a value is thrown, this value will be stored + // in a memory location provided by __cxa_allocate_exception(...) (on the + // throw side) or __cxa_begin_catch(...) (on the catch side). + // This memory will have a shadow, so with the loads and stores we will be + // able to propagate labels on data thrown through exceptions, without any + // special handling of the LandingPadInst. + // + // The second element in the pair result of the LandingPadInst is a + // register value, but it is for a type ID and should never be tainted. + DFSF.setShadow(&LPI, DFSF.DFS.getZeroShadow(&LPI)); + DFSF.setOrigin(&LPI, DFSF.DFS.ZeroOrigin); +} + void DFSanVisitor::visitGetElementPtrInst(GetElementPtrInst &GEPI) { - visitOperandShadowInst(GEPI); + if (ClCombineOffsetLabelsOnGEP) { + visitInstOperands(GEPI); + return; + } + + // Only propagate shadow/origin of base pointer value but ignore those of + // offset operands. + Value *BasePointer = GEPI.getPointerOperand(); + DFSF.setShadow(&GEPI, DFSF.getShadow(BasePointer)); + if (DFSF.DFS.shouldTrackOrigins()) + DFSF.setOrigin(&GEPI, DFSF.getOrigin(BasePointer)); } void DFSanVisitor::visitExtractElementInst(ExtractElementInst &I) { - visitOperandShadowInst(I); + visitInstOperands(I); } void DFSanVisitor::visitInsertElementInst(InsertElementInst &I) { - visitOperandShadowInst(I); + visitInstOperands(I); } void DFSanVisitor::visitShuffleVectorInst(ShuffleVectorInst &I) { - visitOperandShadowInst(I); + visitInstOperands(I); } void DFSanVisitor::visitExtractValueInst(ExtractValueInst &I) { if (!DFSF.DFS.shouldTrackFieldsAndIndices()) { - visitOperandShadowInst(I); + visitInstOperands(I); return; } @@ -1817,11 +2639,12 @@ void DFSanVisitor::visitExtractValueInst(ExtractValueInst &I) { Value *AggShadow = DFSF.getShadow(Agg); Value *ResShadow = IRB.CreateExtractValue(AggShadow, I.getIndices()); DFSF.setShadow(&I, ResShadow); + visitInstOperandOrigins(I); } void DFSanVisitor::visitInsertValueInst(InsertValueInst &I) { if (!DFSF.DFS.shouldTrackFieldsAndIndices()) { - visitOperandShadowInst(I); + visitInstOperands(I); return; } @@ -1830,6 +2653,7 @@ void DFSanVisitor::visitInsertValueInst(InsertValueInst &I) { Value *InsShadow = DFSF.getShadow(I.getInsertedValueOperand()); Value *Res = IRB.CreateInsertValue(AggShadow, InsShadow, I.getIndices()); DFSF.setShadow(&I, Res); + visitInstOperandOrigins(I); } void DFSanVisitor::visitAllocaInst(AllocaInst &I) { @@ -1849,8 +2673,13 @@ void DFSanVisitor::visitAllocaInst(AllocaInst &I) { if (AllLoadsStores) { IRBuilder<> IRB(&I); DFSF.AllocaShadowMap[&I] = IRB.CreateAlloca(DFSF.DFS.PrimitiveShadowTy); + if (DFSF.DFS.shouldTrackOrigins()) { + DFSF.AllocaOriginMap[&I] = + IRB.CreateAlloca(DFSF.DFS.OriginTy, nullptr, "_dfsa"); + } } DFSF.setShadow(&I, DFSF.DFS.ZeroPrimitiveShadow); + DFSF.setOrigin(&I, DFSF.DFS.ZeroOrigin); } void DFSanVisitor::visitSelectInst(SelectInst &I) { @@ -1858,35 +2687,79 @@ void DFSanVisitor::visitSelectInst(SelectInst &I) { Value *TrueShadow = DFSF.getShadow(I.getTrueValue()); Value *FalseShadow = DFSF.getShadow(I.getFalseValue()); Value *ShadowSel = nullptr; + const bool ShouldTrackOrigins = DFSF.DFS.shouldTrackOrigins(); + std::vector<Value *> Shadows; + std::vector<Value *> Origins; + Value *TrueOrigin = + ShouldTrackOrigins ? DFSF.getOrigin(I.getTrueValue()) : nullptr; + Value *FalseOrigin = + ShouldTrackOrigins ? DFSF.getOrigin(I.getFalseValue()) : nullptr; if (isa<VectorType>(I.getCondition()->getType())) { ShadowSel = DFSF.combineShadowsThenConvert(I.getType(), TrueShadow, FalseShadow, &I); + if (ShouldTrackOrigins) { + Shadows.push_back(TrueShadow); + Shadows.push_back(FalseShadow); + Origins.push_back(TrueOrigin); + Origins.push_back(FalseOrigin); + } } else { if (TrueShadow == FalseShadow) { ShadowSel = TrueShadow; + if (ShouldTrackOrigins) { + Shadows.push_back(TrueShadow); + Origins.push_back(TrueOrigin); + } } else { ShadowSel = SelectInst::Create(I.getCondition(), TrueShadow, FalseShadow, "", &I); + if (ShouldTrackOrigins) { + Shadows.push_back(ShadowSel); + Origins.push_back(SelectInst::Create(I.getCondition(), TrueOrigin, + FalseOrigin, "", &I)); + } } } DFSF.setShadow(&I, ClTrackSelectControlFlow ? DFSF.combineShadowsThenConvert( I.getType(), CondShadow, ShadowSel, &I) : ShadowSel); + if (ShouldTrackOrigins) { + if (ClTrackSelectControlFlow) { + Shadows.push_back(CondShadow); + Origins.push_back(DFSF.getOrigin(I.getCondition())); + } + DFSF.setOrigin(&I, DFSF.combineOrigins(Shadows, Origins, &I)); + } } void DFSanVisitor::visitMemSetInst(MemSetInst &I) { IRBuilder<> IRB(&I); Value *ValShadow = DFSF.getShadow(I.getValue()); - IRB.CreateCall(DFSF.DFS.DFSanSetLabelFn, - {ValShadow, IRB.CreateBitCast(I.getDest(), Type::getInt8PtrTy( - *DFSF.DFS.Ctx)), - IRB.CreateZExtOrTrunc(I.getLength(), DFSF.DFS.IntptrTy)}); + Value *ValOrigin = DFSF.DFS.shouldTrackOrigins() + ? DFSF.getOrigin(I.getValue()) + : DFSF.DFS.ZeroOrigin; + IRB.CreateCall( + DFSF.DFS.DFSanSetLabelFn, + {ValShadow, ValOrigin, + IRB.CreateBitCast(I.getDest(), Type::getInt8PtrTy(*DFSF.DFS.Ctx)), + IRB.CreateZExtOrTrunc(I.getLength(), DFSF.DFS.IntptrTy)}); } void DFSanVisitor::visitMemTransferInst(MemTransferInst &I) { IRBuilder<> IRB(&I); + + // CopyOrMoveOrigin transfers origins by refering to their shadows. So we + // need to move origins before moving shadows. + if (DFSF.DFS.shouldTrackOrigins()) { + IRB.CreateCall( + DFSF.DFS.DFSanMemOriginTransferFn, + {IRB.CreatePointerCast(I.getArgOperand(0), IRB.getInt8PtrTy()), + IRB.CreatePointerCast(I.getArgOperand(1), IRB.getInt8PtrTy()), + IRB.CreateIntCast(I.getArgOperand(2), DFSF.DFS.IntptrTy, false)}); + } + Value *RawDestShadow = DFSF.DFS.getShadowAddress(I.getDest(), &I); Value *SrcShadow = DFSF.DFS.getShadowAddress(I.getSource(), &I); Value *LenShadow = @@ -1907,28 +2780,50 @@ void DFSanVisitor::visitMemTransferInst(MemTransferInst &I) { } if (ClEventCallbacks) { IRB.CreateCall(DFSF.DFS.DFSanMemTransferCallbackFn, - {RawDestShadow, I.getLength()}); + {RawDestShadow, + IRB.CreateZExtOrTrunc(I.getLength(), DFSF.DFS.IntptrTy)}); } } +static bool isAMustTailRetVal(Value *RetVal) { + // Tail call may have a bitcast between return. + if (auto *I = dyn_cast<BitCastInst>(RetVal)) { + RetVal = I->getOperand(0); + } + if (auto *I = dyn_cast<CallInst>(RetVal)) { + return I->isMustTailCall(); + } + return false; +} + void DFSanVisitor::visitReturnInst(ReturnInst &RI) { if (!DFSF.IsNativeABI && RI.getReturnValue()) { switch (DFSF.IA) { case DataFlowSanitizer::IA_TLS: { + // Don't emit the instrumentation for musttail call returns. + if (isAMustTailRetVal(RI.getReturnValue())) + return; + Value *S = DFSF.getShadow(RI.getReturnValue()); IRBuilder<> IRB(&RI); Type *RT = DFSF.F->getFunctionType()->getReturnType(); unsigned Size = getDataLayout().getTypeAllocSize(DFSF.DFS.getShadowTy(RT)); - if (Size <= kRetvalTLSSize) { + if (Size <= RetvalTLSSize) { // If the size overflows, stores nothing. At callsite, oversized return // shadows are set to zero. IRB.CreateAlignedStore(S, DFSF.getRetvalTLS(RT, IRB), - kShadowTLSAlignment); + ShadowTLSAlignment); + } + if (DFSF.DFS.shouldTrackOrigins()) { + Value *O = DFSF.getOrigin(RI.getReturnValue()); + IRB.CreateStore(O, DFSF.getRetvalOriginTLS()); } break; } case DataFlowSanitizer::IA_Args: { + // TODO: handle musttail call returns for IA_Args. + IRBuilder<> IRB(&RI); Type *RT = DFSF.F->getFunctionType()->getReturnType(); Value *InsVal = @@ -1942,164 +2837,250 @@ void DFSanVisitor::visitReturnInst(ReturnInst &RI) { } } -void DFSanVisitor::visitCallBase(CallBase &CB) { - Function *F = CB.getCalledFunction(); - if ((F && F->isIntrinsic()) || CB.isInlineAsm()) { - visitOperandShadowInst(CB); - return; +void DFSanVisitor::addShadowArguments(Function &F, CallBase &CB, + std::vector<Value *> &Args, + IRBuilder<> &IRB) { + FunctionType *FT = F.getFunctionType(); + + auto *I = CB.arg_begin(); + + // Adds non-variable argument shadows. + for (unsigned N = FT->getNumParams(); N != 0; ++I, --N) + Args.push_back(DFSF.collapseToPrimitiveShadow(DFSF.getShadow(*I), &CB)); + + // Adds variable argument shadows. + if (FT->isVarArg()) { + auto *LabelVATy = ArrayType::get(DFSF.DFS.PrimitiveShadowTy, + CB.arg_size() - FT->getNumParams()); + auto *LabelVAAlloca = + new AllocaInst(LabelVATy, getDataLayout().getAllocaAddrSpace(), + "labelva", &DFSF.F->getEntryBlock().front()); + + for (unsigned N = 0; I != CB.arg_end(); ++I, ++N) { + auto *LabelVAPtr = IRB.CreateStructGEP(LabelVATy, LabelVAAlloca, N); + IRB.CreateStore(DFSF.collapseToPrimitiveShadow(DFSF.getShadow(*I), &CB), + LabelVAPtr); + } + + Args.push_back(IRB.CreateStructGEP(LabelVATy, LabelVAAlloca, 0)); } - // Calls to this function are synthesized in wrappers, and we shouldn't - // instrument them. - if (F == DFSF.DFS.DFSanVarargWrapperFn.getCallee()->stripPointerCasts()) - return; + // Adds the return value shadow. + if (!FT->getReturnType()->isVoidTy()) { + if (!DFSF.LabelReturnAlloca) { + DFSF.LabelReturnAlloca = new AllocaInst( + DFSF.DFS.PrimitiveShadowTy, getDataLayout().getAllocaAddrSpace(), + "labelreturn", &DFSF.F->getEntryBlock().front()); + } + Args.push_back(DFSF.LabelReturnAlloca); + } +} - IRBuilder<> IRB(&CB); +void DFSanVisitor::addOriginArguments(Function &F, CallBase &CB, + std::vector<Value *> &Args, + IRBuilder<> &IRB) { + FunctionType *FT = F.getFunctionType(); - DenseMap<Value *, Function *>::iterator i = - DFSF.DFS.UnwrappedFnMap.find(CB.getCalledOperand()); - if (i != DFSF.DFS.UnwrappedFnMap.end()) { - Function *F = i->second; - switch (DFSF.DFS.getWrapperKind(F)) { - case DataFlowSanitizer::WK_Warning: - CB.setCalledFunction(F); - IRB.CreateCall(DFSF.DFS.DFSanUnimplementedFn, - IRB.CreateGlobalStringPtr(F->getName())); - DFSF.setShadow(&CB, DFSF.DFS.getZeroShadow(&CB)); - return; - case DataFlowSanitizer::WK_Discard: - CB.setCalledFunction(F); - DFSF.setShadow(&CB, DFSF.DFS.getZeroShadow(&CB)); - return; - case DataFlowSanitizer::WK_Functional: - CB.setCalledFunction(F); - visitOperandShadowInst(CB); - return; - case DataFlowSanitizer::WK_Custom: - // Don't try to handle invokes of custom functions, it's too complicated. - // Instead, invoke the dfsw$ wrapper, which will in turn call the __dfsw_ - // wrapper. - if (CallInst *CI = dyn_cast<CallInst>(&CB)) { - FunctionType *FT = F->getFunctionType(); - TransformedFunction CustomFn = DFSF.DFS.getCustomFunctionType(FT); - std::string CustomFName = "__dfsw_"; - CustomFName += F->getName(); - FunctionCallee CustomF = DFSF.DFS.Mod->getOrInsertFunction( - CustomFName, CustomFn.TransformedType); - if (Function *CustomFn = dyn_cast<Function>(CustomF.getCallee())) { - CustomFn->copyAttributesFrom(F); + auto *I = CB.arg_begin(); - // Custom functions returning non-void will write to the return label. - if (!FT->getReturnType()->isVoidTy()) { - CustomFn->removeAttributes(AttributeList::FunctionIndex, - DFSF.DFS.ReadOnlyNoneAttrs); - } - } + // Add non-variable argument origins. + for (unsigned N = FT->getNumParams(); N != 0; ++I, --N) + Args.push_back(DFSF.getOrigin(*I)); - std::vector<Value *> Args; + // Add variable argument origins. + if (FT->isVarArg()) { + auto *OriginVATy = + ArrayType::get(DFSF.DFS.OriginTy, CB.arg_size() - FT->getNumParams()); + auto *OriginVAAlloca = + new AllocaInst(OriginVATy, getDataLayout().getAllocaAddrSpace(), + "originva", &DFSF.F->getEntryBlock().front()); - auto i = CB.arg_begin(); - for (unsigned n = FT->getNumParams(); n != 0; ++i, --n) { - Type *T = (*i)->getType(); - FunctionType *ParamFT; - if (isa<PointerType>(T) && - (ParamFT = dyn_cast<FunctionType>( - cast<PointerType>(T)->getElementType()))) { - std::string TName = "dfst"; - TName += utostr(FT->getNumParams() - n); - TName += "$"; - TName += F->getName(); - Constant *T = DFSF.DFS.getOrBuildTrampolineFunction(ParamFT, TName); - Args.push_back(T); - Args.push_back( - IRB.CreateBitCast(*i, Type::getInt8PtrTy(*DFSF.DFS.Ctx))); - } else { - Args.push_back(*i); - } - } + for (unsigned N = 0; I != CB.arg_end(); ++I, ++N) { + auto *OriginVAPtr = IRB.CreateStructGEP(OriginVATy, OriginVAAlloca, N); + IRB.CreateStore(DFSF.getOrigin(*I), OriginVAPtr); + } - i = CB.arg_begin(); - const unsigned ShadowArgStart = Args.size(); - for (unsigned n = FT->getNumParams(); n != 0; ++i, --n) - Args.push_back( - DFSF.collapseToPrimitiveShadow(DFSF.getShadow(*i), &CB)); + Args.push_back(IRB.CreateStructGEP(OriginVATy, OriginVAAlloca, 0)); + } - if (FT->isVarArg()) { - auto *LabelVATy = ArrayType::get(DFSF.DFS.PrimitiveShadowTy, - CB.arg_size() - FT->getNumParams()); - auto *LabelVAAlloca = new AllocaInst( - LabelVATy, getDataLayout().getAllocaAddrSpace(), - "labelva", &DFSF.F->getEntryBlock().front()); + // Add the return value origin. + if (!FT->getReturnType()->isVoidTy()) { + if (!DFSF.OriginReturnAlloca) { + DFSF.OriginReturnAlloca = new AllocaInst( + DFSF.DFS.OriginTy, getDataLayout().getAllocaAddrSpace(), + "originreturn", &DFSF.F->getEntryBlock().front()); + } + Args.push_back(DFSF.OriginReturnAlloca); + } +} - for (unsigned n = 0; i != CB.arg_end(); ++i, ++n) { - auto LabelVAPtr = IRB.CreateStructGEP(LabelVATy, LabelVAAlloca, n); - IRB.CreateStore( - DFSF.collapseToPrimitiveShadow(DFSF.getShadow(*i), &CB), - LabelVAPtr); - } +bool DFSanVisitor::visitWrappedCallBase(Function &F, CallBase &CB) { + IRBuilder<> IRB(&CB); + switch (DFSF.DFS.getWrapperKind(&F)) { + case DataFlowSanitizer::WK_Warning: + CB.setCalledFunction(&F); + IRB.CreateCall(DFSF.DFS.DFSanUnimplementedFn, + IRB.CreateGlobalStringPtr(F.getName())); + DFSF.setShadow(&CB, DFSF.DFS.getZeroShadow(&CB)); + DFSF.setOrigin(&CB, DFSF.DFS.ZeroOrigin); + return true; + case DataFlowSanitizer::WK_Discard: + CB.setCalledFunction(&F); + DFSF.setShadow(&CB, DFSF.DFS.getZeroShadow(&CB)); + DFSF.setOrigin(&CB, DFSF.DFS.ZeroOrigin); + return true; + case DataFlowSanitizer::WK_Functional: + CB.setCalledFunction(&F); + visitInstOperands(CB); + return true; + case DataFlowSanitizer::WK_Custom: + // Don't try to handle invokes of custom functions, it's too complicated. + // Instead, invoke the dfsw$ wrapper, which will in turn call the __dfsw_ + // wrapper. + CallInst *CI = dyn_cast<CallInst>(&CB); + if (!CI) + return false; - Args.push_back(IRB.CreateStructGEP(LabelVATy, LabelVAAlloca, 0)); - } + const bool ShouldTrackOrigins = DFSF.DFS.shouldTrackOrigins(); + FunctionType *FT = F.getFunctionType(); + TransformedFunction CustomFn = DFSF.DFS.getCustomFunctionType(FT); + std::string CustomFName = ShouldTrackOrigins ? "__dfso_" : "__dfsw_"; + CustomFName += F.getName(); + FunctionCallee CustomF = DFSF.DFS.Mod->getOrInsertFunction( + CustomFName, CustomFn.TransformedType); + if (Function *CustomFn = dyn_cast<Function>(CustomF.getCallee())) { + CustomFn->copyAttributesFrom(&F); - if (!FT->getReturnType()->isVoidTy()) { - if (!DFSF.LabelReturnAlloca) { - DFSF.LabelReturnAlloca = - new AllocaInst(DFSF.DFS.PrimitiveShadowTy, - getDataLayout().getAllocaAddrSpace(), - "labelreturn", &DFSF.F->getEntryBlock().front()); - } - Args.push_back(DFSF.LabelReturnAlloca); - } + // Custom functions returning non-void will write to the return label. + if (!FT->getReturnType()->isVoidTy()) { + CustomFn->removeAttributes(AttributeList::FunctionIndex, + DFSF.DFS.ReadOnlyNoneAttrs); + } + } - for (i = CB.arg_begin() + FT->getNumParams(); i != CB.arg_end(); ++i) - Args.push_back(*i); + std::vector<Value *> Args; - CallInst *CustomCI = IRB.CreateCall(CustomF, Args); - CustomCI->setCallingConv(CI->getCallingConv()); - CustomCI->setAttributes(TransformFunctionAttributes(CustomFn, - CI->getContext(), CI->getAttributes())); + // Adds non-variable arguments. + auto *I = CB.arg_begin(); + for (unsigned N = FT->getNumParams(); N != 0; ++I, --N) { + Type *T = (*I)->getType(); + FunctionType *ParamFT; + if (isa<PointerType>(T) && + (ParamFT = dyn_cast<FunctionType>(T->getPointerElementType()))) { + std::string TName = "dfst"; + TName += utostr(FT->getNumParams() - N); + TName += "$"; + TName += F.getName(); + Constant *Trampoline = + DFSF.DFS.getOrBuildTrampolineFunction(ParamFT, TName); + Args.push_back(Trampoline); + Args.push_back( + IRB.CreateBitCast(*I, Type::getInt8PtrTy(*DFSF.DFS.Ctx))); + } else { + Args.push_back(*I); + } + } - // Update the parameter attributes of the custom call instruction to - // zero extend the shadow parameters. This is required for targets - // which consider PrimitiveShadowTy an illegal type. - for (unsigned n = 0; n < FT->getNumParams(); n++) { - const unsigned ArgNo = ShadowArgStart + n; - if (CustomCI->getArgOperand(ArgNo)->getType() == - DFSF.DFS.PrimitiveShadowTy) - CustomCI->addParamAttr(ArgNo, Attribute::ZExt); - } + // Adds shadow arguments. + const unsigned ShadowArgStart = Args.size(); + addShadowArguments(F, CB, Args, IRB); - if (!FT->getReturnType()->isVoidTy()) { - LoadInst *LabelLoad = IRB.CreateLoad(DFSF.DFS.PrimitiveShadowTy, - DFSF.LabelReturnAlloca); - DFSF.setShadow(CustomCI, DFSF.expandFromPrimitiveShadow( - FT->getReturnType(), LabelLoad, &CB)); - } + // Adds origin arguments. + const unsigned OriginArgStart = Args.size(); + if (ShouldTrackOrigins) + addOriginArguments(F, CB, Args, IRB); - CI->replaceAllUsesWith(CustomCI); - CI->eraseFromParent(); - return; + // Adds variable arguments. + append_range(Args, drop_begin(CB.args(), FT->getNumParams())); + + CallInst *CustomCI = IRB.CreateCall(CustomF, Args); + CustomCI->setCallingConv(CI->getCallingConv()); + CustomCI->setAttributes(transformFunctionAttributes( + CustomFn, CI->getContext(), CI->getAttributes())); + + // Update the parameter attributes of the custom call instruction to + // zero extend the shadow parameters. This is required for targets + // which consider PrimitiveShadowTy an illegal type. + for (unsigned N = 0; N < FT->getNumParams(); N++) { + const unsigned ArgNo = ShadowArgStart + N; + if (CustomCI->getArgOperand(ArgNo)->getType() == + DFSF.DFS.PrimitiveShadowTy) + CustomCI->addParamAttr(ArgNo, Attribute::ZExt); + if (ShouldTrackOrigins) { + const unsigned OriginArgNo = OriginArgStart + N; + if (CustomCI->getArgOperand(OriginArgNo)->getType() == + DFSF.DFS.OriginTy) + CustomCI->addParamAttr(OriginArgNo, Attribute::ZExt); + } + } + + // Loads the return value shadow and origin. + if (!FT->getReturnType()->isVoidTy()) { + LoadInst *LabelLoad = + IRB.CreateLoad(DFSF.DFS.PrimitiveShadowTy, DFSF.LabelReturnAlloca); + DFSF.setShadow(CustomCI, DFSF.expandFromPrimitiveShadow( + FT->getReturnType(), LabelLoad, &CB)); + if (ShouldTrackOrigins) { + LoadInst *OriginLoad = + IRB.CreateLoad(DFSF.DFS.OriginTy, DFSF.OriginReturnAlloca); + DFSF.setOrigin(CustomCI, OriginLoad); } - break; } + + CI->replaceAllUsesWith(CustomCI); + CI->eraseFromParent(); + return true; } + return false; +} +void DFSanVisitor::visitCallBase(CallBase &CB) { + Function *F = CB.getCalledFunction(); + if ((F && F->isIntrinsic()) || CB.isInlineAsm()) { + visitInstOperands(CB); + return; + } + + // Calls to this function are synthesized in wrappers, and we shouldn't + // instrument them. + if (F == DFSF.DFS.DFSanVarargWrapperFn.getCallee()->stripPointerCasts()) + return; + + DenseMap<Value *, Function *>::iterator UnwrappedFnIt = + DFSF.DFS.UnwrappedFnMap.find(CB.getCalledOperand()); + if (UnwrappedFnIt != DFSF.DFS.UnwrappedFnMap.end()) + if (visitWrappedCallBase(*UnwrappedFnIt->second, CB)) + return; + + IRBuilder<> IRB(&CB); + + const bool ShouldTrackOrigins = DFSF.DFS.shouldTrackOrigins(); FunctionType *FT = CB.getFunctionType(); if (DFSF.DFS.getInstrumentedABI() == DataFlowSanitizer::IA_TLS) { + // Stores argument shadows. unsigned ArgOffset = 0; const DataLayout &DL = getDataLayout(); for (unsigned I = 0, N = FT->getNumParams(); I != N; ++I) { + if (ShouldTrackOrigins) { + // Ignore overflowed origins + Value *ArgShadow = DFSF.getShadow(CB.getArgOperand(I)); + if (I < DFSF.DFS.NumOfElementsInArgOrgTLS && + !DFSF.DFS.isZeroShadow(ArgShadow)) + IRB.CreateStore(DFSF.getOrigin(CB.getArgOperand(I)), + DFSF.getArgOriginTLS(I, IRB)); + } + unsigned Size = DL.getTypeAllocSize(DFSF.DFS.getShadowTy(FT->getParamType(I))); // Stop storing if arguments' size overflows. Inside a function, arguments // after overflow have zero shadow values. - if (ArgOffset + Size > kArgTLSSize) + if (ArgOffset + Size > ArgTLSSize) break; IRB.CreateAlignedStore( DFSF.getShadow(CB.getArgOperand(I)), DFSF.getArgTLS(FT->getParamType(I), ArgOffset, IRB), - kShadowTLSAlignment); - ArgOffset += alignTo(Size, kShadowTLSAlignment); + ShadowTLSAlignment); + ArgOffset += alignTo(Size, ShadowTLSAlignment); } } @@ -2119,53 +3100,72 @@ void DFSanVisitor::visitCallBase(CallBase &CB) { } if (DFSF.DFS.getInstrumentedABI() == DataFlowSanitizer::IA_TLS) { + // Don't emit the epilogue for musttail call returns. + if (isa<CallInst>(CB) && cast<CallInst>(CB).isMustTailCall()) + return; + + // Loads the return value shadow. IRBuilder<> NextIRB(Next); const DataLayout &DL = getDataLayout(); unsigned Size = DL.getTypeAllocSize(DFSF.DFS.getShadowTy(&CB)); - if (Size > kRetvalTLSSize) { + if (Size > RetvalTLSSize) { // Set overflowed return shadow to be zero. DFSF.setShadow(&CB, DFSF.DFS.getZeroShadow(&CB)); } else { LoadInst *LI = NextIRB.CreateAlignedLoad( DFSF.DFS.getShadowTy(&CB), DFSF.getRetvalTLS(CB.getType(), NextIRB), - kShadowTLSAlignment, "_dfsret"); + ShadowTLSAlignment, "_dfsret"); DFSF.SkipInsts.insert(LI); DFSF.setShadow(&CB, LI); DFSF.NonZeroChecks.push_back(LI); } + + if (ShouldTrackOrigins) { + LoadInst *LI = NextIRB.CreateLoad( + DFSF.DFS.OriginTy, DFSF.getRetvalOriginTLS(), "_dfsret_o"); + DFSF.SkipInsts.insert(LI); + DFSF.setOrigin(&CB, LI); + } } } // Do all instrumentation for IA_Args down here to defer tampering with the // CFG in a way that SplitEdge may be able to detect. if (DFSF.DFS.getInstrumentedABI() == DataFlowSanitizer::IA_Args) { + // TODO: handle musttail call returns for IA_Args. + FunctionType *NewFT = DFSF.DFS.getArgsFunctionType(FT); Value *Func = IRB.CreateBitCast(CB.getCalledOperand(), PointerType::getUnqual(NewFT)); - std::vector<Value *> Args; - auto i = CB.arg_begin(), E = CB.arg_end(); - for (unsigned n = FT->getNumParams(); n != 0; ++i, --n) - Args.push_back(*i); + const unsigned NumParams = FT->getNumParams(); + + // Copy original arguments. + auto *ArgIt = CB.arg_begin(), *ArgEnd = CB.arg_end(); + std::vector<Value *> Args(NumParams); + std::copy_n(ArgIt, NumParams, Args.begin()); - i = CB.arg_begin(); - for (unsigned n = FT->getNumParams(); n != 0; ++i, --n) - Args.push_back(DFSF.getShadow(*i)); + // Add shadow arguments by transforming original arguments. + std::generate_n(std::back_inserter(Args), NumParams, + [&]() { return DFSF.getShadow(*ArgIt++); }); if (FT->isVarArg()) { - unsigned VarArgSize = CB.arg_size() - FT->getNumParams(); + unsigned VarArgSize = CB.arg_size() - NumParams; ArrayType *VarArgArrayTy = ArrayType::get(DFSF.DFS.PrimitiveShadowTy, VarArgSize); AllocaInst *VarArgShadow = - new AllocaInst(VarArgArrayTy, getDataLayout().getAllocaAddrSpace(), - "", &DFSF.F->getEntryBlock().front()); + new AllocaInst(VarArgArrayTy, getDataLayout().getAllocaAddrSpace(), + "", &DFSF.F->getEntryBlock().front()); Args.push_back(IRB.CreateConstGEP2_32(VarArgArrayTy, VarArgShadow, 0, 0)); - for (unsigned n = 0; i != E; ++i, ++n) { + + // Copy remaining var args. + unsigned GepIndex = 0; + std::for_each(ArgIt, ArgEnd, [&](Value *Arg) { IRB.CreateStore( - DFSF.getShadow(*i), - IRB.CreateConstGEP2_32(VarArgArrayTy, VarArgShadow, 0, n)); - Args.push_back(*i); - } + DFSF.getShadow(Arg), + IRB.CreateConstGEP2_32(VarArgArrayTy, VarArgShadow, 0, GepIndex++)); + Args.push_back(Arg); + }); } CallBase *NewCB; @@ -2202,13 +3202,22 @@ void DFSanVisitor::visitPHINode(PHINode &PN) { // Give the shadow phi node valid predecessors to fool SplitEdge into working. Value *UndefShadow = UndefValue::get(ShadowTy); - for (PHINode::block_iterator i = PN.block_begin(), e = PN.block_end(); i != e; - ++i) { - ShadowPN->addIncoming(UndefShadow, *i); - } + for (BasicBlock *BB : PN.blocks()) + ShadowPN->addIncoming(UndefShadow, BB); - DFSF.PHIFixups.push_back(std::make_pair(&PN, ShadowPN)); DFSF.setShadow(&PN, ShadowPN); + + PHINode *OriginPN = nullptr; + if (DFSF.DFS.shouldTrackOrigins()) { + OriginPN = + PHINode::Create(DFSF.DFS.OriginTy, PN.getNumIncomingValues(), "", &PN); + Value *UndefOrigin = UndefValue::get(DFSF.DFS.OriginTy); + for (BasicBlock *BB : PN.blocks()) + OriginPN->addIncoming(UndefOrigin, BB); + DFSF.setOrigin(&PN, OriginPN); + } + + DFSF.PHIFixups.push_back({&PN, ShadowPN, OriginPN}); } namespace { |