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 "mem/cache/base.hh" 46#include "mem/cache/replacement_policies/base.hh" 47#include "mem/cache/replacement_policies/replaceable_entry.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 / numBlocksPerSector), 56 sectorShift(floorLog2(blkSize)), 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::tagsInit() 67{ 68 // Create blocks and sector blocks 69 blks = std::vector<SectorSubBlk>(numBlocks); 70 secBlks = std::vector<SectorBlk>(numSectors); 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 // Associate a replacement data entry to the sector 81 sec_blk->replacementData = replacementPolicy->instantiateEntry(); 82 83 // Initialize all blocks in this sector 84 sec_blk->blks.resize(numBlocksPerSector); 85 for (unsigned k = 0; k < numBlocksPerSector; ++k){ 86 // Select block within the set to be linked 87 SectorSubBlk*& blk = sec_blk->blks[k]; 88 89 // Locate next cache block 90 blk = &blks[blk_index]; 91 92 // Associate a data chunk to the block 93 blk->data = &dataBlks[blkSize*blk_index]; 94 95 // Associate sector block to this block 96 blk->setSectorBlock(sec_blk); 97 98 // Associate the sector replacement data to this block 99 blk->replacementData = sec_blk->replacementData; 100 101 // Set its index and sector offset 102 blk->setSectorOffset(k); 103 104 // Update block index 105 ++blk_index; 106 } 107 108 // Link block to indexing policy 109 indexingPolicy->setEntry(sec_blk, sec_blk_index); 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 a cache hit 153 if (blk != nullptr) { 154 // Update number of references to accessed block 155 blk->refCount++; 156 157 // Get block's sector 158 SectorSubBlk* sub_blk = static_cast<SectorSubBlk*>(blk); 159 const SectorBlk* sector_blk = sub_blk->getSectorBlock(); 160 161 // Update replacement data of accessed block, which is shared with 162 // the whole sector it belongs to 163 replacementPolicy->touch(sector_blk->replacementData); 164 } 165 166 // The tag lookup latency is the same for a hit or a miss 167 lat = lookupLatency; 168 169 return blk; 170} 171 172void 173SectorTags::insertBlock(const PacketPtr pkt, CacheBlk *blk) 174{ 175 // Get block's sector 176 SectorSubBlk* sub_blk = static_cast<SectorSubBlk*>(blk); 177 const SectorBlk* sector_blk = sub_blk->getSectorBlock(); 178 179 // When a block is inserted, the tag is only a newly used tag if the 180 // sector was not previously present in the cache. 181 if (sector_blk->isValid()) { 182 // An existing entry's replacement data is just updated 183 replacementPolicy->touch(sector_blk->replacementData); 184 } else { 185 // Increment tag counter 186 tagsInUse++; 187 188 // A new entry resets the replacement data 189 replacementPolicy->reset(sector_blk->replacementData); 190 } 191 192 // Do common block insertion functionality 193 BaseTags::insertBlock(pkt, blk); 194} 195 196CacheBlk* 197SectorTags::findBlock(Addr addr, bool is_secure) const 198{ 199 // Extract sector tag 200 const Addr tag = extractTag(addr); 201 202 // The address can only be mapped to a specific location of a sector 203 // due to sectors being composed of contiguous-address entries 204 const Addr offset = extractSectorOffset(addr); 205 206 // Find all possible sector entries that may contain the given address 207 const std::vector<ReplaceableEntry*> entries = 208 indexingPolicy->getPossibleEntries(addr); 209 210 // Search for block 211 for (const auto& sector : entries) { 212 auto blk = static_cast<SectorBlk*>(sector)->blks[offset]; 213 if (blk->getTag() == tag && blk->isValid() && 214 blk->isSecure() == is_secure) { 215 return blk; 216 } 217 } 218 219 // Did not find block 220 return nullptr; 221} 222 223CacheBlk* 224SectorTags::findVictim(Addr addr, const bool is_secure, const std::size_t size, 225 std::vector<CacheBlk*>& evict_blks) const 226{ 227 // Get possible entries to be victimized 228 const std::vector<ReplaceableEntry*> sector_entries = 229 indexingPolicy->getPossibleEntries(addr); 230 231 // Check if the sector this address belongs to has been allocated 232 Addr tag = extractTag(addr); 233 SectorBlk* victim_sector = nullptr; 234 for (const auto& sector : sector_entries) { 235 SectorBlk* sector_blk = static_cast<SectorBlk*>(sector); 236 if ((tag == sector_blk->getTag()) && sector_blk->isValid() && 237 (is_secure == sector_blk->isSecure())){ 238 victim_sector = sector_blk; 239 break; 240 } 241 } 242 243 // If the sector is not present 244 if (victim_sector == nullptr){ 245 // Choose replacement victim from replacement candidates 246 victim_sector = static_cast<SectorBlk*>(replacementPolicy->getVictim( 247 sector_entries)); 248 } 249 250 // Get the entry of the victim block within the sector 251 SectorSubBlk* victim = victim_sector->blks[extractSectorOffset(addr)]; 252 253 // Get evicted blocks. Blocks are only evicted if the sectors mismatch and 254 // the currently existing sector is valid. 255 if ((tag == victim_sector->getTag()) && 256 (is_secure == victim_sector->isSecure())){ 257 // It would be a hit if victim was valid, and upgrades do not call 258 // findVictim, so it cannot happen 259 assert(!victim->isValid()); 260 } else { 261 // The whole sector must be evicted to make room for the new sector 262 for (const auto& blk : victim_sector->blks){ 263 evict_blks.push_back(blk); 264 } 265 } 266 267 return victim; 268} 269 270int 271SectorTags::extractSectorOffset(Addr addr) const 272{ 273 return (addr >> sectorShift) & sectorMask; 274} 275 276Addr 277SectorTags::regenerateBlkAddr(const CacheBlk* blk) const 278{ 279 const SectorSubBlk* blk_cast = static_cast<const SectorSubBlk*>(blk); 280 const SectorBlk* sec_blk = blk_cast->getSectorBlock(); 281 const Addr sec_addr = indexingPolicy->regenerateAddr(blk->tag, sec_blk); 282 return sec_addr | ((Addr)blk_cast->getSectorOffset() << sectorShift); 283} 284 285void 286SectorTags::forEachBlk(std::function<void(CacheBlk &)> visitor) 287{ 288 for (SectorSubBlk& blk : blks) { 289 visitor(blk); 290 } 291} 292 293bool 294SectorTags::anyBlk(std::function<bool(CacheBlk &)> visitor) 295{ 296 for (SectorSubBlk& blk : blks) { 297 if (visitor(blk)) { 298 return true; 299 } 300 } 301 return false; 302} 303 304SectorTags * 305SectorTagsParams::create() 306{ 307 // There must be a indexing policy 308 fatal_if(!indexing_policy, "An indexing policy is required"); 309 310 return new SectorTags(this); 311} 312