Merge pull request #9 from bdunahu/bdunahuHEADmaster

Fixed bugs introduced with cache ways, small cleanups

3 files changed, 34 insertions, 49 deletions

diff --git a/inc/cache.h b/inc/cache.h
index b55b30c..0eee833 100644
--- a/inc/cache.h
+++ b/inc/cache.h
@@ -75,29 +75,14 @@ nn	 * Constructor.
 	 */
 	int priming_address(int address);
 	/**
-	 * Walks the ways in this set of ways. If none of the tags match, returns -1. Otherwise, returns
-	 * the index the matching data is located.
+	 * Searches the set of ways in cache belonging to `index' for `tag'. If a match is found,
+	 * returns the true index into the table. If a match is not found, returns a address suitable to
+	 * replace, dictated by the LRU replacement policy..
 	 * @param an index aligned to the set of ways in `this->data'
 	 * @param the tag to be matched
-	 * @return -1 if the tag is not present in this set of ways (not in cache), or the true index if
-	 * the tag is present.
+	 * @return the true index if the tag is present, or the index to be replaced if not.
 	 */
-	int is_address_missing(int true_index, int tag);
-	/**
-	 * Converts an index into a set of ways into an index into `this->data', which is a
-	 * 1D array. The next `this->ways' entries after the returned index represent the ways in the
-	 * set for this index.
-	 * @param an index to a set of ways
-	 * @param an index aligned to the set of ways in `this->data'
-	 */
-	int get_true_index(int index);
-	/**
-	 * Selects an index into the `data' and `meta' tables for write back using a random replacement
-	 * policy.
-	 * @param an index aligned to the set of ways in `this->data'
-	 * @return an index aligned to the data line selected for eviction
-	 */
-	int get_replacement_index(int index);
+	int search_ways_for(int true_index, int tag);
 	/**
 	 * The number of bits required to specify a line in this level of cache.
 	 */
@@ -108,6 +93,10 @@ nn	 * Constructor.
 	 */
 	unsigned int ways;
 	/**
+	 * The current access number. Used to assign usage data for the LRU replacement policy.
+	 */
+	unsigned int access_num;
+	/**
 	 * 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
diff --git a/inc/definitions.h b/inc/definitions.h
index f0946b8..737656d 100644
--- a/inc/definitions.h
+++ b/inc/definitions.h
@@ -43,11 +43,6 @@
 #define MEM_LINES static_cast<int>(pow(2, MEM_LINE_SPEC))
 
 /**
- * The total number of cycles a memory access takes
- */
-#define MEM_DELAY 3
-
-/**
  * 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/src/cache.cc b/src/cache.cc
index c8879b5..95ddf4a 100644
--- a/src/cache.cc
+++ b/src/cache.cc
@@ -20,6 +20,7 @@
 #include <cstdlib>
 #include <iostream>
 #include <iterator>
+#include <limits.h>
 
 Cache::Cache(Storage *lower, unsigned int size, unsigned int ways, int delay) : Storage(delay)
 {
@@ -33,6 +34,7 @@ Cache::Cache(Storage *lower, unsigned int size, unsigned int ways, int delay) :
 	this->size = size;
 	// store the number of bits which are moved into the tag field
 	this->ways = ways;
+	this->access_num = 0;
 }
 
 Cache::~Cache()
@@ -87,9 +89,15 @@ Cache::process(void *id, int address, std::function<void(int index, int offset)>
 		return 0;
 
 	int tag, index, offset;
+	std::array<int, 3> *meta;
+
 	GET_FIELDS(address, &tag, &index, &offset);
-	index = this->get_true_index(index);
+	index = this->search_ways_for(index, tag);
 	request_handler(index, offset);
+	// set usage status
+	meta = &this->meta.at(index);
+	meta->at(2) = (this->access_num % INT_MAX);
+	++this->access_num;
 
 	return 1;
 }
@@ -97,26 +105,25 @@ Cache::process(void *id, int address, std::function<void(int index, int offset)>
 int
 Cache::priming_address(int address)
 {
-	int tag, index, offset;
+	int tag, index, offset, t_index;
 	int r1, r2;
 	std::array<signed int, LINE_SIZE> *evict;
 	std::array<int, 3> *meta;
 
 	r1 = 0;
 	GET_FIELDS(address, &tag, &index, &offset);
-	index = this->get_true_index(index);
+	t_index = this->search_ways_for(index, tag);
+	meta = &this->meta.at(t_index);
 
-	if (this->is_address_missing(index, tag)) {
+	if (meta->at(0) != tag) {
 		r1 = 1;
 
-		index = this->get_replacement_index(index);
-		meta = &this->meta.at(index);
-		evict = &this->data->at(index);
+		evict = &this->data->at(t_index);
 
 		// handle eviction of dirty cache lines
 		if (meta->at(1) >= 0) {
 			r2 = this->lower->write_line(
-				this, *evict, ((index << LINE_SPEC) + (meta->at(0) << (this->size + LINE_SPEC))));
+				this, *evict, ((index << LINE_SPEC) + (meta->at(0) << (this->size - this->ways + LINE_SPEC))));
 			if (r2)
 				meta->at(1) = -1;
 		} else {
@@ -131,24 +138,18 @@ Cache::priming_address(int address)
 }
 
 int
-Cache::is_address_missing(int index, int tag)
+Cache::search_ways_for(int index, int tag)
 {
-	int i;
+	int i, r;
+
+	index = index * (1 << this->ways);
+	r = INT_MAX;
 
 	for (i = 0; i < (1 << this->ways); ++i)
 		if (this->meta.at(index + i).at(0) == tag)
-			return i;
-	return -1;
-}
-
-int
-Cache::get_true_index(int index)
-{
-	return index * (1 << this->ways);
-}
-
-int
-Cache::get_replacement_index(int index)
-{
-	return index + (rand() % (1 << this->ways));
+			return i + index;
+	for (i = 0; i < (1 << this->ways); ++i)
+		if (this->meta.at(index + i).at(2) < r)
+			r = i;
+	return r + index;
 }