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