Pointer reversal, but it's busted...

3 files changed, 128 insertions, 34 deletions

diff --git a/src/gc/gen3.c b/src/gc/gen3.c
index 09fa452..6a35611 100644
--- a/src/gc/gen3.c
+++ b/src/gc/gen3.c
@@ -101,14 +101,6 @@ static size_t object_size_total_slots(const struct object_size 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) {
diff --git a/src/gc/sms.c b/src/gc/sms.c
index dcee0c1..6261dc1 100644
--- a/src/gc/sms.c
+++ b/src/gc/sms.c
@@ -1,5 +1,6 @@
 #include "../gc.h"
 #include "../util.h"
+#include <assert.h>
 #include <inttypes.h>
 #include <stdio.h>
 #include <stdlib.h>
@@ -10,11 +11,15 @@ struct object_header {
   bool is_compiled_function : 1;
   int rsvd : 1;
   uint16_t untraced_slot_count : 13;
-  uint16_t value_slot_count;
+  uintptr_t saved_tag : 3;
+  uint16_t value_slot_count : 13;
   struct object_header *next;
   uintptr_t slots[];
 };
 
+static_assert(sizeof(struct object_header) == 2 * sizeof(uintptr_t),
+              "sizeof(struct object_header) == 2 * sizeof(uintptr_t)");
+
 /**
  * A singly-linked list of live objects.
  */
@@ -48,12 +53,16 @@ static const struct object_header *hdrc(const void *ptr) {
 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 the initial value wasn't a pointer to an unmarked object, we can bail
+  // out quickly. (This makes our loop invariant simpler.)
   if (!is_ptr(initial_value))
     return;
   struct object *obj = untag_ptr(initial_value);
   if (!obj)
     return;
+  struct object_header *header = hdr(obj);
+  if (header->mark)
+    return;
 
   // Otherwise, we do a traversal starting at the value, doing pointer reversal
   // to avoid recursion.
@@ -64,34 +73,125 @@ static void gc_mark(const struct value initial_value) {
   // 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.
+  // In pointer reversal, instead of using that space, we store a pointer to the
+  // object we came from in a local variable, prev. We encode the index of the
+  // slot we came from by replacing the tag in that slot with TAG_GC_INTERNAL.
+  // The tag that was there before is saved in the header's saved_tag field.
+  // This allows searching for the slot.
+  //
+  // From prev and saved_tag, we can reconstruct the value of the slot, so we
+  // have the freedom to use the non-tag bits of the slot for whatever we want.
+  // If, when we go into an object, we store the _old_ value of prev in that
+  // slot, we have space to store the object we're coming from in prev. This
+  // way, we don't need an auxiliary stack.
+  //
+  // We define the invariants in terms of the tricolor abstraction: the heap
+  // starts white, objects become gray as we traverse them, and finally become
+  // black after they've been traversed.
+  //
+  // - A white object does not have its mark bit set.
+  // - A gray object has its mark bit set, and is either pointed to by obj, or
+  //   is in the prev linked list.
+  // - A black object has its mark bit set, but is not pointed to by obj, nor is
+  //   it in the prev linked list.
   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.
+    // INVARIANT: obj points to a white object that we're about to make gray.
+    // Since it's white, none of its fields should have the tag TAG_GC_INTERNAL,
+    // so it shouldn't have a saved tag either.
+    assume(!header->mark);
+    assume(header->saved_tag == 0);
 
-      // Check the object's fields, looking for one that
+    // Mark the object, making it gray.
+    header->mark = true;
 
-      todo("gc_mark 1");
+    // Search for a field containing a pointer to a white object.
+    size_t i;
+    struct value *slot;
+    struct object *slot_ptr;
+    for (i = 0; i < header->value_slot_count; i++) {
+      slot = (struct value *)&header->slots[i];
+      if (!is_ptr(*slot))
+        continue;
+      slot_ptr = untag_ptr(*slot);
+      if (!slot_ptr)
+        continue;
+      if (hdrc(slot_ptr)->mark)
+        continue;
+      break;
     }
-    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]);
-  */
+    // If we found one, we traverse into it.
+    if (i != header->value_slot_count) {
+      header->saved_tag = get_tag(*slot);
+      *slot = tag_ptr(prev, TAG_GC_INTERNAL);
+      prev = obj;
+      obj = slot_ptr;
+      header = hdr(obj);
+      continue;
+    }
+
+    // If didn't find one, we can make this object black by popping the stack.
+    // We need to continue popping the stack until we have another gray object
+    // in obj.
+    for (;;) {
+      // INVARIANT: The object is gray, but is about to become black.
+
+      // If this was the object we started traversal with, we're actually done!
+      if (!prev)
+        return;
+
+      // Compute the value to restore into the slot.
+      header = hdr(prev);
+      struct value slot_value = tag_ptr(obj, header->saved_tag);
+
+      // Move prev into obj.
+      obj = prev;
+
+      // Find the slot of obj with TAG_GC_INTERNAL.
+      for (i = 0; i < header->value_slot_count; i++) {
+        slot = (struct value *)&header->slots[i];
+        // This is get_tag, but that function doesn't allow TAG_GC_INTERNAL.
+        if ((slot->bits & 0b111) == TAG_GC_INTERNAL)
+          break;
+      }
+      assume(i != header->value_slot_count);
+
+      // Use the value stored there to restore the old value of prev, and write
+      // its old value back to it. This is effectively what's in untag_ptr, but
+      // that function doesn't allow TAG_GC_INTERNAL.
+      prev = (struct object *)((uintptr_t)slot->bits & ~0b111);
+      *slot = slot_value;
+
+      // The old obj is now black. We need to determine if the new obj has any
+      // more references to white objects, or if instead it should become black
+      // too.
+      for (i += 1; i < header->value_slot_count; i++) {
+        slot = (struct value *)&header->slots[i];
+        if (!is_ptr(*slot))
+          continue;
+        slot_ptr = untag_ptr(*slot);
+        if (!slot_ptr)
+          continue;
+        if (hdrc(slot_ptr)->mark)
+          continue;
+        break;
+      }
+
+      // If the object had no more references to white objects, we can make it
+      // black with this same loop.
+      if (i == header->value_slot_count)
+        continue;
+
+      // Otherwise, we traverse into the object we found.
+      header->saved_tag = get_tag(*slot);
+      *slot = tag_ptr(prev, TAG_GC_INTERNAL);
+      prev = obj;
+      obj = slot_ptr;
+      header = hdr(obj);
+      break;
+    }
+  }
 }
 
 static void gc_sweep(void) {
@@ -124,7 +224,7 @@ void gc_collect(void) {
 }
 
 struct object *gc_alloc(size_t value_slot_count, size_t untraced_slot_count) {
-  assume(value_slot_count < (1 << 16));
+  assume(value_slot_count < (1 << 13));
   assume(untraced_slot_count < (1 << 13));
 
   const size_t total_bytes =
diff --git a/src/value.c b/src/value.c
index b4e22a9..eacc21c 100644
--- a/src/value.c
+++ b/src/value.c
@@ -133,7 +133,9 @@ enum value_tag get_tag(struct value value) {
 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(tag == TAG_BIGINT_OR_NIL || tag == TAG_BUILTIN_OBJECT ||
+         tag == TAG_SIMPLE_ARRAY || tag == TAG_STANDARD_OBJECT ||
+         tag == TAG_GC_INTERNAL);
   assume(((uintptr_t)obj & 0b111) == 0);
   return (struct value){.bits = (uintptr_t)obj | tag};
 }