3d mesh

11 files changed, 493 insertions, 31 deletions

diff --git a/TODO b/TODO
index 00de3fc..ebd482e 100644
--- a/TODO
+++ b/TODO
@@ -1 +1,5 @@
 add stats
+
++ torus3d gets stuck because sometimes there's not output path, I guess one
+  solution could be to add two 'output' virtual channels, but that seems a bit
+  wasteful. I'll have to think about some alternatives
diff --git a/include/gran/component.h b/include/gran/component.h
index 289d0a6..4b728a4 100644
--- a/include/gran/component.h
+++ b/include/gran/component.h
@@ -36,6 +36,7 @@ struct component {
 
 static inline stat send(struct component *from, struct component *to, struct packet pkt)
 {
+	assert(to && from);
 	if (!to->receive) {
 		/* printf formatted asserts would maybe be preferable? */
 		error(
diff --git a/include/gran/grid/node3d.h b/include/gran/grid/node3d.h
new file mode 100644
index 0000000..e424d9b
--- /dev/null
+++ b/include/gran/grid/node3d.h
@@ -0,0 +1,38 @@
+#ifndef GRAN_GRID_NODE3D_H
+#define GRAN_GRID_NODE3D_H
+
+/** @todo rename to mesh to follow conventions a bit better */
+
+#include <gran/component.h>
+#include <stdint.h>
+
+struct component *create_grid_node3d(uint8_t x, uint8_t y, uint8_t z);
+
+stat grid_node3d_connect(struct component *node,
+		struct component *n,
+		struct component *s,
+		struct component *w,
+		struct component *e,
+		struct component *u,
+		struct component *d,
+		struct component *l);
+
+static inline uint64_t grid3d_addr(uint8_t x, uint8_t y, uint8_t z, uint32_t off)
+{
+	return off
+		| ((uint64_t)x << 32)
+		| ((uint64_t)y << 40)
+		| ((uint64_t)z << 48)
+		;
+}
+
+static inline void addr_grid3d(uint64_t addr, uint8_t *x, uint8_t *y, uint8_t *z, uint32_t *off)
+{
+	if (off) *off = addr & 0xffffffff;
+	if (x) *x = (addr >> 32) & 0xff;
+	if (y) *y = (addr >> 40) & 0xff;
+	if (z) *z = (addr >> 48) & 0xff;
+	assert(((addr >> 56) & 0xff) == 0);
+}
+
+#endif /* GRAN_GRID_NODE3D_H */
diff --git a/include/gran/packet.h b/include/gran/packet.h
index 2fec036..85ff961 100644
--- a/include/gran/packet.h
+++ b/include/gran/packet.h
@@ -179,20 +179,15 @@ static inline uint64_t packet_convu64(struct packet *pkt)
 	return res;
 }
 
-/* not good, should be taken from the local clock domain or something
- * but eh for now */
-extern uint64_t ticker;
-
 static inline struct packet create_packet(uint64_t from, uint64_t to, uint64_t size, void *data, enum packet_flags flags)
 {
 	assert(size <= 64);
 	assert(packet_align(from) == from);
 
-
 	uint64_t aligned = packet_align(to);
 	uint64_t mask = packet_mask(to, size);
 	struct packet pkt = (struct packet){
-		.timestamp = ticker++,
+		.timestamp = 0,
 		.from = from,
 		.to = aligned,
 		.mask = mask,
diff --git a/src/grid/node3d.c b/src/grid/node3d.c
new file mode 100644
index 0000000..f404ea0
--- /dev/null
+++ b/src/grid/node3d.c
@@ -0,0 +1,205 @@
+#include <gran/grid/node3d.h>
+
+struct reg {
+	struct packet pkt;
+	bool busy;
+};
+
+struct node3d {
+	struct component component;
+	uint8_t x, y, z;
+
+	uint64_t timestamp;
+
+	struct component *n, *s, *w, *e, *u, *d, *l;
+
+	struct reg n_in, s_in, w_in, e_in, u_in, d_in, l_in;
+};
+
+static stat reg_receive(struct reg *r, struct packet pkt)
+{
+	if (r->busy)
+		return EBUSY;
+
+	r->pkt = pkt;
+	r->busy = true;
+	return OK;
+}
+
+/* LX = node.x > pkt.x, etc */
+enum match {
+	LX = (1 << 0),
+	LY = (1 << 1),
+	LZ = (1 << 2),
+	GX = (1 << 3),
+	GY = (1 << 4),
+	GZ = (1 << 5),
+	NX = (1 << 6),
+	NY = (1 << 7),
+	NZ = (1 << 8),
+};
+
+static void maybe_route_reg(struct node3d *node3d, struct reg *reg, enum match m, uint64_t *oldest, struct packet **pkt, bool **busy)
+{
+	if (!reg->busy)
+		return;
+
+	uint8_t x, y, z;
+	addr_grid3d(reg->pkt.to, &x, &y, &z, NULL);
+
+	if ((m & LX) && x < node3d->x)
+		return;
+
+	if ((m & LY) && y < node3d->y)
+		return;
+
+	if ((m & LZ) && z < node3d->z)
+		return;
+
+	if ((m & GX) && x > node3d->x)
+		return;
+
+	if ((m & GY) && y > node3d->y)
+		return;
+
+	if ((m & GZ) && z > node3d->z)
+		return;
+
+	if ((m & NX) && x == node3d->x)
+		return;
+
+	if ((m & NY) && y == node3d->y)
+		return;
+
+	if ((m & NZ) && z == node3d->z)
+		return;
+
+	if (reg->pkt.timestamp < *oldest) {
+		*oldest = reg->pkt.timestamp;
+		*busy = &reg->busy;
+		*pkt = &reg->pkt;
+	}
+}
+
+static stat route(struct node3d *node3d, struct component *next, enum match m)
+{
+	uint64_t oldest = -1; struct packet *pkt = NULL; bool *busy = NULL;
+	maybe_route_reg(node3d, &node3d->l_in, m, &oldest, &pkt, &busy);
+	maybe_route_reg(node3d, &node3d->n_in, m, &oldest, &pkt, &busy);
+	maybe_route_reg(node3d, &node3d->s_in, m, &oldest, &pkt, &busy);
+	maybe_route_reg(node3d, &node3d->e_in, m, &oldest, &pkt, &busy);
+	maybe_route_reg(node3d, &node3d->w_in, m, &oldest, &pkt, &busy);
+	maybe_route_reg(node3d, &node3d->u_in, m, &oldest, &pkt, &busy);
+	maybe_route_reg(node3d, &node3d->d_in, m, &oldest, &pkt, &busy);
+
+	/* no suitable match */
+	if (pkt == NULL)
+		return OK;
+
+	assert(busy);
+
+	if (!next) {
+		abort(); /* for now, eventually should probably return to sender */
+		return OK;
+	}
+
+	stat ret = SEND(node3d, next, *pkt);
+	if (ret == EBUSY)
+		return OK;
+
+	*busy = false;
+	return OK;
+}
+
+static stat node3d_clock(struct node3d *node3d)
+{
+	node3d->timestamp++;
+
+	stat ret = OK;
+	if ((ret = route(node3d, node3d->e, LX | NX)))
+		return ret;
+
+	if ((ret = route(node3d, node3d->w, GX | NX)))
+		return ret;
+
+	if ((ret = route(node3d, node3d->n, LX | GX | LY | NY)))
+		return ret;
+
+	if ((ret = route(node3d, node3d->s, LX | GX | GY | NY)))
+		return ret;
+
+	if ((ret = route(node3d, node3d->u, LX | GX | LY | GY | LZ | NZ)))
+		return ret;
+
+	if ((ret = route(node3d, node3d->d, LX | GX | LY | GY | GZ | NZ)))
+		return ret;
+
+	if ((ret = route(node3d, node3d->l, LX | LY | LZ | GX | GY | GZ)))
+		return ret;
+
+	return OK;
+}
+
+static stat node3d_receive(struct node3d *node3d, struct component *from, struct packet pkt)
+{
+	if (from == node3d->l) {
+		/* add time when packet entered network */
+		pkt.timestamp = node3d->timestamp;
+		return reg_receive(&node3d->l_in, pkt);
+	}
+
+	if (from == node3d->n)
+		return reg_receive(&node3d->n_in, pkt);
+
+	if (from == node3d->s)
+		return reg_receive(&node3d->s_in, pkt);
+
+	if (from == node3d->w)
+		return reg_receive(&node3d->w_in, pkt);
+
+	if (from == node3d->e)
+		return reg_receive(&node3d->e_in, pkt);
+
+	if (from == node3d->u)
+		return reg_receive(&node3d->u_in, pkt);
+
+	if (from == node3d->d)
+		return reg_receive(&node3d->d_in, pkt);
+
+	abort();
+	return OK;
+}
+
+struct component *create_grid_node3d(uint8_t x, uint8_t y, uint8_t z)
+{
+	struct node3d *node = calloc(1, sizeof(struct node3d));
+	if (!node)
+		return NULL;
+
+	node->component.receive = (receive_callback)node3d_receive;
+	node->component.clock = (clock_callback)node3d_clock;
+	node->x = x;
+	node->y = y;
+	node->z = z;
+	return (struct component *)node;
+}
+
+stat grid_node3d_connect(struct component *node,
+		struct component *n,
+		struct component *s,
+		struct component *w,
+		struct component *e,
+		struct component *u,
+		struct component *d,
+		struct component *l)
+{
+	struct node3d *node3d = (struct node3d *)node;
+	node3d->n = n;
+	node3d->s = s;
+	node3d->w = w;
+	node3d->e = e;
+	node3d->u = u;
+	node3d->d = d;
+	node3d->l = l;
+	return OK;
+}
diff --git a/src/grid/source.mk b/src/grid/source.mk
index e23d7db..79fe708 100644
--- a/src/grid/source.mk
+++ b/src/grid/source.mk
@@ -1 +1 @@
-SOURCES += src/grid/node.c
+SOURCES += src/grid/node.c src/grid/node3d.c
diff --git a/src/root.c b/src/root.c
index 366822e..172728e 100644
--- a/src/root.c
+++ b/src/root.c
@@ -8,9 +8,6 @@
 
 #define MAX_DOMAINS 512
 
-/** @todo ugly global, time values should be taken from local clock domain */
-uint64_t ticker = 0;
-
 struct gran_root {
 	size_t num_domains;
 	struct clock_domain *(domains[MAX_DOMAINS]);
diff --git a/src/torus3d/node.c b/src/torus3d/node.c
index 15cc7ee..4111c48 100644
--- a/src/torus3d/node.c
+++ b/src/torus3d/node.c
@@ -20,6 +20,8 @@ struct torus3d_node {
 	struct port port_x, port_y, port_z;
 
 	struct reg x_in, y_in, z_in, child_in;
+
+	bool prio;
 };
 
 static stat port_receive(struct torus3d_node *torus3d, struct port *port, struct reg *reg)
@@ -37,23 +39,15 @@ static stat port_receive(struct torus3d_node *torus3d, struct port *port, struct
 
 	/* Dally/spiral routing though I'm a bit unsure if this works for 2D/3D
 	 * toruses (1D seems to work, 2D not so much atm) */
-	int chan = 0;
-	if (port == &torus3d->port_x)
-		chan = sx < dx;
-	else if (port == &torus3d->port_y)
-		chan = sy < dy;
-	else if (port == &torus3d->port_z)
-		chan = sz < dz;
-	else
-		abort();
-
+	int chan = is_set(&reg->pkt, PACKET_DONE);
 	if (port->r[chan].busy)
 		return OK;
 
-	printf("(%d, %d, %d) to (%d, %d, %d) via (%d, %d, %d)\n",
+	printf("(%d, %d, %d) to (%d, %d, %d) via (%d, %d, %d) c %d\n",
 			sx, sy, sz,
 			dx, dy, dz,
-			torus3d->x, torus3d->y, torus3d->z);
+			torus3d->x, torus3d->y, torus3d->z,
+			chan);
 
 	port->r[chan].pkt = reg->pkt;
 	port->r[chan].busy = true;
@@ -113,18 +107,23 @@ static void maybe_route_reg(struct torus3d_node *torus3d, struct reg *reg, enum
 	}
 }
 
-static void maybe_route_port(struct torus3d_node *torus3d, struct port *port, enum match m, uint64_t *oldest, struct packet **pkt, bool **busy)
-{
-	maybe_route_reg(torus3d, &port->r[0], m, oldest, pkt, busy);
-	maybe_route_reg(torus3d, &port->r[1], m, oldest, pkt, busy);
-}
-
 static stat route(struct torus3d_node *torus3d, struct component *next, enum match m)
 {
+	bool prio = torus3d->prio;
 	uint64_t oldest = -1; struct packet *pkt = NULL; bool *busy = NULL;
-	maybe_route_port(torus3d, &torus3d->port_x, m, &oldest, &pkt, &busy);
-	maybe_route_port(torus3d, &torus3d->port_y, m, &oldest, &pkt, &busy);
-	maybe_route_port(torus3d, &torus3d->port_z, m, &oldest, &pkt, &busy);
+
+	/* prioritise current priority port */
+	maybe_route_reg(torus3d, &torus3d->port_x.r[prio], m, &oldest, &pkt, &busy);
+	maybe_route_reg(torus3d, &torus3d->port_y.r[prio], m, &oldest, &pkt, &busy);
+	maybe_route_reg(torus3d, &torus3d->port_z.r[prio], m, &oldest, &pkt, &busy);
+
+	/* if no suitable match found, check other ports as well */
+	if (pkt == NULL) {
+		maybe_route_reg(torus3d, &torus3d->port_x.r[!prio], m, &oldest, &pkt, &busy);
+		maybe_route_reg(torus3d, &torus3d->port_y.r[!prio], m, &oldest, &pkt, &busy);
+		maybe_route_reg(torus3d, &torus3d->port_z.r[!prio], m, &oldest, &pkt, &busy);
+	}
+
 	maybe_route_reg(torus3d, &torus3d->child_in, m, &oldest, &pkt, &busy);
 
 	/* no suitable match */
@@ -143,6 +142,8 @@ static stat route(struct torus3d_node *torus3d, struct component *next, enum mat
 
 static stat torus3d_clock(struct torus3d_node *torus3d)
 {
+	torus3d->prio = !torus3d->prio;
+
 	stat ret = OK;
 	if ((ret = port_receive(torus3d, &torus3d->port_x, &torus3d->x_in)))
 		return ret;
diff --git a/tests/simple_grid3d/sim.c b/tests/simple_grid3d/sim.c
new file mode 100644
index 0000000..6df29dd
--- /dev/null
+++ b/tests/simple_grid3d/sim.c
@@ -0,0 +1,142 @@
+#include <assert.h>
+
+#include <gran/root.h>
+#include <gran/mem/simple_mem.h>
+#include <gran/bus/simple_bus.h>
+#include <gran/uart/simple_uart.h>
+#include <gran/grid/node3d.h>
+#include <gran/cpu/riscv/simple_riscv64.h>
+
+#include "../build/tests/simple_grid3d/test.inc"
+
+static size_t idx_1d(int x, int y, int z, uint8_t xw, uint8_t yw, uint8_t zw)
+{
+	(void)xw; /* maybe unused */
+	assert(0 <= x && x < xw);
+	assert(0 <= y && y < yw);
+	assert(0 <= z && z < zw);
+	return (x * yw * zw) + (y * zw) + z;
+}
+
+static struct component *grid_at(struct component **grid,
+		int x, int y, int z,
+		uint8_t xw, uint8_t yw, uint8_t zw)
+{
+	if (x < 0)
+		return NULL;
+
+	if (y < 0)
+		return NULL;
+
+	if (z < 0)
+		return NULL;
+
+	if (x >= xw)
+		return NULL;
+
+	if (y >= yw)
+		return NULL;
+
+	if (z >= zw)
+		return NULL;
+
+	return grid[idx_1d(x, y, z, xw, yw, zw)];
+}
+
+static void connect_grid3d(struct component **grid, struct component *c,
+		uint8_t x,  uint8_t y,  uint8_t z,
+		uint8_t xw, uint8_t yw, uint8_t zw)
+{
+	grid_node3d_connect(grid_at(grid, x, y, z, xw, yw, zw),
+			grid_at(grid, x  , y+1, z  , xw, yw, zw),
+			grid_at(grid, x  , y-1, z  , xw, yw, zw),
+			grid_at(grid, x-1, y  , z  , xw, yw, zw),
+			grid_at(grid, x+1, y  , z  , xw, yw, zw),
+			grid_at(grid, x  , y  , z+1, xw, yw, zw),
+			grid_at(grid, x  , y  , z-1, xw, yw, zw),
+			c);
+}
+
+static stat build_torus3d(struct clock_domain *clk, uint8_t x, uint8_t y, uint8_t z)
+{
+	struct component **grid = calloc(x * y * z, sizeof(struct component *));
+	assert(grid);
+
+	struct component **pes = calloc(x * y * z, sizeof(struct component *));
+	assert(pes);
+
+	for (size_t i = 0; i < x; ++i)
+	for (size_t j = 0; j < y; ++j)
+	for (size_t k = 0; k < z; ++k) {
+		struct component *node = create_grid_node3d(i, j, k);
+		clock_domain_add(clk, node);
+		grid[idx_1d(i, j, k, x, y, z)] = node;
+
+		if (i == 0 && j == 0 && k == 0)
+			continue;
+
+		if (i == 0 && j == 0 && k == 1)
+			continue;
+
+		struct component *imem = create_simple_mem(4096);
+		init_simple_mem(imem, 0,
+				build_tests_simple_grid3d_test_bin_len,
+				build_tests_simple_grid3d_test_bin);
+
+		uint64_t rcv = grid3d_addr(i, j, k, 0);
+		struct component *rv64 = create_simple_riscv64(rcv, 0, imem, node);
+		simple_riscv64_set_reg(rv64, 10, i); /* a0 */
+		simple_riscv64_set_reg(rv64, 11, j); /* a1 */
+		simple_riscv64_set_reg(rv64, 12, k); /* a2 */
+		simple_riscv64_set_reg(rv64, 13, x); /* a3 */
+		simple_riscv64_set_reg(rv64, 14, y); /* a4 */
+		simple_riscv64_set_reg(rv64, 15, z); /* a5 */
+
+		clock_domain_add(clk, rv64);
+		clock_domain_add(clk, imem);
+
+		pes[idx_1d(i, j, k, x, y, z)] = rv64;
+	}
+
+	struct component *uart = create_simple_uart();
+	clock_domain_add(clk, uart);
+	connect_grid3d(grid, uart, 0, 0, 0, x, y, z);
+
+	struct component *dmem = create_simple_mem(4096);
+	clock_domain_add(clk, dmem);
+	connect_grid3d(grid, dmem, 0, 0, 1, x, y, z);
+
+	for (int i = 0; i < x; ++i)
+	for (int j = 0; j < y; ++j)
+	for (int k = 0; k < z; ++k) {
+		if (i == 0 && j == 0 && k == 0)
+			continue;
+
+		if (i == 0 && j == 0 && k == 1)
+			continue;
+
+		connect_grid3d(grid,
+				pes[idx_1d(i, j, k, x, y, z)],
+				i, j, k, x, y, z);
+	}
+
+	free(grid);
+	free(pes);
+	return OK;
+}
+
+int main()
+{
+	struct clock_domain *clk = create_clock_domain(NS(1));
+
+	stat r = build_torus3d(clk, 4, 4, 4);
+	assert(r == OK);
+
+	struct gran_root *root = create_root();
+	root_add_clock(root, clk);
+
+	r = root_run(root);
+	assert(r == OK);
+
+	destroy_root(root);
+}
diff --git a/tests/simple_grid3d/source.mk b/tests/simple_grid3d/source.mk
new file mode 100644
index 0000000..4c19568
--- /dev/null
+++ b/tests/simple_grid3d/source.mk
@@ -0,0 +1,18 @@
+GRID3D_TEST_OBJ		!= ./scripts/gen-deps --sources "tests/simple_grid3d/sim.c"
+TEST_PROGS		+= build/tests/simple_grid3d/sim
+
+build/tests/simple_grid3d/test.inc: tests/simple_grid3d/test.c
+	riscv64-unknown-elf-gcc -O2 -Wall -Wextra -ffreestanding -nostdlib \
+		-march=rv64i -mabi=lp64 \
+		-o build/tests/simple_grid3d/test \
+		tests/simple_grid3d/test.c
+	riscv64-unknown-elf-objcopy -Obinary \
+		build/tests/simple_grid3d/test \
+		build/tests/simple_grid3d/test.bin
+	xxd -i build/tests/simple_grid3d/test.bin \
+		> build/tests/simple_grid3d/test.inc
+
+build/tests/simple_grid3d/sim.o: build/tests/simple_grid3d/test.inc
+
+build/tests/simple_grid3d/sim: $(GRID3D_TEST_OBJ) $(OBJS)
+	$(COMPILE) $(GRID3D_TEST_OBJ) $(OBJS) -o $@
diff --git a/tests/simple_grid3d/test.c b/tests/simple_grid3d/test.c
new file mode 100644
index 0000000..2953d41
--- /dev/null
+++ b/tests/simple_grid3d/test.c
@@ -0,0 +1,61 @@
+__attribute__((always_inline))
+static inline void print_int8(volatile char *uart, unsigned x)
+{
+	*uart = ((x >> 4) & 0xf) + '0';
+	*uart = ((x >> 0) & 0xf) + '0';
+}
+
+__attribute__((always_inline))
+static inline void print_addr(volatile char *uart, unsigned x, unsigned y, unsigned z)
+{
+	*uart = '(';
+	print_int8(uart, x);
+	*uart = ',';
+	*uart = ' ';
+	print_int8(uart, y);
+	*uart = ',';
+	*uart = ' ';
+	print_int8(uart, z);
+	*uart = ')';
+	*uart = '\n';
+}
+
+__attribute__((always_inline))
+static inline unsigned wrap(unsigned x, unsigned X)
+{
+	return x + 1 >= X ? 0 : x + 1;
+}
+
+__attribute__((always_inline))
+static inline unsigned next_idx(unsigned x, unsigned y, unsigned z, unsigned X, unsigned Y, unsigned Z)
+{
+	unsigned zi = wrap(z, Z);
+	unsigned yi = zi < z ? wrap(y, Y) : y;
+	unsigned xi = yi < y ? wrap(x, X) : x;
+
+	return (xi << 16) | (yi << 8) | zi;
+}
+
+void _start(unsigned x, unsigned y, unsigned z, unsigned X, unsigned Y, unsigned Z)
+{
+	volatile char *uart = (char *)4096;
+	/* x = 1ULL << 32, y = 1ULL << 40, z = 1ULL << 48 I guess */
+	volatile unsigned *control = (unsigned *)(1ULL << 48);
+
+
+	if (x == 0 && y == 0 && z == 2) {
+		goto do_work;
+	} else {
+		while (*control != ((x << 16) | (y << 8) | z)) {}
+	}
+
+do_work:
+	print_addr(uart, x, y, z);
+	*control = next_idx(x, y, z, X, Y, Z);
+
+	if (x == X - 1 && y == Y - 1 && z == Z - 1)
+		asm("ebreak");
+
+	/* otherwise just loop */
+	while (1) {}
+}