snoop_filter.hh revision 10403:b3231fc8ae9d 
1/*
2 * Copyright (c) 2013 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 * Authors: Stephan Diestelhorst <stephan.diestelhorst@arm.com>
38 */
39
40/**
41 * @file
42 * Definition of a snoop filter.
43 */
44
45#ifndef __MEM_SNOOP_FILTER_HH__
46#define __MEM_SNOOP_FILTER_HH__
47
48#include <utility>
49
50#include "base/hashmap.hh"
51#include "mem/packet.hh"
52#include "mem/port.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 */
86class SnoopFilter : public SimObject {
87  public:
88    typedef std::vector<SlavePort*> SnoopList;
89
90    SnoopFilter (const SnoopFilterParams *p) : SimObject(p),
91        linesize(p->system->cacheLineSize()), lookupLatency(p->lookup_latency)
92    {
93    }
94
95    /**
96     * Init a new snoop filter and tell it about all the slave ports of the
97     * enclosing bus.
98     *
99     * @param bus_slave_ports Vector of slave ports that the bus is attached to.
100     */
101    void setSlavePorts(const std::vector<SlavePort*>& bus_slave_ports) {
102        slavePorts = bus_slave_ports;
103    }
104
105    /**
106     * Lookup a request (from a slave port) in the snoop filter and return a
107     * list of other slave ports that need forwarding of the resulting snoops.
108     * Additionally, update the tracking structures with new request
109     * information.
110     *
111     * @param cpkt          Pointer to the request packet.  Not changed.
112     * @param slave_port    Slave port where the request came from.
113     * @return Pair of a vector of snoop target ports and lookup latency.
114     */
115    std::pair<SnoopList, Cycles> lookupRequest(const Packet* cpkt,
116                                               const SlavePort& slave_port);
117
118    /**
119     * For a successful request, update all data structures in the snoop filter
120     * reflecting the changes caused by that request
121     *
122     * @param cpkt          Pointer to the request packet.  Not changed.
123     * @param slave_port    Slave port where the request came from.
124     * @param will_retry    This request will retry on this bus / snoop filter
125     */
126    void updateRequest(const Packet* cpkt, const SlavePort& slave_port,
127                       bool will_retry);
128
129    /**
130     * Handle an incoming snoop from below (the master port).  These can upgrade the
131     * tracking logic and may also benefit from additional steering thanks to the
132     * snoop filter.
133     * @param cpkt Pointer to const Packet containing the snoop.
134     * @return Pair with a vector of SlavePorts that need snooping and a lookup
135     *         latency.
136     */
137    std::pair<SnoopList, Cycles> lookupSnoop(const Packet* cpkt);
138
139    /**
140     * Let the snoop filter see any snoop responses that turn into request responses
141     * and indicate cache to cache transfers.  These will update the corresponding
142     * state in the filter.
143     *
144     * @param cpkt     Pointer to const Packet holding the snoop response.
145     * @param rsp_port SlavePort that sends the response.
146     * @param req_port SlavePort that made the original request and is the
147     *                 destination of the snoop response.
148     */
149    void updateSnoopResponse(const Packet *cpkt, const SlavePort& rsp_port,
150                             const SlavePort& req_port);
151
152    /**
153     * Pass snoop responses that travel downward through the snoop filter and let
154     * them update the snoop filter state.  No additional routing happens.
155     *
156     * @param cpkt     Pointer to const Packet holding the snoop response.
157     * @param rsp_port SlavePort that sends the response.
158     * @param req_port MasterPort through which the response leaves this cluster.
159     */
160    void updateSnoopForward(const Packet *cpkt, const SlavePort& rsp_port,
161                            const MasterPort& req_port);
162
163    /**
164     * Update the snoop filter with a response from below (outer / other cache,
165     * or memory) and update the tracking information in the snoop filter.
166     *
167     * @param cpkt       Pointer to const Packet holding the snoop response.
168     * @param slave_port SlavePort that made the original request and is the target
169     *                   of this response.
170     */
171    void updateResponse(const Packet *cpkt, const SlavePort& slave_port);
172
173    /**
174     * Simple factory methods for standard return values for lookupRequest
175     */
176    std::pair<SnoopList, Cycles> snoopAll(Cycles latency) const
177    {
178        return std::make_pair(slavePorts, latency);
179    }
180    std::pair<SnoopList, Cycles> snoopSelected(const SnoopList& slave_ports,
181                                               Cycles latency) const
182    {
183        return std::make_pair(slave_ports, latency);
184    }
185    std::pair<SnoopList, Cycles> snoopDown(Cycles latency) const
186    {
187        SnoopList empty;
188        return std::make_pair(empty , latency);
189    }
190
191    virtual void regStats();
192
193  protected:
194    typedef uint64_t SnoopMask;
195   /**
196    * Per cache line item tracking a bitmask of SlavePorts who have an
197    * outstanding request to this line (requested) or already share a cache line
198    * with this address (holder).
199    */
200    struct SnoopItem {
201        SnoopMask requested;
202        SnoopMask holder;
203    };
204    /**
205     * Convert a single port to a corresponding, one-hot bitmask
206     * @param port SlavePort that should be converted.
207     * @return One-hot bitmask corresponding to the port.
208     */
209    SnoopMask portToMask(const SlavePort& port) const;
210    /**
211     * Convert multiple ports to a corresponding bitmask
212     * @param ports SnoopList that should be converted.
213     * @return Bitmask corresponding to the ports in the list.
214     */
215    SnoopMask portListToMask(const SnoopList& ports) const;
216    /**
217     * Converts a bitmask of ports into the corresponing list of ports
218     * @param ports SnoopMask of the requested ports
219     * @return SnoopList containing all the requested SlavePorts
220     */
221    SnoopList maskToPortList(SnoopMask ports) const;
222
223  private:
224    /** Simple hash set of cached addresses. */
225    m5::hash_map<Addr, SnoopItem> cachedLocations;
226    /** List of all attached slave ports. */
227    SnoopList slavePorts;
228    /** Cache line size. */
229    const unsigned linesize;
230    /** Latency for doing a lookup in the filter */
231    const Cycles lookupLatency;
232
233    /** Statistics */
234    Stats::Scalar totRequests;
235    Stats::Scalar hitSingleRequests;
236    Stats::Scalar hitMultiRequests;
237
238    Stats::Scalar totSnoops;
239    Stats::Scalar hitSingleSnoops;
240    Stats::Scalar hitMultiSnoops;
241};
242
243inline SnoopFilter::SnoopMask
244SnoopFilter::portToMask(const SlavePort& port) const
245{
246    unsigned id = (unsigned)port.getId();
247    assert(id != (unsigned)InvalidPortID);
248    assert((int)id < 8 * sizeof(SnoopMask));
249
250    return ((SnoopMask)1) << id;
251}
252
253inline SnoopFilter::SnoopMask
254SnoopFilter::portListToMask(const SnoopList& ports) const
255{
256    SnoopMask m = 0;
257    for (auto port = ports.begin(); port != ports.end(); ++port)
258        m |= portToMask(**port);
259    return m;
260}
261
262inline SnoopFilter::SnoopList
263SnoopFilter::maskToPortList(SnoopMask port_mask) const
264{
265    SnoopList res;
266    for (auto port = slavePorts.begin(); port != slavePorts.end(); ++port)
267        if (port_mask & portToMask(**port))
268            res.push_back(*port);
269    return res;
270}
271#endif // __MEM_SNOOP_FILTER_HH__
272