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 <ax...@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.