src/mem/cache/mshr.cc

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