1/*
2 * Copyright (c) 2013-2017,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 * Authors: Stephan Diestelhorst
38 */
39
40/**
41 * @file
42 * Implementation of a snoop filter.
43 */
44
45#include "mem/snoop_filter.hh"
46
47#include "base/logging.hh"
48#include "base/trace.hh"
49#include "debug/SnoopFilter.hh"
50#include "sim/system.hh"
51
52const int SnoopFilter::SNOOP_MASK_SIZE;
53
54void
55SnoopFilter::eraseIfNullEntry(SnoopFilterCache::iterator& sf_it)
56{
57 SnoopItem& sf_item = sf_it->second;
58 if ((sf_item.requested | sf_item.holder).none()) {
59 cachedLocations.erase(sf_it);
60 DPRINTF(SnoopFilter, "%s: Removed SF entry.\n",
61 __func__);
62 }
63}
64
65std::pair<SnoopFilter::SnoopList, Cycles>
66SnoopFilter::lookupRequest(const Packet* cpkt, const SlavePort& slave_port)
67{
68 DPRINTF(SnoopFilter, "%s: src %s packet %s\n", __func__,
69 slave_port.name(), cpkt->print());
70
71 // check if the packet came from a cache
72 bool allocate = !cpkt->req->isUncacheable() && slave_port.isSnooping() &&
73 cpkt->fromCache();
74 Addr line_addr = cpkt->getBlockAddr(linesize);
75 if (cpkt->isSecure()) {
76 line_addr |= LineSecure;
77 }
78 SnoopMask req_port = portToMask(slave_port);
79 reqLookupResult = cachedLocations.find(line_addr);
80 bool is_hit = (reqLookupResult != cachedLocations.end());
81
82 // If the snoop filter has no entry, and we should not allocate,
83 // do not create a new snoop filter entry, simply return a NULL
84 // portlist.
85 if (!is_hit && !allocate)
86 return snoopDown(lookupLatency);
87
88 // If no hit in snoop filter create a new element and update iterator
89 if (!is_hit)
90 reqLookupResult = cachedLocations.emplace(line_addr, SnoopItem()).first;
91 SnoopItem& sf_item = reqLookupResult->second;
92 SnoopMask interested = sf_item.holder | sf_item.requested;
93
94 // Store unmodified value of snoop filter item in temp storage in
95 // case we need to revert because of a send retry in
96 // updateRequest.
97 retryItem = sf_item;
98
99 totRequests++;
100 if (is_hit) {
101 if (interested.count() == 1)
102 hitSingleRequests++;
103 else
104 hitMultiRequests++;
105 }
106
107 DPRINTF(SnoopFilter, "%s: SF value %x.%x\n",
108 __func__, sf_item.requested, sf_item.holder);
109
110 // If we are not allocating, we are done
111 if (!allocate)
112 return snoopSelected(maskToPortList(interested & ~req_port),
113 lookupLatency);
114
115 if (cpkt->needsResponse()) {
116 if (!cpkt->cacheResponding()) {
117 // Max one request per address per port
118 panic_if((sf_item.requested & req_port).any(),
119 "double request :( SF value %x.%x\n",
120 sf_item.requested, sf_item.holder);
121
122 // Mark in-flight requests to distinguish later on
123 sf_item.requested |= req_port;
124 DPRINTF(SnoopFilter, "%s: new SF value %x.%x\n",
125 __func__, sf_item.requested, sf_item.holder);
126 } else {
127 // NOTE: The memInhibit might have been asserted by a cache closer
128 // to the CPU, already -> the response will not be seen by this
129 // filter -> we do not need to keep the in-flight request, but make
130 // sure that we know that that cluster has a copy
131 panic_if((sf_item.holder & req_port).none(),
132 "Need to hold the value!");
133 DPRINTF(SnoopFilter,
134 "%s: not marking request. SF value %x.%x\n",
135 __func__, sf_item.requested, sf_item.holder);
136 }
137 } else { // if (!cpkt->needsResponse())
138 assert(cpkt->isEviction());
139 // make sure that the sender actually had the line
140 panic_if((sf_item.holder & req_port).none(), "requester %x is not a " \
141 "holder :( SF value %x.%x\n", req_port,
142 sf_item.requested, sf_item.holder);
143 // CleanEvicts and Writebacks -> the sender and all caches above
144 // it may not have the line anymore.
145 if (!cpkt->isBlockCached()) {
146 sf_item.holder &= ~req_port;
147 DPRINTF(SnoopFilter, "%s: new SF value %x.%x\n",
148 __func__, sf_item.requested, sf_item.holder);
149 }
150 }
151
152 return snoopSelected(maskToPortList(interested & ~req_port), lookupLatency);
153}
154
155void
156SnoopFilter::finishRequest(bool will_retry, Addr addr, bool is_secure)
157{
158 if (reqLookupResult != cachedLocations.end()) {
159 // since we rely on the caller, do a basic check to ensure
160 // that finishRequest is being called following lookupRequest
161 Addr line_addr = (addr & ~(Addr(linesize - 1)));
162 if (is_secure) {
163 line_addr |= LineSecure;
164 }
165 assert(reqLookupResult->first == line_addr);
166 if (will_retry) {
167 // Undo any changes made in lookupRequest to the snoop filter
168 // entry if the request will come again. retryItem holds
169 // the previous value of the snoopfilter entry.
170 reqLookupResult->second = retryItem;
171
172 DPRINTF(SnoopFilter, "%s: restored SF value %x.%x\n",
173 __func__, retryItem.requested, retryItem.holder);
174 }
175
176 eraseIfNullEntry(reqLookupResult);
177 }
178}
179
180std::pair<SnoopFilter::SnoopList, Cycles>
181SnoopFilter::lookupSnoop(const Packet* cpkt)
182{
183 DPRINTF(SnoopFilter, "%s: packet %s\n", __func__, cpkt->print());
184
185 assert(cpkt->isRequest());
186
187 Addr line_addr = cpkt->getBlockAddr(linesize);
188 if (cpkt->isSecure()) {
189 line_addr |= LineSecure;
190 }
191 auto sf_it = cachedLocations.find(line_addr);
192 bool is_hit = (sf_it != cachedLocations.end());
193
194 panic_if(!is_hit && (cachedLocations.size() >= maxEntryCount),
195 "snoop filter exceeded capacity of %d cache blocks\n",
196 maxEntryCount);
197
198 // If the snoop filter has no entry, simply return a NULL
199 // portlist, there is no point creating an entry only to remove it
200 // later
201 if (!is_hit)
202 return snoopDown(lookupLatency);
203
204 SnoopItem& sf_item = sf_it->second;
205
206 DPRINTF(SnoopFilter, "%s: old SF value %x.%x\n",
207 __func__, sf_item.requested, sf_item.holder);
208
209 SnoopMask interested = (sf_item.holder | sf_item.requested);
210
211 totSnoops++;
212
213 if (interested.count() == 1)
214 hitSingleSnoops++;
215 else
216 hitMultiSnoops++;
217
218 // ReadEx and Writes require both invalidation and exlusivity, while reads
219 // require neither. Writebacks on the other hand require exclusivity but
220 // not the invalidation. Previously Writebacks did not generate upward
221 // snoops so this was never an issue. Now that Writebacks generate snoops
222 // we need a special case for Writebacks. Additionally cache maintenance
223 // operations can generate snoops as they clean and/or invalidate all
224 // caches down to the specified point of reference.
225 assert(cpkt->isWriteback() || cpkt->req->isUncacheable() ||
226 (cpkt->isInvalidate() == cpkt->needsWritable()) ||
227 cpkt->req->isCacheMaintenance());
228 if (cpkt->isInvalidate() && sf_item.requested.none()) {
229 // Early clear of the holder, if no other request is currently going on
230 // @todo: This should possibly be updated even though we do not filter
231 // upward snoops
232 sf_item.holder = 0;
233 }
234
235 eraseIfNullEntry(sf_it);
236 DPRINTF(SnoopFilter, "%s: new SF value %x.%x interest: %x \n",
237 __func__, sf_item.requested, sf_item.holder, interested);
238
239 return snoopSelected(maskToPortList(interested), lookupLatency);
240}
241
242void
243SnoopFilter::updateSnoopResponse(const Packet* cpkt,
244 const SlavePort& rsp_port,
245 const SlavePort& req_port)
246{
247 DPRINTF(SnoopFilter, "%s: rsp %s req %s packet %s\n",
248 __func__, rsp_port.name(), req_port.name(), cpkt->print());
249
250 assert(cpkt->isResponse());
251 assert(cpkt->cacheResponding());
252
253 // if this snoop response is due to an uncacheable request, or is
254 // being turned into a normal response, there is nothing more to
255 // do
256 if (cpkt->req->isUncacheable() || !req_port.isSnooping()) {
257 return;
258 }
259
260 Addr line_addr = cpkt->getBlockAddr(linesize);
261 if (cpkt->isSecure()) {
262 line_addr |= LineSecure;
263 }
264 SnoopMask rsp_mask = portToMask(rsp_port);
265 SnoopMask req_mask = portToMask(req_port);
266 SnoopItem& sf_item = cachedLocations[line_addr];
267
268 DPRINTF(SnoopFilter, "%s: old SF value %x.%x\n",
269 __func__, sf_item.requested, sf_item.holder);
270
271 // The source should have the line
272 panic_if((sf_item.holder & rsp_mask).none(),
273 "SF value %x.%x does not have the line\n",
274 sf_item.requested, sf_item.holder);
275
276 // The destination should have had a request in
277 panic_if((sf_item.requested & req_mask).none(), "SF value %x.%x missing "\
278 "the original request\n", sf_item.requested, sf_item.holder);
279
280 // If the snoop response has no sharers the line is passed in
281 // Modified state, and we know that there are no other copies, or
282 // they will all be invalidated imminently
283 if (!cpkt->hasSharers()) {
284 DPRINTF(SnoopFilter,
285 "%s: dropping %x because non-shared snoop "
286 "response SF val: %x.%x\n", __func__, rsp_mask,
287 sf_item.requested, sf_item.holder);
288 sf_item.holder = 0;
289 }
290 assert(!cpkt->isWriteback());
291 // @todo Deal with invalidating responses
292 sf_item.holder |= req_mask;
293 sf_item.requested &= ~req_mask;
294 assert((sf_item.requested | sf_item.holder).any());
295 DPRINTF(SnoopFilter, "%s: new SF value %x.%x\n",
296 __func__, sf_item.requested, sf_item.holder);
297}
298
299void
300SnoopFilter::updateSnoopForward(const Packet* cpkt,
301 const SlavePort& rsp_port, const MasterPort& req_port)
302{
303 DPRINTF(SnoopFilter, "%s: rsp %s req %s packet %s\n",
304 __func__, rsp_port.name(), req_port.name(), cpkt->print());
305
306 assert(cpkt->isResponse());
307 assert(cpkt->cacheResponding());
308
309 Addr line_addr = cpkt->getBlockAddr(linesize);
310 if (cpkt->isSecure()) {
311 line_addr |= LineSecure;
312 }
313 auto sf_it = cachedLocations.find(line_addr);
314 bool is_hit = sf_it != cachedLocations.end();
315
316 // Nothing to do if it is not a hit
317 if (!is_hit)
318 return;
319
320 SnoopItem& sf_item = sf_it->second;
321
322 DPRINTF(SnoopFilter, "%s: old SF value %x.%x\n",
323 __func__, sf_item.requested, sf_item.holder);
324
325 // If the snoop response has no sharers the line is passed in
326 // Modified state, and we know that there are no other copies, or
327 // they will all be invalidated imminently
328 if (!cpkt->hasSharers()) {
329 sf_item.holder = 0;
330 }
331 DPRINTF(SnoopFilter, "%s: new SF value %x.%x\n",
332 __func__, sf_item.requested, sf_item.holder);
333 eraseIfNullEntry(sf_it);
334
335}
336
337void
338SnoopFilter::updateResponse(const Packet* cpkt, const SlavePort& slave_port)
339{
340 DPRINTF(SnoopFilter, "%s: src %s packet %s\n",
341 __func__, slave_port.name(), cpkt->print());
342
343 assert(cpkt->isResponse());
344
345 // we only allocate if the packet actually came from a cache, but
346 // start by checking if the port is snooping
347 if (cpkt->req->isUncacheable() || !slave_port.isSnooping())
348 return;
349
350 // next check if we actually allocated an entry
351 Addr line_addr = cpkt->getBlockAddr(linesize);
352 if (cpkt->isSecure()) {
353 line_addr |= LineSecure;
354 }
355 auto sf_it = cachedLocations.find(line_addr);
356 if (sf_it == cachedLocations.end())
357 return;
358
359 SnoopMask slave_mask = portToMask(slave_port);
360 SnoopItem& sf_item = sf_it->second;
361
362 DPRINTF(SnoopFilter, "%s: old SF value %x.%x\n",
363 __func__, sf_item.requested, sf_item.holder);
364
365 // Make sure we have seen the actual request, too
366 panic_if((sf_item.requested & slave_mask).none(),
367 "SF value %x.%x missing request bit\n",
368 sf_item.requested, sf_item.holder);
369
370 sf_item.requested &= ~slave_mask;
371 // Update the residency of the cache line.
372
373 if (cpkt->req->isCacheMaintenance()) {
374 // A cache clean response does not carry any data so it
375 // shouldn't change the holders, unless it is invalidating.
376 if (cpkt->isInvalidate()) {
377 sf_item.holder &= ~slave_mask;
378 }
379 eraseIfNullEntry(sf_it);
380 } else {
381 // Any other response implies that a cache above will have the
382 // block.
383 sf_item.holder |= slave_mask;
384 assert((sf_item.holder | sf_item.requested).any());
385 }
386 DPRINTF(SnoopFilter, "%s: new SF value %x.%x\n",
387 __func__, sf_item.requested, sf_item.holder);
388}
389
390void
391SnoopFilter::regStats()
392{
393 SimObject::regStats();
394
395 totRequests
396 .name(name() + ".tot_requests")
397 .desc("Total number of requests made to the snoop filter.");
398
399 hitSingleRequests
400 .name(name() + ".hit_single_requests")
401 .desc("Number of requests hitting in the snoop filter with a single "\
402 "holder of the requested data.");
403
404 hitMultiRequests
405 .name(name() + ".hit_multi_requests")
406 .desc("Number of requests hitting in the snoop filter with multiple "\
407 "(>1) holders of the requested data.");
408
409 totSnoops
410 .name(name() + ".tot_snoops")
411 .desc("Total number of snoops made to the snoop filter.");
412
413 hitSingleSnoops
414 .name(name() + ".hit_single_snoops")
415 .desc("Number of snoops hitting in the snoop filter with a single "\
416 "holder of the requested data.");
417
418 hitMultiSnoops
419 .name(name() + ".hit_multi_snoops")
420 .desc("Number of snoops hitting in the snoop filter with multiple "\
421 "(>1) holders of the requested data.");
422}
423
424SnoopFilter *
425SnoopFilterParams::create()
426{
427 return new SnoopFilter(this);
428}