src/mem/snoop_filter.hh

   1 /*
   2  * Copyright (c) 2013-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  * 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 /**
  39  * @file
  40  * Definition of a snoop filter.
  41  */
  42
  43 #ifndef __MEM_SNOOP_FILTER_HH__
  44 #define __MEM_SNOOP_FILTER_HH__
  45
  46 #include <bitset>
  47 #include <unordered_map>
  48 #include <utility>
  49
  50 #include "mem/packet.hh"
  51 #include "mem/port.hh"
  52 #include "mem/qport.hh"
  53 #include "params/SnoopFilter.hh"
  54 #include "sim/sim_object.hh"
  55 #include "sim/system.hh"
  56
  57 /**
  58  * This snoop filter keeps track of which connected port has a
  59  * particular line of data. It can be queried (through lookup*) on
  60  * memory requests from above (reads / writes / ...); and also from
  61  * below (snoops). The snoop filter precisely knows about the location
  62  * of lines "above" it through a map from cache line address to
  63  * sharers/ports. The snoop filter ties into the flows of requests
  64  * (when they succeed at the lower interface), regular responses from
  65  * below and also responses from sideway's caches (in update*). This
  66  * allows the snoop filter to model cache-line residency by snooping
  67  * the messages.
  68  *
  69  * The tracking happens in two fields to be able to distinguish
  70  * between in-flight requests (in requested) and already pulled in
  71  * lines (in holder). This distinction is used for producing tighter
  72  * assertions and tracking request completion. For safety, (requested
  73  * | holder) should be notified and the requesting MSHRs will take
  74  * care of ordering.
  75  *
  76  * Overall, some trickery is required because:
  77  * (1) snoops are not followed by an ACK, but only evoke a response if
  78  *     they need to (hit dirty)
  79  * (2) side-channel information is funnelled through direct modifications of
  80  *     pkt, instead of proper messages through the bus
  81  * (3) there are no clean evict messages telling the snoop filter that a local,
  82  *     upper cache dropped a line, making the snoop filter pessimistic for now
  83  * (4) ordering: there is no single point of order in the system.  Instead,
  84  *     requesting MSHRs track order between local requests and remote snoops
  85  */
  86 class SnoopFilter : public SimObject {
  87   public:
  88
  89     // Change for systems with more than 256 ports tracked by this object
  90     static const int SNOOP_MASK_SIZE = 256;
  91
  92     typedef std::vector<QueuedResponsePort*> SnoopList;
  93
  94     SnoopFilter (const SnoopFilterParams &p) :
  95         SimObject(p), reqLookupResult(cachedLocations.end()),
  96         linesize(p.system->cacheLineSize()), lookupLatency(p.lookup_latency),
  97         maxEntryCount(p.max_capacity / p.system->cacheLineSize()),
  98         stats(this)
  99     {
 100     }
 101
 102     /**
 103      * Init a new snoop filter and tell it about all the cpu_sideports
 104      * of the enclosing bus.
 105      *
 106      * @param _cpu_side_ports Response ports that the bus is attached to.
 107      */
 108     void setCPUSidePorts(const SnoopList& _cpu_side_ports) {
 109         localResponsePortIds.resize(_cpu_side_ports.size(), InvalidPortID);
 110
 111         PortID id = 0;
 112         for (const auto& p : _cpu_side_ports) {
 113             // no need to track this port if it is not snooping
 114             if (p->isSnooping()) {
 115                 cpuSidePorts.push_back(p);
 116                 localResponsePortIds[p->getId()] = id++;
 117             }
 118         }
 119
 120         // make sure we can deal with this many ports
 121         fatal_if(id > SNOOP_MASK_SIZE,
 122                  "Snoop filter only supports %d snooping ports, got %d\n",
 123                  SNOOP_MASK_SIZE, id);
 124     }
 125
 126     /**
 127      * Lookup a request (from a CPU-side port) in the snoop filter and
 128      * return a list of other CPU-side ports that need forwarding of the
 129      * resulting snoops.  Additionally, update the tracking structures
 130      * with new request information. Note that the caller must also
 131      * call finishRequest once it is known if the request needs to
 132      * retry or not.
 133      *
 134      * @param cpkt              Pointer to the request packet. Not changed.
 135      * @param cpu_side_port     Response port where the request came from.
 136      * @return Pair of a vector of snoop target ports and lookup latency.
 137      */
 138     std::pair<SnoopList, Cycles> lookupRequest(const Packet* cpkt,
 139                                         const ResponsePort& cpu_side_port);
 140
 141     /**
 142      * For an un-successful request, revert the change to the snoop
 143      * filter. Also take care of erasing any null entries. This method
 144      * relies on the result from lookupRequest being stored in
 145      * reqLookupResult.
 146      *
 147      * @param will_retry    This request will retry on this bus / snoop filter
 148      * @param addr          Packet address, merely for sanity checking
 149      */
 150     void finishRequest(bool will_retry, Addr addr, bool is_secure);
 151
 152     /**
 153      * Handle an incoming snoop from below (the memory-side port). These
 154      * can upgrade the tracking logic and may also benefit from
 155      * additional steering thanks to the snoop filter.
 156      *
 157      * @param cpkt Pointer to const Packet containing the snoop.
 158      * @return Pair with a vector of ResponsePorts that need snooping and a
 159      * lookup latency.
 160      */
 161     std::pair<SnoopList, Cycles> lookupSnoop(const Packet* cpkt);
 162
 163     /**
 164      * Let the snoop filter see any snoop responses that turn into
 165      * request responses and indicate cache to cache transfers. These
 166      * will update the corresponding state in the filter.
 167      *
 168      * @param cpkt     Pointer to const Packet holding the snoop response.
 169      * @param rsp_port ResponsePort that sends the response.
 170      * @param req_port ResponsePort that made the original request and is the
 171      *                 destination of the snoop response.
 172      */
 173     void updateSnoopResponse(const Packet *cpkt, const ResponsePort& rsp_port,
 174                              const ResponsePort& req_port);
 175
 176     /**
 177      * Pass snoop responses that travel downward through the snoop
 178      * filter and let them update the snoop filter state.  No
 179      * additional routing happens.
 180      *
 181      * @param cpkt     Pointer to const Packet holding the snoop response.
 182      * @param rsp_port ResponsePort that sends the response.
 183      * @param req_port RequestPort through which the response is forwarded.
 184      */
 185     void updateSnoopForward(const Packet *cpkt, const ResponsePort& rsp_port,
 186                             const RequestPort& req_port);
 187
 188     /**
 189      * Update the snoop filter with a response from below (outer /
 190      * other cache, or memory) and update the tracking information in
 191      * the snoop filter.
 192      *
 193      * @param cpkt          Pointer to const Packet holding the snoop response.
 194      * @param cpu_side_port ResponsePort that made the original request and
 195      *                      is the target of this response.
 196      */
 197     void updateResponse(const Packet *cpkt, const ResponsePort& cpu_side_port);
 198
 199     virtual void regStats();
 200
 201   protected:
 202
 203     /**
 204      * The underlying type for the bitmask we use for tracking. This
 205      * limits the number of snooping ports supported per crossbar.
 206      */
 207     typedef std::bitset<SNOOP_MASK_SIZE> SnoopMask;
 208
 209     /**
 210     * Per cache line item tracking a bitmask of ResponsePorts who have an
 211     * outstanding request to this line (requested) or already share a
 212     * cache line with this address (holder).
 213     */
 214     struct SnoopItem {
 215         SnoopMask requested;
 216         SnoopMask holder;
 217     };
 218     /**
 219      * HashMap of SnoopItems indexed by line address
 220      */
 221     typedef std::unordered_map<Addr, SnoopItem> SnoopFilterCache;
 222
 223     /**
 224      * Simple factory methods for standard return values.
 225      */
 226     std::pair<SnoopList, Cycles> snoopAll(Cycles latency) const
 227     {
 228         return std::make_pair(cpuSidePorts, latency);
 229     }
 230     std::pair<SnoopList, Cycles> snoopSelected(const SnoopList&
 231                                 _cpu_side_ports, Cycles latency) const
 232     {
 233         return std::make_pair(_cpu_side_ports, latency);
 234     }
 235     std::pair<SnoopList, Cycles> snoopDown(Cycles latency) const
 236     {
 237         SnoopList empty;
 238         return std::make_pair(empty , latency);
 239     }
 240
 241     /**
 242      * Convert a single port to a corresponding, one-hot bitmask
 243      * @param port ResponsePort that should be converted.
 244      * @return One-hot bitmask corresponding to the port.
 245      */
 246     SnoopMask portToMask(const ResponsePort& port) const;
 247     /**
 248      * Converts a bitmask of ports into the corresponing list of ports
 249      * @param ports SnoopMask of the requested ports
 250      * @return SnoopList containing all the requested ResponsePorts
 251      */
 252     SnoopList maskToPortList(SnoopMask ports) const;
 253
 254   private:
 255
 256     /**
 257      * Removes snoop filter items which have no requestors and no holders.
 258      */
 259     void eraseIfNullEntry(SnoopFilterCache::iterator& sf_it);
 260
 261     /** Simple hash set of cached addresses. */
 262     SnoopFilterCache cachedLocations;
 263
 264     /**
 265      * A request lookup must be followed by a call to finishRequest to inform
 266      * the operation's success. If a retry is needed, however, all changes
 267      * made to the snoop filter while performing the lookup must be undone.
 268      * This structure keeps track of the state previous to such changes.
 269      */
 270     struct ReqLookupResult {
 271         /** Iterator used to store the result from lookupRequest. */
 272         SnoopFilterCache::iterator it;
 273
 274         /**
 275          * Variable to temporarily store value of snoopfilter entry
 276          * in case finishRequest needs to undo changes made in lookupRequest
 277          * (because of crossbar retry)
 278          */
 279         SnoopItem retryItem;
 280
 281         /**
 282          * The constructor must be informed of the internal cache's end
 283          * iterator, so do not allow the compiler to implictly define it.
 284          *
 285          * @param end_it Iterator to the end of the internal cache.
 286          */
 287         ReqLookupResult(SnoopFilterCache::iterator end_it)
 288             : it(end_it), retryItem{0, 0}
 289         {
 290         }
 291         ReqLookupResult() = delete;
 292     } reqLookupResult;
 293
 294     /** List of all attached snooping CPU-side ports. */
 295     SnoopList cpuSidePorts;
 296     /** Track the mapping from port ids to the local mask ids. */
 297     std::vector<PortID> localResponsePortIds;
 298     /** Cache line size. */
 299     const unsigned linesize;
 300     /** Latency for doing a lookup in the filter */
 301     const Cycles lookupLatency;
 302     /** Max capacity in terms of cache blocks tracked, for sanity checking */
 303     const unsigned maxEntryCount;
 304
 305     /**
 306      * Use the lower bits of the address to keep track of the line status
 307      */
 308     enum LineStatus {
 309         /** block holds data from the secure memory space */
 310         LineSecure = 0x01,
 311     };
 312
 313     /** Statistics */
 314     struct SnoopFilterStats : public Stats::Group {
 315         SnoopFilterStats(Stats::Group *parent);
 316
 317         Stats::Scalar totRequests;
 318         Stats::Scalar hitSingleRequests;
 319         Stats::Scalar hitMultiRequests;
 320
 321         Stats::Scalar totSnoops;
 322         Stats::Scalar hitSingleSnoops;
 323         Stats::Scalar hitMultiSnoops;
 324     } stats;
 325 };
 326
 327 inline SnoopFilter::SnoopMask
 328 SnoopFilter::portToMask(const ResponsePort& port) const
 329 {
 330     assert(port.getId() != InvalidPortID);
 331     // if this is not a snooping port, return a zero mask
 332     return !port.isSnooping() ? 0 :
 333         ((SnoopMask)1) << localResponsePortIds[port.getId()];
 334 }
 335
 336 inline SnoopFilter::SnoopList
 337 SnoopFilter::maskToPortList(SnoopMask port_mask) const
 338 {
 339     SnoopList res;
 340     for (const auto& p : cpuSidePorts)
 341         if ((port_mask & portToMask(*p)).any())
 342             res.push_back(p);
 343     return res;
 344 }
 345
 346 #endif // __MEM_SNOOP_FILTER_HH__