summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/gc/gen3.c8
-rw-r--r--src/gc/sms.c150
-rw-r--r--src/value.c4
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};
}
generated by cgit v1.2.3 (git 2.25.1) at 2025-04-28 17:19:36 +0000