xv6-riscv revision 5 uses an eight-entry Virtio split queue. Each block request consumes a chain of three direct descriptors: command header, data buffer, and one-byte status. At most two requests can hold complete chains simultaneously because a third chain would require nine descriptors. The Virtio indirect-descriptor feature can represent those three elements behind one main-ring descriptor, raising the queue’s descriptor-limited ceiling from two requests to eight when the device offers the feature.
The implementation target is not “make the benchmark number larger.” The target is a driver whose feature negotiation, publication order, request lifetime, completion validation, fault behavior, and measurements can be defended from traces.
This is an original LibreUni lab. It uses the licensed upstream teaching kernel and the public Virtio specification; it does not reproduce another course’s assignment or solution.
Implementation contract
Maintain a repository branch with the pinned upstream commit as a verified ancestor, plus generated evidence outside the source diff. Learners studying the operating systems sequence cumulatively retain earlier labs; independent learners may start directly from the pinned baseline.
- the driver and minimal, non-conflicting syscall/user-test support needed by the design, preserving earlier cumulative interfaces;
- a test manifest mapping each invariant to an oracle and named mutant;
- raw measurement output and a script or exact command sequence that reproduces every table;
- a design memo of 1,500–2,500 words;
- a driver-lab patch-range diff against the recorded lab-start commit, plus the ancestry evidence back to the pinned baseline; and
- a diagnostic self-verification trace with the code and execution logs available.
A diff that cannot be built from the declared commit is invalid. Performance claims are meaningless until correctness invariants pass. The 720-minute workload is a planning estimate, not permission to stop with an unverified state.
Non-negotiable invariants
Label these I1–I10 in the memo and cite the code and test that establish each one.
| ID | Invariant |
|---|---|
| I1 | A feature is used only if the device offered it and the driver accepted it before FEATURES_OK. |
| I2 | One request owns either one indirect head descriptor or one complete direct chain, never a partial mixture. |
| I3 | Descriptor contents and the available-ring slot become device-visible before the published available index. |
| I4 | The data-buffer direction bit matches the operation: device-writable for reads, device-readable for writes. |
| I5 | 0 ≤ in_flight ≤ negotiated_queue_capacity; full/empty remains correct across 16-bit index wrap. |
| I6 | A used-ring ID is bounds-checked before indexing driver metadata. |
| I7 | A request transitions to terminal state once; duplicate completion before reap is detected, not completed twice. |
| I8 | Completion state and status become visible before a waiter is woken; waiters recheck a predicate in a loop. |
| I9 | A descriptor, indirect table, status byte, and data buffer are not reused until device ownership ended and the waiter/reaper transferred ownership. |
| I10 | Timeout or process death does not imply device cancellation; no timed-out buffer is reused without specified quiescence/reset evidence. |
Defense boundary. Standard split-ring used entries return a descriptor-chain head ID, not the driver’s private generation counter. A software generation detects many lifecycle defects, but it cannot distinguish a malicious stale completion that arrives after the same head ID has been legitimately reused unless the protocol returns equivalent identity. Safety after reset therefore depends on verified device/queue quiescence, not generation numbers alone.
Retrieval — before opening source. Explain why eight main-ring entries permit only two baseline requests but as many as eight indirect requests. State the resource that still may reduce observed concurrency below eight.
Reveal the diagnostic answerExpandCollapse
Baseline requests each require three direct descriptors, so floor(8/3)=2 complete chains fit. An indirect request consumes one main descriptor that points to its private three-entry indirect table, so eight heads can fit if all other resources are available. Buffer-cache locking, process scheduling, available workload, device service time, and driver metadata can reduce observed concurrency; eight is a descriptor-capacity ceiling, not a throughput promise.
Pin and verify the baseline
The required baseline is the official tag xv6-riscv-rev5, commit 7d7adbb1b0acbd67c9766a20d0f9900fef2789fa. Preserve its LICENSE and upstream notices. Do not reset a cumulative branch to this commit: verify ancestry, record the reviewed exit commit from the preceding lab as the driver-lab start, and branch from that state.
Standalone setup only:
git clone https://github.com/mit-pdos/xv6-riscv.git libreuni-xv6-driver
cd libreuni-xv6-driver
git checkout 7d7adbb1b0acbd67c9766a20d0f9900fef2789fa
git switch -c libreuni/virtio-indirect-lifecycle
git rev-parse HEAD
make qemu
For a cumulative branch, run the following from the accepted prior-lab state instead of cloning again:
git merge-base --is-ancestor 7d7adbb1b0acbd67c9766a20d0f9900fef2789fa HEAD
git merge-base HEAD 7d7adbb1b0acbd67c9766a20d0f9900fef2789fa
git rev-parse HEAD
git switch -c libreuni/virtio-indirect-lifecycle
The first command must exit zero; the second must print the pinned baseline; the third is the lab-start commit to preserve in the implementation record. In standalone setup, rev-parse instead prints the baseline itself. The revision-5 Makefile requires a RISC-V toolchain and QEMU 7.2 or newer. Capture regression evidence before changing the driver; on a cumulative branch, this also proves the earlier labs still build and run:
$ usertests -q
$ stressfs
Save command output before editing. If the baseline fails, repair the environment rather than changing kernel code to hide the failure.
Read the path as one protocol
Inspect these files and record the named state each contributes:
| File | Required observation |
|---|---|
kernel/bio.c, kernel/buf.h | buffer lock, valid, disk, and caller ownership |
kernel/virtio_disk.c | feature negotiation, descriptor allocation, publication, wait, completion, free |
kernel/virtio.h | register offsets, queue layouts, flags, NUM=8 |
kernel/trap.c, kernel/plic.c | external-interrupt claim, dispatch, acknowledgment, PLIC completion |
kernel/riscv.h | memory-order primitive and r_time() source |
kernel/syscall.c, kernel/sysproc.c, user/user.h, user/usys.pl | test-only control/stat syscall path |
Makefile | kernel/user objects, programs, CPU count, QEMU invocation |
The baseline worked trace of a single block request is:
Baseline evidence checkpoint
Add temporary trace points or use GDB to capture one read and one write. The trace must identify:
- all three descriptor indices and flags;
- sector and block-number relation;
avail.idxbefore/after publication;used_idxand deviceused->idxat completion;- the interrupting hart;
b->diskbefore sleep and before wake; and- the point at which each descriptor becomes free.
Remove ad hoc print flooding before the final patch. The permanent trace facility is bounded and structured.
Reveal the baseline trace verification criteriaExpandCollapse
A complete derivation requires a causally ordered trace, not a list of function names. A read’s data descriptor has VRING_DESC_F_WRITE because the device writes into memory; a write’s data descriptor lacks that flag because the device reads memory. The request head is the first descriptor ID placed in the available ring and later returned in the used ring. Descriptor reclamation occurs in the waiting thread after completion wakes it in revision 5.
Virtio descriptor flags and queue invariants
Evaluate each statement regarding Virtio descriptor flags, queue operations, and buffer directions in xv6:
Classify each option as correct or incorrect, or leave uncertain options unanswered (“I don't know”) and verify at any time.
Milestone A — isolate negotiation from queue layout
The baseline explicitly clears VIRTIO_RING_F_INDIRECT_DESC from the offered feature word. Refactor feature selection into a small testable decision whose output records whether indirect descriptors were accepted. Requirements:
- read offered features;
- reject features the driver does not implement;
- retain
VIRTIO_RING_F_INDIRECT_DESConly when the indirect path is compiled and offered; - write the accepted set;
- set
FEATURES_OKand re-read status as the baseline does; and - select direct fallback if the feature is absent.
The test harness must call the pure decision logic with synthetic feature words. Do not depend on undocumented QEMU command-line properties to simulate absence.
Interface sketch, not a solution
struct vdisk_features {
uint32_t accepted;
int indirect;
};
// Pure decision: no MMIO inside this function.
struct vdisk_features choose_vdisk_features(uint32_t offered,
int indirect_build_enabled);
Tests must cover offered+enabled, offered+disabled, absent+enabled, and unknown offered bits. The MMIO initialization code remains responsible for status transitions.
Application — reject force-indirect. A mutant sets VRING_DESC_F_INDIRECT in descriptors whenever the build supports it, even when the device did not offer the feature. Which invariant fails before the first request, and what deterministic unit input exposes it?
Reveal the oracleExpandCollapse
I1 fails. Call the decision function with an offered word whose indirect bit is clear and build support enabled. The result must select direct fallback and must not set the indirect bit in accepted. A test that boots only one default QEMU instance may never exercise this case.
Milestone B — implement one-head indirect requests
Add VRING_DESC_F_INDIRECT using the value defined by the Virtio specification. For each main descriptor slot, provide a persistent, device-visible, suitably aligned three-entry indirect table. It cannot live on a stack that disappears while the device owns it.
The indirect entries describe:
| Indirect entry | Buffer | Device direction |
|---|---|---|
| 0 | struct virtio_blk_req | device reads |
| 1 | b->data | device writes for block read; device reads for block write |
| 2 | one-byte status | device writes |
The main descriptor points to the indirect table, has length 3 × sizeof(struct virtq_desc), and sets VRING_DESC_F_INDIRECT. It must not also chain direct descriptors with NEXT. The used-ring ID remains the main descriptor index.
The xv6 kernel directly maps the relevant physical RAM, but the memo must still justify why each address given to the device is a valid DMA address in this teaching machine. “The C pointer compiled” is not evidence.
Request resource model
Define resource acquisition as one transaction:
reserve head slot
reserve per-head request metadata and indirect table
initialize command, data, and status entries
publish exactly one head
If any required resource is unavailable, release everything acquired in that attempt before sleeping/retrying. Partial descriptor ownership is forbidden by I2.
Direct fallback remains first-class
Do not delete the direct-chain implementation. Factor common command/status setup while retaining two publication shapes. Both must satisfy the same lifecycle, status, wait, and trace interfaces. Run correctness and fault tests in both modes.
Application — direction audit. For an xv6 bread, write the flags for all three indirect entries. Repeat for bwrite. Explain the flag name from the device’s perspective.
Reveal the flag auditExpandCollapse
Entry 0 is device-readable and chains to entry 1. For bread, entry 1 sets device-write plus next because the device fills b->data; for bwrite, entry 1 sets next without device-write because the device consumes b->data. Entry 2 sets device-write because the device writes status. The main indirect descriptor uses the indirect flag and no direct-chain next flag.
Milestone C — make request lifetime explicit
Replace implicit combinations of free[], info[].b, status, and b->disk with one auditable lifecycle. The exact enum names may differ, but every transition needs a lock, actor, and test.
State PUBLISHED is the device-ownership boundary. Rollback from it is prohibited without a device-defined cancel/reset/quiesce operation. A timeout may mark diagnostic state, stop admission, or fail-stop the teaching kernel; it may not transition directly to FREE.
Metadata sketch
enum req_state { REQ_FREE, REQ_RESERVED, REQ_BUILT,
REQ_PUBLISHED, REQ_COMPLETED, REQ_REAPED };
struct req_meta {
enum req_state state;
uint32_t generation;
struct buf *buffer;
uint64_t submit_time;
uint64_t complete_time;
unsigned char status;
};
This sketch is not a full implementation. Decide which fields are device-written, which lock protects transitions, when generation advances, and whether timing reads occur inside or outside the lock. Do not expose kernel pointers through a user-visible stats syscall.
Completion validation order
The interrupt path must establish, in order:
- interrupt status belongs to the device and is acknowledged as specified;
- used-ring writes are visible before entries are consumed;
id < NUMbefore anyinfo[id]access;- request state is
PUBLISHED; - status is success before the buffer is declared valid to the caller;
- state becomes
COMPLETEDandb->diskbecomes false under the protocol lock; - waiters are woken after the predicate transition; and
used_idxadvances exactly once per consumed used entry.
For an invalid ID, duplicate completion, or error status, a revision-5 teaching kernel may fail-stop with a stable diagnostic rather than implement full filesystem error propagation. It must not index out of bounds, report success, free owned DMA memory, or continue in an unknowable queue state.
Transfer — generation limit. A duplicate used entry for head 3 arrives after head 3 was completed, reaped, incremented to generation 18, and republished. The hardware used entry carries only ID 3. Can private generation=18 prove that this completion belongs to generation 18?
Reveal the protocol boundaryExpandCollapse
No. The standard split-ring used entry does not return the private generation. The driver can detect a duplicate before reuse because state is no longer PUBLISHED, and test hooks can carry synthetic generation metadata, but a post-reuse stale ID is indistinguishable from the current request at this interface. The Virtio device contract and verified reset/quiescence prevent such late completions. Claiming generation alone solves the case overstates the protocol.
Milestone D — publish with a provable happens-before edge
Virtio’s split-ring sequence requires the driver to write descriptor contents and the available-ring entry, execute a suitable memory barrier, then update avail.idx; further ordering applies before notification checks/doorbells. Preserve the baseline’s architecture-appropriate synchronization or replace it only with an equally justified primitive.
Create a test-only device observer hook at the publication boundary. When enabled, it snapshots the head descriptor, indirect entries, status poison, generation, and ring slot at the instant the driver is about to expose or has exposed avail.idx, according to the tested phase. The hook must verify that:
- every address and length is initialized;
- indirect chaining terminates correctly;
- status begins with a non-success poison value;
- direction flags match operation;
- head/generation metadata agrees with the ring slot; and
- no post-publication mutation occurs before completion.
The hook makes an early-publication mutant deterministic in QEMU, where accidental strong ordering might otherwise hide it. It supplements, rather than replaces, the source-level barrier argument.
Ring-wrap proof obligation
avail.idx and used.idx are 16-bit monotonically increasing counters that wrap naturally. Physical ring slots use % NUM. Do not reduce the stored counters modulo NUM or compare only physical indices for full/empty.
Provide a pure ring arithmetic test that advances at least 65,540 logical submissions/completions without performing 65,540 disk operations. Check occupancy, slot selection, and empty/full transitions across both the eight-entry wrap and the 16-bit counter wrap.
Reveal the wrap oracleExpandCollapse
For unsigned 16-bit producer and consumer counters with at most NUM outstanding, (uint16)(producer - consumer) yields occupancy across natural wrap. The harness should place counters near 65535, submit and complete while never exceeding eight, and compare against a wider reference model. Any implementation that stores only index % 8 cannot distinguish full from empty when the physical indices are equal.
Milestone E — bounded observability without print storms
Add a fixed-size trace ring, for example 256 events, whose writer never allocates or sleeps in interrupt context. Each event should include only what is needed to reconstruct causality:
sequence, r_time, cpu, event,
head, generation, operation, block,
avail_idx, used_idx, in_flight, status
Required event types: reserve, build, publish, sleep, interrupt, complete, wake, reap, rollback, and fault-detected. If the trace overwrites old entries, count drops/overwrites explicitly. Sequence numbers must let the reader detect missing events.
Add a snapshot interface for aggregate statistics:
- submitted/completed reads and writes;
- direct versus indirect submissions;
- descriptor-wait count and accumulated wait time;
- maximum in-flight requests;
- interrupts and completions drained per interrupt;
- request-time histogram or bounded sample sufficient for median/p95;
- error/fault-injection counters; and
- trace-overwrite count.
Copy a consistent snapshot to user space without holding the driver spinlock across copyout. One admissible pattern copies counters to a local kernel struct under the lock, releases the lock, then copies the local snapshot to user memory.
Time units
Use raw r_time() deltas or calibrate them against the revision-5 timer interval. Do not label raw counter differences “nanoseconds” without a verified timebase. QEMU measurements describe the emulator and host run, not physical Virtio hardware.
Application — trace completeness. A trace contains publish(g=7), complete(g=7), and publish(g=8) for head 2, but no reap(g=7) or overwrite marker. Which invariant cannot be audited, even if all file data is correct?
Reveal the missing proofExpandCollapse
I9 cannot be audited: the trace does not show that generation 7’s descriptor/table/buffer ownership returned to the driver before reuse for generation 8. Correct output is insufficient because a timing change could expose early reuse. Either the reap event is missing due to trace loss—which must be marked—or the lifecycle is wrong.
Milestone F — deterministic fault injection
Compile fault controls only in an explicit test build such as VDISK_FAULT_TEST. A normal build must not expose a user-controlled kernel fault surface. A test-only control call should arm one mode for the th matching event, report whether it fired, and reset to a known disabled state at boot.
Required modes:
| Mode | Injection point | Correct observable outcome |
|---|---|---|
SPURIOUS_WAKE | while a request remains PUBLISHED | waiter wakes, rechecks, and sleeps again; no early return |
HOLD_COMPLETIONS | before consuming selected used entries | request resources remain owned; other controller process can release hold |
BAD_USED_ID | completion decoder | stable fail-stop before metadata indexing |
DUPLICATE_PRE_REAP | feed one accepted ID again before reap | duplicate-state detection; no second wake/free/refcount update |
STATUS_ERROR | completion status validation | no success/valid declaration; stable fail-stop or explicit propagated error |
PUBLISH_OBSERVER | descriptor publication boundary | deterministic snapshot proves all fields precede publication |
DESCRIPTOR_PRESSURE | hold completions while many readers submit | submitters block without partial ownership; release drains and wakes |
LATE_AFTER_TIMEOUT | hold request past a diagnostic deadline | timeout never frees/reuses DMA-owned resources |
HOLD_COMPLETIONS needs a separate controlling process because the faulting worker may be asleep. Release must make forward progress without requiring the held worker to run first.
Timeout policy for the core lab
Full Virtio reset is outside the core implementation. When a diagnostic deadline expires, choose one documented safe behavior:
- mark the device failed, stop new submissions, retain all in-flight resources, emit a bounded trace, and fail-stop; or
- retain ownership and wait for the test controller to release the held completion.
Returning an error while freeing the descriptor or buffer is forbidden. Recovery with queue reset is an extension only if it follows the negotiated transport procedure and proves that the device can no longer use old descriptors before release.
Tests must kill named wrong implementations
For each mutant below, include a one-line code transformation, the test that fails, the expected failure, and evidence that the unmutated driver passes. An automated test harness or adversarial reviewer may apply equivalent mutations rather than your exact macro.
| Mutant name | Deliberate defect | Test that must kill it |
|---|---|---|
M_FORCE_INDIRECT | use indirect descriptors when feature absent | synthetic negotiation matrix |
M_PUBLISH_INDEX_FIRST | advance avail.idx before descriptor visibility | publication observer |
M_REVERSE_DIRECTION | invert device-write flag on data entry | known-block read/write checksum test |
M_PARTIAL_RESERVE | keep one descriptor after multi-resource failure | pressure/rollback inventory test |
M_IF_WAIT | replace predicate while with if | spurious wake test |
M_WAKE_BEFORE_STATE | wake before terminal predicate update | controlled wait/interrupt interleaving |
M_TRUST_USED_ID | index info[id] before range check | bad-ID injection |
M_ACCEPT_DUPLICATE | omit PUBLISHED state check | duplicate-pre-reap injection |
M_IGNORE_STATUS | set b->disk=0 on nonzero status | status-error injection |
M_FREE_IN_INTERRUPT | recycle head/table before waiter reaps | hold waiter + pressure + trace check |
M_MODULO_COUNTERS | store only indices modulo eight | pure 16-bit wrap test |
M_TIMEOUT_CANCELS | free a held request when deadline expires | late-after-timeout ownership test |
Required test groups
Upstream regression
Run in direct fallback and indirect modes:
usertests -q
stressfs
grind
usertests -q and stressfs must reach their normal completion markers. Revision-5 grind runs forever by design: drive it from an external harness for a declared duration or progress count, require continued A/B progress with no panic or failure diagnostic, then terminate that QEMU run from the harness. Record the exact command, CPU count, build mode, QEMU version, completion markers for finite tests, and the bound plus termination method for grind. An invented grind exit marker is invalid evidence.
On a cumulative branch, run every earlier lab’s accepted exit suite before and after this driver change. A passing upstream suite cannot substitute for a scheduler or synchronization invariant that the cumulative branch added.
Data integrity
Write deterministic per-block patterns to a temporary file larger than NBUF, wait for every write call to return, close the descriptors, terminate QEMU normally, and reboot the same image before reading/verifying in sequential and permuted block order. Use multiple child processes on disjoint files to create concurrent misses. A checksum mismatch must print file, logical block, expected generation, and observed checksum without dumping arbitrary data. This is a clean-restart integrity test, not a sudden-power-loss durability claim: revision 5 exposes no user-level flush contract for proving the latter.
Deterministic queue pressure
Arm HOLD_COMPLETIONS, launch at least eight disjoint cold reads, wait until the trace proves the queue reached its resource ceiling, release completions, and require every worker to finish with correct data. The direct build should expose its two-request descriptor ceiling; the indirect build should admit more than two and may reach eight. If another subsystem limits it, report that trace rather than fabricating a result.
Fault isolation
Run each fail-stop injection in a fresh throwaway fs.img/QEMU process. Match a stable diagnostic and verify that no later success marker appears. Rebuild the image for the next destructive case. Do not infer safety from a hung emulator.
Wrap and lifecycle unit tests
Exercise pure negotiation/ring functions without device I/O. Check every legal state edge and reject every illegal edge. Advance the reference counter across 65,535 and compare against a wider oracle.
Test-oracle table
Your manifest must have this form:
| Test | Precondition | Trigger | Observable oracle | Mutant killed |
|---|---|---|---|---|
vdisk_spurious_wake | one worker asleep in PUBLISHED | wake without completion | no return; later real completion returns once | M_IF_WAIT |
vdisk_bad_id | fault-test build | used ID = NUM | vdisk fault: bad-id before any array access | M_TRUST_USED_ID |
Add every required test. “Kernel did not crash” is not a sufficient oracle for data integrity or ordering.
Measurements must explain, not decorate
Compare at least these builds:
- baseline-compatible direct chains;
- indirect descriptors enabled and offered; and
- indirect-capable build with synthetic negotiation selecting direct fallback for unit tests.
For runtime measurements, hold constant:
- recorded lab-start commit and final code except mode;
- QEMU and host version;
CPUS=1andCPUS=3as separate conditions;- image state and file contents;
- operation count, read/write mix, access order, and concurrency;
- warm-up rule and buffer-cache treatment; and
- number of repetitions.
Use at least three workloads:
- one process, cold sequential reads over a file larger than
NBUF; - four processes, disjoint cold reads to expose queue concurrency;
- controlled writes followed by reboot and checksum verification.
Report:
| Metric | Why it is needed |
|---|---|
| completed operations / raw-time interval | throughput under declared time units |
| median and p95 request time | distribution, not only average |
| max in-flight | whether indirect descriptors changed concurrency |
| descriptor waits and wait time | whether main-ring capacity is binding |
| completions / interrupt | batching behavior |
| CPU count and workload | reproducibility and contention context |
| data-integrity result | performance never substitutes for correctness |
Do not claim real-device speedup from QEMU. A valid result may show no throughput improvement because the filesystem, emulator, host scheduler, or workload is the bottleneck. The memo must connect observed max-in-flight and descriptor waits to any performance claim.
Transfer — interpret a null result. Indirect mode reaches six in-flight requests instead of two, but throughput is unchanged and p95 latency rises. Give three plausible mechanisms and one measurement for each.
Reveal an evidence mapExpandCollapse
- Device/emulator service is already saturated: inspect device utilization or completion rate versus queue depth.
- Extra queueing increases waiting without parallel service: split submit-to-dispatch and dispatch-to-complete times.
- A shared kernel/host lock or CPU is the bottleneck: compare
CPUS=1/3, lock-wait instrumentation, and host CPU saturation. - The workload hits another cache/path limit: inspect descriptor-wait count and actual block-driver submissions versus user operations.
The conclusion should identify which evidence discriminates mechanisms, not select one from intuition.
Design memo
Use these headings; each section must cite code, trace events, or test output.
Baseline and threat model
State the pinned ancestor, recorded lab-start commit, inherited cumulative changes, queue shape, device assumptions, trusted Virtio guarantees, and failures you inject. Distinguish a buggy driver, a spec-compliant device, and a device that violates the protocol.
State and ownership proof
Define every request state, owner, lock, and legal edge. Prove I1–I10. Include the point after which rollback is forbidden and the point before which reuse is forbidden.
Direct and indirect layouts
Draw both descriptor layouts, feature fallback, address lifetime, flags, alignment, and maximum in-flight calculation. Explain why the indirect table is persistent and device-visible.
Ordering argument
Identify descriptor stores, available-ring store, barriers, index publication, notification, used-ring synchronization, terminal state, wake, and reap. A source line list without happens-before claims is incomplete.
Failure analysis
For every injection, state detected symptom, contained state, resources intentionally retained, and why no unauthorized reuse occurs. Disclose that full reset/recovery is omitted.
Evaluation
Present raw-data link/path, environment, repetitions, summary statistics, uncertainty, and competing explanations. Separate QEMU evidence from hardware claims.
Residual risk
Name at least three untested assumptions, including post-reuse stale IDs, device reset, and filesystem error propagation. State the experiment or design work needed to reduce each risk.
Self-audit and diagnostic verification questions
Audit your implementation against these questions, verifying each against runtime traces or source invariants:
- Why does one indirect descriptor increase request capacity without increasing main-ring size?
- Which exact store publishes device ownership, and what must happen-before it?
- Why is the data descriptor device-writable for a read but not a write?
- What prevents a spurious wakeup from returning an incomplete buffer?
- Where is a used ID checked, and what state remains safe when it is invalid?
- Why can a private generation counter not identify a stale used entry after head reuse?
- Which resources remain pinned after your diagnostic timeout, and what event would permit release?
- How does the direct fallback prove that feature negotiation is not ceremonial?
- Show the counter values immediately before and after 16-bit wrap; why is full distinguishable from empty?
- Why can a descriptor be completed but not yet reusable?
- Which test fails if completion state is written after
wakeup? - What evidence shows indirect descriptors affected the bottleneck rather than only max in-flight?
- If p95 worsens while throughput improves, which objective decides acceptance?
- Which claim in the memo would become invalid on a noncoherent DMA platform?
- What additional protocol is required to recover rather than fail-stop after a device timeout?
- Which earlier-lab invariant is most exposed when a submitter sleeps for descriptors, and what regression trace proves this driver preserved it?
An answer may consult source and traces. Guessing an undocumented guarantee is worse than identifying the boundary.
Verification checklist and defect conditions
| Dimension | Invariant criterion | Verification evidence |
|---|---|---|
| Baseline reconstruction | Clean build from pinned commit | Exact commit, passing baseline, causal read/write traces |
| Negotiation and fallback | Compliance with Virtio feature negotiation | Synthetic feature matrix and zero unsupported feature use |
| Indirect implementation | Memory-safe chained descriptor allocation | Correct persistent layout, directions, fallback, and rollback |
| Lifecycle and ordering | Invariants I1–I10 preserved across all transitions | I1–I10 mapped to code, legal transitions, barriers, completion order |
| Fault injection | Deterministic fault handling and recovery | Deterministic failure modes with bounded, documented outcomes |
| Mutation-killing tests | Falsification of flawed driver variants | Every named mutant fails for the intended reason; correct builds pass |
| Data integrity/regression | Filesystem consistency after reboot | Upstream and reboot/checksum evidence in both modes |
| Measurement and analysis | Controlled performance evaluation | Controlled runs, raw data, tails, concurrency, uncertainty |
| Architectural understanding | Complete derivation of ownership and race boundaries | Precise residual-risk disclosure and falsifiable explanations |
Critical defect conditions that invalidate verification:
- device uses an unoffered feature;
- user-visible success on nonzero device status;
- descriptor or buffer reuse while device ownership may remain;
- out-of-bounds metadata access from an invalid used ID;
- data corruption hidden by rebuilding the image;
- fabricated timing units or unrun tests; or
- a copied full solution or assignment.
Suggested work allocation and exit evidence
| Work unit | Planned minutes | Exit evidence |
|---|---|---|
| environment and baseline trace | 75 | commit/build/test record; one read and write trace |
| feature decision and direct fallback | 75 | synthetic negotiation tests |
| indirect descriptor path | 180 | direct+indirect data-integrity tests; capacity trace |
| lifecycle, trace ring, and stats | 135 | state-edge tests and consistent snapshot |
| fault hooks and mutation matrix | 150 | failing mutant logs and passing correct logs |
| measurements, memo, and self-audit | 105 | raw runs, analysis, final memo |
| Total | 720 |
Exit evidence, not elapsed time, completes a work unit. A failed invariant returns the implementation to the relevant milestone.
Extension work
Extensions are considered only after the core implementation passes all verification invariants:
- implement Virtio queue reset when the feature/transport supports it, with proof that old DMA ownership ended;
- propagate block errors through buffer cache and filesystem without panic;
- negotiate event-index notification suppression and measure interrupt batching;
- implement packed virtqueues;
- add multiple queues with per-CPU submission while preserving fairness; or
- port the protocol to a noncoherent DMA model with explicit cache synchronization.
Each extension needs new mutants and failure oracles. Feature count is not quality evidence.
Deep Practice
Solve these problems to test and consolidate your understanding. Complete worked solutions and diagnostic hints are available for each problem.
Exercise 5.3.1: Verifying Features-OK in Virtio MMIO Negotiation
Trace the feature negotiation sequence mandated by the OASIS Virtio 1.3 specification for MMIO transport. Explain why reading the STATUS register immediately after setting FEATURES_OK is required before asserting DRIVER_OK.
HintExpandCollapse
The device clears FEATURES_OK if the subset of negotiated features is unacceptable.
Worked solutionExpandCollapse
The negotiation protocol requires:
- Driver resets device by writing 0 to
STATUS. - Driver sets the
ACKNOWLEDGEstatus bit (1). - Driver sets the
DRIVERstatus bit (2). - Driver reads the device-offered feature bits from
DEVICE_FEATURES. - Driver writes the accepted feature subset (e.g., enabling
VIRTIO_RING_F_INDIRECT_DESConly if offered and supported) intoDRIVER_FEATURES. - Driver sets the
FEATURES_OKstatus bit (8). - Verification step: Driver immediately reads
STATUS. The specification dictates that if the device does not accept the requested feature combination, it clearsFEATURES_OK. If the read showsFEATURES_OKis clear, the driver must abort initialization, as the device refuses to operate with that feature set. - Only if
FEATURES_OKremains set does the driver proceed to configure queues and writeDRIVER_OK(4).
Exercise 5.3.2: Constructing 3-Entry Indirect Descriptor Tables
Construct the 3-entry indirect descriptor table used for a Virtio block read in xv6.
Specify the fields (addr, len, flags, next) for each entry:
- Entry 0: Request header (
struct virtio_blk_req). - Entry 1: Data payload buffer (512 bytes).
- Entry 2: One-byte status response (
uint8 status).
HintExpandCollapse
Header and status are device-writable/readable according to protocol; chained with VRING_DESC_F_NEXT.
Worked solutionExpandCollapse
The indirect table is a contiguous array of three struct virtq_desc:
- Entry 0 (Header):
addr: Physical address ofstruct virtio_blk_req(specifying typeVIRTIO_BLK_T_INand sector number).len:sizeof(struct virtio_blk_req)(16 bytes).flags:VRING_DESC_F_NEXT(device reads the header, points to next entry).next: 1.
- Entry 1 (Data payload):
addr: Physical address of target disk bufferb->data.len: 512 bytes (BSIZE).flags:VRING_DESC_F_WRITE | VRING_DESC_F_NEXT(on a read, the device writes data into memory; points to next).next: 2.
- Entry 2 (Status byte):
addr: Physical address of 1-byte completion statusinfo[idx].status.len: 1 byte.flags:VRING_DESC_F_WRITE(device writes completion status; noNEXTflag, terminating chain).next: 0.
The single descriptor placed in the main virtqueue table has flags = VRING_DESC_F_INDIRECT, pointing to this 3-entry table.
Exercise 5.3.3: Proving Safe Available Ring Memory Barrier Publication
Let avail->ring[avail->idx % N] = head_id and avail->idx++. Prove that an architecture memory fence (__sync_synchronize() or dma_wmb()) is strictly necessary between populating the descriptor/ring entry and incrementing avail->idx.
HintExpandCollapse
Show that out-of-order execution allows the peripheral to read uncommitted descriptor data.
Worked solutionExpandCollapse
Assume for contradiction that the memory barrier is omitted:
- On modern superscalar or weakly ordered processors (such as multi-core RISC-V or ARM), independent memory writes can retire out of program order to memory.
- The store updating
avail->idx(which signals to the device that a new request exists) may become visible to the Virtio MMIO peripheral before the stores writing the descriptor contents oravail->ring[...]entry commit to RAM. - The device observes the incremented
avail->idx, readsavail->ring[...], and fetches the referenced descriptor table. - Because the descriptor table writes are still buffered in processor store queues, the device reads uninitialized memory or stale pointers from a prior request.
- The device executes DMA against an invalid host memory address, causing silent memory corruption or bus faults.
Therefore, an explicit release barrier:
is strictly mandatory.
Exercise 5.3.4: Formalizing the Driver Request Lifecycle State Machine
Formalize the state machine for driver request slots:
Specify the legal transitions, triggering events, and the invariant that prevents duplicate interrupt completions from corrupting driver state.
HintExpandCollapse
Define transitions: allocate -> prepare -> submit -> interrupt/done -> wait_reap -> free.
Worked solutionExpandCollapse
- State set:
- Transitions:
- Driver allocates a free request index and populates indirect descriptors.
- Descriptors published to available ring, doorbell notified.
- Device places ID in used ring and triggers interrupt; handler verifies
state == IN_FLIGHT, records status, marksCOMPLETED, and wakes waiter. - Sleeping waiter awakens, reads status, reclaims buffer, and marks
REAPED. - Slot returned to allocator pool with incremented generation.
- Duplicate completion defense:
If an interrupt arrives with descriptor ID when (for instance, if is already
COMPLETEDorFREE), the driver detects a protocol violation or duplicate interrupt. It ignores the spurious notification and flags an error without waking waiters or double-releasing buffers.
Exercise 5.3.5: Establishing Hardware Quiescence Before Buffer Reclaim
Explain why a driver cannot safely free a DMA buffer when a timeout expires in virtio_disk_rw(). Detail the sequence of hardware reset operations required to achieve verified device quiescence before memory reclamation.
HintExpandCollapse
The device engine may still access host memory unless reset to 0 and verified.
Worked solutionExpandCollapse
- The hazard:
A software timeout indicates that the host has waited longer than its deadline. It provides zero guarantees regarding device controller state. If the driver frees the kernel buffer
struct buf *bor returns it to the buffer cache while the device DMA engine is still active, the device may write 512 bytes into the buffer milliseconds later, corrupting whatever new file block or page table now occupies that memory. - Quiescence protocol:
To safely reclaim memory after a timeout or catastrophic device hang:
- Driver writes
0to the MMIOSTATUSregister to initiate a full device reset. - Driver polls
STATUSuntil reading0, confirming the hardware reset has completed and all internal DMA pipelines are aborted. - Driver unmaps or revokes all IOMMU mappings associated with outstanding virtqueue requests.
- Only after reset is acknowledged as complete is it safe to mark in-flight request slots as failed and release data buffers.
- Driver writes