[0/2] maple_tree: Fix mas_prev() state regression.

Message

Liam R. Howlett Sept. 21, 2023, 6:12 p.m. UTC

Pedro Falcato contacted me on IRC with an mprotect regression which was
bisected back to the iterator changes for maple tree.  Root cause
analysis showed the mas_prev() running off the end of the VMA space
(previous from 0) followed by mas_find(), would skip the first value.

This patch set introduces maple state underflow/overflow so the sequence
of calls on the maple state will return what the user expects.

Liam R. Howlett (2):
  maple_tree: Add mas_active() to detect in-tree walks
  maple_tree: Add MAS_UNDERFLOW and MAS_OVERFLOW states

 include/linux/maple_tree.h |  11 ++
 lib/maple_tree.c           | 221 +++++++++++++++++++++++++++----------
 lib/test_maple_tree.c      |  87 ++++++++++++---
 3 files changed, 246 insertions(+), 73 deletions(-)

Comments

Andrew Morton Sept. 21, 2023, 6:25 p.m. UTC | #1

On Thu, 21 Sep 2023 14:12:34 -0400 "Liam R. Howlett" <[e-mail]> wrote:

> Pedro Falcato contacted me on IRC with an mprotect regression which was
> bisected back to the iterator changes for maple tree.  Root cause
> analysis showed the mas_prev() running off the end of the VMA space
> (previous from 0) followed by mas_find(), would skip the first value.
> 
> This patch set introduces maple state underflow/overflow so the sequence
> of calls on the maple state will return what the user expects.

It isn't clear what are the user-visible effects of this flaw?  Please
send this along and I'll paste it in.

Patch 1 should be titled "Add mas_is_active ...".

And patch 1 should have had cc:stable in the changelog.

It's [e-mail], although [e-mail] works just fine.

Liam R. Howlett Sept. 21, 2023, 6:53 p.m. UTC | #2

* Andrew Morton <[e-mail]> [230921 14:25]:
> On Thu, 21 Sep 2023 14:12:34 -0400 "Liam R. Howlett" <[e-mail]> wrote:
> 
> > Pedro Falcato contacted me on IRC with an mprotect regression which was
> > bisected back to the iterator changes for maple tree.  Root cause
> > analysis showed the mas_prev() running off the end of the VMA space
> > (previous from 0) followed by mas_find(), would skip the first value.
> > 
> > This patch set introduces maple state underflow/overflow so the sequence
> > of calls on the maple state will return what the user expects.
> 
> It isn't clear what are the user-visible effects of this flaw?  Please
> send this along and I'll paste it in.


User may notice that mas_prev() or mas_next() calls that result in going
outside of the limit passed to the call will cause incorrect returns on
subsequent calls using that maple state, such as mas_find() skipping an
entry.

> 
> Patch 1 should be titled "Add mas_is_active ...".

Oh yes, sorry.

> 
> And patch 1 should have had cc:stable in the changelog.

Ah, I sent the series to stable but didn't add that to the changelog.
I'll do that in v2 as it seems I need to update patch 2 anyways.

> 
> It's [e-mail], although [e-mail] works just fine.

Matthew Wilcox Sept. 21, 2023, 7:23 p.m. UTC | #3

On Thu, Sep 21, 2023 at 02:53:30PM -0400, Liam R. Howlett wrote:
> * Andrew Morton <[e-mail]> [230921 14:25]:
> > On Thu, 21 Sep 2023 14:12:34 -0400 "Liam R. Howlett" <[e-mail]> wrote:
> > 
> > > Pedro Falcato contacted me on IRC with an mprotect regression which was
> > > bisected back to the iterator changes for maple tree.  Root cause
> > > analysis showed the mas_prev() running off the end of the VMA space
> > > (previous from 0) followed by mas_find(), would skip the first value.
> > > 
> > > This patch set introduces maple state underflow/overflow so the sequence
> > > of calls on the maple state will return what the user expects.
> > 
> > It isn't clear what are the user-visible effects of this flaw?  Please
> > send this along and I'll paste it in.
> 
> 
> User may notice that mas_prev() or mas_next() calls that result in going
> outside of the limit passed to the call will cause incorrect returns on
> subsequent calls using that maple state, such as mas_find() skipping an
> entry.

When Andrew says "User visible" he means "userspace visible".  Not
"in kernel user visible".  What are the _consequences_.

I'd say that if the user maps something at address 0, mprotect() can
then fail to ... or something.

Andrew Morton Sept. 21, 2023, 11:27 p.m. UTC | #4

On Thu, 21 Sep 2023 20:23:11 +0100 Matthew Wilcox <[e-mail]> wrote:

> > > It isn't clear what are the user-visible effects of this flaw?  Please
> > > send this along and I'll paste it in.
> > 
> > 
> > User may notice that mas_prev() or mas_next() calls that result in going
> > outside of the limit passed to the call will cause incorrect returns on
> > subsequent calls using that maple state, such as mas_find() skipping an
> > entry.
> 
> When Andrew says "User visible" he means "userspace visible".  Not
> "in kernel user visible".  What are the _consequences_.

Thanks ;)

We have a Link:
(https://gist.github.com/heatd/85d2971fae1501b55b6ea401fbbe485b) but it
takes us to the reproducer code.  If it took us to Pedro's initial bug
report then the sun would shine and birds would sing.

Liam R. Howlett Sept. 21, 2023, 11:34 p.m. UTC | #5

* Andrew Morton <[e-mail]> [230921 19:27]:
> On Thu, 21 Sep 2023 20:23:11 +0100 Matthew Wilcox <[e-mail]> wrote:
> 
> > > > It isn't clear what are the user-visible effects of this flaw?  Please
> > > > send this along and I'll paste it in.
> > > 
> > > 
> > > User may notice that mas_prev() or mas_next() calls that result in going
> > > outside of the limit passed to the call will cause incorrect returns on
> > > subsequent calls using that maple state, such as mas_find() skipping an
> > > entry.
> > 
> > When Andrew says "User visible" he means "userspace visible".  Not
> > "in kernel user visible".  What are the _consequences_.
> 
> Thanks ;)
> 
> We have a Link:
> (https://gist.github.com/heatd/85d2971fae1501b55b6ea401fbbe485b) but it
> takes us to the reproducer code.  If it took us to Pedro's initial bug
> report then the sun would shine and birds would sing.
> 

I don't think the irc channel is logged so I'll respin with a cleaner
changelog for both patches and the subject of patch 1.

Thanks,
Liam

Pedro Falcato Sept. 21, 2023, 11:41 p.m. UTC | #6

On Fri, Sep 22, 2023 at 12:34 AM Liam R. Howlett
<[e-mail]> wrote:
>
> * Andrew Morton <[e-mail]> [230921 19:27]:
> > On Thu, 21 Sep 2023 20:23:11 +0100 Matthew Wilcox <[e-mail]> wrote:
> >
> > > > > It isn't clear what are the user-visible effects of this flaw?  Please
> > > > > send this along and I'll paste it in.
> > > >
> > > >
> > > > User may notice that mas_prev() or mas_next() calls that result in going
> > > > outside of the limit passed to the call will cause incorrect returns on
> > > > subsequent calls using that maple state, such as mas_find() skipping an
> > > > entry.
> > >
> > > When Andrew says "User visible" he means "userspace visible".  Not
> > > "in kernel user visible".  What are the _consequences_.
> >
> > Thanks ;)
> >
> > We have a Link:
> > (https://gist.github.com/heatd/85d2971fae1501b55b6ea401fbbe485b) but it
> > takes us to the reproducer code.  If it took us to Pedro's initial bug
> > report then the sun would shine and birds would sing.
> >
>
> I don't think the irc channel is logged so I'll respin with a cleaner
> changelog for both patches and the subject of patch 1.

FYI:

The original distro bug report: https://bugs.archlinux.org/task/79656
The original userspace program bug report:
https://github.com/cebix/macemu/issues/271

(and yes, this is my fault, I should've raised this on the ML with the
regression tracker and all, but I tried to write my own fix then
realized it was trickier than it looked and pinged Liam)

Liam R. Howlett Sept. 21, 2023, 11:51 p.m. UTC | #7

* Pedro Falcato <[e-mail]> [230921 19:41]:
> On Fri, Sep 22, 2023 at 12:34 AM Liam R. Howlett
> <[e-mail]> wrote:
> >
> > * Andrew Morton <[e-mail]> [230921 19:27]:
> > > On Thu, 21 Sep 2023 20:23:11 +0100 Matthew Wilcox <[e-mail]> wrote:
> > >
> > > > > > It isn't clear what are the user-visible effects of this flaw?  Please
> > > > > > send this along and I'll paste it in.
> > > > >
> > > > >
> > > > > User may notice that mas_prev() or mas_next() calls that result in going
> > > > > outside of the limit passed to the call will cause incorrect returns on
> > > > > subsequent calls using that maple state, such as mas_find() skipping an
> > > > > entry.
> > > >
> > > > When Andrew says "User visible" he means "userspace visible".  Not
> > > > "in kernel user visible".  What are the _consequences_.
> > >
> > > Thanks ;)
> > >
> > > We have a Link:
> > > (https://gist.github.com/heatd/85d2971fae1501b55b6ea401fbbe485b) but it
> > > takes us to the reproducer code.  If it took us to Pedro's initial bug
> > > report then the sun would shine and birds would sing.
> > >
> >
> > I don't think the irc channel is logged so I'll respin with a cleaner
> > changelog for both patches and the subject of patch 1.
> 
> FYI:
> 
> The original distro bug report: https://bugs.archlinux.org/task/79656
> The original userspace program bug report:
> https://github.com/cebix/macemu/issues/271
> 
> (and yes, this is my fault, I should've raised this on the ML with the
> regression tracker and all, but I tried to write my own fix then
> realized it was trickier than it looked and pinged Liam)

No problem at all, but since the links are available I will put them
into the changelog.

Thanks,
Liam