blk-mq: Kyber multiqueue I/O scheduler
Subsystems (3)
v3 cover blk-mq: Kyber multiqueue I/O scheduler
From: Omar Sandoval <[email protected]>
This is v3 of Kyber, an I/O scheduler for multiqueue devices combining several techniques: the scalable bitmap library, the new blk-stats API, and queue depth throttling similar to blk-wbt. v1 was here [1], v2 was here [2].
v3 reworks how hardware queues are restarted when domain tokens are exhausted. Instead of reintroducing the QUEUE_FLAG_RESTART bit, which was removed in 6d8c6c0f97ad ("blk-mq: Restart a single queue if tag sets are shared"), the new approach hooks into the sbitmap queues like we do for driver tags since da55f2cc7841 ("blk-mq: use sbq wait queues instead of restart for driver tags").
This series is based on block/for-next + the initialization fix series I sent out yesterday [2]. Patches 1 and 2 implement a new sbitmap operation. Patch 3 exports a couple of helpers. Patch 4 moves a scheduler callback to somewhere more useful. Patch 5 implements the new scheduler.
Thanks!
1: http://marc.info/?l=linux-block&m=148978871820916&w=2
2: http://marc.info/?l=linux-block&m=149132467510945&w=2
Omar Sandoval (5):
sbitmap: add sbitmap_get_shallow() operation
blk-mq: add shallow depth option for blk_mq_get_tag()
blk-mq: export helpers
blk-mq-sched: make completed_request() callback more useful
blk-mq: introduce Kyber multiqueue I/O scheduler
Documentation/block/kyber-iosched.txt | 14 + block/Kconfig.iosched | 9 + block/Makefile | 1 + block/blk-mq-sched.h | 11 +- block/blk-mq-tag.c | 5 +- block/blk-mq.c | 7 +- block/blk-mq.h | 1 + block/kyber-iosched.c | 717 ++++++++++++++++++++++++++++++++++ include/linux/blk-mq.h | 1 + include/linux/elevator.h | 2 +- include/linux/sbitmap.h | 55 +++ lib/sbitmap.c | 75 +++- 12 files changed, 880 insertions(+), 18 deletions(-) create mode 100644 Documentation/block/kyber-iosched.txt create mode 100644 block/kyber-iosched.c
Signature · 1 line
2.12.2
PATCH v3 1/5 sbitmap: add sbitmap_get_shallow() operation
From: Omar Sandoval <[email protected]>
This operation supports the use case of limiting the number of bits that can be allocated for a given operation. Rather than setting aside some bits at the end of the bitmap, we can set aside bits in each word of the bitmap. This means we can keep the allocation hints spread out and support sbitmap_resize() nicely at the cost of lower granularity for the allowed depth.
--- include/linux/sbitmap.h | 55 ++++++++++++++++++++++++++++++++++++ lib/sbitmap.c | 75 ++++++++++++++++++++++++++++++++++++++++++++----- 2 files changed, 123 insertions(+), 7 deletions(-)
include/linux/sbitmap.h +55 -0
@@ -176,6 +176,25 @@ void sbitmap_resize(struct sbitmap *sb, unsigned int depth);int sbitmap_get (struct sbitmap *sb,unsigned int alloc_hint,bool round_robin);/** +* sbitmap_get_shallow() - Try to allocate a free bit from a &struct sbitmap, +* limiting the depth used from each word. +* @sb: Bitmap to allocate from. +* @alloc_hint: Hint for where to start searching for a free bit. +* @shallow_depth: The maximum number of bits to allocate from a single word. +* +* This rather specific operation allows for having multiple users with +* different allocation limits. E.g., there can be a high-priority class that +* uses sbitmap_get() and a low-priority class that uses sbitmap_get_shallow() +* with a @shallow_depth of (1 << (@sb->shift - 1)). Then, the low-priority +* class can only allocate half of the total bits in the bitmap, preventing it +* from starving out the high-priority class. +* +* Return: Non-negative allocated bit number if successful, -1 otherwise. +*/ +int sbitmap_get_shallow (struct sbitmap *sb,unsigned int alloc_hint, +unsigned long shallow_depth); + +/** * sbitmap_any_bit_set() - Check for a set bit in a &struct sbitmap. * @sb: Bitmap to check. *
@@ -326,6 +345,19 @@ void sbitmap_queue_resize(struct sbitmap_queue *sbq, unsigned int depth);int __sbitmap_queue_get (struct sbitmap_queue *sbq);/** +* __sbitmap_queue_get_shallow() - Try to allocate a free bit from a &struct +* sbitmap_queue, limiting the depth used from each word, with preemption +* already disabled. +* @sbq: Bitmap queue to allocate from. +* @shallow_depth: The maximum number of bits to allocate from a single word. +* See sbitmap_get_shallow(). +* +* Return: Non-negative allocated bit number if successful, -1 otherwise. +*/ +int __sbitmap_queue_get_shallow (struct sbitmap_queue *sbq, +unsigned int shallow_depth); + +/** * sbitmap_queue_get() - Try to allocate a free bit from a &struct * sbitmap_queue. * @sbq: Bitmap queue to allocate from.
@@ -346,6 +378,29 @@ static inline int sbitmap_queue_get(struct sbitmap_queue *sbq, }/** +* sbitmap_queue_get_shallow() - Try to allocate a free bit from a &struct +* sbitmap_queue, limiting the depth used from each word. +* @sbq: Bitmap queue to allocate from. +* @cpu: Output parameter; will contain the CPU we ran on (e.g., to be passed to +* sbitmap_queue_clear()). +* @shallow_depth: The maximum number of bits to allocate from a single word. +* See sbitmap_get_shallow(). +* +* Return: Non-negative allocated bit number if successful, -1 otherwise. +*/ +static inline int sbitmap_queue_get_shallow (struct sbitmap_queue *sbq, +unsigned int *cpu, +unsigned int shallow_depth) +{ +int nr; + + *cpu =get_cpu (); + nr =__sbitmap_queue_get_shallow (sbq, shallow_depth); +put_cpu (); +return nr; +} + +/** * sbitmap_queue_clear() - Free an allocated bit and wake up waiters on a * &struct sbitmap_queue. * @sbq: Bitmap to free from.
lib/sbitmap.c +68 -7
113 lines not on this page · raw message
Signature · 1 line
2.12.2
PATCH v3 2/5 blk-mq: add shallow depth option for blk_mq_get_tag()
In reply to Omar SandovalFrom: Omar Sandoval <[email protected]>
Wire up the sbitmap_get_shallow() operation to the tag code so that a caller can limit the number of tags available to it.
--- block/blk-mq-tag.c | 5 ++++- block/blk-mq.h | 1 + 2 files changed, 5 insertions(+), 1 deletion(-)
block/blk-mq-tag.c +4 -1
@@ -96,7 +96,10 @@ static int __blk_mq_get_tag(struct blk_mq_alloc_data *data,if (!(data->flags &BLK_MQ_REQ_INTERNAL ) && !hctx_may_queue (data->hctx, bt))return -1 ; -return __sbitmap_queue_get (bt); +if (data->shallow_depth) +return __sbitmap_queue_get_shallow (bt, data->shallow_depth); +else +return __sbitmap_queue_get (bt); }unsigned int blk_mq_get_tag (struct blk_mq_alloc_data *data)
block/blk-mq.h +1 -0
@@ -141,6 +141,7 @@ struct blk_mq_alloc_data {/* input parameter */ struct request_queue *q;unsigned int flags; +unsigned int shallow_depth;/* input & output parameter */ struct blk_mq_ctx *ctx;
Signature · 1 line
2.12.2
PATCH v3 3/5 blk-mq: export helpers
In reply to Omar SandovalFrom: Omar Sandoval <[email protected]>
blk_mq_finish_request() is required for schedulers that define their own put_request(). blk_mq_run_hw_queue() is required for schedulers that hold back requests to be run later.
--- block/blk-mq.c | 2 ++ include/linux/blk-mq.h | 1 + 2 files changed, 3 insertions(+)
block/blk-mq.c +2 -0
@@ -368,6 +368,7 @@ void blk_mq_finish_request(struct request *rq) {blk_mq_finish_hctx_request (blk_mq_map_queue (rq->q, rq->mq_ctx->cpu), rq); } +EXPORT_SYMBOL_GPL (blk_mq_finish_request);void blk_mq_free_request (struct request *rq) {
@@ -1183,6 +1184,7 @@ void blk_mq_run_hw_queue(struct blk_mq_hw_ctx *hctx, bool async) {__blk_mq_delay_run_hw_queue (hctx, async,0 ); } +EXPORT_SYMBOL (blk_mq_run_hw_queue);void blk_mq_run_hw_queues (struct request_queue *q,bool async) {
include/linux/blk-mq.h +1 -0
@@ -238,6 +238,7 @@ void blk_mq_start_hw_queues(struct request_queue *q);void blk_mq_start_stopped_hw_queue (struct blk_mq_hw_ctx *hctx,bool async);void blk_mq_start_stopped_hw_queues (struct request_queue *q,bool async);void blk_mq_delay_run_hw_queue (struct blk_mq_hw_ctx *hctx,unsigned long msecs); +void blk_mq_run_hw_queue (struct blk_mq_hw_ctx *hctx,bool async);void blk_mq_run_hw_queues (struct request_queue *q,bool async);void blk_mq_delay_queue (struct blk_mq_hw_ctx *hctx,unsigned long msecs); void blk_mq_tagset_busy_iter(struct blk_mq_tag_set *tagset,
Signature · 1 line
2.12.2
PATCH v3 4/5 blk-mq-sched: make completed_request() callback more useful
In reply to Omar SandovalFrom: Omar Sandoval <[email protected]>
Currently, this callback is called right after put_request() and has no distinguishable purpose. Instead, let's call it before put_request() as soon as I/O has completed on the request, before we account it in blk-stat. With this, Kyber can enable stats when it sees a latency outlier and make sure the outlier gets accounted.
--- block/blk-mq-sched.h | 11 +++-------- block/blk-mq.c | 5 ++++- include/linux/elevator.h | 2 +- 3 files changed, 8 insertions(+), 10 deletions(-)
block/blk-mq-sched.h +3 -8
@@ -82,17 +82,12 @@ blk_mq_sched_allow_merge(struct request_queue *q, struct request *rq,return true; } -static inline void -blk_mq_sched_completed_request (struct blk_mq_hw_ctx *hctx,struct request *rq) +static inline void blk_mq_sched_completed_request (struct request *rq) { -struct elevator_queue *e = hctx->queue->elevator; +struct elevator_queue *e = rq->q->elevator;if (e && e->type->ops.mq.completed_request) - e->type->ops.mq.completed_request (hctx, rq); - -BUG_ON (rq->internal_tag ==-1 ); - -blk_mq_put_tag (hctx, hctx->sched_tags, rq->mq_ctx, rq->internal_tag); + e->type->ops.mq.completed_request (rq); }static inline void blk_mq_sched_started_request (struct request *rq)
block/blk-mq.c +4 -1
@@ -350,7 +350,7 @@ void __blk_mq_finish_request(struct blk_mq_hw_ctx *hctx, struct blk_mq_ctx *ctx,if (rq->tag !=-1 )blk_mq_put_tag (hctx, hctx->tags, ctx, rq->tag);if (sched_tag !=-1 ) -blk_mq_sched_completed_request (hctx, rq); +blk_mq_put_tag (hctx, hctx->sched_tags, ctx, sched_tag);blk_mq_sched_restart (hctx);blk_queue_exit (q); }
@@ -444,6 +444,9 @@ static void __blk_mq_complete_request(struct request *rq) {struct request_queue *q = rq->q; +if (rq->internal_tag !=-1 ) +blk_mq_sched_completed_request (rq); +blk_mq_stat_add (rq);if (!q->softirq_done_fn)
include/linux/elevator.h +1 -1
@@ -106,7 +106,7 @@ struct elevator_mq_ops {void (*insert_requests)(struct blk_mq_hw_ctx *,struct list_head *,bool );struct request *(*dispatch_request)(struct blk_mq_hw_ctx *);bool (*has_work)(struct blk_mq_hw_ctx *); -void (*completed_request)(struct blk_mq_hw_ctx *,struct request *); +void (*completed_request)(struct request *);void (*started_request)(struct request *);void (*requeue_request)(struct request *);struct request *(*former_request)(struct request_queue *,struct request *);
Signature · 1 line
2.12.2
PATCH v3 5/5 blk-mq: introduce Kyber multiqueue I/O scheduler
In reply to Omar SandovalFrom: Omar Sandoval <[email protected]>
The Kyber I/O scheduler is an I/O scheduler for fast devices designed to scale to multiple queues. Users configure only two knobs, the target read and synchronous write latencies, and the scheduler tunes itself to achieve that latency goal.
The implementation is based on "tokens", built on top of the scalable bitmap library. Tokens serve as a mechanism for limiting requests. There are two tiers of tokens: queueing tokens and dispatch tokens.
A queueing token is required to allocate a request. In fact, these tokens are actually the blk-mq internal scheduler tags, but the scheduler manages the allocation directly in order to implement its policy.
Dispatch tokens are device-wide and split up into two scheduling
domains: reads vs. writes. Each hardware queue dispatches batches round-robin between the scheduling domains as long as tokens are available for that domain.
These tokens can be used as the mechanism to enable various policies. The policy Kyber uses is inspired by active queue management techniques for network routing, similar to blk-wbt. The scheduler monitors latencies and scales the number of dispatch tokens accordingly. Queueing tokens are used to prevent starvation of synchronous requests by asynchronous requests.
Various extensions are possible, including better heuristics and ionice support. The new scheduler isn't set as the default yet.
--- Documentation/block/kyber-iosched.txt | 14 + block/Kconfig.iosched | 9 + block/Makefile | 1 + block/kyber-iosched.c | 717 ++++++++++++++++++++++++++++++++++ 4 files changed, 741 insertions(+) create mode 100644 Documentation/block/kyber-iosched.txt create mode 100644 block/kyber-iosched.c
Documentation/block/kyber-iosched.txt new file +14 -0
@@ -0,0 +1,14 @@ +Kyber I/O scheduler tunables +=========================== + +The only two tunables for the Kyber scheduler are the target latencies for +reads and synchronous writes. Kyber will throttle requests in order to meet +these target latencies. + +read_lat_nsec +------------- +Target latency for reads (in nanoseconds). + +write_lat_nsec +-------------- +Target latency for synchronous writes (in nanoseconds).
block/Kconfig.iosched +9 -0
@@ -69,6 +69,15 @@ config MQ_IOSCHED_DEADLINE ---help--- MQ version of the deadline IO scheduler. +config MQ_IOSCHED_KYBER + tristate "Kyber I/O scheduler" + default y + ---help--- + The Kyber I/O scheduler is a low-overhead scheduler suitable for + multiqueue and other fast devices. Given target latencies for reads and + synchronous writes, it will self-tune queue depths to achieve that + goal. + endmenu endif
block/Makefile +1 -0
@@ -20,6 +20,7 @@ obj-$(CONFIG_IOSCHED_NOOP) += noop-iosched.o obj-$(CONFIG_IOSCHED_DEADLINE) += deadline-iosched.o obj-$(CONFIG_IOSCHED_CFQ) += cfq-iosched.o obj-$(CONFIG_MQ_IOSCHED_DEADLINE) += mq-deadline.o +obj-$(CONFIG_MQ_IOSCHED_KYBER) += kyber-iosched.o obj-$(CONFIG_BLOCK_COMPAT) += compat_ioctl.o obj-$(CONFIG_BLK_CMDLINE_PARSER) += cmdline-parser.o
block/kyber-iosched.c new file +717 -0
717 lines not on this page · raw message
Signature · 1 line
2.12.2