linux-kernel - [RFC PATCH v6.6] maple_tree: Fix mas

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Message-ID: <20250428184058.1416274-1-Liam.Howlett@oracle.com>
Date: Mon, 28 Apr 2025 14:40:58 -0400
From: "Liam R. Howlett" <Liam.Howlett@...cle.com>
To: "Liam R . Howlett" <Liam.Howlett@...cle.com>
Cc: sidhartha.kumar@...cle.com, maple-tree@...ts.infradead.org,
        linux-mm@...ck.org, linux-kernel@...r.kernel.org,
        Zhaoyang Huang <zhaoyang.huang@...soc.com>,
        Hailong Liu <hailong.liu@...o.com>,
        Lorenzo Stoakes <lorenzo.stoakes@...cle.com>,
        Suren Baghdasaryan <surenb@...gle.com>,
        "zhangpeng . 00 @ bytedance . com" <zhangpeng.00@...edance.com>,
        Steve Kang <Steve.Kang@...soc.com>,
        Matthew Wilcox <willy@...radead.org>
Subject: [RFC PATCH v6.6] maple_tree: Fix mas_prealloc() reset

A previously used maple state may not be in the correct state for the
preallocation to correctly calculate the number of nodes necessary for the
configured store operation.

The user visible effect of which is warning that there are no nodes
allocated followed by a crash when there is a null pointer dereference
shortly after.

The NULL pointer dereference has been reported to happen when a vma
iterator is used to preallocate after walking to a leaf node but then
requesting to preallocate for a store across node boundaries (in v6.6.
of the kernel).  The altered range means that there may not been enough
nodes as the maple state has been incorrectly configured.  A critical
step is that the vma iterator then detects the misconfigured maple state
and resets, thus ensuring the tree is not corrupted - but ultimately
causes a failure when there are no nodes left.

Detect a misconfigured maple state in the mas_preallocate() code by
examining the current location and planned write to ensure a reset is
done if required.  The performance impacts are minimal and within the
noise in initial testing.

Reported-by: Zhaoyang Huang <zhaoyang.huang@...soc.com>
Reported-by: Hailong Liu <hailong.liu@...o.com>
Fixes: fec29364348fe ("maple_tree: reduce resets during store setup")
Link: https://lore.kernel.org/all/1652f7eb-a51b-4fee-8058-c73af63bacd1@oppo.com/
Cc: Lorenzo Stoakes <lorenzo.stoakes@...cle.com>
Cc: Suren Baghdasaryan <surenb@...gle.com>
Cc: Hailong Liu <hailong.liu@...o.com>
Cc: zhangpeng.00@...edance.com <zhangpeng.00@...edance.com>
Cc: Steve Kang <Steve.Kang@...soc.com>
Cc: Matthew Wilcox <willy@...radead.org>
Signed-off-by: Liam R. Howlett <Liam.Howlett@...cle.com>
---
 lib/maple_tree.c | 35 +++++++++++++++++++++++++++++++----
 1 file changed, 31 insertions(+), 4 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 4eda949063602..17af9073494f5 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -5350,6 +5350,8 @@ static inline void mte_destroy_walk(struct maple_enode *enode,
 
 static void mas_wr_store_setup(struct ma_wr_state *wr_mas)
 {
+	unsigned char node_size;
+
 	if (!mas_is_active(wr_mas->mas)) {
 		if (mas_is_start(wr_mas->mas))
 			return;
@@ -5372,17 +5374,42 @@ static void mas_wr_store_setup(struct ma_wr_state *wr_mas)
 	 * writes within this node.  This is to stop partial walks in
 	 * mas_prealloc() from being reset.
 	 */
+
+	/* Leaf root node is safe */
+	if (mte_is_root(wr_mas->mas->node))
+		return;
+
+	/* Cannot span beyond this node */
 	if (wr_mas->mas->last > wr_mas->mas->max)
 		goto reset;
 
-	if (wr_mas->entry)
+	/* Cannot span before this node */
+	if (wr_mas->mas->index < wr_mas->mas->min)
+		goto reset;
+
+	wr_mas->type = mte_node_type(wr_mas->mas->node);
+	/* unfinished walk is okay */
+	if (!ma_is_leaf(wr_mas->type))
 		return;
 
-	if (mte_is_leaf(wr_mas->mas->node) &&
-	    wr_mas->mas->last == wr_mas->mas->max)
+	/* Leaf node that ends in 0 means a spanning store */
+	if (!wr_mas->entry &&
+	    (wr_mas->mas->last == wr_mas->mas->max))
 		goto reset;
 
-	return;
+	mas_wr_node_walk(wr_mas);
+	if (wr_mas->r_min == wr_mas->mas->index &&
+	    wr_mas->r_max == wr_mas->mas->last)
+		return; /* exact fit, no allocations */
+
+	wr_mas->slots = ma_slots(wr_mas->node, wr_mas->type);
+	mas_wr_end_piv(wr_mas);
+	node_size = mas_wr_new_end(wr_mas);
+	if (node_size >= mt_slots[wr_mas->type])
+		goto reset; /* Not going to fit */
+
+	if (node_size - 1 > mt_min_slots[wr_mas->type])
+		return; /* sufficient and will fit */
 
 reset:
 	mas_reset(wr_mas->mas);
-- 
2.47.2