src/mem/cache/mshr.cc

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