ruby: fixed token bugs associated with owner token counts

This patch fixes several bugs related to previous inconsistent assumptions on
how many tokens the Owner had.  Mike Marty should have fixes these bugs years
ago.  :)

1 files changed, 111 insertions, 41 deletions

diff --git a/src/mem/protocol/MOESI_CMP_token-L1cache.sm b/src/mem/protocol/MOESI_CMP_token-L1cache.sm
index 8424479bd..d3e993efa 100644
--- a/src/mem/protocol/MOESI_CMP_token-L1cache.sm
+++ b/src/mem/protocol/MOESI_CMP_token-L1cache.sm
@@ -112,6 +112,7 @@ machine(L1Cache, "Token protocol")
     // Lock/Unlock for distributed
     Persistent_GETX,     desc="Another processor has priority to read/write";
     Persistent_GETS,     desc="Another processor has priority to read";
+    Persistent_GETS_Last_Token, desc="Another processor has priority to read, no more tokens";
     Own_Lock_or_Unlock,  desc="This processor now has priority";
 
     // Triggers
@@ -208,6 +209,7 @@ machine(L1Cache, "Token protocol")
 
   Entry getCacheEntry(Address addr), return_by_ref="yes" {
     if (L1DcacheMemory.isTagPresent(addr)) {
+      assert(L1IcacheMemory.isTagPresent(addr) == false);
       return static_cast(Entry, L1DcacheMemory[addr]);
     } else {
       return static_cast(Entry, L1IcacheMemory[addr]);
@@ -216,6 +218,7 @@ machine(L1Cache, "Token protocol")
 
   int getTokens(Address addr) {
     if (L1DcacheMemory.isTagPresent(addr)) {
+      assert(L1IcacheMemory.isTagPresent(addr) == false);
       return static_cast(Entry, L1DcacheMemory[addr]).Tokens;
     } else if (L1IcacheMemory.isTagPresent(addr)) {
       return static_cast(Entry, L1IcacheMemory[addr]).Tokens;
@@ -269,6 +272,7 @@ machine(L1Cache, "Token protocol")
       // Make sure the token count is in range
       assert(getCacheEntry(addr).Tokens >= 0);
       assert(getCacheEntry(addr).Tokens <= max_tokens());
+      assert(getCacheEntry(addr).Tokens != (max_tokens() / 2));
 
       if ((state == State:I_L) ||
           (state == State:IM_L) ||
@@ -287,6 +291,7 @@ machine(L1Cache, "Token protocol")
       } else if ((state == State:S_L) ||
                  (state == State:SM_L)) {
         assert(getCacheEntry(addr).Tokens >= 1);
+        assert(getCacheEntry(addr).Tokens < (max_tokens() / 2));
 
         // Make sure the line is locked...
         // assert(persistentTable.isLocked(addr));
@@ -327,8 +332,7 @@ machine(L1Cache, "Token protocol")
 
       // You have at least half the token in O-like states
       if (state == State:O && state == State:OM) {
-        assert(getCacheEntry(addr).Tokens >= 1); // Must have at least one token
-        assert(getCacheEntry(addr).Tokens >= (max_tokens() / 2)); // Only mostly true; this might not always hold
+        assert(getCacheEntry(addr).Tokens > (max_tokens() / 2));
       }
 
       getCacheEntry(addr).CacheState := state;
@@ -462,7 +466,12 @@ machine(L1Cache, "Token protocol")
             trigger(Event:Own_Lock_or_Unlock, in_msg.Address);
           } else {
             if (persistentTable.typeOfSmallest(in_msg.Address) == AccessType:Read) {
-              trigger(Event:Persistent_GETS, in_msg.Address);
+              if (getTokens(in_msg.Address) == 1 ||
+                  getTokens(in_msg.Address) == (max_tokens() / 2) + 1) {
+                trigger(Event:Persistent_GETS_Last_Token, in_msg.Address);
+              } else {
+                trigger(Event:Persistent_GETS, in_msg.Address);
+              }
             } else {
               trigger(Event:Persistent_GETX, in_msg.Address);
             }
@@ -489,7 +498,8 @@ machine(L1Cache, "Token protocol")
             trigger(Event:Transient_GETX, in_msg.Address);
           }
         } else if (in_msg.Type == CoherenceRequestType:GETS) {
-          if ( (L1DcacheMemory.isTagPresent(in_msg.Address) || L1IcacheMemory.isTagPresent(in_msg.Address)) && getCacheEntry(in_msg.Address).Tokens == 1) {
+          if (getTokens(in_msg.Address) == 1 || 
+              getTokens(in_msg.Address) == (max_tokens() / 2) + 1) {
             if (in_msg.isLocal) {
               trigger(Event:Transient_Local_GETS_Last_Token, in_msg.Address);
             }
@@ -557,16 +567,19 @@ machine(L1Cache, "Token protocol")
 
         if (getTokens(in_msg.Address) + in_msg.Tokens != max_tokens()) {
           if (in_msg.Type == CoherenceResponseType:ACK) {
+            assert(in_msg.Tokens < (max_tokens() / 2));
             trigger(Event:Ack, in_msg.Address);
           } else if (in_msg.Type == CoherenceResponseType:DATA_OWNER) {
             trigger(Event:Data_Owner, in_msg.Address);
           } else if (in_msg.Type == CoherenceResponseType:DATA_SHARED) {
+            assert(in_msg.Tokens < (max_tokens() / 2));
             trigger(Event:Data_Shared, in_msg.Address);
           } else {
             error("Unexpected message");
           }
         } else {
           if (in_msg.Type == CoherenceResponseType:ACK) {
+            assert(in_msg.Tokens < (max_tokens() / 2));
             trigger(Event:Ack_All_Tokens, in_msg.Address);
           } else if (in_msg.Type == CoherenceResponseType:DATA_OWNER || in_msg.Type == CoherenceResponseType:DATA_SHARED) {
             trigger(Event:Data_All_Tokens, in_msg.Address);
@@ -914,10 +927,32 @@ machine(L1Cache, "Token protocol")
     getCacheEntry(address).Tokens := 0;
   }
 
-  action(cc_sharedReplacement, "\c", desc="Issue dirty writeback") {
+  action(cc_sharedReplacement, "\c", desc="Issue shared writeback") {
 
     // don't send writeback if replacing block with no tokens
-    if (getCacheEntry(address).Tokens != 0) {
+    assert (getCacheEntry(address).Tokens > 0);
+    enqueue(responseNetwork_out, ResponseMsg, latency = l1_response_latency) {
+        out_msg.Address := address;
+        out_msg.Sender := machineID;
+
+        out_msg.Destination.add(mapAddressToRange(address,
+                                                  MachineType:L2Cache,
+                                                  l2_select_low_bit,
+                                                  l2_select_num_bits));
+
+        out_msg.Tokens := getCacheEntry(address).Tokens;
+        out_msg.DataBlk := getCacheEntry(address).DataBlk;
+        // assert(getCacheEntry(address).Dirty == false);
+        out_msg.Dirty := false;
+
+        out_msg.MessageSize := MessageSizeType:Writeback_Data;
+        out_msg.Type := CoherenceResponseType:WB_SHARED_DATA;
+    }
+    getCacheEntry(address).Tokens := 0;
+  }
+
+  action(tr_tokenReplacement, "tr", desc="Issue token writeback") {
+    if (getCacheEntry(address).Tokens > 0) {
       enqueue(responseNetwork_out, ResponseMsg, latency = l1_response_latency) {
         out_msg.Address := address;
         out_msg.Sender := machineID;
@@ -933,16 +968,11 @@ machine(L1Cache, "Token protocol")
         out_msg.Dirty := false;
 
         // always send the data?
-        if (getCacheEntry(address).Tokens > 1) {
-          out_msg.MessageSize := MessageSizeType:Writeback_Data;
-          out_msg.Type := CoherenceResponseType:WB_SHARED_DATA;
-        } else {
-          out_msg.MessageSize := MessageSizeType:Writeback_Control;
-          out_msg.Type := CoherenceResponseType:WB_TOKENS;
-        }
+        out_msg.MessageSize := MessageSizeType:Writeback_Control;
+        out_msg.Type := CoherenceResponseType:WB_TOKENS;
       }
-      getCacheEntry(address).Tokens := 0;
     }
+    getCacheEntry(address).Tokens := 0;
   }
 
 
@@ -970,7 +1000,7 @@ machine(L1Cache, "Token protocol")
 
   action(d_sendDataWithNTokenIfAvail, "\dd", desc="Send data and a token from cache to requestor") {
     peek(requestNetwork_in, RequestMsg) {
-      if (getCacheEntry(address).Tokens > N_tokens) {
+      if (getCacheEntry(address).Tokens > (N_tokens + (max_tokens() / 2))) {
         enqueue(responseNetwork_out, ResponseMsg, latency = l1_response_latency) {
           out_msg.Address := address;
           out_msg.Type := CoherenceResponseType:DATA_SHARED;
@@ -1017,7 +1047,7 @@ machine(L1Cache, "Token protocol")
         out_msg.Type := CoherenceResponseType:DATA_OWNER;
         out_msg.Sender := machineID;
         out_msg.Destination.add(in_msg.Requestor);
-        assert(getCacheEntry(address).Tokens >= 1);
+        assert(getCacheEntry(address).Tokens > (max_tokens() / 2));
         out_msg.Tokens := getCacheEntry(address).Tokens;
         out_msg.DataBlk := getCacheEntry(address).DataBlk;
         out_msg.Dirty := getCacheEntry(address).Dirty;
@@ -1036,11 +1066,16 @@ machine(L1Cache, "Token protocol")
     if (getCacheEntry(address).Tokens > 0) {
       enqueue(responseNetwork_out, ResponseMsg, latency = l1_response_latency) {
         out_msg.Address := address;
-        out_msg.Type := CoherenceResponseType:ACK;
+        if (getCacheEntry(address).Tokens > (max_tokens() / 2)) {
+          out_msg.Type := CoherenceResponseType:DATA_OWNER;
+        } else {
+          out_msg.Type := CoherenceResponseType:ACK;
+        }
         out_msg.Sender := machineID;
         out_msg.Destination.add(persistentTable.findSmallest(address));
         assert(getCacheEntry(address).Tokens >= 1);
         out_msg.Tokens := getCacheEntry(address).Tokens;
+        out_msg.DataBlk := getCacheEntry(address).DataBlk;
         out_msg.MessageSize := MessageSizeType:Response_Control;
       }
     }
@@ -1055,7 +1090,7 @@ machine(L1Cache, "Token protocol")
       out_msg.Type := CoherenceResponseType:DATA_OWNER;
       out_msg.Sender := machineID;
       out_msg.Destination.add(persistentTable.findSmallest(address));
-      assert(getCacheEntry(address).Tokens >= 1);
+      assert(getCacheEntry(address).Tokens > (max_tokens() / 2));
       out_msg.Tokens := getCacheEntry(address).Tokens;
       out_msg.DataBlk := getCacheEntry(address).DataBlk;
       out_msg.Dirty := getCacheEntry(address).Dirty;
@@ -1070,7 +1105,11 @@ machine(L1Cache, "Token protocol")
     if (getCacheEntry(address).Tokens > 1) {
       enqueue(responseNetwork_out, ResponseMsg, latency = l1_response_latency) {
         out_msg.Address := address;
-        out_msg.Type := CoherenceResponseType:ACK;
+        if (getCacheEntry(address).Tokens > (max_tokens() / 2)) {
+          out_msg.Type := CoherenceResponseType:DATA_OWNER;
+        } else {
+          out_msg.Type := CoherenceResponseType:ACK;
+        }
         out_msg.Sender := machineID;
         out_msg.Destination.add(persistentTable.findSmallest(address));
         assert(getCacheEntry(address).Tokens >= 1);
@@ -1079,6 +1118,7 @@ machine(L1Cache, "Token protocol")
         } else {
           out_msg.Tokens := getCacheEntry(address).Tokens - 1;
         }
+        out_msg.DataBlk := getCacheEntry(address).DataBlk;
         out_msg.MessageSize := MessageSizeType:Response_Control;
       }
     }
@@ -1091,31 +1131,45 @@ machine(L1Cache, "Token protocol")
 
   action(ff_sendDataWithAllButNorOneTokens, "\f", desc="Send data and out tokens but one to starver") {
     //assert(persistentTable.findSmallest(address) != id); // Make sure we never bounce tokens to ourself
-    assert(getCacheEntry(address).Tokens > 0);
-    if (getCacheEntry(address).Tokens > 1) {
-      enqueue(responseNetwork_out, ResponseMsg, latency = l1_response_latency) {
+    assert(getCacheEntry(address).Tokens > ((max_tokens() / 2) + 1));
+    enqueue(responseNetwork_out, ResponseMsg, latency = l1_response_latency) {
         out_msg.Address := address;
         out_msg.Type := CoherenceResponseType:DATA_OWNER;
         out_msg.Sender := machineID;
         out_msg.Destination.add(persistentTable.findSmallest(address));
-        assert(getCacheEntry(address).Tokens >= 1);
-        if (getCacheEntry(address).Tokens > N_tokens) {
+        if (getCacheEntry(address).Tokens > (N_tokens + (max_tokens() / 2))) {
           out_msg.Tokens := getCacheEntry(address).Tokens - N_tokens;
         } else {
           out_msg.Tokens := getCacheEntry(address).Tokens - 1;
         }
+        assert(out_msg.Tokens > (max_tokens() / 2));
         out_msg.DataBlk := getCacheEntry(address).DataBlk;
         out_msg.Dirty := getCacheEntry(address).Dirty;
         out_msg.MessageSize := MessageSizeType:Response_Data;
-      }
-      if (getCacheEntry(address).Tokens > N_tokens) {
-        getCacheEntry(address).Tokens := N_tokens;
-      } else {
-        getCacheEntry(address).Tokens := 1;
-      }
+    }
+    if (getCacheEntry(address).Tokens > (N_tokens + (max_tokens() / 2))) {
+      getCacheEntry(address).Tokens := N_tokens;
+    } else {
+      getCacheEntry(address).Tokens := 1;
     }
   }
 
+  action(fo_sendDataWithOwnerToken, "fo", desc="Send data and owner tokens") {
+    assert(getCacheEntry(address).Tokens == ((max_tokens() / 2) + 1));
+    enqueue(responseNetwork_out, ResponseMsg, latency = l1_response_latency) {
+        out_msg.Address := address;
+        out_msg.Type := CoherenceResponseType:DATA_OWNER;
+        out_msg.Sender := machineID;
+        out_msg.Destination.add(persistentTable.findSmallest(address));
+        out_msg.Tokens := getCacheEntry(address).Tokens;
+        assert(out_msg.Tokens > (max_tokens() / 2));
+        out_msg.DataBlk := getCacheEntry(address).DataBlk;
+        out_msg.Dirty := getCacheEntry(address).Dirty;
+        out_msg.MessageSize := MessageSizeType:Response_Data;
+    }
+    getCacheEntry(address).Tokens := 0;
+  }
+
   action(g_bounceResponseToStarver, "g", desc="Redirect response to starving processor") {
     // assert(persistentTable.isLocked(address));
 
@@ -1313,11 +1367,16 @@ machine(L1Cache, "Token protocol")
       peek(requestNetwork_in, RequestMsg) {
         enqueue(responseNetwork_out, ResponseMsg, latency = l1_response_latency) {
           out_msg.Address := address;
-          out_msg.Type := CoherenceResponseType:ACK;
+          if (getCacheEntry(address).Tokens > (max_tokens() / 2)) {
+            out_msg.Type := CoherenceResponseType:DATA_OWNER;
+          } else {
+            out_msg.Type := CoherenceResponseType:ACK;
+          }
           out_msg.Sender := machineID;
           out_msg.Destination.add(in_msg.Requestor);
           assert(getCacheEntry(address).Tokens >= 1);
           out_msg.Tokens := getCacheEntry(address).Tokens;
+          out_msg.DataBlk := getCacheEntry(address).DataBlk;
           out_msg.MessageSize := MessageSizeType:Response_Control;
         }
       }
@@ -1336,6 +1395,7 @@ machine(L1Cache, "Token protocol")
   }
 
   action(gg_deallocateL1CacheBlock, "\g", desc="Deallocate cache block.  Sets the cache to invalid, allowing a replacement in parallel with a fetch.") {
+    assert(getTokens(address) == 0);
     if (L1DcacheMemory.isTagPresent(address)) {
       L1DcacheMemory.deallocate(address);
     } else {
@@ -1432,7 +1492,7 @@ machine(L1Cache, "Token protocol")
     m_popRequestQueue;
   }
 
-  transition(NP, {Persistent_GETX, Persistent_GETS}, I_L) {
+  transition(NP, {Persistent_GETX, Persistent_GETS, Persistent_GETS_Last_Token}, I_L) {
     l_popPersistentQueue;
   }
 
@@ -1459,7 +1519,7 @@ machine(L1Cache, "Token protocol")
   }
 
   transition(I, L1_Replacement) {
-    cc_sharedReplacement;
+    tr_tokenReplacement;
     gg_deallocateL1CacheBlock;
   }
 
@@ -1472,12 +1532,12 @@ machine(L1Cache, "Token protocol")
     m_popRequestQueue;
   }
 
-  transition(I, {Persistent_GETX, Persistent_GETS}, I_L) {
+  transition(I, {Persistent_GETX, Persistent_GETS, Persistent_GETS_Last_Token}, I_L) {
     e_sendAckWithCollectedTokens;
     l_popPersistentQueue;
   }
 
-  transition(I_L, {Persistent_GETX, Persistent_GETS}) {
+  transition(I_L, {Persistent_GETX, Persistent_GETS, Persistent_GETS_Last_Token}) {
     l_popPersistentQueue;
   }
 
@@ -1548,12 +1608,12 @@ machine(L1Cache, "Token protocol")
     l_popPersistentQueue;
   }
 
-  transition(S, Persistent_GETS, S_L) {
+  transition(S, {Persistent_GETS, Persistent_GETS_Last_Token}, S_L) {
     f_sendAckWithAllButNorOneTokens;
     l_popPersistentQueue;
   }
 
-  transition(S_L, Persistent_GETS) {
+  transition(S_L, {Persistent_GETS, Persistent_GETS_Last_Token}) {
     l_popPersistentQueue;
   }
 
@@ -1615,6 +1675,11 @@ machine(L1Cache, "Token protocol")
     l_popPersistentQueue;
   }
 
+  transition(O, Persistent_GETS_Last_Token, I_L) {
+    fo_sendDataWithOwnerToken;
+    l_popPersistentQueue;
+  }
+
   transition(O, Transient_GETS) {
     d_sendDataWithToken;
     m_popRequestQueue;
@@ -1798,7 +1863,7 @@ machine(L1Cache, "Token protocol")
     m_popRequestQueue;
   }
 
-  transition(IS, {Persistent_GETX, Persistent_GETS}, IS_L) {
+  transition(IS, {Persistent_GETX, Persistent_GETS, Persistent_GETS_Last_Token}, IS_L) {
     e_sendAckWithCollectedTokens;
     l_popPersistentQueue;
   }
@@ -1807,7 +1872,7 @@ machine(L1Cache, "Token protocol")
     l_popPersistentQueue;
   }
 
-  transition(IM, {Persistent_GETX, Persistent_GETS}, IM_L) {
+  transition(IM, {Persistent_GETX, Persistent_GETS, Persistent_GETS_Last_Token}, IM_L) {
     e_sendAckWithCollectedTokens;
     l_popPersistentQueue;
   }
@@ -1821,12 +1886,12 @@ machine(L1Cache, "Token protocol")
     l_popPersistentQueue;
   }
 
-  transition(SM, Persistent_GETS, SM_L) {
+  transition(SM, {Persistent_GETS, Persistent_GETS_Last_Token}, SM_L) {
     f_sendAckWithAllButNorOneTokens;
     l_popPersistentQueue;
   }
 
-  transition(SM_L, Persistent_GETS) {
+  transition(SM_L, {Persistent_GETS, Persistent_GETS_Last_Token}) {
     l_popPersistentQueue;
   }
 
@@ -1840,6 +1905,11 @@ machine(L1Cache, "Token protocol")
     l_popPersistentQueue;
   }
 
+  transition(OM, Persistent_GETS_Last_Token, IM_L) {
+    fo_sendDataWithOwnerToken;
+    l_popPersistentQueue;
+  }
+
   // Transitions from IM/SM
 
   transition({IM, SM}, Ack) {