src/mem/cache/tags/sector_tags.cc

   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
  50 SectorTags::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
  66 void
  67 SectorTags::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
 113 void
 114 SectorTags::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
 135 CacheBlk*
 136 SectorTags::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
 182 void
 183 SectorTags::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
 209 CacheBlk*
 210 SectorTags::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
 236 CacheBlk*
 237 SectorTags::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
 280     return victim;
 281 }
 282
 283 int
 284 SectorTags::extractSectorOffset(Addr addr) const
 285 {
 286     return (addr >> sectorShift) & sectorMask;
 287 }
 288
 289 Addr
 290 SectorTags::regenerateBlkAddr(const CacheBlk* blk) const
 291 {
 292     const SectorSubBlk* blk_cast = static_cast<const SectorSubBlk*>(blk);
 293     const SectorBlk* sec_blk = blk_cast->getSectorBlock();
 294     const Addr sec_addr = indexingPolicy->regenerateAddr(blk->tag, sec_blk);
 295     return sec_addr | ((Addr)blk_cast->getSectorOffset() << sectorShift);
 296 }
 297
 298 void
 299 SectorTags::forEachBlk(std::function<void(CacheBlk &)> visitor)
 300 {
 301     for (SectorSubBlk& blk : blks) {
 302         visitor(blk);
 303     }
 304 }
 305
 306 bool
 307 SectorTags::anyBlk(std::function<bool(CacheBlk &)> visitor)
 308 {
 309     for (SectorSubBlk& blk : blks) {
 310         if (visitor(blk)) {
 311             return true;
 312         }
 313     }
 314     return false;
 315 }
 316
 317 SectorTags *
 318 SectorTagsParams::create()
 319 {
 320     // There must be a indexing policy
 321     fatal_if(!indexing_policy, "An indexing policy is required");
 322
 323     return new SectorTags(this);
 324 }