add ideal allocation tracker

+ Kind of like CHERI, but uses out-of-line pointer information.
  The idea is that a core that is compatible with ALLOC_IF queries
  the allocation tracker if an address is legal and gets a response.
  This ideal tracker effectively has infinite memory and doesn't talk to
  any other components, but a real implementation might want to limit
  the allocations per process or chat with some reserved memory region
  somewhere else in the system to maintain a binary tree or something.

13 files changed, 433 insertions, 13 deletions

diff --git a/.gitmodules b/.gitmodules
new file mode 100644
index 0000000..bf47852
--- /dev/null
+++ b/.gitmodules
@@ -0,0 +1,3 @@
+[submodule "deps/conts"]
+	path = deps/conts
+	url = https://metanimi.dy.fi/git/conts
diff --git a/Makefile b/Makefile
index 108c182..d6af17d 100644
--- a/Makefile
+++ b/Makefile
@@ -1,10 +1,10 @@
 DO	!= echo -n > deps.mk
 
 DEBUGFLAGS	!= [ $(RELEASE) ] && echo "-flto=auto -O2 -DNODEBUG" || echo "-O0 -g -DDEBUG"
-CFLAGS		= -Wall -Wextra -g
+CFLAGS		= -Wall -Wextra -g -std=gnu23
 DEPFLAGS	= -MT $@ -MMD -MP -MF $@.d
 LINTFLAGS	= -fsyntax-only
-INCLUDEFLAGS	= -Iinclude
+INCLUDEFLAGS	= -Iinclude -Ideps/conts/include
 COMPILEFLAGS	=
 LINKFLAGS	=
 
diff --git a/deps/conts b/deps/conts
new file mode 160000
+Subproject 2d63e807ac56cad97bf32bec0e8372dc2bed240
diff --git a/include/gran/if/alloc.h b/include/gran/if/alloc.h
new file mode 100644
index 0000000..1fec04b
--- /dev/null
+++ b/include/gran/if/alloc.h
@@ -0,0 +1,36 @@
+#ifndef GRAN_ALLOC_IF_H
+#define GRAN_ALLOC_IF_H
+
+#include <stdint.h>
+
+/* completely arbitrary values */
+enum alloc_if_op {
+	ALLOC_IF_NEW = 0x00,
+	ALLOC_IF_RM = 0x40,
+	ALLOC_IF_Q = 0x80,
+};
+
+enum alloc_if_ret {
+	ALLOC_IF_OK,
+	ALLOC_IF_ERR_SPACE,
+	ALLOC_IF_ERR_RANGE,
+};
+
+struct alloc_if_new {
+	uint64_t space, start, end;
+};
+
+struct alloc_if_rm {
+	uint64_t space, start, end;
+};
+
+struct alloc_if_q {
+	uint64_t space, addr;
+};
+
+struct alloc_if_r {
+	enum alloc_if_ret r;
+	uint64_t start, end;
+};
+
+#endif /* GRAN_ALLOC_IF_H */
diff --git a/include/gran/mem/ideal_alloc.h b/include/gran/mem/ideal_alloc.h
new file mode 100644
index 0000000..009f91a
--- /dev/null
+++ b/include/gran/mem/ideal_alloc.h
@@ -0,0 +1,11 @@
+#ifndef GRAN_IDEAL_ALLOC_H
+#define GRAN_IDEAL_ALLOC_H
+
+#include <stdint.h>
+#include <gran/if/alloc.h>
+#include <gran/component.h>
+
+struct component *create_ideal_alloc(uint64_t spaces);
+void ideal_alloc_connect(struct component *alloc, struct component *send);
+
+#endif /* GRAN_IDEAL_ALLOC_H */
diff --git a/src/ideal_noc.c b/src/ideal_noc.c
index 0ebc17e..d2816d6 100644
--- a/src/ideal_noc.c
+++ b/src/ideal_noc.c
@@ -17,7 +17,7 @@ struct noc {
 	struct component **lower; /* countedby[elems] */
 };
 
-stat ideal_noc_receive(struct noc *n, struct component *from, struct packet pkt)
+static stat ideal_noc_receive(struct noc *n, struct component *from, struct packet pkt)
 {
 	(void)from; /* unused */
 	uint32_t elem;
@@ -33,7 +33,7 @@ stat ideal_noc_receive(struct noc *n, struct component *from, struct packet pkt)
 	return OK;
 }
 
-stat ideal_noc_clock(struct noc *n)
+static stat ideal_noc_clock(struct noc *n)
 {
 	size_t counter = n->latency == 0 ? 0 : (n->counter + 1) % n->latency;
 	if (counter != 0)
@@ -78,7 +78,7 @@ stat ideal_noc_clock(struct noc *n)
 	return OK;
 }
 
-void ideal_noc_destroy(struct noc *n)
+static void ideal_noc_destroy(struct noc *n)
 {
 	free(n->in);
 	free(n->out);
diff --git a/src/mem/ideal_alloc.c b/src/mem/ideal_alloc.c
new file mode 100644
index 0000000..0396123
--- /dev/null
+++ b/src/mem/ideal_alloc.c
@@ -0,0 +1,209 @@
+#include <stdlib.h>
+#include <gran/mem/ideal_alloc.h>
+
+/** @todo almost everyone has the same def for reg, should maybe make common */
+struct reg {
+	struct packet pkt;
+	bool busy;
+};
+
+struct region {
+	uint64_t start, end;
+};
+
+static inline int region_cmp(struct region a, struct region b)
+{
+	if (a.start == b.start && a.end == b.end)
+		return 0;
+
+	if (a.start > b.start)
+		return 1;
+
+	if (a.end < b.end)
+		return -1;
+
+	return 0;
+}
+
+#define SPTREE_NAME regions
+#define SPTREE_TYPE struct region
+#define SPTREE_CMP(a, b) region_cmp((a), (b))
+#include <conts/sptree.h>
+
+struct space {
+	struct regions regions;
+};
+
+static struct space create_space()
+{
+	return (struct space){.regions = regions_create()};
+}
+
+static void destroy_space(struct space *space)
+{
+	regions_destroy(&space->regions);
+}
+
+#define VEC_NAME spaces
+#define VEC_TYPE struct space
+#include <conts/vec.h>
+
+struct alloc {
+	struct component component;
+	struct spaces spaces;
+	uint64_t max_spaces;
+
+	struct reg in;
+	struct reg out;
+
+	struct component *send;
+};
+
+static void alloc_destroy(struct alloc *a)
+{
+	foreach(spaces, s, &a->spaces) {
+		destroy_space(s);
+	}
+
+	spaces_destroy(&a->spaces);
+	free(a);
+}
+
+static stat alloc_receive(struct alloc *a, struct component *from, struct packet pkt)
+{
+	(void)from; /* unused */
+	if (a->in.busy)
+		return EBUSY;
+
+	a->in.pkt = pkt;
+	a->in.busy = true;
+	return OK;
+}
+
+static stat alloc_resp(struct alloc *a, enum alloc_if_ret resp, uint64_t start, uint64_t end)
+{
+	a->in.busy = false;
+
+	struct packet pkt = response(a->in.pkt);
+	struct alloc_if_r *r = (struct alloc_if_r *)&pkt.data;
+	r->r = resp;
+	r->start = start;
+	r->end = end;
+
+	stat ret = SEND(a, a->send, pkt);
+	if (ret == EBUSY) {
+		a->out.pkt = pkt;
+		a->out.busy = true;
+		return OK;
+	}
+
+	return ret;
+}
+
+static stat alloc_new(struct alloc *a)
+{
+	struct alloc_if_new *n = (struct alloc_if_new *)&a->in.pkt.data;
+	if (n->space >= a->max_spaces)
+		return alloc_resp(a, ALLOC_IF_ERR_SPACE, 0, 0);
+
+	struct space *space = spaces_at(&a->spaces, n->space);
+	assert(space);
+
+	struct region new = {.start = n->start, .end = n->end};
+	struct region *region = regions_insert(&space->regions, new);
+	if (!region) {
+		alloc_resp(a, ALLOC_IF_ERR_RANGE, 0, 0);
+		return EMEM;
+	}
+
+	return alloc_resp(a, ALLOC_IF_OK, n->start, n->end);
+}
+
+static stat alloc_rm(struct alloc *a)
+{
+	struct alloc_if_rm *rm = (struct alloc_if_rm *)&a->in.pkt.data;
+	if (rm->space >= a->max_spaces)
+		return alloc_resp(a, ALLOC_IF_ERR_SPACE, 0, 0);
+
+	struct space *space = spaces_at(&a->spaces, rm->space);
+	assert(space);
+
+	struct region find = {.start = rm->start, .end = rm->end};
+	struct region *region = regions_find(&space->regions, find);
+	if (!region)
+		return alloc_resp(a, ALLOC_IF_ERR_RANGE, 0, 0);
+
+	regions_remove_found(&space->regions, region);
+	regions_free_found(&space->regions, region);
+	return alloc_resp(a, ALLOC_IF_OK, 0, 0);
+}
+
+static stat alloc_q(struct alloc *a)
+{
+	struct alloc_if_q *q = (struct alloc_if_q *)&a->in.pkt.data;
+	if (q->space >= a->max_spaces)
+		return alloc_resp(a, ALLOC_IF_ERR_SPACE, 0, 0);
+
+	struct space *space = spaces_at(&a->spaces, q->space);
+	assert(space);
+
+	struct region find = {.start = q->addr, .end = q->addr};
+	struct region *region = regions_find(&space->regions, find);
+	if (!region)
+		return alloc_resp(a, ALLOC_IF_ERR_RANGE, 0, 0);
+
+	return alloc_resp(a, ALLOC_IF_OK, region->start, region->end);
+}
+
+static stat alloc_clock(struct alloc *a)
+{
+	if (!a->in.busy)
+		return OK;
+
+	if (a->out.busy) {
+		stat ret = SEND(a, a->send, a->out.pkt);
+		if (ret == EBUSY)
+			return OK;
+
+		assert(ret == OK);
+		a->out.busy = false;
+	}
+
+	uint32_t off = (uint32_t)a->in.pkt.to;
+	switch (off) {
+	case ALLOC_IF_NEW: return alloc_new(a);
+	case ALLOC_IF_RM: return alloc_rm(a);
+	case ALLOC_IF_Q: return alloc_q(a);
+	default: break;
+	}
+
+	return OK;
+}
+
+void ideal_alloc_connect(struct component *alloc, struct component *send)
+{
+	struct alloc *a = (struct alloc *)alloc;
+	assert(a->send == NULL);
+	a->send = send;
+}
+
+struct component *create_ideal_alloc(uint64_t max_spaces)
+{
+	struct alloc *a = calloc(1, sizeof(struct alloc));
+	a->spaces = spaces_create(max_spaces);
+	if (spaces_uninit(&a->spaces)) {
+		free(a);
+		return NULL;
+	}
+
+	for (size_t i = 0; i < max_spaces; ++i) {
+		struct space space = create_space();
+		spaces_append(&a->spaces, space);
+	}
+
+	a->max_spaces = max_spaces;
+	a->component.clock = (clock_callback)alloc_clock;
+	a->component.receive = (receive_callback)alloc_receive;
+	a->component.destroy = (destroy_callback)alloc_destroy;
+	return (struct component *)a;
+}
diff --git a/src/mem/source.mk b/src/mem/source.mk
index 7d1a717..264d8bc 100644
--- a/src/mem/source.mk
+++ b/src/mem/source.mk
@@ -1 +1 @@
-SOURCES += src/mem/simple_mem.c
+SOURCES += src/mem/simple_mem.c src/mem/ideal_alloc.c
diff --git a/tests/simple_ideal_alloc/sim.c b/tests/simple_ideal_alloc/sim.c
new file mode 100644
index 0000000..6aeb5b6
--- /dev/null
+++ b/tests/simple_ideal_alloc/sim.c
@@ -0,0 +1,26 @@
+#include <assert.h>
+
+#include <gran/root.h>
+#include <gran/mem/ideal_alloc.h>
+
+#include "testbench.h"
+
+int main()
+{
+	struct component *traffic_gen = create_testbench();
+	struct component *ideal_alloc = create_ideal_alloc(1);
+
+	ideal_alloc_connect(ideal_alloc, traffic_gen);
+	testbench_connect(traffic_gen, ideal_alloc);
+
+	struct clock_domain *clk = create_clock_domain(NS(1));
+	clock_domain_add(clk, traffic_gen);
+	clock_domain_add(clk, ideal_alloc);
+
+	struct gran_root *root = create_root();
+	root_add_clock(root, clk);
+
+	assert(root_run(root) == OK);
+
+	destroy_root(root);
+}
diff --git a/tests/simple_ideal_alloc/source.mk b/tests/simple_ideal_alloc/source.mk
new file mode 100644
index 0000000..f797cdd
--- /dev/null
+++ b/tests/simple_ideal_alloc/source.mk
@@ -0,0 +1,7 @@
+ALLOC_TB_OBJ		!= ./scripts/gen-deps --sources "tests/simple_ideal_alloc/testbench.c"
+IDEAL_ALLOC_TEST_OBJ	!= ./scripts/gen-deps --sources "tests/simple_ideal_alloc/sim.c"
+
+TEST_PROGS		+= build/tests/simple_ideal_alloc/sim
+
+build/tests/simple_ideal_alloc/sim: $(ALLOC_TB_OBJ) $(IDEAL_ALLOC_TEST_OBJ) $(OBJS)
+	$(COMPILE) $(ALLOC_TB_OBJ) $(IDEAL_ALLOC_TEST_OBJ) $(TEST_OBJS) $(OBJS) -o $@
diff --git a/tests/simple_ideal_alloc/testbench.c b/tests/simple_ideal_alloc/testbench.c
new file mode 100644
index 0000000..703c2a8
--- /dev/null
+++ b/tests/simple_ideal_alloc/testbench.c
@@ -0,0 +1,119 @@
+#include <gran/if/alloc.h>
+#include "testbench.h"
+
+struct reg {
+	struct packet pkt;
+	bool busy;
+};
+
+struct tb {
+	struct component component;
+	struct component *dut;
+	struct reg in;
+
+	enum {
+		ADD_REGION,
+		QUERY_EXISTING,
+		REMOVE_REGION,
+		QUERY_NONEXISTING,
+		FINAL
+	} state;
+};
+
+static stat tb_receive(struct tb *tb, struct component *from, struct packet pkt)
+{
+	assert(tb->dut == from);
+	tb->in.pkt = pkt;
+	tb->in.busy = true;
+	return OK;
+}
+
+static stat tb_clock(struct tb *tb)
+{
+	assert(tb->dut);
+
+	switch (tb->state) {
+	case ADD_REGION: {
+		struct alloc_if_new n = {.space = 0, .start = 0, .end = 10};
+		struct packet pkt = create_packet(0, ALLOC_IF_NEW, sizeof(n), &n, PACKET_WRITE);
+		assert(SEND(tb, tb->dut, pkt) == OK);
+		tb->state = QUERY_EXISTING;
+		break;
+	}
+
+	case QUERY_EXISTING: {
+		if (!tb->in.busy)
+			break;
+
+		struct alloc_if_r *r = (struct alloc_if_r *)&tb->in.pkt.data;
+		assert(r->r == ALLOC_IF_OK);
+
+		struct alloc_if_q q = {.space = 0, .addr = 5};
+		struct packet pkt = create_packet(0, ALLOC_IF_Q, sizeof(q), &q, PACKET_WRITE);
+		assert(SEND(tb, tb->dut, pkt) == OK);
+		tb->state = REMOVE_REGION;
+		tb->in.busy = false;
+		break;
+	}
+
+	case REMOVE_REGION: {
+		if (!tb->in.busy)
+			break;
+
+		struct alloc_if_r *r = (struct alloc_if_r *)&tb->in.pkt.data;
+		assert(r->r == ALLOC_IF_OK);
+		assert(r->start == 0);
+		assert(r->end == 10);
+
+		struct alloc_if_rm rm = {.space = 0, .start = 0, .end = 10};
+		struct packet pkt = create_packet(0, ALLOC_IF_RM, sizeof(rm), &rm, PACKET_WRITE);
+		assert(SEND(tb, tb->dut, pkt) == OK);
+		tb->state = QUERY_NONEXISTING;
+		tb->in.busy = false;
+		break;
+	}
+
+	case QUERY_NONEXISTING: {
+		if (!tb->in.busy)
+			break;
+
+		struct alloc_if_r *r = (struct alloc_if_r *)&tb->in.pkt.data;
+		assert(r->r == ALLOC_IF_OK);
+
+		struct alloc_if_q q = {.space = 0, .addr = 5};
+		struct packet pkt = create_packet(0, ALLOC_IF_Q, sizeof(q), &q, PACKET_WRITE);
+		assert(SEND(tb, tb->dut, pkt) == OK);
+		tb->state = FINAL;
+		tb->in.busy = false;
+		break;
+	}
+
+	case FINAL: {
+		if (!tb->in.busy)
+			break;
+
+		struct alloc_if_r *r = (struct alloc_if_r *)&tb->in.pkt.data;
+		assert(r->r != ALLOC_IF_OK);
+		return DONE;
+	}
+
+	default: abort();
+	}
+
+	return OK;
+}
+
+struct component *create_testbench()
+{
+	struct tb *tb = calloc(1, sizeof(struct tb));
+	tb->component.clock = (clock_callback)tb_clock;
+	tb->component.receive = (receive_callback)tb_receive;
+	return (struct component *)tb;
+}
+
+stat testbench_connect(struct component *tb, struct component *dut)
+{
+	struct tb *t = (struct tb *)tb;
+	t->dut = dut;
+	return OK;
+}
diff --git a/tests/simple_ideal_alloc/testbench.h b/tests/simple_ideal_alloc/testbench.h
new file mode 100644
index 0000000..6f72060
--- /dev/null
+++ b/tests/simple_ideal_alloc/testbench.h
@@ -0,0 +1,9 @@
+#ifndef GRAN_IDEAL_ALLOC_TESTBENCH_H
+#define GRAN_IDEAL_ALLOC_TESTBENCH_H
+
+#include <gran/component.h>
+
+struct component *create_testbench();
+stat testbench_connect(struct component *tb, struct component *dut);
+
+#endif /* GRAN_IDEAL_ALLOC_TESTBENCH_H */
diff --git a/tests/simple_mem/source.mk b/tests/simple_mem/source.mk
index 1c19967..3a65965 100644
--- a/tests/simple_mem/source.mk
+++ b/tests/simple_mem/source.mk
@@ -1,4 +1,4 @@
-TEST_OBJS	!= ./scripts/gen-deps --sources "tests/simple_mem/traffic_gen.c"
+TRAFFIC_OBJ	!= ./scripts/gen-deps --sources "tests/simple_mem/traffic_gen.c"
 NO_BUS_TEST_OBJ	!= ./scripts/gen-deps --sources "tests/simple_mem/no_bus.c"
 BUS_TEST_OBJ	!= ./scripts/gen-deps --sources "tests/simple_mem/bus.c"
 MANY_TEST_OBJ	!= ./scripts/gen-deps --sources "tests/simple_mem/many.c"
@@ -7,11 +7,11 @@ TEST_PROGS	+= build/tests/simple_mem/no_bus \
 		   build/tests/simple_mem/bus \
 		   build/tests/simple_mem/many
 
-build/tests/simple_mem/no_bus: $(NO_BUS_TEST_OBJ) $(TEST_OBJS) $(OBJS)
-	$(COMPILE) $(NO_BUS_TEST_OBJ) $(TEST_OBJS) $(OBJS) -o $@
+build/tests/simple_mem/no_bus: $(NO_BUS_TEST_OBJ) $(TRAFFIC_OBJ) $(OBJS)
+	$(COMPILE) $(NO_BUS_TEST_OBJ) $(TRAFFIC_OBJ) $(OBJS) -o $@
 
-build/tests/simple_mem/bus: $(BUS_TEST_OBJ) $(TEST_OBJS) $(OBJS)
-	$(COMPILE) $(BUS_TEST_OBJ) $(TEST_OBJS) $(OBJS) -o $@
+build/tests/simple_mem/bus: $(BUS_TEST_OBJ) $(TRAFFIC_OBJ) $(OBJS)
+	$(COMPILE) $(BUS_TEST_OBJ) $(TRAFFIC_OBJ) $(OBJS) -o $@
 
-build/tests/simple_mem/many: $(MANY_TEST_OBJ) $(TEST_OBJS) $(OBJS)
-	$(COMPILE) $(MANY_TEST_OBJ) $(TEST_OBJS) $(OBJS) -o $@
+build/tests/simple_mem/many: $(MANY_TEST_OBJ) $(TRAFFIC_OBJ) $(OBJS)
+	$(COMPILE) $(MANY_TEST_OBJ) $(TRAFFIC_OBJ) $(OBJS) -o $@