USB · Module 23
USB FIFO Design
Backpressure takes time to arrive and the writes already in flight land after it, so a watermark set at FULL drops exactly the pipeline depth in bytes — every time the FIFO fills, silently, and only under sustained load.
An endpoint FIFO is a ring buffer with two pointers, and there is nothing interesting about that. What is interesting is one number: the occupancy at which it tells the writer to stop.
Almost everybody gets it wrong the first time, and the wrong answer is wrong by a fixed, knowable amount.
1. The Obvious Answer
Assert backpressure when the FIFO is full. It sounds like a definition rather than a choice:
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
// looks like a tautology. is a data-loss bug.
assign stop_writing = full;The assumption buried in that line is that stop_writing arrives instantly. It does not. It is registered leaving the FIFO, it crosses whatever pipeline sits between the FIFO and whatever is filling it, and it is registered arriving at the writer. Call that round trip LAT cycles.
During every one of those LAT cycles the writer, which has not yet been told anything, keeps writing.
The round trip that the watermark has to pay for
2. The Arithmetic
Let the watermark be WM and suppose the FIFO reaches it at cycle t.
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
cycle t count = WM, almost_full asserts
cycle t gate still reflects cycle t-LAT -> write lands
cycle t+1 gate still stale -> write lands
...
cycle t+LAT-1 -> write lands
cycle t+LAT the writer finally sees it -> stops
LAT writes land after the watermark asserts.
peak occupancy = WM + LAT
and for that to be DEPTH and not one byte more:
WM = DEPTH - LATSo with DEPTH = 16 and LAT = 2 the watermark is 14, and the peak occupancy is exactly 16 — the FIFO is used completely and nothing is dropped.
Set the watermark at DEPTH and the two in-flight writes arrive at a full FIFO. Two bytes disappear, every single time the FIFO fills.
3. Why This Bug Survives to Production
Read the failure mode carefully, because every part of it hides the cause:
| What happens | Why it hides the bug |
|---|---|
| it needs the FIFO to reach the watermark | impossible under light load — so it passes every casual test |
| it needs the reader to fall behind | so it needs sustained traffic, not a burst |
| bytes vanish from the middle of a packet | so the CRC catches it and the packet looks merely corrupt |
| the host retries | and the retry meets the same sustained load and fails identically |
| throughput degrades, nothing errors | so it is filed as a performance problem |
The bug report reads "the device is fine until it gets busy, and then it gets slow", and the person investigating goes looking at clock frequencies. The actual event is silent data loss on a fixed schedule.
4. What We Are Building
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
usb_fifo_watermark #(DEPTH=16, AW=4, DW=8, LAT=2)
inputs outputs
------ -------
wr_req / wr_data wr_gate what the writer SEES (LAT stale)
rd_en wr_push what the writer ISSUED
flush wr_accept what actually LANDED
full / empty / almost_full
count / hwm
overflow a byte was DROPPED
wm_event IDLE / FLOW / INFLIGHT /
BLOCKED / OVERFLOW
n_writes n_reads n_overflows n_underflows
n_blocked n_inflight n_flushesThree separate write signals look like over-engineering until you notice that the bug lives in the gap between them. wr_push is what the writer issued given the stale gate; wr_accept is what the FIFO had room for. When the watermark is right those two are identical on every cycle. When it is wrong, the difference between them is the dropped data.
n_inflight is the other load-bearing counter: writes that landed above the watermark. Those are the writes the reservation exists for, and counting them separately turns "there is room for the in-flight writes" from an argument into a measurement.
5. Verilog-2005 Implementation
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
// usb_fifo_watermark -- an endpoint FIFO, and the one number in it that is
// almost always chosen wrong.
//
// THE NUMBER
//
// An endpoint FIFO tells the writer to stop by asserting a backpressure
// signal. The obvious place to assert it is when the FIFO is FULL.
//
// That is wrong, and it is wrong by a fixed, knowable amount.
//
// Backpressure does not arrive instantly. It is registered on the way out of
// the FIFO, crosses whatever pipeline sits between the FIFO and the writer,
// and is registered on the way in. By the time the writer sees it, LAT cycles
// have passed -- and during every one of those cycles the writer, which knew
// nothing, kept writing.
//
// watermark at FULL -> LAT writes arrive at a full FIFO
// -> LAT bytes dropped
// -> every time, silently, only under load
//
// THE CORRECT WATERMARK
//
// WM = DEPTH - LAT
//
// Assert backpressure LAT slots early, so the LAT writes that are already in
// flight have somewhere to land. Then the peak occupancy is exactly DEPTH:
// not less (which would waste the FIFO) and not more (which would drop data).
//
// count = WM at cycle t, writer stops at t+LAT
// writes land at t, t+1, ... t+LAT-1 -> LAT of them
// peak = WM + LAT = DEPTH. Exactly.
//
// WHY THE BUG IS SO HARD TO FIND
//
// It cannot happen under light load, because the FIFO never reaches the
// watermark. It needs SUSTAINED writes with the reader falling behind -- and
// then it drops bytes in the MIDDLE of a packet, so the CRC catches it, the
// host retries, and the retry hits the same sustained load and fails the same
// way. The symptom is "the device is fine until it is busy, and then it is
// slow", which reads like a performance problem and is data loss.
//
// WHAT THIS BLOCK REPORTS
//
// hwm the highest occupancy ever reached. THE measurement: it must
// equal DEPTH exactly. Lower means the watermark is too early and
// the FIFO is bigger than it needs to be; there is no "higher",
// because higher is dropped data.
// n_inflight writes that landed AFTER the watermark asserted. Per episode
// this must never exceed LAT -- it is the in-flight count made
// observable instead of assumed.
// n_overflows bytes dropped. For any writer that honours wr_gate this is 0,
// and if it is not, the watermark is wrong.
module usb_fifo_watermark #(
parameter integer DEPTH = 16, // FIFO slots
parameter integer AW = 4, // address width: 2**AW == DEPTH
parameter integer DW = 8, // data width
parameter integer LAT = 2 // register stages between FIFO and writer
// (LAT >= 2 for the pipe slice below)
) (
input wire clk,
input wire rst_n,
input wire wr_req, // the writer WANTS to write this cycle
input wire [DW-1:0] wr_data,
input wire rd_en,
input wire flush, // bus reset / SET_CONFIGURATION (ch 21.5)
output wire wr_gate, // what the writer sees: LAT cycles STALE
output wire wr_push, // the write the writer actually issued
output wire wr_accept, // the write that actually landed
output wire [DW-1:0] rd_data,
output wire rd_valid,
output wire empty,
output wire full,
output wire almost_full,
output wire [AW:0] count,
output wire [AW:0] hwm,
output wire overflow, // a byte was DROPPED
output wire underflow,
output wire [2:0] wm_event,
output reg [31:0] n_writes,
output reg [31:0] n_reads,
output reg [31:0] n_overflows,
output reg [31:0] n_underflows,
output reg [31:0] n_blocked,
output reg [31:0] n_inflight,
output reg [31:0] n_flushes
);
// ---- The named outcomes of a cycle. One cycle, one event. ----
localparam [2:0] WM_IDLE = 3'd0; // nothing happened
localparam [2:0] WM_FLOW = 3'd1; // a write landed, below the watermark
localparam [2:0] WM_INFLIGHT = 3'd2; // a write landed ABOVE the watermark:
// one of the LAT already in flight
localparam [2:0] WM_BLOCKED = 3'd3; // the gate refused the write
localparam [2:0] WM_OVERFLOW = 3'd4; // a byte was DROPPED
// ---- THE watermark. ----
//
// DEPTH - LAT, and not one slot either side of it. Too high drops data;
// too low means the FIFO stalls the writer while it still has room, which
// costs throughput and, on an isochronous endpoint, a frame.
localparam integer WM = DEPTH - LAT;
// Compare against the LAST address, never against the count: DEPTH does
// not fit in AW bits (16 in 4 bits is 0), which is the trap of chapter
// 22.2 and chapter 23.2.
localparam [AW-1:0] LAST_ADDR = DEPTH - 1;
localparam [AW:0] DEPTH_C = DEPTH;
localparam [AW:0] WM_C = WM;
localparam [AW:0] ZERO_C = 0;
reg [DW-1:0] mem [0:DEPTH-1];
reg [AW-1:0] wr_ptr_r, rd_ptr_r;
reg [AW:0] count_r, hwm_r;
// ---- The backpressure path made EXPLICIT. ----
//
// This shift register is the whole bug. In a real design it is not a
// shift register -- it is the output flop, a pipeline stage, and the
// writer's input flop, spread across three files -- which is exactly why
// its depth is so easy to forget when the watermark is chosen.
reg [LAT-1:0] af_pipe_r;
assign count = count_r;
assign hwm = hwm_r;
assign empty = (count_r == ZERO_C);
assign full = (count_r == DEPTH_C);
assign almost_full = (count_r >= WM_C);
// The writer sees backpressure as it was LAT cycles ago. It has no way to
// know that, and no way to do better.
assign wr_gate = !af_pipe_r[LAT-1];
assign wr_push = wr_req && wr_gate;
// A push into a full FIFO DROPS the byte. It does not stall the writer --
// the writer is upstream and unaware -- and it does not corrupt an
// address. It simply loses a byte out of the middle of a packet.
assign overflow = wr_push && full;
assign wr_accept = wr_push && !full;
assign rd_valid = rd_en && !empty;
assign underflow = rd_en && empty;
assign rd_data = mem[rd_ptr_r];
assign wm_event = overflow ? WM_OVERFLOW
: (wr_req && !wr_gate) ? WM_BLOCKED
: (wr_accept && almost_full) ? WM_INFLIGHT
: wr_accept ? WM_FLOW
: WM_IDLE;
integer k;
always @(posedge clk or negedge rst_n) begin
if (!rst_n) begin
wr_ptr_r <= {AW{1'b0}};
rd_ptr_r <= {AW{1'b0}};
count_r <= ZERO_C;
hwm_r <= ZERO_C;
af_pipe_r <= {LAT{1'b0}};
n_writes <= 32'd0;
n_reads <= 32'd0;
n_overflows <= 32'd0;
n_underflows <= 32'd0;
n_blocked <= 32'd0;
n_inflight <= 32'd0;
n_flushes <= 32'd0;
for (k = 0; k < DEPTH; k = k + 1) mem[k] <= {DW{1'b0}};
end else begin
if (flush) begin
// A flush empties the FIFO -- AND clears the backpressure pipe.
//
// Leaving the pipe alone is a real bug with a mild symptom: the FIFO
// is empty and the writer is still throttled for LAT cycles, because
// the wire carrying "almost full" is carrying a fact about a FIFO
// that no longer exists. It costs throughput, never data, which is
// why it survives review.
wr_ptr_r <= {AW{1'b0}};
rd_ptr_r <= {AW{1'b0}};
count_r <= ZERO_C;
af_pipe_r <= {LAT{1'b0}};
n_flushes <= n_flushes + 32'd1;
end else begin
af_pipe_r <= {af_pipe_r[LAT-2:0], almost_full};
if (wr_accept) begin
mem[wr_ptr_r] <= wr_data;
wr_ptr_r <= (wr_ptr_r == LAST_ADDR) ? {AW{1'b0}} : wr_ptr_r + 1'b1;
end
if (rd_valid)
rd_ptr_r <= (rd_ptr_r == LAST_ADDR) ? {AW{1'b0}} : rd_ptr_r + 1'b1;
// The count follows what LANDED, never what was requested. Counting
// wr_push instead of wr_accept makes the FIFO believe it holds
// bytes it dropped, and the error is permanent.
if (wr_accept && !rd_valid) count_r <= count_r + 1'b1;
else if (rd_valid && !wr_accept) count_r <= count_r - 1'b1;
if (wr_accept) n_writes <= n_writes + 32'd1;
if (rd_valid) n_reads <= n_reads + 32'd1;
if (overflow) n_overflows <= n_overflows + 32'd1;
if (underflow) n_underflows <= n_underflows + 32'd1;
if (wr_req && !wr_gate) n_blocked <= n_blocked + 32'd1;
if (wr_accept && almost_full)
n_inflight <= n_inflight + 32'd1;
end
// The high-water mark. Sampled from the registered count, so it is the
// occupancy the FIFO actually reached and not a prediction about it.
if (count_r > hwm_r) hwm_r <= count_r;
end
end
endmodule6. SystemVerilog Implementation
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
// usb_fifo_watermark -- an endpoint FIFO, and the one number in it that is
// almost always chosen wrong.
//
// THE NUMBER
//
// An endpoint FIFO tells the writer to stop by asserting a backpressure
// signal. The obvious place to assert it is when the FIFO is FULL.
//
// That is wrong, and it is wrong by a fixed, knowable amount.
//
// Backpressure does not arrive instantly. It is registered on the way out of
// the FIFO, crosses whatever pipeline sits between the FIFO and the writer,
// and is registered on the way in. By the time the writer sees it, LAT cycles
// have passed -- and during every one of those cycles the writer, which knew
// nothing, kept writing.
//
// watermark at FULL -> LAT writes arrive at a full FIFO
// -> LAT bytes dropped
// -> every time, silently, only under load
//
// THE CORRECT WATERMARK
//
// WM = DEPTH - LAT
//
// Assert backpressure LAT slots early, so the LAT writes that are already in
// flight have somewhere to land. Then the peak occupancy is exactly DEPTH:
// not less (which would waste the FIFO) and not more (which would drop data).
//
// count = WM at cycle t, writer stops at t+LAT
// writes land at t, t+1, ... t+LAT-1 -> LAT of them
// peak = WM + LAT = DEPTH. Exactly.
//
// WHY THE BUG IS SO HARD TO FIND
//
// It cannot happen under light load, because the FIFO never reaches the
// watermark. It needs SUSTAINED writes with the reader falling behind -- and
// then it drops bytes in the MIDDLE of a packet, so the CRC catches it, the
// host retries, and the retry hits the same sustained load and fails the same
// way. The symptom is "the device is fine until it is busy, and then it is
// slow", which reads like a performance problem and is data loss.
package usb_wm_pkg;
// The outcomes of one cycle, named. WM_INFLIGHT deserves its own name
// rather than being folded into WM_FLOW: a write that lands above the
// watermark is a write that is only safe because the slots were reserved
// for it, and counting those separately is how the reservation is proved
// rather than assumed.
typedef enum logic [2:0] {
WM_IDLE = 3'd0, // nothing happened
WM_FLOW = 3'd1, // a write landed, below the watermark
WM_INFLIGHT = 3'd2, // a write landed ABOVE the watermark
WM_BLOCKED = 3'd3, // the gate refused the write
WM_OVERFLOW = 3'd4 // a byte was DROPPED
} wm_event_e;
endpackage
module usb_fifo_watermark
import usb_wm_pkg::*;
#(
parameter int DEPTH = 16, // FIFO slots
parameter int AW = 4, // address width: 2**AW == DEPTH
parameter int DW = 8, // data width
parameter int LAT = 2 // register stages between FIFO and writer
// (LAT >= 2 for the pipe slice below)
) (
input logic clk,
input logic rst_n,
input logic wr_req, // the writer WANTS to write this cycle
input logic [DW-1:0] wr_data,
input logic rd_en,
input logic flush, // bus reset / SET_CONFIGURATION (ch 21.5)
output logic wr_gate, // what the writer sees: LAT cycles STALE
output logic wr_push, // the write the writer actually issued
output logic wr_accept, // the write that actually landed
output logic [DW-1:0] rd_data,
output logic rd_valid,
output logic empty,
output logic full,
output logic almost_full,
output logic [AW:0] count,
output logic [AW:0] hwm,
output logic overflow, // a byte was DROPPED
output logic underflow,
output wm_event_e wm_event,
output logic [31:0] n_writes,
output logic [31:0] n_reads,
output logic [31:0] n_overflows,
output logic [31:0] n_underflows,
output logic [31:0] n_blocked,
output logic [31:0] n_inflight,
output logic [31:0] n_flushes
);
// ---- THE watermark. ----
//
// DEPTH - LAT, and not one slot either side of it. Too high drops data;
// too low means the FIFO stalls the writer while it still has room, which
// costs throughput and, on an isochronous endpoint, a frame.
localparam int WM = DEPTH - LAT;
// Compare against the LAST address, never against the count: DEPTH does
// not fit in AW bits (16 in 4 bits is 0), which is the trap of chapter
// 22.2 and chapter 23.2.
localparam logic [AW-1:0] LAST_ADDR = AW'(DEPTH - 1);
localparam logic [AW:0] DEPTH_C = (AW+1)'(DEPTH);
localparam logic [AW:0] WM_C = (AW+1)'(WM);
localparam logic [AW:0] ZERO_C = '0;
logic [DW-1:0] mem [DEPTH];
logic [AW-1:0] wr_ptr_r, rd_ptr_r;
logic [AW:0] count_r, hwm_r;
// ---- The backpressure path made EXPLICIT. ----
//
// This shift register is the whole bug. In a real design it is not a
// shift register -- it is the output flop, a pipeline stage, and the
// writer's input flop, spread across three files -- which is exactly why
// its depth is so easy to forget when the watermark is chosen.
logic [LAT-1:0] af_pipe_r;
assign count = count_r;
assign hwm = hwm_r;
assign empty = (count_r == ZERO_C);
assign full = (count_r == DEPTH_C);
assign almost_full = (count_r >= WM_C);
// The writer sees backpressure as it was LAT cycles ago. It has no way to
// know that, and no way to do better.
assign wr_gate = !af_pipe_r[LAT-1];
assign wr_push = wr_req && wr_gate;
// A push into a full FIFO DROPS the byte. It does not stall the writer --
// the writer is upstream and unaware -- and it does not corrupt an
// address. It simply loses a byte out of the middle of a packet.
assign overflow = wr_push && full;
assign wr_accept = wr_push && !full;
assign rd_valid = rd_en && !empty;
assign underflow = rd_en && empty;
assign rd_data = mem[rd_ptr_r];
always_comb begin
if (overflow) wm_event = WM_OVERFLOW;
else if (wr_req && !wr_gate) wm_event = WM_BLOCKED;
else if (wr_accept && almost_full) wm_event = WM_INFLIGHT;
else if (wr_accept) wm_event = WM_FLOW;
else wm_event = WM_IDLE;
end
always_ff @(posedge clk or negedge rst_n) begin
if (!rst_n) begin
wr_ptr_r <= '0;
rd_ptr_r <= '0;
count_r <= ZERO_C;
hwm_r <= ZERO_C;
af_pipe_r <= '0;
n_writes <= '0;
n_reads <= '0;
n_overflows <= '0;
n_underflows <= '0;
n_blocked <= '0;
n_inflight <= '0;
n_flushes <= '0;
foreach (mem[k]) mem[k] <= '0;
end else begin
if (flush) begin
// A flush empties the FIFO -- AND clears the backpressure pipe.
//
// Leaving the pipe alone is a real bug with a mild symptom: the FIFO
// is empty and the writer is still throttled for LAT cycles, because
// the wire carrying "almost full" is carrying a fact about a FIFO
// that no longer exists. It costs throughput, never data, which is
// why it survives review.
wr_ptr_r <= '0;
rd_ptr_r <= '0;
count_r <= ZERO_C;
af_pipe_r <= '0;
n_flushes <= n_flushes + 32'd1;
end else begin
af_pipe_r <= {af_pipe_r[LAT-2:0], almost_full};
if (wr_accept) begin
mem[wr_ptr_r] <= wr_data;
wr_ptr_r <= (wr_ptr_r == LAST_ADDR) ? '0 : wr_ptr_r + 1'b1;
end
if (rd_valid)
rd_ptr_r <= (rd_ptr_r == LAST_ADDR) ? '0 : rd_ptr_r + 1'b1;
// The count follows what LANDED, never what was requested. Counting
// wr_push instead of wr_accept makes the FIFO believe it holds
// bytes it dropped, and the error is permanent.
if (wr_accept && !rd_valid) count_r <= count_r + 1'b1;
else if (rd_valid && !wr_accept) count_r <= count_r - 1'b1;
if (wr_accept) n_writes <= n_writes + 32'd1;
if (rd_valid) n_reads <= n_reads + 32'd1;
if (overflow) n_overflows <= n_overflows + 32'd1;
if (underflow) n_underflows <= n_underflows + 32'd1;
if (wr_req && !wr_gate) n_blocked <= n_blocked + 32'd1;
if (wr_accept && almost_full)
n_inflight <= n_inflight + 32'd1;
end
// The high-water mark. Sampled from the registered count, so it is the
// occupancy the FIFO actually reached and not a prediction about it.
if (count_r > hwm_r) hwm_r <= count_r;
end
end
endmodule7. VHDL-2008 Implementation
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
-- usb_fifo_watermark -- an endpoint FIFO, and the one number in it that is
-- almost always chosen wrong.
--
-- THE NUMBER
--
-- An endpoint FIFO tells the writer to stop by asserting a backpressure
-- signal. The obvious place to assert it is when the FIFO is FULL.
--
-- That is wrong, and it is wrong by a fixed, knowable amount.
--
-- Backpressure does not arrive instantly. It is registered on the way out of
-- the FIFO, crosses whatever pipeline sits between the FIFO and the writer,
-- and is registered on the way in. By the time the writer sees it, LAT cycles
-- have passed -- and during every one of those cycles the writer, which knew
-- nothing, kept writing.
--
-- watermark at FULL -> LAT writes arrive at a full FIFO
-- -> LAT bytes dropped
-- -> every time, silently, only under load
--
-- THE CORRECT WATERMARK
--
-- WM = DEPTH - LAT
--
-- Assert backpressure LAT slots early, so the LAT writes that are already in
-- flight have somewhere to land. Then the peak occupancy is exactly DEPTH:
-- not less (which would waste the FIFO) and not more (which would drop data).
--
-- count = WM at cycle t, writer stops at t+LAT
-- writes land at t, t+1, ... t+LAT-1 -> LAT of them
-- peak = WM + LAT = DEPTH. Exactly.
--
-- WHY THE BUG IS SO HARD TO FIND
--
-- It cannot happen under light load, because the FIFO never reaches the
-- watermark. It needs SUSTAINED writes with the reader falling behind -- and
-- then it drops bytes in the MIDDLE of a packet, so the CRC catches it, the
-- host retries, and the retry hits the same sustained load and fails the same
-- way. The symptom is "the device is fine until it is busy, and then it is
-- slow", which reads like a performance problem and is data loss.
library ieee;
use ieee.std_logic_1164.all;
package usb_wm_pkg is
-- The outcomes of one cycle, named. WM_INFLIGHT deserves its own name
-- rather than being folded into WM_FLOW: a write that lands above the
-- watermark is a write that is only safe because the slots were reserved
-- for it, and counting those separately is how the reservation is proved
-- rather than assumed.
type wm_event_t is (WM_IDLE, WM_FLOW, WM_INFLIGHT, WM_BLOCKED, WM_OVERFLOW);
function wm_code (e : wm_event_t) return std_logic_vector;
end package usb_wm_pkg;
package body usb_wm_pkg is
-- The encoding is written out rather than derived from the position, so
-- it is pinned to the same numbers the Verilog and SystemVerilog use and
-- a reordering of the type cannot silently change the interface.
function wm_code (e : wm_event_t) return std_logic_vector is
begin
case e is
when WM_IDLE => return "000";
when WM_FLOW => return "001";
when WM_INFLIGHT => return "010";
when WM_BLOCKED => return "011";
when WM_OVERFLOW => return "100";
end case;
end function;
end package body usb_wm_pkg;
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
use work.usb_wm_pkg.all;
entity usb_fifo_watermark is
generic (
DEPTH : integer := 16; -- FIFO slots
AW : integer := 4; -- address width: 2**AW = DEPTH
DW : integer := 8; -- data width
LAT : integer := 2 -- register stages between FIFO and writer
-- (LAT >= 2 for the pipe slice below)
);
port (
clk : in std_logic;
rst_n : in std_logic;
wr_req : in std_logic; -- the writer WANTS to write this cycle
wr_data : in std_logic_vector(DW-1 downto 0);
rd_en : in std_logic;
flush : in std_logic; -- bus reset / SET_CONFIGURATION (ch 21.5)
wr_gate : out std_logic; -- what the writer sees: LAT cycles STALE
wr_push : out std_logic; -- the write the writer actually issued
wr_accept : out std_logic; -- the write that actually landed
rd_data : out std_logic_vector(DW-1 downto 0);
rd_valid : out std_logic;
empty : out std_logic;
full : out std_logic;
almost_full: out std_logic;
count : out std_logic_vector(AW downto 0);
hwm : out std_logic_vector(AW downto 0);
overflow : out std_logic; -- a byte was DROPPED
underflow : out std_logic;
wm_event : out std_logic_vector(2 downto 0);
n_writes : out std_logic_vector(31 downto 0);
n_reads : out std_logic_vector(31 downto 0);
n_overflows : out std_logic_vector(31 downto 0);
n_underflows : out std_logic_vector(31 downto 0);
n_blocked : out std_logic_vector(31 downto 0);
n_inflight : out std_logic_vector(31 downto 0);
n_flushes : out std_logic_vector(31 downto 0)
);
end entity usb_fifo_watermark;
architecture rtl of usb_fifo_watermark is
-- ---- THE watermark. ----
--
-- DEPTH - LAT, and not one slot either side of it. Too high drops data;
-- too low means the FIFO stalls the writer while it still has room, which
-- costs throughput and, on an isochronous endpoint, a frame.
constant WM : integer := DEPTH - LAT;
-- Compare against the LAST address, never against the count: DEPTH does
-- not fit in AW bits (16 in 4 bits is 0), which is the trap of chapter
-- 22.2 and chapter 23.2.
constant LAST_ADDR : unsigned(AW-1 downto 0) := to_unsigned(DEPTH-1, AW);
constant DEPTH_C : unsigned(AW downto 0) := to_unsigned(DEPTH, AW+1);
constant WM_C : unsigned(AW downto 0) := to_unsigned(WM, AW+1);
constant ZERO_C : unsigned(AW downto 0) := (others => '0');
type mem_t is array (0 to DEPTH-1) of std_logic_vector(DW-1 downto 0);
signal mem_r : mem_t := (others => (others => '0'));
signal wr_ptr_r : unsigned(AW-1 downto 0) := (others => '0');
signal rd_ptr_r : unsigned(AW-1 downto 0) := (others => '0');
signal count_r : unsigned(AW downto 0) := (others => '0');
signal hwm_r : unsigned(AW downto 0) := (others => '0');
-- ---- The backpressure path made EXPLICIT. ----
--
-- This shift register is the whole bug. In a real design it is not a
-- shift register -- it is the output flop, a pipeline stage, and the
-- writer's input flop, spread across three files -- which is exactly why
-- its depth is so easy to forget when the watermark is chosen.
signal af_pipe_r : std_logic_vector(LAT-1 downto 0) := (others => '0');
signal s_empty, s_full, s_af : std_logic;
signal s_gate, s_push, s_accept : std_logic;
signal s_rdv, s_unf, s_ovf : std_logic;
signal s_event : wm_event_t;
-- Accumulators are held as unsigned rather than as range-constrained
-- integers: a constrained integer aborts simulation on overflow, which
-- turns a mutation into a crash instead of a measured kill (chapter 22.3).
signal c_writes, c_reads, c_ovf : unsigned(31 downto 0) := (others => '0');
signal c_unf, c_blocked : unsigned(31 downto 0) := (others => '0');
signal c_inflight, c_flushes : unsigned(31 downto 0) := (others => '0');
begin
s_empty <= '1' when count_r = ZERO_C else '0';
s_full <= '1' when count_r = DEPTH_C else '0';
s_af <= '1' when count_r >= WM_C else '0';
-- The writer sees backpressure as it was LAT cycles ago. It has no way to
-- know that, and no way to do better.
s_gate <= not af_pipe_r(LAT-1);
s_push <= wr_req and s_gate;
-- A push into a full FIFO DROPS the byte. It does not stall the writer --
-- the writer is upstream and unaware -- and it does not corrupt an
-- address. It simply loses a byte out of the middle of a packet.
s_ovf <= s_push and s_full;
s_accept <= s_push and (not s_full);
s_rdv <= rd_en and (not s_empty);
s_unf <= rd_en and s_empty;
s_event <= WM_OVERFLOW when s_ovf = '1'
else WM_BLOCKED when (wr_req = '1' and s_gate = '0')
else WM_INFLIGHT when (s_accept = '1' and s_af = '1')
else WM_FLOW when s_accept = '1'
else WM_IDLE;
empty <= s_empty;
full <= s_full;
almost_full <= s_af;
wr_gate <= s_gate;
wr_push <= s_push;
wr_accept <= s_accept;
overflow <= s_ovf;
underflow <= s_unf;
rd_valid <= s_rdv;
rd_data <= mem_r(to_integer(rd_ptr_r));
count <= std_logic_vector(count_r);
hwm <= std_logic_vector(hwm_r);
wm_event <= wm_code(s_event);
n_writes <= std_logic_vector(c_writes);
n_reads <= std_logic_vector(c_reads);
n_overflows <= std_logic_vector(c_ovf);
n_underflows <= std_logic_vector(c_unf);
n_blocked <= std_logic_vector(c_blocked);
n_inflight <= std_logic_vector(c_inflight);
n_flushes <= std_logic_vector(c_flushes);
process (clk, rst_n)
begin
if rst_n = '0' then
wr_ptr_r <= (others => '0');
rd_ptr_r <= (others => '0');
count_r <= (others => '0');
hwm_r <= (others => '0');
af_pipe_r <= (others => '0');
mem_r <= (others => (others => '0'));
c_writes <= (others => '0');
c_reads <= (others => '0');
c_ovf <= (others => '0');
c_unf <= (others => '0');
c_blocked <= (others => '0');
c_inflight <= (others => '0');
c_flushes <= (others => '0');
elsif rising_edge(clk) then
if flush = '1' then
-- A flush empties the FIFO -- AND clears the backpressure pipe.
--
-- Leaving the pipe alone is a real bug with a mild symptom: the FIFO
-- is empty and the writer is still throttled for LAT cycles, because
-- the wire carrying "almost full" is carrying a fact about a FIFO
-- that no longer exists. It costs throughput, never data, which is
-- why it survives review.
wr_ptr_r <= (others => '0');
rd_ptr_r <= (others => '0');
count_r <= (others => '0');
af_pipe_r <= (others => '0');
c_flushes <= c_flushes + 1;
else
af_pipe_r <= af_pipe_r(LAT-2 downto 0) & s_af;
if s_accept = '1' then
mem_r(to_integer(wr_ptr_r)) <= wr_data;
if wr_ptr_r = LAST_ADDR then
wr_ptr_r <= (others => '0');
else
wr_ptr_r <= wr_ptr_r + 1;
end if;
end if;
if s_rdv = '1' then
if rd_ptr_r = LAST_ADDR then
rd_ptr_r <= (others => '0');
else
rd_ptr_r <= rd_ptr_r + 1;
end if;
end if;
-- The count follows what LANDED, never what was requested. Counting
-- s_push instead of s_accept makes the FIFO believe it holds bytes
-- it dropped, and the error is permanent.
if s_accept = '1' and s_rdv = '0' then
count_r <= count_r + 1;
elsif s_rdv = '1' and s_accept = '0' then
count_r <= count_r - 1;
end if;
if s_accept = '1' then c_writes <= c_writes + 1; end if;
if s_rdv = '1' then c_reads <= c_reads + 1; end if;
if s_ovf = '1' then c_ovf <= c_ovf + 1; end if;
if s_unf = '1' then c_unf <= c_unf + 1; end if;
if wr_req = '1' and s_gate = '0' then
c_blocked <= c_blocked + 1;
end if;
if s_accept = '1' and s_af = '1' then
c_inflight <= c_inflight + 1;
end if;
end if;
-- The high-water mark. Sampled from the registered count, so it is the
-- occupancy the FIFO actually reached and not a prediction about it.
if count_r > hwm_r then
hwm_r <= count_r;
end if;
end if;
end process;
end architecture rtl;8. Seeing the In-Flight Writes Land
The watermark asserts, two more writes land, and the FIFO is exactly full
usb_fifo_watermark — WM = DEPTH − LAT = 14
10 cyclesNow the same stimulus with the watermark at DEPTH, which is mutation F1 and is what the obvious answer actually does:
The same sequence with the watermark at FULL — two bytes gone
the F1 mutation — WM = DEPTH = 16
10 cyclesPut the two waveforms side by side. The inputs are identical. The gate behaves identically. The only difference is one constant — and one of them loses two bytes out of every packet that fills the FIFO.
9. The Testbenches
The exhaustive domain is every occupancy, reached for real:
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
17 occupancies (0..DEPTH)
x 8 combinations of {wr_req, rd_en, flush}
x 2 consecutive cycles each
and every occupancy is reached by REAL writes through the
REAL gate. Nothing is forced.
That last point is the design of the suite: a watermark that
is too early CANNOT reach the high occupancies, and the
failure to reach them is a checked result rather than a
silent gap in coverage.Two checks carry most of the weight. The first is the per-episode in-flight tracker:
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
// ---- in-flight bookkeeping, per watermark episode ----
if (e_af && !ep_active) begin ep_active = 1'b1; ep_inflight = 0; end
if (!e_af) ep_active = 1'b0;
if (e_acc && e_af) begin
ep_inflight = ep_inflight + 1;
if (ep_inflight > worst_inflight) worst_inflight = ep_inflight;
check(ep_inflight <= LAT,
"more writes landed above the watermark than there are pipeline stages -- the model of the backpressure path is wrong");
endThe second is the pair of bounds on the high-water mark at the end of the run:
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
// ---- THE measurement. Exactly DEPTH -- both bounds. ----
check(hwm === DEPTH[AW:0],
"the peak occupancy is not exactly DEPTH: below it the watermark is too early and slots are wasted, above it is impossible");
check(worst_inflight == LAT,
"the worst observed run of in-flight writes is not LAT -- the suite never drove the FIFO into the corner the watermark exists for");That second line is the one that is easy to omit. A run whose worst in-flight run is 0 has never tested the reservation at all — it has demonstrated that a FIFO works when it is not under pressure.
9.1 Verilog testbench
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
// Testbench for usb_fifo_watermark (Verilog-2005).
//
// WHAT IS EXHAUSTIVE HERE
//
// Every occupancy from 0 to DEPTH, crossed with every state of the
// backpressure pipe that is reachable at that occupancy, crossed with all
// eight combinations of {wr_req, rd_en, flush}. Every occupancy is REACHED
// by real writes through the real gate -- never forced -- so a watermark
// that stops the writer early simply cannot reach the high occupancies, and
// that failure to reach them is itself a checked result.
//
// THE MEASUREMENT THAT MATTERS
//
// The high-water mark must be EXACTLY DEPTH.
//
// below DEPTH the watermark is too early: the FIFO is larger than the
// design needs, and the writer is throttled while slots
// are free.
// above DEPTH impossible -- the slots do not exist. What actually
// happens is n_overflows > 0 and bytes disappear.
//
// A suite that only checks "no overflow" passes a watermark of 1, which
// wastes fifteen of sixteen slots. Both bounds are checked.
`timescale 1ns/1ps
module tb_fw_v;
localparam integer DEPTH = 16;
localparam integer AW = 4;
localparam integer DW = 8;
localparam integer LAT = 2;
localparam integer WM = DEPTH - LAT;
localparam [2:0] WM_IDLE = 3'd0;
localparam [2:0] WM_FLOW = 3'd1;
localparam [2:0] WM_INFLIGHT = 3'd2;
localparam [2:0] WM_BLOCKED = 3'd3;
localparam [2:0] WM_OVERFLOW = 3'd4;
reg clk = 1'b0, rst_n = 1'b0;
reg wr_req = 1'b0, rd_en = 1'b0, flush = 1'b0;
reg [DW-1:0] wr_data = 8'd0;
wire wr_gate, wr_push, wr_accept, rd_valid;
wire empty, full, almost_full, overflow, underflow;
wire [DW-1:0] rd_data;
wire [AW:0] count, hwm;
wire [2:0] wm_event;
wire [31:0] n_writes, n_reads, n_overflows, n_underflows;
wire [31:0] n_blocked, n_inflight, n_flushes;
usb_fifo_watermark #(.DEPTH(DEPTH), .AW(AW), .DW(DW), .LAT(LAT)) dut (
.clk(clk), .rst_n(rst_n),
.wr_req(wr_req), .wr_data(wr_data), .rd_en(rd_en), .flush(flush),
.wr_gate(wr_gate), .wr_push(wr_push), .wr_accept(wr_accept),
.rd_data(rd_data), .rd_valid(rd_valid),
.empty(empty), .full(full), .almost_full(almost_full),
.count(count), .hwm(hwm),
.overflow(overflow), .underflow(underflow), .wm_event(wm_event),
.n_writes(n_writes), .n_reads(n_reads), .n_overflows(n_overflows),
.n_underflows(n_underflows), .n_blocked(n_blocked),
.n_inflight(n_inflight), .n_flushes(n_flushes)
);
always #5 clk = ~clk;
integer errors = 0;
integer checks = 0;
task check(input cond, input [1023:0] msg);
begin
checks = checks + 1;
if (!cond) begin
errors = errors + 1;
if (errors <= 25)
$display("FAIL @%0t: %0s | cnt=%0d gate=%b af=%b pipe=%b ev=%0d",
$time, msg, count, wr_gate, almost_full, dut.af_pipe_r, wm_event);
end
end
endtask
// ------------------------------------------------------------------
// The shadow FIFO. Independent storage, independent pointers, and an
// independent copy of the backpressure pipe -- because the pipe is the
// thing under test and a model that reads it from the DUT proves nothing.
// ------------------------------------------------------------------
reg [DW-1:0] m_mem [0:DEPTH-1];
integer m_wrp, m_rdp, m_cnt, m_hwm;
reg [LAT-1:0] m_pipe;
integer m_writes, m_reads, m_ovf, m_unf, m_blocked, m_inflight, m_flushes;
// Per-episode in-flight tracking: how many writes have landed since the
// watermark last asserted. The bound is LAT, and it is the whole argument
// for WM = DEPTH - LAT.
integer ep_inflight, worst_inflight;
reg ep_active;
integer seen_cnt [0:DEPTH];
integer n_states, n_transitions;
task model_reset;
integer i;
begin
m_wrp = 0; m_rdp = 0; m_cnt = 0; m_hwm = 0; m_pipe = {LAT{1'b0}};
m_writes = 0; m_reads = 0; m_ovf = 0; m_unf = 0;
m_blocked = 0; m_inflight = 0; m_flushes = 0;
ep_inflight = 0; ep_active = 1'b0;
for (i = 0; i < DEPTH; i = i + 1) m_mem[i] = {DW{1'b0}};
end
endtask
// Apply the inputs, check every combinational output against the model
// BEFORE the clock edge -- see chapter 23.2 -- then step and advance the
// model in lockstep.
task step(input rq, input [DW-1:0] dat, input re, input fl);
reg e_af, e_gate, e_push, e_full, e_empty, e_ovf, e_acc, e_rdv, e_unf;
reg [2:0] e_ev;
begin
wr_req = rq; wr_data = dat; rd_en = re; flush = fl;
#1;
e_af = (m_cnt >= WM);
e_gate = !m_pipe[LAT-1];
e_push = rq && e_gate;
e_full = (m_cnt == DEPTH);
e_empty = (m_cnt == 0);
e_ovf = e_push && e_full;
e_acc = e_push && !e_full;
e_rdv = re && !e_empty;
e_unf = re && e_empty;
e_ev = e_ovf ? WM_OVERFLOW
: (rq && !e_gate) ? WM_BLOCKED
: (e_acc && e_af) ? WM_INFLIGHT
: e_acc ? WM_FLOW
: WM_IDLE;
check(count === m_cnt[AW:0], "count disagrees with the shadow FIFO");
check(empty === e_empty, "empty disagrees");
check(full === e_full, "full disagrees");
check(almost_full === e_af, "almost_full disagrees -- the watermark is not DEPTH-LAT");
check(wr_gate === e_gate, "wr_gate disagrees -- the backpressure pipe is the wrong depth");
check(wr_push === e_push, "wr_push disagrees");
check(wr_accept === e_acc, "wr_accept disagrees");
check(overflow === e_ovf, "overflow disagrees");
check(rd_valid === e_rdv, "rd_valid disagrees");
check(underflow === e_unf, "underflow disagrees");
check(wm_event === e_ev, "wm_event disagrees with the signals it summarises");
// ---- THE hard bound. The slots do not exist above DEPTH. ----
check(m_cnt <= DEPTH, "the shadow FIFO exceeded DEPTH");
check(count <= DEPTH[AW:0], "occupancy exceeded DEPTH -- data has been lost");
// ---- A writer that honours the gate must NEVER overflow. That is
// ---- the entire claim the watermark makes.
check(!e_ovf, "a write was DROPPED although the writer honoured wr_gate -- the watermark is too high");
// ---- FIFO order and data integrity. ----
if (e_rdv)
check(rd_data === m_mem[m_rdp],
"rd_data is not the oldest byte -- FIFO order or storage is broken");
// ---- in-flight bookkeeping, per watermark episode ----
if (e_af && !ep_active) begin ep_active = 1'b1; ep_inflight = 0; end
if (!e_af) ep_active = 1'b0;
if (e_acc && e_af) begin
ep_inflight = ep_inflight + 1;
if (ep_inflight > worst_inflight) worst_inflight = ep_inflight;
check(ep_inflight <= LAT,
"more writes landed above the watermark than there are pipeline stages -- the model of the backpressure path is wrong");
end
if (!fl && m_cnt <= DEPTH) begin
if (seen_cnt[m_cnt] == 0) begin seen_cnt[m_cnt] = 1; n_states = n_states + 1; end
end
n_transitions = n_transitions + 1;
// ---- advance the model ----
if (fl) begin
m_wrp = 0; m_rdp = 0; m_cnt = 0; m_pipe = {LAT{1'b0}};
m_flushes = m_flushes + 1;
end else begin
m_pipe = {m_pipe[LAT-2:0], e_af};
if (e_acc) begin
m_mem[m_wrp] = dat;
m_wrp = (m_wrp == DEPTH-1) ? 0 : m_wrp + 1;
m_writes = m_writes + 1;
if (e_af) m_inflight = m_inflight + 1;
end
if (e_rdv) begin
m_rdp = (m_rdp == DEPTH-1) ? 0 : m_rdp + 1;
m_reads = m_reads + 1;
end
if (e_acc && !e_rdv) m_cnt = m_cnt + 1;
else if (e_rdv && !e_acc) m_cnt = m_cnt - 1;
if (e_ovf) m_ovf = m_ovf + 1;
if (e_unf) m_unf = m_unf + 1;
if (rq && !e_gate) m_blocked = m_blocked + 1;
end
if (m_cnt > m_hwm) m_hwm = m_cnt;
@(posedge clk);
#1;
wr_req = 1'b0; rd_en = 1'b0; flush = 1'b0;
end
endtask
// Empty the FIFO and clear the pipe, the way a bus reset does.
task do_flush;
begin
step(1'b0, 8'd0, 1'b0, 1'b1);
check(count === {(AW+1){1'b0}}, "the FIFO was not emptied by a flush");
check(wr_gate === 1'b1, "the backpressure pipe survived a flush -- the writer is throttled by a fact about a FIFO that no longer exists");
end
endtask
// Drive the FIFO to exactly `target` occupancy using real writes through
// the real gate. If the gate stops us short, that is a finding, not a
// setup problem.
integer fill_i;
task fill_to(input integer target);
begin
do_flush;
fill_i = 0;
while ((m_cnt < target) && (fill_i < 4*DEPTH)) begin
step(1'b1, fill_i[7:0] ^ 8'ha5, 1'b0, 1'b0);
fill_i = fill_i + 1;
end
check(m_cnt == target,
"could not reach the requested occupancy through the gate -- the watermark stops the writer before the FIFO is full");
end
endtask
integer c, combo, it, burst;
integer d_expect;
reg [DW-1:0] rdat;
initial begin
for (c = 0; c <= DEPTH; c = c + 1) seen_cnt[c] = 0;
n_states = 0; n_transitions = 0; worst_inflight = 0;
model_reset;
repeat (3) @(posedge clk);
rst_n = 1'b1;
@(posedge clk); #1;
// ---- Phase A: the state after reset ----
check(count === {(AW+1){1'b0}}, "reset did not empty the FIFO");
check(empty === 1'b1, "reset did not assert empty");
check(full === 1'b0, "reset asserted full");
check(almost_full === 1'b0, "reset asserted almost_full");
check(wr_gate === 1'b1, "reset left the writer throttled");
check(hwm === {(AW+1){1'b0}}, "reset did not clear the high-water mark");
// ---- Phase B: EXHAUSTIVE. Every occupancy x every input combination.
// ---- Each occupancy is reached by real writes through the real gate.
for (c = 0; c <= DEPTH; c = c + 1) begin
for (combo = 0; combo < 8; combo = combo + 1) begin
fill_to(c);
step(combo[0], (c*8 + combo) & 8'hff, combo[1], combo[2]);
// and one more cycle with the same inputs, so a pipe stage that is
// one short is exposed rather than merely delayed
step(combo[0], (c*8 + combo + 1) & 8'hff, combo[1], combo[2]);
end
end
// ---- Phase C: directed. The exact sequence the bug needs. ----
//
// Fill to the watermark, then keep writing. Exactly LAT writes must
// land -- no more, because the slots run out, and no fewer, because
// the writer has not yet been told.
fill_to(WM);
check(almost_full === 1'b1, "the watermark did not assert at DEPTH-LAT");
check(wr_gate === 1'b1, "the writer was throttled before the backpressure could possibly have reached it");
d_expect = WM;
for (it = 0; it < LAT + 4; it = it + 1) begin
step(1'b1, 8'h5a + it[7:0], 1'b0, 1'b0);
if (it < LAT) d_expect = d_expect + 1;
check(m_cnt == d_expect,
"the number of writes that landed after the watermark is not LAT");
end
check(m_cnt == DEPTH,
"the in-flight writes did not fill the FIFO exactly -- the watermark is not DEPTH-LAT");
check(full === 1'b1, "the FIFO should be exactly full after the in-flight writes");
check(n_overflows === 32'd0, "a byte was dropped by a writer that honoured the gate");
// ---- Phase D: sustained load. The writer asks on nearly every cycle
// ---- and the reader falls behind: the only regime in which the bug
// ---- can happen at all.
do_flush;
for (it = 0; it < 12000; it = it + 1)
step(($unsigned($random) % 100) < 92, $random, ($unsigned($random) % 100) < 38, 1'b0);
// ---- Phase E: drain and check FIFO order end to end ----
for (it = 0; it < 3*DEPTH; it = it + 1)
step(1'b0, 8'd0, 1'b1, 1'b0);
check(empty === 1'b1, "the FIFO did not drain");
// ---- Phase F: bursts, flushes, and the pipe surviving one ----
for (it = 0; it < 900; it = it + 1) begin
burst = ($unsigned($random) % 20) + 1;
for (c = 0; c < burst; c = c + 1)
step(1'b1, $random, ($unsigned($random) % 100) < 20, 1'b0);
if (($unsigned($random) % 100) < 30) do_flush;
end
// ---- Phase G: fully random, everything live ----
for (it = 0; it < 24000; it = it + 1)
step(($unsigned($random) % 100) < 55, $random, ($unsigned($random) % 100) < 55,
($unsigned($random) % 1000) < 4);
// ---- Reach and final agreement ----
check(n_writes === m_writes[31:0], "n_writes disagrees with the model");
check(n_reads === m_reads[31:0], "n_reads disagrees with the model");
check(n_overflows === m_ovf[31:0], "n_overflows disagrees with the model");
check(n_underflows === m_unf[31:0], "n_underflows disagrees with the model");
check(n_blocked === m_blocked[31:0], "n_blocked disagrees with the model");
check(n_inflight === m_inflight[31:0], "n_inflight disagrees with the model");
check(n_flushes === m_flushes[31:0], "n_flushes disagrees with the model");
check(hwm === m_hwm[AW:0], "hwm disagrees with the model");
check(n_overflows === 32'd0,
"bytes were dropped although every write honoured wr_gate");
check(n_states == DEPTH + 1,
"not every occupancy from 0 to DEPTH was reached");
// ---- THE measurement. Exactly DEPTH -- both bounds. ----
check(hwm === DEPTH[AW:0],
"the peak occupancy is not exactly DEPTH: below it the watermark is too early and slots are wasted, above it is impossible");
check(worst_inflight == LAT,
"the worst observed run of in-flight writes is not LAT -- the suite never drove the FIFO into the corner the watermark exists for");
check(n_inflight > 32'd0, "no write ever landed above the watermark");
check(n_blocked > 32'd0, "the gate never refused a write");
check(n_flushes > 32'd0, "no flush was ever exercised");
$display("REACH occupancies=%0d/%0d transitions=%0d worst-inflight=%0d of %0d HWM=%0d of %0d",
n_states, DEPTH+1, n_transitions, worst_inflight, LAT, hwm, DEPTH);
$display("COUNTERS writes=%0d reads=%0d overflow=%0d underflow=%0d blocked=%0d inflight=%0d flushes=%0d",
n_writes, n_reads, n_overflows, n_underflows, n_blocked, n_inflight, n_flushes);
$display("%0s: %0d errors in %0d checks", (errors==0)?"PASS":"FAIL", errors, checks);
$finish;
end
endmodule9.2 SystemVerilog testbench
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
// Testbench for usb_fifo_watermark (SystemVerilog).
//
// WHAT IS EXHAUSTIVE HERE
//
// Every occupancy from 0 to DEPTH, crossed with every state of the
// backpressure pipe that is reachable at that occupancy, crossed with all
// eight combinations of {wr_req, rd_en, flush}. Every occupancy is REACHED
// by real writes through the real gate -- never forced -- so a watermark
// that stops the writer early simply cannot reach the high occupancies, and
// that failure to reach them is itself a checked result.
//
// THE MEASUREMENT THAT MATTERS
//
// The high-water mark must be EXACTLY DEPTH.
//
// below DEPTH the watermark is too early: the FIFO is larger than the
// design needs, and the writer is throttled while slots
// are free.
// above DEPTH impossible -- the slots do not exist. What actually
// happens is n_overflows > 0 and bytes disappear.
//
// A suite that only checks "no overflow" passes a watermark of 1, which
// wastes fifteen of sixteen slots. Both bounds are checked.
`timescale 1ns/1ps
module tb_fw_sv;
import usb_wm_pkg::*;
localparam int DEPTH = 16;
localparam int AW = 4;
localparam int DW = 8;
localparam int LAT = 2;
localparam int WM = DEPTH - LAT;
logic clk = 1'b0, rst_n = 1'b0;
logic wr_req = 1'b0, rd_en = 1'b0, flush = 1'b0;
logic [DW-1:0] wr_data = '0;
logic wr_gate, wr_push, wr_accept, rd_valid;
logic empty, full, almost_full, overflow, underflow;
logic [DW-1:0] rd_data;
logic [AW:0] count, hwm;
wm_event_e wm_event;
logic [31:0] n_writes, n_reads, n_overflows, n_underflows;
logic [31:0] n_blocked, n_inflight, n_flushes;
usb_fifo_watermark #(.DEPTH(DEPTH), .AW(AW), .DW(DW), .LAT(LAT)) dut (.*);
always #5 clk = ~clk;
int errors = 0, checks = 0;
task automatic check(input logic cond, input string msg);
checks++;
if (!cond) begin
errors++;
if (errors <= 25)
$display("FAIL @%0t: %0s | cnt=%0d gate=%b af=%b pipe=%b ev=%0d",
$time, msg, count, wr_gate, almost_full, dut.af_pipe_r, wm_event);
end
endtask
// ------------------------------------------------------------------
// The shadow FIFO. Independent storage, independent pointers, and an
// independent copy of the backpressure pipe -- because the pipe is the
// thing under test and a model that reads it from the DUT proves nothing.
// ------------------------------------------------------------------
logic [DW-1:0] m_mem [DEPTH];
int m_wrp, m_rdp, m_cnt, m_hwm;
logic [LAT-1:0] m_pipe;
int m_writes, m_reads, m_ovf, m_unf, m_blocked, m_inflight, m_flushes;
// Per-episode in-flight tracking: how many writes have landed since the
// watermark last asserted. The bound is LAT, and it is the whole argument
// for WM = DEPTH - LAT.
int ep_inflight, worst_inflight;
logic ep_active;
int seen_cnt [DEPTH+1];
int n_states, n_transitions;
task automatic model_reset();
m_wrp = 0; m_rdp = 0; m_cnt = 0; m_hwm = 0; m_pipe = '0;
m_writes = 0; m_reads = 0; m_ovf = 0; m_unf = 0;
m_blocked = 0; m_inflight = 0; m_flushes = 0;
ep_inflight = 0; ep_active = 1'b0;
foreach (m_mem[i]) m_mem[i] = '0;
endtask
// Apply the inputs, check every combinational output against the model
// BEFORE the clock edge -- see chapter 23.2 -- then step and advance the
// model in lockstep.
task automatic step(input logic rq, input logic [DW-1:0] dat,
input logic re, input logic fl);
logic e_af, e_gate, e_push, e_full, e_empty, e_ovf, e_acc, e_rdv, e_unf;
wm_event_e e_ev;
wr_req = rq; wr_data = dat; rd_en = re; flush = fl;
#1;
e_af = (m_cnt >= WM);
e_gate = !m_pipe[LAT-1];
e_push = rq && e_gate;
e_full = (m_cnt == DEPTH);
e_empty = (m_cnt == 0);
e_ovf = e_push && e_full;
e_acc = e_push && !e_full;
e_rdv = re && !e_empty;
e_unf = re && e_empty;
// Written as if/else rather than a ternary chain: an enum-valued
// ternary needs an explicit cast in Icarus, and the cast would turn a
// type error into a silent truncation.
if (e_ovf) e_ev = WM_OVERFLOW;
else if (rq && !e_gate) e_ev = WM_BLOCKED;
else if (e_acc && e_af) e_ev = WM_INFLIGHT;
else if (e_acc) e_ev = WM_FLOW;
else e_ev = WM_IDLE;
check(count === (AW+1)'(m_cnt), "count disagrees with the shadow FIFO");
check(empty === e_empty, "empty disagrees");
check(full === e_full, "full disagrees");
check(almost_full === e_af, "almost_full disagrees -- the watermark is not DEPTH-LAT");
check(wr_gate === e_gate, "wr_gate disagrees -- the backpressure pipe is the wrong depth");
check(wr_push === e_push, "wr_push disagrees");
check(wr_accept === e_acc, "wr_accept disagrees");
check(overflow === e_ovf, "overflow disagrees");
check(rd_valid === e_rdv, "rd_valid disagrees");
check(underflow === e_unf, "underflow disagrees");
check(wm_event === e_ev, "wm_event disagrees with the signals it summarises");
// ---- THE hard bound. The slots do not exist above DEPTH. ----
check(m_cnt <= DEPTH, "the shadow FIFO exceeded DEPTH");
check(count <= (AW+1)'(DEPTH), "occupancy exceeded DEPTH -- data has been lost");
// ---- A writer that honours the gate must NEVER overflow. That is
// ---- the entire claim the watermark makes.
check(!e_ovf, "a write was DROPPED although the writer honoured wr_gate -- the watermark is too high");
// ---- FIFO order and data integrity. ----
if (e_rdv)
check(rd_data === m_mem[m_rdp],
"rd_data is not the oldest byte -- FIFO order or storage is broken");
// ---- in-flight bookkeeping, per watermark episode ----
if (e_af && !ep_active) begin ep_active = 1'b1; ep_inflight = 0; end
if (!e_af) ep_active = 1'b0;
if (e_acc && e_af) begin
ep_inflight++;
if (ep_inflight > worst_inflight) worst_inflight = ep_inflight;
check(ep_inflight <= LAT,
"more writes landed above the watermark than there are pipeline stages -- the model of the backpressure path is wrong");
end
if (!fl && m_cnt <= DEPTH)
if (seen_cnt[m_cnt] == 0) begin seen_cnt[m_cnt] = 1; n_states++; end
n_transitions++;
// ---- advance the model ----
if (fl) begin
m_wrp = 0; m_rdp = 0; m_cnt = 0; m_pipe = '0;
m_flushes++;
end else begin
m_pipe = {m_pipe[LAT-2:0], e_af};
if (e_acc) begin
m_mem[m_wrp] = dat;
m_wrp = (m_wrp == DEPTH-1) ? 0 : m_wrp + 1;
m_writes++;
if (e_af) m_inflight++;
end
if (e_rdv) begin
m_rdp = (m_rdp == DEPTH-1) ? 0 : m_rdp + 1;
m_reads++;
end
if (e_acc && !e_rdv) m_cnt++;
else if (e_rdv && !e_acc) m_cnt--;
if (e_ovf) m_ovf++;
if (e_unf) m_unf++;
if (rq && !e_gate) m_blocked++;
end
if (m_cnt > m_hwm) m_hwm = m_cnt;
@(posedge clk);
#1;
wr_req = 1'b0; rd_en = 1'b0; flush = 1'b0;
endtask
// Empty the FIFO and clear the pipe, the way a bus reset does.
task automatic do_flush();
step(1'b0, '0, 1'b0, 1'b1);
check(count === '0, "the FIFO was not emptied by a flush");
check(wr_gate === 1'b1, "the backpressure pipe survived a flush -- the writer is throttled by a fact about a FIFO that no longer exists");
endtask
// Drive the FIFO to exactly `target` occupancy using real writes through
// the real gate. If the gate stops us short, that is a finding, not a
// setup problem.
task automatic fill_to(input int target);
int i;
do_flush();
i = 0;
while ((m_cnt < target) && (i < 4*DEPTH)) begin
step(1'b1, DW'(i) ^ 8'ha5, 1'b0, 1'b0);
i++;
end
check(m_cnt == target,
"could not reach the requested occupancy through the gate -- the watermark stops the writer before the FIFO is full");
endtask
int c, combo, it, burst, d_expect;
initial begin
foreach (seen_cnt[i]) seen_cnt[i] = 0;
n_states = 0; n_transitions = 0; worst_inflight = 0;
model_reset();
repeat (3) @(posedge clk);
rst_n = 1'b1;
@(posedge clk); #1;
// ---- Phase A: the state after reset ----
check(count === '0, "reset did not empty the FIFO");
check(empty === 1'b1, "reset did not assert empty");
check(full === 1'b0, "reset asserted full");
check(almost_full === 1'b0, "reset asserted almost_full");
check(wr_gate === 1'b1, "reset left the writer throttled");
check(hwm === '0, "reset did not clear the high-water mark");
// ---- Phase B: EXHAUSTIVE. Every occupancy x every input combination.
// ---- Each occupancy is reached by real writes through the real gate.
for (c = 0; c <= DEPTH; c++) begin
for (combo = 0; combo < 8; combo++) begin
fill_to(c);
step(combo[0], DW'(c*8 + combo), combo[1], combo[2]);
// and one more cycle with the same inputs, so a pipe stage that is
// one short is exposed rather than merely delayed
step(combo[0], DW'(c*8 + combo + 1), combo[1], combo[2]);
end
end
// ---- Phase C: directed. The exact sequence the bug needs. ----
//
// Fill to the watermark, then keep writing. Exactly LAT writes must
// land -- no more, because the slots run out, and no fewer, because
// the writer has not yet been told.
fill_to(WM);
check(almost_full === 1'b1, "the watermark did not assert at DEPTH-LAT");
check(wr_gate === 1'b1, "the writer was throttled before the backpressure could possibly have reached it");
d_expect = WM;
for (it = 0; it < LAT + 4; it++) begin
step(1'b1, 8'h5a + DW'(it), 1'b0, 1'b0);
if (it < LAT) d_expect++;
check(m_cnt == d_expect,
"the number of writes that landed after the watermark is not LAT");
end
check(m_cnt == DEPTH,
"the in-flight writes did not fill the FIFO exactly -- the watermark is not DEPTH-LAT");
check(full === 1'b1, "the FIFO should be exactly full after the in-flight writes");
check(n_overflows === 32'd0, "a byte was dropped by a writer that honoured the gate");
// ---- Phase D: sustained load. The writer asks on nearly every cycle
// ---- and the reader falls behind: the only regime in which the bug
// ---- can happen at all.
do_flush();
for (it = 0; it < 12000; it++)
step($urandom_range(0,99) < 92, DW'($urandom()),
$urandom_range(0,99) < 38, 1'b0);
// ---- Phase E: drain and check FIFO order end to end ----
for (it = 0; it < 3*DEPTH; it++)
step(1'b0, '0, 1'b1, 1'b0);
check(empty === 1'b1, "the FIFO did not drain");
// ---- Phase F: bursts, flushes, and the pipe surviving one ----
for (it = 0; it < 900; it++) begin
burst = $urandom_range(1, 20);
for (c = 0; c < burst; c++)
step(1'b1, DW'($urandom()), $urandom_range(0,99) < 20, 1'b0);
if ($urandom_range(0,99) < 30) do_flush();
end
// ---- Phase G: fully random, everything live ----
for (it = 0; it < 24000; it++)
step($urandom_range(0,99) < 55, DW'($urandom()),
$urandom_range(0,99) < 55, $urandom_range(0,999) < 4);
// ---- Reach and final agreement ----
check(n_writes === 32'(m_writes), "n_writes disagrees with the model");
check(n_reads === 32'(m_reads), "n_reads disagrees with the model");
check(n_overflows === 32'(m_ovf), "n_overflows disagrees with the model");
check(n_underflows === 32'(m_unf), "n_underflows disagrees with the model");
check(n_blocked === 32'(m_blocked), "n_blocked disagrees with the model");
check(n_inflight === 32'(m_inflight), "n_inflight disagrees with the model");
check(n_flushes === 32'(m_flushes), "n_flushes disagrees with the model");
check(hwm === (AW+1)'(m_hwm), "hwm disagrees with the model");
check(n_overflows === 32'd0,
"bytes were dropped although every write honoured wr_gate");
check(n_states == DEPTH + 1,
"not every occupancy from 0 to DEPTH was reached");
// ---- THE measurement. Exactly DEPTH -- both bounds. ----
check(hwm === (AW+1)'(DEPTH),
"the peak occupancy is not exactly DEPTH: below it the watermark is too early and slots are wasted, above it is impossible");
check(worst_inflight == LAT,
"the worst observed run of in-flight writes is not LAT -- the suite never drove the FIFO into the corner the watermark exists for");
check(n_inflight > 32'd0, "no write ever landed above the watermark");
check(n_blocked > 32'd0, "the gate never refused a write");
check(n_flushes > 32'd0, "no flush was ever exercised");
$display("REACH occupancies=%0d/%0d transitions=%0d worst-inflight=%0d of %0d HWM=%0d of %0d",
n_states, DEPTH+1, n_transitions, worst_inflight, LAT, hwm, DEPTH);
$display("COUNTERS writes=%0d reads=%0d overflow=%0d underflow=%0d blocked=%0d inflight=%0d flushes=%0d",
n_writes, n_reads, n_overflows, n_underflows, n_blocked, n_inflight, n_flushes);
$display("%0s: %0d errors in %0d checks", (errors==0)?"PASS":"FAIL", errors, checks);
$finish;
end
endmodule9.3 VHDL testbench
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
-- Testbench for usb_fifo_watermark (VHDL-2008).
--
-- WHAT IS EXHAUSTIVE HERE
--
-- Every occupancy from 0 to DEPTH, crossed with every state of the
-- backpressure pipe that is reachable at that occupancy, crossed with all
-- eight combinations of (wr_req, rd_en, flush). Every occupancy is REACHED
-- by real writes through the real gate -- never forced -- so a watermark
-- that stops the writer early simply cannot reach the high occupancies, and
-- that failure to reach them is itself a checked result.
--
-- THE MEASUREMENT THAT MATTERS
--
-- The high-water mark must be EXACTLY DEPTH.
--
-- below DEPTH the watermark is too early: the FIFO is larger than the
-- design needs, and the writer is throttled while slots
-- are free.
-- above DEPTH impossible -- the slots do not exist. What actually
-- happens is n_overflows > 0 and bytes disappear.
--
-- A suite that only checks "no overflow" passes a watermark of 1, which
-- wastes fifteen of sixteen slots. Both bounds are checked.
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
use std.textio.all;
use work.usb_wm_pkg.all;
entity tb_fw_vhdl is
end entity tb_fw_vhdl;
architecture sim of tb_fw_vhdl is
constant DEPTH : integer := 16;
constant AW : integer := 4;
constant DW : integer := 8;
constant LAT : integer := 2;
constant WM : integer := DEPTH - LAT;
signal clk : std_logic := '0';
signal rst_n : std_logic := '0';
signal done : boolean := false;
signal wr_req : std_logic := '0';
signal rd_en : std_logic := '0';
signal flush : std_logic := '0';
signal wr_data : std_logic_vector(DW-1 downto 0) := (others => '0');
signal wr_gate, wr_push, wr_accept, rd_valid : std_logic;
signal empty, full, almost_full, overflow, underflow : std_logic;
signal rd_data : std_logic_vector(DW-1 downto 0);
signal count, hwm : std_logic_vector(AW downto 0);
signal wm_event : std_logic_vector(2 downto 0);
signal n_writes, n_reads, n_overflows, n_underflows : std_logic_vector(31 downto 0);
signal n_blocked, n_inflight, n_flushes : std_logic_vector(31 downto 0);
begin
dut : entity work.usb_fifo_watermark
generic map (DEPTH => DEPTH, AW => AW, DW => DW, LAT => LAT)
port map (
clk => clk, rst_n => rst_n,
wr_req => wr_req, wr_data => wr_data, rd_en => rd_en, flush => flush,
wr_gate => wr_gate, wr_push => wr_push, wr_accept => wr_accept,
rd_data => rd_data, rd_valid => rd_valid,
empty => empty, full => full, almost_full => almost_full,
count => count, hwm => hwm,
overflow => overflow, underflow => underflow, wm_event => wm_event,
n_writes => n_writes, n_reads => n_reads, n_overflows => n_overflows,
n_underflows => n_underflows, n_blocked => n_blocked,
n_inflight => n_inflight, n_flushes => n_flushes
);
clk <= (not clk) after 5 ns when not done else '0';
stim : process
type mem_arr is array (0 to DEPTH-1) of std_logic_vector(DW-1 downto 0);
type seen_arr is array (0 to DEPTH) of integer;
variable errors, checks : integer := 0;
-- ----------------------------------------------------------------
-- The shadow FIFO. Independent storage, independent pointers, and an
-- independent copy of the backpressure pipe -- because the pipe is the
-- thing under test and a model that reads it from the DUT proves
-- nothing.
-- ----------------------------------------------------------------
variable m_mem : mem_arr := (others => (others => '0'));
variable m_wrp, m_rdp, m_cnt, m_hwm : integer := 0;
variable m_pipe : std_logic_vector(LAT-1 downto 0) := (others => '0');
variable m_writes, m_reads, m_ovf, m_unf : integer := 0;
variable m_blocked, m_inflight, m_flushes : integer := 0;
-- Per-episode in-flight tracking: how many writes have landed since the
-- watermark last asserted. The bound is LAT, and it is the whole
-- argument for WM = DEPTH - LAT.
variable ep_inflight, worst_inflight : integer := 0;
variable ep_active : boolean := false;
variable seen_cnt : seen_arr := (others => 0);
variable n_states, n_transitions : integer := 0;
-- A deterministic LFSR, so a rerun reproduces exactly the same traffic.
variable lfsr : unsigned(31 downto 0) := x"1234ABCD";
impure function rnd32 return unsigned is
begin
lfsr := lfsr(30 downto 0) &
(lfsr(31) xor lfsr(21) xor lfsr(1) xor lfsr(0));
return lfsr;
end function;
-- VHDL does not allow slicing a function result directly, so the byte
-- is taken through a variable.
impure function rnd_byte return std_logic_vector is
variable v : unsigned(31 downto 0);
begin
v := rnd32;
return std_logic_vector(v(DW-1 downto 0));
end function;
-- Only the low 30 bits are converted: a full 32-bit unsigned does not
-- fit in VHDL's INTEGER, and to_integer aborts the run rather than
-- wrapping -- which would turn a stimulus detail into a fatal error.
impure function rnd_nat return integer is
variable v : unsigned(31 downto 0);
begin
v := rnd32;
return to_integer(v(29 downto 0));
end function;
impure function rnd_lt (pct, base : integer) return std_logic is
begin
if (rnd_nat mod base) < pct then return '1'; else return '0'; end if;
end function;
impure function rnd_range (lo, hi : integer) return integer is
begin
return lo + (rnd_nat mod (hi - lo + 1));
end function;
procedure chk (cond : boolean; msg : string) is
begin
checks := checks + 1;
if not cond then
errors := errors + 1;
if errors <= 25 then
report "FAIL: " & msg &
" | cnt=" & integer'image(m_cnt) &
" gate=" & std_logic'image(wr_gate) &
" af=" & std_logic'image(almost_full)
severity note;
end if;
end if;
end procedure;
-- Apply the inputs, check every combinational output against the model
-- BEFORE the clock edge -- see chapter 23.2 -- then step and advance the
-- model in lockstep.
procedure step (rq : std_logic; dat : std_logic_vector(DW-1 downto 0);
re : std_logic; fl : std_logic) is
variable e_af, e_gate, e_push, e_full, e_empty : boolean;
variable e_ovf, e_acc, e_rdv, e_unf : boolean;
variable e_ev : wm_event_t;
begin
wr_req <= rq; wr_data <= dat; rd_en <= re; flush <= fl;
wait for 1 ns;
e_af := (m_cnt >= WM);
e_gate := (m_pipe(LAT-1) = '0');
e_push := (rq = '1') and e_gate;
e_full := (m_cnt = DEPTH);
e_empty := (m_cnt = 0);
e_ovf := e_push and e_full;
e_acc := e_push and (not e_full);
e_rdv := (re = '1') and (not e_empty);
e_unf := (re = '1') and e_empty;
if e_ovf then e_ev := WM_OVERFLOW;
elsif (rq = '1') and (not e_gate) then e_ev := WM_BLOCKED;
elsif e_acc and e_af then e_ev := WM_INFLIGHT;
elsif e_acc then e_ev := WM_FLOW;
else e_ev := WM_IDLE;
end if;
chk(unsigned(count) = to_unsigned(m_cnt, AW+1), "count disagrees with the shadow FIFO");
chk((empty = '1') = e_empty, "empty disagrees");
chk((full = '1') = e_full, "full disagrees");
chk((almost_full = '1') = e_af, "almost_full disagrees -- the watermark is not DEPTH-LAT");
chk((wr_gate = '1') = e_gate, "wr_gate disagrees -- the backpressure pipe is the wrong depth");
chk((wr_push = '1') = e_push, "wr_push disagrees");
chk((wr_accept = '1') = e_acc, "wr_accept disagrees");
chk((overflow = '1') = e_ovf, "overflow disagrees");
chk((rd_valid = '1') = e_rdv, "rd_valid disagrees");
chk((underflow = '1') = e_unf, "underflow disagrees");
chk(wm_event = wm_code(e_ev), "wm_event disagrees with the signals it summarises");
-- ---- THE hard bound. The slots do not exist above DEPTH. ----
chk(m_cnt <= DEPTH, "the shadow FIFO exceeded DEPTH");
chk(unsigned(count) <= to_unsigned(DEPTH, AW+1),
"occupancy exceeded DEPTH -- data has been lost");
-- ---- A writer that honours the gate must NEVER overflow. That is
-- ---- the entire claim the watermark makes.
chk(not e_ovf, "a write was DROPPED although the writer honoured wr_gate -- the watermark is too high");
-- ---- FIFO order and data integrity. ----
if e_rdv then
chk(rd_data = m_mem(m_rdp),
"rd_data is not the oldest byte -- FIFO order or storage is broken");
end if;
-- ---- in-flight bookkeeping, per watermark episode ----
if e_af and not ep_active then ep_active := true; ep_inflight := 0; end if;
if not e_af then ep_active := false; end if;
if e_acc and e_af then
ep_inflight := ep_inflight + 1;
if ep_inflight > worst_inflight then worst_inflight := ep_inflight; end if;
chk(ep_inflight <= LAT,
"more writes landed above the watermark than there are pipeline stages -- the model of the backpressure path is wrong");
end if;
if (fl = '0') and (m_cnt <= DEPTH) then
if seen_cnt(m_cnt) = 0 then
seen_cnt(m_cnt) := 1;
n_states := n_states + 1;
end if;
end if;
n_transitions := n_transitions + 1;
-- ---- advance the model ----
if fl = '1' then
m_wrp := 0; m_rdp := 0; m_cnt := 0;
m_pipe := (others => '0');
m_flushes := m_flushes + 1;
else
if e_af then
m_pipe := m_pipe(LAT-2 downto 0) & '1';
else
m_pipe := m_pipe(LAT-2 downto 0) & '0';
end if;
if e_acc then
m_mem(m_wrp) := dat;
if m_wrp = DEPTH-1 then m_wrp := 0; else m_wrp := m_wrp + 1; end if;
m_writes := m_writes + 1;
if e_af then m_inflight := m_inflight + 1; end if;
end if;
if e_rdv then
if m_rdp = DEPTH-1 then m_rdp := 0; else m_rdp := m_rdp + 1; end if;
m_reads := m_reads + 1;
end if;
if e_acc and not e_rdv then m_cnt := m_cnt + 1;
elsif e_rdv and not e_acc then m_cnt := m_cnt - 1;
end if;
if e_ovf then m_ovf := m_ovf + 1; end if;
if e_unf then m_unf := m_unf + 1; end if;
if (rq = '1') and (not e_gate) then m_blocked := m_blocked + 1; end if;
end if;
if m_cnt > m_hwm then m_hwm := m_cnt; end if;
wait until rising_edge(clk);
wait for 1 ns;
wr_req <= '0'; rd_en <= '0'; flush <= '0';
end procedure;
-- Empty the FIFO and clear the pipe, the way a bus reset does.
procedure do_flush is
begin
step('0', (others => '0'), '0', '1');
chk(unsigned(count) = 0, "the FIFO was not emptied by a flush");
chk(wr_gate = '1', "the backpressure pipe survived a flush -- the writer is throttled by a fact about a FIFO that no longer exists");
end procedure;
-- Drive the FIFO to exactly `target` occupancy using real writes through
-- the real gate. If the gate stops us short, that is a finding, not a
-- setup problem.
procedure fill_to (target : integer) is
variable i : integer := 0;
begin
do_flush;
i := 0;
while (m_cnt < target) and (i < 4*DEPTH) loop
step('1', std_logic_vector(to_unsigned(i, DW) xor x"a5"), '0', '0');
i := i + 1;
end loop;
chk(m_cnt = target,
"could not reach the requested occupancy through the gate -- the watermark stops the writer before the FIFO is full");
end procedure;
variable c, combo, it, burst, d_expect : integer;
variable rq_v, re_v, fl_v : std_logic;
variable ln : line;
begin
wait for 33 ns;
rst_n <= '1';
wait until rising_edge(clk);
wait for 1 ns;
-- ---- Phase A: the state after reset ----
chk(unsigned(count) = 0, "reset did not empty the FIFO");
chk(empty = '1', "reset did not assert empty");
chk(full = '0', "reset asserted full");
chk(almost_full = '0', "reset asserted almost_full");
chk(wr_gate = '1', "reset left the writer throttled");
chk(unsigned(hwm) = 0, "reset did not clear the high-water mark");
-- ---- Phase B: EXHAUSTIVE. Every occupancy x every input combination.
-- ---- Each occupancy is reached by real writes through the real gate.
for ci in 0 to DEPTH loop
for cb in 0 to 7 loop
fill_to(ci);
if (cb mod 2) = 1 then rq_v := '1'; else rq_v := '0'; end if;
if ((cb / 2) mod 2) = 1 then re_v := '1'; else re_v := '0'; end if;
if ((cb / 4) mod 2) = 1 then fl_v := '1'; else fl_v := '0'; end if;
step(rq_v, std_logic_vector(to_unsigned((ci*8 + cb) mod 256, DW)), re_v, fl_v);
-- and one more cycle with the same inputs, so a pipe stage that is
-- one short is exposed rather than merely delayed
step(rq_v, std_logic_vector(to_unsigned((ci*8 + cb + 1) mod 256, DW)), re_v, fl_v);
end loop;
end loop;
-- ---- Phase C: directed. The exact sequence the bug needs. ----
--
-- Fill to the watermark, then keep writing. Exactly LAT writes must
-- land -- no more, because the slots run out, and no fewer, because
-- the writer has not yet been told.
fill_to(WM);
chk(almost_full = '1', "the watermark did not assert at DEPTH-LAT");
chk(wr_gate = '1', "the writer was throttled before the backpressure could possibly have reached it");
d_expect := WM;
for i in 0 to LAT + 3 loop
step('1', std_logic_vector(to_unsigned((16#5a# + i) mod 256, DW)), '0', '0');
if i < LAT then d_expect := d_expect + 1; end if;
chk(m_cnt = d_expect,
"the number of writes that landed after the watermark is not LAT");
end loop;
chk(m_cnt = DEPTH,
"the in-flight writes did not fill the FIFO exactly -- the watermark is not DEPTH-LAT");
chk(full = '1', "the FIFO should be exactly full after the in-flight writes");
chk(unsigned(n_overflows) = 0, "a byte was dropped by a writer that honoured the gate");
-- ---- Phase D: sustained load. The writer asks on nearly every cycle
-- ---- and the reader falls behind: the only regime in which the bug
-- ---- can happen at all.
do_flush;
for i in 0 to 11999 loop
rq_v := rnd_lt(92, 100);
re_v := rnd_lt(38, 100);
step(rq_v, rnd_byte, re_v, '0');
end loop;
-- ---- Phase E: drain and check FIFO order end to end ----
for i in 0 to 3*DEPTH - 1 loop
step('0', (others => '0'), '1', '0');
end loop;
chk(empty = '1', "the FIFO did not drain");
-- ---- Phase F: bursts, flushes, and the pipe surviving one ----
for i in 0 to 899 loop
burst := rnd_range(1, 20);
for j in 1 to burst loop
re_v := rnd_lt(20, 100);
step('1', rnd_byte, re_v, '0');
end loop;
if rnd_lt(30, 100) = '1' then do_flush; end if;
end loop;
-- ---- Phase G: fully random, everything live ----
for i in 0 to 23999 loop
rq_v := rnd_lt(55, 100);
re_v := rnd_lt(55, 100);
fl_v := rnd_lt(4, 1000);
step(rq_v, rnd_byte, re_v, fl_v);
end loop;
-- ---- Reach and final agreement ----
chk(unsigned(n_writes) = to_unsigned(m_writes, 32), "n_writes disagrees with the model");
chk(unsigned(n_reads) = to_unsigned(m_reads, 32), "n_reads disagrees with the model");
chk(unsigned(n_overflows) = to_unsigned(m_ovf, 32), "n_overflows disagrees with the model");
chk(unsigned(n_underflows) = to_unsigned(m_unf, 32), "n_underflows disagrees with the model");
chk(unsigned(n_blocked) = to_unsigned(m_blocked, 32), "n_blocked disagrees with the model");
chk(unsigned(n_inflight) = to_unsigned(m_inflight, 32), "n_inflight disagrees with the model");
chk(unsigned(n_flushes) = to_unsigned(m_flushes, 32), "n_flushes disagrees with the model");
chk(unsigned(hwm) = to_unsigned(m_hwm, AW+1), "hwm disagrees with the model");
chk(unsigned(n_overflows) = 0,
"bytes were dropped although every write honoured wr_gate");
chk(n_states = DEPTH + 1,
"not every occupancy from 0 to DEPTH was reached");
-- ---- THE measurement. Exactly DEPTH -- both bounds. ----
chk(unsigned(hwm) = to_unsigned(DEPTH, AW+1),
"the peak occupancy is not exactly DEPTH: below it the watermark is too early and slots are wasted, above it is impossible");
chk(worst_inflight = LAT,
"the worst observed run of in-flight writes is not LAT -- the suite never drove the FIFO into the corner the watermark exists for");
chk(unsigned(n_inflight) > 0, "no write ever landed above the watermark");
chk(unsigned(n_blocked) > 0, "the gate never refused a write");
chk(unsigned(n_flushes) > 0, "no flush was ever exercised");
write(ln, string'("REACH occupancies=") & integer'image(n_states) &
"/" & integer'image(DEPTH+1) &
" transitions=" & integer'image(n_transitions) &
" worst-inflight=" & integer'image(worst_inflight) &
" of " & integer'image(LAT) &
" HWM=" & integer'image(to_integer(unsigned(hwm))) &
" of " & integer'image(DEPTH));
writeline(output, ln);
write(ln, string'("COUNTERS writes=") & integer'image(to_integer(unsigned(n_writes))) &
" reads=" & integer'image(to_integer(unsigned(n_reads))) &
" overflow=" & integer'image(to_integer(unsigned(n_overflows))) &
" underflow=" & integer'image(to_integer(unsigned(n_underflows))) &
" blocked=" & integer'image(to_integer(unsigned(n_blocked))) &
" inflight=" & integer'image(to_integer(unsigned(n_inflight))) &
" flushes=" & integer'image(to_integer(unsigned(n_flushes))));
writeline(output, ln);
if errors = 0 then
write(ln, string'("PASS: 0 errors in ") & integer'image(checks) & " checks");
else
write(ln, string'("FAIL: ") & integer'image(errors) & " errors in " &
integer'image(checks) & " checks");
end if;
writeline(output, ln);
done <= true;
wait;
end process;
end architecture sim;10. Exhaustive Verification
| Measure | Verilog | SystemVerilog | VHDL |
|---|---|---|---|
| Occupancies reached | 17 / 17 | 17 / 17 | 17 / 17 |
| Transitions | 47499 | 47077 | 47191 |
| Checks executed | 687756 | 681503 | 683252 |
| writes accepted | 23611 | 23615 | 23657 |
| reads | 19041 | 18755 | 18841 |
| writes refused by the gate | 11402 | 11114 | 11054 |
| writes landed above the watermark | 2728 | 2632 | 2659 |
| underflows exercised | 892 | 1013 | 913 |
| flushes exercised | 602 | 636 | 624 |
| bytes dropped | 0 | 0 | 0 |
| worst in-flight run | 2 of 2 | 2 of 2 | 2 of 2 |
| peak occupancy | 16 of 16 | 16 of 16 | 16 of 16 |
| Result | PASS | PASS | PASS |
Three rows are the whole chapter. Bytes dropped: 0. Worst in-flight run: 2 of a bound of 2 — the reservation was used completely, so it was genuinely tested. Peak occupancy: 16 of 16 — the FIFO was filled exactly, so the watermark is not merely safe but tight.
2728 writes landed above the watermark across the run. Every one of them is a write that the FIFO had no way to refuse and that had somewhere to go only because the arithmetic in §2 reserved a slot for it.
11. Mutation Testing
| # | Mutation | Verilog | SysVer | VHDL |
|---|---|---|---|---|
| F1 | backpressure asserted at FULL — the obvious answer | 67198 | 63629 | 65766 |
| F2 | watermark one slot too high (DEPTH − LAT + 1) | 46159 | 43212 | 43864 |
| F3 | the backpressure pipe is one stage short | 52821 | 52006 | 53535 |
| F4 | no pipe at all — the writer sees almost_full directly | 59474 | 57333 | 59643 |
| F5 | a flush does not clear the backpressure pipe | 7631 | 7237 | 7994 |
| F6 | the write pointer clamps instead of wrapping | 16032 | 15367 | 15705 |
| F7 | a read from an empty FIFO is honoured | 50584 | 55884 | 52748 |
| — | unmutated baseline | 0 | 0 | 0 |
All seven die in all three languages, all counts distinct.
F1 and F2 are the same bug at two magnitudes. F1 drops LAT bytes per fill; F2 drops one. F2 still scores 46 000, which is the useful result: the suite does not merely notice catastrophic watermarks, it notices a watermark that is wrong by one slot.
F3 and F4 are the mirror image — a watermark that is effectively too early. Neither drops a byte. Both are caught anyway, by the high-water-mark bound and by wr_gate disagreeing with the model. A suite that only checked for data loss would pass both, and would therefore have no opinion about a FIFO that is twice the size it needs to be.
F5 is the smallest at ~7600, and that is exactly right: leaving the backpressure pipe dirty across a flush costs LAT cycles of throughput, once, per flush. It is a real bug with a mild symptom — which is precisely why it survives code review, and precisely why a low mutation score is informative rather than reassuring.
12. Debugging Walkthrough: The Device That Gets Slow When It Gets Busy
The report. A USB mass-storage device sustains 30 MB/s writing a single large file and collapses to 4 MB/s when the host also reads from it. No errors are logged anywhere. The vendor's own tool reports the device as healthy.
Step 1 — is it the media? Benchmark the flash directly, bypassing USB. It sustains 90 MB/s under the mixed workload. Not the media.
Step 2 — is it the host? Try a second host, a second cable, a second port. Identical. Not the host.
Step 3 — trace the bus. Now it is visible: the device is NAKing a large fraction of OUT transactions, and a smaller fraction of the packets it does accept come back with a CRC error and get retried.
Step 4 — the CRC errors are the clue, not the NAKs. NAKs on a busy device are normal flow control. CRC errors on a short, well-terminated cable at high speed are not — and they should be random. Histogram them: they are not random. They cluster exactly when the read stream is active, which is exactly when the write FIFO's reader falls behind.
Step 5 — instrument the FIFO. Add hwm and n_overflows. n_overflows is non-zero, and it rises by exactly 2 each time the FIFO fills.
Step 6 — 2 is LAT. The backpressure path is an output flop plus an input flop on the writer. The watermark was set to DEPTH. The two writes already in flight when backpressure asserted were dropped, silently, every time.
Step 7 — why the throughput collapsed. Each dropped byte corrupts a packet. The packet fails CRC, the host retries it, the retry meets the same sustained load and fails again. The bandwidth is being spent retransmitting packets the device itself destroyed.
13. UVM and Assertions
13.1 The sequences
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
class usb_fifo_item extends uvm_sequence_item;
`uvm_object_utils(usb_fifo_item)
rand bit wr_req;
rand bit [7:0] wr_data;
rand bit rd_en;
rand bit flush;
constraint c_flush_rare { flush dist {0 := 999, 1 := 1}; }
function new(string name = "usb_fifo_item"); super.new(name); endfunction
endclass
// THE sequence for this chapter. The writer asks on nearly every cycle and
// the reader falls behind -- the ONLY regime in which the watermark bug can
// happen at all. A balanced random sequence never fills the FIFO and
// therefore never tests the watermark, which is how this bug reaches
// production with a green regression behind it.
class sustained_load_seq extends uvm_sequence #(usb_fifo_item);
`uvm_object_utils(sustained_load_seq)
function new(string name = "sustained_load_seq"); super.new(name); endfunction
task body();
repeat (4000) begin
usb_fifo_item it = usb_fifo_item::type_id::create("it");
start_item(it);
if (!it.randomize() with {
wr_req dist {1 := 92, 0 := 8};
rd_en dist {1 := 38, 0 := 62};
flush == 0;
})
`uvm_error("RAND", "sustained randomize failed")
finish_item(it);
end
endtask
endclass
// Fill to the watermark and then keep pushing. The number of writes that
// land after the watermark asserts must be exactly LAT: no fewer, because
// the writer has not been told yet, and no more, because the slots run out.
class fill_past_watermark_seq extends uvm_sequence #(usb_fifo_item);
`uvm_object_utils(fill_past_watermark_seq)
function new(string name = "fill_past_watermark_seq"); super.new(name); endfunction
task body();
repeat (200) begin
usb_fifo_item it;
// drain, so every repetition starts from the same place
repeat (20) begin
it = usb_fifo_item::type_id::create("it");
start_item(it);
if (!it.randomize() with { wr_req == 0; rd_en == 1; flush == 0; })
`uvm_error("RAND", "drain randomize failed")
finish_item(it);
end
// then write with no reads at all, straight through the watermark
repeat (24) begin
it = usb_fifo_item::type_id::create("it");
start_item(it);
if (!it.randomize() with { wr_req == 1; rd_en == 0; flush == 0; })
`uvm_error("RAND", "fill randomize failed")
finish_item(it);
end
end
endtask
endclass
// A flush while the FIFO is above the watermark. The pipe is carrying
// "almost full" at the moment the FIFO ceases to exist, and the bug is
// that the writer keeps being throttled by it afterwards.
class flush_while_throttled_seq extends uvm_sequence #(usb_fifo_item);
`uvm_object_utils(flush_while_throttled_seq)
function new(string name = "flush_while_throttled_seq"); super.new(name); endfunction
task body();
repeat (300) begin
usb_fifo_item it;
repeat (18) begin
it = usb_fifo_item::type_id::create("it");
start_item(it);
if (!it.randomize() with { wr_req == 1; rd_en == 0; flush == 0; })
`uvm_error("RAND", "prefill randomize failed")
finish_item(it);
end
it = usb_fifo_item::type_id::create("it");
start_item(it);
if (!it.randomize() with { flush == 1; wr_req == 0; rd_en == 0; })
`uvm_error("RAND", "flush randomize failed")
finish_item(it);
// The very next cycle the writer must be free again. If it is not,
// the pipe survived the flush.
it = usb_fifo_item::type_id::create("it");
start_item(it);
if (!it.randomize() with { wr_req == 1; rd_en == 0; flush == 0; })
`uvm_error("RAND", "post-flush randomize failed")
finish_item(it);
end
endtask
endclass13.2 The scoreboard
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
class usb_fifo_scoreboard extends uvm_scoreboard;
`uvm_component_utils(usb_fifo_scoreboard)
uvm_analysis_imp #(usb_fifo_mon_item, usb_fifo_scoreboard) ap;
localparam int DEPTH = 16;
localparam int LAT = 2;
localparam int WM = DEPTH - LAT;
// An INDEPENDENT queue. Not a mirror of the DUT's pointers -- a separate
// data structure, so a pointer bug shows up as wrong DATA and not merely
// as a disagreeing count.
byte unsigned sb_q[$];
int unsigned hwm, ep_inflight, worst_inflight;
bit ep_active;
int unsigned n_drops, n_blocked, n_flushes;
function new(string name, uvm_component parent);
super.new(name, parent);
ap = new("ap", this);
endfunction
function void write(usb_fifo_mon_item t);
// ---- A byte was DROPPED. For a writer that honours wr_gate this can
// ---- never happen, and it is the entire claim the watermark makes.
if (t.overflow) begin
n_drops++;
`uvm_error("OVERFLOW",
$sformatf("a byte was dropped at occupancy %0d -- the watermark is at or above DEPTH and %0d writes were already in flight",
t.count, LAT))
end
// ---- The occupancy can never exceed DEPTH: the slots do not exist. ----
if (t.count > DEPTH)
`uvm_error("IMPOSSIBLE",
$sformatf("count=%0d exceeds DEPTH=%0d", t.count, DEPTH))
// ---- The watermark is WHERE IT IS SUPPOSED TO BE. Checked directly,
// ---- not inferred from the absence of drops: a watermark of 1 also
// ---- produces no drops.
if (t.almost_full !== (t.count >= WM))
`uvm_error("WATERMARK",
$sformatf("almost_full=%b at count=%0d -- the watermark is not DEPTH-LAT=%0d",
t.almost_full, t.count, WM))
// ---- The in-flight reservation, per episode. ----
if (t.almost_full && !ep_active) begin ep_active = 1; ep_inflight = 0; end
if (!t.almost_full) ep_active = 0;
if (t.wr_accept && t.almost_full) begin
ep_inflight++;
if (ep_inflight > worst_inflight) worst_inflight = ep_inflight;
if (ep_inflight > LAT)
`uvm_error("INFLIGHT",
$sformatf("%0d writes have landed above the watermark but the backpressure path is only %0d stages deep -- the model of the round trip is wrong",
ep_inflight, LAT))
end
// ---- Data, in order. ----
if (t.flush) begin
sb_q.delete();
n_flushes++;
// The pipe belongs to a FIFO that no longer exists.
if (!t.wr_gate_next)
`uvm_error("STALE_BP",
"the writer is still throttled the cycle after a flush -- the backpressure pipe was not cleared")
end else begin
if (t.wr_accept) sb_q.push_back(t.wr_data);
if (t.rd_valid) begin
if (sb_q.size() == 0)
`uvm_error("PHANTOM", "a read was completed with the FIFO empty")
else if (t.rd_data !== sb_q[0])
`uvm_error("DATA",
$sformatf("read 0x%02h, expected 0x%02h -- FIFO order or storage is broken",
t.rd_data, sb_q[0]))
void'(sb_q.pop_front());
end
end
if (t.wr_req && !t.wr_gate) n_blocked++;
if (t.count > hwm) hwm = t.count;
endfunction
function void report_phase(uvm_phase phase);
`uvm_info("SB", $sformatf("hwm=%0d worst-inflight=%0d drops=%0d blocked=%0d flushes=%0d",
hwm, worst_inflight, n_drops, n_blocked, n_flushes), UVM_LOW)
// ---- THE measurement, and BOTH bounds of it. ----
if (hwm != DEPTH)
`uvm_error("HWM",
$sformatf("peak occupancy was %0d, not DEPTH=%0d: below it the watermark is too early and slots are being wasted; above it is impossible",
hwm, DEPTH))
if (worst_inflight != LAT)
`uvm_error("COVERAGE",
$sformatf("the worst run of in-flight writes was %0d of %0d -- the stimulus never drove the FIFO into the corner the watermark exists for",
worst_inflight, LAT))
if (n_blocked == 0)
`uvm_error("COVERAGE", "the gate never refused a write")
if (n_flushes == 0)
`uvm_error("COVERAGE", "no flush was ever exercised")
endfunction
endclass13.3 Coverage
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
covergroup cg_fifo @(posedge clk iff rst_n);
// Every occupancy individually, with the three that decide the design
// separated out: the watermark itself, one above it, and exactly full.
cp_count : coverpoint count {
bins low[] = {[0:WM-1]};
bins at_watermark = {WM};
bins inflight[] = {[WM+1:DEPTH-1]};
bins exactly_full = {DEPTH};
illegal_bins over = {[DEPTH+1:$]}; // the slots do not exist
}
cp_gate : coverpoint wr_gate;
cp_af : coverpoint almost_full;
cp_event : coverpoint wm_event;
// The cross that matters, and the reason to write a covergroup here at
// all: the FIFO is above the watermark AND the gate is still open. That
// is the in-flight window, and a run that never hits it has not tested
// the watermark no matter how many cycles it ran.
x_inflight_window : cross cp_af, cp_gate {
bins the_window = binsof(cp_af) intersect {1} &&
binsof(cp_gate) intersect {1};
}
// And a write actually landing inside that window.
x_landed_above_wm : cross cp_af, cp_event {
bins landed = binsof(cp_af) intersect {1} &&
binsof(cp_event) intersect {WM_INFLIGHT};
}
endgroupillegal_bins over is doing real work. An occupancy above DEPTH is not a coverage hole to be filled — it is physically impossible, and if it is ever sampled the model of the FIFO is wrong rather than merely incomplete.
13.4 Assertions
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
module usb_fifo_watermark_sva
import usb_wm_pkg::*;
#(
parameter int DEPTH = 16,
parameter int AW = 4,
parameter int LAT = 2
) (
input logic clk,
input logic rst_n,
input logic wr_req,
input logic rd_en,
input logic flush,
input logic wr_gate,
input logic wr_push,
input logic wr_accept,
input logic rd_valid,
input logic empty,
input logic full,
input logic almost_full,
input logic [AW:0] count,
input logic [AW:0] hwm,
input logic overflow,
input logic underflow,
input wm_event_e wm_event
);
localparam int WM = DEPTH - LAT;
default clocking cb @(posedge clk); endclocking
default disable iff (!rst_n);
// ---- 1. THE property. A writer that honours the gate never overflows. ----
property p_no_drop;
!overflow;
endproperty
a_no_drop : assert property (p_no_drop)
else $error("a byte was DROPPED -- the watermark does not cover the writes in flight");
// ---- 2. The slots do not exist above DEPTH. ----
property p_bounded;
count <= (AW+1)'(DEPTH);
endproperty
a_bounded : assert property (p_bounded);
// ---- 3. The watermark is where it is supposed to be. Checked DIRECTLY,
// ---- because a watermark of 1 also satisfies property 1.
property p_watermark_position;
almost_full == (count >= (AW+1)'(WM));
endproperty
a_watermark_position : assert property (p_watermark_position)
else $error("almost_full does not assert at exactly DEPTH-LAT");
// ---- 4. THE in-flight bound, stated as a sequence. Once the watermark
// ---- asserts and stays asserted, the gate must be shut by cycle LAT
// ---- -- no later, or more than LAT writes can land.
property p_gate_shuts_within_lat;
($rose(almost_full) && !flush) ##1 (almost_full && !flush)[*LAT-1]
|-> ##0 !wr_gate;
endproperty
a_gate_shuts_within_lat : assert property (p_gate_shuts_within_lat)
else $error("the gate was still open more than LAT cycles after the watermark asserted");
// ---- 5. ...and not EARLIER than the pipeline allows. A gate that shuts
// ---- early is not a safety bug; it is a FIFO that is bigger than it
// ---- needs to be, and nothing else in this file would notice.
property p_gate_not_early;
$fell(wr_gate) |-> $past(almost_full, LAT);
endproperty
a_gate_not_early : assert property (p_gate_not_early)
else $error("the gate shut before the watermark could have reached the writer -- slots are being wasted");
// ---- 6. The count follows what LANDED. ----
property p_count_tracks_accept;
(!flush && wr_accept && !rd_valid) |=> (count == $past(count) + 1'b1);
endproperty
a_count_tracks_accept : assert property (p_count_tracks_accept);
property p_count_tracks_read;
(!flush && rd_valid && !wr_accept) |=> (count == $past(count) - 1'b1);
endproperty
a_count_tracks_read : assert property (p_count_tracks_read);
// ---- 7. A flush empties the FIFO AND frees the writer. ----
property p_flush_clears_everything;
flush |=> (count == '0) && wr_gate;
endproperty
a_flush_clears_everything : assert property (p_flush_clears_everything)
else $error("a flush left the writer throttled by a fact about a FIFO that no longer exists");
// ---- 8. No phantom reads. ----
property p_no_read_when_empty;
empty |-> !rd_valid;
endproperty
a_no_read_when_empty : assert property (p_no_read_when_empty);
// ---- 9. The high-water mark never falls. ----
property p_hwm_monotonic;
hwm >= $past(hwm);
endproperty
a_hwm_monotonic : assert property (p_hwm_monotonic);
// ---- Cover: the states the watermark exists for. ----
c_at_watermark : cover property ((count == (AW+1)'(WM)));
c_exactly_full : cover property ((count == (AW+1)'(DEPTH)));
c_inflight_win : cover property ((almost_full && wr_gate && wr_accept));
c_refused : cover property ((wr_req && !wr_gate));
c_flush_high : cover property ((flush && $past(almost_full)));
endmodule
bind usb_fifo_watermark
usb_fifo_watermark_sva #(.DEPTH(DEPTH), .AW(AW), .LAT(LAT)) u_sva (.*);14. Choosing DEPTH and LAT in a Real Device
The arithmetic gives the watermark once you know LAT. Getting LAT right is the part that takes engineering rather than algebra:
| Contributor | Typical | Notes |
|---|---|---|
| FIFO output register | 1 | almost always present for timing |
| pipeline / interconnect | 0–2 | count the flops, do not estimate them |
| writer's input register | 1 | almost always present |
| synchroniser, if the writer is in another clock domain | 2 or more | and then the whole analysis changes — see Chapter 23.5 |
And DEPTH follows from the watermark rather than the other way round: it must be at least LAT (or the watermark is negative and the FIFO can never open), and for a USB endpoint it wants to be at least one maximum packet size so that a full packet can be buffered without a mid-packet stall — 64 bytes for a full-speed bulk endpoint, 512 for high speed.
15. Common Misconceptions
"Backpressure at full is the definition of backpressure." It is the definition of backpressure that arrives instantly. Yours does not.
"A deeper FIFO fixes it." It does not. A deeper FIFO takes longer to fill and then drops the same LAT bytes. The watermark is the fix; depth is a different parameter solving a different problem.
"Setting the watermark low is the safe choice." It wastes slots and throttles the writer while the FIFO has room. On an isochronous endpoint that is a dropped frame, and isochronous frames are not retried.
"No overflow means the watermark is right." WM = 1 never overflows. The measurement is peak occupancy == DEPTH, which pins it from both sides.
"The CRC will catch it." The CRC catches the corruption and hides the cause. What you see is a retry storm, filed as a performance problem.
"CRC errors mean a cable." Signal-integrity errors are uniform in time. FIFO-overflow errors correlate with load. Histogram before you re-cable.
"$random % 1000 < 4 is a 0.4% probability." $random is signed, so it is about 50%.
16. Exercises
1. Set LAT = 3 without touching the watermark expression and predict, from §2 alone, what hwm becomes and how many bytes are dropped per fill. Then run it.
2. F2 is wrong by a single slot and still scores 46 000. Find the first check that fires and explain why an off-by-one is as visible as F1's off-by-two.
3. F3 and F4 drop nothing at all. Identify every check that kills them and argue what a suite that only checked for data loss would have concluded.
4. §11 lists three mutations that are provably equivalent. Prove one of them, then break the watermark and show the same mutation is no longer equivalent.
5. Delete SVA property 5 and find the smallest watermark that still passes the whole file. That number is what property 5 is worth.
6. The writer is in a 30 MHz domain and the FIFO in a 60 MHz domain, with two synchroniser stages each way. Work out LAT in FIFO cycles, then in writer cycles, and say which one the watermark expression needs.
17. Summary
| Idea | Why it matters |
|---|---|
| Backpressure has latency | and the writer keeps writing throughout it |
WM = DEPTH − LAT | reserve one slot per cycle of round trip |
| Peak occupancy must be exactly DEPTH | lower wastes slots, higher is dropped data |
wr_push vs wr_accept | the gap between them is the lost data |
n_inflight is counted | the reservation is measured, never assumed |
| Only sustained load can trigger it | so light-load testing proves nothing |
| The CRC hides the cause | a retry storm is filed as a performance bug |
| Non-random CRC errors are not a cable | histogram against throughput first |
| A flush must clear the pipe too | or the writer is throttled by a dead FIFO |
| Three obvious mutations are equivalent | because a correct watermark makes overflow unreachable |
$random is signed | % 1000 < 4 is a coin flip, not 0.4% |
| 17 occupancies, all reached for real | 7 mutations, all killed in 3 languages |
Tooling
| Step | Command |
|---|---|
| Verilog-2005 | iverilog -g2005 -o fw_v.out fw_v.v fw_v_tb.v && ./fw_v.out |
| SystemVerilog | iverilog -g2012 -o fw_sv.out fw_sv.sv fw_sv_tb.sv && ./fw_sv.out |
| VHDL-2008 analyse | nvc --std=2008 -a fw_vhdl.vhd fw_vhdl_tb.vhd |
| VHDL-2008 elaborate | nvc --std=2008 -e tb_fw_vhdl |
| VHDL-2008 run | nvc --std=2008 -r tb_fw_vhdl |
| One mutation | iverilog -g2005 -DMUT_F1 -o mm fw_v_mut.v fw_v_tb.v && ./mm |
All three implementations pass with 0 errors: 17 of 17 occupancies reached through the real gate, ~684 000 checks, zero bytes dropped, a worst in-flight run of exactly LAT, and a peak occupancy of exactly DEPTH.
Chapter 23.4 — Protocol FSMs turns to the state machine that consumes what this FIFO holds. Its organising rule is stricter than it sounds: every error resynchronises to IDLE. A packet recogniser that tries to recover in place — skipping the bad byte, guessing the length — stays out of step for the rest of the session, because there is no way to know where the next packet begins except by waiting for one to start.
Continue learning
Related tutorials
- Related topic
Hub Architecture
A hub is three devices in one package, and its repeater is deliberately asymmetric: downstream is a broadcast, upstream is a select of exactly one — and two talkers connects neither.
- Related topic
Port Management
Three uncoordinated sources move a hub port and collide in the same cycle — and the host, whose information is stale by construction, is the one that loses.
- Related topic
Downstream Device Discovery
A hub cannot interrupt the host, so every port event waits to be asked for — and the window between the poll and the acknowledgement is where devices are silently lost.
- Related topic
Cascading Hubs
The seven-tier rule is a timing constraint wearing a topology costume — and the limit applies to hubs, not to devices, which is one comparison operator almost everyone gets wrong.
Standards & specifications
- Governing standard
- USB-IF (Universal Serial Bus Specification)(opens USB Implementers Forum (USB-IF) in a new tab)
Defines the USB bus — its electrical signalling, connectors, packet and transaction model, device framework and the descriptors a device must expose — together with the device-class specifications layered on it. It does not define host-controller register interfaces (xHCI and EHCI are separate documents) nor any operating system's driver architecture.
This page also covers RTL structure, verification approach and debugging technique. Those are engineering practice built on the standard, not requirements the standard itself imposes.
Where this fits
Part of the USB curriculum.