linux-kernel.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
* [PATCH Fix 0/2] Fix out-of-bounds maple tree isue
@ 2022-07-22 16:06 Liam Howlett
  2022-07-22 16:06 ` [PATCH Fix 2/2] kernel/fork: Detect mas_store() failure in dup_mmap() Liam Howlett
  2022-07-22 16:06 ` [PATCH Fix 1/2] maple_tree: Fix mas_expected_entries() off by one Liam Howlett
  0 siblings, 2 replies; 3+ messages in thread
From: Liam Howlett @ 2022-07-22 16:06 UTC (permalink / raw)
  To: maple-tree, linux-mm, linux-kernel, Andrew Morton, Yu Zhao; +Cc: Hugh Dickins

The out of bounds maple tree issue was actually a maple tree error being
treated as a node.  This was caused by the requested allocation of more
nodes than was available while forking, but there was no memory
available.  This series adds one node to the calculated
mas_expected_entries() to ensure there is enough nodes, adds a flag to
WARN_ON() if a request for nodes is hit with zero nodes available during
a preallocated operation, and also adds the necessary check in the fork
operation to fail.

Liam R. Howlett (2):
  maple_tree: Fix mas_expected_entries() off by one
  kernel/fork: Detect mas_store() failure in dup_mmap()

 include/linux/maple_tree.h |  1 +
 kernel/fork.c              |  5 +++++
 lib/maple_tree.c           | 26 +++++++++++++++++++++-----
 3 files changed, 27 insertions(+), 5 deletions(-)

-- 
2.35.1

^ permalink raw reply	[flat|nested] 3+ messages in thread

* [PATCH Fix 2/2] kernel/fork: Detect mas_store() failure in dup_mmap()
  2022-07-22 16:06 [PATCH Fix 0/2] Fix out-of-bounds maple tree isue Liam Howlett
@ 2022-07-22 16:06 ` Liam Howlett
  2022-07-22 16:06 ` [PATCH Fix 1/2] maple_tree: Fix mas_expected_entries() off by one Liam Howlett
  1 sibling, 0 replies; 3+ messages in thread
From: Liam Howlett @ 2022-07-22 16:06 UTC (permalink / raw)
  To: maple-tree, linux-mm, linux-kernel, Andrew Morton, Yu Zhao; +Cc: Hugh Dickins

mas_store() should not fail, but protect against potential failures by
checking the maple state for mas_is_err().

Fixes: 57579b57de57 (kernel/fork: use maple tree for dup_mmap() during forking)
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
---
 kernel/fork.c | 5 +++++
 1 file changed, 5 insertions(+)

diff --git a/kernel/fork.c b/kernel/fork.c
index 2d7ce88da540..dfa2d5d22ed1 100644
--- a/kernel/fork.c
+++ b/kernel/fork.c
@@ -685,6 +685,8 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
 		mas.index = tmp->vm_start;
 		mas.last = tmp->vm_end - 1;
 		mas_store(&mas, tmp);
+		if (mas_is_err(&mas))
+			goto fail_nomem_mas_store;
 
 		mm->map_count++;
 		if (!(tmp->vm_flags & VM_WIPEONFORK))
@@ -708,6 +710,9 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
 fail_uprobe_end:
 	uprobe_end_dup_mmap();
 	return retval;
+
+fail_nomem_mas_store:
+	unlink_anon_vmas(tmp);
 fail_nomem_anon_vma_fork:
 	mpol_put(vma_policy(tmp));
 fail_nomem_policy:
-- 
2.35.1

^ permalink raw reply related	[flat|nested] 3+ messages in thread

* [PATCH Fix 1/2] maple_tree: Fix mas_expected_entries() off by one
  2022-07-22 16:06 [PATCH Fix 0/2] Fix out-of-bounds maple tree isue Liam Howlett
  2022-07-22 16:06 ` [PATCH Fix 2/2] kernel/fork: Detect mas_store() failure in dup_mmap() Liam Howlett
@ 2022-07-22 16:06 ` Liam Howlett
  1 sibling, 0 replies; 3+ messages in thread
From: Liam Howlett @ 2022-07-22 16:06 UTC (permalink / raw)
  To: maple-tree, linux-mm, linux-kernel, Andrew Morton, Yu Zhao; +Cc: Hugh Dickins

When inserting nodes, a final call to split the nodes will require a new
parent.  Add this as the working area for mas_expected_entries().

Add a maple state flag which will WARN_ON() if there is insufficient
nodes allocated.

Export mas_is_err() to be used in checking mas_store() returns
externally.

Fixes: 06b152b7980a (Maple Tree: add new data structure)
Reported-by: Yu Zhao <yuzhao@google.com>
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
---
 include/linux/maple_tree.h |  1 +
 lib/maple_tree.c           | 26 +++++++++++++++++++++-----
 2 files changed, 22 insertions(+), 5 deletions(-)

diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h
index bdb891b0d2b5..a30e03b06bed 100644
--- a/include/linux/maple_tree.h
+++ b/include/linux/maple_tree.h
@@ -457,6 +457,7 @@ void mas_store_prealloc(struct ma_state *mas, void *entry);
 void *mas_find(struct ma_state *mas, unsigned long max);
 void *mas_find_rev(struct ma_state *mas, unsigned long min);
 int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp);
+bool mas_is_err(struct ma_state *mas);
 
 bool mas_nomem(struct ma_state *mas, gfp_t gfp);
 void mas_pause(struct ma_state *mas);
diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index d00ad50b258e..a3ead5fb5307 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -64,9 +64,15 @@
 
 #define MA_ROOT_PARENT 1
 
-/* Maple state flags */
+/*
+ * Maple state flags
+ * * MA_STATE_BULK		- Bulk insert mode
+ * * MA_STATE_REBALANCE		- Indicate a rebalance during bulk insert
+ * * MA_STATE_PREALLOC		- Preallocated nodes, WARN_ON allocation
+ */
 #define MA_STATE_BULK		1
 #define MA_STATE_REBALANCE	2
+#define MA_STATE_PREALLOC	4
 
 #define ma_parent_ptr(x) ((struct maple_pnode *)(x))
 #define ma_mnode_ptr(x) ((struct maple_node *)(x))
@@ -243,7 +249,7 @@ static inline bool mas_is_start(struct ma_state *mas)
 	return mas->node == MAS_START;
 }
 
-static inline bool mas_is_err(struct ma_state *mas)
+bool mas_is_err(struct ma_state *mas)
 {
 	return xa_is_err(mas->node);
 }
@@ -1215,6 +1221,12 @@ static inline void mas_alloc_nodes(struct ma_state *mas, gfp_t gfp)
 		return;
 
 	mas_set_alloc_req(mas, 0);
+	if (mas->mas_flags & MA_STATE_PREALLOC) {
+		if (allocated)
+			return;
+		WARN_ON(!allocated);
+	}
+
 	if (!allocated || mas->alloc->node_count == MAPLE_ALLOC_SLOTS - 1) {
 		node = (struct maple_alloc *)mt_alloc_one(gfp);
 		if (!node)
@@ -5706,6 +5718,7 @@ int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp)
 	int ret;
 
 	mas_node_count_gfp(mas, 1 + mas_mt_height(mas) * 3, gfp);
+	mas->mas_flags |= MA_STATE_PREALLOC;
 	if (likely(!mas_is_err(mas)))
 		return 0;
 
@@ -5748,7 +5761,7 @@ void mas_destroy(struct ma_state *mas)
 
 		mas->mas_flags &= ~MA_STATE_REBALANCE;
 	}
-	mas->mas_flags &= ~MA_STATE_BULK;
+	mas->mas_flags &= ~(MA_STATE_BULK|MA_STATE_PREALLOC);
 
 	while (mas->alloc && !((unsigned long)mas->alloc & 0x1)) {
 		node = mas->alloc;
@@ -5799,7 +5812,6 @@ int mas_expected_entries(struct ma_state *mas, unsigned long nr_entries)
 	 * insertion of entries.
 	 */
 	nr_nodes = max(nr_entries, nr_entries * 2 + 1);
-
 	if (!mt_is_alloc(mas->tree))
 		nonleaf_cap = MAPLE_RANGE64_SLOTS - 2;
 
@@ -5807,7 +5819,11 @@ int mas_expected_entries(struct ma_state *mas, unsigned long nr_entries)
 	nr_nodes = DIV_ROUND_UP(nr_nodes, MAPLE_RANGE64_SLOTS - 1);
 	/* Internal nodes */
 	nr_nodes += DIV_ROUND_UP(nr_nodes, nonleaf_cap);
-	mas_node_count(mas, nr_nodes);
+	/* Add one for working room */
+	mas_node_count(mas, nr_nodes + 1);
+
+	/* Detect if allocations run out */
+	mas->mas_flags |= MA_STATE_PREALLOC;
 
 	if (!mas_is_err(mas))
 		return 0;
-- 
2.35.1

^ permalink raw reply related	[flat|nested] 3+ messages in thread

end of thread, other threads:[~2022-07-22 16:08 UTC | newest]

Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-07-22 16:06 [PATCH Fix 0/2] Fix out-of-bounds maple tree isue Liam Howlett
2022-07-22 16:06 ` [PATCH Fix 2/2] kernel/fork: Detect mas_store() failure in dup_mmap() Liam Howlett
2022-07-22 16:06 ` [PATCH Fix 1/2] maple_tree: Fix mas_expected_entries() off by one Liam 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).