H3.5 Arbiter Mutation Regression

ExpertFixVerilator · serverReview the topic

Fix two arbiter checkers that run side by side: one loses count of reset owners, one forgets a broken premise.

Hardware context: Round-robin arbiter with accepted-grant priority updates. Expose starvation, priority wrap and illegitimate grants across requester counts.

A regression runs two checkers on the same arbiter. On a correct arbiter both should stay silent, and their counts should balance. They do not. Each checker has one bug.

grant_retention_checker checks every offer, receipt and lock against the arbiter rules. Its counts must balance: every retained client ends exactly once. service_fairness_checker checks that waiting clients are served in time. Its edge deadline holds only while transfers keep coming.

The tests call both checkers on every edge of the same arbiter. They use N = 1, 2, 3, 5 and 8, a correct arbiter, and many faulty ones. They check the fairness report after every edge, and both final reports.

Find the two bugs, one in each class, and fix them. The full rules are in the specification. Grant Retention Under Backpressure and Bounded Service Fairness explain each checker on its own.

Signals in the Timeline

SignalWidthRole
clients4input of each check
maximum_interval3input of each check
hardware_fault4input of each check
Full specification
CheckerIts rules
grant_retention_checkerThe first part below: the arbiter rules, the 12 compared fields and the report.
service_fairness_checkerThe second part below: waits, ages, the progress premise and the report.
The class (keep these names and types)
class grant_retention_checker;
  function new(input int clients, initial_priority);
  function void sample(input int cycle, input bit reset, ready, input bit [7:0] requests,
                       input int pre_pointer, input bit pre_locked, input bit [7:0] pre_owner,
                       input bit valid, input bit [7:0] grant, winner,
                       input bit accepted, input bit [7:0] accepted_client, input bit canceled,
                       input int post_pointer, input bit post_locked, input bit [7:0] post_owner);
  function string report();
endclass
RuleWhat the arbiter does
ClientsN is the number of clients. Clients are 0 to N - 1. Request bits at N and above are ignored.
Fresh choiceWith no retained client, scan the clients in circular order, starting at priority_state. The first one that requests is offered.
Offervalid = 1, winner = the client and grant = its one-hot bit. With no offer, valid = 0, winner = 0xff and grant = 0.
TransferA transfer happens at an edge with reset = 0, valid = 1 and ready = 1. priority_state then becomes winner + 1, wrapping to 0 after N - 1.
StallAt an edge with valid = 1 and ready = 0, the offered client becomes the retained client. priority_state does not move.
Retained offerWhile the retained client keeps requesting, it stays offered. Requests from other clients cannot take its place.
WithdrawalIf the retained client drops its request, the offer is idle for that whole cycle. This holds even when others request and ready = 1.
After a withdrawalAt that edge canceled = 1 and the retained client is released. priority_state does not move. A fresh choice starts in the next cycle.
Resetreset is synchronous and active high. While it is 1 the offer is idle. Its edge accepts nothing, sets priority_state to 0 and releases the retained client.
Receiptsaccepted and accepted_client describe the transfer at the last edge. accepted_client is 0xff when there was none. Reset clears both, and canceled stays 0.
Lock registerslocked and locked_client show the retained client. With none, locked = 0 and locked_client = 0xff.

Each sample() call describes one edge. Check the old state against your model first. Then predict the edge, check the offer and receipts, and update your model. Check the new state last.

BitFieldCompares
0PREPpriority_state before the edge
1PRELOCKlocked before the edge
2PREOWNERlocked_client before the edge
3VALIDvalid of the offer
4GRANTthe whole grant bitmap
5WINNERwinner of the offer
6ACCEPTaccepted after the edge
7CLIENTaccepted_client after the edge
8CANCELcanceled after the edge
9POSTPpriority_state after the edge
10POSTLOCKlocked after the edge
11POSTOWNERlocked_client after the edge

Your model follows the rules, never the hardware. It must not copy the pointer or the lock from the pins, even after a mismatch. Keep checking after errors and through resets.

Report itemMeaning
FIRSTThe first mismatch, as FIELD@cycle:expected>actual with both values in 8 hex digits. Within one edge, the lowest bit wins. OK when there is none.
MASKAll field bits that ever failed, in 3 hex digits.
BADThe number of edges with at least one mismatch.
ATransfers your model predicts.
SEENEdges where the accepted pin was 1.
MATCHPredicted transfers where the pin was 1 and accepted_client was right.
OPENRetained clients started: the first stalled edge of a fresh offer. A transfer with no stall opens nothing.
RETRetained clients that ended in a transfer.
WITHDRAWRetained clients that ended by withdrawal.
RESET_CANCELRetained clients that ended by reset.
RESETSReset edges.
PYour predicted priority_state after the last edge.
OWNERYour predicted retained client in 2 hex digits, or ff.

The report joins the items with |, as FIRST=OK|MASK=000|... in the order above. Every retained client ends exactly once, so OPEN = RET + WITHDRAW + RESET_CANCEL, plus 1 if one is still retained.

Faulty arbiterWhat is wrong
1It makes a fresh choice even while a client is retained.
2The pointer moves on a stalled offer.
3It keeps offering a retained client that has withdrawn.
4It never retains a stalled offer.
5The pointer wraps to 1 instead of 0, so client 0 is skipped. With N = 1 it behaves correctly.
6The retained client survives reset.
7grant also has a bit for every other client that asks.
8The old receipt survives reset.
The class (keep these names and types)
class service_fairness_checker;
  function new(input int clients, maximum_interval);
  function void sample(input int cycle, input bit reset, input bit [7:0] requests,
                       input bit accepted, input bit [7:0] client);
  function string report();
endclass

N is 1, 2, 3, 5 or 8, and G = maximum_interval is 1 to 4. sample() gets the requests and the receipts read 1 ns after each edge. client is the accepted client.

RuleMeaning
WaitA client below N that asks has an open wait. The wait ends when it is served or stops asking. Reset ends every wait.
grant_ageTransfers to other clients during the wait. Only edges with accepted = 1 count. Stalls do not.
cycle_ageEdges in the wait, including the current one. On the first edge of a wait it is 1.
Own serviceWhen the client itself transfers, both ages clear before any check. Service on the last allowed edge is on time.
GRANT errorgrant_age reaches N. Report it once per wait.
GAPNon-reset edges in a row where some client asks and nothing transfers. An edge with no requests, or with a transfer, sets GAP to 0.
ENV errorGAP reaches G = maximum_interval. Report ENV and set QUAL to 0. Only reset sets QUAL back to 1.
CYCLE errorWhile QUAL = 1, cycle_age reaches N × G. Report it once per wait.
Order in one edgeUpdate GAP and check ENV first. Then count the transfer. Then go through clients 0 to N - 1, with GRANT before CYCLE.
ResetClears all ages, the once-per-wait flags and GAP, and sets QUAL to 1. FIRST, MASK, BAD, the error counts and SERVICE stay.

Why N × G: a round robin serves a waiting client within N transfers. If a transfer comes at least every G edges, the client waits at most N × G edges. Without that premise, a wall-clock deadline proves nothing.

Report itemMeaning
FIRSTThe first error, as ENV@cycle, GRANT@cycle:client or CYCLE@cycle:client. OK when there is none.
MASKENV adds 1, GRANT adds 2 and CYCLE adds 4, in decimal.
BADEdges with at least one new error.
QUAL1 while the progress premise holds, 0 after an ENV error.
GAPThe current GAP.
AEdges where the accepted pin was 1.
ENV, GRANT, CYCLEHow many of each error were reported.
WAITgrant_age/cycle_age for clients 0 to N - 1, separated by commas.
SERVICETransfers each client received over the whole run, separated by commas.

The report joins the items with |, as FIRST=OK|MASK=0|... in the order above.

Faulty arbiterWhat is wrong
5The pointer wraps to 1 instead of 0, so client 0 is skipped. With N = 1 it behaves correctly.
9The pointer returns to 0 after every transfer, so it acts as a fixed-priority arbiter.

Inputs are steady 1 ns before each rising edge. The tests read the offer and the old state just before the edge. They read the receipts and the new state 1 ns after it.

The line the tests compare
PREFIX=<edges where a fairness report was wrong>|<final fairness report>|TRACE=<the arbiter trace>|SAFETY=<final retention report>

The traces mix both families: steady traffic with stalls, and random traffic with withdrawals and resets. Each checker must keep working when the other one reports an error.

The result compares this line with the expected text, character by character. It shows both lengths and whether the two lines match. On a mismatch the log prints your line.

Examples

Example 1

Both Checkers Clean on the Deadline
Input
N = 3, G = 2, priority 1, correct arbiter. All clients ask for 8 edges, with ready = 1 on odd edges.
Output
your_line_length = 1712, expected_line_length = 1712, lines_match = yes

Client 0 is served on edge 5, exactly N × G edges into its wait, so there is no fairness error. Each of the 4 transfers follows a stall, so OPEN=4 and RET=4.

Example 2

Starvation with Steady Progress
Input
The same traffic with faulty arbiter 5, which skips client 0
Output
your_line_length = 1743, expected_line_length = 1743, lines_match = yes

The fairness report shows GRANT@5:0 first, with QUAL still 1. The retention report also fails, first at POSTP@3, because the pointer wraps to 1 instead of 0.

Example 3

A Stalled Receiver Breaks the Premise
Input
N = 3, G = 2, correct arbiter. All clients ask for 8 edges with ready = 0, then nobody asks.
Output
your_line_length = 1715, expected_line_length = 1715, lines_match = yes

ENV is reported on edge 1, and QUAL stays 0. The retention report is clean: one retained client opens and later ends by withdrawal, so OPEN=1 and WITHDRAW=1.

Constraints and Contract

  • Predict from your own models. Use the pins only for comparison.
  • A clean run on 32 edges shows no violation in that run. It is not a proof of fairness.
  • Keep both class names, the method names and the argument types.

Hints

Hint 1

Run the ledger check by hand on a trace with a reset during a stall. Does OPEN equal RET + WITHDRAW + RESET_CANCEL?

Hint 2

In the fairness checker, find every place that sets QUAL. Which events may set it back to 1?

Hint 3

One bug is in the reset branch of grant_retention_checker.sample(): it forgets to count the cancelled owner. The other sets qualified = 1 on a transfer.

What the grader checks: Both checkers watch the same real arbiters, one correct and many with distinct faults. Every fairness report after every edge and the final retention report are compared. A finite run is not a proof of fairness.

111 checks on Verilator · server. Run the examples first, then check the full regression. Full checks use the server judge. Downloads contain public samples only. A passing result establishes the tested cases, not a proof for all possible inputs.

See all 8 steps and the final capstone

Report a problem with this page

Your code SystemVerilogSaved locally
Ln 1, Col 1Tab indents · Ctrl/⌘ + Enter runs samples
Not run yet

Both Checkers Clean on the Deadline

Input
N = 3, G = 2, priority 1, correct arbiter. All clients ask for 8 edges, with ready = 1 on odd edges.
Expected output
your_line_length = 1712, expected_line_length = 1712, lines_match = yes

Client 0 is served on edge 5, exactly N × G edges into its wait, so there is no fairness error. Each of the 4 transfers follows a stall, so OPEN=4 and RET=4.

Run samples executes all 3 public checks. Check all tests runs 111 checks on the server.

Verilator · server