Part 4 ended with five Bug Zoo bugs that escaped every test. Three of them, BUG_5 (round-robin pointer stuck), BUG_6 (priority ignored) and BUG_7 (priority applied when disabled), were reached constantly: the random hunt had contention and mixed priorities in every round. They escaped because every check was about data, and these bugs only change which legal order the packets arrive in. This lesson writes the checker they need.

Which bugs does better checking catch, and what does it need from the stimulus?

The obvious answer, and why it breaks

The obvious plan is to add an arbitration checker and expect the three bugs to fall. The checker turned out to need two things beyond its own logic. It needed a model of time it could trust, since arbitration decisions are hidden inside the design (lesson 5.5 tells how two earlier versions failed). And it needed stimulus that makes priorities contend at the moments it can judge. Checking and stimulus are not independent: a checker can only judge situations the test creates.

Build it: the arbitration checker

For each input the checker remembers the headers accepted but not yet started at an output; the oldest is at the head of the FIFO and competes for its output. It judges only packets whose first flit leaves exactly two cycles after the previous tail on the same output: the grant was then made in the cycle the output became free, the one moment the pins prove when arbitration happened. At that moment it checks priority (a waiting high-priority packet never loses to a low one when prio_en is set) and fairness (round-robin lets at most 3 others go first).

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
60
61
62
63
64
65
66
67
68
69

// dcr_fair.svh: DCRouter step 7, arbitration checkers (R6), from the pins. Included inside
// `module tb` after dcr_env.svh and dcr_sva.svh (it uses ctrl_q).
// For each input it remembers, in order, the headers accepted but not yet started at an output;
// the oldest one is at the head of the input FIFO and competes for its output once the input's
// previous packet has left. The grant itself is invisible at the pins: a granted packet may
// wait for a credit before its first flit leaves. So the checker judges only packets whose
// first flit leaves exactly 2 cycles after the previous tail on the same output: the grant was
// then made in the cycle the output became free, which is exactly when inputs contend for it.
// At that grant, every other input whose head packet was already waiting for the output is checked:
//   priority: with prio_en, a waiting high-priority packet must never lose to a low one;
//   fairness: among equal priorities (all packets when prio_en is clear) round-robin lets at
//   most 3 others win before it; a 4th is a failure.
// A higher-priority winner restarts the count, since priority legally reorders the rotation.
typedef struct { int dst, prio, at; } hol_t;
hol_t hol_q [4][$];
bit   hdr_next [4] = '{1, 1, 1, 1};
bit   busy [4] = '{0, 0, 0, 0};                    // input is forwarding a started packet
int   free_at [4] = '{0, 0, 0, 0};                 // cycle its previous packet finished leaving
int   skips [4] = '{0, 0, 0, 0};
int   cyc = 0, prio_viol = 0, fair_viol = 0, max_skips = 0;
bit   started [4] = '{0, 0, 0, 0};                 // an output is between header and tail
int   owner_o [4];                                 // the input whose packet it is sending
int   last_tail [4] = '{-9, -9, -9, -9};          // cycle of the last tail on each output

always @(posedge clk) begin
  cyc++;
  if (!rst) begin
    for (int i = 0; i < 4; i++)                    // headers entering the FIFOs
      if (in_vld[i] && in_rdy[i]) begin
        if (hdr_next[i]) hol_q[i].push_back('{int'(in_data[16*i+14 +: 2]), int'(in_data[16*i+13]), cyc});
        hdr_next[i] = in_last[i];
      end
    for (int o = 0; o < 4; o++) if (out_vld[o]) begin
      logic [15:0] d;
      d = out_data[16*o +: 16];
      if (!started[o]) begin                       // a packet starts on output o
        int s, p;
        s = d[8:7]; p = d[13];
        started[o] = 1;
        owner_o[o] = s;
        if (last_tail[o] + 2 == cyc)               // granted the cycle the output became free
        for (int j = 0; j < 4; j++)
          if (j != s && hol_q[j].size() > 0 && !busy[j] && hol_q[j][0].dst == o &&
              hol_q[j][0].at + 2 <= cyc && free_at[j] + 2 <= cyc) begin
            if (ctrl_q[4] && hol_q[j][0].prio > p) begin
              prio_viol++;
              fail($sformatf("R6: low-priority packet from input %0d won output %0d over a waiting high-priority packet from input %0d", s, o, j));
            end else if (!ctrl_q[4] || hol_q[j][0].prio == p) begin
              skips[j]++;
              if (skips[j] > max_skips) max_skips = skips[j];
              if (skips[j] == 4) begin
                fair_viol++;
                fail($sformatf("R6: input %0d waited while 4 packets from other inputs won output %0d", j, o));
              end
            end else skips[j] = 0;                 // a higher-priority winner: rotation restarts
          end
        if (hol_q[s].size() > 0) void'(hol_q[s].pop_front());
        busy[s] = 1;
        skips[s] = 0;
      end
      if (out_last[o]) begin                       // tails carry no source field
        started[o] = 0;
        busy[owner_o[o]] = 0;
        free_at[owner_o[o]] = cyc;
        last_tail[o] = cyc;
      end
    end
  end
end

The step-7 testbench runs the random hunt with every checker, then two hot-spot phases: all inputs send to output 1, inputs 2 and 3 at high priority, once with prio_en set and once clear.

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

// uses: dcrouter
// DCRouter step 7: the random hunt with every checker so far: the scoreboard and counters
// (lesson 4.1), the local assertions (lesson 5.3) and the arbitration checkers (dcr_fair.svh).
// Two hot-spot phases follow the hunt: all four inputs send to output 1, inputs 2 and 3 at high
// priority, once with prio_en set and once with it clear, so priorities contend every time the
// output frees up. Compile with +define+NO_HOTSPOT to run the hunt alone.
module tb;
  `include "dcr_env.svh"
  `include "dcr_hunt.svh"
  `include "dcr_sva.svh"
  `include "dcr_fair.svh"
  task automatic hot_spot(bit prio_on);
    apb_wr(8'h00, {26'b0, 1'b1, prio_on, 4'hF});
    gap_pct = '{0, 0, 0, 0};
    drain_pct = '{100, 100, 100, 100};
    for (int n = 0; n < 12; n++)
      for (int i = 0; i < 4; i++) queue_pkt(i, 1, i >= 2, 2);
    wait_drain(20000);
  endtask
  initial begin
    reset_dut();
    hunt();
`ifndef NO_HOTSPOT
    hot_spot(1);
    hot_spot(0);
`endif
    final_checks();
    finish($sformatf("checked hunt: %0d packets; most consecutive losses for one waiting input: %0d", sent_pkts.sum(), max_skips));
  end
endmodule

It passes on the clean design, and on the clean design across 30 further seeds; the worst wait any input saw was exactly 3 packets, the round-robin bound. Against the Bug Zoo:

clean design: PASS
  BUG_1  caught  ERROR @855: out0: unexpected flit 3d43
  BUG_2  caught  ERROR @135: out1: flit 0000, expected 3b10 from input 3
  BUG_3  caught  ERROR @4165: out1: out_err 1 on flit 2811, expected 0
  BUG_4  caught  ERROR @189155: out2: out_err 0 on flit 00e2, expected 1
  BUG_5  caught  ERROR @59225: R6: input 3 waited while 4 packets from other inputs won output 1
  BUG_6  caught  ERROR @257235: R6: low-priority packet from input 0 won output 1 over a waiting high-prior
  BUG_7  caught  ERROR @256155: R6: input 0 waited while 4 packets from other inputs won output 1
  BUG_8  caught  ERROR @85: out1: out_err 1 on flit 7580, expected 0
  BUG_9  caught  ERROR @318115: credit audit: 1 flits left output 0 into a stalled sink, expected 4
  BUG_10 caught  ERROR @221575: credit audit: 3 flits left output 0 into a stalled sink, expected 4
  BUG_11 caught  ERROR @245345: PKT_CNT3: read 4a, expected 4c
  BUG_12 caught  ERROR @4975: out3: out_err 1 on flit 0037, expected 0
  BUG_13 caught  ERROR @36725: out2: out_err 0 on flit 0084, expected 1
  BUG_14 caught  ERROR @245435: ERR_CNT2: read 4a, expected 4
  BUG_15 missed  
  BUG_16 missed  
  BUG_17 missed  
  BUG_18 missed  
  BUG_19 missed  
  BUG_20 caught  ERROR @36815: R13: fell asleep in the middle of a packet
  BUG_21 caught  ERROR @39985: R13: in_vld 1000 did not wake the router
  BUG_22 caught  ERROR @260105: credit audit: 2 flits left output 0 into a stalled sink, expected 4
  BUG_23 missed  
  BUG_24 caught  ERROR @785: out0: unexpected flit ff82
caught 18 of 24 bugs

The same testbench compiled with +define+NO_HOTSPOT (the hunt alone, every checker still present):

clean design: PASS
  BUG_1  caught  ERROR @855: out0: unexpected flit 3d43
  BUG_2  caught  ERROR @135: out1: flit 0000, expected 3b10 from input 3
  BUG_3  caught  ERROR @4165: out1: out_err 1 on flit 2811, expected 0
  BUG_4  caught  ERROR @189155: out2: out_err 0 on flit 00e2, expected 1
  BUG_5  caught  ERROR @59225: R6: input 3 waited while 4 packets from other inputs won output 1
  BUG_8  caught  ERROR @85: out1: out_err 1 on flit 7580, expected 0
  BUG_9  caught  ERROR @310245: credit audit: 1 flits left output 0 into a stalled sink, expected 4
  BUG_10 caught  ERROR @216575: credit audit: 3 flits left output 0 into a stalled sink, expected 4
  BUG_11 caught  ERROR @240345: PKT_CNT3: read 4a, expected 4c
  BUG_12 caught  ERROR @4975: out3: out_err 1 on flit 0037, expected 0
  BUG_13 caught  ERROR @36725: out2: out_err 0 on flit 0084, expected 1
  BUG_14 caught  ERROR @240435: ERR_CNT2: read 32, expected 4
  BUG_20 caught  ERROR @36815: R13: fell asleep in the middle of a packet
  BUG_21 caught  ERROR @39985: R13: in_vld 1000 did not wake the router
  BUG_22 caught  ERROR @255105: credit audit: 2 flits left output 0 into a stalled sink, expected 4
  BUG_24 caught  ERROR @785: out0: unexpected flit ff82
caught 16 of 24 bugs

How to read it: 18 caught with the hot spots, 16 without. On the hunt's traffic alone the checker catches BUG_5, because high-numbered inputs starve often enough to exceed the bound at moments it can judge. BUG_6 and BUG_7 need the hot spots: only there do high- and low-priority packets contend for one output every time it frees up. The checker was ready; the stimulus had to create the situation it judges.

The bug-catch matrix after Part 5

How to read it: across all five testbenches, 22 of 24 bugs are caught. Part 5 added BUG_5, BUG_6, BUG_7, the arbitration bugs. The two still missing, BUG_16 and BUG_23, are different in kind: no test ever clears PKT_CNT3, and no test ever disables a port. They were never reached. More checkers cannot help; something must reveal what the stimulus never did, and that is coverage (Part 6).

What Part 5 has shown

• Stimulus reaches, checkers detect: BUG_5, 6, 7 were reached throughout Part 4 and caught only when a checker looked at arbitration.

• Assertions speed up and sharpen detection: BUG_21 reported eleven times earlier, naming the rule (lesson 5.3).

• Checkers need trustworthy models of time: judge only where the pins make timing certain (lesson 5.5).

• Checkers need the right stimulus: hot spots made priority contention common enough to judge.

• Some bugs need neither more stimulus nor more checks, but knowledge of what was never done: Part 6.

How real teams use this

What breaks

Version 2 of this checker (lesson 5.5) did report BUG_9, BUG_10 and BUG_22, as priority violations. The bugs were real; the label was wrong, because lost credits broke the checker's own credit count. A failure message is a hypothesis about the cause, written by a checker with assumptions. The first failing check points where to look, not what is wrong (Part 13).

Key takeaways

• An arbitration checker built from the pins caught the three bugs every data check missed.

• It needed a trustworthy model of hidden timing and stimulus that creates the situations it judges.

• 22 of 24 caught; the last two were never reached, which is what coverage is for.

Related topics

• Part 5 overview: Checking