[PATCH 0/6] sbitmap: fix offset hint wrap and some optimizations

[PATCH 0/6] sbitmap: fix offset hint wrap and some optimizations

[chengming.zhou]

From: Chengming Zhou <zhouchengming@bytedance.com>

Hello,

This series aim to fix and simplify the offset hint wrap logic, also
include some minor optimizations.

patch 01,02 fix offset hint wrap logic in strict round-robin mode.

patch 03,04 simplify the sbitmap_find_bit() code by removing wrap logic.

patch 05,06 are two minor optimizations.

Thanks!

Chengming Zhou (6):
  sbitmap: fix hint wrap in the failure case
  sbitmap: fix round-robin non-wrap find with hint > 0
  sbitmap: don't loop twice in find_next_zero_bit()
  sbitmap: remove offset wrap logic when finding bit in word
  sbitmap: wake_index doesn't need to be atomic_t
  sbitmap: check ws_active before check waitqueues

 include/linux/sbitmap.h |  2 +-
 lib/sbitmap.c           | 66 ++++++++++++++++++++---------------------
 2 files changed, 33 insertions(+), 35 deletions(-)

-- 
2.41.0

[PATCH 1/6] sbitmap: fix hint wrap in the failure case

[chengming.zhou]

From: Chengming Zhou <zhouchengming@bytedance.com>

```
hint = nr + 1;
if (hint >= depth - 1)
	hint = 0;
```

Now we wrap the hint to 0 in the failure case, but:
1. hint == depth - 1, is actually an available offset hint, which
   we shouldn't wrap hint to 0.
2. In the strict round_robin non-wrap case, we shouldn't wrap at all.

```
wrap = wrap && hint;
```

We only need to check wrap based on the original hint ( > 0), don't need
to recheck the new hint which maybe updated in the failure case.
Also delete the mismatched comments by the way.

Signed-off-by: Chengming Zhou <zhouchengming@bytedance.com>
---
 lib/sbitmap.c | 16 ++++++++--------
 1 file changed, 8 insertions(+), 8 deletions(-)

diff --git a/lib/sbitmap.c b/lib/sbitmap.c
index eff4e42c425a..5ed6c2adf58e 100644
--- a/lib/sbitmap.c
+++ b/lib/sbitmap.c
@@ -144,12 +144,7 @@ static int __sbitmap_get_word(unsigned long *word, unsigned long depth,
 	while (1) {
 		nr = find_next_zero_bit(word, depth, hint);
 		if (unlikely(nr >= depth)) {
-			/*
-			 * We started with an offset, and we didn't reset the
-			 * offset to 0 in a failure case, so start from 0 to
-			 * exhaust the map.
-			 */
-			if (hint && wrap) {
+			if (wrap) {
 				hint = 0;
 				continue;
 			}
@@ -160,8 +155,13 @@ static int __sbitmap_get_word(unsigned long *word, unsigned long depth,
 			break;
 
 		hint = nr + 1;
-		if (hint >= depth - 1)
-			hint = 0;
+		if (hint >= depth) {
+			if (wrap) {
+				hint = 0;
+				continue;
+			}
+			return -1;
+		}
 	}
 
 	return nr;
-- 
2.41.0

[PATCH 2/6] sbitmap: fix round-robin non-wrap find with hint > 0

[chengming.zhou]

From: Chengming Zhou <zhouchengming@bytedance.com>

If we have alloc_hint > 0 and don't wrap, we need to recheck
sb->map[index] with hint == 0 to exhaust the map.

Signed-off-by: Chengming Zhou <zhouchengming@bytedance.com>
---
 lib/sbitmap.c | 10 +++++++++-
 1 file changed, 9 insertions(+), 1 deletion(-)

diff --git a/lib/sbitmap.c b/lib/sbitmap.c
index 5ed6c2adf58e..ccb96d1f92ba 100644
--- a/lib/sbitmap.c
+++ b/lib/sbitmap.c
@@ -192,10 +192,18 @@ static int sbitmap_find_bit(struct sbitmap *sb,
 			    unsigned int alloc_hint,
 			    bool wrap)
 {
+	unsigned int map_nr = sb->map_nr;
 	unsigned int i;
 	int nr = -1;
 
-	for (i = 0; i < sb->map_nr; i++) {
+	/*
+	 * If we have alloc_hint > 0 and don't wrap, we need to
+	 * recheck sb->map[index] with hint == 0 to exhaust the map.
+	 */
+	if (alloc_hint && !wrap)
+		map_nr += 1;
+
+	for (i = 0; i < map_nr; i++) {
 		nr = sbitmap_find_bit_in_word(&sb->map[index],
 					      min_t(unsigned int,
 						    __map_depth(sb, index),
-- 
2.41.0

[PATCH 3/6] sbitmap: don't loop twice in find_next_zero_bit()

[chengming.zhou]

From: Chengming Zhou <zhouchengming@bytedance.com>

__sbitmap_get_shallow() try to allocate a free bit with a limited depth,
which always wrap when finding a free bit in the word, even in the
round-robin case. So it seems we don't need strict round-robin here.

This way will loop twice in find_next_zero_bit() in the word, no point
in looping twice in find_next_zero_bit() if we don't want strict
round-robin for this case.

Signed-off-by: Chengming Zhou <zhouchengming@bytedance.com>
---
 lib/sbitmap.c | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

diff --git a/lib/sbitmap.c b/lib/sbitmap.c
index ccb96d1f92ba..0f3943bd3940 100644
--- a/lib/sbitmap.c
+++ b/lib/sbitmap.c
@@ -268,7 +268,9 @@ static int __sbitmap_get_shallow(struct sbitmap *sb,
 	unsigned int index;
 
 	index = SB_NR_TO_INDEX(sb, alloc_hint);
-	alloc_hint = SB_NR_TO_BIT(sb, alloc_hint);
+
+	/* No point in looping twice in find_next_zero_bit() for this case. */
+	alloc_hint = 0;
 
 	return sbitmap_find_bit(sb, shallow_depth, index, alloc_hint, true);
 }
-- 
2.41.0

[PATCH 4/6] sbitmap: remove offset wrap logic when finding bit in word

[chengming.zhou]

From: Chengming Zhou <zhouchengming@bytedance.com>

We actually don't need the offset hint wrap logic in word:

1. Strict round-robin mode: just search from that offset hint,
   we will recheck that word at last if offset hint > 0.

2. No round-robin mode: we use offset hint == 0, so don't need
   to wrap offset hint too.

We remove offset wrap logic and simplify the code.

Signed-off-by: Chengming Zhou <zhouchengming@bytedance.com>
---
 lib/sbitmap.c | 36 ++++++++++--------------------------
 1 file changed, 10 insertions(+), 26 deletions(-)

diff --git a/lib/sbitmap.c b/lib/sbitmap.c
index 0f3943bd3940..50bdf3a31947 100644
--- a/lib/sbitmap.c
+++ b/lib/sbitmap.c
@@ -134,34 +134,21 @@ void sbitmap_resize(struct sbitmap *sb, unsigned int depth)
 EXPORT_SYMBOL_GPL(sbitmap_resize);
 
 static int __sbitmap_get_word(unsigned long *word, unsigned long depth,
-			      unsigned int hint, bool wrap)
+			      unsigned int hint)
 {
 	int nr;
 
-	/* don't wrap if starting from 0 */
-	wrap = wrap && hint;
-
 	while (1) {
 		nr = find_next_zero_bit(word, depth, hint);
-		if (unlikely(nr >= depth)) {
-			if (wrap) {
-				hint = 0;
-				continue;
-			}
+		if (unlikely(nr >= depth))
 			return -1;
-		}
 
 		if (!test_and_set_bit_lock(nr, word))
 			break;
 
 		hint = nr + 1;
-		if (hint >= depth) {
-			if (wrap) {
-				hint = 0;
-				continue;
-			}
+		if (hint >= depth)
 			return -1;
-		}
 	}
 
 	return nr;
@@ -169,14 +156,13 @@ static int __sbitmap_get_word(unsigned long *word, unsigned long depth,
 
 static int sbitmap_find_bit_in_word(struct sbitmap_word *map,
 				    unsigned int depth,
-				    unsigned int alloc_hint,
-				    bool wrap)
+				    unsigned int alloc_hint)
 {
 	int nr;
 
 	do {
 		nr = __sbitmap_get_word(&map->word, depth,
-					alloc_hint, wrap);
+					alloc_hint);
 		if (nr != -1)
 			break;
 		if (!sbitmap_deferred_clear(map))
@@ -189,8 +175,7 @@ static int sbitmap_find_bit_in_word(struct sbitmap_word *map,
 static int sbitmap_find_bit(struct sbitmap *sb,
 			    unsigned int depth,
 			    unsigned int index,
-			    unsigned int alloc_hint,
-			    bool wrap)
+			    unsigned int alloc_hint)
 {
 	unsigned int map_nr = sb->map_nr;
 	unsigned int i;
@@ -200,7 +185,7 @@ static int sbitmap_find_bit(struct sbitmap *sb,
 	 * If we have alloc_hint > 0 and don't wrap, we need to
 	 * recheck sb->map[index] with hint == 0 to exhaust the map.
 	 */
-	if (alloc_hint && !wrap)
+	if (alloc_hint)
 		map_nr += 1;
 
 	for (i = 0; i < map_nr; i++) {
@@ -208,7 +193,7 @@ static int sbitmap_find_bit(struct sbitmap *sb,
 					      min_t(unsigned int,
 						    __map_depth(sb, index),
 						    depth),
-					      alloc_hint, wrap);
+					      alloc_hint);
 
 		if (nr != -1) {
 			nr += index << sb->shift;
@@ -240,8 +225,7 @@ static int __sbitmap_get(struct sbitmap *sb, unsigned int alloc_hint)
 	else
 		alloc_hint = 0;
 
-	return sbitmap_find_bit(sb, UINT_MAX, index, alloc_hint,
-				!sb->round_robin);
+	return sbitmap_find_bit(sb, UINT_MAX, index, alloc_hint);
 }
 
 int sbitmap_get(struct sbitmap *sb)
@@ -272,7 +256,7 @@ static int __sbitmap_get_shallow(struct sbitmap *sb,
 	/* No point in looping twice in find_next_zero_bit() for this case. */
 	alloc_hint = 0;
 
-	return sbitmap_find_bit(sb, shallow_depth, index, alloc_hint, true);
+	return sbitmap_find_bit(sb, shallow_depth, index, alloc_hint);
 }
 
 int sbitmap_get_shallow(struct sbitmap *sb, unsigned long shallow_depth)
-- 
2.41.0

[PATCH 5/6] sbitmap: wake_index doesn't need to be atomic_t

[chengming.zhou]

From: Chengming Zhou <zhouchengming@bytedance.com>

We use wake_index to remember from which to wake up next time, which
doesn't need to be atomic_t since we only read it once before wakeups,
and write it once after wakeups.

Signed-off-by: Chengming Zhou <zhouchengming@bytedance.com>
---
 include/linux/sbitmap.h |  2 +-
 lib/sbitmap.c           | 12 ++++++------
 2 files changed, 7 insertions(+), 7 deletions(-)

diff --git a/include/linux/sbitmap.h b/include/linux/sbitmap.h
index d662cf136021..bdbe478ba4dc 100644
--- a/include/linux/sbitmap.h
+++ b/include/linux/sbitmap.h
@@ -116,7 +116,7 @@ struct sbitmap_queue {
 	/**
 	 * @wake_index: Next wait queue in @ws to wake up.
 	 */
-	atomic_t wake_index;
+	unsigned int wake_index;
 
 	/**
 	 * @ws: Wait queues.
diff --git a/lib/sbitmap.c b/lib/sbitmap.c
index 50bdf3a31947..6778ab3fc6a5 100644
--- a/lib/sbitmap.c
+++ b/lib/sbitmap.c
@@ -419,7 +419,7 @@ int sbitmap_queue_init_node(struct sbitmap_queue *sbq, unsigned int depth,
 
 	sbq->min_shallow_depth = UINT_MAX;
 	sbq->wake_batch = sbq_calc_wake_batch(sbq, depth);
-	atomic_set(&sbq->wake_index, 0);
+	sbq->wake_index = 0;
 	atomic_set(&sbq->ws_active, 0);
 	atomic_set(&sbq->completion_cnt, 0);
 	atomic_set(&sbq->wakeup_cnt, 0);
@@ -549,7 +549,7 @@ static void __sbitmap_queue_wake_up(struct sbitmap_queue *sbq, int nr)
 	if (!atomic_read(&sbq->ws_active))
 		return;
 
-	wake_index = atomic_read(&sbq->wake_index);
+	wake_index = READ_ONCE(sbq->wake_index);
 	for (i = 0; i < SBQ_WAIT_QUEUES; i++) {
 		struct sbq_wait_state *ws = &sbq->ws[wake_index];
 
@@ -570,8 +570,8 @@ static void __sbitmap_queue_wake_up(struct sbitmap_queue *sbq, int nr)
 			break;
 	}
 
-	if (wake_index != atomic_read(&sbq->wake_index))
-		atomic_set(&sbq->wake_index, wake_index);
+	if (wake_index != READ_ONCE(sbq->wake_index))
+		WRITE_ONCE(sbq->wake_index, wake_index);
 }
 
 void sbitmap_queue_wake_up(struct sbitmap_queue *sbq, int nr)
@@ -672,7 +672,7 @@ void sbitmap_queue_wake_all(struct sbitmap_queue *sbq)
 	 * sbitmap_queue_wake_up().
 	 */
 	smp_mb();
-	wake_index = atomic_read(&sbq->wake_index);
+	wake_index = READ_ONCE(sbq->wake_index);
 	for (i = 0; i < SBQ_WAIT_QUEUES; i++) {
 		struct sbq_wait_state *ws = &sbq->ws[wake_index];
 
@@ -702,7 +702,7 @@ void sbitmap_queue_show(struct sbitmap_queue *sbq, struct seq_file *m)
 	seq_puts(m, "}\n");
 
 	seq_printf(m, "wake_batch=%u\n", sbq->wake_batch);
-	seq_printf(m, "wake_index=%d\n", atomic_read(&sbq->wake_index));
+	seq_printf(m, "wake_index=%d\n", READ_ONCE(sbq->wake_index));
 	seq_printf(m, "ws_active=%d\n", atomic_read(&sbq->ws_active));
 
 	seq_puts(m, "ws={\n");
-- 
2.41.0

[PATCH 6/6] sbitmap: check ws_active before check waitqueues

[chengming.zhou]

From: Chengming Zhou <zhouchengming@bytedance.com>

When !ws_active, we don't need to check waitqueues at all. So add
this check in sbitmap_queue_wake_all(), like we do in
sbitmap_queue_wake_up().

Signed-off-by: Chengming Zhou <zhouchengming@bytedance.com>
---
 lib/sbitmap.c | 4 ++++
 1 file changed, 4 insertions(+)

diff --git a/lib/sbitmap.c b/lib/sbitmap.c
index 6778ab3fc6a5..38c265e4ef9d 100644
--- a/lib/sbitmap.c
+++ b/lib/sbitmap.c
@@ -672,6 +672,10 @@ void sbitmap_queue_wake_all(struct sbitmap_queue *sbq)
 	 * sbitmap_queue_wake_up().
 	 */
 	smp_mb();
+
+	if (!atomic_read(&sbq->ws_active))
+		return;
+
 	wake_index = READ_ONCE(sbq->wake_index);
 	for (i = 0; i < SBQ_WAIT_QUEUES; i++) {
 		struct sbq_wait_state *ws = &sbq->ws[wake_index];
-- 
2.41.0

Re: [PATCH 1/6] sbitmap: fix hint wrap in the failure case

[Gabriel Krisman Bertazi]

chengming.zhou@linux.dev writes:

> From: Chengming Zhou <zhouchengming@bytedance.com>
>
> ```
> hint = nr + 1;
> if (hint >= depth - 1)
> 	hint = 0;
> ```
>
> Now we wrap the hint to 0 in the failure case, but:
> 1. hint == depth - 1, is actually an available offset hint, which
>    we shouldn't wrap hint to 0.
> 2. In the strict round_robin non-wrap case, we shouldn't wrap at all.
>
> ```
> wrap = wrap && hint;
> ```
>
> We only need to check wrap based on the original hint ( > 0), don't need
> to recheck the new hint which maybe updated in the failure case.
> Also delete the mismatched comments by the way.
>
> Signed-off-by: Chengming Zhou <zhouchengming@bytedance.com>
> ---
>  lib/sbitmap.c | 16 ++++++++--------
>  1 file changed, 8 insertions(+), 8 deletions(-)
>
> diff --git a/lib/sbitmap.c b/lib/sbitmap.c
> index eff4e42c425a..5ed6c2adf58e 100644
> --- a/lib/sbitmap.c
> +++ b/lib/sbitmap.c
> @@ -144,12 +144,7 @@ static int __sbitmap_get_word(unsigned long *word, unsigned long depth,
>  	while (1) {
>  		nr = find_next_zero_bit(word, depth, hint);
>  		if (unlikely(nr >= depth)) {
> -			/*
> -			 * We started with an offset, and we didn't reset the
> -			 * offset to 0 in a failure case, so start from 0 to
> -			 * exhaust the map.
> -			 */
> -			if (hint && wrap) {
> +			if (wrap) {
>  				hint = 0;
>  				continue;

I think this is wrong.  If you start with an offset in the wrap case and
the bitmap is completely full this will become busy wait until a bit is
available. The hint check is what make you break out of the loop early,
after wrapping, re-walking the entire bitmap and failing to find any
available space.

> @@ -160,8 +155,13 @@ static int __sbitmap_get_word(unsigned long *word, unsigned long depth,
>  			break;
>  
>  		hint = nr + 1;
> -		if (hint >= depth - 1)
> -			hint = 0;
> +		if (hint >= depth) {
> +			if (wrap) {
> +				hint = 0;
> +				continue;
> +			}
> +			return -1;
> +		}
>  	}
>  
>  	return nr;

-- 
Gabriel Krisman Bertazi

Re: [PATCH 1/6] sbitmap: fix hint wrap in the failure case

[Chengming Zhou]

On 2023/7/21 03:06, Gabriel Krisman Bertazi wrote:
> chengming.zhou@linux.dev writes:
> 
>> From: Chengming Zhou <zhouchengming@bytedance.com>
>>
>> ```
>> hint = nr + 1;
>> if (hint >= depth - 1)
>> 	hint = 0;
>> ```
>>
>> Now we wrap the hint to 0 in the failure case, but:
>> 1. hint == depth - 1, is actually an available offset hint, which
>>    we shouldn't wrap hint to 0.
>> 2. In the strict round_robin non-wrap case, we shouldn't wrap at all.
>>
>> ```
>> wrap = wrap && hint;
>> ```
>>
>> We only need to check wrap based on the original hint ( > 0), don't need
>> to recheck the new hint which maybe updated in the failure case.
>> Also delete the mismatched comments by the way.
>>
>> Signed-off-by: Chengming Zhou <zhouchengming@bytedance.com>
>> ---
>>  lib/sbitmap.c | 16 ++++++++--------
>>  1 file changed, 8 insertions(+), 8 deletions(-)
>>
>> diff --git a/lib/sbitmap.c b/lib/sbitmap.c
>> index eff4e42c425a..5ed6c2adf58e 100644
>> --- a/lib/sbitmap.c
>> +++ b/lib/sbitmap.c
>> @@ -144,12 +144,7 @@ static int __sbitmap_get_word(unsigned long *word, unsigned long depth,
>>  	while (1) {
>>  		nr = find_next_zero_bit(word, depth, hint);
>>  		if (unlikely(nr >= depth)) {
>> -			/*
>> -			 * We started with an offset, and we didn't reset the
>> -			 * offset to 0 in a failure case, so start from 0 to
>> -			 * exhaust the map.
>> -			 */
>> -			if (hint && wrap) {
>> +			if (wrap) {
>>  				hint = 0;
>>  				continue;
> 
> I think this is wrong.  If you start with an offset in the wrap case and
> the bitmap is completely full this will become busy wait until a bit is
> available. The hint check is what make you break out of the loop early,
> after wrapping, re-walking the entire bitmap and failing to find any
> available space.

Ah yes, you are right, thanks for your explanation. Here we need to check
"hint && wrap" to avoid wrap repeatedly.

Will drop this change in the next version.

> 
>> @@ -160,8 +155,13 @@ static int __sbitmap_get_word(unsigned long *word, unsigned long depth,
>>  			break;
>>  
>>  		hint = nr + 1;

Here we overwrite hint, may cause repeated wrap. So I think it's clearer that
we set "wrap" to false after we wrap?

```
if (wrap) {
	wrap = false;
	hint = 0;
	continue;
}
```

Thanks!

>> -		if (hint >= depth - 1)
>> -			hint = 0;
>> +		if (hint >= depth) {
>> +			if (wrap) {
>> +				hint = 0;
>> +				continue;
>> +			}
>> +			return -1;
>> +		}
>>  	}
>>  
>>  	return nr;
>