Model extension, as in Hybrids and Snoop Filters: H's holder record is a finite inclusive filter F with a limited number of entries. The H directory column shows F's entry for X.
Suppose C0 sends GetS(Y), F needs an entry for Y, and the set Y maps to is full, here with X's entry. H must choose a victim and reclaim it before admitting GetS(Y), which waits meanwhile. Victim choice is a policy: an entry with fewer holders, or only clean holders, costs fewer back-invalidations. Dropping the victim is not an option, because the invariant would then have a false negative. The inclusive policy of Hybrids and Snoop Filters removes the listed copies first: H-initiated back-invalidation, not a cache's own eviction.
Use MSI. Warm-up from X = 0: C0 and C1 both have S / 0, H records S{C0,C1}, memory = 0. H chooses X's entry as the victim and freezes conflicting X requests while the retirement is pending. It records both holders as expected acks and waits for both.
Step | C0 state / value | C1 state / value | H directory | Memory | Newest data |
|---|---|---|---|---|---|
0 warm-up | S / 0 | S / 0 | S{C0,C1} | 0 | C0, C1 and memory: 0 |
(assumed) H admits tracking retirement | S / 0 | S / 0 | S{C0,C1}, pend tracking retirement, acks 0/2 | 0 | C0, C1 and memory: 0 |
1 Inv at C0 | I / - | S / 0 | S{C0,C1}, pend tracking retirement, acks 0/2 | 0 | C1 and memory: 0 |
2 Inv at C1 | I / - | I / - | S{C0,C1}, pend tracking retirement, acks 0/2 | 0 | memory: 0 |
3 Inv-Ack from C1 at H | I / - | I / - | S{C0,C1}, pend tracking retirement, acks 1/2 | 0 | memory: 0 |
4 Inv-Ack from C0 at H | I / - | I / - | S{C0,C1}, pend tracking retirement, acks 2/2 | 0 | memory: 0 |
(assumed) H commits retirement | I / - | I / - | U | 0 | memory: 0 |
A bare Inv-Ack does not carry X = 1, so a dirty victim needs Fwd-GetM on H's own behalf. Take an independent snapshot: from X = 0, C0 acquired M and stored 1, H records exclusive(C0), memory = 0. The messages are those of the clean case with Fwd-GetM and Data(1) in place of Inv and Inv-Ack, so only the table is shown.
Step | C0 state / value | C1 state / value | H directory | Memory | Newest data |
|---|---|---|---|---|---|
0 warm-up | M / 1 | I / - | exclusive(C0) | 0 | C0: 1 |
(assumed) H admits tracking retirement | M / 1 | I / - | exclusive(C0), pend tracking retirement, data 0/1 | 0 | C0: 1 |
1 Fwd-GetM(X) at C0, for H's recovery | I / - | I / - | exclusive(C0), pend tracking retirement, data 0/1 | 0 | Data(1) in flight to H |
2 Data(1) at H | I / - | I / - | exclusive(C0), pend tracking retirement, data 1/1 | 0 | H buffer: 1 |
H writes memory, X = 1 | I / - | I / - | exclusive(C0), pend tracking retirement, data 1/1 | 1 | H buffer and memory: 1 |
(assumed) entry freed | I / - | I / - | U | 1 | memory: 1 |
Dirty data reaches memory before the entry is freed. If C0 was already evicting X, it is in MI^A when the Fwd-GetM arrives: it answers from its writeback buffer with Data(1) and moves to II^A. If its PutM arrives before the entry is freed, H already holds C0's Data, so it sends Put-Ack with no second memory write. A PutM that arrives later reaches an H that no longer records C0 as a holder, so it gets Put-Ack with no directory or memory change. Because of the silent E-to-M store, an exclusive(C0) victim in MESI takes this dirty path even when C0 may still be clean.
Reclamation condition | Why it matters |
|---|---|
Block or safely merge conflicting work | A new fill cannot escape the expected set during retirement. |
Match all expected acknowledgements | A delayed response cannot be mistaken for one from a later use of the entry. |
Preserve any current dirty payload | The only newest value must not vanish with tracking capacity. |
Keep coverage until retirement commits | Absence lookups must not become trustworthy too early. |
The clean example completes under A1-A6 (assumptions), here A4: each target eventually accepts its Inv. If one target cannot respond, the entry stays pending; this example does not claim progress through a permanent component failure. Backpressure on retirement may reduce capacity without being a permission bug.
H has received only one of the two required acknowledgements. It cannot base safety on unseen endpoint state; its protocol-visible evidence is still incomplete.