A core stopped making progress: what is it waiting for?

A watchdog fires: C0 has not retired a store for a long time. A timeout says only that something is slow. To classify the hang you need each controller's own record of what it waits for. The general method of following a wait backwards is in Following the Wait and the Hardware Debug course's hangs part. For coherence the records are fixed: the core-side MSHRs, H's pending entries, and the message queues between them.

1. Take a snapshot: stop clocks and scan out, or freeze admission and read through the debug port, so the dump is one consistent moment (see Debug Hooks in Controllers).

2. Dump every MSHR for the stuck line, H's pending entry for it, and the occupancy and credits of every queue on the path.

3. Draw one edge per wait: waiter, target and the item it waits for (Data, Inv-Ack, a free slot, a credit).

4. Follow the edges. At each target, check whether it holds a record of the item: an entry, a queued message or a resource it will release.

5. Resume, wait, freeze and dump again. If counters moved, the system is not stuck: it is livelock, starvation or slow backpressure.

Worked case A: H waits for an Inv-Ack that C1 never saw

Warm-up: two completed reads, C0 S / 0, C1 S / 0, H S{C0,C1}, memory = 0, as in Upgrade from Shared, with the same roles: C0 upgrades, C1 is the sharer. In this illustrative failure the Inv to C1 is dropped on the way (a fabric or ingress bug: the course model promises reliable delivery, so a lost message is always a bug).

The chain C0 to H to C1 ends at an agent with no record: a lost message. C1's line state says which leg was lost. C1 still in S means the Inv never took effect at C1. C1's own port tap or ingress counter separates a fabric drop from C1 discarding the Inv. If C1 were I / - with nothing queued, check H's input for a PutS from C1 first (a notified eviction also leaves C1 in I); with no PutS, the Inv was delivered and the Inv-Ack was lost or never sent. Either way, H's ack counting did its job: the bug shows up as a hang, not as stale data. Compare the missed Inv of the previous lesson, where H did not wait and C1 read a stale value.

Worked case B: a credit cycle

Use the checkpoint of A Protocol Deadlock, with its roles: C1's GetM for X holds H's only pending entry P; C0's GetS for Y holds H's only ingress slot Q while it waits for P; C0's egress slot T0 holds Data(1) for X and waits for space in Q. The dump differs from case A in one way: every target has a record. P is held and waits for the data in T0; T0 holds it and waits for Q; Q is held by GetS(Y), which waits for P. The chain closes on itself, nothing is lost, and the newest value is safe in T0. The fix is a reserved response path, not a retransmission.

Classify the dump mechanically

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

def classify(waits, owes):
    for start in waits:
        path, node = [], start
        while node in waits:
            if node in path:
                return "deadlock: " + " -> ".join(path[path.index(node):] + [node])
            path.append(node)
            target, item = waits[node]
            if item not in owes.get(target, set()):
                return f"lost message: {node} waits for {item} from {target}, which has no record of it"
            node = target
    return "no cycle and no dangling wait: compare two dumps for slow progress"
def timeout_only(waits, owes):          # broken variant: every stuck entry is called deadlock
    return "deadlock" if waits else "ok"
lost_inv = ({"C0.MSHR X": ("H.pend X", "Data X"), "H.pend X": ("C1", "Inv-Ack X")},
            {"H.pend X": {"Data X"}, "C1": set()})       # C1: S / 0, no MSHR, no Inv queued
inv_ack_in_flight = (lost_inv[0], {"H.pend X": {"Data X"}, "C1": {"Inv-Ack X"}})
credit_cycle = ({"C1.MSHR X": ("H.P", "Data X"), "H.P": ("C0.T0", "Data(1) X"),
                 "C0.T0": ("H.Q", "free slot"), "H.Q": ("H.P", "free entry")},
                {"H.P": {"Data X", "free entry"}, "C0.T0": {"Data(1) X"}, "H.Q": {"free slot"}})
a, b, c = classify(*lost_inv), classify(*inv_ack_in_flight), classify(*credit_cycle)
assert a.startswith("lost message") and "from C1" in a
assert b.startswith("no cycle")                 # the ack exists, it is only late
assert c == "deadlock: H.P -> C0.T0 -> H.Q -> H.P"
assert len({timeout_only(*d) for d in (lost_inv, inv_ack_in_flight, credit_cycle)}) == 1
assert len({x.split(":")[0] for x in (a, b, c)}) == 3
print("PASS: dumps separate a lost Inv, a late Inv-Ack and a credit cycle, a timeout cannot")

The same edges give three different answers depending on what each target holds: a lost Inv (C1 has no record), a late Inv-Ack (C1 has it queued, so wait or look for backpressure), and a cycle. The broken variant, which calls every timeout a deadlock, gives one answer for all three.

Related topics

• Shared course model

• Previous: stale-data triage

• Progress assumptions

• What MSHRs and pending entries hold