runtime/GC/SemiSpace/semispace.c

   1 /*===-- semispace.c - Simple semi-space copying garbage collector ---------===*\
   2 |*
   3 |*                     The LLVM Compiler Infrastructure
   4 |*
   5 |* This file was developed by the LLVM research group and is distributed under
   6 |* the University of Illinois Open Source 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 typedef struct GCRoot {
 101   void **RootPtr;
 102   void *Meta;
 103 } GCRoot;
 104
 105 typedef struct GCRoots {
 106   struct GCRoots *Next;
 107   unsigned NumRoots;
 108   GCRoot RootRecords[];
 109 } GCRoots;
 110 GCRoots *llvm_gc_root_chain;
 111
 112 void llvm_cg_walk_gcroots(void (*FP)(void **Root, void *Meta)) {
 113   GCRoots *R = llvm_gc_root_chain;
 114   for (; R; R = R->Next) {
 115     unsigned i, e;
 116     for (i = 0, e = R->NumRoots; i != e; ++i)
 117       FP(R->RootRecords[i].RootPtr, R->RootRecords[i].Meta);
 118   }
 119 }
 120 /* END FIXME! */
 121
 122