linux-kernel - Re: [PATCH 2/3] maple_tree: use preallocations in mas_store

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: <3342fd24-84f5-430f-8900-fd2d8ddae639@bytedance.com>
Date:   Wed, 11 Oct 2023 15:40:17 +0800
From:   Peng Zhang <zhangpeng.00@...edance.com>
To:     Sidhartha Kumar <sidhartha.kumar@...cle.com>
Cc:     akpm@...ux-foundation.org, willy@...radead.org,
        liam.howlett@...cle.com, linux-kernel@...r.kernel.org,
        maple-tree@...ts.infradead.org, linux-mm@...ck.org,
        Peng Zhang <zhangpeng.00@...edance.com>
Subject: Re: [PATCH 2/3] maple_tree: use preallocations in mas_store_gfp()



在 2023/10/11 08:17, Sidhartha Kumar 写道:
> On 10/9/23 8:03 PM, Peng Zhang wrote:
>> Hi,
>>
>> 在 2023/10/10 04:16, Sidhartha Kumar 写道:
>>> Preallocate maple nodes before call to mas_wr_store_entry(). If a new
>>> node is not needed, go directly to mas_wr_store_entry(), otherwise
>>> allocate the needed nodes and set the MA_STATE_PREALLOC flag.
>>>
>>> Signed-off-by: Sidhartha Kumar <sidhartha.kumar@...cle.com>
>>> ---
>>>   lib/maple_tree.c | 22 +++++++++++++++++++---
>>>   1 file changed, 19 insertions(+), 3 deletions(-)
>>>
>>> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
>>> index e239197a57fc..25ae66e585f4 100644
>>> --- a/lib/maple_tree.c
>>> +++ b/lib/maple_tree.c
>>> @@ -5478,17 +5478,33 @@ int mas_prealloc_calc(struct ma_wr_state *wr_mas)
>>>   int mas_store_gfp(struct ma_state *mas, void *entry, gfp_t gfp)
>>>   {
>>>       MA_WR_STATE(wr_mas, mas, entry);
>>> +    int request;
>>>       mas_wr_store_setup(&wr_mas);
>>> -    trace_ma_write(__func__, mas, 0, entry);
>>> -retry:
>>> +    wr_mas.content = mas_start(mas);
>>> +
>>> +    request = mas_prealloc_calc(&wr_mas);
>> mas_wr_store_entry() does something similar to mas_prealloc_calc().
>> Now, making it do it twice would incur additional overhead.
>> We encountered this issue while optimizing preallocation, but it
>> hasn't been resolved yet. Previously, this problem only occurred
>> when using mas_preallocate(). Now, this change would bring this
>> impact to all write operations on maple tree. What do you think
>> about it?
>>
> 
> After talking to Liam, I will have to implement the store type enum feature on the Maple Tree Work list so that mas_prealloc_calc() can start a partial walk and write that information to the enum. mas_wr_store_entry() can then read that enum to continue the walk that was already started rather than having to redo the whole walk. This could also be used in mas_preallocate(). Do you have any suggestions for the implementation of this enum?
There is another scenario where this enum can be useful,
as seen in the implementation of mas_replace_entry() in [1].
It is a faster alternative to mas_store(), but it is not safe.
If we can determine through the enum while writing the maple
tree that a faster write operation can be performed, it would
be beneficial. Some performance improvements can also be
observed in [1].

[1] https://lore.kernel.org/lkml/49f0181a-55a4-41aa-8596-877560c8b802@bytedance.com/
> 
> Thanks,
> Sid
> 
>> Thanks,
>> Peng
>>> +    if (!request)
>>> +        goto store_entry;
>>> +
>>> +    mas_node_count_gfp(mas, request, gfp);
>>> +    if (unlikely(mas_is_err(mas))) {
>>> +        mas_set_alloc_req(mas, 0);
>>> +        mas_destroy(mas);
>>> +        mas_reset(mas);
>>> +        return xa_err(mas->node);
>>> +    }
>>> +    mas->mas_flags |= MA_STATE_PREALLOC;
>>> +
>>> +store_entry:
>>>       mas_wr_store_entry(&wr_mas);
>>>       if (unlikely(mas_nomem(mas, gfp)))
>>> -        goto retry;
>>> +        goto store_entry;
>>>       if (unlikely(mas_is_err(mas)))
>>>           return xa_err(mas->node);
>>> +    trace_ma_write(__func__, mas, 0, entry);
>>>       return 0;
>>>   }
>>>   EXPORT_SYMBOL_GPL(mas_store_gfp);
>>
> 
>