blk-mq.rst

  1.. SPDX-License-Identifier: GPL-2.0
  2
  3================================================
  4Multi-Queue Block IO Queueing Mechanism (blk-mq)
  5================================================
  6
  7The Multi-Queue Block IO Queueing Mechanism is an API to enable fast storage
  8devices to achieve a huge number of input/output operations per second (IOPS)
  9through queueing and submitting IO requests to block devices simultaneously,
 10benefiting from the parallelism offered by modern storage devices.
 11
 12Introduction
 13============
 14
 15Background
 16----------
 17
 18Magnetic hard disks have been the de facto standard from the beginning of the
 19development of the kernel. The Block IO subsystem aimed to achieve the best
 20performance possible for those devices with a high penalty when doing random
 21access, and the bottleneck was the mechanical moving parts, a lot slower than
 22any layer on the storage stack. One example of such optimization technique
 23involves ordering read/write requests according to the current position of the
 24hard disk head.
 25
 26However, with the development of Solid State Drives and Non-Volatile Memories
 27without mechanical parts nor random access penalty and capable of performing
 28high parallel access, the bottleneck of the stack had moved from the storage
 29device to the operating system. In order to take advantage of the parallelism
 30in those devices' design, the multi-queue mechanism was introduced.
 31
 32The former design had a single queue to store block IO requests with a single
 33lock. That did not scale well in SMP systems due to dirty data in cache and the
 34bottleneck of having a single lock for multiple processors. This setup also
 35suffered with congestion when different processes (or the same process, moving
 36to different CPUs) wanted to perform block IO. Instead of this, the blk-mq API
 37spawns multiple queues with individual entry points local to the CPU, removing
 38the need for a lock. A deeper explanation on how this works is covered in the
 39following section (`Operation`_).
 40
 41Operation
 42---------
 43
 44When the userspace performs IO to a block device (reading or writing a file,
 45for instance), blk-mq takes action: it will store and manage IO requests to
 46the block device, acting as middleware between the userspace (and a file
 47system, if present) and the block device driver.
 48
 49blk-mq has two group of queues: software staging queues and hardware dispatch
 50queues. When the request arrives at the block layer, it will try the shortest
 51path possible: send it directly to the hardware queue. However, there are two
 52cases that it might not do that: if there's an IO scheduler attached at the
 53layer or if we want to try to merge requests. In both cases, requests will be
 54sent to the software queue.
 55
 56Then, after the requests are processed by software queues, they will be placed
 57at the hardware queue, a second stage queue where the hardware has direct access
 58to process those requests. However, if the hardware does not have enough
 59resources to accept more requests, blk-mq will place requests on a temporary
 60queue, to be sent in the future, when the hardware is able.
 61
 62Software staging queues
 63~~~~~~~~~~~~~~~~~~~~~~~
 64
 65The block IO subsystem adds requests in the software staging queues
 66(represented by struct blk_mq_ctx) in case that they weren't sent
 67directly to the driver. A request is one or more BIOs. They arrived at the
 68block layer through the data structure struct bio. The block layer
 69will then build a new structure from it, the struct request that will
 70be used to communicate with the device driver. Each queue has its own lock and
 71the number of queues is defined by a per-CPU or per-node basis.
 72
 73The staging queue can be used to merge requests for adjacent sectors. For
 74instance, requests for sector 3-6, 6-7, 7-9 can become one request for 3-9.
 75Even if random access to SSDs and NVMs have the same time of response compared
 76to sequential access, grouped requests for sequential access decreases the
 77number of individual requests. This technique of merging requests is called
 78plugging.
 79
 80Along with that, the requests can be reordered to ensure fairness of system
 81resources (e.g. to ensure that no application suffers from starvation) and/or to
 82improve IO performance, by an IO scheduler.
 83
 84IO Schedulers
 85^^^^^^^^^^^^^
 86
 87There are several schedulers implemented by the block layer, each one following
 88a heuristic to improve the IO performance. They are "pluggable" (as in plug
 89and play), in the sense of they can be selected at run time using sysfs. You
 90can read more about Linux's IO schedulers `here
 91<https://www.kernel.org/doc/html/latest/block/index.html>`_. The scheduling
 92happens only between requests in the same queue, so it is not possible to merge
 93requests from different queues, otherwise there would be cache trashing and a
 94need to have a lock for each queue. After the scheduling, the requests are
 95eligible to be sent to the hardware. One of the possible schedulers to be
 96selected is the NONE scheduler, the most straightforward one. It will just
 97place requests on whatever software queue the process is running on, without
 98any reordering. When the device starts processing requests in the hardware
 99queue (a.k.a. run the hardware queue), the software queues mapped to that
100hardware queue will be drained in sequence according to their mapping.
101
102Hardware dispatch queues
103~~~~~~~~~~~~~~~~~~~~~~~~
104
105The hardware queue (represented by struct blk_mq_hw_ctx) is a struct
106used by device drivers to map the device submission queues (or device DMA ring
107buffer), and are the last step of the block layer submission code before the
108low level device driver taking ownership of the request. To run this queue, the
109block layer removes requests from the associated software queues and tries to
110dispatch to the hardware.
111
112If it's not possible to send the requests directly to hardware, they will be
113added to a linked list (``hctx->dispatch``) of requests. Then,
114next time the block layer runs a queue, it will send the requests laying at the
115``dispatch`` list first, to ensure a fairness dispatch with those
116requests that were ready to be sent first. The number of hardware queues
117depends on the number of hardware contexts supported by the hardware and its
118device driver, but it will not be more than the number of cores of the system.
119There is no reordering at this stage, and each software queue has a set of
120hardware queues to send requests for.
121
122.. note::
123
124        Neither the block layer nor the device protocols guarantee
125        the order of completion of requests. This must be handled by
126        higher layers, like the filesystem.
127
128Tag-based completion
129~~~~~~~~~~~~~~~~~~~~
130
131In order to indicate which request has been completed, every request is
132identified by an integer, ranging from 0 to the dispatch queue size. This tag
133is generated by the block layer and later reused by the device driver, removing
134the need to create a redundant identifier. When a request is completed in the
135driver, the tag is sent back to the block layer to notify it of the finalization.
136This removes the need to do a linear search to find out which IO has been
137completed.
138
139Further reading
140---------------
141
142- `Linux Block IO: Introducing Multi-queue SSD Access on Multi-core Systems <http://kernel.dk/blk-mq.pdf>`_
143
144- `NOOP scheduler <https://en.wikipedia.org/wiki/Noop_scheduler>`_
145
146- `Null block device driver <https://www.kernel.org/doc/html/latest/block/null_blk.html>`_
147
148Source code documentation
149=========================
150
151.. kernel-doc:: include/linux/blk-mq.h
152
153.. kernel-doc:: block/blk-mq.c