src/mem/cache/mshr.cc

   1 /*
   2  * Copyright (c) 2012-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  * Copyright (c) 2002-2005 The Regents of The University of Michigan
  15  * Copyright (c) 2010 Advanced Micro Devices, Inc.
  16  * All rights reserved.
  17  *
  18  * Redistribution and use in source and binary forms, with or without
  19  * modification, are permitted provided that the following conditions are
  20  * met: redistributions of source code must retain the above copyright
  21  * notice, this list of conditions and the following disclaimer;
  22  * redistributions in binary form must reproduce the above copyright
  23  * notice, this list of conditions and the following disclaimer in the
  24  * documentation and/or other materials provided with the distribution;
  25  * neither the name of the copyright holders nor the names of its
  26  * contributors may be used to endorse or promote products derived from
  27  * this software without specific prior written permission.
  28  *
  29  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  30  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  31  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  32  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  33  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  34  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  35  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  36  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  37  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  38  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  39  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  40  *
  41  * Authors: Erik Hallnor
  42  *          Dave Greene
  43  */
  44
  45 /**
  46  * @file
  47  * Miss Status and Handling Register (MSHR) definitions.
  48  */
  49
  50 #include <algorithm>
  51 #include <cassert>
  52 #include <string>
  53 #include <vector>
  54
  55 #include "base/misc.hh"
  56 #include "base/types.hh"
  57 #include "debug/Cache.hh"
  58 #include "mem/cache/cache.hh"
  59 #include "mem/cache/mshr.hh"
  60 #include "sim/core.hh"
  61
  62 using namespace std;
  63
  64 MSHR::MSHR() : readyTime(0), _isUncacheable(false), downstreamPending(false),
  65                pendingModified(false),
  66                postInvalidate(false), postDowngrade(false),
  67                queue(NULL), order(0), blkAddr(0),
  68                blkSize(0), isSecure(false), inService(false),
  69                isForward(false), allocOnFill(false),
  70                data(NULL)
  71 {
  72 }
  73
  74
  75 MSHR::TargetList::TargetList()
  76     : needsWritable(false), hasUpgrade(false)
  77 {}
  78
  79
  80 inline void
  81 MSHR::TargetList::add(PacketPtr pkt, Tick readyTime,
  82                       Counter order, Target::Source source, bool markPending)
  83 {
  84     if (source != Target::FromSnoop) {
  85         if (pkt->needsWritable()) {
  86             needsWritable = true;
  87         }
  88
  89         // StoreCondReq is effectively an upgrade if it's in an MSHR
  90         // since it would have been failed already if we didn't have a
  91         // read-only copy
  92         if (pkt->isUpgrade() || pkt->cmd == MemCmd::StoreCondReq) {
  93             hasUpgrade = true;
  94         }
  95     }
  96
  97     if (markPending) {
  98         // Iterate over the SenderState stack and see if we find
  99         // an MSHR entry. If we do, set the downstreamPending
 100         // flag. Otherwise, do nothing.
 101         MSHR *mshr = pkt->findNextSenderState<MSHR>();
 102         if (mshr != NULL) {
 103             assert(!mshr->downstreamPending);
 104             mshr->downstreamPending = true;
 105         } else {
 106             // No need to clear downstreamPending later
 107             markPending = false;
 108         }
 109     }
 110
 111     emplace_back(pkt, readyTime, order, source, markPending);
 112 }
 113
 114
 115 static void
 116 replaceUpgrade(PacketPtr pkt)
 117 {
 118     // remember if the current packet has data allocated
 119     bool has_data = pkt->hasData() || pkt->hasRespData();
 120
 121     if (pkt->cmd == MemCmd::UpgradeReq) {
 122         pkt->cmd = MemCmd::ReadExReq;
 123         DPRINTF(Cache, "Replacing UpgradeReq with ReadExReq\n");
 124     } else if (pkt->cmd == MemCmd::SCUpgradeReq) {
 125         pkt->cmd = MemCmd::SCUpgradeFailReq;
 126         DPRINTF(Cache, "Replacing SCUpgradeReq with SCUpgradeFailReq\n");
 127     } else if (pkt->cmd == MemCmd::StoreCondReq) {
 128         pkt->cmd = MemCmd::StoreCondFailReq;
 129         DPRINTF(Cache, "Replacing StoreCondReq with StoreCondFailReq\n");
 130     }
 131
 132     if (!has_data) {
 133         // there is no sensible way of setting the data field if the
 134         // new command actually would carry data
 135         assert(!pkt->hasData());
 136
 137         if (pkt->hasRespData()) {
 138             // we went from a packet that had no data (neither request,
 139             // nor response), to one that does, and therefore we need to
 140             // actually allocate space for the data payload
 141             pkt->allocate();
 142         }
 143     }
 144 }
 145
 146
 147 void
 148 MSHR::TargetList::replaceUpgrades()
 149 {
 150     if (!hasUpgrade)
 151         return;
 152
 153     for (auto& t : *this) {
 154         replaceUpgrade(t.pkt);
 155     }
 156
 157     hasUpgrade = false;
 158 }
 159
 160
 161 void
 162 MSHR::TargetList::clearDownstreamPending()
 163 {
 164     for (auto& t : *this) {
 165         if (t.markedPending) {
 166             // Iterate over the SenderState stack and see if we find
 167             // an MSHR entry. If we find one, clear the
 168             // downstreamPending flag by calling
 169             // clearDownstreamPending(). This recursively clears the
 170             // downstreamPending flag in all caches this packet has
 171             // passed through.
 172             MSHR *mshr = t.pkt->findNextSenderState<MSHR>();
 173             if (mshr != NULL) {
 174                 mshr->clearDownstreamPending();
 175             }
 176         }
 177     }
 178 }
 179
 180
 181 bool
 182 MSHR::TargetList::checkFunctional(PacketPtr pkt)
 183 {
 184     for (auto& t : *this) {
 185         if (pkt->checkFunctional(t.pkt)) {
 186             return true;
 187         }
 188     }
 189
 190     return false;
 191 }
 192
 193
 194 void
 195 MSHR::TargetList::print(std::ostream &os, int verbosity,
 196                         const std::string &prefix) const
 197 {
 198     for (auto& t : *this) {
 199         const char *s;
 200         switch (t.source) {
 201           case Target::FromCPU:
 202             s = "FromCPU";
 203             break;
 204           case Target::FromSnoop:
 205             s = "FromSnoop";
 206             break;
 207           case Target::FromPrefetcher:
 208             s = "FromPrefetcher";
 209             break;
 210           default:
 211             s = "";
 212             break;
 213         }
 214         ccprintf(os, "%s%s: ", prefix, s);
 215         t.pkt->print(os, verbosity, "");
 216     }
 217 }
 218
 219
 220 void
 221 MSHR::allocate(Addr blk_addr, unsigned blk_size, PacketPtr target,
 222                Tick when_ready, Counter _order, bool alloc_on_fill)
 223 {
 224     blkAddr = blk_addr;
 225     blkSize = blk_size;
 226     isSecure = target->isSecure();
 227     readyTime = when_ready;
 228     order = _order;
 229     assert(target);
 230     isForward = false;
 231     allocOnFill = alloc_on_fill;
 232     _isUncacheable = target->req->isUncacheable();
 233     inService = false;
 234     downstreamPending = false;
 235     assert(targets.isReset());
 236     // Don't know of a case where we would allocate a new MSHR for a
 237     // snoop (mem-side request), so set source according to request here
 238     Target::Source source = (target->cmd == MemCmd::HardPFReq) ?
 239         Target::FromPrefetcher : Target::FromCPU;
 240     targets.add(target, when_ready, _order, source, true);
 241     assert(deferredTargets.isReset());
 242     data = NULL;
 243 }
 244
 245
 246 void
 247 MSHR::clearDownstreamPending()
 248 {
 249     assert(downstreamPending);
 250     downstreamPending = false;
 251     // recursively clear flag on any MSHRs we will be forwarding
 252     // responses to
 253     targets.clearDownstreamPending();
 254 }
 255
 256 bool
 257 MSHR::markInService(bool pending_modified_resp)
 258 {
 259     assert(!inService);
 260     if (isForwardNoResponse()) {
 261         // we just forwarded the request packet & don't expect a
 262         // response, so get rid of it
 263         assert(getNumTargets() == 1);
 264         popTarget();
 265         return true;
 266     }
 267
 268     inService = true;
 269     pendingModified = targets.needsWritable || pending_modified_resp;
 270     postInvalidate = postDowngrade = false;
 271
 272     if (!downstreamPending) {
 273         // let upstream caches know that the request has made it to a
 274         // level where it's going to get a response
 275         targets.clearDownstreamPending();
 276     }
 277     return false;
 278 }
 279
 280
 281 void
 282 MSHR::deallocate()
 283 {
 284     assert(targets.empty());
 285     targets.resetFlags();
 286     assert(deferredTargets.isReset());
 287     inService = false;
 288 }
 289
 290 /*
 291  * Adds a target to an MSHR
 292  */
 293 void
 294 MSHR::allocateTarget(PacketPtr pkt, Tick whenReady, Counter _order,
 295                      bool alloc_on_fill)
 296 {
 297     // assume we'd never issue a prefetch when we've got an
 298     // outstanding miss
 299     assert(pkt->cmd != MemCmd::HardPFReq);
 300
 301     // uncacheable accesses always allocate a new MSHR, and cacheable
 302     // accesses ignore any uncacheable MSHRs, thus we should never
 303     // have targets addded if originally allocated uncacheable
 304     assert(!_isUncacheable);
 305
 306     // potentially re-evaluate whether we should allocate on a fill or
 307     // not
 308     allocOnFill = allocOnFill || alloc_on_fill;
 309
 310     // if there's a request already in service for this MSHR, we will
 311     // have to defer the new target until after the response if any of
 312     // the following are true:
 313     // - there are other targets already deferred
 314     // - there's a pending invalidate to be applied after the response
 315     //   comes back (but before this target is processed)
 316     // - this target requires a writable block and either we're not
 317     //   getting a writable block back or we have already snooped
 318     //   another read request that will downgrade our writable block
 319     //   to non-writable (Shared or Owned)
 320     if (inService &&
 321         (!deferredTargets.empty() || hasPostInvalidate() ||
 322          (pkt->needsWritable() &&
 323           (!isPendingModified() || hasPostDowngrade() || isForward)))) {
 324         // need to put on deferred list
 325         if (hasPostInvalidate())
 326             replaceUpgrade(pkt);
 327         deferredTargets.add(pkt, whenReady, _order, Target::FromCPU, true);
 328     } else {
 329         // No request outstanding, or still OK to append to
 330         // outstanding request: append to regular target list.  Only
 331         // mark pending if current request hasn't been issued yet
 332         // (isn't in service).
 333         targets.add(pkt, whenReady, _order, Target::FromCPU, !inService);
 334     }
 335 }
 336
 337 bool
 338 MSHR::handleSnoop(PacketPtr pkt, Counter _order)
 339 {
 340     DPRINTF(Cache, "%s for %s addr %#llx size %d\n", __func__,
 341             pkt->cmdString(), pkt->getAddr(), pkt->getSize());
 342
 343     // when we snoop packets the needsWritable and isInvalidate flags
 344     // should always be the same, however, this assumes that we never
 345     // snoop writes as they are currently not marked as invalidations
 346     panic_if(pkt->needsWritable() != pkt->isInvalidate(),
 347              "%s got snoop %s to addr %#llx where needsWritable, "
 348              "does not match isInvalidate", name(), pkt->cmdString(),
 349              pkt->getAddr());
 350
 351     if (!inService || (pkt->isExpressSnoop() && downstreamPending)) {
 352         // Request has not been issued yet, or it's been issued
 353         // locally but is buffered unissued at some downstream cache
 354         // which is forwarding us this snoop.  Either way, the packet
 355         // we're snooping logically precedes this MSHR's request, so
 356         // the snoop has no impact on the MSHR, but must be processed
 357         // in the standard way by the cache.  The only exception is
 358         // that if we're an L2+ cache buffering an UpgradeReq from a
 359         // higher-level cache, and the snoop is invalidating, then our
 360         // buffered upgrades must be converted to read exclusives,
 361         // since the upper-level cache no longer has a valid copy.
 362         // That is, even though the upper-level cache got out on its
 363         // local bus first, some other invalidating transaction
 364         // reached the global bus before the upgrade did.
 365         if (pkt->needsWritable()) {
 366             targets.replaceUpgrades();
 367             deferredTargets.replaceUpgrades();
 368         }
 369
 370         return false;
 371     }
 372
 373     // From here on down, the request issued by this MSHR logically
 374     // precedes the request we're snooping.
 375     if (pkt->needsWritable()) {
 376         // snooped request still precedes the re-request we'll have to
 377         // issue for deferred targets, if any...
 378         deferredTargets.replaceUpgrades();
 379     }
 380
 381     if (hasPostInvalidate()) {
 382         // a prior snoop has already appended an invalidation, so
 383         // logically we don't have the block anymore; no need for
 384         // further snooping.
 385         return true;
 386     }
 387
 388     if (isPendingModified() || pkt->isInvalidate()) {
 389         // We need to save and replay the packet in two cases:
 390         // 1. We're awaiting a writable copy (Modified or Exclusive),
 391         //    so this MSHR is the orgering point, and we need to respond
 392         //    after we receive data.
 393         // 2. It's an invalidation (e.g., UpgradeReq), and we need
 394         //    to forward the snoop up the hierarchy after the current
 395         //    transaction completes.
 396
 397         // Start by determining if we will eventually respond or not,
 398         // matching the conditions checked in Cache::handleSnoop
 399         bool will_respond = isPendingModified() && pkt->needsResponse() &&
 400             pkt->cmd != MemCmd::InvalidateReq;
 401
 402         // The packet we are snooping may be deleted by the time we
 403         // actually process the target, and we consequently need to
 404         // save a copy here. Clear flags and also allocate new data as
 405         // the original packet data storage may have been deleted by
 406         // the time we get to process this packet. In the cases where
 407         // we are not responding after handling the snoop we also need
 408         // to create a copy of the request to be on the safe side. In
 409         // the latter case the cache is responsible for deleting both
 410         // the packet and the request as part of handling the deferred
 411         // snoop.
 412         PacketPtr cp_pkt = will_respond ? new Packet(pkt, true, true) :
 413             new Packet(new Request(*pkt->req), pkt->cmd);
 414
 415         if (isPendingModified()) {
 416             // we are the ordering point, and will consequently
 417             // respond, and depending on whether the packet
 418             // needsWritable or not we either pass a Shared line or a
 419             // Modified line
 420             pkt->setCacheResponding();
 421
 422             // inform the cache hierarchy that this cache had the line
 423             // in the Modified state, even if the response is passed
 424             // as Shared (and thus non-writable)
 425             pkt->setResponderHadWritable();
 426
 427             // in the case of an uncacheable request there is no need
 428             // to set the responderHadWritable flag, but since the
 429             // recipient does not care there is no harm in doing so
 430         }
 431         targets.add(cp_pkt, curTick(), _order, Target::FromSnoop,
 432                     downstreamPending && targets.needsWritable);
 433
 434         if (pkt->needsWritable()) {
 435             // This transaction will take away our pending copy
 436             postInvalidate = true;
 437         }
 438     }
 439
 440     if (!pkt->needsWritable() && !pkt->req->isUncacheable()) {
 441         // This transaction will get a read-shared copy, downgrading
 442         // our copy if we had a writable one
 443         postDowngrade = true;
 444         // make sure that any downstream cache does not respond with a
 445         // writable (and dirty) copy even if it has one, unless it was
 446         // explicitly asked for one
 447         pkt->setHasSharers();
 448     }
 449
 450     return true;
 451 }
 452
 453
 454 bool
 455 MSHR::promoteDeferredTargets()
 456 {
 457     assert(targets.empty());
 458     if (deferredTargets.empty()) {
 459         return false;
 460     }
 461
 462     // swap targets & deferredTargets lists
 463     std::swap(targets, deferredTargets);
 464
 465     // clear deferredTargets flags
 466     deferredTargets.resetFlags();
 467
 468     order = targets.front().order;
 469     readyTime = std::max(curTick(), targets.front().readyTime);
 470
 471     return true;
 472 }
 473
 474
 475 void
 476 MSHR::promoteWritable()
 477 {
 478     if (deferredTargets.needsWritable &&
 479         !(hasPostInvalidate() || hasPostDowngrade())) {
 480         // We got a writable response, but we have deferred targets
 481         // which are waiting to request a writable copy (not because
 482         // of a pending invalidate).  This can happen if the original
 483         // request was for a read-only block, but we got a writable
 484         // response anyway. Since we got the writable copy there's no
 485         // need to defer the targets, so move them up to the regular
 486         // target list.
 487         assert(!targets.needsWritable);
 488         targets.needsWritable = true;
 489         // if any of the deferred targets were upper-level cache
 490         // requests marked downstreamPending, need to clear that
 491         assert(!downstreamPending);  // not pending here anymore
 492         deferredTargets.clearDownstreamPending();
 493         // this clears out deferredTargets too
 494         targets.splice(targets.end(), deferredTargets);
 495         deferredTargets.resetFlags();
 496     }
 497 }
 498
 499
 500 bool
 501 MSHR::checkFunctional(PacketPtr pkt)
 502 {
 503     // For printing, we treat the MSHR as a whole as single entity.
 504     // For other requests, we iterate over the individual targets
 505     // since that's where the actual data lies.
 506     if (pkt->isPrint()) {
 507         pkt->checkFunctional(this, blkAddr, isSecure, blkSize, NULL);
 508         return false;
 509     } else {
 510         return (targets.checkFunctional(pkt) ||
 511                 deferredTargets.checkFunctional(pkt));
 512     }
 513 }
 514
 515
 516 void
 517 MSHR::print(std::ostream &os, int verbosity, const std::string &prefix) const
 518 {
 519     ccprintf(os, "%s[%#llx:%#llx](%s) %s %s %s state: %s %s %s %s %s\n",
 520              prefix, blkAddr, blkAddr + blkSize - 1,
 521              isSecure ? "s" : "ns",
 522              isForward ? "Forward" : "",
 523              allocOnFill ? "AllocOnFill" : "",
 524              isForwardNoResponse() ? "ForwNoResp" : "",
 525              needsWritable() ? "Wrtbl" : "",
 526              _isUncacheable ? "Unc" : "",
 527              inService ? "InSvc" : "",
 528              downstreamPending ? "DwnPend" : "",
 529              hasPostInvalidate() ? "PostInv" : "",
 530              hasPostDowngrade() ? "PostDowngr" : "");
 531
 532     ccprintf(os, "%s  Targets:\n", prefix);
 533     targets.print(os, verbosity, prefix + "    ");
 534     if (!deferredTargets.empty()) {
 535         ccprintf(os, "%s  Deferred Targets:\n", prefix);
 536         deferredTargets.print(os, verbosity, prefix + "      ");
 537     }
 538 }
 539
 540 std::string
 541 MSHR::print() const
 542 {
 543     ostringstream str;
 544     print(str);
 545     return str.str();
 546 }