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                pendingDirty(false),
  66                postInvalidate(false), postDowngrade(false),
  67                queue(NULL), order(0), blkAddr(0),
  68                blkSize(0), isSecure(false), inService(false),
  69                isForward(false), threadNum(InvalidThreadID), data(NULL)
  70 {
  71 }
  72
  73
  74 MSHR::TargetList::TargetList()
  75     : needsExclusive(false), hasUpgrade(false)
  76 {}
  77
  78
  79 inline void
  80 MSHR::TargetList::add(PacketPtr pkt, Tick readyTime,
  81                       Counter order, Target::Source source, bool markPending)
  82 {
  83     if (source != Target::FromSnoop) {
  84         if (pkt->needsExclusive()) {
  85             needsExclusive = true;
  86         }
  87
  88         // StoreCondReq is effectively an upgrade if it's in an MSHR
  89         // since it would have been failed already if we didn't have a
  90         // read-only copy
  91         if (pkt->isUpgrade() || pkt->cmd == MemCmd::StoreCondReq) {
  92             hasUpgrade = true;
  93         }
  94     }
  95
  96     if (markPending) {
  97         // Iterate over the SenderState stack and see if we find
  98         // an MSHR entry. If we do, set the downstreamPending
  99         // flag. Otherwise, do nothing.
 100         MSHR *mshr = pkt->findNextSenderState<MSHR>();
 101         if (mshr != NULL) {
 102             assert(!mshr->downstreamPending);
 103             mshr->downstreamPending = true;
 104         } else {
 105             // No need to clear downstreamPending later
 106             markPending = false;
 107         }
 108     }
 109
 110     emplace_back(pkt, readyTime, order, source, markPending);
 111 }
 112
 113
 114 static void
 115 replaceUpgrade(PacketPtr pkt)
 116 {
 117     if (pkt->cmd == MemCmd::UpgradeReq) {
 118         pkt->cmd = MemCmd::ReadExReq;
 119         DPRINTF(Cache, "Replacing UpgradeReq with ReadExReq\n");
 120     } else if (pkt->cmd == MemCmd::SCUpgradeReq) {
 121         pkt->cmd = MemCmd::SCUpgradeFailReq;
 122         DPRINTF(Cache, "Replacing SCUpgradeReq with SCUpgradeFailReq\n");
 123     } else if (pkt->cmd == MemCmd::StoreCondReq) {
 124         pkt->cmd = MemCmd::StoreCondFailReq;
 125         DPRINTF(Cache, "Replacing StoreCondReq with StoreCondFailReq\n");
 126     }
 127 }
 128
 129
 130 void
 131 MSHR::TargetList::replaceUpgrades()
 132 {
 133     if (!hasUpgrade)
 134         return;
 135
 136     for (auto& t : *this) {
 137         replaceUpgrade(t.pkt);
 138     }
 139
 140     hasUpgrade = false;
 141 }
 142
 143
 144 void
 145 MSHR::TargetList::clearDownstreamPending()
 146 {
 147     for (auto& t : *this) {
 148         if (t.markedPending) {
 149             // Iterate over the SenderState stack and see if we find
 150             // an MSHR entry. If we find one, clear the
 151             // downstreamPending flag by calling
 152             // clearDownstreamPending(). This recursively clears the
 153             // downstreamPending flag in all caches this packet has
 154             // passed through.
 155             MSHR *mshr = t.pkt->findNextSenderState<MSHR>();
 156             if (mshr != NULL) {
 157                 mshr->clearDownstreamPending();
 158             }
 159         }
 160     }
 161 }
 162
 163
 164 bool
 165 MSHR::TargetList::checkFunctional(PacketPtr pkt)
 166 {
 167     for (auto& t : *this) {
 168         if (pkt->checkFunctional(t.pkt)) {
 169             return true;
 170         }
 171     }
 172
 173     return false;
 174 }
 175
 176
 177 void
 178 MSHR::TargetList::print(std::ostream &os, int verbosity,
 179                         const std::string &prefix) const
 180 {
 181     for (auto& t : *this) {
 182         const char *s;
 183         switch (t.source) {
 184           case Target::FromCPU:
 185             s = "FromCPU";
 186             break;
 187           case Target::FromSnoop:
 188             s = "FromSnoop";
 189             break;
 190           case Target::FromPrefetcher:
 191             s = "FromPrefetcher";
 192             break;
 193           default:
 194             s = "";
 195             break;
 196         }
 197         ccprintf(os, "%s%s: ", prefix, s);
 198         t.pkt->print(os, verbosity, "");
 199     }
 200 }
 201
 202
 203 void
 204 MSHR::allocate(Addr blk_addr, unsigned blk_size, PacketPtr target,
 205                Tick when_ready, Counter _order)
 206 {
 207     blkAddr = blk_addr;
 208     blkSize = blk_size;
 209     isSecure = target->isSecure();
 210     readyTime = when_ready;
 211     order = _order;
 212     assert(target);
 213     isForward = false;
 214     _isUncacheable = target->req->isUncacheable();
 215     inService = false;
 216     downstreamPending = false;
 217     threadNum = 0;
 218     assert(targets.isReset());
 219     // Don't know of a case where we would allocate a new MSHR for a
 220     // snoop (mem-side request), so set source according to request here
 221     Target::Source source = (target->cmd == MemCmd::HardPFReq) ?
 222         Target::FromPrefetcher : Target::FromCPU;
 223     targets.add(target, when_ready, _order, source, true);
 224     assert(deferredTargets.isReset());
 225     data = NULL;
 226 }
 227
 228
 229 void
 230 MSHR::clearDownstreamPending()
 231 {
 232     assert(downstreamPending);
 233     downstreamPending = false;
 234     // recursively clear flag on any MSHRs we will be forwarding
 235     // responses to
 236     targets.clearDownstreamPending();
 237 }
 238
 239 bool
 240 MSHR::markInService(bool pending_dirty_resp)
 241 {
 242     assert(!inService);
 243     if (isForwardNoResponse()) {
 244         // we just forwarded the request packet & don't expect a
 245         // response, so get rid of it
 246         assert(getNumTargets() == 1);
 247         popTarget();
 248         return true;
 249     }
 250
 251     inService = true;
 252     pendingDirty = targets.needsExclusive || pending_dirty_resp;
 253     postInvalidate = postDowngrade = false;
 254
 255     if (!downstreamPending) {
 256         // let upstream caches know that the request has made it to a
 257         // level where it's going to get a response
 258         targets.clearDownstreamPending();
 259     }
 260     return false;
 261 }
 262
 263
 264 void
 265 MSHR::deallocate()
 266 {
 267     assert(targets.empty());
 268     targets.resetFlags();
 269     assert(deferredTargets.isReset());
 270     inService = false;
 271 }
 272
 273 /*
 274  * Adds a target to an MSHR
 275  */
 276 void
 277 MSHR::allocateTarget(PacketPtr pkt, Tick whenReady, Counter _order)
 278 {
 279     // assume we'd never issue a prefetch when we've got an
 280     // outstanding miss
 281     assert(pkt->cmd != MemCmd::HardPFReq);
 282
 283     // uncacheable accesses always allocate a new MSHR, and cacheable
 284     // accesses ignore any uncacheable MSHRs, thus we should never
 285     // have targets addded if originally allocated uncacheable
 286     assert(!_isUncacheable);
 287
 288     // if there's a request already in service for this MSHR, we will
 289     // have to defer the new target until after the response if any of
 290     // the following are true:
 291     // - there are other targets already deferred
 292     // - there's a pending invalidate to be applied after the response
 293     //   comes back (but before this target is processed)
 294     // - this target requires an exclusive block and either we're not
 295     //   getting an exclusive block back or we have already snooped
 296     //   another read request that will downgrade our exclusive block
 297     //   to shared
 298     if (inService &&
 299         (!deferredTargets.empty() || hasPostInvalidate() ||
 300          (pkt->needsExclusive() &&
 301           (!isPendingDirty() || hasPostDowngrade() || isForward)))) {
 302         // need to put on deferred list
 303         if (hasPostInvalidate())
 304             replaceUpgrade(pkt);
 305         deferredTargets.add(pkt, whenReady, _order, Target::FromCPU, true);
 306     } else {
 307         // No request outstanding, or still OK to append to
 308         // outstanding request: append to regular target list.  Only
 309         // mark pending if current request hasn't been issued yet
 310         // (isn't in service).
 311         targets.add(pkt, whenReady, _order, Target::FromCPU, !inService);
 312     }
 313 }
 314
 315 bool
 316 MSHR::handleSnoop(PacketPtr pkt, Counter _order)
 317 {
 318     DPRINTF(Cache, "%s for %s addr %#llx size %d\n", __func__,
 319             pkt->cmdString(), pkt->getAddr(), pkt->getSize());
 320     if (!inService || (pkt->isExpressSnoop() && downstreamPending)) {
 321         // Request has not been issued yet, or it's been issued
 322         // locally but is buffered unissued at some downstream cache
 323         // which is forwarding us this snoop.  Either way, the packet
 324         // we're snooping logically precedes this MSHR's request, so
 325         // the snoop has no impact on the MSHR, but must be processed
 326         // in the standard way by the cache.  The only exception is
 327         // that if we're an L2+ cache buffering an UpgradeReq from a
 328         // higher-level cache, and the snoop is invalidating, then our
 329         // buffered upgrades must be converted to read exclusives,
 330         // since the upper-level cache no longer has a valid copy.
 331         // That is, even though the upper-level cache got out on its
 332         // local bus first, some other invalidating transaction
 333         // reached the global bus before the upgrade did.
 334         if (pkt->needsExclusive()) {
 335             targets.replaceUpgrades();
 336             deferredTargets.replaceUpgrades();
 337         }
 338
 339         return false;
 340     }
 341
 342     // From here on down, the request issued by this MSHR logically
 343     // precedes the request we're snooping.
 344     if (pkt->needsExclusive()) {
 345         // snooped request still precedes the re-request we'll have to
 346         // issue for deferred targets, if any...
 347         deferredTargets.replaceUpgrades();
 348     }
 349
 350     if (hasPostInvalidate()) {
 351         // a prior snoop has already appended an invalidation, so
 352         // logically we don't have the block anymore; no need for
 353         // further snooping.
 354         return true;
 355     }
 356
 357     if (isPendingDirty() || pkt->isInvalidate()) {
 358         // We need to save and replay the packet in two cases:
 359         // 1. We're awaiting an exclusive copy, so ownership is pending,
 360         //    and we need to respond after we receive data.
 361         // 2. It's an invalidation (e.g., UpgradeReq), and we need
 362         //    to forward the snoop up the hierarchy after the current
 363         //    transaction completes.
 364
 365         // Actual target device (typ. a memory) will delete the
 366         // packet on reception, so we need to save a copy here.
 367
 368         // Clear flags and also allocate new data as the original
 369         // packet data storage may have been deleted by the time we
 370         // get to send this packet.
 371         PacketPtr cp_pkt = nullptr;
 372
 373         if (isPendingDirty()) {
 374             // Case 1: The new packet will need to get the response from the
 375             // MSHR already queued up here
 376             cp_pkt = new Packet(pkt, true, true);
 377             pkt->assertMemInhibit();
 378             // in the case of an uncacheable request there is no need
 379             // to set the exclusive flag, but since the recipient does
 380             // not care there is no harm in doing so
 381             pkt->setSupplyExclusive();
 382         } else {
 383             // Case 2: We only need to buffer the packet for information
 384             // purposes; the original request can proceed without waiting
 385             // => Create a copy of the request, as that may get deallocated as
 386             // well
 387             cp_pkt = new Packet(new Request(*pkt->req), pkt->cmd);
 388             DPRINTF(Cache, "Copying packet %p -> %p and request %p -> %p\n",
 389                     pkt, cp_pkt, pkt->req, cp_pkt->req);
 390         }
 391         targets.add(cp_pkt, curTick(), _order, Target::FromSnoop,
 392                     downstreamPending && targets.needsExclusive);
 393
 394         if (pkt->needsExclusive()) {
 395             // This transaction will take away our pending copy
 396             postInvalidate = true;
 397         }
 398     }
 399
 400     if (!pkt->needsExclusive() && !pkt->req->isUncacheable()) {
 401         // This transaction will get a read-shared copy, downgrading
 402         // our copy if we had an exclusive one
 403         postDowngrade = true;
 404         pkt->assertShared();
 405     }
 406
 407     return true;
 408 }
 409
 410
 411 bool
 412 MSHR::promoteDeferredTargets()
 413 {
 414     assert(targets.empty());
 415     if (deferredTargets.empty()) {
 416         return false;
 417     }
 418
 419     // swap targets & deferredTargets lists
 420     std::swap(targets, deferredTargets);
 421
 422     // clear deferredTargets flags
 423     deferredTargets.resetFlags();
 424
 425     order = targets.front().order;
 426     readyTime = std::max(curTick(), targets.front().readyTime);
 427
 428     return true;
 429 }
 430
 431
 432 void
 433 MSHR::promoteExclusive()
 434 {
 435     if (deferredTargets.needsExclusive &&
 436         !(hasPostInvalidate() || hasPostDowngrade())) {
 437         // We got an exclusive response, but we have deferred targets
 438         // which are waiting to request an exclusive copy (not because
 439         // of a pending invalidate).  This can happen if the original
 440         // request was for a read-only (non-exclusive) block, but we
 441         // got an exclusive copy anyway because of the E part of the
 442         // MOESI/MESI protocol.  Since we got the exclusive copy
 443         // there's no need to defer the targets, so move them up to
 444         // the regular target list.
 445         assert(!targets.needsExclusive);
 446         targets.needsExclusive = true;
 447         // if any of the deferred targets were upper-level cache
 448         // requests marked downstreamPending, need to clear that
 449         assert(!downstreamPending);  // not pending here anymore
 450         deferredTargets.clearDownstreamPending();
 451         // this clears out deferredTargets too
 452         targets.splice(targets.end(), deferredTargets);
 453         deferredTargets.resetFlags();
 454     }
 455 }
 456
 457
 458 bool
 459 MSHR::checkFunctional(PacketPtr pkt)
 460 {
 461     // For printing, we treat the MSHR as a whole as single entity.
 462     // For other requests, we iterate over the individual targets
 463     // since that's where the actual data lies.
 464     if (pkt->isPrint()) {
 465         pkt->checkFunctional(this, blkAddr, isSecure, blkSize, NULL);
 466         return false;
 467     } else {
 468         return (targets.checkFunctional(pkt) ||
 469                 deferredTargets.checkFunctional(pkt));
 470     }
 471 }
 472
 473
 474 void
 475 MSHR::print(std::ostream &os, int verbosity, const std::string &prefix) const
 476 {
 477     ccprintf(os, "%s[%#llx:%#llx](%s) %s %s %s state: %s %s %s %s %s\n",
 478              prefix, blkAddr, blkAddr + blkSize - 1,
 479              isSecure ? "s" : "ns",
 480              isForward ? "Forward" : "",
 481              isForwardNoResponse() ? "ForwNoResp" : "",
 482              needsExclusive() ? "Excl" : "",
 483              _isUncacheable ? "Unc" : "",
 484              inService ? "InSvc" : "",
 485              downstreamPending ? "DwnPend" : "",
 486              hasPostInvalidate() ? "PostInv" : "",
 487              hasPostDowngrade() ? "PostDowngr" : "");
 488
 489     ccprintf(os, "%s  Targets:\n", prefix);
 490     targets.print(os, verbosity, prefix + "    ");
 491     if (!deferredTargets.empty()) {
 492         ccprintf(os, "%s  Deferred Targets:\n", prefix);
 493         deferredTargets.print(os, verbosity, prefix + "      ");
 494     }
 495 }
 496
 497 std::string
 498 MSHR::print() const
 499 {
 500     ostringstream str;
 501     print(str);
 502     return str.str();
 503 }