Re: [Gems-users] MESI_CMP_filter_directory - race with PUTX

["Rubén Titos" <rtitos@xxxxxxxxxxx>]

Hi Luke,

Thanks for your reply. The silent drop of a stale PUTX is actually the first thing I looked into when I was debugging the protocol: I looked for the "conversion" of the PUTX into a PUTX_old when the node is removed as a sharer, but I noticed that in certain cases this didn't happen, and I'll try to show when (numbers in brackets refer to msg arrival time of my picture):
- (2) Exclusive=Sharers={L1cache-1]
- (6) Exclusive=Sharers={L1cache-1] -----> Sharers={L1cache-0, L1cache-1]
- (7) Sharers={L1cache-0, L1cache-1] ------> L1_PUTX not discarded since L1cache-1 is a sharer
- (some time in between 7 and 8) L1_GETX from L1cache-1 arrives but the line is locked in MT_IB, waiting for the WB_Data from L1cache-1 to complete the $-to-$ transfer.
- (8) Sharers={L1cache-0, L1cache-1] ------> When WB_Data arrives, data is written to the L2 cache and L1cache-1 stays as a sharer, because the WB msg doesn't inform L2 that when the Fwd_GETS arrived, the data was sent to both L1cache-0 and L2 from the TBE, since it was being replaced.
-  (10) Sharers={L1cache-0, L1cache-1] ------> At this point, there is a chance that the L1_PUTX is served and a WB_ack is sent to L1cache-1 while the block is still in MP at L1, thus avoiding the buggy race. But since the recycling of both L1_PUTX and L1_GETX can leave any of them at the front of the queue after the previous WB_Data is processed. If it happens that is the turn for L1_GETX, the request will be served and, since L1cache-1 is in sharers, the L1_PUTX won't be discarded but recycled instead.
- (15) Sharers={L1cache-1] ------> Since the GETX request was originated from the replacing cache, L1cache-1 "never leaves" the sharers list and thus the PUTX never will turn into a PUTX_old. After the Exclusive_Unblock is received, the line is unlocked at L2 and the PUTX is (incorrectly) served; when the WB_Ack arrives at L1, the block is in M state, causing the crash.

I think this race could be solved by informing the L2 that it should remove the last owner of the block. I've added a bit "removeLastOwner" that is set to true if the message "DataSfromL1" contains data sent from TBE. The bit is always copied to the Unblock msg, so that when the L2 receives the Unblock from L1cache-0, it can remove L1cache-1 from sharers and exclusive, while waiting for the WB_Data. In this way, L1cache-0 is a the only sharer but it doesn't have permission to write the block (block in SS at L2 and S at Exclusive's L1). This solved this particular type of race for me. Probably it could be solved as well by including a similar "removeWritebacker" directly in the WB_Data message.

However, this is not the only kind of race that the randomized tester can extract from this protocol. A similar "invalid transition" crash occurs when a PUTX from a certain block is delayed enough cycles, and a second request to the replaced block (served by the replacing cache because the block was forwarded to another cache and thus invalidated and removed from TBE in the replacer) manages to complete before the PUTX has arrived at L2. Here you have the trace:

http://skywalker.inf.um.es/~rtitos/files/tester_output

I know that this races are due to the way I insert the L1_Replacement events when flushing the cache, and, as Dan Gibson noted, they cannot occur in the Simics+ruby in order model, as long as a second request is not considered until the first one (the one that trigger the replacement) has comleted. But they way I flush the L1 cache (by issuing replacement events at xact begin, without having a "real" data request but an artificial "FLUSH" request instead) could potentially lead to such problems. Of course, the features of ruby's simple network make it impossible(?) for a later GETX to "surpass" a previous PUTX for the same block (or at least none of my benchmarks has crashed due to this race when running with simics). However, I think in a realistic environment (if messages could get delayed many cycles) it could actually happen.

Cheers,

Ruben

On Jan 17, 2008 11:42 PM, Luke Yen <lyen@xxxxxxxxxxx> wrote:

Hi Rubin,

   I'll work with you to resolve this issue, and then I'll post a solution
to the list.

   Thanks for the nice picture of the problem.  After looking at the
protocol and your illustration of the problem, I am puzzled by how
transition (17) WB_ACK can occur.  This is because the L2 controller file
distinguishes between L1_PUTX and L1_PUTX_old, and this distinction is
made by checking whether the requestor is a sharer of the block.  Here's
the relevant code:

    } else if (type == CoherenceRequestType:PUTX) {
      if (isSharer(addr, requestor)) {
        return Event:L1_PUTX;
      } else {
        return Event:L1_PUTX_old;
      }

  Looking at the SS_MB->MT transition, there is an action to clear the
sharers list, and make the requestor the exclusive owner:

  transition(SS_MB, Exclusive_Unblock, MT) {
    // update actual directory
    mmu_markExclusiveFromUnblock;
    // mark block as trans if needed
    f_markBlockTransIfTrans;
    k_popUnblockQueue;
  }

  action(mmu_markExclusiveFromUnblock, "\mu", desc="set the exclusive
owner") {
    peek(L1unblockNetwork_in, ResponseMsg) {
      L2cacheMemory[address].Sharers.clear();
      L2cacheMemory[address].Exclusive := in_msg.Sender;
      addSharer(address, in_msg.Sender);
    }
  }

  Thus, when MT sees PUTX, it should be L1_PUTX_old and not L1_PUTX, and
thus the request should be silently dropped, without sending the WB_ACK
back to the L1cache-1.

  Can you check your trace and confirm whether L1cache-1 is marked as a
sharer when the block is in MT state at the L2 (e.g. when (16) occurs)?

  Thanks,
    Luke

On Tue, 15 Jan 2008, Rubén Titos wrote:

> Dear list,
>
> I've been working for some time now with MESI_CMP_filter_directory in GEMS
> 2.0, and so far I hadn't run into any protocol bug. However, after including
> some cache flushing functionality (that barely modified the L1 protocol
> file) I've come across the following race condition, when debugging my own
> version  the tester and randomization=true. I believe this mistake is
> independient from my code, as I haven't changed any protocol state, event
> nor transition, but just added an extra event and some minor additions to
> the code in_port(mandatoryQueue_in).
>
> In an attempt for clarity, I'll avoid pasting the debug trace, but instead
> I'm going to describe the race condition (btw I've also drawn it, you can
> have a look here

> http://skywalker.inf.um.es/~rtitos/files/protocol_race.png< http://skywalker.inf.um.es/%7Ertitos/files/protocol_race.png>)

> - It is initiated by the replacement of the line (state M) at L1cache-1 (in
> my case when flushing the cache, but it may as well happen in the original
> version of such protocol with any common replacement). The PUTX msg sent by
> L1cache-1 is delayed many cycles during its trip to the L2, and in the
> meantime the following happens:
> --- L1cache-0 issues a GETS, that arrives at L2 and is forwarded to the
> L1cache-1, finding the line in state I_M (since it's being replaced).
> --- L1cache-1 send the data (dataSfromL1) to the requestor (L1cache-0) and a
> writeback to the L2, and sets the line is state I.
> --- The L1cache-0 receives the data and sends an unblock to the L2.
> --- The L1cache-1 receives a Store request, and since the block is in state
> I it issues a new GETX message, setting the block to IM state.
> --- The unblock from core 0 arrives at L2 and updates the directory (but it
> doesn't remove the core 1 from the sharer list).
> - Finally, the L1_PUTX arrives at L2. Since the L1cache-1 is still a sharer,
> is not marked at L1_PUT_old, but instead is recycled (the line is blocked at
> L2 (MT_IB) waiting for a WB_Data from L1cache-1).
> - The GETX from L1cache-1 arrives at L2 and it's also recycled.
> - Both GETX and PUTX from L1cache-1 are recycled a few times.
> - The WB_data from core 1 arrives, and the line is unblocked.
> - In this moment, the GETX is the next msg in the recycled queue (because
> PUTX was considered right before the WB_data arrived), so it's processed and
> the line blocked again, from SS to SS_MB state. The L2 send INV to L1cache-0
> and L2Data to L1cache-1.
> - The PUTX is recycled over and over again since the line is blocked.
> - L1cache-1 receives L2Data, transits from IM to IM_M, waiting for the ack
> from L1cache-0.
> - L1cache-0 receives Inv and sends Ack to L1cache-1.
> - L1cache-1 receives Ack, changes from IM_M to M (resolves the store miss)
> and send Exclusive_Unblock to L2.
> - When the L2 receives the Exclusive_Unblock, changes the state from SS_MB
> to MT.
> - In this moment, the line is not blocked so the PUTX is processed and a
> WB_Ack is sent to the L1cache-1.
> - CRASH: Upon reception, the line is in state M and it shouldn't receive any
> WB_Ack msg in this state (no valid transition).
>
> Can anyone confirm this protocol bug? Or am I missing some subtle but
> important step? Again, my code didn't touch any of the "basic protocol
> stuff", but what confuses me is that the randomized tester can't make the
> original protocol break, but breaks my own version.
>
> Cheers,
>
> Rubén
>
> --
> Ruben Titos
> Parallel Computing and Architecture Group (GACOP)
> Computer Engineering Dept.
> University of Murcia
>

-- 
Ruben Titos
Parallel Computing and Architecture Group (GACOP)
Computer Engineering Dept.
University of Murcia