diff options
Diffstat (limited to 'src/gc/gen3.c')
| -rw-r--r-- | src/gc/gen3.c | 566 |
1 files changed, 566 insertions, 0 deletions
diff --git a/src/gc/gen3.c b/src/gc/gen3.c new file mode 100644 index 0000000..09fa452 --- /dev/null +++ b/src/gc/gen3.c @@ -0,0 +1,566 @@ +#include "../gc.h" +#include "../platform.h" +#include "../util.h" +#include <stdbool.h> +#include <stddef.h> +#include <stdint.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +/** + * Constants that should probably be learned. + */ +static const size_t NURSERY_L1D_SIZE_FACTOR = 1; +static const size_t YOUNG_HEAP_L3_SIZE_FACTOR = 2; + +/** + * Objects each have a header, with a slightly different layout depending on + * which heap the object is in. Each header tracks the layout of the object + * itself, as well as some other properties, in a uniform way. via the + * `enum object_kind` and `struct object_size` types. + */ + +/** + * Gives special properties the object might have, as well as the interpretation + * of its size. + */ +enum object_kind { + /** + * A normal object. Has up to 2¹⁶ slots for values, and up to 2¹³ slots for + * untraced `uintptr_t`s (which may simply be used as bytes). + */ + OBJECT_NORMAL, + + /** + * An untraced object. Has up to 2²⁹ slots for untraced `uintptr_t`s (which + * may simply be used as bytes). + */ + OBJECT_UNTRACED, + + /** + * A wrapper for a pointer to a code address. When this object gets collected, + * calls `free_code` on its first untraced slot. + */ + OBJECT_COMPILED_FUNCTION, + + /** + * A hashtable keyed by the addresses. This behaves like a normal object, but + * the first untraced slot gets set to the `uintptr_t` 1 whenever a collection + * traces the hashtable. + * + * The hashtable uses this information to rehash after each collection. + */ + OBJECT_HASHTABLE_EQ, +}; + +/** + * A `size_t`-sized encoding of the object size. Also stores an extra bit used + * to indicate that the object has been moved in nursery collection, and that + * the object has been marked in old-heap collection. + */ +struct object_size { + enum object_kind kind : 2; + bool mark : 1; + size_t bits : (8 * sizeof(size_t)) - 3; +}; + +/** + * Returns the number of slots for values the object has. + */ +static size_t object_size_value_slots(const struct object_size size) { + switch (size.kind) { + case OBJECT_NORMAL: + case OBJECT_COMPILED_FUNCTION: + case OBJECT_HASHTABLE_EQ: + return size.bits >> ((4 * sizeof(size_t)) - 3); + case OBJECT_UNTRACED: + return 0; + } +} + +/** + * Returns the number of untraced slots the object has. + */ +static size_t object_size_untraced_slots(const struct object_size size) { + switch (size.kind) { + case OBJECT_NORMAL: + case OBJECT_COMPILED_FUNCTION: + case OBJECT_HASHTABLE_EQ: + return size.bits & ((1 << ((4 * sizeof(size_t)) - 3)) - 1); + case OBJECT_UNTRACED: + return size.bits; + } +} + +/** + * Returns the total number of slots the object has. + */ +static size_t object_size_total_slots(const struct object_size size) { + return object_size_value_slots(size) + object_size_untraced_slots(size); +} + +/** + * This struct is used as an opaque type for the fields of an object. + */ +struct object { + uintptr_t hd; + uintptr_t tl[]; +}; + +/** + * Returns the number of slots for values the object has. + */ +static size_t object_value_slots(const struct object *const obj) { + return object_size_value_slots(((const struct object_size *)obj)[-1]); +} + +/** + * Returns the number of untraced slots the object has. + */ +static size_t object_untraced_slots(const struct object *const obj) { + return object_size_untraced_slots(((const struct object_size *)obj)[-1]); +} + +/** + * Returns the total number of slots the object has. + */ +static size_t object_total_slots(const struct object *const obj) { + return object_value_slots(obj) + object_untraced_slots(obj); +} + +/** + * This is the layout of an object in the nursery. + */ +struct nursery_object { + struct object_size size; + uintptr_t slots[]; +}; + +/** + * This is the layout of an object in the young-heap. Because the young-heap is + * collected with mark-compact, it needs a dedicated forwarding pointer (or in + * our case, a forwarding offset) and can't simply overwrite the object slots + * with one. + */ +struct young_heap_object { + uintptr_t fwd; + struct object_size size; + uintptr_t slots[]; +}; + +/** + * This is the layout of an object in the old-heap. It matches the nursery + * layout at the moment. + */ +struct old_heap_object { + struct object_size size; + uintptr_t slots[]; +}; + +/** + * The nursery and young-heap each have a layout like: + * + * ┌──────────────┐ ←── Top ─┐ + * │remembered set│ │ + * ├──────────────┤ ←── Limit │ + * │ free │ │ + * │ space │ │ + * ├──────────────┤ ←── Next ├─ Size + * │ │ │ + * │ │ │ + * │ objects │ │ + * │ │ │ + * │ │ │ + * └──────────────┘ ←── Bottom ─┘ + * + * The layout of both regions are defined by the four labelled pointers, so we + * define them. + */ +static uintptr_t nursery_bottom, nursery_next, nursery_limit, nursery_top; +static uintptr_t young_heap_bottom, young_heap_next, young_heap_limit, + young_heap_top; +static size_t nursery_size, young_heap_size; +static size_t max_needed_young_heap_size_during_collection; + +/** + * The old-heap is composed of blocks, each of which are stored in an + * intrusive doubly linked list per size class. Size classes start at 8 bytes + * and go up to 64KiB, with a "large object" size class past that. For size + * classes up to and including 4KiB, blocks are 64KiB in size. Past that, blocks + * are sized to fit one object of the size class. + * + * Each block has a local free-list of objects of the size class. + */ +enum old_heap_size_class { + SIZE_8 = 0, + SIZE_16, + SIZE_32, + SIZE_64, + SIZE_128, + SIZE_256, + SIZE_512, + SIZE_1024, + SIZE_2048, + SIZE_4096, + SIZE_8192, + SIZE_16384, + SIZE_32768, + SIZE_65536, + SIZE_HUGE, + + SIZE_CLASS_COUNT, +}; + +struct old_heap_block { + struct old_heap_block *prev, *next; + struct old_heap_free_object *free_list; +}; + +struct old_heap_free_object { + struct old_heap_free_object *next; +}; + +static struct old_heap_block old_heap_sentinels[SIZE_CLASS_COUNT]; + +/** + * The root stack is an arbitrary 4KiB. It shouldn't get anywhere near this + * deep, so this is simply a convenient size. + */ +static struct value *root_stack[4096 / sizeof(uintptr_t)] = {0}; +static size_t root_stack_depth = 0; + +#include <stdarg.h> +static inline __attribute__((format(printf, 1, 2))) void +gc_debugf(const char *fmt, ...) { + va_list ap; + va_start(ap, fmt); + vfprintf(stderr, fmt, ap); + va_end(ap); +} + +void gc_init(void) { + // Allocate the nursery and young-heap. + nursery_size = get_l1d_size() * NURSERY_L1D_SIZE_FACTOR; + nursery_bottom = nursery_next = alloc_gc_region(nursery_size); + nursery_limit = nursery_top = nursery_bottom + nursery_size; + assume(nursery_bottom); + + young_heap_size = get_l3_size() * YOUNG_HEAP_L3_SIZE_FACTOR; + young_heap_bottom = young_heap_next = alloc_gc_region(young_heap_size); + young_heap_limit = young_heap_top = young_heap_bottom + young_heap_size; + assume(young_heap_bottom); + + // Compute how much space could be used when migrating the nursery to the + // young-heap, at a maximum. We collect the young-heap if its size gets below + // this. + max_needed_young_heap_size_during_collection = + (nursery_size * (sizeof(struct young_heap_object) + sizeof(uintptr_t))) / + (sizeof(struct nursery_object) + sizeof(uintptr_t)); + + // Self-link the old-heap. + for (size_t i = 0; i < SIZE_CLASS_COUNT; i++) { + old_heap_sentinels[i].prev = old_heap_sentinels[i].next = + &old_heap_sentinels[i]; + } +} + +static struct object *gc_alloc_in_nursery(const struct object_size object_size, + const size_t nursery_object_size) { + // Check if there's enough space in the nursery. + uintptr_t new_next = nursery_next + nursery_object_size; + if (new_next > nursery_limit) { + gc_collect_nursery(); + new_next = nursery_next + nursery_object_size; + assume(new_next <= nursery_limit); + } + + // Reserve the space. + struct nursery_object *obj = (struct nursery_object *)nursery_next; + nursery_next = new_next; + + // Hand the space back. + obj->size = object_size; + return (struct object *)&obj->slots[0]; +} + +static struct object * +gc_alloc_in_young_heap(const struct object_size object_size, + const size_t young_heap_object_size) { + todo("gc_alloc: young heap"); +} + +static struct object *gc_alloc_in_old_heap(const struct object_size object_size, + const size_t old_heap_object_size) { + todo("gc_alloc: old heap"); +} + +struct object *gc_alloc(const size_t value_slot_count, + const size_t untraced_slot_count) { + gc_debugf("gc_alloc(%zu, %zu) = ", value_slot_count, untraced_slot_count); + + // First, decide if this is an untraced object and check the object size. + const bool is_untraced = value_slot_count == 0; + if (is_untraced) { + assume(untraced_slot_count < (1 << 29)); + } else { + assume(value_slot_count < (1 << 16)); + assume(untraced_slot_count < (1 << 13)); + } + + // First, calculate the amount of space we'll need to store the object in the + // various heaps. + const size_t object_size_bytes = (value_slot_count * sizeof(struct value)) + + (untraced_slot_count * sizeof(uintptr_t)); + assume(object_size_bytes > 0); + const size_t nursery_object_size = + sizeof(struct nursery_object) + object_size_bytes, + young_heap_object_size = + sizeof(struct young_heap_object) + object_size_bytes, + old_heap_object_size = + sizeof(struct old_heap_object) + object_size_bytes; + + // Check whether the object is inherently too large, and should get allocated + // directly into another heap. + const bool nursery_fits = nursery_object_size <= nursery_size, + young_heap_fits = young_heap_object_size <= young_heap_size; + + // Construct the object size. This is common to all the headers, so why not. + const struct object_size object_size = { + .kind = is_untraced ? OBJECT_UNTRACED : OBJECT_NORMAL, + .mark = false, + .bits = is_untraced ? untraced_slot_count + : (value_slot_count << ((4 * sizeof(size_t)) - 3)) | + untraced_slot_count, + }; + assume(object_size_value_slots(object_size) == value_slot_count); + assume(object_size_untraced_slots(object_size) == untraced_slot_count); + + // Everything above this line should get inlined and constant-folded. + struct object *obj = + nursery_fits ? gc_alloc_in_nursery(object_size, nursery_object_size) + : young_heap_fits + ? gc_alloc_in_young_heap(object_size, young_heap_object_size) + : gc_alloc_in_old_heap(object_size, old_heap_object_size); + memset(obj, 0, object_value_slots(obj) * sizeof(uintptr_t)); + gc_debugf("%p\n", (void *)obj); + return obj; +} + +struct object *gc_alloc_compiled_function(size_t value_slot_count, + size_t untraced_slot_count) { + todo("gc_alloc_compiled_function"); +} + +struct object *gc_alloc_hashtable_eq(size_t value_slot_count, + size_t untraced_slot_count) { + todo("gc_alloc_hashtable_eq"); +} + +/** + * Relocates the pointer in the slot, if necessary. Returns whether it did + * (i.e., whether the pointer was a nursery pointer). + */ +static bool gc_collect_nursery_relocate(struct value *slot) { + gc_debugf("gc_collect_nursery_relocate(%p): %p -", slot, (void *)slot->bits); + char relocation_type = 'x'; + struct value old_value = *slot; + + // Check if the value was a pointer. If not, we don't need to relocate it. + if (!is_ptr(old_value)) + goto out; + + // Check if the object is in the nursery. If not, we don't need to relocate + // it. + struct object *old_obj = untag_ptr(old_value); + if (!(nursery_bottom <= (uintptr_t)old_obj && + (uintptr_t)old_obj <= nursery_top)) + goto out; + + // Check if the object has already been relocated. + struct nursery_object *old_header = + (struct nursery_object *)((uintptr_t)old_obj - + sizeof(struct nursery_object)); + struct object *new_obj; + if (old_header->size.mark) { + new_obj = (struct object *)old_header->slots[0]; + relocation_type = 'o'; + } else { + // Allocate a new object in the young-heap. + assume(young_heap_next < young_heap_limit); + assume((young_heap_next & 0b111) == 0); + struct young_heap_object *new_header = + (struct young_heap_object *)young_heap_next; + new_obj = (struct object *)&new_header->slots[0]; + size_t total_slots = object_size_total_slots(old_header->size); + assume(total_slots > 0); + uintptr_t new_next = (uintptr_t)&new_header->slots[total_slots]; + assume(new_next < young_heap_limit); + young_heap_next = new_next; + gc_debugf("{%p - %p (%zu)}", &old_header->slots[0], + &old_header->slots[total_slots], total_slots); + + // Copy the object. + new_header->size = old_header->size; + memcpy(new_obj, old_obj, total_slots * sizeof(uintptr_t)); + + // Mark the object as relocated. + old_header->size.mark = true; + old_header->slots[0] = (uintptr_t)new_obj; + + // Update the relocation flag. + relocation_type = '>'; + } + *slot = tag_ptr(new_obj, get_tag(old_value)); + +out: + gc_debugf("%c %p\n", relocation_type, (void *)slot->bits); + return relocation_type != 'x'; +} + +void gc_collect_nursery(void) { + gc_debugf("--- gc ---\n"); + + // Check that there's enough space in the young-heap. + assume(max_needed_young_heap_size_during_collection < + (young_heap_limit - young_heap_next)); + + // Keep a "finger" at the point at which we've started relocating objects. + uintptr_t finger = young_heap_next; + + // Relocate the roots. + for (size_t i = 0; i < root_stack_depth; i++) + gc_collect_nursery_relocate(root_stack[i]); + + // Relocate or promote fields of the remembered set. + while (nursery_limit != nursery_top) { + struct value *slot = *(struct value **)nursery_limit; + nursery_limit += sizeof(struct value *); + + // If the slot was in a nursery object, ignore it. + if (nursery_bottom <= (uintptr_t)slot && (uintptr_t)slot <= nursery_top) + continue; + + // If the slot didn't contain a pointer, ignore it. + if (!is_ptr(*slot)) + continue; + struct object *ptr = untag_ptr(*slot); + + // If the slot pointed to a nursery object, relocate it. + if (nursery_bottom <= (uintptr_t)ptr && (uintptr_t)ptr <= nursery_top) { + gc_collect_nursery_relocate(slot); + continue; + } + + // If the slot was in the young-set but did not point to the nursery set, we + // don't care about it either. + if (young_heap_bottom <= (uintptr_t)slot && + (uintptr_t)slot <= young_heap_top) + continue; + + // TODO: Remembered set + todo("relocate remembered set"); + } + + // Walk the objects we just moved to the young-heap, relocating their fields. + while (finger < young_heap_next) { + // Relocate any fields. + struct young_heap_object *header = (struct young_heap_object *)finger; + size_t value_slot_count = object_size_value_slots(header->size); + for (size_t i = 0; i < value_slot_count; i++) + gc_collect_nursery_relocate((struct value *)&header->slots[i]); + + // Advance the finger. + size_t total_slot_count = object_size_total_slots(header->size); + finger = (uintptr_t)&header->slots[total_slot_count]; + } + + // Reset the nursery's pointers. + nursery_next = nursery_bottom; + assume(nursery_limit == nursery_top); + + // Clear the nursery's memory. + clear_gc_region(nursery_bottom, nursery_size); +} + +void gc_collect_young_heap(void) { todo("gc_collect_young_heap"); } + +void gc_collect_old_heap(void) { todo("gc_collect_old_heap"); } + +struct value gc_read_value_slot(const struct object *obj, size_t slot_index) { + gc_debugf("gc_read_value_slot(%p, %zu) = ", obj, slot_index); + assume(slot_index < object_value_slots(obj)); + struct value *slots = (struct value *)obj; + struct value value = slots[slot_index]; + gc_debugf("%p\n", (void *)value.bits); + return value; +} + +uintptr_t gc_read_untraced_slot(const struct object *obj, size_t slot_index) { + assume(slot_index < object_untraced_slots(obj)); + todo("gc_read_untraced_slot"); +} + +uint8_t gc_read_untraced_byte(const struct object *obj, size_t byte_index) { + todo("gc_read_untraced_byte"); +} + +void gc_write_value_slot(struct object *obj, size_t slot_index, + struct value value) { + gc_debugf("gc_write_value_slot(%p, %zu, %p)\n", obj, slot_index, + (void *)value.bits); + gc_debugf(" object_value_slots = %zu\n", object_value_slots(obj)); + gc_debugf(" object_untraced_slots = %zu\n", object_untraced_slots(obj)); + assume(slot_index < object_value_slots(obj)); + if (nursery_next == nursery_limit) { + gc_root_push(&obj); + if (!(value.bits & 1)) + gc_root_push(&value); + gc_collect_nursery(); + if (!(value.bits & 1)) + gc_root_pop(); + gc_root_pop(); + } + + nursery_limit -= sizeof(uintptr_t); + uintptr_t **remembered_set = (uintptr_t **)nursery_limit; + *remembered_set = (uintptr_t *)obj + slot_index * sizeof(uintptr_t); + + struct value *slots = (struct value *)obj; + slots[slot_index] = value; +} + +void gc_write_untraced_slot(struct object *obj, size_t slot_index, + uintptr_t value) { + assume(slot_index < object_untraced_slots(obj)); + todo("gc_write_untraced_slot"); +} + +void gc_write_untraced_byte(struct object *obj, size_t byte_index, + uint8_t byte) { + todo("gc_write_untraced_byte"); +} + +void gc_root_push(struct value *root) { + assume(root_stack_depth < sizeof(root_stack)); + root_stack[root_stack_depth++] = root; +} + +void gc_root_pop(void) { + assume(root_stack_depth > 0); + root_stack_depth--; +} + +void gc_debug(void) { + fprintf(stderr, "nursery size: %#zx\n", nursery_size); + fprintf(stderr, "nursery top: %p\n", (void *)nursery_top); + fprintf(stderr, "nursery limit: %p\n", (void *)nursery_limit); + fprintf(stderr, "nursery next: %p\n", (void *)nursery_next); + fprintf(stderr, "nursery bottom: %p\n", (void *)nursery_bottom); + fprintf(stderr, "\n"); + fprintf(stderr, "young-heap size: %#zx\n", young_heap_size); + fprintf(stderr, "young-heap top: %p\n", (void *)young_heap_top); + fprintf(stderr, "young-heap limit: %p\n", (void *)young_heap_limit); + fprintf(stderr, "young-heap next: %p\n", (void *)young_heap_next); + fprintf(stderr, "young-heap bottom: %p\n", (void *)young_heap_bottom); +} |