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