* [PATCH 1/6] sbitmap: fix hint wrap in the failure case
2023-07-20 9:45 [PATCH 0/6] sbitmap: fix offset hint wrap and some optimizations chengming.zhou
@ 2023-07-20 9:45 ` chengming.zhou
2023-07-20 19:06 ` Gabriel Krisman Bertazi
2023-07-20 9:45 ` [PATCH 2/6] sbitmap: fix round-robin non-wrap find with hint > 0 chengming.zhou
` (4 subsequent siblings)
5 siblings, 1 reply; 9+ messages in thread
From: chengming.zhou @ 2023-07-20 9:45 UTC (permalink / raw)
To: axboe, osandov, ming.lei, kbusch, krisman
Cc: linux-kernel, linux-block, zhouchengming
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
^ permalink raw reply related [flat|nested] 9+ messages in thread* Re: [PATCH 1/6] sbitmap: fix hint wrap in the failure case
2023-07-20 9:45 ` [PATCH 1/6] sbitmap: fix hint wrap in the failure case chengming.zhou
@ 2023-07-20 19:06 ` Gabriel Krisman Bertazi
2023-07-21 3:51 ` Chengming Zhou
0 siblings, 1 reply; 9+ messages in thread
From: Gabriel Krisman Bertazi @ 2023-07-20 19:06 UTC (permalink / raw)
To: chengming.zhou
Cc: axboe, osandov, ming.lei, kbusch, linux-kernel, linux-block,
zhouchengming
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
^ permalink raw reply [flat|nested] 9+ messages in thread* Re: [PATCH 1/6] sbitmap: fix hint wrap in the failure case
2023-07-20 19:06 ` Gabriel Krisman Bertazi
@ 2023-07-21 3:51 ` Chengming Zhou
0 siblings, 0 replies; 9+ messages in thread
From: Chengming Zhou @ 2023-07-21 3:51 UTC (permalink / raw)
To: Gabriel Krisman Bertazi
Cc: axboe, osandov, ming.lei, kbusch, linux-kernel, linux-block,
zhouchengming
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;
>
^ permalink raw reply [flat|nested] 9+ messages in thread
* [PATCH 2/6] sbitmap: fix round-robin non-wrap find with hint > 0
2023-07-20 9:45 [PATCH 0/6] sbitmap: fix offset hint wrap and some optimizations chengming.zhou
2023-07-20 9:45 ` [PATCH 1/6] sbitmap: fix hint wrap in the failure case chengming.zhou
@ 2023-07-20 9:45 ` chengming.zhou
2023-07-20 9:45 ` [PATCH 3/6] sbitmap: don't loop twice in find_next_zero_bit() chengming.zhou
` (3 subsequent siblings)
5 siblings, 0 replies; 9+ messages in thread
From: chengming.zhou @ 2023-07-20 9:45 UTC (permalink / raw)
To: axboe, osandov, ming.lei, kbusch, krisman
Cc: linux-kernel, linux-block, zhouchengming
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
^ permalink raw reply related [flat|nested] 9+ messages in thread* [PATCH 3/6] sbitmap: don't loop twice in find_next_zero_bit()
2023-07-20 9:45 [PATCH 0/6] sbitmap: fix offset hint wrap and some optimizations chengming.zhou
2023-07-20 9:45 ` [PATCH 1/6] sbitmap: fix hint wrap in the failure case chengming.zhou
2023-07-20 9:45 ` [PATCH 2/6] sbitmap: fix round-robin non-wrap find with hint > 0 chengming.zhou
@ 2023-07-20 9:45 ` chengming.zhou
2023-07-20 9:45 ` [PATCH 4/6] sbitmap: remove offset wrap logic when finding bit in word chengming.zhou
` (2 subsequent siblings)
5 siblings, 0 replies; 9+ messages in thread
From: chengming.zhou @ 2023-07-20 9:45 UTC (permalink / raw)
To: axboe, osandov, ming.lei, kbusch, krisman
Cc: linux-kernel, linux-block, zhouchengming
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
^ permalink raw reply related [flat|nested] 9+ messages in thread* [PATCH 4/6] sbitmap: remove offset wrap logic when finding bit in word
2023-07-20 9:45 [PATCH 0/6] sbitmap: fix offset hint wrap and some optimizations chengming.zhou
` (2 preceding siblings ...)
2023-07-20 9:45 ` [PATCH 3/6] sbitmap: don't loop twice in find_next_zero_bit() chengming.zhou
@ 2023-07-20 9:45 ` chengming.zhou
2023-07-20 9:45 ` [PATCH 5/6] sbitmap: wake_index doesn't need to be atomic_t chengming.zhou
2023-07-20 9:45 ` [PATCH 6/6] sbitmap: check ws_active before check waitqueues chengming.zhou
5 siblings, 0 replies; 9+ messages in thread
From: chengming.zhou @ 2023-07-20 9:45 UTC (permalink / raw)
To: axboe, osandov, ming.lei, kbusch, krisman
Cc: linux-kernel, linux-block, zhouchengming
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
^ permalink raw reply related [flat|nested] 9+ messages in thread* [PATCH 5/6] sbitmap: wake_index doesn't need to be atomic_t
2023-07-20 9:45 [PATCH 0/6] sbitmap: fix offset hint wrap and some optimizations chengming.zhou
` (3 preceding siblings ...)
2023-07-20 9:45 ` [PATCH 4/6] sbitmap: remove offset wrap logic when finding bit in word chengming.zhou
@ 2023-07-20 9:45 ` chengming.zhou
2023-07-20 9:45 ` [PATCH 6/6] sbitmap: check ws_active before check waitqueues chengming.zhou
5 siblings, 0 replies; 9+ messages in thread
From: chengming.zhou @ 2023-07-20 9:45 UTC (permalink / raw)
To: axboe, osandov, ming.lei, kbusch, krisman
Cc: linux-kernel, linux-block, zhouchengming
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
^ permalink raw reply related [flat|nested] 9+ messages in thread* [PATCH 6/6] sbitmap: check ws_active before check waitqueues
2023-07-20 9:45 [PATCH 0/6] sbitmap: fix offset hint wrap and some optimizations chengming.zhou
` (4 preceding siblings ...)
2023-07-20 9:45 ` [PATCH 5/6] sbitmap: wake_index doesn't need to be atomic_t chengming.zhou
@ 2023-07-20 9:45 ` chengming.zhou
5 siblings, 0 replies; 9+ messages in thread
From: chengming.zhou @ 2023-07-20 9:45 UTC (permalink / raw)
To: axboe, osandov, ming.lei, kbusch, krisman
Cc: linux-kernel, linux-block, zhouchengming
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
^ permalink raw reply related [flat|nested] 9+ messages in thread