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