From 84621ed660336db30bcd92c085263634a8afa24c Mon Sep 17 00:00:00 2001 From: "Michael D. Lowis" Date: Fri, 3 Apr 2015 12:20:23 -0400 Subject: [PATCH] Started outlining the algorithm for collection --- modules/atf | 2 +- source/runtime/gc.c | 77 ++++++++++++++++++++++++++++++++++++------- source/runtime/gc.h | 8 +++-- source/runtime/heap.c | 17 ++++++++++ source/runtime/heap.h | 13 ++++---- source/runtime/main.c | 4 +-- tests/test_heap.c | 2 ++ 7 files changed, 99 insertions(+), 24 deletions(-) diff --git a/modules/atf b/modules/atf index 04d4571..0110dca 160000 --- a/modules/atf +++ b/modules/atf @@ -1 +1 @@ -Subproject commit 04d4571218dbef83a4321209c21b383defb9dc16 +Subproject commit 0110dca83199322915e157fc1278ee6b58dfb4f8 diff --git a/source/runtime/gc.c b/source/runtime/gc.c index da1a32d..56f2222 100644 --- a/source/runtime/gc.c +++ b/source/runtime/gc.c @@ -1,23 +1,47 @@ #include "gc.h" #include "heap.h" +#include +#include typedef struct { uint64_t objmap; uint8_t data[]; } obj_t; -static heap_t* heap = NULL; +typedef struct root_t { + struct root_t* next; + void* address; + size_t size; +} root_t; -void gc_init(void* stack_bottom) +static heap_t* Heap = NULL; +static uintptr_t* Stack_Bottom = NULL; +static root_t* Roots = NULL; + +void gc_init(uintptr_t* stack_bottom) +{ + Stack_Bottom = stack_bottom; + Heap = heap_create(); +} + +void gc_shutdown(void) { - (void)stack_bottom; - heap = heap_create(); + heap_destroy(Heap); +} + +void gc_add_root(void* address, size_t size) +{ + root_t* root = (root_t*)malloc(sizeof(root_t)); + root->address = address; + root->size = size; + root->next = Roots; + Roots = root; } void* gc_object(uint64_t objmap, size_t num_slots) { (void)objmap; - return heap_allocate(heap, num_slots+1); + return heap_allocate(Heap, num_slots+1); } void* gc_allocate(size_t size) @@ -25,15 +49,46 @@ void* gc_allocate(size_t size) size_t slot_sz = sizeof(uintptr_t); size_t remainder = size % slot_sz; size_t num_slots = (size / slot_sz) + ((remainder == 0) ? 0 : (slot_sz - remainder)); - return heap_allocate(heap, num_slots + 1); + return heap_allocate(Heap, num_slots + 1); } -void gc_collect(void) -{ +static void gc_scan_object(void* object) { + (void)object; } -void gc_shutdown(void) -{ - heap_destroy(heap); +static void gc_scan_region(uintptr_t* start, uintptr_t* stop) { + for (; start < stop; start++) { + obj_t* obj = (obj_t*)heap_find_and_mark(Heap, start); + if (NULL != obj) + gc_scan_object(obj); + } } +static void gc_scan_stack(void) { + /* Setup pointers to the stack top and bottom */ + uintptr_t* stack_bot = Stack_Bottom; + uintptr_t* stack_top = (uintptr_t*)&stack_top; + /* Make sure we swap them in the event the stack grows downward */ + if (stack_bot > stack_top) { + uintptr_t* temp = stack_top; + stack_top = stack_bot; + stack_bot = temp; + } + /* Scan the stack and mark any live objects */ + gc_scan_region(stack_bot, stack_top); +} + +static void gc_scan_roots(void) { + root_t* root = Roots; + for (; root != NULL; root = root->next) + gc_scan_region(root->address, root->address + (root->size / sizeof(uintptr_t))); +} + +void gc_collect(void) +{ + heap_start_collection(Heap); + gc_scan_stack(); + gc_scan_roots(); + gc_scan_object(NULL); + heap_finish_collection(Heap); +} diff --git a/source/runtime/gc.h b/source/runtime/gc.h index 1e43fef..545468e 100644 --- a/source/runtime/gc.h +++ b/source/runtime/gc.h @@ -8,7 +8,11 @@ #include #include -void gc_init(void* stack_bottom); +void gc_init(uintptr_t* stack_bottom); + +void gc_shutdown(void); + +void gc_add_root(void* address, size_t size); void* gc_object(uint64_t objmap, size_t num_slots); @@ -16,6 +20,4 @@ void* gc_allocate(size_t size); void gc_collect(void); -void gc_shutdown(void); - #endif /* GC_H */ diff --git a/source/runtime/heap.c b/source/runtime/heap.c index 4378d7d..038d2ad 100644 --- a/source/runtime/heap.c +++ b/source/runtime/heap.c @@ -57,3 +57,20 @@ void* heap_allocate(heap_t* heap, uintptr_t num_slots) return obj; } +void heap_start_collection(heap_t* heap) +{ + (void)heap; +} + +void heap_finish_collection(heap_t* heap) +{ + (void)heap; +} + +void* heap_find_and_mark(heap_t* heap, uintptr_t* addr) +{ + (void)heap; + (void)addr; + return NULL; +} + diff --git a/source/runtime/heap.h b/source/runtime/heap.h index 9c134b4..361e409 100644 --- a/source/runtime/heap.h +++ b/source/runtime/heap.h @@ -14,13 +14,6 @@ #define HEAP_INDEX_OFFSET (MIN_NUM_SLOTS) #define NUM_HEAP_STACKS (MAX_NUM_SLOTS) -/* - -/\__/\ -| . . | -\____/ - -*/ typedef struct block_t { struct block_t* next; @@ -38,4 +31,10 @@ void heap_destroy(heap_t* heap); void* heap_allocate(heap_t* heap, uintptr_t num_slots); +void heap_start_collection(heap_t* heap); + +void heap_finish_collection(heap_t* heap); + +void* heap_find_and_mark(heap_t* heap, uintptr_t* addr); + #endif /* HEAP_H */ diff --git a/source/runtime/main.c b/source/runtime/main.c index c232333..b16ca1d 100644 --- a/source/runtime/main.c +++ b/source/runtime/main.c @@ -2,10 +2,10 @@ int main(int argc, char** argv) { extern int ATC_Main(int argc, char** argv); - int ret_code; + uintptr_t ret_code; gc_init(&ret_code); ret_code = ATC_Main(argc, argv); gc_shutdown(); - return ret_code; + return (int)ret_code; } diff --git a/tests/test_heap.c b/tests/test_heap.c index 347cbc5..73ce97c 100644 --- a/tests/test_heap.c +++ b/tests/test_heap.c @@ -1,6 +1,7 @@ #include "atf.h" #include "heap.h" +#include "gc.h" TEST_SUITE(Heap) { /* Verify: heap_create *************************************************************************/ @@ -10,6 +11,7 @@ TEST_SUITE(Heap) { CHECK(NULL != heap_allocate(heap, 64)); CHECK(NULL != heap_allocate(heap, 65)); heap_destroy(heap); + gc_collect(); } /* Verify: heap_alloc -- 2.55.0