technically speaking deadlock free, but starves

21 files changed, 196 insertions, 313 deletions

diff --git a/src/components/bus/simple_bus.c b/src/bus/simple_bus.c
index 1932419..1932419 100644
--- a/src/components/bus/simple_bus.c
+++ b/src/bus/simple_bus.c
diff --git a/src/bus/source.mk b/src/bus/source.mk
new file mode 100644
index 0000000..e812785
--- /dev/null
+++ b/src/bus/source.mk
@@ -0,0 +1 @@
+SOURCES += src/bus/simple_bus.c
diff --git a/src/components/bus/source.mk b/src/components/bus/source.mk
deleted file mode 100644
index 98a10b6..0000000
--- a/src/components/bus/source.mk
+++ /dev/null
@@ -1 +0,0 @@
-SOURCES += src/components/bus/simple_bus.c
diff --git a/src/components/cpu/riscv/source.mk b/src/components/cpu/riscv/source.mk
deleted file mode 100644
index da1cef6..0000000
--- a/src/components/cpu/riscv/source.mk
+++ /dev/null
@@ -1 +0,0 @@
-SOURCES += src/components/cpu/riscv/simple_riscv64.c
diff --git a/src/components/cpu/source.mk b/src/components/cpu/source.mk
deleted file mode 100644
index ef808f6..0000000
--- a/src/components/cpu/source.mk
+++ /dev/null
@@ -1 +0,0 @@
-include src/components/cpu/*/source.mk
diff --git a/src/components/grid/node.c b/src/components/grid/node.c
deleted file mode 100644
index 57ef7ed..0000000
--- a/src/components/grid/node.c
+++ /dev/null
@@ -1,133 +0,0 @@
-/* very simple grid node with 32bit private region, does not currently signal
- * being busy or anything. I think I might have to refine the message passing
- * interface I have, but this is good enough.
- *
- * Each node should have a router beneath it, just to simplify my life. A router
- * is basically a bus with a fallback ascension path.
- */
-#include <stdbool.h>
-
-#include <gran/grid/node.h>
-
-struct grid_node {
-	struct component component;
-	uint8_t u, v, x, y;
-	struct component *left, *right, *up, *down, *ascend, *lower;
-
-	struct component *send;
-	struct packet pkt;
-	bool busy;
-};
-
-static stat grid_clock(struct grid_node *grid)
-{
-	if (!grid->busy)
-		return OK;
-
-	stat r = SEND(grid, grid->send, grid->pkt);
-	if (r == EBUSY)
-		return OK;
-
-	grid->busy = false;
-	return r;
-}
-
-static stat grid_receive(struct grid_node *grid, struct component *from, struct packet pkt)
-{
-	if (grid->busy)
-		return EBUSY;
-
-	uint8_t u;
-	uint8_t v;
-	uint8_t x;
-	uint8_t y;
-	uint64_t addr = pkt.to;
-	addr_grid(addr, NULL, &x, &y, &u, &v);
-
-	grid->busy = true;
-	grid->pkt = pkt;
-
-	if (grid->u == u && grid->v == v && grid->x == x && grid->y == y) {
-		if (!grid->lower)
-			goto nosuch;
-
-		grid->send = grid->lower;
-		return OK;
-	}
-
-	if (grid->u != u || grid->v != v) {
-		if (!grid->ascend)
-			goto nosuch;
-
-		grid->send = grid->ascend;
-		return OK;
-	}
-
-	if (y < grid->y) {
-		if (!grid->down)
-			goto nosuch;
-
-		grid->send = grid->down;
-		return OK;
-	}
-
-	if (y > grid->y) {
-		if (!grid->up)
-			goto nosuch;
-
-		grid->send = grid->up;
-		return OK;
-	}
-
-	if (x < grid->x) {
-		if (!grid->left)
-			goto nosuch;
-
-		grid->send = grid->left;
-		return OK;
-	}
-
-	if (x > grid->x) {
-		if (!grid->right)
-			return EBUS;
-
-		grid->send = grid->right;
-		return OK;
-	}
-
-nosuch:
-	grid->send = from;
-	grid->pkt = response(pkt);
-	set_flags(&grid->pkt, PACKET_ERROR);
-	return OK;
-}
-
-struct component *create_grid_node(uint8_t u, uint8_t v, uint8_t x, uint8_t y)
-{
-	struct grid_node *node = calloc(1, sizeof(struct grid_node));
-	if (!node)
-		return NULL;
-
-	node->component.receive = (receive_callback)grid_receive;
-	node->component.clock = (clock_callback)grid_clock;
-	node->u = u;
-	node->v = v;
-	node->x = x;
-	node->y = y;
-	return (struct component *)node;
-}
-
-stat grid_node_connect(struct component *node,
-		struct component *left, struct component *right,
-		struct component *up, struct component *down,
-		struct component *lower, struct component *ascend)
-{
-	struct grid_node *n = (struct grid_node *)node;
-	n->left = left;
-	n->right = right;
-	n->up = up;
-	n->down = down;
-	n->lower = lower;
-	n->ascend = ascend;
-	return OK;
-}
diff --git a/src/components/grid/router.c b/src/components/grid/router.c
deleted file mode 100644
index 63c4011..0000000
--- a/src/components/grid/router.c
+++ /dev/null
@@ -1,136 +0,0 @@
-#include <stdbool.h>
-
-#include <gran/grid/node.h>
-#include <gran/grid/router.h>
-#include <gran/vec.h>
-
-struct router_region {
-	uint32_t addr;
-	uint32_t size;
-	struct component *component;
-};
-
-struct node_router {
-	struct component component;
-	struct component *ascend;
-	struct vec regions;
-	uint8_t u, v, x, y;
-
-	struct component *send;
-	struct packet pkt;
-	bool busy;
-};
-
-static struct router_region *find_region(struct node_router *router, uint32_t addr)
-{
-	for (size_t i = 0; i < vec_len(&router->regions); ++i) {
-		struct router_region *region = vec_at(&router->regions, i);
-
-		if (addr >= region->addr && addr < region->addr + region->size)
-			return region;
-	}
-
-	return NULL;
-}
-
-static stat router_clock(struct node_router *router)
-{
-	if (!router->busy)
-		return OK;
-
-	stat r = SEND(router, router->send, router->pkt);
-	if (r == EBUSY)
-		return OK;
-
-	router->busy = false;
-	return OK;
-}
-
-static stat router_receive(struct node_router *router, struct component *from, struct packet pkt)
-{
-	if (router->busy)
-		return EBUSY;
-
-	router->busy = true;
-
-	uint64_t addr = pkt.to;
-	uint8_t u;
-	uint8_t v;
-	uint8_t x;
-	uint8_t y;
-	addr_grid(addr, NULL, &x, &y, &u, &v);
-
-	router->pkt = pkt;
-
-	if (router->u != u || router->v != v || router->x != x || router->y != y) {
-		if (!router->ascend)
-			goto nosuch;
-
-		router->send = router->ascend;
-		return OK;
-	}
-
-	struct router_region *region = find_region(router, addr);
-	if (!region)
-		goto nosuch;
-
-	router->send = region->component;
-	return OK;
-
-nosuch:
-	router->send = from;
-	router->pkt = response(pkt);
-	set_flags(&router->pkt, PACKET_ERROR);
-	return OK;
-}
-
-struct component *create_node_router(uint8_t u, uint8_t v, uint8_t x, uint8_t y)
-{
-	struct node_router *router = calloc(1, sizeof(struct node_router));
-	if (!router)
-		return NULL;
-
-	router->u = u;
-	router->v = v;
-	router->x = x;
-	router->y = y;
-
-	router->component.receive = (receive_callback)router_receive;
-	router->component.clock = (clock_callback)router_clock;
-	router->regions = vec_create(sizeof(struct router_region));
-
-	return (struct component *)router;
-}
-
-stat node_router_add(struct component *router, struct component *component, uint32_t addr, uint32_t size)
-{
-	struct node_router *nr = (struct node_router *)router;
-	struct router_region *found = find_region(nr, addr);
-	if (!found)           found = find_region(nr, addr + size);
-
-	if (found) {
-		error("%s overlaps with %s at %x",
-				found->component->name,
-				component->name,
-				found->addr
-		     );
-
-		return EEXISTS;
-	}
-
-	struct router_region r = (struct router_region){
-		.addr = addr,
-		.size = size,
-		.component = component
-	};
-	vect_append(struct node_region, nr->regions, &r);
-
-	return OK;
-}
-
-stat node_router_ascend(struct component *router, struct component *node)
-{
-	struct node_router *nr = (struct node_router *)router;
-	nr->ascend = node;
-	return OK;
-}
diff --git a/src/components/grid/source.mk b/src/components/grid/source.mk
deleted file mode 100644
index 4fb44ec..0000000
--- a/src/components/grid/source.mk
+++ /dev/null
@@ -1 +0,0 @@
-SOURCES += src/components/grid/node.c src/components/grid/router.c
diff --git a/src/components/mem/source.mk b/src/components/mem/source.mk
deleted file mode 100644
index 9c339ba..0000000
--- a/src/components/mem/source.mk
+++ /dev/null
@@ -1 +0,0 @@
-SOURCES += src/components/mem/simple_mem.c
diff --git a/src/components/source.mk b/src/components/source.mk
deleted file mode 100644
index c45f391..0000000
--- a/src/components/source.mk
+++ /dev/null
@@ -1 +0,0 @@
-include src/components/*/source.mk
diff --git a/src/components/uart/source.mk b/src/components/uart/source.mk
deleted file mode 100644
index af26289..0000000
--- a/src/components/uart/source.mk
+++ /dev/null
@@ -1 +0,0 @@
-SOURCES += src/components/uart/simple_uart.c
diff --git a/src/components/cpu/riscv/simple_riscv64.c b/src/cpu/riscv/simple_riscv64.c
index 987838e..1c4e810 100644
--- a/src/components/cpu/riscv/simple_riscv64.c
+++ b/src/cpu/riscv/simple_riscv64.c
@@ -149,7 +149,7 @@ static void set_reg(struct simple_riscv64 *cpu, size_t i, uint64_t v)
 
 #define EXTEND_IMM12(x) ((int32_t)((x) << 20) >> 20)
 #define EXTEND_IMM20(x) ((int32_t)((x) << 12) >> 12)
-#define SHAMT(x) ((x) & 0b11111)
+#define SHAMT(x) ((x) & 0b111111)
 
 static stat op_imm(struct simple_riscv64 *cpu, union rv_insn insn)
 {
@@ -545,6 +545,8 @@ static stat simple_riscv64_receive(struct simple_riscv64 *cpu, struct component
 
 static stat simple_riscv64_clock(struct simple_riscv64 *cpu)
 {
+	stat ret = OK;
+
 	/* there's an active data transfer we should handle */
 	if (cpu->dls.state != LDST_IDLE) {
 		assert(!is_set(&cpu->dls.pkt, PACKET_ERROR));
@@ -569,15 +571,15 @@ static stat simple_riscv64_clock(struct simple_riscv64 *cpu)
 			return OK;
 	}
 
-	if (cpu->ils.state == LDST_BLOCKED) {
-		stat ret = SEND(cpu, cpu->imem, cpu->ils.pkt);
-		if (ret == EBUSY)
-			return OK;
+	if (cpu->ils.state == LDST_BLOCKED)
+		goto send;
 
+	if (cpu->ils.state == LDST_SENT)
 		return OK;
-	}
 
-	uint32_t insn = 0;
+	/* this effectively encodes a NOP */
+	uint32_t insn = OP_IMM;
+
 	if (cpu->ils.state == LDST_DONE) {
 		assert(!is_set(&cpu->dls.pkt, PACKET_ERROR));
 
@@ -585,24 +587,9 @@ static stat simple_riscv64_clock(struct simple_riscv64 *cpu)
 		cpu->ils.state = LDST_IDLE;
 	}
 
-	if (cpu->ils.state == LDST_IDLE) {
-		cpu->ils.pkt = create_packet(cpu->rcv + 64,
-						cpu->pc,
-						sizeof(uint32_t),
-						NULL,
-						PACKET_READ);
-		cpu->ils.state = LDST_SENT;
-		stat ret = SEND(cpu, cpu->imem, cpu->ils.pkt);
-		if (ret == EBUSY) {
-			cpu->ils.state = LDST_BLOCKED;
-			return ret;
-		}
-	}
-
 	// for now assume little endian emulated and host cpu
 	union rv_insn i = {.val = insn};
 
-	stat ret = OK;
 	// all formats have identical opcodes, use whatever
 	switch (i.rtype.op) {
 	case OP_IMM: ret = op_imm(cpu, i); break;
@@ -625,17 +612,30 @@ static stat simple_riscv64_clock(struct simple_riscv64 *cpu)
 		return ENOSUCH;
 	}
 
-	return ret;
-}
+	if (cpu->ils.state == LDST_IDLE) {
+		cpu->ils.pkt = create_packet(cpu->rcv + 64,
+						cpu->pc,
+						sizeof(uint32_t),
+						NULL,
+						PACKET_READ);
+		cpu->ils.state = LDST_BLOCKED;
+	}
 
-static void simple_riscv64_destroy(struct simple_riscv64 *cpu)
-{
-	destroy(cpu->imem);
-	destroy(cpu->dmem);
-	free(cpu);
+send:
+	if (cpu->ils.state == LDST_BLOCKED) {
+		stat ret = SEND(cpu, cpu->imem, cpu->ils.pkt);
+		if (ret == EBUSY) {
+			cpu->ils.state = LDST_BLOCKED;
+			return ret;
+		}
+
+		cpu->ils.state = LDST_SENT;
+	}
+
+	return ret;
 }
 
-struct component *create_simple_riscv64(uint64_t rcv, uint32_t start_pc,
+struct component *create_simple_riscv64(uint64_t rcv, uint64_t start_pc,
                                         struct component *imem,
                                         struct component *dmem)
 {
@@ -645,12 +645,20 @@ struct component *create_simple_riscv64(uint64_t rcv, uint32_t start_pc,
 
 	new->component.receive = (receive_callback)simple_riscv64_receive;
 	new->component.clock = (clock_callback)simple_riscv64_clock;
-	new->component.destroy = (destroy_callback)simple_riscv64_destroy;
 
 	new->pc = start_pc;
 	new->rcv = rcv;
 	new->imem = imem;
 	new->dmem = dmem;
+
+	/* fetch new instruction at start */
+	new->ils.state = LDST_BLOCKED;
+	new->ils.pkt = create_packet(new->rcv + 64,
+					new->pc,
+					sizeof(uint32_t),
+					NULL,
+					PACKET_READ);
+
 	return (struct component *)new;
 }
 
diff --git a/src/cpu/riscv/source.mk b/src/cpu/riscv/source.mk
new file mode 100644
index 0000000..aa11801
--- /dev/null
+++ b/src/cpu/riscv/source.mk
@@ -0,0 +1 @@
+SOURCES += src/cpu/riscv/simple_riscv64.c
diff --git a/src/cpu/source.mk b/src/cpu/source.mk
new file mode 100644
index 0000000..47dcc3e
--- /dev/null
+++ b/src/cpu/source.mk
@@ -0,0 +1 @@
+include src/cpu/*/source.mk
diff --git a/src/grid/node.c b/src/grid/node.c
new file mode 100644
index 0000000..16cce1b
--- /dev/null
+++ b/src/grid/node.c
@@ -0,0 +1,145 @@
+/* very simple grid node with 32bit private region, does not currently signal
+ * being busy or anything. I think I might have to refine the message passing
+ * interface I have, but this is good enough.
+ *
+ * Each node should have a router beneath it, just to simplify my life. A router
+ * is basically a bus with a fallback ascension path.
+ */
+#include <stdbool.h>
+
+#include <gran/grid/node.h>
+
+struct port {
+	struct component *send;
+	struct packet pkt;
+	bool busy;
+};
+
+struct grid_node {
+	struct component component;
+	uint16_t x, y;
+
+	struct port left, right, up, down, lower;
+};
+
+static void port_clock(struct grid_node *grid, struct port *port)
+{
+	if (!port->busy)
+		return;
+
+	stat r = SEND(grid, port->send, port->pkt);
+	if (r == EBUSY)
+		return;
+
+	port->busy = false;
+}
+
+static stat grid_clock(struct grid_node *grid)
+{
+	port_clock(grid, &grid->left);
+	port_clock(grid, &grid->right);
+	port_clock(grid, &grid->up);
+	port_clock(grid, &grid->down);
+	port_clock(grid, &grid->lower);
+	return OK;
+}
+
+static stat port_receive(struct port *port, struct packet pkt)
+{
+	if (port->busy)
+		return EBUSY;
+
+	port->pkt = pkt;
+	port->busy = true;
+	return OK;
+}
+
+static stat grid_receive(struct grid_node *grid, struct component *from, struct packet pkt)
+{
+	uint16_t x;
+	uint16_t y;
+	uint64_t addr = pkt.to;
+	addr_grid(addr, NULL, &x, &y);
+
+	if (grid->x == x && grid->y == y) {
+		if (!grid->lower.send)
+			goto nosuch;
+
+		return port_receive(&grid->lower, pkt);
+	}
+
+	if (y < grid->y) {
+		if (!grid->down.send)
+			goto nosuch;
+
+		return port_receive(&grid->down, pkt);
+	}
+
+	if (y > grid->y) {
+		if (!grid->up.send)
+			goto nosuch;
+
+		return port_receive(&grid->up, pkt);
+	}
+
+	if (x < grid->x) {
+		if (!grid->left.send)
+			goto nosuch;
+
+		return port_receive(&grid->left, pkt);
+	}
+
+	if (x > grid->x) {
+		if (!grid->right.send)
+			goto nosuch;
+
+		return port_receive(&grid->right, pkt);
+	}
+
+nosuch:
+	set_flags(&pkt, PACKET_ERROR);
+	if (from == grid->lower.send)
+		return port_receive(&grid->lower, pkt);
+
+	if (from == grid->left.send)
+		return port_receive(&grid->left, pkt);
+
+	if (from == grid->right.send)
+		return port_receive(&grid->right, pkt);
+
+	if (from == grid->down.send)
+		return port_receive(&grid->down, pkt);
+
+	if (from == grid->up.send)
+		return port_receive(&grid->up, pkt);
+
+	abort();
+	return OK;
+}
+
+struct component *create_grid_node(uint16_t x, uint16_t y)
+{
+	struct grid_node *node = calloc(1, sizeof(struct grid_node));
+	if (!node)
+		return NULL;
+
+	node->component.receive = (receive_callback)grid_receive;
+	node->component.clock = (clock_callback)grid_clock;
+	node->x = x;
+	node->y = y;
+	return (struct component *)node;
+}
+
+stat grid_node_connect(struct component *node,
+		struct component *left, struct component *right,
+		struct component *up, struct component *down,
+		struct component *lower)
+{
+	struct grid_node *n = (struct grid_node *)node;
+	n->left.send = left;
+	n->right.send = right;
+	n->up.send = up;
+	n->down.send = down;
+	n->lower.send = lower;
+	return OK;
+}
diff --git a/src/grid/source.mk b/src/grid/source.mk
new file mode 100644
index 0000000..e23d7db
--- /dev/null
+++ b/src/grid/source.mk
@@ -0,0 +1 @@
+SOURCES += src/grid/node.c
diff --git a/src/components/mem/simple_mem.c b/src/mem/simple_mem.c
index e435ea5..0a3a3ce 100644
--- a/src/components/mem/simple_mem.c
+++ b/src/mem/simple_mem.c
@@ -19,7 +19,7 @@ struct simple_mem {
 
 static stat simple_mem_clock(struct simple_mem *mem)
 {
-	if (mem->busy)
+	if (!mem->busy)
 		return OK;
 
 	stat r = SEND(mem, mem->send, mem->pkt);
@@ -35,6 +35,7 @@ static stat simple_mem_receive(struct simple_mem *mem, struct component *from, s
 	if (mem->busy)
 		return EBUSY;
 
+	mem->busy = true;
 	mem->send = from;
 
 	uint64_t offset = pkt.to % mem->size;
diff --git a/src/mem/source.mk b/src/mem/source.mk
new file mode 100644
index 0000000..7d1a717
--- /dev/null
+++ b/src/mem/source.mk
@@ -0,0 +1 @@
+SOURCES += src/mem/simple_mem.c
diff --git a/src/source.mk b/src/source.mk
index db585ee..dd92722 100644
--- a/src/source.mk
+++ b/src/source.mk
@@ -1,6 +1,4 @@
-include src/components/source.mk
+include src/*/source.mk
 
-# everything except main
-SRC_LOCAL != echo src/*.c | sed 's|src/main.c||g'
-SOURCES += $(SRC_LOCAL)
-MAIN_SRC = src/main.c
+SOURCES += src/root.c src/clock_domain.c src/vec.c
+MAIN_SRC += src/main.c
diff --git a/src/components/uart/simple_uart.c b/src/uart/simple_uart.c
index 1528a70..e640ae1 100644
--- a/src/components/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/src/uart/source.mk b/src/uart/source.mk
new file mode 100644
index 0000000..cdc0bc9
--- /dev/null
+++ b/src/uart/source.mk
@@ -0,0 +1 @@
+SOURCES += src/uart/simple_uart.c