| 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
| ||
|
Message-ID: <20260130205935.2559335-24-Liam.Howlett@oracle.com>
Date: Fri, 30 Jan 2026 15:59:28 -0500
From: "Liam R. Howlett" <Liam.Howlett@...cle.com>
To: Andrew Morton <akpm@...ux-foundation.org>
Cc: maple-tree@...ts.infradead.org, linux-mm@...ck.org,
linux-kernel@...r.kernel.org, Suren Baghdasaryan <surenb@...gle.com>,
Matthew Wilcox <willy@...radead.org>,
Sidhartha Kumar <sidhartha.kumar@...cle.com>,
Vlastimil Babka <vbabka@...e.cz>, Alice Ryhl <aliceryhl@...gle.com>,
Kuninori Morimoto <kuninori.morimoto.gx@...esas.com>,
Geert Uytterhoeven <geert@...ux-m68k.org>,
Arnd Bergmann <arnd@...db.de>, Christian Kujau <lists@...dbynature.de>,
SeongJae Park <sj@...nel.org>,
"Liam R. Howlett" <Liam.Howlett@...cle.com>
Subject: [PATCH v3 23/30] maple_tree: Add test for rebalance calculation off-by-one
During the big node removal, an incorrect rebalance step went too far up
the tree causing insufficient nodes. Test the faulty condition by
recreating the scenario in the userspace testing.
Signed-off-by: Liam R. Howlett <Liam.Howlett@...cle.com>
---
tools/testing/radix-tree/maple.c | 125 +++++++++++++++++++++++++++++++
1 file changed, 125 insertions(+)
diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c
index dfd7099f0d8ef..5ea45d67556a8 100644
--- a/tools/testing/radix-tree/maple.c
+++ b/tools/testing/radix-tree/maple.c
@@ -35888,6 +35888,127 @@ static __init int build_full_tree(struct maple_tree *mt, unsigned int flags,
return ret;
}
+static noinline void __init check_erase_rebalance(struct maple_tree *mt)
+{
+ unsigned long val;
+ void *enode;
+ int ret;
+
+ MA_STATE(mas, mt, 0, 0);
+
+ /*
+ * During removal of big node, the rebalance started going too high,
+ * which resulted in too many nodes trying to be used.
+ *
+ * Create a rebalance which results in an exactly full parent (0-9) that
+ * does not need to be rebalanced. This required two full levels,
+ * followed by an insufficient level which will be rebalanced into two
+ * nodes, finally leaves that need to be rebalanced into one node.
+ *
+ * The bugs tree:
+ * root 4 Label R
+ * /\ /\
+ * 9 X F
+ * /\ /\ /
+ * 9 X E
+ * /\ /\ /\
+ * 4 8 C D
+ * /\ /\
+ * 6 9 A B
+ * ^ becomes 5 with the write.
+ *
+ * Below, the reconstruction leaves the root with 2 entries, the setup
+ * uses the letter labels above.
+ */
+
+ ret = build_full_tree(mt, MT_FLAGS_ALLOC_RANGE, 4);
+ MT_BUG_ON(mt, ret);
+
+ /* Cheap expansion to 5 levels */
+ mtree_store(mt, ULONG_MAX, xa_mk_value(0), GFP_KERNEL);
+ /* rcu is used to ensure node use */
+ mt_set_in_rcu(mt);
+ mas_lock(&mas);
+
+ /* Node A had 6 entries */
+ mas_walk(&mas);
+ MAS_BUG_ON(&mas, mas_data_end(&mas) < 6);
+ while (mas_data_end(&mas) > 6) {
+ mas_erase(&mas);
+ mas_next(&mas, ULONG_MAX);
+ }
+
+ /* Move to Node B */
+ enode = (void*) mas.node;
+ while (mas.node == enode)
+ mas_next(&mas, ULONG_MAX);
+
+ /* Node B had 9 entries */
+ MAS_BUG_ON(&mas, mas_data_end(&mas) < 9);
+ while (mas_data_end(&mas) > 9) {
+ mas_erase(&mas);
+ mas_next(&mas, ULONG_MAX);
+ }
+
+ /* Move to Node C */
+ mas_ascend(&mas);
+ val = mas.max;
+ /* Adjust entries to be 4 */
+ while (mas_data_end(&mas) > 4) {
+ mas_set(&mas, val);
+ mas_erase(&mas);
+ mas_prev(&mas, 0);
+ val = mas.index;
+ mas_ascend(&mas);
+ }
+
+ /* Move to Node D */
+ mas_ascend(&mas);
+ mas.offset = 1;
+ mas_descend(&mas);
+ val = mas.max;
+ /* Adjust entries to be 8 */
+ while (mas_data_end(&mas) < 8) {
+ mas_set(&mas, val--);
+ mas_store_gfp(&mas, &mas, GFP_KERNEL);
+ mas_ascend(&mas);
+ }
+
+ /* Move to Node E */
+ mas_ascend(&mas);
+ val = mas.max;
+ MAS_BUG_ON(&mas, mas_data_end(&mas) > 9);
+ /* Adjust Node E to 9 entries */
+ while (mas_data_end(&mas) < 9) {
+ mas_set(&mas, val--);
+ mas_store_gfp(&mas, &mas, GFP_KERNEL);
+ mas_ascend(&mas);
+ mas_ascend(&mas);
+ }
+
+ /* Move to Node F */
+ mas_ascend(&mas);
+ val = mas.max;
+ MAS_BUG_ON(&mas, mas_data_end(&mas) > 9);
+ /* Adjust Node F to 9 entries */
+ while (mas_data_end(&mas) < 9) {
+ mas_set(&mas, val--);
+ mas_store_gfp(&mas, &mas, GFP_KERNEL);
+ mas_ascend(&mas);
+ mas_ascend(&mas);
+ mas_ascend(&mas);
+ }
+
+ /* Test is set up, walk to first entry */
+ mas_set(&mas, 0);
+ mas_next(&mas, ULONG_MAX);
+ /* overwrite the entry to cause a rebalance, which was 1 too few */
+ mas_set_range(&mas, 0, mas.last);
+ mas_preallocate(&mas, NULL, GFP_KERNEL);
+ mas_store_prealloc(&mas, NULL);
+ mas_unlock(&mas);
+}
+
static noinline void __init check_mtree_dup(struct maple_tree *mt)
{
DEFINE_MTREE(new);
@@ -36249,6 +36370,10 @@ void farmer_tests(void)
check_mtree_dup(&tree);
mtree_destroy(&tree);
+ mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
+ check_erase_rebalance(&tree);
+ mtree_destroy(&tree);
+
/* RCU testing */
mt_init_flags(&tree, 0);
check_erase_testset(&tree);
--
2.47.3
Powered by blists - more mailing lists