blk-mq-sched: improve SCSI-MQ 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]>

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

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

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

index 4ab69435708c..845e5baf8af1 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,7 +125,7 @@ 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);

@@ -136,7 +136,7 @@ void blk_mq_sched_dispatch_requests(struct blk_mq_hw_ctx *hctx)
 	 * on the dispatch list, OR if we did have work but weren't able
 	 * to make progress.
 	 */
-	if (!did_work && has_sched_dispatch) {
+	if (do_sched_dispatch && has_sched_dispatch) {
 		do {
 			struct request *rq;
 

Signature · 1 line

2.9.5

Quoted 8 lines · Ming Lei

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.

Quoted 1 line

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

Jens and I did some testing with xfs/297 and couldn't find any issues, so

Reviewed-by Omar Sandoval <[email protected]>

Quoted 17 lines

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

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

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

index 4ab69435708c..845e5baf8af1 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);
 

Quoted 11 lines

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

 	/* RCU or SRCU read lock is needed before checking quiesced flag */

@@ -125,7 +125,7 @@ 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);

block/blk-mq-sched.c void blk_mq_sched_dispatch_requests(struct blk_mq_hw_ctx *hctx) · line 138

Quoted 3 lines

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

@@ -136,7 +136,7 @@ void blk_mq_sched_dispatch_requests(struct blk_mq_hw_ctx *hctx)
 	 * on the dispatch list, OR if we did have work but weren't able
 	 * to make progress.
 	 */

Quoted 8 lines

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

-	if (!did_work && has_sched_dispatch) {
+	if (do_sched_dispatch && has_sched_dispatch) {
 		do {
 			struct request *rq;
 

Signature · 1 line

2.9.5

Quoted 9 lines · Omar Sandoval

Quoted 8 lines · Ming Lei

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.

Quoted 6 lines

Quoted 1 line

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

Jens and I did some testing with xfs/297 and couldn't find any issues, so

Reviewed-by Omar Sandoval <[email protected]>

I take it back, the comment below needs to be updated

Quoted 17 lines

Quoted 17 lines

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

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

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

index 4ab69435708c..845e5baf8af1 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);
 

Quoted 14 lines

Quoted 11 lines

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

 	/* RCU or SRCU read lock is needed before checking quiesced flag */

@@ -125,7 +125,7 @@ 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);

block/blk-mq-sched.c void blk_mq_sched_dispatch_requests(struct blk_mq_hw_ctx *hctx) · line 138

Quoted 3 lines

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

@@ -136,7 +136,7 @@ void blk_mq_sched_dispatch_requests(struct blk_mq_hw_ctx *hctx)
 	 * on the dispatch list, OR if we did have work but weren't able
 	 * to make progress.
 	 */

This should be updated to say:

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.

Quoted 53 lines · Omar Sandoval

Quoted 9 lines · Omar Sandoval

Quoted 8 lines · Ming Lei

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.

Quoted 6 lines

Quoted 1 line

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

Jens and I did some testing with xfs/297 and couldn't find any issues, so

Reviewed-by Omar Sandoval <[email protected]>

I take it back, the comment below needs to be updated

Quoted 17 lines

Quoted 17 lines

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

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

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

index 4ab69435708c..845e5baf8af1 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);
 

Quoted 14 lines

Quoted 11 lines

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

 	/* RCU or SRCU read lock is needed before checking quiesced flag */

@@ -125,7 +125,7 @@ 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);

block/blk-mq-sched.c void blk_mq_sched_dispatch_requests(struct blk_mq_hw_ctx *hctx) · line 138

Quoted 3 lines

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

@@ -136,7 +136,7 @@ void blk_mq_sched_dispatch_requests(struct blk_mq_hw_ctx *hctx)
 	 * on the dispatch list, OR if we did have work but weren't able
 	 * to make progress.
 	 */

This should be updated to say:

Quoted 2 lines

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.

By the way, did you experiment with changing blk_mq_dispatch_rq_list() to return true IFF _all_ requests were dispatched, instead of _any_ requests were dispatched?

Quoted 9 lines · Omar Sandoval

Quoted 8 lines · Ming Lei

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.

Quoted 6 lines

Quoted 1 line

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

Jens and I did some testing with xfs/297 and couldn't find any issues, so

Reviewed-by Omar Sandoval <[email protected]>

I take it back, the comment below needs to be updated

Quoted 17 lines

Quoted 17 lines

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

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

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

index 4ab69435708c..845e5baf8af1 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);
 

Quoted 14 lines

Quoted 11 lines

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

 	/* RCU or SRCU read lock is needed before checking quiesced flag */

@@ -125,7 +125,7 @@ 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);

block/blk-mq-sched.c void blk_mq_sched_dispatch_requests(struct blk_mq_hw_ctx *hctx) · line 138

Quoted 3 lines

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

@@ -136,7 +136,7 @@ void blk_mq_sched_dispatch_requests(struct blk_mq_hw_ctx *hctx)
 	 * on the dispatch list, OR if we did have work but weren't able
 	 * to make progress.
 	 */

This should be updated to say:

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.

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 | 54 ++++++++++++++++++++++++++++++++++++-------------
 1 file changed, 40 insertions(+), 14 deletions(-)

include/linux/sbitmap.h +13 -6

index a1904aadbc45..2329b9e1a0e2 100644
@@ -211,10 +211,14 @@ bool sbitmap_any_bit_set(const struct sbitmap *sb);
  */
 bool sbitmap_any_bit_clear(const struct sbitmap *sb);
 
+#define SB_NR_TO_INDEX(sb, bitnr) ((bitnr) >> (sb)->shift)
+#define SB_NR_TO_BIT(sb, bitnr) ((bitnr) & ((1U << (sb)->shift) - 1U))
+
 typedef bool (*sb_for_each_fn)(struct sbitmap *, unsigned int, void *);
 
 /**
  * sbitmap_for_each_set() - Iterate over each set bit in a &struct sbitmap.
+ * @off: Where to start the iteration
  * @sb: Bitmap to iterate over.
  * @fn: Callback. Should return true to continue or false to break early.
  * @data: Pointer to pass to callback.

@@ -222,35 +226,57 @@ typedef bool (*sb_for_each_fn)(struct sbitmap *, unsigned int, void *);
  * This is inline even though it's non-trivial so that the function calls to the
  * callback will hopefully get optimized away.
  */
-static inline void sbitmap_for_each_set(struct sbitmap *sb, sb_for_each_fn fn,
-					void *data)
+static inline void __sbitmap_for_each_set(struct sbitmap *sb,
+					  unsigned int off,
+					  sb_for_each_fn fn, void *data)
 {
-	unsigned int i;
+	unsigned int index = SB_NR_TO_INDEX(sb, off);
+	unsigned int nr = SB_NR_TO_BIT(sb, off);
+	unsigned int scanned = 0;
 
-	for (i = 0; i < sb->map_nr; i++) {
-		struct sbitmap_word *word = &sb->map[i];
-		unsigned int off, nr;
+	while (1) {
+		struct sbitmap_word *word = &sb->map[index];
+		unsigned int depth = min_t(unsigned int, word->depth - nr,

include/linux/sbitmap.h +9 -5

+		off = index << sb->shift;
 		while (1) {
-			nr = find_next_bit(&word->word, word->depth, nr);
-			if (nr >= word->depth)
+			nr = find_next_bit(&word->word, depth, nr);
+			if (nr >= depth)
 				break;
-
 			if (!fn(sb, off + nr, data))
 				return;
 
 			nr++;
 		}
+ next:
+		if (scanned >= sb->depth)
+			break;
+		nr = 0;
+		if (++index >= sb->map_nr)
+			index = 0;
 	}
 }
 
-#define SB_NR_TO_INDEX(sb, bitnr) ((bitnr) >> (sb)->shift)
-#define SB_NR_TO_BIT(sb, bitnr) ((bitnr) & ((1U << (sb)->shift) - 1U))

include/linux/sbitmap.h +6 -0

+ */
+static inline void sbitmap_for_each_set(struct sbitmap *sb, sb_for_each_fn fn,
+					void *data)
+{
+	__sbitmap_for_each_set(sb, 0, fn, data);
+}
 

static inline unsigned long *__sbitmap_word(struct sbitmap *sb,
unsigned int bitnr)

Signature · 1 line

2.9.5

Quoted 4 lines · Ming Lei

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

Cc Omar Sandoval <[email protected]>

A couple of comments below, once you address those you can add

Reviewed-by Omar Sandoval <[email protected]>

Quoted 52 lines

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

---
 include/linux/sbitmap.h | 54 ++++++++++++++++++++++++++++++++++++-------------
 1 file changed, 40 insertions(+), 14 deletions(-)

include/linux/sbitmap.h +16 -7

index a1904aadbc45..2329b9e1a0e2 100644
@@ -211,10 +211,14 @@ bool sbitmap_any_bit_set(const struct sbitmap *sb);
  */
 bool sbitmap_any_bit_clear(const struct sbitmap *sb);
 
+#define SB_NR_TO_INDEX(sb, bitnr) ((bitnr) >> (sb)->shift)
+#define SB_NR_TO_BIT(sb, bitnr) ((bitnr) & ((1U << (sb)->shift) - 1U))
+
 typedef bool (*sb_for_each_fn)(struct sbitmap *, unsigned int, void *);
 
 /**
  * sbitmap_for_each_set() - Iterate over each set bit in a &struct sbitmap.
+ * @off: Where to start the iteration
  * @sb: Bitmap to iterate over.
  * @fn: Callback. Should return true to continue or false to break early.
  * @data: Pointer to pass to callback.

@@ -222,35 +226,57 @@ typedef bool (*sb_for_each_fn)(struct sbitmap *, unsigned int, void *);
  * This is inline even though it's non-trivial so that the function calls to the
  * callback will hopefully get optimized away.
  */
-static inline void sbitmap_for_each_set(struct sbitmap *sb, sb_for_each_fn fn,
-					void *data)
+static inline void __sbitmap_for_each_set(struct sbitmap *sb,
+					  unsigned int off,
+					  sb_for_each_fn fn, void *data)
 {
-	unsigned int i;
+	unsigned int index = SB_NR_TO_INDEX(sb, off);
+	unsigned int nr = SB_NR_TO_BIT(sb, off);
+	unsigned int scanned = 0;
 
-	for (i = 0; i < sb->map_nr; i++) {
-		struct sbitmap_word *word = &sb->map[i];
-		unsigned int off, nr;
+	while (1) {
+		struct sbitmap_word *word = &sb->map[index];
+		unsigned int depth = min_t(unsigned int, word->depth - nr,
+					   sb->depth - scanned);
 
+		scanned += depth;
 		if (!word->word)
-			continue;
+			goto next;
 

include/linux/sbitmap.h typedef bool (*sb_for_each_fn)(struct sbitmap *, unsigned int, void *); · line 246

Quoted 3 lines

include/linux/sbitmap.h +1 -2

-		nr = 0;
-		off = i << sb->shift;
+		depth += nr;

I had to think hard to convince myself this was right. If above we set depth to (sb->depth - scanned), then we must have already looped at

least once, so nr must be 0, therefore this is okay. Am I following this correctly? I think reassigning like so would be more clear:

		depth = min_t(unsigned int, word->depth, sb->depth - scanned);

Quoted 30 lines

include/linux/sbitmap.h +14 -5

+		off = index << sb->shift;
 		while (1) {
-			nr = find_next_bit(&word->word, word->depth, nr);
-			if (nr >= word->depth)
+			nr = find_next_bit(&word->word, depth, nr);
+			if (nr >= depth)
 				break;
-
 			if (!fn(sb, off + nr, data))
 				return;
 
 			nr++;
 		}
+ next:
+		if (scanned >= sb->depth)
+			break;
+		nr = 0;
+		if (++index >= sb->map_nr)
+			index = 0;
 	}
 }
 
-#define SB_NR_TO_INDEX(sb, bitnr) ((bitnr) >> (sb)->shift)
-#define SB_NR_TO_BIT(sb, bitnr) ((bitnr) & ((1U << (sb)->shift) - 1U))
+/**
+ * sbitmap_for_each_set() - Iterate over each set bit in a &struct sbitmap.
+ * @sb: Bitmap to iterate over.
+ * @fn: Callback. Should return true to continue or false to break early.
+ * @data: Pointer to pass to callback.

include/linux/sbitmap.h typedef bool (*sb_for_each_fn)(struct sbitmap *, unsigned int, void *); · line 273

Quoted 3 lines

include/linux/sbitmap.h +3 -0

+ *
+ * This is inline even though it's non-trivial so that the function calls to the
+ * callback will hopefully get optimized away.

This part of the comment doesn't make sense for this wrapper, please remove it.

Quoted 62 lines · Omar Sandoval

Quoted 4 lines · Ming Lei

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

Cc Omar Sandoval <[email protected]>

A couple of comments below, once you address those you can add

Reviewed-by Omar Sandoval <[email protected]>

Quoted 52 lines

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

---
 include/linux/sbitmap.h | 54 ++++++++++++++++++++++++++++++++++++-------------
 1 file changed, 40 insertions(+), 14 deletions(-)

include/linux/sbitmap.h +16 -7

index a1904aadbc45..2329b9e1a0e2 100644
@@ -211,10 +211,14 @@ bool sbitmap_any_bit_set(const struct sbitmap *sb);
  */
 bool sbitmap_any_bit_clear(const struct sbitmap *sb);
 
+#define SB_NR_TO_INDEX(sb, bitnr) ((bitnr) >> (sb)->shift)
+#define SB_NR_TO_BIT(sb, bitnr) ((bitnr) & ((1U << (sb)->shift) - 1U))
+
 typedef bool (*sb_for_each_fn)(struct sbitmap *, unsigned int, void *);
 
 /**
  * sbitmap_for_each_set() - Iterate over each set bit in a &struct sbitmap.
+ * @off: Where to start the iteration
  * @sb: Bitmap to iterate over.
  * @fn: Callback. Should return true to continue or false to break early.
  * @data: Pointer to pass to callback.

@@ -222,35 +226,57 @@ typedef bool (*sb_for_each_fn)(struct sbitmap *, unsigned int, void *);
  * This is inline even though it's non-trivial so that the function calls to the
  * callback will hopefully get optimized away.
  */
-static inline void sbitmap_for_each_set(struct sbitmap *sb, sb_for_each_fn fn,
-					void *data)
+static inline void __sbitmap_for_each_set(struct sbitmap *sb,
+					  unsigned int off,
+					  sb_for_each_fn fn, void *data)
 {
-	unsigned int i;
+	unsigned int index = SB_NR_TO_INDEX(sb, off);
+	unsigned int nr = SB_NR_TO_BIT(sb, off);
+	unsigned int scanned = 0;
 
-	for (i = 0; i < sb->map_nr; i++) {
-		struct sbitmap_word *word = &sb->map[i];
-		unsigned int off, nr;
+	while (1) {
+		struct sbitmap_word *word = &sb->map[index];
+		unsigned int depth = min_t(unsigned int, word->depth - nr,
+					   sb->depth - scanned);
 
+		scanned += depth;
 		if (!word->word)
-			continue;
+			goto next;
 

Quoted 6 lines

include/linux/sbitmap.h typedef bool (*sb_for_each_fn)(struct sbitmap *, unsigned int, void *); · line 246

Quoted 3 lines

include/linux/sbitmap.h +1 -2

-		nr = 0;
-		off = i << sb->shift;
+		depth += nr;

I had to think hard to convince myself this was right. If above we set depth to (sb->depth - scanned), then we must have already looped at

It should be so only in the last loop, in which the 1st half of the word is to be checked because we start from the 2nd half of the same word.

Quoted 2 lines

least once, so nr must be 0, therefore this is okay. Am I following this correctly? I think reassigning like so would be more clear:

Yes, you are right, nr can be non-zero only in the 1st loop.

Quoted 2 lines

		depth = min_t(unsigned int, word->depth, sb->depth - scanned);

If nr isn't zero, the depth to be scanned should be 'word->depth - nr' in the 1st loop, so the above way can't cover this case.

Quoted 77 lines · Ming Lei

Quoted 62 lines · Omar Sandoval

Quoted 4 lines · Ming Lei

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

Cc Omar Sandoval <[email protected]>

A couple of comments below, once you address those you can add

Reviewed-by Omar Sandoval <[email protected]>

Quoted 52 lines

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

---
 include/linux/sbitmap.h | 54 ++++++++++++++++++++++++++++++++++++-------------
 1 file changed, 40 insertions(+), 14 deletions(-)

include/linux/sbitmap.h +16 -7

index a1904aadbc45..2329b9e1a0e2 100644
@@ -211,10 +211,14 @@ bool sbitmap_any_bit_set(const struct sbitmap *sb);
  */
 bool sbitmap_any_bit_clear(const struct sbitmap *sb);
 
+#define SB_NR_TO_INDEX(sb, bitnr) ((bitnr) >> (sb)->shift)
+#define SB_NR_TO_BIT(sb, bitnr) ((bitnr) & ((1U << (sb)->shift) - 1U))
+
 typedef bool (*sb_for_each_fn)(struct sbitmap *, unsigned int, void *);
 
 /**
  * sbitmap_for_each_set() - Iterate over each set bit in a &struct sbitmap.
+ * @off: Where to start the iteration
  * @sb: Bitmap to iterate over.
  * @fn: Callback. Should return true to continue or false to break early.
  * @data: Pointer to pass to callback.

@@ -222,35 +226,57 @@ typedef bool (*sb_for_each_fn)(struct sbitmap *, unsigned int, void *);
  * This is inline even though it's non-trivial so that the function calls to the
  * callback will hopefully get optimized away.
  */
-static inline void sbitmap_for_each_set(struct sbitmap *sb, sb_for_each_fn fn,
-					void *data)
+static inline void __sbitmap_for_each_set(struct sbitmap *sb,
+					  unsigned int off,
+					  sb_for_each_fn fn, void *data)
 {
-	unsigned int i;
+	unsigned int index = SB_NR_TO_INDEX(sb, off);
+	unsigned int nr = SB_NR_TO_BIT(sb, off);
+	unsigned int scanned = 0;
 
-	for (i = 0; i < sb->map_nr; i++) {
-		struct sbitmap_word *word = &sb->map[i];
-		unsigned int off, nr;
+	while (1) {
+		struct sbitmap_word *word = &sb->map[index];
+		unsigned int depth = min_t(unsigned int, word->depth - nr,
+					   sb->depth - scanned);
 
+		scanned += depth;
 		if (!word->word)
-			continue;
+			goto next;
 

Quoted 6 lines

include/linux/sbitmap.h typedef bool (*sb_for_each_fn)(struct sbitmap *, unsigned int, void *); · line 246

Quoted 3 lines

include/linux/sbitmap.h +1 -2

-		nr = 0;
-		off = i << sb->shift;
+		depth += nr;

I had to think hard to convince myself this was right. If above we set depth to (sb->depth - scanned), then we must have already looped at

It should be so only in the last loop, in which the 1st half of the word is to be checked because we start from the 2nd half of the same word.

Quoted 2 lines

least once, so nr must be 0, therefore this is okay. Am I following this correctly? I think reassigning like so would be more clear:

Quoted 7 lines

Yes, you are right, nr can be non-zero only in the 1st loop.

Quoted 2 lines

		depth = min_t(unsigned int, word->depth, sb->depth - scanned);

If nr isn't zero, the depth to be scanned should be 'word->depth - nr' in the 1st loop, so the above way can't cover this case.

What I mean is that you keep the same initialization above, but instead of

		depth += nr
you do
		depth = min_t(unsigned int, word->depth, sb->depth - scanned);

because like I said, the reasoning about why += nr is okay in the sb->depth - scanned case is subtle.

And maybe even replace the

		scanned += depth;
with
		scanned += min_t(unsigned int, word->depth - nr,
	   			 sb->depth - scanned);

I.e., don't reuse the depth local variable for two different things. I'm nitpicking here but this code is tricky enough as it is.

For completeness, I mean this exactly:

	while (1) {
		struct sbitmap_word *word = &sb->map[index];
		unsigned int depth;

		scanned += min_t(unsigned int, word->depth - nr,
				 sb->depth - scanned);
		if (!word->word)
			goto next;

		depth = min_t(unsigned int, word->depth, sb->depth - scanned);

		off = index << sb->shift;
		while (1) {
			nr = find_next_bit(&word->word, depth, nr);
			if (nr >= depth)
				break;

			if (!fn(sb, off + nr, data))
				return;

			nr++;

		}
next:
		if (scanned >= sb->depth)
			break;
		nr = 0;
		if (++index >= sb->map_nr)
			index = 0;
	}

From dd455230fed9200d519d3ae4f4c32a1430506441 Mon Sep 17 00:00:00 2001

On Sun, Sep 10, 2017 at 10:20:27AM -0700, Omar Sandoval wrote:

Quoted 7 lines

What I mean is that you keep the same initialization above, but instead of

		depth += nr
you do
		depth = min_t(unsigned int, word->depth, sb->depth - scanned);

because like I said, the reasoning about why += nr is okay in the sb->depth - scanned case is subtle.

Quoted 7 lines

And maybe even replace the

		scanned += depth;
with
		scanned += min_t(unsigned int, word->depth - nr,
	   			 sb->depth - scanned);

I.e., don't reuse the depth local variable for two different things. I'm nitpicking here but this code is tricky enough as it is.

It wasn't reused in old version, just for saving one local variable, and one extra min_t().

Yeah, I admit it isn't clean enough.

Quoted 7 lines

For completeness, I mean this exactly:

	while (1) {
		struct sbitmap_word *word = &sb->map[index];
		unsigned int depth;

Quoted 6 lines

		scanned += min_t(unsigned int, word->depth - nr,
				 sb->depth - scanned);
		if (!word->word)
			goto next;

		depth = min_t(unsigned int, word->depth, sb->depth - scanned);

two min_t and a little code duplication.

Quoted 10 lines

		off = index << sb->shift;
		while (1) {
			nr = find_next_bit(&word->word, depth, nr);
			if (nr >= depth)
				break;

			if (!fn(sb, off + nr, data))
				return;

			nr++;

Quoted 8 lines

		}
next:
		if (scanned >= sb->depth)
			break;
		nr = 0;
		if (++index >= sb->map_nr)
			index = 0;
	}

The following patch switches to do{}while and handles the 1st scan outside of the loop, then it should be clean enough(no two min_t()), so how about this one?

Quoted 1 line · Ming Lei

On Sun, Sep 10, 2017 at 10:20:27AM -0700, Omar Sandoval wrote:

[snip]

Quoted 32 lines

Quoted 7 lines

What I mean is that you keep the same initialization above, but instead of

		depth += nr
you do
		depth = min_t(unsigned int, word->depth, sb->depth - scanned);

because like I said, the reasoning about why += nr is okay in the sb->depth - scanned case is subtle.

Quoted 7 lines

And maybe even replace the

		scanned += depth;
with
		scanned += min_t(unsigned int, word->depth - nr,
	   			 sb->depth - scanned);

I.e., don't reuse the depth local variable for two different things. I'm nitpicking here but this code is tricky enough as it is.

It wasn't reused in old version, just for saving one local variable, and one extra min_t().

Yeah, I admit it isn't clean enough.

Quoted 12 lines

For completeness, I mean this exactly:

	while (1) {
		struct sbitmap_word *word = &sb->map[index];
		unsigned int depth;

		scanned += min_t(unsigned int, word->depth - nr,
				 sb->depth - scanned);
		if (!word->word)
			goto next;

Quoted 3 lines

Quoted 1 line

		depth = min_t(unsigned int, word->depth, sb->depth - scanned);

two min_t and a little code duplication.

They're similar but they represent different things, so I think trying to deduplicate this code just makes it more confusing. If performance is your concern, I'd be really surprised if there's a noticable difference.

As a side note, I also realized that this code doesn't handle the sb->depth == 0 case. We should change the while (1) to while (scanned < sb->depth) and remove the
if (scanned >= sb->depth) break;

Quoted 20 lines

Quoted 19 lines

		off = index << sb->shift;
		while (1) {
			nr = find_next_bit(&word->word, depth, nr);
			if (nr >= depth)
				break;

			if (!fn(sb, off + nr, data))
				return;

			nr++;
		}
next:
		if (scanned >= sb->depth)
			break;
		nr = 0;
		if (++index >= sb->map_nr)
			index = 0;
	}

Quoted 3 lines

The following patch switches to do{}while and handles the 1st scan outside of the loop, then it should be clean enough(no two min_t()), so how about this one?

I find this one subtler and harder to follow. The less it looks like the typical loop pattern, the longer someone reading the code has to reason about it.

Quoted 37 lines · Omar Sandoval

Quoted 1 line · Ming Lei

On Sun, Sep 10, 2017 at 10:20:27AM -0700, Omar Sandoval wrote:

[snip]

Quoted 32 lines

Quoted 7 lines

What I mean is that you keep the same initialization above, but instead of

		depth += nr
you do
		depth = min_t(unsigned int, word->depth, sb->depth - scanned);

because like I said, the reasoning about why += nr is okay in the sb->depth - scanned case is subtle.

Quoted 7 lines

And maybe even replace the

		scanned += depth;
with
		scanned += min_t(unsigned int, word->depth - nr,
	   			 sb->depth - scanned);

I.e., don't reuse the depth local variable for two different things. I'm nitpicking here but this code is tricky enough as it is.

It wasn't reused in old version, just for saving one local variable, and one extra min_t().

Yeah, I admit it isn't clean enough.

Quoted 12 lines

For completeness, I mean this exactly:

	while (1) {
		struct sbitmap_word *word = &sb->map[index];
		unsigned int depth;

		scanned += min_t(unsigned int, word->depth - nr,
				 sb->depth - scanned);
		if (!word->word)
			goto next;

Quoted 7 lines

Quoted 3 lines

Quoted 1 line

		depth = min_t(unsigned int, word->depth, sb->depth - scanned);

two min_t and a little code duplication.

They're similar but they represent different things, so I think trying to deduplicate this code just makes it more confusing. If performance is your concern, I'd be really surprised if there's a noticable difference.

No only one extra min_t(), also it isn't easy to read the code, since only in the first scan that 'depth' isn't same with 'depth', that is why I set the 1st 'scan' outside of the loop, then we can update 'scan' with 'depth' in every loop. People will be easy to follow the meaning.

Quoted 5 lines

As a side note, I also realized that this code doesn't handle the sb->depth == 0 case. We should change the while (1) to while (scanned < sb->depth) and remove the
if (scanned >= sb->depth) break;

In the attached patch, I remember that the zero depth case is addressed by:

	if (start >= sb->depth)
		return;

which is required since 'start' parameter is introduced in this patch.

Quoted 24 lines

Quoted 23 lines

Quoted 11 lines

		off = index << sb->shift;
		while (1) {
			nr = find_next_bit(&word->word, depth, nr);
			if (nr >= depth)
				break;

			if (!fn(sb, off + nr, data))
				return;

			nr++;

Quoted 8 lines

		}
next:
		if (scanned >= sb->depth)
			break;
		nr = 0;
		if (++index >= sb->map_nr)
			index = 0;
	}

The following patch switches to do{}while and handles the 1st scan outside of the loop, then it should be clean enough(no two min_t()), so how about this one?

Quoted 3 lines

I find this one subtler and harder to follow. The less it looks like the typical loop pattern, the longer someone reading the code has to reason about it.

Looks using 'depth' to update 'scanned' is easier to follow, than two min_t(), since it will make people easy to understand the relation between the two, then understand the whole code.

Honestly I prefer your original patch with a comment on depth += nr. I'd be happy with the following incremental patch on top of your original v4 patch.

include/linux/sbitmap.h +15 -10

index 2329b9e1a0e2..8d747048ae4f 100644
@@ -218,7 +218,7 @@ typedef bool (*sb_for_each_fn)(struct sbitmap *, unsigned int, void *);
 
 /**
  * sbitmap_for_each_set() - Iterate over each set bit in a &struct sbitmap.
- * @off: Where to start the iteration
+ * @off: Where to start the iteration.
  * @sb: Bitmap to iterate over.
  * @fn: Callback. Should return true to continue or false to break early.
  * @data: Pointer to pass to callback.

@@ -230,11 +230,16 @@ static inline void __sbitmap_for_each_set(struct sbitmap *sb,
 					  unsigned int off,
 					  sb_for_each_fn fn, void *data)
 {
-	unsigned int index = SB_NR_TO_INDEX(sb, off);
-	unsigned int nr = SB_NR_TO_BIT(sb, off);
+	unsigned int index;
+	unsigned int nr;
 	unsigned int scanned = 0;
 
-	while (1) {
+	if (off >= sb->depth)
+		off = 0;
+	index = SB_NR_TO_INDEX(sb, off);
+	nr = SB_NR_TO_BIT(sb, off);
+
+	while (scanned < sb->depth) {
 		struct sbitmap_word *word = &sb->map[index];
 		unsigned int depth = min_t(unsigned int, word->depth - nr,
 					   sb->depth - scanned);

@@ -243,6 +248,11 @@ static inline void __sbitmap_for_each_set(struct sbitmap *sb,
 		if (!word->word)
 			goto next;
 
+		/*
+		 * On the first iteration of the outer loop, we need to add the
+		 * bit offset back to the size of the word for find_next_bit().
+		 * On all other iterations, nr is zero, so this is a noop.
+		 */
 		depth += nr;
 		off = index << sb->shift;
 		while (1) {

@@ -254,9 +264,7 @@ static inline void __sbitmap_for_each_set(struct sbitmap *sb,
 
 			nr++;
 		}
- next:
-		if (scanned >= sb->depth)
-			break;
+next:
 		nr = 0;
 		if (++index >= sb->map_nr)
 			index = 0;

@@ -268,9 +276,6 @@ static inline void __sbitmap_for_each_set(struct sbitmap *sb,
  * @sb: Bitmap to iterate over.
  * @fn: Callback. Should return true to continue or false to break early.
  * @data: Pointer to pass to callback.
- *
- * This is inline even though it's non-trivial so that the function calls to the
- * callback will hopefully get optimized away.
  */
 static inline void sbitmap_for_each_set(struct sbitmap *sb, sb_for_each_fn fn,
 					void *data)

Quoted 58 lines · Ming Lei

Quoted 37 lines · Omar Sandoval

Quoted 1 line · Ming Lei

On Sun, Sep 10, 2017 at 10:20:27AM -0700, Omar Sandoval wrote:

[snip]

Quoted 32 lines

Quoted 7 lines

What I mean is that you keep the same initialization above, but instead of

		depth += nr
you do
		depth = min_t(unsigned int, word->depth, sb->depth - scanned);

because like I said, the reasoning about why += nr is okay in the sb->depth - scanned case is subtle.

Quoted 7 lines

And maybe even replace the

		scanned += depth;
with
		scanned += min_t(unsigned int, word->depth - nr,
	   			 sb->depth - scanned);

I.e., don't reuse the depth local variable for two different things. I'm nitpicking here but this code is tricky enough as it is.

It wasn't reused in old version, just for saving one local variable, and one extra min_t().

Yeah, I admit it isn't clean enough.

Quoted 12 lines

For completeness, I mean this exactly:

	while (1) {
		struct sbitmap_word *word = &sb->map[index];
		unsigned int depth;

		scanned += min_t(unsigned int, word->depth - nr,
				 sb->depth - scanned);
		if (!word->word)
			goto next;

Quoted 7 lines

Quoted 3 lines

Quoted 1 line

		depth = min_t(unsigned int, word->depth, sb->depth - scanned);

two min_t and a little code duplication.

They're similar but they represent different things, so I think trying to deduplicate this code just makes it more confusing. If performance is your concern, I'd be really surprised if there's a noticable difference.

No only one extra min_t(), also it isn't easy to read the code, since only in the first scan that 'depth' isn't same with 'depth', that is why I set the 1st 'scan' outside of the loop, then we can update 'scan' with 'depth' in every loop. People will be easy to follow the meaning.

Quoted 5 lines

As a side note, I also realized that this code doesn't handle the sb->depth == 0 case. We should change the while (1) to while (scanned < sb->depth) and remove the
if (scanned >= sb->depth) break;

Quoted 8 lines

In the attached patch, I remember that the zero depth case is addressed by:

	if (start >= sb->depth)
		return;

which is required since 'start' parameter is introduced in this patch.

I think the better way to handle this is

if (start >= sb->depth)

	start = 0;

Since the sbitmap may have gotten resized since the last time the user called this and cached their start value.

Quoted 29 lines

Quoted 28 lines

Quoted 21 lines

Quoted 12 lines

		off = index << sb->shift;
		while (1) {
			nr = find_next_bit(&word->word, depth, nr);
			if (nr >= depth)
				break;

			if (!fn(sb, off + nr, data))
				return;

			nr++;

Quoted 8 lines

		}
next:
		if (scanned >= sb->depth)
			break;
		nr = 0;
		if (++index >= sb->map_nr)
			index = 0;
	}

Quoted 3 lines

The following patch switches to do{}while and handles the 1st scan outside of the loop, then it should be clean enough(no two min_t()), so how about this one?

I find this one subtler and harder to follow. The less it looks like the typical loop pattern, the longer someone reading the code has to reason about it.

Quoted 3 lines

Looks using 'depth' to update 'scanned' is easier to follow, than two min_t(), since it will make people easy to understand the relation between the two, then understand the whole code.

Honestly I prefer your original patch with a comment on depth += nr. I'd be happy with the following incremental patch on top of your original v4 patch.

This function is introduced for dequeuing request from sw queue so that we can dispatch it in scheduler's way.

More importantly, some SCSI devices may set q->queue_depth, which is a per-request_queue limit, and applied on pending I/O from all hctxs. This function is introduced for avoiding to dequeue too many requests from sw queue when ->dispatch isn't flushed completely.

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

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

---
 block/blk-mq.c | 38 ++++++++++++++++++++++++++++++++++++++
 block/blk-mq.h |  2 ++
 2 files changed, 40 insertions(+)

block/blk-mq.c +38 -0

index 3f18cff80050..f063dd0f197f 100644
@@ -880,6 +880,44 @@ 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_dispatch_rq_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 98252b79b80b..e42748bfb959 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_dispatch_rq_from_ctx(struct blk_mq_hw_ctx *hctx,
+					    struct blk_mq_ctx *start);
 
 /*
  * Internal helpers for allocating/freeing the request map

Signature · 1 line

2.9.5

Quoted 10 lines · Ming Lei

This function is introduced for dequeuing request from sw queue so that we can dispatch it in scheduler's way.

More importantly, some SCSI devices may set q->queue_depth, which is a per-request_queue limit, and applied on pending I/O from all hctxs. This function is introduced for avoiding to dequeue too many requests from sw queue when ->dispatch isn't flushed completely.

blk_mq_dispatch_rq_from_ctx() doesn't actually dispatch the request. Can you please rename it blk_mq_dequeue_from_ctx() or something like that? (Same for the dispatch_rq_from_ctx helper.)

So that it becomes easy to support to dispatch from sw queue in the following patch.

No functional change.

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

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

---
 block/blk-mq-sched.c | 28 ++++++++++++++++++----------
 1 file changed, 18 insertions(+), 10 deletions(-)

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

index 845e5baf8af1..f69752961a34 100644

block/blk-mq-sched.c +15 -10

+{
+	LIST_HEAD(rq_list);
+
+	do {
+		struct request *rq;
+
+		rq = e->type->ops.mq.dispatch_request(hctx);
+		if (!rq)
+			break;
+		list_add(&rq->queuelist, &rq_list);
+	} while (blk_mq_dispatch_rq_list(q, &rq_list));
+}
+
 void blk_mq_sched_dispatch_requests(struct blk_mq_hw_ctx *hctx)
 {
 	struct request_queue *q = hctx->queue;

@@ -136,16 +152,8 @@ void blk_mq_sched_dispatch_requests(struct blk_mq_hw_ctx *hctx)
 	 * on the dispatch list, OR if we did have work but weren't able
 	 * to make progress.
 	 */
-	if (do_sched_dispatch && has_sched_dispatch) {
-		do {
-			struct request *rq;
-
-			rq = e->type->ops.mq.dispatch_request(hctx);
-			if (!rq)
-				break;
-			list_add(&rq->queuelist, &rq_list);
-		} while (blk_mq_dispatch_rq_list(q, &rq_list));
-	}
+	if (do_sched_dispatch && has_sched_dispatch)
+		blk_mq_do_dispatch(q, e, hctx);
 }
 
 bool blk_mq_sched_try_merge(struct request_queue *q, struct bio *bio,

Signature · 1 line

2.9.5

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.

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 per-lun queue depth. 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 hurted.

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 Bart Van Assche <[email protected]>

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

---
 block/blk-mq-sched.c   | 61 +++++++++++++++++++++++++++++++++++++++++++++-----
 include/linux/blk-mq.h |  2 ++
 2 files changed, 57 insertions(+), 6 deletions(-)

block/blk-mq-sched.c +21 -3

index f69752961a34..735e432294ab 100644
@@ -89,9 +89,9 @@ static bool blk_mq_sched_restart_hctx(struct blk_mq_hw_ctx *hctx)
 	return false;
 }
 
-static void blk_mq_do_dispatch(struct request_queue *q,
-			       struct elevator_queue *e,
-			       struct blk_mq_hw_ctx *hctx)
+static void blk_mq_do_dispatch_sched(struct request_queue *q,
+				     struct elevator_queue *e,
+				     struct blk_mq_hw_ctx *hctx)
 {
 	LIST_HEAD(rq_list);
 

@@ -105,6 +105,42 @@ static void blk_mq_do_dispatch(struct request_queue *q,
 	} 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 request_queue *q,
+				   struct blk_mq_hw_ctx *hctx)
+{
+	LIST_HEAD(rq_list);
+	struct blk_mq_ctx *ctx = READ_ONCE(hctx->dispatch_from);
+	bool dispatched;
+

block/blk-mq-sched.c +23 -3

+		dispatched = blk_mq_dispatch_rq_list(q, &rq_list);
+	} while (dispatched);
+
+	if (!dispatched)
+		WRITE_ONCE(hctx->dispatch_from, blk_mq_next_ctx(hctx, ctx));
+}
+
 void blk_mq_sched_dispatch_requests(struct blk_mq_hw_ctx *hctx)
 {
 	struct request_queue *q = hctx->queue;

@@ -142,18 +178,31 @@ void blk_mq_sched_dispatch_requests(struct blk_mq_hw_ctx *hctx)
 	if (!list_empty(&rq_list)) {
 		blk_mq_sched_mark_restart_hctx(hctx);
 		do_sched_dispatch = blk_mq_dispatch_rq_list(q, &rq_list);
-	} else if (!has_sched_dispatch) {
+	} else if (!has_sched_dispatch && !q->queue_depth) {
+		/*
+		 * If there is no per-request_queue depth, we
+		 * flush all requests in this hw queue, otherwise
+		 * pick up request one by one from sw queue for
+		 * avoiding to mess up I/O merge when dispatch
+		 * is busy, which can be triggered easily by
+		 * per-request_queue queue depth
+		 */
 		blk_mq_flush_busy_ctxs(hctx, &rq_list);
 		blk_mq_dispatch_rq_list(q, &rq_list);
 	}
 
+	if (!do_sched_dispatch)
+		return;
+
 	/*
 	 * 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.
 	 */
-	if (do_sched_dispatch && has_sched_dispatch)
-		blk_mq_do_dispatch(q, e, hctx);
+	if (has_sched_dispatch)
+		blk_mq_do_dispatch_sched(q, e, hctx);
+	else
+		blk_mq_do_dispatch_ctx(q, hctx);
 }
 
 bool blk_mq_sched_try_merge(struct request_queue *q, struct bio *bio,

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 72 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.

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 per-lun queue depth. 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 hurted.

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 Bart Van Assche <[email protected]>

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

---
 block/blk-mq-sched.c   | 61 +++++++++++++++++++++++++++++++++++++++++++++-----
 include/linux/blk-mq.h |  2 ++
 2 files changed, 57 insertions(+), 6 deletions(-)

block/blk-mq-sched.c +28 -3

index f69752961a34..735e432294ab 100644
@@ -89,9 +89,9 @@ static bool blk_mq_sched_restart_hctx(struct blk_mq_hw_ctx *hctx)
 	return false;
 }
 
-static void blk_mq_do_dispatch(struct request_queue *q,
-			       struct elevator_queue *e,
-			       struct blk_mq_hw_ctx *hctx)
+static void blk_mq_do_dispatch_sched(struct request_queue *q,
+				     struct elevator_queue *e,
+				     struct blk_mq_hw_ctx *hctx)
 {
 	LIST_HEAD(rq_list);
 

@@ -105,6 +105,42 @@ static void blk_mq_do_dispatch(struct request_queue *q,
 	} 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 request_queue *q,
+				   struct blk_mq_hw_ctx *hctx)
+{
+	LIST_HEAD(rq_list);
+	struct blk_mq_ctx *ctx = READ_ONCE(hctx->dispatch_from);
+	bool dispatched;
+
+	do {
+		struct request *rq;
+
+		rq = blk_mq_dispatch_rq_from_ctx(hctx, ctx);
+		if (!rq)
+			break;
+		list_add(&rq->queuelist, &rq_list);

block/blk-mq-sched.c static void blk_mq_do_dispatch(struct request_queue *q, · line 135

Quoted 3 lines

block/blk-mq-sched.c +3 -0

+
+		/* round robin for fair dispatch */
+		ctx = blk_mq_next_ctx(hctx, rq->mq_ctx);

Hm... this next ctx will get skipped if the dispatch on the previous ctx fails, since we call blk_mq_next_ctx() again. Seems unfair. Maybe move the blk_mq_next_ctx() from the if (!dispatched) below into the if (!rq) above?

Quoted 73 lines · Omar Sandoval

Quoted 72 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.

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 per-lun queue depth. 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 hurted.

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 Bart Van Assche <[email protected]>

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

---
 block/blk-mq-sched.c   | 61 +++++++++++++++++++++++++++++++++++++++++++++-----
 include/linux/blk-mq.h |  2 ++
 2 files changed, 57 insertions(+), 6 deletions(-)

block/blk-mq-sched.c +28 -3

index f69752961a34..735e432294ab 100644
@@ -89,9 +89,9 @@ static bool blk_mq_sched_restart_hctx(struct blk_mq_hw_ctx *hctx)
 	return false;
 }
 
-static void blk_mq_do_dispatch(struct request_queue *q,
-			       struct elevator_queue *e,
-			       struct blk_mq_hw_ctx *hctx)
+static void blk_mq_do_dispatch_sched(struct request_queue *q,
+				     struct elevator_queue *e,
+				     struct blk_mq_hw_ctx *hctx)
 {
 	LIST_HEAD(rq_list);
 

@@ -105,6 +105,42 @@ static void blk_mq_do_dispatch(struct request_queue *q,
 	} 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 request_queue *q,
+				   struct blk_mq_hw_ctx *hctx)
+{
+	LIST_HEAD(rq_list);
+	struct blk_mq_ctx *ctx = READ_ONCE(hctx->dispatch_from);
+	bool dispatched;
+
+	do {
+		struct request *rq;
+
+		rq = blk_mq_dispatch_rq_from_ctx(hctx, ctx);
+		if (!rq)
+			break;
+		list_add(&rq->queuelist, &rq_list);

Quoted 8 lines

block/blk-mq-sched.c static void blk_mq_do_dispatch(struct request_queue *q, · line 135

Quoted 3 lines

block/blk-mq-sched.c +3 -0

+
+		/* round robin for fair dispatch */
+		ctx = blk_mq_next_ctx(hctx, rq->mq_ctx);

Hm... this next ctx will get skipped if the dispatch on the previous ctx fails, since we call blk_mq_next_ctx() again. Seems unfair. Maybe move the blk_mq_next_ctx() from the if (!dispatched) below into the if (!rq) above?

In case of if (!rq), that means there isn't any request in all ctxs belonging to this hctx, so it is reasonable to start the dispatch from any one of these ctxs next time, include the next one.

If dispatch fails on previous ctx, the rq from that ctx will be put into ->dispatch, so it is fair to start dispatch from next ctx next time too.

Quoted 83 lines · Ming Lei

Quoted 73 lines · Omar Sandoval

Quoted 72 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.

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 per-lun queue depth. 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 hurted.

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 Bart Van Assche <[email protected]>

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

---
 block/blk-mq-sched.c   | 61 +++++++++++++++++++++++++++++++++++++++++++++-----
 include/linux/blk-mq.h |  2 ++
 2 files changed, 57 insertions(+), 6 deletions(-)

block/blk-mq-sched.c +28 -3

index f69752961a34..735e432294ab 100644
@@ -89,9 +89,9 @@ static bool blk_mq_sched_restart_hctx(struct blk_mq_hw_ctx *hctx)
 	return false;
 }
 
-static void blk_mq_do_dispatch(struct request_queue *q,
-			       struct elevator_queue *e,
-			       struct blk_mq_hw_ctx *hctx)
+static void blk_mq_do_dispatch_sched(struct request_queue *q,
+				     struct elevator_queue *e,
+				     struct blk_mq_hw_ctx *hctx)
 {
 	LIST_HEAD(rq_list);
 

@@ -105,6 +105,42 @@ static void blk_mq_do_dispatch(struct request_queue *q,
 	} 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 request_queue *q,
+				   struct blk_mq_hw_ctx *hctx)
+{
+	LIST_HEAD(rq_list);
+	struct blk_mq_ctx *ctx = READ_ONCE(hctx->dispatch_from);
+	bool dispatched;
+
+	do {
+		struct request *rq;
+
+		rq = blk_mq_dispatch_rq_from_ctx(hctx, ctx);
+		if (!rq)
+			break;
+		list_add(&rq->queuelist, &rq_list);

Quoted 8 lines

block/blk-mq-sched.c static void blk_mq_do_dispatch(struct request_queue *q, · line 135

Quoted 3 lines

block/blk-mq-sched.c +3 -0

+
+		/* round robin for fair dispatch */
+		ctx = blk_mq_next_ctx(hctx, rq->mq_ctx);

Hm... this next ctx will get skipped if the dispatch on the previous ctx fails, since we call blk_mq_next_ctx() again. Seems unfair. Maybe move the blk_mq_next_ctx() from the if (!dispatched) below into the if (!rq) above?

Quoted 3 lines

In case of if (!rq), that means there isn't any request in all ctxs belonging to this hctx, so it is reasonable to start the dispatch from any one of these ctxs next time, include the next one.

Yep, that case is okay.

Quoted 3 lines

If dispatch fails on previous ctx, the rq from that ctx will be put into ->dispatch, so it is fair to start dispatch from next ctx next time too.

I'm talking about this case

	LIST_HEAD(rq_list);
	struct blk_mq_ctx *ctx = READ_ONCE(hctx->dispatch_from);
	bool dispatched;
 
	/*
	 * Let's say that ctxs 0, 1, and 2 all have requests pending and
	 * hctx->dispatch_from was ctx0, so ctx is ctx0 when we start.
	 */
	do {
		struct request *rq;
 
		rq = blk_mq_dispatch_rq_from_ctx(hctx, ctx);
		if (!rq)
			break;
		list_add(&rq->queuelist, &rq_list);

		/* Now rq is a request from ctx0 */

		/* round robin for fair dispatch */
		ctx = blk_mq_next_ctx(hctx, rq->mq_ctx);
		/* Now ctx is ctx1. */
 
		dispatched = blk_mq_dispatch_rq_list(q, &rq_list);

		/* If we couldn't dispatch, we break here. */

	} while (dispatched);
 
	if (!dispatched)
		/*
		 * Now we set hctx->dispatch_from to ctx2, so we've
		 * skipped over ctx1.
		 */
		WRITE_ONCE(hctx->dispatch_from, blk_mq_next_ctx(hctx, ctx));

Quoted 121 lines · Omar Sandoval

Quoted 83 lines · Ming Lei

Quoted 73 lines · Omar Sandoval

Quoted 72 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.

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 per-lun queue depth. 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 hurted.

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 Bart Van Assche <[email protected]>

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

---
 block/blk-mq-sched.c   | 61 +++++++++++++++++++++++++++++++++++++++++++++-----
 include/linux/blk-mq.h |  2 ++
 2 files changed, 57 insertions(+), 6 deletions(-)

block/blk-mq-sched.c +28 -3

index f69752961a34..735e432294ab 100644
@@ -89,9 +89,9 @@ static bool blk_mq_sched_restart_hctx(struct blk_mq_hw_ctx *hctx)
 	return false;
 }
 
-static void blk_mq_do_dispatch(struct request_queue *q,
-			       struct elevator_queue *e,
-			       struct blk_mq_hw_ctx *hctx)
+static void blk_mq_do_dispatch_sched(struct request_queue *q,
+				     struct elevator_queue *e,
+				     struct blk_mq_hw_ctx *hctx)
 {
 	LIST_HEAD(rq_list);
 

@@ -105,6 +105,42 @@ static void blk_mq_do_dispatch(struct request_queue *q,
 	} 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 request_queue *q,
+				   struct blk_mq_hw_ctx *hctx)
+{
+	LIST_HEAD(rq_list);
+	struct blk_mq_ctx *ctx = READ_ONCE(hctx->dispatch_from);
+	bool dispatched;
+
+	do {
+		struct request *rq;
+
+		rq = blk_mq_dispatch_rq_from_ctx(hctx, ctx);
+		if (!rq)
+			break;
+		list_add(&rq->queuelist, &rq_list);

Quoted 8 lines

block/blk-mq-sched.c static void blk_mq_do_dispatch(struct request_queue *q, · line 135

Quoted 3 lines

block/blk-mq-sched.c +3 -0

+
+		/* round robin for fair dispatch */
+		ctx = blk_mq_next_ctx(hctx, rq->mq_ctx);

Hm... this next ctx will get skipped if the dispatch on the previous ctx fails, since we call blk_mq_next_ctx() again. Seems unfair. Maybe move the blk_mq_next_ctx() from the if (!dispatched) below into the if (!rq) above?

Quoted 3 lines

In case of if (!rq), that means there isn't any request in all ctxs belonging to this hctx, so it is reasonable to start the dispatch from any one of these ctxs next time, include the next one.

Yep, that case is okay.

Quoted 3 lines

If dispatch fails on previous ctx, the rq from that ctx will be put into ->dispatch, so it is fair to start dispatch from next ctx next time too.

I'm talking about this case

	LIST_HEAD(rq_list);
	struct blk_mq_ctx *ctx = READ_ONCE(hctx->dispatch_from);
	bool dispatched;
 
	/*
	 * Let's say that ctxs 0, 1, and 2 all have requests pending and
	 * hctx->dispatch_from was ctx0, so ctx is ctx0 when we start.
	 */
	do {
		struct request *rq;
 
		rq = blk_mq_dispatch_rq_from_ctx(hctx, ctx);
		if (!rq)
			break;
		list_add(&rq->queuelist, &rq_list);

		/* Now rq is a request from ctx0 */

		/* round robin for fair dispatch */
		ctx = blk_mq_next_ctx(hctx, rq->mq_ctx);
		/* Now ctx is ctx1. */
 
		dispatched = blk_mq_dispatch_rq_list(q, &rq_list);

		/* If we couldn't dispatch, we break here. */

Quoted 8 lines

	} while (dispatched);
 
	if (!dispatched)
		/*
		 * Now we set hctx->dispatch_from to ctx2, so we've
		 * skipped over ctx1.
		 */
		WRITE_ONCE(hctx->dispatch_from, blk_mq_next_ctx(hctx, ctx));

Good catch, looks it can be fixed by simply changing the above line into following:

WRITE_ONCE(hctx->dispatch_from, ctx);

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

@@ -142,18 +178,31 @@ void blk_mq_sched_dispatch_requests(struct blk_mq_hw_ctx *hctx)
 	if (!list_empty(&rq_list)) {
 		blk_mq_sched_mark_restart_hctx(hctx);
 		do_sched_dispatch = blk_mq_dispatch_rq_list(q, &rq_list);
-	} else if (!has_sched_dispatch) {
+	} else if (!has_sched_dispatch && !q->queue_depth) {
+		/*

Quoted 11 lines · Ming Lei

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

@@ -142,18 +178,31 @@ void blk_mq_sched_dispatch_requests(struct blk_mq_hw_ctx *hctx)
 	if (!list_empty(&rq_list)) {
 		blk_mq_sched_mark_restart_hctx(hctx);
 		do_sched_dispatch = blk_mq_dispatch_rq_list(q, &rq_list);
-	} else if (!has_sched_dispatch) {
+	} else if (!has_sched_dispatch && !q->queue_depth) {
+		/*
+		 * If there is no per-request_queue depth, we
+		 * flush all requests in this hw queue, otherwise
+		 * pick up request one by one from sw queue for
+		 * avoiding to mess up I/O merge when dispatch

block/blk-mq-sched.c void blk_mq_sched_dispatch_requests(struct blk_mq_hw_ctx *hctx) · line 192

Quoted 6 lines

block/blk-mq-sched.c +3 -0

+		 * is busy, which can be triggered easily by
+		 * per-request_queue queue depth
+		 */
 		blk_mq_flush_busy_ctxs(hctx, &rq_list);
 		blk_mq_dispatch_rq_list(q, &rq_list);
 	}

I don't like this part at all. It's a heuristic, and on top of that,

it's a heuristic based on a weak assumption that if q->queue_depth == 0,

then we never run into BUSY constraints. I think that would be stronger if it was based on "is this using shared tags", but even that is not

great at all. It's perfectly possible to have a shared tags setup and never run into resource constraints. The opposite condition is also true

- you can run without shared tags, and yet hit resource constraints constantly. Hence this is NOT a good test for deciding whether to flush everything at once or not. In short, I think a much better test case would be "has this device ever returned BLK_STS_RESOURCE. As it so happens, that's easy enough to keep track of and base this test on.

Additionally, this further differentiates dispatch cases. I'd much rather just have one sane dispatch case. I realize we are balancing between performance/scalability and practical cases like merging here, but it should not be impossible to do.

Quoted 7 lines · Ming Lei

(quoted diff) +2 -1

@@ -142,18 +178,31 @@ void blk_mq_sched_dispatch_requests(struct blk_mq_hw_ctx *hctx)
 	if (!list_empty(&rq_list)) {
 		blk_mq_sched_mark_restart_hctx(hctx);
 		do_sched_dispatch = blk_mq_dispatch_rq_list(q, &rq_list);
-	} else if (!has_sched_dispatch) {
+	} else if (!has_sched_dispatch && !q->queue_depth) {
+		/*

Review void blk_mq_sched_dispatch_requests(struct blk_mq_hw_ctx *hctx) · line 192

Quoted 10 lines

(quoted diff) +7 -0

+		 * If there is no per-request_queue depth, we
+		 * flush all requests in this hw queue, otherwise
+		 * pick up request one by one from sw queue for
+		 * avoiding to mess up I/O merge when dispatch
+		 * is busy, which can be triggered easily by
+		 * per-request_queue queue depth
+		 */
 		blk_mq_flush_busy_ctxs(hctx, &rq_list);
 		blk_mq_dispatch_rq_list(q, &rq_list);
 	}

I don't like this part at all. It's a heuristic, and on top of that, it's a heuristic based on a weak assumption that if q->queue_depth == 0, then we never run into BUSY constraints. I think that would be stronger

if it was based on "is this using shared tags", but even that is not great at all. It's perfectly possible to have a shared tags setup and never run into resource constraints. The opposite condition is also true
- you can run without shared tags, and yet hit resource constraints constantly. Hence this is NOT a good test for deciding whether to flush everything at once or not. In short, I think a much better test case would be "has this device ever returned BLK_STS_RESOURCE. As it so happens, that's easy enough to keep track of and base this test on.

Quoted 22 lines · Jens Axboe

Quoted 7 lines · Ming Lei

(quoted diff) +2 -1

@@ -142,18 +178,31 @@ void blk_mq_sched_dispatch_requests(struct blk_mq_hw_ctx *hctx)
 	if (!list_empty(&rq_list)) {
 		blk_mq_sched_mark_restart_hctx(hctx);
 		do_sched_dispatch = blk_mq_dispatch_rq_list(q, &rq_list);
-	} else if (!has_sched_dispatch) {
+	} else if (!has_sched_dispatch && !q->queue_depth) {
+		/*

Review void blk_mq_sched_dispatch_requests(struct blk_mq_hw_ctx *hctx) · line 192

Quoted 10 lines

(quoted diff) +7 -0

+		 * If there is no per-request_queue depth, we
+		 * flush all requests in this hw queue, otherwise
+		 * pick up request one by one from sw queue for
+		 * avoiding to mess up I/O merge when dispatch
+		 * is busy, which can be triggered easily by
+		 * per-request_queue queue depth
+		 */
 		blk_mq_flush_busy_ctxs(hctx, &rq_list);
 		blk_mq_dispatch_rq_list(q, &rq_list);
 	}

I don't like this part at all. It's a heuristic, and on top of that, it's a heuristic based on a weak assumption that if q->queue_depth == 0, then we never run into BUSY constraints. I think that would be stronger

Quoted 8 lines

if it was based on "is this using shared tags", but even that is not great at all. It's perfectly possible to have a shared tags setup and never run into resource constraints. The opposite condition is also true
- you can run without shared tags, and yet hit resource constraints constantly. Hence this is NOT a good test for deciding whether to flush everything at once or not. In short, I think a much better test case would be "has this device ever returned BLK_STS_RESOURCE. As it so happens, that's easy enough to keep track of and base this test on.

Hi Jens,

The attached patch follows your suggestion, and uses EWMA to compute the average length of hctx->dispatch, then only flush all requests from ctxs if the average length is zero, what do you think about this approach? Or other suggestions?

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]>

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

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

block/blk-mq-debugfs.c +1 -0

index 980e73095643..7a27f262c96a 100644
@@ -182,6 +182,7 @@ static const char *const hctx_state_name[] = {
 	HCTX_STATE_NAME(SCHED_RESTART),
 	HCTX_STATE_NAME(TAG_WAITING),
 	HCTX_STATE_NAME(START_ON_RUN),
+	HCTX_STATE_NAME(DISPATCH_BUSY),
 };
 #undef HCTX_STATE_NAME
 

block/blk-mq-sched.c +41 -17

index 735e432294ab..97e7a4fe3a32 100644
@@ -146,7 +146,6 @@ 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 do_sched_dispatch = true;
 	LIST_HEAD(rq_list);
 
 	/* RCU or SRCU read lock is needed before checking quiesced flag */

@@ -177,8 +176,33 @@ void blk_mq_sched_dispatch_requests(struct blk_mq_hw_ctx *hctx)
 	 */
 	if (!list_empty(&rq_list)) {
 		blk_mq_sched_mark_restart_hctx(hctx);
-		do_sched_dispatch = blk_mq_dispatch_rq_list(q, &rq_list);
-	} else if (!has_sched_dispatch && !q->queue_depth) {
+		blk_mq_dispatch_rq_list(q, &rq_list);
+
+		/*
+		 * We may clear DISPATCH_BUSY just after it
+		 * is set from another context, the only cost
+		 * is that one request is dequeued a bit early,
+		 * we can survive that. Given the window is
+		 * small enough, no need to worry about performance
+		 * effect.
+		 */
+		if (list_empty_careful(&hctx->dispatch))
+			clear_bit(BLK_MQ_S_DISPATCH_BUSY, &hctx->state);
+	}
+
+	/*
+	 * If DISPATCH_BUSY is set, that means hw queue is busy
+	 * and requests in the list of hctx->dispatch need to
+	 * be flushed first, so return early.
+	 *
+	 * Wherever DISPATCH_BUSY is set, blk_mq_run_hw_queue()
+	 * will be run to try to make progress, so it is always
+	 * safe to check the state here.
+	 */
+	if (test_bit(BLK_MQ_S_DISPATCH_BUSY, &hctx->state))
+		return;
+
+	if (!has_sched_dispatch) {
 		/*
 		 * If there is no per-request_queue depth, we
 		 * flush all requests in this hw queue, otherwise

@@ -187,22 +211,21 @@ void blk_mq_sched_dispatch_requests(struct blk_mq_hw_ctx *hctx)
 		 * is busy, which can be triggered easily by
 		 * per-request_queue queue depth
 		 */
-		blk_mq_flush_busy_ctxs(hctx, &rq_list);
-		blk_mq_dispatch_rq_list(q, &rq_list);
-	}
-
-	if (!do_sched_dispatch)
-		return;
+		if (!q->queue_depth) {
+			blk_mq_flush_busy_ctxs(hctx, &rq_list);
+			blk_mq_dispatch_rq_list(q, &rq_list);
+		} else {
+			blk_mq_do_dispatch_ctx(q, hctx);
+		}
+	} else {
 
-	/*
-	 * 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.
-	 */
-	if (has_sched_dispatch)
+		/*
+		 * 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.
+		 */
 		blk_mq_do_dispatch_sched(q, e, hctx);
-	else
-		blk_mq_do_dispatch_ctx(q, hctx);
+	}
 }
 
 bool blk_mq_sched_try_merge(struct request_queue *q, struct bio *bio,

@@ -330,6 +353,7 @@ static bool blk_mq_sched_bypass_insert(struct blk_mq_hw_ctx *hctx,
 	 */
 	spin_lock(&hctx->lock);
 	list_add(&rq->queuelist, &hctx->dispatch);
+	set_bit(BLK_MQ_S_DISPATCH_BUSY, &hctx->state);
 	spin_unlock(&hctx->lock);
 	return true;
 }

block/blk-mq.c +6 -0

index f063dd0f197f..6af56a71c1cd 100644
@@ -1140,6 +1140,11 @@ bool blk_mq_dispatch_rq_list(struct request_queue *q, struct list_head *list)
 
 		spin_lock(&hctx->lock);
 		list_splice_init(list, &hctx->dispatch);
+		/*
+		 * DISPATCH_BUSY won't be cleared until all requests
+		 * in hctx->dispatch are dispatched successfully
+		 */
+		set_bit(BLK_MQ_S_DISPATCH_BUSY, &hctx->state);
 		spin_unlock(&hctx->lock);
 
 		/*

@@ -1927,6 +1932,7 @@ static int blk_mq_hctx_notify_dead(unsigned int cpu, struct hlist_node *node)
 
 	spin_lock(&hctx->lock);
 	list_splice_tail_init(&tmp, &hctx->dispatch);
+	set_bit(BLK_MQ_S_DISPATCH_BUSY, &hctx->state);
 	spin_unlock(&hctx->lock);
 
 	blk_mq_run_hw_queue(hctx, true);

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

index 7b7a366a97f3..13f6c25fa461 100644
@@ -172,6 +172,7 @@ enum {
 	BLK_MQ_S_SCHED_RESTART	= 2,
 	BLK_MQ_S_TAG_WAITING	= 3,
 	BLK_MQ_S_START_ON_RUN	= 4,
+	BLK_MQ_S_DISPATCH_BUSY	= 5,
 
 	BLK_MQ_MAX_DEPTH	= 10240,
 

Signature · 1 line

2.9.5

Quoted 8 lines · Ming Lei

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.

Quoted 6 lines

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]>

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

Neat. I did something similar when I first started on I/O scheduling for blk-mq, but I completely serialized dispatch so only one CPU would be dispatching a given hctx at a time. I ended up ditching it because it was actually a performance regression on artificial null-blk tests with many CPUs and 1 hctx, and it was also really hard to get right without deadlocks. Yours still allows concurrent dispatch from multiple CPUs, so you probably wouldn't have those same issues, but I don't like how handwavy this is about races on the DISPATCH_BUSY bit, and how the handling of that bit is spread around everywhere. I'm not totally opposed to taking this as is, but what do you think about serializing the dispatch per hctx completely?