blk-mq-sched: improve sequential I/O performance

When hw queue is busy, we shouldn't take requests from scheduler queue any more, otherwise it is difficult to do IO merge.

This patch fixes the awful IO performance on some SCSI devices(lpfc, qla2xxx, ...) when mq-deadline/kyber is used by not taking requests if hw queue is busy.

Reviewed-by Bart Van Assche <[email protected]>

Reviewed-by Christoph Hellwig <[email protected]>

Signed-off-by Ming Lei <[email protected]>

---
 block/blk-mq-sched.c | 12 ++++++------
 1 file changed, 6 insertions(+), 6 deletions(-)

block/blk-mq-sched.c +6 -6

index 4ab69435708c..eca011fdfa0e 100644
@@ -94,7 +94,7 @@ void blk_mq_sched_dispatch_requests(struct blk_mq_hw_ctx *hctx)
 	struct request_queue *q = hctx->queue;
 	struct elevator_queue *e = q->elevator;
 	const bool has_sched_dispatch = e && e->type->ops.mq.dispatch_request;
-	bool did_work = false;
+	bool do_sched_dispatch = true;
 	LIST_HEAD(rq_list);
 
 	/* RCU or SRCU read lock is needed before checking quiesced flag */

@@ -125,18 +125,18 @@ void blk_mq_sched_dispatch_requests(struct blk_mq_hw_ctx *hctx)
 	 */
 	if (!list_empty(&rq_list)) {
 		blk_mq_sched_mark_restart_hctx(hctx);
-		did_work = blk_mq_dispatch_rq_list(q, &rq_list);
+		do_sched_dispatch = blk_mq_dispatch_rq_list(q, &rq_list);
 	} else if (!has_sched_dispatch) {
 		blk_mq_flush_busy_ctxs(hctx, &rq_list);
 		blk_mq_dispatch_rq_list(q, &rq_list);
 	}
 
 	/*
-	 * We want to dispatch from the scheduler if we had no work left
-	 * on the dispatch list, OR if we did have work but weren't able
-	 * to make progress.
+	 * We want to dispatch from the scheduler if there was nothing
+	 * on the dispatch list or we were able to dispatch from the
+	 * dispatch list.
 	 */
-	if (!did_work && has_sched_dispatch) {
+	if (do_sched_dispatch && has_sched_dispatch) {
 		do {
 			struct request *rq;
 

Signature · 1 line

2.9.5

We need to iterate ctx starting from any ctx in round robin way, so introduce this helper.

Cc Omar Sandoval <[email protected]>

Signed-off-by Ming Lei <[email protected]>

---
 include/linux/sbitmap.h | 64 ++++++++++++++++++++++++++++++++++++-------------
 1 file changed, 47 insertions(+), 17 deletions(-)

SCSI devices use host-wide tagset, and the shared driver tag space is often quite big. Meantime there is also queue depth for each lun( .cmd_per_lun), which is often small, for example, on both lpfc and qla2xxx, .cmd_per_lun is just 3.

So lots of requests may stay in sw queue, and we always flush all belonging to same hw queue and dispatch them all to driver, unfortunately it is easy to cause queue busy because of the small .cmd_per_lun. Once these requests are flushed out, they have to stay in hctx->dispatch, and no bio merge can participate into these requests, and sequential IO performance is hurt a lot.

This patch introduces blk_mq_dequeue_from_ctx for dequeuing request from sw queue so that we can dispatch them in scheduler's way, then we can avoid to dequeue too many requests from sw queue when ->dispatch isn't flushed completely.

This patch improves dispatching from sw queue when there is per-request-queue queue depth by taking request one by one from sw queue, just like the way of IO scheduler.

Reviewed-by Omar Sandoval <[email protected]>

Reviewed-by Bart Van Assche <[email protected]>

Signed-off-by Ming Lei <[email protected]>

---
 block/blk-mq-sched.c   | 50 ++++++++++++++++++++++++++++++++++++++++++++++++--
 block/blk-mq.c         | 39 +++++++++++++++++++++++++++++++++++++++
 block/blk-mq.h         |  2 ++
 include/linux/blk-mq.h |  2 ++
 4 files changed, 91 insertions(+), 2 deletions(-)

block/blk-mq-sched.c +48 -2

index be29ba849408..14b354f617e5 100644
@@ -104,6 +104,39 @@ static void blk_mq_do_dispatch_sched(struct blk_mq_hw_ctx *hctx)
 	} while (blk_mq_dispatch_rq_list(q, &rq_list));
 }
 
+static struct blk_mq_ctx *blk_mq_next_ctx(struct blk_mq_hw_ctx *hctx,
+					  struct blk_mq_ctx *ctx)
+{
+	unsigned idx = ctx->index_hw;
+
+	if (++idx == hctx->nr_ctx)
+		idx = 0;
+
+	return hctx->ctxs[idx];
+}
+
+static void blk_mq_do_dispatch_ctx(struct blk_mq_hw_ctx *hctx)
+{
+	struct request_queue *q = hctx->queue;
+	LIST_HEAD(rq_list);
+	struct blk_mq_ctx *ctx = READ_ONCE(hctx->dispatch_from);
+
+	do {
+		struct request *rq;
+
+		rq = blk_mq_dequeue_from_ctx(hctx, ctx);
+		if (!rq)
+			break;
+		list_add(&rq->queuelist, &rq_list);
+
+		/* round robin for fair dispatch */
+		ctx = blk_mq_next_ctx(hctx, rq->mq_ctx);
+
+	} while (blk_mq_dispatch_rq_list(q, &rq_list));
+
+	WRITE_ONCE(hctx->dispatch_from, ctx);
+}
+
 void blk_mq_sched_dispatch_requests(struct blk_mq_hw_ctx *hctx)
 {
 	struct request_queue *q = hctx->queue;

@@ -143,10 +176,23 @@ void blk_mq_sched_dispatch_requests(struct blk_mq_hw_ctx *hctx)
 	 */
 	if (!list_empty(&rq_list)) {
 		blk_mq_sched_mark_restart_hctx(hctx);
-		if (blk_mq_dispatch_rq_list(q, &rq_list) && has_sched_dispatch)
-			blk_mq_do_dispatch_sched(hctx);
+		if (blk_mq_dispatch_rq_list(q, &rq_list)) {
+			if (has_sched_dispatch)
+				blk_mq_do_dispatch_sched(hctx);
+			else
+				blk_mq_do_dispatch_ctx(hctx);
+		}
 	} else if (has_sched_dispatch) {
 		blk_mq_do_dispatch_sched(hctx);
+	} else if (q->queue_depth) {
+		/*
+		 * If there is per-request_queue depth, we dequeue
+		 * request one by one from sw queue for avoiding to mess
+		 * up I/O merge when dispatch runs out of resource, which
+		 * can be triggered easily when there is per-request_queue
+		 * queue depth or .cmd_per_lun, such as SCSI device.
+		 */
+		blk_mq_do_dispatch_ctx(hctx);
 	} else {
 		blk_mq_flush_busy_ctxs(hctx, &rq_list);
 		blk_mq_dispatch_rq_list(q, &rq_list);

block/blk-mq.c +39 -0

index 076cbab9c3e0..394cb75d66fa 100644
@@ -911,6 +911,45 @@ void blk_mq_flush_busy_ctxs(struct blk_mq_hw_ctx *hctx, struct list_head *list)
 }
 EXPORT_SYMBOL_GPL(blk_mq_flush_busy_ctxs);
 
+struct dispatch_rq_data {
+	struct blk_mq_hw_ctx *hctx;
+	struct request *rq;
+};
+
+static bool dispatch_rq_from_ctx(struct sbitmap *sb, unsigned int bitnr,
+		void *data)
+{
+	struct dispatch_rq_data *dispatch_data = data;
+	struct blk_mq_hw_ctx *hctx = dispatch_data->hctx;
+	struct blk_mq_ctx *ctx = hctx->ctxs[bitnr];
+
+	spin_lock(&ctx->lock);
+	if (unlikely(!list_empty(&ctx->rq_list))) {
+		dispatch_data->rq = list_entry_rq(ctx->rq_list.next);
+		list_del_init(&dispatch_data->rq->queuelist);
+		if (list_empty(&ctx->rq_list))
+			sbitmap_clear_bit(sb, bitnr);
+	}
+	spin_unlock(&ctx->lock);
+
+	return !dispatch_data->rq;
+}
+
+struct request *blk_mq_dequeue_from_ctx(struct blk_mq_hw_ctx *hctx,
+					struct blk_mq_ctx *start)
+{
+	unsigned off = start ? start->index_hw : 0;
+	struct dispatch_rq_data data = {
+		.hctx = hctx,
+		.rq   = NULL,
+	};
+
+	__sbitmap_for_each_set(&hctx->ctx_map, off,
+			       dispatch_rq_from_ctx, &data);
+
+	return data.rq;
+}
+
 static inline unsigned int queued_to_index(unsigned int queued)
 {
 	if (!queued)

block/blk-mq.h +2 -0

index ef15b3414da5..231cfb0d973b 100644
@@ -35,6 +35,8 @@ void blk_mq_flush_busy_ctxs(struct blk_mq_hw_ctx *hctx, struct list_head *list);
 bool blk_mq_hctx_has_pending(struct blk_mq_hw_ctx *hctx);
 bool blk_mq_get_driver_tag(struct request *rq, struct blk_mq_hw_ctx **hctx,
 				bool wait);
+struct request *blk_mq_dequeue_from_ctx(struct blk_mq_hw_ctx *hctx,
+					struct blk_mq_ctx *start);
 
 /*
  * Internal helpers for allocating/freeing the request map

include/linux/blk-mq.h +2 -0

index 50c6485cb04f..7b7a366a97f3 100644
@@ -30,6 +30,8 @@ struct blk_mq_hw_ctx {
 
 	struct sbitmap		ctx_map;
 
+	struct blk_mq_ctx	*dispatch_from;
+
 	struct blk_mq_ctx	**ctxs;
 	unsigned int		nr_ctx;
 

Signature · 1 line

2.9.5

Quoted 17 lines · Ming Lei

SCSI devices use host-wide tagset, and the shared driver tag space is often quite big. Meantime there is also queue depth for each lun( .cmd_per_lun), which is often small, for example, on both lpfc and qla2xxx, .cmd_per_lun is just 3.

So lots of requests may stay in sw queue, and we always flush all belonging to same hw queue and dispatch them all to driver, unfortunately it is easy to cause queue busy because of the small .cmd_per_lun. Once these requests are flushed out, they have to stay in hctx->dispatch, and no bio merge can participate into these requests, and sequential IO performance is hurt a lot.

This patch introduces blk_mq_dequeue_from_ctx for dequeuing request from sw queue so that we can dispatch them in scheduler's way, then we can avoid to dequeue too many requests from sw queue when ->dispatch isn't flushed completely.

Quoted 3 lines

This patch improves dispatching from sw queue when there is per-request-queue queue depth by taking request one by one from sw queue, just like the way of IO scheduler.

This still didn't address Jens' concern about using q->queue_depth as the heuristic for whether to do the full sw queue flush or one-by-one dispatch. The EWMA approach is a bit too complex for now, can you please try the heuristic of whether the driver ever returned BLK_STS_RESOURCE?

Quoted 18 lines · Omar Sandoval

Quoted 17 lines · Ming Lei

SCSI devices use host-wide tagset, and the shared driver tag space is often quite big. Meantime there is also queue depth for each lun( .cmd_per_lun), which is often small, for example, on both lpfc and qla2xxx, .cmd_per_lun is just 3.

So lots of requests may stay in sw queue, and we always flush all belonging to same hw queue and dispatch them all to driver, unfortunately it is easy to cause queue busy because of the small .cmd_per_lun. Once these requests are flushed out, they have to stay in hctx->dispatch, and no bio merge can participate into these requests, and sequential IO performance is hurt a lot.

This patch introduces blk_mq_dequeue_from_ctx for dequeuing request from sw queue so that we can dispatch them in scheduler's way, then we can avoid to dequeue too many requests from sw queue when ->dispatch isn't flushed completely.

Quoted 8 lines

Quoted 3 lines

This patch improves dispatching from sw queue when there is per-request-queue queue depth by taking request one by one from sw queue, just like the way of IO scheduler.

This still didn't address Jens' concern about using q->queue_depth as the heuristic for whether to do the full sw queue flush or one-by-one dispatch. The EWMA approach is a bit too complex for now, can you please try the heuristic of whether the driver ever returned BLK_STS_RESOURCE?

That can be done easily, but I am not sure if it is good.

For example, inside queue rq path of NVMe, kmalloc(GFP_ATOMIC) is often used, if kmalloc() returns NULL just once, BLK_STS_RESOURCE will be returned to blk-mq, then blk-mq will never do full sw queue flush even when kmalloc() always succeed from that time on.

Even EWMA approach isn't good on SCSI-MQ too, because some SCSI's .cmd_per_lun is very small, such as 3 on lpfc and qla2xxx, and one full flush will trigger BLK_STS_RESOURCE easily.

So I suggest to use the way of q->queue_depth first, since we don't get performance degrade report on other devices(!q->queue_depth) with blk-mq. We can improve this way in the future if we have better approach.

What do you think about it?

Quoted 28 lines · Ming Lei

Quoted 18 lines · Omar Sandoval

Quoted 17 lines · Ming Lei

SCSI devices use host-wide tagset, and the shared driver tag space is often quite big. Meantime there is also queue depth for each lun( .cmd_per_lun), which is often small, for example, on both lpfc and qla2xxx, .cmd_per_lun is just 3.

So lots of requests may stay in sw queue, and we always flush all belonging to same hw queue and dispatch them all to driver, unfortunately it is easy to cause queue busy because of the small .cmd_per_lun. Once these requests are flushed out, they have to stay in hctx->dispatch, and no bio merge can participate into these requests, and sequential IO performance is hurt a lot.

This patch introduces blk_mq_dequeue_from_ctx for dequeuing request from sw queue so that we can dispatch them in scheduler's way, then we can avoid to dequeue too many requests from sw queue when ->dispatch isn't flushed completely.

Quoted 8 lines

Quoted 3 lines

This patch improves dispatching from sw queue when there is per-request-queue queue depth by taking request one by one from sw queue, just like the way of IO scheduler.

This still didn't address Jens' concern about using q->queue_depth as the heuristic for whether to do the full sw queue flush or one-by-one dispatch. The EWMA approach is a bit too complex for now, can you please try the heuristic of whether the driver ever returned BLK_STS_RESOURCE?

Quoted 7 lines

That can be done easily, but I am not sure if it is good.

For example, inside queue rq path of NVMe, kmalloc(GFP_ATOMIC) is often used, if kmalloc() returns NULL just once, BLK_STS_RESOURCE will be returned to blk-mq, then blk-mq will never do full sw queue flush even when kmalloc() always succeed from that time on.

Have it be a bit more than a single bit, then. Reset it every x IOs or something like that, that'll be more representative of transient busy conditions anyway.

Quoted 37 lines · Jens Axboe

Quoted 35 lines · Ming Lei

Quoted 18 lines · Omar Sandoval

Quoted 17 lines · Ming Lei

SCSI devices use host-wide tagset, and the shared driver tag space is often quite big. Meantime there is also queue depth for each lun( .cmd_per_lun), which is often small, for example, on both lpfc and qla2xxx, .cmd_per_lun is just 3.

So lots of requests may stay in sw queue, and we always flush all belonging to same hw queue and dispatch them all to driver, unfortunately it is easy to cause queue busy because of the small .cmd_per_lun. Once these requests are flushed out, they have to stay in hctx->dispatch, and no bio merge can participate into these requests, and sequential IO performance is hurt a lot.

This patch introduces blk_mq_dequeue_from_ctx for dequeuing request from sw queue so that we can dispatch them in scheduler's way, then we can avoid to dequeue too many requests from sw queue when ->dispatch isn't flushed completely.

Quoted 8 lines

Quoted 3 lines

This patch improves dispatching from sw queue when there is per-request-queue queue depth by taking request one by one from sw queue, just like the way of IO scheduler.

This still didn't address Jens' concern about using q->queue_depth as the heuristic for whether to do the full sw queue flush or one-by-one dispatch. The EWMA approach is a bit too complex for now, can you please try the heuristic of whether the driver ever returned BLK_STS_RESOURCE?

That can be done easily, but I am not sure if it is good.

For example, inside queue rq path of NVMe, kmalloc(GFP_ATOMIC) is often used, if kmalloc() returns NULL just once, BLK_STS_RESOURCE will be returned to blk-mq, then blk-mq will never do full sw queue flush even when kmalloc() always succeed from that time on.

Quoted 3 lines

Have it be a bit more than a single bit, then. Reset it every x IOs or something like that, that'll be more representative of transient busy conditions anyway.

OK, that can be done via a simplified EWMA by considering the dispatch result only.

Even EWMA approach isn't good on SCSI-MQ too, because some SCSI's .cmd_per_lun is very small, such as 3 on lpfc and qla2xxx, and one full flush will trigger BLK_STS_RESOURCE easily.

So I suggest to use the way of q->queue_depth first, since we don't get performance degrade report on other devices(!q->queue_depth) with blk-mq. We can improve this way in the future if we have better approach.

Quoted 9 lines · Ming Lei

Even EWMA approach isn't good on SCSI-MQ too, because some SCSI's .cmd_per_lun is very small, such as 3 on lpfc and qla2xxx, and one full flush will trigger BLK_STS_RESOURCE easily.

So I suggest to use the way of q->queue_depth first, since we don't get performance degrade report on other devices(!q->queue_depth) with blk-mq. We can improve this way in the future if we have better approach.

Measurements have shown that even with this patch series applied sequential I/O performance is still below that of the legacy block and SCSI layers. So this patch series is not the final solution. (See also John Garry's e-mail of October 10th - https://lkml.org/lkml/2017/10/10/401). I have been wondering what could be causing that performance difference. Maybe it's because requests can reside for a while in the hctx dispatch queue and hence are unvisible for the scheduler while in the hctx dispatch queue? Should we modify blk_mq_dispatch_rq_list() such that it puts back requests that have not been accepted by .queue_rq() onto the scheduler queue(s) instead of to the hctx dispatch queue? If we would make that change, would it allow us to drop patch "blk-mq-sched: improve dispatching from sw queue"?

Quoted 11 lines · Bart Van Assche

Quoted 9 lines · Ming Lei

Even EWMA approach isn't good on SCSI-MQ too, because some SCSI's .cmd_per_lun is very small, such as 3 on lpfc and qla2xxx, and one full flush will trigger BLK_STS_RESOURCE easily.

So I suggest to use the way of q->queue_depth first, since we don't get performance degrade report on other devices(!q->queue_depth) with blk-mq. We can improve this way in the future if we have better approach.

Quoted 11 lines

Measurements have shown that even with this patch series applied sequential I/O performance is still below that of the legacy block and SCSI layers. So this patch series is not the final solution. (See also John Garry's e-mail of October 10th - https://lkml.org/lkml/2017/10/10/401). I have been wondering what could be causing that performance difference. Maybe it's because requests can reside for a while in the hctx dispatch queue and hence are unvisible for the scheduler while in the hctx dispatch queue? Should we modify blk_mq_dispatch_rq_list() such that it puts back requests that have not been accepted by .queue_rq() onto the scheduler queue(s) instead of to the hctx dispatch queue? If we would make that change, would it allow us to drop patch "blk-mq-sched: improve dispatching from sw queue"?

Yes, it's clear that even with the full series, we're not completely there yet. We are closer, though, and I do want to close that gap up as much as we can. I think everybody will be more motivated and have an easier time getting the last bit of the way there, once we have a good foundation in.

It may be the reason that you hint at, if we do see a lot of requeueing or BUSY in the test case. That would prematurely move requests from the schedulers knowledge and into the hctx->dispatch holding area. It'd be useful to have a standard SATA test run and see if we're missing merging in that case (since merging is what it boils down to). If we are, then it's not hctx->dispatch issues.

During dispatching, we moved all requests from hctx->dispatch to one temporary list, then dispatch them one by one from this list. Unfortunately during this period, run queue from other contexts may think the queue is idle, then start to dequeue from sw/scheduler queue and still try to dispatch because ->dispatch is empty. This way hurts sequential I/O performance because requests are dequeued when lld queue is busy.

This patch introduces the state of BLK_MQ_S_DISPATCH_BUSY to make sure that request isn't dequeued until ->dispatch is flushed.

Reviewed-by Bart Van Assche <[email protected]>

Reviewed-by Christoph Hellwig <[email protected]>

Signed-off-by Ming Lei <[email protected]>

---
 block/blk-mq-debugfs.c |  1 +
 block/blk-mq-sched.c   | 38 ++++++++++++++++++++++++++++++++------
 block/blk-mq.c         |  5 +++++
 include/linux/blk-mq.h |  1 +
 4 files changed, 39 insertions(+), 6 deletions(-)