fa_lru.hh revision 11722
12810Srdreslin@umich.edu/* 29796Sprakash.ramrakhyani@arm.com * Copyright (c) 2012-2013 ARM Limited 39347SAndreas.Sandberg@arm.com * All rights reserved. 49347SAndreas.Sandberg@arm.com * 59347SAndreas.Sandberg@arm.com * The license below extends only to copyright in the software and shall 69347SAndreas.Sandberg@arm.com * not be construed as granting a license to any other intellectual 79347SAndreas.Sandberg@arm.com * property including but not limited to intellectual property relating 89347SAndreas.Sandberg@arm.com * to a hardware implementation of the functionality of the software 99347SAndreas.Sandberg@arm.com * licensed hereunder. You may use the software subject to the license 109347SAndreas.Sandberg@arm.com * terms below provided that you ensure that this notice is replicated 119347SAndreas.Sandberg@arm.com * unmodified and in its entirety in all distributions of the software, 129347SAndreas.Sandberg@arm.com * modified or unmodified, in source code or in binary form. 139347SAndreas.Sandberg@arm.com * 142810Srdreslin@umich.edu * Copyright (c) 2003-2005 The Regents of The University of Michigan 152810Srdreslin@umich.edu * All rights reserved. 162810Srdreslin@umich.edu * 172810Srdreslin@umich.edu * Redistribution and use in source and binary forms, with or without 182810Srdreslin@umich.edu * modification, are permitted provided that the following conditions are 192810Srdreslin@umich.edu * met: redistributions of source code must retain the above copyright 202810Srdreslin@umich.edu * notice, this list of conditions and the following disclaimer; 212810Srdreslin@umich.edu * redistributions in binary form must reproduce the above copyright 222810Srdreslin@umich.edu * notice, this list of conditions and the following disclaimer in the 232810Srdreslin@umich.edu * documentation and/or other materials provided with the distribution; 242810Srdreslin@umich.edu * neither the name of the copyright holders nor the names of its 252810Srdreslin@umich.edu * contributors may be used to endorse or promote products derived from 262810Srdreslin@umich.edu * this software without specific prior written permission. 272810Srdreslin@umich.edu * 282810Srdreslin@umich.edu * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 292810Srdreslin@umich.edu * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 302810Srdreslin@umich.edu * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 312810Srdreslin@umich.edu * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 322810Srdreslin@umich.edu * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 332810Srdreslin@umich.edu * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 342810Srdreslin@umich.edu * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 352810Srdreslin@umich.edu * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 362810Srdreslin@umich.edu * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 372810Srdreslin@umich.edu * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 382810Srdreslin@umich.edu * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 392810Srdreslin@umich.edu * 402810Srdreslin@umich.edu * Authors: Erik Hallnor 412810Srdreslin@umich.edu */ 422810Srdreslin@umich.edu 432810Srdreslin@umich.edu/** 442810Srdreslin@umich.edu * @file 452810Srdreslin@umich.edu * Declaration of a fully associative LRU tag store. 462810Srdreslin@umich.edu */ 472810Srdreslin@umich.edu 486216Snate@binkert.org#ifndef __MEM_CACHE_TAGS_FA_LRU_HH__ 496216Snate@binkert.org#define __MEM_CACHE_TAGS_FA_LRU_HH__ 502810Srdreslin@umich.edu 512810Srdreslin@umich.edu#include <list> 5211168Sandreas.hansson@arm.com#include <unordered_map> 532810Srdreslin@umich.edu 5411722Ssophiane.senni@gmail.com#include "mem/cache/base.hh" 5511486Snikos.nikoleris@arm.com#include "mem/cache/blk.hh" 568229Snate@binkert.org#include "mem/cache/tags/base.hh" 572810Srdreslin@umich.edu#include "mem/packet.hh" 589796Sprakash.ramrakhyani@arm.com#include "params/FALRU.hh" 592810Srdreslin@umich.edu 602810Srdreslin@umich.edu/** 612810Srdreslin@umich.edu * A fully associative cache block. 622810Srdreslin@umich.edu */ 632810Srdreslin@umich.educlass FALRUBlk : public CacheBlk 642810Srdreslin@umich.edu{ 652810Srdreslin@umich.edupublic: 662810Srdreslin@umich.edu /** The previous block in LRU order. */ 672810Srdreslin@umich.edu FALRUBlk *prev; 682810Srdreslin@umich.edu /** The next block in LRU order. */ 692810Srdreslin@umich.edu FALRUBlk *next; 702810Srdreslin@umich.edu /** Has this block been touched? */ 712810Srdreslin@umich.edu bool isTouched; 722810Srdreslin@umich.edu 732810Srdreslin@umich.edu /** 742810Srdreslin@umich.edu * A bit mask of the sizes of cache that this block is resident in. 752810Srdreslin@umich.edu * Each bit represents a power of 2 in MB size cache. 762810Srdreslin@umich.edu * If bit 0 is set, this block is in a 1MB cache 772810Srdreslin@umich.edu * If bit 2 is set, this block is in a 4MB cache, etc. 782810Srdreslin@umich.edu * There is one bit for each cache smaller than the full size (default 792810Srdreslin@umich.edu * 16MB). 802810Srdreslin@umich.edu */ 812810Srdreslin@umich.edu int inCache; 822810Srdreslin@umich.edu}; 832810Srdreslin@umich.edu 842810Srdreslin@umich.edu/** 852810Srdreslin@umich.edu * A fully associative LRU cache. Keeps statistics for accesses to a number of 862810Srdreslin@umich.edu * cache sizes at once. 872810Srdreslin@umich.edu */ 882810Srdreslin@umich.educlass FALRU : public BaseTags 892810Srdreslin@umich.edu{ 902810Srdreslin@umich.edu public: 912810Srdreslin@umich.edu /** Typedef the block type used in this class. */ 922810Srdreslin@umich.edu typedef FALRUBlk BlkType; 932810Srdreslin@umich.edu /** Typedef a list of pointers to the local block type. */ 942810Srdreslin@umich.edu typedef std::list<FALRUBlk*> BlkList; 956227Snate@binkert.org 962810Srdreslin@umich.edu protected: 972810Srdreslin@umich.edu /** Array of pointers to blocks at the cache size boundaries. */ 982810Srdreslin@umich.edu FALRUBlk **cacheBoundaries; 992810Srdreslin@umich.edu /** A mask for the FALRUBlk::inCache bits. */ 1002810Srdreslin@umich.edu int cacheMask; 1012810Srdreslin@umich.edu /** The number of different size caches being tracked. */ 1026227Snate@binkert.org unsigned numCaches; 1032810Srdreslin@umich.edu 1042810Srdreslin@umich.edu /** The cache blocks. */ 1052810Srdreslin@umich.edu FALRUBlk *blks; 1062810Srdreslin@umich.edu 1072810Srdreslin@umich.edu /** The MRU block. */ 1082810Srdreslin@umich.edu FALRUBlk *head; 1092810Srdreslin@umich.edu /** The LRU block. */ 1102810Srdreslin@umich.edu FALRUBlk *tail; 1112810Srdreslin@umich.edu 1122810Srdreslin@umich.edu /** Hash table type mapping addresses to cache block pointers. */ 11311168Sandreas.hansson@arm.com typedef std::unordered_map<Addr, FALRUBlk *, std::hash<Addr> > hash_t; 1142810Srdreslin@umich.edu /** Iterator into the address hash table. */ 1152810Srdreslin@umich.edu typedef hash_t::const_iterator tagIterator; 1162810Srdreslin@umich.edu 1172810Srdreslin@umich.edu /** The address hash table. */ 1182810Srdreslin@umich.edu hash_t tagHash; 1192810Srdreslin@umich.edu 1202810Srdreslin@umich.edu /** 1212810Srdreslin@umich.edu * Find the cache block for the given address. 1222810Srdreslin@umich.edu * @param addr The address to find. 1232810Srdreslin@umich.edu * @return The cache block of the address, if any. 1242810Srdreslin@umich.edu */ 1252810Srdreslin@umich.edu FALRUBlk * hashLookup(Addr addr) const; 1262810Srdreslin@umich.edu 1272810Srdreslin@umich.edu /** 1282810Srdreslin@umich.edu * Move a cache block to the MRU position. 1292810Srdreslin@umich.edu * @param blk The block to promote. 1302810Srdreslin@umich.edu */ 1312810Srdreslin@umich.edu void moveToHead(FALRUBlk *blk); 1322810Srdreslin@umich.edu 1332810Srdreslin@umich.edu /** 1342810Srdreslin@umich.edu * Check to make sure all the cache boundaries are still where they should 1352810Srdreslin@umich.edu * be. Used for debugging. 1362810Srdreslin@umich.edu * @return True if everything is correct. 1372810Srdreslin@umich.edu */ 1382810Srdreslin@umich.edu bool check(); 1392810Srdreslin@umich.edu 1402810Srdreslin@umich.edu /** 1412810Srdreslin@umich.edu * @defgroup FALRUStats Fully Associative LRU specific statistics 1422810Srdreslin@umich.edu * The FA lru stack lets us track multiple cache sizes at once. These 1432810Srdreslin@umich.edu * statistics track the hits and misses for different cache sizes. 1442810Srdreslin@umich.edu * @{ 1452810Srdreslin@umich.edu */ 1462810Srdreslin@umich.edu 1472810Srdreslin@umich.edu /** Hits in each cache size >= 128K. */ 1485999Snate@binkert.org Stats::Vector hits; 1492810Srdreslin@umich.edu /** Misses in each cache size >= 128K. */ 1505999Snate@binkert.org Stats::Vector misses; 1512810Srdreslin@umich.edu /** Total number of accesses. */ 1525999Snate@binkert.org Stats::Scalar accesses; 1532810Srdreslin@umich.edu 1542810Srdreslin@umich.edu /** 1552810Srdreslin@umich.edu * @} 1562810Srdreslin@umich.edu */ 1572810Srdreslin@umich.edu 1582810Srdreslin@umich.edupublic: 1599796Sprakash.ramrakhyani@arm.com 1609796Sprakash.ramrakhyani@arm.com typedef FALRUParams Params; 1619796Sprakash.ramrakhyani@arm.com 1622810Srdreslin@umich.edu /** 1632810Srdreslin@umich.edu * Construct and initialize this cache tagstore. 1642810Srdreslin@umich.edu */ 1659796Sprakash.ramrakhyani@arm.com FALRU(const Params *p); 1669086Sandreas.hansson@arm.com ~FALRU(); 1672810Srdreslin@umich.edu 1682810Srdreslin@umich.edu /** 1692810Srdreslin@umich.edu * Register the stats for this object. 1702810Srdreslin@umich.edu * @param name The name to prepend to the stats name. 1712810Srdreslin@umich.edu */ 17211169Sandreas.hansson@arm.com void regStats() override; 1732810Srdreslin@umich.edu 1742810Srdreslin@umich.edu /** 1753862Sstever@eecs.umich.edu * Invalidate a cache block. 1763862Sstever@eecs.umich.edu * @param blk The block to invalidate. 1772810Srdreslin@umich.edu */ 17811169Sandreas.hansson@arm.com void invalidate(CacheBlk *blk) override; 1792810Srdreslin@umich.edu 1802810Srdreslin@umich.edu /** 18111483Snikos.nikoleris@arm.com * Access block and update replacement data. May not succeed, in which 18211484Snikos.nikoleris@arm.com * case nullptr pointer is returned. This has all the implications of a 18311484Snikos.nikoleris@arm.com * cache access and should only be used as such. 1845716Shsul@eecs.umich.edu * Returns the access latency and inCache flags as a side effect. 1852810Srdreslin@umich.edu * @param addr The address to look for. 18610028SGiacomo.Gabrielli@arm.com * @param is_secure True if the target memory space is secure. 1872810Srdreslin@umich.edu * @param asid The address space ID. 1882810Srdreslin@umich.edu * @param lat The latency of the access. 1892810Srdreslin@umich.edu * @param inCache The FALRUBlk::inCache flags. 1902810Srdreslin@umich.edu * @return Pointer to the cache block. 1912810Srdreslin@umich.edu */ 19210815Sdavid.guillen@arm.com CacheBlk* accessBlock(Addr addr, bool is_secure, Cycles &lat, 19310815Sdavid.guillen@arm.com int context_src, int *inCache); 19410815Sdavid.guillen@arm.com 19510815Sdavid.guillen@arm.com /** 19610815Sdavid.guillen@arm.com * Just a wrapper of above function to conform with the base interface. 19710815Sdavid.guillen@arm.com */ 19810815Sdavid.guillen@arm.com CacheBlk* accessBlock(Addr addr, bool is_secure, Cycles &lat, 19911169Sandreas.hansson@arm.com int context_src) override; 2002810Srdreslin@umich.edu 2012810Srdreslin@umich.edu /** 2022810Srdreslin@umich.edu * Find the block in the cache, do not update the replacement data. 2032810Srdreslin@umich.edu * @param addr The address to look for. 20410028SGiacomo.Gabrielli@arm.com * @param is_secure True if the target memory space is secure. 2052810Srdreslin@umich.edu * @param asid The address space ID. 2062810Srdreslin@umich.edu * @return Pointer to the cache block. 2072810Srdreslin@umich.edu */ 20811169Sandreas.hansson@arm.com CacheBlk* findBlock(Addr addr, bool is_secure) const override; 2092810Srdreslin@umich.edu 2102810Srdreslin@umich.edu /** 2112810Srdreslin@umich.edu * Find a replacement block for the address provided. 2122982Sstever@eecs.umich.edu * @param pkt The request to a find a replacement candidate for. 2132810Srdreslin@umich.edu * @return The block to place the replacement in. 2142810Srdreslin@umich.edu */ 21511169Sandreas.hansson@arm.com CacheBlk* findVictim(Addr addr) override; 2165717Shsul@eecs.umich.edu 21711169Sandreas.hansson@arm.com void insertBlock(PacketPtr pkt, CacheBlk *blk) override; 2182810Srdreslin@umich.edu 2192810Srdreslin@umich.edu /** 2202810Srdreslin@umich.edu * Return the block size of this cache. 2212810Srdreslin@umich.edu * @return The block size. 2222810Srdreslin@umich.edu */ 2236227Snate@binkert.org unsigned 2246227Snate@binkert.org getBlockSize() const 2252810Srdreslin@umich.edu { 2262810Srdreslin@umich.edu return blkSize; 2272810Srdreslin@umich.edu } 2282810Srdreslin@umich.edu 2292810Srdreslin@umich.edu /** 2302810Srdreslin@umich.edu * Return the subblock size of this cache, always the block size. 2312810Srdreslin@umich.edu * @return The block size. 2322810Srdreslin@umich.edu */ 2336227Snate@binkert.org unsigned 2346227Snate@binkert.org getSubBlockSize() const 2352810Srdreslin@umich.edu { 2362810Srdreslin@umich.edu return blkSize; 2372810Srdreslin@umich.edu } 2382810Srdreslin@umich.edu 2392810Srdreslin@umich.edu /** 24010941Sdavid.guillen@arm.com * Return the number of sets this cache has 24110941Sdavid.guillen@arm.com * @return The number of sets. 24210941Sdavid.guillen@arm.com */ 24310941Sdavid.guillen@arm.com unsigned 24411169Sandreas.hansson@arm.com getNumSets() const override 24510941Sdavid.guillen@arm.com { 24610941Sdavid.guillen@arm.com return 1; 24710941Sdavid.guillen@arm.com } 24810941Sdavid.guillen@arm.com 24910941Sdavid.guillen@arm.com /** 25010941Sdavid.guillen@arm.com * Return the number of ways this cache has 25110941Sdavid.guillen@arm.com * @return The number of ways. 25210941Sdavid.guillen@arm.com */ 25310941Sdavid.guillen@arm.com unsigned 25411169Sandreas.hansson@arm.com getNumWays() const override 25510941Sdavid.guillen@arm.com { 25610941Sdavid.guillen@arm.com return numBlocks; 25710941Sdavid.guillen@arm.com } 25810941Sdavid.guillen@arm.com 25910941Sdavid.guillen@arm.com /** 26010941Sdavid.guillen@arm.com * Find the cache block given set and way 26110941Sdavid.guillen@arm.com * @param set The set of the block. 26210941Sdavid.guillen@arm.com * @param way The way of the block. 26310941Sdavid.guillen@arm.com * @return The cache block. 26410941Sdavid.guillen@arm.com */ 26511169Sandreas.hansson@arm.com CacheBlk* findBlockBySetAndWay(int set, int way) const override; 26610941Sdavid.guillen@arm.com 26710941Sdavid.guillen@arm.com /** 2682810Srdreslin@umich.edu * Align an address to the block size. 2692810Srdreslin@umich.edu * @param addr the address to align. 2702810Srdreslin@umich.edu * @return The aligned address. 2712810Srdreslin@umich.edu */ 2722810Srdreslin@umich.edu Addr blkAlign(Addr addr) const 2732810Srdreslin@umich.edu { 2742810Srdreslin@umich.edu return (addr & ~(Addr)(blkSize-1)); 2752810Srdreslin@umich.edu } 2762810Srdreslin@umich.edu 2772810Srdreslin@umich.edu /** 2782810Srdreslin@umich.edu * Generate the tag from the addres. For fully associative this is just the 2792810Srdreslin@umich.edu * block address. 2802810Srdreslin@umich.edu * @param addr The address to get the tag from. 2812810Srdreslin@umich.edu * @return The tag. 2822810Srdreslin@umich.edu */ 28311169Sandreas.hansson@arm.com Addr extractTag(Addr addr) const override 2842810Srdreslin@umich.edu { 2852810Srdreslin@umich.edu return blkAlign(addr); 2862810Srdreslin@umich.edu } 2872810Srdreslin@umich.edu 2882810Srdreslin@umich.edu /** 2892810Srdreslin@umich.edu * Return the set of an address. Only one set in a fully associative cache. 2902810Srdreslin@umich.edu * @param addr The address to get the set from. 2912810Srdreslin@umich.edu * @return 0. 2922810Srdreslin@umich.edu */ 29311169Sandreas.hansson@arm.com int extractSet(Addr addr) const override 2942810Srdreslin@umich.edu { 2952810Srdreslin@umich.edu return 0; 2962810Srdreslin@umich.edu } 2972810Srdreslin@umich.edu 2982810Srdreslin@umich.edu /** 2992810Srdreslin@umich.edu * Regenerate the block address from the tag and the set. 3002810Srdreslin@umich.edu * @param tag The tag of the block. 3012810Srdreslin@umich.edu * @param set The set the block belongs to. 3022810Srdreslin@umich.edu * @return the block address. 3032810Srdreslin@umich.edu */ 30411169Sandreas.hansson@arm.com Addr regenerateBlkAddr(Addr tag, unsigned set) const override 3052810Srdreslin@umich.edu { 3062810Srdreslin@umich.edu return (tag); 3072810Srdreslin@umich.edu } 3087612SGene.Wu@arm.com 3097612SGene.Wu@arm.com /** 3109663Suri.wiener@arm.com * @todo Implement as in lru. Currently not used 3119663Suri.wiener@arm.com */ 31211169Sandreas.hansson@arm.com virtual std::string print() const override { return ""; } 3139663Suri.wiener@arm.com 3149663Suri.wiener@arm.com /** 3159347SAndreas.Sandberg@arm.com * Visit each block in the tag store and apply a visitor to the 3169347SAndreas.Sandberg@arm.com * block. 3179347SAndreas.Sandberg@arm.com * 3189347SAndreas.Sandberg@arm.com * The visitor should be a function (or object that behaves like a 3199347SAndreas.Sandberg@arm.com * function) that takes a cache block reference as its parameter 3209347SAndreas.Sandberg@arm.com * and returns a bool. A visitor can request the traversal to be 3219347SAndreas.Sandberg@arm.com * stopped by returning false, returning true causes it to be 3229347SAndreas.Sandberg@arm.com * called for the next block in the tag store. 3239347SAndreas.Sandberg@arm.com * 3249347SAndreas.Sandberg@arm.com * \param visitor Visitor to call on each block. 3259347SAndreas.Sandberg@arm.com */ 32611168Sandreas.hansson@arm.com void forEachBlk(CacheBlkVisitor &visitor) override { 3279347SAndreas.Sandberg@arm.com for (int i = 0; i < numBlocks; i++) { 3289347SAndreas.Sandberg@arm.com if (!visitor(blks[i])) 3299347SAndreas.Sandberg@arm.com return; 3309347SAndreas.Sandberg@arm.com } 3319347SAndreas.Sandberg@arm.com } 3329796Sprakash.ramrakhyani@arm.com 3332810Srdreslin@umich.edu}; 3342810Srdreslin@umich.edu 3356216Snate@binkert.org#endif // __MEM_CACHE_TAGS_FA_LRU_HH__ 336