initial torus stuff

+ Not quite deadlock free for 2D/3D for whatever reason

11 files changed, 489 insertions, 0 deletions

diff --git a/NOTES b/NOTES
new file mode 100644
index 0000000..4b0a0ec
--- /dev/null
+++ b/NOTES
@@ -0,0 +1,26 @@
+Slightly drunken ramblings:
+
+Currently, I'm imagining that a 3D torus with one-way communication would
+probably be the best way forward. It has some nice properties like a fairly
+simple construction, decent average response times (but not the best minimum
+response times, unfortunately) and a fairly simple broadcast scheme (though
+without ack).
+
+Coherence is of course more difficult, but I would imagine that
+changing the memory model to be a bit more loose wouldn't hurt. Essentially, we
+would have one node somewhere be a global 'lock' that gives out LR/SC
+permissions, fairly high latency unfortunately but arguably the simplest
+approach. All caches are not coherent, but would have to respect atomic
+operations.
+
+One maybe interesting thing could be to not have virtual memory, instead opt for
+some kind of k-tree with byte-accurate permissions, kind of like cheri. Each
+pointer could have a second pointer that tells which allocation it is from, and
+we have a TLB-like cache for fast lookups. We could also have multiple of these
+trees, one in local memory for private allocations, for example. With process
+IDs, my beloved. Also, semi-cooperative interrupts? With enough cores, static
+thread scheduling might also be workable. Potentially also external node access
+checking, so untrusted packets can't read memory that's not for some process
+(avoid stuff like the router capturing thing in Linux wifi fw).
+
+
diff --git a/include/gran/packet.h b/include/gran/packet.h
index 5f8bd9c..2fec036 100644
--- a/include/gran/packet.h
+++ b/include/gran/packet.h
@@ -22,6 +22,7 @@ struct packet {
 	uint64_t from;
 	uint64_t to;
 	uint64_t mask;
+	uint64_t timestamp;
 	uint8_t data[64];
 	enum packet_flags flags;
 };
@@ -178,14 +179,20 @@ 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++,
 		.from = from,
 		.to = aligned,
 		.mask = mask,
diff --git a/include/gran/torus3d/node.h b/include/gran/torus3d/node.h
new file mode 100644
index 0000000..bd02a1f
--- /dev/null
+++ b/include/gran/torus3d/node.h
@@ -0,0 +1,35 @@
+#ifndef GRAN_TORUS3D_NODE_H
+#define GRAN_TORUS3D_NODE_H
+
+#include <gran/component.h>
+#include <stdint.h>
+
+struct component *create_torus3d_node(uint8_t x, uint8_t y, uint8_t z);
+
+stat torus3d_node_connect(struct component *node,
+		struct component *x_in,
+		struct component *y_in,
+		struct component *z_in,
+		struct component *child,
+		struct component *x_out,
+		struct component *y_out,
+		struct component *z_out);
+
+static inline void addr_torus3d(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);
+}
+
+static inline uint64_t torus3d_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)
+		   ;
+}
+
+#endif /* GRAN_TORUS3D_NODE_H */
diff --git a/src/mem/simple_mem.c b/src/mem/simple_mem.c
index 0a3a3ce..77d8319 100644
--- a/src/mem/simple_mem.c
+++ b/src/mem/simple_mem.c
@@ -6,6 +6,7 @@
 #include <stdbool.h>
 
 #include <gran/mem/simple_mem.h>
+#include <gran/torus3d/node.h>
 
 struct simple_mem {
 	struct component component;
diff --git a/src/root.c b/src/root.c
index 172728e..366822e 100644
--- a/src/root.c
+++ b/src/root.c
@@ -8,6 +8,9 @@
 
 #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
new file mode 100644
index 0000000..15cc7ee
--- /dev/null
+++ b/src/torus3d/node.c
@@ -0,0 +1,221 @@
+#include <gran/torus3d/node.h>
+
+struct reg {
+	struct packet pkt;
+	bool busy;
+};
+
+struct port {
+	struct reg r[2];
+};
+
+struct torus3d_node {
+	struct component component;
+	uint8_t x, y, z /*, w for 4D but that might be a bit overkill*/;
+
+	struct component *x_next, *y_next, *z_next,
+			 *x_prev, *y_prev, *z_prev,
+			 *child;
+
+	struct port port_x, port_y, port_z;
+
+	struct reg x_in, y_in, z_in, child_in;
+};
+
+static stat port_receive(struct torus3d_node *torus3d, struct port *port, struct reg *reg)
+{
+	if (!reg->busy)
+		return OK;
+
+	/* source */
+	uint8_t sx, sy, sz;
+	addr_torus3d(reg->pkt.from, &sx, &sy, &sz, NULL);
+
+	/* dst */
+	uint8_t dx, dy, dz;
+	addr_torus3d(reg->pkt.to, &dx, &dy, &dz, NULL);
+
+	/* 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();
+
+	if (port->r[chan].busy)
+		return OK;
+
+	printf("(%d, %d, %d) to (%d, %d, %d) via (%d, %d, %d)\n",
+			sx, sy, sz,
+			dx, dy, dz,
+			torus3d->x, torus3d->y, torus3d->z);
+
+	port->r[chan].pkt = reg->pkt;
+	port->r[chan].busy = true;
+	reg->busy = false;
+	return OK;
+}
+
+static stat reg_receive(struct reg *r, struct packet pkt)
+{
+	if (r->busy)
+		return EBUSY;
+
+	r->pkt = pkt;
+	r->busy = true;
+	return OK;
+}
+
+enum match {
+	MX = (1 << 0),
+	MY = (1 << 1),
+	MZ = (1 << 2),
+	NX = (1 << 3),
+	NY = (1 << 4),
+	NZ = (1 << 5),
+};
+
+static void maybe_route_reg(struct torus3d_node *torus3d, struct reg *reg, enum match m, uint64_t *oldest, struct packet **pkt, bool **busy)
+{
+	if (!reg->busy)
+		return;
+
+	uint8_t x, y, z;
+	addr_torus3d(reg->pkt.to, &x, &y, &z, NULL);
+
+	if ((m & MX) && x != torus3d->x)
+		return;
+
+	if ((m & MY) && y != torus3d->y)
+		return;
+
+	if ((m & MZ) && z != torus3d->z)
+		return;
+
+	if ((m & NX) && x == torus3d->x)
+		return;
+
+	if ((m & NY) && y == torus3d->y)
+		return;
+
+	if ((m & NZ) && z == torus3d->z)
+		return;
+
+	if (reg->pkt.timestamp < *oldest) {
+		*oldest = reg->pkt.timestamp;
+		*busy = &reg->busy;
+		*pkt = &reg->pkt;
+	}
+}
+
+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)
+{
+	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);
+	maybe_route_reg(torus3d, &torus3d->child_in, m, &oldest, &pkt, &busy);
+
+	/* no suitable match */
+	if (pkt == NULL)
+		return OK;
+
+	assert(busy);
+
+	stat ret = SEND(torus3d, next, *pkt);
+	if (ret == EBUSY)
+		return OK;
+
+	*busy = false;
+	return OK;
+}
+
+static stat torus3d_clock(struct torus3d_node *torus3d)
+{
+	stat ret = OK;
+	if ((ret = port_receive(torus3d, &torus3d->port_x, &torus3d->x_in)))
+		return ret;
+
+	if ((ret = port_receive(torus3d, &torus3d->port_y, &torus3d->y_in)))
+		return ret;
+
+	if ((ret = port_receive(torus3d, &torus3d->port_z, &torus3d->z_in)))
+		return ret;
+
+	if ((ret = route(torus3d, torus3d->x_next, NX)))
+		return ret;
+
+	if ((ret = route(torus3d, torus3d->y_next, NY | MX)))
+		return ret;
+
+	if ((ret = route(torus3d, torus3d->z_next, NZ | MX | MY)))
+		return ret;
+
+	if ((ret = route(torus3d, torus3d->child, MX | MY | MZ)))
+		return ret;
+
+	return OK;
+}
+
+static stat torus3d_receive(struct torus3d_node *torus3d, struct component *from, struct packet pkt)
+{
+	if (from == torus3d->child)
+		return reg_receive(&torus3d->child_in, pkt);
+
+	if (from == torus3d->x_prev)
+		return reg_receive(&torus3d->x_in, pkt);
+
+	if (from == torus3d->y_prev)
+		return reg_receive(&torus3d->y_in, pkt);
+
+	if (from == torus3d->z_prev)
+		return reg_receive(&torus3d->z_in, pkt);
+
+	abort();
+	return OK;
+}
+
+struct component *create_torus3d_node(uint8_t x, uint8_t y, uint8_t z)
+{
+	struct torus3d_node *node = calloc(1, sizeof(struct torus3d_node));
+	if (!node)
+		return NULL;
+
+	node->component.receive = (receive_callback)torus3d_receive;
+	node->component.clock = (clock_callback)torus3d_clock;
+	node->x = x;
+	node->y = y;
+	node->z = z;
+	return (struct component *)node;
+}
+
+stat torus3d_node_connect(struct component *node,
+		struct component *x_in,
+		struct component *y_in,
+		struct component *z_in,
+		struct component *child,
+		struct component *x_out,
+		struct component *y_out,
+		struct component *z_out)
+{
+	struct torus3d_node *n = (struct torus3d_node *)node;
+	n->x_prev = x_in;
+	n->y_prev = y_in;
+	n->z_prev = z_in;
+	n->child = child;
+	n->x_next = x_out;
+	n->y_next = y_out;
+	n->z_next = z_out;
+	return OK;
+}
diff --git a/src/torus3d/source.mk b/src/torus3d/source.mk
new file mode 100644
index 0000000..4770dad
--- /dev/null
+++ b/src/torus3d/source.mk
@@ -0,0 +1 @@
+SOURCES += src/torus3d/node.c
diff --git a/src/uart/simple_uart.c b/src/uart/simple_uart.c
index 1528a70..e640ae1 100644
--- a/src/uart/simple_uart.c
+++ b/src/uart/simple_uart.c
@@ -38,6 +38,7 @@ static stat simple_uart_receive(struct simple_uart *uart, struct component *from
 	}
 
 	putchar(packet_convu8(&pkt));
+	fflush(stdout);
 	set_flags(&uart->pkt, PACKET_DONE);
 	return OK;
 }
diff --git a/tests/simple_torus3d/sim.c b/tests/simple_torus3d/sim.c
new file mode 100644
index 0000000..b3ff41b
--- /dev/null
+++ b/tests/simple_torus3d/sim.c
@@ -0,0 +1,115 @@
+#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/torus3d/node.h>
+#include <gran/cpu/riscv/simple_riscv64.h>
+
+#include "../build/tests/simple_torus3d/test.inc"
+
+static size_t idx_1d(int x, int y, int z, uint8_t xw, uint8_t yw, uint8_t zw)
+{
+	uint8_t xi = (x + xw) % xw;
+	uint8_t yi = (y + yw) % yw;
+	uint8_t zi = (z + zw) % zw;
+	return (xi * yw * zw) + (yi * zw) + zi;
+}
+
+static void torus3d_connect_grid(struct component **grid, struct component *c,
+		uint8_t x,  uint8_t y,  uint8_t z,
+		uint8_t xw, uint8_t yw, uint8_t zw)
+{
+	torus3d_node_connect(grid[idx_1d(x, y, z, xw, yw, zw)],
+			grid[idx_1d(x-1, y  , z  , xw, yw, zw)],
+			grid[idx_1d(x  , y-1, z  , xw, yw, zw)],
+			grid[idx_1d(x  , y  , z-1, xw, yw, zw)],
+			c,
+			grid[idx_1d(x+1, y  , z  , xw, yw, zw)],
+			grid[idx_1d(x  , y+1, z  , xw, yw, zw)],
+			grid[idx_1d(x  , y  , z+1, xw, yw, zw)]);
+}
+
+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_torus3d_node(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_torus3d_test_bin_len,
+				build_tests_simple_torus3d_test_bin);
+
+		uint64_t rcv = torus3d_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);
+	torus3d_connect_grid(grid, uart, 0, 0, 0, x, y, z);
+
+	struct component *dmem = create_simple_mem(4096);
+	clock_domain_add(clk, dmem);
+	torus3d_connect_grid(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;
+
+		torus3d_connect_grid(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, 1, 10, 10);
+	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_torus3d/source.mk b/tests/simple_torus3d/source.mk
new file mode 100644
index 0000000..e045a3c
--- /dev/null
+++ b/tests/simple_torus3d/source.mk
@@ -0,0 +1,18 @@
+TORUS3D_TEST_OBJ	!= ./scripts/gen-deps --sources "tests/simple_torus3d/sim.c"
+TEST_PROGS		+= build/tests/simple_torus3d/sim
+
+build/tests/simple_torus3d/test.inc: tests/simple_torus3d/test.c
+	riscv64-unknown-elf-gcc -O2 -Wall -Wextra -ffreestanding -nostdlib \
+		-march=rv64i -mabi=lp64 \
+		-o build/tests/simple_torus3d/test \
+		tests/simple_torus3d/test.c
+	riscv64-unknown-elf-objcopy -Obinary \
+		build/tests/simple_torus3d/test \
+		build/tests/simple_torus3d/test.bin
+	xxd -i build/tests/simple_torus3d/test.bin \
+		> build/tests/simple_torus3d/test.inc
+
+build/tests/simple_torus3d/sim.o: build/tests/simple_torus3d/test.inc
+
+build/tests/simple_torus3d/sim: $(TORUS3D_TEST_OBJ) $(OBJS)
+	$(COMPILE) $(TORUS3D_TEST_OBJ) $(OBJS) -o $@
diff --git a/tests/simple_torus3d/test.c b/tests/simple_torus3d/test.c
new file mode 100644
index 0000000..2953d41
--- /dev/null
+++ b/tests/simple_torus3d/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) {}
+}