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

[Omar Sandoval <osandov@osandov.com>]

On Thu, Nov 29, 2018 at 12:34:12PM -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.

Maybe also add "We're already fetching that cache line, so we might as
well check the whole word."

> This avoids a potential extra round trip in the
> bit looping.
> 
> Signed-off-by: Jens Axboe <axboe@kernel.dk>
> 
> ---
> 
> diff --git a/lib/sbitmap.c b/lib/sbitmap.c
> index fdd1b8aa8ac6..2987b2ac8ed7 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;
> @@ -130,12 +139,8 @@ 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) {
> +		if (index >= sb->map_nr)
>  			index = 0;
> -			alloc_hint = 0;
> -		}

We need to set alloc_hint = 0 here for the round_robin case.

>  	}
>  
>  	return nr;
> 
> -- 
> Jens Axboe
>