src/mem/cache/cache.hh

   1 /*
   2  * Copyright (c) 2012-2018 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) 2002-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  * Authors: Erik Hallnor
  41  *          Dave Greene
  42  *          Steve Reinhardt
  43  *          Ron Dreslinski
  44  *          Andreas Hansson
  45  */
  46
  47 /**
  48  * @file
  49  * Describes a cache based on template policies.
  50  */
  51
  52 #ifndef __MEM_CACHE_CACHE_HH__
  53 #define __MEM_CACHE_CACHE_HH__
  54
  55 #include <unordered_set>
  56
  57 #include "base/logging.hh" // fatal, panic, and warn
  58 #include "enums/Clusivity.hh"
  59 #include "mem/cache/base.hh"
  60 #include "mem/cache/blk.hh"
  61 #include "mem/cache/mshr.hh"
  62 #include "mem/cache/tags/base.hh"
  63 #include "params/Cache.hh"
  64 #include "sim/eventq.hh"
  65
  66 //Forward decleration
  67 class BasePrefetcher;
  68
  69 /**
  70  * A template-policy based cache. The behavior of the cache can be altered by
  71  * supplying different template policies. TagStore handles all tag and data
  72  * storage @sa TagStore, \ref gem5MemorySystem "gem5 Memory System"
  73  */
  74 class Cache : public BaseCache
  75 {
  76   protected:
  77
  78     /**
  79      * The CPU-side port extends the base cache slave port with access
  80      * functions for functional, atomic and timing requests.
  81      */
  82     class CpuSidePort : public CacheSlavePort
  83     {
  84       private:
  85
  86         // a pointer to our specific cache implementation
  87         Cache *cache;
  88
  89       protected:
  90
  91         virtual bool recvTimingSnoopResp(PacketPtr pkt);
  92
  93         virtual bool tryTiming(PacketPtr pkt);
  94
  95         virtual bool recvTimingReq(PacketPtr pkt);
  96
  97         virtual Tick recvAtomic(PacketPtr pkt);
  98
  99         virtual void recvFunctional(PacketPtr pkt);
 100
 101         virtual AddrRangeList getAddrRanges() const;
 102
 103       public:
 104
 105         CpuSidePort(const std::string &_name, Cache *_cache,
 106                     const std::string &_label);
 107
 108     };
 109
 110     /**
 111      * Override the default behaviour of sendDeferredPacket to enable
 112      * the memory-side cache port to also send requests based on the
 113      * current MSHR status. This queue has a pointer to our specific
 114      * cache implementation and is used by the MemSidePort.
 115      */
 116     class CacheReqPacketQueue : public ReqPacketQueue
 117     {
 118
 119       protected:
 120
 121         Cache &cache;
 122         SnoopRespPacketQueue &snoopRespQueue;
 123
 124       public:
 125
 126         CacheReqPacketQueue(Cache &cache, MasterPort &port,
 127                             SnoopRespPacketQueue &snoop_resp_queue,
 128                             const std::string &label) :
 129             ReqPacketQueue(cache, port, label), cache(cache),
 130             snoopRespQueue(snoop_resp_queue) { }
 131
 132         /**
 133          * Override the normal sendDeferredPacket and do not only
 134          * consider the transmit list (used for responses), but also
 135          * requests.
 136          */
 137         virtual void sendDeferredPacket();
 138
 139         /**
 140          * Check if there is a conflicting snoop response about to be
 141          * send out, and if so simply stall any requests, and schedule
 142          * a send event at the same time as the next snoop response is
 143          * being sent out.
 144          */
 145         bool checkConflictingSnoop(Addr addr)
 146         {
 147             if (snoopRespQueue.hasAddr(addr)) {
 148                 DPRINTF(CachePort, "Waiting for snoop response to be "
 149                         "sent\n");
 150                 Tick when = snoopRespQueue.deferredPacketReadyTime();
 151                 schedSendEvent(when);
 152                 return true;
 153             }
 154             return false;
 155         }
 156     };
 157
 158     /**
 159      * The memory-side port extends the base cache master port with
 160      * access functions for functional, atomic and timing snoops.
 161      */
 162     class MemSidePort : public CacheMasterPort
 163     {
 164       private:
 165
 166         /** The cache-specific queue. */
 167         CacheReqPacketQueue _reqQueue;
 168
 169         SnoopRespPacketQueue _snoopRespQueue;
 170
 171         // a pointer to our specific cache implementation
 172         Cache *cache;
 173
 174       protected:
 175
 176         virtual void recvTimingSnoopReq(PacketPtr pkt);
 177
 178         virtual bool recvTimingResp(PacketPtr pkt);
 179
 180         virtual Tick recvAtomicSnoop(PacketPtr pkt);
 181
 182         virtual void recvFunctionalSnoop(PacketPtr pkt);
 183
 184       public:
 185
 186         MemSidePort(const std::string &_name, Cache *_cache,
 187                     const std::string &_label);
 188     };
 189
 190     /** Tag and data Storage */
 191     BaseTags *tags;
 192
 193     /** Prefetcher */
 194     BasePrefetcher *prefetcher;
 195
 196     /** Temporary cache block for occasional transitory use */
 197     CacheBlk *tempBlock;
 198
 199     /**
 200      * This cache should allocate a block on a line-sized write miss.
 201      */
 202     const bool doFastWrites;
 203
 204     /**
 205      * Turn line-sized writes into WriteInvalidate transactions.
 206      */
 207     void promoteWholeLineWrites(PacketPtr pkt);
 208
 209     /**
 210      * Notify the prefetcher on every access, not just misses.
 211      */
 212     const bool prefetchOnAccess;
 213
 214      /**
 215      * Clusivity with respect to the upstream cache, determining if we
 216      * fill into both this cache and the cache above on a miss. Note
 217      * that we currently do not support strict clusivity policies.
 218      */
 219     const Enums::Clusivity clusivity;
 220
 221      /**
 222      * Determine if clean lines should be written back or not. In
 223      * cases where a downstream cache is mostly inclusive we likely
 224      * want it to act as a victim cache also for lines that have not
 225      * been modified. Hence, we cannot simply drop the line (or send a
 226      * clean evict), but rather need to send the actual data.
 227      */
 228     const bool writebackClean;
 229
 230     /**
 231      * Upstream caches need this packet until true is returned, so
 232      * hold it for deletion until a subsequent call
 233      */
 234     std::unique_ptr<Packet> pendingDelete;
 235
 236     /**
 237      * Writebacks from the tempBlock, resulting on the response path
 238      * in atomic mode, must happen after the call to recvAtomic has
 239      * finished (for the right ordering of the packets). We therefore
 240      * need to hold on to the packets, and have a method and an event
 241      * to send them.
 242      */
 243     PacketPtr tempBlockWriteback;
 244
 245     /**
 246      * Send the outstanding tempBlock writeback. To be called after
 247      * recvAtomic finishes in cases where the block we filled is in
 248      * fact the tempBlock, and now needs to be written back.
 249      */
 250     void writebackTempBlockAtomic() {
 251         assert(tempBlockWriteback != nullptr);
 252         PacketList writebacks{tempBlockWriteback};
 253         doWritebacksAtomic(writebacks);
 254         tempBlockWriteback = nullptr;
 255     }
 256
 257     /**
 258      * An event to writeback the tempBlock after recvAtomic
 259      * finishes. To avoid other calls to recvAtomic getting in
 260      * between, we create this event with a higher priority.
 261      */
 262     EventFunctionWrapper writebackTempBlockAtomicEvent;
 263
 264     /**
 265      * Store the outstanding requests that we are expecting snoop
 266      * responses from so we can determine which snoop responses we
 267      * generated and which ones were merely forwarded.
 268      */
 269     std::unordered_set<RequestPtr> outstandingSnoop;
 270
 271     /**
 272      * Does all the processing necessary to perform the provided request.
 273      * @param pkt The memory request to perform.
 274      * @param blk The cache block to be updated.
 275      * @param lat The latency of the access.
 276      * @param writebacks List for any writebacks that need to be performed.
 277      * @return Boolean indicating whether the request was satisfied.
 278      */
 279     bool access(PacketPtr pkt, CacheBlk *&blk,
 280                 Cycles &lat, PacketList &writebacks);
 281
 282     /**
 283      *Handle doing the Compare and Swap function for SPARC.
 284      */
 285     void cmpAndSwap(CacheBlk *blk, PacketPtr pkt);
 286
 287     /**
 288      * Find a block frame for new block at address addr targeting the
 289      * given security space, assuming that the block is not currently
 290      * in the cache.  Append writebacks if any to provided packet
 291      * list.  Return free block frame.  May return nullptr if there are
 292      * no replaceable blocks at the moment.
 293      */
 294     CacheBlk *allocateBlock(Addr addr, bool is_secure, PacketList &writebacks);
 295
 296     /**
 297      * Invalidate a cache block.
 298      *
 299      * @param blk Block to invalidate
 300      */
 301     void invalidateBlock(CacheBlk *blk);
 302
 303     /**
 304      * Maintain the clusivity of this cache by potentially
 305      * invalidating a block. This method works in conjunction with
 306      * satisfyRequest, but is separate to allow us to handle all MSHR
 307      * targets before potentially dropping a block.
 308      *
 309      * @param from_cache Whether we have dealt with a packet from a cache
 310      * @param blk The block that should potentially be dropped
 311      */
 312     void maintainClusivity(bool from_cache, CacheBlk *blk);
 313
 314     /**
 315      * Populates a cache block and handles all outstanding requests for the
 316      * satisfied fill request. This version takes two memory requests. One
 317      * contains the fill data, the other is an optional target to satisfy.
 318      * @param pkt The memory request with the fill data.
 319      * @param blk The cache block if it already exists.
 320      * @param writebacks List for any writebacks that need to be performed.
 321      * @param allocate Whether to allocate a block or use the temp block
 322      * @return Pointer to the new cache block.
 323      */
 324     CacheBlk *handleFill(PacketPtr pkt, CacheBlk *blk,
 325                          PacketList &writebacks, bool allocate);
 326
 327     /**
 328      * Determine whether we should allocate on a fill or not. If this
 329      * cache is mostly inclusive with regards to the upstream cache(s)
 330      * we always allocate (for any non-forwarded and cacheable
 331      * requests). In the case of a mostly exclusive cache, we allocate
 332      * on fill if the packet did not come from a cache, thus if we:
 333      * are dealing with a whole-line write (the latter behaves much
 334      * like a writeback), the original target packet came from a
 335      * non-caching source, or if we are performing a prefetch or LLSC.
 336      *
 337      * @param cmd Command of the incoming requesting packet
 338      * @return Whether we should allocate on the fill
 339      */
 340     inline bool allocOnFill(MemCmd cmd) const override
 341     {
 342         return clusivity == Enums::mostly_incl ||
 343             cmd == MemCmd::WriteLineReq ||
 344             cmd == MemCmd::ReadReq ||
 345             cmd == MemCmd::WriteReq ||
 346             cmd.isPrefetch() ||
 347             cmd.isLLSC();
 348     }
 349
 350     /*
 351      * Handle a timing request that hit in the cache
 352      *
 353      * @param ptk The request packet
 354      * @param blk The referenced block
 355      * @param request_time The tick at which the block lookup is compete
 356      */
 357     void handleTimingReqHit(PacketPtr pkt, CacheBlk *blk, Tick request_time);
 358
 359     /*
 360      * Handle a timing request that missed in the cache
 361      *
 362      * @param ptk The request packet
 363      * @param blk The referenced block
 364      * @param forward_time The tick at which we can process dependent requests
 365      * @param request_time The tick at which the block lookup is compete
 366      */
 367     void handleTimingReqMiss(PacketPtr pkt, CacheBlk *blk, Tick forward_time,
 368                              Tick request_time);
 369
 370     /**
 371      * Performs the access specified by the request.
 372      * @param pkt The request to perform.
 373      */
 374     void recvTimingReq(PacketPtr pkt);
 375
 376     /**
 377      * Insert writebacks into the write buffer
 378      */
 379     void doWritebacks(PacketList& writebacks, Tick forward_time);
 380
 381     /**
 382      * Send writebacks down the memory hierarchy in atomic mode
 383      */
 384     void doWritebacksAtomic(PacketList& writebacks);
 385
 386     /**
 387      * Handling the special case of uncacheable write responses to
 388      * make recvTimingResp less cluttered.
 389      */
 390     void handleUncacheableWriteResp(PacketPtr pkt);
 391
 392     /**
 393      * Service non-deferred MSHR targets using the received response
 394      *
 395      * Iterates through the list of targets that can be serviced with
 396      * the current response. Any writebacks that need to performed
 397      * must be appended to the writebacks parameter.
 398      *
 399      * @param mshr The MSHR that corresponds to the reponse
 400      * @param pkt The response packet
 401      * @param blk The reference block
 402      * @param writebacks List of writebacks that need to be performed
 403      */
 404     void serviceMSHRTargets(MSHR *mshr, const PacketPtr pkt, CacheBlk *blk,
 405                             PacketList& writebacks);
 406
 407     /**
 408      * Handles a response (cache line fill/write ack) from the bus.
 409      * @param pkt The response packet
 410      */
 411     void recvTimingResp(PacketPtr pkt);
 412
 413     /**
 414      * Snoops bus transactions to maintain coherence.
 415      * @param pkt The current bus transaction.
 416      */
 417     void recvTimingSnoopReq(PacketPtr pkt);
 418
 419     /**
 420      * Handle a snoop response.
 421      * @param pkt Snoop response packet
 422      */
 423     void recvTimingSnoopResp(PacketPtr pkt);
 424
 425     /**
 426      * Performs the access specified by the request.
 427      * @param pkt The request to perform.
 428      * @return The number of ticks required for the access.
 429      */
 430     Tick recvAtomic(PacketPtr pkt);
 431
 432     /**
 433      * Snoop for the provided request in the cache and return the estimated
 434      * time taken.
 435      * @param pkt The memory request to snoop
 436      * @return The number of ticks required for the snoop.
 437      */
 438     Tick recvAtomicSnoop(PacketPtr pkt);
 439
 440     /**
 441      * Performs the access specified by the request.
 442      * @param pkt The request to perform.
 443      * @param fromCpuSide from the CPU side port or the memory side port
 444      */
 445     void functionalAccess(PacketPtr pkt, bool fromCpuSide);
 446
 447     /**
 448      * Perform any necessary updates to the block and perform any data
 449      * exchange between the packet and the block. The flags of the
 450      * packet are also set accordingly.
 451      *
 452      * @param pkt Request packet from upstream that hit a block
 453      * @param blk Cache block that the packet hit
 454      * @param deferred_response Whether this hit is to block that
 455      *                          originally missed
 456      * @param pending_downgrade Whether the writable flag is to be removed
 457      *
 458      * @return True if the block is to be invalidated
 459      */
 460     void satisfyRequest(PacketPtr pkt, CacheBlk *blk,
 461                         bool deferred_response = false,
 462                         bool pending_downgrade = false);
 463
 464     void doTimingSupplyResponse(PacketPtr req_pkt, const uint8_t *blk_data,
 465                                 bool already_copied, bool pending_inval);
 466
 467     /**
 468      * Perform an upward snoop if needed, and update the block state
 469      * (possibly invalidating the block). Also create a response if required.
 470      *
 471      * @param pkt Snoop packet
 472      * @param blk Cache block being snooped
 473      * @param is_timing Timing or atomic for the response
 474      * @param is_deferred Is this a deferred snoop or not?
 475      * @param pending_inval Do we have a pending invalidation?
 476      *
 477      * @return The snoop delay incurred by the upwards snoop
 478      */
 479     uint32_t handleSnoop(PacketPtr pkt, CacheBlk *blk,
 480                          bool is_timing, bool is_deferred, bool pending_inval);
 481
 482     /**
 483      * Create a writeback request for the given block.
 484      * @param blk The block to writeback.
 485      * @return The writeback request for the block.
 486      */
 487     PacketPtr writebackBlk(CacheBlk *blk);
 488
 489     /**
 490      * Create a writeclean request for the given block.
 491      * @param blk The block to write clean
 492      * @param dest The destination of this clean operation
 493      * @return The write clean packet for the block.
 494      */
 495     PacketPtr writecleanBlk(CacheBlk *blk, Request::Flags dest, PacketId id);
 496
 497     /**
 498      * Create a CleanEvict request for the given block.
 499      * @param blk The block to evict.
 500      * @return The CleanEvict request for the block.
 501      */
 502     PacketPtr cleanEvictBlk(CacheBlk *blk);
 503
 504
 505     void memWriteback() override;
 506     void memInvalidate() override;
 507     bool isDirty() const override;
 508
 509     /**
 510      * Cache block visitor that writes back dirty cache blocks using
 511      * functional writes.
 512      *
 513      * \return Always returns true.
 514      */
 515     bool writebackVisitor(CacheBlk &blk);
 516     /**
 517      * Cache block visitor that invalidates all blocks in the cache.
 518      *
 519      * @warn Dirty cache lines will not be written back to memory.
 520      *
 521      * \return Always returns true.
 522      */
 523     bool invalidateVisitor(CacheBlk &blk);
 524
 525     /**
 526      * Create an appropriate downstream bus request packet for the
 527      * given parameters.
 528      * @param cpu_pkt  The miss that needs to be satisfied.
 529      * @param blk The block currently in the cache corresponding to
 530      * cpu_pkt (nullptr if none).
 531      * @param needsWritable Indicates that the block must be writable
 532      * even if the request in cpu_pkt doesn't indicate that.
 533      * @return A new Packet containing the request, or nullptr if the
 534      * current request in cpu_pkt should just be forwarded on.
 535      */
 536     PacketPtr createMissPacket(PacketPtr cpu_pkt, CacheBlk *blk,
 537                                bool needsWritable) const;
 538
 539     /**
 540      * Return the next queue entry to service, either a pending miss
 541      * from the MSHR queue, a buffered write from the write buffer, or
 542      * something from the prefetcher. This function is responsible
 543      * for prioritizing among those sources on the fly.
 544      */
 545     QueueEntry* getNextQueueEntry();
 546
 547     /**
 548      * Send up a snoop request and find cached copies. If cached copies are
 549      * found, set the BLOCK_CACHED flag in pkt.
 550      */
 551     bool isCachedAbove(PacketPtr pkt, bool is_timing = true) const;
 552
 553     /**
 554      * Return whether there are any outstanding misses.
 555      */
 556     bool outstandingMisses() const
 557     {
 558         return !mshrQueue.isEmpty();
 559     }
 560
 561     CacheBlk *findBlock(Addr addr, bool is_secure) const {
 562         return tags->findBlock(addr, is_secure);
 563     }
 564
 565     bool inCache(Addr addr, bool is_secure) const override {
 566         return (tags->findBlock(addr, is_secure) != 0);
 567     }
 568
 569     bool inMissQueue(Addr addr, bool is_secure) const override {
 570         return (mshrQueue.findMatch(addr, is_secure) != 0);
 571     }
 572
 573     /**
 574      * Find next request ready time from among possible sources.
 575      */
 576     Tick nextQueueReadyTime() const;
 577
 578   public:
 579     /** Instantiates a basic cache object. */
 580     Cache(const CacheParams *p);
 581
 582     /** Non-default destructor is needed to deallocate memory. */
 583     virtual ~Cache();
 584
 585     void regStats() override;
 586
 587     /**
 588      * Take an MSHR, turn it into a suitable downstream packet, and
 589      * send it out. This construct allows a queue entry to choose a suitable
 590      * approach based on its type.
 591      *
 592      * @param mshr The MSHR to turn into a packet and send
 593      * @return True if the port is waiting for a retry
 594      */
 595     bool sendMSHRQueuePacket(MSHR* mshr);
 596
 597     /**
 598      * Similar to sendMSHR, but for a write-queue entry
 599      * instead. Create the packet, and send it, and if successful also
 600      * mark the entry in service.
 601      *
 602      * @param wq_entry The write-queue entry to turn into a packet and send
 603      * @return True if the port is waiting for a retry
 604      */
 605     bool sendWriteQueuePacket(WriteQueueEntry* wq_entry);
 606
 607     /** serialize the state of the caches
 608      * We currently don't support checkpointing cache state, so this panics.
 609      */
 610     void serialize(CheckpointOut &cp) const override;
 611     void unserialize(CheckpointIn &cp) override;
 612 };
 613
 614 /**
 615  * Wrap a method and present it as a cache block visitor.
 616  *
 617  * For example the forEachBlk method in the tag arrays expects a
 618  * callable object/function as their parameter. This class wraps a
 619  * method in an object and presents  callable object that adheres to
 620  * the cache block visitor protocol.
 621  */
 622 class CacheBlkVisitorWrapper : public CacheBlkVisitor
 623 {
 624   public:
 625     typedef bool (Cache::*VisitorPtr)(CacheBlk &blk);
 626
 627     CacheBlkVisitorWrapper(Cache &_cache, VisitorPtr _visitor)
 628         : cache(_cache), visitor(_visitor) {}
 629
 630     bool operator()(CacheBlk &blk) override {
 631         return (cache.*visitor)(blk);
 632     }
 633
 634   private:
 635     Cache &cache;
 636     VisitorPtr visitor;
 637 };
 638
 639 /**
 640  * Cache block visitor that determines if there are dirty blocks in a
 641  * cache.
 642  *
 643  * Use with the forEachBlk method in the tag array to determine if the
 644  * array contains dirty blocks.
 645  */
 646 class CacheBlkIsDirtyVisitor : public CacheBlkVisitor
 647 {
 648   public:
 649     CacheBlkIsDirtyVisitor()
 650         : _isDirty(false) {}
 651
 652     bool operator()(CacheBlk &blk) override {
 653         if (blk.isDirty()) {
 654             _isDirty = true;
 655             return false;
 656         } else {
 657             return true;
 658         }
 659     }
 660
 661     /**
 662      * Does the array contain a dirty line?
 663      *
 664      * \return true if yes, false otherwise.
 665      */
 666     bool isDirty() const { return _isDirty; };
 667
 668   private:
 669     bool _isDirty;
 670 };
 671
 672 #endif // __MEM_CACHE_CACHE_HH__