Merge pull request #2 from bdunahu/bdunahu

[WIP] Memory Rewrite

17 files changed, 453 insertions, 549 deletions

diff --git a/.clang-format b/.clang-format
index 39ed432..30fe2e7 100644
--- a/.clang-format
+++ b/.clang-format
@@ -1,11 +1,12 @@
 ---
 Language: Cpp
+AlwaysBreakAfterDefinitionReturnType: All
 AlignAfterOpenBracket: AlwaysBreak
 AllowAllParametersOfDeclarationOnNextLine: true
 BinPackParameters: false
 BreakBeforeBraces: Linux
 PointerAlignment: Right
-ColumnLimit: 80
+ColumnLimit: 100
 IndentWidth: 4
 TabWidth: 4
 UseTab: Always
\ No newline at end of file
diff --git a/CMakeLists.txt b/CMakeLists.txt
index f8ec7be..558f214 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -1,7 +1,8 @@
 cmake_minimum_required(VERSION 3.5)
-set(CMAKE_CXX_COMPILER "g++")
 project(ram)
 
+option(RAM_TESTS "Enable creation of a memory-subsystem test binary." ON)
+
 set(CMAKE_EXPORT_COMPILE_COMMANDS ON)
 
 add_compile_options(-Wall -lstdc++ -g -O0)
@@ -11,28 +12,26 @@ add_compile_options(-Wextra -Wpedantic)
 set(CMAKE_CXX_STANDARD 17)
 set(CMAKE_CXX_STANDARD_REQUIRED ON)
 
-# header files
-include_directories(
-	${PROJECT_SOURCE_DIR}/inc
-)
-
 # gather source files
 file(GLOB_RECURSE SRCS "src/*.cc")
 
 # binary executable
 add_library(${PROJECT_NAME}_lib ${SRCS})
-target_link_libraries(${PROJECT_NAME}_lib)
+target_include_directories(${PROJECT_NAME}_lib PUBLIC ${PROJECT_SOURCE_DIR}/inc)
 
-find_package(Catch2 REQUIRED)
+if(RAM_TESTS)
+	find_package(Catch2 REQUIRED)
 
-#gather test files
-file(GLOB_RECURSE TESTS "tests/*.cc")
+	#gather test files
+	file(GLOB_RECURSE TESTS "tests/*.cc")
 
-# test executable
-add_executable(tests ${SRCS} ${TESTS})
-target_link_libraries(tests PRIVATE Catch2::Catch2WithMain PRIVATE)
+	# test executable
+	add_executable(tests ${SRCS} ${TESTS})
+	target_include_directories(tests PRIVATE ${PROJECT_SOURCE_DIR}/inc ${PROJECT_SOURCE_DIR}/inc)
+	target_link_libraries(tests PRIVATE Catch2::Catch2WithMain PRIVATE)
 
-# test discovery
-include(CTest)
-include(Catch)
-catch_discover_tests(tests)
+	# test discovery
+	include(CTest)
+	include(Catch)
+	catch_discover_tests(tests)
+endif()
diff --git a/inc/cache.h b/inc/cache.h
index 0f15536..6f06466 100644
--- a/inc/cache.h
+++ b/inc/cache.h
@@ -3,77 +3,75 @@
 #include "definitions.h"
 #include "storage.h"
 #include <array>
+#include <cmath>
 #include <functional>
 #include <ostream>
 
+/**
+ * Parse an address into a tag, index into the cache table, and a line
+ * offset.
+ * @param the address to be parsed
+ * @param the resulting tag
+ * @param the resulting index
+ * @param the resulting offset
+ */
+// clang-format off
+#define GET_FIELDS(a, t, i, o) \
+    *(t) = GET_MID_BITS(a, this->size + LINE_SPEC - this->ways, MEM_WORD_SPEC); \
+    *(i) = GET_MID_BITS(a, LINE_SPEC, this->size + LINE_SPEC - this->ways); \
+    *(o) = GET_LS_BITS(a, LINE_SPEC)
+// clang-format on
+
 class Cache : public Storage
 {
   public:
 	/**
-	 * Constructor.
+nn	 * Constructor.
 	 * @param The number of `lines` contained in memory. The total number of
 	 * words is this number multiplied by LINE_SIZE.
 	 * @param The next lowest level in storage. Methods from this object are
 	 * called in case of a cache miss.
+	 * @param The number of bits required to specify a line in this level of cache.
+	 * @param The number of ways this line of cache uses, or the number of data addresses stored for
+   * certain address index.
 	 * @param The number of clock cycles each access takes.
 	 * @return A new cache object.
 	 */
-	Cache(Storage *lower, int delay);
+	Cache(Storage *lower, unsigned int size, unsigned int ways, int delay);
 	~Cache();
 
-	int
-	write_word(void *, signed int, int) override;
-	int
-	write_line(void *, std::array<signed int, LINE_SIZE>, int) override;
-	int
-	read_line(void *, int, std::array<signed int, LINE_SIZE> &) override;
-	int
-	read_word(void *, int, signed int &) override;
-
-	/**
-	 * Getter for the meta attribute.
-	 * TODO this doesn't seem like good object-oriented practice.
-	 * @return this->meta
-	 */
-	std::array<std::array<int, 2>, L1_CACHE_LINES>
-	get_meta() const;
+	int write_word(void *, signed int, int) override;
+	int write_line(void *, std::array<signed int, LINE_SIZE>, int) override;
+	int read_line(void *, int, std::array<signed int, LINE_SIZE> &) override;
+	int read_word(void *, int, signed int &) override;
 
   private:
+	int process(
+		void *id, int address, std::function<void(int index, int offset)> request_handler) override;
 	/**
-	 * Helper for all access methods.
-	 * Calls `request_handler` when `id` is allowed to complete its
-	 * request cycle.
-	 * @param the source making the request
-	 * @param the address to write to
-	 * @param the function to call when an access should be completed
-	 */
-	int
-	process(void *id, int address, std::function<void(int index, int offset)> request_handler);
-	/**
-	 * Returns OK if `id` is allowed to complete its request this cycle.
-	 * Handles cache misses, wait times, and setting the current id this
-	 * storage is serving.
-	 * @param the id asking for a resource
-	 * @return 1 if the access can be carried out this function call, 0 otherwise.
-	 */
-	int
-	is_access_cleared(void *id, int address);
-	/**
-	 * Helper for is_access_cleared.
+	 * Helper for process.
 	 * Fetches `address` from a lower level of storage if it is not already
 	 * present. The victim line is chosen/written back.
 	 * @param the address that must be present in cache.
 	 * @param 0 if the address is currently in cache, 1 if it is being fetched.
 	 */
-	int
-	is_address_missing(int address);
+	int is_address_missing(int address);
+	/**
+	 * The number of bits required to specify a line in this level of cache.
+	 */
+	unsigned int size;
+	/**
+	 * The number of bits required to specify a way, or the number of data addresses stored for
+	 * certain address index.
+	 */
+	unsigned int ways;
 	/**
 	 * 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_LINES> meta;
+	std::vector<std::array<signed int, 3>> meta;
 };
 
 #endif /* CACHE_H_INCLUDED */
diff --git a/inc/definitions.h b/inc/definitions.h
index 6fa29ee..8513361 100644
--- a/inc/definitions.h
+++ b/inc/definitions.h
@@ -20,22 +20,12 @@
  * The number of bits to specify a memory line
  * The total number of lines in memory
  */
-#define MEM_WORD_SPEC 10
+#define MEM_WORD_SPEC 16
 #define MEM_LINE_SPEC static_cast<unsigned int>(MEM_WORD_SPEC - LINE_SPEC)
 #define MEM_WORDS static_cast<int>(pow(2, MEM_WORD_SPEC))
 #define MEM_LINES static_cast<int>(pow(2, MEM_LINE_SPEC))
 
 /**
- * The number of bits to specify a l1 cache word
- * The number of bits to specify a l1 cache line
- * The total number of lines in l1 cache
- */
-#define L1_CACHE_WORD_SPEC 7
-#define L1_CACHE_LINE_SPEC                                                     \
-	static_cast<unsigned int>(L1_CACHE_WORD_SPEC - LINE_SPEC)
-#define L1_CACHE_LINES static_cast<int>(pow(2, L1_CACHE_LINE_SPEC))
-
-/**
  * The total number of cycles a memory access takes
  */
 #define MEM_DELAY 3
@@ -46,42 +36,6 @@
 #define L1_CACHE_DELAY 0
 
 /**
- * The number of general purpose registers
- */
-#define GPR_NUM 16
-
-/**
- * The number of vector registers
- */
-#define V_NUM 8
-
-/**
- * The number of bits to specify an instruction type
- */
-#define TYPE_SIZE 2
-
-/**
- * The number of bits to specify a register
- */
-#define REG_SIZE 5
-
-/**
- * The number of bits to specify an R-Type opcode.
- */
-#define R_OPCODE_SIZE 5
-
-/**
- * The number of bits to specify an opcode.
- */
-#define OPCODE_SIZE 4
-
-/**
- * The maximum value an integer can hold.
- * The minimum is always this number plus one negated.
- */
-#define MAX_INT 2147483647
-
-/**
  * 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
diff --git a/inc/dram.h b/inc/dram.h
index c6c3159..2a4e358 100644
--- a/inc/dram.h
+++ b/inc/dram.h
@@ -5,6 +5,15 @@
 #include <functional>
 #include <ostream>
 
+// clang-format off
+/**
+ * Ensures address is within the current memory size using a clean wrap.
+ * @param an address
+ */
+#define WRAP_ADDRESS(a) \
+  ((a < 0) ? ((a % MEM_WORDS) + MEM_WORDS) % MEM_WORDS : a % MEM_WORDS)
+// clang-format on
+
 class Dram : public Storage
 {
   public:
@@ -16,42 +25,25 @@ class Dram : public Storage
 	Dram(int delay);
 	~Dram();
 
-	int
-	write_word(void *, signed int, int) override;
-	int
-	write_line(void *, std::array<signed int, LINE_SIZE>, int) override;
-	int
-	read_word(void *, int, signed int &) override;
-	int
-	read_line(void *, int, std::array<signed int, LINE_SIZE> &) override;
+	int write_word(void *, signed int, int) override;
+	int write_line(void *, std::array<signed int, LINE_SIZE>, int) override;
+	int read_word(void *, int, signed int &) override;
+	int read_line(void *, int, std::array<signed int, LINE_SIZE> &) override;
 
 	/**
 	 * TODO This will accept a file at a later date.
 	 */
-	void
-	load(std::vector<signed int> program);
+	void load(std::vector<signed int> program);
 
   private:
+	int process(void *id, int address, std::function<void(int line, int word)> request_handler) override;
 	/**
-	 * Helper for all access methods.
-	 * Calls `request_handler` when `id` is allowed to complete its
-	 * request cycle.
-	 * @param the source making the request
-	 * @param the address to write to
-	 * @param the function to call when an access should be completed
-	 * @return 1 if the access completed successfully, 0 otherwise
-	 */
-	int
-	process(void *id, int address, std::function<void(int line, int word)> request_handler);
-	/**
-	 * Returns OK if `id` is allowed to complete its request this cycle.
-	 * Handles wait times, side door, and setting the current id this
-	 * storage is serving.
-	 * @param the source making the request
-	 * @return 1 if the access can be completed this function call, 0 otherwise
+	 * Given `address`, returns the line and word it is in.
+	 * @param an address
+	 * @param the line (row) `address` is in
+	 * @param the word (column) `address` corresponds to
 	 */
-	int
-	is_access_cleared(void *id);
+	void get_memory_index(int address, int &line, int &word);
 };
 
 #endif /* DRAM_H_INCLUDED */
diff --git a/inc/storage.h b/inc/storage.h
index 81194da..1bf5805 100644
--- a/inc/storage.h
+++ b/inc/storage.h
@@ -3,6 +3,7 @@
 #include "definitions.h"
 #include <algorithm>
 #include <array>
+#include <functional>
 #include <map>
 #include <vector>
 
@@ -24,10 +25,8 @@ class Storage
 	 * @param the address to write to.
 	 * @return 1 if the request was completed, 0 otherwise.
 	 */
-	virtual int
-	write_word(void *id, signed int data, int address) = 0;
-	virtual int
-	write_line(void *id, std::array<signed int, LINE_SIZE> data_line, int address) = 0;
+	virtual int write_word(void *id, signed int data, int address) = 0;
+	virtual int write_line(void *id, std::array<signed int, LINE_SIZE> data_line, int address) = 0;
 
 	/**
 	 * Get the data line at `address`.
@@ -36,10 +35,8 @@ class Storage
 	 * @param the data being returned
 	 * @return 1 if the request was completed, 0 otherwise
 	 */
-	virtual int
-	read_line(void *id, int address, std::array<signed int, LINE_SIZE> &data) = 0;
-	virtual int
-	read_word(void *id, int address, signed int &data) = 0;
+	virtual int read_line(void *id, int address, std::array<signed int, LINE_SIZE> &data) = 0;
+	virtual int read_word(void *id, int address, signed int &data) = 0;
 
 	/**
 	 * Sidedoor view of `lines` of memory starting at `base`.
@@ -48,11 +45,34 @@ class Storage
 	 * @return A matrix of data values, where each row is a line and each column
 	 * is a word.
 	 */
-	std::vector<std::array<signed int, LINE_SIZE>>
-	view(int base, int lines) const;
+	std::vector<std::array<signed int, LINE_SIZE>> view(int base, int lines) const;
 
   protected:
 	/**
+	 * Helper for all access methods.
+	 * Calls `request_handler` when `id` is allowed to complete its
+	 * request cycle.
+	 * May include extra checks depending on storage device.
+	 * @param the source making the request
+	 * @param the address to write to
+	 * @param the function to call when an access should be completed
+	 */
+	virtual int
+	process(void *id, int address, std::function<void(int index, int offset)> request_handler) = 0;
+	/**
+	 * Helper for process. Given `id`, returns 0 if the request should trivially be ignored.
+	 * @param the source making the request
+	 * @return 0 if the request should not be completed, 1 if it should be evaluated further.
+	 */
+	int preprocess(void *id);
+	/**
+	 * Returns OK if `id` should complete its request this cycle. In the case it can, automatically
+	 * clears the current requester.
+	 * @param the id asking for a resource
+	 * @return 1 if the access can be carried out this function call, 0 otherwise.
+	 */
+	int is_data_ready();
+	/**
 	 * The data currently stored in this level of storage.
 	 */
 	std::vector<std::array<signed int, LINE_SIZE>> *data;
diff --git a/inc/utils.h b/inc/utils.h
deleted file mode 100644
index a375b68..0000000
--- a/inc/utils.h
+++ /dev/null
@@ -1,39 +0,0 @@
-#ifndef UTILS_H
-#define UTILS_H
-#include <string>
-
-/**
- * Parse an address into a tag, index into the cache table, and a line
- * offset.
- * @param the address to be parsed
- * @param the resulting tag
- * @param the resulting index
- * @param the resulting offset
- */
-void get_cache_fields(int address, int *tag, int *index, int *offset);
-
-/**
- * Formats a string using snprintf.
- * @param an object that represents the format string
- * @param arguments to be formatted
- * @return a string object holding the formatted result
- */
-const std::string string_format(const char *const zcFormat, ...);
-
-/**
- * Given `address`, returns an address that is within the current memory size
- * using a clean wrap.
- * @param an address
- * @return an address guaranteed to be within range.
- */
-int wrap_address(int address);
-
-/**
- * Given `address`, returns the line and word it is in.
- * @param an address
- * @param the line (row) `address` is in
- * @param the word (column) `address` corresponds to
- */
-void get_memory_index(int address, int &line, int &word);
-
-#endif /* UTILS_H_INCLUDED */
diff --git a/src/cache.cc b/src/cache.cc
index bbb90b4..08545fd 100644
--- a/src/cache.cc
+++ b/src/cache.cc
@@ -1,14 +1,20 @@
 #include "cache.h"
 #include "definitions.h"
-#include "utils.h"
-#include <bits/stdc++.h>
+#include <iostream>
 #include <iterator>
 
-Cache::Cache(Storage *lower, int delay) : Storage(delay)
+Cache::Cache(Storage *lower, unsigned int size, unsigned int ways, int delay) : Storage(delay)
 {
-	this->data->resize(L1_CACHE_LINES);
+	int true_size;
+
+	true_size = 1 << size;
+	this->data->resize(true_size);
+	this->meta = std::vector<std::array<signed int, 3>>(true_size, {-1, -1, -1});
 	this->lower = lower;
-	this->meta.fill({-1, -1});
+
+	this->size = size;
+	// store the number of bits which are moved into the tag field
+	this->ways = ways;
 }
 
 Cache::~Cache()
@@ -36,7 +42,6 @@ Cache::write_line(void *id, std::array<signed int, LINE_SIZE> data_line, int add
 	});
 }
 
-// TODO: tests for multi level cache
 int
 Cache::read_line(void *id, int address, std::array<signed int, LINE_SIZE> &data_line)
 {
@@ -56,36 +61,14 @@ Cache::read_word(void *id, int address, signed int &data)
 int
 Cache::process(void *id, int address, std::function<void(int index, int offset)> request_handler)
 {
-	int r;
-	r = this->is_access_cleared(id, address);
-	if (r) {
-		int tag, index, offset;
-		get_cache_fields(address, &tag, &index, &offset);
-		request_handler(index, offset);
-	}
-	return r;
-}
+	if (!preprocess(id) || is_address_missing(address) || !this->is_data_ready())
+		return 0;
 
-int
-Cache::is_access_cleared(void *id, int address)
-{
-	/* Do this first--then process the first cycle immediately. */
-	if (id == nullptr)
-		throw std::invalid_argument("Accessor cannot be nullptr.");
-	if (this->current_request == nullptr)
-		this->current_request = id;
-	if (this->current_request == id) {
-		if (is_address_missing(address))
-			return 0;
-		else if (this->wait_time == 0) {
-			this->current_request = nullptr;
-			this->wait_time = delay;
-			return 1;
-		} else {
-			--this->wait_time;
-		}
-	}
-	return 0;
+	int tag, index, offset;
+	GET_FIELDS(address, &tag, &index, &offset);
+	request_handler(index, offset);
+
+	return 1;
 }
 
 int
@@ -93,9 +76,9 @@ Cache::is_address_missing(int expected)
 {
 	int r, q, tag, index, offset;
 	std::array<signed int, LINE_SIZE> *actual;
-	std::array<int, 2> *meta;
+	std::array<int, 3> *meta;
 
-	get_cache_fields(expected, &tag, &index, &offset);
+	GET_FIELDS(expected, &tag, &index, &offset);
 	r = 0;
 	meta = &this->meta.at(index);
 	actual = &this->data->at(index);
@@ -104,8 +87,7 @@ Cache::is_address_missing(int expected)
 		r = 1;
 		if (meta->at(1) >= 0) {
 			q = this->lower->write_line(
-				this, *actual,
-				((index << LINE_SPEC) + (meta->at(0) << (L1_CACHE_LINE_SPEC + LINE_SPEC))));
+				this, *actual, ((index << LINE_SPEC) + (meta->at(0) << (this->size + LINE_SPEC))));
 			if (q) {
 				meta->at(1) = -1;
 			}
@@ -120,10 +102,12 @@ Cache::is_address_missing(int expected)
 	return r;
 }
 
-std::array<std::array<int, 2>, L1_CACHE_LINES>
-Cache::get_meta() const
-{
-	std::array<std::array<int, 2>, L1_CACHE_LINES> ret;
-	std::copy(std::begin(this->meta), std::end(this->meta), std::begin(ret));
-	return ret;
-}
+// unsigned int
+// Cache::get_true_index(unsigned int index)
+// {
+// }
+
+// unsigned int
+// Cache::get_replacement_index(unsigned int index)
+// {
+// }
diff --git a/src/dram.cc b/src/dram.cc
index d81e2d2..53db16b 100644
--- a/src/dram.cc
+++ b/src/dram.cc
@@ -4,7 +4,6 @@
 #include <bits/stdc++.h>
 #include <bitset>
 #include <iterator>
-#include <utils.h>
 
 Dram::Dram(int delay) : Storage(delay) { this->data->resize(MEM_LINES); }
 
@@ -25,7 +24,6 @@ Dram::write_word(void *id, signed int data, int address)
 	return process(id, address, [&](int line, int word) { this->data->at(line).at(word) = data; });
 }
 
-// TODO requires testing
 int
 Dram::read_line(void *id, int address, std::array<signed int, LINE_SIZE> &data_line)
 {
@@ -56,32 +54,18 @@ Dram::load(std::vector<signed int> program)
 int
 Dram::process(void *id, int address, std::function<void(int line, int word)> request_handler)
 {
-	int r;
-	r = this->is_access_cleared(id);
-	if (r) {
-		int line, word;
-		get_memory_index(address, line, word);
-		request_handler(line, word);
-	}
-	return r;
+	if (!preprocess(id) || !this->is_data_ready())
+		return 0;
+
+	int line, word;
+	get_memory_index(address, line, word);
+	request_handler(line, word);
+	return 1;
 }
 
-int
-Dram::is_access_cleared(void *id)
+void
+Dram::get_memory_index(int address, int &line, int &word)
 {
-	/* Do this first--then process the first cycle immediately. */
-	if (id == nullptr)
-		throw std::invalid_argument("Accessor cannot be nullptr.");
-	if (this->current_request == nullptr)
-		this->current_request = id;
-	if (this->current_request == id) {
-		if (this->wait_time == 0) {
-			this->current_request = nullptr;
-			this->wait_time = delay;
-			return 1;
-		} else {
-			--this->wait_time;
-		}
-	}
-	return 0;
+	line = WRAP_ADDRESS(address) / LINE_SIZE;
+	word = address % LINE_SIZE;
 }
diff --git a/src/storage.cc b/src/storage.cc
index 4ad916b..ee2e7e7 100644
--- a/src/storage.cc
+++ b/src/storage.cc
@@ -1,8 +1,10 @@
 #include "storage.h"
 #include "definitions.h"
 #include <algorithm>
+#include <stdexcept>
 
-Storage::Storage(int delay) {
+Storage::Storage(int delay)
+{
 	this->data = new std::vector<std::array<signed int, LINE_SIZE>>;
 	this->delay = delay;
 	this->lower = nullptr;
@@ -18,3 +20,32 @@ Storage::view(int base, int lines) const
 	std::copy(this->data->begin() + base, this->data->begin() + base + lines, ret.begin());
 	return ret;
 }
+
+int
+Storage::preprocess(void *id)
+{
+	if (id == nullptr)
+		throw std::invalid_argument("Accessor cannot be nullptr.");
+
+	if (this->current_request == nullptr)
+		this->current_request = id;
+
+	return this->current_request == id;
+}
+
+int
+Storage::is_data_ready()
+{
+	int r;
+
+	r = 0;
+	if (this->wait_time == 0) {
+		this->current_request = nullptr;
+		this->wait_time = delay;
+		r = 1;
+	} else {
+		--this->wait_time;
+	}
+
+	return r;
+}
diff --git a/src/utils.cc b/src/utils.cc
deleted file mode 100644
index e12a0e0..0000000
--- a/src/utils.cc
+++ /dev/null
@@ -1,42 +0,0 @@
-#include "utils.h"
-#include "definitions.h"
-#include <cstdarg>
-#include <string>
-#include <vector>
-
-void get_cache_fields(int address, int *tag, int *index, int *offset)
-{
-	*tag = GET_MID_BITS(address, L1_CACHE_LINE_SPEC + LINE_SPEC, MEM_WORD_SPEC);
-	*index = GET_MID_BITS(address, LINE_SPEC, L1_CACHE_LINE_SPEC + LINE_SPEC);
-	*offset = GET_LS_BITS(address, LINE_SPEC);
-}
-
-const std::string string_format(const char *const zcFormat, ...)
-{
-	va_list vaArgs;
-	va_start(vaArgs, zcFormat);
-
-	va_list vaArgsCopy;
-	va_copy(vaArgsCopy, vaArgs);
-	const int iLen = std::vsnprintf(NULL, 0, zcFormat, vaArgsCopy);
-	va_end(vaArgsCopy);
-
-	std::vector<char> zc(iLen + 1);
-	std::vsnprintf(zc.data(), zc.size(), zcFormat, vaArgs);
-	va_end(vaArgs);
-	return std::string(zc.data(), iLen);
-}
-
-int wrap_address(int address)
-{
-	if (address < 0) {
-		return ((address % MEM_WORDS) + MEM_WORDS) % MEM_WORDS;
-	}
-	return address % MEM_WORDS;
-}
-
-void get_memory_index(int address, int &line, int &word)
-{
-	line = wrap_address(address) / LINE_SIZE;
-	word = address % LINE_SIZE;
-}
diff --git a/tests/c11.h b/tests/c11.h
new file mode 100644
index 0000000..e5599db
--- /dev/null
+++ b/tests/c11.h
@@ -0,0 +1,54 @@
+#include "cache.h"
+#include "dram.h"
+#include "storage.h"
+#include <algorithm>
+#include <array>
+#include <catch2/catch_test_macros.hpp>
+#include <functional>
+
+/**
+ * one way associative, single level
+ */
+class C11
+{
+  public:
+	C11()
+	{
+		this->m_delay = 4;
+		this->c_delay = 2;
+		this->mem = new int();
+		this->fetch = new int();
+		this->c = new Cache(new Dram(this->m_delay), 5, 0, this->c_delay);
+		this->expected = {0, 0, 0, 0};
+		this->actual = this->c->view(0, 1)[0];
+	}
+
+	~C11()
+	{
+		delete this->c;
+		delete this->mem;
+		delete this->fetch;
+	}
+
+	void
+	wait_then_do(int delay, std::function<int()> f)
+	{
+		for (int i = 0; i < delay; ++i) {
+			int r = f();
+
+			// check response
+			CHECK(!r);
+			// check for early modifications
+			actual = c->view(0, 1)[0];
+			REQUIRE(this->expected == this->actual);
+		}
+	}
+
+	int m_delay;
+	int c_delay;
+	Cache *c;
+	int *mem;
+	int *fetch;
+	std::array<signed int, LINE_SIZE> expected;
+	std::array<signed int, LINE_SIZE> actual;
+};
diff --git a/tests/cache.cc b/tests/cache.cc
deleted file mode 100644
index 313f93f..0000000
--- a/tests/cache.cc
+++ /dev/null
@@ -1,167 +0,0 @@
-#include "cache.h"
-#include "dram.h"
-#include <catch2/catch_test_macros.hpp>
-
-class CacheFixture
-{
-  public:
-	CacheFixture()
-	{
-		this->m_delay = 4;
-		this->c_delay = 2;
-		this->d = new Dram(this->m_delay);
-		this->c = new Cache(this->d, this->c_delay);
-		this->mem = new int;
-		this->fetch = new int;
-		this->expected = {0, 0, 0, 0};
-		this->actual = this->c->view(0, 1)[0];
-	}
-
-	~CacheFixture()
-	{
-		delete this->c;
-		delete this->mem;
-		delete this->fetch;
-	}
-
-	/**
-	 * An operation that is done a lot.
-	 */
-	void
-	wait_for_storage(int delay, int expected, std::function<int()> f)
-	{
-		for (int i = 0; i < delay; ++i) {
-			int r = f();
-
-			// check response
-			CHECK(r == expected);
-			// check for early modifications
-			actual = c->view(0, 1)[0];
-			REQUIRE(this->expected == this->actual);
-		}
-	}
-
-	int m_delay;
-	int c_delay;
-	Cache *c;
-	Dram *d;
-	int *mem;
-	int *fetch;
-	std::array<signed int, LINE_SIZE> expected;
-	std::array<signed int, LINE_SIZE> actual;
-};
-
-TEST_CASE_METHOD(CacheFixture, "store 0th element in DELAY cycles", "[dram]")
-{
-	int r;
-	signed int w;
-	CHECK(expected == actual);
-
-	w = 0x11223344;
-	// delay + 1 due to internal logic, when mem
-	// finishes handle_miss still returns 'blocked'
-	this->wait_for_storage(this->m_delay + this->c_delay + 1, 0, [this, w]() {
-		return this->c->write_word(this->mem, w, 0b0);
-	});
-
-	r = c->write_word(this->mem, w, 0b0);
-	CHECK(r);
-
-	actual = this->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);
-}
-
-TEST_CASE_METHOD(CacheFixture, "store 0th, 1st element in DELAY cycles, with conflict", "[cache]")
-{
-	signed int w;
-	int r, i;
-	CHECK(expected == actual);
-
-	w = 0x11223344;
-	// delay + 1 due to internal logic, when mem
-	// finishes handle_miss still returns 'blocked'
-	for (i = 0; i < this->m_delay + this->c_delay + 1; ++i) {
-		r = c->write_word(this->mem, w, 0b0);
-		CHECK(!r);
-		r = c->write_word(this->fetch, w, 0b1);
-		CHECK(!r);
-
-		// check for early modifications
-		actual = c->view(0, 1)[0];
-		REQUIRE(this->expected == this->actual);
-	}
-
-	r = c->write_word(this->mem, w, 0b0);
-	CHECK(r);
-
-	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);
-
-	// this should have been loaded already!
-	this->wait_for_storage(
-		this->c_delay, 0, [this, w]() { return this->c->write_word(this->fetch, w, 0b1); });
-
-	r = c->write_word(this->fetch, w, 0b1);
-	CHECK(r);
-
-	expected.at(1) = w;
-	actual = c->view(0, 1)[0];
-	REQUIRE(expected == actual);
-}
-
-TEST_CASE_METHOD(
-	CacheFixture, "store 0th, 1st element different tags, in DELAY cycles, no conflict", "[cache]")
-{
-	int r;
-	signed int w;
-	CHECK(expected == actual);
-
-	w = 0x11223344;
-	// delay + 1 due to internal logic, when mem
-	// finishes handle_miss still returns 'blocked'
-	this->wait_for_storage(this->m_delay + this->c_delay + 1, 0, [this, w]() {
-		return this->c->write_word(this->mem, w, 0b0);
-	});
-
-	r = c->write_word(this->mem, w, 0b0);
-	CHECK(r);
-
-	expected.at(0) = w;
-	actual = c->view(0, 1)[0];
-	REQUIRE(expected == actual);
-
-	// write back to memory
-	// fetch new address (don't run the completion cycle yet)
-	this->wait_for_storage(this->m_delay + this->m_delay + 1, 0, [this, w]() {
-		return this->c->write_word(this->fetch, w, 0b10000001);
-	});
-
-	// after the fetch, this cache line should be empty
-	this->c->write_word(this->fetch, w, 0b10000001);
-	CHECK(r);
-
-	expected.at(0) = 0;
-	actual = c->view(0, 1)[0];
-	CHECK(expected == actual);
-
-	this->wait_for_storage(
-		this->c_delay, 0, [this, w]() { return this->c->write_word(this->fetch, w, 0b10000001); });
-
-	r = c->write_word(this->fetch, w, 0b10000001);
-	CHECK(r);
-
-	expected.at(0) = 0;
-	expected.at(1) = w;
-	actual = c->view(0, 1)[0];
-	REQUIRE(expected == actual);
-}
diff --git a/tests/cache_1_1.cc b/tests/cache_1_1.cc
new file mode 100644
index 0000000..7d16f76
--- /dev/null
+++ b/tests/cache_1_1.cc
@@ -0,0 +1,111 @@
+#include "c11.h"
+#include "cache.h"
+#include "dram.h"
+#include <catch2/catch_test_macros.hpp>
+
+TEST_CASE_METHOD(C11, "store 0th element in DELAY cycles", "[dram]")
+{
+	int r;
+	signed int w;
+	CHECK(expected == actual);
+
+	w = 0x11223344;
+	// delay + 1 due to internal logic, when mem
+	// finishes is_address_missing still returns '1'
+	this->wait_then_do(this->m_delay + this->c_delay + 1, [this, w]() {
+		return this->c->write_word(this->mem, w, 0b0);
+	});
+
+	r = c->write_word(this->mem, w, 0b0);
+	CHECK(r);
+
+	expected.at(0) = w;
+	actual = c->view(0, 1)[0];
+	REQUIRE(expected == actual);
+}
+
+TEST_CASE_METHOD(C11, "store 0th, 1st element in DELAY cycles, with conflict", "[cache]")
+{
+	signed int w;
+	int r, i;
+	CHECK(expected == actual);
+
+	w = 0x11223344;
+	// delay + 1 due to internal logic, when mem
+	// finishes is_address_missing still returns '1'
+	for (i = 0; i < this->m_delay + this->c_delay + 1; ++i) {
+		r = c->write_word(this->mem, w, 0b0);
+		CHECK(!r);
+		r = c->write_word(this->fetch, w, 0b1);
+		CHECK(!r);
+
+		// check for early modifications
+		actual = c->view(0, 1)[0];
+		REQUIRE(this->expected == this->actual);
+	}
+
+	r = c->write_word(this->mem, w, 0b0);
+	CHECK(r);
+
+	expected.at(0) = w;
+	actual = c->view(0, 1)[0];
+	REQUIRE(expected == actual);
+
+	// this should have been loaded already!
+	this->wait_then_do(
+		this->c_delay, [this, w]() { return this->c->write_word(this->fetch, w, 0b1); });
+
+	r = c->write_word(this->fetch, w, 0b1);
+	CHECK(r);
+
+	expected.at(1) = w;
+	actual = c->view(0, 1)[0];
+	REQUIRE(expected == actual);
+}
+
+TEST_CASE_METHOD(
+	C11, "store 0th, 1st element different tags, in DELAY cycles, no conflict", "[cache]")
+{
+	int r;
+	signed int w;
+	CHECK(expected == actual);
+
+	w = 0x11223344;
+	// delay + 1 due to internal logic, when mem
+	// finishes is_address_missing still returns '1'
+	this->wait_then_do(this->m_delay + this->c_delay + 1, [this, w]() {
+		return this->c->write_word(this->mem, w, 0b0);
+	});
+
+	r = c->write_word(this->mem, w, 0b0);
+	CHECK(r);
+
+	expected.at(0) = w;
+	actual = c->view(0, 1)[0];
+	REQUIRE(expected == actual);
+
+	// write back to memory
+	// fetch new address (don't run the completion cycle yet)
+	this->wait_then_do(this->m_delay + this->m_delay + 1, [this, w]() {
+		return this->c->write_word(this->fetch, w, 0b10000001);
+	});
+
+	// after the fetch, this cache line should be empty
+	this->c->write_word(this->fetch, w, 0b10000001);
+	CHECK(r);
+
+	expected.at(0) = 0;
+	actual = c->view(0, 1)[0];
+	CHECK(expected == actual);
+
+	this->wait_then_do(
+		this->c_delay, [this, w]() { return this->c->write_word(this->fetch, w, 0b10000001); });
+
+	r = c->write_word(this->fetch, w, 0b10000001);
+	CHECK(r);
+
+	expected.at(0) = 0;
+	expected.at(1) = w;
+	actual = c->view(0, 1)[0];
+	REQUIRE(expected == actual);
+}
diff --git a/tests/cache_2_1.cc b/tests/cache_2_1.cc
new file mode 100644
index 0000000..cb48d2a
--- /dev/null
+++ b/tests/cache_2_1.cc
@@ -0,0 +1,87 @@
+#include "c11.h"
+#include "cache.h"
+#include "dram.h"
+#include "storage.h"
+#include <catch2/catch_test_macros.hpp>
+#include <iostream>
+
+/**
+ * One way associative, two level
+ * Assuming that each address is 14 bits (16384 word address space):
+ * LEVEL1: OFFSET=2, INDEX=5(32), TAG=7
+ * LEVEL2: OFFSET=2, INDEX=7(128), TAG=5
+ */
+class C21 : public C11
+{
+  public:
+	C21() : C11()
+	{
+		this->c2 = new Cache(new Dram(this->m_delay), 7, 0, this->c_delay);
+		this->c = new Cache(this->c2, 5, 0, this->c_delay);
+	}
+
+	Cache *c2;
+};
+
+// TEST_CASE_METHOD(C21, "store 32th, 33rd element in DELAY cycles",
+
+TEST_CASE_METHOD(C21, "store 32th, 96th element in DELAY cycles, evict to level 2", "[2level_cache]")
+{
+	int r;
+	signed int w;
+	CHECK(expected == actual);
+
+	w = 0x11223344;
+	// delay + 1 due to internal logic, when mem
+	// finishes handle_miss still returns 'blocked'
+	this->wait_then_do(this->m_delay + (this->c_delay * 2) + 2, [this, w]() {
+		return this->c->write_word(this->mem, w, 0b10000000);
+	});
+
+	r = this->c->write_word(this->mem, w, 0b10000000);
+	CHECK(r);
+
+	// check level 2
+	// note this is write-back == no write
+	actual = this->c2->view(32, 1)[0];
+	REQUIRE(expected == actual);
+
+	// check level 1
+	expected.at(0) = w;
+	actual = this->c->view(0, 1)[0];
+	REQUIRE(expected == actual);
+
+	// wait = evict
+	this->wait_then_do(this->c_delay + 1, [this, w]() {
+		return this->c->write_word(this->mem, w, 0b110000000);
+	});
+
+	// check level 2
+	actual = this->c2->view(32, 1)[0];
+	REQUIRE(expected == actual);
+
+	// read in line
+	this->wait_then_do(this->m_delay + this->c_delay + 1, [this, w]() {
+		return this->c->write_word(this->mem, w, 0b110000000);
+	});
+
+	expected.at(0) = 0;
+	// perform write
+	this->wait_then_do(this->c_delay + 1, [this, w]() {
+		return this->c->write_word(this->mem, w, 0b110000000);
+	});
+
+	r = this->c->write_word(this->mem, w, 0b110000000);
+	CHECK(r);
+
+	// check level 2
+	actual = this->c2->view(96, 1)[0];
+	REQUIRE(expected == actual);
+	expected.at(0) = w;
+	actual = this->c2->view(32, 1)[0];
+	REQUIRE(expected == actual);
+
+	// check level 1
+	actual = this->c->view(0, 1)[0];
+	REQUIRE(expected == actual);
+}
diff --git a/tests/dram.cc b/tests/dram.cc
index 086ca4a..06a7720 100644
--- a/tests/dram.cc
+++ b/tests/dram.cc
@@ -2,10 +2,10 @@
 #include <array>
 #include <catch2/catch_test_macros.hpp>
 
-class DramFixture
+class D
 {
   public:
-	DramFixture()
+	D()
 	{
 		this->delay = 3;
 		this->d = new Dram(this->delay);
@@ -15,7 +15,7 @@ class DramFixture
 		this->actual = this->d->view(0, 1)[0];
 	}
 
-	~DramFixture()
+	~D()
 	{
 		delete this->d;
 		delete this->mem;
@@ -44,14 +44,15 @@ class DramFixture
 	std::array<signed int, LINE_SIZE> actual;
 };
 
-TEST_CASE_METHOD(DramFixture, "store 0th element in DELAY cycles", "[dram]")
+TEST_CASE_METHOD(D, "store 0th element in DELAY cycles", "[dram]")
 {
 	int r;
 	signed int w;
 	CHECK(expected == actual);
 
 	w = 0x11223344;
-	this->wait_for_storage(this->delay, [this, w]() { return this->d->write_word(this->mem, w, 0x0); });
+	this->wait_for_storage(
+		this->delay, [this, w]() { return this->d->write_word(this->mem, w, 0x0); });
 
 	r = this->d->write_word(this->mem, w, 0x0);
 
@@ -61,14 +62,15 @@ TEST_CASE_METHOD(DramFixture, "store 0th element in DELAY cycles", "[dram]")
 	REQUIRE(expected == actual);
 }
 
-TEST_CASE_METHOD(DramFixture, "store 0th, 1st element in DELAY cycles, no conflict", "[dram]")
+TEST_CASE_METHOD(D, "store 0th, 1st element in DELAY cycles, no conflict", "[dram]")
 {
 	int r;
 	signed int w;
 	CHECK(expected == actual);
 
 	w = 0x11223344;
-	this->wait_for_storage(this->delay, [this, w]() { return this->d->write_word(this->mem, w, 0x0); });
+	this->wait_for_storage(
+		this->delay, [this, w]() { return this->d->write_word(this->mem, w, 0x0); });
 
 	r = d->write_word(this->mem, w, 0x0);
 	REQUIRE(r);
@@ -77,7 +79,8 @@ TEST_CASE_METHOD(DramFixture, "store 0th, 1st element in DELAY cycles, no confli
 	actual = d->view(0, 1)[0];
 	REQUIRE(expected == actual);
 
-	this->wait_for_storage(this->delay, [this, w]() { return this->d->write_word(this->fetch, w, 0x1); });
+	this->wait_for_storage(
+		this->delay, [this, w]() { return this->d->write_word(this->fetch, w, 0x1); });
 
 	r = d->write_word(this->fetch, w, 0x1);
 	CHECK(r);
@@ -87,7 +90,7 @@ TEST_CASE_METHOD(DramFixture, "store 0th, 1st element in DELAY cycles, no confli
 	REQUIRE(expected == actual);
 }
 
-TEST_CASE_METHOD(DramFixture, "store 0th element in DELAY cycles with conflict", "[dram]")
+TEST_CASE_METHOD(D, "store 0th element in DELAY cycles with conflict", "[dram]")
 {
 	int r, i;
 	signed int w;
@@ -112,7 +115,8 @@ TEST_CASE_METHOD(DramFixture, "store 0th element in DELAY cycles with conflict",
 	actual = d->view(0, 1)[0];
 	REQUIRE(expected == actual);
 
-	this->wait_for_storage(this->delay, [this, w]() { return this->d->write_word(this->fetch, w, 0x1); });
+	this->wait_for_storage(
+		this->delay, [this, w]() { return this->d->write_word(this->fetch, w, 0x1); });
 
 	r = d->write_word(this->fetch, w, 0x1);
 	CHECK(r);
@@ -122,7 +126,7 @@ TEST_CASE_METHOD(DramFixture, "store 0th element in DELAY cycles with conflict",
 	REQUIRE(expected == actual);
 }
 
-TEST_CASE_METHOD(DramFixture, "store line in DELAY cycles", "[dram]")
+TEST_CASE_METHOD(D, "store line in DELAY cycles", "[dram]")
 {
 	int r;
 	signed int w;
@@ -142,7 +146,7 @@ TEST_CASE_METHOD(DramFixture, "store line in DELAY cycles", "[dram]")
 	REQUIRE(expected == actual);
 }
 
-TEST_CASE_METHOD(DramFixture, "store line in DELAY cycles no conflict", "[dram]")
+TEST_CASE_METHOD(D, "store line in DELAY cycles no conflict", "[dram]")
 {
 	int r;
 	signed int w;
@@ -173,7 +177,7 @@ TEST_CASE_METHOD(DramFixture, "store line in DELAY cycles no conflict", "[dram]"
 	REQUIRE(expected == actual);
 }
 
-TEST_CASE_METHOD(DramFixture, "store line in DELAY cycles with conflict", "[dram]")
+TEST_CASE_METHOD(D, "store line in DELAY cycles with conflict", "[dram]")
 {
 	int r, i;
 	signed int w;
@@ -212,8 +216,7 @@ TEST_CASE_METHOD(DramFixture, "store line in DELAY cycles with conflict", "[dram
 	REQUIRE(expected == actual);
 }
 
-TEST_CASE_METHOD(
-	DramFixture, "store line in DELAY cycles, read in DELAY cycles, no conflict", "[dram]")
+TEST_CASE_METHOD(D, "store line in DELAY cycles, read in DELAY cycles, no conflict", "[dram]")
 {
 	int r, i, addr;
 	signed int w;
@@ -242,8 +245,7 @@ TEST_CASE_METHOD(
 	REQUIRE(expected == actual);
 }
 
-TEST_CASE_METHOD(
-	DramFixture, "store line in DELAY cycles, read in DELAY cycles with conflict", "[dram]")
+TEST_CASE_METHOD(D, "store line in DELAY cycles, read in DELAY cycles with conflict", "[dram]")
 {
 	int r, i, addr;
 	signed int w;
@@ -276,7 +278,7 @@ TEST_CASE_METHOD(
 }
 
 TEST_CASE_METHOD(
-	DramFixture,
+	D,
 	"store line in DELAY cycles, read one element at a time in DELAY cycles "
 	"with conflict",
 	"[dram]")
diff --git a/tests/utils.cc b/tests/utils.cc
deleted file mode 100644
index 2e0e934..0000000
--- a/tests/utils.cc
+++ /dev/null
@@ -1,65 +0,0 @@
-#include "utils.h"
-#include "definitions.h"
-#include <catch2/catch_test_macros.hpp>
-
-TEST_CASE("Parse arbitrary fields # one", "[utils]")
-{
-	int tag, index, offset;
-	int address = 0b0001010101;
-	get_cache_fields(address, &tag, &index, &offset);
-	CHECK(tag == 0b000);
-	CHECK(index == 0b10101);
-	CHECK(offset == 0b01);
-}
-
-TEST_CASE("Parse arbitrary fields # two", "[utils]")
-{
-	int tag, index, offset;
-	int address = 0b0100111011;
-	get_cache_fields(address, &tag, &index, &offset);
-	CHECK(tag == 0b010);
-	CHECK(index == 0b01110);
-	CHECK(offset == 0b11);
-}
-
-TEST_CASE("wrap address outside upper bound", "[utils]")
-{
-	int address = MEM_WORDS + 25;
-	int wrapped = wrap_address(address);
-	REQUIRE(wrapped == 25);
-}
-
-TEST_CASE("wrap address inside upper bound", "[utils]")
-{
-	int address = MEM_WORDS - 25;
-	int wrapped = wrap_address(address);
-	REQUIRE(wrapped == MEM_WORDS - 25);
-}
-
-TEST_CASE("wrap address at upper bound", "[utils]")
-{
-	int address = MEM_WORDS;
-	int wrapped = wrap_address(address);
-	REQUIRE(wrapped == 0);
-}
-
-TEST_CASE("wrap address lower than 0 with magnitude lesser than mem size", "[utils]")
-{
-	int address = -10;
-	int wrapped = wrap_address(address);
-	REQUIRE(wrapped == MEM_WORDS - 10);
-}
-
-TEST_CASE("wrap address lower than 0 but with magnitude greater than mem size", "[utils]")
-{
-	int address = -(MEM_WORDS + 10);
-	int wrapped = wrap_address(address);
-	REQUIRE(wrapped == MEM_WORDS - 10);
-}
-
-TEST_CASE("wrap address at 0", "[utils]")
-{
-	int address = 0;
-	int wrapped = wrap_address(address);
-	REQUIRE(wrapped == 0);
-}