Cascading Hubs

  MAX_TOPO_LEVEL = 6

  if (hdev->level == MAX_TOPO_LEVEL)
          → "Unsupported bus topology: hub nested too deep"

   hub:       child_level  <   MAX_LEVEL      (must leave room below)
   function:  child_level  <=  MAX_LEVEL      (only has to fit)

// usb_topology_guard -- the rule that stops a USB tree getting too deep.
//
// The constraint is usually quoted as "seven tiers", as though it were an
// architectural choice. It is not. It is a TIMING constraint that has been
// quantised into a topology rule, and this module computes both forms so
// that the relationship between them is visible.
//
// Every hub inserted between the host and a device adds delay in BOTH
// directions: the cable to it, its own repeater turnaround (chapter 18.1),
// and the cable onward. The host, having sent a token, waits a bounded time
// for the response before declaring the transaction lost -- and that bound
// is fixed by the protocol, not by the topology. So the tree may only be as
// deep as the round trip allows.
//
// The depth rule is the timing rule rounded down to something a host can
// check with an integer compare at enumeration time, which is the only
// moment it actually can check it.
//
// One asymmetry matters and is the most commonly missed part of the rule:
// THE LIMIT IS ON HUBS, NOT ON DEVICES. The last tier is reserved for
// functions. A hub at the maximum level is refused; a mouse at that same
// level is perfectly legal, because it terminates the chain instead of
// extending it.
module usb_topology_guard #(
  parameter integer MAX_LEVEL    = 6,   // Linux calls this MAX_TOPO_LEVEL
  parameter [16:0]  HUB_DELAY    = 17'd11, // repeater turnaround, delay units
  parameter [16:0]  CABLE_DELAY  = 17'd5,  // one cable, delay units
  parameter integer MAX_ROUNDTRIP = 90  // what the host will wait out
) (
  input  wire        clk,
  input  wire        rst_n,

  input  wire        attach_valid,
  input  wire [3:0]  parent_level,      // 0 = the root hub
  input  wire [15:0] parent_delay,      // accumulated one-way delay to parent
  input  wire        is_hub,            // the attaching device is itself a hub

  output wire [3:0]  child_level,
  output wire [15:0] child_delay,
  output wire [15:0] round_trip,
  output wire        accept,
  output wire [1:0]  reject_reason,     // 0 none, 1 too deep, 2 too slow

  output reg  [31:0] reject_depth_count,
  output reg  [31:0] reject_timing_count,
  output reg         ever_rejected
);
  localparam [1:0] REJ_NONE = 2'd0, REJ_DEPTH = 2'd1, REJ_TIMING = 2'd2;

  // The child sits one tier below its parent. Saturating, because a level
  // that wrapped would turn "impossibly deep" into "at the root", which is
  // the one answer that must never come out of this block.
  wire [4:0] next_level = {1'b0, parent_level} + 5'd1;
  assign child_level = (next_level > 5'd15) ? 4'd15 : next_level[3:0];

  // One more cable and one more repeater, one way.
  // Widened to 17 bits BEFORE the addition, so the sum cannot wrap in the
  // intermediate -- chapter 17.5's signedness lesson in its width form.
  wire [16:0] per_tier  = CABLE_DELAY[16:0] + HUB_DELAY[16:0];
  wire [16:0] next_delay = {1'b0, parent_delay} + per_tier;
  assign child_delay = (next_delay > 17'hFFFF) ? 16'hFFFF : next_delay[15:0];

  // The host's wait is a ROUND trip: out and back.
  wire [17:0] rt = {1'b0, child_delay} * 18'd2;
  assign round_trip = (rt > 18'hFFFF) ? 16'hFFFF : rt[15:0];

  // THE ASYMMETRY. A hub extends the chain, so it must leave room below it;
  // a function terminates the chain and only has to fit. Linux refuses a hub
  // whose parent is already at MAX_TOPO_LEVEL, which is this comparison.
  wire depth_ok  = is_hub ? (child_level < MAX_LEVEL[3:0])
                          : (child_level <= MAX_LEVEL[3:0]);
  wire timing_ok = (round_trip <= MAX_ROUNDTRIP[15:0]);

  assign accept = attach_valid && depth_ok && timing_ok;

  // Depth is reported FIRST when both fail. The depth rule is the coarse,
  // checkable form of the timing rule, so a host that is told "too deep"
  // gets the actionable message -- "remove a hub" -- rather than a timing
  // number it cannot act on.
  assign reject_reason = !attach_valid ? REJ_NONE
                       : !depth_ok     ? REJ_DEPTH
                       : !timing_ok    ? REJ_TIMING
                                       : REJ_NONE;

  always @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      reject_depth_count  <= 32'd0;
      reject_timing_count <= 32'd0;
      ever_rejected       <= 1'b0;
    end else if (attach_valid && !accept) begin
      ever_rejected <= 1'b1;
      if (reject_reason == REJ_DEPTH)
        reject_depth_count  <= reject_depth_count  + 32'd1;
      else
        reject_timing_count <= reject_timing_count + 32'd1;
    end
  end
endmodule

package usb_topo_pkg;
  // Why an attach was refused. Two DIFFERENT constraints can refuse the same
  // attach, and a host that cannot tell them apart cannot advise the user:
  // "too deep" means remove a hub, "too slow" means shorten the cabling.
  typedef enum logic [1:0] {
    REJ_NONE,
    REJ_DEPTH,    // the tier limit -- the quantised form of the rule
    REJ_TIMING    // the round-trip budget -- the rule itself
  } reject_e;
endpackage

// usb_topology_guard_sv -- the rule that stops a USB tree getting too deep.
//
// The constraint is usually quoted as "seven tiers", as though it were an
// architectural choice. It is not. It is a TIMING constraint that has been
// quantised into a topology rule, and this module computes both forms so
// that the relationship between them is visible.
//
// Every hub inserted between the host and a device adds delay in BOTH
// directions: the cable to it, its own repeater turnaround (chapter 18.1),
// and the cable onward. The host, having sent a token, waits a bounded time
// for the response before declaring the transaction lost -- and that bound
// is fixed by the protocol, not by the topology.
//
// One asymmetry matters and is the most commonly missed part of the rule:
// THE LIMIT IS ON HUBS, NOT ON DEVICES. The last tier is reserved for
// functions. A hub at the maximum level is refused; a mouse at that same
// level is legal, because it terminates the chain instead of extending it.
module usb_topology_guard_sv
  import usb_topo_pkg::*;
#(
  parameter int unsigned MAX_LEVEL     = 6,   // Linux: MAX_TOPO_LEVEL
  parameter int unsigned HUB_DELAY     = 11,
  parameter int unsigned CABLE_DELAY   = 5,
  parameter int unsigned MAX_ROUNDTRIP = 90
) (
  input  logic        clk,
  input  logic        rst_n,

  input  logic        attach_valid,
  input  logic [3:0]  parent_level,
  input  logic [15:0] parent_delay,
  input  logic        is_hub,

  output logic [3:0]  child_level,
  output logic [15:0] child_delay,
  output logic [15:0] round_trip,
  output logic        accept,
  output reject_e     reject_reason,

  output logic [31:0] reject_depth_count,
  output logic [31:0] reject_timing_count,
  output logic        ever_rejected
);
  initial begin
    if (MAX_LEVEL < 1)
      $fatal(1, "MAX_LEVEL=%0d: a tree with no tiers holds nothing",
             MAX_LEVEL);
    // The shallowest possible attach must still fit, or nothing can ever be
    // enumerated and the two constraints contradict each other.
    if (2*(CABLE_DELAY + HUB_DELAY) > MAX_ROUNDTRIP)
      $fatal(1, "a single tier already costs %0d of a %0d budget",
             2*(CABLE_DELAY + HUB_DELAY), MAX_ROUNDTRIP);
  end

  // The child sits one tier below its parent. Saturating, because a level
  // that wrapped would turn "impossibly deep" into "at the root", which is
  // the one answer that must never come out of this block.
  wire [4:0] next_level = 5'(parent_level) + 5'd1;
  assign child_level = (next_level > 5'd15) ? 4'd15 : next_level[3:0];

  // One more cable and one more repeater, one way. Widened before the add.
  wire [16:0] next_delay = 17'(parent_delay) + 17'(CABLE_DELAY)
                                             + 17'(HUB_DELAY);
  assign child_delay = (next_delay > 17'hFFFF) ? 16'hFFFF : next_delay[15:0];

  // The host's wait is a ROUND trip: out and back.
  wire [17:0] rt = 18'(child_delay) * 18'd2;
  assign round_trip = (rt > 18'hFFFF) ? 16'hFFFF : rt[15:0];

  // THE ASYMMETRY. A hub extends the chain, so it must leave room below it;
  // a function terminates the chain and only has to fit.
  wire depth_ok  = is_hub ? (child_level <  4'(MAX_LEVEL))
                          : (child_level <= 4'(MAX_LEVEL));
  wire timing_ok = (round_trip <= 16'(MAX_ROUNDTRIP));

  assign accept = attach_valid && depth_ok && timing_ok;

  // Depth is reported FIRST when both fail: it is the actionable message.
  always_comb begin
    if      (!attach_valid) reject_reason = REJ_NONE;
    else if (!depth_ok)     reject_reason = REJ_DEPTH;
    else if (!timing_ok)    reject_reason = REJ_TIMING;
    else                    reject_reason = REJ_NONE;
  end

  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      reject_depth_count <= '0; reject_timing_count <= '0;
      ever_rejected <= 1'b0;
    end else if (attach_valid && !accept) begin
      ever_rejected <= 1'b1;
      if (reject_reason == REJ_DEPTH)
        reject_depth_count  <= reject_depth_count  + 1;
      else
        reject_timing_count <= reject_timing_count + 1;
    end
  end
endmodule

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;

package usb_topo_pkg is
  -- Why an attach was refused. Two DIFFERENT constraints can refuse the same
  -- attach, and a host that cannot tell them apart cannot advise the user:
  -- "too deep" means remove a hub, "too slow" means shorten the cabling.
  type reject_t is (REJ_NONE, REJ_DEPTH, REJ_TIMING);
end package;

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
use work.usb_topo_pkg.all;

-- usb_topology_guard_vhdl -- the rule that stops a USB tree getting too deep.
--
-- The constraint is usually quoted as "seven tiers", as though it were an
-- architectural choice. It is not. It is a TIMING constraint that has been
-- quantised into a topology rule, and this module computes both forms so
-- that the relationship between them is visible.
--
-- Every hub inserted between the host and a device adds delay in BOTH
-- directions: the cable to it, its own repeater turnaround (chapter 18.1),
-- and the cable onward. The host, having sent a token, waits a bounded time
-- for the response before declaring the transaction lost.
--
-- One asymmetry matters and is the most commonly missed part of the rule:
-- THE LIMIT IS ON HUBS, NOT ON DEVICES. The last tier is reserved for
-- functions. A hub at the maximum level is refused; a mouse at that same
-- level is legal, because it terminates the chain instead of extending it.
entity usb_topology_guard_vhdl is
  generic (
    MAX_LEVEL     : positive := 6;      -- Linux: MAX_TOPO_LEVEL
    HUB_DELAY     : natural  := 11;
    CABLE_DELAY   : natural  := 5;
    MAX_ROUNDTRIP : positive := 90
  );
  port (
    clk                 : in  std_logic;
    rst_n               : in  std_logic;

    attach_valid        : in  std_logic;
    parent_level        : in  unsigned(3 downto 0);
    parent_delay        : in  unsigned(15 downto 0);
    is_hub              : in  std_logic;

    child_level         : out unsigned(3 downto 0);
    child_delay         : out unsigned(15 downto 0);
    round_trip          : out unsigned(15 downto 0);
    accept_o            : out std_logic;
    reject_reason       : out reject_t;

    reject_depth_count  : out unsigned(31 downto 0);
    reject_timing_count : out unsigned(31 downto 0);
    ever_rejected       : out std_logic
  );
end entity;

architecture rtl of usb_topology_guard_vhdl is
  signal cl_i    : unsigned(3 downto 0)  := (others => '0');
  signal cd_i    : unsigned(15 downto 0) := (others => '0');
  signal rt_i    : unsigned(15 downto 0) := (others => '0');
  signal acc_i   : std_logic := '0';
  signal rej_i   : reject_t  := REJ_NONE;
  signal depth_ok, timing_ok : boolean := false;

  signal rd_r, rt_r : unsigned(31 downto 0) := (others => '0');
  signal ever_r     : std_logic := '0';
begin
  assert MAX_LEVEL >= 1
    report "a tree with no tiers holds nothing" severity failure;
  -- The shallowest possible attach must still fit, or nothing can ever be
  -- enumerated and the two constraints contradict each other.
  assert 2*(CABLE_DELAY + HUB_DELAY) <= MAX_ROUNDTRIP
    report "a single tier already exceeds the round-trip budget"
    severity failure;

  -- The child sits one tier below its parent. Saturating, because a level
  -- that wrapped would turn "impossibly deep" into "at the root", which is
  -- the one answer that must never come out of this block.
  process (parent_level)
    variable nl : unsigned(4 downto 0);
  begin
    nl := ('0' & parent_level) + 1;
    if nl > 15 then cl_i <= to_unsigned(15, 4);
    else            cl_i <= nl(3 downto 0); end if;
  end process;

  -- One more cable and one more repeater, one way. Widened before the add.
  process (parent_delay)
    variable nd : unsigned(16 downto 0);
  begin
    nd := ('0' & parent_delay)
          + to_unsigned(CABLE_DELAY, 17) + to_unsigned(HUB_DELAY, 17);
    if nd > 65535 then cd_i <= to_unsigned(65535, 16);
    else               cd_i <= nd(15 downto 0); end if;
  end process;

  -- The host's wait is a ROUND trip: out and back.
  process (cd_i)
    -- cd_i & '0' IS cd_i * 2, exactly, in 17 bits. Written as a shift
    -- rather than a multiply because numeric_std's "unsigned * natural"
    -- returns a result as wide as both operands together -- 34 bits here,
    -- which does not fit the variable and is a runtime error, not a
    -- truncation. The concatenation states the intent and the width.
    variable r : unsigned(16 downto 0);
  begin
    r := cd_i & '0';
    if r > 65535 then rt_i <= to_unsigned(65535, 16);
    else              rt_i <= r(15 downto 0); end if;
  end process;

  -- THE ASYMMETRY. A hub extends the chain, so it must leave room below it;
  -- a function terminates the chain and only has to fit.
  depth_ok  <= (cl_i < to_unsigned(MAX_LEVEL, 4)) when is_hub = '1'
               else (cl_i <= to_unsigned(MAX_LEVEL, 4));
  timing_ok <= rt_i <= to_unsigned(MAX_ROUNDTRIP, 16);

  acc_i <= '1' when (attach_valid = '1' and depth_ok and timing_ok) else '0';

  -- Depth is reported FIRST when both fail: it is the actionable message.
  rej_i <= REJ_NONE   when attach_valid = '0' else
           REJ_DEPTH  when not depth_ok       else
           REJ_TIMING when not timing_ok      else
           REJ_NONE;

  child_level         <= cl_i;
  child_delay         <= cd_i;
  round_trip          <= rt_i;
  accept_o            <= acc_i;
  reject_reason       <= rej_i;
  reject_depth_count  <= rd_r;
  reject_timing_count <= rt_r;
  ever_rejected       <= ever_r;

  process (clk, rst_n)
  begin
    if rst_n = '0' then
      rd_r <= (others => '0'); rt_r <= (others => '0'); ever_r <= '0';
    elsif rising_edge(clk) then
      if attach_valid = '1' and acc_i = '0' then
        ever_r <= '1';
        if rej_i = REJ_DEPTH then rd_r <= rd_r + 1;
        else                      rt_r <= rt_r + 1; end if;
      end if;
    end if;
  end process;
end architecture;

    for (H=0; H<2; H=H+1)
     for (L=0; L<16; L=L+1)
      for (D=0; D<256; D=D+1) begin
        probe(L[3:0], D[15:0], H[0]);
        acc_tbl[H][L][D] = accept;
        n_exh = n_exh + 1;
        ...
      end

    // These are statements about the SHAPE of the decision surface. No
    // reference model supplies them, and they are the reason the table
    // above was recorded.
    for (L=0; L<16; L=L+1)
     for (D=0; D<256; D=D+1) begin
       // 1. THE ASYMMETRY: anywhere a hub may attach, a function may too.
       //    The converse is false, and that is the whole point -- the last
       //    tier is reserved for devices that terminate the chain.
       check(!acc_tbl[1][L][D] || acc_tbl[0][L][D],
             "a hub was accepted where a function was not");
       // 2. MONOTONIC IN DEPTH: rejection never un-rejects deeper down.
       if (L > 0)
         check(!acc_tbl[1][L][D] || acc_tbl[1][L-1][D],
               "a hub accepted deeper than one that was rejected");
       // 3. MONOTONIC IN DELAY: more delay never becomes acceptable.
       if (D > 0)
         check(!acc_tbl[1][L][D] || acc_tbl[1][L][D-1],
               "a slower path accepted where a faster one was not");
     end

  exhaustive topology sweep: 8192 of 8192 points verified
  structural properties: asymmetry + two monotonicities held

  REACH: exhaustive=8192 accepted=330 rejected-depth=5376 rejected-timing=2486
  [Verilog] usb_topology_guard: 0 errors — PASS
  [SystemVerilog] usb_topology_guard_sv: 0 errors — PASS
  [VHDL] usb_topology_guard_vhdl: 0 errors — PASS

  wire depth_ok  = is_hub ? (child_level <= MAX_LEVEL[3:0])
                          : (child_level <= MAX_LEVEL[3:0]);

  wire depth_ok  = (child_level < MAX_LEVEL[3:0]);    // function loses a tier

// A topology is a PATH, not a point. Generating one means generating a
// chain and asking the guard about each link in turn, which is what makes
// this worth a sequence rather than a directed loop.
class topology_item extends uvm_sequence_item;
  `uvm_object_utils(topology_item)
  rand bit [3:0]  parent_level;
  rand bit [15:0] parent_delay;
  rand bit        is_hub;

  // Bias toward the boundary. Uniform random over the whole space spends
  // almost all its time deep in "obviously rejected" territory -- section 11
  // measured that: only 330 of 8192 uniform points are accepted at all.
  constraint c_near_boundary {
    parent_level dist { [0:3] := 2, [4:6] := 6, [7:15] := 1 };
    parent_delay dist { [0:29] := 8, [30:60] := 3, [61:511] := 1 };
  }
endclass

// Build a whole tree and walk it, so the ACCUMULATION is exercised rather
// than just the comparison.
class cascade_seq extends uvm_sequence #(topology_item);
  `uvm_object_utils(cascade_seq)
  rand int unsigned depth;
  constraint c_depth { depth inside {[1:9]}; }

  task body();
    topology_item it;
    bit [3:0]  lvl = 0;
    bit [15:0] dly = 0;
    for (int i = 0; i < depth; i++) begin
      it = topology_item::type_id::create($sformatf("link%0d", i));
      start_item(it);
      it.parent_level = lvl;
      it.parent_delay = dly;
      // Only the LAST link is a function; everything above it must be a hub
      // for the chain to exist at all.
      it.is_hub = (i < depth-1);
      finish_item(it);
      // carry the accumulated cost forward -- this is the part a
      // point-at-a-time test never exercises
      lvl = it.child_level;
      dly = it.child_delay;
    end
  endtask
endclass

class topology_scoreboard extends uvm_scoreboard;
  `uvm_component_utils(topology_scoreboard)

  // accept[is_hub][level][delay], accumulated across the whole run.
  local bit seen   [bit[20:0]];
  local bit accept [bit[20:0]];

  function void write(topology_txn t);
    bit [20:0] key = {t.is_hub, t.parent_level, t.parent_delay[15:0]};
    seen[key] = 1; accept[key] = t.accept;

    // THE ASYMMETRY, checked whenever both halves have been observed.
    if (t.is_hub && t.accept) begin
      bit [20:0] fkey = {1'b0, t.parent_level, t.parent_delay[15:0]};
      if (seen.exists(fkey) && !accept[fkey])
        `uvm_error("TOPO/ASYM", $sformatf(
          "a hub was accepted at level %0d where a function was refused",
          t.parent_level))
    end
  endfunction

  // Monotonicity can only be judged once the run is over, because it is a
  // relationship between two DIFFERENT inputs (section 11).
  function void check_phase(uvm_phase phase);
    foreach (accept[k]) begin
      bit [20:0] shallower = k - 21'(1 << 16);   // one tier up
      if (accept[k] && seen.exists(shallower) && !accept[shallower])
        `uvm_error("TOPO/MONO",
          "a deeper attach was accepted where a shallower one was refused")
    end
  endfunction
endclass

covergroup topo_cg with function sample(
    bit [3:0] lvl, bit is_hub, bit acc, reject_e why);
  cp_level : coverpoint lvl { bins shallow = {[0:3]};
                              bins at_limit = {4, 5, 6};   // the boundary
                              bins deep = {[7:15]}; }
  cp_kind  : coverpoint is_hub;
  cp_why   : coverpoint why;
  // The bin that matters: BOTH kinds tested at EVERY boundary level, which
  // is the only way the asymmetry is observable at all.
  x_asym : cross cp_level, cp_kind, cp_why;
endgroup

  // A hub is never accepted where a function would be refused. Section 3.
  // Checked with is_hub as a free variable, which is what makes it a
  // statement about the RULE rather than about one attach.
  property p_hub_implies_function;
    @(posedge clk) disable iff (!rst_n)
      (attach_valid && is_hub && accept)
        |-> (child_level <= MAX_LEVEL);
  endproperty
  a_hub_implies_function : assert property (p_hub_implies_function);

  // The level never wraps: a child is always deeper than its parent unless
  // the counter has saturated. Mutation T4.
  property p_level_monotone;
    @(posedge clk) disable iff (!rst_n)
      (child_level > parent_level) || (child_level == 4'd15);
  endproperty
  a_level_monotone : assert property (p_level_monotone)
    else $error("child_level wrapped: an impossibly deep tree read as shallow");

  // Round trip is exactly twice one-way. Mutation T3.
  property p_round_trip;
    @(posedge clk) disable iff (!rst_n)
      (child_delay < 16'h8000) |-> (round_trip == child_delay * 2);
  endproperty
  a_round_trip : assert property (p_round_trip);

  // Accept and reason never disagree.
  property p_reason_consistent;
    @(posedge clk) disable iff (!rst_n)
      accept |-> (reject_reason == REJ_NONE);
  endproperty
  a_reason_consistent : assert property (p_reason_consistent);