ShadowStackGC.cpp revision dce4a407a24b04eebc6a376f8e62b41aaa7b071f 
1//===-- ShadowStackGC.cpp - GC support for uncooperative targets ----------===//
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 file implements lowering for the llvm.gc* intrinsics for targets that do
11// not natively support them (which includes the C backend). Note that the code
12// generated is not quite as efficient as algorithms which generate stack maps
13// to identify roots.
14//
15// This pass implements the code transformation described in this paper:
16//   "Accurate Garbage Collection in an Uncooperative Environment"
17//   Fergus Henderson, ISMM, 2002
18//
19// In runtime/GC/SemiSpace.cpp is a prototype runtime which is compatible with
20// ShadowStackGC.
21//
22// In order to support this particular transformation, all stack roots are
23// coallocated in the stack. This allows a fully target-independent stack map
24// while introducing only minor runtime overhead.
25//
26//===----------------------------------------------------------------------===//
27
28#include "llvm/CodeGen/GCs.h"
29#include "llvm/ADT/StringExtras.h"
30#include "llvm/CodeGen/GCStrategy.h"
31#include "llvm/IR/CallSite.h"
32#include "llvm/IR/IRBuilder.h"
33#include "llvm/IR/IntrinsicInst.h"
34#include "llvm/IR/Module.h"
35
36using namespace llvm;
37
38#define DEBUG_TYPE "shadowstackgc"
39
40namespace {
41
42  class ShadowStackGC : public GCStrategy {
43    /// RootChain - This is the global linked-list that contains the chain of GC
44    /// roots.
45    GlobalVariable *Head;
46
47    /// StackEntryTy - Abstract type of a link in the shadow stack.
48    ///
49    StructType *StackEntryTy;
50    StructType *FrameMapTy;
51
52    /// Roots - GC roots in the current function. Each is a pair of the
53    /// intrinsic call and its corresponding alloca.
54    std::vector<std::pair<CallInst*,AllocaInst*> > Roots;
55
56  public:
57    ShadowStackGC();
58
59    bool initializeCustomLowering(Module &M) override;
60    bool performCustomLowering(Function &F) override;
61
62  private:
63    bool IsNullValue(Value *V);
64    Constant *GetFrameMap(Function &F);
65    Type* GetConcreteStackEntryType(Function &F);
66    void CollectRoots(Function &F);
67    static GetElementPtrInst *CreateGEP(LLVMContext &Context,
68                                        IRBuilder<> &B, Value *BasePtr,
69                                        int Idx1, const char *Name);
70    static GetElementPtrInst *CreateGEP(LLVMContext &Context,
71                                        IRBuilder<> &B, Value *BasePtr,
72                                        int Idx1, int Idx2, const char *Name);
73  };
74
75}
76
77static GCRegistry::Add<ShadowStackGC>
78X("shadow-stack", "Very portable GC for uncooperative code generators");
79
80namespace {
81  /// EscapeEnumerator - This is a little algorithm to find all escape points
82  /// from a function so that "finally"-style code can be inserted. In addition
83  /// to finding the existing return and unwind instructions, it also (if
84  /// necessary) transforms any call instructions into invokes and sends them to
85  /// a landing pad.
86  ///
87  /// It's wrapped up in a state machine using the same transform C# uses for
88  /// 'yield return' enumerators, This transform allows it to be non-allocating.
89  class EscapeEnumerator {
90    Function &F;
91    const char *CleanupBBName;
92
93    // State.
94    int State;
95    Function::iterator StateBB, StateE;
96    IRBuilder<> Builder;
97
98  public:
99    EscapeEnumerator(Function &F, const char *N = "cleanup")
100      : F(F), CleanupBBName(N), State(0), Builder(F.getContext()) {}
101
102    IRBuilder<> *Next() {
103      switch (State) {
104      default:
105        return nullptr;
106
107      case 0:
108        StateBB = F.begin();
109        StateE = F.end();
110        State = 1;
111
112      case 1:
113        // Find all 'return', 'resume', and 'unwind' instructions.
114        while (StateBB != StateE) {
115          BasicBlock *CurBB = StateBB++;
116
117          // Branches and invokes do not escape, only unwind, resume, and return
118          // do.
119          TerminatorInst *TI = CurBB->getTerminator();
120          if (!isa<ReturnInst>(TI) && !isa<ResumeInst>(TI))
121            continue;
122
123          Builder.SetInsertPoint(TI->getParent(), TI);
124          return &Builder;
125        }
126
127        State = 2;
128
129        // Find all 'call' instructions.
130        SmallVector<Instruction*,16> Calls;
131        for (Function::iterator BB = F.begin(),
132                                E = F.end(); BB != E; ++BB)
133          for (BasicBlock::iterator II = BB->begin(),
134                                    EE = BB->end(); II != EE; ++II)
135            if (CallInst *CI = dyn_cast<CallInst>(II))
136              if (!CI->getCalledFunction() ||
137                  !CI->getCalledFunction()->getIntrinsicID())
138                Calls.push_back(CI);
139
140        if (Calls.empty())
141          return nullptr;
142
143        // Create a cleanup block.
144        LLVMContext &C = F.getContext();
145        BasicBlock *CleanupBB = BasicBlock::Create(C, CleanupBBName, &F);
146        Type *ExnTy = StructType::get(Type::getInt8PtrTy(C),
147                                      Type::getInt32Ty(C), NULL);
148        Constant *PersFn =
149          F.getParent()->
150          getOrInsertFunction("__gcc_personality_v0",
151                              FunctionType::get(Type::getInt32Ty(C), true));
152        LandingPadInst *LPad = LandingPadInst::Create(ExnTy, PersFn, 1,
153                                                      "cleanup.lpad",
154                                                      CleanupBB);
155        LPad->setCleanup(true);
156        ResumeInst *RI = ResumeInst::Create(LPad, CleanupBB);
157
158        // Transform the 'call' instructions into 'invoke's branching to the
159        // cleanup block. Go in reverse order to make prettier BB names.
160        SmallVector<Value*,16> Args;
161        for (unsigned I = Calls.size(); I != 0; ) {
162          CallInst *CI = cast<CallInst>(Calls[--I]);
163
164          // Split the basic block containing the function call.
165          BasicBlock *CallBB = CI->getParent();
166          BasicBlock *NewBB =
167            CallBB->splitBasicBlock(CI, CallBB->getName() + ".cont");
168
169          // Remove the unconditional branch inserted at the end of CallBB.
170          CallBB->getInstList().pop_back();
171          NewBB->getInstList().remove(CI);
172
173          // Create a new invoke instruction.
174          Args.clear();
175          CallSite CS(CI);
176          Args.append(CS.arg_begin(), CS.arg_end());
177
178          InvokeInst *II = InvokeInst::Create(CI->getCalledValue(),
179                                              NewBB, CleanupBB,
180                                              Args, CI->getName(), CallBB);
181          II->setCallingConv(CI->getCallingConv());
182          II->setAttributes(CI->getAttributes());
183          CI->replaceAllUsesWith(II);
184          delete CI;
185        }
186
187        Builder.SetInsertPoint(RI->getParent(), RI);
188        return &Builder;
189      }
190    }
191  };
192}
193
194// -----------------------------------------------------------------------------
195
196void llvm::linkShadowStackGC() { }
197
198ShadowStackGC::ShadowStackGC() : Head(nullptr), StackEntryTy(nullptr) {
199  InitRoots = true;
200  CustomRoots = true;
201}
202
203Constant *ShadowStackGC::GetFrameMap(Function &F) {
204  // doInitialization creates the abstract type of this value.
205  Type *VoidPtr = Type::getInt8PtrTy(F.getContext());
206
207  // Truncate the ShadowStackDescriptor if some metadata is null.
208  unsigned NumMeta = 0;
209  SmallVector<Constant*, 16> Metadata;
210  for (unsigned I = 0; I != Roots.size(); ++I) {
211    Constant *C = cast<Constant>(Roots[I].first->getArgOperand(1));
212    if (!C->isNullValue())
213      NumMeta = I + 1;
214    Metadata.push_back(ConstantExpr::getBitCast(C, VoidPtr));
215  }
216  Metadata.resize(NumMeta);
217
218  Type *Int32Ty = Type::getInt32Ty(F.getContext());
219
220  Constant *BaseElts[] = {
221    ConstantInt::get(Int32Ty, Roots.size(), false),
222    ConstantInt::get(Int32Ty, NumMeta, false),
223  };
224
225  Constant *DescriptorElts[] = {
226    ConstantStruct::get(FrameMapTy, BaseElts),
227    ConstantArray::get(ArrayType::get(VoidPtr, NumMeta), Metadata)
228  };
229
230  Type *EltTys[] = { DescriptorElts[0]->getType(),DescriptorElts[1]->getType()};
231  StructType *STy = StructType::create(EltTys, "gc_map."+utostr(NumMeta));
232
233  Constant *FrameMap = ConstantStruct::get(STy, DescriptorElts);
234
235  // FIXME: Is this actually dangerous as WritingAnLLVMPass.html claims? Seems
236  //        that, short of multithreaded LLVM, it should be safe; all that is
237  //        necessary is that a simple Module::iterator loop not be invalidated.
238  //        Appending to the GlobalVariable list is safe in that sense.
239  //
240  //        All of the output passes emit globals last. The ExecutionEngine
241  //        explicitly supports adding globals to the module after
242  //        initialization.
243  //
244  //        Still, if it isn't deemed acceptable, then this transformation needs
245  //        to be a ModulePass (which means it cannot be in the 'llc' pipeline
246  //        (which uses a FunctionPassManager (which segfaults (not asserts) if
247  //        provided a ModulePass))).
248  Constant *GV = new GlobalVariable(*F.getParent(), FrameMap->getType(), true,
249                                    GlobalVariable::InternalLinkage,
250                                    FrameMap, "__gc_" + F.getName());
251
252  Constant *GEPIndices[2] = {
253                          ConstantInt::get(Type::getInt32Ty(F.getContext()), 0),
254                          ConstantInt::get(Type::getInt32Ty(F.getContext()), 0)
255                          };
256  return ConstantExpr::getGetElementPtr(GV, GEPIndices);
257}
258
259Type* ShadowStackGC::GetConcreteStackEntryType(Function &F) {
260  // doInitialization creates the generic version of this type.
261  std::vector<Type*> EltTys;
262  EltTys.push_back(StackEntryTy);
263  for (size_t I = 0; I != Roots.size(); I++)
264    EltTys.push_back(Roots[I].second->getAllocatedType());
265
266  return StructType::create(EltTys, "gc_stackentry."+F.getName().str());
267}
268
269/// doInitialization - If this module uses the GC intrinsics, find them now. If
270/// not, exit fast.
271bool ShadowStackGC::initializeCustomLowering(Module &M) {
272  // struct FrameMap {
273  //   int32_t NumRoots; // Number of roots in stack frame.
274  //   int32_t NumMeta;  // Number of metadata descriptors. May be < NumRoots.
275  //   void *Meta[];     // May be absent for roots without metadata.
276  // };
277  std::vector<Type*> EltTys;
278  // 32 bits is ok up to a 32GB stack frame. :)
279  EltTys.push_back(Type::getInt32Ty(M.getContext()));
280  // Specifies length of variable length array.
281  EltTys.push_back(Type::getInt32Ty(M.getContext()));
282  FrameMapTy = StructType::create(EltTys, "gc_map");
283  PointerType *FrameMapPtrTy = PointerType::getUnqual(FrameMapTy);
284
285  // struct StackEntry {
286  //   ShadowStackEntry *Next; // Caller's stack entry.
287  //   FrameMap *Map;          // Pointer to constant FrameMap.
288  //   void *Roots[];          // Stack roots (in-place array, so we pretend).
289  // };
290
291  StackEntryTy = StructType::create(M.getContext(), "gc_stackentry");
292
293  EltTys.clear();
294  EltTys.push_back(PointerType::getUnqual(StackEntryTy));
295  EltTys.push_back(FrameMapPtrTy);
296  StackEntryTy->setBody(EltTys);
297  PointerType *StackEntryPtrTy = PointerType::getUnqual(StackEntryTy);
298
299  // Get the root chain if it already exists.
300  Head = M.getGlobalVariable("llvm_gc_root_chain");
301  if (!Head) {
302    // If the root chain does not exist, insert a new one with linkonce
303    // linkage!
304    Head = new GlobalVariable(M, StackEntryPtrTy, false,
305                              GlobalValue::LinkOnceAnyLinkage,
306                              Constant::getNullValue(StackEntryPtrTy),
307                              "llvm_gc_root_chain");
308  } else if (Head->hasExternalLinkage() && Head->isDeclaration()) {
309    Head->setInitializer(Constant::getNullValue(StackEntryPtrTy));
310    Head->setLinkage(GlobalValue::LinkOnceAnyLinkage);
311  }
312
313  return true;
314}
315
316bool ShadowStackGC::IsNullValue(Value *V) {
317  if (Constant *C = dyn_cast<Constant>(V))
318    return C->isNullValue();
319  return false;
320}
321
322void ShadowStackGC::CollectRoots(Function &F) {
323  // FIXME: Account for original alignment. Could fragment the root array.
324  //   Approach 1: Null initialize empty slots at runtime. Yuck.
325  //   Approach 2: Emit a map of the array instead of just a count.
326
327  assert(Roots.empty() && "Not cleaned up?");
328
329  SmallVector<std::pair<CallInst*, AllocaInst*>, 16> MetaRoots;
330
331  for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
332    for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E;)
333      if (IntrinsicInst *CI = dyn_cast<IntrinsicInst>(II++))
334        if (Function *F = CI->getCalledFunction())
335          if (F->getIntrinsicID() == Intrinsic::gcroot) {
336            std::pair<CallInst*, AllocaInst*> Pair = std::make_pair(
337              CI, cast<AllocaInst>(CI->getArgOperand(0)->stripPointerCasts()));
338            if (IsNullValue(CI->getArgOperand(1)))
339              Roots.push_back(Pair);
340            else
341              MetaRoots.push_back(Pair);
342          }
343
344  // Number roots with metadata (usually empty) at the beginning, so that the
345  // FrameMap::Meta array can be elided.
346  Roots.insert(Roots.begin(), MetaRoots.begin(), MetaRoots.end());
347}
348
349GetElementPtrInst *
350ShadowStackGC::CreateGEP(LLVMContext &Context, IRBuilder<> &B, Value *BasePtr,
351                         int Idx, int Idx2, const char *Name) {
352  Value *Indices[] = { ConstantInt::get(Type::getInt32Ty(Context), 0),
353                       ConstantInt::get(Type::getInt32Ty(Context), Idx),
354                       ConstantInt::get(Type::getInt32Ty(Context), Idx2) };
355  Value* Val = B.CreateGEP(BasePtr, Indices, Name);
356
357  assert(isa<GetElementPtrInst>(Val) && "Unexpected folded constant");
358
359  return dyn_cast<GetElementPtrInst>(Val);
360}
361
362GetElementPtrInst *
363ShadowStackGC::CreateGEP(LLVMContext &Context, IRBuilder<> &B, Value *BasePtr,
364                         int Idx, const char *Name) {
365  Value *Indices[] = { ConstantInt::get(Type::getInt32Ty(Context), 0),
366                       ConstantInt::get(Type::getInt32Ty(Context), Idx) };
367  Value *Val = B.CreateGEP(BasePtr, Indices, Name);
368
369  assert(isa<GetElementPtrInst>(Val) && "Unexpected folded constant");
370
371  return dyn_cast<GetElementPtrInst>(Val);
372}
373
374/// runOnFunction - Insert code to maintain the shadow stack.
375bool ShadowStackGC::performCustomLowering(Function &F) {
376  LLVMContext &Context = F.getContext();
377
378  // Find calls to llvm.gcroot.
379  CollectRoots(F);
380
381  // If there are no roots in this function, then there is no need to add a
382  // stack map entry for it.
383  if (Roots.empty())
384    return false;
385
386  // Build the constant map and figure the type of the shadow stack entry.
387  Value *FrameMap = GetFrameMap(F);
388  Type *ConcreteStackEntryTy = GetConcreteStackEntryType(F);
389
390  // Build the shadow stack entry at the very start of the function.
391  BasicBlock::iterator IP = F.getEntryBlock().begin();
392  IRBuilder<> AtEntry(IP->getParent(), IP);
393
394  Instruction *StackEntry = AtEntry.CreateAlloca(ConcreteStackEntryTy, nullptr,
395                                                 "gc_frame");
396
397  while (isa<AllocaInst>(IP)) ++IP;
398  AtEntry.SetInsertPoint(IP->getParent(), IP);
399
400  // Initialize the map pointer and load the current head of the shadow stack.
401  Instruction *CurrentHead  = AtEntry.CreateLoad(Head, "gc_currhead");
402  Instruction *EntryMapPtr  = CreateGEP(Context, AtEntry, StackEntry,
403                                        0,1,"gc_frame.map");
404  AtEntry.CreateStore(FrameMap, EntryMapPtr);
405
406  // After all the allocas...
407  for (unsigned I = 0, E = Roots.size(); I != E; ++I) {
408    // For each root, find the corresponding slot in the aggregate...
409    Value *SlotPtr = CreateGEP(Context, AtEntry, StackEntry, 1 + I, "gc_root");
410
411    // And use it in lieu of the alloca.
412    AllocaInst *OriginalAlloca = Roots[I].second;
413    SlotPtr->takeName(OriginalAlloca);
414    OriginalAlloca->replaceAllUsesWith(SlotPtr);
415  }
416
417  // Move past the original stores inserted by GCStrategy::InitRoots. This isn't
418  // really necessary (the collector would never see the intermediate state at
419  // runtime), but it's nicer not to push the half-initialized entry onto the
420  // shadow stack.
421  while (isa<StoreInst>(IP)) ++IP;
422  AtEntry.SetInsertPoint(IP->getParent(), IP);
423
424  // Push the entry onto the shadow stack.
425  Instruction *EntryNextPtr = CreateGEP(Context, AtEntry,
426                                        StackEntry,0,0,"gc_frame.next");
427  Instruction *NewHeadVal   = CreateGEP(Context, AtEntry,
428                                        StackEntry, 0, "gc_newhead");
429  AtEntry.CreateStore(CurrentHead, EntryNextPtr);
430  AtEntry.CreateStore(NewHeadVal, Head);
431
432  // For each instruction that escapes...
433  EscapeEnumerator EE(F, "gc_cleanup");
434  while (IRBuilder<> *AtExit = EE.Next()) {
435    // Pop the entry from the shadow stack. Don't reuse CurrentHead from
436    // AtEntry, since that would make the value live for the entire function.
437    Instruction *EntryNextPtr2 = CreateGEP(Context, *AtExit, StackEntry, 0, 0,
438                                           "gc_frame.next");
439    Value *SavedHead = AtExit->CreateLoad(EntryNextPtr2, "gc_savedhead");
440                       AtExit->CreateStore(SavedHead, Head);
441  }
442
443  // Delete the original allocas (which are no longer used) and the intrinsic
444  // calls (which are no longer valid). Doing this last avoids invalidating
445  // iterators.
446  for (unsigned I = 0, E = Roots.size(); I != E; ++I) {
447    Roots[I].first->eraseFromParent();
448    Roots[I].second->eraseFromParent();
449  }
450
451  Roots.clear();
452  return true;
453}
454