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: <pmbppturwnp55itvjqw2xukilf4z6m2mj2fjub5tmib7uy76ia@rtvg5v4ruh2t>
Date: Thu, 3 Jul 2025 02:00:37 -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> [250628 07:59]:
> 
> 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?

Ah.. ma_root is a pointer which could be a node, null, or an entry.  We
won't get here with a NULL or an entry.. because we don't need to walk
those.

So at this point, we are entering with a node which could currently be
two types; arange64 or range64.

Cheers,
Liam