fa_lru.cc revision 13225
12810Srdreslin@umich.edu/* 213165Sodanrc@yahoo.com.br * Copyright (c) 2018 Inria 312665Snikos.nikoleris@arm.com * Copyright (c) 2013,2016-2018 ARM Limited 49796Sprakash.ramrakhyani@arm.com * All rights reserved. 59796Sprakash.ramrakhyani@arm.com * 69796Sprakash.ramrakhyani@arm.com * The license below extends only to copyright in the software and shall 79796Sprakash.ramrakhyani@arm.com * not be construed as granting a license to any other intellectual 89796Sprakash.ramrakhyani@arm.com * property including but not limited to intellectual property relating 99796Sprakash.ramrakhyani@arm.com * to a hardware implementation of the functionality of the software 109796Sprakash.ramrakhyani@arm.com * licensed hereunder. You may use the software subject to the license 119796Sprakash.ramrakhyani@arm.com * terms below provided that you ensure that this notice is replicated 129796Sprakash.ramrakhyani@arm.com * unmodified and in its entirety in all distributions of the software, 139796Sprakash.ramrakhyani@arm.com * modified or unmodified, in source code or in binary form. 149796Sprakash.ramrakhyani@arm.com * 152810Srdreslin@umich.edu * Copyright (c) 2003-2005 The Regents of The University of Michigan 162810Srdreslin@umich.edu * All rights reserved. 172810Srdreslin@umich.edu * 182810Srdreslin@umich.edu * Redistribution and use in source and binary forms, with or without 192810Srdreslin@umich.edu * modification, are permitted provided that the following conditions are 202810Srdreslin@umich.edu * met: redistributions of source code must retain the above copyright 212810Srdreslin@umich.edu * notice, this list of conditions and the following disclaimer; 222810Srdreslin@umich.edu * redistributions in binary form must reproduce the above copyright 232810Srdreslin@umich.edu * notice, this list of conditions and the following disclaimer in the 242810Srdreslin@umich.edu * documentation and/or other materials provided with the distribution; 252810Srdreslin@umich.edu * neither the name of the copyright holders nor the names of its 262810Srdreslin@umich.edu * contributors may be used to endorse or promote products derived from 272810Srdreslin@umich.edu * this software without specific prior written permission. 282810Srdreslin@umich.edu * 292810Srdreslin@umich.edu * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 302810Srdreslin@umich.edu * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 312810Srdreslin@umich.edu * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 322810Srdreslin@umich.edu * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 332810Srdreslin@umich.edu * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 342810Srdreslin@umich.edu * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 352810Srdreslin@umich.edu * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 362810Srdreslin@umich.edu * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 372810Srdreslin@umich.edu * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 382810Srdreslin@umich.edu * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 392810Srdreslin@umich.edu * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 402810Srdreslin@umich.edu * 412810Srdreslin@umich.edu * Authors: Erik Hallnor 4212665Snikos.nikoleris@arm.com * Nikos Nikoleris 4313165Sodanrc@yahoo.com.br * Daniel Carvalho 442810Srdreslin@umich.edu */ 452810Srdreslin@umich.edu 462810Srdreslin@umich.edu/** 472810Srdreslin@umich.edu * @file 482810Srdreslin@umich.edu * Definitions a fully associative LRU tagstore. 492810Srdreslin@umich.edu */ 502810Srdreslin@umich.edu 5111486Snikos.nikoleris@arm.com#include "mem/cache/tags/fa_lru.hh" 5211486Snikos.nikoleris@arm.com 536216Snate@binkert.org#include <cassert> 542810Srdreslin@umich.edu#include <sstream> 552810Srdreslin@umich.edu 562810Srdreslin@umich.edu#include "base/intmath.hh" 5712334Sgabeblack@google.com#include "base/logging.hh" 5812727Snikos.nikoleris@arm.com#include "mem/cache/base.hh" 5913225Sodanrc@yahoo.com.br#include "mem/cache/replacement_policies/replaceable_entry.hh" 602810Srdreslin@umich.edu 6113222Sodanrc@yahoo.com.brstd::string 6213222Sodanrc@yahoo.com.brFALRUBlk::print() const 6313222Sodanrc@yahoo.com.br{ 6413222Sodanrc@yahoo.com.br return csprintf("%s inCachesMask: %#x", CacheBlk::print(), inCachesMask); 6513222Sodanrc@yahoo.com.br} 6613222Sodanrc@yahoo.com.br 679796Sprakash.ramrakhyani@arm.comFALRU::FALRU(const Params *p) 6812665Snikos.nikoleris@arm.com : BaseTags(p), 6912665Snikos.nikoleris@arm.com 7012665Snikos.nikoleris@arm.com cacheTracking(p->min_tracked_cache_size, size, blkSize) 712810Srdreslin@umich.edu{ 722810Srdreslin@umich.edu if (!isPowerOf2(blkSize)) 732810Srdreslin@umich.edu fatal("cache block size (in bytes) `%d' must be a power of two", 742810Srdreslin@umich.edu blkSize); 752810Srdreslin@umich.edu if (!isPowerOf2(size)) 762810Srdreslin@umich.edu fatal("Cache Size must be power of 2 for now"); 772810Srdreslin@umich.edu 7812665Snikos.nikoleris@arm.com blks = new FALRUBlk[numBlocks]; 7913216Sodanrc@yahoo.com.br} 8013216Sodanrc@yahoo.com.br 8113216Sodanrc@yahoo.com.brFALRU::~FALRU() 8213216Sodanrc@yahoo.com.br{ 8313216Sodanrc@yahoo.com.br delete[] blks; 8413216Sodanrc@yahoo.com.br} 8513216Sodanrc@yahoo.com.br 8613216Sodanrc@yahoo.com.brvoid 8713216Sodanrc@yahoo.com.brFALRU::init(BaseCache* cache) 8813216Sodanrc@yahoo.com.br{ 8913216Sodanrc@yahoo.com.br // Set parent cache 9013216Sodanrc@yahoo.com.br setCache(cache); 912810Srdreslin@umich.edu 922810Srdreslin@umich.edu head = &(blks[0]); 9311484Snikos.nikoleris@arm.com head->prev = nullptr; 942810Srdreslin@umich.edu head->next = &(blks[1]); 9513218Sodanrc@yahoo.com.br head->setPosition(0, 0); 9612629Sodanrc@yahoo.com.br head->data = &dataBlks[0]; 972810Srdreslin@umich.edu 986978SLisa.Hsu@amd.com for (unsigned i = 1; i < numBlocks - 1; i++) { 992810Srdreslin@umich.edu blks[i].prev = &(blks[i-1]); 1002810Srdreslin@umich.edu blks[i].next = &(blks[i+1]); 10113218Sodanrc@yahoo.com.br blks[i].setPosition(0, i); 10212629Sodanrc@yahoo.com.br 10312629Sodanrc@yahoo.com.br // Associate a data chunk to the block 10412629Sodanrc@yahoo.com.br blks[i].data = &dataBlks[blkSize*i]; 1052810Srdreslin@umich.edu } 10612665Snikos.nikoleris@arm.com 10712665Snikos.nikoleris@arm.com tail = &(blks[numBlocks - 1]); 10812665Snikos.nikoleris@arm.com tail->prev = &(blks[numBlocks - 2]); 10912665Snikos.nikoleris@arm.com tail->next = nullptr; 11013218Sodanrc@yahoo.com.br tail->setPosition(0, numBlocks - 1); 11112665Snikos.nikoleris@arm.com tail->data = &dataBlks[(numBlocks - 1) * blkSize]; 11212665Snikos.nikoleris@arm.com 11312665Snikos.nikoleris@arm.com cacheTracking.init(head, tail); 1142810Srdreslin@umich.edu} 1152810Srdreslin@umich.edu 1162810Srdreslin@umich.eduvoid 1179796Sprakash.ramrakhyani@arm.comFALRU::regStats() 1182810Srdreslin@umich.edu{ 1199796Sprakash.ramrakhyani@arm.com BaseTags::regStats(); 12012665Snikos.nikoleris@arm.com cacheTracking.regStats(name()); 1212810Srdreslin@umich.edu} 1222810Srdreslin@umich.edu 1232810Srdreslin@umich.eduvoid 12410815Sdavid.guillen@arm.comFALRU::invalidate(CacheBlk *blk) 1252810Srdreslin@umich.edu{ 12613165Sodanrc@yahoo.com.br // Erase block entry reference in the hash table 12713165Sodanrc@yahoo.com.br auto num_erased = tagHash.erase(std::make_pair(blk->tag, blk->isSecure())); 12813165Sodanrc@yahoo.com.br 12913165Sodanrc@yahoo.com.br // Sanity check; only one block reference should be erased 13013165Sodanrc@yahoo.com.br assert(num_erased == 1); 13113165Sodanrc@yahoo.com.br 13213165Sodanrc@yahoo.com.br // Invalidate block entry. Must be done after the hash is erased 13312566Snikos.nikoleris@arm.com BaseTags::invalidate(blk); 13412636Sodanrc@yahoo.com.br 13512745Sodanrc@yahoo.com.br // Decrease the number of tags in use 13612745Sodanrc@yahoo.com.br tagsInUse--; 13712745Sodanrc@yahoo.com.br 13812648Sodanrc@yahoo.com.br // Move the block to the tail to make it the next victim 13912648Sodanrc@yahoo.com.br moveToTail((FALRUBlk*)blk); 1402810Srdreslin@umich.edu} 1412810Srdreslin@umich.edu 14210815Sdavid.guillen@arm.comCacheBlk* 14311870Snikos.nikoleris@arm.comFALRU::accessBlock(Addr addr, bool is_secure, Cycles &lat) 14410815Sdavid.guillen@arm.com{ 14511870Snikos.nikoleris@arm.com return accessBlock(addr, is_secure, lat, 0); 14610815Sdavid.guillen@arm.com} 14710815Sdavid.guillen@arm.com 14810815Sdavid.guillen@arm.comCacheBlk* 14912665Snikos.nikoleris@arm.comFALRU::accessBlock(Addr addr, bool is_secure, Cycles &lat, 15012665Snikos.nikoleris@arm.com CachesMask *in_caches_mask) 1512810Srdreslin@umich.edu{ 15212665Snikos.nikoleris@arm.com CachesMask mask = 0; 15312677Sodanrc@yahoo.com.br FALRUBlk* blk = static_cast<FALRUBlk*>(findBlock(addr, is_secure)); 1542810Srdreslin@umich.edu 15512775Snikos.nikoleris@arm.com if (blk && blk->isValid()) { 15611722Ssophiane.senni@gmail.com // If a cache hit 15711722Ssophiane.senni@gmail.com lat = accessLatency; 15811722Ssophiane.senni@gmail.com // Check if the block to be accessed is available. If not, 15911722Ssophiane.senni@gmail.com // apply the accessLatency on top of block->whenReady. 16011722Ssophiane.senni@gmail.com if (blk->whenReady > curTick() && 16111722Ssophiane.senni@gmail.com cache->ticksToCycles(blk->whenReady - curTick()) > 16211722Ssophiane.senni@gmail.com accessLatency) { 16311722Ssophiane.senni@gmail.com lat = cache->ticksToCycles(blk->whenReady - curTick()) + 16411722Ssophiane.senni@gmail.com accessLatency; 16511722Ssophiane.senni@gmail.com } 16612665Snikos.nikoleris@arm.com mask = blk->inCachesMask; 16712677Sodanrc@yahoo.com.br 16812665Snikos.nikoleris@arm.com moveToHead(blk); 1692810Srdreslin@umich.edu } else { 17011722Ssophiane.senni@gmail.com // If a cache miss 17111722Ssophiane.senni@gmail.com lat = lookupLatency; 1722810Srdreslin@umich.edu } 17312665Snikos.nikoleris@arm.com if (in_caches_mask) { 17412665Snikos.nikoleris@arm.com *in_caches_mask = mask; 1752810Srdreslin@umich.edu } 1762810Srdreslin@umich.edu 17712665Snikos.nikoleris@arm.com cacheTracking.recordAccess(blk); 17812665Snikos.nikoleris@arm.com 1792810Srdreslin@umich.edu return blk; 1802810Srdreslin@umich.edu} 1812810Srdreslin@umich.edu 18210815Sdavid.guillen@arm.comCacheBlk* 18310028SGiacomo.Gabrielli@arm.comFALRU::findBlock(Addr addr, bool is_secure) const 1842810Srdreslin@umich.edu{ 18512775Snikos.nikoleris@arm.com FALRUBlk* blk = nullptr; 18612775Snikos.nikoleris@arm.com 18712677Sodanrc@yahoo.com.br Addr tag = extractTag(addr); 18812775Snikos.nikoleris@arm.com auto iter = tagHash.find(std::make_pair(tag, is_secure)); 18912775Snikos.nikoleris@arm.com if (iter != tagHash.end()) { 19012775Snikos.nikoleris@arm.com blk = (*iter).second; 19112775Snikos.nikoleris@arm.com } 1922810Srdreslin@umich.edu 1932810Srdreslin@umich.edu if (blk && blk->isValid()) { 19412677Sodanrc@yahoo.com.br assert(blk->tag == tag); 19512676Sodanrc@yahoo.com.br assert(blk->isSecure() == is_secure); 1962810Srdreslin@umich.edu } 19712775Snikos.nikoleris@arm.com 1982810Srdreslin@umich.edu return blk; 1992810Srdreslin@umich.edu} 2002810Srdreslin@umich.edu 20112743Sodanrc@yahoo.com.brReplaceableEntry* 20210941Sdavid.guillen@arm.comFALRU::findBlockBySetAndWay(int set, int way) const 20310941Sdavid.guillen@arm.com{ 20410941Sdavid.guillen@arm.com assert(set == 0); 20510941Sdavid.guillen@arm.com return &blks[way]; 20610941Sdavid.guillen@arm.com} 20710941Sdavid.guillen@arm.com 20810941Sdavid.guillen@arm.comCacheBlk* 20912746Sodanrc@yahoo.com.brFALRU::findVictim(Addr addr, const bool is_secure, 21012746Sodanrc@yahoo.com.br std::vector<CacheBlk*>& evict_blks) const 2112810Srdreslin@umich.edu{ 21212744Sodanrc@yahoo.com.br // The victim is always stored on the tail for the FALRU 21312744Sodanrc@yahoo.com.br FALRUBlk* victim = tail; 21412744Sodanrc@yahoo.com.br 21512744Sodanrc@yahoo.com.br // There is only one eviction for this replacement 21612744Sodanrc@yahoo.com.br evict_blks.push_back(victim); 21712744Sodanrc@yahoo.com.br 21812744Sodanrc@yahoo.com.br return victim; 2192810Srdreslin@umich.edu} 2202810Srdreslin@umich.edu 2212810Srdreslin@umich.eduvoid 22213215Sodanrc@yahoo.com.brFALRU::insertBlock(const Addr addr, const bool is_secure, 22313215Sodanrc@yahoo.com.br const int src_master_ID, const uint32_t task_ID, 22413215Sodanrc@yahoo.com.br CacheBlk *blk) 2255717Shsul@eecs.umich.edu{ 22612636Sodanrc@yahoo.com.br FALRUBlk* falruBlk = static_cast<FALRUBlk*>(blk); 22712636Sodanrc@yahoo.com.br 22812636Sodanrc@yahoo.com.br // Make sure block is not present in the cache 22912665Snikos.nikoleris@arm.com assert(falruBlk->inCachesMask == 0); 23012636Sodanrc@yahoo.com.br 23112636Sodanrc@yahoo.com.br // Do common block insertion functionality 23213215Sodanrc@yahoo.com.br BaseTags::insertBlock(addr, is_secure, src_master_ID, task_ID, blk); 23312636Sodanrc@yahoo.com.br 23412745Sodanrc@yahoo.com.br // Increment tag counter 23512745Sodanrc@yahoo.com.br tagsInUse++; 23612745Sodanrc@yahoo.com.br 23712636Sodanrc@yahoo.com.br // New block is the MRU 23812636Sodanrc@yahoo.com.br moveToHead(falruBlk); 23912636Sodanrc@yahoo.com.br 24012636Sodanrc@yahoo.com.br // Insert new block in the hash table 24112775Snikos.nikoleris@arm.com tagHash[std::make_pair(blk->tag, blk->isSecure())] = falruBlk; 2425717Shsul@eecs.umich.edu} 2435717Shsul@eecs.umich.edu 2445717Shsul@eecs.umich.eduvoid 2452810Srdreslin@umich.eduFALRU::moveToHead(FALRUBlk *blk) 2462810Srdreslin@umich.edu{ 24712648Sodanrc@yahoo.com.br // If block is not already head, do the moving 24812648Sodanrc@yahoo.com.br if (blk != head) { 24912665Snikos.nikoleris@arm.com cacheTracking.moveBlockToHead(blk); 25012648Sodanrc@yahoo.com.br // If block is tail, set previous block as new tail 2512810Srdreslin@umich.edu if (blk == tail){ 25211484Snikos.nikoleris@arm.com assert(blk->next == nullptr); 2532810Srdreslin@umich.edu tail = blk->prev; 25411484Snikos.nikoleris@arm.com tail->next = nullptr; 25512648Sodanrc@yahoo.com.br // Inform block's surrounding blocks that it has been moved 2562810Srdreslin@umich.edu } else { 2572810Srdreslin@umich.edu blk->prev->next = blk->next; 2582810Srdreslin@umich.edu blk->next->prev = blk->prev; 2592810Srdreslin@umich.edu } 26012648Sodanrc@yahoo.com.br 26112648Sodanrc@yahoo.com.br // Swap pointers 2622810Srdreslin@umich.edu blk->next = head; 26311484Snikos.nikoleris@arm.com blk->prev = nullptr; 2642810Srdreslin@umich.edu head->prev = blk; 2652810Srdreslin@umich.edu head = blk; 26612665Snikos.nikoleris@arm.com 26712665Snikos.nikoleris@arm.com cacheTracking.check(head, tail); 2682810Srdreslin@umich.edu } 2692810Srdreslin@umich.edu} 2702810Srdreslin@umich.edu 27112648Sodanrc@yahoo.com.brvoid 27212648Sodanrc@yahoo.com.brFALRU::moveToTail(FALRUBlk *blk) 27312648Sodanrc@yahoo.com.br{ 27412648Sodanrc@yahoo.com.br // If block is not already tail, do the moving 27512648Sodanrc@yahoo.com.br if (blk != tail) { 27612665Snikos.nikoleris@arm.com cacheTracking.moveBlockToTail(blk); 27712648Sodanrc@yahoo.com.br // If block is head, set next block as new head 27812648Sodanrc@yahoo.com.br if (blk == head){ 27912648Sodanrc@yahoo.com.br assert(blk->prev == nullptr); 28012648Sodanrc@yahoo.com.br head = blk->next; 28112648Sodanrc@yahoo.com.br head->prev = nullptr; 28212648Sodanrc@yahoo.com.br // Inform block's surrounding blocks that it has been moved 28312648Sodanrc@yahoo.com.br } else { 28412648Sodanrc@yahoo.com.br blk->prev->next = blk->next; 28512648Sodanrc@yahoo.com.br blk->next->prev = blk->prev; 28612648Sodanrc@yahoo.com.br } 28712648Sodanrc@yahoo.com.br 28812648Sodanrc@yahoo.com.br // Swap pointers 28912648Sodanrc@yahoo.com.br blk->prev = tail; 29012648Sodanrc@yahoo.com.br blk->next = nullptr; 29112648Sodanrc@yahoo.com.br tail->next = blk; 29212648Sodanrc@yahoo.com.br tail = blk; 29312665Snikos.nikoleris@arm.com 29412665Snikos.nikoleris@arm.com cacheTracking.check(head, tail); 29512648Sodanrc@yahoo.com.br } 29612648Sodanrc@yahoo.com.br} 29712648Sodanrc@yahoo.com.br 2989796Sprakash.ramrakhyani@arm.comFALRU * 2999796Sprakash.ramrakhyani@arm.comFALRUParams::create() 3009796Sprakash.ramrakhyani@arm.com{ 3019796Sprakash.ramrakhyani@arm.com return new FALRU(this); 3029796Sprakash.ramrakhyani@arm.com} 3039796Sprakash.ramrakhyani@arm.com 30412665Snikos.nikoleris@arm.comvoid 30513164Sodanrc@yahoo.com.brFALRU::CacheTracking::check(const FALRUBlk *head, const FALRUBlk *tail) const 30612665Snikos.nikoleris@arm.com{ 30712665Snikos.nikoleris@arm.com#ifdef FALRU_DEBUG 30813164Sodanrc@yahoo.com.br const FALRUBlk* blk = head; 30912665Snikos.nikoleris@arm.com unsigned curr_size = 0; 31012665Snikos.nikoleris@arm.com unsigned tracked_cache_size = minTrackedSize; 31112665Snikos.nikoleris@arm.com CachesMask in_caches_mask = inAllCachesMask; 31212665Snikos.nikoleris@arm.com int j = 0; 31312665Snikos.nikoleris@arm.com 31412665Snikos.nikoleris@arm.com while (blk) { 31512665Snikos.nikoleris@arm.com panic_if(blk->inCachesMask != in_caches_mask, "Expected cache mask " 31612665Snikos.nikoleris@arm.com "%x found %x", blk->inCachesMask, in_caches_mask); 31712665Snikos.nikoleris@arm.com 31812665Snikos.nikoleris@arm.com curr_size += blkSize; 31912665Snikos.nikoleris@arm.com if (curr_size == tracked_cache_size && blk != tail) { 32012665Snikos.nikoleris@arm.com panic_if(boundaries[j] != blk, "Unexpected boundary for the %d-th " 32112665Snikos.nikoleris@arm.com "cache", j); 32212665Snikos.nikoleris@arm.com tracked_cache_size <<= 1; 32312665Snikos.nikoleris@arm.com // from this point, blocks fit only in the larger caches 32412665Snikos.nikoleris@arm.com in_caches_mask &= ~(1U << j); 32512665Snikos.nikoleris@arm.com ++j; 32612665Snikos.nikoleris@arm.com } 32712665Snikos.nikoleris@arm.com blk = blk->next; 32812665Snikos.nikoleris@arm.com } 32912665Snikos.nikoleris@arm.com#endif // FALRU_DEBUG 33012665Snikos.nikoleris@arm.com} 33112665Snikos.nikoleris@arm.com 33212665Snikos.nikoleris@arm.comvoid 33312665Snikos.nikoleris@arm.comFALRU::CacheTracking::init(FALRUBlk *head, FALRUBlk *tail) 33412665Snikos.nikoleris@arm.com{ 33512665Snikos.nikoleris@arm.com // early exit if we are not tracking any extra caches 33612665Snikos.nikoleris@arm.com FALRUBlk* blk = numTrackedCaches ? head : nullptr; 33712665Snikos.nikoleris@arm.com unsigned curr_size = 0; 33812665Snikos.nikoleris@arm.com unsigned tracked_cache_size = minTrackedSize; 33912665Snikos.nikoleris@arm.com CachesMask in_caches_mask = inAllCachesMask; 34012665Snikos.nikoleris@arm.com int j = 0; 34112665Snikos.nikoleris@arm.com 34212665Snikos.nikoleris@arm.com while (blk) { 34312665Snikos.nikoleris@arm.com blk->inCachesMask = in_caches_mask; 34412665Snikos.nikoleris@arm.com 34512665Snikos.nikoleris@arm.com curr_size += blkSize; 34612665Snikos.nikoleris@arm.com if (curr_size == tracked_cache_size && blk != tail) { 34712665Snikos.nikoleris@arm.com boundaries[j] = blk; 34812665Snikos.nikoleris@arm.com 34912665Snikos.nikoleris@arm.com tracked_cache_size <<= 1; 35012665Snikos.nikoleris@arm.com // from this point, blocks fit only in the larger caches 35112665Snikos.nikoleris@arm.com in_caches_mask &= ~(1U << j); 35212665Snikos.nikoleris@arm.com ++j; 35312665Snikos.nikoleris@arm.com } 35412665Snikos.nikoleris@arm.com blk = blk->next; 35512665Snikos.nikoleris@arm.com } 35612665Snikos.nikoleris@arm.com} 35712665Snikos.nikoleris@arm.com 35812665Snikos.nikoleris@arm.com 35912665Snikos.nikoleris@arm.comvoid 36012665Snikos.nikoleris@arm.comFALRU::CacheTracking::moveBlockToHead(FALRUBlk *blk) 36112665Snikos.nikoleris@arm.com{ 36212665Snikos.nikoleris@arm.com // Get the mask of all caches, in which the block didn't fit 36312665Snikos.nikoleris@arm.com // before moving it to the head 36412665Snikos.nikoleris@arm.com CachesMask update_caches_mask = inAllCachesMask ^ blk->inCachesMask; 36512665Snikos.nikoleris@arm.com 36612665Snikos.nikoleris@arm.com for (int i = 0; i < numTrackedCaches; i++) { 36712665Snikos.nikoleris@arm.com CachesMask current_cache_mask = 1U << i; 36812665Snikos.nikoleris@arm.com if (current_cache_mask & update_caches_mask) { 36912665Snikos.nikoleris@arm.com // if the ith cache didn't fit the block (before it is moved to 37012665Snikos.nikoleris@arm.com // the head), move the ith boundary 1 block closer to the 37112665Snikos.nikoleris@arm.com // MRU 37212665Snikos.nikoleris@arm.com boundaries[i]->inCachesMask &= ~current_cache_mask; 37312665Snikos.nikoleris@arm.com boundaries[i] = boundaries[i]->prev; 37412665Snikos.nikoleris@arm.com } else if (boundaries[i] == blk) { 37512665Snikos.nikoleris@arm.com // Make sure the boundary doesn't point to the block 37612665Snikos.nikoleris@arm.com // we are about to move 37712665Snikos.nikoleris@arm.com boundaries[i] = blk->prev; 37812665Snikos.nikoleris@arm.com } 37912665Snikos.nikoleris@arm.com } 38012665Snikos.nikoleris@arm.com 38112665Snikos.nikoleris@arm.com // Make block reside in all caches 38212665Snikos.nikoleris@arm.com blk->inCachesMask = inAllCachesMask; 38312665Snikos.nikoleris@arm.com} 38412665Snikos.nikoleris@arm.com 38512665Snikos.nikoleris@arm.comvoid 38612665Snikos.nikoleris@arm.comFALRU::CacheTracking::moveBlockToTail(FALRUBlk *blk) 38712665Snikos.nikoleris@arm.com{ 38812665Snikos.nikoleris@arm.com CachesMask update_caches_mask = blk->inCachesMask; 38912665Snikos.nikoleris@arm.com 39012665Snikos.nikoleris@arm.com for (int i = 0; i < numTrackedCaches; i++) { 39112665Snikos.nikoleris@arm.com CachesMask current_cache_mask = 1U << i; 39212665Snikos.nikoleris@arm.com if (current_cache_mask & update_caches_mask) { 39312665Snikos.nikoleris@arm.com // if the ith cache fitted the block (before it is moved to 39412665Snikos.nikoleris@arm.com // the tail), move the ith boundary 1 block closer to the 39512665Snikos.nikoleris@arm.com // LRU 39612665Snikos.nikoleris@arm.com boundaries[i] = boundaries[i]->next; 39712665Snikos.nikoleris@arm.com if (boundaries[i] == blk) { 39812665Snikos.nikoleris@arm.com // Make sure the boundary doesn't point to the block 39912665Snikos.nikoleris@arm.com // we are about to move 40012665Snikos.nikoleris@arm.com boundaries[i] = blk->next; 40112665Snikos.nikoleris@arm.com } 40212665Snikos.nikoleris@arm.com boundaries[i]->inCachesMask |= current_cache_mask; 40312665Snikos.nikoleris@arm.com } 40412665Snikos.nikoleris@arm.com } 40512665Snikos.nikoleris@arm.com 40612665Snikos.nikoleris@arm.com // The block now fits only in the actual cache 40712665Snikos.nikoleris@arm.com blk->inCachesMask = 0; 40812665Snikos.nikoleris@arm.com} 40912665Snikos.nikoleris@arm.com 41012665Snikos.nikoleris@arm.comvoid 41112665Snikos.nikoleris@arm.comFALRU::CacheTracking::recordAccess(FALRUBlk *blk) 41212665Snikos.nikoleris@arm.com{ 41312665Snikos.nikoleris@arm.com for (int i = 0; i < numTrackedCaches; i++) { 41412665Snikos.nikoleris@arm.com if (blk && ((1U << i) & blk->inCachesMask)) { 41512665Snikos.nikoleris@arm.com hits[i]++; 41612665Snikos.nikoleris@arm.com } else { 41712665Snikos.nikoleris@arm.com misses[i]++; 41812665Snikos.nikoleris@arm.com } 41912665Snikos.nikoleris@arm.com } 42012665Snikos.nikoleris@arm.com 42112665Snikos.nikoleris@arm.com // Record stats for the actual cache too 42212775Snikos.nikoleris@arm.com if (blk && blk->isValid()) { 42312665Snikos.nikoleris@arm.com hits[numTrackedCaches]++; 42412665Snikos.nikoleris@arm.com } else { 42512665Snikos.nikoleris@arm.com misses[numTrackedCaches]++; 42612665Snikos.nikoleris@arm.com } 42712665Snikos.nikoleris@arm.com 42812665Snikos.nikoleris@arm.com accesses++; 42912665Snikos.nikoleris@arm.com} 43012665Snikos.nikoleris@arm.com 43112665Snikos.nikoleris@arm.comvoid 43212665Snikos.nikoleris@arm.comprintSize(std::ostream &stream, size_t size) 43312665Snikos.nikoleris@arm.com{ 43412665Snikos.nikoleris@arm.com static const char *SIZES[] = { "B", "kB", "MB", "GB", "TB", "ZB" }; 43512665Snikos.nikoleris@arm.com int div = 0; 43612665Snikos.nikoleris@arm.com while (size >= 1024 && div < (sizeof SIZES / sizeof *SIZES)) { 43712665Snikos.nikoleris@arm.com div++; 43812665Snikos.nikoleris@arm.com size >>= 10; 43912665Snikos.nikoleris@arm.com } 44012665Snikos.nikoleris@arm.com stream << size << SIZES[div]; 44112665Snikos.nikoleris@arm.com} 44212665Snikos.nikoleris@arm.com 44312665Snikos.nikoleris@arm.comvoid 44412665Snikos.nikoleris@arm.comFALRU::CacheTracking::regStats(std::string name) 44512665Snikos.nikoleris@arm.com{ 44612665Snikos.nikoleris@arm.com hits 44712665Snikos.nikoleris@arm.com .init(numTrackedCaches + 1) 44812665Snikos.nikoleris@arm.com .name(name + ".falru_hits") 44912665Snikos.nikoleris@arm.com .desc("The number of hits in each cache size.") 45012665Snikos.nikoleris@arm.com ; 45112665Snikos.nikoleris@arm.com misses 45212665Snikos.nikoleris@arm.com .init(numTrackedCaches + 1) 45312665Snikos.nikoleris@arm.com .name(name + ".falru_misses") 45412665Snikos.nikoleris@arm.com .desc("The number of misses in each cache size.") 45512665Snikos.nikoleris@arm.com ; 45612665Snikos.nikoleris@arm.com accesses 45712665Snikos.nikoleris@arm.com .name(name + ".falru_accesses") 45812665Snikos.nikoleris@arm.com .desc("The number of accesses to the FA LRU cache.") 45912665Snikos.nikoleris@arm.com ; 46012665Snikos.nikoleris@arm.com 46112665Snikos.nikoleris@arm.com for (unsigned i = 0; i < numTrackedCaches + 1; ++i) { 46212665Snikos.nikoleris@arm.com std::stringstream size_str; 46312665Snikos.nikoleris@arm.com printSize(size_str, minTrackedSize << i); 46412665Snikos.nikoleris@arm.com hits.subname(i, size_str.str()); 46512665Snikos.nikoleris@arm.com hits.subdesc(i, "Hits in a " + size_str.str() + " cache"); 46612665Snikos.nikoleris@arm.com misses.subname(i, size_str.str()); 46712665Snikos.nikoleris@arm.com misses.subdesc(i, "Misses in a " + size_str.str() + " cache"); 46812665Snikos.nikoleris@arm.com } 46912665Snikos.nikoleris@arm.com} 470