Re: [PATCH] maple_tree: Fix mas_prev() state separation code

[Liam R. Howlett]

* Kees Cook <keescook@xxxxxxxxxxxx> [231207 16:04]:
> On Thu, Dec 07, 2023 at 02:33:19PM -0500, Liam R. Howlett wrote:
> > mas_prev() was setting the ma_underflow condition when the limit was
> > reached and not when the limit was attempting to go lower.  This
> > resulted in the incorrect behaviour on subsequent actions.
> > 
> > This commit fixes the status setting to only set ma_underflow when the
> > lower limit is attempted to be decremented, and modifies the testing to
> > ensure that's the case.
> > 
> > Signed-off-by: Liam R. Howlett <Liam.Howlett@xxxxxxxxxx>
> 
> Is this is related to the report[1] I forwarded? If so, please add these tags
> too:
> 
>  Reported-by: Linux Kernel Functional Testing <lkft@xxxxxxxxxx>
>  Closes: https://lore.kernel.org/all/CA+G9fYs-j2FYZSFSVZj48mgoM9gQd4-7M2mu2Ez3D1DqDdW2bQ@xxxxxxxxxxxxxx/ [1]
> 

Ah, yes it is.  I missed these tags. Sorry about that.

I have another patch to send in regards to this area on the
mmap_region() side but it's less urgent.  I'll Cc you on that one as
well.


> Thanks either way!
> 
> -Kees
> 
> > ---
> > 
> > Andrew,
> > 
> > This should be clean to squash into 7f79fdb1d94d7 ("maple_tree: separate
> > ma_state node from status.") which is currently in your mm-unstable
> > branch.
> > 
> > Thanks,
> > Liam
> > 
> > 
> >  lib/maple_tree.c      | 16 ++++++++++++----
> >  lib/test_maple_tree.c |  9 +++++++--
> >  2 files changed, 19 insertions(+), 6 deletions(-)
> > 
> > diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> > index 89f8d21602774..47f2a7a973852 100644
> > --- a/lib/maple_tree.c
> > +++ b/lib/maple_tree.c
> > @@ -4432,6 +4432,9 @@ static void *mas_prev_slot(struct ma_state *mas, unsigned long min, bool empty)
> >  		mas->last = mas->index - 1;
> >  		mas->index = mas_safe_min(mas, pivots, mas->offset);
> >  	} else  {
> > +		if (mas->index <= min)
> > +			goto underflow;
> > +
> >  		if (mas_prev_node(mas, min)) {
> >  			mas_rewalk(mas, save_point);
> >  			goto retry;
> > @@ -4452,15 +4455,15 @@ static void *mas_prev_slot(struct ma_state *mas, unsigned long min, bool empty)
> >  	if (unlikely(mas_rewalk_if_dead(mas, node, save_point)))
> >  		goto retry;
> >  
> > -	if (mas->index <= min)
> > -		mas->status = ma_underflow;
> >  
> >  	if (likely(entry))
> >  		return entry;
> >  
> >  	if (!empty) {
> > -		if (mas_is_underflow(mas))
> > +		if (mas->index <= min) {
> > +			mas->status = ma_underflow;
> >  			return NULL;
> > +		}
> >  
> >  		goto again;
> >  	}
> > @@ -4596,7 +4599,7 @@ static void *mas_next_slot(struct ma_state *mas, unsigned long max, bool empty)
> >  		if (unlikely(mas_rewalk_if_dead(mas, node, save_point)))
> >  			goto retry;
> >  
> > -		if (pivot >= max) {
> > +		if (pivot >= max) { /* Was at the limit, next will extend beyond */
> >  			mas->status = ma_overflow;
> >  			return NULL;
> >  		}
> > @@ -4611,6 +4614,11 @@ static void *mas_next_slot(struct ma_state *mas, unsigned long max, bool empty)
> >  		else
> >  			mas->last = mas->max;
> >  	} else  {
> > +		if (mas->last >= max) {
> > +			mas->status = ma_overflow;
> > +			return NULL;
> > +		}
> > +
> >  		if (mas_next_node(mas, node, max)) {
> >  			mas_rewalk(mas, save_point);
> >  			goto retry;
> > diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c
> > index 15fbeb788f3ac..29185ac5c727f 100644
> > --- a/lib/test_maple_tree.c
> > +++ b/lib/test_maple_tree.c
> > @@ -3294,8 +3294,8 @@ static noinline void __init check_state_handling(struct maple_tree *mt)
> >  	MT_BUG_ON(mt, mas.last != 0x1500);
> >  	MT_BUG_ON(mt, !mas_is_active(&mas));
> >  
> > -	/* next:active ->active */
> > -	entry = mas_next(&mas, ULONG_MAX);
> > +	/* next:active ->active (spanning limit) */
> > +	entry = mas_next(&mas, 0x2100);
> >  	MT_BUG_ON(mt, entry != ptr2);
> >  	MT_BUG_ON(mt, mas.index != 0x2000);
> >  	MT_BUG_ON(mt, mas.last != 0x2500);
> > @@ -3360,6 +3360,11 @@ static noinline void __init check_state_handling(struct maple_tree *mt)
> >  	MT_BUG_ON(mt, entry != ptr);
> >  	MT_BUG_ON(mt, mas.index != 0x1000);
> >  	MT_BUG_ON(mt, mas.last != 0x1500);
> > +	MT_BUG_ON(mt, !mas_is_active(&mas)); /* spanning limit */
> > +	entry = mas_prev(&mas, 0x1200); /* underflow */
> > +	MT_BUG_ON(mt, entry != NULL);
> > +	MT_BUG_ON(mt, mas.index != 0x1000);
> > +	MT_BUG_ON(mt, mas.last != 0x1500);
> >  	MT_BUG_ON(mt, !mas_is_underflow(&mas));
> >  
> >  	/* prev:underflow -> underflow (lower limit) spanning end range */
> > -- 
> > 2.40.1
> > 
> 
> -- 
> Kees Cook