fa_lru.hh revision 9347
12817Sksewell@umich.edu/* 22817Sksewell@umich.edu * Copyright (c) 2012 ARM Limited 32817Sksewell@umich.edu * All rights reserved. 42817Sksewell@umich.edu * 52817Sksewell@umich.edu * The license below extends only to copyright in the software and shall 62817Sksewell@umich.edu * not be construed as granting a license to any other intellectual 72817Sksewell@umich.edu * property including but not limited to intellectual property relating 82817Sksewell@umich.edu * to a hardware implementation of the functionality of the software 92817Sksewell@umich.edu * licensed hereunder. You may use the software subject to the license 102817Sksewell@umich.edu * terms below provided that you ensure that this notice is replicated 112817Sksewell@umich.edu * unmodified and in its entirety in all distributions of the software, 122817Sksewell@umich.edu * modified or unmodified, in source code or in binary form. 132817Sksewell@umich.edu * 142817Sksewell@umich.edu * Copyright (c) 2003-2005 The Regents of The University of Michigan 152817Sksewell@umich.edu * All rights reserved. 162817Sksewell@umich.edu * 172817Sksewell@umich.edu * Redistribution and use in source and binary forms, with or without 182817Sksewell@umich.edu * modification, are permitted provided that the following conditions are 192817Sksewell@umich.edu * met: redistributions of source code must retain the above copyright 202817Sksewell@umich.edu * notice, this list of conditions and the following disclaimer; 212817Sksewell@umich.edu * redistributions in binary form must reproduce the above copyright 222817Sksewell@umich.edu * notice, this list of conditions and the following disclaimer in the 232817Sksewell@umich.edu * documentation and/or other materials provided with the distribution; 242817Sksewell@umich.edu * neither the name of the copyright holders nor the names of its 252817Sksewell@umich.edu * contributors may be used to endorse or promote products derived from 262817Sksewell@umich.edu * this software without specific prior written permission. 272817Sksewell@umich.edu * 282817Sksewell@umich.edu * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 292817Sksewell@umich.edu * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 302817Sksewell@umich.edu * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 312817Sksewell@umich.edu * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 322817Sksewell@umich.edu * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 332834Sksewell@umich.edu * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 342817Sksewell@umich.edu * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 352817Sksewell@umich.edu * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 362817Sksewell@umich.edu * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 372817Sksewell@umich.edu * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 382817Sksewell@umich.edu * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 392817Sksewell@umich.edu * 402817Sksewell@umich.edu * Authors: Erik Hallnor 412817Sksewell@umich.edu */ 422817Sksewell@umich.edu 432817Sksewell@umich.edu/** 442817Sksewell@umich.edu * @file 452817Sksewell@umich.edu * Declaration of a fully associative LRU tag store. 462817Sksewell@umich.edu */ 472817Sksewell@umich.edu 482817Sksewell@umich.edu#ifndef __MEM_CACHE_TAGS_FA_LRU_HH__ 492817Sksewell@umich.edu#define __MEM_CACHE_TAGS_FA_LRU_HH__ 502817Sksewell@umich.edu 512817Sksewell@umich.edu#include <list> 522817Sksewell@umich.edu 532817Sksewell@umich.edu#include "base/hashmap.hh" 542817Sksewell@umich.edu#include "mem/cache/tags/base.hh" 552817Sksewell@umich.edu#include "mem/cache/blk.hh" 562817Sksewell@umich.edu#include "mem/packet.hh" 573126Sktlim@umich.edu 582817Sksewell@umich.edu/** 592817Sksewell@umich.edu * A fully associative cache block. 602817Sksewell@umich.edu */ 612817Sksewell@umich.educlass FALRUBlk : public CacheBlk 622817Sksewell@umich.edu{ 632817Sksewell@umich.edupublic: 642817Sksewell@umich.edu /** The previous block in LRU order. */ 652817Sksewell@umich.edu FALRUBlk *prev; 662817Sksewell@umich.edu /** The next block in LRU order. */ 672817Sksewell@umich.edu FALRUBlk *next; 682817Sksewell@umich.edu /** Has this block been touched? */ 692817Sksewell@umich.edu bool isTouched; 702817Sksewell@umich.edu 712817Sksewell@umich.edu /** 722817Sksewell@umich.edu * A bit mask of the sizes of cache that this block is resident in. 732817Sksewell@umich.edu * Each bit represents a power of 2 in MB size cache. 742817Sksewell@umich.edu * If bit 0 is set, this block is in a 1MB cache 752817Sksewell@umich.edu * If bit 2 is set, this block is in a 4MB cache, etc. 762817Sksewell@umich.edu * There is one bit for each cache smaller than the full size (default 772817Sksewell@umich.edu * 16MB). 782817Sksewell@umich.edu */ 792817Sksewell@umich.edu int inCache; 802817Sksewell@umich.edu}; 812817Sksewell@umich.edu 822817Sksewell@umich.edu/** 832817Sksewell@umich.edu * A fully associative LRU cache. Keeps statistics for accesses to a number of 842817Sksewell@umich.edu * cache sizes at once. 852817Sksewell@umich.edu */ 862817Sksewell@umich.educlass FALRU : public BaseTags 872817Sksewell@umich.edu{ 882817Sksewell@umich.edu public: 892817Sksewell@umich.edu /** Typedef the block type used in this class. */ 902817Sksewell@umich.edu typedef FALRUBlk BlkType; 912817Sksewell@umich.edu /** Typedef a list of pointers to the local block type. */ 922817Sksewell@umich.edu typedef std::list<FALRUBlk*> BlkList; 932817Sksewell@umich.edu 942817Sksewell@umich.edu protected: 952817Sksewell@umich.edu /** The block size of the cache. */ 962817Sksewell@umich.edu const unsigned blkSize; 972817Sksewell@umich.edu /** The size of the cache. */ 982817Sksewell@umich.edu const unsigned size; 992817Sksewell@umich.edu /** The hit latency of the cache. */ 1002817Sksewell@umich.edu const Cycles hitLatency; 1012817Sksewell@umich.edu 1022817Sksewell@umich.edu /** Array of pointers to blocks at the cache size boundaries. */ 1032817Sksewell@umich.edu FALRUBlk **cacheBoundaries; 1042817Sksewell@umich.edu /** A mask for the FALRUBlk::inCache bits. */ 1052817Sksewell@umich.edu int cacheMask; 1062817Sksewell@umich.edu /** The number of different size caches being tracked. */ 1072817Sksewell@umich.edu unsigned numCaches; 1082817Sksewell@umich.edu 1092817Sksewell@umich.edu /** The cache blocks. */ 1102817Sksewell@umich.edu FALRUBlk *blks; 1112817Sksewell@umich.edu 1122817Sksewell@umich.edu /** The MRU block. */ 1132817Sksewell@umich.edu FALRUBlk *head; 1142817Sksewell@umich.edu /** The LRU block. */ 1152817Sksewell@umich.edu FALRUBlk *tail; 1162875Sksewell@umich.edu 1172875Sksewell@umich.edu /** Hash table type mapping addresses to cache block pointers. */ 1182817Sksewell@umich.edu typedef m5::hash_map<Addr, FALRUBlk *, m5::hash<Addr> > hash_t; 1192817Sksewell@umich.edu /** Iterator into the address hash table. */ 1202817Sksewell@umich.edu typedef hash_t::const_iterator tagIterator; 1212817Sksewell@umich.edu 1222817Sksewell@umich.edu /** The address hash table. */ 1232817Sksewell@umich.edu hash_t tagHash; 1242817Sksewell@umich.edu 1252817Sksewell@umich.edu /** 1262817Sksewell@umich.edu * Find the cache block for the given address. 1272817Sksewell@umich.edu * @param addr The address to find. 1282817Sksewell@umich.edu * @return The cache block of the address, if any. 1292817Sksewell@umich.edu */ 1302817Sksewell@umich.edu FALRUBlk * hashLookup(Addr addr) const; 1312817Sksewell@umich.edu 1322817Sksewell@umich.edu /** 1332817Sksewell@umich.edu * Move a cache block to the MRU position. 1342817Sksewell@umich.edu * @param blk The block to promote. 1352817Sksewell@umich.edu */ 1362817Sksewell@umich.edu void moveToHead(FALRUBlk *blk); 1372817Sksewell@umich.edu 1382817Sksewell@umich.edu /** 1392817Sksewell@umich.edu * Check to make sure all the cache boundaries are still where they should 1402817Sksewell@umich.edu * be. Used for debugging. 1412875Sksewell@umich.edu * @return True if everything is correct. 1422875Sksewell@umich.edu */ 1432817Sksewell@umich.edu bool check(); 1442817Sksewell@umich.edu 1452817Sksewell@umich.edu /** 1462817Sksewell@umich.edu * @defgroup FALRUStats Fully Associative LRU specific statistics 1472817Sksewell@umich.edu * The FA lru stack lets us track multiple cache sizes at once. These 1482817Sksewell@umich.edu * statistics track the hits and misses for different cache sizes. 1492817Sksewell@umich.edu * @{ 1502817Sksewell@umich.edu */ 1512817Sksewell@umich.edu 1522817Sksewell@umich.edu /** Hits in each cache size >= 128K. */ 1532817Sksewell@umich.edu Stats::Vector hits; 1542817Sksewell@umich.edu /** Misses in each cache size >= 128K. */ 1552817Sksewell@umich.edu Stats::Vector misses; 1562817Sksewell@umich.edu /** Total number of accesses. */ 1572817Sksewell@umich.edu Stats::Scalar accesses; 1582817Sksewell@umich.edu 1592817Sksewell@umich.edu /** 1602817Sksewell@umich.edu * @} 1612817Sksewell@umich.edu */ 1622817Sksewell@umich.edu 1632817Sksewell@umich.edupublic: 1642817Sksewell@umich.edu /** 1652817Sksewell@umich.edu * Construct and initialize this cache tagstore. 1662875Sksewell@umich.edu * @param blkSize The block size of the cache. 1672817Sksewell@umich.edu * @param size The size of the cache. 1683221Sktlim@umich.edu * @param hit_latency The hit latency of the cache. 1693221Sktlim@umich.edu */ 1702817Sksewell@umich.edu FALRU(unsigned blkSize, unsigned size, Cycles hit_latency); 1712817Sksewell@umich.edu ~FALRU(); 1722817Sksewell@umich.edu 1732817Sksewell@umich.edu /** 1742817Sksewell@umich.edu * Register the stats for this object. 1753221Sktlim@umich.edu * @param name The name to prepend to the stats name. 1762817Sksewell@umich.edu */ 1772817Sksewell@umich.edu void regStats(const std::string &name); 1782817Sksewell@umich.edu 1792817Sksewell@umich.edu /** 1802817Sksewell@umich.edu * Invalidate a cache block. 1812817Sksewell@umich.edu * @param blk The block to invalidate. 1822875Sksewell@umich.edu */ 1832875Sksewell@umich.edu void invalidate(BlkType *blk); 1842817Sksewell@umich.edu 1852817Sksewell@umich.edu /** 1862817Sksewell@umich.edu * Access block and update replacement data. May not succeed, in which case 1872817Sksewell@umich.edu * NULL pointer is returned. This has all the implications of a cache 1882817Sksewell@umich.edu * access and should only be used as such. 1892817Sksewell@umich.edu * Returns the access latency and inCache flags as a side effect. 1902817Sksewell@umich.edu * @param addr The address to look for. 1912817Sksewell@umich.edu * @param asid The address space ID. 1922817Sksewell@umich.edu * @param lat The latency of the access. 1932817Sksewell@umich.edu * @param inCache The FALRUBlk::inCache flags. 1942817Sksewell@umich.edu * @return Pointer to the cache block. 1952817Sksewell@umich.edu */ 1962817Sksewell@umich.edu FALRUBlk* accessBlock(Addr addr, Cycles &lat, int context_src, int *inCache = 0); 1972817Sksewell@umich.edu 1982817Sksewell@umich.edu /** 1992817Sksewell@umich.edu * Find the block in the cache, do not update the replacement data. 2002817Sksewell@umich.edu * @param addr The address to look for. 2012817Sksewell@umich.edu * @param asid The address space ID. 2022817Sksewell@umich.edu * @return Pointer to the cache block. 2032817Sksewell@umich.edu */ 2042817Sksewell@umich.edu FALRUBlk* findBlock(Addr addr) const; 2052817Sksewell@umich.edu 2062817Sksewell@umich.edu /** 2072817Sksewell@umich.edu * Find a replacement block for the address provided. 2082817Sksewell@umich.edu * @param pkt The request to a find a replacement candidate for. 2092817Sksewell@umich.edu * @param writebacks List for any writebacks to be performed. 2102817Sksewell@umich.edu * @return The block to place the replacement in. 2112817Sksewell@umich.edu */ 2122817Sksewell@umich.edu FALRUBlk* findVictim(Addr addr, PacketList & writebacks); 2132817Sksewell@umich.edu 2142817Sksewell@umich.edu void insertBlock(Addr addr, BlkType *blk, int context_src); 2152817Sksewell@umich.edu 2162817Sksewell@umich.edu /** 2172817Sksewell@umich.edu * Return the hit latency of this cache. 2182817Sksewell@umich.edu * @return The hit latency. 2192817Sksewell@umich.edu */ 2202817Sksewell@umich.edu Cycles getHitLatency() const 2212817Sksewell@umich.edu { 2222817Sksewell@umich.edu return hitLatency; 2232817Sksewell@umich.edu } 2242817Sksewell@umich.edu 2252817Sksewell@umich.edu /** 2262817Sksewell@umich.edu * Return the block size of this cache. 2272817Sksewell@umich.edu * @return The block size. 2282817Sksewell@umich.edu */ 2292817Sksewell@umich.edu unsigned 2302817Sksewell@umich.edu getBlockSize() const 2312817Sksewell@umich.edu { 2322817Sksewell@umich.edu return blkSize; 2332817Sksewell@umich.edu } 2342817Sksewell@umich.edu 2352817Sksewell@umich.edu /** 2362817Sksewell@umich.edu * Return the subblock size of this cache, always the block size. 2372817Sksewell@umich.edu * @return The block size. 2382817Sksewell@umich.edu */ 2392817Sksewell@umich.edu unsigned 2402817Sksewell@umich.edu getSubBlockSize() const 2412817Sksewell@umich.edu { 2423126Sktlim@umich.edu return blkSize; 2433126Sktlim@umich.edu } 2443126Sktlim@umich.edu 2452817Sksewell@umich.edu /** 2462817Sksewell@umich.edu * Align an address to the block size. 2472817Sksewell@umich.edu * @param addr the address to align. 2482817Sksewell@umich.edu * @return The aligned address. 2493126Sktlim@umich.edu */ 2503126Sktlim@umich.edu Addr blkAlign(Addr addr) const 2513126Sktlim@umich.edu { 2522817Sksewell@umich.edu return (addr & ~(Addr)(blkSize-1)); 2532817Sksewell@umich.edu } 2542817Sksewell@umich.edu 2552817Sksewell@umich.edu /** 2562817Sksewell@umich.edu * Generate the tag from the addres. For fully associative this is just the 2572817Sksewell@umich.edu * block address. 2582817Sksewell@umich.edu * @param addr The address to get the tag from. 2592817Sksewell@umich.edu * @return The tag. 2602817Sksewell@umich.edu */ 2612817Sksewell@umich.edu Addr extractTag(Addr addr) const 2622817Sksewell@umich.edu { 2632817Sksewell@umich.edu return blkAlign(addr); 2642817Sksewell@umich.edu } 2652817Sksewell@umich.edu 2662817Sksewell@umich.edu /** 2672817Sksewell@umich.edu * Return the set of an address. Only one set in a fully associative cache. 2682817Sksewell@umich.edu * @param addr The address to get the set from. 2692817Sksewell@umich.edu * @return 0. 2702817Sksewell@umich.edu */ 2712817Sksewell@umich.edu int extractSet(Addr addr) const 2722817Sksewell@umich.edu { 2732817Sksewell@umich.edu return 0; 2742817Sksewell@umich.edu } 2752817Sksewell@umich.edu 2762817Sksewell@umich.edu /** 2772817Sksewell@umich.edu * Calculate the block offset of an address. 2782817Sksewell@umich.edu * @param addr the address to get the offset of. 2792817Sksewell@umich.edu * @return the block offset. 2802817Sksewell@umich.edu */ 2812817Sksewell@umich.edu int extractBlkOffset(Addr addr) const 2822817Sksewell@umich.edu { 2832817Sksewell@umich.edu return (addr & (Addr)(blkSize-1)); 2842817Sksewell@umich.edu } 2852817Sksewell@umich.edu 2862817Sksewell@umich.edu /** 2872817Sksewell@umich.edu * Regenerate the block address from the tag and the set. 2882817Sksewell@umich.edu * @param tag The tag of the block. 2892817Sksewell@umich.edu * @param set The set the block belongs to. 2902986Sgblack@eecs.umich.edu * @return the block address. 2912817Sksewell@umich.edu */ 2922817Sksewell@umich.edu Addr regenerateBlkAddr(Addr tag, int set) const 2932817Sksewell@umich.edu { 2942817Sksewell@umich.edu return (tag); 2952817Sksewell@umich.edu } 2962817Sksewell@umich.edu 2972817Sksewell@umich.edu /** 2982817Sksewell@umich.edu *iterated through all blocks and clear all locks 2992817Sksewell@umich.edu *Needed to clear all lock tracking at once 3002817Sksewell@umich.edu */ 3012817Sksewell@umich.edu virtual void clearLocks(); 3022817Sksewell@umich.edu 3032817Sksewell@umich.edu /** 3042817Sksewell@umich.edu * Visit each block in the tag store and apply a visitor to the 3052817Sksewell@umich.edu * block. 3062817Sksewell@umich.edu * 3072817Sksewell@umich.edu * The visitor should be a function (or object that behaves like a 3082817Sksewell@umich.edu * function) that takes a cache block reference as its parameter 3092817Sksewell@umich.edu * and returns a bool. A visitor can request the traversal to be 3102817Sksewell@umich.edu * stopped by returning false, returning true causes it to be 3112817Sksewell@umich.edu * called for the next block in the tag store. 3122817Sksewell@umich.edu * 3132986Sgblack@eecs.umich.edu * \param visitor Visitor to call on each block. 3142817Sksewell@umich.edu */ 3152817Sksewell@umich.edu template <typename V> 3162817Sksewell@umich.edu void forEachBlk(V &visitor) { 3172817Sksewell@umich.edu for (int i = 0; i < numBlocks; i++) { 3182817Sksewell@umich.edu if (!visitor(blks[i])) 3192817Sksewell@umich.edu return; 3202817Sksewell@umich.edu } 3212817Sksewell@umich.edu } 3222817Sksewell@umich.edu}; 3232817Sksewell@umich.edu 3242817Sksewell@umich.edu#endif // __MEM_CACHE_TAGS_FA_LRU_HH__ 3252817Sksewell@umich.edu