fa_lru.hh revision 12728:57bdea4f96aa
12810SN/A/* 212728Snikos.nikoleris@arm.com * Copyright (c) 2012-2013,2016,2018 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 * 142810SN/A * Copyright (c) 2003-2005 The Regents of The University of Michigan 152810SN/A * All rights reserved. 162810SN/A * 172810SN/A * Redistribution and use in source and binary forms, with or without 182810SN/A * modification, are permitted provided that the following conditions are 192810SN/A * met: redistributions of source code must retain the above copyright 202810SN/A * notice, this list of conditions and the following disclaimer; 212810SN/A * redistributions in binary form must reproduce the above copyright 222810SN/A * notice, this list of conditions and the following disclaimer in the 232810SN/A * documentation and/or other materials provided with the distribution; 242810SN/A * neither the name of the copyright holders nor the names of its 252810SN/A * contributors may be used to endorse or promote products derived from 262810SN/A * this software without specific prior written permission. 272810SN/A * 282810SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 292810SN/A * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 302810SN/A * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 312810SN/A * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 322810SN/A * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 332810SN/A * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 342810SN/A * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 352810SN/A * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 362810SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 372810SN/A * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 382810SN/A * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 392810SN/A * 402810SN/A * Authors: Erik Hallnor 412810SN/A * Nikos Nikoleris 422810SN/A */ 432810SN/A 442810SN/A/** 452810SN/A * @file 462810SN/A * Declaration of a fully associative LRU tag store. 472810SN/A */ 482810SN/A 4912492Sodanrc@yahoo.com.br#ifndef __MEM_CACHE_TAGS_FA_LRU_HH__ 5012492Sodanrc@yahoo.com.br#define __MEM_CACHE_TAGS_FA_LRU_HH__ 512810SN/A 5212727Snikos.nikoleris@arm.com#include <cstdint> 5312728Snikos.nikoleris@arm.com#include <functional> 542810SN/A#include <string> 558229Snate@binkert.org#include <unordered_map> 568229Snate@binkert.org 5712727Snikos.nikoleris@arm.com#include "base/bitfield.hh" 582810SN/A#include "base/intmath.hh" 5912727Snikos.nikoleris@arm.com#include "base/logging.hh" 6010815Sdavid.guillen@arm.com#include "base/statistics.hh" 6112727Snikos.nikoleris@arm.com#include "base/types.hh" 629796Sprakash.ramrakhyani@arm.com#include "mem/cache/blk.hh" 639796Sprakash.ramrakhyani@arm.com#include "mem/cache/tags/base.hh" 642810SN/A#include "mem/packet.hh" 652810SN/A#include "params/FALRU.hh" 662810SN/A 672810SN/A// Uncomment to enable sanity checks for the FALRU cache and the 682810SN/A// TrackedCaches class 692810SN/A//#define FALRU_DEBUG 709796Sprakash.ramrakhyani@arm.com 712810SN/A// A bitmask of the caches we are keeping track of. Currently the 722810SN/A// lowest bit is the smallest cache we are tracking, as it is 739796Sprakash.ramrakhyani@arm.com// specified by the corresponding parameter. The rest of the bits are 749796Sprakash.ramrakhyani@arm.com// for exponentially growing cache sizes. 7511893Snikos.nikoleris@arm.comtypedef uint32_t CachesMask; 7611893Snikos.nikoleris@arm.com 779796Sprakash.ramrakhyani@arm.com/** 789796Sprakash.ramrakhyani@arm.com * A fully associative cache block. 7911722Ssophiane.senni@gmail.com */ 8011722Ssophiane.senni@gmail.comclass FALRUBlk : public CacheBlk 8111722Ssophiane.senni@gmail.com{ 8211722Ssophiane.senni@gmail.com public: 8311722Ssophiane.senni@gmail.com /** The previous block in LRU order. */ 8411722Ssophiane.senni@gmail.com FALRUBlk *prev; 8511722Ssophiane.senni@gmail.com /** The next block in LRU order. */ 8610693SMarco.Balboni@ARM.com FALRUBlk *next; 872810SN/A 882810SN/A /** A bit mask of the caches that fit this block. */ 892810SN/A CachesMask inCachesMask; 902810SN/A}; 912810SN/A 922810SN/A/** 932810SN/A * A fully associative LRU cache. Keeps statistics for accesses to a number of 9412513Sodanrc@yahoo.com.br * cache sizes at once. 952810SN/A */ 962810SN/Aclass FALRU : public BaseTags 972810SN/A{ 986978SLisa.Hsu@amd.com public: 9912553Snikos.nikoleris@arm.com /** Typedef the block type used in this class. */ 1006978SLisa.Hsu@amd.com typedef FALRUBlk BlkType; 10112629Sodanrc@yahoo.com.br 10212629Sodanrc@yahoo.com.br protected: 10312629Sodanrc@yahoo.com.br /** The cache blocks. */ 1042810SN/A FALRUBlk *blks; 1052810SN/A 10612513Sodanrc@yahoo.com.br /** The MRU block. */ 1072810SN/A FALRUBlk *head; 1082810SN/A /** The LRU block. */ 1092810SN/A FALRUBlk *tail; 1102810SN/A 1112810SN/A /** Hash table type mapping addresses to cache block pointers. */ 1125999Snate@binkert.org typedef std::unordered_map<Addr, FALRUBlk *, std::hash<Addr> > hash_t; 1132810SN/A /** Iterator into the address hash table. */ 1142810SN/A typedef hash_t::const_iterator tagIterator; 1155999Snate@binkert.org 1162810SN/A /** The address hash table. */ 1172810SN/A hash_t tagHash; 1182810SN/A 1192810SN/A /** 1202810SN/A * Find the cache block for the given address. 1212810SN/A * @param addr The address to find. 1225999Snate@binkert.org * @return The cache block of the address, if any. 1232810SN/A */ 1242810SN/A FALRUBlk * hashLookup(Addr addr) const; 1252810SN/A 1262810SN/A /** 1272810SN/A * Move a cache block to the MRU position. 1282810SN/A * 1292810SN/A * @param blk The block to promote. 13012513Sodanrc@yahoo.com.br */ 1315999Snate@binkert.org void moveToHead(FALRUBlk *blk); 1326978SLisa.Hsu@amd.com 1338833Sdam.sunwoo@arm.com /** 1346978SLisa.Hsu@amd.com * Move a cache block to the LRU position. 1356978SLisa.Hsu@amd.com * 1368833Sdam.sunwoo@arm.com * @param blk The block to demote. 1376978SLisa.Hsu@amd.com */ 1386978SLisa.Hsu@amd.com void moveToTail(FALRUBlk *blk); 13910024Sdam.sunwoo@arm.com 14010024Sdam.sunwoo@arm.com public: 14110024Sdam.sunwoo@arm.com typedef FALRUParams Params; 14210024Sdam.sunwoo@arm.com 14310024Sdam.sunwoo@arm.com /** 14410024Sdam.sunwoo@arm.com * Construct and initialize this cache tagstore. 14510024Sdam.sunwoo@arm.com */ 14610024Sdam.sunwoo@arm.com FALRU(const Params *p); 14710024Sdam.sunwoo@arm.com ~FALRU(); 14810025Stimothy.jones@arm.com 14910025Stimothy.jones@arm.com /** 15010025Stimothy.jones@arm.com * Register the stats for this object. 15110025Stimothy.jones@arm.com */ 15210025Stimothy.jones@arm.com void regStats() override; 1532810SN/A 1542810SN/A /** 1552810SN/A * Invalidate a cache block. 1562810SN/A * @param blk The block to invalidate. 1572810SN/A */ 1589796Sprakash.ramrakhyani@arm.com void invalidate(CacheBlk *blk) override; 1599796Sprakash.ramrakhyani@arm.com 1602810SN/A /** 1612810SN/A * Access block and update replacement data. May not succeed, in which 1622810SN/A * case nullptr pointer is returned. This has all the implications of a 1632810SN/A * cache access and should only be used as such. 1642810SN/A * Returns the access latency and inCachesMask flags as a side effect. 1652810SN/A * @param addr The address to look for. 1662810SN/A * @param is_secure True if the target memory space is secure. 1679796Sprakash.ramrakhyani@arm.com * @param lat The latency of the access. 1682810SN/A * @param in_cache_mask Mask indicating the caches in which the blk fits. 1692810SN/A * @return Pointer to the cache block. 1702810SN/A */ 1712810SN/A CacheBlk* accessBlock(Addr addr, bool is_secure, Cycles &lat, 1722810SN/A CachesMask *in_cache_mask); 1739796Sprakash.ramrakhyani@arm.com 1742810SN/A /** 1759796Sprakash.ramrakhyani@arm.com * Just a wrapper of above function to conform with the base interface. 1762810SN/A */ 1772810SN/A CacheBlk* accessBlock(Addr addr, bool is_secure, Cycles &lat) override; 1782810SN/A 1792810SN/A /** 1802810SN/A * Find the block in the cache, do not update the replacement data. 18112728Snikos.nikoleris@arm.com * @param addr The address to look for. 1827612SGene.Wu@arm.com * @param is_secure True if the target memory space is secure. 1837612SGene.Wu@arm.com * @param asid The address space ID. 18410024Sdam.sunwoo@arm.com * @return Pointer to the cache block. 18510024Sdam.sunwoo@arm.com */ 18612728Snikos.nikoleris@arm.com CacheBlk* findBlock(Addr addr, bool is_secure) const override; 18710024Sdam.sunwoo@arm.com 18810024Sdam.sunwoo@arm.com /** 1899663Suri.wiener@arm.com * Find replacement victim based on address. 1909663Suri.wiener@arm.com * 19112728Snikos.nikoleris@arm.com * @param addr Address to find a victim for. 19210815Sdavid.guillen@arm.com * @return Cache block to be replaced. 19310815Sdavid.guillen@arm.com */ 19410815Sdavid.guillen@arm.com CacheBlk* findVictim(Addr addr) override; 19510815Sdavid.guillen@arm.com 19610815Sdavid.guillen@arm.com /** 19710815Sdavid.guillen@arm.com * Insert the new block into the cache and update replacement data. 19810815Sdavid.guillen@arm.com * 19912743Sodanrc@yahoo.com.br * @param pkt Packet holding the address to update 20012743Sodanrc@yahoo.com.br * @param blk The block to update. 20112743Sodanrc@yahoo.com.br */ 20212743Sodanrc@yahoo.com.br void insertBlock(PacketPtr pkt, CacheBlk *blk) override; 20312743Sodanrc@yahoo.com.br 20412743Sodanrc@yahoo.com.br /** 20512743Sodanrc@yahoo.com.br * Find the cache block given set and way 20612743Sodanrc@yahoo.com.br * @param set The set of the block. 20712743Sodanrc@yahoo.com.br * @param way The way of the block. 20811893Snikos.nikoleris@arm.com * @return The cache block. 20911893Snikos.nikoleris@arm.com */ 21011893Snikos.nikoleris@arm.com CacheBlk* findBlockBySetAndWay(int set, int way) const override; 21111893Snikos.nikoleris@arm.com 21211893Snikos.nikoleris@arm.com /** 21311893Snikos.nikoleris@arm.com * Generate the tag from the addres. For fully associative this is just the 21411893Snikos.nikoleris@arm.com * block address. 21511893Snikos.nikoleris@arm.com * @param addr The address to get the tag from. 21611893Snikos.nikoleris@arm.com * @return The tag. 21711893Snikos.nikoleris@arm.com */ 21810815Sdavid.guillen@arm.com Addr extractTag(Addr addr) const override 21910815Sdavid.guillen@arm.com { 22010815Sdavid.guillen@arm.com return blkAlign(addr); 22110815Sdavid.guillen@arm.com } 22210815Sdavid.guillen@arm.com 22310815Sdavid.guillen@arm.com /** 22411893Snikos.nikoleris@arm.com * Return the set of an address. Only one set in a fully associative cache. 22510815Sdavid.guillen@arm.com * @param addr The address to get the set from. 22610815Sdavid.guillen@arm.com * @return 0. 22710941Sdavid.guillen@arm.com */ 22810941Sdavid.guillen@arm.com int extractSet(Addr addr) const override 22910941Sdavid.guillen@arm.com { 23010941Sdavid.guillen@arm.com return 0; 23110941Sdavid.guillen@arm.com } 23210941Sdavid.guillen@arm.com 23310941Sdavid.guillen@arm.com /** 23410941Sdavid.guillen@arm.com * Regenerate the block address from the tag. 23510941Sdavid.guillen@arm.com * 23610941Sdavid.guillen@arm.com * @param block The block. 23710941Sdavid.guillen@arm.com * @return the block address. 23810941Sdavid.guillen@arm.com */ 23910941Sdavid.guillen@arm.com Addr regenerateBlkAddr(const CacheBlk* blk) const override 24010941Sdavid.guillen@arm.com { 24110941Sdavid.guillen@arm.com return blk->tag; 24210941Sdavid.guillen@arm.com } 24310941Sdavid.guillen@arm.com 24410941Sdavid.guillen@arm.com void forEachBlk(std::function<void(CacheBlk &)> visitor) override { 24510941Sdavid.guillen@arm.com for (int i = 0; i < numBlocks; i++) { 24612566Snikos.nikoleris@arm.com visitor(blks[i]); 24712704Snikos.nikoleris@arm.com } 24812704Snikos.nikoleris@arm.com } 24912704Snikos.nikoleris@arm.com 25012566Snikos.nikoleris@arm.com bool anyBlk(std::function<bool(CacheBlk &)> visitor) override { 25112566Snikos.nikoleris@arm.com for (int i = 0; i < numBlocks; i++) { 25212566Snikos.nikoleris@arm.com if (visitor(blks[i])) { 25312566Snikos.nikoleris@arm.com return true; 25412566Snikos.nikoleris@arm.com } 25512704Snikos.nikoleris@arm.com } 25612566Snikos.nikoleris@arm.com return false; 25712566Snikos.nikoleris@arm.com } 25812704Snikos.nikoleris@arm.com 25912704Snikos.nikoleris@arm.com private: 26012704Snikos.nikoleris@arm.com /** 26112704Snikos.nikoleris@arm.com * Mechanism that allows us to simultaneously collect miss 26212566Snikos.nikoleris@arm.com * statistics for multiple caches. Currently, we keep track of 26310815Sdavid.guillen@arm.com * caches from a set minimum size of interest up to the actual 26412600Sodanrc@yahoo.com.br * cache size. 26512744Sodanrc@yahoo.com.br */ 26612744Sodanrc@yahoo.com.br class CacheTracking 26712744Sodanrc@yahoo.com.br { 26812744Sodanrc@yahoo.com.br public: 26912744Sodanrc@yahoo.com.br CacheTracking(unsigned min_size, unsigned max_size, 27012744Sodanrc@yahoo.com.br unsigned block_size) 27112744Sodanrc@yahoo.com.br : blkSize(block_size), 27212600Sodanrc@yahoo.com.br minTrackedSize(min_size), 27312600Sodanrc@yahoo.com.br numTrackedCaches(max_size > min_size ? 27412744Sodanrc@yahoo.com.br floorLog2(max_size) - floorLog2(min_size) : 0), 27512600Sodanrc@yahoo.com.br inAllCachesMask(mask(numTrackedCaches)), 27612600Sodanrc@yahoo.com.br boundaries(new FALRUBlk *[numTrackedCaches]) 27712744Sodanrc@yahoo.com.br { 27812744Sodanrc@yahoo.com.br fatal_if(numTrackedCaches > sizeof(CachesMask) * 8, 27912600Sodanrc@yahoo.com.br "Not enough bits (%s) in type CachesMask type to keep " 28011870Snikos.nikoleris@arm.com "track of %d caches\n", sizeof(CachesMask), 28110815Sdavid.guillen@arm.com numTrackedCaches); 28210815Sdavid.guillen@arm.com } 28310815Sdavid.guillen@arm.com 28412636Sodanrc@yahoo.com.br ~CacheTracking() 28512636Sodanrc@yahoo.com.br { 28612636Sodanrc@yahoo.com.br delete[] boundaries; 28712636Sodanrc@yahoo.com.br } 28812636Sodanrc@yahoo.com.br 28912636Sodanrc@yahoo.com.br /** 29012636Sodanrc@yahoo.com.br * Initialiaze cache blocks and the tracking mechanism 29110815Sdavid.guillen@arm.com * 29212574Sodanrc@yahoo.com.br * All blocks in the cache need to be initialized once. 29312574Sodanrc@yahoo.com.br * 29412574Sodanrc@yahoo.com.br * @param blk the MRU block 29512574Sodanrc@yahoo.com.br * @param blk the LRU block 29612574Sodanrc@yahoo.com.br */ 29712574Sodanrc@yahoo.com.br void init(FALRUBlk *head, FALRUBlk *tail); 29812574Sodanrc@yahoo.com.br 29910815Sdavid.guillen@arm.com /** 30012728Snikos.nikoleris@arm.com * Update boundaries as a block will be moved to the MRU. 30112728Snikos.nikoleris@arm.com * 30212728Snikos.nikoleris@arm.com * For all caches that didn't fit the block before moving it, 30312728Snikos.nikoleris@arm.com * we move their boundaries one block closer to the MRU. We 30412728Snikos.nikoleris@arm.com * also update InCacheMasks as neccessary. 30512728Snikos.nikoleris@arm.com * 30612728Snikos.nikoleris@arm.com * @param blk the block that will be moved to the head 30712728Snikos.nikoleris@arm.com */ 30812728Snikos.nikoleris@arm.com void moveBlockToHead(FALRUBlk *blk); 30912728Snikos.nikoleris@arm.com 31012728Snikos.nikoleris@arm.com /** 31112728Snikos.nikoleris@arm.com * Update boundaries as a block will be moved to the LRU. 31212728Snikos.nikoleris@arm.com * 31312728Snikos.nikoleris@arm.com * For all caches that fitted the block before moving it, we 31412728Snikos.nikoleris@arm.com * move their boundaries one block closer to the LRU. We 31512728Snikos.nikoleris@arm.com * also update InCacheMasks as neccessary. 31612728Snikos.nikoleris@arm.com * 31712728Snikos.nikoleris@arm.com * @param blk the block that will be moved to the head 31812728Snikos.nikoleris@arm.com */ 31912728Snikos.nikoleris@arm.com void moveBlockToTail(FALRUBlk *blk); 32012728Snikos.nikoleris@arm.com 32112728Snikos.nikoleris@arm.com /** 32212728Snikos.nikoleris@arm.com * Notify of a block access. 32312728Snikos.nikoleris@arm.com * 32412728Snikos.nikoleris@arm.com * This should be called every time a block is accessed and it 32512728Snikos.nikoleris@arm.com * updates statistics. If the input block is nullptr then we 32612728Snikos.nikoleris@arm.com * treat the access as a miss. The block's InCacheMask 32712728Snikos.nikoleris@arm.com * determines the caches in which the block fits. 32812728Snikos.nikoleris@arm.com * 32912728Snikos.nikoleris@arm.com * @param blk the block to record the access for 33012728Snikos.nikoleris@arm.com */ 33112728Snikos.nikoleris@arm.com void recordAccess(FALRUBlk *blk); 33212728Snikos.nikoleris@arm.com 33312728Snikos.nikoleris@arm.com /** 33412728Snikos.nikoleris@arm.com * Check that the tracking mechanism is in consistent state. 3352810SN/A * 3362810SN/A * Iterate from the head (MRU) to the tail (LRU) of the list 3372810SN/A * of blocks and assert the inCachesMask and the boundaries 3382810SN/A * are in consistent state. 3392810SN/A * 3402810SN/A * @param head the MRU block of the actual cache 3412810SN/A * @param head the LRU block of the actual cache 3422810SN/A */ 3432810SN/A void check(FALRUBlk *head, FALRUBlk *tail); 3442810SN/A 34510024Sdam.sunwoo@arm.com /** 34610024Sdam.sunwoo@arm.com * Register the stats for this object. 34710024Sdam.sunwoo@arm.com */ 34810024Sdam.sunwoo@arm.com void regStats(std::string name); 34910024Sdam.sunwoo@arm.com 35010024Sdam.sunwoo@arm.com private: 35110024Sdam.sunwoo@arm.com /** The size of the cache block */ 35210024Sdam.sunwoo@arm.com const unsigned blkSize; 35312492Sodanrc@yahoo.com.br /** The smallest cache we are tracking */ 354 const unsigned minTrackedSize; 355 /** The number of different size caches being tracked. */ 356 const int numTrackedCaches; 357 /** A mask for all cache being tracked. */ 358 const CachesMask inAllCachesMask; 359 /** Array of pointers to blocks at the cache boundaries. */ 360 FALRUBlk** boundaries; 361 362 protected: 363 /** 364 * @defgroup FALRUStats Fully Associative LRU specific statistics 365 * The FA lru stack lets us track multiple cache sizes at once. These 366 * statistics track the hits and misses for different cache sizes. 367 * @{ 368 */ 369 370 /** Hits in each cache */ 371 Stats::Vector hits; 372 /** Misses in each cache */ 373 Stats::Vector misses; 374 /** Total number of accesses */ 375 Stats::Scalar accesses; 376 377 /** 378 * @} 379 */ 380 }; 381 CacheTracking cacheTracking; 382}; 383 384#endif // __MEM_CACHE_TAGS_FA_LRU_HH__ 385