src/mem/cache/tags/sector_tags.cc

   1 /*
   2  * Copyright (c) 2018, 2020 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
  29 /**
  30  * @file
  31  * Definitions of a sector tag store.
  32  */
  33
  34 #include "mem/cache/tags/sector_tags.hh"
  35
  36 #include <cassert>
  37 #include <memory>
  38 #include <string>
  39
  40 #include "base/intmath.hh"
  41 #include "base/logging.hh"
  42 #include "base/types.hh"
  43 #include "mem/cache/base.hh"
  44 #include "mem/cache/replacement_policies/base.hh"
  45 #include "mem/cache/replacement_policies/replaceable_entry.hh"
  46 #include "mem/cache/tags/indexing_policies/base.hh"
  47
  48 SectorTags::SectorTags(const SectorTagsParams &p)
  49     : BaseTags(p), allocAssoc(p.assoc),
  50       sequentialAccess(p.sequential_access),
  51       replacementPolicy(p.replacement_policy),
  52       numBlocksPerSector(p.num_blocks_per_sector),
  53       numSectors(numBlocks / numBlocksPerSector),
  54       sectorShift(floorLog2(blkSize)), sectorMask(numBlocksPerSector - 1),
  55       sectorStats(stats, *this)
  56 {
  57     // There must be a indexing policy
  58     fatal_if(!p.indexing_policy, "An indexing policy is required");
  59
  60     // Check parameters
  61     fatal_if(blkSize < 4 || !isPowerOf2(blkSize),
  62              "Block size must be at least 4 and a power of 2");
  63     fatal_if(!isPowerOf2(numBlocksPerSector),
  64              "# of blocks per sector must be non-zero and a power of 2");
  65 }
  66
  67 void
  68 SectorTags::tagsInit()
  69 {
  70     // Create blocks and sector blocks
  71     blks = std::vector<SectorSubBlk>(numBlocks);
  72     secBlks = std::vector<SectorBlk>(numSectors);
  73
  74     // Initialize all blocks
  75     unsigned blk_index = 0;       // index into blks array
  76     for (unsigned sec_blk_index = 0; sec_blk_index < numSectors;
  77          sec_blk_index++)
  78     {
  79         // Locate next cache sector
  80         SectorBlk* sec_blk = &secBlks[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         // Link block to indexing policy
 111         indexingPolicy->setEntry(sec_blk, sec_blk_index);
 112     }
 113 }
 114
 115 void
 116 SectorTags::invalidate(CacheBlk *blk)
 117 {
 118     BaseTags::invalidate(blk);
 119
 120     // Get block's sector
 121     SectorSubBlk* sub_blk = static_cast<SectorSubBlk*>(blk);
 122     const SectorBlk* sector_blk = sub_blk->getSectorBlock();
 123
 124     // When a block in a sector is invalidated, it does not make the tag
 125     // invalid automatically, as there might be other blocks in the sector
 126     // using it. The tag is invalidated only when there is a single block
 127     // in the sector.
 128     if (!sector_blk->isValid()) {
 129         // Decrease the number of tags in use
 130         stats.tagsInUse--;
 131         assert(stats.tagsInUse.value() >= 0);
 132
 133         // Invalidate replacement data, as we're invalidating the sector
 134         replacementPolicy->invalidate(sector_blk->replacementData);
 135     }
 136 }
 137
 138 CacheBlk*
 139 SectorTags::accessBlock(Addr addr, bool is_secure, Cycles &lat)
 140 {
 141     CacheBlk *blk = findBlock(addr, is_secure);
 142
 143     // Access all tags in parallel, hence one in each way.  The data side
 144     // either accesses all blocks in parallel, or one block sequentially on
 145     // a hit.  Sequential access with a miss doesn't access data.
 146     stats.tagAccesses += allocAssoc;
 147     if (sequentialAccess) {
 148         if (blk != nullptr) {
 149             stats.dataAccesses += 1;
 150         }
 151     } else {
 152         stats.dataAccesses += allocAssoc*numBlocksPerSector;
 153     }
 154
 155     // If a cache hit
 156     if (blk != nullptr) {
 157         // Update number of references to accessed block
 158         blk->increaseRefCount();
 159
 160         // Get block's sector
 161         SectorSubBlk* sub_blk = static_cast<SectorSubBlk*>(blk);
 162         const SectorBlk* sector_blk = sub_blk->getSectorBlock();
 163
 164         // Update replacement data of accessed block, which is shared with
 165         // the whole sector it belongs to
 166         replacementPolicy->touch(sector_blk->replacementData);
 167     }
 168
 169     // The tag lookup latency is the same for a hit or a miss
 170     lat = lookupLatency;
 171
 172     return blk;
 173 }
 174
 175 void
 176 SectorTags::insertBlock(const PacketPtr pkt, CacheBlk *blk)
 177 {
 178     // Get block's sector
 179     SectorSubBlk* sub_blk = static_cast<SectorSubBlk*>(blk);
 180     const SectorBlk* sector_blk = sub_blk->getSectorBlock();
 181
 182     // When a block is inserted, the tag is only a newly used tag if the
 183     // sector was not previously present in the cache.
 184     if (sector_blk->isValid()) {
 185         // An existing entry's replacement data is just updated
 186         replacementPolicy->touch(sector_blk->replacementData);
 187     } else {
 188         // Increment tag counter
 189         stats.tagsInUse++;
 190         assert(stats.tagsInUse.value() <= numSectors);
 191
 192         // A new entry resets the replacement data
 193         replacementPolicy->reset(sector_blk->replacementData);
 194     }
 195
 196     // Do common block insertion functionality
 197     BaseTags::insertBlock(pkt, blk);
 198 }
 199
 200 void
 201 SectorTags::moveBlock(CacheBlk *src_blk, CacheBlk *dest_blk)
 202 {
 203     const bool dest_was_valid =
 204         static_cast<SectorSubBlk*>(dest_blk)->getSectorBlock()->isValid();
 205
 206     BaseTags::moveBlock(src_blk, dest_blk);
 207
 208     // Get blocks' sectors. The blocks have effectively been swapped by now,
 209     // so src points to an invalid block, and dest to the moved valid one.
 210     SectorSubBlk* src_sub_blk = static_cast<SectorSubBlk*>(src_blk);
 211     const SectorBlk* src_sector_blk = src_sub_blk->getSectorBlock();
 212     SectorSubBlk* dest_sub_blk = static_cast<SectorSubBlk*>(dest_blk);
 213     const SectorBlk* dest_sector_blk = dest_sub_blk->getSectorBlock();
 214
 215     // Since the blocks were using different replacement data pointers,
 216     // we must touch the replacement data of the new entry, and invalidate
 217     // the one that is being moved.
 218     // When a block in a sector is invalidated, it does not make the tag
 219     // invalid automatically, as there might be other blocks in the sector
 220     // using it. The tag is invalidated only when there is a single block
 221     // in the sector.
 222     if (!src_sector_blk->isValid()) {
 223         // Invalidate replacement data, as we're invalidating the sector
 224         replacementPolicy->invalidate(src_sector_blk->replacementData);
 225
 226         if (dest_was_valid) {
 227             // If destination sector was valid, and the source sector became
 228             // invalid, there is one less tag being used
 229             stats.tagsInUse--;
 230             assert(stats.tagsInUse.value() >= 0);
 231         }
 232     } else if (!dest_was_valid) {
 233         // If destination sector was invalid and became valid, and the source
 234         // sector is still valid, there is one extra tag being used
 235         stats.tagsInUse++;
 236         assert(stats.tagsInUse.value() <= numSectors);
 237     }
 238
 239     if (dest_was_valid) {
 240         replacementPolicy->touch(dest_sector_blk->replacementData);
 241     } else {
 242         replacementPolicy->reset(dest_sector_blk->replacementData);
 243     }
 244 }
 245
 246 CacheBlk*
 247 SectorTags::findBlock(Addr addr, bool is_secure) const
 248 {
 249     // Extract sector tag
 250     const Addr tag = extractTag(addr);
 251
 252     // The address can only be mapped to a specific location of a sector
 253     // due to sectors being composed of contiguous-address entries
 254     const Addr offset = extractSectorOffset(addr);
 255
 256     // Find all possible sector entries that may contain the given address
 257     const std::vector<ReplaceableEntry*> entries =
 258         indexingPolicy->getPossibleEntries(addr);
 259
 260     // Search for block
 261     for (const auto& sector : entries) {
 262         auto blk = static_cast<SectorBlk*>(sector)->blks[offset];
 263         if (blk->matchTag(tag, is_secure)) {
 264             return blk;
 265         }
 266     }
 267
 268     // Did not find block
 269     return nullptr;
 270 }
 271
 272 CacheBlk*
 273 SectorTags::findVictim(Addr addr, const bool is_secure, const std::size_t size,
 274                        std::vector<CacheBlk*>& evict_blks)
 275 {
 276     // Get possible entries to be victimized
 277     const std::vector<ReplaceableEntry*> sector_entries =
 278         indexingPolicy->getPossibleEntries(addr);
 279
 280     // Check if the sector this address belongs to has been allocated
 281     Addr tag = extractTag(addr);
 282     SectorBlk* victim_sector = nullptr;
 283     for (const auto& sector : sector_entries) {
 284         SectorBlk* sector_blk = static_cast<SectorBlk*>(sector);
 285         if (sector_blk->matchTag(tag, is_secure)) {
 286             victim_sector = sector_blk;
 287             break;
 288         }
 289     }
 290
 291     // If the sector is not present
 292     if (victim_sector == nullptr){
 293         // Choose replacement victim from replacement candidates
 294         victim_sector = static_cast<SectorBlk*>(replacementPolicy->getVictim(
 295                                                 sector_entries));
 296     }
 297
 298     // Get the entry of the victim block within the sector
 299     SectorSubBlk* victim = victim_sector->blks[extractSectorOffset(addr)];
 300
 301     // Get evicted blocks. Blocks are only evicted if the sectors mismatch and
 302     // the currently existing sector is valid.
 303     if (victim_sector->matchTag(tag, is_secure)) {
 304         // It would be a hit if victim was valid, and upgrades do not call
 305         // findVictim, so it cannot happen
 306         assert(!victim->isValid());
 307     } else {
 308         // The whole sector must be evicted to make room for the new sector
 309         for (const auto& blk : victim_sector->blks){
 310             if (blk->isValid()) {
 311                 evict_blks.push_back(blk);
 312             }
 313         }
 314     }
 315
 316     // Update number of sub-blocks evicted due to a replacement
 317     sectorStats.evictionsReplacement[evict_blks.size()]++;
 318
 319     return victim;
 320 }
 321
 322 int
 323 SectorTags::extractSectorOffset(Addr addr) const
 324 {
 325     return (addr >> sectorShift) & sectorMask;
 326 }
 327
 328 Addr
 329 SectorTags::regenerateBlkAddr(const CacheBlk* blk) const
 330 {
 331     const SectorSubBlk* blk_cast = static_cast<const SectorSubBlk*>(blk);
 332     const SectorBlk* sec_blk = blk_cast->getSectorBlock();
 333     const Addr sec_addr =
 334         indexingPolicy->regenerateAddr(blk->getTag(), sec_blk);
 335     return sec_addr | ((Addr)blk_cast->getSectorOffset() << sectorShift);
 336 }
 337
 338 SectorTags::SectorTagsStats::SectorTagsStats(BaseTagStats &base_group,
 339     SectorTags& _tags)
 340   : Stats::Group(&base_group), tags(_tags),
 341     evictionsReplacement(this, "evictions_replacement",
 342         "Number of blocks evicted due to a replacement")
 343 {
 344 }
 345
 346 void
 347 SectorTags::SectorTagsStats::regStats()
 348 {
 349     Stats::Group::regStats();
 350
 351     evictionsReplacement.init(tags.numBlocksPerSector + 1);
 352     for (unsigned i = 0; i <= tags.numBlocksPerSector; ++i) {
 353         evictionsReplacement.subname(i, std::to_string(i));
 354         evictionsReplacement.subdesc(i, "Number of replacements that caused " \
 355             "the eviction of " + std::to_string(i) + " blocks");
 356     }
 357 }
 358
 359 void
 360 SectorTags::forEachBlk(std::function<void(CacheBlk &)> visitor)
 361 {
 362     for (SectorSubBlk& blk : blks) {
 363         visitor(blk);
 364     }
 365 }
 366
 367 bool
 368 SectorTags::anyBlk(std::function<bool(CacheBlk &)> visitor)
 369 {
 370     for (SectorSubBlk& blk : blks) {
 371         if (visitor(blk)) {
 372             return true;
 373         }
 374     }
 375     return false;
 376 }