| /* |
| * Copyright (c) 2002-2005 The Regents of The University of Michigan |
| * All rights reserved. |
| * |
| * Redistribution and use in source and binary forms, with or without |
| * modification, are permitted provided that the following conditions are |
| * met: redistributions of source code must retain the above copyright |
| * notice, this list of conditions and the following disclaimer; |
| * redistributions in binary form must reproduce the above copyright |
| * notice, this list of conditions and the following disclaimer in the |
| * documentation and/or other materials provided with the distribution; |
| * neither the name of the copyright holders nor the names of its |
| * contributors may be used to endorse or promote products derived from |
| * this software without specific prior written permission. |
| * |
| * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
| * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
| * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| * |
| * Authors: Erik Hallnor |
| */ |
| |
| /** |
| * @file |
| * Declaration of the Indirect Index Cache (IIC) tags store. |
| */ |
| |
| #ifndef __IIC_HH__ |
| #define __IIC_HH__ |
| |
| #include <list> |
| #include <vector> |
| |
| #include "mem/cache/blk.hh" |
| #include "mem/cache/tags/iic_repl/repl.hh" |
| #include "mem/packet.hh" |
| #include "base/statistics.hh" |
| #include "mem/cache/tags/base.hh" |
| |
| class BaseCache; // Forward declaration |
| |
| /** |
| * IIC cache blk. |
| */ |
| class IICTag : public CacheBlk |
| { |
| public: |
| /** |
| * Copy the contents of the given IICTag into this one. |
| * @param rhs The tag to copy. |
| * @return const reference to this tag. |
| */ |
| const IICTag& operator=(const IICTag& rhs) |
| { |
| CacheBlk::operator=(rhs); |
| chain_ptr = rhs.chain_ptr; |
| re = rhs.re; |
| set = rhs.set; |
| trivialData = rhs.trivialData; |
| numData = rhs.numData; |
| data_ptr.clear(); |
| for (int i = 0; i < rhs.numData; ++i) { |
| data_ptr.push_back(rhs.data_ptr[i]); |
| } |
| return *this; |
| } |
| |
| /** Hash chain pointer into secondary store. */ |
| unsigned long chain_ptr; |
| /** Data array pointers for each subblock. */ |
| std::vector<unsigned long> data_ptr; |
| /** Replacement Entry pointer. */ |
| void *re; |
| /** |
| * An array to store small compressed data. Conceputally the same size |
| * as the unsused data array pointers. |
| */ |
| uint8_t *trivialData; |
| /** |
| * The number of allocated subblocks. |
| */ |
| int numData; |
| }; |
| |
| /** |
| * A hash set for the IIC primary lookup table. |
| */ |
| class IICSet{ |
| public: |
| /** The associativity of the primary table. */ |
| int assoc; |
| |
| /** The number of hash chains followed when finding the last block. */ |
| int depth; |
| /** The current number of blocks on the chain. */ |
| int size; |
| |
| /** Tag pointer into the secondary tag storage. */ |
| unsigned long chain_ptr; |
| |
| /** The LRU list of the primary table. MRU is at 0 index. */ |
| IICTag ** tags; |
| |
| /** |
| * Find the addr in this set, return the chain pointer to the secondary if |
| * it isn't found. |
| * @param asid The address space ID. |
| * @param tag The address to find. |
| * @param chain_ptr The chain pointer to start the search of the secondary |
| * @return Pointer to the tag, NULL if not found. |
| */ |
| IICTag* findTag( Addr tag, unsigned long &chain_ptr) |
| { |
| depth = 1; |
| for (int i = 0; i < assoc; ++i) { |
| if (tags[i]->tag == tag && tags[i]->isValid()) { |
| return tags[i]; |
| } |
| } |
| chain_ptr = this->chain_ptr; |
| return 0; |
| } |
| |
| /** |
| * Find an usused tag in this set. |
| * @return Pointer to the unused tag, NULL if none are free. |
| */ |
| IICTag* findFree() |
| { |
| for (int i = 0; i < assoc; ++i) { |
| if (!tags[i]->isValid()) { |
| return tags[i]; |
| } |
| } |
| return 0; |
| } |
| |
| /** |
| * Move a tag to the head of the LRU list |
| * @param tag The tag to move. |
| */ |
| void moveToHead(IICTag *tag); |
| |
| /** |
| * Move a tag to the tail (LRU) of the LRU list |
| * @param tag The tag to move. |
| */ |
| void moveToTail(IICTag *tag); |
| }; |
| |
| /** |
| * The IIC tag store. This is a hardware-realizable, fully-associative tag |
| * store that uses software replacement, e.g. Gen. |
| */ |
| class IIC : public BaseTags |
| { |
| public: |
| /** Typedef of the block type used in this class. */ |
| typedef IICTag BlkType; |
| /** Typedef for list of pointers to the local block type. */ |
| typedef std::list<IICTag*> BlkList; |
| |
| protected: |
| /** The number of set in the primary table. */ |
| const unsigned hashSets; |
| /** The block size in bytes. */ |
| const unsigned blkSize; |
| /** The associativity of the primary table. */ |
| const unsigned assoc; |
| /** The base hit latency. */ |
| const unsigned hitLatency; |
| /** The subblock size, used for compression. */ |
| const unsigned subSize; |
| |
| /** The number of subblocks */ |
| const unsigned numSub; |
| /** The number of bytes used by data pointers */ |
| const unsigned trivialSize; |
| |
| /** The amount to shift address to get the tag. */ |
| const unsigned tagShift; |
| /** The mask to get block offset bits. */ |
| const unsigned blkMask; |
| |
| /** The amount to shift to get the subblock number. */ |
| const unsigned subShift; |
| /** The mask to get the correct subblock number. */ |
| const unsigned subMask; |
| |
| /** The latency of a hash lookup. */ |
| const unsigned hashDelay; |
| /** The number of data blocks. */ |
| const unsigned numBlocks; |
| /** The total number of tags in primary and secondary. */ |
| const unsigned numTags; |
| /** The number of tags in the secondary tag store. */ |
| const unsigned numSecondary; |
| |
| /** The Null tag pointer. */ |
| const unsigned tagNull; |
| /** The last tag in the primary table. */ |
| const unsigned primaryBound; |
| |
| /** All of the tags */ |
| IICTag *tagStore; |
| /** |
| * Pointer to the head of the secondary freelist (maintained with chain |
| * pointers. |
| */ |
| unsigned long freelist; |
| /** |
| * The data block freelist. |
| */ |
| std::list<unsigned long> blkFreelist; |
| |
| /** The primary table. */ |
| IICSet *sets; |
| |
| /** The replacement policy. */ |
| Repl *repl; |
| |
| /** An array of data reference counters. */ |
| int *dataReferenceCount; |
| |
| /** The data blocks. */ |
| uint8_t *dataStore; |
| |
| /** Storage for the fast access data of each cache block. */ |
| uint8_t **dataBlks; |
| |
| /** |
| * Count of the current number of free secondary tags. |
| * Used for debugging. |
| */ |
| int freeSecond; |
| |
| // IIC Statistics |
| /** |
| * @addtogroup IICStatistics IIC Statistics |
| * @{ |
| */ |
| |
| /** Hash hit depth of cache hits. */ |
| Stats::Distribution hitHashDepth; |
| /** Hash depth for cache misses. */ |
| Stats::Distribution missHashDepth; |
| /** Count of accesses to each hash set. */ |
| Stats::Distribution setAccess; |
| |
| /** The total hash depth for every miss. */ |
| Stats::Scalar missDepthTotal; |
| /** The total hash depth for all hits. */ |
| Stats::Scalar hitDepthTotal; |
| /** The number of hash misses. */ |
| Stats::Scalar hashMiss; |
| /** The number of hash hits. */ |
| Stats::Scalar hashHit; |
| /** @} */ |
| |
| public: |
| /** |
| * Collection of parameters for the IIC. |
| */ |
| class Params { |
| public: |
| /** The size in bytes of the cache. */ |
| unsigned size; |
| /** The number of sets in the primary table. */ |
| unsigned numSets; |
| /** The block size in bytes. */ |
| unsigned blkSize; |
| /** The associativity of the primary table. */ |
| unsigned assoc; |
| /** The number of cycles for each hash lookup. */ |
| unsigned hashDelay; |
| /** The number of cycles to read the data. */ |
| unsigned hitLatency; |
| /** The replacement policy. */ |
| Repl *rp; |
| /** The subblock size in bytes. */ |
| unsigned subblockSize; |
| }; |
| |
| /** |
| * Construct and initialize this tag store. |
| * @param params The IIC parameters. |
| * @todo |
| * Should make a way to have less tags in the primary than blks in the |
| * cache. Also should be able to specify number of secondary blks. |
| */ |
| IIC(Params ¶ms); |
| |
| /** |
| * Destructor. |
| */ |
| virtual ~IIC(); |
| |
| /** |
| * Register the statistics. |
| * @param name The name to prepend to the statistic descriptions. |
| */ |
| void regStats(const std::string &name); |
| |
| /** |
| * Regenerate the block address from the tag. |
| * @param tag The tag of the block. |
| * @param set Not needed for the iic. |
| * @return The block address. |
| */ |
| Addr regenerateBlkAddr(Addr tag, int set) { |
| return (((Addr)tag << tagShift)); |
| } |
| |
| /** |
| * Return the block size. |
| * @return The block size. |
| */ |
| unsigned |
| getBlockSize() const |
| { |
| return blkSize; |
| } |
| |
| /** |
| * Return the subblock size. |
| * @return The subblock size. |
| */ |
| unsigned |
| getSubBlockSize() const |
| { |
| return subSize; |
| } |
| |
| /** |
| * Return the hit latency. |
| * @return the hit latency. |
| */ |
| int getHitLatency() const |
| { |
| return hitLatency; |
| } |
| |
| /** |
| * Generate the tag from the address. |
| * @param addr The address to a get a tag for. |
| * @return the tag. |
| */ |
| Addr extractTag(Addr addr) const |
| { |
| return (addr >> tagShift); |
| } |
| |
| /** |
| * Return the set, always 0 for IIC. |
| * @return 0. |
| */ |
| int extractSet(Addr addr) const |
| { |
| return 0; |
| } |
| |
| /** |
| * Get the block offset of an address. |
| * @param addr The address to get the offset of. |
| * @return the block offset of the address. |
| */ |
| int extractBlkOffset(Addr addr) const |
| { |
| return (addr & blkMask); |
| } |
| |
| /** |
| * Align an address to the block size. |
| * @param addr the address to align. |
| * @return The block address. |
| */ |
| Addr blkAlign(Addr addr) const |
| { |
| return (addr & ~(Addr)blkMask); |
| } |
| |
| /** |
| * Swap the position of two tags. |
| * @param index1 The first tag location. |
| * @param index2 The second tag location. |
| */ |
| void tagSwap(unsigned long index1, unsigned long index2); |
| |
| /** |
| * Clear the reference bit of the tag and return its old value. |
| * @param index The pointer of the tag to manipulate. |
| * @return The previous state of the reference bit. |
| */ |
| bool clearRef(unsigned long index) |
| { |
| bool tmp = tagStore[index].isReferenced(); |
| tagStore[index].status &= ~BlkReferenced; |
| return tmp; |
| } |
| |
| /** |
| * Invalidate a block. |
| * @param blk The block to invalidate. |
| */ |
| void invalidateBlk(BlkType *blk); |
| |
| /** |
| * Access block and update replacement data. May not succeed, in which case |
| * NULL pointer is returned. This has all the implications of a cache |
| * access and should only be used as such. |
| * Returns the access latency and inCache flags as a side effect. |
| * @param addr The address to find. |
| * @param asid The address space ID. |
| * @param lat The access latency. |
| * @return A pointer to the block found, if any. |
| */ |
| IICTag* accessBlock(Addr addr, int &lat); |
| |
| /** |
| * Find the block, do not update the replacement data. |
| * @param addr The address to find. |
| * @param asid The address space ID. |
| * @return A pointer to the block found, if any. |
| */ |
| IICTag* findBlock(Addr addr) const; |
| |
| /** |
| * Find a replacement block for the address provided. |
| * @param pkt The request to a find a replacement candidate for. |
| * @param writebacks List for any writebacks to be performed. |
| * @return The block to place the replacement in. |
| */ |
| IICTag* findVictim(Addr addr, PacketList &writebacks); |
| |
| void insertBlock(Addr addr, BlkType *blk); |
| |
| /** |
| * Called at end of simulation to complete average block reference stats. |
| */ |
| virtual void cleanupRefs(); |
| |
| private: |
| /** |
| * Return the hash of the address. |
| * @param addr The address to hash. |
| * @return the hash of the address. |
| */ |
| unsigned hash(Addr addr) const; |
| |
| /** |
| * Search for a block in the secondary tag store. Returns the number of |
| * hash lookups as a side effect. |
| * @param asid The address space ID. |
| * @param tag The tag to match. |
| * @param chain_ptr The first entry to search. |
| * @param depth The number of hash lookups made while searching. |
| * @return A pointer to the block if found. |
| */ |
| IICTag *secondaryChain(Addr tag, unsigned long chain_ptr, |
| int *depth) const; |
| |
| /** |
| * Free the resources associated with the next replacement block. |
| * @param writebacks A list of any writebacks to perform. |
| */ |
| void freeReplacementBlock(PacketList & writebacks); |
| |
| /** |
| * Return the pointer to a free data block. |
| * @param writebacks A list of any writebacks to perform. |
| * @return A pointer to a free data block. |
| */ |
| unsigned long getFreeDataBlock(PacketList & writebacks); |
| |
| /** |
| * Get a free tag in the given hash set. |
| * @param set The hash set to search. |
| * @param writebacks A list of any writebacks to perform. |
| * @return a pointer to a free tag. |
| */ |
| IICTag* getFreeTag(int set, PacketList & writebacks); |
| |
| /** |
| * Free the resources associated with the given tag. |
| * @param tag_ptr The tag to free. |
| */ |
| void freeTag(IICTag *tag_ptr); |
| |
| /** |
| * Mark the given data block as being available. |
| * @param data_ptr The data block to free. |
| */ |
| void freeDataBlock(unsigned long data_ptr); |
| }; |
| #endif // __IIC_HH__ |
| |