CXL State Management

13.3 used five state names as if everyone agreed what they were.

They are not names. Each one is a tuple of facts about a line, and the interesting part of the space is the states between them — the ones that exist while a transition is still in progress, and which outnumber the stable states people draw on whiteboards.

1. The Engineering Problem — Most Of The State Space Is Invisible

Ask an engineer to draw MESI and you get four circles. Ask them to draw the states a real controller implements and the answer is usually somewhere between twelve and thirty, most of which have no name in any textbook.

The gap is the transient states, and there are three reasons they matter more than the stable ones.

A line spends a large fraction of its life in them. Between deciding to fetch a line and having it, the line is in a state that is neither the old one nor the new one. Measured over a sampled run in this chapter, 16% of a line's observed lifetime was spent mid-transition. On a system with longer link latencies the fraction rises, because the transient duration is set by the interconnect and the stable duration is set by the workload.

Every hard coherency bug lives in them. A snoop that arrives while a line is in flight cannot be answered from the state the line is leaving and cannot be answered from the state it has not reached. Dropping it stalls a requester forever; answering it immediately answers from a state that is about to be wrong. Neither the old state nor the new one is a correct place to stand.

They are where the state and its meaning come apart. A stable state is a consistent tuple — permission, data, duty, all agreeing. A transition changes all three, and if it changes them in different cycles there is an interval in which the line is describable by no legal tuple at all.

The state space is the contract; the flows are how it gets used. This chapter builds the space and the machinery. Module 14 owns the concrete read, write and ownership-transfer flows that walk through it.

2. The One-Sentence Model

A state is a tuple of facts, not a name. The encoding exists to make illegal tuples unrepresentable, the transition graph exists to make illegal moves impossible, and the machinery exists to change every fact in the tuple at the same instant.

Call it one tuple, one instant. Every defect in this chapter is a fact that changed on its own, a move with no edge, or a state nothing downstream can interpret.

3. What This Chapter Owns

Deferred:

The line against Module 14 is worth stating precisely. This chapter answers "what states exist, which moves are legal, and how is a move applied." Module 14 answers "what actually happens when a host reads a line a device has modified" — a sequence of messages that walks a path through this graph. A flow that cannot be expressed as a path here is a flow that is wrong; that is what makes the space worth building first.

4. Teaching-Model Boundary

Every model below is a teaching model, compiled and simulated with Icarus Verilog 13.0, and checked by a testbench whose oracle is structurally different from the design.

What these models are not: a coherency controller. There is no request pipeline, no directory cache, no MSHR allocation policy, no back-invalidation, and no CXL encoding. A production controller has one state machine per outstanding transaction on top of the per-line state this chapter builds.

Four conventions carry over and are used without comment.

Every checker tests cond !== 1'b1. On an uninitialised signal !cond evaluates to x, which is not true, so a naive check passes vacuously.

Unreachable monitors get a FAULT_INJECT build of the same source. This chapter needs it four times — for the torn-tuple monitor, the recovery-loss monitor, the double-outcome monitor, and the undefined-encoding monitor. A monitor that has never fired is a monitor nobody has tested.

Where two policies are compared, they are one source under a parameter. state_decode takes SEPARATE_PERM, snoop_race takes DROP_SNOOPS, line_ctrl takes TRUST_CALLER. Every comparison in this chapter is a measured difference between two instances of the same file.

Every displayed value is a captured signal. No summary line prints a literal.

5. RTL 1 — A State Is A Tuple, Not A Name

Start with what a state means rather than what it is called:

  // The single source of truth: permission is DERIVED from state, never stored.
  assign d_rd     = (st == S) || (st == E) || (st == M) || (st == O);
  assign d_wr     = (st == E) || (st == M);
  assign has_data = d_rd;
  assign owes_data= (st == M) || (st == O);
  assign stable   = (st <= O);

Four facts. Every named state is one combination of them, and the reason the encoding exists is to make the other combinations unrepresentable:

  // Three tuples that must never exist: write without read, owing data
  // without holding it, and write permission in a state that is not exclusive.
  // The third is checked against the STATE's exclusivity rather than against
  // the decode, so it catches a stored permission that no longer matches.
  assign exclusive = (st == E) || (st == M);
  assign illegal_tuple_err = (can_write && !can_read)
                          || (owes_data && !has_data)
                          || (can_write && !exclusive);

The SEPARATE_PERM parameter is where the chapter earns its title. It builds a second copy of the same module that stores permission in its own registers rather than deriving it — which is what a real design does when the tag array and the permission check live in different pipeline stages, and it is how two records of one fact end up disagreeing.

Drive both builds. Load the stored copy with the permission for M, then move the state to O without telling it. Measured:

  decode  : perm drift (stored)=1 illegal tuple (stored)=1 | derived=0/0

The stored build now claims write permission on an owned line. The derived build cannot reach that state at all — not because it checks for it, but because the expression that produces can_write has no way to disagree with the state it reads. That is the difference between an invariant enforced by a checker and one enforced by construction.

All five stable states were checked against an oracle that holds the four facts as a hand-written table, and the three transient encodings were confirmed to report stable=0.

6. RTL 2 — Which Moves Exist At All

A transition table is not "what happens next." That is a flow. This is the prior question: does this edge exist in the graph?

      M: legal = ((cause == C_LRD) && (to_st == M))
              || ((cause == C_LWR) && (to_st == M))
              || ((cause == C_RRD) && (to_st == O))
              || ((cause == C_RWR) && (to_st == I))
              || ((cause == C_EVI) && (to_st == I));

Every legal edge is written once, in one place. A design that spreads this across a dozen case statements in a dozen modules has no way to answer "is this edge legal" as a question at all — the answer is distributed across the implementation, which means it cannot be checked, reviewed, or compared against a specification.

The testbench sweeps the whole space: 8 source states × 6 causes × 8 destination states = 384 combinations, each compared against an oracle that is an explicit hand-written edge list. Measured:

  legality: 28 legal edges out of 384 combinations, rejected=1

Twenty-eight edges out of three hundred and eighty-four. Slightly over 7% of the combinations are legal moves; the rest are things a correct controller must never do. That ratio is the argument for writing the table down: a state machine spread across the implementation is a state machine in which the other 93% are reachable by accident.

The rejected transition in the run is the one worth naming: S straight to M. It looks obviously right — the agent has the line and wants to write it — and it is illegal, because acquiring write permission from a shared state requires invalidating the other holders, and that takes time. The legal edge is S to the upgrade transient. Skipping it is not an optimisation; it is a design that grants write permission while other agents still hold readable copies.

7. RTL 3 — The States Nobody Draws

Between "I want this line" and "I have it" the line is in a transient state. The model tracks the three things that matter about it: how long it has been there, whether a second request arrived for a line already in flight, and whether it ever resolved at all.

  assign stuck_err      = busy_q && (age_q >= TIMEOUT[7:0]);
  assign reenter_err    = enter && busy_q;

with the peak latched rather than sampled:

        // Latch the peak: the window that caused the problem has closed by the
        // time anyone looks at a current-value counter.
        if (age_q + 8'd1 > max_age) max_age <= age_q + 8'd1;

Three transactions were driven: a short one, one that never completed, and a short one after it. Measured:

  transient: entered=3 completed=3 stuck=1 reenter=1
  peak age : first=5 after the long one=14, unreduced by a later short window=14

Read the last figure carefully. A later short window does not reduce the latched peak. A current-value counter would read 2 by the time anyone investigated, and the fourteen-cycle transaction that caused the problem would be invisible. This is the same reasoning as the exposure-window latch in 13.2, applied to a different window, and it is the single most common reason a performance counter fails to explain an intermittent stall.

reenter_err catches the case that looks harmless: a second request for a line that is already being fetched. Without the check, the second request overwrites the pending target, and the fill that eventually arrives is applied to the wrong intent — a read-fill landing in a state that expected write permission.

8. Waveform — A Line Through Its Whole Life

Transcribed from the printed cycle trace of the controller in section 15.

The busy row is the point of the chapter. It is high for four of the ten cycles shown, and during every one of them the line is in a state that no MESI diagram contains. The single refused pulse at cycle 2 is a second request arriving for a line already in flight — refused at the state machine's boundary, not absorbed into it.

Over the full trace:

  moves=6 refused=1 illegal_exposed=0

Six legal moves, one refusal, and the state never left the eight defined encodings. The last figure is the one a reviewer should ask about, and section 15 explains why it is not trivially zero.

9. RTL 4 — A Transition Is Not One Write

A transition changes three things: the state, the permission it grants, and the duty it carries. They must change together or not at all.

  // The monitor reads the committed state, so it is a statement about what the
  // line IS -- not about the request that produced it.
  assign torn_err = ((st_q == M) && !(wr_q && duty_q))
                 || ((st_q == O) && !(duty_q && !wr_q))
                 || ((st_q == S) && (wr_q || duty_q))
                 || ((st_q == I) && (wr_q || duty_q));

The monitor is unreachable in the atomic build, so the same source carries a hook:

      // FAULT_INJECT commits the state now and the duty one commit late --
      // the pipeline stage that lags, rather than one that never fires. Every
      // torn tuple in the monitor becomes reachable this way.
      wr_q   <= next_wr;
      dly_q  <= next_duty;
      duty_q <= (FAULT_INJECT != 0) ? dly_q : next_duty;

The late duty rather than a frozen one is deliberate, and it is worth explaining because the first version of this model used a frozen duty and two clauses of the monitor stayed unreachable. A duty that never updates can only produce one shape of torn tuple; a duty that lags by one commit can produce all four. Measured across a sequence through M, O and I:

  atomic   : torn (atomic build)=0  torn (faulty build)=1
  torn     : at M=1 at O=1 at I=1 (faulty build); atomic build=0

Three different torn tuples, all from one lagging register. The atomic build committed five states and never produced one. Note what the faulty build looks like from the outside: the state field is always a legal value, the permission field is always a legal value, and only their combination is impossible — which is why a monitor on any single field would report a clean run.

10. RTL 5 — The Snoop That Arrives Mid-Flight

This is the hardest case in the chapter and the reason transient states cannot be an implementation detail.

A snoop arrives for a line that is mid-transition. It cannot be answered from the state the line is leaving — that state is about to be wrong. It cannot be answered from the state the line has not reached — that state does not have the data yet. And it cannot be dropped, because a requester on the far side of a link is waiting for it.

  // A snoop during a transition is deferred; one outside a transition is
  // answered at once; and a deferred snoop is answered when the line settles.
  assign defer      = snoop && in_transient && (DROP_SNOOPS == 0);
  assign answer_now = (snoop && !in_transient)
                   || (pend_q && transition_done);
  // The build that drops them is what a design does when it has no queue.
  assign dropped_err = snoop && in_transient && (DROP_SNOOPS != 0);

Deferral is the only correct move, and it requires storage: the requester's identity has to survive until the line settles. A design without that storage has exactly two options, and both are wrong.

Both builds were driven with a snoop outside a transition, a snoop during one, and the completion. Measured:

  snoop    : deferred=1 answered=2 dropped=0 | dropping build dropped=1

The correct build answered two snoops — the one on a settled line immediately, and the deferred one when the transition completed — and remembered the requester's identity across the gap. The dropping build answered one and lost the other, with no error visible to the requester, which simply waits.

This is where the state space stops being a diagram and starts costing silicon. The queue that holds a deferred snoop is per outstanding transaction, and its depth is a design parameter that the transient duration determines.

11. RTL 6 — Getting Out Of Any State Safely

An error recovery must reach I from wherever the line happens to be. The constraint is that a line carrying a debt must settle it on the way out:

        IDLE: if (recover) begin
                dirty_q <= (cur_st == M) || (cur_st == O);
                // A clean line goes straight to invalidation; a dirty one must
                // settle first. The branch is the whole model.
                ph_q <= (SKIP_SETTLE == 0 && ((cur_st == M) || (cur_st == O)))
                        ? SETTLE : INVAL;
                n_recoveries <= n_recoveries + 8'd1;
              end

with the failure it prevents made explicit:

  // Reaching the invalidating phase with an unsettled debt is data loss.
  assign lost_on_recovery_err = (ph_q == INVAL) && dirty_q;

That monitor is unreachable in the correct build, so SKIP_SETTLE provides a build that invalidates a dirty line without settling it. Three recoveries were driven — from S, from M, and from O. Measured:

  recovery : recoveries=3 writebacks=2 lost_on_recovery=0 | skip-settle build lost=1

A clean line skipped the settling phase entirely and reached safety in one step. The dirty ones waited, and the model held in the settling phase across multiple cycles until the writeback completed rather than advancing on a timer. The skip-settle build reached the invalidating phase with the debt outstanding and the monitor fired.

The reason this model exists separately from the eviction path in 13.3 is that recovery has no cooperating agent. An eviction is a decision the cache makes with the protocol running normally; a recovery happens because something has already gone wrong, and it must work from every state including the transients.

12. RTL 7 — One Place Where Permission Is Checked

A design with two permission checks has two chances to disagree. This is the one:

  // The three denials are different problems with different costs. Merging
  // them tells an engineer an access failed and nothing about the fix.
  assign deny_in_flight  = acc_valid && transient;
  assign deny_no_copy    = acc_valid && !transient && (st == I);
  assign deny_read_only  = acc_valid && !transient && acc_is_write && rd_ok && !wr_ok;
  assign allow           = acc_valid && !transient
                           && (acc_is_write ? (wr_ok || (FAULT_INJECT != 0))
                                            : rd_ok);

Three denials, each with a different remedy and a different cost: fetch the line, upgrade the permission, wait for the transition. A single access_denied signal tells an engineer that something failed and nothing about which of those three to look at.

Every state was driven for both a read and a write — sixteen accesses across the whole space. Measured:

  gate    : allow=6 fetch=2 upgrade=2 wait=6 double=0

Six allowed, two needing a fetch (read and write on I), two needing an upgrade (write on S and on O), and six landing on a line in flight — the three transient states times two access types. That last figure is the chapter's argument in one number: more accesses were blocked by a transition than by any permission problem.

double_denial_err counts the outcomes and requires exactly one:

  assign double_denial_err = acc_valid &&
    (({3'd0,allow} + {3'd0,deny_no_copy} + {3'd0,deny_read_only}
      + {3'd0,deny_in_flight}) != 4'd1);

It cannot fire in the correct gate. The FAULT_INJECT build grants a write on a line that only has read permission, so the access is simultaneously allowed and told to upgrade. Measured: checked=0, faulty=1.

13. RTL 8 — Where A Line Actually Spends Its Life

Everything above argues that the transient states matter. This model measures it:

  logic [31:0] weighted;   // 16 bits x 100 needs 23; 16 would silently wrap
  assign weighted = {16'd0, t_transient} * 32'd100;
  assign transient_pct = (t_total == 16'd0) ? 8'd0
                       : (weighted / {16'd0, t_total});

Thirty samples were taken across a line's life. Measured:

  census  : I=10 S=6 E=2 M=4 O=3 transient=5 of 30 (16%)

Sixteen percent of the line's observed life was spent in a state no MESI diagram contains. That number is a property of this stimulus rather than of any real workload — the point is not the value but that it is measurable at all, and that a design which treats the transients as an implementation detail is treating a sixth of the state space as an implementation detail.

The width commentary is the same defect class that appeared eight times across Module 12: Verilog sizes an expression from its operands, not its destination, so a 16-bit multiply by 100 wraps above 655 samples and reports a plausible, wrong percentage under exactly the sustained load an engineer would use it to investigate.

The empty-sample guard reports zero rather than a hundred before any sample is taken, for the same reason it did in 13.3: a ratio computed from no evidence is at its most confident precisely when it knows least.

14. RTL 9 — Two Causes, One Cycle

A local write and a remote read arrive for the same line in the same cycle. They cannot both be applied to the same starting state:

  // Remote requests win. A local access can be retried against the new state;
  // a remote one has a requester waiting on the far side of a link.
  assign take_remote      = remote_req;
  assign take_local       = (APPLY_BOTH != 0) ? local_req
                                              : (local_req && !remote_req);
  assign reeval_needed    = local_req && remote_req;
  assign reeval_cause     = local_cause;
  assign both_applied_err = take_local && take_remote;

The priority is not arbitrary. A local access can be retried by the core that issued it, at the cost of a few cycles. A remote request has an agent on the far side of a link waiting on it, with a timeout running, and possibly a whole coherency transaction blocked behind it. Losing a local request costs latency; losing a remote one can stop the protocol.

The reeval_cause output is the part that is easy to omit. The losing local access must be re-evaluated against the state the winner left behind — a write that was legal against M may need an upgrade transient against O. Discarding the cause and simply retrying the access is correct only if the retry re-enters the permission gate from the top, which is a property of the surrounding pipeline rather than of this model.

Measured:

  conflict: remote wins, reeval=1 | both-applied build err=1

The correct build took the remote cause, refused the local one, and asked for a re-evaluation carrying the local cause. The APPLY_BOTH build applied both to one starting state and was caught.

15. RTL 10 — The Machinery Assembled

Everything above, wired for one line: hold the state, refuse moves with no edge, enter and leave the transients, and never expose a state the rest of the system cannot interpret.

  // Four bits for eight states. That is not waste -- it is what every real
  // design looks like, and it is why an undefined encoding is representable
  // at all. A field exactly as wide as its state space cannot hold a bug.
  localparam logic [3:0] I=4'd0, S=4'd1, E=4'd2, M=4'd3, O=4'd4;
  localparam logic [3:0] T_IS=4'd5, T_IM=4'd6, T_SM=4'd7;

The width choice is the interesting one, and it came out of the mutation work in section 17. A three-bit field holding eight defined states makes the undefined-encoding monitor dead code — there is no value it can detect, so it reads zero whether it works or not. Real state fields are wider than their state spaces, because encodings get reserved, extended, or padded to a byte, and that is precisely where an undefined state comes from.

  // Eight of the sixteen encodings mean something. A state outside the space
  // is not a wrong answer, it is an uninterpretable one -- nothing downstream
  // can decode a permission from it.
  assign illegal_exposed_err = (st_q > T_SM);

The TRUST_CALLER build applies whatever move is asked for without checking that the edge exists, and the encoding it lands on need not be one of the eight. Driving an eviction of an invalid line — a cause with no edge from I — the checked build refused and the trusting build landed outside the state space entirely. Measured:

  ctrl    : moves=13 refused=2 illegal_exposed=0 | trusting build exposed=1

Thirteen legal moves through a full life, two refusals, and the state never left the eight defined encodings. The line was driven from I through the fill transient into E, to M, to O, through the upgrade transient back to M, and separately through the write-intent transient — the second fill transient, which lands in M regardless of how many other agents held the line, because the intent was a write.

The guard on the request path is a single condition:

    if (fill && busy) begin
      ...
    end else if (req && !busy) begin

A fill is only meaningful for a line in flight, and a request is only meaningful for a line that is not. An unexpected fill for a settled line was driven and did not move the state or advance the move counter — it belongs to no transaction, and a controller that accepts it is a controller that will apply a stale response from a transaction it already completed.

16. Quantitative Reasoning

Everything below follows from the measured numbers above.

The graph is sparse. 28 legal edges out of 384 source-cause-destination combinations is 7.3%. That ratio is why the table is written in one place: 93% of the combinations are moves a correct controller must never make, and a state machine distributed across an implementation makes them reachable by omission rather than by decision.

Transient occupancy scales with the interconnect, not the workload. Measured at 16% of a sampled life with a short fill. The stable-state residency is set by how often the workload touches the line; the transient residency is set by the fetch latency. Double the link latency and the transient fraction roughly doubles, which is why the number matters more on a CXL system than on a single die.

The state field costs more than the state count suggests. Eight states need three bits. Adding the three transients to a four-state MESI space takes it from four states to seven, which crosses the two-bit boundary — the transients, not the Owned state, are what force the third bit in a MESI design. Padding to four bits for future encodings costs a fourth bit per line: at a 64-byte line, four bits of state is 0.78% of the tracked capacity before any sharer vector.

The deferred-snoop queue is sized by concurrency, not by latency. One entry per outstanding transaction that can receive a snoop. A controller with 16 MSHRs needs 16 deferral slots plus the requester identity in each; at 6 bits of identity that is 112 bits of storage whose only purpose is to hold snoops that arrived at an inconvenient moment.

Three denials, three costs. A fetch costs a full memory or link round trip. An upgrade costs an invalidation round trip to every sharer. A wait costs the remainder of the current transient. Measured over the whole state space, six of sixteen accesses hit the third case — more than either of the other two — and a design that reports all three as one signal cannot tell an engineer which of those three costs it is paying.

17. Assertions

Presented as SystemVerilog and executed as procedural checkers — see section 19.

Permission is a function of state.

property p_no_perm_drift;
  @(posedge clk) disable iff (!rst_n)  (can_write == derived_wr);
endproperty

Write permission implies exclusivity.

property p_write_needs_exclusive;
  @(posedge clk) disable iff (!rst_n)  can_write |-> exclusive;
endproperty

A debt implies the data is held.

property p_debt_needs_data;
  @(posedge clk) disable iff (!rst_n)  owes_data |-> has_data;
endproperty

Only edges in the graph are applied.

property p_only_legal_edges;
  @(posedge clk) disable iff (!rst_n)  (apply && !legal) |-> illegal_transition_err;
endproperty

A transient state always resolves.

property p_transient_resolves;
  @(posedge clk) disable iff (!rst_n)
    in_transient |-> ##[1:TIMEOUT] !in_transient;
endproperty

No second request for a line already in flight.

property p_no_reenter;
  @(posedge clk) disable iff (!rst_n)  (enter && in_transient) |-> reenter_err;
endproperty

The committed tuple is always legal.

property p_no_torn_tuple;
  @(posedge clk) disable iff (!rst_n)  !torn_err;
endproperty

A snoop during a transition is deferred, never dropped.

property p_snoop_deferred;
  @(posedge clk) disable iff (!rst_n)  (snoop && in_transient) |-> defer;
endproperty

Every deferred snoop is eventually answered.

property p_deferred_answered;
  @(posedge clk) disable iff (!rst_n)
    deferred_pending |-> ##[1:$] answer_now;
endproperty

A recovery settles the debt before invalidating.

property p_recovery_settles;
  @(posedge clk) disable iff (!rst_n)  (phase == INVAL) |-> !debt_outstanding;
endproperty

Exactly one outcome per access.

property p_one_outcome;
  @(posedge clk) disable iff (!rst_n)
    acc_valid |-> $countones({allow, deny_no_copy, deny_read_only, deny_in_flight}) == 1;
endproperty

Never two causes applied to one starting state.

property p_one_cause;
  @(posedge clk) disable iff (!rst_n)  !(take_local && take_remote);
endproperty

The state never leaves the defined space.

property p_state_defined;
  @(posedge clk) disable iff (!rst_n)  (st <= T_SM);
endproperty

18. Mutation Testing

86 mutations were injected into the ten models, one at a time, each a single-line change a competent engineer could plausibly write. Every one must make the testbench print RESULT: FAIL.

Representative mutations, all killed:

Eleven mutations survived the first run. None was patched away; each was classified and either the testbench or the design was extended.

Four stimulus gaps. The bench never sampled the E or O states in the census, never entered the write-intent transient at all, never issued a fill for a settled line, and never followed a long transient with a short one. Four cases added, four mutations killed. The write-intent gap is the instructive one: the bench walked I to S to M by way of a read, and never once asked for a line it intended to write, so an entire transient state was unexercised.

Two unobserved outputs. The transient share before any sample was taken, and the outstanding-debt flag during a recovery, were both computed and never read.

Four unreachable checkers. The torn-tuple monitor, the recovery-loss monitor, the double-outcome monitor and the undefined-encoding monitor are all unreachable in a correct design — that is what makes them invariants. Three were resolved with a FAULT_INJECT build of the same source. The fourth was different, and is worth its own paragraph.

One dead monitor, fixed in the design rather than the bench. illegal_exposed_err tested st_q > T_SM on a three-bit state field holding exactly eight defined states. There is no value it can detect. It is not an unreachable invariant — it is dead code that reads zero whether it works or not, and no fault-injection hook could make it fire. The correct response was to widen the state field to four bits, which is what every real design does anyway: encodings get reserved, extended, or padded, and a field exactly as wide as its state space cannot hold this class of bug or detect it. The monitor then became live, and the TRUST_CALLER build was able to land outside the space and be caught.

One provably equivalent mutation, replaced rather than recorded. The mutation that removed the !busy guard from the request path changed nothing observable, because the transient arm of the case statement already produced the same refusal. The guard and the case arm express one fact twice, so mutating either alone is unobservable. It was replaced with a behaviour-changing mutation on the write-intent fill — which then exposed the stimulus gap above.

A survivor is a finding, not a nuisance. Two of the eleven here changed the design rather than the testbench, and both changes were improvements a reviewer would have asked for independently.

19. Verification Strategy

The oracle must not be the design. Each testbench models the same behaviour in a structurally different representation.

For state_decode the design derives four facts from one state value. The oracle is a hand-written table that knows nothing about the encoding:

      if (s==1) begin rd=1; hd=1; end                       // S
      if (s==2) begin rd=1; wr=1; hd=1; end                 // E
      if (s==3) begin rd=1; wr=1; hd=1; od=1; end           // M
      if (s==4) begin rd=1; hd=1; od=1; end                 // O

For transition_table the design is a nested case statement. The oracle is an explicit edge list written as integer comparisons, and the two are compared across all 384 combinations rather than on a sampled subset. An exhaustive sweep is affordable here precisely because the space is small, and it is the only way to find an edge that exists but should not — a directed test can only find edges that are missing.

For perm_gate the design produces four one-hot outputs. The oracle produces a single integer outcome code, so a design bug that asserts two outputs cannot be reproduced by an oracle that structurally has only one.

For atomic_update the design holds three registers and a monitor over them. The oracle is a table of which tuple each state requires, applied before the commit rather than after.

Every displayed value is a captured signal. Where a value is sampled before a later event changes it, it is latched into a named integer first. No $display in these benches prints a literal.

Delta-cycle discipline. A continuous assignment read in the same delta as its driver changes returns the previous value; every sample of a combinational output is preceded by a settle.

Coverage recorded: 136 assertion sites across three testbenches; all eight states entered including all three transients; all 384 source-cause-destination combinations swept; every state driven for both a read and a write through the permission gate; recoveries from a clean state, from M and from O; snoops inside and outside a transition on both policies; and a transient that resolves, one that does not, and one that follows a longer one.

20. Synthesis and Implementation Reality

The transients force the third state bit. Four stable MESI states fit in two bits. Add three transients and the count is seven, which does not. The state field in any real controller is sized by the transients, not by the named states — and the Owned state from 13.3 then rides along in a bit that was already paid for.

The transition table is a ROM or a decode, not a case statement. At eight states and six causes the flat logic here is fine. At the twenty-plus states of a production controller the same structure becomes a lookup, and the important property is unchanged: the graph is data in one place rather than control flow in many.

The deferred-snoop queue is real storage on a real critical path. It is written when a snoop arrives during a transition and read when the transition completes, so the fill path and the snoop path both touch it in the same cycle. That is a two-port structure per outstanding transaction, and its depth is what bounds how many snoops a controller can absorb before it must backpressure the interconnect.

Atomicity is a placement problem. The state, permission and duty registers must commit from one enable. Splitting them across pipeline stages is exactly the lagging-register fault the FAULT_INJECT build models, and it happens not because anyone decides to but because the three fields end up in different physical arrays for timing reasons.

Reset must land in a defined encoding. st_q resets to I. A state field wider than its space has reset values that mean nothing, and a controller that comes out of reset in encoding 12 has no legal move at all — the illegal_exposed_err monitor is as much a reset check as a transition check.

The permission gate is combinational and on the access path. Merging the three denials would shorten it by a gate and cost every future debugger the information about which remedy applies. That is a bad trade, and section 21 argues the counters are worth even more than the signals.

21. Silicon Observability

Four error signals belong in silicon, not just in simulation. torn_err, illegal_transition_err, illegal_exposed_err and lost_on_recovery_err all detect states from which no correct behaviour is possible, and all four are a handful of gates over registers that already exist. A machine check on any of them converts a silent corruption into a diagnosable fault with a line address attached.

n_entered minus n_completed should be the number of lines currently in flight. A drift is the signature of a transaction that was abandoned — an MSHR freed without its state machine settling — and it is silent until the line is touched again.

max_age is the counter people forget to latch. A current-value age reads whatever is happening now; the fourteen-cycle transaction that caused the stall completed minutes ago. Measured in this chapter: a later short window did not reduce a latched peak of 14, which a current-value counter would have reported as 2.

22. Debug Lab

  decode  : perm drift (stored)=1 illegal tuple (stored)=1 | derived=0/0

assign d_wr = (st == E) || (st == M);      // derived, never stored
assign illegal_tuple_err = (can_write && !can_read)
                        || (owes_data && !has_data)
                        || (can_write && !exclusive);

  legality: 28 legal edges out of 384 combinations, rejected=1

      S: legal = ((cause == C_LWR) && (to_st == T_SM))   // never straight to M

  peak age : first=5 after the long one=14, unreduced by a later short window=14

if (age_q + 8'd1 > max_age) max_age <= age_q + 8'd1;   // latch, never sample
assign stuck_err = busy_q && (age_q >= TIMEOUT[7:0]);

  torn     : at M=1 at O=1 at I=1 (faulty build); atomic build=0

    end else if (commit) begin
      st_q   <= next_st;
      wr_q   <= next_wr;
      duty_q <= next_duty;      // one enable, three registers
    end

  snoop    : deferred=1 answered=2 dropped=0 | dropping build dropped=1

assign defer      = snoop && in_transient;
assign answer_now = (snoop && !in_transient) || (pend_q && transition_done);

  recovery : recoveries=3 writebacks=2 lost_on_recovery=0 | skip-settle build lost=1

ph_q <= ((cur_st == M) || (cur_st == O)) ? SETTLE : INVAL;
SETTLE: if (wb_done) begin dirty_q <= 1'b0; ph_q <= INVAL; end

  gate    : allow=6 fetch=2 upgrade=2 wait=6 double=0

assign deny_in_flight = acc_valid && transient;
assign deny_no_copy   = acc_valid && !transient && (st == I);
assign deny_read_only = acc_valid && !transient && acc_is_write && rd_ok && !wr_ok;

  ctrl    : moves=13 refused=2 illegal_exposed=0 | trusting build exposed=1

localparam logic [3:0] I=4'd0, ... T_SM=4'd7;   // wider than the space
assign illegal_exposed_err = (st_q > T_SM);

23. Design Review

What was built. Ten models: a decode that derives four facts from one state and a parameterised twin that stores them instead, a transition table swept exhaustively, a transient tracker with a latched peak, an atomic commit with a lagging-register fault build, a snoop deferral with a dropping twin, a recovery path with a skip-settle twin, a permission gate with three separate denials, a state census, a two-cause conflict resolver, and a per-line controller that refuses moves with no edge.

What was measured. Permission drift and an illegal tuple reached in the stored build and unreachable in the derived one. 28 legal edges out of 384, with S-to-M correctly refused. A latched peak transient age of 14 that a later short window did not reduce. Three distinct torn tuples from one lagging register. One snoop deferred and answered after the transition against one dropped. Three recoveries, two writebacks, and no loss — with the skip-settle build caught. Six accesses allowed, two needing a fetch, two an upgrade, and six blocked by a transition. 16% of a sampled line's life spent mid-transition. Thirteen legal moves through a full life with no undefined encoding exposed.

What would be different in production. The transition table would be a lookup rather than flat logic, and would carry twenty-plus states rather than eight. Each outstanding transaction would have its own state machine layered above the per-line state. The deferral queue would be sized and backpressured rather than single-entry. The permission gate would be pipelined, which reintroduces every window this chapter closed. None of that changes the invariants; all of it multiplies the places they can be violated.

The strongest argument against this design. Deriving permission from state rather than storing it puts a decode on the access path, and on a design where that path is already critical, storing the permission alongside the tag is the obvious optimisation. That argument is correct — and the measured consequence is that the two records can then disagree, so the drift monitor becomes mandatory rather than optional. The trade is a decode against a comparator plus a machine check, and which one wins is a timing question rather than an architectural one.

What would be built differently next time. The state field should have been four bits from the start. It was widened because a mutation proved the undefined-encoding monitor was dead code, but the design reason was already there: real state fields are wider than their state spaces, and a field sized exactly to its enumeration cannot represent the bug or detect it.

24. How This Appears In Real Engineering

In a microarchitecture review, the question that separates a specified design from an aspirational one is "where is the transition table." If the answer is "in the controller," the design has a state machine nobody can review. If the answer is a single table, it can be diffed against a specification and swept exhaustively before RTL exists.

In a coherency controller bring-up, the first counters to look at are n_entered minus n_completed and the latched max_age. Both detect transactions that were abandoned rather than merely slow, and both are silent in every other view of the system.

In a performance investigation, separating the three access denials is what turns "the cache is slow" into "we are paying for upgrades, not misses" — which points at data layout rather than at capacity, and those have completely different fixes.

In a verification plan review, an exhaustive sweep of the transition space is cheap at this size and is the only way to find an edge that exists and should not. Directed tests find missing edges; they cannot find extra ones, because nobody writes a test for a move they did not intend to implement.

In silicon debug, the difference between a dropped snoop and a slow one is invisible at the requester — both look like a timeout. The counter that separates them lives in the responder, costs almost nothing, and has to be designed in before tapeout because it cannot be inferred afterwards.

In a design review of somebody else's controller, ask what happens to a snoop that arrives mid-transition. The answer tells you immediately whether the transient states were designed or discovered.

25. Common Misconceptions

"MESI has four states." MESI has four stable states. A controller implementing it has those plus one transient per outstanding transaction type, and the transients are what push the state field past two bits.

"Transient states are an implementation detail." Measured at 16% of a sampled line's life, and six of sixteen accesses in the permission sweep were blocked by one. They are a sixth of the state space and the majority of the hard bugs.

"A state is a name." It is a tuple of permission, residence and duty. The name is shorthand for a combination of facts, and the encoding exists to make the other combinations unrepresentable.

"If the state value is legal, the line is in a legal state." Measured: three distinct torn tuples in which both the state field and the permission field held legal values and only their combination was impossible. A monitor on any single field reports a clean run.

"A snoop can be answered from the current state." Not during a transition. The current state is about to be wrong and the next one does not have the data. Deferral is the only correct move, and it needs storage.

"An unreachable monitor should be deleted." Unreachable is what an invariant looks like. Delete it and the condition it watches becomes undetectable in silicon. Prove it reachable with a fault-injection build instead — unless it is genuinely dead code, like a range check on a field that cannot hold an out-of-range value, in which case the fix is in the design.

"Recovery just invalidates everything." A line carrying a debt must settle it first. Measured: the build that skipped settling reached the invalidating phase with the debt outstanding, which is data loss dressed as error handling.

"A wider state field wastes bits." It is where undefined encodings become representable and detectable. A field sized exactly to its enumeration can neither hold the bug nor find it.

26. Interview Reasoning

27. Exercises

1. Calculation. A controller has 6 stable states and one transient per outstanding transaction type across 4 types. Compute the minimum state-field width, the width after padding to the next power of two, and the storage cost per 64-byte line as a percentage of tracked capacity.

2. Analysis. A design reports a transient occupancy of 16% at a 4-cycle fill latency. Estimate the occupancy at a 40-cycle CXL link latency under the same access pattern, state the assumption your estimate depends on, and name the measurement that would confirm or refute it.

3. RTL task. Extend transient_tracker to support two concurrent transactions for different lines. State what state that requires per transaction, and the failure that becomes possible if the two share one age counter.

4. Assertion task. Write the property proving the committed tuple is always legal. Then explain why it passes trivially on a design that derives permission from state, and what design change is required to make it a meaningful check.

5. Design task. Add a second transient for a read that finds the line being written by another agent. State which of the models in this chapter must change, which new edges appear in the graph, and what a snoop arriving in that state must do.

6. Testbench design. Design the stimulus that distinguishes a controller which refuses illegal moves from one that applies whatever it is asked. Explain why a directed test derived from the intended flows passes on both, and what the minimum stimulus is.

7. Debug task. A system shows n_entered rising steadily while n_completed tracks it exactly, and yet lines occasionally become permanently inaccessible. Give your investigation order and name the counter that distinguishes an abandoned transaction from a slow one.

8. Design review. A colleague proposes storing permission alongside the tag rather than decoding it from the state, arguing that it removes a decode from the critical path. Give the strongest version of that argument, then the monitor that becomes mandatory if it is accepted, and its cost.

28. Summary

A state is a tuple of facts, not a name.

• Four facts, one encoding. Permission, residence and duty are derived from the state, never stored beside it. The parameterised twin that stores them reached permission drift and an illegal tuple; the derived build cannot represent either.
• The graph is sparse. 28 legal edges out of 384 source-cause-destination combinations — 7.3%. S straight to M was correctly refused: acquiring write permission from a shared state requires invalidating the sharers, and that takes a transient.
• Most of the state space is transient. Measured at 16% of a sampled line's life, with six of sixteen permission-gate accesses blocked by a transition — more than by any permission problem.
• The peak must be latched. A transient age of 14 survived a later short window that a current-value counter would have reported as 2.
• A transition is one event with three effects. A duty register lagging by one commit produced three distinct torn tuples, at M, at O and at I, while every individual field held a legal value throughout.
• A snoop mid-flight is deferred, never dropped. The correct build answered 2 snoops and carried the requester identity across the gap; the build without a queue dropped 1 and reported nothing.
• Recovery settles before it invalidates. Three recoveries, 2 writebacks, zero loss — and the skip-settle build reached the invalidating phase with its debt outstanding and was caught.
• Three denials, three remedies. Fetch, upgrade, wait — measured at 2, 2 and 6. One merged signal tells an engineer that something failed and nothing about which cost is being paid.
• The state field is wider than the state space on purpose. That is where an undefined encoding becomes both representable and detectable; the trusting build landed outside the eight defined states and the monitor fired.
• Verification: 136 assertion sites, 86 of 86 mutations killed, zero surviving. Eleven first-run escapes were four stimulus gaps, two unobserved outputs, four unreachable checkers needing fault-injection hooks, one dead monitor fixed by widening the state field, and one provably equivalent mutation replaced rather than recorded.

Next: 13.5 Relationship to CHI, which takes this state space to a boundary: what happens when a CHI fabric's coherency domain meets a CXL link, and which of the guarantees in this module survive the crossing.