[PATCH V2 0/3] blk-mq: improve IO perf in case of none io sched

[PATCH V2 0/3] blk-mq: improve IO perf in case of none io sched

[Ming Lei]

Hi,

The 1st 2 patch improves ctx->lock uses, and it is observed that IOPS
may be improved by ~5% in rand IO test on MegaRaid SAS run by Kashyap.

The 3rd patch fixes rand IO performance regression on MegaRaid SAS
test, still reported by Kashyap.

V2:
	- fix list corruption in patch 1/3

Ming Lei (3):
  blk-mq: use list_splice_tail_init() to insert requests
  blk-mq: only attempt to merge bio if there is rq in sw queue
  blk-mq: dequeue request one by one from sw queue iff hctx is busy

 block/blk-mq-sched.c   | 14 ++++----------
 block/blk-mq.c         | 38 ++++++++++++++++++++++++++++++--------
 include/linux/blk-mq.h |  1 +
 3 files changed, 35 insertions(+), 18 deletions(-)

Cc: Kashyap Desai <kashyap.desai@broadcom.com>
Cc: Laurence Oberman <loberman@redhat.com>
Cc: Omar Sandoval <osandov@fb.com>
Cc: Christoph Hellwig <hch@lst.de>
Cc: Bart Van Assche <bart.vanassche@wdc.com>
Cc: Hannes Reinecke <hare@suse.de>

-- 
2.9.5

[PATCH V2 1/3] blk-mq: use list_splice_tail_init() to insert requests

[Ming Lei]

list_splice_tail_init() is much more faster than inserting each
request one by one, given all requets in 'list' belong to
same sw queue and ctx->lock is required to insert requests.

Cc: Kashyap Desai <kashyap.desai@broadcom.com>
Cc: Laurence Oberman <loberman@redhat.com>
Cc: Omar Sandoval <osandov@fb.com>
Cc: Christoph Hellwig <hch@lst.de>
Cc: Bart Van Assche <bart.vanassche@wdc.com>
Signed-off-by: Ming Lei <ming.lei@redhat.com>
---
 block/blk-mq.c | 14 +++++++-------
 1 file changed, 7 insertions(+), 7 deletions(-)

diff --git a/block/blk-mq.c b/block/blk-mq.c
index 22fe394d0b49..359382b59d40 100644
--- a/block/blk-mq.c
+++ b/block/blk-mq.c
@@ -1545,19 +1545,19 @@ void blk_mq_insert_requests(struct blk_mq_hw_ctx *hctx, struct blk_mq_ctx *ctx,
 			    struct list_head *list)
 
 {
+	struct request *rq;
+
 	/*
 	 * preemption doesn't flush plug list, so it's possible ctx->cpu is
 	 * offline now
 	 */
-	spin_lock(&ctx->lock);
-	while (!list_empty(list)) {
-		struct request *rq;
-
-		rq = list_first_entry(list, struct request, queuelist);
+	list_for_each_entry(rq, list, queuelist) {
 		BUG_ON(rq->mq_ctx != ctx);
-		list_del_init(&rq->queuelist);
-		__blk_mq_insert_req_list(hctx, rq, false);
+		trace_block_rq_insert(hctx->queue, rq);
 	}
+
+	spin_lock(&ctx->lock);
+	list_splice_tail_init(list, &ctx->rq_list);
 	blk_mq_hctx_mark_pending(hctx, ctx);
 	spin_unlock(&ctx->lock);
 }
-- 
2.9.5

[PATCH V2 2/3] blk-mq: only attempt to merge bio if there is rq in sw queue

[Ming Lei]

Only attempt to merge bio iff the ctx->rq_list isn't empty, because:

1) for high-performance SSD, most of times dispatch may succeed, then
there may be nothing left in ctx->rq_list, so don't try to merge over
sw queue if it is empty, then we can save one acquiring of ctx->lock

2) we can't expect good merge performance on per-cpu sw queue, and missing
one merge on sw queue won't be a big deal since tasks can be scheduled from
one CPU to another.

Cc: Kashyap Desai <kashyap.desai@broadcom.com>
Cc: Laurence Oberman <loberman@redhat.com>
Cc: Omar Sandoval <osandov@fb.com>
Cc: Christoph Hellwig <hch@lst.de>
Cc: Bart Van Assche <bart.vanassche@wdc.com>
Reported-by: Kashyap Desai <kashyap.desai@broadcom.com>
Signed-off-by: Ming Lei <ming.lei@redhat.com>
---
 block/blk-mq-sched.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/block/blk-mq-sched.c b/block/blk-mq-sched.c
index 56c493c6cd90..f5745acc2d98 100644
--- a/block/blk-mq-sched.c
+++ b/block/blk-mq-sched.c
@@ -339,7 +339,8 @@ bool __blk_mq_sched_bio_merge(struct request_queue *q, struct bio *bio)
 		return e->type->ops.mq.bio_merge(hctx, bio);
 	}
 
-	if (hctx->flags & BLK_MQ_F_SHOULD_MERGE) {
+	if ((hctx->flags & BLK_MQ_F_SHOULD_MERGE) &&
+			!list_empty_careful(&ctx->rq_list)) {
 		/* default per sw-queue merge */
 		spin_lock(&ctx->lock);
 		ret = blk_mq_attempt_merge(q, ctx, bio);
-- 
2.9.5

[PATCH V2 3/3] blk-mq: dequeue request one by one from sw queue iff hctx is busy

[Ming Lei]

It won't be efficient to dequeue request one by one from sw queue,
but we have to do that when queue is busy for better merge performance.

This patch takes EWMA to figure out if queue is busy, then only dequeue
request one by one from sw queue when queue is busy.

Kashyap verified that this patch basically brings back rand IO perf
on megasas_raid in case of none io scheduler. Meantime I tried this
patch on HDD, and not see obvious performance loss on sequential IO
test too.

Fixes: b347689ffbca ("blk-mq-sched: improve dispatching from sw queue")
Cc: Kashyap Desai <kashyap.desai@broadcom.com>
Cc: Laurence Oberman <loberman@redhat.com>
Cc: Omar Sandoval <osandov@fb.com>
Cc: Christoph Hellwig <hch@lst.de>
Cc: Bart Van Assche <bart.vanassche@wdc.com>
Cc: Hannes Reinecke <hare@suse.de>
Reported-by: Kashyap Desai <kashyap.desai@broadcom.com>
Signed-off-by: Ming Lei <ming.lei@redhat.com>
---
 block/blk-mq-sched.c   | 11 ++---------
 block/blk-mq.c         | 24 +++++++++++++++++++++++-
 include/linux/blk-mq.h |  1 +
 3 files changed, 26 insertions(+), 10 deletions(-)

diff --git a/block/blk-mq-sched.c b/block/blk-mq-sched.c
index f5745acc2d98..8fbf3db32666 100644
--- a/block/blk-mq-sched.c
+++ b/block/blk-mq-sched.c
@@ -219,15 +219,8 @@ void blk_mq_sched_dispatch_requests(struct blk_mq_hw_ctx *hctx)
 		}
 	} else if (has_sched_dispatch) {
 		blk_mq_do_dispatch_sched(hctx);
-	} else if (q->mq_ops->get_budget) {
-		/*
-		 * If we need to get budget before queuing request, we
-		 * dequeue request one by one from sw queue for avoiding
-		 * to mess up I/O merge when dispatch runs out of resource.
-		 *
-		 * TODO: get more budgets, and dequeue more requests in
-		 * one time.
-		 */
+	} else if (READ_ONCE(hctx->busy)) {
+		/* dequeue request one by one from sw queue if queue is busy */
 		blk_mq_do_dispatch_ctx(hctx);
 	} else {
 		blk_mq_flush_busy_ctxs(hctx, &rq_list);
diff --git a/block/blk-mq.c b/block/blk-mq.c
index 359382b59d40..a1a188000d44 100644
--- a/block/blk-mq.c
+++ b/block/blk-mq.c
@@ -1074,6 +1074,25 @@ static bool blk_mq_mark_tag_wait(struct blk_mq_hw_ctx **hctx,
 	return true;
 }
 
+/* update queue busy with EWMA (7/8 * ewma(t)  + 1/8 * busy(t + 1)) */
+static void blk_mq_update_hctx_busy(struct blk_mq_hw_ctx *hctx, unsigned int busy)
+{
+	const unsigned weight = 8;
+	const unsigned factor = 4;
+	unsigned int ewma;
+
+	if (hctx->queue->elevator)
+		return;
+
+	ewma = READ_ONCE(hctx->busy);
+
+	ewma *= weight - 1;
+	ewma += busy << factor;
+	ewma /= weight;
+
+	WRITE_ONCE(hctx->busy, ewma);
+}
+
 #define BLK_MQ_RESOURCE_DELAY	3		/* ms units */
 
 /*
@@ -1210,8 +1229,11 @@ bool blk_mq_dispatch_rq_list(struct request_queue *q, struct list_head *list,
 		else if (needs_restart && (ret == BLK_STS_RESOURCE))
 			blk_mq_delay_run_hw_queue(hctx, BLK_MQ_RESOURCE_DELAY);
 
+		blk_mq_update_hctx_busy(hctx, 1);
+
 		return false;
-	}
+	} else
+		blk_mq_update_hctx_busy(hctx, 0);
 
 	/*
 	 * If the host/device is unable to accept more work, inform the
diff --git a/include/linux/blk-mq.h b/include/linux/blk-mq.h
index e3147eb74222..a5113e22d720 100644
--- a/include/linux/blk-mq.h
+++ b/include/linux/blk-mq.h
@@ -34,6 +34,7 @@ struct blk_mq_hw_ctx {
 
 	struct sbitmap		ctx_map;
 
+	unsigned int		busy;
 	struct blk_mq_ctx	*dispatch_from;
 
 	struct blk_mq_ctx	**ctxs;
-- 
2.9.5

Re: [PATCH V2 1/3] blk-mq: use list_splice_tail_init() to insert requests

[Christoph Hellwig]

On Fri, Jun 29, 2018 at 04:12:50PM +0800, Ming Lei wrote:
> list_splice_tail_init() is much more faster than inserting each
> request one by one, given all requets in 'list' belong to
> same sw queue and ctx->lock is required to insert requests.

Looks fine:

Reviewed-by: Christoph Hellwig <hch@lst.de>

We should still make the trace loop conditional, but than can be a
separate patch.

Re: [PATCH V2 2/3] blk-mq: only attempt to merge bio if there is rq in sw queue

[Christoph Hellwig]

On Fri, Jun 29, 2018 at 04:12:51PM +0800, Ming Lei wrote:
> Only attempt to merge bio iff the ctx->rq_list isn't empty, because:
> 
> 1) for high-performance SSD, most of times dispatch may succeed, then
> there may be nothing left in ctx->rq_list, so don't try to merge over
> sw queue if it is empty, then we can save one acquiring of ctx->lock
> 
> 2) we can't expect good merge performance on per-cpu sw queue, and missing
> one merge on sw queue won't be a big deal since tasks can be scheduled from
> one CPU to another.

Looks good,

Reviewed-by: Christoph Hellwig <hch@lst.de>

Re: [PATCH V2 3/3] blk-mq: dequeue request one by one from sw queue iff hctx is busy

[Christoph Hellwig]

> +/* update queue busy with EWMA (7/8 * ewma(t)  + 1/8 * busy(t + 1)) */
> +static void blk_mq_update_hctx_busy(struct blk_mq_hw_ctx *hctx, unsigned int busy)

Overly long line.  Also busy really is a bool, so I think we should
pass it as such.

Also I think this needs a much better comment describing why we
are using this algorith.  Also expanding the EWMA acronym would help,
I had to look it up first.

> +	const unsigned weight = 8;
> +	const unsigned factor = 4;

Where do these magic constants come from?

> +	unsigned int ewma;
> +
> +	if (hctx->queue->elevator)
> +		return;
> +
> +	ewma = READ_ONCE(hctx->busy);
> +
> +	ewma *= weight - 1;
> +	ewma += busy << factor;

With the bool parameter and expanding the "factor" which really is
a shift value this would be:

	if (busy)
		ewma += 16;

which at least is a little more understandable, although still not
great.

Re: [PATCH V2 3/3] blk-mq: dequeue request one by one from sw queue iff hctx is busy

[Jens Axboe]

On 6/29/18 2:12 AM, Ming Lei wrote:
> It won't be efficient to dequeue request one by one from sw queue,
> but we have to do that when queue is busy for better merge performance.
> 
> This patch takes EWMA to figure out if queue is busy, then only dequeue
> request one by one from sw queue when queue is busy.
> 
> Kashyap verified that this patch basically brings back rand IO perf
> on megasas_raid in case of none io scheduler. Meantime I tried this
> patch on HDD, and not see obvious performance loss on sequential IO
> test too.

Outside of the comments of others, please also export ->busy from
the blk-mq debugfs code.

> diff --git a/include/linux/blk-mq.h b/include/linux/blk-mq.h
> index e3147eb74222..a5113e22d720 100644
> --- a/include/linux/blk-mq.h
> +++ b/include/linux/blk-mq.h
> @@ -34,6 +34,7 @@ struct blk_mq_hw_ctx {
>  
>  	struct sbitmap		ctx_map;
>  
> +	unsigned int		busy;
>  	struct blk_mq_ctx	*dispatch_from;
>  
>  	struct blk_mq_ctx	**ctxs;

This adds another hole. Consider swapping it a bit, ala:

	struct blk_mq_ctx       *dispatch_from;
	unsigned int            busy;

	unsigned int            nr_ctx;
	struct blk_mq_ctx       **ctxs;

to eliminate a hole, instead of adding one more.

-- 
Jens Axboe

Re: [PATCH V2 3/3] blk-mq: dequeue request one by one from sw queue iff hctx is busy

[Ming Lei]

On Fri, Jun 29, 2018 at 10:39:44AM +0200, Christoph Hellwig wrote:
> > +/* update queue busy with EWMA (7/8 * ewma(t)  + 1/8 * busy(t + 1)) */
> > +static void blk_mq_update_hctx_busy(struct blk_mq_hw_ctx *hctx, unsigned int busy)
> 
> Overly long line.  Also busy really is a bool, so I think we should
> pass it as such.

OK.

> 
> Also I think this needs a much better comment describing why we
> are using this algorith.  Also expanding the EWMA acronym would help,
> I had to look it up first.

EWMA(exponentially weighted moving average)[1] is used here to compute
if queue is busy, because it is one simple way to compute the 'average'
value of queue busy. Also weight is applied here so that it can decrease
exponentially.

In this patch, the weight is 7/8 for history busy, and 1/8 for current
busy.

[1] https://en.wikipedia.org/wiki/Moving_average#cite_note-5

> 
> > +	const unsigned weight = 8;
> > +	const unsigned factor = 4;
> 
> Where do these magic constants come from?

As mentioned above, 'weight' is for the weight in EWMA, and factor is
applied for not computing busy as zero.

> 
> > +	unsigned int ewma;
> > +
> > +	if (hctx->queue->elevator)
> > +		return;
> > +
> > +	ewma = READ_ONCE(hctx->busy);
> > +
> > +	ewma *= weight - 1;
> > +	ewma += busy << factor;
> 
> With the bool parameter and expanding the "factor" which really is
> a shift value this would be:
> 
> 	if (busy)
> 		ewma += 16;
> 
> which at least is a little more understandable, although still not
> great.

Now we just use 1 as busy, 0 as non-busy, in theory it may be possible
to describe how busy the queue is by passing a integer value.

Thanks,
Ming

Re: [PATCH V2 3/3] blk-mq: dequeue request one by one from sw queue iff hctx is busy

[Ming Lei]

On Fri, Jun 29, 2018 at 08:58:16AM -0600, Jens Axboe wrote:
> On 6/29/18 2:12 AM, Ming Lei wrote:
> > It won't be efficient to dequeue request one by one from sw queue,
> > but we have to do that when queue is busy for better merge performance.
> > 
> > This patch takes EWMA to figure out if queue is busy, then only dequeue
> > request one by one from sw queue when queue is busy.
> > 
> > Kashyap verified that this patch basically brings back rand IO perf
> > on megasas_raid in case of none io scheduler. Meantime I tried this
> > patch on HDD, and not see obvious performance loss on sequential IO
> > test too.
> 
> Outside of the comments of others, please also export ->busy from
> the blk-mq debugfs code.

Good idea!

> 
> > diff --git a/include/linux/blk-mq.h b/include/linux/blk-mq.h
> > index e3147eb74222..a5113e22d720 100644
> > --- a/include/linux/blk-mq.h
> > +++ b/include/linux/blk-mq.h
> > @@ -34,6 +34,7 @@ struct blk_mq_hw_ctx {
> >  
> >  	struct sbitmap		ctx_map;
> >  
> > +	unsigned int		busy;
> >  	struct blk_mq_ctx	*dispatch_from;
> >  
> >  	struct blk_mq_ctx	**ctxs;
> 
> This adds another hole. Consider swapping it a bit, ala:
> 
> 	struct blk_mq_ctx       *dispatch_from;
> 	unsigned int            busy;
> 
> 	unsigned int            nr_ctx;
> 	struct blk_mq_ctx       **ctxs;
> 
> to eliminate a hole, instead of adding one more.

OK

Thanks,
Ming