Directory Management

Module 16 · Chapter 16.3 · CHI RTL Design Thinking

Project thread — 16.2 was the RN-F snoop pipeline. 16.3 manages the directory RAM; 16.4 is the cache controller.

1. Learning Outcomes

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

• Name the directory's RTL operations — lookup, update, eviction.
• Explain why a full set forces an eviction to make room for a new line.
• State that a victim entry may be reused only after its sharers are back-invalidated.
• Describe the coherence hole from reusing an entry with live sharers.
• Diagnose the silent corruption from eviction without back-invalidation.
• Implement a representative eviction model in SystemVerilog, Verilog-2001, and VHDL.

2. Why Should I Learn This?

The directory is the home's source of truth about who holds each line, and its RTL must keep that truth accurate through every operation. Lookup and update are the easy paths; eviction is where accuracy is most easily lost. The directory is finite and set-associative, so a new line arriving to a full set must displace an existing entry — and that displaced entry may still describe live cache copies.

This is the trap: if the directory reuses the victim entry without dealing with those copies, the caches that hold the victim's line become invisible to the directory. A later write to that address looks up the reused entry, sees the new line's sharers, and never snoops the caches that still hold the old line — so they keep a stale copy and use it. The fix is a back-invalidation: before reusing an entry, the directory must invalidate the victim's sharers, removing those cache copies so nothing untracked remains. This chapter is the directory's RTL and the one rule — back-invalidate before reuse — that keeps eviction from silently breaking coherence.

3. Key Terms

4. Previous Chapter Connection

This chapter is the RTL of the directory you have used since Module 11. Chapter 11.1 introduced back-invalidation conceptually — a directory eviction forcing a cache eviction; this chapter is the logic that performs it and why omitting it is fatal. Chapter 15.5 covered the performance cost of back-invalidations (an undersized directory churns caches); this chapter is the correctness requirement that they happen at all.

The distinction from Chapter 16.1 matters. There, the hazard was two requests to the same line racing on one entry — solved by serialization. Here, the hazard is a new line displacing a different line's entry — solved by back-invalidation. Both are directory-integrity rules, but they guard different things: 16.1 keeps concurrent updates to one entry atomic; 16.3 keeps an entry's reuse from orphaning the line it used to track. Together they keep the directory an accurate map of the caches.

5. Core Concept — back-invalidate before reuse

Managing the directory means lookup, update, and eviction — and a victim entry may be reused only after its sharers are back-invalidated.

• Lookup and update. A lookup reads a line's sharer/state entry; an update modifies it on a transaction. These preserve the directory's accuracy directly.
• A full set forces eviction. The directory is finite and set-associative. A new line mapping to a full set must evict a victim entry to be tracked.
• The victim may have live sharers. The evicted entry's sharer vector may be non-empty — caches still hold the victim's line.
• Back-invalidate, then reuse. Before reusing the entry, the directory must back-invalidate the victim's sharers — invalidating those cache copies — so nothing untracked remains. Only then may the entry track the new line.

The synthesis:

Directory management is lookup, update, and eviction. Eviction is the hazard: a new line arriving to a full set displaces a victim entry that may still describe live cache copies. The entry may be reused only after those sharers are back-invalidated (their copies removed). Reusing it immediately leaves the caches holding a line the directory no longer tracks — a coherence hole: a later write misses them, and they use stale data.

6. Engineering Mental Model — a lending library's index card

Think of a library that tracks borrowed books on index cards in a small box (the directory), one card per borrowed book.

• Each card lists who has borrowed a book (the sharer vector). Looking up a card tells the librarian who to contact.
• The box is full. To track a new loan, the librarian must reuse an old card — but the old card's book is still out with borrowers.
• The right procedure: before reusing the card, the librarian recalls the book from its borrowers (back-invalidation) — so that book is returned and no longer out. Then the card is free to describe the new loan.
• The wrong procedure: the librarian just erases and rewrites the card for the new book. Now the old book is still out with borrowers, but there is no card for it. If someone reports that old book damaged (a write), the librarian checks the card — which now describes a different book — and never contacts the people who actually have it. They keep the damaged book, unaware.

The recalled book is a back-invalidated line; the erased-and-rewritten card is the reused entry. You must recall before rewriting, or the old borrowers become invisible.

7. Engineering Diagram — the directory operations

The eviction path is evict → back-invalidate → reuse, in that order. The back-invalidation step removes the victim's cache copies before the entry is repurposed. Skipping it — jumping straight from evict to reuse — is the coherence hole.

8. Engineering Diagram — the directory entry lifecycle

The entry cannot go from TRACKED straight to reusable — it must pass through EVICTING, where back-invalidations are in flight, and reach INVALID only when they complete. The DebugLab is a transition that skips EVICTING, reusing a still-tracked entry.

9. Why Skipping Back-Invalidation Breaks Coherence

The coherence hole, made explicit.

• The directory is the only snoop guide. The home snoops only the sharers the directory records (Chapter 15.6). A cache the directory does not list is a cache the home will never snoop.
• Reuse erases the victim's sharers. Overwriting the entry with the new line replaces the victim's sharer vector with the new line's — the victim's sharers are now unrecorded.
• The old copies become invisible. Those caches still hold the victim's line, but the directory has forgotten them. They are an untracked cached line.
• A later write misses them. A write to the victim's address looks up the reused entry, snoops the new line's sharers, and never snoops the old caches — so they keep a stale copy and use it. Silent coherence violation.

The point to carry:

The directory is an inclusion-style invariant: every cached line must be tracked by the directory, so that every cached copy is reachable by a snoop. Eviction is the one operation that can violate inclusion — it removes a directory entry while the cache copies it described still exist. Back-invalidation is what restores inclusion before the violation can matter: by removing the cache copies as the entry is removed, it keeps the two in step, so there is never a cached line without a directory entry. Skipping back-invalidation breaks inclusion silently — the cache and directory disagree, and coherence is only correct while they agree. This is why the ordering is strict: the cache copies must be gone before the entry is reused, never after and never not-at-all. An entry reuse that races ahead of its back-invalidations, or omits them, leaves a window (or a permanent state) where inclusion is broken and a snoop can miss a real holder. Directory correctness is inclusion, and eviction is where inclusion is won or lost.

10. Evicting an Entry — with and without back-invalidation

A new line Y maps to a full set; the victim entry tracks line X with sharers.

1. Victim selected: entry for X. Line X's entry is chosen for eviction. Its sharer vector shows caches c1 and c3 hold X.
2. With back-invalidation. The directory issues back-invalidations to c1 and c3 — they invalidate their copies of X. When both confirm, X is gone from all caches.
3. With back-invalidation — reuse. The entry, now describing no live copies, is reused for line Y. The directory is accurate: X is untracked because it is uncached.
4. Without back-invalidation. The directory overwrites X's entry with Y immediately. c1 and c3 still hold X, but the directory now lists Y's sharers.
5. Without back-invalidation — the hole. A core writes X. The home looks up the entry (now Y), snoops Y's sharers, and never snoops c1/c3. They keep stale X and use it. Corruption.

Back-invalidation kept the directory accurate; skipping it made X invisible. The DebugLab is steps 4–5.

11. RTL / Hardware View — eviction with back-invalidation

An entry with live sharers must complete back-invalidations before it is reusable. Representative.

// Representative directory eviction model (educational).
// A victim entry with live sharers must have those sharers BACK-INVALIDATED before the
// entry is reused for a new line. The entry becomes reusable ONLY when the back-
// invalidations are complete. Reusing it immediately orphans the victim's cache copies.
module chi_dir_evict #(parameter NNODE = 8) (
  input  logic              clk, rst_n,
  input  logic              evict_start,     // this entry chosen as victim
  input  logic [NNODE-1:0]  victim_sharers,  // caches still holding the victim line
  input  logic [NNODE-1:0]  binv_ack,        // back-invalidation acks arriving
  output logic [NNODE-1:0]  binv_pending,    // sharers not yet invalidated
  output logic              back_inval_done, // all sharers invalidated
  output logic              reusable         // entry may be reused now
);
  logic [NNODE-1:0] pend_q;
  logic             evicting_q;
 
  assign binv_pending    = pend_q;
  assign back_inval_done = evicting_q && (pend_q == '0);   // no sharer left
  // The entry is reusable ONLY when back-invalidation is complete.
  assign reusable        = back_inval_done;
 
  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      pend_q <= '0; evicting_q <= 1'b0;
    end else if (evict_start) begin
      pend_q     <= victim_sharers;   // must invalidate all current sharers
      evicting_q <= 1'b1;
    end else if (evicting_q) begin
      pend_q <= pend_q & ~binv_ack;   // clear acked sharers
      if ((pend_q & ~binv_ack) == '0) evicting_q <= 1'b0;  // done
    end
  end
endmodule

The same behavior in Verilog-2001:

// Representative directory eviction model (Verilog-2001).
module chi_dir_evict #(parameter NNODE = 8) (
  input                  clk, rst_n, evict_start,
  input  [NNODE-1:0]     victim_sharers, binv_ack,
  output [NNODE-1:0]     binv_pending,
  output                 back_inval_done, reusable
);
  reg [NNODE-1:0] pend_q; reg evicting_q;
  assign binv_pending    = pend_q;
  assign back_inval_done = evicting_q & (pend_q == {NNODE{1'b0}});
  assign reusable        = back_inval_done;
 
  always @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      pend_q <= {NNODE{1'b0}}; evicting_q <= 1'b0;
    end else if (evict_start) begin
      pend_q <= victim_sharers; evicting_q <= 1'b1;
    end else if (evicting_q) begin
      pend_q <= pend_q & ~binv_ack;
      if ((pend_q & ~binv_ack) == {NNODE{1'b0}}) evicting_q <= 1'b0;
    end
  end
endmodule

And in VHDL:

-- Representative directory eviction model (VHDL).
library ieee;
use ieee.std_logic_1164.all;
 
entity chi_dir_evict is
  generic ( NNODE : integer := 8 );
  port (
    clk, rst_n      : in  std_logic;
    evict_start     : in  std_logic;
    victim_sharers  : in  std_logic_vector(NNODE-1 downto 0);
    binv_ack        : in  std_logic_vector(NNODE-1 downto 0);
    binv_pending    : out std_logic_vector(NNODE-1 downto 0);
    back_inval_done : out std_logic;
    reusable        : out std_logic
  );
end entity;
 
architecture rtl of chi_dir_evict is
  signal pend_q     : std_logic_vector(NNODE-1 downto 0) := (others => '0');
  signal evicting_q : std_logic := '0';
  signal done       : std_logic;
begin
  done            <= '1' when (evicting_q = '1' and pend_q = (pend_q'range => '0')) else '0';
  binv_pending    <= pend_q;
  back_inval_done <= done;
  reusable        <= done;                 -- reusable ONLY when back-inval complete
 
  process (clk, rst_n)
  begin
    if rst_n = '0' then
      pend_q <= (others => '0'); evicting_q <= '0';
    elsif rising_edge(clk) then
      if evict_start = '1' then
        pend_q <= victim_sharers; evicting_q <= '1';
      elsif evicting_q = '1' then
        pend_q <= pend_q and (not binv_ack);
        if (pend_q and (not binv_ack)) = (pend_q'range => '0') then
          evicting_q <= '0';
        end if;
      end if;
    end if;
  end process;
end architecture;

In all three, reusable asserts only when back_inval_done — every victim sharer has acked its back-invalidation. The DebugLab makes the entry reusable immediately on evict_start, ignoring the pending sharers.

12. Verification View — no reuse with live sharers

The properties enforce inclusion: an entry is reusable only when its sharers are gone.

// Bind to chi_dir_evict.
// 1. The entry is reusable only when NO victim sharer remains pending.
property p_reuse_needs_binv_done;
  @(posedge clk) disable iff (!rst_n)
    reusable |-> (binv_pending == '0);
endproperty
 
// 2. On eviction start, all current sharers become pending back-invalidations.
property p_all_sharers_pending;
  @(posedge clk) disable iff (!rst_n)
    evict_start |=> (binv_pending == $past(victim_sharers) & ~binv_ack);
endproperty
 
// 3. A sharer is never left tracked-but-orphaned: no reuse while a sharer is pending.
property p_no_orphan;
  @(posedge clk) disable iff (!rst_n)
    (binv_pending != '0) |-> !reusable;
endproperty

The system point, beyond the checks:

The eviction path is a sequenced obligation, and that is what makes it harder than lookup or update, which are combinational reads and writes. Eviction cannot complete in a cycle — it must issue back-invalidations, wait for their acks, and only then free the entry, so the entry passes through a multi-cycle EVICTING state where it is neither the old line nor the new. The correctness property is fundamentally temporal: reusable must lag evict_start by however long the back-invalidations take. A design that treats eviction as instantaneous — freeing the entry the moment the victim is chosen — collapses that sequence and breaks inclusion. This is a common shape for RTL correctness bugs: an operation that is logically atomic (evict-and-reuse) is physically multi-cycle (issue, wait, complete), and the bug is doing the second half before the first half finishes. The verification must therefore assert the ordering across time — no reuse until back-invalidation done — not just a same-cycle relationship. Whenever a resource is freed and reallocated, the question to ask is: what must complete before the free is safe? Here it is the back-invalidations; freeing ahead of them is the bug.

• What it proves: no reuse while a victim sharer is pending; all sharers enter the pending set.
• What it does not prove: the back-invalidation messages are correctly delivered — that is the snoop path.
• Bug signature: reusable asserted while binv_pending is non-zero.

13. Testbench — an entry with live sharers must not be reusable yet

Evicts an entry with two sharers and checks it is not reusable until both ack.

module tb_chi_dir_evict;
  localparam NNODE = 8;
  logic clk = 0, rst_n = 0, evict_start;
  logic [NNODE-1:0] victim_sharers, binv_ack, binv_pending;
  logic back_inval_done, reusable;
  int errors = 0;
 
  chi_dir_evict #(.NNODE(NNODE)) dut (.*);
  always #5 clk = ~clk;
 
  initial begin
    evict_start = 0; binv_ack = 0; victim_sharers = 0;
    @(posedge clk) rst_n = 1;
 
    // Evict an entry whose line is held by caches 1 and 3.
    @(posedge clk) begin victim_sharers = 8'b0000_1010; evict_start = 1; end
    @(posedge clk) evict_start = 0;
    #1;
    if (reusable) begin errors++; $display("FAIL reusable with sharers still live!"); end
    else $display("PASS not reusable: sharers pending = %b", binv_pending);
 
    // Cache 1 acks its back-invalidation; still one pending.
    @(posedge clk) binv_ack = 8'b0000_0010;
    @(posedge clk) binv_ack = 0;
    #1;
    if (reusable) begin errors++; $display("FAIL reusable with cache 3 still holding"); end
    else $display("PASS still not reusable: pending = %b", binv_pending);
 
    // Cache 3 acks; now all sharers invalidated -> reusable.
    @(posedge clk) binv_ack = 8'b0000_1000;
    @(posedge clk) binv_ack = 0;
    #1;
    if (!reusable || !back_inval_done) begin errors++; $display("FAIL not reusable after all acks"); end
    else $display("PASS reusable after back-invalidation complete");
 
    if (errors == 0) $display("ALL TESTS PASSED");
    else             $display("%0d FAILURE(S)", errors);
    $finish;
  end
endmodule

Expected output:

PASS not reusable: sharers pending = 00001010
PASS still not reusable: pending = 00001000
PASS reusable after back-invalidation complete
ALL TESTS PASSED

14. DebugLab — reusing a directory entry without back-invalidation

line X tracked; sharer vector = caches {c1, c3} (both hold X)
new line Y maps to X's (full) set -> X's entry chosen as victim
buggy evict: overwrite entry with Y IMMEDIATELY, no back-invalidation
  -> c1, c3 STILL hold X, but the directory entry now describes Y
  -> X is untracked (invisible to the directory)
later: core writes X -> home looks up entry (= Y) -> snoops Y's sharers -> NOT c1/c3
  -> c1, c3 keep stale X -> use it -> corruption
correct: back-invalidate c1, c3 (remove their X copies) BEFORE reusing the entry for Y

15. Common Mistakes

• Reusing without back-invalidation. Assumption: overwrite is enough. Bug: untracked line, stale data (the DebugLab). Prevention: back-invalidate first.
• Reusing before acks return. Assumption: issuing suffices. Bug: a race window. Prevention: reuse only when back-inval done.
• Ignoring the victim's sharer vector. Assumption: the entry is free. Bug: live copies orphaned. Prevention: check for live sharers.
• Treating eviction as instantaneous. Assumption: single-cycle. Bug: sequence collapsed. Prevention: model the EVICTING state.
• Confusing with same-address serialization. Assumption: 16.1 covers it. Bug: different hazard. Prevention: 16.1 is one entry; 16.3 is entry reuse.
• Under-provisioning to force churn. Assumption: back-invals are rare. Bug: constant eviction (Chapter 15.5). Prevention: size the directory.

16. Engineering Checklist

• Implement lookup, update, and eviction for the directory RAM.
• On a full-set miss, select a victim entry.
• Back-invalidate every sharer recorded in the victim entry.
• Make the entry reusable only after back-invalidations complete.
• Never reuse an entry while a victim sharer is pending.
• Maintain inclusion — every cached line tracked by the directory.

17. Key Takeaways

• Directory management is lookup, update, and eviction.
• A full set forces an eviction to track a new line.
• A victim entry may be reused only after its sharers are back-invalidated.
• Reusing it early leaves an untracked cached line — a coherence hole.
• A later write misses the orphaned sharers, and they use stale data.
• Directory correctness is inclusion; the model here is representative.

18. Quick Revision

Directory management. The directory RAM supports lookup (read a line's sharer/state), update (modify it on a transaction), and eviction — and eviction carries the correctness burden. The directory is finite and set-associative, so a new line mapping to a full set must displace a victim entry, which may still describe live cache copies (its sharer vector is non-empty). The invariant: a victim entry may be reused only after its sharers are back-invalidated — their cache copies removed — so nothing untracked remains. The failure to avoid: reusing the entry immediately, overwriting it with the new line without back-invalidating the victim's sharers. Those caches still hold the victim's line, but the directory now records the new line's sharers, so the victim's copies are untracked — a coherence hole. A later write to the victim's address looks up the reused entry, snoops the new sharers, and never snoops the orphaned caches, which keep and use a stale copy. Directory correctness is an inclusion invariant (every cached line tracked), and eviction is the one operation that can break it; back-invalidation restores inclusion by removing the copies as the entry is freed. Reuse must follow back-invalidation, sequenced across the multi-cycle EVICTING state — never precede it. This is the RTL necessity behind Chapter 15.5's performance cost. Representative model; 16.4 covers the cache controller.

Coming Next

Chapter 16.4 — Cache Controllers. The directory tracks caches; the cache controller is the RTL inside each one. Chapter 16.4 covers the cache-controller pipeline — how it services core accesses, snoops, and fills, and why a dirty line being evicted to make room for a fill must be captured into a writeback buffer before the fill overwrites it, or the dirty data is lost.