new simpler GC

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);
+}