src/mem/cache/tags/fa_lru.hh

   1 /*
   2  * Copyright (c) 2003-2005 The Regents of The University of Michigan
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions are
   7  * met: redistributions of source code must retain the above copyright
   8  * notice, this list of conditions and the following disclaimer;
   9  * redistributions in binary form must reproduce the above copyright
  10  * notice, this list of conditions and the following disclaimer in the
  11  * documentation and/or other materials provided with the distribution;
  12  * neither the name of the copyright holders nor the names of its
  13  * contributors may be used to endorse or promote products derived from
  14  * this software without specific prior written permission.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  19  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  20  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  26  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  *
  28  * Authors: Erik Hallnor
  29  */
  30
  31 /**
  32  * @file
  33  * Declaration of a fully associative LRU tag store.
  34  */
  35
  36 #ifndef __FA_LRU_HH__
  37 #define __FA_LRU_HH__
  38
  39 #include <list>
  40
  41 #include "mem/cache/blk.hh"
  42 #include "mem/packet.hh"
  43 #include "base/hashmap.hh"
  44 #include "mem/cache/tags/base.hh"
  45
  46 /**
  47  * A fully associative cache block.
  48  */
  49 class FALRUBlk : public CacheBlk
  50 {
  51 public:
  52     /** The previous block in LRU order. */
  53     FALRUBlk *prev;
  54     /** The next block in LRU order. */
  55     FALRUBlk *next;
  56     /** Has this block been touched? */
  57     bool isTouched;
  58
  59     /**
  60      * A bit mask of the sizes of cache that this block is resident in.
  61      * Each bit represents a power of 2 in MB size cache.
  62      * If bit 0 is set, this block is in a 1MB cache
  63      * If bit 2 is set, this block is in a 4MB cache, etc.
  64      * There is one bit for each cache smaller than the full size (default
  65      * 16MB).
  66      */
  67     int inCache;
  68 };
  69
  70 /**
  71  * A fully associative LRU cache. Keeps statistics for accesses to a number of
  72  * cache sizes at once.
  73  */
  74 class FALRU : public BaseTags
  75 {
  76   public:
  77     /** Typedef the block type used in this class. */
  78     typedef FALRUBlk BlkType;
  79     /** Typedef a list of pointers to the local block type. */
  80     typedef std::list<FALRUBlk*> BlkList;
  81   protected:
  82     /** The block size of the cache. */
  83     const int blkSize;
  84     /** The size of the cache. */
  85     const int size;
  86     /** The number of blocks in the cache. */
  87     const int numBlks; // calculated internally
  88     /** The hit latency of the cache. */
  89     const int hitLatency;
  90
  91     /** Array of pointers to blocks at the cache size  boundaries. */
  92     FALRUBlk **cacheBoundaries;
  93     /** A mask for the FALRUBlk::inCache bits. */
  94     int cacheMask;
  95     /** The number of different size caches being tracked. */
  96     int numCaches;
  97
  98     /** The cache blocks. */
  99     FALRUBlk *blks;
 100
 101     /** The MRU block. */
 102     FALRUBlk *head;
 103     /** The LRU block. */
 104     FALRUBlk *tail;
 105
 106     /** Hash table type mapping addresses to cache block pointers. */
 107     typedef m5::hash_map<Addr, FALRUBlk *, m5::hash<Addr> > hash_t;
 108     /** Iterator into the address hash table. */
 109     typedef hash_t::const_iterator tagIterator;
 110
 111     /** The address hash table. */
 112     hash_t tagHash;
 113
 114     /**
 115      * Find the cache block for the given address.
 116      * @param addr The address to find.
 117      * @return The cache block of the address, if any.
 118      */
 119     FALRUBlk * hashLookup(Addr addr) const;
 120
 121     /**
 122      * Move a cache block to the MRU position.
 123      * @param blk The block to promote.
 124      */
 125     void moveToHead(FALRUBlk *blk);
 126
 127     /**
 128      * Check to make sure all the cache boundaries are still where they should
 129      * be. Used for debugging.
 130      * @return True if everything is correct.
 131      */
 132     bool check();
 133
 134     /**
 135      * @defgroup FALRUStats Fully Associative LRU specific statistics
 136      * The FA lru stack lets us track multiple cache sizes at once. These
 137      * statistics track the hits and misses for different cache sizes.
 138      * @{
 139      */
 140
 141     /** Hits in each cache size >= 128K. */
 142     Stats::Vector hits;
 143     /** Misses in each cache size >= 128K. */
 144     Stats::Vector misses;
 145     /** Total number of accesses. */
 146     Stats::Scalar accesses;
 147
 148     /**
 149      * @}
 150      */
 151
 152 public:
 153     /**
 154      * Construct and initialize this cache tagstore.
 155      * @param blkSize The block size of the cache.
 156      * @param size The size of the cache.
 157      * @param hit_latency The hit latency of the cache.
 158      */
 159     FALRU(int blkSize, int size, int hit_latency);
 160
 161     /**
 162      * Register the stats for this object.
 163      * @param name The name to prepend to the stats name.
 164      */
 165     void regStats(const std::string &name);
 166
 167     /**
 168      * Invalidate a cache block.
 169      * @param blk The block to invalidate.
 170      */
 171     void invalidateBlk(BlkType *blk);
 172
 173     /**
 174      * Access block and update replacement data.  May not succeed, in which case
 175      * NULL pointer is returned.  This has all the implications of a cache
 176      * access and should only be used as such.
 177      * Returns the access latency and inCache flags as a side effect.
 178      * @param addr The address to look for.
 179      * @param asid The address space ID.
 180      * @param lat The latency of the access.
 181      * @param inCache The FALRUBlk::inCache flags.
 182      * @return Pointer to the cache block.
 183      */
 184     FALRUBlk* accessBlock(Addr addr, int &lat, int *inCache = 0);
 185
 186     /**
 187      * Find the block in the cache, do not update the replacement data.
 188      * @param addr The address to look for.
 189      * @param asid The address space ID.
 190      * @return Pointer to the cache block.
 191      */
 192     FALRUBlk* findBlock(Addr addr) const;
 193
 194     /**
 195      * Find a replacement block for the address provided.
 196      * @param pkt The request to a find a replacement candidate for.
 197      * @param writebacks List for any writebacks to be performed.
 198      * @return The block to place the replacement in.
 199      */
 200     FALRUBlk* findVictim(Addr addr, PacketList & writebacks);
 201
 202     void insertBlock(Addr addr, BlkType *blk);
 203
 204     /**
 205      * Return the hit latency of this cache.
 206      * @return The hit latency.
 207      */
 208     int getHitLatency() const
 209     {
 210         return hitLatency;
 211     }
 212
 213     /**
 214      * Return the block size of this cache.
 215      * @return The block size.
 216      */
 217     int getBlockSize()
 218     {
 219         return blkSize;
 220     }
 221
 222     /**
 223      * Return the subblock size of this cache, always the block size.
 224      * @return The block size.
 225      */
 226     int getSubBlockSize()
 227     {
 228         return blkSize;
 229     }
 230
 231     /**
 232      * Align an address to the block size.
 233      * @param addr the address to align.
 234      * @return The aligned address.
 235      */
 236     Addr blkAlign(Addr addr) const
 237     {
 238         return (addr & ~(Addr)(blkSize-1));
 239     }
 240
 241     /**
 242      * Generate the tag from the addres. For fully associative this is just the
 243      * block address.
 244      * @param addr The address to get the tag from.
 245      * @return The tag.
 246      */
 247     Addr extractTag(Addr addr) const
 248     {
 249         return blkAlign(addr);
 250     }
 251
 252     /**
 253      * Return the set of an address. Only one set in a fully associative cache.
 254      * @param addr The address to get the set from.
 255      * @return 0.
 256      */
 257     int extractSet(Addr addr) const
 258     {
 259         return 0;
 260     }
 261
 262     /**
 263      * Calculate the block offset of an address.
 264      * @param addr the address to get the offset of.
 265      * @return the block offset.
 266      */
 267     int extractBlkOffset(Addr addr) const
 268     {
 269         return (addr & (Addr)(blkSize-1));
 270     }
 271
 272     /**
 273      * Regenerate the block address from the tag and the set.
 274      * @param tag The tag of the block.
 275      * @param set The set the block belongs to.
 276      * @return the block address.
 277      */
 278     Addr regenerateBlkAddr(Addr tag, int set) const
 279     {
 280         return (tag);
 281     }
 282 };
 283
 284 #endif