implement initial fallback bounds checkHEADmaster

+ Binary tree to keep track of regions is probably not the fastest
  method, but easy enough to implement and works for now. In practice
  the matrix example is ~10x slower with fallback checking compared to
  finding the allocation in the hashmap, so hopefully compilers can
  ensure that the base of the allocation really is the base

1 files changed, 90 insertions, 38 deletions

diff --git a/src/vm.c b/src/vm.c
index 6ebf35b..5197ad2 100644
--- a/src/vm.c
+++ b/src/vm.c
@@ -32,6 +32,31 @@ struct alloc {
 	void *base, *top;
 };
 
+static inline int regions_cmp(struct alloc *a, struct alloc *b)
+{
+	/* special case used for finding containing region */
+	if (b->base == b->top) {
+		void *query = b->base;
+		if (query >= a->base && query <= a->top)
+			return 0;
+
+		if (query < a->base)
+			return -1;
+
+		return 1;
+	}
+
+	if (b->base < a->base)
+		return -1;
+
+	return 0;
+}
+
+#define SPTREE_NAME regions
+#define SPTREE_TYPE struct alloc
+#define SPTREE_CMP(a, b) regions_cmp(&(a), &(b))
+#include <conts/sptree.h>
+
 struct allocs {
 	/* must always be pow2 */
 	size_t size;
@@ -41,6 +66,12 @@ struct allocs {
 struct berg_vm {
 	struct funcs funcs;
 	struct allocs allocs;
+
+	/* binary tree for allocations. Probably not the fastest data structure
+	 * possible, and we could for example extend struct alloc with a
+	 * tree-like structure to cut down on individual allocations, but good
+	 * enough for testing */
+	struct regions regions;
 };
 
 struct berg_func {
@@ -110,19 +141,16 @@ top:
 	return 0;
 }
 
-static long allocs_insert(struct allocs *allocs, void *ptr, size_t size)
+static long allocs_insert(struct allocs *allocs, struct alloc alloc)
 {
-	void *top = ptr + size;
-
 	while (1) {
 		/* try to place allocation into map */
-		size_t idx = allocs_idx(ptr, allocs->size);
+		size_t idx = allocs_idx(alloc.base, allocs->size);
 		struct alloc *node = &allocs->buf[idx];
 
 		/* free slot */
 		if (node->base == NULL) {
-			node->base = ptr;
-			node->top = top;
+			*node = alloc;
 			return 0;
 		}
 
@@ -153,6 +181,7 @@ struct berg_vm *create_berg_vm()
 
 	/* 2^4 elements to start with */
 	vm->allocs = allocs_create(4);
+	vm->regions = regions_create();
 	return vm;
 }
 
@@ -464,7 +493,14 @@ static long escape_malloc(size_t argc, const struct ejit_arg args[argc])
 	if (!ptr)
 		return 0;
 
-	if (allocs_insert(&vm->allocs, ptr, size)) {
+	struct alloc alloc = {.base = ptr, .top = ptr + size};
+	if (allocs_insert(&vm->allocs, alloc)) {
+		free(ptr);
+		return 0;
+	}
+
+	if (!regions_insert(&vm->regions, alloc)) {
+		allocs_remove(&vm->allocs, ptr);
 		free(ptr);
 		return 0;
 	}
@@ -481,6 +517,9 @@ static long escape_free(size_t argc, const struct ejit_arg args[argc])
 		abort();
 	}
 
+	struct alloc find = {.base = ptr, .top = ptr};
+	regions_remove(&vm->regions, find);
+
 	free(ptr);
 	return 0;
 }
@@ -620,7 +659,44 @@ static long compile_lshi(struct berg_func *f, struct berg_insn *i)
 	return 0;
 }
 
-static long compile_reg_bounds_check(struct berg_func *f, ejit_escape_i_t handler, uint8_t base, uint8_t offset, uint8_t data, enum ejit_type type)
+static long check_bounds(struct berg_vm *vm, intptr_t base, intptr_t offset)
+{
+	struct alloc find = {.base = (void *)base, .top = (void *)base};
+	struct alloc *exists = regions_find(&vm->regions, find);
+	if (!exists)
+		return -1;
+
+	if (exists->base > (void *)base)
+		return -1;
+
+	if (exists->top < (void *)(base + offset))
+		return -1;
+
+	return 0;
+}
+
+static long escape_bounds_check(size_t argc, const struct ejit_arg args[argc])
+{
+	struct berg_vm *vm = EJIT_PARAM(argc, args, 0, struct berg_vm *);
+	intptr_t base = EJIT_PARAM(argc, args, 1, intptr_t);
+	intptr_t offset = EJIT_PARAM(argc, args, 2, intptr_t);
+
+	if (!check_bounds(vm, base, offset))
+		return 0;
+
+	if (!check_bounds(vm, offset, base))
+		return 0;
+
+	fprintf(stderr, "bounds check failed for %llx(%llx)\n",
+			(long long)base, (long long)offset);
+
+	/** @todo in the real thing, the thread would be killed an all resources
+	 * freed, but this is good enough for now */
+	abort();
+	return 0;
+}
+
+static long compile_reg_bounds_check(struct berg_func *f, uint8_t base, uint8_t offset)
 {
 	/* load base */
 	ejit_rshi(f->func, TMP0, ejit_gpr_from(base), 4);
@@ -640,12 +716,11 @@ static long compile_reg_bounds_check(struct berg_func *f, ejit_escape_i_t handle
 	/* do slow fallback */
 	struct ejit_operand args[] = {
 		EJIT_OPERAND_GPR(TMP0.r, EJIT_POINTER),
-		EJIT_OPERAND_GPR(ejit_gpr_from(base).r, EJIT_POINTER),
+		EJIT_OPERAND_GPR(ejit_gpr_from(base).r, EJIT_TYPE(intptr_t)),
 		EJIT_OPERAND_GPR(ejit_gpr_from(offset).r, EJIT_TYPE(intptr_t)),
-		EJIT_OPERAND_GPR(ejit_gpr_from(data).r, type)
 	};
 	ejit_movi(f->func, TMP0, (uintptr_t)f->vm);
-	ejit_escapei_l(f->func, handler, 4, args);
+	ejit_escapei_l(f->func, escape_bounds_check, 3, args);
 
 	struct ejit_reloc base_continue = ejit_jmp(f->func);
 	ejit_patch(f->func, base_check, ejit_label(f->func));
@@ -658,7 +733,7 @@ static long compile_reg_bounds_check(struct berg_func *f, ejit_escape_i_t handle
 
 	/* do slow fallback */
 	ejit_movi(f->func, TMP0, (uintptr_t)f->vm);
-	ejit_escapei_l(f->func, handler, 4, args);
+	ejit_escapei_l(f->func, escape_bounds_check, 3, args);
 
 	struct ejit_label ok = ejit_label(f->func);
 	ejit_patch(f->func, top_check, ok);
@@ -666,18 +741,6 @@ static long compile_reg_bounds_check(struct berg_func *f, ejit_escape_i_t handle
 	return 0;
 }
 
-static long escape_stxr_32_bounds_check(size_t argc, const struct ejit_arg args[argc])
-{
-	struct berg_vm *vm = EJIT_PARAM(argc, args, 0, struct berg_vm *);
-	void *base = EJIT_PARAM(argc, args, 1, void *);
-	intptr_t offset = EJIT_PARAM(argc, args, 2, intptr_t);
-	int32_t data = EJIT_PARAM(argc, args, 3, int32_t);
-
-	fprintf(stderr, "stxr32 fallback bounds check unimplemented\n");
-	abort();
-	return 0;
-}
-
 static long compile_stxr_32(struct berg_func *f, struct berg_insn *i)
 {
 	/* for now, always check if address is valid */
@@ -685,25 +748,13 @@ static long compile_stxr_32(struct berg_func *f, struct berg_insn *i)
 	uint8_t offset = i->rd;
 	uint8_t data = i->rb;
 
-	compile_reg_bounds_check(f, escape_stxr_32_bounds_check, base, offset, data, EJIT_INT32);
+	compile_reg_bounds_check(f, base, offset);
 
 	/* ok, do actual store */
 	ejit_stxr_32(f->func, ejit_gpr_from(data), ejit_gpr_from(base), ejit_gpr_from(offset));
 	return 0;
 }
 
-static long escape_ldxr_i32_bounds_check(size_t argc, const struct ejit_arg args[argc])
-{
-	struct berg_vm *vm = EJIT_PARAM(argc, args, 0, struct berg_vm *);
-	void *base = EJIT_PARAM(argc, args, 1, void *);
-	intptr_t offset = EJIT_PARAM(argc, args, 2, intptr_t);
-	int32_t data = EJIT_PARAM(argc, args, 3, int32_t);
-
-	fprintf(stderr, "ldxr32 fallback bounds check unimplemented\n");
-	abort();
-	return 0;
-}
-
 static long compile_ldxr_i32(struct berg_func *f, struct berg_insn *i)
 {
 	/* for now, always check if address is valid */
@@ -711,7 +762,7 @@ static long compile_ldxr_i32(struct berg_func *f, struct berg_insn *i)
 	uint8_t offset = i->rd;
 	uint8_t data = i->rb;
 
-	compile_reg_bounds_check(f, escape_ldxr_i32_bounds_check, base, offset, data, EJIT_INT32);
+	compile_reg_bounds_check(f, base, offset);
 
 	/* ok, do actual load */
 	ejit_ldxr_i32(f->func, ejit_gpr_from(data), ejit_gpr_from(base), ejit_gpr_from(offset));
@@ -834,6 +885,7 @@ void destroy_berg_vm(struct berg_vm *vm)
 		destroy_berg_func(*f);
 	}
 	funcs_destroy(&vm->funcs);
+	regions_destroy(&vm->regions);
 
 	for (size_t i = 0; i < vm->allocs.size; ++i) {
 		struct alloc a = vm->allocs.buf[i];