base_set_assoc.hh revision 11169
12SN/A/* 21762SN/A * Copyright (c) 2012-2014 ARM Limited 32SN/A * All rights reserved. 42SN/A * 52SN/A * The license below extends only to copyright in the software and shall 62SN/A * not be construed as granting a license to any other intellectual 72SN/A * property including but not limited to intellectual property relating 82SN/A * to a hardware implementation of the functionality of the software 92SN/A * licensed hereunder. You may use the software subject to the license 102SN/A * terms below provided that you ensure that this notice is replicated 112SN/A * unmodified and in its entirety in all distributions of the software, 122SN/A * modified or unmodified, in source code or in binary form. 132SN/A * 142SN/A * Copyright (c) 2003-2005,2014 The Regents of The University of Michigan 152SN/A * All rights reserved. 162SN/A * 172SN/A * Redistribution and use in source and binary forms, with or without 182SN/A * modification, are permitted provided that the following conditions are 192SN/A * met: redistributions of source code must retain the above copyright 202SN/A * notice, this list of conditions and the following disclaimer; 212SN/A * redistributions in binary form must reproduce the above copyright 222SN/A * notice, this list of conditions and the following disclaimer in the 232SN/A * documentation and/or other materials provided with the distribution; 242SN/A * neither the name of the copyright holders nor the names of its 252SN/A * contributors may be used to endorse or promote products derived from 262SN/A * this software without specific prior written permission. 272665Ssaidi@eecs.umich.edu * 282665Ssaidi@eecs.umich.edu * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 292665Ssaidi@eecs.umich.edu * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 302SN/A * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 312SN/A * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 32360SN/A * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 33360SN/A * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 342SN/A * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 352SN/A * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 362SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 372SN/A * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 382SN/A * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 392SN/A * 401858SN/A * Authors: Erik Hallnor 411858SN/A */ 421858SN/A 432SN/A/** 444117Sgblack@eecs.umich.edu * @file 45180SN/A * Declaration of a base set associative tag store. 462SN/A */ 476329Sgblack@eecs.umich.edu 482378SN/A#ifndef __MEM_CACHE_TAGS_BASESETASSOC_HH__ 496214Snate@binkert.org#define __MEM_CACHE_TAGS_BASESETASSOC_HH__ 506658Snate@binkert.org 5156SN/A#include <cassert> 525958Sgblack@eecs.umich.edu#include <cstring> 532SN/A#include <list> 546658Snate@binkert.org 555154Sgblack@eecs.umich.edu#include "mem/cache/tags/base.hh" 565154Sgblack@eecs.umich.edu#include "mem/cache/tags/cacheset.hh" 575154Sgblack@eecs.umich.edu#include "mem/cache/base.hh" 585154Sgblack@eecs.umich.edu#include "mem/cache/blk.hh" 595154Sgblack@eecs.umich.edu#include "mem/packet.hh" 605154Sgblack@eecs.umich.edu#include "params/BaseSetAssoc.hh" 612680Sktlim@umich.edu 622401SN/A/** 632378SN/A * A BaseSetAssoc cache tag store. 645758Shsul@eecs.umich.edu * @sa \ref gem5MemorySystem "gem5 Memory System" 655771Shsul@eecs.umich.edu * 665758Shsul@eecs.umich.edu * The BaseSetAssoc tags provide a base, as well as the functionality 675758Shsul@eecs.umich.edu * common to any set associative tags. Any derived class must implement 685771Shsul@eecs.umich.edu * the methods related to the specifics of the actual replacment policy. 695758Shsul@eecs.umich.edu * These are: 705771Shsul@eecs.umich.edu * 715758Shsul@eecs.umich.edu * BlkType* accessBlock(); 725758Shsul@eecs.umich.edu * BlkType* findVictim(); 735771Shsul@eecs.umich.edu * void insertBlock(); 745758Shsul@eecs.umich.edu * void invalidate(); 755758Shsul@eecs.umich.edu */ 762SN/Aclass BaseSetAssoc : public BaseTags 772SN/A{ 782SN/A public: 792SN/A /** Typedef the block type used in this tag store. */ 802378SN/A typedef CacheBlk BlkType; 812378SN/A /** Typedef for a list of pointers to the local block class. */ 822378SN/A typedef std::list<BlkType*> BlkList; 832378SN/A /** Typedef the set type used in this tag store. */ 842680Sktlim@umich.edu typedef CacheSet<CacheBlk> SetType; 852SN/A 862SN/A 872SN/A protected: 882SN/A /** The associativity of the cache. */ 895183Ssaidi@eecs.umich.edu const unsigned assoc; 905183Ssaidi@eecs.umich.edu /** The allocatable associativity of the cache (alloc mask). */ 912680Sktlim@umich.edu unsigned allocAssoc; 925713Shsul@eecs.umich.edu /** The number of sets in the cache. */ 93180SN/A const unsigned numSets; 943971Sgblack@eecs.umich.edu /** Whether tags and data are accessed sequentially. */ 956658Snate@binkert.org const bool sequentialAccess; 963971Sgblack@eecs.umich.edu 973971Sgblack@eecs.umich.edu /** The cache sets. */ 983971Sgblack@eecs.umich.edu SetType *sets; 99180SN/A 1005713Shsul@eecs.umich.edu /** The cache blocks. */ 1012SN/A BlkType *blks; 1022SN/A /** The data blocks, 1 per cache block. */ 1032SN/A uint8_t *dataBlks; 1042SN/A 1052SN/A /** The amount to shift the address to get the set. */ 1062680Sktlim@umich.edu int setShift; 1072SN/A /** The amount to shift the address to get the tag. */ 1082680Sktlim@umich.edu int tagShift; 1092SN/A /** Mask out all bits that aren't part of the set index. */ 1105543Ssaidi@eecs.umich.edu unsigned setMask; 1112SN/A /** Mask out all bits that aren't part of the block offset. */ 1122SN/A unsigned blkMask; 1132SN/A 1142SN/Apublic: 1152SN/A 1165543Ssaidi@eecs.umich.edu /** Convenience typedef. */ 1172SN/A typedef BaseSetAssocParams Params; 1185543Ssaidi@eecs.umich.edu 1195543Ssaidi@eecs.umich.edu /** 1205543Ssaidi@eecs.umich.edu * Construct and initialize this tag store. 1212SN/A */ 1225154Sgblack@eecs.umich.edu BaseSetAssoc(const Params *p); 1235154Sgblack@eecs.umich.edu 1245154Sgblack@eecs.umich.edu /** 1252SN/A * Destructor 1262SN/A */ 1272SN/A virtual ~BaseSetAssoc(); 128360SN/A 1291408SN/A /** 1301408SN/A * Return the block size. 131360SN/A * @return the block size. 1321514SN/A */ 1331514SN/A unsigned 1341514SN/A getBlockSize() const 1351514SN/A { 1365543Ssaidi@eecs.umich.edu return blkSize; 1372SN/A } 1385999Snate@binkert.org 1392SN/A /** 1402SN/A * Return the subblock size. In the case of BaseSetAssoc it is always 1412SN/A * the block size. 1422SN/A * @return The block size. 1435154Sgblack@eecs.umich.edu */ 1442SN/A unsigned 1451395SN/A getSubBlockSize() const 1461395SN/A { 1472SN/A return blkSize; 1482SN/A } 1492378SN/A 1502401SN/A /** 1512378SN/A * Return the number of sets this cache has 1522378SN/A * @return The number of sets. 1532378SN/A */ 1542SN/A unsigned 1554997Sgblack@eecs.umich.edu getNumSets() const override 1564997Sgblack@eecs.umich.edu { 1574997Sgblack@eecs.umich.edu return numSets; 1584997Sgblack@eecs.umich.edu } 1595282Srstrong@cs.ucsd.edu 1605282Srstrong@cs.ucsd.edu /** 1615282Srstrong@cs.ucsd.edu * Return the number of ways this cache has 1625282Srstrong@cs.ucsd.edu * @return The number of ways. 1635282Srstrong@cs.ucsd.edu */ 1645282Srstrong@cs.ucsd.edu unsigned 1655282Srstrong@cs.ucsd.edu getNumWays() const override 1665282Srstrong@cs.ucsd.edu { 1675282Srstrong@cs.ucsd.edu return assoc; 1685282Srstrong@cs.ucsd.edu } 1695282Srstrong@cs.ucsd.edu 1705282Srstrong@cs.ucsd.edu /** 1715282Srstrong@cs.ucsd.edu * Find the cache block given set and way 1725282Srstrong@cs.ucsd.edu * @param set The set of the block. 1735282Srstrong@cs.ucsd.edu * @param way The way of the block. 1745282Srstrong@cs.ucsd.edu * @return The cache block. 1755282Srstrong@cs.ucsd.edu */ 1765282Srstrong@cs.ucsd.edu CacheBlk *findBlockBySetAndWay(int set, int way) const override; 1775282Srstrong@cs.ucsd.edu 1785282Srstrong@cs.ucsd.edu /** 1795282Srstrong@cs.ucsd.edu * Invalidate the given block. 1805282Srstrong@cs.ucsd.edu * @param blk The block to invalidate. 1815282Srstrong@cs.ucsd.edu */ 1825282Srstrong@cs.ucsd.edu void invalidate(CacheBlk *blk) override 1835282Srstrong@cs.ucsd.edu { 1845282Srstrong@cs.ucsd.edu assert(blk); 1855282Srstrong@cs.ucsd.edu assert(blk->isValid()); 1865282Srstrong@cs.ucsd.edu tagsInUse--; 1875282Srstrong@cs.ucsd.edu assert(blk->srcMasterId < cache->system->maxMasters()); 1882SN/A occupancies[blk->srcMasterId]--; 1892SN/A blk->srcMasterId = Request::invldMasterId; 1905282Srstrong@cs.ucsd.edu blk->task_id = ContextSwitchTaskId::Unknown; 1915282Srstrong@cs.ucsd.edu blk->tickInserted = curTick(); 1925282Srstrong@cs.ucsd.edu } 1932SN/A 1942SN/A /** 1952SN/A * Access block and update replacement data. May not succeed, in which case 1962SN/A * NULL pointer is returned. This has all the implications of a cache 1972SN/A * access and should only be used as such. Returns the access latency as a 1982SN/A * side effect. 1992SN/A * @param addr The address to find. 2002SN/A * @param is_secure True if the target memory space is secure. 2012SN/A * @param asid The address space ID. 2025713Shsul@eecs.umich.edu * @param lat The access latency. 2035713Shsul@eecs.umich.edu * @return Pointer to the cache block if found. 2045713Shsul@eecs.umich.edu */ 2055713Shsul@eecs.umich.edu CacheBlk* accessBlock(Addr addr, bool is_secure, Cycles &lat, 2065713Shsul@eecs.umich.edu int context_src) override 2075713Shsul@eecs.umich.edu { 208180SN/A Addr tag = extractTag(addr); 2095713Shsul@eecs.umich.edu int set = extractSet(addr); 2105713Shsul@eecs.umich.edu BlkType *blk = sets[set].findBlk(tag, is_secure); 2112SN/A lat = accessLatency;; 2122SN/A 2132SN/A // Access all tags in parallel, hence one in each way. The data side 2142SN/A // either accesses all blocks in parallel, or one block sequentially on 2152SN/A // a hit. Sequential access with a miss doesn't access data. 2165282Srstrong@cs.ucsd.edu tagAccesses += allocAssoc; 2171970SN/A if (sequentialAccess) { 2181970SN/A if (blk != NULL) { 2191970SN/A dataAccesses += 1; 2202SN/A } 2212SN/A } else { 2222SN/A dataAccesses += allocAssoc; 2232SN/A } 2245282Srstrong@cs.ucsd.edu 2255282Srstrong@cs.ucsd.edu if (blk != NULL) { 2265282Srstrong@cs.ucsd.edu if (blk->whenReady > curTick() 2275282Srstrong@cs.ucsd.edu && cache->ticksToCycles(blk->whenReady - curTick()) 2285282Srstrong@cs.ucsd.edu > accessLatency) { 2295282Srstrong@cs.ucsd.edu lat = cache->ticksToCycles(blk->whenReady - curTick()); 2305282Srstrong@cs.ucsd.edu } 2315282Srstrong@cs.ucsd.edu blk->refCount += 1; 2325282Srstrong@cs.ucsd.edu } 2335282Srstrong@cs.ucsd.edu 2345282Srstrong@cs.ucsd.edu return blk; 2355282Srstrong@cs.ucsd.edu } 2362680Sktlim@umich.edu 2373311Ssaidi@eecs.umich.edu /** 2384434Ssaidi@eecs.umich.edu * Finds the given address in the cache, do not update replacement data. 2394434Ssaidi@eecs.umich.edu * i.e. This is a no-side-effect find of a block. 2404434Ssaidi@eecs.umich.edu * @param addr The address to find. 2414434Ssaidi@eecs.umich.edu * @param is_secure True if the target memory space is secure. 2423311Ssaidi@eecs.umich.edu * @param asid The address space ID. 2433311Ssaidi@eecs.umich.edu * @return Pointer to the cache block if found. 2442SN/A */ 2452SN/A CacheBlk* findBlock(Addr addr, bool is_secure) const override; 2462SN/A 2472SN/A /** 2482SN/A * Find an invalid block to evict for the address provided. 249360SN/A * If there are no invalid blocks, this will return the block 2502SN/A * in the least-recently-used position. 2512SN/A * @param addr The addr to a find a replacement candidate for. 252360SN/A * @return The candidate block. 2532378SN/A */ 2542378SN/A CacheBlk* findVictim(Addr addr) override 2552378SN/A { 2563669Sbinkertn@umich.edu BlkType *blk = NULL; 2572378SN/A int set = extractSet(addr); 2585154Sgblack@eecs.umich.edu 2592SN/A // prefer to evict an invalid block 2602561SN/A for (int i = 0; i < allocAssoc; ++i) { 2612378SN/A blk = sets[set].blks[i]; 2623114Sgblack@eecs.umich.edu if (!blk->isValid()) 2633114Sgblack@eecs.umich.edu break; 2643114Sgblack@eecs.umich.edu } 2653114Sgblack@eecs.umich.edu 2663114Sgblack@eecs.umich.edu return blk; 2673114Sgblack@eecs.umich.edu } 2683114Sgblack@eecs.umich.edu 2693114Sgblack@eecs.umich.edu /** 2703114Sgblack@eecs.umich.edu * Insert the new block into the cache. 2713114Sgblack@eecs.umich.edu * @param pkt Packet holding the address to update 272360SN/A * @param blk The block to update. 2733114Sgblack@eecs.umich.edu */ 2744793Sgblack@eecs.umich.edu void insertBlock(PacketPtr pkt, CacheBlk *blk) override 2754793Sgblack@eecs.umich.edu { 2764793Sgblack@eecs.umich.edu Addr addr = pkt->getAddr(); 2774793Sgblack@eecs.umich.edu MasterID master_id = pkt->req->masterId(); 2784793Sgblack@eecs.umich.edu uint32_t task_id = pkt->req->taskId(); 2794793Sgblack@eecs.umich.edu 2804793Sgblack@eecs.umich.edu if (!blk->isTouched) { 2814793Sgblack@eecs.umich.edu tagsInUse++; 2824793Sgblack@eecs.umich.edu blk->isTouched = true; 2834793Sgblack@eecs.umich.edu if (!warmedUp && tagsInUse.value() >= warmupBound) { 2844793Sgblack@eecs.umich.edu warmedUp = true; 2854793Sgblack@eecs.umich.edu warmupCycle = curTick(); 2864793Sgblack@eecs.umich.edu } 2874793Sgblack@eecs.umich.edu } 2884793Sgblack@eecs.umich.edu 2894793Sgblack@eecs.umich.edu // If we're replacing a block that was previously valid update 2904793Sgblack@eecs.umich.edu // stats for it. This can't be done in findBlock() because a 2914793Sgblack@eecs.umich.edu // found block might not actually be replaced there if the 2924793Sgblack@eecs.umich.edu // coherence protocol says it can't be. 2934793Sgblack@eecs.umich.edu if (blk->isValid()) { 2944793Sgblack@eecs.umich.edu replacements[0]++; 2954793Sgblack@eecs.umich.edu totalRefs += blk->refCount; 2966399Sgblack@eecs.umich.edu ++sampledRefs; 2976399Sgblack@eecs.umich.edu blk->refCount = 0; 2986399Sgblack@eecs.umich.edu 2996399Sgblack@eecs.umich.edu // deal with evicted block 3004793Sgblack@eecs.umich.edu assert(blk->srcMasterId < cache->system->maxMasters()); 3014793Sgblack@eecs.umich.edu occupancies[blk->srcMasterId]--; 3024793Sgblack@eecs.umich.edu 3034793Sgblack@eecs.umich.edu blk->invalidate(); 3043114Sgblack@eecs.umich.edu } 3053114Sgblack@eecs.umich.edu 3063114Sgblack@eecs.umich.edu blk->isTouched = true; 3073114Sgblack@eecs.umich.edu 3083114Sgblack@eecs.umich.edu // Set tag for new block. Caller is responsible for setting status. 3093114Sgblack@eecs.umich.edu blk->tag = extractTag(addr); 3103114Sgblack@eecs.umich.edu 3113669Sbinkertn@umich.edu // deal with what we are bringing in 3123669Sbinkertn@umich.edu assert(master_id < cache->system->maxMasters()); 3133669Sbinkertn@umich.edu occupancies[master_id]++; 3143669Sbinkertn@umich.edu blk->srcMasterId = master_id; 3153669Sbinkertn@umich.edu blk->task_id = task_id; 3163669Sbinkertn@umich.edu blk->tickInserted = curTick(); 3173669Sbinkertn@umich.edu 3183669Sbinkertn@umich.edu // We only need to write into one tag and one data block. 3193669Sbinkertn@umich.edu tagAccesses += 1; 3203669Sbinkertn@umich.edu dataAccesses += 1; 3213669Sbinkertn@umich.edu } 3223669Sbinkertn@umich.edu 3233669Sbinkertn@umich.edu /** 3243669Sbinkertn@umich.edu * Limit the allocation for the cache ways. 3255513SMichael.Adler@intel.com * @param ways The maximum number of ways available for replacement. 3265513SMichael.Adler@intel.com */ 3272680Sktlim@umich.edu virtual void setWayAllocationMax(int ways) override 3286701Sgblack@eecs.umich.edu { 3296701Sgblack@eecs.umich.edu fatal_if(ways < 1, "Allocation limit must be greater than zero"); 3306701Sgblack@eecs.umich.edu allocAssoc = ways; 3315958Sgblack@eecs.umich.edu } 3325958Sgblack@eecs.umich.edu 3335958Sgblack@eecs.umich.edu /** 3345958Sgblack@eecs.umich.edu * Get the way allocation mask limit. 3352093SN/A * @return The maximum number of ways available for replacement. 3362462SN/A */ 3372715Sstever@eecs.umich.edu virtual int getWayAllocationMax() const override 3382715Sstever@eecs.umich.edu { 3392715Sstever@eecs.umich.edu return allocAssoc; 3402715Sstever@eecs.umich.edu } 3415154Sgblack@eecs.umich.edu 3422SN/A /** 3432SN/A * Generate the tag from the given address. 344360SN/A * @param addr The address to get the tag from. 3452SN/A * @return The tag of the address. 3462SN/A */ 347360SN/A Addr extractTag(Addr addr) const override 348 { 349 return (addr >> tagShift); 350 } 351 352 /** 353 * Calculate the set index from the address. 354 * @param addr The address to get the set from. 355 * @return The set index of the address. 356 */ 357 int extractSet(Addr addr) const override 358 { 359 return ((addr >> setShift) & setMask); 360 } 361 362 /** 363 * Align an address to the block size. 364 * @param addr the address to align. 365 * @return The block address. 366 */ 367 Addr blkAlign(Addr addr) const 368 { 369 return (addr & ~(Addr)blkMask); 370 } 371 372 /** 373 * Regenerate the block address from the tag. 374 * @param tag The tag of the block. 375 * @param set The set of the block. 376 * @return The block address. 377 */ 378 Addr regenerateBlkAddr(Addr tag, unsigned set) const override 379 { 380 return ((tag << tagShift) | ((Addr)set << setShift)); 381 } 382 383 /** 384 * Called at end of simulation to complete average block reference stats. 385 */ 386 void cleanupRefs() override; 387 388 /** 389 * Print all tags used 390 */ 391 std::string print() const override; 392 393 /** 394 * Called prior to dumping stats to compute task occupancy 395 */ 396 void computeStats() override; 397 398 /** 399 * Visit each block in the tag store and apply a visitor to the 400 * block. 401 * 402 * The visitor should be a function (or object that behaves like a 403 * function) that takes a cache block reference as its parameter 404 * and returns a bool. A visitor can request the traversal to be 405 * stopped by returning false, returning true causes it to be 406 * called for the next block in the tag store. 407 * 408 * \param visitor Visitor to call on each block. 409 */ 410 void forEachBlk(CacheBlkVisitor &visitor) override { 411 for (unsigned i = 0; i < numSets * assoc; ++i) { 412 if (!visitor(blks[i])) 413 return; 414 } 415 } 416}; 417 418#endif // __MEM_CACHE_TAGS_BASESETASSOC_HH__ 419