Three tickets, one word

The overnight regression has three new failures in three different blocks, and all three tickets say the same thing: hang. One test ended with a watchdog line. The other two ran until the global timeout, 20,000 cycles of a test that should take 500. Three engineers open three waveforms at the last cycle.

Are these the same kind of failure? What would you measure before anyone scrolls a waveform?

What people usually do, and why it fails

The word hang gets used for anything that stops finishing, so all three get the hang treatment: look at the last cycles for a stuck signal. That works for exactly one of them. In the other two the signals are not stuck at all: requests rise and fall, grants come and go, and the waveform looks busy. One engineer decides the design is "just slow" and raises the timeout; another adds a bigger buffer.

The three classes have different causes. A deadlock is a cycle of waits: fix the arrow that should not exist (who is waiting for whom is the next lesson). A livelock is activity that never completes: look for symmetry in retries. Starvation is one agent never served while others are: look at the arbiter's policy. Starting with the wrong one costs a day. Part 5 showed each class on its own; here the job is to tell them apart on one system, from numbers.

The method: two counters per agent

1. Name the agents that share something: masters, engines, ports, threads of a bench.

2. Define an attempt for each: a step towards a goal that it can take on its own. Here: winning its first resource. On a bus: a request issued, a retry, a NACK received.

3. Define progress for each: a goal reached. Here: a job finished. On a bus: a response received, a word delivered. Never a toggle, a grant on its own or a poll.

4. Count both per agent in windows a few times longer than the longest legal job (64 cycles here, with jobs of about 6).

5. Classify each agent whose progress was zero for two windows in a row: attempts above zero means it is livelocked; zero attempts means it is blocked.

6. Then classify the system: nobody attempting and nobody progressing is a deadlock; a stuck agent that keeps trying is a livelock; blocked agents while others progress is starvation, or a partial deadlock.

One case shares starvation's numbers: a deadlock of some agents while others, which do not need the same resources, keep working. Zero attempts with others progressing means blocked; the wait-for table says whether it is behind an arbiter (starvation) or behind a cycle (a partial deadlock).

On the debug loop this is Observe: it decides which kind of observation comes next.

The picture: three fingerprints

Read across a panel. Empty everywhere is a deadlock. Outline without fill is an agent that tries and fails. Nothing at all for one agent while the others are full is starvation.

Do it: one system, four modes

Three agents share two resources (think of two buffers, two locks, or a bus and a FIFO). A job needs both for three cycles. Each resource has an arbiter that keeps its owner until the owner lets go. The modes are four ways the same design gets built:

• MODE 0, as intended: everyone takes R0 then R1; round-robin arbiters.

• MODE 1: agent 1 takes R1 first and holds it while it waits for R0.

• MODE 2: agent 1 still takes R1 first, but agents 0 and 1 are polite: if the second resource does not come within two cycles, they let go and retry after the same back-off.

• MODE 3: both orders are right, but the arbiters are fixed priority and agents 0 and 1 come back after a one-cycle pause.

The bench carries the liveness monitor from the method, an activity watchdog (no request or grant changed for 200 cycles) and a global timeout.

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

// res_arb: one shared resource (a buffer, a lock, a bus). It has at most one owner; the owner
// keeps it while its request stays high. RR=1 picks round-robin from the last owner, RR=0 is
// fixed priority (requester 0 first).
module res_arb #(parameter bit RR = 1) (
  input  logic       clk, rst_n,
  input  logic [2:0] req,
  output logic [2:0] gnt
);
  logic [1:0] owner, last;                         // owner 3 = free
  logic [1:0] pick;
  always_comb begin
    pick = 2'd3;
    for (int k = 1; k <= 3; k++) begin
      int i;
      i = RR ? (int'(last) + k) % 3 : k - 1;
      if (req[i] && pick == 2'd3) pick = 2'(i);
    end
  end
  always_ff @(posedge clk or negedge rst_n)
    if (!rst_n) begin owner <= 2'd3; last <= 2'd2; end
    else if (owner == 2'd3) begin if (pick != 2'd3) begin owner <= pick; last <= pick; end end
    else if (!req[owner]) owner <= 2'd3;             // released: free for one cycle
  assign gnt = (owner == 2'd3) ? 3'b000 : 3'(1) << owner;
endmodule

// agent: does jobs that need both resources for HOLD cycles. It takes FIRST, then the other.
// POLITE=1: if the second is not granted within 2 cycles it lets go of the first and retries
// after BACKOFF cycles. PAUSE is the gap between jobs.
module agent #(parameter bit FIRST = 0, parameter bit POLITE = 0, parameter int BACKOFF = 4,
               parameter int PAUSE = 2, parameter int HOLD = 3) (
  input  logic       clk, rst_n,
  input  logic [1:0] gnt,                          // gnt[r]: this agent owns resource r
  output logic [1:0] req,
  output logic       got_first,                    // pulse: obtained its first resource (an attempt)
  output logic       done                          // pulse: a job finished (progress)
);
  typedef enum logic [2:0] {IDLE, ASK1, ASK2, WORK, BACK} st_t;
  st_t st;
  logic [7:0] n;
  localparam bit SECOND = !FIRST;
  assign req[FIRST]  = (st == ASK1) || (st == ASK2) || (st == WORK);
  assign req[SECOND] = (st == ASK2) || (st == WORK);
  assign got_first   = (st == ASK1) && gnt[FIRST];
  assign done        = (st == WORK) && (n == 8'(HOLD - 1));
  always_ff @(posedge clk or negedge rst_n)
    if (!rst_n) begin st <= IDLE; n <= '0; end
    else case (st)
      IDLE: if (n >= 8'(PAUSE)) begin st <= ASK1; n <= '0; end else n <= n + 8'd1;
      ASK1: if (gnt[FIRST]) begin st <= ASK2; n <= '0; end
      ASK2: if (gnt[SECOND]) begin st <= WORK; n <= '0; end
            else if (POLITE && n == 8'd1) begin st <= BACK; n <= '0; end
            else n <= n + 8'd1;
      WORK: if (done) begin st <= IDLE; n <= '0; end else n <= n + 8'd1;
      BACK: if (n >= 8'(BACKOFF)) begin st <= ASK1; n <= '0; end else n <= n + 8'd1;
      default: st <= IDLE;
    endcase
endmodule

The design as intended

$ iverilog -g2012 -Plls_tb.MODE=0 -o m0.vvp lls_tb.sv && vvp -n m0.vvp
window 1-64: attempts 3/3/2  jobs done 3/2/2
window 65-128: attempts 3/2/3  jobs done 2/3/3
...
window 385-448: attempts 3/3/2  jobs done 3/2/3
PASS: MODE=0, 20 jobs each in 482 cycles

This is the healthy fingerprint: in every window each agent attempts about as often as it finishes, and every agent finishes something. Keep this line; it is what the broken modes are compared with.

Three broken modes

$ vvp -n m1.vvp
window 1-64: attempts 1/1/0  jobs done 0/0/0
window 65-128: attempts 0/0/0  jobs done 0/0/0
  agent 0: BLOCKED (waits, never served)
  agent 1: BLOCKED (waits, never served)
  agent 2: BLOCKED (waits, never served)
FAIL cycle=128: LIVENESS: DEADLOCK: no attempts and no progress anywhere
...
$ vvp -n m2.vvp
window 1-64: attempts 4/6/3  jobs done 0/0/3
window 65-128: attempts 3/6/3  jobs done 0/0/3
  agent 0: LIVELOCK (tries, never finishes)
  agent 1: LIVELOCK (tries, never finishes)
  agent 2: progress
FAIL cycle=128: LIVENESS: LIVELOCK: a stuck agent keeps trying
...
$ vvp -n m3.vvp
window 1-64: attempts 4/4/0  jobs done 4/3/0
window 65-128: attempts 4/4/0  jobs done 4/4/0
  agent 0: progress
  agent 1: progress
  agent 2: BLOCKED (waits, never served)
FAIL cycle=128: LIVENESS: STARVATION: others progress, a waiting agent is never served
...

• MODE 1: one attempt each for agents 0 and 1 in the first window, then nothing at all. Each won its first resource and is holding it while it waits for the other's. Agent 2 waits behind them for R0. That is a deadlock, and the next step is the wait-for table.

• MODE 2: agents 0 and 1 win their first resource again and again (agent 1 six times a window) and never finish. That is a livelock: two agents giving way to each other in step. Agent 2 slips through the gaps and finishes three jobs a window. The system is not stopped, which is why the class must be decided per agent.

• MODE 3: the two busy agents finish four jobs a window each; agent 2 has not won R0 once. Its request is up the whole time, so it is waiting, not idle. That is starvation, and its owner is whoever chose fixed priority.

All three verdicts arrive at cycle 128, two windows after the trouble starts. The two windows are the rule that keeps a single slow window from being called a hang.

What the usual guards say about the same three runs

$ vvp -n m1.vvp +NOLIVE
FAIL cycle=212: ACTIVITY WATCHDOG: no request or grant changed for 200 cycles
...
$ vvp -n m2.vvp +NOLIVE
FAIL cycle=20000: TIMEOUT: jobs done 0/0/1000
...
$ vvp -n m3.vvp +NOLIVE
FAIL cycle=20000: TIMEOUT: jobs done 1250/1249/0
...

The activity watchdog sees the deadlock, because there the wires really stop. It is blind to the other two: in MODE 2 the requests toggle every few cycles, in MODE 3 the bus is busier than ever. The timeout catches both at cycle 20,000, about 156 times later than the liveness monitor, and its message only hints at the class through the job counts. These are the scene's three tickets: one watchdog line and two timeouts. Verilator 5.048 prints the same lines for all of these runs.

What the evidence says

The class came from two numbers per agent, not from a waveform, and the same pair of counters split all three. The deadlock is the only class with no attempts anywhere; the livelock is the only one where attempts and progress come apart for the same agent; starvation is the only one where one agent's numbers differ from the others'. The monitor's message names the class, the agents and the next step, which is what Observe should hand to Localise.

Traps

Related topics

• Part 7 · Hangs and Deadlocks

• Part 5: starvation and livelock

• Part 5: hangs and deadlocks

• Protocol First Principles: deadlock, livelock and starvation

• Counters and performance probes