src/mem/cache/tags/base_set_assoc.hh

   1 /*
   2  * Copyright (c) 2012-2014 ARM Limited
   3  * All rights reserved.
   4  *
   5  * The license below extends only to copyright in the software and shall
   6  * not be construed as granting a license to any other intellectual
   7  * property including but not limited to intellectual property relating
   8  * to a hardware implementation of the functionality of the software
   9  * licensed hereunder.  You may use the software subject to the license
  10  * terms below provided that you ensure that this notice is replicated
  11  * unmodified and in its entirety in all distributions of the software,
  12  * modified or unmodified, in source code or in binary form.
  13  *
  14  * Copyright (c) 2003-2005,2014 The Regents of The University of Michigan
  15  * All rights reserved.
  16  *
  17  * Redistribution and use in source and binary forms, with or without
  18  * modification, are permitted provided that the following conditions are
  19  * met: redistributions of source code must retain the above copyright
  20  * notice, this list of conditions and the following disclaimer;
  21  * redistributions in binary form must reproduce the above copyright
  22  * notice, this list of conditions and the following disclaimer in the
  23  * documentation and/or other materials provided with the distribution;
  24  * neither the name of the copyright holders nor the names of its
  25  * contributors may be used to endorse or promote products derived from
  26  * this software without specific prior written permission.
  27  *
  28  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  29  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  30  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  31  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  32  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  33  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  34  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  35  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  36  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  37  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  38  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  39  *
  40  * Authors: Erik Hallnor
  41  */
  42
  43 /**
  44  * @file
  45  * Declaration of a base set associative tag store.
  46  */
  47
  48 #ifndef __MEM_CACHE_TAGS_BASESETASSOC_HH__
  49 #define __MEM_CACHE_TAGS_BASESETASSOC_HH__
  50
  51 #include <cassert>
  52 #include <cstring>
  53 #include <list>
  54
  55 #include "mem/cache/base.hh"
  56 #include "mem/cache/blk.hh"
  57 #include "mem/cache/tags/base.hh"
  58 #include "mem/cache/tags/cacheset.hh"
  59 #include "mem/packet.hh"
  60 #include "params/BaseSetAssoc.hh"
  61
  62 /**
  63  * A BaseSetAssoc cache tag store.
  64  * @sa  \ref gem5MemorySystem "gem5 Memory System"
  65  *
  66  * The BaseSetAssoc tags provide a base, as well as the functionality
  67  * common to any set associative tags. Any derived class must implement
  68  * the methods related to the specifics of the actual replacment policy.
  69  * These are:
  70  *
  71  * BlkType* accessBlock();
  72  * BlkType* findVictim();
  73  * void insertBlock();
  74  * void invalidate();
  75  */
  76 class BaseSetAssoc : public BaseTags
  77 {
  78   public:
  79     /** Typedef the block type used in this tag store. */
  80     typedef CacheBlk BlkType;
  81     /** Typedef the set type used in this tag store. */
  82     typedef CacheSet<CacheBlk> SetType;
  83
  84
  85   protected:
  86     /** The associativity of the cache. */
  87     const unsigned assoc;
  88     /** The allocatable associativity of the cache (alloc mask). */
  89     unsigned allocAssoc;
  90     /** The number of sets in the cache. */
  91     const unsigned numSets;
  92     /** Whether tags and data are accessed sequentially. */
  93     const bool sequentialAccess;
  94
  95     /** The cache sets. */
  96     SetType *sets;
  97
  98     /** The cache blocks. */
  99     BlkType *blks;
 100     /** The data blocks, 1 per cache block. */
 101     uint8_t *dataBlks;
 102
 103     /** The amount to shift the address to get the set. */
 104     int setShift;
 105     /** The amount to shift the address to get the tag. */
 106     int tagShift;
 107     /** Mask out all bits that aren't part of the set index. */
 108     unsigned setMask;
 109     /** Mask out all bits that aren't part of the block offset. */
 110     unsigned blkMask;
 111
 112 public:
 113
 114     /** Convenience typedef. */
 115      typedef BaseSetAssocParams Params;
 116
 117     /**
 118      * Construct and initialize this tag store.
 119      */
 120     BaseSetAssoc(const Params *p);
 121
 122     /**
 123      * Destructor
 124      */
 125     virtual ~BaseSetAssoc();
 126
 127     /**
 128      * Find the cache block given set and way
 129      * @param set The set of the block.
 130      * @param way The way of the block.
 131      * @return The cache block.
 132      */
 133     CacheBlk *findBlockBySetAndWay(int set, int way) const override;
 134
 135     /**
 136      * Invalidate the given block.
 137      * @param blk The block to invalidate.
 138      */
 139     void invalidate(CacheBlk *blk) override
 140     {
 141         assert(blk);
 142         assert(blk->isValid());
 143         tagsInUse--;
 144         assert(blk->srcMasterId < cache->system->maxMasters());
 145         occupancies[blk->srcMasterId]--;
 146         blk->srcMasterId = Request::invldMasterId;
 147         blk->task_id = ContextSwitchTaskId::Unknown;
 148         blk->tickInserted = curTick();
 149     }
 150
 151     /**
 152      * Access block and update replacement data. May not succeed, in which case
 153      * nullptr is returned. This has all the implications of a cache
 154      * access and should only be used as such. Returns the access latency as a
 155      * side effect.
 156      * @param addr The address to find.
 157      * @param is_secure True if the target memory space is secure.
 158      * @param asid The address space ID.
 159      * @param lat The access latency.
 160      * @return Pointer to the cache block if found.
 161      */
 162     CacheBlk* accessBlock(Addr addr, bool is_secure, Cycles &lat,
 163                           int context_src) override
 164     {
 165         Addr tag = extractTag(addr);
 166         int set = extractSet(addr);
 167         BlkType *blk = sets[set].findBlk(tag, is_secure);
 168
 169         // Access all tags in parallel, hence one in each way.  The data side
 170         // either accesses all blocks in parallel, or one block sequentially on
 171         // a hit.  Sequential access with a miss doesn't access data.
 172         tagAccesses += allocAssoc;
 173         if (sequentialAccess) {
 174             if (blk != nullptr) {
 175                 dataAccesses += 1;
 176             }
 177         } else {
 178             dataAccesses += allocAssoc;
 179         }
 180
 181         if (blk != nullptr) {
 182             // If a cache hit
 183             lat = accessLatency;
 184             // Check if the block to be accessed is available. If not,
 185             // apply the accessLatency on top of block->whenReady.
 186             if (blk->whenReady > curTick() &&
 187                 cache->ticksToCycles(blk->whenReady - curTick()) >
 188                 accessLatency) {
 189                 lat = cache->ticksToCycles(blk->whenReady - curTick()) +
 190                 accessLatency;
 191             }
 192             blk->refCount += 1;
 193         } else {
 194             // If a cache miss
 195             lat = lookupLatency;
 196         }
 197
 198         return blk;
 199     }
 200
 201     /**
 202      * Finds the given address in the cache, do not update replacement data.
 203      * i.e. This is a no-side-effect find of a block.
 204      * @param addr The address to find.
 205      * @param is_secure True if the target memory space is secure.
 206      * @param asid The address space ID.
 207      * @return Pointer to the cache block if found.
 208      */
 209     CacheBlk* findBlock(Addr addr, bool is_secure) const override;
 210
 211     /**
 212      * Find an invalid block to evict for the address provided.
 213      * If there are no invalid blocks, this will return the block
 214      * in the least-recently-used position.
 215      * @param addr The addr to a find a replacement candidate for.
 216      * @return The candidate block.
 217      */
 218     CacheBlk* findVictim(Addr addr) override
 219     {
 220         BlkType *blk = nullptr;
 221         int set = extractSet(addr);
 222
 223         // prefer to evict an invalid block
 224         for (int i = 0; i < allocAssoc; ++i) {
 225             blk = sets[set].blks[i];
 226             if (!blk->isValid())
 227                 break;
 228         }
 229
 230         return blk;
 231     }
 232
 233     /**
 234      * Insert the new block into the cache.
 235      * @param pkt Packet holding the address to update
 236      * @param blk The block to update.
 237      */
 238      void insertBlock(PacketPtr pkt, CacheBlk *blk) override
 239      {
 240          Addr addr = pkt->getAddr();
 241          MasterID master_id = pkt->req->masterId();
 242          uint32_t task_id = pkt->req->taskId();
 243
 244          if (!blk->isTouched) {
 245              tagsInUse++;
 246              blk->isTouched = true;
 247              if (!warmedUp && tagsInUse.value() >= warmupBound) {
 248                  warmedUp = true;
 249                  warmupCycle = curTick();
 250              }
 251          }
 252
 253          // If we're replacing a block that was previously valid update
 254          // stats for it. This can't be done in findBlock() because a
 255          // found block might not actually be replaced there if the
 256          // coherence protocol says it can't be.
 257          if (blk->isValid()) {
 258              replacements[0]++;
 259              totalRefs += blk->refCount;
 260              ++sampledRefs;
 261              blk->refCount = 0;
 262
 263              // deal with evicted block
 264              assert(blk->srcMasterId < cache->system->maxMasters());
 265              occupancies[blk->srcMasterId]--;
 266
 267              blk->invalidate();
 268          }
 269
 270          blk->isTouched = true;
 271
 272          // Set tag for new block.  Caller is responsible for setting status.
 273          blk->tag = extractTag(addr);
 274
 275          // deal with what we are bringing in
 276          assert(master_id < cache->system->maxMasters());
 277          occupancies[master_id]++;
 278          blk->srcMasterId = master_id;
 279          blk->task_id = task_id;
 280          blk->tickInserted = curTick();
 281
 282          // We only need to write into one tag and one data block.
 283          tagAccesses += 1;
 284          dataAccesses += 1;
 285      }
 286
 287     /**
 288      * Limit the allocation for the cache ways.
 289      * @param ways The maximum number of ways available for replacement.
 290      */
 291     virtual void setWayAllocationMax(int ways) override
 292     {
 293         fatal_if(ways < 1, "Allocation limit must be greater than zero");
 294         allocAssoc = ways;
 295     }
 296
 297     /**
 298      * Get the way allocation mask limit.
 299      * @return The maximum number of ways available for replacement.
 300      */
 301     virtual int getWayAllocationMax() const override
 302     {
 303         return allocAssoc;
 304     }
 305
 306     /**
 307      * Generate the tag from the given address.
 308      * @param addr The address to get the tag from.
 309      * @return The tag of the address.
 310      */
 311     Addr extractTag(Addr addr) const override
 312     {
 313         return (addr >> tagShift);
 314     }
 315
 316     /**
 317      * Calculate the set index from the address.
 318      * @param addr The address to get the set from.
 319      * @return The set index of the address.
 320      */
 321     int extractSet(Addr addr) const override
 322     {
 323         return ((addr >> setShift) & setMask);
 324     }
 325
 326     /**
 327      * Align an address to the block size.
 328      * @param addr the address to align.
 329      * @return The block address.
 330      */
 331     Addr blkAlign(Addr addr) const
 332     {
 333         return (addr & ~(Addr)blkMask);
 334     }
 335
 336     /**
 337      * Regenerate the block address from the tag.
 338      * @param tag The tag of the block.
 339      * @param set The set of the block.
 340      * @return The block address.
 341      */
 342     Addr regenerateBlkAddr(Addr tag, unsigned set) const override
 343     {
 344         return ((tag << tagShift) | ((Addr)set << setShift));
 345     }
 346
 347     /**
 348      * Called at end of simulation to complete average block reference stats.
 349      */
 350     void cleanupRefs() override;
 351
 352     /**
 353      * Print all tags used
 354      */
 355     std::string print() const override;
 356
 357     /**
 358      * Called prior to dumping stats to compute task occupancy
 359      */
 360     void computeStats() override;
 361
 362     /**
 363      * Visit each block in the tag store and apply a visitor to the
 364      * block.
 365      *
 366      * The visitor should be a function (or object that behaves like a
 367      * function) that takes a cache block reference as its parameter
 368      * and returns a bool. A visitor can request the traversal to be
 369      * stopped by returning false, returning true causes it to be
 370      * called for the next block in the tag store.
 371      *
 372      * \param visitor Visitor to call on each block.
 373      */
 374     void forEachBlk(CacheBlkVisitor &visitor) override {
 375         for (unsigned i = 0; i < numSets * assoc; ++i) {
 376             if (!visitor(blks[i]))
 377                 return;
 378         }
 379     }
 380 };
 381
 382 #endif // __MEM_CACHE_TAGS_BASESETASSOC_HH__