linux-kernel - Re: [PATCH v2 RFC 2/4] lib/sbitmap: fix shallow

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <698a01e6-cb03-43a2-a0f1-5c8555dea8c1@acm.org>
Date: Tue, 17 Dec 2024 13:47:11 -0800
From: Bart Van Assche <bvanassche@....org>
To: Yu Kuai <yukuai1@...weicloud.com>, axboe@...nel.dk,
 akpm@...ux-foundation.org, ming.lei@...hat.com, yang.yang@...o.com,
 osandov@...com, paolo.valente@...aro.org
Cc: linux-block@...r.kernel.org, linux-kernel@...r.kernel.org,
 yukuai3@...wei.com, yi.zhang@...wei.com, yangerkun@...wei.com
Subject: Re: [PATCH v2 RFC 2/4] lib/sbitmap: fix shallow_depth tag allocation

On 12/16/24 6:40 PM, Yu Kuai wrote:
> From: Yu Kuai <yukuai3@...wei.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.