blk-mq: multiqueue I/O scheduler

From: Omar Sandoval <[email protected]>

This patch series implements 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.

These patches are on top of my earlier blk-stats series [1]. They also need a fix in Jens' for-linus branch in order to work properly [2].

Patches 1 and 2 implement a new sbitmap operation and patch 3 exports a required function. Patch 4 implements the new scheduler, named Kyber.

The commit message in patch 4 describes Kyber in detail. The scheduler employs some heuristics that I've experimented with, but that's probably the area that needs the most work. I'll be at LSF/MM next week, and there's currently a lightning talk on the schedule to discuss improvements and extensions.

A quick test case that demonstrates the scheduler in action:

---
[global]
filename=/dev/nvme0n1
direct=1
runtime=10s
time_based
group_reporting

[writers]
numjobs=40
ioengine=libaio
iodepth=1024
rw=randwrite

[reader]
new_group
rate_iops=1000
ioengine=sync
rw=randread
---

With Kyber set to a target latency of 1 ms, the reader sees latencies of 8 ms on average. Kyber brings this down to just over 1 ms.

Thanks!

1: http://marc.info/?l=linux-block&m=148952547205774&w=2
2: http://git.kernel.dk/cgit/linux-block/commit/?h=for-linus&id=efd4b81abbe1ac753717f2f10cd3dab8bed6c103

Omar Sandoval (4):
sbitmap: add sbitmap_get_shallow() operation
blk-mq: add shallow depth option for blk_mq_get_tag()
blk-mq: export blk_mq_finish_request()
blk-mq: introduce Kyber multiqueue I/O scheduler

 block/Kconfig.iosched   |   8 +
 block/Makefile          |   1 +
 block/blk-mq-tag.c      |   5 +-
 block/blk-mq.c          |   1 +
 block/blk-mq.h          |   1 +
 block/elevator.c        |   9 +-
 block/kyber-iosched.c   | 586 ++++++++++++++++++++++++++++++++++++++++++++++++
 include/linux/sbitmap.h |  55 +++++
 lib/sbitmap.c           |  75 ++++++-
 9 files changed, 729 insertions(+), 12 deletions(-)
 create mode 100644 block/kyber-iosched.c

2.12.0

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(-)

index d4e0a204c118..a1904aadbc45 100644
@@ -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.

2.12.0

From: 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(-)

index e48bc2c72615..1f25d466ebdc 100644
@@ -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)

index 8d49c06fc520..77ec66369f21 100644
@@ -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;

2.12.0

From: Omar Sandoval <[email protected]>

This is required for schedulers that define their own put_request().

---
 block/blk-mq.c | 1 +
 1 file changed, 1 insertion(+)

index 559f9b0f24a1..94973103e809 100644
@@ -370,6 +370,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)
 {

2.12.0

From: 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 a single knob, the target read latency, 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 read latencies and scales the number of available write 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.

---
 block/Kconfig.iosched |   8 +
 block/Makefile        |   1 +
 block/elevator.c      |   9 +-
 block/kyber-iosched.c | 586 ++++++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 600 insertions(+), 4 deletions(-)
 create mode 100644 block/kyber-iosched.c

index 58fc8684788d..ba6c9be67fa4 100644
@@ -69,6 +69,14 @@ 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 a target latency, it will
+	  self-tune queue depths to achieve that goal.
+
 endmenu
 
 endif

index 081bb680789b..6146d2eaaeaa 100644
@@ -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

index 01139f549b5b..44a6e42ffc1a 100644
@@ -221,14 +221,15 @@ int elevator_init(struct request_queue *q, char *name)
 
 	if (!e) {
 		/*
-		 * For blk-mq devices, we default to using mq-deadline,
-		 * if available, for single queue devices. If deadline
-		 * isn't available OR we have multiple queues, default
-		 * to "none".
+		 * For blk-mq, we default to using mq-deadline for single-queue
+		 * devices and kyber for multi-queue devices. We fall back to
+		 * "none" if the preferred scheduler isn't available.
 		 */
 		if (q->mq_ops) {
 			if (q->nr_hw_queues == 1)
 				e = elevator_get("mq-deadline", false);
+			else
+				e = elevator_get("kyber", false);
 			if (!e)
 				return 0;
 		} else

2.12.0

Of course, this is supposed to say, without Kyber, the reader sees latencies of 8 ms. With Kyber set to a target latency of 1 ms, the actual average latency is just over 1 ms.

[ .. ]

A silent round of applause for you.
Very much appreciated.

And actually, I have been looking at properly supporting host-wide tag maps, so the concept of 'shallow' queue depth might be the way to go here.

And as I have some other questions, too (assigning a new tag on requeue?) it might be an idea to spread this out into a formal session at LSF. If there are some slots left, that is.

Cheers,

Hannes
-- =

Dr. Hannes Reinecke zSeries & Storage
[email protected] +49 911 74053 688
SUSE LINUX Products GmbH, Maxfeldstr. 5, 90409 N=FCrnberg
GF: J. Hawn, J. Guild, F. Imend=F6rffer, HRB 16746 (AG N=FCrnberg)
_______________________________________________
Lsf mailing list
[email protected]
https://lists.linuxfoundation.org/mailman/listinfo/lsf

scritto:

I would be very interested in such a discussion too.

Thanks,
Paolo

_______________________________________________
Lsf mailing list
[email protected]
https://lists.linuxfoundation.org/mailman/listinfo/lsf

OK. Added.

Martin K. Petersen	Oracle Linux Engineering
_______________________________________________
Lsf mailing list
[email protected]
https://lists.linuxfoundation.org/mailman/listinfo/lsf

T24gU2F0LCAyMDE3LTAzLTE4IGF0IDEyOjE0ICswMTAwLCBIYW5uZXMgUmVpbmVja2Ugd3JvdGU6 DQo+IE9uIDAzLzE3LzIwMTcgMTE6MDMgUE0sIE9tYXIgU2FuZG92YWwgd3JvdGU6DQo+ID4gRnJv bTogT21hciBTYW5kb3ZhbCA8b3NhbmRvdkBmYi5jb20+DQo+ID4gDQo+ID4gVGhpcyBwYXRjaCBz ZXJpZXMgaW1wbGVtZW50cyBhbiBJL08gc2NoZWR1bGVyIGZvciBtdWx0aXF1ZXVlIGRldmljZXMN Cj4gPiBjb21iaW5pbmcgc2V2ZXJhbCB0ZWNobmlxdWVzOiB0aGUgc2NhbGFibGUgYml0bWFwIGxp YnJhcnksIHRoZSBuZXcNCj4gPiBibGstc3RhdHMgQVBJLCBhbmQgcXVldWUgZGVwdGggdGhyb3R0 bGluZyBzaW1pbGFyIHRvIGJsay13YnQuDQo+ID4gDQo+ID4gVGhlc2UgcGF0Y2hlcyBhcmUgb24g dG9wIG9mIG15IGVhcmxpZXIgYmxrLXN0YXRzIHNlcmllcyBbMV0uIFRoZXkgYWxzbw0KPiA+IG5l ZWQgYSBmaXggaW4gSmVucycgZm9yLWxpbnVzIGJyYW5jaCBpbiBvcmRlciB0byB3b3JrIHByb3Bl cmx5IFsyXS4NCj4gPiANCj4gPiBQYXRjaGVzIDEgYW5kIDIgaW1wbGVtZW50IGEgbmV3IHNiaXRt YXAgb3BlcmF0aW9uIGFuZCBwYXRjaCAzIGV4cG9ydHMgYQ0KPiA+IHJlcXVpcmVkIGZ1bmN0aW9u LiBQYXRjaCA0IGltcGxlbWVudHMgdGhlIG5ldyBzY2hlZHVsZXIsIG5hbWVkIEt5YmVyLg0KPiA+ IA0KPiA+IFRoZSBjb21taXQgbWVzc2FnZSBpbiBwYXRjaCA0IGRlc2NyaWJlcyBLeWJlciBpbiBk ZXRhaWwuIFRoZSBzY2hlZHVsZXINCj4gPiBlbXBsb3lzIHNvbWUgaGV1cmlzdGljcyB0aGF0IEkn dmUgZXhwZXJpbWVudGVkIHdpdGgsIGJ1dCB0aGF0J3MgcHJvYmFibHkNCj4gPiB0aGUgYXJlYSB0 aGF0IG5lZWRzIHRoZSBtb3N0IHdvcmsuIEknbGwgYmUgYXQgTFNGL01NIG5leHQgd2VlaywgYW5k DQo+ID4gdGhlcmUncyBjdXJyZW50bHkgYSBsaWdodG5pbmcgdGFsayBvbiB0aGUgc2NoZWR1bGUg dG8gZGlzY3Vzcw0KPiA+IGltcHJvdmVtZW50cyBhbmQgZXh0ZW5zaW9ucy4NCj4gPiANCj4gDQo+ IFsgLi4gXQ0KPiANCj4gQSBzaWxlbnQgcm91bmQgb2YgYXBwbGF1c2UgZm9yIHlvdS4NCj4gVmVy eSBtdWNoIGFwcHJlY2lhdGVkLg0KPiANCj4gQW5kIGFjdHVhbGx5LCBJIGhhdmUgYmVlbiBsb29r aW5nIGF0IHByb3Blcmx5IHN1cHBvcnRpbmcgaG9zdC13aWRlIHRhZw0KPiBtYXBzLCBzbyB0aGUg Y29uY2VwdCBvZiAnc2hhbGxvdycgcXVldWUgZGVwdGggbWlnaHQgYmUgdGhlIHdheSB0byBnbyBo ZXJlLg0KPiANCj4gQW5kIGFzIEkgaGF2ZSBzb21lIG90aGVyIHF1ZXN0aW9ucywgdG9vIChhc3Np Z25pbmcgYSBuZXcgdGFnIG9uDQo+IHJlcXVldWU/KSBpdCBtaWdodCBiZSBhbiBpZGVhIHRvIHNw cmVhZCB0aGlzIG91dCBpbnRvIGEgZm9ybWFsIHNlc3Npb24NCj4gYXQgTFNGLiBJZiB0aGVyZSBh cmUgc29tZSBzbG90cyBsZWZ0LCB0aGF0IGlzLg0KDQpJZiBubyBzbG90IGNhbiBiZSBmb3VuZCwg aG93IGFib3V0IG9yZ2FuaXppbmcgYW4gZXZlbmluZyBzZXNzaW9uIGFib3V0IHRoaXMNCm5ldyBz Y2hlZHVsZXI/DQoNCkJhcnQu