Re: [PATCH v2] sbitmap: don't loop for find_next_zero_bit() for !round_robin

[Omar Sandoval <osandov@osandov.com>]

On Thu, Nov 29, 2018 at 12:47:49PM -0700, Jens Axboe wrote:
> If we aren't forced to do round robin tag allocation, just use the
> allocation hint to find the index for the tag word, don't use it for the
> offset inside the word. This avoids a potential extra round trip in the
> bit looping, and since we're fetching this cacheline, we may as well
> check the whole word from the start.

Reviewed-by: Omar Sandoval <osandov@fb.com>

> Signed-off-by: Jens Axboe <axboe@kernel.dk>
> 
> ---
> 
> Since v1:
> 
> - Reset alloc_hint if we loop for the round-robin case
> - Update commit message
> 
> diff --git a/lib/sbitmap.c b/lib/sbitmap.c
> index fdd1b8aa8ac6..45cab6bbc1c7 100644
> --- a/lib/sbitmap.c
> +++ b/lib/sbitmap.c
> @@ -118,10 +118,19 @@ int sbitmap_get(struct sbitmap *sb, unsigned int alloc_hint, bool round_robin)
>  
>  	index = SB_NR_TO_INDEX(sb, alloc_hint);
>  
> +	/*
> +	 * Unless we're doing round robin tag allocation, just use the
> +	 * alloc_hint to find the right word index. No point in looping
> +	 * twice in find_next_zero_bit() for that case.
> +	 */
> +	if (round_robin)
> +		alloc_hint = SB_NR_TO_BIT(sb, alloc_hint);
> +	else
> +		alloc_hint = 0;
> +
>  	for (i = 0; i < sb->map_nr; i++) {
>  		nr = __sbitmap_get_word(&sb->map[index].word,
> -					sb->map[index].depth,
> -					SB_NR_TO_BIT(sb, alloc_hint),
> +					sb->map[index].depth, alloc_hint,
>  					!round_robin);
>  		if (nr != -1) {
>  			nr += index << sb->shift;
> @@ -129,13 +138,9 @@ int sbitmap_get(struct sbitmap *sb, unsigned int alloc_hint, bool round_robin)
>  		}
>  
>  		/* Jump to next index. */
> -		index++;
> -		alloc_hint = index << sb->shift;
> -
> -		if (index >= sb->map_nr) {
> +		alloc_hint = 0;
> +		if (++index >= sb->map_nr)
>  			index = 0;
> -			alloc_hint = 0;
> -		}
>  	}
>  
>  	return nr;
> -- 
> Jens Axboe
>