1 /*===-- semispace.c - Simple semi-space copying garbage collector ---------===*\
3 |* The LLVM Compiler Infrastructure
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.
8 |*===----------------------------------------------------------------------===*|
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.
16 \*===----------------------------------------------------------------------===*/
18 #include "../GCInterface.h"
23 /* AllocPtr - This points to the next byte that is available for allocation.
25 static char *AllocPtr;
27 /* AllocEnd - This points to the first byte not available for allocation. When
28 * AllocPtr passes this, we have run out of space.
30 static char *AllocEnd;
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.
36 static void *CurSpace, *OtherSpace;
38 /* SpaceSize - The size of each space. */
39 static unsigned SpaceSize;
41 /* llvm_gc_initialize - Allocate the two spaces that we plan to switch between.
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;
50 /* We always want to inline the fast path, but never want to inline the slow
53 void *llvm_gc_allocate(unsigned Size) __attribute__((always_inline));
54 static void* llvm_gc_alloc_slow(unsigned Size) __attribute__((noinline));
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);
65 static void* llvm_gc_alloc_slow(unsigned Size) {
67 if (AllocPtr+Size > AllocEnd) {
68 fprintf(stderr, "Garbage collector ran out of memory "
69 "allocating object of size: %d\n", Size);
73 return llvm_gc_allocate(Size);
77 static void process_pointer(void **Root, void *Meta) {
78 printf("process_root[0x%p] = 0x%p\n", (void*) Root, (void*) *Root);
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);
86 printf("Garbage collecting!!\n");
87 llvm_cg_walk_gcroots(process_pointer);
91 /* We use no read/write barriers */
92 void *llvm_gc_read(void **P) { return *P; }
93 void llvm_gc_write(void *V, void **P) { *P = V; }
96 /*===----------------------------------------------------------------------===**
97 * FIXME: This should be in a code-generator specific library, but for now this
98 * will work for all code generators.
100 typedef struct GCRoot {
105 typedef struct GCRoots {
106 struct GCRoots *Next;
108 GCRoot RootRecords[];
110 GCRoots *llvm_gc_root_chain;
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) {
116 for (i = 0, e = R->NumRoots; i != e; ++i)
117 FP(R->RootRecords[i].RootPtr, R->RootRecords[i].Meta);