new simpler GC

14 files changed, 1128 insertions, 280 deletions

diff --git a/src/Makefile b/src/Makefile
index 0f4841b..e9d49c7 100644
--- a/src/Makefile
+++ b/src/Makefile
@@ -2,11 +2,15 @@ SRCS = $(sort $(wildcard $(srcdir)/*.c))
 OBJS = $(patsubst $(srcdir)/%.c,obj/%.o,$(SRCS))
 DEPS = $(patsubst $(srcdir)/%.c,obj/%.d,$(SRCS))
 
+gc_impl = sms
+
 CFLAGS =
 CPPFLAGS =
 LDFLAGS =
 
-CFLAGS_AUTO = -fdata-sections -ffunction-sections -flto -g -O3 -std=c11 -Wall -Werror=implicit-function-declaration
+# CFLAGS_AUTO = -fdata-sections -ffunction-sections -flto -g -O3 -std=c11 -Wall -Werror=implicit-function-declaration
+# CFLAGS_AUTO = -g -Og -std=c11 -Wall -Werror=implicit-function-declaration
+CFLAGS_AUTO = -flto -g -Og -std=c11 -Wall -Werror=implicit-function-declaration
 LDFLAGS_AUTO =
 LDLIBS_AUTO = -lm
 
@@ -26,7 +30,7 @@ else
 
 include $(srcdir)/platform/$(platform).mk
 
-imb3.elf: $(OBJS) obj/gc/gc.o obj/platform/$(platform).o
+imb3.elf: $(OBJS) obj/gc/$(gc_impl).o obj/platform/$(platform).o
 	$(CC) $(CFLAGS_ALL) $(LDFLAGS_ALL) -o $@ $^ $(LDLIBS_ALL)
 
 obj/%.o: $(srcdir)/%.c
diff --git a/src/gc.h b/src/gc.h
index d7ce8b0..8acaacc 100644
--- a/src/gc.h
+++ b/src/gc.h
@@ -21,4 +21,9 @@ void gc_write_value_slot(struct object *, size_t, struct value);
 void gc_write_untraced_slot(struct object *, size_t, uintptr_t);
 void gc_write_untraced_byte(struct object *, size_t, uint8_t);
 
+void gc_root_push(struct value *);
+void gc_root_pop(void);
+
+void gc_debug(void);
+
 #endif // IMB3_GC_H
diff --git a/src/gc/gc.c b/src/gc/gc.c
deleted file mode 100644
index 1c0daec..0000000
--- a/src/gc/gc.c
+++ /dev/null
@@ -1,266 +0,0 @@
-#include "../gc.h"
-#include "../platform.h"
-#include "../util.h"
-#include <stdbool.h>
-#include <stddef.h>
-#include <stdint.h>
-#include <stdlib.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(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(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;
-  }
-}
-
-/**
- * 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 *obj) {
-  return object_size_value_slots(((struct object_size *)obj)[-1]);
-}
-
-/**
- * Returns the number of untraced slots the object has.
- */
-static size_t object_untraced_slots(const struct object *obj) {
-  return object_size_untraced_slots(((struct object_size *)obj)[-1]);
-}
-
-/**
- * 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 {
-  size_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
- *     │              │
- *     │              │
- *     │    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(get_l1d_size() * NURSERY_L1D_SIZE_FACTOR);
-  assume(nursery_bottom);
-  young_heap_bottom = young_heap_next =
-      (uintptr_t)malloc(get_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];
-  }
-}
-
-struct object *gc_alloc(size_t value_slot_count, size_t untraced_slot_count) {
-  todo("gc_alloc");
-}
-
-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");
-}
-
-struct value gc_read_value_slot(const struct object *obj, size_t slot_index) {
-  assume(slot_index < object_value_slots(obj));
-  todo("gc_read_value_slot");
-}
-
-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) {
-  assume(slot_index < object_value_slots(obj));
-  todo("gc_write_value_slot");
-}
-
-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");
-}
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);
+}
diff --git a/src/gc/sms.c b/src/gc/sms.c
new file mode 100644
index 0000000..dcee0c1
--- /dev/null
+++ b/src/gc/sms.c
@@ -0,0 +1,205 @@
+#include "../gc.h"
+#include "../util.h"
+#include <inttypes.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+struct object_header {
+  bool mark : 1;
+  bool is_compiled_function : 1;
+  int rsvd : 1;
+  uint16_t untraced_slot_count : 13;
+  uint16_t value_slot_count;
+  struct object_header *next;
+  uintptr_t slots[];
+};
+
+/**
+ * A singly-linked list of live objects.
+ */
+static struct object_header *live_objects = NULL;
+
+/**
+ * The number of bytes of live data, including object headers.
+ */
+static size_t live_bytes = 0;
+
+/**
+ * The number of bytes of live data to reach before collecting.
+ */
+static size_t limit_bytes = 80 * 1024 * 1024;
+
+/**
+ * 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;
+
+static struct object_header *hdr(void *ptr) {
+  return &((struct object_header *)ptr)[-1];
+}
+
+static const struct object_header *hdrc(const void *ptr) {
+  return &((const struct object_header *)ptr)[-1];
+}
+
+void gc_init(void) {}
+
+static void gc_mark(const struct value initial_value) {
+  // If the initial value just wasn't a pointer, we don't need to mark it.
+  if (!is_ptr(initial_value))
+    return;
+  struct object *obj = untag_ptr(initial_value);
+  if (!obj)
+    return;
+
+  // Otherwise, we do a traversal starting at the value, doing pointer reversal
+  // to avoid recursion.
+  //
+  // In simple recursive marking, we store where we came from in the call
+  // stack. Each stack frame effectively stores:
+  //
+  // 1. the pointer to the object we came from
+  // 2. the index of the slot we came from in that object
+  //
+  // In pointer reversal, instead of using that space, we store where we came
+  // from in the previous object itself. This relies on having the
+  // TAG_GC_INTERNAL tag.
+  struct object *prev = NULL;
+  while (obj) {
+    // Check if the object has already been marked. If so, we don't need to
+    // traverse it.
+    struct object_header *header = hdr(obj);
+    if (!header->mark) {
+      // Invariant: We've just started traversing this object, so none of its
+      // fields should have TAG_GC_INTERNAL.
+
+      // Check the object's fields, looking for one that
+
+      todo("gc_mark 1");
+    }
+    todo("gc_mark 2");
+  }
+
+  /*
+  struct object_header *header = hdr(obj);
+  if (header->mark)
+    return;
+  header->mark = true;
+  struct value *slots = (struct value *)&header->slots[0];
+  for (size_t i = 0; i < header->value_slot_count; i++)
+    gc_mark(slots[i]);
+  */
+}
+
+static void gc_sweep(void) {
+  struct object_header **head = &live_objects, *header;
+  while ((header = *head)) {
+    if ((*head)->mark) {
+      (*head)->mark = false;
+      head = &header->next;
+    } else {
+      *head = header->next;
+      const size_t total_bytes =
+          sizeof(struct object_header) +
+          (header->value_slot_count + header->untraced_slot_count) *
+              sizeof(uintptr_t);
+      free(header);
+      live_bytes -= total_bytes;
+    }
+  }
+}
+
+void gc_collect(void) {
+  fprintf(stderr, "gc_collect()... ");
+  for (size_t i = 0; i < root_stack_depth; i++)
+    gc_mark(*root_stack[i]);
+  const size_t before = live_bytes;
+  gc_sweep();
+  const size_t after = live_bytes;
+  fprintf(stderr, "collected %zu bytes\n", before - after);
+  assume(live_bytes < limit_bytes);
+}
+
+struct object *gc_alloc(size_t value_slot_count, size_t untraced_slot_count) {
+  assume(value_slot_count < (1 << 16));
+  assume(untraced_slot_count < (1 << 13));
+
+  const size_t total_bytes =
+      sizeof(struct object_header) +
+      (value_slot_count + untraced_slot_count) * sizeof(uintptr_t);
+  if ((live_bytes += total_bytes) >= limit_bytes)
+    gc_collect();
+  struct object_header *header = malloc(total_bytes);
+  if (!header) {
+    gc_collect();
+    header = malloc(total_bytes);
+    if (!header)
+      todo("OOM");
+  }
+  memset(header, 0, total_bytes);
+  header->value_slot_count = value_slot_count;
+  header->untraced_slot_count = untraced_slot_count;
+  header->next = live_objects;
+  live_objects = header;
+  return (struct object *)&header->slots[0];
+}
+
+struct object *gc_alloc_compiled_function(size_t value_slot_count,
+                                          size_t untraced_slot_count) {
+  struct object *obj = gc_alloc(value_slot_count, untraced_slot_count);
+  hdr(obj)->is_compiled_function = true;
+  return obj;
+}
+
+struct object *gc_alloc_hashtable_eq(size_t value_slot_count,
+                                     size_t untraced_slot_count) {
+  return gc_alloc(value_slot_count, untraced_slot_count);
+}
+
+struct value gc_read_value_slot(const struct object *obj, size_t slot_index) {
+  assume(slot_index < hdrc(obj)->value_slot_count);
+  struct value *slots = (struct value *)obj;
+  struct value value = slots[slot_index];
+  return value;
+}
+
+uintptr_t gc_read_untraced_slot(const struct object *obj, size_t slot_index) {
+  assume(slot_index < hdrc(obj)->untraced_slot_count);
+  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) {
+  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 < hdrc(obj)->untraced_slot_count);
+  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, "live bytes = %zu\n", live_bytes); }
diff --git a/src/main.c b/src/main.c
deleted file mode 100644
index 2f6fcf2..0000000
--- a/src/main.c
+++ /dev/null
@@ -1,6 +0,0 @@
-#include "gc.h"
-#include "util.h"
-
-int main(int argc, char **argv) {
-  return 0;
-}
diff --git a/src/platform.h b/src/platform.h
index 2dbfd26..0bb6bbe 100644
--- a/src/platform.h
+++ b/src/platform.h
@@ -2,11 +2,15 @@
 #define IMB3_PLATFORM_H
 
 #include <stddef.h>
+#include <stdint.h>
 #include <stdnoreturn.h>
 
 size_t get_l1d_size(void);
 size_t get_l3_size(void);
 
+uintptr_t alloc_gc_region(size_t);
+void clear_gc_region(uintptr_t, size_t);
+
 void panic_begin(void);
 noreturn void panic_end(void);
 
diff --git a/src/platform/3ds.c b/src/platform/3ds.c
index 5683422..5566121 100644
--- a/src/platform/3ds.c
+++ b/src/platform/3ds.c
@@ -6,6 +6,7 @@
 #include <inttypes.h>
 #include <stdio.h>
 #include <stdlib.h>
+#include <string.h>
 
 /**
  * These cache-size details are from
@@ -16,6 +17,16 @@
 size_t get_l1d_size(void) { return 16 * 1024; }
 size_t get_l3_size(void) { return 2 * 1024 * 1024; }
 
+uintptr_t alloc_gc_region(size_t size) {
+  void *ptr = malloc(size);
+  assume(ptr != NULL);
+  return (uintptr_t)ptr;
+}
+
+void clear_gc_region(uintptr_t addr, size_t size) {
+  memset((void *)addr, 0, size);
+}
+
 void panic_begin(void) { consoleInit(GFX_TOP, NULL); }
 
 noreturn void panic_end(void) {
@@ -35,6 +46,51 @@ noreturn void panic_end(void) {
   exit(1);
 }
 
+static void gc_test(void) {
+  gc_debug();
+
+  const struct value ZERO = {.bits = (0 << 2) | TAG_FIXNUM};
+
+  struct object *values = gc_alloc(64, 0);
+  struct object *value_slot_counts = gc_alloc(64, 0);
+  gc_root_push(&values);
+  gc_root_push(&value_slot_counts);
+
+  for (size_t i = 0; i < 10000000; i++) {
+    if ((rand() & 0b11) == 0) {
+      size_t value_slot_count = rand() & 63;
+      if (!value_slot_count)
+        value_slot_count = 1;
+      size_t untraced_slot_count = rand() & 63;
+      struct value value =
+          alloc_builtin_object(ZERO, value_slot_count, untraced_slot_count);
+      size_t i = rand() % 63;
+      gc_write_value_slot(values, i, value);
+      gc_write_value_slot(value_slot_counts, i,
+                          integer_of_int(value_slot_count));
+    } else {
+      size_t i = rand() & 63;
+      struct value value = gc_read_value_slot(values, i);
+      struct value value_slot_count_value =
+          gc_read_value_slot(value_slot_counts, i);
+      if (!value.bits)
+        continue;
+      assume(get_tag(value) == TAG_BUILTIN_OBJECT);
+      assume(get_tag(value_slot_count_value) == TAG_FIXNUM);
+      struct object *obj = untag_ptr(value);
+      intptr_t value_slot_count = untag_fixnum(value_slot_count_value);
+      size_t j = rand() % value_slot_count;
+      size_t k = rand() % 63;
+      gc_write_value_slot(obj, j, gc_read_value_slot(values, k));
+    }
+  }
+
+  gc_root_pop();
+  gc_root_pop();
+
+  gc_debug();
+}
+
 int main(int argc, char **argv) {
   gfxInit(GSP_BGR8_OES, GSP_BGR8_OES, false);
 
@@ -66,7 +122,7 @@ int main(int argc, char **argv) {
     if (kDown & KEY_START)
       break; // break in order to return to hbmenu
     if (kDown & KEY_A)
-      todo("GM");
+      gc_test();
 
     circlePosition pos;
     hidCircleRead(&pos);
diff --git a/src/platform/3ds.mk b/src/platform/3ds.mk
index cbe7e0b..0b0d2f2 100644
--- a/src/platform/3ds.mk
+++ b/src/platform/3ds.mk
@@ -15,4 +15,4 @@ all: imb3.3dsx
 .PHONY: 3dslink
 
 imb3.3dsx: imb3.elf
-	3dsxtool $< $@
+	$(DEVKITPRO)/../../bin/3dsxtool $< $@
diff --git a/src/platform/linux.c b/src/platform/linux.c
index e69de29..3305869 100644
--- a/src/platform/linux.c
+++ b/src/platform/linux.c
@@ -0,0 +1,158 @@
+#define _GNU_SOURCE
+#include "../gc.h"
+#include "../platform.h"
+#include "../util.h"
+#include <errno.h>
+#include <fcntl.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <sys/mman.h>
+#include <unistd.h>
+
+int main(int argc, char **argv) {
+  // As a test of the garbage collector, we're doing a bunch of random
+  // mutations.
+  gc_init();
+  srand(0);
+  gc_debug();
+
+  const struct value ZERO = {.bits = (0 << 2) | TAG_FIXNUM};
+
+  struct object *values = gc_alloc(64, 0);
+  struct object *value_slot_counts = gc_alloc(64, 0);
+  gc_root_push(&values);
+  gc_root_push(&value_slot_counts);
+
+  for (size_t i = 0; i < 1000000; i++) {
+    if ((rand() & 0b11) == 0) {
+      size_t value_slot_count = 3;
+      if (!value_slot_count)
+        value_slot_count = 1;
+      size_t untraced_slot_count = rand() & 255;
+      struct value value =
+          alloc_builtin_object(ZERO, value_slot_count, untraced_slot_count);
+      size_t i = rand() % 63;
+      gc_write_value_slot(values, i, value);
+      gc_write_value_slot(value_slot_counts, i,
+                          integer_of_int(value_slot_count));
+    } else {
+      size_t i = rand() & 63;
+      struct value value = gc_read_value_slot(values, i);
+      struct value value_slot_count_value =
+          gc_read_value_slot(value_slot_counts, i);
+      if (!value.bits)
+        continue;
+      assume(get_tag(value) == TAG_BUILTIN_OBJECT);
+      assume(get_tag(value_slot_count_value) == TAG_FIXNUM);
+      struct object *obj = untag_ptr(value);
+      intptr_t value_slot_count = untag_fixnum(value_slot_count_value);
+      size_t j = rand() % value_slot_count;
+      size_t k = rand() % 63;
+      gc_write_value_slot(obj, j, gc_read_value_slot(values, k));
+    }
+  }
+
+  gc_debug();
+  return 0;
+}
+
+void panic_begin(void) {}
+noreturn void panic_end(void) { abort(); }
+
+static size_t read_cache_size(const char *path) {
+  int fd = open(path, O_RDONLY | O_CLOEXEC);
+  if (fd == -1)
+    fprintf(stderr, "open %s: %s\n", path, strerror(errno)), abort();
+
+  char buf[4096];
+  size_t len = 0;
+  for (;;) {
+    ssize_t ret = read(fd, &buf[len], sizeof(buf) - len);
+    if (ret == 0)
+      break;
+    else if (ret < 0 && errno == EINTR)
+      continue;
+    else if (ret < 0)
+      fprintf(stderr, "read %s: %s\n", path, strerror(errno)), abort();
+    else
+      len += ret;
+  }
+
+  if (close(fd))
+    fprintf(stderr, "close %s: %s\n", path, strerror(errno)), abort();
+
+  size_t i = 0, out = 0;
+  while (i < len) {
+    char ch = buf[i];
+    if ('0' <= ch && ch <= '9') {
+      out = 10 * out + (ch - '0');
+      i++;
+    } else {
+      break;
+    }
+  }
+  if (i < len) {
+    char ch = buf[i];
+    if (ch == 'K') {
+      out *= 1024;
+      i++;
+    } else if (ch == 'M') {
+      out *= 1024 * 1024;
+      i++;
+    }
+  }
+  if (i < len && buf[i] == '\n')
+    i++;
+  if (i != len) {
+    fprintf(stderr, "invalid cache size in %s: [", path);
+    for (size_t j = 0; j < len; j++) {
+      fprintf(stderr, "%s", i == j ? "|" : j ? " " : "");
+      char ch = buf[j];
+      if (' ' <= ch && ch <= '~' && ch != '\'' && ch != '\\')
+        fprintf(stderr, "'%c'", ch);
+      else if (ch == '\n')
+        fprintf(stderr, "'\\n'");
+      else if (ch == '\'')
+        fprintf(stderr, "\"'\"");
+      else if (ch == '\\')
+        fprintf(stderr, "'\\\\'");
+      else
+        fprintf(stderr, "%02hhx", buf[j]);
+    }
+    fprintf(stderr, "]\n");
+    abort();
+  }
+
+  return out;
+}
+
+size_t get_l1d_size(void) {
+  return read_cache_size("/sys/devices/system/cpu/cpu0/cache/index0/size");
+}
+
+size_t get_l3_size(void) {
+  return read_cache_size("/sys/devices/system/cpu/cpu0/cache/index2/size");
+}
+
+uintptr_t alloc_gc_region(size_t size) {
+  static uintptr_t base_ptr = 0x10000;
+  static size_t page_size = 0;
+  if (!page_size)
+    page_size = sysconf(_SC_PAGE_SIZE);
+
+  void *ptr = mmap((void *)base_ptr, size, PROT_READ | PROT_WRITE,
+                   MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
+  if (ptr == MAP_FAILED)
+    perror("alloc_gc_region"), exit(111);
+  base_ptr =
+      (((uintptr_t)ptr + size + page_size - 1) & ~(page_size - 1)) + page_size;
+  return (uintptr_t)ptr;
+}
+
+void clear_gc_region(uintptr_t addr, size_t size) {
+  void *new_ptr = mmap((void *)addr, size, PROT_READ | PROT_WRITE,
+                       MAP_PRIVATE | MAP_ANONYMOUS | MAP_FIXED, -1, 0);
+  if (new_ptr == MAP_FAILED)
+    perror("clear_gc_region"), exit(111);
+}
diff --git a/src/util.c b/src/util.c
index 14a213a..b512296 100644
--- a/src/util.c
+++ b/src/util.c
@@ -1,11 +1,13 @@
 #include "util.h"
+#include "gc.h"
 #include "platform.h"
 #include <stdarg.h>
 #include <stdio.h>
 
 noreturn void assume__failed(const char *file, int line, const char *expr) {
   panic_begin();
-  fprintf(stderr, "%s:%d: assertion failed: %s\n", file, line, expr);
+  fprintf(stderr, "%s:%d: assertion failed: %s\n\n", file, line, expr);
+  gc_debug();
   panic_end();
 }
 
@@ -16,5 +18,20 @@ noreturn void todo__impl(const char *file, int line, const char *fmt, ...) {
   va_start(ap, fmt);
   vprintf(fmt, ap);
   va_end(ap);
+  printf("\n");
+  gc_debug();
+  panic_end();
+}
+
+noreturn void unreachable__impl(const char *file, int line, const char *fmt,
+                                ...) {
+  panic_begin();
+  printf("%s:%d: unreachable code entered: ", file, line);
+  va_list ap;
+  va_start(ap, fmt);
+  vprintf(fmt, ap);
+  va_end(ap);
+  printf("\n");
+  gc_debug();
   panic_end();
 }
diff --git a/src/util.h b/src/util.h
index 569054b..4384fcd 100644
--- a/src/util.h
+++ b/src/util.h
@@ -28,4 +28,9 @@ todo__impl(const char *file, int line, const char *fmt, ...);
 
 #define todo(...) todo__impl(__FILE__, __LINE__, __VA_ARGS__)
 
+__attribute__((format(printf, 3, 4))) noreturn void
+unreachable__impl(const char *file, int line, const char *fmt, ...);
+
+#define unreachable(...) unreachable__impl(__FILE__, __LINE__, __VA_ARGS__)
+
 #endif // IMB3_UTIL_H
diff --git a/src/value.c b/src/value.c
index 07af689..b4e22a9 100644
--- a/src/value.c
+++ b/src/value.c
@@ -1,5 +1,11 @@
 #include "value.h"
 #include "gc.h"
+#include "util.h"
+#include <inttypes.h>
+
+static const intptr_t FIXNUM_MIN = -((intptr_t)1 << (4 * sizeof(void *) - 3)),
+                      FIXNUM_MAX =
+                          ((intptr_t)1 << (4 * sizeof(void *) - 3)) - 1;
 
 enum builtin {
   BUILTIN_BUILTIN_CLASS_BIGNUM,
@@ -83,6 +89,8 @@ static struct value pop(void) { return (struct value){.bits = 0}; }
 
 struct value alloc_builtin_object(struct value class, size_t value_slot_count,
                                   size_t untraced_slot_count) {
+  assume(value_slot_count != 0);
+
   struct object *obj;
   if (class.bits == builtins[BUILTIN_BUILTIN_CLASS_COMPILED_FUNCTION].bits)
     obj = gc_alloc_compiled_function(value_slot_count, untraced_slot_count);
@@ -96,6 +104,51 @@ struct value alloc_builtin_object(struct value class, size_t value_slot_count,
   };
 }
 
+struct value integer_of_int(intptr_t n) {
+  if (FIXNUM_MIN <= n && n <= FIXNUM_MAX) {
+    struct value value = (struct value){.bits = (n << 2) | TAG_FIXNUM};
+    assume(untag_fixnum(value) == n);
+    return value;
+  } else {
+    todo("integer_of_int: bigint %" PRIdPTR, n);
+  }
+}
+
+enum value_tag get_tag(struct value value) {
+  uintptr_t low_bits = value.bits & 0b111;
+  switch (low_bits) {
+  case 0b000:
+  case 0b010:
+  case 0b100:
+  case 0b110:
+    return (enum value_tag)low_bits;
+  case 0b001:
+  case 0b101:
+    return TAG_FIXNUM;
+  default:
+    unreachable("invalid tag for value %p", (void *)value.bits);
+  }
+}
+
+bool is_ptr(struct value value) { return !(value.bits & 1); }
+
+struct value tag_ptr(struct object *obj, enum value_tag tag) {
+  assume((tag & 0b1) == 0);
+  assume(((uintptr_t)obj & 0b111) == 0);
+  return (struct value){.bits = (uintptr_t)obj | tag};
+}
+
+intptr_t untag_fixnum(struct value value) {
+  assume(get_tag(value) == TAG_FIXNUM);
+  intptr_t bits = value.bits;
+  return bits >> 2;
+}
+
+struct object *untag_ptr(struct value value) {
+  assume(is_ptr(value));
+  return (struct object *)((uintptr_t)value.bits & ~0b111);
+}
+
 void bootstrap(void) {
   // Since it is its own class, standard-class needs to be constructed
   // manually.
diff --git a/src/value.h b/src/value.h
index 3795486..1331d9d 100644
--- a/src/value.h
+++ b/src/value.h
@@ -1,9 +1,15 @@
 #ifndef IMB3_VALUE_H
 #define IMB3_VALUE_H
 
+#include <stdbool.h>
 #include <stddef.h>
 #include <stdint.h>
 
+/**
+ * Declared "for real" in gc.h.
+ */
+struct object;
+
 struct value {
   uintptr_t bits;
 };
@@ -18,7 +24,7 @@ enum value_tag {
    * Fixnums, i.e. integers that are stored directly in the value rather than
    * being pointed to. This is a two-bit tag rather than a three-bit tag...
    */
-  VALUE_FIXNUM = 0b01,
+  TAG_FIXNUM = 0b01,
 
   /**
    * A builtin-object.
@@ -34,13 +40,54 @@ enum value_tag {
    * A standard-object, effectively a pair of a class and a slot array.
    */
   TAG_STANDARD_OBJECT = 0b110,
+
+  /**
+   * An tag that is _invalid_ for values, but may be used by the internals of
+   * the garbage collector.
+   */
+  TAG_GC_INTERNAL = 0b111,
 };
 
 /**
+ * The nil constant.
+ */
+static const struct value NIL = {.bits = 0};
+
+/**
  * Allocates a builtin-object with the given class and slot count.
  */
-struct value make_builtin_object(struct value class, size_t value_slot_count,
-                                 size_t untraced_slot_count);
+struct value alloc_builtin_object(struct value class, size_t value_slot_count,
+                                  size_t untraced_slot_count);
+
+/**
+ * Stores an intptr_t as a fixnum or a bignum.
+ */
+struct value integer_of_int(intptr_t);
+
+/**
+ * Returns the tag of a value.
+ */
+enum value_tag get_tag(struct value);
+
+/**
+ * Returns whether a value is a pointer.
+ */
+bool is_ptr(struct value);
+
+/**
+ * Tags a pointer.
+ */
+struct value tag_ptr(struct object *, enum value_tag);
+
+/**
+ * Untags a fixnum.
+ */
+intptr_t untag_fixnum(struct value);
+
+/**
+ * Untags a pointer.
+ */
+struct object *untag_ptr(struct value);
 
 /**
  * Bootstraps the class heirarchy. This should only be called once.