← Back to branch summary

~ubuntu-branches/ubuntu/saucy/clamav/saucy

« back to all changes in this revision

Viewing changes to libclamav/c++/llvm/lib/CodeGen/ShadowStackGC.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Leonel Nunez
  • Date: 2008-02-11 22:52:13 UTC
  • mfrom: (1.1.6 upstream)
  • mto: This revision was merged to the branch mainline in revision 38.
  • Revision ID: james.westby@ubuntu.com-20080211225213-p2uwj4czso1w2f8h
Tags: upstream-0.92~dfsg
Import upstream version 0.92~dfsg

Show diffs side-by-side

added added

removed removed

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