Index: lib/Transforms/Instrumentation/SafeStack.cpp =================================================================== --- lib/Transforms/Instrumentation/SafeStack.cpp +++ lib/Transforms/Instrumentation/SafeStack.cpp @@ -19,6 +19,8 @@ #include "llvm/ADT/Statistic.h" #include "llvm/ADT/Triple.h" #include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Analysis/MemoryBuiltins.h" +#include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/CodeGen/Passes.h" #include "llvm/IR/Constants.h" #include "llvm/IR/DataLayout.h" @@ -65,106 +67,14 @@ namespace { -/// Check whether a given alloca instruction (AI) should be put on the safe -/// stack or not. The function analyzes all uses of AI and checks whether it is -/// only accessed in a memory safe way (as decided statically). -bool IsSafeStackAlloca(const AllocaInst *AI) { - // Go through all uses of this alloca and check whether all accesses to the - // allocated object are statically known to be memory safe and, hence, the - // object can be placed on the safe stack. - - SmallPtrSet Visited; - SmallVector WorkList; - WorkList.push_back(AI); - - // A DFS search through all uses of the alloca in bitcasts/PHI/GEPs/etc. - while (!WorkList.empty()) { - const Instruction *V = WorkList.pop_back_val(); - for (const Use &UI : V->uses()) { - auto I = cast(UI.getUser()); - assert(V == UI.get()); - - switch (I->getOpcode()) { - case Instruction::Load: - // Loading from a pointer is safe. - break; - case Instruction::VAArg: - // "va-arg" from a pointer is safe. - break; - case Instruction::Store: - if (V == I->getOperand(0)) - // Stored the pointer - conservatively assume it may be unsafe. - return false; - // Storing to the pointee is safe. - break; - - case Instruction::GetElementPtr: - if (!cast(I)->hasAllConstantIndices()) - // GEP with non-constant indices can lead to memory errors. - // This also applies to inbounds GEPs, as the inbounds attribute - // represents an assumption that the address is in bounds, rather than - // an assertion that it is. - return false; - - // We assume that GEP on static alloca with constant indices is safe, - // otherwise a compiler would detect it and warn during compilation. - - if (!isa(AI->getArraySize())) - // However, if the array size itself is not constant, the access - // might still be unsafe at runtime. - return false; - - /* fallthrough */ - - case Instruction::BitCast: - case Instruction::IntToPtr: - case Instruction::PHI: - case Instruction::PtrToInt: - case Instruction::Select: - // The object can be safe or not, depending on how the result of the - // instruction is used. - if (Visited.insert(I).second) - WorkList.push_back(cast(I)); - break; - - case Instruction::Call: - case Instruction::Invoke: { - // FIXME: add support for memset and memcpy intrinsics. - ImmutableCallSite CS(I); - - // LLVM 'nocapture' attribute is only set for arguments whose address - // is not stored, passed around, or used in any other non-trivial way. - // We assume that passing a pointer to an object as a 'nocapture' - // argument is safe. - // FIXME: a more precise solution would require an interprocedural - // analysis here, which would look at all uses of an argument inside - // the function being called. - ImmutableCallSite::arg_iterator B = CS.arg_begin(), E = CS.arg_end(); - for (ImmutableCallSite::arg_iterator A = B; A != E; ++A) - if (A->get() == V && !CS.doesNotCapture(A - B)) - // The parameter is not marked 'nocapture' - unsafe. - return false; - continue; - } - - default: - // The object is unsafe if it is used in any other way. - return false; - } - } - } - - // All uses of the alloca are safe, we can place it on the safe stack. - return true; -} - /// The SafeStack pass splits the stack of each function into the /// safe stack, which is only accessed through memory safe dereferences /// (as determined statically), and the unsafe stack, which contains all /// local variables that are accessed in unsafe ways. class SafeStack : public FunctionPass { const TargetMachine *TM; - const TargetLoweringBase *TLI; + const TargetLoweringBase *TL; + const TargetLibraryInfo *TLI; const DataLayout *DL; Type *StackPtrTy; @@ -221,16 +131,25 @@ AllocaInst *DynamicTop, ArrayRef DynamicAllocas); + bool IsSafeStackAlloca(const AllocaInst *AI, + ObjectSizeOffsetVisitor &Visitor); + + bool IsMemIntrinsicSafe(const MemIntrinsic *MI, const Use &U, + ObjectSizeOffsetVisitor &Visitor); + bool IsAccessSafe(Value *Addr, uint64_t Size, + ObjectSizeOffsetVisitor &Visitor); + public: static char ID; // Pass identification, replacement for typeid. SafeStack(const TargetMachine *TM) - : FunctionPass(ID), TM(TM), TLI(nullptr), DL(nullptr) { + : FunctionPass(ID), TM(TM), TL(nullptr), TLI(nullptr), DL(nullptr) { initializeSafeStackPass(*PassRegistry::getPassRegistry()); } SafeStack() : SafeStack(nullptr) {} void getAnalysisUsage(AnalysisUsage &AU) const override { AU.addRequired(); + AU.addRequired(); } bool doInitialization(Module &M) override { @@ -247,6 +166,135 @@ bool runOnFunction(Function &F) override; }; // class SafeStack +bool SafeStack::IsAccessSafe(Value *Addr, uint64_t Size, + ObjectSizeOffsetVisitor &Visitor) { + SizeOffsetType SizeOffset = Visitor.compute(Addr); + if (!Visitor.bothKnown(SizeOffset)) + return false; + + uint64_t ObjectSize = SizeOffset.first.getZExtValue(); + int64_t Offset = SizeOffset.second.getSExtValue(); + return Offset >= 0 && ObjectSize >= uint64_t(Offset) && + ObjectSize - uint64_t(Offset) >= Size; +} + +bool SafeStack::IsMemIntrinsicSafe(const MemIntrinsic *MI, const Use &U, + ObjectSizeOffsetVisitor &Visitor) { + // All MemIntrincis have destination address in Arg0 and size in Arg2. + if (MI->getRawDest() != U) return true; + const auto *Len = dyn_cast(MI->getLength()); + // Non-constant size => unsafe. + if (!Len) return false; + return IsAccessSafe(U, Len->getZExtValue(), Visitor); +} + +/// Check whether a given alloca instruction (AI) should be put on the safe +/// stack or not. The function analyzes all uses of AI and checks whether it is +/// only accessed in a memory safe way (as decided statically). +bool SafeStack::IsSafeStackAlloca(const AllocaInst *AI, + ObjectSizeOffsetVisitor &Visitor) { + // Go through all uses of this alloca and check whether all accesses to the + // allocated object are statically known to be memory safe and, hence, the + // object can be placed on the safe stack. + auto AA = &getAnalysis().getAAResults(); + + SmallPtrSet Visited; + SmallVector WorkList; + WorkList.push_back(AI); + + // A DFS search through all uses of the alloca in bitcasts/PHI/GEPs/etc. + while (!WorkList.empty()) { + const Instruction *V = WorkList.pop_back_val(); + for (const Use &UI : V->uses()) { + auto I = cast(UI.getUser()); + assert(V == UI.get()); + + switch (I->getOpcode()) { + case Instruction::Load: + // Loading from a pointer is safe. + break; + case Instruction::VAArg: + // "va-arg" from a pointer is safe. + break; + case Instruction::Store: + if (V == I->getOperand(0)) + // Stored the pointer - conservatively assume it may be unsafe. + return false; + if (!IsAccessSafe(UI, DL->getTypeStoreSize(I->getOperand(0)->getType()), + Visitor)) + return false; + break; + + case Instruction::GetElementPtr: + if (!cast(I)->hasAllConstantIndices()) + // GEP with non-constant indices can lead to memory errors. + // This also applies to inbounds GEPs, as the inbounds attribute + // represents an assumption that the address is in bounds, rather than + // an assertion that it is. + return false; + + // We assume that GEP on static alloca with constant indices is safe, + // otherwise a compiler would detect it and warn during compilation. + + if (!isa(AI->getArraySize())) + // However, if the array size itself is not constant, the access + // might still be unsafe at runtime. + return false; + + /* fallthrough */ + + case Instruction::BitCast: + case Instruction::IntToPtr: + case Instruction::PHI: + case Instruction::PtrToInt: + case Instruction::Select: + // The object can be safe or not, depending on how the result of the + // instruction is used. + if (Visited.insert(I).second) + WorkList.push_back(cast(I)); + break; + + case Instruction::Call: + case Instruction::Invoke: { + // FIXME: add support for memset and memcpy intrinsics. + ImmutableCallSite CS(I); + + if (const MemIntrinsic *MI = dyn_cast(I)) { + if (!IsMemIntrinsicSafe(MI, UI, Visitor)) + return false; + continue; + } + + // LLVM 'nocapture' attribute is only set for arguments whose address + // is not stored, passed around, or used in any other non-trivial way. + // We assume that passing a pointer to an object as a 'nocapture' + // argument is safe. + // FIXME: a more precise solution would require an interprocedural + // analysis here, which would look at all uses of an argument inside + // the function being called. + ImmutableCallSite::arg_iterator B = CS.arg_begin(), E = CS.arg_end(); + for (ImmutableCallSite::arg_iterator A = B; A != E; ++A) { + if (A->get() == V) { + if (!CS.doesNotCapture(A - B)) + return false; + if (!AA->onlyReadsMemory(CS) && !CS.onlyReadsMemory(A - B)) + return false; + } + } + continue; + } + + default: + // The object is unsafe if it is used in any other way. + return false; + } + } + } + + // All uses of the alloca are safe, we can place it on the safe stack. + return true; +} + Value *SafeStack::getOrCreateUnsafeStackPtr(IRBuilder<> &IRB, Function &F) { Module &M = *F.getParent(); Triple TargetTriple(M.getTargetTriple()); @@ -254,7 +302,7 @@ unsigned Offset; unsigned AddressSpace; // Check if the target keeps the unsafe stack pointer at a fixed offset. - if (TLI && TLI->getSafeStackPointerLocation(AddressSpace, Offset)) { + if (TL && TL->getSafeStackPointerLocation(AddressSpace, Offset)) { Constant *OffsetVal = ConstantInt::get(Type::getInt32Ty(F.getContext()), Offset); return ConstantExpr::getIntToPtr(OffsetVal, @@ -300,11 +348,13 @@ SmallVectorImpl &DynamicAllocas, SmallVectorImpl &Returns, SmallVectorImpl &StackRestorePoints) { + ObjectSizeOffsetVisitor Visitor(*DL, TLI, F.getContext(), + /*RoundToAlign=*/true); for (Instruction &I : instructions(&F)) { if (auto AI = dyn_cast(&I)) { ++NumAllocas; - if (IsSafeStackAlloca(AI)) + if (IsSafeStackAlloca(AI, Visitor)) continue; if (AI->isStaticAlloca()) { @@ -548,8 +598,8 @@ } auto AA = &getAnalysis().getAAResults(); - - TLI = TM ? TM->getSubtargetImpl(F)->getTargetLowering() : nullptr; + TL = TM ? TM->getSubtargetImpl(F)->getTargetLowering() : nullptr; + TLI = &getAnalysis().getTLI(); { // Make sure the regular stack protector won't run on this function Index: test/Transforms/SafeStack/call.ll =================================================================== --- test/Transforms/SafeStack/call.ll +++ test/Transforms/SafeStack/call.ll @@ -6,10 +6,11 @@ ; no arrays / no nested arrays ; Requires no protector. -; CHECK-LABEL: @foo( define void @foo(i8* %a) nounwind uwtable safestack { entry: + ; CHECK-LABEL: define void @foo( ; CHECK-NOT: __safestack_unsafe_stack_ptr + ; CHECK: ret void %a.addr = alloca i8*, align 8 store i8* %a, i8** %a.addr, align 8 %0 = load i8*, i8** %a.addr, align 8 @@ -18,3 +19,105 @@ } declare i32 @printf(i8*, ...) + +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" +target triple = "x86_64-unknown-linux-gnu" + +define void @call_memset(i64 %len) safestack { +entry: + ; CHECK-LABEL: define void @call_memset + ; CHECK: @__safestack_unsafe_stack_ptr + ; CHECK: ret void + %q = alloca [10 x i8], align 1 + %arraydecay = getelementptr inbounds [10 x i8], [10 x i8]* %q, i32 0, i32 0 + call void @llvm.memset.p0i8.i64(i8* %arraydecay, i8 1, i64 %len, i32 1, i1 false) + ret void +} + +define void @call_constant_memset() safestack { +entry: + ; CHECK-LABEL: define void @call_constant_memset + ; CHECK-NOT: @__safestack_unsafe_stack_ptr + ; CHECK: ret void + %q = alloca [10 x i8], align 1 + %arraydecay = getelementptr inbounds [10 x i8], [10 x i8]* %q, i32 0, i32 2 + call void @llvm.memset.p0i8.i64(i8* %arraydecay, i8 1, i64 7, i32 1, i1 false) + ret void +} + +define void @call_constant_overflow_memset() safestack { +entry: + ; CHECK-LABEL: define void @call_constant_overflow_memset + ; CHECK: @__safestack_unsafe_stack_ptr + ; CHECK: ret void + %q = alloca [10 x i8], align 1 + %arraydecay = getelementptr inbounds [10 x i8], [10 x i8]* %q, i32 0, i32 7 + call void @llvm.memset.p0i8.i64(i8* %arraydecay, i8 1, i64 5, i32 1, i1 false) + ret void +} + +define void @call_constant_underflow_memset() safestack { +entry: + ; CHECK-LABEL: define void @call_constant_underflow_memset + ; CHECK: @__safestack_unsafe_stack_ptr + ; CHECK: ret void + %q = alloca [10 x i8], align 1 + %arraydecay = getelementptr [10 x i8], [10 x i8]* %q, i32 0, i32 -1 + call void @llvm.memset.p0i8.i64(i8* %arraydecay, i8 1, i64 3, i32 1, i1 false) + ret void +} + +; Readonly nocapture -> safe +define void @call_readonly(i64 %len) safestack { +entry: + ; CHECK-LABEL: define void @call_readonly + ; CHECK-NOT: @__safestack_unsafe_stack_ptr + ; CHECK: ret void + %q = alloca [10 x i8], align 1 + %arraydecay = getelementptr inbounds [10 x i8], [10 x i8]* %q, i32 0, i32 0 + call void @readonly(i8* %arraydecay) + ret void +} + +; Readonly nocapture -> safe +define void @call_arg_readonly(i64 %len) safestack { +entry: + ; CHECK-LABEL: define void @call_arg_readonly + ; CHECK-NOT: @__safestack_unsafe_stack_ptr + ; CHECK: ret void + %q = alloca [10 x i8], align 1 + %arraydecay = getelementptr inbounds [10 x i8], [10 x i8]* %q, i32 0, i32 0 + call void @arg_readonly(i8* %arraydecay) + ret void +} + +; Readwrite nocapture -> unsafe +define void @call_readwrite(i64 %len) safestack { +entry: + ; CHECK-LABEL: define void @call_readwrite + ; CHECK: @__safestack_unsafe_stack_ptr + ; CHECK: ret void + %q = alloca [10 x i8], align 1 + %arraydecay = getelementptr inbounds [10 x i8], [10 x i8]* %q, i32 0, i32 0 + call void @readwrite(i8* %arraydecay) + ret void +} + +; Captures the argument -> unsafe +define void @call_capture(i64 %len) safestack { +entry: + ; CHECK-LABEL: define void @call_capture + ; CHECK: @__safestack_unsafe_stack_ptr + ; CHECK: ret void + %q = alloca [10 x i8], align 1 + %arraydecay = getelementptr inbounds [10 x i8], [10 x i8]* %q, i32 0, i32 0 + call void @capture(i8* %arraydecay) + ret void +} + +declare void @readonly(i8* nocapture) readonly +declare void @arg_readonly(i8* readonly nocapture) +declare void @readwrite(i8* nocapture) +declare void @capture(i8* readonly) readonly + +declare void @llvm.memset.p0i8.i64(i8* nocapture, i8, i64, i32, i1) nounwind argmemonly