USB Controllers on SoC

   PHASE7 SHARED   : grants=7976 blocks=6589 worst_wait=29
   PHASE7 DEDICATED: grants=8348 blocks=0    worst_wait=0

   block_ep    who asked and could not have one
   holder_ep   who has been sitting on one LONGEST

   Report the second. The first is a victim.

// usb_fifo_pool -- the one architectural difference between USB device
// controllers that actually changes the software you write.
//
// THE REGISTER MAPS ARE DIFFERENT AND IT DOES NOT MATTER
//
// DWC2, MUSB and xHCI have completely different register layouts, different
// naming, different bit positions. Porting between them is a week of
// tedious, mechanical work that a careful engineer gets right.
//
// The thing that is NOT mechanical, and that people get wrong for months,
// is how the controller allocates PACKET BUFFERS to endpoints:
//
//     DEDICATED   every endpoint owns a fixed slice of RAM.
//                 MUSB-style. Deterministic. Wastes memory.
//
//     SHARED      endpoints allocate from a common pool.
//                 DWC2-style. Better utilisation. Introduces
//                 HEAD-OF-LINE BLOCKING.
//
// A SHARED POOL FAILS BY LATENCY, NOT BY ERROR
//
// Nothing is lost. No packet is corrupted, no transfer fails, no error bit
// is set anywhere. Some packets are simply LATE -- and the late ones are
// specifically the ones queued behind an endpoint that is holding a buffer
// and not releasing it.
//
// That is why it is diagnosed so slowly. Every error counter in the device
// reads zero, and the symptom is a latency distribution with a tail.
//
// AND THE FAILURE IS NOT PROPORTIONAL TO LOAD
//
// Below the point where the pool is exhausted, a shared pool behaves
// EXACTLY like a dedicated one -- same latency, same throughput, bit for
// bit. Above it, blocking appears suddenly and the tail grows fast.
//
// There is no gradual degradation to notice in testing, which is the same
// shape as chapter 25.4's retry cliff and has the same consequence: every
// measurement taken below the knee says the design is fine.
//
// THE BLOCKED ENDPOINT IS NOT THE ENDPOINT AT FAULT
//
// This is the part that sends people to the wrong place. When endpoint 2
// cannot get a buffer, the controller reports a problem on endpoint 2. The
// bug is in whatever is holding the buffer -- usually an endpoint whose
// firmware forgot to release one, or whose host stopped polling it.
//
//     Report the HOLDER, not the requester.
//
// So this block names the endpoint that has held a buffer longest, which is
// the one to go and look at.
module usb_fifo_pool #(
  parameter integer N_EP  = 4,   // hardware endpoints
  parameter integer N_BUF = 2    // packet buffers in the SHARED pool
) (
  input  wire       clk,
  input  wire       rst_n,

  input  wire       mode,        // 0 = DEDICATED, 1 = SHARED
  input  wire       req_valid,   // this endpoint wants a buffer
  input  wire [1:0] req_ep,
  input  wire       rel_valid,   // this endpoint is done with its buffer
  input  wire [1:0] rel_ep,
  input  wire       eot,

  output wire            grant,      // a buffer was handed out this cycle
  output wire [1:0]      grant_ep,
  output wire            block_pulse,
  output wire [1:0]      block_ep,   // who could not get one
  output wire [1:0]      holder_ep,  // who has held one LONGEST -- the culprit
  output wire [N_EP-1:0] held,
  output wire [N_EP-1:0] pending,
  output wire [3:0]      free_bufs,
  output wire [3:0]      ram_bufs,   // the architectural cost, in buffers
  output wire [15:0]     worst_wait,
  output wire            err_pulse,
  output wire [1:0]      err_code,

  output reg [31:0] n_req,
  output reg [31:0] n_grant,
  output reg [31:0] n_block,
  output reg [31:0] n_release,
  output reg [31:0] n_double,    // requested while already holding
  output reg [31:0] n_unheld     // released without holding
);

  localparam [1:0] E_NONE   = 2'd0,
                   E_DOUBLE = 2'd1,   // a request from an endpoint that holds
                   E_UNHELD = 2'd2;   // a release from one that does not

  // Widths derived from the parameters' own type, never from the width the
  // DEFAULT value happens to need -- chapter 25.4's retry budget is what
  // that rule came from.
  localparam [3:0] NBUF4 = N_BUF;
  localparam [3:0] NEP4  = N_EP;

  reg [N_EP-1:0] held_r, pend_r;
  reg [15:0]     age_r  [0:N_EP-1];   // cycles this endpoint has HELD
  reg [15:0]     wait_r [0:N_EP-1];   // cycles this endpoint has WAITED
  reg [15:0]     worst_r;
  reg            gr_r, bl_r, er_r;
  reg [1:0]      gep_r, bep_r, hep_r;
  reg [1:0]      ec_r;

  assign grant       = gr_r;
  assign grant_ep    = gep_r;
  assign block_pulse = bl_r;
  assign block_ep    = bep_r;
  assign holder_ep   = hep_r;
  assign held        = held_r;
  assign pending     = pend_r;
  assign worst_wait  = worst_r;
  assign err_pulse   = er_r;
  assign err_code    = ec_r;

  // ---- How many buffers exist, and how many are left. ----
  //
  // In DEDICATED mode each endpoint has its own slice, so the capacity is
  // N_EP and an endpoint can never be short of a buffer it already owns.
  // In SHARED mode the capacity is N_BUF, which is the whole point: fewer
  // buffers than endpoints is the saving, and it is also the blocking.
  function [3:0] popc;
    input [N_EP-1:0] v;
    integer i;
    begin
      popc = 4'd0;
      for (i = 0; i < N_EP; i = i + 1)
        if (v[i]) popc = popc + 4'd1;
    end
  endfunction

  // The capacity is computed in exactly ONE place and used everywhere. It
  // appears in four expressions; writing the conditional out four times is
  // four chances for the architecture to be half-changed, and a pool that is
  // dedicated for its capacity check and shared for its report is a design
  // nobody would write on purpose and everybody writes by editing.
  wire [3:0] cap;
  assign cap       = mode ? NBUF4 : NEP4;
  assign ram_bufs  = cap;
  assign free_bufs = cap - popc(held_r);

  // ---- The oldest holder. ----
  //
  // Not the largest endpoint number, not the most recent: the one that has
  // been sitting on a buffer longest. On a real device that is almost
  // always an endpoint whose firmware forgot to hand one back, and it is
  // the only endpoint in the system worth looking at when another one
  // blocks.
  function [1:0] oldest_holder;
    input dummy;
    integer i;
    reg [15:0] best;
    begin
      oldest_holder = 2'd0;
      best          = 16'd0;
      for (i = 0; i < N_EP; i = i + 1)
        if (held_r[i] && (age_r[i] >= best)) begin
          best          = age_r[i];
          oldest_holder = i[1:0];
        end
    end
  endfunction

  // ---- Among waiting endpoints, the one that has waited longest. ----
  //
  // A fairness policy, and a deliberate one: granting to the lowest
  // endpoint number instead is one line shorter and starves the high ones
  // for as long as the low ones keep asking.
  function [1:0] longest_waiter;
    input dummy;
    integer i;
    reg [15:0] best;
    reg        any;
    begin
      longest_waiter = 2'd0;
      best           = 16'd0;
      any            = 1'b0;
      for (i = 0; i < N_EP; i = i + 1)
        if (pend_r[i] && (!any || (wait_r[i] > best))) begin
          best           = wait_r[i];
          longest_waiter = i[1:0];
          any            = 1'b1;
        end
    end
  endfunction

  integer j;
  reg [N_EP-1:0] held_n, pend_n;
  reg [15:0]     age_n  [0:N_EP-1];
  reg [15:0]     wait_n [0:N_EP-1];
  reg [15:0]     worst_n;
  reg            gr_n, bl_n, er_n;
  reg [1:0]      gep_n, bep_n, hep_n, ec_n;
  reg            req_n, rls_n, dbl_n, unh_n;
  reg [3:0]      free_n;
  reg [1:0]      wnr;

  always @* begin
    held_n  = held_r;
    pend_n  = pend_r;
    worst_n = worst_r;
    gr_n    = 1'b0; bl_n = 1'b0; er_n = 1'b0;
    gep_n   = 2'd0; bep_n = 2'd0; hep_n = 2'd0; ec_n = E_NONE;
    req_n   = 1'b0; rls_n = 1'b0; dbl_n = 1'b0; unh_n = 1'b0;
    for (j = 0; j < N_EP; j = j + 1) begin
      age_n[j]  = age_r[j];
      wait_n[j] = wait_r[j];
    end

    if (eot) begin
      // Nothing: the counters are the report.
    end else begin
      // ---- A release happens FIRST. ----
      //
      // Ordering, not style. A release and a request in the same cycle is
      // the common case on a busy controller, and doing the request first
      // blocks an endpoint against a buffer that is being handed back on
      // the very same cycle. It costs one cycle of latency per collision
      // and it is invisible unless somebody counts blocks.
      if (rel_valid) begin
        if (held_r[rel_ep]) begin
          held_n[rel_ep] = 1'b0;
          age_n[rel_ep]  = 16'd0;
          rls_n          = 1'b1;
        end else begin
          // Firmware handed back a buffer it does not have. Harmless to the
          // hardware and a real bug in the driver, so it is named rather
          // than ignored.
          er_n  = 1'b1; ec_n = E_UNHELD;
          unh_n = 1'b1;
        end
      end

      free_n = cap - popc(held_n);

      if (req_valid) begin
        req_n = 1'b1;
        if (held_r[req_ep] && !(rel_valid && (rel_ep == req_ep))) begin
          // Asking for a second buffer while still holding the first.
          er_n  = 1'b1; ec_n = E_DOUBLE;
          dbl_n = 1'b1;
        end else if (free_n != 4'd0) begin
          held_n[req_ep] = 1'b1;
          age_n[req_ep]  = 16'd0;
          pend_n[req_ep] = 1'b0;
          wait_n[req_ep] = 16'd0;
          gr_n           = 1'b1;
          gep_n          = req_ep;
        end else begin
          // ---- BLOCKED. And the report names the HOLDER. ----
          //
          // `block_ep` is the endpoint that asked; `holder_ep` is the one
          // that has been sitting on a buffer longest. Reporting only the
          // first sends an engineer to read the firmware of an endpoint
          // that is behaving perfectly.
          pend_n[req_ep] = 1'b1;
          bl_n           = 1'b1;
          bep_n          = req_ep;
          hep_n          = oldest_holder(1'b0);
        end
      end else if (|pend_r) begin
        // ---- A waiting endpoint retries automatically. ----
        //
        // A real endpoint with data does not stop wanting a buffer because
        // it was refused once. Modelling the request as a one-shot makes
        // the pool look far better than it is, because every refusal then
        // costs the testbench a retry it has to remember to issue.
        free_n = cap - popc(held_n);
        if (free_n != 4'd0) begin
          wnr             = longest_waiter(1'b0);
          held_n[wnr]     = 1'b1;
          age_n[wnr]      = 16'd0;
          pend_n[wnr]     = 1'b0;
          if (wait_r[wnr] > worst_r) worst_n = wait_r[wnr];
          wait_n[wnr]     = 16'd0;
          gr_n            = 1'b1;
          gep_n           = wnr;
        end
      end

      // ---- Ages and waits advance for everyone still in that state. ----
      for (j = 0; j < N_EP; j = j + 1) begin
        if (held_n[j] && held_r[j] && (age_r[j] != 16'hFFFF))
          age_n[j] = age_r[j] + 16'd1;
        if (pend_n[j] && (wait_r[j] != 16'hFFFF))
          wait_n[j] = wait_r[j] + 16'd1;
        if (pend_n[j] && (wait_n[j] > worst_n)) worst_n = wait_n[j];
      end
    end
  end

  always @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      held_r  <= {N_EP{1'b0}};
      pend_r  <= {N_EP{1'b0}};
      worst_r <= 16'd0;
      gr_r    <= 1'b0; bl_r <= 1'b0; er_r <= 1'b0;
      gep_r   <= 2'd0; bep_r <= 2'd0; hep_r <= 2'd0; ec_r <= E_NONE;
      for (j = 0; j < N_EP; j = j + 1) begin
        age_r[j]  <= 16'd0;
        wait_r[j] <= 16'd0;
      end
      n_req     <= 32'd0;
      n_grant   <= 32'd0;
      n_block   <= 32'd0;
      n_release <= 32'd0;
      n_double  <= 32'd0;
      n_unheld  <= 32'd0;
    end else begin
      held_r  <= held_n;
      pend_r  <= pend_n;
      worst_r <= worst_n;
      gr_r    <= gr_n; bl_r <= bl_n; er_r <= er_n;
      gep_r   <= gep_n; bep_r <= bep_n; hep_r <= hep_n; ec_r <= ec_n;
      for (j = 0; j < N_EP; j = j + 1) begin
        age_r[j]  <= age_n[j];
        wait_r[j] <= wait_n[j];
      end

      if (req_n) n_req     <= n_req     + 32'd1;
      if (gr_n)  n_grant   <= n_grant   + 32'd1;
      if (bl_n)  n_block   <= n_block   + 32'd1;
      if (rls_n) n_release <= n_release + 32'd1;
      if (dbl_n) n_double  <= n_double  + 32'd1;
      if (unh_n) n_unheld  <= n_unheld  + 32'd1;
    end
  end
endmodule

// usb_fifo_pool -- the one architectural difference between USB device
// controllers that actually changes the software you write.
//
// THE REGISTER MAPS ARE DIFFERENT AND IT DOES NOT MATTER
//
// DWC2, MUSB and xHCI have completely different register layouts, different
// naming, different bit positions. Porting between them is a week of
// tedious, mechanical work that a careful engineer gets right.
//
// The thing that is NOT mechanical, and that people get wrong for months,
// is how the controller allocates PACKET BUFFERS to endpoints:
//
//     DEDICATED   every endpoint owns a fixed slice of RAM.
//                 MUSB-style. Deterministic. Wastes memory.
//
//     SHARED      endpoints allocate from a common pool.
//                 DWC2-style. Better utilisation. Introduces
//                 HEAD-OF-LINE BLOCKING.
//
// A SHARED POOL FAILS BY LATENCY, NOT BY ERROR
//
// Nothing is lost. No packet is corrupted, no transfer fails, no error bit
// is set anywhere. Some packets are simply LATE -- and the late ones are
// specifically the ones queued behind an endpoint that is holding a buffer
// and not releasing it.
//
// That is why it is diagnosed so slowly. Every error counter in the device
// reads zero, and the symptom is a latency distribution with a tail.
//
// AND THE FAILURE IS NOT PROPORTIONAL TO LOAD
//
// Below the point where the pool is exhausted, a shared pool behaves
// EXACTLY like a dedicated one -- same latency, same throughput, bit for
// bit. Above it, blocking appears suddenly and the tail grows fast.
//
// There is no gradual degradation to notice in testing, which is the same
// shape as chapter 25.4's retry cliff and has the same consequence: every
// measurement taken below the knee says the design is fine.
//
// THE BLOCKED ENDPOINT IS NOT THE ENDPOINT AT FAULT
//
// This is the part that sends people to the wrong place. When endpoint 2
// cannot get a buffer, the controller reports a problem on endpoint 2. The
// bug is in whatever is holding the buffer -- usually an endpoint whose
// firmware forgot to release one, or whose host stopped polling it.
//
//     Report the HOLDER, not the requester.
//
// So this block names the endpoint that has held a buffer longest, which is
// the one to go and look at.
package usb_pool_pkg;
  // The architecture is a TYPE, not a bit. A one-bit port called `mode` is
  // a number somebody has to look up in a comment; this prints DEDICATED
  // and SHARED in the waveform viewer and in every log line.
  typedef enum logic {
    M_DEDICATED = 1'b0,   // every endpoint owns a fixed slice of RAM
    M_SHARED    = 1'b1    // endpoints allocate from a common pool
  } pool_mode_e;

  typedef enum logic [1:0] {
    E_NONE   = 2'd0,
    E_DOUBLE = 2'd1,      // a request from an endpoint that already holds
    E_UNHELD = 2'd2       // a release from one that does not
  } pool_err_e;
endpackage

module usb_fifo_pool
  import usb_pool_pkg::*;
 #(
  parameter int N_EP  = 4,       // hardware endpoints
  parameter int N_BUF = 2        // packet buffers in the SHARED pool
) (
  input  logic       clk,
  input  logic       rst_n,

  input  pool_mode_e mode,
  input  logic       req_valid,  // this endpoint wants a buffer
  input  logic [1:0] req_ep,
  input  logic       rel_valid,  // this endpoint is done with its buffer
  input  logic [1:0] rel_ep,
  input  logic       eot,

  output logic            grant,     // a buffer was handed out this cycle
  output logic [1:0]      grant_ep,
  output logic            block_pulse,
  output logic [1:0]      block_ep,  // who could not get one
  output logic [1:0]      holder_ep, // who has held one LONGEST -- the culprit
  output logic [N_EP-1:0] held,
  output logic [N_EP-1:0] pending,
  output logic [3:0]      free_bufs,
  output logic [3:0]      ram_bufs,  // the architectural cost, in buffers
  output logic [15:0]     worst_wait,
  output logic            err_pulse,
  output pool_err_e       err_code,

  output logic [31:0] n_req,
  output logic [31:0] n_grant,
  output logic [31:0] n_block,
  output logic [31:0] n_release,
  output logic [31:0] n_double,    // requested while already holding
  output logic [31:0] n_unheld     // released without holding
);

  // Widths derived from the parameters' own type, never from the width the
  // DEFAULT value happens to need -- chapter 25.4's retry budget is what
  // that rule came from.
  localparam logic [3:0] NBUF4 = 4'(N_BUF);
  localparam logic [3:0] NEP4  = 4'(N_EP);

  logic [N_EP-1:0] held_r, pend_r;
  logic [15:0]     age_r  [N_EP-1:0];  // cycles this endpoint has HELD
  logic [15:0]     wait_r [N_EP-1:0];  // cycles this endpoint has WAITED
  logic [15:0]     worst_r;
  logic            gr_r, bl_r, er_r;
  logic [1:0]      gep_r, bep_r, hep_r;
  pool_err_e       ec_r;

  assign grant       = gr_r;
  assign grant_ep    = gep_r;
  assign block_pulse = bl_r;
  assign block_ep    = bep_r;
  assign holder_ep   = hep_r;
  assign held        = held_r;
  assign pending     = pend_r;
  assign worst_wait  = worst_r;
  assign err_pulse   = er_r;
  assign err_code    = ec_r;

  // ---- How many buffers exist, and how many are left. ----
  //
  // In DEDICATED mode each endpoint has its own slice, so the capacity is
  // N_EP and an endpoint can never be short of a buffer it already owns.
  // In SHARED mode the capacity is N_BUF, which is the whole point: fewer
  // buffers than endpoints is the saving, and it is also the blocking.
  function automatic logic [3:0] popc(input logic [N_EP-1:0] v);
    int i;
    begin
      popc = 4'd0;
      for (i = 0; i < N_EP; i = i + 1)
        if (v[i]) popc = popc + 4'd1;
    end
  endfunction

  // The capacity is computed in exactly ONE place and used everywhere. It
  // appears in four expressions; writing the conditional out four times is
  // four chances for the architecture to be half-changed, and a pool that is
  // dedicated for its capacity check and shared for its report is a design
  // nobody would write on purpose and everybody writes by editing.
  logic [3:0] cap;
  assign cap       = (mode == M_SHARED) ? NBUF4 : NEP4;
  assign ram_bufs  = cap;
  assign free_bufs = cap - popc(held_r);

  // ---- The oldest holder. ----
  //
  // Not the largest endpoint number, not the most recent: the one that has
  // been sitting on a buffer longest. On a real device that is almost
  // always an endpoint whose firmware forgot to hand one back, and it is
  // the only endpoint in the system worth looking at when another one
  // blocks.
  function automatic logic [1:0] oldest_holder();
    int i;
    logic [15:0] best;
    begin
      oldest_holder = 2'd0;
      best          = 16'd0;
      for (i = 0; i < N_EP; i = i + 1)
        if (held_r[i] && (age_r[i] >= best)) begin
          best          = age_r[i];
          oldest_holder = i[1:0];
        end
    end
  endfunction

  // ---- Among waiting endpoints, the one that has waited longest. ----
  //
  // A fairness policy, and a deliberate one: granting to the lowest
  // endpoint number instead is one line shorter and starves the high ones
  // for as long as the low ones keep asking.
  function automatic logic [1:0] longest_waiter();
    int i;
    logic [15:0] best;
    logic        any;
    begin
      longest_waiter = 2'd0;
      best           = 16'd0;
      any            = 1'b0;
      for (i = 0; i < N_EP; i = i + 1)
        if (pend_r[i] && (!any || (wait_r[i] > best))) begin
          best           = wait_r[i];
          longest_waiter = i[1:0];
          any            = 1'b1;
        end
    end
  endfunction

  int j;
  logic [N_EP-1:0] held_n, pend_n;
  logic [15:0]     age_n  [N_EP-1:0];
  logic [15:0]     wait_n [N_EP-1:0];
  logic [15:0]     worst_n;
  logic            gr_n, bl_n, er_n;
  logic [1:0]      gep_n, bep_n, hep_n;
  pool_err_e       ec_n;
  logic            req_n, rls_n, dbl_n, unh_n;
  logic [3:0]      free_n;
  logic [1:0]      wnr;

  always_comb begin
    held_n  = held_r;
    pend_n  = pend_r;
    worst_n = worst_r;
    gr_n    = 1'b0; bl_n = 1'b0; er_n = 1'b0;
    gep_n   = 2'd0; bep_n = 2'd0; hep_n = 2'd0; ec_n = E_NONE;
    req_n   = 1'b0; rls_n = 1'b0; dbl_n = 1'b0; unh_n = 1'b0;
    for (j = 0; j < N_EP; j = j + 1) begin
      age_n[j]  = age_r[j];
      wait_n[j] = wait_r[j];
    end

    if (eot) begin
      // Nothing: the counters are the report.
    end else begin
      // ---- A release happens FIRST. ----
      //
      // Ordering, not style. A release and a request in the same cycle is
      // the common case on a busy controller, and doing the request first
      // blocks an endpoint against a buffer that is being handed back on
      // the very same cycle. It costs one cycle of latency per collision
      // and it is invisible unless somebody counts blocks.
      if (rel_valid) begin
        if (held_r[rel_ep]) begin
          held_n[rel_ep] = 1'b0;
          age_n[rel_ep]  = 16'd0;
          rls_n          = 1'b1;
        end else begin
          // Firmware handed back a buffer it does not have. Harmless to the
          // hardware and a real bug in the driver, so it is named rather
          // than ignored.
          er_n  = 1'b1; ec_n = E_UNHELD;
          unh_n = 1'b1;
        end
      end

      free_n = cap - popc(held_n);

      if (req_valid) begin
        req_n = 1'b1;
        if (held_r[req_ep] && !(rel_valid && (rel_ep == req_ep))) begin
          // Asking for a second buffer while still holding the first.
          er_n  = 1'b1; ec_n = E_DOUBLE;
          dbl_n = 1'b1;
        end else if (free_n != 4'd0) begin
          held_n[req_ep] = 1'b1;
          age_n[req_ep]  = 16'd0;
          pend_n[req_ep] = 1'b0;
          wait_n[req_ep] = 16'd0;
          gr_n           = 1'b1;
          gep_n          = req_ep;
        end else begin
          // ---- BLOCKED. And the report names the HOLDER. ----
          //
          // `block_ep` is the endpoint that asked; `holder_ep` is the one
          // that has been sitting on a buffer longest. Reporting only the
          // first sends an engineer to read the firmware of an endpoint
          // that is behaving perfectly.
          pend_n[req_ep] = 1'b1;
          bl_n           = 1'b1;
          bep_n          = req_ep;
          hep_n          = oldest_holder();
        end
      end else if (|pend_r) begin
        // ---- A waiting endpoint retries automatically. ----
        //
        // A real endpoint with data does not stop wanting a buffer because
        // it was refused once. Modelling the request as a one-shot makes
        // the pool look far better than it is, because every refusal then
        // costs the testbench a retry it has to remember to issue.
        free_n = cap - popc(held_n);
        if (free_n != 4'd0) begin
          wnr             = longest_waiter();
          held_n[wnr]     = 1'b1;
          age_n[wnr]      = 16'd0;
          pend_n[wnr]     = 1'b0;
          if (wait_r[wnr] > worst_r) worst_n = wait_r[wnr];
          wait_n[wnr]     = 16'd0;
          gr_n            = 1'b1;
          gep_n           = wnr;
        end
      end

      // ---- Ages and waits advance for everyone still in that state. ----
      for (j = 0; j < N_EP; j = j + 1) begin
        if (held_n[j] && held_r[j] && (age_r[j] != 16'hFFFF))
          age_n[j] = age_r[j] + 16'd1;
        if (pend_n[j] && (wait_r[j] != 16'hFFFF))
          wait_n[j] = wait_r[j] + 16'd1;
        if (pend_n[j] && (wait_n[j] > worst_n)) worst_n = wait_n[j];
      end
    end
  end

  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      held_r  <= '0;
      pend_r  <= '0;
      worst_r <= 16'd0;
      gr_r    <= 1'b0; bl_r <= 1'b0; er_r <= 1'b0;
      gep_r   <= 2'd0; bep_r <= 2'd0; hep_r <= 2'd0; ec_r <= E_NONE;
      for (j = 0; j < N_EP; j = j + 1) begin
        age_r[j]  <= 16'd0;
        wait_r[j] <= 16'd0;
      end
      n_req     <= 32'd0;
      n_grant   <= 32'd0;
      n_block   <= 32'd0;
      n_release <= 32'd0;
      n_double  <= 32'd0;
      n_unheld  <= 32'd0;
    end else begin
      held_r  <= held_n;
      pend_r  <= pend_n;
      worst_r <= worst_n;
      gr_r    <= gr_n; bl_r <= bl_n; er_r <= er_n;
      gep_r   <= gep_n; bep_r <= bep_n; hep_r <= hep_n; ec_r <= ec_n;
      for (j = 0; j < N_EP; j = j + 1) begin
        age_r[j]  <= age_n[j];
        wait_r[j] <= wait_n[j];
      end

      if (req_n) n_req     <= n_req     + 32'd1;
      if (gr_n)  n_grant   <= n_grant   + 32'd1;
      if (bl_n)  n_block   <= n_block   + 32'd1;
      if (rls_n) n_release <= n_release + 32'd1;
      if (dbl_n) n_double  <= n_double  + 32'd1;
      if (unh_n) n_unheld  <= n_unheld  + 32'd1;
    end
  end
endmodule

-- usb_fifo_pool -- the one architectural difference between USB device
-- controllers that actually changes the software you write.
--
-- THE REGISTER MAPS ARE DIFFERENT AND IT DOES NOT MATTER
--
-- DWC2, MUSB and xHCI have completely different register layouts, different
-- naming, different bit positions. Porting between them is a week of
-- tedious, mechanical work that a careful engineer gets right.
--
-- The thing that is NOT mechanical, and that people get wrong for months, is
-- how the controller allocates PACKET BUFFERS to endpoints:
--
--     DEDICATED   every endpoint owns a fixed slice of RAM.
--                 MUSB-style. Deterministic. Wastes memory.
--
--     SHARED      endpoints allocate from a common pool.
--                 DWC2-style. Better utilisation. Introduces
--                 HEAD-OF-LINE BLOCKING.
--
-- A SHARED POOL FAILS BY LATENCY, NOT BY ERROR
--
-- Nothing is lost. No packet is corrupted, no transfer fails, no error bit
-- is set anywhere. Some packets are simply LATE -- and the late ones are
-- specifically the ones queued behind an endpoint that is holding a buffer
-- and not releasing it.
--
-- That is why it is diagnosed so slowly. Every error counter in the device
-- reads zero, and the symptom is a latency distribution with a tail.
--
-- AND THE FAILURE IS NOT PROPORTIONAL TO LOAD
--
-- Below the point where the pool is exhausted, a shared pool behaves EXACTLY
-- like a dedicated one -- same latency, same throughput, bit for bit. Above
-- it, blocking appears suddenly and the tail grows fast.
--
-- There is no gradual degradation to notice in testing, which is the same
-- shape as chapter 25.4's retry cliff and has the same consequence: every
-- measurement taken below the knee says the design is fine.
--
-- THE BLOCKED ENDPOINT IS NOT THE ENDPOINT AT FAULT
--
-- When endpoint 2 cannot get a buffer, the controller reports a problem on
-- endpoint 2. The bug is in whatever is holding the buffer -- usually an
-- endpoint whose firmware forgot to release one, or whose host stopped
-- polling it.
--
--     Report the HOLDER, not the requester.
--
-- So this block names the endpoint that has held a buffer longest, which is
-- the one to go and look at.
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;

package usb_pool_pkg is
  constant M_DEDICATED : std_logic := '0';
  constant M_SHARED    : std_logic := '1';

  constant E_NONE   : std_logic_vector(1 downto 0) := "00";
  constant E_DOUBLE : std_logic_vector(1 downto 0) := "01";
  constant E_UNHELD : std_logic_vector(1 downto 0) := "10";

  type age_array is array (natural range <>) of unsigned(15 downto 0);
end package;

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

entity usb_fifo_pool is
  generic (
    N_EP  : integer := 4;    -- hardware endpoints
    N_BUF : integer := 2     -- packet buffers in the SHARED pool
  );
  port (
    clk       : in std_logic;
    rst_n     : in std_logic;

    mode      : in std_logic;                     -- '0' DEDICATED, '1' SHARED
    req_valid : in std_logic;
    req_ep    : in std_logic_vector(1 downto 0);
    rel_valid : in std_logic;
    rel_ep    : in std_logic_vector(1 downto 0);
    eot       : in std_logic;

    grant       : out std_logic;
    grant_ep    : out std_logic_vector(1 downto 0);
    block_pulse : out std_logic;
    block_ep    : out std_logic_vector(1 downto 0);
    holder_ep   : out std_logic_vector(1 downto 0);
    held        : out std_logic_vector(N_EP-1 downto 0);
    pending     : out std_logic_vector(N_EP-1 downto 0);
    free_bufs   : out unsigned(3 downto 0);
    ram_bufs    : out unsigned(3 downto 0);
    worst_wait  : out unsigned(15 downto 0);
    err_pulse   : out std_logic;
    err_code    : out std_logic_vector(1 downto 0);

    n_req     : out unsigned(31 downto 0);
    n_grant   : out unsigned(31 downto 0);
    n_block   : out unsigned(31 downto 0);
    n_release : out unsigned(31 downto 0);
    n_double  : out unsigned(31 downto 0);
    n_unheld  : out unsigned(31 downto 0)
  );
end entity;

architecture rtl of usb_fifo_pool is
  signal held_r, pend_r : std_logic_vector(N_EP-1 downto 0)
    := (others => '0');
  signal age_r, wait_r  : age_array(0 to N_EP-1)
    := (others => (others => '0'));
  signal worst_r : unsigned(15 downto 0) := (others => '0');
  signal gr_r, bl_r, er_r : std_logic := '0';
  signal gep_r, bep_r, hep_r : std_logic_vector(1 downto 0) := "00";
  signal ec_r : std_logic_vector(1 downto 0) := E_NONE;

  signal req_c, grant_c, block_c : unsigned(31 downto 0) := (others => '0');
  signal rel_c, dbl_c, unh_c     : unsigned(31 downto 0) := (others => '0');

  function popc (v : std_logic_vector) return unsigned is
    variable c : unsigned(3 downto 0) := (others => '0');
  begin
    for i in v'range loop
      if v(i) = '1' then c := c + 1; end if;
    end loop;
    return c;
  end function;

  function capacity (m : std_logic) return unsigned is
  begin
    if m = M_SHARED then
      return to_unsigned(N_BUF, 4);
    else
      return to_unsigned(N_EP, 4);
    end if;
  end function;
begin
  held      <= held_r;
  pending   <= pend_r;
  ram_bufs  <= capacity(mode);
  free_bufs <= capacity(mode) - popc(held_r);

  grant       <= gr_r;
  grant_ep    <= gep_r;
  block_pulse <= bl_r;
  block_ep    <= bep_r;
  holder_ep   <= hep_r;
  worst_wait  <= worst_r;
  err_pulse   <= er_r;
  err_code    <= ec_r;

  n_req     <= req_c;
  n_grant   <= grant_c;
  n_block   <= block_c;
  n_release <= rel_c;
  n_double  <= dbl_c;
  n_unheld  <= unh_c;

  process (clk, rst_n)
    variable held_v, pend_v : std_logic_vector(N_EP-1 downto 0);
    variable age_v, wait_v  : age_array(0 to N_EP-1);
    variable held_pre       : std_logic_vector(N_EP-1 downto 0);
    variable worst_v        : unsigned(15 downto 0);
    variable gr_v, bl_v, er_v : std_logic;
    variable gep_v, bep_v, hep_v, ec_v : std_logic_vector(1 downto 0);
    variable free_v  : unsigned(3 downto 0);
    variable e, r    : integer range 0 to N_EP-1;
    variable best    : unsigned(15 downto 0);
    variable any     : boolean;
    variable wnr     : integer range 0 to N_EP-1;
  begin
    if rst_n = '0' then
      held_r  <= (others => '0');
      pend_r  <= (others => '0');
      age_r   <= (others => (others => '0'));
      wait_r  <= (others => (others => '0'));
      worst_r <= (others => '0');
      gr_r    <= '0'; bl_r <= '0'; er_r <= '0';
      gep_r   <= "00"; bep_r <= "00"; hep_r <= "00"; ec_r <= E_NONE;
      req_c   <= (others => '0');
      grant_c <= (others => '0');
      block_c <= (others => '0');
      rel_c   <= (others => '0');
      dbl_c   <= (others => '0');
      unh_c   <= (others => '0');
    elsif rising_edge(clk) then
      held_v   := held_r;
      pend_v   := pend_r;
      held_pre := held_r;
      age_v    := age_r;
      wait_v   := wait_r;
      worst_v  := worst_r;
      gr_v := '0'; bl_v := '0'; er_v := '0';
      gep_v := "00"; bep_v := "00"; hep_v := "00"; ec_v := E_NONE;
      e := to_integer(unsigned(req_ep));
      r := to_integer(unsigned(rel_ep));

      if eot = '1' then
        -- Nothing: the counters are the report.
        null;
      else
        -- ---- A release happens FIRST. ----
        --
        -- Ordering, not style. A release and a request in the same cycle is
        -- the common case on a busy controller, and doing the request first
        -- blocks an endpoint against a buffer that is being handed back on
        -- the very same cycle. It costs one cycle of latency per collision
        -- and it is invisible unless somebody counts blocks.
        if rel_valid = '1' then
          if held_v(r) = '1' then
            held_v(r) := '0';
            age_v(r)  := (others => '0');
            rel_c     <= rel_c + 1;
          else
            -- Firmware handed back a buffer it does not have. Harmless to
            -- the hardware and a real bug in the driver, so it is named
            -- rather than ignored.
            er_v  := '1';
            ec_v  := E_UNHELD;
            unh_c <= unh_c + 1;
          end if;
        end if;

        free_v := capacity(mode) - popc(held_v);

        if req_valid = '1' then
          req_c <= req_c + 1;
          if (held_r(e) = '1')
             and not (rel_valid = '1' and rel_ep = req_ep) then
            -- Asking for a second buffer while still holding the first.
            er_v  := '1';
            ec_v  := E_DOUBLE;
            dbl_c <= dbl_c + 1;
          elsif free_v /= x"0" then
            held_v(e) := '1';
            age_v(e)  := (others => '0');
            pend_v(e) := '0';
            wait_v(e) := (others => '0');
            gr_v      := '1';
            gep_v     := req_ep;
            grant_c   <= grant_c + 1;
          else
            -- ---- BLOCKED. And the report names the HOLDER. ----
            --
            -- block_ep is the endpoint that asked; holder_ep is the one
            -- that has been sitting on a buffer longest. Reporting only the
            -- first sends an engineer to read the firmware of an endpoint
            -- that is behaving perfectly.
            pend_v(e) := '1';
            bl_v      := '1';
            bep_v     := req_ep;
            best      := (others => '0');
            hep_v     := "00";
            for i in 0 to N_EP-1 loop
              if held_r(i) = '1' and age_r(i) >= best then
                best  := age_r(i);
                hep_v := std_logic_vector(to_unsigned(i, 2));
              end if;
            end loop;
            block_c <= block_c + 1;
          end if;
        elsif pend_v /= (pend_v'range => '0') then
          -- ---- A waiting endpoint retries automatically. ----
          --
          -- A real endpoint with data does not stop wanting a buffer
          -- because it was refused once. Modelling the request as a
          -- one-shot makes the pool look far better than it is.
          free_v := capacity(mode) - popc(held_v);
          if free_v /= x"0" then
            -- Among waiting endpoints, the one that has waited LONGEST.
            -- Granting to the lowest endpoint number instead is one line
            -- shorter and starves the high ones for as long as the low ones
            -- keep asking.
            best := (others => '0');
            any  := false;
            wnr  := 0;
            for i in 0 to N_EP-1 loop
              if pend_v(i) = '1' and ((not any) or wait_v(i) > best) then
                best := wait_v(i);
                wnr  := i;
                any  := true;
              end if;
            end loop;
            held_v(wnr) := '1';
            age_v(wnr)  := (others => '0');
            pend_v(wnr) := '0';
            if wait_v(wnr) > worst_v then worst_v := wait_v(wnr); end if;
            wait_v(wnr) := (others => '0');
            gr_v        := '1';
            gep_v       := std_logic_vector(to_unsigned(wnr, 2));
            grant_c     <= grant_c + 1;
          end if;
        end if;

        -- ---- Ages and waits advance for everyone still in that state. ----
        for i in 0 to N_EP-1 loop
          if held_v(i) = '1' and held_pre(i) = '1' and age_v(i) /= x"FFFF" then
            age_v(i) := age_v(i) + 1;
          end if;
          if pend_v(i) = '1' and wait_v(i) /= x"FFFF" then
            wait_v(i) := wait_v(i) + 1;
          end if;
          if pend_v(i) = '1' and wait_v(i) > worst_v then
            worst_v := wait_v(i);
          end if;
        end loop;
      end if;

      held_r  <= held_v;
      pend_r  <= pend_v;
      age_r   <= age_v;
      wait_r  <= wait_v;
      worst_r <= worst_v;
      gr_r    <= gr_v; bl_r <= bl_v; er_r <= er_v;
      gep_r   <= gep_v; bep_r <= bep_v; hep_r <= hep_v; ec_r <= ec_v;
    end if;
  end process;
end architecture;

   2 architectures x 16 holding states x 9 operations = 288

   Of those, the states with MORE HOLDERS THAN BUFFERS in shared
   mode are UNREACHABLE by construction: five states, nine
   operations each, 45 combinations.

   243 required. 45 declared unreachable and proven never to occur.

`timescale 1ns/1ps
// Testbench for usb_fifo_pool.
//
// The oracle is a shadow model written from the chapter's rules rather than
// from the RTL, re-derived every cycle and compared against every output.
//
// THE EXHAUSTIVE CLAIM IS OVER (ARCHITECTURE, POOL STATE, OPERATION)
//
// A buffer allocator's answer depends on three things at once: which
// architecture it is configured as, exactly which endpoints are currently
// holding, and what is being asked. Sweeping any one of them alone proves
// nothing about the other two -- and the interesting behaviour, blocking,
// exists only at particular combinations.
//
//     2 modes x 16 holding states x 9 operations = 288
//
// Of those, the nine with all four endpoints holding in SHARED mode are
// UNREACHABLE by construction: the pool has three buffers. That is a claim
// about the design, so the testbench makes it explicitly and requires the
// other 279 -- rather than quietly reporting 279/288 and leaving a reader
// to wonder which nine were missed and why. Chapter 24.4's argument, in the
// place it actually bites.
module tb_fp_v;

  localparam integer N_EP  = 4;
  localparam integer N_BUF = 2;

  localparam [1:0] E_NONE = 2'd0, E_DOUBLE = 2'd1, E_UNHELD = 2'd2;

  reg        clk = 1'b0, rst_n = 1'b0;
  reg        mode = 1'b0, req_valid = 1'b0, rel_valid = 1'b0, eot = 1'b0;
  reg  [1:0] req_ep = 2'd0, rel_ep = 2'd0;

  wire            grant, block_pulse, err_pulse;
  wire [1:0]      grant_ep, block_ep, holder_ep, err_code;
  wire [N_EP-1:0] held, pending;
  wire [3:0]      free_bufs, ram_bufs;
  wire [15:0]     worst_wait;
  wire [31:0] n_req, n_grant, n_block, n_release, n_double, n_unheld;

  usb_fifo_pool #(.N_EP(N_EP), .N_BUF(N_BUF)) dut (
    .clk(clk), .rst_n(rst_n),
    .mode(mode), .req_valid(req_valid), .req_ep(req_ep),
    .rel_valid(rel_valid), .rel_ep(rel_ep), .eot(eot),
    .grant(grant), .grant_ep(grant_ep),
    .block_pulse(block_pulse), .block_ep(block_ep), .holder_ep(holder_ep),
    .held(held), .pending(pending),
    .free_bufs(free_bufs), .ram_bufs(ram_bufs), .worst_wait(worst_wait),
    .err_pulse(err_pulse), .err_code(err_code),
    .n_req(n_req), .n_grant(n_grant), .n_block(n_block),
    .n_release(n_release), .n_double(n_double), .n_unheld(n_unheld)
  );

  always #5 clk = ~clk;

  // ---------------- the shadow model ----------------
  reg [N_EP-1:0] m_held, m_pend;
  reg [15:0]     m_age  [0:N_EP-1];
  reg [15:0]     m_wait [0:N_EP-1];
  reg [15:0]     m_worst;
  reg            m_gr, m_bl, m_er;
  reg [1:0]      m_gep, m_bep, m_hep, m_ec;
  reg [31:0] c_req, c_grant, c_block, c_rel, c_dbl, c_unh;

  integer errors = 0, checks = 0, steps = 0;
  integer k;

  // reach: mode (2) x holding state (16) x operation (9)
  reg [0:0] reach [0:287];
  integer   n_reach, n_unreach;

  task ck;
    input [255:0] nm;
    input [31:0]  got, exp;
    begin
      checks = checks + 1;
      if (got !== exp) begin
        errors = errors + 1;
        if (errors < 25)
          $display("FAIL t=%0t step=%0d %0s got=%0d exp=%0d",
                   $time, steps, nm, got, exp);
      end
    end
  endtask

  function [3:0] popc;
    input [N_EP-1:0] v;
    integer i;
    begin
      popc = 4'd0;
      for (i = 0; i < N_EP; i = i + 1) if (v[i]) popc = popc + 4'd1;
    end
  endfunction

  // The oldest holder, from the model's own ages. The tie-break matches the
  // design's documented one: on equal age the highest endpoint index wins,
  // because the scan uses >= and runs upwards.
  function [1:0] m_oldest;
    input dummy;
    integer i;
    reg [15:0] best;
    begin
      m_oldest = 2'd0; best = 16'd0;
      for (i = 0; i < N_EP; i = i + 1)
        if (m_held[i] && (m_age[i] >= best)) begin
          best = m_age[i]; m_oldest = i[1:0];
        end
    end
  endfunction

  function [1:0] m_waiter;
    input dummy;
    integer i;
    reg [15:0] best;
    reg        any;
    begin
      m_waiter = 2'd0; best = 16'd0; any = 1'b0;
      for (i = 0; i < N_EP; i = i + 1)
        if (m_pend[i] && (!any || (m_wait[i] > best))) begin
          best = m_wait[i]; m_waiter = i[1:0]; any = 1'b1;
        end
    end
  endfunction

  reg [N_EP-1:0] m_held_pre;

  task model_step;
    integer j;
    reg [3:0] free_m;
    reg [1:0] w;
    begin
      m_gr = 1'b0; m_bl = 1'b0; m_er = 1'b0;
      m_gep = 2'd0; m_bep = 2'd0; m_hep = 2'd0; m_ec = E_NONE;

      if (eot) begin
        // nothing
      end else begin
        // A release is applied FIRST: a release and a request in the same
        // cycle is the common case, and doing the request first blocks an
        // endpoint against a buffer being handed back on that very cycle.
        if (rel_valid) begin
          if (m_held[rel_ep]) begin
            m_held[rel_ep] = 1'b0;
            m_age[rel_ep]  = 16'd0;
            c_rel = c_rel + 1;
          end else begin
            m_er = 1'b1; m_ec = E_UNHELD;
            c_unh = c_unh + 1;
          end
        end

        free_m = (mode ? N_BUF[3:0] : N_EP[3:0]) - popc(m_held);

        if (req_valid) begin
          c_req = c_req + 1;
          if (m_held[req_ep] && !(rel_valid && (rel_ep == req_ep))) begin
            m_er = 1'b1; m_ec = E_DOUBLE;
            c_dbl = c_dbl + 1;
          end else if (free_m != 4'd0) begin
            m_held[req_ep] = 1'b1;
            m_age[req_ep]  = 16'd0;
            m_pend[req_ep] = 1'b0;
            m_wait[req_ep] = 16'd0;
            m_gr  = 1'b1; m_gep = req_ep;
            c_grant = c_grant + 1;
          end else begin
            m_pend[req_ep] = 1'b1;
            m_bl  = 1'b1; m_bep = req_ep;
            m_hep = m_oldest(1'b0);
            c_block = c_block + 1;
          end
        end else if (|m_pend) begin
          free_m = (mode ? N_BUF[3:0] : N_EP[3:0]) - popc(m_held);
          if (free_m != 4'd0) begin
            w = m_waiter(1'b0);
            m_held[w] = 1'b1;
            m_age[w]  = 16'd0;
            m_pend[w] = 1'b0;
            if (m_wait[w] > m_worst) m_worst = m_wait[w];
            m_wait[w] = 16'd0;
            m_gr = 1'b1; m_gep = w;
            c_grant = c_grant + 1;
          end
        end

        for (j = 0; j < N_EP; j = j + 1) begin
          if (m_held[j] && m_held_pre[j] && (m_age[j] != 16'hFFFF))
            m_age[j] = m_age[j] + 16'd1;
          if (m_pend[j] && (m_wait[j] != 16'hFFFF))
            m_wait[j] = m_wait[j] + 16'd1;
          if (m_pend[j] && (m_wait[j] > m_worst)) m_worst = m_wait[j];
        end
      end
    end
  endtask

  task check_out;
    begin
      ck("held",       {28'd0, held},       {28'd0, m_held});
      ck("pending",    {28'd0, pending},    {28'd0, m_pend});
      ck("free_bufs",  {28'd0, free_bufs},
         {28'd0, (mode ? N_BUF[3:0] : N_EP[3:0]) - popc(m_held)});
      ck("ram_bufs",   {28'd0, ram_bufs}, {28'd0, mode ? N_BUF[3:0] : N_EP[3:0]});
      ck("grant",      {31'd0, grant},       {31'd0, m_gr});
      ck("grant_ep",   {30'd0, grant_ep},    {30'd0, m_gep});
      ck("block_pulse",{31'd0, block_pulse}, {31'd0, m_bl});
      ck("block_ep",   {30'd0, block_ep},    {30'd0, m_bep});
      ck("holder_ep",  {30'd0, holder_ep},   {30'd0, m_hep});
      ck("worst_wait", {16'd0, worst_wait},  {16'd0, m_worst});
      ck("err_pulse",  {31'd0, err_pulse},   {31'd0, m_er});
      ck("err_code",   {30'd0, err_code},    {30'd0, m_ec});
      ck("n_req",     n_req,     c_req);
      ck("n_grant",   n_grant,   c_grant);
      ck("n_block",   n_block,   c_block);
      ck("n_release", n_release, c_rel);
      ck("n_double",  n_double,  c_dbl);
      ck("n_unheld",  n_unheld,  c_unh);
      // ---- the structural invariant ----
      //
      // A buffer is held by exactly one endpoint and the pool cannot be
      // oversubscribed. If this ever fails the allocator has handed the
      // same RAM to two endpoints, which is a data-corruption bug rather
      // than a latency one.
      ck("capacity", {28'd0, popc(held)},
                     {28'd0, (mode ? N_BUF[3:0] : N_EP[3:0]) - free_bufs});
      if (popc(held) > (mode ? N_BUF[3:0] : N_EP[3:0])) begin
        errors = errors + 1;
        $display("FAIL pool oversubscribed: %0d held of %0d", popc(held),
                 mode ? N_BUF : N_EP);
      end
    end
  endtask

  task step;
    integer idx;
    begin
      m_held_pre = m_held;
      if (!eot) begin
        idx = (mode ? 144 : 0) + {28'd0, m_held} * 9 +
              (req_valid ? {30'd0, req_ep} :
               rel_valid ? (4 + {30'd0, rel_ep}) : 8);
        reach[idx] = 1'b1;
      end
      model_step;
      @(posedge clk);
      #1;
      steps = steps + 1;
      check_out;
    end
  endtask

  task req; input [1:0] e;
    begin
      req_valid = 1'b1; rel_valid = 1'b0; eot = 1'b0; req_ep = e;
      step;
      req_valid = 1'b0;
    end
  endtask

  task rel; input [1:0] e;
    begin
      req_valid = 1'b0; rel_valid = 1'b1; eot = 1'b0; rel_ep = e;
      step;
      rel_valid = 1'b0;
    end
  endtask

  task nop;
    begin
      req_valid = 1'b0; rel_valid = 1'b0; eot = 1'b0;
      step;
    end
  endtask

  // ---- A release and a request in the SAME cycle. ----
  //
  // The common case on a busy controller, and the one that distinguishes an
  // allocator which applies the release first from one which does not. The
  // first version of this testbench drove it exactly once, in a directed
  // phase, and the mutation that reverses the order scored 11 -- correct,
  // and one reordered phase from zero.
  task reqrel; input [1:0] e_req; input [1:0] e_rel;
    begin
      req_valid = 1'b1; rel_valid = 1'b1; eot = 1'b0;
      req_ep = e_req; rel_ep = e_rel;
      step;
      req_valid = 1'b0; rel_valid = 1'b0;
    end
  endtask

  task reset_all; input m;
    integer j;
    begin
      req_valid = 1'b0; rel_valid = 1'b0; eot = 1'b0;
      rst_n = 1'b0;
      @(posedge clk); #1;
      rst_n = 1'b1;
      mode  = m;
      m_held = {N_EP{1'b0}}; m_pend = {N_EP{1'b0}}; m_worst = 16'd0;
      m_gr = 1'b0; m_bl = 1'b0; m_er = 1'b0;
      m_gep = 2'd0; m_bep = 2'd0; m_hep = 2'd0; m_ec = E_NONE;
      for (j = 0; j < N_EP; j = j + 1) begin
        m_age[j] = 16'd0; m_wait[j] = 16'd0;
      end
      c_req=0; c_grant=0; c_block=0; c_rel=0; c_dbl=0; c_unh=0;
      @(negedge clk);
    end
  endtask

  integer i, md, st, op, b, w, h0, h1, w0, w1;
  integer base_block, base_grant, n_skipped, n_fair, n_same;
  integer lat_ded, lat_shr;

  initial begin
    for (k = 0; k < 288; k = k + 1) reach[k] = 1'b0;
    n_skipped = 0;

    repeat (3) @(posedge clk);
    rst_n = 1'b1;
    @(negedge clk);

    // ================= PHASE 1 -- the exhaustive (mode, state, op) sweep ==
    //
    // Each holding state is reached BY REQUESTING, never by forcing: a
    // state forced into the design is a state the design never proved it
    // can reach (chapter 22.4).
    for (md = 0; md < 2; md = md + 1)
      for (st = 0; st < 16; st = st + 1)
        for (op = 0; op < 9; op = op + 1) begin
          if ((md == 1) && (popc(st[3:0]) > N_BUF[3:0])) begin
            // UNREACHABLE BY CONSTRUCTION, and declared rather than
            // silently missing: the shared pool has N_BUF buffers, so any
            // state with more holders than that cannot occur. Five of the
            // sixteen states, nine operations each.
            n_skipped = n_skipped + 1;
          end else begin
            reset_all(md[0]);
            for (b = 0; b < N_EP; b = b + 1)
              if (st[b]) req(b[1:0]);
            if (op < 4)      req(op[1:0]);
            else if (op < 8) rel(op[1:0] - 2'd0);
            else             nop;
          end
        end
    if (n_skipped != 45) begin
      errors = errors + 1;
      $display("FAIL skipped %0d unreachable combinations, expected 45",
               n_skipped);
    end

    // ================= PHASE 2 -- DEDICATED never blocks ==================
    //
    // Every endpoint holding at once, repeatedly, with no pool to exhaust.
    // The whole architectural claim in one assertion.
    reset_all(1'b0);
    base_block = c_block;
    for (i = 0; i < 40; i = i + 1) begin
      for (b = 0; b < N_EP; b = b + 1) req(b[1:0]);
      for (b = 0; b < N_EP; b = b + 1) rel(b[1:0]);
    end
    if (c_block != base_block) begin
      errors = errors + 1;
      $display("FAIL DEDICATED blocked %0d times", c_block - base_block);
    end
    if (ram_bufs != N_EP) begin
      errors = errors + 1;
      $display("FAIL DEDICATED reports %0d buffers, expected %0d",
               ram_bufs, N_EP);
    end

    // ================= PHASE 3 -- SHARED is IDENTICAL below the knee ======
    //
    // Three endpoints and three buffers: the pool is never exhausted, so a
    // shared pool behaves exactly like a dedicated one. Bit for bit, no
    // blocking, same grants. This is why the problem is never seen in
    // testing -- every measurement below the knee says the design is fine.
    reset_all(1'b1);
    base_block = c_block; base_grant = c_grant;
    for (i = 0; i < 40; i = i + 1) begin
      for (b = 0; b < N_BUF; b = b + 1) req(b[1:0]);
      for (b = 0; b < N_BUF; b = b + 1) rel(b[1:0]);
    end
    lat_shr = c_block - base_block;
    if (lat_shr != 0) begin
      errors = errors + 1;
      $display("FAIL SHARED blocked %0d times below the knee", lat_shr);
    end
    if (c_grant - base_grant != 40 * N_BUF) begin
      errors = errors + 1;
      $display("FAIL SHARED granted %0d below the knee, expected %0d",
               c_grant - base_grant, 40 * N_BUF);
    end

    // ================= PHASE 4 -- one endpoint past the knee ==============
    //
    // The fourth endpoint asks while three are held. Nothing is lost and
    // nothing errors: it waits. And the report names the HOLDER.
    reset_all(1'b1);
    req(2'd0);                    // ep0 takes a buffer and keeps it
    nop; nop; nop;                // ...and ages
    req(2'd1);
    base_block = c_block;
    req(2'd3);                    // the pool is empty: ep3 blocks
    if (c_block != base_block + 1) begin
      errors = errors + 1;
      $display("FAIL the fourth request did not block");
    end
    if (block_ep !== 2'd3) begin
      errors = errors + 1;
      $display("FAIL block_ep is %0d, expected 3", block_ep);
    end
    // ---- THE point of the block. ----
    if (holder_ep !== 2'd0) begin
      errors = errors + 1;
      $display("FAIL holder_ep is %0d, expected 0 (the oldest holder)",
               holder_ep);
    end
    if (err_pulse !== 1'b0) begin
      errors = errors + 1;
      $display("FAIL blocking raised an error: it is latency, not an error");
    end
    // ...and it is granted the moment a buffer comes back, without asking
    // again.
    rel(2'd1);
    if (!grant || (grant_ep !== 2'd3)) begin
      errors = errors + 1;
      $display("FAIL ep3 was not granted on release (grant=%0b ep=%0d)",
               grant, grant_ep);
    end

    // ================= PHASE 5 -- fairness, over EVERY pair ===============
    //
    // Two endpoints hold the pool; the other two wait. The one that blocked
    // FIRST must be served first, whichever two they are and whichever order
    // they blocked in.
    //
    // The first version of this phase drove exactly one scenario -- endpoint
    // 1 blocking before endpoint 0 -- and the mutation that serves the lowest
    // pending index instead of the longest waiter died on FIVE checks. A
    // property with one instance is a property that is nearly untested, so
    // every choice of two holders and both orders of the two waiters is
    // driven: 6 x 2 = 12 scenarios.
    n_fair = 0;
    for (h0 = 0; h0 < N_EP; h0 = h0 + 1)
      for (h1 = h0 + 1; h1 < N_EP; h1 = h1 + 1)
        for (op = 0; op < 2; op = op + 1) begin
          // the two endpoints that are NOT holding are the two waiters
          w0 = -1; w1 = -1;
          for (b = 0; b < N_EP; b = b + 1)
            if ((b != h0) && (b != h1)) begin
              if (w0 < 0) w0 = b; else w1 = b;
            end
          // `op` picks which of them blocks first, so the longest waiter is
          // sometimes the lower index and sometimes the higher one. An
          // arbiter that serves the lowest index looks correct in half of
          // these and only in half.
          if (op == 1) begin i = w0; w0 = w1; w1 = i; end

          reset_all(1'b1);
          req(h0[1:0]); req(h1[1:0]);      // the pool is full
          req(w0[1:0]);                    // this one blocks FIRST
          nop; nop; nop;
          req(w1[1:0]);                    // and this one SECOND
          nop;
          if (pending !== ((4'd1 << w0) | (4'd1 << w1))) begin
            errors = errors + 1;
            $display("FAIL holders %0d,%0d: expected %0d and %0d waiting, pending=%b",
                     h0, h1, w0, w1, pending);
          end
          rel(h0[1:0]);
          if (!grant || (grant_ep !== w0[1:0])) begin
            errors = errors + 1;
            $display("FAIL holders %0d,%0d: served ep%0d, the longest waiter is %0d",
                     h0, h1, grant_ep, w0);
          end
          // ...and the second waiter is served on the next release, not
          // before it.
          rel(h1[1:0]);
          if (!grant || (grant_ep !== w1[1:0])) begin
            errors = errors + 1;
            $display("FAIL holders %0d,%0d: the second waiter was not served",
                     h0, h1);
          end
          n_fair = n_fair + 1;
        end
    if (n_fair != 12) begin
      errors = errors + 1;
      $display("FAIL fairness scenarios %0d, expected 12", n_fair);
    end

    // ================= PHASE 5b -- release + request, EVERY pair =========
    //
    // At capacity, in one cycle, on different endpoints. This is the common
    // case on a busy controller and it is the one that distinguishes an
    // allocator which applies the release first from one which does not: the
    // buffer being handed back this cycle is the buffer the requester needs.
    //
    // Get the order wrong and nothing breaks -- the requester waits one cycle
    // longer, every single time, and the only symptom is a block count
    // nobody is looking at. Driven for every (holder released, requester)
    // pair rather than once, for the same reason as phase 5.
    n_same = 0;
    for (h0 = 0; h0 < N_EP; h0 = h0 + 1)
      for (h1 = h0 + 1; h1 < N_EP; h1 = h1 + 1)
        for (op = 0; op < 2; op = op + 1)
          for (i = 0; i < 2; i = i + 1) begin
            w0 = -1; w1 = -1;
            for (b = 0; b < N_EP; b = b + 1)
              if ((b != h0) && (b != h1)) begin
                if (w0 < 0) w0 = b; else w1 = b;
              end
            reset_all(1'b1);
            req(h0[1:0]); req(h1[1:0]);        // the pool is full
            base_block = c_block;
            // release one holder and have one non-holder ask, same cycle
            if (op == 0) reqrel((i == 0) ? w0[1:0] : w1[1:0], h0[1:0]);
            else         reqrel((i == 0) ? w0[1:0] : w1[1:0], h1[1:0]);
            if (c_block != base_block) begin
              errors = errors + 1;
              $display("FAIL same-cycle release+request blocked (holders %0d,%0d)",
                       h0, h1);
            end
            if (!grant) begin
              errors = errors + 1;
              $display("FAIL same-cycle release+request was not granted");
            end
            n_same = n_same + 1;
          end
    if (n_same != 24) begin
      errors = errors + 1;
      $display("FAIL same-cycle scenarios %0d, expected 24", n_same);
    end

    // ================= PHASE 6 -- the two firmware bugs ===================
    reset_all(1'b1);
    req(2'd0);
    b = c_dbl;
    req(2'd0);                    // asking again while holding
    if (c_dbl != b + 1) begin
      errors = errors + 1;
      $display("FAIL a double request was not reported");
    end
    b = c_unh;
    rel(2'd2);                    // releasing without holding
    if (c_unh != b + 1) begin
      errors = errors + 1;
      $display("FAIL an unheld release was not reported");
    end
    // ...and a release-then-request on the SAME endpoint in one cycle is
    // legal, not a double request.
    reset_all(1'b1);
    req(2'd1);
    b = c_dbl;
    req_valid = 1'b1; rel_valid = 1'b1; req_ep = 2'd1; rel_ep = 2'd1;
    eot = 1'b0;
    step;
    req_valid = 1'b0; rel_valid = 1'b0;
    if (c_dbl != b) begin
      errors = errors + 1;
      $display("FAIL release+request on one endpoint reported as a double");
    end

    // The random phase is switchable, because a mutation score is only
    // interesting once it is DECOMPOSED. The directed phases already reach
    // every situation the exhaustiveness proof requires, so nothing in that
    // claim depends on it.
`ifndef DIRECTED_ONLY
    // ================= PHASE 7 -- random, in both architectures ===========
    //
    // The stimulus is BIASED, and it has to be. Drawing an endpoint
    // uniformly for a request hits one that is already holding about half
    // the time, so a uniform run spends its cycles on double-request and
    // unheld-release reports and almost never fills the pool -- the first
    // version of this phase produced 4159 double requests and ZERO blocks.
    //
    // Requesting from an endpoint that does NOT hold, and releasing from
    // one that does, is what a working driver does. The misuse cases still
    // appear at a few percent, which is roughly their real rate and enough
    // to keep those two checks under load.
    for (md = 1; md >= 0; md = md - 1) begin
      reset_all(md[0]);
      base_block = c_block; base_grant = c_grant;
      for (i = 0; i < 20000; i = i + 1) begin
        w = $unsigned($random) % 100;
        if (w < 48) begin
          // a request, preferably from an endpoint with no buffer
          b = $unsigned($random) % N_EP;
          if ((w >= 45) || !m_held[b[1:0]]) req(b[1:0]);
          else begin
            for (k = 0; k < N_EP; k = k + 1)
              if (!m_held[k[1:0]]) b = k;
            req(b[1:0]);
          end
        end else if (w < 82) begin
          // a release, preferably from one that has a buffer
          b = $unsigned($random) % N_EP;
          if ((w >= 79) || m_held[b[1:0]]) rel(b[1:0]);
          else begin
            for (k = 0; k < N_EP; k = k + 1)
              if (m_held[k[1:0]]) b = k;
            rel(b[1:0]);
          end
        end else if (w < 94) begin
          // BOTH in one cycle: a holder hands a buffer back while a
          // non-holder asks for one.
          b = 0; op = 1;
          for (k = 0; k < N_EP; k = k + 1) begin
            if (m_held[k[1:0]])  b  = k;     // someone to release
            if (!m_held[k[1:0]]) op = k;     // someone to ask
          end
          reqrel(op[1:0], b[1:0]);
        end else nop;
      end
      $display("PHASE7 %0s: grants=%0d blocks=%0d worst_wait=%0d",
               md ? "SHARED   " : "DEDICATED",
               c_grant - base_grant, c_block - base_block, worst_wait);
    end

`endif

    // ================= the exhaustiveness proof ==========================
    n_reach = 0; n_unreach = 0;
    for (k = 0; k < 288; k = k + 1) begin
      st = (k % 144) / 9;
      if ((k >= 144) && (popc(st[3:0]) > N_BUF[3:0])) begin
        n_unreach = n_unreach + 1;
        // ...and a declared-unreachable combination must actually never
        // have occurred. A declaration is a claim, and a claim that is
        // falsified must fire (chapter 24.4).
        if (reach[k]) begin
          errors = errors + 1;
          $display("FAIL a declared-unreachable combination OCCURRED: held=%0d op=%0d",
                   st, k % 9);
        end
      end else n_reach = n_reach + reach[k];
    end
    if (n_reach != 243) begin
      errors = errors + 1;
      $display("FAIL reachable (mode,state,op) %0d/243", n_reach);
      for (k = 0; k < 288; k = k + 1) begin
        st = (k % 144) / 9;
        if (!reach[k] && !((k >= 144) && (popc(st[3:0]) > N_BUF[3:0])))
          $display("  unreached mode=%0d held=%0d op=%0d", k / 144, st, k % 9);
      end
    end

    $display("steps=%0d checks=%0d reach=%0d/243 (+%0d declared unreachable) errors=%0d",
             steps, checks, n_reach, n_unreach, errors);
    $display("req=%0d grant=%0d block=%0d release=%0d double=%0d unheld=%0d",
             n_req, n_grant, n_block, n_release, n_double, n_unheld);
    $display("worst_wait=%0d", worst_wait);
    $display("%0s: %0d errors in %0d checks",
             (errors == 0) ? "PASS" : "FAIL", errors, checks);
    $finish;
  end
endmodule