cheney copying collector

1 files changed, 192 insertions, 0 deletions

diff --git a/cheney_c89.c b/cheney_c89.c
new file mode 100644
index 0000000..bb66973
--- /dev/null
+++ b/cheney_c89.c
@@ -0,0 +1,192 @@
+/* Copyright (C) 2024 Peter McGoron
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as
+ * published by the Free Software Foundation, either version 3 of the
+ * License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this program. If not, see
+ * <https://www.gnu.org/licenses/>.
+*/
+
+#include <stdlib.h>
+#include <limits.h>
+#include <assert.h>
+#include <string.h>
+#include "uns.h"
+#include "internal/c89_relo.h"
+#include "cheney_c89.h"
+
+struct ctx {
+	unsigned char *tospace;
+	unsigned char *tospace_end;
+	unsigned char *tospace_alloc;
+};
+
+const size_t uns_cheney_c89_ctx_size = sizeof(struct ctx);
+
+static void zero_ctx(struct ctx *ctx)
+{
+	ctx->tospace = 0;
+	ctx->tospace_end = 0;
+	ctx->tospace_alloc = 0;
+}
+
+void uns_cheney_c89_deinit(struct uns_gc *gc)
+{
+	struct ctx *ctx = gc->ctx;
+
+	free(ctx->tospace);
+}
+
+/* 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)
+{
+	unsigned char *p;
+
+	p = uns_c89_relo_init(ctx->tospace_alloc, len, is_record);
+	ctx->tospace_alloc = p + len;
+
+	return p;
+}
+
+/* Move an entire object pointed to by p from fromspace to tospace. */
+static unsigned char *relocate(struct uns_gc *gc, unsigned char *p)
+{
+	size_t l;
+	unsigned char *res;
+	struct ctx *ctx = gc->ctx;
+
+	if (!p)
+		return NULL;
+	res = uns_c89_relo_get_relo(p);
+	if (res)
+		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;
+
+	uns_c89_relo_set_relo(p, res);
+	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)
+{
+	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(p, i));
+		memcpy(p, &newp, sizeof(void *));
+	}
+}
+
+int uns_cheney_c89_collect(struct uns_gc *gc)
+{
+	/* Save fromspace */
+	struct ctx *ctx = gc->ctx;
+	unsigned char *fromspace = ctx->tospace;
+	unsigned char *fromspace_lim = ctx->tospace_alloc;
+	unsigned char *scanptr;
+
+	size_t newlen = gc->next_alloc;
+	struct uns_root_list *root;
+
+	assert(gc->next_alloc >= fromspace_lim - fromspace);
+
+	/* Bail out immediately if allocation fails. This preserves
+	 * the objects as they were.
+	 */
+	ctx->tospace = malloc(newlen);
+	if (!ctx->tospace) {
+		ctx->tospace = fromspace;
+		return 1;
+	}
+
+	/* Setup statistics */
+	gc->before_collection = fromspace_lim - fromspace;
+	gc->after_collection = 0;
+	gc->collection_number += 1;
+
+	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) {
+		if (uns_c89_relo_is_record(scanptr))
+			scan_record(gc, scanptr);
+		scanptr += uns_c89_relo_get_len(scanptr);
+	}
+
+	free(fromspace);
+	if (gc->after_gc)
+		gc->after_gc(gc);
+	return 1;
+}
+
+static void *alloc(struct uns_gc *gc, size_t bytes, int is_record)
+{
+	struct ctx *ctx = gc->ctx;
+
+	if (ctx->tospace_end - ctx->tospace_alloc < bytes)
+		uns_cheney_c89_collect(gc);
+	if (ctx->tospace_end - ctx->tospace_alloc < bytes)
+		gc->oom(gc);
+
+	return raw_alloc(ctx, bytes, is_record);
+}
+
+void *uns_cheney_c89_alloc(struct uns_gc *gc, size_t bytes)
+{
+	return alloc(gc, bytes, 0);
+}
+
+void *uns_cheney_c89_alloc_record(struct uns_gc *gc, size_t records)
+{
+	size_t i;
+	unsigned char *res = alloc(gc, records*sizeof(void *), 1);
+
+	for (i = 0; i < records; i++)
+		uns_c89_relo_record_set(res, i, NULL);
+
+	return res;
+}
+
+int uns_cheney_c89_init(struct uns_gc *gc)
+{
+	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;
+
+	zero_ctx(ctx);
+	ctx->tospace = malloc(gc->next_alloc);
+	if (!ctx->tospace)
+		return 0;
+
+	ctx->tospace_alloc = ctx->tospace;
+	ctx->tospace_end = ctx->tospace + gc->next_alloc;
+	return 1;
+}