First step at garbage collection

We now visit all objects and change the tag of those which are unreachable, to CHUNK_TAG_FREE.
Next step will be to implement compaction to combine all free chunks at the end of the memory
space.

FossilOrigin-Name: f8641c857b5d430f45d7c1f36fb00866659a5ea78f36ee0535c9166060ea0e19

3 files changed, 128 insertions, 4 deletions

diff --git a/src/lib/aplwc_internal.h b/src/lib/aplwc_internal.h
index b87cfad..1637ef2 100644
--- a/src/lib/aplwc_internal.h
+++ b/src/lib/aplwc_internal.h
@@ -19,6 +19,7 @@ struct aplwc {
 	size_t size;
 	struct memory_ptr_frame *memptrs;
 	struct root_ptr *rootptrs;
+	unsigned int reachable_bit:1;
 };
 
 struct memory_ptr_frame {
diff --git a/src/lib/main.c b/src/lib/main.c
index 4571c78..8aceded 100644
--- a/src/lib/main.c
+++ b/src/lib/main.c
@@ -19,6 +19,7 @@ aplwc_new(struct aplwc_fns fns, enum aplwc_rc *rcp)
 		goto end;
 	}
 
+	aplwc->modules = NULL;
 	aplwc->fns = fns;
 	memory_init(aplwc);
 
diff --git a/src/lib/memory.c b/src/lib/memory.c
index 694a31b..d540739 100644
--- a/src/lib/memory.c
+++ b/src/lib/memory.c
@@ -14,8 +14,10 @@ enum chunk_tag {
 
 struct chunk {
 	struct chunk *next;
+	struct chunk *stack;
 	size_t size;
 	enum chunk_tag tag;
+	unsigned int reachable:1;
 	uint8_t *data;
 };
 
@@ -27,6 +29,7 @@ memory_init(struct aplwc *aplwc)
 	aplwc->size = 0;
 	aplwc->memptrs = NULL;
 	aplwc->rootptrs = NULL;
+	aplwc->reachable_bit = 0;
 }
 
 void
@@ -61,6 +64,8 @@ fixrefs(struct aplwc *aplwc, uint8_t *new, uint8_t *old)
 		sub = old-new;
 	}
 
+	FIX(aplwc->modules);
+
 	for(c = (struct chunk *)new; c; c = c->next){
 		FIX(c->next);
 		FIX(c->data);
@@ -130,8 +135,7 @@ grow(struct aplwc *aplwc, size_t extra)
 		fixrefs(aplwc, aligned_data, aplwc->data);
 		if(aplwc->fns.dealloc)
 			aplwc->fns.dealloc(aplwc->unaligned_data);
-		for(free = &head; (*free); free = &(*free)->next)
-			assert((*free)->tag != CHUNK_TAG_FREE);
+		for(free = &head; (*free); free = &(*free)->next);
 	}else
 		free = &head;
 
@@ -141,6 +145,7 @@ grow(struct aplwc *aplwc, size_t extra)
 	(*free)->data = NULL;
 	(*free)->size = aligned_newsize - aplwc->size;
 	(*free)->next = NULL;
+	(*free)->stack = NULL;
 
 	aplwc->unaligned_data = unaligned_data;
 	aplwc->data = aligned_data;
@@ -170,19 +175,132 @@ find_free(struct aplwc *aplwc, size_t min)
 	return c;
 }
 
+static void
+push(struct aplwc *aplwc, struct chunk **stack, void *p)
+{
+	struct chunk *c;
+
+	if(p == NULL)
+		return;
+	c = (struct chunk *)(((uint8_t*)p)-HEADER_SIZE);
+	assert(c->tag != CHUNK_TAG_FREE);
+
+	if(c->reachable == aplwc->reachable_bit)
+		return;
+	
+	assert(c->stack == NULL);
+	c->reachable = aplwc->reachable_bit;
+	c->stack = *stack;
+	*stack = c;
+}
+
+static struct chunk *
+pop(struct chunk **stack)
+{
+	struct chunk *c;
+
+	assert(stack);
+	assert(*stack);
+
+	c = *stack;
+	*stack = c->stack;
+	c->stack = NULL;
+
+	return c;
+}
+
+static void
+collect(struct aplwc *aplwc)
+{
+	struct chunk *c;
+	struct chunk *stack;
+	struct memory_ptr_frame *frame;
+	struct root_ptr *root;
+	size_t i;
+
+	aplwc->reachable_bit = ~aplwc->reachable_bit;
+
+	/* Mark reachable chunks */
+
+	stack = NULL;
+	push(aplwc, &stack, aplwc->modules);
+	
+	for(frame = aplwc->memptrs; frame; frame = frame->link)
+		for(i = 0; i < frame->count; i++)
+			if(frame->ptrs[i])
+				push(aplwc, &stack, *frame->ptrs[i]);
+	
+	for(root = aplwc->rootptrs; root; root = root->link)
+		if(root->ptr)
+			push(aplwc, &stack, root->ptr);
+
+	while(stack){
+		c = pop(&stack);
+#define PUSH(type, ptr) push(aplwc, &stack, ((type *)c->data)->ptr)
+		switch(c->tag){
+		case CHUNK_TAG_APLWC_LINE:
+			PUSH(struct aplwc_line, text);
+			PUSH(struct aplwc_line, tokens);
+			break;
+		case CHUNK_TAG_STRING:
+			break;
+		case CHUNK_TAG_TOKEN_LIST:
+			PUSH(struct token_list, text);
+			break;
+		case CHUNK_TAG_APLWC_VALUE:
+			break;
+		case CHUNK_TAG_APLWC_MODULE:
+			PUSH(struct aplwc_module, name);
+			PUSH(struct aplwc_module, tokens);
+			PUSH(struct aplwc_module, link);
+			break;
+		case CHUNK_TAG_FREE:
+			break;
+		}
+#undef PUSH
+	}
+
+	/* Free chunks not marked */
+	for(c = (struct chunk *)aplwc->data; c; c = c->next){
+		if((c->reachable != aplwc->reachable_bit)){
+			c->tag = CHUNK_TAG_FREE;
+			c->data = NULL;
+		}
+	}
+}
+
+static void
+compact(struct aplwc *aplwc)
+{
+	UNUSED_PARAMETER(aplwc);
+}
+
 static void *
 alloc(struct aplwc *aplwc, size_t size, enum chunk_tag tag)
 {
 	struct chunk *free;
 	struct chunk *new;
 
+	int attempt;
+
+	attempt = 0;
 retry:
 	free = find_free(aplwc, size);
 	if(!free){
-		if(grow(aplwc, size))
+		switch(attempt++){
+		case 0:
+			collect(aplwc);
 			goto retry;
-		else
+		case 1:
+			compact(aplwc);
+			goto retry;
+		case 2:
+			if(grow(aplwc, size))
+				goto retry;
+			/* fall-through */
+		default:
 			return NULL;
+		}
 	}
 
 	assert(free->data == NULL);
@@ -194,11 +312,15 @@ retry:
 		free->tag = CHUNK_TAG_FREE;
 		free->size = new->size - (HEADER_SIZE + size);
 		free->data = NULL;
+		free->stack = NULL;
+		free->next = new->next;
+		new->next = free;
 	}
 
 	new->tag = tag;
 	new->size = sizeof(struct chunk) + size;
 	new->data = ((uint8_t*)new) + sizeof(struct chunk);
+	new->reachable = aplwc->reachable_bit;
 
 	new->data += ((uintptr_t)new->data) % ALIGNMENT;