sector_tags.cc revision 13445
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), 5513219Sodanrc@yahoo.com.br numSectors(numBlocks / p->num_blocks_per_sector), blks(numBlocks), 5613219Sodanrc@yahoo.com.br secBlks(numSectors), sectorShift(floorLog2(blkSize)), 5713219Sodanrc@yahoo.com.br sectorMask(numBlocksPerSector - 1) 5812752Sodanrc@yahoo.com.br{ 5912752Sodanrc@yahoo.com.br // Check parameters 6012752Sodanrc@yahoo.com.br fatal_if(blkSize < 4 || !isPowerOf2(blkSize), 6112752Sodanrc@yahoo.com.br "Block size must be at least 4 and a power of 2"); 6212752Sodanrc@yahoo.com.br fatal_if(!isPowerOf2(numBlocksPerSector), 6312752Sodanrc@yahoo.com.br "# of blocks per sector must be non-zero and a power of 2"); 6413216Sodanrc@yahoo.com.br} 6513216Sodanrc@yahoo.com.br 6613216Sodanrc@yahoo.com.brvoid 6713419Sodanrc@yahoo.com.brSectorTags::tagsInit() 6813216Sodanrc@yahoo.com.br{ 6913219Sodanrc@yahoo.com.br // Initialize all blocks 7012752Sodanrc@yahoo.com.br unsigned blk_index = 0; // index into blks array 7113219Sodanrc@yahoo.com.br for (unsigned sec_blk_index = 0; sec_blk_index < numSectors; 7213219Sodanrc@yahoo.com.br sec_blk_index++) 7313219Sodanrc@yahoo.com.br { 7413219Sodanrc@yahoo.com.br // Locate next cache sector 7513219Sodanrc@yahoo.com.br SectorBlk* sec_blk = &secBlks[sec_blk_index]; 7612752Sodanrc@yahoo.com.br 7713219Sodanrc@yahoo.com.br // Link block to indexing policy 7813219Sodanrc@yahoo.com.br indexingPolicy->setEntry(sec_blk, sec_blk_index); 7913219Sodanrc@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 } 10712752Sodanrc@yahoo.com.br } 10812752Sodanrc@yahoo.com.br} 10912752Sodanrc@yahoo.com.br 11012752Sodanrc@yahoo.com.brvoid 11112752Sodanrc@yahoo.com.brSectorTags::invalidate(CacheBlk *blk) 11212752Sodanrc@yahoo.com.br{ 11312752Sodanrc@yahoo.com.br BaseTags::invalidate(blk); 11412752Sodanrc@yahoo.com.br 11512752Sodanrc@yahoo.com.br // Get block's sector 11612752Sodanrc@yahoo.com.br SectorSubBlk* sub_blk = static_cast<SectorSubBlk*>(blk); 11712752Sodanrc@yahoo.com.br const SectorBlk* sector_blk = sub_blk->getSectorBlock(); 11812752Sodanrc@yahoo.com.br 11912752Sodanrc@yahoo.com.br // When a block in a sector is invalidated, it does not make the tag 12012752Sodanrc@yahoo.com.br // invalid automatically, as there might be other blocks in the sector 12112752Sodanrc@yahoo.com.br // using it. The tag is invalidated only when there is a single block 12212752Sodanrc@yahoo.com.br // in the sector. 12312752Sodanrc@yahoo.com.br if (!sector_blk->isValid()) { 12412752Sodanrc@yahoo.com.br // Decrease the number of tags in use 12512752Sodanrc@yahoo.com.br tagsInUse--; 12612752Sodanrc@yahoo.com.br 12712752Sodanrc@yahoo.com.br // Invalidate replacement data, as we're invalidating the sector 12812752Sodanrc@yahoo.com.br replacementPolicy->invalidate(sector_blk->replacementData); 12912752Sodanrc@yahoo.com.br } 13012752Sodanrc@yahoo.com.br} 13112752Sodanrc@yahoo.com.br 13212752Sodanrc@yahoo.com.brCacheBlk* 13312752Sodanrc@yahoo.com.brSectorTags::accessBlock(Addr addr, bool is_secure, Cycles &lat) 13412752Sodanrc@yahoo.com.br{ 13512752Sodanrc@yahoo.com.br CacheBlk *blk = findBlock(addr, is_secure); 13612752Sodanrc@yahoo.com.br 13712752Sodanrc@yahoo.com.br // Access all tags in parallel, hence one in each way. The data side 13812752Sodanrc@yahoo.com.br // either accesses all blocks in parallel, or one block sequentially on 13912752Sodanrc@yahoo.com.br // a hit. Sequential access with a miss doesn't access data. 14012752Sodanrc@yahoo.com.br tagAccesses += allocAssoc; 14112752Sodanrc@yahoo.com.br if (sequentialAccess) { 14212752Sodanrc@yahoo.com.br if (blk != nullptr) { 14312752Sodanrc@yahoo.com.br dataAccesses += 1; 14412752Sodanrc@yahoo.com.br } 14512752Sodanrc@yahoo.com.br } else { 14612752Sodanrc@yahoo.com.br dataAccesses += allocAssoc*numBlocksPerSector; 14712752Sodanrc@yahoo.com.br } 14812752Sodanrc@yahoo.com.br 14913418Sodanrc@yahoo.com.br // If a cache hit 15012752Sodanrc@yahoo.com.br if (blk != nullptr) { 15112752Sodanrc@yahoo.com.br // Update number of references to accessed block 15212752Sodanrc@yahoo.com.br blk->refCount++; 15312752Sodanrc@yahoo.com.br 15412752Sodanrc@yahoo.com.br // Get block's sector 15512752Sodanrc@yahoo.com.br SectorSubBlk* sub_blk = static_cast<SectorSubBlk*>(blk); 15612752Sodanrc@yahoo.com.br const SectorBlk* sector_blk = sub_blk->getSectorBlock(); 15712752Sodanrc@yahoo.com.br 15812752Sodanrc@yahoo.com.br // Update replacement data of accessed block, which is shared with 15912752Sodanrc@yahoo.com.br // the whole sector it belongs to 16012752Sodanrc@yahoo.com.br replacementPolicy->touch(sector_blk->replacementData); 16112752Sodanrc@yahoo.com.br } 16212752Sodanrc@yahoo.com.br 16313418Sodanrc@yahoo.com.br // The tag lookup latency is the same for a hit or a miss 16413418Sodanrc@yahoo.com.br lat = lookupLatency; 16513418Sodanrc@yahoo.com.br 16612752Sodanrc@yahoo.com.br return blk; 16712752Sodanrc@yahoo.com.br} 16812752Sodanrc@yahoo.com.br 16912752Sodanrc@yahoo.com.brvoid 17013215Sodanrc@yahoo.com.brSectorTags::insertBlock(const Addr addr, const bool is_secure, 17113215Sodanrc@yahoo.com.br const int src_master_ID, const uint32_t task_ID, 17213215Sodanrc@yahoo.com.br CacheBlk *blk) 17312752Sodanrc@yahoo.com.br{ 17412752Sodanrc@yahoo.com.br // Get block's sector 17512752Sodanrc@yahoo.com.br SectorSubBlk* sub_blk = static_cast<SectorSubBlk*>(blk); 17612752Sodanrc@yahoo.com.br const SectorBlk* sector_blk = sub_blk->getSectorBlock(); 17712752Sodanrc@yahoo.com.br 17812752Sodanrc@yahoo.com.br // When a block is inserted, the tag is only a newly used tag if the 17912752Sodanrc@yahoo.com.br // sector was not previously present in the cache. 18012752Sodanrc@yahoo.com.br if (sector_blk->isValid()) { 18112752Sodanrc@yahoo.com.br // An existing entry's replacement data is just updated 18212752Sodanrc@yahoo.com.br replacementPolicy->touch(sector_blk->replacementData); 18312752Sodanrc@yahoo.com.br } else { 18412752Sodanrc@yahoo.com.br // Increment tag counter 18512752Sodanrc@yahoo.com.br tagsInUse++; 18612752Sodanrc@yahoo.com.br 18712752Sodanrc@yahoo.com.br // A new entry resets the replacement data 18812752Sodanrc@yahoo.com.br replacementPolicy->reset(sector_blk->replacementData); 18912752Sodanrc@yahoo.com.br } 19013445Sodanrc@yahoo.com.br 19113445Sodanrc@yahoo.com.br // Do common block insertion functionality 19213445Sodanrc@yahoo.com.br BaseTags::insertBlock(addr, is_secure, src_master_ID, task_ID, blk); 19312752Sodanrc@yahoo.com.br} 19412752Sodanrc@yahoo.com.br 19512752Sodanrc@yahoo.com.brCacheBlk* 19612752Sodanrc@yahoo.com.brSectorTags::findBlock(Addr addr, bool is_secure) const 19712752Sodanrc@yahoo.com.br{ 19812752Sodanrc@yahoo.com.br // Extract sector tag 19912752Sodanrc@yahoo.com.br const Addr tag = extractTag(addr); 20012752Sodanrc@yahoo.com.br 20112752Sodanrc@yahoo.com.br // The address can only be mapped to a specific location of a sector 20212752Sodanrc@yahoo.com.br // due to sectors being composed of contiguous-address entries 20312752Sodanrc@yahoo.com.br const Addr offset = extractSectorOffset(addr); 20412752Sodanrc@yahoo.com.br 20513219Sodanrc@yahoo.com.br // Find all possible sector entries that may contain the given address 20613219Sodanrc@yahoo.com.br const std::vector<ReplaceableEntry*> entries = 20713219Sodanrc@yahoo.com.br indexingPolicy->getPossibleEntries(addr); 20812752Sodanrc@yahoo.com.br 20912752Sodanrc@yahoo.com.br // Search for block 21013219Sodanrc@yahoo.com.br for (const auto& sector : entries) { 21113217Sodanrc@yahoo.com.br auto blk = static_cast<SectorBlk*>(sector)->blks[offset]; 21212752Sodanrc@yahoo.com.br if (blk->getTag() == tag && blk->isValid() && 21312752Sodanrc@yahoo.com.br blk->isSecure() == is_secure) { 21412752Sodanrc@yahoo.com.br return blk; 21512752Sodanrc@yahoo.com.br } 21612752Sodanrc@yahoo.com.br } 21712752Sodanrc@yahoo.com.br 21812752Sodanrc@yahoo.com.br // Did not find block 21912752Sodanrc@yahoo.com.br return nullptr; 22012752Sodanrc@yahoo.com.br} 22112752Sodanrc@yahoo.com.br 22212752Sodanrc@yahoo.com.brCacheBlk* 22312752Sodanrc@yahoo.com.brSectorTags::findVictim(Addr addr, const bool is_secure, 22412752Sodanrc@yahoo.com.br std::vector<CacheBlk*>& evict_blks) const 22512752Sodanrc@yahoo.com.br{ 22613219Sodanrc@yahoo.com.br // Get possible entries to be victimized 22713219Sodanrc@yahoo.com.br const std::vector<ReplaceableEntry*> sector_entries = 22813219Sodanrc@yahoo.com.br indexingPolicy->getPossibleEntries(addr); 22912752Sodanrc@yahoo.com.br 23012752Sodanrc@yahoo.com.br // Check if the sector this address belongs to has been allocated 23112752Sodanrc@yahoo.com.br Addr tag = extractTag(addr); 23212752Sodanrc@yahoo.com.br SectorBlk* victim_sector = nullptr; 23313219Sodanrc@yahoo.com.br for (const auto& sector : sector_entries) { 23413217Sodanrc@yahoo.com.br SectorBlk* sector_blk = static_cast<SectorBlk*>(sector); 23513217Sodanrc@yahoo.com.br if ((tag == sector_blk->getTag()) && sector_blk->isValid() && 23613217Sodanrc@yahoo.com.br (is_secure == sector_blk->isSecure())){ 23713217Sodanrc@yahoo.com.br victim_sector = sector_blk; 23812752Sodanrc@yahoo.com.br break; 23912752Sodanrc@yahoo.com.br } 24012752Sodanrc@yahoo.com.br } 24112752Sodanrc@yahoo.com.br 24212752Sodanrc@yahoo.com.br // If the sector is not present 24312752Sodanrc@yahoo.com.br if (victim_sector == nullptr){ 24412752Sodanrc@yahoo.com.br // Choose replacement victim from replacement candidates 24512752Sodanrc@yahoo.com.br victim_sector = static_cast<SectorBlk*>(replacementPolicy->getVictim( 24613219Sodanrc@yahoo.com.br sector_entries)); 24712752Sodanrc@yahoo.com.br } 24812752Sodanrc@yahoo.com.br 24913219Sodanrc@yahoo.com.br // Get the entry of the victim block within the sector 25012756Snikos.nikoleris@arm.com SectorSubBlk* victim = victim_sector->blks[extractSectorOffset(addr)]; 25112752Sodanrc@yahoo.com.br 25212752Sodanrc@yahoo.com.br // Get evicted blocks. Blocks are only evicted if the sectors mismatch and 25312752Sodanrc@yahoo.com.br // the currently existing sector is valid. 25412752Sodanrc@yahoo.com.br if ((tag == victim_sector->getTag()) && 25512752Sodanrc@yahoo.com.br (is_secure == victim_sector->isSecure())){ 25612752Sodanrc@yahoo.com.br // It would be a hit if victim was valid, and upgrades do not call 25712752Sodanrc@yahoo.com.br // findVictim, so it cannot happen 25812752Sodanrc@yahoo.com.br assert(!victim->isValid()); 25912752Sodanrc@yahoo.com.br } else { 26012752Sodanrc@yahoo.com.br // The whole sector must be evicted to make room for the new sector 26112752Sodanrc@yahoo.com.br for (const auto& blk : victim_sector->blks){ 26212752Sodanrc@yahoo.com.br evict_blks.push_back(blk); 26312752Sodanrc@yahoo.com.br } 26412752Sodanrc@yahoo.com.br } 26512752Sodanrc@yahoo.com.br 26612752Sodanrc@yahoo.com.br return victim; 26712752Sodanrc@yahoo.com.br} 26812752Sodanrc@yahoo.com.br 26912752Sodanrc@yahoo.com.brint 27012752Sodanrc@yahoo.com.brSectorTags::extractSectorOffset(Addr addr) const 27112752Sodanrc@yahoo.com.br{ 27212752Sodanrc@yahoo.com.br return (addr >> sectorShift) & sectorMask; 27312752Sodanrc@yahoo.com.br} 27412752Sodanrc@yahoo.com.br 27512752Sodanrc@yahoo.com.brAddr 27612752Sodanrc@yahoo.com.brSectorTags::regenerateBlkAddr(const CacheBlk* blk) const 27712752Sodanrc@yahoo.com.br{ 27812752Sodanrc@yahoo.com.br const SectorSubBlk* blk_cast = static_cast<const SectorSubBlk*>(blk); 27913219Sodanrc@yahoo.com.br const SectorBlk* sec_blk = blk_cast->getSectorBlock(); 28013219Sodanrc@yahoo.com.br const Addr sec_addr = indexingPolicy->regenerateAddr(blk->tag, sec_blk); 28113219Sodanrc@yahoo.com.br return sec_addr | ((Addr)blk_cast->getSectorOffset() << sectorShift); 28212752Sodanrc@yahoo.com.br} 28312752Sodanrc@yahoo.com.br 28412752Sodanrc@yahoo.com.brvoid 28512752Sodanrc@yahoo.com.brSectorTags::forEachBlk(std::function<void(CacheBlk &)> visitor) 28612752Sodanrc@yahoo.com.br{ 28712752Sodanrc@yahoo.com.br for (SectorSubBlk& blk : blks) { 28812752Sodanrc@yahoo.com.br visitor(blk); 28912752Sodanrc@yahoo.com.br } 29012752Sodanrc@yahoo.com.br} 29112752Sodanrc@yahoo.com.br 29212752Sodanrc@yahoo.com.brbool 29312752Sodanrc@yahoo.com.brSectorTags::anyBlk(std::function<bool(CacheBlk &)> visitor) 29412752Sodanrc@yahoo.com.br{ 29512752Sodanrc@yahoo.com.br for (SectorSubBlk& blk : blks) { 29612752Sodanrc@yahoo.com.br if (visitor(blk)) { 29712752Sodanrc@yahoo.com.br return true; 29812752Sodanrc@yahoo.com.br } 29912752Sodanrc@yahoo.com.br } 30012752Sodanrc@yahoo.com.br return false; 30112752Sodanrc@yahoo.com.br} 30212752Sodanrc@yahoo.com.br 30312752Sodanrc@yahoo.com.brSectorTags * 30412752Sodanrc@yahoo.com.brSectorTagsParams::create() 30512752Sodanrc@yahoo.com.br{ 30613219Sodanrc@yahoo.com.br // There must be a indexing policy 30713219Sodanrc@yahoo.com.br fatal_if(!indexing_policy, "An indexing policy is required"); 30813219Sodanrc@yahoo.com.br 30912752Sodanrc@yahoo.com.br return new SectorTags(this); 31012752Sodanrc@yahoo.com.br} 311