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