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      * @return the tag.
 352      */
 353     Addr extractTag(Addr addr) const
 354     {
 355         return (addr >> tagShift);
 356     }
 357
 358    /**
 359      * Return the set, always 0 for IIC.
 360      * @return 0.
 361      */
 362     int extractSet(Addr addr) const
 363     {
 364         return 0;
 365     }
 366
 367     /**
 368      * Get the block offset of an address.
 369      * @param addr The address to get the offset of.
 370      * @return the block offset of the address.
 371      */
 372     int extractBlkOffset(Addr addr) const
 373     {
 374         return (addr & blkMask);
 375     }
 376
 377     /**
 378      * Align an address to the block size.
 379      * @param addr the address to align.
 380      * @return The block address.
 381      */
 382     Addr blkAlign(Addr addr) const
 383     {
 384         return (addr & ~(Addr)blkMask);
 385     }
 386
 387     /**
 388      * Check for the address in the tagstore.
 389      * @param asid The address space ID.
 390      * @param addr The address to find.
 391      * @return true if it is found.
 392      */
 393     bool probe(Addr addr) const;
 394
 395     /**
 396      * Swap the position of two tags.
 397      * @param index1 The first tag location.
 398      * @param index2 The second tag location.
 399      */
 400     void tagSwap(unsigned long index1, unsigned long index2);
 401
 402     /**
 403      * Clear the reference bit of the tag and return its old value.
 404      * @param index The pointer of the tag to manipulate.
 405      * @return The previous state of the reference bit.
 406      */
 407     bool clearRef(unsigned long index)
 408     {
 409         bool tmp = tagStore[index].isReferenced();
 410         tagStore[index].status &= ~BlkReferenced;
 411         return tmp;
 412     }
 413
 414     /**
 415      * Invalidate a block.
 416      * @param blk The block to invalidate.
 417      */
 418     void invalidateBlk(BlkType *blk);
 419
 420     /**
 421      * Find the block and update the replacement data. This call also returns
 422      * the access latency as a side effect.
 423      * @param addr The address to find.
 424      * @param asid The address space ID.
 425      * @param lat The access latency.
 426      * @return A pointer to the block found, if any.
 427      */
 428     IICTag* findBlock(Addr addr, int &lat);
 429
 430     /**
 431      * Find the block, do not update the replacement data.
 432      * @param addr The address to find.
 433      * @param asid The address space ID.
 434      * @return A pointer to the block found, if any.
 435      */
 436     IICTag* findBlock(Addr addr) const;
 437
 438     /**
 439      * Find a replacement block for the address provided.
 440      * @param pkt The request to a find a replacement candidate for.
 441      * @param writebacks List for any writebacks to be performed.
 442      * @return The block to place the replacement in.
 443      */
 444     IICTag* findReplacement(Addr addr, PacketList &writebacks);
 445
 446     /**
 447      * Read the data from the internal storage of the given cache block.
 448      * @param blk The block to read the data from.
 449      * @param data The buffer to read the data into.
 450      * @return The cache block's data.
 451      */
 452     void readData(IICTag *blk, uint8_t *data);
 453
 454     /**
 455      * Write the data into the internal storage of the given cache block.
 456      * @param blk The block to write to.
 457      * @param data The data to write.
 458      * @param size The number of bytes to write.
 459      * @param writebacks A list for any writebacks to be performed. May be
 460      * needed when writing to a compressed block.
 461      */
 462     void writeData(IICTag *blk, uint8_t *data, int size,
 463                    PacketList & writebacks);
 464
 465     /**
 466      * Called at end of simulation to complete average block reference stats.
 467      */
 468     virtual void cleanupRefs();
 469 private:
 470     /**
 471      * Return the hash of the address.
 472      * @param addr The address to hash.
 473      * @return the hash of the address.
 474      */
 475     unsigned hash(Addr addr) const;
 476
 477     /**
 478      * Search for a block in the secondary tag store. Returns the number of
 479      * hash lookups as a side effect.
 480      * @param asid The address space ID.
 481      * @param tag The tag to match.
 482      * @param chain_ptr The first entry to search.
 483      * @param depth The number of hash lookups made while searching.
 484      * @return A pointer to the block if found.
 485      */
 486     IICTag *secondaryChain(Addr tag, unsigned long chain_ptr,
 487                             int *depth) const;
 488
 489     /**
 490      * Free the resources associated with the next replacement block.
 491      * @param writebacks A list of any writebacks to perform.
 492      */
 493     void freeReplacementBlock(PacketList & writebacks);
 494
 495     /**
 496      * Return the pointer to a free data block.
 497      * @param writebacks A list of any writebacks to perform.
 498      * @return A pointer to a free data block.
 499      */
 500     unsigned long getFreeDataBlock(PacketList & writebacks);
 501
 502     /**
 503      * Get a free tag in the given hash set.
 504      * @param set The hash set to search.
 505      * @param writebacks A list of any writebacks to perform.
 506      * @return a pointer to a free tag.
 507      */
 508     IICTag* getFreeTag(int set, PacketList & writebacks);
 509
 510     /**
 511      * Free the resources associated with the given tag.
 512      * @param tag_ptr The tag to free.
 513      */
 514     void freeTag(IICTag *tag_ptr);
 515
 516     /**
 517      * Mark the given data block as being available.
 518      * @param data_ptr The data block to free.
 519      */
 520     void freeDataBlock(unsigned long data_ptr);
 521 };
 522 #endif // __IIC_HH__
 523