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     // If the snoop response has no sharers the line is passed in
 261     // Modified state, and we know that there are no other copies, or
 262     // they will all be invalidated imminently
 263     if (!cpkt->hasSharers()) {
 264         DPRINTF(SnoopFilter,
 265                 "%s: dropping %x because non-shared snoop "
 266                 "response SF val: %x.%x\n", __func__,  rsp_mask,
 267                 sf_item.requested, sf_item.holder);
 268         sf_item.holder = 0;
 269     }
 270     assert(!cpkt->isWriteback());
 271     sf_item.holder |=  req_mask;
 272     sf_item.requested &= ~req_mask;
 273     assert(sf_item.requested | sf_item.holder);
 274     DPRINTF(SnoopFilter, "%s:   new SF value %x.%x\n",
 275             __func__, sf_item.requested, sf_item.holder);
 276 }
 277
 278 void
 279 SnoopFilter::updateSnoopForward(const Packet* cpkt,
 280         const SlavePort& rsp_port, const MasterPort& req_port)
 281 {
 282     DPRINTF(SnoopFilter, "%s: packet rsp %s req %s addr 0x%x cmd %s\n",
 283             __func__, rsp_port.name(), req_port.name(), cpkt->getAddr(),
 284             cpkt->cmdString());
 285
 286     assert(cpkt->isResponse());
 287     assert(cpkt->cacheResponding());
 288
 289     Addr line_addr = cpkt->getBlockAddr(linesize);
 290     auto sf_it = cachedLocations.find(line_addr);
 291     bool is_hit = sf_it != cachedLocations.end();
 292
 293     // Nothing to do if it is not a hit
 294     if (!is_hit)
 295         return;
 296
 297     SnoopItem& sf_item = sf_it->second;
 298
 299     DPRINTF(SnoopFilter, "%s:   old SF value %x.%x\n",
 300             __func__,  sf_item.requested, sf_item.holder);
 301
 302     // If the snoop response has no sharers the line is passed in
 303     // Modified state, and we know that there are no other copies, or
 304     // they will all be invalidated imminently
 305     if (!cpkt->hasSharers()) {
 306         sf_item.holder = 0;
 307     }
 308     DPRINTF(SnoopFilter, "%s:   new SF value %x.%x\n",
 309             __func__, sf_item.requested, sf_item.holder);
 310     eraseIfNullEntry(sf_it);
 311
 312 }
 313
 314 void
 315 SnoopFilter::updateResponse(const Packet* cpkt, const SlavePort& slave_port)
 316 {
 317     DPRINTF(SnoopFilter, "%s: packet src %s addr 0x%x cmd %s\n",
 318             __func__, slave_port.name(), cpkt->getAddr(), cpkt->cmdString());
 319
 320     assert(cpkt->isResponse());
 321
 322     // Ultimately we should check if the packet came from an
 323     // allocating source, not just if the port is snooping
 324     bool allocate = !cpkt->req->isUncacheable() && slave_port.isSnooping();
 325     if (!allocate)
 326         return;
 327
 328     Addr line_addr = cpkt->getBlockAddr(linesize);
 329     SnoopMask slave_mask = portToMask(slave_port);
 330     SnoopItem& sf_item = cachedLocations[line_addr];
 331
 332     DPRINTF(SnoopFilter, "%s:   old SF value %x.%x\n",
 333             __func__,  sf_item.requested, sf_item.holder);
 334
 335     // Make sure we have seen the actual request, too
 336     panic_if(!(sf_item.requested & slave_mask), "SF value %x.%x missing "\
 337              "request bit\n", sf_item.requested, sf_item.holder);
 338
 339     // Update the residency of the cache line. If the response has no
 340     // sharers we know that the line has been invalidated in all
 341     // branches that are not where we are responding to.
 342      if (!cpkt->hasSharers())
 343         sf_item.holder = 0;
 344     sf_item.holder |=  slave_mask;
 345     sf_item.requested &= ~slave_mask;
 346     assert(sf_item.holder | sf_item.requested);
 347     DPRINTF(SnoopFilter, "%s:   new SF value %x.%x\n",
 348             __func__, sf_item.requested, sf_item.holder);
 349 }
 350
 351 void
 352 SnoopFilter::regStats()
 353 {
 354     SimObject::regStats();
 355
 356     totRequests
 357         .name(name() + ".tot_requests")
 358         .desc("Total number of requests made to the snoop filter.");
 359
 360     hitSingleRequests
 361         .name(name() + ".hit_single_requests")
 362         .desc("Number of requests hitting in the snoop filter with a single "\
 363               "holder of the requested data.");
 364
 365     hitMultiRequests
 366         .name(name() + ".hit_multi_requests")
 367         .desc("Number of requests hitting in the snoop filter with multiple "\
 368               "(>1) holders of the requested data.");
 369
 370     totSnoops
 371         .name(name() + ".tot_snoops")
 372         .desc("Total number of snoops made to the snoop filter.");
 373
 374     hitSingleSnoops
 375         .name(name() + ".hit_single_snoops")
 376         .desc("Number of snoops hitting in the snoop filter with a single "\
 377               "holder of the requested data.");
 378
 379     hitMultiSnoops
 380         .name(name() + ".hit_multi_snoops")
 381         .desc("Number of snoops hitting in the snoop filter with multiple "\
 382               "(>1) holders of the requested data.");
 383 }
 384
 385 SnoopFilter *
 386 SnoopFilterParams::create()
 387 {
 388     return new SnoopFilter(this);
 389 }