[PATCH v6 2/2] erofs-utils: optimize buffer allocation logic

[Huang Jianan]

Hi Weiwen, Xiang,

在 2021/1/22 21:21, Gao Xiang 写道:
> On Fri, Jan 22, 2021 at 09:14:08PM +0800, Gao Xiang wrote:
>> Hi Weiwen,
>>
>> On Tue, Jan 19, 2021 at 01:49:51PM +0800, Hu Weiwen wrote:
>>
>> ...
>>
>>>   	bb = NULL;
>>>
>>> -	list_for_each_entry(cur, &blkh.list, list) {
>>> -		unsigned int used_before, used;
>>> +	if (!used0 || alignsize == EROFS_BLKSIZ)
>>> +		goto alloc;
>>> +
>>> +	/* try to find a most-fit mapped buffer block first */
>>> +	used_before = EROFS_BLKSIZ -
>>> +		round_up(size + required_ext + inline_ext, alignsize);
>> Honestly, after seen above I feel I'm not good at math now
>> since I smell somewhat strange of this, apart from the pending
>> patch you raised [1], the algebra is
>>
>> /* since all buffers should be aligned with alignsize */
>> erofs_off_t alignedoffset = roundup(used_before, alignsize);
>>
>> and (alignedoffset + size + required_ext + inline_ext <= EROFS_BLKSIZ)
>>
>> and why it can be equal to
>> used_before = EROFS_BLKSIZ - round_up(size + required_ext + inline_ext, alignsize);
>>
>> Could you explain this in detail if possible? for example,
>> size = 3
>> inline_ext = 62
>> alignsize = 32
>>
>> so 4096 - roundup(3 + 62, 32) = 4096 - 96 = 4000
>> but, the real used_before can be even started at 4032, since
>> alignedoffset = roundup(4032, 32) = 4032
>> 4032 + 62 = 4094 <= EROFS_BLKSIZ.
>>
>> Am I stll missing something?
>>
> Oh, the example itself is wrong, yet I still feel no good at
> this formula, e.g I'm not sure if it works for alignsize which
> cannot be divided by EROFS_BLKSIZ (although currently alignsize =
> 4 or 32)
>
> Thanks,
> Gao Xiang


We can divide several parts of data in EROFS_BLKSIZ  as follows:

____________________________________________________________________________________

|||||

|  used_before |alignedoffset|   size + required_ext + inline_ext 
|tail_data |

|________________ 
|_________________|_____________________________________|___________|

Use alignsize to represent these data:

1) alignsize * num_x = used_before + alignedoffset
2) alignsize * num_y = size + required_ext + inline_ext + tail_data
3) alignsize * num_z = EROFS_BLKSIZ

So we can get,
4) num_x + num_y = num_z

If we use
used_before = EROFS_BLKSIZ - round_up(size + required_ext + inline_ext, alignsize);
here, num_y should be an integer.

Consider the following two situations:

1) If EROFS_BLKSIZ can be divisible by alignsize, num_z is an integer. so num_x is an integer.
    The following formula can be satisfied:
    erofs_off_t alignedoffset = roundup(used_before, alignsize);
    
2）If EROFS_BLKSIZ can't be divisible by alignsize, num_z isn't an integer and num_x won't be an integer.
    The formula can't be satisfied.

So I think it should be
used_before = round_down(EROFS_BLKSIZ - size-required_ext - inline_ext , alignsize);
here.

Sorry for my poor english and figure. . .


Thanks,
Jianan

>> IMO, I don't want too hard on such math, I'd like to just use
>> used_before = EROFS_BLKSIZ - (size + required_ext + inline_ext);
>> and simply skip the bb if __erofs_battach is fail (as I said before,
>> the internal __erofs_battach can be changed, and I don't want to
>> imply that always succeed.)
>>
>> If you also agree that, I'll send out a revised version along
>> with a cleanup patch to clean up erofs_balloc() as well, which
>> is more complicated than before.
>>
>> [1] https://lore.kernel.org/r/20210121162606.8168-1-sehuww@mail.scut.edu.cn/
>>
>> Thanks,
>> Gao Xiang
>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.ozlabs.org/pipermail/linux-erofs/attachments/20210122/6ad7da64/attachment.htm>