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 __MEM_CACHE_TAGS_FA_LRU_HH__
  37 #define __MEM_CACHE_TAGS_FA_LRU_HH__
  38
  39 #include <list>
  40
  41 #include "base/hashmap.hh"
  42 #include "mem/cache/tags/base.hh"
  43 #include "mem/cache/blk.hh"
  44 #include "mem/packet.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
  82   protected:
  83     /** The block size of the cache. */
  84     const unsigned blkSize;
  85     /** The size of the cache. */
  86     const unsigned size;
  87     /** The hit latency of the cache. */
  88     const unsigned hitLatency;
  89
  90     /** Array of pointers to blocks at the cache size  boundaries. */
  91     FALRUBlk **cacheBoundaries;
  92     /** A mask for the FALRUBlk::inCache bits. */
  93     int cacheMask;
  94     /** The number of different size caches being tracked. */
  95     unsigned numCaches;
  96
  97     /** The cache blocks. */
  98     FALRUBlk *blks;
  99
 100     /** The MRU block. */
 101     FALRUBlk *head;
 102     /** The LRU block. */
 103     FALRUBlk *tail;
 104
 105     /** Hash table type mapping addresses to cache block pointers. */
 106     typedef m5::hash_map<Addr, FALRUBlk *, m5::hash<Addr> > hash_t;
 107     /** Iterator into the address hash table. */
 108     typedef hash_t::const_iterator tagIterator;
 109
 110     /** The address hash table. */
 111     hash_t tagHash;
 112
 113     /**
 114      * Find the cache block for the given address.
 115      * @param addr The address to find.
 116      * @return The cache block of the address, if any.
 117      */
 118     FALRUBlk * hashLookup(Addr addr) const;
 119
 120     /**
 121      * Move a cache block to the MRU position.
 122      * @param blk The block to promote.
 123      */
 124     void moveToHead(FALRUBlk *blk);
 125
 126     /**
 127      * Check to make sure all the cache boundaries are still where they should
 128      * be. Used for debugging.
 129      * @return True if everything is correct.
 130      */
 131     bool check();
 132
 133     /**
 134      * @defgroup FALRUStats Fully Associative LRU specific statistics
 135      * The FA lru stack lets us track multiple cache sizes at once. These
 136      * statistics track the hits and misses for different cache sizes.
 137      * @{
 138      */
 139
 140     /** Hits in each cache size >= 128K. */
 141     Stats::Vector hits;
 142     /** Misses in each cache size >= 128K. */
 143     Stats::Vector misses;
 144     /** Total number of accesses. */
 145     Stats::Scalar accesses;
 146
 147     /**
 148      * @}
 149      */
 150
 151 public:
 152     /**
 153      * Construct and initialize this cache tagstore.
 154      * @param blkSize The block size of the cache.
 155      * @param size The size of the cache.
 156      * @param hit_latency The hit latency of the cache.
 157      */
 158     FALRU(unsigned blkSize, unsigned size, unsigned hit_latency);
 159
 160     /**
 161      * Register the stats for this object.
 162      * @param name The name to prepend to the stats name.
 163      */
 164     void regStats(const std::string &name);
 165
 166     /**
 167      * Invalidate a cache block.
 168      * @param blk The block to invalidate.
 169      */
 170     void invalidateBlk(BlkType *blk);
 171
 172     /**
 173      * Access block and update replacement data.  May not succeed, in which case
 174      * NULL pointer is returned.  This has all the implications of a cache
 175      * access and should only be used as such.
 176      * Returns the access latency and inCache flags as a side effect.
 177      * @param addr The address to look for.
 178      * @param asid The address space ID.
 179      * @param lat The latency of the access.
 180      * @param inCache The FALRUBlk::inCache flags.
 181      * @return Pointer to the cache block.
 182      */
 183     FALRUBlk* accessBlock(Addr addr, int &lat, int context_src, int *inCache = 0);
 184
 185     /**
 186      * Find the block in the cache, do not update the replacement data.
 187      * @param addr The address to look for.
 188      * @param asid The address space ID.
 189      * @return Pointer to the cache block.
 190      */
 191     FALRUBlk* findBlock(Addr addr) const;
 192
 193     /**
 194      * Find a replacement block for the address provided.
 195      * @param pkt The request to a find a replacement candidate for.
 196      * @param writebacks List for any writebacks to be performed.
 197      * @return The block to place the replacement in.
 198      */
 199     FALRUBlk* findVictim(Addr addr, PacketList & writebacks);
 200
 201     void insertBlock(Addr addr, BlkType *blk, int context_src);
 202
 203     /**
 204      * Return the hit latency of this cache.
 205      * @return The hit latency.
 206      */
 207     int getHitLatency() const
 208     {
 209         return hitLatency;
 210     }
 211
 212     /**
 213      * Return the block size of this cache.
 214      * @return The block size.
 215      */
 216     unsigned
 217     getBlockSize() const
 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     unsigned
 227     getSubBlockSize() const
 228     {
 229         return blkSize;
 230     }
 231
 232     /**
 233      * Align an address to the block size.
 234      * @param addr the address to align.
 235      * @return The aligned address.
 236      */
 237     Addr blkAlign(Addr addr) const
 238     {
 239         return (addr & ~(Addr)(blkSize-1));
 240     }
 241
 242     /**
 243      * Generate the tag from the addres. For fully associative this is just the
 244      * block address.
 245      * @param addr The address to get the tag from.
 246      * @return The tag.
 247      */
 248     Addr extractTag(Addr addr) const
 249     {
 250         return blkAlign(addr);
 251     }
 252
 253     /**
 254      * Return the set of an address. Only one set in a fully associative cache.
 255      * @param addr The address to get the set from.
 256      * @return 0.
 257      */
 258     int extractSet(Addr addr) const
 259     {
 260         return 0;
 261     }
 262
 263     /**
 264      * Calculate the block offset of an address.
 265      * @param addr the address to get the offset of.
 266      * @return the block offset.
 267      */
 268     int extractBlkOffset(Addr addr) const
 269     {
 270         return (addr & (Addr)(blkSize-1));
 271     }
 272
 273     /**
 274      * Regenerate the block address from the tag and the set.
 275      * @param tag The tag of the block.
 276      * @param set The set the block belongs to.
 277      * @return the block address.
 278      */
 279     Addr regenerateBlkAddr(Addr tag, int set) const
 280     {
 281         return (tag);
 282     }
 283
 284     /**
 285      *iterated through all blocks and clear all locks
 286      *Needed to clear all lock tracking at once
 287      */
 288     virtual void clearLocks();
 289 };
 290
 291 #endif // __MEM_CACHE_TAGS_FA_LRU_HH__