Re: [PATCH V2 02/20] sbitmap: introduce __sbitmap_for_each_set()

[Bart Van Assche <Bart.VanAssche@xxxxxxx>]

On Sat, 2017-08-05 at 14:56 +0800, Ming Lei wrote:
> /**
>   * sbitmap_for_each_set() - Iterate over each set bit in a &struct sbitmap.
> + * @off: Offset to iterate from
>   * @sb: Bitmap to iterate over.
>   * @fn: Callback. Should return true to continue or false to break early.
>   * @data: Pointer to pass to callback.

Using 'off' as the name for the new argument seems confusing to me since that
argument starts from zero and is not an offset relative to anything. Please
consider to use 'start' as the name for this argument.

> -static inline void sbitmap_for_each_set(struct sbitmap *sb, sb_for_each_fn fn,
> -					void *data)
> +static inline void __sbitmap_for_each_set(struct sbitmap *sb,
> +					  unsigned int off,
> +					  sb_for_each_fn fn, void *data)
>  {
> -	unsigned int i;
> +	unsigned int index = SB_NR_TO_INDEX(sb, off);

Is it really useful to rename 'i' into 'index'? I think that change makes this
patch harder to read than necessary.

> +	unsigned int nr = SB_NR_TO_BIT(sb, off);
> +	unsigned int scanned = 0;
>  
> -	for (i = 0; i < sb->map_nr; i++) {
> -		struct sbitmap_word *word = &sb->map[i];
> -		unsigned int off, nr;
> +	while (1) {

Sorry but this change looks incorrect to me. I think the following two tests
have to be performed before the while loop starts to avoid triggering an
out-of-bounds reference of sb->map[]:
* Whether or not sb->map_nr is zero.
* Whether or not index >= sb->map_nr. I propose to start iterating from the
  start of @sb in this case.

Additionally, the new loop in __sbitmap_for_each_set() looks more complicated
and more fragile to me than necessary. How about using the code below? That
code needs one local variable less than your implementation.

static inline void __sbitmap_for_each_set(struct sbitmap *sb,
					  const unsigned int start,
					  sb_for_each_fn fn, void *data)
{
	unsigned int i = start >> sb->shift;
	unsigned int nr = start & ((1 << sb->shift) - 1);
	bool cycled = false;

	if (!sb->map_nr)
		return;

	if (unlikely(i >= sb->map_nr)) {
		i = 0;
		nr = 0;
	}

	while (true) {
		struct sbitmap_word *word = &sb->map[i];
		unsigned int off;

		off = i << sb->shift;
		while (1) {
			nr = find_next_bit(&word->word, word->depth, nr);
			if (cycled && off + nr >= start)
				return;

			if (nr >= word->depth)
				break;

			if (!fn(sb, off + nr, data))
				return;

			nr++;
		}
		if (++i >= sb->map_nr) {
			cycled = true;
			i = 0;
		}
		nr = 0;
	}
}

Thanks,

Bart.