Multi-Queue Block IO Queueing Mechanism (blk-mq)¶

The Multi-Queue Block IO Queueing Mechanism is an API to enable fast storage devices to achieve a huge number of input/output operations per second (IOPS) through queueing and submitting IO requests to block devices simultaneously, benefiting from the parallelism offered by modern storage devices.

Introduction¶

Background¶

Magnetic hard disks have been the de facto standard from the beginning of the development of the kernel. The Block IO subsystem aimed to achieve the best performance possible for those devices with a high penalty when doing random access, and the bottleneck was the mechanical moving parts, a lot slower than any layer on the storage stack. One example of such optimization technique involves ordering read/write requests according to the current position of the hard disk head.

However, with the development of Solid State Drives and Non-Volatile Memories without mechanical parts nor random access penalty and capable of performing high parallel access, the bottleneck of the stack had moved from the storage device to the operating system. In order to take advantage of the parallelism in those devices’ design, the multi-queue mechanism was introduced.

The former design had a single queue to store block IO requests with a single lock. That did not scale well in SMP systems due to dirty data in cache and the bottleneck of having a single lock for multiple processors. This setup also suffered with congestion when different processes (or the same process, moving to different CPUs) wanted to perform block IO. Instead of this, the blk-mq API spawns multiple queues with individual entry points local to the CPU, removing the need for a lock. A deeper explanation on how this works is covered in the following section (Operation).

Operation¶

When the userspace performs IO to a block device (reading or writing a file, for instance), blk-mq takes action: it will store and manage IO requests to the block device, acting as middleware between the userspace (and a file system, if present) and the block device driver.

blk-mq has two group of queues: software staging queues and hardware dispatch queues. When the request arrives at the block layer, it will try the shortest path possible: send it directly to the hardware queue. However, there are two cases that it might not do that: if there’s an IO scheduler attached at the layer or if we want to try to merge requests. In both cases, requests will be sent to the software queue.

Then, after the requests are processed by software queues, they will be placed at the hardware queue, a second stage queue were the hardware has direct access to process those requests. However, if the hardware does not have enough resources to accept more requests, blk-mq will places requests on a temporary queue, to be sent in the future, when the hardware is able.

Software staging queues¶

The block IO subsystem adds requests in the software staging queues (represented by struct blk_mq_ctx) in case that they weren’t sent directly to the driver. A request is one or more BIOs. They arrived at the block layer through the data structure struct bio. The block layer will then build a new structure from it, the struct request that will be used to communicate with the device driver. Each queue has its own lock and the number of queues is defined by a per-CPU or per-node basis.

The staging queue can be used to merge requests for adjacent sectors. For instance, requests for sector 3-6, 6-7, 7-9 can become one request for 3-9. Even if random access to SSDs and NVMs have the same time of response compared to sequential access, grouped requests for sequential access decreases the number of individual requests. This technique of merging requests is called plugging.

Along with that, the requests can be reordered to ensure fairness of system resources (e.g. to ensure that no application suffers from starvation) and/or to improve IO performance, by an IO scheduler.

IO Schedulers¶

There are several schedulers implemented by the block layer, each one following a heuristic to improve the IO performance. They are “pluggable” (as in plug and play), in the sense of they can be selected at run time using sysfs. You can read more about Linux’s IO schedulers here. The scheduling happens only between requests in the same queue, so it is not possible to merge requests from different queues, otherwise there would be cache trashing and a need to have a lock for each queue. After the scheduling, the requests are eligible to be sent to the hardware. One of the possible schedulers to be selected is the NONE scheduler, the most straightforward one. It will just place requests on whatever software queue the process is running on, without any reordering. When the device starts processing requests in the hardware queue (a.k.a. run the hardware queue), the software queues mapped to that hardware queue will be drained in sequence according to their mapping.

Hardware dispatch queues¶

The hardware queue (represented by struct blk_mq_hw_ctx) is a struct used by device drivers to map the device submission queues (or device DMA ring buffer), and are the last step of the block layer submission code before the low level device driver taking ownership of the request. To run this queue, the block layer removes requests from the associated software queues and tries to dispatch to the hardware.

If it’s not possible to send the requests directly to hardware, they will be added to a linked list (hctx->dispatch) of requests. Then, next time the block layer runs a queue, it will send the requests laying at the dispatch list first, to ensure a fairness dispatch with those requests that were ready to be sent first. The number of hardware queues depends on the number of hardware contexts supported by the hardware and its device driver, but it will not be more than the number of cores of the system. There is no reordering at this stage, and each software queue has a set of hardware queues to send requests for.

Note

Neither the block layer nor the device protocols guarantee the order of completion of requests. This must be handled by higher layers, like the filesystem.

Tag-based completion¶

In order to indicate which request has been completed, every request is identified by an integer, ranging from 0 to the dispatch queue size. This tag is generated by the block layer and later reused by the device driver, removing the need to create a redundant identifier. When a request is completed in the drive, the tag is sent back to the block layer to notify it of the finalization. This removes the need to do a linear search to find out which IO has been completed.

Source code documentation¶

struct blk_mq_hw_ctx¶: State for a hardware queue facing the hardware block device

Definition

struct blk_mq_hw_ctx {
  struct {
    spinlock_t lock;
    struct list_head        dispatch;
    unsigned long           state;
  };
  struct delayed_work     run_work;
  cpumask_var_t cpumask;
  int next_cpu;
  int next_cpu_batch;
  unsigned long           flags;
  void *sched_data;
  struct request_queue    *queue;
  struct blk_flush_queue  *fq;
  void *driver_data;
  struct sbitmap          ctx_map;
  struct blk_mq_ctx       *dispatch_from;
  unsigned int            dispatch_busy;
  unsigned short          type;
  unsigned short          nr_ctx;
  struct blk_mq_ctx       **ctxs;
  spinlock_t dispatch_wait_lock;
  wait_queue_entry_t dispatch_wait;
  atomic_t wait_index;
  struct blk_mq_tags      *tags;
  struct blk_mq_tags      *sched_tags;
  unsigned long           queued;
  unsigned long           run;
#define BLK_MQ_MAX_DISPATCH_ORDER       7;
  unsigned long           dispatched[BLK_MQ_MAX_DISPATCH_ORDER];
  unsigned int            numa_node;
  unsigned int            queue_num;
  atomic_t nr_active;
  atomic_t elevator_queued;
  struct hlist_node       cpuhp_online;
  struct hlist_node       cpuhp_dead;
  struct kobject          kobj;
  unsigned long           poll_considered;
  unsigned long           poll_invoked;
  unsigned long           poll_success;
#ifdef CONFIG_BLK_DEBUG_FS;
  struct dentry           *debugfs_dir;
  struct dentry           *sched_debugfs_dir;
#endif;
  struct list_head        hctx_list;
  struct srcu_struct      srcu[];
};

Members

{unnamed_struct}: anonymous
lock: Protects the dispatch list.
dispatch: Used for requests that are ready to be dispatched to the hardware but for some reason (e.g. lack of resources) could not be sent to the hardware. As soon as the driver can send new requests, requests at this list will be sent first for a fairer dispatch.
state: BLK_MQ_S_* flags. Defines the state of the hw queue (active, scheduled to restart, stopped).
run_work: Used for scheduling a hardware queue run at a later time.
cpumask: Map of available CPUs where this hctx can run.
next_cpu: Used by blk_mq_hctx_next_cpu() for round-robin CPU selection from cpumask.
next_cpu_batch: Counter of how many works left in the batch before changing to the next CPU.
flags: BLK_MQ_F_* flags. Defines the behaviour of the queue.
sched_data: Pointer owned by the IO scheduler attached to a request queue. It’s up to the IO scheduler how to use this pointer.
queue: Pointer to the request queue that owns this hardware context.
fq: Queue of requests that need to perform a flush operation.
driver_data: Pointer to data owned by the block driver that created this hctx
ctx_map: Bitmap for each software queue. If bit is on, there is a pending request in that software queue.
dispatch_from: Software queue to be used when no scheduler was selected.
dispatch_busy: Number used by blk_mq_update_dispatch_busy() to decide if the hw_queue is busy using Exponential Weighted Moving Average algorithm.
type: HCTX_TYPE_* flags. Type of hardware queue.
nr_ctx: Number of software queues.
ctxs: Array of software queues.
dispatch_wait_lock: Lock for dispatch_wait queue.
dispatch_wait: Waitqueue to put requests when there is no tag available at the moment, to wait for another try in the future.
wait_index: Index of next available dispatch_wait queue to insert requests.
tags: Tags owned by the block driver. A tag at this set is only assigned when a request is dispatched from a hardware queue.
sched_tags: Tags owned by I/O scheduler. If there is an I/O scheduler associated with a request queue, a tag is assigned when that request is allocated. Else, this member is not used.
queued: Number of queued requests.
run: Number of dispatched requests.
dispatched: Number of dispatch requests by queue.
numa_node: NUMA node the storage adapter has been connected to.
queue_num: Index of this hardware queue.
nr_active: Number of active requests. Only used when a tag set is shared across request queues.
elevator_queued: Number of queued requests on hctx.
cpuhp_online: List to store request if CPU is going to die
cpuhp_dead: List to store request if some CPU die.
kobj: Kernel object for sysfs.
poll_considered: Count times blk_poll() was called.
poll_invoked: Count how many requests blk_poll() polled.
poll_success: Count how many polled requests were completed.
debugfs_dir: debugfs directory for this hardware queue. Named as cpu<cpu_number>.
sched_debugfs_dir: debugfs directory for the scheduler.
hctx_list: if this hctx is not in use, this is an entry in q->unused_hctx_list.
srcu: Sleepable RCU. Use as lock when type of the hardware queue is blocking (BLK_MQ_F_BLOCKING). Must be the last member - see also blk_mq_hw_ctx_size().

struct blk_mq_queue_map¶: Map software queues to hardware queues

Definition

struct blk_mq_queue_map {
  unsigned int *mq_map;
  unsigned int nr_queues;
  unsigned int queue_offset;
};

Members

mq_map: CPU ID to hardware queue index map. This is an array with nr_cpu_ids elements. Each element has a value in the range [queue_offset, queue_offset + nr_queues).
nr_queues: Number of hardware queues to map CPU IDs onto.
queue_offset: First hardware queue to map onto. Used by the PCIe NVMe driver to map each hardware queue type (enum hctx_type) onto a distinct set of hardware queues.

enum hctx_type¶: Type of hardware queue

Constants

HCTX_TYPE_DEFAULT: All I/O not otherwise accounted for.
HCTX_TYPE_READ: Just for READ I/O.
HCTX_TYPE_POLL: Polled I/O of any kind.
HCTX_MAX_TYPES: Number of types of hctx.

struct blk_mq_tag_set¶: tag set that can be shared between request queues

Definition

struct blk_mq_tag_set {
  struct blk_mq_queue_map map[HCTX_MAX_TYPES];
  unsigned int            nr_maps;
  const struct blk_mq_ops *ops;
  unsigned int            nr_hw_queues;
  unsigned int            queue_depth;
  unsigned int            reserved_tags;
  unsigned int            cmd_size;
  int numa_node;
  unsigned int            timeout;
  unsigned int            flags;
  void *driver_data;
  atomic_t active_queues_shared_sbitmap;
  struct sbitmap_queue    __bitmap_tags;
  struct sbitmap_queue    __breserved_tags;
  struct blk_mq_tags      **tags;
  struct mutex            tag_list_lock;
  struct list_head        tag_list;
};

Members

map: One or more ctx -> hctx mappings. One map exists for each hardware queue type (enum hctx_type) that the driver wishes to support. There are no restrictions on maps being of the same size, and it’s perfectly legal to share maps between types.
nr_maps: Number of elements in the map array. A number in the range [1, HCTX_MAX_TYPES].
ops: Pointers to functions that implement block driver behavior.
nr_hw_queues: Number of hardware queues supported by the block driver that owns this data structure.
queue_depth: Number of tags per hardware queue, reserved tags included.
reserved_tags: Number of tags to set aside for BLK_MQ_REQ_RESERVED tag allocations.
cmd_size: Number of additional bytes to allocate per request. The block driver owns these additional bytes.
numa_node: NUMA node the storage adapter has been connected to.
timeout: Request processing timeout in jiffies.
flags: Zero or more BLK_MQ_F_* flags.
driver_data: Pointer to data owned by the block driver that created this tag set.
active_queues_shared_sbitmap: number of active request queues per tag set.
__bitmap_tags: A shared tags sbitmap, used over all hctx’s
__breserved_tags: A shared reserved tags sbitmap, used over all hctx’s
tags: Tag sets. One tag set per hardware queue. Has nr_hw_queues elements.
tag_list_lock: Serializes tag_list accesses.
tag_list: List of the request queues that use this tag set. See also request_queue.tag_set_list.

struct blk_mq_queue_data¶: Data about a request inserted in a queue

Definition

struct blk_mq_queue_data {
  struct request *rq;
  bool last;
};

Members

rq: Request pointer.
last: If it is the last request in the queue.

struct blk_mq_ops¶: Callback functions that implements block driver behaviour.

Definition

struct blk_mq_ops {
  blk_status_t (*queue_rq)(struct blk_mq_hw_ctx *, const struct blk_mq_queue_data *);
  void (*commit_rqs)(struct blk_mq_hw_ctx *);
  bool (*get_budget)(struct request_queue *);
  void (*put_budget)(struct request_queue *);
  enum blk_eh_timer_return (*timeout)(struct request *, bool);
  int (*poll)(struct blk_mq_hw_ctx *);
  void (*complete)(struct request *);
  int (*init_hctx)(struct blk_mq_hw_ctx *, void *, unsigned int);
  void (*exit_hctx)(struct blk_mq_hw_ctx *, unsigned int);
  int (*init_request)(struct blk_mq_tag_set *set, struct request *, unsigned int, unsigned int);
  void (*exit_request)(struct blk_mq_tag_set *set, struct request *, unsigned int);
  void (*initialize_rq_fn)(struct request *rq);
  void (*cleanup_rq)(struct request *);
  bool (*busy)(struct request_queue *);
  int (*map_queues)(struct blk_mq_tag_set *set);
#ifdef CONFIG_BLK_DEBUG_FS;
  void (*show_rq)(struct seq_file *m, struct request *rq);
#endif;
};

Members

queue_rq

Queue a new request from block IO.

commit_rqs

If a driver uses bd->last to judge when to submit requests to hardware, it must define this function. In case of errors that make us stop issuing further requests, this hook serves the purpose of kicking the hardware (which the last request otherwise would have done).

get_budget

Reserve budget before queue request, once .queue_rq is run, it is driver’s responsibility to release the reserved budget. Also we have to handle failure case of .get_budget for avoiding I/O deadlock.

put_budget

Release the reserved budget.

timeout

Called on request timeout.

poll

Called to poll for completion of a specific tag.

complete

Mark the request as complete.

init_hctx

Called when the block layer side of a hardware queue has been set up, allowing the driver to allocate/init matching structures.

exit_hctx

Ditto for exit/teardown.

init_request

Called for every command allocated by the block layer to allow the driver to set up driver specific data.

Tag greater than or equal to queue_depth is for setting up flush request.

exit_request

Ditto for exit/teardown.

initialize_rq_fn

Called from inside blk_get_request().

cleanup_rq

Called before freeing one request which isn’t completed yet, and usually for freeing the driver private data.

busy

If set, returns whether or not this queue currently is busy.

map_queues

This allows drivers specify their own queue mapping by overriding the setup-time function that builds the mq_map.

show_rq

Used by the debugfs implementation to show driver-specific information about a request.

enum mq_rq_state blk_mq_rq_state(struct request *rq)¶: read the current MQ_RQ_* state of a request

Parameters

struct request *rq: target request.

struct request * blk_mq_rq_from_pdu(void *pdu)¶: cast a PDU to a request

Parameters

void *pdu: the PDU (Protocol Data Unit) to be casted

Return

request

Description

Driver command data is immediately after the request. So subtract request size to get back to the original request.

void * blk_mq_rq_to_pdu(struct request *rq)¶: cast a request to a PDU

Parameters

struct request *rq: the request to be casted

Return

pointer to the PDU

Description

Driver command data is immediately after the request. So add request to get the PDU.

void blk_mq_quiesce_queue(struct request_queue *q)¶: wait until all ongoing dispatches have finished

Parameters

struct request_queue *q: request queue.

Note

this function does not prevent that the struct request end_io() callback function is invoked. Once this function is returned, we make sure no dispatch can happen until the queue is unquiesced via blk_mq_unquiesce_queue().

void blk_mq_complete_request(struct request *rq)¶: end I/O on a request

Parameters

struct request *rq: the request being processed

Description

Complete a request by scheduling the ->complete_rq operation.

void blk_mq_start_request(struct request *rq)¶: Start processing a request

Parameters

struct request *rq: Pointer to request to be started

Description

Function used by device drivers to notify the block layer that a request is going to be processed now, so blk layer can do proper initializations such as starting the timeout timer.

void __blk_mq_run_hw_queue(struct blk_mq_hw_ctx *hctx)¶: Run a hardware queue.

Parameters

struct blk_mq_hw_ctx *hctx: Pointer to the hardware queue to run.

Description

Send pending requests to the hardware.

void __blk_mq_delay_run_hw_queue(struct blk_mq_hw_ctx *hctx, bool async, unsigned long msecs)¶: Run (or schedule to run) a hardware queue.

Parameters

struct blk_mq_hw_ctx *hctx: Pointer to the hardware queue to run.
bool async: If we want to run the queue asynchronously.
unsigned long msecs: Milliseconds of delay to wait before running the queue.

Description

If !async, try to run the queue now. Else, run the queue asynchronously and with a delay of msecs.

void blk_mq_delay_run_hw_queue(struct blk_mq_hw_ctx *hctx, unsigned long msecs)¶: Run a hardware queue asynchronously.

Parameters

struct blk_mq_hw_ctx *hctx: Pointer to the hardware queue to run.
unsigned long msecs: Milliseconds of delay to wait before running the queue.

Description

Run a hardware queue asynchronously with a delay of msecs.

void blk_mq_run_hw_queue(struct blk_mq_hw_ctx *hctx, bool async)¶: Start to run a hardware queue.

Parameters

struct blk_mq_hw_ctx *hctx: Pointer to the hardware queue to run.
bool async: If we want to run the queue asynchronously.

Description

Check if the request queue is not in a quiesced state and if there are pending requests to be sent. If this is true, run the queue to send requests to hardware.

void blk_mq_run_hw_queues(struct request_queue *q, bool async)¶: Run all hardware queues in a request queue.

Parameters

struct request_queue *q: Pointer to the request queue to run.
bool async: If we want to run the queue asynchronously.

void blk_mq_delay_run_hw_queues(struct request_queue *q, unsigned long msecs)¶: Run all hardware queues asynchronously.

Parameters

struct request_queue *q: Pointer to the request queue to run.
unsigned long msecs: Milliseconds of delay to wait before running the queues.

bool blk_mq_queue_stopped(struct request_queue *q)¶: check whether one or more hctxs have been stopped

Parameters

struct request_queue *q: request queue.

Description

The caller is responsible for serializing this function against blk_mq_{start,stop}_hw_queue().

void blk_mq_request_bypass_insert(struct request *rq, bool at_head, bool run_queue)¶: Insert a request at dispatch list.

Parameters

struct request *rq: Pointer to request to be inserted.
bool at_head: true if the request should be inserted at the head of the list.
bool run_queue: If we should run the hardware queue after inserting the request.

Description

Should only be used carefully, when the caller knows we want to bypass a potential IO scheduler on the target device.

void blk_mq_try_issue_directly(struct blk_mq_hw_ctx *hctx, struct request *rq, blk_qc_t *cookie)¶: Try to send a request directly to device driver.

Parameters

struct blk_mq_hw_ctx *hctx: Pointer of the associated hardware queue.
struct request *rq: Pointer to request to be sent.
blk_qc_t *cookie: Request queue cookie.

Description

If the device has enough resources to accept a new request now, send the request directly to device driver. Else, insert at hctx->dispatch queue, so we can try send it another time in the future. Requests inserted at this queue have higher priority.

blk_qc_t blk_mq_submit_bio(struct bio *bio)¶: Create and send a request to block device.

Parameters

struct bio *bio: Bio pointer.

Description

Builds up a request structure from q and bio and send to the device. The request may not be queued directly to hardware if: * This request can be merged with another one * We want to place request at plug queue for possible future merging * There is an IO scheduler active at this queue

It will not queue the request if there is an error with the bio, or at the request creation.

Return

Request queue cookie.

int blk_poll(struct request_queue *q, blk_qc_t cookie, bool spin)¶: poll for IO completions

Parameters

struct request_queue *q: the queue
blk_qc_t cookie: cookie passed back at IO submission time
bool spin: whether to spin for completions

Description

Poll for completions on the passed in queue. Returns number of completed entries found. If spin is true, then blk_poll will continue looping until at least one completion is found, unless the task is otherwise marked running (or we need to reschedule).

Multi-Queue Block IO Queueing Mechanism (blk-mq)¶

Introduction¶

Background¶

Operation¶

Software staging queues¶

IO Schedulers¶

Hardware dispatch queues¶

Tag-based completion¶

Further reading¶

Source code documentation¶