From 81986f380b95bcf68673beef1482c1b4dead1a91 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Fri, 17 Apr 2020 15:19:47 -0400 Subject: [PATCH] maple_tree: Fix limits check with retry entries When entries are relocated, the retry entry may not fall within the limits of this node as it has been relocated to the next node. Also, add define U8_MAX UCHAR_MAX in test code. Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 16 ++--- lib/test_maple_tree.c | 77 +++++++++++++++++++++ tools/testing/radix-tree/linux/maple_tree.h | 1 + 3 files changed, 86 insertions(+), 8 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 75cac4a7fe7d..9a1aa95dafea 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -2201,7 +2201,7 @@ static inline enum maple_type mas_determine_type(struct ma_state *mas, * mas_may_move_gap() - May move the gap to the proceeding node. * * 1. Check back for a gap and move it - * 2. check front for a gap. + * 2. Check front for a gap. * Ensure we cover the scenario where there is an empty node due to allocation * failures - Move the gap wherever it can go and free this node. */ @@ -2241,7 +2241,7 @@ static inline void mas_may_move_gap(struct ma_state *mas) break; } while (new_end--); - if (new_end == UCHAR_MAX) { + if (new_end == U8_MAX) { new_end = 0; empty = true; } @@ -2275,7 +2275,7 @@ static inline void mas_may_move_gap(struct ma_state *mas) if (end == new_end) // no gap at back again. return; - if (new_end == UCHAR_MAX) { + if (new_end == U8_MAX) { new_end = 0; empty = true; } @@ -3625,10 +3625,10 @@ use_left: mas_adopt_children(mas, mas->node); // Redirect reads to the new node. - mte_set_pivot(p_mas->node, mte_parent_slot(mas->node), r_mas->max); + mas_set_safe_pivot(p_mas, mte_parent_slot(mas->node), r_mas->max); // indicate to skip this slot. mte_set_rcu_slot(p_mas->node, mte_parent_slot(r_mas->node), - XA_SKIP_ENTRY); + XA_SKIP_ENTRY); if (mt_is_alloc(mas->tree)) @@ -5532,12 +5532,13 @@ void mas_validate_limits(struct ma_state *mas) for (i = 0; i < mt_slot_count(mas->node); i++) { unsigned long piv = mas_get_safe_pivot(mas, i); + void *entry; if (!piv) break; + entry = mas_get_rcu_slot(mas, i); if (prev_piv > piv) { - void *entry = mas_get_rcu_slot(mas, i); if (!mt_will_coalesce(entry)) { pr_err(MA_PTR"[%u] %lu < %lu\n", mas_mn(mas), i, piv, prev_piv); @@ -5547,7 +5548,6 @@ void mas_validate_limits(struct ma_state *mas) } if (piv < mas->min) { - void *entry = mas_get_rcu_slot(mas, i); if (!mt_will_coalesce(entry)) { if (piv < mas->min) @@ -5558,7 +5558,7 @@ void mas_validate_limits(struct ma_state *mas) MT_BUG_ON(mas->tree, piv < mas->min); } } - if (piv > mas->max) { + if ((piv > mas->max) && !xa_is_retry(entry)) { pr_err(MA_PTR"[%u] %lu > %lu\n", mas_mn(mas), i, piv, mas->max); mt_dump(mas->tree); diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index d283dffaaca6..fda68625687f 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -10763,6 +10763,76 @@ STORE, 140590376587264, 140590376591359, STORE, 140590376591360, 140590376595455, */ }; + unsigned long set21[] = { +STORE, 93874710941696, 93874711363583, +STORE, 93874711367680, 93874711408639, +STORE, 93874711408640, 93874711412735, +STORE, 93874720989184, 93874721124351, +STORE, 140708365086720, 140708365099007, +STORE, 140708365099008, 140708367192063, +STORE, 140708367192064, 140708367196159, +STORE, 140708367196160, 140708367200255, +STORE, 140708367200256, 140708367667199, +STORE, 140708367667200, 140708369760255, +STORE, 140708369760256, 140708369764351, +STORE, 140708369764352, 140708369768447, +STORE, 140708369768448, 140708369784831, +STORE, 140708369784832, 140708371877887, +STORE, 140708371877888, 140708371881983, +STORE, 140708371881984, 140708371886079, +STORE, 140708371886080, 140708371902463, +STORE, 140708371902464, 140708373995519, +STORE, 140708373995520, 140708373999615, +STORE, 140708373999616, 140708374003711, +STORE, 140708374003712, 140708375662591, +STORE, 140708375662592, 140708377759743, +STORE, 140708377759744, 140708377776127, +STORE, 140708377776128, 140708377784319, +STORE, 140708377784320, 140708377800703, +STORE, 140708377800704, 140708377899007, +STORE, 140708377899008, 140708379992063, +STORE, 140708379992064, 140708379996159, +STORE, 140708379996160, 140708380000255, +STORE, 140708380000256, 140708380016639, +STORE, 140708380016640, 140708380045311, +STORE, 140708380045312, 140708382138367, +STORE, 140708382138368, 140708382142463, +STORE, 140708382142464, 140708382146559, +STORE, 140708382146560, 140708382298111, +STORE, 140708382298112, 140708384391167, +STORE, 140708384391168, 140708384395263, +STORE, 140708384395264, 140708384399359, +STORE, 140708384399360, 140708384407551, +STORE, 140708384407552, 140708384497663, +STORE, 140708384497664, 140708386590719, +STORE, 140708386590720, 140708386594815, +STORE, 140708386594816, 140708386598911, +STORE, 140708386598912, 140708386865151, +STORE, 140708386865152, 140708388958207, +STORE, 140708388958208, 140708388974591, +STORE, 140708388974592, 140708388978687, +STORE, 140708388978688, 140708388982783, +STORE, 140708388982784, 140708389011455, +STORE, 140708389011456, 140708391108607, +STORE, 140708391108608, 140708391112703, +STORE, 140708391112704, 140708391116799, +STORE, 140708391116800, 140708391260159, +STORE, 140708393291776, 140708393308159, +STORE, 140708393308160, 140708393312255, +STORE, 140708393312256, 140708393316351, +STORE, 140708393316352, 140708393353215, +STORE, 140708393353216, 140708393357311, +STORE, 140708393357312, 140708393361407, +STORE, 140708393361408, 140708393365503, +STORE, 140708393365504, 140708393369599, +STORE, 140730557042688, 140730557177855, +STORE, 140730557235200, 140730557247487, +STORE, 140730557247488, 140730557251583, +ERASE, 140708393353216, 140708393357311, +ERASE, 140708393312256, 140708393316351, +ERASE, 140708393308160, 140708393312255, +ERASE, 140708393291776, 140708393308159, + }; int cnt = 0; MA_STATE(mas, mt, 0, 0); @@ -10928,6 +10998,13 @@ STORE, 140590376591360, 140590376595455, rcu_barrier(); check_load(mt, 94849009414144, NULL); mtree_destroy(mt); + + mt_set_non_kernel(99); + mtree_init(mt, MAPLE_ALLOC_RANGE); + check_erase2_testset(mt, set21, ARRAY_SIZE(set21)); + rcu_barrier(); + mt_validate(mt); + mtree_destroy(mt); } static noinline void check_alloc_rev_range(struct maple_tree *mt) diff --git a/tools/testing/radix-tree/linux/maple_tree.h b/tools/testing/radix-tree/linux/maple_tree.h index dbf00f34d877..529b19bd47b6 100644 --- a/tools/testing/radix-tree/linux/maple_tree.h +++ b/tools/testing/radix-tree/linux/maple_tree.h @@ -1 +1,2 @@ #include "../../../../include/linux/maple_tree.h" +#define U8_MAX UCHAR_MAX -- 2.50.1