Snoop-Driven Invalidation

Module 9 · Chapter 9.4 · Snoop Flows

Project thread — 9.3 read the response's fields. This chapter follows one outcome — invalidation — and its timing rule. 9.5 turns to cache-to-cache data transfer via snoop.

1. Learning Outcomes

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

• Describe how a snoop forces a holder to Invalid — the steps the snooped cache performs.
• Explain why invalidation is the mechanism that makes a single writer possible.
• State the timing rule: the writer must wait for every holder to confirm invalidation.
• Trace how the home gates completion on collecting all invalidation confirmations.
• Diagnose the stale-read window when a write proceeds before invalidation is confirmed.
• Implement a representative invalidation-confirmation gate in SystemVerilog, Verilog-2001, and VHDL.

2. Why Should I Learn This?

Invalidation is the outcome behind every write. Before a core can modify a shared line, every other copy must be gone — and a snoop is what makes them go. You have seen the snoop types that invalidate (SnpUnique, SnpCleanInvalid, SnpMakeInvalid); this chapter is about the invalidation itself: what the snooped cache actually does, and — the part that trips designs up — when the writer is allowed to trust that it is done.

The subtlety is timing. Invalidation takes cycles: the holder must stop serving the line and transition its state, then say so. If the writer begins before that confirmation arrives, there is a window where a stale copy still exists and can be read — a coherence violation created not by a wrong action but by a premature one. Understanding invalidation means understanding the handshake that closes that window: confirm, then proceed.

3. Key Terms

4. Previous Chapter Connection

Chapter 9.2 named the invalidating snoops; Chapter 9.3 showed the response reports the holder's final state. This chapter connects them into a sequence with timing: the snoop goes out, the holder invalidates, the holder confirms with a response reporting I, and only when all such confirmations are in does the requester's transaction complete.

So invalidation is not a single event but a round trip per holder, and the home must collect them all. The single-writer state ReadUnique and MakeUnique promised (Chapters 8.2, 8.8) is only real once every holder has confirmed. This chapter is where "invalidate the others" becomes "invalidate the others and wait until they say they did."

5. Core Concept — invalidate, confirm, then let the writer proceed

A snoop-driven invalidation is a per-holder round trip, and the writer proceeds only after every round trip completes.

• The snoop forces I. The home sends an invalidating snoop (SnpUnique / SnpCleanInvalid / SnpMakeInvalid). The holder must stop serving the line and transition it to Invalid.
• The holder confirms. The holder returns a response reporting state I (SnpResp, or SnpRespData if it also returned dirty data). This confirmation is the home's proof the copy is gone.
• The home collects all confirmations. With several holders, the home issues several snoops and waits for every one to confirm I before it considers the line clear of other copies.
• Only then, complete. The home sends the requester's completion (CompData / Comp) only after all invalidations are confirmed. The requester writes only after completion — so no stale copy exists when it does.

The synthesis:

Snoop-driven invalidation forces each holder to I and makes it confirm. The single-writer state is real only when every holder has confirmed, so the home gates the requester's completion on collecting all confirmations. Invalidate, confirm, then complete — the write proceeds after the last confirmation, never before, so no stale copy can be read while it happens.

6. Engineering Mental Model — everyone must confirm before you edit

You want to edit the shared document, and three colleagues each hold a copy.

• You ask the coordinator (home) to make you the sole editor. The coordinator tells each colleague to destroy their copy (the invalidating snoops).
• Each colleague, once done, texts back "done" (the confirmation). Until then, they might still be reading their copy.
• The coordinator waits for all three "done" texts. Only when the last one arrives does it tell you "you're clear to edit" (completion).
• If the coordinator told you "go ahead" after only two texts, the third colleague could still be reading their old copy while you rewrite — they would act on stale content.

The discipline is simple and strict: collect every confirmation before granting the edit. One missing "done" is one colleague still holding a copy — and one stale read waiting to happen.

7. Engineering Diagram — waiting for every confirmation

Read the last message's timing: CompData waits for both SnpResp confirmations. Send it after one, and the other sharer is still valid when RN0 writes — a stale copy in the wild. The gate is the point.

8. What the Snooped Cache Does to Invalidate

Invalidation is a small sequence inside the holder, not a single instant.

The rule to carry: the holder is not invalidated until it has transitioned to I and said so. The confirmation is what the home can act on; the internal transition alone is invisible to everyone else. So "invalidated" means confirmed invalidated — and until the response reporting I arrives, the home must treat the holder as still holding the line.

9. Confirm Before Proceed — the completion gate

The timing rule deserves its own statement, because it is where invalidation becomes correct.

• A copy exists until confirmed gone. Between the snoop being sent and the confirmation arriving, the holder still has the line and could serve it.
• So completion must wait. The home withholds the requester's completion until every outstanding invalidation has confirmed I. The requester writes only after completion.
• All, not some. With N holders, all N confirmations are required. Completing after N−1 leaves one live copy — enough to break coherence.
• This is the single-writer guarantee in practice. "Single writer" is not established by issuing the snoops but by collecting their confirmations. The gate is what turns intent into invariant.

The point to carry:

Invalidation has a duration, and coherence lives in respecting it. The single-writer invariant is a statement about a moment — when the write happens, no other copy exists — and the only way to guarantee that moment is to not let the write happen until every holder has confirmed its copy is gone. The completion gate is that guarantee: it converts a set of in-flight invalidations into the single fact the writer needs — they are all done. Issuing snoops starts the process; collecting confirmations finishes it, and only then is it safe to proceed.

10. Walkthrough — ReadUnique invalidating two sharers

RN0 issues ReadUnique; RN1 and RN2 both hold the line in SC.

1. REQ. RN0 asks for unique ownership to write.
2. Snoop both. The directory shows two sharers, so HN sends SnpUnique to both RN1 and RN2. Two invalidations are now outstanding.
3. RN1 confirms. RN1 stops serving the line, transitions SC → I, and returns SnpResp reporting I. One confirmation in; one still outstanding.
4. Home waits. HN does not complete yet — RN2 has not confirmed, so a valid copy may still exist at RN2.
5. RN2 confirms. RN2 transitions SC → I and returns SnpResp reporting I. Now all confirmations are in.
6. Complete. HN returns CompData to RN0. RN0 installs the line UC, becomes the single writer, and may write.

The line was clear of other copies only at step 5. Completing at step 3 — after one confirmation — would let RN0 write while RN2 still held and could read the line. The gate at step 4 is what prevents it.

11. RTL / Hardware View — an invalidation-confirmation gate

The home's core mechanism is a counter: load the number of holders to invalidate, decrement on each confirmation, and allow completion only when the count reaches zero. Representative and sequential.

// Representative invalidation-confirmation gate (educational).
// On start, load the number of holders that must invalidate. Each confirmation
// (a snoop response reporting Invalid) decrements the count. The requester's
// transaction may complete ONLY when all confirmations are in (remaining == 0).
module chi_inval_gate #(parameter W = 4) (
  input  logic         clk, rst_n,
  input  logic         start,        // begin the invalidation phase
  input  logic [W-1:0] expected,     // number of holders to invalidate
  input  logic         resp_inv,     // a holder confirmed Invalid this cycle
  output logic [W-1:0] remaining,    // invalidations still outstanding
  output logic         can_complete  // all confirmed -> home may send completion
);
  logic         busy;
  logic [W-1:0] rem_q;
 
  assign remaining    = rem_q;
  // Completion is allowed only once every invalidation has confirmed.
  assign can_complete = busy && (rem_q == '0);
 
  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      busy  <= 1'b0;
      rem_q <= '0;
    end else if (start) begin
      busy  <= 1'b1;
      rem_q <= expected;                       // load outstanding count
    end else if (busy && resp_inv && rem_q != '0) begin
      rem_q <= rem_q - 1'b1;                    // one more holder confirmed I
    end
  end
endmodule

The same behavior in Verilog-2001:

// Representative invalidation-confirmation gate (Verilog-2001).
module chi_inval_gate #(parameter W = 4) (
  input  clk, rst_n, start, resp_inv,
  input  [W-1:0] expected,
  output [W-1:0] remaining,
  output can_complete
);
  reg busy;
  reg [W-1:0] rem_q;
 
  assign remaining    = rem_q;
  assign can_complete = busy && (rem_q == {W{1'b0}});
 
  always @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      busy  <= 1'b0;
      rem_q <= {W{1'b0}};
    end else if (start) begin
      busy  <= 1'b1;
      rem_q <= expected;
    end else if (busy && resp_inv && rem_q != {W{1'b0}}) begin
      rem_q <= rem_q - 1'b1;
    end
  end
endmodule

And in VHDL:

-- Representative invalidation-confirmation gate (VHDL).
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
 
entity chi_inval_gate is
  generic ( W : integer := 4 );
  port (
    clk, rst_n   : in  std_logic;
    start        : in  std_logic;
    expected     : in  unsigned(W-1 downto 0);
    resp_inv     : in  std_logic;
    remaining    : out unsigned(W-1 downto 0);
    can_complete : out std_logic
  );
end entity;
 
architecture rtl of chi_inval_gate is
  signal busy  : std_logic := '0';
  signal rem_q : unsigned(W-1 downto 0) := (others => '0');
begin
  remaining    <= rem_q;
  can_complete <= '1' when (busy = '1' and rem_q = 0) else '0';
 
  process (clk, rst_n)
  begin
    if rst_n = '0' then
      busy  <= '0';
      rem_q <= (others => '0');
    elsif rising_edge(clk) then
      if start = '1' then
        busy  <= '1';
        rem_q <= expected;
      elsif busy = '1' and resp_inv = '1' and rem_q /= 0 then
        rem_q <= rem_q - 1;
      end if;
    end if;
  end process;
end architecture;

All three withhold can_complete until remaining reaches zero — every holder confirmed. The requester's completion is gated on this signal, so it never writes with a live copy outstanding. The DebugLab shows the coherence break when completion ignores the gate.

12. Verification View — no completion until all confirm

The property that keeps invalidation safe: completion is impossible while any invalidation is outstanding.

// Bind to chi_inval_gate.
// 1. Completion is never allowed while invalidations remain outstanding.
property p_no_complete_while_pending;
  @(posedge clk) disable iff (!rst_n)
    (remaining != '0) |-> !can_complete;
endproperty
 
// 2. Completion implies every invalidation has confirmed (remaining == 0).
property p_complete_needs_all;
  @(posedge clk) disable iff (!rst_n)
    can_complete |-> (remaining == '0);
endproperty

The system point, beyond the checks:

The gate turns a distributed fact — "no cache holds this line" — into a local signal the requester can act on. That fact cannot be observed directly; it can only be assembled from each holder's confirmation, and it is true only once the last one arrives. So the counter is not bookkeeping, it is the materialization of the single-writer invariant: remaining == 0 is the precise moment the line is clear, and gating completion on it is the only way to ensure the write lands in that moment. Anything that lets the write proceed with remaining > 0 is asserting a fact that is not yet true.

• What it proves: completion requires all confirmations; none while any remain.
• What it does not prove: each holder actually reached I — that is the holder's response correctness (Chapter 9.3).
• Bug signature: completion asserted with remaining > 0 — a write proceeding past a live copy.

13. Testbench — completion waits for every confirmation

Loads two holders, confirms them one at a time, and checks completion is withheld until both are in.

module tb_chi_inval_gate;
  localparam W = 4;
  logic clk = 0, rst_n = 0, start = 0, resp_inv = 0;
  logic [W-1:0] expected = '0, remaining;
  logic can_complete;
  int errors = 0;
 
  chi_inval_gate #(.W(W)) dut (.*);
  always #5 clk = ~clk;
 
  initial begin
    @(posedge clk) rst_n = 1;
 
    // Two holders must invalidate.
    @(posedge clk) begin start = 1; expected = 4'd2; end
    @(posedge clk) start = 0;
    if (can_complete) begin errors++; $display("FAIL complete with 2 pending"); end
    else $display("PASS not complete: 2 pending");
 
    // First confirmation.
    @(posedge clk) resp_inv = 1;
    @(posedge clk) resp_inv = 0;
    if (can_complete) begin errors++; $display("FAIL complete with 1 pending"); end
    else $display("PASS not complete: 1 pending");
 
    // Second confirmation -> now complete.
    @(posedge clk) resp_inv = 1;
    @(posedge clk) resp_inv = 0;
    if (!can_complete) begin errors++; $display("FAIL not complete after all confirmed"); end
    else $display("PASS complete after both confirmed");
 
    if (errors == 0) $display("ALL TESTS PASSED");
    else             $display("%0d FAILURE(S)", errors);
    $finish;
  end
endmodule

Expected output:

PASS not complete: 2 pending
PASS not complete: 1 pending
PASS complete after both confirmed
ALL TESTS PASSED

14. DebugLab — completing before invalidation is confirmed

RN0 ReadUnique; RN1 = SC, RN2 = SC (two sharers)
HN SnpUnique -> RN1 and RN2
RN1 confirms I; RN2 has NOT confirmed yet (still SC)
HN sends CompData to RN0 anyway  <-- premature: 1 invalidation outstanding
RN0 installs UC and writes L = NEW
  meanwhile RN2 still SC(OLD) -> RN2 reads L -> OLD   (stale!)
RN2 confirms I a few cycles later -> too late

15. Common Mistakes

• Completing before all confirm. Assumption: issuing snoops is enough. Bug: stale-read window (the DebugLab). Prevention: gate completion on every confirmation.
• Treating "invalidated" as instant. Assumption: the transition is immediate. Bug: acting during the window. Prevention: invalidated means confirmed-invalidated.
• Counting some, not all, holders. Assumption: a subset suffices. Bug: a surviving copy. Prevention: collect confirmations from every holder.
• Ignoring in-flight local access. Assumption: the holder is idle. Bug: a local read/write races the snoop. Prevention: reconcile in-flight accesses on invalidation.
• Dropping dirty data on invalidation. Assumption: invalidation discards. Bug: lost dirty data. Prevention: return it with PassDirty (Chapter 9.3).
• No timeout on outstanding snoops. Assumption: confirmations always arrive. Bug: a hang. Prevention: track and bound outstanding invalidations.

16. Engineering Checklist

• Force each holder to Invalid with an invalidating snoop.
• Have each holder stop serving the line and confirm I in its response.
• Count the holders to invalidate; collect every confirmation.
• Gate completion on remaining == 0 — never complete with an outstanding invalidation.
• Return dirty data (with PassDirty) as part of an invalidating snoop when applicable.
• Let the requester write only after completion — never during the window.

17. Key Takeaways

• Invalidation forces a holder to Invalid and is the mechanism that makes a single writer possible.
• It is a per-holder round trip: the holder stops serving, transitions to I, and confirms.
• "Invalidated" means confirmed invalidated — the internal transition alone is invisible to the home.
• The home gates the requester's completion on collecting all invalidation confirmations.
• Completing early opens a stale-read window where a live copy can serve old data — a coherence violation.
• Confirm every holder, then complete; the model here is representative.

18. Quick Revision

Snoop-driven invalidation. A snoop forces a holder to Invalid, and that invalidation is the mechanism that makes a single writer possible. But it is a per-holder round trip with duration: the snooped cache must stop serving the line, transition to I, return any dirty data (with PassDirty), and confirm by reporting I in its response. The rule that makes it correct is timing — the home gates the requester's completion on collecting every invalidation confirmation. "Single writer" is established not by issuing the snoops but by collecting their confirmations: only when the last holder reports I is the line clear of other copies. Complete before all confirm — send the completion with an invalidation still outstanding — and the requester writes while a holder is still valid, opening a stale-read window where the old value can be served: a coherence violation from a premature completion, not a wrong action. Count the holders, collect every confirmation, gate completion on remaining == 0. Representative model; 9.5 covers cache-to-cache data transfer via snoop.

Coming Next

Chapter 9.5 — Snoop Data Transfer. Invalidation cleared the other copies; now follow the data. Chapter 9.5 covers cache-to-cache transfer via the snoop response — how a snooped cache's data reaches the requester directly, without a trip to memory, when a holder has the line the requester needs. It builds on the SnpRespData you have seen to show the performance win of sourcing data from a peer cache, and the coherence care that direct transfer requires.