linux-next.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
* [PATCH] maple_tree: Fix mas_prev() state separation code
       [not found] <20231207014104.n6vul2ylgqjnsfia@revolve>
@ 2023-12-07 19:33 ` Liam R. Howlett
  2023-12-07 21:04   ` Kees Cook
  0 siblings, 1 reply; 3+ messages in thread
From: Liam R. Howlett @ 2023-12-07 19:33 UTC (permalink / raw)
  To: Andrew Morton, Kees Cook
  Cc: maple-tree, linux-mm, linux-kernel, Mark Brown, Naresh Kamboju,
	linux-kselftest, Linux ARM, kft-triage, regressions, Will Deacon,
	Catalin Marinas, Dan Carpenter, Eric Biederman, linux-next,
	Liam R. Howlett

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@oracle.com>
---

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


^ permalink raw reply related	[flat|nested] 3+ messages in thread
* Re: [PATCH] maple_tree: Fix mas_prev() state separation code
  2023-12-07 19:33 ` [PATCH] maple_tree: Fix mas_prev() state separation code Liam R. Howlett
@ 2023-12-07 21:04   ` Kees Cook
  2023-12-08 17:54     ` Liam R. Howlett
  0 siblings, 1 reply; 3+ messages in thread
From: Kees Cook @ 2023-12-07 21:04 UTC (permalink / raw)
  To: Liam R. Howlett
  Cc: Andrew Morton, maple-tree, linux-mm, linux-kernel, Mark Brown,
	Naresh Kamboju, linux-kselftest, Linux ARM, kft-triage,
	regressions, Will Deacon, Catalin Marinas, Dan Carpenter,
	Eric Biederman, linux-next

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@oracle.com>

Is this is related to the report[1] I forwarded? If so, please add these tags
too:

 Reported-by: Linux Kernel Functional Testing <lkft@linaro.org>
 Closes: https://lore.kernel.org/all/CA+G9fYs-j2FYZSFSVZj48mgoM9gQd4-7M2mu2Ez3D1DqDdW2bQ@mail.gmail.com/ [1]

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

^ permalink raw reply	[flat|nested] 3+ messages in thread
* Re: [PATCH] maple_tree: Fix mas_prev() state separation code
  2023-12-07 21:04   ` Kees Cook
@ 2023-12-08 17:54     ` Liam R. Howlett
  0 siblings, 0 replies; 3+ messages in thread
From: Liam R. Howlett @ 2023-12-08 17:54 UTC (permalink / raw)
  To: Kees Cook
  Cc: Andrew Morton, maple-tree, linux-mm, linux-kernel, Mark Brown,
	Naresh Kamboju, linux-kselftest, Linux ARM, kft-triage,
	regressions, Will Deacon, Catalin Marinas, Dan Carpenter,
	Eric Biederman, linux-next

* Kees Cook <keescook@chromium.org> [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@oracle.com>
> 
> Is this is related to the report[1] I forwarded? If so, please add these tags
> too:
> 
>  Reported-by: Linux Kernel Functional Testing <lkft@linaro.org>
>  Closes: https://lore.kernel.org/all/CA+G9fYs-j2FYZSFSVZj48mgoM9gQd4-7M2mu2Ez3D1DqDdW2bQ@mail.gmail.com/ [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

^ permalink raw reply	[flat|nested] 3+ messages in thread
end of thread, other threads:[~2023-12-08 17:54 UTC | newest]

Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
     [not found] <20231207014104.n6vul2ylgqjnsfia@revolve>
2023-12-07 19:33 ` [PATCH] maple_tree: Fix mas_prev() state separation code Liam R. Howlett
2023-12-07 21:04   ` Kees Cook
2023-12-08 17:54     ` Liam R. Howlett

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).