Initial commit

2 files changed, 213 insertions, 0 deletions

diff --git a/src/gc/gc-debug.c b/src/gc/gc-debug.c
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/src/gc/gc-debug.c
diff --git a/src/gc/gc.c b/src/gc/gc.c
new file mode 100644
index 0000000..f53fd79
--- /dev/null
+++ b/src/gc/gc.c
@@ -0,0 +1,213 @@
+#include "../util.h"
+#include <stdbool.h>
+#include <stddef.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+/**
+ * These cache-size details are from
+ * https://www.copetti.org/writings/consoles/nintendo-3ds/. We call the second
+ * level of cache (only available on N3DS) L3, since this GC design only cares
+ * about L1D and L3.
+ */
+static const size_t L1D_SIZE = 16 * 1024, L3_SIZE = 2 * 1024 * 1024;
+
+/**
+ * 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 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_EQ_HASHTABLE,
+
+  /**
+   * 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 `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_value_slots(struct object_size size) {
+  switch (size.kind) {
+  case OBJECT_NORMAL:
+  case OBJECT_EQ_HASHTABLE:
+  case OBJECT_COMPILED_FUNCTION:
+    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_untraced_slots(struct object_size size) {
+  switch (size.kind) {
+  case OBJECT_NORMAL:
+  case OBJECT_EQ_HASHTABLE:
+  case OBJECT_COMPILED_FUNCTION:
+    return size.bits & ((1 << ((4 * sizeof(size_t)) - 3)) - 1);
+  case OBJECT_UNTRACED:
+    return size.bits;
+  }
+}
+
+/**
+ * This struct is used as an opaque type for the fields of an object.
+ */
+struct object {
+  uintptr_t hd;
+  uintptr_t tl[];
+};
+
+/**
+ * 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 {
+  struct object_size size;
+  size_t fwd;
+  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
+ *     │              │
+ *     │              │
+ *     │    objects   │
+ *     │              │
+ *     │              │
+ *     └──────────────┘ ←── Bottom
+ *
+ * The layout of both regions are defined by the four labelled pointers, so we
+ * define them.
+ */
+uintptr_t nursery_bottom, nursery_next, nursery_limit, nursery_top;
+uintptr_t young_heap_bottom, young_heap_next, young_heap_limit, young_heap_top;
+
+/**
+ * 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];
+
+void gc_init(void) {
+  // Allocate the nursery and young-heap.
+  nursery_bottom = nursery_next =
+      (uintptr_t)malloc(L1D_SIZE * NURSERY_L1D_SIZE_FACTOR);
+  assume(nursery_bottom);
+  young_heap_bottom = young_heap_next =
+      (uintptr_t)malloc(L3_SIZE * YOUNG_HEAP_L3_SIZE_FACTOR);
+  assume(young_heap_bottom);
+
+  // 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];
+  }
+}