StackProtector.cpp revision 62406fdc6f199e4e7df60830be45de4da97b34c7
1//===-- StackProtector.cpp - Stack Protector 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 inserts stack protectors into functions which need them. A variable 11// with a random value in it is stored onto the stack before the local variables 12// are allocated. Upon exiting the block, the stored value is checked. If it's 13// changed, then there was some sort of violation and the program aborts. 14// 15//===----------------------------------------------------------------------===// 16 17#define DEBUG_TYPE "stack-protector" 18#include "llvm/CodeGen/StackProtector.h" 19#include "llvm/CodeGen/Analysis.h" 20#include "llvm/CodeGen/Passes.h" 21#include "llvm/ADT/SmallPtrSet.h" 22#include "llvm/ADT/Statistic.h" 23#include "llvm/Analysis/Dominators.h" 24#include "llvm/Analysis/ValueTracking.h" 25#include "llvm/IR/Attributes.h" 26#include "llvm/IR/Constants.h" 27#include "llvm/IR/DataLayout.h" 28#include "llvm/IR/DerivedTypes.h" 29#include "llvm/IR/Function.h" 30#include "llvm/IR/GlobalValue.h" 31#include "llvm/IR/GlobalVariable.h" 32#include "llvm/IR/IRBuilder.h" 33#include "llvm/IR/Instructions.h" 34#include "llvm/IR/IntrinsicInst.h" 35#include "llvm/IR/Intrinsics.h" 36#include "llvm/IR/Module.h" 37#include "llvm/Support/CommandLine.h" 38#include <cstdlib> 39using namespace llvm; 40 41STATISTIC(NumFunProtected, "Number of functions protected"); 42STATISTIC(NumAddrTaken, "Number of local variables that have their address" 43 " taken."); 44 45static cl::opt<bool> EnableSelectionDAGSP("enable-selectiondag-sp", 46 cl::init(true), cl::Hidden); 47 48char StackProtector::ID = 0; 49INITIALIZE_PASS(StackProtector, "stack-protector", "Insert stack protectors", 50 false, true) 51 52FunctionPass *llvm::createStackProtectorPass(const TargetMachine *TM) { 53 return new StackProtector(TM); 54} 55 56StackProtector::SSPLayoutKind 57StackProtector::getSSPLayout(const AllocaInst *AI) const { 58 return AI ? Layout.lookup(AI) : SSPLK_None; 59} 60 61bool StackProtector::runOnFunction(Function &Fn) { 62 F = &Fn; 63 M = F->getParent(); 64 DT = getAnalysisIfAvailable<DominatorTree>(); 65 TLI = TM->getTargetLowering(); 66 67 if (!RequiresStackProtector()) 68 return false; 69 70 Attribute Attr = Fn.getAttributes().getAttribute( 71 AttributeSet::FunctionIndex, "stack-protector-buffer-size"); 72 if (Attr.isStringAttribute()) 73 Attr.getValueAsString().getAsInteger(10, SSPBufferSize); 74 75 ++NumFunProtected; 76 return InsertStackProtectors(); 77} 78 79/// \param [out] IsLarge is set to true if a protectable array is found and 80/// it is "large" ( >= ssp-buffer-size). In the case of a structure with 81/// multiple arrays, this gets set if any of them is large. 82bool StackProtector::ContainsProtectableArray(Type *Ty, bool &IsLarge, 83 bool Strong, 84 bool InStruct) const { 85 if (!Ty) 86 return false; 87 if (ArrayType *AT = dyn_cast<ArrayType>(Ty)) { 88 if (!AT->getElementType()->isIntegerTy(8)) { 89 // If we're on a non-Darwin platform or we're inside of a structure, don't 90 // add stack protectors unless the array is a character array. 91 // However, in strong mode any array, regardless of type and size, 92 // triggers a protector. 93 if (!Strong && (InStruct || !Trip.isOSDarwin())) 94 return false; 95 } 96 97 // If an array has more than SSPBufferSize bytes of allocated space, then we 98 // emit stack protectors. 99 if (SSPBufferSize <= TLI->getDataLayout()->getTypeAllocSize(AT)) { 100 IsLarge = true; 101 return true; 102 } 103 104 if (Strong) 105 // Require a protector for all arrays in strong mode 106 return true; 107 } 108 109 const StructType *ST = dyn_cast<StructType>(Ty); 110 if (!ST) 111 return false; 112 113 bool NeedsProtector = false; 114 for (StructType::element_iterator I = ST->element_begin(), 115 E = ST->element_end(); 116 I != E; ++I) 117 if (ContainsProtectableArray(*I, IsLarge, Strong, true)) { 118 // If the element is a protectable array and is large (>= SSPBufferSize) 119 // then we are done. If the protectable array is not large, then 120 // keep looking in case a subsequent element is a large array. 121 if (IsLarge) 122 return true; 123 NeedsProtector = true; 124 } 125 126 return NeedsProtector; 127} 128 129bool StackProtector::HasAddressTaken(const Instruction *AI) { 130 for (Value::const_use_iterator UI = AI->use_begin(), UE = AI->use_end(); 131 UI != UE; ++UI) { 132 const User *U = *UI; 133 if (const StoreInst *SI = dyn_cast<StoreInst>(U)) { 134 if (AI == SI->getValueOperand()) 135 return true; 136 } else if (const PtrToIntInst *SI = dyn_cast<PtrToIntInst>(U)) { 137 if (AI == SI->getOperand(0)) 138 return true; 139 } else if (isa<CallInst>(U)) { 140 return true; 141 } else if (isa<InvokeInst>(U)) { 142 return true; 143 } else if (const SelectInst *SI = dyn_cast<SelectInst>(U)) { 144 if (HasAddressTaken(SI)) 145 return true; 146 } else if (const PHINode *PN = dyn_cast<PHINode>(U)) { 147 // Keep track of what PHI nodes we have already visited to ensure 148 // they are only visited once. 149 if (VisitedPHIs.insert(PN)) 150 if (HasAddressTaken(PN)) 151 return true; 152 } else if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(U)) { 153 if (HasAddressTaken(GEP)) 154 return true; 155 } else if (const BitCastInst *BI = dyn_cast<BitCastInst>(U)) { 156 if (HasAddressTaken(BI)) 157 return true; 158 } 159 } 160 return false; 161} 162 163/// \brief Check whether or not this function needs a stack protector based 164/// upon the stack protector level. 165/// 166/// We use two heuristics: a standard (ssp) and strong (sspstrong). 167/// The standard heuristic which will add a guard variable to functions that 168/// call alloca with a either a variable size or a size >= SSPBufferSize, 169/// functions with character buffers larger than SSPBufferSize, and functions 170/// with aggregates containing character buffers larger than SSPBufferSize. The 171/// strong heuristic will add a guard variables to functions that call alloca 172/// regardless of size, functions with any buffer regardless of type and size, 173/// functions with aggregates that contain any buffer regardless of type and 174/// size, and functions that contain stack-based variables that have had their 175/// address taken. 176bool StackProtector::RequiresStackProtector() { 177 bool Strong = false; 178 bool NeedsProtector = false; 179 if (F->getAttributes().hasAttribute(AttributeSet::FunctionIndex, 180 Attribute::StackProtectReq)) { 181 NeedsProtector = true; 182 Strong = true; // Use the same heuristic as strong to determine SSPLayout 183 } else if (F->getAttributes().hasAttribute(AttributeSet::FunctionIndex, 184 Attribute::StackProtectStrong)) 185 Strong = true; 186 else if (!F->getAttributes().hasAttribute(AttributeSet::FunctionIndex, 187 Attribute::StackProtect)) 188 return false; 189 190 for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) { 191 BasicBlock *BB = I; 192 193 for (BasicBlock::iterator II = BB->begin(), IE = BB->end(); II != IE; 194 ++II) { 195 if (AllocaInst *AI = dyn_cast<AllocaInst>(II)) { 196 if (AI->isArrayAllocation()) { 197 // SSP-Strong: Enable protectors for any call to alloca, regardless 198 // of size. 199 if (Strong) 200 return true; 201 202 if (const ConstantInt *CI = 203 dyn_cast<ConstantInt>(AI->getArraySize())) { 204 if (CI->getLimitedValue(SSPBufferSize) >= SSPBufferSize) { 205 // A call to alloca with size >= SSPBufferSize requires 206 // stack protectors. 207 Layout.insert(std::make_pair(AI, SSPLK_LargeArray)); 208 NeedsProtector = true; 209 } else if (Strong) { 210 // Require protectors for all alloca calls in strong mode. 211 Layout.insert(std::make_pair(AI, SSPLK_SmallArray)); 212 NeedsProtector = true; 213 } 214 } else { 215 // A call to alloca with a variable size requires protectors. 216 Layout.insert(std::make_pair(AI, SSPLK_LargeArray)); 217 NeedsProtector = true; 218 } 219 continue; 220 } 221 222 bool IsLarge = false; 223 if (ContainsProtectableArray(AI->getAllocatedType(), IsLarge, Strong)) { 224 Layout.insert(std::make_pair(AI, IsLarge ? SSPLK_LargeArray 225 : SSPLK_SmallArray)); 226 NeedsProtector = true; 227 continue; 228 } 229 230 if (Strong && HasAddressTaken(AI)) { 231 ++NumAddrTaken; 232 Layout.insert(std::make_pair(AI, SSPLK_AddrOf)); 233 NeedsProtector = true; 234 } 235 } 236 } 237 } 238 239 return NeedsProtector; 240} 241 242static bool InstructionWillNotHaveChain(const Instruction *I) { 243 return !I->mayHaveSideEffects() && !I->mayReadFromMemory() && 244 isSafeToSpeculativelyExecute(I); 245} 246 247/// Identify if RI has a previous instruction in the "Tail Position" and return 248/// it. Otherwise return 0. 249/// 250/// This is based off of the code in llvm::isInTailCallPosition. The difference 251/// is that it inverts the first part of llvm::isInTailCallPosition since 252/// isInTailCallPosition is checking if a call is in a tail call position, and 253/// we are searching for an unknown tail call that might be in the tail call 254/// position. Once we find the call though, the code uses the same refactored 255/// code, returnTypeIsEligibleForTailCall. 256static CallInst *FindPotentialTailCall(BasicBlock *BB, ReturnInst *RI, 257 const TargetLoweringBase *TLI) { 258 // Establish a reasonable upper bound on the maximum amount of instructions we 259 // will look through to find a tail call. 260 unsigned SearchCounter = 0; 261 const unsigned MaxSearch = 4; 262 bool NoInterposingChain = true; 263 264 for (BasicBlock::reverse_iterator I = llvm::next(BB->rbegin()), 265 E = BB->rend(); 266 I != E && SearchCounter < MaxSearch; ++I) { 267 Instruction *Inst = &*I; 268 269 // Skip over debug intrinsics and do not allow them to affect our MaxSearch 270 // counter. 271 if (isa<DbgInfoIntrinsic>(Inst)) 272 continue; 273 274 // If we find a call and the following conditions are satisifed, then we 275 // have found a tail call that satisfies at least the target independent 276 // requirements of a tail call: 277 // 278 // 1. The call site has the tail marker. 279 // 280 // 2. The call site either will not cause the creation of a chain or if a 281 // chain is necessary there are no instructions in between the callsite and 282 // the call which would create an interposing chain. 283 // 284 // 3. The return type of the function does not impede tail call 285 // optimization. 286 if (CallInst *CI = dyn_cast<CallInst>(Inst)) { 287 if (CI->isTailCall() && 288 (InstructionWillNotHaveChain(CI) || NoInterposingChain) && 289 returnTypeIsEligibleForTailCall(BB->getParent(), CI, RI, *TLI)) 290 return CI; 291 } 292 293 // If we did not find a call see if we have an instruction that may create 294 // an interposing chain. 295 NoInterposingChain = 296 NoInterposingChain && InstructionWillNotHaveChain(Inst); 297 298 // Increment max search. 299 SearchCounter++; 300 } 301 302 return 0; 303} 304 305/// Insert code into the entry block that stores the __stack_chk_guard 306/// variable onto the stack: 307/// 308/// entry: 309/// StackGuardSlot = alloca i8* 310/// StackGuard = load __stack_chk_guard 311/// call void @llvm.stackprotect.create(StackGuard, StackGuardSlot) 312/// 313/// Returns true if the platform/triple supports the stackprotectorcreate pseudo 314/// node. 315static bool CreatePrologue(Function *F, Module *M, ReturnInst *RI, 316 const TargetLoweringBase *TLI, const Triple &Trip, 317 AllocaInst *&AI, Value *&StackGuardVar) { 318 bool SupportsSelectionDAGSP = false; 319 PointerType *PtrTy = Type::getInt8PtrTy(RI->getContext()); 320 unsigned AddressSpace, Offset; 321 if (TLI->getStackCookieLocation(AddressSpace, Offset)) { 322 Constant *OffsetVal = 323 ConstantInt::get(Type::getInt32Ty(RI->getContext()), Offset); 324 325 StackGuardVar = ConstantExpr::getIntToPtr( 326 OffsetVal, PointerType::get(PtrTy, AddressSpace)); 327 } else if (Trip.getOS() == llvm::Triple::OpenBSD) { 328 StackGuardVar = M->getOrInsertGlobal("__guard_local", PtrTy); 329 cast<GlobalValue>(StackGuardVar) 330 ->setVisibility(GlobalValue::HiddenVisibility); 331 } else { 332 SupportsSelectionDAGSP = true; 333 StackGuardVar = M->getOrInsertGlobal("__stack_chk_guard", PtrTy); 334 } 335 336 IRBuilder<> B(&F->getEntryBlock().front()); 337 AI = B.CreateAlloca(PtrTy, 0, "StackGuardSlot"); 338 LoadInst *LI = B.CreateLoad(StackGuardVar, "StackGuard"); 339 B.CreateCall2(Intrinsic::getDeclaration(M, Intrinsic::stackprotector), LI, 340 AI); 341 342 return SupportsSelectionDAGSP; 343} 344 345/// InsertStackProtectors - Insert code into the prologue and epilogue of the 346/// function. 347/// 348/// - The prologue code loads and stores the stack guard onto the stack. 349/// - The epilogue checks the value stored in the prologue against the original 350/// value. It calls __stack_chk_fail if they differ. 351bool StackProtector::InsertStackProtectors() { 352 bool HasPrologue = false; 353 bool SupportsSelectionDAGSP = 354 EnableSelectionDAGSP && !TM->Options.EnableFastISel; 355 AllocaInst *AI = 0; // Place on stack that stores the stack guard. 356 Value *StackGuardVar = 0; // The stack guard variable. 357 358 for (Function::iterator I = F->begin(), E = F->end(); I != E;) { 359 BasicBlock *BB = I++; 360 ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator()); 361 if (!RI) 362 continue; 363 364 if (!HasPrologue) { 365 HasPrologue = true; 366 SupportsSelectionDAGSP &= 367 CreatePrologue(F, M, RI, TLI, Trip, AI, StackGuardVar); 368 } 369 370 if (SupportsSelectionDAGSP) { 371 // Since we have a potential tail call, insert the special stack check 372 // intrinsic. 373 Instruction *InsertionPt = 0; 374 if (CallInst *CI = FindPotentialTailCall(BB, RI, TLI)) { 375 InsertionPt = CI; 376 } else { 377 InsertionPt = RI; 378 // At this point we know that BB has a return statement so it *DOES* 379 // have a terminator. 380 assert(InsertionPt != 0 && "BB must have a terminator instruction at " 381 "this point."); 382 } 383 384 Function *Intrinsic = 385 Intrinsic::getDeclaration(M, Intrinsic::stackprotectorcheck); 386 CallInst::Create(Intrinsic, StackGuardVar, "", InsertionPt); 387 388 } else { 389 // If we do not support SelectionDAG based tail calls, generate IR level 390 // tail calls. 391 // 392 // For each block with a return instruction, convert this: 393 // 394 // return: 395 // ... 396 // ret ... 397 // 398 // into this: 399 // 400 // return: 401 // ... 402 // %1 = load __stack_chk_guard 403 // %2 = load StackGuardSlot 404 // %3 = cmp i1 %1, %2 405 // br i1 %3, label %SP_return, label %CallStackCheckFailBlk 406 // 407 // SP_return: 408 // ret ... 409 // 410 // CallStackCheckFailBlk: 411 // call void @__stack_chk_fail() 412 // unreachable 413 414 // Create the FailBB. We duplicate the BB every time since the MI tail 415 // merge pass will merge together all of the various BB into one including 416 // fail BB generated by the stack protector pseudo instruction. 417 BasicBlock *FailBB = CreateFailBB(); 418 419 // Split the basic block before the return instruction. 420 BasicBlock *NewBB = BB->splitBasicBlock(RI, "SP_return"); 421 422 // Update the dominator tree if we need to. 423 if (DT && DT->isReachableFromEntry(BB)) { 424 DT->addNewBlock(NewBB, BB); 425 DT->addNewBlock(FailBB, BB); 426 } 427 428 // Remove default branch instruction to the new BB. 429 BB->getTerminator()->eraseFromParent(); 430 431 // Move the newly created basic block to the point right after the old 432 // basic block so that it's in the "fall through" position. 433 NewBB->moveAfter(BB); 434 435 // Generate the stack protector instructions in the old basic block. 436 IRBuilder<> B(BB); 437 LoadInst *LI1 = B.CreateLoad(StackGuardVar); 438 LoadInst *LI2 = B.CreateLoad(AI); 439 Value *Cmp = B.CreateICmpEQ(LI1, LI2); 440 B.CreateCondBr(Cmp, NewBB, FailBB); 441 } 442 } 443 444 // Return if we didn't modify any basic blocks. I.e., there are no return 445 // statements in the function. 446 if (!HasPrologue) 447 return false; 448 449 return true; 450} 451 452/// CreateFailBB - Create a basic block to jump to when the stack protector 453/// check fails. 454BasicBlock *StackProtector::CreateFailBB() { 455 LLVMContext &Context = F->getContext(); 456 BasicBlock *FailBB = BasicBlock::Create(Context, "CallStackCheckFailBlk", F); 457 IRBuilder<> B(FailBB); 458 if (Trip.getOS() == llvm::Triple::OpenBSD) { 459 Constant *StackChkFail = M->getOrInsertFunction( 460 "__stack_smash_handler", Type::getVoidTy(Context), 461 Type::getInt8PtrTy(Context), NULL); 462 463 B.CreateCall(StackChkFail, B.CreateGlobalStringPtr(F->getName(), "SSH")); 464 } else { 465 Constant *StackChkFail = M->getOrInsertFunction( 466 "__stack_chk_fail", Type::getVoidTy(Context), NULL); 467 B.CreateCall(StackChkFail); 468 } 469 B.CreateUnreachable(); 470 return FailBB; 471} 472