Does a flipped state bit just give a wrong value?

No. Data bits hold values; state bits, tags and directory entries hold permissions and responsibility. A flip in data gives one wrong value. A flip in metadata changes what the protocol does next: who may write, who receives an Inv, where dirty data is written back. So the question for each structure is not only how likely a flip is, but what an undetected flip breaks.

The asymmetry in the directory rows is the inclusive-filter invariant of Snoop Filter Correctness: an extra holder is a false positive (cost), a missing holder is a false negative (a correctness bug).

Worked case: a lost sharer bit

MSI. Warm-up from X = 0: C0 and C1 both read X, so both hold S / 0 and H records S{C0,C1}, memory = 0. Assume an undetected flip clears C1's bit. C0 then upgrades. H finds no other sharer, sends no Inv and grants M with permission-only Data. The messages and the end state are those of the deliberately broken grant in What a Violation Looks Like, with the same roles; the cause here is a storage flip instead of a protocol bug, so only the table is shown.

SWMR is already broken at step 2, before any value changes: C0 holds M while C1 still holds S. No checker that looks only at messages would flag step 1: H did exactly what its entry said. The defence is a code on the entry that turns the flip into a corrected or at least a detected event before H acts on it.

Parity and SECDED

Parity adds one bit so that the total number of ones is even. Any single flip makes it odd, so parity detects one flip, but it cannot say which bit flipped, and two flips cancel and go unnoticed. Parity is enough where a detected error can be repaired by discarding the copy: a clean data line, or the tag of a line whose separately protected state says it is clean.

SECDED (single-error correction, double-error detection) is a Hamming code plus one overall parity bit. With r check bits a Hamming code can locate one flip among d data bits when 2^r is at least d + r + 1. For 8 data bits r = 4 (a 12-bit Hamming codeword), and the overall parity bit makes 13; for 64 data bits r = 7, plus the overall bit gives the common illustrative layout of 64 data bits and 8 check bits (72 bits stored). On decode, the Hamming syndrome names the flipped position, and the overall parity tells one flip (odd) from two (even, syndrome non-zero).

The check below implements SECDED over 8 data bits and tests every data value: every single flip is corrected and every double flip is detected. It then shows the two failure cases: parity alone gives the same answer for every single flip, so it cannot correct, and misses double flips; a Hamming code without the overall bit silently miscorrects double flips into wrong data.

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

from itertools import combinations
DATA_POS = [p for p in range(1, 13) if p & (p - 1)]  # 3,5,6,7,9,10,11,12
CHECK_POS = [1, 2, 4, 8]
def encode(d):
    w = [0] * 13  # w[0] is the overall parity bit
    for i, p in enumerate(DATA_POS):
        w[p] = (d >> i) & 1
    for c in CHECK_POS:
        w[c] = sum(w[p] for p in range(1, 13) if p & c and p != c) % 2
    w[0] = sum(w[1:]) % 2
    return w
def data_of(w):
    return sum(w[p] << i for i, p in enumerate(DATA_POS))
def decode(w, overall=True):
    w = list(w)
    s = sum(c for c in CHECK_POS if sum(w[p] for p in range(1, 13) if p & c) % 2)
    if not overall:  # Hamming SEC only: no double-error detection
        if 0 < s < 13:
            w[s] ^= 1
        return ("ok" if s == 0 else "corrected"), data_of(w)
    p = sum(w) % 2
    if s == 0 and p == 0:
        return "ok", data_of(w)
    if p == 1 and s < 13:
        if s:
            w[s] ^= 1  # s = 0: the overall bit itself flipped
        return "corrected", data_of(w)
    return "uncorrectable", None
def flipped(w, *bits):
    w = list(w)
    for b in bits:
        w[b] ^= 1
    return w
def check_bits(d):
    r = 1
    while 2 ** r < d + r + 1:
        r += 1
    return r
assert check_bits(8) + 1 == 5 and check_bits(64) + 1 == 8  # 13-bit and 72-bit codewords
miscorrected = 0
for d in range(256):
    w = encode(d)
    assert decode(w) == ("ok", d)
    for i in range(13):
        assert decode(flipped(w, i)) == ("corrected", d)
    for i, j in combinations(range(13), 2):
        assert decode(flipped(w, i, j))[0] == "uncorrectable"
    for i, j in combinations(range(1, 13), 2):
        status, value = decode(flipped(w, i, j), overall=False)
        miscorrected += status != "uncorrectable" and value != d
assert miscorrected > 0  # failing case 1: without the overall bit, double flips become wrong data
def parity_check(bits):
    return sum(bits) % 2
word = [1, 0, 1, 1, 0, 0, 1, 0]
stored = word + [parity_check(word)]
syndromes = {parity_check(flipped(stored, i)) for i in range(9)}
assert syndromes == {1}  # failing case 2: every single flip looks the same, nothing to correct
assert parity_check(flipped(stored, 2, 5)) == 0  # and a double flip goes unseen
print("PASS: SECDED corrects every single flip and detects every double flip, parity and SEC-only do not")

Real designs choose a code per structure: SECDED on data arrays and directory entries, often parity on tags and state where the line can be discarded, and stronger codes where multi-bit upsets in adjacent cells are expected. Physical interleaving, so that neighbouring cells belong to different codewords, turns one upset that hits adjacent cells into single flips in several words. Treat these as general guidelines, not a product's choices.

Related topics

• Shared course model

• Same end state, protocol cause

• False positive versus false negative

• Next: poisoned data