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