1 //===-- SafeStack.cpp - Safe Stack Insertion ------------------------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This pass splits the stack into the safe stack (kept as-is for LLVM backend) 11 // and the unsafe stack (explicitly allocated and managed through the runtime 12 // support library). 13 // 14 // http://clang.llvm.org/docs/SafeStack.html 15 // 16 //===----------------------------------------------------------------------===// 17 18 #include "SafeStackColoring.h" 19 #include "SafeStackLayout.h" 20 #include "llvm/ADT/Statistic.h" 21 #include "llvm/ADT/Triple.h" 22 #include "llvm/Analysis/BranchProbabilityInfo.h" 23 #include "llvm/Analysis/ScalarEvolution.h" 24 #include "llvm/Analysis/ScalarEvolutionExpressions.h" 25 #include "llvm/CodeGen/Passes.h" 26 #include "llvm/IR/Constants.h" 27 #include "llvm/IR/DIBuilder.h" 28 #include "llvm/IR/DataLayout.h" 29 #include "llvm/IR/DerivedTypes.h" 30 #include "llvm/IR/Function.h" 31 #include "llvm/IR/IRBuilder.h" 32 #include "llvm/IR/InstIterator.h" 33 #include "llvm/IR/Instructions.h" 34 #include "llvm/IR/IntrinsicInst.h" 35 #include "llvm/IR/Intrinsics.h" 36 #include "llvm/IR/MDBuilder.h" 37 #include "llvm/IR/Module.h" 38 #include "llvm/Pass.h" 39 #include "llvm/Support/CommandLine.h" 40 #include "llvm/Support/Debug.h" 41 #include "llvm/Support/Format.h" 42 #include "llvm/Support/MathExtras.h" 43 #include "llvm/Support/raw_os_ostream.h" 44 #include "llvm/Target/TargetLowering.h" 45 #include "llvm/Target/TargetSubtargetInfo.h" 46 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 47 #include "llvm/Transforms/Utils/Local.h" 48 #include "llvm/Transforms/Utils/ModuleUtils.h" 49 50 using namespace llvm; 51 using namespace llvm::safestack; 52 53 #define DEBUG_TYPE "safestack" 54 55 enum UnsafeStackPtrStorageVal { ThreadLocalUSP, SingleThreadUSP }; 56 57 static cl::opt<UnsafeStackPtrStorageVal> USPStorage("safe-stack-usp-storage", 58 cl::Hidden, cl::init(ThreadLocalUSP), 59 cl::desc("Type of storage for the unsafe stack pointer"), 60 cl::values(clEnumValN(ThreadLocalUSP, "thread-local", 61 "Thread-local storage"), 62 clEnumValN(SingleThreadUSP, "single-thread", 63 "Non-thread-local storage"), 64 clEnumValEnd)); 65 66 namespace llvm { 67 68 STATISTIC(NumFunctions, "Total number of functions"); 69 STATISTIC(NumUnsafeStackFunctions, "Number of functions with unsafe stack"); 70 STATISTIC(NumUnsafeStackRestorePointsFunctions, 71 "Number of functions that use setjmp or exceptions"); 72 73 STATISTIC(NumAllocas, "Total number of allocas"); 74 STATISTIC(NumUnsafeStaticAllocas, "Number of unsafe static allocas"); 75 STATISTIC(NumUnsafeDynamicAllocas, "Number of unsafe dynamic allocas"); 76 STATISTIC(NumUnsafeByValArguments, "Number of unsafe byval arguments"); 77 STATISTIC(NumUnsafeStackRestorePoints, "Number of setjmps and landingpads"); 78 79 } // namespace llvm 80 81 namespace { 82 83 /// Rewrite an SCEV expression for a memory access address to an expression that 84 /// represents offset from the given alloca. 85 /// 86 /// The implementation simply replaces all mentions of the alloca with zero. 87 class AllocaOffsetRewriter : public SCEVRewriteVisitor<AllocaOffsetRewriter> { 88 const Value *AllocaPtr; 89 90 public: 91 AllocaOffsetRewriter(ScalarEvolution &SE, const Value *AllocaPtr) 92 : SCEVRewriteVisitor(SE), AllocaPtr(AllocaPtr) {} 93 94 const SCEV *visitUnknown(const SCEVUnknown *Expr) { 95 if (Expr->getValue() == AllocaPtr) 96 return SE.getZero(Expr->getType()); 97 return Expr; 98 } 99 }; 100 101 /// The SafeStack pass splits the stack of each function into the safe 102 /// stack, which is only accessed through memory safe dereferences (as 103 /// determined statically), and the unsafe stack, which contains all 104 /// local variables that are accessed in ways that we can't prove to 105 /// be safe. 106 class SafeStack : public FunctionPass { 107 const TargetMachine *TM; 108 const TargetLoweringBase *TL; 109 const DataLayout *DL; 110 ScalarEvolution *SE; 111 112 Type *StackPtrTy; 113 Type *IntPtrTy; 114 Type *Int32Ty; 115 Type *Int8Ty; 116 117 Value *UnsafeStackPtr = nullptr; 118 119 /// Unsafe stack alignment. Each stack frame must ensure that the stack is 120 /// aligned to this value. We need to re-align the unsafe stack if the 121 /// alignment of any object on the stack exceeds this value. 122 /// 123 /// 16 seems like a reasonable upper bound on the alignment of objects that we 124 /// might expect to appear on the stack on most common targets. 125 enum { StackAlignment = 16 }; 126 127 /// \brief Build a value representing a pointer to the unsafe stack pointer. 128 Value *getOrCreateUnsafeStackPtr(IRBuilder<> &IRB, Function &F); 129 130 /// \brief Return the value of the stack canary. 131 Value *getStackGuard(IRBuilder<> &IRB, Function &F); 132 133 /// \brief Load stack guard from the frame and check if it has changed. 134 void checkStackGuard(IRBuilder<> &IRB, Function &F, ReturnInst &RI, 135 AllocaInst *StackGuardSlot, Value *StackGuard); 136 137 /// \brief Find all static allocas, dynamic allocas, return instructions and 138 /// stack restore points (exception unwind blocks and setjmp calls) in the 139 /// given function and append them to the respective vectors. 140 void findInsts(Function &F, SmallVectorImpl<AllocaInst *> &StaticAllocas, 141 SmallVectorImpl<AllocaInst *> &DynamicAllocas, 142 SmallVectorImpl<Argument *> &ByValArguments, 143 SmallVectorImpl<ReturnInst *> &Returns, 144 SmallVectorImpl<Instruction *> &StackRestorePoints); 145 146 /// \brief Calculate the allocation size of a given alloca. Returns 0 if the 147 /// size can not be statically determined. 148 uint64_t getStaticAllocaAllocationSize(const AllocaInst* AI); 149 150 /// \brief Allocate space for all static allocas in \p StaticAllocas, 151 /// replace allocas with pointers into the unsafe stack and generate code to 152 /// restore the stack pointer before all return instructions in \p Returns. 153 /// 154 /// \returns A pointer to the top of the unsafe stack after all unsafe static 155 /// allocas are allocated. 156 Value *moveStaticAllocasToUnsafeStack(IRBuilder<> &IRB, Function &F, 157 ArrayRef<AllocaInst *> StaticAllocas, 158 ArrayRef<Argument *> ByValArguments, 159 ArrayRef<ReturnInst *> Returns, 160 Instruction *BasePointer, 161 AllocaInst *StackGuardSlot); 162 163 /// \brief Generate code to restore the stack after all stack restore points 164 /// in \p StackRestorePoints. 165 /// 166 /// \returns A local variable in which to maintain the dynamic top of the 167 /// unsafe stack if needed. 168 AllocaInst * 169 createStackRestorePoints(IRBuilder<> &IRB, Function &F, 170 ArrayRef<Instruction *> StackRestorePoints, 171 Value *StaticTop, bool NeedDynamicTop); 172 173 /// \brief Replace all allocas in \p DynamicAllocas with code to allocate 174 /// space dynamically on the unsafe stack and store the dynamic unsafe stack 175 /// top to \p DynamicTop if non-null. 176 void moveDynamicAllocasToUnsafeStack(Function &F, Value *UnsafeStackPtr, 177 AllocaInst *DynamicTop, 178 ArrayRef<AllocaInst *> DynamicAllocas); 179 180 bool IsSafeStackAlloca(const Value *AllocaPtr, uint64_t AllocaSize); 181 182 bool IsMemIntrinsicSafe(const MemIntrinsic *MI, const Use &U, 183 const Value *AllocaPtr, uint64_t AllocaSize); 184 bool IsAccessSafe(Value *Addr, uint64_t Size, const Value *AllocaPtr, 185 uint64_t AllocaSize); 186 187 public: 188 static char ID; // Pass identification, replacement for typeid. 189 SafeStack(const TargetMachine *TM) 190 : FunctionPass(ID), TM(TM), TL(nullptr), DL(nullptr) { 191 initializeSafeStackPass(*PassRegistry::getPassRegistry()); 192 } 193 SafeStack() : SafeStack(nullptr) {} 194 195 void getAnalysisUsage(AnalysisUsage &AU) const override { 196 AU.addRequired<ScalarEvolutionWrapperPass>(); 197 } 198 199 bool doInitialization(Module &M) override { 200 DL = &M.getDataLayout(); 201 202 StackPtrTy = Type::getInt8PtrTy(M.getContext()); 203 IntPtrTy = DL->getIntPtrType(M.getContext()); 204 Int32Ty = Type::getInt32Ty(M.getContext()); 205 Int8Ty = Type::getInt8Ty(M.getContext()); 206 207 return false; 208 } 209 210 bool runOnFunction(Function &F) override; 211 }; // class SafeStack 212 213 uint64_t SafeStack::getStaticAllocaAllocationSize(const AllocaInst* AI) { 214 uint64_t Size = DL->getTypeAllocSize(AI->getAllocatedType()); 215 if (AI->isArrayAllocation()) { 216 auto C = dyn_cast<ConstantInt>(AI->getArraySize()); 217 if (!C) 218 return 0; 219 Size *= C->getZExtValue(); 220 } 221 return Size; 222 } 223 224 bool SafeStack::IsAccessSafe(Value *Addr, uint64_t AccessSize, 225 const Value *AllocaPtr, uint64_t AllocaSize) { 226 AllocaOffsetRewriter Rewriter(*SE, AllocaPtr); 227 const SCEV *Expr = Rewriter.visit(SE->getSCEV(Addr)); 228 229 uint64_t BitWidth = SE->getTypeSizeInBits(Expr->getType()); 230 ConstantRange AccessStartRange = SE->getUnsignedRange(Expr); 231 ConstantRange SizeRange = 232 ConstantRange(APInt(BitWidth, 0), APInt(BitWidth, AccessSize)); 233 ConstantRange AccessRange = AccessStartRange.add(SizeRange); 234 ConstantRange AllocaRange = 235 ConstantRange(APInt(BitWidth, 0), APInt(BitWidth, AllocaSize)); 236 bool Safe = AllocaRange.contains(AccessRange); 237 238 DEBUG(dbgs() << "[SafeStack] " 239 << (isa<AllocaInst>(AllocaPtr) ? "Alloca " : "ByValArgument ") 240 << *AllocaPtr << "\n" 241 << " Access " << *Addr << "\n" 242 << " SCEV " << *Expr 243 << " U: " << SE->getUnsignedRange(Expr) 244 << ", S: " << SE->getSignedRange(Expr) << "\n" 245 << " Range " << AccessRange << "\n" 246 << " AllocaRange " << AllocaRange << "\n" 247 << " " << (Safe ? "safe" : "unsafe") << "\n"); 248 249 return Safe; 250 } 251 252 bool SafeStack::IsMemIntrinsicSafe(const MemIntrinsic *MI, const Use &U, 253 const Value *AllocaPtr, 254 uint64_t AllocaSize) { 255 // All MemIntrinsics have destination address in Arg0 and size in Arg2. 256 if (MI->getRawDest() != U) return true; 257 const auto *Len = dyn_cast<ConstantInt>(MI->getLength()); 258 // Non-constant size => unsafe. FIXME: try SCEV getRange. 259 if (!Len) return false; 260 return IsAccessSafe(U, Len->getZExtValue(), AllocaPtr, AllocaSize); 261 } 262 263 /// Check whether a given allocation must be put on the safe 264 /// stack or not. The function analyzes all uses of AI and checks whether it is 265 /// only accessed in a memory safe way (as decided statically). 266 bool SafeStack::IsSafeStackAlloca(const Value *AllocaPtr, uint64_t AllocaSize) { 267 // Go through all uses of this alloca and check whether all accesses to the 268 // allocated object are statically known to be memory safe and, hence, the 269 // object can be placed on the safe stack. 270 SmallPtrSet<const Value *, 16> Visited; 271 SmallVector<const Value *, 8> WorkList; 272 WorkList.push_back(AllocaPtr); 273 274 // A DFS search through all uses of the alloca in bitcasts/PHI/GEPs/etc. 275 while (!WorkList.empty()) { 276 const Value *V = WorkList.pop_back_val(); 277 for (const Use &UI : V->uses()) { 278 auto I = cast<const Instruction>(UI.getUser()); 279 assert(V == UI.get()); 280 281 switch (I->getOpcode()) { 282 case Instruction::Load: { 283 if (!IsAccessSafe(UI, DL->getTypeStoreSize(I->getType()), AllocaPtr, 284 AllocaSize)) 285 return false; 286 break; 287 } 288 case Instruction::VAArg: 289 // "va-arg" from a pointer is safe. 290 break; 291 case Instruction::Store: { 292 if (V == I->getOperand(0)) { 293 // Stored the pointer - conservatively assume it may be unsafe. 294 DEBUG(dbgs() << "[SafeStack] Unsafe alloca: " << *AllocaPtr 295 << "\n store of address: " << *I << "\n"); 296 return false; 297 } 298 299 if (!IsAccessSafe(UI, DL->getTypeStoreSize(I->getOperand(0)->getType()), 300 AllocaPtr, AllocaSize)) 301 return false; 302 break; 303 } 304 case Instruction::Ret: { 305 // Information leak. 306 return false; 307 } 308 309 case Instruction::Call: 310 case Instruction::Invoke: { 311 ImmutableCallSite CS(I); 312 313 if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { 314 if (II->getIntrinsicID() == Intrinsic::lifetime_start || 315 II->getIntrinsicID() == Intrinsic::lifetime_end) 316 continue; 317 } 318 319 if (const MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) { 320 if (!IsMemIntrinsicSafe(MI, UI, AllocaPtr, AllocaSize)) { 321 DEBUG(dbgs() << "[SafeStack] Unsafe alloca: " << *AllocaPtr 322 << "\n unsafe memintrinsic: " << *I 323 << "\n"); 324 return false; 325 } 326 continue; 327 } 328 329 // LLVM 'nocapture' attribute is only set for arguments whose address 330 // is not stored, passed around, or used in any other non-trivial way. 331 // We assume that passing a pointer to an object as a 'nocapture 332 // readnone' argument is safe. 333 // FIXME: a more precise solution would require an interprocedural 334 // analysis here, which would look at all uses of an argument inside 335 // the function being called. 336 ImmutableCallSite::arg_iterator B = CS.arg_begin(), E = CS.arg_end(); 337 for (ImmutableCallSite::arg_iterator A = B; A != E; ++A) 338 if (A->get() == V) 339 if (!(CS.doesNotCapture(A - B) && (CS.doesNotAccessMemory(A - B) || 340 CS.doesNotAccessMemory()))) { 341 DEBUG(dbgs() << "[SafeStack] Unsafe alloca: " << *AllocaPtr 342 << "\n unsafe call: " << *I << "\n"); 343 return false; 344 } 345 continue; 346 } 347 348 default: 349 if (Visited.insert(I).second) 350 WorkList.push_back(cast<const Instruction>(I)); 351 } 352 } 353 } 354 355 // All uses of the alloca are safe, we can place it on the safe stack. 356 return true; 357 } 358 359 Value *SafeStack::getOrCreateUnsafeStackPtr(IRBuilder<> &IRB, Function &F) { 360 // Check if there is a target-specific location for the unsafe stack pointer. 361 if (TL) 362 if (Value *V = TL->getSafeStackPointerLocation(IRB)) 363 return V; 364 365 // Otherwise, assume the target links with compiler-rt, which provides a 366 // thread-local variable with a magic name. 367 Module &M = *F.getParent(); 368 const char *UnsafeStackPtrVar = "__safestack_unsafe_stack_ptr"; 369 auto UnsafeStackPtr = 370 dyn_cast_or_null<GlobalVariable>(M.getNamedValue(UnsafeStackPtrVar)); 371 372 bool UseTLS = USPStorage == ThreadLocalUSP; 373 374 if (!UnsafeStackPtr) { 375 auto TLSModel = UseTLS ? 376 GlobalValue::InitialExecTLSModel : 377 GlobalValue::NotThreadLocal; 378 // The global variable is not defined yet, define it ourselves. 379 // We use the initial-exec TLS model because we do not support the 380 // variable living anywhere other than in the main executable. 381 UnsafeStackPtr = new GlobalVariable( 382 M, StackPtrTy, false, GlobalValue::ExternalLinkage, nullptr, 383 UnsafeStackPtrVar, nullptr, TLSModel); 384 } else { 385 // The variable exists, check its type and attributes. 386 if (UnsafeStackPtr->getValueType() != StackPtrTy) 387 report_fatal_error(Twine(UnsafeStackPtrVar) + " must have void* type"); 388 if (UseTLS != UnsafeStackPtr->isThreadLocal()) 389 report_fatal_error(Twine(UnsafeStackPtrVar) + " must " + 390 (UseTLS ? "" : "not ") + "be thread-local"); 391 } 392 return UnsafeStackPtr; 393 } 394 395 Value *SafeStack::getStackGuard(IRBuilder<> &IRB, Function &F) { 396 Value *StackGuardVar = nullptr; 397 if (TL) 398 StackGuardVar = TL->getIRStackGuard(IRB); 399 if (!StackGuardVar) 400 StackGuardVar = 401 F.getParent()->getOrInsertGlobal("__stack_chk_guard", StackPtrTy); 402 return IRB.CreateLoad(StackGuardVar, "StackGuard"); 403 } 404 405 void SafeStack::findInsts(Function &F, 406 SmallVectorImpl<AllocaInst *> &StaticAllocas, 407 SmallVectorImpl<AllocaInst *> &DynamicAllocas, 408 SmallVectorImpl<Argument *> &ByValArguments, 409 SmallVectorImpl<ReturnInst *> &Returns, 410 SmallVectorImpl<Instruction *> &StackRestorePoints) { 411 for (Instruction &I : instructions(&F)) { 412 if (auto AI = dyn_cast<AllocaInst>(&I)) { 413 ++NumAllocas; 414 415 uint64_t Size = getStaticAllocaAllocationSize(AI); 416 if (IsSafeStackAlloca(AI, Size)) 417 continue; 418 419 if (AI->isStaticAlloca()) { 420 ++NumUnsafeStaticAllocas; 421 StaticAllocas.push_back(AI); 422 } else { 423 ++NumUnsafeDynamicAllocas; 424 DynamicAllocas.push_back(AI); 425 } 426 } else if (auto RI = dyn_cast<ReturnInst>(&I)) { 427 Returns.push_back(RI); 428 } else if (auto CI = dyn_cast<CallInst>(&I)) { 429 // setjmps require stack restore. 430 if (CI->getCalledFunction() && CI->canReturnTwice()) 431 StackRestorePoints.push_back(CI); 432 } else if (auto LP = dyn_cast<LandingPadInst>(&I)) { 433 // Exception landing pads require stack restore. 434 StackRestorePoints.push_back(LP); 435 } else if (auto II = dyn_cast<IntrinsicInst>(&I)) { 436 if (II->getIntrinsicID() == Intrinsic::gcroot) 437 llvm::report_fatal_error( 438 "gcroot intrinsic not compatible with safestack attribute"); 439 } 440 } 441 for (Argument &Arg : F.args()) { 442 if (!Arg.hasByValAttr()) 443 continue; 444 uint64_t Size = 445 DL->getTypeStoreSize(Arg.getType()->getPointerElementType()); 446 if (IsSafeStackAlloca(&Arg, Size)) 447 continue; 448 449 ++NumUnsafeByValArguments; 450 ByValArguments.push_back(&Arg); 451 } 452 } 453 454 AllocaInst * 455 SafeStack::createStackRestorePoints(IRBuilder<> &IRB, Function &F, 456 ArrayRef<Instruction *> StackRestorePoints, 457 Value *StaticTop, bool NeedDynamicTop) { 458 assert(StaticTop && "The stack top isn't set."); 459 460 if (StackRestorePoints.empty()) 461 return nullptr; 462 463 // We need the current value of the shadow stack pointer to restore 464 // after longjmp or exception catching. 465 466 // FIXME: On some platforms this could be handled by the longjmp/exception 467 // runtime itself. 468 469 AllocaInst *DynamicTop = nullptr; 470 if (NeedDynamicTop) { 471 // If we also have dynamic alloca's, the stack pointer value changes 472 // throughout the function. For now we store it in an alloca. 473 DynamicTop = IRB.CreateAlloca(StackPtrTy, /*ArraySize=*/nullptr, 474 "unsafe_stack_dynamic_ptr"); 475 IRB.CreateStore(StaticTop, DynamicTop); 476 } 477 478 // Restore current stack pointer after longjmp/exception catch. 479 for (Instruction *I : StackRestorePoints) { 480 ++NumUnsafeStackRestorePoints; 481 482 IRB.SetInsertPoint(I->getNextNode()); 483 Value *CurrentTop = DynamicTop ? IRB.CreateLoad(DynamicTop) : StaticTop; 484 IRB.CreateStore(CurrentTop, UnsafeStackPtr); 485 } 486 487 return DynamicTop; 488 } 489 490 void SafeStack::checkStackGuard(IRBuilder<> &IRB, Function &F, ReturnInst &RI, 491 AllocaInst *StackGuardSlot, Value *StackGuard) { 492 Value *V = IRB.CreateLoad(StackGuardSlot); 493 Value *Cmp = IRB.CreateICmpNE(StackGuard, V); 494 495 auto SuccessProb = BranchProbabilityInfo::getBranchProbStackProtector(true); 496 auto FailureProb = BranchProbabilityInfo::getBranchProbStackProtector(false); 497 MDNode *Weights = MDBuilder(F.getContext()) 498 .createBranchWeights(SuccessProb.getNumerator(), 499 FailureProb.getNumerator()); 500 Instruction *CheckTerm = 501 SplitBlockAndInsertIfThen(Cmp, &RI, 502 /* Unreachable */ true, Weights); 503 IRBuilder<> IRBFail(CheckTerm); 504 // FIXME: respect -fsanitize-trap / -ftrap-function here? 505 Constant *StackChkFail = F.getParent()->getOrInsertFunction( 506 "__stack_chk_fail", IRB.getVoidTy(), nullptr); 507 IRBFail.CreateCall(StackChkFail, {}); 508 } 509 510 /// We explicitly compute and set the unsafe stack layout for all unsafe 511 /// static alloca instructions. We save the unsafe "base pointer" in the 512 /// prologue into a local variable and restore it in the epilogue. 513 Value *SafeStack::moveStaticAllocasToUnsafeStack( 514 IRBuilder<> &IRB, Function &F, ArrayRef<AllocaInst *> StaticAllocas, 515 ArrayRef<Argument *> ByValArguments, ArrayRef<ReturnInst *> Returns, 516 Instruction *BasePointer, AllocaInst *StackGuardSlot) { 517 if (StaticAllocas.empty() && ByValArguments.empty()) 518 return BasePointer; 519 520 DIBuilder DIB(*F.getParent()); 521 522 StackColoring SSC(F, StaticAllocas); 523 SSC.run(); 524 SSC.removeAllMarkers(); 525 526 // Unsafe stack always grows down. 527 StackLayout SSL(StackAlignment); 528 if (StackGuardSlot) { 529 Type *Ty = StackGuardSlot->getAllocatedType(); 530 unsigned Align = 531 std::max(DL->getPrefTypeAlignment(Ty), StackGuardSlot->getAlignment()); 532 SSL.addObject(StackGuardSlot, getStaticAllocaAllocationSize(StackGuardSlot), 533 Align, SSC.getFullLiveRange()); 534 } 535 536 for (Argument *Arg : ByValArguments) { 537 Type *Ty = Arg->getType()->getPointerElementType(); 538 uint64_t Size = DL->getTypeStoreSize(Ty); 539 if (Size == 0) 540 Size = 1; // Don't create zero-sized stack objects. 541 542 // Ensure the object is properly aligned. 543 unsigned Align = std::max((unsigned)DL->getPrefTypeAlignment(Ty), 544 Arg->getParamAlignment()); 545 SSL.addObject(Arg, Size, Align, SSC.getFullLiveRange()); 546 } 547 548 for (AllocaInst *AI : StaticAllocas) { 549 Type *Ty = AI->getAllocatedType(); 550 uint64_t Size = getStaticAllocaAllocationSize(AI); 551 if (Size == 0) 552 Size = 1; // Don't create zero-sized stack objects. 553 554 // Ensure the object is properly aligned. 555 unsigned Align = 556 std::max((unsigned)DL->getPrefTypeAlignment(Ty), AI->getAlignment()); 557 558 SSL.addObject(AI, Size, Align, SSC.getLiveRange(AI)); 559 } 560 561 SSL.computeLayout(); 562 unsigned FrameAlignment = SSL.getFrameAlignment(); 563 564 // FIXME: tell SSL that we start at a less-then-MaxAlignment aligned location 565 // (AlignmentSkew). 566 if (FrameAlignment > StackAlignment) { 567 // Re-align the base pointer according to the max requested alignment. 568 assert(isPowerOf2_32(FrameAlignment)); 569 IRB.SetInsertPoint(BasePointer->getNextNode()); 570 BasePointer = cast<Instruction>(IRB.CreateIntToPtr( 571 IRB.CreateAnd(IRB.CreatePtrToInt(BasePointer, IntPtrTy), 572 ConstantInt::get(IntPtrTy, ~uint64_t(FrameAlignment - 1))), 573 StackPtrTy)); 574 } 575 576 IRB.SetInsertPoint(BasePointer->getNextNode()); 577 578 if (StackGuardSlot) { 579 unsigned Offset = SSL.getObjectOffset(StackGuardSlot); 580 Value *Off = IRB.CreateGEP(BasePointer, // BasePointer is i8* 581 ConstantInt::get(Int32Ty, -Offset)); 582 Value *NewAI = 583 IRB.CreateBitCast(Off, StackGuardSlot->getType(), "StackGuardSlot"); 584 585 // Replace alloc with the new location. 586 StackGuardSlot->replaceAllUsesWith(NewAI); 587 StackGuardSlot->eraseFromParent(); 588 } 589 590 for (Argument *Arg : ByValArguments) { 591 unsigned Offset = SSL.getObjectOffset(Arg); 592 Type *Ty = Arg->getType()->getPointerElementType(); 593 594 uint64_t Size = DL->getTypeStoreSize(Ty); 595 if (Size == 0) 596 Size = 1; // Don't create zero-sized stack objects. 597 598 Value *Off = IRB.CreateGEP(BasePointer, // BasePointer is i8* 599 ConstantInt::get(Int32Ty, -Offset)); 600 Value *NewArg = IRB.CreateBitCast(Off, Arg->getType(), 601 Arg->getName() + ".unsafe-byval"); 602 603 // Replace alloc with the new location. 604 replaceDbgDeclare(Arg, BasePointer, BasePointer->getNextNode(), DIB, 605 /*Deref=*/true, -Offset); 606 Arg->replaceAllUsesWith(NewArg); 607 IRB.SetInsertPoint(cast<Instruction>(NewArg)->getNextNode()); 608 IRB.CreateMemCpy(Off, Arg, Size, Arg->getParamAlignment()); 609 } 610 611 // Allocate space for every unsafe static AllocaInst on the unsafe stack. 612 for (AllocaInst *AI : StaticAllocas) { 613 IRB.SetInsertPoint(AI); 614 unsigned Offset = SSL.getObjectOffset(AI); 615 616 uint64_t Size = getStaticAllocaAllocationSize(AI); 617 if (Size == 0) 618 Size = 1; // Don't create zero-sized stack objects. 619 620 replaceDbgDeclareForAlloca(AI, BasePointer, DIB, /*Deref=*/true, -Offset); 621 replaceDbgValueForAlloca(AI, BasePointer, DIB, -Offset); 622 623 // Replace uses of the alloca with the new location. 624 // Insert address calculation close to each use to work around PR27844. 625 std::string Name = std::string(AI->getName()) + ".unsafe"; 626 while (!AI->use_empty()) { 627 Use &U = *AI->use_begin(); 628 Instruction *User = cast<Instruction>(U.getUser()); 629 630 Instruction *InsertBefore; 631 if (auto *PHI = dyn_cast<PHINode>(User)) 632 InsertBefore = PHI->getIncomingBlock(U)->getTerminator(); 633 else 634 InsertBefore = User; 635 636 IRBuilder<> IRBUser(InsertBefore); 637 Value *Off = IRBUser.CreateGEP(BasePointer, // BasePointer is i8* 638 ConstantInt::get(Int32Ty, -Offset)); 639 Value *Replacement = IRBUser.CreateBitCast(Off, AI->getType(), Name); 640 641 if (auto *PHI = dyn_cast<PHINode>(User)) { 642 // PHI nodes may have multiple incoming edges from the same BB (why??), 643 // all must be updated at once with the same incoming value. 644 auto *BB = PHI->getIncomingBlock(U); 645 for (unsigned I = 0; I < PHI->getNumIncomingValues(); ++I) 646 if (PHI->getIncomingBlock(I) == BB) 647 PHI->setIncomingValue(I, Replacement); 648 } else { 649 U.set(Replacement); 650 } 651 } 652 653 AI->eraseFromParent(); 654 } 655 656 // Re-align BasePointer so that our callees would see it aligned as 657 // expected. 658 // FIXME: no need to update BasePointer in leaf functions. 659 unsigned FrameSize = alignTo(SSL.getFrameSize(), StackAlignment); 660 661 // Update shadow stack pointer in the function epilogue. 662 IRB.SetInsertPoint(BasePointer->getNextNode()); 663 664 Value *StaticTop = 665 IRB.CreateGEP(BasePointer, ConstantInt::get(Int32Ty, -FrameSize), 666 "unsafe_stack_static_top"); 667 IRB.CreateStore(StaticTop, UnsafeStackPtr); 668 return StaticTop; 669 } 670 671 void SafeStack::moveDynamicAllocasToUnsafeStack( 672 Function &F, Value *UnsafeStackPtr, AllocaInst *DynamicTop, 673 ArrayRef<AllocaInst *> DynamicAllocas) { 674 DIBuilder DIB(*F.getParent()); 675 676 for (AllocaInst *AI : DynamicAllocas) { 677 IRBuilder<> IRB(AI); 678 679 // Compute the new SP value (after AI). 680 Value *ArraySize = AI->getArraySize(); 681 if (ArraySize->getType() != IntPtrTy) 682 ArraySize = IRB.CreateIntCast(ArraySize, IntPtrTy, false); 683 684 Type *Ty = AI->getAllocatedType(); 685 uint64_t TySize = DL->getTypeAllocSize(Ty); 686 Value *Size = IRB.CreateMul(ArraySize, ConstantInt::get(IntPtrTy, TySize)); 687 688 Value *SP = IRB.CreatePtrToInt(IRB.CreateLoad(UnsafeStackPtr), IntPtrTy); 689 SP = IRB.CreateSub(SP, Size); 690 691 // Align the SP value to satisfy the AllocaInst, type and stack alignments. 692 unsigned Align = std::max( 693 std::max((unsigned)DL->getPrefTypeAlignment(Ty), AI->getAlignment()), 694 (unsigned)StackAlignment); 695 696 assert(isPowerOf2_32(Align)); 697 Value *NewTop = IRB.CreateIntToPtr( 698 IRB.CreateAnd(SP, ConstantInt::get(IntPtrTy, ~uint64_t(Align - 1))), 699 StackPtrTy); 700 701 // Save the stack pointer. 702 IRB.CreateStore(NewTop, UnsafeStackPtr); 703 if (DynamicTop) 704 IRB.CreateStore(NewTop, DynamicTop); 705 706 Value *NewAI = IRB.CreatePointerCast(NewTop, AI->getType()); 707 if (AI->hasName() && isa<Instruction>(NewAI)) 708 NewAI->takeName(AI); 709 710 replaceDbgDeclareForAlloca(AI, NewAI, DIB, /*Deref=*/true); 711 AI->replaceAllUsesWith(NewAI); 712 AI->eraseFromParent(); 713 } 714 715 if (!DynamicAllocas.empty()) { 716 // Now go through the instructions again, replacing stacksave/stackrestore. 717 for (inst_iterator It = inst_begin(&F), Ie = inst_end(&F); It != Ie;) { 718 Instruction *I = &*(It++); 719 auto II = dyn_cast<IntrinsicInst>(I); 720 if (!II) 721 continue; 722 723 if (II->getIntrinsicID() == Intrinsic::stacksave) { 724 IRBuilder<> IRB(II); 725 Instruction *LI = IRB.CreateLoad(UnsafeStackPtr); 726 LI->takeName(II); 727 II->replaceAllUsesWith(LI); 728 II->eraseFromParent(); 729 } else if (II->getIntrinsicID() == Intrinsic::stackrestore) { 730 IRBuilder<> IRB(II); 731 Instruction *SI = IRB.CreateStore(II->getArgOperand(0), UnsafeStackPtr); 732 SI->takeName(II); 733 assert(II->use_empty()); 734 II->eraseFromParent(); 735 } 736 } 737 } 738 } 739 740 bool SafeStack::runOnFunction(Function &F) { 741 DEBUG(dbgs() << "[SafeStack] Function: " << F.getName() << "\n"); 742 743 if (!F.hasFnAttribute(Attribute::SafeStack)) { 744 DEBUG(dbgs() << "[SafeStack] safestack is not requested" 745 " for this function\n"); 746 return false; 747 } 748 749 if (F.isDeclaration()) { 750 DEBUG(dbgs() << "[SafeStack] function definition" 751 " is not available\n"); 752 return false; 753 } 754 755 TL = TM ? TM->getSubtargetImpl(F)->getTargetLowering() : nullptr; 756 SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE(); 757 758 ++NumFunctions; 759 760 SmallVector<AllocaInst *, 16> StaticAllocas; 761 SmallVector<AllocaInst *, 4> DynamicAllocas; 762 SmallVector<Argument *, 4> ByValArguments; 763 SmallVector<ReturnInst *, 4> Returns; 764 765 // Collect all points where stack gets unwound and needs to be restored 766 // This is only necessary because the runtime (setjmp and unwind code) is 767 // not aware of the unsafe stack and won't unwind/restore it prorerly. 768 // To work around this problem without changing the runtime, we insert 769 // instrumentation to restore the unsafe stack pointer when necessary. 770 SmallVector<Instruction *, 4> StackRestorePoints; 771 772 // Find all static and dynamic alloca instructions that must be moved to the 773 // unsafe stack, all return instructions and stack restore points. 774 findInsts(F, StaticAllocas, DynamicAllocas, ByValArguments, Returns, 775 StackRestorePoints); 776 777 if (StaticAllocas.empty() && DynamicAllocas.empty() && 778 ByValArguments.empty() && StackRestorePoints.empty()) 779 return false; // Nothing to do in this function. 780 781 if (!StaticAllocas.empty() || !DynamicAllocas.empty() || 782 !ByValArguments.empty()) 783 ++NumUnsafeStackFunctions; // This function has the unsafe stack. 784 785 if (!StackRestorePoints.empty()) 786 ++NumUnsafeStackRestorePointsFunctions; 787 788 IRBuilder<> IRB(&F.front(), F.begin()->getFirstInsertionPt()); 789 UnsafeStackPtr = getOrCreateUnsafeStackPtr(IRB, F); 790 791 // Load the current stack pointer (we'll also use it as a base pointer). 792 // FIXME: use a dedicated register for it ? 793 Instruction *BasePointer = 794 IRB.CreateLoad(UnsafeStackPtr, false, "unsafe_stack_ptr"); 795 assert(BasePointer->getType() == StackPtrTy); 796 797 AllocaInst *StackGuardSlot = nullptr; 798 // FIXME: implement weaker forms of stack protector. 799 if (F.hasFnAttribute(Attribute::StackProtect) || 800 F.hasFnAttribute(Attribute::StackProtectStrong) || 801 F.hasFnAttribute(Attribute::StackProtectReq)) { 802 Value *StackGuard = getStackGuard(IRB, F); 803 StackGuardSlot = IRB.CreateAlloca(StackPtrTy, nullptr); 804 IRB.CreateStore(StackGuard, StackGuardSlot); 805 806 for (ReturnInst *RI : Returns) { 807 IRBuilder<> IRBRet(RI); 808 checkStackGuard(IRBRet, F, *RI, StackGuardSlot, StackGuard); 809 } 810 } 811 812 // The top of the unsafe stack after all unsafe static allocas are 813 // allocated. 814 Value *StaticTop = 815 moveStaticAllocasToUnsafeStack(IRB, F, StaticAllocas, ByValArguments, 816 Returns, BasePointer, StackGuardSlot); 817 818 // Safe stack object that stores the current unsafe stack top. It is updated 819 // as unsafe dynamic (non-constant-sized) allocas are allocated and freed. 820 // This is only needed if we need to restore stack pointer after longjmp 821 // or exceptions, and we have dynamic allocations. 822 // FIXME: a better alternative might be to store the unsafe stack pointer 823 // before setjmp / invoke instructions. 824 AllocaInst *DynamicTop = createStackRestorePoints( 825 IRB, F, StackRestorePoints, StaticTop, !DynamicAllocas.empty()); 826 827 // Handle dynamic allocas. 828 moveDynamicAllocasToUnsafeStack(F, UnsafeStackPtr, DynamicTop, 829 DynamicAllocas); 830 831 // Restore the unsafe stack pointer before each return. 832 for (ReturnInst *RI : Returns) { 833 IRB.SetInsertPoint(RI); 834 IRB.CreateStore(BasePointer, UnsafeStackPtr); 835 } 836 837 DEBUG(dbgs() << "[SafeStack] safestack applied\n"); 838 return true; 839 } 840 841 } // anonymous namespace 842 843 char SafeStack::ID = 0; 844 INITIALIZE_TM_PASS_BEGIN(SafeStack, "safe-stack", 845 "Safe Stack instrumentation pass", false, false) 846 INITIALIZE_TM_PASS_END(SafeStack, "safe-stack", 847 "Safe Stack instrumentation pass", false, false) 848 849 FunctionPass *llvm::createSafeStackPass(const llvm::TargetMachine *TM) { 850 return new SafeStack(TM); 851 } 852