mem-cache: Add MoveToTail to FALRU

FALRU was missing MoveToTail functionality within its invalidate
function, and MoveToHead was doing unnecessary passes when the
moved block was the head already.

Besides, added some comments to make the code understandable.

Change-Id: I2430d82b5d53c88b102a62610ea38b46d6e03a55
Reviewed-on: https://gem5-review.googlesource.com/9541
Reviewed-by: Nikos Nikoleris <nikos.nikoleris@arm.com>
Maintainer: Nikos Nikoleris <nikos.nikoleris@arm.com>

2 files changed, 82 insertions, 12 deletions

diff --git a/src/mem/cache/tags/fa_lru.cc b/src/mem/cache/tags/fa_lru.cc
index f02b55a8d..b75497ea2 100644
--- a/src/mem/cache/tags/fa_lru.cc
+++ b/src/mem/cache/tags/fa_lru.cc
@@ -64,7 +64,7 @@ FALRU::FALRU(const Params *p)
 
     // Track all cache sizes from 128K up by powers of 2
     numCaches = floorLog2(size) - 17;
-    if (numCaches >0){
+    if (numCaches > 0){
         cacheBoundaries = new FALRUBlk *[numCaches];
         cacheMask = (ULL(1) << numCaches) - 1;
     } else {
@@ -164,9 +164,11 @@ FALRU::hashLookup(Addr addr) const
 void
 FALRU::invalidate(CacheBlk *blk)
 {
-    // TODO: We need to move the block to the tail to make it the next victim
     BaseTags::invalidate(blk);
 
+    // Move the block to the tail to make it the next victim
+    moveToTail((FALRUBlk*)blk);
+
     // Erase block entry in the hash table
     tagHash.erase(blk->tag);
 }
@@ -276,25 +278,41 @@ FALRU::insertBlock(PacketPtr pkt, CacheBlk *blk)
 void
 FALRU::moveToHead(FALRUBlk *blk)
 {
-    int updateMask = blk->inCache ^ cacheMask;
-    for (unsigned i = 0; i < numCaches; i++){
-        if ((1<<i) & updateMask) {
-            cacheBoundaries[i]->inCache &= ~(1<<i);
-            cacheBoundaries[i] = cacheBoundaries[i]->prev;
-        } else if (cacheBoundaries[i] == blk) {
-            cacheBoundaries[i] = blk->prev;
-        }
-    }
-    blk->inCache = cacheMask;
+    // If block is not already head, do the moving
     if (blk != head) {
+        // Get all caches that this block does not reside in
+        int updateMask = blk->inCache ^ cacheMask;
+
+        // Update boundaries for all cache sizes
+        for (unsigned i = 0; i < numCaches; i++){
+            // If block has been moved to a place before this boundary,
+            // all blocks in it will be pushed towards the LRU position,
+            // making one leave the boundary
+            if ((1U<<i) & updateMask) {
+                cacheBoundaries[i]->inCache &= ~(1U<<i);
+                cacheBoundaries[i] = cacheBoundaries[i]->prev;
+            // If the block resides exactly at this boundary, the previous
+            // block is pushed to its position
+            } else if (cacheBoundaries[i] == blk) {
+                cacheBoundaries[i] = blk->prev;
+            }
+        }
+
+        // Make block reside in all caches
+        blk->inCache = cacheMask;
+
+        // If block is tail, set previous block as new tail
         if (blk == tail){
             assert(blk->next == nullptr);
             tail = blk->prev;
             tail->next = nullptr;
+        // Inform block's surrounding blocks that it has been moved
         } else {
             blk->prev->next = blk->next;
             blk->next->prev = blk->prev;
         }
+
+        // Swap pointers
         blk->next = head;
         blk->prev = nullptr;
         head->prev = blk;
@@ -302,6 +320,50 @@ FALRU::moveToHead(FALRUBlk *blk)
     }
 }
 
+void
+FALRU::moveToTail(FALRUBlk *blk)
+{
+    // If block is not already tail, do the moving
+    if (blk != tail) {
+        // Update boundaries for all cache sizes
+        for (unsigned i = 0; i < numCaches; i++){
+            // If block has been moved to a place after this boundary,
+            // all blocks in it will be pushed towards the MRU position,
+            // making one enter the boundary
+            if ((1U<<i) & blk->inCache) {
+                // If the first block after the boundary is the block,
+                // get its successor
+                if (cacheBoundaries[i]->next == blk){
+                    cacheBoundaries[i] = cacheBoundaries[i]->next->next;
+                } else {
+                    cacheBoundaries[i] = cacheBoundaries[i]->next;
+                }
+                cacheBoundaries[i]->inCache |= (1U<<i);
+            }
+        }
+
+        // Make block reside in the last cache only
+        blk->inCache = 0;
+
+        // If block is head, set next block as new head
+        if (blk == head){
+            assert(blk->prev == nullptr);
+            head = blk->next;
+            head->prev = nullptr;
+        // Inform block's surrounding blocks that it has been moved
+        } else {
+            blk->prev->next = blk->next;
+            blk->next->prev = blk->prev;
+        }
+
+        // Swap pointers
+        blk->prev = tail;
+        blk->next = nullptr;
+        tail->next = blk;
+        tail = blk;
+    }
+}
+
 bool
 FALRU::check()
 {
diff --git a/src/mem/cache/tags/fa_lru.hh b/src/mem/cache/tags/fa_lru.hh
index 129af9f37..73d66604f 100644
--- a/src/mem/cache/tags/fa_lru.hh
+++ b/src/mem/cache/tags/fa_lru.hh
@@ -122,11 +122,19 @@ class FALRU : public BaseTags
 
     /**
      * Move a cache block to the MRU position.
+     *
      * @param blk The block to promote.
      */
     void moveToHead(FALRUBlk *blk);
 
     /**
+     * Move a cache block to the LRU position.
+     *
+     * @param blk The block to demote.
+     */
+    void moveToTail(FALRUBlk *blk);
+
+    /**
      * Check to make sure all the cache boundaries are still where they should
      * be. Used for debugging.
      * @return True if everything is correct.