Re: [PATCH v2 RFC 2/4] lib/sbitmap: fix shallow_depth tag allocation

[Bart Van Assche <bvanassche@acm.org>]

On 12/16/24 6:40 PM, Yu Kuai wrote:
> From: Yu Kuai <yukuai3@huawei.com>
> 
> Currently, shallow_depth is used by bfq, kyber and mq-deadline, they both

both -> all

> pass in the value for the whole sbitmap, while sbitmap treats the value

treats for -> applies to

> for just one word. Which means, shallow_depth never work as expected,

work -> works

> and there really is no such functional tests to covert it.

is ... tests -> is ... test or are ... tests

covert -> cover

> Consider that callers doesn't know which word will be used, and it's

Consider -> Considering
doesn't -> don't

> diff --git a/include/linux/sbitmap.h b/include/linux/sbitmap.h
> index 189140bf11fc..92e77bc13cf6 100644
> --- a/include/linux/sbitmap.h
> +++ b/include/linux/sbitmap.h
> @@ -213,12 +213,12 @@ int sbitmap_get(struct sbitmap *sb);
>    * sbitmap_get_shallow() - Try to allocate a free bit from a &struct sbitmap,
>    * limiting the depth used from each word.
>    * @sb: Bitmap to allocate from.
> - * @shallow_depth: The maximum number of bits to allocate from a single word.
> + * @shallow_depth: The maximum number of bits to allocate from the bitmap.
>    *
>    * This rather specific operation allows for having multiple users with
>    * different allocation limits. E.g., there can be a high-priority class that
>    * uses sbitmap_get() and a low-priority class that uses sbitmap_get_shallow()
> - * with a @shallow_depth of (1 << (@sb->shift - 1)). Then, the low-priority
> + * with a @shallow_depth of (sb->depth << 1). Then, the low-priority

(sb->depth << 1) -> (sb->depth >> 1)

> diff --git a/lib/sbitmap.c b/lib/sbitmap.c
> index d3412984170c..6b8b909614a5 100644
> --- a/lib/sbitmap.c
> +++ b/lib/sbitmap.c
> @@ -208,8 +208,27 @@ static int sbitmap_find_bit_in_word(struct sbitmap_word *map,
>   	return nr;
>   }
>   
> +static unsigned int __map_depth_with_shallow(const struct sbitmap *sb,
> +					     int index,
> +					     unsigned int shallow_depth)
> +{
> +	unsigned int pre_word_bits = 0;
> +
> +	if (shallow_depth >= sb->depth)
> +		return __map_depth(sb, index);
> +
> +	if (index > 0)
> +		pre_word_bits += (index - 1) << sb->shift;

Why "index - 1" instead of "index"?

> +
> +	if (shallow_depth <= pre_word_bits)
> +		return 0;
> +
> +	return min_t(unsigned int, __map_depth(sb, index),
> +				   shallow_depth - pre_word_bits);
> +}

How about renaming pre_word_bits into lower_bound?

Otherwise this patch looks good to me.

Thanks,

Bart.