Re: [PATCH V4 02/14] sbitmap: introduce __sbitmap_for_each_set()

[Omar Sandoval <osandov@osandov.com>]

On Thu, Sep 14, 2017 at 07:59:43AM -0700, Omar Sandoval wrote:

[snip]

> Honestly I prefer your original patch with a comment on depth += nr. I'd
> be happy with the following incremental patch on top of your original v4
> patch.

Oh, and the change renaming the off parameter to start would be good to
include, too.

> diff --git a/include/linux/sbitmap.h b/include/linux/sbitmap.h
> index 2329b9e1a0e2..8d747048ae4f 100644
> --- a/include/linux/sbitmap.h
> +++ b/include/linux/sbitmap.h
> @@ -218,7 +218,7 @@ typedef bool (*sb_for_each_fn)(struct sbitmap *, unsigned int, void *);
>  
>  /**
>   * sbitmap_for_each_set() - Iterate over each set bit in a &struct sbitmap.
> - * @off: Where to start the iteration
> + * @off: Where to start the iteration.
>   * @sb: Bitmap to iterate over.
>   * @fn: Callback. Should return true to continue or false to break early.
>   * @data: Pointer to pass to callback.
> @@ -230,11 +230,16 @@ static inline void __sbitmap_for_each_set(struct sbitmap *sb,
>  					  unsigned int off,
>  					  sb_for_each_fn fn, void *data)
>  {
> -	unsigned int index = SB_NR_TO_INDEX(sb, off);
> -	unsigned int nr = SB_NR_TO_BIT(sb, off);
> +	unsigned int index;
> +	unsigned int nr;
>  	unsigned int scanned = 0;
>  
> -	while (1) {
> +	if (off >= sb->depth)
> +		off = 0;
> +	index = SB_NR_TO_INDEX(sb, off);
> +	nr = SB_NR_TO_BIT(sb, off);
> +
> +	while (scanned < sb->depth) {
>  		struct sbitmap_word *word = &sb->map[index];
>  		unsigned int depth = min_t(unsigned int, word->depth - nr,
>  					   sb->depth - scanned);
> @@ -243,6 +248,11 @@ static inline void __sbitmap_for_each_set(struct sbitmap *sb,
>  		if (!word->word)
>  			goto next;
>  
> +		/*
> +		 * On the first iteration of the outer loop, we need to add the
> +		 * bit offset back to the size of the word for find_next_bit().
> +		 * On all other iterations, nr is zero, so this is a noop.
> +		 */
>  		depth += nr;
>  		off = index << sb->shift;
>  		while (1) {
> @@ -254,9 +264,7 @@ static inline void __sbitmap_for_each_set(struct sbitmap *sb,
>  
>  			nr++;
>  		}
> - next:
> -		if (scanned >= sb->depth)
> -			break;
> +next:
>  		nr = 0;
>  		if (++index >= sb->map_nr)
>  			index = 0;
> @@ -268,9 +276,6 @@ static inline void __sbitmap_for_each_set(struct sbitmap *sb,
>   * @sb: Bitmap to iterate over.
>   * @fn: Callback. Should return true to continue or false to break early.
>   * @data: Pointer to pass to callback.
> - *
> - * This is inline even though it's non-trivial so that the function calls to the
> - * callback will hopefully get optimized away.
>   */
>  static inline void sbitmap_for_each_set(struct sbitmap *sb, sb_for_each_fn fn,
>  					void *data)