mem-cache: Revamp multiple size tracking for FALRU caches

This change fixes a few bugs and refactors the mechanism by which
caches that use the FALRU tags can output statistics for multiple
cache sizes ranging from the minimum cache of interest up to the
actual configured cache size.

Change-Id: Ibea029cf275a8c068c26eceeb06c761fc53aede2
Reviewed-on: https://gem5-review.googlesource.com/9826
Reviewed-by: Daniel Carvalho <odanrc@yahoo.com.br>
Maintainer: Nikos Nikoleris <nikos.nikoleris@arm.com>

1 files changed, 142 insertions, 46 deletions

diff --git a/src/mem/cache/tags/fa_lru.hh b/src/mem/cache/tags/fa_lru.hh
index 73d66604f..bec98e3a7 100644
--- a/src/mem/cache/tags/fa_lru.hh
+++ b/src/mem/cache/tags/fa_lru.hh
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2012-2013,2016 ARM Limited
+ * Copyright (c) 2012-2013,2016,2018 ARM Limited
  * All rights reserved.
  *
  * The license below extends only to copyright in the software and shall
@@ -38,6 +38,7 @@
  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  *
  * Authors: Erik Hallnor
+ *          Nikos Nikoleris
  */
 
 /**
@@ -51,12 +52,23 @@
 #include <list>
 #include <unordered_map>
 
+#include "base/intmath.hh"
 #include "mem/cache/base.hh"
 #include "mem/cache/blk.hh"
 #include "mem/cache/tags/base.hh"
 #include "mem/packet.hh"
 #include "params/FALRU.hh"
 
+// Uncomment to enable sanity checks for the FALRU cache and the
+// TrackedCaches class
+//#define FALRU_DEBUG
+
+// A bitmask of the caches we are keeping track of. Currently the
+// lowest bit is the smallest cache we are tracking, as it is
+// specified by the corresponding parameter. The rest of the bits are
+// for exponentially growing cache sizes.
+typedef uint32_t CachesMask;
+
 /**
  * A fully associative cache block.
  */
@@ -68,15 +80,8 @@ class FALRUBlk : public CacheBlk
     /** The next block in LRU order. */
     FALRUBlk *next;
 
-    /**
-     * A bit mask of the sizes of cache that this block is resident in.
-     * Each bit represents a power of 2 in MB size cache.
-     * If bit 0 is set, this block is in a 1MB cache
-     * If bit 2 is set, this block is in a 4MB cache, etc.
-     * There is one bit for each cache smaller than the full size (default
-     * 16MB).
-     */
-    int inCache;
+    /** A bit mask of the caches that fit this block. */
+    CachesMask inCachesMask;
 };
 
 /**
@@ -90,13 +95,6 @@ class FALRU : public BaseTags
     typedef FALRUBlk BlkType;
 
   protected:
-    /** Array of pointers to blocks at the cache size  boundaries. */
-    FALRUBlk **cacheBoundaries;
-    /** A mask for the FALRUBlk::inCache bits. */
-    int cacheMask;
-    /** The number of different size caches being tracked. */
-    unsigned numCaches;
-
     /** The cache blocks. */
     FALRUBlk *blks;
 
@@ -134,31 +132,6 @@ class FALRU : public BaseTags
      */
     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.
-     */
-    bool check();
-
-    /**
-     * @defgroup FALRUStats Fully Associative LRU specific statistics
-     * The FA lru stack lets us track multiple cache sizes at once. These
-     * statistics track the hits and misses for different cache sizes.
-     * @{
-     */
-
-    /** Hits in each cache size >= 128K. */
-    Stats::Vector hits;
-    /** Misses in each cache size >= 128K. */
-    Stats::Vector misses;
-    /** Total number of accesses. */
-    Stats::Scalar accesses;
-
-    /**
-     * @}
-     */
-
   public:
     typedef FALRUParams Params;
 
@@ -170,7 +143,6 @@ class FALRU : public BaseTags
 
     /**
      * Register the stats for this object.
-     * @param name The name to prepend to the stats name.
      */
     void regStats() override;
 
@@ -184,15 +156,15 @@ class FALRU : public BaseTags
      * Access block and update replacement data.  May not succeed, in which
      * case nullptr pointer is returned.  This has all the implications of a
      * cache access and should only be used as such.
-     * Returns the access latency and inCache flags as a side effect.
+     * Returns the access latency and inCachesMask flags as a side effect.
      * @param addr The address to look for.
      * @param is_secure True if the target memory space is secure.
      * @param lat The latency of the access.
-     * @param inCache The FALRUBlk::inCache flags.
+     * @param in_cache_mask Mask indicating the caches in which the blk fits.
      * @return Pointer to the cache block.
      */
     CacheBlk* accessBlock(Addr addr, bool is_secure, Cycles &lat,
-                          int *inCache);
+                          CachesMask *in_cache_mask);
 
     /**
      * Just a wrapper of above function to conform with the base interface.
@@ -287,6 +259,130 @@ class FALRU : public BaseTags
                 return;
         }
     }
+
+  private:
+    /**
+     * Mechanism that allows us to simultaneously collect miss
+     * statistics for multiple caches. Currently, we keep track of
+     * caches from a set minimum size of interest up to the actual
+     * cache size.
+     */
+    class CacheTracking
+    {
+      public:
+        CacheTracking(unsigned min_size, unsigned max_size,
+                      unsigned block_size)
+            : blkSize(block_size),
+              minTrackedSize(min_size),
+              numTrackedCaches(max_size > min_size ?
+                               floorLog2(max_size) - floorLog2(min_size) : 0),
+              inAllCachesMask(mask(numTrackedCaches)),
+              boundaries(new FALRUBlk *[numTrackedCaches])
+        {
+            fatal_if(numTrackedCaches > sizeof(CachesMask) * 8,
+                     "Not enough bits (%s) in type CachesMask type to keep "
+                     "track of %d caches\n", sizeof(CachesMask),
+                     numTrackedCaches);
+        }
+
+        ~CacheTracking()
+        {
+            delete[] boundaries;
+        }
+
+        /**
+         * Initialiaze cache blocks and the tracking mechanism
+         *
+         * All blocks in the cache need to be initialized once.
+         *
+         * @param blk the MRU block
+         * @param blk the LRU block
+         */
+        void init(FALRUBlk *head, FALRUBlk *tail);
+
+        /**
+         * Update boundaries as a block will be moved to the MRU.
+         *
+         * For all caches that didn't fit the block before moving it,
+         * we move their boundaries one block closer to the MRU. We
+         * also update InCacheMasks as neccessary.
+         *
+         * @param blk the block that will be moved to the head
+         */
+        void moveBlockToHead(FALRUBlk *blk);
+
+        /**
+         * Update boundaries as a block will be moved to the LRU.
+         *
+         * For all caches that fitted the block before moving it, we
+         * move their boundaries one block closer to the LRU. We
+         * also update InCacheMasks as neccessary.
+         *
+         * @param blk the block that will be moved to the head
+         */
+        void moveBlockToTail(FALRUBlk *blk);
+
+        /**
+         * Notify of a block access.
+         *
+         * This should be called every time a block is accessed and it
+         * updates statistics. If the input block is nullptr then we
+         * treat the access as a miss. The block's InCacheMask
+         * determines the caches in which the block fits.
+         *
+         * @param blk the block to record the access for
+         */
+        void recordAccess(FALRUBlk *blk);
+
+        /**
+         * Check that the tracking mechanism is in consistent state.
+         *
+         * Iterate from the head (MRU) to the tail (LRU) of the list
+         * of blocks and assert the inCachesMask and the boundaries
+         * are in consistent state.
+         *
+         * @param head the MRU block of the actual cache
+         * @param head the LRU block of the actual cache
+         */
+        void check(FALRUBlk *head, FALRUBlk *tail);
+
+        /**
+         * Register the stats for this object.
+         */
+        void regStats(std::string name);
+
+      private:
+        /** The size of the cache block */
+        const unsigned blkSize;
+        /** The smallest cache we are tracking */
+        const unsigned minTrackedSize;
+        /** The number of different size caches being tracked. */
+        const int numTrackedCaches;
+        /** A mask for all cache being tracked. */
+        const CachesMask inAllCachesMask;
+        /** Array of pointers to blocks at the cache boundaries. */
+        FALRUBlk** boundaries;
+
+      protected:
+        /**
+         * @defgroup FALRUStats Fully Associative LRU specific statistics
+         * The FA lru stack lets us track multiple cache sizes at once. These
+         * statistics track the hits and misses for different cache sizes.
+         * @{
+         */
+
+        /** Hits in each cache */
+        Stats::Vector hits;
+        /** Misses in each cache */
+        Stats::Vector misses;
+        /** Total number of accesses */
+        Stats::Scalar accesses;
+
+        /**
+         * @}
+         */
+    };
+    CacheTracking cacheTracking;
 };
 
 #endif // __MEM_CACHE_TAGS_FA_LRU_HH__