+ maple-tree-add-new-data-structure-fix-2.patch added to mm-unstable branch

+ maple-tree-add-new-data-structure-fix-2.patch added to mm-unstable branch

[Andrew Morton]

The patch titled
     Subject: maple_tree: drop typedef from header
has been added to the -mm mm-unstable branch.  Its filename is
     maple-tree-add-new-data-structure-fix-2.patch

This patch will shortly appear at
     https://git.kernel.org/pub/scm/linux/kernel/git/akpm/25-new.git/tree/patches/maple-tree-add-new-data-structure-fix-2.patch

This patch will later appear in the mm-unstable branch at
    git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm

Before you just go and hit "reply", please:
   a) Consider who else should be cc'ed
   b) Prefer to cc a suitable mailing list as well
   c) Ideally: find the original patch on the mailing list and do a
      reply-to-all to that, adding suitable additional cc's

*** Remember to use Documentation/process/submit-checklist.rst when testing your code ***

The -mm tree is included into linux-next via the mm-everything
branch at git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
and is updated there every 2-3 working days

------------------------------------------------------
From: Liam Howlett <liam.howlett@oracle.com>
Subject: maple_tree: drop typedef from header
Date: Tue, 19 Jul 2022 17:10:15 +0000

These typedefs are not used and cause issues with rust in the kernel.

Link: https://lkml.kernel.org/r/20220719171006.3299123-1-Liam.Howlett@oracle.com
Fixes: fb7297e8a66b ("Maple Tree: add new data structure")
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
Reported-by: Li Hongyu <lihongyu1999@bupt.edu.cn>
Suggested-by: Matthew Wilcox <willy@infradead.org>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
---

 include/linux/maple_tree.h |    2 --
 1 file changed, 2 deletions(-)

--- a/include/linux/maple_tree.h~maple-tree-add-new-data-structure-fix-2
+++ a/include/linux/maple_tree.h
@@ -72,8 +72,6 @@
  *   0x010 : 32 bit values, type in 0-2, slot in 3-6
  *   0x110 : 64 bit values, type in 0-2, slot in 3-6
  */
-typedef struct maple_enode *maple_enode; /* encoded node */
-typedef struct maple_pnode *maple_pnode; /* parent node */
 
 /*
  * This metadata is used to optimize the gap updating code and in reverse
_

Patches currently in -mm which might be from liam.howlett@oracle.com are

android-binder-fix-lockdep-check-on-clearing-vma.patch
maple-tree-add-new-data-structure-fix.patch
maple-tree-add-new-data-structure-fix-2.patch
mm-start-tracking-vmas-with-maple-tree-fix.patch
mm-mmap-use-advanced-maple-tree-api-for-mmap_region-fix.patch
mm-mlock-drop-dead-code-in-count_mm_mlocked_page_nr.patch

+ maple-tree-add-new-data-structure-fix-2.patch added to mm-unstable branch

[Andrew Morton]

The patch titled
     Subject: maple_tree: add a mas_destroy() call to mas_expected_entries() failure path
has been added to the -mm mm-unstable branch.  Its filename is
     maple-tree-add-new-data-structure-fix-2.patch

This patch will shortly appear at
     https://git.kernel.org/pub/scm/linux/kernel/git/akpm/25-new.git/tree/patches/maple-tree-add-new-data-structure-fix-2.patch

This patch will later appear in the mm-unstable branch at
    git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm

Before you just go and hit "reply", please:
   a) Consider who else should be cc'ed
   b) Prefer to cc a suitable mailing list as well
   c) Ideally: find the original patch on the mailing list and do a
      reply-to-all to that, adding suitable additional cc's

*** Remember to use Documentation/process/submit-checklist.rst when testing your code ***

The -mm tree is included into linux-next via the mm-everything
branch at git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
and is updated there every 2-3 working days

------------------------------------------------------
From: Liam Howlett <liam.howlett@oracle.com>
Subject: maple_tree: add a mas_destroy() call to mas_expected_entries() failure path
Date: Thu, 21 Jul 2022 00:58:43 +0000

In an exceedingly rare case, there is a possibility that allocating all of
the nodes may fail in a way that the maple state is left with some
allocations completed.  This would happen if the single allocation
succeeds but bulk allocation fails, or if multiple bulk allocations are
required and somewhere along the way one fails.  The partial return is
already cleaned up, but the successful allocations will remain in the
maple state.  When this happens, mas_expected_entries() may leak memory. 
Fix this by moving mas_destroy() above mas_expected_entries() and add a
call to mas_destroy() to clear out all allocated memory.

Link: https://lkml.kernel.org/r/20220721005828.379405-1-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
---

 lib/maple_tree.c |   89 ++++++++++++++++++++++-----------------------
 1 file changed, 45 insertions(+), 44 deletions(-)

--- a/lib/maple_tree.c~maple-tree-add-new-data-structure-fix-2
+++ a/lib/maple_tree.c
@@ -5706,6 +5706,50 @@ int mas_preallocate(struct ma_state *mas
 }
 
 /*
+ * mas_destroy() - destroy a maple state.
+ * @mas: The maple state
+ *
+ * Upon completion, check the left-most node and rebalance against the node to
+ * the right if necessary.  Frees any allocated nodes associated with this maple
+ * state.
+ */
+void mas_destroy(struct ma_state *mas)
+{
+	struct maple_alloc *node;
+
+	/*
+	 * When using mas_for_each() to insert an expected number of elements,
+	 * it is possible that the number inserted is less than the expected
+	 * number.  To fix an invalid final node, a check is performed here to
+	 * rebalance the previous node with the final node.
+	 */
+	if (mas->mas_flags & MA_STATE_REBALANCE) {
+		unsigned char end;
+
+		if (mas_is_start(mas))
+			mas_start(mas);
+
+		mtree_range_walk(mas);
+		end = mas_data_end(mas) + 1;
+		if (end < mt_min_slot_count(mas->node) - 1)
+			mas_destroy_rebalance(mas, end);
+
+		mas->mas_flags &= ~MA_STATE_REBALANCE;
+	}
+	mas->mas_flags &= ~MA_STATE_BULK;
+
+	while (mas->alloc && !((unsigned long)mas->alloc & 0x1)) {
+		node = mas->alloc;
+		mas->alloc = node->slot[0];
+		if (node->node_count > 0)
+			mt_free_bulk(node->node_count,
+				     (void __rcu **)&node->slot[1]);
+		kmem_cache_free(maple_node_cache, node);
+	}
+	mas->alloc = NULL;
+}
+
+/*
  * mas_expected_entries() - Set the expected number of entries that will be inserted.
  * @mas: The maple state
  * @nr_entries: The number of expected entries.
@@ -5758,54 +5802,11 @@ int mas_expected_entries(struct ma_state
 
 	ret = xa_err(mas->node);
 	mas->node = enode;
+	mas_destroy(mas);
 	return ret;
 
 }
 
-/*
- * mas_destroy() - destroy a maple state.
- * @mas: The maple state
- *
- * Upon completion, check the left-most node and rebalance against the node to
- * the right if necessary.  Frees any allocated nodes associated with this maple
- * state.
- */
-void mas_destroy(struct ma_state *mas)
-{
-	struct maple_alloc *node;
-
-	/*
-	 * When using mas_for_each() to insert an expected number of elements,
-	 * it is possible that the number inserted is less than the expected
-	 * number.  To fix an invalid final node, a check is performed here to
-	 * rebalance the previous node with the final node.
-	 */
-	if (mas->mas_flags & MA_STATE_REBALANCE) {
-		unsigned char end;
-
-		if (mas_is_start(mas))
-			mas_start(mas);
-
-		mtree_range_walk(mas);
-		end = mas_data_end(mas) + 1;
-		if (end < mt_min_slot_count(mas->node) - 1)
-			mas_destroy_rebalance(mas, end);
-
-		mas->mas_flags &= ~MA_STATE_REBALANCE;
-	}
-	mas->mas_flags &= ~MA_STATE_BULK;
-
-	while (mas->alloc && !((unsigned long)mas->alloc & 0x1)) {
-		node = mas->alloc;
-		mas->alloc = node->slot[0];
-		if (node->node_count > 0)
-			mt_free_bulk(node->node_count,
-				     (void __rcu **)&node->slot[1]);
-		kmem_cache_free(maple_node_cache, node);
-	}
-	mas->alloc = NULL;
-}
-
 /**
  * mas_next() - Get the next entry.
  * @mas: The maple state
_

Patches currently in -mm which might be from liam.howlett@oracle.com are

android-binder-fix-lockdep-check-on-clearing-vma.patch
maple-tree-add-new-data-structure-fix-2.patch
maple-tree-add-new-data-structure-fix.patch
kernel-fork-use-maple-tree-for-dup_mmap-during-forking-fix.patch
maple_tree-do-not-inline-write-slow-path.patch

+ maple-tree-add-new-data-structure-fix-2.patch added to mm-unstable branch

[Andrew Morton]

The patch titled
     Subject: maple_tree: fix mas_spanning_rebalance() corner case
has been added to the -mm mm-unstable branch.  Its filename is
     maple-tree-add-new-data-structure-fix-2.patch

This patch will shortly appear at
     https://git.kernel.org/pub/scm/linux/kernel/git/akpm/25-new.git/tree/patches/maple-tree-add-new-data-structure-fix-2.patch

This patch will later appear in the mm-unstable branch at
    git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm

Before you just go and hit "reply", please:
   a) Consider who else should be cc'ed
   b) Prefer to cc a suitable mailing list as well
   c) Ideally: find the original patch on the mailing list and do a
      reply-to-all to that, adding suitable additional cc's

*** Remember to use Documentation/process/submit-checklist.rst when testing your code ***

The -mm tree is included into linux-next via the mm-everything
branch at git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
and is updated there every 2-3 working days

------------------------------------------------------
From: Liam Howlett <liam.howlett@oracle.com>
Subject: maple_tree: fix mas_spanning_rebalance() corner case
Date: Wed, 29 Jun 2022 15:23:50 +0000

When a node is insufficient during a spanning rebalance loop and
mast_spanning_rebalance() is called to combine neighbouring nodes, the
loop should not terminate regardless of if neighbours exist or not.  This
will allow the data to be stored in the correct node.

Link: https://lkml.kernel.org/r/20220629152340.3451959-2-Liam.Howlett@oracle.com
Fixes: 37a4d714b7d9 (maple_tree: fix underflow in mas_spanning_rebalance())
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
Reported-by: Yu Zhao <yuzhao@google.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
---

 lib/maple_tree.c |    5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)

--- a/lib/maple_tree.c~maple-tree-add-new-data-structure-fix-2
+++ a/lib/maple_tree.c
@@ -3029,8 +3029,7 @@ static int mas_spanning_rebalance(struct
 		if (mas_is_root_limits(mast->orig_l))
 			break;
 
-		if (!mast_spanning_rebalance(mast))
-			break;
+		mast_spanning_rebalance(mast);
 
 		/* rebalancing from other nodes may require another loop. */
 		if (!count)
@@ -6521,6 +6520,7 @@ static inline void *mas_first_entry(stru
 	max = mas->max;
 	mas->offset = 0;
 	while (likely(!ma_is_leaf(mt))) {
+		MT_BUG_ON(mas->tree, mte_dead_node(mas->node));
 		slots = ma_slots(mn, mt);
 		pivots = ma_pivots(mn, mt);
 		max = pivots[0];
@@ -6531,6 +6531,7 @@ static inline void *mas_first_entry(stru
 		mn = mas_mn(mas);
 		mt = mte_node_type(mas->node);
 	}
+	MT_BUG_ON(mas->tree, mte_dead_node(mas->node));
 
 	mas->max = max;
 	slots = ma_slots(mn, mt);
_

Patches currently in -mm which might be from liam.howlett@oracle.com are

android-binder-fix-lockdep-check-on-clearing-vma.patch
maple-tree-add-new-data-structure-fix.patch
maple-tree-add-new-data-structure-fix-2.patch
lib-test_maple_tree-add-testing-for-maple-tree-fix.patch
mm-mlock-drop-dead-code-in-count_mm_mlocked_page_nr.patch

+ maple-tree-add-new-data-structure-fix-2.patch added to mm-unstable branch

[Andrew Morton]

The patch titled
     Subject: maple_tree: fix mas_next() when already on the last node entry
has been added to the -mm mm-unstable branch.  Its filename is
     maple-tree-add-new-data-structure-fix-2.patch

This patch will shortly appear at
     https://git.kernel.org/pub/scm/linux/kernel/git/akpm/25-new.git/tree/patches/maple-tree-add-new-data-structure-fix-2.patch

This patch will later appear in the mm-unstable branch at
    git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm

Before you just go and hit "reply", please:
   a) Consider who else should be cc'ed
   b) Prefer to cc a suitable mailing list as well
   c) Ideally: find the original patch on the mailing list and do a
      reply-to-all to that, adding suitable additional cc's

*** Remember to use Documentation/process/submit-checklist.rst when testing your code ***

The -mm tree is included into linux-next via the mm-everything
branch at git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
and is updated there every 2-3 working days

------------------------------------------------------
From: Liam Howlett <liam.howlett@oracle.com>
Subject: maple_tree: fix mas_next() when already on the last node entry
Date: Tue, 17 May 2022 14:59:22 +0000

It is possible to return the metadata as the next entry if the last node
entry is already in the maple state and the limit is not reached.  Check
for this condition in mas_next_nentry() where the node end is returned.

Link: https://lkml.kernel.org/r/20220517145913.3480729-1-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
Reported-by: Sven Schnelle <svens@linux.ibm.com>
Reported-by: Guenter Roeck <linux@roeck-us.net>
Reported-by: Heiko Carstens <hca@linux.ibm.com>
Tested-by: Sven Schnelle <svens@linux.ibm.com>
Cc: Stephen Rothwell <sfr@canb.auug.org.au>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
---

 lib/maple_tree.c |    3 +++
 1 file changed, 3 insertions(+)

--- a/lib/maple_tree.c~maple-tree-add-new-data-structure-fix-2
+++ a/lib/maple_tree.c
@@ -4547,6 +4547,9 @@ static inline void *mas_next_nentry(stru
 		return NULL;
 
 	count = ma_data_end(node, type, pivots, mas->max);
+	if (mas->offset > count)
+		return NULL;
+
 	while (mas->offset < count) {
 		pivot = pivots[mas->offset];
 		entry = mas_slot(mas, slots, mas->offset);
_

Patches currently in -mm which might be from liam.howlett@oracle.com are

maple-tree-add-new-data-structure-fix.patch
maple-tree-add-new-data-structure-fix-2.patch
lib-test_maple_tree-add-testing-for-maple-tree-fix.patch
mm-start-tracking-vmas-with-maple-tree-fix-2.patch
mm-remove-the-vma-linked-list-fix.patch

+ maple-tree-add-new-data-structure-fix-2.patch added to mm-unstable branch

[Andrew Morton]

The patch titled
     Subject: maple_tree: fix mas_next() when already on the last node entry
has been added to the -mm mm-unstable branch.  Its filename is
     maple-tree-add-new-data-structure-fix-2.patch

This patch will shortly appear at
     https://git.kernel.org/pub/scm/linux/kernel/git/akpm/25-new.git/tree/patches/maple-tree-add-new-data-structure-fix-2.patch

This patch will later appear in the mm-unstable branch at
    git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm

Before you just go and hit "reply", please:
   a) Consider who else should be cc'ed
   b) Prefer to cc a suitable mailing list as well
   c) Ideally: find the original patch on the mailing list and do a
      reply-to-all to that, adding suitable additional cc's

*** Remember to use Documentation/process/submit-checklist.rst when testing your code ***

The -mm tree is included into linux-next via the mm-everything
branch at git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
and is updated there every 2-3 working days

------------------------------------------------------
From: Liam Howlett <liam.howlett@oracle.com>
Subject: maple_tree: fix mas_next() when already on the last node entry
Date: Tue, 17 May 2022 14:59:22 +0000

It is possible to return the metadata as the next entry if the last node
entry is already in the maple state and the limit is not reached.  Check
for this condition in mas_next_nentry() where the node end is returned.

Link: https://lkml.kernel.org/r/20220517145913.3480729-1-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
Reported-by: Sven Schnelle <svens@linux.ibm.com>
Reported-by: Guenter Roeck <linux@roeck-us.net>
Reported-by: Heiko Carstens <hca@linux.ibm.com>
Tested-by: Sven Schnelle <svens@linux.ibm.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
---

 lib/maple_tree.c |    3 +++
 1 file changed, 3 insertions(+)

--- a/lib/maple_tree.c~maple-tree-add-new-data-structure-fix-2
+++ a/lib/maple_tree.c
@@ -4547,6 +4547,9 @@ static inline void *mas_next_nentry(stru
 		return NULL;
 
 	count = ma_data_end(node, type, pivots, mas->max);
+	if (mas->offset > count)
+		return NULL;
+
 	while (mas->offset < count) {
 		pivot = pivots[mas->offset];
 		entry = mas_slot(mas, slots, mas->offset);
_

Patches currently in -mm which might be from liam.howlett@oracle.com are

maple-tree-add-new-data-structure-fix.patch
maple-tree-add-new-data-structure-fix-2.patch
lib-test_maple_tree-add-testing-for-maple-tree-fix.patch
mm-start-tracking-vmas-with-maple-tree-fix-2.patch
mm-remove-the-vma-linked-list-fix.patch