Compute chunk->next based on chunk->size, and add some debug checks

FossilOrigin-Name: d0b062b28f5486e63437cfefde99508c64b25d1bf6fecdc0af8c49a80a76ed80

2 files changed, 86 insertions, 38 deletions

diff --git a/src/include/aplwc_macros.h b/src/include/aplwc_macros.h
index b65848f..f68fea9 100644
--- a/src/include/aplwc_macros.h
+++ b/src/include/aplwc_macros.h
@@ -27,12 +27,15 @@
 #if APLWC_BUILD_TYPE_DEBUG
  #define ALWAYS(x) ((x) ? 1 : (assert(0), 0))
  #define NEVER(x)  ((x) ? (assert(0), 1) : 0)
+ #define DEBUG(x)  debug_##x
 #elif APLWC_BUILD_TYPE_RELEASE
- #define ALWAYS(x) (X)
- #define NEVER(X)  (X)
+ #define ALWAYS(x) (x)
+ #define NEVER(x)  (x)
+ #define DEBUG(x)  ((void)0)
 #elif APLWC_BUILD_TYPE_COVERAGE
  #define ALWAYS(x) (1)
  #define NEVER(x)  (0)
+ #define DEBUG(x)  ((void)0)
 #endif
 
 
diff --git a/src/lib/memory.c b/src/lib/memory.c
index e277bd7..fbc0af7 100644
--- a/src/lib/memory.c
+++ b/src/lib/memory.c
@@ -32,11 +32,11 @@ enum chunk_tag {
 };
 
 struct chunk {
-	struct chunk *next;
 	struct chunk *stack;
 	size_t size;
 	enum chunk_tag tag;
 	unsigned int reachable:1;
+	unsigned int last:1;
 };
 
 void
@@ -66,6 +66,19 @@ data(struct chunk *c)
 	return p + HEADER_SIZE;
 }
 
+struct chunk *
+next(struct chunk *c)
+{
+	uint8_t *p;
+
+	if(c->last)
+		return NULL;
+
+	p = (uint8_t*)c;
+
+	return (struct chunk *)(p + c->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: \
@@ -100,10 +113,8 @@ data(struct chunk *c)
 
 #define VISIT_ALL_PTRS(X, data) do{ \
 	VISIT_ROOT_PTRS(X); \
-	for(c = (struct chunk *)(data); c; c = c->next){ \
-		X(c->next); \
+	for(c = (struct chunk *)(data); c; c = next(c)) \
 		VISIT_CHUNK_PTRS(X, c); \
-	} \
 }while(0)
 
 static void
@@ -138,7 +149,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, *last;
+	struct chunk *free, *head, *last;
 
 	if(aplwc->fns.alloc == NULL)
 		goto error;
@@ -164,24 +175,24 @@ 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)
-			if((*free)->next)
-				assert((*free)->tag != CHUNK_TAG_FREE);
+		for(free = head; free; free = next(free))
+			if(next(free))
+				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)->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;
+				last = free;
+	}
+
+	free = (struct chunk *)(aligned_data + aplwc->size);
+	free->tag = CHUNK_TAG_FREE;
+	free->size = aligned_newsize - aplwc->size;
+	free->stack = NULL;
+	free->last = 1;
+
+	if(last){
+		if(last && (last->tag == CHUNK_TAG_FREE))
+			last->size += free->size;
+		else
+			last->last = 0;
 	}
 
 	aplwc->unaligned_data = unaligned_data;
@@ -204,7 +215,7 @@ find_free(struct aplwc *aplwc, size_t min)
 	if(aplwc->data == NULL)
 		return NULL;
 	
-	for(c = (struct chunk *)aplwc->data; c; c = c->next){
+	for(c = (struct chunk *)aplwc->data; c; c = next(c)){
 		if((c->tag == CHUNK_TAG_FREE) && (c->size >= min))
 			break;
 	}
@@ -249,7 +260,7 @@ pop(struct chunk **stack)
 static void
 collect(struct aplwc *aplwc)
 {
-	struct chunk *c;
+	struct chunk *c, *prev;
 	struct chunk *stack;
 	struct memory_ptr_frame *frame;
 	struct root_ptr *root;
@@ -270,9 +281,17 @@ collect(struct aplwc *aplwc)
 	}
 
 	/* 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;
+	prev = NULL;
+	for(c = (struct chunk *)aplwc->data; c; prev = c, c = next(c)){
+		if((c->reachable != aplwc->reachable_bit) || (c->tag == CHUNK_TAG_FREE)){
+			if(prev && (prev->tag == CHUNK_TAG_FREE)){
+				prev->size += c->size;
+				prev->last = c->last;
+				c = prev;
+			}else{
+				c->tag = CHUNK_TAG_FREE;
+			}
+		}
 	}
 }
 
@@ -295,39 +314,59 @@ swapptr(struct aplwc *aplwc, void *old, void *new)
 static void
 compact(struct aplwc *aplwc)
 {
-	struct chunk *c, *prev, *next;
+	struct chunk *c, *prev;
 	void *oldptr, *newptr;
 	size_t size;
+	int last;
 
-	for(c = (struct chunk *)aplwc->data, prev = NULL; c; prev = c, c = c->next){
+	for(c = (struct chunk *)aplwc->data, prev = NULL; c; prev = c, c = next(c)){
 		if((prev == NULL) || (prev->tag != CHUNK_TAG_FREE))
 			continue;
 
 		if(c->tag == CHUNK_TAG_FREE){
 			prev->size += c->size;
-			prev->next = c->next;
+			prev->last = c->last;
 		}else{
 			/* swap prev and c */
 			oldptr = data(c);
 			newptr = data(prev);
 
-			next = c->next;
 			size = prev->size;
+			last = c->last;
 			
 			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;
+			c->last = last;
+			prev->last = 0;
 
 			swapptr(aplwc, oldptr, newptr);
 		}
 	}
 }
 
+static void
+debug_check_mem(struct aplwc *aplwc)
+{
+	uint64_t size;
+	struct chunk *c, *prev;
+
+	size = 0;
+	prev = NULL;
+	for(c = (struct chunk *)aplwc->data; c; prev = c, c = next(c)){
+		assert(((uint8_t*)c) < (aplwc->data+aplwc->size));
+		size += c->size;
+		assert((c->last == 0) != (size == aplwc->size));
+		if(c->tag == CHUNK_TAG_FREE)
+			assert((prev == NULL) || (prev->tag != CHUNK_TAG_FREE));
+	}
+	
+	assert(size == aplwc->size);
+}
+
 static void *
 alloc(struct aplwc *aplwc, size_t size, enum chunk_tag tag)
 {
@@ -344,6 +383,7 @@ alloc(struct aplwc *aplwc, size_t size, enum chunk_tag tag)
 
 	attempt = 0;
 retry:
+	DEBUG(check_mem(aplwc));
 	free = find_free(aplwc, size);
 	if(!free){
 		switch(attempt++){
@@ -371,14 +411,19 @@ retry:
 		free->tag = CHUNK_TAG_FREE;
 		free->size = new->size - (HEADER_SIZE + size);
 		free->stack = NULL;
-		free->next = new->next;
-		new->next = free;
+
+		if(new->last){
+			new->last = 0;
+			free->last = 1;
+		}
+
+		new->size = size+HEADER_SIZE;
 	}
 
 	new->tag = tag;
-	new->size = size + HEADER_SIZE;
 	new->reachable = aplwc->reachable_bit;
 
+	DEBUG(check_mem(aplwc));
 	return data(new);
 }