| /*===-- semispace.c - Simple semi-space copying garbage collector ---------===*\ |
| |* |
| |* The LLVM Compiler Infrastructure |
| |* |
| |* This file is distributed under the University of Illinois Open Source |
| |* License. See LICENSE.TXT for details. |
| |* |
| |*===----------------------------------------------------------------------===*| |
| |* |
| |* This garbage collector is an extremely simple copying collector. It splits |
| |* the managed region of memory into two pieces: the current space to allocate |
| |* from, and the copying space. When the portion being allocated from fills up, |
| |* a garbage collection cycle happens, which copies all live blocks to the other |
| |* half of the managed space. |
| |* |
| \*===----------------------------------------------------------------------===*/ |
| |
| #include "../GCInterface.h" |
| #include <stdio.h> |
| #include <stdlib.h> |
| #include <string.h> |
| |
| /* AllocPtr - This points to the next byte that is available for allocation. |
| */ |
| static char *AllocPtr; |
| |
| /* AllocEnd - This points to the first byte not available for allocation. When |
| * AllocPtr passes this, we have run out of space. |
| */ |
| static char *AllocEnd; |
| |
| /* CurSpace/OtherSpace - These pointers point to the two regions of memory that |
| * we switch between. The unallocated portion of the CurSpace is known to be |
| * zero'd out, but the OtherSpace contains junk. |
| */ |
| static void *CurSpace, *OtherSpace; |
| |
| /* SpaceSize - The size of each space. */ |
| static unsigned SpaceSize; |
| |
| /* llvm_gc_initialize - Allocate the two spaces that we plan to switch between. |
| */ |
| void llvm_gc_initialize(unsigned InitialHeapSize) { |
| SpaceSize = InitialHeapSize/2; |
| CurSpace = AllocPtr = calloc(1, SpaceSize); |
| OtherSpace = malloc(SpaceSize); |
| AllocEnd = AllocPtr + SpaceSize; |
| } |
| |
| /* We always want to inline the fast path, but never want to inline the slow |
| * path. |
| */ |
| void *llvm_gc_allocate(unsigned Size) __attribute__((always_inline)); |
| static void* llvm_gc_alloc_slow(unsigned Size) __attribute__((noinline)); |
| |
| void *llvm_gc_allocate(unsigned Size) { |
| char *OldAP = AllocPtr; |
| char *NewEnd = OldAP+Size; |
| if (NewEnd > AllocEnd) |
| return llvm_gc_alloc_slow(Size); |
| AllocPtr = NewEnd; |
| return OldAP; |
| } |
| |
| static void* llvm_gc_alloc_slow(unsigned Size) { |
| llvm_gc_collect(); |
| if (AllocPtr+Size > AllocEnd) { |
| fprintf(stderr, "Garbage collector ran out of memory " |
| "allocating object of size: %d\n", Size); |
| exit(1); |
| } |
| |
| return llvm_gc_allocate(Size); |
| } |
| |
| |
| static void process_pointer(void **Root, void *Meta) { |
| printf("process_root[0x%p] = 0x%p\n", (void*) Root, (void*) *Root); |
| } |
| |
| void llvm_gc_collect() { |
| // Clear out the space we will be copying into. |
| // FIXME: This should do the copy, then clear out whatever space is left. |
| memset(OtherSpace, 0, SpaceSize); |
| |
| printf("Garbage collecting!!\n"); |
| llvm_cg_walk_gcroots(process_pointer); |
| abort(); |
| } |
| |
| /* We use no read/write barriers */ |
| void *llvm_gc_read(void *ObjPtr, void **FieldPtr) { return *FieldPtr; } |
| void llvm_gc_write(void *V, void *ObjPtr, void **FieldPtr) { *FieldPtr = V; } |
| |
| |
| /*===----------------------------------------------------------------------===** |
| * FIXME: This should be in a code-generator specific library, but for now this |
| * will work for all code generators. |
| */ |
| typedef struct FrameMap FrameMap; |
| struct FrameMap { |
| int32_t NumRoots; // Number of roots in stack frame. |
| int32_t NumMeta; // Number of metadata descriptors. May be < NumRoots. |
| void *Meta[]; // May be absent for roots without metadata. |
| }; |
| |
| typedef struct StackEntry StackEntry; |
| struct StackEntry { |
| StackEntry *Next; // Caller's stack entry. |
| const FrameMap *Map; // Pointer to constant FrameMap. |
| void *Roots[]; // Stack roots (in-place array). |
| }; |
| StackEntry *llvm_gc_root_chain; |
| |
| void llvm_cg_walk_gcroots(void (*FP)(void **Root, void *Meta)) { |
| StackEntry *R; |
| for (R = llvm_gc_root_chain; R; R = R->Next) { |
| unsigned i, e; |
| for (i = 0, e = R->Map->NumMeta; i != e; ++i) |
| FP(&R->Roots[i], R->Map->Meta[i]); |
| for (e = R->Map->NumRoots; i != e; ++i) |
| FP(&R->Roots[i], NULL); |
| } |
| } |
| /* END FIXME! */ |
| |
| |