From e15121ab56044a6a119aec75a6a994c47c2b243c Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Thu, 24 Sep 2020 08:53:33 -0400 Subject: [PATCH] maple_tree: Add validation for nulls in non-leaves Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 12 ++++++++++++ lib/test_maple_tree.c | 17 +++++++++++++++++ 2 files changed, 29 insertions(+) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 905bc28f7fb6..763108325ed0 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -5051,6 +5051,8 @@ void mas_validate_limits(struct ma_state *mas) { int i; unsigned long prev_piv = 0; + void **slots = ma_get_slots(mte_to_node(mas->node), + mte_node_type(mas->node)); if (mte_is_root(mas->node)) return; // all limits are fine here. @@ -5061,6 +5063,14 @@ void mas_validate_limits(struct ma_state *mas) if (!piv) break; + if (!mte_is_leaf(mas->node)) { + if (!slots[i]) + pr_err(MA_PTR"[%u] cannot be null\n", + mas_mn(mas), i); + + MT_BUG_ON(mas->tree, !slots[i]); + } + if (prev_piv > piv) { pr_err(MA_PTR"[%u] piv %lu < prev_piv %lu\n", mas_mn(mas), i, piv, prev_piv); @@ -5083,6 +5093,8 @@ void mas_validate_limits(struct ma_state *mas) MT_BUG_ON(mas->tree, piv > mas->max); } prev_piv = piv; + if (piv == mas->max) + break; } } diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index 41005574cd86..ae13a3c4aae4 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -32365,9 +32365,22 @@ static noinline void check_gap_combining(struct maple_tree *mt) xa_mk_value(seq400[8])); mtree_test_store_range(mt, seq400[10], seq400[11], xa_mk_value(seq400[10])); + mt_validate(mt); mt_set_non_kernel(0); mtree_destroy(mt); } +static noinline void check_node_overwrite(struct maple_tree *mt) +{ + int i, max = 4000; + + for (i = 0; i < max; i++) { + mtree_test_store_range(mt, i*100, i*100 + 50, xa_mk_value(i*100)); + } + + mtree_test_store_range(mt, 319951, 367950, NULL); + mt_dump(mt); + mt_validate(mt); +} static void check_dfs_preorder(struct maple_tree *mt) { @@ -32646,6 +32659,10 @@ static int maple_tree_seed(void) check_gap_combining(&tree); mtree_destroy(&tree); + mtree_init(&tree, MAPLE_ALLOC_RANGE); + check_node_overwrite(&tree); + mtree_destroy(&tree); + rcu_barrier(); pr_info("maple_tree: %u of %u tests passed\n", maple_tree_tests_passed, maple_tree_tests_run); -- 2.50.1