linux-kernel - Re: [PATCH 1/2] maple tree: Clean up mtree_range

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: <58be76a0-8fc3-4d5d-959e-eabe7664e277@arm.com>
Date: Sat, 28 Jun 2025 17:27:56 +0530
From: Dev Jain <dev.jain@....com>
To: "Liam R. Howlett" <Liam.Howlett@...cle.com>, akpm@...ux-foundation.org,
 richard.weiyang@...il.com, maple-tree@...ts.infradead.org,
 linux-mm@...ck.org, linux-kernel@...r.kernel.org
Subject: Re: [PATCH 1/2] maple tree: Clean up mtree_range_walk()


On 27/06/25 1:28 am, Liam R. Howlett wrote:
> * Dev Jain <dev.jain@....com> [250626 13:19]:
>> The special casing for offset == 0 is being done because min will stay
>> mas->min in this case. So refactor the code to use the while loop for
>> setting the max and getting the corresponding offset, and only set the
>> min for offset > 0.
>>
>> Signed-off-by: Dev Jain <dev.jain@....com>
>> ---
>>   lib/maple_tree.c | 11 +++--------
>>   1 file changed, 3 insertions(+), 8 deletions(-)
>>
>> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
>> index 0e85e92c5375..6c89e6790fb5 100644
>> --- a/lib/maple_tree.c
>> +++ b/lib/maple_tree.c
>> @@ -2770,13 +2770,8 @@ static inline void *mtree_range_walk(struct ma_state *mas)
>>   		end = ma_data_end(node, type, pivots, max);
>>   		prev_min = min;
>>   		prev_max = max;
>> -		if (pivots[0] >= mas->index) {
>> -			offset = 0;
>> -			max = pivots[0];
>> -			goto next;
>> -		}
>>   
> This new line should be dropped.
>
>> -		offset = 1;
>> +		offset = 0;
>>   		while (offset < end) {
> This should now be a do {} while();
>
>>   			if (pivots[offset] >= mas->index) {
>>   				max = pivots[offset];
>> @@ -2784,9 +2779,9 @@ static inline void *mtree_range_walk(struct ma_state *mas)
>>   			}
>>   			offset++;
>>   		}
> There should be a new line here.
>
>> +		if (likely(offset))
>> +			min = pivots[offset - 1] + 1;
>>   
>> -		min = pivots[offset - 1] + 1;
>> -next:
>>   		slots = ma_slots(node, type);
>>   		next = mt_slot(mas->tree, slots, offset);
>>   		if (unlikely(ma_dead_node(node)))
>> -- 
>> 2.30.2
>>
> The current way will check pivot 0, then skip the main loop.  Pivot 0
> has an equal chance of being the range you are looking for, but that
> probability increases based on a lower number of entries in the node.
> The root node, which we always pass through, can have as little as two
> entries, so then it's 50/50 you want pivot 0.

My understanding of the tree currently is that ma_root is a single slot.
Or can it be a normal node with 31 slots?

>
> With the way you've written it, it will check offset < end (which will
> always be the case for the first time), then do the same work as the
> out-of-loop check, then check offset an extra time after the loop.
>
> If it's written with a do {} while, the initial check of offset < end is
> avoided, but you will end up checking offset an extra time to see if min
> needs to be set.
>
> If pivot 0 is NOT the entry you want, then the current code will check
> pivot 0, then execute the loop one less time.  In the even of a root
> node with 2 entries, it will not enter the loop at all.
>
> So, the way it is written is less code execution by avoiding unnecessary
> assignment of min and checks (of offset == 0 and offset < end).

Thank you for your detailed explanation. I will have to read more to
understand what you have written : )

>
> Thanks,
> Liam