A directed test pushes three words into a FIFO, waits, then pops them. Another pushes, pops, pushes, pops. Both pass. In the full system, data streams through the FIFO with a push and a pop in almost every cycle, and after a few thousand cycles it reports itself full while holding a single word. The designer had written each case separately and never the case where both happen at once.
Why do bugs that need simultaneous events escape tests, and how are they found?
The obvious tests exercise each operation and check its effect: push and see the count rise, pop and see it fall. Hardware is not a sequence of operations; in a single cycle, many things change at once. The logic for "push and pop together" is a separate case, sometimes a separate branch, sometimes a priority between two conditions that was chosen wrongly. Tests written one operation at a time never take that branch.
Events meeting in one cycle | Typical mistake |
|---|---|
Push and pop on a FIFO | Counted as a push (or a pop) |
A send and a credit return | The return is lost (DCRouter BUG_9) |
A grant and the end of the previous packet | The new owner starts before the old one finishes |
Tails finishing on several outputs at once | Only one is counted (DCRouter BUG_11) |
A request arriving as a block goes to sleep | The request is stranded |
A register write and a hardware update to the same field | One silently wins |
An occupancy counter whose {push, pop} = 11 branch adds one instead of staying put, next to a true occupancy for comparison. Test A pushes and pops in separate cycles; test B streams data through with both in the same cycle.
// A FIFO occupancy counter with a race bug: when a push and a pop happen in the
// same cycle, it adds one instead of staying put. Test A pushes three words, then pops
// them, never both in one cycle: the count is right. Test B streams words through,
// pushing and popping together every cycle: the count drifts upward although the
// FIFO never holds more than one word. The checker compares count with the true
// occupancy after each test.
module tb;
logic clk = 0;
always #5 clk = ~clk;
initial begin $dumpfile("wave.vcd"); $dumpvars(0, tb); end
int cyc = 0;
always @(posedge clk) cyc <= cyc + 1;
logic push = 0, pop = 0;
logic [3:0] count = 0, occ = 0; // count: the design's; occ: the truth
always @(posedge clk) begin
case ({push, pop})
2'b10: count <= count + 4'd1;
2'b01: count <= count - 4'd1;
2'b11: count <= count + 4'd1; // BUG: should stay the same
default: ;
endcase
occ <= occ + (push ? 4'd1 : 4'd0) - (pop ? 4'd1 : 4'd0);
end
// test A: cycles 0-2 push, 3-5 pop. test B: cycle 7 push, cycles 8-11 push and pop, cycle 12 pop
always @(posedge clk) begin
push <= (cyc <= 2) || (cyc >= 7 && cyc <= 11);
pop <= (cyc >= 3 && cyc <= 5) || (cyc >= 8 && cyc <= 12);
end
int a_ok = 0, b_bad = 0;
always @(posedge clk) begin
if (cyc == 6 && count == occ) a_ok = 1;
if (cyc == 14 && count != occ) b_bad = 1;
end
initial begin
#200;
if (a_ok && b_bad) $display("PASS: separate pushes and pops kept the count right; simultaneous ones made it drift to %0d with the FIFO empty", count);
else $display("FAIL: test A ok %0d, test B caught %0d", a_ok, b_bad);
$finish;
end
endmoduleHow to read it, slot by slot:
Slots 0 to 6, test A: three pushes then three pops, never together. count and occ agree at every slot: 1, 2, 3, 2, 1, 0.
Slot 7: test B's first push alone: both go to 1 at slot 8.
Slots 8 to 11: push and pop together every cycle. The true occupancy stays at 1; count climbs 2, 3, 4, 5.
Slot 12: the final pop leaves the FIFO empty, but count only falls to 4. A design using this count would report itself nearly full while empty.
Approach | How it creates simultaneous events |
|---|---|
Random timing | Random gaps and delays make events coincide in many combinations (Part 4) |
Random back-pressure | Stalling consumers at random times collides arrivals with departures |
Streaming traffic | Full-rate traffic makes push and pop together the normal case |
Coverage crosses | A bin for "push and pop in one cycle at each occupancy" shows whether it happened (Part 6) |
Formal | Considers every combination of events in every cycle (Part 7) |
Practice | Effect |
|---|---|
Randomised delays and back-pressure in every agent | Simultaneous events become routine instead of rare |
Cross coverage of concurrent conditions | Missing combinations are visible as holes |
Formal proofs of counters and credit loops | Every simultaneous case checked, not sampled |
DCRouter's Bug Zoo contains four concurrency bugs, including this exact counter mistake inside its FIFO (BUG_2) and a credit return lost when it coincides with a send (BUG_9). The smoke test of lesson 0.7 catches BUG_2 by luck of its timing; BUG_9 only reduces DCRouter's credits, so the router keeps working, more slowly, and no data check ever fails. It is a concurrency bug that looks like a performance bug.
Any two of: a FIFO push and pop, a send and a credit return on one output, tails finishing on two outputs, a grant and a sleep decision, a register write and a counter increment.
If the race loses a resource (like a credit) instead of corrupting data, the design keeps working with less of it, so only throughput suffers.
Hardware changes many things per cycle; many bugs need two events in the same cycle.
Tests that do one operation at a time never reach those cases.
Random timing, back-pressure, coverage crosses and formal reach simultaneous events.