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

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

[Yu Kuai]

From: Yu Kuai <yukuai3@huawei.com>

Yu Kuai (3):
  block/mq-deadline: Revert "block/mq-deadline: Fix the tag reservation
    code"
  lib/sbitmap: don't export sbitmap_get_shallow()
  lib/sbitmap: fix shallow_depth tag allocation

 block/kyber-iosched.c   |  2 +-
 block/mq-deadline.c     | 20 +++-----------------
 include/linux/sbitmap.h | 19 +------------------
 lib/sbitmap.c           | 34 ++++++++++++++++++++++++++--------
 4 files changed, 31 insertions(+), 44 deletions(-)

-- 
2.39.2

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

[Yu Kuai]

From: Yu Kuai <yukuai3@huawei.com>

This reverts commit 39823b47bbd40502632ffba90ebb34fff7c8b5e8.

Because tag reservation is not fixed and will introduce performance
problem.

1) Set min_shallow_depth to 1 will end up setting wake_batch to 1,
   deadline has no reason to do this. And this will cause performance
   degradation in some high concurrency test, for both IO bandwidth
   and cpu usage.
2) async_depth is nr_requests, hence shallow_depth will always set to
   1 << bt->sb.shift. For consequence, no tag can be reserved.

The next patch will fix tag reservation again.

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

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

[Bart Van Assche]

On 12/9/24 7:55 PM, Yu Kuai wrote:
> From: Yu Kuai <yukuai3@huawei.com>
> 
> This reverts commit 39823b47bbd40502632ffba90ebb34fff7c8b5e8.
> 
> Because tag reservation is not fixed and will introduce performance
> problem.

As explained in detail in the patch description and in the comments
added by that patch, commit 39823b47bbd4 ("block/mq-deadline: Fix the
tag reservation code") fixes broken code. So reverting that commit is
wrong. I think that patches 1/3 and 3/3 of this series should be
combined into a single patch.

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

As explained in the commit message, this is done because
min_shallow_depth must be less than or equal to shallow_depth.
Additionally, mq-deadline is not the only I/O scheduler that sets
min_shallow_depth to 1. BFQ does this too.

> 2) async_depth is nr_requests, hence shallow_depth will always set to
>     1 << bt->sb.shift. For consequence, no tag can be reserved.

This is not correct. dd->async_depth can be modified via sysfs.

Bart.

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

[Yu Kuai]

Hi,

在 2024/12/10 2:02, Bart Van Assche 写道:
> 
>> 1) Set min_shallow_depth to 1 will end up setting wake_batch to 1,
>>     deadline has no reason to do this. And this will cause performance
>>     degradation in some high concurrency test, for both IO bandwidth
>>     and cpu usage.
> 
> As explained in the commit message, this is done because
> min_shallow_depth must be less than or equal to shallow_depth.
> Additionally, mq-deadline is not the only I/O scheduler that sets
> min_shallow_depth to 1. BFQ does this too.

No, BFQ is totally different, one task from bfq can be limited to just
one request, due to the cgroup policy of bfq.
> 
>> 2) async_depth is nr_requests, hence shallow_depth will always set to
>>     1 << bt->sb.shift. For consequence, no tag can be reserved.
> 
> This is not correct. dd->async_depth can be modified via sysfs.

So, I'm trying to understand, there are two cases:

1) the default value of async_depth is nr_requests, and no tag can be
reserved, right? Do we want to fix this?
2) User must change async_depth to a lower value to make it work.

Now, I understand why you want to change min_shallow_depth to 1.
However, I think we should also set min_shallow_depth while writing
sysfs as well.

> 
> Bart.
> .
> 

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

[Yu Kuai]

Hi,

在 2024/12/10 2:02, Bart Van Assche 写道:
> This is not correct. dd->async_depth can be modified via sysfs.

How about the following patch to fix min_shallow_depth for deadline?

Thanks,
Kuai

diff --git a/block/mq-deadline.c b/block/mq-deadline.c
index a9cf8e19f9d1..040ebb0b192d 100644
--- a/block/mq-deadline.c
+++ b/block/mq-deadline.c
@@ -667,8 +667,7 @@ static void dd_depth_updated(struct blk_mq_hw_ctx *hctx)
         struct blk_mq_tags *tags = hctx->sched_tags;

         dd->async_depth = q->nr_requests;
-
-       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(). */
@@ -1012,6 +1011,47 @@ SHOW_INT(deadline_fifo_batch_show, dd->fifo_batch);
  #undef SHOW_INT
  #undef SHOW_JIFFIES

+static ssize_t deadline_async_depth_store(struct elevator_queue *e,
+                                         const char *page, size_t count)
+{
+       struct deadline_data *dd = e->elevator_data;
+       struct request_queue *q = dd->q;
+       struct blk_mq_hw_ctx *hctx;
+       unsigned long i;
+       int v;
+       int ret = kstrtoint(page, 0, &v);
+
+       if (ret < 0)
+               return ret;
+
+       if (v < 1)
+               v = 1;
+       else if (v > dd->q->nr_requests)
+               v = dd->q->nr_requests;
+
+       if (v == dd->async_depth)
+               return count;
+
+       blk_mq_freeze_queue(q);
+       blk_mq_quiesce_queue(q);
+
+       dd->async_depth = v;
+       if (blk_mq_is_shared_tags(q->tag_set->flags)) {
+               sbitmap_queue_min_shallow_depth(
+                       &q->sched_shared_tags->bitmap_tags, 
dd->async_depth);
+       } else {
+               queue_for_each_hw_ctx(q, hctx, i)
+                       sbitmap_queue_min_shallow_depth(
+                               &hctx->sched_tags->bitmap_tags,
+                               dd->async_depth);
+       }
+
+       blk_mq_unquiesce_queue(q);
+       blk_mq_unfreeze_queue(q);
+
+       return count;
+}
+
  #define STORE_FUNCTION(__FUNC, __PTR, MIN, MAX, __CONV) 
         \
  static ssize_t __FUNC(struct elevator_queue *e, const char *page, 
size_t count)        \
  {                                                                      \
@@ -1037,7 +1077,6 @@ 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_fifo_batch_store, &dd->fifo_batch, 0, INT_MAX);
  #undef STORE_FUNCTION
  #undef STORE_INT

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

[Yu Kuai]

Hi,

在 2024/12/10 9:50, Yu Kuai 写道:
> Hi,
> 
> 在 2024/12/10 2:02, Bart Van Assche 写道:
>> This is not correct. dd->async_depth can be modified via sysfs.
> 
> How about the following patch to fix min_shallow_depth for deadline?
> 
> Thanks,
> Kuai
> 
> diff --git a/block/mq-deadline.c b/block/mq-deadline.c
> index a9cf8e19f9d1..040ebb0b192d 100644
> --- a/block/mq-deadline.c
> +++ b/block/mq-deadline.c
> @@ -667,8 +667,7 @@ static void dd_depth_updated(struct blk_mq_hw_ctx 
> *hctx)
>          struct blk_mq_tags *tags = hctx->sched_tags;
> 
>          dd->async_depth = q->nr_requests;
> -
> -       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(). */
> @@ -1012,6 +1011,47 @@ SHOW_INT(deadline_fifo_batch_show, dd->fifo_batch);
>   #undef SHOW_INT
>   #undef SHOW_JIFFIES
> 
> +static ssize_t deadline_async_depth_store(struct elevator_queue *e,
> +                                         const char *page, size_t count)
> +{
> +       struct deadline_data *dd = e->elevator_data;
> +       struct request_queue *q = dd->q;
> +       struct blk_mq_hw_ctx *hctx;
> +       unsigned long i;
> +       int v;
> +       int ret = kstrtoint(page, 0, &v);
> +
> +       if (ret < 0)
> +               return ret;
> +
> +       if (v < 1)
> +               v = 1;
> +       else if (v > dd->q->nr_requests)
> +               v = dd->q->nr_requests;
> +
> +       if (v == dd->async_depth)
> +               return count;
> +
> +       blk_mq_freeze_queue(q);
> +       blk_mq_quiesce_queue(q);
> +
> +       dd->async_depth = v;
> +       if (blk_mq_is_shared_tags(q->tag_set->flags)) {
> +               sbitmap_queue_min_shallow_depth(
> +                       &q->sched_shared_tags->bitmap_tags, 
> dd->async_depth);
> +       } else {
> +               queue_for_each_hw_ctx(q, hctx, i)
> +                       sbitmap_queue_min_shallow_depth(
> +                               &hctx->sched_tags->bitmap_tags,
> +                               dd->async_depth);
> +       }

Just realized that this is not ok, q->sysfs_lock must be held to protect
changing hctx, however, the lock ordering is q->sysfs_lock before
eq->sysfs_lock, and this context already hold eq->sysfs_lock.

First of all, are we in the agreement that it's not acceptable to
sacrifice performance in the default scenario just to make sure
functional correctness if async_depth is set to 1?

If so, following are the options that I can think of to fix this:

1) make async_depth read-only, if 75% tags will hurt performance in some
cases, user can increase nr_requests to prevent it.
2) refactor elevator sysfs api, remove eq->sysfs_lock and replace it
with q->sysfs_lock, so deadline_async_depth_store() will be protected
against changing hctxs, and min_shallow_depth can be updated here.
3) other options?

Thanks,
Kuai

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

[Bart Van Assche]

On 12/9/24 10:22 PM, Yu Kuai wrote:
> First of all, are we in the agreement that it's not acceptable to
> sacrifice performance in the default scenario just to make sure
> functional correctness if async_depth is set to 1?

How much does this affect performance? If this affects performance
significantly I agree that this needs to be fixed.

> If so, following are the options that I can think of to fix this:
> 
> 1) make async_depth read-only, if 75% tags will hurt performance in some
> cases, user can increase nr_requests to prevent it.
> 2) refactor elevator sysfs api, remove eq->sysfs_lock and replace it
> with q->sysfs_lock, so deadline_async_depth_store() will be protected
> against changing hctxs, and min_shallow_depth can be updated here.
> 3) other options?

Another option is to remove the ability to configure async_depth. If it
is too much trouble to get the implementation right without causing
regressions for existing workloads, one possibility is to remove support
for restricting the number of asynchronous requests in flight.

Thanks,

Bart.

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

[Zhiguo Niu]

Bart Van Assche <bvanassche@acm.org> 于2024年12月11日周三 04:33写道：
>
> On 12/9/24 10:22 PM, Yu Kuai wrote:
> > First of all, are we in the agreement that it's not acceptable to
> > sacrifice performance in the default scenario just to make sure
> > functional correctness if async_depth is set to 1?
>
> How much does this affect performance? If this affects performance
> significantly I agree that this needs to be fixed.
>
> > If so, following are the options that I can think of to fix this:
> >
> > 1) make async_depth read-only, if 75% tags will hurt performance in some
> > cases, user can increase nr_requests to prevent it.
> > 2) refactor elevator sysfs api, remove eq->sysfs_lock and replace it
> > with q->sysfs_lock, so deadline_async_depth_store() will be protected
> > against changing hctxs, and min_shallow_depth can be updated here.
> > 3) other options?
>
> Another option is to remove the ability to configure async_depth. If it
> is too much trouble to get the implementation right without causing
> regressions for existing workloads, one possibility is to remove support
> for restricting the number of asynchronous requests in flight.
Hi Bart,
I think it is very useful to restrict asynchronous requests when IO
loading is very heavy by aysnc_depth.
the following is my androidbench experiment in android device(sched_tag=128):
1. setting heavy IO
while true; do fio -directory=/data -direct=0 -rw=write -bs=64M
-size=1G -numjobs=5 -name=fiotest
2. run androidbench  and results：
                orignial async_depth
async_depth=nr_requests*3/4      delta
seq read             33.176                                216.49
                      183.314
seq write             28.57                                  62.152
                         33.582
radom read         1.518                                  1.648
                        0.13
radom write         3.546                                  4.27
                          0.724
and our customer also feedback there is optimization when they test
APP cold start and benchmark after tunning async_depth.
thanks！
>
> Thanks,
>
> Bart.
>

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

[Yu Kuai]

Hi,

在 2024/12/11 10:38, Zhiguo Niu 写道:
> Bart Van Assche <bvanassche@acm.org> 于2024年12月11日周三 04:33写道：
>>
>> On 12/9/24 10:22 PM, Yu Kuai wrote:
>>> First of all, are we in the agreement that it's not acceptable to
>>> sacrifice performance in the default scenario just to make sure
>>> functional correctness if async_depth is set to 1?
>>
>> How much does this affect performance? If this affects performance
>> significantly I agree that this needs to be fixed.
>>
>>> If so, following are the options that I can think of to fix this:
>>>
>>> 1) make async_depth read-only, if 75% tags will hurt performance in some
>>> cases, user can increase nr_requests to prevent it.
>>> 2) refactor elevator sysfs api, remove eq->sysfs_lock and replace it
>>> with q->sysfs_lock, so deadline_async_depth_store() will be protected
>>> against changing hctxs, and min_shallow_depth can be updated here.
>>> 3) other options?
>>
>> Another option is to remove the ability to configure async_depth. If it
>> is too much trouble to get the implementation right without causing
>> regressions for existing workloads, one possibility is to remove support
>> for restricting the number of asynchronous requests in flight.
> Hi Bart,
> I think it is very useful to restrict asynchronous requests when IO
> loading is very heavy by aysnc_depth.
> the following is my androidbench experiment in android device(sched_tag=128):
> 1. setting heavy IO
> while true; do fio -directory=/data -direct=0 -rw=write -bs=64M
> -size=1G -numjobs=5 -name=fiotest
> 2. run androidbench  and results：
>                  orignial async_depth
> async_depth=nr_requests*3/4      delta
> seq read             33.176                                216.49
>                        183.314
> seq write             28.57                                  62.152
>                           33.582
> radom read         1.518                                  1.648
>                          0.13
> radom write         3.546                                  4.27
>                            0.724
> and our customer also feedback there is optimization when they test
> APP cold start and benchmark after tunning async_depth.

So do you guys writing async_depth? Looks like you're using
nr_requests*3/4. If this is the case, the above option 1) is still
working for you guys. However, in this test, I think the lower
async_depth is, the better result you'll get.

Thanks,
Kuai


> thanks！
>>
>> Thanks,
>>
>> Bart.
>>
> .
> 

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

[Zhiguo Niu]

Yu Kuai <yukuai1@huaweicloud.com> 于2024年12月11日周三 10:58写道：
>
> Hi,
>
> 在 2024/12/11 10:38, Zhiguo Niu 写道:
> > Bart Van Assche <bvanassche@acm.org> 于2024年12月11日周三 04:33写道：
> >>
> >> On 12/9/24 10:22 PM, Yu Kuai wrote:
> >>> First of all, are we in the agreement that it's not acceptable to
> >>> sacrifice performance in the default scenario just to make sure
> >>> functional correctness if async_depth is set to 1?
> >>
> >> How much does this affect performance? If this affects performance
> >> significantly I agree that this needs to be fixed.
> >>
> >>> If so, following are the options that I can think of to fix this:
> >>>
> >>> 1) make async_depth read-only, if 75% tags will hurt performance in some
> >>> cases, user can increase nr_requests to prevent it.
> >>> 2) refactor elevator sysfs api, remove eq->sysfs_lock and replace it
> >>> with q->sysfs_lock, so deadline_async_depth_store() will be protected
> >>> against changing hctxs, and min_shallow_depth can be updated here.
> >>> 3) other options?
> >>
> >> Another option is to remove the ability to configure async_depth. If it
> >> is too much trouble to get the implementation right without causing
> >> regressions for existing workloads, one possibility is to remove support
> >> for restricting the number of asynchronous requests in flight.
> > Hi Bart,
> > I think it is very useful to restrict asynchronous requests when IO
> > loading is very heavy by aysnc_depth.
> > the following is my androidbench experiment in android device(sched_tag=128):
> > 1. setting heavy IO
> > while true; do fio -directory=/data -direct=0 -rw=write -bs=64M
> > -size=1G -numjobs=5 -name=fiotest
> > 2. run androidbench  and results：
> >                  orignial async_depth
> > async_depth=nr_requests*3/4      delta
> > seq read             33.176                                216.49
> >                        183.314
> > seq write             28.57                                  62.152
> >                           33.582
> > radom read         1.518                                  1.648
> >                          0.13
> > radom write         3.546                                  4.27
> >                            0.724
> > and our customer also feedback there is optimization when they test
> > APP cold start and benchmark after tunning async_depth.
>
> So do you guys writing async_depth? Looks like you're using
> nr_requests*3/4. If this is the case, the above option 1) is still
> working for you guys. However, in this test, I think the lower
> async_depth is, the better result you'll get.
Hi Kuai,
yes, we modify async_depth to nr_reqeusts*3/4 by sysfs.
thanks!
>
> Thanks,
> Kuai
>
>
> > thanks！
> >>
> >> Thanks,
> >>
> >> Bart.
> >>
> > .
> >
>
>

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

[Yu Kuai]

Hi,

在 2024/12/11 4:33, Bart Van Assche 写道:
> How much does this affect performance? If this affects performance
> significantly I agree that this needs to be fixed.

We are testing megaraid-sas, with 24 jobs * 1024 iodepth, for randread
and randrw tests, v5.10 is about 20% better than v6.6.

I verified that just set wake_batch from 1 back to 8 can fix this.

Thanks,
Kuai

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

[Yu Kuai]

Hi, Bart

在 2024/12/11 4:33, Bart Van Assche 写道:
>> If so, following are the options that I can think of to fix this:
>>
>> 1) make async_depth read-only, if 75% tags will hurt performance in some
>> cases, user can increase nr_requests to prevent it.
>> 2) refactor elevator sysfs api, remove eq->sysfs_lock and replace it
>> with q->sysfs_lock, so deadline_async_depth_store() will be protected
>> against changing hctxs, and min_shallow_depth can be updated here.
>> 3) other options?
> 
> Another option is to remove the ability to configure async_depth. If it
> is too much trouble to get the implementation right without causing
> regressions for existing workloads, one possibility is to remove support
> for restricting the number of asynchronous requests in flight.

If you agree, I'll use following option in the next version:

4) set min_async_depth to 64 (after treating min_shallow_depth for the
whole sbitmap instead of one word).

The good thing is that user can still set async_depth without changing
wake_batch, the side effect is that async_depth can't be used if
nr_requests <= 64;

Thanks,
Kuai

[PATCH RFC 2/3] lib/sbitmap: don't export sbitmap_get_shallow()

[Yu Kuai]

From: Yu Kuai <yukuai3@huawei.com>

Because it's only used inside sbitmap.c.

Signed-off-by: Yu Kuai <yukuai3@huawei.com>
---
 block/kyber-iosched.c   |  2 +-
 include/linux/sbitmap.h | 17 -----------------
 lib/sbitmap.c           |  3 +--
 3 files changed, 2 insertions(+), 20 deletions(-)

diff --git a/block/kyber-iosched.c b/block/kyber-iosched.c
index 4155594aefc6..2cb579b288e1 100644
--- a/block/kyber-iosched.c
+++ b/block/kyber-iosched.c
@@ -159,7 +159,7 @@ struct kyber_queue_data {
 
 	/*
 	 * Async request percentage, converted to per-word depth for
-	 * sbitmap_get_shallow().
+	 * sbitmap_queue_get_shallow().
 	 */
 	unsigned int async_depth;
 
diff --git a/include/linux/sbitmap.h b/include/linux/sbitmap.h
index 189140bf11fc..e1730f5fdf9c 100644
--- a/include/linux/sbitmap.h
+++ b/include/linux/sbitmap.h
@@ -209,23 +209,6 @@ void sbitmap_resize(struct sbitmap *sb, unsigned int depth);
  */
 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.
- *
- * This rather specific operation allows for having multiple users with
- * different allocation limits. E.g., there can be a high-priority class that
- * uses sbitmap_get() and a low-priority class that uses sbitmap_get_shallow()
- * with a @shallow_depth of (1 << (@sb->shift - 1)). Then, the low-priority
- * class can only allocate half of the total bits in the bitmap, preventing it
- * from starving out the high-priority class.
- *
- * Return: Non-negative allocated bit number if successful, -1 otherwise.
- */
-int sbitmap_get_shallow(struct sbitmap *sb, unsigned long shallow_depth);
-
 /**
  * sbitmap_any_bit_set() - Check for a set bit in a &struct sbitmap.
  * @sb: Bitmap to check.
diff --git a/lib/sbitmap.c b/lib/sbitmap.c
index d3412984170c..9d4213ce7916 100644
--- a/lib/sbitmap.c
+++ b/lib/sbitmap.c
@@ -287,7 +287,7 @@ static int __sbitmap_get_shallow(struct sbitmap *sb,
 	return sbitmap_find_bit(sb, shallow_depth, index, alloc_hint, true);
 }
 
-int sbitmap_get_shallow(struct sbitmap *sb, unsigned long shallow_depth)
+static int sbitmap_get_shallow(struct sbitmap *sb, unsigned long shallow_depth)
 {
 	int nr;
 	unsigned int hint, depth;
@@ -302,7 +302,6 @@ int sbitmap_get_shallow(struct sbitmap *sb, unsigned long shallow_depth)
 
 	return nr;
 }
-EXPORT_SYMBOL_GPL(sbitmap_get_shallow);
 
 bool sbitmap_any_bit_set(const struct sbitmap *sb)
 {
-- 
2.39.2

Re: [PATCH RFC 2/3] lib/sbitmap: don't export sbitmap_get_shallow()

[Bart Van Assche]

On 12/9/24 7:55 PM, Yu Kuai wrote:
> -/**
> - * 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.
> - *
> - * This rather specific operation allows for having multiple users with
> - * different allocation limits. E.g., there can be a high-priority class that
> - * uses sbitmap_get() and a low-priority class that uses sbitmap_get_shallow()
> - * with a @shallow_depth of (1 << (@sb->shift - 1)). Then, the low-priority
> - * class can only allocate half of the total bits in the bitmap, preventing it
> - * from starving out the high-priority class.
> - *
> - * Return: Non-negative allocated bit number if successful, -1 otherwise.
> - */
> -int sbitmap_get_shallow(struct sbitmap *sb, unsigned long shallow_depth);

Please retain the above comment block by moving it into lib/sbitmap.c.

Thanks,

Bart.

Re: [PATCH RFC 2/3] lib/sbitmap: don't export sbitmap_get_shallow()

[Yu Kuai]

Hi,

在 2024/12/10 2:05, Bart Van Assche 写道:
> On 12/9/24 7:55 PM, Yu Kuai wrote:
>> -/**
>> - * 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.
>> - *
>> - * This rather specific operation allows for having multiple users with
>> - * different allocation limits. E.g., there can be a high-priority 
>> class that
>> - * uses sbitmap_get() and a low-priority class that uses 
>> sbitmap_get_shallow()
>> - * with a @shallow_depth of (1 << (@sb->shift - 1)). Then, the 
>> low-priority
>> - * class can only allocate half of the total bits in the bitmap, 
>> preventing it
>> - * from starving out the high-priority class.
>> - *
>> - * Return: Non-negative allocated bit number if successful, -1 
>> otherwise.
>> - */
>> -int sbitmap_get_shallow(struct sbitmap *sb, unsigned long 
>> shallow_depth);
> 
> Please retain the above comment block by moving it into lib/sbitmap.c.
> 

Since the comment must be updated after patch 3, I'll apply the last
patch and update comment first, and do this cleanup at last.

Thanks,
Kuai

> Thanks,
> 
> Bart.
> .
> 

[PATCH RFC 3/3] 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 treate 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 how many
bits are available in the last 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 |  2 +-
 lib/sbitmap.c           | 31 +++++++++++++++++++++++++------
 2 files changed, 26 insertions(+), 7 deletions(-)

diff --git a/include/linux/sbitmap.h b/include/linux/sbitmap.h
index e1730f5fdf9c..ffb9907c7070 100644
--- a/include/linux/sbitmap.h
+++ b/include/linux/sbitmap.h
@@ -461,7 +461,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 9d4213ce7916..13831c7536a3 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;
-- 
2.39.2

Re: [PATCH RFC 3/3] lib/sbitmap: fix shallow_depth tag allocation

[Bart Van Assche]

On 12/9/24 7:55 PM, Yu Kuai wrote:
> 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 treate 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.

treate -> treats

The above text is incorrect. I have verified that shallow_depth 
restricts the queue depth of asynchronous requests for mq-deadline if it
is reduced from its default value. The function dd_word_to_depth() in
mq-deadline converts the value written into the sysfs attribute into a
value that is appropriate for the sbitmap implementation.

That being said, it seems like a good idea to me to modify how the
sbitmap code interprets 'shallow_depth'.

Thanks,

Bart.

Re: [PATCH RFC 3/3] lib/sbitmap: fix shallow_depth tag allocation

[Yu Kuai]

Hi,

在 2024/12/10 2:11, Bart Van Assche 写道:
> On 12/9/24 7:55 PM, Yu Kuai wrote:
>> 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 treate 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.
> 
> treate -> treats
> 
> The above text is incorrect. I have verified that shallow_depth 
> restricts the queue depth of asynchronous requests for mq-deadline if it
> is reduced from its default value. The function dd_word_to_depth() in
> mq-deadline converts the value written into the sysfs attribute into a
> value that is appropriate for the sbitmap implementation.

Hi,

please notice that patch 1 is reverted in this set, which means
dd_word_to_depth() is not existed. :)

And for patch 1, dd_word_to_depth() doesn't(and can't) handle the last
word, for the case that avaliable bits in the last word is less than
1 << sb->shift. So, in fact it's not convert to the appropriate value.

> 
> That being said, it seems like a good idea to me to modify how the
> sbitmap code interprets 'shallow_depth'.

Good to know!

Thanks,
Kuai

> 
> Thanks,
> 
> Bart.
> .
>