* sbitmap: check cleared bits when iterating busy bits
@ 2018-12-03 21:56 Jens Axboe
2018-12-03 22:05 ` Omar Sandoval
0 siblings, 1 reply; 3+ messages in thread
From: Jens Axboe @ 2018-12-03 21:56 UTC (permalink / raw)
To: linux-block@vger.kernel.org; +Cc: Omar Sandoval
When we are iterating the set bits in a word, we also need to factor in
the cleared bits. Don't call fn() unless the bit is also not set in
the cleared word.
Fixes: ea86ea2cdced ("sbitmap: ammortize cost of clearing bits")
Signed-off-by: Jens Axboe <axboe@kernel.dk>
diff --git a/include/linux/sbitmap.h b/include/linux/sbitmap.h
index 92806a2dbab7..9f374fbcdba6 100644
--- a/include/linux/sbitmap.h
+++ b/include/linux/sbitmap.h
@@ -283,6 +283,11 @@ static inline void __sbitmap_for_each_set(struct sbitmap *sb,
nr = find_next_bit(&word->word, depth, nr);
if (nr >= depth)
break;
+ /* if set in cleared, it's actually free */
+ if (test_bit(nr, &word->cleared)) {
+ nr++;
+ continue;
+ }
if (!fn(sb, (index << sb->shift) + nr, data))
return;
--
Jens Axboe
^ permalink raw reply related [flat|nested] 3+ messages in thread
* Re: sbitmap: check cleared bits when iterating busy bits
2018-12-03 21:56 sbitmap: check cleared bits when iterating busy bits Jens Axboe
@ 2018-12-03 22:05 ` Omar Sandoval
2018-12-03 22:20 ` Jens Axboe
0 siblings, 1 reply; 3+ messages in thread
From: Omar Sandoval @ 2018-12-03 22:05 UTC (permalink / raw)
To: Jens Axboe; +Cc: linux-block@vger.kernel.org
On Mon, Dec 03, 2018 at 02:56:17PM -0700, Jens Axboe wrote:
> When we are iterating the set bits in a word, we also need to factor in
> the cleared bits. Don't call fn() unless the bit is also not set in
> the cleared word.
>
> Fixes: ea86ea2cdced ("sbitmap: ammortize cost of clearing bits")
> Signed-off-by: Jens Axboe <axboe@kernel.dk>
>
> diff --git a/include/linux/sbitmap.h b/include/linux/sbitmap.h
> index 92806a2dbab7..9f374fbcdba6 100644
> --- a/include/linux/sbitmap.h
> +++ b/include/linux/sbitmap.h
> @@ -283,6 +283,11 @@ static inline void __sbitmap_for_each_set(struct sbitmap *sb,
> nr = find_next_bit(&word->word, depth, nr);
> if (nr >= depth)
> break;
> + /* if set in cleared, it's actually free */
> + if (test_bit(nr, &word->cleared)) {
> + nr++;
> + continue;
> + }
> if (!fn(sb, (index << sb->shift) + nr, data))
> return;
>
> --
> Jens Axboe
>
How about something like this:
diff --git a/include/linux/sbitmap.h b/include/linux/sbitmap.h
index f0f49bbb2617..fe9122386255 100644
--- a/include/linux/sbitmap.h
+++ b/include/linux/sbitmap.h
@@ -265,12 +265,14 @@ static inline void __sbitmap_for_each_set(struct sbitmap *sb,
nr = SB_NR_TO_BIT(sb, start);
while (scanned < sb->depth) {
- struct sbitmap_word *word = &sb->map[index];
- unsigned int depth = min_t(unsigned int, word->depth - nr,
+ unsigned long word;
+ unsigned int depth = min_t(unsigned int,
+ sb->map[index].depth - nr,
sb->depth - scanned);
scanned += depth;
- if (!word->word)
+ word = sb->map[index].word & ~sb->map[index].cleared;
+ if (!word)
goto next;
/*
@@ -280,7 +282,7 @@ static inline void __sbitmap_for_each_set(struct sbitmap *sb,
*/
depth += nr;
while (1) {
- nr = find_next_bit(&word->word, depth, nr);
+ nr = find_next_bit(&word, depth, nr);
if (nr >= depth)
break;
if (!fn(sb, (index << sb->shift) + nr, data))
Might be marginally faster.
^ permalink raw reply related [flat|nested] 3+ messages in thread
* Re: sbitmap: check cleared bits when iterating busy bits
2018-12-03 22:05 ` Omar Sandoval
@ 2018-12-03 22:20 ` Jens Axboe
0 siblings, 0 replies; 3+ messages in thread
From: Jens Axboe @ 2018-12-03 22:20 UTC (permalink / raw)
To: Omar Sandoval; +Cc: linux-block@vger.kernel.org
On 12/3/18 3:05 PM, Omar Sandoval wrote:
> On Mon, Dec 03, 2018 at 02:56:17PM -0700, Jens Axboe wrote:
>> When we are iterating the set bits in a word, we also need to factor in
>> the cleared bits. Don't call fn() unless the bit is also not set in
>> the cleared word.
>>
>> Fixes: ea86ea2cdced ("sbitmap: ammortize cost of clearing bits")
>> Signed-off-by: Jens Axboe <axboe@kernel.dk>
>>
>> diff --git a/include/linux/sbitmap.h b/include/linux/sbitmap.h
>> index 92806a2dbab7..9f374fbcdba6 100644
>> --- a/include/linux/sbitmap.h
>> +++ b/include/linux/sbitmap.h
>> @@ -283,6 +283,11 @@ static inline void __sbitmap_for_each_set(struct sbitmap *sb,
>> nr = find_next_bit(&word->word, depth, nr);
>> if (nr >= depth)
>> break;
>> + /* if set in cleared, it's actually free */
>> + if (test_bit(nr, &word->cleared)) {
>> + nr++;
>> + continue;
>> + }
>> if (!fn(sb, (index << sb->shift) + nr, data))
>> return;
>>
>> --
>> Jens Axboe
>>
>
> How about something like this:
>
> diff --git a/include/linux/sbitmap.h b/include/linux/sbitmap.h
> index f0f49bbb2617..fe9122386255 100644
> --- a/include/linux/sbitmap.h
> +++ b/include/linux/sbitmap.h
> @@ -265,12 +265,14 @@ static inline void __sbitmap_for_each_set(struct sbitmap *sb,
> nr = SB_NR_TO_BIT(sb, start);
>
> while (scanned < sb->depth) {
> - struct sbitmap_word *word = &sb->map[index];
> - unsigned int depth = min_t(unsigned int, word->depth - nr,
> + unsigned long word;
> + unsigned int depth = min_t(unsigned int,
> + sb->map[index].depth - nr,
> sb->depth - scanned);
>
> scanned += depth;
> - if (!word->word)
> + word = sb->map[index].word & ~sb->map[index].cleared;
> + if (!word)
> goto next;
>
> /*
> @@ -280,7 +282,7 @@ static inline void __sbitmap_for_each_set(struct sbitmap *sb,
> */
> depth += nr;
> while (1) {
> - nr = find_next_bit(&word->word, depth, nr);
> + nr = find_next_bit(&word, depth, nr);
> if (nr >= depth)
> break;
> if (!fn(sb, (index << sb->shift) + nr, data))
>
> Might be marginally faster.
Yeah that looks fine as well, tests out good too.
--
Jens Axboe
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2018-12-03 22:20 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2018-12-03 21:56 sbitmap: check cleared bits when iterating busy bits Jens Axboe
2018-12-03 22:05 ` Omar Sandoval
2018-12-03 22:20 ` Jens Axboe
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox