Descriptor Rings and the Producer-Consumer Contract

A device that performs work on behalf of a processor needs a way to be told what to do. The interface cannot be a function call, because the device is not executing the processor’s code; it must be a data structure in memory that both sides can see, with a protocol for handing ownership back and forth. Nearly every modern device uses the same answer: a ring of fixed-size descriptors, an index the driver writes, an index the device writes, and a rule that says which of them owns a given slot at any moment.

The shape of the structure

A ring is an array of descriptors allocated in memory that the device can read. Each descriptor contains enough information to locate one unit of work: the address of a buffer, its length, and some flags the device interprets. The array is treated as circular; the device walks it in order and wraps from the last entry to the first.

Two indices accompany the array, and their placement matters. The driver’s index lives in host memory and is written by the driver before it notifies the device. The device’s index is written by the device into memory, where the driver can read it. Because the device’s writes must be visible to the driver without a round trip, that index is a target for device DMA — the device writes the value directly into a host-memory location the driver polls, rather than exposing it as a register the driver must read across the interconnect.

The ring is sized to a power of two so that the wrap is a mask rather than a modulo. A 256-entry ring wraps with a bitwise AND against 255, which costs a gate and no divider. This is the same reasoning that makes power-of-two buffer sizes ubiquitous in hardware, and it is why ring sizes are almost never round decimal numbers.

The ownership bit, and why indices alone are not enough

The naive protocol is: the driver advances its index to publish new descriptors, the device advances its own index to report completions, and the driver infers how much space is free from the difference. This works until the ring is full. With a ring of $N$ entries, the driver can publish $N$ descriptors and the two indices become equal — indistinguishable from an empty ring. The usual fix in software queues is to keep one slot empty so that equal indices mean empty and adjacent indices mean full, and that trick is used here too, but it is not sufficient on its own.

The deeper problem is that a slot’s state cannot be inferred from the indices when the device may be reading a descriptor that the driver has already moved past. Consider a ring where the driver has published entries 0 through 7 and the device has completed 0 through 3. The driver may now reuse slots 4 through 7 once the device has finished with them, but it must not reuse slot 8’s memory while the device is still reading it. Indices tell the driver where the device’s progress is, but the driver’s reuse of a slot is a separate decision that must happen only after the device is done with it.

Two mechanisms resolve this, and real devices use one or both. The first is a completion queue separate from the submission queue: the device writes a completion entry containing the identifier of the request it finished, and the driver consumes completions rather than inferring them from an index. This decouples submission depth from completion depth and makes the driver’s bookkeeping explicit. The second is an ownership bit inside each descriptor: the driver sets a bit to hand a slot to the device, and the device clears it when the slot is free. The driver’s rule becomes “a slot may be rewritten only when the ownership bit has been cleared”, which is checkable per slot instead of inferred from a global counter.

#include <stdint.h>
#include <stdbool.h>

#define RING 256
#define MASK (RING - 1)

struct desc {
    uint64_t addr;
    uint32_t len;
    uint16_t flags;
    uint16_t owner;   /* 1 = device owns the slot */
};

struct ring {
    struct desc d[RING];
    volatile uint32_t head;   /* driver writes: next slot to fill */
    volatile uint32_t tail;   /* device writes: next slot to complete */
};

/* publish one buffer; returns false when the ring has no free slot */
bool submit(struct ring *r, uint64_t addr, uint32_t len)
{
    uint32_t h = r->head;
    if (((h + 1) & MASK) == (r->tail & MASK))
        return false;                 /* full: one slot kept empty */

    struct desc *s = &r->d[h & MASK];
    s->addr = addr;
    s->len = len;
    s->flags = 0;
    s->owner = 1;                     /* hand ownership to the device */
    __atomic_thread_fence(__ATOMIC_RELEASE);
    r->head = h + 1;                  /* publish after the descriptor is written */
    return true;
}

The fence before the index update is not decoration. Without it the processor may publish the new head before the descriptor contents are visible, and the device — which reads memory directly and does not participate in the core’s ordering — may fetch a half-written descriptor. The release fence orders the descriptor writes before the index write; the device’s read of the index then acts as the acquire side.

Reclaim is the mirror image. The driver walks forward from its own tail and stops at the first slot the device still owns, so the free region is always a contiguous run and a slot cannot be reused out of order.

/* reclaim slots the device has finished with */
uint32_t reap(struct ring *r)
{
    uint32_t t = r->tail, done = 0;

    while ((r->head & MASK) != (t & MASK)) {
        struct desc *s = &r->d[t & MASK];
        if (s->owner) break;          /* still owned by the device */
        t++; done++;                  /* the device cleared owner: slot is free */
    }
    r->tail = t;
    return done;
}

The doorbell, and why it is a separate register

The driver could publish an index and let the device poll memory, but polling memory continuously costs the device power and the interconnect bandwidth. Instead the driver writes the index to a doorbell register, which is an MMIO write that tells the device new work exists. The device then reads the descriptors at its leisure.

The doorbell is a small optimization with a large consequence: it is a posted write, so the driver does not learn when the device has seen it. A driver that frees the buffer immediately after ringing the doorbell has a use-after-free. The buffer must stay alive until a completion arrives, and the completion arrives through a different channel — the device’s write to the tail index, or an interrupt, or both.

Because doorbell writes are themselves expensive, drivers batch them. A driver that publishes sixteen descriptors and rings once saves fifteen transactions but adds latency to each request. The natural trade is a threshold: ring immediately if the device is idle, otherwise accumulate until a batch size is reached. This is the same batching logic that governs the interrupt side, described in Interrupt Moderation and Event Delivery at High Rates. The doorbell itself is an ordinary MMIO write, subject to the posted-write rules covered in Memory-Mapped Registers and the Ordering Rules Behind a Store, which is why a driver that needs the device to see an index before some other operation must order the two explicitly rather than assuming the writes arrive in program order.

Memory ordering across the boundary

The core and the device do not share an ordering domain, and the rules differ by architecture. On a machine with a strong memory model, a store followed by a store is observed in order by a third party in most cases, but device accesses are frequently mapped with attributes that weaken even that. On a weakly ordered machine, the compiler and the processor are both free to move the index write before the descriptor writes unless a barrier prevents it.

The portable discipline is three rules. Write the descriptor fully before publishing it. Publish it with a release operation, and consume the device’s index with an acquire operation. And never rely on the ordering of two MMIO writes without a read-back or a fence between them, because posted writes may be reordered within their traffic class.

The device side has its own obligations, and they are specified by the device rather than by the architecture. A device that writes completions must ensure the completion data reaches memory before the index that announces it, or the driver may read a completion whose payload is stale. Devices implement this with an internal barrier before the index write, and the requirement is usually stated in the device’s programming manual as an ordering rule on the completion path.

Wrap-around and the arithmetic of indices

The indices are free-running counters, not masked positions. A 32-bit head that increments on every submission wraps after roughly four billion operations, and the slot position is head & MASK. This choice makes “the ring is full” and “the ring is empty” distinguishable without a separate count, and it makes the difference head - tail the number of outstanding entries — as long as the difference is computed in the counter’s own width and the counter does not overflow between reads.

That last condition is the subtle one. If the driver reads a 32-bit tail and the device updates a 64-bit counter, or vice versa, a wrap can occur between two reads and produce a difference that looks negative or enormous. Rings whose 16-bit indices are read against a device’s 32-bit counter produce exactly this class of bug. The rule is that both sides must agree on the counter width and the driver must read the value once, not twice.

A second arithmetic hazard is the difference between “number of entries the device has completed” and “number of entries the driver has reclaimed”. These diverge whenever the driver batches reclamation, and a driver that uses the device’s tail as its own free count will overrun. The two counters must be maintained separately, and the invariant is that the driver’s reclaim pointer never passes the device’s completion pointer.

What the structure costs

The ring trades memory for synchronization. A 256-entry ring of 16-byte descriptors is 4 KiB, one page, which is a convenient size for mapping and for keeping the whole structure within a single translation. Larger rings buy burst absorption and cost cache footprint: the device walks the ring linearly, so a ring that exceeds the last-level cache is re-read from memory on every pass, and the descriptors compete with the data buffers for cache capacity.

The structure also fixes the granularity of work. One descriptor is one unit, so a transfer smaller than the descriptor overhead is dominated by bookkeeping, and a transfer much larger than one buffer must be split across several descriptors with a flag to mark the last. Devices that support chaining or scatter-gather lists encode the chain inside the descriptor, which turns the ring into a two-level structure: the ring holds pointers, and the pointed-to lists hold the actual buffer addresses. The extra indirection is the price of describing a transfer larger than a single descriptor can address.

The failure modes are correspondingly structural. A driver that publishes an index without a fence produces intermittent corruption that reproduces only under load. A driver that reuses a slot before the ownership bit clears produces data that the device writes into a buffer that has been repurposed. And a device whose completion index advances past a descriptor the driver never wrote produces work on stale data. All three are eliminated by the same discipline: one owner per slot at any instant, and a release barrier at every handoff.