sbitmap: check cleared bits when iterating busy bits

sbitmap: check cleared bits when iterating busy bits

[Jens Axboe]

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

Re: sbitmap: check cleared bits when iterating busy bits

[Omar Sandoval]

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.

Re: sbitmap: check cleared bits when iterating busy bits

[Jens Axboe]

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