new simpler GC

1 files changed, 205 insertions, 0 deletions

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