Re: [PATCH 1/4] maple_tree: Fix get wrong data_end in mtree_lookup_walk()

[Liam R. Howlett]

* Peng Zhang <zhangpeng.00@xxxxxxxxxxxxx> [230310 13:53]:
> 
> 在 2023/3/11 01:58, Liam R. Howlett 写道:
> > * Peng Zhang <zhangpeng.00@xxxxxxxxxxxxx> [230310 09:09]:
> > > if (likely(offset > end))
> > > 	max = pivots[offset];
> > > 
> > > The above code should be changed to if (likely(offset < end)), which is
> > > correct. This affects the correctness of ma_data_end().
> > No.  The way it is written is correct.  If we are not at the last slot,
> > then we take the pivot as the max for the next level of the tree.  If we
> > are at the last slot, then the max is already the correct value.
> 
> As you said, If we are not at the last slot, we take the pivot as the max
> 
for the next level of the tree. At this time, “offset < end” is satisfied,

> but in the original code, when offset > end, take the pivot as the max.
> 
Please *think again*, it is wrong. The code may have been written
> incorrectly
> by mistake, not what you said it was written.

Sorry, yes.  That does look like a bug.

> 
> > > Now it seems
> > > that the final result will not be wrong, but it is best to change it.
> > Why is it best to change it?
> > 
> > > This patch does not change the code as above, because it simplifies the
> > > code by the way.
> > > 
> > > Signed-off-by: Peng Zhang <zhangpeng.00@xxxxxxxxxxxxx>
> > > ---
> > >   lib/maple_tree.c | 15 +++++----------
> > >   1 file changed, 5 insertions(+), 10 deletions(-)
> > > 
> > > diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> > > index 646297cae5d1..b3164266cfde 100644
> > > --- a/lib/maple_tree.c
> > > +++ b/lib/maple_tree.c
> > > @@ -3875,18 +3875,13 @@ static inline void *mtree_lookup_walk(struct ma_state *mas)
> > >   		end = ma_data_end(node, type, pivots, max);
> > >   		if (unlikely(ma_dead_node(node)))
> > >   			goto dead_node;
> > > -
> > > -		if (pivots[offset] >= mas->index)
> > > -			goto next;
> > > -
> > >   		do {
> > > -			offset++;
> > > -		} while ((offset < end) && (pivots[offset] < mas->index));
> > > -
> > > -		if (likely(offset > end))
> > > -			max = pivots[offset];
> > > +			if (pivots[offset] >= mas->index) {
> > > +				max = pivots[offset];
> > You can overflow the pivots array here because offset can actually be
> > larger than the array.  I am surprised this passes the maple tree test
> > program, but with a full node and walking to the end, it will address
> > the pivots array out of bounds.
> > 
> > I wrote it the way I did to minimize the instructions in the loop by
> > avoiding the overflow check.
> 
> It is not possible overflow pivots array, because only when
> "while (++offset < end)" is satisfied, we enter the loop body.
> So if we access pivots[offset], “offset < end” must be satisfied.
> Maybe you need to read the code to know, instead of looking at
> the diff.
> 
> The modified code looks like this:
> 
>         do {
>             if (pivots[offset] >= mas->index) {
>                 max = pivots[offset];
>                 break;
>             }
>         } while (++offset < end);
> 

Yes, you are right.  It will terminate before overflowing.

Since this is a fix, it needs a fixes tag in the commit log.  Can you
come up with a test case for this one as well?

Fixes: 54a611b60590 ("Maple Tree: add new data structure")
Reviewed-by: Liam R. Howlett <Liam.Howlett@xxxxxxxxxx>

> > > +				break;
> > > +			}
> > > +		} while (++offset < end);
> > > -next:
> > >   		slots = ma_slots(node, type);
> > >   		next = mt_slot(mas->tree, slots, offset);
> > >   		if (unlikely(ma_dead_node(node)))
> > > -- 
> > > 2.20.1
> > >