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,13 +67,137 @@ namespace { +/// 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 ways that we can't prove to +/// be safe. +class SafeStack : public FunctionPass { + const TargetMachine *TM; + const TargetLoweringBase *TL; + const TargetLibraryInfo *TLI; + const DataLayout *DL; + + Type *StackPtrTy; + Type *IntPtrTy; + Type *Int32Ty; + Type *Int8Ty; + + Value *UnsafeStackPtr = nullptr; + + /// Unsafe stack alignment. Each stack frame must ensure that the stack is + /// aligned to this value. We need to re-align the unsafe stack if the + /// alignment of any object on the stack exceeds this value. + /// + /// 16 seems like a reasonable upper bound on the alignment of objects that we + /// might expect to appear on the stack on most common targets. + enum { StackAlignment = 16 }; + + /// \brief Build a constant representing a pointer to the unsafe stack + /// pointer. + Value *getOrCreateUnsafeStackPtr(IRBuilder<> &IRB, Function &F); + + /// \brief Find all static allocas, dynamic allocas, return instructions and + /// stack restore points (exception unwind blocks and setjmp calls) in the + /// given function and append them to the respective vectors. + void findInsts(Function &F, SmallVectorImpl &StaticAllocas, + SmallVectorImpl &DynamicAllocas, + SmallVectorImpl &Returns, + SmallVectorImpl &StackRestorePoints); + + /// \brief Allocate space for all static allocas in \p StaticAllocas, + /// replace allocas with pointers into the unsafe stack and generate code to + /// restore the stack pointer before all return instructions in \p Returns. + /// + /// \returns A pointer to the top of the unsafe stack after all unsafe static + /// allocas are allocated. + Value *moveStaticAllocasToUnsafeStack(IRBuilder<> &IRB, Function &F, + ArrayRef StaticAllocas, + ArrayRef Returns); + + /// \brief Generate code to restore the stack after all stack restore points + /// in \p StackRestorePoints. + /// + /// \returns A local variable in which to maintain the dynamic top of the + /// unsafe stack if needed. + AllocaInst * + createStackRestorePoints(IRBuilder<> &IRB, Function &F, + ArrayRef StackRestorePoints, + Value *StaticTop, bool NeedDynamicTop); + + /// \brief Replace all allocas in \p DynamicAllocas with code to allocate + /// space dynamically on the unsafe stack and store the dynamic unsafe stack + /// top to \p DynamicTop if non-null. + void moveDynamicAllocasToUnsafeStack(Function &F, Value *UnsafeStackPtr, + 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), 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 { + DL = &M.getDataLayout(); + + StackPtrTy = Type::getInt8PtrTy(M.getContext()); + IntPtrTy = DL->getIntPtrType(M.getContext()); + Int32Ty = Type::getInt32Ty(M.getContext()); + Int8Ty = Type::getInt8Ty(M.getContext()); + + return false; + } + + 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 IsSafeStackAlloca(const AllocaInst *AI) { +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; @@ -95,7 +221,9 @@ if (V == I->getOperand(0)) // Stored the pointer - conservatively assume it may be unsafe. return false; - // Storing to the pointee is safe. + if (!IsAccessSafe(UI, DL->getTypeStoreSize(I->getOperand(0)->getType()), + Visitor)) + return false; break; case Instruction::GetElementPtr: @@ -132,6 +260,12 @@ // 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' @@ -140,10 +274,14 @@ // 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; + 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; } @@ -158,95 +296,6 @@ 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 DataLayout *DL; - - Type *StackPtrTy; - Type *IntPtrTy; - Type *Int32Ty; - Type *Int8Ty; - - Value *UnsafeStackPtr = nullptr; - - /// Unsafe stack alignment. Each stack frame must ensure that the stack is - /// aligned to this value. We need to re-align the unsafe stack if the - /// alignment of any object on the stack exceeds this value. - /// - /// 16 seems like a reasonable upper bound on the alignment of objects that we - /// might expect to appear on the stack on most common targets. - enum { StackAlignment = 16 }; - - /// \brief Build a constant representing a pointer to the unsafe stack - /// pointer. - Value *getOrCreateUnsafeStackPtr(IRBuilder<> &IRB, Function &F); - - /// \brief Find all static allocas, dynamic allocas, return instructions and - /// stack restore points (exception unwind blocks and setjmp calls) in the - /// given function and append them to the respective vectors. - void findInsts(Function &F, SmallVectorImpl &StaticAllocas, - SmallVectorImpl &DynamicAllocas, - SmallVectorImpl &Returns, - SmallVectorImpl &StackRestorePoints); - - /// \brief Allocate space for all static allocas in \p StaticAllocas, - /// replace allocas with pointers into the unsafe stack and generate code to - /// restore the stack pointer before all return instructions in \p Returns. - /// - /// \returns A pointer to the top of the unsafe stack after all unsafe static - /// allocas are allocated. - Value *moveStaticAllocasToUnsafeStack(IRBuilder<> &IRB, Function &F, - ArrayRef StaticAllocas, - ArrayRef Returns); - - /// \brief Generate code to restore the stack after all stack restore points - /// in \p StackRestorePoints. - /// - /// \returns A local variable in which to maintain the dynamic top of the - /// unsafe stack if needed. - AllocaInst * - createStackRestorePoints(IRBuilder<> &IRB, Function &F, - ArrayRef StackRestorePoints, - Value *StaticTop, bool NeedDynamicTop); - - /// \brief Replace all allocas in \p DynamicAllocas with code to allocate - /// space dynamically on the unsafe stack and store the dynamic unsafe stack - /// top to \p DynamicTop if non-null. - void moveDynamicAllocasToUnsafeStack(Function &F, Value *UnsafeStackPtr, - AllocaInst *DynamicTop, - ArrayRef DynamicAllocas); - -public: - static char ID; // Pass identification, replacement for typeid. - SafeStack(const TargetMachine *TM) - : FunctionPass(ID), TM(TM), TLI(nullptr), DL(nullptr) { - initializeSafeStackPass(*PassRegistry::getPassRegistry()); - } - SafeStack() : SafeStack(nullptr) {} - - void getAnalysisUsage(AnalysisUsage &AU) const override { - AU.addRequired(); - } - - bool doInitialization(Module &M) override { - DL = &M.getDataLayout(); - - StackPtrTy = Type::getInt8PtrTy(M.getContext()); - IntPtrTy = DL->getIntPtrType(M.getContext()); - Int32Ty = Type::getInt32Ty(M.getContext()); - Int8Ty = Type::getInt8Ty(M.getContext()); - - return false; - } - - bool runOnFunction(Function &F) override; -}; // class SafeStack - Value *SafeStack::getOrCreateUnsafeStackPtr(IRBuilder<> &IRB, Function &F) { Module &M = *F.getParent(); Triple TargetTriple(M.getTargetTriple()); @@ -254,7 +303,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 +349,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 +599,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 Index: test/Transforms/SafeStack/store.ll =================================================================== --- /dev/null +++ test/Transforms/SafeStack/store.ll @@ -0,0 +1,63 @@ +; RUN: opt -safe-stack -S -mtriple=i386-pc-linux-gnu < %s -o - | FileCheck %s +; RUN: opt -safe-stack -S -mtriple=x86_64-pc-linux-gnu < %s -o - | FileCheck %s + +@.str = private unnamed_addr constant [4 x i8] c"%s\0A\00", align 1 + +define void @bad_store() nounwind uwtable safestack { +entry: + ; CHECK-LABEL: @bad_store( + ; CHECK: __safestack_unsafe_stack_ptr + ; CHECK: ret void + %a = alloca i32, align 4 + %0 = ptrtoint i32* %a to i64 + %1 = inttoptr i64 %0 to i64* + store i64 zeroinitializer, i64* %1 + ret void +} + +define void @good_store() nounwind uwtable safestack { +entry: + ; CHECK-LABEL: @good_store( + ; CHECK-NOT: __safestack_unsafe_stack_ptr + ; CHECK: ret void + %a = alloca i32, align 4 + %0 = bitcast i32* %a to i8* + store i8 zeroinitializer, i8* %0 + ret void +} + +define void @overflow_gep_store() nounwind uwtable safestack { +entry: + ; CHECK-LABEL: @overflow_gep_store( + ; CHECK: __safestack_unsafe_stack_ptr + ; CHECK: ret void + %a = alloca i32, align 4 + %0 = bitcast i32* %a to i8* + %1 = getelementptr i8, i8* %0, i32 4 + store i8 zeroinitializer, i8* %1 + ret void +} + +define void @underflow_gep_store() nounwind uwtable safestack { +entry: + ; CHECK-LABEL: @underflow_gep_store( + ; CHECK: __safestack_unsafe_stack_ptr + ; CHECK: ret void + %a = alloca i32, align 4 + %0 = bitcast i32* %a to i8* + %1 = getelementptr i8, i8* %0, i32 -1 + store i8 zeroinitializer, i8* %1 + ret void +} + +define void @good_gep_store() nounwind uwtable safestack { +entry: + ; CHECK-LABEL: @good_gep_store( + ; CHECK-NOT: __safestack_unsafe_stack_ptr + ; CHECK: ret void + %a = alloca i32, align 4 + %0 = bitcast i32* %a to i8* + %1 = getelementptr i8, i8* %0, i32 3 + store i8 zeroinitializer, i8* %1 + ret void +}