H10.2 Scatter/gather Descriptor Walk

MediumFixVerilator · serverReview the topic

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

SignalWidthRole
start_index8input of each check
descriptor_count4input of each check
Full specification
The function (keep its signature)
function automatic string descriptor_walk(input logic [511:0] descriptors, input int start_index);
Bits of a slotHolds
7:0Source byte address.
15:8Destination byte address.
23:16Length in bytes.
31:24Next slot. 255 ends the chain.
32Valid bit.
63:33Always 0.
ErrorChecked in this order for the current slot
1, pointerThe slot number is not 0 to 7.
2, loopThis slot already ran in this walk.
3, invalidThe valid bit is 0.
4, boundsThe length is above 32, or source + length or destination + length is above 128.
5, overlapThe 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

Report a problem with this page

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

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.
Expected 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.

Run samples executes all 5 public checks. Check all tests runs 38 checks on the server.

Verilator · server