Skip to contentSkip to conversation

maple_tree: Fix mas_prev() state regression.

PATCH Applied Liam R. Howlett 4 participants 12 messages Sep 21, 2023

Subsystems (3)

v1 of 2 Applied 2/2 Latest is v2 →

lore
Share & tools
lore
#0 lore raw

cover maple_tree: Fix mas_prev() state regression.

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(-)
Signature · 1 line
2.39.2
#1 lore raw

PATCH 1/2 maple_tree: Add mas_active() to detect in-tree walks

Instead of constantly checking each possibility of the maple state, create a fast path that will skip over checking unlikely states.

---
 include/linux/maple_tree.h | 9 +++++++++
 1 file changed, 9 insertions(+)
include/linux/maple_tree.h +9 -0
index e41c70ac7744..f66f5f78f8cf 100644
@@ -511,6 +511,15 @@ static inline bool mas_is_paused(const struct ma_state *mas)
 	return mas->node == MAS_PAUSE;
 }
 
+/* Check if the mas is pointing to a node or not */
+static inline bool mas_is_active(struct ma_state *mas)
+{
+	if ((unsigned long)mas->node >= MAPLE_RESERVED_RANGE)
+		return true;
+
+	return false;
+}
+
 /**
  * mas_reset() - Reset a Maple Tree operation state.
  * @mas: Maple Tree operation state.
Signature · 1 line
2.39.2
#2 lore raw

PATCH 2/2 maple_tree: Add MAS_UNDERFLOW and MAS_OVERFLOW states

In reply to Liam R. Howlett

When updating the maple tree iterator to avoid rewalks, an issue was introduced when shifting beyond the limits. This can be seen by trying to go to the previous address of 0, which would set the maple node to MAS_NONE and keep the range as the last entry.

Subsequent calls to mas_find() would then search upwards from mas->last and skip the value at mas->index/mas->last. This showed up as a bug in mprotect which skips the actual VMA at the current range after attempting to go to the previous VMA from 0.

Since MAS_NONE is used for handling of the maple tree when it's a single entry at 0 (just a pointer), changing the handling of MAS_NONE in mas_find() would make the code more complicated and error prone. Furthermore, there was no way to tell which limit was hit, and thus which action to take (next or the entry at the current range).

This solution is to add two states to track what happened with the previous iterator action. This allows for the expected behaviour of the next command to return the correct item (either the item at the range requested, or the next/previous).

Tests are also added and updated accordingly.

Reported-by [email protected]
Fixes 39193685d585 ("maple_tree: try harder to keep active node with mas_prev()")
Cc stable <[email protected]>
---
 include/linux/maple_tree.h |   2 +
 lib/maple_tree.c           | 221 +++++++++++++++++++++++++++----------
 lib/test_maple_tree.c      |  87 ++++++++++++---
 3 files changed, 237 insertions(+), 73 deletions(-)
include/linux/maple_tree.h +2 -0
index f66f5f78f8cf..d01e850b570f 100644
@@ -428,6 +428,8 @@ struct ma_wr_state {
 #define MAS_ROOT	((struct maple_enode *)5UL)
 #define MAS_NONE	((struct maple_enode *)9UL)
 #define MAS_PAUSE	((struct maple_enode *)17UL)
+#define MAS_OVERFLOW	((struct maple_enode *)33UL)
+#define MAS_UNDERFLOW	((struct maple_enode *)65UL)
 #define MA_ERROR(err) \
 		((struct maple_enode *)(((unsigned long)err << 2) | 2UL))
 
lib/maple_tree.c +163 -58

458 lines not on this page · raw message

lib/test_maple_tree.c +72 -15

193 lines not on this page · raw message

Signature · 1 line
2.39.2
#3 lore raw

Re: [PATCH 2/2] maple_tree: Add MAS_UNDERFLOW and MAS_OVERFLOW states

Quoted 3 lines · Liam R. Howlett

Since MAS_NONE is used for handling of the maple tree when it's a single entry at 0 (just a pointer), changing the handling of MAS_NONE in mas_find() would make the code more complicated and error prone.

Single entry at index 0 is MAS_ROOT, not MAS_NONE.

#4 lore raw

Re: [PATCH 2/2] maple_tree: Add MAS_UNDERFLOW and MAS_OVERFLOW states

Quoted 6 lines · Matthew Wilcox
Quoted 3 lines · Liam R. Howlett

Since MAS_NONE is used for handling of the maple tree when it's a single entry at 0 (just a pointer), changing the handling of MAS_NONE in mas_find() would make the code more complicated and error prone.

Single entry at index 0 is MAS_ROOT, not MAS_NONE.

Ah, sorry. I didn't explain this well. We end up in MAS_NONE when we search from MAS_ROOT upwards.. that is, there's a value only at 0 and we request 1 - ULONG_MAX, or we've called mas_find() with an index > 0. So there is no node in the tree for this entry.

The complication arises when mas_prev(), mas_next() or mas_walk()/mas_find() has already set MAS_NONE, then we can't tell the difference and so we don't really know what the Right Thing to do would be.

maintainer
#5 lore raw
In reply to Liam R. Howlett
Quoted 7 lines · On Thu, 21 Sep 2023 14:12:34 -0400 "Liam R. Howlett" <[email protected]>…

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 [email protected], although [email protected] works just fine.

#6 lore raw
Quoted 7 lines · Andrew Morton
Quoted 5 lines · On Thu, 21 Sep 2023 14:12:34 -0400 "Liam R. Howlett" <[email protected]>…

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.

Quoted 5 lines
Quoted 2 lines

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.

Quoted 2 lines

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

Oh yes, sorry.

Quoted 2 lines

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.

Quoted 2 lines

It's [email protected], although [email protected] works just fine.

#7 lore raw
Quoted 11 lines · Liam R. Howlett
Quoted 10 lines · Andrew Morton
Quoted 7 lines · On Thu, 21 Sep 2023 14:12:34 -0400 "Liam R. Howlett" <[email protected]>…

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.

Quoted 8 lines
Quoted 2 lines

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.

maintainer
#8 lore raw
Quoted 11 lines · On Thu, 21 Sep 2023 20:23:11 +0100 Matthew Wilcox <[email protected]> wrote:
Quoted 8 lines
Quoted 2 lines

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.

#9 lore raw
Quoted 14 lines · Andrew Morton
Quoted 11 lines · On Thu, 21 Sep 2023 20:23:11 +0100 Matthew Wilcox <[email protected]> wrote:
Quoted 8 lines
Quoted 2 lines

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_.

Quoted 7 lines

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

#10 lore raw
Quoted 18 lines · Liam R. Howlett
Quoted 16 lines · Andrew Morton
Quoted 11 lines · On Thu, 21 Sep 2023 20:23:11 +0100 Matthew Wilcox <[email protected]> wrote:
Quoted 8 lines
Quoted 2 lines

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 ;)

Quoted 8 lines
Quoted 5 lines

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)

Signature · 1 line
Pedro
#11 lore raw
Quoted 31 lines · Pedro Falcato
Quoted 18 lines · Liam R. Howlett
Quoted 16 lines · Andrew Morton
Quoted 11 lines · On Thu, 21 Sep 2023 20:23:11 +0100 Matthew Wilcox <[email protected]> wrote:
Quoted 8 lines
Quoted 2 lines

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 ;)

Quoted 8 lines
Quoted 5 lines

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:

Quoted 7 lines

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