Invalidations

Module 2 · Chapter 2.7 · Coherency Protocol Foundations

Project thread — 2.6 said a dirty line must be rescued before it is lost. Invalidation is the event that most often forces that: a peer's write. This chapter is the mechanism; 2.8 asks how the Home Node decides whom to invalidate — broadcast or directory.

1. Learning Outcomes

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

• Explain why a write to a shared line requires invalidating every other copy first.
• Trace the request → snoop-invalidate → acknowledge → grant flow through the CHI cast.
• Identify why the write must wait for all acknowledgements, and what breaks if it does not.
• Distinguish invalidating a clean copy (drop) from a dirty copy (rescue its data first).
• Implement a representative invalidate-acknowledgement tracker in SystemVerilog, Verilog-2001, and VHDL.
• Verify that the write is granted only after every sharer has acknowledged.

2. Why Should I Learn This?

Invalidation is where the single-writer rule is enforced, cycle by cycle. Every coherent store to shared data triggers one: the writer cannot proceed until the fabric has torn down the other copies. Get its timing wrong — proceed one ack early — and two cores momentarily disagree, which is the whole class of "works until two threads hammer the same line" bugs.

It is also the most common trigger for the writeback of 2.6: a peer's write invalidates your dirty line, so the invalidation must rescue that data on the way out. Invalidations tie ownership, dirty data, and serialization together into one handshake.

3. Key Terms

4. Previous Chapter Connection

Chapter 2.5 named the single owner; 2.6 made its writeback obligation concrete. Both assumed a line could reach a single-owner state — but how does a writer displace the other copies? By invalidating them.

Invalidation is the operational side of "single writer." When a core wants to write a line others share, the Home Node must remove every peer copy before granting the write. And because one of those copies might be dirty (2.6), the invalidation is also where that dirty data is rescued. This chapter is the handshake that makes SWMR happen.

5. Core Concept — remove the copies, then write

To become the single writer of a line, a core must ensure no other readable copy exists. The steps:

1. Request. The writer asks the Home Node for exclusive (unique) access to the line.
2. Snoop-invalidate. The HN, knowing who holds the line, sends each sharer a snoop-invalidate.
3. Acknowledge. Each sharer drops its copy (state → Invalid) and replies. A dirty sharer also returns its data — the invalidation rescues it before the copy vanishes.
4. Grant. Once every ack is in, the HN grants the writer exclusive access. Now it is the sole owner and may write.

The gating rule:

The write waits for every acknowledgement. The grant is issued only after all sharers have confirmed invalidation. If the write proceeded earlier, a stale sharer could still read the old value — two cores disagreeing on one address, exactly the failure coherency forbids.

A clean copy is invalidated by simply dropping it. A dirty copy cannot be dropped (2.6) — its data is returned in the ack, either to the requester (for a read-unique) or to memory. Invalidation and writeback are two halves of the same event.

6. Engineering Mental Model — recalling every library copy

A core that wants to rewrite a shared document must first make sure no outstanding copy survives.

• It asks the librarian (Home Node), who knows exactly who checked out copies.
• The librarian sends each borrower a recall (snoop-invalidate): return or destroy your copy.
• Each borrower confirms — and if their copy had hand-written notes (dirty), they send those notes back so nothing is lost.
• Only when every borrower has confirmed does the librarian hand the writer the exclusive master to edit.

If the writer started editing while one borrower still had a copy, two versions would exist — which is exactly what the recall exists to prevent.

7. Engineering Diagram — the invalidation handshake

Time flows down: the grant (last arrow) is drawn strictly below the acknowledgement (third arrow) because it must happen after it. That vertical order is the correctness property.

8. Worked Example — one sharer, then several

CPU0 wants to write line A. Compare the invalidation cost with one and with several sharers.

The pattern: the writer's latency is set by the slowest sharer to acknowledge, and the write cannot complete until the last one does. One sharer or many, the rule is identical — all copies gone before the write proceeds. (How the HN finds the sharers to snoop — broadcast to everyone, or a directory targeting only the three that hold it — is Chapter 2.8.)

9. Transaction Walkthrough — request to grant

Trace CPU0's write of a line CPU1 holds dirty, step by step. Representative behavioral flow, not a byte-level trace.

1. CPU0 → RN0 → Home Node: request unique. The store misses write permission; RN0 asks the HN for exclusive access to A. Stall risk: none yet. Tracking updated: the HN opens a transaction for A.
2. HN directory lookup. The HN finds CPU1 holds A (dirty). Event: it must invalidate CPU1 and collect its data. It records how many acks to expect (here, one).
3. HN → RN1: snoop-invalidate A. Purpose: remove CPU1's copy. Sender HN, receiver RN1. Stall risk: the grant now waits on RN1's ack.
4. RN1 invalidates and acks (+ data). CPU1's line goes to Invalid; because it was dirty, the ack carries the newest data (rescued, per 2.6). RN1 → HN.
5. HN → RN0: grant unique + data. With the (only) ack in and pending count at zero, the HN grants CPU0 exclusive access and forwards the rescued data. Completion: CPU0 is now the sole owner (M) and writes.

Two events had to align: all invalidations acknowledged (Invariant 1 — single writer), and the write ordered at the HN (Invariant 2). The grant is where both are satisfied at once.

10. RTL / Hardware View — an invalidate-acknowledgement tracker

A representative tracker for the gating rule: it counts outstanding invalidate acknowledgements and grants the write only when the count reaches zero. This is the forward-progress logic on the Home Node / requester side. Behavioral and simplified: one ack per cycle, one transaction, no data path.

// Representative invalidate-acknowledgement tracker (educational, not a full
// Home Node). Gates the write grant on all sharers acknowledging invalidation.
module invalidate_ack_tracker #(
  parameter int CW = 4                 // pending-count width (max sharers = 2^CW-1)
)(
  input  logic          clk,
  input  logic          rst_n,
  input  logic          inv_start,     // begin: snoop-invalidate all sharers
  input  logic [CW-1:0] inv_count,     // number of sharers to invalidate
  input  logic          inv_ack,       // one sharer acknowledged this cycle
  output logic [CW-1:0] pending,       // acks still outstanding
  output logic          inv_busy,      // invalidation in progress
  output logic          inv_grant      // pulse: all acks in, the write may proceed
);
  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      pending   <= '0;
      inv_busy  <= 1'b0;
      inv_grant <= 1'b0;
    end else begin
      inv_grant <= 1'b0;                       // default: no grant this cycle
      if (inv_start) begin
        if (inv_count == '0) begin
          inv_grant <= 1'b1;                    // no sharers -> immediate grant
          inv_busy  <= 1'b0;
        end else begin
          pending  <= inv_count;               // wait for this many acks
          inv_busy <= 1'b1;
        end
      end else if (inv_busy && inv_ack) begin
        if (pending == 1) begin
          pending   <= '0;
          inv_busy  <= 1'b0;
          inv_grant <= 1'b1;                    // last ack -> grant now
        end else begin
          pending <= pending - 1'b1;
        end
      end
    end
  end
endmodule

The same behavior in Verilog-2001:

// Representative invalidate-acknowledgement tracker (Verilog-2001).
module invalidate_ack_tracker #(
  parameter CW = 4
)(
  input               clk,
  input               rst_n,
  input               inv_start,
  input  [CW-1:0]     inv_count,
  input               inv_ack,
  output reg [CW-1:0] pending,
  output reg          inv_busy,
  output reg          inv_grant
);
  always @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      pending <= {CW{1'b0}}; inv_busy <= 1'b0; inv_grant <= 1'b0;
    end else begin
      inv_grant <= 1'b0;
      if (inv_start) begin
        if (inv_count == {CW{1'b0}}) begin
          inv_grant <= 1'b1; inv_busy <= 1'b0;      // no sharers
        end else begin
          pending <= inv_count; inv_busy <= 1'b1;
        end
      end else if (inv_busy && inv_ack) begin
        if (pending == 1) begin
          pending <= {CW{1'b0}}; inv_busy <= 1'b0; inv_grant <= 1'b1;
        end else begin
          pending <= pending - 1'b1;
        end
      end
    end
  end
endmodule

And in VHDL:

-- Representative invalidate-acknowledgement tracker (VHDL).
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
 
entity invalidate_ack_tracker is
  generic ( CW : integer := 4 );
  port (
    clk, rst_n : in  std_logic;
    inv_start  : in  std_logic;
    inv_count  : in  std_logic_vector(CW-1 downto 0);
    inv_ack    : in  std_logic;
    pending    : out std_logic_vector(CW-1 downto 0);
    inv_busy   : out std_logic;
    inv_grant  : out std_logic
  );
end entity;
 
architecture rtl of invalidate_ack_tracker is
  signal cnt   : unsigned(CW-1 downto 0) := (others => '0');
  signal busy  : std_logic := '0';
  signal grant : std_logic := '0';
begin
  process(clk, rst_n)
  begin
    if rst_n = '0' then
      cnt <= (others => '0'); busy <= '0'; grant <= '0';
    elsif rising_edge(clk) then
      grant <= '0';
      if inv_start = '1' then
        if unsigned(inv_count) = 0 then
          grant <= '1'; busy <= '0';                 -- no sharers
        else
          cnt <= unsigned(inv_count); busy <= '1';
        end if;
      elsif busy = '1' and inv_ack = '1' then
        if cnt = 1 then
          cnt <= (others => '0'); busy <= '0'; grant <= '1';
        else
          cnt <= cnt - 1;
        end if;
      end if;
    end if;
  end process;
 
  pending   <= std_logic_vector(cnt);
  inv_busy  <= busy;
  inv_grant <= grant;
end architecture;

All three model the identical rule: load the sharer count, decrement on each ack, and grant only when the count reaches zero.

11. Timing View — the write waits for the ack

CPU0 stores line A while CPU1 shares it. Watch the Home Node send the invalidate, CPU1 drop its copy and acknowledge, and CPU0 gain M only afterward. Timing is representative — real latencies are not fixed cycle counts.

Read the ordering straight off: A@CPU0 becomes M at t4, one cycle after inv_ack at t3. The grant never precedes the acknowledgement — that gap is the single-writer guarantee in time.

12. Verification View — no grant before every ack

Three properties enforce the gating rule.

// Bind to invalidate_ack_tracker.
// 1. The grant is never issued while acks are still outstanding.
property p_no_early_grant;
  @(posedge clk) disable iff (!rst_n) (inv_busy && (pending != 0)) |-> !inv_grant;
endproperty
assert property (p_no_early_grant);
 
// 2. A grant means the pending count is zero (all sharers acknowledged).
property p_grant_means_done;
  @(posedge clk) disable iff (!rst_n) inv_grant |-> (pending == 0);
endproperty
assert property (p_grant_means_done);
 
// 3. Once busy, only an ack decreases the pending count (no spontaneous drop).
property p_ack_decrements;
  @(posedge clk) disable iff (!rst_n)
    (inv_busy && !inv_ack && !inv_start) |=> $stable(pending);
endproperty
assert property (p_ack_decrements);

The system invariant is a scoreboard rule:

The write to a line is granted only after the number of invalidate acks equals the number of sharers that held it. A grant with any sharer still valid is a single-writer violation.

• What it proves: the write waits for full invalidation — no core can read the old value once the writer proceeds.
• What it does not prove: that a dropped ack is ever recovered (a lost ack hangs the transaction — a liveness concern handled by protocol-level timeout/retry), nor that dirty data was correctly rescued (2.6), nor cross-line ordering (Module 12).
• Bug signature when it fails: inv_grant asserted while pending != 0 — the writer proceeded with a live sharer, so a stale read or a second writer follows.

13. Testbench — grant only after the last ack

Deterministic stimulus; the grant pulse is sampled each cycle — no sampling race.

module tb_invalidate_ack_tracker;
  logic clk = 0, rst_n;
  logic inv_start, inv_ack;
  logic [3:0] inv_count, pending;
  logic inv_busy, inv_grant;
  int errors = 0;
 
  invalidate_ack_tracker #(.CW(4)) dut (.*);
  always #5 clk = ~clk;
 
  task automatic step(input logic st, ak, input logic [3:0] cnt,
                      input logic exp_busy, exp_grant, input logic [3:0] exp_pend,
                      input string tag);
    inv_start = st; inv_ack = ak; inv_count = cnt;
    @(posedge clk); #1;
    inv_start = 0; inv_ack = 0; inv_count = 0;
    if (inv_busy !== exp_busy || inv_grant !== exp_grant || pending !== exp_pend) begin
      errors++;
      $display("FAIL [%s] busy/grant/pending = %b/%b/%0d (exp %b/%b/%0d)",
               tag, inv_busy, inv_grant, pending, exp_busy, exp_grant, exp_pend);
    end else
      $display("PASS [%s] busy=%b grant=%b pending=%0d", tag, inv_busy, inv_grant, pending);
  endtask
 
  initial begin
    rst_n = 0; step(0,0,4'd0, 0,0,4'd0, "reset"); rst_n = 1;
    // Three sharers: start, then three acks -> grant on the third.
    step(1,0,4'd3, 1,0,4'd3, "start: 3 sharers");
    step(0,1,4'd0, 1,0,4'd2, "ack 1 -> pending 2");
    step(0,1,4'd0, 1,0,4'd1, "ack 2 -> pending 1");
    step(0,1,4'd0, 0,1,4'd0, "ack 3 -> GRANT");
    if (inv_busy) begin errors++; $display("FAIL: busy after grant"); end
    // No-sharer case: immediate grant.
    step(1,0,4'd0, 0,1,4'd0, "start: 0 sharers -> immediate grant");
 
    if (errors == 0) $display("ALL TESTS PASSED");
    else             $display("%0d FAILURE(S)", errors);
    $finish;
  end
endmodule

Expected output:

PASS [reset] busy=0 grant=0 pending=0
PASS [start: 3 sharers] busy=1 grant=0 pending=3
PASS [ack 1 -> pending 2] busy=1 grant=0 pending=2
PASS [ack 2 -> pending 1] busy=1 grant=0 pending=1
PASS [ack 3 -> GRANT] busy=0 grant=1 pending=0
PASS [start: 0 sharers -> immediate grant] busy=0 grant=1 pending=0
ALL TESTS PASSED

14. DebugLab — the write that jumped the last ack

cyc  event      pending  inv_grant  note
 2   start (3)   3        0
 3   ack 1       2        0
 4   ack 2       1        1 (!)      granted with pending=1 — one sharer still live
 5   ack 3       0        0          the last ack arrives too late

15. Common Mistakes

• Granting the write before all acks. Assumption: most acknowledgements is close enough. Bug: a live sharer reads the old value (the DebugLab). Prevention: gate the grant on pending == 0.
• Dropping a dirty copy on invalidation. Assumption: invalidation just marks the line invalid. Bug: the newest value is lost (2.6). Prevention: a dirty sharer returns its data in the ack before going Invalid.
• Broadcasting invalidates to non-holders. Assumption: snoop everyone to be safe. Bug: wasted snoop bandwidth and acks from caches that never held the line. Prevention: a directory targets only actual sharers (2.8).
• Ignoring an invalidate that races the sharer's own request. Assumption: requests are independent. Bug: deadlock or a lost copy when a sharer requests and is invalidated at once. Prevention: the Home Node serializes conflicting requests to one order.
• Clearing the pending count on a lost ack via timeout-and-proceed. Assumption: a timeout means the sharer is gone. Bug: a slow-but-live sharer is treated as invalidated. Prevention: recover a lost ack with retry, not by granting early.
• Treating this counter as the full Home Node. Assumption: ack counting is the whole invalidation path. Bug: missing the directory, data routing, and conflict handling. Prevention: this is the completion-gating concept; the full HN is Modules 4 and 11.

16. Engineering Checklist

• A write to a shared line invalidates every other copy before proceeding.
• The grant is gated on all invalidate acks (pending == 0), never a partial condition.
• A dirty sharer returns its data in the ack; a clean sharer just drops the copy.
• Conflicting requests to the same line are serialized by the Home Node.
• A lost ack is recovered by retry, never by granting the write early.
• The writer's latency is bounded by the slowest sharer to acknowledge.

17. Key Takeaways

• Invalidation removes peer copies so a writer can become the single owner.
• The flow is request → snoop-invalidate → acknowledge → grant, and the grant is strictly after all acks.
• The write waits for every acknowledgement — one ack short is a single-writer (coherency) violation.
• Invalidating a dirty copy rescues its data (returned in the ack); a clean copy is just dropped.
• The writer's latency is set by the slowest sharer, and completion releases the tracked transaction.
• This tracker is representative — the completion-gating concept, not a full Home Node.

18. Quick Revision

Invalidations. To write a shared line, remove every other copy first. Flow: writer requests unique → Home Node snoop-invalidates each sharer → each drops its copy (→ Invalid) and acks (a dirty one returns data) → HN grants only after all acks. The grant is strictly after the last ack — one ack short leaves a live stale reader (coherency violation). Clean copy = drop; dirty copy = rescue data first (2.6). The writer's latency is the slowest sharer's; a lost ack needs retry, not an early grant. A directory targets only real sharers (2.8). Representative model, not a full Home Node.

Coming Next

Chapter 2.8 — Snoop Mechanisms. This chapter assumed the Home Node knew exactly whom to invalidate. The next one asks how: broadcast the snoop to every cache and let non-holders ignore it, or keep a directory that tracks sharers and snoops only them. That choice — broadcast versus directory — is the central scalability tradeoff in coherent interconnects, and the reason CHI is built around distributed Home Nodes.