Cache Controllers

Module 16 · Chapter 16.4 · CHI RTL Design Thinking

Project thread — 16.3 managed the directory RAM. 16.4 is the RN cache controller; 16.5 is the tracker table.

1. Learning Outcomes

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

• Name what the cache controller services — core accesses, snoops, fills, writebacks.
• Explain why a dirty victim being evicted must be written back to memory.
• State that the victim must be captured into a writeback buffer before the fill.
• Describe why the fill and the victim share the same cache-line storage.
• Diagnose the lost dirty data from a fill before capture.
• Implement a representative evict-then-fill model in SystemVerilog, Verilog-2001, and VHDL.

2. Why Should I Learn This?

The cache controller is the RN's engine — it turns core loads and stores, incoming snoops, and returning fills into cache-line state changes. Most of it is bookkeeping; the dangerous part is eviction with a dirty victim, because two operations there compete for the same physical storage: the victim currently occupies the cache line, and the fill is about to write it.

If those two are ordered wrong, dirty data is destroyed. A dirty victim holds a value newer than memory, so it must be written back — but the fill data will overwrite the exact bytes the victim occupies. The controller must capture the victim into a writeback buffer first, then let the fill proceed. Get the order wrong — fill before capture — and the victim's data is gone before it was saved; the writeback then drains fill data (or garbage) to the victim's memory address, losing the update and corrupting memory. This chapter is the cache controller and the one ordering — capture, then fill — that keeps a dirty eviction from silently corrupting memory.

3. Key Terms

4. Previous Chapter Connection

This chapter is the RTL of the cache you have modeled since Module 10. Cache states (Chapter 10.1) live in the tag RAM here; writebacks of dirty lines (Chapter 8.6) are issued by this controller; snoops (Chapter 16.2) hit this cache. Where those chapters described the cache's behavior, this one is the datapath and control that realize it.

The victim-vs-fill hazard is a structural hazard on the cache-line storage — the same class of problem as the directory's entry reuse (Chapter 16.3), but on data rather than tracking metadata. In 16.3, a directory entry was reused before its old meaning was retired (back-invalidation). Here, a cache line is overwritten before its old contents are saved (writeback capture). Both are "reuse a resource before retiring its prior occupant" bugs, and both are fixed by sequencing the retirement before the reuse. This chapter is that pattern applied to the cache's data storage — the last of the RTL structural hazards before the module turns to trackers.

5. Core Concept — capture the dirty victim, then fill

The cache controller services accesses, snoops, and fills — and on a dirty eviction it must capture the victim into a writeback buffer before the fill overwrites the line.

• A fill displaces a victim. Filling a line into a full set overwrites the chosen way, whose current occupant is the victim.
• A dirty victim must be written back. If the victim is dirty (UD/SD), it holds the only value newer than memory, so it must be written back — not just dropped.
• Fill and victim share storage. The fill data and the victim occupy the same cache-line bytes. The fill will destroy the victim's data when it writes.
• Capture first, then fill. The controller must copy the dirty victim into a writeback buffer (from which the writeback drains to memory) before allowing the fill. Only then is the victim's data safe.

The synthesis:

The cache controller services core accesses, snoops, and fills. On a miss that fills into a set whose way holds a dirty victim, the victim (newer than memory) must be written back — but the fill overwrites the same cache-line storage. So the controller must capture the dirty victim into a writeback buffer before the fill proceeds. Filling before capture destroys the victim's data — the writeback drains garbage, the update is lost, and memory is corrupted.

6. Engineering Mental Model — repainting an occupied parking space

Think of a single parking space (the cache way) with a car in it (the victim), and a new car (the fill) that needs the space.

• The old car is valuable and unique (a dirty line — the only copy of something). Before the new car parks, the old car must be driven to the garage (written back to memory).
• Crucially, the old car must be moved out of the space first — into a holding lane (the writeback buffer) — before the new car pulls in. The space cannot hold both.
• Right order: move the old car to the holding lane (capture), then let the new car park (fill). From the holding lane, the old car is driven to the garage (writeback drains). Nothing lost.
• Wrong order: let the new car park on top of the old one — impossible in reality, but in RTL the fill just overwrites the bytes. The old car is crushed (dirty data destroyed). Then the "tow to garage" (writeback) hauls away the new car's plates on the old car's paperwork — garbage to the wrong address.

The holding lane is the writeback buffer; moving the old car out first is capture-then-fill. Parking on top of the old car is the fill-before-capture bug.

7. Engineering Diagram — the cache-controller datapath

The capture edge (data RAM → writeback buffer) must fire before the fill edge (fill → data RAM). Both touch the same line in the RAM; capturing first preserves the victim. The DebugLab lets the fill edge fire first.

8. Engineering Diagram — the eviction/fill FSM

The path is VALID DIRTY → CAPTURE → FILL → VALID NEW. FILL is reachable only through CAPTURE — the victim's data is in the writeback buffer before the line is overwritten. A transition from VALID DIRTY straight to FILL (skipping CAPTURE) is the bug.

9. Why Fill-Before-Capture Loses Data

The hazard, made explicit.

• The victim is the only current copy. A dirty victim (UD/SD) is newer than memory — its data exists nowhere else. Losing it loses the value.
• The fill overwrites the storage. The fill writes the newly-fetched line into the same cache-line bytes the victim occupies. After the fill, the victim's data is gone from the RAM.
• A late capture reads fill data. If the writeback captures after the fill, it reads the fill's data (or a half-overwritten mix) — not the victim's. The writeback drains wrong data.
• Memory is corrupted at the victim's address. The writeback targets the victim's address but carries the fill's data — so the victim's update is lost and the victim's memory location is overwritten with garbage.

The point to carry:

This is a read-before-write ordering on a shared storage resource, and it is one of the most classic hardware hazards there is — the same shape as a register read that must happen before the write that clobbers it. The cache-line storage is written by the fill and read by the writeback capture, and correctness demands the read (capture) precede the write (fill). What makes it easy to get wrong is that the fill and the writeback are logically independent transactions — one brings data in, the other sends data out — so a designer may pipeline them for throughput without noticing they alias on the same physical line. The aliasing is the whole problem: they are not independent, because they touch the same bytes. The fix is to make the dependency explicit — the fill must wait for the capture — turning an accidental alias into an ordered sequence. This is why a victim buffer exists at all: it decouples the two by giving the victim a separate home (the buffer) so the writeback can drain on its own schedule after the line is safely freed for the fill. Capture-then-fill is the sequencing that the buffer makes possible.

10. Evicting a Dirty Victim — right and wrong order

A miss fills line Y into a way holding dirty victim X.

1. Right order — capture X. The controller copies dirty victim X's data into the writeback buffer. X's value is now safely held outside the cache line.
2. Right order — fill Y. With X captured, the fill writes Y into the cache line, overwriting X's old storage. Y is now cached; X is in the buffer.
3. Right order — drain X. The writeback transaction drains X from the buffer to X's memory address. X's update is preserved; memory is correct.
4. Wrong order — fill Y first. The controller writes Y into the cache line before capturing X. X's data in the RAM is now overwritten by Y — gone.
5. Wrong order — writeback drains garbage. The writeback captures after the fill, reading Y's data (not X's), and drains it to X's memory address. X's update is lost, and X's location holds Y's bytes — memory corrupted.

Capture-first preserved X; fill-first destroyed it and corrupted memory. The DebugLab is steps 4–5.

11. RTL / Hardware View — capture then fill

The fill is permitted only after the dirty victim is captured into the writeback buffer. Representative.

// Representative cache evict-then-fill control (educational).
// A dirty victim must be CAPTURED into the writeback buffer BEFORE the fill overwrites
// the cache line -- both target the same storage. The fill is gated on victim_captured.
// Filling before capture destroys the victim's dirty data and corrupts its memory line.
module chi_cache_evict_fill (
  input  logic clk, rst_n,
  input  logic evict_dirty,     // a dirty victim is being evicted for a fill
  input  logic fill_data_ready, // the fill data has arrived
  input  logic wb_buf_free,     // the writeback buffer can accept the victim
  output logic capture_victim,  // copy the dirty victim into the WB buffer
  output logic do_fill,         // overwrite the cache line with the fill
  output logic victim_captured  // the victim is safely in the WB buffer
);
  logic captured_q;
  assign victim_captured = captured_q;
  // Capture the dirty victim first, when the buffer is free.
  assign capture_victim  = evict_dirty && !captured_q && wb_buf_free;
  // Fill ONLY after the victim is captured (or when there is no dirty victim to save).
  assign do_fill         = fill_data_ready && (captured_q || !evict_dirty);
 
  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n)                     captured_q <= 1'b0;
    else if (capture_victim)        captured_q <= 1'b1;   // victim now in WB buffer
    else if (do_fill)               captured_q <= 1'b0;   // done; ready for next evict
  end
endmodule

The same behavior in Verilog-2001:

// Representative cache evict-then-fill control (Verilog-2001).
module chi_cache_evict_fill (
  input  wire clk, rst_n, evict_dirty, fill_data_ready, wb_buf_free,
  output wire capture_victim, do_fill,
  output wire victim_captured
);
  reg captured_q;
  assign victim_captured = captured_q;
  assign capture_victim  = evict_dirty & ~captured_q & wb_buf_free;
  assign do_fill         = fill_data_ready & (captured_q | ~evict_dirty);
 
  always @(posedge clk or negedge rst_n) begin
    if (!rst_n)              captured_q <= 1'b0;
    else if (capture_victim) captured_q <= 1'b1;
    else if (do_fill)        captured_q <= 1'b0;
  end
endmodule

And in VHDL:

-- Representative cache evict-then-fill control (VHDL).
library ieee;
use ieee.std_logic_1164.all;
 
entity chi_cache_evict_fill is
  port (
    clk, rst_n      : in  std_logic;
    evict_dirty     : in  std_logic;
    fill_data_ready : in  std_logic;
    wb_buf_free     : in  std_logic;
    capture_victim  : out std_logic;
    do_fill         : out std_logic;
    victim_captured : out std_logic
  );
end entity;
 
architecture rtl of chi_cache_evict_fill is
  signal captured_q : std_logic := '0';
  signal cap, fil   : std_logic;
begin
  cap <= evict_dirty and (not captured_q) and wb_buf_free;
  fil <= fill_data_ready and (captured_q or (not evict_dirty));
  capture_victim  <= cap;
  do_fill         <= fil;
  victim_captured <= captured_q;
 
  process (clk, rst_n)
  begin
    if rst_n = '0' then
      captured_q <= '0';
    elsif rising_edge(clk) then
      if cap = '1' then
        captured_q <= '1';        -- victim captured to WB buffer
      elsif fil = '1' then
        captured_q <= '0';
      end if;
    end if;
  end process;
end architecture;

In all three, do_fill is gated on captured_q (or no dirty victim) — the fill cannot overwrite the line until the victim is captured. The DebugLab drops the captured_q term from do_fill, letting the fill run before capture.

12. Verification View — no fill before capture

The properties enforce the ordering: a dirty victim is captured before its line is filled.

// Bind to chi_cache_evict_fill.
// 1. When evicting a dirty victim, the fill never runs before the victim is captured.
property p_no_fill_before_capture;
  @(posedge clk) disable iff (!rst_n)
    (evict_dirty && do_fill) |-> victim_captured;
endproperty
 
// 2. Capture precedes fill in time for a dirty eviction.
property p_capture_then_fill;
  @(posedge clk) disable iff (!rst_n)
    (evict_dirty && capture_victim) |-> !do_fill;   // not the same cycle as capture
endproperty
 
// 3. With no dirty victim, the fill may proceed directly (no needless stall).
property p_clean_fill_direct;
  @(posedge clk) disable iff (!rst_n)
    (!evict_dirty && fill_data_ready) |-> do_fill;
endproperty

The system point, beyond the checks:

The correctness property here is an ordering across time between two independent-looking datapaths, which is exactly the kind of property that unit-testing each datapath in isolation will miss. Test the fill path alone and it fills correctly; test the writeback path alone and it drains correctly; only when they share a cache line does the ordering matter, and only a test that evicts a dirty victim while filling the same way exercises it. This is the recurring lesson of the whole RTL module: the dangerous bugs live at the interaction between correct-in-isolation components — the same-line request race (16.1), the dirty-snoop response (16.2), the directory reuse (16.3), and now the victim-fill alias (16.4). Each component is individually fine; the bug is a missing dependency between them. Verification must therefore be written against the interactions — force the two paths to collide on the same resource — not just the paths. The victim_captured handshake is the explicit dependency that makes the interaction safe, and the property that fill waits for it is the one that must be proven, because it is the only thing standing between two independently-correct datapaths and a corrupted memory line.

• What it proves: the fill waits for the victim capture on a dirty eviction; clean fills proceed directly.
• What it does not prove: the writeback drains the buffer to the correct address — that is the writeback path.
• Bug signature: do_fill asserted on a dirty eviction while victim_captured is low.

13. Testbench — the fill must wait for the victim capture

Evicts a dirty victim and checks the fill does not proceed until the victim is captured.

module tb_chi_cache_evict_fill;
  logic clk = 0, rst_n = 0, evict_dirty, fill_data_ready, wb_buf_free;
  logic capture_victim, do_fill, victim_captured;
  int errors = 0;
 
  chi_cache_evict_fill dut (.*);
  always #5 clk = ~clk;
 
  // Guard: the fill must never run on a dirty eviction before the victim is captured.
  always @(posedge clk) if (rst_n && evict_dirty && do_fill && !victim_captured) begin
    errors++; $display("FAIL fill before capture -> dirty victim destroyed!");
  end
 
  initial begin
    evict_dirty = 0; fill_data_ready = 0; wb_buf_free = 1;
    @(posedge clk) rst_n = 1;
 
    // Dirty eviction: fill data is ready, but the victim is not yet captured.
    @(posedge clk) begin evict_dirty = 1; fill_data_ready = 1; end
    #1;
    if (do_fill) begin errors++; $display("FAIL fill fired before capture"); end
    else $display("PASS fill held: capturing victim first (capture=%0b)", capture_victim);
 
    // Next cycle: the victim is captured; now the fill may proceed.
    @(posedge clk);
    #1;
    if (!victim_captured) begin errors++; $display("FAIL victim not captured"); end
    else if (!do_fill) begin errors++; $display("FAIL fill did not proceed after capture"); end
    else $display("PASS victim captured, fill proceeds");
 
    @(posedge clk) begin evict_dirty = 0; fill_data_ready = 0; end
 
    // Clean fill (no dirty victim): proceeds directly, no stall.
    @(posedge clk) begin evict_dirty = 0; fill_data_ready = 1; end
    #1;
    if (!do_fill) begin errors++; $display("FAIL clean fill stalled"); end
    else $display("PASS clean fill proceeds directly");
 
    if (errors == 0) $display("ALL TESTS PASSED");
    else             $display("%0d FAILURE(S)", errors);
    $finish;
  end
endmodule

Expected output:

PASS fill held: capturing victim first (capture=1)
PASS victim captured, fill proceeds
PASS clean fill proceeds directly
ALL TESTS PASSED

14. DebugLab — filling before the dirty victim is captured

way holds dirty victim X (value = NEW_X, only copy newer than memory)
miss fills line Y into the same way; fill data ready
buggy controller: do_fill fires immediately (no victim_captured gate)
  -> fill writes Y into the cache line -> NEW_X in the RAM OVERWRITTEN by Y
  -> writeback captures AFTER the fill -> reads Y (not NEW_X)
  -> drains Y to X's memory address -> X's update LOST, X's memory = garbage(Y)
correct: capture NEW_X into WB buffer FIRST -> then fill Y -> drain NEW_X to X's address

15. Common Mistakes

• Filling before capture. Assumption: fill and writeback are independent. Bug: victim destroyed (the DebugLab). Prevention: gate fill on capture.
• No victim buffer. Assumption: write back in place. Bug: no decoupling, forced collision. Prevention: capture to a buffer.
• Capturing after the fill. Assumption: any order works. Bug: reads fill data. Prevention: capture first.
• Dropping a dirty victim. Assumption: eviction is free. Bug: lost update. Prevention: dirty victims write back.
• Stalling clean fills. Assumption: always capture. Bug: needless latency. Prevention: only dirty victims need capture.
• Confusing with directory eviction. Assumption: 16.3 covers it. Bug: data vs metadata. Prevention: 16.3 is the directory; 16.4 is the cache data.

16. Engineering Checklist

• Service core accesses, snoops, fills, and writebacks in the controller.
• On a dirty eviction, capture the victim into the writeback buffer.
• Gate the fill on the victim being captured.
• Drain the writeback (victim data) to the victim's address.
• Let clean fills proceed directly — no needless capture.
• Verify the fill/writeback interaction on the same line, not each in isolation.

17. Key Takeaways

• The cache controller services accesses, snoops, fills, and writebacks.
• A dirty victim displaced by a fill must be written back.
• The fill and the victim share the same cache-line storage.
• Capture the dirty victim into a writeback buffer before the fill.
• Filling first destroys the victim and drains garbage to memory.
• Retire the occupant before reusing the storage; the model here is representative.

18. Quick Revision

Cache controllers. The cache controller is the RN's RTL engine, servicing core accesses, snoops, fills, and writebacks. The correctness crux is a dirty eviction: when a miss fills a line into a set whose chosen way holds a dirty victim (state UD/SD — a value newer than memory), the victim must be written back, but the fill will overwrite the same cache-line storage the victim occupies. So the controller must capture the dirty victim into a writeback buffer (from which the writeback drains to memory) before allowing the fill to overwrite the line. The failure to avoid: starting the fill before the capture — the fill overwrites the victim's data in the RAM, destroying the only copy newer than memory, and the writeback then captures after the fill and drains the fill's data (or garbage) to the victim's memory address, losing the update and corrupting memory. This is a read-before-write hazard: the cache line is read by the writeback capture and written by the fill, and the read must precede the write. The fill and writeback look independent but alias on the same bytes; a victim buffer decouples them, and gating the fill on victim_captured makes the ordering explicit — capture, then fill. It is the cache-datapath counterpart of Chapter 16.3's directory-entry reuse: retire the occupant before reusing the storage. Representative model; 16.5 covers transaction tracking.

Coming Next

Chapter 16.5 — Transaction Tracking. Every outstanding transaction needs a tracker entry; managing that table has its own hazard. Chapter 16.5 covers transaction tracking — the tracker (MSHR) table's allocation and deallocation, and why an entry must be freed only when the transaction is fully complete, or a late response finds no tracker — or worse, a reallocated one — and is misapplied.