src/mem/cache/tags/base.hh

   1 /*
   2  * Copyright (c) 2012-2014,2016-2019 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 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
  41 /**
  42  * @file
  43  * Declaration of a common base class for cache tagstore objects.
  44  */
  45
  46 #ifndef __MEM_CACHE_TAGS_BASE_HH__
  47 #define __MEM_CACHE_TAGS_BASE_HH__
  48
  49 #include <cassert>
  50 #include <cstdint>
  51 #include <functional>
  52 #include <string>
  53
  54 #include "base/callback.hh"
  55 #include "base/logging.hh"
  56 #include "base/statistics.hh"
  57 #include "base/types.hh"
  58 #include "mem/cache/cache_blk.hh"
  59 #include "mem/packet.hh"
  60 #include "params/BaseTags.hh"
  61 #include "sim/clocked_object.hh"
  62
  63 class System;
  64 class IndexingPolicy;
  65 class ReplaceableEntry;
  66
  67 /**
  68  * A common base class of Cache tagstore objects.
  69  */
  70 class BaseTags : public ClockedObject
  71 {
  72   protected:
  73     /** The block size of the cache. */
  74     const unsigned blkSize;
  75     /** Mask out all bits that aren't part of the block offset. */
  76     const Addr blkMask;
  77     /** The size of the cache. */
  78     const unsigned size;
  79     /** The tag lookup latency of the cache. */
  80     const Cycles lookupLatency;
  81
  82     /** System we are currently operating in. */
  83     System *system;
  84
  85     /** Indexing policy */
  86     BaseIndexingPolicy *indexingPolicy;
  87
  88     /**
  89      * The number of tags that need to be touched to meet the warmup
  90      * percentage.
  91      */
  92     const unsigned warmupBound;
  93     /** Marked true when the cache is warmed up. */
  94     bool warmedUp;
  95
  96     /** the number of blocks in the cache */
  97     const unsigned numBlocks;
  98
  99     /** The data blocks, 1 per cache block. */
 100     std::unique_ptr<uint8_t[]> dataBlks;
 101
 102     /**
 103      * TODO: It would be good if these stats were acquired after warmup.
 104      */
 105     struct BaseTagStats : public Stats::Group
 106     {
 107         BaseTagStats(BaseTags &tags);
 108
 109         void regStats() override;
 110         void preDumpStats() override;
 111
 112         BaseTags &tags;
 113
 114         /** Per cycle average of the number of tags that hold valid data. */
 115         Stats::Average tagsInUse;
 116
 117         /** The total number of references to a block before it is replaced. */
 118         Stats::Scalar totalRefs;
 119
 120         /**
 121          * The number of reference counts sampled. This is different
 122          * from replacements because we sample all the valid blocks
 123          * when the simulator exits.
 124          */
 125         Stats::Scalar sampledRefs;
 126
 127         /**
 128          * Average number of references to a block before is was replaced.
 129          * @todo This should change to an average stat once we have them.
 130          */
 131         Stats::Formula avgRefs;
 132
 133         /** The cycle that the warmup percentage was hit. 0 on failure. */
 134         Stats::Scalar warmupCycle;
 135
 136         /** Average occupancy of each requestor using the cache */
 137         Stats::AverageVector occupancies;
 138
 139         /** Average occ % of each requestor using the cache */
 140         Stats::Formula avgOccs;
 141
 142         /** Occupancy of each context/cpu using the cache */
 143         Stats::Vector occupanciesTaskId;
 144
 145         /** Occupancy of each context/cpu using the cache */
 146         Stats::Vector2d ageTaskId;
 147
 148         /** Occ % of each context/cpu using the cache */
 149         Stats::Formula percentOccsTaskId;
 150
 151         /** Number of tags consulted over all accesses. */
 152         Stats::Scalar tagAccesses;
 153         /** Number of data blocks consulted over all accesses. */
 154         Stats::Scalar dataAccesses;
 155     } stats;
 156
 157   public:
 158     typedef BaseTagsParams Params;
 159     BaseTags(const Params &p);
 160
 161     /**
 162      * Destructor.
 163      */
 164     virtual ~BaseTags() {}
 165
 166     /**
 167      * Initialize blocks. Must be overriden by every subclass that uses
 168      * a block type different from its parent's, as the current Python
 169      * code generation does not allow templates.
 170      */
 171     virtual void tagsInit() = 0;
 172
 173     /**
 174      * Average in the reference count for valid blocks when the simulation
 175      * exits.
 176      */
 177     void cleanupRefs();
 178
 179     /**
 180      * Computes stats just prior to dump event
 181      */
 182     void computeStats();
 183
 184     /**
 185      * Print all tags used
 186      */
 187     std::string print();
 188
 189     /**
 190      * Finds the block in the cache without touching it.
 191      *
 192      * @param addr The address to look for.
 193      * @param is_secure True if the target memory space is secure.
 194      * @return Pointer to the cache block.
 195      */
 196     virtual CacheBlk *findBlock(Addr addr, bool is_secure) const;
 197
 198     /**
 199      * Find a block given set and way.
 200      *
 201      * @param set The set of the block.
 202      * @param way The way of the block.
 203      * @return The block.
 204      */
 205     virtual ReplaceableEntry* findBlockBySetAndWay(int set, int way) const;
 206
 207     /**
 208      * Align an address to the block size.
 209      * @param addr the address to align.
 210      * @return The block address.
 211      */
 212     Addr blkAlign(Addr addr) const
 213     {
 214         return addr & ~blkMask;
 215     }
 216
 217     /**
 218      * Calculate the block offset of an address.
 219      * @param addr the address to get the offset of.
 220      * @return the block offset.
 221      */
 222     int extractBlkOffset(Addr addr) const
 223     {
 224         return (addr & blkMask);
 225     }
 226
 227     /**
 228      * Limit the allocation for the cache ways.
 229      * @param ways The maximum number of ways available for replacement.
 230      */
 231     virtual void setWayAllocationMax(int ways)
 232     {
 233         panic("This tag class does not implement way allocation limit!\n");
 234     }
 235
 236     /**
 237      * Get the way allocation mask limit.
 238      * @return The maximum number of ways available for replacement.
 239      */
 240     virtual int getWayAllocationMax() const
 241     {
 242         panic("This tag class does not implement way allocation limit!\n");
 243         return -1;
 244     }
 245
 246     /**
 247      * This function updates the tags when a block is invalidated
 248      *
 249      * @param blk A valid block to invalidate.
 250      */
 251     virtual void invalidate(CacheBlk *blk)
 252     {
 253         assert(blk);
 254         assert(blk->isValid());
 255
 256         stats.occupancies[blk->getSrcRequestorId()]--;
 257         stats.totalRefs += blk->getRefCount();
 258         stats.sampledRefs++;
 259
 260         blk->invalidate();
 261     }
 262
 263     /**
 264      * Find replacement victim based on address. If the address requires
 265      * blocks to be evicted, their locations are listed for eviction. If a
 266      * conventional cache is being used, the list only contains the victim.
 267      * However, if using sector or compressed caches, the victim is one of
 268      * the blocks to be evicted, but its location is the only one that will
 269      * be assigned to the newly allocated block associated to this address.
 270      * @sa insertBlock
 271      *
 272      * @param addr Address to find a victim for.
 273      * @param is_secure True if the target memory space is secure.
 274      * @param size Size, in bits, of new block to allocate.
 275      * @param evict_blks Cache blocks to be evicted.
 276      * @return Cache block to be replaced.
 277      */
 278     virtual CacheBlk* findVictim(Addr addr, const bool is_secure,
 279                                  const std::size_t size,
 280                                  std::vector<CacheBlk*>& evict_blks) = 0;
 281
 282     /**
 283      * Access block and update replacement data. May not succeed, in which case
 284      * nullptr is returned. This has all the implications of a cache access and
 285      * should only be used as such. Returns the tag lookup latency as a side
 286      * effect.
 287      *
 288      * @param addr The address to find.
 289      * @param is_secure True if the target memory space is secure.
 290      * @param lat The latency of the tag lookup.
 291      * @return Pointer to the cache block if found.
 292      */
 293     virtual CacheBlk* accessBlock(Addr addr, bool is_secure, Cycles &lat) = 0;
 294
 295     /**
 296      * Generate the tag from the given address.
 297      *
 298      * @param addr The address to get the tag from.
 299      * @return The tag of the address.
 300      */
 301     virtual Addr extractTag(const Addr addr) const;
 302
 303     /**
 304      * Insert the new block into the cache and update stats.
 305      *
 306      * @param pkt Packet holding the address to update
 307      * @param blk The block to update.
 308      */
 309     virtual void insertBlock(const PacketPtr pkt, CacheBlk *blk);
 310
 311     /**
 312      * Move a block's metadata to another location decided by the replacement
 313      * policy. It behaves as a swap, however, since the destination block
 314      * should be invalid, the result is a move.
 315      *
 316      * @param src_blk The source block.
 317      * @param dest_blk The destination block. Must be invalid.
 318      */
 319     virtual void moveBlock(CacheBlk *src_blk, CacheBlk *dest_blk);
 320
 321     /**
 322      * Regenerate the block address.
 323      *
 324      * @param block The block.
 325      * @return the block address.
 326      */
 327     virtual Addr regenerateBlkAddr(const CacheBlk* blk) const = 0;
 328
 329     /**
 330      * Visit each block in the tags and apply a visitor
 331      *
 332      * The visitor should be a std::function that takes a cache block
 333      * reference as its parameter.
 334      *
 335      * @param visitor Visitor to call on each block.
 336      */
 337     virtual void forEachBlk(std::function<void(CacheBlk &)> visitor) = 0;
 338
 339     /**
 340      * Find if any of the blocks satisfies a condition
 341      *
 342      * The visitor should be a std::function that takes a cache block
 343      * reference as its parameter. The visitor will terminate the
 344      * traversal early if the condition is satisfied.
 345      *
 346      * @param visitor Visitor to call on each block.
 347      */
 348     virtual bool anyBlk(std::function<bool(CacheBlk &)> visitor) = 0;
 349
 350   private:
 351     /**
 352      * Update the reference stats using data from the input block
 353      *
 354      * @param blk The input block
 355      */
 356     void cleanupRefsVisitor(CacheBlk &blk);
 357
 358     /**
 359      * Update the occupancy and age stats using data from the input block
 360      *
 361      * @param blk The input block
 362      */
 363     void computeStatsVisitor(CacheBlk &blk);
 364 };
 365
 366 #endif //__MEM_CACHE_TAGS_BASE_HH__