#include "../gc.h" #include "../platform.h" #include "../util.h" #include #include #include #include #include #include /** * 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 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); }