enforce single unit per clock cycle, order to serve storage requests

4 files changed, 180 insertions, 130 deletions

diff --git a/inc/storage.h b/inc/storage.h
index a38f17d..95b6749 100644
--- a/inc/storage.h
+++ b/inc/storage.h
@@ -2,18 +2,35 @@
 #define STORAGE_H
 #include "definitions.h"
 #include "response.h"
+#include <algorithm>
 #include <array>
-#include <unordered_map>
+#include <deque>
 #include <vector>
 
 enum Accessor {
 	MEM,
 	FETCH,
 	L1CACHE,
-	IDLE,
 	SIDE,
 };
 
+/**
+ * Wrapper class for std::deque.
+ *
+ * Implements a deque that does not push duplicate objects.
+ */
+template <typename T> class Deque : public std::deque<T>
+{
+  public:
+	using std::deque<T>::deque;
+
+	void push_back(const T &value)
+	{
+		if (std::find(this->begin(), this->end(), value) == this->end())
+			std::deque<T>::push_back(value);
+	}
+};
+
 class Storage
 {
   public:
@@ -41,6 +58,10 @@ class Storage
 	 * is a word.
 	 */
 	std::vector<std::array<signed int, LINE_SIZE>> view(int base, int lines);
+	/**
+	 * Advances to the next job if the current job is completed.
+	 */
+	void resolve();
 
   protected:
 	/**
@@ -62,11 +83,11 @@ class Storage
 	 */
 	int delay;
 	/**
-	 * The accessor currently being serviced.
+	 * The accessors currently being serviced, in first come first serve order.
 	 */
-	enum Accessor servicing;
+	Deque<enum Accessor> deque;
 	/**
-	 * The number of cycles until the currently request is completed.
+	 * The number of cycles until the current request is completed.
 	 */
 	int wait_time;
 };
diff --git a/src/storage/dram.cc b/src/storage/dram.cc
index 4c4ca84..32f3fbb 100644
--- a/src/storage/dram.cc
+++ b/src/storage/dram.cc
@@ -2,14 +2,15 @@
 #include "definitions.h"
 #include "response.h"
 #include <algorithm>
+#include <iostream>
 
 Dram::Dram(int lines, int delay)
 {
 	this->data = new std::vector<std::array<signed int, LINE_SIZE>>;
 	this->data->resize(lines);
 	this->delay = delay;
+	this->wait_time = this->delay;
 	this->lower = nullptr;
-	this->servicing = IDLE;
 }
 
 Dram::~Dram() { delete this->data; }
@@ -23,17 +24,12 @@ Response Dram::write(Accessor accessor, signed int data, int address)
 		r = OK;
 	} else {
 		/* Do this first--then process the first cycle immediately. */
-		if (this->servicing == IDLE) {
-			this->servicing = accessor;
-			this->wait_time = delay;
-		}
+		this->deque.push_back(accessor);
 
-		if (this->servicing == accessor) {
+		if (this->deque.front() == accessor) {
 			if (this->wait_time == 0) {
 				this->do_write(data, address);
 				r = OK;
-			} else {
-				--this->wait_time;
 			}
 		}
 	}
diff --git a/src/storage/storage.cc b/src/storage/storage.cc
index 024699b..429ac2b 100644
--- a/src/storage/storage.cc
+++ b/src/storage/storage.cc
@@ -18,6 +18,15 @@ void Storage::do_write(signed data, int address)
 	int line = address / LINE_SIZE;
 	int word = address % LINE_SIZE;
 
-	this->servicing = IDLE;
 	this->data->at(line).at(word) = data;
 }
+
+void Storage::resolve()
+{
+	if (this->wait_time == 0) {
+		this->deque.pop_front();
+		this->wait_time = delay;
+	} else {
+		--this->wait_time;
+	}
+}
diff --git a/tests/dram.cc b/tests/dram.cc
index ba81508..e0189c7 100644
--- a/tests/dram.cc
+++ b/tests/dram.cc
@@ -23,7 +23,7 @@ TEST_CASE(
 	signed int w = 0x11223344;
 
 	Response r = d->write(MEM, w, 0x00000000);
-	REQUIRE(r == OK);
+	CHECK(r == OK);
 
 	expected.at(0) = w;
 	actual = d->view(0, 1)[0];
@@ -35,34 +35,28 @@ TEST_CASE(
 TEST_CASE(
 	"Construct singleton dram, store 0th element in three cycles", "[dram]")
 {
-	Dram *d = new Dram(1, 3);
+	int delay = 3;
+	Dram *d = new Dram(1, delay);
 	std::array<signed int, LINE_SIZE> expected = {0, 0, 0, 0};
 	std::array<signed int, LINE_SIZE> actual = d->view(0, 1)[0];
 	CHECK(expected == actual);
 
 	signed int w = 0x11223344;
 
-	// MEMORY CYCLE 1
-	Response r = d->write(MEM, w, 0x00000000);
-	actual = d->view(0, 1)[0];
-	REQUIRE(expected == actual);
-	REQUIRE(r == WAIT);
+	int i;
+	Response r;
+	for (i = 0; i < delay; ++i) {
+		r = d->write(MEM, w, 0x00000000);
+		CHECK(r == WAIT);
 
-	// MEMORY CYCLE 2
-	r = d->write(MEM, w, 0x00000000);
-	actual = d->view(0, 1)[0];
-	REQUIRE(expected == actual);
-	REQUIRE(r == WAIT);
+		actual = d->view(0, 1)[0];
+		REQUIRE(expected == actual);
+		d->resolve();
+	}
 
-	// MEMORY CYCLE 3
 	r = d->write(MEM, w, 0x00000000);
-	actual = d->view(0, 1)[0];
-	REQUIRE(expected == actual);
-	REQUIRE(r == WAIT);
-
-	// MEMORY CYCLE 4
-	r = d->write(MEM, w, 0x00000000);
-	REQUIRE(r == OK);
+	CHECK(r == OK);
+	d->resolve();
 
 	expected.at(0) = w;
 	actual = d->view(0, 1)[0];
@@ -76,66 +70,58 @@ TEST_CASE(
 	"conflict",
 	"[dram]")
 {
-	Dram *d = new Dram(1, 3);
+	int delay = 3;
+	Dram *d = new Dram(1, delay);
 	std::array<signed int, LINE_SIZE> expected = {0, 0, 0, 0};
 	std::array<signed int, LINE_SIZE> actual = d->view(0, 1)[0];
 	CHECK(expected == actual);
 
-	signed int w1 = 0x11223344;
-	signed int w2 = 0x55667788;
+	signed int w = 0x11223344;
 
-	// MEMORY CYCLE 1
-	Response r = d->write(MEM, w1, 0x00000000);
-	actual = d->view(0, 1)[0];
-	REQUIRE(expected == actual);
-	REQUIRE(r == WAIT);
+	int i;
+	Response r;
+	for (i = 0; i < delay; ++i) {
+		r = d->write(MEM, w, 0x00000000);
+		CHECK(r == WAIT);
 
-	// MEMORY CYCLE 2
-	actual = d->view(0, 1)[0];
-	r = d->write(MEM, w1, 0x00000000);
-	actual = d->view(0, 1)[0];
-	REQUIRE(expected == actual);
-	REQUIRE(r == WAIT);
+		actual = d->view(0, 1)[0];
+		CHECK(r == WAIT);
 
-	// MEMORY CYCLE 3
-	r = d->write(MEM, w1, 0x00000000);
-	actual = d->view(0, 1)[0];
-	REQUIRE(expected == actual);
-	REQUIRE(r == WAIT);
+		REQUIRE(expected == actual);
+		d->resolve();
+	}
 
-	// MEMORY CYCLE 4
-	r = d->write(MEM, w1, 0x00000000);
+	r = d->write(MEM, w, 0x00000000);
 	REQUIRE(r == OK);
-	// NOTE: servicing on the same clock cycle should probably not be allowed
-	// FETCH CYCLE 1
-	r = d->write(FETCH, w2, 0x00000001);
-	actual = d->view(0, 1)[0];
-	REQUIRE(r == WAIT);
+	// clock cycle did NOT resolve yet!
+	// this fetch should not make progress
+	r = d->write(FETCH, w, 0x00000001);
+	CHECK(r == WAIT);
 
-	expected.at(0) = w1;
 	actual = d->view(0, 1)[0];
-	CHECK(expected == actual);
+	CHECK(r == WAIT);
+	d->resolve();
 
-	// FETCH CYCLE 2
-	r = d->write(FETCH, w2, 0x00000001);
+	expected.at(0) = w;
 	actual = d->view(0, 1)[0];
 	REQUIRE(expected == actual);
-	REQUIRE(r == WAIT);
 
-	// FETCH CYCLE 3
-	r = d->write(FETCH, w2, 0x00000001);
-	actual = d->view(0, 1)[0];
-	REQUIRE(expected == actual);
-	REQUIRE(r == WAIT);
+	for (i = 0; i < delay; ++i) {
+		r = d->write(FETCH, w, 0x00000001);
+		CHECK(r == WAIT);
 
-	// FETCH CYCLE 4
-	r = d->write(FETCH, w2, 0x00000001);
+		actual = d->view(0, 1)[0];
+		REQUIRE(expected == actual);
+		d->resolve();
+	}
+
+	r = d->write(FETCH, w, 0x00000001);
 	actual = d->view(0, 1)[0];
-	REQUIRE(r == OK);
+	CHECK(r == OK);
 
-	expected.at(1) = w2;
+	expected.at(1) = w;
 	actual = d->view(0, 1)[0];
-	CHECK(expected == actual);
+	REQUIRE(expected == actual);
 
 	delete d;
 }
@@ -145,103 +131,141 @@ TEST_CASE(
 	"conflict",
 	"[dram]")
 {
-	Dram *d = new Dram(1, 3);
+	int delay = 2;
+	Dram *d = new Dram(1, 2);
 	std::array<signed int, LINE_SIZE> expected = {0, 0, 0, 0};
 	std::array<signed int, LINE_SIZE> actual = d->view(0, 1)[0];
 	CHECK(expected == actual);
 
-	signed int w1 = 0x11223344;
-	signed int w2 = 0x55667788;
+	signed int w = 0x11223344;
 
-	// MEMORY CYCLE 1
-	Response r = d->write(MEM, w1, 0x00000000);
-	actual = d->view(0, 1)[0];
-	REQUIRE(expected == actual);
-	REQUIRE(r == WAIT);
+	int i;
+	Response r;
+	for (i = 0; i < delay; ++i) {
+		r = d->write(MEM, w, 0x00000000);
+		CHECK(r == WAIT);
+
+		r = d->write(FETCH, w, 0x00000001);
+		CHECK(r == WAIT);
+
+		actual = d->view(0, 1)[0];
+		REQUIRE(expected == actual);
+		d->resolve();
+	}
+
+	r = d->write(MEM, w, 0x00000000);
+	CHECK(r == OK);
+	r = d->write(FETCH, w, 0x00000001);
+	CHECK(r == WAIT);
+	d->resolve();
 
-	// MEMORY CYCLE 2
-	actual = d->view(0, 1)[0];
-	r = d->write(MEM, w1, 0x00000000);
 	actual = d->view(0, 1)[0];
+	expected.at(0) = w;
 	REQUIRE(expected == actual);
-	REQUIRE(r == WAIT);
-	// FETCH CYCLE 1
-	r = d->write(FETCH, w2, 0x00000001);
+
+	for (i = 0; i < delay; ++i) {
+		r = d->write(FETCH, w, 0x00000001);
+		CHECK(r == WAIT);
+
+		r = d->write(MEM, w, 0x00000003);
+		CHECK(r == WAIT);
+
+		actual = d->view(0, 1)[0];
+		REQUIRE(expected == actual);
+		d->resolve();
+	}
+
+	r = d->write(FETCH, w, 0x00000001);
 	actual = d->view(0, 1)[0];
-	REQUIRE(r == WAIT);
+	CHECK(r == OK);
+	r = d->write(MEM, w, 0x00000003);
+	CHECK(r == WAIT);
 
-	r = d->write(MEM, w1, 0x00000000);
+	expected.at(1) = w;
 	actual = d->view(0, 1)[0];
 	REQUIRE(expected == actual);
-	REQUIRE(r == WAIT);
-	// FETCH CYCLE 1
-	r = d->write(FETCH, w2, 0x00000001);
-	actual = d->view(0, 1)[0];
-	REQUIRE(r == WAIT);
 
-	r = d->write(MEM, w1, 0x00000000);
-	REQUIRE(r == OK);
-	// NOTE: servicing on the same clock cycle should probably not be allowed
-	// FETCH CYCLE 1
-	r = d->write(FETCH, w2, 0x00000001);
-	actual = d->view(0, 1)[0];
-	REQUIRE(r == WAIT);
+	delete d;
+}
 
-	expected.at(0) = w1;
-	actual = d->view(0, 1)[0];
+TEST_CASE("Many conflicting requests first-come first serve", "[dram]")
+{
+	int delay = 1;
+	Dram *d = new Dram(1, delay);
+	std::array<signed int, LINE_SIZE> expected = {0, 0, 0, 0};
+	std::array<signed int, LINE_SIZE> actual = d->view(0, 1)[0];
 	CHECK(expected == actual);
 
-	r = d->write(FETCH, w2, 0x00000001);
+	signed int w = 0x11223344;
+
+	Response r;
+	r = d->write(FETCH, w, 0x00000000);
+	r = d->write(MEM, w, 0x00000001);
+
 	actual = d->view(0, 1)[0];
 	REQUIRE(expected == actual);
-	REQUIRE(r == WAIT);
+	d->resolve();
 
-	r = d->write(FETCH, w2, 0x00000001);
+	r = d->write(FETCH, w, 0x00000000);
+	r = d->write(L1CACHE, w, 0x00000002);
+	// call mem after cache
+	r = d->write(MEM, w, 0x00000001);
+
+	expected.at(0) = w;
 	actual = d->view(0, 1)[0];
 	REQUIRE(expected == actual);
-	REQUIRE(r == WAIT);
+	d->resolve();
+
+	r = d->write(MEM, w, 0x00000001);
+	r = d->write(L1CACHE, w, 0x00000002);
 
-	r = d->write(FETCH, w2, 0x00000001);
 	actual = d->view(0, 1)[0];
-	REQUIRE(r == OK);
+	REQUIRE(expected == actual);
+	d->resolve();
 
-	expected.at(1) = w2;
+	r = d->write(MEM, w, 0x00000001);
+	r = d->write(L1CACHE, w, 0x00000002);
+
+	expected.at(1) = w;
 	actual = d->view(0, 1)[0];
-	CHECK(expected == actual);
+	REQUIRE(expected == actual);
 
 	delete d;
 }
 
 TEST_CASE("Sidedoor bypasses delay", "[dram]")
 {
-	Dram *d = new Dram(1, 3);
+	int delay = 3;
+	Dram *d = new Dram(1, delay);
 	std::array<signed int, LINE_SIZE> expected = {0, 0, 0, 0};
 	std::array<signed int, LINE_SIZE> actual = d->view(0, 1)[0];
 	CHECK(expected == actual);
 
-	signed int w1 = 0x11223344;
-	signed int w2 = 0x55667788;
+	signed int w = 0x11223344;
+
+	int i;
+	Response r;
+	for (i = 0; i < delay - 1; ++i) {
+		r = d->write(MEM, w, 0x00000000);
+		CHECK(r == WAIT);
 
-	// MEMORY CYCLE 1
-	Response r = d->write(MEM, w1, 0x00000000);
-	actual = d->view(0, 1)[0];
-	REQUIRE(expected == actual);
-	REQUIRE(r == WAIT);
+		actual = d->view(0, 1)[0];
+		REQUIRE(expected == actual);
+		d->resolve();
+	}
 
-	// MEMORY CYCLE 2
-	actual = d->view(0, 1)[0];
-	r = d->write(MEM, w1, 0x00000000);
+	r = d->write(MEM, w, 0x00000000);
+	CHECK(r == WAIT);
 	actual = d->view(0, 1)[0];
 	REQUIRE(expected == actual);
-	REQUIRE(r == WAIT);
-	// SIDE CYCLE 1
-	r = d->write(SIDE, w2, 0x00000001);
+
+	r = d->write(SIDE, w, 0x00000001);
 	actual = d->view(0, 1)[0];
-	REQUIRE(r == OK);
+	CHECK(r == OK);
 
-	expected.at(1) = w2;
+	expected.at(1) = w;
 	actual = d->view(0, 1)[0];
-	CHECK(expected == actual);
+	REQUIRE(expected == actual);
 
 	delete d;
 }