USB · Module 22
EHCI Overview
EHCI has no command queue — it is a DMA engine walking a linked list software edits underneath it, around a ring with no end, where a link pointer is a packed word and the terminate bit must be read first.
Module 21 built the device side. This module is the host side — and the first thing to understand about a USB host controller is that it does not work the way you would expect a peripheral to work.
1. EHCI Does Not Have a Command Queue
The obvious design for a host controller is a command queue: software writes "do this transfer" into a FIFO, hardware pops it, does it, and posts a completion. That is how most DMA engines work. EHCI does not do this.
Software builds a linked list of Queue Heads in host memory and writes one register with the address of the first one. From that moment the controller walks the list by itself — fetching each node, doing any work it finds there, following the node's link pointer to the next one — for as long as the schedule is enabled.
2. A Link Pointer Is Not an Address
Each link is one 32-bit word, and only part of it is an address:
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
31 5 4 3 2 1 0
+---------------------------------+---+-----+-----+
| address bits 31:5 |rsv| Typ | T |
+---------------------------------+---+-----+-----+
T (bit 0) TERMINATE. If set there is no next node, and the
rest of the word is MEANINGLESS -- not zero,
meaningless. Software may leave anything there.
Typ (2:1) what the next node IS: iTD / QH / siTD / FSTN.
bits 4:3 reserved. Mask them; do not assume they are zero.
bits 31:5 the address. Nodes are 32-byte aligned, which is
exactly why five bits are free to carry the rest.The alignment is not a convenience — it is what makes the encoding possible. Because every node is 32-byte aligned, the bottom five bits of every pointer are known to be zero, so the specification spends them on other fields. A controller that treats the word as an address gets a pointer with up to 31 added to it, into the middle of a descriptor.
And the order of operations is forced:
The decode, and the only order that is safe
3. The Async List Is Circular, So "The End" Does Not Exist
The asynchronous schedule — bulk and control traffic — is a ring. The last Queue Head points back to the first. There is no terminator anywhere in it.
That is deliberate, and it solves a real problem: software can add and remove nodes while the controller is walking, and the controller never finds a broken chain. Unlinking a node means pointing its predecessor past it; the controller either sees the old pointer or the new one, and both are valid rings.
But it leaves a question with no obvious answer. When is the controller finished? It cannot be "when the list ends", because it does not end.
4. The H Bit, and Termination by Lap
Exactly one Queue Head in the ring is marked Head — the H bit. The controller keeps one flag, Reclamation, and two rules:
| Event | Effect |
|---|---|
| work done at any node | Reclamation ← 1 |
| arriving at the H-bit node with Reclamation = 1 | clear it, carry on |
| arriving at the H-bit node with Reclamation = 0 | stop |
The controller stops when it has gone all the way round and found nothing to do.
The asynchronous ring, and the node that makes stopping possible
5. Only Queue Heads Belong in the Async List
The Typ field has four values, and three of them are periodic:
Typ | Node | Schedule |
|---|---|---|
00 | iTD — isochronous transfer descriptor | periodic |
01 | QH — queue head | asynchronous |
10 | siTD — split isochronous descriptor | periodic |
11 | FSTN — frame span traversal node | periodic |
An iTD in the asynchronous list is a software bug, and the consequence of following it is specific: the controller would read an isochronous descriptor as a queue head, interpreting one structure's fields as another's. That is not a transfer that fails; it is a DMA engine told to read from an address assembled out of a transfer-length field.
So the walker refuses, and counts it. Mutation K4 in §11 removes that refusal.
6. What We Are Building
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
ehci_async_walker
from the schedule to the fetch engine
----------------- -------------------
async_enable terminate / typ / typ_valid
word_valid next_addr (masked, 32-byte aligned)
link_word [31:0] follow (dereference this cycle)
node_is_head bad_type (wrong list)
node_did_work
async_doorbell walking / async_idle / stopped
reclamation
n_steps / n_laps / n_idles / n_bad_type / n_workThe whole decode is combinational — the controller decides whether to dereference in the cycle the word arrives — and only two bits are registered: Reclamation, and a latch recording that the walk stopped.
7. Verilog-2005 Implementation
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
// ehci_async_walker -- the EHCI host controller as what it actually is: a DMA
// engine that follows pointers software built, around a list that has no end.
//
// THE CONTROLLER DOES NOT HAVE A COMMAND QUEUE
//
// Software does not hand EHCI a list of transfers. It builds a linked list of
// Queue Heads IN HOST MEMORY and writes one register with the address of the
// first one. From then on the controller walks that list by itself, fetching
// each node, doing any work it finds, and following the node's link pointer
// to the next one -- for ever, while the schedule is enabled.
//
// That inverts the usual relationship. The hardware is not being told what to
// do; it is READING a data structure another agent is editing at the same
// time. Every rule below follows from that.
//
// A LINK POINTER IS NOT AN ADDRESS
//
// Each link is one 32-bit word, and only part of it is an address:
//
// 31 5 4 3 2 1 0
// +---------------------------------+---+-----+-----+
// | address bits 31:5 |rsv| Typ | T |
// +---------------------------------+---+-----+-----+
//
// T (bit 0) TERMINATE. If set, there is no next node. The rest of
// the word is MEANINGLESS -- not "zero", meaningless.
// Typ (2:1) what the next node IS: iTD / QH / siTD / FSTN.
// bits 4:3 reserved. Must be masked off, not assumed zero.
// bits 31:5 the address. Nodes are 32-byte aligned, which is why
// five bits are available to carry the other fields.
//
// So the order of operations is forced, and it is the same discipline as a
// packet header's CRC (chapter 20.4): CHECK T FIRST. A controller that
// computes the next address and then notices the T bit has already formed a
// DMA address out of a word software filled with something else.
//
// THE ASYNC LIST IS CIRCULAR, SO "THE END" DOES NOT EXIST
//
// The asynchronous schedule -- bulk and control traffic -- is a RING. The
// last Queue Head points back to the first. There is no terminator, by
// design: software can add and remove nodes without the controller ever
// finding a broken chain.
//
// Which leaves a question with no obvious answer: when is the controller
// FINISHED? It cannot be "when the list ends", because it does not.
//
// THE H BIT AND THE RECLAMATION FLAG
//
// Exactly one Queue Head in the ring is marked HEAD (the H bit). The
// controller keeps one flag, Reclamation, and two rules:
//
// doing any work at any node -> Reclamation = 1
// arriving at the H-bit node -> if Reclamation is 0, STOP.
// otherwise clear it and carry on.
//
// So the controller stops when it has gone all the way round and found
// nothing to do. "Empty" is not a property of the list -- it is a LAP with no
// work in it. That is a genuinely unusual way to terminate a traversal, and
// it is the reason an idle EHCI controller stops burning memory bandwidth
// without software having to tell it anything.
//
// ONLY QUEUE HEADS BELONG IN THE ASYNC LIST
//
// iTD and siTD are isochronous, which is periodic traffic; FSTN is a
// frame-span traversal node, also periodic. A non-QH type in the async list
// is a software bug, and the controller must not follow it -- following it
// would interpret an isochronous descriptor as a queue head.
module ehci_async_walker (
input wire clk,
input wire rst_n,
input wire async_enable, // ASYNCSCHEDULE bit in USBCMD
input wire word_valid, // a link word has been fetched
input wire [31:0] link_word, // ...and here it is
input wire node_is_head, // the node we just visited had the H bit
input wire node_did_work, // ...and had a transfer to run
input wire async_doorbell,// software: "look again, I added work"
output wire terminate, // the T bit
output wire [1:0] typ, // the Typ field
output wire typ_valid, // ...which means NOTHING if T is set
output wire [31:0] next_addr, // masked to a 32-byte boundary
output wire follow, // dereference next_addr this cycle
output wire bad_type, // a non-QH node in the async list
output wire walking,
output wire async_idle, // a full lap with no work: stop
output wire stopped, // ...latched, until the doorbell rings
output wire reclamation,
output reg [31:0] n_steps,
output reg [31:0] n_laps,
output reg [31:0] n_idles,
output reg [31:0] n_bad_type,
output reg [31:0] n_work
);
localparam [1:0] TYP_ITD = 2'd0, // isochronous: periodic, not async
TYP_QH = 2'd1, // queue head: the only legal async node
TYP_SITD = 2'd2, // split isochronous: periodic
TYP_FSTN = 2'd3; // frame span traversal: periodic
// stopped_r latches the empty-list condition. Without it the walker would
// stop for exactly one cycle and then restart, because the thing that made
// it stop -- arriving at the head with nothing done -- is no longer true
// the moment it stops walking.
reg stopped_r;
reg reclaim_r;
assign walking = async_enable && !stopped_r;
assign reclamation = reclaim_r;
assign stopped = stopped_r;
// ---- THE DECODE, AND ITS ORDER ----
//
// T is bit 0 and it is read FIRST. With T set the rest of the word is not
// an address and not a type; it is whatever software left there.
assign terminate = word_valid && link_word[0];
assign typ_valid = word_valid && !link_word[0];
assign typ = link_word[2:1];
// Bits 4:3 are reserved and are MASKED, not assumed zero. Software is
// permitted to leave anything in them.
assign next_addr = {link_word[31:5], 5'b00000};
// A non-QH node in the asynchronous list is a software error. Following it
// would read an isochronous descriptor as a queue head.
assign bad_type = typ_valid && (typ != TYP_QH);
// Dereference only when the schedule is running, a word has been fetched,
// the T bit is clear, and the type is one that belongs here.
assign follow = walking && word_valid && !link_word[0] && !bad_type;
// ---- THE TERMINATION RULE ----
//
// Arriving at the H-bit node with Reclamation clear means a whole lap
// produced no work. That -- and only that -- is how this traversal ends.
wire visiting = walking && word_valid;
wire lap_done = visiting && node_is_head;
assign async_idle = lap_done && !reclaim_r && !node_did_work;
// Written as one next-state expression rather than a sequence of
// assignments: work done at the head node must leave Reclamation SET even
// though arriving at the head clears it, and leaving that to a
// last-assignment rule is how the two orderings diverge between languages.
wire reclaim_next = !async_enable ? 1'b0
: node_did_work && visiting ? 1'b1 // work always sets
: lap_done ? 1'b0 // a clean lap clears
: reclaim_r;
// Software restarts a stopped walker by ringing the doorbell -- which is
// the only way the controller can learn that the list it found empty is
// not empty any more. Disabling the schedule also clears the latch.
wire stopped_next = !async_enable ? 1'b0
: async_doorbell ? 1'b0
: async_idle ? 1'b1
: stopped_r;
always @(posedge clk or negedge rst_n) begin
if (!rst_n) begin
stopped_r <= 1'b0;
reclaim_r <= 1'b0;
n_steps <= 32'd0;
n_laps <= 32'd0;
n_idles <= 32'd0;
n_bad_type <= 32'd0;
n_work <= 32'd0;
end else begin
stopped_r <= stopped_next;
reclaim_r <= reclaim_next;
if (follow) n_steps <= n_steps + 32'd1;
if (lap_done) n_laps <= n_laps + 32'd1;
if (async_idle) n_idles <= n_idles + 32'd1;
if (walking && bad_type) n_bad_type <= n_bad_type + 32'd1;
if (visiting && node_did_work) n_work <= n_work + 32'd1;
end
end
endmodulereclaim_next is one expression, and the order inside it is a specification decision. Work done at the head node must leave Reclamation set, even though arriving at the head is what clears it. Written as two if statements inside the clocked block, the answer would depend on the language's last-assignment rule; written as a priority chain, it is visible. Mutation K7 inverts exactly those two lines.
8. SystemVerilog Implementation
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
// ehci_async_walker -- the EHCI host controller as what it actually is: a DMA
// engine that follows pointers software built, around a list that has no end.
//
// THE CONTROLLER DOES NOT HAVE A COMMAND QUEUE
//
// Software does not hand EHCI a list of transfers. It builds a linked list of
// Queue Heads IN HOST MEMORY and writes one register with the address of the
// first one. From then on the controller walks that list by itself, fetching
// each node, doing any work it finds, and following the node's link pointer
// to the next one -- for ever, while the schedule is enabled.
//
// That inverts the usual relationship. The hardware is not being told what to
// do; it is READING a data structure another agent is editing at the same
// time. Every rule below follows from that.
//
// A LINK POINTER IS NOT AN ADDRESS
//
// Each link is one 32-bit word, and only part of it is an address:
//
// 31 5 4 3 2 1 0
// +---------------------------------+---+-----+-----+
// | address bits 31:5 |rsv| Typ | T |
// +---------------------------------+---+-----+-----+
//
// T (bit 0) TERMINATE. If set, there is no next node. The rest of
// the word is MEANINGLESS -- not "zero", meaningless.
// Typ (2:1) what the next node IS: iTD / QH / siTD / FSTN.
// bits 4:3 reserved. Must be masked off, not assumed zero.
// bits 31:5 the address. Nodes are 32-byte aligned, which is why
// five bits are available to carry the other fields.
//
// So the order of operations is forced, and it is the same discipline as a
// packet header's CRC (chapter 20.4): CHECK T FIRST. A controller that
// computes the next address and then notices the T bit has already formed a
// DMA address out of a word software filled with something else.
//
// THE ASYNC LIST IS CIRCULAR, SO "THE END" DOES NOT EXIST
//
// The asynchronous schedule -- bulk and control traffic -- is a RING. The
// last Queue Head points back to the first. There is no terminator, by
// design: software can add and remove nodes without the controller ever
// finding a broken chain.
//
// Which leaves a question with no obvious answer: when is the controller
// FINISHED? It cannot be "when the list ends", because it does not.
//
// THE H BIT AND THE RECLAMATION FLAG
//
// Exactly one Queue Head in the ring is marked HEAD (the H bit). The
// controller keeps one flag, Reclamation, and two rules:
//
// doing any work at any node -> Reclamation = 1
// arriving at the H-bit node -> if Reclamation is 0, STOP.
// otherwise clear it and carry on.
//
// So the controller stops when it has gone all the way round and found
// nothing to do. "Empty" is not a property of the list -- it is a LAP with no
// work in it. That is a genuinely unusual way to terminate a traversal, and
// it is the reason an idle EHCI controller stops burning memory bandwidth
// without software having to tell it anything.
//
// ONLY QUEUE HEADS BELONG IN THE ASYNC LIST
//
// iTD and siTD are isochronous, which is periodic traffic; FSTN is a
// frame-span traversal node, also periodic. A non-QH type in the async list
// is a software bug, and the controller must not follow it -- following it
// would interpret an isochronous descriptor as a queue head.
package ehci_walker_pkg;
// What the Typ field says the next node IS. Only TYP_QH belongs in the
// asynchronous list -- the other three are periodic descriptors, and
// naming them is what makes "this one is in the wrong list" a statement
// the design can make rather than a comment in a header file.
typedef enum logic [1:0] {
TYP_ITD = 2'd0, // isochronous transfer descriptor: PERIODIC
TYP_QH = 2'd1, // queue head: the only legal asynchronous node
TYP_SITD = 2'd2, // split isochronous descriptor: PERIODIC
TYP_FSTN = 2'd3 // frame span traversal node: PERIODIC
} link_typ_e;
// The bit positions inside a link pointer, named once. A link word is not
// an address with some flags bolted on; it is a packed structure, and the
// address is the part that survives after the other fields are removed.
parameter int LINK_T_BIT = 0; // TERMINATE
parameter int LINK_TYP_LSB = 1; // Typ, two bits
parameter int LINK_ADDR_LSB = 5; // the address starts here: 32-byte align
endpackage
module ehci_async_walker
import ehci_walker_pkg::*;
(
input logic clk,
input logic rst_n,
input logic async_enable, // ASYNCSCHEDULE bit in USBCMD
input logic word_valid, // a link word has been fetched
input logic [31:0] link_word, // ...and here it is
input logic node_is_head, // the node we just visited had the H bit
input logic node_did_work, // ...and had a transfer to run
input logic async_doorbell,// software: "look again, I added work"
output logic terminate, // the T bit
output link_typ_e typ, // the Typ field
output logic typ_valid, // ...which means NOTHING if T is set
output logic [31:0] next_addr, // masked to a 32-byte boundary
output logic follow, // dereference next_addr this cycle
output logic bad_type, // a non-QH node in the async list
output logic walking,
output logic async_idle, // a full lap with no work: stop
output logic stopped, // ...latched, until the doorbell rings
output logic reclamation,
output logic [31:0] n_steps,
output logic [31:0] n_laps,
output logic [31:0] n_idles,
output logic [31:0] n_bad_type,
output logic [31:0] n_work
);
// stopped_r latches the empty-list condition. Without it the walker would
// stop for exactly one cycle and then restart, because the thing that made
// it stop -- arriving at the head with nothing done -- is no longer true
// the moment it stops walking.
logic stopped_r;
logic reclaim_r;
assign walking = async_enable && !stopped_r;
assign reclamation = reclaim_r;
assign stopped = stopped_r;
// ---- THE DECODE, AND ITS ORDER ----
//
// T is bit 0 and it is read FIRST. With T set the rest of the word is not
// an address and not a type; it is whatever software left there.
assign terminate = word_valid && link_word[LINK_T_BIT];
assign typ_valid = word_valid && !link_word[LINK_T_BIT];
assign typ = link_typ_e'(link_word[LINK_TYP_LSB+1 -: 2]);
// Bits 4:3 are reserved and are MASKED, not assumed zero. Software is
// permitted to leave anything in them.
assign next_addr = {link_word[31:LINK_ADDR_LSB], {LINK_ADDR_LSB{1'b0}}};
// A non-QH node in the asynchronous list is a software error. Following it
// would read an isochronous descriptor as a queue head.
assign bad_type = typ_valid && (typ != TYP_QH);
// Dereference only when the schedule is running, a word has been fetched,
// the T bit is clear, and the type is one that belongs here.
assign follow = walking && word_valid && !link_word[LINK_T_BIT] && !bad_type;
// ---- THE TERMINATION RULE ----
//
// Arriving at the H-bit node with Reclamation clear means a whole lap
// produced no work. That -- and only that -- is how this traversal ends.
logic visiting, lap_done;
assign visiting = walking && word_valid;
assign lap_done = visiting && node_is_head;
assign async_idle = lap_done && !reclaim_r && !node_did_work;
// Written as one next-state expression rather than a sequence of
// assignments: work done at the head node must leave Reclamation SET even
// though arriving at the head clears it, and leaving that to a
// last-assignment rule is how the two orderings diverge between languages.
logic reclaim_next, stopped_next;
always_comb begin
if (!async_enable) reclaim_next = 1'b0;
else if (node_did_work && visiting) reclaim_next = 1'b1; // work always sets
else if (lap_done) reclaim_next = 1'b0; // a clean lap clears
else reclaim_next = reclaim_r;
end
// Software restarts a stopped walker by ringing the doorbell -- which is
// the only way the controller can learn that the list it found empty is
// not empty any more. Disabling the schedule also clears the latch.
always_comb begin
if (!async_enable) stopped_next = 1'b0;
else if (async_doorbell) stopped_next = 1'b0;
else if (async_idle) stopped_next = 1'b1;
else stopped_next = stopped_r;
end
always_ff @(posedge clk or negedge rst_n) begin
if (!rst_n) begin
stopped_r <= 1'b0;
reclaim_r <= 1'b0;
n_steps <= '0;
n_laps <= '0;
n_idles <= '0;
n_bad_type <= '0;
n_work <= '0;
end else begin
stopped_r <= stopped_next;
reclaim_r <= reclaim_next;
if (follow) n_steps <= n_steps + 1;
if (lap_done) n_laps <= n_laps + 1;
if (async_idle) n_idles <= n_idles + 1;
if (walking && bad_type) n_bad_type <= n_bad_type + 1;
if (visiting && node_did_work) n_work <= n_work + 1;
end
end
endmoduleThe bit positions live in the package as named parameters — LINK_T_BIT, LINK_TYP_LSB, LINK_ADDR_LSB. That is not tidiness: link_word[31:5] appearing in three places is three chances to write [31:4], and the resulting bug is a DMA address off by a multiple of 16 that only shows up on nodes whose address happens to have bit 4 set.
9. VHDL-2008 Implementation
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
-- ehci_async_walker -- the EHCI host controller as what it actually is: a DMA
-- engine that follows pointers software built, around a list that has no end.
--
-- THE CONTROLLER DOES NOT HAVE A COMMAND QUEUE
--
-- Software does not hand EHCI a list of transfers. It builds a linked list of
-- Queue Heads IN HOST MEMORY and writes one register with the address of the
-- first one. From then on the controller walks that list by itself, fetching
-- each node, doing any work it finds, and following the node's link pointer
-- to the next one -- for ever, while the schedule is enabled.
--
-- That inverts the usual relationship. The hardware is not being told what to
-- do; it is READING a data structure another agent is editing at the same
-- time. Every rule below follows from that.
--
-- A LINK POINTER IS NOT AN ADDRESS
--
-- Each link is one 32-bit word, and only part of it is an address:
--
-- 31 5 4 3 2 1 0
-- +---------------------------------+---+-----+-----+
-- | address bits 31:5 |rsv| Typ | T |
-- +---------------------------------+---+-----+-----+
--
-- T (bit 0) TERMINATE. If set, there is no next node, and the rest of
-- the word is MEANINGLESS -- not "zero", meaningless.
-- Typ (2:1) what the next node IS: iTD / QH / siTD / FSTN.
-- bits 4:3 reserved. Must be masked off, not assumed zero.
-- bits 31:5 the address. Nodes are 32-byte aligned, which is why five
-- bits are available to carry the other fields.
--
-- So the order of operations is forced, and it is the same discipline as a
-- packet header's CRC (chapter 20.4): CHECK T FIRST. A controller that
-- computes the next address and then notices the T bit has already formed a
-- DMA address out of a word software filled with something else.
--
-- THE ASYNC LIST IS CIRCULAR, SO "THE END" DOES NOT EXIST
--
-- The asynchronous schedule -- bulk and control traffic -- is a RING. The
-- last Queue Head points back to the first. There is no terminator, by
-- design: software can add and remove nodes without the controller ever
-- finding a broken chain.
--
-- Which leaves a question with no obvious answer: when is the controller
-- FINISHED? It cannot be "when the list ends", because it does not.
--
-- THE H BIT AND THE RECLAMATION FLAG
--
-- Exactly one Queue Head in the ring is marked HEAD (the H bit). The
-- controller keeps one flag, Reclamation, and two rules:
--
-- doing any work at any node -> Reclamation = 1
-- arriving at the H-bit node -> if Reclamation is 0, STOP.
-- otherwise clear it and carry on.
--
-- So the controller stops when it has gone all the way round and found
-- nothing to do. "Empty" is not a property of the list -- it is a LAP with no
-- work in it.
--
-- ONLY QUEUE HEADS BELONG IN THE ASYNC LIST
--
-- iTD and siTD are isochronous, which is periodic traffic; FSTN is a
-- frame-span traversal node, also periodic. A non-QH type in the async list
-- is a software bug, and following it would interpret an isochronous
-- descriptor as a queue head. VHDL's enumerated type makes the four
-- possibilities a closed set, so "which of these belongs here" is a question
-- the design is forced to answer for all of them.
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
package ehci_walker_pkg is
type link_typ_t is (
TYP_ITD, -- isochronous transfer descriptor: PERIODIC
TYP_QH, -- queue head: the only legal asynchronous node
TYP_SITD, -- split isochronous descriptor: PERIODIC
TYP_FSTN -- frame span traversal node: PERIODIC
);
-- The bit positions inside a link pointer, named once. A link word is not
-- an address with some flags bolted on; it is a packed structure, and the
-- address is the part that survives after the other fields are removed.
constant LINK_T_BIT : natural := 0; -- TERMINATE
constant LINK_TYP_LSB : natural := 1; -- Typ, two bits
constant LINK_ADDR_LSB : natural := 5; -- the address: 32-byte aligned
function typ_decode(w : std_logic_vector(31 downto 0)) return link_typ_t;
function typ_code(t : link_typ_t) return std_logic_vector;
end package;
package body ehci_walker_pkg is
function typ_decode(w : std_logic_vector(31 downto 0)) return link_typ_t is
begin
return link_typ_t'val(
to_integer(unsigned(w(LINK_TYP_LSB + 1 downto LINK_TYP_LSB))));
end function;
function typ_code(t : link_typ_t) return std_logic_vector is
begin
return std_logic_vector(to_unsigned(link_typ_t'pos(t), 2));
end function;
end package body;
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
use work.ehci_walker_pkg.all;
entity ehci_async_walker is
port (
clk : in std_logic;
rst_n : in std_logic;
async_enable : in std_logic; -- ASYNCSCHEDULE bit in USBCMD
word_valid : in std_logic; -- a link word has been fetched
link_word : in std_logic_vector(31 downto 0);
node_is_head : in std_logic; -- the node we visited had the H bit
node_did_work : in std_logic; -- ...and had a transfer to run
async_doorbell : in std_logic; -- software: "look again"
terminate : out std_logic;
typ : out std_logic_vector(1 downto 0);
typ_valid : out std_logic; -- means NOTHING if T is set
next_addr : out std_logic_vector(31 downto 0);
follow : out std_logic;
bad_type : out std_logic; -- a non-QH node in the async list
walking : out std_logic;
async_idle : out std_logic; -- a full lap with no work: stop
stopped : out std_logic; -- ...latched, until the doorbell
reclamation : out std_logic;
n_steps : out std_logic_vector(31 downto 0);
n_laps : out std_logic_vector(31 downto 0);
n_idles : out std_logic_vector(31 downto 0);
n_bad_type : out std_logic_vector(31 downto 0);
n_work : out std_logic_vector(31 downto 0)
);
end entity;
architecture rtl of ehci_async_walker is
-- stopped_r latches the empty-list condition. Without it the walker would
-- stop for exactly one cycle and then restart, because the thing that made
-- it stop -- arriving at the head with nothing done -- is no longer true
-- the moment it stops walking.
signal stopped_r : std_logic := '0';
signal reclaim_r : std_logic := '0';
signal walk_s, term_s, tv_s, bad_s, fol_s : std_logic;
signal vis_s, lap_s, idle_s : std_logic;
signal ty_s : link_typ_t;
signal stopped_n, reclaim_n : std_logic;
signal st_c, lp_c, id_c, bt_c, wk_c : unsigned(31 downto 0)
:= (others => '0');
begin
walk_s <= async_enable and (not stopped_r);
walking <= walk_s;
stopped <= stopped_r;
reclamation <= reclaim_r;
-- ---- THE DECODE, AND ITS ORDER ----
--
-- T is bit 0 and it is read FIRST. With T set the rest of the word is not
-- an address and not a type; it is whatever software left there.
term_s <= word_valid and link_word(LINK_T_BIT);
tv_s <= word_valid and (not link_word(LINK_T_BIT));
ty_s <= typ_decode(link_word);
terminate <= term_s;
typ_valid <= tv_s;
typ <= typ_code(ty_s);
-- Bits 4:3 are reserved and are MASKED, not assumed zero. Software is
-- permitted to leave anything in them.
next_addr <= link_word(31 downto LINK_ADDR_LSB)
& (LINK_ADDR_LSB - 1 downto 0 => '0');
-- A non-QH node in the asynchronous list is a software error. Following it
-- would read an isochronous descriptor as a queue head.
bad_s <= '1' when (tv_s = '1' and ty_s /= TYP_QH) else '0';
bad_type <= bad_s;
-- Dereference only when the schedule is running, a word has been fetched,
-- the T bit is clear, and the type is one that belongs here.
fol_s <= '1' when (walk_s = '1' and word_valid = '1'
and link_word(LINK_T_BIT) = '0' and bad_s = '0')
else '0';
follow <= fol_s;
-- ---- THE TERMINATION RULE ----
--
-- Arriving at the H-bit node with Reclamation clear means a whole lap
-- produced no work. That -- and only that -- is how this traversal ends.
vis_s <= walk_s and word_valid;
lap_s <= vis_s and node_is_head;
idle_s <= '1' when (lap_s = '1' and reclaim_r = '0'
and node_did_work = '0') else '0';
async_idle <= idle_s;
-- Written as one priority chain rather than a sequence of assignments:
-- work done AT the head node must leave Reclamation SET even though
-- arriving at the head clears it, and leaving that to VHDL's
-- last-assignment rule is how the two orderings diverge between languages.
reclaim_n <= '0' when async_enable = '0'
else '1' when (node_did_work = '1' and vis_s = '1') -- work sets
else '0' when lap_s = '1' -- a clean lap
else reclaim_r;
-- Software restarts a stopped walker by ringing the doorbell -- which is
-- the only way the controller can learn that the list it found empty is
-- not empty any more. Disabling the schedule also clears the latch.
stopped_n <= '0' when async_enable = '0'
else '0' when async_doorbell = '1'
else '1' when idle_s = '1'
else stopped_r;
regs : process (clk, rst_n)
begin
if rst_n = '0' then
stopped_r <= '0';
reclaim_r <= '0';
st_c <= (others => '0');
lp_c <= (others => '0');
id_c <= (others => '0');
bt_c <= (others => '0');
wk_c <= (others => '0');
elsif rising_edge(clk) then
stopped_r <= stopped_n;
reclaim_r <= reclaim_n;
if fol_s = '1' then
st_c <= st_c + 1;
end if;
if lap_s = '1' then
lp_c <= lp_c + 1;
end if;
if idle_s = '1' then
id_c <= id_c + 1;
end if;
if walk_s = '1' and bad_s = '1' then
bt_c <= bt_c + 1;
end if;
if vis_s = '1' and node_did_work = '1' then
wk_c <= wk_c + 1;
end if;
end if;
end process;
n_steps <= std_logic_vector(st_c);
n_laps <= std_logic_vector(lp_c);
n_idles <= std_logic_vector(id_c);
n_bad_type <= std_logic_vector(bt_c);
n_work <= std_logic_vector(wk_c);
end architecture;VHDL's link_typ_t closes the set: a case over it must handle all four values, so "which of these belongs in this list?" becomes a question the design is forced to answer for every one of them rather than a comment in a header.
10. Seeing the Lap
Work, a lap, an empty lap, a stop, and the doorbell
ehci_async_walker — termination by lap
10 cycles11. The Testbenches
Each suite sweeps the whole decode against the whole of the walker's state:
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
2 (stopped) x 2 (reclamation) <- the walker's entire state
x 2 (async_enable) x 2 (word_valid)
x 2 (T bit) x 4 (Typ) x 2 (reserved bits 4:3)
x 2 (is_head) x 2 (did_work) x 2 (doorbell)
= 2048 one-step transitionsBoth latched bits are reached through legal transitions only — goto_state enables the schedule, does work to set Reclamation, and walks laps to set the stop latch, rather than forcing registers. And the reserved bits 4:3 are swept as a dimension of their own, because "the design masks them" and "the design happens to be tested with them zero" are different claims.
11.1 Verilog testbench
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
`timescale 1ns/1ps
module tb_aw_v;
reg clk=0, rst_n=0;
reg async_enable=0, word_valid=0, node_is_head=0, node_did_work=0;
reg async_doorbell=0;
reg [31:0] link_word=0;
wire terminate, typ_valid, follow, bad_type, walking, async_idle;
wire stopped, reclamation;
wire [1:0] typ;
wire [31:0] next_addr;
wire [31:0] n_steps, n_laps, n_idles, n_bad_type, n_work;
always #5 clk=~clk;
ehci_async_walker dut (
.clk(clk), .rst_n(rst_n), .async_enable(async_enable),
.word_valid(word_valid), .link_word(link_word),
.node_is_head(node_is_head), .node_did_work(node_did_work),
.async_doorbell(async_doorbell), .terminate(terminate), .typ(typ),
.typ_valid(typ_valid), .next_addr(next_addr), .follow(follow),
.bad_type(bad_type), .walking(walking), .async_idle(async_idle),
.stopped(stopped), .reclamation(reclamation), .n_steps(n_steps),
.n_laps(n_laps), .n_idles(n_idles), .n_bad_type(n_bad_type),
.n_work(n_work));
localparam [1:0] TYP_ITD=0, TYP_QH=1, TYP_SITD=2, TYP_FSTN=3;
// ---- SHADOW MODEL of the two latched bits ----
integer s_stopped, s_reclaim;
integer m_steps, m_laps, m_idles, m_bad, m_work;
integer errors=0, i, a, b, c, d, e, f, g, h, k;
integer steps_before;
integer n_exh=0;
integer n_typ [0:3];
integer n_follow=0, n_term=0, n_badt=0, n_idle=0, n_lap=0;
task check(input cond, input [639:0] msg);
begin if (!cond) begin errors=errors+1;
if (errors <= 25)
$display(" FAIL: %0s (en=%b vld=%b word=%h head=%b work=%b db=%b | T=%b typ=%0d tv=%b addr=%h fol=%b bad=%b walk=%b idle=%b rec=%b || model stop=%0d rec=%0d, t=%0t)",
msg, async_enable, word_valid, link_word, node_is_head,
node_did_work, async_doorbell, terminate, typ, typ_valid,
next_addr, follow, bad_type, walking, async_idle,
reclamation, s_stopped, s_reclaim, $time);
end end
endtask
task check_comb;
reg e_term, e_tv, e_bad, e_follow, e_walk, e_idle, e_vis, e_lap;
reg [31:0] e_addr;
reg [1:0] e_typ;
begin
// The model builds the decode from named bit extractions rather than
// the design's direct indexing -- a different route to the same answer.
e_walk = async_enable && (s_stopped == 0);
e_term = word_valid && (link_word[0] == 1'b1);
e_tv = word_valid && (link_word[0] == 1'b0);
e_typ = link_word[2:1];
e_addr = link_word & 32'hFFFF_FFE0;
e_bad = e_tv && (e_typ != TYP_QH);
e_follow = e_walk && e_tv && !e_bad;
e_vis = e_walk && word_valid;
e_lap = e_vis && node_is_head;
e_idle = e_lap && (s_reclaim == 0) && !node_did_work;
check(terminate === e_term, "terminate matches the model");
check(typ_valid === e_tv, "typ_valid matches the model");
check(typ === e_typ, "typ matches the model");
check(next_addr === e_addr, "next_addr matches the model");
check(bad_type === e_bad, "bad_type matches the model");
check(follow === e_follow, "follow matches the model");
check(walking === e_walk, "walking matches the model");
check(async_idle === e_idle, "async_idle matches the model");
check(stopped === (s_stopped != 0), "stopped matches the model");
check(reclamation === (s_reclaim != 0), "reclamation matches the model");
// ---- SAFETY PROPERTIES, independent of the model ----
// 1. THE property. With the T bit set the word is not an address and
// not a type -- nothing may be dereferenced and nothing decoded.
if (terminate) begin
check(!follow,
"a terminated link was followed -- that word is not an address");
check(!typ_valid,
"a terminated link reported a type -- there is no next node");
check(!bad_type,
"a terminated link was type-checked at all");
end
// 2. The address is always 32-byte aligned: the low five bits carry
// other fields and must be masked, never assumed zero.
check(next_addr[4:0] === 5'd0,
"next_addr is not 32-byte aligned -- the T/Typ bits leaked into it");
// 3. Only a Queue Head may be followed in the ASYNC list. An iTD or
// siTD here would be read as a queue head.
if (follow)
check(typ === TYP_QH,
"a non-QH node was followed in the asynchronous list");
// 4. Nothing happens at all while the schedule is disabled.
if (!async_enable) begin
check(!walking, "the walker ran with the schedule disabled");
check(!follow, "a link was followed with the schedule disabled");
check(!async_idle, "the idle condition fired with the schedule off");
end
// 5. A stopped walker does not walk.
if (stopped) check(!walking, "a stopped walker was still walking");
// 6. The idle condition requires a lap: it cannot fire at a node that
// is not the head.
if (async_idle)
check(node_is_head && walking && word_valid,
"the empty-list condition fired somewhere other than the head");
// 7. A lap that DID work never idles -- that is the whole point of the
// reclamation flag.
if (node_did_work && walking && word_valid)
check(!async_idle,
"the walker stopped on a lap in which it did work");
if (e_tv) n_typ[e_typ] = n_typ[e_typ] + 1;
if (e_follow) n_follow = n_follow + 1;
if (e_term) n_term = n_term + 1;
if (e_bad) n_badt = n_badt + 1;
if (e_idle) n_idle = n_idle + 1;
if (e_lap) n_lap = n_lap + 1;
end
endtask
task model_step;
reg e_walk, e_vis, e_lap, e_idle, e_tv, e_bad, e_follow;
reg [1:0] e_typ;
begin
e_walk = async_enable && (s_stopped == 0);
e_vis = e_walk && word_valid;
e_lap = e_vis && node_is_head;
e_idle = e_lap && (s_reclaim == 0) && !node_did_work;
e_tv = word_valid && (link_word[0] == 1'b0);
e_typ = link_word[2:1];
e_bad = e_tv && (e_typ != TYP_QH);
e_follow = e_walk && e_tv && !e_bad;
if (e_follow) m_steps = m_steps + 1;
if (e_lap) m_laps = m_laps + 1;
if (e_idle) m_idles = m_idles + 1;
if (e_walk && e_bad) m_bad = m_bad + 1;
if (e_vis && node_did_work) m_work = m_work + 1;
if (!async_enable) s_stopped = 0;
else if (async_doorbell) s_stopped = 0;
else if (e_idle) s_stopped = 1;
if (!async_enable) s_reclaim = 0;
else if (node_did_work && e_vis) s_reclaim = 1;
else if (e_lap) s_reclaim = 0;
end
endtask
task step;
begin
#1;
check_comb;
model_step;
@(posedge clk); #1;
check(stopped === (s_stopped != 0), "stopped tracked the model");
check(reclamation === (s_reclaim != 0), "reclamation tracked the model");
check(n_steps === m_steps[31:0], "n_steps matches the model");
check(n_laps === m_laps[31:0], "n_laps matches the model");
check(n_idles === m_idles[31:0], "n_idles matches the model");
check(n_bad_type === m_bad[31:0], "n_bad_type matches the model");
check(n_work === m_work[31:0], "n_work matches the model");
end
endtask
task idle_in;
begin
word_valid=0; node_is_head=0; node_did_work=0; async_doorbell=0;
end
endtask
task hard_reset;
begin
rst_n=0; async_enable=0; link_word=0; idle_in;
@(posedge clk); #1; @(posedge clk); #1; rst_n=1; #1;
s_stopped=0; s_reclaim=0;
m_steps=0; m_laps=0; m_idles=0; m_bad=0; m_work=0;
end
endtask
// Force the two latched bits into a chosen combination using only legal
// transitions -- no register forcing.
task goto_state(input want_stopped, input want_reclaim);
begin
hard_reset;
async_enable=1; step; idle_in;
if (want_reclaim) begin
// any work at any node sets Reclamation
word_valid=1; link_word=32'h0000_0002; node_did_work=1; step; idle_in;
end
if (want_stopped) begin
// a lap at the head with nothing done stops the walker; do it
// without disturbing Reclamation if it is wanted set
if (want_reclaim) begin
// arriving at the head clears Reclamation, so stop first then
// re-set it with a doorbell restart and one unit of work
word_valid=1; link_word=32'h0000_0002; node_is_head=1; step; idle_in;
word_valid=1; link_word=32'h0000_0002; node_is_head=1; step; idle_in;
end else begin
word_valid=1; link_word=32'h0000_0002; node_is_head=1; step; idle_in;
end
end
#1;
check(stopped === want_stopped, "goto_state reached the stopped bit");
if (!want_stopped)
check(reclamation === want_reclaim,
"goto_state reached the reclamation bit");
end
endtask
initial begin
for (i=0;i<4;i=i+1) n_typ[i]=0;
hard_reset;
check(!walking, "the walker is idle after reset");
check(!reclamation, "with reclamation clear");
// ===== A. EXHAUSTIVE sweep of the decode and the lap rule =====
// 2 (stopped) x 2 (reclamation) x 2 (async_enable) x 2 (word_valid)
// x 2 (T) x 4 (Typ) x 2 (reserved bits 4:3) x 2 (is_head)
// x 2 (did_work) x 2 (doorbell)
// = 2048 one-step transitions: the whole decode against the whole of
// the walker's state.
for (k=0; k<2; k=k+1) // stopped
for (a=0; a<2; a=a+1) // reclamation
for (b=0; b<2; b=b+1) // async_enable
for (c=0; c<2; c=c+1) // word_valid
for (d=0; d<2; d=d+1) // T bit
for (e=0; e<4; e=e+1) // Typ
for (f=0; f<2; f=f+1) // reserved bits 4:3
for (g=0; g<2; g=g+1) // is_head
for (h=0; h<2; h=h+1) // did_work
for (i=0; i<2; i=i+1) begin // doorbell
goto_state(k[0], a[0]);
async_enable = b[0];
word_valid = c[0];
// a recognisable address in the high bits, plus the reserved
// bits, the Typ field and the T bit in the low five
link_word = {27'h5A5_A5A5, f[0], f[0], e[1:0], d[0]};
node_is_head = g[0];
node_did_work = h[0];
async_doorbell = i[0];
step;
n_exh = n_exh + 1;
idle_in;
end
$display(" exhaustive walker sweep: %0d of %0d transitions verified",
n_exh, 2*2*2*2*2*4*2*2*2*2);
// ===== B. directed: a lap round the ring =====
hard_reset; async_enable=1; step; idle_in;
check(walking, "enabling the schedule starts the walk");
// 1. A QH link with T clear: follow it, address masked.
word_valid=1; link_word=32'h1234_5673; // typ=01 (QH), T=1 -> terminate
#1;
check(terminate, "bit 0 set means TERMINATE");
check(!follow, "so nothing is dereferenced");
check(!typ_valid, "and the type field means nothing");
step; idle_in;
// 2. The same word with T clear.
word_valid=1; link_word=32'h1234_5672; // typ=01 (QH), T=0
#1;
check(!terminate, "bit 0 clear means there IS a next node");
check(typ_valid && (typ === TYP_QH), "and it is a Queue Head");
check(follow, "so it is followed");
check(next_addr === 32'h1234_5660,
"with the low five bits masked off -- 32-byte aligned");
step; idle_in;
check(n_steps === 32'd1, "one step taken");
// 3. An isochronous descriptor in the ASYNC list: not followed.
word_valid=1; link_word=32'h1234_5670; // typ=00 (iTD), T=0
#1;
check(typ_valid && (typ === TYP_ITD), "an iTD was decoded");
check(bad_type, "which does not belong in the asynchronous list");
check(!follow, "so it is NOT followed");
step; idle_in;
check(n_bad_type === 32'd1, "and the software error was counted");
// 4. Reserved bits 4:3 are masked, not assumed zero.
word_valid=1; link_word=32'hABCD_EF1A; // bits 4:3 = 11, typ=01, T=0
#1;
check(follow, "a QH with reserved bits set is still followed");
check(next_addr === 32'hABCD_EF00,
"and the reserved bits are masked out of the address");
step; idle_in;
// ===== C. directed: the H bit and the reclamation flag =====
hard_reset; async_enable=1; step; idle_in;
// 5. Work at an ordinary node sets Reclamation.
word_valid=1; link_word=32'h0000_0002; node_did_work=1; step; idle_in;
#1; check(reclamation, "doing work sets the Reclamation flag");
// 6. Arriving at the head with Reclamation set clears it and carries on.
word_valid=1; link_word=32'h0000_0002; node_is_head=1; #1;
check(!async_idle,
"the head with Reclamation set does NOT stop the walker");
step; idle_in;
#1;
check(!reclamation, "but it does clear the flag");
check(walking, "and the walk continues");
check(n_laps === 32'd1, "one lap completed");
// 7. THE case. Arriving at the head again with nothing done since is a
// whole lap with no work: the list is empty and the walker stops.
word_valid=1; link_word=32'h0000_0002; node_is_head=1; #1;
check(async_idle,
"a second head visit with no work means the list is EMPTY");
step; idle_in;
#1;
check(stopped, "so the walker stops");
check(!walking, "and stops walking");
check(n_idles === 32'd1, "one empty-list detection");
// 8. It stays stopped. The list did not change; nothing has told it to
// look again.
steps_before = n_steps;
word_valid=1; link_word=32'h0000_0002; step; idle_in;
#1; check(!walking, "a stopped walker stays stopped");
check(n_steps === steps_before[31:0],
"and takes no FURTHER steps -- the counter did not move");
// 9. The doorbell is how software says "I added work, look again".
async_doorbell=1; step; idle_in;
#1;
check(!stopped, "the doorbell clears the stop");
check(walking, "and the walk restarts");
// 10. Work AT the head node leaves Reclamation set, even though
// arriving at the head clears it. Order matters.
hard_reset; async_enable=1; step; idle_in;
word_valid=1; link_word=32'h0000_0002;
node_is_head=1; node_did_work=1; #1;
check(!async_idle, "a head visit that did work does not stop the walker");
step; idle_in;
#1;
check(reclamation,
"and leaves Reclamation SET -- work outranks the head's clear");
// 11. Disabling the schedule clears everything.
async_enable=0; step; idle_in;
#1;
check(!walking, "disabling the schedule stops the walk");
check(!reclamation, "and clears Reclamation");
check(!stopped, "and the stop latch");
// ===== D. randomised =====
hard_reset; async_enable=1;
for (i=0;i<40000;i=i+1) begin
async_enable = ({$random}%32)!=0;
word_valid = ({$random}%4)!=0;
link_word = {$random};
// bias hard toward Queue Heads, which is what an async list contains
if (({$random}%4)!=0) link_word[2:1] = TYP_QH;
if (({$random}%6)!=0) link_word[0] = 1'b0;
node_is_head = ({$random}%8)==0;
node_did_work = ({$random}%3)==0;
async_doorbell = ({$random}%64)==0;
step;
end
for (i=0;i<4;i=i+1)
check(n_typ[i] > 500, "every link type was decoded many times");
check(n_follow > 5000, "links were followed many times");
check(n_term > 2000, "terminated links were seen many times");
check(n_badt > 1000, "non-QH nodes in the async list were seen often");
check(n_lap > 1000, "the head node was reached often");
check(n_idle > 200, "the empty-list condition fired often");
$display("");
$display(" REACH: transitions=%0d | types decoded: itd=%0d qh=%0d sitd=%0d fstn=%0d",
n_exh, n_typ[0], n_typ[1], n_typ[2], n_typ[3]);
$display(" CASES: followed=%0d terminated=%0d bad-type=%0d laps=%0d empty-list=%0d",
n_follow, n_term, n_badt, n_lap, n_idle);
$display(" COUNTERS: steps=%0d laps=%0d idles=%0d bad-type=%0d work=%0d",
n_steps, n_laps, n_idles, n_bad_type, n_work);
$display(" [Verilog] ehci_async_walker: %0d errors", errors);
$display(" [Verilog] %0s", errors==0 ? "PASS" : "FAIL");
$display("");
$finish;
end
endmodule11.2 SystemVerilog testbench
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
`timescale 1ns/1ps
module tb_aw_sv;
import ehci_walker_pkg::*;
logic clk=0, rst_n=0;
logic async_enable=0, word_valid=0, node_is_head=0, node_did_work=0;
logic async_doorbell=0;
logic [31:0] link_word=0;
logic terminate, typ_valid, follow, bad_type, walking, async_idle;
logic stopped, reclamation;
link_typ_e typ;
logic [31:0] next_addr;
logic [31:0] n_steps, n_laps, n_idles, n_bad_type, n_work;
// Icarus seeds $random and $urandom identically, so an unseeded run would
// replay the Verilog suite's stimulus exactly. See chapter 20.5 section 9.2.
int urandom_seed = 22101;
always #5 clk=~clk;
ehci_async_walker dut (
.clk, .rst_n, .async_enable, .word_valid, .link_word, .node_is_head,
.node_did_work, .async_doorbell, .terminate, .typ, .typ_valid,
.next_addr, .follow, .bad_type, .walking, .async_idle, .stopped,
.reclamation, .n_steps, .n_laps, .n_idles, .n_bad_type, .n_work);
// ---- SHADOW MODEL of the two latched bits ----
int s_stopped, s_reclaim;
int m_steps, m_laps, m_idles, m_bad, m_work;
int errors=0, i, a, b, c, d, e, f, g, h, k;
int steps_before;
int n_exh=0;
int n_typ [4];
int n_follow=0, n_term=0, n_badt=0, n_idle=0, n_lap=0;
task automatic check(input bit cond, input string msg);
// Icarus will not call .name() on a net, so the enum output is copied
// into a variable of the same type before being printed.
link_typ_e ty_v;
if (!cond) begin
errors++;
ty_v = typ;
if (errors <= 25)
$display(" FAIL: %0s (en=%b vld=%b word=%h head=%b work=%b db=%b | T=%b typ=%s tv=%b addr=%h fol=%b bad=%b walk=%b idle=%b rec=%b || model stop=%0d rec=%0d, t=%0t)",
msg, async_enable, word_valid, link_word, node_is_head,
node_did_work, async_doorbell, terminate, ty_v.name(),
typ_valid, next_addr, follow, bad_type, walking, async_idle,
reclamation, s_stopped, s_reclaim, $time);
end
endtask
task automatic check_comb;
bit e_term, e_tv, e_bad, e_follow, e_walk, e_idle, e_vis, e_lap;
logic [31:0] e_addr;
link_typ_e e_typ;
begin
// The model builds the decode from named bit extractions rather than
// the design's direct indexing -- a different route to the same answer.
e_walk = async_enable && (s_stopped == 0);
e_term = word_valid && (link_word[0] == 1'b1);
e_tv = word_valid && (link_word[0] == 1'b0);
e_typ = link_typ_e'(link_word[2:1]);
e_addr = link_word & 32'hFFFF_FFE0;
e_bad = e_tv && (e_typ != TYP_QH);
e_follow = e_walk && e_tv && !e_bad;
e_vis = e_walk && word_valid;
e_lap = e_vis && node_is_head;
e_idle = e_lap && (s_reclaim == 0) && !node_did_work;
check(terminate === e_term, "terminate matches the model");
check(typ_valid === e_tv, "typ_valid matches the model");
check(typ === e_typ, "typ matches the model");
check(next_addr === e_addr, "next_addr matches the model");
check(bad_type === e_bad, "bad_type matches the model");
check(follow === e_follow, "follow matches the model");
check(walking === e_walk, "walking matches the model");
check(async_idle === e_idle, "async_idle matches the model");
check(stopped === (s_stopped != 0), "stopped matches the model");
check(reclamation === (s_reclaim != 0), "reclamation matches the model");
// ---- SAFETY PROPERTIES, independent of the model ----
// 1. THE property. With the T bit set the word is not an address and
// not a type -- nothing may be dereferenced and nothing decoded.
if (terminate) begin
check(!follow,
"a terminated link was followed -- that word is not an address");
check(!typ_valid,
"a terminated link reported a type -- there is no next node");
check(!bad_type,
"a terminated link was type-checked at all");
end
// 2. The address is always 32-byte aligned: the low five bits carry
// other fields and must be masked, never assumed zero.
check(next_addr[4:0] === 5'd0,
"next_addr is not 32-byte aligned -- the T/Typ bits leaked into it");
// 3. Only a Queue Head may be followed in the ASYNC list. An iTD or
// siTD here would be read as a queue head.
if (follow)
check(typ === TYP_QH,
"a non-QH node was followed in the asynchronous list");
// 4. Nothing happens at all while the schedule is disabled.
if (!async_enable) begin
check(!walking, "the walker ran with the schedule disabled");
check(!follow, "a link was followed with the schedule disabled");
check(!async_idle, "the idle condition fired with the schedule off");
end
// 5. A stopped walker does not walk.
if (stopped) check(!walking, "a stopped walker was still walking");
// 6. The idle condition requires a lap: it cannot fire at a node that
// is not the head.
if (async_idle)
check(node_is_head && walking && word_valid,
"the empty-list condition fired somewhere other than the head");
// 7. A lap that DID work never idles -- that is the whole point of the
// reclamation flag.
if (node_did_work && walking && word_valid)
check(!async_idle,
"the walker stopped on a lap in which it did work");
if (e_tv) n_typ[int'(e_typ)] = n_typ[int'(e_typ)] + 1;
if (e_follow) n_follow = n_follow + 1;
if (e_term) n_term = n_term + 1;
if (e_bad) n_badt = n_badt + 1;
if (e_idle) n_idle = n_idle + 1;
if (e_lap) n_lap = n_lap + 1;
end
endtask
task automatic model_step;
bit e_walk, e_vis, e_lap, e_idle, e_tv, e_bad, e_follow;
link_typ_e e_typ;
begin
e_walk = async_enable && (s_stopped == 0);
e_vis = e_walk && word_valid;
e_lap = e_vis && node_is_head;
e_idle = e_lap && (s_reclaim == 0) && !node_did_work;
e_tv = word_valid && (link_word[0] == 1'b0);
e_typ = link_typ_e'(link_word[2:1]);
e_bad = e_tv && (e_typ != TYP_QH);
e_follow = e_walk && e_tv && !e_bad;
if (e_follow) m_steps = m_steps + 1;
if (e_lap) m_laps = m_laps + 1;
if (e_idle) m_idles = m_idles + 1;
if (e_walk && e_bad) m_bad = m_bad + 1;
if (e_vis && node_did_work) m_work = m_work + 1;
if (!async_enable) s_stopped = 0;
else if (async_doorbell) s_stopped = 0;
else if (e_idle) s_stopped = 1;
if (!async_enable) s_reclaim = 0;
else if (node_did_work && e_vis) s_reclaim = 1;
else if (e_lap) s_reclaim = 0;
end
endtask
task automatic step;
begin
#1;
check_comb;
model_step;
@(posedge clk); #1;
check(stopped === (s_stopped != 0), "stopped tracked the model");
check(reclamation === (s_reclaim != 0), "reclamation tracked the model");
check(n_steps === 32'(m_steps), "n_steps matches the model");
check(n_laps === 32'(m_laps), "n_laps matches the model");
check(n_idles === 32'(m_idles), "n_idles matches the model");
check(n_bad_type === 32'(m_bad), "n_bad_type matches the model");
check(n_work === 32'(m_work), "n_work matches the model");
end
endtask
task automatic idle_in;
begin
word_valid=0; node_is_head=0; node_did_work=0; async_doorbell=0;
end
endtask
task automatic hard_reset;
begin
rst_n=0; async_enable=0; link_word=0; idle_in;
@(posedge clk); #1; @(posedge clk); #1; rst_n=1; #1;
s_stopped=0; s_reclaim=0;
m_steps=0; m_laps=0; m_idles=0; m_bad=0; m_work=0;
end
endtask
// Force the two latched bits into a chosen combination using only legal
// transitions -- no register forcing.
task automatic goto_state(input bit want_stopped, input bit want_reclaim);
begin
hard_reset;
async_enable=1; step; idle_in;
if (want_reclaim) begin
// any work at any node sets Reclamation
word_valid=1; link_word=32'h0000_0002; node_did_work=1; step; idle_in;
end
if (want_stopped) begin
// a lap at the head with nothing done stops the walker; do it
// without disturbing Reclamation if it is wanted set
if (want_reclaim) begin
// arriving at the head clears Reclamation, so stop first then
// re-set it with a doorbell restart and one unit of work
word_valid=1; link_word=32'h0000_0002; node_is_head=1; step; idle_in;
word_valid=1; link_word=32'h0000_0002; node_is_head=1; step; idle_in;
end else begin
word_valid=1; link_word=32'h0000_0002; node_is_head=1; step; idle_in;
end
end
#1;
check(stopped === want_stopped, "goto_state reached the stopped bit");
if (!want_stopped)
check(reclamation === want_reclaim,
"goto_state reached the reclamation bit");
end
endtask
initial begin
void'($urandom(urandom_seed));
foreach (n_typ[i]) n_typ[i]=0;
hard_reset;
check(!walking, "the walker is idle after reset");
check(!reclamation, "with reclamation clear");
// ===== A. EXHAUSTIVE sweep of the decode and the lap rule =====
// 2 (stopped) x 2 (reclamation) x 2 (async_enable) x 2 (word_valid)
// x 2 (T) x 4 (Typ) x 2 (reserved bits 4:3) x 2 (is_head)
// x 2 (did_work) x 2 (doorbell)
// = 2048 one-step transitions: the whole decode against the whole of
// the walker's state.
for (k=0; k<2; k=k+1) // stopped
for (a=0; a<2; a=a+1) // reclamation
for (b=0; b<2; b=b+1) // async_enable
for (c=0; c<2; c=c+1) // word_valid
for (d=0; d<2; d=d+1) // T bit
for (e=0; e<4; e=e+1) // Typ
for (f=0; f<2; f=f+1) // reserved bits 4:3
for (g=0; g<2; g=g+1) // is_head
for (h=0; h<2; h=h+1) // did_work
for (i=0; i<2; i=i+1) begin // doorbell
goto_state(k[0], a[0]);
async_enable = b[0];
word_valid = c[0];
// a recognisable address in the high bits, plus the reserved
// bits, the Typ field and the T bit in the low five
link_word = {27'h5A5_A5A5, f[0], f[0], e[1:0], d[0]};
node_is_head = g[0];
node_did_work = h[0];
async_doorbell = i[0];
step;
n_exh = n_exh + 1;
idle_in;
end
$display(" exhaustive walker sweep: %0d of %0d transitions verified",
n_exh, 2*2*2*2*2*4*2*2*2*2);
// ===== B. directed: a lap round the ring =====
hard_reset; async_enable=1; step; idle_in;
check(walking, "enabling the schedule starts the walk");
// 1. A QH link with T clear: follow it, address masked.
word_valid=1; link_word=32'h1234_5673; // typ=01 (QH), T=1 -> terminate
#1;
check(terminate, "bit 0 set means TERMINATE");
check(!follow, "so nothing is dereferenced");
check(!typ_valid, "and the type field means nothing");
step; idle_in;
// 2. The same word with T clear.
word_valid=1; link_word=32'h1234_5672; // typ=01 (QH), T=0
#1;
check(!terminate, "bit 0 clear means there IS a next node");
check(typ_valid && (typ === TYP_QH), "and it is a Queue Head");
check(follow, "so it is followed");
check(next_addr === 32'h1234_5660,
"with the low five bits masked off -- 32-byte aligned");
step; idle_in;
check(n_steps === 32'd1, "one step taken");
// 3. An isochronous descriptor in the ASYNC list: not followed.
word_valid=1; link_word=32'h1234_5670; // typ=00 (iTD), T=0
#1;
check(typ_valid && (typ === TYP_ITD), "an iTD was decoded");
check(bad_type, "which does not belong in the asynchronous list");
check(!follow, "so it is NOT followed");
step; idle_in;
check(n_bad_type === 32'd1, "and the software error was counted");
// 4. Reserved bits 4:3 are masked, not assumed zero.
word_valid=1; link_word=32'hABCD_EF1A; // bits 4:3 = 11, typ=01, T=0
#1;
check(follow, "a QH with reserved bits set is still followed");
check(next_addr === 32'hABCD_EF00,
"and the reserved bits are masked out of the address");
step; idle_in;
// ===== C. directed: the H bit and the reclamation flag =====
hard_reset; async_enable=1; step; idle_in;
// 5. Work at an ordinary node sets Reclamation.
word_valid=1; link_word=32'h0000_0002; node_did_work=1; step; idle_in;
#1; check(reclamation, "doing work sets the Reclamation flag");
// 6. Arriving at the head with Reclamation set clears it and carries on.
word_valid=1; link_word=32'h0000_0002; node_is_head=1; #1;
check(!async_idle,
"the head with Reclamation set does NOT stop the walker");
step; idle_in;
#1;
check(!reclamation, "but it does clear the flag");
check(walking, "and the walk continues");
check(n_laps === 32'd1, "one lap completed");
// 7. THE case. Arriving at the head again with nothing done since is a
// whole lap with no work: the list is empty and the walker stops.
word_valid=1; link_word=32'h0000_0002; node_is_head=1; #1;
check(async_idle,
"a second head visit with no work means the list is EMPTY");
step; idle_in;
#1;
check(stopped, "so the walker stops");
check(!walking, "and stops walking");
check(n_idles === 32'd1, "one empty-list detection");
// 8. It stays stopped. The list did not change; nothing has told it to
// look again.
steps_before = n_steps;
word_valid=1; link_word=32'h0000_0002; step; idle_in;
#1; check(!walking, "a stopped walker stays stopped");
check(n_steps === 32'(steps_before),
"and takes no FURTHER steps -- the counter did not move");
// 9. The doorbell is how software says "I added work, look again".
async_doorbell=1; step; idle_in;
#1;
check(!stopped, "the doorbell clears the stop");
check(walking, "and the walk restarts");
// 10. Work AT the head node leaves Reclamation set, even though
// arriving at the head clears it. Order matters.
hard_reset; async_enable=1; step; idle_in;
word_valid=1; link_word=32'h0000_0002;
node_is_head=1; node_did_work=1; #1;
check(!async_idle, "a head visit that did work does not stop the walker");
step; idle_in;
#1;
check(reclamation,
"and leaves Reclamation SET -- work outranks the head's clear");
// 11. Disabling the schedule clears everything.
async_enable=0; step; idle_in;
#1;
check(!walking, "disabling the schedule stops the walk");
check(!reclamation, "and clears Reclamation");
check(!stopped, "and the stop latch");
// ===== D. randomised =====
hard_reset; async_enable=1;
for (i=0;i<40000;i=i+1) begin
async_enable = ($urandom%32)!=0;
word_valid = ($urandom%4)!=0;
link_word = $urandom;
// bias hard toward Queue Heads, which is what an async list contains
if (($urandom%4)!=0) link_word[2:1] = 2'(TYP_QH);
if (($urandom%6)!=0) link_word[0] = 1'b0;
node_is_head = ($urandom%8)==0;
node_did_work = ($urandom%3)==0;
async_doorbell = ($urandom%64)==0;
step;
end
foreach (n_typ[i]) check(n_typ[i] > 500, "every link type was decoded many times");
check(n_follow > 5000, "links were followed many times");
check(n_term > 2000, "terminated links were seen many times");
check(n_badt > 1000, "non-QH nodes in the async list were seen often");
check(n_lap > 1000, "the head node was reached often");
check(n_idle > 200, "the empty-list condition fired often");
$display("");
$display(" REACH: transitions=%0d | types decoded: itd=%0d qh=%0d sitd=%0d fstn=%0d",
n_exh, n_typ[0], n_typ[1], n_typ[2], n_typ[3]);
$display(" CASES: followed=%0d terminated=%0d bad-type=%0d laps=%0d empty-list=%0d",
n_follow, n_term, n_badt, n_lap, n_idle);
$display(" COUNTERS: steps=%0d laps=%0d idles=%0d bad-type=%0d work=%0d",
n_steps, n_laps, n_idles, n_bad_type, n_work);
$display(" [SystemVerilog] ehci_async_walker: %0d errors", errors);
$display(" [SystemVerilog] %0s", errors==0 ? "PASS" : "FAIL");
$display("");
$finish;
end
endmodule11.3 VHDL testbench
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
use ieee.math_real.all;
use work.ehci_walker_pkg.all;
entity tb_aw_vhdl is
end entity;
architecture sim of tb_aw_vhdl is
signal clk : std_logic := '0';
signal rst_n : std_logic := '0';
signal async_enable, word_valid, node_is_head : std_logic := '0';
signal node_did_work, async_doorbell : std_logic := '0';
signal link_word : std_logic_vector(31 downto 0) := (others => '0');
signal terminate, typ_valid, follow, bad_type : std_logic;
signal walking, async_idle, stopped, reclamation : std_logic;
signal typ : std_logic_vector(1 downto 0);
signal next_addr : std_logic_vector(31 downto 0);
signal n_steps, n_laps, n_idles, n_bad_type, n_work
: std_logic_vector(31 downto 0);
signal running : boolean := true;
type cnt4_t is array (0 to 3) of integer;
begin
clk <= not clk after 5 ns when running else '0';
dut : entity work.ehci_async_walker
port map (clk => clk, rst_n => rst_n, async_enable => async_enable,
word_valid => word_valid, link_word => link_word,
node_is_head => node_is_head, node_did_work => node_did_work,
async_doorbell => async_doorbell, terminate => terminate,
typ => typ, typ_valid => typ_valid, next_addr => next_addr,
follow => follow, bad_type => bad_type, walking => walking,
async_idle => async_idle, stopped => stopped,
reclamation => reclamation, n_steps => n_steps,
n_laps => n_laps, n_idles => n_idles, n_bad_type => n_bad_type,
n_work => n_work);
stim : process
variable seed1 : positive := 2917;
variable seed2 : positive := 8123;
variable r1 : real;
-- VHDL-2008 requires a shared variable to have a protected type, so the
-- bookkeeping lives inside the single stimulus process instead.
variable errors : integer := 0;
-- SHADOW MODEL of the two latched bits.
variable s_stopped, s_reclaim : integer := 0;
variable m_steps, m_laps, m_idles, m_bad, m_work : integer := 0;
variable n_exh : integer := 0;
variable n_typ : cnt4_t := (others => 0);
variable n_follow, n_term, n_badt, n_idle, n_lap : integer := 0;
variable steps_before : integer := 0;
procedure check(cond : boolean; msg : string) is
begin
if not cond then
errors := errors + 1;
if errors <= 25 then
report " FAIL: " & msg
& " (en=" & std_logic'image(async_enable)(2)
& " vld=" & std_logic'image(word_valid)(2)
& " head=" & std_logic'image(node_is_head)(2)
& " work=" & std_logic'image(node_did_work)(2)
& " db=" & std_logic'image(async_doorbell)(2)
& " | T=" & std_logic'image(terminate)(2)
& " typ=" & integer'image(to_integer(unsigned(typ)))
& " tv=" & std_logic'image(typ_valid)(2)
& " fol=" & std_logic'image(follow)(2)
& " bad=" & std_logic'image(bad_type)(2)
& " walk=" & std_logic'image(walking)(2)
& " idle=" & std_logic'image(async_idle)(2)
& " rec=" & std_logic'image(reclamation)(2)
& " || model stop=" & integer'image(s_stopped)
& " rec=" & integer'image(s_reclaim)
& ")" severity note;
end if;
end if;
end procedure;
procedure rnd(variable v : out integer; m : integer) is
begin
uniform(seed1, seed2, r1);
v := integer(floor(r1 * real(m)));
end procedure;
procedure check_comb is
variable e_term, e_tv, e_bad, e_follow : boolean;
variable e_walk, e_idle, e_vis, e_lap : boolean;
variable e_typ : link_typ_t;
variable e_addr : std_logic_vector(31 downto 0);
begin
-- The model builds the decode from named slices rather than the
-- design's helper functions -- a different route to the same answer.
e_walk := async_enable = '1' and s_stopped = 0;
e_term := word_valid = '1' and link_word(0) = '1';
e_tv := word_valid = '1' and link_word(0) = '0';
e_typ := link_typ_t'val(to_integer(unsigned(link_word(2 downto 1))));
e_addr := link_word(31 downto 5) & "00000";
e_bad := e_tv and e_typ /= TYP_QH;
e_follow := e_walk and e_tv and not e_bad;
e_vis := e_walk and word_valid = '1';
e_lap := e_vis and node_is_head = '1';
e_idle := e_lap and s_reclaim = 0 and node_did_work = '0';
check((terminate = '1') = e_term, "terminate matches the model");
check((typ_valid = '1') = e_tv, "typ_valid matches the model");
check(typ = typ_code(e_typ), "typ matches the model");
check(next_addr = e_addr, "next_addr matches the model");
check((bad_type = '1') = e_bad, "bad_type matches the model");
check((follow = '1') = e_follow, "follow matches the model");
check((walking = '1') = e_walk, "walking matches the model");
check((async_idle = '1') = e_idle, "async_idle matches the model");
check((stopped = '1') = (s_stopped /= 0), "stopped matches the model");
check((reclamation = '1') = (s_reclaim /= 0),
"reclamation matches the model");
-- ---- SAFETY PROPERTIES, independent of the model ----
-- 1. THE property. With the T bit set the word is not an address and
-- not a type -- nothing may be dereferenced and nothing decoded.
if terminate = '1' then
check(follow = '0',
"a terminated link was followed -- that word is not an address");
check(typ_valid = '0',
"a terminated link reported a type -- there is no next node");
check(bad_type = '0',
"a terminated link was type-checked at all");
end if;
-- 2. The address is always 32-byte aligned.
check(next_addr(4 downto 0) = "00000",
"next_addr is not 32-byte aligned -- the T/Typ bits leaked into it");
-- 3. Only a Queue Head may be followed in the ASYNC list.
if follow = '1' then
check(typ = typ_code(TYP_QH),
"a non-QH node was followed in the asynchronous list");
end if;
-- 4. Nothing happens at all while the schedule is disabled.
if async_enable = '0' then
check(walking = '0', "the walker ran with the schedule disabled");
check(follow = '0', "a link was followed with the schedule disabled");
check(async_idle = '0',
"the idle condition fired with the schedule off");
end if;
-- 5. A stopped walker does not walk.
if stopped = '1' then
check(walking = '0', "a stopped walker was still walking");
end if;
-- 6. The idle condition requires a lap.
if async_idle = '1' then
check(node_is_head = '1' and walking = '1' and word_valid = '1',
"the empty-list condition fired somewhere other than the head");
end if;
-- 7. A lap that DID work never idles.
if node_did_work = '1' and walking = '1' and word_valid = '1' then
check(async_idle = '0',
"the walker stopped on a lap in which it did work");
end if;
if e_tv then
n_typ(link_typ_t'pos(e_typ)) := n_typ(link_typ_t'pos(e_typ)) + 1;
end if;
if e_follow then n_follow := n_follow + 1; end if;
if e_term then n_term := n_term + 1; end if;
if e_bad then n_badt := n_badt + 1; end if;
if e_idle then n_idle := n_idle + 1; end if;
if e_lap then n_lap := n_lap + 1; end if;
end procedure;
procedure model_step is
variable e_walk, e_vis, e_lap, e_idle, e_tv, e_bad, e_follow : boolean;
variable e_typ : link_typ_t;
begin
e_walk := async_enable = '1' and s_stopped = 0;
e_vis := e_walk and word_valid = '1';
e_lap := e_vis and node_is_head = '1';
e_idle := e_lap and s_reclaim = 0 and node_did_work = '0';
e_tv := word_valid = '1' and link_word(0) = '0';
e_typ := link_typ_t'val(to_integer(unsigned(link_word(2 downto 1))));
e_bad := e_tv and e_typ /= TYP_QH;
e_follow := e_walk and e_tv and not e_bad;
if e_follow then m_steps := m_steps + 1; end if;
if e_lap then m_laps := m_laps + 1; end if;
if e_idle then m_idles := m_idles + 1; end if;
if e_walk and e_bad then m_bad := m_bad + 1; end if;
if e_vis and node_did_work = '1' then m_work := m_work + 1; end if;
if async_enable = '0' then s_stopped := 0;
elsif async_doorbell = '1' then s_stopped := 0;
elsif e_idle then s_stopped := 1;
end if;
if async_enable = '0' then s_reclaim := 0;
elsif node_did_work = '1' and e_vis then s_reclaim := 1;
elsif e_lap then s_reclaim := 0;
end if;
end procedure;
procedure step is
begin
wait for 1 ns;
check_comb;
model_step;
wait until rising_edge(clk);
wait for 1 ns;
check((stopped = '1') = (s_stopped /= 0), "stopped tracked the model");
check((reclamation = '1') = (s_reclaim /= 0),
"reclamation tracked the model");
check(n_steps = std_logic_vector(to_unsigned(m_steps, 32)),
"n_steps matches the model");
check(n_laps = std_logic_vector(to_unsigned(m_laps, 32)),
"n_laps matches the model");
check(n_idles = std_logic_vector(to_unsigned(m_idles, 32)),
"n_idles matches the model");
check(n_bad_type = std_logic_vector(to_unsigned(m_bad, 32)),
"n_bad_type matches the model");
check(n_work = std_logic_vector(to_unsigned(m_work, 32)),
"n_work matches the model");
end procedure;
procedure idle_in is
begin
word_valid <= '0'; node_is_head <= '0'; node_did_work <= '0';
async_doorbell <= '0';
end procedure;
procedure hard_reset is
begin
rst_n <= '0'; async_enable <= '0'; link_word <= (others => '0');
idle_in;
wait until rising_edge(clk); wait for 1 ns;
wait until rising_edge(clk); wait for 1 ns;
rst_n <= '1'; wait for 1 ns;
s_stopped := 0; s_reclaim := 0;
m_steps := 0; m_laps := 0; m_idles := 0; m_bad := 0; m_work := 0;
end procedure;
-- Force the two latched bits into a chosen combination using only legal
-- transitions -- no register forcing.
procedure goto_state(want_stopped : std_logic; want_reclaim : std_logic) is
begin
hard_reset;
async_enable <= '1'; step; idle_in;
if want_reclaim = '1' then
word_valid <= '1'; link_word <= x"00000002"; node_did_work <= '1';
step; idle_in;
end if;
if want_stopped = '1' then
if want_reclaim = '1' then
word_valid <= '1'; link_word <= x"00000002"; node_is_head <= '1';
step; idle_in;
word_valid <= '1'; link_word <= x"00000002"; node_is_head <= '1';
step; idle_in;
else
word_valid <= '1'; link_word <= x"00000002"; node_is_head <= '1';
step; idle_in;
end if;
end if;
wait for 1 ns;
check(stopped = want_stopped, "goto_state reached the stopped bit");
if want_stopped = '0' then
check(reclamation = want_reclaim,
"goto_state reached the reclamation bit");
end if;
end procedure;
variable iv : integer;
variable bk, ba, bb, bc, bd, bf, bg, bh, bi : std_logic;
variable lw : std_logic_vector(31 downto 0);
begin
hard_reset;
check(walking = '0', "the walker is idle after reset");
check(reclamation = '0', "with reclamation clear");
-- ===== A. EXHAUSTIVE sweep of the decode and the lap rule =====
-- 2 (stopped) x 2 (reclamation) x 2 (async_enable) x 2 (word_valid)
-- x 2 (T) x 4 (Typ) x 2 (reserved bits 4:3) x 2 (is_head)
-- x 2 (did_work) x 2 (doorbell)
-- = 2048 one-step transitions.
for k in 0 to 1 loop
if k = 1 then bk := '1'; else bk := '0'; end if;
for a in 0 to 1 loop
if a = 1 then ba := '1'; else ba := '0'; end if;
for b in 0 to 1 loop
if b = 1 then bb := '1'; else bb := '0'; end if;
for c in 0 to 1 loop
if c = 1 then bc := '1'; else bc := '0'; end if;
for d in 0 to 1 loop
if d = 1 then bd := '1'; else bd := '0'; end if;
for e in 0 to 3 loop
for f in 0 to 1 loop
if f = 1 then bf := '1'; else bf := '0'; end if;
for g in 0 to 1 loop
if g = 1 then bg := '1'; else bg := '0'; end if;
for h in 0 to 1 loop
if h = 1 then bh := '1'; else bh := '0'; end if;
for i2 in 0 to 1 loop
if i2 = 1 then bi := '1'; else bi := '0'; end if;
goto_state(bk, ba);
async_enable <= bb;
word_valid <= bc;
-- a recognisable address in the high bits, plus the
-- reserved bits, the Typ field and the T bit below
lw := "101101011010010110100101101"
& bf & bf
& std_logic_vector(to_unsigned(e, 2))
& bd;
link_word <= lw;
node_is_head <= bg;
node_did_work <= bh;
async_doorbell <= bi;
step;
n_exh := n_exh + 1;
idle_in;
end loop;
end loop;
end loop;
end loop;
end loop;
end loop;
end loop;
end loop;
end loop;
end loop;
report " exhaustive walker sweep: " & integer'image(n_exh)
& " of 2048 transitions verified" severity note;
-- ===== B. directed: a lap round the ring =====
hard_reset; async_enable <= '1'; step; idle_in;
check(walking = '1', "enabling the schedule starts the walk");
-- 1. A QH link with T SET: terminate, nothing dereferenced.
word_valid <= '1'; link_word <= x"12345673";
wait for 1 ns;
check(terminate = '1', "bit 0 set means TERMINATE");
check(follow = '0', "so nothing is dereferenced");
check(typ_valid = '0', "and the type field means nothing");
step; idle_in;
-- 2. The same word with T clear.
word_valid <= '1'; link_word <= x"12345672";
wait for 1 ns;
check(terminate = '0', "bit 0 clear means there IS a next node");
check(typ_valid = '1' and typ = typ_code(TYP_QH),
"and it is a Queue Head");
check(follow = '1', "so it is followed");
check(next_addr = x"12345660",
"with the low five bits masked off -- 32-byte aligned");
step; idle_in;
check(n_steps = std_logic_vector(to_unsigned(1, 32)), "one step taken");
-- 3. An isochronous descriptor in the ASYNC list: not followed.
word_valid <= '1'; link_word <= x"12345670";
wait for 1 ns;
check(typ_valid = '1' and typ = typ_code(TYP_ITD), "an iTD was decoded");
check(bad_type = '1',
"which does not belong in the asynchronous list");
check(follow = '0', "so it is NOT followed");
step; idle_in;
check(n_bad_type = std_logic_vector(to_unsigned(1, 32)),
"and the software error was counted");
-- 4. Reserved bits 4:3 are masked, not assumed zero.
word_valid <= '1'; link_word <= x"ABCDEF1A";
wait for 1 ns;
check(follow = '1', "a QH with reserved bits set is still followed");
check(next_addr = x"ABCDEF00",
"and the reserved bits are masked out of the address");
step; idle_in;
-- ===== C. directed: the H bit and the reclamation flag =====
hard_reset; async_enable <= '1'; step; idle_in;
-- 5. Work at an ordinary node sets Reclamation.
word_valid <= '1'; link_word <= x"00000002"; node_did_work <= '1';
step; idle_in;
wait for 1 ns;
check(reclamation = '1', "doing work sets the Reclamation flag");
-- 6. Arriving at the head with Reclamation set clears it and carries on.
word_valid <= '1'; link_word <= x"00000002"; node_is_head <= '1';
wait for 1 ns;
check(async_idle = '0',
"the head with Reclamation set does NOT stop the walker");
step; idle_in;
wait for 1 ns;
check(reclamation = '0', "but it does clear the flag");
check(walking = '1', "and the walk continues");
check(n_laps = std_logic_vector(to_unsigned(1, 32)), "one lap completed");
-- 7. THE case. Arriving at the head again with nothing done since is a
-- whole lap with no work: the list is empty and the walker stops.
word_valid <= '1'; link_word <= x"00000002"; node_is_head <= '1';
wait for 1 ns;
check(async_idle = '1',
"a second head visit with no work means the list is EMPTY");
step; idle_in;
wait for 1 ns;
check(stopped = '1', "so the walker stops");
check(walking = '0', "and stops walking");
check(n_idles = std_logic_vector(to_unsigned(1, 32)),
"one empty-list detection");
-- 8. It stays stopped.
steps_before := to_integer(unsigned(n_steps));
word_valid <= '1'; link_word <= x"00000002"; step; idle_in;
wait for 1 ns;
check(walking = '0', "a stopped walker stays stopped");
check(to_integer(unsigned(n_steps)) = steps_before,
"and takes no FURTHER steps -- the counter did not move");
-- 9. The doorbell is how software says "I added work, look again".
async_doorbell <= '1'; step; idle_in;
wait for 1 ns;
check(stopped = '0', "the doorbell clears the stop");
check(walking = '1', "and the walk restarts");
-- 10. Work AT the head node leaves Reclamation set, even though
-- arriving at the head clears it. Order matters.
hard_reset; async_enable <= '1'; step; idle_in;
word_valid <= '1'; link_word <= x"00000002";
node_is_head <= '1'; node_did_work <= '1';
wait for 1 ns;
check(async_idle = '0',
"a head visit that did work does not stop the walker");
step; idle_in;
wait for 1 ns;
check(reclamation = '1',
"and leaves Reclamation SET -- work outranks the head's clear");
-- 11. Disabling the schedule clears everything.
async_enable <= '0'; step; idle_in;
wait for 1 ns;
check(walking = '0', "disabling the schedule stops the walk");
check(reclamation = '0', "and clears Reclamation");
check(stopped = '0', "and the stop latch");
-- ===== D. randomised =====
-- ieee.math_real.uniform is a genuinely different generator from either
-- Verilog builtin, which is what makes this column independent evidence.
hard_reset; async_enable <= '1';
for i in 0 to 39999 loop
rnd(iv, 32); if iv /= 0 then async_enable <= '1';
else async_enable <= '0'; end if;
rnd(iv, 4); if iv /= 0 then word_valid <= '1';
else word_valid <= '0'; end if;
for b in 0 to 31 loop
rnd(iv, 2);
if iv = 1 then lw(b) := '1'; else lw(b) := '0'; end if;
end loop;
-- bias hard toward Queue Heads, which is what an async list contains
rnd(iv, 4); if iv /= 0 then lw(2 downto 1) := typ_code(TYP_QH); end if;
rnd(iv, 6); if iv /= 0 then lw(0) := '0'; end if;
link_word <= lw;
rnd(iv, 8); if iv = 0 then node_is_head <= '1';
else node_is_head <= '0'; end if;
rnd(iv, 3); if iv = 0 then node_did_work <= '1';
else node_did_work <= '0'; end if;
rnd(iv, 64); if iv = 0 then async_doorbell <= '1';
else async_doorbell <= '0'; end if;
step;
end loop;
for i in 0 to 3 loop
check(n_typ(i) > 500, "every link type was decoded many times");
end loop;
check(n_follow > 5000, "links were followed many times");
check(n_term > 2000, "terminated links were seen many times");
check(n_badt > 1000, "non-QH nodes in the async list were seen often");
check(n_lap > 1000, "the head node was reached often");
check(n_idle > 200, "the empty-list condition fired often");
report " REACH: transitions=" & integer'image(n_exh)
& " | types decoded: itd=" & integer'image(n_typ(0))
& " qh=" & integer'image(n_typ(1))
& " sitd=" & integer'image(n_typ(2))
& " fstn=" & integer'image(n_typ(3)) severity note;
report " CASES: followed=" & integer'image(n_follow)
& " terminated=" & integer'image(n_term)
& " bad-type=" & integer'image(n_badt)
& " laps=" & integer'image(n_lap)
& " empty-list=" & integer'image(n_idle) severity note;
report " COUNTERS: steps="
& integer'image(to_integer(unsigned(n_steps)))
& " laps=" & integer'image(to_integer(unsigned(n_laps)))
& " idles=" & integer'image(to_integer(unsigned(n_idles)))
& " bad-type=" & integer'image(to_integer(unsigned(n_bad_type)))
& " work=" & integer'image(to_integer(unsigned(n_work)))
severity note;
report " [VHDL] ehci_async_walker: " & integer'image(errors) & " errors"
severity note;
if errors = 0 then
report " [VHDL] PASS" severity note;
else
report " [VHDL] FAIL" severity failure;
end if;
running <= false;
wait;
end process;
end architecture;12. Exhaustive Verification
| Measure | Verilog | SystemVerilog | VHDL |
|---|---|---|---|
| Exhaustive transitions | 2048 / 2048 | 2048 / 2048 | 2048 / 2048 |
| iTD decoded | 1794 | 1884 | 1841 |
| QH decoded | 25049 | 25116 | 25069 |
| siTD decoded | 1858 | 1860 | 1891 |
| FSTN decoded | 1800 | 1842 | 1827 |
| links followed | 18290 | 18247 | 18760 |
| terminated links | 3056 | 3023 | 2992 |
| wrong-list nodes | 5452 | 5586 | 5559 |
| laps completed | 4337 | 4295 | 4274 |
| empty-list detections | 1564 | 1534 | 1541 |
| Result | PASS | PASS | PASS |
All four link types are decoded thousands of times and the testbenches assert it. The empty-list detection row is the one that makes §4's claim evidence: the termination rule fired about 1550 times, which required the randomiser to produce the specific sequence head → no work → head repeatedly rather than by luck.
13. Mutation Testing
| # | Mutation | Verilog | SysVer | VHDL |
|---|---|---|---|---|
| K1 | a terminated link is followed anyway | 44338 | 44331 | 44368 |
| K2 | the type is decoded even with T set | 47724 | 47856 | 47690 |
| K3 | the address is not masked | 87892 | 87848 | 87766 |
| K4 | any node type is followed in the async list | 93027 | 93349 | 93202 |
| K5 | the termination test is inverted | 282988 | 281159 | 281086 |
| K6 | the idle test ignores work at the head node | 214148 | 214831 | 218468 |
| K7 | a lap clears Reclamation even when work was done | 215312 | 213197 | 215246 |
| — | unmutated baseline | 0 | 0 | 0 |
All seven die in all three languages, all counts distinct, columns within 2%.
K1 and K2 are the two halves of "check T first". K1 dereferences a terminated link — a DMA read from whatever software left in that word. K2 merely reports a type for it, which sounds harmless and is not: a downstream stage that trusts typ_valid now has a node type for a node that does not exist. They score almost identically (44 338 and 47 724), which says the suite treats "acted on untrusted bits" and "described untrusted bits" as equally serious — and it should, because the second is how the first gets written.
K3 at ~87 800 is the unmasked address. Note it is twice K1: an unmasked address is wrong on every followed link, not just terminated ones.
K5, K6 and K7 are the three ways to get the lap rule wrong, and they are the three largest at 281 000–283 000 and ~215 000. That is the right shape: the lap rule is the only thing that ever stops this walker, so breaking it breaks every subsequent cycle. K5 inverts the test — the walker stops on a busy list and spins for ever on an empty one, which is the worst of both. K6 drops the !node_did_work term, so work at the head node no longer prevents the stop. K7 inverts the priority so a lap clears Reclamation even when work was done at that very node.
14. Debugging Walkthrough: The Controller That Stops Under Light Load
The report. A USB host controller works perfectly under heavy traffic. Under light traffic — one idle keyboard, nothing else — transfers occasionally stall for hundreds of milliseconds and then resume. The heavier the load, the less often it happens.
Step 1 — what does "resumes" mean? Something eventually kicks it. Correlate: the stalls end when any other endpoint gets work. So the controller is not broken; it has stopped looking, and the next doorbell restarts it.
Step 2 — is stopping wrong? No. Stopping on an empty lap is correct and desirable; it is how the controller stops burning memory bandwidth. The question is why it stops when there is work.
Step 3 — when does it stop? Trace async_idle against node_is_head and node_did_work. The stop fires on head visits where work was done at the head node itself.
Step 4 — why that is wrong. The head Queue Head is a real endpoint like any other; the H bit marks its position in the ring, not its function. Work at the head is work, and it must set Reclamation. The controller was clearing Reclamation on arrival at the head after the work had set it.
Step 5 — why heavy load hides it. With several active endpoints, the head is rarely the only node with work, so Reclamation is nearly always set by someone else before the head is reached. The bug needs the head node to be the only busy one — which is exactly the single-idle-keyboard case.
Step 6 — the cause. The two updates were written as consecutive assignments in a clocked block, and the head-clears line came second. Mutation K7, in production.
15. UVM: Walking a Ring You Also Edit
15.1 The transaction
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
class ehci_node_item extends uvm_sequence_item;
`uvm_object_utils(ehci_node_item)
// ONE NODE VISIT: the word fetched, plus what the node turned out to be.
rand bit word_valid;
rand bit terminate;
rand link_typ_e typ;
rand bit [26:0] addr_hi; // bits 31:5 of the link pointer
rand bit [1:0] reserved; // bits 4:3 -- software may leave anything
rand bit node_is_head;
rand bit node_did_work;
rand bit async_doorbell;
rand bit async_enable;
// An asynchronous list contains queue heads. The wrong-list case is a
// software bug and gets its own sequence rather than flooding here.
constraint c_mostly_qh { typ dist { TYP_QH := 90, TYP_ITD := 4,
TYP_SITD := 3, TYP_FSTN := 3 }; }
// The ring is circular: a terminated link in the ASYNC list is itself
// unusual, and worth generating deliberately rather than constantly.
constraint c_rarely_terminated { terminate dist {0 := 85, 1 := 15}; }
// Exactly one node in the ring carries the H bit, so head visits are a
// small fraction of node visits -- and the reserved bits are NOT biased
// toward zero, because "the design masks them" is the claim under test.
constraint c_ring_shape {
node_is_head dist {0 := 7, 1 := 1};
node_did_work dist {0 := 2, 1 := 1};
async_doorbell dist {0 := 63, 1 := 1};
async_enable dist {1 := 31, 0 := 1};
}
function bit [31:0] to_link_word();
return {addr_hi, reserved, typ, terminate};
endfunction
function new(string name = "ehci_node_item"); super.new(name); endfunction
function string convert2string();
return $sformatf("word=%08h T=%0b typ=%s head=%0b work=%0b",
to_link_word(), terminate, typ.name(), node_is_head,
node_did_work);
endfunction
endclass15.2 Sequences
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
// THE sequence for this chapter: a complete lap round the ring with NO work
// anywhere, which is the only thing that stops the walker. Random traffic
// produces it eventually; this produces it on demand, which is what makes
// the termination rule testable rather than merely reachable.
class empty_lap_seq extends uvm_sequence #(ehci_node_item);
`uvm_object_utils(empty_lap_seq)
function new(string name = "empty_lap_seq"); super.new(name); endfunction
rand int unsigned ring_size;
constraint c_ring { ring_size inside {[2:8]}; }
task body();
repeat (200) begin
ehci_node_item it;
int unsigned n = $urandom_range(2, 8);
// one lap: the head, then n-1 ordinary nodes, none of them busy
for (int i = 0; i < n; i++) begin
it = ehci_node_item::type_id::create("it");
start_item(it);
it.c_mostly_qh.constraint_mode(0);
it.c_rarely_terminated.constraint_mode(0);
it.c_ring_shape.constraint_mode(0);
if (!it.randomize() with { async_enable == 1;
word_valid == 1;
terminate == 0;
typ == TYP_QH;
node_is_head == (i == 0);
node_did_work == 0;
async_doorbell == 0; })
`uvm_error("RAND", "empty-lap randomize failed")
finish_item(it);
end
end
endtask
endclass
// THE other one: a lap in which the ONLY busy node is the head itself. This
// is the population that separates "work sets Reclamation" from "arriving at
// the head clears it", and it is the single-idle-keyboard case from the
// debugging walkthrough. Ordinary random traffic visits it rarely, because
// it needs the head to be busy and every other node not to be.
class busy_head_only_seq extends uvm_sequence #(ehci_node_item);
`uvm_object_utils(busy_head_only_seq)
function new(string name = "busy_head_only_seq"); super.new(name); endfunction
task body();
repeat (300) begin
ehci_node_item it;
int unsigned n = $urandom_range(2, 6);
for (int i = 0; i < n; i++) begin
it = ehci_node_item::type_id::create("it");
start_item(it);
it.c_mostly_qh.constraint_mode(0);
it.c_rarely_terminated.constraint_mode(0);
it.c_ring_shape.constraint_mode(0);
if (!it.randomize() with { async_enable == 1;
word_valid == 1;
terminate == 0;
typ == TYP_QH;
node_is_head == (i == 0);
node_did_work == (i == 0); // ONLY the head
async_doorbell == 0; })
`uvm_error("RAND", "busy-head randomize failed")
finish_item(it);
end
end
endtask
endclass
// Software errors: descriptors from the PERIODIC schedule appearing in the
// asynchronous list, and terminated links whose remaining bits are garbage.
// The property under test is that neither is dereferenced.
class malformed_list_seq extends uvm_sequence #(ehci_node_item);
`uvm_object_utils(malformed_list_seq)
function new(string name = "malformed_list_seq"); super.new(name); endfunction
task body();
repeat (500) begin
ehci_node_item it = ehci_node_item::type_id::create("it");
start_item(it);
it.c_mostly_qh.constraint_mode(0);
it.c_rarely_terminated.constraint_mode(0);
if (!it.randomize() with { async_enable == 1; word_valid == 1;
(terminate == 1)
|| (typ != TYP_QH); })
`uvm_error("RAND", "malformed randomize failed")
finish_item(it);
end
endtask
endclass15.3 The scoreboard
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
class ehci_walker_scoreboard extends uvm_scoreboard;
`uvm_component_utils(ehci_walker_scoreboard)
uvm_analysis_imp #(ehci_walker_mon_item, ehci_walker_scoreboard) ap;
// The scoreboard keeps its OWN Reclamation flag and stop latch.
bit sb_reclaim, sb_stopped;
int unsigned n_followed, n_refused_terminate, n_refused_type;
int unsigned n_stops, n_laps, n_work_at_head;
function new(string name, uvm_component parent);
super.new(name, parent);
ap = new("ap", this);
endfunction
function void write(ehci_walker_mon_item t);
bit walking = t.async_enable && !sb_stopped;
bit visiting = walking && t.word_valid;
bit lap = visiting && t.node_is_head;
bit idle = lap && !sb_reclaim && !t.node_did_work;
// ---- THE property. A terminated link is never dereferenced, and
// ---- never even described.
if (t.word_valid && t.terminate) begin
if (t.follow)
`uvm_error("TERMINATED",
"a terminated link was followed -- that 32-bit word is whatever software left there, not an address")
if (t.typ_valid)
`uvm_error("TERMINATED",
"a terminated link reported a node type -- there is no next node to have a type")
n_refused_terminate++;
end
// ---- The address is always 32-byte aligned: the low five bits carry
// ---- other fields and must be masked.
if (t.next_addr[4:0] != 5'd0)
`uvm_error("ALIGNMENT",
$sformatf("next_addr=%08h is not 32-byte aligned -- the T and Typ fields leaked into a DMA address",
t.next_addr))
// ---- Only a Queue Head may be followed in the ASYNC list ----
if (t.follow && (t.typ != TYP_QH))
`uvm_error("WRONG_LIST",
$sformatf("a %s was followed in the asynchronous list -- an isochronous descriptor is about to be read as a queue head",
t.typ.name()))
if (t.word_valid && !t.terminate && (t.typ != TYP_QH)) n_refused_type++;
if (t.follow) n_followed++;
// ---- THE termination rule ----
if (idle != t.async_idle)
`uvm_error("LAP",
$sformatf("async_idle=%0b, expected %0b (head=%0b reclaim=%0b work=%0b)",
t.async_idle, idle, t.node_is_head, sb_reclaim,
t.node_did_work))
if (lap) n_laps++;
if (lap && t.node_did_work) begin
// The single-idle-keyboard case: work AT the head must not be erased
// by the head's own clear.
if (t.async_idle)
`uvm_error("LAP",
"the walker stopped on a lap in which the head node itself did work")
n_work_at_head++;
end
if (idle) n_stops++;
// ---- Advance the scoreboard's own flags, by the spec's rules ----
if (!t.async_enable) sb_reclaim = 0;
else if (t.node_did_work && visiting) sb_reclaim = 1; // work outranks
else if (lap) sb_reclaim = 0;
if (!t.async_enable) sb_stopped = 0;
else if (t.async_doorbell) sb_stopped = 0;
else if (idle) sb_stopped = 1;
if (t.reclamation !== sb_reclaim)
`uvm_error("RECLAIM",
$sformatf("reclamation=%0b, scoreboard=%0b", t.reclamation, sb_reclaim))
if (t.stopped !== sb_stopped)
`uvm_error("STOPPED",
$sformatf("stopped=%0b, scoreboard=%0b", t.stopped, sb_stopped))
endfunction
function void report_phase(uvm_phase phase);
`uvm_info("SB", $sformatf(
"followed=%0d refused(T)=%0d refused(type)=%0d laps=%0d stops=%0d work-at-head=%0d",
n_followed, n_refused_terminate, n_refused_type, n_laps, n_stops,
n_work_at_head), UVM_LOW)
if (n_stops == 0) `uvm_error("COVERAGE",
"the walker never stopped -- the termination rule this block exists for is untested")
if (n_work_at_head == 0) `uvm_error("COVERAGE",
"work was never done AT the head node -- the priority between 'work sets' and 'the lap clears' is untested")
if (n_refused_terminate == 0) `uvm_error("COVERAGE",
"no terminated link was ever presented")
if (n_refused_type == 0) `uvm_error("COVERAGE",
"no wrong-list node was ever presented")
endfunction
endclassThe n_work_at_head guard is the one worth stealing. A regression in which the head node is never the busy one passes identically against a design that clears Reclamation on arrival — which is the bug from §14. Counting that specific population turns "we tested the lap rule" into a measurement.
15.4 Functional coverage
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
covergroup ehci_walker_cg with function sample(
bit valid, bit t_bit, link_typ_e typ, bit [1:0] rsvd, bit head,
bit work, bit reclaim, bit stopped, bit follow, bit idle);
cp_typ : coverpoint typ { bins all[] = {TYP_ITD, TYP_QH, TYP_SITD, TYP_FSTN}; }
cp_t : coverpoint t_bit { bins next_node = {0}; bins terminate = {1}; }
// THE cross. Every node type under BOTH terminate states -- because the
// rule is that a terminated link's type is not decoded AT ALL, and proving
// that needs terminated links carrying every type in turn.
x_typ_t : cross cp_typ, cp_t;
// The reserved bits are NOT biased toward zero. A design that assumes them
// zero passes every test in which they are.
cp_rsvd : coverpoint rsvd { bins patterns[] = {2'b00, 2'b01, 2'b10, 2'b11}; }
x_rsvd_follow : cross cp_rsvd, cp_t;
// THE lap cross. Four bins, and only one of them stops the walker:
// (head, no work, reclaim clear). The other three are the cases that must
// NOT stop it, and each corresponds to a different mutation.
cp_head : coverpoint head { bins head = {1}; bins ordinary = {0}; }
cp_work : coverpoint work { bins busy = {1}; bins idle_node = {0}; }
cp_reclaim : coverpoint reclaim { bins set = {1}; bins clear = {0}; }
x_lap_rule : cross cp_head, cp_work, cp_reclaim;
// The stop latch in both states, and the doorbell that clears it.
cp_stopped : coverpoint stopped { bins running = {0}; bins stopped = {1}; }
x_stop_valid : cross cp_stopped, cp_t;
endgroupx_lap_rule is an eight-bin cross over the three inputs to the termination rule, and the bins map one-to-one onto the mutations:
| head | work | reclaim | stops? | mutation that gets this wrong |
|---|---|---|---|---|
| yes | no | clear | yes | — the correct stop |
| yes | no | set | no | K5 (inverted test) |
| yes | yes | clear | no | K6, K7 |
| no | any | any | no | — |
A regression that closes six of the eight bins has, by construction, left at least one of K5/K6/K7 untested.
16. SystemVerilog Assertions
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
module ehci_async_walker_sva
import ehci_walker_pkg::*;
(
input logic clk,
input logic rst_n,
input logic async_enable,
input logic word_valid,
input logic [31:0] link_word,
input logic node_is_head,
input logic node_did_work,
input logic async_doorbell,
input logic terminate,
input link_typ_e typ,
input logic typ_valid,
input logic [31:0] next_addr,
input logic follow,
input logic bad_type,
input logic walking,
input logic async_idle,
input logic stopped,
input logic reclamation
);
default clocking cb @(posedge clk); endclocking
default disable iff (!rst_n);
// ---- 1. THE property. A terminated link is never dereferenced. ----
property p_terminated_never_followed;
(word_valid && link_word[LINK_T_BIT]) |-> !follow;
endproperty
a_terminated_never_followed :
assert property (p_terminated_never_followed)
else $error("a terminated link was followed -- that word is not an address");
// ---- 2. ...and never even described. ----
property p_terminated_has_no_type;
(word_valid && link_word[LINK_T_BIT]) |-> !typ_valid;
endproperty
a_terminated_has_no_type : assert property (p_terminated_has_no_type);
// ---- 3. The address is always 32-byte aligned. ----
property p_address_aligned;
next_addr[LINK_ADDR_LSB-1:0] == '0;
endproperty
a_address_aligned : assert property (p_address_aligned)
else $error("next_addr=%08h -- the T and Typ fields leaked into a DMA address",
next_addr);
// ---- 4. Only a Queue Head is followed in the asynchronous list. ----
property p_only_qh_followed;
follow |-> (typ == TYP_QH);
endproperty
a_only_qh_followed : assert property (p_only_qh_followed)
else $error("a %s was followed in the asynchronous list", typ.name());
// ---- 5. Nothing happens with the schedule disabled. ----
property p_disabled_is_quiet;
!async_enable |-> (!walking && !follow && !async_idle);
endproperty
a_disabled_is_quiet : assert property (p_disabled_is_quiet);
// ---- 6. THE termination rule, stated exactly. ----
property p_idle_iff_empty_lap;
async_idle == (walking && word_valid && node_is_head
&& !reclamation && !node_did_work);
endproperty
a_idle_iff_empty_lap : assert property (p_idle_iff_empty_lap)
else $error("the empty-list condition fired on the wrong cycle");
// ---- 7. Work at ANY node, including the head, sets Reclamation. ----
property p_work_sets_reclamation;
(walking && word_valid && node_did_work && async_enable)
|=> reclamation;
endproperty
a_work_sets_reclamation : assert property (p_work_sets_reclamation)
else $error("work was done and Reclamation did not set -- if this was the head node, the walker will stop on a busy list");
// ---- 8. A lap with no work clears it. ----
property p_clean_lap_clears_reclamation;
(walking && word_valid && node_is_head && !node_did_work
&& async_enable) |=> !reclamation;
endproperty
a_clean_lap_clears_reclamation :
assert property (p_clean_lap_clears_reclamation);
// ---- 9. A stopped walker does not walk, and only the doorbell or
// ---- disabling the schedule releases it.
property p_stopped_does_not_walk;
stopped |-> !walking;
endproperty
a_stopped_does_not_walk : assert property (p_stopped_does_not_walk);
property p_stop_is_sticky;
(stopped && async_enable && !async_doorbell) |=> stopped;
endproperty
a_stop_is_sticky : assert property (p_stop_is_sticky)
else $error("the walker restarted with nothing having told it to -- it will oscillate");
// ---- 10. The doorbell always releases it. ----
property p_doorbell_releases;
(async_enable && async_doorbell) |=> !stopped;
endproperty
a_doorbell_releases : assert property (p_doorbell_releases);
// ---- Cover: the interesting populations were reached. ----
c_stop : cover property ((async_idle));
c_work_at_head : cover property ((walking && word_valid && node_is_head
&& node_did_work));
c_terminated : cover property ((word_valid && link_word[LINK_T_BIT]));
c_wrong_list : cover property ((bad_type));
c_rsvd_set : cover property ((follow && (link_word[4:3] != 2'b00)));
endmodule
bind ehci_async_walker ehci_async_walker_sva u_sva (.*);17. Common Misconceptions
"The host controller is told what transfers to do." It is handed a pointer to a data structure and walks it. Nothing is ever "submitted" to EHCI.
"A link pointer is an address." It is a packed word: an address in bits 31:5, reserved bits in 4:3, a type in 2:1 and a terminate flag in bit 0. The address is what is left after the others are masked off.
"The T bit means the pointer is null." It means the whole word is meaningless. Software is free to leave anything in the other 31 bits, including something that looks like a valid address.
"The reserved bits will be zero." They are reserved, which means software need not write them and hardware must not read them. Masking is mandatory.
"The list ends somewhere." The asynchronous list is a ring. Its circularity is what lets software edit it safely while the controller walks it.
"The controller stops when the list is empty." It stops when it has completed a lap with no work. Those are different statements, and only the second is checkable from local state.
"Work at the head node is special." The H bit marks a position, not a function. The head is an ordinary endpoint that also happens to be where laps are counted.
"A node of the wrong type is harmless — it just will not have any work." Following it reads an isochronous descriptor as a queue head, which means reading one structure's length field as another's pointer.
18. Exercises
1. Remove the !link_word[0] term from follow and predict which of the seven safety properties fires first. Then explain why the count (44 338) is roughly half of K3's, given that both are address-formation bugs.
2. K6 and K7 differ by 0.5% and are not duplicates. Construct a stimulus in which they score differently, and explain what that stimulus has to contain.
3. The design masks bits 4:0. Change the mask to bits 3:0 — an off-by-one in the alignment rather than no mask at all — and measure. Is the count closer to K3's or to zero, and what does that tell you about how the sweep covers address bits?
4. Add the periodic schedule, in which iTD, siTD and FSTN are all legal and QH is legal too. What does bad_type become, and which of the ten SVA properties need a schedule-selector input?
5. Property 10 is trivially true. Find the other trivially-true property in the list, and argue for keeping or removing each.
6. Software unlinks a Queue Head by pointing its predecessor past it. Write the sequence of link words the walker sees if it fetches the predecessor during that edit, and show that both possible outcomes are valid rings. Then find the case that is not safe, and look up what the Interrupt on Async Advance doorbell is actually for.
19. Summary
| Idea | Why it matters |
|---|---|
| EHCI has no command queue | it walks a structure software edits underneath it |
| A link pointer is a packed word | address 31:5, reserved 4:3, Typ 2:1, T in bit 0 |
| Check T first | with T set the rest of the word is meaningless |
| Mask bits 4:0 | nodes are 32-byte aligned; that is why the bits are free |
| The async list is a ring | so software can edit it safely mid-walk |
| ...so "the end" does not exist | termination cannot mean "the list ran out" |
| The H bit plus Reclamation | stop after a lap that produced no work |
| Work at any node sets Reclamation | including the head — that priority is the bug in §14 |
| Only QH belongs in the async list | an iTD here would be read as a queue head |
stopped is latched; walking is not | or the walker oscillates |
| The doorbell is how software restarts it | the controller is no longer looking |
| 2048-transition exhaustive verification | the whole decode × the whole of the state |
| 7 mutations, all killed in 3 languages | including three different ways to break the lap rule |
Tooling
| Step | Command |
|---|---|
| Verilog-2005 | iverilog -g2005 -o aw_v.out aw_v.v aw_v_tb.v && ./aw_v.out |
| SystemVerilog | iverilog -g2012 -o aw_sv.out aw_sv.sv aw_sv_tb.sv && ./aw_sv.out |
| VHDL-2008 analyse | nvc --std=2008 -a aw_vhdl.vhd aw_vhdl_tb.vhd |
| VHDL-2008 elaborate | nvc --std=2008 -e tb_aw_vhdl |
| VHDL-2008 run | nvc --std=2008 -r tb_aw_vhdl |
| One mutation | iverilog -g2005 -DMUT_K1 -o mm aw_v_mut.v aw_v_tb.v && ./mm |
All three implementations pass with 0 errors: 2048 of 2048 exhaustive transitions, 40 000 randomised cycles, every link type decoded and asserted decoded.
Chapter 22.2 — xHCI Overview is what replaced all of this. xHCI throws away linked lists and uses rings — and solves the producer/consumer ownership problem with a single bit per entry, the Cycle Bit, so that neither side ever has to tell the other where it has got to. The rule is one line long, the hardware is a handful of flops, and getting the toggle wrong desynchronises a ring permanently.
Continue learning
Related tutorials
- Related topic
xHCI Overview
xHCI shares a ring between software and hardware using one Cycle bit per TRB and no pointer exchange at all — and an unowned entry holds the previous lap's complete, plausible descriptor.
- Related topic
Host-Side Scheduling
A USB transaction cannot be stopped once its token goes out, so the scheduler must ask whether it will finish before it starts — and the periodic reserve exists to protect bulk traffic, not to limit isochronous.
- Related topic
Host Resource Management
Software cannot edit a context hardware owns, so xHCI has two of them — and inside a Configure Endpoint command the Drop flags are applied before the Add flags, making drop+add an atomic re-initialisation.
- Related topic
DMA Integration
A descriptor has a byte count and the wire has packets, and the rule that converts one to the other is not ceil(length / packet size) — the version that is hangs on exactly the buffer sizes everybody uses.
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.