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: <3yrtyxb6mwtwrov4vngtcy34pl77easph6hueo5m3nxlqx6o5c@f4frvl5cxees>
Date: Thu, 26 Jun 2025 15:58:03 -0400
From: "Liam R. Howlett" <Liam.Howlett@...cle.com>
To: Dev Jain <dev.jain@....com>
Cc: 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()

* 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.

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).

Thanks,
Liam