Bandwidth Allocation

Chapter 17.3 treated the budget as a single bit. can_fit arrived from somewhere, said yes or no, and the arbiter used it as one of three eligibility terms — never asking where it came from.

This chapter is where it comes from, and it is not a constant.

The frame's allocation is refreshed at every boundary and consumed transaction by transaction, so can_fit depends on everything already committed to the frame. The arbiter's answer at microframe 5 depends on decisions it made at microframes 0 through 4.

And it introduces a distinction 17.3 did not need: a scheduler has two numbers for every transaction, and they are not the same number.

1. What This Chapter Is Not — the 16.4 Boundary

Chapter 16.4 also computed bandwidth, so the difference has to be stated first.

16.4 decided who may hold a reservation. This chapter spends it. An endpoint admitted in 16.4 still has to fit in the specific frame the scheduler is filling, alongside everything else admitted to the same frame — and the per-frame ledger is what tracks that.

The numbers themselves come from 16.4 and are not recomputed here: bus time in nanoseconds, worst-case bit stuffing at 7/6, and the periodic cap — 90% of a full-speed frame, 80% of a high-speed microframe. This chapter takes a cost as given and is about what happens to the ledger.

2. Two Numbers for Every Transaction

Here is the distinction the module has been building toward.

A scheduler must decide before the transaction runs. It cannot know what the transaction will actually cost — a device may NAK, a packet may be short, a retry may occur — so it decides using an estimate.

It must account after the transaction runs. Only then is the actual cost known, and the ledger has to reflect what really happened or every later decision in the frame is made against fiction.

   ESTIMATED cost --> the ADMISSION decision   (before)
   ACTUAL cost    --> the LEDGER correction    (after)

3. The Ledger, and Its Four Operations

Refresh. At a frame boundary the budget is restored in full. The previous frame's consumption is gone; a frame does not borrow from its successor.

Reserve. A transaction is admitted and its estimate is deducted. Only a successful reservation consumes anything — a rejected one must leave the ledger untouched, because there is no partial admission (16.4 §6 made the same argument about configurations).

Settle. The transaction completes. The estimate is given back and the actual cost taken, in one operation. If the actual exceeds what the frame could absorb, the budget saturates at zero and an overrun is recorded.

Idle. Nothing happens to the ledger. Most cycles.

Their precedence must be stated, not inherited from the order the branches happen to appear in, because two of them can arrive together (§4).

4. The Collision: a Boundary and a Reservation

A frame boundary and a reservation in the same cycle. Does the reservation consume the old frame's remainder or the new frame's fresh budget?

Both are defensible and the design must pick one and say so. This design charges it to the new frame, on the grounds that a reservation made at a boundary is a reservation for the frame that is starting — the transaction will run in the new frame, so it should be paid for out of the new frame.

Leaving this implicit is how sequential RTL acquires defects that appear only under load, because the collision is rare when traffic is light and common when it is not. §12's mutation G3 takes the other choice and costs 1170 failures.

Saturation, not wrapping. A budget that wraps reports a nearly empty frame as a nearly full one — the direction that admits still more work into a frame already over-committed. This is the third time Module 16 and 17 have made that argument (16.1, 16.3, 16.5) and it is the same argument each time: when a counter must be wrong, it should be wrong in the direction that raises an alarm rather than silences one.

The two orange stages are §2's pair. The estimate decides; the actual corrects. Everything between them is bookkeeping, and §12's G4 is what happens when the second stage quietly uses the first stage's number.

5. The Hardware, Before Any Language

State retained: the remaining budget, and a sticky overrun flag.

On reset or bus reset: the budget is full and the overrun flag clear.

can_fit is combinational — estimate ≤ remaining, inclusive — and it is an output, because 17.3 consumes it as an eligibility term and 16.4 established that a transaction exactly filling the allocation is legal.

Precedence: a frame boundary outranks a settlement, which outranks a reservation.

On a boundary: the budget is restored — less any reservation arriving in the same cycle, which is charged to the new frame (§4).

On a settlement: the estimate is returned and the actual cost taken, in one expression at full width so the intermediate cannot wrap between the two operations. If the result is negative the budget saturates at zero and the overrun flag sets — and stays set, because a frame that was over-committed is a fact about the configuration, not about the instant.

On an accepted reservation: the estimate is deducted. On a rejected one: nothing.

6. Verilog

The RTL contract

• What it models: the per-frame bandwidth ledger of a host-controller scheduler.
• Why it exists: because can_fit is a function of what has already been committed to the frame (§0), and because decisions and accounting use different numbers (§2).
• Inputs: frame_tick, reserve_valid + reserve_est, settle_valid + settle_est + settle_act, bus_reset.
• Authoritative state: rem_r, over_r. Nothing else is stored.
• Derived state: can_fit, reserve_ok, and the settlement expression — all combinational.
• Outputs: remaining, overrun, can_fit, reserve_ok.
• Hardware implied: one COST_W+1 register, one subtractor, one signed adder one bit wider, two comparators, one flag.
• Reset: asynchronous active-low rst_n; bus_reset synchronous and equivalent; both restore the full budget and clear the overrun.
• Priority: frame boundary > settlement > reservation (§3).
• Latency: can_fit and reserve_ok are combinational; the ledger updates on the next edge.
• Boundary behaviour: the fit test is inclusive; the budget saturates at zero and never wraps.
• Collision behaviour: a reservation arriving at a frame boundary is charged to the new frame (§4).
• Assumptions: one transaction in flight; settle_est is the value that was reserved; costs arrive already computed by 16.4's arithmetic.
• Omissions: no per-class ledgers, no multiple transactions in flight, no cost computation.
• What DV should verify: that a rejected reservation consumes nothing; that the fit boundary is inclusive; that a settlement uses the actual cost; that the budget saturates; that the overrun flag is sticky; that the boundary collision is charged to the new frame.

// usb_frame_budget -- how much of this frame is left, and who may still use it.
//
// Chapter 16.4 decided whether an isochronous endpoint could be ADMITTED at
// all: an arithmetic done once, at configuration time, against a fixed cap.
// This module is the other half. The cap is a per-frame quantity, it is
// REFRESHED at every frame boundary, and it is consumed transaction by
// transaction as the scheduler commits work into the frame.
//
// The distinction the module exists to teach is that a scheduler has TWO
// numbers for every transaction and they are not the same number:
//
//   ESTIMATED cost -- known BEFORE the transaction, used to decide
//   ACTUAL cost    -- known AFTER it, used to correct the account
//
// A design that uses the estimate for both makes correct decisions and keeps
// a wrong ledger; a design that waits for the actual cost cannot decide at
// all. Both numbers are necessary, and mutation G5 measures what happens
// when the second is quietly replaced by the first.
module usb_frame_budget #(
  parameter integer COST_W   = 16,
  parameter integer BUDGET   = 100000   // ns of periodic allocation per frame
) (
  input  wire                clk,
  input  wire                rst_n,
  input  wire                bus_reset,
  input  wire                frame_tick,      // a new frame begins
  // ---- reservation: decided from the ESTIMATE, before the transaction ----
  input  wire                reserve_valid,
  input  wire [COST_W-1:0]   reserve_est,
  output wire                reserve_ok,      // the estimate fits
  // ---- settlement: corrected by the ACTUAL cost, after the transaction ----
  input  wire                settle_valid,
  input  wire [COST_W-1:0]   settle_est,      // what was reserved
  input  wire [COST_W-1:0]   settle_act,      // what it really cost
  // ---- state ----
  output wire [COST_W:0]     remaining,       // ns left in this frame
  output wire                overrun,         // sticky: actual exceeded the frame
  output wire                can_fit          // combinational, for the arbiter
);
  localparam [COST_W:0] BUDGET_V = BUDGET;

  reg [COST_W:0] rem_r;
  reg            over_r;

  assign remaining = rem_r;
  assign overrun   = over_r;

  // The fit test is INCLUSIVE: a transaction that exactly fills the frame is
  // legal. The budget is what MAY be used, not what must be left over --
  // the same boundary Chapter 16.4 had to construct stimulus to reach.
  wire [COST_W:0] est_ext = {1'b0, reserve_est};
  assign can_fit    = (est_ext <= rem_r);
  assign reserve_ok = reserve_valid && can_fit;

  // Settlement: give back what was reserved, take what it actually cost.
  // Computed in one expression at full width so the intermediate cannot
  // wrap between the two operations.
  wire signed [COST_W+2:0] settled =
      $signed({2'b00, rem_r})
    + $signed({2'b00, {1'b0, settle_est}})
    - $signed({2'b00, {1'b0, settle_act}});

  // An actual cost larger than the remaining budget allows means the frame
  // has been over-committed. The budget SATURATES at zero rather than
  // wrapping -- a wrapped budget reports a nearly empty frame as a nearly
  // full one, which is the direction that admits still more work.
  wire underflow = (settled < 0);

  always @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      rem_r <= BUDGET_V; over_r <= 1'b0;
    end else if (bus_reset) begin
      rem_r <= BUDGET_V; over_r <= 1'b0;
    end else begin
      // COLLISION: a frame boundary and a reservation in the same cycle.
      // The boundary wins and the reservation is charged against the NEW
      // frame, because a reservation made at a boundary is a reservation
      // FOR the frame that is starting. Stated here rather than inherited
      // from the order the branches happen to appear in.
      if (frame_tick) begin
        rem_r <= (reserve_valid && ({1'b0, reserve_est} <= BUDGET_V))
                 ? (BUDGET_V - {1'b0, reserve_est})
                 : BUDGET_V;
      end else begin
        if (settle_valid) begin
          rem_r  <= underflow ? {(COST_W+1){1'b0}} : settled[COST_W:0];
          if (underflow) over_r <= 1'b1;
        end else if (reserve_ok) begin
          // Only a SUCCESSFUL reservation consumes budget. A rejected one
          // must consume nothing -- there is no partial admission.
          rem_r <= rem_r - est_ext;
        end
      end
    end
  end
endmodule

Two details are worth naming.

The settlement is one signed expression at full width. Computing remaining + est into a register and then subtracting act gives an intermediate that can overflow upward before the subtraction brings it back — a value that never existed in the ledger but was briefly representable in it. One expression, two extra bits, and the intermediate cannot misbehave.

underflow is a signed comparison against zero, which is the one place this design could have repeated Chapter 15.3's defect. $signed on both operands is explicit for exactly that reason.

7. SystemVerilog

package usb_budget_pkg;
  // What this cycle does to the frame's ledger. Naming the four cases makes
  // their PRECEDENCE explicit -- which matters because a frame boundary and
  // a reservation can arrive together, and source-code ordering is not an
  // acceptable way to decide which wins.
  typedef enum logic [1:0] {
    L_IDLE,      // nothing happens to the ledger
    L_REFRESH,   // a frame boundary: the budget is restored
    L_SETTLE,    // a completed transaction is trued up to its ACTUAL cost
    L_RESERVE    // an accepted reservation consumes its ESTIMATE
  } ledger_e;
endpackage

module usb_frame_budget_sv
  import usb_budget_pkg::*;
#(
  parameter int unsigned COST_W = 16,
  parameter int unsigned BUDGET = 100000
) (
  input  logic              clk,
  input  logic              rst_n,
  input  logic              bus_reset,
  input  logic              frame_tick,
  input  logic              reserve_valid,
  input  logic [COST_W-1:0] reserve_est,
  output logic              reserve_ok,
  input  logic              settle_valid,
  input  logic [COST_W-1:0] settle_est,
  input  logic [COST_W-1:0] settle_act,
  output logic [COST_W:0]   remaining,
  output logic              overrun,
  output logic              can_fit,
  output ledger_e           ledger_op
);
  initial begin
    if (BUDGET == 0)
      $fatal(1, "BUDGET=0 admits nothing at all");
    if (BUDGET > ((1 << COST_W) - 1))
      $fatal(1, "BUDGET=%0d cannot be represented in COST_W=%0d bits",
             BUDGET, COST_W);
  end

  localparam logic [COST_W:0] BUDGET_V = (COST_W+1)'(BUDGET);

  // The fit test is INCLUSIVE: a transaction that exactly fills the frame is
  // legal. The budget is what MAY be used, not what must be left over.
  wire [COST_W:0] est_ext = {1'b0, reserve_est};
  assign can_fit    = (est_ext <= remaining);
  assign reserve_ok = reserve_valid && can_fit;

  // PRECEDENCE, stated rather than inherited from branch order. A frame
  // boundary outranks a settlement, which outranks a reservation.
  always_comb begin
    if      (frame_tick)  ledger_op = L_REFRESH;
    else if (settle_valid) ledger_op = L_SETTLE;
    else if (reserve_ok)   ledger_op = L_RESERVE;
    else                   ledger_op = L_IDLE;
  end

  // Settlement in one signed expression at full width, so the intermediate
  // cannot wrap between giving back the estimate and taking the actual.
  wire signed [COST_W+2:0] settled =
      $signed({2'b00, remaining})
    + $signed({2'b00, 1'b0, settle_est})
    - $signed({2'b00, 1'b0, settle_act});
  wire underflow = (settled < 0);

  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n || bus_reset) begin
      remaining <= BUDGET_V;
      overrun   <= 1'b0;
    end else begin
      unique case (ledger_op)
        L_IDLE: ;

        L_REFRESH: begin
          // COLLISION: a reservation arriving at a frame boundary is charged
          // against the NEW frame, because a reservation made at a boundary
          // is a reservation FOR the frame that is starting.
          remaining <= (reserve_valid && (est_ext <= BUDGET_V))
                       ? (BUDGET_V - est_ext) : BUDGET_V;
        end

        L_SETTLE: begin
          // SATURATE at zero. A wrapped budget reports a nearly empty frame
          // as a nearly full one -- the direction that admits still more work.
          remaining <= underflow ? '0 : (COST_W+1)'(settled);
          if (underflow) overrun <= 1'b1;
        end

        L_RESERVE: begin
          // Only a SUCCESSFUL reservation consumes budget; a rejected one
          // consumes nothing, because there is no partial admission.
          remaining <= remaining - est_ext;
        end
      endcase
    end
  end
endmodule

ledger_e makes §3's precedence a declaration rather than a branch order. L_REFRESH, L_SETTLE, L_RESERVE, L_IDLE are computed in one always_comb and consumed by one unique case — so the question which operation wins when two arrive together is answered in a place a reviewer can find, instead of being a property of where the else if happens to sit.

It is also an output, which §14's debugging uses: knowing why the ledger moved is a different question from knowing that it did.

8. VHDL

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

package usb_budget_pkg is
  -- What this cycle does to the frame's ledger. Naming the four cases makes
  -- their PRECEDENCE explicit, which matters because a frame boundary and a
  -- reservation can arrive together and source-code ordering is not an
  -- acceptable way to decide which wins.
  type ledger_t is (L_IDLE, L_REFRESH, L_SETTLE, L_RESERVE);
end package;

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

entity usb_frame_budget_vhdl is
  generic (
    COST_W : positive := 16;
    BUDGET : positive := 100000
  );
  port (
    clk           : in  std_logic;
    rst_n         : in  std_logic;
    bus_reset     : in  std_logic;
    frame_tick    : in  std_logic;
    reserve_valid : in  std_logic;
    reserve_est   : in  unsigned(COST_W-1 downto 0);
    reserve_ok    : out std_logic;
    settle_valid  : in  std_logic;
    settle_est    : in  unsigned(COST_W-1 downto 0);
    settle_act    : in  unsigned(COST_W-1 downto 0);
    remaining     : out unsigned(COST_W downto 0);
    overrun       : out std_logic;
    can_fit       : out std_logic;
    ledger_op     : out ledger_t
  );
end entity;

architecture rtl of usb_frame_budget_vhdl is
  constant BUDGET_V : unsigned(COST_W downto 0) :=
    to_unsigned(BUDGET, COST_W+1);

  signal rem_r  : unsigned(COST_W downto 0) := (others => '0');
  signal over_r : std_logic := '0';
  signal est_ext : unsigned(COST_W downto 0);
  signal fit     : boolean;
  signal ok      : std_logic;
  signal op      : ledger_t;
  -- SIGNED, because the settlement can legitimately go below zero before it
  -- is saturated. numeric_std makes that a different TYPE from the unsigned
  -- ledger, so the sign cannot be lost by an accidental mixed expression --
  -- the property Chapter 15.3 found Verilog does not provide.
  signal settled : signed(COST_W+2 downto 0);
  signal underflow : boolean;
begin
  assert BUDGET <= 2**COST_W - 1
    report "BUDGET cannot be represented in COST_W bits" severity failure;

  remaining <= rem_r;
  overrun   <= over_r;
  reserve_ok<= ok;
  can_fit   <= '1' when fit else '0';
  ledger_op <= op;

  -- The fit test is INCLUSIVE: a transaction that exactly fills the frame is
  -- legal. The budget is what MAY be used, not what must be left over.
  est_ext <= '0' & reserve_est;
  fit     <= est_ext <= rem_r;
  ok      <= '1' when (reserve_valid = '1' and fit) else '0';

  -- PRECEDENCE, stated rather than inherited from branch order.
  op <= L_REFRESH when frame_tick = '1' else
        L_SETTLE  when settle_valid = '1' else
        L_RESERVE when ok = '1' else
        L_IDLE;

  settled <= signed("00" & rem_r)
           + signed("000" & settle_est)
           - signed("000" & settle_act);
  underflow <= settled < 0;

  process (clk, rst_n)
  begin
    if rst_n = '0' then
      rem_r <= BUDGET_V; over_r <= '0';
    elsif rising_edge(clk) then
      if bus_reset = '1' then
        rem_r <= BUDGET_V; over_r <= '0';
      else
        case op is
          when L_IDLE =>
            null;

          when L_REFRESH =>
            -- COLLISION: a reservation arriving at a frame boundary is
            -- charged against the NEW frame, because a reservation made at
            -- a boundary is a reservation FOR the frame that is starting.
            if reserve_valid = '1' and est_ext <= BUDGET_V then
              rem_r <= BUDGET_V - est_ext;
            else
              rem_r <= BUDGET_V;
            end if;

          when L_SETTLE =>
            -- SATURATE at zero. A wrapped budget reports a nearly empty
            -- frame as a nearly full one: the direction that admits more.
            if underflow then
              rem_r  <= (others => '0');
              over_r <= '1';
            else
              rem_r <= unsigned(settled(COST_W downto 0));
            end if;

          when L_RESERVE =>
            -- Only a SUCCESSFUL reservation consumes budget; a rejected one
            -- consumes nothing, because there is no partial admission.
            rem_r <= rem_r - est_ext;
        end case;
      end if;
    end if;
  end process;
end architecture;

settled is signed while the ledger is unsigned, and numeric_std makes those distinct types. A mixed expression is an analysis error rather than a silent reinterpretation — the property Chapter 15.3 established that Verilog does not provide, where a single unsigned operand silently converts an entire comparison.

This is the constructive half of that finding. 15.3 showed Verilog losing a sign; here VHDL cannot, because the two types are different types and the conversion has to be written. The explicit unsigned(settled(COST_W downto 0)) on the way back is the cost of that guarantee, and it is a fair price.

9. Comparing the Three

10. The Testbenches

The model keeps an unbounded integer ledger and clamps only when reporting — a different method from the design's fixed-width signed expression with saturation, so a width or saturation defect cannot be reproduced by it.

A testbench defect worth recording, because it is the same class as the one 17.1 §9 found. The first version checked reserve_ok after the step that asserted the request:

      step(0,1,i[COST_W-1:0],0,0,0);          // reserve exactly i
      check(reserve_ok === 1'b1, "...");      // WRONG: request already gone

reserve_ok is combinational on reserve_valid, which step() deasserts on the way out — so the check read the deasserted value and failed for every one of a thousand sweep points. The fix samples the decision inside the step, and the lesson is that a combinational output must be observed while its input is applied. Both of this module's testbench defects so far have been about when a value was read, not about what was checked.

The directed sequence covers §3's operations and §4's collision:

  REACH: reservations=1397 rejected=971 settlements=1456 overruns=525
         exact-fits=3 collisions=114

971 rejections and 525 overruns matter as much as the successes: a bench that only ever admitted work would never exercise the "consumes nothing" path or the saturation, and mutations G2 and G6 both live there.

11. Mutation Testing — Across All Three Languages

G4 is the largest at 12 057, which is the point of §2 made numerically: the accounting defect is the most detectable defect here, and it changes no decision at all. Every can_fit answer under G4 is correct; every admission is correct; only the ledger drifts. A bench that checked decisions and not state would score it zero.

G1 is the smallest at 23, and for the reason 16.4 §13 documented at length: an exclusive-versus-inclusive boundary differs only when a cost exactly equals the remaining budget, and that coincidence is rare. The measured run produced 3 exact fits in 6000 randomised cycles. The directed sweep — every cost from 0 to BUDGET against a full frame — is what actually kills it, and without that sweep G1 would be close to a survivor.

12. Assertions

  // A1. SAFETY, the invariant the whole module maintains: the ledger never
  //     exceeds the per-frame allocation.
  property p_never_over_budget;
    @(posedge clk) disable iff (!rst_n)
      (remaining <= BUDGET);
  endproperty
  a_never_over_budget: assert property (p_never_over_budget);

  // A2. SAFETY: a rejected reservation consumes NOTHING. There is no partial
  //     admission -- this is mutation G2's inverse.
  property p_reject_consumes_nothing;
    @(posedge clk) disable iff (!rst_n || bus_reset)
      (reserve_valid && !reserve_ok && !frame_tick && !settle_valid)
        |=> $stable(remaining);
  endproperty
  a_reject_consumes_nothing: assert property (p_reject_consumes_nothing);

  // A3. SAFETY: an accepted reservation moves the ledger by EXACTLY the
  //     estimate. An equality, so it catches both a missing deduction and a
  //     deduction of the wrong amount.
  property p_reserve_moves_by_estimate;
    @(posedge clk) disable iff (!rst_n || bus_reset)
      (reserve_ok && !frame_tick && !settle_valid)
        |=> (remaining == $past(remaining) - $past(reserve_est));
  endproperty
  a_reserve_moves_by_estimate: assert property (p_reserve_moves_by_estimate);

  // A4. ACCOUNTING, §2, and the property mutation G4 violates: a settlement
  //     moves the ledger by (estimate - ACTUAL), never by zero.
  property p_settle_uses_actual;
    @(posedge clk) disable iff (!rst_n || bus_reset)
      (settle_valid && !frame_tick && !underflow_obs)
        |=> (remaining == $past(remaining) + $past(settle_est)
                                           - $past(settle_act));
  endproperty
  a_settle_uses_actual: assert property (p_settle_uses_actual);

  // A5. SAFETY: the overrun flag is sticky -- it never falls except through
  //     a reset. An over-committed frame is a fact about the configuration.
  property p_overrun_sticky;
    @(posedge clk) disable iff (!rst_n || bus_reset)
      $fell(overrun) |-> 1'b0;
  endproperty
  a_overrun_sticky: assert property (p_overrun_sticky);

  // A6. PROGRESS: a frame boundary always restores the budget. A ledger that
  //     never refreshed would satisfy A1..A5 perfectly and would stop the
  //     bus after one frame's worth of work.
  property p_boundary_refreshes;
    @(posedge clk) disable iff (!rst_n || bus_reset)
      (frame_tick && !reserve_valid) |=> (remaining == BUDGET);
  endproperty
  a_boundary_refreshes: assert property (p_boundary_refreshes);

Assertion contracts

A6 is the only progress property and §47's argument applies unchanged. A ledger that never refreshed would satisfy A1 through A5 perfectly — it would never exceed the allocation, never move on a rejection, move correctly on reservations and settlements, and keep a sticky flag sticky. It would also fill up once and refuse everything for ever.

A3 and A4 are deliberately equalities rather than inequalities. The ledger decreased is true of a design that deducted the wrong amount; the ledger decreased by exactly the estimate is not. G4 is precisely a settlement that moves the ledger by the wrong amount — zero instead of est − act — and only an equality catches it.

13. Verification: a Ledger Is Not a Scenario Space

Chapter 17.3 made the case for UVM and this chapter does not inherit it.

The state is one number and one flag. The operations are four, their precedence is fixed, and the interesting cases are the boundary collision, the exact fit, the saturation and the sticky flag — four directed tests, not a distribution.

What §11 shows is that the directed work carried this chapter. G1 was nearly a survivor until the sweep over every cost from 0 to BUDGET was added; 3 exact fits in 6000 random cycles was never going to be enough. Constrained-random would have had the same problem — an exact-equality boundary is not something a solver finds unless it is told to.

Where this block belongs in a UVM environment is as a component of 17.3's, supplying can_fit to the arbiter while the scoreboard checks both the grant and the ledger. That is the environment worth building, and the coverage bin it needs from here is budget_region { empty, linear, exact, full, overrun } — because §11's G1 result is exactly the exact bin being nearly unvisited.

14. Debugging: the Frame That Reports Space It Does Not Have

A controller admits transactions normally for a while. Over minutes, it begins deferring work that should fit — the frame reports a few hundred nanoseconds free and refuses a transaction that needs less than that. No overrun is flagged. Resetting the controller clears it, and it recurs.

"Refuses work that should fit" with no overrun is an accounting symptom, not a mechanism symptom — and §2 predicts it exactly. The decision logic is working: it is comparing correctly against a number that has drifted.

The chain:

Is the ledger drifting, or is the cost estimate wrong? Sum the estimates of everything admitted in one frame and compare against BUDGET − remaining. If they disagree, the ledger is wrong; if they agree, the estimates are. That one comparison separates a 17.4 defect from a 16.4 defect.

Does the drift accumulate per transaction or per frame? Per transaction points at the settlement (§2): an actual cost that is never applied, or applied as the estimate — mutation G4. Per frame points at the refresh: a boundary that does not fully restore, or a reservation charged to the wrong frame — mutation G3.

Does remaining ever exceed BUDGET? A1. If it does, a settlement returned more than it took, and the estimate/actual pair are mismatched rather than the arithmetic being wrong.

Is overrun ever set? If the frame is genuinely over-committed the flag says so and the fault is upstream, in admission. If the flag is clear and work is being refused, the ledger is lying — and G4 is the first mutation to check against.

The first divergence. Run the bench's independent integer ledger alongside the design's and compare at every operation. The first operation where they differ names the defect: a refresh, a reservation, or a settlement.

15. Common Misconceptions

"Bandwidth allocation is the same as bandwidth reservation." 16.4 decides whether an endpoint may exist; this decides whether a transaction may go now (§1). Different question, different state, different failure.

"One cost per transaction is enough." There are two (§2), and using the estimate for both keeps a wrong ledger while making correct decisions — 12 057 failures (§11).

"If the decisions are right, the scheduler is right." G4 changes no decision at all and is the most detectable mutation in the chapter.

"A rejected transaction can safely deduct and be refunded later." It must consume nothing (§3). There is no partial admission, and G2 costs 8613 failures.

"The budget can wrap — it'll be refreshed next frame anyway." A wrapped budget reports a full frame as empty (§4) and admits more work into a frame already over-committed.

"An overrun flag should clear when the next frame refreshes." The budget refreshes; the fact that a frame was over-committed does not stop being true (§3). G5 costs 3855 failures.

"The exact-fit boundary is a corner case not worth testing." §11: 3 exact fits in 6000 random cycles, and G1 is nearly a survivor without the directed sweep.

16. Exercises

1. A frame has 4000 ns remaining. Three transactions are admitted with estimates of 1200, 1500 and 1300 ns. The first actually costs 1100, the second 1700, the third 1300. Work out the ledger after each reservation and each settlement, and say whether the frame overran.

2. §4 charges a boundary-collision reservation to the new frame. Work out what the other policy produces for the sequence in exercise 1 if the third reservation lands on a boundary, and say which policy you would ship.

3. Implement separate ledgers for periodic and opportunistic work, with the periodic cap at 80% of the frame. Determine what can_fit must become and how many bits the arbiter of 17.3 now needs.

4. Mutation G4 changes no decision. Write a testbench that checks only can_fit and reserve_ok — no ledger comparison — and confirm G4 scores zero against it. Then state the general rule.

5. §11 shows G1 nearly survives without the directed sweep. Compute how many random cycles would be needed to hit the exact-equality boundary 20 times at the measured rate, and say whether that is a reasonable regression.

6. Add support for two transactions in flight. Decide what settle_est must now identify, and what breaks if settlements can complete out of order.

17. Summary

can_fit is not a constant (§0). It is a function of everything already committed to the frame, refreshed at every boundary — so the arbiter's answer late in a frame depends on decisions it made early in the same frame.

This is not 16.4 (§1). That chapter decided whether an endpoint may hold a reservation at all, once, at configuration time. This one spends the reservation, every frame, transaction by transaction.

A scheduler has two numbers for every transaction (§2): the estimate, known before and used to decide, and the actual, known after and used to correct. Using one for both makes every decision correctly and keeps a wrong ledger — and §11 measures that at 12 057 failures, the largest in the chapter, on a mutation that changes no decision at all.

The boundary collision must be stated, not inherited from branch order (§4). This design charges a reservation arriving at a boundary to the new frame; the other choice costs 1170 failures and is equally defensible if declared.

The budget saturates at zero (§4), for the third time in two modules and the same reason each time: a wrapped counter reports a full frame as empty, which is the direction that admits still more work.

All three HDL implementations were simulated (§18), and six mutations died in all three (§11). G1 — the exclusive fit boundary — is the smallest at 23, and would be near-survivor without the directed sweep over every cost from 0 to BUDGET: the measured run produced 3 exact fits in 6000 randomised cycles.

And a testbench defect of the same class as 17.1's (§10): a combinational output checked after its input had been deasserted. Both of this module's bench defects so far have been about when a value was read.

18. Tooling, Honestly

19. What Comes Next

Three questions are now answered. 17.3 chose who. This chapter checked whether the work fits the frame's allocation. 17.1 and 17.2 built the opportunities themselves.

One question is left, and it is physical rather than arithmetic.

A transaction that fits the budget may still not fit the time remaining. Budget is an allocation — a quantity of frame time reserved for a class of work. Placement is about where in the frame the transaction actually lands, and a transaction started too close to the boundary is still on the wire when the boundary arrives.

Chapter 17.5 is that last check: the guard band the host keeps at the end of every frame, what happens to a transaction refused by it, and what it means when one runs past the end anyway.

Browse the full path on the USB tutorials index.