runtime/GC/SemiSpace/semispace.c

   1 /*===-- semispace.c - Simple semi-space copying garbage collector ---------===*\
   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 garbage collector is an extremely simple copying collector.  It splits
  11 |* the managed region of memory into two pieces: the current space to allocate
  12 |* from, and the copying space.  When the portion being allocated from fills up,
  13 |* a garbage collection cycle happens, which copies all live blocks to the other
  14 |* half of the managed space.
  15 |*
  16 \*===----------------------------------------------------------------------===*/
  17
  18 #include "../GCInterface.h"
  19 #include <stdio.h>
  20 #include <stdlib.h>
  21 #include <string.h>
  22
  23 /* AllocPtr - This points to the next byte that is available for allocation.
  24  */
  25 static char *AllocPtr;
  26
  27 /* AllocEnd - This points to the first byte not available for allocation.  When
  28  * AllocPtr passes this, we have run out of space.
  29  */
  30 static char *AllocEnd;
  31
  32 /* CurSpace/OtherSpace - These pointers point to the two regions of memory that
  33  * we switch between.  The unallocated portion of the CurSpace is known to be
  34  * zero'd out, but the OtherSpace contains junk.
  35  */
  36 static void *CurSpace, *OtherSpace;
  37
  38 /* SpaceSize - The size of each space. */
  39 static unsigned SpaceSize;
  40
  41 /* llvm_gc_initialize - Allocate the two spaces that we plan to switch between.
  42  */
  43 void llvm_gc_initialize(unsigned InitialHeapSize) {
  44   SpaceSize = InitialHeapSize/2;
  45   CurSpace = AllocPtr = calloc(1, SpaceSize);
  46   OtherSpace = malloc(SpaceSize);
  47   AllocEnd = AllocPtr + SpaceSize;
  48 }
  49
  50 /* We always want to inline the fast path, but never want to inline the slow
  51  * path.
  52  */
  53 void *llvm_gc_allocate(unsigned Size) __attribute__((always_inline));
  54 static void* llvm_gc_alloc_slow(unsigned Size) __attribute__((noinline));
  55
  56 void *llvm_gc_allocate(unsigned Size) {
  57   char *OldAP = AllocPtr;
  58   char *NewEnd = OldAP+Size;
  59   if (NewEnd > AllocEnd)
  60     return llvm_gc_alloc_slow(Size);
  61   AllocPtr = NewEnd;
  62   return OldAP;
  63 }
  64
  65 static void* llvm_gc_alloc_slow(unsigned Size) {
  66   llvm_gc_collect();
  67   if (AllocPtr+Size > AllocEnd) {
  68     fprintf(stderr, "Garbage collector ran out of memory "
  69             "allocating object of size: %d\n", Size);
  70     exit(1);
  71   }
  72
  73   return llvm_gc_allocate(Size);
  74 }
  75
  76
  77 static void process_pointer(void **Root, void *Meta) {
  78   printf("process_root[0x%p] = 0x%p\n", (void*) Root, (void*) *Root);
  79 }
  80
  81 void llvm_gc_collect() {
  82   // Clear out the space we will be copying into.
  83   // FIXME: This should do the copy, then clear out whatever space is left.
  84   memset(OtherSpace, 0, SpaceSize);
  85
  86   printf("Garbage collecting!!\n");
  87   llvm_cg_walk_gcroots(process_pointer);
  88   abort();
  89 }
  90
  91 /* We use no read/write barriers */
  92 void *llvm_gc_read(void *ObjPtr, void **FieldPtr) { return *FieldPtr; }
  93 void llvm_gc_write(void *V, void *ObjPtr, void **FieldPtr) { *FieldPtr = V; }
  94
  95
  96 /*===----------------------------------------------------------------------===**
  97  * FIXME: This should be in a code-generator specific library, but for now this
  98  * will work for all code generators.
  99  */
 100 struct FrameMap {
 101   int32_t NumRoots; // Number of roots in stack frame.
 102   int32_t NumMeta;  // Number of metadata descriptors. May be < NumRoots.
 103   void *Meta[];     // May be absent for roots without metadata.
 104 };
 105
 106 struct StackEntry {
 107   ShadowStackEntry *Next; // Caller's stack entry.
 108   const FrameMap *Map;    // Pointer to constant FrameMap.
 109   void *Roots[];          // Stack roots (in-place array).
 110 };
 111 StackEntry *llvm_gc_root_chain;
 112
 113 void llvm_cg_walk_gcroots(void (*FP)(void **Root, void *Meta)) {
 114   for (StackEntry *R; R; R = R->Next) {
 115     unsigned i, e;
 116     for (i = 0, e = R->NumMeta; i != e; ++i)
 117       FP(&R->Roots[i], R->Map->Meta[i]);
 118     for (e = R->NumRoots; i != e; ++i)
 119       FP(&R->Roots[i], NULL);
 120   }
 121 }
 122 /* END FIXME! */
 123
 124