From 6f9c0c5afb2877c0e95586a6db123029eba86b9b Mon Sep 17 00:00:00 2001 From: Nathan Ringo Date: Thu, 28 Nov 2024 19:45:37 -0600 Subject: Pointer reversal, but it's busted... --- src/gc/sms.c | 150 +++++++++++++++++++++++++++++++++++++++++++++++++---------- 1 file changed, 125 insertions(+), 25 deletions(-) (limited to 'src/gc/sms.c') 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 #include #include #include @@ -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 = -- cgit v1.2.3