Fix a descriptor-chain model that copies the same block again and again when a chain loops back on itself.
Hardware context: Memory-to-memory DMA with owned descriptors and bounded bus bursts. Walk a finite scatter/gather descriptor chain and reject invalid links.
A DMA engine follows a chain of descriptors. Software made a mistake and pointed a descriptor back at itself. The reference model then copied the same block eight times before it reported the loop.
The function descriptor_walk models the engine on a memory of 128 bytes. Eight slots each describe one copy and name the next slot. The walk starts at start_index, checks each slot, copies its bytes and moves on. It stops at the end of the chain or at the first error.
The tests run 38 chains: valid chains, self-loops, longer loops, bad pointers, invalid slots, copies past the end and overlapping copies. The whole report, including every memory byte, is compared.
Find the bug and fix it.
Signals in the Timeline
| Signal | Width | Role |
|---|---|---|
start_index | 8 | input of each check |
descriptor_count | 4 | input of each check |
Full specification
function automatic string descriptor_walk(input logic [511:0] descriptors, input int start_index);
| Bits of a slot | Holds |
|---|---|
| 7:0 | Source byte address. |
| 15:8 | Destination byte address. |
| 23:16 | Length in bytes. |
| 31:24 | Next slot. 255 ends the chain. |
| 32 | Valid bit. |
| 63:33 | Always 0. |
| Error | Checked in this order for the current slot |
|---|---|
| 1, pointer | The slot number is not 0 to 7. |
| 2, loop | This slot already ran in this walk. |
| 3, invalid | The valid bit is 0. |
| 4, bounds | The length is above 32, or source + length or destination + length is above 128. |
| 5, overlap | The length is above 0 and the two ranges overlap. |
Slot k sits in bits 64k + 63 down to 64k of descriptors. Memory has 128 bytes.
The walk stops at the first failed check. A failed slot copies nothing. Copies made before it stay made.
A slot that passes copies its bytes in address order, then the walk moves to its next slot. A later slot may read bytes that an earlier slot wrote.
After eight slots have run, the walk stops. If the next slot is not 255, it reports error 1 for a number outside 0 to 7 and error 2 otherwise.
Memory byte a starts as (17 × a + 0x5a) mod 256. So byte 0 is 0x5a, byte 1 is 0x6b and byte 64 is 0x9a.
Each slot that runs adds slot:source>destination/length; in decimal, for example 0:0>64/4;. Then comes E=error|NODE=slot|DONE=count|BYTES=total|MEM=. After it come all 128 bytes as two hex digits each, address 0 first. NODE is the slot where the walk stopped, or 255 after a clean end.
The whole report string is compared with the expected one. The result shows the length of your report, the expected length and whether the two match.
Examples
Example 1
Two Chained Copies- Input
start 0. Slot 0 copies 4 bytes from 0 to 64, next 1. Slot 1 copies 4 bytes from 64 to 80, next 255.
- Output
report_length = 307, expected_length = 307, match = yes
Slot 1 reads the bytes that slot 0 just wrote, so bytes 80 to 83 become 5a 6b 7c 8d. The report starts 0:0>64/4;1:64>80/4;E=0|NODE=255|DONE=2|BYTES=8.
Example 2
A Self-Loop- Input
start 0. Slot 0 copies 4 bytes from 0 to 64, next 0.
- Output
report_length = 295, expected_length = 295, match = yes
Slot 0 runs once. When the walk comes back to slot 0, it stops with error 2. The report starts 0:0>64/4;E=2|NODE=0|DONE=1|BYTES=4.
Example 3
A Copy Past the End- Input
start 0. Slot 0 copies 16 bytes from 120 to 64, next 255.
- Output
report_length = 286, expected_length = 286, match = yes
Bytes 120 to 135 do not fit in 128 bytes. The walk stops with error 4 before it copies anything. The report starts E=4|NODE=0|DONE=0|BYTES=0, and memory is unchanged.
Example 4
A Pointer to an Empty Slot- Input
start 0. Slot 0 copies 4 bytes from 0 to 64, next 7. Slot 7 is all zeros.
- Output
report_length = 295, expected_length = 295, match = yes
Slot 0 runs. Slot 7 has its valid bit clear, so the walk stops with error 3. The copy from slot 0 stays. The report starts 0:0>64/4;E=3|NODE=7|DONE=1|BYTES=4.
Example 5
Eight Slots and a Bad Pointer- Input
start 0. Slot k copies 4 bytes from 4k to 64 + 4k and points to slot k + 1. Slot 7 points to 9.
- Output
report_length = 364, expected_length = 364, match = yes
All eight slots run and copy 32 bytes in all. Slot 9 does not exist, so the report shows E=1|NODE=9|DONE=8|BYTES=32.
Constraints and Contract
- A loop is about slots, not addresses. Two slots may copy the same bytes without forming a loop.
- Keep the function name, its arguments and the return type.
Hints
Hint 1
A chain can come back to any slot that already ran, including itself. What must the walk remember to notice that?
Hint 2
Trace the second example. Slot 0 points to slot 0. How many times may it run? What must the report say after that?
Hint 3
The walk sets seen[node] after each copy, but nothing reads it. Right after the pointer check, stop with error 2 when seen[node] is set.
What the grader checks: The tests run 38 chains with every error type and loops of many lengths. They compare the list of copies and all 128 memory bytes. Passing shows that the model follows these chains, not that a hardware engine fetches descriptors correctly.
38 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