linux-kernel - Re: [PATCH v2 1/2] lib/sbitmap: convert 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] [day] [month] [year] [list]

Message-ID: <12f8070a-5358-af01-8535-e94405bea931@huaweicloud.com>
Date: Fri, 1 Aug 2025 15:44:24 +0800
From: Yu Kuai <yukuai1@...weicloud.com>
To: Yu Kuai <yukuai1@...weicloud.com>, Jan Kara <jack@...e.cz>
Cc: yukuai@...nel.org, axboe@...nel.dk, akpm@...ux-foundation.org,
 yang.yang@...o.com, dlemoal@...nel.org, ming.lei@...hat.com,
 linux-block@...r.kernel.org, linux-kernel@...r.kernel.org,
 yi.zhang@...wei.com, yangerkun@...wei.com, johnny.chenyi@...wei.com,
 Omar Sandoval <osandov@...com>, "yukuai (C)" <yukuai3@...wei.com>
Subject: Re: [PATCH v2 1/2] lib/sbitmap: convert shallow_depth from one word
 to the whole sbitmap

Hi,

在 2025/08/01 8:24, Yu Kuai 写道:
> Hi,
> 
> 在 2025/08/01 0:27, Jan Kara 写道:
>> On Thu 31-07-25 10:38:58, Yu Kuai wrote:
>>> Hi,
>>>
>>> 在 2025/07/31 2:24, Yu Kuai 写道:
>>>> hi, Jan!
>>>>
>>>> 在 2025/7/30 21:03, Jan Kara 写道:
>>>>> I think having two APIs will be even more confusing than the current
>>>>> state.
>>>>> But as I wrote I think you can have API to specify shallow depth in 
>>>>> total
>>>>> size and in sbitmap_queue_get_shallow() do:
>>>>>
>>>>> shallow_per_word = (shallow_depth << sb->shift) / sb->depth;
>>> In order to consider the last word, I think we should use __map_depth()
>>> here.
>>
>> Right.
>>
>>>>> rounding_index = shallow_depth - shallow_per_word * sb->depth;
>>> And then it's not possible to calculate this rounding index easily. How
>>> about following, although the reminder handling is not perfect.
>>>
>>>   static unsigned int __map_depth_with_shallow(const struct sbitmap *sb,
>>>                                               int index,
>>>                                               unsigned int 
>>> shallow_depth)
>>>   {
>>>          unsigned int word_depth = __map_depth(sb, index);
>>>          unsigned int shallow_word_depth = word_depth * shallow_depth;
>>>          unsigned reminder = do_div(shallow_word_depth, sb->depth);
>>>
>>>          if (reminder && !(index & 0x1))
>>
>> Well, why not:
>>     if (remainder > index)
> Do you mean reminder > index * shallow_depth? This looks correct, and
> with the consideration for the last word:
> 
> if (index == sb->map_nr - 1)
>      shallow_word_depth = max(shallow_word_depth, 1);
> else if (reminder > index * shallow_depth)

Sorry there is a mistake, should use the word_depth here, following is
an example for 4 word sbitmap(64+64+64+32), I do the math manually, and
the results look perfect :)

| shallow_depth | word0  | word1  | word2  | word3 | total |
| ------------- | ------ | ------ | ------ | ----- | ----- |
| 224           | 64     | 64     | 64     | 32    | 224   |
| 112           | 32     | 32     | 32     | 16    | 112   |
| 113           | 32 + 1 | 32     | 32     | 16    | 113   |
| 114           | 32 + 1 | 32 + 1 | 32     | 16    | 114   |
| 115           | 32 + 1 | 32 + 1 | 32 + 1 | 16    | 115   |
| 116           | 33     | 33     | 33     | 16+1  | 116   |
>      shallow_word_depth++;
> 
> Thanks,
> Kuai
> 
>> ?
>>
>> That should accurately distribute the remainder across the remaining 
>> words,
>> shouldn't it?
>>
>>>                  shallow_word_depth++;
>>>
>>>          return shallow_word_depth;
>>>   }
>>
>>                                 Honza
>>
> 
> .
>