[PATCH RESEND v2 0/5] A few bugfix and cleanup patches for sbitmap

[PATCH RESEND v2 0/5] A few bugfix and cleanup patches for sbitmap

[Kemeng Shi]

Hi, this series contain a bugfix patch to correct wake_batch
recalculation to avoid potential IO hung and a few cleanup patches to
remove unnecessary check and repeat code in sbitmap. Thanks.

---
v2:
 -add patch "sbitmap: correct wake_batch recalculation to avoid potential
IO hung"
---

Kemeng Shi (5):
  sbitmap: remove unnecessary calculation of alloc_hint in
    __sbitmap_get_shallow
  sbitmap: remove redundant check in __sbitmap_queue_get_batch
  sbitmap: rewrite sbitmap_find_bit_in_index to reduce repeat code
  sbitmap: add sbitmap_find_bit to remove repeat code in
    __sbitmap_get/__sbitmap_get_shallow
  sbitmap: correct wake_batch recalculation to avoid potential IO hung

 lib/sbitmap.c | 103 ++++++++++++++++++++++----------------------------
 1 file changed, 46 insertions(+), 57 deletions(-)

-- 
2.30.0

[PATCH RESEND v2 1/5] sbitmap: remove unnecessary calculation of alloc_hint in __sbitmap_get_shallow

[Kemeng Shi]

We calculate allow_hint in next word as following:

/* low sb->shift bit of alloc_hint will be 0 after this shift */
alloc_hint = index << sb->shift;

/* get low sb->shift bit of alloc_hit */
SB_NR_TO_BIT(sb, alloc_hint)

So alloc_hit in next word will always be zero. Simpfy alloc_hit calculation
in __sbitmap_get_shallow according to the alloc_hit calculation in
__sbitmap_get.

Signed-off-by: Kemeng Shi <shikemeng@huaweicloud.com>
---
 lib/sbitmap.c | 11 ++++-------
 1 file changed, 4 insertions(+), 7 deletions(-)

diff --git a/lib/sbitmap.c b/lib/sbitmap.c
index 586deb333237..cb5e03a2d65b 100644
--- a/lib/sbitmap.c
+++ b/lib/sbitmap.c
@@ -243,6 +243,7 @@ static int __sbitmap_get_shallow(struct sbitmap *sb,
 	int nr = -1;
 
 	index = SB_NR_TO_INDEX(sb, alloc_hint);
+	alloc_hint = SB_NR_TO_BIT(sb, alloc_hint);
 
 	for (i = 0; i < sb->map_nr; i++) {
 again:
@@ -250,7 +251,7 @@ static int __sbitmap_get_shallow(struct sbitmap *sb,
 					min_t(unsigned int,
 					      __map_depth(sb, index),
 					      shallow_depth),
-					SB_NR_TO_BIT(sb, alloc_hint), true);
+					alloc_hint, true);
 		if (nr != -1) {
 			nr += index << sb->shift;
 			break;
@@ -260,13 +261,9 @@ static int __sbitmap_get_shallow(struct sbitmap *sb,
 			goto again;
 
 		/* Jump to next index. */
-		index++;
-		alloc_hint = index << sb->shift;
-
-		if (index >= sb->map_nr) {
+		alloc_hint = 0;
+		if (++index >= sb->map_nr)
 			index = 0;
-			alloc_hint = 0;
-		}
 	}
 
 	return nr;
-- 
2.30.0

Re: [PATCH RESEND v2 1/5] sbitmap: remove unnecessary calculation of alloc_hint in __sbitmap_get_shallow

[Jan Kara]

On Thu 22-12-22 22:33:49, Kemeng Shi wrote:
> We calculate allow_hint in next word as following:
> 
> /* low sb->shift bit of alloc_hint will be 0 after this shift */
> alloc_hint = index << sb->shift;
> 
> /* get low sb->shift bit of alloc_hit */
> SB_NR_TO_BIT(sb, alloc_hint)
> 
> So alloc_hit in next word will always be zero. Simpfy alloc_hit calculation
> in __sbitmap_get_shallow according to the alloc_hit calculation in
> __sbitmap_get.
> 
> Signed-off-by: Kemeng Shi <shikemeng@huaweicloud.com>

Looks good to me, nice cleanup. I'd just somewhat rephrase the changelog
to:

Updates to alloc_hint in the loop in __sbitmap_get_shallow() are mostly
pointless and equivalent to setting alloc_hint to zero (because
SB_NR_TO_BIT() considers only low sb->shift bits from alloc_hint). So
simplify the logic.

Anyway, feel free to add:

Reviewed-by: Jan Kara <jack@suse.cz>

								Honza

> ---
>  lib/sbitmap.c | 11 ++++-------
>  1 file changed, 4 insertions(+), 7 deletions(-)
> 
> diff --git a/lib/sbitmap.c b/lib/sbitmap.c
> index 586deb333237..cb5e03a2d65b 100644
> --- a/lib/sbitmap.c
> +++ b/lib/sbitmap.c
> @@ -243,6 +243,7 @@ static int __sbitmap_get_shallow(struct sbitmap *sb,
>  	int nr = -1;
>  
>  	index = SB_NR_TO_INDEX(sb, alloc_hint);
> +	alloc_hint = SB_NR_TO_BIT(sb, alloc_hint);
>  
>  	for (i = 0; i < sb->map_nr; i++) {
>  again:
> @@ -250,7 +251,7 @@ static int __sbitmap_get_shallow(struct sbitmap *sb,
>  					min_t(unsigned int,
>  					      __map_depth(sb, index),
>  					      shallow_depth),
> -					SB_NR_TO_BIT(sb, alloc_hint), true);
> +					alloc_hint, true);
>  		if (nr != -1) {
>  			nr += index << sb->shift;
>  			break;
> @@ -260,13 +261,9 @@ static int __sbitmap_get_shallow(struct sbitmap *sb,
>  			goto again;
>  
>  		/* Jump to next index. */
> -		index++;
> -		alloc_hint = index << sb->shift;
> -
> -		if (index >= sb->map_nr) {
> +		alloc_hint = 0;
> +		if (++index >= sb->map_nr)
>  			index = 0;
> -			alloc_hint = 0;
> -		}
>  	}
>  
>  	return nr;
> -- 
> 2.30.0
> 
-- 
Jan Kara <jack@suse.com>
SUSE Labs, CR

[PATCH RESEND v2 2/5] sbitmap: remove redundant check in __sbitmap_queue_get_batch

[Kemeng Shi]

Commit fbb564a557809 ("lib/sbitmap: Fix invalid loop in
__sbitmap_queue_get_batch()") mentioned that "Checking free bits when
setting the target bits. Otherwise, it may reuse the busying bits."
This commit add check to make sure all masked bits in word before
cmpxchg is zero. Then the existing check after cmpxchg to check any
zero bit is existing in masked bits in word is redundant.

Actually, old value of word before cmpxchg is stored in val and we
will filter out busy bits in val by "(get_mask & ~val)" after cmpxchg.
So we will not reuse busy bits methioned in commit fbb564a557809
("lib/sbitmap: Fix invalid loop in __sbitmap_queue_get_batch()"). Revert
new-added check to remove redundant check.

Signed-off-by: Kemeng Shi <shikemeng@huaweicloud.com>
---
 lib/sbitmap.c | 8 +++-----
 1 file changed, 3 insertions(+), 5 deletions(-)

diff --git a/lib/sbitmap.c b/lib/sbitmap.c
index cb5e03a2d65b..11e75f4040fb 100644
--- a/lib/sbitmap.c
+++ b/lib/sbitmap.c
@@ -518,11 +518,9 @@ unsigned long __sbitmap_queue_get_batch(struct sbitmap_queue *sbq, int nr_tags,
 
 			get_mask = ((1UL << nr_tags) - 1) << nr;
 			val = READ_ONCE(map->word);
-			do {
-				if ((val & ~get_mask) != val)
-					goto next;
-			} while (!atomic_long_try_cmpxchg(ptr, &val,
-							  get_mask | val));
+			while (!atomic_long_try_cmpxchg(ptr, &val,
+							  get_mask | val))
+				;
 			get_mask = (get_mask & ~val) >> nr;
 			if (get_mask) {
 				*offset = nr + (index << sb->shift);
-- 
2.30.0

Re: [PATCH RESEND v2 2/5] sbitmap: remove redundant check in __sbitmap_queue_get_batch

[Jan Kara]

On Thu 22-12-22 22:33:50, Kemeng Shi wrote:
> Commit fbb564a557809 ("lib/sbitmap: Fix invalid loop in
> __sbitmap_queue_get_batch()") mentioned that "Checking free bits when
> setting the target bits. Otherwise, it may reuse the busying bits."
> This commit add check to make sure all masked bits in word before
> cmpxchg is zero. Then the existing check after cmpxchg to check any
> zero bit is existing in masked bits in word is redundant.
> 
> Actually, old value of word before cmpxchg is stored in val and we
> will filter out busy bits in val by "(get_mask & ~val)" after cmpxchg.
> So we will not reuse busy bits methioned in commit fbb564a557809
> ("lib/sbitmap: Fix invalid loop in __sbitmap_queue_get_batch()"). Revert
> new-added check to remove redundant check.
> 
> Signed-off-by: Kemeng Shi <shikemeng@huaweicloud.com>

...

> diff --git a/lib/sbitmap.c b/lib/sbitmap.c
> index cb5e03a2d65b..11e75f4040fb 100644
> --- a/lib/sbitmap.c
> +++ b/lib/sbitmap.c
> @@ -518,11 +518,9 @@ unsigned long __sbitmap_queue_get_batch(struct sbitmap_queue *sbq, int nr_tags,
>  
>  			get_mask = ((1UL << nr_tags) - 1) << nr;
>  			val = READ_ONCE(map->word);
> -			do {
> -				if ((val & ~get_mask) != val)
> -					goto next;
> -			} while (!atomic_long_try_cmpxchg(ptr, &val,
> -							  get_mask | val));
> +			while (!atomic_long_try_cmpxchg(ptr, &val,
> +							  get_mask | val))
> +				;
>  			get_mask = (get_mask & ~val) >> nr;
>  			if (get_mask) {
>  				*offset = nr + (index << sb->shift);

So I agree this will result in correct behavior but it can change
performance. In the original code, we end up doing
atomic_long_try_cmpxchg() only for words where we have a chance of getting
all tags allocated. Now we just accept any word where we could allocate at
least one bit. Frankly the original code looks rather restrictive and also
the fact that we look only from the first zero bit in the word looks
unnecessarily restrictive so maybe I miss some details about what's
expected from __sbitmap_queue_get_batch(). So all in all I wanted to point
out this needs more scrutiny from someone understanding better expectations
from __sbitmap_queue_get_batch().

								Honza
-- 
Jan Kara <jack@suse.com>
SUSE Labs, CR

Re: [PATCH RESEND v2 2/5] sbitmap: remove redundant check in __sbitmap_queue_get_batch

[Kemeng Shi]

Hi Jan, thanks for review.
on 12/22/2022 7:23 PM, Jan Kara wrote:
>> diff --git a/lib/sbitmap.c b/lib/sbitmap.c
>> index cb5e03a2d65b..11e75f4040fb 100644
>> --- a/lib/sbitmap.c
>> +++ b/lib/sbitmap.c
>> @@ -518,11 +518,9 @@ unsigned long __sbitmap_queue_get_batch(struct sbitmap_queue *sbq, int nr_tags,
>>  
>>  			get_mask = ((1UL << nr_tags) - 1) << nr;
>>  			val = READ_ONCE(map->word);
>> -			do {
>> -				if ((val & ~get_mask) != val)
>> -					goto next;
>> -			} while (!atomic_long_try_cmpxchg(ptr, &val,
>> -							  get_mask | val));
>> +			while (!atomic_long_try_cmpxchg(ptr, &val,
>> +							  get_mask | val))
>> +				;
>>  			get_mask = (get_mask & ~val) >> nr;
>>  			if (get_mask) {
>>  				*offset = nr + (index << sb->shift);
> 
> So I agree this will result in correct behavior but it can change
> performance. In the original code, we end up doing
> atomic_long_try_cmpxchg() only for words where we have a chance of getting
> all tags allocated. Now we just accept any word where we could allocate at
> least one bit. Frankly the original code looks rather restrictive and also
> the fact that we look only from the first zero bit in the word looks
> unnecessarily restrictive so maybe I miss some details about what's
> expected from __sbitmap_queue_get_batch(). So all in all I wanted to point
> out this needs more scrutiny from someone understanding better expectations
> from __sbitmap_queue_get_batch().
In the very beginning, __sbitmap_queue_get_batch will return if we only
get partial tags allocated. Recent commit fbb564a557809 ("lib/sbitmap: Fix
invalid loop in __sbitmap_queue_get_batch()") thought we may reuse busying
bits in old codes and change behavior of __sbitmap_queue_get_batch() to get
all tags. However we will not reuse busying bits in old codes actually. So
I try to revert this wrong fix and keep the behavior of
__sbitmap_queue_get_batch() as it designed to be at beginning.

Besides, if we keep to get all tags,the check below is redundant.
	get_mask = (get_mask & ~ret) >> nr;
	if (get_mask) {
		...
	}
As we only reach here if we get all tags and the check above will always
pass. So this check in old codes should be removed.

-- 
Best wishes
Kemeng Shi

Re: [PATCH RESEND v2 2/5] sbitmap: remove redundant check in __sbitmap_queue_get_batch

[Jan Kara]

[Added to CC original author of the problematic commit and reviewer]

On Thu 22-12-22 19:49:12, Kemeng Shi wrote:
> Hi Jan, thanks for review.
> on 12/22/2022 7:23 PM, Jan Kara wrote:
> >> diff --git a/lib/sbitmap.c b/lib/sbitmap.c
> >> index cb5e03a2d65b..11e75f4040fb 100644
> >> --- a/lib/sbitmap.c
> >> +++ b/lib/sbitmap.c
> >> @@ -518,11 +518,9 @@ unsigned long __sbitmap_queue_get_batch(struct sbitmap_queue *sbq, int nr_tags,
> >>  
> >>  			get_mask = ((1UL << nr_tags) - 1) << nr;
> >>  			val = READ_ONCE(map->word);
> >> -			do {
> >> -				if ((val & ~get_mask) != val)
> >> -					goto next;
> >> -			} while (!atomic_long_try_cmpxchg(ptr, &val,
> >> -							  get_mask | val));
> >> +			while (!atomic_long_try_cmpxchg(ptr, &val,
> >> +							  get_mask | val))
> >> +				;
> >>  			get_mask = (get_mask & ~val) >> nr;
> >>  			if (get_mask) {
> >>  				*offset = nr + (index << sb->shift);
> > 
> > So I agree this will result in correct behavior but it can change
> > performance. In the original code, we end up doing
> > atomic_long_try_cmpxchg() only for words where we have a chance of getting
> > all tags allocated. Now we just accept any word where we could allocate at
> > least one bit. Frankly the original code looks rather restrictive and also
> > the fact that we look only from the first zero bit in the word looks
> > unnecessarily restrictive so maybe I miss some details about what's
> > expected from __sbitmap_queue_get_batch(). So all in all I wanted to point
> > out this needs more scrutiny from someone understanding better expectations
> > from __sbitmap_queue_get_batch().
> In the very beginning, __sbitmap_queue_get_batch will return if we only
> get partial tags allocated. Recent commit fbb564a557809 ("lib/sbitmap: Fix
> invalid loop in __sbitmap_queue_get_batch()") thought we may reuse busying
> bits in old codes and change behavior of __sbitmap_queue_get_batch() to get
> all tags. However we will not reuse busying bits in old codes actually. So
> I try to revert this wrong fix and keep the behavior of
> __sbitmap_queue_get_batch() as it designed to be at beginning.

I see and now I agree. Please add tag:

Fixes: fbb564a557809 ("lib/sbitmap: Fix invalid loop in __sbitmap_queue_get_batch()") 

to your commit. Also feel free to add:

Reviewed-by: Jan Kara <jack@suse.cz>
 
> Besides, if we keep to get all tags,the check below is redundant.
> 	get_mask = (get_mask & ~ret) >> nr;
> 	if (get_mask) {
> 		...
> 	}
> As we only reach here if we get all tags and the check above will always
> pass. So this check in old codes should be removed.

Yeah, I agree.

								Honza

-- 
Jan Kara <jack@suse.com>
SUSE Labs, CR

[PATCH RESEND v2 3/5] sbitmap: rewrite sbitmap_find_bit_in_index to reduce repeat code

[Kemeng Shi]

Rewrite sbitmap_find_bit_in_index as following:
1. Rename sbitmap_find_bit_in_index to sbitmap_find_bit_in_word
2. Accept "struct sbitmap_word *" directly instead of accepting
"struct sbitmap *" and "int index" to get "struct sbitmap_word *".
3. Accept depth/shallow_depth and wrap for __sbitmap_get_word from caller
to support need of both __sbitmap_get_shallow and __sbitmap_get.

With helper function sbitmap_find_bit_in_word, we can remove repeat
code in __sbitmap_get_shallow to find bit considring deferred clear.

Signed-off-by: Kemeng Shi <shikemeng@huaweicloud.com>
---
 lib/sbitmap.c | 29 ++++++++++++++---------------
 1 file changed, 14 insertions(+), 15 deletions(-)

diff --git a/lib/sbitmap.c b/lib/sbitmap.c
index 11e75f4040fb..3f7e276a427d 100644
--- a/lib/sbitmap.c
+++ b/lib/sbitmap.c
@@ -167,15 +167,16 @@ static int __sbitmap_get_word(unsigned long *word, unsigned long depth,
 	return nr;
 }
 
-static int sbitmap_find_bit_in_index(struct sbitmap *sb, int index,
-				     unsigned int alloc_hint)
+static int sbitmap_find_bit_in_word(struct sbitmap_word *map,
+				    unsigned int depth,
+				    unsigned int alloc_hint,
+				    bool wrap)
 {
-	struct sbitmap_word *map = &sb->map[index];
 	int nr;
 
 	do {
-		nr = __sbitmap_get_word(&map->word, __map_depth(sb, index),
-					alloc_hint, !sb->round_robin);
+		nr = __sbitmap_get_word(&map->word, depth,
+					alloc_hint, wrap);
 		if (nr != -1)
 			break;
 		if (!sbitmap_deferred_clear(map))
@@ -203,7 +204,8 @@ static int __sbitmap_get(struct sbitmap *sb, unsigned int alloc_hint)
 		alloc_hint = 0;
 
 	for (i = 0; i < sb->map_nr; i++) {
-		nr = sbitmap_find_bit_in_index(sb, index, alloc_hint);
+		nr = sbitmap_find_bit_in_word(&sb->map[index], __map_depth(sb, index),
+					      alloc_hint, !sb->round_robin);
 		if (nr != -1) {
 			nr += index << sb->shift;
 			break;
@@ -246,20 +248,17 @@ static int __sbitmap_get_shallow(struct sbitmap *sb,
 	alloc_hint = SB_NR_TO_BIT(sb, alloc_hint);
 
 	for (i = 0; i < sb->map_nr; i++) {
-again:
-		nr = __sbitmap_get_word(&sb->map[index].word,
-					min_t(unsigned int,
-					      __map_depth(sb, index),
-					      shallow_depth),
-					alloc_hint, true);
+		nr = sbitmap_find_bit_in_word(&sb->map[index],
+					      min_t(unsigned int,
+						    __map_depth(sb, index),
+						    shallow_depth),
+					      alloc_hint, true);
+
 		if (nr != -1) {
 			nr += index << sb->shift;
 			break;
 		}
 
-		if (sbitmap_deferred_clear(&sb->map[index]))
-			goto again;
-
 		/* Jump to next index. */
 		alloc_hint = 0;
 		if (++index >= sb->map_nr)
-- 
2.30.0

Re: [PATCH RESEND v2 3/5] sbitmap: rewrite sbitmap_find_bit_in_index to reduce repeat code

[Jan Kara]

On Thu 22-12-22 22:33:51, Kemeng Shi wrote:
> Rewrite sbitmap_find_bit_in_index as following:
> 1. Rename sbitmap_find_bit_in_index to sbitmap_find_bit_in_word
> 2. Accept "struct sbitmap_word *" directly instead of accepting
> "struct sbitmap *" and "int index" to get "struct sbitmap_word *".
> 3. Accept depth/shallow_depth and wrap for __sbitmap_get_word from caller
> to support need of both __sbitmap_get_shallow and __sbitmap_get.
> 
> With helper function sbitmap_find_bit_in_word, we can remove repeat
> code in __sbitmap_get_shallow to find bit considring deferred clear.
> 
> Signed-off-by: Kemeng Shi <shikemeng@huaweicloud.com>
> ---
>  lib/sbitmap.c | 29 ++++++++++++++---------------
>  1 file changed, 14 insertions(+), 15 deletions(-)

Just one style nit below. Please fix that up. Otherwise feel free to add:

Reviewed-by: Jan Kara <jack@suse.cz>

> diff --git a/lib/sbitmap.c b/lib/sbitmap.c
> index 11e75f4040fb..3f7e276a427d 100644
> --- a/lib/sbitmap.c
> +++ b/lib/sbitmap.c
> @@ -167,15 +167,16 @@ static int __sbitmap_get_word(unsigned long *word, unsigned long depth,
>  	return nr;
>  }
>  
> -static int sbitmap_find_bit_in_index(struct sbitmap *sb, int index,
> -				     unsigned int alloc_hint)
> +static int sbitmap_find_bit_in_word(struct sbitmap_word *map,
> +				    unsigned int depth,
> +				    unsigned int alloc_hint,
> +				    bool wrap)
>  {
> -	struct sbitmap_word *map = &sb->map[index];
>  	int nr;
>  
>  	do {
> -		nr = __sbitmap_get_word(&map->word, __map_depth(sb, index),
> -					alloc_hint, !sb->round_robin);
> +		nr = __sbitmap_get_word(&map->word, depth,
> +					alloc_hint, wrap);
>  		if (nr != -1)
>  			break;
>  		if (!sbitmap_deferred_clear(map))
> @@ -203,7 +204,8 @@ static int __sbitmap_get(struct sbitmap *sb, unsigned int alloc_hint)
>  		alloc_hint = 0;
>  
>  	for (i = 0; i < sb->map_nr; i++) {
> -		nr = sbitmap_find_bit_in_index(sb, index, alloc_hint);
> +		nr = sbitmap_find_bit_in_word(&sb->map[index], __map_depth(sb, index),

Please avoid lines over 80 characters.

> +					      alloc_hint, !sb->round_robin);
>  		if (nr != -1) {
>  			nr += index << sb->shift;
>  			break;

								Honza
-- 
Jan Kara <jack@suse.com>
SUSE Labs, CR

[PATCH RESEND v2 4/5] sbitmap: add sbitmap_find_bit to remove repeat code in __sbitmap_get/__sbitmap_get_shallow

[Kemeng Shi]

There are three differences between __sbitmap_get and
__sbitmap_get_shallow when searching free bit:
1. __sbitmap_get_shallow limit number of bit to search per word.
__sbitmap_get has no such limit.
2. __sbitmap_get_shallow always searches with wrap set. __sbitmap_get set
wrap according to round_robin.
3. __sbitmap_get_shallow always searches from first bit in first word.
__sbitmap_get searches from first bit when round_robin is not set
otherwise searches from SB_NR_TO_BIT(sb, alloc_hint).

Add helper function sbitmap_find_bit function to do common search while
accept "limit depth per word", "wrap flag" and "first bit to
search" from caller to support the need of both __sbitmap_get and
__sbitmap_get_shallow.

Signed-off-by: Kemeng Shi <shikemeng@huaweicloud.com>
---
 lib/sbitmap.c | 72 +++++++++++++++++++++++++--------------------------
 1 file changed, 35 insertions(+), 37 deletions(-)

diff --git a/lib/sbitmap.c b/lib/sbitmap.c
index 3f7e276a427d..b6d3bb1c3675 100644
--- a/lib/sbitmap.c
+++ b/lib/sbitmap.c
@@ -186,26 +186,22 @@ static int sbitmap_find_bit_in_word(struct sbitmap_word *map,
 	return nr;
 }
 
-static int __sbitmap_get(struct sbitmap *sb, unsigned int alloc_hint)
+static int sbitmap_find_bit(struct sbitmap *sb,
+			    unsigned int depth,
+			    unsigned int index,
+			    unsigned int alloc_hint,
+			    bool wrap)
 {
-	unsigned int i, index;
+	unsigned int i;
 	int nr = -1;
 
-	index = SB_NR_TO_INDEX(sb, alloc_hint);
-
-	/*
-	 * Unless we're doing round robin tag allocation, just use the
-	 * alloc_hint to find the right word index. No point in looping
-	 * twice in find_next_zero_bit() for that case.
-	 */
-	if (sb->round_robin)
-		alloc_hint = SB_NR_TO_BIT(sb, alloc_hint);
-	else
-		alloc_hint = 0;
-
 	for (i = 0; i < sb->map_nr; i++) {
-		nr = sbitmap_find_bit_in_word(&sb->map[index], __map_depth(sb, index),
-					      alloc_hint, !sb->round_robin);
+		nr = sbitmap_find_bit_in_word(&sb->map[index],
+					      min_t(unsigned int,
+						    __map_depth(sb, index),
+						    depth),
+					      alloc_hint, wrap);
+
 		if (nr != -1) {
 			nr += index << sb->shift;
 			break;
@@ -215,11 +211,32 @@ static int __sbitmap_get(struct sbitmap *sb, unsigned int alloc_hint)
 		alloc_hint = 0;
 		if (++index >= sb->map_nr)
 			index = 0;
+
 	}
 
 	return nr;
 }
 
+static int __sbitmap_get(struct sbitmap *sb, unsigned int alloc_hint)
+{
+	unsigned int index;
+
+	index = SB_NR_TO_INDEX(sb, alloc_hint);
+
+	/*
+	 * Unless we're doing round robin tag allocation, just use the
+	 * alloc_hint to find the right word index. No point in looping
+	 * twice in find_next_zero_bit() for that case.
+	 */
+	if (sb->round_robin)
+		alloc_hint = SB_NR_TO_BIT(sb, alloc_hint);
+	else
+		alloc_hint = 0;
+
+	return sbitmap_find_bit(sb, UINT_MAX, index, alloc_hint,
+				!sb->round_robin);
+}
+
 int sbitmap_get(struct sbitmap *sb)
 {
 	int nr;
@@ -241,31 +258,12 @@ static int __sbitmap_get_shallow(struct sbitmap *sb,
 				 unsigned int alloc_hint,
 				 unsigned long shallow_depth)
 {
-	unsigned int i, index;
-	int nr = -1;
+	unsigned int index;
 
 	index = SB_NR_TO_INDEX(sb, alloc_hint);
 	alloc_hint = SB_NR_TO_BIT(sb, alloc_hint);
 
-	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),
-						    shallow_depth),
-					      alloc_hint, true);
-
-		if (nr != -1) {
-			nr += index << sb->shift;
-			break;
-		}
-
-		/* Jump to next index. */
-		alloc_hint = 0;
-		if (++index >= sb->map_nr)
-			index = 0;
-	}
-
-	return nr;
+	return sbitmap_find_bit(sb, shallow_depth, index, alloc_hint, true);
 }
 
 int sbitmap_get_shallow(struct sbitmap *sb, unsigned long shallow_depth)
-- 
2.30.0

Re: [PATCH RESEND v2 4/5] sbitmap: add sbitmap_find_bit to remove repeat code in __sbitmap_get/__sbitmap_get_shallow

[Jan Kara]

On Thu 22-12-22 22:33:52, Kemeng Shi wrote:
> There are three differences between __sbitmap_get and
> __sbitmap_get_shallow when searching free bit:
> 1. __sbitmap_get_shallow limit number of bit to search per word.
> __sbitmap_get has no such limit.
> 2. __sbitmap_get_shallow always searches with wrap set. __sbitmap_get set
> wrap according to round_robin.
> 3. __sbitmap_get_shallow always searches from first bit in first word.
> __sbitmap_get searches from first bit when round_robin is not set
> otherwise searches from SB_NR_TO_BIT(sb, alloc_hint).
> 
> Add helper function sbitmap_find_bit function to do common search while
> accept "limit depth per word", "wrap flag" and "first bit to
> search" from caller to support the need of both __sbitmap_get and
> __sbitmap_get_shallow.
> 
> Signed-off-by: Kemeng Shi <shikemeng@huaweicloud.com>

One style nit below, otherwise feel free to add:

Reviewed-by: Jan Kara <jack@suse.cz>


> @@ -215,11 +211,32 @@ static int __sbitmap_get(struct sbitmap *sb, unsigned int alloc_hint)
>  		alloc_hint = 0;
>  		if (++index >= sb->map_nr)
>  			index = 0;
> +
>  	}

Pointless empty line here...

								Honza
-- 
Jan Kara <jack@suse.com>
SUSE Labs, CR

[PATCH RESEND v2 5/5] sbitmap: correct wake_batch recalculation to avoid potential IO hung

[Kemeng Shi]

Commit 180dccb0dba4f ("blk-mq: fix tag_get wait task can't be awakened")
mentioned that in case of shared tags, there could be just one real
active hctx(queue) because of lazy detection of tag idle. Then driver tag
allocation may wait forever on this real active hctx(queue) if wake_batch
is > hctx_max_depth where hctx_max_depth is available tags depth for the
actve hctx(queue). However, the condition wake_batch > hctx_max_depth is
not strong enough to avoid IO hung as the sbitmap_queue_wake_up will only
wake up one wait queue for each wake_batch even though there is only one
waiter in the woken wait queue. After this, there is only one tag to free
and wake_batch may not be reached anymore. Commit 180dccb0dba4f ("blk-mq:
fix tag_get wait task can't be awakened") methioned that driver tag
allocation may wait forever. Actually, the inactive hctx(queue) will be
truely idle after at most 30 seconds and will call blk_mq_tag_wakeup_all
to wake one waiter per wait queue to break the hung. But IO hung for 30
seconds is also not acceptable. Set batch size to small enough that depth
of the shared hctx(queue) is enough to wake up all of the queues like
sbq_calc_wake_batch do to fix this potential IO hung.

Although hctx_max_depth will be clamped to at least 4 while wake_batch
recalculation does not do the clamp, the wake_batch will be always
recalculated to 1 when hctx_max_depth <= 4.

Fixes: 180dccb0dba4 ("blk-mq: fix tag_get wait task can't be awakened")
Signed-off-by: Kemeng Shi <shikemeng@huaweicloud.com>
---
 lib/sbitmap.c | 5 +----
 1 file changed, 1 insertion(+), 4 deletions(-)

diff --git a/lib/sbitmap.c b/lib/sbitmap.c
index b6d3bb1c3675..804fe99783e4 100644
--- a/lib/sbitmap.c
+++ b/lib/sbitmap.c
@@ -458,13 +458,10 @@ void sbitmap_queue_recalculate_wake_batch(struct sbitmap_queue *sbq,
 					    unsigned int users)
 {
 	unsigned int wake_batch;
-	unsigned int min_batch;
 	unsigned int depth = (sbq->sb.depth + users - 1) / users;
 
-	min_batch = sbq->sb.depth >= (4 * SBQ_WAIT_QUEUES) ? 4 : 1;
-
 	wake_batch = clamp_val(depth / SBQ_WAIT_QUEUES,
-			min_batch, SBQ_WAKE_BATCH);
+			1, SBQ_WAKE_BATCH);
 
 	WRITE_ONCE(sbq->wake_batch, wake_batch);
 }
-- 
2.30.0

Re: [PATCH RESEND v2 5/5] sbitmap: correct wake_batch recalculation to avoid potential IO hung

[Jan Kara]

On Thu 22-12-22 22:33:53, Kemeng Shi wrote:
> Commit 180dccb0dba4f ("blk-mq: fix tag_get wait task can't be awakened")
> mentioned that in case of shared tags, there could be just one real
> active hctx(queue) because of lazy detection of tag idle. Then driver tag
> allocation may wait forever on this real active hctx(queue) if wake_batch
> is > hctx_max_depth where hctx_max_depth is available tags depth for the
> actve hctx(queue). However, the condition wake_batch > hctx_max_depth is
> not strong enough to avoid IO hung as the sbitmap_queue_wake_up will only
> wake up one wait queue for each wake_batch even though there is only one
> waiter in the woken wait queue. After this, there is only one tag to free
> and wake_batch may not be reached anymore. Commit 180dccb0dba4f ("blk-mq:
> fix tag_get wait task can't be awakened") methioned that driver tag
> allocation may wait forever. Actually, the inactive hctx(queue) will be
> truely idle after at most 30 seconds and will call blk_mq_tag_wakeup_all
> to wake one waiter per wait queue to break the hung. But IO hung for 30
> seconds is also not acceptable. Set batch size to small enough that depth
> of the shared hctx(queue) is enough to wake up all of the queues like
> sbq_calc_wake_batch do to fix this potential IO hung.
> 
> Although hctx_max_depth will be clamped to at least 4 while wake_batch
> recalculation does not do the clamp, the wake_batch will be always
> recalculated to 1 when hctx_max_depth <= 4.
> 
> Fixes: 180dccb0dba4 ("blk-mq: fix tag_get wait task can't be awakened")
> Signed-off-by: Kemeng Shi <shikemeng@huaweicloud.com>

So the condition in sbitmap_queue_recalculate_wake_batch() also seemed
strange to me and the changelogs of commits 180dccb0dba4 and 10825410b95
("blk-mq: Fix wrong wakeup batch configuration which will cause hang")
didn't add much confidence about the magic batch setting to 4. Let me add
to CC original author of this code if he has any thoughts on why using
wake batch of 4 is safe for cards with say 32 tags in case active_users is
currently 32. Because I don't see why that is correct either.

								Honza

> ---
>  lib/sbitmap.c | 5 +----
>  1 file changed, 1 insertion(+), 4 deletions(-)
> 
> diff --git a/lib/sbitmap.c b/lib/sbitmap.c
> index b6d3bb1c3675..804fe99783e4 100644
> --- a/lib/sbitmap.c
> +++ b/lib/sbitmap.c
> @@ -458,13 +458,10 @@ void sbitmap_queue_recalculate_wake_batch(struct sbitmap_queue *sbq,
>  					    unsigned int users)
>  {
>  	unsigned int wake_batch;
> -	unsigned int min_batch;
>  	unsigned int depth = (sbq->sb.depth + users - 1) / users;
>  
> -	min_batch = sbq->sb.depth >= (4 * SBQ_WAIT_QUEUES) ? 4 : 1;
> -
>  	wake_batch = clamp_val(depth / SBQ_WAIT_QUEUES,
> -			min_batch, SBQ_WAKE_BATCH);
> +			1, SBQ_WAKE_BATCH);
>  
>  	WRITE_ONCE(sbq->wake_batch, wake_batch);
>  }
> -- 
> 2.30.0
> 
-- 
Jan Kara <jack@suse.com>
SUSE Labs, CR

Re: [PATCH RESEND v2 5/5] sbitmap: correct wake_batch recalculation to avoid potential IO hung

[Yu Kuai]

Hi,

在 2022/12/22 21:41, Jan Kara 写道:
> On Thu 22-12-22 22:33:53, Kemeng Shi wrote:
>> Commit 180dccb0dba4f ("blk-mq: fix tag_get wait task can't be awakened")
>> mentioned that in case of shared tags, there could be just one real
>> active hctx(queue) because of lazy detection of tag idle. Then driver tag
>> allocation may wait forever on this real active hctx(queue) if wake_batch
>> is > hctx_max_depth where hctx_max_depth is available tags depth for the
>> actve hctx(queue). However, the condition wake_batch > hctx_max_depth is
>> not strong enough to avoid IO hung as the sbitmap_queue_wake_up will only
>> wake up one wait queue for each wake_batch even though there is only one
>> waiter in the woken wait queue. After this, there is only one tag to free
>> and wake_batch may not be reached anymore. Commit 180dccb0dba4f ("blk-mq:
>> fix tag_get wait task can't be awakened") methioned that driver tag
>> allocation may wait forever. Actually, the inactive hctx(queue) will be
>> truely idle after at most 30 seconds and will call blk_mq_tag_wakeup_all
>> to wake one waiter per wait queue to break the hung. But IO hung for 30
>> seconds is also not acceptable. Set batch size to small enough that depth
>> of the shared hctx(queue) is enough to wake up all of the queues like
>> sbq_calc_wake_batch do to fix this potential IO hung.
>>
>> Although hctx_max_depth will be clamped to at least 4 while wake_batch
>> recalculation does not do the clamp, the wake_batch will be always
>> recalculated to 1 when hctx_max_depth <= 4.
>>
>> Fixes: 180dccb0dba4 ("blk-mq: fix tag_get wait task can't be awakened")
>> Signed-off-by: Kemeng Shi <shikemeng@huaweicloud.com>
> 
> So the condition in sbitmap_queue_recalculate_wake_batch() also seemed
> strange to me and the changelogs of commits 180dccb0dba4 and 10825410b95
> ("blk-mq: Fix wrong wakeup batch configuration which will cause hang")
> didn't add much confidence about the magic batch setting to 4. Let me add
> to CC original author of this code if he has any thoughts on why using
> wake batch of 4 is safe for cards with say 32 tags in case active_users is
> currently 32. Because I don't see why that is correct either.
> 

If I remember this correctly, the reason to use 4 here in the first
place is to avoid performance degradation. And for why this is safe
because 4 * 8 = 32. Someone is waiting for tag means 32 tags is all
grabbed, and wake batch of 4 will make sure at least 8 wait queues will
be awaken. It's right some waitqueue might only have one waiter, but I
don't think this will cause io hang.

Thanks,
Kuai
> 								Honza
> 
>> ---
>>   lib/sbitmap.c | 5 +----
>>   1 file changed, 1 insertion(+), 4 deletions(-)
>>
>> diff --git a/lib/sbitmap.c b/lib/sbitmap.c
>> index b6d3bb1c3675..804fe99783e4 100644
>> --- a/lib/sbitmap.c
>> +++ b/lib/sbitmap.c
>> @@ -458,13 +458,10 @@ void sbitmap_queue_recalculate_wake_batch(struct sbitmap_queue *sbq,
>>   					    unsigned int users)
>>   {
>>   	unsigned int wake_batch;
>> -	unsigned int min_batch;
>>   	unsigned int depth = (sbq->sb.depth + users - 1) / users;
>>   
>> -	min_batch = sbq->sb.depth >= (4 * SBQ_WAIT_QUEUES) ? 4 : 1;
>> -
>>   	wake_batch = clamp_val(depth / SBQ_WAIT_QUEUES,
>> -			min_batch, SBQ_WAKE_BATCH);
>> +			1, SBQ_WAKE_BATCH);
>>   
>>   	WRITE_ONCE(sbq->wake_batch, wake_batch);
>>   }
>> -- 
>> 2.30.0
>>

Re: [PATCH RESEND v2 5/5] sbitmap: correct wake_batch recalculation to avoid potential IO hung

[Yu Kuai]

在 2022/12/26 15:50, Yu Kuai 写道:

>> why using
>> wake batch of 4 is safe for cards with say 32 tags in case 
>> active_users is
>> currently 32. Because I don't see why that is correct either.
>>

I see, you guys are worried that during the period that some hctx
complete all it's not idle yet. It's right waiter might wait for
other hctx to become idle to be awaken in this case. However, I'm
not sure which way is better.

Ming, do you have any idea?

Thanks,
Kuai

Re: [PATCH RESEND v2 5/5] sbitmap: correct wake_batch recalculation to avoid potential IO hung

[Kemeng Shi]

Friendly ping...

on 12/26/2022 4:57 PM, Yu Kuai wrote:
> 在 2022/12/26 15:50, Yu Kuai 写道:
> 
>>> why using
>>> wake batch of 4 is safe for cards with say 32 tags in case active_users is
>>> currently 32. Because I don't see why that is correct either.
>>>
> 
> I see, you guys are worried that during the period that some hctx
> complete all it's not idle yet. It's right waiter might wait for
> other hctx to become idle to be awaken in this case. However, I'm
> not sure which way is better.
> 
> Ming, do you have any idea?
> 
> Thanks,
> Kuai
> 

-- 
Best wishes
Kemeng Shi

Re: [PATCH RESEND v2 5/5] sbitmap: correct wake_batch recalculation to avoid potential IO hung

[Kemeng Shi]

on 1/3/2023 10:12 AM, Kemeng Shi wrote:
> Friendly ping...
> 
> on 12/26/2022 4:57 PM, Yu Kuai wrote:
>> 在 2022/12/26 15:50, Yu Kuai 写道:
>>
>>>> why using
>>>> wake batch of 4 is safe for cards with say 32 tags in case active_users is
>>>> currently 32. Because I don't see why that is correct either.
>>>>
>>
>> I see, you guys are worried that during the period that some hctx
>> complete all it's not idle yet. It's right waiter might wait for
>> other hctx to become idle to be awaken in this case. However, I'm
>> not sure which way is better.
>>
>> Ming, do you have any idea?
>>
>> Thanks,
>> Kuai
>>
> 
Hi Jan. The magic batch 4 seems just for performance initially while
lacks of full consideration. And there is no better solution provided
in futher. Do you have any suggestion that I can do to make more
progress.

-- 
Best wishes
Kemeng Shi

Re: [PATCH RESEND v2 5/5] sbitmap: correct wake_batch recalculation to avoid potential IO hung

[Jan Kara]

On Mon 16-01-23 10:15:08, Kemeng Shi wrote:
> 
> 
> on 1/3/2023 10:12 AM, Kemeng Shi wrote:
> > Friendly ping...
> > 
> > on 12/26/2022 4:57 PM, Yu Kuai wrote:
> >> 在 2022/12/26 15:50, Yu Kuai 写道:
> >>
> >>>> why using
> >>>> wake batch of 4 is safe for cards with say 32 tags in case active_users is
> >>>> currently 32. Because I don't see why that is correct either.
> >>>>
> >>
> >> I see, you guys are worried that during the period that some hctx
> >> complete all it's not idle yet. It's right waiter might wait for
> >> other hctx to become idle to be awaken in this case. However, I'm
> >> not sure which way is better.
> >>
> >> Ming, do you have any idea?
> >>
> >> Thanks,
> >> Kuai
> >>
> > 
> Hi Jan. The magic batch 4 seems just for performance initially while
> lacks of full consideration. And there is no better solution provided
> in futher. Do you have any suggestion that I can do to make more
> progress.

Yeah, since there was not any good reasoning behind the magic batch of size
4, feel free to add:

Reviewed-by: Jan Kara <jack@suse.cz>

to this patch.

								Honza
-- 
Jan Kara <jack@suse.com>
SUSE Labs, CR