src/mem/cache/prefetch/queued.hh

   1 /*
   2  * Copyright (c) 2014-2015 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  * Redistribution and use in source and binary forms, with or without
  15  * modification, are permitted provided that the following conditions are
  16  * met: redistributions of source code must retain the above copyright
  17  * notice, this list of conditions and the following disclaimer;
  18  * redistributions in binary form must reproduce the above copyright
  19  * notice, this list of conditions and the following disclaimer in the
  20  * documentation and/or other materials provided with the distribution;
  21  * neither the name of the copyright holders nor the names of its
  22  * contributors may be used to endorse or promote products derived from
  23  * this software without specific prior written permission.
  24  *
  25  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  26  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  27  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  28  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  29  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  30  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  31  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  32  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  33  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  34  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  35  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  36  */
  37
  38 #ifndef __MEM_CACHE_PREFETCH_QUEUED_HH__
  39 #define __MEM_CACHE_PREFETCH_QUEUED_HH__
  40
  41 #include <cstdint>
  42 #include <list>
  43 #include <utility>
  44
  45 #include "base/statistics.hh"
  46 #include "base/types.hh"
  47 #include "mem/cache/prefetch/base.hh"
  48 #include "mem/packet.hh"
  49
  50 struct QueuedPrefetcherParams;
  51
  52 namespace Prefetcher {
  53
  54 class Queued : public Base
  55 {
  56   protected:
  57     struct DeferredPacket : public BaseTLB::Translation {
  58         /** Owner of the packet */
  59         Queued *owner;
  60         /** Prefetch info corresponding to this packet */
  61         PrefetchInfo pfInfo;
  62         /** Time when this prefetch becomes ready */
  63         Tick tick;
  64         /** The memory packet generated by this prefetch */
  65         PacketPtr pkt;
  66         /** The priority of this prefetch */
  67         int32_t priority;
  68         /** Request used when a translation is needed */
  69         RequestPtr translationRequest;
  70         ThreadContext *tc;
  71         bool ongoingTranslation;
  72
  73         /**
  74          * Constructor
  75          * @param o QueuedPrefetcher in charge of this request
  76          * @param pfi PrefechInfo object associated to this packet
  77          * @param t Time when this prefetch becomes ready
  78          * @param p PacketPtr with the memory request of the prefetch
  79          * @param prio This prefetch priority
  80          */
  81         DeferredPacket(Queued *o, PrefetchInfo const &pfi, Tick t,
  82             int32_t prio) : owner(o), pfInfo(pfi), tick(t), pkt(nullptr),
  83             priority(prio), translationRequest(), tc(nullptr),
  84             ongoingTranslation(false) {
  85         }
  86
  87         bool operator>(const DeferredPacket& that) const
  88         {
  89             return priority > that.priority;
  90         }
  91         bool operator<(const DeferredPacket& that) const
  92         {
  93             return priority < that.priority;
  94         }
  95         bool operator<=(const DeferredPacket& that) const
  96         {
  97             return !(*this > that);
  98         }
  99
 100         /**
 101          * Create the associated memory packet
 102          * @param paddr physical address of this packet
 103          * @param blk_size block size used by the prefetcher
 104          * @param requestor_id Requestor ID of the access that generated
 105          * this prefetch
 106          * @param tag_prefetch flag to indicate if the packet needs to be
 107          *        tagged
 108          * @param t time when the prefetch becomes ready
 109          */
 110         void createPkt(Addr paddr, unsigned blk_size, RequestorID requestor_id,
 111                        bool tag_prefetch, Tick t);
 112
 113         /**
 114          * Sets the translation request needed to obtain the physical address
 115          * of this request.
 116          * @param req The Request with the virtual address of this request
 117          */
 118         void setTranslationRequest(const RequestPtr &req)
 119         {
 120             translationRequest = req;
 121         }
 122
 123         void markDelayed() override
 124         {}
 125
 126         void finish(const Fault &fault, const RequestPtr &req,
 127                             ThreadContext *tc, BaseTLB::Mode mode) override;
 128
 129         /**
 130          * Issues the translation request to the provided TLB
 131          * @param tlb the tlb that has to translate the address
 132          */
 133         void startTranslation(BaseTLB *tlb);
 134     };
 135
 136     std::list<DeferredPacket> pfq;
 137     std::list<DeferredPacket> pfqMissingTranslation;
 138
 139     using const_iterator = std::list<DeferredPacket>::const_iterator;
 140     using iterator = std::list<DeferredPacket>::iterator;
 141
 142     // PARAMETERS
 143
 144     /** Maximum size of the prefetch queue */
 145     const unsigned queueSize;
 146
 147     /**
 148      * Maximum size of the queue holding prefetch requests with missing
 149      * address translations
 150      */
 151     const unsigned missingTranslationQueueSize;
 152
 153     /** Cycles after generation when a prefetch can first be issued */
 154     const Cycles latency;
 155
 156     /** Squash queued prefetch if demand access observed */
 157     const bool queueSquash;
 158
 159     /** Filter prefetches if already queued */
 160     const bool queueFilter;
 161
 162     /** Snoop the cache before generating prefetch (cheating basically) */
 163     const bool cacheSnoop;
 164
 165     /** Tag prefetch with PC of generating access? */
 166     const bool tagPrefetch;
 167
 168     /** Percentage of requests that can be throttled */
 169     const unsigned int throttleControlPct;
 170
 171     struct QueuedStats : public Stats::Group
 172     {
 173         QueuedStats(Stats::Group *parent);
 174         // STATS
 175         Stats::Scalar pfIdentified;
 176         Stats::Scalar pfBufferHit;
 177         Stats::Scalar pfInCache;
 178         Stats::Scalar pfRemovedFull;
 179         Stats::Scalar pfSpanPage;
 180     } statsQueued;
 181   public:
 182     using AddrPriority = std::pair<Addr, int32_t>;
 183
 184     Queued(const QueuedPrefetcherParams *p);
 185     virtual ~Queued();
 186
 187     void notify(const PacketPtr &pkt, const PrefetchInfo &pfi) override;
 188
 189     void insert(const PacketPtr &pkt, PrefetchInfo &new_pfi, int32_t priority);
 190
 191     virtual void calculatePrefetch(const PrefetchInfo &pfi,
 192                                    std::vector<AddrPriority> &addresses) = 0;
 193     PacketPtr getPacket() override;
 194
 195     Tick nextPrefetchReadyTime() const override
 196     {
 197         return pfq.empty() ? MaxTick : pfq.front().tick;
 198     }
 199
 200   private:
 201
 202     /**
 203      * Adds a DeferredPacket to the specified queue
 204      * @param queue selected queue to use
 205      * @param dpp DeferredPacket to add
 206      */
 207     void addToQueue(std::list<DeferredPacket> &queue, DeferredPacket &dpp);
 208
 209     /**
 210      * Starts the translations of the queued prefetches with a
 211      * missing translation. It performs a maximum specified number of
 212      * translations. Successful translations cause the prefetch request to be
 213      * queued in the queue of ready requests.
 214      * @param max maximum number of translations to perform
 215      */
 216     void processMissingTranslations(unsigned max);
 217
 218     /**
 219      * Indicates that the translation of the address of the provided  deferred
 220      * packet has been successfully completed, and it can be enqueued as a
 221      * new prefetch request.
 222      * @param dp the deferred packet that has completed the translation request
 223      * @param failed whether the translation was successful
 224      */
 225     void translationComplete(DeferredPacket *dp, bool failed);
 226
 227     /**
 228      * Checks whether the specified prefetch request is already in the
 229      * specified queue. If the request is found, its priority is updated.
 230      * @param queue selected queue to check
 231      * @param pfi information of the prefetch request to be added
 232      * @param priority priority of the prefetch request to be added
 233      * @return True if the prefetch request was found in the queue
 234      */
 235     bool alreadyInQueue(std::list<DeferredPacket> &queue,
 236                         const PrefetchInfo &pfi, int32_t priority);
 237
 238     /**
 239      * Returns the maxmimum number of prefetch requests that are allowed
 240      * to be created from the number of prefetch candidates provided.
 241      * The behavior of this service is controlled with the throttleControlPct
 242      * parameter.
 243      * @param total number of prefetch candidates generated by the prefetcher
 244      * @return the number of these request candidates are allowed to be created
 245      */
 246     size_t getMaxPermittedPrefetches(size_t total) const;
 247
 248     RequestPtr createPrefetchRequest(Addr addr, PrefetchInfo const &pfi,
 249                                         PacketPtr pkt);
 250 };
 251
 252 } // namespace Prefetcher
 253
 254 #endif //__MEM_CACHE_PREFETCH_QUEUED_HH__
 255