Cache Ownership Transfer

Everything in this module has been building to one question, and it is the hardest in CXL.cache:

What must the system prove before writable ownership of a line moves?

1. Ownership Is Not Data Movement

The instinct is that transferring ownership means copying a line from A to B. It does not, and the distinction is the chapter.

A line's bytes may exist in several places at once. Several caches may hold copies; memory holds one too. Nothing about that is a problem — copies are how caching works.

What must be unique is permission to modify. Ownership transfer is therefore not a data-movement operation with a permission side-effect; it is a permission operation that sometimes has a data side-effect:

A transfer that copies the line and updates a state field has done the easy half. The hard half is proving that nobody else can still write it, and that proof is what this chapter builds.

2. The One-Sentence Model

Revoke before grant. Writable ownership may be granted only once every other holder that could conflict has been revoked and has said so, and only once the authoritative value is safe — so a transfer is a proof obligation with two independent conditions, and a permission that moves before either is discharged has not been transferred, it has been duplicated.

Call it the proof obligation. The grant is not the transfer; the proof is.

3. What This Chapter Owns

4. The Exchange

Architectural. The arrows are obligations, not named messages — this repository's source policy does not permit naming CXL.cache messages.

The final arrow is the whole chapter. It is the last thing to happen, and everything above it is the proof that it is safe.

5. The Ownership State Machine

Teaching model — these are not CXL.cache state encodings. Three things to read off it.

The two transient states are where the proof happens, and nobody holds writable permission in either. Not the old owner, not the new one. That is not a gap to be minimised; it is the correctness property, and §8 shows it as a flat pair of zeros in the waveform.

Every commit arrow carries the same two conditions, joined by AND. One is not enough, and §9 is about what happens when the second is dropped.

Every transient has an abort arrow. A transfer that cannot finish must return the line to a defined owner, or the line is locked forever — §11.

6. Teaching-model boundary

7. RTL 1 — Who Must Be Revoked

  // The requester is not on its own invalidation list, and an agent that
  // holds nothing is not either.
  assign self_bit = (4'd1 << requester);
  assign mask     = INCLUDE_SELF ? sharers : (sharers & ~self_bit);

=== EXP8: who must be revoked ===
  sharers=1101 requester=0 : correct mask=1100 targets=2 | include-self mask=1101
  the requester was excluded from its own list       : ok
  the include-self variant waits on itself forever   : ok
  only the requester holds it : targets=0 zero-target transfers=1
  zero targets is legitimate and fast                : ok
  and the fast path was counted separately           : ok

Two results worth separating.

The requester must not be on its own list. It will never acknowledge its own invalidation, so a transfer that waits for it waits forever — a hang produced by an off-by-one in a mask.

Zero targets is legitimate and fast. If nobody else holds the line, there is nothing to revoke and the transfer can commit as soon as the value is secured. Counting that path separately matters because a workload with mostly zero-target transfers has cheap ownership movement, and one with many sharers does not — and the difference is invisible in an average latency.

8. RTL 2 — The Bitmap Is Not Enough

This is the chapter's central module and the place it goes beyond 3.4.

A set-based tracker handles duplicates correctly:

=== EXP2: a duplicate acknowledgement ===
  set-based : awaiting=0100 remaining=1 duplicates=1 busy=1 epoch=2
  a duplicate ack was idempotent: still waiting on 2 : ok
  and it was classified as a duplicate, not progress : ok
  count-based variant : remaining=0
  the count-based variant declared itself complete   : ok

The count-based variant is complete after two acknowledgements from the same agent, because a counter knows how many and not who. That is 3.4's argument, confirmed.

Now the question a bitmap cannot answer. A line may be transferred many times. Suppose a transfer completes, a new one begins, and an acknowledgement from the previous transfer arrives late:

  // An acknowledgement is usable only if it belongs to THIS transfer and
  // names an agent this transfer is actually waiting on.
  assign fresh    = NO_EPOCH ? 1'b1 : (ack_epoch == epoch_q);
  assign expected = awaiting_q[ack_from];

=== EXP3: a LATE acknowledgement from a finished transfer ===
  new transfer epoch=3 (previous was 2), awaiting=1010
  stale ack from agent 1, epoch 2 : correct remaining=2 stale=1
                                    no-epoch remaining=1
  the epoch tag rejected the straggler               : ok
  without epochs it satisfied an unrelated obligation: ok

The straggler belonged to epoch 2 and arrived during epoch 3. Agent 1 is legitimately on the new transfer's required list — so the bitmap sees a bit it is waiting for, from an agent it is waiting on, and clears it. An obligation was discharged by a message that had nothing to do with it.

Bit 2 means "agent 2". It does not mean "agent 2, for this transfer". The epoch supplies the missing half of the identity, and without it the transfer can commit while a real holder has not yet answered — which is the single-writer violation this whole chapter exists to prevent.

Note what is not wrong here. The bitmap is still right about duplicates, still names the non-responders, and is still better than a count. It is simply incomplete once a line can be transferred more than once — which is always.

9. Waveform — A Complete Transfer, With a Duplicate and a Straggler

Read device_writable and host_writable together across cycles 2 to 7: both are zero for six consecutive cycles. That flat pair is the single-writer invariant made visible — during the proof, the right to modify belongs to nobody, and the system is strictly less capable than before the transfer began.

That is the cost of correctness, and it is why transfer latency matters: every cycle in the transient is a cycle in which the line cannot be written by anyone.

The measured tail confirms the two rejections:

two_writers=0 grant_before_acks=0 stale=1 dup=1 transfers=1

10. RTL 3 — Two Conditions, Joined by AND

  // The single condition that authorises a commit. GRANT_EARLY removes it.
  assign commit    = GRANT_EARLY ? 1'b1 : (acks_complete && data_secured);

=== EXP4: ownership commits only when both conditions hold ===
  device asked : state=1 transient=1 dev_writable=0 host_writable=0
  nobody holds writable permission mid-transfer      : ok
  nothing complete yet : correct state=1 | grant-early state=2
  the correct FSM stayed transient                   : ok
  the grant-early variant already committed          : ok
  acks done, data NOT secured : state=1 | grant-early state=2
  acks alone are not sufficient to commit            : ok
  data secured too : state=2 dev_writable=1 transfers=1
  both conditions met, ownership committed           : ok
  never two writable owners                          : ok

Acknowledgements alone are not sufficient. The middle case is the one designs get wrong: every holder has been revoked, so no one else can write the line — and the old owner's modified value has not yet been handed over. Committing there produces a line whose new owner cannot supply its own current value.

Permission and data are separate conditions with separate evidence, and the AND is not a formality.

11. RTL 4 — Permission May Not Move Ahead of the Value

=== EXP6: permission may not move ahead of the value ===
  old owner dirty : data_secured=0 | ignore-dirty secured=1
  not secure while the value is still owed           : ok
  the ignore-dirty variant moved permission anyway   : ok
  after handover  : data_secured=1 with-data transfers=1
  the value was handed over before permission moved  : ok
  the ignore-dirty variant lost the only copy        : ok

Note the asymmetry with a clean old owner: nothing is owed, data_secured is immediately true, and the transfer costs only the revocation. Transfers from a clean owner are cheap; transfers from a modified owner carry a data movement, and the counters separate them because the two have different costs and different causes.

12. RTL 5 — A Transfer That Cannot Finish

      if (abort) begin
        n_abort_q <= n_abort_q + 8'd1;
        // Naming the non-responders is what makes the abort actionable.
        blame_q   <= awaiting;

=== EXP7: an abandoned transfer must not lock the line forever ===
  agent 2 never answered : aborts=1 blame=0100 max_age=13
  the transfer was aborted rather than left hanging  : ok
  and it named the agent that did not answer         : ok
  worst age was exactly 13 = limit plus the abort cycle: ok
  without a bound the line stayed locked             : ok

This is the worst failure in the chapter if it is missing. An abandoned transfer leaves the line permanently transient, so every future request for it is deferred forever — the line becomes unusable for the life of the system, and nothing reports why.

The abort must also name the non-responders. blame=0100 says agent 2; without it the recovery knows a transfer failed and not which agent to reset or quiesce.

The measured worst age is 13, not 12. The age advances on the cycle the abort fires, so the peak includes that cycle. Asserting the exact value rather than a bound is what pins that off-by-one — see §14.

12b. RTL 6 — Block the Line, Not the Cache

  // Only the SAME line is blocked. Blocking everything would serialise the
  // whole cache behind one transfer.
  assign conflict = line_transient && (req_line == busy_line);

=== EXP5: a transient line blocks its own line only ===
  same line, transient : correct accept=0 | no-block accept=1
  the conflicting request was deferred               : ok
  the no-block variant let it through                : ok
  different line       : accept=1
  an unrelated line proceeded concurrently           : ok

Both halves are properties. Accepting a conflicting request on a transient line lets a second transaction act on a line whose ownership is mid-proof. Blocking unrelated lines is not a safety bug at all — it is a throughput disaster, serialising the entire cache behind one transfer, and a mutation that does it is caught by a test for the thing that should still work.

13. The Proof, as Structures

Two arrows enter the FSM as evidence and one as an escape. The design is legible as exactly that: two independent proofs that must both arrive, and a bound that ends the attempt if either never does.

14. Quantitative Reasoning — What a Transfer Costs

Illustrative. Decompose it:

T_transfer ≈ serialisation
           + mask computation
           + slowest required acknowledgement
           + value handover (only if the old owner is modified)
           + commit

The term that matters is the third, and it is a maximum, not a sum:

With N sharers each taking L cycles: parallel is L, serial is N × L. The difference is the entire scalability argument for ownership transfer — a design whose acknowledgements serialise degrades linearly in sharer count, and one whose acknowledgements are parallel does not degrade at all in the common case.

That is why the zero-target counter from §6 is worth having: it distinguishes transfers with no revocation at all — the cheapest case — from transfers whose cost is set by whoever is slowest.

Measured, using this chapter's teaching latencies:

=== EXP9: every started transfer completes or aborts ===
  started=24 completed=15 aborted=6 with-sharers=8 with-dirty=5
  transfer counts matched an independent oracle      : ok
  no transfer finished without starting              : ok
  mean latency 12 cycles, worst 20

Transfers from a modified owner cost 20 against 8 for clean ones — two and a half times, entirely the value handover.

15. Assertions

Icarus Verilog 13.0 does not support concurrent SVA here, so every property is synthesisable checker logic verified in simulation. The assert property form states the intent.

Safety

Liveness

The first is the one the no-timeout variant violates. Note it is stated as ends, not completes — an abort is a legitimate ending, and conflating the two is how a design ends up with no bound at all.

Performance goals

16. Mutation Testing

Twenty-two mutations. Twenty-two killed.

The first run scored 16 of 22. Two of the six survivors taught something.

"An unexpected agent's ack clears a bit" survived a test that looked like it covered it. The test drove an acknowledgement from an agent that was not on the required list and asserted remaining was unchanged — and it was unchanged, on both designs, because clearing an already-clear bit is invisible in the bitmap. The observable difference is classification: the correct design counts it as a duplicate, the mutant counts it as progress.

  and it was classified as a duplicate, not progress : ok
  exactly one genuine acknowledgement was counted     : ok

A state change with no state change is still a bug, and only the counters can see it.

"Max transfer age lags by one" survived a bound. For the third time in this batch, an assertion said "no more than" where the design has an exact answer. Pinning it to 13 killed the mutation — and pinning it required first understanding why 13 rather than 12, which is itself worth knowing.

The other four were the now-familiar shapes: three checkers unreachable by construction, needing either a deliberately broken variant or an instance reserved for illegal stimulus.

17. Verification Plan

The coverage cross is sharer count against acknowledgement behaviour against owner cleanliness: zero / one / many sharers, crossed with prompt / duplicate / stale / missing acknowledgements, crossed with clean / modified old owner. The stale column is the one that does not exist in a single-transfer test plan, and it is where the epoch bug lives.

18. Silicon Observability

Stale acknowledgement count is the one that would otherwise be invisible. In a correct design it should be rare and non-zero — stragglers happen. A rising rate means the fabric is reordering more than expected or a partner is retransmitting, and it is the earliest warning that the epoch mechanism is doing real work rather than sitting idle.

19. Debug Lab

// Ownership requested — hand it over.
if (state == TO_DEVICE) state <= DEVICE_OWNED;

  nothing complete yet : correct state=1 | grant-early state=2
  the grant-early variant already committed          : ok

assign commit = acks_complete && data_secured;
if (commit && !acks_complete) grant_before_acks_err <= 1'b1;

if (ack_valid && awaiting_q[ack_from]) awaiting_q[ack_from] <= 1'b0;   // no epoch

  stale ack from agent 1, epoch 2 : correct remaining=2 stale=1
                                    no-epoch remaining=1

assign fresh = (ack_epoch == epoch_q);
// ... and epoch_q advances on every new transfer
if (ack_valid && !fresh) n_stale_q <= n_stale_q + 8'd1;   // count, do not apply

if (ack_valid) ack_count <= ack_count - 1;   // how many, not who

  set-based : remaining=1 duplicates=1
  count-based variant : remaining=0

if (ack_valid && fresh && awaiting_q[ack_from]) awaiting_q[ack_from] <= 1'b0;
else if (ack_valid && fresh)                    n_dup_q <= n_dup_q + 8'd1;

assign commit = acks_complete;   // data not considered

  old owner dirty : data_secured=0 | ignore-dirty secured=1
  the ignore-dirty variant lost the only copy        : ok

assign commit = acks_complete && data_secured;
if (data_secured && owed_q) value_lost_err <= 1'b1;

assign accept = req;   // transient state not consulted

  same line, transient : correct accept=0 | no-block accept=1

assign conflict = line_transient && (req_line == busy_line);
assign accept   = req && !conflict;

// Wait for acknowledgements.
if (all_acked) commit();     // and if they never arrive?

  agent 2 never answered : aborts=1 blame=0100 max_age=13
  without a bound the line stayed locked             : ok

assign abort = busy && (age_q >= LIMIT);
if (abort) begin blame_q <= awaiting; n_abort_q <= n_abort_q + 8'd1; end

assign mask = sharers;   // includes the requester

  sharers=1101 requester=0 : correct mask=1100 | include-self mask=1101
  the include-self variant waits on itself forever   : ok

assign mask = sharers & ~(1 << requester);
if (mask[requester]) self_invalidate_err <= 1'b1;

sharers_m[idx] <= sharers | (1 << new_owner);   // owner added to the sharer set

  abuse instance flagged an owner listed as a sharer: ok

if (wr_owned && wr_sharers[wr_owner]) owner_also_sharer_err <= 1'b1;

20. Design Review

1. What exactly is proven before a grant? If the answer is only "the acknowledgements arrived", the data condition is missing.
2. Does the acknowledgement tracker record who, or how many?
3. Can an acknowledgement from a previous transfer be distinguished from a current one?
4. Is the requester excluded from its own invalidation set?
5. Is anyone writable during the transient? Nobody should be.
6. What bounds a transfer, and does the abort name the non-responders?
7. Does a transient line block only its own line?
8. Do the acknowledgements proceed in parallel or serially? That decides how the design scales with sharer count.
9. Can the metadata represent a contradiction, and is that checked at the write?
10. What happens on reset mid-transfer?

21. How This Appears in Real Engineering

Architecture. Whether acknowledgements are collected in parallel decides whether ownership transfer scales with sharer count. It is a topology and fabric decision as much as a protocol one.

RTL. The epoch is three or four bits and it is the difference between a design that works and one that fails rarely and inexplicably. It is also the field most likely to be removed by someone optimising for area who has not seen the failure.

DV. The stale-acknowledgement case does not exist in a single-transfer test plan. It has to be constructed deliberately, and it is the highest-value test in this chapter.

Post-silicon. The abort blame mask and the stale count are the two registers that turn "the machine hung on one address" into a specific agent and a specific mechanism.

Performance. Transfer latency is a maximum over acknowledgements, so the tail agent sets the cost. Optimising the mean does nothing.

22. Common Misconceptions

23. Interview Reasoning

24. Exercises

1. Analysis. A machine reports transfers=10000, aborts=3, stale_acks=0, and one address is permanently unusable. Explain why stale_acks=0 is itself suspicious, and name the two faults consistent with all four facts.

2. Design. Extend the transfer to support a downgrade — the owner keeps a clean copy rather than being fully invalidated. State what changes in the required set, what changes in the commit condition, and which existing assertion must be weakened.

3. RTL task. Make the epoch two bits wide and construct the sequence that defeats it. State the minimum epoch width for a given maximum message lifetime, and the counter that would warn you the margin is thin.

4. DV task. Write the coverage cross for ownership transfer, then explain why two of its points cannot be reached by a test plan organised around a single transfer.

5. Debug task. A design shows rare single-writer violations only on lines transferred more than once per microsecond. Give your investigation order and the one counter that confirms the cause.

6. Design review. A colleague proposes removing the epoch to save four bits per tracker entry, arguing that acknowledgements cannot outlive their transfer because the fabric is in-order. Give the strongest version of that argument, then name what must be true system-wide for it to hold and what happens the first time it does not.

25. Summary

Revoke before grant. The grant is not the transfer; the proof is.

• Ownership is a right, not a location. Bytes may be in many places; permission to modify is in exactly one.
• Nobody holds writable permission during the transfer — measured as both writable signals flat at zero through the entire transient.
• A set beats a count: duplicates are idempotent and the vector names who did not answer.
• A set is still not enough. Bit N means "agent N", not "agent N, for this transfer" — so a straggler from a finished transfer can discharge an unrelated obligation. An epoch supplies the missing identity.
• Two conditions, joined by AND: every required holder revoked, and the authoritative value secured. Acknowledgements alone commit a line whose new owner cannot supply its own value.
• The requester is not on its own invalidation list, or the transfer waits forever — and only on the upgrade path, which hides it.
• A transient blocks its own line only. Blocking the cache is safe and unusable.
• Every transfer must be bounded, and the abort must name the non-responders. An unbounded transfer makes one address permanently unusable and reports nothing.
• Latency is a maximum over acknowledgements, not a sum — if they parallelise. That single property decides how ownership transfer scales with sharer count.
• Measured: transfers from a modified owner cost 20 cycles against 8 for clean ones.
• Verification lesson: a state change with no state change is still a bug. A mutation survived a test that drove exactly the right stimulus, because the effect was visible only in the classification counters.

That completes Module 8 — CXL.cache. A device may borrow host memory; the host coordinates; the device must remain answerable; the accelerator around it must keep making progress; and moving the right to write requires proving that nobody else still has it.