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 for Android: free password hash cracker in your pocket

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

Message-ID: <1b99962f-80e2-7047-acd2-c6e90c26ba81@huaweicloud.com>
Date: Wed, 18 Dec 2024 09:18:03 +0800
From: Yu Kuai <yukuai1@...weicloud.com>
To: Bart Van Assche <bvanassche@....org>, 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,
 yi.zhang@...wei.com, yangerkun@...wei.com, "yukuai (C)" <yukuai3@...wei.com>
Subject: Re: [PATCH v2 RFC 2/4] lib/sbitmap: fix shallow_depth tag allocation

Hi,

在 2024/12/18 5:47, Bart Van Assche 写道:
> 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"?

We're finding bit in the 'index' word, and pre_word_bits are the number
of bits in previous workds.

> 
>> +
>> +    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?

Yes.
> 
> Otherwise this patch looks good to me.
> 

Thanks,
Kuai

> Thanks,
> 
> Bart.
> .
>