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 "mem/cache/cache_blk.hh"
  43 #include "mem/cache/tags/repl/repl.hh"
  44 #include "mem/packet.hh"
  45 #include "base/statistics.hh"
  46 #include "mem/cache/tags/base_tags.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   protected:
 171     /** The number of set in the primary table. */
 172     const int hashSets;
 173     /** The block size in bytes. */
 174     const int blkSize;
 175     /** The associativity of the primary table. */
 176     const int assoc;
 177     /** The base hit latency. */
 178     const int hitLatency;
 179     /** The subblock size, used for compression. */
 180     const int subSize;
 181
 182     /** The number of subblocks */
 183     const int numSub;
 184     /** The number of bytes used by data pointers */
 185     const int trivialSize;
 186
 187     /** The amount to shift address to get the tag. */
 188     const int tagShift;
 189     /** The mask to get block offset bits. */
 190     const unsigned blkMask;
 191
 192     /** The amount to shift to get the subblock number. */
 193     const int subShift;
 194     /** The mask to get the correct subblock number. */
 195     const unsigned subMask;
 196
 197     /** The latency of a hash lookup. */
 198     const int hashDelay;
 199     /** The number of data blocks. */
 200     const int numBlocks;
 201     /** The total number of tags in primary and secondary. */
 202     const int numTags;
 203     /** The number of tags in the secondary tag store. */
 204     const int numSecondary;
 205
 206     /** The Null tag pointer. */
 207     const int tagNull;
 208     /** The last tag in the primary table. */
 209     const int primaryBound;
 210
 211     /** All of the tags */
 212     IICTag *tagStore;
 213     /**
 214      * Pointer to the head of the secondary freelist (maintained with chain
 215      * pointers.
 216      */
 217     unsigned long freelist;
 218     /**
 219      * The data block freelist.
 220      */
 221     std::list<unsigned long> blkFreelist;
 222
 223     /** The primary table. */
 224     IICSet *sets;
 225
 226     /** The replacement policy. */
 227     Repl *repl;
 228
 229     /** An array of data reference counters. */
 230     int *dataReferenceCount;
 231
 232     /** The data blocks. */
 233     uint8_t *dataStore;
 234
 235     /** Storage for the fast access data of each cache block. */
 236     uint8_t **dataBlks;
 237
 238     /**
 239      * Count of the current number of free secondary tags.
 240      * Used for debugging.
 241      */
 242     int freeSecond;
 243
 244     // IIC Statistics
 245     /**
 246      * @addtogroup IICStatistics IIC Statistics
 247      * @{
 248      */
 249
 250     /** Hash hit depth of cache hits. */
 251     Stats::Distribution<> hitHashDepth;
 252     /** Hash depth for cache misses. */
 253     Stats::Distribution<> missHashDepth;
 254     /** Count of accesses to each hash set. */
 255     Stats::Distribution<> setAccess;
 256
 257     /** The total hash depth for every miss. */
 258     Stats::Scalar<> missDepthTotal;
 259     /** The total hash depth for all hits. */
 260     Stats::Scalar<> hitDepthTotal;
 261     /** The number of hash misses. */
 262     Stats::Scalar<> hashMiss;
 263     /** The number of hash hits. */
 264     Stats::Scalar<> hashHit;
 265     /** @} */
 266
 267   public:
 268     /**
 269      * Collection of parameters for the IIC.
 270      */
 271     class Params {
 272       public:
 273         /** The size in bytes of the cache. */
 274         int size;
 275         /** The number of sets in the primary table. */
 276         int numSets;
 277         /** The block size in bytes. */
 278         int blkSize;
 279         /** The associativity of the primary table. */
 280         int assoc;
 281         /** The number of cycles for each hash lookup. */
 282         int hashDelay;
 283         /** The number of cycles to read the data. */
 284         int hitLatency;
 285         /** The replacement policy. */
 286         Repl *rp;
 287         /** The subblock size in bytes. */
 288         int subblockSize;
 289     };
 290
 291     /**
 292      * Construct and initialize this tag store.
 293      * @param params The IIC parameters.
 294      * @todo
 295      * Should make a way to have less tags in the primary than blks in the
 296      * cache. Also should be able to specify number of secondary blks.
 297      */
 298     IIC(Params &params);
 299
 300     /**
 301      * Destructor.
 302      */
 303     virtual ~IIC();
 304
 305     /**
 306      * Register the statistics.
 307      * @param name The name to prepend to the statistic descriptions.
 308      */
 309     void regStats(const std::string &name);
 310
 311     /**
 312      * Regenerate the block address from the tag.
 313      * @param tag The tag of the block.
 314      * @param set Not needed for the iic.
 315      * @return The block address.
 316      */
 317     Addr regenerateBlkAddr(Addr tag, int set) {
 318         return (((Addr)tag << tagShift));
 319     }
 320
 321     /**
 322      * Return the block size.
 323      * @return The block size.
 324      */
 325     int getBlockSize()
 326     {
 327         return blkSize;
 328     }
 329
 330     /**
 331      * Return the subblock size.
 332      * @return The subblock size.
 333      */
 334     int getSubBlockSize()
 335     {
 336         return subSize;
 337     }
 338
 339     /**
 340      * Return the hit latency.
 341      * @return the hit latency.
 342      */
 343     int getHitLatency() const
 344     {
 345         return hitLatency;
 346     }
 347
 348     /**
 349      * Generate the tag from the address.
 350      * @param addr The address to a get a tag for.
 351      * @param blk Ignored here.
 352      * @return the tag.
 353      */
 354     Addr extractTag(Addr addr, IICTag *blk) const
 355     {
 356         return (addr >> tagShift);
 357     }
 358
 359      /**
 360      * Generate the tag from the address.
 361      * @param addr The address to a get a tag for.
 362      * @return the tag.
 363      */
 364     Addr extractTag(Addr addr) const
 365     {
 366         return (addr >> tagShift);
 367     }
 368
 369    /**
 370      * Return the set, always 0 for IIC.
 371      * @return 0.
 372      */
 373     int extractSet(Addr addr) const
 374     {
 375         return 0;
 376     }
 377
 378     /**
 379      * Get the block offset of an address.
 380      * @param addr The address to get the offset of.
 381      * @return the block offset of the address.
 382      */
 383     int extractBlkOffset(Addr addr) const
 384     {
 385         return (addr & blkMask);
 386     }
 387
 388     /**
 389      * Align an address to the block size.
 390      * @param addr the address to align.
 391      * @return The block address.
 392      */
 393     Addr blkAlign(Addr addr) const
 394     {
 395         return (addr & ~(Addr)blkMask);
 396     }
 397
 398     /**
 399      * Check for the address in the tagstore.
 400      * @param asid The address space ID.
 401      * @param addr The address to find.
 402      * @return true if it is found.
 403      */
 404     bool probe(Addr addr) const;
 405
 406     /**
 407      * Swap the position of two tags.
 408      * @param index1 The first tag location.
 409      * @param index2 The second tag location.
 410      */
 411     void tagSwap(unsigned long index1, unsigned long index2);
 412
 413     /**
 414      * Clear the reference bit of the tag and return its old value.
 415      * @param index The pointer of the tag to manipulate.
 416      * @return The previous state of the reference bit.
 417      */
 418     bool clearRef(unsigned long index)
 419     {
 420         bool tmp = tagStore[index].isReferenced();
 421         tagStore[index].status &= ~BlkReferenced;
 422         return tmp;
 423     }
 424
 425     /**
 426      * Decompress a block if it is compressed.
 427      * @param index The tag store index for the block to uncompress.
 428      */
 429     void decompressBlock(unsigned long index);
 430
 431     /**
 432      * Try and compress a block if it is not already compressed.
 433      * @param index The tag store index for the block to compress.
 434      */
 435     void compressBlock(unsigned long index);
 436
 437     /**
 438      * Invalidate a block.
 439      * @param blk The block to invalidate.
 440      */
 441     void invalidateBlk(BlkType *blk);
 442
 443     /**
 444      * Find the block and update the replacement data. This call also returns
 445      * the access latency as a side effect.
 446      * @param addr The address to find.
 447      * @param asid The address space ID.
 448      * @param lat The access latency.
 449      * @return A pointer to the block found, if any.
 450      */
 451     IICTag* findBlock(Addr addr, int &lat);
 452
 453     /**
 454      * Find the block, do not update the replacement data.
 455      * @param addr The address to find.
 456      * @param asid The address space ID.
 457      * @return A pointer to the block found, if any.
 458      */
 459     IICTag* findBlock(Addr addr) const;
 460
 461     /**
 462      * Find a replacement block for the address provided.
 463      * @param pkt The request to a find a replacement candidate for.
 464      * @param writebacks List for any writebacks to be performed.
 465      * @param compress_blocks List of blocks to compress, for adaptive comp.
 466      * @return The block to place the replacement in.
 467      */
 468     IICTag* findReplacement(PacketPtr &pkt, PacketList &writebacks,
 469                             BlkList &compress_blocks);
 470
 471     /**
 472      * Read the data from the internal storage of the given cache block.
 473      * @param blk The block to read the data from.
 474      * @param data The buffer to read the data into.
 475      * @return The cache block's data.
 476      */
 477     void readData(IICTag *blk, uint8_t *data);
 478
 479     /**
 480      * Write the data into the internal storage of the given cache block.
 481      * @param blk The block to write to.
 482      * @param data The data to write.
 483      * @param size The number of bytes to write.
 484      * @param writebacks A list for any writebacks to be performed. May be
 485      * needed when writing to a compressed block.
 486      */
 487     void writeData(IICTag *blk, uint8_t *data, int size,
 488                    PacketList & writebacks);
 489
 490     /**
 491      * Called at end of simulation to complete average block reference stats.
 492      */
 493     virtual void cleanupRefs();
 494 private:
 495     /**
 496      * Return the hash of the address.
 497      * @param addr The address to hash.
 498      * @return the hash of the address.
 499      */
 500     unsigned hash(Addr addr) const;
 501
 502     /**
 503      * Search for a block in the secondary tag store. Returns the number of
 504      * hash lookups as a side effect.
 505      * @param asid The address space ID.
 506      * @param tag The tag to match.
 507      * @param chain_ptr The first entry to search.
 508      * @param depth The number of hash lookups made while searching.
 509      * @return A pointer to the block if found.
 510      */
 511     IICTag *secondaryChain(Addr tag, unsigned long chain_ptr,
 512                             int *depth) const;
 513
 514     /**
 515      * Free the resources associated with the next replacement block.
 516      * @param writebacks A list of any writebacks to perform.
 517      */
 518     void freeReplacementBlock(PacketList & writebacks);
 519
 520     /**
 521      * Return the pointer to a free data block.
 522      * @param writebacks A list of any writebacks to perform.
 523      * @return A pointer to a free data block.
 524      */
 525     unsigned long getFreeDataBlock(PacketList & writebacks);
 526
 527     /**
 528      * Get a free tag in the given hash set.
 529      * @param set The hash set to search.
 530      * @param writebacks A list of any writebacks to perform.
 531      * @return a pointer to a free tag.
 532      */
 533     IICTag* getFreeTag(int set, PacketList & writebacks);
 534
 535     /**
 536      * Free the resources associated with the given tag.
 537      * @param tag_ptr The tag to free.
 538      */
 539     void freeTag(IICTag *tag_ptr);
 540
 541     /**
 542      * Mark the given data block as being available.
 543      * @param data_ptr The data block to free.
 544      */
 545     void freeDataBlock(unsigned long data_ptr);
 546 };
 547 #endif // __IIC_HH__
 548