Saturday, January 10, 2026

Building a virtio-serial FPGA device (Part 4): Virtqueue processing

This is the fourth post in a series about building a virtio-serial device in Verilog for an FPGA development board. This time we'll look at processing the virtio-serial device's transmit and receive virtqueues.

Series table of contents

  1. Part 1: Overview
  2. Part 2 - MMIO registers, DMA, and interrupts
  3. Part 3 - virtio-serial device design
  4. Part 4 - Virtqueue processing (you are here)
  5. Part 5 - UART receiver and transmitter
  6. Part 6 - Writing the RISC-V firmware

The code is available at https://gitlab.com/stefanha/virtio-serial-fpga.

The virtio-serial device has a pair of virtqueues that allow the driver to transmit and receive data. The driver enqueues empty buffers onto the receiveq (virtqueue 0) and the device fills them with received data. The driver enqueues buffers containing data onto the transmitq (virtqueue 1) and the device sends them.

This logic is split into two modules: virtqueue_reader for the transmitq and virtqueue_writer for the receiveq. The interface of virtqueue_reader looks like this:

/* Stream data from a virtqueue without framing */
module virtqueue_reader (
    input clk,
    input resetn,

    /* Number of elements in descriptor table */
    input [15:0] queue_size,
    /* Lower 32-bits of Virtqueue Descriptor Area address */
    input [31:0] queue_desc_low,
    /* Lower 32-bits of Virtqueue Driver Area address */
    input [31:0] queue_driver_low,
    /* Lower 32-bits of Virtqueue Device Area address */
    input [31:0] queue_device_low,
    input queue_notify,            /* kick */

    input phase,
    output reg [31:0] data = 0,
    output reg [2:0] data_len = 0,
    output ready,

    /* For DMA */
    output reg ram_valid = 0,
    input ram_ready,
    output reg [3:0] ram_wstrb = 0,
    output reg [21:0] ram_addr = 0,
    output reg [31:0] ram_wdata = 0,
    input [31:0] ram_rdata
);

If you are familiar with the VIRTIO specification you might recognize queue_size, queue_desc_low, queue_driver_low, queue_device_low, and queue_notify since they are values provided by the VIRTIO MMIO Transport. The driver configures them with the memory addresses of the virtqueue data structures in RAM. The device will DMA to access those data structures. The driver can kick the device to indicate that new buffers have been enqueued using queue_notify.

The reader interface consists of phase, data, data_len, and ready and this is what the rdwr_stream module needs to use virtqueue_reader as a data source. rdwr_stream will keep reading the next byte(s) by flipping the phase bit and waiting for ready to be asserted by the device. Note that the device can provide up to 4 bytes at a time through the 32-bit data register and data_len allows the device to indicate how much data was read.

Finally, the DMA interface is how virtqueue_reader initiates RAM accesses so it can fetch the virtqueue data structures that the driver has configured.

The state machine

Virtqueue processing consists of multiple steps and cannot be completed within a single clock cycle. Therefore the processing is decomposed into a state machine where each step consists of a DMA transfer or waiting for an event. Here are the states:

`define STATE_WAIT_PHASE 0                 /* waiting for phase bit to flip */
`define STATE_READ_AVAIL_IDX 1             /* waiting for avail.idx read */
`define STATE_WAIT_NOTIFY 2                /* waiting for queue notify (kick) */
`define STATE_READ_DESCRIPTOR_ADDR_LOW 3   /* waiting for descriptor read */
`define STATE_READ_DESCRIPTOR_LEN 4
`define STATE_READ_DESCRIPTOR_FLAGS_NEXT 5
`define STATE_READ_BUFFER 6                /* waiting for data buffer read */
`define STATE_WRITE_USED_ELEM_ID 7         /* waiting for used element write */
`define STATE_WRITE_USED_ELEM_LEN 8
`define STATE_WRITE_USED_FLAGS_IDX 9       /* waiting for used.flags/used.idx write */
`define STATE_READ_AVAIL_RING_ENTRY 10     /* waiting for avail element read */

The device starts up in STATE_WAIT_PHASE because it is waiting to be asked to read the first byte(s). As soon as rdwr_stream flips the phase bit, virtqueue_reader must check the virtqueue to see if any data buffers are available.

I won't describe all the details of virtqueue processing, but here is a summary of the steps involved. See the VIRTIO specification or the code for the details.

  1. Read the avail.idx field from RAM in case the driver has enqueued more buffers.
  2. Read the avail.ring[i] entry from RAM to fetch the descriptor table index of the next available buffer.
  3. Read the descriptor from RAM to find out the buffer address and length.
  4. Repeatedly read bytes from the buffer until the current descriptor is empty. If the descriptor is chained, read the next descriptor from RAM and repeat.
  5. If the chain is finished, check avail.idx again in case there are more buffers available.

After a buffer has been fully consumed, there are also several steps to fill out a used descriptor and increment the used.idx field so that the driver is aware that the buffer is done.

There are two wait states when the device stops until it there is more work to do. First, rdwr_stream will stop asking to read more data if the writer is too slow. This flow control ensures that data is not dropped due to a slow writer. This is STATE_WAIT_PHASE. Second, if the device wants to read but the virtqueue is empty, then it has to wait until queue_notify goes high. This is STATE_WAIT_NOTIFY.

The virtqueue_writer module is similar to virtqueue_reader but it fills in the buffers with data instead of consuming them.

A quick side note about memory alignment: the memory interface is 32-bit aligned, so it is only possible to read an entire 32-bit value from memory at multiples of 4 bytes. On a fancier CPU with a cache the unit would be a cache line (e.g. 128 bytes). When the data structures being DMAed are not aligned it becomes tedious to handle the shifting and masking, especially when reading data from a source and writing it to a destination. Life is much simpler when everything is aligned, because data can be trivially read or written in a single access without any special logic to adjust the data to fit the cache line size.

Conclusion

The virtqueue_reader and virtqueue_writer modules use DMA to read or write data from/to RAM buffers provided by the driver running on the PicoRV32 RISC-V CPU inside the FPGA. They are state machines that run through a sequence of DMA transfers and provide the reader/writer interfaces that the rdwr_module uses to transfer data. In the next post we will look at the UART receiver and transmitter.

Building a virtio-serial FPGA device (Part 6): Writing the RISC-V firmware

This is the final post in a series about building a virtio-serial device in Verilog for an FPGA development board. This time we'll look at the firmware running on the PicoRV32 RISC-V soft-core in the FPGA.

Series table of contents

  1. Part 1: Overview
  2. Part 2 - MMIO registers, DMA, and interrupts
  3. Part 3 - virtio-serial device design
  4. Part 4 - Virtqueue processing
  5. Part 5 - UART receiver and transmitter
  6. Part 6 - Writing the RISC-V firmware (you are here)

The code is available at https://gitlab.com/stefanha/virtio-serial-fpga.

The PicoRV32 RISC-V soft-core boots up executing code from flash memory at 0x10000000. Since RISC-V is supported by LLVM and gcc, it is possible to write the firmware in several languages. For this project I wanted to use Rust and was aware of several existing crates that already provide APIs for things that would be needed.

I used a Rust no_std environment, which means that the standard library (std) is not available and only the core library (core) is available. Crates written for embedded systems and low-level programming often support no_std, but most other crates rely on the standard library and an operating system. no_std is a niche in the Rust ecosystem but it works pretty well.

The following crates came in handy:

  • riscv-rt provides the basic startup code for bare metal on RISC-V. It has the linker script, assembly pre-Rust startup code, and provides things that Rust's runtime needs.
  • safe-mmio is an API for MMIO device register access. This was helpful for low-level testing of device registers during the early phases of the project.
  • virtio-drivers has a virtio-serial driver! I didn't need to implement virtqueues, the VIRTIO MMIO Transport, or the virtio-serial driver software myself.

Initially I thought I could get away without a memory allocator since no_std does not have one by default and it would be extra work to set one up. However, virtio-drivers needed one for the virtio-serial device (I don't think it is really necessary, but the code is written that way). Luckily the embedded-alloc has memory allocators that are easy to set up and just need a piece of memory to operate in.

Aside from the setup code, the firmware is trivial. The CPU just sends a hello world message and then echoes back bytes received from the virtio-serial device.

#[riscv_rt::entry]
fn main() -> ! {
    unsafe {
        extern "C" {
            static _heap_size: u8;
        }
        let heap_bottom = riscv_rt::heap_start() as usize;
        let heap_size = &_heap_size as *const u8 as usize;
        HEAP.init(heap_bottom, heap_size);
    }

    // Point virtio-drivers at the MMIO device registers
    let header = NonNull::new(0x04000000u32 as *mut VirtIOHeader).unwrap();
    let transport = unsafe { MmioTransport::new(header, 0x1000) }.unwrap();

    // Put the string on the stack so the device can DMA (it cannot DMA flash memory)
    let mut buf: [u8; 13] = *b"Hello world\r\n";

    if transport.device_type() == DeviceType::Console {
        let mut console = VirtIOConsole::::new(transport).unwrap();
        console.send_bytes(&buf).unwrap();
        loop {
            if let Ok(Some(ch)) = console.recv(true) {
                buf[0] = ch;
                console.send_bytes(&buf[0..1]).unwrap();
            }
        }
    }
    loop {}
}

In the early phases I ran tests on the iCESugar board that lit up an LED to indicate the test result. As things became more complex I switched over to Verilog simulation. I wrote testbenches that exercise the Verilog modules I had written. This is similar to unit testing software.

In the later stages of the project, I changed the approach once more in order to do integration testing and debugging. To get more visibility into what was happening in the full design with a CPU and virtio-serial device, I used GTKWave to view the VCD files that Icarus Verilog can write during simulation. You can see every cycle and every value in each register or wire in the entire design, including the PicoRV32 RISC-V CPU, virtio-serial device, etc.

This allowed very powerful debugging since the CPU activity is visible (see the program counter in the reg_pc register in the screenshot) alongside the virtio-serial device's internal state. It is possible to look up the program counter in the firmware disassembly to follow the program flow and see where things went wrong.

Conclusion

The firmware is a small Rust codebase that uses existing crates, including riscv-rt and virtio-drivers. Throughout the project I used several debugging and simulation approaches, depending on the level of complexity. Thanks to the open source code and tools available, it was possible to complete this project using fairly convenient and powerful tools and without spending a lot of time reinventing the wheel. Or at least without reinventing the wheels I didn't want to reinvent :).

Let me know if you enjoy FPGAs and projects you've done!

Building a virtio-serial FPGA device (Part 5): UART receiver and transmitter

This is the fifth post in a series about building a virtio-serial device in Verilog for an FPGA development board. This time we'll look at the UART receiver and transmitter.

Series table of contents

  1. Part 1: Overview
  2. Part 2 - MMIO registers, DMA, and interrupts
  3. Part 3 - virtio-serial device design
  4. Part 4 - Virtqueue processing
  5. Part 5 - UART receiver and transmitter (you are here)
  6. Part 6 - Writing the RISC-V firmware

The code is available at https://gitlab.com/stefanha/virtio-serial-fpga.

How UARTs work

A Universal Asynchronous Receiver-Transmitter (UART) is a simple interface for data transfer that only requires a transmitter (tx) and a receiver (rx) wire. There is no clock wire because both sides of the connection use their own clocks and sample the signal in order to reconstruct the bits being transferred. This agreed-upon data transfer rate (or baud rate) is usually modest and the frame encoding is also not the most efficient way of transferring data, but UARTs get the job done and are commonly used for debug consoles, modems, and other relatively low data rate interfaces.

There is a framing protocol that makes it easier to reconstruct the transferred data. This is important because failure to correctly reconstruct the data results in corrupted data being received on the other side. In this project I used a 9,600 bit/s baud rate and 8 data bits, no parity bit, and 1 stop bit (sometimes written as 8N1). The framing works as follows:

  • When no data is being transferred, the signal is 1.
  • Before the data byte, a start bit is sent with the value 0. This way a receiver can detect the beginning of a frame.
  • The start bit is followed by the 8 data bits in least significant bit order.
  • After the data bits the frame ends with a stop bit with the value 1.

The job of the transmitter is to follow this framing protocol. The job of the receiver is to detect the next frame and to reconstruct the byte being transferred.

Implementation

The uart_reader and uart_writer modules implement the UART receiver and transmitter, respectively. They are designed around the rdwr_stream module's reader and writer interfaces. That means uart_reader receives the next byte from the UART rx pin whenever it is asked to read more data and uart_writer transmits on the UART tx pin whenever it is asked to write more data.

uart_reader follows a trick I learnt from the PicoSoC's simpleuart module: once the rx pin goes from 1 to 0, it waits until half the period (e.g. 9,600 baud @ 12 MHz / 2 = 625 clock cycles) has passed before sampling the rx pin. This works well because the UART only transfers data on the iCESugar PCB and is not exposed to much noise. Fancier approaches involve sampling the pin every clock cycle in order to try to reconstruct the value more accurately, but they don't seem to be necessary for this project.

Here is the core uart_reader code, a state machine that parses the incoming frame:

always @(posedge clk) begin
    ...
    div_counter <= div_counter + 1;
    case (bit_counter)
    0: begin // looking for the start bit
        if (rx == `START_BIT) begin
            div_counter <= 0;
            bit_counter <= 1;
        end
    end
    1: begin
        /* Sample in the middle of the period */
        if (div_counter == clk_div >> 1) begin
            div_counter <= 0;
            bit_counter <= 2;
        end
    end
    10: begin // expecting the stop bit
        if (div_counter == clk_div) begin
            if (rx == `STOP_BIT && !reg_ready) begin
                data <= {24'h0, rx_buf};
                data_len <= 1;
                reg_ready <= 1;
            end
            bit_counter <= 0;
        end
    end
    default: begin // receive the next data bit
        if (div_counter == clk_div) begin
            rx_buf <= {rx, rx_buf[7:1]};
            div_counter <= 0;
            bit_counter <= bit_counter + 1;
        end
    end
    endcase

The uart_writer module is similar, but it has a transmit buffer that it sends over the UART tx pin with the framing that I've described here.

Conclusion

The uart_reader and uart_writer modules are responsible for receiving and transmitting data over the UART rx/tx pins. They implement the framing protocol that UARTs use to protect data. In the next post we will cover the firmware running on the PicoRV32 RISC-V soft-core that drives the I/O.

Building a virtio-serial FPGA device (Part 3): virtio-serial device design

This is the third post in a series about building a virtio-serial device in Verilog for an FPGA development board. This time we'll look at the design of the virtio-serial device and how to decompose it into modules.

Series table of contents

  1. Part 1: Overview
  2. Part 2 - MMIO registers, DMA, and interrupts
  3. Part 3 - virtio-serial device design (you are here)
  4. Part 4 - Virtqueue processing
  5. Part 5 - UART receiver and transmitter
  6. Part 6 - Writing the RISC-V firmware

The code is available at https://gitlab.com/stefanha/virtio-serial-fpga.

A virtio-serial device is a serial controller, enabling communication with the outside world. The iCESugar FPGA development board has UART rx and tx pins connecting the FPGA to a separate microcontroller that acts as a bridge for USB serial communication. That means the FPGA can wiggle the bits on the UART tx pin to send bytes to a computer connected to the board via USB and you can receive bits from the computer through the UART rx pin. The purpose of the virtio-serial device is to present a VIRTIO device to the PicoRV32 RISC-V CPU inside the FPGA so the software on the CPU can send and receive data.

Device design

The virtio-serial device implements the Console device type defined in the VIRTIO specification and exposes it to the driver running on the CPU via the VIRTIO MMIO Transport. The terms "serial" and "console" are used interchangeably in the VIRTIO community and I will usually use serial unless I'm specifically talking about the Console device type section in the VIRTIO specification.

VIRTIO separates the concept of a device type (like net, block, or console) from the transport that allows the driver to access the device. This architecture allows VIRTIO to be used across a range of different machines, including machines that have a PCI bus, MMIO devices, and so on. Fortunately the VIRTIO MMIO transport is fairly easy to implement from scratch.

The virtio_serial_mmio module implements the virtio-serial device from the following parts:

  • VIRTIO MMIO Transport - MMIO device registers conforming to the VIRTIO specification. They allow the CPU to configure the device and initiate data transfers.
  • UART reader & virtqueue writer - Incoming data from the UART rx pin is enqueued on the VIRTIO Console receiveq (virtqueue 0) where the driver can receive it.
  • Virtqueue reader & UART writer - The VIRTIO Console transmitq (virtqueue 1) lets the driver enqueue data that the device sends over the UART tx pin.

The virtio-serial device interfaces with the outside world through an MMIO interface that the CPU uses to access the device registers, a DMA interface for initiating RAM memory transfers, and the UART rx/tx pins for actually sending and receive data.

Note that both the virtqueue_reader and the virtqueue_writer modules require DMA access, so I reused the spram_mux module that multiplexes the CPU and the virtio-serial device's RAM accesses. spram_mux is used inside virtio_serial_mmio to multiplex access to the single DMA interface.

Reader and writer interfaces

Since the job of the device is to transfer data between the virtqueues and the UART rx/tx pins, it is organized around a module named rdwr_stream that constantly attempts to read data from a source and write it to a destination:

/* Stream data from a reader to a writer */
module rdwr_stream (
    input clk,
    input resetn,

    /* The reader interface */
    output reg rd_phase = 0,
    input [31:0] rd_data,
    input [2:0] rd_data_len,
    input rd_ready,

    /* The writer interface */
    output reg wr_phase = 0,
    output reg [31:0] wr_data = 0,
    output reg [2:0] wr_data_len = 0,
    input wr_ready
);

By implementing the reader and writer interfaces for the virtqueues and UART rx/tx pins, it becomes possible to pump data between them using rdwr_stream. For testing it's also possible to configure virtqueue loopback or UART loopback so that the virtqueue logic or the UART logic can be exercised in isolation.

The reader and writer interfaces that the rdwr_stream module uses are the central abstraction in the virtio-serial device. You might notice that this interface uses a phase bit rather than a valid bit like in the valid/ready interface for MMIO and DMA. Every transfer is initiated by flipping the phase bit from its previous value. I find the phase bit approach easier to work with because it distinguishes back-to-back transfers, whereas interfaces that allow the valid bit to stay 1 for back-to-back transfers are harder to debug. It would be possible to switch to a valid/ready interface though.

To summarize, there are 4 reader or writer implementations that can be connected freely through the rdwr_stream module:

  1. virtqueue_reader - reads buffers from the transmitq virtqueue (virtqueue 1).
  2. virtqueue_writer - writes buffers to the receiveq virtqueue (virtqueue 0).
  3. uart_reader - reads data from the UART rx pin.
  4. uart_writer - writes data to the UART tx pin.

Conclusion

The virtio-serial device consists of the VIRTIO MMIO Transport device registers plus two rdwr_streams that transfer data between virtqueues and the UART. The next post will look at how virtqueue processing works.

Building a virtio-serial FPGA device (Part 2): MMIO registers, DMA, and interrupts

This is the second post in a series about building a virtio-serial device in Verilog for an FPGA development board. This time we'll look at integrating MMIO devices to the PicoSoC (an open source System-on-Chip using the PicoRV32 RISC-V soft-core).

Series table of contents

  1. Part 1: Overview
  2. Part 2 - MMIO registers, DMA, and interrupts (you are here)
  3. Part 3 - virtio-serial device design
  4. Part 4 - Virtqueue processing
  5. Part 5 - UART receiver and transmitter
  6. Part 6 - Writing the RISC-V firmware

There are three common ways in which devices interact with a system:

  • Memory-mapped hardware registers let driver software running on the CPU communicate with the device. This is called MMIO.
  • Direct Memory Access (DMA) lets the device initiate RAM read or write accesses without tying up the CPU. This is typically used for bulk data transfers. An example is a network card receiving a packet into memory buffer.
  • Interrupts allow the device to signal the CPU that can event has occurred.

PicoSoC supports MMIO device registers and interrupts out of the box. It does not support DMA, but I will explain how this can be added by modifying the code later.

Memory-mapped I/O registers

First let's look at implementing MMIO registers for a device in PicoSoC. The PicoRV32 CPU's memory interface looks like this:

output        mem_valid // request a memory transfer
output        mem_instr // hint that CPU is fetching an instruction
input         mem_ready // reply to memory transfer

output [31:0] mem_addr  // address
output [31:0] mem_wdata // data being written
output [ 3:0] mem_wstrb // 0000 - read
                        // 0001 - write 1 byte
                        // 0011 - write 2 bytes
                        // 0111 - write 3 bytes
                        // 1111 - write 4 bytes
input  [31:0] mem_rdata // data being read

When mem_valid is 1 the CPU is requesting a memory transfer. The memory address in mem_addr is decoded and the appropriate device is selected according to the memory map (e.g. virtio-serial device at 0x04000000-0x040000ff). The selected device then handles the memory transfer and asserts mem_ready to let the CPU know that the transfer has completed.

In order to handle MMIO device register accesses, the virtio-serial device needs a similar memory interface. The register logic is implemented in a case statement that handles wdata or rdata depending on the semantics of the register. Here is the VIRTIO MMIO MagicValue register implementation that reads a constant identifying this as a VIRTIO MMIO device:

module virtio_serial_mmio (
    ...
    input iomem_valid,
    output iomem_ready,
    input [3:0] iomem_wstrb,
    input [7:0] iomem_addr,
    input [31:0] iomem_wdata,
    output [31:0] iomem_rdata,
    ...
);
    ...
    always @(posedge clk) begin
        ...
        case (iomem_addr)
            `REG_MAGIC_VALUE: begin
                // Note that ready and rdata are basically iomem_ready
                // and iomem_rdata but there is some more glue behind
                // this.
                ready <= 1;
                rdata <= `MAGIC_VALUE;
            end

Direct Memory Access

MMIO registers are appropriate when the CPU needs to initiate some activity in the device, but it ties up the CPU during the load/store instructions that are accessing the device registers. For bulk data transfer it is common to use DMA instead where a device initiates RAM data transfers itself without CPU involvement. This allows the CPU to continue running independently of device activity.

VIRTIO is built around DMA because the virtqueues live in RAM and the device initiates accesses to both the virtqueue data structures as well as the actual data buffers containing the I/O payload.

The iCESugar board has Single Port RAM (SPRAM), which means that it can only be accessed through one interface and that is already connected to the CPU. In order to allow the virtio-serial device to access RAM, it is necessary to multiplex the SPRAM interface between the CPU and the virtio-serial device. I chose to implement a fixed-priority arbiter to do this because fancier a round-robin strategy is not necessary for this project. The virtio-serial device will only access RAM in short bursts, so the CPU will not be starved.

You can look at the spram_mux module to see the implementation, but it basically has 2 input memory interfaces and 1 output memory interface. One input interface is high priority and the other is low priority. The virtio-serial device uses the high priority port and the CPU uses the low priority port.

The virtio-serial device is designed for DMA via a state machine that keeps track of the current memory access that is being performed. When the device sees the ready input asserted, it knows the DMA transfer has completed and it transitions to the next state (often multiple memory accesses are performed in sequence to load the virtqueue data structures).

For example, here are state machine transitions for loading the first two fields of the virtqueue descriptor:

always @(posedge clk) begin
    ...
    if (ram_valid && ram_ready) begin
        ...
        case (state)
        ...
        `STATE_READ_DESCRIPTOR_ADDR_LOW: begin
            desc_addr_low <= ram_rdata;
            ram_addr <= ram_addr + 2;
            state <= `STATE_READ_DESCRIPTOR_LEN;
        end
        `STATE_READ_DESCRIPTOR_LEN: begin
            desc_len <= ram_rdata;
            ram_addr <= ram_addr + 1;
            state <= `STATE_READ_DESCRIPTOR_FLAGS_NEXT;
        end

When the DMA transfer completes in the STATE_READ_DESCRIPTOR_ADDR_LOW state, the virtqueue descriptor's buffer address (low 32 bits) are stored into the desc_addr_low register for later use and ram_addr is updated to the memory address of the virtqueue descriptor's length field. The STATE_READ_DESCRIPTOR_LEN state has similar logic.

In other words, DMA transfers require splitting up the device implementation into a state machine that handles DMA completion in a future clock cycle. In the software world this is similar to callbacks in event loops where code is split up because we need to wait for a completion.

Interrupts

The PicoRV32 soft-core has basic interrupt support, but it does not implement the standard RISC-V Control and Status Registers (CSRs) for interrupt handling. Supporting this would require extra work on the firmware side because the existing riscv-rt Rust crate doesn't implement the PicoRV32 interrupt mechanism. Also, I ended up running low on logic cells in the FPGA, so I disabled the PicoRV32's optional interrupt support to save space. Luckily VIRTIO devices support busy waiting, so interrupts are not required.

Conclusion

This post described how the virtio-serial device is connected to the PicoSoC and how MMIO registers and DMA work. MMIO register implementation was easy, but I spent quite a bit of time debugging waveforms with GTKWave to make sure that the memory interface and spram_mux was both working correctly and not wasting clock cycles. In the next post we'll look at the design of the virtio-serial device.

Building a virtio-serial FPGA device (Part 1): Overview

This is a the first post in a series about building a virtio-serial device in Verilog for a Field Programmable Gate Array (FPGA) development board. This was a project I did in my spare time to become familiar with logic design. I hope these blog posts will offer a glimpse into designing your own devices and FPGA development.

Series table of contents

  1. Part 1: Overview (you are here)
  2. Part 2 - MMIO registers, DMA, and interrupts
  3. Part 3 - virtio-serial device design
  4. Part 4 - Virtqueue processing
  5. Part 5 - UART receiver and transmitter
  6. Part 6 - Writing the RISC-V firmware

Having developed systems software including firmware, device drivers for Linux, and device emulation in QEMU, I wanted to implement a device from scratch on an FPGA, leaving the comfort of the software world and getting some experience with hardware internals. And it didn't take long before I got both the good and the bad experiences. For example, when a device has to process data structures that are not aligned in memory and what a pain that becomes! More on that later.

A few years ago, I ordered a development board with an iCE40UP5k FPGA with the intention of implementing a CPU and maybe a USB controller. I was busy with other things though and the FPGA ended up in a drawer until I recently felt the time was right to dive in.

The muselab iCESugar board that I used for this project costs around 50 USD. It does not support high-speed interfaces like PCIe or Ethernet, but it has 5280 logic cells, 128 KB RAM, 8 MB of flash memory, and a collection of basic I/O including onboard LEDs, UART pins, and PMOD headers. That puts it roughly on par with an Arduino microcontroller board, except you're not stuck with a particular microcontroller because you can design your own or use existing soft-cores, as they are called.

The board can be flashed via USB and loading the manufacturer's demos was an eye opener: it can run several different CPU soft-cores (RISC-V, 6502, etc) and there is even enough capacity to run MicroPython on a soft-core. Typing Python into the prompt and getting output back knowing that the CPU it is running on is just some Verilog code that you can read and modify is neat.

Out the available demo soft-cores, the PicoRV32 RISC-V soft-core interested me most because it's a 32-bit microcontroller with open source compiler toolchain support despite the Verilog implementation being tiny. You can write firmware for the PicoRV32 in Rust, C, etc.

A tiny soft-core is important because it leaves logic cells free for integrating custom devices. There is no point in a fancier soft-core if it complicates the project or limits the number of cells available for my own logic.

The PicoRV32 code comes with an example System-on-Chip (SoC) called PicoSoC that integrates RAM, flash, and UART serial port communication. Custom memory-mapped I/O (MMIO) devices can be wired into the SoC by adding address decoding logic and connecting the devices to the bus. PicoSoC is a great time-saver for developing a custom RV32 SoC because RAM and flash are critical but not particularly exciting to integrate yourself.

The PicoSoC exposes a trivial MMIO register interface for the UART, but I wanted to replace it with a virtio-serial device in order to learn about implementing a more advanced device. VIRTIO devices use Direct Memory Access (DMA) and interrupts, although I ended up not implementing interrupts due to running out of logic cells in the end. This provides an opportunity to implement a device from scratch that is small but not trivial.

While PicoSoC has no PCI bus for the popular VIRTIO PCI transport, it is possible to implement the VIRTIO MMIO transport for this SoC since that just involves selecting some address space for the device's registers where the PicoRV32 CPU can access the device.

Having covered all this, the goal of this project is to write a virtio-serial device in Verilog and integrate it into PicoSoC. This also requires writing firmware that runs on the PicoRV32 soft-core to prove that the virtio-serial device works. In the posts that follow, I'll describe the main stops on the journey to building this.

The next post will cover MMIO registers, DMA, and interrupts.

You can also check out the code for this project at https://gitlab.com/stefanha/virtio-serial-fpga.

Thursday, December 11, 2025

What's new in VIRTIO 1.4

With the VIRTIO 1.4 specification for I/O devices expected to be published soon, here are the most prominent changes. For more fine-grained changes like the latest offloading capabilities in virtio-net devices, please refer to the draft specification.

New device types

The most exciting changes are new device types that allow for entirely new I/O devices to be built with VIRTIO. In 1.4 there are new device types that are especially relevant for automotive and embedded systems.

  • The Controller Area Network (CAN) device provides access to the CAN bus that is popular in automotive systems.
  • The Serial Peripheral Interface (SPI) Controller device provides access to the SPI bus that a large number of devices in embedded systems support. This will make low-level control of SD cards, flash memory, sensors, displays, and more possible via VIRTIO.
  • The Media (V4L2) device exposes Video4Linux over VIRTIO so that webcams and related devices can be supported.
  • The Real Time Clock (RTC) provides clock and alarm functionality.

Infrastructure

In addition to the new devices, VIRTIO itself has evolved to provide new functionality across device types:

  • Device suspend is now supported. Previously a running device could only be reset but not suspended.
  • The Device parts mechanism has been introduced in order to save and restore device state for live migration and snapshot save/load use cases.

This is a nice step forward for VIRTIO. Congratulations to everyone who contributed to VIRTIO 1.4!

Thursday, September 11, 2025

Video and slides available for "Making io_uring Pervasive in QEMU" talk at KVM Forum 2025

My KVM Forum 2025 talk "Making io_uring Pervasive in QEMU" is now available on YouTube. The slides are also available here (PDF).

This talk is about integrating Linux io_uring into QEMU's event loop to enable performance optimizations and use new kernel features available through io_uring. This topic is also relevant for other I/O-intensive applications (network services, software-defined networking or storage systems, databases, etc) that require modifications in order to take advantage of io_uring. The challenge is usually how to move from a reactor-based event loop that monitors file descriptors to a proactor-based event loop that waits for asynchronous operation completion. In QEMU this can be solved by keeping existing fd monitoring users while introducing an API for io_uring request submission that new code can use.

Wednesday, June 25, 2025

Profiling tools I use for QEMU storage performance optimization

A fair amount of the development work I do is related to storage performance in QEMU/KVM. Although I have written about disk I/O benchmarking and my performance analysis workflow in the past, I haven't covered the performance tools that I frequently rely on. In this post I'll go over what's in my toolbox and hopefully this will be helpful to others.

Performance analysis is hard when the system is slow but there is no clear bottleneck. If a CPU profile shows that a function is consuming significant amounts of time, then that's a good target for optimizations. On the other hand, if the profile is uniform and each function only consumes a small fraction of time, then it is difficult to gain much by optimizing just one function (although taking function call nesting into account may point towards parent functions that can be optimized):

If you are measuring just one metric, then eventually the profile will become uniform and there isn't much left to optimize. It helps to measure at multiple layers of the system in order to increase the chance of finding bottlenecks.

Here are the tools I like to use when hunting for QEMU storage performance optimizations.

kvm_stat

kvm_stat is a tool that runs on the host and counts events from the kvm.ko kernel module, including device register accesses (MMIO), interrupt injections, and more. These are often associated with vmentry/vmexit events where control passes between the guest and the hypervisor. Each time this happens there is a cost and it is preferrable to minimize the number of vmentry/vmexit events.

kvm_stat will let you identify inefficiencies when guest drivers are accessing devices as well as low-level activity (MSRs, nested page tables, etc) that can be optimized.

Here is output from an I/O intensive workload:

 Event                                         Total %Total CurAvg/s
 kvm_entry                                   1066255   20.3    43513
 kvm_exit                                    1066266   20.3    43513
 kvm_hv_timer_state                           954944   18.2    38754
 kvm_msr                                      487702    9.3    19878
 kvm_apicv_accept_irq                         278926    5.3    11430
 kvm_apic_accept_irq                          278920    5.3    11430
 kvm_vcpu_wakeup                              250055    4.8    10128
 kvm_pv_tlb_flush                             250000    4.8    10123
 kvm_msi_set_irq                              229439    4.4     9345
 kvm_ple_window_update                        213309    4.1     8836
 kvm_fast_mmio                                123433    2.3     5000
 kvm_wait_lapic_expire                         39855    0.8     1628
 kvm_apic_ipi                                   9614    0.2      457
 kvm_apic                                       9614    0.2      457
 kvm_unmap_hva_range                               9    0.0        1
 kvm_fpu                                          42    0.0        0
 kvm_mmio                                         28    0.0        0
 kvm_userspace_exit                               21    0.0        0
 vcpu_match_mmio                                  19    0.0        0
 kvm_emulate_insn                                 19    0.0        0
 kvm_pio                                           2    0.0        0
 Total                                       5258472          214493

Here I'm looking for high CurAvg/s rates. Any counters at 100k/s are well worth investigating.

Important events:

  • kvm_entry/kvm_exit: vmentries and vmexits are when the CPU transfers control between guest mode and the hypervisor.
  • kvm_msr: Model Specific Register accesses
  • kvm_msi_set_irq: Interrupt injections (Message Signalled Interrupts)
  • kvm_fast_mmio/kvm_mmio/kvm_pio: Device register accesses

sysstat

sysstat is a venerable suite of performance monitoring tools cover CPU, network, disk, memory activity. It can be used equally within guests and on the host. It is like an extended version of the classic vmstat(8) tool.

The mpstat, pidstat, and iostat tools are the ones I use most often:

  • mpstat reports CPU consumption, including %usr (userspace), %sys (kernel), %guest (guest mode), %steal (hypervisor), and more. Use this to find CPUs that are maxed out or poor use of parallelism/multi-threading.
  • pidstat reports per-process and per-thread statistics. This is useful for identifying specific threads that are consuming resources.
  • iostat reports disk statistics. This is useful for comparing I/O statistics between bare metal and guests.

blktrace

blktrace monitors Linux block I/O activity. This can be used equally within guests and on the host. Often it's interesting to capture traces in both the guest and on the host so they can be compared. If the I/O pattern is different then something in the I/O stack is modifying requests. That can be a sign of a misconfiguration.

The blktrace data can be analyzed and plotted with the btt command. For example, the latencies from driver submission to completion can be summarized to find the overhead compared to bare metal.

perf-top

In its default mode, perf-top is a sampling CPU profiler. It periodically collects the CPU's program counter value so that a profile can be generated showing hot functions. It supports call graph recording with the -g option if you want to aggregate nested function calls and find out which parent functions are responsible for the most CPU usage.

perf-top (and its non-interactive perf-record/perf-report cousin) is good at identifying inner loops of programs, excessive memcpy/memset, expensive locking instructions, instructions with poor cache hit rates, etc. When I use it to profile QEMU it shows the host kernel and QEMU userspace activity. It does not show guest activity.

Here is the output without call graph recording where we can see vmexit activity, QEMU virtqueue processing, and excessive memset at the top of the profile:

   3.95%  [kvm_intel]                 [k] vmx_vmexit
   3.37%  qemu-system-x86_64          [.] virtqueue_split_pop
   2.64%  libc.so.6                   [.] __memset_evex_unaligned_erms
   2.50%  [kvm_intel]                 [k] vmx_spec_ctrl_restore_host
   1.57%  [kernel]                    [k] native_irq_return_iret
   1.13%  qemu-system-x86_64          [.] bdrv_co_preadv_part
   1.13%  [kernel]                    [k] sync_regs
   1.09%  [kernel]                    [k] native_write_msr
   1.05%  [nvme]                      [k] nvme_poll_cq

The goal is to find functions or families of functions that consume significant amounts of CPU time so they can be optimized. If the profile is uniform with most functions taking less then 1%, then the bottlenecks are more likely to be found with other tools.

perf-trace

perf-trace is an strace-like tool for monitoring system call activity. For performance monitoring it has a --summary option that shows time spent in system calls and the counts. This is how you can identify system calls that block for a long time or that are called too often.

Here is an example from the host showing a summary of a QEMU IOThread that uses io_uring for disk I/O and ioeventfd/irqfd for VIRTIO device activity:

 IO iothread1 (332737), 1763284 events, 99.9%

   syscall            calls  errors  total       min       avg       max       stddev
                                     (msec)    (msec)    (msec)    (msec)        (%)
   --------------- --------  ------ -------- --------- --------- ---------     ------
   io_uring_enter    351680      0  8016.308     0.003     0.023     0.209      0.11%
   write             390189      0  1238.501     0.002     0.003     0.098      0.08%
   read              121057      0   305.355     0.002     0.003     0.019      0.14%
   ppoll              18707      0    62.228     0.002     0.003     0.023      0.32%

Conclusion

We looked at kvm_stat, sysstat, blktrace, perf-top, and perf-trace. They provide performance metrics from different layers of the system. Another worthy mention is the bcc collection of eBPF-based tools that offers a huge array of performance monitoring and troubleshooting tools. Let me know which tools you like to use!

Tuesday, October 1, 2024

Video and slides available for "IOThread Virtqueue Mapping" talk at KVM Forum 2024

My KVM Forum 2024 talk "IOThread Virtqueue Mapping: Improving virtio-blk SMP scalability in QEMU" is now available on YouTube. The slides are also available here.

IOThread Virtqueue Mapping is a new QEMU feature for configuring multiple IOThreads that will handle a virtio-blk device's virtqueues. This means QEMU can take advantage of the host's Linux multi-queue block layer and assign CPUs to I/O processing. Giving additional resources to virtio-blk emulation allows QEMU to achieve higher IOPS and saturate fast local NVMe drives. This is especially important for applications that submit I/O on many vCPUs simultaneously - a workload that QEMU had trouble keeping up with in the past.

You can read more about IOThread Virtqueue Mapping in this Red Hat blog post.

Sunday, March 31, 2024

Where are the Supply Chain Safe Programming Languages?

Programming languages currently offer few defences against supply chain attacks where a malicious third-party library compromises a program. As I write this, the open source community is trying to figure out the details of the xz-utils backdoor, but there is a long history of supply chain attacks. High profile incidents have made plain the danger of shipping software built from large numbers dependencies, many of them unaudited and under little scrutiny for malicious code. In this post I will share ideas on future supply chain safe programming languages.

Supply Chain Safe Programming Languages?

I'm using the term Supply Chain Safe Programming Languages for languages that defend against supply chain attacks and allow library dependencies to be introduced with strong guarantees about what the dependencies can and cannot do. This type of programming language is not yet widely available as of March 2024, to the best of my knowledge.

Supply chain safety is often associated with software packaging and distribution techniques for verifying that software was built from known good inputs. Although adding supply chain safety tools on top of existing programming languages is a pragmatic solution, I think future progress requires addressing supply chain safety directly in the programming language.

Why today's languages are not supply chain safe

Many existing languages have a module system that gives the programmer control over the visibility of variables and functions. By hiding variable and functions from other modules, one might hope to achieve isolation so that a component like a decompression library could not read a sensitive variable from the program. Unfortunately this level of isolation between components is not really available in popular programming languages today even in languages with public/private visibility features. Visibility is more of a software engineering tool for keeping programs decoupled than an isolation mechanism that actually protects components of a program from each other. There are many ways to bypass visibility.

The fundamental problem is that existing programming languages do not even acknowledge that programs often consist of untrusted components. Compilers and interpreters currently treat the entire input source code as having more or less the same level of trust. Here are some of the ways in which today's programming languages fall short:

  • Unsafe programming languages like C, C++, and even Rust allow the programmer to bypass the type system to do pretty much anything.
  • Dynamic languages like Python and JavaScript have introspection and monkey patching abilities that allow the programmer to hook other parts of the program and escape attempts at isolation.
  • Build systems and metaprogramming facilities like macros allow untrusted components to generate code that executes in the context of another component.
  • Standard libraries provide access to spawning new programs, remapping virtual memory, loading shared libraries written in unsafe languages, hijacking function calls through the linker, raw access to the program's memory space with /proc/self/mem, and so on. All of these can bypass language-level mechanisms for isolating components in a program.

Whatever your current language, it's unlikely that the language itself allows you to isolate components of a program. The best approach we have today for run-time isolation is through sandboxing. Examples of sandboxing approaches include seccomp(2), v8 Isolates for JavaScript, invoking untrusted code in a WebAssembly runtime, or the descendents of chroot(2).

Sandboxes are not supported directly by the programming language and have a number of drawbacks and limitations. Integrating sandboxing into programs is tedious so they are primarily used in the most critical attack surfaces like web browsers or hypervisors. There is usually a performance overhead associated with interacting with the sandbox because data needs to be marshalled or copied. Sandboxing is an opt-in mechanism that doesn't raise the bar of software in general. I believe that supply chain safe programming languages could offer similar isolation but as the default for most software.

What a Supply Chain Safe Programming Language looks like

The goal of a supply chain safe programming language is to isolate components of a program by default. Rather than leaving supply chain safety outside the scope of the language, the language should allow components to be integrated with strong guarantees about what effects they can have on each other. There may be practical reasons to offer an escape hatch to unsafe behavior, but the default needs to be safe.

At what level of granularity should isolation operate? I think modules are too coarse grained because they are often collections of functions that perform very different types of computation requiring different levels of access to resources. The level of granularity should at least go down to the function level within a component, although even achieving module-level granularity would be a major improvement over today's standards.

An example is that a hash table lookup function should be unable to connect to the internet. That way the function can be used without fear of it becoming a liability if it contains bugs or its source code is manipulated by an attacker.

A well-known problem in programming language security is that the majority of languages expose ambient capabilities to all components in a program. Ambient capabilities provide access to resources that are not explicitly passed in to the component. Think of a file descriptor in a POSIX process that is available to any function in the program, including a string compare function that has no business manipulating file descriptors.

Capability-based security approaches are a solution to the ambient capabilities problem in languages today. Although mainstream programming languages do not offer capabilities as part of the language, there have been special-purpose and research languages that demonstrated that this approach works. In a type safe programming language with capability-based security it becomes possible to give components access to only those resources that they require. Usually type safety is the mechanism that prevents capabilities from being created out of thin air, although other approaches may be possible for dynamic languages. The type system will not allow a component to create itself a new capability that the component does not already possess.

Capability-based security addresses safety at runtime, but it does not address safety at compile time. If we want to compose programs from untrusted components then it is not possible to rely on today's build scripts, code generators, or macro systems. The problem is that they can be abused by a component to execute code in the context of another component.

Compile-time supply chain safety means isolating components so their code stays within their component. For example, a "leftpad" macro that pads a string literal with leading spaces would be unsafe if it can generate code that is compiled as part of the main program using the macro. Similarly, a build script for the leftpad module must not be able to affect or escape the build environment.

Macros, build scripts, code generators, and so on are powerful tools that programmers find valuable. The challenge for supply chain safe programming languages is to harness that power so that it remains convenient to use without endangering safety. One example solution is running build scripts in an isolated environment that cannot affect other components in the program. This way a component can take advantage of custom build-time behavior without endangering the program. However, it is unclear to me how far inter-component facilities like macros can be made safe, if at all.

Conclusion

I don't have the answers or even a prototype, but I think supply chain safe programming languages are an inevitability. Modern programs are composed of many third-party components yet we do not have effective techniques for confining components. Languages treat the entire program as trusted rather than as separate untrusted components that must be isolated.

Hopefully we will begin to see new mainstream programming languages emerge that are supply chain safe, not just memory safe!

Wednesday, March 6, 2024

How to access libvirt domains in KubeVirt

KubeVirt makes it possible to run virtual machines on Kubernetes alongside container workloads. Virtual machines are configured using VirtualMachineInstance YAML. But under the hood of KubeVirt lies the same libvirt tooling that is commonly used to run KVM virtual machines on Linux. Accessing libvirt can be convenient for development and troubleshooting.

Note that bypassing KubeVirt must be done carefully. Doing this in production may interfere with running VMs. If a feature is missing from KubeVirt, then please request it.

The following diagram shows how the user's VirtualMachineInstance is turned into a libvirt domain:

Accessing virsh

Libvirt's virsh command-line tool is available inside the virt-launcher Pod that runs a virtual machine. First determine vm1's virt-launcher Pod name by filtering on its label (thanks to Alice Frosi for this trick!):

$ kubectl get pod -l vm.kubevirt.io/name=vm1
NAME                      READY   STATUS    RESTARTS   AGE
virt-launcher-vm1-5gxvg   2/2     Running   0          8m13s

Find the name of the libvirt domain (this is guessable but it doesn't hurt to check):

$ kubectl exec virt-launcher-vm1-5gxvg -- virsh list
 Id   Name          State
-----------------------------
 1    default_vm1   running

Arbitrary virsh commands can be invoked. Here is an example of dumping the libvirt domain XML:

$ kubectl exec virt-launcher-vm1-5gxvg -- virsh dumpxml default_vm1
<domain type='kvm' id='1'>
  <name>default_vm1</name>
...

Viewing libvirt logs and full the QEMU command-line

The libvirt logs are captured by Kubernetes so you can view them with kubectl log <virt-launcher-pod-name>. If you don't know the virt-launcher pod name, check with kubectl get pod and look for your virtual machine's name.

The full QEMU command-line is part of the libvirt logs, but unescaping the JSON string is inconvenient. Here is another way to get the full QEMU command-line:

$ kubectl exec <virt-launcher-pod-name> -- ps aux | grep qemu

Customizing KubeVirt's libvirt domain XML

KubeVirt has a feature for customizing libvirt domain XML called hook sidecars. After the libvirt XML is generated, it is sent to a user-defined container that processes the XML and returns it back. The libvirt domain is defined using this processed XML. To learn more about how it works, check out the documentation.

Hook sidecars are available when the Sidecar feature gate is enabled in the kubevirt/kubevirt custom resource. Normally only the cluster administrator can modify the kubevirt CR, so be sure to check when trying this feature:

$ kubectl auth can-i update  kubevirt/kubevirt -n kubevirt
yes

Although you can provide a complete container image for the hook sidecar, there is a shortcut if you just want to run a script. A generic hook sidecar image is available that launches a script which can be provided as a ConfigMap. Here is example YAML including a ConfigMap that I've used to test the libvirt IOThread Virtqueue Mapping feature:

---
apiVersion: kubevirt.io/v1
kind: KubeVirt
metadata:
  name: kubevirt
  namespace: kubevirt
spec:
  configuration:
    developerConfiguration: 
      featureGates:
        - Sidecar
---
apiVersion: cdi.kubevirt.io/v1beta1
kind: DataVolume
metadata:
  name: "fedora"
spec:
  storage:
    accessModes:
        - ReadWriteOnce
    resources:
      requests:
        storage: 5Gi
  source:
    http:
      url: "https://download.fedoraproject.org/pub/fedora/linux/releases/38/Cloud/x86_64/images/Fedora-Cloud-Base-38-1.6.x86_64.raw.xz"
---
apiVersion: v1
kind: ConfigMap
metadata:
  name: sidecar-script
data:
  my_script.sh: |
    #!/usr/bin/env python3
    import xml.etree.ElementTree as ET
    import os.path
    import sys
    
    NUM_IOTHREADS = 4
    VOLUME_NAME = 'data' # VirtualMachine volume name
    
    def main(xml):
        domain = ET.fromstring(xml)
    
        domain.find('iothreads').text = str(NUM_IOTHREADS)
    
        disk = domain.find(f"./devices/disk/alias[@name='ua-{VOLUME_NAME}']..")
        driver = disk.find('driver')
        del driver.attrib['iothread']
        iothreads = ET.SubElement(driver, 'iothreads')
        for i in range(NUM_IOTHREADS):
            iothread = ET.SubElement(iothreads, 'iothread')
            iothread.set('id', str(i + 1))
    
        ET.dump(domain)
    
    if __name__ == "__main__":
        # Workaround for https://github.com/kubevirt/kubevirt/issues/11276
        if os.path.exists('/tmp/ran-once'):
            main(sys.argv[4])
        else:
            open('/tmp/ran-once', 'wb')
            print(sys.argv[4])
---
apiVersion: kubevirt.io/v1
kind: VirtualMachineInstance
metadata:
  creationTimestamp: 2018-07-04T15:03:08Z
  generation: 1
  labels:
    kubevirt.io/os: linux
  name: vm1
  annotations:
    hooks.kubevirt.io/hookSidecars: '[{"args": ["--version", "v1alpha3"],
      "image": "kubevirt/sidecar-shim:20240108_99b6c4bdb",
      "configMap": {"name": "sidecar-script",
                    "key": "my_script.sh",
                    "hookPath": "/usr/bin/onDefineDomain"}}]'
spec:
  domain:
    ioThreadsPolicy: auto
    cpu:
      cores: 8
    devices:
      blockMultiQueue: true
      disks:
      - disk:
          bus: virtio
        name: disk0
      - disk:
          bus: virtio
        name: data
    machine:
      type: q35
    resources:
      requests:
        memory: 1024M
  volumes:
  - name: disk0
    persistentVolumeClaim:
      claimName: fedora
  - name: data
    emptyDisk:
      capacity: 8Gi

If you need to go down one level further and customize the QEMU command-line, see my post on passing QEMU command-line options in libvirt domain XML.

More KubeVirt debugging tricks

The official KubeVirt documentation has a Virtualization Debugging section with more tricks for customizing libvirt logging, launching QEMU with strace or gdb, etc. Thanks to Alice Frosi for sharing the link!

Conclusion

It is possible to get libvirt access in KubeVirt for development and testing. This can make troubleshooting easier and it gives you the full range of libvirt domain XML if you want to experiment with features that are not yet exposed by KubeVirt.

Thursday, January 25, 2024

Key-Value Stores: The Foundation of File Systems and Databases

File systems and relational databases are like cousins. They share more than is apparent at first glance.

It's not immediately obvious that relational databases and file systems rely upon the same underlying concept. That underlying concept is the key-value store and this article explores how both file systems and databases can be implemented on top of key-value stores.

The key-value store interface

Key-value stores provide an ordered map data structure. A map is a data structure that supports storing and retrieving from a collection of pairs. It's called a map because it is like a mathematical relation from a given key to an associated value. These are the key-value pairs that a key-value store holds. Finally, ordered means that the collection can be traversed in sorted key order. Not all key-value store implementations support ordered traversal, but both file systems and databases need this property as we shall see.

Here is a key-value store with an integer key and a string value:

Notice that the keys can be enumerated in sorted order: 2 → 14 → 17.

A key-value store provides the following interface for storing and retrieving values by a given key:

  • put(Key, Value) - an insert/update operation that stores a value for a given key
  • get(Key) -> Value - a lookup operation that retrieves the most recently stored value for a given key
  • first() -> Key, last() -> Key, next(Key) -> Key, prev(Key) -> Key - a cursor API that enumerates keys in sorted order

You've probably seen this sort of API if you have explored libraries like LevelDB, RocksDB, LMDB, BoltDB, etc or used NoSQL key-value stores. File systems and databases usually implement their own customized key-value stores rather than use these off-the-shelf solutions.

Why key-value stores are necessary

Let's look at how the key-value store interface relates to disks. Disks present a range of blocks that can be read or written at their block addresses. Disks can be thought of like arrays in programming. They have O(1) lookup and update time complexity but inserting or removing a value before the end of the array is O(n) because subsequent elements need to be copied. They are efficient for dense datasets where every element is populated but inefficient for sparse datasets that involve insertion and removal.

Workloads that involve insertion or removal are not practical when the cost is O(n) for realistic sizes of n. That's why programs often use in-memory data structures like hash tables or balanced trees instead of arrays. Key-value stores can be thought of as the on-disk equivalent to these in-memory data structures. Inserting or removing values from a key-value store takes sub-linear time, perhaps O(log n) or even better amortized time. We won't go into the data structures used to implement key-value stores, but B+ trees and Log-Structured Merge-Trees are popular choices.

This gives us an intuition about when key-value stores are needed and why they are an effective tool. Now let's look at how file systems and databases can be built on top of key-value stores next.

Building a file system on a key-value store

First let's start with how data is stored in files. A file system locates file data on disk by translating file offsets to Logical Block Addresses (LBAs). This is necessary because file data may not be stored contiguously on disk and files can be sparse with unallocated "holes" where nothing has been written yet. Thus, each file can be implemented as a key-value store with <Offset, <LBA, Length>> key-value pairs that comprise the translations needed to locate data on disk:

Reading and writing to the file involves looking up Offset -> LBA translations and inserting new translations when new blocks are allocated for the file. This is a good fit for a key-value store, but it's not the only place where file systems employ key-value stores.

File systems track free blocks that are not in used by files or metadata so that the block allocator can quickly satisfy allocation requests. This can be implemented as a key-value store with <LBA, Length> key-value pairs representing all free LBA ranges.

If the block allocator needs to satisfy contiguous allocation requests then a second key-value store with <Length, LBA> key-value pairs can serve as an efficient lookup or index. A best-fit allocator uses this key-value store by looking up the requested contiguous allocation size. Either an free LBA range of the matching size will be found or the next ordered key can be traversed when lookup fails to find a bigger free range capable of satisfying this allocation request. This is an important pattern with key-value stores: we can have one main key-value store plus one or more indices that are derived from the same key-value pairs but use a different datum as the key than the primary key-value store, allowing efficient lookups and ordered traversal. The same pattern will come up in databases too.

Next, let's look at how to represent directory metadata in a key-value store. Files are organized into a hierarchy of directories (or folders). The file system stores the directory entries belonging to each directory. Each directory can be organized as a key-value store with filenames as keys and inode numbers as values. Path traversal consists of looking up directory entries in each directory along file path components like home, user, and file in the path /home/user/file. When a file is created, a new directory entry is inserted. When a file is deleted, its directory entry is removed. The contents of a directory can be listed by traversing the keys.

Some file systems like BTRFS use key-value stores for other on-disk structures such as snapshots, checksums, etc, too. There is even a root key-value store in BTRS from which all these other key-value stores can be looked up. We'll see that the same concept of a "forest of trees" or a root key-value store that points to other key-value stores also appears in databases below.

Update (2025-07-21): Another good example of the connection between file systems and key-value stores is the "File Systems Unfit as Distributed Storage Backends: Lessons from 10 Years of Ceph Evolution" paper (PDF) where a key-value store is used to hold the metadata and raw blocks are used to hold file data.

Building a database on a key-value store

The core concept in relational databases is the table, which contains the rows of the data we wish to store. The table columns are the various fields that are stored by each row. One or more columns make up the primary key by which table lookups are typically performed. The table can be implemented as a key-value store using the primary key columns as the key and the remainder of the columns as the value:

This key-value store can look up rows in the table by their Id. What if we want to look up a row by Username instead?

To enable efficient lookups by Username, a secondary key-value store called an index maintains a mapping from Username to Id. The index does not duplicate all the columns in the table, just the Username and Id. To perform a query like SELECT * FROM Users WHERE Username = 'codd', the index is first used to look up the Id and then the remainder of the columns are looked up from the table.

SQLite's file format documentation shows the details of how data is organized along these lines and the power of key-value stores. The file format has a header the references the "table b-tree" that points to the roots of all tables. This means there is an entry point key-value store that points to all the other key-value stores associated with tables, indices, etc in the database. This is similar to the forest of trees we saw in the BTRFS file system where the key-value store acts as the central data structure tying everything together.

Conclusion

If a disk is like an array in programming, then a key-value store is like a dict. It offers a convenient interface for storing and retrieving sparse data with good performance. Both file systems and databases are abundant with sparse data and therefore fit naturally on top of key-value store. The actual key-value store implementations inside file systems and databases may be specialized variants of B-trees and other data structures that don't even call themselves key-value stores, but the fundamental abstraction upon which file systems and databases are built is the key-value store.

Tuesday, January 2, 2024

QEMU AioContext removal and how it was done

This post is about the AioContext lock removal in QEMU 9.0 (planned for release in 2024), how we got here, and what it means for multi-threaded code in QEMU.

Early QEMU as a single-threaded program

Until 2009 QEMU was largely a single-threaded program. This had the benefit that the code didn't need to consider thread-safety and was thus simpler and less bug-prone. The main loop interleaved running the next piece of guest code and handling external events such as timers, disk I/O, and network I/O. This architecture had the downside that emulating multi-processor guests was bottlenecked by the single host CPU on which QEMU ran. There was no parallelism and this became problematic as multi-processor guests became popular.

Multi-threading with vCPU threads and the Big QEMU Lock

The architecture was modified to support running dedicated vCPU threads for KVM guests. This made parallelism possible for multi-processor guests but the feature was initially only available for KVM guests. The Multi-Threaded TCG (MTTCG) feature eventually allowed translated code to also take advantage of vCPU threads in 2016.

A straightforward approach to making all existing code thread-safe was taken: the Big QEMU Lock (BQL) was introduced to serialize access to QEMU's internal state. The BQL is a single global mutex that is used to protect the majority of QEMU's internal state. KVM vCPU threads do not need access to QEMU's internal state while executing guest code, so they don't hold the BQL most of the time. The main loop thread drops the BQL while blocking in ppoll(2) and this allows vCPU threads to acquire the lock when they come out of guest code.

Multi-threading with IOThreads and the AioContext lock

Although the vCPU bottleneck had been solved, device emulation still ran with the BQL held. This meant that only a single QEMU thread could process I/O requests at a time. For I/O bound workloads this was a bottleneck and especially disk I/O performance suffered due to this limitation. My first attempt at removing the bottleneck in 2012 amounted to writing a new "dataplane" code path outside the BQL, but it lacked the features that users needed like disk image file formats, I/O throttling, etc because it couldn't use the existing code that relied on the BQL. The long term solution would be introducing thread-safety to the existing code and that led to the creation of the AioContext lock.

The AioContext lock was like a mini-BQL but for an event loop (QEMU calls this an AioContext) instead of the entire program. Initially the event loop would acquire the lock while running event handlers, thereby ensuring mutual exclusion for all handlers associated with the event loop. Another thread could acquire the lock to stop the event loop from running and safely access variables. This was a crude approach though and propagated the BQL way of thinking further. QEMU began to suffer from deadlocks and race conditions now that multi-threading was possible. Although I wrote developer documentation about how the model worked, it became tricky to gain confidence in the safety of the code as the whole QEMU block layer needed to grapple with AioContext locking and did so incompletely and inconsistently.

The upshot of all of this was that disk I/O processing could run in a dedicated event loop thread (QEMU calls this an IOThread) while the QEMU monitor could acquire the AioContext lock for a brief moment to inspect the emulated disk for an "info block" monitor command, for example. Unlike the earlier "dataplane" approach, it was now possible for the QEMU block layer to run outside the BQL and instead rely on the AioContext lock.

Removing the AioContext lock

Paolo Bonzini had the idea to gradually eliminate the AioContext lock in favor of fine-grained locks because we kept hitting problems with the AioContext lock that I described above. His insight was to change the model so that handler functions would explicitly take their AioContext's lock instead acquiring the lock around the entire event loop iteration. The advantage to letting handlers take the lock was that they could also replace it with another mechanism. Eventually it would be possible to move away from the AioContext lock.

What came after was a multi-year journey that I credit to Paolo's vision. Emanuele Giuseppe Esposito worked with Paolo on putting fine-grained locking into practice and on sorting through the entire QEMU block layer to determine under which threads and locks variables were accessed. This was a massive effort and required a lot of persistence. Kevin Wolf figured out how to use clang's Thread Safety Analysis (TSA) to check some of the locking rules at compile time. Kevin also spent a lot of time protecting the block driver graph with a reader/writer lock so that in-flight I/O does not crash amidst modifications to the graph. Emanuele and Kevin gave a talk at KVM Forum 2023 about the larger QEMU multi-queue block layer effort and the slides are available here (PDF).

Once everything that previously relied on the AioContext lock had switched to another form of thread-safety, it was possible to remove the AioContext lock as nothing used it anymore. The BQL is still widely used and covers global state that is accessed from few threads. Code that can run in any IOThread now uses its own locks or other mechanisms. The complexity of the codebase is still roughly the same as with the AioContext lock, but now there are fine-grained locks, which are easier to understand and there are fewer undocumented locking assumptions that led to deadlocks and races in the past.

Conclusion

QEMU's AioContext lock enabled multi-threading but was also associated with deadlocks and race conditions due to its ambient nature. From QEMU 9.0 onwards, QEMU will switch to fine-grained locks that are more localized and make thread-safety more explicit. Changing locking in a large program is time-consuming and difficult. It took a multi-person multi-year effort to complete this work, but it forms the basis for further work including the QEMU multi-queue block layer effort that push multi-threading further in QEMU.