src/mem/snoop_filter.cc

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