Owner Tracking

Module 11 · Chapter 11.4 · Directory-Based Coherency

Project thread — 11.3 encoded the sharer set. This chapter stores the owner — one ID, not a set. 11.5 quantifies the directory's scaling win.

1. Learning Outcomes

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

• Contrast how the directory stores the owner (one ID) versus the sharer set (a bitmask).
• Describe the owner ID and owner-valid fields of a directory entry.
• State when memory owns the line versus a cache — the owner-valid bit.
• State the consistency invariant — the owner is always a recorded sharer.
• Diagnose the failure when the owner ID names a cache not in the sharer set.
• Implement a representative owner store in SystemVerilog, Verilog-2001, and VHDL.

2. Why Should I Learn This?

The owner is the cache the home turns to for the latest data and the eventual writeback (Chapter 10.3). The directory must store who that is — and because it is exactly one cache, it stores it very differently from the sharer set. A set of many caches needs a bitmask; a single owner needs only a pointer — an owner ID of a handful of bits. That compactness is why owner tracking is cheap, and knowing the representation is knowing another piece of the directory's storage.

The subtlety is that this one small field must stay consistent with the sharer set. An owner is a holder, so the owner ID must name a cache that is also in the sharer set — two records that must never contradict. When they do, the home is handed a lie: it fetches dirty data from a cache the directory itself does not list as holding the line. This chapter is about storing the owner compactly and keeping that one pointer honest against the set beside it.

3. Key Terms

4. Previous Chapter Connection

Chapter 10.3 established that a line has one owner — memory, or a single cache in UD/SD. Chapter 11.3 showed how the directory encodes the sharer set. This chapter is the companion: how the directory encodes the owner.

The two records differ in shape. The sharer set is a group, so it needs a set-shaped encoding (a bitmask, or coarse groups). The owner is a singleton, so it needs only a pointer — an owner ID — plus a bit for whether a cache owns it at all. This chapter stores that pointer, and ties it back to Chapter 10.3's consistency requirement from the directory's angle: the owner ID and the sharer set are two fields of one entry, and they must agree — the owner must be in the sharer set.

5. Core Concept — one pointer, bound to the sharer set

The directory stores the owner as a compact pointer, and that pointer must stay consistent with the sharer set.

• The owner is one cache. Unlike the sharer set (many caches), the owner is exactly one — so it is stored as an owner ID, a pointer of log2(N) bits, not a bitmask.
• The owner-valid bit. A single bit records whether a cache owns the dirty line (valid) or memory owns it (clear, for a clean line). The owner ID is meaningful only when owner-valid is set.
• The entry's fields. A directory entry holds, per line: the sharer bitmask, the owner ID, the owner-valid bit, and the line state. Owner and sharers are two fields of the same entry.
• Owner-in-sharers. The binding invariant: when a cache owns the line, the owner ID must name a cache that is in the sharer set — an owner is always a holder (Chapter 10.3). The two fields must agree.

The synthesis:

The directory stores the owner as an owner ID (a pointer, log2(N) bits) plus an owner-valid bit (a cache owns, or memory does) — far cheaper than a set, because the owner is a singleton. The owner ID and the sharer set are fields of one entry and must stay consistent: the owner must be one of the recorded sharers. A directory that names an owner outside its sharer set contradicts itself.

6. Engineering Mental Model — the highlighted name on the list

Back to the front desk's sign-out list — now with one name highlighted.

• The list is everyone currently borrowing the document (the sharer set). Any number of names.
• One name is highlighted to mark the person responsible for the annotated master copy — the owner. Instead of a second list, the desk just keeps a note of which name is highlighted: "owner = row 3." That note is the owner ID — a pointer, not a copy.
• There is also a flag for "no one is responsible — the master is in the archive" (memory owns): the owner-valid bit, clear.
• The rule that keeps this honest: the highlighted name must be on the list. If the note says "owner = row 3" but row 3 is blank — that borrower already returned their copy — the desk is pointing at someone who is not a borrower. It would then ask a non-borrower for the annotated master.

A pointer into the list is cheap, but only meaningful while it points at a real entry. Keep the highlighted name on the list.

7. Engineering Diagram — a directory entry's fields

Three fields per entry: the sharer bitmask (a set), the owner ID (a pointer), and the owner-valid bit (cache versus memory). The owner ID is one pointer into the set the bitmask describes — and it must point at a cache the bitmask lists.

8. Owner Storage versus Sharer Storage

The two records, stored differently for their different shapes.

The rule to carry: store a set as a bitmask, but store a singleton as a pointer — the owner ID is far cheaper than a second bitmask. The owner-valid bit distinguishes a cache owner from memory ownership. And the owner ID is not independent: it must point at a cache the sharer bitmask also has set — the two fields describe the same reality and must agree.

9. The Owner-in-Sharers Invariant

The consistency rule binding the owner to the sharers deserves its own statement.

• An owner is a holder. A cache that owns the dirty line necessarily holds it (Chapter 10.3) — so it is in the sharer set. Owner and sharer are not separate memberships.
• So the owner ID must be a set sharer bit. When owner-valid is set, sharers[owner_id] must be 1. The pointer must land on a recorded holder.
• Update both together. Any event changing ownership (transfer, upgrade) or sharing (a sharer evicts) must keep the invariant — never clear a sharer bit while the owner ID still points at it, and never set an owner ID for a non-sharer.
• Violation is self-contradiction. If the owner ID names a cache not in the sharer set, the directory asserts two incompatible things: "this cache does not hold the line" and "this cache owns its dirty data." The home cannot act coherently on a contradiction.

The point to carry:

The owner ID is a pointer into the sharer set, and a pointer is only sound while its target is valid. The directory's two fields — set and pointer — are a single description of the line's holders, with the owner distinguished among them; keeping the pointer inside the set is what makes them one consistent picture. Break the invariant and the home is asked to fetch dirty data from a cache the directory's own set says is not a holder — an instruction that cannot be satisfied, ending in a stale read or a dropped fetch. The compactness of a pointer is bought with the duty to keep it pointing at a real sharer.

10. Reading the Entry — owner and sharers together

Read a directory entry and act on it.

1. The entry. Sharer bitmask = RN0 and RN2 hold the line; owner-valid = set; owner ID = RN2.
2. Check consistency. Is RN2 in the sharer set? Yes — the invariant holds. The entry is self-consistent.
3. A read needs the latest data. The home routes the data fetch to the owner, RN2 — which the sharer set confirms is a holder. RN2 supplies the dirty data.
4. A write invalidates all. The home snoops the sharer set (RN0 and RN2), collecting the dirty data from the owner (RN2) with PassDirty.
5. Consistent throughout. Every action used the owner ID and the sharer set together, and they agreed.

The fetch in step 3 was safe because the owner (RN2) was a recorded sharer. Had the owner ID said RN1 — not in the sharer set — step 3 would fetch dirty data from a cache the directory lists as a non-holder: the DebugLab.

11. RTL / Hardware View — an owner store

The owner store holds the owner ID and valid bit and checks consistency against the sharer bitmask. Representative.

// Representative directory owner store (educational).
// The owner is stored as an ID (pointer) plus a valid bit. owner-valid clear means
// MEMORY owns the (clean) line. The binding invariant: when a cache owns, the owner
// ID must be a SET bit in the sharer bitmask -- the owner is always a recorded sharer.
module chi_owner_store #(parameter N = 4, parameter IDW = 2) (
  input  logic [N-1:0]   sharers,     // the sharer bitmask
  input  logic [IDW-1:0] owner_id,    // pointer to the owning cache
  input  logic           owner_valid, // 1 = a cache owns; 0 = memory owns
  output logic           owner_is_memory,
  output logic           owner_in_sharers, // the owner ID is a set sharer bit
  output logic           consistent        // entry is self-consistent
);
  assign owner_is_memory  = !owner_valid;
  // Is the pointed-to cache actually a recorded sharer?
  assign owner_in_sharers = sharers[owner_id];
  // Consistent if memory owns (no cache owner) OR the owner is a recorded sharer.
  assign consistent = owner_is_memory || owner_in_sharers;
endmodule

The same behavior in Verilog-2001:

// Representative directory owner store (Verilog-2001).
module chi_owner_store #(parameter N = 4, parameter IDW = 2) (
  input  [N-1:0]   sharers,
  input  [IDW-1:0] owner_id,
  input            owner_valid,
  output           owner_is_memory,
  output           owner_in_sharers,
  output           consistent
);
  assign owner_is_memory  = !owner_valid;
  assign owner_in_sharers = sharers[owner_id];
  assign consistent = owner_is_memory || owner_in_sharers;
endmodule

And in VHDL:

-- Representative directory owner store (VHDL).
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
 
entity chi_owner_store is
  generic ( N : integer := 4; IDW : integer := 2 );
  port (
    sharers          : in  std_logic_vector(N-1 downto 0);
    owner_id         : in  std_logic_vector(IDW-1 downto 0);
    owner_valid      : in  std_logic;
    owner_is_memory  : out std_logic;
    owner_in_sharers : out std_logic;
    consistent       : out std_logic
  );
end entity;
 
architecture rtl of chi_owner_store is
  signal ois : std_logic;
begin
  ois <= sharers(to_integer(unsigned(owner_id)));
  owner_is_memory  <= not owner_valid;
  owner_in_sharers <= ois;
  consistent <= '1' when (owner_valid = '0') or (ois = '1') else '0';
end architecture;

All three flag consistent only when memory owns the line or the owner ID points at a set sharer bit — the owner-in-sharers invariant. The DebugLab shows the failure when the pointer lands outside the set.

12. Verification View — the owner is always a recorded sharer

The properties that keep owner storage sound: a cache owner is a recorded sharer, and owner-valid distinguishes memory ownership.

// Bind to chi_owner_store.
// 1. When a cache owns the line, its owner ID must be a set sharer bit.
property p_owner_in_sharers;
  @(*) owner_valid |-> sharers[owner_id];
endproperty
 
// 2. Owner-valid clear means memory owns — no cache owner claimed.
property p_memory_when_invalid;
  @(*) (!owner_valid) |-> owner_is_memory;
endproperty
 
// 3. Consistency holds exactly when memory owns or the owner is a sharer.
property p_consistent_def;
  @(*) consistent == (owner_is_memory || owner_in_sharers);
endproperty

The system point, beyond the checks:

A directory entry is a small database record, and like any record with a foreign key, its pointer field must reference a valid row. The owner ID is a foreign key into the sharer set: it names one cache among the holders, so it is only meaningful while that cache is actually recorded as a holder. This is why owner and sharer updates cannot be independent — they are a referential-integrity pair, and an event that changes one may invalidate the other. The compact owner-ID representation is a real storage win, but it inherits the classic hazard of pointers: a dangling reference. Keeping the owner ID inside the sharer set is exactly the discipline of never letting the pointer dangle.

• What it proves: a cache owner is a recorded sharer; owner-valid means memory when clear.
• What it does not prove: the sharer set itself is complete — that is Chapters 10.4, 11.3.
• Bug signature: owner-valid set with the owner ID pointing at a clear sharer bit — a dangling owner.

13. Testbench — consistent and contradictory entries

Drives consistent and contradictory owner/sharer combinations and checks the flags.

module tb_chi_owner_store;
  localparam N = 4, IDW = 2;
  logic [N-1:0] sharers;
  logic [IDW-1:0] owner_id;
  logic owner_valid, owner_is_memory, owner_in_sharers, consistent;
  int errors = 0;
 
  chi_owner_store #(.N(N), .IDW(IDW)) dut (.*);
 
  task automatic check(input logic [N-1:0] sh, input logic [IDW-1:0] oid, input logic ov,
                       input logic exp_cons, input string name);
    sharers = sh; owner_id = oid; owner_valid = ov; #1;
    if (consistent !== exp_cons) begin
      errors++; $display("FAIL %s: cons=%0b mem=%0b in=%0b", name, consistent, owner_is_memory, owner_in_sharers);
    end else $display("PASS %s: cons=%0b (mem=%0b in=%0b)", name, consistent, owner_is_memory, owner_in_sharers);
  endtask
 
  initial begin
    check(4'b0101, 2'd2, 1'b1, 1'b1, "sharers {RN0,RN2}, owner RN2 -> consistent");
    check(4'b0101, 2'd0, 1'b1, 1'b1, "sharers {RN0,RN2}, owner RN0 -> consistent");
    check(4'b0101, 2'd1, 1'b1, 1'b0, "owner RN1 NOT a sharer -> CONTRADICTION");
    check(4'b0000, 2'd0, 1'b0, 1'b1, "clean line, memory owns -> consistent");
 
    if (errors == 0) $display("ALL TESTS PASSED");
    else             $display("%0d FAILURE(S)", errors);
    $finish;
  end
endmodule

Expected output:

PASS sharers {RN0,RN2}, owner RN2 -> consistent: cons=1 (mem=0 in=1)
PASS sharers {RN0,RN2}, owner RN0 -> consistent: cons=1 (mem=0 in=1)
PASS owner RN1 NOT a sharer -> CONTRADICTION: cons=0 (mem=0 in=0)
PASS clean line, memory owns -> consistent: cons=1 (mem=1 in=0)
ALL TESTS PASSED

14. DebugLab — an owner ID outside the sharer set

directory entry for line L:
  sharer bitmask = RN0, RN2   (RN1 bit CLEAR)
  owner_valid    = 1
  owner_id       = RN1        <-- points at a cache NOT in the sharer set
home needs dirty data -> routes fetch to owner RN1
  RN1 is not recorded as a holder (and may not hold L) -> no valid data
  -> stale memory served / fetch dropped

15. Common Mistakes

• Owner ID outside the sharer set. Assumption: owner and sharers are independent. Bug: dangling owner (the DebugLab). Prevention: owner-in-sharers, updated together.
• Evicting a sharer that is the owner. Assumption: any sharer can leave. Bug: the owner pointer dangles. Prevention: move ownership before removing the owner from the set.
• Ignoring owner-valid. Assumption: the owner ID is always meaningful. Bug: reading a stale owner for a clean line. Prevention: owner-valid gates the ID.
• Storing the owner as a bitmask. Assumption: reuse the sharer encoding. Bug: wasteful. Prevention: a singleton is a pointer.
• Assuming memory never owns. Assumption: a cache always owns. Bug: mishandling clean lines. Prevention: owner-valid clear means memory owns.
• Updating one field, not both. Assumption: partial updates are fine. Bug: drift. Prevention: keep the entry self-consistent.

16. Engineering Checklist

• Store the owner as an owner ID (pointer) plus an owner-valid bit.
• Use owner-valid to distinguish a cache owner from memory ownership.
• Keep the owner ID inside the sharer set — the owner is a recorded sharer.
• Update the owner ID and sharer bitmask together on any change.
• Move ownership before removing the current owner from the sharer set.
• Verify each entry is self-consistent — no dangling owner.

17. Key Takeaways

• The owner is one cache, so the directory stores it as an owner ID (a pointer) plus an owner-valid bit.
• Owner-valid clear means memory owns the (clean) line; set means a cache owns the dirty line.
• The owner ID is far cheaper than a set — log2(N) bits, not N.
• The binding invariant: the owner is always a recorded sharer — sharers[owner_id] is set.
• An owner ID outside the sharer set is a self-contradiction — the home fetches dirty data from a non-holder.
• Store a pointer, keep it inside the set; the model here is representative.

18. Quick Revision

Owner tracking. The directory records the owner — the single cache holding a line's dirty data — as an owner ID (a pointer of log2(N) bits) plus an owner-valid bit, far cheaper than the sharer set's bitmask because the owner is a singleton. Owner-valid clear means memory owns the clean line; set means a cache owns the dirty line, named by the owner ID. The owner ID and the sharer bitmask are two fields of one directory entry and must stay consistent: the owner is always a recorded sharer, so when owner-valid is set, sharers[owner_id] must be set too — a pointer into the set. Update the owner ID and the sharer set together; an owner ID that dangles outside the sharer set is a self-contradiction — the directory says a cache both does not hold the line and owns its dirty data — and the home, trusting the owner field, fetches dirty data from a non-holder, serving stale or dropping the fetch. One pointer, kept inside the set. Representative model; 11.5 quantifies why directories trade storage for snoop bandwidth.

Coming Next

Chapter 11.5 — Directory Scalability Benefits. You have seen how the directory stores sharers and the owner; the next chapter quantifies why it is worth the storage. Chapter 11.5 makes the scaling argument explicit — directories trade storage for snoop bandwidth, paying directory memory to avoid broadcasting to every cache — and shows why, as core counts rise, that trade goes overwhelmingly in the directory's favour, and why under-provisioning the storage repays the saving in wasted bandwidth.