Merge pull request #19 from bdunahu/bdunahu

cache store, handle load requests to memory, write allocate policy
-- changes look good

10 files changed, 447 insertions, 42 deletions

diff --git a/inc/cache.h b/inc/cache.h
index d470e6c..e8b7030 100644
--- a/inc/cache.h
+++ b/inc/cache.h
@@ -1,6 +1,8 @@
 #ifndef CACHE_H
 #define CACHE_H
-#include <storage.h>
+#include "definitions.h"
+#include "storage.h"
+#include <array>
 
 class Cache : public Storage
 {
@@ -14,11 +16,30 @@ class Cache : public Storage
 	 * @param The number of clock cycles each access takes.
 	 * @return A new cache object.
 	 */
-	Cache(int lines, Storage *lower, int delay);
+	Cache(Storage *lower, int delay);
 	~Cache();
 
 	Response write(Accessor accessor, signed int data, int address) override;
-	Response read(Accessor accessor, int address, std::array<signed int, LINE_SIZE>& data) override;
+	Response read(
+		Accessor accessor,
+		int address,
+		std::array<signed int, LINE_SIZE> &data) override;
+
+  private:
+	/**
+	 * Fetches `address` from a lower level of storage if it is not already
+	 * present. If it is not, temporarily sets the is_blocked attribute of this
+	 * cache level to true, and the victim line is chosen/written back.
+	 * @param the address that must be present in cache.
+	 */
+	void fetch_resource(int address);
+	/**
+	 * An array of metadata about elements in `data`.
+	 * If the first value of an element is negative, the corresponding
+	 * element in `data` is invalid. If the most second value of an element
+	 * is nonzero, the corresponding element in `data` is dirty.
+	 */
+	std::array<std::array<int, 2>, L1_CACHE_SIZE> meta;
 };
 
 #endif /* CACHE_H_INCLUDED */
diff --git a/inc/definitions.h b/inc/definitions.h
index 4b01be9..877065e 100644
--- a/inc/definitions.h
+++ b/inc/definitions.h
@@ -2,25 +2,49 @@
 #define DEFINITIONS_H
 #include <cmath>
 
-/* The number of bits to specify a word in a line
+/**
+ * The number of bits to specify a word in a line
  */
 #define LINE_SPEC 2
+/**
+ * The total number of words in a line
+ */
 #define LINE_SIZE (int)pow(2, 2)
 
-/* The number of bits to specify a memory line
- * (/ (expt 2 15) 4)
+/**
+ * The number of bits to specify a memory line
+ * calculated as: (/ (expt 2 15) 4)
  */
 #define MEM_SPEC 13
+/**
+ * The total number of words in memory
+ */
 #define MEM_SIZE (int)pow(2, MEM_SPEC)
 
-/* The number of bits to specify a l1 cache line
+/**
+ * The number of bits to specify a l1 cache line
  */
 #define L1_CACHE_SPEC 5
+/**
+ * The total number of words in l1 cache
+ */
 #define L1_CACHE_SIZE (int)pow(2, L1_CACHE_SPEC)
 
-/* Parses some bits.
+/**
+ * Return the N least-significant bits from integer K using a bit mask
+ * @param the integer to be parsed
+ * @param the number of bits to be parsed
+ * @return the N least-significant bits from K
+ */
+#define GET_LS_BITS(k, n) ((k) & ((1 << (n)) - 1))
+/**
+ * Return the bits from integer K starting at N and ending at M using a bit
+ * mask
+ * @param the integer to be parsed
+ * @param the index of the starting bit to be parsed
+ * @param the index of the ending bit to be parsed
+ * @return a section of bits from K
  */
-#define LAST(k, n) ((k) & ((1 << (n)) - 1))
-#define MID(k, m, n) LAST((k) >> (m), ((n) - (m)))
+#define GET_MID_BITS(k, m, n) GET_LS_BITS((k) >> (m), ((n) - (m)))
 
 #endif /* DEFINITIONS_H_INCLUDED */
diff --git a/inc/dram.h b/inc/dram.h
index 1061d6b..20221b7 100644
--- a/inc/dram.h
+++ b/inc/dram.h
@@ -19,7 +19,15 @@ class Dram : public Storage
 	Response read(Accessor accessor, int address, std::array<signed int, LINE_SIZE>& data) override;
 
 	private:
+	/**
+	 * Helper for `write`.
+	 */
+	void do_write(signed int, int);
+	/**
+	 * Helper for `read`.
+	 */
 	void do_read(std::array<signed int, LINE_SIZE>& data_line, int address);
 };
 
 #endif /* DRAM_H_INCLUDED */
+
diff --git a/inc/storage.h b/inc/storage.h
index 1fb41b0..793b982 100644
--- a/inc/storage.h
+++ b/inc/storage.h
@@ -32,7 +32,10 @@ class Storage
 	 * @return a status code reflecting the state of the request, and the
 	 * data being returned.
 	 */
-	virtual Response read(Accessor accessor, int address, std::array<signed int, LINE_SIZE>& data) = 0;
+	virtual Response read(
+		Accessor accessor,
+		int address,
+		std::array<signed int, LINE_SIZE> &data) = 0;
 	/**
 	 * Sidedoor view of `lines` of memory starting at `base`.
 	 * @param The base line to start getting memory from.
@@ -48,10 +51,6 @@ class Storage
 
   protected:
 	/**
-	 * Helper for `write`.
-	 */
-	void do_write(signed int, int);
-	/**
 	 * The data currently stored in this level of storage.
 	 */
 	std::vector<std::array<signed int, LINE_SIZE>> *data;
@@ -73,6 +72,11 @@ class Storage
 	 * The number of cycles until the current request is completed.
 	 */
 	int wait_time;
+	/**
+	 * A flag indicating whether this level of storage is currently waiting for
+	 * a lower level.
+	 */
+	int is_waiting;
 };
 
 #endif /* STORAGE_H_INCLUDED */
diff --git a/src/storage/cache.cc b/src/storage/cache.cc
index 67cedda..2031367 100644
--- a/src/storage/cache.cc
+++ b/src/storage/cache.cc
@@ -1,22 +1,78 @@
 #include "cache.h"
 #include "definitions.h"
 #include "response.h"
+#include "utils.h"
 #include <bits/stdc++.h>
 
-Cache::Cache(int lines, Storage *lower, int delay)
+Cache::Cache(Storage *lower, int delay)
 {
 	this->data = new std::vector<std::array<signed int, LINE_SIZE>>;
-	this->data->resize(lines);
-	this->lower = lower;
+	this->data->resize(L1_CACHE_SIZE);
 	this->delay = delay;
-	this->lower = nullptr;
+	this->is_waiting = false;
+	this->lower = lower;
+	this->meta.fill({-1, -1});
+	this->requester = IDLE;
+	this->wait_time = this->delay;
 }
 
 Cache::~Cache() { delete this->data; }
 
 Response Cache::write(Accessor accessor, signed int data, int address)
 {
+	Response r = WAIT;
+
+	/* Do this first--then process the first cycle immediately. */
+	if (this->requester == IDLE)
+		this->requester = accessor;
+
+	if (this->requester == accessor) {
+		fetch_resource(address);
+		if (this->is_waiting)
+			r = BLOCKED;
+		else if (this->wait_time == 0) {
+			int tag, index, offset;
+			get_bit_fields(address, &tag, &index, &offset);
+			this->data->at(index).at(offset) = data;
+			this->meta[index].at(1) = 1;
+			r = OK;
+		}
+	}
+
+	return r;
+}
+
+Response Cache::read(
+	Accessor accessor, int address, std::array<signed int, LINE_SIZE> &data)
+{
 	return WAIT;
 }
 
-Response Cache::read(Accessor accessor, int address, std::array<signed int, LINE_SIZE>& data) { return WAIT; }
+void Cache::fetch_resource(int expected)
+{
+	Response r = OK;
+	int tag, index, offset;
+	std::array<signed int, LINE_SIZE> actual;
+	std::array<int, 2> *meta;
+
+	get_bit_fields(expected, &tag, &index, &offset);
+	meta = &this->meta.at(index);
+
+	if (meta->at(0) != tag) {
+		// address not in cache
+		if (meta->at(1) >= 0) {
+			// occupant is dirty
+			// TODO
+			r = WAIT;
+		} else {
+			actual = this->data->at(index);
+			r = this->lower->read(L1CACHE, expected, actual);
+			if (r == OK) {
+				meta->at(0) = tag;
+				meta->at(1) = -1;
+			}
+		}
+	}
+
+	this->is_waiting = (r == OK) ? false : true;
+}
diff --git a/src/storage/dram.cc b/src/storage/dram.cc
index 0db4c35..441f10b 100644
--- a/src/storage/dram.cc
+++ b/src/storage/dram.cc
@@ -8,13 +8,22 @@ 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->is_waiting = false;
 	this->lower = nullptr;
 	this->requester = IDLE;
+	this->wait_time = this->delay;
 }
 
 Dram::~Dram() { delete this->data; }
 
+void Dram::do_write(signed data, int address)
+{
+	int line = address / LINE_SIZE;
+	int word = address % LINE_SIZE;
+
+	this->data->at(line).at(word) = data;
+}
+
 Response Dram::write(Accessor accessor, signed int data, int address)
 {
 	Response r = WAIT;
@@ -38,20 +47,26 @@ Response Dram::write(Accessor accessor, signed int data, int address)
 	return r;
 }
 
-void Dram::do_read(std::array<signed int, LINE_SIZE>& data_line, int address){
+void Dram::do_read(std::array<signed int, LINE_SIZE> &data_line, int address)
+{
 	int line = address / LINE_SIZE;
 	data_line = this->data->at(line);
 }
 
-Response Dram::read(Accessor accessor, int address, std::array<signed int, LINE_SIZE>& data) { 
+Response Dram::read(
+	Accessor accessor, int address, std::array<signed int, LINE_SIZE> &data)
+{
 	Response r = WAIT;
+
 	if (this->requester == IDLE)
 		this->requester = accessor;
+
 	if (this->requester == accessor) {
 		if (this->wait_time == 0) {
 			this->do_read(data, address);
 			r = OK;
 		}
 	}
-	return r; 
- }
+
+	return r;
+}
diff --git a/src/storage/storage.cc b/src/storage/storage.cc
index e3067a2..61531d1 100644
--- a/src/storage/storage.cc
+++ b/src/storage/storage.cc
@@ -13,20 +13,12 @@ Storage::view(int base, int lines)
 	return ret;
 }
 
-void Storage::do_write(signed data, int address)
-{
-	int line = address / LINE_SIZE;
-	int word = address % LINE_SIZE;
-
-	this->data->at(line).at(word) = data;
-}
-
 void Storage::resolve()
 {
 	if (this->wait_time == 0) {
 		this->requester = IDLE;
 		this->wait_time = delay;
-	} else if (this->requester != IDLE) {
+	} else if (this->requester != IDLE && !this->is_waiting) {
 		--this->wait_time;
 	}
 }
diff --git a/src/utils/utils.cc b/src/utils/utils.cc
index b4bdb2f..dfeb2b3 100644
--- a/src/utils/utils.cc
+++ b/src/utils/utils.cc
@@ -1,11 +1,11 @@
-#include "definitions.h"
 #include "utils.h"
+#include "definitions.h"
 
 void get_bit_fields(int address, int *tag, int *index, int *offset)
 {
 	*tag =
-		MID(address, LINE_SPEC + L1_CACHE_SPEC,
+		GET_MID_BITS(address, LINE_SPEC + L1_CACHE_SPEC,
 			MEM_SPEC + LINE_SPEC + L1_CACHE_SPEC);
-	*index = MID(address, LINE_SPEC, L1_CACHE_SPEC + LINE_SPEC);
-	*offset = LAST(address, LINE_SPEC);
+	*index = GET_MID_BITS(address, LINE_SPEC, L1_CACHE_SPEC + LINE_SPEC);
+	*offset = GET_LS_BITS(address, LINE_SPEC);
 }
diff --git a/tests/cache.cc b/tests/cache.cc
index 3c1fba6..8d1e806 100644
--- a/tests/cache.cc
+++ b/tests/cache.cc
@@ -1,12 +1,299 @@
 #include "cache.h"
 #include "definitions.h"
+#include "dram.h"
 #include <catch2/catch_test_macros.hpp>
 
-TEST_CASE("Constructor singleton dram", "[cache]")
+TEST_CASE("Constructor singleton cache", "[cache]")
 {
-	Cache *c = new Cache(1, nullptr, LINE_SIZE);
+	Cache *c = new Cache(nullptr, 0);
 	std::array<signed int, LINE_SIZE> expected = {0, 0, 0, 0};
 	std::array<signed int, LINE_SIZE> actual = c->view(0, 1)[0];
 	REQUIRE(expected == actual);
 	delete c;
 }
+
+TEST_CASE("no delay stores instantly", "[cache]")
+{
+	int delay = 0;
+	Dram *d = new Dram(MEM_SIZE, delay);
+	Cache *c = new Cache(d, 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;
+
+	Response r;
+
+	r = c->write(MEM, w, 0b0);
+	CHECK(r == OK);
+	d->resolve();
+	c->resolve();
+
+	actual = d->view(0, 1)[0];
+	// we do NOT write back now!
+	REQUIRE(expected == actual);
+
+	expected.at(0) = w;
+	actual = c->view(0, 1)[0];
+	REQUIRE(expected == actual);
+
+	delete d;
+	delete c;
+}
+
+TEST_CASE("cache takes \"forever\"", "[cache]")
+{
+	int delay = 0;
+	Dram *d = new Dram(MEM_SIZE, delay);
+	Cache *c = new Cache(d, delay + 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 w = 0x11223344;
+
+	int i;
+	Response r;
+	for (i = 0; i < delay + 2; ++i) {
+		r = c->write(MEM, w, 0b0);
+		CHECK(r == WAIT); // WAIT
+
+		actual = c->view(0, 1)[0];
+		REQUIRE(expected == actual);
+		c->resolve();
+		d->resolve();
+	}
+
+	r = c->write(MEM, w, 0b0);
+	CHECK(r == OK);
+	d->resolve();
+
+	actual = d->view(0, 1)[0];
+	// we do NOT write back now!
+	REQUIRE(expected == actual);
+
+	expected.at(0) = w;
+	actual = c->view(0, 1)[0];
+	REQUIRE(expected == actual);
+
+	delete d;
+	delete c;
+}
+
+TEST_CASE("dram takes \"forever\"", "[cache]")
+{
+	int delay = 0;
+	Dram *d = new Dram(MEM_SIZE, delay + 2);
+	Cache *c = new Cache(d, 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;
+
+	int i;
+	Response r;
+	for (i = 0; i < delay + 2; ++i) {
+		r = c->write(MEM, w, 0b0);
+		CHECK(r == BLOCKED); // BLOCKED
+
+		actual = c->view(0, 1)[0];
+		REQUIRE(expected == actual);
+		c->resolve();
+		d->resolve();
+	}
+
+	r = c->write(MEM, w, 0b0);
+	CHECK(r == OK);
+	d->resolve();
+
+	actual = d->view(0, 1)[0];
+	// we do NOT write back now!
+	REQUIRE(expected == actual);
+
+	expected.at(0) = w;
+	actual = c->view(0, 1)[0];
+	REQUIRE(expected == actual);
+
+	delete d;
+	delete c;
+}
+
+TEST_CASE("dram and cache take \"forever\"", "[cache]")
+{
+	int delay = 2;
+	Dram *d = new Dram(MEM_SIZE, delay + 2);
+	Cache *c = new Cache(d, 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;
+
+	int i;
+	Response r;
+	for (i = 0; i < delay + 2; ++i) {
+		r = c->write(MEM, w, 0b0);
+		CHECK(r == BLOCKED); // BLOCKED
+
+		actual = c->view(0, 1)[0];
+		REQUIRE(expected == actual);
+		c->resolve();
+		d->resolve();
+	}
+
+	for (i = 0; i < delay; ++i) {
+		r = c->write(MEM, w, 0b0);
+		CHECK(r == WAIT); // WAIT
+
+		actual = c->view(0, 1)[0];
+		REQUIRE(expected == actual);
+		c->resolve();
+		d->resolve();
+	}
+
+	r = c->write(MEM, w, 0b0);
+	CHECK(r == OK);
+	c->resolve();
+	d->resolve();
+
+	actual = d->view(0, 1)[0];
+	// we do NOT write back now!
+	REQUIRE(expected == actual);
+
+	expected.at(0) = w;
+	actual = c->view(0, 1)[0];
+	REQUIRE(expected == actual);
+
+	delete d;
+	delete c;
+}
+
+TEST_CASE("dram takes \"forever\", two concurrent requests same index", "[cache]")
+{
+	int delay = 0;
+	Dram *d = new Dram(MEM_SIZE, delay + 2);
+	Cache *c = new Cache(d, 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;
+
+	int i;
+	Response r;
+	for (i = 0; i < delay + 2; ++i) {
+		r = c->write(MEM, w, 0b0);
+		CHECK(r == BLOCKED); // BLOCKED
+
+		r = c->write(FETCH, w, 0b1);
+		CHECK(r == WAIT); // WAIT
+
+		actual = c->view(0, 1)[0];
+		REQUIRE(expected == actual);
+		c->resolve();
+		d->resolve();
+	}
+
+	r = c->write(MEM, w, 0b0);
+	CHECK(r == OK);
+	r = c->write(FETCH, w, 0b1);
+	CHECK(r == WAIT);
+
+	c->resolve();
+	d->resolve();
+
+	actual = d->view(0, 1)[0];
+	// we do NOT write back now!
+	REQUIRE(expected == actual);
+
+	expected.at(0) = w;
+	actual = c->view(0, 1)[0];
+	REQUIRE(expected == actual);
+
+	r = c->write(FETCH, w, 0b1);
+	// this should have been loaded already!
+	CHECK(r == OK);
+
+	c->resolve();
+	d->resolve();
+
+	expected.at(1) = w;
+	actual = c->view(0, 1)[0];
+	REQUIRE(expected == actual);
+
+	delete d;
+	delete c;
+}
+
+TEST_CASE("dram takes \"forever\", two concurrent requests different index", "[cache]")
+{
+	int delay = 0;
+	Dram *d = new Dram(MEM_SIZE, delay + 2);
+	Cache *c = new Cache(d, 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;
+
+	int i;
+	Response r;
+	for (i = 0; i < delay + 2; ++i) {
+		r = c->write(MEM, w, 0b0);
+		CHECK(r == BLOCKED); // BLOCKED
+
+		r = c->write(FETCH, w, 0b100);
+		CHECK(r == WAIT); // WAIT
+
+		actual = c->view(0, 1)[0];
+		REQUIRE(expected == actual);
+		c->resolve();
+		d->resolve();
+	}
+
+	r = c->write(MEM, w, 0b0);
+	CHECK(r == OK);
+	r = c->write(FETCH, w, 0b1);
+	CHECK(r == WAIT);
+
+	c->resolve();
+	d->resolve();
+
+	actual = d->view(0, 1)[0];
+	// we do NOT write back now!
+	REQUIRE(expected == actual);
+
+	expected.at(0) = w;
+	actual = c->view(0, 1)[0];
+	REQUIRE(expected == actual);
+
+	for (i = 0; i < delay + 2; ++i) {
+		r = c->write(FETCH, w, 0b100);
+		CHECK(r == BLOCKED); // BLOCKED
+
+		actual = c->view(0, 1)[0];
+		REQUIRE(expected == actual);
+		c->resolve();
+		d->resolve();
+	}
+
+	r = c->write(FETCH, w, 0b1);
+	CHECK(r == OK);
+
+	c->resolve();
+	d->resolve();
+
+	expected.at(1) = w;
+	actual = c->view(0, 1)[0];
+	REQUIRE(expected == actual);
+
+	delete d;
+	delete c;
+}
+
+TEST_CASE("dram takes \"forever\", two concurrent requests different tag", "[cache]")
+{
+	// TODO
+}
diff --git a/tests/dram.cc b/tests/dram.cc
index 95ef90a..27fc24f 100644
--- a/tests/dram.cc
+++ b/tests/dram.cc
@@ -85,8 +85,6 @@ TEST_CASE(
 		CHECK(r == WAIT);
 
 		actual = d->view(0, 1)[0];
-		CHECK(r == WAIT);
-
 		REQUIRE(expected == actual);
 		d->resolve();
 	}