Skip to contentSkip to conversation

maple_tree-add-mas_underflow-and-mas_overflow-states.patch removed from -mm tree

merged mm-hotfixes-stable Andrew Morton 1 participant 1 message Sep 30, 2023 Stable branch

lore
Share & tools
lore

Andrew Morton

author tree notice Applied
#0 lore raw

The quilt patch titled
Subject: maple_tree: add MAS_UNDERFLOW and MAS_OVERFLOW states
has been removed from the -mm tree. Its filename was
maple_tree-add-mas_underflow-and-mas_overflow-states.patch

This patch was dropped because it was merged into the mm-hotfixes-stable branch of git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm

------------------------------------------------------
From: "Liam R. Howlett" <[email protected]>
Subject: maple_tree: add MAS_UNDERFLOW and MAS_OVERFLOW states
Date: Thu, 21 Sep 2023 14:12:36 -0400

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 may already be set when searching for a value that isn't contained within a node, 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.

---

 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 renamed from include/linux/maple_tree.h~maple_tree-add-mas_underflow-and-mas_overflow-states +2 -0
@@ -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 renamed from lib/maple_tree.c~maple_tree-add-mas_underflow-and-mas_overflow-states +163 -58

458 lines not on this page · raw message

lib/test_maple_tree.c renamed from lib/test_maple_tree.c~maple_tree-add-mas_underflow-and-mas_overflow-states +72 -15

193 lines not on this page · raw message

_

Patches currently in -mm which might be from [email protected] are

mm-mempolicy-fix-set_mempolicy_home_node-previous-vma-pointer.patch mmap-fix-vma_iterator-in-error-path-of-vma_merge.patch mmap-fix-error-paths-with-dup_anon_vma.patch mmap-add-clarifying-comment-to-vma_merge-code.patch radix-tree-test-suite-fix-allocation-calculation-in-kmem_cache_alloc_bulk.patch