A driver fills a descriptor with a buffer address and length, advances a producer index, and rings a device doorbell. The CPU reordered the producer-index store before the descriptor stores. The device observes new work, reads the old length and address, and transfers data into a frame that has already been reassigned.
The defect is not “DMA is unsafe.” The driver published ownership before the work description was complete. Device I/O is a concurrent protocol between agents with different clocks, caches, and failure modes. Correctness comes from explicit state transitions and ordering edges.
Buffer-ownership invariant. At every instant, the protocol identifies which agent may read or write each descriptor and data buffer. Ownership changes only after all prior writes required by the new owner are visible, and reclamation occurs only after the old owner can no longer access the object.
A device contract precedes driver code
A driver needs more than register addresses. Its contract must define:
| Contract field | Questions that must have one answer |
|---|---|
| register semantics | width, alignment, reset value, read/write side effects, reserved bits |
| command publication | which fields are written first; what store or I/O barrier orders them |
| device ownership | when the device may read descriptors or write buffers |
| completion | status encoding, interrupt condition, acknowledgment sequence, batching |
| queue capacity | full/empty test, wrap rule, maximum outstanding work |
| failure | malformed status, timeout meaning, reset/quiescence, late completion |
| concurrency | which locks protect software metadata; which fields the device changes independently |
Memory-mapped I/O (MMIO) gives device registers addresses in a processor-visible range. Register access is not ordinary RAM access: reads and writes can have side effects, widths can be constrained, and the platform defines ordering and caching attributes. In C, volatile can stop the compiler from removing or merging an access, but it does not create a cross-CPU lock, a device memory barrier, or a DMA ownership protocol. Kernel code should use architecture/platform MMIO accessors and barriers whose contract matches the device.
Programmed I/O (PIO) has the CPU copy data through registers or memory. Direct memory access (DMA) lets a device transfer between device-visible memory and itself after the CPU supplies descriptors. DMA removes a CPU copy loop from the data path; it adds another memory-accessing agent whose authority and lifetime must be controlled.
Retrieval — separate three guarantees. For an MMIO command register, state what volatile, a spinlock, and a device write barrier each establish. None may be described as a substitute for the other two.
Reveal the diagnostic answerExpandCollapse
volatileconstrains compiler treatment of the access according to the C implementation; it does not by itself order another core or device.- A spinlock serializes participating CPU threads and usually carries CPU memory-ordering semantics; the device does not acquire it.
- The architecture/platform’s device barrier orders specified CPU memory operations with respect to device observation.
Confusing these layers often produces code that passes on one machine because its memory model is stronger than the driver’s stated assumptions.
Device memory access and DMA ordering invariants
Evaluate each statement regarding memory-mapped IO registers, volatile qualifiers, and DMA synchronization:
Classify each option as correct or incorrect, or leave uncertain options unanswered (“I don't know”) and verify at any time.
Polling and interrupts trade work for notification latency
Polling repeatedly reads status. It can give bounded detection delay when a core polls at a controlled period, but consumes CPU work even when no event arrives. An interrupt transfers control when a device signals an event; it avoids idle polling but pays entry, dispatch, acknowledgment, and cache-disruption costs per notification.
For a periodic poll every seconds, uniformly distributed event arrival gives expected detection delay and worst-case delay near If one poll costs CPU seconds, polling occupancy is approximately
For event rate and interrupt-handling CPU time per event,
until queueing, coalescing, or saturation invalidates the independent-event model. Equating the two gives a first-order crossover The result is meaningful only if the latency constraint permits period and the measured costs match the platform.
Worked example: sparse control events
A device produces 200 events/s. One status poll costs 120 ns. The deadline requires detection within 50 µs, so choose µs for worst-case compliance. Polling consumes
of one CPU. If one interrupt consumes 2.5 µs of CPU time, interrupts consume
Interrupts use less CPU under these assumptions. Polling may still be chosen if its tighter jitter matters, if a dedicated core is available, or if event bursts would produce interrupt storms. The model does not decide the objective.
Coalescing changes the event unit
If the device posts 64 completions and sends one interrupt, the fixed notification cost is amortized across the batch. Coalescing reduces interrupt rate but delays early completions. The control variable is a count or timer threshold; evaluate both CPU occupancy and tail completion latency.
Application — choose a coalescing bound. Events arrive at 80,000/s. One interrupt costs 1.5 µs of CPU time. Batching 16 completions per interrupt adds at most 200 µs by policy. Calculate notification CPU occupancy without and with full batches; state why the latency claim still needs a burst/idle analysis.
Reveal the calculationExpandCollapse
Without batching, occupancy is 80,000 × 1.5 µs = 0.12, or 12% of one CPU. With full batches of 16, interrupt rate is 5,000/s and occupancy is 0.75%. Full batches do not always form: after a sparse arrival, a timer must release a partial batch, and the first completion may wait near the timer limit. The 200 µs policy bound also excludes interrupt dispatch and scheduling delay unless those are included explicitly.
DMA changes who moves bytes
For a transfer of bytes, compare two CPU-busy models:
DMA is advantageous for CPU occupancy when its fixed setup cost is less than the avoided CPU copy cost. It does not make the device latency or bus transfer disappear. Small transfers can favor PIO because DMA setup dominates.
Worked crossover under the simulator’s constants
The investigation below uses a 3 GHz CPU, 500 setup cycles for programmed I/O, 1,800 for DMA, 1,200 per interrupt, two CPU cycles per copied byte, and 100 MB/s transfer rate. Equating interrupt-driven PIO and DMA CPU work:
Under these invented constants, DMA has lower modeled CPU occupancy above 650 bytes; interrupt-driven PIO has lower fixed CPU work below it.
For 4 KiB, 1 ms latency, and 100 operations/s:
| Mechanism | CPU busy per operation | Elapsed per operation | CPU occupancy |
|---|---|---|---|
| busy polling + PIO | 1.0439 ms | 1.0439 ms | 10.44% |
| interrupt + CPU copy | 0.00330 ms | 1.0443 ms | 0.033% |
| DMA + completion interrupt | 0.00100 ms | 1.0420 ms | 0.010% |
DMA has both the lowest CPU occupancy and, by a small margin, the lowest elapsed time for this 4 KiB state: its larger setup is outweighed by eliminating the modeled CPU copy. That elapsed-time result can reverse for transfers below the 650-byte crossover. Latency and CPU demand remain different objectives.
Experiment: change bytes, events, and device latency
The simulator assumes one independent operation, no queueing, a fixed 100 MB/s transfer rate, and the numeric constants listed above. Polling means continuous busy waiting for the modeled device latency, not periodic polling. CPU occupancy is capped at 100%; once offered work exceeds capacity, the widget does not model the resulting queue or latency growth.
Prediction — quantify before moving a slider. At 64 bytes, 0.1 ms device latency, and 2,000 operations/s, which has lower modeled CPU occupancy: interrupt-driven copying or DMA? Use the fixed-cycle equations, then set the widget to that state.
Choose polling, interrupts, or DMA from workload evidence
Change transfer size, device latency, and operation rate. The timeline separates elapsed device time from CPU occupancy and exposes when setup overhead or busy waiting dominates.
Explicit model: 3 GHz CPU, 500 setup cycles for programmed I/O, 1,800 for DMA, 1,200 per interrupt, two CPU cycles per CPU-copied byte, and 100 MB/s device transfer. Polling occupies the CPU during both device latency and transfer. Very short CPU phases receive an eight-pixel minimum marker, so their drawn width is not a timing claim. Occupancy is capped at 100%; a larger offered load means the requested rate is unsustainable on one CPU. These are teaching assumptions—not hardware claims.
Static state: 4 KiB transfers, 1 ms device latency, 100 operations/s, interrupt-driven CPU copying. The CPU is free during device latency but pays setup, interrupt, and copy work.
Interrupt-driven copying consumes (500 + 1200 + 128)/3 GHz = 0.609 µs per operation, or about 0.122% of a CPU at 2,000/s. DMA consumes 3,000/3 GHz = 1 µs per operation, or 0.200%. The small transfer favors CPU copy under this CPU-work model; device latency changes elapsed time but not these two modeled CPU-work equations.
Transfer — invalidate one assumption. Replace the constant 100 MB/s device with a device that sustains four transfers concurrently but slows each transfer by 30% at queue depth four. State what additional state the model needs before it can predict throughput and tail latency.
Reveal the modeling requirementsExpandCollapse
The model needs at least queue depth, arrival process, number of service lanes, service-time dependence on concurrency, completion order, and a latency distribution rather than one constant. CPU occupancy can still be computed per submission/completion, but end-to-end latency requires waiting time plus concurrency-dependent service. A single-operation bar cannot support a queueing claim.
Descriptor rings encode ownership
High-throughput devices use shared-memory descriptors. A descriptor typically contains a device-visible address, length, direction, command, and status. A split ring such as Virtio has driver-written available state and device-written used state.
For ring capacity and monotonic producer/consumer counters, the software invariant is
Slots are indexed modulo but counters should retain enough generation information to distinguish full from empty after wrap. Publication follows a release pattern:
write descriptor fields
write barrier for device visibility
write ring slot containing descriptor head
write barrier required by transport
advance published producer index
notify device if required
The device may access the descriptor immediately after the publication point. Editing a submitted descriptor before completion violates ownership even if the CPU still has a pointer to it.
Worked wrap trace
An eight-entry ring has monotonic producer=14, consumer=10, so occupancy is four. Published requests occupy logical sequence numbers 10–13 and physical slots 2–5. The producer’s next physical slot is 14 mod 8 = 6.
Publishing three requests uses slots 6, 7, and 0, then advances producer to 17. Occupancy becomes seven. One slot remains. Comparing only producer mod 8 = 1 with consumer mod 8 = 2 does not directly reveal occupancy; generation-bearing counters do.
Application — kill publish-first. A mutation advances producer before writing the descriptor’s length. Construct an interleaving in which the device reads a valid old address and old length. State which single happens-before edge is missing.
Reveal the failing interleavingExpandCollapse
CPU publishes producer 15; device observes the new index and reads slot 6; slot 6 still contains the previous generation’s descriptor; device begins DMA; CPU writes the new address and length too late. The missing edge is “all descriptor and ring-slot stores happen before the publication-index store as observed by the device.” A CPU-only lock does not create that edge unless the device participates in its memory-ordering protocol, which it does not.
Coherence, synchronization, and IOMMU authority
A coherent DMA allocation lets CPU and device observe each other’s writes without explicit cache-line cleaning for coherence, but coherent memory still needs barriers to order fields. A streaming DMA mapping may require explicit synchronization when ownership passes between CPU and device. Linux’s DMA API documents separate dma_sync_*_for_device and dma_sync_*_for_cpu operations for reused streaming mappings.
An IOMMU translates a device-visible I/O virtual address and enforces device permissions. It can restrict a device to the pages assigned to its DMA context, but it cannot repair a driver that reuses a still-owned buffer. Teardown requires both:
- stop or quiesce old device transactions; and
- revoke/invalidate device translations before the physical pages enter a new ownership domain.
Counterexample: timeout is not cancellation
A request exceeds its deadline. The driver returns an error, unmaps the DMA address, and allocates the frame to another process. The device completes late and writes into the new process’s memory. The timeout proved only that completion was not observed by a deadline. Safe recovery must retain the buffer or complete a documented cancel/reset/quiesce protocol before reuse.
Interrupt handling closes the protocol
An interrupt handler must drain enough device state that the interrupt condition is understood and acknowledged according to the device contract. It must also preserve concurrency invariants:
- validate completion IDs before indexing software arrays;
- synchronize before reading device-written status or data;
- transition each request to completed at most once;
- detach ownership before waking a waiter that may free resources;
- avoid blocking work that cannot run in interrupt context; and
- handle more than one completion per interrupt when the device batches.
Worked race: wake before state
Waiter code uses while (req.state != DONE) sleep(req, lock). The interrupt handler calls wakeup(req) and then writes req.state = DONE. A waiter can wake, reacquire the lock before the state store, observe IN_FLIGHT, and sleep again after the one wakeup has passed. The fix is to update completion state while holding the protocol lock and wake after the state transition is visible. The loop remains necessary because wakeups can be spurious or another event can change scheduling.
Duplicate and malformed completions
A duplicate completion must not decrement a reference twice or recycle a descriptor already assigned to another generation. Track request identity and lifecycle, validate id < ring_size, require state == IN_FLIGHT, and pair a reusable slot with a generation or sequence number when delayed events can cross reuse. A malformed status is a device/transport failure to report; treating every completion as success converts device error into silent data corruption.
Transfer — teardown defense. A hot-unplug event arrives with four requests in flight. Write a state sequence that permits their buffers to be reused. “Wait 100 ms” is not an admissible transition.
Reveal a valid boundary sequenceExpandCollapse
Stop admitting new submissions; mark the device stopping; mask or route interrupts according to the platform contract; request and verify device/queue reset or another specified quiescence mechanism; drain or fail completions while keeping buffers pinned; revoke DMA mappings and invalidate IOMMU state after quiescence; transition every request exactly once to completed/failed; wake waiters; then release descriptors and buffers. If the platform cannot prove quiescence, retaining/quarantining the memory is safer than reuse.
Deep Practice
Solve these problems to test and consolidate your understanding. Complete worked solutions and diagnostic hints are available for each problem.
Exercise 5.1.1: Calculating the Polling versus Interrupt CPU Occupancy Crossover
A peripheral device produces I/O events at mean rate events per second.
- Polling implementation: The CPU polls every with each poll requiring of CPU execution time.
- Interrupt-driven implementation: Each event triggers a hardware interrupt requiring of CPU service time (entry, context save, driver handler, EOI acknowledgment, context restore).
- Calculate the steady-state CPU occupancy of the polling driver
- Compute the event arrival rate at which the interrupt-driven driver consumes identical CPU occupancy
- If the actual arrival rate is determine which notification strategy minimizes CPU overhead.
HintExpandCollapse
Occupancy for polling is C_p / P; occupancy for interrupts is lambda * C_i.
Worked solutionExpandCollapse
- Polling occupancy:
- Crossover arrival rate Set
- Evaluation at Because polling consumes CPU whereas interrupts consume Polling minimizes CPU occupancy at this arrival rate.
Exercise 5.1.2: Memory Barrier Placement in Producer-Consumer Descriptor Rings
A driver submits a DMA packet by populating a ring descriptor desc[idx] in host RAM (fields: buffer_pa, length, flags) and subsequently ringing an MMIO doorbell register DOORBELL = idx to notify the network device.
- Explain the race condition that occurs if the CPU or compiler reorders the doorbell store before the descriptor field stores.
- Specify the exact memory barrier or fence required between the descriptor initialization and the MMIO doorbell write on weakly ordered architectures.
HintExpandCollapse
The device starts fetching memory immediately upon receiving the doorbell write.
Worked solutionExpandCollapse
- Reordering race condition:
If the MMIO store to
DOORBELLreaches the peripheral before the writes todesc[idx]retire to coherent RAM or cache, the device immediately readsdesc[idx]. The device observes uninitialized or stale descriptor values (e.g., an old buffer address or invalid length), causing the device to read or overwrite unauthorized host memory. - Barrier specification:
The driver must place a release memory barrier or write memory barrier (
smp_wmb()oratomic_thread_fence(memory_order_release)) immediately before the doorbell store:
This enforces the happens-before relationship:desc[idx].buffer_pa = dma_addr; desc[idx].length = packet_len; desc[idx].flags = DESC_VALID; dma_wmb(); /* guarantees memory writes precede MMIO writes */ mmio_write32(&dev->doorbell, idx);
Exercise 5.1.3: Deriving Transfer-Size Thresholds for DMA versus Programmed I/O
A 2 GHz CPU executes programmed I/O (PIO) or direct memory access (DMA):
- PIO setup is negligible, but copying requires 3 CPU cycles per transferred byte.
- DMA setup requires pinning pages, setting up descriptors, and cache flushing/invalidation, costing a fixed The DMA engine transfers data without CPU intervention.
- Both schemes pay a fixed for completion interrupt processing.
- Write the CPU cycle cost functions and for a transfer of bytes.
- Find the breakeven transfer size where DMA becomes strictly more efficient for CPU occupancy than PIO.
HintExpandCollapse
Set C_PIO(B) = C_DMA(B) and solve for B.
Worked solutionExpandCollapse
- Cost functions:
- For Programmed I/O:
- For DMA:
- Breakeven size For transfers strictly greater than 600 bytes, DMA is more CPU-efficient; for transfers smaller than 600 bytes (e.g., 64-byte control packets), PIO avoids the setup tax and reduces total CPU load.
Exercise 5.1.4: Proving Buffer Invariant Violations on Premature Timeout Reclamation
Suppose a disk driver submits a DMA read request for physical buffer After 5 seconds, the request has not completed, and a software timeout fires. Prove that unmapping and immediately reallocating it to an unrelated process violates the buffer-ownership invariant unless the device is proven quiesced.
HintExpandCollapse
A timeout measures only software wait time, not device bus state; the device may commit transfer cycles later.
Worked solutionExpandCollapse
Assume for contradiction that the driver frees and reallocates buffer to Process immediately upon timeout expiration without issuing a hardware reset or awaiting device quiescence:
- The expiration of a software timer proves only that no completion interrupt was processed; it does not prove the peripheral hardware aborted its bus mastering activity.
- The device controller may be delayed due to internal queueing, bus contention, or high controller latency.
- Once buffer is reassigned to Process Process begins writing sensitive data into
- At the delayed device DMA engine initiates or finishes writing its delayed disk block into physical address
- The device overwrites ‘s active data, destroying memory contents and violating the buffer-ownership invariant:
Therefore, buffer cannot be freed or reused until the driver executes a verified hardware reset, aborts the in-flight command on the controller, and confirms bus quiescence.
Exercise 5.1.5: Eliminating Lost Wakeup Races in Asynchronous Driver Waiters
Analyze the following buggy driver completion sequence between an interrupt handler and a sleeping process:
- Waiter:
while (req->status == PENDING) { sleep_on(&req->wq); } - Handler:
wake_up(&req->wq); req->status = DONE;
Show how this order can cause an indefinite deadlock, and formulate the correct synchronized sequence.
HintExpandCollapse
Show that the waiter can evaluate the condition right before the handler executes both lines.
Worked solutionExpandCollapse
- Failure schedule:
- Waiter reads
req->status, observesPENDING. - Before the waiter enters the sleep queue, a hardware interrupt fires on the CPU.
- The interrupt handler executes: calls
wake_up(&req->wq), but the wait queue is currently empty. - The interrupt handler then sets
req->status = DONEand returns from interrupt. - The preempted waiter resumes and executes
sleep_on(&req->wq). - The waiter is now suspended indefinitely because the wakeup occurred in the past, causing a lost wakeup and indefinite thread hang.
- Waiter reads
- Correct synchronization protocol:
The status transition must happen before the wakeup, and both operations must be protected by the queue lock:
- In handler:
acquire(&req->lock); req->status = DONE; wake_up_locked(&req->wq); release(&req->lock); - In waiter:
acquire(&req->lock); while (req->status == PENDING) { sleep_locked(&req->wq, &req->lock); } release(&req->lock);
req->lockensures that checking the condition and sleeping is atomic with respect to the state modification and wakeup. - In handler: