linux-kernel - Re: [PATCH v2 4/6] maple_tree: break on convergence in mas_spanning

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 for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <vpy4kd24dq3mx2wwtiqkmxdnndlact5trv4pwn55ul2xzu4zkz@adyb5e665grg>
Date: Tue, 25 Feb 2025 10:47:55 -0500
From: "Liam R. Howlett" <Liam.Howlett@...cle.com>
To: Sidhartha Kumar <sidhartha.kumar@...cle.com>
Cc: linux-kernel@...r.kernel.org, maple-tree@...ts.infradead.org,
        linux-mm@...ck.org, akpm@...ux-foundation.org,
        richard.weiyang@...il.com
Subject: Re: [PATCH v2 4/6] maple_tree: break on convergence in
 mas_spanning_rebalance()

* Sidhartha Kumar <sidhartha.kumar@...cle.com> [250221 11:36]:
> This allows support for using the vacant height to calculate the worst
> case number of nodes needed for wr_rebalance operation.
> mas_spanning_rebalance() was seen to perform unnecessary node allocations.
> We can reduce allocations by breaking early during the rebalancing loop
> once we realize that we have ascended to a common ancestor.
> 
> Suggested-by: Liam Howlett <liam.howlett@...cle.com>
> Reviewed-by: Wei Yang <richard.weiyang@...il.com>
> Signed-off-by: Sidhartha Kumar <sidhartha.kumar@...cle.com>

Reviewed-by: Liam R. Howlett <Liam.Howlett@...cle.com>

> ---
>  lib/maple_tree.c | 19 ++++++++++++++++---
>  1 file changed, 16 insertions(+), 3 deletions(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index ef71af0529f4..4de257003251 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -2896,11 +2896,24 @@ static void mas_spanning_rebalance(struct ma_state *mas,
>  		mast_combine_cp_right(mast);
>  		mast->orig_l->last = mast->orig_l->max;
>  
> -		if (mast_sufficient(mast))
> -			continue;
> +		if (mast_sufficient(mast)) {
> +			if (mast_overflow(mast))
> +				continue;
> +
> +			if (mast->orig_l->node == mast->orig_r->node) {
> +			       /*
> +				* The data in b_node should be stored in one
> +				* node and in the tree
> +				*/
> +				slot = mast->l->offset;
> +				/* May be a new root stored in mast->bn */
> +				if (mas_is_root_limits(mast->orig_l))
> +					new_height++;
> +				break;
> +			}
>  
> -		if (mast_overflow(mast))
>  			continue;
> +		}
>  
>  		/* May be a new root stored in mast->bn */
>  		if (mas_is_root_limits(mast->orig_l)) {
> -- 
> 2.43.0
>