The Scheduling Question

   The frame, in order:

     ISO   -- cannot retry        -> place while the frame is empty
     INT   -- can retry, reserved -> after ISO, before best-effort
     CTRL  -- must always fit     -> before bulk, so the bus stays
                                     reconfigurable
     BULK  -- no deadline at all  -> the remainder, ROUND-ROBIN

   Each line's position is forced by a property, not chosen.

// =====================================================================
//  usb_frame_sched -- "Describe USB 2.0 host scheduling" in hardware.
//
//  Chapter 27.5's admission control answered "can these endpoints
//  coexist". This answers the next question: "in what order, in THIS
//  frame" -- and the order is the whole answer:
//
//      Periodic traffic is placed FIRST, before anything that merely
//      wants to go fast. Bulk gets the remainder, and only the
//      remainder.
//
//  That is not a fairness policy. It is the mechanism by which the
//  guarantee made at admission time is actually kept: an endpoint
//  promised a slot in every frame gets it because it is placed before
//  the traffic that would otherwise fill the frame.
//
//  The second half of the answer is the one candidates omit: bulk is
//  served ROUND-ROBIN. Bulk has no reservation, so nothing stops one
//  bulk endpoint from taking the whole remainder of every frame forever
//  -- nothing except a rotating pointer, which is the only fairness
//  mechanism in the entire schedule.
// =====================================================================
module usb_frame_sched #(
  parameter integer FRAME_BYTES = 1500,
  parameter integer N_SLOT      = 8,
  parameter integer TXN_OH      = 13     // per-transaction overhead
) (
  input  wire        clk,
  input  wire        rst_n,

  // ---- a new frame begins ----
  input  wire        frame_tick,

  // ---- the endpoint table ----
  input  wire        cfg_wr,
  input  wire [2:0]  cfg_slot,
  input  wire [1:0]  cfg_type,     // X_CTRL / X_ISO / X_INT / X_BULK
  input  wire [10:0] cfg_maxp,
  input  wire [7:0]  cfg_interval, // frames between polls (periodic)
  input  wire        cfg_enable,

  // ---- the emitted schedule, one entry per cycle ----
  output wire        ent_valid,
  output wire [2:0]  ent_slot,
  output wire [1:0]  ent_type,
  output wire [15:0] ent_bytes,
  output wire        frame_busy,
  output wire [15:0] frame_used,
  output wire [15:0] frame_num,

  // ---- observability ----
  output wire [31:0] n_frames,
  output wire [31:0] n_entries,
  output wire [31:0] n_periodic,
  output wire [31:0] n_bulk,
  output wire [31:0] n_missed,      // must always read 0
  output wire [31:0] n_overrun,     // must always read 0
  output wire [31:0] n_starved      // bulk slots passed over while due
);

  localparam [1:0] X_CTRL = 2'd0, X_ISO = 2'd1, X_INT = 2'd2, X_BULK = 2'd3;

  // ---- the phases of a frame, in the order that keeps the promise ----
  localparam [2:0] P_IDLE = 3'd0,
                   P_ISO  = 3'd1,
                   P_INT  = 3'd2,
                   P_CTRL = 3'd3,
                   P_BULK = 3'd4,
                   P_END  = 3'd5;

  reg [1:0]  ty   [0:N_SLOT-1];
  reg [10:0] mp   [0:N_SLOT-1];
  reg [7:0]  iv   [0:N_SLOT-1];
  reg        en   [0:N_SLOT-1];
  // Frames since this endpoint was last served. Compared against its
  // interval to detect a missed deadline, which is the only thing in this
  // design that a schedule can get wrong without producing a wrong byte.
  reg [15:0] age  [0:N_SLOT-1];

  reg [2:0]  ph;
  reg [2:0]  scan;        // which slot the current phase is examining
  reg [15:0] used_r;
  reg [15:0] fnum_r;
  // ---- the round-robin pointer, and why it needs TWO registers ----
  //
  // A single pointer that advances once per examined slot advances N_SLOT
  // times per frame and therefore returns to exactly where it started --
  // it never rotates at all, and the same bulk endpoint wins every frame
  // forever. The bug is invisible in one frame and total over many.
  //
  // So rr_r is where the NEXT frame starts, updated only when an endpoint
  // is actually served, and bidx is the index the current frame is walking.
  reg [2:0]  rr_r;
  reg [2:0]  bidx;
  reg [2:0]  rr_seen;

  reg        ev_r;
  reg [2:0]  es_r;
  reg [1:0]  et_r;
  reg [15:0] eb_r;

  reg [31:0] fr_c, ent_c, per_c, blk_c, miss_c, over_c, starv_c;

  assign ent_valid  = ev_r;
  assign ent_slot   = es_r;
  assign ent_type   = et_r;
  assign ent_bytes  = eb_r;
  assign frame_busy = (ph != P_IDLE);
  assign frame_used = used_r;
  assign frame_num  = fnum_r;

  assign n_frames   = fr_c;
  assign n_entries  = ent_c;
  assign n_periodic = per_c;
  assign n_bulk     = blk_c;
  assign n_missed   = miss_c;
  assign n_overrun  = over_c;
  assign n_starved  = starv_c;

  // ---- is a periodic endpoint due in this frame? ----
  //
  // The interval is a power of two, so "every Nth frame" is a mask test
  // rather than a division. An endpoint with interval 1 is due every
  // frame; one with interval 8 is due when the low three bits are zero.
  function due_now;
    input [7:0]  interval;
    input [15:0] f;
    begin
      if (interval <= 8'd1) due_now = 1'b1;
      else                  due_now = ((f & {8'd0, (interval - 8'd1)}) == 16'd0);
    end
  endfunction

  function [15:0] cost_of;
    input [10:0] m;
    begin cost_of = {5'd0, m} + TXN_OH[15:0]; end
  endfunction

  integer k;

  always @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      ph      <= P_IDLE;
      scan    <= 3'd0;
      used_r  <= 16'd0;
      fnum_r  <= 16'd0;
      rr_r    <= 3'd0;
      bidx    <= 3'd0;
      rr_seen <= 3'd0;
      ev_r    <= 1'b0;
      es_r    <= 3'd0;
      et_r    <= X_CTRL;
      eb_r    <= 16'd0;
      fr_c    <= 32'd0;
      ent_c   <= 32'd0;
      per_c   <= 32'd0;
      blk_c   <= 32'd0;
      miss_c  <= 32'd0;
      over_c  <= 32'd0;
      starv_c <= 32'd0;
      for (k = 0; k < N_SLOT; k = k + 1) begin
        ty[k]  <= X_CTRL;
        mp[k]  <= 11'd0;
        iv[k]  <= 8'd1;
        en[k]  <= 1'b0;
        age[k] <= 16'd0;
      end
    end else begin
      ev_r <= 1'b0;

      // ---- table writes are only accepted between frames ----
      //
      // Reconfiguring mid-frame would change the schedule the host is
      // already executing, and the endpoint that had already been placed
      // would be served under its old parameters. The host does this
      // between frames, so the design refuses to do it any other way.
      if (cfg_wr && (ph == P_IDLE)) begin
        ty[cfg_slot] <= cfg_type;
        mp[cfg_slot] <= cfg_maxp;
        iv[cfg_slot] <= cfg_interval;
        en[cfg_slot] <= cfg_enable;
        age[cfg_slot] <= 16'd0;
      end

      case (ph)
        // =============================================================
        P_IDLE: begin
          if (frame_tick) begin
            ph      <= P_ISO;
            scan    <= 3'd0;
            used_r  <= 16'd0;
            rr_seen <= 3'd0;
            fr_c    <= fr_c + 32'd1;
            // Every enabled periodic endpoint ages by one frame. An
            // endpoint served this frame will have its age cleared below.
            for (k = 0; k < N_SLOT; k = k + 1)
              if (en[k] && ((ty[k] == X_ISO) || (ty[k] == X_INT)))
                age[k] <= age[k] + 16'd1;
          end
        end

        // =============================================================
        //  ISOCHRONOUS FIRST. It cannot retry, so it cannot be deferred:
        //  an isochronous transaction that does not happen in its frame
        //  does not happen at all.
        // =============================================================
        P_ISO: begin
          if (scan == N_SLOT - 1) ph <= P_INT;
          scan <= scan + 3'd1;

          if (en[scan] && (ty[scan] == X_ISO) && due_now(iv[scan], fnum_r)
              && ((used_r + cost_of(mp[scan])) <= FRAME_BYTES)) begin
            ev_r   <= 1'b1;
            es_r   <= scan;
            et_r   <= X_ISO;
            eb_r   <= cost_of(mp[scan]);
            used_r <= used_r + cost_of(mp[scan]);
            age[scan] <= 16'd0;
            ent_c  <= ent_c + 32'd1;
            per_c  <= per_c + 32'd1;
          end
        end

        // =============================================================
        //  INTERRUPT SECOND. Reserved, but retryable, so it may be
        //  deferred within its interval -- which is exactly why it is
        //  placed after isochronous rather than before.
        // =============================================================
        P_INT: begin
          if (scan == N_SLOT - 1) ph <= P_CTRL;
          scan <= scan + 3'd1;

          if (en[scan] && (ty[scan] == X_INT) && due_now(iv[scan], fnum_r)
              && ((used_r + cost_of(mp[scan])) <= FRAME_BYTES)) begin
            ev_r   <= 1'b1;
            es_r   <= scan;
            et_r   <= X_INT;
            eb_r   <= cost_of(mp[scan]);
            used_r <= used_r + cost_of(mp[scan]);
            age[scan] <= 16'd0;
            ent_c  <= ent_c + 32'd1;
            per_c  <= per_c + 32'd1;
          end
        end

        // =============================================================
        //  CONTROL THIRD, and it is placed before bulk rather than
        //  competing with it. Control is how the host changes the
        //  schedule; a frame full of bulk that leaves no room for
        //  control is a bus that cannot be reconfigured.
        // =============================================================
        P_CTRL: begin
          if (scan == N_SLOT - 1) begin
            ph   <= P_BULK;
            bidx <= rr_r;        // resume where the last frame left off
          end
          scan <= scan + 3'd1;

          if (en[scan] && (ty[scan] == X_CTRL)
              && ((used_r + cost_of(mp[scan])) <= FRAME_BYTES)) begin
            ev_r   <= 1'b1;
            es_r   <= scan;
            et_r   <= X_CTRL;
            eb_r   <= cost_of(mp[scan]);
            used_r <= used_r + cost_of(mp[scan]);
            ent_c  <= ent_c + 32'd1;
          end
        end

        // =============================================================
        //  BULK LAST, ROUND-ROBIN, until the frame is full.
        //
        //  The rotating pointer is the ONLY fairness mechanism in the
        //  whole schedule. Bulk has no reservation, so without it one
        //  bulk endpoint would take the entire remainder of every frame
        //  forever and the others would never move a byte -- with no
        //  error reported anywhere, because nothing was promised.
        // =============================================================
        P_BULK: begin
          if (rr_seen == N_SLOT - 1) ph <= P_END;
          rr_seen <= rr_seen + 3'd1;
          bidx    <= bidx + 3'd1;

          if (en[bidx] && (ty[bidx] == X_BULK)) begin
            if ((used_r + cost_of(mp[bidx])) <= FRAME_BYTES) begin
              ev_r   <= 1'b1;
              es_r   <= bidx;
              et_r   <= X_BULK;
              eb_r   <= cost_of(mp[bidx]);
              used_r <= used_r + cost_of(mp[bidx]);
              ent_c  <= ent_c + 32'd1;
              blk_c  <= blk_c + 32'd1;
              // The next frame starts AFTER the last one served, which is
              // what makes the rotation real.
              rr_r   <= bidx + 3'd1;
            end else begin
              // Passed over for want of room. Counted, because "the frame
              // was full" and "this endpoint is being starved" look the
              // same in one frame and are different over many.
              starv_c <= starv_c + 32'd1;
            end
          end
        end

        // =============================================================
        P_END: begin
          ph     <= P_IDLE;
          fnum_r <= fnum_r + 16'd1;

          // ---- the deadline check, once per frame ----
          //
          // An endpoint whose age has passed its interval has missed a
          // deadline it was promised. Unreachable on a correct schedule,
          // counted so a run can publish zero.
          for (k = 0; k < N_SLOT; k = k + 1)
            if (en[k] && ((ty[k] == X_ISO) || (ty[k] == X_INT))
                && (age[k] > {8'd0, iv[k]}))
              miss_c <= miss_c + 32'd1;

          if (used_r > FRAME_BYTES) over_c <= over_c + 32'd1;
        end

        default: ph <= P_IDLE;
      endcase
    end
  end

endmodule

// =====================================================================
//  usb_frame_sched -- SystemVerilog.
//
//  The frame phases become a named enumeration, which is worth more here
//  than in most designs: the ORDER of those phases IS the answer to the
//  interview question, and `P_ISO -> P_INT -> P_CTRL -> P_BULK` in a
//  waveform says the whole thing at a glance.
//
//  Chapter 27.5's admission control answered "can these endpoints
//  coexist". This answers the next question: "in what order, in THIS
//  frame" -- and the order is the whole answer:
//
//      Periodic traffic is placed FIRST, before anything that merely
//      wants to go fast. Bulk gets the remainder, and only the
//      remainder.
//
//  That is not a fairness policy. It is the mechanism by which the
//  guarantee made at admission time is actually kept: an endpoint
//  promised a slot in every frame gets it because it is placed before
//  the traffic that would otherwise fill the frame.
//
//  The second half of the answer is the one candidates omit: bulk is
//  served ROUND-ROBIN. Bulk has no reservation, so nothing stops one
//  bulk endpoint from taking the whole remainder of every frame forever
//  -- nothing except a rotating pointer, which is the only fairness
//  mechanism in the entire schedule.
// =====================================================================
module usb_frame_sched #(
  parameter int FRAME_BYTES = 1500,
  parameter int N_SLOT      = 8,
  parameter int TXN_OH      = 13     // per-transaction overhead
) (
  input  logic       clk,
  input  logic       rst_n,

  // ---- a new frame begins ----
  input  logic       frame_tick,

  // ---- the endpoint table ----
  input  logic       cfg_wr,
  input  logic [2:0] cfg_slot,
  input  logic [1:0] cfg_type,     // X_CTRL / X_ISO / X_INT / X_BULK
  input  logic [10:0]cfg_maxp,
  input  logic [7:0] cfg_interval, // frames between polls (periodic)
  input  logic       cfg_enable,

  // ---- the emitted schedule, one entry per cycle ----
  output logic       ent_valid,
  output logic [2:0] ent_slot,
  output logic [1:0] ent_type,
  output logic [15:0]ent_bytes,
  output logic       frame_busy,
  output logic [15:0]frame_used,
  output logic [15:0]frame_num,

  // ---- observability ----
  output logic [31:0]n_frames,
  output logic [31:0]n_entries,
  output logic [31:0]n_periodic,
  output logic [31:0]n_bulk,
  output logic [31:0]n_missed,      // must always read 0
  output logic [31:0]n_overrun,     // must always read 0
  output logic [31:0]n_starved      // bulk slots passed over while due
);

  typedef enum logic [1:0] { X_CTRL = 2'd0, X_ISO = 2'd1,
                             X_INT  = 2'd2, X_BULK = 2'd3 } xfer_e;

  // ---- the phases of a frame, in the order that keeps the promise ----
  // The ORDER of these is the answer to the interview question, and a
  // waveform showing P_ISO -> P_INT -> P_CTRL -> P_BULK says it at a glance.
  typedef enum logic [2:0] {
    P_IDLE = 3'd0,
    P_ISO  = 3'd1,
    P_INT  = 3'd2,
    P_CTRL = 3'd3,
    P_BULK = 3'd4,
    P_END  = 3'd5
  } phase_e;

  xfer_e     ty   [N_SLOT];
  logic [10:0] mp [N_SLOT];
  logic [7:0] iv  [N_SLOT];
  logic      en   [N_SLOT];
  // Frames since this endpoint was last served. Compared against its
  // interval to detect a missed deadline, which is the only thing in this
  // design that a schedule can get wrong without producing a wrong byte.
  logic [15:0] age [N_SLOT];

  phase_e    ph;
  logic [2:0] scan;        // which slot the current phase is examining
  logic [15:0] used_r;
  logic [15:0] fnum_r;
  // ---- the round-robin pointer, and why it needs TWO registers ----
  //
  // A single pointer that advances once per examined slot advances N_SLOT
  // times per frame and therefore returns to exactly where it started --
  // it never rotates at all, and the same bulk endpoint wins every frame
  // forever. The bug is invisible in one frame and total over many.
  //
  // So rr_r is where the NEXT frame starts, updated only when an endpoint
  // is actually served, and bidx is the index the current frame is walking.
  logic [2:0] rr_r;
  logic [2:0] bidx;
  logic [2:0] rr_seen;

  logic      ev_r;
  logic [2:0] es_r;
  xfer_e     et_r;
  logic [15:0] eb_r;

  logic [31:0] fr_c, ent_c, per_c, blk_c, miss_c, over_c, starv_c;

  assign ent_valid  = ev_r;
  assign ent_slot   = es_r;
  assign ent_type   = et_r;
  assign ent_bytes  = eb_r;
  assign frame_busy = (ph != P_IDLE);
  assign frame_used = used_r;
  assign frame_num  = fnum_r;

  assign n_frames   = fr_c;
  assign n_entries  = ent_c;
  assign n_periodic = per_c;
  assign n_bulk     = blk_c;
  assign n_missed   = miss_c;
  assign n_overrun  = over_c;
  assign n_starved  = starv_c;

  // ---- is a periodic endpoint due in this frame? ----
  //
  // The interval is a power of two, so "every Nth frame" is a mask test
  // rather than a division. An endpoint with interval 1 is due every
  // frame; one with interval 8 is due when the low three bits are zero.
  function automatic logic due_now(logic [7:0] interval, logic [15:0] f);
    begin
      if (interval <= 8'd1) due_now = 1'b1;
      else                  due_now = ((f & {8'd0, (interval - 8'd1)}) == 16'd0);
    end
  endfunction

  function automatic logic [15:0] cost_of(logic [10:0] m);
    return {5'd0, m} + 16'(TXN_OH);
  endfunction


  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      ph      <= P_IDLE;
      scan    <= 3'd0;
      used_r  <= 16'd0;
      fnum_r  <= 16'd0;
      rr_r    <= 3'd0;
      bidx    <= 3'd0;
      rr_seen <= 3'd0;
      ev_r    <= 1'b0;
      es_r    <= 3'd0;
      et_r    <= X_CTRL;
      eb_r    <= 16'd0;
      fr_c    <= 32'd0;
      ent_c   <= 32'd0;
      per_c   <= 32'd0;
      blk_c   <= 32'd0;
      miss_c  <= 32'd0;
      over_c  <= 32'd0;
      starv_c <= 32'd0;
      for (int k = 0; k < N_SLOT; k++) begin
        ty[k]  <= X_CTRL;
        mp[k]  <= 11'd0;
        iv[k]  <= 8'd1;
        en[k]  <= 1'b0;
        age[k] <= 16'd0;
      end
    end else begin
      ev_r <= 1'b0;

      // ---- table writes are only accepted between frames ----
      //
      // Reconfiguring mid-frame would change the schedule the host is
      // already executing, and the endpoint that had already been placed
      // would be served under its old parameters. The host does this
      // between frames, so the design refuses to do it any other way.
      if (cfg_wr && (ph == P_IDLE)) begin
        ty[cfg_slot] <= xfer_e'(cfg_type);
        mp[cfg_slot] <= cfg_maxp;
        iv[cfg_slot] <= cfg_interval;
        en[cfg_slot] <= cfg_enable;
        age[cfg_slot] <= 16'd0;
      end

      case (ph)
        // =============================================================
        P_IDLE: begin
          if (frame_tick) begin
            ph      <= P_ISO;
            scan    <= 3'd0;
            used_r  <= 16'd0;
            rr_seen <= 3'd0;
            fr_c    <= fr_c + 32'd1;
            // Every enabled periodic endpoint ages by one frame. An
            // endpoint served this frame will have its age cleared below.
            for (int k = 0; k < N_SLOT; k++)
              if (en[k] && ((ty[k] == X_ISO) || (ty[k] == X_INT)))
                age[k] <= age[k] + 16'd1;
          end
        end

        // =============================================================
        //  ISOCHRONOUS FIRST. It cannot retry, so it cannot be deferred:
        //  an isochronous transaction that does not happen in its frame
        //  does not happen at all.
        // =============================================================
        P_ISO: begin
          if (scan == N_SLOT - 1) ph <= P_INT;
          scan <= scan + 3'd1;

          if (en[scan] && (ty[scan] == X_ISO) && due_now(iv[scan], fnum_r)
              && ((used_r + cost_of(mp[scan])) <= FRAME_BYTES)) begin
            ev_r   <= 1'b1;
            es_r   <= scan;
            et_r   <= X_ISO;
            eb_r   <= cost_of(mp[scan]);
            used_r <= used_r + cost_of(mp[scan]);
            age[scan] <= 16'd0;
            ent_c  <= ent_c + 32'd1;
            per_c  <= per_c + 32'd1;
          end
        end

        // =============================================================
        //  INTERRUPT SECOND. Reserved, but retryable, so it may be
        //  deferred within its interval -- which is exactly why it is
        //  placed after isochronous rather than before.
        // =============================================================
        P_INT: begin
          if (scan == N_SLOT - 1) ph <= P_CTRL;
          scan <= scan + 3'd1;

          if (en[scan] && (ty[scan] == X_INT) && due_now(iv[scan], fnum_r)
              && ((used_r + cost_of(mp[scan])) <= FRAME_BYTES)) begin
            ev_r   <= 1'b1;
            es_r   <= scan;
            et_r   <= X_INT;
            eb_r   <= cost_of(mp[scan]);
            used_r <= used_r + cost_of(mp[scan]);
            age[scan] <= 16'd0;
            ent_c  <= ent_c + 32'd1;
            per_c  <= per_c + 32'd1;
          end
        end

        // =============================================================
        //  CONTROL THIRD, and it is placed before bulk rather than
        //  competing with it. Control is how the host changes the
        //  schedule; a frame full of bulk that leaves no room for
        //  control is a bus that cannot be reconfigured.
        // =============================================================
        P_CTRL: begin
          if (scan == N_SLOT - 1) begin
            ph   <= P_BULK;
            bidx <= rr_r;        // resume where the last frame left off
          end
          scan <= scan + 3'd1;

          if (en[scan] && (ty[scan] == X_CTRL)
              && ((used_r + cost_of(mp[scan])) <= FRAME_BYTES)) begin
            ev_r   <= 1'b1;
            es_r   <= scan;
            et_r   <= X_CTRL;
            eb_r   <= cost_of(mp[scan]);
            used_r <= used_r + cost_of(mp[scan]);
            ent_c  <= ent_c + 32'd1;
          end
        end

        // =============================================================
        //  BULK LAST, ROUND-ROBIN, until the frame is full.
        //
        //  The rotating pointer is the ONLY fairness mechanism in the
        //  whole schedule. Bulk has no reservation, so without it one
        //  bulk endpoint would take the entire remainder of every frame
        //  forever and the others would never move a byte -- with no
        //  error reported anywhere, because nothing was promised.
        // =============================================================
        P_BULK: begin
          if (rr_seen == N_SLOT - 1) ph <= P_END;
          rr_seen <= rr_seen + 3'd1;
          bidx    <= bidx + 3'd1;

          if (en[bidx] && (ty[bidx] == X_BULK)) begin
            if ((used_r + cost_of(mp[bidx])) <= FRAME_BYTES) begin
              ev_r   <= 1'b1;
              es_r   <= bidx;
              et_r   <= X_BULK;
              eb_r   <= cost_of(mp[bidx]);
              used_r <= used_r + cost_of(mp[bidx]);
              ent_c  <= ent_c + 32'd1;
              blk_c  <= blk_c + 32'd1;
              // The next frame starts AFTER the last one served, which is
              // what makes the rotation real.
              rr_r   <= bidx + 3'd1;
            end else begin
              // Passed over for want of room. Counted, because "the frame
              // was full" and "this endpoint is being starved" look the
              // same in one frame and are different over many.
              starv_c <= starv_c + 32'd1;
            end
          end
        end

        // =============================================================
        P_END: begin
          ph     <= P_IDLE;
          fnum_r <= fnum_r + 16'd1;

          // ---- the deadline check, once per frame ----
          //
          // An endpoint whose age has passed its interval has missed a
          // deadline it was promised. Unreachable on a correct schedule,
          // counted so a run can publish zero.
          for (int k = 0; k < N_SLOT; k++)
            if (en[k] && ((ty[k] == X_ISO) || (ty[k] == X_INT))
                && (age[k] > {8'd0, iv[k]}))
              miss_c <= miss_c + 32'd1;

          if (used_r > FRAME_BYTES) over_c <= over_c + 32'd1;
        end

        default: ph <= P_IDLE;
      endcase
    end
  end

endmodule

-- =====================================================================
--  usb_frame_sched -- VHDL-2008.
--
--  The frame phases are a real enumeration type, so the ORDER that is the
--  answer to this chapter's question is declared once, in one place, and
--  the compiler refuses to confuse a phase with a transfer type.
--
--  Constants and types are prefixed because VHDL identifiers are
--  case-insensitive: a package name and a same-named port are one name,
--  and the port wins silently.
-- =====================================================================
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;

package fs_pkg is
  type xfer_t is (XT_CTRL, XT_ISO, XT_INT, XT_BULK);

  -- The order of these IS the answer to the interview question.
  type phase_t is (PH_IDLE, PH_ISO, PH_INT, PH_CTRL, PH_BULK, PH_END);

  constant TXN_OH_C : natural := 13;

  function xfer_of(v : std_logic_vector(1 downto 0)) return xfer_t;
  function code_of(t : xfer_t) return std_logic_vector;
  function periodic_t(t : xfer_t) return boolean;

  type mp_arr is array (natural range <>) of unsigned(10 downto 0);
  type iv_arr is array (natural range <>) of unsigned(7 downto 0);
  type ag_arr is array (natural range <>) of unsigned(15 downto 0);
  type ty_arr is array (natural range <>) of xfer_t;
end package;

package body fs_pkg is
  function xfer_of(v : std_logic_vector(1 downto 0)) return xfer_t is
  begin
    case v is
      when "00"   => return XT_CTRL;
      when "01"   => return XT_ISO;
      when "10"   => return XT_INT;
      when others => return XT_BULK;
    end case;
  end function;

  function code_of(t : xfer_t) return std_logic_vector is
  begin
    case t is
      when XT_CTRL => return "00";
      when XT_ISO  => return "01";
      when XT_INT  => return "10";
      when XT_BULK => return "11";
    end case;
  end function;

  function periodic_t(t : xfer_t) return boolean is
  begin
    return t = XT_ISO or t = XT_INT;
  end function;
end package body;

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

entity usb_frame_sched is
  generic (
    FRAME_BYTES : natural := 1500;
    N_SLOT      : natural := 8;
    TXN_OH      : natural := 13
  );
  port (
    clk          : in  std_logic;
    rst_n        : in  std_logic;

    frame_tick   : in  std_logic;

    cfg_wr       : in  std_logic;
    cfg_slot     : in  std_logic_vector(2 downto 0);
    cfg_type     : in  std_logic_vector(1 downto 0);
    cfg_maxp     : in  std_logic_vector(10 downto 0);
    cfg_interval : in  std_logic_vector(7 downto 0);
    cfg_enable   : in  std_logic;

    ent_valid    : out std_logic;
    ent_slot     : out std_logic_vector(2 downto 0);
    ent_type     : out std_logic_vector(1 downto 0);
    ent_bytes    : out std_logic_vector(15 downto 0);
    frame_busy   : out std_logic;
    frame_used   : out std_logic_vector(15 downto 0);
    frame_num    : out std_logic_vector(15 downto 0);

    n_frames     : out std_logic_vector(31 downto 0);
    n_entries    : out std_logic_vector(31 downto 0);
    n_periodic   : out std_logic_vector(31 downto 0);
    n_bulk       : out std_logic_vector(31 downto 0);
    n_missed     : out std_logic_vector(31 downto 0);
    n_overrun    : out std_logic_vector(31 downto 0);
    n_starved    : out std_logic_vector(31 downto 0)
  );
end entity;

architecture rtl of usb_frame_sched is
  signal ty  : ty_arr(0 to N_SLOT-1) := (others => XT_CTRL);
  signal mp  : mp_arr(0 to N_SLOT-1) := (others => (others => '0'));
  signal iv  : iv_arr(0 to N_SLOT-1) := (others => to_unsigned(1, 8));
  signal en  : std_logic_vector(N_SLOT-1 downto 0) := (others => '0');
  -- Frames since this endpoint was last served, compared against its
  -- interval. A missed deadline is the only thing a schedule can get wrong
  -- without producing a single wrong byte.
  signal age : ag_arr(0 to N_SLOT-1) := (others => (others => '0'));

  signal ph      : phase_t := PH_IDLE;
  signal scan    : natural range 0 to 7 := 0;
  signal used_r  : unsigned(15 downto 0) := (others => '0');
  signal fnum_r  : unsigned(15 downto 0) := (others => '0');

  -- TWO pointers, not one. A single pointer advanced once per examined slot
  -- advances N_SLOT times per frame and therefore returns to exactly where
  -- it started -- it never rotates, and the same bulk endpoint wins every
  -- frame forever. rr_r is where the NEXT frame starts and is updated only
  -- when an endpoint is actually served; bidx walks the current frame.
  signal rr_r    : natural range 0 to 7 := 0;
  signal bidx    : natural range 0 to 7 := 0;
  signal rr_seen : natural range 0 to 7 := 0;

  signal ev_r : std_logic := '0';
  signal es_r : natural range 0 to 7 := 0;
  signal et_r : xfer_t := XT_CTRL;
  signal eb_r : unsigned(15 downto 0) := (others => '0');

  signal fr_c, ent_c, per_c, blk_c, miss_c, over_c, starv_c
    : unsigned(31 downto 0) := (others => '0');

  -- The interval is a power of two, so "every Nth frame" is a mask test.
  function due_now(interval : unsigned(7 downto 0);
                   f        : unsigned(15 downto 0)) return boolean is
  begin
    if interval <= 1 then
      return true;
    else
      return (f and resize(interval - 1, 16)) = 0;
    end if;
  end function;

  function cost_of(m : unsigned(10 downto 0)) return unsigned is
  begin
    return resize(m, 16) + to_unsigned(TXN_OH_C, 16);
  end function;
begin

  ent_valid  <= ev_r;
  ent_slot   <= std_logic_vector(to_unsigned(es_r, 3));
  ent_type   <= code_of(et_r);
  ent_bytes  <= std_logic_vector(eb_r);
  frame_busy <= '0' when ph = PH_IDLE else '1';
  frame_used <= std_logic_vector(used_r);
  frame_num  <= std_logic_vector(fnum_r);

  n_frames   <= std_logic_vector(fr_c);
  n_entries  <= std_logic_vector(ent_c);
  n_periodic <= std_logic_vector(per_c);
  n_bulk     <= std_logic_vector(blk_c);
  n_missed   <= std_logic_vector(miss_c);
  n_overrun  <= std_logic_vector(over_c);
  n_starved  <= std_logic_vector(starv_c);

  main : process(clk, rst_n)
    variable cs : natural;
  begin
    if rst_n = '0' then
      ph      <= PH_IDLE;
      scan    <= 0;
      used_r  <= (others => '0');
      fnum_r  <= (others => '0');
      rr_r    <= 0;
      bidx    <= 0;
      rr_seen <= 0;
      ev_r    <= '0';
      es_r    <= 0;
      et_r    <= XT_CTRL;
      eb_r    <= (others => '0');
      fr_c    <= (others => '0');
      ent_c   <= (others => '0');
      per_c   <= (others => '0');
      blk_c   <= (others => '0');
      miss_c  <= (others => '0');
      over_c  <= (others => '0');
      starv_c <= (others => '0');
      ty  <= (others => XT_CTRL);
      mp  <= (others => (others => '0'));
      iv  <= (others => to_unsigned(1, 8));
      en  <= (others => '0');
      age <= (others => (others => '0'));

    elsif rising_edge(clk) then
      ev_r <= '0';

      -- Table writes are accepted only BETWEEN frames. Reconfiguring
      -- mid-frame would change a schedule the host is already executing,
      -- and an endpoint already placed would be served under its old
      -- parameters.
      if cfg_wr = '1' and ph = PH_IDLE then
        cs := to_integer(unsigned(cfg_slot));
        ty(cs)  <= xfer_of(cfg_type);
        mp(cs)  <= unsigned(cfg_maxp);
        iv(cs)  <= unsigned(cfg_interval);
        en(cs)  <= cfg_enable;
        age(cs) <= (others => '0');
      end if;

      case ph is
        when PH_IDLE =>
          if frame_tick = '1' then
            ph      <= PH_ISO;
            scan    <= 0;
            used_r  <= (others => '0');
            rr_seen <= 0;
            fr_c    <= fr_c + 1;
            -- Every enabled periodic endpoint ages by one frame; one served
            -- this frame has its age cleared below.
            for k in 0 to N_SLOT-1 loop
              if en(k) = '1' and periodic_t(ty(k)) then
                age(k) <= age(k) + 1;
              end if;
            end loop;
          end if;

        -- ISOCHRONOUS FIRST. It cannot retry, so it cannot be deferred: a
        -- transaction that does not happen in its frame does not happen.
        when PH_ISO =>
          if scan = N_SLOT - 1 then ph <= PH_INT; end if;
          if scan = N_SLOT - 1 then scan <= 0; else scan <= scan + 1; end if;

          if en(scan) = '1' and ty(scan) = XT_ISO
             and due_now(iv(scan), fnum_r)
             and (used_r + cost_of(mp(scan))) <= to_unsigned(FRAME_BYTES, 16) then
            ev_r     <= '1';
            es_r     <= scan;
            et_r     <= XT_ISO;
            eb_r     <= cost_of(mp(scan));
            used_r   <= used_r + cost_of(mp(scan));
            age(scan) <= (others => '0');
            ent_c    <= ent_c + 1;
            per_c    <= per_c + 1;
          end if;

        -- INTERRUPT SECOND. Reserved but retryable, so it may be deferred
        -- within its interval -- which is why it goes after isochronous.
        when PH_INT =>
          if scan = N_SLOT - 1 then ph <= PH_CTRL; end if;
          if scan = N_SLOT - 1 then scan <= 0; else scan <= scan + 1; end if;

          if en(scan) = '1' and ty(scan) = XT_INT
             and due_now(iv(scan), fnum_r)
             and (used_r + cost_of(mp(scan))) <= to_unsigned(FRAME_BYTES, 16) then
            ev_r     <= '1';
            es_r     <= scan;
            et_r     <= XT_INT;
            eb_r     <= cost_of(mp(scan));
            used_r   <= used_r + cost_of(mp(scan));
            age(scan) <= (others => '0');
            ent_c    <= ent_c + 1;
            per_c    <= per_c + 1;
          end if;

        -- CONTROL THIRD, before bulk rather than competing with it.
        -- Control is how the host changes the schedule; a frame full of
        -- bulk that leaves no room for control is a bus that cannot be
        -- reconfigured.
        when PH_CTRL =>
          if scan = N_SLOT - 1 then
            ph   <= PH_BULK;
            bidx <= rr_r;          -- resume where the last frame left off
          end if;
          if scan = N_SLOT - 1 then scan <= 0; else scan <= scan + 1; end if;

          if en(scan) = '1' and ty(scan) = XT_CTRL
             and (used_r + cost_of(mp(scan))) <= to_unsigned(FRAME_BYTES, 16) then
            ev_r   <= '1';
            es_r   <= scan;
            et_r   <= XT_CTRL;
            eb_r   <= cost_of(mp(scan));
            used_r <= used_r + cost_of(mp(scan));
            ent_c  <= ent_c + 1;
          end if;

        -- BULK LAST, ROUND-ROBIN, until the frame is full. The rotating
        -- pointer is the ONLY fairness mechanism in the whole schedule:
        -- bulk has no reservation, so without it one endpoint would take
        -- the entire remainder of every frame forever, with no error
        -- reported anywhere because nothing was promised.
        when PH_BULK =>
          if rr_seen = N_SLOT - 1 then ph <= PH_END; end if;
          if rr_seen = N_SLOT - 1 then rr_seen <= 0; else rr_seen <= rr_seen + 1; end if;
          if bidx = N_SLOT - 1 then bidx <= 0; else bidx <= bidx + 1; end if;

          if en(bidx) = '1' and ty(bidx) = XT_BULK then
            if (used_r + cost_of(mp(bidx))) <= to_unsigned(FRAME_BYTES, 16) then
              ev_r   <= '1';
              es_r   <= bidx;
              et_r   <= XT_BULK;
              eb_r   <= cost_of(mp(bidx));
              used_r <= used_r + cost_of(mp(bidx));
              ent_c  <= ent_c + 1;
              blk_c  <= blk_c + 1;
              -- The next frame starts AFTER the last one served, which is
              -- what makes the rotation real.
              if bidx = N_SLOT - 1 then rr_r <= 0; else rr_r <= bidx + 1; end if;
            else
              -- Passed over for want of room. Counted, because "the frame
              -- was full" and "this endpoint is starved" look the same in
              -- one frame and are different over many.
              starv_c <= starv_c + 1;
            end if;
          end if;

        when PH_END =>
          ph     <= PH_IDLE;
          fnum_r <= fnum_r + 1;

          -- The deadline check, once per frame. Unreachable on a correct
          -- schedule, counted so a run can publish zero.
          for k in 0 to N_SLOT-1 loop
            if en(k) = '1' and periodic_t(ty(k))
               and age(k) > resize(iv(k), 16) then
              miss_c <= miss_c + 1;
            end if;
          end loop;

          if used_r > to_unsigned(FRAME_BYTES, 16) then
            over_c <= over_c + 1;
          end if;
      end case;
    end if;
  end process;

end architecture;

   What one frame can tell you about fairness:  NOTHING.

     frame 41: bulk slot 3 served, slots 0,1,2,4..7 passed over

   Correct rotation and total starvation produce the
   IDENTICAL frame. Only the sequence of frames differs.

// =====================================================================
//  Testbench for usb_frame_sched.
//
//  Two properties here cannot be checked one transaction at a time.
//
//  ORDER is a property of a whole frame: every entry must belong to a
//  type of priority at least as low as the one before it. So the bench
//  collects a frame's entries and checks the sequence, not the items.
//
//  FAIRNESS is a property of many frames: a round-robin pointer cannot
//  be observed in one frame at all. So the bench counts how many frames
//  each bulk endpoint waits, and asserts a bound over the whole run.
// =====================================================================
`timescale 1ns/1ps
module tb_fs_v;

  localparam integer FRAME_BYTES = 1500;
  localparam integer N_SLOT      = 8;
  localparam integer TXN_OH      = 13;

  localparam [1:0] X_CTRL = 2'd0, X_ISO = 2'd1, X_INT = 2'd2, X_BULK = 2'd3;

  reg         clk = 1'b0, rst_n = 1'b0;
  reg         frame_tick = 1'b0;
  reg         cfg_wr = 1'b0;
  reg  [2:0]  cfg_slot = 3'd0;
  reg  [1:0]  cfg_type = X_CTRL;
  reg  [10:0] cfg_maxp = 11'd0;
  reg  [7:0]  cfg_interval = 8'd1;
  reg         cfg_enable = 1'b0;

  wire        ent_valid, frame_busy;
  wire [2:0]  ent_slot;
  wire [1:0]  ent_type;
  wire [15:0] ent_bytes, frame_used, frame_num;
  wire [31:0] n_frames, n_entries, n_periodic, n_bulk,
              n_missed, n_overrun, n_starved;

  usb_frame_sched #(.FRAME_BYTES(FRAME_BYTES), .N_SLOT(N_SLOT),
                    .TXN_OH(TXN_OH)) dut (
    .clk(clk), .rst_n(rst_n), .frame_tick(frame_tick),
    .cfg_wr(cfg_wr), .cfg_slot(cfg_slot), .cfg_type(cfg_type),
    .cfg_maxp(cfg_maxp), .cfg_interval(cfg_interval), .cfg_enable(cfg_enable),
    .ent_valid(ent_valid), .ent_slot(ent_slot), .ent_type(ent_type),
    .ent_bytes(ent_bytes), .frame_busy(frame_busy),
    .frame_used(frame_used), .frame_num(frame_num),
    .n_frames(n_frames), .n_entries(n_entries), .n_periodic(n_periodic),
    .n_bulk(n_bulk), .n_missed(n_missed), .n_overrun(n_overrun),
    .n_starved(n_starved)
  );

  always #5 clk = ~clk;

  integer errors = 0, checks = 0, steps = 0, frames = 0;
  integer seed;

  function [31:0] urand;
    input dummy;
    begin urand = $random(seed) & 32'h3FFF_FFFF; end
  endfunction

  // ---- the shadow table ----
  reg [1:0]  s_ty [0:N_SLOT-1];
  reg [10:0] s_mp [0:N_SLOT-1];
  reg [7:0]  s_iv [0:N_SLOT-1];
  reg        s_en [0:N_SLOT-1];

  // ---- per-frame collection ----
  reg [2:0]  f_slot [0:63];
  reg [1:0]  f_type [0:63];
  reg [15:0] f_byte [0:63];
  integer    f_n;
  reg [15:0] f_sum;

  // ---- the two headline counters ----
  integer n_order = 0;     // an entry out of priority order
  integer n_over  = 0;     // a frame that exceeded its byte budget

  // ---- fairness: frames since each bulk slot was last served ----
  integer bulk_wait [0:N_SLOT-1];
  integer worst_wait = 0;
  integer ph3_worst  = 0;
  reg     fair_check = 1'b0;
  integer g_frames = 0, g_entries = 0, g_periodic = 0, g_bulk = 0, g_starved = 0;

  // ---- exhaustive reach over (type, interval, frame phase) ----
  reg reach [0:127];
  integer ri, n_reach;

  task ck(input cond, input [255:0] what);
    begin
      checks = checks + 1;
      if (!cond) begin
        errors = errors + 1;
        if (errors <= 20)
          $display("  ERROR @%0t frame=%0d: %0s", $time, frames, what);
      end
    end
  endtask

  // ---- priority, which is NOT the numeric type code ----
  //
  // The type encoding is arbitrary; the placement order is the design's
  // whole thesis. Mapping one to the other explicitly is how the bench
  // avoids checking the encoding by accident.
  function [1:0] prio;
    input [1:0] t;
    begin
      case (t)
        X_ISO:   prio = 2'd0;
        X_INT:   prio = 2'd1;
        X_CTRL:  prio = 2'd2;
        default: prio = 2'd3;   // bulk
      endcase
    end
  endfunction

  function due_f;
    input [7:0] interval;
    input [15:0] f;
    begin
      if (interval <= 8'd1) due_f = 1'b1;
      else                  due_f = ((f & {8'd0, (interval - 8'd1)}) == 16'd0);
    end
  endfunction

  // ---------------------------------------------------------------
  //  Configure one slot. Only legal between frames.
  // ---------------------------------------------------------------
  task cfg(input [2:0] sl, input [1:0] t, input [10:0] m,
           input [7:0] interval, input e);
    begin
      cfg_wr = 1'b1; cfg_slot = sl; cfg_type = t;
      cfg_maxp = m; cfg_interval = interval; cfg_enable = e;
      s_ty[sl] = t; s_mp[sl] = m; s_iv[sl] = interval; s_en[sl] = e;
      @(posedge clk); #1;
      cfg_wr = 1'b0;
      steps = steps + 1;
    end
  endtask

  // ---------------------------------------------------------------
  //  Run one complete frame and check everything about it.
  // ---------------------------------------------------------------
  task run_frame;
    integer guard, a, p;
    reg [15:0] fnum_at_start;
    begin
      fnum_at_start = frame_num;
      f_n   = 0;
      f_sum = 16'd0;

      frame_tick = 1'b1;
      @(posedge clk); #1;
      frame_tick = 1'b0;
      steps = steps + 1;

      // ---- collect until the frame ends ----
      //
      // Bounded. An unbounded wait here is an infinite loop the moment a
      // mutation stops the phase machine advancing, and the run would
      // never reach the summary that says which mutation did it.
      guard = 0;
      while (frame_busy && (guard < 8 * N_SLOT + 32)) begin
        if (ent_valid) begin
          if (f_n < 64) begin
            f_slot[f_n] = ent_slot;
            f_type[f_n] = ent_type;
            f_byte[f_n] = ent_bytes;
          end
          f_sum = f_sum + ent_bytes;
          f_n   = f_n + 1;
        end
        // ---- checked EVERY cycle, not once per frame ----
        //
        // The design's running byte total must equal the bench's
        // accumulation at every point inside the frame, not merely at the
        // end. A scheduler that overshoots and then corrects would pass an
        // end-of-frame check and fail this one.
        ck(frame_used === f_sum[15:0],
           "the running byte total disagrees mid-frame");
        ck(!(ent_valid && !frame_busy),
           "an entry was emitted outside a frame");
        @(posedge clk); #1;
        steps = steps + 1;
        guard = guard + 1;
      end
      ck(guard < 8 * N_SLOT + 32, "the frame never ended");
      // one more cycle to catch an entry emitted on the last phase cycle
      if (ent_valid) begin
        if (f_n < 64) begin
          f_slot[f_n] = ent_slot; f_type[f_n] = ent_type; f_byte[f_n] = ent_bytes;
        end
        f_sum = f_sum + ent_bytes;
        f_n   = f_n + 1;
      end
      frames   = frames + 1;
      g_frames = g_frames + 1;

      // ---- PROPERTY 1: priority order across the whole frame ----
      for (a = 1; a < f_n && a < 64; a = a + 1)
        if (prio(f_type[a]) < prio(f_type[a-1])) begin
          n_order = n_order + 1;
          ck(1'b0, "an entry was placed before a higher-priority one");
        end
      ck(n_order == 0, "the frame was not in priority order");

      // ---- PROPERTY 2: each entry's cost is maxp + overhead ----
      for (a = 0; a < f_n && a < 64; a = a + 1)
        ck(f_byte[a] === ({5'd0, s_mp[f_slot[a]]} + TXN_OH),
           "an entry was charged the wrong number of bytes");

      // ---- PROPERTY 3: the frame never overruns ----
      if (f_sum > FRAME_BYTES) n_over = n_over + 1;
      ck(f_sum <= FRAME_BYTES, "the frame exceeded its byte budget");
      ck(n_over == 0, "a frame overran");
      ck(n_overrun === 32'd0, "the design detected its own overrun");

      // ---- PROPERTY 4: every DUE periodic endpoint that fits was served ----
      //
      // The liveness half. A schedule that places nothing is in perfect
      // priority order and perfectly within budget.
      for (a = 0; a < N_SLOT; a = a + 1)
        if (s_en[a] && ((s_ty[a] == X_ISO) || (s_ty[a] == X_INT))
            && due_f(s_iv[a], fnum_at_start)
            && (({5'd0, s_mp[a]} + TXN_OH) <= FRAME_BYTES)) begin
          p = 0;
          for (ri = 0; ri < f_n && ri < 64; ri = ri + 1)
            if (f_slot[ri] == a[2:0]) p = 1;
          ck(p == 1, "a due periodic endpoint was not served in its frame");
        end

      // ---- PROPERTY 5: served ONLY when due ----
      //
      // The other half of property 4, and the half that is easy to forget:
      // a scheduler that serves every periodic endpoint every frame misses
      // no deadlines and violates nothing the liveness check looks at. It
      // is still wrong -- it spends bandwidth that was reserved for
      // somebody else, and for an isochronous endpoint it delivers data the
      // application has not produced yet.
      for (a = 0; a < N_SLOT; a = a + 1)
        if (s_en[a] && ((s_ty[a] == X_ISO) || (s_ty[a] == X_INT))
            && !due_f(s_iv[a], fnum_at_start)) begin
          p = 0;
          for (ri = 0; ri < f_n && ri < 64; ri = ri + 1)
            if (f_slot[ri] == a[2:0]) p = 1;
          ck(p == 0, "a periodic endpoint was served in a frame it was not due");
        end

      // ---- PROPERTY 6: no missed deadlines, ever ----
      ck(n_missed === 32'd0, "the design reported a missed deadline");

      // ---- PROPERTY 7: the fairness bound, EVERY frame ----
      //
      // Checked per frame rather than once at the end. A single
      // end-of-phase check kills a non-rotating pointer exactly once, and
      // one kill is indistinguishable from luck.
      if (fair_check)
        for (a = 0; a < N_SLOT; a = a + 1)
          if (s_en[a] && (s_ty[a] == X_BULK))
            ck(bulk_wait[a] <= N_SLOT,
               "a bulk endpoint waited longer than the round-robin bound");

      // ---- fairness bookkeeping, checked over the whole run ----
      for (a = 0; a < N_SLOT; a = a + 1) begin
        if (s_en[a] && (s_ty[a] == X_BULK)) begin
          p = 0;
          for (ri = 0; ri < f_n && ri < 64; ri = ri + 1)
            if (f_slot[ri] == a[2:0]) p = 1;
          if (p) bulk_wait[a] = 0;
          else begin
            bulk_wait[a] = bulk_wait[a] + 1;
            if (bulk_wait[a] > worst_wait) worst_wait = bulk_wait[a];
          end
        end else begin
          bulk_wait[a] = 0;
        end
      end

      g_entries  = g_entries + f_n;
      g_periodic = n_periodic;
      g_bulk     = n_bulk;
      g_starved  = n_starved;
    end
  endtask

  task reset_dut;
    integer a;
    begin
      rst_n = 1'b0;
      frame_tick = 0; cfg_wr = 0;
      @(posedge clk); @(posedge clk);
      rst_n = 1'b1;
      for (a = 0; a < N_SLOT; a = a + 1) begin
        s_ty[a] = X_CTRL; s_mp[a] = 11'd0; s_iv[a] = 8'd1; s_en[a] = 1'b0;
        bulk_wait[a] = 0;
      end
      @(posedge clk); #1;
    end
  endtask

  integer ti, vi, fi, k, a4, pj;
  integer per_budget;
  reg [1:0] rt;
  reg [10:0] rm;
  reg [7:0] rv;
  reg re;
  reg [7:0] ivs [0:3];
  reg [1:0] tys [0:3];

  initial begin
    for (ri = 0; ri < 128; ri = ri + 1) reach[ri] = 1'b0;
    ivs[0] = 8'd1; ivs[1] = 8'd2; ivs[2] = 8'd4; ivs[3] = 8'd8;
    tys[0] = X_CTRL; tys[1] = X_ISO; tys[2] = X_INT; tys[3] = X_BULK;
    seed = 32'd27006;

    // =============================================================
    //  PHASE 1 (DIRECTED, EXHAUSTIVE) -- one endpoint of every
    //  (type, interval), observed through all 8 frame phases.
    //  4 x 4 x 8 = 128.
    // =============================================================
    for (ti = 0; ti < 4; ti = ti + 1)
    for (vi = 0; vi < 4; vi = vi + 1) begin
      reset_dut;
      cfg(3'd0, tys[ti], 11'd64, ivs[vi], 1'b1);
      for (fi = 0; fi < 8; fi = fi + 1) begin
        run_frame;
        ri = (ti * 32) + (vi * 8) + fi;
        reach[ri] = 1'b1;
      end
    end

    // =============================================================
    //  PHASE 2 (DIRECTED, EXHAUSTIVE) -- ORDER, over every
    //  assignment of the four types to four slots.
    //
    //  The types are placed in slots in a DIFFERENT order from the
    //  order they must be emitted in, so a scheduler that simply
    //  walked its table would produce the wrong sequence. 24
    //  permutations, and the emitted order must be identical in all.
    // =============================================================
    for (pj = 0; pj < 24; pj = pj + 1) begin
      reset_dut;
      // a simple permutation generator: rotate and swap
      cfg(3'd0, tys[(pj)      % 4], 11'd64, 8'd1, 1'b1);
      cfg(3'd1, tys[(pj / 4 + 1) % 4], 11'd64, 8'd1, 1'b1);
      cfg(3'd2, tys[(pj / 8 + 2) % 4], 11'd64, 8'd1, 1'b1);
      cfg(3'd3, tys[(pj / 12 + 3) % 4], 11'd64, 8'd1, 1'b1);
      run_frame;
      run_frame;
    end

    // =============================================================
    //  PHASE 3 (DIRECTED) -- FAIRNESS, which one frame cannot show.
    //
    //  EIGHT bulk endpoints of 800 bytes each. 813 bytes apiece means
    //  exactly ONE fits in a 1500-byte frame, so seven are passed over
    //  every single frame -- and the question is whether it is always
    //  the same seven.
    //
    //  The sizing matters. An earlier version used 400-byte endpoints,
    //  three of which fit, and the worst wait was 1 frame: a fixed
    //  priority would have looked almost as good as a rotation. Making
    //  only ONE fit forces the wait to N_SLOT-1 under a correct
    //  rotation and to UNBOUNDED under a fixed one.
    // =============================================================
    reset_dut;
    for (k = 0; k < N_SLOT; k = k + 1)
      cfg(k[2:0], X_BULK, 11'd800, 8'd0, 1'b1);
    worst_wait = 0;
    fair_check = 1'b1;
    for (k = 0; k < 64; k = k + 1) run_frame;
    fair_check = 1'b0;
    // ---- the bound is only PROVABLE for this configuration ----
    //
    // The pointer advances when an endpoint is served, so the wait is
    // bounded by N_SLOT only while at least one bulk endpoint fits in every
    // frame -- which is true here by construction (413 bytes into 1500) and
    // NOT true in general. In a frame whose periodic traffic fills the
    // budget no bulk is served, the pointer does not move, and every bulk
    // endpoint waits one frame longer.
    //
    // So the bound is asserted here, where it holds, and the run-wide worst
    // case is reported as an observation rather than checked against a
    // number it is not required to meet.
    ph3_worst = worst_wait;
    ck(ph3_worst <= N_SLOT,
       "a bulk endpoint waited longer than the round-robin bound");
    ck(ph3_worst > 0,
       "no bulk endpoint was ever passed over: fairness was not exercised");

    // =============================================================
    //  PHASE 4 (DIRECTED) -- periodic traffic must NOT be displaced
    //  by bulk, however much bulk there is.
    //
    //  One isochronous endpoint plus eight slots' worth of bulk. The
    //  isochronous endpoint must be served in every single frame.
    // =============================================================
    reset_dut;
    cfg(3'd0, X_ISO, 11'd1023, 8'd1, 1'b1);
    for (k = 1; k < N_SLOT; k = k + 1)
      cfg(k[2:0], X_BULK, 11'd400, 8'd0, 1'b1);
    for (k = 0; k < 32; k = k + 1) begin
      run_frame;
      a4 = 0;
      for (ri = 0; ri < f_n && ri < 64; ri = ri + 1)
        if (f_slot[ri] == 3'd0) a4 = 1;
      ck(a4 == 1, "bulk traffic displaced an isochronous endpoint");
    end

    // =============================================================
    //  PHASE 5 (DIRECTED) -- a configuration write mid-frame is
    //  ignored, because it would change a schedule already running.
    // =============================================================
    //  Swept over every slot and over every cycle of the frame at which
    //  the write could land, because one attempt kills the mutation once
    //  and one kill is indistinguishable from luck.
    for (pj = 0; pj < N_SLOT; pj = pj + 1)
    for (vi = 1; vi < 6; vi = vi + 1) begin
      reset_dut;
      cfg(pj[2:0], X_ISO, 11'd64, 8'd1, 1'b1);
      frame_tick = 1'b1;
      @(posedge clk); #1;
      frame_tick = 1'b0;
      steps = steps + 1;
      // advance into the frame by a varying number of cycles
      for (k = 0; k < vi; k = k + 1) begin @(posedge clk); #1; steps = steps + 1; end
      // mid-frame: try to disable the endpoint
      cfg_wr = 1'b1; cfg_slot = pj[2:0]; cfg_type = X_ISO;
      cfg_maxp = 11'd64; cfg_interval = 8'd1; cfg_enable = 1'b0;
      @(posedge clk); #1;
      cfg_wr = 1'b0;
      steps = steps + 1;
      // drain the frame
      k = 0;
      while (frame_busy && (k < 64)) begin @(posedge clk); #1; k = k + 1; end
      // the endpoint must still be enabled: the write was refused
      run_frame;
      a4 = 0;
      for (ri = 0; ri < f_n && ri < 64; ri = ri + 1)
        if (f_slot[ri] == pj[2:0]) a4 = 1;
      ck(a4 == 1, "a mid-frame configuration write took effect");
    end

    // =============================================================
    //  PHASE 6 (RANDOM) -- an arbitrary endpoint mix.
    // =============================================================
`ifndef DIRECTED_ONLY
    reset_dut;
    for (k = 0; k < 3000; k = k + 1) begin
      if ((k % 8) == 0) begin
        // ---- the random phase applies ADMISSION CONTROL ----
        //
        // A scheduler cannot keep a promise the schedule never had room
        // for. Configuring an arbitrary mix overcommits the frame, the
        // periodic endpoints that do not fit miss their deadlines, and the
        // design correctly reports it -- 386 "missed deadline" errors in
        // the first run of this bench, none of them the scheduler's fault.
        //
        // Chapter 27.5's admission control is a PRECONDITION for this
        // chapter's guarantees, so the stimulus has to respect it.
        per_budget = 0;
        for (a4 = 0; a4 < N_SLOT; a4 = a4 + 1) begin
          rt = tys[urand(0) % 4];
          rm = (urand(0) % 2) ? 11'd64 : 11'd400;
          rv = ivs[urand(0) % 4];
          re = ((urand(0) % 4) != 0);
          if (re && ((rt == X_ISO) || (rt == X_INT))) begin
            if ((per_budget + rm + TXN_OH) > 1350) re = 1'b0;
            else per_budget = per_budget + rm + TXN_OH;
          end
          cfg(a4[2:0], rt, rm, rv, re);
        end
      end
      run_frame;
    end
`endif

    n_reach = 0;
    for (ri = 0; ri < 128; ri = ri + 1) if (reach[ri]) n_reach = n_reach + 1;

    $display("steps=%0d checks=%0d frames=%0d reach=%0d/128 errors=%0d",
             steps, checks, g_frames, n_reach, errors);
    $display("[sched] entries=%0d periodic=%0d bulk=%0d starved=%0d",
             g_entries, g_periodic, g_bulk, g_starved);
    $display("[fairness] round-robin bound phase=%0d (<= %0d required), run-wide worst=%0d",
             ph3_worst, N_SLOT, worst_wait);
    $display("[the whole point] out-of-order entries = %0d, frame overruns = %0d",
             n_order, n_over);
    if (n_reach != 128) begin
      $display("FAIL: exhaustive sweep incomplete"); errors = errors + 1;
    end
    if (errors == 0) $display("PASS: 0 errors in %0d checks", checks);
    else             $display("FAIL: %0d errors in %0d checks", errors, checks);
    $finish;
  end

endmodule

// =====================================================================
//  Testbench for usb_frame_sched.
//
//  Two properties here cannot be checked one transaction at a time.
//
//  ORDER is a property of a whole frame: every entry must belong to a
//  type of priority at least as low as the one before it. So the bench
//  collects a frame's entries and checks the sequence, not the items.
//
//  FAIRNESS is a property of many frames: a round-robin pointer cannot
//  be observed in one frame at all. So the bench counts how many frames
//  each bulk endpoint waits, and asserts a bound over the whole run.
// =====================================================================
`timescale 1ns/1ps
module tb_fs_sv;

  localparam integer FRAME_BYTES = 1500;
  localparam integer N_SLOT      = 8;
  localparam integer TXN_OH      = 13;

  localparam [1:0] X_CTRL = 2'd0, X_ISO = 2'd1, X_INT = 2'd2, X_BULK = 2'd3;

  logic       clk = 1'b0, rst_n = 1'b0;
  logic       frame_tick = 1'b0;
  logic       cfg_wr = 1'b0;
  logic [2:0] cfg_slot = 3'd0;
  logic [1:0] cfg_type = X_CTRL;
  logic [10:0] cfg_maxp = 11'd0;
  logic [7:0] cfg_interval = 8'd1;
  logic       cfg_enable = 1'b0;

  logic       ent_valid, frame_busy;
  logic [2:0] ent_slot;
  logic [1:0] ent_type;
  logic [15:0] ent_bytes, frame_used, frame_num;
  logic [31:0] n_frames, n_entries, n_periodic, n_bulk,
               n_missed, n_overrun, n_starved;

  usb_frame_sched #(.FRAME_BYTES(FRAME_BYTES), .N_SLOT(N_SLOT),
                    .TXN_OH(TXN_OH)) dut (
    .clk(clk), .rst_n(rst_n), .frame_tick(frame_tick),
    .cfg_wr(cfg_wr), .cfg_slot(cfg_slot), .cfg_type(cfg_type),
    .cfg_maxp(cfg_maxp), .cfg_interval(cfg_interval), .cfg_enable(cfg_enable),
    .ent_valid(ent_valid), .ent_slot(ent_slot), .ent_type(ent_type),
    .ent_bytes(ent_bytes), .frame_busy(frame_busy),
    .frame_used(frame_used), .frame_num(frame_num),
    .n_frames(n_frames), .n_entries(n_entries), .n_periodic(n_periodic),
    .n_bulk(n_bulk), .n_missed(n_missed), .n_overrun(n_overrun),
    .n_starved(n_starved)
  );

  always #5 clk = ~clk;

  integer errors = 0, checks = 0, steps = 0, frames = 0;
  integer seed;

  function automatic logic [31:0] urand(bit dummy);
    return $random(seed) & 32'h3FFF_FFFF;
  endfunction

  // ---- the shadow table ----
  logic [1:0] s_ty [0:N_SLOT-1];
  logic [10:0] s_mp [0:N_SLOT-1];
  logic [7:0] s_iv [0:N_SLOT-1];
  logic      s_en [0:N_SLOT-1];

  // ---- per-frame collection ----
  logic [2:0] f_slot [0:63];
  logic [1:0] f_type [0:63];
  logic [15:0] f_byte [0:63];
  integer    f_n;
  logic [15:0] f_sum;

  // ---- the two headline counters ----
  integer n_order = 0;     // an entry out of priority order
  integer n_over  = 0;     // a frame that exceeded its byte budget

  // ---- fairness: frames since each bulk slot was last served ----
  integer bulk_wait [0:N_SLOT-1];
  integer worst_wait = 0;
  integer ph3_worst  = 0;
  logic   fair_check = 1'b0;
  integer g_frames = 0, g_entries = 0, g_periodic = 0, g_bulk = 0, g_starved = 0;

  // ---- exhaustive reach over (type, interval, frame phase) ----
  logic reach [0:127];
  integer ri, n_reach;

  task ck(input logic cond, input logic [255:0] what);
    begin
      checks = checks + 1;
      if (!cond) begin
        errors = errors + 1;
        if (errors <= 20)
          $display("  ERROR @%0t frame=%0d: %0s", $time, frames, what);
      end
    end
  endtask

  // ---- priority, which is NOT the numeric type code ----
  //
  // The type encoding is arbitrary; the placement order is the design's
  // whole thesis. Mapping one to the other explicitly is how the bench
  // avoids checking the encoding by accident.
  function automatic logic [1:0] prio(logic [1:0] t);
    begin
      case (t)
        X_ISO:   prio = 2'd0;
        X_INT:   prio = 2'd1;
        X_CTRL:  prio = 2'd2;
        default: prio = 2'd3;   // bulk
      endcase
    end
  endfunction

  function automatic logic due_f(logic [7:0] interval, logic [15:0] f);
    begin
      if (interval <= 8'd1) due_f = 1'b1;
      else                  due_f = ((f & {8'd0, (interval - 8'd1)}) == 16'd0);
    end
  endfunction

  // ---------------------------------------------------------------
  //  Configure one slot. Only legal between frames.
  // ---------------------------------------------------------------
  task cfg(input logic [2:0] sl, input logic [1:0] t, input logic [10:0] m,
           input logic [7:0] interval, input logic e);
    begin
      cfg_wr = 1'b1; cfg_slot = sl; cfg_type = t;
      cfg_maxp = m; cfg_interval = interval; cfg_enable = e;
      s_ty[sl] = t; s_mp[sl] = m; s_iv[sl] = interval; s_en[sl] = e;
      @(posedge clk); #1;
      cfg_wr = 1'b0;
      steps = steps + 1;
    end
  endtask

  // ---------------------------------------------------------------
  //  Run one complete frame and check everything about it.
  // ---------------------------------------------------------------
  task run_frame;
    integer guard, a, p;
    logic [15:0] fnum_at_start;
    begin
      fnum_at_start = frame_num;
      f_n   = 0;
      f_sum = 16'd0;

      frame_tick = 1'b1;
      @(posedge clk); #1;
      frame_tick = 1'b0;
      steps = steps + 1;

      // ---- collect until the frame ends ----
      //
      // Bounded. An unbounded wait here is an infinite loop the moment a
      // mutation stops the phase machine advancing, and the run would
      // never reach the summary that says which mutation did it.
      guard = 0;
      while (frame_busy && (guard < 8 * N_SLOT + 32)) begin
        if (ent_valid) begin
          if (f_n < 64) begin
            f_slot[f_n] = ent_slot;
            f_type[f_n] = ent_type;
            f_byte[f_n] = ent_bytes;
          end
          f_sum = f_sum + ent_bytes;
          f_n   = f_n + 1;
        end
        // ---- checked EVERY cycle, not once per frame ----
        //
        // The design's running byte total must equal the bench's
        // accumulation at every point inside the frame, not merely at the
        // end. A scheduler that overshoots and then corrects would pass an
        // end-of-frame check and fail this one.
        ck(frame_used === f_sum[15:0],
           "the running byte total disagrees mid-frame");
        ck(!(ent_valid && !frame_busy),
           "an entry was emitted outside a frame");
        @(posedge clk); #1;
        steps = steps + 1;
        guard = guard + 1;
      end
      ck(guard < 8 * N_SLOT + 32, "the frame never ended");
      // one more cycle to catch an entry emitted on the last phase cycle
      if (ent_valid) begin
        if (f_n < 64) begin
          f_slot[f_n] = ent_slot; f_type[f_n] = ent_type; f_byte[f_n] = ent_bytes;
        end
        f_sum = f_sum + ent_bytes;
        f_n   = f_n + 1;
      end
      frames   = frames + 1;
      g_frames = g_frames + 1;

      // ---- PROPERTY 1: priority order across the whole frame ----
      for (a = 1; a < f_n && a < 64; a = a + 1)
        if (prio(f_type[a]) < prio(f_type[a-1])) begin
          n_order = n_order + 1;
          ck(1'b0, "an entry was placed before a higher-priority one");
        end
      ck(n_order == 0, "the frame was not in priority order");

      // ---- PROPERTY 2: each entry's cost is maxp + overhead ----
      for (a = 0; a < f_n && a < 64; a = a + 1)
        ck(f_byte[a] === ({5'd0, s_mp[f_slot[a]]} + TXN_OH),
           "an entry was charged the wrong number of bytes");

      // ---- PROPERTY 3: the frame never overruns ----
      if (f_sum > FRAME_BYTES) n_over = n_over + 1;
      ck(f_sum <= FRAME_BYTES, "the frame exceeded its byte budget");
      ck(n_over == 0, "a frame overran");
      ck(n_overrun === 32'd0, "the design detected its own overrun");

      // ---- PROPERTY 4: every DUE periodic endpoint that fits was served ----
      //
      // The liveness half. A schedule that places nothing is in perfect
      // priority order and perfectly within budget.
      for (a = 0; a < N_SLOT; a = a + 1)
        if (s_en[a] && ((s_ty[a] == X_ISO) || (s_ty[a] == X_INT))
            && due_f(s_iv[a], fnum_at_start)
            && (({5'd0, s_mp[a]} + TXN_OH) <= FRAME_BYTES)) begin
          p = 0;
          for (ri = 0; ri < f_n && ri < 64; ri = ri + 1)
            if (f_slot[ri] == a[2:0]) p = 1;
          ck(p == 1, "a due periodic endpoint was not served in its frame");
        end

      // ---- PROPERTY 5: served ONLY when due ----
      //
      // The other half of property 4, and the half that is easy to forget:
      // a scheduler that serves every periodic endpoint every frame misses
      // no deadlines and violates nothing the liveness check looks at. It
      // is still wrong -- it spends bandwidth that was reserved for
      // somebody else, and for an isochronous endpoint it delivers data the
      // application has not produced yet.
      for (a = 0; a < N_SLOT; a = a + 1)
        if (s_en[a] && ((s_ty[a] == X_ISO) || (s_ty[a] == X_INT))
            && !due_f(s_iv[a], fnum_at_start)) begin
          p = 0;
          for (ri = 0; ri < f_n && ri < 64; ri = ri + 1)
            if (f_slot[ri] == a[2:0]) p = 1;
          ck(p == 0, "a periodic endpoint was served in a frame it was not due");
        end

      // ---- PROPERTY 6: no missed deadlines, ever ----
      ck(n_missed === 32'd0, "the design reported a missed deadline");

      // ---- PROPERTY 7: the fairness bound, EVERY frame ----
      //
      // Checked per frame rather than once at the end. A single
      // end-of-phase check kills a non-rotating pointer exactly once, and
      // one kill is indistinguishable from luck.
      if (fair_check)
        for (a = 0; a < N_SLOT; a = a + 1)
          if (s_en[a] && (s_ty[a] == X_BULK))
            ck(bulk_wait[a] <= N_SLOT,
               "a bulk endpoint waited longer than the round-robin bound");

      // ---- fairness bookkeeping, checked over the whole run ----
      for (a = 0; a < N_SLOT; a = a + 1) begin
        if (s_en[a] && (s_ty[a] == X_BULK)) begin
          p = 0;
          for (ri = 0; ri < f_n && ri < 64; ri = ri + 1)
            if (f_slot[ri] == a[2:0]) p = 1;
          if (p) bulk_wait[a] = 0;
          else begin
            bulk_wait[a] = bulk_wait[a] + 1;
            if (bulk_wait[a] > worst_wait) worst_wait = bulk_wait[a];
          end
        end else begin
          bulk_wait[a] = 0;
        end
      end

      g_entries  = g_entries + f_n;
      g_periodic = n_periodic;
      g_bulk     = n_bulk;
      g_starved  = n_starved;
    end
  endtask

  task reset_dut;
    integer a;
    begin
      rst_n = 1'b0;
      frame_tick = 0; cfg_wr = 0;
      @(posedge clk); @(posedge clk);
      rst_n = 1'b1;
      for (a = 0; a < N_SLOT; a = a + 1) begin
        s_ty[a] = X_CTRL; s_mp[a] = 11'd0; s_iv[a] = 8'd1; s_en[a] = 1'b0;
        bulk_wait[a] = 0;
      end
      @(posedge clk); #1;
    end
  endtask

  integer ti, vi, fi, k, a4, pj;
  integer per_budget;
  logic [1:0] rt;
  logic [10:0] rm;
  logic [7:0] rv;
  logic re;
  logic [7:0] ivs [0:3];
  logic [1:0] tys [0:3];

  initial begin
    for (ri = 0; ri < 128; ri = ri + 1) reach[ri] = 1'b0;
    ivs[0] = 8'd1; ivs[1] = 8'd2; ivs[2] = 8'd4; ivs[3] = 8'd8;
    tys[0] = X_CTRL; tys[1] = X_ISO; tys[2] = X_INT; tys[3] = X_BULK;
    seed = 32'd27006;

    // =============================================================
    //  PHASE 1 (DIRECTED, EXHAUSTIVE) -- one endpoint of every
    //  (type, interval), observed through all 8 frame phases.
    //  4 x 4 x 8 = 128.
    // =============================================================
    for (ti = 0; ti < 4; ti = ti + 1)
    for (vi = 0; vi < 4; vi = vi + 1) begin
      reset_dut;
      cfg(3'd0, tys[ti], 11'd64, ivs[vi], 1'b1);
      for (fi = 0; fi < 8; fi = fi + 1) begin
        run_frame;
        ri = (ti * 32) + (vi * 8) + fi;
        reach[ri] = 1'b1;
      end
    end

    // =============================================================
    //  PHASE 2 (DIRECTED, EXHAUSTIVE) -- ORDER, over every
    //  assignment of the four types to four slots.
    //
    //  The types are placed in slots in a DIFFERENT order from the
    //  order they must be emitted in, so a scheduler that simply
    //  walked its table would produce the wrong sequence. 24
    //  permutations, and the emitted order must be identical in all.
    // =============================================================
    for (pj = 0; pj < 24; pj = pj + 1) begin
      reset_dut;
      // a simple permutation generator: rotate and swap
      cfg(3'd0, tys[(pj)      % 4], 11'd64, 8'd1, 1'b1);
      cfg(3'd1, tys[(pj / 4 + 1) % 4], 11'd64, 8'd1, 1'b1);
      cfg(3'd2, tys[(pj / 8 + 2) % 4], 11'd64, 8'd1, 1'b1);
      cfg(3'd3, tys[(pj / 12 + 3) % 4], 11'd64, 8'd1, 1'b1);
      run_frame;
      run_frame;
    end

    // =============================================================
    //  PHASE 3 (DIRECTED) -- FAIRNESS, which one frame cannot show.
    //
    //  EIGHT bulk endpoints of 800 bytes each. 813 bytes apiece means
    //  exactly ONE fits in a 1500-byte frame, so seven are passed over
    //  every single frame -- and the question is whether it is always
    //  the same seven.
    //
    //  The sizing matters. An earlier version used 400-byte endpoints,
    //  three of which fit, and the worst wait was 1 frame: a fixed
    //  priority would have looked almost as good as a rotation. Making
    //  only ONE fit forces the wait to N_SLOT-1 under a correct
    //  rotation and to UNBOUNDED under a fixed one.
    // =============================================================
    reset_dut;
    for (k = 0; k < N_SLOT; k = k + 1)
      cfg(k[2:0], X_BULK, 11'd800, 8'd0, 1'b1);
    worst_wait = 0;
    fair_check = 1'b1;
    for (k = 0; k < 64; k = k + 1) run_frame;
    fair_check = 1'b0;
    // ---- the bound is only PROVABLE for this configuration ----
    //
    // The pointer advances when an endpoint is served, so the wait is
    // bounded by N_SLOT only while at least one bulk endpoint fits in every
    // frame -- which is true here by construction (413 bytes into 1500) and
    // NOT true in general. In a frame whose periodic traffic fills the
    // budget no bulk is served, the pointer does not move, and every bulk
    // endpoint waits one frame longer.
    //
    // So the bound is asserted here, where it holds, and the run-wide worst
    // case is reported as an observation rather than checked against a
    // number it is not required to meet.
    ph3_worst = worst_wait;
    ck(ph3_worst <= N_SLOT,
       "a bulk endpoint waited longer than the round-robin bound");
    ck(ph3_worst > 0,
       "no bulk endpoint was ever passed over: fairness was not exercised");

    // =============================================================
    //  PHASE 4 (DIRECTED) -- periodic traffic must NOT be displaced
    //  by bulk, however much bulk there is.
    //
    //  One isochronous endpoint plus eight slots' worth of bulk. The
    //  isochronous endpoint must be served in every single frame.
    // =============================================================
    reset_dut;
    cfg(3'd0, X_ISO, 11'd1023, 8'd1, 1'b1);
    for (k = 1; k < N_SLOT; k = k + 1)
      cfg(k[2:0], X_BULK, 11'd400, 8'd0, 1'b1);
    for (k = 0; k < 32; k = k + 1) begin
      run_frame;
      a4 = 0;
      for (ri = 0; ri < f_n && ri < 64; ri = ri + 1)
        if (f_slot[ri] == 3'd0) a4 = 1;
      ck(a4 == 1, "bulk traffic displaced an isochronous endpoint");
    end

    // =============================================================
    //  PHASE 5 (DIRECTED) -- a configuration write mid-frame is
    //  ignored, because it would change a schedule already running.
    // =============================================================
    //  Swept over every slot and over every cycle of the frame at which
    //  the write could land, because one attempt kills the mutation once
    //  and one kill is indistinguishable from luck.
    for (pj = 0; pj < N_SLOT; pj = pj + 1)
    for (vi = 1; vi < 6; vi = vi + 1) begin
      reset_dut;
      cfg(pj[2:0], X_ISO, 11'd64, 8'd1, 1'b1);
      frame_tick = 1'b1;
      @(posedge clk); #1;
      frame_tick = 1'b0;
      steps = steps + 1;
      // advance into the frame by a varying number of cycles
      for (k = 0; k < vi; k = k + 1) begin @(posedge clk); #1; steps = steps + 1; end
      // mid-frame: try to disable the endpoint
      cfg_wr = 1'b1; cfg_slot = pj[2:0]; cfg_type = X_ISO;
      cfg_maxp = 11'd64; cfg_interval = 8'd1; cfg_enable = 1'b0;
      @(posedge clk); #1;
      cfg_wr = 1'b0;
      steps = steps + 1;
      // drain the frame
      k = 0;
      while (frame_busy && (k < 64)) begin @(posedge clk); #1; k = k + 1; end
      // the endpoint must still be enabled: the write was refused
      run_frame;
      a4 = 0;
      for (ri = 0; ri < f_n && ri < 64; ri = ri + 1)
        if (f_slot[ri] == pj[2:0]) a4 = 1;
      ck(a4 == 1, "a mid-frame configuration write took effect");
    end

    // =============================================================
    //  PHASE 6 (RANDOM) -- an arbitrary endpoint mix.
    // =============================================================
`ifndef DIRECTED_ONLY
    reset_dut;
    for (k = 0; k < 3000; k = k + 1) begin
      if ((k % 8) == 0) begin
        // ---- the random phase applies ADMISSION CONTROL ----
        //
        // A scheduler cannot keep a promise the schedule never had room
        // for. Configuring an arbitrary mix overcommits the frame, the
        // periodic endpoints that do not fit miss their deadlines, and the
        // design correctly reports it -- 386 "missed deadline" errors in
        // the first run of this bench, none of them the scheduler's fault.
        //
        // Chapter 27.5's admission control is a PRECONDITION for this
        // chapter's guarantees, so the stimulus has to respect it.
        per_budget = 0;
        for (a4 = 0; a4 < N_SLOT; a4 = a4 + 1) begin
          rt = tys[urand(0) % 4];
          rm = (urand(0) % 2) ? 11'd64 : 11'd400;
          rv = ivs[urand(0) % 4];
          re = ((urand(0) % 4) != 0);
          if (re && ((rt == X_ISO) || (rt == X_INT))) begin
            if ((per_budget + rm + TXN_OH) > 1350) re = 1'b0;
            else per_budget = per_budget + rm + TXN_OH;
          end
          cfg(a4[2:0], rt, rm, rv, re);
        end
      end
      run_frame;
    end
`endif

    n_reach = 0;
    for (ri = 0; ri < 128; ri = ri + 1) if (reach[ri]) n_reach = n_reach + 1;

    $display("steps=%0d checks=%0d frames=%0d reach=%0d/128 errors=%0d",
             steps, checks, g_frames, n_reach, errors);
    $display("[sched] entries=%0d periodic=%0d bulk=%0d starved=%0d",
             g_entries, g_periodic, g_bulk, g_starved);
    $display("[fairness] round-robin bound phase=%0d (<= %0d required), run-wide worst=%0d",
             ph3_worst, N_SLOT, worst_wait);
    $display("[the whole point] out-of-order entries = %0d, frame overruns = %0d",
             n_order, n_over);
    if (n_reach != 128) begin
      $display("FAIL: exhaustive sweep incomplete"); errors = errors + 1;
    end
    if (errors == 0) $display("PASS: 0 errors in %0d checks", checks);
    else             $display("FAIL: %0d errors in %0d checks", errors, checks);
    $finish;
  end

endmodule