From 601da2dfae29eac952ef8297c5a0ace37dea4540 Mon Sep 17 00:00:00 2001 From: Michael Williamson Date: Tue, 19 Mar 2024 15:33:09 +0000 Subject: Move mark-and-sweep GC to its own directory --- runtime/meson.build | 2 +- runtime/src/shed/gc.c | 132 -------------------------------- runtime/src/shed/gc/mark-and-sweep/gc.c | 132 ++++++++++++++++++++++++++++++++ 3 files changed, 133 insertions(+), 133 deletions(-) delete mode 100644 runtime/src/shed/gc.c create mode 100644 runtime/src/shed/gc/mark-and-sweep/gc.c (limited to 'runtime') diff --git a/runtime/meson.build b/runtime/meson.build index 310c34ed..cbc098df 100644 --- a/runtime/meson.build +++ b/runtime/meson.build @@ -14,11 +14,11 @@ static_library( 'shed', 'src/shed/alloc.c', 'src/shed/effects.c', - 'src/shed/gc.c', 'src/shed/ints.c', 'src/shed/primitives.c', 'src/shed/strings.c', 'src/shed/namespaces/Shed/Builtins.c', + 'src/shed/gc/mark-and-sweep/gc.c', ) if meson.get_external_property('shed_runtime_is_wasm', false) diff --git a/runtime/src/shed/gc.c b/runtime/src/shed/gc.c deleted file mode 100644 index 2d6ab05f..00000000 --- a/runtime/src/shed/gc.c +++ /dev/null @@ -1,132 +0,0 @@ -#include - -#include "../patio/patio.h" -#include "./alloc.h" -#include "./gc.h" -#include "./primitives.h" - -// == GC objects == - -bool is_gc_object(ShedObject object) { - // Check that the object is not one of: - // * unit (0) - // * false (0) - // * true (1) - return !(object == 0 || object == 1); -} - -// == Marking == - -// The mark value for each object is initialized to 0. Each mark phase -// alternates between using 0b010 and 0b100 as the mark value. We check only for -// the bit set to 1, meaning static values can have a mark value of 0b110 to be -// considered always marked. -PatioInt current_mark_value = 0b010; - -void alternate_mark_value() { - current_mark_value ^= 0b110; -} - -bool is_marked(struct ShedGcObjectHeader* object) { - return (object->mark & current_mark_value) == current_mark_value; -} - -void mark(struct ShedGcObjectHeader* object) { - if (object == NULL || is_marked(object)) { - return; - } - - object->mark = current_mark_value; - - struct RuntimeType* runtime_type = &shed__rtti[object->runtime_type_tag]; - - struct ShedGcObjectHeader** children = (struct ShedGcObjectHeader**) ( - ((void*) object) + runtime_type->children_offset - ); - - for (size_t child_index = 0; child_index < runtime_type->children_count; child_index++) { - mark(children[child_index]); - } -} - -// == Roots == - -typedef size_t ShedGcRootIndex; - -ShedGcRootIndex gc_root_stack_index = 0; - -struct ShedGcObjectHeader* gc_root_stack[16384]; - -ShedGcRootIndex shed__runtime__gc_get_root_stack_index() { - return gc_root_stack_index; -} - -void shed__runtime__gc_set_root_stack_index(ShedGcRootIndex new_gc_root_stack_index) { - gc_root_stack_index = new_gc_root_stack_index; -} - -static void shed__runtime__gc_push_root_gc_object(struct ShedGcObjectHeader* gc_root) { - gc_root_stack[gc_root_stack_index] = gc_root; - gc_root_stack_index++; -} - -void shed__runtime__gc_push_root(ShedObject gc_root) { - if (!is_gc_object(gc_root)) { - return; - } - - shed__runtime__gc_push_root_gc_object((struct ShedGcObjectHeader*) gc_root); -} - -// == Allocation == - -struct ShedGcObjectHeader* first = NULL; - -void* shed__runtime__gc_alloc(size_t size, uint32_t runtime_type_tag) { - struct ShedGcObjectHeader* object = malloc(size); - object->next = first; - object->mark = 0; - object->runtime_type_tag = runtime_type_tag; - - // TODO: is it possible to leave adding the root to the caller, and avoid - // having to add so many roots? (Since some values will immediately become a - // descendant of a root.) - - shed__runtime__gc_push_root_gc_object(object); - - first = object; - - return object; -} - -// == Collection == - -void mark_reachable() { - for (size_t i = 0; i < gc_root_stack_index; i++) { - mark(gc_root_stack[i]); - } -} - -void sweep() { - struct ShedGcObjectHeader** object = &first; - while (*object != NULL) { - if (is_marked(*object)) { - object = &(*object)->next; - } else { - struct ShedGcObjectHeader* next = (*object)->next; - free(*object); - *object = next; - } - } -} - -void shed__runtime__gc_collect() { - // We only want to collect periodically, but we currently always collect to - // hopefully surface errors more quickly. - - alternate_mark_value(); - - mark_reachable(); - - sweep(); -} diff --git a/runtime/src/shed/gc/mark-and-sweep/gc.c b/runtime/src/shed/gc/mark-and-sweep/gc.c new file mode 100644 index 00000000..e874157a --- /dev/null +++ b/runtime/src/shed/gc/mark-and-sweep/gc.c @@ -0,0 +1,132 @@ +#include + +#include "../../../patio/patio.h" +#include "../../alloc.h" +#include "../../gc.h" +#include "../../primitives.h" + +// == GC objects == + +bool is_gc_object(ShedObject object) { + // Check that the object is not one of: + // * unit (0) + // * false (0) + // * true (1) + return !(object == 0 || object == 1); +} + +// == Marking == + +// The mark value for each object is initialized to 0. Each mark phase +// alternates between using 0b010 and 0b100 as the mark value. We check only for +// the bit set to 1, meaning static values can have a mark value of 0b110 to be +// considered always marked. +PatioInt current_mark_value = 0b010; + +void alternate_mark_value() { + current_mark_value ^= 0b110; +} + +bool is_marked(struct ShedGcObjectHeader* object) { + return (object->mark & current_mark_value) == current_mark_value; +} + +void mark(struct ShedGcObjectHeader* object) { + if (object == NULL || is_marked(object)) { + return; + } + + object->mark = current_mark_value; + + struct RuntimeType* runtime_type = &shed__rtti[object->runtime_type_tag]; + + struct ShedGcObjectHeader** children = (struct ShedGcObjectHeader**) ( + ((void*) object) + runtime_type->children_offset + ); + + for (size_t child_index = 0; child_index < runtime_type->children_count; child_index++) { + mark(children[child_index]); + } +} + +// == Roots == + +typedef size_t ShedGcRootIndex; + +ShedGcRootIndex gc_root_stack_index = 0; + +struct ShedGcObjectHeader* gc_root_stack[16384]; + +ShedGcRootIndex shed__runtime__gc_get_root_stack_index() { + return gc_root_stack_index; +} + +void shed__runtime__gc_set_root_stack_index(ShedGcRootIndex new_gc_root_stack_index) { + gc_root_stack_index = new_gc_root_stack_index; +} + +static void shed__runtime__gc_push_root_gc_object(struct ShedGcObjectHeader* gc_root) { + gc_root_stack[gc_root_stack_index] = gc_root; + gc_root_stack_index++; +} + +void shed__runtime__gc_push_root(ShedObject gc_root) { + if (!is_gc_object(gc_root)) { + return; + } + + shed__runtime__gc_push_root_gc_object((struct ShedGcObjectHeader*) gc_root); +} + +// == Allocation == + +struct ShedGcObjectHeader* first = NULL; + +void* shed__runtime__gc_alloc(size_t size, uint32_t runtime_type_tag) { + struct ShedGcObjectHeader* object = malloc(size); + object->next = first; + object->mark = 0; + object->runtime_type_tag = runtime_type_tag; + + // TODO: is it possible to leave adding the root to the caller, and avoid + // having to add so many roots? (Since some values will immediately become a + // descendant of a root.) + + shed__runtime__gc_push_root_gc_object(object); + + first = object; + + return object; +} + +// == Collection == + +void mark_reachable() { + for (size_t i = 0; i < gc_root_stack_index; i++) { + mark(gc_root_stack[i]); + } +} + +void sweep() { + struct ShedGcObjectHeader** object = &first; + while (*object != NULL) { + if (is_marked(*object)) { + object = &(*object)->next; + } else { + struct ShedGcObjectHeader* next = (*object)->next; + free(*object); + *object = next; + } + } +} + +void shed__runtime__gc_collect() { + // We only want to collect periodically, but we currently always collect to + // hopefully surface errors more quickly. + + alternate_mark_value(); + + mark_reachable(); + + sweep(); +} -- cgit v1.2.3