src/mem/cache/tags/fa_lru.hh

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