base_set_assoc.hh revision 12746:0d0c266663d4
11689SN/A/* 28707Sandreas.hansson@arm.com * Copyright (c) 2012-2014,2017 ARM Limited 38707Sandreas.hansson@arm.com * All rights reserved. 48707Sandreas.hansson@arm.com * 58707Sandreas.hansson@arm.com * The license below extends only to copyright in the software and shall 68707Sandreas.hansson@arm.com * not be construed as granting a license to any other intellectual 78707Sandreas.hansson@arm.com * property including but not limited to intellectual property relating 88707Sandreas.hansson@arm.com * to a hardware implementation of the functionality of the software 98707Sandreas.hansson@arm.com * licensed hereunder. You may use the software subject to the license 108707Sandreas.hansson@arm.com * terms below provided that you ensure that this notice is replicated 118707Sandreas.hansson@arm.com * unmodified and in its entirety in all distributions of the software, 128707Sandreas.hansson@arm.com * modified or unmodified, in source code or in binary form. 138707Sandreas.hansson@arm.com * 142325SN/A * Copyright (c) 2003-2005,2014 The Regents of The University of Michigan 157897Shestness@cs.utexas.edu * All rights reserved. 161689SN/A * 171689SN/A * Redistribution and use in source and binary forms, with or without 181689SN/A * modification, are permitted provided that the following conditions are 191689SN/A * met: redistributions of source code must retain the above copyright 201689SN/A * notice, this list of conditions and the following disclaimer; 211689SN/A * redistributions in binary form must reproduce the above copyright 221689SN/A * notice, this list of conditions and the following disclaimer in the 231689SN/A * documentation and/or other materials provided with the distribution; 241689SN/A * neither the name of the copyright holders nor the names of its 251689SN/A * contributors may be used to endorse or promote products derived from 261689SN/A * this software without specific prior written permission. 271689SN/A * 281689SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 291689SN/A * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 301689SN/A * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 311689SN/A * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 321689SN/A * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 331689SN/A * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 341689SN/A * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 351689SN/A * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 361689SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 371689SN/A * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 381689SN/A * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 391689SN/A * 402665Ssaidi@eecs.umich.edu * Authors: Erik Hallnor 412665Ssaidi@eecs.umich.edu */ 422756Sksewell@umich.edu 437897Shestness@cs.utexas.edu/** 441689SN/A * @file 451689SN/A * Declaration of a base set associative tag store. 468779Sgblack@eecs.umich.edu */ 476658Snate@binkert.org 482733Sktlim@umich.edu#ifndef __MEM_CACHE_TAGS_BASE_SET_ASSOC_HH__ 498229Snate@binkert.org#define __MEM_CACHE_TAGS_BASE_SET_ASSOC_HH__ 508229Snate@binkert.org 518229Snate@binkert.org#include <functional> 524762Snate@binkert.org#include <string> 538779Sgblack@eecs.umich.edu#include <vector> 544762Snate@binkert.org 554762Snate@binkert.org#include "base/logging.hh" 568232Snate@binkert.org#include "base/types.hh" 578232Snate@binkert.org#include "debug/CacheRepl.hh" 588232Snate@binkert.org#include "mem/cache/base.hh" 594762Snate@binkert.org#include "mem/cache/blk.hh" 604762Snate@binkert.org#include "mem/cache/replacement_policies/base.hh" 618793Sgblack@eecs.umich.edu#include "mem/cache/tags/base.hh" 628779Sgblack@eecs.umich.edu#include "mem/cache/tags/cacheset.hh" 634762Snate@binkert.org#include "mem/packet.hh" 648460SAli.Saidi@ARM.com#include "params/BaseSetAssoc.hh" 654762Snate@binkert.org 662794Sktlim@umich.edu/** 672794Sktlim@umich.edu * A BaseSetAssoc cache tag store. 688733Sgeoffrey.blake@arm.com * @sa \ref gem5MemorySystem "gem5 Memory System" 692794Sktlim@umich.edu * 702794Sktlim@umich.edu * The BaseSetAssoc placement policy divides the cache into s sets of w 715702Ssaidi@eecs.umich.edu * cache lines (ways). A cache line is mapped onto a set, and can be placed 725702Ssaidi@eecs.umich.edu * into any of the ways of this set. 738232Snate@binkert.org */ 745702Ssaidi@eecs.umich.educlass BaseSetAssoc : public BaseTags 755702Ssaidi@eecs.umich.edu{ 768737Skoansin.tan@gmail.com public: 775529Snate@binkert.org /** Typedef the block type used in this tag store. */ 782669Sktlim@umich.edu typedef CacheBlk BlkType; 796221Snate@binkert.org /** Typedef the set type used in this tag store. */ 801060SN/A typedef CacheSet<CacheBlk> SetType; 815529Snate@binkert.org 825712Shsul@eecs.umich.edu protected: 831060SN/A /** The associativity of the cache. */ 841060SN/A const unsigned assoc; 851060SN/A /** The allocatable associativity of the cache (alloc mask). */ 862292SN/A unsigned allocAssoc; 872733Sktlim@umich.edu 882292SN/A /** The cache blocks. */ 892292SN/A std::vector<BlkType> blks; 902292SN/A 912292SN/A /** The number of sets in the cache. */ 928707Sandreas.hansson@arm.com const unsigned numSets; 938707Sandreas.hansson@arm.com 948707Sandreas.hansson@arm.com /** Whether tags and data are accessed sequentially. */ 958707Sandreas.hansson@arm.com const bool sequentialAccess; 968707Sandreas.hansson@arm.com 978707Sandreas.hansson@arm.com /** The cache sets. */ 988707Sandreas.hansson@arm.com std::vector<SetType> sets; 998707Sandreas.hansson@arm.com 1008707Sandreas.hansson@arm.com /** The amount to shift the address to get the set. */ 1018707Sandreas.hansson@arm.com int setShift; 1028707Sandreas.hansson@arm.com /** The amount to shift the address to get the tag. */ 1038707Sandreas.hansson@arm.com int tagShift; 1048707Sandreas.hansson@arm.com /** Mask out all bits that aren't part of the set index. */ 1058707Sandreas.hansson@arm.com unsigned setMask; 1068707Sandreas.hansson@arm.com 1078707Sandreas.hansson@arm.com /** Replacement policy */ 1088707Sandreas.hansson@arm.com BaseReplacementPolicy *replacementPolicy; 1098707Sandreas.hansson@arm.com 1108707Sandreas.hansson@arm.com public: 1118707Sandreas.hansson@arm.com /** Convenience typedef. */ 1128707Sandreas.hansson@arm.com typedef BaseSetAssocParams Params; 1138707Sandreas.hansson@arm.com 1148707Sandreas.hansson@arm.com /** 1158707Sandreas.hansson@arm.com * Construct and initialize this tag store. 1168707Sandreas.hansson@arm.com */ 1178707Sandreas.hansson@arm.com BaseSetAssoc(const Params *p); 1188707Sandreas.hansson@arm.com 1198707Sandreas.hansson@arm.com /** 1208707Sandreas.hansson@arm.com * Destructor 1218707Sandreas.hansson@arm.com */ 1228707Sandreas.hansson@arm.com virtual ~BaseSetAssoc() {}; 1238707Sandreas.hansson@arm.com 1248707Sandreas.hansson@arm.com /** 1258707Sandreas.hansson@arm.com * This function updates the tags when a block is invalidated. It also 1268707Sandreas.hansson@arm.com * updates the replacement data. 1278707Sandreas.hansson@arm.com * 1281060SN/A * @param blk The block to invalidate. 1291755SN/A */ 1305606Snate@binkert.org void invalidate(CacheBlk *blk) override; 1311060SN/A 1321060SN/A /** 1331060SN/A * Access block and update replacement data. May not succeed, in which case 1341060SN/A * nullptr is returned. This has all the implications of a cache 1351060SN/A * access and should only be used as such. Returns the access latency as a 1361755SN/A * side effect. 1371060SN/A * @param addr The address to find. 1381060SN/A * @param is_secure True if the target memory space is secure. 1391060SN/A * @param lat The access latency. 1401060SN/A * @return Pointer to the cache block if found. 1411060SN/A */ 1421060SN/A CacheBlk* accessBlock(Addr addr, bool is_secure, Cycles &lat) override 1435336Shines@cs.fsu.edu { 1441060SN/A BlkType *blk = findBlock(addr, is_secure); 1454873Sstever@eecs.umich.edu 1461060SN/A // Access all tags in parallel, hence one in each way. The data side 1471060SN/A // either accesses all blocks in parallel, or one block sequentially on 1481060SN/A // a hit. Sequential access with a miss doesn't access data. 1492829Sksewell@umich.edu tagAccesses += allocAssoc; 1505606Snate@binkert.org if (sequentialAccess) { 1512829Sksewell@umich.edu if (blk != nullptr) { 1522829Sksewell@umich.edu dataAccesses += 1; 1532829Sksewell@umich.edu } 1542829Sksewell@umich.edu } else { 1552829Sksewell@umich.edu dataAccesses += allocAssoc; 1562829Sksewell@umich.edu } 1572829Sksewell@umich.edu 1582829Sksewell@umich.edu if (blk != nullptr) { 1592829Sksewell@umich.edu // If a cache hit 1602829Sksewell@umich.edu lat = accessLatency; 1612829Sksewell@umich.edu // Check if the block to be accessed is available. If not, 1622829Sksewell@umich.edu // apply the accessLatency on top of block->whenReady. 1632829Sksewell@umich.edu if (blk->whenReady > curTick() && 1642829Sksewell@umich.edu cache->ticksToCycles(blk->whenReady - curTick()) > 1652829Sksewell@umich.edu accessLatency) { 1662829Sksewell@umich.edu lat = cache->ticksToCycles(blk->whenReady - curTick()) + 1672829Sksewell@umich.edu accessLatency; 1682829Sksewell@umich.edu } 1692829Sksewell@umich.edu 1702829Sksewell@umich.edu // Update number of references to accessed block 1712829Sksewell@umich.edu blk->refCount++; 1725336Shines@cs.fsu.edu 1732829Sksewell@umich.edu // Update replacement data of accessed block 1744873Sstever@eecs.umich.edu replacementPolicy->touch(blk->replacementData); 1752829Sksewell@umich.edu } else { 1762829Sksewell@umich.edu // If a cache miss 1772829Sksewell@umich.edu lat = lookupLatency; 1782875Sksewell@umich.edu } 1795606Snate@binkert.org 1802875Sksewell@umich.edu return blk; 1812875Sksewell@umich.edu } 1822875Sksewell@umich.edu 1832875Sksewell@umich.edu /** 1842875Sksewell@umich.edu * Finds the given address in the cache, do not update replacement data. 1852875Sksewell@umich.edu * i.e. This is a no-side-effect find of a block. 1863859Sbinkertn@umich.edu * @param addr The address to find. 1872875Sksewell@umich.edu * @param is_secure True if the target memory space is secure. 1882875Sksewell@umich.edu * @param asid The address space ID. 1892875Sksewell@umich.edu * @return Pointer to the cache block if found. 1903859Sbinkertn@umich.edu */ 1912875Sksewell@umich.edu CacheBlk* findBlock(Addr addr, bool is_secure) const override; 1922875Sksewell@umich.edu 1932875Sksewell@umich.edu /** 1942875Sksewell@umich.edu * Find a block given set and way. 1952875Sksewell@umich.edu * 1962875Sksewell@umich.edu * @param set The set of the block. 1972875Sksewell@umich.edu * @param way The way of the block. 1983221Sktlim@umich.edu * @return The block. 1993221Sktlim@umich.edu */ 2002875Sksewell@umich.edu ReplaceableEntry* findBlockBySetAndWay(int set, int way) const override; 2012875Sksewell@umich.edu 2022875Sksewell@umich.edu /** 2032875Sksewell@umich.edu * Find replacement victim based on address. The list of evicted blocks 2045336Shines@cs.fsu.edu * only contains the victim. 2052875Sksewell@umich.edu * 2064873Sstever@eecs.umich.edu * @param addr Address to find a victim for. 2072875Sksewell@umich.edu * @param is_secure True if the target memory space is secure. 2082875Sksewell@umich.edu * @param evict_blks Cache blocks to be evicted. 2092875Sksewell@umich.edu * @return Cache block to be replaced. 2105595Sgblack@eecs.umich.edu */ 2112733Sktlim@umich.edu CacheBlk* findVictim(Addr addr, const bool is_secure, 2123781Sgblack@eecs.umich.edu std::vector<CacheBlk*>& evict_blks) const override 2133781Sgblack@eecs.umich.edu { 2141060SN/A // Get possible locations for the victim block 2155737Scws3k@cs.virginia.edu std::vector<CacheBlk*> locations = getPossibleLocations(addr); 2165737Scws3k@cs.virginia.edu 2175737Scws3k@cs.virginia.edu // Choose replacement victim from replacement candidates 2182292SN/A CacheBlk* victim = static_cast<CacheBlk*>(replacementPolicy->getVictim( 2195595Sgblack@eecs.umich.edu std::vector<ReplaceableEntry*>( 2205595Sgblack@eecs.umich.edu locations.begin(), locations.end()))); 2215595Sgblack@eecs.umich.edu 2225595Sgblack@eecs.umich.edu // There is only one eviction for this replacement 2235595Sgblack@eecs.umich.edu evict_blks.push_back(victim); 2241060SN/A 2255595Sgblack@eecs.umich.edu DPRINTF(CacheRepl, "set %x, way %x: selecting blk for replacement\n", 2264329Sktlim@umich.edu victim->set, victim->way); 2271060SN/A 2285529Snate@binkert.org return victim; 2292292SN/A } 2302292SN/A 2311060SN/A /** 2325595Sgblack@eecs.umich.edu * Find all possible block locations for insertion and replacement of 2334329Sktlim@umich.edu * an address. Should be called immediately before ReplacementPolicy's 2342292SN/A * findVictim() not to break cache resizing. 2355529Snate@binkert.org * Returns blocks in all ways belonging to the set of the address. 2361060SN/A * 2375529Snate@binkert.org * @param addr The addr to a find possible locations for. 2382292SN/A * @return The possible locations. 2392292SN/A */ 2406221Snate@binkert.org const std::vector<CacheBlk*> getPossibleLocations(Addr addr) const 2412292SN/A { 2421060SN/A return sets[extractSet(addr)].blks; 2438707Sandreas.hansson@arm.com } 2448707Sandreas.hansson@arm.com 2458707Sandreas.hansson@arm.com /** 2462873Sktlim@umich.edu * Insert the new block into the cache and update replacement data. 2472873Sktlim@umich.edu * 2482873Sktlim@umich.edu * @param pkt Packet holding the address to update 2492873Sktlim@umich.edu * @param blk The block to update. 2502873Sktlim@umich.edu */ 2515804Snate@binkert.org void insertBlock(PacketPtr pkt, CacheBlk *blk) override 2522873Sktlim@umich.edu { 2532873Sktlim@umich.edu // Insert block 2541060SN/A BaseTags::insertBlock(pkt, blk); 2551060SN/A 2562292SN/A // Increment tag counter 2572843Sktlim@umich.edu tagsInUse++; 2586221Snate@binkert.org 2591060SN/A // Update replacement policy 2603221Sktlim@umich.edu replacementPolicy->reset(blk->replacementData); 2613221Sktlim@umich.edu } 2623221Sktlim@umich.edu 2633221Sktlim@umich.edu /** 2643221Sktlim@umich.edu * Limit the allocation for the cache ways. 2651681SN/A * @param ways The maximum number of ways available for replacement. 2664598Sbinkertn@umich.edu */ 2672794Sktlim@umich.edu virtual void setWayAllocationMax(int ways) override 2682316SN/A { 2698733Sgeoffrey.blake@arm.com fatal_if(ways < 1, "Allocation limit must be greater than zero"); 2708707Sandreas.hansson@arm.com allocAssoc = ways; 2712316SN/A } 2724598Sbinkertn@umich.edu 2734598Sbinkertn@umich.edu /** 2744598Sbinkertn@umich.edu * Get the way allocation mask limit. 2752794Sktlim@umich.edu * @return The maximum number of ways available for replacement. 2762316SN/A */ 2778793Sgblack@eecs.umich.edu virtual int getWayAllocationMax() const override 2788793Sgblack@eecs.umich.edu { 2798793Sgblack@eecs.umich.edu return allocAssoc; 2808793Sgblack@eecs.umich.edu } 2811681SN/A 2822325SN/A /** 2832325SN/A * Generate the tag from the given address. 2842325SN/A * @param addr The address to get the tag from. 2851060SN/A * @return The tag of the address. 2862292SN/A */ 2872292SN/A Addr extractTag(Addr addr) const override 2882292SN/A { 2892292SN/A return (addr >> tagShift); 2902292SN/A } 2912292SN/A 2921060SN/A /** 2931060SN/A * Regenerate the block address from the tag and set. 2941060SN/A * 2951060SN/A * @param block The block. 2961060SN/A * @return the block address. 2971060SN/A */ 2981060SN/A Addr regenerateBlkAddr(const CacheBlk* blk) const override 2991060SN/A { 3001060SN/A return ((blk->tag << tagShift) | ((Addr)blk->set << setShift)); 3011060SN/A } 3021060SN/A 3032292SN/A void forEachBlk(std::function<void(CacheBlk &)> visitor) override { 3041060SN/A for (CacheBlk& blk : blks) { 3051060SN/A visitor(blk); 3061060SN/A } 3071060SN/A } 3081060SN/A 3091060SN/A bool anyBlk(std::function<bool(CacheBlk &)> visitor) override { 3101060SN/A for (CacheBlk& blk : blks) { 3111060SN/A if (visitor(blk)) { 3122292SN/A return true; 3132292SN/A } 3142292SN/A } 3152292SN/A return false; 3168793Sgblack@eecs.umich.edu } 3178793Sgblack@eecs.umich.edu 3188793Sgblack@eecs.umich.edu private: 3198793Sgblack@eecs.umich.edu /** 3208793Sgblack@eecs.umich.edu * Calculate the set index from the address. 3212831Sksewell@umich.edu * 3228793Sgblack@eecs.umich.edu * @param addr The address to get the set from. 3238793Sgblack@eecs.umich.edu * @return The set index of the address. 3248793Sgblack@eecs.umich.edu */ 3258793Sgblack@eecs.umich.edu int extractSet(Addr addr) const 3268793Sgblack@eecs.umich.edu { 3272831Sksewell@umich.edu return ((addr >> setShift) & setMask); 3282292SN/A } 3292316SN/A}; 3302292SN/A 3312292SN/A#endif //__MEM_CACHE_TAGS_BASE_SET_ASSOC_HH__ 3322292SN/A