Major API reorganization, test infrastructure

The API is now hidden behind functions. The GC struct can have an
unstable layout without affecting any compiled binaries (users of
Universal Service or collectors hidden behind the API). The
collectors can be called directly if desired.

The API now allows for different allocation flags. These will be
used in future extensions (like weak pointers). For now none are
used.

Tests are compiled for each collector. I can't think of a good
solution that will encompass everything I want to write, but for
now this will work on POSIX systems.

1 files changed, 361 insertions, 98 deletions

diff --git a/cheney_c89.c b/cheney_c89.c
index abdbb76..d1b499d 100644
--- a/cheney_c89.c
+++ b/cheney_c89.c
@@ -21,187 +21,450 @@
 #include <assert.h>
 #include <string.h>
 #include "uns.h"
-#include "internal/c89_relo.h"
 #include "cheney_c89.h"
 
 struct ctx {
+	/** Pointer to the beginning of the heap. */
 	unsigned char *tospace;
+
+	/** Pointer to one past the end of the heap. */
 	unsigned char *tospace_end;
+
+	/** Pointer to the next place to alloc data. This may be one
+	  * past the end of the heap, meaning there is no space left
+	  * on the heap.
+	  */
 	unsigned char *tospace_alloc;
+
+	/** A value set by the user to control the next heap size after
+	  * a collection.
+	  */
+	size_t new_heap_size;
+
+	uns_cheney_c89_collect_callback cb;
+	struct uns_cheney_c89_statistics stats;
 };
 
-const size_t uns_cheney_c89_ctx_size = sizeof(struct ctx);
+void uns_cheney_c89_deinit(Uns_GC gc)
+{
+	struct ctx *ctx = uns_ctx(gc);
+
+	free(ctx->tospace);
+	free(ctx);
+}
 
-static void zero_ctx(struct ctx *ctx)
+void uns_cheney_c89_set_collect_callback(
+	Uns_GC gc,
+	uns_cheney_c89_collect_callback cb
+)
 {
-	ctx->tospace = 0;
-	ctx->tospace_end = 0;
-	ctx->tospace_alloc = 0;
+	struct ctx *ctx = uns_ctx(gc);
+	ctx->cb = cb;
 }
 
-void uns_cheney_c89_deinit(struct uns_gc *gc)
+void uns_cheney_c89_set_new_heap_size(Uns_GC gc, size_t l)
 {
-	struct ctx *ctx = gc->ctx;
+	struct ctx *ctx = uns_ctx(gc);
+	ctx->new_heap_size = l;
+}
 
-	free(ctx->tospace);
+size_t uns_cheney_c89_get_new_heap_size(Uns_GC gc)
+{
+	struct ctx *ctx = uns_ctx(gc);
+	return ctx->new_heap_size;
+}
+
+/** Header of a allocated region is a single uns_sword.
+  *
+  * 0: Relocated. What follows is a pointer to the relocated region.
+  * Positive: allocated bytes.
+  * Negative: allocated record of pointers with this many bytes.
+  *
+  * All lengths must be representable in positive and negative.
+  * Hence UNS_SWORD_MIN and UNS_SWORD_MAX are disallowed length
+  * values.
+  *
+  * Relocated pointers only exist during copying and are not present
+  * during normal execution.
+  */
+
+/** Destructured header. "len" is always the readable length of the
+  * region in bytes (it is always positive).
+  */
+struct hdr {
+	enum {
+		RELO,
+		REGION,
+		RECORD
+	} typ;
+	uns_sword len;
+};
+
+/** Number of fields in a record. */
+#define REC_FIELDS(n) ((n)/sizeof(void*))
+
+/** Size in bytes of the header. */
+#define HDR_LEN sizeof(uns_sword)
+
+/** Extract a header from a pointer to a region. */
+#define HDR_PTR(p) ((unsigned char *)p - HDR_LEN)
+
+/** Minimum size of a region. */
+#define MIN_REG_LEN sizeof(void*)
+
+/** Destructure header pointed to by p
+  *
+  * # Parameters
+  * - `out notnull hdr`: Destructured header.
+  * - `notnull p`: Pointer to a header. This is not a pointer to a region.
+  *   For a pointer to a region, use `hdr_extract`.
+  */
+static void hdr_read(struct hdr *hdr, unsigned char *p)
+{
+	assert(hdr);
+	assert(p);
+
+	memcpy(&hdr->len, p, HDR_LEN);
+	if (hdr->len < 0) {
+		hdr->typ = RECORD;
+		hdr->len = -hdr->len;
+	} else if (hdr->len == 0) {
+		hdr->typ = RELO;
+		hdr->len = sizeof(void*);
+	} else {
+		hdr->typ = REGION;
+	}
+}
+
+/** Destructure header from a pointer to a region.
+  *
+  * # Parameters
+  * - `out notnull hdr`: Destructured header.
+  * - `notnull p`: Pointer to a region. This is not a pointer to the
+  *   header.
+  */
+#define hdr_extract(h,p) hdr_read(h, HDR_PTR(p))
+
+/** Write a header to a location.
+  *
+  * # Parameters
+  * - `notnull hdr`: Header description with all fields filled out. This
+  *   function does not do sanity checking and may overflow if given
+  *   bad data.
+  * - `notnull p`: Header to where the header should be written to.
+  *   This will overwrite data at the pointer location. The pointer
+  *   becomes a pointer to a header, not a pointer to a region.
+  */
+static void hdr_write_direct(struct hdr *hdr, unsigned char *p)
+{
+	uns_sword s;
+
+	assert(hdr);
+	assert(p);
+
+	switch (hdr->typ) {
+	case REGION: s = hdr->len; break;
+	case RELO: s = 0; break;
+	case RECORD: s = -hdr->len; break;
+	}
+
+	memcpy(p, &s, HDR_LEN);
+}
+
+/** Write to the header of a region.
+  *
+  * # Parameters
+  * - `notnull hdr`: See `hdr_write_direct`.
+  * - `notnull p`: Header to a region. The call will do pointer arithmetic
+  *   to get the pointer to the header, and write to the header. It will
+  *   not overwrite region data.
+  */
+#define hdr_write(h, p) hdr_write_direct(h, HDR_PTR(p))
+
+/** Returns true if there is enough space in the heap for a region with
+  * length `bytes`.
+  */
+static int enough_space(struct ctx *ctx, uns_sword bytes)
+{
+	return ctx->tospace_end - ctx->tospace_alloc >= bytes + HDR_LEN;
 }
 
-/* Allocate without doing bounds checking. This is common code for
- * collecting (when all values will fit into the tospace) and
- * allocation (where bounds checking is done beforehand).
- */
-static void *raw_alloc(struct ctx *ctx, size_t len, int is_record)
+/** Allocate region without bounds checking.
+  *
+  * # Parameters
+  * - `len`: Length in bytes of the entire record. This includes the header
+  *   region. The length should have been adjusted by the caller to include
+  *   the minimum region length.
+  * # Returns
+  * A pointer to a region.
+  */
+static void *raw_alloc(struct ctx *ctx, uns_sword len, int is_record)
 {
 	unsigned char *p;
+	struct hdr hdr = {0};
 
-/*
-	printf("%lu (%ld)\n", (unsigned long)(len + sizeof(struct uns_c89_relo_hdr)),
-                              (long)(ctx->tospace_end - ctx->tospace_alloc));
-*/
-	assert(ctx->tospace_alloc + sizeof(struct uns_c89_relo_hdr) + len <= ctx->tospace_end);
-	p = uns_c89_relo_init(ctx->tospace_alloc, len, is_record);
-	ctx->tospace_alloc = p + len;
+	assert(len >= HDR_LEN + MIN_REG_LEN);
 
-	return p;
+	hdr.len = len - HDR_LEN;
+	if (is_record) {
+		hdr.typ = RECORD;
+	} else {
+		hdr.typ = REGION;
+	}
+
+	assert(enough_space(ctx, len));
+
+	p = ctx->tospace_alloc;
+	hdr_write_direct(&hdr, p);
+	ctx->tospace_alloc += len;
+
+	return p + HDR_LEN;
 }
 
-/* Move an entire object pointed to by p from fromspace to tospace. */
-static unsigned char *relocate(struct uns_gc *gc, unsigned char *p)
+/** Move an entire object to the new heap during collection.
+  *
+  * This function does nothing if `p` is NULL. Otherwise, `p` is a pointer
+  * to a region.
+  * If `p` was relocated (typ == `RELO`), then this function returns a
+  * pointer to the relocated header in tospace.
+  * Otherwise, it allocates memory in the tospace, copies the entire region
+  * with its header to the tospace, and modifies the region in the fromspace
+  * to be a region of type `RELO`.
+  */
+static unsigned char *relocate(struct ctx *ctx, unsigned char *p)
 {
-	size_t l;
-	unsigned char *res;
-	struct ctx *ctx = gc->ctx;
+	void *res;
+	struct hdr hdr = {0};
 
 	if (!p)
 		return NULL;
-	res = uns_c89_relo_get_relo(p);
-	if (res)
+	hdr_extract(&hdr, p);
+
+	if (hdr.typ == RELO) {
+		memcpy(&res, p, sizeof(void*));
 		return res;
+	}
 
-	l = uns_c89_relo_get_len(p);
-	res = raw_alloc(ctx, l, uns_c89_relo_is_record(p));
-	memcpy(res, p, l);
-	gc->after_collection += l + sizeof(struct uns_c89_relo_hdr);
+	assert(hdr.len >= MIN_REG_LEN);
 
-	uns_c89_relo_set_relo(p, res);
+	/* Write entire region to memory */
+	res = raw_alloc(ctx, HDR_LEN + hdr.len, hdr.typ == RECORD);
+	memcpy(res, p, hdr.len);
+	hdr_write(&hdr, res);
+
+	/* Change old pointer to relocation pointer */
+	hdr.typ = RELO;
+	hdr_write(&hdr, p);
+	memcpy(p, &res, sizeof(void*));
 	return res;
 }
 
-/* Scan each part of the record pointed to by "p" and relocate it. */
-static void scan_record(struct uns_gc *gc, unsigned char *p)
+/** Calculate the starting byte index of an element in a record.
+  *
+  * # Parameters
+  * - `notnull p`: Pointer to a region.
+  * - `loc`: Index into the region.
+  */
+static size_t record_index(Uns_ptr p, size_t loc)
+{
+	struct hdr hdr = {0};
+
+	assert(p);
+	hdr_extract(&hdr, p);
+	assert(hdr.typ == RECORD);
+
+	/* Turn hdr.len into the number of records in the region */
+	assert(loc < hdr.len / sizeof(void*));
+	assert(loc < SIZE_MAX/sizeof(void*));
+	return loc * sizeof(void*);
+}
+
+void *uns_cheney_c89_get(Uns_ptr p, size_t loc,
+                         enum uns_fld_type *typ)
+{
+	void *r;
+
+	if (typ)
+		*typ = UNS_POINTER;
+	loc = record_index(p, loc);
+	memcpy(&r, (unsigned char *)p + loc, sizeof(void*));
+	return r;
+}
+
+void uns_cheney_c89_set(Uns_ptr p, size_t loc,
+                        enum uns_fld_type typ, void *newp)
+{
+	assert(typ == UNS_POINTER);
+	loc = record_index(p, loc);
+	memcpy((unsigned char  *)p + loc, &newp, sizeof(void*));
+}
+
+/** Relocate each pointer in a record and record its new pointer.
+  *
+  * # Parameters
+  * - `notnull p`: Pointer to a record.
+  * - `len`: Number of elements in the record.
+  */
+static void scan_record(struct ctx *ctx, void *p, size_t len)
 {
-	size_t l = uns_c89_relo_get_record_len(p);
 	size_t i;
 	void *newp;
 
-	for (i = 0; i < l; i++) {
-		newp = relocate(gc, uns_c89_relo_record_get((void *)p, i));
-		uns_c89_relo_record_set((void *)p, i, newp);
+	for (i = 0; i < len; i++) {
+		newp = relocate(ctx,
+		                uns_cheney_c89_get(p, i, NULL));
+		uns_cheney_c89_set(p, i, UNS_POINTER, newp);
+	}
+}
+
+/** Main section of the copying algorithm. */
+static void relocate_everything(Uns_GC gc)
+{
+	unsigned char *scanptr;
+	struct uns_ctr *root;
+	struct ctx *ctx = uns_ctx(gc);
+	struct hdr hdr = {0};
+
+	/* Relocate roots */
+	for (root = uns_roots(gc); root; root = root->next)
+		root->p = relocate(ctx, root->p);
+
+	/* Scan the heap until the end of allocated space. If there
+	 * is a record at this location, read the record and relocate
+	 * all values, and then change each field to the relocated
+	 * record pointer.
+	 */
+	scanptr = ctx->tospace;
+	while (scanptr != ctx->tospace_alloc) {
+		/* scanptr currently points to the header data. */
+		hdr_read(&hdr, scanptr);
+		scanptr += HDR_LEN;
+
+		if (hdr.typ == RECORD)
+			scan_record(ctx, scanptr, (size_t)hdr.len/sizeof(void*));
+		scanptr += hdr.len;
 	}
+
 }
 
-int uns_cheney_c89_collect(struct uns_gc *gc)
+int uns_cheney_c89_collect(Uns_GC gc)
 {
 	/* Save fromspace */
-	struct ctx *ctx = gc->ctx;
+	struct ctx *ctx = uns_ctx(gc);
 	unsigned char *fromspace = ctx->tospace;
 	unsigned char *fromspace_lim = ctx->tospace_alloc;
-	unsigned char *scanptr;
 
-	size_t newlen = gc->next_alloc;
-	struct uns_ctr *root;
+	size_t newlen = ctx->new_heap_size;
 
-	assert(gc->next_alloc >= fromspace_lim - fromspace);
+	ctx->stats.usage_before = fromspace_lim - fromspace;
 
 	/* Bail out immediately if allocation fails. This preserves
 	 * the objects as they were.
 	 */
+	assert(newlen >= fromspace_lim - fromspace);
 	ctx->tospace = malloc(newlen);
 	if (!ctx->tospace) {
 		ctx->tospace = fromspace;
 		return 1;
 	}
 
-	/* Setup statistics */
-	gc->before_collection = fromspace_lim - fromspace;
-/*
-	printf("before: %ld\n", gc->before_collection);
-*/
-	gc->after_collection = 0;
-	gc->collection_number += 1;
-
+	/* Setup context to be valid for the allocator */
 	ctx->tospace_end = ctx->tospace + newlen;
 	ctx->tospace_alloc = ctx->tospace;
 
-	/* Relocate roots */
-	for (root = gc->roots; root; root = root->next)
-		root->p = relocate(gc, root->p);
-
-	scanptr = ctx->tospace;
-	while (scanptr != ctx->tospace_alloc) {
-		/* scanptr currently points to the header data that the mutator
-		 * does not usually see.
-		 */
-		scanptr += sizeof(struct uns_c89_relo_hdr);
-		if (uns_c89_relo_is_record(scanptr))
-			scan_record(gc, scanptr);
-		scanptr += uns_c89_relo_get_len(scanptr);
-	}
+	relocate_everything(gc);
 
 	free(fromspace);
-	if (gc->after_gc)
-		gc->after_gc(gc);
+
+	ctx->stats.usage_after = ctx->tospace_alloc - ctx->tospace;
+	ctx->stats.collection_number += 1;
+	if (ctx->cb)
+		ctx->cb(gc, &ctx->stats);
+
 	return 1;
 }
 
-static void *alloc(struct uns_gc *gc, size_t bytes, int is_record)
+static void *alloc(Uns_GC gc, size_t bytes, int is_record)
 {
-	struct ctx *ctx = gc->ctx;
-	size_t total_bytes = bytes + sizeof(struct uns_c89_relo_hdr);
+	struct ctx *ctx = uns_ctx(gc);
+	uns_sword bytes_as_sword;
+
+	if (bytes >= UNS_SWORD_MAX) {
+		uns_on_oom(gc);
+		return NULL;
+	} else if (bytes < MIN_REG_LEN) {
+		bytes = MIN_REG_LEN;
+	}
+
+	bytes_as_sword = (uns_sword)bytes + HDR_LEN;
 
 	/* Make sure to check for header space when allocating */
-	if (ctx->tospace_end - ctx->tospace_alloc < total_bytes)
+	if (!enough_space(ctx, bytes_as_sword)) {
 		uns_cheney_c89_collect(gc);
-	if (ctx->tospace_end - ctx->tospace_alloc < total_bytes)
-		gc->oom(gc);
+		if (!enough_space(ctx, bytes_as_sword)) {
+			uns_on_oom(gc);
+			return NULL;
+		}
+	}
 
-	return raw_alloc(ctx, bytes, is_record);
+	return raw_alloc(ctx, HDR_LEN + bytes, is_record);
 }
 
-void *uns_cheney_c89_alloc(struct uns_gc *gc, size_t bytes)
+void *uns_cheney_c89_alloc(Uns_GC gc, size_t bytes, enum uns_bytes_type typ)
 {
+	assert(typ == UNS_NOEXEC);
 	return alloc(gc, bytes, 0);
 }
 
-void *uns_cheney_c89_alloc_record(struct uns_gc *gc, size_t records)
+void *uns_cheney_c89_alloc_rec(Uns_GC gc, size_t len, enum uns_record_type typ)
 {
+	void *p;
 	size_t i;
-	unsigned char *res = alloc(gc, records*sizeof(void *), 1);
+	assert(typ == UNS_POINTERS_ONLY);
+
+	if (len >= SIZE_MAX/sizeof(void*)) {
+	    	uns_on_oom(gc);
+		return NULL;
+	} else if (len == 0) {
+		len = 1;
+	}
 
-	for (i = 0; i < records; i++)
-		uns_c89_relo_record_set((void *)res, i, NULL);
+	p = alloc(gc, len*sizeof(void*), 1);
+	if (p == NULL)
+		return NULL;
 
-	return res;
+	for (i = 0; i < len; i++)
+		uns_cheney_c89_set(p, i, UNS_POINTER, NULL);
+	return p;
 }
 
-int uns_cheney_c89_init(struct uns_gc *gc)
+int uns_cheney_c89_init(Uns_GC gc, size_t heap_size)
 {
-	struct ctx *ctx = gc->ctx;
-
-	gc->deinit = uns_cheney_c89_deinit;
-	gc->collect = uns_cheney_c89_collect;
-	gc->alloc = uns_cheney_c89_alloc;
-	gc->alloc_record = uns_cheney_c89_alloc_record;
-	gc->len = uns_c89_relo_get_len;
-	gc->record_set_ptr = uns_c89_relo_record_set;
-	gc->record_get_ptr = uns_c89_relo_record_get;
+	struct ctx *ctx = malloc(sizeof(struct ctx));
+	if (!ctx)
+		return 0;
 
-	zero_ctx(ctx);
-	ctx->tospace = malloc(gc->next_alloc);
-	if (!ctx->tospace)
+	uns_deinit(gc);
+	ctx->tospace_alloc = ctx->tospace = malloc(heap_size);
+	if (!ctx->tospace) {
+		free(ctx);
 		return 0;
+	}
+
+	ctx->stats.usage_before = ctx->stats.usage_after
+		= ctx->stats.collection_number = 0;
+
+	ctx->tospace_end = ctx->tospace + heap_size;
+	ctx->new_heap_size = heap_size;
+	ctx->cb = NULL;
+
+	uns_set_ctx(gc, ctx);
+	uns_set_deinit(gc, uns_cheney_c89_deinit);
+	uns_set_collect(gc, uns_cheney_c89_collect);
+	uns_set_alloc(gc, uns_cheney_c89_alloc);
+	uns_set_alloc_rec(gc, uns_cheney_c89_alloc_rec);
+	uns_set_set(gc, uns_cheney_c89_set);
+	uns_set_get(gc, uns_cheney_c89_get);
 
-	ctx->tospace_alloc = ctx->tospace;
-	ctx->tospace_end = ctx->tospace + gc->next_alloc;
 	return 1;
 }