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 for a list of pointers to the local block class. */
  82     typedef std::list<BlkType*> BlkList;
  83     /** Typedef the set type used in this tag store. */
  84     typedef CacheSet<CacheBlk> SetType;
  85
  86
  87   protected:
  88     /** The associativity of the cache. */
  89     const unsigned assoc;
  90     /** The allocatable associativity of the cache (alloc mask). */
  91     unsigned allocAssoc;
  92     /** The number of sets in the cache. */
  93     const unsigned numSets;
  94     /** Whether tags and data are accessed sequentially. */
  95     const bool sequentialAccess;
  96
  97     /** The cache sets. */
  98     SetType *sets;
  99
 100     /** The cache blocks. */
 101     BlkType *blks;
 102     /** The data blocks, 1 per cache block. */
 103     uint8_t *dataBlks;
 104
 105     /** The amount to shift the address to get the set. */
 106     int setShift;
 107     /** The amount to shift the address to get the tag. */
 108     int tagShift;
 109     /** Mask out all bits that aren't part of the set index. */
 110     unsigned setMask;
 111     /** Mask out all bits that aren't part of the block offset. */
 112     unsigned blkMask;
 113
 114 public:
 115
 116     /** Convenience typedef. */
 117      typedef BaseSetAssocParams Params;
 118
 119     /**
 120      * Construct and initialize this tag store.
 121      */
 122     BaseSetAssoc(const Params *p);
 123
 124     /**
 125      * Destructor
 126      */
 127     virtual ~BaseSetAssoc();
 128
 129     /**
 130      * Find the cache block given set and way
 131      * @param set The set of the block.
 132      * @param way The way of the block.
 133      * @return The cache block.
 134      */
 135     CacheBlk *findBlockBySetAndWay(int set, int way) const override;
 136
 137     /**
 138      * Invalidate the given block.
 139      * @param blk The block to invalidate.
 140      */
 141     void invalidate(CacheBlk *blk) override
 142     {
 143         assert(blk);
 144         assert(blk->isValid());
 145         tagsInUse--;
 146         assert(blk->srcMasterId < cache->system->maxMasters());
 147         occupancies[blk->srcMasterId]--;
 148         blk->srcMasterId = Request::invldMasterId;
 149         blk->task_id = ContextSwitchTaskId::Unknown;
 150         blk->tickInserted = curTick();
 151     }
 152
 153     /**
 154      * Access block and update replacement data. May not succeed, in which case
 155      * nullptr is returned. This has all the implications of a cache
 156      * access and should only be used as such. Returns the access latency as a
 157      * side effect.
 158      * @param addr The address to find.
 159      * @param is_secure True if the target memory space is secure.
 160      * @param asid The address space ID.
 161      * @param lat The access latency.
 162      * @return Pointer to the cache block if found.
 163      */
 164     CacheBlk* accessBlock(Addr addr, bool is_secure, Cycles &lat,
 165                           int context_src) override
 166     {
 167         Addr tag = extractTag(addr);
 168         int set = extractSet(addr);
 169         BlkType *blk = sets[set].findBlk(tag, is_secure);
 170
 171         // Access all tags in parallel, hence one in each way.  The data side
 172         // either accesses all blocks in parallel, or one block sequentially on
 173         // a hit.  Sequential access with a miss doesn't access data.
 174         tagAccesses += allocAssoc;
 175         if (sequentialAccess) {
 176             if (blk != nullptr) {
 177                 dataAccesses += 1;
 178             }
 179         } else {
 180             dataAccesses += allocAssoc;
 181         }
 182
 183         if (blk != nullptr) {
 184             // If a cache hit
 185             lat = accessLatency;
 186             // Check if the block to be accessed is available. If not,
 187             // apply the accessLatency on top of block->whenReady.
 188             if (blk->whenReady > curTick() &&
 189                 cache->ticksToCycles(blk->whenReady - curTick()) >
 190                 accessLatency) {
 191                 lat = cache->ticksToCycles(blk->whenReady - curTick()) +
 192                 accessLatency;
 193             }
 194             blk->refCount += 1;
 195         } else {
 196             // If a cache miss
 197             lat = lookupLatency;
 198         }
 199
 200         return blk;
 201     }
 202
 203     /**
 204      * Finds the given address in the cache, do not update replacement data.
 205      * i.e. This is a no-side-effect find of a block.
 206      * @param addr The address to find.
 207      * @param is_secure True if the target memory space is secure.
 208      * @param asid The address space ID.
 209      * @return Pointer to the cache block if found.
 210      */
 211     CacheBlk* findBlock(Addr addr, bool is_secure) const override;
 212
 213     /**
 214      * Find an invalid block to evict for the address provided.
 215      * If there are no invalid blocks, this will return the block
 216      * in the least-recently-used position.
 217      * @param addr The addr to a find a replacement candidate for.
 218      * @return The candidate block.
 219      */
 220     CacheBlk* findVictim(Addr addr) override
 221     {
 222         BlkType *blk = nullptr;
 223         int set = extractSet(addr);
 224
 225         // prefer to evict an invalid block
 226         for (int i = 0; i < allocAssoc; ++i) {
 227             blk = sets[set].blks[i];
 228             if (!blk->isValid())
 229                 break;
 230         }
 231
 232         return blk;
 233     }
 234
 235     /**
 236      * Insert the new block into the cache.
 237      * @param pkt Packet holding the address to update
 238      * @param blk The block to update.
 239      */
 240      void insertBlock(PacketPtr pkt, CacheBlk *blk) override
 241      {
 242          Addr addr = pkt->getAddr();
 243          MasterID master_id = pkt->req->masterId();
 244          uint32_t task_id = pkt->req->taskId();
 245
 246          if (!blk->isTouched) {
 247              tagsInUse++;
 248              blk->isTouched = true;
 249              if (!warmedUp && tagsInUse.value() >= warmupBound) {
 250                  warmedUp = true;
 251                  warmupCycle = curTick();
 252              }
 253          }
 254
 255          // If we're replacing a block that was previously valid update
 256          // stats for it. This can't be done in findBlock() because a
 257          // found block might not actually be replaced there if the
 258          // coherence protocol says it can't be.
 259          if (blk->isValid()) {
 260              replacements[0]++;
 261              totalRefs += blk->refCount;
 262              ++sampledRefs;
 263              blk->refCount = 0;
 264
 265              // deal with evicted block
 266              assert(blk->srcMasterId < cache->system->maxMasters());
 267              occupancies[blk->srcMasterId]--;
 268
 269              blk->invalidate();
 270          }
 271
 272          blk->isTouched = true;
 273
 274          // Set tag for new block.  Caller is responsible for setting status.
 275          blk->tag = extractTag(addr);
 276
 277          // deal with what we are bringing in
 278          assert(master_id < cache->system->maxMasters());
 279          occupancies[master_id]++;
 280          blk->srcMasterId = master_id;
 281          blk->task_id = task_id;
 282          blk->tickInserted = curTick();
 283
 284          // We only need to write into one tag and one data block.
 285          tagAccesses += 1;
 286          dataAccesses += 1;
 287      }
 288
 289     /**
 290      * Limit the allocation for the cache ways.
 291      * @param ways The maximum number of ways available for replacement.
 292      */
 293     virtual void setWayAllocationMax(int ways) override
 294     {
 295         fatal_if(ways < 1, "Allocation limit must be greater than zero");
 296         allocAssoc = ways;
 297     }
 298
 299     /**
 300      * Get the way allocation mask limit.
 301      * @return The maximum number of ways available for replacement.
 302      */
 303     virtual int getWayAllocationMax() const override
 304     {
 305         return allocAssoc;
 306     }
 307
 308     /**
 309      * Generate the tag from the given address.
 310      * @param addr The address to get the tag from.
 311      * @return The tag of the address.
 312      */
 313     Addr extractTag(Addr addr) const override
 314     {
 315         return (addr >> tagShift);
 316     }
 317
 318     /**
 319      * Calculate the set index from the address.
 320      * @param addr The address to get the set from.
 321      * @return The set index of the address.
 322      */
 323     int extractSet(Addr addr) const override
 324     {
 325         return ((addr >> setShift) & setMask);
 326     }
 327
 328     /**
 329      * Align an address to the block size.
 330      * @param addr the address to align.
 331      * @return The block address.
 332      */
 333     Addr blkAlign(Addr addr) const
 334     {
 335         return (addr & ~(Addr)blkMask);
 336     }
 337
 338     /**
 339      * Regenerate the block address from the tag.
 340      * @param tag The tag of the block.
 341      * @param set The set of the block.
 342      * @return The block address.
 343      */
 344     Addr regenerateBlkAddr(Addr tag, unsigned set) const override
 345     {
 346         return ((tag << tagShift) | ((Addr)set << setShift));
 347     }
 348
 349     /**
 350      * Called at end of simulation to complete average block reference stats.
 351      */
 352     void cleanupRefs() override;
 353
 354     /**
 355      * Print all tags used
 356      */
 357     std::string print() const override;
 358
 359     /**
 360      * Called prior to dumping stats to compute task occupancy
 361      */
 362     void computeStats() override;
 363
 364     /**
 365      * Visit each block in the tag store and apply a visitor to the
 366      * block.
 367      *
 368      * The visitor should be a function (or object that behaves like a
 369      * function) that takes a cache block reference as its parameter
 370      * and returns a bool. A visitor can request the traversal to be
 371      * stopped by returning false, returning true causes it to be
 372      * called for the next block in the tag store.
 373      *
 374      * \param visitor Visitor to call on each block.
 375      */
 376     void forEachBlk(CacheBlkVisitor &visitor) override {
 377         for (unsigned i = 0; i < numSets * assoc; ++i) {
 378             if (!visitor(blks[i]))
 379                 return;
 380         }
 381     }
 382 };
 383
 384 #endif // __MEM_CACHE_TAGS_BASESETASSOC_HH__