* 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
> > >
