linux-kernel - Re: [PATCH RESEND] maple: fix incorrect rewinding in mas_empty_area

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: <4a72mtf5n4mzirudx3z2z6b72ropqs7f4kp2dlezkib4k5em56@hiw63iieahph>
Date: Thu, 18 Sep 2025 16:20:32 -0400
From: "Liam R. Howlett" <Liam.Howlett@...cle.com>
To: Gladyshev Ilya <foxido@...ido.dev>
Cc: Andrew Morton <akpm@...ux-foundation.org>, maple-tree@...ts.infradead.org,
        linux-mm@...ck.org, linux-kernel@...r.kernel.org
Subject: Re: [PATCH RESEND] maple: fix incorrect rewinding in
 mas_empty_area_rev

* Gladyshev Ilya <foxido@...ido.dev> [250918 14:26]:
> Previously, mas_empty_area_rev was rewinding to the previous node if
> some offset was cached. This could lead to incorrect results because a
> useful gap could be skipped. However, this was never triggered in the
> kernel because mm subsystem calls mas_empty_area_rev on non cached mas.

Can you please produce a test case, ideally in lib/test_maple_tree.c or
tools/testing/radix_tree/maple.c that triggers your issue?  I add all
new tests to one of these places so the error does not return.

You can build maple in tools/testing/radix_tree/ and run it to run the
tests.

It also helps understand the issue.

> 
> This patch unifies the rewind logic between mas_empty_area_rev and
> mas_empty_area, so they both rewind in their correct directions.

How are these unified?  They are still different functions..?  What is
the correct direction, in your opinion?

> 
> Signed-off-by: Gladyshev Ilya <foxido@...ido.dev>
> ---
>  lib/maple_tree.c | 10 +++++-----
>  1 file changed, 5 insertions(+), 5 deletions(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index b4ee2d29d7a9..c7790fff4825 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -5138,15 +5138,15 @@ int mas_empty_area_rev(struct ma_state *mas, unsigned long min,
>  
>  	if (mas_is_start(mas))
>  		mas_start(mas);
> -	else if ((mas->offset < 2) && (!mas_rewind_node(mas)))
> -		return -EBUSY;
>  
>  	if (unlikely(mas_is_none(mas) || mas_is_ptr(mas)))
>  		return mas_sparse_area(mas, min, max, size, false);
> -	else if (mas->offset >= 2)
> -		mas->offset -= 2;
> -	else

This does not make sense to me by inspection.
> +	else if (!mas->offset)
>  		mas->offset = mas_data_end(mas);

If we are at the start of the node, go to the end of the node.  If we
are continuing the search, why are we restarting the same node?

> +	else if (mas->offset <= mas_data_end(mas) - 2)
> +		mas->offset = mas->offset + 2;

If we are at the offset less than or equal 2 of the end of the node, we
advance two slots.  This is supposed to be going down but you are going
up?

> +	else if (!mas_skip_node(mas))
> +		return -EBUSY;

Go to the next node, which would be larger addresses or return -EBUSY?

>  
>  
>  	/* The start of the window can only be within these values. */
> 
> base-commit: cbf658dd09419f1ef9de11b9604e950bdd5c170b

This function is to find a gap from top (highest) down (to lower)
addresses.  On entry, it needs to decrement the offset or go to the
previous node.  You are resetting to start from the end of the node or
incrementing two slots.  Failing that (which will only happen when we
are within two of the end of a node), you will go to the NEXT node
which seems the wrong direction?

Can you produce a test case that shows that we are skipping a gap?

Thanks,
Liam