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 mid Requester ID of the access that generated this prefetch
 105          * @param tag_prefetch flag to indicate if the packet needs to be
 106          *        tagged
 107          * @param t time when the prefetch becomes ready
 108          */
 109         void createPkt(Addr paddr, unsigned blk_size, MasterID mid,
 110                        bool tag_prefetch, Tick t);
 111
 112         /**
 113          * Sets the translation request needed to obtain the physical address
 114          * of this request.
 115          * @param req The Request with the virtual address of this request
 116          */
 117         void setTranslationRequest(const RequestPtr &req)
 118         {
 119             translationRequest = req;
 120         }
 121
 122         void markDelayed() override
 123         {}
 124
 125         void finish(const Fault &fault, const RequestPtr &req,
 126                             ThreadContext *tc, BaseTLB::Mode mode) override;
 127
 128         /**
 129          * Issues the translation request to the provided TLB
 130          * @param tlb the tlb that has to translate the address
 131          */
 132         void startTranslation(BaseTLB *tlb);
 133     };
 134
 135     std::list<DeferredPacket> pfq;
 136     std::list<DeferredPacket> pfqMissingTranslation;
 137
 138     using const_iterator = std::list<DeferredPacket>::const_iterator;
 139     using iterator = std::list<DeferredPacket>::iterator;
 140
 141     // PARAMETERS
 142
 143     /** Maximum size of the prefetch queue */
 144     const unsigned queueSize;
 145
 146     /**
 147      * Maximum size of the queue holding prefetch requests with missing
 148      * address translations
 149      */
 150     const unsigned missingTranslationQueueSize;
 151
 152     /** Cycles after generation when a prefetch can first be issued */
 153     const Cycles latency;
 154
 155     /** Squash queued prefetch if demand access observed */
 156     const bool queueSquash;
 157
 158     /** Filter prefetches if already queued */
 159     const bool queueFilter;
 160
 161     /** Snoop the cache before generating prefetch (cheating basically) */
 162     const bool cacheSnoop;
 163
 164     /** Tag prefetch with PC of generating access? */
 165     const bool tagPrefetch;
 166
 167     /** Percentage of requests that can be throttled */
 168     const unsigned int throttleControlPct;
 169
 170     struct QueuedStats : public Stats::Group
 171     {
 172         QueuedStats(Stats::Group *parent);
 173         // STATS
 174         Stats::Scalar pfIdentified;
 175         Stats::Scalar pfBufferHit;
 176         Stats::Scalar pfInCache;
 177         Stats::Scalar pfRemovedFull;
 178         Stats::Scalar pfSpanPage;
 179     } statsQueued;
 180   public:
 181     using AddrPriority = std::pair<Addr, int32_t>;
 182
 183     Queued(const QueuedPrefetcherParams *p);
 184     virtual ~Queued();
 185
 186     void notify(const PacketPtr &pkt, const PrefetchInfo &pfi) override;
 187
 188     void insert(const PacketPtr &pkt, PrefetchInfo &new_pfi, int32_t priority);
 189
 190     virtual void calculatePrefetch(const PrefetchInfo &pfi,
 191                                    std::vector<AddrPriority> &addresses) = 0;
 192     PacketPtr getPacket() override;
 193
 194     Tick nextPrefetchReadyTime() const override
 195     {
 196         return pfq.empty() ? MaxTick : pfq.front().tick;
 197     }
 198
 199   private:
 200
 201     /**
 202      * Adds a DeferredPacket to the specified queue
 203      * @param queue selected queue to use
 204      * @param dpp DeferredPacket to add
 205      */
 206     void addToQueue(std::list<DeferredPacket> &queue, DeferredPacket &dpp);
 207
 208     /**
 209      * Starts the translations of the queued prefetches with a
 210      * missing translation. It performs a maximum specified number of
 211      * translations. Successful translations cause the prefetch request to be
 212      * queued in the queue of ready requests.
 213      * @param max maximum number of translations to perform
 214      */
 215     void processMissingTranslations(unsigned max);
 216
 217     /**
 218      * Indicates that the translation of the address of the provided  deferred
 219      * packet has been successfully completed, and it can be enqueued as a
 220      * new prefetch request.
 221      * @param dp the deferred packet that has completed the translation request
 222      * @param failed whether the translation was successful
 223      */
 224     void translationComplete(DeferredPacket *dp, bool failed);
 225
 226     /**
 227      * Checks whether the specified prefetch request is already in the
 228      * specified queue. If the request is found, its priority is updated.
 229      * @param queue selected queue to check
 230      * @param pfi information of the prefetch request to be added
 231      * @param priority priority of the prefetch request to be added
 232      * @return True if the prefetch request was found in the queue
 233      */
 234     bool alreadyInQueue(std::list<DeferredPacket> &queue,
 235                         const PrefetchInfo &pfi, int32_t priority);
 236
 237     /**
 238      * Returns the maxmimum number of prefetch requests that are allowed
 239      * to be created from the number of prefetch candidates provided.
 240      * The behavior of this service is controlled with the throttleControlPct
 241      * parameter.
 242      * @param total number of prefetch candidates generated by the prefetcher
 243      * @return the number of these request candidates are allowed to be created
 244      */
 245     size_t getMaxPermittedPrefetches(size_t total) const;
 246
 247     RequestPtr createPrefetchRequest(Addr addr, PrefetchInfo const &pfi,
 248                                         PacketPtr pkt);
 249 };
 250
 251 } // namespace Prefetcher
 252
 253 #endif //__MEM_CACHE_PREFETCH_QUEUED_HH__
 254