src/mem/cache/tags/iic.hh

   1 /*
   2  * Copyright (c) 2002-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 the Indirect Index Cache (IIC) tags store.
  34  */
  35
  36 #ifndef __IIC_HH__
  37 #define __IIC_HH__
  38
  39 #include <list>
  40 #include <vector>
  41
  42 #include "base/statistics.hh"
  43 #include "mem/cache/tags/iic_repl/repl.hh"
  44 #include "mem/cache/tags/base.hh"
  45 #include "mem/cache/blk.hh"
  46 #include "mem/packet.hh"
  47
  48 class BaseCache; // Forward declaration
  49
  50 /**
  51  * IIC cache blk.
  52  */
  53 class IICTag : public CacheBlk
  54 {
  55   public:
  56     /**
  57      * Copy the contents of the given IICTag into this one.
  58      * @param rhs The tag to copy.
  59      * @return const reference to this tag.
  60      */
  61     const IICTag& operator=(const IICTag& rhs)
  62     {
  63         CacheBlk::operator=(rhs);
  64         chain_ptr = rhs.chain_ptr;
  65         re = rhs.re;
  66         set = rhs.set;
  67         trivialData = rhs.trivialData;
  68         numData = rhs.numData;
  69         data_ptr.clear();
  70         for (int i = 0; i < rhs.numData; ++i) {
  71             data_ptr.push_back(rhs.data_ptr[i]);
  72         }
  73         return *this;
  74     }
  75
  76     /** Hash chain pointer into secondary store. */
  77     unsigned long chain_ptr;
  78     /** Data array pointers for each subblock. */
  79     std::vector<unsigned long> data_ptr;
  80     /** Replacement Entry pointer. */
  81     void *re;
  82     /**
  83      * An array to store small compressed data. Conceputally the same size
  84      * as the unsused data array pointers.
  85      */
  86     uint8_t *trivialData;
  87     /**
  88      * The number of allocated subblocks.
  89      */
  90     int numData;
  91 };
  92
  93 /**
  94  * A hash set for the IIC primary lookup table.
  95  */
  96 class IICSet{
  97   public:
  98     /** The associativity of the primary table. */
  99     int assoc;
 100
 101     /** The number of hash chains followed when finding the last block. */
 102     int depth;
 103     /** The current number of blocks on the chain. */
 104     int size;
 105
 106     /** Tag pointer into the secondary tag storage. */
 107     unsigned long chain_ptr;
 108
 109     /** The LRU list of the primary table. MRU is at 0 index. */
 110     IICTag ** tags;
 111
 112     /**
 113      * Find the addr in this set, return the chain pointer to the secondary if
 114      * it isn't found.
 115      * @param asid The address space ID.
 116      * @param tag The address to find.
 117      * @param chain_ptr The chain pointer to start the search of the secondary
 118      * @return Pointer to the tag, NULL if not found.
 119      */
 120     IICTag* findTag( Addr tag, unsigned long &chain_ptr)
 121     {
 122         depth = 1;
 123         for (int i = 0; i < assoc; ++i) {
 124             if (tags[i]->tag == tag && tags[i]->isValid()) {
 125                 return tags[i];
 126             }
 127         }
 128         chain_ptr = this->chain_ptr;
 129         return 0;
 130     }
 131
 132     /**
 133      * Find an usused tag in this set.
 134      * @return Pointer to the unused tag, NULL if none are free.
 135      */
 136     IICTag* findFree()
 137     {
 138         for (int i = 0; i < assoc; ++i) {
 139             if (!tags[i]->isValid()) {
 140                 return tags[i];
 141             }
 142         }
 143         return 0;
 144     }
 145
 146     /**
 147      * Move a tag to the head of the LRU list
 148      * @param tag The tag to move.
 149      */
 150     void moveToHead(IICTag *tag);
 151
 152     /**
 153      * Move a tag to the tail (LRU) of the LRU list
 154      * @param tag The tag to move.
 155      */
 156     void moveToTail(IICTag *tag);
 157 };
 158
 159 /**
 160  * The IIC tag store. This is a hardware-realizable, fully-associative tag
 161  * store that uses software replacement, e.g. Gen.
 162  */
 163 class IIC : public BaseTags
 164 {
 165   public:
 166     /** Typedef of the block type used in this class. */
 167     typedef IICTag BlkType;
 168     /** Typedef for list of pointers to the local block type. */
 169     typedef std::list<IICTag*> BlkList;
 170
 171   protected:
 172     /** The number of set in the primary table. */
 173     const unsigned hashSets;
 174     /** The block size in bytes. */
 175     const unsigned blkSize;
 176     /** The associativity of the primary table. */
 177     const unsigned assoc;
 178     /** The base hit latency. */
 179     const unsigned hitLatency;
 180     /** The subblock size, used for compression. */
 181     const unsigned subSize;
 182
 183     /** The number of subblocks */
 184     const unsigned numSub;
 185     /** The number of bytes used by data pointers */
 186     const unsigned trivialSize;
 187
 188     /** The amount to shift address to get the tag. */
 189     const unsigned tagShift;
 190     /** The mask to get block offset bits. */
 191     const unsigned blkMask;
 192
 193     /** The amount to shift to get the subblock number. */
 194     const unsigned subShift;
 195     /** The mask to get the correct subblock number. */
 196     const unsigned subMask;
 197
 198     /** The latency of a hash lookup. */
 199     const unsigned hashDelay;
 200     /** The total number of tags in primary and secondary. */
 201     const unsigned numTags;
 202     /** The number of tags in the secondary tag store. */
 203     const unsigned numSecondary;
 204
 205     /** The Null tag pointer. */
 206     const unsigned tagNull;
 207     /** The last tag in the primary table. */
 208     const unsigned primaryBound;
 209
 210     /** All of the tags */
 211     IICTag *tagStore;
 212     /**
 213      * Pointer to the head of the secondary freelist (maintained with chain
 214      * pointers.
 215      */
 216     unsigned long freelist;
 217     /**
 218      * The data block freelist.
 219      */
 220     std::list<unsigned long> blkFreelist;
 221
 222     /** The primary table. */
 223     IICSet *sets;
 224
 225     /** The replacement policy. */
 226     Repl *repl;
 227
 228     /** An array of data reference counters. */
 229     int *dataReferenceCount;
 230
 231     /** The data blocks. */
 232     uint8_t *dataStore;
 233
 234     /** Storage for the fast access data of each cache block. */
 235     uint8_t **dataBlks;
 236
 237     /**
 238      * Count of the current number of free secondary tags.
 239      * Used for debugging.
 240      */
 241     int freeSecond;
 242
 243     // IIC Statistics
 244     /**
 245      * @addtogroup IICStatistics IIC Statistics
 246      * @{
 247      */
 248
 249     /** Hash hit depth of cache hits. */
 250     Stats::Distribution hitHashDepth;
 251     /** Hash depth for cache misses. */
 252     Stats::Distribution missHashDepth;
 253     /** Count of accesses to each hash set. */
 254     Stats::Distribution setAccess;
 255
 256     /** The total hash depth for every miss. */
 257     Stats::Scalar missDepthTotal;
 258     /** The total hash depth for all hits. */
 259     Stats::Scalar hitDepthTotal;
 260     /** The number of hash misses. */
 261     Stats::Scalar hashMiss;
 262     /** The number of hash hits. */
 263     Stats::Scalar hashHit;
 264     /** @} */
 265
 266   public:
 267     /**
 268      * Collection of parameters for the IIC.
 269      */
 270     class Params {
 271       public:
 272         /** The size in bytes of the cache. */
 273         unsigned size;
 274         /** The number of sets in the primary table. */
 275         unsigned numSets;
 276         /** The block size in bytes. */
 277         unsigned blkSize;
 278         /** The associativity of the primary table. */
 279         unsigned assoc;
 280         /** The number of cycles for each hash lookup. */
 281         unsigned hashDelay;
 282         /** The number of cycles to read the data. */
 283         unsigned hitLatency;
 284         /** The replacement policy. */
 285         Repl *rp;
 286         /** The subblock size in bytes. */
 287         unsigned subblockSize;
 288     };
 289
 290     /**
 291      * Construct and initialize this tag store.
 292      * @param params The IIC parameters.
 293      * @todo
 294      * Should make a way to have less tags in the primary than blks in the
 295      * cache. Also should be able to specify number of secondary blks.
 296      */
 297     IIC(Params &params);
 298
 299     /**
 300      * Destructor.
 301      */
 302     virtual ~IIC();
 303
 304     /**
 305      * Register the statistics.
 306      * @param name The name to prepend to the statistic descriptions.
 307      */
 308     void regStats(const std::string &name);
 309
 310     /**
 311      * Regenerate the block address from the tag.
 312      * @param tag The tag of the block.
 313      * @param set Not needed for the iic.
 314      * @return The block address.
 315      */
 316     Addr regenerateBlkAddr(Addr tag, int set) {
 317         return (((Addr)tag << tagShift));
 318     }
 319
 320     /**
 321      * Return the block size.
 322      * @return The block size.
 323      */
 324     unsigned
 325     getBlockSize() const
 326     {
 327         return blkSize;
 328     }
 329
 330     /**
 331      * Return the subblock size.
 332      * @return The subblock size.
 333      */
 334     unsigned
 335     getSubBlockSize() const
 336     {
 337         return subSize;
 338     }
 339
 340     /**
 341      * Return the hit latency.
 342      * @return the hit latency.
 343      */
 344     int getHitLatency() const
 345     {
 346         return hitLatency;
 347     }
 348
 349      /**
 350      * Generate the tag from the address.
 351      * @param addr The address to a get a tag for.
 352      * @return the tag.
 353      */
 354     Addr extractTag(Addr addr) const
 355     {
 356         return (addr >> tagShift);
 357     }
 358
 359    /**
 360      * Return the set, always 0 for IIC.
 361      * @return 0.
 362      */
 363     int extractSet(Addr addr) const
 364     {
 365         return 0;
 366     }
 367
 368     /**
 369      * Get the block offset of an address.
 370      * @param addr The address to get the offset of.
 371      * @return the block offset of the address.
 372      */
 373     int extractBlkOffset(Addr addr) const
 374     {
 375         return (addr & blkMask);
 376     }
 377
 378     /**
 379      * Align an address to the block size.
 380      * @param addr the address to align.
 381      * @return The block address.
 382      */
 383     Addr blkAlign(Addr addr) const
 384     {
 385         return (addr & ~(Addr)blkMask);
 386     }
 387
 388     /**
 389      * Swap the position of two tags.
 390      * @param index1 The first tag location.
 391      * @param index2 The second tag location.
 392      */
 393     void tagSwap(unsigned long index1, unsigned long index2);
 394
 395     /**
 396      * Clear the reference bit of the tag and return its old value.
 397      * @param index The pointer of the tag to manipulate.
 398      * @return The previous state of the reference bit.
 399      */
 400     bool clearRef(unsigned long index)
 401     {
 402         bool tmp = tagStore[index].isReferenced();
 403         tagStore[index].status &= ~BlkReferenced;
 404         return tmp;
 405     }
 406
 407     /**
 408      * Invalidate a block.
 409      * @param blk The block to invalidate.
 410      */
 411     void invalidateBlk(BlkType *blk);
 412
 413     /**
 414      * Access block and update replacement data.  May not succeed, in which case
 415      * NULL pointer is returned.  This has all the implications of a cache
 416      * access and should only be used as such.
 417      * Returns the access latency and inCache flags as a side effect.
 418      * @param addr The address to find.
 419      * @param asid The address space ID.
 420      * @param lat The access latency.
 421      * @return A pointer to the block found, if any.
 422      */
 423     IICTag* accessBlock(Addr addr, int &lat, int context_src);
 424
 425     /**
 426      * Find the block, do not update the replacement data.
 427      * @param addr The address to find.
 428      * @param asid The address space ID.
 429      * @return A pointer to the block found, if any.
 430      */
 431     IICTag* findBlock(Addr addr) const;
 432
 433     /**
 434      * Find a replacement block for the address provided.
 435      * @param pkt The request to a find a replacement candidate for.
 436      * @param writebacks List for any writebacks to be performed.
 437      * @return The block to place the replacement in.
 438      */
 439     IICTag* findVictim(Addr addr, PacketList &writebacks);
 440
 441     void insertBlock(Addr addr, BlkType *blk, int context_src);
 442     /**
 443      *iterated through all blocks and clear all locks
 444      *Needed to clear all lock tracking at once
 445      */
 446     virtual void clearLocks();
 447
 448     /**
 449      * Called at end of simulation to complete average block reference stats.
 450      */
 451     virtual void cleanupRefs();
 452
 453 private:
 454     /**
 455      * Return the hash of the address.
 456      * @param addr The address to hash.
 457      * @return the hash of the address.
 458      */
 459     unsigned hash(Addr addr) const;
 460
 461     /**
 462      * Search for a block in the secondary tag store. Returns the number of
 463      * hash lookups as a side effect.
 464      * @param asid The address space ID.
 465      * @param tag The tag to match.
 466      * @param chain_ptr The first entry to search.
 467      * @param depth The number of hash lookups made while searching.
 468      * @return A pointer to the block if found.
 469      */
 470     IICTag *secondaryChain(Addr tag, unsigned long chain_ptr,
 471                             int *depth) const;
 472
 473     /**
 474      * Free the resources associated with the next replacement block.
 475      * @param writebacks A list of any writebacks to perform.
 476      */
 477     void freeReplacementBlock(PacketList & writebacks);
 478
 479     /**
 480      * Return the pointer to a free data block.
 481      * @param writebacks A list of any writebacks to perform.
 482      * @return A pointer to a free data block.
 483      */
 484     unsigned long getFreeDataBlock(PacketList & writebacks);
 485
 486     /**
 487      * Get a free tag in the given hash set.
 488      * @param set The hash set to search.
 489      * @param writebacks A list of any writebacks to perform.
 490      * @return a pointer to a free tag.
 491      */
 492     IICTag* getFreeTag(int set, PacketList & writebacks);
 493
 494     /**
 495      * Free the resources associated with the given tag.
 496      * @param tag_ptr The tag to free.
 497      */
 498     void freeTag(IICTag *tag_ptr);
 499
 500     /**
 501      * Mark the given data block as being available.
 502      * @param data_ptr The data block to free.
 503      */
 504     void freeDataBlock(unsigned long data_ptr);
 505
 506 };
 507 #endif // __IIC_HH__
 508