vault

The Multi-Queue Block Layer blk-mq

14 min read

The Multi-Queue Block Layer blk-mq

The multi-queue block layer — blk-mq — is the kernel subsystem that turns a stream of block-I/O descriptors (bios) into device commands while scaling across many CPU cores. It replaced the original single-queue block layer, in which every device had one request_queue guarded by one global spinlock (queue_lock) — a structure that bottlenecked badly once devices could service millions of I/O operations per second (IOPS) instead of hundreds (LWN, “The multiqueue block layer”). blk-mq’s central idea is a two-level queue model: many per-CPU software staging queues where requests are buffered, merged, and scheduled, feeding a small fixed number of hardware dispatch queues that map onto the device’s own submission queues (kernel docs). It was merged in Linux 3.13 (2014), and as of Linux 5.0 (March 2019) it is the only block layer: the legacy single-queue path and its schedulers (CFQ, the old deadline, noop) were deleted (Axboe, “block: remove legacy IO schedulers”, Oct 2018). This note is the architectural overview; the two queue levels are dissected in Software and Hardware Queues in blk-mq.

This note is pinned to Linux 6.12 LTS (released 2024-11-17; the current newest LTS at the time of writing is 6.18, 2025-11-30). Structural facts below are verified against the v6.12 source blobs listed in sources.

Mental Model

Think of blk-mq as a two-stage conveyor belt with many feeder lanes and a few exit gates. Each CPU has its own feeder lane (a software staging queue, struct blk_mq_ctx) into which the I/O it generates is dropped — no two CPUs share a lane, so they never fight over a lock to insert work. Periodically the contents of the feeder lanes are gathered, optionally reordered by an I/O scheduler, and handed to one of a small number of exit gates (hardware dispatch queues, struct blk_mq_hw_ctx, universally abbreviated hctx). Each exit gate corresponds to a real submission queue on the device — a Non-Volatile Memory Express (NVMe) controller, for instance, exposes one submission/completion queue pair per CPU, and blk-mq mirrors that.

The single-queue layer had one lane and one gate for the whole device, with a single lock on the lane. On a machine with dozens of cores all issuing I/O, that lock “will bounce frequently between the processors” (LWN) — the cache line holding the lock ping-pongs between caches, and throughput collapses well below what the hardware can absorb. blk-mq removes the shared lane.

flowchart TB
  subgraph CPUS["Submitting CPUs"]
    C0["CPU 0"]
    C1["CPU 1"]
    C2["CPU 2"]
    C3["CPU 3"]
  end
  C0 --> SW0["sw queue<br/>blk_mq_ctx[0]"]
  C1 --> SW1["sw queue<br/>blk_mq_ctx[1]"]
  C2 --> SW2["sw queue<br/>blk_mq_ctx[2]"]
  C3 --> SW3["sw queue<br/>blk_mq_ctx[3]"]
  SW0 --> SCHED["I/O scheduler<br/>(mq-deadline / BFQ / Kyber / none)<br/>+ merging"]
  SW1 --> SCHED
  SW2 --> SCHED
  SW3 --> SCHED
  SCHED --> HW0["hw queue<br/>blk_mq_hw_ctx[0]<br/>(hctx)"]
  SCHED --> HW1["hw queue<br/>blk_mq_hw_ctx[1]<br/>(hctx)"]
  HW0 --> SQ0["device submission<br/>queue 0"]
  HW1 --> SQ1["device submission<br/>queue 1"]
  SQ0 --> DEV["Storage device"]
  SQ1 --> DEV

The blk-mq two-level model. What it shows: each CPU inserts into its own software staging queue (no inter-CPU lock contention on insert); the staging queues are drained through an optional I/O scheduler and merging step into a small set of hardware dispatch queues (hctx), each bound to a real device submission queue. The insight: the per-CPU feeder lanes are the whole scaling story — submission is lock-free across cores, and the only fan-in happens at the hardware queues, which the device is built to handle in parallel.

Why the Single Queue Had to Die

The original block layer was designed when “a high-performance drive could handle hundreds of I/O operations per second” (LWN). Its core data structure was a single request_queue per device, holding a linked list of pending struct request objects, protected by one spinlock conventionally called queue_lock. Every operation — inserting a freshly built request, merging an adjacent bio into an existing request, the I/O scheduler picking the next request to dispatch, the driver pulling a request off for the device — had to take that one lock.

This is fine when the device is the bottleneck. It is catastrophic when the lock is the bottleneck. LWN describes the request queue bluntly as “one of the biggest bottlenecks in the entire system. It is protected by a single lock which, on a large system, will bounce frequently between the processors. It is a linked list, a notably cache-unfriendly data structure especially when modifications must be made” (LWN). A linked list is pointer-chasing — each node is a separate cache line — so even traversing the queue thrashes the cache, and every modification dirties a line that other CPUs may hold.

Solid-state drives, and then NVMe devices, broke this model. An NVMe SSD can sustain hundreds of thousands to millions of IOPS, and the protocol is designed for parallelism: the host and controller communicate through paired ring buffers in host memory (a submission queue and a completion queue), and a controller can expose one such pair per CPU. Feeding such a device through a single serialized software queue wastes most of its capacity. The fix has to make submission itself parallel — and that is exactly what per-CPU software staging queues do.

blk-mq, the work of Jens Axboe and Shaohua Li, was the answer (LWN). It was merged into mainline in 3.13 (early 2014) and became feature-complete around 3.16 (Thomas-Krenn wiki). The SCSI (Small Computer System Interface) layer gained a multi-queue path, scsi-mq, in 3.17 (scsi-mq paper, Caldwell 2015). For several years the two block layers coexisted, drivers being converted one by one.

The 5.0 Cutover — blk-mq Becomes the Only Block Layer

By late 2018 the conversion was complete enough that Axboe could delete the old path. In a 30-patch series titled “blk-mq driver conversions and legacy path removal,” patch 20 — “block: remove legacy IO schedulers” — deleted block/cfq-iosched.c (4,916 lines), block/deadline-iosched.c (560 lines), and block/noop-iosched.c (124 lines), authored by Jens Axboe on 31 October 2018 (patchwork). The single-queue request-processing machinery went with them.

These changes shipped in Linux 5.0, released March 2019. From 5.0 onward there is exactly one block layer — blk-mq — and exactly one family of I/O schedulers: the multi-queue ones, mq-deadline (the new default), BFQ (Budget Fair Queueing), Kyber, and none (a no-op FIFO pass-through). An observer upgrading to 5.0.0-rc8 confirmed that CFQ and the legacy deadline scheduler simply no longer existed (Berthon, 2019). The schedulers are covered in Linux IO Schedulers Overview; do not confuse the deleted single-queue deadline with the surviving mq-deadline.

Uncertain

Verify: that the single-queue request path (the request_fn-style queues, not just the legacy schedulers) was fully removed in the same 5.0 release rather than trickling out across 5.0–5.1. Reason: the cited primary source (the patchwork patch) is specifically the scheduler removal; the broader single-queue infrastructure removal is corroborated by secondary sources (Berthon) but I did not fetch the exact merge commit for the request_fn deletion. To resolve: locate the mainline commit removing blk_queue_make_request/request_fn legacy queueing and confirm its first tagged release. uncertain

How a Driver Registers with blk-mq

The driver-facing contract is two structures and a short registration sequence. A driver fills in a struct blk_mq_ops — a table of callbacks — and a struct blk_mq_tag_set describing the queue geometry, then asks blk-mq to build a queue.

The operations table (from include/linux/blk-mq.h, v6.12) centers on one mandatory callback:

struct blk_mq_ops {
    /* Queue a new request from block IO. (mandatory) */
    blk_status_t (*queue_rq)(struct blk_mq_hw_ctx *,
                             const struct blk_mq_queue_data *);
 
    /* Queue a list of requests, all belonging to the same queue. */
    void (*queue_rqs)(struct request **rqlist);
 
    /* Called to poll for completion of a specific tag. */
    int (*poll)(struct blk_mq_hw_ctx *, struct io_comp_batch *);
 
    /* Mark the request as complete. */
    void (*complete)(struct request *);
 
    /* Per-hardware-queue and per-request setup/teardown. */
    int  (*init_hctx)(struct blk_mq_hw_ctx *, void *, unsigned int);
    int  (*init_request)(struct blk_mq_tag_set *set, struct request *,
                         unsigned int, unsigned int);
 
    /* Let the driver supply its own CPU->queue mapping. */
    void (*map_queues)(struct blk_mq_tag_set *set);
    /* ... timeout, get_budget/put_budget, commit_rqs, etc. */
};

Line by line: queue_rq is the heart of the driver — blk-mq calls it with a hardware-queue pointer and a blk_mq_queue_data (which carries rq, the request, and last, a hint that this is the last of a batch so the driver can ring the doorbell once). The driver translates the struct request into a device command and submits it, returning BLK_STS_OK on success or BLK_STS_RESOURCE/BLK_STS_DEV_RESOURCE to push back. queue_rqs is the batched variant; a driver “is guaranteed that each request belongs to the same queue” (comment in blk-mq.h) and may leave un-submitted requests on the list for blk-mq to retry individually. poll drives polled completions for low-latency I/O. init_hctx/init_request let the driver allocate per-queue and per-command private data — cmd_size extra bytes are carved out behind each request for exactly this. map_queues lets a driver override the default CPU-to-hardware-queue mapping (the NVMe driver does this; see blk-mq CPU to Queue Mapping).

The tag set describes the geometry (from include/linux/blk-mq.h):

struct blk_mq_tag_set {
    const struct blk_mq_ops *ops;
    struct blk_mq_queue_map  map[HCTX_MAX_TYPES];
    unsigned int nr_maps;        /* number of map[] entries in use */
    unsigned int nr_hw_queues;   /* number of hardware dispatch queues */
    unsigned int queue_depth;    /* tags per hardware queue */
    unsigned int reserved_tags;
    unsigned int cmd_size;       /* extra bytes per request for the driver */
    int          numa_node;
    unsigned int flags;          /* BLK_MQ_F_* */
    /* ... */
};

nr_hw_queues is how many hardware dispatch queues the device wants — typically the number of hardware submission queues it exposes; queue_depth is how many in-flight requests each hardware queue allows, which becomes the size of its tag space (tags are dissected in Tag Sets and Request Allocation). The map[] array holds the CPU-to-queue mappings, one per hardware queue type (HCTX_TYPE_DEFAULT, HCTX_TYPE_READ, HCTX_TYPE_POLL) — see Software and Hardware Queues in blk-mq for what queue types mean.

The registration sequence has two steps. First the driver calls blk_mq_alloc_tag_set(set), which validates the geometry and allocates the per-queue tag bitmaps. The validation in v6.12 is strict (block/blk-mq.c): it rejects nr_hw_queues == 0, rejects queue_depth == 0, requires queue_depth >= reserved_tags + BLK_MQ_TAG_MIN, and requires ops->queue_rq to be present. It also clamps: if nr_maps == 1 and the driver asked for more hardware queues than CPUs, it caps nr_hw_queues at nr_cpu_ids, because “there is no use for more h/w queues than cpus if we just have a single map” (comment in blk_mq_alloc_tag_set). It also caps queue_depth at BLK_MQ_MAX_DEPTH (10240) and shrinks it to 64 inside a kdump crash kernel to conserve memory.

Second, the driver builds the actual queue and disk. In v6.12 the entry point is blk_mq_alloc_queue(set, lim, queuedata) (or the convenience wrapper blk_mq_alloc_disk()), which internally calls blk_alloc_queue() then blk_mq_init_allocated_queue() (block/blk-mq.c).

Uncertain

Verify: the current spelling of the queue-creation entry point. The brief and much older documentation refer to blk_mq_init_queue(), but a grep of the v6.12 block/blk-mq.c and include/linux/blk-mq.h blobs finds no blk_mq_init_queue symbol — the in-tree path is blk_mq_alloc_queue() / blk_mq_alloc_disk() / blk_mq_init_allocated_queue(). Reason: the API was renamed at some point between the era the docs describe and 6.12. To resolve: identify the commit that renamed blk_mq_init_queue → blk_mq_alloc_queue and the release it shipped in; until then treat blk_mq_init_queue as the historical name and blk_mq_alloc_queue as the 6.12 name. uncertain

The Request Lifecycle at a Glance

submit_bio() (covered in The Block IO Submission Path) eventually reaches blk_mq_submit_bio(). The bio is converted into a struct request drawn from the per-queue tag pool. Where the request goes next depends on configuration, decided in blk_mq_insert_request() (block/blk-mq.c):

  • If an I/O scheduler is attached (q->elevator is set), the request is handed to the scheduler’s insert_requests callback, which holds it in the scheduler’s own data structures.
  • If no scheduler is attached (the none case), the request is added to the software staging queue for the current CPU — list_add_tail(&rq->queuelist, &ctx->rq_lists[hctx->type]) — and that staging queue is marked “has pending work” via blk_mq_hctx_mark_pending().
  • Flush and passthrough requests bypass both and go straight onto the hardware queue’s dispatch list.

Later, blk_mq_run_hw_queue() drains the staging queues (or pulls from the scheduler) into the hardware queue and calls the driver’s queue_rq. When the device completes a request it returns the request’s integer tag; blk-mq uses the tag to find the struct request in O(1) without searching, then runs the completion path. The mechanics of running and dispatching live in Software and Hardware Queues in blk-mq.

Failure Modes and Common Misunderstandings

“blk-mq means the device must have multiple hardware queues.” No. Plenty of devices declare nr_hw_queues = 1. blk-mq still gives them per-CPU software staging queues — the scaling benefit on the submission side survives even with a single hardware queue, because the hot path (inserting requests) is per-CPU. The single hardware queue is just the fan-in point.

“mq-deadline is the old deadline scheduler.” It is a rewrite for the multi-queue framework. The single-queue deadline was deleted in 5.0. They share a design philosophy (deadline-bounded dispatch) but are different code.

Confusing none with “no block layer.” none is a real, selectable scheduler: a FIFO pass-through that does no reordering, used for fast NVMe where reordering buys nothing and merging is cheap to skip. It is still blk-mq underneath.

Tag exhaustion stalls. Because in-flight requests are bounded by queue_depth tags per hardware queue, a driver that holds tags too long (slow device, stuck command) starves new submissions. The symptom is rising I/O latency with the device not obviously saturated; dispatch_wait and the request timeout path (ops->timeout) are the relevant machinery. Tag accounting is detailed in Tag Sets and Request Allocation.

Alternatives and Historical Context

The only alternative to blk-mq is the thing it replaced — the single-queue layer — and that no longer exists in any supported kernel (gone since 5.0/2019). There is therefore no “choose blk-mq vs single-queue” decision in a modern kernel; the choice that remains is which I/O scheduler to attach on top (or none), which is a genuine trade-off covered in Linux IO Schedulers Overview and Choosing an IO Scheduler.

In spirit, blk-mq is the block-layer instance of a kernel-wide pattern: replace a globally locked shared structure with per-CPU data plus a small fan-in, the same pattern used throughout the kernel to scale on many cores (see Linux Kernel Synchronization MOC). NVMe’s own host/controller design — per-CPU submission/completion queue pairs — is the hardware mirror image of blk-mq’s software model, which is why the two compose so cleanly (NVMe Queue Pairs and the Driver).

Production Notes

Userspace sees blk-mq through sysfs. Under /sys/block/<dev>/queue/ the file scheduler shows the available and active scheduler (e.g. [none] mq-deadline kyber bfq), and nr_requests reflects the per-queue depth. Under /sys/block/<dev>/mq/ there is one directory per hardware queue, each exposing its CPU mask and tag state — a direct window onto the hctx structures. blktrace/blkparse and the block: tracepoints (e.g. block_rq_insert, block_rq_issue) trace requests through the staging and dispatch stages.

The default scheduler in modern distributions is device-class dependent, chosen by udev rules: none for NVMe (reordering wastes CPU on a device that is already massively parallel), and mq-deadline or bfq for rotational and slower SATA/SAS devices. Do not assume mq-deadline everywhere; check cat /sys/block/<dev>/queue/scheduler.

Uncertain

Verify: the exact current distro udev defaults (which scheduler is auto-selected for NVMe vs rotational vs SATA SSD). Reason: these are set by udev rule files that vary by distribution and change over time; not pinned to a primary source here. To resolve: inspect the shipping udev rules (e.g. 60-ioschedulers.rules) on the target distribution at the kernel version in use. uncertain

See Also

Graph View

Backlinks