Evict Flow

Module 8 · Chapter 8.7 · Request Flows

Project thread — 8.6 wrote back a dirty line; this chapter drops a clean one, which needs no data. Together they are the eviction pair. 8.8 is MakeUnique — upgrading Shared to Unique without re-fetching.

1. Learning Outcomes

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

• State that Evict drops a clean owned line (UC/SC) that needs no writeback.
• Explain that Evict moves no data — memory already holds the value.
• Describe Evict's real purpose: keeping the home's directory precise.
• Distinguish Evict from WriteBack — clean versus dirty, no-data versus data.
• Diagnose why silently dropping clean lines pollutes the directory.
• Implement a representative Evict decision in SystemVerilog, Verilog-2001, and VHDL.

2. Why Should I Learn This?

Most cache evictions are of clean lines — data that was read but never modified, which memory already holds. Dropping such a line loses nothing, so it needs no writeback. Yet the home still benefits from knowing it happened, and that is what Evict is: a cheap notification that costs a request and a completion, no data.

Its lesson is that coherence hardware tracks not just data but who holds what. The home's directory — and the snoop filter that often backs it — decides which caches to snoop on any transaction. If that record drifts, the home either wastes snoops on caches that no longer hold a line, or, in a precise filter, is forced to back-invalidate real lines to make room for stale entries. Evict keeps the record honest. Understanding it is understanding the bookkeeping that keeps snoops targeted and the filter clean — a performance concern that, left unattended, degrades a whole system.

3. Key Terms

4. Previous Chapter Connection

Chapter 8.6's WriteBack evicted a dirty line — its data had to reach memory before the cache let go, under the full DBID handshake. Evict is the other half of the eviction pair: the clean case.

Because a clean line's data is already in memory, Evict carries no data and needs no DBID — it is just a REQ and a Comp. What it shares with WriteBack is the end state (the cache goes Invalid) and the discipline of choosing the right one: WriteBack if dirty, Evict if clean. And it adds a new idea the read/write flows did not stress — the flow exists not to move data but to keep the home's directory accurate.

5. Core Concept — drop a clean line, notify the home, no data

An Evict drops a clean line the requester holds and tells the home, so the directory stays precise. It moves no data and ends the cache Invalid.

• Clean only. The line is UC or SC — clean, matching memory. Its data need not be saved; a dirty line would use WriteBack (Chapter 8.6).
• Request. The cache sends Evict to the home. No DBID, no data — there is nothing to write back.
• Directory update. The home removes the requester from the line's holder set in its directory (and snoop filter), so it will not snoop this cache for this line again.
• Complete. The home returns Comp. The cache transitions the line to I and frees the entry.

The synthesis:

Evict drops a clean line and notifies the home — a REQ → Comp exchange with no data, because memory already holds the value. Its purpose is directory precision: the home removes the requester from the holder set, so future snoops skip this cache. WriteBack moves dirty data; Evict moves only information. Use WriteBack for dirty lines, Evict for clean.

6. Engineering Mental Model — return an unmarked copy, tell the desk

The office document once more — but this time you were only reading it, and your copy has no edits (a clean line).

• You do not need to file anything — the master copy already has everything yours does. You just recycle your copy.
• But you do tell the front desk "I've finished with document 47" (the Evict notification). Now the desk's checkout log no longer lists you as holding it.
• If you silently shred your copy without telling the desk, the log still says you have it. Later, when someone needs the document back from all holders, the desk pings you needlessly — and if the log is full, it might even recall a document you are actively using to free a slot, because it thinks you are still holding one you are not.

The copy was worthless to keep (clean), but the checkout log matters. Evict is the courtesy note that keeps it accurate.

7. Engineering Diagram — an Evict

Two beats, no data: the cache announces it is dropping a clean line, the home updates its directory and acknowledges, and the line goes to Invalid. Compare WriteBack's four beats with a DBID grant and a data transfer — Evict is that flow with the data removed, because there is nothing dirty to save.

8. Evict versus WriteBack

The eviction pair, side by side.

The rule to carry: dirtiness picks the flow. A dirty line must WriteBack — its data would be lost otherwise. A clean line uses Evict — its data is already in memory, so no transfer is needed, and the flow exists only to keep the directory accurate. Both end the cache in I; they differ entirely in whether data moves.

9. Why Notify at All — directory precision

Since Evict moves no data, its whole value is the notification, and that value is worth stating.

• The home tracks holders. The directory (often a snoop filter) records which caches hold each line, so the home snoops only actual holders on a read-unique or write.
• Silent drops make it drift. If a cache drops a clean line without Evict, the directory still lists it — a phantom holder. The home then snoops a cache that no longer has the line.
• Phantom snoops waste bandwidth. Each needless snoop consumes fabric and delays the transaction waiting for a "not present" response.
• Filters can back-invalidate. A precise snoop filter has finite capacity; phantom entries occupy slots. To make room for a new line, the filter may back-invalidate a real, in-use line — evicting something the cache actively needs. Silent drops turn into thrashing.

The point to carry:

Evict is a data-free flow whose payload is accuracy. Coherence hardware acts on its record of who holds what: it snoops that set and sizes its filter to it. Let the record over-approximate — list holders that have gone — and the home pays in wasted snoops and, worse, back-invalidations that evict lines still in use. Evict is cheap insurance against that drift: one request, one completion, and the directory stays true. The line was worthless to keep; the knowledge that it is gone is not.

10. Flow Walkthrough — Evict a clean SC line

RN0 holds a line in SC (clean) and must reuse the entry for a new line.

1. Choose the flow. The line is clean, so Evict is correct — a dirty line would need WriteBack. No data will move.
2. REQ. RN0 sends Evict to HN. There is no DBID and no data beat.
3. Directory update. HN removes RN0 from this line's holder set (and its snoop filter). It will no longer snoop RN0 for this line.
4. Comp. HN returns Comp. RN0 transitions the line SC → I and reuses the entry.

End state: RN0 no longer holds the line, the directory reflects that precisely, and no data moved. A later ReadUnique from another core will not snoop RN0 for this line — because RN0 told the home it was gone. Skip step 2 (drop silently) and the directory keeps a phantom RN0 — the DebugLab.

11. RTL / Hardware View — an Evict decision

The requester's Evict logic is small: on a clean eviction, notify the home; on a dirty one, route to WriteBack instead; and never send data. Representative and sequential.

// Representative requester-side Evict decision (educational).
// A CLEAN line eviction issues Evict (notify the home; no data). A DIRTY line
// must route to WriteBack instead (its data would be lost). Evict never sends
// data, and the line goes Invalid only after Comp.
module chi_evict_txn (
  input  logic clk, rst_n,
  input  logic evict,            // this cache wants to drop the line
  input  logic is_dirty,         // dirty -> WriteBack, not Evict
  input  logic comp,             // home acknowledged the Evict
  output logic evict_req,        // issue Evict (clean line) -- notify the home
  output logic route_writeback,  // dirty line: use WriteBack instead
  output logic sends_data,       // Evict never carries data
  output logic invalidated       // line dropped to I (after Comp)
);
  typedef enum logic { IDLE, WAIT_COMP } state_t;
  state_t state, next;
 
  always_comb begin
    next = state;
    case (state)
      IDLE:      if (evict && !is_dirty) next = WAIT_COMP;  // clean -> notify
      WAIT_COMP: if (comp)               next = IDLE;
    endcase
  end
 
  // Notify on a clean eviction; a dirty line is sent to WriteBack, not dropped.
  assign evict_req       = (state == IDLE) && evict && !is_dirty;
  assign route_writeback = (state == IDLE) && evict &&  is_dirty;
  assign sends_data      = 1'b0;                         // Evict moves no data
  assign invalidated     = (state == WAIT_COMP) && comp; // drop to I after Comp
 
  always_ff @(posedge clk or negedge rst_n)
    if (!rst_n) state <= IDLE;
    else        state <= next;
endmodule

The same behavior in Verilog-2001:

// Representative requester-side Evict decision (Verilog-2001).
module chi_evict_txn (
  input clk, rst_n, evict, is_dirty, comp,
  output evict_req, route_writeback, sends_data, invalidated
);
  localparam IDLE = 1'b0, WAIT_COMP = 1'b1;
  reg state, next;
 
  always @* begin
    next = state;
    case (state)
      IDLE:      next = (evict && !is_dirty) ? WAIT_COMP : IDLE;
      WAIT_COMP: next = comp ? IDLE : WAIT_COMP;
    endcase
  end
 
  assign evict_req       = (state == IDLE) && evict && !is_dirty;
  assign route_writeback = (state == IDLE) && evict &&  is_dirty;
  assign sends_data      = 1'b0;
  assign invalidated     = (state == WAIT_COMP) && comp;
 
  always @(posedge clk or negedge rst_n)
    if (!rst_n) state <= IDLE;
    else        state <= next;
endmodule

And in VHDL:

-- Representative requester-side Evict decision (VHDL).
library ieee;
use ieee.std_logic_1164.all;
 
entity chi_evict_txn is
  port (
    clk, rst_n      : in  std_logic;
    evict           : in  std_logic;
    is_dirty        : in  std_logic;
    comp            : in  std_logic;
    evict_req       : out std_logic;
    route_writeback : out std_logic;
    sends_data      : out std_logic;
    invalidated     : out std_logic
  );
end entity;
 
architecture rtl of chi_evict_txn is
  type state_t is (IDLE, WAIT_COMP);
  signal state : state_t := IDLE;
begin
  process (clk, rst_n)
  begin
    if rst_n = '0' then
      state <= IDLE;
    elsif rising_edge(clk) then
      case state is
        when IDLE      => if evict = '1' and is_dirty = '0' then state <= WAIT_COMP; end if;
        when WAIT_COMP => if comp = '1'                     then state <= IDLE;      end if;
      end case;
    end if;
  end process;
 
  evict_req       <= '1' when (state = IDLE and evict = '1' and is_dirty = '0') else '0';
  route_writeback <= '1' when (state = IDLE and evict = '1' and is_dirty = '1') else '0';
  sends_data      <= '0';
  invalidated     <= '1' when (state = WAIT_COMP and comp = '1') else '0';
end architecture;

All three notify on a clean eviction (evict_req), route a dirty line to WriteBack instead, and never send data. The DebugLab shows what happens when a clean eviction skips the notification.

12. Verification View — clean-only, notify, no data

The properties that keep Evict correct: it is issued only for clean lines, always notifies, and never sends data.

// Bind to chi_evict_txn.
// 1. Evict is issued only for a CLEAN line — a dirty line routes to WriteBack.
property p_evict_only_clean;
  @(posedge clk) disable iff (!rst_n)
    evict_req |-> !is_dirty;
endproperty
 
// 2. A clean eviction always NOTIFIES (issues Evict) — it never silently drops.
property p_notify_on_clean_evict;
  @(posedge clk) disable iff (!rst_n)
    (evict && !is_dirty && !route_writeback) |-> evict_req;
endproperty
 
// 3. Evict never carries data, and a dirty eviction is routed to WriteBack.
property p_no_data_and_dirty_routed;
  @(posedge clk) disable iff (!rst_n)
    (sends_data == 1'b0) && ((evict && is_dirty) |-> route_writeback);
endproperty

The system point, beyond the checks:

Evict is the flow that carries no data, so its correctness is entirely about information. Two facts must be conveyed truthfully: that the line was clean (so no data is owed) and that it is now gone (so the directory can drop the holder). Get the first wrong — Evict a dirty line — and you lose data, the WriteBack that should have run. Get the second wrong — drop silently — and you corrupt the directory with a phantom holder. Neither is a data-path bug; both are failures to keep the home's model of the world accurate. The whole point of Evict is that the model stays true even when nothing moves.

• What it proves: Evict is clean-only, always notifies, and moves no data.
• What it does not prove: the home actually updated its directory — that is the home side.
• Bug signature: a clean eviction with no Evict issued — a phantom holder left in the directory.

13. Testbench — clean notifies, dirty routes to WriteBack

Evicts a clean line and checks the notification and no-data, then confirms a dirty line routes to WriteBack instead.

module tb_chi_evict_txn;
  logic clk = 0, rst_n = 0, evict = 0, is_dirty = 0, comp = 0;
  logic evict_req, route_writeback, sends_data, invalidated;
  int errors = 0;
 
  chi_evict_txn dut (.*);
  always #5 clk = ~clk;
 
  initial begin
    @(posedge clk) rst_n = 1;
 
    // Clean line: Evict issued, no data, no WriteBack routing.
    @(posedge clk) begin evict = 1; is_dirty = 0; end
    if (!evict_req || route_writeback || sends_data) begin
      errors++; $display("FAIL clean evict: req=%0b wb=%0b data=%0b",
                         evict_req, route_writeback, sends_data); end
    else $display("PASS clean line: Evict issued, no data");
    @(posedge clk) evict = 0;
 
    // Complete -> invalidate.
    @(posedge clk) comp = 1;
    if (!invalidated) begin errors++; $display("FAIL not invalidated on Comp"); end
    else $display("PASS invalidated after Comp");
    @(posedge clk) comp = 0;
 
    // Dirty line: no Evict, routes to WriteBack.
    @(posedge clk) begin evict = 1; is_dirty = 1; end
    if (evict_req || !route_writeback) begin
      errors++; $display("FAIL dirty line: req=%0b wb=%0b", evict_req, route_writeback); end
    else $display("PASS dirty line: routed to WriteBack, no Evict");
    @(posedge clk) evict = 0;
 
    if (errors == 0) $display("ALL TESTS PASSED");
    else             $display("%0d FAILURE(S)", errors);
    $finish;
  end
endmodule

Expected output:

PASS clean line: Evict issued, no data
PASS invalidated after Comp
PASS dirty line: routed to WriteBack, no Evict
ALL TESTS PASSED

14. DebugLab — silently dropping clean lines

RN0 holds many SC lines, then drops them locally WITHOUT Evict
directory still lists RN0 as a holder of all of them (phantom)
later: RN2 issues ReadUnique(L) -> HN snoops RN0 (phantom) -> "not present"
       many such wasted snoops per transaction
filter full of phantom entries -> HN back-invalidates a HOT line in RN0
       to reclaim a slot -> RN0 re-fetches a line it never wanted to lose

15. Common Mistakes

• Dropping clean lines silently. Assumption: no data means no notice needed. Bug: phantom holders (the DebugLab). Prevention: issue Evict on clean eviction.
• Evicting a dirty line. Assumption: any line can be dropped. Bug: lost dirty data. Prevention: dirty lines use WriteBack (Chapter 8.6).
• Sending data on an Evict. Assumption: eviction transfers the line. Bug: needless traffic. Prevention: Evict carries no data.
• Expecting a DBID. Assumption: Evict is a write. Bug: waiting for a grant that never comes. Prevention: Evict is REQ → Comp, no DBID.
• Not going to Invalid. Assumption: the cache keeps a copy. Bug: stale holder. Prevention: Evict ends the cache in I.
• Assuming Evict preserves data. Assumption: Evict is a light WriteBack. Bug: dirty data dropped. Prevention: Evict is for clean lines only.

16. Engineering Checklist

• Use Evict only for a clean line (UC/SC) — dirty lines WriteBack.
• Send no data and expect no DBID — Evict is REQ → Comp.
• Issue Evict on clean eviction — never drop silently.
• Let the home remove the holder from its directory / snoop filter.
• Transition the line to I after Comp.
• Keep the directory precise to avoid phantom snoops and back-invalidations.

17. Key Takeaways

• Evict drops a clean owned line (UC/SC) that needs no writeback — memory already has the value.
• It moves no data; the flow is REQ → Comp, with the cache ending I.
• Its purpose is directory precision — the home removes the requester from the holder set.
• Silently dropping clean lines leaves phantom holders, causing wasted snoops and, in a precise filter, back-invalidations.
• Dirtiness picks the flow: WriteBack for dirty, Evict for clean.
• Notify on clean eviction, move no data, keep the directory true; the model here is representative.

18. Quick Revision

Evict flow. Evict drops a clean owned line (UC/SC) that needs no writeback — memory already holds the value — so the flow moves no data and is just REQ Evict → Comp, the cache ending Invalid. It is the lightweight sibling of WriteBack: dirtiness picks the flow — a dirty line must WriteBack to preserve its data, a clean line uses Evict. Evict's purpose is not data movement but directory precision: the home removes the requester from the line's holder set (and snoop filter), so it will not snoop this cache for this line again. The failure to avoid is dropping clean lines silently, without Evict: the directory keeps phantom holders, drawing needless snoops, and a precise snoop filter — full of stale entries — is forced to back-invalidate lines still in use, causing thrashing. The data is always safe; the home's model of who holds what is what breaks. Clean-only, no data, always notify. Representative model; 8.8 is the MakeUnique flow — upgrading Shared to Unique without re-fetching data.

Coming Next

Chapter 8.8 — MakeUnique Flow. Evict and WriteBack ended a line's residence; MakeUnique changes its permission in place. Chapter 8.8 walks the upgrade a core uses when it already holds a line Shared and now wants to write it — how it obtains Unique ownership by invalidating the other sharers without re-fetching the data it already has, why that saves a full data transfer, and how it differs from ReadUnique, which fetches the line anew. It is the efficient path from reader to writer.