Transaction Tracking

Module 16 · Chapter 16.5 · CHI RTL Design Thinking

Project thread — 16.4 was the cache controller. 16.5 is the tracker table; 16.6 bounds outstanding requests.

1. Learning Outcomes

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

• Explain that a tracker entry holds a transaction's state for its whole life.
• State that a transaction may gather multiple response/data flits.
• Describe the expected-response mask that records outstanding flits.
• State that an entry is freed only when the mask is cleared and the transaction is complete.
• Diagnose the orphan or alias from freeing an entry on the first flit.
• Implement a representative tracker model in SystemVerilog, Verilog-2001, and VHDL.

2. Why Should I Learn This?

The tracker table is a node's memory of what is in flight — every outstanding transaction has an entry holding its address, type, ID, and which responses it still awaits. Allocation is straightforward (find a free entry, Chapter 16.1); deallocation is where correctness is won or lost, because freeing an entry is declaring the transaction done — and declaring it done too early is a bug with two nasty faces.

A transaction often expects several flits — a completion and data, or multiple snoop responses. If the entry is freed on the first flit, a later flit for the same transaction arrives to find no entry — it is an orphan, dropped or misrouted, and the original transaction hangs waiting for a completion that was silently lost. Worse, if the freed slot has been reallocated to a new transaction, the late flit is applied to the wrong transaction — aliasing one transaction's response onto another and corrupting both. The fix is an expected-response mask: free the entry only when every expected flit has arrived. This chapter is the tracker and the deallocation discipline that keeps late flits from becoming orphans or aliases.

3. Key Terms

4. Previous Chapter Connection

This chapter is the deallocation half of the tracker whose allocation you saw in Chapter 16.1. There, allocation was gated by the address hazard (one active transaction per line); here, deallocation is gated by the expected-response mask (all flits in). Both keep the tracker an accurate model of what is in flight — one at the front (don't allocate a conflict), one at the back (don't free too early).

The multi-flit nature of a transaction is something you have seen throughout: a read returns a completion plus data (Chapter 13.1), a snoop gathers multiple snoop responses (Chapter 9.3), data arrives over several beats (Chapter 13.1). Each of those is an expected flit the tracker must wait for. This chapter ties them together: the tracker's job is to know exactly which flits a transaction still owes, and to hold the entry until they all arrive — the accounting that makes "the transaction is complete" a precise, checkable condition.

5. Core Concept — free only when the mask is clear

A tracker entry holds a transaction's state and an expected-response mask; the entry is deallocated only when the mask is fully cleared and the transaction is complete.

• The entry persists for the whole life. From allocation to completion, the entry holds the transaction's address, type, TxnID, and its expected-response mask.
• A transaction expects multiple flits. The mask records which response/data flits are still outstanding — a completion, data beats, multiple snoop responses.
• Each flit clears its bit. As an expected flit arrives, its mask bit is cleared (accumulation). The transaction is complete when the mask reaches zero.
• Deallocate only when done. The entry is freed only when the mask is all-clear and the completion is acknowledged — never on the first flit while others are outstanding.

The synthesis:

A tracker entry holds a transaction's state and an expected-response mask of the flits it still owes. Each arriving flit clears its bit; the transaction is complete when the mask is zero. The entry is deallocated only then. Freeing it on the first flit leaves later flits to arrive as orphans (dropped — the transaction hangs) or, if the slot was reallocated, as aliases applied to the wrong transaction — corrupting both.

6. Engineering Mental Model — a delivery-tracking clipboard

Think of a receiving desk tracking multi-parcel orders on clipboards (tracker entries).

• Each order's clipboard lists all the parcels expected for that order (the expected-response mask) — say a box, an envelope, and a tube. The clipboard stays on the desk until all three arrive.
• As each parcel arrives, the clerk ticks it off the clipboard (clears a mask bit). Only when every item is ticked is the order complete and the clipboard filed away (deallocated).
• The bug — filing early. Suppose the clerk files the clipboard the moment the first parcel (the box) arrives. When the envelope shows up later, there is no clipboard for it — the clerk does not know which order it belongs to. It is set aside, lost (orphaned), and the order is never actually completed.
• The worse bug — a reused clipboard. If that filed clipboard was wiped and reused for a new order, the late envelope is ticked onto the new order's clipboard — the new order now shows an item it never expected (aliased), and both orders are wrong.

The clipboard is the tracker entry; the checklist is the expected-response mask. File it only when every item is ticked, or late parcels become lost or misfiled.

7. Engineering Diagram — the tracker table

The deallocation gate is the critical stage: it frees the entry only when the mask is zero and the transaction is complete. Until then, every late flit finds its entry and clears its bit. The DebugLab moves the free before the gate — on the first flit.

8. When an Entry May Be Freed

The deallocation condition, spelled out.

The rule to carry: an entry is freed only when the transaction owes nothing more. The expected-response mask is the ledger of what is owed; while any bit is set, a flit is still coming, and freeing the entry would strand it. Only when the mask is all-clear — every expected response and data flit collected — and the completion is acknowledged is the transaction truly done and the entry safe to reuse. Freeing on any earlier condition risks an orphan or, after reallocation, an alias.

9. Why Premature Deallocation Corrupts

The two failure modes of freeing too early.

• A transaction owes multiple flits. Many transactions expect more than one flit — a completion and data, or several snoop responses. The entry must survive until all arrive.
• Freeing early strands the rest. Free the entry on the first flit and the remaining flits have no entry to land in.
• Orphan (no reallocation yet). A late flit finds its entry gone — it is dropped or misrouted. The original transaction never completes (it was waiting for that flit) — a hang.
• Alias (slot reallocated). If the freed slot was reallocated to a new transaction, the late flit is applied to that new transaction — clearing a bit it does not own, or delivering data to the wrong requester. Both transactions are corrupted.

The point to carry:

Premature deallocation is a lifetime bug — the entry's lifetime is cut shorter than the transaction's — and lifetime bugs are insidious because they only bite when the timing lines up: the freed-early entry is only dangerous once a late flit actually arrives, and catastrophic only once the slot is reallocated before that flit. Under light load, flits arrive close together and the window is tiny, so the bug hides; under heavy load, with reordering and contention stretching the gap between a transaction's flits, the window widens and the orphans and aliases appear. The correct mental model is that a tracker entry is a resource whose lifetime must exactly cover the transaction's — allocated no later than the first flit could arrive, freed no earlier than the last flit has arrived. The expected-response mask is what makes "the last flit has arrived" a precise condition rather than a guess. This is the same lifetime discipline as the directory entry (16.3) and the cache victim (16.4): a resource must not be reused until its current occupant is completely finished with it — and "completely" here means the mask is zero.

10. Tracking a Multi-Flit Transaction — right and wrong

A read transaction expecting a completion and two data beats — a 3-flit transaction.

1. Allocate with mask = 3 flits. The entry is allocated; the expected-response mask marks completion + beat0 + beat1 outstanding.
2. Completion arrives. Its mask bit clears; beat0 and beat1 still outstanding. Mask non-zero — keep the entry.
3. Beat0 arrives. Its bit clears; beat1 still outstanding. Mask non-zero — keep the entry.
4. Beat1 arrives. Its bit clears; mask is now zero. All flits collected — the transaction is complete.
5. Deallocate. With the mask clear and completion acknowledged, the entry is freed. Every flit found its entry; the requester got all its data.
6. Wrong — free at step 2. Freeing on the completion strands beat0 and beat1. They arrive as orphans (data dropped — the requester never gets its line, a hang) or, if the slot was reused, are written as beats of the wrong transaction — corrupting it.

The mask held the entry until all three flits arrived; freeing on the first lost the data beats. The DebugLab is step 6.

11. RTL / Hardware View — the tracker with an expected-response mask

Each arriving flit clears its mask bit; the entry frees only when the mask is zero. Representative.

// Representative transaction tracker (educational).
// Each entry holds an EXPECTED-RESPONSE mask of the flits the transaction still owes.
// An arriving flit clears its bit. The entry is deallocated ONLY when the mask is fully
// cleared AND the completion is acknowledged -- never on the first flit, which would
// orphan the rest (or, after reallocation, alias them onto a new transaction).
module chi_tracker #(parameter NFLIT = 4) (
  input  logic              clk, rst_n,
  input  logic              alloc,          // allocate this entry
  input  logic [NFLIT-1:0]  expected_init,  // which flits this transaction expects
  input  logic [NFLIT-1:0]  flit_arrived,   // one-hot: an expected flit just arrived
  input  logic              cmpl_ack,        // completion acknowledged
  output logic [NFLIT-1:0]  expected_mask,   // flits still outstanding
  output logic              can_dealloc,     // safe to free the entry
  output logic              active
);
  logic [NFLIT-1:0] mask_q;
  logic             active_q;
 
  assign expected_mask = mask_q;
  assign active        = active_q;
  // Free ONLY when every expected flit is in (mask==0) AND completion is acknowledged.
  assign can_dealloc   = active_q && (mask_q == '0) && cmpl_ack;
 
  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      mask_q <= '0; active_q <= 1'b0;
    end else if (alloc) begin
      mask_q   <= expected_init;   // set the expected-response mask
      active_q <= 1'b1;
    end else if (active_q) begin
      mask_q <= mask_q & ~flit_arrived;   // clear the bit of each arriving flit
      if (can_dealloc) active_q <= 1'b0;  // free only when fully complete
    end
  end
endmodule

The same behavior in Verilog-2001:

// Representative transaction tracker (Verilog-2001).
module chi_tracker #(parameter NFLIT = 4) (
  input                  clk, rst_n, alloc, cmpl_ack,
  input  [NFLIT-1:0]     expected_init, flit_arrived,
  output [NFLIT-1:0]     expected_mask,
  output                 can_dealloc, active
);
  reg [NFLIT-1:0] mask_q; reg active_q;
  assign expected_mask = mask_q;
  assign active        = active_q;
  assign can_dealloc   = active_q & (mask_q == {NFLIT{1'b0}}) & cmpl_ack;
 
  always @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      mask_q <= {NFLIT{1'b0}}; active_q <= 1'b0;
    end else if (alloc) begin
      mask_q <= expected_init; active_q <= 1'b1;
    end else if (active_q) begin
      mask_q <= mask_q & ~flit_arrived;
      if (can_dealloc) active_q <= 1'b0;
    end
  end
endmodule

And in VHDL:

-- Representative transaction tracker (VHDL).
library ieee;
use ieee.std_logic_1164.all;
 
entity chi_tracker is
  generic ( NFLIT : integer := 4 );
  port (
    clk, rst_n    : in  std_logic;
    alloc         : in  std_logic;
    expected_init : in  std_logic_vector(NFLIT-1 downto 0);
    flit_arrived  : in  std_logic_vector(NFLIT-1 downto 0);
    cmpl_ack      : in  std_logic;
    expected_mask : out std_logic_vector(NFLIT-1 downto 0);
    can_dealloc   : out std_logic;
    active        : out std_logic
  );
end entity;
 
architecture rtl of chi_tracker is
  signal mask_q   : std_logic_vector(NFLIT-1 downto 0) := (others => '0');
  signal active_q : std_logic := '0';
  signal dealloc  : std_logic;
begin
  dealloc       <= '1' when (active_q = '1' and mask_q = (mask_q'range => '0')
                             and cmpl_ack = '1') else '0';
  expected_mask <= mask_q;
  can_dealloc   <= dealloc;
  active        <= active_q;
 
  process (clk, rst_n)
  begin
    if rst_n = '0' then
      mask_q <= (others => '0'); active_q <= '0';
    elsif rising_edge(clk) then
      if alloc = '1' then
        mask_q <= expected_init; active_q <= '1';
      elsif active_q = '1' then
        mask_q <= mask_q and (not flit_arrived);
        if dealloc = '1' then active_q <= '0'; end if;
      end if;
    end if;
  end process;
end architecture;

In all three, can_dealloc requires mask_q == 0 and cmpl_ack — the entry lives until every expected flit is in. The DebugLab frees on any flit, ignoring the mask.

12. Verification View — no free with flits outstanding

The properties enforce the lifetime: no deallocation while the mask is non-zero.

// Bind to chi_tracker.
// 1. The entry is never deallocated while any expected flit is still outstanding.
property p_no_free_with_pending;
  @(posedge clk) disable iff (!rst_n)
    can_dealloc |-> (expected_mask == '0);
endproperty
 
// 2. An arriving flit clears exactly its bit (accumulation is monotone toward zero).
property p_flit_clears_bit;
  @(posedge clk) disable iff (!rst_n)
    (active && |flit_arrived) |=> ((expected_mask & $past(flit_arrived)) == '0);
endproperty
 
// 3. An active entry stays active until fully complete (no premature free).
property p_active_until_complete;
  @(posedge clk) disable iff (!rst_n)
    (active && expected_mask != '0) |=> active;
endproperty

The system point, beyond the checks:

The tracker's expected_mask turns "is this transaction done?" from a judgment into a countable fact, and that shift is what makes deallocation safe. A design that frees "when it looks done" — on a completion, on the first data flit, on a timeout — is making a judgment that can be wrong whenever a transaction's flits are more numerous or more spread out than the designer assumed. The mask removes the judgment: the transaction is done exactly when the mask is zero, by construction, because the mask enumerates precisely what was expected at allocation. This is a general principle for lifetime management in hardware: represent the completion condition as explicit accounted state, not as an inferred event, so that "safe to free" is a read of that state rather than a guess about timing. The cost is a few bits per entry (the mask); the benefit is that orphans and aliases become impossible rather than merely unlikely. And it composes with the allocation-side hazard (16.1): the mask ensures the entry lives long enough, while the hazard check ensures it was allocated at the right time — together they pin the entry's lifetime to exactly cover the transaction.

• What it proves: no deallocation with flits outstanding; each flit clears its bit; active until complete.
• What it does not prove: the expected_init mask matches what the transaction truly owes — a spec-derived value.
• Bug signature: can_dealloc (or a free) asserted while expected_mask is non-zero.

13. Testbench — an entry must survive until all flits arrive

Tracks a 3-flit transaction and checks the entry frees only after the last flit.

module tb_chi_tracker;
  localparam NFLIT = 4;
  logic clk = 0, rst_n = 0, alloc, cmpl_ack;
  logic [NFLIT-1:0] expected_init, flit_arrived, expected_mask;
  logic can_dealloc, active;
  int errors = 0;
 
  chi_tracker #(.NFLIT(NFLIT)) dut (.*);
  always #5 clk = ~clk;
 
  // Guard: the entry must never deallocate while flits are still outstanding.
  always @(posedge clk) if (rst_n && can_dealloc && expected_mask != 0) begin
    errors++; $display("FAIL dealloc with mask=%b outstanding -> orphan/alias!", expected_mask);
  end
 
  initial begin
    alloc = 0; cmpl_ack = 0; flit_arrived = 0; expected_init = 0;
    @(posedge clk) rst_n = 1;
 
    // Allocate a transaction expecting 3 flits: completion(0) + beat0(1) + beat1(2).
    @(posedge clk) begin alloc = 1; expected_init = 4'b0111; end
    @(posedge clk) alloc = 0;
 
    // Completion arrives -> mask still has the two data beats -> must NOT free.
    @(posedge clk) begin flit_arrived = 4'b0001; cmpl_ack = 1; end
    @(posedge clk) flit_arrived = 0;
    #1;
    if (can_dealloc) begin errors++; $display("FAIL freed after completion, beats pending"); end
    else $display("PASS held: mask=%b (beats outstanding)", expected_mask);
 
    // Beat0 arrives -> still one beat left.
    @(posedge clk) flit_arrived = 4'b0010;
    @(posedge clk) flit_arrived = 0;
    #1;
    if (can_dealloc) begin errors++; $display("FAIL freed with beat1 outstanding"); end
    else $display("PASS held: mask=%b", expected_mask);
 
    // Beat1 arrives -> mask clear -> now free.
    @(posedge clk) flit_arrived = 4'b0100;
    @(posedge clk) flit_arrived = 0;
    #1;
    if (!can_dealloc) begin errors++; $display("FAIL not freed after all flits"); end
    else $display("PASS all flits in (mask=%b) -> deallocate", expected_mask);
 
    if (errors == 0) $display("ALL TESTS PASSED");
    else             $display("%0d FAILURE(S)", errors);
    $finish;
  end
endmodule

Expected output:

PASS held: mask=0110 (beats outstanding)
PASS held: mask=0100
PASS all flits in (mask=0000) -> deallocate
ALL TESTS PASSED

14. DebugLab — freeing a tracker entry on the first response

transaction T expects: completion + beat0 + beat1  (3 flits)
buggy tracker: frees T's entry on the FIRST flit (completion)
  -> beat0, beat1 still in flight, entry GONE
  -> beat0 arrives: no entry for T -> ORPHAN (dropped) -> T hangs (missing data)
  -> if slot reallocated to T2 before beat1: beat1 applied to T2
     -> T2 gets a stray data beat / a cleared bit it never owned -> T2 corrupted
correct: expected_mask = {compl,beat0,beat1}; clear per flit; free only when mask==0

15. Common Mistakes

• Freeing on the first flit. Assumption: one flit means done. Bug: orphans/aliases (the DebugLab). Prevention: free when the mask clears.
• No expected-response mask. Assumption: completion implies all flits. Bug: data beats stranded. Prevention: track every expected flit.
• Ignoring the completion ack. Assumption: mask-clear is enough. Bug: freeing before confirmation. Prevention: require the ack too.
• Reusing a slot too soon. Assumption: freed means safe. Bug: alias onto the new transaction. Prevention: lifetime covers the transaction.
• Assuming single-flit transactions. Assumption: one response each. Bug: multi-flit transactions break. Prevention: size the mask to the max flits.
• Confusing with allocation hazard. Assumption: 16.1 covers it. Bug: alloc vs dealloc. Prevention: 16.1 allocates; 16.5 deallocates.

16. Engineering Checklist

• Hold each transaction's state in a tracker entry for its whole life.
• Record the flits it owes in an expected-response mask.
• Clear a mask bit as each expected flit arrives.
• Deallocate only when the mask is zero and the completion is acknowledged.
• Never free an entry while a flit is outstanding.
• Size the mask to the maximum flits any transaction can owe.

17. Key Takeaways

• A tracker entry holds a transaction's state for its whole life.
• A transaction may owe multiple response/data flits.
• An expected-response mask records which flits are still outstanding.
• The entry is freed only when the mask is clear and the completion is acknowledged.
• Freeing on the first flit orphans later flits (hang) or aliases them (corruption).
• The entry's lifetime must cover the transaction; the model here is representative.

18. Quick Revision

Transaction tracking. A tracker entry (CHI's MSHR) holds an outstanding transaction's state — address, type, TxnID, and an expected-response mask of the flits it still owes — for its whole life, from allocation (Chapter 16.1) to completion. Because a transaction often gathers multiple flits (a completion and data beats, or several snoop responses), the entry must persist until every expected flit arrives: each arriving flit clears its mask bit, and the transaction is complete when the mask is zero. The entry is deallocated only when the mask is fully cleared and the completion is acknowledged — never on the first flit. The failure to avoid: freeing on the first flit, which cuts the entry's lifetime shorter than the transaction's. A still-outstanding later flit then finds no entry — an orphan (dropped/misrouted → the original transaction hangs) — or, if the slot was reallocated, is applied to the new transaction — an alias that corrupts both. The expected-response mask makes "all flits in" a precise, countable condition, so deallocation reads accounted state instead of guessing at timing. This is the deallocation-side counterpart of 16.1's allocation hazard, and the same lifetime discipline as the directory entry (16.3) and cache victim (16.4): reuse a resource only when its occupant is completely done. Representative model; 16.6 covers bounding outstanding requests.

Coming Next

Chapter 16.6 — Outstanding Requests. The tracker table is finite, so the number of in-flight requests must be bounded; the last chapter of the module closes that loop. Chapter 16.6 covers outstanding requests — how a node bounds its in-flight count to the tracker and transaction-ID capacity, and why an issue gate must check for a free tracker entry and a unique ID, not just a link credit, before issuing.