[PATCH RFC v2 0/4] lib/sbitmap: fix shallow_depth tag allocation

[PATCH RFC v2 0/4] lib/sbitmap: fix shallow_depth tag allocation

[Yu Kuai]

From: Yu Kuai <yukuai3@huawei.com>

Changes in RFC v2:
 - update commit message for patch 1;
 - also handle min_shallow_depth in patch 2;
 - add patch 3 to choose none elevator by default;
 - add patch 4 to fix default wake_batch;

Yu Kuai (4):
  block/mq-deadline: Revert "block/mq-deadline: Fix the tag reservation
    code"
  lib/sbitmap: fix shallow_depth tag allocation
  block/elevator: choose none elevator for high IO concurrency ability
    disk
  block/mq-deadline: introduce min_async_depth

 block/elevator.c        | 11 +++++++++
 block/mq-deadline.c     | 35 +++++++++++++-------------
 include/linux/sbitmap.h |  6 ++---
 lib/sbitmap.c           | 55 +++++++++++++++++++++--------------------
 4 files changed, 59 insertions(+), 48 deletions(-)

-- 
2.39.2

[PATCH RFC v2 1/4] block/mq-deadline: Revert "block/mq-deadline: Fix the tag reservation code"

[Yu Kuai]

From: Yu Kuai <yukuai3@huawei.com>

This reverts commit 39823b47bbd40502632ffba90ebb34fff7c8b5e8.

1) Set min_shallow_depth to 1 will end up setting wake_batch to 1,
   and this will cause performance degradation in some high concurrency
   test, for both IO bandwidth and cpu usage.

   async_depth can be changed by sysfs, and the minimal value is 1. This
   is why min_shallow_depth is set to 1 at initialization to make sure
   functional is correct if async_depth is set to 1. However, sacrifice
   performance in the default scenario is not acceptable.

2) dd_to_word_depth() is supposed to scale down async_depth, however, user
   can set low nr_requests and sb->depth can be less than 1 << sb->shift,
   then dd_to_word_depth() will end up scale up async_depth.

Fixes: 39823b47bbd4 ("block/mq-deadline: Fix the tag reservation code")
Signed-off-by: Yu Kuai <yukuai3@huawei.com>
---
 block/mq-deadline.c | 20 +++-----------------
 1 file changed, 3 insertions(+), 17 deletions(-)

diff --git a/block/mq-deadline.c b/block/mq-deadline.c
index 91b3789f710e..1f0d175a941e 100644
--- a/block/mq-deadline.c
+++ b/block/mq-deadline.c
@@ -487,20 +487,6 @@ static struct request *dd_dispatch_request(struct blk_mq_hw_ctx *hctx)
 	return rq;
 }
 
-/*
- * 'depth' is a number in the range 1..INT_MAX representing a number of
- * requests. Scale it with a factor (1 << bt->sb.shift) / q->nr_requests since
- * 1..(1 << bt->sb.shift) is the range expected by sbitmap_get_shallow().
- * Values larger than q->nr_requests have the same effect as q->nr_requests.
- */
-static int dd_to_word_depth(struct blk_mq_hw_ctx *hctx, unsigned int qdepth)
-{
-	struct sbitmap_queue *bt = &hctx->sched_tags->bitmap_tags;
-	const unsigned int nrr = hctx->queue->nr_requests;
-
-	return ((qdepth << bt->sb.shift) + nrr - 1) / nrr;
-}
-
 /*
  * Called by __blk_mq_alloc_request(). The shallow_depth value set by this
  * function is used by __blk_mq_get_tag().
@@ -517,7 +503,7 @@ static void dd_limit_depth(blk_opf_t opf, struct blk_mq_alloc_data *data)
 	 * Throttle asynchronous requests and writes such that these requests
 	 * do not block the allocation of synchronous requests.
 	 */
-	data->shallow_depth = dd_to_word_depth(data->hctx, dd->async_depth);
+	data->shallow_depth = dd->async_depth;
 }
 
 /* Called by blk_mq_update_nr_requests(). */
@@ -527,9 +513,9 @@ static void dd_depth_updated(struct blk_mq_hw_ctx *hctx)
 	struct deadline_data *dd = q->elevator->elevator_data;
 	struct blk_mq_tags *tags = hctx->sched_tags;
 
-	dd->async_depth = q->nr_requests;
+	dd->async_depth = max(1UL, 3 * q->nr_requests / 4);
 
-	sbitmap_queue_min_shallow_depth(&tags->bitmap_tags, 1);
+	sbitmap_queue_min_shallow_depth(&tags->bitmap_tags, dd->async_depth);
 }
 
 /* Called by blk_mq_init_hctx() and blk_mq_init_sched(). */
-- 
2.39.2

[PATCH v2 RFC 2/4] lib/sbitmap: fix shallow_depth tag allocation

[Yu Kuai]

From: Yu Kuai <yukuai3@huawei.com>

Currently, shallow_depth is used by bfq, kyber and mq-deadline, they both
pass in the value for the whole sbitmap, while sbitmap treats the value
for just one word. Which means, shallow_depth never work as expected,
and there really is no such functional tests to covert it.

Consider that callers doesn't know which word will be used, and it's
not possible to distinguish the last word and previous word. Fix this
problem by treating shallow_depth for the whole sbitmap in
sbitmap_find_bit().

Fixes: 00e043936e9a ("blk-mq: introduce Kyber multiqueue I/O scheduler")
Fixes: a52a69ea89dc ("block, bfq: limit tags for writes and async I/O")
Fixes: 07757588e507 ("block/mq-deadline: Reserve 25% of scheduler tags for synchronous requests")
Signed-off-by: Yu Kuai <yukuai3@huawei.com>
---
 include/linux/sbitmap.h |  6 ++---
 lib/sbitmap.c           | 55 +++++++++++++++++++++--------------------
 2 files changed, 31 insertions(+), 30 deletions(-)

diff --git a/include/linux/sbitmap.h b/include/linux/sbitmap.h
index 189140bf11fc..92e77bc13cf6 100644
--- a/include/linux/sbitmap.h
+++ b/include/linux/sbitmap.h
@@ -213,12 +213,12 @@ int sbitmap_get(struct sbitmap *sb);
  * sbitmap_get_shallow() - Try to allocate a free bit from a &struct sbitmap,
  * limiting the depth used from each word.
  * @sb: Bitmap to allocate from.
- * @shallow_depth: The maximum number of bits to allocate from a single word.
+ * @shallow_depth: The maximum number of bits to allocate from the bitmap.
  *
  * This rather specific operation allows for having multiple users with
  * different allocation limits. E.g., there can be a high-priority class that
  * uses sbitmap_get() and a low-priority class that uses sbitmap_get_shallow()
- * with a @shallow_depth of (1 << (@sb->shift - 1)). Then, the low-priority
+ * with a @shallow_depth of (sb->depth << 1). Then, the low-priority
  * class can only allocate half of the total bits in the bitmap, preventing it
  * from starving out the high-priority class.
  *
@@ -478,7 +478,7 @@ unsigned long __sbitmap_queue_get_batch(struct sbitmap_queue *sbq, int nr_tags,
  * sbitmap_queue, limiting the depth used from each word, with preemption
  * already disabled.
  * @sbq: Bitmap queue to allocate from.
- * @shallow_depth: The maximum number of bits to allocate from a single word.
+ * @shallow_depth: The maximum number of bits to allocate from the queue.
  * See sbitmap_get_shallow().
  *
  * If you call this, make sure to call sbitmap_queue_min_shallow_depth() after
diff --git a/lib/sbitmap.c b/lib/sbitmap.c
index d3412984170c..6b8b909614a5 100644
--- a/lib/sbitmap.c
+++ b/lib/sbitmap.c
@@ -208,8 +208,27 @@ static int sbitmap_find_bit_in_word(struct sbitmap_word *map,
 	return nr;
 }
 
+static unsigned int __map_depth_with_shallow(const struct sbitmap *sb,
+					     int index,
+					     unsigned int shallow_depth)
+{
+	unsigned int pre_word_bits = 0;
+
+	if (shallow_depth >= sb->depth)
+		return __map_depth(sb, index);
+
+	if (index > 0)
+		pre_word_bits += (index - 1) << sb->shift;
+
+	if (shallow_depth <= pre_word_bits)
+		return 0;
+
+	return min_t(unsigned int, __map_depth(sb, index),
+				   shallow_depth - pre_word_bits);
+}
+
 static int sbitmap_find_bit(struct sbitmap *sb,
-			    unsigned int depth,
+			    unsigned int shallow_depth,
 			    unsigned int index,
 			    unsigned int alloc_hint,
 			    bool wrap)
@@ -218,12 +237,12 @@ static int sbitmap_find_bit(struct sbitmap *sb,
 	int nr = -1;
 
 	for (i = 0; i < sb->map_nr; i++) {
-		nr = sbitmap_find_bit_in_word(&sb->map[index],
-					      min_t(unsigned int,
-						    __map_depth(sb, index),
-						    depth),
-					      alloc_hint, wrap);
+		unsigned int depth = __map_depth_with_shallow(sb, index,
+							      shallow_depth);
 
+		if (depth)
+			nr = sbitmap_find_bit_in_word(&sb->map[index], depth,
+						      alloc_hint, wrap);
 		if (nr != -1) {
 			nr += index << sb->shift;
 			break;
@@ -406,27 +425,9 @@ EXPORT_SYMBOL_GPL(sbitmap_bitmap_show);
 static unsigned int sbq_calc_wake_batch(struct sbitmap_queue *sbq,
 					unsigned int depth)
 {
-	unsigned int wake_batch;
-	unsigned int shallow_depth;
-
-	/*
-	 * Each full word of the bitmap has bits_per_word bits, and there might
-	 * be a partial word. There are depth / bits_per_word full words and
-	 * depth % bits_per_word bits left over. In bitwise arithmetic:
-	 *
-	 * bits_per_word = 1 << shift
-	 * depth / bits_per_word = depth >> shift
-	 * depth % bits_per_word = depth & ((1 << shift) - 1)
-	 *
-	 * Each word can be limited to sbq->min_shallow_depth bits.
-	 */
-	shallow_depth = min(1U << sbq->sb.shift, sbq->min_shallow_depth);
-	depth = ((depth >> sbq->sb.shift) * shallow_depth +
-		 min(depth & ((1U << sbq->sb.shift) - 1), shallow_depth));
-	wake_batch = clamp_t(unsigned int, depth / SBQ_WAIT_QUEUES, 1,
-			     SBQ_WAKE_BATCH);
-
-	return wake_batch;
+	return clamp_t(unsigned int,
+		       min(depth, sbq->min_shallow_depth) / SBQ_WAIT_QUEUES,
+		       1, SBQ_WAKE_BATCH);
 }
 
 int sbitmap_queue_init_node(struct sbitmap_queue *sbq, unsigned int depth,
-- 
2.39.2

[PATCH v2 3/4] block/elevator: choose none elevator for high IO concurrency ability disk

[Yu Kuai]

From: Yu Kuai <yukuai3@huawei.com>

The maximal default nr_requests is 256, and if disk can handle more than
256 requests concurrently, use elevator in this case is useless, on the
one hand it limits the number of requests to 256, on the other hand,
it can't merge or sort IO because requests are dispatched to disk
immediately and the elevator is just empty.

For example, for nvme megaraid with 512 queue_depth by default, we have
to change default elevator to none, otherwise deadline will lose a lot of
performance.

Signed-off-by: Yu Kuai <yukuai3@huawei.com>
---
 block/elevator.c | 11 +++++++++++
 1 file changed, 11 insertions(+)

diff --git a/block/elevator.c b/block/elevator.c
index 7c3ba80e5ff4..4cce1e7c47d5 100644
--- a/block/elevator.c
+++ b/block/elevator.c
@@ -568,6 +568,17 @@ static struct elevator_type *elevator_get_default(struct request_queue *q)
 	    !blk_mq_is_shared_tags(q->tag_set->flags))
 		return NULL;
 
+	/*
+	 * If nr_queues will be less than disk ability, requests will be
+	 * dispatched to disk immediately, it's useless to use elevator. User
+	 * should set a bigger nr_requests or limit disk ability manually if
+	 * they really want to use elevator.
+	 */
+	if (q->queue_depth && q->queue_depth >= BLKDEV_DEFAULT_RQ * 2)
+		return NULL;
+	if (!q->queue_depth && q->tag_set->queue_depth >= BLKDEV_DEFAULT_RQ * 2)
+		return NULL;
+
 	return elevator_find_get("mq-deadline");
 }
 
-- 
2.39.2

[PATCH RFC v2 4/4] block/mq-deadline: introduce min_async_depth

[Yu Kuai]

From: Yu Kuai <yukuai3@huawei.com>

min_shallow_depth must be less or equal to any shallow_depth value, and
it's 1 currently, and this will change default wake_batch to 1, causing
performance degradation for fast disk with high concurrency. This patch
make following changes:

- set default minimal async_depth to 64, to avoid performance
  degradation in the commen case. And user can set lower value if
  necessary.
- disable throttling asynchronous requests by default, to prevent
  performance degradation in some special setup. User must set a value
  to async_depth to enable it.
- if async_depth is set already, don't reset it if user sets new
  nr_requests.

Fixes: 07757588e507 ("block/mq-deadline: Reserve 25% of scheduler tags for synchronous requests")
Signed-off-by: Yu Kuai <yukuai3@huawei.com>
---
 block/mq-deadline.c | 19 ++++++++++++++++---
 1 file changed, 16 insertions(+), 3 deletions(-)

diff --git a/block/mq-deadline.c b/block/mq-deadline.c
index 1f0d175a941e..9be0a33985ce 100644
--- a/block/mq-deadline.c
+++ b/block/mq-deadline.c
@@ -24,6 +24,16 @@
 #include "blk-mq-debugfs.h"
 #include "blk-mq-sched.h"
 
+/*
+ * async_depth is used to reserve scheduler tags for synchronous requests,
+ * and the value will affect sbitmap wake_batch. The default minimal value is 64
+ * because the corresponding wake_batch is 8, and lower wake_batch may affect
+ * IO performance.
+ */
+static unsigned int min_async_depth = 64;
+module_param(min_async_depth, int, 0444);
+MODULE_PARM_DESC(min_async_depth, "The minimal number of tags available for asynchronous requests");
+
 /*
  * See Documentation/block/deadline-iosched.rst
  */
@@ -513,9 +523,12 @@ static void dd_depth_updated(struct blk_mq_hw_ctx *hctx)
 	struct deadline_data *dd = q->elevator->elevator_data;
 	struct blk_mq_tags *tags = hctx->sched_tags;
 
-	dd->async_depth = max(1UL, 3 * q->nr_requests / 4);
+	if (q->nr_requests > min_async_depth)
+		sbitmap_queue_min_shallow_depth(&tags->bitmap_tags,
+						min_async_depth);
 
-	sbitmap_queue_min_shallow_depth(&tags->bitmap_tags, dd->async_depth);
+	if (q->nr_requests <= dd->async_depth)
+		dd->async_depth = 0;
 }
 
 /* Called by blk_mq_init_hctx() and blk_mq_init_sched(). */
@@ -814,7 +827,7 @@ STORE_JIFFIES(deadline_write_expire_store, &dd->fifo_expire[DD_WRITE], 0, INT_MA
 STORE_JIFFIES(deadline_prio_aging_expire_store, &dd->prio_aging_expire, 0, INT_MAX);
 STORE_INT(deadline_writes_starved_store, &dd->writes_starved, INT_MIN, INT_MAX);
 STORE_INT(deadline_front_merges_store, &dd->front_merges, 0, 1);
-STORE_INT(deadline_async_depth_store, &dd->async_depth, 1, INT_MAX);
+STORE_INT(deadline_async_depth_store, &dd->async_depth, min_async_depth, INT_MAX);
 STORE_INT(deadline_fifo_batch_store, &dd->fifo_batch, 0, INT_MAX);
 #undef STORE_FUNCTION
 #undef STORE_INT
-- 
2.39.2

Re: [PATCH RFC v2 1/4] block/mq-deadline: Revert "block/mq-deadline: Fix the tag reservation code"

[Bart Van Assche]

On 12/16/24 6:40 PM, Yu Kuai wrote:
> From: Yu Kuai <yukuai3@huawei.com>
> 
> This reverts commit 39823b47bbd40502632ffba90ebb34fff7c8b5e8.
> 
> 1) Set min_shallow_depth to 1 will end up setting wake_batch to 1,
>     and this will cause performance degradation in some high concurrency
>     test, for both IO bandwidth and cpu usage.
> 
>     async_depth can be changed by sysfs, and the minimal value is 1. This
>     is why min_shallow_depth is set to 1 at initialization to make sure
>     functional is correct if async_depth is set to 1. However, sacrifice
>     performance in the default scenario is not acceptable.
> 
> 2) dd_to_word_depth() is supposed to scale down async_depth, however, user
>     can set low nr_requests and sb->depth can be less than 1 << sb->shift,
>     then dd_to_word_depth() will end up scale up async_depth.

Although this patch fixes a performance regression, it breaks the
async_depth functionality. If we are going to break that functionality
temporarily, I propose to do something like this:

diff --git a/block/mq-deadline.c b/block/mq-deadline.c
index 20a8a3afb88b..4cc7b5db4669 100644
--- a/block/mq-deadline.c
+++ b/block/mq-deadline.c
@@ -487,37 +487,12 @@ static struct request *dd_dispatch_request(struct 
blk_mq_hw_ctx *hctx)
  	return rq;
  }

-/*
- * 'depth' is a number in the range 1..INT_MAX representing a number of
- * requests. Scale it with a factor (1 << bt->sb.shift) / 
q->nr_requests since
- * 1..(1 << bt->sb.shift) is the range expected by sbitmap_get_shallow().
- * Values larger than q->nr_requests have the same effect as 
q->nr_requests.
- */
-static int dd_to_word_depth(struct blk_mq_hw_ctx *hctx, unsigned int 
qdepth)
-{
-	struct sbitmap_queue *bt = &hctx->sched_tags->bitmap_tags;
-	const unsigned int nrr = hctx->queue->nr_requests;
-
-	return ((qdepth << bt->sb.shift) + nrr - 1) / nrr;
-}
-
  /*
   * Called by __blk_mq_alloc_request(). The shallow_depth value set by this
   * function is used by __blk_mq_get_tag().
   */
  static void dd_limit_depth(blk_opf_t opf, struct blk_mq_alloc_data *data)
  {
-	struct deadline_data *dd = data->q->elevator->elevator_data;
-
-	/* Do not throttle synchronous reads. */
-	if (op_is_sync(opf) && !op_is_write(opf))
-		return;
-
-	/*
-	 * Throttle asynchronous requests and writes such that these requests
-	 * do not block the allocation of synchronous requests.
-	 */
-	data->shallow_depth = dd_to_word_depth(data->hctx, dd->async_depth);
  }

  /* Called by blk_mq_update_nr_requests(). */
@@ -525,11 +500,8 @@ static void dd_depth_updated(struct blk_mq_hw_ctx 
*hctx)
  {
  	struct request_queue *q = hctx->queue;
  	struct deadline_data *dd = q->elevator->elevator_data;
-	struct blk_mq_tags *tags = hctx->sched_tags;

  	dd->async_depth = q->nr_requests;
-
-	sbitmap_queue_min_shallow_depth(&tags->bitmap_tags, 1);
  }

  /* Called by blk_mq_init_hctx() and blk_mq_init_sched(). */

Re: [PATCH v2 RFC 2/4] lib/sbitmap: fix shallow_depth tag allocation

[Bart Van Assche]

On 12/16/24 6:40 PM, Yu Kuai wrote:
> From: Yu Kuai <yukuai3@huawei.com>
> 
> Currently, shallow_depth is used by bfq, kyber and mq-deadline, they both

both -> all

> pass in the value for the whole sbitmap, while sbitmap treats the value

treats for -> applies to

> for just one word. Which means, shallow_depth never work as expected,

work -> works

> and there really is no such functional tests to covert it.

is ... tests -> is ... test or are ... tests

covert -> cover

> Consider that callers doesn't know which word will be used, and it's

Consider -> Considering
doesn't -> don't

> diff --git a/include/linux/sbitmap.h b/include/linux/sbitmap.h
> index 189140bf11fc..92e77bc13cf6 100644
> --- a/include/linux/sbitmap.h
> +++ b/include/linux/sbitmap.h
> @@ -213,12 +213,12 @@ int sbitmap_get(struct sbitmap *sb);
>    * sbitmap_get_shallow() - Try to allocate a free bit from a &struct sbitmap,
>    * limiting the depth used from each word.
>    * @sb: Bitmap to allocate from.
> - * @shallow_depth: The maximum number of bits to allocate from a single word.
> + * @shallow_depth: The maximum number of bits to allocate from the bitmap.
>    *
>    * This rather specific operation allows for having multiple users with
>    * different allocation limits. E.g., there can be a high-priority class that
>    * uses sbitmap_get() and a low-priority class that uses sbitmap_get_shallow()
> - * with a @shallow_depth of (1 << (@sb->shift - 1)). Then, the low-priority
> + * with a @shallow_depth of (sb->depth << 1). Then, the low-priority

(sb->depth << 1) -> (sb->depth >> 1)

> diff --git a/lib/sbitmap.c b/lib/sbitmap.c
> index d3412984170c..6b8b909614a5 100644
> --- a/lib/sbitmap.c
> +++ b/lib/sbitmap.c
> @@ -208,8 +208,27 @@ static int sbitmap_find_bit_in_word(struct sbitmap_word *map,
>   	return nr;
>   }
>   
> +static unsigned int __map_depth_with_shallow(const struct sbitmap *sb,
> +					     int index,
> +					     unsigned int shallow_depth)
> +{
> +	unsigned int pre_word_bits = 0;
> +
> +	if (shallow_depth >= sb->depth)
> +		return __map_depth(sb, index);
> +
> +	if (index > 0)
> +		pre_word_bits += (index - 1) << sb->shift;

Why "index - 1" instead of "index"?

> +
> +	if (shallow_depth <= pre_word_bits)
> +		return 0;
> +
> +	return min_t(unsigned int, __map_depth(sb, index),
> +				   shallow_depth - pre_word_bits);
> +}

How about renaming pre_word_bits into lower_bound?

Otherwise this patch looks good to me.

Thanks,

Bart.

Re: [PATCH v2 3/4] block/elevator: choose none elevator for high IO concurrency ability disk

[Bart Van Assche]

On 12/16/24 6:40 PM, Yu Kuai wrote:
> From: Yu Kuai <yukuai3@huawei.com>
> 
> The maximal default nr_requests is 256, and if disk can handle more than
> 256 requests concurrently, use elevator in this case is useless, on the
> one hand it limits the number of requests to 256, on the other hand,
> it can't merge or sort IO because requests are dispatched to disk
> immediately and the elevator is just empty.
> 
> For example, for nvme megaraid with 512 queue_depth by default, we have
> to change default elevator to none, otherwise deadline will lose a lot of
> performance.
> 
> Signed-off-by: Yu Kuai <yukuai3@huawei.com>
> ---
>   block/elevator.c | 11 +++++++++++
>   1 file changed, 11 insertions(+)
> 
> diff --git a/block/elevator.c b/block/elevator.c
> index 7c3ba80e5ff4..4cce1e7c47d5 100644
> --- a/block/elevator.c
> +++ b/block/elevator.c
> @@ -568,6 +568,17 @@ static struct elevator_type *elevator_get_default(struct request_queue *q)
>   	    !blk_mq_is_shared_tags(q->tag_set->flags))
>   		return NULL;
>   
> +	/*
> +	 * If nr_queues will be less than disk ability, requests will be
> +	 * dispatched to disk immediately, it's useless to use elevator. User
> +	 * should set a bigger nr_requests or limit disk ability manually if
> +	 * they really want to use elevator.
> +	 */
> +	if (q->queue_depth && q->queue_depth >= BLKDEV_DEFAULT_RQ * 2)
> +		return NULL;
> +	if (!q->queue_depth && q->tag_set->queue_depth >= BLKDEV_DEFAULT_RQ * 2)
> +		return NULL;
> +
>   	return elevator_find_get("mq-deadline");
>   }

Shouldn't this patch be submitted separately since it is independent of
the rest of the patches in this series?

Thanks,

Bart.

Re: [PATCH RFC v2 4/4] block/mq-deadline: introduce min_async_depth

[Bart Van Assche]

On 12/16/24 6:40 PM, Yu Kuai wrote:
> +static unsigned int min_async_depth = 64;
> +module_param(min_async_depth, int, 0444);
> +MODULE_PARM_DESC(min_async_depth, "The minimal number of tags available for asynchronous requests");

Users may not like it that this parameter is read-only.

> @@ -513,9 +523,12 @@ static void dd_depth_updated(struct blk_mq_hw_ctx *hctx)
>   	struct deadline_data *dd = q->elevator->elevator_data;
>   	struct blk_mq_tags *tags = hctx->sched_tags;
>   
> -	dd->async_depth = max(1UL, 3 * q->nr_requests / 4);

Shouldn't this assignment be retained instead of removing it? 
Additionally, some time ago a user requested to initialize 
dd->async_depth to q->nr_requests instead of 3/4 of that value because
the lower value introduced a performance regression.

Thanks,

Bart.

Re: [PATCH RFC v2 4/4] block/mq-deadline: introduce min_async_depth

[Yu Kuai]

Hi,

在 2024/12/18 6:13, Bart Van Assche 写道:
> On 12/16/24 6:40 PM, Yu Kuai wrote:
>> +static unsigned int min_async_depth = 64;
>> +module_param(min_async_depth, int, 0444);
>> +MODULE_PARM_DESC(min_async_depth, "The minimal number of tags 
>> available for asynchronous requests");
> 
> Users may not like it that this parameter is read-only.
> 
>> @@ -513,9 +523,12 @@ static void dd_depth_updated(struct blk_mq_hw_ctx 
>> *hctx)
>>       struct deadline_data *dd = q->elevator->elevator_data;
>>       struct blk_mq_tags *tags = hctx->sched_tags;
>> -    dd->async_depth = max(1UL, 3 * q->nr_requests / 4);
> 
> Shouldn't this assignment be retained instead of removing it? 
> Additionally, some time ago a user requested to initialize 
> dd->async_depth to q->nr_requests instead of 3/4 of that value because
> the lower value introduced a performance regression.
dd->async_depth is initialized to 0 now, functionally I think
it's the same as q->nr_requests. And I do explain this in commit
message, maybe it's not clear?

BTW, if user sets new nr_requests and async_depth < new nr_requests,
async_depth won't be reset after this patch.

Thanks,
Kuai

> 
> Thanks,
> 
> Bart.
> 
> .
> 

Re: [PATCH RFC v2 4/4] block/mq-deadline: introduce min_async_depth

[Yu Kuai]

Hi,

在 2024/12/18 9:12, Yu Kuai 写道:
> 
> Users may not like it that this parameter is read-only.

I can't make this read-write, because set lower value will cause
problems for existing elevator, because wake_batch has to be
updated as well.

Thanks,
Kuai

Re: [PATCH RFC v2 1/4] block/mq-deadline: Revert "block/mq-deadline: Fix the tag reservation code"

[Yu Kuai]

Hi,

在 2024/12/18 5:39, Bart Van Assche 写道:
> On 12/16/24 6:40 PM, Yu Kuai wrote:
>> From: Yu Kuai <yukuai3@huawei.com>
>>
>> This reverts commit 39823b47bbd40502632ffba90ebb34fff7c8b5e8.
>>
>> 1) Set min_shallow_depth to 1 will end up setting wake_batch to 1,
>>     and this will cause performance degradation in some high concurrency
>>     test, for both IO bandwidth and cpu usage.
>>
>>     async_depth can be changed by sysfs, and the minimal value is 1. This
>>     is why min_shallow_depth is set to 1 at initialization to make sure
>>     functional is correct if async_depth is set to 1. However, sacrifice
>>     performance in the default scenario is not acceptable.
>>
>> 2) dd_to_word_depth() is supposed to scale down async_depth, however, 
>> user
>>     can set low nr_requests and sb->depth can be less than 1 << 
>> sb->shift,
>>     then dd_to_word_depth() will end up scale up async_depth.
> 
> Although this patch fixes a performance regression, it breaks the
> async_depth functionality. If we are going to break that functionality
> temporarily, I propose to do something like this:

Yes, I'll split this patch, and merge the async_depth changes into the
last patch.

Thanks,
Kuai

> 
> diff --git a/block/mq-deadline.c b/block/mq-deadline.c
> index 20a8a3afb88b..4cc7b5db4669 100644
> --- a/block/mq-deadline.c
> +++ b/block/mq-deadline.c
> @@ -487,37 +487,12 @@ static struct request *dd_dispatch_request(struct 
> blk_mq_hw_ctx *hctx)
>       return rq;
>   }
> 
> -/*
> - * 'depth' is a number in the range 1..INT_MAX representing a number of
> - * requests. Scale it with a factor (1 << bt->sb.shift) / 
> q->nr_requests since
> - * 1..(1 << bt->sb.shift) is the range expected by sbitmap_get_shallow().
> - * Values larger than q->nr_requests have the same effect as 
> q->nr_requests.
> - */
> -static int dd_to_word_depth(struct blk_mq_hw_ctx *hctx, unsigned int 
> qdepth)
> -{
> -    struct sbitmap_queue *bt = &hctx->sched_tags->bitmap_tags;
> -    const unsigned int nrr = hctx->queue->nr_requests;
> -
> -    return ((qdepth << bt->sb.shift) + nrr - 1) / nrr;
> -}
> -
>   /*
>    * Called by __blk_mq_alloc_request(). The shallow_depth value set by 
> this
>    * function is used by __blk_mq_get_tag().
>    */
>   static void dd_limit_depth(blk_opf_t opf, struct blk_mq_alloc_data *data)
>   {
> -    struct deadline_data *dd = data->q->elevator->elevator_data;
> -
> -    /* Do not throttle synchronous reads. */
> -    if (op_is_sync(opf) && !op_is_write(opf))
> -        return;
> -
> -    /*
> -     * Throttle asynchronous requests and writes such that these requests
> -     * do not block the allocation of synchronous requests.
> -     */
> -    data->shallow_depth = dd_to_word_depth(data->hctx, dd->async_depth);
>   }
> 
>   /* Called by blk_mq_update_nr_requests(). */
> @@ -525,11 +500,8 @@ static void dd_depth_updated(struct blk_mq_hw_ctx 
> *hctx)
>   {
>       struct request_queue *q = hctx->queue;
>       struct deadline_data *dd = q->elevator->elevator_data;
> -    struct blk_mq_tags *tags = hctx->sched_tags;
> 
>       dd->async_depth = q->nr_requests;
> -
> -    sbitmap_queue_min_shallow_depth(&tags->bitmap_tags, 1);
>   }
> 
>   /* Called by blk_mq_init_hctx() and blk_mq_init_sched(). */
> 
> .
> 

Re: [PATCH v2 RFC 2/4] lib/sbitmap: fix shallow_depth tag allocation

[Yu Kuai]

Hi,

在 2024/12/18 5:47, Bart Van Assche 写道:
> On 12/16/24 6:40 PM, Yu Kuai wrote:
>> From: Yu Kuai <yukuai3@huawei.com>
>>
>> Currently, shallow_depth is used by bfq, kyber and mq-deadline, they both
> 
> both -> all
> 
>> pass in the value for the whole sbitmap, while sbitmap treats the value
> 
> treats for -> applies to
> 
>> for just one word. Which means, shallow_depth never work as expected,
> 
> work -> works
> 
>> and there really is no such functional tests to covert it.
> 
> is ... tests -> is ... test or are ... tests
> 
> covert -> cover
> 
>> Consider that callers doesn't know which word will be used, and it's
> 
> Consider -> Considering
> doesn't -> don't
> 
>> diff --git a/include/linux/sbitmap.h b/include/linux/sbitmap.h
>> index 189140bf11fc..92e77bc13cf6 100644
>> --- a/include/linux/sbitmap.h
>> +++ b/include/linux/sbitmap.h
>> @@ -213,12 +213,12 @@ int sbitmap_get(struct sbitmap *sb);
>>    * sbitmap_get_shallow() - Try to allocate a free bit from a &struct 
>> sbitmap,
>>    * limiting the depth used from each word.
>>    * @sb: Bitmap to allocate from.
>> - * @shallow_depth: The maximum number of bits to allocate from a 
>> single word.
>> + * @shallow_depth: The maximum number of bits to allocate from the 
>> bitmap.
>>    *
>>    * This rather specific operation allows for having multiple users with
>>    * different allocation limits. E.g., there can be a high-priority 
>> class that
>>    * uses sbitmap_get() and a low-priority class that uses 
>> sbitmap_get_shallow()
>> - * with a @shallow_depth of (1 << (@sb->shift - 1)). Then, the 
>> low-priority
>> + * with a @shallow_depth of (sb->depth << 1). Then, the low-priority
> 
> (sb->depth << 1) -> (sb->depth >> 1)
> 
>> diff --git a/lib/sbitmap.c b/lib/sbitmap.c
>> index d3412984170c..6b8b909614a5 100644
>> --- a/lib/sbitmap.c
>> +++ b/lib/sbitmap.c
>> @@ -208,8 +208,27 @@ static int sbitmap_find_bit_in_word(struct 
>> sbitmap_word *map,
>>       return nr;
>>   }
>> +static unsigned int __map_depth_with_shallow(const struct sbitmap *sb,
>> +                         int index,
>> +                         unsigned int shallow_depth)
>> +{
>> +    unsigned int pre_word_bits = 0;
>> +
>> +    if (shallow_depth >= sb->depth)
>> +        return __map_depth(sb, index);
>> +
>> +    if (index > 0)
>> +        pre_word_bits += (index - 1) << sb->shift;
> 
> Why "index - 1" instead of "index"?

We're finding bit in the 'index' word, and pre_word_bits are the number
of bits in previous workds.

> 
>> +
>> +    if (shallow_depth <= pre_word_bits)
>> +        return 0;
>> +
>> +    return min_t(unsigned int, __map_depth(sb, index),
>> +                   shallow_depth - pre_word_bits);
>> +}
> 
> How about renaming pre_word_bits into lower_bound?

Yes.
> 
> Otherwise this patch looks good to me.
> 

Thanks,
Kuai

> Thanks,
> 
> Bart.
> .
> 

Re: [PATCH v2 3/4] block/elevator: choose none elevator for high IO concurrency ability disk

[Yu Kuai]

Hi,

在 2024/12/18 5:50, Bart Van Assche 写道:
> On 12/16/24 6:40 PM, Yu Kuai wrote:
>> From: Yu Kuai <yukuai3@huawei.com>
>>
>> The maximal default nr_requests is 256, and if disk can handle more than
>> 256 requests concurrently, use elevator in this case is useless, on the
>> one hand it limits the number of requests to 256, on the other hand,
>> it can't merge or sort IO because requests are dispatched to disk
>> immediately and the elevator is just empty.
>>
>> For example, for nvme megaraid with 512 queue_depth by default, we have
>> to change default elevator to none, otherwise deadline will lose a lot of
>> performance.
>>
>> Signed-off-by: Yu Kuai <yukuai3@huawei.com>
>> ---
>>   block/elevator.c | 11 +++++++++++
>>   1 file changed, 11 insertions(+)
>>
>> diff --git a/block/elevator.c b/block/elevator.c
>> index 7c3ba80e5ff4..4cce1e7c47d5 100644
>> --- a/block/elevator.c
>> +++ b/block/elevator.c
>> @@ -568,6 +568,17 @@ static struct elevator_type 
>> *elevator_get_default(struct request_queue *q)
>>           !blk_mq_is_shared_tags(q->tag_set->flags))
>>           return NULL;
>> +    /*
>> +     * If nr_queues will be less than disk ability, requests will be
>> +     * dispatched to disk immediately, it's useless to use elevator. 
>> User
>> +     * should set a bigger nr_requests or limit disk ability manually if
>> +     * they really want to use elevator.
>> +     */
>> +    if (q->queue_depth && q->queue_depth >= BLKDEV_DEFAULT_RQ * 2)
>> +        return NULL;
>> +    if (!q->queue_depth && q->tag_set->queue_depth >= 
>> BLKDEV_DEFAULT_RQ * 2)
>> +        return NULL;
>> +
>>       return elevator_find_get("mq-deadline");
>>   }
> 
> Shouldn't this patch be submitted separately since it is independent of
> the rest of the patches in this series?

Yes, this patch was added to this set by mistake. My bad. :(
I'm supposed to use the cleanup patch from v1 to replace this patch.

Thanks,
Kuai

> 
> Thanks,
> 
> Bart.
> 
> 
> .
> 

Re: [PATCH RFC v2 4/4] block/mq-deadline: introduce min_async_depth

[Bart Van Assche]

On 12/17/24 5:14 PM, Yu Kuai wrote:
> I can't make this read-write, because set lower value will cause
> problems for existing elevator, because wake_batch has to be
> updated as well.

Should the request queue perhaps be frozen before wake_batch is updated?

Thanks,

Bart.

Re: [PATCH RFC v2 4/4] block/mq-deadline: introduce min_async_depth

[Bart Van Assche]

On 12/17/24 5:12 PM, Yu Kuai wrote:
> dd->async_depth is initialized to 0 now, functionally I think
> it's the same as q->nr_requests. And I do explain this in commit
> message, maybe it's not clear?

It would be good to add a comment in the source code that explains that
__blk_mq_get_tag() does not restrict tag allocation if dd->async_depth
is zero because that causes data->shallow_depth to be zero.

Thanks,

Bart.

Re: [PATCH RFC v2 4/4] block/mq-deadline: introduce min_async_depth

[Yu Kuai]

Hi,

在 2024/12/19 2:00, Bart Van Assche 写道:
> On 12/17/24 5:14 PM, Yu Kuai wrote:
>> I can't make this read-write, because set lower value will cause
>> problems for existing elevator, because wake_batch has to be
>> updated as well.
> 
> Should the request queue perhaps be frozen before wake_batch is updated?

Yes, we should. The good thing is for now it's frozen already:
  - update nr_requests context;
  - switch elevator;

However, if you mean do this while writing async_depth, freeze queue
is not enough, we have to ping all the hctx as well by q->sysfs_lock,
which is not possible.

Or if you mean do this while write the new min_async_depth, then we have
to update wat_batch for all the queues in the system, too crazy for
me...

Thanks,
Kuai

> 
> Thanks,
> 
> Bart.
> 
> .
> 

Re: [PATCH RFC v2 4/4] block/mq-deadline: introduce min_async_depth

[Yu Kuai]

Hi,

在 2024/12/19 2:06, Bart Van Assche 写道:
> On 12/17/24 5:12 PM, Yu Kuai wrote:
>> dd->async_depth is initialized to 0 now, functionally I think
>> it's the same as q->nr_requests. And I do explain this in commit
>> message, maybe it's not clear?
> 
> It would be good to add a comment in the source code that explains that
> __blk_mq_get_tag() does not restrict tag allocation if dd->async_depth
> is zero because that causes data->shallow_depth to be zero.
> 

Ok.

Thanks,
Kuai

> Thanks,
> 
> Bart.
> .
> 

Re: [PATCH RFC v2 4/4] block/mq-deadline: introduce min_async_depth

[Bart Van Assche]

On 12/18/24 5:21 PM, Yu Kuai wrote:
> Hi,
> 
> 在 2024/12/19 2:00, Bart Van Assche 写道:
>> On 12/17/24 5:14 PM, Yu Kuai wrote:
>>> I can't make this read-write, because set lower value will cause
>>> problems for existing elevator, because wake_batch has to be
>>> updated as well.
>>
>> Should the request queue perhaps be frozen before wake_batch is updated?
> 
> Yes, we should. The good thing is for now it's frozen already:
>   - update nr_requests context;
>   - switch elevator;
> 
> However, if you mean do this while writing async_depth, freeze queue
> is not enough, we have to ping all the hctx as well by q->sysfs_lock,
> which is not possible.
> 
> Or if you mean do this while write the new min_async_depth, then we have
> to update wat_batch for all the queues in the system, too crazy for
> me...

Should min_async_depth perhaps be a request queue attribute instead of
an mq-deadline I/O scheduler attribute?

Thanks,

Bart.

Re: [PATCH RFC v2 4/4] block/mq-deadline: introduce min_async_depth

[Yu Kuai]

Hi,

在 2024/12/20 3:25, Bart Van Assche 写道:
> On 12/18/24 5:21 PM, Yu Kuai wrote:
>> Hi,
>>
>> 在 2024/12/19 2:00, Bart Van Assche 写道:
>>> On 12/17/24 5:14 PM, Yu Kuai wrote:
>>>> I can't make this read-write, because set lower value will cause
>>>> problems for existing elevator, because wake_batch has to be
>>>> updated as well.
>>>
>>> Should the request queue perhaps be frozen before wake_batch is updated?
>>
>> Yes, we should. The good thing is for now it's frozen already:
>>   - update nr_requests context;
>>   - switch elevator;
>>
>> However, if you mean do this while writing async_depth, freeze queue
>> is not enough, we have to ping all the hctx as well by q->sysfs_lock,
>> which is not possible.
>>
>> Or if you mean do this while write the new min_async_depth, then we have
>> to update wat_batch for all the queues in the system, too crazy for
>> me...
> 
> Should min_async_depth perhaps be a request queue attribute instead of
> an mq-deadline I/O scheduler attribute?

Yes, I think this make sense, at least kyber and deadline can both
benefit from this. And I might must add a new async_depth_updated() api
to the elevator ops.

Thanks,
Kuai

> 
> Thanks,
> 
> Bart.
> 
> 
> .
>