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     {
  99     }
 100
 101     /**
 102      * Init a new snoop filter and tell it about all the cpu_sideports
 103      * of the enclosing bus.
 104      *
 105      * @param _cpu_side_ports Response ports that the bus is attached to.
 106      */
 107     void setCPUSidePorts(const SnoopList& _cpu_side_ports) {
 108         localResponsePortIds.resize(_cpu_side_ports.size(), InvalidPortID);
 109
 110         PortID id = 0;
 111         for (const auto& p : _cpu_side_ports) {
 112             // no need to track this port if it is not snooping
 113             if (p->isSnooping()) {
 114                 cpuSidePorts.push_back(p);
 115                 localResponsePortIds[p->getId()] = id++;
 116             }
 117         }
 118
 119         // make sure we can deal with this many ports
 120         fatal_if(id > SNOOP_MASK_SIZE,
 121                  "Snoop filter only supports %d snooping ports, got %d\n",
 122                  SNOOP_MASK_SIZE, id);
 123     }
 124
 125     /**
 126      * Lookup a request (from a CPU-side port) in the snoop filter and
 127      * return a list of other CPU-side ports that need forwarding of the
 128      * resulting snoops.  Additionally, update the tracking structures
 129      * with new request information. Note that the caller must also
 130      * call finishRequest once it is known if the request needs to
 131      * retry or not.
 132      *
 133      * @param cpkt              Pointer to the request packet. Not changed.
 134      * @param cpu_side_port     Response port where the request came from.
 135      * @return Pair of a vector of snoop target ports and lookup latency.
 136      */
 137     std::pair<SnoopList, Cycles> lookupRequest(const Packet* cpkt,
 138                                         const ResponsePort& cpu_side_port);
 139
 140     /**
 141      * For an un-successful request, revert the change to the snoop
 142      * filter. Also take care of erasing any null entries. This method
 143      * relies on the result from lookupRequest being stored in
 144      * reqLookupResult.
 145      *
 146      * @param will_retry    This request will retry on this bus / snoop filter
 147      * @param addr          Packet address, merely for sanity checking
 148      */
 149     void finishRequest(bool will_retry, Addr addr, bool is_secure);
 150
 151     /**
 152      * Handle an incoming snoop from below (the memory-side port). These
 153      * can upgrade the tracking logic and may also benefit from
 154      * additional steering thanks to the snoop filter.
 155      *
 156      * @param cpkt Pointer to const Packet containing the snoop.
 157      * @return Pair with a vector of ResponsePorts that need snooping and a
 158      * lookup latency.
 159      */
 160     std::pair<SnoopList, Cycles> lookupSnoop(const Packet* cpkt);
 161
 162     /**
 163      * Let the snoop filter see any snoop responses that turn into
 164      * request responses and indicate cache to cache transfers. These
 165      * will update the corresponding state in the filter.
 166      *
 167      * @param cpkt     Pointer to const Packet holding the snoop response.
 168      * @param rsp_port ResponsePort that sends the response.
 169      * @param req_port ResponsePort that made the original request and is the
 170      *                 destination of the snoop response.
 171      */
 172     void updateSnoopResponse(const Packet *cpkt, const ResponsePort& rsp_port,
 173                              const ResponsePort& req_port);
 174
 175     /**
 176      * Pass snoop responses that travel downward through the snoop
 177      * filter and let them update the snoop filter state.  No
 178      * additional routing happens.
 179      *
 180      * @param cpkt     Pointer to const Packet holding the snoop response.
 181      * @param rsp_port ResponsePort that sends the response.
 182      * @param req_port RequestPort through which the response is forwarded.
 183      */
 184     void updateSnoopForward(const Packet *cpkt, const ResponsePort& rsp_port,
 185                             const RequestPort& req_port);
 186
 187     /**
 188      * Update the snoop filter with a response from below (outer /
 189      * other cache, or memory) and update the tracking information in
 190      * the snoop filter.
 191      *
 192      * @param cpkt          Pointer to const Packet holding the snoop response.
 193      * @param cpu_side_port ResponsePort that made the original request and
 194      *                      is the target of this response.
 195      */
 196     void updateResponse(const Packet *cpkt, const ResponsePort& cpu_side_port);
 197
 198     virtual void regStats();
 199
 200   protected:
 201
 202     /**
 203      * The underlying type for the bitmask we use for tracking. This
 204      * limits the number of snooping ports supported per crossbar.
 205      */
 206     typedef std::bitset<SNOOP_MASK_SIZE> SnoopMask;
 207
 208     /**
 209     * Per cache line item tracking a bitmask of ResponsePorts who have an
 210     * outstanding request to this line (requested) or already share a
 211     * cache line with this address (holder).
 212     */
 213     struct SnoopItem {
 214         SnoopMask requested;
 215         SnoopMask holder;
 216     };
 217     /**
 218      * HashMap of SnoopItems indexed by line address
 219      */
 220     typedef std::unordered_map<Addr, SnoopItem> SnoopFilterCache;
 221
 222     /**
 223      * Simple factory methods for standard return values.
 224      */
 225     std::pair<SnoopList, Cycles> snoopAll(Cycles latency) const
 226     {
 227         return std::make_pair(cpuSidePorts, latency);
 228     }
 229     std::pair<SnoopList, Cycles> snoopSelected(const SnoopList&
 230                                 _cpu_side_ports, Cycles latency) const
 231     {
 232         return std::make_pair(_cpu_side_ports, latency);
 233     }
 234     std::pair<SnoopList, Cycles> snoopDown(Cycles latency) const
 235     {
 236         SnoopList empty;
 237         return std::make_pair(empty , latency);
 238     }
 239
 240     /**
 241      * Convert a single port to a corresponding, one-hot bitmask
 242      * @param port ResponsePort that should be converted.
 243      * @return One-hot bitmask corresponding to the port.
 244      */
 245     SnoopMask portToMask(const ResponsePort& port) const;
 246     /**
 247      * Converts a bitmask of ports into the corresponing list of ports
 248      * @param ports SnoopMask of the requested ports
 249      * @return SnoopList containing all the requested ResponsePorts
 250      */
 251     SnoopList maskToPortList(SnoopMask ports) const;
 252
 253   private:
 254
 255     /**
 256      * Removes snoop filter items which have no requestors and no holders.
 257      */
 258     void eraseIfNullEntry(SnoopFilterCache::iterator& sf_it);
 259
 260     /** Simple hash set of cached addresses. */
 261     SnoopFilterCache cachedLocations;
 262
 263     /**
 264      * A request lookup must be followed by a call to finishRequest to inform
 265      * the operation's success. If a retry is needed, however, all changes
 266      * made to the snoop filter while performing the lookup must be undone.
 267      * This structure keeps track of the state previous to such changes.
 268      */
 269     struct ReqLookupResult {
 270         /** Iterator used to store the result from lookupRequest. */
 271         SnoopFilterCache::iterator it;
 272
 273         /**
 274          * Variable to temporarily store value of snoopfilter entry
 275          * in case finishRequest needs to undo changes made in lookupRequest
 276          * (because of crossbar retry)
 277          */
 278         SnoopItem retryItem;
 279
 280         /**
 281          * The constructor must be informed of the internal cache's end
 282          * iterator, so do not allow the compiler to implictly define it.
 283          *
 284          * @param end_it Iterator to the end of the internal cache.
 285          */
 286         ReqLookupResult(SnoopFilterCache::iterator end_it)
 287             : it(end_it), retryItem{0, 0}
 288         {
 289         }
 290         ReqLookupResult() = delete;
 291     } reqLookupResult;
 292
 293     /** List of all attached snooping CPU-side ports. */
 294     SnoopList cpuSidePorts;
 295     /** Track the mapping from port ids to the local mask ids. */
 296     std::vector<PortID> localResponsePortIds;
 297     /** Cache line size. */
 298     const unsigned linesize;
 299     /** Latency for doing a lookup in the filter */
 300     const Cycles lookupLatency;
 301     /** Max capacity in terms of cache blocks tracked, for sanity checking */
 302     const unsigned maxEntryCount;
 303
 304     /**
 305      * Use the lower bits of the address to keep track of the line status
 306      */
 307     enum LineStatus {
 308         /** block holds data from the secure memory space */
 309         LineSecure = 0x01,
 310     };
 311
 312     /** Statistics */
 313     Stats::Scalar totRequests;
 314     Stats::Scalar hitSingleRequests;
 315     Stats::Scalar hitMultiRequests;
 316
 317     Stats::Scalar totSnoops;
 318     Stats::Scalar hitSingleSnoops;
 319     Stats::Scalar hitMultiSnoops;
 320 };
 321
 322 inline SnoopFilter::SnoopMask
 323 SnoopFilter::portToMask(const ResponsePort& port) const
 324 {
 325     assert(port.getId() != InvalidPortID);
 326     // if this is not a snooping port, return a zero mask
 327     return !port.isSnooping() ? 0 :
 328         ((SnoopMask)1) << localResponsePortIds[port.getId()];
 329 }
 330
 331 inline SnoopFilter::SnoopList
 332 SnoopFilter::maskToPortList(SnoopMask port_mask) const
 333 {
 334     SnoopList res;
 335     for (const auto& p : cpuSidePorts)
 336         if ((port_mask & portToMask(*p)).any())
 337             res.push_back(p);
 338     return res;
 339 }
 340
 341 #endif // __MEM_SNOOP_FILTER_HH__