112752Sodanrc@yahoo.com.br/* 212752Sodanrc@yahoo.com.br * Copyright (c) 2018 Inria 312752Sodanrc@yahoo.com.br * All rights reserved. 412752Sodanrc@yahoo.com.br * 512752Sodanrc@yahoo.com.br * Redistribution and use in source and binary forms, with or without 612752Sodanrc@yahoo.com.br * modification, are permitted provided that the following conditions are 712752Sodanrc@yahoo.com.br * met: redistributions of source code must retain the above copyright 812752Sodanrc@yahoo.com.br * notice, this list of conditions and the following disclaimer; 912752Sodanrc@yahoo.com.br * redistributions in binary form must reproduce the above copyright 1012752Sodanrc@yahoo.com.br * notice, this list of conditions and the following disclaimer in the 1112752Sodanrc@yahoo.com.br * documentation and/or other materials provided with the distribution; 1212752Sodanrc@yahoo.com.br * neither the name of the copyright holders nor the names of its 1312752Sodanrc@yahoo.com.br * contributors may be used to endorse or promote products derived from 1412752Sodanrc@yahoo.com.br * this software without specific prior written permission. 1512752Sodanrc@yahoo.com.br * 1612752Sodanrc@yahoo.com.br * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1712752Sodanrc@yahoo.com.br * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1812752Sodanrc@yahoo.com.br * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1912752Sodanrc@yahoo.com.br * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2012752Sodanrc@yahoo.com.br * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2112752Sodanrc@yahoo.com.br * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2212752Sodanrc@yahoo.com.br * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2312752Sodanrc@yahoo.com.br * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2412752Sodanrc@yahoo.com.br * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2512752Sodanrc@yahoo.com.br * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2612752Sodanrc@yahoo.com.br * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2712752Sodanrc@yahoo.com.br * 2812752Sodanrc@yahoo.com.br * Authors: Daniel Carvalho 2912752Sodanrc@yahoo.com.br */ 3012752Sodanrc@yahoo.com.br 3112752Sodanrc@yahoo.com.br/** 3212752Sodanrc@yahoo.com.br * @file 3313219Sodanrc@yahoo.com.br * Definitions of a sector tag store. 3412752Sodanrc@yahoo.com.br */ 3512752Sodanrc@yahoo.com.br 3612752Sodanrc@yahoo.com.br#include "mem/cache/tags/sector_tags.hh" 3712752Sodanrc@yahoo.com.br 3812752Sodanrc@yahoo.com.br#include <cassert> 3912752Sodanrc@yahoo.com.br#include <memory> 4012752Sodanrc@yahoo.com.br#include <string> 4112752Sodanrc@yahoo.com.br 4212752Sodanrc@yahoo.com.br#include "base/intmath.hh" 4312752Sodanrc@yahoo.com.br#include "base/logging.hh" 4412752Sodanrc@yahoo.com.br#include "base/types.hh" 4512752Sodanrc@yahoo.com.br#include "mem/cache/base.hh" 4612752Sodanrc@yahoo.com.br#include "mem/cache/replacement_policies/base.hh" 4713225Sodanrc@yahoo.com.br#include "mem/cache/replacement_policies/replaceable_entry.hh" 4813219Sodanrc@yahoo.com.br#include "mem/cache/tags/indexing_policies/base.hh" 4912752Sodanrc@yahoo.com.br 5012752Sodanrc@yahoo.com.brSectorTags::SectorTags(const SectorTagsParams *p) 5113219Sodanrc@yahoo.com.br : BaseTags(p), allocAssoc(p->assoc), 5212752Sodanrc@yahoo.com.br sequentialAccess(p->sequential_access), 5312752Sodanrc@yahoo.com.br replacementPolicy(p->replacement_policy), 5412752Sodanrc@yahoo.com.br numBlocksPerSector(p->num_blocks_per_sector), 5513938Sodanrc@yahoo.com.br numSectors(numBlocks / numBlocksPerSector), 5613938Sodanrc@yahoo.com.br sectorShift(floorLog2(blkSize)), sectorMask(numBlocksPerSector - 1) 5712752Sodanrc@yahoo.com.br{ 5812752Sodanrc@yahoo.com.br // Check parameters 5912752Sodanrc@yahoo.com.br fatal_if(blkSize < 4 || !isPowerOf2(blkSize), 6012752Sodanrc@yahoo.com.br "Block size must be at least 4 and a power of 2"); 6112752Sodanrc@yahoo.com.br fatal_if(!isPowerOf2(numBlocksPerSector), 6212752Sodanrc@yahoo.com.br "# of blocks per sector must be non-zero and a power of 2"); 6313216Sodanrc@yahoo.com.br} 6413216Sodanrc@yahoo.com.br 6513216Sodanrc@yahoo.com.brvoid 6613419Sodanrc@yahoo.com.brSectorTags::tagsInit() 6713216Sodanrc@yahoo.com.br{ 6813938Sodanrc@yahoo.com.br // Create blocks and sector blocks 6913938Sodanrc@yahoo.com.br blks = std::vector<SectorSubBlk>(numBlocks); 7013938Sodanrc@yahoo.com.br secBlks = std::vector<SectorBlk>(numSectors); 7113938Sodanrc@yahoo.com.br 7213219Sodanrc@yahoo.com.br // Initialize all blocks 7312752Sodanrc@yahoo.com.br unsigned blk_index = 0; // index into blks array 7413219Sodanrc@yahoo.com.br for (unsigned sec_blk_index = 0; sec_blk_index < numSectors; 7513219Sodanrc@yahoo.com.br sec_blk_index++) 7613219Sodanrc@yahoo.com.br { 7713219Sodanrc@yahoo.com.br // Locate next cache sector 7813219Sodanrc@yahoo.com.br SectorBlk* sec_blk = &secBlks[sec_blk_index]; 7912752Sodanrc@yahoo.com.br 8013219Sodanrc@yahoo.com.br // Associate a replacement data entry to the sector 8113219Sodanrc@yahoo.com.br sec_blk->replacementData = replacementPolicy->instantiateEntry(); 8213219Sodanrc@yahoo.com.br 8313219Sodanrc@yahoo.com.br // Initialize all blocks in this sector 8413219Sodanrc@yahoo.com.br sec_blk->blks.resize(numBlocksPerSector); 8513219Sodanrc@yahoo.com.br for (unsigned k = 0; k < numBlocksPerSector; ++k){ 8612752Sodanrc@yahoo.com.br // Select block within the set to be linked 8713219Sodanrc@yahoo.com.br SectorSubBlk*& blk = sec_blk->blks[k]; 8812752Sodanrc@yahoo.com.br 8913219Sodanrc@yahoo.com.br // Locate next cache block 9013219Sodanrc@yahoo.com.br blk = &blks[blk_index]; 9112752Sodanrc@yahoo.com.br 9213219Sodanrc@yahoo.com.br // Associate a data chunk to the block 9313219Sodanrc@yahoo.com.br blk->data = &dataBlks[blkSize*blk_index]; 9412752Sodanrc@yahoo.com.br 9513219Sodanrc@yahoo.com.br // Associate sector block to this block 9613219Sodanrc@yahoo.com.br blk->setSectorBlock(sec_blk); 9713218Sodanrc@yahoo.com.br 9813219Sodanrc@yahoo.com.br // Associate the sector replacement data to this block 9913219Sodanrc@yahoo.com.br blk->replacementData = sec_blk->replacementData; 10012752Sodanrc@yahoo.com.br 10113219Sodanrc@yahoo.com.br // Set its index and sector offset 10213219Sodanrc@yahoo.com.br blk->setSectorOffset(k); 10312752Sodanrc@yahoo.com.br 10413219Sodanrc@yahoo.com.br // Update block index 10513219Sodanrc@yahoo.com.br ++blk_index; 10612752Sodanrc@yahoo.com.br } 10714117Sodanrc@yahoo.com.br 10814117Sodanrc@yahoo.com.br // Link block to indexing policy 10914117Sodanrc@yahoo.com.br indexingPolicy->setEntry(sec_blk, sec_blk_index); 11012752Sodanrc@yahoo.com.br } 11112752Sodanrc@yahoo.com.br} 11212752Sodanrc@yahoo.com.br 11312752Sodanrc@yahoo.com.brvoid 11412752Sodanrc@yahoo.com.brSectorTags::invalidate(CacheBlk *blk) 11512752Sodanrc@yahoo.com.br{ 11612752Sodanrc@yahoo.com.br BaseTags::invalidate(blk); 11712752Sodanrc@yahoo.com.br 11812752Sodanrc@yahoo.com.br // Get block's sector 11912752Sodanrc@yahoo.com.br SectorSubBlk* sub_blk = static_cast<SectorSubBlk*>(blk); 12012752Sodanrc@yahoo.com.br const SectorBlk* sector_blk = sub_blk->getSectorBlock(); 12112752Sodanrc@yahoo.com.br 12212752Sodanrc@yahoo.com.br // When a block in a sector is invalidated, it does not make the tag 12312752Sodanrc@yahoo.com.br // invalid automatically, as there might be other blocks in the sector 12412752Sodanrc@yahoo.com.br // using it. The tag is invalidated only when there is a single block 12512752Sodanrc@yahoo.com.br // in the sector. 12612752Sodanrc@yahoo.com.br if (!sector_blk->isValid()) { 12712752Sodanrc@yahoo.com.br // Decrease the number of tags in use 12812752Sodanrc@yahoo.com.br tagsInUse--; 12912752Sodanrc@yahoo.com.br 13012752Sodanrc@yahoo.com.br // Invalidate replacement data, as we're invalidating the sector 13112752Sodanrc@yahoo.com.br replacementPolicy->invalidate(sector_blk->replacementData); 13212752Sodanrc@yahoo.com.br } 13312752Sodanrc@yahoo.com.br} 13412752Sodanrc@yahoo.com.br 13512752Sodanrc@yahoo.com.brCacheBlk* 13612752Sodanrc@yahoo.com.brSectorTags::accessBlock(Addr addr, bool is_secure, Cycles &lat) 13712752Sodanrc@yahoo.com.br{ 13812752Sodanrc@yahoo.com.br CacheBlk *blk = findBlock(addr, is_secure); 13912752Sodanrc@yahoo.com.br 14012752Sodanrc@yahoo.com.br // Access all tags in parallel, hence one in each way. The data side 14112752Sodanrc@yahoo.com.br // either accesses all blocks in parallel, or one block sequentially on 14212752Sodanrc@yahoo.com.br // a hit. Sequential access with a miss doesn't access data. 14312752Sodanrc@yahoo.com.br tagAccesses += allocAssoc; 14412752Sodanrc@yahoo.com.br if (sequentialAccess) { 14512752Sodanrc@yahoo.com.br if (blk != nullptr) { 14612752Sodanrc@yahoo.com.br dataAccesses += 1; 14712752Sodanrc@yahoo.com.br } 14812752Sodanrc@yahoo.com.br } else { 14912752Sodanrc@yahoo.com.br dataAccesses += allocAssoc*numBlocksPerSector; 15012752Sodanrc@yahoo.com.br } 15112752Sodanrc@yahoo.com.br 15213418Sodanrc@yahoo.com.br // If a cache hit 15312752Sodanrc@yahoo.com.br if (blk != nullptr) { 15412752Sodanrc@yahoo.com.br // Update number of references to accessed block 15512752Sodanrc@yahoo.com.br blk->refCount++; 15612752Sodanrc@yahoo.com.br 15712752Sodanrc@yahoo.com.br // Get block's sector 15812752Sodanrc@yahoo.com.br SectorSubBlk* sub_blk = static_cast<SectorSubBlk*>(blk); 15912752Sodanrc@yahoo.com.br const SectorBlk* sector_blk = sub_blk->getSectorBlock(); 16012752Sodanrc@yahoo.com.br 16112752Sodanrc@yahoo.com.br // Update replacement data of accessed block, which is shared with 16212752Sodanrc@yahoo.com.br // the whole sector it belongs to 16312752Sodanrc@yahoo.com.br replacementPolicy->touch(sector_blk->replacementData); 16412752Sodanrc@yahoo.com.br } 16512752Sodanrc@yahoo.com.br 16613418Sodanrc@yahoo.com.br // The tag lookup latency is the same for a hit or a miss 16713418Sodanrc@yahoo.com.br lat = lookupLatency; 16813418Sodanrc@yahoo.com.br 16912752Sodanrc@yahoo.com.br return blk; 17012752Sodanrc@yahoo.com.br} 17112752Sodanrc@yahoo.com.br 17212752Sodanrc@yahoo.com.brvoid 17313752Sodanrc@yahoo.com.brSectorTags::insertBlock(const PacketPtr pkt, CacheBlk *blk) 17412752Sodanrc@yahoo.com.br{ 17512752Sodanrc@yahoo.com.br // Get block's sector 17612752Sodanrc@yahoo.com.br SectorSubBlk* sub_blk = static_cast<SectorSubBlk*>(blk); 17712752Sodanrc@yahoo.com.br const SectorBlk* sector_blk = sub_blk->getSectorBlock(); 17812752Sodanrc@yahoo.com.br 17912752Sodanrc@yahoo.com.br // When a block is inserted, the tag is only a newly used tag if the 18012752Sodanrc@yahoo.com.br // sector was not previously present in the cache. 18112752Sodanrc@yahoo.com.br if (sector_blk->isValid()) { 18212752Sodanrc@yahoo.com.br // An existing entry's replacement data is just updated 18312752Sodanrc@yahoo.com.br replacementPolicy->touch(sector_blk->replacementData); 18412752Sodanrc@yahoo.com.br } else { 18512752Sodanrc@yahoo.com.br // Increment tag counter 18612752Sodanrc@yahoo.com.br tagsInUse++; 18712752Sodanrc@yahoo.com.br 18812752Sodanrc@yahoo.com.br // A new entry resets the replacement data 18912752Sodanrc@yahoo.com.br replacementPolicy->reset(sector_blk->replacementData); 19012752Sodanrc@yahoo.com.br } 19113445Sodanrc@yahoo.com.br 19213445Sodanrc@yahoo.com.br // Do common block insertion functionality 19313752Sodanrc@yahoo.com.br BaseTags::insertBlock(pkt, blk); 19412752Sodanrc@yahoo.com.br} 19512752Sodanrc@yahoo.com.br 19612752Sodanrc@yahoo.com.brCacheBlk* 19712752Sodanrc@yahoo.com.brSectorTags::findBlock(Addr addr, bool is_secure) const 19812752Sodanrc@yahoo.com.br{ 19912752Sodanrc@yahoo.com.br // Extract sector tag 20012752Sodanrc@yahoo.com.br const Addr tag = extractTag(addr); 20112752Sodanrc@yahoo.com.br 20212752Sodanrc@yahoo.com.br // The address can only be mapped to a specific location of a sector 20312752Sodanrc@yahoo.com.br // due to sectors being composed of contiguous-address entries 20412752Sodanrc@yahoo.com.br const Addr offset = extractSectorOffset(addr); 20512752Sodanrc@yahoo.com.br 20613219Sodanrc@yahoo.com.br // Find all possible sector entries that may contain the given address 20713219Sodanrc@yahoo.com.br const std::vector<ReplaceableEntry*> entries = 20813219Sodanrc@yahoo.com.br indexingPolicy->getPossibleEntries(addr); 20912752Sodanrc@yahoo.com.br 21012752Sodanrc@yahoo.com.br // Search for block 21113219Sodanrc@yahoo.com.br for (const auto& sector : entries) { 21213217Sodanrc@yahoo.com.br auto blk = static_cast<SectorBlk*>(sector)->blks[offset]; 21312752Sodanrc@yahoo.com.br if (blk->getTag() == tag && blk->isValid() && 21412752Sodanrc@yahoo.com.br blk->isSecure() == is_secure) { 21512752Sodanrc@yahoo.com.br return blk; 21612752Sodanrc@yahoo.com.br } 21712752Sodanrc@yahoo.com.br } 21812752Sodanrc@yahoo.com.br 21912752Sodanrc@yahoo.com.br // Did not find block 22012752Sodanrc@yahoo.com.br return nullptr; 22112752Sodanrc@yahoo.com.br} 22212752Sodanrc@yahoo.com.br 22312752Sodanrc@yahoo.com.brCacheBlk* 22413941Sodanrc@yahoo.com.brSectorTags::findVictim(Addr addr, const bool is_secure, const std::size_t size, 22512752Sodanrc@yahoo.com.br std::vector<CacheBlk*>& evict_blks) const 22612752Sodanrc@yahoo.com.br{ 22713219Sodanrc@yahoo.com.br // Get possible entries to be victimized 22813219Sodanrc@yahoo.com.br const std::vector<ReplaceableEntry*> sector_entries = 22913219Sodanrc@yahoo.com.br indexingPolicy->getPossibleEntries(addr); 23012752Sodanrc@yahoo.com.br 23112752Sodanrc@yahoo.com.br // Check if the sector this address belongs to has been allocated 23212752Sodanrc@yahoo.com.br Addr tag = extractTag(addr); 23312752Sodanrc@yahoo.com.br SectorBlk* victim_sector = nullptr; 23413219Sodanrc@yahoo.com.br for (const auto& sector : sector_entries) { 23513217Sodanrc@yahoo.com.br SectorBlk* sector_blk = static_cast<SectorBlk*>(sector); 23613217Sodanrc@yahoo.com.br if ((tag == sector_blk->getTag()) && sector_blk->isValid() && 23713217Sodanrc@yahoo.com.br (is_secure == sector_blk->isSecure())){ 23813217Sodanrc@yahoo.com.br victim_sector = sector_blk; 23912752Sodanrc@yahoo.com.br break; 24012752Sodanrc@yahoo.com.br } 24112752Sodanrc@yahoo.com.br } 24212752Sodanrc@yahoo.com.br 24312752Sodanrc@yahoo.com.br // If the sector is not present 24412752Sodanrc@yahoo.com.br if (victim_sector == nullptr){ 24512752Sodanrc@yahoo.com.br // Choose replacement victim from replacement candidates 24612752Sodanrc@yahoo.com.br victim_sector = static_cast<SectorBlk*>(replacementPolicy->getVictim( 24713219Sodanrc@yahoo.com.br sector_entries)); 24812752Sodanrc@yahoo.com.br } 24912752Sodanrc@yahoo.com.br 25013219Sodanrc@yahoo.com.br // Get the entry of the victim block within the sector 25112756Snikos.nikoleris@arm.com SectorSubBlk* victim = victim_sector->blks[extractSectorOffset(addr)]; 25212752Sodanrc@yahoo.com.br 25312752Sodanrc@yahoo.com.br // Get evicted blocks. Blocks are only evicted if the sectors mismatch and 25412752Sodanrc@yahoo.com.br // the currently existing sector is valid. 25512752Sodanrc@yahoo.com.br if ((tag == victim_sector->getTag()) && 25612752Sodanrc@yahoo.com.br (is_secure == victim_sector->isSecure())){ 25712752Sodanrc@yahoo.com.br // It would be a hit if victim was valid, and upgrades do not call 25812752Sodanrc@yahoo.com.br // findVictim, so it cannot happen 25912752Sodanrc@yahoo.com.br assert(!victim->isValid()); 26012752Sodanrc@yahoo.com.br } else { 26112752Sodanrc@yahoo.com.br // The whole sector must be evicted to make room for the new sector 26212752Sodanrc@yahoo.com.br for (const auto& blk : victim_sector->blks){ 26312752Sodanrc@yahoo.com.br evict_blks.push_back(blk); 26412752Sodanrc@yahoo.com.br } 26512752Sodanrc@yahoo.com.br } 26612752Sodanrc@yahoo.com.br 26712752Sodanrc@yahoo.com.br return victim; 26812752Sodanrc@yahoo.com.br} 26912752Sodanrc@yahoo.com.br 27012752Sodanrc@yahoo.com.brint 27112752Sodanrc@yahoo.com.brSectorTags::extractSectorOffset(Addr addr) const 27212752Sodanrc@yahoo.com.br{ 27312752Sodanrc@yahoo.com.br return (addr >> sectorShift) & sectorMask; 27412752Sodanrc@yahoo.com.br} 27512752Sodanrc@yahoo.com.br 27612752Sodanrc@yahoo.com.brAddr 27712752Sodanrc@yahoo.com.brSectorTags::regenerateBlkAddr(const CacheBlk* blk) const 27812752Sodanrc@yahoo.com.br{ 27912752Sodanrc@yahoo.com.br const SectorSubBlk* blk_cast = static_cast<const SectorSubBlk*>(blk); 28013219Sodanrc@yahoo.com.br const SectorBlk* sec_blk = blk_cast->getSectorBlock(); 28113219Sodanrc@yahoo.com.br const Addr sec_addr = indexingPolicy->regenerateAddr(blk->tag, sec_blk); 28213219Sodanrc@yahoo.com.br return sec_addr | ((Addr)blk_cast->getSectorOffset() << sectorShift); 28312752Sodanrc@yahoo.com.br} 28412752Sodanrc@yahoo.com.br 28512752Sodanrc@yahoo.com.brvoid 28612752Sodanrc@yahoo.com.brSectorTags::forEachBlk(std::function<void(CacheBlk &)> visitor) 28712752Sodanrc@yahoo.com.br{ 28812752Sodanrc@yahoo.com.br for (SectorSubBlk& blk : blks) { 28912752Sodanrc@yahoo.com.br visitor(blk); 29012752Sodanrc@yahoo.com.br } 29112752Sodanrc@yahoo.com.br} 29212752Sodanrc@yahoo.com.br 29312752Sodanrc@yahoo.com.brbool 29412752Sodanrc@yahoo.com.brSectorTags::anyBlk(std::function<bool(CacheBlk &)> visitor) 29512752Sodanrc@yahoo.com.br{ 29612752Sodanrc@yahoo.com.br for (SectorSubBlk& blk : blks) { 29712752Sodanrc@yahoo.com.br if (visitor(blk)) { 29812752Sodanrc@yahoo.com.br return true; 29912752Sodanrc@yahoo.com.br } 30012752Sodanrc@yahoo.com.br } 30112752Sodanrc@yahoo.com.br return false; 30212752Sodanrc@yahoo.com.br} 30312752Sodanrc@yahoo.com.br 30412752Sodanrc@yahoo.com.brSectorTags * 30512752Sodanrc@yahoo.com.brSectorTagsParams::create() 30612752Sodanrc@yahoo.com.br{ 30713219Sodanrc@yahoo.com.br // There must be a indexing policy 30813219Sodanrc@yahoo.com.br fatal_if(!indexing_policy, "An indexing policy is required"); 30913219Sodanrc@yahoo.com.br 31012752Sodanrc@yahoo.com.br return new SectorTags(this); 31112752Sodanrc@yahoo.com.br} 312