Incorrect State Transition

Module 18 · Chapter 18.2 · CHI Debugging

Project thread — 18.1 debugged lost ownership. 18.2 debugs incorrect state transitions; 18.3 debugs missing snoops.

1. Learning Outcomes

By the end of this chapter you should be able to:

• Define an incorrect state transition — a missing or wrong FSM transition.
• Recognize the symptom — a cache behaving inconsistently with the events it received.
• Read the waveform signature — an event that should transition the state, but it stays (or goes wrong).
• Use a golden shadow FSM to find the first divergence.
• Locate the missing/mis-conditioned arc from the divergent (state, event) pair.
• Implement a representative shadow-FSM detector in SystemVerilog, Verilog-2001, and VHDL.

2. Why Should I Learn This?

A cache line's behavior is governed by its state, and if the state is wrong, everything downstream is wrong — the cache answers snoops incorrectly, sources stale data, or misses actions it owed. Incorrect state transitions are a large family of coherence bugs, and they are hard to debug by inspection because a wrong state looks, on its own, like a legal state — a line in SC is a perfectly normal thing, unless it should have been invalidated.

The efficient diagnosis is not to reason about the state in isolation but to compare the design's state against a golden one. A shadow FSM — a trusted, independent copy of the correct transition table — runs alongside the design, fed the same events, and computes what the state should be. The first cycle the two diverge is the bad transition, and its (current state, event) pair points directly at the arc in the transition table that is missing or mis-conditioned. This turns "why is this cache in the wrong state?" from an open-ended puzzle into a single-cycle localization. This chapter is that technique.

3. Key Terms

4. Previous Chapter Connection

This chapter debugs the state machines Module 16 implemented — the RN-F snoop FSM (Chapter 16.2), the cache-controller FSM (Chapter 16.4). Where those chapters built the transitions, this one finds the ones that are wrong. The shadow FSM is the reference-model idea of Chapter 17.4 applied to state: an independent golden computation, compared against the design.

The distinction from Chapter 18.1 is the kind of failure. Lost ownership was a data failure — the value was destroyed. An incorrect transition is a control failure — the state is wrong, though the data may be intact. They often appear together (a wrong state causes a wrong data action), but the diagnosis differs: lost ownership traces ownership; an incorrect transition compares against a golden FSM. This chapter adds the shadow-FSM technique to the debugger's toolkit — the sharpest tool for any state-machine failure, and the one that turns a wrong-state symptom into a pinpointed arc.

5. Core Concept — compare against a golden shadow FSM

An incorrect state transition is a missing or wrong arc in the cache FSM; the diagnosis is a golden shadow FSM whose first divergence from the design is the bad transition.

• The state is FSM-driven. A line's state changes only on events — accesses, snoops, completions — through the FSM's transition arcs.
• Incorrect means missing or wrong. A missing arc leaves the line stuck in a stale state (the event did nothing); a wrong arc moves it to the wrong state.
• A wrong state looks legal alone. Any single state (SC, UD, …) is individually valid — the bug is that it is wrong for the events received, invisible without a reference.
• The shadow FSM is the reference. Run a golden, independent copy of the correct FSM on the same events; the first cycle its state diverges from the design's is the bad transition — and the (state, event) at that cycle names the faulty arc.

The synthesis:

An incorrect state transition is a missing arc (state stuck) or a wrong arc (state goes to the wrong value) in a cache's FSM — invisible in isolation because any single state looks legal. The diagnosis is a golden shadow FSM run on the same events: the first cycle it diverges from the design's state is the bad transition, and the divergent (current state, event) pair points directly at the faulty arc in the transition table.

6. Engineering Mental Model — two navigators, one route

Think of two navigators following the same set of turn-by-turn instructions (events) on the same road.

• One navigator is a trusted expert (the shadow FSM) who knows the correct route perfectly. The other is the trainee (the design) whose map may have an error.
• Both start at the same place and receive the same instructions. At each instruction, each moves to where they think they should be.
• As long as they agree on their location after each instruction, the trainee's map is correct so far.
• The first instruction after which they disagree — the expert is at the junction, the trainee is still at the previous street — is the exact point the trainee's map is wrong. You know the instruction (event) and the starting location (state), so you know precisely which map entry (arc) is broken.

The expert navigator is the golden shadow FSM; the disagreement is the first divergence. You do not need to inspect the whole map — the first point of disagreement, with its instruction and location, names the single broken entry.

7. Engineering Diagram — the cache FSM with the missing arc

The correct FSM has an SC → I arc on an invalidating snoop; the buggy design is missing it, so an SC line stays SC when snoop-invalidated. The shadow FSM takes the arc and goes I; the design does not — and they diverge at that event, naming the missing arc. The debugger sees the divergence and reads off the faulty (SC, SnpInvalid) entry.

8. Waveform Signature

The signature is the mismatch going high: the shadow moves to I on the snoop while DUT.state stays SC. The first mismatch cycle is the bad transition, and the event (SnpInv) with the state just before (SC) name the faulty arc (SC, SnpInv). The debugger reads the fix straight off the waveform.

9. Diagnosis Path

The methodical trace using the shadow FSM.

The rule to carry: do not reason about the wrong state — diverge against a golden one. A wrong state is indistinguishable from a legal state by inspection, so the productive move is comparison, not contemplation. The shadow FSM makes the bug temporal and local: the first divergence cycle is the transition, and the (state, event) at that cycle is the arc. You never need to understand why the whole trace is wrong — only the one arc where the design first disagreed with the reference.

10. Tracing an Incorrect Transition — a worked trace

A cache responds to a snoop as if shared for a line that another core has already taken unique — it should be invalid.

1. Symptom: wrong-state behavior. The cache sources/acknowledges a line as SC when the coherence history says it should be I. Its state is wrong.
2. Run the shadow FSM. Feed the golden FSM the same event stream — the ReadShared that made it SC, then the SnpInvalid from another core's ReadUnique.
3. Find the first divergence. Through the ReadShared, DUT and shadow agree (both SC). At the SnpInvalid, the shadow goes I; the DUT stays SC. First divergence: that cycle.
4. Read the arc. At divergence the state was SC and the event was SnpInvalid. The faulty arc is (SC, SnpInvalid) → I — which the DUT is missing.
5. Fix. Add the SC → I transition on an invalidating snoop to the cache FSM (Chapter 16.2/16.4). Re-run: DUT and shadow now agree.

The wrong-state symptom localized to a single missing arc via the first divergence. The DebugLab formalizes this.

11. Detector View — a golden shadow FSM

Compute the expected next state from the current state and event; flag any cycle the design's next state differs. Representative.

// Representative shadow-FSM detector (educational).
// A GOLDEN next-state function computes the expected state from (current, event). The
// detector compares the design's actual next state against it; the FIRST mismatch is the
// bad transition, and the (cur_state, event) at that cycle names the faulty arc.
typedef enum logic [1:0] { ST_I, ST_SC, ST_UC, ST_UD } state_e;
typedef enum logic [1:0] { EV_RDSH, EV_RDUNI, EV_SNPINV, EV_NONE } event_e;
 
module chi_state_shadow (
  input  logic   clk, rst_n,
  input  state_e dut_state,     // the design's current state (observed)
  input  event_e ev,            // the event this cycle
  output state_e expected,      // golden expected next state from (dut_state, ev)
  output logic   mismatch       // dut_state disagrees with the golden expectation
);
  // GOLDEN next-state function (the correct transition table).
  function automatic state_e golden_next(state_e s, event_e e);
    case (e)
      EV_RDSH:   golden_next = ST_SC;                         // I -> SC
      EV_RDUNI:  golden_next = ST_UC;                         // I -> UC
      EV_SNPINV: golden_next = ST_I;                          // ANY -> I  (the key arc)
      default:   golden_next = s;                             // no event: hold
    endcase
  endfunction
 
  state_e exp_q;
  assign expected = exp_q;
  // Mismatch: the design's observed state differs from what the golden FSM expected.
  assign mismatch = (dut_state != exp_q);
 
  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) exp_q <= ST_I;
    else        exp_q <= golden_next(exp_q, ev);   // shadow advances on the SAME events
  end
endmodule

The same behavior in Verilog-2001:

// Representative shadow-FSM detector (Verilog-2001).
module chi_state_shadow (
  input        clk, rst_n,
  input  [1:0] dut_state,       // 0=I 1=SC 2=UC 3=UD
  input  [1:0] ev,              // 0=RdSh 1=RdUni 2=SnpInv 3=None
  output [1:0] expected,
  output       mismatch
);
  localparam ST_I=2'd0, ST_SC=2'd1, ST_UC=2'd2;
  localparam EV_RDSH=2'd0, EV_RDUNI=2'd1, EV_SNPINV=2'd2;
  reg [1:0] exp_q;
 
  function [1:0] golden_next; input [1:0] s, e;
    begin
      case (e)
        EV_RDSH:   golden_next = ST_SC;
        EV_RDUNI:  golden_next = ST_UC;
        EV_SNPINV: golden_next = ST_I;
        default:   golden_next = s;
      endcase
    end
  endfunction
 
  assign expected = exp_q;
  assign mismatch = (dut_state != exp_q);
 
  always @(posedge clk or negedge rst_n) begin
    if (!rst_n) exp_q <= ST_I;
    else        exp_q <= golden_next(exp_q, ev);
  end
endmodule

And in VHDL:

-- Representative shadow-FSM detector (VHDL).
library ieee;
use ieee.std_logic_1164.all;
 
entity chi_state_shadow is
  port (
    clk, rst_n : in  std_logic;
    dut_state  : in  std_logic_vector(1 downto 0);   -- 00=I 01=SC 10=UC 11=UD
    ev         : in  std_logic_vector(1 downto 0);   -- 00=RdSh 01=RdUni 10=SnpInv 11=None
    expected   : out std_logic_vector(1 downto 0);
    mismatch   : out std_logic
  );
end entity;
 
architecture rtl of chi_state_shadow is
  constant ST_I  : std_logic_vector(1 downto 0) := "00";
  constant ST_SC : std_logic_vector(1 downto 0) := "01";
  constant ST_UC : std_logic_vector(1 downto 0) := "10";
  signal exp_q   : std_logic_vector(1 downto 0) := ST_I;
 
  function golden_next(s, e : std_logic_vector(1 downto 0)) return std_logic_vector is
  begin
    case e is
      when "00"   => return ST_SC;     -- RdSh  -> SC
      when "01"   => return ST_UC;     -- RdUni -> UC
      when "10"   => return ST_I;      -- SnpInv-> I  (the key arc)
      when others => return s;         -- none: hold
    end case;
  end function;
begin
  expected <= exp_q;
  mismatch <= '1' when dut_state /= exp_q else '0';
 
  process (clk, rst_n)
  begin
    if rst_n = '0' then
      exp_q <= ST_I;
    elsif rising_edge(clk) then
      exp_q <= golden_next(exp_q, ev);   -- shadow advances on the same events
    end if;
  end process;
end architecture;

All three advance a golden FSM on the same events and raise mismatch when the design's observed state disagrees — the first mismatch being the bad transition. The DebugLab's design is missing the SnpInvalid → I arc, so it stays SC while the shadow goes I.

12. Assertion View — the design tracks the golden FSM

The properties formalize the check: the design's state matches the golden next-state at all times.

// Bind to chi_state_shadow.
// 1. The design's state always matches the golden expected state (no divergence).
property p_matches_golden;
  @(posedge clk) disable iff (!rst_n)
    !mismatch;
endproperty
 
// 2. An invalidating snoop always drives the state to I (the arc under test).
property p_snpinv_goes_I;
  @(posedge clk) disable iff (!rst_n)
    (ev == EV_SNPINV) |=> (dut_state == ST_I);
endproperty
 
// 3. The first mismatch is the bad transition -- capture (cur_state, event) there.
//    cover: (mismatch && !$past(mismatch)) -> record $past(dut_state), $past(ev)

The system point, beyond the checks:

The shadow-FSM method works because it converts a state question ("is this state right?") — which has no local answer — into a transition question ("did this arc fire correctly?") — which does. A state is a snapshot with no inherent right or wrong; a transition is a function of a known input (event) and a known prior (state), so it has a definite correct output that a golden table specifies. By comparing every cycle, the detector catches the error at the transition where it is introduced, not at some later cycle where its consequences surface — and the first divergence is guaranteed to be the root transition, because up to that point the two FSMs were identical. This is a powerful and general debugging pattern: when a piece of state can be wrong for non-local reasons, run an independent golden computation of that state in lockstep and diff them — the diff localizes the bug to the exact step it was introduced. It is the reference-model idea (Chapter 17.4) specialized to a sequential machine, and it inherits the same requirement: the shadow must be independent (a separate, trusted transition table), or a shared FSM bug would make both diverge the same way and hide the error (common-mode, Chapter 17.4).

• What it proves: the design's state matches the golden FSM every cycle (no bad transitions).
• What it does not prove: the golden table is correct — that is a review obligation (independence).
• Bug signature: mismatch asserting — the first cycle names the faulty arc via (state, event).

13. Testbench — a missing arc must show as a divergence

Drives the event stream past a snoop the design mishandles and checks the shadow diverges.

module tb_chi_state_shadow;
  logic clk = 0, rst_n = 0;
  logic [1:0] dut_state, ev, expected;
  logic mismatch;
  localparam ST_I=2'd0, ST_SC=2'd1, ST_UC=2'd2;
  localparam EV_RDSH=2'd0, EV_RDUNI=2'd1, EV_SNPINV=2'd2, EV_NONE=2'd3;
  int errors = 0;
 
  chi_state_shadow dut (.*);
  always #5 clk = ~clk;
 
  // Model a BUGGY design FSM: it is MISSING the SnpInvalid -> I arc (stays put).
  logic [1:0] dut_fsm;
  always @(posedge clk or negedge rst_n) begin
    if (!rst_n) dut_fsm <= ST_I;
    else case (ev)
      EV_RDSH:  dut_fsm <= ST_SC;
      EV_RDUNI: dut_fsm <= ST_UC;
      // EV_SNPINV: (missing!) -> dut_fsm stays -> the bug
      default:  dut_fsm <= dut_fsm;
    endcase
  end
  assign dut_state = dut_fsm;
 
  initial begin
    ev = EV_NONE;
    @(posedge clk) rst_n = 1;
 
    // ReadShared -> SC: design and shadow agree.
    @(posedge clk) ev = EV_RDSH;
    @(posedge clk) ev = EV_NONE;
    #1;
    if (mismatch) begin errors++; $display("FAIL false mismatch after RdShared"); end
    else $display("PASS agree after ReadShared (both SC)");
 
    // SnpInvalid: shadow -> I, but buggy design STAYS SC -> divergence.
    @(posedge clk) ev = EV_SNPINV;
    @(posedge clk) ev = EV_NONE;
    #1;
    if (!mismatch) begin errors++; $display("FAIL missing SC->I arc NOT detected"); end
    else $display("PASS divergence at SnpInvalid: DUT=%0d shadow(exp)=%0d -> bad arc (SC,SnpInv)", dut_state, expected);
 
    if (errors == 0) $display("ALL TESTS PASSED");
    else             $display("%0d FAILURE(S)", errors);
    $finish;
  end
endmodule

Expected output:

PASS agree after ReadShared (both SC)
PASS divergence at SnpInvalid: DUT=1 shadow(exp)=0 -> bad arc (SC,SnpInv)
ALL TESTS PASSED

14. DebugLab — a cache stuck shared after an invalidating snoop

events: ReadShared (-> SC), then SnpInvalid (from another core's ReadUnique)
after ReadShared:  DUT = SC, shadow = SC  -> AGREE
at SnpInvalid:     shadow: SC -> I         DUT: stays SC   -> FIRST DIVERGENCE
  -> mismatch high; state before = SC, event = SnpInvalid
  -> faulty arc = (SC, SnpInvalid) -> I, which the DUT FSM is MISSING
correct: add SC -> I on SnpInvalid -> DUT tracks the shadow again

15. Common Mistakes

• Reasoning about the wrong state. Assumption: inspect the state. Bug: a wrong state looks legal. Prevention: diff against a golden FSM.
• No shadow FSM. Assumption: the design's state is self-evidently right. Bug: no reference. Prevention: run a golden shadow.
• A non-independent shadow. Assumption: reuse the design's FSM. Bug: common-mode (Chapter 17.4). Prevention: an independent table.
• Chasing a late symptom. Assumption: the bug is where behavior looks wrong. Bug: it is at the first divergence. Prevention: find the first mismatch.
• Missing an arc vs wrong arc. Assumption: only wrong destinations. Bug: a stuck state (missing arc). Prevention: check both.
• Confusing with lost ownership. Assumption: same family. Bug: state vs data. Prevention: 18.2 is control; 18.1 is data.

16. Engineering Checklist

• Run a golden shadow FSM on the same events as the design.
• Find the first cycle the design's state diverges from the shadow.
• Read the (state, event) at that cycle to name the faulty arc.
• Determine whether the arc is missing (stuck) or wrong (bad destination).
• Add/correct the arc in the transition table (16.2 / 16.4).
• Keep the shadow FSM independent of the design (no common-mode).

17. Key Takeaways

• An incorrect transition is a missing arc (stuck) or a wrong arc (bad state).
• A wrong state is invisible in isolation — any single state looks legal.
• A golden shadow FSM run on the same events reveals the bug.
• The first divergence is the bad transition; its (state, event) names the arc.
• Diff, do not contemplate; the shadow must be independent.
• Diagnose state failures by comparison; the model here is representative.

18. Quick Revision

Incorrect state transition. A cache line's state is driven by an FSM reacting to events (accesses, snoops, completions), and an incorrect transition is a missing arc (the event does nothing, leaving the line stuck in a stale state) or a wrong arc (the state goes to the wrong value). The cache then behaves inconsistently with the events it received — responding to a snoop as shared when it should be invalid, or claiming a dirty copy it no longer holds. The failure is hard to see by inspection because any single state is individually legal; the bug is that it is wrong for the events. The diagnosis is a golden shadow FSM — a trusted, independent copy of the correct transition table — run on the same events: the first cycle the design's state diverges from the shadow's is the bad transition, and the (current state, event) at that cycle names the faulty arc directly. This converts an unanswerable state question into a definite transition question, and localizes the bug to the exact step it was introduced (up to there the two FSMs were identical). Root causes are transition-table bugs in the RN-F snoop FSM (Chapter 16.2) or the cache controller (Chapter 16.4). The shadow must be independent (Chapter 17.4), or a shared bug hides the error. Diff, do not contemplate. Representative model; 18.3 debugs missing snoops.

Coming Next

Chapter 18.3 — Missing Snoop. An incorrect transition is a local FSM failure; a missing snoop is a fabric-level one. Chapter 18.3 covers missing snoops — a sharer that should have been snooped but was not, the waveform signature of a coherence action with an empty snoop channel to a known sharer, and the diagnosis of comparing snoops sent against the directory's sharer set to find the sharer that was skipped.