What can H do when it no longer knows who holds X?

H reads X's directory entry and the ECC reports an uncorrectable error, or the entry was lost with a failed array bank. H must not guess. Treating the entry as U lets H serve the next reader from memory, which may be stale; treating it as the last value it remembers can skip a holder. The safe reading is unknown: any cache may hold X in any state, including M.

That is the conservative rule already used for capacity. A Dir_i B entry in overflow means 'every cache may hold X' and its next GetM invalidates all of them (Limited Pointers and Coarse Vectors); a filter that cannot answer must use a conservative fallback (Snoop Filter Correctness). Rule: unknown means broadcast. Here the broadcast also has to recover a dirty value, as in Filter Eviction and Back-Invalidation, where H used Fwd-GetM on its own behalf.

The recovery recall

Model extension for this lesson. When an entry is unknown, H freezes new requests for X behind the pending entry and sends Fwd-GetM on its own behalf, called a recall, to every cache except the requester (which sent GetS, so it holds nothing). A cache holding X in M answers Data with its value and goes to I. A cache in S or I answers Inv-Ack and ends in I. When every target has answered, H knows exactly: no cache holds X, and memory is current once any recalled dirty data has been written. The entry is rebuilt as U, and the waiting request continues as an ordinary one. The table writes the untrusted entry as unknown, and recall k/2 counts the answers (Data or Inv-Ack) H has received out of the recalls it sent.

To make the cost visible, extend the course model to three caches C0, C1, C2 for this lesson. MSI. Warm-up from X = 0: C0 acquired M and stored 1, so C0 M / 1, C1 and C2 I / -, H exclusive(C0), memory = 0. C1 sends GetS. Reading the entry for it, H's ECC reports an uncorrectable error.

C1 gets 1, the correct value. Had H treated the entry as U, it would have read memory and returned 0 while C0 still held M / 1: a stale read and, after C1 got S, a writer beside a reader. Messages 3 and 4 are the price of not knowing: C2 never held X.

What recovery costs

Every copy is revoked too, so readers that had S miss again afterwards. A design can add a non-destructive probe that reports a cache's state and keeps its copy, so H can rebuild the sharer list instead of emptying it; that needs a message type the course vocabulary does not have. If a whole directory bank is lost, every line it tracked becomes unknown and recovery amounts to recalling that whole address range from every cache. Recovery is a rare slow path: it only has to be correct, not fast.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

import random
def truth(holders):
    dirty = [v for s, v in holders.values() if s == "M"]
    return dirty[0] if dirty else 0  # MSI: memory is current unless a cache holds M
def recover(holders, requester, n, strategy, responsive=True):
    """Serve a GetS after the entry for X is lost. Returns (result, probes)."""
    if strategy == "assume_U":
        return ("data", 0), 0  # read memory, which holds 0
    mem, probes = 0, 0
    for c in range(n):
        if c == requester:
            continue
        probes += 1
        state, value = holders.get(c, ("I", None))
        if state == "M":
            if not responsive:
                return ("poison", None), probes  # the only newest copy will not answer
            mem = value  # Data back to H, H writes memory
        holders[c] = ("I", None)
    return ("data", mem), probes
rng = random.Random(10)
stale_seen = 0
for trial in range(2000):
    n = rng.choice([3, 8, 64])
    requester = rng.randrange(n)
    others = [c for c in range(n) if c != requester]
    if rng.random() < 0.5:
        holders = {rng.choice(others): ("M", rng.randrange(1, 100))}
    else:
        holders = {c: ("S", 0) for c in rng.sample(others, rng.randrange(0, len(others) + 1))}
    want = truth(holders)
    naive, _ = recover(dict(holders), requester, n, "assume_U")
    stale_seen += naive != ("data", want)
    result, probes = recover(dict(holders), requester, n, "recall")
    assert result == ("data", want) and probes == n - 1
    if want != 0:
        dead, _ = recover(dict(holders), requester, n, "recall", responsive=False)
        assert dead == ("poison", None)  # never stale data
assert stale_seen > 0  # failing case: treating unknown as U returns stale memory
print("PASS: recall rebuilds the value with n - 1 probes, assume-U returns stale data")

The check builds random holder sets with a fixed seed: either one M holder with some value, or any number of clean S holders. Recalling every other cache always returns the true value with n - 1 probes; reading memory as if the entry were U returns stale data whenever a cache held M. If the M holder cannot answer, recall reports poison rather than a value.

When the entry cannot be rebuilt

Recall works only if every possible holder answers. Suppose C0 held M / 1 and was powered off without flushing (Flushing Before Power-Down is the rule it broke), or C0's own tag or state for X also failed. The only record of the dirty copy was H's entry, and the only copy will not answer. Memory holds 0, which is wrong. H must not grant 0 as good data.

Two things are needed. First, H must notice: without a time-out on the recall, H's pending entry waits forever, and the progress argument of Stating Progress Assumptions does not cover a component that never answers. Second, H must contain the loss: if it still knows the address, it writes poison for X's line to memory and grants C1 Data(poisoned), so the error surfaces only at a consumer. If even the address is unknown, for example because the entry's own tag failed, H cannot tell which line to poison, and the error has to be escalated, as the next lesson classifies.

Related topics

• Shared course model

• Overflow: unknown means broadcast

• Conservative fallback

• Recalling dirty data on H's behalf

• Next: recovery limits