src/mem/protocol/MOESI_SMP_directory-cache.sm

   1
   2 /*
   3  * Copyright (c) 1999-2005 Mark D. Hill and David A. Wood
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions are
   8  * met: redistributions of source code must retain the above copyright
   9  * notice, this list of conditions and the following disclaimer;
  10  * redistributions in binary form must reproduce the above copyright
  11  * notice, this list of conditions and the following disclaimer in the
  12  * documentation and/or other materials provided with the distribution;
  13  * neither the name of the copyright holders nor the names of its
  14  * contributors may be used to endorse or promote products derived from
  15  * this software without specific prior written permission.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  18  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  19  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  20  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  21  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  22  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  23  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  24  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  25  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  26  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  27  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  28  */
  29
  30 /*
  31  * $Id$
  32  *
  33  */
  34
  35 machine(L1Cache, "Directory protocol") {
  36
  37   MessageBuffer requestFromCache, network="To", virtual_network="0", ordered="false";
  38   MessageBuffer responseFromCache, network="To", virtual_network="2", ordered="false";
  39   MessageBuffer unblockFromCache, network="To", virtual_network="3", ordered="false";
  40
  41   MessageBuffer forwardToCache, network="From", virtual_network="1", ordered="false";
  42   MessageBuffer responseToCache, network="From", virtual_network="2", ordered="false";
  43
  44   // STATES
  45   enumeration(State, desc="Cache states", default="L1Cache_State_I") {
  46     // Base states
  47     NP, desc="Not Present";
  48     I, desc="Idle";
  49     S, desc="Shared";
  50     O, desc="Owned";
  51     E, desc="Exclusive (clean)";
  52     M, desc="Modified (dirty)";
  53     MM, desc="Modified (dirty and locally modified)";
  54
  55     // Transient States
  56     IM, "IM", desc="Issued GetX";
  57     SM, "SM", desc="Issued GetX, we still have an old copy of the line";
  58     OM, "OM", desc="Issued GetX, received data";
  59     IS, "IS", desc="Issued GetS";
  60     OI, "OI", desc="Issued PutO, waiting for ack";
  61     MI, "MI", desc="Issued PutX, waiting for ack";
  62     II, "II", desc="Issued PutX/O, saw Fwd_GETS or Fwd_GETX, waiting for ack";
  63   }
  64
  65   // EVENTS
  66   enumeration(Event, desc="Cache events") {
  67     Load,            desc="Load request from the processor";
  68     Ifetch,          desc="I-fetch request from the processor";
  69     Store,           desc="Store request from the processor";
  70     L2_Replacement,  desc="Replacement";
  71     L1_to_L2,        desc="L1 to L2 transfer";
  72     L2_to_L1D,       desc="L2 to L1-Data transfer";
  73     L2_to_L1I,       desc="L2 to L1-Instruction transfer";
  74
  75     // Requests
  76     Own_GETX,      desc="We observe our own GetX forwarded back to us";
  77     Fwd_GETX,      desc="A GetX from another processor";
  78     Fwd_GETS,      desc="A GetS from another processor";
  79     Inv,           desc="Invalidations from the directory";
  80
  81     // Responses
  82     Ack,             desc="Received an ack message";
  83     Data,            desc="Received a data message, responder has a shared copy";
  84     Exclusive_Data_Clean,  desc="Received a data message, no other processor has it, data is clean";
  85     Exclusive_Data_Dirty,  desc="Received a data message, no other processor has it, data is dirty";
  86
  87     Writeback_Ack,   desc="Writeback O.K. from directory";
  88     Writeback_Nack,  desc="Writeback not O.K. from directory";
  89
  90     // Triggers
  91     All_acks,                  desc="Received all required data and message acks";
  92   }
  93
  94   // TYPES
  95
  96   // CacheEntry
  97   structure(Entry, desc="...", interface="AbstractCacheEntry") {
  98     State CacheState,        desc="cache state";
  99     bool Dirty,              desc="Is the data dirty (different than memory)?";
 100     DataBlock DataBlk,       desc="data for the block";
 101   }
 102
 103   // TBE fields
 104   structure(TBE, desc="...") {
 105     State TBEState,          desc="Transient state";
 106     DataBlock DataBlk,       desc="data for the block, required for concurrent writebacks";
 107     bool Dirty,              desc="Is the data dirty (different than memory)?";
 108     int NumPendingMsgs, default="0",     desc="Number of acks/data messages that this processor is waiting for";
 109   }
 110
 111   external_type(CacheMemory) {
 112     bool cacheAvail(Address);
 113     Address cacheProbe(Address);
 114     void allocate(Address);
 115     void deallocate(Address);
 116     Entry lookup(Address);
 117     void changePermission(Address, AccessPermission);
 118     bool isTagPresent(Address);
 119   }
 120
 121   external_type(TBETable) {
 122     TBE lookup(Address);
 123     void allocate(Address);
 124     void deallocate(Address);
 125     bool isPresent(Address);
 126   }
 127
 128   MessageBuffer mandatoryQueue, abstract_chip_ptr="true", ordered="false";
 129   Sequencer sequencer, abstract_chip_ptr="true", constructor_hack="i";
 130   StoreBuffer storeBuffer, abstract_chip_ptr="true", constructor_hack="i";
 131
 132   TBETable TBEs, template_hack="<L1Cache_TBE>";
 133   CacheMemory L1IcacheMemory, template_hack="<L1Cache_Entry>", constructor_hack='L1_CACHE_NUM_SETS_BITS,L1_CACHE_ASSOC,MachineType_L1Cache,int_to_string(i)+"_L1I"', abstract_chip_ptr="true";
 134   CacheMemory L1DcacheMemory, template_hack="<L1Cache_Entry>", constructor_hack='L1_CACHE_NUM_SETS_BITS,L1_CACHE_ASSOC,MachineType_L1Cache,int_to_string(i)+"_L1D"', abstract_chip_ptr="true";
 135   CacheMemory L2cacheMemory, template_hack="<L1Cache_Entry>", constructor_hack='L2_CACHE_NUM_SETS_BITS,L2_CACHE_ASSOC,MachineType_L1Cache,int_to_string(i)+"_L2"', abstract_chip_ptr="true";
 136
 137   Entry getCacheEntry(Address addr), return_by_ref="yes" {
 138     if (L2cacheMemory.isTagPresent(addr)) {
 139       return L2cacheMemory[addr];
 140     } else if (L1DcacheMemory.isTagPresent(addr)) {
 141       return L1DcacheMemory[addr];
 142     } else {
 143       return L1IcacheMemory[addr];
 144     }
 145   }
 146
 147   void changePermission(Address addr, AccessPermission permission) {
 148     if (L2cacheMemory.isTagPresent(addr)) {
 149       return L2cacheMemory.changePermission(addr, permission);
 150     } else if (L1DcacheMemory.isTagPresent(addr)) {
 151       return L1DcacheMemory.changePermission(addr, permission);
 152     } else {
 153       return L1IcacheMemory.changePermission(addr, permission);
 154     }
 155   }
 156
 157   bool isCacheTagPresent(Address addr) {
 158     return (L2cacheMemory.isTagPresent(addr) || L1DcacheMemory.isTagPresent(addr) || L1IcacheMemory.isTagPresent(addr));
 159   }
 160
 161   State getState(Address addr) {
 162     assert((L1DcacheMemory.isTagPresent(addr) && L1IcacheMemory.isTagPresent(addr)) == false);
 163     assert((L1IcacheMemory.isTagPresent(addr) && L2cacheMemory.isTagPresent(addr)) == false);
 164     assert((L1DcacheMemory.isTagPresent(addr) && L2cacheMemory.isTagPresent(addr)) == false);
 165
 166     if(TBEs.isPresent(addr)) {
 167       return TBEs[addr].TBEState;
 168     } else if (isCacheTagPresent(addr)) {
 169       return getCacheEntry(addr).CacheState;
 170     }
 171     return State:NP;
 172   }
 173
 174   void setState(Address addr, State state) {
 175     assert((L1DcacheMemory.isTagPresent(addr) && L1IcacheMemory.isTagPresent(addr)) == false);
 176     assert((L1IcacheMemory.isTagPresent(addr) && L2cacheMemory.isTagPresent(addr)) == false);
 177     assert((L1DcacheMemory.isTagPresent(addr) && L2cacheMemory.isTagPresent(addr)) == false);
 178
 179     if (TBEs.isPresent(addr)) {
 180       TBEs[addr].TBEState := state;
 181     }
 182
 183     if (isCacheTagPresent(addr)) {
 184       getCacheEntry(addr).CacheState := state;
 185
 186       if (state == State:E) {
 187         assert(getCacheEntry(addr).Dirty == false);
 188       }
 189
 190       if ((state == State:M) || (state == State:MM)) {
 191         assert(getCacheEntry(addr).Dirty == true);
 192       }
 193
 194       // Set permission
 195       if (state == State:MM) {
 196         changePermission(addr, AccessPermission:Read_Write);
 197       } else if ((state == State:S) ||
 198                  (state == State:O) ||
 199                  (state == State:M) ||
 200                  (state == State:E) ||
 201                  (state == State:SM) ||
 202                  (state == State:OM)) {
 203         changePermission(addr, AccessPermission:Read_Only);
 204       } else {
 205         changePermission(addr, AccessPermission:Invalid);
 206       }
 207     }
 208   }
 209
 210   Event mandatory_request_type_to_event(CacheRequestType type) {
 211     if (type == CacheRequestType:LD) {
 212       return Event:Load;
 213     } else if (type == CacheRequestType:IFETCH) {
 214       return Event:Ifetch;
 215     } else if ((type == CacheRequestType:ST) || (type == CacheRequestType:ATOMIC)) {
 216       return Event:Store;
 217     } else {
 218       error("Invalid CacheRequestType");
 219     }
 220   }
 221
 222   MessageBuffer triggerQueue, ordered="true";
 223
 224   // ** OUT_PORTS **
 225
 226   out_port(requestNetwork_out, RequestMsg, requestFromCache);
 227   out_port(responseNetwork_out, ResponseMsg, responseFromCache);
 228   out_port(unblockNetwork_out, ResponseMsg, unblockFromCache);
 229   out_port(triggerQueue_out, TriggerMsg, triggerQueue);
 230
 231   // ** IN_PORTS **
 232
 233   // Trigger Queue
 234   in_port(triggerQueue_in, TriggerMsg, triggerQueue) {
 235     if (triggerQueue_in.isReady()) {
 236       peek(triggerQueue_in, TriggerMsg) {
 237         if (in_msg.Type == TriggerType:ALL_ACKS) {
 238           trigger(Event:All_acks, in_msg.Address);
 239         } else {
 240           error("Unexpected message");
 241         }
 242       }
 243     }
 244   }
 245
 246   // Nothing from the request network
 247
 248   // Forward Network
 249   in_port(forwardToCache_in, RequestMsg, forwardToCache) {
 250     if (forwardToCache_in.isReady()) {
 251       peek(forwardToCache_in, RequestMsg) {
 252         if (in_msg.Type == CoherenceRequestType:GETX) {
 253           if (in_msg.Requestor == machineID) {
 254             trigger(Event:Own_GETX, in_msg.Address);
 255           } else {
 256             trigger(Event:Fwd_GETX, in_msg.Address);
 257           }
 258         } else if (in_msg.Type == CoherenceRequestType:GETS) {
 259           trigger(Event:Fwd_GETS, in_msg.Address);
 260         } else if (in_msg.Type == CoherenceRequestType:INV) {
 261           trigger(Event:Inv, in_msg.Address);
 262         } else if (in_msg.Type == CoherenceRequestType:WB_ACK) {
 263           trigger(Event:Writeback_Ack, in_msg.Address);
 264         } else if (in_msg.Type == CoherenceRequestType:WB_NACK) {
 265           trigger(Event:Writeback_Nack, in_msg.Address);
 266         } else {
 267           error("Unexpected message");
 268         }
 269       }
 270     }
 271   }
 272
 273   // Response Network
 274   in_port(responseToCache_in, ResponseMsg, responseToCache) {
 275     if (responseToCache_in.isReady()) {
 276       peek(responseToCache_in, ResponseMsg) {
 277         if (in_msg.Type == CoherenceResponseType:ACK) {
 278           trigger(Event:Ack, in_msg.Address);
 279         } else if (in_msg.Type == CoherenceResponseType:DATA) {
 280           trigger(Event:Data, in_msg.Address);
 281         } else if (in_msg.Type == CoherenceResponseType:DATA_EXCLUSIVE_CLEAN) {
 282           trigger(Event:Exclusive_Data_Clean, in_msg.Address);
 283         } else if (in_msg.Type == CoherenceResponseType:DATA_EXCLUSIVE_DIRTY) {
 284           trigger(Event:Exclusive_Data_Dirty, in_msg.Address);
 285         } else {
 286           error("Unexpected message");
 287         }
 288       }
 289     }
 290   }
 291
 292   // Nothing from the unblock network
 293
 294   // Mandatory Queue
 295   in_port(mandatoryQueue_in, CacheMsg, mandatoryQueue, desc="...") {
 296     if (mandatoryQueue_in.isReady()) {
 297       peek(mandatoryQueue_in, CacheMsg) {
 298
 299         // Check for data access to blocks in I-cache and ifetchs to blocks in D-cache
 300
 301         if (in_msg.Type == CacheRequestType:IFETCH) {
 302           // ** INSTRUCTION ACCESS ***
 303
 304           // Check to see if it is in the OTHER L1
 305           if (L1DcacheMemory.isTagPresent(in_msg.Address)) {
 306             // The block is in the wrong L1, try to write it to the L2
 307             if (L2cacheMemory.cacheAvail(in_msg.Address)) {
 308               trigger(Event:L1_to_L2, in_msg.Address);
 309             } else {
 310               trigger(Event:L2_Replacement, L2cacheMemory.cacheProbe(in_msg.Address));
 311             }
 312           }
 313
 314           if (L1IcacheMemory.isTagPresent(in_msg.Address)) {
 315             // The tag matches for the L1, so the L1 fetches the line.  We know it can't be in the L2 due to exclusion
 316             trigger(mandatory_request_type_to_event(in_msg.Type), in_msg.Address);
 317           } else {
 318             if (L1IcacheMemory.cacheAvail(in_msg.Address)) {
 319               // L1 does't have the line, but we have space for it in the L1
 320               if (L2cacheMemory.isTagPresent(in_msg.Address)) {
 321                 // L2 has it (maybe not with the right permissions)
 322                 trigger(Event:L2_to_L1I, in_msg.Address);
 323               } else {
 324                 // We have room, the L2 doesn't have it, so the L1 fetches the line
 325                 trigger(mandatory_request_type_to_event(in_msg.Type), in_msg.Address);
 326               }
 327             } else {
 328               // No room in the L1, so we need to make room
 329               if (L2cacheMemory.cacheAvail(L1IcacheMemory.cacheProbe(in_msg.Address))) {
 330                 // The L2 has room, so we move the line from the L1 to the L2
 331                 trigger(Event:L1_to_L2, L1IcacheMemory.cacheProbe(in_msg.Address));
 332               } else {
 333                 // The L2 does not have room, so we replace a line from the L2
 334                 trigger(Event:L2_Replacement, L2cacheMemory.cacheProbe(L1IcacheMemory.cacheProbe(in_msg.Address)));
 335               }
 336             }
 337           }
 338         } else {
 339           // *** DATA ACCESS ***
 340
 341           // Check to see if it is in the OTHER L1
 342           if (L1IcacheMemory.isTagPresent(in_msg.Address)) {
 343             // The block is in the wrong L1, try to write it to the L2
 344             if (L2cacheMemory.cacheAvail(in_msg.Address)) {
 345               trigger(Event:L1_to_L2, in_msg.Address);
 346             } else {
 347               trigger(Event:L2_Replacement, L2cacheMemory.cacheProbe(in_msg.Address));
 348             }
 349           }
 350
 351           if (L1DcacheMemory.isTagPresent(in_msg.Address)) {
 352             // The tag matches for the L1, so the L1 fetches the line.  We know it can't be in the L2 due to exclusion
 353             trigger(mandatory_request_type_to_event(in_msg.Type), in_msg.Address);
 354           } else {
 355             if (L1DcacheMemory.cacheAvail(in_msg.Address)) {
 356               // L1 does't have the line, but we have space for it in the L1
 357               if (L2cacheMemory.isTagPresent(in_msg.Address)) {
 358                 // L2 has it (maybe not with the right permissions)
 359                 trigger(Event:L2_to_L1D, in_msg.Address);
 360               } else {
 361                 // We have room, the L2 doesn't have it, so the L1 fetches the line
 362                 trigger(mandatory_request_type_to_event(in_msg.Type), in_msg.Address);
 363               }
 364             } else {
 365               // No room in the L1, so we need to make room
 366               if (L2cacheMemory.cacheAvail(L1DcacheMemory.cacheProbe(in_msg.Address))) {
 367                 // The L2 has room, so we move the line from the L1 to the L2
 368                 trigger(Event:L1_to_L2, L1DcacheMemory.cacheProbe(in_msg.Address));
 369               } else {
 370                 // The L2 does not have room, so we replace a line from the L2
 371                 trigger(Event:L2_Replacement, L2cacheMemory.cacheProbe(L1DcacheMemory.cacheProbe(in_msg.Address)));
 372               }
 373             }
 374           }
 375         }
 376       }
 377     }
 378   }
 379
 380   // ACTIONS
 381
 382   action(a_issueGETS, "a", desc="Issue GETS") {
 383     enqueue(requestNetwork_out, RequestMsg, latency="ISSUE_LATENCY") {
 384       out_msg.Address := address;
 385       out_msg.Type := CoherenceRequestType:GETS;
 386       out_msg.Requestor := machineID;
 387       out_msg.Destination.add(map_Address_to_Directory(address));
 388       out_msg.MessageSize := MessageSizeType:Request_Control;
 389       //      TBEs[address].NumPendingMsgs := numberOfNodes(); // One from each other processor (n-1) plus the memory (+1)
 390     }
 391   }
 392
 393   action(b_issueGETX, "b", desc="Issue GETX") {
 394     enqueue(requestNetwork_out, RequestMsg, latency="(ISSUE_LATENCY-1)") {
 395       out_msg.Address := address;
 396       out_msg.Type := CoherenceRequestType:GETX;
 397       out_msg.Requestor := machineID;
 398       out_msg.Destination.add(map_Address_to_Directory(address));
 399       out_msg.MessageSize := MessageSizeType:Request_Control;
 400       //      TBEs[address].NumPendingMsgs := numberOfNodes(); // One from each other processor (n-1) plus the memory (+1)
 401     }
 402   }
 403
 404   action(d_issuePUTX, "d", desc="Issue PUTX") {
 405     enqueue(requestNetwork_out, RequestMsg, latency="ISSUE_LATENCY") {
 406       out_msg.Address := address;
 407       out_msg.Type := CoherenceRequestType:PUTX;
 408       out_msg.Requestor := machineID;
 409       out_msg.Destination.add(map_Address_to_Directory(address));
 410       out_msg.MessageSize := MessageSizeType:Writeback_Control;
 411     }
 412   }
 413
 414   action(dd_issuePUTO, "\d", desc="Issue PUTO") {
 415     enqueue(requestNetwork_out, RequestMsg, latency="ISSUE_LATENCY") {
 416       out_msg.Address := address;
 417       out_msg.Type := CoherenceRequestType:PUTO;
 418       out_msg.Requestor := machineID;
 419       out_msg.Destination.add(map_Address_to_Directory(address));
 420       out_msg.MessageSize := MessageSizeType:Writeback_Control;
 421     }
 422   }
 423
 424   action(e_sendData, "e", desc="Send data from cache to requestor") {
 425     peek(forwardToCache_in, RequestMsg) {
 426       enqueue(responseNetwork_out, ResponseMsg, latency="CACHE_RESPONSE_LATENCY") {
 427         out_msg.Address := address;
 428         out_msg.Type := CoherenceResponseType:DATA;
 429         out_msg.Sender := machineID;
 430         out_msg.Destination.add(in_msg.Requestor);
 431         out_msg.DataBlk := getCacheEntry(address).DataBlk;
 432         out_msg.Dirty := getCacheEntry(address).Dirty;
 433         out_msg.Acks := in_msg.Acks;
 434         out_msg.MessageSize := MessageSizeType:Response_Data;
 435       }
 436     }
 437   }
 438
 439   action(ee_sendDataExclusive, "\e", desc="Send data from cache to requestor, don't keep a shared copy") {
 440     peek(forwardToCache_in, RequestMsg) {
 441       enqueue(responseNetwork_out, ResponseMsg, latency="CACHE_RESPONSE_LATENCY") {
 442         out_msg.Address := address;
 443         out_msg.Type := CoherenceResponseType:DATA_EXCLUSIVE_DIRTY;
 444         out_msg.Sender := machineID;
 445         out_msg.Destination.add(in_msg.Requestor);
 446         out_msg.DataBlk := getCacheEntry(address).DataBlk;
 447         out_msg.Dirty := getCacheEntry(address).Dirty;
 448         out_msg.Acks := in_msg.Acks;
 449         out_msg.MessageSize := MessageSizeType:Response_Data;
 450       }
 451     }
 452   }
 453
 454   action(f_sendAck, "f", desc="Send ack from cache to requestor") {
 455     peek(forwardToCache_in, RequestMsg) {
 456       enqueue(responseNetwork_out, ResponseMsg, latency="CACHE_RESPONSE_LATENCY") {
 457         out_msg.Address := address;
 458         out_msg.Type := CoherenceResponseType:ACK;
 459         out_msg.Sender := machineID;
 460         out_msg.Destination.add(in_msg.Requestor);
 461         out_msg.Acks := 0 - 1; // -1
 462         out_msg.MessageSize := MessageSizeType:Response_Control;
 463       }
 464     }
 465   }
 466
 467   action(g_sendUnblock, "g", desc="Send unblock to memory") {
 468     enqueue(unblockNetwork_out, ResponseMsg, latency="NULL_LATENCY") {
 469       out_msg.Address := address;
 470       out_msg.Type := CoherenceResponseType:UNBLOCK;
 471       out_msg.Sender := machineID;
 472       out_msg.Destination.add(map_Address_to_Directory(address));
 473       out_msg.MessageSize := MessageSizeType:Unblock_Control;
 474     }
 475   }
 476
 477   action(gg_sendUnblockExclusive, "\g", desc="Send unblock exclusive to memory") {
 478     enqueue(unblockNetwork_out, ResponseMsg, latency="NULL_LATENCY") {
 479       out_msg.Address := address;
 480       out_msg.Type := CoherenceResponseType:UNBLOCK_EXCLUSIVE;
 481       out_msg.Sender := machineID;
 482       out_msg.Destination.add(map_Address_to_Directory(address));
 483       out_msg.MessageSize := MessageSizeType:Unblock_Control;
 484     }
 485   }
 486
 487   action(h_load_hit, "h", desc="Notify sequencer the load completed.") {
 488     DEBUG_EXPR(getCacheEntry(address).DataBlk);
 489     sequencer.readCallback(address, getCacheEntry(address).DataBlk);
 490   }
 491
 492   action(hh_store_hit, "\h", desc="Notify sequencer that store completed.") {
 493     DEBUG_EXPR(getCacheEntry(address).DataBlk);
 494     sequencer.writeCallback(address, getCacheEntry(address).DataBlk);
 495     getCacheEntry(address).Dirty := true;
 496   }
 497
 498   action(i_allocateTBE, "i", desc="Allocate TBE") {
 499     check_allocate(TBEs);
 500     TBEs.allocate(address);
 501     TBEs[address].DataBlk := getCacheEntry(address).DataBlk; // Data only used for writebacks
 502     TBEs[address].Dirty := getCacheEntry(address).Dirty;
 503   }
 504
 505   action(j_popTriggerQueue, "j", desc="Pop trigger queue.") {
 506     triggerQueue_in.dequeue();
 507   }
 508
 509   action(k_popMandatoryQueue, "k", desc="Pop mandatory queue.") {
 510     mandatoryQueue_in.dequeue();
 511   }
 512
 513   action(l_popForwardQueue, "l", desc="Pop forwareded request queue.") {
 514     forwardToCache_in.dequeue();
 515   }
 516
 517   action(m_decrementNumberOfMessages, "m", desc="Decrement the number of messages for which we're waiting") {
 518     peek(responseToCache_in, ResponseMsg) {
 519       TBEs[address].NumPendingMsgs := TBEs[address].NumPendingMsgs - in_msg.Acks;
 520     }
 521   }
 522
 523   action(mm_decrementNumberOfMessages, "\m", desc="Decrement the number of messages for which we're waiting") {
 524     peek(forwardToCache_in, RequestMsg) {
 525       TBEs[address].NumPendingMsgs := TBEs[address].NumPendingMsgs - in_msg.Acks;
 526     }
 527   }
 528
 529   action(n_popResponseQueue, "n", desc="Pop response queue") {
 530     responseToCache_in.dequeue();
 531   }
 532
 533   action(o_checkForCompletion, "o", desc="Check if we have received all the messages required for completion") {
 534     if (TBEs[address].NumPendingMsgs == 0) {
 535       enqueue(triggerQueue_out, TriggerMsg) {
 536         out_msg.Address := address;
 537         out_msg.Type := TriggerType:ALL_ACKS;
 538       }
 539     }
 540   }
 541
 542   action(q_sendDataFromTBEToCache, "q", desc="Send data from TBE to cache") {
 543     peek(forwardToCache_in, RequestMsg) {
 544       enqueue(responseNetwork_out, ResponseMsg, latency="CACHE_RESPONSE_LATENCY") {
 545         out_msg.Address := address;
 546         out_msg.Type := CoherenceResponseType:DATA;
 547         out_msg.Sender := machineID;
 548         out_msg.Destination.add(in_msg.Requestor);
 549         out_msg.DataBlk := TBEs[address].DataBlk;
 550         out_msg.Dirty := TBEs[address].Dirty;
 551         out_msg.Acks := in_msg.Acks;
 552         out_msg.MessageSize := MessageSizeType:Response_Data;
 553       }
 554     }
 555   }
 556
 557   action(qq_sendDataFromTBEToMemory, "\q", desc="Send data from TBE to memory") {
 558     enqueue(unblockNetwork_out, ResponseMsg, latency="CACHE_RESPONSE_LATENCY") {
 559       out_msg.Address := address;
 560       out_msg.Sender := machineID;
 561       out_msg.Destination.add(map_Address_to_Directory(address));
 562       out_msg.Dirty := TBEs[address].Dirty;
 563       if (TBEs[address].Dirty) {
 564         out_msg.Type := CoherenceResponseType:WRITEBACK_DIRTY;
 565         out_msg.DataBlk := TBEs[address].DataBlk;
 566         out_msg.MessageSize := MessageSizeType:Writeback_Data;
 567       } else {
 568         out_msg.Type := CoherenceResponseType:WRITEBACK_CLEAN;
 569         // NOTE: in a real system this would not send data.  We send
 570         // data here only so we can check it at the memory
 571         out_msg.DataBlk := TBEs[address].DataBlk;
 572         out_msg.MessageSize := MessageSizeType:Writeback_Control;
 573       }
 574     }
 575   }
 576
 577   action(s_deallocateTBE, "s", desc="Deallocate TBE") {
 578     TBEs.deallocate(address);
 579   }
 580
 581   action(u_writeDataToCache, "u", desc="Write data to cache") {
 582     peek(responseToCache_in, ResponseMsg) {
 583       getCacheEntry(address).DataBlk := in_msg.DataBlk;
 584       getCacheEntry(address).Dirty := in_msg.Dirty;
 585     }
 586   }
 587
 588   action(v_writeDataToCacheVerify, "v", desc="Write data to cache, assert it was same as before") {
 589     peek(responseToCache_in, ResponseMsg) {
 590       assert(getCacheEntry(address).DataBlk == in_msg.DataBlk);
 591       getCacheEntry(address).DataBlk := in_msg.DataBlk;
 592       getCacheEntry(address).Dirty := in_msg.Dirty;
 593     }
 594   }
 595
 596   action(kk_deallocateL1CacheBlock, "\k", desc="Deallocate cache block.  Sets the cache to invalid, allowing a replacement in parallel with a fetch.") {
 597     if (L1DcacheMemory.isTagPresent(address)) {
 598       L1DcacheMemory.deallocate(address);
 599     } else {
 600       L1IcacheMemory.deallocate(address);
 601     }
 602   }
 603
 604   action(ii_allocateL1DCacheBlock, "\i", desc="Set L1 D-cache tag equal to tag of block B.") {
 605     if (L1DcacheMemory.isTagPresent(address) == false) {
 606       L1DcacheMemory.allocate(address);
 607     }
 608   }
 609
 610   action(jj_allocateL1ICacheBlock, "\j", desc="Set L1 I-cache tag equal to tag of block B.") {
 611     if (L1IcacheMemory.isTagPresent(address) == false) {
 612       L1IcacheMemory.allocate(address);
 613     }
 614   }
 615
 616   action(vv_allocateL2CacheBlock, "\v", desc="Set L2 cache tag equal to tag of block B.") {
 617     L2cacheMemory.allocate(address);
 618   }
 619
 620   action(rr_deallocateL2CacheBlock, "\r", desc="Deallocate L2 cache block.  Sets the cache to not present, allowing a replacement in parallel with a fetch.") {
 621     L2cacheMemory.deallocate(address);
 622   }
 623
 624   action(ss_copyFromL1toL2, "\s", desc="Copy data block from L1 (I or D) to L2") {
 625     if (L1DcacheMemory.isTagPresent(address)) {
 626       L2cacheMemory[address] := L1DcacheMemory[address];
 627     } else {
 628       L2cacheMemory[address] := L1IcacheMemory[address];
 629     }
 630   }
 631
 632   action(tt_copyFromL2toL1, "\t", desc="Copy data block from L2 to L1 (I or D)") {
 633     if (L1DcacheMemory.isTagPresent(address)) {
 634       L1DcacheMemory[address] := L2cacheMemory[address];
 635     } else {
 636       L1IcacheMemory[address] := L2cacheMemory[address];
 637     }
 638   }
 639
 640   action(uu_profileMiss, "\u", desc="Profile the demand miss") {
 641     peek(mandatoryQueue_in, CacheMsg) {
 642       profile_miss(in_msg, id);
 643     }
 644   }
 645
 646   action(zz_recycleMandatoryQueue, "\z", desc="Send the head of the mandatory queue to the back of the queue.") {
 647     mandatoryQueue_in.recycle();
 648   }
 649
 650   //*****************************************************
 651   // TRANSITIONS
 652   //*****************************************************
 653
 654   // Transitions for Load/Store/L2_Replacement from transient states
 655   transition({IM, SM, OM, IS, OI, MI, II}, {Store, L2_Replacement}) {
 656     zz_recycleMandatoryQueue;
 657   }
 658
 659   transition({IM, IS, OI, MI, II}, {Load, Ifetch}) {
 660     zz_recycleMandatoryQueue;
 661   }
 662
 663   transition({IM, SM, OM, IS, OI, MI, II}, L1_to_L2) {
 664     zz_recycleMandatoryQueue;
 665   }
 666
 667   // Transitions moving data between the L1 and L2 caches
 668   transition({I, S, O, E, M, MM}, L1_to_L2) {
 669     vv_allocateL2CacheBlock;
 670     ss_copyFromL1toL2; // Not really needed for state I
 671     kk_deallocateL1CacheBlock;
 672   }
 673
 674   transition({I, S, O, E, M, MM}, L2_to_L1D) {
 675     ii_allocateL1DCacheBlock;
 676     tt_copyFromL2toL1; // Not really needed for state I
 677     rr_deallocateL2CacheBlock;
 678   }
 679
 680   transition({I, S, O, E, M, MM}, L2_to_L1I) {
 681     jj_allocateL1ICacheBlock;
 682     tt_copyFromL2toL1; // Not really needed for state I
 683     rr_deallocateL2CacheBlock;
 684   }
 685
 686   // Transitions from Idle
 687   transition({NP, I}, Load, IS) {
 688     ii_allocateL1DCacheBlock;
 689     i_allocateTBE;
 690     a_issueGETS;
 691     uu_profileMiss;
 692     k_popMandatoryQueue;
 693   }
 694
 695   transition({NP, I}, Ifetch, IS) {
 696     jj_allocateL1ICacheBlock;
 697     i_allocateTBE;
 698     a_issueGETS;
 699     uu_profileMiss;
 700     k_popMandatoryQueue;
 701   }
 702
 703   transition({NP, I}, Store, IM) {
 704     ii_allocateL1DCacheBlock;
 705     i_allocateTBE;
 706     b_issueGETX;
 707     uu_profileMiss;
 708     k_popMandatoryQueue;
 709   }
 710
 711   transition(I, L2_Replacement) {
 712     rr_deallocateL2CacheBlock;
 713   }
 714
 715   transition({NP, I}, Inv) {
 716     f_sendAck;
 717     l_popForwardQueue;
 718   }
 719
 720   // Transitions from Shared
 721   transition({S, SM}, {Load, Ifetch}) {
 722     h_load_hit;
 723     k_popMandatoryQueue;
 724   }
 725
 726   transition(S, Store, SM) {
 727     i_allocateTBE;
 728     b_issueGETX;
 729     uu_profileMiss;
 730     k_popMandatoryQueue;
 731   }
 732
 733   transition(S, L2_Replacement, I) {
 734     rr_deallocateL2CacheBlock;
 735   }
 736
 737   transition(S, Inv, I) {
 738     f_sendAck;
 739     l_popForwardQueue;
 740   }
 741
 742   // Transitions from Owned
 743   transition({O, OM}, {Load, Ifetch}) {
 744     h_load_hit;
 745     k_popMandatoryQueue;
 746   }
 747
 748   transition(O, Store, OM) {
 749     i_allocateTBE;
 750     b_issueGETX;
 751     //    p_decrementNumberOfMessagesByOne;
 752     uu_profileMiss;
 753     k_popMandatoryQueue;
 754   }
 755
 756   transition(O, L2_Replacement, OI) {
 757     i_allocateTBE;
 758     dd_issuePUTO;
 759     rr_deallocateL2CacheBlock;
 760   }
 761
 762   transition(O, Fwd_GETX, I) {
 763     e_sendData;
 764     l_popForwardQueue;
 765   }
 766
 767   transition(O, Fwd_GETS) {
 768     e_sendData;
 769     l_popForwardQueue;
 770   }
 771
 772   // Transitions from MM
 773   transition(MM, {Load, Ifetch}) {
 774     h_load_hit;
 775     k_popMandatoryQueue;
 776   }
 777
 778   transition(MM, Store) {
 779     hh_store_hit;
 780     k_popMandatoryQueue;
 781   }
 782
 783   transition(MM, L2_Replacement, MI) {
 784     i_allocateTBE;
 785     d_issuePUTX;
 786     rr_deallocateL2CacheBlock;
 787   }
 788
 789   transition(MM, Fwd_GETX, I) {
 790     e_sendData;
 791     l_popForwardQueue;
 792   }
 793
 794   transition(MM, Fwd_GETS, I) {
 795     ee_sendDataExclusive;
 796     l_popForwardQueue;
 797   }
 798
 799   // Transitions from M
 800   transition({E, M}, {Load, Ifetch}) {
 801     h_load_hit;
 802     k_popMandatoryQueue;
 803   }
 804
 805   transition({E, M}, Store, MM) {
 806     hh_store_hit;
 807     k_popMandatoryQueue;
 808   }
 809
 810   transition({E, M}, L2_Replacement, MI) {
 811     i_allocateTBE;
 812     d_issuePUTX;
 813     rr_deallocateL2CacheBlock;
 814   }
 815
 816   transition({E, M}, Fwd_GETX, I) {
 817     e_sendData;
 818     l_popForwardQueue;
 819   }
 820
 821   transition({E, M}, Fwd_GETS, O) {
 822     e_sendData;
 823     l_popForwardQueue;
 824   }
 825
 826   // Transitions from IM
 827
 828   transition(IM, Inv) {
 829     f_sendAck;
 830     l_popForwardQueue;
 831   }
 832
 833   transition(IM, Ack) {
 834     m_decrementNumberOfMessages;
 835     o_checkForCompletion;
 836     n_popResponseQueue;
 837   }
 838
 839   transition(IM, Data, OM) {
 840     u_writeDataToCache;
 841     m_decrementNumberOfMessages;
 842     o_checkForCompletion;
 843     n_popResponseQueue;
 844   }
 845
 846   // Transitions from SM
 847   transition(SM, Inv, IM) {
 848     f_sendAck;
 849     l_popForwardQueue;
 850   }
 851
 852   transition(SM, Ack) {
 853     m_decrementNumberOfMessages;
 854     o_checkForCompletion;
 855     n_popResponseQueue;
 856   }
 857
 858   transition(SM, Data, OM) {
 859     v_writeDataToCacheVerify;
 860     m_decrementNumberOfMessages;
 861     o_checkForCompletion;
 862     n_popResponseQueue;
 863   }
 864
 865   // Transitions from OM
 866   transition(OM, Own_GETX) {
 867     mm_decrementNumberOfMessages;
 868     o_checkForCompletion;
 869     l_popForwardQueue;
 870   }
 871
 872   transition(OM, Fwd_GETX, IM) {
 873     e_sendData;
 874     l_popForwardQueue;
 875   }
 876
 877   transition(OM, Fwd_GETS, OM) {
 878     e_sendData;
 879     l_popForwardQueue;
 880   }
 881
 882   transition(OM, Ack) {
 883     m_decrementNumberOfMessages;
 884     o_checkForCompletion;
 885     n_popResponseQueue;
 886   }
 887
 888   transition(OM, All_acks, MM) {
 889     hh_store_hit;
 890     gg_sendUnblockExclusive;
 891     s_deallocateTBE;
 892     j_popTriggerQueue;
 893   }
 894
 895   // Transitions from IS
 896
 897   transition(IS, Inv) {
 898     f_sendAck;
 899     l_popForwardQueue;
 900   }
 901
 902   transition(IS, Data, S) {
 903     u_writeDataToCache;
 904     m_decrementNumberOfMessages;
 905     h_load_hit;
 906     g_sendUnblock;
 907     s_deallocateTBE;
 908     n_popResponseQueue;
 909   }
 910
 911   transition(IS, Exclusive_Data_Clean, E) {
 912     u_writeDataToCache;
 913     m_decrementNumberOfMessages;
 914     h_load_hit;
 915     gg_sendUnblockExclusive;
 916     s_deallocateTBE;
 917     n_popResponseQueue;
 918   }
 919
 920   transition(IS, Exclusive_Data_Dirty, M) {
 921     u_writeDataToCache;
 922     m_decrementNumberOfMessages;
 923     h_load_hit;
 924     gg_sendUnblockExclusive;
 925     s_deallocateTBE;
 926     n_popResponseQueue;
 927   }
 928
 929   // Transitions from OI/MI
 930
 931   transition(MI, Fwd_GETS) {
 932     q_sendDataFromTBEToCache;
 933     l_popForwardQueue;
 934   }
 935
 936   transition(MI, Fwd_GETX, II) {
 937     q_sendDataFromTBEToCache;
 938     l_popForwardQueue;
 939   }
 940
 941   transition(OI, Fwd_GETS) {
 942     q_sendDataFromTBEToCache;
 943     l_popForwardQueue;
 944   }
 945
 946   transition(OI, Fwd_GETX, II) {
 947     q_sendDataFromTBEToCache;
 948     l_popForwardQueue;
 949   }
 950
 951   transition({OI, MI}, Writeback_Ack, I) {
 952     qq_sendDataFromTBEToMemory;
 953     s_deallocateTBE;
 954     l_popForwardQueue;
 955   }
 956
 957   transition(MI, Writeback_Nack, OI) {
 958     // FIXME: This might cause deadlock by re-using the writeback
 959     // channel, we should handle this case differently.
 960     dd_issuePUTO;
 961     l_popForwardQueue;
 962   }
 963
 964   // Transitions from II
 965   transition(II, Writeback_Ack, I) {
 966     g_sendUnblock;
 967     s_deallocateTBE;
 968     l_popForwardQueue;
 969   }
 970
 971   transition(II, Writeback_Nack, I) {
 972     s_deallocateTBE;
 973     l_popForwardQueue;
 974   }
 975
 976   transition(II, Inv) {
 977     f_sendAck;
 978     l_popForwardQueue;
 979   }
 980 }
 981