Re: [PATCH 2/2] maple tree: Add and fix some comments

[Dev Jain]

On 27/06/25 1:34 am, Liam R. Howlett wrote:
> * Dev Jain <dev.jain@xxxxxxx> [250626 13:19]:
> > Add comments explaining the fields for maple_metadata, since "end" is
> > ambiguous and "gap" can be confused as the largest gap, whereas it
> > is actually the offset of the largest gap.
> >
> > MAPLE_ROOT_NODE is used for mt_mk_root() and mt_safe_root(), indicating
> > that it is used to mark the node as root. So fix the comment.
> That's not quite the entire story here.
>
> The first pointer in the tree may not be a node at all, and may be an
> entry.  So having that bit set tells us the root of the tree is a node,
> so the comment is correct but maybe you have a better way of expressing
> this information?

Hmm. Can you please correct me on my understanding - when we have an
empty tree, then we insert a root and can store a value there. Now when
we store the second entry, we allocate a node and make the root a node,
the root points to that node, and we store the values at offsets 0 and 1.

I am reading more to answer my own question.

> > Add comment for mas_ascend() to explain, whose min and max we are
> > trying to find. Explain that, for example, if we are already on offset
> > zero, then the parent min is mas->min, otherwise we need to walk up
> > to find the implied pivot min.
> >
> > Signed-off-by: Dev Jain <dev.jain@xxxxxxx>
> > ---
> >   include/linux/maple_tree.h | 4 ++--
> >   lib/maple_tree.c           | 9 +++++++--
> >   2 files changed, 9 insertions(+), 4 deletions(-)
> >
> > diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h
> > index 9ef129038224..bafe143b1f78 100644
> > --- a/include/linux/maple_tree.h
> > +++ b/include/linux/maple_tree.h
> > @@ -75,8 +75,8 @@
> >    * searching for gaps or any other code that needs to find the end of the data.
> >    */
> >   struct maple_metadata {
> > -	unsigned char end;
> > -	unsigned char gap;
> > +	unsigned char end;	/* end of data */
> > +	unsigned char gap;	/* offset of largest gap */
> Thanks.
>
> >   };
> >   
> >   /*
> > diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> > index 6c89e6790fb5..e4735ccd06f2 100644
> > --- a/lib/maple_tree.c
> > +++ b/lib/maple_tree.c
> > @@ -338,7 +338,7 @@ static inline void mte_set_node_dead(struct maple_enode *mn)
> >   	smp_wmb(); /* Needed for RCU */
> >   }
> >   
> > -/* Bit 1 indicates the root is a node */
> > +/* Bit 1 indicates the node is the root */
> >   #define MAPLE_ROOT_NODE			0x02
> >   /* maple_type stored bit 3-6 */
> >   #define MAPLE_ENODE_TYPE_SHIFT		0x03
> > @@ -1053,7 +1053,7 @@ static inline void mte_set_gap(const struct maple_enode *mn,
> >    * mas_ascend() - Walk up a level of the tree.
> >    * @mas: The maple state
> >    *
> > - * Sets the @mas->max and @mas->min to the correct values when walking up.  This
> > + * Sets the @mas->max and @mas->min for the parent node of mas->node.  This
> >    * may cause several levels of walking up to find the correct min and max.
> >    * May find a dead node which will cause a premature return.
> >    * Return: 1 on dead node, 0 otherwise
> > @@ -1098,6 +1098,11 @@ static int mas_ascend(struct ma_state *mas)
> >   
> >   	min = 0;
> >   	max = ULONG_MAX;
> > +
> > +	/*
> > +	 * !mas->offset => parent node min == mas->min. mas->offset => need
> > +	 * to walk up to find the implied pivot min.
> The => arrows here are a bit hard to parse, especially mixed with ==.
> Maybe use more words?

Okay.

> > +	 */
> >   	if (!mas->offset) {
> >   		min = mas->min;
> >   		set_min = true;
> > --
> > 2.30.2