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

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

[Jens Axboe]

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.

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;
-		}
 	}
 
 	return nr;

-- 
Jens Axboe

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

[Omar Sandoval]

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
> 

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

[Jens Axboe]

On 11/29/18 12:42 PM, Omar Sandoval wrote:
> 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."

Sure, will add.

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

Good point, does need a reset for the loop for that case.

-- 
Jens Axboe