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.

Which filter mistake is a correctness bug?

Consider the independent dirty snapshot C0 M / 1, C1 I / -, H exclusive(C0), memory = 0, newest C0: 1. If F wrongly omitted C0, H would grant C1 from memory with 0 instead of 1. This is a counterfactual unsafe decision, not a valid alternative transaction. The classification of exact, false-positive, false-negative and unknown results is in Hybrids and Snoop Filters.

When does the filter allocate?

The invariant covers an admitted fill, not only stable cache tags. The simplest choice allocates C1 into F(X) when H admits C1's GetS, before Data leaves H. An alternative allocates when H learns the Data was delivered; that is safe only because H's pending entry for X already blocks every conflicting request until then, so the pending entry covers C1 in the meantime. Allocating after delivery with no pending entry would leave C1 holding S / 0 with no entry: a false negative.

Allocation can fail. If F's set for X is full, the GetS must wait while H reclaims a victim entry, which is the subject of Filter Eviction and Back-Invalidation.

Where false positives come from

Silent clean eviction (the Part 3 variant) is the natural source. C0 drops its S copy without PutS, so F(X) still lists C0. The next GetM sends C0 an Inv, and C0 answers Inv-Ack from I: one wasted round trip, no error. With notified eviction (the course default), PutS lets H remove C0 and free the entry.

In MESI, a cache in E can store without telling H (the silent E-to-M store of MESI and the Exclusive State). F records exclusive(C0) but cannot tell E from M, so an exclusive entry must be treated as possibly dirty: a GetS forwards to C0 rather than reading memory, and reclaiming the entry must recover data rather than send a bare Inv.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

def covers(holders, F):
    return holders <= F
def targets(request, F, exclusive):
    return set(F) if request == "GetM" else ({exclusive} if exclusive else set())
assert covers({"C0"}, {"C0"})
assert covers(set(), {"C0", "C1"})       # false positive: costs work only
assert not covers({"C0"}, set())          # false negative: correctness bug
admitted_fill = {"C1"}                    # GetS admitted, Data not yet delivered
assert not covers(admitted_fill, {"C0"})
assert covers(admitted_fill, {"C0", "C1"})
F = {"C0"}                                # C0 evicted silently, F still lists it
assert targets("GetM", F, None) == {"C0"} # one wasted Inv, answered from I
assert targets("GetS", {"C0"}, "C0") == {"C0"}  # E may be M: forward, not memory
assert targets("GetS", {"C0", "C1"}, None) == set()
print("PASS: inclusive coverage includes admitted fills, false positives only cost work")

This is a set-invariant check, not a protocol simulator. A real fallback must actually deliver to every relevant cache and collect the responses.

Related topics

• Shared course model

• Hybrids and Snoop Filters

• Pending obligations