[2f361290c8] The memory manager now knows how to reclaim unreferenced memory.

FossilOrigin-Name: 6bd5d1bb47db13116499d9399573fefc28fb6548ace9297c358c730f10a1a0b0

3 files changed, 217 insertions, 57 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..a53a37e 100644
--- a/src/lib/memory.c
+++ b/src/lib/memory.c
@@ -14,9 +14,10 @@ enum chunk_tag {
 
 struct chunk {
 	struct chunk *next;
+	struct chunk *stack;
 	size_t size;
 	enum chunk_tag tag;
-	uint8_t *data;
+	unsigned int reachable:1;
 };
 
 void
@@ -27,6 +28,7 @@ memory_init(struct aplwc *aplwc)
 	aplwc->size = 0;
 	aplwc->memptrs = NULL;
 	aplwc->rootptrs = NULL;
+	aplwc->reachable_bit = 0;
 }
 
 void
@@ -36,17 +38,58 @@ memory_destroy(struct aplwc *aplwc)
 		aplwc->fns.dealloc(aplwc->unaligned_data);
 }
 
-static void
-fixrefs(struct aplwc *aplwc, uint8_t *new, uint8_t *old)
+void *
+data(struct chunk *c)
 {
-#define FIX(ptr) do{ \
-	if(ptr){ \
-		(ptr) = (void*)(((uint8_t*)(ptr))+add); \
-		(ptr) = (void*)(((uint8_t*)(ptr))-sub); \
+	uint8_t *p;
+
+	p = (uint8_t*)c;
+	return p + HEADER_SIZE;
+}
+
+#define VISIT_FIELD(X, tag, ptr) X(((struct tag *)data(c))->ptr)
+#define VISIT_CHUNK_PTRS(X, c) switch(c->tag){ \
+	case CHUNK_TAG_APLWC_LINE: \
+		VISIT_FIELD(X, aplwc_line, text); \
+		VISIT_FIELD(X, aplwc_line, tokens); \
+		break; \
+	case CHUNK_TAG_STRING: \
+		break; \
+	case CHUNK_TAG_TOKEN_LIST: \
+		VISIT_FIELD(X, token_list, text); \
+		break; \
+	case CHUNK_TAG_APLWC_VALUE: \
+		break; \
+	case CHUNK_TAG_APLWC_MODULE: \
+		VISIT_FIELD(X, aplwc_module, name); \
+		VISIT_FIELD(X, aplwc_module, tokens); \
+		VISIT_FIELD(X, aplwc_module, link); \
+		break; \
+	case CHUNK_TAG_FREE: \
+		break; \
+	}
+#define VISIT_ROOT_PTRS(X) do{ \
+	X(aplwc->modules); \
+	for(frame = aplwc->memptrs; frame; frame = frame->link) \
+		for(i = 0; i < frame->count; i++) \
+			if(frame->ptrs[i]) \
+				X(*frame->ptrs[i]); \
+	for(root = aplwc->rootptrs; root; root = root->link) \
+		if(root->ptr) \
+			X(root->ptr); \
+}while(0)
+
+#define VISIT_ALL_PTRS(X, data) do{ \
+	VISIT_ROOT_PTRS(X); \
+	for(c = (struct chunk *)(data); c; c = c->next){ \
+		X(c->next); \
+		VISIT_CHUNK_PTRS(X, c); \
 	} \
 }while(0)
 
-#define FIX_DATA(type, ptr) FIX(((type *)c->data)->ptr)
+static void
+fixrefs(struct aplwc *aplwc, uint8_t *new, uint8_t *old)
+{
 
 	struct chunk *c;
 	struct memory_ptr_frame *frame;
@@ -61,43 +104,14 @@ fixrefs(struct aplwc *aplwc, uint8_t *new, uint8_t *old)
 		sub = old-new;
 	}
 
-	for(c = (struct chunk *)new; c; c = c->next){
-		FIX(c->next);
-		FIX(c->data);
-
-		switch(c->tag){
-		case CHUNK_TAG_APLWC_LINE:
-			FIX_DATA(struct aplwc_line, text);
-			FIX_DATA(struct aplwc_line, tokens);
-			break;
-		case CHUNK_TAG_STRING:
-			break;
-		case CHUNK_TAG_TOKEN_LIST:
-			FIX_DATA(struct token_list, text);
-			break;
-		case CHUNK_TAG_APLWC_VALUE:
-			break;
-		case CHUNK_TAG_APLWC_MODULE:
-			FIX_DATA(struct aplwc_module, name);
-			FIX_DATA(struct aplwc_module, tokens);
-			FIX_DATA(struct aplwc_module, link);
-			break;
-		case CHUNK_TAG_FREE:
-			break;
-		}
-	}
-
-	for(frame = aplwc->memptrs; frame; frame = frame->link)
-		for(i = 0; i < frame->count; i++)
-			if(frame->ptrs[i])
-				FIX(*frame->ptrs[i]);
-	
-	for(root = aplwc->rootptrs; root; root = root->link)
-		if(root->ptr)
-			FIX(root->ptr);
-
+#define FIX(ptr) do{ \
+	if(ptr){ \
+		(ptr) = (void*)(((uint8_t*)(ptr))+add); \
+		(ptr) = (void*)(((uint8_t*)(ptr))-sub); \
+	} \
+}while(0)
+	VISIT_ALL_PTRS(FIX, new);
 #undef FIX
-#undef FIX_DATA
 }
 
 static enum aplwc_rc
@@ -105,7 +119,7 @@ grow(struct aplwc *aplwc, size_t extra)
 {
 	uint8_t *unaligned_data, *aligned_data;
 	size_t unaligned_newsize, aligned_newsize, adjust;
-	struct chunk **free, *head;
+	struct chunk **free, *head, *last;
 
 	if(aplwc->fns.alloc == NULL)
 		goto error;
@@ -124,6 +138,7 @@ grow(struct aplwc *aplwc, size_t extra)
 
 	assert(aligned_newsize >= (aplwc->size + extra));
 	head = (struct chunk *)aligned_data;
+	last = NULL;
 
 	if(aplwc->data){
 		memmove(aligned_data, aplwc->data, aplwc->size);
@@ -131,16 +146,24 @@ grow(struct aplwc *aplwc, size_t extra)
 		if(aplwc->fns.dealloc)
 			aplwc->fns.dealloc(aplwc->unaligned_data);
 		for(free = &head; (*free); free = &(*free)->next)
-			assert((*free)->tag != CHUNK_TAG_FREE);
+			if((*free)->next)
+				assert((*free)->tag != CHUNK_TAG_FREE);
+			else
+				last = (*free);
 	}else
 		free = &head;
 
-
 	(*free) = (struct chunk *)(aligned_data + aplwc->size);
 	(*free)->tag = CHUNK_TAG_FREE;
-	(*free)->data = NULL;
 	(*free)->size = aligned_newsize - aplwc->size;
 	(*free)->next = NULL;
+	(*free)->stack = NULL;
+
+	if(last && (last->tag == CHUNK_TAG_FREE)){
+		assert(last->next == (*free));
+		last->size += (*free)->size;
+		last->next = NULL;
+	}
 
 	aplwc->unaligned_data = unaligned_data;
 	aplwc->data = aligned_data;
@@ -170,22 +193,157 @@ 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;
+
+#define PUSH(ptr) push(aplwc, &stack, ptr)
+	VISIT_ROOT_PTRS(PUSH);
+	while(stack){
+		c = pop(&stack);
+		VISIT_CHUNK_PTRS(PUSH, c);
+#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;
+	}
+}
+
+static void
+swapptr(struct aplwc *aplwc, void *old, void *new)
+{
+	struct chunk *c;
+	struct memory_ptr_frame *frame;
+	struct root_ptr *root;
+	size_t i;
+
+#define SWAP(ptr) do{ \
+	if((ptr) == old) \
+		(ptr) = new; \
+}while(0)
+	VISIT_ALL_PTRS(SWAP, new);
+#undef SWAP
+}
+
+static void
+compact(struct aplwc *aplwc)
+{
+	struct chunk *c, *prev, *next;
+	void *oldptr, *newptr;
+	size_t size;
+
+	for(c = (struct chunk *)aplwc->data, prev = NULL; c; prev = c, c = c->next){
+		if((prev == NULL) || (prev->tag != CHUNK_TAG_FREE))
+			continue;
+
+		if(c->tag == CHUNK_TAG_FREE){
+			prev->size += c->size;
+			prev->next = c->next;
+		}else{
+			/* swap prev and c */
+			oldptr = data(c);
+			newptr = data(prev);
+
+			next = c->next;
+			size = prev->size;
+			
+			memmove(prev, c, c->size);
+
+			c = (struct chunk *)(((uint8_t *)prev) + prev->size);
+			prev->next = c;
+			c->next = next;
+			c->stack = NULL;
+			c->tag = CHUNK_TAG_FREE;
+			c->size = size;
+
+			swapptr(aplwc, oldptr, newptr);
+		}
+	}
+}
+
 static void *
 alloc(struct aplwc *aplwc, size_t size, enum chunk_tag tag)
 {
 	struct chunk *free;
 	struct chunk *new;
+	size_t pad;
 
+	int attempt;
+
+	pad = size % ALIGNMENT;
+	if(pad)
+		size += ALIGNMENT - pad;
+		
+
+	attempt = 0;
 retry:
 	free = find_free(aplwc, size);
 	if(!free){
-		if(grow(aplwc, size))
+		switch(attempt++){
+		case 0:
+			collect(aplwc);
+			goto retry;
+		case 1:
+			compact(aplwc);
 			goto retry;
-		else
+		case 2:
+			if(grow(aplwc, size))
+				goto retry;
+			/* fall-through */
+		default:
 			return NULL;
+		}
 	}
 
-	assert(free->data == NULL);
+	assert(free->tag == CHUNK_TAG_FREE);
 
 	new = free;
 
@@ -193,16 +351,16 @@ retry:
 		free = (struct chunk *)(((uint8_t*)free) + HEADER_SIZE + size);
 		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->data += ((uintptr_t)new->data) % ALIGNMENT;
+	new->size = size + HEADER_SIZE;
+	new->reachable = aplwc->reachable_bit;
 
-	return new->data;
+	return data(new);
 }
 
 struct aplwc_ref