sector_tags.cc (13219:454ecc63338d) | sector_tags.cc (13222:0dbcc7d7d66f) |
---|---|
1/* 2 * Copyright (c) 2018 Inria 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions are 7 * met: redistributions of source code must retain the above copyright 8 * notice, this list of conditions and the following disclaimer; 9 * redistributions in binary form must reproduce the above copyright 10 * notice, this list of conditions and the following disclaimer in the 11 * documentation and/or other materials provided with the distribution; 12 * neither the name of the copyright holders nor the names of its 13 * contributors may be used to endorse or promote products derived from 14 * this software without specific prior written permission. 15 * 16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 * 28 * Authors: Daniel Carvalho 29 */ 30 31/** 32 * @file 33 * Definitions of a sector tag store. 34 */ 35 36#include "mem/cache/tags/sector_tags.hh" 37 38#include <cassert> 39#include <memory> 40#include <string> 41 42#include "base/intmath.hh" 43#include "base/logging.hh" 44#include "base/types.hh" | 1/* 2 * Copyright (c) 2018 Inria 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions are 7 * met: redistributions of source code must retain the above copyright 8 * notice, this list of conditions and the following disclaimer; 9 * redistributions in binary form must reproduce the above copyright 10 * notice, this list of conditions and the following disclaimer in the 11 * documentation and/or other materials provided with the distribution; 12 * neither the name of the copyright holders nor the names of its 13 * contributors may be used to endorse or promote products derived from 14 * this software without specific prior written permission. 15 * 16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 * 28 * Authors: Daniel Carvalho 29 */ 30 31/** 32 * @file 33 * Definitions of a sector tag store. 34 */ 35 36#include "mem/cache/tags/sector_tags.hh" 37 38#include <cassert> 39#include <memory> 40#include <string> 41 42#include "base/intmath.hh" 43#include "base/logging.hh" 44#include "base/types.hh" |
45#include "debug/CacheRepl.hh" | |
46#include "mem/cache/base.hh" 47#include "mem/cache/replacement_policies/base.hh" 48#include "mem/cache/tags/indexing_policies/base.hh" 49 50SectorTags::SectorTags(const SectorTagsParams *p) 51 : BaseTags(p), allocAssoc(p->assoc), 52 sequentialAccess(p->sequential_access), 53 replacementPolicy(p->replacement_policy), 54 numBlocksPerSector(p->num_blocks_per_sector), 55 numSectors(numBlocks / p->num_blocks_per_sector), blks(numBlocks), 56 secBlks(numSectors), sectorShift(floorLog2(blkSize)), 57 sectorMask(numBlocksPerSector - 1) 58{ 59 // Check parameters 60 fatal_if(blkSize < 4 || !isPowerOf2(blkSize), 61 "Block size must be at least 4 and a power of 2"); 62 fatal_if(!isPowerOf2(numBlocksPerSector), 63 "# of blocks per sector must be non-zero and a power of 2"); 64} 65 66void 67SectorTags::init(BaseCache* cache) 68{ 69 // Set parent cache 70 setCache(cache); 71 72 // Initialize all blocks 73 unsigned blk_index = 0; // index into blks array 74 for (unsigned sec_blk_index = 0; sec_blk_index < numSectors; 75 sec_blk_index++) 76 { 77 // Locate next cache sector 78 SectorBlk* sec_blk = &secBlks[sec_blk_index]; 79 80 // Link block to indexing policy 81 indexingPolicy->setEntry(sec_blk, sec_blk_index); 82 83 // Associate a replacement data entry to the sector 84 sec_blk->replacementData = replacementPolicy->instantiateEntry(); 85 86 // Initialize all blocks in this sector 87 sec_blk->blks.resize(numBlocksPerSector); 88 for (unsigned k = 0; k < numBlocksPerSector; ++k){ 89 // Select block within the set to be linked 90 SectorSubBlk*& blk = sec_blk->blks[k]; 91 92 // Locate next cache block 93 blk = &blks[blk_index]; 94 95 // Associate a data chunk to the block 96 blk->data = &dataBlks[blkSize*blk_index]; 97 98 // Associate sector block to this block 99 blk->setSectorBlock(sec_blk); 100 101 // Associate the sector replacement data to this block 102 blk->replacementData = sec_blk->replacementData; 103 104 // Set its index and sector offset 105 blk->setSectorOffset(k); 106 107 // Update block index 108 ++blk_index; 109 } 110 } 111} 112 113void 114SectorTags::invalidate(CacheBlk *blk) 115{ 116 BaseTags::invalidate(blk); 117 118 // Get block's sector 119 SectorSubBlk* sub_blk = static_cast<SectorSubBlk*>(blk); 120 const SectorBlk* sector_blk = sub_blk->getSectorBlock(); 121 122 // When a block in a sector is invalidated, it does not make the tag 123 // invalid automatically, as there might be other blocks in the sector 124 // using it. The tag is invalidated only when there is a single block 125 // in the sector. 126 if (!sector_blk->isValid()) { 127 // Decrease the number of tags in use 128 tagsInUse--; 129 130 // Invalidate replacement data, as we're invalidating the sector 131 replacementPolicy->invalidate(sector_blk->replacementData); 132 } 133} 134 135CacheBlk* 136SectorTags::accessBlock(Addr addr, bool is_secure, Cycles &lat) 137{ 138 CacheBlk *blk = findBlock(addr, is_secure); 139 140 // Access all tags in parallel, hence one in each way. The data side 141 // either accesses all blocks in parallel, or one block sequentially on 142 // a hit. Sequential access with a miss doesn't access data. 143 tagAccesses += allocAssoc; 144 if (sequentialAccess) { 145 if (blk != nullptr) { 146 dataAccesses += 1; 147 } 148 } else { 149 dataAccesses += allocAssoc*numBlocksPerSector; 150 } 151 152 if (blk != nullptr) { 153 // If a cache hit 154 lat = accessLatency; 155 // Check if the block to be accessed is available. If not, 156 // apply the accessLatency on top of block->whenReady. 157 if (blk->whenReady > curTick() && 158 cache->ticksToCycles(blk->whenReady - curTick()) > 159 accessLatency) { 160 lat = cache->ticksToCycles(blk->whenReady - curTick()) + 161 accessLatency; 162 } 163 164 // Update number of references to accessed block 165 blk->refCount++; 166 167 // Get block's sector 168 SectorSubBlk* sub_blk = static_cast<SectorSubBlk*>(blk); 169 const SectorBlk* sector_blk = sub_blk->getSectorBlock(); 170 171 // Update replacement data of accessed block, which is shared with 172 // the whole sector it belongs to 173 replacementPolicy->touch(sector_blk->replacementData); 174 } else { 175 // If a cache miss 176 lat = lookupLatency; 177 } 178 179 return blk; 180} 181 182void 183SectorTags::insertBlock(const Addr addr, const bool is_secure, 184 const int src_master_ID, const uint32_t task_ID, 185 CacheBlk *blk) 186{ 187 // Do common block insertion functionality 188 BaseTags::insertBlock(addr, is_secure, src_master_ID, task_ID, blk); 189 190 // Get block's sector 191 SectorSubBlk* sub_blk = static_cast<SectorSubBlk*>(blk); 192 const SectorBlk* sector_blk = sub_blk->getSectorBlock(); 193 194 // When a block is inserted, the tag is only a newly used tag if the 195 // sector was not previously present in the cache. 196 // This assumes BaseTags::insertBlock does not set the valid bit. 197 if (sector_blk->isValid()) { 198 // An existing entry's replacement data is just updated 199 replacementPolicy->touch(sector_blk->replacementData); 200 } else { 201 // Increment tag counter 202 tagsInUse++; 203 204 // A new entry resets the replacement data 205 replacementPolicy->reset(sector_blk->replacementData); 206 } 207} 208 209CacheBlk* 210SectorTags::findBlock(Addr addr, bool is_secure) const 211{ 212 // Extract sector tag 213 const Addr tag = extractTag(addr); 214 215 // The address can only be mapped to a specific location of a sector 216 // due to sectors being composed of contiguous-address entries 217 const Addr offset = extractSectorOffset(addr); 218 219 // Find all possible sector entries that may contain the given address 220 const std::vector<ReplaceableEntry*> entries = 221 indexingPolicy->getPossibleEntries(addr); 222 223 // Search for block 224 for (const auto& sector : entries) { 225 auto blk = static_cast<SectorBlk*>(sector)->blks[offset]; 226 if (blk->getTag() == tag && blk->isValid() && 227 blk->isSecure() == is_secure) { 228 return blk; 229 } 230 } 231 232 // Did not find block 233 return nullptr; 234} 235 236CacheBlk* 237SectorTags::findVictim(Addr addr, const bool is_secure, 238 std::vector<CacheBlk*>& evict_blks) const 239{ 240 // Get possible entries to be victimized 241 const std::vector<ReplaceableEntry*> sector_entries = 242 indexingPolicy->getPossibleEntries(addr); 243 244 // Check if the sector this address belongs to has been allocated 245 Addr tag = extractTag(addr); 246 SectorBlk* victim_sector = nullptr; 247 for (const auto& sector : sector_entries) { 248 SectorBlk* sector_blk = static_cast<SectorBlk*>(sector); 249 if ((tag == sector_blk->getTag()) && sector_blk->isValid() && 250 (is_secure == sector_blk->isSecure())){ 251 victim_sector = sector_blk; 252 break; 253 } 254 } 255 256 // If the sector is not present 257 if (victim_sector == nullptr){ 258 // Choose replacement victim from replacement candidates 259 victim_sector = static_cast<SectorBlk*>(replacementPolicy->getVictim( 260 sector_entries)); 261 } 262 263 // Get the entry of the victim block within the sector 264 SectorSubBlk* victim = victim_sector->blks[extractSectorOffset(addr)]; 265 266 // Get evicted blocks. Blocks are only evicted if the sectors mismatch and 267 // the currently existing sector is valid. 268 if ((tag == victim_sector->getTag()) && 269 (is_secure == victim_sector->isSecure())){ 270 // It would be a hit if victim was valid, and upgrades do not call 271 // findVictim, so it cannot happen 272 assert(!victim->isValid()); 273 } else { 274 // The whole sector must be evicted to make room for the new sector 275 for (const auto& blk : victim_sector->blks){ 276 evict_blks.push_back(blk); 277 } 278 } 279 | 45#include "mem/cache/base.hh" 46#include "mem/cache/replacement_policies/base.hh" 47#include "mem/cache/tags/indexing_policies/base.hh" 48 49SectorTags::SectorTags(const SectorTagsParams *p) 50 : BaseTags(p), allocAssoc(p->assoc), 51 sequentialAccess(p->sequential_access), 52 replacementPolicy(p->replacement_policy), 53 numBlocksPerSector(p->num_blocks_per_sector), 54 numSectors(numBlocks / p->num_blocks_per_sector), blks(numBlocks), 55 secBlks(numSectors), sectorShift(floorLog2(blkSize)), 56 sectorMask(numBlocksPerSector - 1) 57{ 58 // Check parameters 59 fatal_if(blkSize < 4 || !isPowerOf2(blkSize), 60 "Block size must be at least 4 and a power of 2"); 61 fatal_if(!isPowerOf2(numBlocksPerSector), 62 "# of blocks per sector must be non-zero and a power of 2"); 63} 64 65void 66SectorTags::init(BaseCache* cache) 67{ 68 // Set parent cache 69 setCache(cache); 70 71 // Initialize all blocks 72 unsigned blk_index = 0; // index into blks array 73 for (unsigned sec_blk_index = 0; sec_blk_index < numSectors; 74 sec_blk_index++) 75 { 76 // Locate next cache sector 77 SectorBlk* sec_blk = &secBlks[sec_blk_index]; 78 79 // Link block to indexing policy 80 indexingPolicy->setEntry(sec_blk, sec_blk_index); 81 82 // Associate a replacement data entry to the sector 83 sec_blk->replacementData = replacementPolicy->instantiateEntry(); 84 85 // Initialize all blocks in this sector 86 sec_blk->blks.resize(numBlocksPerSector); 87 for (unsigned k = 0; k < numBlocksPerSector; ++k){ 88 // Select block within the set to be linked 89 SectorSubBlk*& blk = sec_blk->blks[k]; 90 91 // Locate next cache block 92 blk = &blks[blk_index]; 93 94 // Associate a data chunk to the block 95 blk->data = &dataBlks[blkSize*blk_index]; 96 97 // Associate sector block to this block 98 blk->setSectorBlock(sec_blk); 99 100 // Associate the sector replacement data to this block 101 blk->replacementData = sec_blk->replacementData; 102 103 // Set its index and sector offset 104 blk->setSectorOffset(k); 105 106 // Update block index 107 ++blk_index; 108 } 109 } 110} 111 112void 113SectorTags::invalidate(CacheBlk *blk) 114{ 115 BaseTags::invalidate(blk); 116 117 // Get block's sector 118 SectorSubBlk* sub_blk = static_cast<SectorSubBlk*>(blk); 119 const SectorBlk* sector_blk = sub_blk->getSectorBlock(); 120 121 // When a block in a sector is invalidated, it does not make the tag 122 // invalid automatically, as there might be other blocks in the sector 123 // using it. The tag is invalidated only when there is a single block 124 // in the sector. 125 if (!sector_blk->isValid()) { 126 // Decrease the number of tags in use 127 tagsInUse--; 128 129 // Invalidate replacement data, as we're invalidating the sector 130 replacementPolicy->invalidate(sector_blk->replacementData); 131 } 132} 133 134CacheBlk* 135SectorTags::accessBlock(Addr addr, bool is_secure, Cycles &lat) 136{ 137 CacheBlk *blk = findBlock(addr, is_secure); 138 139 // Access all tags in parallel, hence one in each way. The data side 140 // either accesses all blocks in parallel, or one block sequentially on 141 // a hit. Sequential access with a miss doesn't access data. 142 tagAccesses += allocAssoc; 143 if (sequentialAccess) { 144 if (blk != nullptr) { 145 dataAccesses += 1; 146 } 147 } else { 148 dataAccesses += allocAssoc*numBlocksPerSector; 149 } 150 151 if (blk != nullptr) { 152 // If a cache hit 153 lat = accessLatency; 154 // Check if the block to be accessed is available. If not, 155 // apply the accessLatency on top of block->whenReady. 156 if (blk->whenReady > curTick() && 157 cache->ticksToCycles(blk->whenReady - curTick()) > 158 accessLatency) { 159 lat = cache->ticksToCycles(blk->whenReady - curTick()) + 160 accessLatency; 161 } 162 163 // Update number of references to accessed block 164 blk->refCount++; 165 166 // Get block's sector 167 SectorSubBlk* sub_blk = static_cast<SectorSubBlk*>(blk); 168 const SectorBlk* sector_blk = sub_blk->getSectorBlock(); 169 170 // Update replacement data of accessed block, which is shared with 171 // the whole sector it belongs to 172 replacementPolicy->touch(sector_blk->replacementData); 173 } else { 174 // If a cache miss 175 lat = lookupLatency; 176 } 177 178 return blk; 179} 180 181void 182SectorTags::insertBlock(const Addr addr, const bool is_secure, 183 const int src_master_ID, const uint32_t task_ID, 184 CacheBlk *blk) 185{ 186 // Do common block insertion functionality 187 BaseTags::insertBlock(addr, is_secure, src_master_ID, task_ID, blk); 188 189 // Get block's sector 190 SectorSubBlk* sub_blk = static_cast<SectorSubBlk*>(blk); 191 const SectorBlk* sector_blk = sub_blk->getSectorBlock(); 192 193 // When a block is inserted, the tag is only a newly used tag if the 194 // sector was not previously present in the cache. 195 // This assumes BaseTags::insertBlock does not set the valid bit. 196 if (sector_blk->isValid()) { 197 // An existing entry's replacement data is just updated 198 replacementPolicy->touch(sector_blk->replacementData); 199 } else { 200 // Increment tag counter 201 tagsInUse++; 202 203 // A new entry resets the replacement data 204 replacementPolicy->reset(sector_blk->replacementData); 205 } 206} 207 208CacheBlk* 209SectorTags::findBlock(Addr addr, bool is_secure) const 210{ 211 // Extract sector tag 212 const Addr tag = extractTag(addr); 213 214 // The address can only be mapped to a specific location of a sector 215 // due to sectors being composed of contiguous-address entries 216 const Addr offset = extractSectorOffset(addr); 217 218 // Find all possible sector entries that may contain the given address 219 const std::vector<ReplaceableEntry*> entries = 220 indexingPolicy->getPossibleEntries(addr); 221 222 // Search for block 223 for (const auto& sector : entries) { 224 auto blk = static_cast<SectorBlk*>(sector)->blks[offset]; 225 if (blk->getTag() == tag && blk->isValid() && 226 blk->isSecure() == is_secure) { 227 return blk; 228 } 229 } 230 231 // Did not find block 232 return nullptr; 233} 234 235CacheBlk* 236SectorTags::findVictim(Addr addr, const bool is_secure, 237 std::vector<CacheBlk*>& evict_blks) const 238{ 239 // Get possible entries to be victimized 240 const std::vector<ReplaceableEntry*> sector_entries = 241 indexingPolicy->getPossibleEntries(addr); 242 243 // Check if the sector this address belongs to has been allocated 244 Addr tag = extractTag(addr); 245 SectorBlk* victim_sector = nullptr; 246 for (const auto& sector : sector_entries) { 247 SectorBlk* sector_blk = static_cast<SectorBlk*>(sector); 248 if ((tag == sector_blk->getTag()) && sector_blk->isValid() && 249 (is_secure == sector_blk->isSecure())){ 250 victim_sector = sector_blk; 251 break; 252 } 253 } 254 255 // If the sector is not present 256 if (victim_sector == nullptr){ 257 // Choose replacement victim from replacement candidates 258 victim_sector = static_cast<SectorBlk*>(replacementPolicy->getVictim( 259 sector_entries)); 260 } 261 262 // Get the entry of the victim block within the sector 263 SectorSubBlk* victim = victim_sector->blks[extractSectorOffset(addr)]; 264 265 // Get evicted blocks. Blocks are only evicted if the sectors mismatch and 266 // the currently existing sector is valid. 267 if ((tag == victim_sector->getTag()) && 268 (is_secure == victim_sector->isSecure())){ 269 // It would be a hit if victim was valid, and upgrades do not call 270 // findVictim, so it cannot happen 271 assert(!victim->isValid()); 272 } else { 273 // The whole sector must be evicted to make room for the new sector 274 for (const auto& blk : victim_sector->blks){ 275 evict_blks.push_back(blk); 276 } 277 } 278 |
280 DPRINTF(CacheRepl, "set %x, way %x, sector offset %x: selecting blk " \ 281 "for replacement\n", victim->getSet(), victim->getWay(), 282 victim->getSectorOffset()); 283 | |
284 return victim; 285} 286 287int 288SectorTags::extractSectorOffset(Addr addr) const 289{ 290 return (addr >> sectorShift) & sectorMask; 291} 292 293Addr 294SectorTags::regenerateBlkAddr(const CacheBlk* blk) const 295{ 296 const SectorSubBlk* blk_cast = static_cast<const SectorSubBlk*>(blk); 297 const SectorBlk* sec_blk = blk_cast->getSectorBlock(); 298 const Addr sec_addr = indexingPolicy->regenerateAddr(blk->tag, sec_blk); 299 return sec_addr | ((Addr)blk_cast->getSectorOffset() << sectorShift); 300} 301 302void 303SectorTags::forEachBlk(std::function<void(CacheBlk &)> visitor) 304{ 305 for (SectorSubBlk& blk : blks) { 306 visitor(blk); 307 } 308} 309 310bool 311SectorTags::anyBlk(std::function<bool(CacheBlk &)> visitor) 312{ 313 for (SectorSubBlk& blk : blks) { 314 if (visitor(blk)) { 315 return true; 316 } 317 } 318 return false; 319} 320 321SectorTags * 322SectorTagsParams::create() 323{ 324 // There must be a indexing policy 325 fatal_if(!indexing_policy, "An indexing policy is required"); 326 327 return new SectorTags(this); 328} | 279 return victim; 280} 281 282int 283SectorTags::extractSectorOffset(Addr addr) const 284{ 285 return (addr >> sectorShift) & sectorMask; 286} 287 288Addr 289SectorTags::regenerateBlkAddr(const CacheBlk* blk) const 290{ 291 const SectorSubBlk* blk_cast = static_cast<const SectorSubBlk*>(blk); 292 const SectorBlk* sec_blk = blk_cast->getSectorBlock(); 293 const Addr sec_addr = indexingPolicy->regenerateAddr(blk->tag, sec_blk); 294 return sec_addr | ((Addr)blk_cast->getSectorOffset() << sectorShift); 295} 296 297void 298SectorTags::forEachBlk(std::function<void(CacheBlk &)> visitor) 299{ 300 for (SectorSubBlk& blk : blks) { 301 visitor(blk); 302 } 303} 304 305bool 306SectorTags::anyBlk(std::function<bool(CacheBlk &)> visitor) 307{ 308 for (SectorSubBlk& blk : blks) { 309 if (visitor(blk)) { 310 return true; 311 } 312 } 313 return false; 314} 315 316SectorTags * 317SectorTagsParams::create() 318{ 319 // There must be a indexing policy 320 fatal_if(!indexing_policy, "An indexing policy is required"); 321 322 return new SectorTags(this); 323} |