Cache Coherency Review

Module 12 spent five chapters making sure a unit of memory had exactly one owner, and built an isolation guard specifically to enforce it.

This module removes that restriction on purpose.

1. The Engineering Problem — Two Copies Of One Truth

Everything in Module 12 rested on a simplification: one allocation, one owner, and a guard that made any other access a security event. That is a clean model and it is not how a cache works.

The moment two agents may both hold a copy of the same memory, three questions appear that a pool never had to answer.

Who is allowed to write? If two agents both hold a copy and both write, there are two truths and no way to reconcile them. Something has to make writing exclusive without making reading exclusive, because reading is the common case and serialising it would destroy performance.

What happens to the other copies? A write that leaves stale copies alive has not written anything meaningful — it has created a system where the answer to a read depends on which agent asks. That is not a performance problem; it is a correctness problem with no error signal.

And when is a permission actually yours? Asking for exclusive access is not the same as having it. Between the request and the grant there is a window in which other agents still hold copies, and anything that treats the request as the grant will write into a system that still disagrees with it.

Coherency is the machinery that answers those three questions. It is not "keeping caches in sync" — that phrase describes a symptom and hides every mechanism. Coherency is a set of permissions, an invariant those permissions preserve, and a protocol that moves permission between agents without ever violating the invariant.

2. The One-Sentence Model

A cache line is not data you have. It is permission you hold. Permission has a scope — read, or read and write — a holder, and a revocation path. The data is the easy part; the permission is the protocol.

Call it permission, not possession. Every state name in every coherency protocol ever built is shorthand for "what am I allowed to do with this line, and who else is allowed to do what".

3. What This Chapter Owns

Module 13 has a sharp internal split and one important forward boundary.

Deferred:

This chapter is deliberately a review, and it is not a soft one. It establishes the vocabulary the rest of the module depends on — permission, invariant, upgrade, downgrade, sharer, owner, transient — and it spends as much effort on what coherency does not promise as on what it does, because every one of those three misconceptions produces a real bug that no coherency protocol will catch for you.

4. Teaching-Model Boundary

Nothing in this chapter is a CXL message, opcode, encoding or timing. There are no snoop message names, no channel names, no state encodings, no cache line size attributed to the specification, and no claim about how any of this is represented on a CXL link.

What is transferable is the model: permissions, the invariant, and the obligations a protocol must discharge to move permission safely. Those are the same whether the agents sit on one die, on two sockets, or on opposite ends of a CXL link — which is exactly why 13.2 can take this vocabulary and ask what changes when the link is long.

5. RTL 1 and 2 — Four States Are Four Permissions

The classic four-state model, written as what it actually is: a permission encoding.

// Teaching model of GENERAL cache coherency theory (Papamarcos & Patel, 1984).
// This is NOT "the CXL protocol"; CXL does not define these state names as a
// wire protocol.
//   I = no permission        S = read, shared      E = read+write, exclusive, clean
//   M = read+write, dirty
module mesi_line (
  input  logic clk, rst_n,
  input  logic       lcl_rd, lcl_wr, evict,      // this agent's own actions
  input  logic       rem_rd, rem_wr,             // another agent's action, seen as a snoop
  input  logic       others_have,                // any other agent already holds a copy
  output logic [1:0] state,
  output logic       can_read, can_write, dirty,
  output logic       need_wb, need_inval, silent_upgrade,
  output logic [7:0] n_wb, n_inval, n_silent
);
  localparam logic [1:0] I = 2'd0, S = 2'd1, E = 2'd2, M = 2'd3;
 
  // Permission is DERIVED from state. It is never stored separately: a second
  // copy of the truth is a second thing that can be wrong.
  assign can_read  = (st_q != I);
  assign can_write = (st_q == E) || (st_q == M);
  assign dirty     = (st_q == M);

Read that permission table as the definition and the state names as labels for it:

E is the state most people cannot justify, and it is the whole reason MESI beats the three-state protocol it replaced. E means I have the only copy and it is unmodified. A write from E therefore needs no interconnect traffic at all — nobody else has a copy to invalidate. Measured, that upgrade is silent:

  E -> M                     : silent_upgrades=1 invalidations=0
  S -> M                     : invalidations=1

Same local operation, same resulting state, and one of them costs a broadcast while the other costs nothing. A read that arrives when nobody else holds the line lands in E precisely so that a later write can be free — measured, a read miss with no sharers gives state=2 (E), and the same read with sharers present gives state=1 (S).

The permission checker is separate from the state machine on purpose, and it distinguishes two denials:

  // The two denials are different problems. No copy means fetch the line;
  // read-only means the line is here and permission must be UPGRADED, which
  // costs an invalidation the fetch does not.
  assign deny_no_copy   = acc_valid && (line_state == I);
  assign deny_read_only = acc_valid && acc_is_write && (line_state == S);

Measured over the run: no_copy=1, read_only=1, counted separately. Merging them tells an engineer that an access failed and nothing about whether the fix is a fetch or an upgrade — and those have completely different costs.

6. Waveform — An Upgrade Is Not Instant

Transcribed from the printed cycle trace of the upgrade model in section 9.

Read acks_seen against grant. The grant does not rise when the request is made, when the invalidations are sent, or when the first acknowledgement returns. It rises when acks_seen reaches acks_need, and not before.

That gap is the single most important thing in this chapter. A design that treats the request as the permission will write into a system where three other agents still believe they hold a valid readable copy — and every one of them will keep serving reads from it.

7. RTL 3 — The Invariant: Single Writer, Multiple Readers

Everything above exists to preserve one property.

  // Two separate failures, because they mean different things. Two writers is a
  // protocol bug; a writer coexisting with a reader is a stale-data bug. A
  // single "coherency violation" flag cannot tell an engineer which.
  assign two_writer_err         = (n_writers > 3'd1);
  assign writer_with_reader_err = (n_writers == 3'd1) && (n_readers != 3'd0);
  assign swmr_ok                = !two_writer_err && !writer_with_reader_err;

SWMR: at most one agent may hold write permission for a line at any time, and while one does, no other agent may hold read permission. Measured across four agents:

The two illegal rows are counted separately, measured at two_writer_err=1 and writer_with_reader_err=1 in their respective cases. They are different bugs. Two writers means the protocol handed out exclusive permission twice — a grant-side failure. A writer coexisting with a reader means an invalidation did not land or was not waited for — a revocation-side failure. An engineer chasing the first looks at the arbitration; chasing the second, at the acknowledgement path.

Note what SWMR does not say. It says nothing about how long a permission is held, in what order permissions are granted, or what happens to lines other than this one. It is a per-line safety property and nothing more, which is why sections 11 through 13 exist.

8. RTL 4 — Coherence Order

The second invariant is about values rather than permissions.

  // The line has exactly one current value at any point in the order. A read
  // that returns anything else is a stale read, which is the failure the whole
  // protocol exists to prevent.
  assign rd_val = cur_val;

Every write to a line takes a position in a single order, and a read returns the value of the most recent write in that order. Measured over three writes from three different agents: value 0xC3 at position 3, last written by agent 1, with a read after each write returning exactly what was last written.

The testbench models this with an explicit growing history and reads its tail, while the design keeps a single current value — two representations of one invariant, compared on every operation.

The subtlety worth naming: the order is per line, and it is not a wall-clock order. Two agents writing the same line are serialised into one sequence; two agents writing different lines are not serialised at all. That distinction is section 11 and it is where most misunderstanding lives.

9. RTL 5 — No Silent Upgrade

Read permission never becomes write permission while another agent still holds a copy.

  // The requester's own bit never counts as a sharer to invalidate.
  always_comb begin
    others = sharer_vec;
    others[req_agent] = 1'b0;
  end
  logic [2:0] need;
  assign need = {2'b0,others[0]} + {2'b0,others[1]} + {2'b0,others[2]} + {2'b0,others[3]};
 
  // The grant is released ONLY when every acknowledgement is in. Granting on
  // the request, or on a partial count, is the classic coherency bug.
  assign upgrade_grant = busy_q && (seen_q >= need_q);

Three behaviours, all measured:

The last row is the E case from section 5 arriving from the other direction: with nothing to invalidate, the upgrade is free. The middle row matters because a duplicate acknowledgement is not a harmless extra — if the count can be inflated, it can reach the target before the real acknowledgements arrive, and the grant becomes premature.

An in-flight upgrade is also not restarted by a later request: measured, its acknowledgement target stays at 3 and its progress at 1 when a second request for a different sharer set arrives mid-flight.

10. RTL 6 — Dirty Data Must Survive Eviction

  assign wb_required    = evict_req && (line_state == M);
  // A clean eviction completes immediately; a dirty one only when the data is
  // safely written back.
  assign evict_complete = (evict_req && (line_state != M)) || (pend_q && wb_done);

Measured: 1 writeback, 2 silent evictions. A line in E or S may be dropped with no traffic at all, because memory already holds the same bytes. A line in M may not, because the cache holds the only copy of that value in the system.

This asymmetry is why E and M are separate states rather than one "writable" state. Collapsing them would force a writeback on every eviction of a line that was never written — a large and permanent cost to avoid tracking one bit.

data_lost_err catches the case that actually loses data: a second eviction arriving while a dirty writeback is still pending. Measured at 1.

11. RTL 7 — Coherency Is Per Line

This is the most misunderstood property in the subject, so it is modelled rather than asserted.

// Coherency is PER LINE. This model exists to show what coherency does NOT give
// you: it says nothing about the order in which writes to DIFFERENT lines become
// visible. That is memory consistency, a separate property.
module per_line_scope #(parameter int DLY_A = 4, parameter int DLY_B = 1) (
  input  logic wr_a, wr_b, observe,
  output logic a_visible, b_visible, reorder_obs,
  output logic [7:0] n_observe, n_reorder
);
  // A reorder is: A was written first, B is already visible, A is not yet.
  assign reorder_obs = observe && a_written && vis_b && !vis_a;

Agent 0 writes line A, then line B one cycle later. Line A takes four cycles to become visible to agent 1; line B takes one. Both lines are perfectly coherent throughout. Measured at the moment the skew is open:

  per-line scope : A visible=0  B visible=1  reorder observed=1

The observer sees the second write and not the first. No coherency rule was broken. Each line independently returned the most recent value written to it, which is the entire promise. The promise says nothing about the relationship between two lines.

This is the boundary between coherency and consistency, and it is why memory-ordering models and barrier instructions exist at all. If coherency implied ordering, no architecture would need a fence.

The model is also careful about what counts as a reorder: with B written and nothing written before it, reorder_obs reads 0. A claim that two operations were reordered requires that there was an earlier operation to reorder against.

12. RTL 8 — False Sharing: Perfectly Correct, Pathological

  // Every write by an agent that does not currently own the line forces a
  // transfer -- regardless of which byte it touches.
  assign transfer = wr_en && have_q && (wr_agent != own_q);
  // The invariant is never broken. That is the point: this is a PERFORMANCE
  // pathology with perfect correctness.
  assign swmr_violated = 1'b0;

Two agents alternate writes to different bytes of the same line. Measured over ten writes:

Nine transfers to do ten bytes of work, and the correctness flag never moves — sampled deliberately while a transfer is in flight, not only when the bus is idle.

The two agents are not sharing data. They are sharing a line, and coherency operates on lines. The fix is a data-layout change — padding the two variables into separate lines — and no amount of protocol work will help, because the protocol is behaving exactly as specified.

This is the cleanest example in the curriculum of a performance property that looks like a correctness property, and telling them apart is what the SWMR counter is for.

13. RTL 9 — The Atomicity Gap

  // A lost update: both agents write back a value derived from the SAME read,
  // so two increments produce one.
  assign lost_update = w0_ok && w1_ok && (t0_q == t1_q);

Two agents each read a location, add one, and write it back. Every read returns the latest value in the coherence order. Every write is properly serialised. Measured:

  atomicity gap  : two increments -> memory=1  lost_update=1

Two increments produced one, and no coherency rule was broken at any point. Coherency guarantees each individual access sees the right value; it says nothing about a sequence of accesses being indivisible.

With a reservation — the read takes one, and any intervening write breaks it — the second write is rejected rather than silently overwriting:

  with reservation: memory=2, rejected write did not count (3 -> 3)

The discriminator there is the update count, not the memory value. Both agents derive the same number, so a wrongly-accepted write leaves the value looking correct; only the counter reveals that a write landed which should not have. That took a deliberate test to expose, and it is a general lesson about choosing what to observe.

14. RTL 10 — What To Count

      // Peak sharer count is latched, never tracked: a fan-out spike that has
      // passed is exactly the event that explains an invalidation storm.
      if (sample_en) begin
        n_samples <= n_samples + 8'd1;
        if (readers > peak_sharers) peak_sharers <= readers;
      end
      // A hard alarm: the system's model of itself is wrong.
      if (swmr_bad) swmr_alarm <= 1'b1;

Measured: sharer counts of 3, 5 and 1 sampled in that order leave peak_sharers=5, and the SWMR alarm is sticky — set by a single event and still set afterwards.

Both properties matter for the same reason. The events worth knowing about in a coherency system are transient: a fan-out spike lasts as long as one upgrade, and an invariant violation may last one cycle. A counter that reports the current value describes neither.

15. Quantitative Reasoning

Invalidation fan-out. An upgrade from S costs one invalidation per other sharer:

messages = sharers - 1        (the requester is not invalidated)

Measured: four agents holding the line means 3 acknowledgements, and the upgrade cannot complete until all three arrive. An upgrade from E costs 0. That is the entire economic argument for the E state.

Upgrade latency is the tail, not the mean. The measured trace takes 4 cycles from request to grant with three sharers responding immediately. The real cost is set by the slowest responder, because the grant waits for the last acknowledgement rather than the average one.

False-sharing amplification.

transfers / writes = 9 / 10 = 90%

Two agents alternating on one line transfer it on nearly every write. With the same two agents on separate lines the figure is zero, for identical useful work.

The silent-upgrade fraction is the number that tells you whether E is earning its bit:

silent / (silent + invalidating)

Measured over the model run: 1 silent upgrade and 1 invalidating upgrade. In a real workload a high fraction means most writes touch lines nobody else holds — the migratory pattern E exists to serve — and a low fraction means the working set is genuinely shared and E is buying little.

Cost of a lost update: one. Two increments produced a value of 1 rather than 2. The error does not scale with contention; it appears with contention, which is why it survives light testing.

16. Assertions

Presented as SystemVerilog for the reader and executed as procedural checker logic, because the available simulator does not run concurrent assertions — see section 18.

Single writer, multiple readers.

property p_swmr;
  @(posedge clk) disable iff (!rst_n)
    (n_writers <= 1) && ((n_writers == 1) -> (n_readers == 0));
endproperty

Write permission implies read permission.

property p_write_implies_read;
  @(posedge clk) disable iff (!rst_n)  can_write |-> can_read;
endproperty

A read returns the latest write in the coherence order.

property p_coherence_order;
  @(posedge clk) disable iff (!rst_n)  rd_en |-> (rd_val == cur_val);
endproperty

No upgrade completes before every invalidation is acknowledged.

property p_no_premature_upgrade;
  @(posedge clk) disable iff (!rst_n)  upgrade_grant |-> (acks_seen >= acks_needed);
endproperty

A dirty line is never dropped without writeback.

property p_no_data_loss;
  @(posedge clk) disable iff (!rst_n)
    (evict_req && (line_state == M)) |-> wb_required;
endproperty

A clean line needs no writeback.

property p_clean_evict_free;
  @(posedge clk) disable iff (!rst_n)
    (evict_req && (line_state != M)) |-> evict_complete;
endproperty

An E to M upgrade is silent.

property p_e_upgrade_silent;
  @(posedge clk) disable iff (!rst_n)
    (lcl_wr && (state == E)) |-> (silent_upgrade && !need_inval);
endproperty

False sharing never violates the invariant.

property p_false_sharing_is_not_a_bug;
  @(posedge clk) disable iff (!rst_n)  transfer |-> !swmr_violated;
endproperty

123 assertion sites across the ten models and the waveform trace. All pass.

17. Mutation Testing

64 mutations injected, 64 killed, 0 surviving.

Representative kills:

Nine mutations did not die on the first run. None was a missing checker.

Three of those are worth naming. The false-sharing one was a sampling error: the correctness flag was only read when no transfer was in flight, so a design that wrongly reported false sharing as a violation looked clean. And two of the reservation mutations were equivalent under the original stimulus — because both agents derive the same value, a wrongly-accepted write leaves memory looking correct. Only the update counter distinguishes them, and only after adding the mirror case where agent 0 writes first.

The taxonomy has now held for ten consecutive batches.

18. Verification Strategy

Tool reality. Icarus Verilog 13.0 is the only simulator present. It does not execute concurrent SVA, so every property in section 16 is presented for the reader and checked procedurally. It also does not enforce unique/priority, rejects an enum-valued ternary without a cast, and rejects a part-select of an expression — including a part-select of a function call's result, which cost a compile here and was fixed with an explicit temporary.

Every run is bounded by a hard timeout, because a runaway loop hangs rather than failing and a PASS/FAIL testbench cannot classify a hang.

Independent oracles. §17's rule is that the testbench must not re-run the design's own state machine.

• mesi_line — design: one four-valued state enum. Oracle: two independent permission booleans plus a dirty flag.
• coherence_order — design: one current value. Oracle: an explicit growing history, read at the tail.
• upgrade_guard — design: a needed/seen counter pair. Oracle: literal expected counts stated per case.
• false_sharing — design: an owner register. Oracle: expected transfer count per alternation pattern.
• atomicity_gap — design: reservations and temporaries. Oracle: expected update count, not value.

The MESI oracle is the important one. The design stores what state the line is in; the oracle stores what the agent is allowed to do, which is what the state is for. A bug that maps a state to the wrong permission is invisible to an oracle that stores the same enum.

Coverage. The points that matter are state, access direction, sharer count, and the concurrency shape of the cycle. The crosses worth driving are state crossed with access direction — the full permission table, which is what catches a mis-mapped state — and sharer count crossed with upgrade, which is the only way to reach both the zero-invalidation and multi-acknowledgement paths. A cross of agent index against state is noise; the design treats agents symmetrically.

19. Synthesis and Implementation Reality

Two bits per line, and that is the cheap part. Four states need two bits of tag-adjacent storage per cache line. For a large cache that is real but unremarkable area, and it is not where coherency costs land.

The snoop path is the timing problem. Every incoming snoop must look up the line, determine the state, and produce a response — on a path parallel to the normal tag lookup and often with a tighter deadline, because the requester is stalled waiting. Practical designs duplicate the tag array so snoops do not contend with local accesses, which doubles the tag storage to buy a port.

The acknowledgement counter scales with the sharer count. A design tracking up to N sharers needs a counter of log2(N)+1 bits per outstanding upgrade, plus somewhere to record which upgrade an arriving acknowledgement belongs to. That identity is what 13.4 turns into transient state.

Broadcast does not scale and a directory costs storage. Invalidating by broadcast is simple and its traffic grows with the agent count; a directory records who holds each line and turns a broadcast into a multicast, at the cost of a sharer vector per line. That trade is the reason directory-based coherency exists, and it is a scale decision rather than a correctness one.

The permission derivation must stay combinational from state. The models here derive can_read and can_write from the state register rather than storing them. Storing them is one flop cheaper to read and introduces a second copy of the truth that can drift — the same class of defect Module 12 found in its derived counters.

No gate counts are offered. The structural claims — two bits per line, a duplicated tag array for snoop bandwidth, a counter per outstanding upgrade, a sharer vector per line for a directory — hold regardless of process.

20. Silicon Observability

The most valuable pair is transfers-per-line against the SWMR alarm. High transfers with a clean alarm is false sharing and the fix is in the data layout. High transfers with a dirty alarm is a protocol bug. They look identical on a bandwidth graph and have nothing in common.

21. Debug Lab

  SWMR : two_writer_err=1 writer_with_reader_err=0

assign two_writer_err         = (n_writers > 3'd1);
assign writer_with_reader_err = (n_writers == 3'd1) && (n_readers != 3'd0);

assign upgrade_grant = busy_q && (seen_q >= need_q);

  false sharing : transfers=9 of 10 writes (90%)  swmr_violated=0

// Nothing in the protocol changes. The fix is data layout: pad the two
// variables so they occupy separate lines.
assign swmr_violated = 1'b0;   // and it stays 0 -- this was never a correctness bug

  atomicity gap : two increments -> memory=1  lost_update=1

assign w0_ok = wr0 && (!atomic_mode || resv0_q);   // the write needs a live reservation
if (w0_ok) begin ... resv1_q <= 1'b0; end          // and it breaks everyone else's

  per-line scope : A visible=0  B visible=1  reorder observed=1

// No RTL fix exists in the coherency protocol. The producer must order its two
// writes explicitly; the model here only makes the reordering observable.
assign reorder_obs = observe && a_written && vis_b && !vis_a;

  evictions : writebacks=1 silent=2 data_lost_err=1

assign wb_required    = evict_req && (line_state == M);
assign evict_complete = (evict_req && (line_state != M)) || (pend_q && wb_done);

  duplicate ack : ack_overflow_err=1

if (ack && (seen_q <  need_q)) seen_q <= seen_q + 3'd1;
if (ack && (seen_q >= need_q)) ack_overflow_err <= 1'b1;

  E -> M : silent_upgrades=1 invalidations=0
  S -> M : invalidations=1

if (st_q == I) begin
  if (others_have) st_n = S; else st_n = E;   // E when nobody else holds it
end

22. Design Review

What a reviewer should attack first.

Whether permission is derived or stored. If can_write is a register rather than a function of the state, there are two copies of the truth and they will drift. Ask to see the assignment.

The grant term. It must be a function of the acknowledgement count. If the request appears anywhere in it, the design writes while sharers still hold copies.

What happens to a surplus acknowledgement. If it is absorbed, the count can be inflated and the wait can be short-circuited. It must be an alarm.

Whether E exists and is reachable. A design with E in the enum and no path into it has paid for the bit and gets none of the benefit. Ask for the silent-upgrade fraction on a private workload.

The eviction path, split by state. A dirty eviction that can complete before its writeback loses data, and it is the only failure here that destroys information.

Whether the two SWMR violations share a counter. They are grant-side and revocation-side failures and a merged flag sends every investigation to the wrong half.

What is deliberately not here. No message names, no channel structure, no encoding — none of that is specified by anything this chapter can cite. No transient states: a line waiting for acknowledgements is neither S nor M, and 13.4 is where that becomes storage. No concrete request flows — Module 14. No directory organisation or fabric — Modules 15 and 16.

23. How This Appears In Real Engineering

In architecture review, the recurring argument is whether E is worth its bit. The answer is a measurement, not a principle: the silent-upgrade fraction on the workloads that matter. On a private, migratory working set E removes a broadcast from every first write; on a genuinely shared one it does almost nothing.

In RTL design, the two defects that recur are a grant derived from a request, and permission stored rather than derived. Both survive review because the block diagram is right — the arrow does point from the acknowledgement collector to the grant — and only the expression is wrong.

In verification, the trap is that most coherency bugs need two agents and a specific interleaving. A single-agent test exercises the whole state machine and proves almost nothing about the protocol, because every interesting property is about what two agents may hold simultaneously.

In bring-up, false sharing is the one that wastes the most time, because it presents as a hardware performance problem and is a software layout problem. The transfers-per-line counter is what ends that argument in minutes rather than weeks.

In software, the three non-guarantees are the whole reason memory models exist. Every fence, every atomic, and every padding attribute in a concurrent codebase is there because coherency deliberately does not promise what people assume it promises.

24. Common Misconceptions

"Coherency keeps caches in sync." It makes each line behave as if there were one copy. It says nothing about caches as a whole, about ordering between lines, or about how long anything takes.

"Coherency gives you memory ordering." Measured false: line B written second was visible while line A written first was not, with both lines perfectly coherent. Ordering across lines is consistency, and it needs a fence.

"Coherency makes updates atomic." Measured false: two increments produced one, with every access correctly ordered and every value correctly returned.

"A cache line holds data." It holds permission, and the data is what the permission is over. Every state name in every protocol is a permission label.

"E is a minor optimisation." It is the difference between a broadcast and nothing on every first write to a privately-held line. Measured: one silent upgrade against one invalidating upgrade for the identical local operation.

"A read never causes traffic." A read by another agent downgrades M to S and forces the dirty data to be forwarded. Reads revoke write permission.

"Requesting exclusive access is having it." The measured trace has four cycles between request and grant, and three agents hold readable copies throughout.

"High coherency traffic means a coherency bug." Nine transfers for ten bytes of work with a perfectly clean invariant is false sharing — a data-layout problem with no protocol fault at all.

25. Interview Reasoning

26. Exercises

1. Calculation. A line is held in S by six agents. One requests an upgrade. Compute the invalidations sent, the acknowledgements awaited, and the same figures if the line had been held in E by one agent. Then state the silent-upgrade fraction for a workload where 80% of first writes touch privately-held lines.

2. Analysis. A read returns a value that was overwritten earlier. Give the two measurements that distinguish "the invalidation never arrived" from "the grant fired before the acknowledgements did", and state what each would read in both cases.

3. RTL task. Extend mesi_line with an Owned state, giving MOESI. State precisely what O grants that S does not, which transition produces O, and what obligation O places on the holder that S does not.

4. Assertion task. Write the property proving that write permission implies read permission. Then explain why this is not implied by the SWMR property, and construct a state encoding on which SWMR holds and this property fails.

5. Design task. Replace broadcast invalidation with a directory holding a sharer vector per line. State the storage cost, what must happen when the vector overflows, and which invariant is at risk if an overflow is handled by silently dropping a sharer.

6. Testbench design. Design the stimulus that proves the E state is reachable and that its upgrade is genuinely silent. Explain why a test that only ever reads lines other agents already hold cannot distinguish a design with E from one without it.

7. Debug task. Two threads update adjacent counters and throughput collapses. Give your investigation order, name the counter that separates a coherency bug from a layout problem, and state what each reading implies for who fixes it.

8. Design review. A colleague argues that read-modify-write needs no special support because coherency already guarantees every read returns the latest value. Give the strongest version of that argument, then the measurement that refutes it, and explain why the memory value alone cannot reveal the failure.

27. Summary

A cache line is not data you have. It is permission you hold.

• Four states are four permissions. I grants nothing, S grants reading, E grants reading and writing with exclusivity, M is E with the data modified. Permission is derived from state and never stored twice.
• E earns its bit by making a write free. Measured: from E, 1 silent upgrade and 0 invalidations; from S, 1 invalidation and a wait. A read miss with no sharers lands in E; with sharers, in S.
• SWMR is the invariant everything serves — at most one writer, and no readers while one exists. The two violations were measured separately at two_writer_err=1 and writer_with_reader_err=1, because they are grant-side and revocation-side failures.
• A request is not a permission. The measured trace has four cycles between request and grant, with 3 acknowledgements outstanding throughout.
• Dirty data must survive eviction. Measured 1 writeback and 2 silent evictions, with a second eviction over a pending writeback raising data_lost_err.
• Coherency is per line. Line B written second was visible while line A written first was not — reorder observed=1, with both lines perfectly coherent. Ordering across lines is consistency and needs a fence.
• Coherency does not make read-modify-write atomic. Two increments produced memory=1, and only the update count — not the value — revealed a wrongly-accepted write.
• False sharing is correct and pathological. 9 transfers for 10 writes, 90%, with swmr_violated=0 sampled while a transfer was in flight.
• Verification: 123 assertion sites, 64 of 64 mutations killed, zero surviving. Nine first-run escapes were seven stimulus gaps, one unreachable checker needing a fault-injection hook, and one unobserved output — zero missing checkers.

Next: 13.2 Shared Memory Across CXL, which takes this entire vocabulary and changes one thing: the agents are no longer on the same die. Everything above still has to hold when the invalidation has to cross a link.