src/mem/cache/coherence/coherence_protocol.cc

   1 /*
   2  * Copyright (c) 2002-2005 The Regents of The University of Michigan
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions are
   7  * met: redistributions of source code must retain the above copyright
   8  * notice, this list of conditions and the following disclaimer;
   9  * redistributions in binary form must reproduce the above copyright
  10  * notice, this list of conditions and the following disclaimer in the
  11  * documentation and/or other materials provided with the distribution;
  12  * neither the name of the copyright holders nor the names of its
  13  * contributors may be used to endorse or promote products derived from
  14  * this software without specific prior written permission.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  19  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  20  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  26  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  *
  28  * Authors: Erik Hallnor
  29  *          Steve Reinhardt
  30  *          Ron Dreslinski
  31  */
  32
  33 /**
  34  * @file
  35  * Definitions of CoherenceProtocol.
  36  */
  37
  38 #include <string>
  39
  40 #include "base/misc.hh"
  41 #include "mem/cache/miss/mshr.hh"
  42 #include "mem/cache/cache.hh"
  43 #include "mem/cache/coherence/coherence_protocol.hh"
  44 #include "sim/builder.hh"
  45
  46 using namespace std;
  47
  48
  49 CoherenceProtocol::StateTransition::StateTransition()
  50     : busCmd(Packet::InvalidCmd), newState(-1), snoopFunc(invalidTransition)
  51 {
  52 }
  53
  54
  55 void
  56 CoherenceProtocol::regStats()
  57 {
  58     // Even though we count all the possible transitions in the
  59     // requestCount and snoopCount arrays, most of these are invalid,
  60     // so we just select the interesting ones to print here.
  61
  62     requestCount[Invalid][Packet::ReadReq]
  63         .name(name() + ".read_invalid")
  64         .desc("read misses to invalid blocks")
  65         ;
  66
  67     requestCount[Invalid][Packet::WriteReq]
  68         .name(name() +".write_invalid")
  69         .desc("write misses to invalid blocks")
  70         ;
  71
  72     requestCount[Invalid][Packet::SoftPFReq]
  73         .name(name() +".swpf_invalid")
  74         .desc("soft prefetch misses to invalid blocks")
  75         ;
  76
  77     requestCount[Invalid][Packet::HardPFReq]
  78         .name(name() +".hwpf_invalid")
  79         .desc("hard prefetch misses to invalid blocks")
  80         ;
  81
  82     requestCount[Shared][Packet::WriteReq]
  83         .name(name() + ".write_shared")
  84         .desc("write misses to shared blocks")
  85         ;
  86
  87     requestCount[Owned][Packet::WriteReq]
  88         .name(name() + ".write_owned")
  89         .desc("write misses to owned blocks")
  90         ;
  91
  92     snoopCount[Shared][Packet::ReadReq]
  93         .name(name() + ".snoop_read_shared")
  94         .desc("read snoops on shared blocks")
  95         ;
  96
  97     snoopCount[Shared][Packet::ReadExReq]
  98         .name(name() + ".snoop_readex_shared")
  99         .desc("readEx snoops on shared blocks")
 100         ;
 101
 102     snoopCount[Shared][Packet::UpgradeReq]
 103         .name(name() + ".snoop_upgrade_shared")
 104         .desc("upgradee snoops on shared blocks")
 105         ;
 106
 107     snoopCount[Modified][Packet::ReadReq]
 108         .name(name() + ".snoop_read_modified")
 109         .desc("read snoops on modified blocks")
 110         ;
 111
 112     snoopCount[Modified][Packet::ReadExReq]
 113         .name(name() + ".snoop_readex_modified")
 114         .desc("readEx snoops on modified blocks")
 115         ;
 116
 117     snoopCount[Owned][Packet::ReadReq]
 118         .name(name() + ".snoop_read_owned")
 119         .desc("read snoops on owned blocks")
 120         ;
 121
 122     snoopCount[Owned][Packet::ReadExReq]
 123         .name(name() + ".snoop_readex_owned")
 124         .desc("readEx snoops on owned blocks")
 125         ;
 126
 127     snoopCount[Owned][Packet::UpgradeReq]
 128         .name(name() + ".snoop_upgrade_owned")
 129         .desc("upgrade snoops on owned blocks")
 130         ;
 131
 132     snoopCount[Exclusive][Packet::ReadReq]
 133         .name(name() + ".snoop_read_exclusive")
 134         .desc("read snoops on exclusive blocks")
 135         ;
 136
 137     snoopCount[Exclusive][Packet::ReadExReq]
 138         .name(name() + ".snoop_readex_exclusive")
 139         .desc("readEx snoops on exclusive blocks")
 140         ;
 141
 142     snoopCount[Shared][Packet::InvalidateReq]
 143         .name(name() + ".snoop_inv_shared")
 144         .desc("Invalidate snoops on shared blocks")
 145         ;
 146
 147     snoopCount[Owned][Packet::InvalidateReq]
 148         .name(name() + ".snoop_inv_owned")
 149         .desc("Invalidate snoops on owned blocks")
 150         ;
 151
 152     snoopCount[Exclusive][Packet::InvalidateReq]
 153         .name(name() + ".snoop_inv_exclusive")
 154         .desc("Invalidate snoops on exclusive blocks")
 155         ;
 156
 157     snoopCount[Modified][Packet::InvalidateReq]
 158         .name(name() + ".snoop_inv_modified")
 159         .desc("Invalidate snoops on modified blocks")
 160         ;
 161
 162     snoopCount[Invalid][Packet::InvalidateReq]
 163         .name(name() + ".snoop_inv_invalid")
 164         .desc("Invalidate snoops on invalid blocks")
 165         ;
 166
 167     snoopCount[Shared][Packet::WriteInvalidateReq]
 168         .name(name() + ".snoop_writeinv_shared")
 169         .desc("WriteInvalidate snoops on shared blocks")
 170         ;
 171
 172     snoopCount[Owned][Packet::WriteInvalidateReq]
 173         .name(name() + ".snoop_writeinv_owned")
 174         .desc("WriteInvalidate snoops on owned blocks")
 175         ;
 176
 177     snoopCount[Exclusive][Packet::WriteInvalidateReq]
 178         .name(name() + ".snoop_writeinv_exclusive")
 179         .desc("WriteInvalidate snoops on exclusive blocks")
 180         ;
 181
 182     snoopCount[Modified][Packet::WriteInvalidateReq]
 183         .name(name() + ".snoop_writeinv_modified")
 184         .desc("WriteInvalidate snoops on modified blocks")
 185         ;
 186
 187     snoopCount[Invalid][Packet::WriteInvalidateReq]
 188         .name(name() + ".snoop_writeinv_invalid")
 189         .desc("WriteInvalidate snoops on invalid blocks")
 190         ;
 191 }
 192
 193
 194 bool
 195 CoherenceProtocol::invalidateTrans(BaseCache *cache, PacketPtr &pkt,
 196                                    CacheBlk *blk, MSHR *mshr,
 197                                    CacheBlk::State & new_state)
 198 {
 199     // invalidate the block
 200     new_state = (blk->status & ~stateMask) | Invalid;
 201     return false;
 202 }
 203
 204
 205 bool
 206 CoherenceProtocol::supplyTrans(BaseCache *cache, PacketPtr &pkt,
 207                                CacheBlk *blk,
 208                                MSHR *mshr,
 209                                CacheBlk::State & new_state)
 210 {
 211     return true;
 212 }
 213
 214
 215 bool
 216 CoherenceProtocol::supplyAndGotoSharedTrans(BaseCache *cache, PacketPtr &pkt,
 217                                             CacheBlk *blk,
 218                                             MSHR *mshr,
 219                                             CacheBlk::State & new_state)
 220 {
 221     new_state = (blk->status & ~stateMask) | Shared;
 222     pkt->flags |= SHARED_LINE;
 223     return supplyTrans(cache, pkt, blk, mshr, new_state);
 224 }
 225
 226
 227 bool
 228 CoherenceProtocol::supplyAndGotoOwnedTrans(BaseCache *cache, PacketPtr &pkt,
 229                                            CacheBlk *blk,
 230                                            MSHR *mshr,
 231                                            CacheBlk::State & new_state)
 232 {
 233     new_state = (blk->status & ~stateMask) | Owned;
 234     pkt->flags |= SHARED_LINE;
 235     return supplyTrans(cache, pkt, blk, mshr, new_state);
 236 }
 237
 238
 239 bool
 240 CoherenceProtocol::supplyAndInvalidateTrans(BaseCache *cache, PacketPtr &pkt,
 241                                             CacheBlk *blk,
 242                                             MSHR *mshr,
 243                                             CacheBlk::State & new_state)
 244 {
 245     new_state = (blk->status & ~stateMask) | Invalid;
 246     return supplyTrans(cache, pkt, blk, mshr, new_state);
 247 }
 248
 249 bool
 250 CoherenceProtocol::assertShared(BaseCache *cache, PacketPtr &pkt,
 251                                             CacheBlk *blk,
 252                                             MSHR *mshr,
 253                                             CacheBlk::State & new_state)
 254 {
 255     new_state = (blk->status & ~stateMask) | Shared;
 256     pkt->flags |= SHARED_LINE;
 257     return false;
 258 }
 259
 260 CoherenceProtocol::CoherenceProtocol(const string &name,
 261                                      const string &protocol,
 262                                      const bool doUpgrades)
 263     : SimObject(name)
 264 {
 265     // Python should catch this, but in case it doesn't...
 266     if (!(protocol == "msi"  || protocol == "mesi" ||
 267           protocol == "mosi" || protocol == "moesi")) {
 268         fatal("CoherenceProtocol: unrecognized protocol %s\n",  protocol);
 269     }
 270
 271     bool hasOwned = (protocol == "mosi" || protocol == "moesi");
 272     bool hasExclusive = (protocol == "mesi" || protocol == "moesi");
 273
 274     if (hasOwned && !doUpgrades) {
 275         fatal("CoherenceProtocol: ownership protocols require upgrade "
 276               "transactions\n(write miss on owned block generates ReadExcl, "
 277               "which will clobber dirty block)\n");
 278     }
 279
 280     // set up a few shortcuts to save typing & visual clutter
 281     typedef Packet P;
 282     StateTransition (&tt)[stateMax+1][NUM_MEM_CMDS] = transitionTable;
 283
 284     P::Command writeToSharedCmd =  doUpgrades ? P::UpgradeReq : P::ReadExReq;
 285     P::Command writeToSharedResp = doUpgrades ? P::UpgradeReq : P::ReadExResp;
 286
 287     // Note that all transitions by default cause a panic.
 288     // Override the valid transitions with the appropriate actions here.
 289
 290     //
 291     // ----- incoming requests: specify outgoing bus request -----
 292     //
 293     tt[Invalid][P::ReadReq].onRequest(P::ReadReq);
 294     // we only support write allocate right now
 295     tt[Invalid][P::WriteReq].onRequest(P::ReadExReq);
 296     tt[Shared][P::WriteReq].onRequest(writeToSharedCmd);
 297     if (hasOwned) {
 298         tt[Owned][P::WriteReq].onRequest(writeToSharedCmd);
 299     }
 300
 301     // Prefetching causes a read
 302     tt[Invalid][P::SoftPFReq].onRequest(P::ReadReq);
 303     tt[Invalid][P::HardPFReq].onRequest(P::ReadReq);
 304
 305     //
 306     // ----- on response to given request: specify new state -----
 307     //
 308     tt[Invalid][P::ReadExResp].onResponse(Modified);
 309     tt[Shared][writeToSharedResp].onResponse(Modified);
 310     // Go to Exclusive state on read response if we have one (will
 311     // move into shared if the shared line is asserted in the
 312     // getNewState function)
 313     //
 314     // originally had this as:
 315     // tt[Invalid][P::ReadResp].onResponse(hasExclusive ? Exclusive: Shared);
 316     // ...but for some reason that caused a link error...
 317     if (hasExclusive) {
 318         tt[Invalid][P::ReadResp].onResponse(Exclusive);
 319     } else {
 320         tt[Invalid][P::ReadResp].onResponse(Shared);
 321     }
 322     if (hasOwned) {
 323         tt[Owned][writeToSharedResp].onResponse(Modified);
 324     }
 325
 326     //
 327     // ----- bus snoop transition functions -----
 328     //
 329     tt[Invalid][P::ReadReq].onSnoop(nullTransition);
 330     tt[Invalid][P::ReadExReq].onSnoop(nullTransition);
 331     tt[Invalid][P::InvalidateReq].onSnoop(invalidateTrans);
 332     tt[Invalid][P::WriteInvalidateReq].onSnoop(invalidateTrans);
 333     tt[Shared][P::ReadReq].onSnoop(hasExclusive
 334                                    ? assertShared : nullTransition);
 335     tt[Shared][P::ReadExReq].onSnoop(invalidateTrans);
 336     tt[Shared][P::InvalidateReq].onSnoop(invalidateTrans);
 337     tt[Shared][P::WriteInvalidateReq].onSnoop(invalidateTrans);
 338     if (doUpgrades) {
 339         tt[Invalid][P::UpgradeReq].onSnoop(nullTransition);
 340         tt[Shared][P::UpgradeReq].onSnoop(invalidateTrans);
 341     }
 342     tt[Modified][P::ReadExReq].onSnoop(supplyAndInvalidateTrans);
 343     tt[Modified][P::ReadReq].onSnoop(hasOwned
 344                                      ? supplyAndGotoOwnedTrans
 345                                      : supplyAndGotoSharedTrans);
 346     tt[Modified][P::InvalidateReq].onSnoop(invalidateTrans);
 347     tt[Modified][P::WriteInvalidateReq].onSnoop(invalidateTrans);
 348
 349     if (hasExclusive) {
 350         tt[Exclusive][P::ReadReq].onSnoop(assertShared);
 351         tt[Exclusive][P::ReadExReq].onSnoop(invalidateTrans);
 352         tt[Exclusive][P::InvalidateReq].onSnoop(invalidateTrans);
 353         tt[Exclusive][P::WriteInvalidateReq].onSnoop(invalidateTrans);
 354     }
 355
 356     if (hasOwned) {
 357         tt[Owned][P::ReadReq].onSnoop(supplyAndGotoOwnedTrans);
 358         tt[Owned][P::ReadExReq].onSnoop(supplyAndInvalidateTrans);
 359         tt[Owned][P::UpgradeReq].onSnoop(invalidateTrans);
 360         tt[Owned][P::InvalidateReq].onSnoop(invalidateTrans);
 361         tt[Owned][P::WriteInvalidateReq].onSnoop(invalidateTrans);
 362     }
 363
 364     // @todo add in hardware prefetch to this list
 365 }
 366
 367
 368 Packet::Command
 369 CoherenceProtocol::getBusCmd(Packet::Command cmdIn, CacheBlk::State state,
 370                              MSHR *mshr)
 371 {
 372     state &= stateMask;
 373     int cmd_idx = (int) cmdIn;
 374
 375     assert(0 <= state && state <= stateMax);
 376     assert(0 <= cmd_idx && cmd_idx < NUM_MEM_CMDS);
 377
 378     Packet::Command cmdOut = transitionTable[state][cmd_idx].busCmd;
 379
 380     assert(cmdOut != Packet::InvalidCmd);
 381
 382     ++requestCount[state][cmd_idx];
 383
 384     return cmdOut;
 385 }
 386
 387
 388 CacheBlk::State
 389 CoherenceProtocol::getNewState(PacketPtr &pkt, CacheBlk::State oldState)
 390 {
 391     CacheBlk::State state = oldState & stateMask;
 392     int cmd_idx = pkt->cmdToIndex();
 393
 394     assert(0 <= state && state <= stateMax);
 395     assert(0 <= cmd_idx && cmd_idx < NUM_MEM_CMDS);
 396
 397     CacheBlk::State newState = transitionTable[state][cmd_idx].newState;
 398
 399     //Check if it's exclusive and the shared line was asserted,
 400     //then  goto shared instead
 401     if (newState == Exclusive && (pkt->flags & SHARED_LINE)) {
 402         newState = Shared;
 403     }
 404
 405     assert(newState != -1);
 406
 407     //Make sure not to loose any other state information
 408     newState = (oldState & ~stateMask) | newState;
 409     return newState;
 410 }
 411
 412
 413 bool
 414 CoherenceProtocol::handleBusRequest(BaseCache *cache, PacketPtr &pkt,
 415                                     CacheBlk *blk,
 416                                     MSHR *mshr,
 417                                     CacheBlk::State & new_state)
 418 {
 419     if (blk == NULL) {
 420         // nothing to do if we don't have a block
 421         return false;
 422     }
 423
 424     CacheBlk::State state = blk->status & stateMask;
 425     int cmd_idx = pkt->cmdToIndex();
 426
 427     assert(0 <= state && state <= stateMax);
 428     assert(0 <= cmd_idx && cmd_idx < NUM_MEM_CMDS);
 429
 430 //    assert(mshr == NULL); // can't currently handle outstanding requests
 431     //Check first if MSHR, and also insure, if there is one, that it is not in service
 432     assert(!mshr || mshr->inService == 0);
 433     ++snoopCount[state][cmd_idx];
 434
 435     bool ret = transitionTable[state][cmd_idx].snoopFunc(cache, pkt, blk, mshr,
 436                                                      new_state);
 437
 438
 439
 440     return ret;
 441 }
 442
 443 bool
 444 CoherenceProtocol::nullTransition(BaseCache *cache, PacketPtr &pkt,
 445                                   CacheBlk *blk, MSHR *mshr,
 446                                   CacheBlk::State & new_state)
 447 {
 448     // do nothing
 449     if (blk)
 450         new_state = blk->status;
 451     return false;
 452 }
 453
 454
 455 bool
 456 CoherenceProtocol::invalidTransition(BaseCache *cache, PacketPtr &pkt,
 457                                      CacheBlk *blk, MSHR *mshr,
 458                                      CacheBlk::State & new_state)
 459 {
 460     panic("Invalid transition");
 461     return false;
 462 }
 463
 464 #ifndef DOXYGEN_SHOULD_SKIP_THIS
 465
 466 BEGIN_DECLARE_SIM_OBJECT_PARAMS(CoherenceProtocol)
 467
 468     Param<string> protocol;
 469     Param<bool> do_upgrades;
 470
 471 END_DECLARE_SIM_OBJECT_PARAMS(CoherenceProtocol)
 472
 473
 474 BEGIN_INIT_SIM_OBJECT_PARAMS(CoherenceProtocol)
 475
 476     INIT_PARAM(protocol, "name of coherence protocol"),
 477     INIT_PARAM_DFLT(do_upgrades, "use upgrade transactions?", true)
 478
 479 END_INIT_SIM_OBJECT_PARAMS(CoherenceProtocol)
 480
 481
 482 CREATE_SIM_OBJECT(CoherenceProtocol)
 483 {
 484     return new CoherenceProtocol(getInstanceName(), protocol,
 485                                  do_upgrades);
 486 }
 487
 488 REGISTER_SIM_OBJECT("CoherenceProtocol", CoherenceProtocol)
 489
 490 #endif // DOXYGEN_SHOULD_SKIP_THIS