fa_lru.hh revision 12743
16908SBrad.Beckmann@amd.com/* 26908SBrad.Beckmann@amd.com * Copyright (c) 2012-2013,2016,2018 ARM Limited 36908SBrad.Beckmann@amd.com * All rights reserved. 46908SBrad.Beckmann@amd.com * 56908SBrad.Beckmann@amd.com * The license below extends only to copyright in the software and shall 66908SBrad.Beckmann@amd.com * not be construed as granting a license to any other intellectual 76908SBrad.Beckmann@amd.com * property including but not limited to intellectual property relating 86908SBrad.Beckmann@amd.com * to a hardware implementation of the functionality of the software 96908SBrad.Beckmann@amd.com * licensed hereunder. You may use the software subject to the license 106908SBrad.Beckmann@amd.com * terms below provided that you ensure that this notice is replicated 116908SBrad.Beckmann@amd.com * unmodified and in its entirety in all distributions of the software, 126908SBrad.Beckmann@amd.com * modified or unmodified, in source code or in binary form. 136908SBrad.Beckmann@amd.com * 146908SBrad.Beckmann@amd.com * Copyright (c) 2003-2005 The Regents of The University of Michigan 156908SBrad.Beckmann@amd.com * All rights reserved. 166908SBrad.Beckmann@amd.com * 176908SBrad.Beckmann@amd.com * Redistribution and use in source and binary forms, with or without 186908SBrad.Beckmann@amd.com * modification, are permitted provided that the following conditions are 196908SBrad.Beckmann@amd.com * met: redistributions of source code must retain the above copyright 206908SBrad.Beckmann@amd.com * notice, this list of conditions and the following disclaimer; 216908SBrad.Beckmann@amd.com * redistributions in binary form must reproduce the above copyright 226908SBrad.Beckmann@amd.com * notice, this list of conditions and the following disclaimer in the 236908SBrad.Beckmann@amd.com * documentation and/or other materials provided with the distribution; 246908SBrad.Beckmann@amd.com * neither the name of the copyright holders nor the names of its 256908SBrad.Beckmann@amd.com * contributors may be used to endorse or promote products derived from 266908SBrad.Beckmann@amd.com * this software without specific prior written permission. 276908SBrad.Beckmann@amd.com * 286908SBrad.Beckmann@amd.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 296908SBrad.Beckmann@amd.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 306908SBrad.Beckmann@amd.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 316908SBrad.Beckmann@amd.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 326908SBrad.Beckmann@amd.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 336908SBrad.Beckmann@amd.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 3412065Snikos.nikoleris@arm.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 3510529Smorr@cs.wisc.edu * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 366908SBrad.Beckmann@amd.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 376908SBrad.Beckmann@amd.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 3811019Sjthestness@gmail.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 396908SBrad.Beckmann@amd.com * 4011019Sjthestness@gmail.com * Authors: Erik Hallnor 4111019Sjthestness@gmail.com * Nikos Nikoleris 426908SBrad.Beckmann@amd.com */ 437538SBrad.Beckmann@amd.com 447539SBrad.Beckmann@amd.com/** 457539SBrad.Beckmann@amd.com * @file 467539SBrad.Beckmann@amd.com * Declaration of a fully associative LRU tag store. 477539SBrad.Beckmann@amd.com */ 487539SBrad.Beckmann@amd.com 497539SBrad.Beckmann@amd.com#ifndef __MEM_CACHE_TAGS_FA_LRU_HH__ 507561SBrad.Beckmann@amd.com#define __MEM_CACHE_TAGS_FA_LRU_HH__ 517561SBrad.Beckmann@amd.com 5210917Sbrandon.potter@amd.com#include <cstdint> 5312598Snikos.nikoleris@arm.com#include <functional> 5412598Snikos.nikoleris@arm.com#include <string> 5510917Sbrandon.potter@amd.com#include <unordered_map> 566908SBrad.Beckmann@amd.com 576908SBrad.Beckmann@amd.com#include "base/bitfield.hh" 586908SBrad.Beckmann@amd.com#include "base/intmath.hh" 596908SBrad.Beckmann@amd.com#include "base/logging.hh" 606908SBrad.Beckmann@amd.com#include "base/statistics.hh" 616908SBrad.Beckmann@amd.com#include "base/types.hh" 626908SBrad.Beckmann@amd.com#include "mem/cache/blk.hh" 636908SBrad.Beckmann@amd.com#include "mem/cache/tags/base.hh" 646908SBrad.Beckmann@amd.com#include "mem/packet.hh" 656908SBrad.Beckmann@amd.com#include "params/FALRU.hh" 6610917Sbrandon.potter@amd.com 676908SBrad.Beckmann@amd.com// Uncomment to enable sanity checks for the FALRU cache and the 686908SBrad.Beckmann@amd.com// TrackedCaches class 696908SBrad.Beckmann@amd.com//#define FALRU_DEBUG 706908SBrad.Beckmann@amd.com 716908SBrad.Beckmann@amd.com// A bitmask of the caches we are keeping track of. Currently the 726908SBrad.Beckmann@amd.com// lowest bit is the smallest cache we are tracking, as it is 736908SBrad.Beckmann@amd.com// specified by the corresponding parameter. The rest of the bits are 746908SBrad.Beckmann@amd.com// for exponentially growing cache sizes. 756908SBrad.Beckmann@amd.comtypedef uint32_t CachesMask; 766908SBrad.Beckmann@amd.com 776908SBrad.Beckmann@amd.com/** 786908SBrad.Beckmann@amd.com * A fully associative cache block. 796908SBrad.Beckmann@amd.com */ 807564SBrad.Beckmann@amd.comclass FALRUBlk : public CacheBlk 818180SBrad.Beckmann@amd.com{ 8210917Sbrandon.potter@amd.com public: 836908SBrad.Beckmann@amd.com /** The previous block in LRU order. */ 846908SBrad.Beckmann@amd.com FALRUBlk *prev; 856908SBrad.Beckmann@amd.com /** The next block in LRU order. */ 866908SBrad.Beckmann@amd.com FALRUBlk *next; 876908SBrad.Beckmann@amd.com 888180SBrad.Beckmann@amd.com /** A bit mask of the caches that fit this block. */ 898180SBrad.Beckmann@amd.com CachesMask inCachesMask; 906908SBrad.Beckmann@amd.com}; 918180SBrad.Beckmann@amd.com 928180SBrad.Beckmann@amd.com/** 936908SBrad.Beckmann@amd.com * A fully associative LRU cache. Keeps statistics for accesses to a number of 9411266SBrad.Beckmann@amd.com * cache sizes at once. 9511266SBrad.Beckmann@amd.com */ 9611266SBrad.Beckmann@amd.comclass FALRU : public BaseTags 9711266SBrad.Beckmann@amd.com{ 9811266SBrad.Beckmann@amd.com public: 9911266SBrad.Beckmann@amd.com /** Typedef the block type used in this class. */ 10011266SBrad.Beckmann@amd.com typedef FALRUBlk BlkType; 10111266SBrad.Beckmann@amd.com 10211266SBrad.Beckmann@amd.com protected: 10311266SBrad.Beckmann@amd.com /** The cache blocks. */ 10411266SBrad.Beckmann@amd.com FALRUBlk *blks; 1057539SBrad.Beckmann@amd.com 10611266SBrad.Beckmann@amd.com /** The MRU block. */ 10711266SBrad.Beckmann@amd.com FALRUBlk *head; 10811266SBrad.Beckmann@amd.com /** The LRU block. */ 10911266SBrad.Beckmann@amd.com FALRUBlk *tail; 11011266SBrad.Beckmann@amd.com 11111266SBrad.Beckmann@amd.com /** Hash table type mapping addresses to cache block pointers. */ 11211266SBrad.Beckmann@amd.com typedef std::unordered_map<Addr, FALRUBlk *, std::hash<Addr> > hash_t; 11311266SBrad.Beckmann@amd.com /** Iterator into the address hash table. */ 11411266SBrad.Beckmann@amd.com typedef hash_t::const_iterator tagIterator; 11511266SBrad.Beckmann@amd.com 11611266SBrad.Beckmann@amd.com /** The address hash table. */ 11711266SBrad.Beckmann@amd.com hash_t tagHash; 11811266SBrad.Beckmann@amd.com 11911266SBrad.Beckmann@amd.com /** 12011266SBrad.Beckmann@amd.com * Find the cache block for the given address. 12111266SBrad.Beckmann@amd.com * @param addr The address to find. 12211266SBrad.Beckmann@amd.com * @return The cache block of the address, if any. 12311266SBrad.Beckmann@amd.com */ 12411266SBrad.Beckmann@amd.com FALRUBlk * hashLookup(Addr addr) const; 1258322Ssteve.reinhardt@amd.com 1268322Ssteve.reinhardt@amd.com /** 12710116Snilay@cs.wisc.edu * Move a cache block to the MRU position. 1288322Ssteve.reinhardt@amd.com * 1296908SBrad.Beckmann@amd.com * @param blk The block to promote. 1306908SBrad.Beckmann@amd.com */ 1316908SBrad.Beckmann@amd.com void moveToHead(FALRUBlk *blk); 1326908SBrad.Beckmann@amd.com 13310311Snilay@cs.wisc.edu /** 13411022Sjthestness@gmail.com * Move a cache block to the LRU position. 13511022Sjthestness@gmail.com * 13611022Sjthestness@gmail.com * @param blk The block to demote. 13711022Sjthestness@gmail.com */ 13811022Sjthestness@gmail.com void moveToTail(FALRUBlk *blk); 13911022Sjthestness@gmail.com 14010311Snilay@cs.wisc.edu public: 14111022Sjthestness@gmail.com typedef FALRUParams Params; 14211022Sjthestness@gmail.com 14311022Sjthestness@gmail.com /** 14411022Sjthestness@gmail.com * Construct and initialize this cache tagstore. 14511022Sjthestness@gmail.com */ 14611022Sjthestness@gmail.com FALRU(const Params *p); 14711022Sjthestness@gmail.com ~FALRU(); 14810311Snilay@cs.wisc.edu 14910311Snilay@cs.wisc.edu /** 1508180SBrad.Beckmann@amd.com * Register the stats for this object. 1518180SBrad.Beckmann@amd.com */ 1526908SBrad.Beckmann@amd.com void regStats() override; 1536908SBrad.Beckmann@amd.com 1546908SBrad.Beckmann@amd.com /** 1556908SBrad.Beckmann@amd.com * Invalidate a cache block. 1566908SBrad.Beckmann@amd.com * @param blk The block to invalidate. 1577564SBrad.Beckmann@amd.com */ 1588180SBrad.Beckmann@amd.com void invalidate(CacheBlk *blk) override; 1596908SBrad.Beckmann@amd.com 1606908SBrad.Beckmann@amd.com /** 1619695Snilay@cs.wisc.edu * Access block and update replacement data. May not succeed, in which 1628436SBrad.Beckmann@amd.com * case nullptr pointer is returned. This has all the implications of a 1639841Snilay@cs.wisc.edu * cache access and should only be used as such. 1648436SBrad.Beckmann@amd.com * Returns the access latency and inCachesMask flags as a side effect. 16510917Sbrandon.potter@amd.com * @param addr The address to look for. 1669468Smalek.musleh@gmail.com * @param is_secure True if the target memory space is secure. 1676908SBrad.Beckmann@amd.com * @param lat The latency of the access. 1688257SBrad.Beckmann@amd.com * @param in_cache_mask Mask indicating the caches in which the blk fits. 16910311Snilay@cs.wisc.edu * @return Pointer to the cache block. 17011022Sjthestness@gmail.com */ 17111022Sjthestness@gmail.com CacheBlk* accessBlock(Addr addr, bool is_secure, Cycles &lat, 17211022Sjthestness@gmail.com CachesMask *in_cache_mask); 17311022Sjthestness@gmail.com 17411022Sjthestness@gmail.com /** 17511022Sjthestness@gmail.com * Just a wrapper of above function to conform with the base interface. 17610311Snilay@cs.wisc.edu */ 17711022Sjthestness@gmail.com CacheBlk* accessBlock(Addr addr, bool is_secure, Cycles &lat) override; 17811022Sjthestness@gmail.com 17911022Sjthestness@gmail.com /** 18011022Sjthestness@gmail.com * Find the block in the cache, do not update the replacement data. 18111022Sjthestness@gmail.com * @param addr The address to look for. 18211022Sjthestness@gmail.com * @param is_secure True if the target memory space is secure. 18311022Sjthestness@gmail.com * @param asid The address space ID. 18411022Sjthestness@gmail.com * @return Pointer to the cache block. 18510311Snilay@cs.wisc.edu */ 18610311Snilay@cs.wisc.edu CacheBlk* findBlock(Addr addr, bool is_secure) const override; 1879793Sakash.bagdia@arm.com 1889793Sakash.bagdia@arm.com /** 1899793Sakash.bagdia@arm.com * Find a block given set and way. 1909793Sakash.bagdia@arm.com * 1919793Sakash.bagdia@arm.com * @param set The set of the block. 1929793Sakash.bagdia@arm.com * @param way The way of the block. 1939793Sakash.bagdia@arm.com * @return The block. 19412598Snikos.nikoleris@arm.com */ 19512976Snikos.nikoleris@arm.com ReplaceableEntry* findBlockBySetAndWay(int set, int way) const override; 19612598Snikos.nikoleris@arm.com 19712598Snikos.nikoleris@arm.com /** 19812598Snikos.nikoleris@arm.com * Find replacement victim based on address. 19912065Snikos.nikoleris@arm.com * 20012065Snikos.nikoleris@arm.com * @param addr Address to find a victim for. 20110311Snilay@cs.wisc.edu * @return Cache block to be replaced. 20211022Sjthestness@gmail.com */ 20311022Sjthestness@gmail.com CacheBlk* findVictim(Addr addr) override; 20411022Sjthestness@gmail.com 20511022Sjthestness@gmail.com /** 20611022Sjthestness@gmail.com * Insert the new block into the cache and update replacement data. 20711022Sjthestness@gmail.com * 20811022Sjthestness@gmail.com * @param pkt Packet holding the address to update 20911022Sjthestness@gmail.com * @param blk The block to update. 21010311Snilay@cs.wisc.edu */ 21111022Sjthestness@gmail.com void insertBlock(PacketPtr pkt, CacheBlk *blk) override; 21211022Sjthestness@gmail.com 21311022Sjthestness@gmail.com /** 21411022Sjthestness@gmail.com * Generate the tag from the addres. For fully associative this is just the 21511022Sjthestness@gmail.com * block address. 21611022Sjthestness@gmail.com * @param addr The address to get the tag from. 21711022Sjthestness@gmail.com * @return The tag. 21811022Sjthestness@gmail.com */ 21911022Sjthestness@gmail.com Addr extractTag(Addr addr) const override 22010311Snilay@cs.wisc.edu { 22110311Snilay@cs.wisc.edu return blkAlign(addr); 2228929Snilay@cs.wisc.edu } 2236908SBrad.Beckmann@amd.com 2246908SBrad.Beckmann@amd.com /** 2256908SBrad.Beckmann@amd.com * Regenerate the block address from the tag. 2266908SBrad.Beckmann@amd.com * 22710519Snilay@cs.wisc.edu * @param block The block. 22810519Snilay@cs.wisc.edu * @return the block address. 22910917Sbrandon.potter@amd.com */ 2306908SBrad.Beckmann@amd.com Addr regenerateBlkAddr(const CacheBlk* blk) const override 2318477Snilay@cs.wisc.edu { 2329841Snilay@cs.wisc.edu return blk->tag; 2338477Snilay@cs.wisc.edu } 2346908SBrad.Beckmann@amd.com 2359468Smalek.musleh@gmail.com void forEachBlk(std::function<void(CacheBlk &)> visitor) override { 2366908SBrad.Beckmann@amd.com for (int i = 0; i < numBlocks; i++) { 2378257SBrad.Beckmann@amd.com visitor(blks[i]); 23810519Snilay@cs.wisc.edu } 23911022Sjthestness@gmail.com } 24011022Sjthestness@gmail.com 24111022Sjthestness@gmail.com bool anyBlk(std::function<bool(CacheBlk &)> visitor) override { 24211022Sjthestness@gmail.com for (int i = 0; i < numBlocks; i++) { 24311022Sjthestness@gmail.com if (visitor(blks[i])) { 24410519Snilay@cs.wisc.edu return true; 2456908SBrad.Beckmann@amd.com } 2466908SBrad.Beckmann@amd.com } 2476908SBrad.Beckmann@amd.com return false; 2486908SBrad.Beckmann@amd.com } 2496908SBrad.Beckmann@amd.com 25010519Snilay@cs.wisc.edu private: 25110519Snilay@cs.wisc.edu /** 25210519Snilay@cs.wisc.edu * Mechanism that allows us to simultaneously collect miss 25310519Snilay@cs.wisc.edu * statistics for multiple caches. Currently, we keep track of 25410519Snilay@cs.wisc.edu * caches from a set minimum size of interest up to the actual 25510519Snilay@cs.wisc.edu * cache size. 25610519Snilay@cs.wisc.edu */ 25710519Snilay@cs.wisc.edu class CacheTracking 25810519Snilay@cs.wisc.edu { 25910519Snilay@cs.wisc.edu public: 26011022Sjthestness@gmail.com CacheTracking(unsigned min_size, unsigned max_size, 26111022Sjthestness@gmail.com unsigned block_size) 26211022Sjthestness@gmail.com : blkSize(block_size), 26311022Sjthestness@gmail.com minTrackedSize(min_size), 26411022Sjthestness@gmail.com numTrackedCaches(max_size > min_size ? 26510519Snilay@cs.wisc.edu floorLog2(max_size) - floorLog2(min_size) : 0), 26610519Snilay@cs.wisc.edu inAllCachesMask(mask(numTrackedCaches)), 26710519Snilay@cs.wisc.edu boundaries(new FALRUBlk *[numTrackedCaches]) 26810519Snilay@cs.wisc.edu { 26911065Snilay@cs.wisc.edu fatal_if(numTrackedCaches > sizeof(CachesMask) * 8, 2709100SBrad.Beckmann@amd.com "Not enough bits (%s) in type CachesMask type to keep " 27112598Snikos.nikoleris@arm.com "track of %d caches\n", sizeof(CachesMask), 272 numTrackedCaches); 273 } 274 275 ~CacheTracking() 276 { 277 delete[] boundaries; 278 } 279 280 /** 281 * Initialiaze cache blocks and the tracking mechanism 282 * 283 * All blocks in the cache need to be initialized once. 284 * 285 * @param blk the MRU block 286 * @param blk the LRU block 287 */ 288 void init(FALRUBlk *head, FALRUBlk *tail); 289 290 /** 291 * Update boundaries as a block will be moved to the MRU. 292 * 293 * For all caches that didn't fit the block before moving it, 294 * we move their boundaries one block closer to the MRU. We 295 * also update InCacheMasks as neccessary. 296 * 297 * @param blk the block that will be moved to the head 298 */ 299 void moveBlockToHead(FALRUBlk *blk); 300 301 /** 302 * Update boundaries as a block will be moved to the LRU. 303 * 304 * For all caches that fitted the block before moving it, we 305 * move their boundaries one block closer to the LRU. We 306 * also update InCacheMasks as neccessary. 307 * 308 * @param blk the block that will be moved to the head 309 */ 310 void moveBlockToTail(FALRUBlk *blk); 311 312 /** 313 * Notify of a block access. 314 * 315 * This should be called every time a block is accessed and it 316 * updates statistics. If the input block is nullptr then we 317 * treat the access as a miss. The block's InCacheMask 318 * determines the caches in which the block fits. 319 * 320 * @param blk the block to record the access for 321 */ 322 void recordAccess(FALRUBlk *blk); 323 324 /** 325 * Check that the tracking mechanism is in consistent state. 326 * 327 * Iterate from the head (MRU) to the tail (LRU) of the list 328 * of blocks and assert the inCachesMask and the boundaries 329 * are in consistent state. 330 * 331 * @param head the MRU block of the actual cache 332 * @param head the LRU block of the actual cache 333 */ 334 void check(FALRUBlk *head, FALRUBlk *tail); 335 336 /** 337 * Register the stats for this object. 338 */ 339 void regStats(std::string name); 340 341 private: 342 /** The size of the cache block */ 343 const unsigned blkSize; 344 /** The smallest cache we are tracking */ 345 const unsigned minTrackedSize; 346 /** The number of different size caches being tracked. */ 347 const int numTrackedCaches; 348 /** A mask for all cache being tracked. */ 349 const CachesMask inAllCachesMask; 350 /** Array of pointers to blocks at the cache boundaries. */ 351 FALRUBlk** boundaries; 352 353 protected: 354 /** 355 * @defgroup FALRUStats Fully Associative LRU specific statistics 356 * The FA lru stack lets us track multiple cache sizes at once. These 357 * statistics track the hits and misses for different cache sizes. 358 * @{ 359 */ 360 361 /** Hits in each cache */ 362 Stats::Vector hits; 363 /** Misses in each cache */ 364 Stats::Vector misses; 365 /** Total number of accesses */ 366 Stats::Scalar accesses; 367 368 /** 369 * @} 370 */ 371 }; 372 CacheTracking cacheTracking; 373}; 374 375#endif // __MEM_CACHE_TAGS_FA_LRU_HH__ 376