mem: Make caches way aware

This patch makes cache sets aware of the way number. This enables
some nice features such as the ablity to restrict way allocation. The
implemented mechanism allows to set a maximum way number to be
allocated 'k' which must fulfill 0 < k <= N (where N is the number of
ways). In the future more sophisticated mechasims can be implemented.

9 files changed, 159 insertions, 16 deletions

diff --git a/src/mem/cache/blk.hh b/src/mem/cache/blk.hh
index f082a9ef0..0be22f45d 100644
--- a/src/mem/cache/blk.hh
+++ b/src/mem/cache/blk.hh
@@ -107,10 +107,10 @@ class CacheBlk
     Tick whenReady;
 
     /**
-     * The set this block belongs to.
+     * The set and way this block belongs to.
      * @todo Move this into subclasses when we fix CacheTags to use them.
      */
-    int set;
+    int set, way;
 
     /** whether this block has been touched */
     bool isTouched;
@@ -168,7 +168,7 @@ class CacheBlk
     CacheBlk()
         : task_id(ContextSwitchTaskId::Unknown),
           asid(-1), tag(0), data(0) ,size(0), status(0), whenReady(0),
-          set(-1), isTouched(false), refCount(0),
+          set(-1), way(-1), isTouched(false), refCount(0),
           srcMasterId(Request::invldMasterId),
           tickInserted(0)
     {}
diff --git a/src/mem/cache/cache_impl.hh b/src/mem/cache/cache_impl.hh
index 040b49464..4c602478f 100644
--- a/src/mem/cache/cache_impl.hh
+++ b/src/mem/cache/cache_impl.hh
@@ -1581,6 +1581,10 @@ Cache::allocateBlock(Addr addr, bool is_secure, PacketList &writebacks)
 {
     CacheBlk *blk = tags->findVictim(addr);
 
+    // It is valid to return NULL if there is no victim
+    if (!blk)
+        return nullptr;
+
     if (blk->isValid()) {
         Addr repl_addr = tags->regenerateBlkAddr(blk->tag, blk->set);
         MSHR *repl_mshr = mshrQueue.findMatch(repl_addr, blk->isSecure());
diff --git a/src/mem/cache/tags/base.hh b/src/mem/cache/tags/base.hh
index e4c0f68d8..05f51167e 100644
--- a/src/mem/cache/tags/base.hh
+++ b/src/mem/cache/tags/base.hh
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2012-2013 ARM Limited
+ * Copyright (c) 2012-2014 ARM Limited
  * All rights reserved.
  *
  * The license below extends only to copyright in the software and shall
@@ -196,6 +196,37 @@ class BaseTags : public ClockedObject
         return (addr & (Addr)(blkSize-1));
     }
 
+    /**
+     * Find the cache block given set and way
+     * @param set The set of the block.
+     * @param way The way of the block.
+     * @return The cache block.
+     */
+    virtual CacheBlk *findBlockBySetAndWay(int set, int way) const = 0;
+
+    /**
+     * Limit the allocation for the cache ways.
+     * @param ways The maximum number of ways available for replacement.
+     */
+    virtual void setWayAllocationMax(int ways)
+    {
+        panic("This tag class does not implement way allocation limit!\n");
+    }
+
+    /**
+     * Get the way allocation mask limit.
+     * @return The maximum number of ways available for replacement.
+     */
+    virtual int getWayAllocationMax() const
+    {
+        panic("This tag class does not implement way allocation limit!\n");
+        return -1;
+    }
+
+    virtual unsigned getNumSets() const = 0;
+
+    virtual unsigned getNumWays() const = 0;
+
     virtual void invalidate(CacheBlk *blk) = 0;
 
     virtual CacheBlk* accessBlock(Addr addr, bool is_secure, Cycles &lat,
diff --git a/src/mem/cache/tags/base_set_assoc.cc b/src/mem/cache/tags/base_set_assoc.cc
index c5ef9cc4b..8c48337bc 100644
--- a/src/mem/cache/tags/base_set_assoc.cc
+++ b/src/mem/cache/tags/base_set_assoc.cc
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2012-2013 ARM Limited
+ * Copyright (c) 2012-2014 ARM Limited
  * All rights reserved.
  *
  * The license below extends only to copyright in the software and shall
@@ -54,7 +54,7 @@
 using namespace std;
 
 BaseSetAssoc::BaseSetAssoc(const Params *p)
-    :BaseTags(p), assoc(p->assoc),
+    :BaseTags(p), assoc(p->assoc), allocAssoc(p->assoc),
      numSets(p->size / (p->block_size * p->assoc)),
      sequentialAccess(p->sequential_access)
 {
@@ -108,6 +108,7 @@ BaseSetAssoc::BaseSetAssoc(const Params *p)
             blk->size = blkSize;
             sets[i].blks[j]=blk;
             blk->set = i;
+            blk->way = j;
         }
     }
 }
@@ -128,6 +129,12 @@ BaseSetAssoc::findBlock(Addr addr, bool is_secure) const
     return blk;
 }
 
+CacheBlk*
+BaseSetAssoc::findBlockBySetAndWay(int set, int way) const
+{
+    return sets[set].blks[way];
+}
+
 void
 BaseSetAssoc::clearLocks()
 {
diff --git a/src/mem/cache/tags/base_set_assoc.hh b/src/mem/cache/tags/base_set_assoc.hh
index 79cfe756f..78c7489fe 100644
--- a/src/mem/cache/tags/base_set_assoc.hh
+++ b/src/mem/cache/tags/base_set_assoc.hh
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2012-2013 ARM Limited
+ * Copyright (c) 2012-2014 ARM Limited
  * All rights reserved.
  *
  * The license below extends only to copyright in the software and shall
@@ -87,6 +87,8 @@ class BaseSetAssoc : public BaseTags
   protected:
     /** The associativity of the cache. */
     const unsigned assoc;
+    /** The allocatable associativity of the cache (alloc mask). */
+    unsigned allocAssoc;
     /** The number of sets in the cache. */
     const unsigned numSets;
     /** Whether tags and data are accessed sequentially. */
@@ -146,6 +148,34 @@ public:
     }
 
     /**
+     * Return the number of sets this cache has
+     * @return The number of sets.
+     */
+    unsigned
+    getNumSets() const
+    {
+        return numSets;
+    }
+
+    /**
+     * Return the number of ways this cache has
+     * @return The number of ways.
+     */
+    unsigned
+    getNumWays() const
+    {
+        return assoc;
+    }
+
+    /**
+     * Find the cache block given set and way
+     * @param set The set of the block.
+     * @param way The way of the block.
+     * @return The cache block.
+     */
+    CacheBlk *findBlockBySetAndWay(int set, int way) const;
+
+    /**
      * Invalidate the given block.
      * @param blk The block to invalidate.
      */
@@ -183,13 +213,13 @@ public:
         // Access all tags in parallel, hence one in each way.  The data side
         // either accesses all blocks in parallel, or one block sequentially on
         // a hit.  Sequential access with a miss doesn't access data.
-        tagAccesses += assoc;
+        tagAccesses += allocAssoc;
         if (sequentialAccess) {
             if (blk != NULL) {
                 dataAccesses += 1;
             }
         } else {
-            dataAccesses += assoc;
+            dataAccesses += allocAssoc;
         }
 
         if (blk != NULL) {
@@ -227,11 +257,10 @@ public:
         int set = extractSet(addr);
 
         // prefer to evict an invalid block
-        for (int i = 0; i < assoc; ++i) {
+        for (int i = 0; i < allocAssoc; ++i) {
             blk = sets[set].blks[i];
-            if (!blk->isValid()) {
+            if (!blk->isValid())
                 break;
-            }
         }
 
         return blk;
@@ -292,6 +321,25 @@ public:
      }
 
     /**
+     * Limit the allocation for the cache ways.
+     * @param ways The maximum number of ways available for replacement.
+     */
+    virtual void setWayAllocationMax(int ways)
+    {
+        fatal_if(ways < 1, "Allocation limit must be greater than zero");
+        allocAssoc = ways;
+    }
+
+    /**
+     * Get the way allocation mask limit.
+     * @return The maximum number of ways available for replacement.
+     */
+    virtual int getWayAllocationMax() const
+    {
+        return allocAssoc;
+    }
+
+    /**
      * Generate the tag from the given address.
      * @param addr The address to get the tag from.
      * @return The tag of the address.
diff --git a/src/mem/cache/tags/fa_lru.cc b/src/mem/cache/tags/fa_lru.cc
index 8d4f75382..a53d25665 100644
--- a/src/mem/cache/tags/fa_lru.cc
+++ b/src/mem/cache/tags/fa_lru.cc
@@ -101,6 +101,8 @@ FALRU::FALRU(const Params *p)
         blks[i].prev = &(blks[i-1]);
         blks[i].next = &(blks[i+1]);
         blks[i].isTouched = false;
+        blks[i].set = 0;
+        blks[i].way = i;
     }
     assert(j == numCaches);
     assert(index == numBlocks);
@@ -227,6 +229,13 @@ FALRU::findBlock(Addr addr, bool is_secure) const
 }
 
 CacheBlk*
+FALRU::findBlockBySetAndWay(int set, int way) const
+{
+    assert(set == 0);
+    return &blks[way];
+}
+
+CacheBlk*
 FALRU::findVictim(Addr addr)
 {
     FALRUBlk * blk = tail;
diff --git a/src/mem/cache/tags/fa_lru.hh b/src/mem/cache/tags/fa_lru.hh
index fd183ab03..1c6bd2431 100644
--- a/src/mem/cache/tags/fa_lru.hh
+++ b/src/mem/cache/tags/fa_lru.hh
@@ -236,6 +236,34 @@ public:
     }
 
     /**
+     * Return the number of sets this cache has
+     * @return The number of sets.
+     */
+    unsigned
+    getNumSets() const
+    {
+        return 1;
+    }
+
+    /**
+     * Return the number of ways this cache has
+     * @return The number of ways.
+     */
+    unsigned
+    getNumWays() const
+    {
+        return numBlocks;
+    }
+
+    /**
+     * Find the cache block given set and way
+     * @param set The set of the block.
+     * @param way The way of the block.
+     * @return The cache block.
+     */
+    CacheBlk* findBlockBySetAndWay(int set, int way) const;
+
+    /**
      * Align an address to the block size.
      * @param addr the address to align.
      * @return The aligned address.
diff --git a/src/mem/cache/tags/lru.cc b/src/mem/cache/tags/lru.cc
index f3a286602..31423f994 100644
--- a/src/mem/cache/tags/lru.cc
+++ b/src/mem/cache/tags/lru.cc
@@ -75,9 +75,17 @@ LRU::findVictim(Addr addr)
 {
     int set = extractSet(addr);
     // grab a replacement candidate
-    BlkType *blk = sets[set].blks[assoc - 1];
+    BlkType *blk = NULL;
+    for (int i = assoc - 1; i >= 0; i--) {
+        BlkType *b = sets[set].blks[i];
+        if (b->way < allocAssoc) {
+            blk = b;
+            break;
+        }
+    }
+    assert(!blk || blk->way < allocAssoc);
 
-    if (blk->isValid()) {
+    if (blk && blk->isValid()) {
         DPRINTF(CacheRepl, "set %x: selecting blk %x for replacement\n",
                 set, regenerateBlkAddr(blk->tag, set));
     }
diff --git a/src/mem/cache/tags/random_repl.cc b/src/mem/cache/tags/random_repl.cc
index e7422a335..9f1ef800a 100644
--- a/src/mem/cache/tags/random_repl.cc
+++ b/src/mem/cache/tags/random_repl.cc
@@ -54,14 +54,22 @@ CacheBlk*
 RandomRepl::findVictim(Addr addr)
 {
     CacheBlk *blk = BaseSetAssoc::findVictim(addr);
+    unsigned set = extractSet(addr);
 
     // if all blocks are valid, pick a replacement at random
-    if (blk->isValid()) {
+    if (blk && blk->isValid()) {
         // find a random index within the bounds of the set
         int idx = random_mt.random<int>(0, assoc - 1);
+        blk = sets[set].blks[idx];
+        // Enforce allocation limit
+        while (blk->way >= allocAssoc) {
+            idx = (idx + 1) % assoc;
+            blk = sets[set].blks[idx];
+        }
+
         assert(idx < assoc);
         assert(idx >= 0);
-        blk = sets[extractSet(addr)].blks[idx];
+        assert(blk->way < allocAssoc);
 
         DPRINTF(CacheRepl, "set %x: selecting blk %x for replacement\n",
                 blk->set, regenerateBlkAddr(blk->tag, blk->set));