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.