sector_tags.cc revision 13215:82cdb8db4643
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 base set associative 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 49SectorTags::SectorTags(const SectorTagsParams *p) 50 : BaseTags(p), assoc(p->assoc), 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), 55 numSets(numSectors / p->assoc), 56 blks(numBlocks), secBlks(numSectors), sets(numSets), 57 sectorShift(floorLog2(blkSize)), 58 setShift(sectorShift + floorLog2(numBlocksPerSector)), 59 tagShift(setShift + floorLog2(numSets)), 60 sectorMask(numBlocksPerSector - 1), setMask(numSets - 1) 61{ 62 // Check parameters 63 fatal_if(blkSize < 4 || !isPowerOf2(blkSize), 64 "Block size must be at least 4 and a power of 2"); 65 fatal_if(!isPowerOf2(numSets), 66 "# of sets must be non-zero and a power of 2"); 67 fatal_if(!isPowerOf2(numBlocksPerSector), 68 "# of blocks per sector must be non-zero and a power of 2"); 69 fatal_if(assoc <= 0, "associativity must be greater than zero"); 70 71 // Initialize all sets 72 unsigned sec_blk_index = 0; // index into sector blks array 73 unsigned blk_index = 0; // index into blks array 74 for (unsigned i = 0; i < numSets; ++i) { 75 sets[i].resize(assoc); 76 77 // Initialize all sectors in this set 78 for (unsigned j = 0; j < assoc; ++j) { 79 // Select block within the set to be linked 80 SectorBlk*& sec_blk = sets[i][j]; 81 82 // Locate next cache sector 83 sec_blk = &secBlks[sec_blk_index]; 84 85 // Associate a replacement data entry to the sector 86 sec_blk->replacementData = replacementPolicy->instantiateEntry(); 87 88 // Initialize all blocks in this sector 89 sec_blk->blks.resize(numBlocksPerSector); 90 for (unsigned k = 0; k < numBlocksPerSector; ++k){ 91 // Select block within the set to be linked 92 SectorSubBlk*& blk = sec_blk->blks[k]; 93 94 // Locate next cache block 95 blk = &blks[blk_index]; 96 97 // Associate a data chunk to the block 98 blk->data = &dataBlks[blkSize*blk_index]; 99 100 // Associate sector block to this block 101 blk->setSectorBlock(sec_blk); 102 103 // Associate the sector replacement data to this block 104 blk->replacementData = sec_blk->replacementData; 105 106 // Set its set, way and sector offset 107 blk->set = i; 108 blk->way = j; 109 blk->setSectorOffset(k); 110 111 // Update block index 112 ++blk_index; 113 } 114 115 // Update sector block index 116 ++sec_blk_index; 117 } 118 } 119} 120 121void 122SectorTags::invalidate(CacheBlk *blk) 123{ 124 BaseTags::invalidate(blk); 125 126 // Get block's sector 127 SectorSubBlk* sub_blk = static_cast<SectorSubBlk*>(blk); 128 const SectorBlk* sector_blk = sub_blk->getSectorBlock(); 129 130 // When a block in a sector is invalidated, it does not make the tag 131 // invalid automatically, as there might be other blocks in the sector 132 // using it. The tag is invalidated only when there is a single block 133 // in the sector. 134 if (!sector_blk->isValid()) { 135 // Decrease the number of tags in use 136 tagsInUse--; 137 138 // Invalidate replacement data, as we're invalidating the sector 139 replacementPolicy->invalidate(sector_blk->replacementData); 140 } 141} 142 143CacheBlk* 144SectorTags::accessBlock(Addr addr, bool is_secure, Cycles &lat) 145{ 146 CacheBlk *blk = findBlock(addr, is_secure); 147 148 // Access all tags in parallel, hence one in each way. The data side 149 // either accesses all blocks in parallel, or one block sequentially on 150 // a hit. Sequential access with a miss doesn't access data. 151 tagAccesses += allocAssoc; 152 if (sequentialAccess) { 153 if (blk != nullptr) { 154 dataAccesses += 1; 155 } 156 } else { 157 dataAccesses += allocAssoc*numBlocksPerSector; 158 } 159 160 if (blk != nullptr) { 161 // If a cache hit 162 lat = accessLatency; 163 // Check if the block to be accessed is available. If not, 164 // apply the accessLatency on top of block->whenReady. 165 if (blk->whenReady > curTick() && 166 cache->ticksToCycles(blk->whenReady - curTick()) > 167 accessLatency) { 168 lat = cache->ticksToCycles(blk->whenReady - curTick()) + 169 accessLatency; 170 } 171 172 // Update number of references to accessed block 173 blk->refCount++; 174 175 // Get block's sector 176 SectorSubBlk* sub_blk = static_cast<SectorSubBlk*>(blk); 177 const SectorBlk* sector_blk = sub_blk->getSectorBlock(); 178 179 // Update replacement data of accessed block, which is shared with 180 // the whole sector it belongs to 181 replacementPolicy->touch(sector_blk->replacementData); 182 } else { 183 // If a cache miss 184 lat = lookupLatency; 185 } 186 187 return blk; 188} 189 190const std::vector<SectorBlk*> 191SectorTags::getPossibleLocations(Addr addr) const 192{ 193 return sets[extractSet(addr)]; 194} 195 196void 197SectorTags::insertBlock(const Addr addr, const bool is_secure, 198 const int src_master_ID, const uint32_t task_ID, 199 CacheBlk *blk) 200{ 201 // Do common block insertion functionality 202 BaseTags::insertBlock(addr, is_secure, src_master_ID, task_ID, blk); 203 204 // Get block's sector 205 SectorSubBlk* sub_blk = static_cast<SectorSubBlk*>(blk); 206 const SectorBlk* sector_blk = sub_blk->getSectorBlock(); 207 208 // When a block is inserted, the tag is only a newly used tag if the 209 // sector was not previously present in the cache. 210 // This assumes BaseTags::insertBlock does not set the valid bit. 211 if (sector_blk->isValid()) { 212 // An existing entry's replacement data is just updated 213 replacementPolicy->touch(sector_blk->replacementData); 214 } else { 215 // Increment tag counter 216 tagsInUse++; 217 218 // A new entry resets the replacement data 219 replacementPolicy->reset(sector_blk->replacementData); 220 } 221} 222 223CacheBlk* 224SectorTags::findBlock(Addr addr, bool is_secure) const 225{ 226 // Extract sector tag 227 const Addr tag = extractTag(addr); 228 229 // The address can only be mapped to a specific location of a sector 230 // due to sectors being composed of contiguous-address entries 231 const Addr offset = extractSectorOffset(addr); 232 233 // Find all possible sector locations for the given address 234 const std::vector<SectorBlk*> locations = getPossibleLocations(addr); 235 236 // Search for block 237 for (const auto& sector : locations) { 238 auto blk = sector->blks[offset]; 239 if (blk->getTag() == tag && blk->isValid() && 240 blk->isSecure() == is_secure) { 241 return blk; 242 } 243 } 244 245 // Did not find block 246 return nullptr; 247} 248 249ReplaceableEntry* 250SectorTags::findBlockBySetAndWay(int set, int way) const 251{ 252 return sets[set][way]; 253} 254 255CacheBlk* 256SectorTags::findVictim(Addr addr, const bool is_secure, 257 std::vector<CacheBlk*>& evict_blks) const 258{ 259 // Get all possible locations of this sector 260 const std::vector<SectorBlk*> sector_locations = 261 getPossibleLocations(addr); 262 263 // Check if the sector this address belongs to has been allocated 264 Addr tag = extractTag(addr); 265 SectorBlk* victim_sector = nullptr; 266 for (const auto& sector : sector_locations){ 267 if ((tag == sector->getTag()) && sector->isValid() && 268 (is_secure == sector->isSecure())){ 269 victim_sector = sector; 270 break; 271 } 272 } 273 274 // If the sector is not present 275 if (victim_sector == nullptr){ 276 // Choose replacement victim from replacement candidates 277 victim_sector = static_cast<SectorBlk*>(replacementPolicy->getVictim( 278 std::vector<ReplaceableEntry*>( 279 sector_locations.begin(), sector_locations.end()))); 280 } 281 282 // Get the location of the victim block within the sector 283 SectorSubBlk* victim = victim_sector->blks[extractSectorOffset(addr)]; 284 285 // Get evicted blocks. Blocks are only evicted if the sectors mismatch and 286 // the currently existing sector is valid. 287 if ((tag == victim_sector->getTag()) && 288 (is_secure == victim_sector->isSecure())){ 289 // It would be a hit if victim was valid, and upgrades do not call 290 // findVictim, so it cannot happen 291 assert(!victim->isValid()); 292 } else { 293 // The whole sector must be evicted to make room for the new sector 294 for (const auto& blk : victim_sector->blks){ 295 evict_blks.push_back(blk); 296 } 297 } 298 299 DPRINTF(CacheRepl, "set %x, way %x, sector offset %x: %s\n", 300 "selecting blk for replacement\n", victim->set, victim->way, 301 victim->getSectorOffset()); 302 303 return victim; 304} 305 306Addr 307SectorTags::extractTag(Addr addr) const 308{ 309 return addr >> tagShift; 310} 311 312int 313SectorTags::extractSet(Addr addr) const 314{ 315 return (addr >> setShift) & setMask; 316} 317 318int 319SectorTags::extractSectorOffset(Addr addr) const 320{ 321 return (addr >> sectorShift) & sectorMask; 322} 323 324Addr 325SectorTags::regenerateBlkAddr(const CacheBlk* blk) const 326{ 327 const SectorSubBlk* blk_cast = static_cast<const SectorSubBlk*>(blk); 328 return ((blk_cast->getTag() << tagShift) | ((Addr)blk->set << setShift) | 329 ((Addr)blk_cast->getSectorOffset() << sectorShift)); 330} 331 332void 333SectorTags::forEachBlk(std::function<void(CacheBlk &)> visitor) 334{ 335 for (SectorSubBlk& blk : blks) { 336 visitor(blk); 337 } 338} 339 340bool 341SectorTags::anyBlk(std::function<bool(CacheBlk &)> visitor) 342{ 343 for (SectorSubBlk& blk : blks) { 344 if (visitor(blk)) { 345 return true; 346 } 347 } 348 return false; 349} 350 351SectorTags * 352SectorTagsParams::create() 353{ 354 return new SectorTags(this); 355} 356