The CHI State Tables

Module 10 · Chapter 10.6 · Cache State Management

Project thread — 10.1–10.5 built the intuition. This chapter connects it to the spec's tables — the grids engineers actually read. 10.7 catalogues the classic state bugs.

1. Learning Outcomes

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

• Describe the layout of a CHI state-transition table — rows are states, columns are events.
• Read a cell as a state-and-action pair — the next state and the required actions.
• State that both halves of a cell are binding — the action is not optional.
• Recognize a blank cell as an event that cannot legally occur in that state.
• Diagnose the misread of applying a cell's next state but skipping its action.
• Implement a representative table lookup in SystemVerilog, Verilog-2001, and VHDL.

2. Why Should I Learn This?

Everything in this module lives, in the specification, inside a handful of dense tables — grids of states against events, with the behavior for each combination in the cell. When you implement or verify a cache, you do not work from prose; you work from these tables. Reading them fluently is the practical skill the whole module has been building toward.

And the tables are easy to misread in one specific way. A cell is not just "go to this state" — it is "go to this state and perform these actions": move this data, send this response. The state and the action are packaged together because they are inseparable — the transition is only correct if both happen. The frequent, expensive mistake is to read the next-state column and treat the action as decoration. Learning to read a cell as a pair — state and action, both binding — is what keeps an implementation faithful to the spec.

3. Key Terms

4. Previous Chapter Connection

Chapter 10.2 gave the transition graph; 10.3–10.5 added ownership, sharing, and dirty-data routing. All of that is what the spec's tables encode — but in a compressed, tabular form you must be able to read.

Each earlier chapter contributed one column or a few cells: the ReadUnique column, the SnpShared column, the WriteBack row. This chapter steps up to the whole grid and the discipline of reading any cell: find the row (current state) and column (event), and read the cell as a next state plus actions. The transitions of 10.2 were the state half; the data movements and responses of Modules 8 and 9 were the action half. The table puts them in one cell — and 10.6 is about never reading only half of it.

5. Core Concept — a cell is a state and an action, both binding

A CHI state table is a grid, and reading it correctly means reading each cell as two inseparable things.

• The layout. Rows are the line's current state (I, UC, UD, SC, SD); columns are events (each request opcode, each snoop). The cell at their intersection is the defined behavior.
• The cell has two halves. A cell specifies the next state the line moves to and the actions required — the data to move (forward, writeback), the response to send. Both are part of the cell.
• Both halves are binding. Applying the next state without the action — or the action without the state — is wrong. The transition is only correct if both happen together.
• Blank means illegal. A blank (or "not applicable") cell marks a (state, event) that cannot legally occur — an event that never arrives in that state. It is not "do nothing"; it is "cannot happen."

The synthesis:

A CHI state table is a grid of states against events, and every cell is a state-and-action pair: the next state and the required actions (data movement, response). Both halves are binding — reading the next state and skipping the action is a misread that loses data or drops a response. A blank cell marks a combination that cannot legally occur. Read every cell whole.

6. Engineering Mental Model — a recipe step, not just a destination

Think of each table cell as a step in a recipe, not just a signpost.

• A signpost would say only "you are now at the next stage." A recipe step says "move to the next stage and, while doing so, do this: whisk in the eggs, set the timer."
• If you read only the stage name and skip the instruction, you arrive at the right point in the recipe with the wrong contents — the eggs never went in.
• Each state-table cell is a recipe step: it names the next state and the action to perform on the way. Do both, in step, or the result is wrong even though the "stage" looks right.

Some steps are also marked "not applicable" — you would never be at that stage facing that ingredient. A blank cell is that: a step the recipe never reaches. The discipline is the same throughout: read the whole step, do the whole step.

7. Engineering Diagram — one row as transitions

Read each arrow as a cell: the arrowhead is the next state; the label names the action. From UD, SnpShared goes to SC with a writeback, SnpUnique goes to I forwarding the dirty data, eviction goes to I writing back. The state and the action are one cell — and the diagram shows only one row of the full grid.

8. Anatomy of a Cell

What every cell contains, and how to read it.

The rule to carry: a cell is read as all of its parts — next state, data action, response action — applied together. The next state alone is only a third of the cell. The two action parts are where the data movement (Module 9) and the response encoding (Chapter 9.3) live, and they are as binding as the state change. A blank cell is a fourth possibility: not an action, but an assertion that the combination is unreachable.

9. Reading a Cell Whole — state and action together

The discipline of reading both halves deserves its own statement.

• Locate the cell. Find the row (current state) and column (event); their intersection is the cell.
• Read the next state. The line will move to the state the cell names.
• Read the actions — always. The same cell demands data movement (forward/writeback) and a response. These are not optional annotations; they are half the cell.
• Apply both, together. The transition is the state change and the actions, performed as one step. Neither is complete without the other.

The point to carry:

A state table compresses the whole protocol into cells, and the compression only works if each cell is read as a complete instruction. The next state answers "where does the line end up?"; the actions answer "what must move and be said on the way?" — and coherence needs both answered. The tables pair them deliberately, because a state change without its action is exactly the class of bug that loses dirty data or drops a response: the line looks right (correct state) while a required transfer never happened. Fluency with the tables is the habit of never reading the state column alone.

10. Reading the Table — a worked cell

Read the cell at (state = UD, event = SnpUnique).

1. Locate. Row UD, column SnpUnique. Their intersection is one cell.
2. Next state. The cell says → I: the line is invalidated.
3. Data action. The cell also says forward the dirty data (SnpRespData) — UD holds the latest value, which must not be lost (Chapter 10.5).
4. Response action. And it says set PassDirty — hand off the writeback responsibility to the recipient (Chapter 9.3).
5. Apply together. The controller transitions UD → I, forwards the dirty data, and sends the response with PassDirty — all as one step.

Read only step 2 — "UD + SnpUnique → I" — and you invalidate the line but drop its dirty data: the state is right, the value is gone. The cell was steps 2–4 together, and that is the DebugLab.

11. RTL / Hardware View — a table lookup

A state-table cell is modeled as a lookup returning both the next state and the actions. Representative — the point is that the actions come out of the same lookup as the state.

// Representative state-table cell lookup (educational).
// A cell is a (next_state, data_action, resp_action) TRIPLE -- the state AND the
// actions come from ONE lookup and must ALL be applied. Skipping the action half
// (e.g., the forward/writeback) loses data even though the state is right.
module chi_table_lookup (
  input  logic [2:0] cur_state,    // I, UC, UD, SC, SD
  input  logic [2:0] event_in,     // e.g., SNP_UNIQUE, SNP_SHARED, EVICT
  output logic [2:0] next_state,   // the cell's next state
  output logic [1:0] data_action,  // 0 none, 1 forward, 2 writeback
  output logic       resp_passdirty,// the cell's response action (PassDirty)
  output logic       legal          // 0 = blank cell (cannot occur)
);
  localparam logic [2:0] I=3'd0, UC=3'd1, UD=3'd2, SC=3'd3, SD=3'd4;
  localparam logic [2:0] SNP_UNIQUE=3'd0, SNP_SHARED=3'd1, EVICT=3'd2, WRITE=3'd3;
  localparam logic [1:0] ACT_NONE=2'd0, ACT_FWD=2'd1, ACT_WB=2'd2;
 
  always_comb begin
    next_state = cur_state; data_action = ACT_NONE; resp_passdirty = 1'b0; legal = 1'b1;
    case (event_in)
      SNP_UNIQUE: begin
        next_state = I;
        // A DIRTY holder forwards its data and passes dirty; a clean holder just invalidates.
        if (cur_state==UD || cur_state==SD) begin data_action = ACT_FWD; resp_passdirty = 1'b1; end
        else if (cur_state==I) legal = 1'b0;   // blank: nothing to snoop
      end
      SNP_SHARED: begin
        next_state = SC;
        if (cur_state==UD || cur_state==SD) data_action = ACT_WB;   // writeback the dirty
        else if (cur_state==I) legal = 1'b0;
      end
      EVICT: begin
        next_state = I;
        if (cur_state==UD || cur_state==SD) data_action = ACT_WB;   // WriteBack dirty
        else if (cur_state==I) legal = 1'b0;
      end
      WRITE: begin
        if (cur_state==UC || cur_state==UD) next_state = UD;        // unique only
        else legal = 1'b0;                                          // blank: illegal from shared/I
      end
      default: legal = 1'b0;
    endcase
  end
endmodule

The same behavior in Verilog-2001:

// Representative state-table cell lookup (Verilog-2001).
module chi_table_lookup (
  input  [2:0] cur_state,
  input  [2:0] event_in,
  output reg [2:0] next_state,
  output reg [1:0] data_action,
  output reg       resp_passdirty,
  output reg       legal
);
  localparam I=3'd0, UC=3'd1, UD=3'd2, SC=3'd3, SD=3'd4;
  localparam SNP_UNIQUE=3'd0, SNP_SHARED=3'd1, EVICT=3'd2, WRITE=3'd3;
  localparam ACT_NONE=2'd0, ACT_FWD=2'd1, ACT_WB=2'd2;
 
  always @* begin
    next_state = cur_state; data_action = ACT_NONE; resp_passdirty = 1'b0; legal = 1'b1;
    case (event_in)
      SNP_UNIQUE: begin
        next_state = I;
        if (cur_state==UD || cur_state==SD) begin data_action = ACT_FWD; resp_passdirty = 1'b1; end
        else if (cur_state==I) legal = 1'b0;
      end
      SNP_SHARED: begin
        next_state = SC;
        if (cur_state==UD || cur_state==SD) data_action = ACT_WB;
        else if (cur_state==I) legal = 1'b0;
      end
      EVICT: begin
        next_state = I;
        if (cur_state==UD || cur_state==SD) data_action = ACT_WB;
        else if (cur_state==I) legal = 1'b0;
      end
      WRITE: begin
        if (cur_state==UC || cur_state==UD) next_state = UD;
        else legal = 1'b0;
      end
      default: legal = 1'b0;
    endcase
  end
endmodule

And in VHDL:

-- Representative state-table cell lookup (VHDL).
library ieee;
use ieee.std_logic_1164.all;
 
entity chi_table_lookup is
  port (
    cur_state      : in  std_logic_vector(2 downto 0);
    event_in       : in  std_logic_vector(2 downto 0);
    next_state     : out std_logic_vector(2 downto 0);
    data_action    : out std_logic_vector(1 downto 0);
    resp_passdirty : out std_logic;
    legal          : out std_logic
  );
end entity;
 
architecture rtl of chi_table_lookup is
  constant I  : std_logic_vector(2 downto 0) := "000";
  constant UC : std_logic_vector(2 downto 0) := "001";
  constant UD : std_logic_vector(2 downto 0) := "010";
  constant SC : std_logic_vector(2 downto 0) := "011";
  constant SD : std_logic_vector(2 downto 0) := "100";
  constant SNP_UNIQUE : std_logic_vector(2 downto 0) := "000";
  constant SNP_SHARED : std_logic_vector(2 downto 0) := "001";
  constant EVICT      : std_logic_vector(2 downto 0) := "010";
  constant WRITE      : std_logic_vector(2 downto 0) := "011";
  function dirty(s : std_logic_vector(2 downto 0)) return boolean is
  begin return (s = UD) or (s = SD); end function;
begin
  process (cur_state, event_in)
  begin
    next_state <= cur_state; data_action <= "00"; resp_passdirty <= '0'; legal <= '1';
    if event_in = SNP_UNIQUE then
      next_state <= I;
      if dirty(cur_state) then data_action <= "01"; resp_passdirty <= '1';
      elsif cur_state = I then legal <= '0'; end if;
    elsif event_in = SNP_SHARED then
      next_state <= SC;
      if dirty(cur_state) then data_action <= "10";
      elsif cur_state = I then legal <= '0'; end if;
    elsif event_in = EVICT then
      next_state <= I;
      if dirty(cur_state) then data_action <= "10";
      elsif cur_state = I then legal <= '0'; end if;
    elsif event_in = WRITE then
      if (cur_state = UC) or (cur_state = UD) then next_state <= UD;
      else legal <= '0'; end if;
    else
      legal <= '0';
    end if;
  end process;
end architecture;

All three return the next state and the actions from one lookup — a dirty holder's SnpUnique cell yields next=I, data_action=forward, resp_passdirty=1. A consumer that used only next_state would invalidate and drop the data — the DebugLab.

12. Verification View — the action travels with the state

The properties that keep a cell whole: a dirty holder's invalidating/downgrading cell carries a data action.

// Bind to chi_table_lookup.
// 1. A SnpUnique cell on a DIRTY holder must carry a forward action AND PassDirty.
property p_dirty_unique_forwards;
  @(*) (event_in == 3'd0 /*SNP_UNIQUE*/ && (cur_state==3'd2 || cur_state==3'd4))
       |-> (next_state==3'd0 /*I*/ && data_action==2'd1 /*FWD*/ && resp_passdirty);
endproperty
 
// 2. A SnpShared or evict cell on a dirty holder must carry a writeback action.
property p_dirty_clean_writes_back;
  @(*) ((event_in==3'd1 /*SNP_SHARED*/ || event_in==3'd2 /*EVICT*/)
        && (cur_state==3'd2 || cur_state==3'd4))
       |-> (data_action==2'd2 /*WB*/);
endproperty
 
// 3. A write from a shared/invalid state is a blank cell (illegal).
property p_write_illegal_from_shared;
  @(*) (event_in==3'd3 /*WRITE*/ && (cur_state==3'd3 || cur_state==3'd4 || cur_state==3'd0))
       |-> !legal;
endproperty

The system point, beyond the checks:

The state tables are the protocol's single source of truth, and their design encodes a lesson: state and action are the same decision. The specification never lists "go to Invalid" without, in the same cell, listing "and forward the dirty data" — because the transition is defined to include the action. So verifying an implementation against the tables is not checking states and actions separately; it is checking that each cell is applied as a unit. The most valuable properties are the ones that bind the action to the state — that a dirty invalidation always forwards, that a dirty downgrade always writes back — because those are exactly the couplings a hurried implementation breaks by reading the next-state column alone.

• What it proves: dirty holders' cells carry the required data and response actions; illegal cells are blank.
• What it does not prove: the actions are executed downstream — the consumer must apply them.
• Bug signature: a next state applied while its data_action / resp_passdirty is ignored.

13. Testbench — reading cells whole

Looks up representative cells and checks both the next state and the actions.

module tb_chi_table_lookup;
  logic [2:0] cur_state, event_in, next_state;
  logic [1:0] data_action;
  logic resp_passdirty, legal;
  int errors = 0;
  localparam I=3'd0, UC=3'd1, UD=3'd2, SC=3'd3, SD=3'd4;
  localparam SNP_UNIQUE=3'd0, SNP_SHARED=3'd1, EVICT=3'd2, WRITE=3'd3;
  localparam ACT_NONE=2'd0, ACT_FWD=2'd1, ACT_WB=2'd2;
 
  chi_table_lookup dut (.*);
 
  task automatic check(input logic [2:0] s, e, exp_ns, input logic [1:0] exp_da,
                       input logic exp_pd, exp_legal, input string name);
    cur_state = s; event_in = e; #1;
    if (next_state !== exp_ns || data_action !== exp_da ||
        resp_passdirty !== exp_pd || legal !== exp_legal) begin
      errors++; $display("FAIL %s: ns=%0d da=%0d pd=%0b legal=%0b",
                         name, next_state, data_action, resp_passdirty, legal);
    end else $display("PASS %s: ns=%0d da=%0d pd=%0b", name, next_state, data_action, resp_passdirty);
  endtask
 
  initial begin
    check(UD, SNP_UNIQUE, I,  ACT_FWD, 1'b1, 1'b1, "UD + SnpUnique -> I, forward, PassDirty");
    check(SC, SNP_UNIQUE, I,  ACT_NONE,1'b0, 1'b1, "SC + SnpUnique -> I, no data");
    check(UD, SNP_SHARED, SC, ACT_WB,  1'b0, 1'b1, "UD + SnpShared -> SC, writeback");
    check(UD, EVICT,      I,  ACT_WB,  1'b0, 1'b1, "UD + evict     -> I, writeback");
    check(SC, WRITE,      SC, ACT_NONE,1'b0, 1'b0, "SC + write     -> BLANK (illegal)");
 
    if (errors == 0) $display("ALL TESTS PASSED");
    else             $display("%0d FAILURE(S)", errors);
    $finish;
  end
endmodule

Expected output:

PASS UD + SnpUnique -> I, forward, PassDirty: ns=0 da=1 pd=1
PASS SC + SnpUnique -> I, no data: ns=0 da=0 pd=0
PASS UD + SnpShared -> SC, writeback: ns=3 da=2 pd=0
PASS UD + evict     -> I, writeback: ns=0 da=2 pd=0
PASS SC + write     -> BLANK (illegal): ns=3 da=0 pd=0
ALL TESTS PASSED

14. DebugLab — reading the next state but skipping the action

cell (UD, SnpUnique): next_state = I, data_action = FORWARD, resp = PassDirty
implementation applied: next_state = I   <-- state only
                        data_action ignored (no forward)
                        resp_passdirty ignored (no PassDirty)
result: line -> I (correct state), dirty data NOT forwarded -> lost
        recipient not told of dirty -> installs clean -> stale later

15. Common Mistakes

• Reading the next state only. Assumption: the action is a note. Bug: data lost, response dropped (the DebugLab). Prevention: apply the whole cell.
• Treating a blank cell as "do nothing." Assumption: blank means no-op. Bug: an illegal event handled wrongly. Prevention: blank means cannot occur.
• Confusing rows and columns. Assumption: any orientation. Bug: reading the wrong cell. Prevention: rows are states, columns are events.
• Applying the action without the state. Assumption: the action is enough. Bug: wrong state. Prevention: both halves together.
• Ignoring the response action. Assumption: only data matters. Bug: the home is misinformed. Prevention: send the cell's response.
• Reading prose instead of the table. Assumption: prose is complete. Bug: missed cases. Prevention: the table is the source of truth.

16. Engineering Checklist

• Read the table by row (state) and column (event) to the cell.
• Read each cell as a state-and-action pair — both halves.
• Apply the next state and the actions (data movement, response) together.
• Treat a blank cell as a combination that cannot occur.
• Never apply a transition without its actions.
• Verify implementations cell-by-cell — state and action bound.

17. Key Takeaways

• The CHI spec encodes behavior in state tables — rows are states, columns are events.
• Every cell is a state-and-action pair: the next state and the required actions.
• Both halves are binding — the data movement and response are not optional.
• A blank cell marks an event that cannot legally occur in that state.
• Reading the next state but skipping the action loses dirty data and drops responses.
• Read every cell whole; state and action together; the model here is representative.

18. Quick Revision

The CHI state tables. The specification encodes cache behavior in state-transition tables: rows are the current state (I, UC, UD, SC, SD), columns are events (each request and snoop), and the cell at their intersection is the defined behavior. The skill is reading a cell as a state-and-action pair — it specifies the next state the line moves to and the actions required: the data to move (forward, writeback) and the response to send (SnpResp, PassDirty). Both halves are binding; the transition is only correct if both happen together. A blank cell marks a (state, event) that cannot legally occur. The classic misread is to take the next-state column and skip the action — for example applying (UD, SnpUnique) → I but not forwarding the dirty data or setting PassDirty — which leaves the state right while the latest value is lost and the recipient misinformed. Read every cell whole: next state and actions, as one step. Representative model; 10.7 catalogues the classic state-machine bugs.

Coming Next

Chapter 10.7 — Common State Bugs. This module built the states, transitions, and tables; the last chapter turns them on their head to study how they break. Chapter 10.7 catalogues the classic CHI cache-state bugs — the recurring mistakes in real implementations: illegal transitions, lost dirty data, stale sharers, ownership drift, and the half-read cells of this chapter — as a checklist of what to look for when a coherence state machine misbehaves. It is the module's closing synthesis, framed as the bugs you will actually hunt.