fa_lru.cc revision 11722
12810Srdreslin@umich.edu/* 29796Sprakash.ramrakhyani@arm.com * Copyright (c) 2013 ARM Limited 39796Sprakash.ramrakhyani@arm.com * All rights reserved. 49796Sprakash.ramrakhyani@arm.com * 59796Sprakash.ramrakhyani@arm.com * The license below extends only to copyright in the software and shall 69796Sprakash.ramrakhyani@arm.com * not be construed as granting a license to any other intellectual 79796Sprakash.ramrakhyani@arm.com * property including but not limited to intellectual property relating 89796Sprakash.ramrakhyani@arm.com * to a hardware implementation of the functionality of the software 99796Sprakash.ramrakhyani@arm.com * licensed hereunder. You may use the software subject to the license 109796Sprakash.ramrakhyani@arm.com * terms below provided that you ensure that this notice is replicated 119796Sprakash.ramrakhyani@arm.com * unmodified and in its entirety in all distributions of the software, 129796Sprakash.ramrakhyani@arm.com * modified or unmodified, in source code or in binary form. 139796Sprakash.ramrakhyani@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 * Definitions a fully associative LRU tagstore. 462810Srdreslin@umich.edu */ 472810Srdreslin@umich.edu 4811486Snikos.nikoleris@arm.com#include "mem/cache/tags/fa_lru.hh" 4911486Snikos.nikoleris@arm.com 506216Snate@binkert.org#include <cassert> 512810Srdreslin@umich.edu#include <sstream> 522810Srdreslin@umich.edu 532810Srdreslin@umich.edu#include "base/intmath.hh" 542814Srdreslin@umich.edu#include "base/misc.hh" 552810Srdreslin@umich.edu 562810Srdreslin@umich.eduusing namespace std; 572810Srdreslin@umich.edu 589796Sprakash.ramrakhyani@arm.comFALRU::FALRU(const Params *p) 5910360Sandreas.hansson@arm.com : BaseTags(p), cacheBoundaries(nullptr) 602810Srdreslin@umich.edu{ 612810Srdreslin@umich.edu if (!isPowerOf2(blkSize)) 622810Srdreslin@umich.edu fatal("cache block size (in bytes) `%d' must be a power of two", 632810Srdreslin@umich.edu blkSize); 642810Srdreslin@umich.edu if (!isPowerOf2(size)) 652810Srdreslin@umich.edu fatal("Cache Size must be power of 2 for now"); 662810Srdreslin@umich.edu 672810Srdreslin@umich.edu // Track all cache sizes from 128K up by powers of 2 682810Srdreslin@umich.edu numCaches = floorLog2(size) - 17; 692810Srdreslin@umich.edu if (numCaches >0){ 702810Srdreslin@umich.edu cacheBoundaries = new FALRUBlk *[numCaches]; 7111189Sandreas.hansson@arm.com cacheMask = (ULL(1) << numCaches) - 1; 722810Srdreslin@umich.edu } else { 732810Srdreslin@umich.edu cacheMask = 0; 742810Srdreslin@umich.edu } 752810Srdreslin@umich.edu 762810Srdreslin@umich.edu warmupBound = size/blkSize; 776978SLisa.Hsu@amd.com numBlocks = size/blkSize; 782810Srdreslin@umich.edu 796978SLisa.Hsu@amd.com blks = new FALRUBlk[numBlocks]; 802810Srdreslin@umich.edu head = &(blks[0]); 816978SLisa.Hsu@amd.com tail = &(blks[numBlocks-1]); 822810Srdreslin@umich.edu 8311484Snikos.nikoleris@arm.com head->prev = nullptr; 842810Srdreslin@umich.edu head->next = &(blks[1]); 852810Srdreslin@umich.edu head->inCache = cacheMask; 862810Srdreslin@umich.edu 876978SLisa.Hsu@amd.com tail->prev = &(blks[numBlocks-2]); 8811484Snikos.nikoleris@arm.com tail->next = nullptr; 892810Srdreslin@umich.edu tail->inCache = 0; 902810Srdreslin@umich.edu 916227Snate@binkert.org unsigned index = (1 << 17) / blkSize; 926227Snate@binkert.org unsigned j = 0; 932810Srdreslin@umich.edu int flags = cacheMask; 946978SLisa.Hsu@amd.com for (unsigned i = 1; i < numBlocks - 1; i++) { 952810Srdreslin@umich.edu blks[i].inCache = flags; 962810Srdreslin@umich.edu if (i == index - 1){ 972810Srdreslin@umich.edu cacheBoundaries[j] = &(blks[i]); 982810Srdreslin@umich.edu flags &= ~ (1<<j); 992810Srdreslin@umich.edu ++j; 1002810Srdreslin@umich.edu index = index << 1; 1012810Srdreslin@umich.edu } 1022810Srdreslin@umich.edu blks[i].prev = &(blks[i-1]); 1032810Srdreslin@umich.edu blks[i].next = &(blks[i+1]); 1042810Srdreslin@umich.edu blks[i].isTouched = false; 10510941Sdavid.guillen@arm.com blks[i].set = 0; 10610941Sdavid.guillen@arm.com blks[i].way = i; 1072810Srdreslin@umich.edu } 1082810Srdreslin@umich.edu assert(j == numCaches); 1096978SLisa.Hsu@amd.com assert(index == numBlocks); 1102810Srdreslin@umich.edu //assert(check()); 1112810Srdreslin@umich.edu} 1122810Srdreslin@umich.edu 1139086Sandreas.hansson@arm.comFALRU::~FALRU() 1149086Sandreas.hansson@arm.com{ 1159086Sandreas.hansson@arm.com if (numCaches) 1169086Sandreas.hansson@arm.com delete[] cacheBoundaries; 1179086Sandreas.hansson@arm.com 1189086Sandreas.hansson@arm.com delete[] blks; 1199086Sandreas.hansson@arm.com} 1209086Sandreas.hansson@arm.com 1212810Srdreslin@umich.eduvoid 1229796Sprakash.ramrakhyani@arm.comFALRU::regStats() 1232810Srdreslin@umich.edu{ 1242810Srdreslin@umich.edu using namespace Stats; 1259796Sprakash.ramrakhyani@arm.com BaseTags::regStats(); 1262810Srdreslin@umich.edu hits 1272810Srdreslin@umich.edu .init(numCaches+1) 1289796Sprakash.ramrakhyani@arm.com .name(name() + ".falru_hits") 1292810Srdreslin@umich.edu .desc("The number of hits in each cache size.") 1302810Srdreslin@umich.edu ; 1312810Srdreslin@umich.edu misses 1322810Srdreslin@umich.edu .init(numCaches+1) 1339796Sprakash.ramrakhyani@arm.com .name(name() + ".falru_misses") 1342810Srdreslin@umich.edu .desc("The number of misses in each cache size.") 1352810Srdreslin@umich.edu ; 1362810Srdreslin@umich.edu accesses 1379796Sprakash.ramrakhyani@arm.com .name(name() + ".falru_accesses") 1382810Srdreslin@umich.edu .desc("The number of accesses to the FA LRU cache.") 1392810Srdreslin@umich.edu ; 1402810Srdreslin@umich.edu 1416227Snate@binkert.org for (unsigned i = 0; i <= numCaches; ++i) { 1422810Srdreslin@umich.edu stringstream size_str; 1432810Srdreslin@umich.edu if (i < 3){ 1442810Srdreslin@umich.edu size_str << (1<<(i+7)) <<"K"; 1452810Srdreslin@umich.edu } else { 1462810Srdreslin@umich.edu size_str << (1<<(i-3)) <<"M"; 1472810Srdreslin@umich.edu } 1482810Srdreslin@umich.edu 1492810Srdreslin@umich.edu hits.subname(i, size_str.str()); 1502810Srdreslin@umich.edu hits.subdesc(i, "Hits in a " + size_str.str() +" cache"); 1512810Srdreslin@umich.edu misses.subname(i, size_str.str()); 1522810Srdreslin@umich.edu misses.subdesc(i, "Misses in a " + size_str.str() +" cache"); 1532810Srdreslin@umich.edu } 1542810Srdreslin@umich.edu} 1552810Srdreslin@umich.edu 1562810Srdreslin@umich.eduFALRUBlk * 1572810Srdreslin@umich.eduFALRU::hashLookup(Addr addr) const 1582810Srdreslin@umich.edu{ 1592810Srdreslin@umich.edu tagIterator iter = tagHash.find(addr); 1602810Srdreslin@umich.edu if (iter != tagHash.end()) { 1612810Srdreslin@umich.edu return (*iter).second; 1622810Srdreslin@umich.edu } 16311484Snikos.nikoleris@arm.com return nullptr; 1642810Srdreslin@umich.edu} 1652810Srdreslin@umich.edu 1662810Srdreslin@umich.eduvoid 16710815Sdavid.guillen@arm.comFALRU::invalidate(CacheBlk *blk) 1682810Srdreslin@umich.edu{ 1699214Slena@cs.wisc.edu assert(blk); 1709214Slena@cs.wisc.edu tagsInUse--; 1712810Srdreslin@umich.edu} 1722810Srdreslin@umich.edu 17310815Sdavid.guillen@arm.comCacheBlk* 17410815Sdavid.guillen@arm.comFALRU::accessBlock(Addr addr, bool is_secure, Cycles &lat, int context_src) 17510815Sdavid.guillen@arm.com{ 17610815Sdavid.guillen@arm.com return accessBlock(addr, is_secure, lat, context_src, 0); 17710815Sdavid.guillen@arm.com} 17810815Sdavid.guillen@arm.com 17910815Sdavid.guillen@arm.comCacheBlk* 18010028SGiacomo.Gabrielli@arm.comFALRU::accessBlock(Addr addr, bool is_secure, Cycles &lat, int context_src, 18110028SGiacomo.Gabrielli@arm.com int *inCache) 1822810Srdreslin@umich.edu{ 1832810Srdreslin@umich.edu accesses++; 1842810Srdreslin@umich.edu int tmp_in_cache = 0; 1852810Srdreslin@umich.edu Addr blkAddr = blkAlign(addr); 1862810Srdreslin@umich.edu FALRUBlk* blk = hashLookup(blkAddr); 1872810Srdreslin@umich.edu 1882810Srdreslin@umich.edu if (blk && blk->isValid()) { 18911722Ssophiane.senni@gmail.com // If a cache hit 19011722Ssophiane.senni@gmail.com lat = accessLatency; 19111722Ssophiane.senni@gmail.com // Check if the block to be accessed is available. If not, 19211722Ssophiane.senni@gmail.com // apply the accessLatency on top of block->whenReady. 19311722Ssophiane.senni@gmail.com if (blk->whenReady > curTick() && 19411722Ssophiane.senni@gmail.com cache->ticksToCycles(blk->whenReady - curTick()) > 19511722Ssophiane.senni@gmail.com accessLatency) { 19611722Ssophiane.senni@gmail.com lat = cache->ticksToCycles(blk->whenReady - curTick()) + 19711722Ssophiane.senni@gmail.com accessLatency; 19811722Ssophiane.senni@gmail.com } 1992810Srdreslin@umich.edu assert(blk->tag == blkAddr); 2002810Srdreslin@umich.edu tmp_in_cache = blk->inCache; 2016227Snate@binkert.org for (unsigned i = 0; i < numCaches; i++) { 2022810Srdreslin@umich.edu if (1<<i & blk->inCache) { 2032810Srdreslin@umich.edu hits[i]++; 2042810Srdreslin@umich.edu } else { 2052810Srdreslin@umich.edu misses[i]++; 2062810Srdreslin@umich.edu } 2072810Srdreslin@umich.edu } 2082810Srdreslin@umich.edu hits[numCaches]++; 2092810Srdreslin@umich.edu if (blk != head){ 2102810Srdreslin@umich.edu moveToHead(blk); 2112810Srdreslin@umich.edu } 2122810Srdreslin@umich.edu } else { 21311722Ssophiane.senni@gmail.com // If a cache miss 21411722Ssophiane.senni@gmail.com lat = lookupLatency; 21511484Snikos.nikoleris@arm.com blk = nullptr; 2166227Snate@binkert.org for (unsigned i = 0; i <= numCaches; ++i) { 2172810Srdreslin@umich.edu misses[i]++; 2182810Srdreslin@umich.edu } 2192810Srdreslin@umich.edu } 2202810Srdreslin@umich.edu if (inCache) { 2212810Srdreslin@umich.edu *inCache = tmp_in_cache; 2222810Srdreslin@umich.edu } 2232810Srdreslin@umich.edu 2242810Srdreslin@umich.edu //assert(check()); 2252810Srdreslin@umich.edu return blk; 2262810Srdreslin@umich.edu} 2272810Srdreslin@umich.edu 2282810Srdreslin@umich.edu 22910815Sdavid.guillen@arm.comCacheBlk* 23010028SGiacomo.Gabrielli@arm.comFALRU::findBlock(Addr addr, bool is_secure) const 2312810Srdreslin@umich.edu{ 2322810Srdreslin@umich.edu Addr blkAddr = blkAlign(addr); 2332810Srdreslin@umich.edu FALRUBlk* blk = hashLookup(blkAddr); 2342810Srdreslin@umich.edu 2352810Srdreslin@umich.edu if (blk && blk->isValid()) { 2362810Srdreslin@umich.edu assert(blk->tag == blkAddr); 2372810Srdreslin@umich.edu } else { 23811484Snikos.nikoleris@arm.com blk = nullptr; 2392810Srdreslin@umich.edu } 2402810Srdreslin@umich.edu return blk; 2412810Srdreslin@umich.edu} 2422810Srdreslin@umich.edu 24310815Sdavid.guillen@arm.comCacheBlk* 24410941Sdavid.guillen@arm.comFALRU::findBlockBySetAndWay(int set, int way) const 24510941Sdavid.guillen@arm.com{ 24610941Sdavid.guillen@arm.com assert(set == 0); 24710941Sdavid.guillen@arm.com return &blks[way]; 24810941Sdavid.guillen@arm.com} 24910941Sdavid.guillen@arm.com 25010941Sdavid.guillen@arm.comCacheBlk* 25110048Saminfar@gmail.comFALRU::findVictim(Addr addr) 2522810Srdreslin@umich.edu{ 2532810Srdreslin@umich.edu FALRUBlk * blk = tail; 2542810Srdreslin@umich.edu assert(blk->inCache == 0); 2552810Srdreslin@umich.edu moveToHead(blk); 2562810Srdreslin@umich.edu tagHash.erase(blk->tag); 2574626Sstever@eecs.umich.edu tagHash[blkAlign(addr)] = blk; 2582810Srdreslin@umich.edu if (blk->isValid()) { 2592814Srdreslin@umich.edu replacements[0]++; 2602810Srdreslin@umich.edu } else { 2612810Srdreslin@umich.edu tagsInUse++; 2622810Srdreslin@umich.edu blk->isTouched = true; 2632810Srdreslin@umich.edu if (!warmedUp && tagsInUse.value() >= warmupBound) { 2642810Srdreslin@umich.edu warmedUp = true; 2657823Ssteve.reinhardt@amd.com warmupCycle = curTick(); 2662810Srdreslin@umich.edu } 2672810Srdreslin@umich.edu } 2682810Srdreslin@umich.edu //assert(check()); 2692810Srdreslin@umich.edu return blk; 2702810Srdreslin@umich.edu} 2712810Srdreslin@umich.edu 2722810Srdreslin@umich.eduvoid 27310815Sdavid.guillen@arm.comFALRU::insertBlock(PacketPtr pkt, CacheBlk *blk) 2745717Shsul@eecs.umich.edu{ 2755717Shsul@eecs.umich.edu} 2765717Shsul@eecs.umich.edu 2775717Shsul@eecs.umich.eduvoid 2782810Srdreslin@umich.eduFALRU::moveToHead(FALRUBlk *blk) 2792810Srdreslin@umich.edu{ 2802810Srdreslin@umich.edu int updateMask = blk->inCache ^ cacheMask; 2816227Snate@binkert.org for (unsigned i = 0; i < numCaches; i++){ 2822810Srdreslin@umich.edu if ((1<<i) & updateMask) { 2832810Srdreslin@umich.edu cacheBoundaries[i]->inCache &= ~(1<<i); 2842810Srdreslin@umich.edu cacheBoundaries[i] = cacheBoundaries[i]->prev; 2852810Srdreslin@umich.edu } else if (cacheBoundaries[i] == blk) { 2862810Srdreslin@umich.edu cacheBoundaries[i] = blk->prev; 2872810Srdreslin@umich.edu } 2882810Srdreslin@umich.edu } 2892810Srdreslin@umich.edu blk->inCache = cacheMask; 2902810Srdreslin@umich.edu if (blk != head) { 2912810Srdreslin@umich.edu if (blk == tail){ 29211484Snikos.nikoleris@arm.com assert(blk->next == nullptr); 2932810Srdreslin@umich.edu tail = blk->prev; 29411484Snikos.nikoleris@arm.com tail->next = nullptr; 2952810Srdreslin@umich.edu } else { 2962810Srdreslin@umich.edu blk->prev->next = blk->next; 2972810Srdreslin@umich.edu blk->next->prev = blk->prev; 2982810Srdreslin@umich.edu } 2992810Srdreslin@umich.edu blk->next = head; 30011484Snikos.nikoleris@arm.com blk->prev = nullptr; 3012810Srdreslin@umich.edu head->prev = blk; 3022810Srdreslin@umich.edu head = blk; 3032810Srdreslin@umich.edu } 3042810Srdreslin@umich.edu} 3052810Srdreslin@umich.edu 3062810Srdreslin@umich.edubool 3072810Srdreslin@umich.eduFALRU::check() 3082810Srdreslin@umich.edu{ 3092810Srdreslin@umich.edu FALRUBlk* blk = head; 3109550Sandreas.hansson@arm.com int tot_size = 0; 3112810Srdreslin@umich.edu int boundary = 1<<17; 3122810Srdreslin@umich.edu int j = 0; 3132810Srdreslin@umich.edu int flags = cacheMask; 3142810Srdreslin@umich.edu while (blk) { 3159550Sandreas.hansson@arm.com tot_size += blkSize; 3162810Srdreslin@umich.edu if (blk->inCache != flags) { 3172810Srdreslin@umich.edu return false; 3182810Srdreslin@umich.edu } 3199550Sandreas.hansson@arm.com if (tot_size == boundary && blk != tail) { 3202810Srdreslin@umich.edu if (cacheBoundaries[j] != blk) { 3212810Srdreslin@umich.edu return false; 3222810Srdreslin@umich.edu } 3232810Srdreslin@umich.edu flags &=~(1 << j); 3242810Srdreslin@umich.edu boundary = boundary<<1; 3252810Srdreslin@umich.edu ++j; 3262810Srdreslin@umich.edu } 3272810Srdreslin@umich.edu blk = blk->next; 3282810Srdreslin@umich.edu } 3292810Srdreslin@umich.edu return true; 3302810Srdreslin@umich.edu} 3317612SGene.Wu@arm.com 3329796Sprakash.ramrakhyani@arm.comFALRU * 3339796Sprakash.ramrakhyani@arm.comFALRUParams::create() 3349796Sprakash.ramrakhyani@arm.com{ 3359796Sprakash.ramrakhyani@arm.com return new FALRU(this); 3369796Sprakash.ramrakhyani@arm.com} 3379796Sprakash.ramrakhyani@arm.com 338