Deadlock

Module 18 · Chapter 18.6 · CHI Debugging

Project thread — 18.5 debugged directory corruption. 18.6 debugs deadlock; 18.7 debugs credit issues.

1. Learning Outcomes

By the end of this chapter you should be able to:

• Define deadlock — a cycle of waits where no agent makes progress.
• Distinguish deadlock (links frozen) from livelock (links busy, no progress).
• Read the waveform signature — channels stalled with valid high, ready low, outstanding flat.
• Reconstruct the wait-for graph among the stalled agents.
• Find the cycle and the back-edge — the forbidden dependency (Chapter 14.3).
• Implement a representative deadlock detector in SystemVerilog, Verilog-2001, and VHDL.

2. Why Should I Learn This?

Deadlock is the most total failure: the fabric stops. Not a wrong value, not a stale copy — nothing completes. It is a liveness failure (no progress), distinct from every prior family, which were safety failures (wrong result). And it is uniquely hard to debug because there is no error event to catch — the design simply stops doing anything, and you must diagnose from the absence of activity.

The key to debugging it is that deadlock has a precise structure: a cycle of waits. Each stalled agent is waiting on another, and those waits form a loop — A waits on B, B waits on A (or a longer cycle). The signature is recognizable — channels stalled with valid high and ready low, the outstanding count flat, for an unbounded time — which also distinguishes it from livelock (links busy, retrying, but no progress). The diagnosis is to reconstruct the wait-for graph and find the cycle; the back-edge that closes it is the forbidden dependency (Chapter 14.3), and removing it breaks the deadlock. This chapter is how to recognize a frozen fabric and trace the cycle to its cause.

3. Key Terms

4. Previous Chapter Connection

This chapter debugs the flow-control and deadlock-avoidance mechanisms of Module 14. The root cause is a violation of Chapter 14.3's drain rule — a response or data acceptance made to wait on a request being issued, which closes a dependency cycle. This chapter finds that cycle from the frozen symptom.

It is the debug counterpart of the design lesson in Chapter 14.3. There, the rule was structural: responses and data must always be sinkable, so the dependency graph stays acyclic. Here, the failure is a graph that has a cycle anyway — because some node violated the rule — and the debug reconstructs the cycle to find the offending back-edge. It also relates to the backpressure of Chapter 14.4: a benign stall (backpressure) is temporary and resolves; a deadlock stall is permanent because of the cycle. Distinguishing "stalled but will resolve" from "stalled forever in a cycle" is the crux, and the wait-for graph is the tool. This chapter is the liveness debug.

5. Core Concept — reconstruct the wait-for cycle

Deadlock is a cycle of waits among stalled agents; the diagnosis is to reconstruct the wait-for graph and find the cycle, whose back-edge is the forbidden dependency.

• Deadlock is a cycle. Each stalled agent is waiting on another to make progress; when those waits form a loop (A → B → … → A), none can proceed — the fabric freezes.
• The signature is persistent stall. The involved channels sit with valid high and ready low, the outstanding count flat, for an unbounded time — no progress, no error.
• Distinguish from livelock. In deadlock the links are frozen (idle); in livelock they are busy (retrying) but still make no progress. The waveform tells them apart.
• Find the cycle and back-edge. Reconstruct who waits on whom among the stalled agents; the cycle is the deadlock, and the back-edge — usually a response/data acceptance waiting on a request (Chapter 14.3) — is the bug.

The synthesis:

Deadlock is a cycle of waits among stalled agents — each waiting on another, so none progresses and the fabric freezes. The signature is channels persistently stalled (valid high, ready low) with the outstanding count flat — frozen links, distinguishing it from livelock (busy links, no progress). The diagnosis is to reconstruct the wait-for graph and find the cycle; its back-edge — typically a response/data acceptance gated on a request (Chapter 14.3) — is the forbidden dependency to remove.

6. Engineering Mental Model — cars gridlocked at a four-way

Think of a four-way intersection where every car is waiting for the car ahead to move.

• Each car occupies part of the intersection and cannot advance until the car in front of it clears — a wait. Normally the front car eventually moves and the whole line flows.
• Gridlock (deadlock) is when the waits form a loop: car A blocks car B's path, B blocks C's, C blocks D's, and D blocks A's. Every car is waiting on the next, around the loop — so no car can move. The intersection freezes.
• The signature is total stillness: every car stopped, engines idling, no movement for a long time — distinct from a traffic jam that is slowly crawling (livelock).
• To clear it, you do not push harder — you map who is blocking whom, find the loop, and break one dependency (wave one car back). The loop is gone, and traffic flows.

The intersection is the fabric; each car's wait is a stalled channel; the loop is the wait-for cycle; breaking one dependency is removing the back-edge. You diagnose by mapping the blocking relationships, not by staring at any one stopped car.

7. Engineering Diagram — the wait-for cycle

A waits on B, B waits on A — a two-agent cycle. A's response acceptance was gated on issuing a request (the forbidden dependency, Chapter 14.3), and B's request needs A to sink the response — so each waits on the other. The back-edge (A's response → request dependency) is the bug; removing it (responses always sinkable) breaks the cycle.

8. Waveform Signature

The signature is valid high and ready low held persistently on both agents, and outstanding flat — no progress. The frozen signal marks the sustained stall. Frozen (non-toggling) links distinguish deadlock from livelock (where valid/ready would toggle as retries fire). A persistent mutual stall with flat outstanding is the deadlock signature.

9. Diagnosis Path

The methodical wait-for reconstruction.

The rule to carry: debug the structure, not the stall. A single stalled channel is ambiguous — it could be benign backpressure (will resolve) or part of a deadlock (never resolves). What disambiguates is the wait-for graph: a cycle means deadlock, no cycle means a resolvable stall. So the diagnosis is graph reconstruction, not staring at one waiting agent. The back-edge — the one dependency that, if removed, makes the graph acyclic — is the bug, and it is almost always the Chapter 14.3 violation: a response or data acceptance that should be unconditional was made to wait on a request.

10. Tracing a Deadlock — a worked trace

The fabric freezes under load; transactions stop completing.

1. Symptom: no progress. Transaction completions stop; the outstanding count is flat. Something is stuck.
2. Frozen, not busy. The stalled channels show valid high, ready low, not toggling — the links are frozen. This is deadlock, not livelock.
3. List the stalled agents. Two agents, A and B, are both stalled — A's response channel and B's request channel are held.
4. Build the wait-for graph. A's response cannot be accepted until A can issue a request (a request credit) — so A waits on B. B's request cannot proceed until B sinks A's response — so B waits on A.
5. Find the cycle. A → B → A — a two-agent cycle. Deadlock confirmed.
6. Back-edge and fix. The forbidden edge is A's response acceptance gated on issuing a request (Chapter 14.3). Removing it — making A's response always sinkable (the drain rule) — breaks the cycle. The fabric flows.

The frozen fabric traced to a two-agent wait cycle and its forbidden back-edge. The DebugLab formalizes this.

11. Detector View — a deadlock detector

Flag a mutual wait held past a threshold with no progress. Representative.

// Representative deadlock detector (educational).
// A deadlock is a persistent wait CYCLE with no progress. Detect the simplest case: a
// MUTUAL wait (A waits on B AND B waits on A) held for more than a threshold number of
// cycles while the outstanding count does not change (no progress). Frozen, not busy.
module chi_deadlock_detect #(parameter THRESH = 64, parameter W = 16) (
  input  logic          clk, rst_n,
  input  logic          a_waits_b,     // agent A is waiting on agent B
  input  logic          b_waits_a,     // agent B is waiting on agent A
  input  logic [W-1:0]  outstanding,   // in-flight transaction count
  output logic          deadlock       // a mutual wait held with no progress
);
  logic [W-1:0] out_q;
  logic [15:0]  stall_cnt;
  logic         cycle, no_progress;
 
  assign cycle       = a_waits_b && b_waits_a;   // a 2-agent wait cycle
  assign no_progress = (outstanding == out_q);   // outstanding unchanged this cycle
  assign deadlock    = cycle && (stall_cnt >= THRESH);
 
  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      out_q <= '0; stall_cnt <= '0;
    end else begin
      out_q <= outstanding;
      // Count cycles the wait cycle persists WITHOUT progress; reset on any progress.
      if (cycle && no_progress) stall_cnt <= stall_cnt + 16'd1;
      else                      stall_cnt <= 16'd0;
    end
  end
endmodule

The same behavior in Verilog-2001:

// Representative deadlock detector (Verilog-2001).
module chi_deadlock_detect #(parameter THRESH = 64, parameter W = 16) (
  input             clk, rst_n, a_waits_b, b_waits_a,
  input  [W-1:0]    outstanding,
  output            deadlock
);
  reg [W-1:0]  out_q;
  reg [15:0]   stall_cnt;
  wire cycle       = a_waits_b & b_waits_a;
  wire no_progress = (outstanding == out_q);
  assign deadlock  = cycle & (stall_cnt >= THRESH);
 
  always @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin out_q <= {W{1'b0}}; stall_cnt <= 16'd0; end
    else begin
      out_q <= outstanding;
      if (cycle & no_progress) stall_cnt <= stall_cnt + 16'd1;
      else                     stall_cnt <= 16'd0;
    end
  end
endmodule

And in VHDL:

-- Representative deadlock detector (VHDL).
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
 
entity chi_deadlock_detect is
  generic ( THRESH : integer := 64; W : integer := 16 );
  port (
    clk, rst_n  : in  std_logic;
    a_waits_b   : in  std_logic;
    b_waits_a   : in  std_logic;
    outstanding : in  unsigned(W-1 downto 0);
    deadlock    : out std_logic
  );
end entity;
 
architecture rtl of chi_deadlock_detect is
  signal out_q     : unsigned(W-1 downto 0) := (others => '0');
  signal stall_cnt : unsigned(15 downto 0) := (others => '0');
  signal cyc, nop  : std_logic;
begin
  cyc      <= a_waits_b and b_waits_a;
  nop      <= '1' when outstanding = out_q else '0';
  deadlock <= '1' when (cyc = '1' and stall_cnt >= THRESH) else '0';
 
  process (clk, rst_n)
  begin
    if rst_n = '0' then
      out_q <= (others => '0'); stall_cnt <= (others => '0');
    elsif rising_edge(clk) then
      out_q <= outstanding;
      if cyc = '1' and nop = '1' then
        stall_cnt <= stall_cnt + 1;
      else
        stall_cnt <= (others => '0');
      end if;
    end if;
  end process;
end architecture;

All three flag deadlock when a mutual wait (the cycle) persists past THRESH cycles without progress (outstanding unchanged). The threshold distinguishes a permanent cycle from a temporary backpressure stall. Extend cycle to a general wait-for cycle for more than two agents. The DebugLab's cycle is a response gated on a request.

12. Assertion View — no permanent wait cycle

The properties formalize liveness: a wait cycle must not persist indefinitely.

// Bind to chi_deadlock_detect.
// 1. A mutual wait must not persist past the threshold (no permanent cycle).
property p_no_permanent_cycle;
  @(posedge clk) disable iff (!rst_n)
    !deadlock;
endproperty
 
// 2. Liveness: an outstanding transaction eventually completes (bounded stall).
//    (strong: outstanding > 0 |-> ##[1:$] (outstanding decreases) -- progress guaranteed)
property p_eventual_progress;
  @(posedge clk) disable iff (!rst_n)
    (outstanding != 0) |-> s_eventually (outstanding < $past(outstanding, THRESH));
endproperty
 
// 3. A response/data acceptance is never gated on a request (the drain rule, 14.3).
//    (structural: sink_resp's logic cone excludes req_credit -- the forbidden back-edge)

The system point, beyond the checks:

Deadlock is unique among the failure families because it is a liveness failure, and liveness cannot be checked the way safety is — there is no bad state to catch, only a bad non-event (something that should happen and doesn't). This is why the detector uses a threshold: you cannot distinguish "stalled forever" from "stalled for a very long time" in finite simulation, so you approximate liveness by declaring a stall past a generous threshold a deadlock. The structural property is the real guarantee — p_no_permanent_cycle is only provable by showing the dependency graph is acyclic (Chapter 14.3), which is a property of the design's connectivity, not its simulated behavior. So deadlock debug has two modes: dynamic (the threshold detector catches a deadlock when it happens, and the wait-for graph localizes it) and static (proving no cycle can exist, by confirming the drain rule holds everywhere). The dynamic mode finds a deadlock; the static mode prevents it. The recurring lesson is that liveness failures need liveness reasoning — about cycles in dependency graphs and eventual progress — not the state-inspection that suffices for safety; and the most reliable fix is structural (break the cycle) rather than parametric (add buffering), because buffering only delays a cycle-based deadlock, never removes it.

• What it proves: a mutual wait does not persist past the threshold.
• What it does not prove: the graph is acyclic in general — that is the structural drain-rule check (14.3).
• Bug signature: deadlock asserted — a persistent wait cycle with no progress.

13. Testbench — a persistent mutual wait must be flagged

Holds a mutual wait with no progress past the threshold and checks the detector fires.

module tb_chi_deadlock_detect;
  localparam THRESH = 8, W = 16;
  logic clk = 0, rst_n = 0, a_waits_b, b_waits_a;
  logic [W-1:0] outstanding;
  logic deadlock;
  int errors = 0;
 
  chi_deadlock_detect #(.THRESH(THRESH), .W(W)) dut (.*);
  always #5 clk = ~clk;
 
  initial begin
    a_waits_b = 0; b_waits_a = 0; outstanding = 16'd3;
    @(posedge clk) rst_n = 1;
 
    // A mutual wait with NO progress (outstanding flat) -> should trip past THRESH.
    @(posedge clk) begin a_waits_b = 1; b_waits_a = 1; end   // the cycle
    repeat (THRESH + 2) @(posedge clk);   // hold with outstanding unchanged
    #1;
    if (!deadlock) begin errors++; $display("FAIL persistent mutual wait NOT flagged"); end
    else $display("PASS deadlock detected: mutual wait held with no progress");
 
    // Break the cycle (drain rule) -> deadlock clears, progress resumes.
    @(posedge clk) begin b_waits_a = 0; outstanding = 16'd2; end   // progress!
    @(posedge clk);
    #1;
    if (deadlock) begin errors++; $display("FAIL deadlock still flagged after progress"); end
    else $display("PASS deadlock cleared once the cycle is broken");
 
    // A brief mutual wait that resolves quickly (backpressure) must NOT be flagged.
    @(posedge clk) begin a_waits_b = 1; b_waits_a = 1; end
    repeat (THRESH - 3) @(posedge clk);   // short stall
    @(posedge clk) begin b_waits_a = 0; outstanding = 16'd1; end  // resolves
    #1;
    if (deadlock) begin errors++; $display("FAIL benign backpressure flagged as deadlock"); end
    else $display("PASS short stall (backpressure) not flagged");
 
    if (errors == 0) $display("ALL TESTS PASSED");
    else             $display("%0d FAILURE(S)", errors);
    $finish;
  end
endmodule

Expected output:

PASS deadlock detected: mutual wait held with no progress
PASS deadlock cleared once the cycle is broken
PASS short stall (backpressure) not flagged
ALL TESTS PASSED

14. DebugLab — a fabric frozen by a response-on-request cycle

symptom: completions stop; outstanding flat; channels valid=1, ready=0, NOT toggling
  -> frozen links -> DEADLOCK (not livelock, which would toggle)
stalled agents: A (response channel), B (request channel)
wait-for graph:
  A: accepts a response only if it can issue a request -> needs a req credit -> WAITS ON B
  B: request needs A to sink the response -> WAITS ON A
  -> A -> B -> A : a 2-agent CYCLE  -> deadlock
back-edge: A's response acceptance gated on a request  (violates the 14.3 drain rule)
correct: responses/data ALWAYS sinkable -> no back-edge -> acyclic -> no deadlock

15. Common Mistakes

• Debugging one stalled channel. Assumption: the stall is the bug. Bug: it is ambiguous. Prevention: reconstruct the wait-for graph.
• Confusing deadlock with livelock. Assumption: frozen equals busy. Bug: different families. Prevention: check if links toggle.
• Adding buffering to fix it. Assumption: more buffers help. Bug: a cycle still deadlocks. Prevention: break the cycle structurally.
• Missing the back-edge. Assumption: the whole graph is the bug. Bug: one edge closes it. Prevention: find the forbidden dependency.
• Relying on timeouts to recover. Assumption: a stuck fabric recovers. Bug: true deadlock does not. Prevention: make it unreachable (14.3).
• Gating a sink on a request. Assumption: batching is fine. Bug: the drain-rule violation. Prevention: responses always sinkable.

16. Engineering Checklist

• On a frozen fabric, confirm deadlock (frozen) vs livelock (busy).
• List the stalled agents (valid high, ready low, outstanding flat).
• Reconstruct the wait-for graph — who waits on whom.
• Find the cycle; identify the back-edge (forbidden dependency).
• Break the cycle — make responses/data unconditionally sinkable (14.3).
• Verify structurally that no sink depends on a request.

17. Key Takeaways

• Deadlock is a cycle of waits — the fabric freezes, nothing completes.
• It is a liveness failure — no progress, no error event.
• The signature is channels stalled (valid high, ready low), outstanding flat.
• Frozen links distinguish deadlock from busy livelock.
• Reconstruct the wait-for graph, find the cycle, remove the back-edge.
• Fix structurally (14.3), not with buffering; the model here is representative.

18. Quick Revision

Deadlock. Deadlock is a liveness failure — a cycle of waits among stalled agents, each waiting on another, so none can progress and the fabric freezes. Unlike every prior (safety) family, there is no wrong result and no error event — the design simply stops. The signature is channels held with valid high and ready low, not toggling, and the outstanding count flat, for an unbounded time — frozen links, which distinguish a true deadlock from a livelock (busy links retrying, no progress). The diagnosis is to reconstruct the wait-for graph among the stalled agents — who is waiting on whom — and find the cycle: a single stall is ambiguous (benign backpressure vs deadlock), but a cycle means permanent. The back-edge that closes the cycle is the forbidden dependency, almost always a response or data acceptance gated on a request being issued — a violation of Chapter 14.3's drain rule that responses and data must always be sinkable. The fix is structural: remove the back-edge so the dependency graph is acyclic (which cannot deadlock) — not more buffering, which only delays a cycle-based deadlock. Deadlock debug has two modes: dynamic (a threshold detector catches a persistent no-progress cycle) and static (prove no cycle can exist). Liveness failures need liveness reasoning — cycles and eventual progress — not state inspection. Representative model; 18.7 debugs credit issues.

Coming Next

Chapter 18.7 — Credit Issues. Deadlock froze the fabric with a dependency cycle; credit issues freeze one channel by starving its flow control. Chapter 18.7 covers credit issues — credit leaks and starvation, the signature of a sender permanently stalled while the receiver has room, and the diagnosis of credit conservation — tracking credits granted, consumed, and returned to find the imbalance.