This story is illustrative and fictional: the design, the numbers and the timeline are invented to show the process. The mechanism is real and appears in the course already. It is the eviction-versus-intervention race, with a Fwd-GetM instead of a Fwd-GetS and the direct route of Three-Hop Versus Four-Hop. The roles stay as in those lessons: C0 evicts, C1 requests.
The illustrative design implements both routes, with a chicken bit choosing between them. On the four-hop route, C0's Data goes to H and says "PutM outstanding", an extension of order B of the eviction lesson (there the mark only keeps C0 out of the sharer set); this design also uses it to mark the coming PutM as stale, which H then acknowledges with no change. On the three-hop route H never sees that Data, so it relies on its Put handler. The handler checked only that the entry was exclusive, not that the sender was the recorded exclusive holder. The course's rule says a Put from a non-holder gets Put-Ack with no directory or memory change; this handler broke it.
Start: C0 acquired M and stored 1. C0 then evicts X under background pressure: the WB entry holds 1, C0 is in MI^A, and PutM W is slow in the fabric. Direct transfer is enabled. MSI.
Step | C0 state / value | C1 state / value | H directory | Memory | Newest data |
|---|---|---|---|---|---|
Initial | M / 1 | I / - | exclusive(C0) | 0 | C0: 1 |
C0 evicts | MI^A / 1 (in WB) | I / - | exclusive(C0) | 0 | C0 WB: 1, PutM(1) in flight to H |
1. GetM R at H | MI^A / 1 (in WB) | IM^D / - | exclusive(C0), pend GetM C1 | 0 | C0 WB: 1, PutM(1) in flight to H |
2. Fwd-GetM at C0 | II^A / - | IM^D / - | exclusive(C0), pend GetM C1 | 0 | Data(1) in flight to C1, PutM(1) in flight to H |
3. Data at C1 | II^A / - | M / 1 | exclusive(C0), pend GetM C1 | 0 | C1: 1, PutM(1) in flight to H |
(assumed) grant delivered | II^A / - | M / 1 | exclusive(C1) | 0 | C1: 1 (stale PutM(1) in flight to H) |
L1. Local store | II^A / - | M / 2 | exclusive(C1) | 0 | C1: 2 (stale PutM(1) in flight to H) |
4. PutM W at H | II^A / - | M / 2 | exclusive(C1), pend PutM C0 | 0 | C1: 2 |
H writes memory (bug) | II^A / - | M / 2 | U | 1 | C1: 2 |
5. Put-Ack at C0 | I / - | M / 2 | U | 1 | C1: 2 |
L2. Local load misses | I / - | M / 2 | U | 1 | C1: 2 |
6. GetS at H | IS^D / - | M / 2 | U, pend GetS C0 | 1 | C1: 2 |
H reads memory | IS^D / - | M / 2 | U, pend GetS C0 | 1 | C1: 2, stale Data(1) in flight to C0 |
7. Data at C0 | S / 1 | M / 2 | U, pend GetS C0 | 1 | C1: 2 |
(assumed) grant delivered | S / 1 | M / 2 | S{C0} | 1 | C1: 2 |
At step 7 C0 holds S while C1 holds M: SWMR is broken, and C0 reads 1 after 2 was written. If C1 later evicts, its PutM comes from a non-holder (H records S{C0}), and the write of 2 is lost entirely. With the correct handler, step 4 sees that C0 is not the recorded holder, sends Put-Ack with no change, and step 6 becomes a Fwd-GetS to C1 that returns 2.
Stage | What happened (illustrative) |
|---|---|
Seen | A fenced MP test (C1 writes X then a flag, C0 waits for the flag and reads X) with an eviction-pressure thread reported the old payload three times in 10^9 runs. Forbidden on every model with fences on both sides: a bug. |
Traced | Following stale-data triage: the trace buffer at H, triggered by the test's failure check through software, filtered on X's line (the ring kept steps 1 to 7), showed a PutM accepted from C0 after H had recorded exclusive(C1). Setting chicken bits one at a time: only "disable direct transfer" made the failure vanish, which pointed at the three-hop path. |
Worked around | Boot firmware sets the bit and locks it. Cost: one extra leg on every dirty-miss critical path. The full regression was rerun with the bit set, and the direct-transfer counter read zero. |
Fixed | Next stepping: the Put handler compares the sender with the recorded holder before accepting data, and only when no transaction for X is pending; otherwise the Put waits in X's pending entry. |
Prevented | Pre-silicon: a directed race test, a cover point for "PutM from a non-holder after a three-hop Fwd-GetM", a wider delay range on the Put class in random tests, and an assertion that a Put from a non-holder never changes the directory or memory. Post-silicon: the failing test joins the regression in both bit settings. |
Why pre-silicon missed it: the random tests bounded Put delays to a few cycles, so a PutM never arrived after a forwarded transfer had completed. The design-level cross of transfer route against Put arrival time was never measured, so nobody saw the hole. The model below reproduces the decision: rare late Puts, two routes, buggy and fixed handlers.
import random
def scenario(direct, strict_put_check, put_late):
"""C0 holds M / 1 and evicts (PutM(1) in flight). C1 sends GetM.
put_late: the PutM reaches H after the Fwd-GetM transfer completed.
Returns the value C0 reads when it later loads X again."""
d = {"state": "exclusive", "holder": "C0"}
mem, c1, stale_put_from = 0, None, None
def handle_put(sender, value):
nonlocal mem
if stale_put_from == sender: # 4-hop Data said a PutM is outstanding
return "ack, no change"
holder_ok = d["holder"] == sender if strict_put_check else True
if d["state"] == "exclusive" and holder_ok:
mem = value # H writes memory, then Put-Ack
d.update(state="U", holder=None)
return "accepted"
return "ack, no change" # Put from a non-holder
if not put_late:
handle_put("C0", 1) # writeback first: order A
c1 = mem # H sources C1 from memory
else:
# Fwd-GetM hits C0 in MI^A, answered from the WB entry, C0 to II^A
if not direct:
stale_put_from = "C0" # Data(1, PutM outstanding) went via H
c1 = 1
d.update(state="exclusive", holder="C1") # grant delivered (assumed)
c1 = 2 # L1. C1 stores X = 2
if put_late:
handle_put("C0", 1) # the late PutM arrives
# L2. C0 loads X again, misses: GetS at H
if d["state"] == "exclusive":
return c1 # Fwd-GetS to C1, Data(2)
return mem # H reads memory
rng = random.Random(2026)
delays = [rng.expovariate(1.0) for _ in range(20000)]
LATE = 6.0 # only rare delays cross the Fwd
runs = {}
for direct in (True, False):
for strict in (False, True):
runs[(direct, strict)] = sum(scenario(direct, strict, t > LATE) != 2 for t in delays)
late_count = sum(t > LATE for t in delays)
assert 0 < late_count < 100 # the window is rare
assert runs[(True, False)] == late_count # bug: every late Put gives a stale read
assert runs[(False, False)] == 0 # chicken bit, 4-hop: hides the bug
assert runs[(True, True)] == 0 # fix: holder check, direct path
assert runs[(False, True)] == 0 # fix with chicken bit also correct
assert scenario(True, False, False) == 2 # bug is invisible without the late Put
print("PASS: stale read only with direct transfer, a late PutM and the weak Put check")The lesson is the process, not the incident: a forbidden outcome seen once, classified against the model, localised with traces and chicken bits, contained by a verified fallback, fixed at the root, and turned into coverage on both sides of tape-out so the same class of bug cannot escape again.
On the four-hop route C0's Data, marked "PutM outstanding", reaches H. H knows the coming PutM is stale and acknowledges it without consulting the faulty check. On the three-hop route that Data goes to C1, so the faulty check is the only defence.