Re: [PATCH v2 hotfix 6.12 1/2] maple_tree: correct tree corruption on spanning store

[Lorenzo Stoakes]

On Mon, Oct 07, 2024 at 10:47:04AM -0400, Liam R. Howlett wrote:
> * Lorenzo Stoakes <lorenzo.stoakes@xxxxxxxxxx> [241006 10:31]:
> > There has been a subtle bug present in the maple tree implementation from
> > its inception.
> >

[snip]

> > +/*
> > + * Traverse the maple tree until the offset of mas->index is reached.
> > + *
> > + * Return: Is this node actually populated with entries possessing pivots equal
> > + *         to or greater than mas->index?
> > + */
> >  static bool mas_wr_walk_index(struct ma_wr_state *wr_mas)
>
> Oh good, I'm returning a bool that was never used.

Yeah...

>
> >  {
> >  	struct ma_state *mas = wr_mas->mas;
> > @@ -3540,8 +3548,11 @@ static bool mas_wr_walk_index(struct ma_wr_state *wr_mas)
> >  		mas_wr_walk_descend(wr_mas);
> >  		wr_mas->content = mas_slot_locked(mas, wr_mas->slots,
> >  						  mas->offset);
> > -		if (ma_is_leaf(wr_mas->type))
> > -			return true;
> > +		if (ma_is_leaf(wr_mas->type)) {
> > +			unsigned long pivot = wr_mas->pivots[mas->offset];
>
> If mas->offset points to the last slot, then this will be outside the
> pivot array.  That is, there is an implied max pivot from the parent
> which may not have a pivot entry.

Yikes, you're right! Would say 'will fix' but you suggest a much better
solution overall that vastly simplifies this patch below...

>
> > +
> > +			return pivot == 0 || mas->index <= pivot;
>
> What is the pivot == 0 portion of this?  The pivot should always have a
> value, unless it's the first pivot in the tree of range 0-0, but then
> there will always be more content to copy.

As discussed in IRC, I suspect one of the tests is using data from an old
version of the maple tree where this had semantic meaning. Without this
tests fail.

However this is irrelevant now because...

>
> > +		}
> >  		mas_wr_walk_traverse(wr_mas);
> >
> >  	}
> > @@ -3701,6 +3712,7 @@ static noinline void mas_wr_spanning_store(struct ma_wr_state *wr_mas)
> >  	struct maple_big_node b_node;
> >  	struct ma_state *mas;
> >  	unsigned char height;
> > +	bool r_populated;
> >
> >  	/* Left and Right side of spanning store */
> >  	MA_STATE(l_mas, NULL, 0, 0);
> > @@ -3742,7 +3754,7 @@ static noinline void mas_wr_spanning_store(struct ma_wr_state *wr_mas)
> >  		r_mas.last++;
> >
> >  	r_mas.index = r_mas.last;
> > -	mas_wr_walk_index(&r_wr_mas);
> > +	r_populated = mas_wr_walk_index(&r_wr_mas);
> >  	r_mas.last = r_mas.index = mas->last;
> >
> >  	/* Set up left side. */
> > @@ -3766,7 +3778,7 @@ static noinline void mas_wr_spanning_store(struct ma_wr_state *wr_mas)
> >  	/* Copy l_mas and store the value in b_node. */
> >  	mas_store_b_node(&l_wr_mas, &b_node, l_mas.end);
> >  	/* Copy r_mas into b_node. */
> > -	if (r_mas.offset <= r_mas.end)
> > +	if (r_populated && r_mas.offset <= r_mas.end)
> >  		mas_mab_cp(&r_mas, r_mas.offset, r_mas.end,
> >  			   &b_node, b_node.b_end + 1);
>
> We may be able to leverage the information contained in r_mas and
> r_wr_mas to determine when contents needs to be copied.
>
> Perhaps r_mas.max > r_mas.last instead?  Where r_mas.max is the node
> max and r_mas.last is the end of the range being written.

...yes I tested this and it works :) so we can drop everything else and
turn this into a one liner.

Will respin now. Thanks!

>
> >  	else
> > --
> > 2.46.2